[Powered by Google Translate] [Odjeljak 7: ugodnije] [Rob Bowden] [Sveučilište Harvard] [Ovo je CS50] [CS50.TV] U redu. Dakle, kao što sam rekao u mom e-pošte, ovo će biti binarno stablo intenzivni odjel. No, tu se ne da mnogo pitanja. Tako ćemo pokušati izvući na svako pitanje i ići u bolne detalje svih najboljih načina obavljanja stvari. Dakle, odmah na početku, idemo kroz uzorak crteža binarnih stabala i slično. Dakle, ovdje, "Sjetite se da binarno stablo ima čvorove slične onima povezane liste, osim umjesto jednog pokazivača postoje dva: jedan za lijevi 'dijete' i jedan za pravo 'dijete'. " Dakle binarno stablo je baš kao i povezanog popisa, osim struct će imati dva pokazivača. Tu je trinary stabala, koji će imati tri pokazivače, postoje N-arna stabla, koje samo imaju generički pokazivač da li onda moram malloc biti dovoljno velik da imaju dovoljno upućuje na svim mogućim djece. Dakle binarno stablo jednostavno dogodi da imaju stalan broj dva. Ako želite, možete dati povezanu popis kao predznak stabla, ali ja ne mislim da itko zove to da. "Nacrtaj kutije-i-strelice dijagram binarnog stabla čvor sadrži Nate je omiljeni broj 7, gdje će svako dijete pokazivač je null. " Dakle ipad način. 

To će biti prilično jednostavan. Mi samo ćeš imati čvor, ja ću ga izvući kao trga. I ja ću nacrtati vrijednosti ovdje. Tako je vrijednost će ići ovdje, i onda ovdje ćemo morati lijevu pokazivač na lijevo i desno pokazivač na desnoj strani. I to je jako puno tako konvenciji da ga zovu lijevo i desno, pokazivač imena. Oba će biti nula. To će samo biti nula, i da će samo biti nula. Ok. Dakle, natrag na ovdje. "S povezane popisu, samo mi morali pohraniti pokazivač na prvi čvor u popisu kako bi se sjetiti cijeli povezanog popisa, ili cijeli popis. Isto tako, s drvećem, imamo samo za pohranu pokazivač na jednom čvoru kako bi se sjetiti cijeli stablo. Ovaj čvor je calle je 'korijen' od stabla. Graditi na slici, od prije ili privući novu kao da imate kutije-i-strelice prikazom binarnog stabla s vrijednost 7, a zatim 3 u lijevo, zatim 9 na desnoj strani, a zatim 6 na desno od 3 ". Idemo vidjeti ako ja mogu sjetiti svega toga u mojoj glavi. Dakle, ovo će biti naš korijen ovdje. Mi ćemo imati neki pokazivač negdje, nešto što ćemo nazvati korijen, i to je pokazujući na ovim tipom. Sada bi novi čvor, što imamo, 3 na lijevoj strani? Dakle, novi čvor s tri, i to na početku ističe null. Ja ću samo staviti N. Sada želimo napraviti da ide s lijeve strane 7. Tako ćemo promijeniti ovu pokazivač do sada ukazuju na ovim tipom. I mi isto. Želimo 9 ovamo koji je u početku samo kaže null. Mi ćemo promijeniti ovu pokazivača, pokažite na devet, a sada želimo staviti šest na desnoj 3. Dakle, to će - napraviti šest. A taj čovjek će ukazati postoji. Ok. Dakle, to je sve što od nas traži da učiniti. 

Sada idemo preko neke terminologije. Već smo razgovarali o tome kako je korijen stabla je top-najviše čvor u stablu. Jedan sadrži sedam. Čvorovi na dnu stabla nazivaju se lišće. Svaki čvor koji ima samo null kao svoje djece je list. Dakle, to je moguće, ako je naš binarno stablo je samo jedan čvor, da je stablo list, i to je to. "The 'Visina' od stabla je broj hmelja morate napraviti dobiti od vrha do list ". Mi ćemo ući u, u drugi, razliku između uravnoteženih i neuravnotežena binarnih stabala, ali za sada, ukupna visina ovog stabla Rekao bih da je 3, iako ako računamo broj skokova morate napraviti kako bi se doći do 9, onda je to stvarno samo visina 2. Upravo sada je to neuravnotežena binarno stablo, ali ćemo razgovarali o uravnotežena kad se dobiva biti relevantan. Dakle, sada možemo govoriti o čvorova u stablu u smislu u odnosu na ostale čvorove u stablu. Tako sada imamo roditelje, djecu, braću i sestre, predaka, potomaka. Oni su prilično zdrav razum, što oni znače. Ako pitamo - to je roditelje. Dakle, ono što je roditelj 3? [Studenti] 7. >> Da. Roditelj samo će biti ono što ukazuje na vas. Onda ono što su djeca 7? [Studenti] 3 i 9. >> Da. Obavijest da "djeca" doslovno znači djecu, pa 6 neće primijeniti, jer to je kao unuka. Ali onda ako idemo potomke, tako što su potomci 7? [Studenti] 3, 6 i 9. >> Da. Potomci root čvor će biti sve u drvetu, osim možda korijen čvor sama, ako ne želite uzeti u obzir da je potomak. I konačno, preci, tako da je suprotnom smjeru. Dakle, ono što su preci 6? [Studenti] 3 i 7. >> Da. 9 nije uključena. To je samo izravna linija natrag do korijena će biti vaši preci. 

"Mi kažemo da je binarno stablo je" naredio "da za svaki čvor u stablu, sve svoje potomke na lijevoj strani imaju manje vrijednosti i sve one na desnoj strani imaju veće vrijednosti. Na primjer, stablo iznad naredio, ali to nije jedino moguće naručiti aranžman. " Prije nego što smo dobili na to, naredio binarno stablo je također poznat kao binarni pretraživanje stabla. Ovdje ćemo se dogoditi da se nazivajući ga je naredio binarnog stabla, ali nikada nisam čuo da se zove naredio binarno stablo prije, i na kvizu smo mnogo više vjerojatno da će staviti binarnog stabla pretraživanja. Oni su jedna te ista, i to je važno da prepoznaju razliku između binarnog stabla i binarnog stabla pretraživanja. Binarno stablo je samo stablo koje ukazuje na dvije stvari. Svaki čvor ukazuje na dvije stvari. Nema razmišljanje o vrijednostima koje to ukazuje na. Tako se sviđa ovdje, jer je binarno stablo pretraživanja, znamo da ako idemo lijevo od 7, onda sve vrijednosti koje smo eventualno mogu doći odlaskom lijevo od sedam moraju biti manje od sedam. Primijetit ćete da su sve vrijednosti manje od 7 su tri i šest. Oni su svi s lijeve strane 7. Ako idemo na desnoj 7, sve mora biti veći od sedam, pa 9 je na desnoj strani 7, tako da smo dobri. To nije slučaj za binarno stablo, za redovite binarnog stabla možemo samo imati tri na vrhu, sedam na lijevoj strani, 9 na lijevoj 7; nema naručivanje vrijednosti bilo koje vrste. Sada, mi zapravo neće to učiniti, jer to je zamorno i nepotrebno, ali "pokušati izvući što više naručili stabala kao što možete zamisliti koristeći brojeve 7, 3, 9, i 6. Koliko različita rješenja postoje? Koja je visina svakog jedan? " 

Mi ćemo napraviti par, ali glavna ideja je, ovo je ni na koji način jedinstveni prikaz binarnog stabla sadrži ove vrijednosti. Sve što trebate je neki binarno stablo koje sadrži 7, 3, 6 i 9. Drugi mogući vrijedi jedan će biti korijen je 3, idite na lijevo, a to je 6, idite na lijevo, a to je 7, idite na lijevo, a to je 9. To je savršeno valjana binarno stablo pretraživanja. To nije vrlo korisno, jer to je isto kao povezane liste i sve ove naputke su samo null. Ali, to je valjan stablo. Da? [Studentski] Zar vrijednosti moraju biti veći na desnoj strani? Ili je to -? >> To sam trebao ići na drugi način. Tu je i - da, ajmo prebaciti da. 9, 7, 6, 3. Dobar ulov. Ona još uvijek ima da slušaju ono što traži binarno stablo je trebalo učiniti. Dakle, sve na lijevoj strani mora biti manje od bilo kojeg čvora. Mi samo mogao pomaknuti, recimo, ovaj šest i staviti ga ovdje. Ne, ne možemo. Zašto sam zadržati taj događaj? Učinimo - ovdje je 6, ovdje je 7, 6 bodova u tri. To je još uvijek vrijedi binarno stablo pretraživanja. Što je krivo, ako sam - ajmo vidjeti ako ja mogu doći do dogovora. Da, u redu. Dakle, ono što je krivo s ovom stablu? Valjda sam već dao naslutiti da nešto nije u redu s njim. Zašto sam zadržati taj događaj? Ok. Ovo izgleda razumno. Ako gledamo na svakom čvoru, kao i sedam, a zatim s lijeve strane 7 je tri. Dakle, imamo tri, stvar s desne strane 3 je šest. A ako pogledate 6, stvar na pravo 6 je devet. Pa zašto je to ne vrijedi binarno pretraživanje stablo? [Studenti] 9 je još uvijek na lijevoj 7. >> Da. To mora biti istina da su sve vrijednosti koje eventualno mogu doći tako da odete na lijevoj sedam manje od sedam. Ako idemo lijevo od sedam, možemo doći do tri, a mi još uvijek može doći do 6, još uvijek možemo doći do 9, ali nakon što je otišao manje od 7, ne bismo trebali biti u mogućnosti doći do broja koji je veći od 7. Dakle, to nije valjan binarno stablo pretraživanja. 

Moj brat je zapravo imao intervju pitanje da je u osnovi to, samo kod se nešto kako bismo provjerili da li je stablo binarno pretraživanje stablo, i tako prva stvar koju je učinio bila samo provjeriti ako je lijevo i desno su točne, a zatim ponoviti tamo dolje. No, ne možete samo to učiniti, morate pratiti činjenice da je sada da sam otišao lijevo od 7, Sve u ovom podstablo mora biti manji od sedam. Ispravan algoritam treba pratiti od granica koje su vrijednosti eventualno može pasti u. Nećemo proći kroz sve njih. Tu je lijepo ponavljanje odnos, iako nismo došli do njih, ili nećemo doći do onih, definiranje koliko ima zapravo jesu. Dakle, tu su 14 od njih. Ideja o tome kako bi to matematički je kao, možete odabrati bilo ni jedan da se korijen čvor, i onda ako sam pokupiti 7 biti korijen čvor, zatim tu su, recimo, neki brojevi koji mogu ići biti moj lijevi čvor, a tu su i neki brojevi koji mogu biti moje pravo čvor, ali ako sam n ukupan broj, onda je iznos koji se može ići na lijevo uvećan za iznos koji se može ići na pravo je n - 1. Dakle, od preostalih brojeva, oni moraju biti u mogućnosti otići ni lijevo ili desno. Čini se da je teško, ako sam stavio 3 prvi onda sve mora ići na lijevoj strani, ali ako sam stavio 7, onda se neke stvari mogu ići na lijevo i neke stvari mogu ići desno. I '3 prvi 'Mislio sam sve što se može ići desno. To je stvarno, samo morate razmišljati o tome što, koliko stvari mogu ići na sljedeću razinu od stabla. I to dolazi od biti 14, ili možete izvući sve od njih, i onda ćete dobiti 14. 

Vraćajući se ovdje, "Naredio binarni stabla su kul jer možemo tražiti kroz njih na vrlo sličan način na potrazi preko sortirani niz. Da biste to učinili, možemo početi u korijenu i rade svoj put prema dolje stablo prema lišća, provjeru Svaki čvor je vrijednosti protiv vrijednosti smo u potrazi za. Ako je trenutni čvora vrijednost manja od vrijednosti tražimo, idete pokraj čvora pravo djeteta. Inače, idete na čvor lijevog djeteta. U nekom trenutku, ili će pronaći vrijednost koju tražite, ili ćete pokrenuti u null, pokazuje vrijednost nije u stablu. " Moram ponovno iscrtavanje stablo smo imali prije, da ću uzeti drugi. No, želimo li pogledati 6, 10, i 1 u stablo. Dakle, ono što je bilo, 7, 9, 3, 6. Ok. Brojevi koje žele izgledati gore, želimo gledati 6. Kako to algoritam rad? Pa, mi također imaju neke root pokazivač na našem stablu. I mi bi ići na korijen i reći, je ta vrijednost jednaka vrijednosti smo u potrazi za? Dakle, mi smo u potrazi za šest, tako da to nije jednaka. Tako smo zadržati ide, a sada možemo reći, u redu, tako da je manje od šest sedam. Znači li to da želimo ići lijevo, ili ne želimo ići na pravo? [Studentski] Left. >> Da. To je znatno lakše, sve što morate učiniti je izvući jedan mogući čvor stabla i onda nemojte - umjesto da pokušavate misliti u vašoj glavi, ok, ako je manje, moram ići lijevo ili ići pravo, samo gleda na ovoj slici, to je vrlo jasno da moram ići lijevo ako je to čvor je veća od vrijednosti da sam u potrazi za. Dakle, idete na lijevoj strani, a sada sam na tri. Želim - 3 je manje od vrijednosti tražim, što je šest. Tako smo ići na pravo, a sada sam završiti na šest, koja je vrijednost tražim, pa sam se vratiti istinito. Sljedeći vrijednost ću tražiti je 10. Ok. Dakle, 10, sada se ide - odsječen da - će slijediti korijen. Sada, 10 će biti veći od sedam, pa želim gledati na desnoj strani. Ja ću doći ovamo, 10 će biti veći od 9, pa ću žele izgledati desno. Ja dolazim ovamo, ali ovdje sada sam na null. Što trebam učiniti ako sam pogodio null? [Studentski] Povratak lažno? >> Da. Nisam našao 10. 1 će biti gotovo identičan slučaj, osim to samo će biti zrcaljeno, umjesto u potrazi dolje na desnoj strani, ja ću pogledati dolje lijevu stranu. 

Sada mislim da smo zapravo doći do koda. Evo gdje - otvaranje CS50 aparat i navigaciju svoj put tamo, ali također možete samo to učiniti u prostoru. To je vjerojatno idealno to učiniti u prostoru, jer možemo raditi u prostoru. "Prvo ćemo trebati novi tip definiciju za binarnog stabla čvor koji sadrži int vrijednosti. Koristeći predloženi typedef nastavku, stvoriti novu definiciju tipa za čvor u binarno stablo. Ako zapnete. . . "Bla, bla, bla. Ok. Dakle, neka je stavi predloženi ovdje, typedef struct čvor, a čvor. Da, u redu. Dakle, ono što su polja idemo da želite u našoj čvoru? [Studentski] Int, a zatim dvije pokazivače? >> Int vrijednost, dva pokazivače? Kako pisati naputke? [Studentski] struct. >> Ja bi povećali u. Da, tako struct node * lijevo, i rekonstruirati čvor * desno. I zapamtite raspravu iz prošlog vremena, da to nema smisla, to nema smisla, ovo nema smisla. Morate sve tamo kako bi se definirati ovaj rekurzivni struct. Ok, tako da je ono što naša stablo će izgledati. Ako nismo trinary stablo, onda čvor može izgledati B1, B2, struct node * B3, gdje je b grana - zapravo, ja sam više čuo je lijevo, sredina, desno, ali bez obzira. Mi samo stalo binarnom, pa desno, lijevo. "Sada proglasiti globalnu varijablu * čvor za korijen stabla." Pa nećemo to učiniti. Da bi se stvari malo teže i više generalizirati, nećemo imati globalnu varijablu čvor. Umjesto toga, u glavnom ćemo proglasiti sve naše čvora stvari, a to znači da u nastavku, kada smo se početi prikazivati Sadrži naša funkcija i naša umetak funkcija, umjesto naših sadrži samo djeluju pomoću ovog globalnog čvora varijablu, idemo da se to uzeti kao argument stablo koje želimo da obraditi. Nakon što je globalnu varijablu je trebao kako bi što lakše. Mi ćemo napraviti stvari teže. Sada uzeti minutu ili tako da se samo napraviti ovu vrstu stvar, gdje unutar glavna želite stvoriti ovo drvo, i to je sve što želim učiniti. Pokušajte i izgraditi ovo drvo u svom glavnom funkciji. 

Ok. Dakle, ne morate čak ni da su izgrađene stablo, cijeli put još. No, svatko ima nešto što sam mogao podići pokazuju kako bi se moglo početi gradnju takvog stabla? [Studentski] Nečiji lupanje, pokušava izaći. [Bowden] Svatko ugodno sa svojim stabla gradnje? [Studentski] Naravno. To nije učinjeno. >> To je u redu. Mi samo možemo završiti - oh, mogu li ga spasiti? Hura. Dakle, ovdje imamo - oh, ja sam malo odsječen. Jesam li ja zumirana u? Povećavanje, pomaknite se. >> Imam pitanje. >> Da? [Studentski] Kada definirate struct, su stvari poput inicijalizirane na ništa? [Bowden] No >> Ok. Dakle, ti bi da inicijalizirati - [Bowden] No Kada definirate, ili kada se proglasi struct, to nije inicijaliziran po defaultu, to je baš kao ako proglasi int. To je točno istu stvar. To je kao da svaki od njegovih pojedinačnih polja može imati smeća vrijednost u tome. >> I to je moguće definirati - ili proglasiti struct na način da se to čini ih inicijalizirati? [Bowden] Da. Dakle, prečac inicijalizacije sintaksa će izgledati - Postoje dva načina možemo to učiniti. Mislim da bismo trebali prevesti ga kako bi bili sigurni zveka to čini. Redoslijed argumenata koji dolazi u struct, ste stavili kao bi argumenata unutar tih vitičastih zagrada. Dakle, ako želite da ga inicijalizirati do 9 i lijevo onda se ništavnim i pravo biti nula, to će biti 9, null, null. Alternativa je, a urednik ne sviđa ovaj sintaksu, i da misli da ja želim novi blok, ali alternativa je nešto poput - ovdje, ja ću ga staviti u novi redak. Vi izričito ne može reći, zaboravila sam točno sintaksu. Tako možete i eksplicitno ih rješavati po imenu, i recimo, . C, ili. Vrijednost = 9,. Lijevo = NULL. Ja sam guessing ove potrebu da se zarezi. . Pravo = NULL, tako da je ovo način da se ne zapravo treba znati redoslijed struct, i kada ste čitajući ovo, to je puno precizniji o čemu je vrijednost je se inicijaliziraju. 

To se događa da se jedna od stvari koje - tako, za najveći dio, C + + je nadskup C. Možete uzeti C kod, premjestiti ga na C + +, i to bi trebalo sastaviti. To je jedna od stvari koje C + + ne podržavaju, tako da ljudi imaju tendenciju da ne to učiniti. Ja ne znam da li je to jedini razlog ljudi imaju tendenciju da ne to učiniti, ali slučaj gdje sam trebao koristiti ga potrebno za rad s C + + i tako nisam mogao koristiti ovu. Još jedan primjer nešto što ne raditi s C + + je kako malloc vraća void * "," tehnički, ali samo mogao reći char * x = malloc štogod, i ona će automatski biti bačeni na char *. To automatski baci se ne događa u C + +. To ne bi sastaviti, a vi bi eksplicitno treba reći char *, malloc, što god, da ga baci na char *. Ne postoje mnoge stvari koje C i C + + ne slažu o, ali one su dvije. Dakle, mi ćemo ići s tom sintaksom. Ali čak i ako mi ne ide s tom sintaksom, što je - može biti krivo s tim? [Studentski] Ne trebam ga dereference? >> Da. Sjetite se da strelica ima implicitnu dereference, pa kad smo tek bave struct, želimo koristiti. dobiti na polju unutrašnjosti struct. A jedini put kad smo koristiti strelicu kada želimo napraviti - dobro, strelica je ekvivalent - to je ono što bi značilo, ako sam koristiti strelicu. Sve strelica znači da je, dereference ovo, sad sam na struct, a ja mogu dobiti polje. Ili se polje izravno ili dereference i dobiti polje - Pretpostavljam da je ovo trebala biti vrijednost. No, ovdje imam posla sa samo struct, a ne pokazivač na struct, i tako ja ne mogu koristiti strelicu. No, ova vrsta stvar možemo učiniti za sve čvorove. Bože moj. Ovo je 6, 7, i 3. Tada možemo postaviti grane u našoj stabla, možemo imati 7 - možemo imati, njegova lijeva treba ukazati na tri. Pa kako ćemo to učiniti? [Studenti, nerazumljivo] >> Da. Adresu node3, a ako nisu imali adresu, onda to jednostavno ne bi sastaviti. No, sjetite se da su to upućuje na sljedeću čvorova. Pravo treba ukazati na devet, i 3 treba ukazati na pravo na šest. Mislim da je to sve skupa. Sve primjedbe ili pitanja? [Student, nerazumljivo] Korijen će biti sedam. Mi samo možemo reći čvor * ptr = ili korijena, = & node7. 

Za naše potrebe, mi ćemo se baviti umetkom, tako da ćemo želite napisati funkciju za umetanje u ovom binarnom stablu i umetanje neizbježno će se zvati malloc stvoriti novi čvor za ovog stabla. Dakle, stvari će se dobiti messy s činjenicom da su neki čvorovi su trenutno na stog i ostali čvorovi će završiti na hrpi kad smo ih umetnuti. To je savršeno valjana, ali jedini razlog mi smo u mogućnosti to učiniti na stog je zato što je tako neprirodan primjer da znamo stablo je trebao biti izgrađen kao 7, 3, 6, 9. Ako nismo, onda ne bi trebala malloc na prvom mjestu. Kao što ćemo vidjeti malo kasnije, trebali bismo se malloc'ing. Upravo sada je savršeno razumna staviti na stog, ali ajmo to promijeniti na malloc provedbu. Dakle, svaki od njih sada će biti nešto poput čvor * node9 = malloc (sizeof (čvor)). A sad ćemo morati učiniti naš ček. ako (node9 == NULL) - Nisam želio da - povratak jednog, a onda možemo učiniti node9-> jer sada je pokazivač, vrijednost = 6, node9-> lijevo = NULL, node9-> Pravo = NULL, a mi ćemo to morati učiniti da za svaki od tih čvorova. Dakle, umjesto, ajmo ga staviti unutar posebnog funkcije. Nazovimo to čvor * build_node, i to je nešto slično API pružamo za Huffman ovo kodiranje. Mi vam dati inicijalizatora funkcije za drvo i dekonstrukcionista "funkcije" Za one stabala i isti za šume. 

Dakle, ovdje ćemo imati inicijalizatora funkciju samo izgraditi čvor za nas. I to će izgledati prilično točno ovako. I čak ću biti lijeni i ne promijeniti ime varijable, iako node9 nema smisla više. Oh, pretpostavljam node9 je vrijednost ne bi trebala biti šest. Sada se možemo vratiti node9. I ovdje bi se trebali vratiti null. Svatko se slažu na toj graditi-čvor funkciji? Dakle, sada možemo samo pozvati da za izgradnju bilo čvor s određenom vrijednosti i null pokazivače. Sada možemo nazvati, možemo napraviti čvor * node9 = build_node (9). I nemojmo učiniti. . . 6, 3, 7, 6, 3, 7. A sada želimo postaviti iste upućuje, osim sada je sve već u smislu upućuje tako da više ne trebate adresu. Ok. Dakle, ono što je zadnja stvar koju želim učiniti? Tu je pogreška-provjera da ja ne radim. Što znači graditi čvor povratak? [Student, nerazumljivo] >> Da. Ako malloc nije uspio, to će se vratiti null. Tako ću lijeno staviti ga ovdje umjesto da radiš što je uvjet za svaki. Ako (node9 == NULL, ili - još jednostavnije, to je ekvivalent samo ako ne node9. Dakle, ako ne node9, ili ne node6, ili ne node3, ili ne node7, vratiti jedan. Možda bismo trebali ispisati malloc nije uspio, ili tako nešto. [Studentski] Je lažno jednaka null, kao i? [Bowden] Bilo nula vrijednost je false. Dakle, null je nula vrijednost. Zero je nula vrijednost. Lažno je nula vrijednost. Bilo - prilično mnogo samo dva nula vrijednosti su nula i nula, lažno je samo mljeveno meso definira kao nula. To vrijedi i ako ne tvrdimo globalnu varijablu. Ako smo imali korijen čvor * ovdje, zatim - Lijepo je stvar o globalnim varijablama je da oni uvijek imaju početnu vrijednost. To nije točno funkcija, kako unutar ovdje, ako imamo, kao što je, čvor * ili čvor x. Mi nemamo pojma što x.value, x.whatever, ili bismo ih mogli ispisati i oni mogli biti proizvoljna. To nije istina globalnih varijabli. Dakle, čvor korijen ili čvor x. Po defaultu, sve što je globalna, ako ne i eksplicitno inicijalizirana na neke vrijednosti, ima nultu vrijednost kao vrijednost. Dakle, ovdje, čvor korijen *, ne izričito inicijalizirati na ništa, tako da je njegova vrijednost zadana će biti nula, što je nula vrijednost upućuje. Zadana vrijednost x. će značiti da x.value je nula, x.left null, a x.right je null. Dakle, budući da je rekonstruirati sve poljima struct će biti nula vrijednosti. Mi ne trebamo koristiti da se ovdje, ipak. [Studentski] U tvorevina su drugačiji od ostalih varijabli, a ostale varijable smeće vrijednosti, to su nule? [Bowden] Druge vrijednosti previše. Tako je u X, X će biti nula. Ako je na globalnom okviru, ona ima početnu vrijednost. >> Ok. [Bowden] Ili je početna vrijednost koju je dao ga ili nula. Mislim da se brine o svemu tome. 

Ok. Dakle, sljedeći dio pitanja pita, "Sada želimo napisati funkciju pod nazivom sadrži s prototip bool sadrži int vrijednosti. " Nećemo učiniti bool sadrži int vrijednost. Naš prototip će izgledati bool sadrži (int vrijednost. I onda mi također idemo proći ga stablo da bi trebao biti ček vidjeti ako ima tu vrijednost. Dakle, čvor * stablo). Ok. A onda ga možemo nazvati s nešto poput, možda ćemo želite printf ili nešto. Sadrži 6, naš korijen. To bi trebalo vratiti jedan, ili istinske, a sadrži pet korijen trebao vratiti false. Tako se drugi provesti ovu. Možete to učiniti bilo iterativno ili rekurzivno. Lijepo je stvar o načinu smo postavili stvari je da ona sama posuđuje našem rekurzivni rješenje puno lakše od globalne varijable način učinio. Jer ako imamo samo sadrži int vrijednost, onda nemamo način recursing dolje subtrees. Mi bi imati odvojenu pomagač funkcije koje recurses dolje subtrees za nas. No, budući da smo promijenili da se stablo kao argument, kojima bi uvijek bili na prvom mjestu, Sada možemo recurse lakše. Dakle, iterativni ili rekurzivna, mi ćemo ići preko oba, ali vidjet ćemo da rekurzivnih završava gore bitak prilično jednostavan. Ok. Ima li netko nešto možemo raditi s? 

[Studentski] Imam rješenje iterativnog. >> Redu, iterativni. Ok, ovo izgleda dobro. Dakle, želite nas prošetati kroz nju? [Studentski] Naravno. Tako sam postaviti temp varijablu da biste dobili prvi čvor stabla. A onda sam provući kroz dok temperatura ne jednak null, pa dok je još na stablu, pretpostavljam. A ako je vrijednost jednaka vrijednosti koje temp pokazuje da, tada vraća tu vrijednost. Inače, on provjerava ako je na desnoj strani ili lijevoj strani. Ako ste ikada dobili situaciju u kojoj nema više stablo, zatim se vraća - to izlazi iz petlje i false. [Bowden] Ok. Tako da se čini dobro. Svatko ima bilo kakve komentare o svemu? Nemam ispravnosti komentare na sve. Jedna stvar koju možemo učiniti je taj tip. Oh, to će ići malo dužeg. Ja ću popraviti taj gore. Ok. 

Svatko treba imati na umu kako je trojni radi. Tu svakako su kvizove u prošlosti da vam dati funkciju s ternarni operatora, i reći, prevesti ovo, učiniti nešto da se ne koristi ternarni. Dakle, ovo je vrlo čest slučaj kada bih misliti da koristite ternarni, gdje ako neki uvjet postaviti varijablu na nešto, drugdje postaviti tu istu varijablu na nešto drugo. To je nešto što je vrlo često se može pretvoriti u takvim stvarima gdje postaviti tu varijablu na to - ili, dobro, je li to istina? Onda je ovo, drugi je ovo. [Studentski] Prvi je ako je istina, zar ne? [Bowden] Aha. Način na koji sam ga uvijek pročitati je, temperatura je jednaka vrijednost veću od vrijednosti temp, onda je to, ostalo je ovo. To je molba pitanje. Je li to veća? Zatim napraviti prvu stvar. Inače to druga stvar. Ja gotovo uvijek - debelo crijevo, ja samo - u mojoj glavi, čitao sam kao drugi. 

Se bilo tko imati rekurzivni rješenje? Ok. Ovaj ćemo se - to je već mogao biti velik, ali ćemo to učiniti još boljim. To je ljepušan velik dio isti točan ideja. To je samo, dobro, ne želite da objasni? [Studentski] Naravno. Dakle, mi smo sigurni da stablo nije null prvi, jer ako je drvo null onda će to povratak false, jer nismo ga pronašli. I ako još uvijek postoji stablo, idemo u - prvo provjerite je li vrijednost je trenutni čvor. Povratak vrijedi ako je to, a ako ne možemo recurse na lijevo ili desno. Zvuči primjereno? >> Mm-hmm. (Ugovor) Dakle, primijetite da je to gotovo - strukturno vrlo sličan iterativnog rješenja. To je samo da umjesto recursing, imali smo while petlja. A osnovni slučaj ovdje, gdje stabla ne jednak null bio uvjet pod kojim smo izbio while petlje. Oni su vrlo slični. No, idemo uzeti ovaj jedan korak dalje. Sada, mi radimo istu stvar ovdje. Obavijest smo vraća istu stvar u oba ova linija, osim za jedan argument je drugačiji. Tako ćemo napraviti da u trodjelna. Udario sam opciju nešto, a to je simbol. Ok. Tako ćemo se vratiti sadrži toga. Ovaj je uzimajući biti više redaka, dobro, zumirani je. Obično, kao stilsku stvar, ne mislim da mnogo ljudi staviti razmak nakon strelice, ali mislim da, ako ste dosljedni, to je u redu. Ako je vrijednost manja od stabla vrijednosti, želimo recurse na stabla lijeve strane, drugo želimo recurse na stabla desno. Dakle, to je bio jedan korak izrade ovo izgleda manji. Korak dva izrade ovo izgleda manji - možemo odvojiti to više redaka. Ok. Korak dva, čineći ga izgledati manje je ovdje, tako da povratna vrijednost jednaka stablo vrijednost, ili sadrži bilo što. 

Ovo je važna stvar. Nisam siguran da li je on rekao da eksplicitno u razredu, ali to se zove kratki spoj procjena. Ideja je vrijednost == stablo vrijednost. Ako je to istina, onda je to istina, a mi želimo da 'ili' da sa što je više ovdje. Dakle, čak i bez razmišljanja o svemu što je ovdje, što je cijeli izraz će vratiti? [Studentski] Istina? >> Da, jer vrijedi ništa, or'd - ili istina or'd sa sve što je nužno istinito. Dakle, čim smo vidjeli povratnu vrijednost = stablo vrijednost, samo mi ide na povratak istina. Ni ide recurse dalje sadrži niz liniju. Možemo uzeti ovaj jedan korak dalje. Povratak stablo ne jednak null i sve to. To je to jedna linija funkcija. Ovo je također primjer kratkog spoja evaluacije. No, sada je ista ideja - umjesto - pa ako stablo nije jednak null - ili, dobro, ako stablo ne jednak null, koji je loš slučaj, ako stablo jednaka null, zatim prvi uvjet će biti lažni. Dakle, lažni anded s ničim će biti što? [Studentski] Netočno. >> Da. Ovo je druga polovica kratkog spoja evaluacije, gdje ako stablo ne jednaka null, onda mi se ne ide na čak ići - ili ako stablo ne jednak null, onda mi se ne ide raditi vrijednost == stablo vrijednosti. Mi samo ćeš odmah vratiti false. Koja je važno, jer ako to nije kratki spoj ocijeniti, onda ako stablo ne jednak null, ovaj drugi uvjet će SEG krivnjom, jer stablo-> vrijednost dereferencing null. Dakle, to je to. Može li se to - pomak jedanput. To je vrlo uobičajena stvar, također, ne čineći ovu jednu liniju s tim, ali to je uobičajena stvar u uvjetima, možda ne baš ovdje, ali ako (stablo! = NULL, i drvo-> vrijednost == vrijednost), što god. To je vrlo česta pojava, gdje umjesto razbiti to u dvije oklijevanja, gdje se sviđa, je stablo null? Ok, to nije null, tako da sada je stablo vrijednost jednaka vrijednosti? Učinite to. Umjesto toga, ovaj uvjet, to se nikada neće SEG kvar jer će izbiti ako se to dogodi biti nula. Pa, mislim da ako je vaš stablo je potpuno nevažeći pokazivač, to još uvijek može SEG kvar, ali to se ne može pokvariti ako SEG stablo je null. Ako je to bila nula, to bi izbiti prije nego li ikada dereferenced pokazivač na prvom mjestu. [Studentski] Je li ovo zove lijeni procjena? 

[Bowden] Lazy procjena je zasebna stvar. Lazy procjena je više kao što tražiti vrijednosti, pitate se izračunati vrijednost, vrsta, ali ne treba odmah. Dakle, dok se zapravo treba, to nije ocijenjen. To nije točno istu stvar, ali u Huffman pset, on kaže da smo "lijeno" pisati. Razlog činimo to je zato što mi zapravo puferski WRITE - ne želimo pisati pojedinačne bitove na vrijeme, ili pojedini bajtova u isto vrijeme, mi umjesto žele dobiti komad bajtova. Onda kada imamo komad bajtova, onda ćemo ga napisati. Iako ga pitati za pisanje - i fwrite i fread učiniti istu vrstu stvari. Oni tampon vaš čita i piše. Iako ga pitati pisati odmah, vjerojatno neće. I ne možete biti sigurni da su stvari će biti napisano dok vi zovete hfclose ili što god to je, koji je tada, kaže, ok, ja sam zatvaranja moj dosje, to znači da sam bolje bih napisati sve nisam pisao još. To ne treba pisati sve iz dok se zatvara datoteku, a zatim ga treba. Dakle, to je upravo ono što lijeni - to čeka dok ne mora dogoditi. Ovo - uzeti 51, a vi ćete ići u nju u više detalja, jer OCaml i sve u 51, sve je rekurzije. Nema iterativnog rješenja, osnovi. Sve je rekurzije, a pasivno vrednovanje će biti važno za puno okolnostima gdje, ako nije lijeno ocijeniti, to bi značilo - Primjer je potoci, koji su beskrajno dugo. U teoriji, možete misliti prirodnih brojeva kao tok 1-2-3-4-5-6-7, Dakle lijeno ocjenjivali stvari su u redu. Ako kažem hoću deseti broj, onda ja mogu procijeniti do desetog broja. Ako želim stoti broj, onda ja mogu procijeniti do stote broju. Bez lijen ocjenu, onda će to pokušati procijeniti sve brojeve odmah. Ti si ocjenu beskonačno mnogo brojeva, a to jednostavno nije moguće. Dakle, postoji mnogo okolnosti u kojima pasivno vrednovanje je samo bitno da dobivanje stvari raditi. 

Sada želimo pisati umetak gdje umetak će biti slično mijenjaju u svojoj definiciji. Dakle, sada je bool umetak (int vrijednost). Mi ćemo to promijeniti za bool umetkom (int vrijednost, čvor * stablo). Mi zapravo će se promijeniti da opet malo, pa ćemo vidjeti zašto. I krenimo build_node, samo za pakao od toga, iznad umetnite tako da ne moram napisati funkcije prototip. Koji je nagovještaja da ste idući u biti koristeći build_node u privitku. Ok. Uzmi trenutak za to. Mislim da sam spasio reviziju ako želite izvući iz toga, ili, barem, ja sam sada. Htio sam blagi pauzu za razmišljanje o logici umetkom, ako ne možete misliti o tome. Uglavnom, samo će ikada biti umetanja na lišću. Kao, ako sam umetnuti jedan, onda sam neizbježno ću se umetanjem 1 - Ja ću se promijeniti u crno - Ja ću biti umetanjem jednog ovamo. Ili, ako sam umetnuti 4, želim da se umetanjem 4 ovamo. Dakle, bez obzira na ono što radite, vi ćete biti ugurate list. Sve što morate učiniti je ponoviti niz drvo dok ne dođete do čvora koji bi trebao biti čvor roditelj, novog čvora roditelj, i onda promijeniti svoju lijevu ili desnu pokazivač, ovisno o tome to je veći ili manji od trenutnog čvora. Promjena taj pokazivač ukazati na novi čvor. Tako ponoviti niz drvo, napraviti list točku na novi čvor. Također razmišljati o tome zašto da zabranjuje vrstu situacije prije, gdje sam konstruirao binarnog stabla gdje je bio ispravan ako je samo gledao u jednom čvoru, ali 9 je bio na lijevoj 7 ako ponovljena dolje skroz. Tako da je nemoguće u ovom scenariju, jer - razmišljam o umetanju 9 ili tako nešto, na prvi čvor, Idem vidjeti 7, a ja samo idem na desno. Dakle, bez obzira što mi je činiti, ako sam umetanjem odlaskom na list, i na list pomoću odgovarajućeg algoritma, to će biti nemoguće za mene za umetanje 9 na lijevoj 7 jer čim sam pogodio sedam ću ići na pravo. Ima li netko nešto za početak s? [Studentski] ja. >> Naravno. [Student, nerazumljivo] [Ostalo učenik, nerazumljivo] [Bowden] To je poštovati. Ok. Želite li objasniti? 

[Studentski] Budući da znamo da su umetanja novi čvorovi na kraju stabla, Ja provući kroz stabla iterativno dok sam na čvoru koji je naglasio na nulu. I onda sam odlučio staviti ga bilo na desnoj strani ili lijevoj strani Korištenjem ove pravu varijablu, ona mi je rekla gdje da ga stavi. A onda, u suštini, samo sam napravio da je zadnji - da točka temperatura čvor za novi čvor koji je stvara, ili na lijevoj strani ili na desnoj strani, ovisno o tome što je vrijednost upravo bio. Konačno, sam postaviti novi čvor vrijednost na vrijednost njegovog ispitivanja. [Bowden] Ok, tako da vidim jedan problem ovdje. To je kao 95% na putu tamo. Onaj problem koji ja vidim, dobro, ne bilo tko drugi vidi problem? Što je okolnost pod kojima su break izvan petlje? [Studentski] Ako temperatura je nula? >> Da. Pa kako se probiti izvan petlje je ako temperatura je nula. Ali, što da radim ovdje? Ja dereference temp, što je neizbježno null. Dakle, druga stvar koju trebate učiniti je ne samo pratiti dok temperatura je nula, Želite li pratiti od roditelja u svim vremenima. Također želimo roditelj čvor *, mislim da možemo zadržati na null na prvom mjestu. To će imati čudan ponašanje za korijen stabla, ali mi ćemo doći do toga. Ako je vrijednost veća od god, onda temp = temperatura u pravu. No, prije nego što smo to učiniti, roditelj = temp. Ili su roditelji uvijek ide na jednakoj temp? Je li to tako? Ako temperatura nije null, onda ću za kretanje prema dolje, bez obzira na sve, na čvoru za koje temp je roditelj. Dakle, roditelj će biti temp, a onda sam se presele temp dolje. Sada temperatura je nula, ali roditelj ukazuje na roditelju stvar koja je nula. Dakle, ovdje dolje, ne želim postaviti pravo jednak jedan. Tako sam se preselio u pravu, pa ako desno = 1, i mislim da i vi želite učiniti - ako premjestiti na lijevoj strani, želite postaviti pravo jednaka 0. Inače, ako ste ikada premjestiti na desno. Dakle, pravo = 0. Ako desnoj = 1, Sada želimo napraviti roditelj pravo pokazivač newnode, drugo želimo napraviti roditelj lijevu pokazivača newnode. Pitanja o tome? Ok. Dakle, ovo je način na koji smo - Pa, zapravo, umjesto za to, mi polovina očekuje da koristite build_node. A onda, ako newnode jednaka null, povratak false. To je to. Sada, to je ono što smo i očekivali da to učinite. 

To je ono što djelatnici rješenja učiniti. Ne slažem se s tim što je "pravo" način će o tome ali to je savršeno u redu i da će raditi. Jedna stvar koja je malo čudno sada je pravo ako stablo započinje kao null, prolazimo u null stabla. Pretpostavljam da to ovisi o tome kako definirati ponašanje prolazi u null stabla. Ja mislim da bi, ako prođe u null stabla, zatim umetanje vrijednost u null stablo treba samo vratiti na stablo, gdje je jedina vrijednost je da jedan čvor. Nemojte ljudi se slažu s tim? Vi bi mogli, ako ste htjeli, ako prođe u null stablo i želite umetnuti vrijednost u tome, povratak false. To je do vas da definiraju da. Da biste to je prva stvar koju sam rekao i onda - dobro, ti si idući u imati problema radi toga, jer to će biti lakše ako smo imali globalni pokazivač na stvar, ali mi ne, pa ako je stablo null, ne postoji ništa što možemo učiniti o tome. Mi samo možemo vratiti false. Dakle, ja ću promijeniti umetak. Mi samo tehnički moglo promijeniti to pravo ovdje, kako se to Ponavljanje više stvari, ali ja ću promijeniti umetak da se čvor ** stablo. Dupli pokazivače. Što to znači? Umjesto da se bave pokazivače na čvorove, stvar ću se manipulira ovaj pokazivač. Ja ću se manipulira ovaj pokazivač. Ja ću se manipulira upućuje izravno. To ima smisla, jer, razmišljam o dolje - dobro, sad to ukazuje na nulu. Ono što želim učiniti je manipulirati ovaj pokazivač do točke da ne null. Želim ukazati na moj novi čvor. Ako sam samo pratiti naputke moje naputke, onda ja ne trebate pratiti roditelja pokazivača. Ja samo mogu pratiti da vidi je li pokazivač pokazuje na nulu, a ako pokazivač pokazuje na nulu, ga promijeniti ukazati na čvoru želim. I ja to mogu promijeniti jer imam pokazivač na pokazivač. Hajdemo vidjeti ovo pravo sada. Vi zapravo možete to učiniti rekurzivno prilično lako. Ne želimo to učiniti? Da, mi radimo. 

Idemo ga vidjeti rekurzivno. Prvo, što je naša baza slučaj će biti? Gotovo uvijek naša baza slučaj, ali zapravo, to je vrsta lukav. Prvo stvari prvi, ako (drvo == NULL) Pretpostavljam da smo tek će se vratiti false. To je različito od vašeg stabla bića null. Ovo je pokazivač na pokazivač korijena bića null što znači da je vaš korijen pokazivač ne postoji. Dakle, ovdje dolje, ako mi je činiti čvor * - neka je samo ponovno ovu. Čvor * korijen = NULL, i onda ću pozvati umetak radeći nešto slično, umetnite 4 u & korijena. Tako i korijen, ako je korijen čvor * onda i korijen će biti čvor **. Ovo vrijedi. U ovom slučaju, stablo, ovdje, stablo nije null - ili umetak. Ovdje. Stablo nije null; * stablo null, što je u redu jer ako * stablo null, onda ja to mogu manipulirati do sada ukazati na ono što sam htjela ukazati na. Ali, ako je stablo null, to znači da sam došao ovamo i rekao null. To nema smisla. Ja ne mogu ništa učiniti s tim. Ako stablo null, povratak false. Tako sam zapravo već rekao što je naš pravi baza slučaj. A što se da će to biti? [Student, nerazumljivo] [Bowden] Da. Dakle, ako (* stablo == NULL). Ovo se odnosi na slučaj ovamo gdje ako moja crvena kazaljka je Pokazivač sam usredotočen na, pa kao što sam usredotočen na ovom pokazivač, sada sam fokusiran na ovaj pokazivač. Sada sam fokusiran na ovaj pokazivač. Dakle, ako moja crvena kazaljka, koja je moja čvor **, je ikada - ako *, moj crveni pokazivač je uvijek nula, to znači da sam u slučaju kada sam s naglaskom na pokazivač koji pokazuje - ovo je pokazivač koji pripada list. Želim promijeniti ovaj pokazivač ukazati na mom novom čvoru. Vrati se ovamo. Moj newnode će biti samo čvor * n = build_node (vrijednost) zatim n, ako n = null, povratak false. Inače želimo promijeniti ono što pokazivač trenutno ukazuje na do sada ukazuju na našem novoizgrađenom čvoru. Mi zapravo može učiniti da je ovdje. Umjesto da se kaže n, možemo reći * stablo = ako * stabla. Svatko razumije da? To što se bave pokazivače na pokazivače, možemo promijeniti null upućuje da ukažu na stvari koje žele im ukazati na. To je naša baza slučaj. 

Sada naša ponavljanja, ili naš rekurzije, će biti vrlo sličan svim ostalim recursions smo radili. Mi ćemo želite umetnuti vrijednost, a sada ću koristiti ternarni opet, ali ono što je naše stanje će biti? Što je to što tražimo da odluči da li želimo ići lijevo ili desno? Ajmo to učiniti u odvojenim koracima. Ako (vrijednost <) što? [Studentski] stablu je vrijednost? [Bowden] Pa sjetite se da sam trenutno - [Studenti, nerazumljivih] [Bowden] Da, tako ovdje, recimo da je ovo zelena strelica je primjer onoga što stablo trenutno je, je pointer na ovaj pokazivač. Dakle, to znači da sam pokazivač na pokazivač na tri. The dereference dvaput dobro zvuči. Što ja - kako ću to učiniti? [Studentski] Dereference jednom, a zatim učinite strelica na taj način? [Bowden] Pa (* stablo) je dereference jednom -> vrijednost će mi dati vrijednost čvora da sam neizravno sam pokazuje na. Dakle, ja mogu napisati ** tree.value ako vam je draže da. Ili radi. Ako je to slučaj, onda želim pozvati umetnuti s vrijednosti. I ono što je moj ažurirani čvor ** će biti? Želim ići na lijevo, tako ** tree.left će biti moj lijevo. I želim pokazivač na tu stvar tako da, ako je lijeva završi null pokazivač, Ja mogu mijenjati ukazati na moj novi čvor. 

I drugi slučaj može biti vrlo slična. Ajmo zapravo čine da je moj ternarni upravo sada. Umetni vrijednost ako vrijednost <(** stablo). Vrijednost. Tada želimo ažurirati naše ** s lijeve strane, drugo želimo ažurirati naše ** desno. [Studentski] da li se pokazivač na pokazivač? [Bowden] Zapamtite da - ** tree.right je čvor zvijezda. [Student, nerazumljivo] >> Da. ** Tree.right je kao što je ovaj pokazivač ili nešto. Dakle, uzimajući pokazivač da, da mi daje ono što želim od pokazivača do tog momka. [Studentski] Može li mi ići opet zašto smo koristeći dvije pokazivače? [Bowden] Aha. Dakle - ne, možete, a da rješenje prije je način to radiš radi bez dva pokazivača. Morate biti u stanju razumjeti pomoću dva pokazivača, i to je čišći rješenje. Također, primijetite da je, što se događa ako je moj stablo - što se događa ako je moj korijen je bio nula? Što će se dogoditi ako ja napraviti ovaj slučaj ovdje? Dakle, čvor * korijen = NULL, umetnite 4 u & korijena. Što je korijen će biti nakon toga? [Student, nerazumljivo] >> Da. Korijen vrijednost će biti četiri. Korijen lijevo će biti nula, korijen pravo će biti nula. U slučaju da nismo proći korijen po adresi, nismo mogli mijenjati korijen. U slučaju stablo - gdje korijen je bio nula, samo smo morali vratiti false. Nema ništa što bi mogao učiniti. Mi ne možemo umetnuti čvor u praznu stabla. No, sada možemo, mi jednostavno napraviti prazno stablo u jedan čvor stabla. Koja je obično očekivani način na koji bi to trebalo raditi. 

Nadalje, to je znatno kraći od Također praćenje roditelja, i tako ćete ponoviti dolje skroz. Sada imam roditelja, a ja samo imam pokazivač roditelj pravo na bilo što. Umjesto toga, ako je to učinio iterativno, to bi se ista ideja s while petlje. No, umjesto da se bave mojim roditelja pokazivač, umjesto moj trenutni pokazivač bi biti stvar da sam izravno sam modificiranje ukazati na moj novi čvor. Ja ne moram nositi s bilo to ukazuje na lijevoj strani. Ja ne moram nositi s bilo to pokazuje na desno. To je samo ono što ovaj pokazivač, ja ću ga postaviti ukazati na moj novi čvor. Svatko shvatiti kako se to radi? Ako ne, zašto ne želimo to učiniti na ovaj način, ali barem da to funkcionira kao rješenje? [Studentski] Kamo ćemo povratak istina? [Bowden] To je vjerojatno upravo ovdje. Ako smo ispravno ga uložite, povratak istina. Inače, ovdje ćemo se žele vratiti što god umetanje vraća. 

I ono što je posebno o ovom rekurzivne funkcije? To je rep rekurzivna, tako dugo dok smo sastaviti s nekim optimizacije, da će priznati da je i nikada nećete dobiti stack overflow od toga, čak i ako naša stablo ima visinu od 10.000 ili 10 milijuna. [Student, nerazumljivo] [Bowden] Mislim da to čini na Dash - ili ono što optimizacija razina je potrebno za rep rekurzije biti priznat. Mislim da je to prepoznaje - GCC i zveka Također imaju različita značenja za njihove optimizacije razinama. Želim reći da je DashO 2, sigurno da će prepoznati rep rekurzija. Ali mi - mogli graditi kao Fibonocci primjer ili nešto. To nije lako za testiranje s tim, jer je teško izgraditi binarno stablo koje je toliko velika. Ali da, mislim da je DashO 2, koji ako kompajlirati sa DashO dvije, to će izgledati za rep rekurzije i optimizirati da van. Vratimo se - umetnite je doslovno zadnja stvar treba. Vratimo se na umetka ovamo gdje idemo napraviti istu ideju. Još uvijek ćete imati nedostatak ne bude u mogućnosti da u potpunosti obrađuju kada je korijen sama je nula, ili prošlosti ulaz null, ali umjesto da se bave s roditeljem pokazivač, ajmo primijeniti istu logiku vođenja upućuje na pokazivače. Ako ovdje ćemo zadržati naš čvor ** sad, i ne trebamo pratiti desno više, ali čvor ** sad = & stablo. I sada naš while petlja će biti dok * sad ne jednak null. Ne trebate pratiti roditelja više. Ne trebate pratiti lijevo i desno. I ja ću ga nazvati temp, jer smo već koristite temp. Ok. Dakle, ako (vrijednost> * temperatura), tada & (* temp) -> desni drugi temp = & (* temp) -> lijevo. I sada, u ovom trenutku, nakon ovog while petlje, Samo sam to učiniti jer možda je lakše razmišljati o iterativno nego rekurzivno, ali nakon ovog while petlje, * Temp je pokazivač želimo promijeniti. 

Prije smo imali roditelja, i htjeli smo promijeniti bilo koji roditelj lijevo ili desno roditelja, ali ako želimo promijeniti roditelj pravo, onda * temp je roditelj u pravu, a možemo ga promijeniti izravno. Dakle, ovdje dolje, možemo učiniti * temp = newnode, i to je to. Dakle, obavijesti, sve što smo učinili u to uzmu linija koda. Kako bi se pratiti od roditelja u svemu što je dodatni napor. Evo, ako mi samo pratiti pokazivača na pokazivač, pa čak i ako smo htjeli da biste dobili osloboditi od svih tih vitičastih zagrada sada, čine ga gledati kraći. Ovo sada je isti rješenje, ali manje linija koda. Jednom kada počnete prepoznajući to kao valjani rješenje, to je također lakše razloga o nego kao, ok, zašto imam ovu zastavu na int desno? Što to znači? Oh, to je znači da svaki put sam ići desno, moram ga postaviti, drugo, ako sam ići lijevo moram ga postaviti na nulu. Evo, ja ne moram razlog za to, to je samo lakše razmišljati o tome. Pitanja? [Student, nerazumljivo] >> Da. Ok, tako da je u posljednjem malo - Valjda jedan brz i jednostavan funkcija možemo učiniti je, let's - zajedno, pretpostavljam, probati i napisati sadrži funkciju koji ne mari da li je binarno stablo pretraživanja. Sadrži funkcija treba vratiti istinito ako nigdje u toj općoj binarno stablo je vrijednost tražimo. Dakle, neka prvi to učiniti rekurzivno i onda ćemo to učiniti iterativno. Mi zapravo može samo to učiniti zajedno, jer će to biti jako kratko. 

Što je moja baza slučaj će biti? [Student, nerazumljivo] [Bowden] Dakle, ako (drvo == NULL), što onda? [Studentski] Povratak lažna. [Bowden] Inače, dobro, ja ne treba drugo. Ako je moja druga baza slučaj. [Student] stablo je vrijednost? >> Da. Dakle, ako (drvo-> vrijednost == vrijednost. Obavijest smo natrag do čvora *, a ne čvor ** e? Sadrži nikada nećete morati koristiti čvor **, jer mi se ne mijenja naputke. Samo smo ih poprijeko. Ako se to dogodi, onda želimo da se vrate istina. Inače želimo proći djecu. Dakle, ne možemo zaključivati ​​o tome da li je sve na lijevoj strani je manje i sve na desnoj strani je veći. Dakle, ono što je naše stanje će biti ovdje - ili, što ćemo učiniti? [Student, nerazumljivo] >> Da. Povratak sadrži (vrijednost, drvo-> lijevo) ili sadrži (vrijednost, stablo-> desni). I to je to. I primijetiti da je neki kratki spoj procjena, gdje ako mi se dogoditi da naći vrijednost u lijevom stablu, mi nikada ne treba gledati na desnoj stabla. To je cijela funkcija. Sada ćemo to učiniti iterativno, koja će biti manje lijepo. Mi ćemo poduzeti uobičajene početak čvor * valutama = stabla. Dok (sad! = NULL). Brzo će se vidjeti problem. Ako sad - ovdje, ako mi ikada break out to, onda smo ponestane stvari za pogledati, pa povratak false. Ako (sad-> vrijednost == vrijednost), povratak istina. Dakle, sada smo na jednom mjestu - Ne znamo da li želimo ići lijevo ili desno. Dakle, samovoljno, neka je samo ići lijevo. Ja očito nisam izvoditi u pitanju, gdje sam potpuno sam napustio sve - Ja samo da će ikada provjeriti lijevu stranu stabla. Ja nikada ne će provjeriti sve što je pravo dijete ništa. Kako mogu popraviti ovo? [Studentski] Morate pratiti lijevo i desno u stog. [Bowden] Aha. Dakle, neka je to učiniti struct lista, čvor * n, a zatim čvor ** sljedeći? Mislim da radi dobro. Mi želimo ići preko lijeve, ili let's - ovdje. Struct Lista = Lista, to ću početi se na tom popisu struct. * Popis = NULL. Tako da će to biti naša povezana popis od subtrees da smo preskočili. Mi ćemo proći lijevo sada, ali budući da smo neminovno morati vratiti na desno, Mi ćemo zadržati desnu stranu unutar našeg struct popisu. Tada ćemo imati new_list ili struct, struct list *, new_list = malloc (sizeof (popis)). Ja ću ignorirati pogreške provjere, ali trebali biste provjeriti da vidi da li je null. New_list čvor kada će se ukazati - oh, to je razlog zašto sam ga htjela ovdje. To će ukazati na drugom struct popisu. To je samo koliko je vezan liste rad. To je isto kao int povezane liste osim samo smo zamjene int s čvora *. To je točno isti. Dakle new_list, vrijednost našeg new_list čvora, će biti sad-> desno. Vrijednost našeg new_list-> next će biti naš izvorni popis, i onda ćemo ažurirati naš popis ukazati na new_list. 

Sada trebamo nekakav način povlačenjem stvari, kao što smo prelazili cijela lijevo podstablo. Sada moramo izvući stvari iz nje, kao sad je null, mi ne želimo samo vratiti false. Želimo sada povući izvan u našem novom popisu. Zgodan način za to - dobro, zapravo, postoji više načina za to. Svatko ima prijedlog? Gdje bih trebao učiniti ovo ili kako bih trebao učiniti? Imamo samo nekoliko minuta, ali bilo kakve prijedloge? Umjesto - jedan način, umjesto našeg stanja bića, dok ono što mi trenutno gledamo nije null, umjesto da ćemo i dalje ići do našeg lista sama po sebi je ništavan. Dakle, ako naš popis završi null, tada smo ponestane stvari koje treba tražiti, pretraživati. No, to znači da je prva stvar u našem popisu samo će biti prvi čvor. Prva stvar će biti - mi više ne treba da se vidi da. Dakle, popis-> n će biti naša stablo. Lista-> next će biti nula. I sada, dok popis ne jednak null. Sad će se povući nešto s našeg popisa. Dakle, sad će se jednako Lista-> n. I onda popis ide na jednak Lista-> n, ili popis-> next. Dakle, ako sad vrijednost jednaka vrijednosti. Sada možemo dodati i naše pravo i naš pokazivač lijevo pokazivač dokle god oni ne null. Ovdje dolje, mislim da smo trebali učiniti da na prvom mjestu. Ako (sad-> desno! = NULL) onda ćemo umetnuti taj čvor u našem popisu. Ako (sad-> lijevo), ovo je malo dodatnog rada, ali to je u redu. Ako (sad-> lijevo! = NULL), i da ćemo umetnuti lijevo u našem povezane liste, i da bi trebao biti to. Mi ponoviti - dokle god imamo nešto u našem listu, imamo još jedan čvor da pogledate. Dakle, mi gledamo na tom čvoru, smo unaprijediti naše liste na sljedeću. Ako je čvor je vrijednost tražimo, možemo se vratiti istina. Inače umetnite obje naše lijeve i desne subtrees, dokle god oni ne null, u našem popisu tako da smo neminovno ide preko njih. Dakle, ako oni nisu bili null, ako je naš korijen pokazivač ukazao na dvije stvari, onda na prvi smo izdvajali nešto tako naš popis završi null. I onda smo stavili dvije stvari natrag, tako da sada naš popis je veličine dva. Onda idemo petlje natrag gore i samo mi ćemo povući, recimo, lijevi pokazivač našeg korijena čvora. I da ću samo držati se događa, a mi ćemo završiti petlje nad svime. 

Primijetit ćete da je to znatno složenija u rekurzivne rješenje. I ja sam rekao više puta da rekurzivna rješenje obično ima mnogo toga zajedničkog s iterativno rješenje. Evo to je upravo ono što rekurzivna rješenje radi. Jedina promjena je da umjesto implicitno koristi snop, program stog, kao način praćenja ono čvorovi još uvijek morate posjetiti, Sada imate izričito koristiti povezanu listu. U oba slučaja se praćenje onoga čvor uvijek treba posjetio. U rekurzivni slučaju to je samo lakše jer stog provodi se za vas kao programa stog. Obavijest da je to povezano popis, to je stog. Što god mi samo staviti na stog je odmah što ćemo skinuti hrpu posjetiti sljedeći. Mi smo izvan vremena, ali kakvih pitanja? [Student, nerazumljivo] [Bowden] Aha. Dakle, ako imamo povezanu listu, struja će ukazati na ovog momka, i sada smo samo napreduje naš povezanu listu da se usredotoče na ovim tipom. Mi smo prešli preko povezanog popisa u toj liniji. I onda mislim da bi trebao osloboditi naše povezanu listu i stvari jednom prije povratka istinita ili lažna, trebamo iteraciju preko našeg povezanog popisa i uvijek ovdje, pretpostavljam, ako mi sad pravo nije jednaka, dodajte ga, tako da sada želimo osloboditi sad, jer, dobro, nije mi potpuno zaboraviti na popisu? Aha. Dakle, to je ono što želimo učiniti ovdje. Gdje je pokazivač? Sad je tada bio - mi želimo na struct popis * 10 iznosi popis sljedeći. Besplatno popis, popis = temp. I u slučaju kada smo se vratili istina, mi trebamo ponoviti tijekom ostatka našeg povezanog popisa oslobađanja stvari. Lijepo je stvar o rekurzivni rješenje je oslobađanje stvari samo znači iskakanje factorings off stog što će se dogoditi za vas. Tako smo otišli iz nešto što je kao tri linije teško razmišljati o-koda na nešto što je znatno mnogo više teško razmišljati o-linija koda. Svaki više pitanja? U redu. Mi smo dobro. Bok! [CS50.TV]