[Powered by Google Translate] [Kafli 7] [Minna Comfortable] [Nate Hardison] [Harvard University] [Þetta er CS50.] [CS50.TV] 

Velkomin á kafla 7. Þökk sé fellibyl Sandy, í stað þess að hafa venjulegan kafla þessa viku, við erum að gera þetta ganga í gegnum, í gegnum hluta af spurningum. Ég ætla að fylgja ásamt Vandamál Set 6 texta, og fara í gegnum allar spurninga í Hluti af spurningum kafla. Ef það eru einhverjar spurningar, vinsamlegast senda þetta á CS50 ræða. 

Alright. Við skulum byrja. Núna er ég að horfa á síðu 3 af Set Vandamál Specification. Við ætlum fyrst að byrja að tala um tvöfaldur tré síðan þeir hafa a einhver fjöldi af máli við vandamál setja þessa viku - að Huffman Tree kóðun. Einn af fyrstu gögn uppbygging við ræddum um á CS50 var array. Mundu að fylki er röð atriða - öll af sömu tegund - geymd við hliðina á hvor öðru í minni. Ef ég er með heiltölu fylki sem ég get teiknað nota box-númer-heiltölur stíl - Við skulum segja að ég hef 5 í fyrsta reitinn, ég 7 í öðrum, þá hef ég 8, 10 og 20 í síðasta reitinn. Mundu, tveir mjög góðir hlutir um þetta fylki er að við höfum þessa föstu-tíma aðgang að tilteknum þáttur  í fylkinu ef við vitum vísitölu. Til dæmis, ef ég vil grípa þriðja þáttur í fylkinu - á vísitölu 2 með núll-undirstaða flokkun kerfi okkar - Ég bókstaflega bara að gera einfalda stærðfræði útreikninga, step í þeirri stöðu í fylking, draga út 8 sem er geymd þar, og ég er gott að fara. 

Einn af the slæmur hlutur óður í this array - sem við ræddum um þegar við ræddum tengd listum - er að ef ég vil setja stak í þessu fylki, Ég ætla að gera nokkrar að færast. Til dæmis, þetta fylki hérna er raðað röð - raðað í hækkandi röð - 5, svo 7, svo 8, síðan 10, og svo 20 - en ef ég vil að setja númer 9 í þessu fylki, Ég ætla að hafa til að skipta sumir af þeim þáttum til að gera pláss. Við getum draga þetta út hér. Ég ætla að hafa til að færa 5, 7, og þá 8; búa til gjá þar sem ég get sett 9, og þá 10 og 20 getur farið til hægri á 9. Þetta er góður af sársauka vegna þess að í versta falli - þegar við erum að þurfa að setja annað hvort í upphafi eða við lok um fjölda, eftir því hvernig við erum að breytast - við might endir upp að þurfa að skipta öllum þeim þáttum sem við erum nú að geyma í fylki. 

Svo, hvað var hátt í kringum þetta? Leiðin í kringum þetta var að fara að tengd-lista aðferð okkar þar - í stað þess að geyma þá þætti 5, 7, 8, 10 og 20 alla hliðina á hvor aðra í minni - hvað við staðinn gerði var geymt þá eins konar hvar við vildum að geyma þá í þessum ítengdu lista hnúður sem ég er að teikna út hér, eins konar tilfallandi. Og þá erum tengd þá saman með þessum næsta ábendingum. Ég get haft músina frá 5 til 7, bendi frá 7 til 8, bendi frá 8 til 10, og að lokum, bendi frá 10 til 20, og þá a null músina á 20 gefur til kynna að það er ekkert eftir. Málamiðlun sem við höfum hér er það nú ef við viljum setja númer 9 í raðaða listanum okkar, allt sem við þurfum að gera er að búa til nýjan hnút með 9, vír það upp til að benda á viðeigandi stað, og þá með tilvísun til-vír 8 að benda niður í 9. Það er nokkuð hratt, miðað við vitum nákvæmlega hvar við viljum að setja 9. En málamiðlun í skiptum fyrir þessu er að við höfum nú misst föstu-tíma aðgang einhverju tilteknu frumefni í gögn uppbygging okkar. Til dæmis, ef ég vil að finna fjórða þáttur í tengda listanum, Ég ætla að hafa til að byrja í upphafi á listanum og vinna leið minni í gegnum talningu hnút-með-hnút þangað til ég finna fjórða einn. 

Í því skyni að fá betri aðgang árangur en í tengda listanum - en einnig halda sumir af the hagur sem við höfðum hvað er sett í tíma úr tengda listanum - tvöfaldur tré er að fara að þurfa að nota aðeins meira minni. Einkum, í stað þess bara að hafa einn músina í tvíundartrés hnút - eins og tengda-lista hnút gerir - við erum að fara að bæta við annarri bendi til tvöfaldur tré hnút. Frekar en bara að hafa eitt bendi á næsta þátt, við erum að fara að hafa músina til vinstri barns og rétt barns. 

Við skulum teikna mynd til að sjá hvað það raunverulega lítur út. Aftur, ég ætla að nota þessa reiti og örvar. A tvöfaldur tré hnút verður að byrja leikinn með bara einfaldur kassi. Það er að fara að hafa pláss fyrir gildi, og þá er líka að fara að hafa pláss fyrir vinstra barn og hægra barn. Ég ætla að merkja þau hér. Við ætlum að hafa vinstri barnið, og þá ætlum við að hafa rétt barn. Það eru til margar mismunandi leiðir til að gera þetta. Stundum um pláss og þægindi, Ég í raun draga það eins og ég er að gera hér á botn þar sem ég ætla að hafa gildi efst, og svo rétt barnið á neðst til hægri, og vinstri barn á botn-vinstri. Fara aftur í þessum efstu myndinni, við höfum gildi á the mjög toppur, þá höfum við vinstri-barn músina, og þá höfum við rétt barns músina. 

Í Set Vandamál við notkun lyfsins, við tölum um að teikna hnút sem hefur gildi 7, og þá vinstri-barn músina sem er núll, og réttur barns músina sem er núll. Við getum annað hvort skrifað höfuðborg NULL í rými fyrir bæði vinstri barn og rétt barnið, eða við getum draga þessa ská skástrik gegnum hvert reitina til að benda að það er núll. Ég ætla að gera það bara vegna þess að það er einfaldara. Það sem þú sérð hér eru tvær leiðir diagramming mjög einfalt tvíundartré hnút þar sem við höfum gildið 7 og núll ábendingum barn. 

Seinni hluti af viðræðum skilgreining okkar um hvernig við tengd listum - Mundu, við höfðum aðeins að halda á fyrstu frumefni í lista að muna alla lista - og sömuleiðis, með tvöfaldur tré, höfum við aðeins að halda eitt bendi á tré í því skyni að hafa stjórn á öllu gögn uppbygging. Þetta sérstaka þáttur í tré er kallað rót hnút í trénu. Til dæmis, ef einn hnút - þessi hnútur inniheldur gildið 7 með núll vinstri-og hægri-barn ábendingum - voru aðeins gildi í trénu okkar, þá myndi þetta vera rót hnút okkar. Það er mjög upphafi tré okkar. Við sjáum þetta aðeins betur þegar við byrjum að bæta fleiri hnúta til tré okkar. Leyfðu mér að draga upp nýja síðu. 

Nú ætlum við að teikna tré sem hefur 7 í rót, og 3 inni vinstri barnsins og 9 inni í hægri barnsins. Aftur, þetta er frekar einfalt. Við höfum fengið 7, draga hnút fyrir 3, hnút í 9, og ég ætla að láta vinstri-barns músina yfir 7 til að benda á hnút sem inniheldur 3, og rétt barns músina í hnút sem inniheldur 7 til hnúturinn inniheldur 9. Nú, síðan 3 og 9 hafa engar börn, við erum að fara að setja alla ábendingum barnið þeirra til að vera núll. Hér rót trésins okkar samsvarar hnúturinn inniheldur númer 7. Þú getur séð að ef allt sem við höfum er bendi til að rót hnút, við getum þá gengið í gegnum tré okkar og aðgang bæði barn hnúður - bæði 3 og 9. Engin þörf á að viðhalda ábendingum til sérhver einn hnút á trénu. Alright. Nú ætlum við að bæta við öðru hnút á þetta línurit. Við ætlum að bæta við hnút inniheldur 6, og við erum að fara að bæta þetta sem rétt barnsins á hnút inniheldur 3. Til að gera það, ég ætla að eyða að núll músina í 3-hnút og vír það upp til að benda á hnút inniheldur 6. Alright. 

Á þessum tímapunkti, við skulum fara yfir smá hugtakanotkun. Til að byrja, Ástæðan fyrir því að þetta er kallað tvöfaldur tré einkum er að það hefur tvö börn ábendingum. Það eru aðrar tegundir af trjám sem hafa fleiri barn ábendingum. Sérstaklega fannst þér a 'reyna' í Set Vandamál 5. Þú munt taka eftir því að á að reyna, var að 27 mismunandi ábendingum til mismunandi börn - einn fyrir hverja 26 stafi í enska stafrófið, og þá 27 í úrfellingarmerki - svo, það er svipað og að gerð tré. En hér, þar sem tvöfaldur það, höfum við aðeins tvö börn ábendingum. 

Í viðbót við þetta rót hnút sem við ræddum um, við höfum einnig verið að kasta í kringum þetta hugtak "barn." Hvað þýðir það að einn hnút að vera barn annars hnút? Það þýðir bókstaflega að barnið tengipunktur er barn annars hnút Ef að annar hnútur er eitt af ábendingum barn hennar sett til að benda á það hnút. Til að setja þetta í fleiri steypu skilmálum, Ef 3 er bent á af einum barnið ábendingum um 7, þá er 3 barn 7. Ef við vorum að reikna út hvað börn 7 eru - Jæja, sjáum við að 7 hefur músina til 3 og bendi til 9 svo 9 og 3 eru börn 7. Níu eru ekki börn því börn ábendingum þess eru null, og 3 hefur aðeins eitt barn, 6. Sex hefur líka ekki börn vegna þess að báðir ábendingum hennar eru null, sem við munum draga núna. 

Auk þess tölum við líka um foreldra tilteknum hnút, og þetta er, eins og þú vilt búast við, hið gagnstæða þessa barns lýsingu. Hver hnútur hefur einungis einn foreldri - í stað tveggja eins og þú might búast við mönnum. Til dæmis, foreldri 3 er 7. Foreldri 9 er 7, og foreldri 6 er 3. Ekki mikið að því. Við höfum einnig skilmála að tala um afa og barnabörn, og almennt við tölum um forfeður og afkomendur tiltekins hnút. Forfeður hnút - eða forfeður, heldur, á hnút - eru öllum hnúður sem liggja á leið frá rót til að hnút. Til dæmis, ef ég er að horfa á hnúturinn 6, þá forfeður eru að fara að vera bæði 3 og 7. Forfeður 9, td eru - ef ég er að horfa á hnúturinn 9 - þá er forfeður 9 bara 7. Og afkomendur eru einmitt hið gagnstæða. Ef ég vil horfa á alla niðjum 7, þá verð ég að líta á allar hnúður undir honum. Svo hef ég 3, 9 og 6 allt sem afkomendur 7. 

Endanleg orð sem við munum tala um er þetta hugmynd af því að vera systkini. Systkini - konar fylgja eftir á þessum fjölskyldu skilmálum - er hnúður sem eru á sama stigi í trénu. Svo eru 3 og 9 systkini vegna þess að þeir eru á sama stigi í trénu. Þeir báðir hafa sama foreldri, 7. The 6 hefur engin systkini því 9 er ekki börn. Og 7 hjartarskinn ekki hafa allir systkini því að það er rót trésins okkar, og það er bara alltaf 1 rót. Fyrir 7 hafa systkini þar þyrfti að vera hnútur yfir 7. Það þyrfti að vera foreldri 7, en þá 7 væri ekki lengur vera rót trésins. Þá að nýju foreldri 7 myndu einnig að eignast barn, og að barnið væri þá systkini af 7. 

Alright. Flutningur á. Þegar við byrjuðum umræðu um tré tvöfaldur, Við ræddum um hvernig við ætluðum að nota þá til að fá forskot á bæði fylki og tengist listum. Og hvernig ætlum við að gera það er með þessa röðun eign. Við segjum að tvöfaldur tré er skipað, samkvæmt forskrift, ef fyrir hvern hnút í tré okkar, allir afkomendur hennar á vinstri - vinstri barnið og alla niðja Vinstrihreyfingin barnsins - hafa minni gildi, og öll hnúður á hægri - rétt barn og öllum niðjum Rétturinn barnsins - hafa hnúta meiri en verðmæti núverandi hnút sem við erum að horfa á. Bara fyrir einfaldleika, við erum að fara að gera ráð fyrir að það eru ekki allir afrit hnútar í trénu okkar. Til dæmis, í þessu tré sem við erum ekki að fara að takast á við að ræða þar sem við höfum gildið 7 á rót  og þá höfum við einnig gildi 7 annars staðar í trénu. Í þessu tilfelli, þú munt taka eftir því að þetta tré er örugglega pantað. Við höfum gildi 7 í rót. Allt til vinstri á 7 - ef ég losa allar þessar litlu merki hér - allt til vinstri 7 - 3 og 6 - þessi gildi eru bæði minni en 7 og allt til hægri - sem er bara þetta 9 - er meiri en 7. 

Þetta er ekki einungis pantað tré með þessi gildi, en við skulum draga nokkrar fleiri af þeim. Það er í raun allt fullt af leiðir að við getum gert þetta. Ég ætla að nota skammstöfun bara að halda hlutum einfalt þar - frekar en að draga út alla reiti-og-örvum - Ég ætla bara að fara að draga númer og bæta örvum tengja þá. Til að byrja, við verðum bara að skrifa upprunalega tré okkar aftur þar sem við áttum 7, og svo a 3, og svo 3 benti aftur til hægri til 6, og 7 var rétt barn sem var 9. Alright. Hvað er önnur leið sem við gætum skrifað þetta tré? Í stað þess að hafa 3 vera vinstri barn 7, við gætum líka hafa 6 vera vinstri barn 7, og 3 vera vinstri barn 6. Það myndi líta út eins og þessu tré hérna þar sem ég hef fengið 7, þá 6, svo 3, og 9 til hægri. Við einnig þurfa ekki að hafa 7 og hnút rót okkar. Við gætum líka hafa 6 og hnút rót okkar. Hvað myndi það líta út? Ef við erum að fara að halda þessari panta eign, allt til vinstri við 6 þarf að vera minna en það. Það er aðeins einn möguleiki og það er 3. En þá eins og hægri barn 6, höfum við tvo möguleika. Fyrst, gætum við hafa 7 og síðan 9, eða við getum draga það - eins og ég er að fara að gera hér - þar sem við höfum 9 og hægra barn á 6, og þá 7 og vinstri barn í 9. 

Nú eru 7 og 6 ekki aðeins mögulegt gildi fyrir rót. Við gætum líka hafa 3 verið á the rót. Hvað gerist ef 3 er í rót? Hér fá hlutina svolítið áhugavert. Þrír hjartarskinn ekki hafa allir gildi sem eru minni en það, svo að allt vinstra megin á trénu er bara að fara að vera null. Það er ekki að fara að vera neitt þarna. Til hægri, gætum við lista það í hækkandi röð. Við gætum hafa 3, þá 6, þá 7 og síðan 9. Eða getum við gert 3, þá 6, svo 9, þá 7. Eða getum við gert 3, þá 7, þá 6, þá 9. Eða, 3, 7 - í raun ekki, við getum ekki gert 7 aftur. Það er eitt okkar þar. Við getum gert 9, og síðan úr 9 við getum gert 6 og síðan 7. Eða getum við gert 3, þá 9, þá 7 og síðan 6. 

Eitt sem þarf að vekja athygli á hér er að þessi tré eru svolítið skrítið-útlit. Einkum, ef við skoðum 4 tré hægra megin - Ég umlykja þá, hér - Þessi tré líta næstum nákvæmlega eins og tengda lista. Hver hnútur hefur aðeins eitt barn, og svo við höfum ekkert af þessu tré-eins og uppbygging sem við sjáum til dæmis,  í einu einn tré hérna á neðst til vinstri. Þessi tré eru í raun kölluð úrkynjuðu tvöfaldur tré, og við munum tala um þetta meira í framtíðinni - sérstaklega ef þú ferð að taka önnur tölvunarfræði námskeið. Þessi tré eru degenerate. Þeir eru ekki mjög gagnlegur því, örugglega, þessi uppbygging lánar sig  að fletta sinnum svipuð í tengda listanum. Við fæ ekki að taka kostur af the auka minni - þetta auka músina - vegna uppbyggingu okkar að vera slæmt á þennan hátt. Frekar en að fara á og draga út tvöfaldur tré sem hafa 9 í rót, sem er það sem kemur síðas mál sem við hefðum, við erum í staðinn, á þessum tímapunkti, að fara að tala svolítið um þetta önnur orð sem við notum þegar að tala um tré sem er kölluð hæð. 

Hæð tré er fjarlægð frá rót til mest fjarlæg hnút, eða frekar fjölda hops sem þú þyrftir að gera til þess að byrja frá rót og svo endað á mest fjarlæg hnút í trénu. Ef við lítum á sumir af þessum trjám sem við höfum dregið hérna, sjáum við að ef við tökum þetta tré í efst í vinstra horninu og við byrjum á 3, þá verðum við að gera 1 step til fá til the 6, annað step til að komast að 7, og þriðja step til að komast að 9. Svo hæð þessu tré er 3. Við getum gert sömu æfingar fyrir önnur tré lýst með þessum græna, og við sjáum að hæð öllum þessum trjám er líka örugglega 3. Það er hluti af því sem gerir þá úrkynjuðu - að hæð þeirra er bara einn minna en fjöldi hnúta í allt tréð. Ef við horfum á þetta öðrum tré sem er kringum með rauðu, á hinn bóginn, sjáum við að mest fjarlæg blaða hnútar eru 6 og 9 - blöðin að þeir hnútar sem hafa ekki börn. Svo, í því skyni að fá úr rót hnút í annaðhvort 6 eða 9, við verðum að gera eitt step til að komast að 7 og svo annað step til að komast að 9, og sömuleiðis, bara annað step frá 7 til að komast í 6. Svo hæð þessu tré hérna er aðeins 2. Þú getur farið til baka og gera það fyrir öllum öðrum trjám sem við ræddum áður hefst með 7 og 6, og þú munt komast að því að hæð af öllum þeim trjám er líka 2. 

Ástæðan sem við höfum verið að tala um að panta tvöfaldur tré og hvers vegna þeir eru kúl er vegna þess að þú getur leitað í þeim mjög svipaðan hátt og leita yfir raðað fylki. Þetta er þar sem við tölum um að fá að bæta útlit tíma yfir þeirri einföldu tengda listanum. Með tengda listanum - ef þú vilt að finna ákveðna hluti - þú ert í besta falli að fara að gera einhvers konar línuleg leit þar sem þú byrjar í upphafi lista og step einn-við-einum - einn hnút eftir einum hnút - gegnum allt listann þar til þú finnur það sem þú ert að leita að. Teknu tilliti til, ef þú hafa a tvöfaldur tré sem er geymd í þessum fallegu sniði, þú getur í raun að fá meira af tvöfaldur leit að fara á þar sem þú skiptir og sigra og leita í gegnum viðeigandi hluta af trénu á hverju skrefi. Við skulum sjá hvernig það virkar. 

Ef við höfum - aftur, fara aftur í upprunalegt tré okkar - við byrjum á 7, höfum við 3 til vinstri, 9 til hægri, og undir 3 við höfum 6. Ef við viljum að leita að númer 6 í þessu tré, viljum við byrja á rót. Við viljum bera gildi sem við erum að leita að, segja 6, að verðmæti geymd í hnút sem við erum nú að leita á, 7, finna að 6 er örugglega minna en 7, svo að við myndum fara til vinstri. Ef verðmæti 6 hefði verið meira en 7, við viljum hafa í stað flutt til hægri. Þar sem við vitum að - vegna uppbyggingu pantaði tvíundartré okkar - öll gildi minna en 7 eru að fara að geyma til vinstri á 7, Það er engin þörf á að einu sinni nenna að horfa í gegnum hægra megin á trénu. Þegar við förum til vinstri og við erum nú í hnút sem inniheldur 3, Við getum gert það sama samanburð aftur þar sem við bera saman 3 og 6. Og við komumst að því á meðan 6 - gildi sem við erum að leita að - er meira en 3, við getum farið á hægri hlið hnút inniheldur 3. Það er enginn vinstri hlið hér, þannig að við gætum hafa hunsað það. En við vitum bara að vegna þess að við erum að horfa á tréð sjálft, og við getum séð að tré hefur ekki börn. 

Það er líka mjög auðvelt að líta upp 6 í þessu tré ef við erum að gera það okkur eins og menn, en við skulum fylgja þessu ferli vélrænt eins og tölva myndi gera að raunverulega skilja reiknirit. Á þessum tímapunkti, við erum nú að horfa á hnút sem inniheldur 6, og við erum að leita að verðmæti 6, svo, reyndar höfum við fundið viðeigandi hnút. Við fundum gildi 6 í trénu okkar, og við getum hætt leit okkar. Á þessum tímapunkti, allt eftir hvað er að gerast, við getum sagt, já, við höfum fundið gildi 6, er það í trénu okkar. Eða, ef við erum að skipuleggja að setja hnút eða gera eitthvað, getum við gert það á þessum tímapunkti. 

Gerum nokkrar fleiri vélarheiti bara að sjá hvernig þetta virkar. Við skulum líta á hvað gerist ef við vorum að reyna að líta upp gildi 10. Ef við værum að leita að verðmæti 10, við viljum byrja á rót. Við myndum sjá að 10 er meira en 7, svo að við myndum fara til hægri. Við viljum fá að 9 og bera 9 til 10 og sjá að 9 er örugglega minna en 10. Svo aftur, viljum við reyna að fara til hægri. En á þessum tímapunkti, myndum við taka eftir því að við erum á núll hnút. Það er ekkert þarna. Það er ekkert þar sem 10 ætti að vera. Þetta er þar sem við getum tilkynnt bilun - að það er örugglega ekki 10 í trénu. Og að lokum, við skulum fara í gegnum er að ræða þar sem við erum að reyna að horfa upp 1 í trénu. Þetta er svipað og það sem gerist ef við skoðum allt 10, nema í stað þess að fara til hægri, við erum að fara að fara til vinstri. Við byrjum á 7 og sjá að 1 er minna en 7, svo við færa til vinstri. Við fáum til 3 og sjá að 1 er minna en 3, svo aftur við að reyna að færa til vinstri. Á þessum tímapunkti sem við höfum núll hnút, svo aftur getum við tilkynna bilun. 

Ef þú vilt læra meira um tvöfaldur tré, það eru allt fullt af skemmtilegur lítill vandamál sem þú getur gert með þeim. Ég legg til að æfa að teikna út af þessum teikningum einn-við-einum og fylgja í gegnum allar mismunandi skrefum, vegna þess að þetta kemur í frábær-vel ekki aðeins þegar þú ert að gera Huffman kóðun vandamál setja heldur einnig í framtíðinni námskeið - bara að læra hvernig á að draga úr þessum gögn uppbygging og hugsa um vandamál með penna og pappír eða, í þessu tilfelli, iPad og stíll. 

Á þessum tímapunkti þó, við erum að fara að fara að gera sumir erfðaskrá æfa og í raun að spila með þessum tveimur trjám og sjá. Ég ætla að skipta aftur yfir í tölvuna mína. Í þessum hluta kafla, í stað þess að nota CS50 hlaupa eða CS50 rýmum Ég ætla að nota tæki. 

Eftir ásamt Set Vandamál forskrift, Ég sé að ég er ætlast til að opna tækið, fara Dropbox möppunni skaltu búa til möppu sem heitir kafla 7, og þá að búa til skrá sem kallast binary_tree.c. Hér förum. Ég hef fengið tækið þegar opinn. Ég ætla draga upp útstöð. Ég ætla að fara í Dropbox möppuna, gera möppu sem heitir section7, og sjá það er alveg tómt. Nú ætla ég að opna binary_tree.c. Alright. Hér förum - tómur skrá. 

Förum aftur til texta. Forskriftin biður að búa til nýja tegund skilgreiningu fyrir tvíundartrés hnút inniheldur int gildi - bara eins og þeim gildum sem við dró út í diagramming okkar áður. Við ætlum að nota þessa boilerplate typedef að við höfum gert hérna að þú ættir að þekkja úr Set Vandamál 5 - ef þú gerðir kjötkássa borð leið sigra Speller program. Þú ættir einnig að viðurkenna það af hluta síðustu viku þar sem við ræddum um tengd listum. Við höfum fengið þetta typedef á strúktúrinn hnút, og við höfum gefið þetta struct node þetta nafn hnút strúktúrinn fyrirfram þannig að við getum þá átt við það þar sem við munum vilja að strúktúr hnút ábendingum sem hluta af struct okkar, en við höfum þá lægi þetta - eða frekar, fylgir þetta - í typedef þannig að seinna í kóðanum, getum við átt við þennan strúktúr sem bara hnút í stað strúktúrinn hnút. 

Þetta er að fara að vera mjög svipað og ein sér-tengda lista skilgreiningu sem við sáum í síðustu viku. Til að gera þetta, við skulum bara byrja á því að skrifa út boilerplate. Við vitum að við verðum að hafa integer, þannig að við setjum í int gildi, og þá í stað þess að hafa bara einn bendi á næsta þátt - eins og við gerðum með ein sér-tengdum listum - við erum að fara að hafa vinstri og hægri barn ábendingum. Það er frekar einfalt líka - struct hnút * vinstri barn; og strúktúr hnút * rétt barn,. Cool. Það lítur út eins og nokkuð góð byrjun. Förum aftur til texta. 

Nú þurfum við að lýsa því yfir á heimsvísu hnút * breytu fyrir rót á tré. Við ætlum að gera þetta heimsvísu eins og við gert fyrstu músina í tengda listanum okkar einnig alþjóðlegt. Þetta var svo að í aðgerðum sem við skrifa við þurfum ekki að halda liggur um þetta rót - þó að við munum sjá að ef þú vilt að skrifa þessar aðgerðir endurkvæmt, það gæti verið betra að ekki einu sinni gefa það í kring eins og a alheims í fyrsta sæti og í staðinn frumstilla það á staðnum í aðal virka. En við munum gera það á heimsvísu að byrja. Aftur, munum við gefa nokkur rými og ég ætla að lýsa yfir hnút * rót. Bara til að vera viss um að ég leyfi þetta ekki forsniðinn, ætla ég að setja það jafnt null. Nú, í meginvirkni - sem við munum skrifa mjög hratt hérna - INT helstu (int argc, const char * argv []) - og ég ætla að byrja að lýsa argv array mitt sem const bara svo að ég veit að þessi rök eru rök sem ég sennilega vilja ekki að breyta. Ef ég vil að breyta þeim að ég ætti líklega að gera afrit af þeim. Þú munt sjá þetta mikið í kóða. Það er allt í lagi annar hvor vegur. Það er í lagi að skilja það sem - sleppt const ef þú vilt. Ég setti oftast það bara svo að ég minna mig  sem ég sennilega vil ekki breyta þeim rök. 

Eins og alltaf, ég ætla að láta þetta aftur 0 línu í lok aðal. Hér mun ég frumstilla rót hnút minn. Eins og það stendur núna, hef ég fékk músina sem er stillt á núll, þannig að það er að benda á neitt. Til að í raun að byrja að byggja upp hnút, Ég þarf fyrst að úthluta minni fyrir það. Ég ætla að gera það með því að gera minni á hrúga með malloc. Ég ætla að setja rót jafn niðurstöðu malloc, og ég ætla að nota sizeof rekstraraðila til að reikna út stærð á hnút. Ástæðan fyrir því að ég nota sizeof hnút í stað þess að segja, að gera eitthvað eins og þetta - malloc (4 + 4 +4) eða malloc 12 - er vegna þess að ég vil kóða mína til að vera eins samhæft og kostur er. Mig langar að vera fær um að taka þessa. C skrá, þýða það á tækinu, og þýða það á 64-bita Mac minn - eða á algjörlega mismunandi arkitektúr - og ég vil þetta allt til að vinna sama. 

Ef ég er að gera ályktanir um stærð breytur - stærð heiltala eða stærð bendill - þá er ég líka að gera ályktanir um hvers konar arkitektúr sem númerið mitt getur tekist saman þegar hlaupa. Alltaf nota sizeof öfugt við handvirkt toppur á strúktúr sviðum. Hin ástæðan er sú að það gæti líka verið padding að þýðandinn setur í strúktúr. Jafnvel bara toppur á einstökum sviðum er ekki eitthvað sem þú vilt að jafnaði að gera, Svo eyða þessi lína. Nú, til að virkilega frumstilla þennan rót hnút, Ég ætla að hafa til að stinga í gildi fyrir hverja ýmsum sviðum þess. Til dæmis, fyrir gildi sem ég veit að ég vil að frumstilla til 7, og nú ætla ég að setja vinstri barnið að vera null og rétt barnið einnig að vera null. Great! Við höfum gert að hluti af sérstakur. 

Forskriftin niður neðst á síðu 3 biður mig að búa til þrjú fleiri hnúta - ein með 3, einn með 6, og einn með 9 - og vír þá upp þannig lítur það nákvæmlega eins og skýringarmynd tré okkar að við vorum að tala um áður. Við skulum gera það mjög hratt hér. Þú munt sjá mjög fljótt að ég ætla að byrja að skrifa fullt af afrit kóða. Ég ætla að búa til hnút * og ég ætla að kalla það þrír. Ég ætla að setja það jafn malloc (sizeof (hnút)). Ég ætla að setja þriggja> gildi = 3. Three -> left_child = NULL, þrír -> hægri _child = NULL, eins og heilbrigður. Það lítur mjög svipað Frumstilli rót, og það er einmitt það sem Ég ætla að gera ef ég byrja Frumstilli 6 og 9 eins og heilbrigður. Ég mun gera það mjög fljótt hér - reyndar, ég ætla að gera smá afrit og líma, og ganga úr skugga um að ég - allt í lagi.  Nú hef ég fengið það afritað og ég get farið á undan og setja þetta jafnt 6. Þú getur séð að það tekur stutta stund og er ekki Super-duglegur. Í réttlátur a lítill hluti, munum við skrifa fall sem vilja gera þetta fyrir okkur. Mig langar til að skipta þetta með 9, í stað þessi með 6. 

Nú höfum við fengið alla tengipunkta okkar til og frumstillt. Við höfum fengið rót okkar sett jafn 7 eða inniheldur gildið 7, hnút okkar inniheldur 3, hnút okkar inniheldur 6, og hnút okkar inniheldur 9. Á þessum tímapunkti, allt sem við þurfum að gera er að víra allt upp. The ástæða ÉG frumstilla allar ábendingar til að null er bara þannig að ég vera viss um að Ég hef engar forsniðinn ábendingum á það fyrir tilviljun. Og líka þar, á þessum tímapunkti, ég hef bara til raunverulega tengja hnúður við hvert annað - við þær að þær séu í raun tengd við - ég þarf ekki að fara í gegnum og gera úr skugga um að öll nulls eru þarna í viðeigandi stöðum. 

Byrjar á rót, veit ég að vinstri barn sem rót er 3. Ég veit að rétt barn í rót er 9. Eftir það, það eina sem barn sem ég hef eftir að hafa áhyggjur af er rétt barn 3, sem er 6. Á þessum tímapunkti, það lítur allt mjög gott. Við munum eyða einhverjum af þessum línum. Nú lítur allt nokkuð gott. Við skulum fara aftur til forskriftir okkar og sjá hvað við þurfum að gera næst. 

Á þessum tímapunkti verðum við að skrifa fall sem kallast 'inniheldur' með frumgerð af "bool inniheldur (int gildi)". Og þetta inniheldur virka er að fara að skila satt  ef tréð benti á af alþjóðlegum rót breytu okkar  inniheldur gildi liðin í aðgerð og ósönn annars. Við skulum fara á undan og gera það. Þetta er að fara að vera nákvæmlega eins og útlit sem við gerðum af hendi á iPad bara svolítið síðan. Skulum súmma aftur í smá og fletta upp. Við erum að fara að setja þessa aðgerð rétt fyrir ofan meginvirkni okkar þannig að við þurfum ekki að gera hvers konar frumgerð. Svo, bool inniheldur (int gildi). Svona. Það er boilerplate yfirlýsingu okkar. Bara til að vera viss um að þetta mun þýða, Ég ætla að fara á undan og bara setja það jafnt return false. Núna þessi aðgerð bara ekki gera neitt og alltaf að tilkynna það verðmæti sem við erum að leita að er ekki í tré. 

Á þessum tímapunkti, er það líklega góð hugmynd - þar sem við höfum skrifað í heild búnt af kóða og við höfum ekki einu sinni reynt að prófa það enn - að ganga úr skugga um að það safnar öllum. There ert a par af hlutum sem við þurfum að gera til að tryggja að þetta mun í raun þýða. Í fyrsta lagi hvort við höfum verið að nota einhverjar aðgerðir í öllum bókasöfnum sem við höfum enn ekki innifalin. Þær aðgerðir sem við höfum notað hingað til eru malloc, og svo höfum við líka verið að nota þessa tegund - þetta nonstandard tegund kallast "bool' - sem er að finna í stöðluðu bool haus skrá. Við viljum örugglega að fela staðall bool.h fyrir bool tegund, og við viljum einnig að # include staðall lib.h fyrir staðall bókasöfn sem eru malloc og frjáls, og allt það. Svo, minnka, við erum að fara að hætta. Við skulum reyna að ganga úr skugga um að þetta raunverulega gerði safna. Við sjáum að það er, þannig að við erum á réttri leið. 

Við skulum opna binary_tree.c aftur. Það safnar. Við skulum fara niður og tryggja að við að setja nokkur símtöl til Inniheldur virka okkar - bara til að vera viss um að það er allt vel og gott. Til dæmis, þegar við gerðum nokkur vélarheiti í trénu okkar fyrr, við reyndum að leita upp þau gildi 6, 10 og 1, og við vissum að 6 væri í trénu, 10 var ekki á trénu, og 1 var ekki í trénu heldur. Við skulum nota þau dæmi um símtöl sem leið til að reikna út hvort Inniheldur virka okkar er að vinna. Til að gera það, ég ætla að nota printf virka, og við erum að fara að prenta út niðurstöðu að hringja til að geyma. Ég ætla að setja í streng "inniheldur (% d) = vegna  við erum að fara að stinga í gildi sem við erum að fara að leita að, og =% s \ n "og nota það sem band snið okkar. Við erum bara að fara að sjá - bókstaflega prenta út á skjáinn - það lítur út eins og virka símtalinu. Þetta er í raun ekki að virka símtalinu.  Þetta er bara strengur hannað til að líta út eins og virka símtalinu. 

Nú erum við að fara að stinga á þeim gildum. Við ætlum að reyna finna á 6, og þá er það sem við erum að fara að gera hér nota þessi ternary rekstraraðila. Við skulum sjá - inniheldur 6 - svo nú er ég búin að finna 6 og ef inniheldur 6 er satt, band sem við ætlum að senda til snið staf í% s er að fara til vera the band "true". Við skulum fletta yfir smá. Annars viljum við senda band "false" Ef inniheldur 6 False. Þetta er svolítið Guffi-útlit, en ég reikna að ég gæti eins vel að sýna hvað ternary rekstraraðili lítur út þar sem við höfum ekki séð það um hríð. Þetta verður gaman, handlaginn leið til að reikna út ef inniheldur virka okkar er að vinna. Ég ætla að fletta aftur yfir til vinstri, og ég ætla að afrita og líma þessa línu nokkrum sinnum. Það breytti sum af þessum gildum í kring, þannig að þetta er að fara að vera 1, og þetta er að fara að vera 10. 

Á þessum tímapunkti sem við höfum fengið gott Inniheldur virka. Við höfum fengið nokkur próf, og við munum sjá hvort þetta virkar allt. Á þessum tímapunkti sem við höfum skrifað nokkrar fleiri kóða. Tími til að hætta út og ganga úr skugga um að allt enn safnar. Hætta út og nú skulum reyna að gera tvöfaldur tré aftur. Jæja, það lítur út eins og við höfum fengið villu, og við höfum fengið þetta lýsa skýrt bókasafn virka printf. Það lítur út eins og við þurfum að fara í og ​​# include standardio.h. Og með því að, allt ætti að þýða. Við erum öll góð. Nú skulum reyna að keyra tvöfaldur tré og sjá hvað gerist. Hér erum við,. / Binary_tree, og við sjáum að, eins og við gerðum ráð fyrir - vegna þess að við höfum ekki innleitt inniheldur enn, eða öllu heldur, höfum við bara sett í staðinn falskur - sjáum við að það er bara aftur rangt fyrir þeim öllum, svo það er allt að vinna að mestu leyti nokkuð vel. 

Förum aftur í og ​​í raun að framkvæma eru á þessum tímapunkti. Ég ætla að fletta niður, súmma inn og - Mundu að reiknirit sem við notuðum var að við byrjuðum á rót hnút og þá á hvern hnút sem við lendum í, gera við samanburð, og byggt á þeirri samanburði við færa annaðhvort vinstri barn eða hægri barn. Þetta er að fara að líta mjög svipað leit tvöfaldur kóða sem við skrifaði áðan í tíma. Þegar við byrjum á, við vitum að við viljum halda í núverandi hnút sem við erum að horfa á, og núverandi hnút er að fara að frumstilla að rót hnút. Og nú erum við að fara að halda áfram í gegnum tré, og muna að okkar stífla ástand -  þegar við gekk reyndar í gegnum dæmi af hendi - var þegar við rakst á núll hnút, ekki þegar við skoðuðum núll barn, heldur þegar við fluttum reyndar í hnút í trénu og komist að því að við erum á núll hnút. Við ætlum að iterate þar nú er ekki jafn null. Og hvað ætlum við að gera? Við ætlum að prófa hvort (nú -> gildi == gildi), þá vitum við að við höfum í raun og veru fundið hnút sem við erum að leita að. Svo hér, getum við aftur satt. Annars viljum við sjá hvort gildið er minna en gildið. Ef gildi núverandi Hnútur er minna en gildið sem við erum að leita að, við erum að fara að flytja til hægri. Svo, nú = nú -> right_child, og annað, við erum að fara að flytja til vinstri. nú = nú -> left_child;. Pretty einfalt. 

Þú kannast líklega lykkjunnar sem lítur mjög svipað og þetta frá tvöfaldur leita fyrr í tíma, nema þá vorum við að takast á við lítil miðjan og hár. Hér höfum við bara að horfa á núverandi gildi, svo það er gott og einfalt. Við skulum vera viss um þetta virki. Fyrst skaltu ganga úr skugga um að það safnar. Útlit eins og það er. Við skulum reyna að keyra það. Og reyndar prentar það út allt sem við gerðum ráð fyrir. Það finnur 6 í trénu, er ekki að finna 10 því 10 er ekki í trénu, og finnur ekki 1 heldur því 1 er líka ekki á trénu. Flott efni. 

Alright. Við skulum fara aftur til forskriftir okkar og sjá hvað er næst. Nú vill það að bæta við fleiri hnútar í tré okkar. Það vill til að bæta við 5, 2 og 8, og að tryggja að okkar inniheldur kóða enn virkar eins og búast mætti. Við skulum fara að gera það. Á þessum tímapunkti, frekar en að gera það pirrandi að afrita og líma aftur, við skulum skrifa fall í raun að búa til hnút. Ef við fletta niður alla leið að helstu, sjáum við að við höfum verið að gera þetta mjög svipuð númerið aftur og aftur í hvert sinn sem við viljum búa til hnút. 

Við skulum skrifa fall sem mun í raun byggja upp hnút fyrir okkur og skila. Ég ætla að kalla það build_node. Ég ætla að byggja upp hnút með tilteknu gildi. Þysja inn hér. Það fyrsta sem ég ætla að gera er í raun að búa til pláss fyrir hnút á hrúga. Svo hnút * n = malloc (sizeof (hnút)), n -> gildi = gildi; og svo hér, ég er bara að fara að frumstilla öllum sviðum til að vera viðeigandi gildi. Og aftast, munum við aftur hnút okkar. Alright. Eitt að hafa í huga er að þetta virka hérna er að fara að skila bendi á minni sem hefur verið hrúga-úthlutað. Hvað er gott um þetta er að þessi hnútur núna - við verðum að lýsa því á hrúga því ef við lýst því á mánudaginn myndum við ekki vera fær um að gera það í þessa aðgerð svona. Þessi minni myndi fara út af umfangi og væri ógild ef við reyndum að nálgast það síðar. Þar sem við erum að lýsa hrúga-úthlutað minni, við erum að fara til verða að gæta frjáls það seinna fyrir áætlun okkar að ekki leka allir minni. Við höfum verið að punting á að fyrir allt annað í kóða bara fyrir sakir einfaldleika er á þeim tíma, en ef þú skrifar alltaf fall sem lítur svona út þar sem þú hefur fengið - sumir kalla það malloc eða realloc inni - þú vilt ganga úr skugga um að þú setur einhvers konar athugasemd hérna sem segir, hey, þú veist, skilar hrúga-úthlutað hnút frumstilla með liðin-í gildi. Og þá þú vilt vera viss um að þú settir í einhverskonar miða sem segir hringir að losa skilað minni. Þannig ef einhver alltaf fer og notar að virka, Þeir vita að það sem þeir fá til baka úr þeim virka á einhverjum tímapunkti verður að vera leystur. 

Miðað við að allt er vel og gott hér, við getum farið niður í númerið okkar og skipta öllum þessum línum hérna með símtöl til okkar byggja hnút virka. Við skulum gera það mjög hratt. Sá hluti sem við erum ekki að fara að skipta er þessi hluti hérna neðst þar sem við víra í raun upp hnúður til að benda á hvort annað, vegna þess að við getum ekki verið að gera aðgerð okkar. En við skulum gera rót = build_node (7), hnútur * þrír = build_node (3); hnút * sex = build_node (6), hnútur * níu = build_node (9),. Og nú, við vildum líka að bæta við hnúta fyrir - hnút * fimm = build_node (5), hnútur * átta = build_node (8); og hvað var hinn hnút? Við skulum sjá hér. Við vildum einnig bæta við 2 - hnút * tveir = build_node (2),. Alright. Á þessum tímapunkti, við vitum að við höfum fengið 7, 3, 9, og 6 allt hlerunarbúnað upp á viðeigandi hátt, en hvað um 5, 8, og 2? Til að halda öllu í góðu horfi, Vér vitum, að réttur barn THREE er 6. Svo ef við ætlum að bæta við 5, The 5 tilheyrir einnig í hægra megin á trénu sem 3 er rót, svo 5 tilheyrir sem vinstri barn 6. Við getum gert þetta með því að segja, sex -> left_child = fimm; og þá 8 tilheyrir sem vinstri barn 9, svo níu -> left_child = átta; og þá er 2 vinstri barn 3, svo að við getum gert það upp hér - þér -> left_child = tveir,. Ef þú hefur ekki alveg fylgst með því, ég legg til að þú draga það út sjálfur. 

Alright. Við skulum spara þetta. Við skulum fara út og ganga úr skugga um að það safnar, og þá getum við bætt á Inniheldur símtöl okkar. Útlit eins og allt enn safnar. Við skulum fara inn og bæta við í sumum inniheldur símtöl. Aftur, ég ætla að gera a lítill hluti af afrita og líma. Nú skulum leita að 5, 8 og 2. Alright. Við skulum vera viss um að þetta allt lítur vel út enn. Great! Vista og hætta. Nú skulum gera, safna saman, og nú skulum hlaupa. Frá niðurstöðum, það útlit eins og allt er að vinna bara gott og vel. Great! Svo nú höfum við fengið Contains okkar virka skrifað. Við skulum fara og byrja að vinna á hvernig á að setja hnúta í trénu þar sem við erum að gera það núna, er það ekki mjög fallegt. 

Ef við förum aftur til forskriftir, það biður okkur að skrifa fall sem kallast setja - aftur, aftur a bool um hvort eða ekki að við gætum í raun að setja hnút í tré - og þá gildi að setja inn í tré greinist eina rök til að setja virka okkar. Við munum koma aftur við ef við gætum örugglega setja hnút innihalda gildi í trénu, sem þýðir að við, einn, haft nóg minni, og síðan tvær að hnúturinn var ekki þegar til staðar í tré frá - Mundu, við erum ekki að fara að hafa afrit gildi í trénu, bara til að gera hlutina einfalt. Alright. Aftur til kóðann. Opnaðu það upp. Zoom í smá, þá fletta niður. Við skulum setja setja inn virka rétt fyrir ofan inniheldur. Aftur, það er að fara að vera kölluð bool setja (int gildi). Gefðu það svolítið meira pláss, og þá, eins og sjálfgefið, skulum setja á return false aftast. Nú neðst, við skulum fara á undan og í stað þess að handvirkt byggja hnúður í helstu okkur og tengi þá upp til að benda á hvert annað eins og við erum að gera, við munum treysta á virka setja inn okkar að gera það. Við munum ekki treysta á virka setja inn okkar að byggja allt tré frá grunni bara enn, heldur að við munum losna við þessar línur - we'll athugasemd út þessar línur - sem byggja hnúður 5, 8 og 2. Og í staðinn munum við setja símtöl til að setja virka okkar að ganga úr skugga um að það virkar. Hér förum. 

Nú höfum við athugasemd út þessar línur. Við höfum aðeins 7, 3, 9 og 6 á trénu okkar á þessum tímapunkti. Til að ganga úr skugga um að þetta er allt að vinna, getum við minnka, gera tvöfaldur tré okkar, keyra hana, og við getum séð að innihalda er nú að segja okkur að við erum algerlega rétt - 5, 8, og 2 eru ekki lengur í trénu. Fara aftur í kóða, og hvernig eigum við að fara að setja inn? Mundu það sem við gerðum þegar við vorum í raun að setja 5, 8 og 2 áður. Við spiluðum að Plinko leikur þar sem við byrjuðum á rót, fór niður tré eitt af eitt og eitt þar til við höfum fundið viðeigandi bilið, og þá erum við hlerunarbúnað í hnút á viðeigandi stað. Við ætlum að gera það sama. Þetta er í grundvallaratriðum eins og að skrifa kóðann sem við notuðum í inniheldur virka að finna stað þar sem hnúturinn að vera, og þá erum við bara að fara að setja hnút þarna. Við skulum byrja að gera það. 

Þannig að við höfum hnút * nú = rót, við erum bara að fara að fylgja inniheldur kóða til við komumst að því að það er ekki alveg að vinna fyrir okkur. Við ætlum að fara í gegnum tré meðan núverandi þátturinn er ekki núll, og ef við finnum gildi sem nú er jafnt gildi sem við erum að reyna að setja - Jæja, þetta er eitt af þeim tilvikum þar sem við gátum ekki raunverulega setja hnút í tré vegna þess að þetta þýðir að við erum með afrit gildi. Hér erum við í raun að fara að skila falskur. Nú, annars ef gildi nú er minna en gildi, Nú vitum við að við að færa til hægri  því gildið tilheyrir í hægri hluta gjaldmiðli tré. Annars erum við að fara að flytja til vinstri. Það er í grundvallaratriðum Contains okkar virka rétt þar. 

Á þessum tímapunkti, þegar við höfum lokið þessu while lykkju, nú músina okkar er að fara að benda á að null hvort aðgerðin hefur ekki nú þegar skilað. Við erum því með veik á stað þar sem við viljum að setja nýjan hnút. Hvað þarf að gera er að í raun byggja nýjan hnút, sem við getum gert nokkuð auðveldlega. Við getum notað frábær handlaginn byggja hnút okkar virka, og eitthvað sem við vissum ekki fyrr - við bara svona tók sem sjálfsagðan hlut, en nú munum við ekki bara að ganga úr skugga um - við munum prófa að ganga úr skugga um að gildi aftur með nýja hnút var í raun ekki null, vegna þess að við viljum ekki að byrja aðgang að minni ef það er núll. Við getum prófað til að tryggja að nýr hnútur er ekki jafnt og null. Eða í staðinn, getum við bara sjá hvort það er í raun núll, og ef það er núll, þá getum við bara aftur falskur snemma. 

Á þessum tímapunkti verðum við að vírinn nýjan hnút í viðeigandi stað hennar í trénu. Ef við lítum til baka á aðal og þar sem við vorum í raun raflögn í gildi áður, sjáum við hvernig við vorum að gera það þegar við vildum að setja 3 í trénu var við að nálgast vinstra barn rót. Þegar við setja 9 í trénu, við þurftum að fá aðgang að rétt barn rót. Við þurftum að hafa músina til foreldris í því skyni að setja inn nýtt gildi í tré. Fletta aftur upp að setja inn, það er ekki að fara að alveg að vinna hérna vegna þess að við höfum ekki foreldri músina. Það sem við viljum vera fær um að gera er að, á þessum tímapunkti, athuga gildi foreldris og sjá - og, nei, Ef gildi foreldris er minna en núverandi gildi, þá rétt barn foreldris skal nýja hnút; Annars vinstri barn foreldris ætti að vera nýr hnútur. En höfum við ekki þetta foreldri músina alveg enn. 

Til þess að fá það, við erum í raun að fara að fylgjast með því sem við förum í gegnum tré og finna viðeigandi stað í lykkju okkar ofan. Við getum gert það með því að fletta aftur upp að ofan virka setja inn okkar og rekja aðra músina breytu kallast foreldri. Við erum að fara að setja það jafnt null upphafi, og þá í hvert skipti sem við förum í gegnum tré, við erum að fara að setja foreldri músina til að passa við núverandi músina. Setja foreldri jafn gjald. This vegur, í hvert sinn sem við förum í gegnum, við erum að fara til að tryggja að þegar núverandi bendill fær incremented foreldri bendillinn segir það - bara eitt stig hærra en núverandi músina í trénu. Það allt lítur mjög vel út. 

Ég held að það eina sem við munum vilja til að stilla er þetta byggja hnút koma aftur null. Til þess að fá að byggja hnút í raun tekist aftur null, við verðum að breyta því kóða, því hér, prófað við aldrei að ganga úr skugga um að malloc skilaði gilt músina. Svo, ef (n = NULL!), Þá - ef malloc skilaði gilt músina, þá munum við að frumstilla hana, Annars munum við bara aftur og það mun á endanum aftur null fyrir okkur. Nú lítur allt mjög vel út. Við skulum vera viss um þetta í raun vinnur. Gera tvöfaldur tré, og ó, að við höfum fengið smá dót að fara á hér. 

Við höfum fengið óbeina yfirlýsingu um virka byggja hnút. Aftur með þessar vistþýðendur, við erum að fara að byrja á toppnum. Hvað það að þýða að ég er að hringja byggja hnút áður en ég hef reyndar lýst því. Við skulum fara aftur til kóðann virkilega fljótt. Flettu niður, og viss nógur, setja virka minn er lýst ofan byggja hnút virka, en ég er að reyna að nota byggja hnút inni insert. Ég ætla að fara í og ​​afrita - og þá líma byggja hnút virka leið upp hér að ofan. Þannig vonandi sem vilja vinna. Við skulum gefa þessu annað fara. Nú safnar það allt. Allt er gott. 

En á þessum tímapunkti, höfum við í raun ekki kallað Insert function okkar. Við vitum bara að það safnar, þannig að við skulum fara í og ​​setja nokkur símtöl inn Við skulum gera það í meginvirkni okkar. Hér, sagði við út 5, 8, og 2, og þá erum við ekki þráð þá upp hérna. Við skulum gera nokkrar símtöl til að setja, og við skulum líka nota sams konar efni sem við notuðum þegar við gert þessar printf símtöl til að tryggja að allt var að fá sett rétt. Ég ætla að afrita og líma, og í stað þess að finna að við erum að fara að gera Insert. Og í stað 6, 10, og 1, þá ætlum við að nota 5, 8 og 2. Þetta ætti vonandi að setja 5, 8 og 2 í tré. Safna saman. Allt er gott. Nú munum við í raun að keyra kerfi okkar. 

Allt skilaði rangar. Svo, 5, 8, og 2 ekki fara, og það lítur út eins Inniheldur ekki finna þá heldur. Hvað er að gerast? Við skulum súmma út. Fyrsta vandamálið var að setja virtist aftur rangt, og það lítur út eins og það er vegna þess að við fórum í staðinn okkar rangar símtali og við aldrei aftur satt. Við getum sett það upp. Annað vandamál er, nú jafnvel ef við gerum - vista þetta, hætta þessu, hlaupa að aftur, hafa þýða það, þá hlaupa það - sjáum við að eitthvað annað gerðist hér. The 5, 8, og 2 voru samt aldrei finna í trénu. Svo, hvað er að gerast? 

Við skulum taka a líta á þetta í reglunum. Við skulum sjá hvort við getum fundið þetta út. Við byrjum með foreldri ekki vera null. Við setjum núverandi bendilinn jafn rót músina, og við erum að fara að vinna okkur niður í gegnum tré. Ef núverandi hnút er ekki núll, þá vitum við að við getum flutt niður svolítið. Við setjum foreldri músina okkar til að vera jöfn núverandi músina, skoðaði gildi - ef gildin eru þau sömu við aftur rangar. Ef gildin eru minni fluttum við til hægri; Annars flutti við til vinstri. Þá erum við að byggja upp hnút. Ég stækka smá. Og hér erum við að fara að reyna að vírinn upp gildi að vera sú sama. Hvað er að gerast? Við skulum sjá hvort hugsanlega Valgrind getur gefið okkur vísbendingu. 

Ég vil nota Valgrind bara vegna Valgrind raun hleypur og segir þér ef það eru einhverjar minni villur. Þegar við hlaupum Valgrind á kóða, eins og þú sérð rétt here--Valgrind./binary_tree--and högg inn. Þú sérð að við vildum ekki hafa allir minni villa, þannig að það lítur út eins og allt er í lagi svo langt. Við gera hafa sumir minni lekur, sem við þekkjum, vegna þess að við erum ekki gerast til að losa eitthvað af hnúður okkar. Við skulum reyna að keyra gdb til að sjá hvað er í raun að gerast. Við munum gera gdb. / Binary_tree. Það stígvélum upp bara fínt. Við skulum setja brjóta lið á Insert. Við skulum hlaupa. Það lítur út eins og við aldrei kallað setja. Það lítur út eins og að vandamálið var bara að þegar ég breytt niður í aðal - allar þessar printf símtöl frá inniheldur - Ég hef aldrei raunverulega breytt þetta til að hringja inn. Nú skulum við gefa það a reyna. Við skulum taka saman. Allt lítur vel út þar. Nú skulum reyna að keyra það, sjá hvað gerist. Alright! Allt lítur nokkuð það gott. 

Endanleg hlutur til að hugsa um er, eru einhverjar brún tilvikum á þessu setja inn? Og það kemur í ljós að vel, sá brún ef það er alltaf áhugavert að hugsa um er, hvað gerist ef tré er tómur og þú kallar þetta setja inn virka? Mun það virka? Jæja, við skulum gefa það a reyna. - Binary_tree c. - Leiðin sem við erum að fara að prófa þetta er, við erum að fara niður í virkni okkar, og frekar en raflögn þessa tengipunkta upp svona, við erum bara að fara að tjá sig út um allt hlutur, og í stað þess að raflögn upp hnúður sjálf, getum við í raun bara að fara á undan og eyða þessu öllu. Við ætlum að gera allt hringja til að setja inn. Svo skulum við gera - í stað 5, 8, og 2, við erum að fara að setja inn 7, 3 og 9. Og þá munum við einnig vilja til að setja 6 eins og heilbrigður. Vista. Hætta. Gerðu tvöfaldur tré. Það safnar öllum. Við getum bara hlaupa það er eins og sjá hvað gerist, en það er líka að fara að vera mjög mikilvægt að ganga úr skugga um að Við höfum engar minni villur, þar sem þetta er eitt af þeim tilvikum brún okkar sem við vitum um. 

Við skulum vera viss um að það virkar vel á Valgrind, sem við munum gera við bara að keyra Valgrind. / binary_tree. Það lítur út eins og við höfum örugglega eina villu úr einu samhengi - við höfum þetta skiptingu kenna. Hvað gerðist? Valgrind segir reyndar okkur hvar það er. Minnka svolítið. Það lítur út eins og það er að gerast í aðgerð setja inn okkar, þar sem við höfum ógilt lesa af stærð 4 á insert, lína 60. Við skulum fara til baka og sjá hvað er að gerast hér. Minnka mjög fljótur. Ég vil vera viss um að það er ekki að fara að brún skjásins þannig að við getum séð allt. Dragðu að í smá. Alright. Flettu niður og vandamálið er hérna. Hvað gerist ef við fá niður og núverandi hnút okkar er þegar núll, foreldri hnút okkar er núll, þannig að ef við horfum upp á mjög toppur, hérna - Ef þetta á meðan lykkja aldrei framkvæmir vegna núverandi gildi okkar er núll - rót okkar er núll svo nú er núll - þá foreldri okkar aldrei fær sett gjald eða gilt gildi, svo, foreldri verður einnig null. Við þurfum að muna að athuga fyrir það Þegar við fá niður hér og við byrjum að fá aðgang að gildi foreldris. Svo, hvað gerist? Jæja, ef foreldri er núll - if (foreldri == NULL) - þá vitum við að Það má ekki vera neitt í trénu. Við verðum að reyna að setja það á the rót. Við getum gert það með því bara að setja rót jafnt nýja hnút. Þá á þessum tímapunkti, er það ekki raunverulega vilja til að fara í gegnum þessar annars. Þess í stað, hérna, getum við gert annaðhvort annað-hvort-annað, eða við gætum sameina allt upp hér er annað, en hér við verðum bara að nota annað og gera það þannig. Nú ætlum við að prófa að tryggja að foreldri okkar er ekki null áður en þá í raun að reyna að fá aðgang viðfangsefnum hennar. Þetta mun hjálpa okkur að koma í veg fyrir skiptingu kenna. Svo, við hætta, minnka, safna saman, hlaupa. 

Engin villa, en við höfum samt fullt af leka minni vegna þess að við vissum ekki að losa eitthvað af hnúður okkar. En ef við förum hér upp og við lítum á útprentun okkar, sjáum við að vel lítur, eins og öll sett inn okkar voru aftur satt, sem er gott. The sett er allt satt, og síðan viðeigandi inniheldur símtöl eru einnig satt. 

Gott starf! Það lítur út eins og við höfum tekist skrifað inn. Það er allt sem við höfum fyrir Problem Set Specification þessari viku. Ein skemmtileg áskorun að hugsa um er hvernig þú myndi reyndar fara í og frjáls öllum hnúður í þessu tré. Við getum gert það í mörgum mismunandi vegu, en ég skal fara að allt að þér að prófa, og sem gaman áskorun, reyna að ganga úr skugga um að þú getur gengið úr skugga að Valgrind skýrslu skilar engar villur og enginn leki. 

Gangi þér vel á þessari viku Huffman kóðun vandamál setja, og við munum sjá þig í næstu viku! [CS50.TV]