[Powered by Google Translate] [Časť 7: Ďalšie Komfortné] [Rob Bowden] [Harvard University] [To je CS50] [CS50.TV] Dobrá. Tak ako som povedal vo svojom e-mailu, to bude binárny strom náročný úsek. Ale tam nie je, že mnoho otázok. Takže budeme sa snažiť a čerpať z každej otázky a ísť do bolestné detailu všetkých najlepších spôsobov, ako robiť veci. Takže hneď na začiatku, sme sa prejsť vzorky kresieb binárnych stromov a podobne. Tak tu, "Pamätaj si, že binárny strom má uzly podobné tým prepojeného zoznamu, okrem namiesto jedného ukazovatele sú dva: jeden pre ľavé "dieťa" a jeden pre pravé "dieťa". " Takže binárny strom je rovnako ako prepojeného zoznamu, okrem struct bude mať dva ukazovatele. Tam je trinary stromy, ktoré sa chystajú tri ukazovatele, tam sú n-árne stromy, ktoré práve majú všeobecný ukazovateľ , Ktoré potom musia malloc byť dostatočne veľké, aby sa dosť ukazovatele na všetkých možných detí. Takže binárne strom len sa stane, že konštantné množstvo dvoch. Ak chcete, môžete si dať prepojeného zoznamu ako unární strom, ale ja si nemyslím, že niekto volá, že. "Nakreslite boxy-a-arrows diagram binárneho stromu uzol obsahujúce Nate obľúbené číslo, 7, kde každé dieťa ukazovateľ je null. " Takže iPad režimu. 

Bude to byť celkom jednoduché. Sme jednoducho bude mať uzol, budem kresliť ako štvorec. A ja budem čerpať hodnoty tu. Takže hodnota pôjde sem, a potom tu dole budeme mať ľavej ukazovateľ vľavo a vpravo ukazovateľ vpravo. A to je veľmi, takže je zvykom nazývať ľavý a pravý, ukazovateľ mená. Obaja títo budú mať hodnotu null. To bude len null, a že bude len null. Dobre. Takže späť sem. "S prepojeného zoznamu, sme mali iba na uloženie ukazovatele na prvom uzla v zozname za účelom pamätať celý spájať zoznam alebo celý zoznam. Rovnako tak, sa stromy, máme iba na uloženie ukazovatele na jednom uzle, aby sa pamätať celý strom. Tento uzol je calle ďalej len "koreň" stromu. Stavať na diagrame z obdobia pred alebo nakresliť nový tak, že máte boxy-a-arrows znázornenie binárneho stromu s hodnotu 7, potom 3 v ľavej, potom 9 na pravej strane, a potom 6 na pravej strane 3 ". Uvidíme, či si pamätám všetko v mojej hlave. Tak to bude naša koreň tu. Dáme si ukazovateľ niekde, niečo, čo budeme volať koreň, a to ukazuje na toho chlapa. Teraz sa vytvoriť nový uzol, čo máme, 3 vľavo? Takže nový uzol s 3, a to na začiatku ukazuje nulový. Ja si len dať N. Teraz chceme, aby sa to ísť vľavo 7. Tak sme zmeniť tento ukazovateľ teraz ukazujú na toho chlapa. A my to isté. Chceme 9 nad tu ktorý spočiatku len hovorí, null. Budeme meniť tento ukazovateľ, prejdite na 9, a teraz chceme dať 6 na pravej strane 3. Takže to bude - urobiť 6. A ten chlap bude smerovať tam. Dobre. Tak to je všetko, čo je od nás žiada robiť. 

Teraz poďme cez niektoré pojmy. Už sme hovorili o tom, ako koreň stromu je na najvyššej uzol v strome. Z ktorých jedna obsahuje 7. Uzly v dolnej časti stromu sa nazývajú listy. Každý uzol, ktorý má jednoducho null ako jeho deti, je list. Je teda možné, ak náš binárny strom je len jeden uzol, že strom je list, a to je všetko. "The" Výška "stromu je počet chmeľu je nutné vykonať sa dostať z vrcholu do listu. " Dostaneme do, v druhej, na rozdiel medzi symetrické a nesymetrické binárnych stromov, ale teraz, celková výška tohto stromu Povedal by som, že je 3, ale ak budete počítať množstvo chmeľu je nutné vykonať tak, aby sa dostať do 9, potom je to naozaj len výška 2. Práve teraz je to nevyvážený binárny strom, ale budeme hovorili o vyvážené, keď sa dostane za relevantné. Takže teraz môžeme hovoriť o uzlov na strome, pokiaľ ide vo vzťahu k ostatným uzlov stromu. Takže teraz máme rodičia, deti, súrodenci, predkov a potomkovia. Oni sú celkom zdravý rozum, čo to znamená. Pýtame Ak sa - je to rodičia. Takže to, čo je nadradený 3? [Študenti] 7. Jo >>. Rodič len bude, čo poukazuje na tebe. Tak čo, sú deti 7? [Študenti] 3 a 9. Jo >>. Všimnite si, že "deti" doslova znamená deti, tak 6 sa nepoužijú, pretože je to ako vnúča. Ale potom, keď pôjdeme potomkov, takže aké sú potomkovia 7? [Študenti] 3, 6 a 9. Jo >>. Potomkovia koreňa bude všetko v stromu, snáď s výnimkou koreňový uzol sám, ak nechcete, aby zvážila, že potomok. A konečne, predkovia, tak je to v opačnom smere. Takže aké sú predkami 6? [Študenti] 3 a 7. Jo >>. 9 nie je zahrnutá. Je to len priame línie späť do koreňového adresára bude vaši predkovia. 

"Povieme, že binárny strom je" prikázal ", ak pre každý uzol v strome, všetky jeho potomkov na ľavej strane majú menšie hodnoty a všetky tie, na pravej strane sú väčšie hodnoty. Napríklad, je strom nad objednal, ale nie je to len možné objednať usporiadanie. " Než sa dostaneme k tomu, objednal binárne strom je tiež známy ako binárny vyhľadávací strom. Tu sa stalo, že sa nazývať to objednané binárne strom, ale nikdy som nepočul, že len objednať binárny strom pred, a na kvíz sme oveľa častejšie, aby strom binárneho vyhľadávania. Sú jedna a tá istá, a to je dôležité, spoznáte rozdiel medzi binárnym stromom a binárne vyhľadávacie strom. Binárne strom je len strom, ktorý ukazuje na dve veci. Každý uzol poukazuje na dve veci. Neexistuje žiadny úvaha o hodnotách, ktoré sa ukazuje na. Tak ako tu, pretože je to binárny vyhľadávací strom, vieme, že keď ideme vľavo 7, potom všetky hodnoty, ktoré môžeme prípadne dosiahnuť tým, že ide vľavo 7 musí byť menší ako 7. Všimnite si, že všetky hodnoty menšie ako 7 sú 3 a 6. Tí sú na ľavej strane 7. Ak pôjdeme na pravej strane 7, všetko musí byť väčšia ako 7, takže 9 je na pravej strane 7, takže sme v pohode. Toto nie je prípad binárneho stromu, pre pravidelné binárneho stromu môžeme len majú 3 v hornej, 7 na ľavej strane, 9 na ľavej strane 7, nie je objednanie hodnôt vôbec. Teraz, nebudeme vlastne robiť, pretože je to nudné a zbytočné, ale "skúsiť nakresliť toľko objednaný stromov, ako si môžete myslieť pomocou čísla 7, 3, 9, a 6. Koľko odlišné usporiadanie sú tam? Aká je výška každej z nich? " 

Urobíme pár, ale hlavná myšlienka je, To je v žiadnom prípade jedinečné znázornenie binárneho stromu, ktorý obsahuje tieto hodnoty. Všetko čo potrebujeme, je nejaký binárny strom, ktorý obsahuje 7, 3, 6 a 9. Ďalším možným platná jeden by koreň je 3, prejsť na ľavej strane a je to 6, prejsť na ľavej strane a je to 7, ísť doľava a je to 9. To je úplne platný binárny vyhľadávací strom. Nie je to veľmi užitočné, pretože je to rovnako ako prepojeného zoznamu a všetky tieto ukazovatele sú len nulový. Ale je to platný strom. Jo? [Študent] Nie hodnoty musia byť väčšie na pravej strane? Alebo je to -? >> Tie som chcel ísť inou cestou. K dispozícii je tiež - jo, poďme prejsť to. 9, 7, 6, 3. Dobrý úlovok. To ešte musí počúvať, čo binárny strom vyhľadávania robiť. Takže všetko na ľavej strane musí byť menšia ako daný uzol. Mohli by sme len presunúť, povedzme, táto 6 a dať sem. Nie, nemôžeme. Prečo som to robiť, že? Poďme urobiť - tu je 6, tu je 7, 6 bodov na 3. To je stále platný binárny vyhľadávací strom. Čo je zle, keď si - uvidíme, či môžem prísť s usporiadaním. Jo, dobre. Takže to, čo je zle s týmto stromom? Myslím, že som už dal náznak, že je niečo v neporiadku s ňou. Prečo som to robiť, že? Dobre. To vyzerá rozumne. Ak sa pozrieme na každom uzle, ako je 7, potom na ľavej strane 7 je 3. Takže máme 3, vec vpravo 3 je 6. A keď sa pozriete na 6, vec vpravo 6 je 9. Tak prečo je to nie je platný binárny vyhľadávací strom? [Študenti] 9, je stále na ľavej strane 7. Jo >>. Musí to byť pravda, že všetky hodnoty, ktoré môžete prípadne dosiahnuť tým, že pôjdete na ľavej strane 7 árov menej ako 7. Ak pôjdeme vľavo 7, dostaneme sa 3 a stále môžeme dostať do 6, môžeme ešte dostať do 9, ale tým, že má preč menej ako 7, by sme však byť schopný sa dostať na číslo, ktoré je väčšie ako 7. Takže to nie je platný binárny vyhľadávací strom. 

Môj brat vlastne mal rozhovor otázku to bolo v podstate to, len kód do niečoho na overenie či strom je binárny vyhľadávací strom, a tak prvá vec, ktorú urobil, bolo, len skontrolovať, ak vľavo a vpravo sú správne, a potom určiť iteráciou tam. Ale nemôžeš len to, že, budete mať neustále prehľad na skutočnosť, že teraz, keď som preč odišiel zo 7., všetko v tomto podstrome musí byť menší ako 7. Správna algoritmus potrebuje sledovať z medzí, ktoré je možné hodnoty možná spadajú dovnútra Nebudeme prejsť všetky z nich. K dispozícii je pekná opakovanie vzťah, aj keď sme sa dostali k tým, inak nebudeme sa k tým, definovanie, koľko ich vlastne je. Takže tam je 14 z nich. Myšlienka na to, ako by to matematicky je ako, si môžete vybrať jeden ľubovoľný jedného byť koreňový uzol, a potom, keď vybrať 7 byť koreňový uzol, potom tam sú, povedzme, niektoré čísla, ktoré môžu ísť byť mojej ľavici uzol, a tam sú niektoré čísla, ktoré môžu byť moja pravá uzol, ale ak som n celkové počty, potom sa suma, ktorá môže ísť vľavo plus suma, ktorá môže ísť vpravo je n - 1. Takže zo zostávajúcich čísel, musí byť schopný ísť buď doľava alebo doprava. Zdá sa, že ťažké, keď som dal 3 prvej potom všetko musí ísť doľava, ale keď som dal 7, potom niektoré veci môže ísť vľavo a niektoré veci môžu ísť na práva. A '3 prvý "Myslel som všetko môže ísť doprava. Je to naozaj, stačí premýšľať o tom, ako, koľko vecí môže ísť na ďalšiu úroveň stromu. A to je sa, že je 14, alebo sa môže čerpať všetky z nich, a potom dostanete 14. 

Vráťme sa späť sem, "Objednaný binárne stromy sú skvelé, pretože môžeme hľadať v nich veľmi podobne ako vyhľadávanie cez triedenom poli. Ak chcete tak urobiť, začneme pri koreni a prácu si cestu dole stromu smerom listov, kontrola každý uzol v hodnoty na hodnoty, ktoré sme hľadáte. Ak je aktuálna uzol je hodnota nižšia ako hodnota, ktorú hľadáme, idete vedľa uzla pravej dieťa. V opačnom prípade, pôjdete do uzla na ľavej dieťa. V určitom bode, budete buď nájsť hodnotu, ktorú hľadáte, alebo budete spúšťať do null, označujúce hodnotu nie je v strome. " Mám k prekreslenie stromu sme mali predtým, že bude trvať sekundu. Ale chceme sa pozrieť do, či 6, 10, a 1 sú v strome. Takže, čo to bolo, 7, 9, 3, 6. Dobre. Čísla chcete vyhľadať, chceme pozrieť do 6. Ako sa tento algoritmus funguje? No, máme aj nejaké koreňový ukazovateľ na náš strom. A mali by sme ísť ku koreňu a povedať, je táto hodnota rovná hodnote my hľadáme? Takže sme hľadali 6, takže to nie je rovnaké. Tak sme ďalej, a teraz hovoríme, áno, takže 6 je menší ako 7. Znamená to, že chceme ísť doľava, alebo chceme ísť doprava? [Študent] Left. Jo >>. Je to výrazne jednoduchšie, všetko, čo musíte urobiť, je nakresliť jeden možný uzol stromu a potom nie - namiesto toho sa snaží myslieť v hlave, v poriadku, ak je to menej, mám ísť doľava alebo ísť právo, Len pri pohľade na tento obrázok, je to veľmi jasné, že musím ísť doľava v prípade, že uzol je väčšia ako hodnota, že som hľadal. Takže idete doľava, teraz som na 3. Chcem - 3, je menšia, než je hodnota Hľadám, čo je o 6. Takže ideme vpravo, a teraz som skončil na 6, čo je hodnota Hľadám, tak som sa vrátiť true. Ďalšie hodnota budem hľadať je 10. Dobre. Takže 10, teraz sa chystá - odrezať, že - bude nasledovať koreň. Teraz, 10 bude väčší ako 7, tak sa chcem pozrieť na pravej strane. Chystám sa ísť sem, 10 bude väčší ako 9, takže budem chcieť pozrieť na pravej strane. Prišiel som sem, ale sem teraz som na null. Čo mám robiť, keď som narazila null? [Študent] Návrat false? Jo >>. Nenašiel som 10. 1 sa bude takmer totožný prípad, okrem toho, že to jednoducho bude prevrátený, namiesto hľadania dole na pravej strane, idem sa pozrieť dolu na ľavej strane. 

Myslím, že teraz sme vlastne dostať ku kódu. Tu je miesto, kde - otvoriť CS50 spotrebič a navigáciu si cestu tam, ale môžete tiež len to je v priestore. Je to asi ideálne, aby to v priestore, pretože môžu pracovať v priestore. "Najprv budeme potrebovať novú definíciu typu pre binárne uzol stromu obsahuje int hodnoty. Použitie dosku spotrebiče typedef nižšie, vytvoriť novú definíciu typu pre uzol v binárnom stromu. Ak narazíte. . . "Bla, bla, bla. Dobre. Takže poďme dať dosku spotrebiče tu, typedef struct uzol, a uzol. Jo, dobre. Takže aké sú polia budeme chcieť v našej uzla? [Študent] Int a potom dva ukazovatele? >> Int hodnota, dva ukazovatele? Ako písať ukazovateľov? [Študent] Struct. >> Mal by som priblížiť dovnútra Jo, tak struct uzol * vľavo, a struct uzol * P. A pamätajte diskusiu od minule, že toto nemá zmysel, to nedáva zmysel, To nedáva zmysel. Musíte všetko, čo sa s cieľom definovať túto rekurzívne struct. Dobre, tak to je to, čo náš strom bude vyzerať. Ak by sme urobili trinary strom, potom uzol môže vyzerať ako b1, b2, struct uzol * b3, kde b je vetva - vlastne, ja som počul, že viac vľavo, stredný, pravý, ale čo. My len o binárny, tak doprava, doľava. "Teraz vyhlásiť globálne uzol * premenné pre koreň stromu." Takže my nebudeme robiť, že. Aby sa veci trochu ťažšie a všeobecnejšie, nebudeme mať globálny uzla premennú. Namiesto toho, v hlavnej budeme deklarovať všetky naše uzla veci, a to znamená, že pod, keď sme rozbehnú naše obsahuje funkcie a náš vložka funkcie, miesto našich obsahuje funkcie len s použitím tohto globálneho uzla premennú, budeme mať trvať ako argument na strom, ktorý chceme, aby to spracovať. S globálne premennú mal robiť veci lepšie. Budeme robiť veci ťažšie. Teraz trvať minútu alebo tak, aby jednoducho takéto veci, kde vo vnútri hlavnej chcete vytvoriť tento strom, a to je všetko, čo chcete robiť. Skúste a postaviť sa k tomuto stromu v hlavnej funkcii. 

Dobre. Takže si ani nemusíte mať postavil strom celú cestu ešte. Ale niekto niečo, čo by som mohol vytiahnuť hore ukázať, ako by sa dalo začať budovať taký strom? [Študent] Niekto búchať, snaží sa dostať von. [Bowden] Každý, kto vyhovuje ich stromu konštrukcia? [Študent] Jasne. Je to neurobil. >> To je v poriadku. Môžeme len dokončiť - oh, môžete si ju uložiť? Hurá. Takže tu máme - oh, som mierne orezané. Som priblíženie? Zväčšenie, prejdite von. >> Mám dotaz. Jo >>? [Študent] Pri definovaní struct, sú veci ako inicializovaná na niečo? [Bowden] No >> Dobre. Takže budete musieť inicializovať - [Bowden] No Pri definovaní, alebo pri deklarovaní struct, nie je inicializovaný v predvolenom nastavení, je to ako keď deklarovať int. Je to presne to isté. Je to ako každý z jednotlivých jeho oblastiach môže mať na odpadky hodnotu v ňom. >> A je možné definovať - ​​alebo vyhlásiť struct spôsobom, aby pri jej inicializovať? [Bowden] Áno. Takže, skratka inicializácia syntaxe bude vyzerať - Existujú dva spôsoby, ako to urobiť môžeme. Myslím, že by sme mali skompilovať aby sa ubezpečil, zvonenie tiež to robí. Poradie argumentov, ktoré prichádza v struct, dáte ako poradie argumentov vnútri týchto zložených zátvoriek. Takže ak chcete inicializovať ju 9 a odišiel sa null a potom doprava bude null, , Že by bolo 9, null, null. Alternatívou je, a editor nemá rád túto syntax, a to si myslí, že chcem nový blok, ale alternatívou je niečo ako - tu, dám to na nový riadok. Môžete výslovne povedať, že som zabudol presnú syntax. Takže môžete explicitne riešiť podľa názvu, a hovoria, . C, alebo. Hodnota = 9,. Left = NULL. Hádam, že je potrebné tieto pravidlá čiarky. . Doprava = NULL, takže tento spôsob nemáte skutočne potrebujú poznať poradí struct, a keď toto čítate, je to oveľa jednoznačnejšie, o tom, čo je hodnota je inicializovaná. 

To sa stane, že je jedna z vecí, ktoré - tak, pre najviac sa rozdeliť, C + +, je nadmnožinou C. Môžete si vziať kód v C, presuňte ju do C + +, a to by malo zostaviť. To je jedna z vecí, ktoré C + + nepodporuje, takže ľudia nemajú tendenciu robiť. Ja neviem, či to je jediný dôvod, prečo ľudia nemajú tendenciu robiť to, ale prípad, kedy som potreboval použiť napríklad pre prácu s C + +, a tak som nemohol použiť. Ďalším príkladom niečoho, čo nefunguje s C + +, je ako malloc vracia "void *," technicky, ale vy ste mohli len povedať, char * x = malloc čokoľvek, a to bude automaticky přetypovat na char *. To automatické obsadenie nestáva v C + +. To by nebolo skompilovať, a vy by ste explicitne potreba povedať char *, malloc, čokoľvek, aby vrci char *. Nie je veľa vecí, ktoré C a C + + nezhodnú na, ale tie sú dva. Takže pôjdeme s touto syntaxou. Ale aj keď sme nešli s tým syntaxou, to, čo je - by mohlo byť zle s tým? [Študent] Ja nemusíte dereferencia to? Jo >>. Pamätajte si, že šípka má implicitné dereferencia, a tak, keď sme len do činenia s struct, chceme použiť. aby sa na pole vnútri struct. A len čas používame šípku je, keď chceme urobiť - no, šípka je ekvivalentná - že to, čo by to znamenalo, keby som šíp. Všetky arrow prostriedok je, dereferencia to, teraz som na struct, a môžem pole. Buď si pole priamo, alebo dereferencia a získať pole - Myslím, že by to malo byť hodnota. Ale tu sa zaoberám len struct, nie ukazovateľ na struct, a tak nemôžem použiť šípku. Ale tieto veci môžeme urobiť pre všetky uzly. Ach môj bože. To je 6, 7, a 3. Potom môžeme nastaviť pobočky v náš strom, môžeme mať 7 - môžeme mať, že by sa jeho ľavá ukazovať na 3. Tak ako to urobíme? [Študenti, nezrozumiteľné] >> Jo. Sídlo node3, a ak ste nemali adresu, potom to jednoducho nebude zostavovať. Ale nezabudnite, že sa jedná o ukazovatele na najbližších uzlov. Pravé smerové 9, a 3 by mali ukazovať o práve na 6. Myslím, že to je všetko nastavené. Akékoľvek pripomienky či otázky? [Študent, nezrozumiteľné] Koreň bude 7. Môžeme len povedať, uzol * ptr = alebo koreň, = & node7. 

Pre naše účely, budeme rokovať s vložkou, takže budeme chcieť napísať funkciu vložiť do tohto binárneho stromu a vložka je nevyhnutne bude volať malloc vytvoriť nový uzol pre tohto stromu. Tak sa veci dostať chaotický s tým, že niektoré uzly sú v súčasnej dobe vo fronte a ostatné uzly sú skončíme na halde, keď vložíme ich. To je úplne v poriadku, ale iba dôvod sme schopní to urobiť na zásobníku Je tomu tak preto, že je to taká sprisahanecké príklad, že vieme, strom má byť konštruované ako 7, 3, 6, 9. Ak by sme nemali, potom by sme nemali malloc na prvom mieste. Ako uvidíme o niečo neskôr, mali by sme byť malloc'ing. Práve teraz je to úplne rozumné, aby na zásobníku, ale poďme zmeniť na malloc realizáciu. Takže každý z nich sa teraz bude niečo ako uzol * node9 = malloc (sizeof (uzol)). A teraz budeme musieť urobiť našu kontrolu. if (node9 == NULL) - Nechcel som, že - return 1, a potom môžeme urobiť node9->, pretože teraz je to ukazovateľ, hodnota = 6, node9-> left = NULL, node9-> P = NULL, a budeme mať k tomu, že pre každú z týchto uzlov. Takže namiesto toho, poďme dať vnútri samostatná funkcia. Hovorme tomu uzol * build_node, a to je trochu podobný API, ktoré poskytujeme na Huffman kódovanie. Dáme vám inicializátor funkcie pre strom a Deconstructor "funkcie" pre tie stromy a rovnaké pre lesy. 

Takže tu budeme mať inicializátor funkciu len vybudovať uzol pre nás. A to bude vyzerať skoro presne takto. A ja dokonca bude lenivý a nie zmeniť názov premennej, aj keď node9 nedáva zmysel. Oh, myslím, že node9 tieto hodnota by nemala byť 6. Teraz sa môžeme vrátiť node9. A tu by sme sa mali vrátiť null. Všetci sa dohodli na tomto build-a-uzol funkcie? Takže teraz môžeme len volať, že k vytvoreniu ľubovoľného uzla s danou hodnotou a null ukazovateľmi. Teraz môžeme nazvať to, že môžeme urobiť uzol * node9 = build_node (9). A poďme urobiť. . . 6, 3, 7, 6, 3, 7. A teraz chceme nastaviť rovnaké ukazovatele, s výnimkou teraz je všetko už z hľadiska ukazovateľov takže už nie je nutné adresu. Dobre. Takže to, čo je to posledné, čo chcem robiť? Tam je pre kontrolu chýb, že som to robiť. Čo stavať uzla návrat? [Študent, nezrozumiteľné] >> Jo. Ak malloc zlyhalo, bude to vráti null. Takže budem lenivo dať sem namiesto toho robil podmienku pre každého. Ak (node9 == NULL, alebo - ešte jednoduchšie, to je ekvivalentná len ak nie node9. Takže ak nie je node9, alebo nie node6, alebo nie node3, alebo nie node7, vráti 1. Možno by sme mali vytlačiť malloc zlyhalo, alebo tak niečo. [Študent] Je false rovná null rovnako? [Bowden] Každá nenulová hodnota je false. Takže null je nulová hodnota. Zero je nulová hodnota. False je nulová hodnota. Akékoľvek - skoro len 2 nulovej hodnoty null a nulové, false je len hash definovaná ako nula. To platí aj v prípade, my deklarovať globálne premenné. Ak by sme mali uzla * koreň tu, potom - za pekná vec, o globálnych premenných je to, že majú vždy počiatočnú hodnotu. To nie je pravda funkcií, ako vo vnútri tu, ak máme, rovnako ako, uzol * alebo uzol x. Nemáme poňatia, čo x.value, x.whatever, alebo môžeme vytlačiť a môžu byť ľubovoľné. To nie je pravda, globálnych premenných. Takže uzol root alebo uzol x. V predvolenom nastavení, všetko, čo je globálny, ak nie je výslovne inicializovaný nejakú hodnotu, má nulovú hodnotu ako hodnotu. Tak tu, uzol * root, nemáme explicitne inicializovať k ničomu, tak jeho východisková hodnota bude nulový, čo je nulová hodnota ukazovateľov. Predvolená hodnota x bude znamenať, že x.value je nulová, x.left je null, a x.right je null. Takže, pretože to je štruktúra, budú všetky oblasti struct byť nulové hodnoty. Nemusíme používať, že tu, hoci. [Študent] Tieto structs sú iné ako iné premenné, a ostatné premenné sú odpadky hodnoty, sú nuly? [Bowden] Iné hodnoty taky. Takže v x, bude x je nula. Ak je to v celosvetovom rozsahu, že má počiatočnú hodnotu. Dobre >>. [Bowden] Buď počiatočná hodnota si ho alebo nula. Myslím, že sa postará o všetko. 

Dobre. Takže ďalšiu časť otázky pýta, "Teraz chceme napísať funkciu nazvanú obsahuje s prototypom bool obsahuje int hodnotu. " Nebudeme robiť bool obsahuje int hodnotu. Náš prototyp bude vyzerať bool obsahuje (int hodnota. A potom sme tiež chystá odovzdať mu strom , Že by mal byť kontroluje, či má túto hodnotu. Takže uzol * strom). Dobre. A potom sme to tak dá nazvať niečím ako, možno budeme chcieť printf alebo tak niečo. Obsahuje 6, náš koreň. To by malo vrátiť jednu, alebo skutočný, vzhľadom k tomu, obsahuje 5 koreň by sa mal vrátiť false. Tak sa druhý na vykonanie tohto. Môžete to urobiť buď opakované alebo rekurzívne. Dobrá vec na tom, ako sme pripraviť veci je to, že to požičiava seba k nášmu rekurzívne riešenie oveľa jednoduchšie ako globálna premenná spôsobom urobil. Pretože ak budeme jednoducho musieť obsahuje int hodnotu, potom máme žiadny spôsob, ako recursing dole podstromy. Museli by sme mať samostatnú pomocnú funkciu, ktorá recurses stanovuje podstromy pre nás. Ale od tej doby sme zmenili, aby sa strom ako argument, ktoré by malo vždy byť na prvom mieste, Teraz môžeme recurse ľahšie. Takže iteratívny alebo rekurzívne, pôjdeme cez oba, ale uvidíme, že rekurzívne skončí ako bytia celkom jednoduché. Dobre. Má niekto niečo môžeme pracovať s? 

[Študent] Mám iteratívny riešenie. >> Dobre, iteratívny. Dobre, to vyzerá dobre. Takže, chcú ísť k nám cez to? [Študent] Jasne. Tak som nastaviť premennú TEMP získať prvý uzol stromu. A potom som prosmyčkovat, zatiaľ čo teplota sa nerovná null, takže aj keď bol ešte na strome, myslím. A v prípade, že hodnota je rovná hodnote, že teplota je ukazuje na, potom vráti túto hodnotu. V opačnom prípade, kontroluje, či je to na pravej strane alebo na ľavej strane. Ak ste niekedy situáciu, keď už nie je strom, potom sa vráti - to ukončí slučku a vráti false. [Bowden] Dobre. Takže to vyzerá dobre. Každý, kto má nejaké pripomienky na čokoľvek? Nemám korektnosť pripomienky vôbec. Jedna vec, ktorú môžeme urobiť, je to chlap. Oh, to pôjde trochu podlhovasté. Urobím to vymyslel. Dobre. 

Každý by si mal uvedomiť, ako trojica funguje. Tam určite bola kvízov v minulosti ktoré vám funkciu s ternárnu operátor, a hovoria, to preložiť, urobiť niečo, čo nepoužíva trojzložkových. Takže je to veľmi bežný prípad, kedy by som si použiť ternárnu, kde v prípade niektorých podmienka nastaviť premennú na niečo, else nastaviť rovnakú premennú na niečo iné. To je niečo, čo veľmi často môže byť premenený na takéto veci kde nastaviť túto premennú na toto - alebo, no, je to pravda? Potom je táto, inak to. [Študent] Prvá z nich je, ak pravda, nie? [Bowden] Jo. Spôsob, akým som vždy čítal, je teplota rovná hodnote väčšia ako temp hodnota, potom to, inak to. Je to pokladám otázku. Je to väčšie? Potom vykonajte prvá vec. Else to druhá vec. Aj takmer vždy - dvojbodka, ja len - v mojej hlave, som čítal, ako inak. 

Má niekto rekurzívne riešenie? Dobre. Tento budeme - to by už bolo skvelé, ale budeme robiť ešte lepšie. To je docela veľa rovnaký presný nápad. Je to len, no, chceš vysvetľovať? [Študent] Jasne. Takže sme uistite sa, že strom nie je null prvý, pretože ak je strom null potom to bude vrátiť false, pretože sme ho nenašli. A ak je to ešte strom, ideme do - sme najprv skontrolujte, či je hodnota aktuálnej uzol. Vracia true, ak je, a ak nie my recurse vľavo alebo vpravo. Znie to vhodné? >> Mm-hmm. (Dohoda) Takže si všimnúť, že je to takmer - štruktúrne veľmi podobné iteratívny riešenie. Je to len, že namiesto toho, aby recursing, mali sme while. A základné prípad, kedy strom nie je rovnaký null bola podmienka, za ktorej sme sa rozišli z cyklu while. Sú veľmi podobné. Ale budeme ešte o krok ďalej. Teraz to isté tu. Oznámenie sa vraciame rovnakú vec v oboch týchto tratiach, s výnimkou jeden argument je iný. Takže budeme robiť, že do trojice. Trafil som možnosť niečo, a to robilo symbol. Dobre. Takže budeme vracať obsahuje, že. Začína to byť viac riadkov, dobre, zväčšovať v ňom je. Obvykle, ako štylistický vec, nemyslím si, že veľa ľudí dať priestor po šíp, ale myslím, že ak ste v súlade, to je v poriadku. Ak je hodnota nižšia ako hodnota stromu, chceme recurse na strome naľavo, else chceme recurse na strome vpravo. Takže to bol prvý krok urobiť z tohto pohľad menšie. Krok dva takže to pohľad menšie - môžeme oddeliť to do niekoľkých riadkov. Dobre. Krok dva, aby to vyzeralo menšie je tu, tak návratová hodnota rovná strom hodnotu, alebo obsahuje čokoľvek. 

To je dôležitá vec. Nie som si istý, či to povedal výslovne v triede, ale je to len skrat hodnotenie. Nápad tu je hodnota == strom hodnota. Ak je to pravda, potom je to pravda, a my chceme, aby "alebo", že s tým, čo je tu. Takže bez premýšľania, čo je tu, to, čo je celý výraz bude vrátiť? [Študent] True? >> Jo, pretože pravda o ničom, or'd - alebo pravda or'd s ničím, je nutne pravdivé. Takže akonáhle vidíme návratovú hodnotu = strom hodnota, sme len tak vrátiť true. Ani ísť do recurse ďalej obsahuje dole riadok. Môžeme si vziať tento krok ďalej. Návrat strom nie je rovnaký neplatné a všetky z toho. To robilo to jeden-line funkcie. To je tiež príklad skrátené vyhodnocovanie. Ale teraz je to rovnaká myšlienka - miesto - takže ak strom sa nerovná null - alebo, dobre, ak strom sa rovná null, čo je ťažký prípad, ak strom rovná null, potom prvou podmienkou bude false. Takže false AND s ničím sa bude čo? [Študent] False. Jo >>. To je druhá polovica skrátené vyhodnocovanie, kde, ak strom nie je rovné null, potom sa nebudeme ani ísť - alebo ak strom má rovnakú hodnotu null, potom nebudeme robiť hodnotu == strom hodnotu. Sme len tak aby sa okamžite vrátil false. Čo je dôležité, pretože ak nie skrat vyhodnotiť, potom ak strom má rovnakú hodnotu null, táto druhá podmienka bude k poruche seg, pretože strom-> hodnota dereferencing null. Tak to je to. Môže to - posun raz v To je veľmi bežná vec tiež, nie robiť toto jeden riadok s tým, ale je to bežná vec v podmienkach, možno nie tu, ale ak (strom! = NULL, a strom-> value == hodnota), robiť čokoľvek. To je veľmi bežný stav, kedy namiesto toho, aby že sa to do dvoch IFS, kde ako je strom nulový? Dobre, to nie je null, tak teraz je to strom hodnota rovná hodnote? Urob to. Namiesto toho, že táto podmienka, bude to nikdy seg poruchu pretože to vypukne, ak sa to stane, že je null. No, myslím, že ak váš strom je úplne neplatný ukazovateľ, to môže ešte seg poruchu, ale nemôže seg poruchu, ak strom je null. Keby to bolo null, by to zlomiť, ako ste niekedy dereferenced ukazovateľ na prvom mieste. [Študent] Je to tzv lenivej vyhodnocovanie? 

[Bowden] Lenivé vyhodnocovanie je samostatná vec. Lenivé vyhodnocovanie je, ako by ste požiadať o hodnotu, pýtaš vypočítať hodnotu, druh, ale nemusíte ju hneď. Takže kým sa skutočne potrebovať, nie je hodnotená. To nie je úplne to isté, ale v Huffmanovo Pset, sa hovorí, že sme "lenivo" písať. Dôvod, prečo sme to urobiť, je preto, že sme vlastne vyrovnávacej pamäte write - Nechceme písať jednotlivé bity v čase, alebo jednotlivé byty v dobe, sme namiesto toho chce dostať kus bajtov. Potom, akonáhle budeme mať kus bajtov, potom budeme písať to. Aj keď ste požiadať ju písať - a fwrite a fread to rovnaký druh veci. Oni bufferu vaše číta a píše. Aj keď sa spýtate to písať hneď, to asi nebude. A môžete si byť istí, že sa veci majú byť zapísané kým nezavoláte hfclose alebo čo to je, ktorý potom hovorí, jo, ja Zatváram svoj súbor, to znamená, že som radšej napísať všetko, čo som nenapísal ešte. To nie je potrebné písať všetko von kým sa pri zatváraní súboru, a potom je treba. Takže to je práve to, čo lenivý - to počká, kým sa to musí stať. Tento - sa 51 a prejdete do neho podrobnejšie, pretože OCaml a všetko v 51, všetko je rekurzia. Nie sú k dispozícii žiadne iteratívny riešenie, v podstate. Všetko je rekurzia, a lenivé vyhodnocovanie bude dôležité pre mnoho okolností kde, ak ste si lenivo vyhodnocovať, znamenalo by to - Príkladom je prúdy, ktoré sú nekonečne dlho. Teoreticky, môžete premýšľať o prirodzených čísel ako prúd 1-2-3-4-5-6-7, Takže lenivo vyhodnotené veci sú v poriadku. Keď poviem, že chcem desiatej číslo, potom môžem hodnotiť až na desiate číslo. Ak chcem sté číslo, potom môžem hodnotiť až po sté číslo. Bez lenivé vyhodnocovanie, potom to bude snažiť zhodnotiť všetky čísla okamžite. Ste hodnotenie nekonečne veľa čísel, a to jednoducho nie je možné. Takže existuje veľa okolností, kedy lenivé vyhodnocovanie je len nevyhnutné na získanie veci do práce. 

Teraz chceme písať vložku, kde vložka bude Podobne zmena v jeho definícii. Takže teraz je to bool vložka (int value). Budeme zmeniť na bool vložky (int hodnota, uzol * strom). Sme vlastne bude meniť, že opäť v trochu, uvidíme prečo. A poďme presunúť build_node, len pre kruci to, nad vložte takže nemáme písať funkcie prototyp. Čo je náznak, že budete používať build_node v letáku. Dobre. Take minútu za to. Myslím, že som zachránil revíziu, ak chcete vytiahnuť z toho, alebo aspoň, som teraz. Chcel som mierny prestávku na premýšľanie o logike vložky, Ak nemôžete myslieť na to. V podstate, budete len niekedy vkladanie na listy. Rovnako ako, keď som vložiť 1, potom som nevyhnutne bude vkladanie 1 - Budem sa zmení na čiernu - Budem sa vloží 1 sem. Alebo keď som vložiť 4, chcem sa vloží 4 sem. Takže bez ohľadu na to, čo robíte, budete sa vloží na list. Jediné, čo musíte urobiť, je iterácii výrub, až sa dostanete do uzla ktoré by mali byť v uzle rodič, nového uzla rodič, a potom zmeniť jeho ľavej alebo pravej myši, v závislosti na tom, či to je väčšia než alebo menšie, než je aktuálna uzol. Zmena tento ukazovateľ poukázať na svojho nového uzla. Takže určiť iteráciou výrub, aby sa list bod nového uzla. Tiež si myslím, že o tom, prečo zakazuje typ situácie pred, kde som postavil binárny strom, kde to bolo správne ak ste len pozrel na jedného uzla, ale 9 bol na ľavej strane 7, ak si zopakovali úplne dole. Tak to je možné v tomto scenári, pretože - premýšľať o vkladanie 9 alebo niečo, na prvom uzla, Idem vidieť 7 a ja som len ísť doprava. Takže bez ohľadu na to, čo mám robiť, keď mám vložením tým, že pôjdete na liste, a k listu pomocou vhodného algoritmu, to bude pre mňa nemožné vložiť 9 naľavo 7 pretože akonáhle som narazila 7 som ísť doprava. Má niekto niečo začať? [Študent] ja. Iste >>. [Študent, nezrozumiteľným] [Ostatné študent, nezrozumiteľným] [Bowden] Je to ocenil. Dobre. Chcete vysvetliť? 

[Študent] Pretože vieme, že sme vkladanie nové uzly na konci stromu, Aj prosmyčkovat stromu iteratívne kým som sa nedostal k uzlu, ktorá ukazovala na nulu. A potom som sa rozhodol dať ho buď na pravej strane alebo na ľavej strane tohto práva využívajú premenné, to mi povedal, kam to dať. A potom, v podstate som len robil, že posledný - že teplota uzol bod na nový uzol, ktorý bol vytváraného buď na ľavej strane, alebo na pravej strane, v závislosti na tom, čo je hodnota práv bol. Nakoniec som nastaviť nový uzol hodnoty na hodnotu jeho testovanie. [Bowden] Dobre, takže vidím jeden problém tu. To je ako 95% ceste tam. Jeden problém, ktorý vidím, dobre, niekto iný vidieť problém? Čo je okolnosť, pod ktorou vymaniť sa z slučky? [Študent] Ak teplota je null? Jo >>. Tak ako sa vymaniť zo slučky, ak je teplota je null. Ale čo mám robiť tu? Aj dereferencia temp, ktorý je nevyhnutne null. Takže ďalšia vec, ktorú musíte urobiť, je nielen sledovať, kým teplota je null, Ak chcete sledovať rodičia za všetkých okolností. Chceme tiež, aby uzol * rodičia, myslím, že môžeme mať, že pri nulovom na prvom mieste. To bude mať podivné správanie pre koreň stromu, ale k tomu sa dostaneme. Ak je hodnota vyššia než čokoľvek, potom temp = temp pravdu. Ale predtým, než to urobíme, rodič = temp. Alebo sa rodičia vždy rovnaké teploty? Je to tak? Ak teplota nie je null, potom budem pohybovať dole, bez ohľadu na to, do uzla, pre ktorý temp je rodič. Takže rodičia to bude temp, a potom som sa presunúť teplota dole. Teraz teplota je null, ale rodičia poukazuje na rodičov na vec, ktorá je null. Takže tu dole, nechcem, aby na pravú mieru sa rovná 1. Tak som sa pohyboval napravo, takže ak P = 1, a myslím, že budete tiež chcieť urobiť - ak presuniete vľavo, ktorú chcete nastaviť priamo rovná 0. Alebo, ak ste niekedy posunie doprava. Takže vpravo = 0. Ak vpravo = 1, Teraz chceme, aby sa materský správny ukazovateľ newnode, inak by sme chcieť, aby materské ľavej ukazovateľ newnode. Otázky týkajúce sa, že? Dobre. Tak toto je spôsob, ako - no, vlastne, miesto toho, čo robíme, sme napoly očakával, môžete použiť build_node. A potom, keď newnode rovná null, vráti false. To je to. Teraz, to je to, čo sme očakávali, aby si urobil. 

To je to, čo zamestnanci riešenie robiť. Nesúhlasím s tým, ako "správne" spôsob, ako ísť na to ale to je úplne v poriadku a že to bude fungovať. Jedna vec, ktorá je trochu divné je teraz ak strom začína za neplatné, míňame v nulovej stromu. Myslím, že to záleží na tom, ako definovať správanie prejde v nulovej stromu. Povedal by som, že ak omdliete v nulovej stromu, potom vložením hodnoty do nuly stromu mal jednoducho vrátiť strom, kde jedinou hodnotou je, že jeden uzol. Ľudia s tým súhlasíte? Dalo by sa, ak by ste chceli, ak predáte null stromu a chcete vložiť hodnotu do neho, vráti false. Je na vás, aby ste definovať, že. Ak chcete urobiť prvá vec, ktorú som povedal, a potom - dobre, budete mať ťažkosti robí, že, pretože že by bolo jednoduchšie, keby sme mali globálny ukazovateľ na vec, ale nemáme, takže ak strom je null, nie je nič, čo môže robiť, že. Môžeme len vráti false. Takže budem meniť vložku. My technicky mohol len zmeniť toto právo tu, ako to iterácia nad vecami, ale budem meniť vložku, aby sa uzol ** strom. Dvojlôžkové ukazovatele. Čo to znamená? Miesto zaoberanie sa ukazovateľov na uzly, čo budem sa manipulovať, je tento ukazovateľ. Budem sa manipulovať tento ukazovateľ. Budem sa manipulovať ukazovatele priamo. To dáva zmysel, pretože, myslím, že o tom sa - dobre, teraz tento bodov na hodnotu null. To, čo chcem urobiť, je manipulovať tento ukazovateľ poukázať na NOT NULL. Chcem, aby to poukázať na môj nový uzol. Keby som len sledovať ukazovatele na mojich ukazovateľov, potom som nemusíte sledovať materskej ukazovateľ. Môžem len sledovať, či je ukazovateľ ukazuje na null, a ak ukazovateľ ukazuje na null, zmeniť, aby ukazoval na uzol chcem. A môžem zmeniť to, pretože mám ukazovateľ na ukazovateľ. Poďme sa pozrieť práve teraz. Môžete si skutočne urobiť rekurzívne celkom ľahko. Chceme urobiť? Áno, máme. 

Poďme sa pozrieť, to rekurzívne. Po prvé, to, čo je naša základňa prípad bude? Takmer vždy náš základný scenár, ale v skutočnosti, to je trochu zložitejšie. Prvé vecí, prvý, if (tree == NULL) Myslím, že sme len tak vrátiť false. To sa líši od svojho stromu bytia null. To je ukazovateľ na vašom koreňovom ukazovatele zatiaľ null čo znamená, že koreňová ukazovateľ neexistuje. Takže tu dole, keď to urobím uzol * - povedzme znovu to. Node * root = NULL, a potom budem volať vložky tým, že robí niečo ako, vložiť do 4 & koreňa. Tak a koreň, ak je koreň uzol * potom a koreň bude uzla **. To je platné. V tomto prípade, strom, tu, Strom nie je null - alebo vložka. Tu. Strom nie je nula, * strom je nulový, čo je v poriadku pretože ak * strom je null, potom som si s ním manipulovať Doteraz poukázať na to, čo chcem, aby to odkazovať. Ale ak strom je null, to znamená, že som sem prišiel a povedal null. To nedáva zmysel. Nemôžem nič robiť s tým. Ak je strom null, vráti false. Takže som v podstate už povedal, čo naša skutočná základňa prípad je. A čo je to, že bude? [Študent, nezrozumiteľným] [Bowden] Áno. Takže ak (* tree == NULL). To sa týka prípadu sem kde, ak má červený ukazovateľ je ukazovateľ som sa zameral na, tak, ako by som sa zameral na tohto ukazovateľa, teraz som sa zameral na tomto ukazovateli. Teraz som sa zameral na tomto ukazovateli. Takže ak má červený ukazovateľ, ktorý je môj uzol **, je vždy - ak *, môj červený ukazovateľ, je stále null, to znamená, že som v prípade, kedy som so zameraním na ukazovateľ, ktorý ukazuje - to je ukazovateľ, ktorý patrí k listu. Chcem zmeniť tento ukazovateľ aby ukazoval na môj nový uzol. Vráťte sa sem. Môj newnode bude len uzol * n = build_node (hodnota) potom n, ak n = NULL, vráti false. Else chceme zmeniť to, čo sa ukazovateľ je v súčasnej dobe ukazuje na sa teraz ukazujú na našej novo postavené uzla. Môžeme skutočne urobiť tu. Namiesto toho povedal n, hovoríme, * tree = ak * stromu. Všetci pochopili, že? Že rokovania s ukazovateľmi na ukazovatele, môžeme zmeniť Null ukazovatele poukázať na veci, ktoré chceme, aby odkazovať. To je náš základný scenár. 

Teraz náš recidívy, alebo naše rekurzia, bude veľmi podobný všetkým ostatným rekurzia sme robili. Budeme chcieť vložiť hodnotu, a teraz budem používať ternárnu znova, ale to, čo je naša podmienka bude? Čo je to, čo hľadáme rozhodnúť, či chceme ísť doľava alebo doprava? Poďme to v samostatných krokoch. Ak (hodnota <), čo? [Študent] Strom je hodnota? [Bowden] Takže nezabudnite, že som v súčasnej dobe - [Študenti, nezrozumiteľné] [Bowden] Jo, tak tu, povedzme, že táto zelená šípka je príkladom toho, čo je v súčasnej dobe strom, je ukazovateľ na tento ukazovateľ. Takže to znamená, že som ukazovateľ na ukazovateľ na 3. The dereferencia dvakrát znelo to dobre. Čo mám - ako to mám urobiť, že? [Študent] dereferencia raz, a potom vykonajte arrow takto? [Bowden] Tak (* strom) je dereferencia raz, -> hodnota bude mi hodnotu uzla, ktorý som nepriamo ukazuje. Tak som si tiež napísať, že ** tree.value ak si to prajete. Buď funguje. Ak tomu tak je, potom chcem zavolať vložiť s hodnotou. A to, čo je moje aktualizovaný uzol ** bude? Chcem ísť doľava, takže ** tree.left bude moja ľavá. A chcem, aby ukazovateľ na tej veci tak, že v prípade, že ľavá nakoniec je nulová ukazovateľ, Ja ju upraviť, aby ukazoval na môj nový uzol. 

A druhý prípad môže byť veľmi podobné. Poďme vlastne urobiť, aby moje trojica práve teraz. Vložte hodnotu, ak hodnota <(** strom). Hodnotu. Potom chceme aktualizovať naše ** doľava, else chceme aktualizovať naše ** vpravo. [Študent] Znamená to, že sa ukazovateľ na ukazovateľ? [Bowden] Nezabudnite, že - ** tree.right je uzol hviezda. [Študent, nezrozumiteľné] >> Jo. ** Tree.right je ako tento ukazovateľ, alebo tak niečo. Takže tým, že ukazovateľ na to, že mi dáva to, čo chcem o ukazovateľ na toho chlapa. [Študent] Mohli by sme ísť znovu, prečo sme pomocou dvoch ukazovateľov? [Bowden] Jo. Takže - nie, môžete, a že riešenie pred Bol to spôsob, ako to urobiť bez toho, aby robili dva ukazovatele. Musíte byť schopní pochopiť pomocou dvoch ukazovateľov, a to je čistejšie riešenie. Všimnite si tiež, že to, čo sa stane, keď môj strom - čo sa stane, keď moja koreňom boli null? Čo sa stane, keď urobím tento prípad tu? Takže uzol * root = NULL, vložte 4 do & koreňa. Čo je koreň bude po tomhle? [Študent, nezrozumiteľné] >> Jo. Root hodnota bude 4. Root vľavo bude null, koreň právo bude null. V prípade, kedy sa neprešiel korene adresou, sme nemohli meniť koreň. V prípade, že sa strom - kde root je nulový, sme jednoducho museli vrátiť false. Nie je nič, čo by sme mohli urobiť. Nemôžeme vložiť uzol do prázdnej stromu. Ale teraz môžeme, sme jednoducho urobiť prázdny strom do jedného uzla stromu. Ktorý je obvykle očakávaným spôsobom, že by to malo fungovať. 

Ďalej, čo je podstatne kratšia ako tiež udržiavanie prehľadu o rodičov, a tak budete určiť iteráciou úplne dole. Teraz mám rodičia, a ja som so svojou materskou vpravo ukazovateľ na čokoľvek. Namiesto toho, či sme to urobili iteratívne, bolo by to rovnaká myšlienka s slučky while. Ale namiesto toho, aby sa museli vysporiadať s mojím materským ukazovateľom, miesto môj súčasný ukazovateľ by vec že som sa priamo mení na bod na môj nový uzol. Nemám sa zaoberať, či je to ukázal na ľavej strane. Nemám sa zaoberať, či je to orientovaná napravo. Je to len, čo tento ukazovateľ je, budem ju nastaviť, aby ukazoval na môj nový uzol. Všetci pochopili, ako to funguje? Ak nie, prečo to chceme urobiť takto, ale aspoň, že to funguje ako riešenie? [Študent] Kde sa vrátime pravda? [Bowden] To je asi tu. Ak sme správne vložiť, vrátiť true. Else, tu dole budeme chcieť vrátiť bez ohľadu vkladanie výnosy. 

A čo je zvláštne na tomto rekurzívne funkcie? Je to tail rekurzívne, tak dlho, ako sme kompilovat s nejakou optimalizáciou, bude si to uvedomiť a nikdy sa pretečeniu zásobníka z toho, aj keď náš strom má výšku 10.000 alebo 10 miliónov. [Študent, nezrozumiteľným] [Bowden] Myslím, že to robí na Dash - alebo čo úroveň optimalizácie je vyžadované pre koncové rekurzia má byť uznané. Myslím, že to uznáva - GCC a zvonenie tiež majú rôzny význam pre ich optimalizáciu úrovne. Chcem povedať, že to Dash 2, pre istotu, že budú uznávať rekurzia chvosta. Ale my - môžete postaviť ako napríklad Fibonocci alebo tak niečo. Nie je to ľahké otestovať s tým, pretože je ťažké postaviť binárny strom, ktorý je tak veľký. Ale jo, myslím, že je to Dash 2, že ak pri kompilácii s Dash 2, bude to vyzerať pre koncových rekurzia a optimalizovať to von. Poďme späť k - vložiť to doslova posledná vec, ktorú potrebuje. Poďme sa vrátiť k vložky sem kde budeme robiť rovnakú myšlienku. To bude mať stále nedostatok, že nie je schopný úplne zvládnuť keď koreň sám je nulový, alebo cez vstup je nulový, ale namiesto toho sa zaoberá materskej ukazovateľ, Poďme používať rovnakú logiku vedenie ukazovateľov na ukazovatele. Ak tu budeme držať naše uzol ** teraz, a nepotrebujeme sledovať priamo už, ale uzol ** cur = & tree. A teraz naše, kým slučka bude zároveň * teraz sa nerovná null. Nemusíte sledovať rodičov už. Nemusíte sledovať pomocou ľavej a pravej. A ja budem hovoriť temp, pretože sme už používate temp. Dobre. Takže ak (hodnota> * temp), potom a (* temp) -> P else temp = & (* temp) -> vľavo. A teraz, v tomto okamihu, po tomto cykle while, Len som to preto, že je to možno jednoduchšie premýšľať o opakované, ako rekurzívne, ale po tomto cykle while, * Teplota je ukazovateľ chceme zmeniť. 

Než sme mali rodičia, a chceli sme zmeniť buď materskú doľava alebo rodičia vpravo, ale ak chceme zmeniť materskej právo, potom * teplota je rodič pravdu, a môžeme zmeniť priamo. Takže tu dole, môžeme urobiť * temp = newnode, a to je všetko. Takže upozornenie, všetko, čo sme robili v to uzavrieť riadky kódu. V záujme sledovať rodičia vo všetkom, čo je ďalšie úsilie. Tu, ak sa len sledovať ukazovateľ na ukazovateľ, a dokonca aj keby sme chceli zbaviť všetkých týchto zložených zátvoriek teraz, aby to vyzeralo kratšia. To je teraz presne rovnaké riešenie, ale menej riadkov kódu. Akonáhle začnete rozpoznávať to ako platný riešenie, je to tiež jednoduchšie uvažovať o než ako, jo, prečo mám tento príznak na int vpravo? Čo to znamená? Oh, to znamenať, že Zakaždým, keď idem pravdu, musím nastaviť, else if Aj choďte doľava musím nastaviť na nulu. Tu, nemám na dôvod, prečo o tom, že je to proste jednoduchšie myslieť. Otázky? [Študent, nezrozumiteľné] >> Jo. Dobre, takže v poslednej bit - Myslím, že jedna rýchla a jednoduchá funkcia, ktorú môžeme urobiť, je, rokov 's - spolu, myslím, vyskúšať a napísať obsahuje funkcie ktoré nie je jedno, či je to binárny vyhľadávací strom. Táto obsahuje funkcie by mala vrátiť hodnotu true ak kdekoľvek v tomto všeobecnom binárnom stromu je hodnota, ktorú hľadáte. Takže poďme sa najprv to rekurzívne a potom to urobíme iteratívne. Môžeme vlastne len to dohromady, pretože to bude naozaj málo. 

Čo je môj základný scenár bude? [Študent, nezrozumiteľným] [Bowden] Takže ak (strom == NULL), potom čo? [Študent] Návrat false. [Bowden] Else, dobre, ja nepotrebujem else. Ak bol môj druhý base-case. [Študent] Tree hodnota? Jo >>. Takže ak (tree-> value == hodnota. Všimnite si, že sme späť do uzla *, nie je uzol ** s? Obsahuje nikdy sa nebudete musieť používať uzla **, pretože sme sa nemení ukazovatele. Sme jednoducho nabehnúť je. Ak sa tak stane, potom chceme vrátiť true. Else chceme prejsť deti. Takže nemôžeme uvažovať o tom, či všetko vľavo je menej a všetko vpravo je väčšia. Takže to, čo je naša podmienka bude tu - alebo, čo budeme robiť? [Študent, nezrozumiteľné] >> Jo. Return obsahuje (hodnota, strom-> vľavo) alebo obsahuje (hodnota, strom-> vpravo). A to je všetko. A všimnite si, že je nejaký skrat hodnotenie, kde, ak sa stane, že nájdete hodnotu v ľavom stromu, sme nikdy nebudete musieť pozerať na pravom stromu. To je celá funkcie. Teraz sa poďme to iteratívne, ktorý bude menej pekné. Vezmeme obvyklé štart uzla * cur = Strom. Kým (teď! = NULL). Rýchlo bude vidieť problém. Pokiaľ teraz - tu, či sa niekedy uniknúť z tohto, potom sme došli veci pozrieť sa na, tak vráti false. Ak (teraz-> value == hodnota), vráti true. Takže teraz sme na mieste - nevieme, či chceme ísť doľava alebo doprava. So ľubovoľne, poďme odišiel. Ja som samozrejme bežať do problému, kedy som úplne opustené všetko - Budem vždy len kontrolovať ľavú stranu stromu. Nikdy kontrolovať všetko, čo je právo dieťaťa na čokoľvek. Ako môžem tento problém vyriešiť? [Študent] Musíte sledovať vľavo a vpravo v zásobníku. [Bowden] Jo. Takže poďme robiť to struct list, uzol * n, a potom uzol ** ďalej? Myslím si, že funguje dobre. Chceme ísť cez ľavé, alebo rokov 's - tu. Struct = zoznam zoznam, bude to začne pretože na tomto struct zozname. * Listy = NULL. Takže to bude náš prepojený zoznam z podstromu, ktoré sme preskočil. Budeme prechádzať zostalo, ale pretože sme nutne potrebovať vrátiť doprava, Budeme držať pravú stranu vo vnútri nášho struct zoznamu. Potom budeme mať new_list alebo struct, struct list *, new_list = malloc (sizeof (zoznam)). Budem ignorovať chyba-kontrolovať, ale mali by ste skontrolovať, či je to null. New_list uzol, že to bude ukazovať na - oh, to je dôvod, prečo som chcel to tu. Bude to poukázať na druhej struct zozname. To je len, ako lineárnymi zoznamy prácu. To je rovnaké ako int prepojenom zoznamu okrem sme len nahradiť int s uzlom *. Je to úplne rovnaké. So new_list, hodnota našej new_list uzla, bude teraz-> kliknite pravým. Hodnota nášho new_list-> next bude náš pôvodný zoznam, a potom budeme aktualizovať náš zoznam, aby ukazoval na new_list. 

Teraz potrebujeme nejaký spôsob ťahanie vecí, ako sme prejsť celý ľavého podstrome. Teraz musíme vytiahnuť veci z toho, ako teraz je null, nechceme len vrátiť false. Chceme teraz vytiahnuť von na našom novom zozname. Najvýhodnejším spôsobom, ako to urobiť - no, vlastne, je tu niekoľko spôsobov, ako to urobiť. Každý, kto má nejaký návrh? Kde by som mal urobiť, alebo ako by som mal urobiť? Máme len pár minút, ale nejaké návrhy? Namiesto toho, aby - jedným spôsobom, namiesto toho, aby náš stav je pri, to, čo sme v súčasnej dobe hľadá v nie je null, miesto budeme fungovať ďalej, kým náš zoznam sám o sebe je null. Takže ak náš zoznam skončí ako bytia null, potom sme došli veci hľadať, prehľadávať. To však znamená, že prvé, čo v našom zozname je len tak byť prvý uzol. Úplne prvá vec, ktorú bude - sme už treba vidieť, že. So list-> n bude náš strom. list-> next bude null. A teraz, keď zoznam sa nerovná null. Cur sa chystá vytiahnuť niečo z nášho zoznamu. Takže teraz sa chystá na rovnej zoznam-> n A potom zoznam bude na rovné zoznam-> n, alebo list-> next. Takže ak teraz hodnota sa rovná hodnote. Teraz môžeme pridať aj našu pravú myši a naše ľavej ukazovateľ ako dlho ako oni to nie je null. Tu dole, myslím, že by sme mali urobiť, že v prvom rade. Ak (teraz-> P! = NULL) potom budeme vložiť tento uzol do nášho zoznamu. Ak (teraz-> vľavo), to je trochu práce navyše, ale je to v poriadku. Ak (teraz-> doľava! = NULL), a budeme vložiť ľavej do nášho prepojeného zoznamu, a že by mali byť, že. My iteráciu - tak dlho, ako budeme mať niečo v našom zozname, máme ďalší uzol na pohľad. Takže sa pozrieme v tomto uzle, sme vopred na náš zoznam k ďalšiemu. Ak tento uzol je hodnota, ktorú hľadáte, môžeme sa vrátiť true. Else vložte obe naše ľavej a pravej podstromu, ako dlho ako oni to nie je null, do nášho zoznamu takže sme nevyhnutne ísť cez ne. Takže ak neboli null, keď náš koreň ukazovateľ upozornil na dve veci, potom najprv sme vytiahli niečo tak náš zoznam skončí ako bytia null. A potom sme dali dve veci späť, takže teraz náš zoznam je veľkosť 2. Potom budeme slučky späť a my len tak vytiahnuť, povedzme, ľavá ukazovateľ nášho koreňového uzla. A to si len dejú, skončíme slučky nad všetkým. 

Všimnite si, že to bolo podstatne zložitejšie v rekurzívne riešenie. A ja som povedal: viackrát že rekurzívne riešenie má zvyčajne veľa spoločného s iteratívny riešenie. Tu je to presne to, čo rekurzívne riešenie robí. Jedinou zmenou je, že namiesto toho, aby implicitne pomocou zásobníka, zásobník programu, ako spôsob, ako udržať sledovať, čo uzly, stále potrebujete navštíviť, Teraz budete musieť použiť prepojeného zoznamu. V oboch prípadoch sa vedenie sledovať, čo uzla musí ešte byť navštívené. V rekurzívne prípade, že je to proste jednoduchšie, pretože zásobník je implementovaný pre vás ako programu zásobníka. Všimnite si, že tento spájať zoznam, to je zásobník. Či sme len dať na stack je hneď to, čo budeme vytiahnite zásobník na návštevu ďalší. Sme z času, ale nejaké otázky? [Študent, nezrozumiteľným] [Bowden] Jo. Takže ak máme prepojeného zoznamu, prúd bude poukázať na toho chlapa, a teraz sme len zlepšovaniu našich prepojeného zoznamu zamerať sa na toho chlapa. Sme tu pojazdom nad prepojeného zoznamu v tomto riadku. A potom myslím, že by sme mali oslobodiť naše prepojeného zoznamu a podobne raz pred vracia hodnotu true alebo false, musíme iterácii nášho prepojeného zoznamu a vždy sa sem, myslím, ak by sme teraz právo nie je rovné, pridajte ho, takže teraz chceme oslobodiť teraz, pretože, no, my sme úplne zabudnúť na zozname? Jo. Takže to je to, čo chceme robiť. Kde je ukazovateľ? Cur bol potom - chceme do struct zoznam * 10 rovná zoznam vedľa. Free listy, listy = temp. A v prípade, kedy sa vráti true, je potrebné, aby sme iterácii po zvyšok nášho prepojeného zoznamu uvoľňovať veci. Pekná vec, o rekurzívne riešenie je uvoľnenie veci jednoducho znamená objavovať factorings zo zásobníka, ktorý bude diať za vás. Takže sme išli z niečoho, čo to ako 3 riadky ťažko think-o kód k niečomu, čo je výrazne oveľa viac tvrdý-k-si-o riadkov kódu. Nejaké ďalšie otázky? Dobrá. Sme dobrí. Bye! [CS50.TV]