[Powered by Google Translate] [Artikel 7] [Minder Gerieflik]
[Nate Hardison] [Harvard Universiteit]
[Hierdie is CS50.] [CS50.TV]
>> Welkom by Artikel 7.
Dankie te orkaan Sandy,
in plaas van met 'n normale deel van hierdie week,
ons om dit te doen deur-stap, deur middel van die afdeling van die vrae.
Ek gaan word die volgende saam met die probleem Stel 6 spesifikasie,
en gaan deur al die vrae in die
'N Artikel VAN VRAE AFDELING.
As daar enige vrae is,
asseblief plaas dit op CS50 Bespreek.
>> Alright. Kom ons begin.
Reg nou is ek op soek na bladsy 3 van die probleem Set spesifikasie.
Ons gaan die eerste keer begin praat oor binêre bome
aangesien dit 'n baie van belang is vir hierdie week se probleem stel -
Huffman Tree kodering.
Een van die heel eerste datastrukture het ons gepraat oor CS50 was die skikking.
Onthou dat 'n skikking is 'n volgorde van die elemente -
almal van dieselfde soort - reg langs mekaar in die geheue gestoor.
As ek 'n heelgetal skikking wat ek kan trek met behulp van hierdie bokse-nommers-heelgetalle styl -
Kom ons sê ek het 5 in die eerste blokkie, ek het 7 in die tweede,
dan het ek 8, 10 en 20 in die finale boks.
Onthou, die twee baie goeie dinge oor hierdie skikking
is dat ons hierdie konstante-time toegang tot 'n bepaalde element
in die skikking as ons weet dat die indeks.
Byvoorbeeld, as ek wil hê dat die derde element in die skikking aan te gryp -
indeks 2 deur gebruik te maak van ons zero-gebaseerde kruip -
Ek het letterlik net 'n eenvoudige wiskundige berekening te doen,
hop tot daardie posisie in die skikking,
trek uit die 8 wat daar geberg word,
en ek is goed om te gaan.
>> Een van die slegte dinge oor hierdie skikking - dat ons het gepraat oor
wanneer ons bespreek geskakelde lyste -
is dat as ek wil 'n element in hierdie skikking te voeg,
Ek gaan om te hê sommige verskuif om te doen.
Byvoorbeeld, hierdie skikking reg hier
in gesorteer einde - gesorteer in stygende volgorde
5, dan 7, dan 8, dan 10 en dan 20 -
maar as ek wil die getal 9 in te voeg in hierdie skikking,
Ek gaan 'n paar van die elemente te skuif om plek te maak.
Ons kan trek dit uit hier.
Ek gaan hê om die 5, 7 beweeg, en dan die 8;
skep 'n gaping waar ek kan die 9,
en dan die 10 en die 20 kan gaan aan die regterkant van die 9.
Dit is 'n soort van 'n pyn want in die ergste geval scenario -
wanneer ons by te voeg aan die begin of aan die einde
van die skikking, afhangende van hoe ons skuif -
ons kan eindig met al die elemente te skuif
dat ons tans stoor in die skikking.
>> So, wat was die manier om hierdie?
Die manier om hierdie was om te gaan na ons gekoppelde-lys van die metode waar -
in plaas van die stoor van die elemente 5, 7, 8, 10 en 20 langs mekaar in die geheue -
wat ons in plaas gedoen het, was stoor dit soort van waar ons wil om dit te stoor
in hierdie gekoppelde-lys nodes wat ek teken hier, soort van ad hoc.
En dan het ons verbind hulle saam gebruik van die volgende wenke.
Ek kan 'n wyser van 5 tot 7,
'n wyser van die 7 8,
'n wyser uit die 8 aan die 10,
en uiteindelik, 'n wyser van die 10 aan die 20,
en dan 'n null wyser op die 20 wat aandui dat daar is niks links.
Die trade-off dat ons hier
is dat dit nou as ons wil hê dat die getal 9 in ons gesorteerde lys te voeg,
al wat ons hoef te doen, is die skep van 'n nuwe node met 9,
bedraad dit om te verwys na die toepaslike plek,
en dan weer draad 8 punt af na die 9.
Dit is redelik vinnig, met die veronderstelling dat ons presies weet waar ons wil die 9 in te voeg.
Maar die trade-off in ruil vir hierdie is dat ons nou verloor het die konstante-time toegang
aan 'n bepaalde element in ons data struktuur.
Byvoorbeeld, as ek wil die vierde element in hierdie geskakelde lys te vind,
Ek gaan te hê om te begin by die begin van die lys
en werk my pad deur die tel van node-by-node totdat ek vind die vierde een.
>> Ten einde beter toegang prestasie as 'n geskakelde lys te kry -
maar behou ook sommige van die voordele wat ons gehad het
in terme van 'n geskakelde lys van invoeging-time -
'n binêre boom gaan 'n bietjie meer geheue nodig het om te gebruik.
In die besonder, in plaas van net een wyser in 'n binêre boom node -
soos die gekoppelde-lys node doen -
ons gaan 'n tweede wyser toe te voeg tot die binêre boom node.
Eerder as om net met 'n wyser na die volgende element,
ons gaan 'n wyser na 'n links kind en 'n regte kind te hê.
>> Kom ons teken 'n prent om te sien wat dit eintlik lyk soos.
Weereens, ek gaan hierdie bokse en pyle te gebruik.
'N binêre boom node sal begin met net 'n eenvoudige boks.
Dit gaan om 'n ruimte te hê vir die waarde,
en dan is dit ook gaan om 'n ruimte vir die linker kind en die regte kind te hê.
Ek gaan hulle hier benoem.
Ons gaan die linker kind te hê, en dan gaan die reg om kind te hê.
Daar is baie verskillende maniere om dit te doen.
Soms vir ruimte en gerief,
Ek sal eintlik teken dit soos ek hier doen op die bodem
waar ek gaan om die waarde te hê aan die bokant,
en dan die regte kind op die onderste reg,
en die linker kind op die linkerhand.
Terug te gaan na die top diagram,
ons het die waarde op die heel boonste,
dan het ons die linker-kind pointer, en dan het ons die reg-kind-wyser.
>> In die Problem Set spesifikasie,
ons praat oor die teken van 'n nodus wat 'n waarde 7,
en dan 'n linker-kind pointer wat null, en 'n regs-kind pointer wat null.
Ons kan óf skryf kapitaal NULL in die ruimte vir
beide die linker-kind en die regte kind, of ons kan hierdie diagonale streep trek
deur elk van die bokse aan te dui dat dit nietig is.
Ek gaan om dit te doen net omdat dit is makliker.
Wat jy hier sien is twee maniere van die diagram van 'n baie eenvoudige binêre boom node
waar ons die waarde 7 en null kind wysers.
>> Die tweede deel van ons spesifikasie gesprekke oor hoe om met geskakelde lyste -
Onthou, ons het net om vas te hou aan die heel eerste element in 'n lys
die hele lys te onthou -
en net so, met 'n binêre boom, ons het net om vas te hou aan een wyser na die boom
ten einde beheer oor die hele data struktuur in stand te hou.
Hierdie spesiale element van die boom is die wortel node van die boom genoem.
Byvoorbeeld, as hierdie een node - hierdie node wat die waarde 7
met null links-en regs-kind-wysers -
was die enigste waarde in ons boom,
dan sou ons wortel node.
Dit is die begin van ons boom.
Ons kan dit 'n bietjie meer duidelik wanneer ons begin met die toevoeging van meer nodes aan ons boom.
Laat my trek 'n nuwe bladsy.
>> Nou gaan ons 'n boom te trek wat 7 by die wortel,
en 3 binnekant van die linker kind, en 9 binnekant van die regte kind.
Weereens, dit is redelik eenvoudig.
Ons 7 het, teken 'n node vir die 3, 'n node vir 9,
en ek gaan die linker-kind-wyser van 7 te stel om te verwys na die nodus met 3,
en die regs-kind wyser van die node met 7 tot die node met 9.
Nou, sedert 3 en 9 nie enige kinders,
ons gaan al van hul kind pointers te stel aan nul.
Hier is die wortel van ons boom ooreenstem met die node met die getal 7.
Jy kan sien dat as al wat ons het, is 'n wyser na die wortel node,
dan kan ons wandel deur ons boom en toegang tot beide kind nodes -
beide 3 en 9.
Nie nodig om wenke te handhaaf elke enkele nodus aan die boom.
Alright. Nou gaan ons nog 'n node te voeg tot hierdie diagram.
Ons gaan 'n node te voeg met 6,
en ons gaan dit as die regte kind van die node met 3 te voeg.
Om dit te doen, ek gaan daardie null pointer uit te vee in die 3-node
en draad dit om te verwys na die nodus met 6. Alright.
>> Op hierdie punt, laat ons gaan oor 'n bietjie van terminologie.
Om mee te begin, die rede dat dit 'n binêre boom in die besonder genoem
is dat dit twee kind wysers.
Daar is ander vorme van bome wat meer kind wysers.
In die besonder, jy het 'n "probeer" in Problem Set 5.
Jy sal sien dat in daardie drie het 27 verskillende verwysings na verskillende kinders gehad -
een vir elk van die 26 briewe in die Engelse alfabet,
en dan die 27ste vir die afkappingsteken -
So, dit is soortgelyk aan 'n tipe van die boom.
Maar hier, omdat dit binêre, ons het net twee kind wysers.
>> Bykomend tot hierdie wortel node wat ons oor gepraat het,
ons het ook gooi rondom die term "kind."
Wat beteken dit vir een node na 'n kind van 'n ander node?
Dit beteken letterlik dat 'n kind node is 'n kind van 'n ander node
indien daardie ander node het een van sy kind verwysings om aan te dui dat die node.
Te stel in meer konkrete terme,
as 3 word uitgewys deur een van die kind-wysers van 7, dan 3 is 'n kind van 7.
As ons om uit te vind wat die kinders van 7 -
Wel, ons sien dat 7 het 'n wyser na 3 en 'n wyser na 9,
so 9 en 3 is die kinders van 7.
Nege het geen kinders omdat sy kind pointers null,
en 3 het slegs een kind, 6.
Ses het ook geen kinders nie, want beide van sy wenke is null, wat ons nou trek.
>> Daarbenewens het ons ook praat oor die ouers van 'n bepaalde nodus,
en dit is, soos mens sou verwag, die omgekeerde van hierdie kind beskrywing.
Elke node het net een ouer in plaas van twee as wat jy kan verwag met die mens.
Byvoorbeeld, die ouer van 3 is 7.
Die ouer van 9 is ook 7, en die ouer van 6 3. Nie veel om dit te.
Ons het ook om te praat oor grootouers en kleinkinders,
en meer in die algemeen praat ons oor die voorvaders
afstammelinge van 'n bepaalde nodus.
Die voorvader van 'n node of voorouers, eerder van 'n node -
is al die nodes wat lê op die pad van die wortel aan daardie node.
Byvoorbeeld, as ek soek op die node 6,
dan is die voorvaders gaan wees beide 3 en 7.
Die voorouers van 9, byvoorbeeld, is - as ek kyk na die node 9 -
dan is die voorvader van 9 is net 7.
En nageslag is presies die teenoorgestelde.
As ek wil om te kyk na al die afstammelinge van 7,
dan moet ek kyk na al die nodes onder dit.
So, ek het 3, 9, en 6 as afstammelinge van 7.
>> Die laaste kwartaal wat ons sal praat oor hierdie idee van 'n broer of suster.
Broers en susters - soort van die volgende saam op hierdie familie-terme -
nodes wat op dieselfde vlak in die boom.
So, 3 en 9 is broers en susters, want hulle is op dieselfde vlak in die boom.
Hulle het albei dieselfde ouer, 7.
Die 6 het geen broers en susters, omdat 9 nie enige kinders.
En 7 het geen broers en susters, want dit is die wortel van ons boom,
en daar is altyd net 1 wortel.
Vir 7 broers en susters te hê sou hê om 'n node bo 7.
Daar sal 'n ouer van 7, in welke geval 7 sal nie langer die wortel van die boom te wees.
Dan dat die nuwe ouer van 7 sal ook 'n kind te hê,
en daardie kind sal dan die broer van 7.
>> Alright. Beweeg op.
Wanneer ons begin ons bespreking van binêre bome,
het ons gepraat oor hoe ons gaan om dit te gebruik om te
kry 'n voordeel oor beide skikkings en geskakelde lyste.
En die manier waarop ons gaan om dit te doen is met hierdie bestel eiendom.
Ons sê dat 'n binêre boom bestel word, volgens die spesifikasie,
indien vir elke node in ons boom, al sy afstammelinge aan die linkerkant -
die linker-kind en van die linker kind se nageslag -
mindere waardes, en al die nodusse op die reg -
die regte kind en al van die regte kind se afstammelinge -
nodes groter as die waarde van die huidige node wat ons is op soek na.
Net vir eenvoud, gaan ons om te aanvaar dat daar nie enige dubbele nodes in ons boom.
Byvoorbeeld, in hierdie boom ons nie van plan om te gaan met die saak
waar ons die waarde 7 by die wortel
en dan het ons ook die waarde 7 elders in die boom.
In hierdie geval, sal jy sien dat hierdie boom is inderdaad bestel.
Ons het die waarde 7 by die wortel.
Alles aan die linkerkant van 7 -
as ek al hierdie merkies maak ongedaan hier -
alles aan die linkerkant van 7 - 3 en die 6 -
daardie waardes is albei minder as 7, en alles na regs - wat is net 9 -
is groter as 7.
>> Dit is nie die enigste bestel boom met hierdie waardes,
maar laat ons trek 'n paar van hulle.
Daar is eintlik 'n hele klomp van die maniere waarop ons dit kan doen.
Ek gaan 'n snelskrif te gebruik net om dinge eenvoudig hou waar -
eerder as teken uit die hele bokse en pyle -
Ek gaan net om die getalle te trek en pyle verbind hulle voeg.
Om mee te begin, sal ons net skryf ons oorspronklike boom weer waar ons 7, en dan 'n 3,
en dan 3 wys terug na die reg aan die 6,
en 7 het 'n reg kind wat was 9.
Alright. Wat is 'n ander manier wat ons kan skryf hierdie boom?
In plaas van om 3 die linker kind van 7,
ons kan ook die 6 die linker kind van 7,
en dan 3 die linker kind van die 6.
Dit sal lyk soos hierdie boom hier waar ek het 7,
dan 6, dan 3, en 'n 9 aan die regterkant.
Ons het ook nie 7 as ons wortel node te hê.
Ons kan ook 6 as ons wortel node.
Wat sal dit lyk?
As ons gaan hierdie bestel eiendom in stand te hou,
alles aan die linkerkant van die 6 het minder as dit te wees.
Daar is slegs een moontlikheid, en dit is 3.
Maar dan as die reg om kind van 6, ons het twee moontlikhede.
Eerstens, kan ons die 7 en dan die 9
of ons kan om dit te trek nie - soos ek is op die punt om hier te doen -
waar ons die 9 as die regte kind van die 6,
en dan die 7 as die linker kind van die 9.
>> Nou, 7 en 6 is nie die enigste moontlike waardes vir die wortel.
Ons kan ook 'n 3 by die wortel.
Wat gebeur as daar 3 is by die wortel?
Dinge hier, 'n bietjie interessant.
Drie nie enige waardes wat minder as dit,
sodat die hele linkerkant van die boom is net gaan om te wees null.
Daar is nie van plan om enigiets daar.
Aan die regterkant, kan ons die lys van dinge in stygende orde.
Ons kan 3, dan 6, dan 7, dan 9.
Of, kan ons doen 3, dan 6, dan 9, dan 7.
Of, kan ons doen 3, dan 7, dan 6, dan 9.
Of, 3, 7 - eintlik nie, kan ons dit nie doen nie 'n 7 nie.
Dit is ons een ding.
Ons kan dit doen 9, en dan van die 9 ons kan doen 6 en dan 7.
Of, kan ons doen 3, dan 9, dan 7, en dan 6.
>> Een ding om jou aandag te vestig op hier is
dat hierdie bome is 'n bietjie weird-looking.
In die besonder, as ons kyk na die 4 bome aan die regterkant -
Ek sal omkring hulle hier -
hierdie bome lyk byna presies soos 'n geskakelde lys.
Elke node het slegs een kind,
En so het ons nie enige van hierdie boom-agtige struktuur wat ons sien, byvoorbeeld,
in hierdie een eensame boom hier op die onderste linkerkantste.
Hierdie bome is eintlik genoem binêre bome te ontaard,
en ons sal praat oor hierdie meer in die toekoms -
veral as jy gaan op die ander rekenaar wetenskap kursusse te neem.
Hierdie bome is ontaard.
Hulle is nie baie nuttig, want, inderdaad, hierdie struktuur leen hom
tye soortgelyk aan dié van 'n geskakelde lys te soek.
Ons nie om voordeel te trek uit die ekstra geheue - hierdie ekstra pointer -
as gevolg van ons struktuur sleg op hierdie manier.
Eerder as om op en trek uit die binêre bome wat 9 by die wortel,
wat is die laaste geval wat ons wil hê,
ons plaas, op hierdie punt, gaan 'n bietjie om te praat oor hierdie ander term
wat ons gebruik wanneer hulle praat oor die bome, wat genoem word die hoogte.
>> Die hoogte van 'n boom is die afstand vanaf die wortel tot die mees verre node,
of eerder die getal van hoep wat jy sal moet maak ten einde
begin van die wortel en dan uiteindelik by die mees afgeleë nodus in die boom.
As ons kyk by sommige van hierdie bome wat ons het hier gevestig,
kan ons sien dat as ons hierdie boom in die boonste linkerkantste hoek en ons begin by die 3,
dan het ons 1 hop te kry om die 6 te maak, 'n tweede hop om te kry aan die 7,
en 1/3 hop te kry tot die 9.
So, die hoogte van hierdie boom is 3.
Ons kan dit doen dieselfde oefening vir die ander bome wat met hierdie groen uiteengesit,
en ons sien dat die hoogte van al hierdie bome is inderdaad ook 3.
Dit is deel van wat maak hulle ontaard -
dat hulle hoogte is net een minder as die aantal nodes in die hele boom.
As ons kyk na die ander boom wat omring is met rooi, aan die ander kant,
sien ons dat die mees verre blaar nodes is die 6 en die 9 -
die blare die nodes wat geen kinders het.
So, in orde te kry van die wortel node óf die 6 of 9,
ons een hop te maak om te kry aan die 7 en dan 'n tweede hop om te kry tot die 9,
en so ook, om net 'n tweede hop van die 7 aan die 6.
So, die hoogte van hierdie boom hier is net 2.
Jy kan terug gaan en doen wat vir al die ander bome wat ons voorheen bespreek
begin met die 7 en die 6,
en jy sal vind dat die hoogte van al die bome is ook 2.
>> Die rede waarom ons het gepraat oor binêre bome bestel
en hoekom hulle is cool is, want jy kan soek deur hulle in
'n soortgelyke manier om te soek oor 'n gesorteerde skikking.
Dit is waar ons praat oor om dat verbeterde lookup tyd
oor die eenvoudige geskakelde lys.
Met 'n geskakelde lys - as jy wil om 'n spesifieke element te vind -
jy by die beste gaan om 'n soort van lineêre soek om te doen
waar jy begin by die begin van 'n lys en hop een-vir-een -
een knoop deur een node -
deur die hele lys totdat jy alles wat jy op soek is na.
AANGESIEN dat, as jy 'n binêre boom wat in hierdie mooi formaat gestoor,
jy kan eintlik meer van 'n binêre soek op
waar jy verdeel en oorwin
en soek deur die toepaslike helfte van die boom by elke stap.
Kom ons kyk hoe dit werk.
>> As ons weer terug te gaan na ons oorspronklike boom -
ons begin op 7, ons het 3 aan die linkerkant, 9 aan die regterkant,
en onder die 3 het ons die 6.
As ons wil hê om te soek na die getal 6 in hierdie boom, wil ons begin by die wortel.
Ons wil vergelyk die waarde wat ons is op soek na, sê 6,
die waarde wat gestoor word in die node wat ons tans op soek is na, 7,
vind dat 6 inderdaad minder as 7, so ons wil skuif na links.
Indien die waarde van 6 was groter as 7, sou ons plaas het na regs verskuif.
Omdat ons weet dat as gevolg van die struktuur van ons bestel binêre boom -
al die waardes minder as 7 geberg gaan word aan die linkerkant van 7,
daar is geen behoefte om selfs moeite soek deur middel van die regterkant van die boom.
Wanneer ons na links beweeg en ons is nou by die node met 3,
kan ons weer dieselfde vergelyking doen waar ons dit vergelyk met die 3 en die 6.
En ons vind dat, terwyl 6 - die waarde wat ons is op soek na - is groter as 3,
ons kan gaan na die regterkant van die node met 3.
Daar is geen linkerkant hier, sodat ons kan geïgnoreer het dat.
Maar ons weet net dat omdat ons is op soek na die boom self,
en ons kan sien dat die boom het nie kinders nie.
>> Dit is ook redelik maklik om op te kyk 6 in hierdie boom as ons dit doen onsself as mense,
maar laat ons hierdie proses volg meganies soos 'n rekenaar sou doen
om regtig te verstaan ​​die algoritme.
Op hierdie punt, ons is nou op soek na 'n node bevat 6,
en ons is op soek vir die waarde 6,
ja, inderdaad, het ons gevind dat die toepaslike node.
Ons het gevind dat die waarde 6 in ons boom, en ons kan ons soek stop.
Op hierdie punt, afhangende van wat gaan aan,
ons kan sê, ja, ons die waarde 6 gevind het, dit bestaan ​​in ons boom.
Of, as ons van plan is om 'n node te voeg of om iets te doen, kan ons dit doen op hierdie punt.
>> Kom ons doen 'n paar soektogte net om te sien hoe dit werk.
Kom ons kyk wat gebeur as ons was om te probeer en kyk op die waarde 10.
As ons kyk op die waarde 10, sal ons begin by die wortel.
Ons wil sien dat 10 groter as 7, so ons wil skuif na regs.
Ons wil na die 9 en vergelyk 9 aan die 10 en sien dat 9 inderdaad minder as 10.
Dit weer doen, wil ons probeer om te beweeg na regs.
Maar op hierdie punt, wil ons sien dat ons op 'n null node.
Daar is niks. Daar is niks waar die 10 moet wees.
Dit is waar ons kan rapporteer mislukking - dat daar is inderdaad geen 10 in die boom.
En ten slotte, laat ons gaan deur middel van die geval waar ons probeer om te kyk 1 in die boom.
Dit is soortgelyk aan wat gebeur as ons kyk op 10, behalwe in plaas van gaan na regs,
ons gaan om te gaan na die linkerkant.
Ons begin by die 7 en sien dat 1 is minder as 7, so ons skuif na links.
Ons kry die 3 en sien dat 1 is minder as 3, so ons probeer weer om na links te beweeg.
Op hierdie punt het ons 'n null node, sodat ons weer kan aanmeld mislukking.
>> As jy wil meer te leer oor binêre bome,
daar is 'n hele klomp van die pret bietjie probleme wat jy kan doen met hulle.
Ek raai jou aan die beoefening van die tekening van hierdie diagramme een-vir-een
en deur al die verskillende stappe volg,
want dit sal kom in die super-handig
nie net wanneer jy doen die Huffman kodering probleem stel
maar ook in die toekomstige kursusse -
net leer hoe om te trek uit hierdie data strukture en dink deur middel van die probleme
met pen en papier, of in hierdie geval, iPad en stylus.
>> Op hierdie punt al, ons gaan om te beweeg op sommige kodering praktyk te doen
en eintlik speel met hierdie binêre bome en sien.
Ek gaan om terug te skakel na my rekenaar.
Vir hierdie deel van die artikel, in plaas van die gebruik van CS50 Run of CS50 Ruimtes,
Ek gaan om die toestel te gebruik.
>> Die volgende saam met die Problem Set spesifikasie,
Ek sien dat ek veronderstel is om oop te maak die toestel,
gaan na my Dropbox gids, skep 'n gids met die naam van Artikel 7,
en dan skep n lêer genaamd binary_tree.c.
Hier gaan ons. Ek het die toestel reeds oop.
Ek gaan trek 'n terminaal.
Ek gaan om te gaan na die Dropbox gids, maak 'n gids met die naam section7,
en sien dit is heeltemal leeg.
Nou gaan ek om oop te maak binary_tree.c.
Alright. Hier gaan ons - leeg lêer.
>> Kom ons gaan terug na die spesifikasie.
Die spesifikasie vra om 'n nuwe soort definisie te skep
vir 'n binêre boom node bevat int waardes -
net soos die waardes wat ons in ons diagram voor getrek.
Ons gaan hierdie boiler typedef te gebruik wat ons het reg hier gedoen
dat jy moet erken van Problem Set 5 -
as jy het die hash tafel weg van die verowering van die speller program.
Jy moet ook erken dit uit verlede week se artikel
waar het ons gepraat oor geskakelde lyste.
Ons het hierdie typedef van 'n struct node,
en ons het hierdie struct node naam van die struct node vooraf
sodat ons kan dan verwys na dit omdat ons sal wil struct node verwysings na
as deel van ons struct, maar ons het dan omring -
of liewer, ingesluit in 'n typedef
sodat, later in die kode, kan ons verwys na hierdie struct as net 'n knoop in plaas van 'n struct node.
>> Dit is baie soortgelyk aan die enkel-geskakelde lys definisie wat ons gesien het verlede week gaan wees.
Om dit te doen, laat ons net begin deur die skryf van die boiler.
Ons weet dat ons 'n heelgetal waarde te hê,
so sal ons in 'n int waarde, en dan in plaas van net een wyser na die volgende element -
soos ons gedoen het met 'n enkel-gekoppelde lyste -
ons gaan links en regs kind pointers te hê.
Dit is ook redelik eenvoudig - struct node * links kind;
en struct node * regte kind;. Cool.
Wat lyk soos 'n baie goeie begin.
Kom ons gaan terug na die spesifikasie.
>> Nou moet ons 'n globale node * veranderlike te verklaar vir die wortel van 'n boom.
Ons gaan hierdie globale net soos ons eerste wyser in ons geskakelde lys ook 'n wêreldwye te maak.
Dit was so dat in die funksies wat ons skryf
ons hoef nie te hou wat rondom hierdie wortel -
maar ons sal sien dat as jy wil om hierdie funksies te rekursief te skryf,
dit dalk beter wees om nie eens te slaag dit rond in die eerste plek as 'n globale
en in plaas inisialiseer dit plaaslik in jou hooffunksie.
Maar, sal ons dit doen wêreldwyd te begin.
Weereens, ons sal 'n paar van ruimtes, en ek gaan 'n node * wortel te verklaar.
Net om seker te maak dat ek nie laat dit geïnitialiseerd, ek gaan om dit te gelyk stel aan nul.
Nou, in die belangrikste funksie - wat sal ons regtig vinnig reg hier te skryf -
int main (int argc, const char * bevat SPASIES []) -
en ek gaan om te begin verklaar my bevat SPASIES skikking as const net sodat ek weet
daardie argumente is argumente dat ek waarskynlik nie wil verander nie.
As ek wil om dit te verander Ek moet seker maak afskrifte van hulle.
Jy sal sien 'n lot in die kode.
Dis boete óf manier. Dit is goed om dit te verlaat as die const weglaat as jy wil.
Ek gewoonlik sit dit in net so dat ek herinner myself
dat ek waarskynlik nie wil hê dat die argumente te verander.
>> Soos altyd, ek gaan hierdie opgawe 0 lyn aan die einde van die hoof te sluit.
Hierheen, ek sal inisialiseer my wortel node.
Soos dit staan ​​op die oomblik, ek het 'n wyser wat aan nul,
so dit is wys niks.
Ten einde om werklik te begin met die bou van die node,
Ek het eers geheue vir dit te ken.
Ek gaan om dit te doen deur die geheue op die hoop, met behulp van malloc te maak.
Ek gaan wortel gelyk aan die resultaat van malloc te stel,
en ek gaan die sizeof operator om te gebruik om die grootte van 'n node te bereken.
Die rede wat ek gebruik sizeof node, in teenstelling met, sê,
om iets te doen soos hierdie - malloc (4 + 4 +4) of malloc 12 -
is, want ek wil my kode verenigbaar as moontlik te wees.
Ek wil in staat wees om hierdie c-lêer te neem, stel dit op die toestel,
en dan stel dit op my 64-bis Mac -
of op 'n heeltemal ander argitektuur -
en ek wil dit al die dieselfde te werk.
>> As ek maak aannames oor die grootte van veranderlikes -
die grootte van 'n int of die grootte van 'n wyser -
dan is ek ook die maak van aannames oor die aard van die architecture
wat my kode suksesvol kan stel wanneer dit uitgevoer word.
Altyd gebruik sizeof, in teenstelling met die hand die WHALM struct velde.
Die ander rede is dat daar dalk ook padding dat die vertaler sit in die struct.
Selfs net 'n opsomming van die individuele velde is nie iets wat jy tipies wil om dit te doen,
so, verwyder daardie lyn.
Nou, om werklik te inisialiseer hierdie wortel node,
Ek gaan hê om te prop in die waardes vir elk van die verskillende velde.
Byvoorbeeld, vir waarde Ek weet ek wil om te inisialiseer tot 7,
en nou gaan ek te stel die linker kind te wees null
en die reg om kind te wees null. Great!
Ons gedoen het dat 'n deel van die spec.
>> Die spesifikasie aan die onderkant van die bladsy 3 vra my drie nodes te skep -
een met 3, een met 6, en een met 9 -
en dan bedraad hulle sodat dit lyk presies soos ons boomdiagram
dat ons oor gepraat het.
Kom ons doen dit redelik vinnig hier.
Jy regtig vinnig sien wat ek gaan om te begin met die skryf van 'n klomp van duplikaat-kode.
Ek gaan 'n node te skep * en ek gaan om te noem dit drie.
Ek gaan om dit gelyk te stel malloc (sizeof (node)).
Ek gaan tot drie-> waarde stel = 3.
Drie -> left_child = NULL, drie -> regs _child = NULL, asook.
Dit lyk redelik soortgelyk aan die inisialisering van die wortel, en dit is presies wat
Ek gaan te hê om te doen as ek begin inisialisering 6 en 9 asook.
Ek sal doen wat regtig vinnig hier - eintlik, ek gaan 'n bietjie kopie en plak om dit te doen,
en maak seker dat ek - alright.
Nou, ek het dit gekopieer en ek kan voort te gaan en stel dit gelyk aan 6.
Jy kan sien dat dit 'n rukkie neem en is nie super-doeltreffende.
In net 'n bietjie, sal ons skryf 'n funksie wat doen dit vir ons.
Ek wil om dit te vervang met 'n 9 is, vervang dit met 'n 6.
>> Nou het ons al van ons nodes geskep en geïnisialiseer.
Ons het ons wortel stel gelyk aan 7, of met die waarde 7,
ons node bevat 3, ons node met 6 en ons node bevat 9.
Op hierdie punt, al wat ons moet doen, is draad alles op.
Die rede waarom ek al die wenke geïnisialiseer aan nul is net sodat ek seker maak dat
Ek het nie enige geïnitialiseerd pointers daar deur 'n ongeluk.
En ook omdat, op hierdie punt, ek het net om werklik die nodusse verbind aan mekaar -
aan die mense wat hulle eintlik verbonde aan - Ek het nie om deur te gaan en maak
seker dat al die nulls is daar in die toepaslike plekke.
>> Begin by die wortel, ek weet dat die wortel se links kind is 3.
Ek weet dat die wortel se reg kind 9.
Daarna het die enigste ander kind wat ek verlaat het om oor bekommerd te wees nie
is 3 se reg kind, wat is 6.
Op hierdie punt, dit lyk redelik goed.
Ons sal verwyder sommige van hierdie lyne.
Nou is alles lyk redelik goed.
Kom ons gaan terug na ons spesifikasie en sien wat ons het om volgende te doen.
>> Op hierdie punt, ons het om te skryf 'n funksie genoem "bevat"
met 'n prototipe van 'Bool bevat (int waarde).
En dit bevat funksie gaan om terug te keer waar
indien die boom wys deur ons wêreldwye wortel veranderlike
bevat die waarde wat geslaag is in die funksie en valse anders.
Kom ons gaan voort en doen wat.
Dit gaan om presies te wees soos die lookup wat ons gedoen het met die hand op die iPad net 'n bietjie gelede.
Kom ons gaan terug zoom in 'n bietjie en scroll up.
Ons gaan hierdie funksie reg te stel bo ons hooffunksie
sodat ons nie enige soort van prototyping te doen.
So, Bool bevat (int waarde).
Daar gaan ons. Daar is ons boiler verklaring.
Net om seker te maak dat dit sal stel,
Ek gaan om voort te gaan en dit net gelykgestel vals om terug te keer.
Reg nou hierdie funksie sal net nie enigiets doen en altyd rapporteer dat
die waarde wat ons soek is nie in die boom.
>> Op hierdie punt, is dit waarskynlik 'n goeie idee -
want ons het 'n hele klomp van die kode geskryf en ons het nie eens probeer om dit te toets nog -
om seker te maak dat dit alles stel.
Daar is 'n paar van die dinge wat ons moet doen om seker te maak dat dit eintlik sal saamstel.
Eerste, kyk of ons het al met behulp van enige funksies in enige biblioteke dat ons nog nie ingesluit nie.
Die funksies wat ons tot dusver gebruik is malloc,
en dan het ons ook die gebruik van hierdie tipe - hierdie nie-standaard tipe genoem 'bool' -
wat is ingesluit in die standaard Bool header-lêer.
Ons wil beslis standaard bool.h vir die Bool tipe in te sluit,
en ons wil ook # include standaard lib.h vir die standaard biblioteke
wat insluit malloc, en vry, en al wat.
So, uitzoomen, ons gaan om te stop.
Kom ons probeer en maak seker dat dit eintlik gedoen saamstel.
Ons sien dat dit nie, so ons is op die regte pad.
>> Kom ons oopmaak binary_tree.c weer.
Dit stel. Kom ons gaan sit en maak seker dat ons voeg 'n paar oproepe vir ons bevat funksie -
net om seker te maak dat dit is alles goed en wel.
Byvoorbeeld, wanneer ons het 'n paar soektogte in ons boom vroeër,
ons probeer om te kyk op die waardes 6, 10 en 1, en ons het geweet dat 6 was in die boom,
10 in die boom was nie, en 1 was nie in die boom.
Kom ons gebruik daardie monster oproepe as 'n manier om uit te vind of
ons bevat funksie werk.
Ten einde dit te doen, ek gaan die printf funksie te gebruik,
en ons gaan uit te druk die resultaat van die oproep om te bevat.
Ek gaan sit in 'n string "bevat (% d) = omdat
ons gaan prop in die waarde wat ons gaan om te kyk vir,
en =% s \ n "en gebruik dit as ons formaat string.
Ons is net gaan om te sien - letterlik uit te druk op die skerm -
wat lyk soos 'n funksie oproep.
Dit is nie eintlik die funksie oproep.
Dit is net 'n string wat ontwerp is om te lyk soos 'n funksie oproep.
>> Nou gaan ons te prop in die waardes.
Ons gaan bevat om te probeer om op 6,
en dan wat ons gaan doen, is dat die drieledige operateur.
Kom ons kyk - bevat 6 - ja, nou het ek vervat 6 en as bevat 6 is waar,
die tou wat ons gaan om te stuur na die% s formaat karakter
gaan die string "ware".
Kom se scroll oor 'n bietjie.
Anders, ons wil stuur die string "vals" as bevat 6 opbrengste valse.
Dit is 'n bietjie stom-soek, maar ek figuur Ek kan net so goed illustreer
wat die drieledige operateur lyk, aangesien ons nie gesien het nie dit vir 'n rukkie.
Dit sal 'n mooi, handige manier om uit te vind of ons bevat funksie werk.
Ek gaan om terug te blaai na links,
en ek gaan hierdie lyn te kopieer en plak 'n paar keer.
Dit verander 'n paar van hierdie waardes rond,
so dit gaan te wees 1, en dit gaan te wees 10.
>> Op hierdie punt het ons 'n mooi bevat funksie.
Ons het 'n paar toetse, en ons sal sien of dit al die werke.
Op hierdie punt het ons meer kode geskryf.
Tyd om op te hou en maak seker dat alles steeds stel.
Sluit uit, en laat ons nou probeer om binêre boom weer.
Wel, dit lyk asof ons het 'n fout,
en ons het dit het uitdruklik verklaar dat die biblioteek funksie printf.
Dit lyk soos wat ons nodig het om in te gaan en # standardio.h sluit.
En met dié, moet alles stel. Ons is almal goed.
Laat ons nou probeer om binêre boom en kyk wat gebeur.
Hier is ons, / binary_tree.
en ons sien dat, as ons verwag -
want ons het nie geïmplementeer nie bevat nie,
of liewer, ons het net in return false -
sien ons dat dit net terugkeer vir almal van hulle vals,
so wat al die werk vir die grootste deel redelik goed.
>> Laat se rug in te gaan en werklik uit te voer bevat op hierdie punt.
Ek gaan om te blaai, zoom in en -
onthou, die algoritme wat ons gebruik het, was dat ons begin by die wortel node
en dan by elke node wat ons teëkom, het ons 'n vergelyking doen,
en wat gebaseer is op daardie vergelyking ons óf beweeg aan die linkerkant kind of aan die regterkant kind.
Dit gaan lyk baie soortgelyk aan die binêre soek kode wat ons geskryf het vroeër in die kwartaal.
Wanneer ons begin, weet ons dat ons wil om vas te hou aan die huidige node
dat ons op soek is na, en die huidige node geïnisialiseer gaan word aan die wortel node.
En nou, ons gaan om voort te gaan deur middel van die boom,
en onthou dat ons stop toestand -
wanneer ons werklik deur die voorbeeld gewerk het met die hand -
was toe ons ondervind 'n null node,
nie wanneer ons kyk na 'n null kind,
maar eerder wanneer ons eintlik na 'n nodus in die boom
en gevind dat ons op 'n null node.
Ons gaan om te itereer totdat die huidige is nie gelyk aan nul.
En wat gaan ons doen?
Ons gaan om te toets of (huidige -> waarde == waarde),
dan weet ons dat ons eintlik het die knoop gevind dat ons op soek is na.
So hier is, kan ons terugkeer waar.
Anders, ons wil om te sien of die waarde is minder as die waarde.
As die huidige node se waarde is minder as die waarde wat ons soek,
ons gaan om te beweeg na regs.
So, huidig ​​= huidige -> right_child; en andersins, ons gaan om te skuif na links.
huidig ​​= huidige -> left_child;. Eenvoudig.
>> Jy het waarskynlik besef die lus wat lyk baie soortgelyk aan dié van
binêre soek vroeër in die kwartaal nie, behalwe dan het ons te doen het met 'n lae, middel, en 'n hoë.
Hier, ons het net om te kyk na 'n huidige waarde,
so dit is lekker en maklik.
Kom ons maak seker dat hierdie kode werk.
Eerstens, maak seker dit stel. Lyk soos dit nie.
Kom ons probeer om dit te draai.
En inderdaad, dit druk uit alles wat ons verwag het.
Dit vind 6 in die boom, vind nie 10 want 10 is nie in die boom,
en dit nie vind nie 1 óf omdat 1 is ook nie in die boom.
Cool stuff.
>> Alright. Kom ons gaan terug na ons spesifikasie en sien wat is volgende.
Nou, dit wil 'n paar meer nodes te voeg aan ons boom.
Dit wil 5, 2 en 8 te voeg, en maak seker dat ons bevat kode
nog steeds werk soos verwag.
Kom ons gaan doen.
Op hierdie punt, eerder as om weer daardie irriterende kopieer en plak,
laat skryf 'n funksie om werklik 'n node.
As ons scroll down al die pad na die hoof, sien ons dat ons dit nou al doen
baie soortgelyke kode oor en oor weer elke keer wat ons wil hê om 'n node te skep.
>> Kom ons skryf 'n funksie wat eintlik 'n node bou vir ons en stuur dit terug.
Ek gaan noem dit build_node.
Ek gaan 'n node te bou met 'n spesifieke waarde.
Zoom hier.
Die eerste ding wat ek gaan doen is eintlik skep ruimte vir die node op die hoop.
So, node * n = malloc (sizeof (node)); n -> waarde = waarde;
en dan hier, is ek net gaan om al die velde te inisialiseer om toepaslike waardes.
En heel aan die einde, sal ons terugkeer ons node.
Alright. Een ding om daarop te let dat hierdie funksie is reg hier
gaan om 'n wyser terug te keer na geheue wat hoop toegewys is.
Wat is mooi oor hierdie is dat hierdie node nou -
ons het dit op die hoop te verklaar, want as ons verklaar dat dit op die stapel
sou ons nie in staat wees om dit te doen in hierdie funksie soos hierdie.
Dat die geheue sal gaan uit van die omvang
en ongeldig sou wees as ons probeer om dit later toegang.
Aangesien ons hoop toegewys geheue te verklaar,
ons gaan hê om te sorg vir bevry dit later
vir ons program nie 'n geheue lek.
Ons het die skrik vir alles anders in die kode
net vir wille van eenvoud op die oomblik,
maar as jy ooit 'n funksie wat lyk soos hierdie
waar jy het - sommige noem dit 'n malloc of realloc binne -
jy wil om seker te maak dat jy 'n soort van kommentaar hier wat sê,
hey, jy weet, gee 'n hoop-toegekende node geïnisialiseer met die vraestel-in waarde.
En dan kan jy wil om seker te maak dat jy in 'n soort van kennis wat sê
die oproeper moet bevry die terugkeer geheue.
Op dié manier, as iemand ooit gaan en gebruik daardie funksie,
weet hulle dat alles wat hulle terug te kry van daardie funksie
op 'n sekere punt sal moet word bevry.
>> Die veronderstelling dat dit is alles goed en wel hier,
ons kan gaan in ons kode en vervang alle van hierdie lyne hier
met 'n oproepe na ons build node funksie.
Kom ons doen dit regtig vinnig.
Die een deel wat ons nie gaan om te vervang, is hierdie gedeelte af hier
aan die onderkant waar ons eintlik bedraad die nodes om te wys aan mekaar,
want wat ons nie kan doen in ons funksie.
Maar, laat ons doen wortel = build_node (7); node * drie = build_node (3);
knoop * Ses = build_node (6); node * 9 = build_node (9);
En nou, ons wou ook nodes te voeg -
node * Vyf = build_node (5); node * Agt = build_node (8);
en wat was die ander node? Kom ons kyk hier. Ons wou ook 'n 2 -
node * twee = build_node (2);
Alright. Op hierdie punt, ons weet dat ons die 7, 3, 9, en die 6 het
alle bedraad gepas nie, maar wat oor die 5, 8, en die 2?
Alles in die korrekte volgorde te hou,
ons weet dat drie se reg kind is 6.
So, as ons gaan die 5 toe te voeg,
die 5 behoort ook in die regterkant van die boom waarvan 3 is die wortel,
so 5 behoort as die linker kind van 6.
Ons kan dit doen deur te sê, ses -> left_child = vyf
en dan die 8 behoort, so as die linker kind van 9 nege -> left_child = agt;
en dan 2 is die linker kind van 3, sodat ons dit kan doen hier - jou -> left_child = twee;.
As jy nie heeltemal volg nie saam met wat, ek stel voor jy trek dit uit jouself.
>> Alright. Kom ons behalwe hierdie. Kom ons gaan uit en maak seker dit stel,
en dan kan ons voeg in ons bevat oproepe.
Dit lyk asof alles nog stel.
Laat in gaan en voeg in sommige bevat oproepe.
Weereens, ek gaan 'n bietjie van kopieer en plak te doen.
Laat ons nou soek vir 5, 8 en 2. Alright.
Kom ons maak seker dat dit alles goed lyk nog steeds. Great! Stoor en sluit.
Nou laat ons saam te stel, en nou laat loop.
Uit die resultate, dit lyk asof alles werk net mooi en goed.
Great! So nou het ons ons bevat funksie geskryf.
Kom ons beweeg op en begin werk oor hoe om nodusse in die boom te voeg
want soos ons doen dit nou, dinge is nie baie mooi.
>> As ons terug gaan na die spesifikasie,
dit ons vra om te skryf van 'n funksie met die naam plaas - weer, die terugkeer van 'n Bool
of ons kan eintlik voeg die nodus in die boom -
en dan die waarde toe te voeg in die boom word gespesifiseer as
die enigste argument aan ons insert funksie.
Ons sal terugkeer waar as ons inderdaad die node wat waarde kan voeg in die boom,
wat beteken dat ons, een, genoeg geheue gehad het,
en dan twee, het daardie node nie reeds bestaan ​​in die boom sedert -
Onthou, ons gaan nie duplikaat waardes te hê in die boom, net om dinge eenvoudig.
Alright. Terug na die kode.
Oop te maak. Zoom in 'n bietjie, dan scroll down.
Kom ons stel die insetsel funksie regs bo die bevat.
Weereens, gaan dit genoem te word nie die Bool insert (int waarde).
Gee dit 'n bietjie meer ruimte, en dan as 'n standaard,
laat ons in ruil vals is heel aan die einde.
Nou af aan die onderkant, laat ons gaan voort en in plaas van die hand die bou van die nodusse
in die hoof onsself en bedrading hulle te wys aan mekaar soos ons dit doen,
sal ons staatmaak op ons insert funksie om dit te doen.
Ons sal ons nie op ons insert funksie net nog die hele boom van nuuts af te bou,
maar eerder sal ons ontslae te raak van hierdie lyne - sal ons kommentaar uit hierdie lyne -
wat bou die nodes 5, 8 en 2.
En in plaas daarvan, sal ons voeg oproepe na ons insert funksie
om seker te maak dat dit eintlik werk.
Hier gaan ons.
>> Nou het ons gedraai uit hierdie lyne.
Ons het net 7, 3, 9, en 6 in ons boom op hierdie punt.
Om seker te maak dat dit alles werk,
ons kan uitzoomen, maak ons ​​binêre boom,
loop dit, en ons kan sien wat die volgende bevat, is nou om ons te vertel dat ons is heeltemal reg -
5, 8 en 2 is nie meer in die boom.
Gaan terug in die kode,
en hoe gaan ons te voeg?
Onthou wat ons gedoen het toe ons eintlik 5 invoeging, 8 en 2 voorheen.
Ons dat Plinko spel gespeel waar ons begin by die wortel,
het die boom af een deur een vir een
totdat ons die toepaslike gaping gevind het,
en dan het ons bedraad in die knoop by die toepaslike plek.
Ons gaan dieselfde ding om te doen.
Dit is basies soos die skryf van die kode wat ons gebruik in die bevat 'n funksie
die plek waar die knoop moet wees om te vind,
en dan is ons net gaan om die knoop reg daar te voeg.
Kom ons begin om dit te doen.
>> So ons het 'n node * huidig ​​= wortel, ons is net gaan om te volg die bevat kode
totdat ons vind dat dit nie heeltemal vir ons werk.
Ons gaan om te gaan deur middel van die boom, terwyl die huidige element is nie null,
en as ons vind dat die huidige se waarde is gelyk aan die waarde wat ons probeer om te steek -
Wel, dit is een van die gevalle wat ons kan eintlik nie die node voeg
in die boom, want dit beteken dat ons het 'n duplikaat waarde.
Hier is ons eintlik gaan om terug te keer vals.
Nou, anders as huidig ​​se waarde is minder as die waarde
nou weet ons dat ons na regs beweeg
omdat die waarde behoort in die regter helfte van die huidige boom.
Anders gaan ons om te beweeg na links.
Dit is basies ons bevat funksioneer reg daar.
>> Op hierdie punt, wanneer het ons hierdie while lus voltooi,
ons huidige wyser gaan word verwys na nul
indien die funksie reeds nie terug nie.
Ons is dus met huidig ​​op die plek waar ons wil die nuwe node in te voeg.
Wat nog gedoen moet word, is om werklik die bou van die nuwe node,
wat ons kan redelik maklik te doen.
Ons kan gebruik maak van ons super-handig build node funksie,
en iets wat ons nie vroeër doen -
ons het net soort van as vanselfsprekend aanvaar, maar nou gaan ons doen net om seker te maak -
ons sal toets om seker te maak dat die waarde wat deur die nuwe node was eintlik
nie null, want ons wil nie om te begin met die toegang tot hierdie geheue as dit is van nul.
Ons kan toets om seker te maak dat die nuwe node is nie gelyk aan nul.
Of in plaas, kan ons net kyk of dit regtig is van nul,
en as dit is van nul is, dan kan ons net return false vroeg.
>> Op hierdie punt, ons het nuwe node in sy toepaslike plek in die boom te bedraad.
As ons terug kyk by die hoof en waar ons was eintlik bedrading in waardes voor,
sien ons dat die manier waarop ons dit doen wanneer ons wou 3 in die boom te sit
is ons toegang tot die linker kind van die wortel.
Wanneer ons 9 in die boom, het ons 'die regte kind van die wortel gehad het om toegang te verkry tot.
Ons het 'n wyser na die ouer te hê ten einde 'n nuwe waarde in die boom te sit.
Blaai terug te voeg, wat nie gaan baie werk hier
want ons het nie 'n ouer wyser.
Wat ons wil hê om in staat wees om dit te doen, op hierdie punt,
die ouer se waarde nagaan en sien - goed, gosh,
indien die ouer se waarde is minder as die huidige waarde,
dan is die ouer se reg kind moet die nuwe node;
andersins, moet die ouer se links kind die nuwe nodus.
Maar, ons het nie hierdie ouer wyser baie nog.
>> Ten einde dit te kry, ons eintlik gaan om dit op te spoor as ons gaan deur middel van die boom
en vind die toepaslike plek in ons lus hierbo.
Ons kan dit doen deur te blaai terug na die top van ons insert funksie
en die dop van 'n ander wyser veranderlike genoem die ouer.
Ons gaan dit op gelyke aanvanklik ingestel op nul,
en dan elke keer as ons gaan deur middel van die boom,
ons gaan die ouer wyser te stel om die huidige wyser aan te pas.
Stel ouer gelyk aan huidige.
Op hierdie manier, elke keer wat ons gaan deur,
ons gaan om te verseker dat as die huidige wyser kry geïnkrementeer
die ouer wyser volg dit - net een vlak hoër as die huidige wyser in die boom.
Dat al lyk redelik goed.
>> Ek dink die een ding wat ons sal wil hê om aan te pas is dit bou node terugkeer null.
In orde te kry bou node om werklik suksesvol null terugkeer,
ons sal hê om die kode te verander,
want hier het ons nooit getoets om seker te maak dat malloc 'n geldige wyser teruggekeer.
So, as (n = NULL), dan
indien malloc 'n geldige wyser terug, dan sal ons inisialiseer;
andersins, sal ons net teruggaan en dit sal uiteindelik terugkeer null vir ons.
Nou al lyk redelik goed. Kom ons maak seker dat dit eintlik stel.
Maak binêre boom, en oh, ons het 'n paar dinge wat hier aangaan nie.
>> Ons het 'n implisiete verklaring van funksie bou node.
Weer, met hierdie samestellers, ons gaan om te begin aan die bokant.
Wat dit moet beteken, is dat ek 'n beroep bou node voordat ek dit werklik verklaar.
Kom ons gaan terug na die kode regtig vinnig.
Scroll down, en seker genoeg, my insert funksie verklaar
bo die bou node funksie,
maar ek probeer om te gebruik node bou binnekant van insert.
Ek gaan om te gaan in en kopieer en plak die bou node funksie pad tot hier aan die bokant.
Op dié manier, hopelik wat sal werk. Kom ons gee dit 'n ander gaan.
Nou is dit almal stel. Alles is goed.
>> Maar op hierdie punt, het ons nie eintlik ons ​​insert funksie genoem.
Ons weet net dat dit stel, so laat in gaan en sit n paar oproepe.
Kom ons doen dit in ons belangrikste funksie.
Hier, het ons opgemerk 5, 8 en 2,
en dan het ons nie bedraad hulle hier neer.
Kom ons maak 'n paar oproepe te voeg,
en laat ons ook gebruik maak van die dieselfde soort van dinge wat ons gebruik
wanneer ons hierdie printf oproepe gemaak om seker te maak dat alles het behoorlik te plaas.
Ek gaan om te kopieer en plak,
en in plaas van bevat ons gaan insetsel te doen.
En in plaas van 6, 10 en 1, gaan ons 5, 8 en 2 te gebruik.
Dit behoort hopelik voeg 5, 8 en 2 in die boom.
Stel. Alles is goed. Nou het ons ons program sal eintlik loop.
>> Alles teruggekeer vals.
So, 5, 8 en 2 gaan nie, en dit lyk asof bevat het hulle nie vind nie óf.
What's going on? Kom ons uitzoomen.
Die eerste probleem was dat insetsel was om terug te keer vals,
en dit lyk soos dit is, want ons het in ons terugkeer vals oproep,
en ons het nooit werklik teruggekeer waar.
Ons kan dit op.
Die tweede probleem is nou selfs as ons dit doen - Hou hierdie, stop hierdie,
hardloop maak weer, stel dit het, dan loop dit -
sien ons dat daar iets anders hier gebeur.
Die 5, 8 en 2 was nog nooit gevind in die boom.
So, wat gaan aan?
>> Kom ons neem 'n blik op hierdie in die kode.
Kom ons kyk of ons kan dit uit figuur.
Ons begin met die ouer nie null.
Ons stel die huidige wyser gelyk aan die wortel pointer,
en ons gaan ons manier om te werk deur middel van die boom af.
Indien die huidige Nodus nie NULL is, dan weet ons dat ons kan beweeg 'n bietjie af.
Ons stel ons ouer wyser te wees gelyk aan die huidige wyser,
kyk na die waarde - as die dieselfde waardes belangrik is ons terug vals.
Indien die waardes is minder het ons verhuis na regs;
andersins, het ons verhuis na links.
Dan sal ons die bou van 'n node. Ek sal zoom in 'n bietjie.
En hier, ons gaan om te probeer om te bedraad die waardes dieselfde wees.
What's going on? Kom ons kyk indien moontlik Valgrind kan gee vir ons 'n wenk.
>> Ek hou van Valgrind te gebruik net omdat regtig vinnig Valgrind lopies
en vir jou vertel as daar 'n geheue foute.
Wanneer ons loop Valgrind op die kode,
soos jy kan sien reg here--Valgrind./binary_tree--and druk enter.
Jy sien dat ons nie 'n geheue fout, sodat dit lyk asof alles is goed so ver.
Ons doen 'n paar geheue lekkasies, wat ons weet, want ons is nie
gebeur enige van ons nodes te bevry.
Kom ons probeer om GDB om te sien wat werklik aangaan.
Ons sal doen gdb / binary_tree. Dit geselflaai net 'n boete.
Kom ons stel 'n breek punt op die insetsel.
Kom ons loop.
Dit lyk soos ons nog nooit eintlik genoem insetsel.
Dit lyk soos die probleem was net dat wanneer ek verander hier in hoof -
al van hierdie printf oproepe van bevat -
Ek het nooit werklik verander hierdie insetsel te roep.
Nou laat ons gee dit 'n probeer. Kom ons stel.
Alles lyk goed daar. Laat ons nou probeer om dit te draai, kyk wat gebeur.
Alright! Alles lyk redelik goed daar.
>> Die laaste ding om oor te dink is, is daar 'n rand gevalle tot hierdie insetsel?
En dit blyk dat, wel, die een kant geval dit is altyd interessant om te dink oor
is, wat gebeur as jou boom is leeg en jy noem dit insert funksie?
Sal dit werk? Wel, laat ons gee dit 'n probeer.
- Binary_tree c.
Die manier waarop ons gaan om dit te toets, ons gaan om te gaan na ons hooffunksie,
en eerder as bedrading hierdie nodes soos hierdie,
ons is maar net gaan om kommentaar te lewer uit die hele ding,
en in plaas van die bedrading op die nodes onsself,
Ons kan eintlik net voort te gaan en verwyder al hierdie dinge.
Ons gaan alles 'n oproep te voeg.
So, laat ons doen - in plaas van 5, 8 en 2, ons gaan 7 in te voeg, 3 en 9.
En dan sal ons ook wil 6 om so goed te voeg.
Red. Afsluit. Maak binêre boom.
Dit stel al nie.
Ons kan nie net loop dit en kyk wat gebeur,
maar dit is ook werklik belangrik gaan wees om seker te maak dat
ons het nie 'n geheue foute,
want dit is een van ons rand gevalle wat ons weet.
>> Kom ons maak seker dat dit goed werk onder Valgrind,
wat ons sal doen deur net loop Valgrind / binary_tree.
Dit lyk of ons inderdaad een fout van een konteks -
ons het hierdie segmentering skuld.
Wat het gebeur?
Valgrind vertel ons waar dit is.
Zoem uit 'n bietjie.
Dit lyk soos dit gebeur in ons insert funksie,
waar ons het 'n ongeldige lees van grootte 4 insert line 60.
Kom ons gaan terug en kyk wat gaan hier aan.
Zoem uit regtig vinnig.
Ek wil om seker te maak dat dit nie gaan na die rand van die skerm, sodat ons alles kan sien.
Trek wat in 'n bietjie. Alright.
Scroll down, en die probleem is reg hier.
Wat gebeur as ons af en ons huidige node is reeds null,
ons voorgangernode null, so as ons kyk op na die heel boonste, reg hier -
indien hierdie while lus nooit voer eintlik
omdat ons huidige waarde null - ons wortel null, sodat die huidige is null
dan is ons ouer nooit kry ingestel op die huidige of 'n geldige waarde,
so, ouer sal ook null.
Ons moet onthou om te kyk vir
teen die tyd kry ons hier af, en ons begin met die toegang tot die ouer se waarde.
So, wat gebeur? Wel, as die ouer is van nul -
if (ouer == null) - dan weet ons dat
moet daar nie iets in die boom.
Ons moet probeer om dit te voeg by die wortel.
Ons kan dit doen deur net die opstel van die wortel gelyk aan die nuwe node.
Toe, op hierdie punt, het ons nie eintlik wil hê om te gaan deur middel van hierdie ander dinge.
In plaas daarvan, reg hier, kan ons doen, hetsy 'n anders-as-anders,
of ons kan kombineer alles hier in 'n ander,
maar hier het ons sal net anders gebruik en dit doen.
Nou gaan ons om te toets om seker te maak dat ons ouer nie, is van nul
voor dan eintlik probeer om sy buiteveld om toegang te verkry tot.
Dit sal ons help vermy die segmentering skuld.
So, ons ophou, uitzoomen, stel, hardloop.
>> Geen foute, maar ons het nog 'n klomp van die geheue lekkasies
omdat ons nie vry om enige van ons nodes.
, Maar as ons gaan hier en ons kyk na ons uitdruk,
sien ons dat, wel, lyk soos almal van ons inserts terugkeer waar is, wat goed is.
Die insetsels is alles waar,
en dan die toepaslike bevat oproepe is ook waar.
>> Goeie werk! Dit lyk soos ons het suksesvol insert geskryf.
Dit is al wat ons het vir hierdie week se Problem Set spesifikasie.
Een pret uitdaging om oor na te dink, is hoe jy regtig sou gaan
en vry al die nodes in hierdie boom.
Ons kan 'n aantal verskillende maniere om dit te doen,
maar ek sal laat dat aan jou om te eksperimenteer,
en as 'n prettige uitdaging, probeer en maak seker dat jy kan seker maak
dat hierdie Valgrind verslag gee geen foute en geen lekkasies.
>> Sterkte op hierdie week se Huffman kodering probleem stel,
en ons sien julle volgende week!
[CS50.TV]