[Powered by Google Translate] [Avsnitt 7] [mindre bekväm] [Nate Hardison] [Harvard University] [Detta är CS50.] [CS50.TV] 

Välkommen till avsnitt 7. Tack vare orkanen Sandy, istället för att ha en normal del den här veckan, vi gör detta genomgång, genom den del av frågorna. Jag kommer att följa tillsammans med problemet Set 6 Specifikation, och går igenom alla frågor i En del av frågorna avsnitt. Om det finns några frågor, posta dessa på CS50 diskutera. 

Okej. Låt oss komma igång. Just nu är jag tittar på sidan 3 i problembild specifikationen. Vi kommer att först börja tala om binära träd eftersom de har en hel del relevans för denna veckas problem set - Huffman Tree kodning. En av de allra första datastrukturer vi pratade om på CS50 var matrisen. Kom ihåg att en array är en sekvens av element - alla av samma typ - lagras intill varandra i minnet. Om jag har ett heltal array som jag kan rita använda denna lådor-nummer-tal stil - Låt oss säga att jag har 5 i den första rutan, jag har 7 i den andra, då har jag 8, 10 och 20 i den slutliga lådan. Kom ihåg att två riktigt bra saker om denna array är att vi har denna konstant gången tillgång till en viss del  i arrayen om vi vet sitt index. Till exempel, om jag vill ta den tredje element i arrayen - vid index 2 med hjälp av vår noll-indexering system - Jag bokstavligen bara måste göra en enkel matematisk beräkning, hoppa till den positionen i gruppen, dra ut 8 som lagras där, och jag är bra att gå. 

En av de dåliga sakerna om detta array - att vi pratade om när vi diskuterade länkade listor - är att om jag vill infoga ett element i denna array Jag kommer att behöva göra några flytta runt. Till exempel denna array här är sorterad ordning - sorterade i stigande ordning - 5, 7 och sedan, då 8, sedan 10, och därefter 20 - men om jag vill infoga numret 9 i denna array Jag kommer att behöva flytta vissa delar för att göra plats. Vi kan dra ut det här. Jag kommer att behöva flytta 5, den 7 och sedan 8; skapa en lucka där jag kan sätta 9, och därefter 10 och 20 kan gå till höger om 9. Detta är typ av en smärta eftersom det värsta scenariot - när vi behöver sätta in antingen i början eller i slutet av matrisen, beroende på hur vi flytta - vi kan sluta med att flytta alla element att vi nu lagrar i arrayen. 

Så, vad var det väg runt detta? Vägen runt detta var att gå till vår länkade-lista metod där - stället för att lagra elementen 5, 7, 8, 10, och 20 alla bredvid varandra i minnet - Vad vi istället gjorde var lagra dem slags överallt där vi ville lagra dem i dessa länkade-lista noder som jag drar ut här, typ av ad hoc. Och vi kopplas ihop dem med hjälp av dessa nästa pekare. Jag kan ha en pekare från 5 till 7, en pekare från 7 till 8, en pekare från 8 till 10, och slutligen, en pekare från 10 till 20, och sedan en null-pekare vid 20 indikerar att det inte finns något kvar. Avvägningen som vi har här är att nu om vi vill in numret 9 i vår sorterad lista, allt vi behöver göra är att skapa en ny nod med 9, ansluta den upp för att peka på lämplig plats, och därefter åter-tråd 8 till peka nedåt till 9. Det är ganska snabbt, förutsatt att vi vet exakt var vi vill infoga 9. Men avvägningen i utbyte för detta är att vi nu har förlorat konstant tid åtkomst till någon speciell del av vårt datastruktur. Till exempel, om jag vill hitta det fjärde elementet i denna länkad lista, Jag kommer att behöva börja från början av listan och arbeta mig igenom räkna nod-för-nod tills jag hittar den fjärde. 

För att få bättre tillgång prestanda än en länkad lista - men också behålla en del av de fördelar som vi hade i termer av insättningsregionen tid från en länkad lista - ett binärt träd kommer att behöva använda lite mer minne. I synnerhet, i stället för att bara ha en pekare i ett binärt träd nod - som länkade-lista nod gör - vi kommer att lägga till en andra pekare till den binära nod. Snarare än att bara ha en pekare till nästa element, vi kommer att ha en pekare till en vänster barn och en höger barn. 

Låt oss rita en bild för att se vad som faktiskt ser ut. Återigen, jag kommer att använda dessa rutor och pilar. En binär trädnod kommer att börja med bara en enkel låda. Det kommer att ha en plats för värdet, och då är det också kommer att ha ett utrymme för vänster barnet och rätt barn. Jag ska märka dem här. Vi kommer att ha den vänstra barnet, och sedan ska vi ha rätt barn. Det finns många olika sätt att göra detta. Ibland för utrymme och bekvämlighet, Jag ska faktiskt dra det som jag gör här på botten där jag kommer att ha värdet vid toppen, och sedan den högra barnet på nedre högra, och den vänstra barnet på nedre vänstra. Att gå tillbaka till denna övre diagram, Vi har värdet högst upp, då har vi den vänstra barnet pekare och sedan har vi rätt-barn pekare. 

I problembild Specification, Vi talar om att dra en nod som har ett värde 7, och sedan en vänster-barn pekare som är null, och en höger-barn pekare som är null. Vi kan antingen skriva kapital NULL i utrymmet för både vänster barnet och den högra barnet, eller vi kan dra denna diagonala snedstreck genom respektive ruta för att ange att det är noll. Jag ska göra det bara för att det är enklare. Det du ser här är två sätt att diagram en mycket enkel nod binärt träd där vi har värdet 7 och noll pekare barn. 

Den andra delen av vår specifikation talar om hur med länkade listor - kom ihåg, vi hade bara att hålla fast vid den allra första elementet i en lista att komma ihåg hela listan - och likaså, med ett binärt träd, har vi bara att hålla fast vid en pekare till trädet För att upprätthålla kontrollen över hela datastrukturen. Denna speciella del av trädet kallas rotnoden av trädet. Till exempel, om denna nod - denna nod innehåller värdet 7 med noll vänster och höger barn pekare - var det enda värdet i vår träd, då detta skulle vara vår rotnoden. Det är början av vår träd. Vi kan se detta lite tydligare när vi börjar lägga till fler noder i vårt träd. Låt mig dra upp en ny sida. 

Nu ska vi dra ett träd som har 7 vid roten, och 3 insidan av vänstra underordnade, och 9 inuti det högra underordnade. Återigen, detta är ganska enkel. Vi har 7, rita en nod för 3, en nod för 9, och jag kommer att ställa den vänstra barnet pekare av 7 för att peka på noden som innehåller 3, och den högra barnet pekare för den nod som innehåller 7 till noden innehållande 9. Nu har sedan 3 och 9 inte några barn, vi kommer att ställa alla sina barn pekare som noll. Här motsvarar roten av vår träd till noden innehåller numret 7. Du kan se att om allt vi har är en pekare till den rotnod, Vi kan sedan gå igenom vår träd och öppna både underordnade noder - både 3 och 9. Du behöver inte hålla pekare till varje enskild nod i trädet. Okej. Nu ska vi lägga till en annan nod detta diagram. Vi kommer att lägga till en nod som innehåller 6, och vi kommer att lägga detta som den rätta barn noden innehåller 3. För att göra det, kommer jag att radera den null-pekare i 3-noden och ansluta den upp för att peka på noden innehållande 6. Okej. 

Vid denna punkt, låt oss gå över lite terminologi. Till att börja med på grund av att detta kallas ett binärt träd i synnerhet är att den har två underordnade pekare. Det finns andra typer av träd som har fler barn pekare. I synnerhet gjorde du en "prova" i problembild 5. Du kommer att märka att i det försök, hade du 27 olika pekare till olika barn - en för vardera av de 26 bokstäverna i det engelska alfabetet, och sedan den 27: e för apostrof - så, det är liknande en typ av träd. Men här, eftersom det är binära, har vi bara två barn pekare. 

Utöver detta rotnoden som vi talade om, Vi har också kastat runt denna term "barn". Vad betyder det för en nod är ett barn av en annan nod? Det betyder bokstavligen att ett barn nod är ett barn av en annan nod om den andra noden har en av dess underordnade pekare som att peka på denna nod. För att sätta detta i mer konkreta termer, om 3 pekas på av en av de underordnade pekare 7, då 3 är ett barn av 7. Om vi ​​skulle räkna ut vad barn 7 är - bra, ser vi att 7 har en pekare till 3 och en pekare till 9, så 9 och 3 är barn till 7. Nio har inga barn eftersom dess underordnade pekare är noll, och 3 har endast ett barn, 6. Sex har också några barn eftersom båda sina pekare är null, vilket vi kommer att dra nu. 

Dessutom talar vi också om föräldrarna till en viss nod, och detta är, som du förväntar dig, baksidan av detta barn beskrivning. Varje nod har endast en förälder - i stället för två som du kan förvänta dig med människor. Till exempel är förälder till 3 7. Förälder till 9 är också 7 och förälder 6 är 3. Inte mycket till det. Vi har också termer för att prata om morföräldrar och barnbarn, och mer generellt talar vi om förfäder och ättlingar till en viss nod. Den anfader en nod - eller förfäder snarare av en nod - är alla de noder som ligger på vägen från roten till den noden. Till exempel, om jag tittar på noden 6, då förfäderna kommer att vara både 3 och 7. Förfäder 9, till exempel, är - om jag tittar på noden 9 - då förfader 9 är bara 7. Och ättlingar är exakt tvärtom. Om jag vill titta på alla ättlingar 7, då måste jag titta på alla noder under den. Så har jag 3, 9 och 6 alla som ättlingar 7. 

Den sista terminen som vi pratar om är denna föreställning om att vara ett syskon. Syskon - typ av följa med på dessa familjen villkor - är noder som är på samma nivå i trädet. Så, 3 och 9 är syskon eftersom de är på samma nivå i trädet. De båda har samma överordnade, 7. Den 6 har inga syskon, eftersom 9 inte har några barn. Och 7 inte har några syskon eftersom det är grunden för vår träd, och det finns alltid bara 1 rot. För 7 att ha syskon skulle behöva vara en nod över 7. Det måste vara en förälder 7, i vilket fall 7 inte längre vara roten av trädet. Då den nya föräldern till 7 skulle också behöva ha ett barn, och att barnet skulle vara syskon 7. 

Okej. Går vidare. När vi började vår diskussion om binära träd, Vi talade om hur vi skulle använda dem för att få en fördel gentemot både arrayer och länkade listor. Och hur vi ska göra det är med denna beställning egenskap. Vi säger att ett binärt träd beställs, enligt specifikationen, om för varje nod i vår träd, alla dess ättlingar till vänster - det vänstra underordnade och alla vänstra barnets ättlingar - har mindre värden, och alla de noder på höger - rätt barn och alla rätt barnets ättlingar - har noder som är större än värdet på den aktuella noden som vi tittar på. Bara för enkelhetens skull kommer vi att anta att det inte finns några dubbletter noder i vårt träd. Till exempel i detta träd vi inte kommer att behandla ärendet där vi har värdet 7 vid roten  och sedan har vi också värdet 7 på andra håll i trädet. I det här fallet kommer du att märka att detta träd verkligen är beställd. Vi har värdet 7 vid roten. Allt till vänster om 7 - Om jag ångra alla dessa små märken här - allt till vänster om 7 - den 3 och 6 - dessa värden är båda mindre än 7, och allt till höger - som är just detta 9 - är större än 7. 

Detta är inte den enda beställt trädet innehåller dessa värden, men låt oss dra några fler av dem. Det finns faktiskt en hel drös olika sätt som vi kan göra det här. Jag kommer att använda en förkortning bara för att hålla det enkelt, där - snarare än att dra ut hela lådor-och-pilar - Jag ska bara dra siffrorna och lägga till pilar som förbinder dem. Till att börja med kommer vi bara skriva vår ursprungliga trädet igen där vi hade 7, och sedan en 3, och sedan 3 pekade tillbaka till höger till 6, och 7 hade rätt barn som var 9. Okej. Vad är ett annat sätt att vi kunde skriva detta träd? Istället för att ha 3 vara den vänstra barn 7, kunde vi också ha 6 vara den vänstra barn 7, och sedan 3 vara den vänstra barn till 6. Det skulle se ut så här trädet här där jag har 7, sedan 6, sedan 3 och en 9 till höger. Vi har inte heller ha 7 som vår rotnoden. Vi skulle också ha 6 som vår rotnoden. Vad skulle det se ut? Om vi ​​ska behålla denna beställda egendom, allt till vänster om 6 måste vara mindre än den. Det finns bara en möjlighet, och det är 3. Men sedan som höger barn 6, har vi två möjligheter. Först kunde vi ha 7 och sedan 9, eller vi kan dra det - som jag är på väg att göra här - där vi har 9 som rätt barn till den 6, och därefter 7 som vänstra underordnade av 9. 

Nu, 7 och 6 är inte de enda möjliga värden för roten. Vi skulle också ha 3 vara roten. Vad händer om 3 ligger till grund? Här, det blir lite intressant. Tre har inga värden som är mindre än det, så att hela vänstra sidan av trädet bara kommer att bli noll. Det kommer inte att bli något där. Till höger kan vi lista saker i stigande ordning. Vi kunde ha 3, sedan 6, sedan 7, sedan 9. Eller kan vi göra 3, sedan 6, sedan 9, sedan 7. Eller kan vi göra 3, sedan 7, sedan 6, sedan 9. Eller, 3, 7 - faktiskt inte, kan vi inte göra en 7 längre. Det är vår en sak där. Vi kan göra 9, och sedan från 9 vi kan göra 6 och därefter 7. Eller, kan vi göra 3, sedan 9, sedan 7 och sedan 6. 

En sak att uppmärksamma er på här är att dessa träd är lite konstig utseende. I synnerhet om vi tittar på de 4 träd på höger sida - Jag cirkel dem här - dessa träd ser nästan exakt ut som en länkad lista. Varje nod har endast ett barn, och så att vi inte har något av detta trädliknande struktur som vi ser, till exempel,  I detta ett ensamt träd över här på längst ner till vänster. Dessa träd är faktiskt kallas degenererade binära träd, och vi ska prata om dessa mer i framtiden - särskilt om du går på att ta andra kurser datavetenskap. Dessa träd är degenererade. De är inte mycket användbar eftersom, ja, ger denna struktur i sig  att lookup gånger som liknar en länkad lista. Vi får inte dra fördel av det extra minnet - denna extra pekare - på grund av vår struktur är dålig på detta sätt. Hellre än att gå vidare och dra ut de binära träd som har 9 vid roten, vilket är det sista fallet att vi skulle ha, vi är i stället på denna punkt, kommer att tala lite om denna andra term att vi använder när vi talar om träd, som kallas höjden. 

Höjden av ett träd är avståndet från roten till den mest avlägsen nod, eller snarare antalet hopp som du skulle behöva göra för att börja från roten och sedan hamna på den mest avlägsna nod i trädet. Om vi ​​tittar på några av dessa träd som vi har ritat här, kan vi se att om vi tar detta träd i det övre vänstra hörnet och vi börjar vid 3, då måste vi göra en hop för att komma till 6, en andra hop för att komma till 7, och en tredje hopp för att komma till 9. Så, är höjden av detta träd 3. Vi kan göra samma övning för de andra träden som beskrivs i denna gröna, och vi ser att höjden av alla dessa träd är också verkligen 3. Det är en del av det som gör dem urarta - att deras höjd är bara en mindre än antalet noder i hela trädet. Om vi ​​tittar på det här andra träd som är inringad med rött, å andra sidan, ser vi att de mest avlägsna lövnoder är 6 och 9 - bladen är de noder som inte har några barn. Så, för att få från rotnoden till antingen 6 eller 9, Vi måste göra ett hopp för att komma till 7 och sedan en andra hop för att komma till 9, och likaså att endast en andra hopp från 7 komma till 6. Så, är höjden av detta träd hit bara 2. Du kan gå tillbaka och göra det för alla andra träd som vi tidigare diskuterade börjar med 7 och 6, och du kommer att finna att höjden av alla dessa träd är också 2. 

Anledningen till att vi har pratat om beställda binära träd och varför de är coolt är att du kan söka igenom dem i ett mycket liknande sätt att söka på en sorterad array. Det är där vi talar om att få den bättre lookup tid över det länkade enkel lista. Med en länkad lista - om du vill hitta ett visst element - du är i bästa kommer att göra någon form av linjär sökning där du börjar i början av en lista och hop en efter en - en nod efter en nod - genom hela listan tills du hittar vad du söker efter. För om du har ett binärt träd som lagras i denna trevliga format du kan faktiskt få mer av en binär sökning pågår där du söndra och härska och sök genom lämplig halv av trädet vid varje steg. Låt oss se hur det fungerar. 

Om vi ​​har - återigen gå tillbaka till vår ursprungliga Tree - Vi börjar på 7, vi har 3 till vänster, 9 till höger, och under 3 har vi 6. Om vi ​​vill söka efter numret 6 i detta träd, skulle vi börja vid roten. Vi skulle jämföra det värde som vi letar efter, säger 6, till det värde som lagras i noden som vi för närvarande tittar på, 7, tycker att 6 är verkligen mindre än 7, så vi skulle flytta till vänster. Om värdet på 6 hade varit större än 7, skulle vi ha istället flyttats till höger. Eftersom vi vet att - på grund av strukturen i vår beställda binärt träd - alla värden mindre än 7 kommer att lagras till vänster om 7, det finns ingen anledning att ens bry tittar genom den högra sidan av trädet. När vi flyttar till vänster och vi är nu på noden som innehåller 3, vi kan göra samma jämförelse igen där vi jämför 3 och 6. Och vi finner att medan 6 - värdet vi letar efter - är större än 3, Vi kan gå till den högra sidan av noden innehåller 3. Det finns ingen vänster sida här, så vi kunde ha ignorerat det. Men vi vet bara att eftersom vi tittar på trädet självt, och vi kan se att trädet inte har några barn. 

Det är också ganska lätt att slå upp 6 i detta träd om vi gör det själva som människor, men låt oss följa denna process mekaniskt som en dator skulle göra att verkligen förstå algoritmen. Vid denna punkt, vi letar nu vid en nod som innehåller 6, och vi letar efter värdet 6, så, ja, vi har hittat rätt nod. Vi hittade värdet 6 i vårt träd och vi kan stoppa vår sökning. Vid denna punkt, beroende på vad som händer, Vi kan säga, ja, har vi funnit värdet 6, den finns i vår träd. Eller, om vi planerar att sätta in en nod eller göra något, kan vi göra det på denna punkt. 

Låt oss göra ett par fler uppslag bara för att se hur det fungerar. Låt oss titta på vad som händer om vi skulle försöka leta upp värdet 10. Om vi ​​skulle slå upp värdet 10, skulle vi börja vid roten. Vi skulle se att 10 är större än 7, så vi skulle flytta till höger. Vi skulle komma till 9 och jämföra 9 till 10 och se att 9 verkligen är mindre än 10. Så återigen, skulle vi försöka att flytta till höger. Men på denna punkt, skulle vi märka att vi är på en noll nod. Det finns inget där. Det finns inget där 10 ska vara. Det är där vi kan rapportera misslyckande - att det verkligen inte 10 i trädet. Och slutligen, låt oss gå igenom de fall där vi försöker slå upp 1 i trädet. Detta liknar vad som händer om vi ser upp 10, utom i stället för att gå till höger, vi kommer att gå åt vänster. Vi börjar vid 7 och se att 1 är mindre än 7, så vi flytta till vänster. Vi kommer till 3 och se att 1 är mindre än 3, så igen vi försöka att flytta till vänster. På denna punkt har vi en noll nod, så vi återigen kan rapportera fel. 

Om du vill lära dig mer om binära träd, Det finns en hel massa roliga problem som du kan göra med dem. Jag föreslår att öva ritningen av dessa diagram ett i taget och efter igenom alla de olika stegen, eftersom detta kommer i super-händig inte bara när du gör Huffman inställda kodning problem men också i framtida kurser - bara att lära sig att dra ut dessa datastrukturer och tänka igenom de problem med papper och penna, eller i det här fallet, iPad och penna. 

Vid denna punkt dock, vi kommer att gå vidare för att göra vissa kodning praxis och faktiskt spela med dessa binära träd och se. Jag ska gå tillbaka till min dator. För denna del av sektionen, istället för att använda CS50 Kör eller CS50 utrymmen, Jag kommer att använda apparaten. 

Efter tillsammans med problemet Set specifikation, Jag ser att jag ska öppna upp apparaten, gå till min Dropbox mapp, skapa en mapp som heter 7 §, och sedan skapa en fil som heter binary_tree.c. Nu kör vi. Jag har apparaten redan öppen. Jag ska dra upp en terminal. Jag ska gå till Dropbox-mappen, gör en katalog som heter section7, och se att det är helt tomt. Nu ska jag öppna binary_tree.c. Okej. Here we go - tom fil. 

Låt oss gå tillbaka till specifikationen. Specifikationen ber att skapa en ny typ definition för ett binärt träd nod innehåller int värden - precis de värden som vi drog ut i vår diagram innan. Vi kommer att använda denna standardtext typedef att vi har gjort rätt här att du ska känna igen från problembild 5 - om du gjorde det hashtabellen sättet erövra stavningskontroll programmet. Du bör också känna igen den från förra veckans avsnitt där vi pratade om länkade listor. Vi har denna typedef en struct nod, och vi har gett denna struct nod detta namn på struct nod i förväg så att vi sedan kan hänvisa till det eftersom vi vill ha pekare struct nod som en del av vår struct, men vi har sedan inringad detta - eller snarare bifogas detta - i en typedef så att senare i koden, kan vi hänvisa till denna struct som bara en nod i stället för en struct nod. 

Detta kommer att bli mycket lik den enskilt-länkade lista definition som vi såg förra veckan. För att göra detta, låt oss bara börja med att skriva ut standardtext. Vi vet att vi måste ha ett heltal, så vi sätta i int-värde, och sedan istället för att bara ha en pekare till nästa element - som vi gjorde med enstaka-länkade listor - vi kommer att ha vänster och höger barn pekare. Det är ganska enkelt också - struct nod * vänster barn; och struct nod * rätt barn,. Cool. Det ser ut som en ganska bra start. Låt oss gå tillbaka till specifikationen. 

Nu måste vi förklara en global variabel nod * för roten av ett träd. Vi kommer att göra detta globala precis som vi gjorde första pekare i vår länkad lista också globalt. Det var så att i de funktioner som vi skriver Vi behöver inte hålla passerar runt denna rot - Men vi får se att om du vill skriva dessa funktioner rekursivt, kan det vara bättre att inte ens ge det runt som en global i första hand och istället initiera den lokalt i din huvudsakliga funktion. Men vi gör det globalt att starta. Återigen ger vi ett par platser, och jag ska förklara en nod * rot. Bara för att se till att jag inte lämnar det oinitierade, kommer jag att ställa in den lika med noll. Nu, i huvudfunktionen - som vi ska skriva riktigt snabbt här - int main (int argc, const char * argv []) - och jag ska börja förklara min argv array som const bara så att jag vet att dessa argument är argument som jag förmodligen inte vill ändra. Om jag vill ändra dem jag borde nog att göra kopior av dem. Du ser detta mycket i kod. Det är bra åt båda hållen. Det är bra att lämna det som - utelämna const om du vill. Jag lägger oftast det bara så att jag påminna mig själv  att jag förmodligen inte vill ändra dessa argument. 

Som alltid, jag ska ta med denna retur 0 rad i slutet av Main. Här kommer jag initiera min rotnoden. Som det ser ut just nu, jag har en pekare som är inställd till noll, så det pekar på ingenting. För att faktiskt börja bygga noden, Jag måste först allokera minne för det. Jag ska göra det genom att minne på heap med malloc. Jag ska ställa rot lika med resultatet av malloc, och jag kommer att använda sizeof operatören för att beräkna storleken på en nod. Anledningen till att jag använder sizeof nod i motsats till, säg, göra något så här - malloc (4 + 4 4) eller malloc 12 - är för att jag vill att min kod för att vara så kompatibla som möjligt. Jag vill kunna ta det här. C. fil, kompilera den på apparaten, och sedan sammanställa det på min 64-bitars Mac - eller på en helt annan arkitektur - och jag vill allt detta ska fungera lika. 

Om jag gör antaganden om storleken på variabler - storleken på en int eller storleken av en pekare - då jag också göra antaganden om vilka typer av arkitekturer som min kod kan lyckas kompilera när den körs. Använd alltid sizeof i motsats till manuell summera struct fälten. Det andra skälet är att det också kan finnas stoppning att kompilatorn sätter in struct. Även bara summera de enskilda fält är inte något som du normalt vill göra, så ta bort den raden. Nu, för att verkligen initiera denna rotnod, Jag kommer att behöva koppla in värden för alla sina olika områden. Till exempel, för värde jag vet att jag vill initiera till 7, och nu ska jag ställa den vänstra barnet att vara noll och det högra underordnade också vara noll. Bra! Vi har gjort den delen av spec. 

Specifikationen ner längst ner på sidan 3 ber mig att skapa ytterligare tre noder - en innehållande 3, en innehållande 6, och en med 9 - och sedan koppla dem så att det ser ut precis som vår träddiagram att vi pratade om tidigare. Låt oss göra det ganska snabbt här. Du ser verkligen snabbt att jag ska börja skriva en massa dubbletter kod. Jag ska skapa en nod * och jag kommer att kalla det tre. Jag ska ställa in den lika med malloc (sizeof (nod)). Jag ska ställa tre-> värde = 3. Tre -> left_child = null; tre -> höger _child = null; också. Det ser ganska lik initiera roten, och det är precis vad Jag kommer att behöva göra om jag börjar initiera 6 och 9 samt. Jag ska göra det riktigt snabbt här - faktiskt, jag ska göra en liten kopiera och klistra in, och se till att jag - okej.  Nu har jag det kopierade och jag kan gå vidare och ställa in lika med 6. Du kan se att det tar ett tag och är inte super-effektiv. På bara lite, vi skriver en funktion som kommer att göra detta för oss. Jag vill ersätta detta med en 9, ersätta den med en 6. 

Nu har vi alla våra noder skapas och initieras. Vi har vår rot satts lika med 7 eller innehåller värdet 7, vår nod innehåller 3, vår nod innehåller 6, och vår nod innehåller 9. Vid denna punkt, är allt vi har att göra tråd allt. Anledningen till att jag initieras alla pekare till null är bara så att jag se till att Jag har inte några oinitierade pekare i det av misstag. Och även då, vid det här laget, jag har bara att faktiskt koppla noderna till varandra - till de som de faktiskt är ansluten till - Jag behöver inte gå igenom och göra Se till att alla nollor är där på rätt plats. 

Börjar på roten, vet jag att roten vänstra barn är 3. Jag vet att roten rätt barn är 9. Efter det, det enda andra barn som jag har kvar att oroa är 3 högra barn, som är 6. Vid denna punkt, det ser allt ganska bra. Vi kommer ta bort några av dessa linjer. Nu allt ser ganska bra ut. Låt oss gå tillbaka till vår specifikation och se vad vi har att göra härnäst. 

På denna punkt måste vi skriva en funktion som kallas "innehåller" med en prototyp av "bool Innehåller (int värde)". Och detta innehåller funktionen kommer att återvända sann  Om trädet utpekas av vår globala rot variabel  innehåller värdet passerat in i funktionen och i annat fall false. Låt oss gå vidare och göra det. Detta kommer att bli precis som lookup som vi gjorde för hand på iPad bara lite sen. Låt oss zooma tillbaka lite och bläddrar uppåt. Vi kommer att lägga denna funktion precis ovanför vår huvudsakliga funktion så att vi inte behöver göra någon form av prototyper. Så innehåller bool (int värde). Där kör vi. Det är vår standardtext deklaration. Bara för att vara säker på att detta kommer att sammanställa, Jag ska gå vidare och bara ställa in den lika med returnera false. Just nu denna funktion bara inte kommer att göra något och alltid rapportera att det värde som vi letar efter inte finns i trädet. 

Vid det här laget är det nog en bra idé - eftersom vi har skrivit en hel del kod och vi har inte ens försökt att testa det ännu - att se till att det hela sammanställer. Det finns ett par saker som vi måste göra för att se till att detta verkligen kommer att sammanställa. Först se om vi har använt alla funktioner i alla bibliotek som vi ännu inte har inkluderat. De funktioner vi har använt hittills är malloc, och då har vi också använt denna typ - detta icke-standard typ som kallas "bool' - som ingår i standard bool header-fil. Vi vill absolut inkludera standard bool.h för bool typ, och vi vill också # include standard lib.h för de vanliga biblioteken som inkluderar malloc och gratis, och allt detta. Så, zooma ut, vi kommer att sluta. Låt oss försöka se till att detta faktiskt gjorde kompilera. Vi ser att det gör, så vi är på rätt spår. 

Vi öppnar upp binary_tree.c igen. Det sammanställer. Låt oss gå ner och se till att vi sätter några samtal till vår Innehåller funktion - bara för att se till att det är allt gott och väl. Till exempel när vi gjorde några sökningar i vår träd tidigare, vi försökte slå upp värdena 6, 10 och 1, och vi visste att 6 var i trädet, 10 var inte i trädet, och 1 var inte i trädet heller. Låt oss använda dessa prov samtal som ett sätt att ta reda på huruvida våra Innehåller funktionen fungerar. För att kunna göra det, jag kommer att använda printf funktionen och vi kommer att skriva ut resultatet av samtalet till innehåller. Jag ska sätta i en sträng "innehåller (% d) = eftersom  vi kommer att koppla in det värde som vi ska leta efter, och =% s \ n "och använda det som vår formatsträng. Vi ska bara se - bokstavligen skriva ut på skärmen - vad som ser ut som en funktion samtal. Detta är faktiskt inte funktionsanropet.  Detta är bara en sträng utformad för att se ut som ett funktionsanrop. 

Nu ska vi koppla in värdena. Vi kommer att försöka innehåller den 6, och sedan vad vi ska göra här är att använda den ternära operatör. Låt oss se - innehåller 6 - så, nu har jag innehöll 6 och om innehåller 6 är sant, den sträng som vi ska skicka till% s format karaktär kommer att vara strängen "sanna". Låt oss rulla över lite. Annars vill vi skicka strängen "false" om innehåller 6 returnerar false. Detta är en liten fånig ut, men jag räkna jag kan lika gärna illustrera vad ternära operatören ser ut eftersom vi inte har sett det på ett tag. Detta kommer att vara en trevlig, praktiskt sätt att ta reda på om våra Innehåller funktionen fungerar. Jag ska rulla tillbaka över till vänster, och jag ska kopiera och klistra in den här raden några gånger. Det ändrade några av dessa värden runt, så detta kommer att bli 1, och detta kommer att bli 10. 

På denna punkt har vi en fin Innehåller funktion. Vi har en del tester, och vi får se om det hela fungerar. På denna punkt har vi skrivit lite mer kod. Dags att sluta upp och se till att allt fortfarande sammanställer. Avsluta ut, och nu ska vi försöka göra binära trädet igen. Tja, det verkar som vi har ett fel, och vi har fått detta förklara tydligt biblioteket funktionen printf. Det ser ut som vi måste gå in och # include standardio.h. Och med det, ska allt sammanställa. Vi är alla bra. Nu ska vi försöka köra binära träd och se vad som händer. Här är vi,. / Binary_tree, och vi ser att, som vi förväntade oss - eftersom vi inte har genomfört innehåller ännu, eller snarare, har vi satt bara i gengäld falsk - ser vi att det bara återvänder falsk för dem alla, så det är alla arbetar för det mesta ganska bra. 

Låt oss gå tillbaka och faktiskt genomföra innehåller på denna punkt. Jag ska rulla ner, zooma in och - kom ihåg var den algoritm som vi använde att vi började på rotnoden och därefter vid varje nod som vi möter, gör vi en jämförelse, och baserat på denna jämförelse vi flytta antingen till vänster barnet eller till höger barnet. Detta kommer att se mycket lik den binära sökkoden som vi skrev tidigare i tiden. När vi börjar, vet vi att vi vill hålla fast vid den aktuella noden att vi tittar på, och den aktuella noden kommer att initieras till rotnoden. Och nu ska vi hålla gå igenom trädet, och kom ihåg att vi stoppa skick -  när vi faktiskt arbetade genom exemplet hand - var när vi stött på ett noll nod, inte när vi tittade på en noll barn, utan snarare när vi flyttade faktiskt till en nod i trädet och fann att vi är på en noll nod. Vi kommer att iterera tills nuvarande är inte lika med noll. Och vad ska vi göra? Vi kommer att testa om (nuvarande -> värde == värde), då vet vi att vi faktiskt har hittat den nod som vi letar efter. Så här kan vi återvända sant. Annars, vill vi se huruvida värdet är mindre än värdet. Om det aktuella nodens värde är mindre än det värde vi letar efter, vi kommer att flytta till höger. Så nuvarande = nuvarande -> right_child, och annars kommer vi att flytta till vänster. nuvarande = nuvarande -> left_child,. Ganska enkel. 

Du känner igen förmodligen slinga som är mycket lik detta från binärsökning tidigare i sikt, förutom då vi hade att göra med låg, medel och hög. Här har vi bara titta på ett nuvärde, så det är trevligt och enkelt. Låt oss se till att denna kod fungerar. Kontrollera först att det sammanställer. Ser ut som det gör. Låt oss försöka köra det. Och mycket riktigt, skriver ut allt som vi förväntade oss. Den finner 6 i trädet, inte hittar 10 eftersom 10 inte är i trädet, och hittar inte 1 antingen på grund 1 är inte heller i trädet. Cool stuff. 

Okej. Låt oss gå tillbaka till vår specifikation och se vad som händer. Nu vill man lägga till några fler noder till vår träd. Det vill lägga 5, 2 och 8, och se till att vår innehåller kod fortfarande fungerar som förväntat. Låt oss gå göra det. Vid denna punkt, snarare än att göra det irriterande kopiera och klistra igen, Låt oss skriva en funktion för att faktiskt skapa en nod. Om vi ​​bläddra ner hela vägen till stora, ser vi att vi har gjort detta mycket liknande kod om och om igen varje gång som vi vill skapa en nod. 

Låt oss skriva en funktion som faktiskt kommer att bygga en nod för oss och returnera den. Jag ska kalla det build_node. Jag ska bygga en nod med ett visst värde. Zooma in här. Det första jag ska göra är att skapa faktiskt utrymme för nod i högen. Så nod * n = malloc (sizeof (nod)), n -> värde = värde; och sedan här, jag ska bara initiera alla fält är lämpliga värden. Och i slutet kommer vi tillbaka vår nod. Okej. En sak att notera är att denna funktion här kommer att returnera en pekare till minne som har hög-allokerad. Vad är trevligt om detta är att denna nod nu - Vi måste förklara det på högen för om vi förklarade det på stacken skulle vi inte kunna göra det i den här funktionen så här. Att minnet skulle gå ut ur räckvidd och skulle vara ogiltig om vi försökte att komma åt den senare. Eftersom vi förklara heap-allokerat minne, vi kommer att behöva ta hand om att befria det senare för vårt program för att inte läcka något minne. Vi har punting på att för allt annat i koden bara för enkelhets skull på tiden, men om du skriver någonsin en funktion som ser ut så här där du har - vissa kallar det en malloc eller realloc inuti - du vill vara säker på att du lägger någon sorts kommentar här uppe som säger, Vet du returnerar en hög-allokerad nod initieras med den skickade i värde. Och då du vill vara säker på att du sätter i någon form av anmärkning som säger uppringaren måste frigöra den returnerade minnet. Detta sätt, om någon någonsin går och använder den funktionen, de vet att vad de får tillbaka från den funktionen vid någon punkt måste frigöras. 

Förutsatt att allt är gott och väl här, vi kan gå ner i vår kod och ersätter alla dessa rader här med samtal till vår bygga nod-funktion. Låt oss göra det riktigt snabbt. Å ena sidan att vi inte kommer att ersätta denna del här nere vid botten där vi faktiskt koppla upp noderna peka på varandra, eftersom att vi inte kan göra i vår funktion. Men låt oss göra root = build_node (7), nod * tre = build_node (3); nod * sex = build_node (6), nod * nio = build_node (9),. Och nu ville vi också att lägga noder för - nod * fem = build_node (5), nod * åtta = build_node (8); och vad som var den andra noden? Låt oss se här. Vi ville också lägga till en 2 - nod * två = build_node (2),. Okej. Vid det här laget vet vi att vi har fått 7, 3 den, den 9 och 6 alla trådbundna upp på lämpligt sätt, men hur är det 5, den 8 och 2? Att hålla allt i rätt ordning, Vi vet att tre rätt barn är 6. Så om vi ska lägga till 5, den 5 hör också i den högra sidan av trädet varav 3 är roten, så 5 hör som vänster barn 6. Vi kan göra detta genom att säga, sex -> left_child = fem; och sedan 8 hör som vänster barn 9, så nio -> left_child = åtta; och därefter 2 är den vänstra barn 3, så att vi kan göra det här uppe - dig -> left_child = två;. Om du inte riktigt följa med det, föreslår jag att du drar ut det själv. 

Okej. Låt oss spara den här. Låt oss gå ut och se till att det sammanställer, och då kan vi lägga till i våra Innehåller samtal. Ser ut som allt fortfarande sammanställer. Låt oss gå in och lägg i några innehåller samtal. Återigen, jag ska göra lite kopiera och klistra in. Nu ska vi leta efter 5, 8 och 2. Okej. Låt oss se till att allt detta ser bra ut ändå. Bra! Spara och avsluta. Nu ska vi göra, sammanställa, och nu ska vi köra. Av resultaten ser det ut som allt fungerar bara trevligt och bra. Bra! Så nu har vi fått våra CONTAINS, funktion skrivs. Låt oss gå vidare och börja arbeta på hur du sätter noder i trädet eftersom, som vi gör det just nu, det är inte mycket vackra. 

Om vi ​​går tillbaka till specifikationen, det ber oss att skriva en funktion som kallas in - igen, tillbaka en bool för om vi kunde faktiskt in nod i trädet - och sedan värdet att sätta in i trädet anges som det enda argumentet för vår Infoga funktion. Vi återkommer sant om vi kunde verkligen sätta noden innehåller värdet i trädet, vilket innebär att vi, ett, hade tillräckligt med minne, och sedan två, gick det nod inte redan finns i trädet sedan - Kom ihåg att vi inte kommer att ha dubbla värden i trädet, bara för att göra det enkelt. Okej. Tillbaka till koden. Öppna den. Zooma in lite, rulla ned. Låt oss sätta insatsen fungerar precis ovanför Innehåller. Återigen, det kommer att kallas bool insats (int värde). Ge det lite mer utrymme, och sedan, som standard, låt oss sätta i gengäld falskt i slutet. Nu nere på botten, låt oss gå vidare och i stället för att manuellt bygga noderna i främsta oss själva och kablar upp dem för att peka på varandra som vi gör, vi lita på våra Infoga funktion att göra det. Vi kommer inte att lita på vår insats funktion för att bygga hela trädet från början ännu, utan vi bli av med dessa rader - we'll kommentera ut dessa rader - som bygger noderna 5, 8, och 2. Och i stället kommer vi in ​​samtal till vår insats funktion att se till att det faktiskt fungerar. Nu kör vi. 

Nu har vi kommenterat ut dessa linjer. Vi har bara 7, 3, 9, och 6 i vårt träd vid denna punkt. För att säkerställa att detta är alla arbetar, Vi kan zooma ut, göra vår binära träd, kör det, och vi kan se som innehåller nu säger till oss att vi är helt rätt - 5, 8, och 2 är inte längre i trädet. Gå tillbaka till koden, och hur ska vi sätta? Kom ihåg vad vi gjorde när vi var faktiskt sätta 5, 8 och 2 tidigare. Vi spelade som Plinko spel där vi började vid roten, gick ner trädet en efter en efter en tills vi hittat rätt lucka, och då vi fast i noden vid lämplig plats. Vi ska göra samma sak. Detta är i princip som att skriva kod som vi använt i innehåller funktionen att hitta platsen där noden bör, och då vi bara kommer att sätta noden där. Låt oss börja göra det. 

Så vi har en nod * nuvarande = rot, vi ska bara följa innehåller kod tills vi tycker att det inte riktigt fungerar för oss. Vi kommer att gå igenom trädet medan det aktuella elementet inte är null, och om vi finner att nuvarande värde är lika med det värde som vi försöker infoga - Nåväl, detta är ett av de fall där vi inte kunde faktiskt in noden in i trädet, eftersom detta innebär att vi har en dubblett värde. Här är vi faktiskt kommer att returnera false. Nu, annars om nuvarande värde är mindre än värdet, Nu vet vi att vi flyttar till höger  eftersom värdet hör hemma i den högra halvan av den aktuella trädet. Annars kommer vi att flytta till vänster. Det är i princip våra Innehåller fungerar där. 

Vid denna punkt, när vi har slutfört detta medan slinga, vår nuvarande pekare kommer att peka på null Om funktionen inte redan tillbaka. Vi därför har nuvarande på den plats där vi vill infoga den nya noden. Vad återstår att göra är att faktiskt bygga den nya noden, som vi kan göra ganska enkelt. Vi kan använda vår super-händig bygga nod funktion, och något som vi inte gjorde tidigare - Vi bara typ av tog för givet men nu ska vi göra bara för att se - vi testar att se till att värdet som returneras av ny nod var faktiskt inte är noll, eftersom vi inte vill börja komma att minnet om det är null. Vi kan testa för att se till att nya noden inte är lika med noll. Eller istället ser vi bara om det faktiskt är noll, och om det är noll, då kan vi bara returnera false tidigt. 

På denna punkt måste vi koppla nya noden i sin rätt plats i trädet. Om vi ​​ser tillbaka på huvud och där vi var faktiskt ledningar i värden före, ser vi att det sätt som vi gjorde det när vi ville sätta 3 i trädet var vi åt vänster barn rot. När vi satte 9 i trädet, hade vi tillgång till rätt barn roten. Vi var tvungna att ha en pekare till den förälder för att få ett nytt värde i trädet. Rulla tillbaka upp för att infoga, det är kommer inte att helt arbeta här eftersom vi inte har en förälder pekare. Vad vi vill kunna göra är att på denna punkt, kontrollera förälderns värde och se - ja, Jisses, om föräldern värde är mindre än det aktuella värdet, då förälderns rätt barn bör vara den nya noden; Annars bör föräldern vänstra barnet vara den nya noden. Men vi har inte denna förälder pekare riktigt än. 

För att få det, vi kommer faktiskt att behöva följa det som vi går igenom trädet och hitta rätt plats i vår slinga ovan. Vi kan göra det genom att rulla tillbaka upp till toppen av vår insats funktion och spåra en annan pekare variabel som kallas förälder. Vi kommer att ställa in den lika med noll från början, och sedan varje gång vi går igenom trädet, vi kommer att ställa den överordnade pekaren för att matcha den aktuella pekaren. Ställ förälder lika med nuvarande. På så sätt varje gång vi går igenom, vi kommer att se till att så markörens aktuella blir ökas föräldern pekaren följer det - bara en nivå högre än den nuvarande pekaren i trädet. Att alla ser ganska bra ut. 

Jag tror att en sak som vi vill ändra är att bygga nod återvänder null. För att få bygga nod till faktiskt framgångsrikt returnera null, vi får ändra denna kod, för här, testade vi aldrig att se till att malloc returnerade en giltig pekare. Så om (n = NULL!), Sedan - Om malloc returnerade en giltig pekare, så vi initiera den; annars kommer vi tillbaka bara och som kommer att sluta återvänder null för oss. Nu allt ser ganska bra ut. Låt oss se till att detta faktiskt sammanställer. Gör binärt träd, och åh, vi har lite grejer på gång här. 

Vi har en implicit deklaration av funktionen bygger nod. Återigen, dessa kompilatorer, vi kommer att börja i toppen. Vad det måste betyda att jag ringer bygga noden innan jag har faktiskt förklarat det. Låt oss gå tillbaka till koden verkligen snabbt. Bläddra nedåt och säker nog, min insats funktion deklareras ovanför bygga noden funktionen, men jag försöker använda bygga nod inuti insatsen. Jag ska gå in och kopiera - och sedan klistra bygga vägen nod-funktion här uppe i toppen. På så sätt förhoppningsvis kommer att fungera. Låt oss ge detta en annan gå. Nu sammanställer allt. Allt är bra. 

Men på denna punkt har vi faktiskt inte kallas våra Infoga funktion. Vi bara vet att det sammanställer, så låt oss gå in och sätta några samtal i. Låt oss göra det i vår huvudsakliga funktion. Här kommenterade vi ut 5, 8 och 2, och då vi inte koppla dem här nere. Låt oss göra några samtal för att infoga, och låt oss också använda samma typ av saker som vi använde När vi gjort dessa printf samtal för att kontrollera att allt var få ordentligt. Jag ska kopiera och klistra in, och i stället för innehåller vi ska inte in. Och istället för 6, 10 och 1, vi kommer att använda 5, 8 och 2. Detta bör förhoppningsvis in 5, 8, och 2 in i trädet. Kompilera. Allt är bra. Nu ska vi faktiskt kör vårt program. 

Allt återvände falskt. Så, 5, 8 och 2 går inte, och det ser ut som innehåller inte hittade dem heller. Vad händer? Låt oss zooma ut. Det första problemet var att insatsen verkade återvända falsk, och det ser ut som beror på att vi kvar i vår avkastning falsk samtal, och vi aldrig återvände sant. Vi kan ställa upp det. Det andra problemet är nu även om vi gör - spara avslutar detta, kör make igen, har kompilera den, kör den - ser vi att något annat hänt här. Den 5, 8 och 2 var fortfarande aldrig funnit i trädet. Så vad händer? 

Låt oss ta en titt på denna i koden. Låt oss se om vi kan lista ut. Vi börjar med den förälder som inte är null. Vi sätter markörens aktuella lika med roten pekaren och vi kommer att arbeta oss ner genom trädet. Om den aktuella noden inte är null, så vet vi att vi kan gå ner lite. Vi sätter vårt moderbolag pekare att vara lika med den aktuella pekaren, kontrollerat värde - om värdena är samma vi återvände falskt. Om värdena är mindre flyttade vi till höger; Annars flyttade vi till vänster. Då kan vi bygga en nod. Jag zooma in lite. Och här kommer vi att försöka att koppla upp värdena vara samma. Vad händer? Låt oss se om det möjligen Valgrind kan ge oss en ledtråd. 

Jag gillar att använda Valgrind bara för att Valgrind riktigt snabbt kör och berättar om det finns några minnesfel. När vi kör Valgrind på koden, som ni kan se rätt here--Valgrind./binary_tree--and tryck enter. Du ser att vi inte hade något minne fel, så det ser ut som om allt är okej så här långt. Vi har några minnesläckor, som vi vet, eftersom vi inte händer att befria någon av våra noder. Låt oss försöka köra GDB att se vad som verkligen händer. Vi gör gdb. / Binary_tree. Det startat upp bra. Låt oss sätta en brytpunkt på insatsen. Låt oss springa. Det ser ut som vi aldrig kallas insatsen. Det ser ut som att problemet var bara att när jag bytte här nere i huvud - alla dessa printf samtal från innehåller - Jag har aldrig egentligen ändrats dessa att ringa insats. Nu ska vi ge det ett försök. Låt oss sammanställa. Alla ser bra där. Nu ska vi försöka köra det, se vad som händer. Okej! Allt ser ganska bra där. 

Den sista sak att tänka på är, finns det någon kant fall till denna insats? Och det visar sig att, ja, det ena kanten så att är alltid intressant att tänka på är, vad händer om ditt träd är tom och du kallar denna insats funktion? Kommer det att fungera? Nåväl, låt oss ge det ett försök. - Binary_tree c.. - Det sätt vi ska testa detta, kommer vi att gå ner till vår huvuduppgift, och i stället ledningar dessa noder upp så här, Vi kommer bara att kommentera bort hela saken, och i stället för ledningar upp noderna själva, Vi kan faktiskt bara gå vidare och ta bort allt detta. Vi kommer att göra allt som en uppmaning att sätta in. Så, låt oss göra - istället för 5, 8 och 2, kommer vi att sätta in 7, 3 och 9. Och sedan ska vi också vill infoga 6 också. Spara. Avsluta. Gör binärt träd. Det sammanställer alla. Vi kan bara köra det som är och se vad som händer, men det är också kommer att bli mycket viktigt att se till att Vi har inte några minnesfel, eftersom detta är en av våra kant fall som vi känner till. 

Låt oss se till att det fungerar bra under Valgrind, vilket vi kommer att göra genom att bara köra Valgrind. / binary_tree. Det ser ut som vi verkligen har en fel från en kontext - vi har denna segmenteringsfel. Vad hände? Valgrind berättar faktiskt oss var det är. Zooma ut lite. Det ser ut som det händer i vår insats funktion, där vi har en ogiltig läsning av storlek 4 på insats, linje 60. Låt oss gå tillbaka och se vad som händer här. Zooma ut riktigt snabbt. Jag vill se till att det inte går till kanten av skärmen så att vi kan se allt. Dra det i lite. Okej. Bläddra nedåt och problemet är här. Vad händer om vi får ner och vår nuvarande nod redan är noll, vår överordnade noden är null, så om vi ser upp på toppen, här - Om detta medan slinga aldrig utför eftersom vår nuvarande värdet är null - vår rot är null så nuvarande är null - då vårt moderbolag aldrig blir inställt på nuvarande eller till ett giltigt värde, så kommer föräldern också null. Vi måste komma ihåg att kontrollera att när vi kommer ner hit, och vi börjar komma förälderns värde. Så, vad händer? Tja, om föräldern är null - if (förälder == null) - då vet vi att det får inte finnas något i trädet. Vi måste försöka sätta in den vid roten. Vi kan göra det genom att bara sätta roten lika med den nya noden. Sedan vid denna tidpunkt, vi faktiskt inte vill gå igenom dessa andra saker. Istället, just här, kan vi göra antingen en annan-if-else, eller vi kunde kombinera allt här uppe i ett annat, men här ska vi bara använda annan och göra det på det sättet. Nu ska vi testa att se till att vårt moderbolag inte är null innan dess faktiskt försöker att komma åt dess fält. Detta kommer att hjälpa oss undvika segmenteringsfel. Så vi slutade, zooma ut, sammanställa, springa. 

Inga fel, men vi har fortfarande en massa minnesläckor eftersom vi inte befria någon av våra noder. Men om vi går upp här och vi ser på vår utskriften, ser vi att, ja, ser ut som alla våra insatser återvände sant, vilket är bra. Insatserna är alla sanna, och sedan lämpliga innehåller samtal är också sant. 

Bra jobbat! Det ser ut som att vi har lyckats skrivit inlägg. Det är allt vi har för denna veckas problembild Specifikation. En rolig utmaning att tänka på är hur du faktiskt skulle gå i och fri alla noderna i trädet. Vi kan göra det ett antal olika sätt, men jag lämnar det upp till dig att experimentera, och som en rolig utmaning, prova och se till att du kan se att detta Valgrind rapport tillbaka några fel och inga läckor. 

Lycka till på veckans Huffmankodning problembild, och vi ses nästa vecka! [CS50.TV]