[Powered by Google Translate] [Část 7: Další Komfortní] [Rob Bowden] [Harvard University] [To je CS50] [CS50.TV] Dobrá. Tak jak jsem řekl ve svém e-mailu, to bude binární strom náročný úsek. Ale tam není, že mnoho otázek. Takže budeme se snažit a čerpat z každé otázky a jít do bolestné detailu všech nejlepších způsobů, jak dělat věci. Takže hned na začátku, jsme se projít vzorku kreseb binárních stromů a podobně. Tak tady, "Pamatuj si, že binární strom má uzly podobné těm propojeného seznamu, kromě namísto jednoho ukazatele jsou dva: jeden pro levé "dítě" a jeden pro pravé "dítě". " Takže binární strom je stejně jako propojeného seznamu, kromě struct bude mít dva ukazatele. Tam je trinary stromy, které se chystají tři ukazatele, tam jsou n-ární stromy, které právě mají obecný ukazatel že pak budou muset malloc být dostatečně velké, aby se dost ukazatele na všech možných dětí. Takže binární strom jen se stane, že konstantní množství dvou. Pokud chcete, můžete si dát propojeného seznamu jako unární strom, ale já si nemyslím, že někdo volá, že. "Nakreslete boxy-a-arrows diagram binárního stromu uzel obsahující Nate oblíbené číslo, 7, kde každé dítě ukazatel je null. " Takže iPad režimu. 

Bude to být docela jednoduché. Jsme prostě bude mít uzel, budu kreslit jako čtverec. A já budu čerpat hodnoty zde. Takže hodnota půjde sem, a pak tady dole budeme mít levé ukazatel vlevo a vpravo ukazatel vpravo. A to je velmi, takže je zvykem nazývat levý a pravý, ukazatel jména. Oba tito budou mít hodnotu null. To bude jen null, a že bude jen null. Dobře. Takže zpět sem. "S propojeného seznamu, jsme měli pouze k uložení ukazatele na prvním uzlu v seznamu za účelem pamatovat celý spojový seznam nebo celý seznam. Stejně tak, se stromy, máme pouze k uložení ukazatele na jednom uzlu, aby se pamatovat celý strom. Tento uzel je calle 'root' stromu. Stavět na diagramu z doby před nebo nakreslit nový tak, že máte boxy-a-arrows znázornění binárního stromu s hodnotu 7, pak 3 v levé, pak 9 na pravé straně, a pak 6 na pravé straně 3 ". Uvidíme, jestli si pamatuju všechno v mé hlavě. Tak to bude naše kořen tady. Dáme si ukazatel někde, něco, co budeme volat kořen, a to ukazuje na toho chlapa. Nyní se vytvořit nový uzel, co máme, 3 vlevo? Takže nový uzel s 3, a to na počátku ukazuje nulový. Já si jen dát N. Nyní chceme, aby se to jít vlevo 7. Tak jsme změnit tento ukazatel nyní ukazují na toho chlapa. A my to samé. Chceme 9 nad zde který zpočátku jen říká, null. Budeme měnit tento ukazatel, přejděte na 9, a nyní chceme dát 6 na pravé straně 3. Takže to bude - udělat 6. A ten chlap bude směřovat tam. Dobře. Tak to je vše, co je od nás žádá dělat. 

Teď pojďme přes některé pojmy. Už jsme mluvili o tom, jak kořen stromu je na nejvyšší uzel ve stromu. Ten obsahuje 7. Uzly v dolní části stromu se nazývají listy. Každý uzel, který má prostě null jako jeho děti, je list. Je tedy možné, pokud náš binární strom je jen jeden uzel, že strom je list, a to je vše. "" Výška "stromu je počet chmele je nutné provést se dostat z vrcholu do listu. " Dostaneme do, v druhé, rozdíl mezi symetrické a nesymetrické binárních stromů, ale nyní, celková výška tohoto stromu Řekl bych, že je 3, ale pokud budete počítat množství chmele je nutné provést tak, aby se dostat do 9, pak je to opravdu jen výška 2. Právě teď je to nevyvážený binární strom, ale budeme mluvili o vyvážené, když se dostane za relevantní. Takže teď můžeme mluvit o uzlů na stromě, pokud jde ve vztahu k ostatním uzlů stromu. Takže teď máme rodiče, děti, sourozenci, předky a potomci. Oni jsou docela zdravý rozum, co to znamená. Ptáme-li se - je to rodiče. Takže to, co je nadřazený 3? [Studenti] 7. Jo >>. Mateřská se jen bude, co poukazuje na tobě. Tak co, jsou děti 7? [Studenti] 3 a 9. Jo >>. Všimněte si, že "děti" doslova znamená děti, tak 6 se nepoužijí, protože je to jako vnouče. Ale pak, pokud půjdeme potomky, takže jaké jsou potomci 7? [Studenti] 3, 6 a 9. Jo >>. Potomci kořene bude všechno v stromu, snad s výjimkou kořenový uzel sám, pokud nechcete, aby zvážila, že potomek. A konečně, předkové, tak je to v opačném směru. Takže jaké jsou předky 6? [Studenti] 3 a 7. Jo >>. 9 není zahrnuta. Je to jen přímé linie zpět do kořenového adresáře bude vaši předkové. 

"Řekneme, že binární strom je" přikázal ", pokud pro každý uzel ve stromu, všechny jeho potomky na levé straně mají menší hodnoty a všechny ty, na pravé straně jsou větší hodnoty. Například, je strom nad objednal, ale není to jen možné objednat uspořádání. " Než se dostaneme k tomu, objednal binární strom je také známý jako binární vyhledávací strom. Zde se stalo, že se nazývat to objednané binární strom, ale nikdy jsem neslyšel, že jen objednat binární strom před, a na kvíz jsme mnohem častěji, aby strom binárního vyhledávání. Jsou jedna a ta samá, a to je důležité, poznáte rozdíl mezi binárním stromem a binární vyhledávací strom. Binární strom je jen strom, který ukazuje na dvě věci. Každý uzel poukazuje na dvě věci. Neexistuje žádný úvaha o hodnotách, které se ukazuje na. Tak jako tady, protože je to binární vyhledávací strom, víme, že když jdeme vlevo 7, pak všechny hodnoty, které můžeme případně dosáhnout tím, že jde vlevo 7 musí být menší než 7. Všimněte si, že všechny hodnoty menší než 7 jsou 3 a 6. Ti jsou na levé straně 7. Pokud se jít napravo 7, všechno musí být větší než 7, takže 9 je na pravé straně 7, takže jsme v pohodě. Toto není případ binárního stromu, pro pravidelné binárního stromu můžeme jen mají 3 nahoře, 7 na levé straně, 9 na levé straně 7, není objednání hodnot vůbec. Nyní, nebudeme vlastně dělat, protože je to nudné a zbytečné, ale "zkusit nakreslit tolik objednané stromů, jak si můžete myslet pomocí čísla 7, 3, 9, a 6. Kolik odlišné uspořádání jsou tam? Co je výška každé z nich? " 

Uděláme pár, ale hlavní myšlenka je, To je v žádném případě jedinečné znázornění binárního stromu, který obsahuje tyto hodnoty. Vše co potřebujeme, je nějaký binární strom, který obsahuje 7, 3, 6 a 9. Dalším možným platné jeden by být kořenový je 3, jít doleva a je to 6, přejděte doleva a je to 7, jít doleva a je to 9. To je naprosto platný binární vyhledávací strom. Není to velmi užitečné, protože je to stejně jako propojeného seznamu a všechny tyto ukazatele jsou jen nulový. Ale je to platný strom. Jo? [Student] Ne hodnoty musí být větší na pravé straně? Nebo je to -? >> Ty jsem chtěl jít na druhou stranu. K dispozici je také - jo, pojďme přejít to. 9, 7, 6, 3. Dobrý úlovek. To ještě musí poslouchat, co binární strom vyhledávání dělat. Takže všechno na levé straně musí být menší než daný uzel. Mohli bychom jen přesunout, řekněme, tato 6 a dát sem. Ne, nemůžeme. Proč jsem to dělat, že? Pojďme udělat - tady je 6, zde je 7, 6 bodů na 3. To je stále platný binární vyhledávací strom. Co je špatně, když si - uvidíme, jestli můžu přijít s uspořádáním. Jo, dobře. Takže to, co je špatně s tímto stromem? Myslím, že jsem už dal náznak, že je něco v nepořádku s ní. Proč jsem to dělat, že? Dobře. To vypadá rozumně. Podíváme-li se na každém uzlu, jako je 7, pak na levé straně 7 je 3. Takže máme 3, věc vpravo 3 je 6. A když se podíváte na 6, ta věc vpravo 6 je 9. Tak proč je to není platný binární vyhledávací strom? [Studenti] 9, je stále na levé straně 7. Jo >>. Musí to být pravda, že všechny hodnoty, které můžete případně dosáhnout tím, že půjdete na levé straně 7 arů méně než 7. Pokud půjdeme vlevo 7, dostaneme se 3 a stále můžeme dostat do 6, můžeme ještě dostat do 9, ale tím, že má pryč méně než 7, bychom však být schopen se dostat na číslo, které je větší než 7. Takže to není platný binární vyhledávací strom. 

Můj bratr vlastně měl rozhovor otázku to bylo v podstatě to, jen kód do něčeho k ověření zda strom je binární vyhledávací strom, a tak první věc, kterou udělal, bylo, jen zkontrolovat, v případě, že levý a pravý jsou správné, a pak iterovat tam. Ale nemůžeš jen to, že, budete mít neustále přehled na skutečnost, že teď, když jsem pryč odešel ze dne 7., vše v tomto podstromu musí být menší než 7. Správný algoritmus potřebuje sledovat z mezí, které je možné hodnoty možná spadají dovnitř Nebudeme projít všechny z nich. K dispozici je pěkná opakování vztah, i když jsme se dostali k těm, jinak nebudeme se k těm, definování, kolik jich vlastně je. Takže tam je 14 z nich. Myšlenka na to, jak by to matematicky je jako, si můžete vybrat jeden libovolný jednoho být kořenový uzel, a pak, když vybrat 7 být kořenový uzel, pak tam jsou, řekněme, některá čísla, které mohou jít být mé levici uzel, a tam jsou některé čísla, která mohou být moje pravá uzel, ale pokud jsem n celkové počty, pak se částka, která může jít vlevo plus částka, která může jít vpravo je n - 1. Takže ze zbývajících čísel, musí být schopen jít buď doleva nebo doprava. Zdá se, že těžké, když jsem dal 3 první pak všechno musí jít doleva, ale když jsem dal 7, pak některé věci může jít vlevo a některé věci mohou jít na práva. A '3 první "Myslel jsem všechno může jít doprava. Je to opravdu, stačí přemýšlet o tom, jak, kolik věcí může jít na další úroveň stromu. A to je se, že je 14, nebo se může čerpat všechny z nich, a pak dostanete 14. 

Vraťme se zpět sem, "Objednané binární stromy jsou skvělé, protože můžeme hledat v nich velmi podobně jako vyhledávání přes tříděném poli. Chcete-li tak učinit, začneme u kořene a práci si cestu dolů stromu směrem listů, kontrola každý uzel v hodnoty na hodnoty, které jsme hledáte. Pokud je aktuální uzel je hodnota nižší než hodnota, kterou hledáme, jdete vedle uzlu pravé dítě. V opačném případě, půjdete do uzlu na levé dítě. V určitém bodě, budete buď najít hodnotu, kterou hledáte, nebo budete spouštět do null, označující hodnotu není ve stromu. " Mám k překreslení stromu jsme měli předtím, že bude trvat sekundu. Ale chceme se podívat do, zda 6, 10, a 1 jsou ve stromu. Takže, co to bylo, 7, 9, 3, 6. Dobře. Čísla chcete vyhledat, chceme podívat do 6. Jak se tento algoritmus funguje? No, máme také nějaké kořenový ukazatel na náš strom. A měli bychom jít ke kořenu a říci, je tato hodnota rovna hodnotě my hledáme? Takže jsme hledali 6, takže to není stejné. Tak jsme dál, a teď říkáme, ano, takže 6 je menší než 7. Znamená to, že chceme jít doleva, nebo chceme jít doprava? [Student] Left. Jo >>. Je to výrazně jednodušší, vše, co musíte udělat, je nakreslit jeden možný uzel stromu a pak ne - místo toho se snaží myslet v hlavě, v pořádku, pokud je to méně, mám jít doleva nebo jít právo, Jen při pohledu na tento obrázek, je to velmi jasné, že musím jít doleva v případě, že uzel je větší než hodnota, že jsem hledal. Takže jdete doleva, teď jsem na 3. Chci - 3, je menší, než je hodnota Hledám, což je o 6. Takže jdeme vpravo, a teď jsem skončil na 6, což je hodnota Hledám, tak jsem se vrátit true. Další hodnota budu hledat je 10. Dobře. Takže 10, nyní se chystá - odříznout, že - bude následovat kořen. Nyní, 10 bude větší než 7, tak se chci podívat na pravé straně. Chystám se jít sem, 10 bude větší než 9, takže budu chtít podívat na pravé straně. Přišel jsem sem, ale sem teď jsem na null. Co mám dělat, když jsem narazila null? [Student] Návrat false? Jo >>. Nenašel jsem 10. 1 se bude téměř totožný případ, kromě toho, že to prostě bude převrácený, namísto hledání dolů na pravé straně, jdu se podívat dolů na levé straně. 

Myslím, že teď jsme vlastně dostat ke kódu. Tady je místo, kde - otevřít CS50 spotřebič a navigaci si cestu tam, ale můžete také jen to je v prostoru. Je to asi ideální, aby to v prostoru, protože mohou pracovat v prostoru. "Nejprve budeme potřebovat novou definici typu pro binární uzel stromu obsahuje int hodnoty. Použití desku spotřebiče typedef níže, vytvořit novou definici typu pro uzel v binárním stromu. Pokud narazíte. . . "Bla, bla, bla. Dobře. Takže pojďme dát desku spotřebiče tady, typedef struct uzel, a uzel. Jo, dobře. Takže jaké jsou pole budeme chtít v naší uzlu? [Student] Int a pak dva ukazatele? >> Int hodnota, dva ukazatele? Jak psát ukazatelů? [Student] Struct. >> Měl bych přiblížit dovnitř Jo, tak struct uzel * vlevo, a struct uzel * P. A pamatujte diskusi od minule, že toto nemá smysl, to nedává smysl, To nedává smysl. Musíte všechno tam s cílem definovat tuto rekurzivní struct. Dobře, tak to je to, co náš strom bude vypadat. Pokud bychom udělali trinary strom, pak uzel může vypadat jako b1, b2, struct uzel * b3, kde b je větev - vlastně, já jsem slyšel, že víc vlevo, střední, pravý, ale co. My jen o binární, tak doprava, doleva. "Teď vyhlásit globální uzel * proměnné pro kořen stromu." Takže my nebudeme dělat, že. Aby se věci poněkud obtížnější a obecnější, nebudeme mít globální uzlu proměnnou. Místo toho, v hlavní budeme deklarovat všechny naše uzlu věci, a to znamená, že pod, když jsme rozběhnou naše obsahuje funkce a náš vložka funkce, místo našich obsahuje funkce jen s použitím tohoto globálního uzlu proměnnou, budeme mít trvat jako argument stromu, který chceme, aby to zpracovat. S globální proměnnou měl dělat věci lépe. Budeme dělat věci těžší. Nyní trvat minutu nebo tak, aby prostě takovéhle věci, kde uvnitř hlavní chcete vytvořit tento strom, a to je vše, co chcete dělat. Zkuste a postavit se k tomuto stromu v hlavní funkci. 

Dobře. Takže si ani nemusíte mít postavil strom celou cestu ještě. Ale někdo něco, co bych mohl vytáhnout nahoru ukázat, jak by se dalo začít budovat takový strom? [Student] Někdo bouchat, snaží se dostat ven. [Bowden] Každý, kdo vyhovuje jejich stromu konstrukce? [Student] Jasně. Je to neudělal. >> To je v pořádku. Můžeme jen dokončit - oh, můžete si ji uložit? Hurá. Takže tu máme - oh, jsem mírně oříznuté. Jsem přiblížení? Zvětšení, přejděte ven. >> Mám dotaz. Jo >>? [Student] Při definování struct, jsou věci jako inicializována na něco? [Bowden] No >> Dobře. Takže budete muset inicializovat - [Bowden] No Při definování, nebo při deklarování struct, není inicializován ve výchozím nastavení, je to jako když deklarovat int. Je to přesně totéž. Je to jako každý z jednotlivých jeho oblastech může mít na odpadky hodnotu v něm. >> A je možné definovat - nebo prohlásit struct způsobem, aby při jejím inicializovat? [Bowden] Ano. Takže, zkratka inicializace syntaxe bude vypadat - Existují dva způsoby, jak to udělat můžeme. Myslím, že bychom měli zkompilovat aby se ujistil, zvonění také to dělá. Pořadí argumentů, které přichází v struct, dáte jako pořadí argumentů uvnitř těchto složených závorek. Takže pokud chcete inicializovat ji 9 a odešel se null a pak doprava bude null, , že by bylo 9, null, null. Alternativou je, a editor nemá rád tuto syntaxi, a to si myslí, že chci nový blok, ale alternativou je něco jako - tady, dám to na nový řádek. Můžete výslovně říci, že jsem zapomněl na přesnou syntaxi. Takže můžete explicitně řešit podle názvu, a říkají, . C, nebo. Hodnota = 9,. Left = NULL. Hádám, že je třeba tato pravidla čárky. . Doprava = NULL, takže tento způsob nemáte skutečně potřebují znát pořadí struct, a když tohle čtete, je to mnohem jednoznačnější, o tom, co je hodnotou inicializována. 

To se stane, že je jedna z věcí, které - tak, pro nejvíce se rozdělit, C + +, je nadmnožinou C. Můžete si vzít kód v C, přesuňte ji k C + +, a to by mělo sestavit. To je jedna z věcí, které C + + nepodporuje, takže lidé mají tendenci, aby to nedělala. Já nevím, jestli je to jediný důvod, proč lidé nemají tendenci dělat to, ale případ, kdy jsem potřeboval použít třeba pro práci s C + +, a tak jsem nemohl použít. Dalším příkladem něčeho, co nefunguje s C + +, je jak malloc vrací "void *," technicky, ale vy jste mohli jen říct, char * x = malloc cokoliv, a to bude automaticky přetypovat na char *. To automatické obsazení nestává v C + +. To by nebylo zkompilovat, a vy byste explicitně potřeba říci char *, malloc, co, hodit to na char *. Není mnoho věcí, které C a C + + neshodnou na, ale ty jsou dva. Takže půjdeme s touto syntaxí. Ale i když jsme nešli s tím syntaxí, to, co je - by mohlo být špatně s tím? [Student] Nepotřebuju, aby dereference to? Jo >>. Pamatujte si, že šipka má implicitní dereference, a tak, když jsme jen do činění s struct, chceme použít. aby se na pole uvnitř struct. A jediný čas používáme šipku je, když chceme udělat - no, šipka je ekvivalentní - že to, co by to znamenalo, kdyby jsem šíp. Všechny arrow prostředek je, dereference to, teď jsem na struct, a můžu pole. Buď si pole přímo, nebo dereference a získat pole - Myslím, že by to mělo být hodnota. Ale tady se zabývám jen struct, ne ukazatel na struct, a tak nemohu použít šipku. Ale tyhle věci můžeme udělat pro všechny uzly. Ach můj bože. To je 6, 7, a 3. Pak můžeme nastavit pobočky v náš strom, můžeme mít 7 - můžeme mít, že by se jeho levá ukazovat na 3. Tak jak to uděláme? [Studenti, nesrozumitelné] >> Jo. Adresa node3, a pokud jste neměli adresu, pak to prostě nebude sestavovat. Ale nezapomeňte, že se jedná o ukazatele na příštích uzlů. Právo by mělo ukazovat na 9, a 3 by měly ukazovat o právu na 6. Myslím, že to je vše nastaveno. Jakékoliv připomínky či dotazy? [Student, nesrozumitelné] Kořen bude 7. Můžeme jen říct, uzel * ptr = nebo kořen, = & node7. 

Pro naše účely, budeme jednat s vložkou, takže budeme chtít napsat funkci vložit do tohoto binárního stromu a vložka je nevyhnutelně bude volat malloc vytvořit nový uzel pro tohoto stromu. Takže věci se dostaneme chaotický s tím, že některé uzly jsou v současné době ve frontě a ostatní uzly jsou skončíme na haldě, když vložíme je. To je zcela v pořádku, ale pouze důvod jsme schopni to udělat na zásobníku Je tomu tak proto, že je to taková spiklenecká příklad, že víme, strom je má být konstruována jako 7, 3, 6, 9. Pokud bychom neměli, pak bychom neměli malloc na prvním místě. Jak uvidíme o něco později, měli bychom být malloc'ing. Právě teď je to naprosto rozumné, aby na zásobníku, ale pojďme změnit na malloc provádění. Takže každý z nich se nyní bude něco jako uzel * node9 = malloc (sizeof (uzel)). A teď budeme muset udělat naši kontrolu. if (node9 == NULL) - Nechtěl jsem, že - return 1, a pak můžeme udělat node9->, protože teď je to ukazatel, hodnota = 6, node9-> left = NULL, node9-> P = NULL, a budeme mít k tomu, že pro každou z těchto uzlů. Takže místo toho, pojďme dát uvnitř samostatná funkce. Říkejme tomu uzel * build_node, a to je poněkud podobný API, které poskytujeme na Huffman kódování. Dáme vám inicializátor funkce pro strom a Deconstructor "funkce" pro ty stromy a stejné pro lesy. 

Takže tady budeme mít inicializátor funkci jen vybudovat uzel pro nás. A to bude vypadat skoro přesně takhle. A já dokonce bude líný a ne změnit název proměnné, i když node9 nedává smysl. Oh, myslím, že node9 tyto hodnota by neměla být 6. Nyní se můžeme vrátit node9. A tady bychom se měli vrátit null. Všichni se dohodly na tomto build-a-uzel funkce? Takže teď můžeme jen volat, že stavět nějaký uzel s danou hodnotou a null ukazateli. Nyní můžeme nazvat to, že můžeme udělat uzel * node9 = build_node (9). A pojďme udělat. . . 6, 3, 7, 6, 3, 7. A teď chceme nastavit stejné ukazatele, s výjimkou teď je všechno už z hlediska ukazatelů takže již není nutné adresu. Dobře. Takže to, co je to poslední, co chci dělat? Tam je pro kontrolu chyb, že jsem to dělat. Co stavět uzlu návrat? [Student, nesrozumitelné] >> Jo. Pokud malloc se nezdařilo, bude to vrátí null. Takže budu líně dát sem místo toho dělal podmínku pro každého. Pokud (node9 == NULL, nebo - ještě jednodušší, to je ekvivalentní jen ne-li node9. Takže pokud není node9, nebo ne node6, nebo ne node3, nebo ne node7, vrátí 1. Možná bychom měli vytisknout malloc se nezdařilo, nebo tak něco. [Student] Je false rovná null stejně? [Bowden] Každá nenulová hodnota je false. Takže null je nulová hodnota. Zero je nulová hodnota. False je nulová hodnota. Jakékoliv - skoro jen 2 nulové hodnoty null a nulové, false je jen hash definována jako nula. To platí iv případě, my deklarovat globální proměnné. Pokud bychom měli uzlu * kořen tady, pak - pěkná věc, o globálních proměnných je to, že mají vždy počáteční hodnotu. To není pravda funkcí, jak uvnitř tady, máme-li, stejně jako, uzel * nebo uzel x. Nemáme ponětí, co x.value, x.whatever, nebo můžeme vytisknout a mohou být libovolné. To není pravda, globálních proměnných. Takže uzel root nebo uzel x. Ve výchozím nastavení, vše, co je globální, není-li výslovně inicializován nějakou hodnotu, má nulovou hodnotu jako hodnotu. Tak tady, uzel * root, nemáme explicitně inicializovat k ničemu, tak jeho výchozí hodnota bude nulový, což je nulová hodnota ukazatelů. Výchozí hodnota x bude znamenat, že x.value je nulová, x.left je null, a x.right je null. Takže, protože to je struktura, budou všechny oblasti struct být nulové hodnoty. Nemusíme používat, že tady, ačkoli. [Student] jsou structs jsou jiné než jiné proměnné, a ostatní proměnné jsou odpadky hodnoty, jsou nuly? [Bowden] Jiné hodnoty taky. Takže v x, bude x je nula. Pokud je to v celosvětovém rozsahu, že má počáteční hodnotu. Dobře >>. [Bowden] Buď počáteční hodnota, kterou dal nebo nula. Myslím, že se postará o všechno. 

Dobře. Takže další část otázky ptá, "Nyní chceme napsat funkci nazvanou obsahuje s prototypem bool obsahuje int hodnotu. " Nebudeme dělat bool obsahuje int hodnotu. Náš prototyp bude vypadat bool obsahuje (int hodnota. A pak jsme také chystá předat strom , že by měl být kontroluje, zda má tuto hodnotu. Takže uzel * strom). Dobře. A pak jsme to tak dá nazvat něčím jako, možná budeme chtít printf nebo tak něco. Obsahuje 6, náš kořen. To by mělo vrátit jednu, nebo skutečný, vzhledem k tomu, obsahuje 5 kořen by se měl vrátit false. Tak se druhý k provedení tohoto. Můžete to udělat buď opakované nebo rekurzivně. Pěkná věc, o tom, jak jsme připravit věci je to, že to půjčuje sebe k našemu rekurzivní řešení mnohem jednodušší než globální proměnná způsobem udělal. Protože pokud budeme prostě muset obsahuje int hodnotu, pak máme žádný způsob, jak recursing dolů podstromy. Museli bychom mít samostatnou pomocnou funkci, která recurses stanoví podstromy pro nás. Ale od té doby jsme změnili, aby se strom jako argument, které by mělo vždy být na prvním místě, Nyní můžeme recurse snadněji. Takže iterativní nebo rekurzivní, půjdeme přes oba, ale uvidíme, že rekurzivní skončí jako bytí docela snadné. Dobře. Má někdo něco můžeme pracovat s? 

[Student] Mám iterativní řešení. >> Dobře, iterativní. Dobře, to vypadá dobře. Takže, chtějí jít k nám přes to? [Student] Jasně. Tak jsem nastavit proměnnou TEMP získat první uzel stromu. A pak jsem prosmyčkovat, zatímco teplota se nerovná null, takže i když byl ještě na stromě, myslím. A v případě, že hodnota je rovna hodnotě, že teplota je ukazuje na, pak vrátí tuto hodnotu. V opačném případě, kontroluje, zda je to na pravé straně nebo na levé straně. Pokud jste někdy situaci, kdy už není strom, pak se vrátí - to ukončí smyčku a vrátí false. [Bowden] Dobře. Takže to vypadá dobře. Každý, kdo má nějaké připomínky na cokoli? Nemám korektnost připomínky vůbec. Jedna věc, kterou můžeme udělat, je to chlap. Oh, to půjde trochu podlouhlé. Udělám to vymyslel. Dobře. 

Každý by si měl uvědomit, jak trojice funguje. Tam určitě byla kvízů v minulosti které vám funkci s ternární operátor, a říkají, to přeložit, udělat něco, co nepoužívá třísložkových. Takže je to velmi běžný případ, kdy bych si použít ternární, kde v případě některých podmínka nastavit proměnnou na něco, else nastavit stejnou proměnnou na něco jiného. To je něco, co velmi často může být přeměněn na takovéhle věci kde nastavit tuto proměnnou na toto - nebo, no, je to pravda? Pak je tato, jinak to. [Student] První z nich je, pokud pravda, ne? [Bowden] Jo. Jak jsem si vždy přečtěte je, temp rovná hodnotě větší než temp hodnota, pak to, jinak to. Je to pokládám otázku. Je to větší? Pak proveďte první věc. Else to druhá věc. I téměř vždy - dvojtečka, já jen - v mé hlavě, jsem četl, jak jinak. 

Má někdo rekurzivní řešení? Dobře. Tenhle budeme - to by již bylo skvělé, ale budeme dělat ještě lépe. To je docela hodně stejný přesný nápad. Je to jen, no, chceš vysvětlovat? [Student] Jasně. Takže jsme ujistěte se, že strom není null první, protože pokud je strom null pak to bude vrátit false, protože jsme ho nenašli. A pokud je to ještě strom, jdeme do - jsme nejprve zkontrolujte, zda je hodnota aktuální uzel. Vrací true, pokud je, a pokud ne my recurse vlevo nebo vpravo. Zní to vhodné? >> Mm-hmm. (Dohoda) Takže si všimnout, že je to téměř - strukturně velmi podobné iterativní řešení. Je to jen, že místo toho, aby recursing, měli jsme while. A základní věc tady, kde strom není stejný null byla podmínka, za níž jsme se rozešli z cyklu while. Jsou velmi podobné. Ale budeme ještě o krok dále. Nyní to samé zde. Oznámení se vracíme stejnou věc v obou těchto tratích, s výjimkou jeden argument je jiný. Takže budeme dělat, že do trojice. Trefil jsem možnost něco, a to dělalo symbol. Dobře. Takže budeme vracet obsahuje, že. Začíná to být více řádků, dobře, zvětšovat v něm je. Obvykle, jako stylistický věc, nemyslím si, že mnoho lidí dát prostor po šíp, ale myslím, že pokud jste v souladu, to je v pořádku. Pokud je hodnota nižší než hodnota stromu, chceme recurse na stromě nalevo, else chceme recurse na stromě vpravo. Takže to byl první krok učinit z tohoto pohled menší. Krok dva takže to pohled menší - můžeme oddělit to do několika řádků. Dobře. Krok dva, aby to vypadalo menší je tady, tak návratová hodnota rovna strom hodnotu, nebo obsahuje cokoliv. 

To je důležitá věc. Nejsem si jistý, jestli to řekl výslovně ve třídě, ale je to jen zkrat hodnocení. Nápad tady je hodnota == strom hodnota. Pokud je to pravda, pak je to pravda, a my chceme, aby "nebo", že s tím, co je tady. Takže bez přemýšlení, co je tady, to, co je celý výraz bude vrátit? [Student] True? >> Jo, protože pravda o ničem, or'd - nebo pravda or'd s ničím, je nutně pravdivé. Takže jakmile vidíme návratovou hodnotu = strom hodnota, jsme jen tak vrátit true. Ani jít do recurse dále obsahuje dolů řádek. Můžeme si vzít tento krok dále. Návrat strom není stejný neplatné a všechny z toho. To dělalo to jeden-line funkce. To je také příklad zkrácené vyhodnocování. Ale teď je to stejná myšlenka - místo - takže pokud strom se nerovná null - nebo, dobře, pokud strom se rovná null, což je těžký případ, pokud strom rovná null, pak první podmínka bude false. Takže false AND s ničím se bude co? [Student] False. Jo >>. To je druhá polovina zkrácené vyhodnocování, kde, pokud strom není rovno null, pak se nebudeme ani jít - nebo pokud strom má stejnou hodnotu null, pak nebudeme dělat hodnotu == strom hodnotu. Jsme jen tak aby se okamžitě vrátil false. Což je důležité, protože pokud ne zkrat vyhodnotit, pak pokud strom má stejnou hodnotu null, tato druhá podmínka bude k poruše seg, protože strom-> hodnota dereferencing null. Tak to je to. Může to - posun jednou v. To je velmi běžná věc také, ne dělat toto jeden řádek s tím, ale je to běžná věc v podmínkách, možná ne tady, ale pokud (strom! = NULL, a strom-> value == hodnota), dělat cokoliv. To je velmi běžný stav, kdy místo toho, aby že se to do dvou IFS, kde jako je strom nulový? Dobře, to není null, takže teď je strom hodnota rovna hodnotě? Udělej to. Namísto toho, že tato podmínka, bude to nikdy seg poruchu protože to vypukne, pokud se to stane, že je null. No, myslím, že pokud váš strom je zcela neplatný ukazatel, to může ještě seg poruchu, ale nemůže seg poruchu, pokud strom je null. Kdyby to bylo null, by to zlomit, než jste někdy dereferenced ukazatel na prvním místě. [Student] Je to tzv. líné vyhodnocování? 

[Bowden] Líné vyhodnocování je samostatná věc. Líné vyhodnocování je, jako byste požádat o hodnotu, ptáš vypočítat hodnotu, druh, ale nemusíte ji hned. Takže dokud se skutečně potřebovat, není hodnocena. To není úplně totéž, ale v Huffmanovo Pset, se říká, že jsme "líně" psát. Důvodem, proč děláme to proto, že jsme vlastně vyrovnávací paměti write - Nechceme psát jednotlivé bity v době, nebo jednotlivé byty v době, jsme místo toho chce dostat kus bajtů. Pak, jakmile budeme mít kus bajtů, pak budeme psát to. I když jste požádat ji psát - a fwrite a fread to stejný druh věci. Oni bufferu vaše čte a píše. I když se zeptáte to psát hned, to asi nebude. A můžete si být jisti, že se věci mají být zapsány dokud nezavoláte hfclose nebo co to je, který pak říká, jo, já Zavírám svůj soubor, to znamená, že jsem radši napsat vše, co jsem nenapsal ještě. To není třeba psát všechno ven dokud se při zavírání souboru, a pak je třeba. Takže to je právě to, co líný - to počká, dokud se to musí stát. Tento - se 51 a přejdete do něj podrobněji, protože OCaml a všechno v 51, vše je rekurze. Nejsou k dispozici žádné iterativní řešení, v podstatě. Všechno je rekurze, a líné vyhodnocování bude důležité pro mnoho okolností kde, pokud jste si líně vyhodnocovat, znamenalo by to - Příkladem je proudy, které jsou nekonečně dlouho. Teoreticky, můžete přemýšlet o přirozených čísel jako proud 1-2-3-4-5-6-7, Takže líně vyhodnocené věci jsou v pořádku. Když řeknu, že chci desáté číslo, pak mohu hodnotit až na desáté číslo. Pokud chci sté číslo, pak mohu hodnotit až po sté číslo. Bez líné vyhodnocování, pak to bude snažit zhodnotit všechna čísla okamžitě. Jste hodnocení nekonečně mnoho čísel, a to prostě není možné. Takže existuje mnoho okolností, kdy líné vyhodnocování je jen nezbytné k získání věci do práce. 

Nyní chceme psát vložku, kde vložka bude Podobně změna v jeho definici. Takže teď je to bool vložka (int value). Budeme změnit na bool vložky (int hodnota, uzel * strom). Jsme vlastně bude měnit, že opět v trochu, uvidíme proč. A pojďme přesunout build_node, jen pro kruci to, nad vložte takže nemáme psát funkce prototyp. Což je náznak, že budete používat build_node v letáku. Dobře. Take minutu za to. Myslím, že jsem zachránil revizi, pokud chcete vytáhnout z toho, nebo alespoň, jsem teď. Chtěl jsem mírný přestávku na přemýšlení o logice vložky, Pokud nemůžete myslet na to. V podstatě, budete jen někdy vkládání na listy. Stejně jako, když jsem vložit 1, pak jsem nevyhnutelně bude vkládání 1 - Budu se změní na černou - Budu se vloží 1 sem. Nebo když jsem vložit 4, chci se vloží 4 sem. Takže bez ohledu na to, co děláte, budete se vloží na list. Jediné, co musíte udělat, je iteraci kácení, až se dostanete do uzlu které by měly být v uzlu rodič, nového uzlu rodič, a potom změnit jeho levé nebo pravé myši, v závislosti na tom, zda to je větší než nebo menší, než je aktuální uzel. Změna tento ukazatel poukázat na svého nového uzlu. Takže iterovat kácení, aby se list bod do nového uzlu. Také si myslím, že o tom, proč zakazuje typ situace před, kde jsem postavil binární strom, kde to bylo správné pokud jste jen podíval na jednoho uzlu, ale 9 byl na levé straně 7, pokud si zopakovali úplně dolů. Tak to je možné v tomto scénáři, protože - přemýšlet o vkládání 9 nebo něco, na prvním uzlu, Jdu vidět 7 a já jsem jen jít doprava. Takže bez ohledu na to, co mám dělat, když mám vložením tím, že půjdete na listu, a k listu pomocí vhodného algoritmu, to bude pro mě nemožné vložit 9 nalevo 7 protože jakmile jsem narazila 7 jsem jít doprava. Má někdo něco začít? [Student] já. Jistě >>. [Student, nesrozumitelným] [Ostatní student, nesrozumitelným] [Bowden] Je to ocenil. Dobře. Chcete vysvětlit? 

[Student] Protože víme, že jsme vkládání nové uzly na konci stromu, I prosmyčkovat stromu iterativně dokud jsem se nedostal k uzlu, která ukazovala na nulu. A pak jsem se rozhodl dát ho buď na pravé straně nebo na levé straně tohoto práva využívají proměnné, to mi řekl, kam to dát. A pak, v podstatě jsem jen dělal, že poslední - že teplota uzel bod na nový uzel, který byl vytvářeného buď na levé straně, nebo na pravé straně, v závislosti na tom, co je hodnota pravý byl. Nakonec jsem nastavit nový uzel hodnoty na hodnotu jeho testování. [Bowden] Dobře, takže vidím jeden problém tady. To je jako 95% cestě tam. Ten problém, který vidím, dobře, někdo jiný vidět problém? Co je okolnost, pod kterou vymanit se z smyčky? [Student] Pokud teplota je null? Jo >>. Tak jak se vymanit ze smyčky, je-li teplota je null. Ale co mám dělat tady? I dereference temp, který je nevyhnutelně null. Takže další věc, kterou musíte udělat, je nejen sledovat, dokud teplota je null, Chcete-li sledovat rodiče za všech okolností. Chceme také, aby uzel * rodiče, myslím, že můžeme mít, že při nulovém na prvním místě. To bude mít podivné chování pro kořen stromu, ale k tomu se dostaneme. Pokud je hodnota vyšší než cokoliv, pak temp = temp pravdu. Ale předtím, než to uděláme, rodič = temp. Nebo se rodiče vždycky stejné teploty? Je to tak? Pokud teplota není null, pak budu pohybovat dolů, bez ohledu na to, do uzlu, pro který temp je rodič. Takže rodiče to bude temp, a pak jsem se přesunout teplota dolů. Nyní teplota je null, ale rodiče poukazuje na rodiče na věc, která je null. Takže tady dole, nechci, aby na pravou míru se rovná 1. Tak jsem se pohyboval napravo, takže pokud P = 1, a myslím, že budete také chtít udělat - pokud přesunete vlevo, kterou chcete nastavit přímo rovna 0. Anebo, pokud jste někdy posune doprava. Takže vpravo = 0. Pokud vpravo = 1, Nyní chceme, aby se mateřský správný ukazatel newnode, jinak bychom chtít, aby mateřské levé ukazatel newnode. Otázky týkající se, že? Dobře. Tak tohle je způsob, jak - no, vlastně, místo toho, co děláme, jsme napůl očekával, můžete použít build_node. A pak, když newnode rovná null, vrátí false. To je to. Nyní, to je to, co jsme očekávali, abys udělal. 

To je to, co zaměstnanci řešení dělat. Nesouhlasím s tím, jak se "správným" způsobem bude o tom ale to je naprosto v pořádku a že to bude fungovat. Jedna věc, která je trochu divné je teď jestliže strom začíná za neplatné, míjíme v nulové stromu. Myslím, že to záleží na tom, jak definovat chování projde v nulové stromu. Řekl bych, že pokud omdlíte v nulové stromu, pak vložením hodnoty do nuly stromu měl prostě vrátit strom, kde jedinou hodnotou je, že jeden uzel. Lidé s tím souhlasíte? Dalo by se, pokud byste chtěli, pokud předáte null stromu a chcete vložit hodnotu do něj, vrátí false. Je na vás, abyste definovat, že. Chcete-li udělat první věc, kterou jsem řekl, a pak - dobře, budete mít potíže dělá, že, protože že by bylo jednodušší, kdyby jsme měli globální ukazatel na věc, ale nemáme, takže pokud strom je null, není nic, co může dělat, že. Můžeme jen vrátí false. Takže budu měnit vložku. My technicky mohl jen změnit toto právo tady, jak to iterace nad věcmi, ale budu měnit vložku, aby se uzel ** strom. Dvoulůžkové ukazatele. Co to znamená? Místo zabývání se ukazatelů na uzly, věc budu se manipulovat, je tento ukazatel. Budu se manipulovat tento ukazatel. Budu se manipulovat ukazatele přímo. To dává smysl, protože, myslím, že o tom se - dobře, teď tento bodů na hodnotu null. To, co chci udělat, je manipulovat tento ukazatel poukázat na NOT NULL. Chci, aby to poukázat na mého nového uzlu. Kdybych jen sledovat ukazatele na mých ukazatelů, pak jsem nemusíte sledovat mateřské ukazatel. Můžu jen sledovat, zda ukazatel ukazuje na null, a pokud ukazatel ukazuje na null, změnit, aby ukazoval na uzel chci. A mohu změnit to, protože mám ukazatel na ukazatel. Pojďme se podívat právě teď. Můžete si skutečně udělat rekurzivně docela snadno. Chceme udělat? Ano, máme. 

Pojďme se podívat, to rekurzivně. Za prvé, to, co je naše základna případ bude? Téměř vždy náš základní scénář, ale ve skutečnosti, to je trochu složitější. První věcí, první, if (tree == NULL) Myslím, že jsme jen tak vrátit false. To se liší od svého stromu bytí null. To je ukazatel na vašem kořenovém ukazatele prozatím null což znamená, že kořenová ukazatel neexistuje. Takže tady dole, když to udělám uzel * - řekněme znovu to. Node * root = NULL, a pak budu volat vložky tím, že dělá něco jako, vložit do 4 & kořene. Tak a kořen, pokud je kořen uzel * pak a kořen bude uzlu **. To je platné. V tomto případě, strom, tady, Strom není null - nebo vložka. Tady. Strom není nula; * strom je nulový, což je v pořádku protože pokud * strom je null, pak jsem si s ním manipulovat se nyní ukazují na to, co chci, aby to odkazovat. Ale pokud strom je null, to znamená, že jsem sem přijel a řekl null. To nedává smysl. Nemůžu nic dělat s tím. Pokud je strom null, vrátí false. Takže jsem v podstatě už řekl, co naše skutečná základna případ je. A co je to, že bude? [Student, nesrozumitelným] [Bowden] Ano. Takže pokud (* tree == NULL). To se týká případu sem kde, pokud má červený ukazatel je ukazatel jsem se zaměřil na, tak, jako bych se zaměřil na tohoto ukazatele, teď jsem se zaměřil na tomto ukazateli. Teď jsem se zaměřil na tomto ukazateli. Takže pokud má červený ukazatel, který je můj uzel **, je vždy - pokud *, můj červený ukazatel, je stále null, to znamená, že jsem v případě, kdy jsem se zaměřením na ukazatel, který ukazuje - to je ukazatel, který patří k listu. Chci změnit tento ukazatel poukázat na můj nový uzel. Vraťte se sem. Můj newnode bude jen uzel * n = build_node (hodnota) pak n, pokud n = NULL, vrátí false. Else chceme změnit to, co se ukazatel je v současné době ukazuje na se nyní ukazují na naší nově postavené uzlu. Můžeme skutečně udělat tady. Místo toho řekl n, říkáme, * tree = pokud * stromu. Všichni pochopili, že? Že jednání s ukazateli na ukazatele, můžeme změnit Null ukazatele poukázat na věci, které chceme, aby odkazovat. To je náš základní scénář. 

Nyní náš recidivy, nebo naše rekurze, bude velmi podobný všem ostatním rekurze jsme dělali. Budeme chtít vložit hodnotu, a teď budu používat ternární znovu, ale to, co je naše podmínka bude? Co je to, co hledáme rozhodnout, zda chceme jít doleva nebo doprava? Pojďme to v samostatných krocích. Pokud (hodnota <), co? [Student] Strom je hodnota? [Bowden] Takže nezapomeňte, že jsem v současné době - [Studenti, nesrozumitelné] [Bowden] Jo, tak tady, řekněme, že tato zelená šipka je příkladem toho, co je v současné době strom, je ukazatel na tento ukazatel. Takže to znamená, že jsem ukazatel na ukazatel na 3. The dereference dvakrát znělo to dobře. Co mám - jak to mám udělat, že? [Student] dereference jednou, a potom proveďte arrow takhle? [Bowden] Tak (* strom) je dereference jednou, -> hodnota se chystá dát mi hodnotu uzlu, který jsem nepřímo ukazuje. Tak jsem si také napsat, že ** tree.value pokud si to přejete. Buď funguje. Pokud tomu tak je, pak chci zavolat vložit s hodnotou. A to, co je moje aktualizován uzel ** bude? Chci jít doleva, takže ** tree.left bude moje levá. A chci, aby ukazatel na té věci tak, že v případě, že levá nakonec je nulový ukazatel, Já ji upravit, aby ukazoval na můj nový uzel. 

A druhý případ může být velmi podobné. Pojďme vlastně udělat, aby mé trojice právě teď. Vložte hodnotu, pokud hodnota <(** strom). Hodnotu. Pak chceme aktualizovat naše ** doleva, else chceme aktualizovat naše ** vpravo. [Student] Znamená to, že se ukazatel na ukazatel? [Bowden] Nezapomeňte, že - ** tree.right je uzel hvězda. [Student, nesrozumitelné] >> Jo. ** Tree.right je jako tento ukazatel, nebo tak něco. Takže tím, že ukazatel na to, že mi dává to, co chci o ukazatel na toho chlapa. [Student] Mohli bychom jít znovu, proč jsme pomocí dvou ukazatelů? [Bowden] Jo. Takže - ne, můžete, a že řešení před Byl to způsob, jak to udělat, aniž by dělali dva ukazatele. Musíte být schopni pochopit pomocí dvou ukazatelů, a to je čistší řešení. Všimněte si také, že to, co se stane, když můj strom - co se stane, když moje kořenem byly null? Co se stane, když udělám tenhle případ tady? Takže uzel * root = NULL, vložte 4 do & kořene. Co je kořen bude po tomhle? [Student, nesrozumitelné] >> Jo. Root hodnota bude 4. Root vlevo bude null, kořen právo bude null. V případě, kdy se nepřešel kořeny adresou, jsme nemohli měnit kořen. V případě, že se strom - kde root je nulový, jsme prostě museli vrátit false. Není nic, co bychom mohli udělat. Nemůžeme vložit uzel do prázdné stromu. Ale teď můžeme, jsme prostě udělat prázdný strom do jednoho uzlu stromu. Který je obvykle očekávaným způsobem, že by to mělo fungovat. 

Dále, což je podstatně kratší než také udržování přehledu o rodiče, a tak budete iterovat úplně dolů. Teď mám rodiče, a já jsem se svou mateřskou vpravo ukazatel na cokoliv. Místo toho, jestli jsme to udělali iterativně, bylo by to stejné nápad s smyčky while. Ale místo toho, aby se museli vypořádat s mým mateřským ukazatelem, místo můj současný ukazatel by věc že jsem se přímo mění na bod na můj nový uzel. Nemám se zabývat, zda je to ukázal na levé straně. Nemám se zabývat, zda je to směřující vpravo. Je to jen, co tento ukazatel je, budu ji nastavit, aby ukazoval na můj nový uzel. Všichni pochopili, jak to funguje? Pokud ne, proč to chceme udělat takhle, ale aspoň, že to funguje jako řešení? [Student] Kde se vrátíme pravda? [Bowden] To je asi tady. Pokud jsme správně vložit, vrátit true. Else, tady dole budeme chtít vrátit bez ohledu vkládání výnosy. 

A co je zvláštního na tomto rekurzivní funkce? Je to tail rekurzivní, tak dlouho, jak jsme kompilovat s nějakou optimalizací, bude si to uvědomit a nikdy se přetečení zásobníku z toho, i když náš strom má výšku 10.000 nebo 10 milionů. [Student, nesrozumitelným] [Bowden] Myslím, že to dělá na Dash - nebo co úroveň optimalizace je vyžadováno pro koncové rekurze má být uznáno. Myslím, že to uznává - GCC a zvonění také mají různý význam pro jejich optimalizaci úrovně. Chci říct, že to DashO 2, pro jistotu, že budou uznávat rekurze ocasu. Ale my - můžete postavit jako například Fibonocci nebo tak něco. Není to snadné otestovat s tím, protože je těžké postavit binární strom, který je tak velký. Ale jo, myslím, že je to DashO 2, že pokud při kompilaci s DashO 2, bude to vypadat pro koncové rekurze a optimalizovat to ven. Pojďme zpět k - vložit to doslova poslední věc, kterou potřebuje. Pojďme se vrátit k vložky sem kde budeme dělat stejnou myšlenku. To bude mít stále nedostatek, že není schopen zcela zvládnout když kořenový sám je nulový, nebo přes vstup je nulový, ale místo toho se zabývá mateřské ukazatel, Pojďme používat stejnou logiku vedení ukazatelů na ukazatele. Pokud zde budeme držet naše uzel ** teď, a nepotřebujeme sledovat přímo už, ale uzel ** cur = & tree. A teď naše, zatímco smyčka bude zároveň * teď se nerovná null. Nemusíte sledovat rodičů už. Nemusíte sledovat pomocí levé a pravé. A já budu říkat temp, protože jsme již používáte temp. Dobře. Takže pokud (hodnota> * temp), pak a (* temp) -> P else temp = & (* temp) -> vlevo. A teď, v tomto okamžiku, po tomto cyklu while, Jen jsem to proto, že je to možná jednodušší přemýšlet o opakované, než rekurzivně, ale po tomto cyklu while, * Teplota je ukazatel chceme změnit. 

Než jsme měli rodiče, a chtěli jsme změnit buď mateřskou doleva nebo rodiče vpravo, ale pokud chceme změnit mateřské právo, pak * teplota je rodič pravdu, a můžeme změnit přímo. Takže tady dole, můžeme udělat * temp = newnode, a to je vše. Takže upozornění, všechno, co jsme dělali v to uzavřít řádky kódu. Aby bylo možné sledovat mateřské ve všech, který je další úsilí. Zde, pokud se jen sledovat ukazatel na ukazatel, a dokonce i kdybychom chtěli zbavit všech těchto složených závorek teď, aby to vypadalo kratší. To je nyní přesně stejné řešení, ale méně řádků kódu. Jakmile začnete rozpoznávat to jako platný řešení, je to také jednodušší uvažovat o než jako, jo, proč mám tento příznak na int vpravo? Co to znamená? Oh, to znamenat, že Pokaždé, když jdu pravdu, musím nastavit, else if I jděte doleva musím nastavit na nulu. Tady, nemám k důvodu o tom, že je to prostě jednodušší myslet. Otázky? [Student, nesrozumitelné] >> Jo. Dobře, takže v poslední bit - Myslím, že jedna rychlá a snadná funkce, kterou můžeme udělat, je, let's - spolu, myslím, vyzkoušet a napsat obsahuje funkce které není jedno, jestli je to binární vyhledávací strom. Tato obsahuje funkce by měla vrátit hodnotu true pokud kdekoli v tomto obecném binárním stromu je hodnota, kterou hledáte. Takže pojďme se nejprve to rekurzivně a pak to uděláme iterativně. Můžeme vlastně jen to dohromady, protože to bude opravdu málo. 

Co je můj základní scénář bude? [Student, nesrozumitelným] [Bowden] Takže pokud (strom == NULL), pak co? [Student] Návrat false. [Bowden] Else, dobře, já nepotřebuju else. Pokud byl můj druhý base-case. [Student] Tree hodnota? Jo >>. Takže pokud (tree-> value == hodnota. Všimněte si, že jsme zpátky do uzlu *, není uzel ** s? Obsahuje nikdy se nebudete muset používat uzlu **, protože jsme se nemění ukazatele. Jsme prostě najet je. Pokud se tak stane, pak chceme vrátit true. Else chceme přejít děti. Takže nemůžeme uvažovat o tom, zda všechno vlevo je méně a všechno vpravo je větší. Takže to, co je naše podmínka bude tady - nebo, co budeme dělat? [Student, nesrozumitelné] >> Jo. Return obsahuje (hodnota, strom-> vlevo) nebo obsahuje (hodnota, strom-> vpravo). A to je vše. A všimněte si, že je nějaký zkrat hodnocení, kde, pokud se stane, že najdete hodnotu v levém stromu, jsme nikdy nebudete muset dívat na pravém stromu. To je celá funkce. Nyní se pojďme to iterativně, který bude méně pěkné. Vezmeme obvyklé start uzlu * cur = strom. Zatímco (teď! = NULL). Rychle bude vidět problém. Pokud teď - tady, jestli se někdy uniknout z tohoto, pak jsme došly věci podívat se na, tak vrátí false. Pokud (teď-> value == hodnota), vrátí true. Takže teď jsme na místě - nevíme, zda chceme jít doleva nebo doprava. Takže libovolně, pojďme odešel. Já jsem samozřejmě běžet do problému, kdy jsem úplně opuštěné všechno - Budu vždy jen kontrolovat levou stranu stromu. Nikdy kontrolovat vše, co je právo dítě nic. Jak mohu tento problém vyřešit? [Student] Musíte sledovat vlevo a vpravo v zásobníku. [Bowden] Jo. Takže pojďme dělat to struct list, uzel * n, a potom uzel ** dál? Myslím si, že funguje dobře. Chceme jít přes levé, nebo let's - tady. Struct = SEZNAM seznam, bude to začne protože na tomto struct seznamu. * List = NULL. Takže to bude náš propojený seznam z podstromů, které jsme přeskočil. Budeme procházet zbylo, ale protože jsme nutně potřebovat vrátit doprava, Budeme držet pravou stranu uvnitř našeho struct seznamu. Pak budeme mít new_list nebo struct, struct list *, new_list = malloc (sizeof (seznam)). Budu ignorovat chyba-kontrolovat, ale měli byste zkontrolovat, jestli je to null. New_list uzel, že to bude ukazovat na - oh, to je důvod, proč jsem chtěl to tady. Bude to poukázat na druhé struct seznamu. To je jen, jak souvisí Seznam prací. To je stejné jako int propojeném seznamu kromě jsme jen nahrazovat int s uzlem *. Je to úplně stejné. Takže new_list, hodnota naší new_list uzlu, bude teď-> klikněte pravým. Hodnota našeho new_list-> next bude náš původní seznam, a pak budeme aktualizovat náš seznam, aby ukazoval na new_list. 

Nyní potřebujeme nějaký způsob tahání věcí, jak jsme projet celý levého podstromu. Teď musíme vytáhnout věci z toho, jako teď je null, nechceme jen vrátit false. Chceme nyní vytáhnout ven na našem novém seznamu. Nejvýhodnějším způsobem, jak to udělat - no, vlastně, je tu několik způsobů, jak to udělat. Každý, kdo má nějaký návrh? Kde bych měl udělat, nebo jak bych měl udělat? Máme jen pár minut, ale nějaké návrhy? Místo toho, aby - jedním způsobem, místo toho, aby náš stav je při, to, co jsme v současné době hledá v není null, místo budeme i nadále pokračovat, dokud náš seznam sám o sobě je null. Takže pokud náš seznam skončí jako bytí null, pak jsme došly věci hledat, prohledávat. Ale to znamená, že první věc, kterou v našem seznamu je jen tak být první uzel. Úplně první věc, kterou bude - jsme již třeba vidět, že. Takže list-> n bude náš strom. list-> next bude null. A teď, když seznam se nerovná null. Cur bude vytáhnout něco z našeho seznamu. Takže teď se chystá na rovné seznam-> n. A pak seznam bude rovné seznam-> n, nebo list-> next. Takže pokud teď hodnota se rovná hodnotě. Nyní můžeme přidat i naši pravou myši a naše levé ukazatel jak dlouho jak oni to není null. Tady dole, myslím, že bychom měli udělat, že na prvním místě. Pokud (teď-> P! = NULL) pak budeme vložit tento uzel do našeho seznamu. Pokud (teď-> vlevo), to je trochu práce navíc, ale to je v pořádku. Pokud (teď-> doleva! = NULL), a budeme vložit doleva do našeho propojeného seznamu, a že by měla být ono. My iteraci - tak dlouho, jak budeme mít něco v našem seznamu, máme další uzel na pohled. Takže se podíváme v tomto uzlu, jsme předem na náš seznam na příští. Pokud tento uzel je hodnota, kterou hledáte, můžeme se vrátit true. Else vložte obě naše levé a pravé podstromy, jak dlouho jak oni to není null, do našeho seznamu takže jsme nevyhnutelně jít přes ně. Takže v případě, že nebyly null, když náš kořen ukazatel upozornil na dvě věci, pak nejprve jsme vytáhli něco tak náš seznam skončí jako bytí null. A pak jsme dali dvě věci zpět, takže teď náš seznam je velikost 2. Pak budeme smyčky zpět a my jen tak vytáhnout, řekněme, levé ukazatel našeho kořenového uzlu. A to si jen dějí, skončíme smyčky nad vším. 

Všimněte si, že to bylo podstatně složitější v rekurzivní řešení. A já jsem řekl: vícekrát že rekurzivní řešení má obvykle mnoho společného s iterativní řešení. Tady je to přesně to, co rekurzivní řešení dělá. Jedinou změnou je, že místo toho, aby implicitně pomocí zásobníku, program zásobník, jako způsob, jak udržet přehled o tom, co uzly stále potřebujete navštívit, Nyní budete muset použít propojeného seznamu. V obou případech se sledování toho, co uzlu je ještě třeba navštívil. V rekurzivní případě, že je to prostě jednodušší, protože zásobník je implementován pro vás jako programu zásobníku. Povšimněte si, že tento spojový seznam, to je zásobník. Ať jsme jen dát na stack je hned to, co budeme vytáhněte zásobník na návštěvu další. Jsme mimo čas, ale na něco zeptat? [Student, nesrozumitelným] [Bowden] Jo. Takže pokud máme propojeného seznamu, proud bude poukázat na toho chlapa, a teď jsme jen zlepšování propojeného seznamu zaměřit se na toho chlapa. Jsme křížení přes propojeného seznamu v tomto řádku. A pak myslím, že bychom měli osvobodit naše propojeného seznamu a podobně jednou před vrací hodnotu true nebo false, musíme iteraci našeho propojeného seznamu a vždy se sem, myslím, pokud bychom teď právo není rovno, přidejte jej, takže teď chceme osvobodit teď, protože, no, my jsme úplně zapomenout na seznamu? Jo. Takže to je to, co chceme dělat. Kde je ukazatel? Cur byl pak - chceme do struct seznam * 10 rovná seznam vedle. Free list, list = temp. A v případě, kdy se vrátí true, je třeba, abychom iteraci po zbytek našeho propojeného seznamu uvolňovat věci. Pěkná věc, o rekurzivní řešení je uvolnění věci prostě znamená objevovat factorings ze zásobníku, který se stane pro vás. Takže jsme šli z něčeho, co to jako 3 řádky těžko think-o kód k něčemu, co je výrazně mnohem více tvrdý-k-si-o řádků kódu. Nějaké další otázky? Dobrá. Jsme v pohodě. Bye! [CS50.TV]