[Powered by Google Translate] [Sectie 7] [minder comfortabel] [Nate Hardison] [Harvard University] [Dit is CS50.] [CS50.TV] 

Welkom bij hoofdstuk 7. Dankzij orkaan Sandy, plaats van een normale sectie deze week we doen dit walk-through, via de rubriek van vragen. Ik ga te volgen, samen met het probleem Set 6-specificatie, en gaan door alle van de vragen in de Een deel van de vragen sectie. Als er vragen zijn, plaats dan graag deze op CS50 te bespreken. 

Alright. Laten we beginnen. Op dit moment ben ik op zoek op pagina 3 van het probleem Set-specificatie. We gaan eerst beginnen te praten over binaire bomen aangezien die hebben veel van belang zijn voor problemen van deze week set - de Huffman codering Tree. Een van de eerste data structuren die we over hadden op CS50 was de array. Bedenk dat een array een reeks elementen - alle van hetzelfde type - naast elkaar in het geheugen opgeslagen. Als ik een integer array die ik kan trekken met behulp van deze boxen-nummers-integers stijl - Laten we zeggen dat ik 5 in het eerste vak, ik heb 7 in de tweede, dan heb ik 8, 10 en 20 in de uiteindelijke doos. Vergeet niet dat de twee echt goede dingen over deze array zijn dat we deze constante-time toegang tot een bepaald element hebben  in de array als we weten zijn index. Bijvoorbeeld, als ik wil het derde element in de array te grijpen - bij index 2 met behulp van onze zero-based indexeringssysteem - Ik letterlijk alleen maar een eenvoudige wiskundige berekening uit te voeren, hop die positie in het array, trek de 8 dat er wordt opgeslagen, en ik ben klaar om te gaan. 

Een van de slechte dingen over deze array - dat hebben we gesproken over toen bespraken we gelinkte lijsten - is dat als ik wil een element in te voegen in deze array, Ik ga te hebben om wat verschuiven rond te doen. Bijvoorbeeld, deze array hier is in de gesorteerde volgorde - in oplopende volgorde gesorteerd - 5 dan 7, dan 8, dan 10, en 20 - maar als ik wil de nummer 9 in te voegen in deze array, Ik zal moeten bepaalde elementen verschuiven om ruimte te maken. We kunnen putten dit uit hier. Ik zal moeten de 5, de 7 verplaatsen en de 8; maak een gat waar ik zet de 9, en de 10 en de 20 kan naar rechts van de 9. Dit is een soort van een pijn omdat in het worst-case scenario - als we hoeven voegen ofwel aan het begin of aan het einde van de array, afhankelijk van hoe we het verschuiven - we kunnen eindigen met alle elementen verschuiven dat we op dit moment te slaan in de array. 

Dus, wat was de manier om dit? De manier om dit was om naar onze linked-lists methode waar - in plaats van het opslaan van de elementen 5, 7, 8, 10 en 20 alle naast elkaar in het geheugen - wat we in plaats daarvan deed was ze opslaan soort waar we wilden op te slaan in deze linked-lists knooppunten die ik tekenen hier, een soort van ad hoc. En dan gaan we verbonden aan elkaar met behulp van deze volgende tips. Ik kan een pointer van 5 tot de 7, een pointer van de 7 de 8, een pointer van de 8 aan de 10, en tenslotte een pointer van de 10 tot de 20, en dan een null pointer op de 20 geeft aan dat er niets meer over. De trade-off die we hier hebben is dat nu als we willen de nummer 9 in te voegen in onze gesorteerde lijst, alles wat we moeten doen is het creëren van een nieuw knooppunt met 9, draad het op te wijzen naar de juiste plaats, en dan her-bedrading de 8 naar beneden wijzen op de 9. Dat is behoorlijk snel, in de veronderstelling weten we precies waar we willen de 9 in te voegen. Maar de trade-off in ruil voor dit is dat we nu hebben de constante-time toegang verloren tot een bepaald element in onze datastructuur. Bijvoorbeeld, als ik wil het vierde element vinden in deze gelinkte lijst, Ik ga moeten beginnen bij het begin van de lijst en werk mijn weg door het tellen van knooppunt-voor-knooppunt tot ik de vierde. 

Met het oog op een betere toegang prestaties dan een gekoppelde lijst te krijgen - maar behouden ook enkele van de voordelen die we hadden in termen van het inbrengen-tijd van een gekoppelde lijst - een binaire boom is gaat nodig hebben om een ​​beetje meer geheugen te gebruiken. In het bijzonder, in plaats van alleen het hebben van een aanwijzer in een binaire boom node - zoals de linked-lists knoop doet - we gaan een tweede pointer toe te voegen aan de binaire boom knooppunt. In plaats van alleen het hebben van een pointer naar het volgende element, we gaan een pointer naar een linker kind en een recht kind te hebben. 

Laten we een tekening maken om te zien hoe dat er daadwerkelijk uitziet. Nogmaals, ik ga deze dozen en pijlen te gebruiken. Een binaire boom knooppunt zal beginnen met slechts een simpele doos. Het gaat om een ​​ruimte voor de waarde hebben, en dan is het ook gaan om een ​​ruimte voor het linker kind en het recht kind te hebben. Ik ga hier benoem ze. We gaan naar links kind hebben, en dan gaan we naar de juiste kind. Er zijn veel verschillende manieren om dit te doen. Soms voor ruimte en gemak, Ik zal echt trek het zoals ik hier doe op de bodem waar ik ga om de waarde hebben aan de top, en dan de juiste kind op de bottom-rechts, en de linker kind op de linksonder. Terug te gaan naar deze top diagram, hebben we de waarde aan de top, dan hebben we de linker-kind pointer, en dan hebben wij het recht-kind pointer. 

In het Probleem Set specificatie, we praten over het tekenen van een knooppunt dat een waarde 7 heeft, en dan van links-kind pointer die nul is, en een rechter-kind pointer die is null. We kunnen het kapitaal NULL ofwel schrijven in de ruimte voor zowel de linker kind en het recht kind, of we kunnen trekken deze schuine streep door elk van de dozen te geven dat null is. Ik ga doen dat alleen maar omdat dat is eenvoudiger. Wat u hier ziet zijn twee manieren om diagrammen een zeer eenvoudige binaire boom knooppunt waar we de waarde 7 en null kind pointers. 

Het tweede deel van onze specificatie vertelt over hoe met gelinkte lijsten - vergeet niet, we hadden alleen vast te houden aan het eerste element in een lijst om de hele lijst herinneren - en eveneens, met een binaire boom, we hebben alleen vast te houden aan een pointer naar de boom om de controle over het gehele data structuur te handhaven. Deze speciale element van de boom heet de root node van de boom. Bijvoorbeeld, indien een knooppunt - dit knooppunt met de waarde 7 met null links-en rechts-kind pointers - waren de enige waarde in onze boom, dan zou dit onze root node zijn. Het is het begin van onze boom. We kunnen dit een beetje duidelijker als we eenmaal beginnen met het toevoegen van meer knooppunten aan onze boom. Laat me trek een nieuwe pagina. 

Nu gaan we een boom die 7 heeft aan de wortel te trekken, en 3 binnenzijde van de linker kind, en 9 binnenkant van de rechter kind. Nogmaals, dit is vrij eenvoudig. We hebben 7 hebt, trek een knooppunt voor de 3, een knooppunt voor 9, en ik ga naar links-kind wijzer van 7 om te wijzen op het knooppunt met 3 in te stellen, en het rechter kind pointer van het knooppunt met 7 tot het knooppunt met 9. Nu, sinds 3 en 9 geen kinderen, we gaan al hun kind pointers ingesteld op null zijn. Hier, de wortel van de boom komt overeen met het knooppunt met het getal 7. U kunt zien dat als alles wat we hebben is een pointer naar die root node, kunnen we dan wandelen door onze boom en toegang tot zowel onderliggende knooppunten - zowel 3 en 9. Geen behoefte om pointers te behouden om elk knooppunt op de boom. Alright. Nu gaan we naar een ander knooppunt toe te voegen aan dit schema. We gaan een knooppunt met 6 toe te voegen, en we gaan dit toe te voegen als het recht kind van de node met 3. Om dat te doen, ga ik dat null-pointer te wissen in de 3-knooppunt en bedrading van het op te wijzen op het knooppunt met 6. Alright. 

Op dit punt, laten we gaan over een beetje van terminologie. Om te beginnen, de reden dat dit wordt een binaire boom name is dat het twee kind pointers heeft. Er zijn andere soorten van bomen die meer kind pointers hebben. In het bijzonder, je hebt een 'proberen' in Probleem Set 5. U zult dat merken in dat proberen, je had 27 verschillende verwijzingen naar verschillende kinderen - een voor elk van de 26 letters in het alfabet Engels, en dan de 27e voor de apostrof - dus, dat is vergelijkbaar met een type boom. Maar hier, omdat het de binaire, we hebben maar twee kinderen pointers. 

In aanvulling op deze root node waar we over spraken, we hebben ook al uitput in deze term 'kind'. Wat betekent het voor het ene knooppunt naar een kind van een ander knooppunt te zijn? Het betekent letterlijk dat een kind knooppunt is een kind van een ander knooppunt indien die andere node heeft een van de onderliggende pointers ingesteld om te wijzen op dat knooppunt. Om dit in meer concrete termen, Als 3 aangeduid wordt door een van de onderliggende wijzers van 7 dan 3 is een kind van 7. Als we te achterhalen wat de kinderen van 7 zijn - goed, zien we dat 7 een pointer naar 3 en een pointer naar 9 heeft, zo 9 en 3 zijn de kinderen van 7. Negen heeft geen kinderen, omdat de kinderen pointers zijn null, en 3 slechts een kind 6. Zes heeft ook geen kinderen, omdat haar beide pointers zijn null, waar we op dit moment te trekken. 

Daarnaast hebben we ook praten over de ouders van een bepaald knooppunt, en dit is, zoals je zou verwachten, de keerzijde van dit kind beschrijving. Elk knooppunt heeft slechts een ouder - in plaats van twee zoals je zou verwachten met mensen. Bijvoorbeeld de ouder van 3 7. De ouder van 9 is 7 en de ouder van 6 3. Niet veel aan. We hebben ook wat te praten over grootouders en kleinkinderen, en meer in het algemeen praten we over de voorouders en afstammelingen van een bepaald knooppunt. De stamvader van een knoop - of voorouders, beter gezegd, van een knooppunt - zijn alle knooppunten die liggen op het pad van de wortel naar dat knooppunt. Bijvoorbeeld, als ik kijk naar het knooppunt 6, dan de voorouders zullen zowel 3 en 7. De voorouders van 9, bijvoorbeeld, zijn - als ik kijk naar het knooppunt 9 - dan is de voorouder van 9 ligt op slechts 7. En afstammelingen zijn precies het omgekeerde. Als ik wil kijken naar alle van de nakomelingen van 7, dan moet ik om te kijken naar alle knooppunten eronder. Dus, ik heb 3, 9 en 6 al als nakomelingen van 7. 

De laatste term die we praten over is deze notie van het zijn een broer of zus. Broers en zussen - soort van volgende mee op deze familie-termen - zijn knopen die op hetzelfde niveau in de boom. Dus, 3 en 9 siblings omdat zij op hetzelfde niveau in de boom. Ze hebben allebei dezelfde ouder, 7. De 6 heeft geen broers en zussen omdat 9 heeft geen kinderen. En 7 heeft geen broers en zussen, want het is de wortel van onze boom, en er is alleen maar 1 root. 7 tot siblings hebben zou er een knooppunt boven 7 zijn. Er zou een ouder van 7, waarbij 7 niet langer de wortel van de boom. Dan is dat nieuwe moedermaatschappij van 7 zou ook een kind te krijgen, en dat kind zou dan het broertje van 7. 

Alright. Verder. Wanneer we onze bespreking van binaire bomen begonnen, hebben we gesproken over hoe we zouden gaan om ze te gebruiken om krijgen een voordeel ten opzichte van beide arrays en gelinkte lijsten. En de manier waarop we dat doen is met deze bestelling eigenschap. We zeggen dat een binaire boom wordt verwezen, volgens de specificatie, indien voor iedere knoop in de boom, al zijn nakomelingen links - de linker kind en alle afstammelingen van de linker kind - hebben minder waarden en alle knooppunten rechts - het recht kind en alle nakomelingen het recht kind - hebben nodes groter is dan de waarde van het huidige knooppunt dat we kijken. Gewoon voor de eenvoud, gaan we ervan uit dat er helemaal geen dubbele knopen in onze boom. Bijvoorbeeld, in deze boom we niet van plan om de zaak te behandelen waar we de waarde 7 aan de wortel  en dan hebben we ook de waarde 7 elders in de boom. In dit geval, zult u merken dat deze boom inderdaad besteld. Wij hebben de waarde 7 bij de wortel. Alles links van 7 - als ik hier ongedaan maken van deze kleine merken - alles links van 7 - de 3 en de 6 - deze waarden liggen beide op minder dan 7, en alles naar rechts - die net is dit 9 - groter is dan 7. 

Dit is niet het enige geordende boom die deze waarden maar laten we trekken nog een paar van hen. Er is eigenlijk een hele hoop manieren waarop we dit kunnen doen. Ik ga een vlugschrift te gebruiken alleen maar om het simpel te houden, waar - in plaats van het tekenen uit het hele dozen-en-pijlen - Ik ga gewoon naar de getallen tekenen en pijlen verbinden ze toe te voegen. Om te beginnen, we zullen gewoon weer schrijven onze oorspronkelijke boom waar we 7, en dan een 3, en vervolgens 3 similisteen naar rechts om de 6, en 7 had het recht kind dat was 9. Alright. Wat is een andere manier dat we deze boom achterlaten? In plaats van 3 de linker kind van 7, we ook de 6 als linker kind van 7, en 3 de linker kind van de 6. Dat zou er als volgt uitzien boom hier, waar ik heb 7, dan 6 dan 3 en een 9 rechts. We hebben evenmin tot 7 als het root node. We kunnen ook hebben 6 als onze root node. Hoe zou dat er uit zien? Als we dit besteld pand te behouden, alles links van de 6 moet minder dan. Er is maar een mogelijkheid, en dat is 3. Maar dan als het recht kind van 6 hebben we twee mogelijkheden. Ten eerste kunnen we de 7 en de 9, of we kunnen tekenen - alsof ik op het punt om hier te doen - waar we de 9 hebben de rechter kind van de 6, en de 7 als het linker kind van de 9. 

Nu, 7 en 6 zijn niet de enige mogelijke waarden voor de root. We konden ook 3 worden aan de wortel. Wat gebeurt er als 3 is aan de wortel? Hier liggen de zaken een beetje interessant. Drie heeft geen waarden die minder dan, zodat dat hele linkerkant van de boom wordt gewoon naar null zijn. Er zal niet er iets. Aan de rechterkant, konden we een lijst dingen in oplopende volgorde. We zouden 3, dan 6, dan 7, dan 9. Of kunnen we doen 3, dan 6, dan 9, vervolgens op 7. Of kunnen we doen op 3 en 7, dan 6, dan 9. Of, 3, 7 - eigenlijk geen, we kunnen niet meer doen een 7. Dat is onze een ding daar. Dat kunnen we doen 9, en vervolgens van de 9 die we kunnen doen 6 en dan op 7. Of kunnen we doen 3, dan 9, dan 7, en vervolgens 6. 

Een ding om uw aandacht te vestigen op hier is dat deze bomen zijn een beetje raar uitzien. In het bijzonder, als we kijken naar de 4 bomen aan de rechterkant - Ik zal omcirkelen ze, hier - deze bomen lijken bijna net zoals een gekoppelde lijst. Elk knooppunt heeft slechts een kind, en we hebben geen van deze boomstructuur die we bijvoorbeeld  in dit ene eenzame boom hier in de linkerbenedenhoek. Deze bomen zijn eigenlijk genoemd ontaarden binaire bomen, en we praten over deze meer in de toekomst - vooral als je gaat naar andere informatica cursussen te volgen. Deze bomen zijn gedegenereerd. Ze zijn niet erg nuttig, want, inderdaad, deze structuur leent zich  de tijden vergelijkbaar met die van een gekoppelde lijst opzoeken. We krijgen niet om te profiteren van de extra geheugen - deze extra pointer - omdat onze structuur slecht zijn op deze manier. In plaats van te gaan en trekken uit de binaire bomen die 9 hebben aan de wortel, dat is de laatste geval is dat we zouden hebben, We zijn in plaats daarvan, op dit punt, gaat een beetje over praten andere term die we gebruiken als we het over bomen, die wordt genoemd de hoogte. 

De hoogte van een boom is de afstand van de basis naar de meest nabije knooppunt, of beter gezegd het aantal hops dat je zou moeten maken om starten vanaf de wortel en dan eindigen op de meest verre node in de boom. Als we kijken naar een aantal van deze bomen die we hier getekend, kunnen we dat als we deze boom in de linker hoek en we beginnen op de 3, dan moeten we een hop om de 6 een tweede stap om de 7 te maken, en een derde hop om naar de 9. Dus de hoogte van de boom is 3. Dat kunnen we doen dezelfde oefening voor de andere bomen geschetst met deze groene, en we zien dat de hoogte van al deze bomen ook inderdaad 3. Dat is een deel van wat maakt ontaarde hen - dat de hoogte slechts een minder dan het aantal knooppunten in de gehele boom. Als we kijken naar deze andere boom is omringd met rode, anderzijds, zien we dat de meest afgelegen leaf nodes zijn de 6 en de 9 - de bladeren zijn die knopen die geen kinderen hebben. Dus, om om van het hoofdknooppunt hetzij de 6 of 9, moeten we een hop te maken om naar de 7 en vervolgens een tweede hop om naar de 9, en ook, om slechts een tweede hop uit de 7 naar de 6. Dus de hoogte van de boom hier slechts 2. U kunt terug gaan en doen dat voor alle andere bomen die we eerder besproken beginnen met de 7 en 6, en je zult zien dat de hoogte van al die bomen ook 2 is. 

De reden dat we hebben het over besteld binaire bomen en waarom ze is cool, want je kunt er doorheen zoeken in een zeer gelijkaardige manier aan het zoeken over een gesorteerde array. Dit is waar we praten over het krijgen van die verbeterde lookup tijd opzichte van de eenvoudige gekoppelde lijst. Met een gekoppelde lijst - als u een bepaald element te vinden - je bent in het beste geval gaan om een ​​soort van lineaire zoekopdracht waar je start aan het begin van een lijst en hop een-voor-een - een knooppunt van een knooppunt - door de hele lijst totdat u vinden wat u zoekt. Overwegende dat, als u een binaire boom die is opgeslagen in deze mooie vorm, kan je eigenlijk meer van een binair zoeken aan de hand waar u verdeel en heers doorzoeken en de passende helft van de boom bij elke stap. Laten we eens kijken hoe dat werkt. 

Als we - weer terug te gaan naar onze oorspronkelijke boom - we beginnen op 7 hebben we 3 links, 9 rechts en onder de 3 hebben we de 6. Als we willen zoeken naar de nummer 6 in deze boom, zouden we beginnen bij de wortel. We zouden vergelijken de waarde die we zoeken, laten we zeggen 6, om de waarde opgeslagen in het knooppunt dat we op dit moment op zoek bent naar, 7, 6 vinden dat inderdaad minder dan 7, dus we naar links. Als de waarde van 6 hoger was dan 7, zou plaats hebben we naar rechts. Omdat we weten dat - als gevolg van de structuur van onze bestelde binaire boom - alle waarden minder dan 7 zullen worden opgeslagen links van 7, er is geen noodzaak om zelfs moeite om te kijken door de rechterkant van de boom. Zodra we naar links en we zijn nu op het knooppunt met 3, we dat kunnen doen dezelfde vergelijking weer waar we de 3 en de 6. En vinden we dat, terwijl 6 - de waarde die we zoeken - groter is dan 3, kunnen we naar de rechterzijde van het knooppunt met 3. Er is geen links hier, dus we konden hebben genegeerd dat. Maar we weten alleen dat, want we kijken naar de boom zelf, en we zien dat de boom geen kinderen heeft. 

Het is ook vrij eenvoudig op te zoeken 6 in deze boom als we doen het onszelf als mens, maar laten we mechanisch volgen dit proces als een computer zou doen om echt te begrijpen het algoritme. Op dit punt zijn we nu op zoek naar een knooppunt dat 6 bevat, en we zijn op zoek naar de waarde 6, ja, inderdaad, we hebben gevonden de juiste node. We vonden dat de waarde 6 in onze boom, en we kunnen onze zoektocht stoppen. Op dit punt, afhankelijk van wat er gaande is, kunnen we zeggen, ja, we hebben de waarde 6 gevonden, bestaat het in onze boom. Of, als we zijn van plan om een ​​knooppunt te voegen of iets doen, kunnen we dat doen op dit punt. 

Laten we een paar lookups alleen maar om zien hoe dit werkt. Laten we eens kijken wat er gebeurt als we zouden proberen en kijken de waarde 10. Als we kijken op de waarde 10, dan zouden we beginnen bij de wortel. We willen zien dat 10 groter is dan 7, dus we zouden naar rechts te verplaatsen. We zouden naar de 9 en 9 vergelijkt de 10 en 9 zien dat inderdaad minder dan 10. Dus nogmaals, we zouden proberen om naar rechts te verplaatsen. Maar op dit punt, zouden we merken dat we op een null-knooppunt. Er is niets daar. Er is niets waar de 10 zou moeten zijn. Dit is waar we kunnen mislukking rapporteren - dat er inderdaad geen 10 in de boom. En tot slot, laten we gaan door de zaak waar we proberen op te zoeken 1 in de boom. Dit is vergelijkbaar met wat er gebeurt als we kijken met 10, behalve in plaats van naar rechts, we gaan naar links. We beginnen bij de 7 en zie dat 1 minder dan 7, dus we gaan naar links. We de 3 en ziet dat 1 minder dan 3, dus opnieuw proberen we naar links. Op dit punt hebben we een null knooppunt, zodat we weer kunnen melden falen. 

Als u meer wilt leren over binaire bomen, Er zijn een hele hoop leuke problemen die je kunt doen met hen. Ik stel voor het beoefenen van de tekening uit deze diagrammen een-voor-een en na door alle verschillende stappen, omdat dit zal komen in superhandige niet alleen wanneer je doet de Huffman codering probleem set maar ook in de toekomst cursussen - gewoon leren hoe te trekken uit deze gegevens structuren en nadenken over de problemen met pen en papier of, in dit geval, iPad en stylus. 

Op dit punt echter, gaan we verder met een aantal codering praktijk doen en eigenlijk spelen met deze binaire bomen en zien. Ik ga om terug te schakelen naar mijn computer. Voor dit deel van het hoofdstuk, in plaats van het gebruik van CS50 Run of CS50 Spaces, Ik ga het apparaat te gebruiken. 

Na samen met het probleem Set specificatie Ik zie dat ik moet openen van het apparaat, ga naar mijn Dropbox-map, maak een map met de naam hoofdstuk 7, en maak vervolgens een bestand met de naam binary_tree.c. Daar gaan we. Ik heb het apparaat al open. Ik ga trekken van een terminal. Ik ga naar de Dropbox-map, maak een map met de naam section7, en zie het is helemaal leeg. Nu ga ik het openstellen van binary_tree.c. Alright. Hier gaan we - leeg bestand. 

Laten we terug gaan naar de specificatie. De specificatie vraagt ​​om een ​​nieuw type definitie voor een binaire boom knooppunt met int-waarden - net als de waarden die we haalde in onze diagrammen voor. We gaan gebruik maken van deze boilerplate typedef dat we hier gedaan dat je moet herkennen uit Probleem Set 5 - als je dat deed de hash table weg van het veroveren van de speller programma. Je moet ook herkennen van sectie van vorige week waar hadden we het over gelinkte lijsten. We hebben dit typedef van een struct knoop, en we hebben gezien deze struct knoop deze naam van struct knoop vooraf zodat wij kunnen dan verwijzen naar het sinds we willen struct knoop pointers hebben als onderdeel van onze struct, maar we hebben dan omringd dit - of liever ingesloten dit - in een typedef zodat later in de code kunnen we verwijzen naar deze struct als slechts een knooppunt in plaats van een struct knoop. 

Dit gaat erg vergelijkbaar met die van de enkelvoudig-gelinkte lijst definitie die we zagen vorige week. Om dit te doen, laten we beginnen met het schrijven van de standaardtekst. We weten dat we naar een geheel getal zijn, dus zetten we in int waarde, en dan in plaats van het hebben van slechts een pointer naar het volgende element - zoals we deden met enkelvoudig gelinkte lijsten - we gaan links en rechts kind pointers hebben. Dat is vrij eenvoudig ook - struct knoop * linker kind; en struct knoop * rechts kind;. Cool. Dat ziet eruit als een redelijk goede start. Laten we terug gaan naar de specificatie. 

Nu moeten we een globale knooppunt * variabele te declareren voor de wortel van een boom. We gaan om dit mondiale net zoals we voor het eerst wijzer gemaakt in onze gelinkte lijst ook mondiaal. Dit was zodat de functies die we schrijven we niet moeten blijven passeren rond deze wortel - hoewel we zullen zien dat als je wilt recursief schrijven van deze functies, het zou beter zijn om zelfs het uitdelen als globale in de eerste plaats en in plaats daarvan lokaal initialiseren in uw belangrijkste functie. Maar, we wereldwijd doen het om te beginnen. Nogmaals, we geven een paar ruimtes, en ik ga naar een knooppunt * wortel te verklaren. Gewoon om ervoor te zorgen dat ik niet laat dit niet-geïnitialiseerd, ik ga het gelijk aan null. Nu, in de belangrijkste functie - die we zullen heel snel schrijven hier - int main (int argc, const char * argv []) - en ik ga beginnen aangeven mijn argv array als const gewoon zo dat ik weet dat deze argumenten zijn argumenten die ik waarschijnlijk niet wilt wijzigen. Als ik wil ze te wijzigen moet ik waarschijnlijk het maken van kopieën van hen. Je ziet dit veel in de code. Het is fijn een van beide manier. Het is fijn om het te laten zoals - de const weglaten als je wilt. Ik meestal zet het in gewoon zo dat ik me te herinneren  dat ik waarschijnlijk niet willen deze argumenten aan te passen. 

Zoals altijd, ik ga deze return 0 lijn aan het eind van de belangrijkste op te nemen. Hier zal ik initialiseren mijn root node. Zoals het er nu op dit moment, ik heb een pointer die is ingesteld op null, dus het is te wijzen op niets. Om daadwerkelijk beginnen met de bouw van het knooppunt, Ik moet eerst naar het geheugen voor het toewijzen. Ik ga dat doen door het maken van het geheugen op de heap malloc gebruikt. Ik ga wortel gelijk is aan het resultaat van malloc in te stellen, en ik ga de sizeof operator om de grootte van een knoop berekenen. De reden dat ik sizeof knooppunt gebruiken in plaats van, laten we zeggen, het doen van zoiets als dit - malloc (4 + 4 +4) of malloc 12 - is omdat ik wil dat mijn code om zo compatibel mogelijk. Ik wil in staat zijn om dit. C bestand te nemen, compileren op het apparaat, en vervolgens compileren het op mijn 64-bit Mac - of op een heel andere architectuur - en ik wil dit allemaal op hetzelfde werken. 

Als ik het maken van veronderstellingen over de omvang van de variabelen - de grootte van een int of de grootte van een pointer - dan ben ik ook het maken van veronderstellingen over de soorten architecturen waarop mijn code met succes kan compileren wanneer deze wordt uitgevoerd. Altijd sizeof tegenover handmatig optellen van de struct velden. De andere reden is dat er mogelijk ook padding dat de compiler zet in de struct. Zelfs alleen het optellen van de afzonderlijke velden is niet iets dat je normaal gesproken wilt doen, zo, verwijdert u die lijn. Nu, om echt te initialiseren deze root node, Ik ga te hebben om aan te sluiten in de waarden voor elk van de verschillende gebieden. Bijvoorbeeld, voor waarde ik weet dat ik wilt initialiseren tot en met 7, en voor nu ga ik stel de linker-kind te zijn null en het recht kind om ook null zijn. Geweldig! Dat hebben we gedaan een deel van de spec. 

De specificatie op de bodem van pagina 3 vraagt ​​me om drie meer knooppunten - een met 3, een met 6 en een met 9 - en dan bedraden zodat het lijkt precies op onze boomdiagram dat we aan het praten waren over eerder. Laten we dat doen vrij snel hier. Je zult heel snel zien dat ik ga om te beginnen met het schrijven van een heleboel dubbele code. Ik ga een knooppunt * maken en ik ga noemen drie. Ik ga je die kunt gelijk aan malloc (sizeof (node)). Ik ga drie-> waarde in te stellen = 3. Drie -> left_child = NULL; drie -> rechts _child = NULL; ook. Dat ziet er redelijk vergelijkbaar met het initialiseren van de wortel, en dat is precies wat Ik ga doen als ik begin het initialiseren van 6 en 9 ook. Ik doe dat heel snel hier - in feite, ik ga een beetje kopiëren en plakken te doen, en zorg ervoor dat ik - goed.  Nu, ik heb gekopieerd en ik kan doorgaan en stel deze gelijk aan 6. Je kunt zien dat dit een tijdje duurt en is niet super-efficiënt. In slechts een klein beetje, dan schrijven we een functie die dit voor ons zal doen. Ik wil dit vervangen door een 9, vervang dat met een 6. 

Nu hebben we al onze nodes aangemaakt en geïnitialiseerd. We hebben onze wortels te stellen gelijk aan 7, of met de waarde 7, onze node met 3, onze knooppunt met 6, en onze node met 9. Op dit punt, alles wat we hoeven te doen is draad alles op. De reden dat ik geïnitialiseerd alle pointers op null is gewoon zo dat ik er zeker van dat Ik heb geen geïnitialiseerde pointers daar per ongeluk. En ook omdat op dit moment heb ik alleen daadwerkelijk de knooppunten met elkaar te verbinden - aan degenen die ze eigenlijk hebt met - Ik heb geen te gaan door en maken ervoor dat alle nullen zijn daar op de juiste plaats. 

Beginnend bij de wortel, weet ik dat de wortel van de linker kind 3. Ik weet dat de wortel van het recht kind is 9. Daarna is de enige andere kind dat ik nog heb te maken over gelijk kind 3, die is 6. Op dit punt, het ziet er allemaal erg goed. We verwijderen een aantal van deze lijnen. Nu is alles ziet er goed uit. Laten we terug gaan naar onze specificatie en zien wat we moeten gaan doen. 

Op dit punt moeten we schrijven de naam van een functie 'bevat' met een prototype van 'bool bevat (int waarde)'. En deze bevat functie gaat return true  als de boom door onze wereldwijde wortel variabele wees  bevat de waarde die in de functie en anders false. Laten we verder gaan en dat doen. Dit gaat precies zoals de lookup die we deden met de hand op de iPad gewoon een beetje geleden. Laten we weer terug in te zoomen een beetje en omhoog. We gaan deze functie te zetten recht boven onze belangrijkste functie zodat we niet om elke vorm van prototyping doen. Dus, bool bevat (int waarde). Daar gaan we dan. Daar is onze standaardtekst verklaring. Gewoon om ervoor te zorgen dat dit zal compileren, Ik ga om verder te gaan en stel het gewoon gelijk aan return false. Op dit moment deze functie gewoon niet alles doen en altijd melden dat de waarde die we zoeken is niet in de boom. 

Op dit punt, is het waarschijnlijk een goed idee - want we hebben geschreven een hele hoop code en we hebben het niet eens geprobeerd te testen nog - om ervoor te zorgen dat het allemaal compileert. Er zijn een paar dingen die we moeten doen om ervoor te zorgen dat dit ook daadwerkelijk zal compileren. Ten eerste, kijken of we al gebruik van alle functies in een bibliotheken die we nog niet hebben opgenomen. De functies die we tot nu toe gebruikt zijn malloc, en dan hebben we ook gebruik gemaakt van dit type - deze niet-standaard type genaamd 'bool' - die is opgenomen in de standaard bool header-bestand. We zijn zeker willen standaard bool.h voor de bool type zijn, en we willen ook # include standaard lib.h voor de standaard bibliotheken dat onder meer malloc, en vrij, en dat allemaal. Dus, uitzoomen, we gaan om te stoppen. Laten we proberen ervoor te zorgen dat dit ook daadwerkelijk het compileren deed. We zien dat het geval is, dus we zijn op de goede weg. 

Laten we weer open binary_tree.c. Het compileert. Laten we naar beneden gaan en ervoor te zorgen dat we een aantal gesprekken te voegen aan onze Bevat functie - alleen maar om ervoor te zorgen dat dat is allemaal goed en wel. Bijvoorbeeld, wanneer we een aantal lookups deden in onze boom eerder, hebben we geprobeerd op te zoeken van de waarden 6, 10, en 1, en we wisten dat 6 was in de boom, 10 was niet in de boom, en 1 was niet in de boom niet. Laten we gebruik maken van deze monster oproepen als een manier om erachter te komen of onze Bevat functie werkt. Om dat te doen, ik ga naar de printf functie te gebruiken, en we gaan voor het afdrukken van het resultaat van de oproep tot bevat. Ik ga in een string "bevat (% d) = omdat  we gaan om aan te sluiten in de waarde die we gaan op zoek naar, en =% s \ n ", en gebruik dat als onze format string. We gaan gewoon om te zien - letterlijk uit te printen op het scherm - wat lijkt op een functie-aanroep. Dit is niet echt de functie-aanroep.  Dit is slechts een string ontworpen om eruit als een functie aanroep. 

Nu gaan we aan te sluiten op de waarden. We gaan bevat proberen op 6, en wat gaan we hier doen is gebruik dat ternaire operator. Laten we eens kijken - bevat 6 - ja, nu ben ik die 6, en indien bevat 6 waar is, de string die we gaan naar de% s karakter gaat naar de string "echte" te zijn. Laten we schuiven dan een beetje. Buiten dat, we willen versturen van de string "false" als bevat 6 false retourneert. Dit is een beetje goofy uitziende, maar ik denk dat ik net zo goed illustreren wat de ternaire operator lijkt omdat we nog niet hebt gezien voor een tijdje. Dit zal een leuke, handige manier om erachter te komen of onze Bevat functie werkt wel. Ik ga terug te bladeren naar links, en ik ga om te kopiëren en deze lijn plak een paar keer. Veranderde sommige van deze waarden rond, dus dit zal worden 1, en dit zal worden 10. 

Op dit punt hebben we een mooi Bevat functie. We hebben een aantal tests, en we zullen zien of dit allemaal werkt. Op dit punt hebben we geschreven wat meer code. Tijd om te stoppen uit en zorg ervoor dat alles nog compileert. Ga uit, en nu laten we proberen het maken van binaire boom weer. Nou, het lijkt erop dat we hebben een fout, En we hebben dit expliciet te verklaren de bibliotheek functie printf. Het lijkt erop dat we moeten gaan en # include standardio.h. En met dat, indien alles samen te stellen. We zijn allemaal goed. Laten we nu eens proberen het uitvoeren van binaire boom en zien wat er gebeurt. Hier zijn we dan,. / Binary_tree, en we zien dat, als we verwacht hadden - omdat we nog niet geïmplementeerd bevat nog, of beter gezegd, hebben we gewoon in return false - zien we dat het gewoon valse terugkeer voor hen allen, dus dat is alle werkende voor het grootste deel vrij goed. 

Laten we terug gaan in een daadwerkelijke uitvoering bevat op dit punt. Ik ga naar beneden scrollen, in te zoomen, en - vergeet niet dat het algoritme dat we gebruikten was dat we begonnen op de root node en dan bij elk knooppunt dat we tegenkomen, we doen een vergelijking, en op basis van die vergelijking we ofwel naar links kind of rechts kind. Dit gaat erg lijken op de binaire zoekcode die we al eerder schreef in de term. Als we beginnen, we weten dat we willen vasthouden aan de huidige node dat we kijken naar, en het huidige knooppunt zal worden geïnitialiseerd naar de root node. En nu gaan we om door te gaan door middel van de boom, en vergeet niet dat onze stoppen voorwaarde -  als we daadwerkelijk gewerkt door het voorbeeld met de hand - was toen kwamen we een null knooppunt, niet toen we keken naar een null-kind, maar wanneer we daadwerkelijk verplaatst naar een knoop in de boom en vond dat we op een null-knooppunt. We gaan herhalen totdat huidig ​​is niet gelijk aan null. En wat gaan we doen? We gaan om te testen of (huidig ​​-> waarde == waarde), dan weten we dat we eigenlijk hebben het knooppunt dat we zoeken gevonden. Dus hier kunnen we return true. Anders willen we zien of de waarde kleiner is dan de waarde. Als de huidige knooppunt lager is dan de waarde die we zoeken, we gaan naar rechts te verplaatsen. Dus, huidig ​​= huidig ​​-> right_child, en anders gaan we naar links te verplaatsen. huidig ​​= huidig ​​-> left_child;. Vrij eenvoudig. 

Misschien herken je de lus die ziet er zeer vergelijkbaar met deze van binair zoeken eerder in de term, behalve dan hebben we te maken hadden met een laag, midden en hoog. Hier, we hoeven alleen maar te kijken naar een actuele waarde, dus het is leuk en eenvoudig. Laten we ervoor zorgen dat deze code werkt. Ten eerste, zorg ervoor dat het compileert. Het lijkt erop dat het doet. Laten we proberen het runnen van het. En inderdaad, het drukt alles wat we verwacht hadden. Het vindt 6 in de boom, niet vinden 10, omdat 10 niet in de boom, en ook niet vinden 1 omdat 1 is ook niet in de boom. Cool stuff. 

Alright. Laten we terug gaan naar onze specificatie en te zien wat de toekomst biedt. Nu wil het wat meer nodes toe te voegen aan onze boom. Het wil 5, 2, en 8 toe te voegen en te zorgen dat onze code bevat te maken nog steeds werkt zoals verwacht. Laten we dat doen. Op dit punt, dan doet dat irritante kopiëren en plakken weer, laten we een functie schrijven om daadwerkelijk een knooppunt. Als we naar beneden scrollen helemaal naar hoofd, zien we dat we al dit doen zeer vergelijkbaar code over en weer iedere keer dat we willen een knooppunt te creëren. 

We beginnen met een functie die een node ook daadwerkelijk te bouwen voor ons en terug te sturen. Ik ga noemen build_node. Ik ga een knooppunt te bouwen met een bepaalde waarde. Zoom in hier. Het eerste wat ik ga doen is eigenlijk ruimte scheppen voor het knooppunt op de heap. Dus, knoop * n = malloc (sizeof (node)); n -> waarde = waarde; en dan hier, ik ben gewoon gaan alle van de velden te initialiseren te zijn de juiste waarden. En helemaal aan het eind, zullen we terug onze node. Alright. Een ding om op te merken is dat deze functie hier gaat een pointer terug te keren naar het geheugen dat is heap-toegewezen. Wat is er leuk aan is, is dat deze knoop nu - we moeten het verklaren op de heap, want als we verklaard dat op de stapel zouden we niet in staat zijn om het te doen in deze functie als deze. Dat geheugen zou gaan van ruimte en zou zijn ongeldig indien we geprobeerd om toegang te krijgen later. Aangezien we verklaren heap-toegewezen geheugen, we zullen moeten zorgen voor het vrijmaken van het later voor ons programma om niet lekken geen geheugen. We hebben punteren op die voor al het andere in de code alleen gemakshalve tegelijkertijd, maar als je ooit een functie schrijven die er zo uitziet waar heb je - sommigen noemen het een malloc of realloc binnen - wilt u ervoor zorgen dat u een soort van reactie zetten hier up die zegt: hey, je weet wel, geeft een heap-toegewezen knooppunt geïnitialiseerd met de doorrekeningen in waarde. En dan wilt u ervoor zorgen dat u in een soort briefje dat zegt: de beller moet bevrijden van de terug-geheugen. Op die manier, als iemand ooit gaat en maakt gebruik van die functie, ze weten dat wat ze terug van die functie op een gegeven moment moeten worden bevrijd. 

Ervan uitgaande dat alles hier goed en wel, kunnen we naar beneden gaan in onze code en vervang alle van deze lijnen hier met oproepen naar onze build knooppunt functie. Laten we dat doen echt snel. Het ene deel dat we niet gaan vervangen is dit deel hier beneden onderaan waar we eigenlijk kabellengte de knooppunten naar elkaar, want dat kunnen we niet doen in onze functie. Maar, laten we het doen root = build_node (7); knoop * drie = build_node (3); knooppunt * zes = build_node (6); knoop * negen = build_node (9);. En nu, wilden we ook nodes toe te voegen voor - knooppunt * vijf = build_node (5); knoop * acht = build_node (8); en wat was het andere knooppunt? Laten we hier zien. We wilden ook nog een 2 - knooppunt * twee = build_node (2);. Alright. Op dit punt, weten we dat we de 7, de 3, de 9, en de 6 kreeg alle bedraad op de juiste wijze, maar hoe zit het met 5, de 8, en de 2? Om alles te houden in de juiste volgorde, we weten dat juist kind drie is 6. Dus, als we gaan naar de 5 toe te voegen, de 5 behoort ook in de rechterkant van de boom waarvan 3 de wortel, dus 5 behoort als de linker kind van 6. We kunnen dit doen door te zeggen, zes -> left_child = vijf; en dan de 8 behoort als de linker kind van 9, dus negen -> left_child = acht; en dan 2 is de linker kind van 3, dus we kunnen dat doen hier - thee -> left_child = twee;. Als je niet helemaal volgen samen met dat, ik stel voor dat je trek het uit jezelf. 

Alright. Laten we bewaar deze. Laten we naar buiten gaan en ervoor te zorgen dat de samenstelling en het en dan kunnen we toevoegen aan onze Bevat gesprekken. Het lijkt erop dat alles nog compileert. Laten we in en voeg in een aantal bevat gesprekken. Nogmaals, ik ga een beetje kopiëren en plakken doen. Nu laten we zoeken naar 5, 8, en 2. Alright. Laten we ervoor zorgen dat dit alles ziet er nog steeds goed uit. Geweldig! Opslaan en stoppen. Laten we nu te maken, samen te stellen, en laten we nu lopen. Uit de resultaten, het lijkt erop dat alles werkt gewoon mooi en goed. Geweldig! Dus nu hebben we onze bevat functiebouwstenen geschreven. Laten we verder gaan en beginnen te werken over hoe je nodes in te voegen in de boom omdat, zoals we doen het nu, dingen zijn niet erg mooi. 

Als we terug gaan naar de specificatie, Het vraagt ​​ons om te schrijven een functie genaamd invoegen - nogmaals, het teruggeven van een bool voor het al dan niet konden we het knooppunt daadwerkelijk in te voegen in de boom - waarna de waarde in te voegen in de boom is gespecificeerd als het enige argument om onze insert functie. We zullen terugkeren waar als we de knoop met waarde inderdaad te voegen in de boom, wat betekent dat we, een, genoeg geheugen had, en dan twee, heeft dat knooppunt niet al bestaan ​​in de boom, omdat - vergeet niet, we niet van plan om dubbele waarden hebben in de boom, alleen maar om dingen eenvoudig. Alright. Terug naar de code. Open het. Zoom in een beetje, dan scroll naar beneden. Laten we de insert-functie rechts boven de bevat. Nogmaals, het is gaan heten bool insert (int waarde). Geef het een beetje meer ruimte, en dan, als standaard, laten we in return false helemaal aan het eind. Nu op de bodem, we gaan je gang en in plaats van handmatig de bouw van de knooppunten in de belangrijkste onszelf en bedrading ze te wijzen op elkaar als we aan het doen, we vertrouwen op onze insert functie om dat te doen. We zullen niet vertrouwen op onze insert-functie om de hele boom van de grond af op te bouwen gewoon nog niet, maar we zullen ontdoen van deze lijnen - we zullen de volgende regels toe - die voortbouwen de knooppunten 5, 8, en 2. En in plaats daarvan zullen we voegen bellen naar onze insert-functie om ervoor te zorgen dat dat echt werkt. Daar gaan we. 

Nu hebben we commentaar van deze lijnen. We slechts 7, 3, 9 en 6 in de boom op dit punt. Om ervoor te zorgen dat dit alles werkt, kunnen we uit te zoomen, onze binaire boom, draaien, en we kunnen zien dat bevat nu ons te vertellen dat we helemaal rechts - 5, 8 en 2 niet langer in de boom. Ga terug in de code, en hoe gaan we om in te voegen? Weet je nog wat we deden toen we waren eigenlijk het plaatsen van 5, 8, en 2 eerder. We speelden dat Plinko spel waar we begonnen aan de wortel, ging de boom voor een door een totdat we vonden de gepaste opening, en dan hebben we vast in de knoop op de juiste plek. We gaan hetzelfde doen. Dit is in principe net als het schrijven van de code die we gebruikt in de functie bevat de plaats waar de knoop moet vinden, en dan gaan we gewoon naar het knooppunt voegen daar. Laten we beginnen om dat te doen. 

Dus hebben we een knoop * huidig ​​= root, we gaan gewoon te houden aan de code bevat totdat we vinden dat het niet helemaal werkt voor ons. We gaan om te gaan door de boom, terwijl het huidige element is niet nul, en als we vinden dat huidig ​​waarde is gelijk aan de waarde die we proberen in te voegen - goed, dit is een van de gevallen die we konden niet echt steek het knooppunt in de boom, omdat dit betekent dat we een dubbele waarde. Hier zijn we echt gaan om terug te keren vals. Nu else if huidig ​​waarde kleiner is dan de waarde, Nu weten we dat we naar rechts te verplaatsen  omdat de waarde hoort in de rechter helft van de huidige boom. Anders gaan we naar links te verplaatsen. Dat is eigenlijk onze Bevat functioneren daar. 

Op dit punt, als we eenmaal hebt voltooid deze while-lus, onze huidig ​​wijzer zal worden gericht op null als de functie nog niet teruggekeerd. We hebben dan ook huidig ​​op de plek waar we willen het nieuwe knooppunt plaatst. Wat nog gedaan moet worden is om daadwerkelijk bouwen van de nieuwe node, die we kunnen vrij gemakkelijk te doen. We kunnen gebruik maken van onze superhandige build knooppunt functie, en iets dat we niet doen eerder - we gewoon een soort van vanzelfsprekend vonden, maar nu zullen we doen alleen maar om ervoor te zorgen - we testen om ervoor te zorgen dat de waarde die wordt geretourneerd door nieuwe knooppunt eigenlijk was niet null is, omdat we niet willen beginnen met het openen dat het geheugen als het null. We kunnen testen om ervoor te zorgen dat nieuwe knooppunt niet gelijk is aan nul. Of in plaats daarvan, kunnen we gewoon zien of het daadwerkelijk nul is, en als het nul is, dan kunnen we gewoon vroeg return false. 

Op dit punt moeten we nieuwe knoop draad in de juiste plek in de boom. Als we terugkijken op de belangrijkste en waar we waren eigenlijk bedrading in waarden voor, zien we dat de manier waarop we dat deden toen we wilden naar 3 in de boom was dat we benaderd de linker kind van de wortel. Wanneer we 9 in de boom, moesten we de juiste kind van de root-toegang. We moesten een pointer naar de moederverbinding om een ​​nieuwe waarde genomen de boom. Scrollen een back-up in te voegen, dat is niet van plan om helemaal hier werken omdat we niet over een parent-pointer. Wij willen kunnen doen is, op dit punt, Controleer de ouders waarde en zie - nou ja, goh, Als de ouder lager is dan de huidige waarde, dan is de ouder het recht kind moet de nieuwe node te zijn; anders, moet de ouder de linker kind van de nieuwe node. Maar, we hebben niet de parent-pointer helemaal nog niet. 

Om het te krijgen, we echt gaan hebben om het te volgen als we door de boom en vind de juiste plek in ons lus boven. We kunnen dat doen door naar een back-up naar de top van onze insert-functie en het bijhouden van een andere pointer variabele genaamd de ouder. We gaan in te stellen die gelijk is aan het begin null, en dan elke keer als we gaan door de boom, we gaan naar de parent-pointer ingesteld op de huidige cursorpositie te passen. Stel ouder van huidig. Op deze manier, elke keer dat we gaan door, we gaan om ervoor te zorgen dat als de huidige cursorpositie wordt opgehoogd de ouder wijzer volgt het - net een niveau hoger dan de huidige cursorpositie in de boom. Dat ziet er allemaal best goed. 

Ik denk dat het een ding dat we willen stellen is dit te bouwen knooppunt terug null. Om te krijgen op te bouwen knooppunt om daadwerkelijk met succes terug te keren null, we moeten die code te wijzigen, want hier hebben we nooit getest om ervoor te zorgen dat malloc een geldige pointer terug. Dus als (n = NULL's), dan - als malloc terug een geldige pointer, dan zullen wij deze initialiseren; anders, zullen we gewoon terug en dat zal uiteindelijk terugkeren null voor ons. Nu zijn alle ziet er goed uit. Laten we ervoor zorgen dat dit eigenlijk compileert. Maak binaire boom, en oh, we hebben een aantal dingen aan de hand. 

We hebben een impliciete verklaring van de functie op te bouwen knooppunt. Nogmaals, met deze compilers, gaan we beginnen aan de top. Wat dat moet betekenen dat ik bel bouwen knooppunt voor ik heb eigenlijk verklaard. Laten we terug gaan naar de code heel snel. Scroll naar beneden, en ja hoor, mijn insert-functie wordt verklaard boven de build knooppunt functie, maar ik probeer te gebruiken node binnenkant van insert. Ik ga naar binnen en kopiëren - en plak de build knooppunt functie weg hier aan de top. Op die manier, hopelijk dat zal werken. Laten we dit nog eens gaan. Nu stelt zij alles. Alles is goed. 

Maar op dit punt hebben we niet echt geroepen onze insert-functie. We weten dat het compileert, dus laten we naar binnen gaan en er wat gesprekken binnen Laten we dat in onze belangrijkste functie. Hier hebben we uitgecommentarieerd 5, 8, en 2, en dan hebben we niet bedraden hier beneden. Laten we wat telefoontjes plegen om in te voegen, en laten we ook dezelfde soort dingen die we gebruikten gebruiken als we deze printf oproepen om ervoor te zorgen dat alles was goed te krijgen geplaatst. Ik ga om te kopiëren en plakken, en bevat in plaats van we gaan insert doen. En in plaats van 6, 10, en 1, we gaan naar 5, 8, en 2 te gebruiken. Deze hopelijk invoegen 5, 8 en 2 in de boom. Samen te stellen. Alles is goed. Nu gaan we echt rennen ons programma. 

Alles terug vals. Dus, 5, 8, en 2 niet gaan, en het lijkt erop Bevat ook niet vinden. Wat is er aan de hand? Laten we uit te zoomen. Het eerste probleem was dat insert leek om terug te keren vals, en het lijkt erop dat dat is omdat we nog in onze return false oproep, en we nooit echt terug waar. Wij kunnen dat op. Het tweede probleem is nu, zelfs als we dat doen - Bewaar deze, sluit deze, draai make nogmaals, laat het dan vervolgens compileren, voer het uit - zien we dat hier nog iets anders gebeurd. De 5, 8 en 2 waren nog nooit gevonden in de boom. Dus, wat is er aan de hand? 

Laten we eens een kijkje nemen op deze in de code. Laten we eens kijken of we dit uitzoeken. We beginnen met de ouder het niet null. We zetten de huidige cursorpositie gelijk aan de wortel wijzer, en we gaan onze af te werken door middel van de boom. Als het huidige knooppunt niet null is, dan weten we dat we naar beneden een beetje. We zetten onze parent-pointer gelijk te zijn aan de huidige cursorpositie, controleerde de waarde - als de waarden gelijk zijn we terug vals. Als de waarden minder zijn we verhuisd naar de rechterkant; anders, zijn we verhuisd naar de linkerkant. Dan bouwen we een knooppunt. Ik zal in te zoomen een beetje. En hier, we gaan proberen om bedraden de waarden hetzelfde te zijn. Wat is er aan de hand? Laten we eens kijken of eventueel Valgrind kan ons een hint. 

Ik wil Valgrind gebruiken, alleen maar omdat Valgrind echt snel loopt en vertelt u of er geheugenfouten. Wanneer we lopen Valgrind op de code, zoals je kunt zien rechts here--Valgrind./binary_tree--and druk op enter. Je ziet dat we geen geheugen fout, dus het lijkt erop dat alles is in orde nu toe. We hebben wel wat geheugenlekken, waarvan we weten, omdat we niet gebeurt met een van onze knooppunten te bevrijden. Laten we proberen het uitvoeren van GDB om te zien wat er eigenlijk aan de hand. We doen gdb. / Binary_tree. Het opgestart prima. Laten we stellen een breekpunt op insert. Laten we lopen. Het lijkt erop dat we nooit echt geroepen insert. Het lijkt erop dat het probleem was alleen dat toen ik veranderde hier beneden in de belangrijkste - al deze printf oproepen bevat - Ik heb nooit echt veranderd deze naar insert bellen. Laten we nu eens te proberen. Laten we samen te stellen. Alle ziet er goed uit daar. Nu gaan we proberen het runnen van het, zie wat er gebeurt. Alright! Alles ziet er goed uit daar. 

Het laatste ding om te denken is, zijn er randgevallen aan deze inzet? En het blijkt dat, nou ja, de ene rand geval dat altijd interessant om na te denken over is, wat gebeurt er als uw boom leeg is en u noemen insert functie? Zal het werken? Nou, laten we het eens proberen. - Binary_tree c. - De manier waarop we dit gaan testen is, gaan we naar beneden te gaan naar onze belangrijkste functie, en in plaats van bedraden deze knooppunten op als dit, we gaan gewoon commentaar uit de hele zaak, en in plaats van de bedrading van de knooppunten zelf, kunnen we eigenlijk gewoon doorgaan en verwijderen van dit alles. We gaan alles een oproep om in te voegen te maken. Dus, laten we het doen - in plaats van 5, 8, en 2, we gaan tot en met 7 plaatsen, 3 en 9. En dan gaan we ook willen tot 6 invoegen ook. Opslaan. Quit. Maak binaire boom. Het compileert alles. We kunnen gewoon draaien zoals het is en zien wat er gebeurt, maar het is ook gaat echt belangrijk om ervoor te zorgen dat we hebben geen geheugenfouten, want dit is een van onze kant gevallen die we kennen. 

Laten we ervoor zorgen dat het goed werkt onder Valgrind, die we zullen doen door alleen rennen Valgrind. / binary_tree. Het lijkt erop dat we inderdaad een fout van de ene context - we hebben dit segmentation fault. Wat is er gebeurd? Valgrind vertelt ons eigenlijk waar het is. Uitzoomen een beetje. Het lijkt erop dat het gebeurt in onze insert-functie, waar we een ongeldige lezen van grootte 4 hebben op insert, lijn 60. Laten we terug gaan en zien wat er hier aan de hand. Zoom uit echt snel. Ik wil ervoor zorgen dat het niet naar de rand van het scherm, zodat we alles kunnen zien. Trek dat in een klein beetje. Alright. Scroll naar beneden, en het probleem is hier. Wat gebeurt er als we naar beneden en onze huidige knooppunt is reeds null, onze parent node is null, dus als we kijken omhoog naar de top, exact hier - als dit while loop nooit daadwerkelijk wordt uitgevoerd omdat onze huidige waarde is null - onze wortel is null dus huidig ​​null - dan is onze ouder wordt nooit op huidig ​​of naar een geldige waarde, zo is, zal ouder ook null zijn. We moeten niet vergeten om te controleren op dat tegen de tijd dat we hier beneden, en we beginnen met het openen van de ouder-waarde. Dus, wat gebeurt er dan? Nou, als de ouder is null - if (ouder == NULL) - dan weten we dat er moet niet iets in de boom. We moeten proberen om deze in te voegen bij de wortel. We kunnen dat doen door gewoon het instellen van de wortel gelijk is aan de nieuwe node. Dan op dit punt hebben we niet echt willen gaan door die andere dingen. In plaats daarvan, exact hier, kunnen we dit doen een else-if-else, of we kunnen combineren alles hier in een ander, maar hier zullen we gewoon anders te gebruiken en het op die manier. Nu, we gaan testen om ervoor te zorgen dat onze ouders niet null is voor die tijd eigenlijk proberen om de velden te gebruiken. Dit zal ons helpen voorkomen dat de segmentation fault. Dus, we stoppen, zoomen, compileren, uit te voeren. 

Geen fouten, maar we hebben nog een heleboel geheugenlekken omdat we niet bevrijden van een van onze knooppunten. Maar, als we hier en we kijken naar onze afdruk, zien we dat, nou, ziet eruit als al onze inzetstukken terugkeerden waar is, wat goed is. De inserts zijn allemaal waar, en vervolgens de juiste Bevat gesprekken zijn ook waar. 

Good job! Het lijkt erop dat we met succes geschreven insert. Dat is alles wat we hebben voor Problem deze week Set specificatie. Een leuke uitdaging om na te denken over hoe je eigenlijk zou gaan in en vrij alle knooppunten in deze boom. We kunnen dit doen op verschillende manieren maar ik laat dat aan jou om te experimenteren, en als een leuke uitdaging, proberen en zorg ervoor dat u er zeker van kunt maken dat dit Valgrind rapport had geen fouten en geen lekken. 

Veel succes op deze week Huffman-codering probleem set, en we zien jullie volgende week! [CS50.TV]