[Powered by Google Translate] [§ 7: Mer komfortabelt] [Rob Bowden] [Harvard University] [Dette er CS50] [CS50.TV] OK. Så som jeg sa i min e-post, dette kommer til å være et binært-tree-intensive delen. Men det er ikke så mange spørsmål. Så vi kommer til å prøve og trekke ut hvert spørsmål og gå inn i smertefulle detalj av alle de beste måtene å gjøre ting på. Så helt i begynnelsen, går vi gjennom eksempler tegninger av binære trær og sånt. Så her: "Husk at en binær treet har noder som ligner på en lenket liste, bortsett fra i stedet for en pekeren er det to: en for venstre 'barn' og en for høyre 'barn'. " Så en binærtreet er akkurat som en lenket liste, bortsett struct kommer til å ha to pekere. Det er trinary trær, som kommer til å ha tre pekere, det er N-ær trær, som bare har en generisk peker at du må da malloc å være store nok til å ha nok pekere til alle mulige barn. Så binærtreet skjer bare for å ha et konstant antall av to. Hvis du vil, kan du gi en lenket liste som unary tre, men jeg tror ikke noen kaller det det. "Tegn en bokser-og-piler diagram av et binært tre node inneholder Nate favoritt nummer, 7, der hvert barn pekeren er null. " Så iPad-modus. 

Det kommer til å være ganske grei. Vi bare skal ha en node, vil jeg tegne det som en firkant. Og jeg vil trekke verdiene her. Så verdien vil gå inn her, og deretter ned her vi vil ha den venstre pekeren til venstre og høyre peker til høyre. Og det er veldig mye så konvensjon for å kalle det venstre og høyre, pekeren navn. Begge disse kommer til å være null. Det vil bare være null, og det vil bare være null. Okay. Så tilbake til her. "Med en lenket liste, vi bare måtte lagre en peker til den første noden i listen for å huske hele lenket liste, eller hele listen. Likeledes med trær, vi bare nødt til å lagre en peker til en enkelt node for å huske hele treet. Denne noden er calle de 'root' av treet. Bygge på diagrammet fra før eller tegne en ny slik at du har en bokser-og-piler skildring av et binært tre med verdien 7, deretter 3 i venstre, deretter 9 på høyre, og deretter 6 på høyre side av den 3 ". La oss se om jeg kan huske alle som i hodet mitt. Så dette kommer til å bli vår root opp her. Vi vil ha noen pekeren et sted, noe som vi kaller rot, og den peker til denne fyren. Nå for å lage en ny node, hva har vi, 3 på venstre? Så en ny node med 3, og det i utgangspunktet peker null. Jeg vil bare sette N. Nå ønsker vi å gjøre det gå til venstre for 7. Så vi endre denne pekeren til nå peker til denne fyren. Og vi gjør det samme. Vi ønsker en 9 over her som i utgangspunktet bare sier null. Vi kommer til å endre denne pekeren, pek på 9, og nå ønsker vi å sette 6 til høyre for tre. Så det kommer til å - lage en 6. Og at fyren vil peke dit. Okay. Så det er alt det ber oss om å gjøre. 

Nå la oss gå over noen terminologi. Vi har allerede snakket om hvordan roten av treet er den øverste node i treet. Den ene inneholder 7. Nodene nederst av treet kalles bladene. Enhver node som bare har null som sine barn er et blad. Så det er mulig, hvis vår binære treet er bare en enkelt node, at et tre er et blad, og det er det. "The 'høyde' av treet er antall hopp du har å gjøre å komme fra toppen til et blad. " Vi får inn, i et sekund, forskjellen mellom balanserte og ubalanserte binære trær, men for nå, den totale høyden av dette treet Jeg vil si er tre, men hvis du teller antall hopp du har å gjøre for å få til 9, så det er egentlig bare en høyde på 2. Akkurat nå er dette en ubalansert binærtreet, men vi vil snakket om balanse når den blir å være relevant. Så nå kan vi snakke om noder i et tre i form i forhold til de andre nodene i treet. Så nå har vi foreldre, barn, søsken, forfedre, og etterkommere. De er ganske sunn fornuft, hva de mener. Hvis vi spør - det er foreldre. Så hva er morselskap for 3? [Studenter] 7. >> Ja. Den av foreldrene er bare kommer til å være hva poeng til deg. Så hva er barn av 7? [Studenter] 3 og 9. >> Ja. Legg merke til at "barn" betyr bokstavelig barn, så 6 ville ikke gjelde, fordi det er som et barnebarn. Men så hvis vi går etterkommere, så hva er etterkommere av 7? [Studenter] 3, 6 og 9. >> Ja. Etterkommere av rotnoden kommer til å være alt i treet, bortsett fra kanskje rotnoden selv, hvis du ikke ønsker å tenke på at en etterkommer. Og til slutt, forfedre, så det er motsatt retning. Så hva er forfedrene til 6? [Studenter] 3 og 7. >> Ja. 9 er ikke inkludert. Det er bare den direkte linjen tilbake til roten kommer til å være deres forfedre. 

"Vi sier at en binær tre er" bestilt "hvis for hver node i treet, alle sine etterkommere på venstre har mindre verdier og alle de på høyre har større verdier. For eksempel er treet over bestilte, men det er ikke den eneste mulige bestilles arrangement. " Før vi kommer til det, en ordnet binærtreet er også kjent som et binært søketre. Her har vi tilfeldigvis kalle det et ordnet binærtreet, men jeg har aldri hørt det kalt en ordnet binærtreet før, og på en quiz er vi mye mer sannsynlig å sette binært søketre. De er en og samme, og det er viktig at du kjenner skillet mellom binære treet og binært søketre. En binær treet er bare et tre som peker på to ting. Hver node peker på to ting. Det er ingen resonnement om de verdiene som den peker til. Så liker over her, siden det er et binært søketre, Vi vet at hvis vi går igjen på 7, så alle de verdier som vi kan muligens nå ved å gå til venstre av 7 må være mindre enn 7. Legg merke til at alle de verdier som er mindre enn 7 er 3 og 6. De er alle til venstre for 7. Hvis vi går til høyre for 7, har alt å være større enn 7, så 9 er til høyre for 7, så vi bra. Dette er ikke tilfelle for et binært tre, for en vanlig binær tre kan vi bare 3 øverst, 7 til venstre, 9 til venstre for 7, det er ingen bestilling av verdier overhodet. Nå vil vi faktisk ikke gjør dette fordi det er kjedelig og unødvendig, men "prøve å trekke så mange bestilte trær som du kan tenke på ved hjelp av tallene 7, 3, 9, og 6. Hvor mange forskjellige arrangementer er det? Hva er høyden av hver av dem? " 

Vi vil gjøre et par, men hovedideen er, dette er på ingen måte en unik representasjon av et binært tre som inneholder disse verdiene. Alt vi trenger er noen binærtreet som inneholder 7, 3, 6, og 9. En annen mulig gyldig en ville være roten er 3, gå til venstre, og det er 6, gå til venstre, og det er 7, gå til venstre, og det er 9. Det er en helt gyldig binært søketre. Det er ikke veldig nyttig, fordi det er akkurat som en lenket liste og alle disse pekerne er bare null. Men det er en gyldig treet. Ja? [Student] Ikke verdiene må være større på høyre? Eller er dette -? >> Disse Jeg mente å gå den andre veien. Det er også - ja, la oss slå det. 9, 7, 6, 3. God fangst. Det har fortsatt å adlyde hva et binært tre søk er ment å gjøre. Så alt til venstre må være mindre enn en gitt node. Vi kan bare flytte, si, dette 6 og sette det her. Nei, det kan vi ikke. Hvorfor får jeg gjøre det? La oss gjøre - her er 6, her er 7, 6 poeng til 3. Dette er fortsatt en gyldig binært søketre. Hva er galt hvis jeg - la oss se om jeg kan komme opp med en ordning. Ja, ok. Så hva er galt med dette treet? Jeg har vel allerede gitt deg et hint om at det er noe galt med den. Hvorfor får jeg gjøre det? Okay. Dette ser rimelig. Hvis vi ser på hver node, som 7, deretter til venstre av 7 er en 3. Så vi har 3, er det ting til høyre for 3 en 6. Og hvis man ser på 6, er det ting til høyre for 6 a 9. Så hvorfor er ikke dette en gyldig binært søketre? [Studenter] 9 er fortsatt til venstre for 7. >> Ja. Det må være sant at alle verdier kan muligens nå ved å gå til venstre for 7 er mindre enn 7. Hvis vi går igjen på 7, får vi til 3, og vi kan fortsatt komme til 6, Vi kan fortsatt komme til 9, men ved å ha gått mindre enn 7, Vi bør ikke være i stand til å få til et tall som er større enn 7. Så dette er ikke en gyldig binært søketre. 

Min bror hadde egentlig et intervju spørsmål som var utgangspunktet dette, bare koden opp noe å validere om et tre er et binært søketre, og så det første han gjorde var bare sjekke for å se hvis venstre og høyre er riktig, og deretter veksle der nede. Men du kan ikke bare gjøre det, du må holde styr av det faktum at nå som jeg har gått igjen på 7, alt i denne subtre må være mindre enn 7. Den korrekte algoritme må holde rede av de grenser som verdiene kan muligens falle igjen Vi vil ikke gå gjennom dem alle. Det er en fin tilbakefall forhold, selv om vi ikke har fått til disse, eller vi vil ikke komme til dem, definere hvor mange det faktisk er. Så det er 14 av dem. Ideen om hvordan du vil gjøre det er matematisk like, du kan plukke noen eneste en å være rotnoden, og hvis jeg plukker 7 for å være rotnoden, så er det, sier noen tall som kan gå være min venstre node, og det er noen tall som kan være min høyre node, men hvis jeg har n totale tallene, og beløpet som kan gå til venstre pluss beløpet som kan gå til høyre er n - 1. Så av de gjenværende tall, må de være i stand til å gå enten til venstre eller høyre. Det virker vanskelig at hvis jeg legger 3 første så alt må gå til venstre, men hvis jeg legger 7, så noen ting kan gå til venstre og noen ting kan gå til høyre. Og ved '3 første "mente jeg alt kan gå til høyre. Det er veldig, du må bare tenke på det som, hvor mange ting kan gå på neste nivå i treet. Og det kommer ut for å være 14, eller du kan tegne dem alle, og da vil du få 14. 

Kommer tilbake hit, "Bestilte binære trær er kult fordi vi kan søke gjennom dem i en svært lik måte å søke over en sortert array. For å gjøre dette, starter vi ved roten og jobbe oss ned treet mot blader, sjekke hver node verdier mot verdiene vi søker etter. Hvis gjeldende node verdi er mindre enn verdien vi leter etter, du går ved siden av noden rett barnet. Ellers går du til nodens venstre barn. På et tidspunkt, vil du enten finne verdien du leter etter, eller du kjører inn i en null, indikerer verdien ikke er i treet. " Jeg må tegne treet vi hadde før, det tar et sekund. Men vi ønsker å se opp om 6, 10, og en er i treet. Så hva det var, 7, 9, 3, 6. Okay. Numrene du ønsker å slå opp, ønsker vi å se opp 6. Hvordan denne algoritmen arbeid? Vel, vi har også noen rot pekeren til treet vårt. Og vi ville gå til roten og si, er denne verdien lik verdien vi leter etter? Så vi leter etter seks, så det er ikke like. Så vi holde det gående, og nå sier vi, ok, så 6 er mindre enn 7. Betyr det at vi ønsker å gå til venstre, eller ønsker vi å gå til høyre? [Student] Venstre. >> Ja. Det er betydelig enklere, er å tegne alt du trenger å gjøre en mulig node av treet og deretter lkke - i stedet for å prøve å tenke i hodet ditt, orden, hvis det er mindre, går jeg til venstre eller gå rett, bare se på dette bildet, er det helt klart at jeg må gå til venstre Hvis denne noden er større enn verdien som jeg leter etter. Slik at du går til venstre, nå er jeg på 3. Jeg vil - 3 er mindre enn verdien jeg ser etter, som er 6. Så vi går til høyre, og nå ender jeg opp på 6, som er verdien jeg leter etter, så jeg kommer tilbake sant. Den neste verdien jeg kommer til å se etter er 10 år. Okay. Så 10, nå, kommer til å - avskåret det - kommer til å følge roten. Nå er 10 kommer til å være større enn 7, så jeg ønsker å se til høyre. Jeg kommer til å komme hit, er 10 kommer til å være større enn 9, så jeg kommer til å ønske å se til høyre. Jeg kom hit, men over her nå er jeg på null. Hva gjør jeg hvis jeg treffer null? [Student] return false? >> Ja. Jeg fant ikke 10. 1 kommer til å være et nesten identisk sak, bortsett fra det er bare kommer til å bli snudd, i stedet for å se ned på høyre side, jeg kommer til å se ned på venstre side. 

Nå tror jeg vi faktisk får til koden. Her er der - åpne opp CS50 apparatet og navigere deg der, men du kan også bare gjøre det i rommet. Det er sannsynligvis ideelt å gjøre det i rommet, fordi vi kan arbeide i verdensrommet. "Først vil vi trenge en ny type definisjon for et binært tre node inneholder int verdier. Bruke standardtekst typedef nedenfor, opprette en ny type definisjon for en node i et binært tre. Hvis du står fast. . . "Blah, blah, blah. Okay. Så la oss sette standardteksten her, typedef struct node, og node. Ja, ok. Så hva er de feltene vi kommer til å ønske i node vårt? [Student] Int og deretter to pekere? >> Int verdi, to pekere? Hvordan skriver jeg pekere? [Student] Struct. >> Jeg skal zoome inn Ja, så struct node * venstre, og struct node * rett. Og husk diskusjonen fra forrige gang, at dette gir ingen mening, gjør dette ingen mening, Dette gir ingen mening. Du trenger alt det for å definere denne rekursiv struct. Ok, så det er hva våre tre kommer til å se ut. Hvis vi gjorde en trinary tre, deretter en node kan se ut B1, B2, struct node * b3, der b er en gren - faktisk har jeg mer hørt det igjen, midten, høyre, men uansett. Vi bare bryr seg om binære, så rett, igjen. "Nå erklærer en global node * variabel for roten av treet." Så vi ikke kommer til å gjøre det. For å gjøre ting litt vanskeligere og mer generalisert, Vi vil ikke ha en global node variabel. I stedet, main vil vi erklære alle våre node ting, og det betyr at under, når vi begynner å kjøre vår inneholder funksjonen og vår innsats funksjon, i stedet for vår inneholder fungerer bare ved hjelp av denne globale node variabel, vi kommer til å ha det ta som et argument treet som vi ønsker den skal behandle. Å ha den globale variabelen var ment å gjøre ting enklere. Vi kommer til å gjøre ting vanskeligere. Nå tar et minutt eller så å bare gjøre denne typen ting, hvor innsiden av hoved du ønsker å opprette dette treet, og det er alt du ønsker å gjøre. Prøv og konstruere dette treet i din viktigste funksjon. 

Okay. Så du trenger ikke engang å ha bygget treet hele veien ennå. Men noen har noe jeg kunne trekke opp å vise hvordan man kan begynne å konstruere et slikt tre? [Student] Noens banging, prøver å komme seg ut. [Bowden] Alle komfortabel med sin tre konstruksjon? [Student] Sure. Det er ikke gjort. >> Det er greit. Vi kan bare fullføre - oh, kan du lagre det? Hurra. Så her har vi - oh, jeg er litt avskåret. Jeg zoomet inn? Zoome inn, bla ut. >> Jeg har et spørsmål. >> Ja? [Student] Når du definerer struct, er ting som initialiseres til noe? [Bowden] Nei >> Ok. Så du ville ha til å initialisere - [Bowden] Nei Når du definerer, eller når du deklarerer en struct, det er ikke initialisert som standard, det er akkurat som om du erklærer en int. Det er akkurat det samme. Det er som hver av de enkelte felt kan ha en søppel verdi i den. >> Og er det mulig å definere - eller å erklære en struct på en måte som det gjør initialisere dem? [Bowden] Ja. Så snarvei initialisering syntaks kommer til å se ut som - Det er to måter vi kan gjøre dette. Jeg tror vi bør samle det å sørge for at Clang også gjør dette. Den rekkefølgen som argumentene som kommer i struct, du setter som rekkefølgen av argumenter innsiden av disse klammeparentes. Så hvis du ønsker å initialisere den til 9 og venstre bli null og deretter til høyre være null, det ville være 9, null, null. Alternativet er, og redaktøren liker ikke denne syntaksen, og det tror jeg vil ha en ny blokk, men alternativet er noe som - her, vil jeg sette den på en ny linje. Du kan eksplisitt si, jeg glemmer den eksakte syntaks. Så du kan eksplisitt løse dem ved navn, og sier: . C, eller. Verdi = 9,. Venstre = NULL. Jeg gjetter disse må være komma. . Høyre = NULL, så denne måten du ikke egentlig trenger å vite rekkefølgen på struct, og når du leser dette, er det mye mer eksplisitt om hva verdien som blir initialisert til. 

Dette skjer for å være en av de tingene som - så, for det meste, C + + er et overordnet sett C. Du kan ta C-kode, flytte den over til C + +, og det bør utarbeide. Dette er en av de tingene som C + + ikke støtter, slik at folk har en tendens til ikke å gjøre det. Jeg vet ikke om det er den eneste grunnen til at folk har en tendens til ikke å gjøre det, men saken der jeg trengte å bruke den trengte å jobbe med C + + og så jeg ikke kunne bruke dette. Et annet eksempel på noe som ikke fungerer med C + + er hvordan malloc returnerer en "void *," teknisk, men du kan bare si char * x = malloc uansett, og den vil automatisk bli kastet til en char *. At automatisk cast skjer ikke i C + +. Det ville ikke kompilere, og du vil eksplisitt trenger å si char *, malloc, uansett, å kaste den til en char *. Det er ikke mange ting som C og C + + er uenige om, men de er to. Så vi vil gå med denne syntaksen. Men selv om vi ikke gå med på at syntaks, hva er - kan være galt med dette? [Student] Jeg trenger ikke å dereference det? >> Ja. Husk at pilen har en implisitt dereferanse, og så når vi bare gjøre med en struct, vi ønsker å bruke. å få på en felt innsiden av struct. Og den eneste gangen vi bruker pil er når vi ønsker å gjøre - vel, er arrow tilsvarer - det er hva det ville ha betydd hvis jeg brukte pil. Alle pilen betyr er, dereferanse dette, nå er jeg på en struct, og jeg kan få feltet. Enten få feltet direkte eller dereferanse og få felt - Jeg antar at dette bør være verdi. Men her jeg arbeider med bare en struct, ikke en peker til en struct, og så jeg kan ikke bruke pilen. Men denne typen ting vi kan gjøre for alle noder. Herregud. Dette er 6, 7 og 3. Da kan vi sette opp avdelinger i treet vårt, kan vi ha 7 - Vi kan ha, bør dens venstre peke til tre. Så hvordan gjør vi det? [Studenter, uforståelig] >> Ja. Adressen til node3, og hvis du ikke har adresse, så det bare ikke ville kompilere. Men husk at disse er pekere til de neste noder. Retten skal peke til 9, og 3 skal peke på høyre til 6. Jeg tror dette er alle satt. Eventuelle kommentarer eller spørsmål? [Student, uforståelig] Roten skal være 7. Vi kan bare si node * ptr = eller rot, = & node7. 

For vårt formål, vi kommer til å være håndtere insert, så vi kommer til å ønske å skrive en funksjon for å sette inn dette binærtreet og innsatsen er uunngåelig kommer til å ringe malloc å opprette en ny node for dette treet. Så ting kommer til å bli rotete med det faktum at noen noder er for tiden på stakken og andre noder kommer til å ende opp på haugen når vi setter dem. Dette er helt gyldig, men den eneste grunnen vi er i stand til å gjøre dette på stakken er fordi det er en så contrived eksempel på at vi vet treet er ment å være konstruert som 7, 3, 6, 9. Hvis vi ikke har dette, så vi ikke ville ha til malloc i første omgang. Som vi skal se litt senere, bør vi malloc'ing. Akkurat nå er det helt rimelig å sette på stakken, men la oss endre dette til en malloc gjennomføring. Slik at hver av disse er nå kommer til å være noe som node * node9 = malloc (sizeof (node)). Og nå er vi nødt til å gjøre vår sjekk. if (node9 == NULL) - Jeg ønsker ikke at - returnere 1, og da kan vi gjøre node9-> fordi nå er det en peker, value = 6, node9-> venstre = NULL, node9-> høyre = NULL, og vi er nødt til å gjøre det for hver av disse nodene. Så i stedet, la oss si det på innsiden av en egen funksjon. La oss kalle det node * build_node, og dette er noe som ligner på APIer vi sørge for Huffman koding. Vi gir deg initializer funksjoner for et tre og Deconstructor "funksjoner" for disse trærne, og det samme for skog. 

Så her vi kommer til å ha en initializer funksjon å bare bygge en node for oss. Og det kommer til å se ganske mye akkurat som dette. Og jeg selv kommer til å være lat og ikke endre navnet på variabelen, selv om node9 gir ingen mening lenger. Oh, I guess node9 verdi ikke skulle ha vært seks. Nå kan vi gå tilbake node9. Og her vi bør gå tilbake null. Alle er enige om at build-a-node funksjon? Så nå kan vi bare kalle det å bygge noen node med en gitt verdi og null pekere. Nå kan vi kalle det, kan vi gjøre node * node9 = build_node (9). Og la oss gjøre. . . 6, 3, 7, 6, 3, 7. Og nå ønsker vi å sette opp de samme pekere, bortsett fra nå alt er allerede i form av pekere så ikke lenger trenger adressen. Okay. Så hva er det siste jeg ønsker å gjøre? Det er en feilkontroll som jeg ikke gjør. Hva bygger node retur? [Student, uforståelig] >> Ja. Hvis malloc mislyktes, vil den komme tilbake null. Så jeg kommer til å lazily sette det ned her i stedet for å gjøre en betingelse for hver. If (node9 == NULL, eller - enda enklere, Dette tilsvarer bare hvis ikke node9. Så hvis ikke node9, eller ikke node6, eller ikke node3, eller ikke node7, tilbake 1. Kanskje vi bør skrive malloc mislyktes, eller noe. [Student] Er falsk lik null også? [Bowden] Enhver null verdi er falsk. Så null er en null verdi. Zero er et null. Falsk er en nullverdi. Noen - ganske mye bare 2 null verdier er null og null, falsk er bare hash definert som null. Dette gjelder også hvis vi erklærer global variabel. Hvis vi hadde node * rot her oppe, da - den fine ting om globale variabler er at de alltid har en initial verdi. Det er ikke sant av funksjoner, hvor innsiden av her, hvis vi har, som, node * eller node x. Vi har ingen anelse om hva x.value, x.whatever, eller vi kan skrive dem ut, og de kan være vilkårlig. Det er ikke sant av globale variabler. Så node rot eller node x. Som standard, alt som er global, hvis ikke eksplisitt initialisert til en viss verdi, har null verdi som verdi. Så her, node * rot, har vi ikke eksplisitt initialisere den til noe, så standardverdien vil være null, som er det null verdi av pekere. Standardverdien av x kommer til å bety at x.value er null, x.left er null, og x.right er null. Så siden det er en struct, vil alle feltene i struct være nullverdier. Vi trenger ikke å bruke den her, skjønt. [Student] De structs er annerledes enn andre variabler, og de andre variablene er søppel verdier, disse er nuller? [Bowden] Andre verdier også. Så i x, vil x være null. Hvis det er på global omfang, har det en initial verdi. >> Ok. [Bowden] Enten den opprinnelige verdien du gav den eller null. Jeg tror det tar seg av alt dette. 

Okay. Så den neste delen av spørsmålet spør, "Nå ønsker vi å skrive en funksjon som heter inneholder med en prototype av bool inneholder int verdi. " Vi kommer ikke til å gjøre bool inneholder int verdi. Vår prototype kommer til å se ut som bool inneholder (int verdi. Og så er vi også kommer til å passere det treet at det bør sjekke for å se om det har den verdien. Så node * tree). Okay. Og så kan vi kalle det med noe sånt som, kanskje vi ønsker å printf eller noe. Inneholder 6, vår rot. Det burde returnere en eller sant, mens inneholder 5 root skal returnere false. Så ta et sekund å gjennomføre dette. Du kan gjøre det enten iterativt eller rekursivt. Det fine med måten vi har satt opp ting er at det gir seg til vår rekursiv løsning mye enklere enn den globale variable måte gjorde. Fordi hvis vi bare har inneholder int verdi, så vi har ingen måte å recursing ned undertreene. Vi må ha en egen hjelper funksjon som recurses ned undertrær for oss. Men siden vi har endret det til å ta treet som et argument, som det bør har alltid vært i første omgang, Nå kan vi Recurse lettere. Så iterativ eller rekursive, vil vi gå over begge, men vi får se at rekursive ender opp med å bli ganske lett. Okay. Har noen noe vi kan jobbe med? 

[Student] Jeg har en iterativ løsning. >> Greit, iterativ. Ok, ser dette bra. Så, ønsker å lede oss gjennom det? [Student] Sure. Så jeg satt en temp variabel å få den første noden i treet. Og da jeg bare sløyfe mens temp ikke lik null, så mens var fortsatt i treet, antar jeg. Og hvis verdi er lik den verdi som temp peker til, da den returnerer den verdien. Ellers sjekker den om det er på høyre eller venstre side. Hvis du noen gang får en situasjon der det ikke er mer tre, så det returnerer - det kommer loopen og returnerer false. [Bowden] Okay. Så det virker bra. Noen som har noen kommentarer til noe? Jeg har ingen korrekthet kommentarer i det hele tatt. Det eneste vi kan gjøre er denne fyren. Å, det kommer til å gå litt ovale. Jeg skal fikse det opp. Okay. 

Alle bør huske hvordan trefoldig fungerer. Det har definitivt vært quizer i det siste som gir deg en funksjon med en trefoldig operatør, og si, oversette dette, gjør noe som ikke bruker trefoldig. Så dette er en veldig vanlig tilfelle av når jeg ville tenke å bruke trefoldig, der hvis noen betingelse sette en variabel til noe, andre satt den samme variabelen til noe annet. Det er noe som svært ofte kan bli forvandlet til denne typen ting der satt den variabelen til dette - eller, vel, er dette sant? Da er dette, annet denne. [Student] Den første er hvis det er sant, ikke sant? [Bowden] Yeah. Slik jeg alltid lest det er, lik temp verdi større enn temp verdi, så dette, annet denne. Det er stille et spørsmål. Er det større? Deretter må du gjøre det første. Andre gjøre andre ting. Jeg nesten alltid - tykktarmen, jeg bare - i hodet mitt, jeg leste som ellers. 

Har noen en rekursiv løsning? Okay. Dette skal vi - det kan allerede være stor, men vi kommer til å gjøre det enda bedre. Dette er ganske mye de samme idé. Det er bare, vel, vil du forklare? [Student] Sure. Så vi å sørge for at treet ikke er null først, fordi hvis treet er null så det kommer til å returnere falsk fordi vi ikke har funnet det. Og hvis det er fortsatt et tre, går vi inn i - vi først sjekke om det er den gjeldende node. Returnere true hvis det er, og hvis ikke vi Recurse på venstre eller høyre. Høres det riktig? >> Mm-hmm. (Avtalen) Så merke til at dette er nesten - strukturelt veldig lik den iterativ løsning. Det er bare at i stedet for recursing, hadde vi en stund loop. Og base case her hvor tre er ikke lik null var tilstanden under som vi brøt ut av mens loop. De er veldig like. Men vi kommer til å ta dette ett skritt videre. Nå gjør vi det samme her. Legg merke til vi er tilbake det samme i begge disse linjene, med unntak av én argument er annerledes. Så vi kommer til å gjøre det til en trefoldig. Jeg traff alternativ noe, og det gjorde et symbol. Okay. Så vi kommer til å returnere inneholder det. Dette blir å være flere linjer, vel, zoomet inn det er. Vanligvis, som et stilistisk ting, tror jeg ikke mange mennesker sette et mellomrom etter pilen, men jeg antar at hvis du er konsekvent, det er greit. Hvis verdien er mindre enn tre verdi, ønsker vi å Recurse på treet til venstre, annet vi ønsker å Recurse på treet rett. Så det var trinn en til å gjøre dette ser mindre. Trinn to for å gjøre dette ser mindre - Vi kan skille dette til flere linjer. Okay. Trinn to for å gjøre det ser mindre er her, så returverdi lik tre verdi, eller som inneholder hva. 

Dette er en viktig ting. Jeg er ikke sikker på om han sa det eksplisitt i klassen, men det heter kortslutning evaluering. Ideen her er verdi == tre verdi. Hvis det er sant, så er dette sant, og vi ønsker å 'eller' det med alt som er over her. Så uten engang å tenke på det som er over her, hva er hele uttrykket kommer til å returnere? [Student] True? >> Ja, fordi sann av noe, or'd - eller sann or'd med noe er nødvendigvis sant. Så så snart vi ser returverdi = tre verdi, vi bare kommer til å returnere true. Ikke engang tenkt å Recurse inneholder ytterligere ned linjen. Vi kan ta dette ett skritt videre. Tilbake treet ikke lik null, og alt dette. Det gjorde det en en-linje funksjon. Dette er også et eksempel på kortslutning evaluering. Men nå er det den samme ideen - i stedet for - så hvis treet ikke lik null - eller, vel, hvis treet ikke lik null, som er det dårlig sak, hvis treet er lik null, så den første betingelsen kommer til å være falsk. Så falske anded med noe kommer til å være hva? [Student] False. >> Ja. Dette er den andre halvparten av kortslutning evaluering, der hvis treet ikke lik null, da vi ikke kommer til å selv gå - eller hvis treet ikke lik null, da vi ikke kommer til å gjøre verdien == tre verdi. Vi bare kommer til å umiddelbart returnere falsk. Som er viktig, siden hvis det ikke kortslutning vurdere, så hvis treet ikke lik null, er denne andre betingelsen skal SEG utsette, fordi tree-> verdi dereferencing null. Så det er det. Kan gjøre dette - skifte en gang over. Dette er en veldig vanlig ting også, ikke gjør dette en tråd med dette men det er en vanlig ting i forhold, kanskje ikke akkurat her, men hvis (tre! = NULL, og tre-> verdi == verdi), gjøre hva. Dette er en svært vanlig tilstand, der i stedet for å ha å bryte denne inn i to ifs, der liker, er treet null? Ok, det er ikke null, så nå er det tre verdi lik verdi? Gjør dette. I stedet denne tilstanden, vil dette aldri SEG feil fordi det vil bryte ut dersom dette skjer for å være null. Vel, jeg antar at hvis treet er en helt ugyldig peker, kan det fortsatt SEG feil, men det kan ikke SEG feil hvis treet er null. Hvis det var null, ville det bryte ut før du noensinne derefereres pekeren i første omgang. [Student] Er dette kalles lat evaluering? 

[Bowden] Lazy evaluering er en egen ting. Lat evaluering er mer som du ber om en verdi, du be om å beregne en verdi, type, men du trenger ikke det umiddelbart. Så før du faktisk trenger det, er det ikke evaluert. Dette er ikke akkurat det samme, men i Huffman pset, det står at vi "dovent" skriver. Grunnen til at vi gjør det er fordi vi faktisk bufring skrive - Vi ønsker ikke å skrive individuelle biter av gangen, eller individuelle bytes gangen, vi i stedet ønsker å få en del av bytes. Så når vi har en del av bytes, så får vi skrive det ut. Selv om du ber om det å skrive - og fwrite og fread gjøre det samme slags ting. De buffer din leser og skriver. Selv om du spør om det å skrive med en gang, det vil sannsynligvis ikke. Og du kan ikke være sikker på at ting kommer til å bli skrevet før du ringer hfclose eller hva det er, som deretter sier, ok, jeg lukker filen min, det betyr at jeg hadde bedre skrive alt jeg har ikke skrevet ennå. Det har ikke trenger å skrive alt ut til du lukker filen, og da er det behov for. Så det er akkurat hva lat - det venter til det har å skje. Dette - ta 51 og du vil gå inn i det i mer detalj, fordi OCaml og alt i 51, er alt rekursjon. Det er ingen iterativ løsninger, i utgangspunktet. Alt er rekursjon, og lat evaluering kommer til å være viktig for mange omstendigheter der, hvis du ikke dovent evaluere, ville det bety - Eksempelet er bekker, som er uendelig lang. I teorien kan du tenke på de naturlige tall som en strøm av 1-2-3-4-5-6-7, Så dovent evaluert ting er bra. Hvis jeg sier jeg vil ha den tiende nummer, så jeg kan vurdere opp til tiende nummeret. Hvis jeg vil hundrede nummer, så jeg kan vurdere opp til hundredel nummer. Uten lat evaluering, så det kommer til å prøve å evaluere alle tall umiddelbart. Du evaluerer uendelig mange tall, og det er bare ikke mulig. Så det er mange tilfeller der lat evaluering er bare viktig for å få ting til å fungere. 

Nå ønsker vi å skrive innlegget der innsatsen skal være tilsvarende endring i definisjonen. Så akkurat nå er det bool innsats (int verdi). Vi kommer til å endre det til bool innsats (int verdi, node * treet). Vi faktisk kommer til å endre det igjen i en bit, vil vi se hvorfor. Og la oss flytte build_node, bare for pokker av det, ovenfor setter så vi ikke trenger å skrive en funksjon prototype. Som er et hint om at du kommer til å bruke build_node i innsatsen. Okay. Ta et minutt for det. Jeg tror jeg reddet revisjonen hvis du ønsker å trekke fra det, eller i det minste, jeg gjorde nå. Jeg ønsket en liten pause for å tenke på logikk innsatsen, hvis du ikke kan tenke på det. I utgangspunktet vil du bare bli lagt på bladene. Som, hvis jeg setter en, så jeg uunngåelig kommer til å bli lagt 1 - Jeg kommer til å endre til sort - Jeg skal bli lagt en over her. Eller hvis jeg setter 4, vil jeg bli lagt 4 over her. Så uansett hva du gjør, du kommer til å bli lagt på et blad. Alt du trenger å gjøre er iterate ned treet til du kommer til noden som bør være noden overordnede, den nye nodens forelder, og deretter endrer sin venstre eller høyre pekeren, avhengig av om den er større enn eller mindre enn den gjeldende node. Endre det pekeren å peke på den nye noden. Så iterate ned treet, gjør bladet peker til den nye noden. Også tenke på hvorfor det forbyr den type situasjon før, der jeg bygget det binære treet der det var riktig hvis du bare så på en enkelt node, men 9 var til venstre for 7 hvis du iterated ned hele veien. Så det er umulig i dette scenariet, siden - tenker på å sette inn 9 eller noe, på den aller første noden, Jeg kommer til å se 7 og jeg bare kommer til å gå til høyre. Så uansett hva jeg gjør, hvis jeg setter inn ved å gå til et blad, og til et blad ved hjelp av riktig algoritme, det kommer til å være umulig for meg å sette 9 til venstre for 7 fordi så snart jeg traff 7 jeg kommer til å gå til høyre. Har noen noe å starte med? [Student] jeg gjør. >> Ja. [Student, uforståelig] [Other student, uforståelig] [Bowden] Det er verdsatt. Okay. Vil du forklare? 

[Student] Siden vi vet at vi setter nye noder på slutten av treet, Jeg løkke gjennom treet iterativt før jeg kom til en node som pekte til null. Og da jeg bestemte meg for å sette det enten på høyre eller venstre side bruker denne retten variabel, det fortalte meg hvor du vil plassere den. Og så, i hovedsak, jeg bare gjort det siste - at temp node peker til den nye noden som det var å skape, enten på venstre eller på høyre side, avhengig av hva verdien høyre var. Slutt stiller jeg den nye noden verdien til verdien av testingen sin. [Bowden] Ok, så jeg ser ett problem her. Dette er som 95% av veien dit. Det eneste problemet jeg ser, vel, ikke se noen andre et problem? Hva er det forhold under hvilke de skal bryte ut av loopen? [Student] Hvis temp er null? >> Ja. Så hvordan kan du bryte ut av loopen er hvis temp er null. Men hva gjør jeg her? Jeg dereferanse temp, som er uunngåelig null. Så den andre tingen du trenger å gjøre er ikke bare å holde styr før temp er null, du ønsker å holde styr på den overordnede til alle tider. Vi ønsker også node * forelder, tror jeg vi kan holde det på null først. Dette kommer til å ha rar oppførsel for roten av treet, men vi kommer til det. Hvis verdien er større enn hva, så temp = temp rett. Men før vi gjør det, foreldre = temp. Eller er foreldre alltid kommer til å like temp? Er det tilfelle? Hvis temp er ikke null, så jeg kommer til å flytte ned, uansett hva, til en node som temp er morselskap. Så foreldre kommer til å bli temp, og da jeg flytter temp ned. Nå temp er null, men foreldre peker den overordnede av det som er null. Så her nede, jeg ønsker ikke å rette tilsvarer 1. Så flyttet jeg til høyre, så hvis høyre = 1, og jeg antar du også ønsker å gjøre - hvis du flytter til venstre, vil du sette rett lik 0.. Eller annet hvis du skulle flytte til høyre. Så rett = 0. Hvis høyre = 1, nå ønsker vi å gjøre den overordnede rett pekeren newnode, annet vi ønsker å gjøre den overordnede venstre pekeren newnode. Spørsmål om det? Okay. Så dette er måten vi - vel, egentlig, i stedet for å gjøre dette, vi halvparten forventet du å bruke build_node. Og så hvis newnode lik null, returnerer false. Det er det. Nå, dette er hva vi forventet at du skal gjøre. 

Dette er hva de ansatte løsningene. Jeg er uenig med dette som den "riktige" måten å gå om det men dette er helt greit, og det vil fungere. En ting som er litt rart akkurat nå er Hvis treet begynner som null, passerer vi et null tre. Jeg antar det avhenger av hvordan du definerer oppførselen til bestått i en null tre. Jeg vil tro at hvis du passerer i en null tre, deretter sette verdien til en null tre bør bare returnere et tre der den eneste verdien er at én node. Folk er enig med det? Du kan, hvis du ville, hvis du passerer i en null tre og du vil sette inn en verdi i det, return false. Det er opp til deg å definere det. For å gjøre det første jeg sa og da - vel, du kommer til å ha problemer med å gjøre det, fordi det ville være lettere om vi hadde en global peker til ting, men vi ikke, så hvis treet er null, er det ingenting vi kan gjøre med det. Vi kan bare returnere false. Så jeg kommer til å endre innsatsen. Vi teknisk kunne bare endre dette her, hvordan det gjentar over ting, men jeg kommer til å endre innsatsen for å ta en node ** treet. Doble pekere. Hva betyr dette? I stedet for å håndtere med pekere til noder, tingen jeg kommer til å være manipulere er denne pekeren. Jeg kommer til å være manipulere denne pekeren. Jeg kommer til å være manipulere pekere direkte. Dette er fornuftig siden, tenk ned - vel, akkurat nå dette peker til null. Hva jeg vil gjøre er å manipulere denne pekeren å peke på ikke null. Jeg vil at det skal peke til min nye node. Hvis jeg bare holde styr på pekere til mine pekere, så jeg ikke trenger å holde styr på en forelder pekeren. Jeg kan bare holde styr for å se om pekeren peker til null, og hvis pekeren peker til null, endre det til å peke på noden jeg ønsker. Og jeg kan endre det siden jeg har en peker til pekeren. La oss se på dette akkurat nå. Du kan faktisk gjøre det rekursivt ganske enkelt. Ønsker vi å gjøre det? Ja, det gjør vi. 

La oss se det rekursivt. Først, er hva våre base case kommer til å bli? Nesten alltid vår base case, men faktisk er dette slags kinkig. First things first, if (tre == NULL) Jeg antar vi bare kommer til å returnere falsk. Dette er forskjellig fra treet blir null. Dette er pekeren til root pekeren blir null noe som betyr at root pekeren ikke eksisterer. Så her nede, hvis jeg gjør node * - la oss bare bruke denne. Node * root = NULL, og da kommer jeg til å ringe innsatsen ved å gjøre noe sånt, Sett 4 inn og rot. Så & rot, hvis rot er en node * da og rot kommer til å være en node **. Dette er gyldig. I dette tilfellet, treet, opp her, Treet er ikke null - eller innsats. Her. Treet er ikke null; * treet er null, noe som er bra fordi hvis * treet er null, så jeg kan manipulere det til nå peke på hva jeg vil den skal peke til. Men hvis treet er null, betyr det at jeg bare kom ned hit og sa null. Det gir ikke mening. Jeg kan ikke gjøre noe med det. Hvis treet er null, returnerer false. Så jeg i utgangspunktet allerede sagt hva vår virkelige base case er. Og hva kommer det til å bli? [Student, uforståelig] [Bowden] Ja. Så hvis (* tre == NULL). Dette relaterer seg til saken over her der hvis min røde pekeren er pekeren jeg fokusert på, så liker jeg fokusert på denne pekeren, nå er jeg fokusert på denne pekeren. Nå er jeg fokusert på denne pekeren. Så hvis min røde pekeren, som er min node **, er noensinne - hvis *, min røde pekeren, er stadig null, det betyr at jeg er på saken hvor jeg fokuserer på en peker som peker - dette er en peker som tilhører et blad. Jeg ønsker å endre denne pekeren å peke på min nye node. Kom tilbake hit. Min newnode vil bare være node * n = build_node (verdi) deretter n, hvis n = NULL, return false. Annet vi ønsker å endre hva pekeren nå peker til til nå peke til vår nybygde node. Vi kan faktisk gjøre det her. Stedet for å si n, sier vi * treet = hvis * treet. Alle forstår det? Som ved å dele med pekere til pekere, Vi kan endre null pekere til å peke på ting vi vil at de skal peke til. Det er vår base case. 

Nå vår tilbakefall, eller vår rekursjon, kommer til å være svært lik alle andre rekursjoner vi har gjort. Vi kommer til å ønske å sette verdi, og nå skal jeg bruke trefoldig igjen, men hva er vår tilstand skal være? Hva er det vi leter etter for å avgjøre om vi ønsker å gå til venstre eller høyre? La oss gjøre det i separate trinn. Hvis (verdi <) hva? [Student] Treets verdi? [Bowden] Så husk at jeg er for tiden - [Studenter, uforståelige] [Bowden] Yeah, så akkurat her, la oss si at dette grønn pil er et eksempel på hva treet øyeblikket er, er en peker til denne pekeren. Så det betyr at jeg er en peker til en peker til tre. Den dereferanse to ganger hørtes bra. Hva gjør jeg - hvordan gjør jeg det? [Student] dereferanse gang, og gjør deretter pilen på den måten? [Bowden] So (* tree) er dereferanse gang, -> verdi kommer til å gi meg verdien av noden som jeg indirekte peker til. Så jeg kan også skrive det ** tree.value hvis du foretrekker det. Enten fungerer. Hvis det er tilfelle, så vil jeg kalle inn med verdi. Og hva er min oppdaterte node ** kommer til å bli? Jeg ønsker å gå til venstre, så ** tree.left kommer til å være min venstre. Og jeg vil at pekeren skal den tingen slik at hvis venstre ender opp med å bli nullpeker, Jeg kan endre det til å peke på min nye node. 

Og det andre tilfellet kan være svært like. La oss faktisk gjøre at trefoldig min akkurat nå. Sett verdi hvis verdi <(** tree). Verdi. Så vi ønsker å oppdatere våre ** til venstre, annet vi ønsker å oppdatere våre ** til høyre. [Student] Blir at pekeren til pekeren? [Bowden] Husk at - ** tree.right er en node stjerne. [Student, uforståelig] >> Ja. ** Tree.right er som denne pekeren eller noe. Så ved å ta en peker til det, gir det meg hva jeg vil av pekeren til den fyren. [Student] Kan vi gå over igjen hvorfor vi bruker de to pekere? [Bowden] Yeah. Så - Nei, det kan du, og at løsningen før var en måte å gjøre det uten å gjøre to pekere. Du må være i stand til å forstå ved hjelp av to pekere, og dette er et renere løsning. Legg også merke til det, hva skjer hvis mitt tre - hva skjer hvis min root var null? Hva skjer hvis jeg gjør denne saken her? Så node * root = NULL, sett 4 inn og rot. Hva er roten kommer til å være etter dette? [Student, uforståelig] >> Ja. Root verdi kommer til å være 4. Root venstre skal være null, er roten til høyre kommer til å være null. I tilfellet hvor vi ikke pass rot etter adresse, vi kunne ikke endre rot. I tilfellet hvor treet - hvor rot var null, vi bare måtte returnere falsk. Det er ingenting vi kan gjøre. Vi kan ikke sette inn en node i et tomt tre. Men nå kan vi, vi bare gjør en tom tre inn i et node treet. Som vanligvis er forventet måte at det er ment å fungere. 

Videre er dette vesentlig kortere enn også holde styr på den overordnede, og slik at du iterate ned hele veien. Nå har jeg mine foreldre, og jeg må bare mine foreldre rett pekeren til uansett. I stedet, hvis vi gjorde dette iterativt, ville det være det samme ideen med en stund loop. Men i stedet for å måtte forholde seg til mine foreldre pekeren, i stedet min nåværende pekeren ville være tingen at jeg direkte endre å peke på min nye node. Jeg trenger ikke å forholde seg til om den peker til venstre. Jeg trenger ikke å forholde seg til om den peker mot høyre. Det er akkurat hva denne pekeren er, kommer jeg til å sette den til å peke på min nye node. Alle forstår hvordan det fungerer? Hvis ikke, hvorfor vi ønsker å gjøre det på denne måten, men i det minste at dette fungerer som en løsning? [Student] Hvor får vi tilbake sant? [Bowden] Det er nok rett her. Hvis vi riktig sett den, return true. Else, her nede vi kommer til å ønske å gå tilbake uansett insert avkastning. 

Og hva er spesielt med denne rekursive funksjonen? Det er halen rekursive, så så lenge vi kompilere med noen optimalisering, det vil gjenkjenne det og du vil aldri få en stack overflow fra dette, selv om vår treet har en høyde på 10.000 eller 10 millioner kroner. [Student, uforståelig] [Bowden] Jeg tror det gjør det på Dash - eller hva optimalisering nivå er nødvendig for en hale rekursjon å bli gjenkjent. Jeg tror det anerkjenner - GCC og Clang også ha forskjellige betydninger for deres optimalisering nivåer. Jeg vil si det er 2 DashO, for at det vil anerkjenne halen rekursjon. Men vi - du kan konstruere som en Fibonocci eksempel eller noe. Det er ikke lett å teste med dette, fordi det er vanskelig å lage et binært tre som er så stor. Men ja, jeg tror det er 2 DashO, som Hvis du kompilere med DashO 2, vil det se etter halen rekursjon og optimalisere det ut. La oss gå tilbake til - sett er bokstavelig talt det siste den trenger. La oss gå tilbake til innsatsen over her hvor vi kommer til å gjøre den samme ideen. Det vil fortsatt ha feil av ikke å kunne helt håndtere når roten selv er null, eller det siste oppføringen er null, men i stedet for å håndtere en forelder peker, la oss bruke den samme logikken holde pekere til pekere. Hvis det her vi holder vår node ** nå, og vi trenger ikke å holde styr på riktig lenger, men node ** nå = & tre. Og nå vår mens loop kommer til å være mens * nå ikke lik null. Trenger ikke å holde styr på foreldrene lenger. Trenger ikke å holde styr på venstre og høyre. Og jeg vil kalle det temp, fordi vi allerede bruker temp. Okay. Så hvis (verdi> * temp), da & (* temp) -> høyre ellers temp = & (* temp) -> venstre. Og nå, på dette punktet, etter dette mens loop, Jeg bare gjør dette fordi kanskje det er lettere å tenke iterativt enn rekursivt, men etter dette mens loop, * Temp er pekeren vi ønsker å endre. 

Før vi hadde foreldre, og vi ønsket å endre en av foreldrene til venstre eller forelder høyre, men hvis vi ønsker å endre overordnede høyre, deretter * temp er foreldre rett, og vi kan endre det direkte. Så her nede, kan vi gjøre * temp = newnode, og det er det. Så varsel, var alt vi gjorde i dette ta ut linjer med kode. For å holde styr på den overordnede i alt som er ekstra innsats. Her, hvis vi bare holde styr på pekeren til pekeren, og selv om vi ønsket å kvitte seg med alle disse klammeparentes nå, at det ser kortere. Dette er nå nøyaktig samme løsning, men færre linjer med kode. Når du begynner å gjenkjenne dette som en gyldig løsning, det er også lettere å resonnere om enn liker, ok, hvorfor har jeg denne flagget på int rett? Hva betyr det? Å, det er et tegn på at hver gang jeg går rett, jeg trenger å sette den, annet hvis jeg går dro jeg trenger å sette den til null. Her har jeg ikke til grunn om det, det er bare lettere å tenke på. Spørsmål? [Student, uforståelig] >> Ja. Ok, så i den siste bit - Jeg antar en rask og enkel funksjon vi kan gjøre er, let's - sammen, antar jeg, prøve og skrive en inneholder funksjon som bryr seg ikke om det er et binært søketre. Dette inneholder funksjonen skal returnere true hvis hvor som helst i denne generelle binære treet er verdien vi leter etter. Så la oss først gjøre det rekursivt og så får vi gjøre det iterativt. Vi kan faktisk bare gjøre det sammen, fordi dette kommer til å bli veldig kort. 

Hva er min base case kommer til å bli? [Student, uforståelig] [Bowden] Så hvis (treet == NULL), hva så? [Student] return false. [Bowden] Else, vel, jeg trenger ikke det andre. Hvis var min andre base case. [Student] Tre verdi? >> Ja. Så hvis (tree-> verdi == verdi. Legg merke til vi er tilbake til node *, ikke node ** s? Inneholder vil aldri trenger å bruke en node **, siden vi ikke endrer pekere. Vi bare krysser dem. Hvis det skjer, så vi ønsker å returnere true. Annet vi ønsker å traversere barna. Så vi kan ikke resonnere om hvorvidt alt til venstre er mindre og alt til høyre er større. Så hva er vår tilstand kommer til å være her - eller, hva skal vi gjøre? [Student, uforståelig] >> Ja. Return inneholder (verdi, tree-> venstre) eller inneholder (verdi, tree-> høyre). Og det er det. Og legg merke til at det er noen kortslutning evaluering, der hvis vi måtte finne verdien i venstre treet, vi aldri trenger å se på høyre treet. Det er hele funksjonen. Nå la oss gjøre det iterativt, som kommer til å bli mindre hyggelig. Vi tar den vanlige starten av node * nå = treet. Mens (nå! = NULL). Raskt kommer til å se et problem. Hvis nå - her ute, hvis vi noen gang bryte ut av dette, så vi har kjørt ut av ting å se på, så return false. Hvis (nå-> verdi == verdi), return true. Så nå er vi på et sted - Vi vet ikke om vi ønsker å gå til venstre eller høyre. Så vilkårlig, la oss bare gå til venstre. Jeg har tydeligvis kjørt inn i et problem der jeg har helt forlatt alt - Jeg vil bare noensinne sjekker venstre side av et tre. Jeg vil aldri se noe som er en riktig barn av noe. Hvordan fikser jeg dette? [Student] Du må holde styr på venstre og høyre i en stabel. [Bowden] Yeah. Så la oss gjøre det struct listen, node * n, og deretter node ** neste? Jeg tror det fungerer fint. Vi ønsker å gå over til venstre, eller let's - her oppe. Struct Ønskeliste =, vil den starte ut på dette struct listen. * List = NULL. Så det kommer til å bli vår lenket liste av undertreene som vi har hoppet over. Vi kommer til å traversere igjen nå, men siden vi uunngåelig må komme tilbake til høyre, Vi kommer til å holde høyre side inne i vår struct liste. Da vil vi ha new_list eller struct, struct listen *, new_list = malloc (sizeof (liste)). Jeg kommer til å ignorere feil-sjekking det, men du bør sjekke for å se om det er null. New_list noden det kommer til å peke på - oh, det er derfor jeg ønsket det opp her. Det kommer til å peke på en annen struct liste. Det er bare hvordan koblet lister arbeid. Dette er det samme som en int lenket liste bortsett vi bare erstatte int med node *. Det er akkurat det samme. Så new_list, verdien av vår new_list node, kommer til å være nå-> høyre. Verdien av vår new_list-> neste kommer til å bli vår opprinnelige liste, og vi kommer til å oppdatere vår liste for å peke på new_list. 

Nå trenger vi en slags måte å trekke ting, som vi har krysset hele venstre subtre. Nå må vi trekke ting ut av det, som nå er null, vi ønsker ikke å bare returnere false. Vi ønsker å nå trekke utenfor på vår nye liste. En praktisk måte å gjøre dette - vel, egentlig, det er flere måter å gjøre dette. Alle som har et forslag? Hvor jeg skal gjøre dette eller hvordan jeg skal gjøre dette? Vi har bare et par minutter, men noen forslag? I stedet for - en vei, i stedet for tilstanden vår tilværelse stund, hva vi for øyeblikket ser på er ikke null, stedet vi kommer til å fortsette å gå til vår liste seg selv er null. Så hvis vår liste ender opp som null, da har vi kjørt ut av ting å se etter, for å søke over. Men det betyr at det første i vår liste er bare kommer til å være den første noden. Den aller første vil være - vi ikke lenger trenger å se det. Så list-> n vil være vår treet. list-> neste kommer til å bli null. Og nå mens listen er ikke lik null. Cur kommer til å trekke noe fra vår liste. Så nå kommer til å like liste-> n. Og så listen kommer til å like liste-> n, eller liste-> neste. Så hvis nå verdi lik verdi. Nå kan vi legge til både vår rett pekeren og vår venstre pekeren så lenge de ikke er null. Her nede, tror jeg vi burde ha gjort det i første omgang. Hvis (nå-> høyre! = NULL) så vi kommer til å sette noden til listen vår. Hvis (nå-> venstre), dette er litt ekstra arbeid, men det er greit. Hvis (nå-> venstre! = NULL), og vi kommer til å sette venstre inn vår lenket liste, og det bør være det. Vi iterate - så lenge vi har noe i vår liste, Vi har en annen node å se på. Så vi ser på den noden, vi fremme vår liste til den neste. Hvis det node er den verdien vi leter etter, kan vi returnere true. Else setter både våre venstre og høyre undertreene, så lenge de ikke er null, i vår liste slik at vi uunngåelig gå over dem. Så hvis de ikke var null, hvis vår root pekeren pekte på to ting, så ved første vi dro noe ut så vår liste ender opp som null. Og da vi satt to ting igjen, så nå vår liste er av størrelse 2. Så vi kommer til å sløyfe tilbake opp og vi bare kommer til å trekke, la oss si, den venstre peker på vår rotnoden. Og det vil bare holde skjer, vi vil ende opp looping over alt. 

Legg merke til at dette var betydelig mer komplisert i den rekursive løsningen. Og jeg har sagt flere ganger at den rekursive løsningen har vanligvis mye til felles med iterativ løsning. Her er dette nøyaktig hva den rekursive løsningen gjør. Den eneste forandringen er at i stedet for å bruke implisitt stabelen, programmet stakken, som din måte å holde styr på hva noder du fortsatt trenger å besøke, nå må du eksplisitt bruke en lenket liste. I begge tilfeller er du holde styr på hva node fortsatt trenger å bli besøkt. I den rekursive fall er det bare enklere fordi en stabel er implementert for deg som programmet stabelen. Legg merke til at dette er også koblet listen, er det en stabel. Uansett hva vi bare sette på stakken er umiddelbart hva vi kommer til å trekke av stabelen å gå til neste. Vi har ikke mer tid, men noen spørsmål? [Student, uforståelig] [Bowden] Yeah. Så hvis vi har vår lenket liste, strøm kommer til å peke til denne fyren, og nå er vi bare fremme våre lenket liste å fokusere på denne fyren. Vi krysser over lenket liste i den linjen. Og da jeg tror vi bør frigjøre vår lenket liste og sånt gang før retur sant eller usant, må vi iterere over vår lenket liste og alltid her nede, tror jeg, hvis vi nå rett er ikke lik, legge det, så nå ønsker vi å frigjøre nå fordi, vel, vi helt glemmer om listen? Ja. Så det er det vi ønsker å gjøre her. Hvor er pekeren? Cur var da - vi ønsker til en struct liste * 10 lik liste neste. Gratis liste, list = temp. Og i tilfelle hvor vi return true, trenger vi å veksle over resten av vår lenket liste frigjør ting. Det fine med den rekursive løsningen er å frigjøre ting betyr bare spratt factorings av stabelen som vil skje for deg. Så vi har gått fra noe som er som 3 linjer med hard-to-tenke-om koden til noe som er betydelig mange flere vanskelige å tenke-om linjer med kode. Noen flere spørsmål? OK. Vi er gode. Bye! [CS50.TV]