[Powered by Google Translate] [Afsnit 7: Mere behagelig] [Rob Bowden] [Harvard University] [Dette er CS50] [CS50.TV] Ok. Så som jeg sagde i min e-mail, Dette vil være et binært-tree-intensiv afdeling. Men der er ikke så mange spørgsmål. Så vi vil forsøge at trække ud hvert spørgsmål og gå ind i smertefulde detaljer alle de bedste måder at gøre tingene på. Så lige i starten, går vi igennem prøve tegninger af binære træer og kram. Så her, "Husk, at et binært træ har knuder svarende til dem, en linket liste, undtagen i stedet for en pointer der er to: én for det venstre "barn" og én til højre "barn". " Så et binært træ er ligesom en linket liste, undtagen struct vil have to pointere. Der er ternær træer, som kommer til at have tre pegepinde, Der er N-ære træer, som blot har en generisk pointer at du derefter nødt til at allokere at være store nok til at have nok henvisninger til alle de mulige børn. Så binært træ bare tilfældigvis har et konstant antal af to. Hvis du vil, kan du give en sammenkædet liste som en Monadiske træ, men jeg tror ikke, nogen kalder det det. "Tegn en æsker-og-pile diagram af et binært træ knude indeholdende Nate yndlings nummer, 7, hvor hvert barn pointer er null. " Så iPad tilstand. 

Det kommer til at være temmelig ligetil. Vi vil bare have en node, vil jeg trække det som en firkant. Og jeg vil tegne værdierne i her. Så værdien vil gå i her, og derefter ned her vil vi have den venstre markøren på venstre og højre markøren til højre. Og det er meget så konvention at kalde det venstre og højre, markøren navne. Begge disse vil være null. Det vil bare være null, og det vil bare være null. Okay. Så tilbage til her. "Med et sammenkædet liste, havde vi kun at gemme en pegepind til det første emne i listen for at huske det hele linkede liste, eller hele listen. Ligeledes med træer, har vi kun til at gemme en pegepind til en enkelt knude for at huske hele træet. Denne node er calle den 'root' af træet. Bygge videre på dit diagram fra før eller tegne en ny sådan at du har en æsker-og-pile skildring af et binært træ med værdien 7 og derefter 3 i venstre, derefter 9 til højre, og derefter 6 på højre side af 3 ". Lad os se om jeg kan huske alt dette i mit hoved. Så det vil være vores rod op her. Vi har nogle pointer eller andet sted, noget, som vi vil kalde rod, og den peger mod denne fyr. Nu at lave en ny knude, hvad har vi, 3 på venstre? Så en ny knude med 3, og det i første omgang peger null. Jeg vil bare sætte N. Nu ønsker vi at gøre, at gå til venstre for 7. Så vi ændre denne pointer til nu pege på denne fyr. Og vi gør det samme. Vi ønsker en 9 herovre som oprindeligt bare siger null. Vi vil ændre denne pointer, peg på 9, og vi ønsker nu at sætte 6 til højre for 3. Så det kommer til at - gøre en 6. Og den fyr vil pege dér. Okay. Så det er alt det beder os om at gøre. 

Lad os nu gå over nogle terminologi. Vi har allerede talt om, hvordan roden af ​​træet er det øverste knude i træet. Den ene indeholdende 7. Knudepunkterne i bunden af ​​træet kaldes bladene. Enhver knude der bare har nul som sine børn, er et blad. Så det er muligt, hvis vores binært træ er blot en enkelt node, at et træ er et blad, og det er det. "Den 'højde' af træet er antallet af humle du har at gøre at komme fra toppen til et blad. " Vi vil komme ind i en anden, forskellen mellem balancerede og ubalancerede binære træer, men for nu, den samlede højde af dette træ Jeg ville sige, er 3, selv hvis man tæller antallet af humle du nødt til at gøre for at komme til 9, så er det virkelig kun en højde på 2. Lige nu er det et ubalanceret binært træ, men vi vil talte om balanceret når det kommer til at være relevant. Så nu kan vi tale om knudepunkter i et træ i form i forhold til de andre knuder i træet. Så nu har vi forældre, børn, søskende, forfædre og efterkommere. De er temmelig sund fornuft, hvad de betyder. Hvis vi spørger - det er forældre. Så hvad er moderselskab for 3? [Studerende] 7. >> Yeah. Moderselskabet er bare at være, hvad peger på dig. Så hvad er de børn af 7? [Studerende] 3 og 9. >> Yeah. Bemærk, at "børn" bogstaveligt betyder børn, så 6 ville ikke finde anvendelse, fordi det er ligesom et barnebarn. Men så hvis vi går efterkommere, så hvad er efterkommere af 7? [Studerende] 3, 6 og 9. >> Yeah. Efterkommerne af roden node bliver alt i træet, undtagen måske rodnoden selv, hvis du ikke ønsker at overveje at en efterkommer. Og endelig forfædre, så det er den modsatte retning. Så hvad er de forfædre 6? [Studerende] 3 og 7. >> Yeah. 9 er ikke inkluderet. Det er bare den direkte afstamning tilbage til roden bliver dine forfædre. 

"Vi siger, at et binært træ er» bestilt «, hvis for hver node i træet, alle sine efterkommere til venstre har mindre værdier og alle af dem til højre har større værdier. For eksempel er træet oven bestilt, men det er ikke den eneste mulige bestilte arrangement. " Før vi kommer til det, en ordnet binært træ er også kendt som en binær søgning træ. Her er vi tilfældigvis være at kalde det en ordnet binært træ, men jeg har aldrig hørt det kaldt en bestilt binært træ før, og på en quiz vi er meget mere tilbøjelige til at sætte binær søgning træ. De er den samme, og det er vigtigt, at du erkender forskellen mellem binært træ og binær søgning træ. Et binært træ er blot et træ, der peger på to ting. Hver node peger på to ting. Der er ingen begrundelse om de værdier, den peger på. Så gerne her over, da det er et binært søgetræ, vi ved, at hvis vi går tilbage af 7, så alle de værdier, som vi overhovedet kan nå ved at gå tilbage på 7 være mindre end 7. Bemærk, at alle værdier mindre end 7 er 3 og 6. De er alle til venstre for 7. Hvis vi går til højre for 7, alt skal være større end 7, så 9 er til højre for 7, så vi er gode. Dette er ikke tilfældet for et binært træ, for en regelmæssig binært træ kan vi bare 3 i toppen, 7 mod venstre, 9 til venstre på 7, og der er ingen bestilling af værdier overhovedet. Nu vil vi faktisk ikke gøre dette, fordi det er kedeligt og unødvendigt, men "forsøge at trække så mange bestilte træer, som du kan tænke på med numrene 7, 3, 9 og 6. Hvor mange forskellige arrangementer er der? Hvad er højden af ​​hver enkelt? " 

Vi vil gøre et par, men det vigtigste idé er, Dette er på ingen måde en unik repræsentation af et binært træ, der indeholder disse værdier. Alt, hvad vi behøver, er nogle binært træ, der indeholder 7, 3, 6 og 9. En anden mulig gyldigt ville være roden er 3, gå til venstre, og det er 6, gå til venstre, og det er 7, gå til venstre, og det er ni. Det er en perfekt gyldig binær søgning træ. Det er ikke meget nyttigt, fordi det er ligesom en linket liste og alle disse henvisninger er lige null. Men det er en gyldig træ. Ja? [Student] Må ikke værdierne er nødt til at være større på højre? Eller er det -? >> Disse Jeg mente at gå den anden vej. Der er også - Ja, lad os skifte det. 9, 7, 6, 3. God fangst. Det skal stadig at adlyde, hvad et binært træ søgning er meningen at gøre. Så alt til venstre skal være mindre end en given node. Vi kunne bare flytte, siger, denne 6 og sætte det her. Nej, vi kan ikke. Hvorfor skal jeg holde gør det? Lad os gøre - her er 6, her er 7, 6 point til 3. Det er stadig et gyldigt binær søgning træ. Hvad er der galt, hvis jeg - lad os se om jeg kan komme op med et arrangement. Ja, okay. Så hvad er der galt med dette træ? Jeg tror, ​​jeg har allerede givet dig en antydning af, at der er noget galt med det. Hvorfor skal jeg holde gør det? Okay. Det ser rimelig. Hvis vi ser på hver knude, såsom 7 og derefter til venstre for 7 er en 3. Så vi har 3, ting til højre for 3 er en 6. Og hvis man ser på 6, ting til højre for 6 er en 9. Så hvorfor er dette ikke en gyldig binær søgning træ? [Studerende] 9 er stadig til venstre på 7. >> Yeah. Det må være sandt, at alle værdier, du kan muligvis nå ved at gå til venstre for 7 er mindre end 7. Hvis vi går tilbage på 7, får vi til 3 og vi kan stadig komme til 6, vi kan stadig komme til 9, men ved at have gået mindre end 7, bør vi ikke være i stand til at komme til et tal, der er større end 7. Så dette er ikke en gyldig binær søgning træ. 

Min bror havde faktisk et interview spørgsmål Det var dybest set det, bare kode op noget at validere hvorvidt et træ er et binært søgetræ, og så det første han gjorde var bare kontrollere at se hvis venstre og højre er korrekte, og derefter gentage dernede. Men du kan ikke bare gøre det, du er nødt til at holde styr af det faktum, at nu hvor jeg har gået tilbage på 7, alt i denne undertræ skal være mindre end 7. Den korrekte algoritme skal holde styr af grænserne, at værdierne muligvis kan falde i. Vi vil ikke gå igennem dem alle. Der er en nice gentagelse forhold, selv om vi ikke har fået dem, eller vi vil ikke komme til dem, definere, hvor mange der rent faktisk er. Så der er 14 af dem. Tanken om, hvordan du ville gøre det matematisk er ligesom, du kan vælge et enkelt til at være roden node, og derefter, hvis jeg vælger 7 for at være roden node, så er der, siger, nogle numre, der kan gå være min venstre knude, og der er nogle tal, der kan være min højre knude, men hvis jeg har N Total tal, så det beløb, som kan gå til venstre plus det beløb, der kan gå til højre er n - 1. Så for de resterende tal, skal de være i stand til at gå enten til venstre eller højre. Det synes vanskeligt at hvis jeg sætter 3 først derefter alt har til at gå til venstre, men hvis jeg sætter 7, så nogle ting kan gå til venstre og nogle ting kan gå til højre. Og ved '3 første 'jeg betød alt kan gå til højre. Det er virkelig, du bare nødt til at tænke på det som, hvor mange ting kan gå på det næste niveau af træet. Og det kommer ud at være 14, eller du kan tegne dem alle, og så får du 14. 

Gå tilbage her, "Ordnet binære træer er cool, fordi vi kan søge igennem dem på en meget lignende måde at søge over et ordnet array. For at gøre det, vi starter ved roden og arbejde vores vej ned i træet mod blade,. kontrol med hvert nodens værdier mod de værdier, vi søger efter Hvis den aktuelle node værdi er mindre end den værdi, vi leder efter, du går ud for node ret barn. Ellers skal du gå til knudepunktet venstre barn. På et tidspunkt, vil du enten finde den værdi, du leder efter, eller du vil løbe ind i en null, angiver værdien er ikke i træet. " Jeg er nødt til at gentegne træet, vi havde før, det vil tage et sekund. Men vi ønsker at slå op, om 6, 10, og 1 er i træet. Så hvad det var, 7, 9, 3, 6. Okay. De numre, du ønsker at slå op, vi ønsker at se op 6. Hvordan virker denne algoritme arbejde? Nå, har vi også nogle rod pointer til vores træ. Og vi ville gå til roden og sige, er denne værdi svarende til den værdi, vi leder efter? Så vi leder efter 6, så det er ikke lige. Så vi holde ud, og nu siger vi, okay, så 6 er mindre end 7. Betyder det, at vi ønsker at gå til venstre, eller ønsker vi at gå til højre? [Student] Venstre. >> Yeah. Det er betydeligt lettere, er alt du skal gøre tegne en mulig knude af træet og derefter du lad være - i stedet for at forsøge at tænke i dit hoved, okay, hvis det er mindre, går jeg til venstre eller gå til højre, bare at kigge på dette billede, er det meget tydeligt, at jeg er nødt til at gå til venstre hvis dette knudepunkt er større end den værdi, som jeg leder efter. Så du går til venstre, nu er jeg ved 3. Jeg vil gerne - 3 er mindre end værdien jeg leder efter, hvilket er 6. Så vi går til højre, og nu jeg ender ved 6, som er værdien jeg leder efter, så jeg vender tilbage sandt. Den næste værdi jeg har tænkt mig at kigge efter, er 10. Okay. Så 10,, nu vil - afbrød det - kommer til at følge roden. Nu er 10 vil være større end 7, så jeg ønsker at se til højre. Jeg har tænkt mig at komme herover, er 10 bliver større end 9, så jeg har tænkt mig at ønsker at se til højre. Jeg kommer herover, men herovre nu er jeg ved null. Hvad gør jeg, hvis jeg ramte null? [Student] Tilbage falsk? >> Yeah. Jeg fandt ikke 10. 1 bliver et næsten identisk fald, undtagen det bare kommer til at blive vendt, i stedet for at kigge ned i højre side, jeg kommer til at se ned langs venstre side. 

Nu tror jeg, vi rent faktisk får at kode. Her er hvor - åbne op for CS50 apparatet og navigere din vej, men du kan også bare gøre det i rummet. Det er sandsynligvis ideel til at gøre det i rummet, fordi vi kan arbejde i rummet. "Først vil vi brug for en ny type definition for et binært træ node indeholder int værdier. Brug af standardteksten typedef nedenfor, oprette en ny type definition for en node i et binært træ. Hvis du går i stå. . . "Blah, blah, blah. Okay. Så lad os sætte standardtekst her, typedef struct node, og node. Ja, okay. Så hvad er de felter, vi gerne vil have i vores knude? [Student] Int og derefter to pointers? >> Int. value, to pointere? Hvordan kan jeg skrive pointers? [Student] Struct. >> Jeg skulle zoome ind Yeah, så struct node * venstre, og struct node * ret. Og husk diskussionen fra sidste gang, at dette giver ingen mening, det giver ingen mening, dette giver ingen mening. Du har brug for alt, hvad der med henblik på at definere dette rekursiv struct. Okay, så det er hvad vores træ kommer til at se ud. Hvis vi gjorde en ternær træ, så et knudepunkt kunne se ud B1, B2, struct node * b3, hvor b er en gren - faktisk har jeg mere hørt det venstre, midt, højre, men uanset hvad. Vi har kun bekymrer sig om binær, så højre, venstre. "Nu erklærer en global node * variabel for roden af ​​træet." Så vi vil ikke gøre det. For at gøre tingene lidt vanskeligere og mere generaliseret, Vi vil ikke have en global node variabel. I stedet for main vil vi erklære alle vores node ting, og det betyder, at nedenfor, når vi begynder at køre vores indeholder funktionsmoduler og vores insert funktion, i stedet for vore indeholder funktionsmoduler bare at bruge denne globale node variabel, vi bliver nødt til det tage som et argument træet, som vi ønsker det skal behandle. Under den globale variabel skulle gøre tingene lettere. Vi kommer til at gøre tingene sværere. Nu tage et minut eller så at bare gøre den slags ting, hvor indersiden af ​​main du vil oprette dette træ, og det er alt du ønsker at gøre. Prøv og konstruere dette træ i din primære funktion. 

Okay. Så du behøver ikke engang at have beregnet træet hele vejen endnu. Men nogen der har noget jeg kunne trække op at vise, hvordan man kan begynde at bygge et sådant træ? [Student] Nogen banging, forsøger at komme ud. [Bowden] Enhver komfortable med deres træ konstruktion? [Student] Sure. Det er ikke sket. >> Det er okay. Vi kan bare færdig - åh, kan du gemme den? Hurra. Så her har vi - oh, jeg lidt afskåret. Er jeg zoomet ind? Zoom ind ved at rulle ud. >> Jeg har et spørgsmål. >> Ja? [Student] Når du definerer struct, er ting som initialiseret til noget? [Bowden] Nej >> Okay. Så du ville have til at initialisere - [Bowden] Nej Når du definerer, eller når du erklærer en struct, det er ikke initialiseret som standard, det er ligesom, hvis du erklærer en int. Det er nøjagtig det samme. Det er ligesom hver af dens individuelle felter kan have en skraldespand værdi i det. >> Og er det muligt at definere - eller at erklære en struct på en sådan måde, at det gør initialisere dem? [Bowden] Ja. Så genvej initialisering syntaks kommer til at se ud - Der er to måder, vi kan gøre dette. Jeg synes, vi skal kompilere det at sikre Dunk også gør det. Rækkefølgen af ​​argumenter, der kommer i struct, du lægger som rækkefølgen af ​​argumenter indersiden af ​​disse krøllede parenteser. Så hvis du ønsker at initialisere den til 9 og overlades null og derefter til højre være null, ville det være 9, null, null. Alternativet er, og redaktøren kan ikke lide denne syntaks, og det tror jeg vil have en ny blok, men alternativet er noget lignende - her, vil jeg sætte det på en ny linje. Du kan udtrykkeligt sige, jeg glemmer den nøjagtige syntaks. Så du kan tage eksplicit stilling til dem ved navn, og sige, . C, eller. Værdi = 9,. Venstre = NULL. Jeg kan gætte disse skal være kommaer. . Højre = NULL, så denne måde behøver du ikke rent faktisk har brug for at vide rækkefølgen af ​​struct, og når du læser dette, er det meget mere eksplicit hvad værdien der bliver initialiseret til. 

Dette sker for at være en af ​​de ting, - så, for det meste, C + + er en overordnet C. Du kan tage C-kode, skal du flytte det over til C + +, og det bør udarbejde. Dette er en af ​​de ting, C + + understøtter ikke, så folk har en tendens til ikke at gøre det. Jeg ved ikke, om det er den eneste grund til folk har en tendens til ikke at gøre det, men det tilfælde, hvor jeg behov for at bruge det nødvendigt at arbejde med C + + og så kunne jeg ikke bruge det. Et andet eksempel på noget, der ikke fungerer sammen med C + + er hvordan malloc returnerer en "void *", teknisk, men du kan bare sige char * x = malloc uanset hvad, og det vil automatisk blive kastet til en char *. Denne automatiske cast sker ikke i C + +. Det ville ikke kompilere, og du vil eksplicit nødt til at sige char *, malloc, uanset, at kaste den til en char *. Der er ikke mange ting, som C og C + + er uenige om, men de er to. Så vi vil gå med denne syntaks. Men selv om vi ikke gå med denne syntaks, hvad er - kunne være galt med det? [Student] Jeg behøver ikke at dereference det? >> Yeah. Husk, at pilen har en implicit dereference, og så når vi bare at gøre med en struct, vi ønsker at bruge. at få på et felt inde i struct. Og den eneste gang vi bruger pil er, når vi ønsker at gøre - godt, pil svarer til - det er, hvad det ville have betydet, hvis jeg brugte pil. Alle pil betyder er, dereference dette, nu er jeg på en struct, og jeg kan få feltet. Enten får feltet direkte eller dereference og få marken - Jeg tror det skulle være værdi. Men her jeg beskæftiger sig med blot en struct, ikke en pointer til en struct, og så jeg kan ikke bruge pilen. Men den slags ting, vi kan gøre for alle noder. Åh min Gud. Dette er 6, 7 og 3. Så kan vi oprette filialer i vores træ, kan vi have 7 - vi kan have, bør dens venstre pege på 3. Så hvordan gør vi det? [Studerende, uforståelig] >> Yeah. Adressen på node3, og hvis du ikke har adresse, så er det bare ikke ville kompilere. Men husk, at det er henvisninger til de næste noder. Den ret bør pege på 9, og 3 skal pege på retten til 6. Jeg tror, ​​det er alle indstillet. Eventuelle kommentarer eller spørgsmål? [Studerende, uforståelig] Roden bliver 7. Vi kan bare sige node * ptr = eller rod, = & node7. 

Til vores formål vil vi beskæftige sig med indsatsen, så vil vi ønsker at skrive en funktion til at indsætte i denne binært træ og indsatsen er uundgåeligt vil kalde malloc at oprette en ny node for dette træ. Så tingene kommer til at få rodet med det faktum, at nogle knuder er i øjeblikket på stakken og andre knudepunkter kommer til at ende op på den bunke, når vi indsætter dem. Det er helt i orden, men den eneste grund vi er i stand til at gøre dette på stakken er fordi det er sådan en konstrueret eksempel, som vi kender træet formodes at være konstrueret som 7, 3, 6, 9. Hvis vi ikke havde det, så ville vi ikke behøver at allokere i første omgang. Som vi vil se lidt senere, bør vi malloc'ing. Lige nu er det helt rimeligt at lægge på stakken, men lad os ændre det til en malloc gennemførelse. Så hver af disse er nu vil være noget i retning af node * node9 = malloc (sizeof (node)). Og nu vi er nødt til at gøre vores kontrol. if (node9 == NULL) - Jeg ville ikke have, at - returnere 1, og så kan vi gøre node9-> fordi nu er det en pointer, value = 6, node9-> venstre = NULL, node9-> højre = NULL, og vi bliver nødt til at gøre det for hver af disse knudepunkter. Så i stedet, lad os sige det inde i en separat funktion. Lad os kalde det node * build_node, og det er noget der ligner det API'er vi sørge for Huffman kodning. Vi giver dig initializer funktioner for et træ og Deconstructor "funktioner" for de træer og det samme for skovene. 

Så her vil vi have en startværdi funktion at bare bygge en node for os. Og det kommer til at se temmelig meget nøjagtigt som dette. Og jeg selv kommer til at være doven og ikke ændre navnet på den variabel, selv om node9 meningsløst længere. Åh, jeg gætte node9 værdi ikke skulle have været 6. Nu kan vi vende tilbage node9. Og her bør vi vende tilbage null. Alle er enige om, at Build-A-node funktion? Så nu kan vi bare kalde det at bygge en node med en bestemt værdi, og null-pegepinde. Nu kan vi kalde det, kan vi gøre node * node9 = build_node (9). Og lad os gøre. . . 6, 3, 7, 6, 3, 7. Og nu ønsker vi at etablere de samme pejlemærker, undtagen nu alt er allerede i form af pegepinde så ikke længere brug for adressen på. Okay. Så hvad er den sidste ting, jeg ønsker at gøre? Der er en fejlkontrol, at jeg ikke gør. Hvad betyder bygge knude afkast? [Studerende, uforståelig] >> Yeah. Hvis malloc mislykkedes, vil den vende tilbage null. Så jeg har tænkt mig at lazily sætte den ned her i stedet for at gøre en betingelse for hver. Hvis (node9 == NULL, eller - endnu nemmere, dette svarer til blot hvis ikke node9. Så hvis ikke node9 eller ikke node6 eller ikke node3 eller ikke node7, returnere 1. Måske skulle vi udskrive malloc fejlede, eller noget. [Student] Er falsk lig med nul så godt? [Bowden] Enhver nulværdi er falsk. Så null er en værdi på nul. Nul er en nulværdi. False er en nul værdi. Enhver - temmelig de kun 2 nulværdier er nul og nul, falsk er bare hash defineres som nul. Dette gælder også, hvis vi erklærer global variabel. Hvis vi havde node * rod op her, derefter - den pæne ting om globale variabler er, at de altid har en indledende værdi. Det er ikke sandt af funktioner, hvor indersiden af ​​her, hvis vi har, ligesom, node * eller node x. Vi har ingen idé om, hvad x.value, x.whatever, eller vi kunne udskrive dem, og de kunne være vilkårlig. Det er ikke tilfældet for globale variable. Så node rod eller node x. Som standard, alt det, der er global, hvis ikke udtrykkeligt initialiseret til en vis værdi, har en værdi på nul som sin værdi. Så her, node * rod, vi ikke udtrykkeligt initialisere det til noget, så dens standardværdi vil blive nulstillet, der er nulværdi af pointere. Standardværdien af ​​x vil betyde, at x.value er nul, x.left er null, og x.right er null. Så da det er en struct, vil alle felterne i struct være nulværdier. Vi behøver ikke at bruge det her, selv om. [Student] De struct er anderledes end andre variabler, og de andre variabler er skrald værdier, disse er nuller? [Bowden] Andre værdier også. Så i x vil x være nul. Hvis det er på globalt omfang, det har en initial værdi. >> Okay. [Bowden] Enten den oprindelige værdi, du gav det eller nul. Jeg tror, ​​der tager sig af alt dette. 

Okay. Så den næste del af spørgsmålet oplyst, "Nu vil vi skrive en funktion kaldet indeholder med en prototype af bool indeholder int værdi. " Vi vil ikke gøre bool indeholder int værdi. Vores prototype kommer til at ligne bool indeholder (int værdi. Og så er vi også kommer til at passere det træet at det skulle kontrollere om det har denne værdi. Så node * træ). Okay. Og så kan vi kalde det med noget lignende, måske vil vi gerne printf eller noget. Indeholder 6, vores rod. Det burde returnere en eller sand, hvorimod indeholder 5 root bør vende tilbage falsk. Så tag et sekund at gennemføre denne. Du kan gøre det enten iterativt eller rekursivt. Det gode ved den måde, vi har sat tingene op, er, at den egner sig til vores rekursiv løsning meget lettere end den globale variabel måde gjorde. For hvis vi bare har indeholder int værdi, så vi har ingen mulighed for rekursiv ned undertræer. Vi skulle have en separat hjælpefunktion, der recurses ned undertræer for os. Men da vi har ændret det til at tage træet som et argument, som det burde have altid været i første omgang, Nu kan vi recurse lettere. Så iterative eller rekursiv, vil vi gå over både, men vi vil se, at rekursive ender med at blive ganske let. Okay. Er der nogen der har noget, vi kan arbejde med? 

[Student] Jeg har fået en iterativ løsning. >> Okay, iterativ. Okay, det ser godt ud. Så ønsker at gå os gennem det? [Student] Sure. Så jeg satte en temp variabel at få den første node i træet. Og så vil jeg bare sløjfes igennem, mens temp ikke er lig nul, så mens stadig var i træet, tror jeg. Og hvis værdien er lig med den værdi, temp peger på, så det returnerer den værdi. Ellers er det tjekker, om det er på højre eller venstre side. Hvis du nogensinde får en situation, hvor der ikke er mere træ, så det vender tilbage - den kommer ud af løkken og returnerer falsk. [Bowden] Okay. Så det virker godt. Nogen der har nogen kommentarer til noget? Jeg har ingen rigtighed kommentarer overhovedet. Det eneste, vi kan gøre, er denne fyr. Åh, det kommer til at gå en lille aflang. Jeg ordner det op. Okay. 

Alle bør huske, hvordan ternære virker. Der har helt klart været quizzer i fortiden der giver dig en funktion med en ternær operatør, og sige, oversætte dette, gøre noget, der ikke bruger ternære. Så dette er en meget almindelig sag, når jeg ville synes at bruge ternære, hvor hvis nogen betingelse en variabel til noget, ellers indstillet, at samme variabel til noget andet. Det er noget, som meget ofte kan omdannes til denne slags ting hvor indstille denne variabel til dette - eller godt, er det sandt? Så er dette, ellers dette. [Student] Den første er, hvis sandt, ikke? [Bowden] Yeah. Den måde jeg altid læse det er, temp lig værdi større end temp værdi, derefter dette, ellers dette. Det er at stille et spørgsmål. Er det større? Så gør den første ting. Else gøre den anden ting. Jeg har næsten altid - i tyktarmen, jeg bare - i mit hoved, læste jeg som andre steder. 

Er der nogen der har en rekursiv løsning? Okay. Denne ene vil vi - det kunne allerede være stor, men vi vil gøre det endnu bedre. Dette er stort set den samme nøjagtige idé. Det er bare, godt, vil du forklare? [Student] Sure. Så vi laver sikker på, at træet ikke er nul først, fordi hvis træet er null så det kommer til at returnere falsk, fordi vi ikke har fundet det. Og hvis der er stadig et træ, vi går ind i - vi først kontrollere, hvis værdien er den aktuelle node. Returnerer sand, hvis den er, og hvis vi ikke recurse til venstre eller højre. Lyder det passende? >> Mm-hmm. (Aftalen) Så bemærke, at det er næsten - strukturelt meget lig den iterative løsning. Det er bare at i stedet for rekursiv havde vi en while-løkke. Og basen tilfældet her, hvor træ ikke er lig nul var en situation, hvor vi brød ud af while-løkken. De er meget ens. Men vi vil tage dette et skridt videre. Nu gør vi det samme her. Bemærk vi tilbage det samme i begge disse linjer, undtagen for ét argument er anderledes. Så vi vil gøre det til en ternær. Jeg ramte option noget, og det gjorde et symbol. Okay. Så vi vil vende tilbage indeholder det. Dette bliver at være flere linjer, ja, zoomet ind det er. Normalt som et stilistisk ting, tror jeg ikke mange mennesker sætte et mellemrum efter pilen, men jeg gætte, hvis du er konsekvent, det er fint. Hvis værdi er mindre end træ værdi, vi ønsker at recurse på træ til venstre, ellers vil vi recurse på træ til højre. Så det var første skridt i at gøre dette look mindre. Trin to af gøre dette look mindre - vi kan adskille dette til flere linier. Okay. Trin to af gør det ser mindre er her, så returværdi lig træ værdi, eller indeholder uanset. 

Dette er en vigtig ting. Jeg er ikke sikker på, om han sagde det udtrykkeligt i klassen, men det hedder kortslutning evaluering. Idéen her er værdi == træ værdi. Hvis det er sandt, så er det sandt, og vi ønsker at 'eller' at med det, der er herovre. Så uden at tænke over hvad der er herovre, hvad er hele udtrykket vil vende tilbage? [Student] True? >> Ja, fordi sand af noget, or'd - eller ægte or'd med noget er nødvendigvis sandt. Så snart vi ser returværdi = træ værdi, Vi vil bare returnere sandt. Ikke engang gå til recurse indeholder yderligere ned på linjen. Vi kan tage et skridt videre. Return træ ikke er lig nul, og alt dette. Det gjorde det til en one-line funktion. Dette er også et eksempel på kortslutning evaluering. Men nu er det den samme idé - i stedet for - så hvis træet ikke er lig nul - eller, ja, hvis træet ikke lig nul, hvilket er slemt tilfælde, hvis træet er lig nul, så den første betingelse vil være falsk. Så falsk anded med noget kommer til at være, hvad? [Student] Falsk. >> Yeah. Dette er den anden halvdel af kortslutning evaluering, hvor, hvis træet ikke lige null, så vi ikke kommer til at selv gå - eller hvis træet ikke lige null, så vi ikke kommer til at gøre værdi == tree værdi. Vi vil bare straks returnere falsk. Hvilket er vigtigt, fordi hvis det gjorde ikke kortslutte evaluere, så hvis træet ikke lige null, er denne anden betingelse vil seg fejl, fordi træ-> værdi dereferere null. Så det er det. Kan gøre dette - skift en gang over. Dette er en meget almindelig ting også, ikke at gøre denne ene linje med dette, men det er en fælles ting i forhold, måske ikke lige her, men hvis (træ! = NULL, og træ-> værdi == værdi), gør hvad. Dette er en meget almindelig tilstand, hvor i stedet for at at bryde denne i to hvis'er, hvor gerne, er træet null? Okay, det er ikke null, så nu er træet værdi svarende til værdi? Gør dette. I stedet er denne betingelse, vil dette aldrig seg fejl fordi det vil bryde ud, hvis dette sker for at være nul. Tja, jeg gætte, hvis dit træ er en helt ugyldig pointer, kan det stadig seg fejl, men det kan ikke seg skyld, hvis træet er null. Hvis det var null, ville det bryde ud, før du nogensinde derefererede markøren i første omgang. [Student] Er dette kaldes doven evaluering? 

[Bowden] Lazy evaluering er en særskilt ting. Lazy evaluering er mere som du beder om en værdi, du bede om at beregne en værdi, slags, men du behøver ikke det samme. Så indtil du rent faktisk har brug for det, er det ikke vurderes. Det er ikke nøjagtigt det samme, men i Huffman Pset, den siger, at vi "dovent" skrive. Grunden til vi gør det er, fordi vi rent faktisk er at pufre skrive - vi ønsker ikke at skrive individuelle bits ad gangen, eller individuelle bytes ad gangen, vi i stedet ønsker at få en bid af bytes. Så når vi har en luns af bytes, så vil vi skrive det ud. Selvom du beder den om at skrive - og fwrite og fread gøre det samme slags ting. De buffer din læser og skriver. Selvom man bede den om at skrive det samme, er det sandsynligvis ikke. Og du kan ikke være sikker på, at tingene kommer til at blive skrevet indtil du ringer hfclose eller hvad det er, som derefter siger, okay, jeg lukker min fil, det betyder at jeg hellere skrive alt det, jeg har ikke skrevet endnu. Det har ingen grund til at skrive alt ud indtil du lukker filen, og så skal det. Så det er bare hvad doven - det venter, indtil det skal ske. Dette - at tage 51 og du vil gå ind i det mere detaljeret, fordi OCaml og alt i 51, alt er rekursion. Der er ingen iterative løsninger, dybest set. Alt er rekursion, og doven evaluering vil være vigtig for mange omstændigheder hvor, hvis du ikke dovent vurdere, ville det betyde - Eksemplet er strømme, som er uendeligt lange. I teorien kan du tænke på de naturlige tal som en strøm af 1-2-3-4-5-6-7, Så dovent vurderede ting er fint. Hvis jeg siger, at jeg vil have den tiende nummer, så jeg kan vurdere op til det tiende nummer. Hvis jeg vil have det hundrededel nummer, så jeg kan vurdere op til det hundrededel nummer. Uden doven evaluering, er det så kommer til at forsøge at evaluere alle numre med det samme. Du evaluerer uendeligt mange tal, og det er bare ikke muligt. Så der er en masse tilfælde, hvor doven evaluering er bare vigtigt for at få tingene til at fungere. 

Nu ønsker vi at skrive insert hvor indsatsen vil være ligeledes ændre sig i sin definition. Så lige nu er det bool insert (int værdi). Vi vil ændre det til bool insert (int værdi, node * træ). Vi faktisk kommer til at ændre det igen i en smule, vil vi se hvorfor. Og lad os gå build_node, bare for dælen af ​​det, ovenfor indsætte så vi ikke behøver at skrive en funktion prototype. Hvilket er en antydning af, at du skal bruge build_node i indsatsen. Okay. Tag et minut til det. Jeg tror, ​​jeg har gemt revisionen, hvis du ønsker at trække fra, eller i det mindste, hvad jeg nu. Jeg ønskede en lille pause til at tænke over logikken i indsatsen, hvis du ikke kan tænke på det. Dybest set, vil du altid kun være indsættelse af blade. Ligesom, hvis jeg indsætter 1, så er jeg uundgåeligt vil være at indsætte 1 - Jeg skifter til sort - æ være at indsætte 1 herovre. Eller hvis jeg indsætter 4, jeg ønsker at blive indsætte 4 herovre. Så uanset hvad du gør, er du nødt til at indsætte på et blad. Alt du skal gøre er at gentage ned i træet, indtil du kommer til knudepunktet der bør være knudens forælder, den nye node forælder, og derefter ændre sin venstre eller højre markør, afhængigt af om den er større eller mindre end den aktuelle node. Ændre denne pegepind til at pege på din nye node. Så gentage ned i træet, at bladet peger på det nye knudepunkt. Også tænke over, hvorfor der forbyder den type situation før, hvor jeg bygget det binære træ, hvor det var korrekt hvis du kun kigget på en enkelt node, men 9 var til venstre for 7 Hvis du gentog ned hele vejen. Så det er umuligt i dette scenario, da - tænker på at indsætte 9 eller noget, i det første emne, Jeg har tænkt mig at se 7 og jeg bare tænkt mig at gå til højre. Så uanset hvad jeg gør, hvis jeg indsætter ved at gå til et blad, og et blad ved hjælp af en passende algoritme, det vil være umuligt for mig at indsætte 9 til venstre på 7 fordi så snart jeg ramte 7 Jeg har tænkt mig at gå til højre. Er der nogen der har noget at starte med? [Student] jeg gør. >> Sure. [Studerende, uforståelig] [Other student, uforståelig] [Bowden] Det er værdsat. Okay. Vil du forklare? 

[Student] Da vi ved, at vi var at indsætte nye knudepunkter i slutningen af ​​træet, Jeg sløjfes igennem træet iterativt indtil jeg fik til et knudepunkt, der pegede til null. Og så besluttede jeg mig for at sige det enten på højre eller venstre side benytter denne ret variabel, og det fortalte mig, hvor til at sætte det. Og så væsentlige, jeg har lige lavet det sidste - at temp node peger på det nye knudepunkt, at det skabte, enten på venstre side eller højre side, alt efter hvad værdien højre var. Endelig jeg indstille den nye node værdi til værdien af ​​sin test. [Bowden] Okay, så jeg ser et spørgsmål her. Det er ligesom 95% af vejen. Den ene spørgsmål, som jeg ser, ja, er der nogen andre se et problem? Hvad er den omstændighed, hvorunder de bryder ud af løkken? [Student] Hvis temp er null? >> Yeah. Så hvordan du bryde ud af løkken er, hvis temp er null. Men hvad gør jeg lige her? Jeg dereference temp, hvilket er uundgåeligt null. Så den anden ting du skal gøre, er ikke bare holde styr indtil temp er nul, der skal holde styr på den forælder på alle tidspunkter. Vi ønsker også node * forælder, jeg tror vi kan holde denne på nul i første omgang. Dette vil have underlige adfærd for roden af ​​træet, men vi vil komme til det. Hvis værdi er større end hvad, så temp = temp højre. Men før vi gør det, forælder = temp. Eller er forældre altid vil lige temp? Er det tilfældet? Hvis temp ikke er nul, så jeg har tænkt mig at flytte ned, uanset hvad, til et knudepunkt, hvor temp er moderselskab. Så forælder kommer til at være temp, og så flytter jeg temp ned. Nu temp er nul, men forældre peger på moderselskab ting, der er null. Så hernede, jeg ikke ønsker at indstille højre er lig med 1. Så flyttede jeg til højre, så hvis højre = 1, og jeg gætter du også ønsker at gøre - hvis du flytter til venstre, du ønsker at indstille højre lig med 0. Eller også, hvis du nogensinde gå til højre. Så højre = 0. Hvis højre = 1, Nu ønsker vi at gøre den forælder rigtige pointer newnode, ellers vil vi gøre den forælder venstre pointer newnode. Spørgsmål om det? Okay. Så dette er den måde, vi - ja, faktisk, i stedet for at gøre dette, vi halvdelen forventes at bruge build_node. Og så hvis newnode lig nul, returnerer falsk. Det er det. Nu, dette er hvad vi forventede dig at gøre. 

Det er, hvad de ansatte løsninger gør. Jeg er uenig med dette som den "rigtige" måde at gå om det men det er helt fint, og det vil virke. En ting, der er lidt underligt lige nu er hvis træet starter som null, vi passere i en null-træ. Jeg gætter det afhænger af, hvordan du definerer opførsel passere i en null træ. Jeg vil tro, at hvis du sender en null træ, derefter indsætte værdien i en null træ skal bare returnere et træ, hvor den eneste værdi, er, at en enkelt node. Må folk enig i det? Du kunne, hvis man ville, hvis du sender en null træ og du ønsker at indsætte en værdi i det, returnere falsk. Det er op til dig at definere det. For at gøre det første, jeg sagde, og derefter - godt, er du nødt til at have problemer med at gøre det, fordi det ville være lettere, hvis vi havde en global pointer til de ting, men vi ved ikke, så hvis træet er nul, er der intet vi kan gøre ved det. Vi kan bare returnere falsk. Så jeg har tænkt mig at ændre indsatsen. Vi teknisk kunne blot ændre denne ret her, hvordan det iteration over ting, men jeg har tænkt mig at ændre indsatsen til at tage en node ** træ. Dobbelte pointers. Hvad betyder dette? Stedet for at behandle pegepinde til knudepunkter, de ting, jeg har tænkt mig at manipulere er denne pointer. Jeg har tænkt mig at blive manipulere denne pointer. Jeg har tænkt mig at blive manipulere pointers direkte. Dette giver mening, da tænke ned - godt, lige nu tyder det til null. Hvad jeg ønsker, er at manipulere denne pegepind til at pege på ikke null. Jeg vil have det til at pege på min nye node. Hvis jeg bare holde styr på henvisninger til mine pointers, så behøver jeg ikke at holde styr på en forælder pointer. Jeg kan bare holde styr at se, om markøren peger til null, og hvis markøren peger til null, ændre det til at pege på den knude, jeg ønsker. Og jeg kan ændre det, da jeg har en pointer til pointer. Lad os se det lige nu. Du kan faktisk gøre det rekursivt temmelig nemt. Ønsker vi at gøre det? Ja, det gør vi. 

Lad os se det rekursivt. For det første er hvad vores base case vil være? Næsten altid vores base case, men faktisk, det er lidt tricky. Første ting først, hvis (træ == NULL) Jeg gætter vi bare vil vende tilbage falsk. Dette er forskelligt fra dit træ er null. Dette er markøren til dit rod pointer er null hvilket betyder, at din rod pointer ikke eksisterer. Så hernede, hvis jeg gør node * - lad os bare genbruge det. Node * root = NULL, og så jeg har tænkt mig at kalde indsatsen ved at gøre noget lignende, indsætte 4 ind & rod. Så & rod, hvis rod er en node * derefter & rod vil være et knudepunkt **. Dette er gyldig. I dette tilfælde, træ, op her, træ ikke er nul - eller indsats. Her. Tree er ikke null; * træ er nul, hvilket er fint fordi hvis * træ er null, så jeg kan manipulere det nu pege på, hvad jeg vil have det til at pege på. Men hvis træet er null, det betyder, at jeg bare kom herned og sagde null. Det giver ikke mening. Jeg kan ikke gøre noget med det. Hvis træet er nul, returnerer falsk. Så jeg dybest set allerede sagt, hvad vores virkelige base case er. Og hvad er det kommer til at være? [Studerende, uforståelig] [Bowden] Ja. Så hvis (* tree == NULL). Det drejer sig om sagen herovre hvor hvis min røde pointer er markøren jeg fokuseret på, så ligesom jeg fokuseret på dette pointer, nu er jeg fokuseret på denne pegepind. Nu er jeg fokuseret på denne pegepind. Så hvis min røde pointer, som er min node **, er nogensinde - hvis *, min røde viser, er altid null, det betyder, at jeg er på det tilfælde, hvor jeg fokuserer på en pegepind, der peger - dette er en pegepind, der hører til et blad. Jeg ønsker at ændre denne pegepind til at pege på min nye node. Kom tilbage herovre. Min newnode vil bare være node * n = build_node (værdi) så n, hvis n = NULL, returnere falsk. Else vi ønsker at ændre, hvad markøren er i øjeblikket peger på nu henvise til vores nybyggede node. Vi kan faktisk gøre det her. I stedet for at sige n, siger vi * træ = hvis * træ. Alle forstår, at? At ved at behandle med pointere til pointere, vi kan ændre null-pegepinde til at pege på ting, vi ønsker dem til at pege på. Det er vores base case. 

Nu er vores tilbagefald, eller vores rekursion, vil være meget lig alle andre rekursioner vi har gjort. Vi vil ønsker at indsætte værdi, og nu vil jeg bruge ternære igen, men hvad er vores betingelse vil være? Hvad er det vi leder efter til at beslutte, om vi ønsker at gå til venstre eller højre? Lad os gøre det i separate trin. Hvis (værdi <) hvad? [Student] Træets værdi? [Bowden] Så husk, at jeg er i øjeblikket - [Studerende, uforståelige] [Bowden] Yeah, så lige her, lad os sige, at det grønne pil er et eksempel på det træ øjeblikket er, er en pointer til den pointer. Så det betyder, at jeg er en pegepind til en pegepind til 3. Den dereference to gange lød godt. Hvad gør jeg - hvordan gør jeg det? [Student] Dereference én gang, og derefter gøre pil på den måde? [Bowden] So (* træ) er dereference en gang, -> værdi vil give mig værdien af ​​den node, som jeg indirekte jeg peger på. Så jeg kan også skrive det ** tree.value, hvis du foretrækker det. Enten virker. Hvis det er tilfældet, så vil jeg kalde indsætte med værdi. Og hvad er min opdateret node ** kommer til at være? Jeg ønsker at gå til venstre, så ** tree.left bliver min venstre. Og jeg vil bevæge markøren, at ting således at hvis venstre ender med at blive nulhenvisning, Jeg kan ændre det til at pege på min nye node. 

Og det andet tilfælde kan være meget ens. Lad os faktisk gøre, at min ternære lige nu. Indsæt værdi, hvis værdi <(** træ). Værdi. Så vi ønsker at opdatere vores ** til venstre, ellers vil vi opdatere vores ** til højre. [Student] Betyder det få markøren til pointer? [Bowden] Husk, at - ** tree.right er et knudepunkt stjerne. [Studerende, uforståelig] >> Yeah. ** Tree.right er ligesom denne pointer eller noget. Så ved at tage en pegepind til det, giver det mig, hvad jeg vil af markøren til den fyr. [Student] Kunne vi gå igen, hvorfor vi bruger de to pointere? [Bowden] Yeah. Så - nej, du kan, og at løsningen før var en måde at gøre det uden at gøre to pointere. Du skal være i stand til at forstå ved hjælp af to pointere, og dette er en renere løsning. Bemærk også, at, hvad sker der, hvis mit træ - hvad sker der hvis min rod var null? Hvad sker der, hvis jeg gør denne sag lige her? Så node * root = NULL, skal du indsætte 4 ind & rod. Hvad er root vil være efter dette? [Studerende, uforståelig] >> Yeah. Root værdi vil være 4. Root venstre bliver null, er root ret vil være null. I tilfælde, hvor vi ikke gik igennem rod efter adresse, Vi kunne ikke ændre rod. I det tilfælde, hvor træet - hvor rod var null, havde vi blot at returnere falsk. Der er intet vi kunne gøre. Vi kan ikke indsætte en node i en tom træ. Men nu kan vi, vi skal bare lave en tom træ ind i en et-node træ. Hvilket er normalt den forventede måde, at det er meningen at arbejde. 

Endvidere er betydeligt kortere end også at holde styr på den forælder, og så du gentage ned hele vejen. Nu har jeg mine forældre, og jeg bare har mine forældre ret pointer til hvad som helst. I stedet, hvis vi gjorde dette iterativt, ville det være den samme idé med en while-løkke. Men i stedet for at skulle beskæftige sig med min overordnede pointer, i stedet min nuværende pointer ville være den ting at jeg direkte er ved at ændre til at pege på min nye node. Jeg behøver ikke at beskæftige sig med, om den peger mod venstre. Jeg behøver ikke at beskæftige sig med, om den peger mod højre. Det er bare hvad denne pointer er, vil jeg sætte den til at pege på min nye node. Alle forstå hvordan det virker? Hvis ikke hvorfor vi ønsker at gøre det på denne måde, men i det mindste at det fungerer som en løsning? [Student] Hvor skal vi returnere sandt? [Bowden] Det er nok lige her. Hvis vi rigtigt indsætte det, returnere sandt. Else, hernede vil vi ønsker at vende tilbage uanset insert afkast. 

Og hvad er specielt ved denne rekursiv funktion? Det er halerekursive, så længe vi kompilere med nogle optimering, det vil erkende det, og du vil aldrig få en stak overflow fra dette, selvom vores træ har en højde på 10.000 eller 10 mio. [Studerende, uforståelig] [Bowden] Jeg tror det gør det på Dash - eller hvad optimering niveau er nødvendig for en hale rekursion at blive genkendt. Jeg tror, ​​det anerkender - GCC og Dunk også have forskellige betydninger for deres optimering niveauer. Jeg vil sige, det er DashO 2, for sikker på, at det vil genkende hale rekursion. Men vi - du kunne konstruere som en Fibonocci eksempel eller noget. Det er ikke nemt at teste med dette, fordi det er svært at konstruere et binært træ, der er så stort. Men ja, jeg synes det er DashO 2, at hvis du kompilerer med DashO 2, vil den kigge efter hale rekursion og optimere det ud. Lad os gå tilbage til - indsæt er bogstaveligt talt det sidste, den har brug for. Lad os gå tilbage til indsatsen over her hvor vi vil gøre det samme idé. Det vil stadig have fejl af ikke at kunne helt klare når roden selv er nul, eller den tidligere post er nul, men i stedet for at behandle en forælder pointer, lad os anvende den samme logik holder henvisninger til pegepinde. Hvis her vi holder vores node ** cur, og vi har ikke brug for at holde styr på højre længere, men node ** nuværende = & træ. Og nu er vores while-løkke bliver mens * cur ikke er lig nul. Behøver ikke at holde styr på forældre længere. Behøver ikke at holde styr på venstre og højre. Og jeg vil kalde det temp, fordi vi allerede bruger temp. Okay. Så hvis (værdi> * temp), derefter & (* temp) -> højre ellers temp = & (* temp) -> til venstre. Og nu, på dette tidspunkt, efter denne while-løkken Jeg kun gøre det, fordi det måske er nemmere at tænke iterativt end rekursivt, men efter denne while-løkken, * Temp er markøren vi ønsker at ændre. 

Før vi havde forælder, og vi ønskede at ændre begge forældre til venstre eller forælder til højre, men hvis vi ønsker at ændre forælder ret, derefter * temp er forælder til højre, og vi kan ændre det direkte. Så hernede, kan vi gøre * temp = newnode, og det er det. Så varsel, var alle vi gjorde i denne tage ud linjer kode. For at holde styr på den forælder i alt det ekstra indsats. Her, hvis vi bare holde styr på markøren til markøren, og selv hvis vi ønskede at slippe af med alle disse krøllede parenteser nu, gøre det ser kortere. Det er nu nøjagtig den samme løsning, men færre linjer kode. Når du begynder at anerkende dette som en gyldig løsning, Det er også lettere at ræsonnere om end lignende, okay, hvorfor skal jeg dette flag på int ret? Hvad betyder det? Åh, det signalerer, at hver gang jeg går til højre, jeg er nødt til at indstille det, ellers hvis jeg går forlod jeg er nødt til at sætte den til nul. Her behøver jeg ikke at ræsonnere over det, det er bare nemmere at tænke over. Spørgsmål? [Studerende, uforståelig] >> Yeah. Okay, så i den sidste bit - Jeg gætte en hurtig og nem funktion, vi kan gøre, er, let's - sammen, tror jeg, så prøv og skrive en indeholder funktion der er ligeglad om det er en binær søgning træ. Denne indeholder funktion skal returnere true hvis overalt i denne generelle binært træ er den værdi, vi leder efter. Så lad os først gøre det rekursivt, og så vil vi gøre det iterativt. Vi kan faktisk bare gøre det sammen, fordi det vil være meget kort. 

Hvad er min base case vil blive? [Studerende, uforståelig] [Bowden] Så hvis (træ == NULL), hvad så? [Student] Tilbage falsk. [Bowden] Else, ja, jeg har ikke brug for andet. Hvis var min anden base case. [Student] Tree værdi? >> Yeah. Så hvis (træ-> værdi == værdi. Bemærk vi er tilbage til node *, ikke node ** s? Indeholder vil aldrig bruge en node **, da vi ikke ændrer pointers. Vi bare gennemkører dem. Hvis det sker, så vil vi returnere sandt. Else ønsker vi at krydse børnene. Så vi kan ikke ræsonnere om, hvorvidt alt til venstre er mindre og alt til højre er større. Så hvad er vores betingelse vil være her - eller hvad skal vi gøre? [Studerende, uforståelig] >> Yeah. Return indeholder (værdi, træ-> venstre) eller indeholder (værdi, træ-> højre). Og det er det. Og mærke der er en vis kortslutning evaluering, hvor, hvis vi tilfældigvis finde værdien i det venstre træ, vi aldrig nødt til at se på det rigtige træ. Det er den samlede funktion. Lad os nu gøre det iterativt, der vil være mindre rart. Vi tager den sædvanlige start node * cur = træ. Mens (nuværende! = NULL). Hurtigt kommer til at se et problem. Hvis cur - herude, hvis vi nogensinde bryde ud af dette, så vi har kørt ud af ting at se på, så returnere falsk. Hvis (aktu-> værdi == værdi) returnere sandt. Så nu er vi på et sted - Vi ved ikke, om vi ønsker at gå til venstre eller højre. Så vilkårligt, lad os bare gå til venstre. Jeg har selvfølgelig løbe ind i et problem, hvor jeg har fuldstændig forladt alt - Jeg vil altid kun tjek venstre side af et træ. Jeg vil aldrig se noget, der er en ret barn af noget. Hvordan kan jeg løse dette? [Student] Du er nødt til at holde styr på den venstre og højre i en stak. [Bowden] Yeah. Så lad os gøre det struct liste, node * n, og derefter node ** næste? Jeg tror, ​​der virker fint. Vi ønsker at gå over til venstre, eller let's - heroppe. Struct List List =, vil det starte på nuværende struct liste. * List = NULL. Så det kommer til at blive vores linkede liste af undertræer som vi har sprunget over. Vi kommer til at gennemkrydse tilbage nu, men da vi uundgåeligt nødt til at komme tilbage til højre, Vi kommer til at holde den højre side inde i vores struct liste. Så må vi have new_list eller struct, struct liste *, new_list = malloc (sizeof (liste)). Jeg har tænkt mig at ignorere fejlsøgning det, men du bør tjekke for at se om det er null. New_list node det vil pege på - åh, det er derfor jeg ville have det op her. Det kommer til at pege på en anden struct liste. Det er bare hvordan forbundet lister arbejde. Dette er det samme som en int forbundet liste bortset fra at vi lige er erstatter int med node *. Det er nøjagtig det samme. Så new_list, værdien af ​​vores new_list node, bliver cur-> højre. Værdien af ​​vores new_list-> næste bliver vores oprindelige liste, og så vil vi opdatere vores liste til at pege på new_list. 

Nu har vi brug for en slags måde at trække tingene, ligesom vi har krydset hele venstre undertræ. Nu skal vi til at trække ting ud af det, ligesom cur er null; vi ikke bare ønsker at returnere falsk. Vi vil nu trække udenfor på vores nye liste. En bekvem måde at gøre dette - ja, faktisk er der flere måder at gøre dette. Nogen der har et forslag? Hvor jeg skulle gøre dette eller hvordan jeg skal gøre dette? Vi har kun et par minutter, men nogen forslag? I stedet for - en måde, i stedet for vores betingelse er, medens, hvad vi i øjeblikket ser på, er ikke nul, i stedet vil vi fortsætte med at gå, indtil vores liste i sig selv er null. Så hvis vores liste ender med at blive null, så har vi løber tør for ting at kigge efter, for at søge over. Men det betyder, at den første ting på vores liste bare vil være den første knude. Den allerførste ting vil være - vi ikke længere behøver at se det. Så list-> n vil være vores træ. list-> næste bliver null. Og nu mens liste er ikke lig nul. Cur vil trække noget fra vores liste. Så cur vil lige liste-> n. Og så liste kommer til at lige liste-> n, eller liste-> næste. Så hvis cur værdi er lig værdi. Nu kan vi tilføje både vores højre pointer og vores venstre pointer så længe de ikke er null. Hernede, tror jeg, vi skulle have gjort det i første omgang. Hvis (aktu-> højre! = NULL) så vil vi indsætte denne knude i vores liste. Hvis (aktu-> venstre), dette er en lille smule ekstra arbejde, men det er fint. Hvis (aktu-> venstre! = NULL), og vi vil indsætte venstre ind i vores linkede liste, og det skal være det. Vi gentage - så længe vi har noget i vores liste, vi har en anden node at se på. Så vi ser på det knudepunkt, vi fremme vores liste til den næste. Hvis dette knudepunkt er den værdi, vi leder efter, kan vi returnere sandt. Else indsætte både vores venstre og højre undertræer, så længe de ikke er null, ind i vores liste således at vi uundgåeligt gå over dem. Så hvis de ikke var null, hvis vores rod pointer pegede på to ting, så først vi trak noget ud, så vores liste ender med at være null. Og så sætter vi to ting tilbage, så nu er vores liste er af størrelse 2. Så vi kommer til at sløjfe tilbage op, og vi vil bare trække, lad os sige, den venstre pointer af vores rod node. Og det bliver bare holde sker, og vi ender looping over alting. 

Bemærk, at dette var signifikant mere kompliceret i den rekursive opløsning. Og jeg har sagt flere gange at den rekursive løsning normalt har meget til fælles med den iterative løsning. Her er det præcis, hvad den rekursive løsning gør. Den eneste ændring er, at i stedet for implicit at bruge stakken, programmet stakken, som din måde at holde styr på, hvad emner, du stadig nødt til at besøge, nu er du nødt til eksplicit bruge en sammenkædet liste. I begge tilfælde er du holde styr på, hvad knude stadig mangler at blive besøgt. I det rekursive tilfælde er det bare lettere, fordi en stak er implementeret for dig som programmet stakken. Bemærk, at dette er forbundet liste, er en stabel. Uanset hvad vi lige har lagt på stakken er det samme, hvad vi kommer til at trække ud stakken for at besøge næste. Vi har ikke mere tid, men nogen spørgsmål? [Studerende, uforståelig] [Bowden] Yeah. Så hvis vi har vores linkede liste, strøm kommer til at pege på denne fyr, og nu er vi bare uddybe vort linkede liste at fokusere på denne fyr. Vi gennemkører over den linkede liste i denne linje. Og så jeg tror vi skal frigøre vores linkede liste og kram en gang før han vendte tilbage sandt eller falsk, er vi nødt til gentage over vores linkede liste og altid hernede, tror jeg, hvis vi cur ret er ikke lig med, tilføje det, så nu vil vi befri cur fordi, ja, vi helt glemmer listen? Yeah. Så det er hvad vi ønsker at gøre her. Hvor er den pointer? Cur var dengang - vi vil en struct liste * 10 lig liste næste. Free liste, list = temp. Og i de tilfælde, hvor vi vender tilbage sandt, har vi brug for at gentage over resten af ​​vores linkede liste befri ting. Det gode ved den rekursive løsning er at frigive tingene betyder blot, popping factorings fra stakken, som vil ske for dig. Så vi er gået fra noget, der er ligesom 3 linjer er svære at tænke-om kode til noget, der er betydeligt mange flere svære at tænke-om linjer kode. Flere spørgsmål? Ok. Vi er gode. Bye! [CS50.TV]