[Powered by Google Translate] [Avsnitt 7: Bekvämare] [Rob Bowden] [Harvard University] [Detta är CS50] [CS50.TV] Okej. Så som jag sa i min e-post, Detta kommer att bli en binär-träd-intensiva delen. Men det finns inte så många frågor. Så vi ska försöka dra ut varje fråga och gå in smärtsamma detalj alla de bästa sätten att göra saker. Så rätt från början, går vi igenom prov ritningar av binära träd och grejer. Så här: "Kom ihåg att ett binärt träd har noder som liknar en länkad lista, utom i stället för en pekare finns två: en för vänster "barn" och en för höger "barn". " Så ett binärt träd är precis som en länkad lista, utom struct kommer att få två pekare. Det finns trinary träd, som kommer att ha tre pekare, Det finns N-ari träd, som bara har en generisk pekare att du har sedan malloc vara stor nog att ha tillräckligt pekare till alla möjliga barn. Så binärt träd råkar bara ha ett konstant antal två. Om du vill kan du ge en länkad lista som unär träd, men jag tror inte att någon kallar det så. "Rita en lådor-och-pilar diagram över ett binärt träd nod innehåller Nates favoritnummer, 7, där varje barn pekare är null. " Så iPad läge. 

Det kommer att bli ganska enkelt. Vi bara kommer att ha en nod, jag drar det som en kvadrat. Och jag drar värdena här. Så värdet kommer att gå in här, och sedan ner hit kommer vi att ha den vänstra pekaren till vänster och höger pekaren till höger. Och det är väldigt mycket så konvention att kalla det vänster och höger, namnen pekaren. Båda dessa kommer att vara noll. Som bara kommer att bli noll, och det kommer bara vara noll. Okej. Så tillbaka till här. "Med en länkad lista, hade vi bara att lagra en pekare till den första noden i listan för att komma ihåg hela länkade listan, eller hela listan. Likaså med träd, har vi bara lagra en pekare till en enda nod för att minnas hela trädet. Denna nod är calle den "roten" av trädet. Bygg på diagrammet från före eller rita en ny så att du har en lådor-och-pilar skildring av ett binärt träd med värdet 7, sedan 3 i den vänstra, sedan 9 till höger, och sedan 6 till höger om 3. " Låt oss se om jag kan komma ihåg allt detta i mitt huvud. Så detta kommer att vara vår rot här uppe. Vi kommer att ha en viss pekare någonstans, något som vi kallar rot, och det är att peka på den här killen. Nu för att göra en ny nod, Vad har vi, 3 på vänster? Så en ny nod med 3, och det först pekar noll. Jag ska bara sätta N. Nu vill vi göra som går till vänster om 7. Så vi ändra pekaren till nu peka på den här killen. Och vi gör samma sak. Vi vill ha en 9 hit som initialt bara säger null. Vi kommer att ändra denna pekare, peka på 9, och nu vill vi sätta 6 till höger om 3. Så det kommer att - göra en 6. Och den killen kommer att peka dit. Okej. Så det är allt ber oss att göra. 

Nu ska vi gå igenom några terminologi. Vi pratade redan om hur trädets rot är den översta noden i trädet. Den som innehåller 7. Noderna vid botten av trädet kallas bladen. Varje nod som bara har noll som sina barn är ett löv. Så det är möjligt, om vår binära träd är bara en enda nod, att ett träd är ett löv, och det är det. "Den" höjd "av trädet är antalet hopp du måste göra att ta sig från toppen till ett löv. " Vi ska komma in i en andra, skillnaden mellan balanserade och obalanserade binära träd, men nu, den totala höjden av detta träd Jag skulle vilja säga är 3, men om man räknar antalet hopp du måste göra för att få till 9, då är det egentligen bara en höjd av 2. Just nu är detta en obalanserad binärt träd, men vi pratade om balanserad när det kommer till att vara relevanta. Så nu kan vi tala om noder i ett träd i termer förhållande till de andra noderna i trädet. Så nu har vi föräldrar, barn, syskon, förfäder och ättlingar. De är ganska sunt förnuft, vad de betyder. Om vi ​​frågar - det är föräldrar. Så vad är förälder till 3? [Studenter] 7. >> Ja. Den förälder bara kommer att vara vad pekar till dig. Vad är barn 7? [Studenter] 3 och 9. >> Ja. Observera att "barn" bokstavligen betyder barn, så 6 skulle inte gälla, eftersom det är som ett barnbarn. Men om vi går ättlingar, så vad är ättlingar till 7? [Studenter] 3, 6 och 9. >> Ja. Ättlingar till rotnoden kommer att vara allt i trädet, utom kanske rotnoden själv, om du inte vill att anse att en ättling. Och slutligen, förfäder, så det är i motsatt riktning. Så vad är förfäder till 6? [Studenter] 3 och 7. >> Ja. 9 ingår inte. Det är bara den direkta släktlinje tillbaka till roten kommer att bli dina förfäder. 

"Vi säger att en binär träd" beställs "om för varje nod i trädet, alla sina ättlingar till vänster har mindre värden och alla de på rätt ha större värden. Till exempel trädet ovanför beställt men det är inte den enda möjliga beställt arrangemang. " Innan vi kommer till det, en ordnad binär träd är också känd som en binärt sökträd. Här har vi råkar kalla det en ordnad binärt träd, men jag har aldrig hört det kallas en ordnad binärt träd innan, och på en frågesport vi är mycket mer benägna att sätta binära sökträd. De är en och samma, och det är viktigt att du känner igen skillnaden mellan binära träd och binära sökträd. En binär träd är bara ett träd som pekar på två saker. Varje nod pekar på två saker. Det finns ingen resonemang om de värderingar som den pekar på. Så vill hit, eftersom det är ett binärt sökträd, Vi vet att om vi går till vänster om 7, då alla de värden som vi kan möjligen nå genom att gå till vänster om 7 måste vara mindre än 7. Lägg märke till att alla värden är mindre än 7 är 3 och 6. De är alla till vänster om 7. Om vi ​​går till höger om 7, har allt att vara större än 7, så 9 är till höger om 7, så vi är bra. Detta är inte fallet för ett binärt träd, för en vanlig binär träd kan vi bara ha 3 upptill, 7 till vänster, 9 till vänster om 7, det finns ingen beställning av värden som helst. Nu kommer vi faktiskt inte göra detta eftersom det är jobbigt och onödigt, men "försök att dra så många beställda träd som du kan tänka dig med siffrorna 7, 3, 9, och 6. Hur många distinkta arrangemang finns det? Vad är höjden av varje? " 

Vi gör ett par, men huvudtanken är, Detta är på intet sätt en unik representation av ett binärt träd som innehåller dessa värden. Allt vi behöver är lite binärt träd som innehåller 7, 3, 6 och 9. En annan möjlig giltigt skulle vara roten är 3, gå till vänster och det är 6, gå till vänster och det är 7, gå till vänster och det är 9. Det är ett fullvärdigt binärt sökträd. Det är inte till stor hjälp, eftersom det är precis som en länkad lista och alla dessa pekare är bara noll. Men det är en giltig träd. Ja? [Student] Inte värdena vara större på höger? Eller är det -? >> De jag menade att gå åt andra hållet. Det finns också - ja, låt oss byta det. 9, 7, 6, 3. God fångst. Det har fortfarande lyda vad en binär träd sökning är tänkt att göra. Så allt till vänster måste vara mindre än en given nod. Vi kan bara flytta, säga, detta 6 och lägga den här. Nej, det kan vi inte. Varför får jag göra det? Låt oss göra - här är 6, här är 7, 6 punkter till 3. Detta är fortfarande ett giltigt binärt sökträd. Vad är det för fel om jag - låt oss se om jag kan komma med ett arrangemang. Ja, okej. Så vad är fel med det här trädet? Jag antar att jag redan har gett dig en vink om att det är något fel med det. Varför får jag göra det? Okej. Detta ser rimligt. Om vi ​​tittar på varje nod, såsom 7, sedan till vänster om 7 är en 3. Så vi har 3, är den sak till höger om 3 a 6. Och om man tittar på 6, är saken till höger om 6 a 9. Så varför är detta inte ett giltigt binärt sökträd? [Studenter] 9 är fortfarande till vänster om 7. >> Ja. Det måste vara sant att alla värden som du kan möjligen nå genom att gå till vänster om 7 är mindre än 7. Om vi ​​går till vänster om 7 får vi till 3 och vi kan fortfarande få till 6, vi kan fortfarande få till 9, men genom att ha gått mindre än 7, Vi bör inte kunna få till ett antal som är större än 7. Så detta är inte en giltig binärt sökträd. 

Min bror hade faktiskt en intervju fråga som var i princip detta, bara kod upp något för att validera om ett träd är ett binärt sökträd, och så det första han gjorde var bara kontrollera Om vänster och höger är korrekta, och sedan iterera nere. Men du kan inte bara göra det, du måste hålla reda det faktum att nu när jag har gått till vänster om 7, allt i denna underträdet måste vara mindre än 7. Den korrekta algoritmen måste hålla reda av gränserna att värdena möjligen kan falla i. Vi kommer inte att gå igenom dem alla. Det finns en trevlig upprepning relation, Även om vi inte har kommit till dem, annars kommer vi inte att få dem, definiera hur många det egentligen är. Så det finns 14 av dem. Idén om hur du skulle göra det är matematiskt som, Du kan välja en enda en som rotnoden, och sedan om jag plockar 7 är rotnoden, då det finns, säger vissa siffror som kan gå bli min vänstra nod, och det finns några siffror som kan vara min högra nod, men om jag har n totala antalet, då det belopp som kan gå till vänster plus det belopp som kan gå till höger N - 1. Så av de återstående siffrorna, måste de kunna gå antingen till vänster eller till höger. Det verkar svårt att om jag sätter 3 först sedan allt måste gå till vänster, men om jag sätter 7, så vissa saker kan gå vänster och vissa saker kan gå till höger. Och med '3 första "jag menade allt kan gå åt höger. Det är verkligen, du måste bara tänka på det som, hur många saker kan gå på nästa nivå i trädet. Och det kommer ut att vara 14, eller så kan du rita dem alla, och då får du 14. 

Gå tillbaka hit, "Beställda binära träd är cool eftersom vi kan söka igenom dem på ett mycket liknande sätt att söka på en sorterad array. För att göra det, börjar vi vid roten och arbeta oss ned trädet mot löv, kontroll varje nod värderingar mot de värden vi söker. Om det aktuella nodens värde är mindre än det värde vi letar efter, du går bredvid nodens högra barn. Annars går du till nodens vänstra barn. Vid något tillfälle hittar du antingen värdet du söker, eller du kommer att stöta på en nolla, anger värdet är inte i trädet. " Jag måste rita trädet vi hade tidigare, det tar en sekund. Men vi vill slå upp om 6, 10 och 1 i trädet. Så vad det var, 7, 9, 3, 6. Okej. De nummer du vill slå upp, vill vi slå upp 6. Hur fungerar denna algoritm arbete? Tja, vi har också några rot pekare till vårt träd. Och vi skulle gå till roten och säga, är detta värde lika med det värde vi söker efter? Så vi letar efter 6, så det är inte lika. Så vi fortsätta, och nu säger vi, okej, så 6 är mindre än 7. Betyder det att vi vill gå åt vänster, eller vill vi gå till höger? [Student] Vänster. >> Ja. Det är betydligt lättare, är rita allt du behöver göra en möjlig nod i trädet och sedan inte - istället för att försöka tänka i huvudet, Okej, om det är mindre, går jag åt vänster eller gå till höger, bara tittar på den här bilden, det är mycket tydligt att jag måste gå till vänster Om denna nod är större än det värde som jag letar efter. Så du går till vänster, nu är jag på 3. Jag vill - 3 är mindre än värdet jag söker, vilket är 6. Så vi gå till höger, och nu har jag hamnar på 6, vilket är det värde som jag letar efter, så jag återkommer sant. Nästa värde jag ska leta efter är 10. Okej. Så 10, nu kommer att - avskuren att - kommer att följa roten. Nu är 10 kommer att vara större än 7, så jag vill se till höger. Jag kommer att komma hit är 10 kommer att vara större än 9, så jag kommer att vilja se till höger. Jag kom hit, men hit nu är jag på noll. Vad gör jag om jag slog noll? [Student] Tillbaka falskt? >> Ja. Jag hittade inte 10. 1 kommer att bli en nästan identisk fall, förutom att det är bara att vändas, istället för att titta ner till höger, ska jag titta ner till vänster. 

Nu tror jag att vi faktiskt få till koden. Här är där - öppna CS50 apparaten och navigera dig fram dit, men du kan också bara göra det i utrymmet. Det är nog perfekt att göra det i det utrymme, eftersom vi kan arbeta i utrymmet. "Först ska vi behöva en ny typ definition ett binärt träd nod innehåller int värden. Använda standardtext typedef nedan, skapa en ny typ definition för en nod i ett binärt träd. Om du fastnar. . . "Bla, bla, bla. Okej. Så låt oss sätta standardtext här, typedef struct nod, och noden. Ja, okej. Så vad är de områden vi kommer att ha i vår nod? [Student] Int och därefter två pekare? >> Int värde, två pekare? Hur skriver jag pekare? [Student] Struct. >> Jag zooma in Ja, så struct nod * vänster, och struct nod * rätt. Och kom ihåg diskussionen från förra gången, att detta är meningslöst, gör ingen mening, detta är meningslöst. Du behöver allt det för att definiera denna rekursiva struktur. Okej, så det är vad vi trädet kommer att se ut. Om vi ​​gjorde en trinary träd, sedan en nod kan se ut b1, b2, struct nod * b3, där b är en gren - faktiskt, jag har mer hört det vänster, mitten, höger, men oavsett. Vi bara bryr sig om binär, så rätt, vänster. "Nu deklarerar en global variabel nod * för roten av trädet." Så vi inte kommer att göra det. För att göra saker och ting lite svårare och mer allmänt, Vi kommer inte att ha en global nod variabel. Istället för stora kommer vi att förklara alla våra nod saker, och det betyder att nedan när vi börjar köra våra Innehåller funktion och vår insats funktion, istället för våra CONTAINS, funktion bara använda denna globala nod variabel, vi kommer att få det ta som argument trädet som vi vill att det ska bearbeta. Med den globala variabeln skulle göra det lättare. Vi kommer att göra saker svårare. Nu tar en minut eller så att bara göra den här sortens saker, där insidan av huvud du vill skapa detta träd, och det är allt du vill göra. Prova och konstruera detta träd i din huvudsakliga funktion. 

Okej. Så du behöver inte ens ha konstruerat trädet hela vägen ännu. Men någon har något jag kunde dra upp att visa hur man kan börja bygga ett sådant träd? [Student] Någons banka, försöker få ut. [Bowden] Alla bekväm med deras träd konstruktion? [Student] Visst. Det är inte gjort. >> Det är bra. Vi kan bara avsluta - Åh, kan du spara den? Hurra. Så här har vi - Åh, jag lite avskurna. Jag zoomat in? Zooma in genom att bläddra ut. >> Jag har en fråga. >> Ja? [Student] När du definierar struct, är saker som initieras till något? [Bowden] Nej >> Okej. Så du måste initiera - [Bowden] Nej När du definierar eller när du deklarerar en struct, det är inte initieras som standard, det är precis som om du deklarerar en int. Det är exakt samma sak. Det är som alla sina enskilda fält kan ha ett skräp värde i det. >> Och är det möjligt att definiera - eller att förklara en struktur på ett sådant sätt att den gör initiera dem? [Bowden] Ja. Så genväg initiering syntax kommer att se ut - Det finns två sätt vi kan göra det här. Jag tycker vi ska sammanställa den att se till att klang också gör detta. Ordningen på argumenten som kommer i struct, du sätter som ordningen av argument inom dessa klammerparenteser. Så om du vill att initiera den till 9 och vänster vara NULL och högerklicka vara noll, skulle det vara 9, null, null. Alternativet är, och redaktören inte gillar denna syntax, och det tror jag vill ha ett nytt block, men alternativet är något som - Här ska jag lägga den på en ny rad. Du uttryckligen säga, jag glömmer den exakta syntaxen. Så du kan explicit ta dem vid namn och säga, . C eller. Värde = 9,. Vänster = NULL. Jag gissar dessa måste vara kommatecken. . Höger = NULL, så detta sätt behöver du inte faktiskt behöver veta ordningen för struct, och när du läser detta, det är mycket tydligare om vad värdet är som initieras till. 

Det råkar vara en av de saker som - så, för det mesta, C + + är ett superset av C. Du kan ta C-kod, flytta den till C + +, och det bör sammanställa. Detta är en av de saker som C + + inte stöder, så att folk tenderar att inte göra det. Jag vet inte om det är den enda anledningen människor tenderar att inte göra det, men fallet där jag behövde använda den behövde för att arbeta med C + + och så jag inte kunde använda det. Ett annat exempel på något som inte fungerar med C + + är hur malloc returnerar ett "tomrum *," tekniskt, men du kan bara säga char * x = malloc helst, och det kommer automatiskt att kastas till en char *. Det automatiska rösterna inte hända i C + +. Det skulle inte kompilera, och du skulle uttryckligen måste säga char *, malloc, vad som helst, för att kasta den till en char *. Det finns inte många saker som C och C + + inte håller på, men de är två. Så vi ska gå med denna syntax. Men även om vi inte gick med den syntax, vad är - kan vara fel med det? [Student] Jag behöver inte dereference det? >> Ja. Kom ihåg att pilen har en implicit dereference, och så när vi bara göra med en struktur, vi vill använda. att komma åt ett fält inne i struct. Och den enda gången vi använder pil är när vi vill göra - bra, är pilen motsvarar - det är vad det skulle ha inneburit att jag använt pil. Allt pil betyder är, dereference detta, nu är jag på en struct, och jag kan få på fältet. Antingen får fältet direkt eller dereference och få fältet - Jag antar att detta borde vara värde. Men här jag har att göra med bara en struct, inte en pekare till en struct, så jag kan inte använda pilen. Men den här sortens saker vi kan göra för alla noder. Herregud. Detta är 6, 7, och 3. Då kan vi ställa upp filialer i vår träd, kan vi 7 - vi kan ha, bör dess vänstra peka till 3. Så hur gör vi det? [Studenter, obegripligt] >> yeah. Adressen till node3, och om du inte har adress, då det bara inte skulle kompilera. Men kom ihåg att detta är pekare till nästa noder. Den rätt bör peka på 9, och 3 skall peka på rätt till 6. Jag tror att det är redo. Några kommentarer eller frågor? [Student, obegripligt] Roten kommer att bli 7. Vi kan bara säga nod * PTR = eller rot, = & node7. 

För våra syften kommer vi att göra med insats, så vi kommer att vilja skriva en funktion för att infoga i denna binära träd och insatsen oundvikligen kommer att ringa malloc för att skapa en ny nod för detta träd. Så det kommer att bli rörigt med det faktum att vissa noder närvarande på stacken och andra noder kommer att hamna på högen när vi sätter dem. Det är helt giltigt, men den enda anledningen vi kan göra detta på stacken är att det är en så krystat exempel som vi vet trädet är tänkt att konstrueras som 7, 3, 6, 9. Om vi ​​inte hade det, så skulle vi inte behöva malloc i första hand. Som vi ser lite senare, bör vi malloc'ing. Just nu är det helt rimligt att sätta på stacken, men låt oss ändra detta till en malloc genomförande. Så alla dessa kommer nu att bli något liknande nod * node9 = malloc (sizeof (nod)). Och nu ska vi få göra vår kontroll. if (node9 == null) - Jag ville inte att - tillbaka 1, och då kan vi göra node9-> för nu är det en pekare, värde = 6, node9-> vänster = NULL, node9-> höger = NULL, och vi kommer att behöva göra det för var och en av dessa noder. Så istället, låt oss uttrycka det inuti en separat funktion. Låt oss kalla det nod * build_node, och detta är något liknar API ger vi för Huffmankodning. Vi ger dig initierare funktioner för ett träd och Deconstructor "funktioner" för dessa träd och samma för skogarna. 

Så här ska vi ha en initierare funktion att bara bygga en nod för oss. Och det kommer att se ut ganska precis så här. Och jag ens kommer att vara lata och inte ändra namnet på variabeln, trots node9 är ingen mening längre. Åh, jag antar node9 värde borde inte ha varit 6. Nu kan vi återgå node9. Och här bör vi returnera null. Alla är överens om att bygg-en-nod funktion? Så nu kan vi bara kalla det för att bygga en nod med ett givet värde och noll pekare. Nu kan vi kalla det, kan vi göra nod * node9 = build_node (9). Och låt oss göra. . . 6, 3, 7, 6, 3, 7. Och nu vill vi skapa samma pekare, utom nu allt är redan i form av pekare så behöver inte längre adressen. Okej. Så vad är det sista jag vill göra? Det finns en felkontroll som jag inte gör. Vad bygger nod tillbaka? [Student, obegripligt] >> Ja. Om malloc misslyckades, det ska returnera null. Så jag ska lättjefullt lägga ner hit istället för att göra en förutsättning för varje. Om (node9 == NULL, eller - ännu enklare, Detta motsvarar bara om inte node9. Så om inte node9 eller inte node6 eller inte node3, eller inte node7, returnera 1. Vi kanske bör skriva ut malloc misslyckades, eller något. [Student] är falskt lika med noll också? [Bowden] Alla nollvärde är falsk. Så null är ett nollvärde. Noll är ett nollvärde. Falskt är ett nollvärde. Varje - ganska mycket bara 2 noll värden är noll och noll, falskt är bara hash definieras som noll. Detta gäller även om vi deklarerar global variabel. Om vi ​​hade rotnoden * här uppe, då - det fina med globala variabler är att de alltid har ett initialt värde. Det är inte sant funktioner, hur insidan av här, om vi har, liksom, nod * eller x noden. Vi har ingen aning om vad x.value, x.whatever, eller vi kunde skriva ut dem och de kan vara godtyckligt. Det är inte sant för globala variabler. Så nod rot eller x noden. Som standard, allt som är global, om inte uttryckligen initialiseras till något värde, har ett nollvärde som dess värde. Så här, nod * rot vi inte uttryckligen initiera den till något, så standardvärdet är noll, vilket är nollvärdet av pekare. Det förvalda värdet på x kommer att betyda att x.value är noll, x.left är null, och x.right är null. Så eftersom det är en struct kommer alla fälten i struct vara nollvärden. Vi behöver inte använda det här, men. [Student] De structs är annorlunda än andra variabler, och de andra variablerna är sopor värden, dessa är nollor? [Bowden] Andra värden också. Så i x, kommer x att vara noll. Om det är på global räckvidd, har den ett initialt värde. >> Okej. [Bowden] Antingen ursprungliga värdet du gav det eller noll. Jag tror att tar hand om allt detta. 

Okej. Så nästa del av frågan frågar "Nu vill vi skriva en funktion som kallas innehåller med en prototyp av bool innehåller int värde. " Vi kommer inte att göra bool innehåller int värde. Vår prototyp kommer att se ut bool innehåller (int värde. Och då vi också kommer att passera den trädet att det bör kontrollera att se om den har värdet. Så nod * träd). Okej. Och då kan vi kalla det med något som, kanske vi kommer att vilja printf eller något. Innehåller 6, vår rot. Det skulle återvända en eller sann, medan innehåller 5 rot ska returnera false. Så ta en sekund för att genomföra detta. Du kan göra det antingen iterativt eller rekursivt. Det fina med hur vi har ställt upp saker är att det lämpar sig för vår rekursiva lösning mycket enklare än det globala variabel sätt gjorde. För om vi bara har innehåller int värde, så har vi inget sätt att recursing ner underträd. Vi skulle behöva ha en separat hjälpare funktion som recurses ner underträd för oss. Men eftersom vi har ändrat den för att ta trädet som ett argument, som det borde ha varit alltid i första hand, Nu kan vi recurse lättare. Så iterativ eller rekursiv, kommer vi att gå över båda, men vi får se till att rekursiva hamnar är ganska lätt. Okej. Har någon något vi kan arbeta med? 

[Student] Jag har en iterativ lösning. >> Okej, iterativ. Okej, här ser bra ut. Så vill gå oss igenom det? [Student] Visst. Så jag satt en temp variabel för att få den första noden i trädet. Och sedan jag loopas bara genom medan temp inte är lika null, så medan var fortfarande i trädet, antar jag. Och om värdet är lika med det värde som temp pekar på, då det returnerar värdet. Annars kontrollerar det om det är på höger eller vänster sida. Om du någonsin få en situation där det inte finns någon mer träd, då återgår - den lämnar slingan och returnerar false. [Bowden] Okej. Så det verkar bra. Någon har några synpunkter på något? Jag har ingen korrekthet kommentarer alls. Det enda vi kan göra är den här killen. Åh, det kommer att gå lite långsträckta. Jag fixar upp det. Okej. 

Alla borde komma ihåg hur ternära fungerar. Det har definitivt varit frågesporter i det förflutna som ger dig en funktion med en ternär operatör, och säga, översätter detta, göra något som inte använder ternära. Så detta är en mycket vanlig fråga om när jag skulle tro att använda ternära, där om någon villkoret en variabel till något, annars satt samma variabel till något annat. Det är något som mycket ofta kan omvandlas till något sådant där satt den variabeln på detta - eller, ja, är detta sant? Då är detta, annars här. [Student] Den första är om detta är sant, eller hur? [Bowden] Ja. Det sätt jag alltid läsa det är lika temp värde större än temp värde, då detta, annars här. Det ställer en fråga. Är det större? Gör sedan det första. Annan göra den andra saken. Jag nästan alltid - tjocktarmen, jag bara - i mitt huvud, läste jag som annars. 

Har någon en rekursiv lösning? Okej. Den här ska vi - det kan redan vara stora, men vi kommer att göra det ännu bättre. Detta är ganska mycket exakt samma idé. Det är bara, ja, vill du förklara? [Student] Visst. Så vi ser till att trädet inte är null först, för om trädet är null så det kommer att returnera false, eftersom vi inte har hittat det. Och om det finns fortfarande ett träd, går vi in ​​i - vi först kontrollera om värdet är den aktuella noden. Returnerar sant om det är, och om inte vi recurse på vänster eller höger. Låter det lämpligt? >> Mm-hmm. (Avtalet) Så märker att detta är nästan - strukturellt mycket lik den iterativa lösningen. Det är bara att istället för att recursing, hade vi en while-slinga. Och basfallet här där träd inte lika null var villkoret under vilket vi bröt ur while-slingan. De är mycket lika. Men vi kommer att ta detta ett steg längre. Nu gör vi samma sak här. Notera att vi tillbaka samma sak i båda dessa linjer, förutom ett argument är annorlunda. Så vi kommer att göra det till en ternär. Jag slog alternativet något, och det gjorde en symbol. Okej. Så vi kommer att återvända innehåller det. Detta är att få vara flera rader, väl, zoomade in det. Vanligtvis en stilistisk sak, jag tror inte många människor sätta ett mellanslag efter pilen, men jag antar att om du är konsekvent, det är bra. Om värdet är mindre än träd värde vill vi recurse på träd vänster, annat vi vill recurse på träd höger. Så det var steg ett att göra denna look mindre. Steg två för att göra denna look mindre - vi kan skilja denna till flera rader. Okej. Steg två för att göra det ser mindre är här, så returvärde lika träd värde, eller innehåller vad som helst. 

Detta är en viktig sak. Jag är inte säker på om han sa det uttryckligen i klassen, men det kallas kortslutning utvärdering. Tanken här är värde == träd värde. Om det är sant, då detta är sant, och vi vill "eller" att med det som är här borta. Så utan att ens tänka på det som är här borta, vad är hela uttrycket kommer att återvända? [Student] sant? >> Ja, eftersom gäller något, or'd - eller sann or'd med något är nödvändigtvis sant. Så snart vi ser returvärde = träd värde, Vi kommer bara att återvända sant. Inte ens gå till recurse längre innehåller fram. Vi kan ta detta ett steg längre. Return träd inte lika null och allt detta. Det gjorde det en-line funktion. Detta är också ett exempel på kortslutning utvärdering. Men nu är det samma idé - istället för - så om träd inte är lika null - eller, ja, Om trädet inte lika null, vilket är den dåliga fallet, Om tree lika null, då det första villkoret kommer att vara falsk. Så falsk-behandlas med något kommer att bli vad? [Student] Falskt. >> Ja. Detta är den andra halvan av kortslutning utvärdering, där om trädet inte lika null, då vi inte kommer att ens gå - eller om träd gör lika null, då vi inte kommer att göra värde == träd värde. Vi ska bara omedelbart returnera false. Vilket är viktigt, eftersom om det inte kortslutning utvärdera, sedan om träd gör lika noll, är detta andra villkor kommer att seg fel, eftersom träd-> värde dereferencing null. Så det är det. Kan göra detta - flytta en gång över. Detta är en mycket vanlig sak också, inte gör detta en linje med detta, men det är en gemensam sak i förhållanden, kanske inte just här, men om (träd! = NULL, och träd-> värde == värde), gör vad som helst. Detta är ett mycket vanligt tillstånd, där i stället för att ha att bryta detta i två IFS, där vill, är trädet noll? Okej, det är inte noll, så nu är trädet lika med värdet? Gör så här. Istället detta villkor kommer detta segment aldrig fel eftersom det kommer att bryta ut om detta råkar vara noll. Tja, jag antar att om ditt träd är en helt ogiltig pekare, kan det seg fortfarande fel, men det kan inte seg fel om träd är null. Om det var noll, skulle det bryta ut innan du någonsin dereferenced pekaren i första hand. [Student] kallas detta lata utvärdering? 

[Bowden] Lat evaluering är en separat sak. Lat evaluering är mer som du ber om ett värde, du ber att beräkna ett värde, typ av, men du behöver inte omedelbart. Så tills du faktiskt behöver det, är det inte utvärderas. Det är inte exakt samma sak, men i Huffman pset, står det att vi "slött" skriva. Anledningen till att vi gör det beror på att vi faktiskt buffra skriva - Vi vill inte skriva enskilda bitar i taget, eller enskilda byte i taget, vill vi istället få en bit av byte. Sen när vi har en bit av byte, så vi ska skriva ut det. Även om du ber den att skriva - och fwrite och fread göra samma saker. De buffert dina läser och skriver. Även om du be den att skriva direkt, kommer det förmodligen inte. Och du kan inte vara säker på att saker och ting kommer att skrivas tills du anropar hfclose eller vad det är, som sedan säger, okej, jag stänger min fil, det betyder att jag bättre skulle skriva allt jag har inte skrivit än. Det har inget behov av att skriva ut allt tills du stänger filen och den behöver. Så det är precis vad lat - det väntar tills det har att hända. Detta - ta 51 och du kommer att gå in i det mer i detalj, eftersom OCaml och allt 51, allt rekursion. Det finns inga iterativa lösningar, i princip. Allt är rekursion, och lata utvärdering kommer att vara viktigt för många omständigheter där, om du inte lättjefullt utvärdera, skulle det betyda - Exemplet är strömmar, som är oändligt lång. I teorin kan du tänka på de naturliga talen som en ström av 1-2-3-4-5-6-7, Så lättjefullt utvärderas saker är bra. Om jag säger att jag vill den tionde numret, så jag kan bedöma upp till den tionde numret. Om jag vill ha hundrade numret, så jag kan bedöma upp till hundrade numret. Utan lat utvärdering, då det kommer att försöka utvärdera alla nummer omedelbart. Du utvärderar oändligt många siffror, och det är bara inte möjligt. Så det finns en hel del omständigheter där lat utvärdering är bara viktigt för att få saker och ting att fungera. 

Nu vill vi skriva insats där insatsen kommer att vara liknande förändras i sin definition. Så just nu är det bool insats (int värde). Vi kommer att ändra det till bool insats (int värde, nod * träd). Vi har faktiskt kommer att ändra på det igen i lite, vi får se varför. Och låt oss gå build_node, bara för fan av det, ovan in så att vi inte behöver skriva en funktion prototyp. Vilket är en fingervisning om att du kommer att använda build_node i insatsen. Okej. Ta en minut för det. Jag tror att jag räddade en översyn om du vill dra från det, eller åtminstone gjorde jag nu. Jag ville ha en liten paus för att tänka på logik insatsen, om du inte kan tänka på det. I grund och botten kommer du alltid bara vara sätta på bladen. Som, om jag sätter en så jag oundvikligen kommer att sätta 1 - Jag ska ändra till svart - Jag ska vara sätta 1 här. Eller om jag sätter 4, jag vill bli sätta 4 här. Så oavsett vad du gör, du kommer att sätta på ett löv. Allt du behöver göra är att upprepa ned trädet tills du kommer till noden som bör vara nodens förälder den nya nodens förälder, och sedan ändra sin vänstra eller högra pekare, beroende på om det är större än eller mindre än den aktuella noden. Ändra den pekare att peka på din nya noden. Så iterera ner trädet, gör bladet pekar på den nya noden. Också tänka på varför som förbjuder den typ av situation före, där jag konstruerade det binära trädet där det var riktigt Om du såg bara en enda nod, men 9 var till vänster om 7 om du upprepade ner hela vägen. Så det är omöjligt i detta scenario, eftersom - tycker om sätter 9 eller något, vid den allra första noden, Jag ska se 7 och jag ska bara gå till höger. Så oavsett vad jag gör, om jag sätter genom att gå till ett löv, och till ett löv med lämplig algoritm, det kommer att vara omöjligt för mig att sätta 9 till vänster om 7 eftersom så fort jag slog 7 Jag ska gå till höger. Har någon något att börja med? [Student] jag gör. >> Visst. [Student, obegripligt] [Annan student, obegripligt] [Bowden] Det är uppskattat. Okej. Vill förklara? 

[Student] Eftersom vi vet att vi sätter nya noder i slutet av trädet, Jag loopas trädet iterativt tills jag kom till en nod som pekade på null. Och då bestämde jag mig för att uttrycka det antingen på höger eller vänster sida med denna rätt variabel, det berättade var att sätta den. Och sedan, i huvudsak gjorde jag just det sista - att temp nod pekar på nya noden att den skapade, antingen på vänster eller på höger sida, beroende på vad värdet rätt var. Slutligen ställer jag den nya noden värdet till värdet av sin testning. [Bowden] Okej, så jag ser en fråga här. Det är som 95% av vägen dit. Den enda fråga som jag ser, ja, ser någon annan ett problem? Vad är den omständighet under vilken de bryter ut på slingan? [Student] Om temp är noll? >> Ja. Så hur du bryta sig ut ur loopen är om temp är noll. Men vad gör jag här? Jag dereference temp, vilket är oundvikligt noll. Så en annan sak du behöver göra är inte bara hålla reda tills temp är noll, du vill hålla reda på föräldern vid alla tidpunkter. Vi vill också överordnade noden *, jag antar att vi kan hålla det vid noll i början. Detta kommer att få konstiga beteende för roten av trädet, men vi kommer till det. Om värdet är större än vad som helst, så temp = temp höger. Men innan vi gör det, förälder = temp. Eller är föräldrar kommer alltid till lika temp? Är det så? Om temp inte är null, så jag ska gå ner, oavsett vad, till en nod som temp är moderbolag. Så förälder kommer att vara temp och sedan jag flytta temp ner. Nu temp är null, men pekar förälder förälder till det som är noll. Så här nere, jag vill inte ställa rätt lika med 1. Så jag flyttade till höger, så om höger = 1, och jag antar att du också vill göra - om du flyttar till vänster, vill du ställa rätt lika med 0. Eller så om du flyttar någonsin till höger. Så rätt = 0. Om höger = 1, nu vill vi göra den förälder rätt pekaren newnode, annat vi vill göra den förälder vänster pekaren newnode. Frågor på det? Okej. Så detta är hur vi - ja, faktiskt, istället för att göra detta, vi förväntade oss halv dig att använda build_node. Och sedan om newnode lika null returnera false. Det är det. Nu är detta vad vi förväntat dig att göra. 

Detta är vad de anställda lösningarna gör. Jag håller inte med detta som "rätt" sätt att gå om det men detta är helt bra och det kommer att fungera. En sak som är lite konstigt just nu är Om trädet börjar som null, passerar vi en null träd. Jag antar att det beror på hur du definierar beteende som passerar i en null träd. Jag skulle tro att om du i en null träd, sedan sätter värdet till en null träd ska bara returnera ett träd där det enda värdet är att enda nod. Har folk håller med om det? Du kan, om du vill, Om du passerar i en null träd och du vill infoga ett värde i det, returnera false. Det är upp till dig att bestämma det. För att göra det första jag sa och sedan - bra, du kommer att ha svårt att göra det, eftersom det skulle vara lättare om vi hade en global pekare till sak, men vi inte, så om trädet är noll, det finns inget vi kan göra åt det. Vi kan bara returnera false. Så jag ska byta insats. Vi tekniskt kan bara ändra denna rätt här, hur det iteration över saker, men jag ska byta insats för att ta en nod ** träd. Dubbla pekare. Vad betyder det här? Istället för att hantera pekare till noderna, det jag tänker att manipulera är pekare. Jag kommer att manipulera denna pekare. Jag kommer att manipulera pekare direkt. Detta är logiskt eftersom fundera ned - ja, just nu tyder detta på null. Vad jag vill göra är att manipulera denna pekare att peka på inte null. Jag vill att det ska peka på min nya noden. Om jag bara hålla koll på pekare till mina pekare, så jag behöver inte hålla reda på en förälder pekare. Jag kan bara hålla reda för att se om pekaren pekar på null, och om pekaren pekar på null, ändra den för att peka på noden jag vill. Och jag kan ändra det eftersom jag har en pekare till pekare. Låt oss se detta just nu. Du kan faktiskt göra det rekursivt ganska enkelt. Vill vi göra det? Ja, det gör vi. 

Låt oss se det rekursivt. Först, vad vår bas fall kommer att bli? Nästan alltid vår bas fallet, men egentligen, är denna typ av knepigt. Första saker först, om (träd == NULL) Jag antar att vi bara ska returnera false. Detta skiljer sig från ditt träd är noll. Detta är pekaren till ditt root pekaren är noll vilket innebär att ditt root pekaren inte existerar. Så här nere, om jag gör nod * - låt oss bara återanvända det. Nod * root = NULL, och då ska jag ringa insats genom att göra något liknande, Sätt 4 i och rot. Så och rot, om rot är en nod * då och rot kommer att vara en nod **. Detta är giltigt. I detta fall, träd, upp här, träd är inte null - eller insats. Här. Träd är inte null; * träd är null, vilket är bra för om * trädet är noll, så jag kan manipulera det att nu peka på vad jag vill att det ska peka på. Men om trädet är noll, innebär att jag bara kom hit och sa noll. Det är inte vettigt. Jag kan inte göra något med det. Om trädet är null returnera false. Så jag i princip redan sagt vad vår verkliga basfallet är. Och vad är det kommer att bli? [Student, obegripligt] [Bowden] Ja. Så om (* träd == NULL). Detta gäller fallet hit där om min röda visaren är pekaren jag fokuserat på, så som jag fokuserat på denna pekare, nu är jag fokuserad på denna pekare. Nu är jag fokuserad på denna pekare. Så om min röda visare, som är min nod **, är någonsin - om *, min röda visare, är någonsin noll, det betyder att jag är på det fall jag fokusera på en pekare som pekar - Detta är en pekare som hör till ett löv. Jag vill ändra denna pekare att peka på min nya noden. Kom tillbaka hit. Min newnode kommer bara att vara nod * n = build_node (värde) sedan n, om n = NULL, returnera false. Annars vill vi ändra på det pekaren för närvarande pekar på att nu peka på vår nybyggda nod. Vi kan faktiskt göra det här. Istället för att säga n säger vi * träd = om * träd. Alla förstår att? Det genom att behandla pekare till pekare, Vi kan ändra null pekare att peka på saker som vi vill att de ska peka på. Det är vår bas fallet. 

Nu vår återkommande, eller vår rekursion, kommer att bli mycket lik alla andra rekursioner Vi har gjort. Vi kommer att vilja sätta värde, och nu ska jag använda ternära igen, men vad vårt tillstånd kommer att bli? Vad är det vi letar efter för att avgöra om vi vill gå åt vänster eller höger? Låt oss göra det i separata steg. Om (värde <) vad? [Student] Trädets värde? [Bowden] Så kom ihåg att jag är närvarande - [Studenter, obegripliga] [Bowden] Ja, så här, låt oss säga att detta gröna pilen är ett exempel på vad träd närvarande är, är en pekare till denna pekare. Så det betyder att jag är en pekare till en pekare till 3. Den dereference lät två gånger bra. Vad gör jag - hur gör jag det? [Student] dereference gång och gör sedan pil på det sättet? [Bowden] Så (* träd) är dereference gång -> värde kommer att ge mig värdet av den nod som jag indirekt är pekar på. Så jag kan också skriva det ** tree.value om du föredrar det. Antingen fungerar. Om så är fallet, då jag vill ringa in med värde. Och vad är min uppdaterade nod ** kommer att bli? Jag vill gå till vänster, så ** tree.left kommer att bli min vänstra. Och jag vill pekaren till det där så att om vänster slutar vara null pekaren, Jag kan ändra den för att peka på min nya noden. 

Och det andra fallet kan vara mycket lika. Låt oss faktiskt göra att min ternära just nu. Sätt värde om värde <(** träd). Värde. Sen vill vi uppdatera våra ** till vänster, annat vi vill uppdatera våra ** till höger. [Student] Blir att pekaren till pekaren? [Bowden] Kom ihåg att - ** tree.right är en nod stjärna. [Student, obegripligt] >> Ja. ** Tree.right är så här pekare eller något. Så genom att ta en pekare till det, ger det mig vad jag vill ha av pekaren till den killen. [Student] Kan vi gå igen varför vi använder två pekare? [Bowden] Ja. Så - nej, det kan du, och den lösningen före var ett sätt att göra det utan att göra två pekare. Du måste kunna förstå att använda två pekare, och detta är en renare lösning. Också märke till att, vad händer om mitt träd - Vad händer om min rot var noll? Vad händer om jag gör det här fallet här? Så nod * root = NULL, sätt 4 i och rot. Vad rot kommer att vara efter detta? [Student, obegripligt] >> Ja. Root värde kommer att bli 4. Root vänster kommer att bli noll, är roten till höger kommer att bli noll. I fallet där vi inte klarade rot efter adress, vi kunde inte ändra root. I det fall då trädet - där rot var noll, Vi hade bara att returnera false. Det finns inget vi kan göra. Vi kan inte sätta en nod i en tom träd. Men nu kan vi, vi bara göra en tom träd i en en-nod träd. Som vanligtvis är den förväntade sätt som det är tänkt att fungera. 

Dessutom är detta betydligt kortare än också hålla reda på förälder och så du iterera ner hela vägen. Nu har jag min förälder och jag har min pekare förälder rätt till vad som helst. Istället, om vi gjorde detta iterativt, det skulle vara samma idé med en while-slinga. Men istället för att behöva handskas med mina föräldrar pekare, istället min nuvarande pekare skulle vara något att jag direkt ändra för att peka på min nya noden. Jag behöver inte ta itu med om det pekar åt vänster. Jag behöver inte ta itu med om det pekar åt höger. Det är bara vad denna pekare är, jag kommer att ställa in den att peka på min nya noden. Alla förstå hur det fungerar? Om inte, varför vill vi göra det här sättet, men åtminstone att detta fungerar som en lösning? [Student] Var återvänder vi sant? [Bowden] Det är förmodligen här. Om vi ​​rätt in den, return true. Annars här nere vi kommer att vilja återvända oavsett insats tillbaka. 

Och vad är speciellt med denna rekursiv funktion? Det är svansen rekursiv, så länge vi sammanställa med viss optimering, Det kommer att erkänna det och du kommer aldrig att få en stack overflow från detta, även om vår träd har en höjd av 10.000 eller 10 miljoner. [Student, obegripligt] [Bowden] Jag tror att det gör det på Dash - eller vad optimeringsnivå krävs för en svans rekursion skall erkännas. Jag tror att det känner igen - GCC och klang också ha olika betydelser för sina optimering nivåer. Jag vill säga att det är DashO 2, för säker på att det kommer att erkänna svansen rekursion. Men vi - du kan bygga som en Fibonocci exempel eller något. Det är inte lätt att testa med detta, eftersom det är svårt att konstruera ett binärt träd som är så stor. Men ja, jag tror det är DashO 2, som Om du kompilerar med DashO 2, kommer det att leta efter svansen rekursion och optimera den ut. Låt oss gå tillbaka till - sätta är bokstavligen det sista den behöver. Låt oss gå tillbaka till insatsen hit där vi ska göra samma idé. Det kommer fortfarande att ha fel att inte kunna att helt hantera när roten själv är null, eller de senaste posten är null men i stället för att hantera en förälder pekare, låt oss tillämpa samma logik hålla pekare till pekare. Om vi ​​här hålla våra nod ** nuvarande, och vi behöver inte hålla reda på just längre, men nod ** nuvarande = & träd. Och nu vår while-slinga kommer att vara när * nuvarande inte lika null. Behöver inte hålla reda på föräldrarnas längre. Behöver inte hålla reda på vänster och höger. Och jag kallar det temp, eftersom vi redan använder temp. Okej. Så om (värde> * temp), då och (* temp) -> höger annars temp = & (* temp) -> vänster. Och nu, vid denna tidpunkt, efter denna while-slinga, Jag gör bara detta eftersom det kanske är lättare att tänka iterativt än rekursivt, men efter detta samtidigt slinga, * Temp är pekaren vill vi ändra på. 

Innan vi hade förälder, och vi ville ändra någon av föräldrarna vänster eller förälder höger, men om vi vill förändra förälder höger, då * temp är moderbolag rätt, och vi kan ändra det direkt. Så här nere, kan vi göra * temp = newnode, och det är det. Så varsel, var allt vi gjorde i detta ta ut rader kod. För att hålla koll på den förälder i allt som är extra ansträngning. Här, om vi bara hålla reda på pekaren till pekaren, och även om vi ville bli av med alla dessa klammerparenteser nu, att det ser kortare. Detta är nu exakt samma lösning, men färre rader kod. När du börjar känna igen detta som en giltig lösning, Det är också lättare att resonera om än liknande, okej, varför har jag denna flagga på int rätt? Vad betyder det? Åh, det vilket innebär att varje gång jag går till höger, måste jag ställa in den, annars om jag går lämnade jag måste ställa den till noll. Här behöver jag inte resonera om det, det är bara lättare att tänka på. Frågor? [Student, obegripligt] >> Ja. Okej, så i den sista biten - Jag antar att en snabb och enkel funktion som vi kan göra är, let's - tillsammans, antar jag, försöka skriva en innehåller funktion som inte bryr sig om det är en binärt sökträd. Detta innehåller funktionen ska returnera sant om någonstans i denna allmänna binära träd är det värde som vi letar efter. Så låt oss först göra det rekursivt och sedan kommer vi att göra det iterativt. Vi kan faktiskt bara göra det tillsammans, eftersom detta kommer att bli riktigt kort. 

Vad är min basfall kommer att? [Student, obegripligt] [Bowden] Så om (träd == NULL), vad? [Student] returnera false. [Bowden] Else, ja, jag behöver inte mer. Om var min andra basfallet. [Student] Träd värde? >> Ja. Så om (träd-> värde == värde. Notera att vi är tillbaka till nod *, inte nod ** s? Innehåller kommer aldrig behöva använda en nod **, eftersom vi inte ändrar pekare. Vi bara korsa dem. Om det händer, då vi vill återvända sant. Annars vill vi korsa barnen. Så vi kan inte resonera om huruvida allt till vänster är mindre och allt till höger är större. Så vad är vårt tillstånd kommer att vara här - eller, vad ska vi göra? [Student, obegripligt] >> Ja. Return innehåller (värde, träd-> vänster) eller innehåller (värde, träd-> höger). Och det är det. Och märker att det finns en viss kortslutning utvärdering, där om vi råkar hitta värdet i den vänstra trädet, vi behöver aldrig att titta på rätt träd. Det är hela funktionen. Nu ska vi göra det iterativt, som kommer att vara mindre trevligt. Vi tar den vanliga start nod * nuvarande = träd. Medan (nuvarande! = Null). Snabbt kommer att se ett problem. Om nuvarande - här ute, om vi någonsin bryta detta, då vi har slut på saker att titta på, så returnera false. Om (valu-> värde == värde), return true. Så nu är vi på en plats - Vi vet inte om vi vill gå åt vänster eller höger. Så godtyckligt, låt oss bara gå till vänster. Jag har naturligtvis stött på en fråga där jag har helt övergiven allt - Jag kommer alltid bara kontrollera den vänstra sidan av ett träd. Jag kommer aldrig kontrollera något som är en rätt barn någonting. Hur åtgärdar jag det? [Student] Du måste hålla koll på vänster och höger i en stapel. [Bowden] Ja. Så låt oss göra det struct listan nod * n och sedan noden ** härnäst? Jag tror att fungerar bra. Vi vill gå över till vänster, eller let's - här uppe. Struct listan list = kommer det börja ut på detta struct lista. * List = NULL. Så det kommer att bli vår länkad lista av underträd som vi har hoppas över. Vi kommer att korsa kvar nu, men eftersom vi oundvikligen måste komma tillbaka till höger, Vi kommer att hålla till höger innanför vår struct lista. Då kommer vi att ha new_list eller struct, struct lista *, new_list = malloc (sizeof (lista)). Jag ska ignorera felkontroll det, men du bör kontrollera om det är noll. New_list noden det kommer att peka på - åh, det är därför jag ville ha det här uppe. Det kommer att peka på en andra struktur lista. Det är bara hur länkade listor arbete. Detta är detsamma som en länkad lista int utom vi bara ersätta int med nod *. Det är exakt samma. Så new_list, värdet av vår new_list nod, kommer att vara valuta-> höger. Värdet av vår new_list-> nästa kommer att bli vår ursprungliga listan, och då ska vi uppdatera vår lista att peka på new_list. 

Nu behöver vi något slags sätt att dra saker, som vi har passerat hela vänstra underträd. Nu måste vi dra saker ur det, Liksom nuvarande är null, vi vill inte bara returnera false. Vi vill nu dra utanför på vår nya lista. Ett bekvämt sätt att göra detta - ja, faktiskt, det finns flera olika sätt att göra detta. Någon har ett förslag? Där jag borde göra det eller hur jag ska göra det? Vi har bara ett par minuter, men några förslag? Istället för - en väg, i stället för vår kondition är under, vad vi nu tittar på är inte noll, istället ska vi fortsätta att gå tills vår lista sig är noll. Så om vår lista hamnar är noll, då har vi slut på saker att leta efter, för att söka över. Men det betyder att det första i vår lista bara kommer att bli den första noden. Det allra första kommer att vara - vi behöver inte längre se det. Så list-> n kommer att vara vår träd. list-> nästa kommer att bli noll. Och nu när listan inte lika null. Cur kommer att dra något från vår lista. Så nuvarande kommer att lika lista-> n. Och sedan lista kommer att lika lista-> n, eller lista-> nästa. Så om nuvarande värde är lika värde. Nu kan vi lägga till både vår rätt pekare och vår vänstra pekare så länge de inte är noll. Här nere, jag antar att vi borde ha gjort det i första hand. Om (valu-> höger! = Null) då kommer vi att sätta in den noden i vår lista. Om (valu-> vänster), här är lite extra arbete, men det är bra. Om (valu-> vänster! = Null), och vi kommer att sätta in vänster i vår länkad lista, och det borde vara det. Vi iterera - så länge vi har något i vår lista, vi har en annan nod att titta på. Så vi tittar på den noden, Vi avancera vår lista till nästa. Om den noden är det värde som vi letar efter, kan vi återvända sant. Annars sätter både våra vänster och höger underträd, så länge de inte är noll, i vår lista så att vi går oundvikligen över dem. Så om de inte är null, om vår rot pekare pekade på två saker, då först drog vi något så vår lista slutar som null. Och då vi sätter två saker tillbaka, så nu vår lista är storlek 2. Sen ska vi slinga tillbaka och vi ska bara dra, låt oss säga, den vänstra pekaren vår rotnoden. Och det kommer bara fortsätta hända, vi kommer att sluta loopa över allt. 

Observera att detta var betydligt mer komplicerat i den rekursiva lösningen. Och jag har sagt flera gånger att den rekursiva lösningen har vanligtvis mycket gemensamt med den iterativa lösningen. Här är det precis vad den rekursiva lösningen gör. Den enda förändringen är att istället för att implicit använder stacken, programmet stacken, som ditt sätt att hålla koll på vad noder du fortfarande behöver besöka, nu måste du explicit använda en länkad lista. I båda fallen är att hålla reda på vad nod fortfarande måste besökas. I den rekursiva fallet är det bara lättare eftersom en stapel genomförs för dig som programmet stacken. Observera att detta länkad lista, är det en stapel. Vad vi lägger bara på stacken är omedelbart vad vi ska dra av stapeln för att besöka nästa. Vi för sent, men några frågor? [Student, obegripligt] [Bowden] Ja. Så om vi har vår länkad lista, ström kommer att peka på den här killen, och nu är vi bara föra vår länkad lista att fokusera på den här killen. Vi korsar över det länkade listan i den linjen. Och då jag antar att vi borde befria vår länkad lista och sånt gång innan han återvände sant eller falskt, måste vi iterera över vår länkad lista och alltid här nere, antar jag, Om vi ​​nuvarande rätt är inte lika med, lägga det, så nu vill vi frigöra nuvarande eftersom bra, vi glömmer helt om listan? Ja. Så det är vad vi vill göra här. Var är pekaren? Cur var då - vi vill en struct lista * 10 är lika med listan nästa. Gratis listan, lista = temp. Och i de fall där vi återvänder sant, behöver vi iterera under resten av vår länkad lista befria saker. Det fina med den rekursiva lösningen frigör saker betyder bara poppar factorings utanför stapeln som kommer att hända för dig. Så vi har gått från något som är som 3 rader svåra att tänka-om kod till något som är betydligt många fler svåra att tänka-om rader kod. Några fler frågor? Okej. Vi är bra. Hej! [CS50.TV]