[Powered by Google Translate] [Sehemu ya 7] [Less Starehe] [Nate Hardison] [Chuo Kikuu cha Harvard] [Hii ni CS50.] [CS50.TV] 

Karibu sehemu ya 7. Shukrani kwa upepo Sandy, badala ya kuwa sehemu ya kawaida ya wiki hii, sisi ni kufanya hii kutembea-kwa njia, kupitia sehemu ya maswali. Mimi naenda kuwa kufuatia pamoja na Matatizo Kuweka 6 Specifikation, na kwenda kwa maswali yote katika Sehemu ya kifungu Maswali. Kama kuna maswali, tafadhali post haya juu ya CS50 Diskutera. 

Alright. Hebu kupata kuanza. Hivi sasa mimi nina kuangalia ukurasa 3 ya Specifikation Set Tatizo. Sisi ni kwenda kwanza kuanza kuzungumza juu ya miti binary tangu wale wana mengi ya umuhimu wa tatizo kuweka wiki hii - Tree Huffman encoding. Moja ya miundo sana kwanza data kuongelea juu ya CS50 ilikuwa safu. Kumbuka kwamba safu ni mlolongo wa mambo - wote wa aina hiyo - kuhifadhiwa haki karibu na kila mmoja katika kumbukumbu. Kama mimi na safu integer kwamba naweza kuchora kwa kutumia mtindo huu masanduku-idadi-integers - Hebu sema nina 5 katika sanduku ya kwanza, nina 7 katika pili, basi nina 8, 10, na 20 katika sanduku ya mwisho. Kumbuka, wawili kwa kweli mambo mema kuhusu safu hii ni kwamba tuna hii hutazama ya wakati kwa kipengele fulani yoyote  katika safu kama tunajua index wake. Kwa mfano, kama nataka kunyakua kipengele cha tatu katika safu - katika index 2 kutumia wetu sifuri-msingi Indexing mfumo - Mimi literally tu kufanya rahisi hisabati hesabu, hop nafasi hiyo katika safu, kujiondoa 8 kwamba ni kuhifadhiwa huko, na mimi nina nzuri ya kwenda. 

Moja ya mambo mabaya juu ya safu hii - kwamba sisi aliyesema kuhusu wakati sisi kujadiliwa orodha wanaohusishwa - ni kwamba kama nataka kuingiza kipengele katika safu hii, Mimi nina kwenda kufanya baadhi shifting kote. Kwa mfano, hii safu haki hapa ni ili sorted - Iliyopangwa katika wakipanda ili - 5, kisha 7, basi 8, kisha 10, na kisha 20 - lakini kama nataka kuingiza namba 9 ndani ya safu hii, Mimi naenda kuwa kuhama baadhi ya vipengele ili kufanya nafasi. Tunaweza kuchora nje hapa. Mimi naenda kuwa na hoja 5, 7, na kisha 8; kujenga pengo ambapo naweza kuweka 9, na kisha 10 na 20 wanaweza kwenda na haki ya 9. Hii ni aina ya maumivu kwa sababu katika hali mbaya zaidi kesi - wakati sisi ni kuwa na kuingiza ama mwanzoni au mwishoni wa safu, kulingana na jinsi sisi ni shifting - sisi inaweza kuishia kuwa kuhama wote wa mambo kwamba sasa tuko hifadhi katika safu. 

Hivyo, nini ilikuwa ni njia ya kuzunguka hili? njia ya kuzunguka hii ilikuwa kwenda njia yetu zilizounganishwa-orodha ambapo - badala ya kuhifadhi mambo ya 5, 7, 8, 10, na 20 wote karibu na kila mmoja katika kumbukumbu - nini sisi badala gani alikuwa kuhifadhi yao ya aina ya popote sisi alitaka kuhifadhi katika haya nodes orodha zilizounganishwa-ambayo mimi nina kuchora nje hapa, aina ya dharula. Na kisha sisi kushikamana kwao pamoja kwa kutumia kuyatumia haya ijayo. Naweza kuwa pointer 5-7, pointer 7-8, pointer 8-10, na hatimaye, pointer 10-20, na kisha pointer null saa 20 kuonyesha kwamba kuna kitu kushoto. biashara-off kwamba sisi hapa ni kwamba sasa kama tunataka Insert namba 9 katika orodha yetu Iliyopangwa, wote sisi kufanya ni kujenga nodi mpya na 9, waya it up kwa uhakika na mahali mwafaka, na kisha re-waya 8 kwa kumweka chini ya 9. Hiyo ni pretty kufunga, kuchukua sisi kujua hasa ambapo tunataka Insert 9. Lakini biashara-off katika kubadilishana kwa ajili ya hii ni kwamba tumekuwa sasa wamepoteza hutazama ya wakati yoyote ya kipengele fulani katika muundo wetu data. Kwa mfano, kama nataka kutafuta kipengele cha nne katika orodha hii zilizounganishwa, Mimi naenda kuwa na kuanza mwanzoni mwa orodha na kazi njia yangu kwa njia ya kuhesabu nodi-na-nodi mpaka mimi kupata moja ya nne. 

Ili kupata fursa nzuri ya kupata utendaji kuliko orodha wanaohusishwa - lakini pia kurejesha baadhi ya faida ambazo tulikuwa katika suala la insertion muda kutoka orodha wanaohusishwa - mti binary kwenda haja ya kutumia zaidi kidogo kumbukumbu. Hasa, badala ya kuwa tu moja pointer katika nodi binary mti - kama orodha zilizounganishwa-nodi gani - sisi ni kwenda kuongeza pointer pili na nodi binary mti. Kuliko kuwa moja pointer kipengele ijayo, sisi itawabidi pointer mtoto wa kushoto na mtoto wa kulia. 

Hebu chora picha kuona nini kwamba kweli inaonekana kama. Tena, mimi naenda kutumia masanduku hayo na mishale. binary mti nodi kuanza mbali na sanduku rahisi tu. Ni kwenda na nafasi kwa ajili ya thamani, na basi ni pia kwenda na nafasi kwa ajili ya mtoto wa kushoto na mtoto wa kulia. Mimi nina kwenda studio yao hapa. Sisi ni kwenda na mtoto wa kushoto, na kisha sisi itawabidi mtoto kulia. Kuna njia nyingi tofauti ya kufanya hii. Wakati mwingine kwa nafasi na urahisi, Mimi itabidi kweli kuteka ni kama mimi nina kufanya hapa juu ya chini ambapo mimi naenda kuwa thamani ya juu, na kisha mtoto wa kulia juu ya chini-kulia, na mtoto wa kushoto juu ya chini-kushoto. Tukirudi kwenye mchoro hii ya juu, tuna thamani katika sana juu, basi tuna pointer kushoto mtoto, na kisha tuna pointer haki-mtoto. 

Katika Specifikation Tatizo Set, sisi majadiliano juu ya kuchora nodi ambayo ina thamani 7, na kisha pointer kushoto mtoto kuwa ni null, na haki-pointer mtoto kuwa ni null. Tunaweza aidha kuandika mtaji null katika nafasi kwa wote mtoto wa kushoto na mtoto wa kulia, au tunaweza kuteka hii slash Ulalo kupitia katika kila masanduku zinaonyesha kwamba ni null. Mimi naenda kufanya kwamba kwa sababu tu kwamba rahisi. Nini kuona hapa ni njia mbili ya diagramming rahisi sana binary mti nodi ambapo tuna thamani 7 na kuyatumia null mtoto. 

sehemu ya pili ya mazungumzo yetu vipimo kuhusu jinsi na orodha wanaohusishwa - kumbuka, sisi tu alikuwa na kushikilia kwa kipengele sana kwanza katika orodha kukumbuka orodha nzima - na vivyo hivyo, na mti binary, sisi tu kushikilia pointer moja kwa mti ili kudumisha udhibiti wa muundo mzima wa data. Kipengele hiki maalum ya mti inaitwa nodi mizizi ya mti. Kwa mfano, kama hii nodi moja - hii nodi zenye thamani 7 kwa null kuyatumia kushoto na kulia-mtoto - walikuwa thamani tu katika mti wetu, kisha hii itakuwa ni mizizi yetu nodi. Ni mwanzo wa mti wetu. Tunaweza kuona hii kidogo wazi zaidi mara moja sisi kuanza kuongeza nodes zaidi kwa mti wetu. Hebu vuta hadi ukurasa mpya. 

Sasa tunakwenda kuchora mti ambayo ina 7 kwenye mizizi, na 3 ndani ya mtoto wa kushoto, na 9 ndani ya mtoto wa kulia. Tena, hii ni pretty rahisi. Sisi tumepewa 7, kuteka nodi kwa 3, nodi kwa 9, na mimi naenda kuweka pointer kushoto mtoto wa 7 kwa uhakika na nodi zenye 3, na pointer haki-mtoto wa nodi zenye 7 na nodi zenye 9. Sasa, tangu 3 na 9 hawana watoto wowote, tunakwenda kuweka yote ya kuyatumia yao mtoto kuwa null. Hapa, mizizi ya mti wetu sambamba na nodi zenye namba 7. Unaweza kuona kwamba kama wote tuna ni pointer nodi kwamba mizizi, tunaweza kisha kutembea kwa njia ya mti wetu na kupata nodes mtoto wote wawili - wote 3 na 9. Hakuna haja ya kudumisha kuyatumia na nodi ya kila moja juu ya mti. Alright. Sasa sisi ni kwenda kuongeza mwingine nodi ili mchoro huu. Sisi ni kwenda kuongeza nodi zenye 6, na sisi ni kwenda kuongeza hii kama mtoto wa kulia wa nodi zenye 3. Ili kufanya hivyo, mimi naenda kufuta kwamba pointer null katika 3-nodi na waya it up kwa uhakika na nodi zenye 6. Alright. 

Katika hatua hii, hebu kwenda juu kidogo ya istilahi. Kuanza, sababu ya kwamba hii inaitwa mti binary hasa ni kwamba ina kuyatumia mtoto mbili. Kuna aina nyingine ya miti ambayo kuyatumia mtoto zaidi. Hasa, mlini 'kujaribu' katika Tatizo Set 5. Utagundua kuwa katika kujaribu kuwa, alikuwa na 27 kuyatumia tofauti na watoto tofauti - moja kwa kila herufi 26 katika alfabeti ya Kiingereza, na kisha 27 kwa apostrophe - hivyo, hiyo ni sawa na aina ya mti. Lakini hapa, tangu binary ni, sisi tu kuyatumia mtoto mbili. 

Mbali na hayo nodi mzizi kwamba kuongelea, tumekuwa pia wamekuwa kutupa kuzunguka hili neno 'mtoto.' Ina maana gani kwa moja nodi kuwa mtoto wa nodi mwingine? Ni maana yake halisi ni kwamba nodi mtoto ni mtoto wa nodi mwingine kama kwamba nodi nyingine ina moja ya kuyatumia yake mtoto kuweka kwa uhakika na nodi hiyo. Ili kuweka hii katika suala thabiti zaidi, ikiwa 3 zimeelekezwa kwa moja na ya kuyatumia mtoto wa 7, kisha 3 ni mtoto wa 7. Kama tulikuwa kufikiri nini watoto wa 7 ni - vizuri, tunaona kwamba 7 ina pointer 3 na pointer 9, hivyo 9 na 3 ni watoto wa 7. Tisa hana watoto kwa sababu mtoto wake kuyatumia ni null, na 3 ana mtoto mmoja tu, 6. Sita pia ana watoto hakuna sababu wote wawili wa kuyatumia yake ni null, ambayo tutaweza kuteka hivi sasa. 

Zaidi ya hayo, sisi pia majadiliano kuhusu wazazi wa nodi fulani, na hii ni, kama d kutarajia, kinyume cha maelezo ya mtoto huyu. Kila node ina moja tu mzazi - badala ya mbili kama unaweza kutarajia kwa binadamu. Kwa mfano, mzazi wa 3 ni 7. mzazi wa 9 ni pia 7, na mzazi wa 6 ni 3. Si sana nayo. Sisi pia kuwa suala kwa majadiliano juu ya mababu na wajukuu, na zaidi kwa ujumla sisi majadiliano juu ya mababu na wazao wa nodi fulani. babu wa nodi - au mababu, badala, ya nodi - wote ni wa nodi kwamba uongo juu ya njia kutoka mizizi kwa nodi hiyo. Kwa mfano, kama mimi nina kuangalia 6 nodi, basi mababu ni kwenda kuwa wote 3 na 7. wahenga wa 9, kwa mfano, ni - kama mimi nina kuangalia 9 nodi - kisha babu wa 9 ni 7 tu. Na kizazi ni hasa reverse. Kama mimi nataka kuangalia wote wa wana wa 7, basi nina kuangalia yote ya nodi chini yake. Hivyo, nina 3, 9, na wote 6 kama wazao wa 7. 

ya muda wa mwisho kwamba tutaweza kuzungumzia ni wazo hili la kuwa ndugu. Ndugu - aina ya kufuatia pamoja juu ya maneno haya ya familia - ni nodes kuwa ni katika ngazi moja katika mti. Hivyo, 3 na 9 ni ndugu kwa sababu wao ni katika ngazi moja katika mti. Wote wawili kuwa na mzazi mmoja, 7. 6 anao ndugu hakuna sababu 9 hana watoto wowote. Na 7 hana ndugu yoyote kwa sababu ni mizizi ya mti wetu, na kuna tu milele 1 mizizi. Kwa 7 kuwa ndugu huko bila kuwa nodi juu 7. Kuna bila kuwa mzazi wa 7, katika kesi ambayo 7 itakuwa hakuna tena kuwa mizizi ya mti. Kisha kwamba mzazi mpya ya 7 ingekuwa pia kuwa na mtoto, na mtoto kwamba basi ingekuwa sibling ya 7. 

Alright. Kuendelea. Tulipoanza majadiliano yetu ya miti binary, sisi walizungumzia jinsi sisi wanakwenda matumizi yao ya kupata faida zaidi ya arrays wote na orodha zilizounganishwa. Na njia tunakwenda kufanya hivyo ni pamoja na mali hii kuagiza. Sisi tunasema kwamba mti binary kuamuru, kulingana na vipimo, ikiwa kwa kila nodi katika mti wetu, wazao wote wa wake wa kushoto - mtoto wa kushoto na wazao wote wa mtoto wa kushoto wa - kuwa na maadili kidogo, na wote wa nodi juu ya haki - mtoto wa kulia na wazao wote wa mtoto haki ya - kuwa nodes mkubwa kuliko thamani ya nodi ya sasa kwamba sisi tunataka. Tu kwa unyenyekevu, tunakwenda kudhani kwamba kuna mtu yoyote duplicate nodes katika mti wetu. Kwa mfano, katika mti huu sisi siyo kwenda kukabiliana na kesi ambapo tuna thamani 7 kwenye mizizi  na kisha sisi pia kuwa na thamani 7 mahali pengine katika mti. Katika kesi hii, utasikia taarifa kwamba mti huu ni kweli aliamuru. Tuna thamani 7 kwenye mizizi. Kila kitu kwa upande wa kushoto wa 7 - kama mimi tengua yote ya alama hizi kidogo hapa - kila kitu kwa upande wa kushoto wa 7-3 na 6 - wale maadili ni wawili chini ya 7, na kila kitu kwa haki - ambayo ni ya haki hii 9 - ni mkubwa kuliko 7. 

Hii si mti tu kuamuru zenye maadili haya, lakini hebu kuteka zaidi wachache wao. Ni kweli kuna rundo zima la njia ambazo tunaweza kufanya hivyo. Mimi naenda kutumia shorthand tu kuweka mambo rahisi ambapo - badala ya kuchora nje zima masanduku-na-mishale - Mimi tu kwenda kuteka idadi na kuongeza mishale ya kuunganisha yao. Kuanza, tutaweza kuandika tu mti yetu ya awali tena ambapo tulikuwa na 7, na kisha 3, na kisha alisema 3 nyuma ya haki ya 6, na 7 alikuwa mtoto haki ya kwamba ilikuwa 9. Alright. Nini njia nyingine kwamba tunaweza kuandika hii mti? Badala ya kuwa na 3 kuwa mtoto wa kushoto wa 7, tunaweza pia kuwa 6 kuwa mtoto wa kushoto wa 7, na kisha 3 kuwa mtoto wa kushoto wa 6. Hiyo bila kuangalia kama mti huu wa haki hapa ambapo mimi nimepata 7, kisha 6, kisha 3, na 9 juu ya haki. Sisi pia hawana kuwa na 7 kama mzizi nodi zetu. Tunaweza pia kuwa 6 kama mzizi nodi zetu. Gani kwamba kuangalia kama? Kama sisi ni kwenda kudumisha mali hii amri, kila kitu kwa upande wa kushoto wa 6 ina kuwa ndogo zaidi. Kuna mmoja tu uwezekano, na kwamba ni 3. Lakini basi kama mtoto wa kulia wa 6, tuna uwezekano mbili. Kwanza, sisi inaweza kuwa na 7 na kisha 9, au sisi inaweza kuteka ni - kama mimi nina kuhusu kufanya hapa - ambapo tuna 9 kama mtoto wa kulia wa 6, na kisha 7 kama mtoto wa kushoto wa 9. 

Sasa, 7 na 6 ni si tu inawezekana maadili kwa mizizi. Tunaweza pia kuwa 3 kuwa kwenye mizizi. Nini kinatokea kama 3 ni katika mizizi? Hapa, mambo kupata kidogo ya kuvutia. Tatu hana maadili yoyote ambayo ni ndogo zaidi, ili mzima wa kushoto upande wa mti ni kwenda tu kuwa null. Kuna si kwenda kuwa kitu chochote huko. Kwa haki, tunaweza kuorodhesha mambo katika wakipanda ili. Tunaweza kuwa na 3, kisha 6, basi 7, kisha 9. Au, tunaweza kufanya 3, kisha 6, basi 9, kisha 7. Au, tunaweza kufanya 3, kisha 7, kisha 6, basi 9. Au, 3, 7 - kweli hakuna, hatuwezi kufanya 7 tena. Hiyo ni yetu kitu kimoja huko. Tunaweza kufanya 9, na kisha kutoka 9 tunaweza kufanya 6 na kisha 7. Au, tunaweza kufanya 3, kisha 9, kisha 7, na kisha 6. 

Jambo moja kuteka mawazo yako kwa hapa ni kwamba haya miti ni kidogo weird-kuangalia. Hasa, ikiwa sisi kuangalia miti 4 upande wa kulia - Mimi itabidi kuzunguka nao, hapa - hizi miti kuangalia karibu hasa kama orodha zinazoungwa. Kila node ana mtoto mmoja tu, na hivyo hatuna yoyote ya muundo huu mti-kama kwamba sisi kuona, kwa mfano,  katika hii moja mti lone juu hapa upande wa kushoto chini. Miti hii ni kweli kuitwa degenerate miti binary, na tutaweza kuzungumzia hayo zaidi katika siku zijazo - hasa kama wewe kwenda kuchukua kozi nyingine sayansi ya kompyuta. Hizi ni miti degenerate. Hawako muhimu sana kwa sababu, kwa kweli, muundo huu imejikita  kwa mara Luke sawa na ile ya orodha zinazoungwa. Hatuna kupata kuchukua faida ya kumbukumbu ya ziada - hii pointer ziada - kwa sababu ya muundo wetu kuwa mbaya kwa njia hii. Badala ya kwenda juu na kuteka miti binary kwamba kuwa na 9 katika mizizi, ambayo ni kesi ya mwisho kwamba tunataka kuwa, tuko badala yake, katika hatua hii, kwenda kuzungumza kidogo kuhusu muda huu wengine kwamba sisi kutumia wakati wakizungumza kuhusu miti, iitwayo urefu. 

urefu wa mti ni umbali kutoka mizizi kwa nodi wengi-mbali, au badala ya idadi ya humle kwamba ingekuwa kufanya ili kuanza kutoka mizizi na kisha kuishia kwenye nodi wengi-mbali katika mti. Kama sisi kuangalia baadhi ya miti hii kuwa tumepata hapa hapa, tunaweza kuona kwamba kama sisi kuchukua mti katika kona ya juu upande wa kushoto na sisi kuanza saa 3, basi tuna kufanya 1 hop kupata 6, hop pili kwa kupata 7, na hop ya tatu kwa kupata 9. Hivyo, urefu wa mti huu ni 3. Tunaweza kufanya zoezi lile kwa miti mingine ilivyoainishwa na kijani hii, na tunaona kwamba urefu wa wote wa miti hii pia ni kweli 3. Hiyo ni sehemu ya nini inawafanya degenerate - kwamba urefu wao ni moja tu chini ya idadi ya pingili katika mti mzima. Tukiangalia mti huu nyingine kwamba wameshikiliwa na nyekundu, kwa upande mwingine, tunaona kwamba wengi-mbali jani nodes ni 6 na 9 - majani kuwa wale nodes kwamba hawana watoto. Hivyo, ili kupata kutoka nodi mzizi ama 6 au 9, tuna kufanya moja hop kupata 7 na kisha hop pili kwa kupata 9, na vivyo hivyo, tu hop pili kutoka 7 kupata 6. Hivyo, urefu wa mti huu zaidi hapa ni tu 2. Unaweza kwenda nyuma na kufanya kwamba kwa yote ya miti mengine ambayo sisi awali kujadiliwa mwanzo na 7 na 6, na utapata kwamba urefu wa yote ya miti wale pia ni 2. 

sababu tumekuwa kuzungumza juu ya kuamuru miti binary na kwa nini wao uko cool ni kwa sababu unaweza kutafuta njia yao katika njia sawa sana kutafuta juu ya safu Iliyopangwa. Hii ni mahali ambapo sisi kuzungumza juu ya kupata kwamba kuboresha lookup wakati juu ya orodha rahisi zinazoungwa. Kwa orodha wanaohusishwa - kama unataka kupata kipengele fulani - wewe ni saa bora kwenda kufanya baadhi ya aina ya tafuta linear ambapo kuanza mwanzo wa orodha na hop moja-na-moja - moja nodi na nodi moja - kupitia orodha nzima mpaka kupata chochote wewe kwa ajili ya kutafuta. Ambapo, kama una mti binary ambayo imehifadhiwa katika muundo huu nice, unaweza kweli kupata zaidi ya tafuta binary kinachoendelea ambapo wewe kugawanya na kushinda na kutafuta njia sahihi ya nusu ya mti kwa kila hatua. Hebu angalia jinsi matendo kwamba. 

Kama tuna - tena, kwenda nyuma ya mti yetu ya awali - sisi kuanza saa 7, tuna 3 upande wa kushoto, 9 juu ya haki, na chini ya 3 tuna 6. Kama tunataka kutafuta namba 6 katika mti huu, tunatarajia kuanza kwenye mizizi. Tunataka kulinganisha thamani sisi ni kuangalia kwa, kusema 6, kwa thamani kuhifadhiwa katika nodi kwamba sasa tuko kuangalia, 7, kupata kwamba 6 ni kweli chini ya 7, hivyo tunatarajia kuhamia kushoto. Kama thamani ya 6 alikuwa mkuu zaidi kuliko 7, tunataka kuwa badala wakiongozwa na haki. Kwa kuwa tunajua kwamba - kutokana na muundo wa mti wetu kuamuru binary - wote wa maadili chini ya 7 ni kwenda kuhifadhiwa ya kushoto ya 7, hakuna haja ya hata bother kuangalia kupitia upande wa kulia wa mti. Mara sisi hoja ya kushoto na tuko sasa kwenye nodi zenye 3, tunaweza kufanya hivyo kulinganisha sawa tena ambapo sisi kulinganisha na 3 6. Na tunaona kwamba wakati 6 - thamani sisi ni kuangalia kwa - ni kubwa zaidi kuliko 3, tunaweza kwenda upande wa kulia wa nodi zenye 3. Hakuna upande wa kushoto hapa, hivyo tunaweza kuwa na kupuuzwa kwamba. Lakini sisi tu kujua kwamba kwa sababu sisi ni kuangalia mti yenyewe, na tunaweza kuona kwamba mti hana watoto. 

Ni pia pretty rahisi kuangalia up 6 katika mti huu kama sisi ni kufanya hivyo wenyewe kama binadamu, lakini hebu kufuata mchakato huu mechanically kama kompyuta bila kufanya kwa kweli kuelewa algorithm. Katika hatua hii, sisi ni sasa kuangalia nodi ambayo ina 6, na sisi ni kuangalia kwa thamani 6, hivyo, kwa hakika, tumekuwa kupatikana nodi mwafaka. Sisi kupatikana thamani 6 katika mti wetu, na tunaweza kuacha tafuta wetu. Katika hatua hii, kutegemea na nini kinaendelea, tunaweza kusema, ndiyo, tumepata thamani 6, ipo katika mti wetu. Au, kama sisi ni mipango ya kuingiza nodi au kufanya kitu, tunaweza kufanya hivyo katika hatua hii. 

Hebu kufanya lookups wanandoa zaidi tu kuona jinsi hii matendo. Hebu tuangalie kile kinachotokea kama sisi tulikuwa na kujaribu na kuangalia juu ya thamani ya 10. Kama sisi kuangalia juu ya thamani ya 10, tunataka kuanza kwenye mizizi. Tunatarajia kuona kwamba 10 ni kubwa kuliko 7, hivyo tunatarajia hoja ya kulia. Tunatarajia kupata 9 na kulinganisha 9-10 na kuona kwamba ni kweli 9 chini ya 10. Hivyo tena, tunatarajia kujaribu hoja ya haki. Lakini katika hatua hii, tunatarajia taarifa kwamba sisi ni saa nodi null. Kuna kitu pale. Kuna kitu ambapo 10 lazima. Hii ni wapi tunaweza kuripoti kushindwa - kwamba kuna shaka hakuna 10 katika mti. Na hatimaye, hebu kwenda kupitia kesi ambapo sisi ni kujaribu kuangalia up 1 katika mti. Hii ni sawa na kile kinachotokea kama sisi kuangalia juu 10, ila badala ya kwenda kulia, tunakwenda kwenda kushoto. Sisi kuanza saa 7 na kuona kwamba ni chini ya 1 7, hivyo sisi hoja ya upande wa kushoto. Sisi kupata 3 na kuona kwamba ni chini ya 1 3, hivyo tena sisi kujaribu hoja ya upande wa kushoto. Katika hatua hii tuna nodi null, hivyo tena tunaweza kuripoti kushindwa. 

Kama wewe unataka kujifunza zaidi kuhusu miti binary, kuna rundo zima la matatizo ya furaha kidogo kwamba unaweza kufanya na wao. Mimi zinaonyesha kufanya mazoezi kuchora nje ya diagrams hizi moja-na-moja na kufuatia kwa njia zote za hatua mbalimbali, kwa sababu hii kuja katika super-Handy si tu wakati wewe kufanya encoding Huffman tatizo kuweka lakini pia katika kozi ya baadaye - tu kujifunza jinsi ya kuchora nje miundo hizi data na kufikiria njia matatizo kalamu na karatasi au, katika kesi hii, iPad na stylus. 

Katika hatua hii, ingawa, tunakwenda na hoja juu ya kufanya baadhi ya mazoezi ya coding na kweli kucheza na miti hii binary na kuona. Mimi nina kwenda kubadili nyuma juu ya kompyuta yangu. Kwa sehemu hii ya sehemu, badala ya kutumia CS50 Run au Spaces CS50, Mimi naenda kutumia appliance. 

Kufuatia pamoja na vipimo Set Tatizo, Mimi naona kwamba natakiwa kufungua appliance, kwenda folda yangu Dropbox, kutengeneza folda aitwaye sehemu 7, na kisha kuunda faili inayoitwa binary_tree.c. Hapa sisi kwenda. Mimi nimepata appliance tayari wazi. Mimi naenda kuvuta terminal. Mimi nina kwenda kwa folda Dropbox, kufanya saraka kuitwa section7, na kuona ni kabisa tupu. Sasa mimi nina kwenda kufungua binary_tree.c. Alright. Hapa sisi kwenda - faili tupu. 

Turudi kwa vipimo. vipimo anauliza kuunda aina mpya ya ufafanuzi kwa binary mti nodi zenye maadili int - tu kama maadili ambayo sisi akauchomoa katika diagramming yetu mbele. Sisi ni kwenda kutumia boilerplate hii typedef kwamba tumefanya haki hapa kwamba unapaswa kutambua kutoka Tatizo Set 5 - kama alivyofanya hash meza njia ya mshindi mpango speller. Pia ni lazima utambue ni kutoka sehemu ya mwisho wa wiki ambapo sisi aliyesema kuhusu orodha zinazoungwa. Sisi tumepewa hii typedef ya nodi struct, na tumekuwa aliyopewa hii nodi struct hii jina ya nodi struct kabla ili tuweze basi rejea ni tangu tutaweza wanataka kuwa na kuyatumia nodi struct kama sehemu ya struct wetu, lakini tumekuwa kisha kuzizunguka hii - au tuseme, iliyoambatanishwa hii - katika typedef hivyo kwamba, baadaye katika kanuni, tunaweza kutaja struct hii kama nodi tu badala ya nodi struct. 

Hii ni kwenda kuwa ni sawa na ufafanuzi moja moja-zilizounganishwa orodha kuwa tuliona wiki iliyopita. Ili kufanya hivyo, hebu tu kuanza kwa kuandika nje boilerplate. Tunajua kwamba sisi kuwa na thamani integer, hivyo tutaweza kuweka katika thamani int, na kisha badala ya kuwa moja tu pointer kipengele ijayo - kama tulivyofanya na orodha moja moja-zilizounganishwa - sisi itawabidi kuyatumia mtoto wa kushoto na kulia. Hiyo ni pretty rahisi mno - struct nodi * kushoto mtoto; na struct nodi * haki ya mtoto;. Cool. Kwamba inaonekana kama mwanzo nzuri. Turudi kwa vipimo. 

Sasa tunahitaji kutangaza kimataifa nodi * variable kwa mizizi ya mti. Sisi ni kwenda kufanya dunia hii tu kama sisi alifanya pointer kwanza katika orodha yetu wanaohusishwa pia kimataifa. Hii ilikuwa ili katika kazi ya kwamba sisi kuandika hatuna kuweka kupita kuzunguka mizizi hii - ingawa tutaweza kuona kwamba kama wewe kufanya unataka kuandika kazi hizi recursively, inaweza kuwa bora hata kupita ni kuzunguka kama kimataifa katika nafasi ya kwanza na badala yake initialize ndani ya nchi katika kazi yako kuu. Lakini, tutaweza kufanya hivyo kimataifa kuanza. Tena, tutaweza kutoa michache ya mazingira, na mimi nina kwenda kutangaza nodi * mizizi. Tu kuhakikisha kwamba mimi si kuondoka uninitialized, Mimi naenda kuweka sawa kwa null. Sasa, katika kazi kuu - ambayo tutaweza kuandika kweli haraka hapa hapa - int kuu (int argc, const Char * argv []) - na mimi nina kwenda kuanza kutangaza safu yangu argv kama const hivyo tu kwamba mimi kujua kwamba wale hoja ni hoja kwamba mimi pengine hawataki kurekebisha. Kama mimi nataka kurekebisha yao mimi lazima pengine kuwa maamuzi nakala yao. Utaona hii mengi katika code. Ni faini ama njia. Ni faini ya kuondoka ni kama - omit const kama Ningependa. Mimi kawaida kuiweka katika hivyo tu kwamba mimi mwenyewe kuwakumbusha  kwamba mimi pengine hawataki kurekebisha hoja hizo. 

Kama kawaida, mimi nina kwenda pamoja na hii ya kurudi 0 line mwisho wa kuu. Hapa, nami initialize mizizi yangu nodi. Kama ulivyo hivi sasa, mimi nimepata pointer hiyo kuweka null, hivyo ni akionyesha chochote. Ili kweli kuanza ujenzi wa nodi, Mimi kwanza haja ya kutenga kumbukumbu kwa ajili yake. Mimi naenda kufanya kwamba kwa kufanya kumbukumbu juu ya lundo kutumia malloc. Mimi naenda kuweka mizizi sawa na matokeo ya malloc, na mimi naenda kutumia operator sizeof kwa mahesabu ya ukubwa wa nodi. sababu kwamba mimi kutumia sizeof nodi kama kinyume na, kusema, kufanya kitu kama hii - malloc (4 + 4 4) au malloc 12 - ni kwa sababu nataka code yangu kuwa kama sambamba iwezekanavyo. Mimi nataka kuwa na uwezo wa kuchukua c. SVG, kukusanya juu appliance, na kisha kukusanya juu ya 64-bit yangu Mac - au juu ya usanifu tofauti kabisa - na mimi nataka yote hii kwa kazi sawa. 

Kama mimi nina kufanya mawazo kuhusu ukubwa wa vigezo - ukubwa wa int au ukubwa wa pointer - basi mimi nina pia kufanya mawazo kuhusu aina ya architectures ambayo code yangu unaweza mafanikio kukusanya wakati kukimbia. Daima kutumia sizeof kinyume na manually summing mashamba struct. Sababu nyingine ni kwamba huenda kuna pia kuwa padding kwamba compiler unaweka katika struct. Hata tu summing mashamba binafsi si kitu ambacho kwa kawaida wewe unataka kufanya, hivyo, kufuta kwamba mstari. Sasa, kwa kweli hii initialize nodi mizizi, Mimi naenda kuwa kuziba katika maadili kwa kila moja ya mashamba yake tofauti. Kwa mfano, kwa thamani najua nataka initialize kwa 7, na kwa sasa mimi naenda kuweka mtoto wa kushoto kuwa null na mtoto haki ya kuwa pia null. Mkuu! Tumefanya kwamba sehemu ya spec. 

vipimo chini chini ya ukurasa wa 3 anayeniuliza kujenga nodes tatu zaidi - moja zenye 3, moja zenye 6, na moja kwa 9 - na kisha waya yao juu hivyo inaonekana hasa kama mti mchoro wetu kwamba sisi walikuwa wanazungumza juu ya awali. Hebu kufanya hivyo pretty haraka hapa. Utaona kweli haraka kwamba mimi nina kwenda kuanza kuandika rundo la code duplicate. Mimi naenda kujenga * nodi na mimi nina kwenda kumwita tatu. Mimi naenda kuweka sawa na malloc (sizeof (node)). Mimi naenda kuweka tatu-> thamani = 3. Tatu -> left_child = null; tatu -> kulia _child = null; vilevile. Hiyo inaonekana pretty sawa na initializing mizizi, na kwamba ni nini hasa Mimi naenda kuwa kufanya kama mimi kuanza initializing 6 na 9 vilevile. Mimi itabidi kufanya hivyo kweli haraka hapa - kwa kweli, mimi naenda kufanya nakala kidogo na kuweka, na kuhakikisha kwamba mimi - alright.  Sasa, nimekuwa got it kunakiliwa na siwezi kwenda mbele na kuweka hii sawa na 6. Unaweza kuona kwamba hii inahitaji muda na sio super-ufanisi. Katika kidogo kidogo tu, tutaweza kuandika kazi kwamba kufanya hili kwa ajili yetu. Nataka kuchukua nafasi hii kwa 9, badala ya kuwa na 6. 

Sasa sisi tumepewa yote ya nodi yetu umba na initialized. Sisi tumepewa mizizi yetu kuweka sawa na 7, au zenye thamani 7, nodi zetu zenye 3, nodi zetu zenye 6, na node zetu zenye 9. Katika hatua hii, wote sisi kufanya ni waya kila kitu juu. sababu mimi initialized kuyatumia yote null ni hivyo tu kwamba mimi kufanya kuwa na uhakika Sina kuyatumia yoyote uninitialized huko kwa ajali. Na pia tangu, katika hatua hii, mimi tu kweli kuungana nodes kwa kila mmoja - kwa wale kwamba wao ni kushikamana na kweli - mimi si kwenda kwa njia na kufanya kuhakikisha kwamba nulls wote ni katika huko katika maeneo husika. 

Kuanzia saa mzizi, najua kwamba mzizi wa mtoto wa kushoto ni 3. Najua kwamba mzizi wa mtoto ni haki ya 9. Baada ya hapo, tu ya mtoto mwingine kwamba nina kushoto na wasiwasi kuhusu ni 3 wa kulia wa mtoto, ambayo ni 6. Katika hatua hii, yote inaonekana pretty nzuri. Tutaweza kufuta baadhi ya mistari haya. Sasa kila kitu inaonekana pretty nzuri. Turudi kwa vipimo yetu na kuona nini tunapaswa kufanya ijayo. 

Katika hatua hii, tuna kuandika kazi iitwayo 'ina' kwa mfano wa 'ina bool (int thamani)'. Na hii ina kazi ni kwenda na kurudi kweli  kama mti alisema kwa variable wetu wa kimataifa mzizi  ina thamani kupita katika kazi na uongo vinginevyo. Hebu kwenda mbele na kufanya hivyo. Hii ni kwenda kuwa hasa kama lookup kwamba sisi alifanya kwa mkono juu ya iPad kidogo tu iliyopita. Hebu zoom nyuma katika kidogo na kitabu juu. Sisi ni kwenda kuweka hii kazi haki juu ya kazi yetu kuu hivyo kwamba hatuna la kufanya aina yoyote ya prototyping. Hivyo, bool ina (int thamani). Kuna sisi kwenda. Kuna boilerplate wetu tamko. Tu kuhakikisha kwamba hii kukusanya, Mimi nina kwenda mbele na kuweka sawa tu kurudi uongo. Hivi sasa kazi hii tu haiwezi kufanya kitu chochote na daima taarifa kwamba thamani ya kwamba sisi ni kuangalia kwa si katika mti. 

Katika hatua hii, ni pengine wazo nzuri - tangu tumekuwa imeandikwa rundo zima la code na hatuna hata walijaribu kupima bado - kuhakikisha kwamba wote compiles. Kuna michache ya mambo ambayo sisi kufanya ili kuhakikisha kwamba hii kweli kukusanya. Kwanza, kuona kama sisi tumekuwa kutumia kazi yoyote katika maktaba yoyote kwamba sisi bado pamoja. kazi tumekuwa kutumika hadi sasa ni malloc, na kisha tumekuwa pia wamekuwa kutumia aina hii - aina hii nonstandard iitwayo 'bool' - ambayo ni pamoja na katika faili kiwango bool header. Sisi dhahiri wanataka ni pamoja bool.h kiwango kwa ajili ya aina bool, na sisi pia wanataka ni pamoja # lib.h kiwango kwa maktaba ya kiwango kuwa ni pamoja na malloc, na bure, na hiyo yote. Hivyo, zoom nje, sisi ni kwenda kuacha. Hebu jaribu na kuhakikisha kwamba hii kweli alifanya kukusanya. Tunaona kwamba hana, hivyo sisi ni juu ya kufuatilia haki. 

Hebu kufungua binary_tree.c tena. Ni compiles. Hebu kwenda chini na kuhakikisha kwamba sisi kuingiza wito kwa baadhi ya kazi yetu ina - tu kuhakikisha kwamba hayo ni yote vizuri na nzuri. Kwa mfano, wakati sisi tulikuwa lookups baadhi katika mti yetu mapema, sisi alijaribu kuangalia juu maadili 6, 10, na 1, na sisi alijua kwamba alikuwa 6 katika mti, 10 hakuwamo katika mti, na 1 hakuwa katika mti ama. Hebu kutumia simu hizo sampuli kama njia ya kufikiri kama au si yetu ina kazi ni kazi. Ili kufanya hivyo, mimi naenda kutumia kazi printf, na sisi ni kwenda magazeti nje matokeo ya wito kwa ina. Mimi naenda kuweka katika string "ina (% d) = kwa sababu  tunakwenda kuziba katika thamani ya kwamba sisi ni kwenda kuangalia, na =% s \ n "na kutumia kama format string yetu. Sisi ni tu kwenda kuona - literally magazeti nje juu ya screen - kile kinachoonekana kama wito kazi. Hii si kweli wito kazi.  Hii ni kamba tu iliyoundwa na kuangalia kama simu kazi. 

Sasa, sisi ni kwenda kuziba katika maadili. Sisi ni kwenda kujaribu ina juu ya 6, na kisha nini tunakwenda kufanya hapa ni kutumia operator ternary. Hebu angalia - ina 6 - hivyo, sasa nimepata zilizomo 6 na kama ina 6 ni kweli, kamba kwamba sisi ni kwenda kutuma format tabia% s ni kwenda kuwa string "kweli". Hebu kitabu juu kidogo. Vinginevyo, tunataka kutuma string "uongo" ikiwa ina anarudi 6 uongo. Hii ni kidogo goofy-kuangalia, lakini Mimi takwimu mimi ili kama vile kuonyesha nini operator ternary inaonekana kama tangu sisi si kuonekana ni kwa muda. Hii itakuwa nzuri, Handy njia ya kufikiri kama yetu ina kazi ni kazi. Mimi naenda kitabu nyuma zaidi kwa upande wa kushoto, na mimi naenda na nakala na kuweka mstari huu mara chache. Ni iliyopita baadhi ya maadili haya ya karibu, hivyo hii itakuwa ni 1, na hii ni kwenda kuwa 10. 

Katika hatua hii sisi tumepewa ina nzuri kazi. Sisi tumepewa baadhi ya vipimo, na tutaweza kuona kama hii yote matendo. Katika hatua hii tumekuwa imeandikwa baadhi zaidi code. Wakati wa kuacha nje na kuhakikisha kwamba kila kitu bado compiles. Quit nje, na sasa hebu jaribu kufanya binary mti tena. Naam, inaonekana kama sisi tumepewa makosa, na tumekuwa got hii wazi kutangaza kazi maktaba printf. Inaonekana kama tunahitaji kwenda katika na # pamoja standardio.h. Na kwa kuwa, kila kitu lazima kukusanya. Sisi sote ni nzuri. Sasa hebu jaribu mbio mti binary na kuona nini kinatokea. Hapa sisi ni,. / Binary_tree, na sisi kuona kwamba, kama sisi inatarajiwa - kwa sababu sisi si kutekelezwa ina bado, au tuseme, tumekuwa tu ya kuweka katika kurudi uongo - tunaona kwamba ni tu kurudi uongo kwa ajili yao wote, hivyo hiyo ni wote kufanya kazi kwa zaidi ya sehemu uungwana vizuri. 

Turudi katika kweli na kutekeleza ina katika hatua hii. Mimi naenda kitabu chini, zoom katika, na - kumbuka, algorithm kwamba sisi kutumika ni kwamba sisi ilianza kwenye nodi mzizi na kisha katika kila nodi kwamba sisi kukutana, sisi kufanya kulinganisha, na kwa kuzingatia kwamba sisi kulinganisha ama hoja ya mtoto wa kushoto au kulia kwa mtoto. Hii ni kwenda kuangalia sana sawa na code binary tafuta kwamba sisi aliandika mapema katika mrefu. Wakati sisi kuanza mbali, tunajua kwamba tunataka kushikilia nodi sasa kwamba sisi ni kuangalia, na node ya sasa ni kwenda initialized na nodi ya mizizi. Na sasa, sisi ni kwenda kuendelea kupitia mti, na kukumbuka kwamba yetu kuacha hali -  wakati sisi kwa kweli alifanya kazi kupitia mfano kwa mkono - ilikuwa wakati sisi wamekutana nodi null, si wakati sisi inaonekana katika mtoto null, lakini badala ya wakati sisi kwa kweli wakiongozwa na nodi katika mti na kukuta kuwa tuko kwenye nodi null. Sisi ni kwenda iterate mpaka cur si sawa kwa null. Na nini ni sisi kwenda kufanya? Sisi ni kwenda kupima kama (cur -> thamani == thamani), basi tunajua kwamba tumekuwa kweli kupatikana nodi kwamba sisi ni kuangalia kwa. Hivyo hapa, tunaweza kurudi kweli. Vinginevyo, tunataka kuona kama au thamani ni chini ya thamani. Kama thamani ya nodi ya sasa ni chini ya thamani sisi ni kuangalia kwa, tunakwenda hoja ya haki. Hivyo, cur = cur -> right_child; na vinginevyo, tunakwenda kwa hoja na kushoto. cur = cur -> left_child;. Pretty rahisi. 

Wewe pengine kutambua kitanzi kwamba inaonekana sana sawa na hii kutoka binary tafuta mapema katika neno, ila basi tulikuwa kushughulika na chini, katikati, na juu. Hapa, sisi tu na kuangalia thamani ya sasa, hivyo ni nzuri na rahisi. Hebu hakikisha code hii ni kazi. Kwanza, kuhakikisha inaandaa. Inaonekana kama ni gani. Hebu jaribu mbio. Na hakika, Prints nje kila kitu kwamba sisi ilivyotarajiwa. Ni hupata 6 katika mti, asipate 10 kwa sababu 10 si katika mti, asipate 1 aidha kwa sababu 1 pia si katika mti. Cool stuff. 

Alright. Turudi kwa vipimo yetu na kuona nini ijayo. Sasa, ni anataka kuongeza nodes baadhi zaidi kwa mti wetu. Ni anataka kuongeza 5, 2, na 8, na kuhakikisha kwamba yetu ina code bado kazi kama ilivyotarajiwa. Hebu kwenda kufanya hivyo. Katika hatua hii, badala ya kufanya kwamba nakala annoying na kuweka tena, hebu kuandika kazi kwa kweli kujenga nodi. Kama sisi kitabu chini njia yote kuu, tunaona kwamba sisi tumekuwa kufanya hii sawa sana code tena na tena kila wakati kwamba tunataka kujenga nodi. 

Hebu kuandika kazi kwamba mapenzi kweli kujenga nodi kwa ajili yetu na kurudi. Mimi naenda kuiita build_node. Mimi nina kwenda kujenga nodi na thamani fulani. Zoom katika hapa. Jambo la kwanza mimi naenda kufanya ni kweli kujenga nafasi ya nodi kwenye chungu. Hivyo, nodi * n = malloc (sizeof (node)); n -> thamani = thamani; na kisha hapa, mimi tu kwenda initialize yote ya mashamba kwa kuwa sahihi maadili. Na mwishoni sana, tutaweza kurudi nodi zetu. Alright. Jambo moja kukumbuka ni kwamba kazi hii hapa hapa ni kwenda na kurudi pointer kumbukumbu ambayo imekuwa chungu-zilizotengwa. Nini nzuri kuhusu hili ni kwamba hii nodi sasa - tuna kutangaza juu ya lundo sababu kama sisi amekiri kuwa ni juu ya stack sisi bila kuwa na uwezo wa kufanya hivyo katika kazi hii kama hii. Kumbukumbu ambayo kwenda nje ya wigo na itakuwa batili kama tulijaribu kupata hiyo baadaye. Tangu tunatangaza lundo-zilizotengwa kumbukumbu, sisi ni kwenda na kuchukua huduma ya kumkomboa hivyo baadaye kwa ajili ya mpango wetu si leak yoyote kumbukumbu. Sisi tumekuwa punting juu ya kwamba kwa ajili ya kila kitu kingine katika code tu kwa ajili ya unyenyekevu wa wakati huo, lakini kama wewe milele kuandika kazi ambayo inaonekana kama hii ambapo nimepata - baadhi kuiita malloc au realloc ndani - unataka kufanya kuhakikisha kwamba kuweka aina fulani ya maoni juu hapa kuwa anasema, hey, unajua, anarudi nodi lundo-zilizotengwa initialized na thamani kupita katika. Na kisha unataka kufanya kuhakikisha kwamba kuweka katika baadhi ya aina ya note kwamba anasema mpigaji lazima huru kumbukumbu akarudi. Kwa njia hiyo, kama mtu milele huenda na anatumia kwamba kazi, wanajua kwamba kila wao kupata nyuma kutoka kazi ambayo wakati fulani haja ya kuwa huru. 

Kutokana kwamba wote ni vizuri na nzuri hapa, tunaweza kwenda chini katika kanuni yetu na kuchukua nafasi yote ya mistari haya wa kulia hapa na wito kwa kazi yetu kujenga nodi. Hebu kufanya kuwa kweli haraka. sehemu moja kwamba sisi siyo kwenda kuchukua nafasi hii ni sehemu chini hapa chini ambapo sisi kweli waya juu nodes kwa uhakika na kila mmoja, kwa sababu hatuwezi kufanya kazi katika yetu. Lakini, hebu kufanya mizizi = build_node (7); nodi * tatu = build_node (3); nodi * sita = build_node (6); nodi * tisa = build_node (9);. Na sasa, sisi pia alitaka kuongeza nodes kwa - nodi * tano = build_node (5); nodi * nane = build_node (8); na nini ilikuwa nodi nyingine? Hebu angalia hapa. Sisi alitaka pia kuongeza 2 - nodi * mbili = build_node (2);. Alright. Katika hatua hii, tunajua kwamba sisi tumepewa 7, 3, 9, na 6 wote wired up ipasavyo, lakini nini kuhusu 5, 8, na 2? Kuweka kila kitu katika utaratibu sahihi, tunajua kwamba watatu mtoto haki ni 6. Hivyo, kama sisi ni kwenda kuongeza 5, 5 pia ni katika upande wa kulia wa mti ambayo 3 ni mizizi, hivyo ni kama mtoto 5 wa kushoto wa 6. Tunaweza kufanya hili kwa kusema, sita -> left_child = tano; na kisha 8 ni kama mtoto wa kushoto wa 9, hivyo tisa -> left_child = nane; na kisha 2 ni mtoto wa kushoto wa 3, ili tuweze kufanya hivyo hapa juu - wewe -> left_child = mbili;. Kama hakuwa kabisa kufuata pamoja na kwamba, mimi zinaonyesha atayateka mwenyewe. 

Alright. Hebu kuokoa hii. Hebu kwenda nje na kuhakikisha inaandaa, na kisha tunaweza kuongeza katika wito wetu ina. Inaonekana kama kila kitu bado compiles. Hebu kwenda katika na kuongeza katika baadhi ina wito. Tena, mimi naenda kufanya kidogo ya nakala na kuweka. Sasa hebu kutafuta 5, 8, na 2. Alright. Hebu kuhakikisha kwamba hii yote inaonekana nzuri bado. Mkuu! Ila na kuacha. Sasa wacha kufanya, kukusanya, na sasa hebu kukimbia. Kutokana na matokeo, inaonekana kama kila kitu ni kazi nzuri tu na vizuri. Mkuu! Hivyo sasa sisi tumepewa ina yetu inafanya kazi zilizoandikwa. Hebu hoja juu na kuanza kazi juu ya namna ya kuingiza nodes katika mti tangu, kama sisi ni haki ya kufanya hivyo sasa, mambo si sana pretty. 

Kama sisi kurudi nyuma kwa vipimo, inauliza sisi kuandika kazi kuitwa Insert - tena, kurudi bool kwa kama au sisi inaweza kweli Insert nodi katika mti - na kisha thamani kuingiza ndani ya mti ni maalum kama hoja tu kwa Insert kazi yetu. Tutarudi kweli kama tunaweza kweli Insert nodi zenye thamani ya mti, ambayo ina maana kwamba sisi, mmoja, alikuwa na kumbukumbu ya kutosha, na kisha mbili, nodi kwamba hakuwa tayari zipo katika mti tangu - kumbuka, sisi si kwenda kuwa na maadili duplicate katika mti, tu kufanya mambo rahisi. Alright. Nyuma kwa kificho. Fungua it up. Zoom katika kidogo, kisha kitabu chini. Hebu kuweka kazi Insert kulia hapo juu ina. Tena, ni kwenda kuitwa bool Insert (int thamani). Kutoa ni kidogo nafasi zaidi, na kisha, kama default, tulenge katika kurudi uongo mwishoni sana. Sasa chini kwa chini, hebu kwenda mbele na badala ya kujenga manually nodes katika kuu wenyewe na wiring yao juu na kumweka kwa kila mengine kama sisi ni kufanya, tutaweza kutegemea Insert kazi yetu kufanya hivyo. Sisi si kuwategemea Insert kazi yetu ya kujenga mti mzima kutoka scratch bado tu, lakini badala tutaweza kujikwamua mistari haya - we'll maoni nje mistari haya - kuwa kujenga nodes 5, 8, na 2. Na badala yake, tutaweza kuingiza wito kwa Insert kazi yetu kuhakikisha kwamba kweli kazi. Hapa sisi kwenda. 

Sasa tumekuwa maoni nje mistari haya. Sisi tu 7, 3, 9, na 6 katika mti wetu katika hatua hii. Ili kuhakikisha kwamba hii yote ni kazi, tunaweza zoom nje, kufanya binary wetu mti, kukimbia, na tunaweza kuona kwamba ina sasa anatuambia kwamba sisi ni haki kabisa - 5, 8, na 2 ni tena katika mti. Nenda nyuma katika kanuni, na jinsi sisi kwenda Insert? Kumbuka sisi alivyofanya tulipokuwa kweli inserting 5, 8, na 2 hapo awali. Sisi alicheza mchezo huo Plinko ambapo sisi ilianza saa mizizi, akashuka mti mmoja kwa mmoja mmoja mpaka sisi kupatikana pengo inafaa, na kisha sisi wired katika nodi katika doa mwafaka. Sisi ni kwenda kufanya kitu kimoja. Hii ni kimsingi kama kuandika kificho kwamba sisi kutumika katika ina kazi kupata doa ambapo nodi lazima, na kisha sisi ni kwenda tu Insert nodi haki pale. Hebu kuanza kufanya hivyo. 

Hivyo tuna nodi * cur = mizizi; sisi ni kwenda tu kufuata ina code mpaka tunaona kwamba haina kabisa kazi kwa ajili yetu. Sisi ni kwenda kupitia mti wakati kipengele sasa si null, na kama sisi kupata thamani kwamba cur ni sawa na thamani ya kwamba sisi ni kujaribu kuingiza - vizuri, hii ni moja ya kesi ambayo tunaweza si kweli Insert nodi katika mti kwa sababu hii ina maana tuna thamani duplicate. Hapa sisi ni kweli kwenda na kurudi uongo. Sasa, mwingine kama thamani cur ni chini ya thamani, sasa tunajua kwamba sisi hoja ya haki  kwa sababu ni mali ya thamani ya nusu katika haki ya mti cur. Vinginevyo, sisi ni kwenda hoja kwa upande wa kushoto. Hiyo ni kimsingi ina kazi zetu pale pale. 

Katika hatua hii, mara moja tumekuwa kukamilika kitanzi wakati, cur wetu pointer inaenda akizungumzia null kama kazi hana tayari akarudi. Sisi ni hiyo kuwa cur katika doa ambapo tunataka Insert nodi mpya. Nini bado kufanyika ni kweli kujenga nodi mpya, ambayo tunaweza kufanya pretty urahisi. Tunaweza kutumia wetu super-Handy kujenga nodi kazi, na kitu ambacho sisi hakufanya mapema - sisi tu aina ya alichukua kwa nafasi lakini sasa tutaweza kufanya tu kuhakikisha - tutaweza mtihani kuhakikisha kwamba thamani akarudi na node mpya ilikuwa kwa kweli ni si null, kwa sababu hatutaki kuanza kupata kwamba kumbukumbu ikiwa ni null. Tunaweza kupima ili kuhakikisha kuwa nodi mpya si sawa kwa null. Au badala yake, tunaweza tu kuona kama ni kweli ni null, na kama ni null, basi tunaweza tu kurudi uongo mapema. 

Katika hatua hii, tuna waya nodi mpya katika doa yake mwafaka katika mti. Kama sisi kuangalia nyuma katika kuu na ambapo sisi walikuwa kweli wiring katika maadili kabla, tunaona kwamba njia ya sisi walikuwa wakifanya hivyo wakati sisi alitaka kuweka 3 katika mti mara sisi kupatikana mtoto wa kushoto wa mizizi. Wakati sisi kuweka 9 katika mti, tulikuwa na kupata mtoto wa kulia wa mizizi. Tulikuwa na kuwa na pointer mzazi ili kuweka thamani mpya katika mti. Scrolling nyuma hadi Insert, si kwamba kwenda kabisa kazi hapa kwa sababu hatuna pointer mzazi. Nini tunataka kuwa na uwezo wa kufanya ni, katika hatua hii, kuangalia thamani ya mzazi na kuona - vizuri, gosh, kama thamani ya mzazi ni chini ya thamani ya sasa, basi mzazi wa mtoto haki lazima nodi mpya; vinginevyo, mzazi wa mtoto wa kushoto lazima nodi mpya. Lakini, hatuna hii pointer mzazi kabisa bado. 

Ili kupata, sisi ni kweli kwenda na kufuatilia ni kama sisi kwenda kwa njia ya mti na kupata doa mwafaka katika kitanzi yetu hapo juu. Tunaweza kufanya hivyo kwa scrolling nyuma hadi juu ya Insert kazi yetu na kufuatilia mwingine kutofautiana pointer kuitwa mzazi. Sisi ni kwenda kuweka sawa kwa null awali, na kisha kila wakati sisi kwenda kwa njia ya mti, tunakwenda kuweka pointer mzazi kwa mechi pointer sasa. Kuweka sawa na mzazi cur. Kwa njia hii, kila wakati sisi kwenda kwa njia ya, tunakwenda kuhakikisha kwamba kama pointer sasa anapata incremented pointer mzazi ifuatavyo it - moja tu ngazi ya juu kuliko pointer sasa katika mti. Hiyo yote inaonekana pretty nzuri. 

Nadhani jambo moja kwamba tutaweza wanataka kurekebisha ni hii kujenga nodi kurudi null. Ili kupata kujenga nodi ili kweli mafanikio kurudi null, tutaweza kurekebisha kwamba kanuni, kwa sababu hapa, sisi kamwe majaribio kuhakikisha kwamba malloc akarudi pointer halali. Hivyo, kama (n = null!), Kisha - ikiwa malloc akarudi pointer halali, basi tutaweza initialize yake; vinginevyo, sisi itabidi kurudi na kwamba itakuwa mwisho juu ya kurudi null kwa ajili yetu. Sasa yote inaonekana pretty nzuri. Hebu kuhakikisha kweli hii inaandaa. Matokeo binary mti, na oh, sisi tumepewa baadhi ya mambo yanayofanyika hapa. 

Sisi tumepewa tamko thabiti wa kazi kujenga nodi. Tena, kwa compilers haya, sisi ni kwenda kuanza saa ya juu. Nini maana ya kwamba ni lazima ni kwamba mimi nina wito kujenga nodi kabla Nimekuwa kwa kweli alitangaza. Turudi kwa kificho kweli haraka. Kitabu chini, na uhakika wa kutosha, Insert kazi yangu ni alitangaza juu ya kazi ya kujenga nodi, lakini nina kujaribu kutumia kujenga nodi ndani ya Insert. Mimi nina kwenda katika nakala na - na kisha kuweka nodi kujenga kazi njia ya juu hapa juu. Kwa njia hiyo, hopefully ambayo kazi. Hebu kutoa hii kwenda nyingine. Sasa wote compiles. Wote ni nzuri. 

Lakini katika hatua hii, sisi si kweli kuitwa Insert wetu kazi. Sisi tu kujua kwamba inaandaa, hivyo hebu kwenda katika na kuweka wito baadhi in Hebu kufanya hivyo katika kazi yetu kuu. Hapa, sisi maoni nje 5, 8, na 2, na kisha sisi hawakuwa waya yao juu chini hapa. Hebu kufanya baadhi wito kwa Insert, na hebu pia kutumia aina moja ya mambo ambayo sisi kutumika wakati tukiwa na simu hizi printf kuhakikisha kwamba kila kitu gani kupata kuingizwa vizuri. Mimi naenda nakala na kuweka, na badala ya ina tunakwenda kufanya Insert. Na badala ya 6, 10, na 1, sisi ni kwenda kutumia 5, 8, na 2. Hii lazima hopefully Insert 5, 8, na 2 katika mti. Kukusanya. Wote ni nzuri. Sasa tutaweza kweli kuendesha programu yetu. 

Kila kitu akarudi uongo. Hivyo, 5, 8, na 2 hakwenda, na inaonekana kama ina hawakuwakuta aidha. Nini kinaendelea? Hebu zoom nje. Tatizo la kwanza ni kwamba Insert walionekana kurejea uongo, na inaonekana kama kwamba kwa sababu sisi kushoto katika wito marejeo yetu ya uongo, na sisi kamwe kweli alirudi kweli. Tunaweza kuweka kwamba up. Tatizo la pili ni, sasa hata kama sisi kufanya - kuokoa huu, kujiondoa hii, kukimbia kufanya tena, kuwa ni kukusanya, kisha kukimbia - tunaona kwamba kitu kingine kilichotokea hapa. 5, 8, na 2 walikuwa bado kamwe kupatikana katika mti. Hivyo, nini kinaendelea? 

Hebu tuangalie hii katika code. Hebu tuone kama tunaweza takwimu hii nje. Tunaweza kuanza na mzazi kutokuwa null. Sisi kuweka pointer sasa sawa na pointer mizizi, na sisi ni kwenda kufanya kazi kwa njia yetu chini kupitia mti. Kama nodi sasa si null, basi tunajua kwamba tunaweza kusonga chini kidogo kidogo. Sisi kuweka mzazi wetu pointer kuwa sawa na pointer sasa, checked thamani - kama maadili ni sawa sisi kurejea uongo. Kama maadili ni chini sisi wakiongozwa na haki; vinginevyo, sisi wakiongozwa na wa kushoto. Kisha sisi kujenga nodi. Mimi itabidi zoom katika kidogo. Na hapa, sisi ni kwenda kujaribu waya juu maadili kuwa sawa. Nini kinaendelea? Hebu angalia kama uwezekano Valgrind anaweza kutupa hint. 

Mimi kama kutumia Valgrind sababu tu Valgrind kweli haraka anaendesha na anakwambia kama kuna makosa kumbukumbu yoyote. Wakati sisi kukimbia Valgrind juu ya kanuni, kama unaweza kuona haki here--Valgrind./binary_tree--and hit kuingia. Unaweza kuona kwamba hatukuwa na kosa lolote kumbukumbu, hivyo inaonekana kama kila kitu ni sawa hadi sasa. Sisi kufanya kuwa uvujaji baadhi ya kumbukumbu, ambayo sisi kujua, kwa sababu sisi siyo kinachotokea kwa huru yoyote ya nodes yetu. Hebu jaribu mbio GDB kuona nini hasa kinachoendelea. Tutaweza kufanya gdb /. Binary_tree. Ni booted up faini tu. Hebu kuweka uhakika wa mapumziko juu ya Insert. Hebu kukimbia. Inaonekana kama sisi kamwe kweli kuitwa Insert. Inaonekana kama tatizo ni kwamba tu wakati mimi iliyopita chini hapa katika kuu - yote ya simu hizi printf kutoka ina - Mimi kamwe kweli iliyopita haya kuwaita Insert. Sasa hebu mkajaribu. Hebu kukusanya. Yote inaonekana nzuri huko. Sasa hebu jaribu mbio, kuona nini kinatokea. Alright! Kila kitu inaonekana pretty nzuri huko. 

Jambo la mwisho kufikiria ni, kuna kesi yoyote makali kwa Insert hii? Na zinageuka kuwa, pamoja, mmoja makali kesi hiyo ni daima kuvutia kufikiri kuhusu ni, nini kinatokea kama mti yako ni tupu na wewe piga kazi hii Insert? Je, ni kazi? Naam, hebu kutoa ni kujaribu. - Binary_tree c. - njia tunakwenda mtihani huu ni, sisi ni kwenda chini kwa kazi yetu kuu, na badala ya wiring nodi hiyo juu kama hii, sisi ni kwenda tu maoni nje jambo nzima, na badala ya wiring up nodes wenyewe, tunaweza kweli tu kwenda mbele na kufuta haya yote. Sisi ni kwenda kufanya kila kitu wito kwa Insert. Hivyo, hebu kufanya - badala ya 5, 8, na 2, tunakwenda Insert 7, 3, na 9. Na kisha tutaweza pia unataka Insert 6 pia. Ila. Kujiondoa. Matokeo binary mti. Ni wote compiles. Tunaweza kukimbia tu ni kama ni na kuona nini kinatokea, lakini pia ni kwenda kuwa kweli ni muhimu ili kuhakikisha kuwa hatuna makosa yoyote kumbukumbu, tangu hii ni moja ya kesi zetu makali kwamba sisi kujua juu. 

Hebu kuhakikisha kwamba ni kazi vizuri chini ya Valgrind, ambayo tutaweza kufanya na kukimbia tu Valgrind. / binary_tree. Inaonekana kama sisi kweli kuwa moja kosa kutoka muktadha mmoja - tuna hii kosa segmentation. Ni nini kilichotokea? Valgrind kweli inatuambia ambapo ni. Fifiza kidogo. Inaonekana kama kinatokea katika Insert kazi yetu, ambapo tuna kusoma batili ya kawaida 4 katika Insert, line 60. Hebu kwenda nyuma na kuona nini kinaendelea hapa. Fifiza kweli haraka. Mimi nataka kuhakikisha kwamba haina kwenda makali ya screen ili tuweze kuona kila kitu. Kuvuta kwamba katika kidogo. Alright. Kitabu chini, na tatizo ni haki hapa. Nini kinatokea kama sisi kupata chini na nodi wetu wa sasa ni tayari null, mzazi wetu nodi ni null, hivyo kama sisi kuangalia hadi saa ya juu sana, haki hapa - kama hii kitanzi wakati kweli kamwe executes kwa sababu thamani yetu ya sasa ni null - mizizi yetu ni null hivyo cur ni null - basi mzazi wetu kamwe anapata kuweka cur au thamani halali, hivyo, mzazi pia kuwa null. Tunahitaji kukumbuka kuangalia kwa kuwa na wakati sisi kupata chini hapa, na sisi kuanza kupata thamani ya mzazi. Hivyo, nini kitatokea? Naam, kama mzazi ni null - kama (mzazi == null) - basi tunajua kwamba lazima kuna kuwa kitu chochote katika mti. Sisi lazima kujaribu kuingiza kwenye mizizi. Tunaweza kufanya hivyo kwa kuweka tu mizizi sawa na nodi ya mwezi. Kisha katika hatua hii, sisi si kweli unataka kwenda kupitia mambo haya mengine. Badala yake, haki hapa, tunaweza kufanya ama kingine-kama-kingine, au sisi inaweza kuchanganya kila kitu hapa juu katika mwingine, lakini hapa tutaweza tu kutumia mwingine na kufanya hivyo. Sasa, sisi ni kwenda kupima ili kuhakikisha kuwa mzazi wetu si null kabla ya hapo kwa kweli kujaribu kupata mashamba yake. Hii itatusaidia kuepuka kosa segmentation. Hivyo, sisi kujiondoa, zoom nje, kukusanya, kukimbia. 

Hakuna makosa, lakini bado tuna rundo la uvujaji kumbukumbu kwa sababu hatukuwa huru yoyote ya nodes yetu. Lakini, kama sisi kwenda hapa na sisi kuangalia printout yetu, tunaona kwamba, vizuri, inaonekana kama wote wa kuwekeza wetu walikuwa kurudi kweli, ambayo ni nzuri. kuwekeza wote ni wa kweli, na kisha sahihi ina wito ni kweli pia. 

Kazi nzuri! Inaonekana kama tumekuwa mafanikio imeandikwa Insert. Hayo ni yote tuna kwa Specifikation Tatizo wiki hii Set. Moja ya kujifurahisha na changamoto ya kufikiria ni jinsi gani kweli kwenda katika na bure wote wa nodi katika mti huu. Tunaweza kufanya hivyo idadi ya njia tofauti, lakini mimi itabidi kuondoka kuwa hadi wewe kwa majaribio, na kama changamoto ya kujifurahisha, kujaribu na kuhakikisha kwamba unaweza kuhakikisha kwamba hii ripoti Valgrind anarudi makosa hakuna uvujaji na hakuna. 

Bahati nzuri juu ya Huffman wiki hii coding kuweka tatizo, na tutaweza kuona wewe wiki ijayo! [CS50.TV]