[Powered by Google Translate] [Afsnit 7] [mindre behagelig] [Nate Hardison] [Harvard University] [Dette er CS50.] [CS50.TV] 

Velkommen til § 7. Takket være orkanen Sandy, stedet for at have en normal afsnit denne uge, vi gør dette walk-through, gennem den del af spørgsmålene. Jeg har tænkt mig at være efter sammen med det Problem Set 6 Specifikation og går gennem alle spørgsmålene i En sektion af spørgsmål sektion. Hvis der er nogen spørgsmål, bedes du sende disse på CS50 diskutere. 

Alright. Lad os komme i gang. Lige nu er jeg kigger på side 3 i Problem Set Specification. Vi vil først begynde at tale om binære træer eftersom de har en masse relevans for denne uges problem sæt - Den Huffman Tree kodning. En af de allerførste datastrukturer vi talte om på CS50 var array. Husk, at et array er en sekvens af elementer - alle af samme type - lagret lige ved siden af ​​hinanden i hukommelsen. Hvis jeg har et heltal array, jeg kan tegne ved hjælp af denne æsker-numre-heltal stil - Lad os sige, at jeg har 5 i den første boks, jeg har 7 i den anden, så har jeg 8, 10 og 20 i den sidste boks. Husk, at to virkelig gode ting om dette array er, at vi har denne konstant-time adgang til nogen bestemt element  i array, hvis vi kender dens indeks. For eksempel, hvis jeg ønsker at få fat det tredje element i array - på indeks 2 ved hjælp af vores nul-baseret indeksering system - Jeg bogstaveligt talt bare nødt til at gøre en simpel matematisk beregning, hop til denne position i sættet, trække de 8, der er gemt der, og jeg er god til at gå. 

En af de dårlige ting om dette array - som vi talte om da vi diskuterede hægtede lister - er, at hvis jeg ønsker at indsætte et element i denne array, Jeg har tænkt mig at have at gøre nogle flytte rundt. For eksempel, array denne ret her er i sorteret orden - sorteret i stigende rækkefølge - 5, derefter 7, derefter 8, derefter 10, og derefter 20 - men hvis jeg ønsker at indsætte nummer 9 i denne array, Jeg har tænkt mig at skulle flytte nogle af de elementer, for at gøre plads. Vi kan trække dette ud her. Jeg har tænkt mig at skulle flytte 5, 7, og derefter 8; skabe et hul, hvor jeg kan sætte 9, og derefter 10 og 20 kan gå til højre for 9. Det er lidt af en smerte, fordi i det værst tænkelige scenario - når vi skulle indsætte enten i begyndelsen eller slutningen af arrayet, vi afhængigt af hvordan er forskydning - vi kan ende med at skulle flytte alle de elementer at vi i øjeblikket er lagring i array. 

Så hvad var den måde omkring dette? Den måde omkring dette var at gå til vores linkede-list metode, hvor - stedet for at lagre de elementer 5, 7, 8, 10 og 20 alle ved siden af ​​hinanden i hukommelsen - hvad vi i stedet gjorde var gemme dem slags overalt, hvor vi ønskede at gemme dem i disse sammenkædede-liste noder, som jeg trækker ud her, slags ad hoc. Og så har vi forbandt dem sammen ved hjælp af disse næste pointers. Jeg kan have en pointer fra 5 til 7, en pointer fra 7 til 8, en pointer fra 8 til 10, og endelig en pointer fra 10 til 20, og derefter en null-pointer på 20 angiver, at der ikke er noget til venstre. Det trade-off, vi har her er, at nu, hvis vi ønsker at indsætte nummer 9 i vores sorteret liste, alt, hvad vi skal gøre, er at oprette en ny node med 9, wire det op til at pege på det relevante sted, og derefter re-wire på 8 til at pege ned til 9. Det er temmelig hurtigt, antager vi ved præcis, hvor vi ønsker at indsætte 9. Men trade-off i bytte for dette er, at vi nu har mistet den konstante-time adgang til nogen særlig del af vores datastruktur. For eksempel, hvis jeg ønsker at finde den fjerde element i denne linkede liste Jeg har tænkt mig at skulle starte ved begyndelsen af ​​listen og arbejde mig igennem tælle node-by-node, indtil jeg finder den fjerde. 

For at få bedre adgang ydeevne end en sammenkædet liste - men også bevarer nogle af de fordele, som vi havde i form af indsættelse-tid fra en sammenkædet liste - et binært træ vil være nødvendigt at bruge lidt mere hukommelse. Især i stedet for bare at have en pointer i et binært træ node - som den sammenkædede liste node gør - vi kommer til at tilføje endnu en pointer til den binære træknude. Snarere end blot at have en markør til den næste element, vi skal have en pointer til en venstre barn og en højre barn. 

Lad os tegne et billede at se, hvad der rent faktisk ser ud. Igen, jeg vil bruge disse kasser og pile. Et binært træ node vil starte med blot et enkelt kasse. Det kommer til at have en plads til den værdi, og så er det også kommer til at have en plads til venstre barn og højre barn. Jeg har tænkt mig at mærke dem her. Vi kommer til at have den venstre barn, og så vil vi have ret barn. Der er mange forskellige måder at gøre dette. Nogle gange for plads og bekvemmelighed, Jeg vil faktisk trække det ligesom jeg gør her på bunden hvor jeg har tænkt mig at få værdien i toppen, og derefter den højre barn på nederste højre, og venstre barn nederst til venstre. Går tilbage til denne øverste diagram Vi har værdien øverst, så har vi den venstre barn pointer, og så har vi ret-barn pointer. 

I Problem Set Specification, vi taler om at tegne en node, der har en værdi 7, og derefter en venstre-barn pointer, der er null, og en højre-barn pointer, der er null. Vi kan enten skrive kapital NULL i rummet for både venstre barn og højre barn, eller vi kan trække denne diagonal skråstreg gennem hver af kasserne for at angive, at det er null. Jeg har tænkt mig at gøre, at bare fordi det er nemmere. Hvad du ser her er to måder diagrambaseret en meget simpel binær træknude hvor vi har værdien 7 og null barn pointers. 

Den anden del af vores specifikation taler om, hvordan med hægtede lister - husk, havde vi kun at holde fast i den allerførste element i en liste at huske hele listen - og ligeledes med et binært træ, har vi kun at holde fast i en pegepind til træet for at opretholde kontrol over hele datastruktur. Denne særlige element i træet kaldes rodknuden i træet. For eksempel, hvis denne ene node - dette knudepunkt indeholder værdien 7 med null venstre-og højre-barn pointers - var den eneste værdi i vores træ, så ville det være vores rodnoden. Det er begyndelsen af ​​vores træ. Vi kan se det lidt mere klart, når vi begynder at tilføje flere noder til vores træ. Lad mig trække op en ny side. 

Nu vil vi tegne et træ, der har 7 ved roden, og 3 indersiden af ​​venstre barn, og 9 indersiden af ​​højre barn. Igen, dette er ret simpelt. Vi har 7, tegne en node for 3, en node for 9, og jeg har tænkt mig at sætte venstre-barn pointer på 7 til at pege på det knudepunkt, der indeholder 3, og højre barnets pointer af knudepunktet indeholdende 7 til knudepunktet indeholdende 9. Nu behøver siden 3 og 9 ikke har nogen børn, vi kommer til at indstille alle deres barn pegepinde til at være null. Her roden af ​​vores træ svarer til knudepunktet indeholder tallet 7. Du kan se, at hvis vi alle har, er en pegepind til at roden node, vi kan så gå igennem vores træ og adgang til begge barn noder - både 3 og 9. Ingen grund til at opretholde henvisninger til hver enkelt node på træet. Alright. Nu vil vi tilføje en anden node til dette diagram. Vi vil tilføje en node indeholdende 6, og vi vil tilføje dette som højre barn af node indeholdende 3. For at gøre dette, vil jeg slette, at null-pointer i 3-node og wire det op til at pege på det knudepunkt indeholdende 6. Alright. 

På dette tidspunkt, lad os gå over en lille smule af terminologi. For at starte, årsagen til, at dette kaldes et binært træ i særdeleshed er, at det har to underordnede pointers. Der er andre typer af træer, der har flere børn pointers. Især gjorde du en 'prøve' i Problem Set 5. Du vil bemærke, at i denne prøve, du havde 27 forskellige henvisninger til forskellige børn - en for hver af de 26 bogstaver i det engelske alfabet, og derefter den 27. til apostrof - så, det er ligner en type træ. Men her, da det er binære, vi kun har to børn pointers. 

Ud over dette rod node, som vi talte om, vi har også været at smide omkring dette begreb 'barn'. Hvad betyder det for en knude at være et barn af en anden node? Det bogstaveligt betyder, at et barn node er et barn af en anden node hvis det andet knudepunkt har en af ​​underordnede pointers indstillet til at pege på det pågældende knudepunkt. For at sætte dette i mere konkrete termer, hvis 3 bliver peget på af en af ​​barnets pointers på 7, så 3 er et barn på 7. Hvis vi skulle finde ud af, hvad børnene på 7 er - godt, vi se, at 7 har en pointer til 3 og en pegepind til 9, så 9 og 3 er børn af 7. Ni har ingen børn, fordi dens barn pointers er null, og 3 har kun ét barn, 6. Seks har heller ingen børn, fordi begge sine pointers er null, som vi vil trække lige nu. 

Desuden har vi også tale om forældre til en bestemt node, og det er, som du ville forvente, det modsatte af dette barn beskrivelse. Hver node har kun én forælder - i stedet for to, som man kunne forvente med mennesker. For eksempel er moderselskab for 3 7. Den forælder af 9 er også 7, og forælder til 6 er 3. Ikke meget til det. Vi har også vilkår at snakke om bedsteforældre og børnebørn, og mere generelt taler vi om forfædrene og efterkommere af et bestemt knudepunkt. Den forfader til en knude - eller forfædre, snarere af en knude - er alle de knudepunkter, der ligger på vejen fra roden til det pågældende knudepunkt. For eksempel, hvis jeg ser på knudepunktet 6 derefter forfædre vil være både 3 og 7. Forfædrene til 9, for eksempel, er - hvis jeg kigger på knudepunktet 9 - så stamfader til 9 er kun 7. Og efterkommere er præcis det modsatte. Hvis jeg ønsker at se på alle de efterkommere af 7, så er jeg nødt til at se på alle knuder under den. Så jeg har 3, 9 og 6 alle som efterkommere af 7. 

Den endelige udtryk, som vi vil tale om, er dette begreb om at være en søskende. Søskende - slags følge med på disse familie vilkår - er noder, der er på samme niveau i træet. Så, 3 og 9 er søskende, fordi de er på samme niveau i træet. De har begge den samme forælder, 7. De 6 har ingen søskende, fordi 9 ikke har nogen børn. Og 7 har ikke nogen søskende, fordi det er roden til vores træ, og der er altid kun 1 root. For 7 har søskende der skulle være et knudepunkt over 7. Der skulle være en forælder på 7, i hvilket tilfælde 7 ville ikke længere være roden af ​​træet. Så det nye moderselskab 7 vil også nødt til at få et barn, og at barnet ville så være søskende til 7. 

Alright. Flytning af. Da vi startede vores diskussion af binære træer, vi talte om, hvordan vi skulle bruge dem til at opnå en fordel over begge arrays og hægtede lister. Og den måde, vi kommer til at gøre det på er med denne bestilling ejendom. Vi siger, at et binært træ er bestilt ifølge beskrivelsen Hvis for hvert knudepunkt i vores træ, alle dens efterkommere til venstre - den venstre barn og alle venstre barnets efterkommere - har mindre værdier, og alle de noder på højre - den rigtige barn og alle højre barnets efterkommere - har knuder større end værdien af ​​den aktuelle node, som vi kigger på. Bare for enkelhed, vil vi antage, at der ikke er nogen dubletter knuder i vores træ. For eksempel har vi i dette træ kommer ikke til at behandle sagen hvor vi har værdien 7 ved roden  og så har vi også værdien 7 andre steder i træet. I dette tilfælde, vil du bemærke, at dette træ faktisk er bestilt. Vi har værdien 7 ved roden. Alt til venstre for 7 - hvis jeg fortryde alle disse små mærker her - Alt til venstre for 7 - 3 og 6 - disse værdier er begge mindre end 7, og alt til højre - der er bare denne 9 - er større end syv. 

Dette er ikke den eneste bestilte træ indeholdende disse værdier, men lad os trække et par mere af dem. Der er faktisk en hel bunke af måder, vi kan gøre dette. Jeg har tænkt mig at bruge en forkortelse bare for at holde tingene simple hvor - snarere end at trække ud hele æsker-og-pile - Jeg skal bare til at trække tallene og tilføje pile forbinder dem. Hvis du vil starte, vi vil bare skrive vores oprindelige træ igen, hvor vi havde 7 og derefter en 3, og derefter 3 pegede tilbage til højre til 6, og 7 havde en højre barn, der var 9. Alright. Hvad er en anden måde, at vi kunne skrive dette træ? I stedet for 3 være den venstre barn 7, kunne vi også have 6 være den venstre barn på 7, og derefter 3 være den venstre barn af 6. Det ville ligne dette træ lige her, hvor jeg har fået 7, derefter 6, derefter 3 og 9 til højre. Vi har også behøver ikke at have 7 som vores root node. Vi kunne også have 6 som vores root node. Hvad ville det se ud? Hvis vi skal fastholde denne bestilt ejendom, alt til venstre for 6 skal være mindre end det. Der er kun én mulighed, og det er 3. Men så som højre barn på 6, har vi to muligheder. Først kunne vi have 7 og derefter 9, eller vi kunne tegne det - ligesom jeg er ved at gøre her - hvor vi har 9 som højre barn af 6, og derefter 7 som venstre barn af 9. 

Nu, 7 og 6 er ikke de eneste mulige værdier for roden. Vi kunne også have 3 være årsagen. Hvad sker der, hvis 3 er ved roden? Her tingene bliver en lille smule interessant. Tre ikke har nogen værdier, der er mindre end det, så at hele venstre side af træet er bare at være null. Der kommer ikke til at være noget der. Til højre, kunne vi nævne tingene i stigende rækkefølge. Vi kunne have 3, derefter 6 og derefter 7, så 9. Eller, kunne vi gøre 3, derefter 6, derefter 9, derefter 7. Eller, kunne vi gøre 3, derefter 7, derefter 6, derefter 9. Eller, 3, 7 - faktisk nej, kan vi ikke gøre en 7 længere. Det er vores eneste ting der. Vi kan gøre 9, og derefter fra 9 vi kan gøre 6 og derefter 7. Eller kan vi gøre 3, derefter 9, derefter 7, og derefter 6. 

Én ting er at henlede Deres opmærksomhed på her er at disse træer er lidt mærkeligt udseende. I Hvis vi især ser på 4 træer på højre side - Jeg vil cirkle dem, her - disse træer ser næsten præcis som en linket liste. Hvert knudepunkt har kun et barn, og så har vi ikke noget af dette træ-lignende struktur, som vi ser, for eksempel,  i dette ene Lone Tree herovre på den nederste venstre. Disse træer er faktisk kaldes degenererede binære træer, og vi vil tale om disse mere i fremtiden - især hvis du gå på at tage andre datalogikurser. Disse træer er degenereret. De er ikke meget nyttigt, fordi, ja, denne struktur egner sig  at slå gange svarende til den for en forbundet liste. Vi får ikke at drage fordel af den ekstra hukommelse - denne ekstra pointer - på grund af vores struktur er dårlig på denne måde. Snarere end at gå på og trække ud de binære træer, der har 9 ved roden, som er den sidste sag, som vi ville have, vi er i stedet, på dette tidspunkt, vil tale lidt om dette andet udtryk at vi bruger når vi taler om træer, som kaldes højden. 

Højden af ​​et træ er afstanden fra roden til den mest fjerntliggende knudepunkt, eller snarere antallet af humle, som du ville have at gøre med henblik på at starte fra roden og derefter ender på det mest for fjern node i træet. Hvis vi ser på nogle af disse træer, som vi har tegnet lige her, Vi kan se, at hvis vi tager dette træ i øverste venstre hjørne, og vi starter på 3, så er vi nødt til at gøre 1 hop for at komme til 6, en anden hop for at komme til 7, og en tredje hop at komme til 9. Således, at højden af ​​dette træ er 3. Vi kan gøre det samme øvelse for de andre træer, der er skitseret i denne grønne, og vi kan se, at højden af ​​alle disse træer er også virkelig 3. Det er en del af hvad der gør dem degenerere - at deres højde er blot en mindre end antallet af knudepunkter i hele træet. Hvis vi ser på dette andet træ, der er omgivet med røde, på den anden side, vi se, at de mest fjerntliggende blad noder er 6 og 9 - bladene er de knuder, der ikke har børn. Så for at komme fra rodnoden til enten 6 eller 9, vi gøre en hop at komme til 7 og derefter en anden hop at komme til 9, og ligeledes, at kun en anden hop fra 7 komme til 6. Så højden af ​​dette træ herovre er kun 2. Du kan gå tilbage og gøre det for alle de andre træer, som vi tidligere diskuterede begyndende med 7 og 6, og du vil opdage, at højden af ​​alle disse træer er også 2. 

Grunden til at vi har talt om bestilt binære træer og hvorfor de er cool, fordi du kan søge igennem dem i en meget lignende måde at søge over et ordnet array. Det er her, vi taler om at få det bedre lookup tid over den enkle forbundet liste. Med en sammenkædet liste - hvis du ønsker at finde et bestemt element - du er i bedste fald kommer til at gøre en slags lineær søgning hvor du starter i begyndelsen af ​​en liste og hop én efter én - en knude ved et knudepunkt - gennem hele listen, indtil du finder det, du søger efter. Betragtninger, hvis du har et binært træ, der er lagret i denne nice format, du kan faktisk få mere af en binær søgning foregår hvor du del og hersk og søgning via passende halvdel af træet i hvert trin. Lad os se, hvordan det fungerer. 

Hvis vi har - igen, gå tilbage til vores oprindelige træ - vi starter kl 7, vi har 3 på venstre, 9 til højre, og under 3 vi har 6. Hvis vi ønsker at søge efter nummer 6 i dette træ, ville vi starte ved roden. Vi ville sammenligne den værdi, vi leder efter, siger 6, til værdien lagret i knude som vi i øjeblikket ser på, 7, finder, at 6 er faktisk mindre end 7, så vi ville flytte til venstre. Hvis værdien af ​​6 havde været større end 7, ville vi have i stedet flyttet til højre. Da vi ved, at - på grund af strukturen i vores bestilte binært træ - alle værdier mindre end 7 vil blive gemt til venstre for 7, der er ingen grund til engang gider kigge gennem højre side af træet. Når vi flytter til venstre, og vi er nu ved knudepunktet indeholdende 3, vi kan gøre det samme sammenligning igen, hvor vi sammenligner 3 og 6. Og vi finder, at mens 6 - den værdi, vi leder efter - er større end 3, vi kan gå til højre side af knudepunktet indeholdende 3. Der er ingen venstre side her, så vi kunne have ignoreret det. Men vi ved kun, at fordi vi ser på selve træet, og vi kan se, at træet har ingen børn. 

Det er også ret nemt at slå op 6 i dette træ, hvis vi gør det os selv som mennesker, men lad os følge denne proces mekanisk som en computer ville gøre for virkelig at forstå algoritmen. På dette tidspunkt er vi nu ser på en node, der indeholder 6, og vi leder efter værdien 6, så, ja, vi har fundet den rette node. Vi fandt værdien 6 i vores træ, og vi kan stoppe vores søgning. På dette tidspunkt, afhængigt af hvad der foregår kan vi sige, ja, vi har fundet værdien 6, det eksisterer i vores træ. Eller, hvis vi planlægger at indsætte en node eller gøre noget, kan vi gøre det på dette tidspunkt. 

Lad os gøre et par flere opslag bare for at se hvordan det virker. Lad os se på, hvad der sker, hvis vi skulle forsøge at slå op værdien 10. Hvis vi skulle se op værdien 10, ville vi starte ved roden. Vi ville se, at 10 er større end 7, så vi ville flytte til højre. Vi ville komme til 9 og sammenligne 9 til 10 og se, at 9 er faktisk mindre end 10. Så igen, ville vi forsøge at flytte til højre. Men på dette punkt, ville vi opdage, at vi er på en null knudepunkt. Der er ikke noget der. Der er ikke noget, hvor 10 bør være. Det er her, vi kan rapportere fejl - at der rent faktisk er nr. 10 i træet. Og endelig, lad os gå igennem det tilfælde, hvor vi forsøger at slå op 1 i træet. Dette svarer til, hvad der sker, hvis vi ser op 10, undtagen i stedet for at gå til højre, vi kommer til at gå til venstre. Vi starter på 7 og se, at 1 er mindre end 7, så vi flytter til venstre. Vi får til 3 og se, at 1 er mindre end 3, så vi igen forsøger at flytte til venstre. På dette tidspunkt har vi en null knude, så vi igen kan rapportere fejl. 

Hvis du ønsker at lære mere om binære træer, Der er en hel masse sjove små problemer, som du kan gøre med dem. Jeg foreslår udøvelse af tegningen af ​​disse diagrammer en efter en og efter gennem alle de forskellige trin, da dette vil komme i super-handy ikke kun når du laver Huffman kodning problem sæt men også i fremtidige kurser - bare lære at trække ud disse datastrukturer og tænke igennem de problemer med pen og papir eller i dette tilfælde, og iPad stylus. 

På dette tidspunkt selv, vi kommer til at gå videre til at gøre nogle kodning praksis og faktisk spille med disse binære træer og se. Jeg har tænkt mig at skifte tilbage til min computer. For denne del af strækningen, i stedet for at bruge CS50 Run eller CS50 Spaces, Jeg har tænkt mig at bruge apparatet. 

Efter sammen med Problem Set specifikation, Jeg kan se, at jeg skulle åbne apparatet, gå til min Dropbox mappe, skal du oprette en mappe kaldet § 7, og derefter oprette en fil kaldet binary_tree.c. Her går vi. Jeg har apparatet allerede åben. Jeg har tænkt mig trække op en terminal. Jeg har tænkt mig at gå til Dropbox mappe, lave en mappe kaldet section7, og se, det er helt tom. Nu jeg har tænkt mig at åbne op binary_tree.c. Alright. Her går vi - tom fil. 

Lad os gå tilbage til specifikationen. Specifikationen anmoder om at skabe en ny type definition et binært træ node indeholdende int værdier - ligesom de værdier, som vi trak i vores diagrammer før. Vi vil bruge denne standardtekst typedef, at vi har gjort lige her at du skal genkende fra Problem Set 5 - hvis du gjorde det hash tabel måde at erobre speller program. Du bør også genkende det fra sidste uges afsnit hvor vi talte om hægtede lister. Vi har fået dette typedef af en struct node, og vi har givet denne struct node dette navn på struct node forhånd så vi kan så henvise til det, da vi ønsker at have struct node pointers som en del af vores struct, men vi har da omringede dette - eller rettere indesluttet dette - i en typedef således at senere i koden, kan vi henvise til denne struct som bare en knude i stedet for en struct node. 

Dette vil være meget lig den enkeltvis-linkede liste definition, som vi så i sidste uge. For at gøre dette, lad os bare starte med at skrive ud standardtekst. Vi ved, at vi skal have en heltalsværdi, så vi vil sætte i int værdi, og så i stedet for at have bare en pointer til den næste element - som vi gjorde med enkeltvis-linked lister - vi bliver nødt til venstre og højre barn pointers. Det er temmelig simpelt også - struct node * venstre barn; og struct node * rigtige barn. Cool. Det ligner en ganske god start. Lad os gå tilbage til specifikationen. 

Nu skal vi til at erklære en global node * variabel for roden af ​​et træ. Vi vil gøre dette globale ligesom vi gjorde første pointerjustering i vores linkede liste også globalt. Det var så at i de funktioner, som vi skriver Vi behøver ikke at holde passerer omkring dette rod - selvom vi vil se, at hvis du ønsker at skrive disse funktioner rekursivt, Det kan være bedre at ikke engang passere den rundt som en global i første omgang og i stedet initialisere det lokalt i din primære funktion. Men, vil vi gøre det på globalt plan at starte. Igen, vil vi give et par rum, og jeg har tænkt mig at erklære en node * rod. Blot for at sørge for, at jeg ikke forlade dette initialiseret, vil jeg sætte den lig med nul. Nu, i hovedfunktion - som vi vil skrive virkelig hurtigt lige her - int main (int argc, const char * argv []) - og jeg har tænkt mig at begynde at erklære min argv array som const bare så jeg ved, at disse argumenter er argumenter, som jeg sandsynligvis ikke vil ændre. Hvis jeg ønsker at ændre dem jeg burde nok være at gøre kopier af dem. Du vil se denne meget i kode. Det er fint begge veje. Det er fint at lade det være som - udelade const, hvis du ønsker. Jeg typisk sætte det i bare så minder jeg mig selv  at jeg sandsynligvis ikke ønsker at ændre disse argumenter. 

Som altid, vil jeg medtage denne return 0 linje i slutningen af ​​main. Her vil jeg initialisere min rodnoden. Som det ser ud lige nu, jeg har en pointer, der er sat til nul, så det peger på noget. For rent faktisk at begynde at opbygge den knude, Jeg skal først tildele hukommelse til det. Jeg har tænkt mig at gøre det ved at gøre hukommelse på heapen ved hjælp af malloc. Jeg har tænkt mig at sætte rod lig med resultatet af malloc, og jeg har tænkt mig at bruge sizeof operatør til at beregne størrelsen af ​​en node. Grunden til at jeg bruger sizeof node i modsætning til, sige, gør noget som dette - malloc (4 + 4 +4) eller malloc 12 - er fordi jeg vil have min kode til at være så kompatibelt som muligt. Jeg ønsker at være i stand til at tage denne. C. fil, kompilere det på apparatet, og derefter kompilere det på min 64-bit Mac - eller på et helt andet arkitektur - og jeg ønsker alt dette til at arbejde det samme. 

Hvis jeg gør antagelser om størrelsen af ​​variabler - størrelsen af ​​en int eller størrelsen af ​​en pegepind - så er jeg også at gøre antagelser om, hvilke former for arkitekturer som min kode kan lykkes at kompilere når de kører. Brug altid sizeof i modsætning til manuelt at summere struct felter. Den anden grund er, at der også kan være polstring at compileren lægger i struct. Selv bare summere de enkelte områder er ikke noget, du typisk vil gøre, så skal du slette denne linje. Nu, for virkelig at initialisere denne rod node, Jeg har tænkt mig at skulle tilslutte værdier for hver af de forskellige felter. For eksempel, for værdi jeg ved, at jeg vil initialisere til 7 og for nu jeg har tænkt mig at sætte venstre barn til at være null og højre barn også være nul. Great! Vi har gjort denne del af spec. 

Specifikationen ned i bunden af ​​side 3 beder mig om at oprette tre flere knuder - en indeholdende 3, en indeholdende 6, og en med 9 - og derefter wire dem op, så det ser ud præcis som vores trædiagram at vi talte om tidligere. Lad os gøre det ret hurtigt her. Du vil se virkelig hurtigt, at jeg har tænkt mig at begynde at skrive en masse dobbelt kode. Jeg har tænkt mig at oprette en node * og jeg har tænkt mig at kalde det tre. Jeg har tænkt mig at sætte det lig med malloc (sizeof (node)). Jeg har tænkt mig at sætte tre-> værdi = 3. Tre -> left_child = NULL; tre -> højre _child = NULL; så godt. Det ser temmelig ligner initialisere roden, og det er præcis, hvad Jeg har tænkt mig at gøre, hvis jeg starter initialisering 6 og 9 samt. Jeg vil gøre det virkelig hurtigt her - faktisk, jeg vil gøre lidt kopiere og indsætte, og sørg for, at I - okay.  Nu har jeg fået det kopieret, og jeg kan gå videre og indstille denne lig med 6. Du kan se, at det tager et stykke tid og er ikke super-effektiv. På bare en lille smule, vil vi skrive en funktion, der vil gøre dette for os. Jeg ønsker at erstatte dette med en 9, erstatte det med en 6. 

Nu har vi alle vores knudepunkter skabt og initialiseret. Vi har fået vores rod sat lig med 7, eller indeholder værdien 7, vores node indeholdende 3, vores node indeholdende 6, og vores node indeholdende 9. På dette tidspunkt, er alt hvad vi behøver at gøre wire hele op. Grunden til at jeg initialiseres alle pegepinde til null er bare så at jeg sørge for, at Jeg har ikke nogen startværdi pejlemærker i der ved et uheld. Og også siden, på dette tidspunkt, jeg kun har til rent faktisk at forbinde noder til hinanden - til dem, at de faktisk er tilsluttet - Jeg behøver ikke at gå igennem og gøre sikker på, at alle nuller er derinde i de relevante steder. 

Start ved roden, jeg ved, at roden venstre barn er 3. Jeg ved, at roden ret barn er 9. Efter dette, den eneste Barn, jeg har tilbage at bekymre sig om er 3 ret barn, hvilket er 6. På dette tidspunkt, det hele ser temmelig godt. Vi vil slette nogle af disse linjer. Nu er alt ser godt ud. Lad os gå tilbage til vores specifikationer og se, hvad vi skal gøre næste. 

På dette punkt har vi at skrive en kaldet funktionen 'indeholder' med en prototype af "bool Indeholder (int værdi) '. Og det indeholder funktionen vil returnere sandt  hvis træet peget på af vores globale rod variabel  indeholder den værdi, der sendes ind i funktionen og falsk ellers. Lad os gå videre og gøre det. Dette vil være præcis som det opslag, som vi gjorde ved hånden på iPad bare en lille smule siden. Lad os ind i en lille smule og rulle op. Vi vil sætte denne funktion lige over vores vigtigste funktion så vi ikke behøver at gøre nogen form for prototyping. Så bool indeholder (int værdi). Der vi går. Der er vores standardtekst erklæring. Blot for at sørge for, at dette vil kompilere, Jeg har tænkt mig at gå videre og bare sætte den lig returnere falsk. Lige nu denne funktion vil bare ikke gøre noget, og altid rapportere, at den værdi, vi leder efter, er ikke i træet. 

På dette tidspunkt er det nok en god ide - siden vi har skrevet en hel bunke af kode, og vi har ikke engang prøvet at teste det endnu - at sikre, at det hele kompilerer. Der er et par ting, som vi skal gøre for at sikre, at dette rent faktisk vil kompilere. Først se, om vi har brugt alle funktioner i nogen biblioteker, som vi endnu ikke har medtaget. De funktioner, vi har brugt hidtil er malloc, og så har vi også brugt denne type - denne ikke-standard type kaldet 'bool' - som er inkluderet i standard bool header fil. Vi vil helt sikkert inkludere standard bool.h for den bool type, og vi ønsker også at # include standard lib.h for standard biblioteker der omfatter malloc, og gratis, og alt dette. Så zoome ud, vi kommer til at holde op. Lad os forsøge at sikre, at dette rent faktisk gjorde kompilere. Vi ser, at det gør det, så vi er på rette spor. 

Lad os åbne binary_tree.c igen. Det kompilerer. Lad os gå ned og sørg for, at vi indsætter nogle opkald til vores indeholder funktionsmoduler - bare for at sørge for, at det er alt sammen meget godt. For eksempel, når vi gjorde nogle opslag i vores træ tidligere vi forsøgte at slå værdierne op 6, 10 og 1, og vi vidste, at 6 var i træet, 10 var ikke i træet, og 1 var ikke i træet enten. Lad os bruge disse eksempler opkald som en måde at finde ud af, om eller ej vores Indeholder funktion er aktiveret. For at gøre det, vil jeg bruge printf funktion, og vi kommer til at udskrive resultatet af indkaldelsen til indeholder. Jeg har tænkt mig at sætte i en streng "indeholder (% d) = fordi  vi kommer til at tilslutte den værdi, vi vil kigge efter, og =% s \ n "og bruge det som vores formatstreng. Vi vil bare se - bogstaveligt talt udskrive på skærmen - hvad der ligner et funktionskald. Det er faktisk ikke den funktion opkald.  Dette er blot en streng designet til at ligne en funktion opkald. 

Nu vil vi tilslutte værdierne. Vi vil prøve indeholder den 6, og derefter hvad vi vil gøre her er at bruge det ternære operatør. Lad os se - indeholder 6 - ja, nu har jeg indeholdt 6, og hvis indeholder 6 er sandt, den streng, som vi vil sende til% s format karakter bliver strengen "true". Lad os rulle over en lille smule. Ellers ønsker vi at sende strengen "falsk", hvis indeholder 6 returnerer falsk. Dette er en lille goofy udseende, men jeg regner med jeg kan lige så godt illustrere hvad den ternære operatør ser ud, da vi ikke har set det for en stund. Dette vil være en pæn, smart måde at finde ud af, om vores Indeholder funktion er aktiveret. Jeg har tænkt mig at rulle tilbage over til venstre, og jeg har tænkt mig at kopiere og indsætte denne linje et par gange. Det ændrede nogle af disse værdier omkring, så dette vil være 1, og dette vil være 10. 

På dette tidspunkt har vi en pæn indeholder funktionsmoduler. Vi har nogle tests, og vi vil se, hvis dette alle værker. På dette tidspunkt har vi skrevet nogle mere kode. Tid til at forlade ud og sørg for, at alt stadig kompilerer. Afslut ud, og lad os nu prøve at lave binært træ igen. Tja, det ser ud til vi har fået en fejl, Og vi har dette udtrykkeligt erklærer biblioteksfunktionen printf. Det ser ud til vi skal gå ind og # include standardio.h. Og med dette, burde alt kompilere. Vi er alle gode. Lad os nu prøve at køre binært træ og se hvad der sker. Her er vi,. / Binary_tree, og vi kan se, at som vi forventede - fordi vi ikke har gennemført indeholder endnu, eller rettere, vi har lige sat i return false - vi se, at det bare er tilbage falsk for dem alle, så er alt arbejder for det meste temmelig godt. 

Lad os gå tilbage i og faktisk gennemfører indeholder på dette punkt. Jeg har tænkt mig at rulle ned, zoome ind, og - husk, den algoritme, som vi brugte var, at vi startede på rodnoden og derefter ved hvert knudepunkt, som vi støder på, gør vi en sammenligning, og baseret på denne sammenligning vi enten bevæge sig mod venstre barn eller højre barn. Dette kommer til at se meget ligner den binære søgekoden, som vi skrev tidligere i udtrykket. Når vi starter, ved vi, at vi ønsker at holde fast i den aktuelle node at vi kigger på, og den aktuelle node vil blive initialiseret til roden node. Og nu vil vi holde gå gennem træet, og husk, at vi stopper tilstand -  når vi faktisk arbejdede gennem eksempel med hånden - var, da vi stødte på en null knude, ikke når vi kiggede på en null barn, men når vi faktisk flyttet til et knudepunkt i træet og fandt, at vi er på en null knudepunkt. Vi kommer til at gentage indtil cur ikke er lig med nul. Og hvad skal vi gøre? Vi kommer til at teste, om (nuværende -> værdi == værdi), så ved vi, at vi faktisk har fundet den knude, som vi leder efter. Så her kan vi returnere sandt. Ellers ønsker vi at se, om eller ikke værdien er mindre end værdien. Hvis den aktuelle node værdi er mindre end den værdi, vi leder efter, vi kommer til at flytte til højre. Så nuværende = nuværende -> right_child, og ellers vil vi flytte til venstre. cur = cur -> left_child. Temmelig enkel. 

Du kender måske den løkke, ligner meget det fra binær søgning tidligere i udtrykket, undtagen da vi havde at gøre med lav, middel og høj. Her har vi bare nødt til at se på en aktuel værdi, så det er rart og enkel. Lad os sørge for denne kode virker. Først sørg for at det kompilerer. Ligner det gør. Lad os prøve at køre det. Og ja, den udskriver alt, hvad vi forventede. Den finder 6 i træet, ikke finder 10, fordi 10 ikke er i træet, og ikke finder 1 enten fordi 1 er heller ikke i træet. Cool stuff. 

Alright. Lad os gå tilbage til vores specifikationer og se, hvad der bliver det næste. Nu er det ønsker at tilføje nogle flere knuder til vores træ. Den ønsker at tilføje 5, 2, og 8, og sørg for, at vores indeholder kode stadig fungerer som forventet. Lad os gå gøre det. På dette tidspunkt, i stedet for at gøre det irriterende kopiere og indsætte igen lad os skrive en funktion til rent faktisk at oprette en node. Hvis vi rulle ned hele vejen til main, kan vi se, at vi har gjort dette meget ens kode igen og igen hver gang, at vi ønsker at skabe en node. 

Lad os skrive en funktion, der rent faktisk vil bygge en node for os og returnere det. Jeg har tænkt mig at kalde det build_node. Jeg har tænkt mig at bygge en node med en bestemt værdi. Zoom ind her. Den første ting jeg har tænkt mig at gøre, er faktisk at skabe plads til node på heapen. Så node * n = malloc (sizeof (node)), n -> value = værdi; og så her, jeg bare at initialisere alle felterne for at være passende værdier. Og til allersidst, vil vi returnere vores node. Alright. Én ting at bemærke er, at denne funktion lige her kommer til at returnere en pointer til hukommelsen, der har været heap-tildelte. Hvad er nice om dette er, at denne knude nu - vi er nødt til at erklære den på heapen, fordi hvis vi erklærede det på stakken ville vi ikke være i stand til at gøre det i denne funktion som denne. Denne hukommelse ville gå ud af rækkevidde og ville være ugyldig, hvis vi forsøgte at få adgang til det senere. Da vi erklære heap-allokeret hukommelse, vi er nødt til at tage sig af at befri den senere for vores program til ikke lække nogen hukommelse. Vi har punting på, at der for alt andet i koden kun for nemheds skyld på det tidspunkt, men hvis du nogensinde skrive en funktion, der ligner denne hvor du har fået - nogle kalder det en malloc eller realloc inde - du vil være sikker på, at du lægger en slags kommentar heroppe der siger, hey, du ved, returnerer en bunke-tildelte node initialiseret med de beståede-i værdi. Og så du vil være sikker på, at du lægger i en slags notat, der siger opkalderen skal befri den returnerede hukommelse. På den måde, hvis nogen nogensinde går og bruger denne funktion, de ved, at uanset hvad de kommer tilbage fra denne funktion på et tidspunkt skal frigøres. 

Antages det, at alt er vel og godt her, vi kan gå ned i vores kode og erstatte alle disse linjer lige her med opkald til vores build node-funktionen. Lad os gøre det virkelig hurtigt. Den ene del, som vi ikke kommer til at erstatte, er denne del hernede ved bunden, hvor vi faktisk wire op knudepunkterne til at pege på hinanden, fordi at vi ikke kan gøre i vores funktion. Men, lad os gøre root = build_node (7); node * tre = build_node (3); node * seks = build_node (6), node * ni = build_node (9). Og nu har vi også ønsket at tilføje noder til - node * fem = build_node (5); node * otte = build_node (8); og hvad var den anden knude? Lad os se her. Vi ønskede også at tilføje en 2 - node * to = build_node (2). Alright. På dette tidspunkt ved vi, at vi har fået den 7, 3, 9, og 6 alle kabelførte passende op, men hvad med 5, 8 og 2? For at holde alt i den rigtige rækkefølge, Vi ved, at tre ret barn er 6. Så hvis vi kommer til at tilføje 5, de 5 også hører til i den højre side af træet, hvoraf 3 er roden, så 5 hører som venstre barn af 6. Vi kan gøre dette ved at sige, seks -> left_child = fem; og derefter 8 hører som venstre barn 9, så ni -> left_child = otte; og derefter 2 er den venstre barn af 3, så vi kan gøre det op her - Dig -> left_child = to;. Hvis du ikke helt følge med det, jeg foreslår, at du trækker det ud selv. 

Alright. Lad os gemme det. Lad os gå ud og sørg for at det kompilerer, og så kan vi tilføje i vores Indeholder opkald. Ligner alt stadig kompilerer. Lad os gå ind og tilføje i nogle indeholder opkald. Igen, jeg vil gøre en lille smule af kopiere og indsætte. Lad os nu søge efter 5, 8 og 2. Alright. Lad os sørge for, at alt dette ser godt ud endnu. Great! Gem og afslut. Nu lad os gøre, kompilere, og lad os nu køre. Ud fra resultaterne ser det ud som alt fungerer bare rart og godt. Great! Så nu har vi fået vores indeholder funktionsmoduler skrevet. Lad os gå videre og begynde at arbejde på, hvordan man indsætter noder i træet siden, da vi gør det lige nu, er tingene ikke meget smuk. 

Hvis vi går tilbage til specifikationen, det beder os om at skrive en funktion kaldet indsætte - igen, returnerer en bool for, hvorvidt vi faktisk kunne indsætte node i træet - og derefter den værdi der skal indsættes i træet er angivet som det eneste argument til vores Indsæt funktion. Vi vil vende tilbage sandt, hvis vi rent faktisk kunne indsætte den knude, der indeholder værdi ind i træet, hvilket betyder, at vi, den ene havde nok hukommelse, og derefter to, havde denne node ikke allerede eksisterer i træet siden - Husk, vi ikke vil have dublerede værdier i træet, bare for at gøre tingene simple. Alright. Back til koden. Åben den op. Zoom ind på en smule, derefter rulle ned. Lad os sætte indsatsen funktionen lige over indeholder. Igen, det kommer til at hedde bool insert (int værdi). Giv det lidt mere plads, og derefter, som en standard, lad os sætte i return false til allersidst. Nu nede i bunden, lad os gå videre og i stedet for manuelt at bygge knudepunkterne i main os selv og ledninger dem op til at pege på hinanden som vi gør, vi stole på vores insert funktion til at gøre det. Vi vil ikke stole på vores insert funktion til at bygge hele træet fra bunden endnu, men snarere vi slippe af med disse linjer - we'll udkommentere disse linjer - der bygger knudepunkterne 5, 8 og 2. Og i stedet, vil vi indsætte opkald til vores insert funktion at sikre, at der rent faktisk virker. Her går vi. 

Nu har vi kommenteret ud disse linjer. Vi har kun 7, 3, 9 og 6 i vores træ på dette punkt. For at sikre at dette er alle arbejder, vi kan zoome ud, gøre vores binært træ, køre det, og vi kan se, der indeholder nu fortæller os, at vi er helt rigtigt - 5, 8 og 2 ikke længere i træet. Gå tilbage ind i koden, og hvordan skal vi indsætte? Husk, hvad vi gjorde, da vi var faktisk indsætte 5, 8 og 2 tidligere. Vi spillede som Plinko spil, hvor vi startede ved roden, gik ned i træet én efter én efter én indtil vi fandt det passende hul, og så har vi kablet i knudepunktet på det rette sted. Vi vil gøre det samme. Dette er dybest set ligesom at skrive den kode, som vi brugte i indeholder funktionen at finde det sted, hvor noden skal være, og så er vi bare at indsætte node lige der. Lad os begynde at gøre det. 

Så vi har en node * cur = rod, vi er bare at følge den indeholder kode indtil vi finder, at det ikke helt virker for os. Vi vil gå gennem træet, mens det aktuelle element ikke er nul, og hvis vi opdager, at nuværende værdi er lig med den værdi, som vi forsøger at indsætte - godt, det er en af ​​de sager, hvor vi ikke kunne faktisk indsætte node ind i træet, fordi det betyder, at vi har en dobbelt værdi. Her vil vi faktisk kommer til at returnere falsk. Nu, ellers hvis nuværende værdi er mindre end værdien, nu ved vi, at vi flytter til højre  fordi værdien hører til i den højre halvdel af cur træet. Ellers vil vi flytte til venstre. Det er dybest set vores indeholder funktionsmoduler lige der. 

På dette tidspunkt, vi engang har fuldført denne while-løkken, vores nuværende pointer vil blive pege på null hvis funktionen ikke allerede vendt tilbage. Vi derfor har cur på det sted, hvor vi ønsker at indsætte den nye node. Hvad mangler at blive gjort, er at faktisk bygge det nye knudepunkt, som vi kan gøre temmelig nemt. Vi kan bruge vores super-handy build node-funktion, og noget, som vi ikke gjorde tidligere - vi bare slags tog for givet, men nu skal vi gøre blot at sørge for - vi vil teste for at sikre, at værdien returneret af ny knude var faktisk ikke null, fordi vi ikke ønsker at begynde at få adgang til denne hukommelse, hvis det er nul. Vi kan teste for at sikre, at ny node ikke er lig med nul. Eller i stedet, kan vi bare se, om det rent faktisk er nul, og hvis det er nul, så kan vi bare returnere falsk tidligt. 

På dette tidspunkt er vi nødt til wire ny knude i sit passende sted i træet. Hvis vi ser tilbage på main og hvor vi faktisk var ledninger i værdier før, vi se, at den måde, vi gjorde det, da vi ønskede at sætte 3 i træet blev vi åbnede venstre barn af roden. Når vi sætter 9 i træet, havde vi at få adgang til højre barn af roden. Vi skulle have en pointer til den forælder, for at sætte en ny værdi ind i træet. Rulning tilbage op til at indsætte, er det ikke kommer til at helt at arbejde her fordi vi ikke har en forælder pointer. Hvad vi ønsker at være i stand til at gøre, er, på dette tidspunkt, kontrollere forældrenes værdi og se - ja, gosh, hvis forældrenes værdi er mindre end den aktuelle værdi, så den forælder ret barn skulle være den nye knude; ellers skal den forælder venstre barn være den nye node. Men vi har ikke denne forælder pointer helt endnu. 

For at få det, vi faktisk nødt til at spore det, som vi går igennem træet og finde den rette plads i vores løkke ovenfor. Det kan vi gøre ved at rulle tilbage op til toppen af ​​vores insert funktion og sporing anden pointer variabel kaldet moderselskabet. Vi kommer til at indstille det lig nul i første omgang, og derefter hver gang vi går igennem træet, vi kommer til at indstille den forælder pointer til at matche den aktuelle pointer. Indstil forælder lig med cur. Denne måde, hver gang vi går igennem, vi vil sikre, at da den nuværende pointer bliver inkrementeres moderselskabet pointer følger det - bare et niveau højere end det aktuelle pointer i træet. At alle ser temmelig godt. 

Jeg tror, ​​den ene ting, vi har lyst til at justere er dette bygge knude tilbage null. For at få opbygge node til rent faktisk held returnere null, vi bliver nødt til at ændre denne kode, fordi her, vi aldrig testes for at sikre, at malloc returnerede en gyldig pointer. Så hvis (n = NULL!), Derefter - hvis malloc returnerede en gyldig pointer, så vil vi initialisere det; ellers vil vi bare vende tilbage, og det vil ende med at vende tilbage null for os. Nu er alle ser temmelig godt. Lad os sørge for dette faktisk kompilerer. Gør binært træ, og åh, vi har nogle ting der foregår her. 

Vi har fået en implicit erklæring af funktionen bygge node. Igen med disse compilere, vil vi starte på toppen. Hvad der må betyde, er, at jeg ringer bygge node, før jeg rent faktisk har erklæret det. Lad os gå tilbage til den kode virkelig hurtigt. Rul ned, og ganske rigtigt, min insert funktion der er erklæret over build node-funktionen, men jeg forsøger at bruge bygge node inde i indsatsen. Jeg har tænkt mig at gå ind og kopiere - og derefter indsætte build node-funktionen heroppe på toppen. På den måde forhåbentlig, der vil arbejde. Lad os give dette en anden gå. Nu er det hele kompilerer. Alt er godt. 

Men på dette punkt, har vi faktisk ikke kaldt vores Indsæt funktion. Vi skal bare vide, at det kompilerer, så lad os gå ind og sætte nogle opkald i. Lad os gøre det i vores vigtigste funktion. Her vi udkommenteret 5, 8 og 2, og så vi ikke wire dem op hernede. Lad os foretage nogle opkald for at indsætte, og lad os også bruge den samme slags ting, som vi brugte når vi gjorde disse printf opkald for at sikre, at alt fik indsat korrekt. Jeg har tænkt mig at kopiere og indsætte, og i stedet for indeholder vi vil gøre indsatsen. Og i stedet for 6, 10, og 1, vi kommer til at bruge 5, 8 og 2. Dette vil forhåbentlig indsætte 5, 8 og 2 ind i træet. Kompiler. Alt er godt. Nu vil vi faktisk køre vores program. 

Alt returneres falsk. Så har 5, 8 og 2 ikke gå, og det ser ud som indeholder ikke fandt dem heller. Hvad sker der? Lad os zoome ud. Det første problem var, at indsatsen syntes at returnere falsk, og det ser ud det er fordi vi forlod i vores tilbagevenden falsk opkald, og vi har faktisk aldrig returneres sandt. Vi kan sætte det op. Det andet problem er, nu, selv om vi gør - gemme dette, skal du afslutte dette, køre make igen, har det kompilere, derefter køre det - vi se, at noget andet er sket her. The 5, 8 og 2 blev fortsat aldrig fundet i træet. Så, hvad sker der? 

Lad os tage et kig på dette i koden. Lad os se om vi kan finde ud af dette. Vi starter med den forælder ikke er null. Vi sætter den aktuelle pointer svarende til roden pointer, og vi vil arbejde vores vej ned gennem træet. Hvis den aktuelle node ikke er nul, så ved vi, at vi kan bevæge os ned en lille smule. Vi sætter vores moderselskab pointer at være lig med den aktuelle pointer, kontrolleret værdien - hvis værdierne er de samme vi vendte tilbage falsk. Hvis værdierne er mindre vi flyttede til højre; ellers, vi flyttet til venstre. Så bygger vi en node. Jeg vil zoome ind en lille smule. Og her vil vi forsøge at wire værdierne op til at være den samme. Hvad sker der? Lad os se om evt Valgrind kan give os et praj. 

Jeg kan godt lide at bruge Valgrind bare fordi Valgrind virkelig hurtigt kører og fortæller dig, hvis der er nogen hukommelsesfejl. Når vi kører Valgrind på koden, som du kan se til højre here--Valgrind./binary_tree--and tryk enter. Du ser, at vi ikke har nogen hukommelse fejl, så det ligner alt er okay indtil videre. Vi har nogle memory leaks, som vi ved, fordi vi ikke er sker at befri nogen af ​​vores noder. Lad os prøve at køre GDB at se, hvad der rent faktisk sker. Vi laver gdb. / Binary_tree. Det startet op fint. Lad os sætte en break point på insert. Lad os køre. Det ser ud som vi faktisk aldrig kaldt insert. Det ligner problemet var bare, at når jeg skiftede ned her i main - alle disse printf opkald fra indeholder - Jeg faktisk aldrig skiftet disse ringe indsats. Nu lad os give det en chance. Lad os kompilere. Alle ser godt dér. Lad os nu prøve at køre det, se hvad der sker. Okay! Alt ser temmelig godt dér. 

Den sidste ting at tænke på er, er der nogen kant sager til denne indsats? Og det viser sig, at, ja, det ene kant sag, der er altid interessant at tænke på er, hvad der sker, hvis dit træ er tom, og du kalder denne insert funktion? Vil det virke? Nå, lad os give det en chance. - Binary_tree c. - Den måde, vi kommer til at teste dette er, vi kommer til at gå ned til vores vigtigste funktion, og i stedet for ledningsføring disse knudepunkter op som dette, vi bare vil kommentere ud hele ting, og i stedet for kabler op knudepunkterne os selv, Vi kan faktisk bare gå videre og slette alt dette. Vi vil gøre alt et opkald for at indsætte. Så lad os gøre - i stedet for 5, 8 og 2, vil vi indsætte 7, 3, og 9. Og så vil vi også ønsker at indsætte 6 samt. Gem. Afslut. Gør binært træ. Det hele kompilerer. Vi kan bare køre det som det er, og se hvad der sker, men det er også vil være virkelig vigtigt at sikre, at vi ikke har nogen hukommelse fejl, da dette er et af vores edge sager, vi kender til. 

Lad os sørge for, at det fungerer godt under Valgrind, som vi vil gøre ved bare at køre Valgrind. / binary_tree. Det ser ud til at vi faktisk har en fejl fra én sammenhæng - vi har denne segmentering fejl. Hvad er der sket? Valgrind faktisk fortæller os, hvor det er. Zoom ud en lille smule. Det ser ud som det sker i vores insert funktion, hvor vi har et ugyldigt læst af størrelse 4 ved insert, linie 60. Lad os gå tilbage og se, hvad der foregår her. Zoom ud virkelig hurtig. Jeg vil være sikker på, at det ikke går ud til kanten af ​​skærmen, så vi kan se alt. Træk, at der i en lille smule. Alright. Rul ned, og problemet er lige her. Hvad sker der, hvis vi får ned og vores nuværende node er allerede null, vores moderselskab node er null, så hvis vi ser op på toppen, lige her - hvis denne while-løkke faktisk aldrig udfører fordi vores nuværende værdi er null - vores rod er nul så cur er null - så vores moderselskab aldrig bliver sat til cur eller til en gyldig værdi, så vil forældrene også være null. Vi skal huske at tjekke for det med den tid, vi kommer herned, og vi begynder at få adgang til moderselskabets værdi. Så, hvad sker der? Tja, hvis moderselskabet er null - if (forælder == NULL) - så ved vi, at der må ikke være noget i træet. Vi skal forsøge at indsætte det ved roden. Det kan vi gøre ved blot at sætte rod lig med den nye node. Så på dette punkt, vi faktisk ikke ønsker at gå gennem disse andre ting. I stedet, lige her, kan vi gøre enten en else-if-else, eller vi kunne kombinere alt op her i en ellers, men her vil vi bare bruge andet og gøre det på den måde. Nu vil vi teste for at sikre, at vores moderselskab ikke er nul inden da faktisk forsøger at få adgang til sine marker. Dette vil hjælpe os til at undgå segmenteringsfejl. Så vi holde op, zoome ud, kompilere, løbe. 

Ingen fejl, men vi har stadig en masse memory leaks fordi vi ikke befri nogen af ​​vores noder. Men hvis vi går op her, og vi ser på vores udskrift, vi se, at, ja, ligner alle vores insertioner blev tilbage sand, hvilket er godt. Skærene er alle sande, og derefter de relevante indeholder opkald er også sandt. 

Godt arbejde! Det ser ud som vi med succes har skrevet insert. Det er alt vi har for denne uges Problem Set Specification. En sjov udfordring at tænke på er, hvordan du rent faktisk ville gå i og fri alle knuder i dette træ. Vi kan gøre en række forskellige måder, men jeg vil overlade det op til dig at eksperimentere, og som en sjov udfordring, så prøv og sørg for, at du kan sørge for at denne Valgrind rapporten returnerer ingen fejl og ingen utætheder. 

Held og lykke på denne uges Huffman kodning problem sæt, og vi vil se dig i næste uge! [CS50.TV]