[Powered by Google Translate] [Deel 7: Meer Comfortabele] [Rob Bowden] [Harvard University] [Dit is CS50] [CS50.TV] Oke. Dus zoals ik al zei in mijn e-mail, Dit wordt een binaire boom intensief sectie. Maar er zijn niet zo veel vragen. Dus we gaan proberen en uit te trekken elke vraag en ga in pijnlijke details van de beste manieren om dingen te doen. Dus meteen aan het begin, we gaan door monster tekeningen van binaire bomen en zo. Dus hier, "Vergeet niet dat een binaire boom knooppunten vergelijkbaar met die van een gekoppelde lijst heeft, behalve in plaats van een wijzer zijn er twee: een voor 'kind' van de linker en een voor het rechter 'kind'. " Dus een binaire boom is net als een gelinkte lijst, met uitzondering van de struct gaat om twee pointers hebben. Er is trinary bomen, die zullen drie wijzers hebben, er zijn N-aire bomen, die gewoon een generieke pointer dat dan moet je malloc groot genoeg om genoeg verwijzingen naar alle mogelijke kinderen. Dus binaire boom toevallig een constant aantal van twee. Als je wilt, kun je een gelinkte lijst als een unaire boom, maar ik denk niet dat iemand noemt het dat. "Teken een dozen-en-pijlen diagram van een binaire boom knooppunt met favoriete nummer Nate's, 7, waar elk kind pointer nul is. " Dus iPad-modus. 

Het zal behoorlijk eenvoudig. We gaan gewoon naar een knooppunt heb, zal ik tekenen als een vierkant. En ik zal de aandacht van de waarden in hier. Dus de waarde moet hierin, en hier beneden we de linker aanwijzer links en rechts pointer rechts. En het is heel erg zelfs conventie noem het links en rechts, de aanwijzer namen. Beide zullen worden null. Dat is gewoon zal nul zijn, en dat zal gewoon null zijn. Oke. Dus terug naar hier. "Met een gekoppelde lijst, we moesten een pointer op te slaan het eerste knooppunt in de lijst om het geheel gekoppelde lijst of de hele lijst onthouden. Ook met bomen, we hoeven alleen maar een pointer op te slaan een knooppunt om de hele boom herinneren. Dit knooppunt is calle de 'root' van de boom. Voort te bouwen op uw diagram van voor of teken een nieuwe zo dat je een dozen-en-pijlen afbeelding van een binaire boom hebben met de waarde 7 dan 3 in de linker, daarna 9 rechts en vervolgens 6 rechts van de 3 '. Laten we eens kijken of ik kan dat allemaal niet vergeten in mijn hoofd. Dus dit gaat onze wortels hier zijn. We hebben een aantal aanwijzer ergens, iets wat we noemen wortel, en het is te wijzen op deze kerel. Nu om een ​​nieuw knooppunt te maken, wat hebben we, 3 aan de linkerkant? Zodat een nieuw knooppunt met 3 en aanvankelijk wijst null. Ik leg N. Nu willen we dat gaan aan de linkerkant van 7. Dus we veranderen pointer naar nu wijzen op deze kerel. En we doen hetzelfde. We willen een 9 hier die in eerste instantie gewoon zegt null. We gaan deze pointer, punt wijzigen tot en met 9, en nu willen we tot en met 6 maken aan het recht van 3. Dus het gaat om - een 6. En die man zal wijzen daar. Oke. Dus dat is alles wat het ons vraagt. 

Laten we nu gaan over een aantal terminologie. We hebben al gesproken over hoe de wortel van de boom is de bovenste knoop in de boom. Degene met 7. De knooppunten aan de onderkant van de boom worden genoemd de bladeren. Elke node die net heeft null als kinderen is een blad. Zo is het mogelijk, als onze binaire boom is slechts een knooppunt, dat een boom is een blad, en dat is het. "De 'hoogte' van de boom is het aantal hops die je moet maken te krijgen van de top tot een blad. " We krijgen in, in een tweede, het verschil tussen gebalanceerde en ongebalanceerde binaire bomen, maar voor nu, de totale hoogte van deze boom Ik zou zeggen is 3, maar als je telt het aantal hops die je moet maken om te krijgen tot 9, dan is het eigenlijk alleen maar een hoogte van 2. Op dit moment is dit een onevenwichtige binaire boom, maar we zullen het over een evenwichtige wanneer het wordt relevant te zijn. Dus nu kunnen we praten over knopen in een boom in termen opzichte van de andere knooppunten in de boom. Dus nu hebben we ouders, kinderen, broers en zussen, voorouders en nakomelingen. Ze zijn redelijk gezond verstand, wat ze betekenen. Als we vragen - het is ouders. Dus wat is de moedermaatschappij van 3? [Studenten] 7. >> Ja. De ouder wordt gewoon gaat worden welke punten voor jou. En wat zijn de kinderen van 7? [Studenten] 3 en 9. >> Ja. Merk op dat "kinderen" letterlijk kinderen betekent, dus 6 niet van toepassing, want het is net een kleinkind. Maar dan als we nakomelingen, dus wat zijn de afstammelingen van 7? [Studenten] 3, 6 en 9. >> Ja. De afstammelingen van de wortel gaat alles in de boom, behalve misschien de root node zelf, als je niet wilt dat een afstammeling te overwegen. En tot slot, voorouders, dus het is de tegenovergestelde richting. Dus wat zijn de voorouders van 6? [Studenten] 3 en 7. >> Ja. 9 is niet inbegrepen. Het is gewoon de directe afstamming terug naar de wortel gaat worden uw voorouders. 

"We zeggen dat een binaire boom is 'besteld' als voor elk knooppunt in de boom, al zijn nakomelingen links hebben minder waarden en alle aan de juiste hebben hogere waarden. Zo wordt de boom boven besteld worden maar het is niet de enige mogelijke geordende. " Voordat we naar die, een geordende binaire boom wordt ook wel een binaire zoekboom. Hier hebben we toevallig noemde het een geordende binaire boom, maar ik heb nooit gehoord dat het wel een geordende binaire boom voor, en op een quiz zijn we veel meer kans om binaire zoekboom te zetten. Ze zijn een en dezelfde, en het is belangrijk dat u herkent het onderscheid tussen binaire boom en binaire zoekboom. Een binaire boom is slechts een boom die naar twee dingen. Elk knooppunt wijst op twee dingen. Er is geen redenering over de waarden die het verwijst. Dus hier graag over, want het is een binaire zoekboom, We weten dat als we naar links van 7, dan alle waarden die we kunnen eventueel bereiken door naar links 7 hebben minder dan 7. Merk op dat alle waarden lager dan 7 zijn 3 en 6. Deze zijn links van 7. Als we naar rechts van 7, alles groter dan 7, dus 9 is aan de rechterkant van 7, dus we zijn goed. Dit is niet het geval voor een binaire boom, een regelmatige binaire boom we gewoon 3 boven, 7 naar links, 9 links van 7, er is geen volgorde van waarden dan ook. Nu zullen we niet echt doen, want het is vervelend en onnodig, maar "proberen om zo veel besteld bomen trekken als je maar kunt bedenken met de cijfers 7, 3, 9 en 6. Hoeveel verschillende regelingen zijn er? Wat is de hoogte van elke? " 

We doen een paar, maar het belangrijkste idee is, dit is geenszins een unieke representatie van een binaire boom die deze waarden. Alles wat we nodig hebben is een aantal binaire boom die 7 bevat, 3, 6, en 9. Een andere mogelijke geldig zou zijn de wortel is 3, naar links en het is 6 naar links en het is 7, naar links en het is 9. Dat is een volkomen geldige binaire zoekboom. Het is niet erg behulpzaam, want het is net als een gekoppelde lijst en al deze pointers zijn gewoon null. Maar het is geldig boom. Ja? [Student] Niet de waarden groter te zijn aan de rechterkant? Of is dit -? >> Deze bedoelde ik de andere kant op te gaan. Er is ook - ja, laten we wisselen dat. 9, 7, 6, 3. Goede vangst. Het heeft nog steeds te gehoorzamen wat een binaire boom zoekopdracht verondersteld wordt te doen. Dus alles naar links moet minder dan een bepaald knooppunt. We konden gewoon bewegen, zeggen, dit 6 en hier zet het. Nee, dat kunnen we niet. Waarom moet ik blijven doen? Laten we het doen - hier is 6, hier is 7, 6 punten 3. Dit is nog steeds een geldige binaire zoekboom. Wat is er mis als ik - laten we eens kijken of ik kan komen met een regeling. Ja, oke. Dus wat is er mis met deze boom? Ik denk dat ik heb al gegeven je een hint dat er iets mis mee is. Waarom moet ik blijven doen? Oke. Dit ziet er redelijk. Als we kijken naar elk knooppunt, zoals 7, dan naar links 7 is 3. Dus we 3 hebben, het ding aan de rechterkant van 3 is een 6. En als je kijkt naar 6, het ding aan de rechterkant van 6 is een 9. Dus waarom is dit geen geldige binaire zoekboom? [Studenten] 9 nog links van 7. >> Ja. Het moet zo dat alle waarden kan eventueel bereiken door naar links van 7 minder dan 7. Als we naar links van 7 komen we bij 3 en we kunnen nog steeds tot 6, we kunnen nog steeds tot 9, maar door zijn gegaan minder dan 7, we niet in staat om naar een getal dat groter is dan 7. Dus dit is geen geldige binaire zoekboom. 

Mijn broer had eigenlijk een interview vraag dat in principe was dit, net code iets om te valideren of een boom is een binaire zoekboom, en dus het eerste wat hij deed was gewoon controleren om te zien als de linker en rechter juist zijn, en dan is er iterate beneden. Maar je kunt niet zomaar doen, je moet bijhouden van het feit dat nu ik ben gegaan links van 7, alles in deze substructuur moet lager zijn dan 7. De juiste algoritme moet bijhouden van de grenzen die de waarden eventueel kan vallen binnen We zullen niet gaan door alle van hen. Er is een mooi herhaling relatie, hoewel we nog niet gekregen om deze, of zullen we niet krijgen op die, het definiëren van hoeveel het er zijn. Er zijn 14 daarvan. Het idee van hoe je het zou doen is het wiskundig als, u kunt kiezen uit een willekeurige enkele ene naar de root node zijn, en dan als ik kies 7 tot en met de root-node zijn, dan zijn er, laten we zeggen, een aantal nummers die kunnen gaan worden mijn linker knooppunt, en er zijn een aantal nummers die kunnen mijn rechter knooppunt te zijn, maar als ik heb n totale aantallen, dan is het bedrag dat kan naar links vermeerderd met het bedrag dat u naar de juiste is n - 1. Zodat de overige getallen, ze kunnen ofwel naar links of rechts. Het lijkt moeilijk, dat, als ik 3 dan eerst alles moet gaan naar links, maar als ik 7 zet, dan sommige dingen kunnen gaan het de linker-en sommige dingen kunnen gaan naar rechts. En door '3 eerste 'Ik meende alles wat kan gaan naar rechts. Het is echt, je moet gewoon zo denken, hoeveel dingen kunnen gaan op het volgende niveau van de boom. En het komt te zijn 14, of u kunt tekenen ze allemaal, en dan krijg je 14. 

Terug te gaan hier, "Geordende binaire bomen zijn cool, want we kunnen zoeken door hen in een zeer vergelijkbare manier om te zoeken op een gesorteerde array. Om dit te doen, we beginnen bij de wortel en werken onze weg naar beneden de boom in de richting van bladeren, het controleren van elk knooppunt van de waarden ten opzichte van de waarden die wij zoekt. Als de huidige knooppunt lager is dan de waarde die we zoeken, ga je naast het knooppunt juiste kind. Anders, ga je naar de linkerkant van de node kind. Op een gegeven moment, zult u vinden, hetzij de waarde die u zoekt, of kom je in een null, met vermelding van de waarde is niet in de boom. " Ik moet de boom hadden we eerder opnieuw te tekenen, dat duurt een seconde. Maar we willen opzoeken of 6, 10, en 1 in de boom. Dus wat was, 7, 9, 3, 6. Oke. De nummers die u wilt opzoeken, we willen kijken met 6. Hoe werkt dit algoritme zijn werk? Nou, we hebben ook een aantal wortel pointer naar onze boom. En we zouden gaan naar de wortel en zeggen: is deze waarde gelijk aan de waarde die we zoekt? Dus we zijn op zoek naar 6, dus het is niet gelijk. Dus we blijven gaan, en nu zeggen we, oke, dus 6 is minder dan 7. Betekent dat dat we willen gaan naar links, of willen we naar de juiste? [Student] Links. >> Ja. Het is veel eenvoudiger, alles wat je hoeft te doen trekken een mogelijke knooppunt van de boom en dan moet je Niet doen - in plaats van te proberen om te denken in je hoofd, oke, als het minder, ga ik naar links of naar rechts, gewoon op zoek naar deze foto, het is heel duidelijk dat ik moet naar links indien dit knooppunt groter is dan de waarde die ik zoek. Dus ga je naar links, nu ben ik op 3. Ik wil - 3 kleiner is dan de waarde Ik ben op zoek naar, dat is 6. Dus gaan we naar rechts, en nu heb ik uiteindelijk op 6, Dit is de waarde Ik ben op zoek naar, dus ik terug waar. De volgende waarde ik ga op zoek naar is 10. Oke. Dus 10, nu gaat - afgesneden dat - naar de wortel te volgen. Nu, 10 zal groter zijn dan 7, dus ik wil kijken naar rechts. Ik ga hier naartoe te komen, wordt 10 zal groter zijn dan 9, dus ik ga naar willen kijken naar rechts. Ik kom hier, maar hier nu ben ik op null. Wat moet ik doen als ik geraakt null? [Student] Terug vals? >> Ja. Ik vind helemaal niet 10. 1 wordt een vrijwel identieke geval, behalve dat het gewoon gaat worden omgedraaid, in plaats van naar aan de rechterzijde, ik ga naar beneden kijken de linkerkant. 

Nu denk ik dat we ook echt om te code. Hier is waar - het openstellen van de CS50 apparaat en er uw weg, maar je kunt ook gewoon doen in de ruimte. Het is waarschijnlijk ideaal om het te doen in de ruimte, want we kunnen werken in de ruimte. "Eerst zullen we een nieuw type definitie voor een binaire boom knooppunt met int-waarden. Met de standaardtekst typedef hieronder een nieuw type definitie van een knooppunt in een binaire boom. Als je vast komt te zitten. . . "Bla, bla, bla. Oke. Dus laten we hier zet de standaardtekst, typedef struct knoop en knoop. Ja, oke. Dus wat zijn de velden gaan we willen in ons knoop? [Student] Int en dan twee pointers? >> Int waarde, twee pointers? Hoe schrijf ik de pointers? [Student] Struct. >> Ik zoomen Ja, dus struct knoop * links, en struct knoop * rechts. En vergeet niet de discussie van de vorige keer, dat dit geen zin heeft, dit heeft geen zin, Dit heeft geen zin. Je moet alles wat er om deze recursieve struct te definiëren. Oke, dus dat is wat onze boom gaat zien. Als we een trinary boom, dan een knoop eruit zou kunnen zien b1, b2, struct knoop * b3, waarbij b een tak - in feite, heb ik meer gehoord links, midden, rechts, maar wat dan ook. We hebben alleen de zorg over binaire, dus rechts, links. "Nu verklaren een wereldwijde knooppunt * variabele voor de wortel van de boom." Dus we gaan niet om dat te doen. Om dingen iets moeilijker en meer algemeen, zullen we niet over een wereldwijde knooppunt variabele. In plaats daarvan, in de belangrijkste zullen we verklaren al onze knooppunt dingen, en dat betekent dat hieronder, als we vertoond onze Bevat functie en onze insert-functie, in plaats van onze bevat functiebouwstenen alleen met behulp van deze wereldwijde knooppunt variabele, we gaan om het te laten nemen als argument de boom die we willen dat het te verwerken. Het hebben van de globale variabele moest dingen makkelijker te maken. We gaan om dingen moeilijker. Neem nu een minuut of zo om dat te doen dit soort dingen, waar binnen van de belangrijkste u wilt deze boom te maken, en dat is alles wat je wilt doen. Probeer en de bouw van deze boom in uw belangrijkste functie. 

Oke. Dus je hoeft niet eens te hebben gebouwd de boom de hele weg nog niet. Maar iemand nog iets wat ik zou kunnen optrekken om te laten zien hoe men zou kunnen beginnen bouwen zoals een boom? [Student] Iemand bonzen, in een poging om eruit te komen. [Bowden] Iedereen comfortabel met hun boom bouw? [Student] Tuurlijk. Het is nog niet klaar. >> Het is prima. We kunnen gewoon afmaken - oh, kunt u het opslaan? Hooray. Hier hebben we dus - oh, ik ben een beetje afgesneden. Ben ik ingezoomd? Zoom in, bladeren uit. >> Ik heb een vraag. >> Ja? [Student] Wanneer u struct te definiëren, zijn dingen als geïnitialiseerd iets? [Bowden] Nee. >> Oke. Dus je zou moeten initialiseren - [Bowden] Nee Bij het definiëren, of wanneer u verklaren een struct, het is niet geïnitialiseerd standaard, het is net als wanneer u verklaart een int. Het is precies hetzelfde. Het is net als elk van de afzonderlijke velden kan een vuilnis waarde in. >> En is het mogelijk om te bepalen - of te verklaren een struct zodanig dat het wel initialiseren? [Bowden] Ja. Dus, snelkoppeling initialisatie syntaxis gaat uitzien - Er zijn twee manieren waarop we dit kunnen doen. Ik denk dat we het te compileren om ervoor te zorgen Clang ook doet. De volgorde van argumenten die komt in de struct, zet je als de volgorde van argumenten binnenkant van deze accolades. Dus als je wilt om het te initialiseren tot 9 en links worden nul en dan rechts nul, het zou 9, null, null. Het alternatief is, en de editor houdt niet van deze syntaxis, en hij denkt dat ik wil een nieuw blok, maar het alternatief is zoiets als - hier, ik zet het op een nieuwe regel. U kunt expliciet zeggen, ik vergeet de exacte syntax. Zo kunt u expliciet aandacht besteden aan hun naam, en zeggen: C. Of. Waarde = 9,. Links = NULL. Ik gok dat deze moeten worden komma's. . Rechts = NULL, dus op deze manier je dat niet doet eigenlijk nodig om de volgorde van de struct kennen, en als je dit leest, het is veel explicieter over wat de waarde er wordt geïnitialiseerd op. 

Dit gebeurt als een van de dingen die - dus voor het grootste deel, C + + is een superset van C. U kunt C-code, verplaats deze naar C + +, en het moet compileren. Dit is een van de dingen die C + + niet ondersteunt, zodat mensen niet geneigd zijn om het te doen. Ik weet niet of dat is de enige reden waarom mensen de neiging om het niet te doen, maar de zaak waar ik moest om het te gebruiken die nodig zijn om te werken met C + + en dus kon ik niet gebruiken. Een ander voorbeeld van iets dat niet werkt met C + + is hoe malloc geeft een "void *," technisch, maar je kon gewoon zeggen char * x = malloc wat dan ook, en het zal automatisch worden geworpen om een ​​char *. Dat automatische cast gebeurt niet in C + +. Dat zou niet compileren, en je zou expliciet moeten zeggen char *, malloc, wat dan ook, om het te werpen naar een char *. Er zijn niet veel dingen die C en C + + het oneens zijn over, maar dat zijn twee. Dus we zullen gaan met deze syntax. Maar zelfs als we niet gaan met dat syntaxis, wat is - kan het mis met deze? [Student] Ik hoef niet te dereference het? >> Ja. Vergeet niet dat de pijl een impliciete dereference heeft, en dus als we gewoon te maken met een struct, we willen gebruiken. te krijgen op een veld binnenkant van de struct. En de enige keer dat we gebruik maken van pijl is wanneer we willen doen - goed pijl gelijk aan - dat is wat het zou betekenen als ik pijl. Alle pijl middelen is, dereference dit, nu ben ik in een struct, en ik kan het veld te krijgen. Ofwel krijgen het veld direct of dereference en krijg het veld - Ik denk dat dit zou moeten zijn waarde. Maar hier ik te maken heb met slechts een struct, niet een pointer naar een struct, en dus kan ik geen gebruik maken van de pijl. Maar dit soort dingen we kunnen doen voor alle knooppunten. Oh mijn God. Dit is 6, 7 en 3. Dan kunnen we het opzetten van de vestigingen in onze boom, kunnen we 7 - we hebben, moet de linkerkant verwijzen naar 3. Dus hoe doen we dat? [Studenten, onverstaanbaar] >> Ja. Het adres van node3, en als je niet-adres hebben, dan is het gewoon niet samen te stellen. Maar vergeet niet dat deze zijn verwijzingen naar de volgende knooppunten. Het recht moet verwijzen naar 9, en 3 moet erop rechts tot 6. Ik denk dat dit is helemaal klaar. Eventuele opmerkingen of vragen? [Student, onverstaanbaar] De wortel gaat worden 7. We kunnen alleen maar zeggen knooppunt * ptr = of wortel, = & node7. 

Voor onze doeleinden, gaan we te maken hebben met insert, dus we gaan een functie wilt invoegen in deze binaire boom schrijven en insert is onvermijdelijk zal malloc bellen om een ​​nieuw knooppunt voor deze boom te creëren. Dus dingen gaan rommelig te krijgen met het feit dat sommige knooppunten zijn op de stapel en andere knooppunten gaan om te eindigen op de heap als we invoegen. Dit is volkomen geldig, maar de enige reden zijn we in staat om dit te doen op de stapel is omdat het zo'n gekunstelde voorbeeld dat we kennen de boom moet worden uitgevoerd als 7, 3, 6, 9. Als we niet over dit, dan zouden we niet te malloc in de eerste plaats. Als we een beetje later te zien, moeten we malloc'ing. Op dit moment is het volkomen redelijk om op de stapel gelegd, maar laten we dit te wijzigen in een malloc implementatie. Dus elk van deze gaat nu iets als knooppunt * node9 = malloc (sizeof (node)). En nu gaan we te hebben om ons in te checken doen. if (node9 == NULL) - Ik wilde niet dat - return 1, en dan kunnen we doen node9-> want nu is het een pointer, value = 6, node9-> links = NULL, node9-> rechts = NULL, en we gaan te hebben om dat te doen voor elk van deze knooppunten. Dus in plaats daarvan laten we binnen zet het een aparte functie. Laten we het knooppunt * build_node, en dit is enigszins vergelijkbaar met de API we voorzien Huffman codering. Wij geven u initializer functies voor een boom en Deconstructor "functies" voor die bomen en hetzelfde voor de bossen. 

Dus hier gaan we een initializer functie hebben gewoon bouwen van een knooppunt voor ons. En het gaat vrij veel precies hetzelfde uitzien als deze. En ik ben zelfs gaan worden lui en niet de naam van de variabele, ook al node9 heeft geen zin meer. Oh, ik denk dat node9 de waarde niet had mogen worden 6. Nu kunnen we terugkeren node9. En hier moeten we terug null. Iedereen mee eens build-a-node functie? Dus nu kunnen we gewoon bellen dat aan een knooppunt met een bepaalde waarde en null pointers te bouwen. Nu kunnen we dat noemen, kunnen we doen knooppunt * node9 = build_node (9). En laten we het doen. . . 6, 3, 7, 6, 3, 7. En nu willen we het opzetten van de zelfde pointers, behalve nu alles is al in termen van pointers dus niet meer nodig het adres van. Oke. Dus wat is het laatste wat ik wil doen? Er is een fout controle dat ik niet doe. Wat betekent bouwen knooppunt terug? [Student, onverstaanbaar] >> Ja. Als malloc is mislukt, keert hij terug null. Dus ik ga lui zet het hier beneden in plaats van het doen van een voorwaarde voor elk. Als (node9 == NULL, of - nog eenvoudiger, Dit komt neer op slechts indien niet node9. Als niet node9 of niet node6 of niet node3 of niet node7 terug 1. Misschien moeten we af te drukken malloc is mislukt, of zoiets. [Student] Is valse gelijk aan ook null? [Bowden] Elke nul is false. Dus null is een nul waarde. Zero is een nulwaarde. False is een nul waarde. Elke - zo ongeveer de enige twee nul-waarden zijn nul en nul, vals is net hash gedefinieerd als nul. Dat geldt ook als we verklaren globale variabele. Als we hadden knooppunt * wortel hier, dan - het mooie van globale variabelen is dat ze altijd een initiële waarde. Dat is niet waar van functies, hoe de binnenkant van hier, als we, net als, knooppunt of knooppunt * x. We hebben geen idee wat x.value, x.whatever, of we kunnen ze afdrukken en ze zouden kunnen zijn willekeurig. Dat is niet het geval voor globale variabelen. Dus knooppunt wortel of knooppunt x. Standaard alles wat globale, zo niet expliciet geïnitialiseerd op een bepaalde waarde, een nulwaarde als waarde. Dus hier, knoop * wortel, hebben we niet expliciet initialiseren om iets, zodat de standaardwaarde nul, de nulwaarde van pointers. De standaard waarde van x gaat betekenen dat x.value nul is, x.left null is, en x.right is null. Dus omdat het een struct worden alle velden van de struct nul waarden. We hoeven niet om dat hier te gebruiken, dat wel. [Student] De structs anders zijn dan andere variabelen, en de andere variabelen vuilnis waarden, dit zijn nullen? [Bowden] Andere waarden ook. Dus in x, zal x nul. Als het op mondiaal bereik, het heeft een initiële waarde. >> Oke. [Bowden] Ofwel de initiële waarde die u gaf het of nul. Ik denk dat zorgt voor dit alles. 

Oke. Dus het volgende deel van de vraag gaat het erom, "Nu willen we een functie genaamd bevat schrijven met een prototype van bool bevat int waarde. " We zijn niet van plan om te doen bool bevat int waarde. Ons prototype eruit komt te zien als bool bevat (int waarde. En dan zijn we ook gaan doorgeven van de boom dat moet worden controleren of zij die waarde. Dus knoop * boom). Oke. En dan kunnen we noemen het met iets als, we misschien willen printf of zoiets. Bevat 6, onze wortel. Dat moet een keer terug, of waar, terwijl bevat 5 root moet return false. Dus neem even de tijd om dit te implementeren. Je kunt het zowel iteratief of recursief. Het leuke aan de manier waarop we opgezet dingen is dat leent zich onze recursieve oplossing gemakkelijker dan de global-variabele manier deed. Want als we alleen maar bevat int waarde, dan hebben we geen enkele manier recursing beneden substructuren. We zouden een aparte helper functie die recurses beneden de substructuren voor ons hebben. Maar sinds we het veranderd om de boom te nemen als een argument, waarin zij moeten altijd zijn in de eerste plaats, Nu kunnen we recurse gemakkelijker. Dus iteratieve of recursieve, gaan we over beide, maar we zullen zien dat recursieve eindigt als vrij eenvoudig. Oke. Heeft iemand iets dat we kunnen samenwerken? 

[Student] Ik heb een iteratieve oplossing. >> Oke, iteratief. Oke, dit ziet er goed uit. Dus, wil je ons er doorheen lopen? [Student] Tuurlijk. Dus ik stel een temp variabele om het eerste knooppunt van de boom te krijgen. En dan ga ik gewoon doorgelust terwijl temp is niet gelijk aan nul, dus terwijl nog in de boom, denk ik. En als de waarde gelijk is aan de waarde die temp wordt verwezen, dan is die waarde geretourneerd. Anders wordt er gecontroleerd of het aan de rechter-of de linkerkant. Als je ooit een situatie waarin er geen meer boom, dan is het terug - ze uit de lus en false. [Bowden] Oke. Dus dat lijkt goed. Iemand enig commentaar op alles? Ik heb geen correctheid commentaar op alle. Het enige wat we kunnen doen is deze kerel. Oh, het gaat om een ​​beetje vrij lange gaan. Ik maak dat op. Oke. 

Iedereen moet zich herinneren hoe ternaire werkt. Er hebben zeker quizzen in het verleden dat geeft je een functie met een ternaire operator, en zeggen: vertalen dit, doe iets dat niet gebruikt ternaire. Dus dit is een veel voorkomende geval van als ik zou denken aan ternaire te gebruiken, waar als enige voorwaarde een variabele om iets, anders ingesteld dat dezelfde variabele naar iets anders. Dat is iets dat heel vaak kan worden omgezet in dit soort dingen waar ingesteld die variabele aan deze - of, nou ja, is dit waar? Dan is dit, anders dit. [Student] De eerste is als het waar is, toch? [Bowden] Ja. De manier waarop ik lees altijd het is, temp is gelijk aan waarde groter dan temp waarde, Dan, anders deze. Het is een vraag. Is het groter? Doe dan het eerste. Anders doen het tweede ding. Ik heb bijna altijd - de dikke darm, ik - in mijn hoofd, ik lees als anders. 

Heeft iemand een recursieve oplossing? Oke. Deze gaan we - het zou al geweldig zijn, maar we gaan het nog beter. Dit is vrij veel het zelfde nauwkeurige idee. Het is gewoon, nou ja, wil je het uitleggen? [Student] Tuurlijk. Dus we ervoor te zorgen dat de boom niet wordt eerst null, want als de boom null is, het gaat om terug te keren vals, want we hebben het niet gevonden. En als er nog steeds een boom, gaan we in op - we eerst controleren of de waarde is de huidige knooppunt. Return true als het is, en als we niet recursief aan de linker of rechter. Klinkt dat juist? >> Mm-hmm. (Overeenkomst) Dus merken dat dit bijna is - structureel zeer vergelijkbaar met de iteratieve oplossing. Het is gewoon dat in plaats van recursing, we een while-lus had. En het basisscenario hier, waar boom is niet gelijk aan nul was de voorwaarde waaronder wij uitbrak van de while-lus. Ze zijn zeer vergelijkbaar. Maar we gaan nog een stap verder te nemen. Nu doen we hetzelfde hier. Let op dat we hetzelfde in beide van deze lijnen terug te keren, behalve een argument verschilt. Dus we gaan die te maken in een ternair. Ik raakte optie iets, en het maakte een symbool. Oke. Dus we gaan om terug te keren bevat dat. Dit wordt aan het worden meerdere regels, goed, ingezoomd is. Meestal als een stilistische ding, ik denk niet dat veel mensen Zet een spatie na de pijl, maar ik denk dat als je consequent, het is prima. Als de waarde lager is dan de boom waarde, we willen recurse op boom links, wat we willen recurse op boom rechts. Dus dat was de eerste stap van het maken van deze look kleiner. Stap twee van het maken van deze look kleinere - we scheiden dit meerdere lijnen. Oke. Stap twee van waardoor het lijkt kleiner is hier, dus return waarde is gelijk aan boom-waarde, of bevat wat dan ook. 

Dit is een belangrijk ding. Ik weet niet zeker of hij zei dat het expliciet in de klas, maar het heet kortsluiting evaluatie. Het idee hier is waarde == boom waarde. Als dat waar is, dan is dit waar is, en we willen 'of' dat met wat hier is voorbij. Dus zonder zelfs te denken over wat er hier, wat is de volledige uitdrukking te gaan om terug te keren? [Student] Waar? >> Ja, omdat ware van alles, or'd - of ware or'd met iets is noodzakelijk waar. Dus zodra we return value = boom waarde te zien, we gaan gewoon om terug te keren waar. Niet eens gaan recurse bevat verder langs de lijn. We kunnen nog een stap verder. Terug boom is niet gelijk aan nul en dit alles. Dat maakte het een een-lijn-functie. Dit is een voorbeeld van kortsluiting evalueren. Maar nu is het hetzelfde idee - in plaats van - dus als boom is niet gelijk aan nul - of, nou ja, als boom doet gelijk null, dat is het slechte geval is, Als tree is gelijk nul, dan is de eerste voorwaarde zal zijn vals. Dus valse ge-AND met iets gaat worden wat? [Student] False. >> Ja. Dit is de andere helft van kortsluiting evaluatie, waar als boom niet gelijk nul, dan zijn we niet van plan om eens te gaan - of als boom doet gelijk null, dan zijn we niet van plan om waarde == boom waarde te doen. We gaan gewoon meteen return false. Dat is belangrijk, want als het deed geen kortsluiting te evalueren, dan als boom doet gelijk null is, wordt deze tweede voorwaarde gaat seg schuld, omdat boom-> waarde wordt dereferentie null. Dus dat is dat. Kan dit - verschuiven een keer over. Dit is een veel voorkomend geval ook, verzin dit niet een lijn met deze, maar het is een gemeenschappelijk ding in omstandigheden, misschien niet hier, maar als (boom! = NULL, en boom-> waarde == waarde), doen wat. Dit is een veel voorkomende aandoening, waarbij in plaats van deze te breken in twee mitsen, waar wil, is de boom null? Oke, het is niet null is, dus nu is de boom waarde gelijk aan waarde? Doe dit. In plaats daarvan, deze voorwaarde, zal dit nooit seg fout want het zal breken als dit gebeurt op null zijn. Nou, ik denk dat als je boom is een volledig ongeldig pointer, kan het nog steeds seg schuld, maar het kan niet seg fout als boom is null. Als het null, zou het uitbreken voordat je ooit dereferentie de aanwijzer in de eerste plaats. [Student] Is dit zogenaamde lazy evaluatie? 

[Bowden] Lazy evaluatie is een apart ding. Lazy evaluatie is meer als je vraagt ​​voor een waarde, u vragen om een ​​waarde, een soort van te berekenen, maar je hoeft niet meteen nodig hebt. Dus totdat u daadwerkelijk nodig hebt, is het niet geëvalueerd. Dit is niet precies hetzelfde, maar in de Huffman PSET, het zegt dat we "lui" te schrijven. De reden dat we dat doen is omdat we eigenlijk het bufferen van de schrijf - we niet willen afzonderlijke stukjes schrijven tegelijk of individuele bytes op een moment, dat we in plaats daarvan willen een stuk van bytes te krijgen. Dan een keer hebben we een stuk van bytes, dan zullen we schrijven het uit. Ook al heb je vragen er een te schrijven - en fwrite en fread doen hetzelfde soort dingen. Ze bufferen je leest en schrijft. Ook al heb je vragen om onmiddelijk te schrijven, zal het waarschijnlijk niet. En je kunt er niet zeker van dat de dingen zullen worden geschreven totdat u hfclose of wat het ook is, die dan zegt, oke, ik sluit mijn dossier, dat betekent dat ik maar beter schrijf alles wat ik nog niet geschreven. Het is niet nodig om alles uit te schrijven totdat u het sluiten van het bestand, en dan moet het. Dus dat is precies wat lui - het wacht totdat het moet gebeuren. Deze - neem 51 en je zult in het gaan in meer detail, omdat OCaml en alles in 51, alles is recursie. Er zijn geen iteratieve oplossingen in principe,. Alles is recursie, en lazy evaluatie zal belangrijk voor veel omstandigheden waar, als je niet lui te evalueren, zou dat betekenen - Het voorbeeld stromen, die oneindig lang. In theorie kunt u denken aan de natuurlijke getallen als een stroom van 1-2-3-4-5-6-7, Dus lui geëvalueerd dingen zijn prima. Als ik zeg dat ik wil dat de tiende nummer, dan kan ik tot evalueren om de tiende nummer. Als ik wil het honderdste nummer, dan kan ik tot evalueren om de honderdste nummer. Zonder lazy evaluatie, dan is het gaan proberen om onmiddellijk te evalueren alle nummers. Je evalueren van oneindig veel getallen, en dat is gewoon niet mogelijk. Dus er zijn veel omstandigheden waarin lazy evaluatie is gewoon van essentieel belang om het verkrijgen van dingen om te werken. 

Nu willen we insert schrijven waar insert gaat worden eveneens veranderen in de definitie ervan. Dus nu is het bool inzetstuk (int waarde). We gaan dat veranderen naar bool insert (int waarde, knoop * boom). We zijn eigenlijk gaat dat weer veranderen in een beetje, zullen we zien waarom. En laten we gaan build_node, alleen voor de deurklink van het, boven te plaatsen zodat we niet een functie prototype te schrijven. Dat is een hint dat je gaat worden met behulp van build_node in insert. Oke. Neem een ​​minuut voor. Ik denk dat ik gered van de herziening als je wilt trekken van dat, of, in ieder geval, ik heb nu. Ik wilde een lichte pauze om na te denken over de logica van insert, als je niet kunt denken. In principe, zal u alleen ooit het invoegen op bladeren. Zoals, als ik plaats 1, dan ga ik onvermijdelijk zal worden invoegen 1 - Ik zal wijzigen in zwart - Ik zal worden het plaatsen van een hier. Of als ik plaats 4, Ik wil graag het invoegen van 4 hier. Dus niet uit wat je doet, je gaat te plaatsen op een blad. Het enige wat je hoeft te doen is herhalen uit de boom totdat je bij het knooppunt dat moet het knooppunt ouder, de nieuwe node ouder te zijn, en wijzig de linker of rechter cursor naargelang Het is groter dan of kleiner dan het huidige knooppunt. Verandering die wijzer om te verwijzen naar uw nieuwe knooppunt. Dus herhalen de boom, maakt het blad verwijzen naar de nieuwe node. Denk ook aan waarom dat verbiedt de aard van de situatie voor, waar ik bouwde de binaire boom waar het was juist als je alleen maar gekeken naar een enkele knoop, maar 9 was aan de linkerkant van 7 als u herhaald helemaal naar beneden. Dus dat is onmogelijk in dit scenario, omdat - denk over het invoegen van 9 of iets, helemaal aan het eerste knooppunt, Ik ga tot en met 7 zien en ik ga gewoon naar rechts. Dus niet uit wat ik doe, als ik het invoegen door te gaan naar een blad, en een blad met de juiste algoritme, het gaat om het onmogelijk voor mij om 9 voegt u aan de linkerkant van 7 want zodra ik 7 raakte ik ga naar rechts. Heeft iemand iets om mee te beginnen? [Student] ik doe. >> Tuurlijk. [Student, onverstaanbaar] [Andere student, onverstaanbaar] [Bowden] Het is gewaardeerd. Oke. Wil je uitleggen? 

[Student] Omdat we weten dat we het plaatsen van nieuwe knooppunten aan het einde van de boom, Ik doorgelust de boom iteratief tot ik op een knooppunt dat wees op null. En toen besloot ik om ofwel zet het op de rechter-of de linkerkant van dit recht gebruik variabele, het zei me waar deze te plaatsen. En dan, in wezen, ik maakte dat laatste - dat temp knooppunt naar het nieuwe knooppunt dat het creëren, hetzij links of rechts, afhankelijk van de waarde gelijk. Tot slot wil ik u de nieuwe node waarde aan de waarde van de testen. [Bowden] Oke, dus ik zie hier een probleem. Dit is als 95% van de heenweg. Het enige probleem dat ik zie, nou ja, heeft iemand anders ziet een probleem? Wat is de omstandigheid waaronder zij uit te breken van de lus? [Student] Als temp null is? >> Ja. Dus hoe je uit te breken van de lus is als temp is null. Maar wat moet ik doen hier? Ik dereference temp, dat is onvermijdelijk null. Dus het andere wat je hoeft te doen is niet alleen bij te houden totdat temp null is, u wilt bijhouden van de moedermaatschappij te allen tijde. We hebben ook knoop * ouder willen, ik denk dat we kunnen die ervoor zorgen dat op nul op het eerste. Dit gaat raar gedrag voor de wortel van de boom, maar we krijgen dat. Als de waarde groter is dan wat dan ook, dan is temp = temp rechts. Maar voordat we dat doen, ouder = temp. Of zijn ouders altijd gaan om een ​​gelijke temp? Is dat het geval? Als temp niet null is, dan ga ik naar beneden, wat er ook gebeurt, een knooppunt waarvoor temp het ouder. Dus ouder gaat worden temp, en dan ga ik verhuizen temp beneden. Nu temp null is, maar ouder wijst op de ouder van het ding dat null is. Dus hier beneden, ik wil niet in te stellen rechts is gelijk aan 1. Dus ik naar rechts verplaatst, dus als rechts = 1, en ik denk dat je ook wilt doen - als u verhuist naar links, die u wilt instellen recht gelijk aan 0. Of anders als je ooit naar rechts te verplaatsen. Dus rechts = 0. Als rechts = 1, Nu willen we de ouders recht pointer newnode te maken, anders willen we de ouders linker pointer newnode te maken. Vragen over zeggen? Oke. Dus dit is de manier waarop we - nou ja, eigenlijk, in plaats van dit te doen, we half verwacht dat je build_node gebruiken. En dan, als newnode gelijk is aan null, false retourneren. Dat is dat. Nu, dit is wat we verwacht je te doen. 

Dit is wat de medewerkers oplossingen te doen. Ik ben het oneens met dit als de "juiste" manier te gaan over het maar dit is perfect in orde en het zal werken. Een ding dat is een beetje raar op dit moment is als de boom begint als null, passeren we in een null-boom. Ik denk dat het hangt af van hoe definieer je het gedrag van het passeren in een null-boom. Ik zou denken dat als je pas in een null-boom, dan het plaatsen van de waarde in een null boom moet gewoon terug een boom waar de enige waarde is dat enkel knooppunt. Hebben mensen het daarmee eens? Je zou, als je wilde, als je langs in een null-boom en u wilt een waarde in te voegen in het, return false. Het is aan jou om te bepalen dat. Om het eerste wat ik zei en dan doen - goed, je gaat om problemen om dat te doen hebben, omdat Het zou makkelijker zijn als we een globale pointer naar het ding, maar we weten niet, dus als boom is null, er is niets wat we kunnen doen over. We kunnen gewoon return false. Dus ik ga naar insert te veranderen. We technisch zou hier gewoon veranderen van dit recht, hoe het itereren over de dingen, maar ik ga insert te veranderen naar een knooppunt te nemen ** boom. Dubbele pointers. Wat betekent dit? In plaats van omgaan met verwijzingen naar knooppunten, het ding dat ik ga worden manipuleren is deze pointer. Ik ga te manipuleren deze pointer. Ik ga te manipuleren pointers direct. Dit is logisch aangezien, na te denken over down - goed, nu wijst dit op null. Wat ik wil doen is te manipuleren deze pointer te wijzen op niet null. Ik wil dat het wijzen op mijn nieuwe knooppunt. Als ik gewoon bijhouden van pointers naar mijn pointers, dan heb ik niet nodig om bij te houden van een ouder pointer. Ik kan gewoon bijhouden om te zien of de wijzer wijst naar null, en als de wijzer wijst naar null, wijzigen om te wijzen op het knooppunt ik wil. En ik kan veranderen want ik heb een verwijzing naar de aanwijzer. Laten we dit nu zien. Je kunt eigenlijk doen recursief vrij gemakkelijk. Willen we dat doen? Ja, we doen. 

Laten we recursief zien. Ten eerste, wat is ons basisscenario gaan worden? Bijna altijd ons basisscenario, maar eigenlijk is dit soort van lastig. First things first, if (boom == NULL) Ik denk dat we gaan gewoon om terug te keren vals. Dit is anders dan uw boom wordt null. Dit is de pointer naar je root pointer wordt null wat betekent dat je root pointer bestaat niet. Dus hier beneden, als ik dat doe knooppunt * - laten we deze opnieuw te gebruiken. Node * root = NULL, en dan ga ik naar insert oproepen door iets te doen, zoals, plaats 4 in & wortel. So & wortel, als root is een knooppunt * Vervolgens & wortel gaat worden een knooppunt **. Dit geldt. In dit geval boom hier, boom is niet null - of insert. Hier. Boom is niet nul; * boom is null, wat fijn is want als * boom is null, dan kan ik manipuleren Tot nu toe wijzen op wat ik wil dat het wijzen. Maar als boom is null, dat betekent dat ik net hier neer en zei: null. Dat is niet logisch. Ik kan niets doen met die. Als boom is null, false retourneren. Dus ik eigenlijk al gezegd wat onze echte basisscenario is. En wat is dat zal worden? [Student, onverstaanbaar] [Bowden] Ja. Dus als (* boom == NULL). Dit heeft betrekking op het geval hier waar als mijn rode wijzer is de pointer Ik ben gericht op, dus zoals ik ben gericht op deze wijzer, nu ben ik gericht op deze wijzer. Nu ben ik gericht op deze wijzer. Dus als mijn rode wijzer, dat is mijn knoop **, is ooit - als *, mijn rode wijzer, is altijd null, dat betekent dat ik op het geval dat ik mij op een pointer die verwijst - Dit is een pointer die behoort tot een blad. Ik wil deze pointer veranderen om te wijzen op mijn nieuwe knooppunt. Kom terug hier. Mijn newnode zal gewoon knooppunt * n = build_node (waarde) dan n, als n = NULL, return false. Wat we willen veranderen wat de aanwijzer op dit moment wijst naar Tot nu toe wijzen op onze nieuw gebouwde node. We kunnen eigenlijk doen dat hier. In plaats van te zeggen n, wij zeggen * boom = als * boom. Iedereen begrijpt dat? Dat door het omgaan met verwijzingen naar pointers, we kunnen veranderen null pointers te wijzen op dingen die we willen dat ze wijzen op. Dat is ons basisscenario. 

Nu onze recidief, of onze recursie, gaat worden zeer vergelijkbaar met alle andere recursies we hebben gedaan. We gaan willen waarde in te voegen, en nu ga ik om opnieuw te gebruiken ternair, maar wat is onze toestand gaat worden? Hoe is het we zoeken om te beslissen of we willen gaan links of rechts? Laten we het doen in afzonderlijke stappen. Als (waarde <) wat? [Student] De boom waarde? [Bowden] Dus herinner me dat ik op dit moment ben - [Studenten, onverstaanbaar] [Bowden] Ja, dus hier, laten we zeggen dat dit groene pijl is een voorbeeld van wat momenteel boom, is een aanwijzing voor deze pointer. Dus dat betekent dat ik ben een pointer naar een pointer naar 3. De dereference twee keer goed klonk. Wat moet ik - hoe doe ik dat? [Student] dereference een keer, en dan doen pijl die manier? [Bowden] Dus (* boom) is het dereference keer -> waarde gaat geven mij de waarde van de node die ik indirect ben wijst. Dus ik kan ook schrijven ** tree.value als u liever dat. Ofwel werkt. Als dat het geval is, dan wil ik bellen met waarde in te voegen. En wat is mijn bijgewerkte knooppunt ** gaat worden? Ik wil naar links, dus ** tree.left wordt mijn linkerhand. En ik wil de aanwijzer naar dat ding zodat als de linker eindigt in de null pointer, Ik kan het aanpassen om te verwijzen naar mijn nieuwe knooppunt. 

En het andere geval kunnen erg lijken. Laten we eigenlijk maken dat mijn ternaire nu. Steek waarde als de waarde <(** boom). Waarde. Dan willen we onze ** updaten naar links, wat we willen onze ** updaten naar rechts. [Student] Heeft de pointer die naar de pointer? [Bowden] Vergeet niet dat - ** tree.right is een knooppunt ster. [Student, onverstaanbaar] >> Ja. ** Tree.right is als deze pointer of iets dergelijks. Dus door het nemen van een pointer naar dat, dat geeft me wat ik wil van de pointer naar die kerel. [Student] Kunnen we nog eens herhalen waarom we met de twee pointers? [Bowden] Ja. Dus - nee, je kunt, en die oplossing voor was een manier om het te doen zonder te doen twee pointers. Je moet in staat zijn om te begrijpen met behulp van twee pointers, en dit is een schonere oplossing. Merk ook op dat, wat gebeurt er als mijn boom - wat gebeurt er als mijn root was null? Wat gebeurt er als ik dit geval hier? Dus knoop * root = NULL, plaats 4 in & wortel. Wat wortel gaat worden na dit? [Student, onverstaanbaar] >> Ja. Root waarde gaat worden 4. Root links gaat worden null is, wordt wortel recht gaat null zijn. In het geval dat we niet voorbij wortel op adres, we konden niet wijzigen wortel. In het geval waar de boom - waarbij root was null, we moesten om terug te keren vals. Er is niets wat we konden doen. We kunnen een knooppunt niet invoegen in een lege boom. Maar nu we kunnen, we gewoon een lege boom te maken in een een-knooppunt boom. Dat is meestal de verwachte manier waarop het zou moeten werken. 

Bovendien is dit aanzienlijk korter dan Ook het bijhouden van de ouder, en dus moet je herhalen helemaal naar beneden. Nu heb ik mijn ouders, en ik heb mijn ouders recht aanwijzer naar het wat dan ook. In plaats daarvan, als we dat dit iteratief, zou het hetzelfde idee met een lus while. Maar in plaats van dat te maken met mijn ouders wijzer, in plaats daarvan mijn huidige pointer zou de zaak zijn dat ik direct aanpassen om te verwijzen naar mijn nieuwe knooppunt. Ik heb niet te maken hebben met de vraag of het is dat naar links wijst. Ik heb niet te maken hebben met de vraag of het is naar rechts. Het is gewoon wat deze pointer is, ik ga in te stellen om te wijzen op mijn nieuwe knooppunt. Iedereen begrijpt hoe het werkt? Indien niet, waarom willen we het op deze manier, maar in ieder geval dat dit werkt als een oplossing? [Student] Waar we terug waar? [Bowden] Dat is waarschijnlijk hier. Als we op de juiste plaats hem terug waar. Else, hier beneden gaan we willen wat insert rendement terug te keren. 

En wat is speciaal aan deze recursieve functie? Het is staart recursieve, dus zolang we samen te stellen met een aantal optimalisatie, het zal erkennen dat en je zal een stack overflow nooit van dit, zelfs indien de boom een ​​hoogte van 10.000 of 10 miljoen. [Student, onverstaanbaar] [Bowden] Ik denk dat het doet het op Dash - of wat optimalisatie niveau is vereist voor een staart recursie wordt herkend. Ik denk dat het herkent - GCC en Clang Ook hebben verschillende betekenissen voor hun optimalisatie niveaus. Ik wil zeggen dat het DashO 2, zeker dat het zal staart recursie herkennen. Maar we - je zou kunnen bouwen als een Fibonocci voorbeeld of iets dergelijks. Het is niet gemakkelijk om te testen met dit, want het is moeilijk te bouwen om een binaire boom die is zo groot. Maar ja, ik denk dat het DashO 2, dat als je compileren met DashO 2, zal hij op zoek naar de staart recursie en het optimaliseren van dat uit. Laten we terug gaan naar - plaats is letterlijk het laatste wat het nodig heeft. Laten we terug gaan naar de insert hier waar gaan we hetzelfde idee te doen. Het zal nog steeds de fout van het niet kunnen om volledig te behandelen wanneer de root zelf null is, of het verleden vermelding is null, maar in plaats van het omgaan met een ouder wijzer, Laten we dezelfde logica van het houden van pointers van toepassing op pointers. Als hier houden we onze knooppunt ** huidig, en we hoeven niet bij te houden meer goed, maar knooppunt ** huidig ​​= & boom. En nu onze while lus gaat worden, terwijl * huidig ​​is niet gelijk aan nul. Heb geen behoefte om bij te houden van de ouders niet meer te houden. Hoeven niet bij te houden van links en rechts. En ik noem het temp, omdat we al gebruik van temp. Oke. Dus als (waarde> * temp), Vervolgens & (* temp) -> rechts anders temp = & (* temp) -> links. En nu, op dit punt, terwijl na deze lus, Ik doe dit omdat misschien is het makkelijker om na te denken over iteratief dan recursief, maar na deze while-lus, * Temp is de aanwijzer we willen veranderen. 

Voordat we hadden ouder, en we wilden een van de ouders links of ouder naar rechts te wijzigen, maar als we willen ouder recht te wijzigen, dan * temp is ouder recht, en we kunnen direct veranderen. Dus hier beneden, kunnen we doen * temp = newnode, en dat is het. Dus aankondiging, alles wat we deden in dit was het afsluiten van regels code. Om bij te houden van de moedermaatschappij in alles wat extra inspanning. Hier, als we gewoon spoor van de aanwijzer te houden om de aanwijzer, en zelfs als we wilden nu te ontdoen van al deze accolades, zodat het lijkt korter. Dit is nu precies dezelfde oplossing, maar minder regels code. Als je eenmaal begint herkennen dit als een geldige oplossing, het is ook makkelijker om te redeneren over dan op, oke, waarom ik deze vlag hebben op int toch? Wat betekent dat? Oh, het is aan te geven dat elke keer als ik ga rechts, ik moet het in te stellen, anders als ik ga linksaf Ik moet het op nul te zetten. Hier, ik heb geen reden om over dat, het is gewoon makkelijker om na te denken over. Vragen? [Student, onverstaanbaar] >> Ja. Oke, dus in het laatste stuk - Ik denk dat een snelle en makkelijke functie die we kunnen doen is, let's - samen, denk ik, probeer en schrijf een bevat de functie die niet uit of het een binaire zoekboom. Deze bevat functie moet true retourneren Als ergens in deze algemene binaire boom is de waarde die we zoeken. Dus laten we eerst recursief te doen en dan zullen we het iteratief te doen. We kunnen eigenlijk alleen maar het samen doen, want dit gaat echt kort. 

Wat is mijn basisscenario gaat worden? [Student, onverstaanbaar] [Bowden] Dus als (boom == NULL), wat dan? [Student] Terug vals. [Bowden] Else, nou ja, ik hoef het anders. Als was mijn andere base case. [Student] Tree waarde? >> Ja. Dus als (boom-> waarde == waarde. Merk op dat we weer terug bij knooppunt * niet, knoop ** s? Bevat zal nooit meer een knooppunt ** te gebruiken, omdat we niet wijzigen pointers. We zijn net doorkruisen ze. Als dat gebeurt, dan willen we return true. Else willen we de kinderen doorkruisen. Dus we kunnen niet redeneren over de vraag of alles naar links is minder en alles aan de rechterkant is groter. Dus wat is onze toestand gaat om hier te zijn - of, wat gaan we doen? [Student, onverstaanbaar] >> Ja. Return bevat (waarde, boom-> links) of bevat (waarde, boom-> rechts). En dat is het. En let er enige kortsluiting evaluatie, waar als we toevallig de waarde in de linker boom te vinden, we nooit moeten kijken naar de juiste boom. Dat is de hele functie. Nu laten we het doen iteratief, die zal minder leuk. We nemen de gebruikelijke start van knooppunt * huidig ​​= boom. Terwijl (huidig! = NULL). Snel naar een probleem te zien. Als huidig ​​- hier, als we ooit uit te breken van deze, dan hebben we opraken van de dingen om naar te kijken, dus return false. Als (huidig-> waarde == waarde), return true. Dus nu zijn we op een plek - we weten niet of we willen gaan naar links of rechts. Dus willekeurig, laten we gewoon gaan verlaten. Ik heb natuurlijk lopen in een probleem waar ik volledig heb opgegeven alles - Ik zal alleen maar Controleer de linkerkant van een boom. Ik zal nooit controleren alles wat een recht kind van alles. Hoe kan ik dit oplossen? [Student] Je moet weg van de linker en rechter houden in een stapel. [Bowden] Ja. Dus laten we het struct lijst, knooppunt * n, en dan knoop ** volgende stap? Ik denk dat werkt prima. We willen gaan over de linker, of let's - hier. Struct lijst list =, zal het beginnen met uit bij deze struct lijst. * List = NULL. Dus dat gaat ons gelinkte lijst te zijn van substructuren die we hebben overgeslagen. We gaan nu Traverse links, maar omdat we onvermijdelijk terug hoeft te komen aan het recht, We gaan de goede kant binnen te houden van onze struct lijst. Dan hebben we new_list of struct, struct lijst *, new_list = malloc (sizeof (lijst)). Ik ga om te negeren foutcontrole dat, maar je moet controleren als het null zien. New_list het knooppunt dat het gaat om te wijzen op - oh, dat is waarom ik wilde het hier. Het zal wijzen op een tweede struct lijst. Dat is gewoon hoe gelinkte lijsten werken. Dit is hetzelfde als een verbonden lijst int behalve dat we gewoon te vervangen int met node *. Het is precies hetzelfde. Dus new_list, de waarde van onze new_list knooppunt, gaat worden cur-> rechts. De waarde van onze new_list-> volgende gaat onze oorspronkelijke lijst te zijn, en dan gaan we onze lijst bij te werken om te wijzen op new_list. 

Nu moeten we een soort van manier zijn om dingen, zoals we hebben doorkruist de hele linker deelboom. Nu moeten we dingen te trekken uit het, zoals huidig ​​is null, we willen niet alleen return false. We willen nu buiten te trekken in onze nieuwe lijst. Een handige manier om dit te doen - nou ja, eigenlijk is er meerdere manieren om dit te doen. Iemand een suggestie? Waar moet ik dit doen of hoe moet ik dit doen? We hebben maar een paar minuten, maar het even welke suggesties? In plaats van - een manier plaats van onze voorwaarde is, terwijl wat we momenteel op zoek naar niet null is, in plaats daarvan gaan we verder te gaan tot onze lijst zelf is null. Dus als onze lijst eindigt als null, dan hebben we uitgeput van dingen te zoeken, om te zoeken over. Maar dat betekent dat het eerste wat in onze lijst slechts gaat om het eerste knooppunt zijn. Het allereerste wat zal zijn - we niet meer nodig om dat te zien. Dus list-> n zal onze boom. list-> volgende gaat worden null. En nu, terwijl de lijst is niet gelijk aan nul. Cur gaat iets te trekken uit onze lijst. Dus huidig ​​gaat gelijk list-> n. En dan de lijst gaat gelijk list-> n, of de lijst-> volgende. Dus als huidig ​​waarde is gelijk aan waarde. Nu kunnen we toevoegen zowel ons recht aanwijzer en onze linker pointer zolang ze niet null zijn. Hier beneden, ik denk dat we moeten dat hebben gedaan in de eerste plaats. Als (huidig-> rechts! = NULL) dan gaan we die knoop te voegen aan onze lijst. Als (huidig-> links), dit is een beetje extra werk, maar het is prima. Als (huidig-> links! = NULL), en we gaan naar links in te voegen in onze verbonden lijst, en dat moet het. We herhalen - zolang we iets in onze lijst, we hebben een ander knooppunt naar te kijken. Dus we kijken naar dat knooppunt, we vooraf onze lijst naar de volgende. Als dat knooppunt is de waarde die we zoeken, kunnen we return true. Else plaatst zowel onze links en rechts substructuren, zolang ze niet null zijn, aan onze lijst zodat we onvermijdelijk gaan over hen. Dus als ze niet null, als onze wortel wijzer wees naar twee dingen, dan we in eerste instantie trok iets uit zodat onze lijst eindigt als null. En dan zetten we twee dingen terug in, dus nu onze lijst is van maat 2. Dan gaan we naar lus een back-up en we gaan gewoon te trekken, laten we zeggen, de linker wijzer van onze root node. En dat zal gewoon blijven gebeuren, we zullen uiteindelijk een lus over alles. 

Merk op dat dit aanzienlijk gecompliceerder in de recursieve oplossing. En ik heb gezegd meerdere keren de recursieve oplossing gewoonlijk veel gemeen met de iteratieve oplossing. Hier dit is precies wat de recursieve oplossing aan het doen is. De enige verandering is dat in plaats van impliciet gebruik van de stapel, het programma stack, als uw manier van het bijhouden van wat knooppunten moet je nog om te bezoeken, nu moet je expliciet gebruik van een gelinkte lijst. In beide gevallen bent u het bijhouden van wat knooppunt nog moet worden bezocht. In het recursieve geval het is gewoon makkelijker, omdat een stapel is geïmplementeerd voor u als het programma stack. Merk op dat deze verbonden lijst is een stapel. Wat we gewoon op de stapel gelegd is meteen wat we gaan te trekken uit de stapel naar de volgende te bezoeken. We hebben geen tijd meer, maar vragen? [Student, onverstaanbaar] [Bowden] Ja. Dus als we onze gekoppelde lijst, stroom gaat verwijzen naar deze man, en nu zijn we gewoon het bevorderen van onze gelinkte lijst te richten op deze kerel. We doorkruisen boven het gekoppelde lijst in die lijn. En dan denk ik dat we moeten onze gelinkte lijst en dat soort dingen vrij een keer voordat hij terugkeerde waar of onwaar, moeten we itereren over onze gelinkte lijst en altijd hier beneden, denk ik, Als we huidig ​​recht is niet gelijk aan, toevoegen, dus nu willen we bevrijden huidig ​​omdat, nou ja, hebben we helemaal vergeten over de lijst? Ja. Dus dat is wat we willen doen hier. Waar is de pointer? Cur was toen - we willen een struct lijst * 10 gelijk is aan de lijst volgende. Vrije lijst, list = temp. En in het geval waar we true retourneren, moeten we herhalen over de rest van ons gelinkte lijst bevrijden dingen. Het leuke van de recursieve oplossing is het vrijmaken van zaken betekent gewoon knallen factorings uit de stapel die zal gebeuren voor je. Dus we zijn gegaan van iets dat is net als 3 regels van hard-to-denken-over-code om iets dat is aanzienlijk veel meer hard-aan-denken-over regels code. Nog meer vragen? Oke. We zijn goed. Bye! [CS50.TV]