[Powered by Google Translate] [Artikel 7: Meer Gerieflik] [Rob Bowden] [Harvard Universiteit] [Hierdie is CS50] [CS50.TV] Alles reg. So soos ek gesê het in my e-pos, dit gaan om 'n binêre-boom-intensiewe afdeling. Maar daar is nie so baie vrae. So ons gaan om te probeer en te trek uit elke vraag en gaan in pynlike detail van al die beste maniere om dinge te doen. So reg aan die begin, ons gaan deur monster tekeninge van binêre bome en stuff. So hier is, "Onthou dat 'n binêre boom nodes soortgelyk aan dié van 'n geskakelde lys, behalwe in plaas van een wyser is daar twee: een vir die linkerkant se kind " en een vir die reg om 'kind'. " So 'n binêre boom is net soos 'n geskakelde lys, behalwe die struct gaan twee wysers te hê. Daar is trinary bome, wat gaan drie verwysings na, daar is 'n N-êre bome, wat net 'n generiese wyser wat jy dan hoef te malloc groot genoeg wees om genoeg verwysings na al die moontlike kinders. So binêre boom gebeur net 'n konstante aantal van twee te hê. As jy wil, kan jy 'n geskakelde lys as 'n Unêre boom, maar ek dink nie enige iemand noem dit dat. "Teken 'n bokse en pyle diagram van 'n binêre boom node met Nate se gunsteling nommer, 7, waar elke kind pointer null. " So iPad af. 

Dit gaan redelik eenvoudig te wees. Ons het net gaan om 'n node te hê, sal ek dit teken as 'n vierkant. En ek sal teken die waardes hier. Sodat die waarde gaan in hier, en dan hier af sal ons die linker muis aan die linkerkant en die regte wyser aan die regterkant. En dit is baie so konvensie noem dit links en regs die wyser name. Beide van hierdie gaan wees null. Dit sal net null, en dit sal wees net null. Okay. So terug hier. "Met 'n geskakelde lys, ons het net 'n wyser te stoor na die eerste nodus in die lys om die hele geskakelde lys om te onthou, of die hele lys. Net so, met bome, ons het net 'n wyser te stoor aan 'n enkele nodus in om die hele boom om te onthou. Hierdie knoop is calle die "wortel" van die boom. Bou op jou diagram voor of teken 'n nuwe een van so 'n aard dat jy 'n blok-en-pyle uitbeelding van 'n binêre boom met die waarde 7, dan 3 in die linkerkant, dan 9 aan die regterkant, en dan 6 op die reg van die 3. " Kom ons kyk of ek kan onthou al wat in my kop. So dit gaan ons wortel hier te wees. Ons sal 'n wyser iewers, iets wat ons sal noem wortel, en dit is wat verwys na hierdie man. Nou 'n nuwe node te maak, Wat moet ons doen, 3 aan die linkerkant? So 'n nuwe nodus met 3, en dit wys aanvanklik null. Ek sal net sit N. Nou wil ons wat gaan aan die linkerkant van 7. Sodat ons verander die wyser nou verwys na hierdie man. En ons doen dieselfde. Ons wil 'n 9 hier wat sê aanvanklik net null. Ons gaan hierdie pointer, punt te verander na 9, en nou wil ons 6 te sit aan die regterkant van 3. So dit gaan - maak 'n 6. En dat die man daar sal wys. Okay. So dis al wat dit vra om te doen. 

Nou, laat ons gaan oor 'n paar terminologie. Ons het reeds gepraat oor hoe die wortel van die boom is die top-mees nodus in die boom. Die een wat 7. Die nodes aan die onderkant van die boom word genoem die blare. Enige node wat net null as sy kinders is 'n blaar. So dit is moontlik, as ons binêre boom is net 'n enkele nodus, dat 'n boom is 'n blaar, en dit is dit. "Die hoogte van die boom is die getal van hoep wat jy het om te maak van die top na 'n blaar te kry. " Ons kry in 'n tweede, die verskil tussen gebalanseerde en ongebalanseerde binêre bome, maar vir nou, die totale hoogte van hierdie boom Ek sou sê, is 3, maar as jy die getal van hoep wat jy moet maak in orde te kry tot 9, dan is dit eintlik net 'n hoogte van 2. Reg nou is dit 'n ongebalanseerde binêre boom, maar ons sal gepraat oor gebalanseer wanneer dit kry om relevant te wees. So nou kan ons praat oor nodes in 'n boom in terme relatief tot die ander nodes in die boom. So nou het ons ouers, kinders, broers en susters, voorouers en nageslag. Hulle is redelik gesonde verstand, wat dit beteken. As ons vra - se ouers. So, wat is die ouer van 3? [Studente] 7. >> Ja. Die ouer is net gaan om te wees wat aan jou wys. Dan wat is die kinders van 7? [Studente] 3 en 9. >> Ja. Let daarop dat "kinders" beteken letterlik kinders, so 6 sal nie van toepassing nie, want dit is soos 'n kleinkind. Maar dan as ons nageslag, so wat is die afstammelinge van 7? [Studente] 3, 6 en 9. >> Ja. Die afstammelinge van die wortel node gaan word alles in die boom, behalwe miskien die wortel node self, as jy nie wil hê dat 'n afstammeling te oorweeg. En laastens, voorouers, so dit is die teenoorgestelde rigting. So, wat is die voorouers van 6? [Studente] 3 en 7. >> Ja. 9 is nie ingesluit nie. Dis net die direkte linie terug na die wortel gaan julle voorvaders te wees. 

"Ons sê dat 'n binêre boom is" beveel "as vir elke nodus in die boom, al sy afstammelinge aan die linkerkant mindere waardes en al van die kinders aan die regterkant het 'n groter waardes. Byvoorbeeld, is die boom hierbo bestel maar dit is nie die enigste moontlike bestel reëling. " Voordat ons dat, 'n geordende binêre boom is ook bekend as 'n binêre soekboom. Hier is ons gebeur noem dit 'n geordende binêre boom, maar ek het dit nog nooit gehoor het 'n geordende binêre boom voor, en op 'n quiz ons is baie meer geneig binêre soekboom te sit. Hulle is een en dieselfde, en dit is belangrik dat jy erken die onderskeid tussen binêre boom en binêre soekboom. 'N binêre boom is net 'n boom wat aan twee dinge. Elke node wys twee dinge. Daar is geen redenasie oor die waardes wat dit dui op. Dus, net soos hier, want dit is 'n binêre soekboom, ons weet dat as ons gaan links van 7, dan al die waardes wat ons kan bereik deur te gaan links van 7 tot minder as 7. Let op dat al die waardes van minder as 7 is 3 en 6. Dit is alles aan die linkerkant van 7. As ons na die reg van 7, alles het meer as 7, so 9 is aan die reg van 7, so ons is goed. Dit is nie die geval vir 'n binêre boom, vir 'n gereelde binêre boom kan net 3 aan die bokant, 7 aan die linkerkant, 9 aan die linkerkant van 7, is daar geen ordening van waardes hoegenaamd. Nou, sal ons nie eintlik dit doen, want dit is 'n vervelige en onnodige, maar probeer om soveel bestel bome te trek as wat jy kan dink deur gebruik te maak van die nommers 7, 3, 9, en 6. Hoeveel duidelike reëlings is daar? Wat is die hoogte van elke een? " 

Ons sal 'n paar doen nie, maar die hoofgedagte is, Dit is in geen manier om 'n unieke voorstelling van 'n binêre boom met hierdie waardes. Al wat ons nodig het, is sommige binêre boom wat met 7, 3, 6, en 9. Nog 'n moontlike geldige een sou wees die wortel 3, gaan aan die linkerkant, en dit is 6, gaan aan die linkerkant, en dit is 7, gaan na die linker-en dit is 9. Dit is 'n perfek geldige binêre soekboom. Dit is nie baie nuttig, want dit is net soos 'n geskakelde lys en al van hierdie wenke is net null. Maar dit is 'n geldige boom. Ja? [Studente] nie die waardes groter wees aan die regterkant? Of is dit? >> Hierdie ek bedoel die ander manier om te gaan. Daar is ook - ja, laat se skakelaar wat. 9, 7, 6, 3. Goeie vangs. Dit het nog steeds om gehoorsaam te wees aan wat 'n binêre boom soek veronderstel is om te doen. So alles aan die linkerkant het minder wees as enige gegewe node. Ons kan net beweeg, sê, hierdie 6 en sit dit hier. Nee, ons kan nie. Hoekom hou ek om dit te doen? Kom ons doen - hier is 6, 7, 6 punte tot 3. Dit is nog steeds 'n geldige binêre soekboom. Wat is verkeerd as ek - laat ons sien of ek kan kom met 'n reëling. Ja, okay. So, wat is verkeerd met hierdie boom? Ek dink ek het reeds aan julle gegee het 'n wenk dat daar is iets fout met dit. Hoekom hou ek om dit te doen? Okay. Dit lyk redelik. As ons kyk by elke node, soos 7, dan na die linkerkant van 7 is 'n 3. So ons het 3, die ding aan die regterkant van 3 is 'n 6. En as jy kyk die ding aan die regterkant van die 6 op 6, is 'n 9. So hoekom is dit nie 'n geldige binêre soekboom? [Studente] 9 is nog steeds aan die linkerkant van 7. >> Ja. Dit moet waar wees dat alle waardes wat jy kan bereik deur te gaan na die linkerkant van 7 is minder as 7. As ons gaan links van 7, kry ons 3 en ons kan nog steeds tot 6, kan ons nog steeds tot 9, maar deur hulle het gegaan en minder as 7, moet ons nie in staat wees om te kry om 'n getal wat groter as 7. Dit is dus nie 'n geldige binêre soekboom. 

My broer eintlik het 'n onderhoud vraag dit was basies net kode up iets te valideer of 'n boom is 'n binêre soekboom, en so die eerste ding wat hy gedoen het was net kyk om te sien indien die linker en regter korrek is, en dan itereer daar. Maar jy kan nie net doen wat, jy het om tred te hou van die feit dat dit nou dat ek weg is links van 7, moet alles in hierdie boomstruktuur inskuif nie minder as 7. Die korrekte algoritme nodig het om tred te hou van die grense wat die waardes moontlik kan val. Ons sal nie deur almal van hulle. Daar is 'n mooi herhaling Betrokkenheid, alhoewel ons nog nie gekry het aan diegene, of sal ons nie vir diegene, definieer hoeveel daar werklik is. So daar is 14 van hulle. Die idee van hoe jy dit sou doen is wiskundig soos, jy kan enige een kies aan die wortel node wees, en dan as ek pluk 7 aan die wortel node wees, dan is daar, sê, 'n paar nommers wat kan gaan my linker node, en daar is 'n paar nommers wat kan my regter node, maar as ek n totaal getalle, dan is die bedrag wat aan die linkerkant kan gaan plus die bedrag wat gaan aan die regterkant N - 1. So van die oorblywende getalle, moet hulle in staat wees om te gaan na die linker-of die regterkant. Dit lyk moeilik dat, as ek 3 eerste dan alles het om te gaan na die linkerkant, maar as ek 7, dan 'n paar dinge kan gaan die linker en 'n paar dinge kan gaan aan die regterkant. En deur die '3 eerste "ek bedoel alles kan gaan aan die regterkant. Dit is regtig, jy hoef net te dink oor dit, hoe baie dinge kan gaan op die volgende vlak van die boom. En dit kom te wees 14, of jy kan trek almal van hulle, en dan sal jy kry 14. 

Gaan terug hier, "Gelas binêre bome is cool omdat ons deur hulle kan soek in 'n soortgelyke manier om oor 'n gesorteerde skikking te soek. Om dit te doen, het ons begin by die wortel en werk ons ​​pad die boom af teenoor blare, die nagaan van elke node se waardes teen die waardes wat ons op soek is na. As die huidige node se waarde is minder as die waarde wat ons soek, jy gaan langs die node se reg kind. Anders gaan jy na die node se linker kind. Op 'n sekere punt, sal jy óf die waarde wat jy op soek is na, of jy loop in 'n null, wat die waarde is nie in die boom. " Ek het die boom wat ons gehad het voordat te teken, wat sal 'n tweede. Maar ons wil om te kyk of 6, 10 en 1 in die boom. So wat dit was, 7, 9, 3, 6. Okay. Die nommers wat jy wil om te kyk, ons wil om te kyk 6. Hoe werk hierdie algoritme werk? Wel, ons het ook 'n paar wortel wyser na ons boom. En ons sal gaan na die wortel en sê, is hierdie waarde gelyk is aan die waarde wat ons op soek is na? So ons is op soek na 6, so dit is nie gelyk nie. So hou ons gaan, en nou is ons sê, okay, so 6 is minder as 7. Beteken dit dat ons wil om te gaan na die linkerkant, of wil ons gaan aan die regterkant? [Studente] links. >> Ja. Dit is aansienlik makliker, is al wat jy hoef te doen, trek een moontlike node van die boom en dan moet jy moenie - in plaas van probeer om te dink in jou kop, okay, as dit is minder, gaan ek aan die linkerkant of die regterkant, net te kyk na hierdie foto, dit is baie duidelik dat ek het om te gaan aan die linkerkant indien hierdie node is groter as die waarde wat ek soek. So gaan jy na links, nou is ek op 3. Ek wil - 3 is minder as die waarde wat ek soek, wat is 6. So gaan ons aan die regterkant, en nou het ek uiteindelik op 6, wat is die waarde wat ek soek, sodat ek terugkeer ware. Die volgende waarde wat ek gaan om te kyk vir is 10. Okay. So 10, nou is, gaan - uitroei dat - gaan om die wortel te volg. Nou, is 10 gaan wees meer as 7, so ek wil om te kyk na die regterkant. Ek gaan om hier te kom, 10 gaan wees groter as 9, so ek gaan om te wil om te kyk na die reg. Ek kom hier, maar hier nou is ek by null. Wat doen ek as ek getref null? [Studente] Terug vals? >> Ja. Ek het dit nie vind 10. 1 gaan na 'n byna identiese geval te wees, behalwe dit is net gaan word omgekeer, in plaas van op soek die regte kant af, ek gaan om te kyk af aan die linkerkant. 

Nou dink ek ons ​​eintlik kry die kode. Hier is waar - die CS50 toestel oopmaak en opgevolg jou pad daar, maar jy kan ook net dit doen in die ruimte. Dit is waarskynlik ideaal om dit te doen in die ruimte, want ons kan werk in die ruimte. "Eers moet ons sal moet 'n nuwe soort definisie vir 'n binêre boom node bevat int waardes. Met behulp van die boiler typedef hieronder, die skep van 'n nuwe soort definisie vir 'n nodus in 'n binêre boom. As jy vashaak. . . "Blah, blah, blah. Okay. So laat ons die boiler hier, typedef struct node, en node. Ja, okay. So, wat is die velde wat ons gaan in ons node wil? [Studente] Int en dan twee wysers? >> Int waarde, twee wysers? Hoe skryf ek die verwysings? [Studente] struct. >> Ek moet zoom. Ja, so struct node * links, en struct node * reg. En onthou die bespreking van die laaste tyd, dat dit maak nie sin nie, dit maak nie sin nie, dit maak nie sin nie. Jy moet alles wat daar in om hierdie rekursiewe struct te definieer. Okay, so dit is wat ons boom gaan lyk. As ons het 'n trinary boom, dan kan 'n nodus lyk B1, B2, struct node * b3, waar b 'n tak - eintlik, het meer ek dit hoor links, middel, regs, maar alles. Ons het net oor binêre, regs, links. "Nou is 'n globale node * veranderlike verklaar vir die wortel van die boom." So ons is nie van plan om dit te doen. Ten einde te maak dinge 'n bietjie meer moeilik en meer algemene, sal ons nie 'n globale node veranderlike. In plaas daarvan, in die hoof sal ons al ons node dinge verklaar, en dit beteken dat hieronder, wanneer ons begin loop ons bevat funksie en ons insert funksie, in plaas van ons bevat funksioneer net die gebruik van hierdie globale node veranderlike, gaan ons dit as 'n argument om die boom wat ons wil hê om dit te verwerk. Met die globale veranderlike is veronderstel om dinge makliker te maak. Ons gaan maak dinge moeiliker. Nou neem 'n minuut of so om net te doen hierdie soort van ding, waar binnekant van die belangrikste wat jy wil om hierdie boom te skep, en dit is al wat jy wil doen. Probeer en konstrueer hierdie boom in jou hooffunksie. 

Okay. So jy hoef nie eens die boom gebou het nog die hele manier. Maar iemand het iets wat ek kan trek om aan te toon hoe 'n mens kan begin die bou van so 'n boom? [Studente] Iemand se gebons, probeer om uit te kry. [Bowden] Enigeen gemaklik met hul boom konstruksie? [Studente] Sure. Dit is nie gedoen nie. >> Dit is fyn. Ons kan net klaar - oh, kan jy dit stoor? Hoera. So hier is ons het - oh, ek is effens sny af. Ek vergrote? Zoom in, blaai. >> Ek het 'n vraag. >> Ja? [Studente] Wanneer jy definieer struct, is dinge soos geïnisialiseer aan enigiets? [Bowden] No >> Goed. So jy wil hê om te inisialiseer - [Bowden] Nr Wanneer jy definieer, of wanneer jy verklaar struct dit is nie geïnisialiseer nie by verstek; dit is net soos as jy 'n int verklaar. Dit is presies dieselfde ding. Dit is soos elkeen van sy individuele velde kan 'n gemors waarde in dit. >> En is dit moontlik om te definieer of te verklaar struct hulle in 'n manier dat dit nie inisialiseer? [Bowden] Ja. So, kortpad inisialisering sintaksis gaan lyk - Daar is twee maniere waarop ons dit kan doen. Ek dink ons ​​moet dit stel om seker te maak dat kletteren doen dit ook. Die volgorde van die argumente wat kom in die struct, jy sit as die volgorde van argumente binnekant van hierdie kode tussen krulhakies. So as jy wil om dit te inisialiseer tot 9 en links van nul en dan null, dit sou wees 9, null, null. Die alternatief is, en die redakteur nie graag hierdie sintaksis, en dit dink ek wil 'n nuwe blok, maar die alternatief is iets soos - hier, ek sit dit op 'n nuwe reël. Kan jy uitdruklik sê, ek vergeet die presiese sintaksis. So kan jy uitdruklik spreek hulle by die naam, en sê: C, of ​​waarde. = 9, links = NULL. Ek vermoed hierdie behoefte te wees kommas. Regs = NULL, so hierdie manier waarop jy dit nie doen nie werklik nodig het om te weet van die orde van die struct, en wanneer jy dit te lees, dit is baie meer eksplisiet oor wat die waarde is geïnisialiseer. 

Dit gebeur om te wees een van die dinge wat - Dus, vir die grootste deel, C + + is 'n superstel van C. Jy kan C-kode, beweeg dit oor C + +, en dit moet stel. Dit is een van die dinge wat C + + ondersteun nie, sodat mense is geneig om dit nie te doen nie. Ek weet nie of dit is die enigste rede waarom mense is geneig om dit nie te doen nie, maar die geval waar ek nodig het om dit te gebruik wat nodig is om te werk met C + + en so ek kon nie gebruik van hierdie. Nog 'n voorbeeld van iets wat nie werk nie met C + + is hoe malloc terug 'n "void *," tegnies, maar jy kan net sê char * x = malloc wat ook al, en dit sal outomaties gewerp te word 'n char *. Dat outomatiese cast gebeur nie in C + +. Dit sou nie saamstel, en jy sal uitdruklik nodig om te sê char *, malloc, wat ook al, om dit te gooi na 'n char *. Daar is baie dinge dat C en C + + nie eens op nie, maar dit is twee. So ons gaan met hierdie sintaksis. Maar selfs as ons nie gaan met daardie sintaksis, wat kan fout wees met hierdie? [Studente] Ek hoef nie te dereference dit? >> Ja. Onthou dat die pyl het 'n implisiete dereference, en so wanneer ons net die hantering van 'n struct, ons wil gebruik. te kry op 'n veld binnekant van die struct. En die enigste keer wat ons gebruik pyltjie wanneer ons wil doen - goed, arrow is gelykstaande aan - dit is wat dit sou beteken het as wat ek gebruik pyl. Alle arrow middel dereference hierdie, nou is ek op 'n struct, en ek kan die veld kry. Óf die veld kry direk of dereference en kry die veld - Ek dink hierdie waarde moet wees. Maar hier is ek doen met net 'n struct, nie 'n wyser na 'n struct, en daarom kan ek nie gebruik maak van die pyl. Maar hierdie soort van ding wat ons kan doen vir al die nodes. Oh my God. Dit is 6, 7 en 3. Dan kan ons die opstel van die takke in ons boom, kan ons 7 - ons kan die linkerkant het, moet wys tot 3. So, hoe doen ons dit? [Studente, onverstaanbare] >> Ja. Die adres van node3, en as jy nie het adres, dan is dit sou net nie saam te stel. Maar onthou dat hierdie verwysings na die volgende nodes. Die reg behoort te wys 9, en 3 moet wys op die reg tot 6. Ek dink dit is al te stel. Enige vrae of kommentaar? [Student, onverstaanbaar] Die wortel gaan wees 7. Ons kan net sê node * ptr = of wortel, = & node7. 

Vir ons doeleindes, ons gaan om te word wat met insert, so ons gaan om te wil om te skryf van 'n funksie te voeg in hierdie binêre boom en voeg is onvermydelik gaan malloc te roep om 'n nuwe node vir hierdie boom te skep. So dinge gaan kry 'n slag met die feit dat 'n paar nodes is tans op die stapel en ander nodes gaan eindig op die hoop wanneer ons dit plaas. Dit is heeltemal geldig, maar die enigste rede ons is in staat om dit te doen op die stapel is omdat dit so 'n slinks voorbeeld wat ons ken die boom veronderstel is om te word gebou as 7, 3, 6, 9. As ons dit nie het nie, dan sou ons nie 'malloc in die eerste plek. Soos ons sal 'n bietjie later sien, moet ons malloc'ing word. Nou is dit heel redelik op die stapel te plaas, maar laat ons dit verander na 'n malloc implementering. So elkeen van hierdie gaan nou iets soos node * node9 = malloc (sizeof (node)). En nou gaan ons ons check te doen. if (node9 == null) - ek wou nie hê dat - terug 1, en dan kan ons doen node9-> want nou is dit 'n wyser, waarde = 6, node9-> links = NULL, node9-> regs = NULL, en ons gaan te hê om dit te doen vir elk van dié nodes. So in plaas daarvan, laat ons dit binnekant van 'n aparte funksie. Kom ons noem dit node * build_node, en dit is ietwat soortgelyk aan die API's bied ons vir Huffman kodering. Ons gee jy initializer funksies vir 'n boom en deconstructor "funksies" vir die bome en die dieselfde vir woude. 

So hier gaan ons 'n initializer funksie te hê om net die bou van 'n node vir ons. En dit gaan pretty much lyk presies soos hierdie. En ek gaan selfs om lui te wees en nie verander nie die naam van die veranderlike, selfs al node9 maak geen sin nie. O, ek dink node9 se waarde moet nie gewees het 6. Nou kan ons terugkeer node9. En hier moet ons terugkeer null. Almal saam op dat die Build-a-node funksie? So ons kan nou net noem dat enige node met 'n gegewe waarde en null pointers te bou. Nou het ons dit kan noem, kan ons node * node9 = build_node (9). En laat ons dit doen. . . 6, 3, 7, 6, 3, 7. En nou wil ons die opstel van die dieselfde pointers, behalwe nou alles is reeds in terme van verwysings so hoef nie meer die adres van. Okay. So, wat is die laaste ding wat ek wil doen? Daar is 'n fout kontrole dat ek nie doen nie. Wat beteken node terugkeer bou? [Student, onverstaanbaar] >> Ja. As malloc het misluk, sal dit terugkeer null. So ek gaan te lui sit dit neer hier in plaas van die doen van 'n voorwaarde vir elkeen. As (node9 == NULL, of - selfs eenvoudiger, dit is gelykstaande aan net indien nie node9. So indien nie node9, of nie node6, of nie node3, of nie node7, terug 1. Miskien moet ons druk malloc het misluk, of iets. [Studente] vals is gelyk aan sowel nul? [Bowden] Enige nul waarde is vals. So null is 'n nul waarde. Zero is 'n nul waarde. Vals is 'n nul waarde. Enige - pretty much die enigste 2 nul waardes is van nul en nul, vals is net hash gedefinieer as nul. Dit geld ook as ons globale veranderlike verklaar. As ons node * wortel het tot hier, dan - die nice ding oor globale veranderlikes is dat hulle altyd 'n aanvanklike waarde. Dis nie waar nie van funksies, hoe binnekant van hier, as ons, soos, node * of node x. Ons het geen idee wat x.value, x.whatever, of ons kan druk hulle en hulle kan willekeurig wees. Dis nie waar nie van globale veranderlikes. So node wortel of node x. By verstek, alles wat wêreldwye, indien nie uitdruklik geïnisialiseer tot 'n sekere waarde, het 'n nul waarde as die waarde daarvan. So hier is, node * wortel, het ons nie uitdruklik inisialiseer enigiets, so sal sy verstek waarde van nul, wat is die nul waarde van wysers. Die standaard waarde van x is gaan om te beteken dat x.value is nul, x.left is van nul en x.right is van nul. So, aangesien dit 'n struct, sal al die velde van die struct nul waardes. Ons hoef nie hier gebruik, al is. [Studente] Die structs is anders as ander veranderlikes, en die ander veranderlikes vullis waardes, dit is nulle? [Bowden] ander waardes ook. So in x, x nul wees. As dit op wêreldwye omvang, dit het 'n aanvanklike waarde. >> Goed. [Bowden] Óf die aanvanklike waarde jy het dit of nul. Ek dink wat sorg van al hierdie. 

Okay. Sodat die volgende deel van die vraag vra, "Nou wil ons 'n funksie met die naam bevat te skryf met 'n prototipe van Bool int waarde bevat. " Ons is nie van plan om te doen Bool bevat int waarde. Ons prototipe gaan lyk Bool bevat (int waarde. En dan is ons ook gaan om die boom te slaag dat dit moet beheer word om te sien of dit dat die waarde. So node * boom). Okay. En dan kan ons noem dit met iets soos, miskien sal ons wil printf of iets. Bevat 6, ons wortel. Dit moet terugkeer, of waar, terwyl bevat 5 wortel moet terugkeer vals. So neem 'n tweede om dit te implementeer. Jy kan dit doen óf iteratief of rekursief. Die nice ding oor die manier waarop ons het dinge op wat dit leen hom tot ons rekursiewe oplossing baie makliker as die globale veranderlike manier gedoen het. Want as ons net int waarde bevat, dan het ons geen manier van recursing subtrees. Ons wil hê dat 'n aparte helper funksie wat recurses die subtrees vir ons te hê. Maar vandat ons het dit verander om die boom te neem as 'n argument, wat dit moet altyd in die eerste plek gewees het, nou kan ons recursief makliker. So iteratiewe of rekursiewe, sal ons gaan oor beide, maar ons sal sien dat die rekursiewe eindig baie maklik. Okay. Is daar iemand het iets wat ons kan werk met? 

[Studente] Ek het 'n iteratiewe oplossing. >> Alle reg, iteratiewe. Goed, dit lyk goed. So, wil ons om te wandel deur dit? [Studente] Sure. So het ek 'n temp veranderlike Die eerste nodus van die boom te kry. En dan het ek net Looped deur terwyl temp nie gelyk aan nul, Dus, terwyl was nog in die boom, dink ek. En as die waarde is gelyk aan die waarde wat temp wys, dan is dit terug daardie waarde. Andersins, dit kontroleer of dit as dit is aan die regterkant of die linkerkant. As jy al ooit 'n situasie waar daar is nie meer boom, dan is dit terug - dit uitgange die lus en terugkeer vals. [Bowden] Goed. So dit lyk goed. Enigeen het enige kommentaar op enigiets? Ek het geen die korrektheid kommentaar at all. Die een ding wat ons kan doen, is hierdie man. Ag, gaan dit 'n bietjie langerige om te gaan. Ek sal regmaak wat up. Okay. 

Almal moet onthou hoe drieledige werk. Daar het beslis in die verlede is vasvrae wat gee jou 'n funksie met 'n drieledige operateur, en sê, te vertaal, iets te doen wat nie drieledige gebruik. So, dit is 'n baie algemene geval van wanneer ek sou dink drieledige te gebruik, waar as sommige toestand 'n veranderlike na iets, anders dat dieselfde veranderlike na iets anders. Dit is iets wat baie dikwels kan omskep word in hierdie soort van ding waar dat die veranderlike te stel - of, wel, is dit waar? Dan is hierdie, anders. [Studente] Die eerste een is indien dit waar is, reg? [Bowden] Ja. Die manier waarop ek dit altyd lees, temp gelyk is aan die waarde groter as temp waarde, dan is dit, anders. Dit is 'n vraag te vra. Is dit 'n groter? Doen dan die eerste ding. Anders doen die tweede ding. Ek word feitlik altyd - die kolon, ek het net in my kop, ek lees anders. 

Is daar iemand het 'n rekursiewe oplossing? Okay. Hierdie een wat ons gaan - dit kan reeds groot wees, maar ons gaan om dit nog beter te maak. Dit is pretty much die presies dieselfde idee. Dit is net goed doen wat jy wil om te verduidelik? [Studente] Sure. So maak ons ​​seker dat die boom nie eerste nulpunt, want as die boom is null dan is dit gaan om terug te keer vals omdat ons dit nog nie gevind nie. En as daar is nog steeds 'n boom, gaan ons in - ons eers kyk of die waarde is die huidige node. True terug gee as dit is, en as ons nie recursief op die linker-of regs. Klink dit gepas? >> Mm-hmm. (Ooreenkoms) So sien dat dit amper is struktureel baie soortgelyk aan die iteratiewe oplossing. Dit is net dat in plaas van recursing, het ons 'n while lus. En die basis geval hier waar die boom is nie gelyk aan nul was die voorwaarde waaronder ons uitgebreek het van die while lus. Hulle is baie soortgelyk. Maar ons gaan hierdie een stap verder te gaan. Nou, ons doen dieselfde ding hier. Kennisgewing ons die dieselfde ding in beide van hierdie lyne is die terugkeer, behalwe vir een argument is anders. So ons gaan om dit te maak in 'n drieledige. Ek opsie iets getref het, en dit het 'n simbool. Okay. So ons gaan om terug te keer bevat. Dit is om verskeie lyne, goed, vergrote in dit is. Gewoonlik, as 'n stilistiese ding, ek dink nie baie mense sit 'n spasie na die pyl, maar ek dink as jy konsekwent, dit is goed. As waarde is minder as boom waarde, ons wil recursief op die boom links, anders wat ons wil recursief op die boom reg. So dit was stap een van die maak van hierdie kyk kleiner. Stap twee van die maak van hierdie kyk kleiner - ons kan skei dit aan verskeie lyne. Okay. Stap twee van die maak van dit lyk kleiner is hier, so opbrengs waarde is gelyk aan boom waarde, of bevat wat ookal. 

Dit is 'n belangrike ding. Ek is nie seker as hy sê dit uitdruklik in die klas, maar dit is kortsluiting evaluering genoem. Die idee hier is 'n waarde == boom waarde. As dit waar is, dan is dit waar, en ons wil "of" dat met alles wat hier. So sonder om selfs te dink oor alles wat hier, wat is die hele uitdrukking gaan om terug te keer? [Studente] True? >> Ja, want waar van enigiets, or'd - of waar or'd met enigiets is noodwendig waar nie. So gou as ons sien return value = boom waarde, ons is maar net gaan om terug te keer waar. Nie eens gaan recursief bevat verder af in die lyn. Ons kan hierdie een stap verder te neem. Return boom is nie gelyk aan nul en al hierdie dinge. Dit maak dit 'n een-line funksie. Dit is ook 'n voorbeeld van 'n kortsluiting evaluering. Maar nou is dit dieselfde idee - in plaas van - so as boom is nie gelyk aan nul - of, wel, as die boom nie gelyk null, wat is die slegte geval, as die boom is gelyk aan nul is, dan is die eerste voorwaarde is gaan om vals te wees. So valse anded met enigiets gaan wees wat? [Studente] False. >> Ja. Dit is die ander helfte van die kortsluiting evaluering, waar as boom is nie gelyk aan nul is, dan is ons nie van plan om selfs te gaan - of indien boom gelyk null, dan het ons nie gaan om die waarde == boom waarde te doen. Ons is net gaan om onmiddellik return false. Wat belangrik is, want as dit nie 'n kortsluiting evalueer, dan as boom gelyk null, is hierdie tweede toestand gaan te seg skuld, omdat boom-> waarde ontwysing null. So dit is dit. Kan hierdie skuif weer oor. Dit is ook 'n baie algemene ding, nie die maak van hierdie een lyn met hierdie, maar dit is 'n algemene ding in omstandighede, miskien nie reg hier, maar as (boom = NULL, en boom-> waarde == waarde), doen wat ook al. Dit is 'n baie algemene toestand, waar in plaas van om om dit te breek in twee ifs, waar wil, is die boom null? Goed, dit is nie null, so nou is die boom waarde gelyk aan waarde? Doen dit. In plaas daarvan, het hierdie toestand, sal dit nooit seg skuld want dit sal breek as dit gebeur te wees null. Wel, ek dink as jou boom is 'n heeltemal ongeldig pointer, kan dit nog steeds seg skuld, maar dit kan nie seg skuld as die boom is null. As dit nul is, sal dit breek uit voor jy al ooit die wyser in die eerste plek be dereferenced. [Studente] Is hierdie sogenaamde lui evaluering? 

[Bowden] Lazy evaluering is 'n aparte ding. Lazy evaluering is meer soos jy vra vir 'n waarde, jy vra 'n waarde te bereken, soort van, maar jy hoef dit nie onmiddellik. So totdat jy dit nodig het, is dit nie geëvalueer. Dit is nie presies dieselfde ding, maar in die Huffman pset, dit sê dat ons "lui" skryf. Die rede waarom ons dit doen, is omdat ons eintlik die skryf buffering - ons wil nie individuele stukkies te skryf op 'n tyd, of individuele bytes op 'n tyd, ons wil plaas 'n stuk grepe te kry. Dan weer ons het 'n stuk van grepe, dan sal ons dit skryf. Selfs al is jy vra om dit te skryf - en fwrite en fread die dieselfde soort van ding doen. Hulle buffer jou lees en skryf. Selfs al is jy vra om dit onmiddellik te skryf, dit sal waarskynlik nie. En jy kan nie seker wees dat dinge gaan geskryf word totdat jy noem hfclose of wat dit ookal is, wat dan sê, okay, ek maak my lêer, dit beteken dat ek beter wil skryf alles wat ek nog nie geskryf nie. Dit is nie nodig om alles uit te skryf totdat jy die sluiting van die lêer, en dan moet dit. So dit is net wat lui - dit wag totdat dit gebeur. Dit - 51 en jy sal dit in meer detail gaan in, omdat OCaml en alles in 51, alles is rekursie. Daar is geen iteratiewe oplossings, basies. Alles is rekursie, en lui evaluering gaan belangrik wees vir 'n baie van die omstandighede waar, as jy nie lui nie evalueer, sou dit beteken - Die voorbeeld is strome, wat is oneindig lank. In teorie, kan jy dink van die natuurlike getalle as 'n stroom van 1-2-3-4-5-6-7 So lui geëvalueer dinge is fyn. As ek sê: Ek wil die tiende nommer, dan sal ek kan evalueer tot die tiende getal. As ek wil die honderdste getal, dan sal ek kan evalueer tot die honderdste getal. Sonder lui evaluering, dan is dit gaan om te probeer om al die getalle onmiddellik te evalueer. Jy evaluering van oneindig baie getalle, en dit is net nie moontlik nie. So daar is 'n baie van die omstandighede waar lui evaluering is net noodsaaklik om dinge uit te werk. 

Nou wil ons insetsel te skryf waar insetsel gaan wees soortgelyke verandering in sy definisie. So nou is dit Bool insert (int waarde). Ons gaan dat Bool insert (int waarde, node * boom) te verander. Ons het eintlik gaan dit weer in 'n bietjie verander, sal ons sien waarom. En laat ons beweeg build_node, net vir die heck dit, hierbo te voeg, sodat ons het nie 'n funksie-prototipe te skryf. Wat is 'n aanduiding dat jy gaan word met behulp van build_node in insetsel. Okay. Neem 'n minuut vir daardie. Ek dink ek het die hersiening gered as jy wil om te trek uit, of ten minste, ek het nou. Ek wou 'n effense breek om te dink oor die logika van die insetsel, as jy nie kan dink. Basies, sal jy altyd net die invoeging word op die blare. Soos, as ek voeg 1, dan is ek onvermydelik gaan word die invoeging van 1 - Ek sal verander na swart - I'll word die invoeging van 1 hier. Of as Ek voeg 4, Ek wil die invoeging van 4 hier. So maak nie saak wat jy doen, jy gaan op 'n blaar word die invoeging. Al wat jy hoef te doen, is itereer die boom af totdat jy by die node wat die node se ouer, die nuwe node se ouer, en dan sy links of regs wyser verander, afhangende van of dit is groter as of minder as die huidige node. Verander dat wyser om te wys op jou nuwe node. So itereer die boom af, maak die blaar punt na die nuwe node. Ook dink oor die rede waarom dit verbied die tipe van situasie voor, waar ek die binêre boom gebou waar dit korrek was as jy net kyk na 'n enkele nodus, maar 9 was aan die linkerkant van 7 as jy al die pad af herhaalde. So dit is onmoontlik in hierdie scenario, aangesien dink oor die invoeging van 9 of iets, op die heel eerste node, Ek gaan 7 te sien en ek is net gaan om te gaan na die regterkant. So maak nie saak wat ek doen, as ek die invoeging deur te gaan na 'n blaar, en aan 'n blaar met behulp van die toepaslike algoritme, dit gaan onmoontlik wees om vir my 9 te voeg aan die linkerkant van 7 want so gou as ek getref 7 Ek gaan om te gaan na die regterkant. Is daar iemand het iets om mee te begin? [Studente] Ek doen. >> Sure. [Student, onverstaanbaar] [Ander student, onverstaanbaar] [Bowden] Dit word waardeer. Okay. Wil jy om te verduidelik? 

[Studente] Omdat ons weet dat ons is die invoeging van nuwe nodes aan die einde van die boom, Ek haak deur die boom iteratief totdat ek by 'n node wat daarop aan nul. En dan het ek besluit om dit te sit aan die regterkant of die linkerkant deur gebruik te maak van hierdie reg veranderlike, dit het vir my gesê waar om dit te sit. En dan, in wese, Ek het net gemaak dat dit die laaste - dat die temp node punt na die nuwe node dat dit skep, óf aan die linkerkant of aan die regterkant, afhangende van wat die waarde was reg. Ten slotte, ek het die nuwe node waarde tot die waarde van die toets. [Bowden] Okay, so ek sien een probleem hier. Dit is soos 95% van die manier waarop daar. Die een probleem wat ek sien, goed, iemand anders sien 'n probleem? Wat is die omstandighede waaronder hulle breek uit van die lus? [Studente] As temp is van nul? >> Ja. So, hoe jy breek uit van die lus is as die temp is null. Maar wat doen ek hier? Ek dereference temp, wat is onvermydelik null. En die ander ding wat jy hoef te doen, is nie net hou totdat die temp is null, jy wil om tred te hou van die ouer ten alle tye. Ons wil ook node * ouer, ek dink ons ​​dat by null kan hou op die eerste. Dit gaan vreemde gedrag te hê vir die wortel van die boom, maar ons sal kry. As waarde is groter as wat ookal, dan temp = temp reg. Maar voordat ons dit doen, ouer = temp. Of ouers is altyd gaan op gelyke temp? Is dit die geval? Indien temp nie null, dan gaan ek om te beweeg, maak nie saak wat, na 'n node waarvoor temp is die ouer. So ouer gaan wees temp, en dan skuif ek temp af. Nou temp is null, maar ouer punte aan die ouer van die ding wat null. So hier, ek wil nie reg te stel gelyk aan 1. So het ek verhuis na die reg, so as regs = 1, en ek dink jy wil ook om te doen - as jy na links beweeg, wil jy reg te stel gelyk aan 0. Of anders as jy ooit na regs beweeg. So reg = 0. As regs = 1, nou wil ons die ouer regs wyser newnode te maak, anders wil ons die ouer links wyser newnode te maak. Vrae oor wat? Okay. So, dit is die manier waarop ons - Wel, eintlik, in plaas van om dit te doen, Ons het half verwag jy build_node te gebruik. En dan as newnode gelyk aan nul, return false. Dit is dit. Nou, dit is wat ons verwag dat jy moet doen. 

Dit is wat die personeel oplossings doen. Ek het nie eens met hierdie as die "regte" manier gaan oor dit maar dit is heeltemal fyn, en dit sal werk. Een ding wat 'n bietjie weird reg nou is indien die boom begin as null, het ons in 'n null boom. Ek dink dit hang af van hoe jy definieer die gedrag van die wat in 'n null boom. Ek sou dink dat as jy slaag in 'n null boom, dan invoeging van die waarde in 'n null boom moet net terugkeer 'n boom waar die enigste waarde is dat enkele nodus. Moenie mense dit eens met wat? Jy kan, as jy wil, as jy slaag in 'n null boom en jy wil 'n waarde toe te voeg in dit, return false. Dit is aan jou om te definieer. Die eerste ding wat ek gesê het en dan te doen - Wel, jy gaan sukkel om dit te doen te hê, want dit makliker sou wees as ons het 'n globale wyser na die ding, maar ons weet nie, so as die boom is null, daar is niks wat ons daaraan kan doen nie. Ons kan net terugkeer vals. So ek gaan insetsel te verander. Ons tegnies kon net verander hierdie reg hier, hoe dit iterating oor dinge, maar ek gaan insetsel te verander na 'n node ** boom. Double wysers. Wat beteken dit? In plaas van die hantering van verwysings na nodes, die ding wat ek gaan manipuleer is dit wyser. Ek gaan om te manipuleer hierdie wyser. Ek gaan om te manipuleer pointers direk. Dit maak sin, aangesien dink oor af - goed, reg nou hierdie punte aan nul. Wat ek wil doen is manipuleer hierdie wyser om te wys nie NULL. Ek wil om dit te wys op my nuwe node. As ek net hou van wysers na my pointers, dan het ek nie nodig om tred te hou van 'n ouer wyser. Ek kan net dop om te sien of die wyser wys aan nul, en indien die wyser wys na NULL, verander dit om te verwys na die node wat ek wil hê. En ek kan dit verander, want ek het 'n wyser na die wyser. Laat hierdie reg nou sien. Jy kan eintlik dit doen rekursief redelik maklik. Wil ons dit te doen? Ja, ons doen. 

Laat ons sien dit rekursief. Eerstens, is wat ons basis geval gaan wees? Byna altyd ons basis geval, maar eintlik is dit soort moeilik. Eerste dinge eerste, indien (boom == null) Ek dink dat ons net gaan om terug te keer vals. Dit is verskil van jou boom null. Dit is die wyser na jou wortel pointer null wat beteken dat jou wortel wyser nie bestaan ​​nie. So hier, as ek dit doen node * - laat ons net hergebruik hierdie. Node * root = NULL, en dan gaan ek voeg deur so iets te doen om te bel, voeg 4 in & Root. So & wortel, as die wortel is 'n node * dan & Root gaan 'n node **. Dit is geldig. In hierdie geval, boom, tot hier, boom is nie null, of voeg. Hier. Boom is nie null, * boom is null, wat is goed want as * boom is van nul, dan sal ek kan manipuleer dit nou verwys na wat ek wil om dit te wys. Maar as die boom is nul, wat beteken dat ek net hier afgekom en gesê null. Dit maak nie sin nie. Ek kan nie iets te doen met dit. As die boom is null, return false. So het ek basies reeds gesê wat ons werklike basis-geval is. En wat is dat gaan wees? [Student, onverstaanbaar] [Bowden] Ja. So as (* boom == null). Dit hou verband met die geval hier waar as my rooi wyser is om die ondeursigtigheid ek gefokus op, so soos ek gefokus op die wyser, nou ek gefokus op die wyser. Nou het ek gefokus op hierdie wyser. So as my rooi pointer, wat is my node **, ooit - indien *, my rooi pointer, is ooit null, wat beteken dat ek by die geval waar ek fokus op 'n wyser dat punte - dit is 'n wyser wat behoort aan 'n blaar. Ek wil hierdie wyser te verander om te wys op my nuwe node. Kom terug hier. My newnode sal net node * n = build_node (waarde) dan n, as n = NULL, return false. Anders wat ons wil om te verander wat die wyser tans verwys na tot nou toe te wys aan ons nuut gebou node. Ons kan eintlik hier doen. Plaas van sê: n, sê ons * boom = * boom. Almal verstaan ​​dat? Wat deur die hantering van verwysings na verwysings, ons kan verander null wysers om te wys op die dinge wat ons wil hê hulle om te verwys na. Dit is ons basis geval. 

Nou ons herhaling, of ons rekursie, gaan wees baie soortgelyk aan alle ander recursions het ons is besig. Ons gaan om te wil om waarde toe te voeg, en nou kan ek gaan drieledige om weer te gebruik nie, maar wat ons toestand gaan wees? Wat is dit wat ons soek om te besluit of ons wil gaan links of regs? Kom ons doen dit in afsonderlike stappe. As (waarde <) wat? [Studente] Die boom se waarde? [Bowden] So onthou dat ek op die oomblik is - [Studente onverstaanbaar] [Bowden] Ja, so hier is, laat ons sê dat hierdie groen pyltjie is 'n voorbeeld van wat boom is tans, is 'n verwysing na hierdie wyser. So dit beteken dat ek 'n wyser na 'n wyser na 3. Die dereference twee keer klink goed. Wat ek doen - hoe doen ek dit? [Studente] Dereference een keer, en dan doen arrow dat die pad? [Bowden] (* boom) is die dereference een keer, -> waarde gaan gee my die waarde van die node dat ek is indirek verwys na. So ek kan ook skryf dit ** tree.value indien u verkies dat. Óf werk. As dit die geval is, dan wil ek noem voeg met 'n waarde. En wat is my opgedateer node ** gaan wees? Ek wil om te gaan na die linkerkant, sodat ** tree.left gaan aan my linkerkant. En ek wil die wyser na daardie ding sodat as die linkerkant eindig synde die null pointer, Ek kan verander om dit te wys op my nuwe node. 

En die ander geval kan wees baie soortgelyk. Kom ons eintlik dat my drieledige nou. Voeg waarde as waarde <(** boom). Waarde. Dan wil ons ons ** te werk aan die linkerkant, anders wat ons wil hê dat ons ** te werk aan die regterkant. [Studente] Beteken dit die wyser na die wyser? [Bowden] Onthou dat - ** tree.right is 'n node ster. [Student, onverstaanbaar] >> Ja. ** Tree.right is soos hierdie wyser of iets. So deur die neem van 'n wyser na daardie, gee my wat ek wil hê van die wyser na daardie man. [Studente] Kan ons gaan oor hoekom ons weer die twee wysers gebruik? [Bowden] Ja. So - nee, jy kan, en dat die oplossing voor was 'n manier om dit te doen sonder om twee wysers. Jy moet in staat wees om te verstaan ​​met behulp van twee verwysings, en dit is 'n skoner oplossing. Ook kennis dat, wat gebeur as my boom - wat gebeur as my wortel null was? Wat gebeur as ek hierdie geval doen reg hier? So node * wortel = NULL, voeg 4 in & Root. Wat is die wortel gaan na hierdie te wees? [Student, onverstaanbaar] >> Ja. Root waarde gaan wees 4. Root links gaan wees null, wortel reg gaan wees null. In die geval waar ons nie slaag wortel adres, ons kan nie verander wortel skiet. In die geval waar die boom waar die wortel null, ons het net gehad het om terug te keer vals. Daar is niks wat ons kan doen nie. Ons kan nie reël invoeg 'n nodus in 'n leë boom. Maar nou kan ons, ons het net 'n leë boom in 'n een-node boom. Wat gewoonlik die verwagte manier waarop dit veronderstel is om te werk. 

Verder, dit is aansienlik korter as ook die dop van die ouer, en so itereer jy al die pad af. Nou het ek my ouers, en ek het my ouers regs wyser na die wat ookal. In plaas daarvan, as ons het dit gedoen iteratief, sou dit dieselfde idee met 'n while lus te wees. Maar in plaas van om te gaan met my ouer pointer, plaas my huidige wyser die ding sou wees dat ek direk die wysiging van om te wys op my nuwe node. Ek het nie te doen met of dit na links. Ek het nie te doen met of dit wys na regs. Dis net wat hierdie wyser is, ek gaan om dit te stel om te wys op my nuwe node. Almal verstaan ​​hoe dit werk? Indien nie waarom wil ons doen dit op hierdie manier, maar ten minste dat dit werk as 'n oplossing? [Studente] Waar terugkeer ons waar? [Bowden] Dit is waarskynlik reg hier. As ons dit korrek voeg, terug waar. Anders, af hier is ons gaan watter insert opbrengste wil om terug te keer. 

En wat is spesiaal oor hierdie rekursiewe funksie? Dit is stert rekursiewe, so lank as wat ons stel met 'n paar optimalisatie, dit sal erken dat en jy sal nooit 'n stack overflow van hierdie, selfs as ons boom het 'n hoogte van 10.000 of 10 miljoen. [Student, onverstaanbaar] [Bowden] Ek dink dit maak dit op Dash - of wat optimization vlak nodig is vir 'n stert rekursie om erken te word. Ek dink dit erken - GCC en kletteren ook verskillende betekenisse vir hul optimization vlakke. Ek wil om te sê dit is DashO 2, vir seker dat dit sal erken Staartrecursie. Maar ons - jy kan bou soos 'n Fibonocci voorbeeld of iets. Dit is nie maklik om te toets met hierdie, want dit is moeilik om te bou 'n binêre boom wat so groot is. Maar ja, ek dink dit is DashO 2, wat as jy met DashO 2 stel, sal dit lyk vir Staartrecursie en te optimaliseer dat uit. Kom ons gaan terug tot - voeg is letterlik die laaste ding wat dit nodig het. Kom ons gaan terug na die insetsel oor hier waar ons gaan dieselfde idee om te doen. Dit sal nog steeds die fout nie in staat is om heeltemal te hanteer wanneer die wortel self, is van nul, of die afgelope inskrywing null, maar in plaas daarvan om met 'n ouer pointer, laat se aansoek doen om dieselfde logika van die behoud van verwysings na verwysings. As ons hier hou ons node ** huidige, en ons hoef nie om tred te hou van reg meer, maar node ** huidige = & boom. En nou is ons while lus gaan wees terwyl * huidig ​​is nie gelyk aan nul. Spoor van ouers hoef nie meer te hou. Hoef nie om tred te hou van links en regs. En ek sal dit noem temp, want ons reeds temp met behulp van. Okay. So as (waarde> * temp), dan & (* temp) -> reg anders temp = & (* temp) -> links. En nou, op hierdie punt, na hierdie while lus, Ek doen dit want miskien is dit is makliker om te dink oor iteratief as rekursief, maar na hierdie while lus, * Temp is die wyser wat ons wil verander. 

Voordat ons ouer, en ons wou óf ouer links of ouer reg om te verander, maar as ons wil ouer reg om te verander, * temp is ouer reg, en ons kan dit direk verander. So hier, kan ons doen * temp = newnode, en dit is dit. So kennisgewing, alles wat ons gedoen het in hierdie reëls van die kode. Ten einde tred te hou met die ouer in al die ekstra inspanning. Hier, as ons net hou van die wyser na die wyser, en selfs as ons wil om ontslae te raak van al hierdie krullerige draadjies nou, maak dat dit lyk korter. Dit is nou die presiese dieselfde oplossing, maar minder reëls van die kode. Sodra jy begin met die erkenning van hierdie as 'n geldige oplossing, dit is ook makliker om te redeneer oor as soos, okay, waarom het ek hierdie vlag op int reg? Wat beteken dit? O, is dit wat beteken dat elke keer as ek gaan reg, ek nodig het om dit te stel, anders as ek gaan links, ek nodig het om dit te stel aan nul. Hier, ek het nie om te redeneer oor wat, dit is net makliker om oor na te dink. Vrae? [Student, onverstaanbaar] >> Ja. Okay, so in die laaste bietjie - Ek dink 'n vinnige en maklike funksie wat ons kan doen is, let's - saam, dink ek, probeer en skryf 'n paragraaf bevat funksie wat nie omgee of dit is 'n binêre soekboom. Dit bevat 'n funksie waar moet terugkeer indien enige plek in hierdie algemene binêre boom is die waarde wat ons is op soek na. So laat ons eers dit rekursief doen en dan kan ons dit sal iteratief doen. Ons kan eintlik net doen dit saam, want dit gaan om te wees regtig kort. 

Wat is my base geval gaan wees? [Student, onverstaanbaar] [Bowden] So as (boom == null), wat dan? [Studente] Terug vals. [Bowden] Else, goed, ek hoef nie die ander dinge. As was my ander basis geval. [Studente] Tree se waarde? >> Ja. So as (boom-> waarde == waarde. Kennisgewing ons terug is node *, nie node ** s? Contains sal nooit hoef te gebruik om 'n node **, Aangesien ons nie die wysiging van wysers. Ons is net kameelkoei hulle. As dit gebeur, dan is ons ware wil om terug te keer. Anders wil ons die kinders te verken. Ons kan dus nie redeneer oor die vraag of alles aan die linkerkant is minder en alles wat aan die regterkant is groter. So, wat is ons toestand gaan om hier te wees - of, wat gaan ons doen? [Student, onverstaanbaar] >> Ja. Return bevat (waarde, boom-> links) of bevat (waarde, boom-> regs). En dit is dit. En let op daar is 'n kortsluiting evaluering, waar as ons gebeur om die waarde te vind in die linker boom, ons nooit nodig om te kyk na die regte boom. Dit is die hele funksie. Nou kom ons doen dit iteratief, wat minder lekker gaan wees. Ons neem die gewone begin van node * huidig ​​= boom. Terwyl (huidige = NULL!). Vinnig gaan om 'n probleem op te sien. As die huidige - hier, as ons ooit te breek uit hierdie, dan het ons hardloop uit van die dinge om na te kyk, so vals terugkeer. As (huidige> waarde == waarde), return true. En nou, ons is op 'n plek - ons weet nie of ons wil om links of regs te gaan. So arbitrêr, laat ons net gaan jy links. Ek het natuurlik loop in 'n kwessie waar ek heeltemal alles verlaat - Sal ek ooit net so die linkerkant van 'n boom. Ek sal nooit so enigiets wat is 'n regte kind van enigiets. Hoe kan ek dit regmaak? [Studente] Jy het die spoor van die links en regs te hou in 'n stapel. [Bowden] Ja. So laat ons maak dit struct lys, node * n, en dan node ** volgende? Ek dink wat goed werk. Ons wil om te gaan oor die linker-of let's hier. Struct Lys =, sal dit begin uit op hierdie struct lys. * Lys = null. So wat gaan ons geskakelde lys van subtrees dat ons het oorgeslaan oor. Ons gaan om te deurkruis nou links, maar omdat ons noodwendig nodig het om terug te kom na regs, Ons gaan die regterkant binne te hou van ons struct lys. Dan sal ons new_list of struct, struct lys *, new_list = malloc (sizeof (list)). Ek gaan om te ignoreer foute te kontroleer dat nie, maar jy moet nagaan om te sien as dit null. New_list die knoop dit gaan om te wys - oh, wat is die rede waarom ek wou dit hier. Dit gaan om te verwys na 'n tweede struct lys. Dit is net hoe geskakelde lyste werk. Dit is dieselfde as 'n int geskakelde lys behalwe ons net die vervanging van int met node *. Dit is presies dieselfde. So new_list, die waarde van ons new_list node, gaan word huidig-> reg. Die waarde van ons new_list-> Volgende gaan ons oorspronklike lys, en dan gaan ons ons lys by te werk om te verwys na new_list. 

Nou moet ons 'n soort van manier van trek dinge, soos ons gekruis die hele linker boomstruktuur inskuif nie. Nou het ons nodig het om goed te trek uit dit, soos die huidige, is van nul, ons wil nie net return false. Ons wil nou buite trek by ons nuwe lys. 'N maklike manier om dit te doen - goed, eintlik, is daar verskeie maniere om dit te doen. Enigiemand het 'n voorstel? Waar moet ek doen of hoe ek moet dit doen? Ons het net 'n paar minute, maar enige voorstelle? In plaas van een manier, in plaas van ons toestand terwyl wat ons tans op soek is nie null, plaas ons gaan om voort te gaan om te gaan totdat ons lys self, is van nul. So as ons lys eindig 'null, dan het ons hardloop uit van die dinge om na te kyk, om te soek oor. Maar dit beteken dat die eerste ding wat in ons lys is net gaan om die eerste nodus. Die heel eerste ding sal wees - ons nie meer nodig om te sien dat. So lys> n sal vir ons 'n boom wees. lys-> Volgende gaan wees null. En nou, terwyl die lys is nie gelyk aan nul. Cur gaan om iets te trek uit ons lys. So huidige gaan op gelyke lys-> n. En dan lys gaan op gelyke lys-> n, of lys-> Volgende. So as die huidige waarde gelyk is aan die waarde. Nou kan ons voeg ons albei reg wyser en ons links wyser so lank as wat hulle is nie null. Hier onder, ek dink ons ​​moet gedoen het nie in die eerste plek. As (huidige> regs = null) dan gaan ons dat die node in ons lys te voeg. As (huidig-> links), dit is 'n bietjie ekstra werk, maar dit is goed. As (huidig-> links = null), en ons gaan die linkerkant in ons geskakelde lys te voeg, en dat moet dit. Ons itereer - so lank as wat ons iets in ons lys, ons het 'n ander node om na te kyk. So ons kyk op daardie node, ons ons lys bevorder na die volgende een. As dit node is die waarde wat ons is op soek na, kan ons terugkeer waar. Anders voeg beide ons links en regs subtrees, so lank as wat hulle is nie null, in ons lys sodat ons onvermydelik gaan oor hulle. So as hulle nie null, as ons wortel wyser wys na twee dinge, dan op die eerste het ons getrek iets uit sodat ons lys eindig 'null. En dan het ons twee dinge terug in, so nou is ons lys van grootte 2. Daarna het ons gaan loop back-up en ons net gaan om te trek, laat ons sê, die linker-wyser van ons wortel node. En dit sal net hou gebeur, sal ons opeindig herhaling oor alles. 

Let daarop dat hierdie was aansienlik meer ingewikkeld in die rekursiewe oplossing. En ek het gesê verskeie kere dat die rekursiewe oplossing het gewoonlik baie in gemeen met die iteratiewe oplossing. Hier is dit presies wat die rekursiewe oplossing is doen. Die enigste verandering is dat in plaas van implisiet gebruik van die stapel, die program stapel, as jou manier van die dop van wat nodes jy nog steeds nodig om te besoek, nou het jy 'n geskakelde lys te gebruik uitdruklik. In beide gevalle sal jy die dop van watter node nog gedoen moet word besoek. In die rekursiewe geval is dit is net makliker omdat 'n stapel geïmplementeer word vir jou as die program stapel. Let daarop dat hierdie geskakelde lys, is dit 'n stapel. Wat ons ook al net op die stapel onmiddellik wat ons gaan om af te trek die stapel na die volgende besoek. Ons is uit die tyd, maar enige vrae? [Student, onverstaanbaar] [Bowden] Ja. So as ons ons geskakelde lys, stroom gaan om te verwys na hierdie man, en nou is ons is net die bevordering van ons geskakelde lys om te fokus op hierdie man. Ons kameelkoei oor die geskakelde lys in daardie lyn. En dan dink ek ons ​​moet ons geskakelde lys en stuff bevry een keer voordat hy terugkeer waar of vals is, moet ons itereer oor ons geskakelde lys en altyd af hier, dink ek, as ons huidige reg is nie gelyk aan, voeg dit, so nou wil ons bevry huidige omdat, goed, ons het heeltemal vergeet van die lys? Ja. So dit is wat ons hier wil doen. Waar is die wyser? Cur was toe - ons wil na 'n struct lys * 10 is gelyk aan lys langs. Gratis lys, lys = temp. En in die geval waar ons terug waar is, het ons nodig het om te itereer oor die res van ons geskakelde lys bevry dinge. Die nice ding oor die rekursiewe oplossing is bevry dinge beteken net knal factorings van die stapel af wat vir jou sal gebeur. Dus het ons van iets wat is soos 3 lyne van harde-tot-dink-oor-kode gegaan iets wat aansienlik baie meer hard-to-dink-oor reëls van die kode. Nog meer vrae? Alles reg. Ons is goed. Bye! [CS50.TV]