[Powered by Google Translate] [Kafli 7: öruggari] [Rob Bowden] [Harvard University] [Þetta er CS50] [CS50.TV] Allt í lagi. Svo eins og ég sagði í bréfinu mínu, þetta er að fara að vera tvöfaldur-tré-ákafur kafla. En það eru ekki svo margar spurningar. Þannig að við erum að fara að reyna að draga út hverja spurningu og fara í sársaukafullar smáatriðum allra bestu leiðir til að gera hlutina. Svo rétt í byrjun, fara við í gegnum teikningar sýni af tvöfaldur tré og efni. Svo hér, "Mundu að tvöfaldur tré er hnúður svipuð í tengda listanum, nema í stað þess að einn músina eru tveir: einn fyrir "barnið" vinstri og einn fyrir hægri barnsins. " Svo tvöfaldur tré er bara eins og tengda lista, nema strúktúrinn er að fara að hafa tvo punkta. Það er trinary tré, sem eru að fara að hafa þrjá punkta, eru N-áhrærir tré, sem bara hafa almenna músina sem þú hefur þá til malloc að vera nógu stórt til að hafa nóg ábendingum til allar mögulegar börn. Svo gerist tvöfaldur tré bara að hafa góða tala af tveimur. Ef þú vilt, getur þú gefa tengda listanum sem unary tré, en ég held ekki að einhver kallar það að. "Teiknaðu kassa-og-Örvar skýringarmynd af tvíundartrés hnút inniheldur uppáhalds númer nate er, 7, þar sem hvert barn bendillinn er null. " Svo iPad ham. 

Það er að fara að vera nokkuð einfalt. Við erum bara að fara að hafa hnút, ég teikna það sem ferningur. Og ég ætla að draga gildi hér. Þannig gildi mun fara í hér, og þá niður hér við munum hafa vinstri bendilinn til vinstri og hægri bendilinn til hægri. Og það er mjög mikið svo venju að kalla það vinstri og hægri, bendillinn nöfn. Báðir þessir eru að fara að vera null. Það verður bara að vera núll, og það verður bara að vera núll. Allt í lagi. Svo aftur hingað. "Með tengist lista, við höfðum aðeins að geyma músina að fyrsta hnút í skránni til að muna allt sem tengist lista, eða alla lista. Sömuleiðis með tré, höfum við bara að geyma músina á einum hnút til að muna allt tréð. Þetta hnútur er Calle á 'rót' í tré. Byggja á myndinni þinni úr áður eða draga nýjan þannig að þú ert með kassa-og-Örvar lýsing af a tvöfaldur tré með gildið 7, en 3 í vinstri, þá 9 til hægri, og svo 6 til hægri af 3. " Við skulum sjá hvort ég man allt sem í höfðinu á mér. Þannig að þetta er að fara að vera rót okkar upp hér. Við munum hafa sumir músina einhversstaðar, eitthvað sem við munum kalla rót, og það er að benda að þetta strákur. Nú til að gera nýjan hnút, Hvað höfum við, 3 til vinstri? Svo nýtt hnút með 3, og það bendir fyrst null. Ég ætla bara að setja N. Nú viljum við gera að fara til vinstri á 7. Þannig að við að breyta þessu bendi til nú benda á þennan gaur. Og við gerum það sama. Við viljum 9 hérna sem upphaflega bara segir null. Við erum að fara að breyta þessu músina, benda til 9, og nú viljum við að setja 6 til hægri af 3. Svo það er að fara til - gera 6. Og þessi strákur mun benda þar. Allt í lagi. Svo það er allt það biður okkur um að gera. 

Nú skulum fara yfir nokkur hugtök. Við töluðum nú þegar um hversu rót trésins er efst mest hnút í trénu. Sá sem inniheldur 7. Hnúður á the botn af trénu kallast blöðin. Sérhver hnútur sem bara hefur null eins og börn hans eru a leaf. Svo það er hægt, ef tvíundartré okkar er bara einn hnút, að tré er lauf, og það er það. "The 'hæð' í tré er fjöldi hops sem þú þarft að gera að fá frá the toppur til blaða. " Við munum fá inn í annað, munurinn milli jafnvægi og ójafnvægi tvöfaldur tré, en nú er heildar hæð þessu tré Ég myndi segja 3, en ef þú telur fjölda hops þú þarft að gera til að fá að 9, þá er það í raun aðeins í hæð 2. Núna er þetta ójafnvægi tvöfaldur tré, en við munum tala um jafnvægi þegar það fær að vera viðeigandi. Svo nú að við getum talað um hnúta í tré í skilmálum miðað til annarra hnúta í trénu. Svo nú höfum við foreldrar, börn, systkini, feður, og niðjar. Þeir eru ansi skynsemi, hvað þeir meina. Ef við spyrjum - foreldra þess. Svo er það foreldri 3? [Nemendur] 7. >> Já. Foreldri er bara að fara að vera það sem bendir til þín. Þá það eru börn 7? [Nemendur] 3 og 9. >> Já. Takið eftir að "börn" bókstaflega þýðir börn, svo 6 myndi ekki gilda, því það er eins og barnabarnið. En ef við förum afkomendur, svo það eru afkomendur 7? [Nemendur] 3, 6 og 9. >> Já. Synir rót hnút er að fara að vera allt í trénu, nema kannski rót hnút sjálft, ef þú vilt ekki að íhuga að afkomandi. Og að lokum, feður, svo það er hið gagnstæða átt. Svo það eru forfeður 6? [Nemendur] 3 og 7. >> Já. 9 er ekki innifalinn. Það er bara bein ætterni baka í rót er að fara að vera feður yðar. 

"Við segjum að tvöfaldur tré er" skipað "ef fyrir hvern hnút í tré, öllum niðjum sínum á vinstri hafa minna gildi og öll þau á hægri hafa meiri gildi. Til dæmis, er tré ofan pantað en það er ekki aðeins mögulegt pantað fyrirkomulag. " Áður en við komum að því, að panta tvöfaldur tré er einnig þekktur eins og a tvöfaldur leita tré. Hér verður að vera að kalla það pantaði tvöfaldur tré, en ég hef aldrei heyrt það kallað að panta tvöfaldur tré áður, og á spurningakeppni við erum miklu líklegri til að setja tvöfaldur leita tré. Þeir eru eitt og hið sama, og það er mikilvægt að þú þekkja greinarmun á tré tvöfaldur og tvöfaldur leita tré. A tvöfaldur tré er bara tré, sem bendir til tvennt. Hver hnútur bendir til tvennt. Það er engin rök um gildi sem það bendir á. Svo eins og hérna, þar sem það er tvöfaldur leita tré, við vitum að ef við förum eftir af 7, þá allt af þeim gildum sem við getum hugsanlega náð með því að fara til vinstri á 7 að vera minna en 7. Takið eftir að öll gildi minna en 7 eru 3 og 6. Þeir eru allir til vinstri á 7. Ef við förum til hægri 7, allt þarf að vera meira en 7, svo er 9 til hægri 7, svo við erum góð. Þetta er ekki málið fyrir tvíundartrés, fyrir venjulega tvöfaldur tré við getum bara 3 efst, 7 til vinstri, 9 til vinstri 7, það er engin röðun gildi neinu tagi. Nú ætlum við í raun ekki að gera þetta því það er leiðinlegur og óþarfa, en "reyna að draga eins marga panta tré sem hægt er að hugsa um nota númer 7, 3, 9 og 6. Hversu margar mismunandi fyrirkomulag er þarna? Hver er hæð hvers og eins? " 

Við munum gera nokkrar, en helsta hugmynd er, þetta er á engan hátt einstök framsetning tvíundartrés inniheldur þessi gildi. Allt sem við þurfum er einhver tvöfaldur tré, sem inniheldur 7, 3, 6, og 9. Önnur möguleg gildi einn væri rót er 3, fara til vinstri og það er 6, fara til vinstri og það er 7, fara til vinstri og það er 9. Það er fullkomlega gild tvöfaldur leita tré. Það er ekki mjög gagnlegt, vegna þess að það er bara eins og tengda lista og allar þessar ábendingar eru bara null. En það er gild tré. Já? [Nemandi] Ekki gildin verða að vera meiri á hægri? Eða er þetta -? >> Þetta sem ég ætlaði að fara í hina áttina. Það er líka - já, við skulum skipta því. 9, 7, 6, 3. Góður fengur. Það hefur samt að hlýða hvað tré tvöfaldur leit er að gera. Svo allt til vinstri verður að vera minna en hverjum hnút. Við gætum bara fara, segja, þetta 6 og setja það hér. Nei, við getum það ekki. Hvers vegna að halda ég að gera það? Við skulum gera - hér er 6 Hér er 7, 6 stig 3. Þetta er enn í gildi tvöfaldur leita tré. Hvað er rangt ef ég - við skulum sjá hvort ég get komið upp með samkomulagi. Já, allt í lagi. Svo hvað er rangt við þetta tré? Ég held að ég hef nú þegar gefið þér vísbendingu um að það sé eitthvað athugavert við það. Hvers vegna að halda ég að gera það? Allt í lagi. Þetta lítur sanngjarnt. Ef við horfum á hvern hnút, eins og 7, síðan til vinstri á 7 er a 3. Svo við höfum 3, hlutur til hægri 3 er 6. Og ef þú horfir á 6, hlutur til hægri 6 er 9. Svo hvers vegna er þetta ekki gild tvöfaldur leita tré? [Nemendur] 9 er enn til vinstri á 7. >> Já. Það verður að vera satt að öll gildi sem þú getur hugsanlega ná því að fara til vinstri á 7 er minna en 7. Ef við förum eftir af 7, fáum við til 3 og við getum enn fengið til 6, getum við samt fá að 9, en eftir að hafa farið minna en 7, við ættum ekki að vera fær um að fá að tala sem er stærri en 7. Svo er þetta ekki gild tvöfaldur leita tré. 

Bróðir minn var reyndar viðtal spurningu það var í rauninni þetta, bara númerið upp eitthvað til að sannreyna hvort tréð er tvöfaldur leita tré, og svo það fyrsta sem hann gerði var bara að athuga ef vinstri og hægri séu réttar, og þá iterate niður. En þú getur ekki bara að gera það, þú þarft að fylgjast með af því að nú þegar ég hef farið til vinstri 7, allt í þessu subtree verður að vera minna en 7. Rétt reiknirit þarf að halda utan af mörk sem gildi geta hugsanlega falla inn Við munum ekki fara í gegnum þá alla. Það er a ágætur endurkomu tengslum, þó að við höfum ekki fengið að þeim, eða við munum ekki komast að þeim, skilgreina hversu margir í raun eru. Þannig að það eru 14 af þeim. Hugmyndin um hvernig þú vilt gera það er stærðfræðilega eins, þú getur valið hvaða einn einn að vera rót hnút, og svo ef ég velja 7 að rót hnút, þá eru, segja, nokkrar tölur sem hægt er að fara að vera vinstri hnútur minn, og það eru nokkrar tölur sem hægt er að réttur hnútur minn, en ef ég hef n heildarfjölda, þá upphæð sem hægt er að fara til vinstri plús upphæð sem getur farið til hægri er n - 1. Svo á eftir eru tölur, þeir verða að vera fær um að fara annað hvort til vinstri eða hægri. Það virðist erfitt að ef ég setti 3 fyrsta þá allt að fara til vinstri, en ef ég setti 7, þá er nokkur atriði sem hægt fara í vinstri og sumt getur farið til hægri. Og '3 fyrst ég ætlaði allt getur farið til hægri. Það er í raun, hefur þú bara að hugsa um það eins og, hversu margt getur farið á næsta stig af trénu. Og það kemur út að vera 14, eða þú getur teiknað þau öll, og þá munt þú fá 14. 

Fara aftur hingað, "Skipað tvöfaldur tré er flott vegna þess að við getum leitað í þeim á mjög svipaðan hátt og leita yfir raðað fylki. Til að gera það, byrjum við á rót og vinna okkur niður tré að leyfi, stöðva gildi hver hnútur gegn gildi sem við erum að leita að. Ef gildi núverandi Hnútur er minna en gildið sem við erum að leita að, þú ferð næst til hægri barn hnúturinn er. Annars, þú ferð vinstra barn hnúturinn er. Á einhverjum tímapunkti munt þú annaðhvort að finna gildi sem þú ert að leita að, eða þú munt hlaupa inn í núll, gefur til kynna að gildi er ekki í tré. " Ég þarf að gera annað uppkast the tré sem við höfðum áður, sem mun taka annað. En við viljum að líta upp hvort 6, 10, og 1 er í trénu. Og hvað það var, 7, 9, 3, 6. Allt í lagi. Tölurnar sem þú vilt að líta upp, viljum við horfa upp 6. Hvernig er þetta reiknirit vinna? Jæja, höfum við einnig nokkur rót músina til tré okkar. Og við myndum fara að rót og segja, er þetta gildi jafnt gildi við erum að leita að? Þannig að við erum að leita að 6, þannig að það er ekki jafn. Þannig höldum við áfram, og nú segjum við, allt í lagi, svo er 6 minna en 7. Er það að við viljum fara til vinstri, eða viljum við fara til hægri? [Nemandi] Vinstri. >> Já. Það er verulega auðveldara, allt sem þú þarft að gera er að draga eina mögulega hnút í tré og þá áttina - í stað þess að reyna að hugsa í hausnum, allt í lagi, ef það er minna, get ég farið til vinstri eða fara rétt, bara að horfa á þessa mynd, það er mjög ljóst að ég þarf að fara til vinstri ef hnútur er meiri en gildi sem ég er að leita að. Svo þú ferð til vinstri, núna er ég á 3. Ég vil - 3 er minna en gildið sem ég er að leita að, sem er 6. Svo förum við til hægri, og nú er ég á endanum á 6, sem er gildi sem ég er að leita að, svo ég aftur satt. Næsta virði ég ætla að leita að er 10. Allt í lagi. Svo 10, nú er að fara að - skera burt það - fara að fylgja rót. Nú, 10 er að fara að vera meira en 7, svo ég vil að líta til hægri. Ég ætla að koma hérna, 10 er að fara að vera meiri en 9, þannig að ég ætla að fara til að vilja líta til hægri. Ég kem hérna, en hérna er ég í null. Hvað á ég að gera ef ég högg null? [Nemandi] return false? >> Já. Ég vissi ekki að finna 10. 1 er að fara til vera a nánast eins mál, nema það er bara að fara að vera hreifi, í stað þess að leita niður hægra megin, ég er að fara að horfa niður á vinstri hlið. 

Nú ég held að við í raun fá að kóða. Hér er þar - opna CS50 tæki og sigla leið þína þar, en þú getur líka bara gert það í rúm. Það er líklega tilvalið að gera það í bili, vegna þess að við getum unnið í rúm. "Fyrst við þurfum nýja tegund skilgreiningu fyrir tvíundartrés hnút innihalda int gildi. Notkun boilerplate typedef neðan, búa til nýja tegund skilgreiningu fyrir hnút í tvíundartrés. Ef þú færð fastur. . . "Bla, bla, bla. Lagi. Svo skulum setja boilerplate hér, typedef struct hnút, og hnút. Já, allt í lagi. Svo það eru reitir sem við erum að fara að vilja í hnút okkar? [Nemandi] Int og þá tvo ábendingum? >> Int gildi, tveir ábendingum? Hvernig skrifa ég punkta? [Nemandi] strúktúr. >> Ég ætti að súmma inn Já, svo strúktúr hnút * vinstri, og strúktúr hnút * rétt. Og muna umræðu frá síðasta tíma, að þetta gerir ekkert vit, það gerir ekkert vit, þetta gerir ekkert vit. Þú þarft allt það til að skilgreina þetta endurkvæma strúktúr. Jæja, svo það er það tré okkar er að fara að líta út. Ef við fengum trinary tré, þá hnúturinn getur litið út B1, B2, strúktúrinn hnút * B3, þar sem B er útibú - í raun, ég hef meira heyrt það vinstri, miðja, hægri, en hvað. Við umönnun aðeins um tvöfaldur, svo til hægri, vinstri. "Nú lýsa alþjóðlegt hnút * breytu fyrir rót af trénu." Þannig að við erum ekki að fara að gera það. Til að gera hlutina aðeins erfiðari og fleiri almenn, við munum ekki hafa alþjóðlegt hnút breytu. Þess í stað í helstu munum lýsa öllum okkar hnút hluti, og það þýðir að neðan, þegar við byrjum að keyra Inniheldur virka okkar og setja virka okkar, í stað þess að finna okkar virka bara að nota þessa alþjóðlegu hnút breytu, við erum að fara að hafa það að taka sem rök trénu, sem við viljum það til að vinna. Having alþjóðlegt breytu átti að gera hlutina auðveldari. Við ætlum að gera hlutina erfiðari. Nú taka eina mínútu eða svo bara að gera þetta svoleiðis, þar inni á helstu sem þú vilt búa til þetta tré, og það er allt sem þú vilt gera. Prófaðu og reisa þetta tré í helstu virka. 

Allt í lagi. Svo þú þarft ekki einu sinni að hafa reist tré alla leið enn. En einhver hefur eitthvað sem ég gæti draga upp til að sýna hvernig maður gæti byrjað að byggja slíkt tré? [Nemandi] Einhver er að lemja, að reyna að komast út. [Bowden] Hver ánægð með byggingu tré þeirra? [Nemandi] Jú. Það er ekki gert. >> Það er allt í lagi. Við getum bara að klára - ó, þú getur vistað það? Húrra. Svo hér höfum við - ó, ég skera örlítið af. Er ég aðdregna í? Þysja inn, fletta út. >> Ég er með spurningu. >> Já? [Nemandi] Þegar þú skilgreinir struct, eru hlutir eins og frumstilla við neitt? [Bowden] Nei >> lagi. Svo þú þyrftir að frumstilla - [Bowden] Nei Þegar þú skilgreinir, eða þegar þú lýsa strúktúr, það er ekki frumstilla við vanræksla, það er bara eins og ef þú lýsa heiltala. Það er nákvæmlega það sama. Það er eins og hvert einstökum sviðum hennar geta haft sorp gildi í það. >> Og það er hægt að skilgreina - eða að lýsa yfir strúktúr á þann hátt að það er frumstilla þá? [Bowden] Já. Svo, smákaka frumstilling setningafræði er að fara að líta út eins og - Það er tvær leiðir sem við getum gert þetta. Ég held að við ættum að þýða það til að tryggja Clang einnig gerir þetta. Röð rök sem koma í strúktúr, þú setur sem röð rök innan þessara hrokkið axlabönd. Svo ef þú vilt að frumstilla hana 9 og fór að null og þá rétt að vera núll, það væri 9, null, null. Hinn kosturinn er, og ritstjóri er ekki eins og þetta setningafræði, og það telur Ég vil nýja blokk, en hinn kosturinn er eitthvað eins og - hér, ég setti hana á nýja línu. Þú getur skýrt sagt, gleyma ég nákvæmlega setningafræði. Svo þú getur sérstaklega takast á við þær með nafni og segi, . C, eða. Gildi = 9,. Vinstri = NULL. Ég giska á þessi þörf til vera kommum. . Rétt = NULL, þannig að þetta vegur þú ert ekki raunverulega þörf til vita röð struct, og þegar þú ert að lesa þetta, það er miklu skýrari um hvaða gildi er verið að frumstilla til. 

Þetta gerist að vera einn af þeim hlutum sem - svo, að mestu leyti, C + + er superset C. Hægt er að taka C kóða, færa það yfir í C ​​+ +, og það ætti að safna saman. Þetta er eitt af því sem C + + styður ekki, svo að fólk hættir ekki að gera það. Ég veit ekki hvort það er eina ástæðan að fólk hafa tilhneigingu til að gera það, en raunin þar sem ég þurfti að nota það þarf að vinna með C + + og svo ég gæti ekki notað þetta. Annað dæmi um eitthvað sem er ekki að vinna með C + + er hvernig malloc skilar "void *," tæknilega, en þú getur bara segja char * x = malloc hvað, og það verður sjálfkrafa varpað á char *. Að sjálfvirk kastað gerist ekki í C + +. Það myndi ekki þýða, og þú vildi sérstaklega þarf að segja char *, malloc, hvað, að greiða það til a char *. Það eru ekki margir hlutir sem C og C + + ósammála um, en þeir eru tveir. Svo munum við fara með þessum setningafræði. En jafnvel þótt við vildum ekki fara með þeim setningafræði, hvað er - gæti verið athugavert við þetta? [Nemandi] Ég þarf ekki að dereference það? >> Já. Mundu að örin hafi óbeina dereference, og svo þegar við erum bara að takast á við a struct, við viljum nota. að fá á sviði inni í strúktúr. Og eina skiptið sem við notum ör er þegar við viljum gera - Jæja, ör jafngildir - það er það sem það hefði átt ef ég nota ör. Allt ör þýðir er, dereference þetta, núna er ég á struct, og ég get á þessu sviði. Annaðhvort fá sviði beint eða dereference og fá sviði - Ég held að þetta ætti að vera gildi. En hér er ég að fást við bara strúktúr, ekki músina til strúktúr, og svo ég get ekki notað á örina. En þessi tegund af hlutur sem við getum gert fyrir alla hnúta. Guð minn góður. Þetta er 6, 7, og 3. Þá getum við sett upp útibú í trénu okkar, getum við fengið 7 - við getum haft, vinstri þess að benda á 3. Svo hvernig gera við það? [Nemendur, óskiljanlegur] >> Já. Heimilisfang node3, og ef þú did ekki hafa netfang, þá er það bara ekki saman. En mundu að þetta eru ábendingar til næstu tengipunkta. Rétt að benda á að 9, og 3 ætti að benda á rétt í 6. Ég held að þetta sé allur setja. Allar athugasemdir eða spurningar? [Námsmaður, óskiljanlegur] Rót er að fara að vera 7. Við getum bara sagt hnút * PTR = eða rót, = & node7. 

Að því er varðar okkar, við erum að fara að takast á við setja inn, þannig að við erum að fara til að vilja skrifa aðgerð til að setja inn í þennan tvíundartrés og settu er óhjákvæmilega að fara að hringja malloc að búa til nýjan hnút á þessu tré. Svo hlutirnir eru að fara að fá sóðalegur með því að sumir hnúður eru nú á mánudaginn og aðrir hnútar eru að fara að enda upp á hrúga þegar við setja þá. Þetta er fullkomlega gild, en eina ástæðan við erum fær um að gera þetta á mánudaginn er vegna þess að það er svo háttuð dæmi sem við þekkjum trénu er ætlað að vera smíðuð 7, 3, 6, 9. Ef við ekki hafa það, þá myndum við ekki þurfa að malloc í fyrsta sæti. Eins og við munum sjá svolítið seinna, ættum við að vera malloc'ing. Núna er það fullkomlega eðlilegt að setja á mánudaginn, en við skulum breyta þessu til malloc framkvæmd. Svo hvert þeirra er nú að fara að vera eitthvað eins og hnút * node9 = malloc (sizeof (hnút)). Og nú erum við að fara að gera stöðva okkar. if (node9 == NULL) - ég vildi ekki að - skila 1, og þá getum við gert node9-> því nú er það bendi, gildi = 6, node9-> vinstri = NULL, node9-> hægri = NULL, og við erum að fara að gera það fyrir hvert af þessum hnúður. Þannig að í stað, skulum setja það inni í sér virka. Við skulum kalla það hnút * build_node, og þetta er nokkuð svipað og API sem við veitum til Huffman kóðun. Við gefa þér upphafsstillingarlisti virka fyrir tré og deconstructor "virka" fyrir þá tré og það sama fyrir skógum. 

Svo hér erum við að fara að hafa upphafsstillingarlisti virka bara byggja hnút fyrir okkur. Og það er að fara að líta nokkurn veginn nákvæmlega eins og þetta. Og ég er enn að fara að vera löt og ekki breyta heiti breytu, jafnvel þótt node9 gerir ekkert vit lengur. Oh, held ég gildi node9 ætti ekki að hafa verið 6. Nú getum við aftur node9. Og hér erum við að fara aftur null. Allir sammála um að byggja-a-hnút virka? Svo nú getum við bara kalla það að byggja hvaða hnút með tilteknu gildi og null ábendingum. Nú getum við kalla það, getum við gert hnút * node9 = build_node (9). Og við skulum gera. . . 6, 3, 7, 6, 3, 7. Og nú viljum við setja upp sömu ábendingar, nema nú allt er þegar í skilmálar af ábendingum þannig að ekki lengur þörf heimilisfang. Allt í lagi. Svo er það síðasta sem ég vil gera? Það er villa-stöðva sem ég ætla ekki að gera. Hvað er byggja hnút aftur? [Námsmaður, óskiljanlegur] >> Já. Ef malloc tókst, verður það aftur null. Þannig að ég ætla að lazily setja hana niður hér í stað þess að gera skilyrði fyrir hvert. Ef (node9 == NULL, eða - jafnvel einfaldari, þetta jafngildir að bara ef ekki node9. Svo ef ekki node9 eða ekki node6 eða ekki node3 eða ekki node7, skila 1. Kannski ættum við að prenta malloc mistókst, eða eitthvað. [Nemandi] er ósatt jafnt null eins og heilbrigður? [Bowden] Allir núll gildi er falskur. Svo er núll núll gildi. Zero er núll gildi. False er núll gildi. Allir - nánast aðeins 2 núll gildi eru null og núll, falskur er bara kjötkássa skilgreint sem núll. Það gildir einnig ef við gerum lýsa alþjóðlegt breytu. Ef við gerðum með hnút * rót upp hér, þá - The ágætur hlutur óður í alþjóðlegum breytur er að þeir hafa alltaf byrjunar gildi. Það er ekki satt að virka, hvernig inni hér, Ef við höfum, eins og hnút * eða hnút x. Við höfum ekki hugmynd um hvað x.value, x.whatever, eða við gætum prentað þá og þeir gætu verið handahófskennt. Það er ekki satt að alþjóðlegum breytur. Svo hnút rót eða hnút x. Sjálfgefið allt sem er alþjóðlegt, ef ekki beinlínis frumstilla að einhverju gildi, hefur núll gildi sem gildi þess. Svo hér, hnút * rót, eigum við ekki beinlínis frumstilla hana neitt, svo sjálfgefið gildi hennar verður núll, sem er núll gildi ábendingum. Sjálfgefið gildi x er að fara að þýða að x.value er núll, x.left er núll, og x.right er null. Svo þar sem það er struct, öllum sviðum strúktúr verður núll gildi. Við þurfum ekki að nota það hér, þó. [Námsmaður] The structs eru öðruvísi en aðrar breytur, og aðrar breytur eru sorp gildi, þetta eru núll? [Bowden] Aðrir gildi líka. Svo í x, x verður að vera núll. Ef það er á alþjóðlegum umfangi, það hefur óákveðinn greinir í ensku byrjunar-gildi. >> Lagi. [Bowden] Annaðhvort upphaflega gildið sem þú gafst henni eða núll. Ég held að það sér um þetta allt. 

Allt í lagi. Svo spyr næsta hluta af þeirri spurningu, "Nú erum við að skrifa fall sem kallast inniheldur með frumgerð af bool inniheldur int gildi. " Við erum ekki að fara að gera bool inniheldur int gildi. Frumgerð okkar er að fara að líta út eins og bool inniheldur (int gildi. Og þá erum við líka að fara að gefa það á tréð að það ætti að stöðva til að sjá hvort það hefur þessi gildi. Svo hnút * tré). Allt í lagi. Og þá getum við kalla það með eitthvað eins og, Kannski við munum vilja printf eða eitthvað. Inniheldur 6, rót okkar. Það ætti að fara aftur einn eða sanna, en inniheldur 5 rót ætti return false. Svo taka a second til að framkvæma þetta. Þú getur gert það annað hvort iteratively eða undirmöppum. The ágætur hlutur óður í the vegur sem við höfum sett það upp að það lánar sig til endurkvæma lausn okkar miklu auðveldara en á heimsvísu-breyta leið gerði. Vegna þess að ef við höfum bara innihalda int gildi, þá höfum við enga leið recursing niður subtrees. Við yrðum að hafa sérstakan hjálpar fall sem recurses niður subtrees fyrir okkur. En þar sem við höfum breytt það að taka tré sem rök, sem hún hefði alltaf verið í fyrsta sæti, nú getum við Kafa fleiri auðveldlega. Svo endurtekningu eða endurkvæma, munum við fara yfir bæði, en við munum sjá að endurkvæma endar að vera mjög auðvelt. Allt í lagi. Hefur einhver hafa eitthvað við að vinna með? 

[Nemandi] Ég hef fengið endurtekningu lausn. >> Allt í lagi, endurtekningu. Jæja, þetta lítur vel út. Svo, langar að ganga okkur í gegnum það? [Nemandi] Jú. Svo ég setja afleysingamanneskja breytu til að fá fyrsta hnút í tré. Og svo ég looped bara í gegnum meðan afleysingamanneskja ekki jafn null, svo á meðan enn var í trénu, held ég. Og ef gildið er jafnt gildi sem afleysingamanneskja bendir til, þá skilar það sem gildi. Annars stöðva það ef það er á hægri eða vinstri hlið. Ef þú færð einhvern tíma aðstæður þar sem það er ekkert meira tré, þá skilar það - það hættir lykkjunnar og skilar falskur. [Bowden] lagi. Svo virðist sem góður. Einhver hefur einhverjar athugasemdir um neitt? Ég hef ekki rétt athugasemdir yfirleitt. The einn hlutur sem við getum gert er þetta strákur. Oh, það er að fara að fara smá millisítt. Ég laga það upp. Allt í lagi. 

Allir ættu að muna hvernig ternary virkar. Það hefur ákveðið Skyndipróf verið í fortíðinni að gefa þér valkost með ternary rekstraraðila, og segja, þýða það, að gera eitthvað sem ekki nota ternary. Svo er þetta mjög algeng tilfelli af þegar ég vildi hugsa að nota ternary, þar sem ef einhver skilyrði sett breytu í eitthvað, annars sett þessi sömu breytu í eitthvað annað. Það er eitthvað sem mjög oft er hægt að breyta í þessa tegund af hlutur þar setja þá breytu í þetta - eða, ja, er þetta satt? Þá er þetta, annars þetta. [Námsmaður] Sú fyrsta er ef satt, ekki satt? [Bowden] Já. The vegur ÉG lesa alltaf það er afleysingamanneskja jafngildir verðmæti meiri en gildi afleysingamanneskja, þá er þetta, annars þetta. Það er að spyrja spurningu. Er það meira? Þá gera það fyrsta. Annars gera annað hlutur. Ég næstum alltaf - í ristli, bara ég - í höfðinu á mér, las ég eins og annað. 

Hefur einhver hafa a endurkvæma lausn? Allt í lagi. Þetta sem við erum að fara að - það gæti nú þegar verið mikil, en við erum að fara að gera hana betri jafnvel. Þetta er laglegur mikill the sami nákvæmur hugmynd. Það er bara vel, viltu útskýra? [Nemandi] Jú. Þannig að við erum að tryggja að tréð er ekki núll fyrst því ef tréð er núll þá er að fara að fara aftur rangt vegna þess að við höfum ekki fundið það. Og ef það er enn tré, förum við inn - við athuga fyrst hvort gildið er núverandi hnút. Return satt ef það er, og ef við ekki Kafa til vinstri eða hægri. Hefur þessi hljóð við? >> Mm-Hmm. (Samningurinn) Svo eftir að þetta er næstum - byggingarlega mjög svipuð endurtekningu lausn. Það er bara að í stað þess recursing, við höfðum meðan lykkja. Og stöð raunin hér þar tré ekki jafn null var ástand þar sem við braust út úr while lykkju. Þeir eru mjög svipuð. En við erum að fara að taka þetta einu skrefi lengra. Nú gerum við það sama hér. Takið eftir að við erum að skila sama í báðum þessum línum, nema eitt rifrildi er öðruvísi. Þannig að við erum að fara að gera það í ternary. Ég lenti valkostur eitthvað, og það gerði tákn. Allt í lagi. Þannig að við erum að fara að fara aftur inniheldur það. Þetta er farin að vera margar línur, Jæja, aðdregna í og ​​það er. Venjulega, sem stylistic hlutur, ég held ekki að margir setja pláss eftir ör, en ég held að ef þú ert samkvæmur, það er í lagi. Ef gildið er minna en gildi tré, viljum við að Kafa í vinstri glugganum, annað sem við viljum Kafa hægri tré. Svo var það skref ein að gera þetta líta minni. Skref tvö að gera þetta líta minni - við getum aðskilið þetta margar línur. Allt í lagi. Skref tvö að gera það líta út minni er hér, svo jafngildir skilagildi tré gildi, eða inniheldur hvað sem er. 

Þetta er mikilvægur hlutur. Ég er ekki viss um að ef hann sagði það beinlínis í bekknum, en það er kallað skammhlaup mat. Hugmyndin hér er gildi == tré gildi. Ef það er satt, þá er það satt, og við viljum að "eða" að með hvað sem er hérna. Svo án þess jafnvel að hugsa um hvað er hérna, það er allt tjáning fara að koma aftur? [Nemandi] True? >> Já, því satt um neitt, or'd - eða satt or'd með nokkuð er endilega satt. Svo um leið og við sjáum aftur gildi = tré gildi, við erum bara að fara að fara aftur satt. Ekki einu sinni að fara að Kafa frekari inniheldur niður línu. Við getum tekið þetta skrefinu lengra. Return tré ekki jafn null og allt þetta. Það gerði það einn-lína virka. Þetta er einnig dæmi um stutt-hringrás mat. En nú er það sama hugmynd - stað - þannig að ef tré er ekki jafn null - eða, ja, ef tré er jafn null, sem er slæmt mál, ef tré jafn null, þá fyrsta skilyrðið er að fara að vera falskur. Svo rangar anded við neitt er að fara að vera það? [Nemandi] False. >> Já. Þetta er hinn helmingurinn af skammhlaupi mat, þar sem ef tré er ekki jafn null, þá erum við ekki að fara að jafnvel fara - eða ef tréð er jafnan null, þá erum við ekki að fara að gera gildi == tré gildi. Við erum bara að fara strax aftur ósatt. Sem er mikilvægt, því ef það gerði ekki skammhlaup meta, þá ef tré er jafn null, Þetta annað ástand er að fara að seg kenna, því tré-> gildi er dereferencing null. Svo er það það. Getur þetta - vakt einu sinni yfir. Þetta er mjög algeng hlutur líka, ekki gera þetta eina línu með þetta, en það er sameiginlegur hlutur í aðstæður, kannski ekki hérna, en ef (tré! = NULL, og tré-> gildi == gildi), að gera hvað sem er. Þetta er mjög algengt ástand, þar sem í stað þess að þurfa að brjóta í tvennt IFS, þar sem eins er tréð null? Jæja, það er ekki núll, þannig er nú tré gildi jafnt gildi? Gera þetta. Þess í stað, þetta ástand, þetta mun aldrei seg sök vegna þess að það mun brjótast út ef þetta gerist á að vera núll. Jæja, ég held ef tré er alveg ógilt músina, það geta enn seg kenna, en það er ekki hægt að seg sök ef tré er null. Ef það væri null, myndi það brjótast út áður en þú dereferenced alltaf bendilinn í fyrsta sæti. [Nemandi] þetta er kallað latur mat? 

[Bowden] Lazy mat er sérstakt mál. Lazy mat er meira eins og þú biður um gildi, þú beðið um að reikna út gildi, eins konar, en þú þarft ekki strax. Svo þar sem þú þarft í raun það, það er ekki metið. Þetta er ekki nákvæmlega það sama, en í Huffman pset, það segir að við "lazily" skrifa. Ástæðan sem við gerum sem er vegna þess að við erum í raun verndað skrifa - við viljum ekki að skrifa einstaka bita í einu, eða einstök bæti í einu, viljum við í staðinn að fá klumpur af bæti. Svo þegar við höfum klumpur af bytes, þá munum við skrifa það út. Jafnvel þó að þú biður hann að skrifa - og fwrite og fread gera sömu tegund af hlutur. Þeir biðminni lesa þín og skrifar. Jafnvel þó að þú biður hann um að skrifa strax, það verður sennilega ekki. Og þú getur ekki verið viss um að hlutirnir eru að fara að skrifa þar til þú kalla hfclose eða hvað sem það er, sem síðan segir, allt í lagi, ég er að loka skrá minn, sem þýðir að ég myndi betur skrifa allt sem ég hef ekki skrifað enn. Það hefur ekki þurft að skrifa allt út þar sem þú ert að loka skrá, og þá þarf að. Svo er það bara hvað latur - það bíður þar til það er að gerast. Þetta - að taka 51 og þú munt fara í það nánar, því OCaml og allt í 51, allt er endurkvæmni. Það eru ekki endurtekningu lausnir, í grundvallaratriðum. Allt er endurkvæmni og latur mat er að fara að vera mikilvægt fyrir a einhver fjöldi af aðstæðum þar, ef þú hefur ekki lazily meta, sem myndi þýða - Dæmið er læki, sem eru óendanlega lengi. Í orði, getur þú hugsa um náttúrlegra talna sem straum af 1-2-3-4-5-6-7, Svo lazily mat hlutir eru í lagi. Ef ég segi ég vil tíunda númer, þá get ég meta allt að tíunda fjölda. Ef ég vil hundraðasta númer, þá get ég metið upp á hundraðasta númer. Án latur mat, þá er það að fara að reyna að meta allar tölur strax. Þú ert að meta óendanlega margar tölur, og það er bara ekki hægt. Þannig að það eru fullt af aðstæðum þar latur mat er bara nauðsynlegt til að fá hlutina til að virka. 

Nú viljum við að skrifa Setja sem setja er að fara að vera álíka breytast í skilgreiningu þess. Svo núna er það bool setja (int gildi). Við erum að fara að breyta því til bool setja inn (int gildi, hnútur * tré). Við erum í raun að fara að breyta því aftur í smá, munum við sjá hvers vegna. Og við skulum færa build_node, bara til að Heck það, yfir setja svo við þurfum ekki að skrifa virka frumgerð. Sem er vísbending um að þú ert að fara að nota build_node í insert. Allt í lagi. Taktu eina mínútu fyrir það. Ég held að ég bjargaði endurskoðun ef þú vilt draga úr því, eða, að minnsta kosti, ég gerði núna. Ég vildi smá hlé til að hugsa um rökfræði insert, ef þú getur ekki hugsað um það. Í grundvallaratriðum, verður þú bara alltaf að setja á laufum. Eins, ef ég setja 1, þá er ég óhjákvæmilega að fara að setja 1 - Ég breytt í svart - Ég skal vera að setja 1 hérna. Eða ef ég set inn 4, vil ég að setja 4 hérna. Svo er sama hvað þú gerir, þú ert að fara að setja á laufblaði. Allt sem þú þarft að gera er að iterate niður tré þar til þú fá til the hnút sem ætti að vera foreldri hnúturinn er, foreldri nýju hnút á, og breyta vinstri eða hægri bendilinn þess, eftir því hvort það er meiri en eða minna en núverandi hnút. Breyting sem bendi til að benda á nýja hnút þinn. Svo iterate niður tré, gera blaða benda til nýjan hnút. Einnig hugsa um hvers vegna það bannar tegund af ástandinu áður, þar sem ég smíða tvöfaldur tré þar sem það var rétt Ef þú lítur aðeins á einum hnút, en 9 var vinstra megin við 7 ef þú iterated niður alla leið. Svo það er ómögulegt í þessari atburðarás, þar sem - hugsa um að setja 9 eða eitthvað, á mjög fyrsta hnút, Ég ætla að sjá 7 og ég ætla bara að fara að fara til hægri. Svo það er sama hvað ég geri, ef ég setja með því að fara í blaða, og í blöðum með viðeigandi reiknirit, það er að fara að vera ómögulegt fyrir mig að setja 9 vinstra megin við 7 því um leið og ég lenti 7 Ég ætla að fara til hægri. Hefur einhver hafa eitthvað til að byrja með? [Nemandi] ég. >> Jú. [Námsmaður, óskiljanlegur] [Önnur nemandi, óskiljanlegur] [Bowden] Það er vel þegið. Allt í lagi. Viltu útskýra? 

[Nemandi] Þar sem við vitum að við vorum að setja nýja hnúta í lok af trénu, Ég looped gegnum tré iteratively þangað til ég fékk að hnút sem benti til null. Og þá ákvað ég að setja það annaðhvort á hægri eða vinstri hlið nota þetta rétt breytu, það sagði mér hvar á að setja það. Og þá, í ​​raun, ég gerði bara það síðasta - að hnútur afleysingamanneskja benda á nýja hnút sem það var að búa til, annaðhvort vinstra megin eða hægra megin, allt eftir því hvaða gildi rétt var. Að lokum setti ég nýja hnút gildi gildi rannsóknaraðferðir sínar. [Bowden] Jæja, svo ég sjá eitt atriði hér. Þetta er eins og 95% af the vegur þar. Eina málið sem ég sé vel, hefur einhver annar séð mál? Hvað er aðstæður þar sem þeir brjótast út úr henni? [Nemandi] Ef hitastig er núll? >> Já. Svo hvernig þú brýtur út úr lykkja ef hitastig er null. En hvað á ég að gera hérna? Ég dereference afleysingamanneskja, sem er óhjákvæmilega null. Svo er annar hlutur sem þú þarft að gera ekki bara að halda utan fyrr en hitastig er núll, þú vilt halda utan um foreldri á öllum tímum. Við viljum líka hnút * foreldri, held ég að við getum haldið að við null í fyrstu. Þetta er að fara að hafa skrítinn hegðun í rót af trénu, en við munum komast að því. Ef gildið er stærra en það sem þá afleysingamanneskja = hitastig rétt. En áður en við gerum það, foreldri = afleysingamanneskja. Eða eru foreldrar fara alltaf jafn afleysingamanneskja? Er það málið? Ef hitastig er ekki núll, þá ætla ég að fara niður, það er sama hvað, í hnút sem afleysingamanneskja er foreldri. Svo foreldri er að fara að vera hitastig, og þá skal ég fara afleysingamanneskja niður. Nú er afleysingamanneskja null, en foreldri bendir á foreldri það sem er null. Svo hérna, ég vil ekki að setja rétt er 1. Svo flutti ég til hægri, þannig að ef rétt = 1, og ég giska á að þú vilt einnig að gera - Ef þú flytur til vinstri, þú vilja til setja rétt jöfn 0. Eða annars ef þú færir alltaf til hægri. Svo rétt = 0. Ef hægri = 1, nú viljum við gera foreldri rétt músina newnode, annað sem við viljum gera foreldri vinstri músina newnode. Spurningar um það? Allt í lagi. Svo er þetta eins og við - ja, reyndar, í stað þess að gera þetta, við ráð helmingur að nota build_node. Og þá ef newnode jafngildir null, return false. Það er það. Nú, þetta er það sem við ráð fyrir að þú gerir. 

Þetta er það sem starfsfólk lausnir. Ég er ósammála með þetta sem "rétta" leið til að fara um það en þetta er fullkomlega í lagi og það mun vinna. Eitt sem er svolítið undarlegt núna er ef tré byrjar eins null, fara við í núll tré. Ég giska á það fer eftir því hvernig þú skilgreinir hegðun liggur í núll tré. Ég myndi held að ef það líður yfir í núll tré, þá setja gildi í núll tré ætti bara að fara aftur upp í tré þar sem aðeins gildi að einn hnút. Ekki fólk sammála því? Þú gætir, ef þú vildir, Ef þú fara í núll tré og þú vilt að setja gildi inn í það, aftur rangt. Það er komið að þér að skilgreina það. Til að gera það fyrsta sem ég sagði og þá - Jæja, þú ert að fara að eiga erfitt með að gera það, vegna þess að það væri auðveldara ef við hefðum á heimsvísu bendi til þings, en við ekki, þannig að ef tré er núll, það er ekkert sem við getum gert það. Við getum bara aftur rangar. Þannig að ég ætla að breyta Setja. Við tæknilega gæti bara breyta hérna, hvernig það er iterating yfir hlutum, en ég ætla að breyta setja inn til að taka hnúturinn ** tré. Double ábendingar. Hvað þýðir þetta? Í stað þess að takast á við ábendingum til hnúður, það sem ég ætla að notfæra sé þetta bendi. Ég ætla að hagræða þessu músina. Ég ætla að notfæra ábendingum beint. Þetta er skynsamlegt þar, hugsa um niður - Jæja, núna Þetta bendir til að null. Það sem ég vil gera er að vinna þetta bendi til að benda á að ekki null. Ég vil það að benda á nýja hnút minn. Ef bara halda utan um ábendingar til að ábendingum mínum, svo ég þarf ekki að halda utan um foreldri músina. Ég get bara fylgst með til að sjá hvort bendillinn er að benda að núll, og ef bendillinn er að benda að núll, breyta því að benda á hnútinn sem ég vil. Og ég get breytt því þar sem ég er með músina á músina. Við skulum sjá þetta núna. Þú getur í raun gert það endurkvæmt nokkuð auðveldlega. Viljum við gera það? Já, gerum við. 

Við skulum sjá það endurkvæmt. Fyrst, hvað er undirstaða okkar tilviki að fara að vera? Næstum alltaf stöð mál okkar, en í raun, það er góður af erfiður. Fyrstur hlutur fyrstur, ef (tré == NULL) Ég held að við erum bara að fara að fara aftur ósatt. Þetta er ólíkt tré að vera null. Þetta er bendi á rót músina þína vera null sem þýðir að rót bendillinn þinn er ekki til. Svo hérna, ef ég hnút * - við skulum bara endurnýta þetta. Hnútur * rót = NULL, og þá ætla ég að hringja í Insert með því að gera eitthvað eins og, setja 4 í & rót. Svo og rót, ef rót er hnútur * þá og rót er að fara til vera a hnút **. Þetta gildir. Í þessu tilfelli, tré, allt hér, tré er ekki núll - eða setja. Hér. Tree er ekki núll, * tré er núll, sem er fínt því ef * tré er núll, þá get ég vinna það að nú benda á það sem ég vil það til að benda á. En ef tré er núll, sem þýðir að ég kom bara niður og sagði null. Það er ekki skynsamleg. Ég get ekki gert neitt með það. Ef tré er núll, return false. Svo ég sagði í rauninni þegar það alvöru stöð ef okkar er. Og hvað er að fara að vera? [Námsmaður, óskiljanlegur] [Bowden] Já. Svo ef (* tré == NULL). Þetta varðar málið hérna þar sem ef rautt músina mín er bendillinn ég áherslu á, svo eins og ég áherslu á þetta bendi, nú er ég áherslu á þessa músina. Nú er ég áherslu á þessa músina. Svo ef rautt músina mín, sem er hnút ** mínir er alltaf - ef *, rauður bendillinn minn er alltaf núll, sem þýðir að ég er að ræða þar sem ég er með áherslu á músina sem vísar - þetta er bendillinn sem tilheyrir blöðum. Ég vil breyta þessu bendi til að benda á nýja hnút minn. Komdu hérna. Newnode minn mun bara vera hnút * n = build_node (gildi) þá n, ef n = null, return false. Annars viljum við breyta því sem bendillinn er nú að benda á að að nú benda á nýlega byggð hnút okkar. Við getum í raun gert það hér. Í stað þess að segja n segja við * Tré = ef * tré. Allir skilja það? Að með því að takast á við ábendingum á ábendingum, við getum breytt null ábendingum til að benda á það sem við viljum þá til að benda á. Það er undirstaða okkar tilviki. 

Nú endurkomu okkar eða endurkvæmni okkar, er að fara að vera mjög svipuð öllum öðrum recursions við höfum verið að gera. Við erum að fara til að vilja setja gildi, og nú ætla ég að nota ternary aftur, en það er ástand okkar að fara að vera? Hvað er það sem við erum að leita að til að ákveða hvort við viljum fara til vinstri eða hægri? Við skulum gera það í sérstökum skrefum. Ef (gildi <) hvað? [Nemandi] gildi tréð er? [Bowden] Svo muna að ég er nú - [Nemendur, óskiljanlegur] [Bowden] Já, svo hérna, við skulum segja að þetta græna ör er dæmi um hvað tré eins og er, er bendi á þessa músina. Svo þýðir að ég bendi á músina til 3. The dereference hljómaði tvisvar vel. Hvað geri ég - hvernig geri ég það? [Nemandi] Dereference einu sinni, og þá gera ör þannig? [Bowden] Svo (* tré) er dereference einu sinni, -> gildi er að fara að gefa mér gildi hnút sem ég er óbeint bendir til. Svo ég get líka skrifað það ** tree.value ef þú vilt það. Annaðhvort virkar. Ef sú er raunin, þá vil ég kalla settu með gildi. Og hvað er uppfærð hnút minn ** að fara að vera? Mig langar til að fara til vinstri, svo ** tree.left er að fara að vera vinstri minn. Og ég vil bendilinn að þessi hlutur þannig að ef vinstri endar að vera null músina, Ég get breytt því að benda á nýja hnút minn. 

Og hitt málið getur verið mjög svipuð. Við skulum í raun gera það ternary minn núna. Settu gildi ef gildi <(** tré). Gildi. Þá viljum við að uppfæra ** okkar til vinstri, annað sem við viljum uppfæra ** okkar til hægri. [Nemandi] Er að fá bendi á músina? [Bowden] Mundu að - ** tree.right er hnútur stjarna. [Námsmaður, óskiljanlegur] >> Já. ** Tree.right er svona músina eða eitthvað. Svo með því að taka bendi á það, sem gefur mér það sem ég vil á músina til að strákur. [Nemandi] gætum við farið aftur hvers vegna við erum að nota tvær ábendingar? [Bowden] Já. Svo - Nei, þú getur, og að lausn fyrir var leið til að gera það án þess að gera tvo punkta. Þú þarft að vera fær um að skilja að nota tvær ábendingar, og þetta er hreinni lausn. Einnig, eftir því, hvað gerist ef tré minn - hvað gerist ef rót minn var null? Hvað gerist ef ég geri þetta mál hérna? Svo hnút * rót = NULL, setja 4 í & rót. Hvað er rót að fara að vera eftir þetta? [Námsmaður, óskiljanlegur] >> Já. Root gildi er að fara að vera 4. Rót vinstri er að fara að vera núll, rót rétt er að fara að vera null. Í tilfelli þar sem við vildum ekki fara rót eftir heimilisfangi, við gátum ekki breyta rót. Í tilviki þar sem tré - sem rót var null, við þurftum bara að skila falskur. Það er ekkert sem við gætum gert. Við getum ekki sett í hnút í tómt tré. En nú getum við, við tökum bara tómt tré í einn hnút tré. Sem er yfirleitt áætlað þannig að það er ætlast til að vinna. 

Jafnframt er verulega styttri en einnig að halda utan um foreldri, og svo þú iterate niður alla leið. Nú hef ég foreldri mitt, og ég hef bara foreldri rétt músina mína til hvað sem er. Staðinn, ef við gerðum þetta iteratively, myndi það vera sama hugmyndin með while lykkju. En í stað þess að þurfa að takast á við músina foreldra mína, stað núverandi bendill minn væri hlutur sem ég er beint að breyta til að benda á nýja hnút minn. Ég þarf ekki að takast á við hvort sem það er að benda til vinstri. Ég þarf ekki að takast á við hvort sem það er að benda til hægri. Það er bara hvað þetta bendillinn er, ég ætla að setja það til að benda á nýja hnút minn. Allir skilja hvernig það virkar? Ef ekki hvers vegna viljum við gera það með þessum hætti, en að minnsta kosti að þetta virkar sem lausn? [Nemandi] Hvar aftur við satt? [Bowden] Það er líklega hérna. Ef við setja rétt það aftur að veruleika. Annars, hérna erum við að fara að vilja til að fara aftur hvað sem setja inn aftur. 

Og hvað er sérstakt við þennan endurkvæma virka? Það er hali endurkvæma, svo lengi sem við safna saman með einhverjum hagræðingu, það mun viðurkenna það og þú munt aldrei fá stafla flæða frá þessu, jafnvel ef tré okkar hefur hæð um 10.000 eða 10 milljónir króna. [Námsmaður, óskiljanlegur] [Bowden] Ég held að það gerir það í Dash - eða hvað hagræðing stigi þarf fyrir hali endurkvæmni að vera viðurkennd. Ég held að það viðurkennir - GCC og Clang einnig hafa mismunandi merkingu fyrir stigum hagræðingu þeirra. Mig langar að segja að það er DashO 2, fyrir víst að það mun viðurkenna hali endurkvæmni. En við - þú gætir byggja eins Fibonocci dæmi eða eitthvað. Það er ekki auðvelt að prófa þetta, því það er erfitt að reisa tvöfaldur tré sem er svo stór. En já, ég held að það DashO 2, sem Ef þú saman við DashO 2, mun það leita endurkvæmni hali og bjartsýni það út. Förum aftur til - setja er bókstaflega síðasta sem það þarf. Við skulum fara aftur til innskotsins hérna þar sem við erum að fara að gera sömu hugmynd. Það verður samt að hafa galli að geta ekki alveg séð þegar rót sjálft er núll, eða síðasta færsla er núll, en í stað þess að takast á við foreldra bendi, við skulum nota sömu rökfræði halda ábendingum á ábendingum. Ef hér við halda hnút okkar ** nú, og við þurfum ekki að halda utan um rétt lengur, en hnútur ** nú = & tré. Og nú meðan lykkja okkar er að fara að vera á meðan * nú ekki jafn null. Ekki þarf að halda utan um foreldra lengur. Ekki þarf að halda utan um vinstri og hægri. Og ég kalla það afleysingamanneskja, vegna þess að við erum nú þegar að nota afleysingamanneskja. Allt í lagi. Svo ef (gildi> * Temp) þá & (* afleysingamanneskja) -> hægri annars Temp = & (* afleysingamanneskja) -> vinstri. Og nú, á þessum tímapunkti, eftir þessa while lykkju, Ég geri bara þetta vegna þess að kannski er auðveldara að hugsa um iteratively en endurkvæmt, en eftir þessa while lykkju, * Hitastig er bendillinn við viljum breyta. 

Áður en við höfðum foreldri, og við vildum að breyta annað hvort foreldri vinstri eða foreldri rétt, en ef við viljum breyta foreldri rétt, þá er * afleysingamanneskja foreldri rétt, og við getum breytt því beint. Svo hérna getum við gert * afleysingamanneskja = newnode, og það er það. Svo fyrirvara, allt sem við gerðum í þessu var að taka út línur af kóða. Til þess að halda utan um foreldri í allt sem er til viðbótar átaki. Hér, ef við höldum bara utan um músina á músina, og jafnvel ef við vildum fá losa af öllum þessum hrokkið axlabönd nú, gera það líta styttri. Þetta er nú það nákvæmlega sama lausnin, en færri línur af kóða. Þegar þú byrjar að viðurkenna þetta sem gild lausn, það er líka auðveldara að ástæðu um en eins og, allt í lagi, af hverju hef ég þessa fána á int rétt? Hvað þýðir það? Oh, það er merkir að í hvert skipti sem ég fer til hægri, þarf ég að setja það, annars ef ég fer eftir sem ég þarf að setja það á núll. Hér hef ég ekki að ástæða um það, það er bara auðveldara að hugsa um. Spurningar? [Námsmaður, óskiljanlegur] >> Já. Jæja, svo í síðasta hluti - Ég giska á einn fljótleg og auðveld aðgerð sem við getum gert er, let's - saman, ég giska á, að reyna að skrifa inniheldur virka sem er ekki sama hvort það er tvöfaldur leita tré. Þetta inniheldur virka ætti að skila satt Ef einhvers staðar í þessu almenna tvöfaldur tré er gildi sem við erum að leita að. Svo skulum fyrst gera það endurkvæmt og þá munum við gera það iteratively. Við getum í raun bara að gera það saman, vegna þess að þetta er að fara að vera mjög stutt. 

Hvað er undirstaða mál mitt að fara að vera? [Námsmaður, óskiljanlegur] [Bowden] Þannig að ef (tré == NULL), hvað þá? [Nemandi] return false. [Bowden] Annars, vel, ég þarf ekki annað. Ef væri önnur stöð mál mitt. [Námsmaður] tré gildi? >> Já. Svo ef (tré-> gildi == gildi. Takið eftir að við erum aftur í hnút *, ekki hnút ** s? Contains mun aldrei þurfa að nota hnút **, þar sem við erum ekki að breyta ábendingum. Við erum bara að fara yfir þá. Ef það gerist, þá viljum við að aftur satt. Annars viljum við fara yfir börnunum. Þannig að við getum ekki rökrætt um það hvort allt til vinstri er minna og allt til hægri er meiri. Svo er það skilyrði okkar að fara að vera hér - eða, hvað ætlum við að gera? [Námsmaður, óskiljanlegur] >> Já. Return inniheldur (gildi, tré-> vinstri) eða inniheldur (gildi, tré-> hægri). Og það er það. Og eftir því að það er einhver skammhlaup mat, þar sem ef við gerast til að finna gildi í vinstri glugganum, Við þurfum aldrei að líta á réttum tré. Það er allt virka. Nú skulum gera það iteratively, sem er að fara að vera minna gaman. Við tökum venjulega upphaf hnút * gjald = tré. Meðan (nú! = NULL). Fljótt að fara að sjá vandann. Ef nú - hér, ef við brjóta alltaf út af þessu, þá höfum við keyrt út af hlutum til að líta á, svo aftur rangt. Ef (nú-> gildi == gildi), aftur við. Svo nú erum við á stað - við vitum ekki hvort við viljum fara til vinstri eða hægri. Svo geðþótta, við skulum bara fara til vinstri. Ég hef greinilega keyrt inn í mál þar sem ég hef alveg yfirgefin allt - Ég mun bara alltaf stöðva á vinstri hlið af tré. Ég mun aldrei athuga eitthvað sem er rétt barn neitt. Hvernig laga ég þetta? [Nemandi] Þú þarft að halda utan um vinstri og hægri í stafla. [Bowden] Já. Svo skulum gera það struct lista, hnút * N, og þá hnút ** næst? Ég held að það virkar fínt. Við viljum fara yfir til vinstri, eða let's - upp hér. Struct lista lista =, verður það að byrja út á þessu strúktúrinn lista. * List = NULL. Svo er að fara að vera tengd lista okkar á subtrees sem við höfum sleppt yfir. Við ætlum að fara yfir til vinstri nú, en þar sem við þurfum óhjákvæmilega að koma aftur til hægri, Við ætlum að halda hægra megin inni í lista strúktúrinn okkar. Síðan munum við hafa new_list eða strúktúr, struct lista *, new_list = malloc (sizeof (listi)). Ég ætla að hunsa villa-stöðva það, en þú ættir að athuga að sjá null ef það er. New_list hnúturinn það er að fara að benda á - ó, það er ástæða þess að ég vildi það upp hér. Það er að fara að benda á annan strúktúrinn lista. Það er bara hvernig tengist listum vinna. Þetta er það sama sem int tengd lista nema að við erum bara að skipta int með hnút *. Það er nákvæmlega það sama. Svo new_list, verðmæti hnút new_list okkar, er að fara að vera nú-> hægri. Verðmæti okkar new_list-> Næsta er að fara að vera frumleg lista okkar, og þá ætlum við að uppfæra lista okkar til að benda á new_list. 

Nú þurfum við einhverskonar leið draga hluti, eins og við höfum traversed allt vinstri subtree. Nú þurfum við að draga efni út af því, eins og nú er núll, við viljum ekki bara aftur ósatt. Við viljum nú draga út á nýja listann okkar. A þægilegri leið til að gera þetta - ja, reyndar, það er margar leiðir til að gera þetta. Einhver með uppástungu? Þar sem ég ætti að gera þetta eða hvernig ég ætti að gera þetta? Við höfum aðeins nokkrar mínútur, en einhverjar uppástungur? Í stað þess - ein leið, í stað þess að ástand okkar að vera á meðan, það sem við erum nú að leita að er ekki núll, stað þess að við erum að fara að halda áfram að fara fram lista okkar sjálft er null. Svo ef lista okkar endar að vera núll, þá höfum við keyrt út af hlutum til að leita að, til að leita á. En það þýðir að það fyrsta sem á listanum okkar er bara að fara til vera the fyrstur hnút. The mjög fyrstur hlutur verður - við þurfum ekki lengur að sjá það. Svo lista-> N verður tré okkar. lista-> Næsta er að fara að vera null. Og nú þegar er ekki jafn null. Nú er að fara að draga eitthvað úr listanum okkar. Svo nú er að fara að jafna lista-> N. Og þá er að fara að jafna lista-> N, eða lista-> Næsta. Þannig jafngildir ef nú gildi gildi. Nú getum við bætt jafnt hægri músina og vinstri bendilinn okkar svo lengi sem þeir eru ekki null. Hérna, ég held við ættum að hafa gert það í fyrsta sæti. Ef (nú-> hægri! = NULL) þá erum við að fara að setja þessi hnút í listanum okkar. Ef (nú-> vinstri), þetta er a lítill hluti af auka vinnu, en það er allt í lagi. Ef (nú-> vinstri! = NULL), og við erum að fara að setja vinstri í tengda listanum okkar, og það ætti að vera það. Við iterate - svo lengi sem við höfum eitthvað á listanum okkar, við höfum annan hnút til að líta á. Svo við lítum á þeim hnút, við fram lista okkar til the næstur einn. Ef þessi hnútur er gildi sem við erum að leita að, getum við aftur satt. Annars setja bæði okkar vinstri og hægri subtrees, svo lengi sem þeir eru ekki null, í listanum okkar þannig að við förum óhjákvæmilega yfir þeim. Svo ef þeir voru ekki null, Ef rót músina okkar benti á tvennt, þá fyrst við tókum eitthvað út svo listinn okkar endar að vera null. Og þá erum við að setja tvo hluti aftur í, svo nú er listi okkar stærð 2. Þá ætlum við að lykkja aftur upp og við erum bara að fara að draga, segjum, vinstri músina yfir hnút rót okkar. Og það verður bara að halda að gerast, við munum á endanum lykkja yfir öllu. 

Takið eftir að þetta var verulega flóknara í endurkvæma lausn. Og ég hef sagt mörgum sinnum að endurkvæma lausn hefur yfirleitt margt sameiginlegt með endurtekningu lausn. Hér er þetta nákvæmlega það sem endurkvæma lausn er að gera. Eina breytingin er að í stað þess óbeint með á mánudaginn, forritið mánudaginn, sem leið að halda utan um hvaða hnúður sem þú þarft samt að fara, nú þú þarft að sérstaklega nota tengda listanum. Í báðum tilvikum eru að halda utan um hvaða hnút enn þarf að vera heimsótt. Í endurkvæma tilviki það er bara auðveldara vegna þess að stafla er sett fyrir þig eins og the program stakkur. Takið eftir að þetta tengist lista, það er stakkur. Whatever við settum bara á mánudaginn er strax það sem við erum að fara að rífa af stafla í heimsókn næst. Við erum út af tími, en einhverjar spurningar? [Námsmaður, óskiljanlegur] [Bowden] Já. Svo ef við höfum tengt lista okkar, nú er að fara að benda á þetta strákur, og nú erum við bara að fara tengda listanum okkar til að einblína á þetta gaur. Við erum að fara yfir á tengda lista í þeirri línu. Og svo ég held að við ættum að losa tengda listanum okkar og efni einu sinni en aftur satt eða ósatt, þurfum við að iterate yfir tengda listanum okkar og alltaf hérna, held ég, ef við nú rétt er ekki jöfn, bæta við það, svo nú viljum við að losa nú vegna þess að vel var við gleymum alveg um listann? Já. Svo það er það sem við viljum gera hér. Hvar er bendillinn? Nú var þá - við viljum að strúktúrinn lista * 10 jafngildir lista næst. Free listi, listi = Temp. Og í þeim tilvikum þegar við aftur satt, þurfum við að iterate yfir afganginn af tengda listanum okkar fría hluti. The ágætur hlutur óður í the endurkvæma lausn er frjáls hluti þýðir bara pabbi factorings burt stafla sem mun gerast fyrir þig. Þannig að við höfum farið frá einhverju sem er eins og 3 línur af harður-til-hugsa-um kóða eitthvað sem er verulega margir fleiri harður-til-hugsa-um línum af kóða. Allir fleiri spurningar? Allt í lagi. Við erum góð. Bless! [CS50.TV]