[Powered by Google Translate] [§ 7] [mindre komfortable]
[Nate Hardison] [Harvard University]
[Dette er CS50.] [CS50.TV]
>> Velkommen til § 7.
Takk til orkan Sandy,
stedet for å ha en normal seksjon denne uken,
vi gjør dette walk-through, gjennom den delen av spørsmål.
Jeg kommer til å følge sammen med oppgavesettet 6 Spesifikasjon,
og gå gjennom alle spørsmålene i
En seksjon av spørsmål delen.
Hvis det er noen spørsmål,
kan du legge disse på CS50 diskutere.
>> Alright. La oss komme i gang.
Akkurat nå er jeg ser på side 3 av oppgavesettet Specification.
Vi skal først begynne å snakke om binære trær
siden de har mye relevans til denne ukens problem set -
den Huffman Tre koding.
En av de aller første datastrukturer vi snakket om på CS50 var tabellen.
Husk at en matrise er en sekvens av elementer -
alle av samme type - lagret rett ved siden av hverandre i minnet.
Hvis jeg har et heltall matrise som jeg kan tegne med dette bokser-nummer-heltall stil -
Si la oss har jeg 5 i den første boksen, jeg har 7 i den andre,
da har jeg 8, 10, og 20 i den endelige boksen.
Husk at to virkelig gode ting om denne tabellen
er at vi har dette konstant tid tilgang til noen bestemt element
i rekken hvis vi vet sin indeks.
For eksempel, hvis jeg ønsker å ta tak i tredje elementet i matrisen -
på indeksen 2 ved hjelp av vår null-indeksering system -
Jeg bokstavelig talt bare nødt til å gjøre en enkel matematisk beregning,
hoppe til den posisjonen i matrisen,
trekke ut 8 som er lagret der,
og jeg er god til å gå.
>> En av de dårlige tingene om denne tabellen - som vi snakket om
når vi diskuterte knyttet lister -
er at hvis jeg ønsker å sette et element i denne matrisen,
Jeg kommer til å gjøre noen flytter rundt.
For eksempel, denne matrise her
er i sortert rekkefølge - sorteres i stigende rekkefølge -
5, 7, deretter deretter 8, deretter 10, og deretter 20 -
men hvis jeg ønsker å sette inn tallet 9 i denne matrisen,
Jeg kommer til å skifte noen av elementene for å gjøre plass.
Vi kan trekke ut av dette her.
Jeg kommer til å flytte 5, den 7, og deretter 8;
skape et gap der jeg kan sette 9,
og deretter 10 og 20 kan gå til høyre for 9.
Dette er en slags smerte fordi i verste fall -
når vi har å sette enten i begynnelsen eller på slutten
av tabellen, avhengig av hvor vi skifter -
Vi kan ende opp med å skifte alle elementene
som vi for tiden lagring i rekken.
>> Så, hva var vei rundt dette?
Veien rundt dette var å gå til vår koblet-liste metode der -
stedet for å lagre elementene 5, 7, 8, 10 og 20 alle ved siden av hverandre i minne -
hva vi i stedet gjorde var lagre dem slags uansett hvor vi ønsket å lagre dem
i disse lenket liste noder som jeg tegner her ute, type ad hoc.
Og da vi koblet dem sammen ved hjelp av disse neste pekere.
Jeg kan ha en peker fra 5 til 7,
en peker fra 7 til 8,
en peker fra 8 til 10,
og til slutt, en peker fra 10 til 20,
og deretter en nullpeker på 20 indikerer at det er ingenting igjen.
Trade-off som vi har her
er at nå hvis vi ønsker å sette inn tallet 9 i vår sortert liste,
alt vi trenger å gjøre er å opprette en ny node med 9,
wire det opp til å peke til riktig sted,
og deretter re-ledning 8 til peke ned til 9.
Det er ganske fort, forutsatt at vi vet nøyaktig hvor vi vil sette inn 9.
Men trade-off i bytte for dette er at vi nå har mistet konstant-time tilgang
til noen bestemt element i vår datastruktur.
For eksempel, hvis jeg ønsker å finne det fjerde elementet i denne lenket liste,
Jeg kommer til å starte på begynnelsen av listen
og jobbe meg gjennom telling node-by-node før jeg finner den fjerde.
>> For å få bedre tilgang ytelse enn en lenket liste -
men også beholde noen av fordelene som vi hadde
i form av innsetting-tid fra en lenket liste -
et binært tre er nødt til å bruke litt mer minne.
Spesielt, i stedet for bare å ha en pekeren i et binært tre node -
som den koblede-listen node gjør -
Vi kommer til å legge en ny peker til binærtreet node.
Snarere enn bare å ha en peker til neste element,
Vi kommer til å ha en peker til en venstre barn og høyre barn.
>> La oss tegne et bilde for å se hva som faktisk ser ut.
Igjen, jeg kommer til å bruke disse bokser og piler.
En binær tre node vil starte med bare en enkel boks.
Det kommer til å ha en plass for verdien,
og da er det også kommer til å ha en plass for venstre barn og høyre barnet.
Jeg kommer til å merke dem her.
Vi kommer til å ha venstre barnet, og da vi kommer til å ha den rette barnet.
Det er mange forskjellige måter å gjøre dette.
Noen ganger for plass og komfort,
Jeg vil faktisk trekke det ut som jeg gjør her på bunnen
hvor jeg kommer til å ha verdien på toppen,
og deretter høyre barnet på nederst til høyre,
og venstre barnet på nederste venstre.
Gå tilbake til denne toppdiagrammet,
Vi har verdien på toppen,
så har vi den venstre barnet peker, og så har vi rett-barn pekeren.
>> I oppgavesettet Specification,
vi snakker om å tegne en node som har en verdi 7,
og deretter en venstre-barn peker som er null, og en høyre-barn peker som er null.
Vi kan enten skrive kapital NULL i feltet for
både venstre barnet og rett barnet, eller vi kan trekke denne diagonal strek
gjennom hver av boksene for å indikere at det er null.
Jeg kommer til å gjøre det bare fordi det er enklere.
Hva du ser her er to måter å diagramfunksjonen en veldig enkel binærtreet node
hvor vi har verdien 7 og null barn pekere.
>> Den andre delen av våre spesifikasjoner snakker om hvordan med koblede lister -
Husk, vi bare måtte holde på den aller første element i en liste
å huske hele listen -
og likeledes med en binær tre, vi bare nødt til å holde på til en peker til treet
for å opprettholde kontroll over hele datastrukturen.
Denne spesielt element av treet kalles rotnoden av treet.
For eksempel, hvis denne en node - denne noden som inneholder verdien 7
med null venstre-og høyre-barn pekere -
var den eneste verdien i treet vårt,
da dette ville være vår rotnoden.
Det er helt i begynnelsen av treet vårt.
Vi kan se dette litt mer tydelig når vi begynner å legge flere noder til treet vårt.
La meg trekke opp en ny side.
>> Nå skal vi tegne et tre som har 7 ved roten,
og 3 innsiden av venstre barnet, og 9 innsiden av høyre barnet.
Igjen, dette er ganske enkel.
Vi har 7, tegne en node for 3, en node for 9,
og jeg kommer til å sette venstre barnet peker på 7 for å peke på noden som inneholder 3,
og rett-barnet pekeren til noden som inneholder 7 til noden inneholder 9.
Nå, siden 3 og 9 ikke har noen barn,
vi kommer til å sette alle sine barn pekere til å være null.
Her svarer roten av treet vårt til noden som inneholder antall 7.
Du kan se at hvis alt vi har er en peker til at rotnoden,
Vi kan da gå gjennom treet vårt og tilgang til begge barn noder -
både 3 og 9.
Du trenger ikke å opprettholde pekere til hver enkelt node på treet.
Alright. Nå skal vi legge til en annen node i dette diagrammet.
Vi kommer til å legge en node som inneholder 6,
og vi kommer til å legge dette som retten barnet til noden som inneholder 3.
For å gjøre det, kommer jeg til å slette den nullpeker i 3-node
og wire det opp til å peke på noden som inneholder seks. Alright.
>> På dette punktet, la oss gå over en liten bit av terminologi.
Hvis du vil starte, grunnen til at dette kalles en binær tre i særdeleshet
er at den har to barn pekere.
Det finnes andre typer trær som har flere barn pekere.
Spesielt, du gjorde en "prøve" i oppgave Set 5.
Du vil merke at i det prøve, hadde du 27 forskjellige pekere til forskjellige barn -
en for hver av de 26 bokstavene i det engelske alfabetet,
og deretter den 27. for apostrof -
Så, det er lik en type tre.
Men her, siden det er binært, vi har bare to barn pekere.
>> I tillegg til dette rotnode som vi snakket om,
Vi har også vært å kaste rundt dette begrepet barnet.
Hva betyr det for en node å være barn av en annen node?
Det betyr bokstavelig talt at et barn node er et barn av en annen node
hvis det andre node har en av sine underordnede pekere satt til å peke til den noden.
For å sette dette inn i mer konkrete termer,
hvis 3 fremheves av en av de underordnede pekere på 7, og deretter 3 er et barn av 7.
Hvis vi skulle finne ut hva barn 7 er -
vel, ser vi at 7 har en peker til 3 og en peker til 9,
så 9 og 3 er barn av 7.
Ni har ingen barn fordi underordnede pekere er null,
og 3 har bare ett barn, 6.
Seks har heller ingen barn fordi begge sine pekere er null, som vi vil trekke akkurat nå.
>> I tillegg har vi også snakke om foreldrene til en bestemt node,
og dette er, som du forventer, det motsatte av dette barnet beskrivelse.
Hver node har bare én forelder - i stedet for to som du kanskje forventer med mennesker.
For eksempel er den overordnede av 3 7.
Foreldre av 9 er også 7, og den overordnede av 6 er 3. Ikke mye til det.
Vi har også vilkår for å snakke om besteforeldre og barnebarn,
og mer generelt snakker vi om forfedrene
og etterkommere av en bestemt node.
Stamfar en node - eller forfedre, snarere av en node -
er alle nodene som ligger på banen fra roten til noden.
For eksempel, hvis jeg ser på noden 6,
da forfedrene kommer til å være både 3 og 7.
Forfedrene til 9, for eksempel, er - hvis jeg ser på noden 9 -
da stamfar 9 er bare 7.
Og etterkommere er nøyaktig det motsatte.
Hvis jeg ønsker å se på alle etterkommere av 7,
så jeg må se på alle nodene under den.
Så har jeg 3, 9 og 6 alle som etterkommere av 7.
>> Den endelige begrep som vi skal snakke om er denne forestillingen om å være et søsken.
Søsken - type følge med på disse familiemedlemmene vilkår -
er noder som er på samme nivå i treet.
Så, 3 og 9 er søsken fordi de er på samme nivå i treet.
De begge har samme overordnede, 7.
Den 6 har ingen søsken fordi 9 ikke har noen barn.
Og 7 ikke har noen søsken fordi det er roten av treet vårt,
og det er bare noen gang en rot.
For 7 for å ha søsken det måtte være en node over 7.
Det må være en forelder av 7, i hvilket tilfelle 7 ville ikke lenger være roten av treet.
Så at ny forelder av 7 ville også ha et barn,
og at barnet ville da være søsken av 7.
>> Alright. Flytte på.
Da vi startet vår diskusjon av binære trær,
Vi snakket om hvordan vi skulle bruke dem til
få en fordel over begge arrays og koblede lister.
Og måten vi skal gjøre det på er med dette bestiller eiendom.
Vi sier at en binær treet er bestilt, i henhold til spesifikasjonen,
hvis for hver node i treet vårt, alle sine etterkommere til venstre -
venstre barn og alle av venstre barnets etterkommere -
har mindre verdier, og alle nodene i høyre -
rett barnet og alle høyre barnets etterkommere -
har noder større enn verdien av gjeldende node som vi ser på.
Bare for enkelhet, vi kommer til å anta at det ikke er noen dupliserte noder i treet vårt.
For eksempel, i dette treet ikke vi kommer til å behandle saken
hvor vi har verdien 7 ved roten
og da har vi også ha verdi 7 andre steder i treet.
I dette tilfellet, vil du legge merke til at dette treet er faktisk bestilt.
Vi har verdien 7 ved roten.
Alt til venstre for 7 -
hvis jeg angre alle disse små merkene her -
alt til venstre for 7 - 3 og 6 -
disse verdiene er begge mindre enn 7, og alt til høyre - som er nettopp dette 9 -
er større enn 7.
>> Dette er ikke den eneste bestilles treet inneholder disse verdiene,
men la oss trekke noen flere av dem.
Det er faktisk en hel haug med måter som vi kan gjøre dette.
Jeg kommer til å bruke en kortform bare for å holde ting enkelt hvor -
stedet for å trekke ut hele bokser-og-piler -
Jeg bare kommer til å trekke tallene og legge til piler som forbinder dem.
Å starte, vi vil bare skrive vår opprinnelige treet igjen der vi hadde 7, og deretter en 3,
og deretter 3 pekte tilbake til høyre til 6,
og 7 hadde rett barn som var 9.
Alright. Hva er en annen måte at vi kunne skrive dette treet?
Stedet for å ha tre være venstre barnet av 7,
vi kan også ha 6 være den venstre barnet av 7,
og deretter 3 være den venstre barn av 6.
Det ville se ut som dette treet rett her hvor jeg har fått 7,
deretter 6, deretter 3, og en 9 på høyre side.
Vi har heller ikke til å ha 7 som vår rotnoden.
Vi kunne også ha 6 som vår rotnoden.
Hva ville det se ut?
Hvis vi skal opprettholde denne bestilles eiendom,
alt til venstre for de 6 må være mindre enn den.
Det er bare én mulighet, og det er tre.
Men da som riktig barn av 6, har vi to muligheter.
Først kunne vi ha 7 og deretter 9,
eller vi kan tegne det - som jeg er i ferd med å gjøre her -
hvor vi har 9 som høyre barn av 6,
og deretter 7 som venstre barn av 9.
>> Nå, 7 og 6 er ikke de eneste mulige verdier for roten.
Vi kunne også ha tre være på roten.
Hva skjer hvis 3 er ved roten?
Her, det blir litt interessant.
Tre ikke har noen verdier som er mindre enn det,
slik at hele venstre side av treet er bare kommer til å være null.
Det er ikke til å være noe der.
Til høyre kan vi liste ting i stigende rekkefølge.
Vi kunne ha 3, deretter 6, så 7, deretter 9.
Eller, vi kunne gjøre 3, deretter 6, deretter 9, deretter 7.
Eller, vi kunne gjøre 3, deretter 7, deretter 6, deretter 9.
Eller, 3, 7 - faktisk nei, vi kan ikke gjøre en 7 lenger.
Det er vår eneste der.
Vi kan gjøre 9, og deretter fra 9 kan vi gjøre 6 og deretter 7.
Eller vi kan gjøre 3, deretter 9, deretter 7, og deretter 6.
>> En ting å trekke oppmerksomheten din til her er
at disse trærne er litt merkelig utseende.
Spesielt hvis vi ser på de fire trærne på høyre side -
Jeg skal sirkle dem, her -
disse trærne ser nesten akkurat ut som en lenket liste.
Hver node har bare ett barn,
og slik at vi ikke har noe av dette trelignende struktur som vi ser, for eksempel,
i dette en ensom treet over her nederst til venstre.
Disse trærne er faktisk kalt degenerert binære trær,
og vi skal snakke om disse mer i fremtiden -
spesielt hvis du går på å ta andre informatikk kurs.
Disse trærne er degenerert.
De er ikke veldig nyttig fordi, ja, gir denne strukturen selv
å slå ganger ligner den av en lenket liste.
Vi får ikke til å dra nytte av den ekstra minne - denne ekstra spisser -
på grunn av strukturen vår er dårlig på denne måten.
Snarere enn å gå på og trekke ut de binære trær som har 9 ved roten,
som er den siste tilfelle at vi ville ha,
vi er i stedet, på dette punktet, kommer til å snakke litt om dette andre uttrykket
at vi bruker når vi snakker om trær, som kalles høyden.
>> Høyden av et tre er avstanden fra roten til den mest-fjern node,
eller snarere antall hopp som du ville ha å gjøre for å
starte fra roten og deretter ende opp på den mest fjerntliggende node i treet.
Hvis vi ser på noen av disse trærne som vi har trukket akkurat her,
Vi kan se at hvis vi tar dette treet i øverste venstre hjørne, og vi starter på 3,
da må vi gjøre en hop for å komme til 6, en andre hopp for å komme til 7,
og en tredje hop for å komme til 9.
Så, er høyden på dette treet 3.
Vi kan gjøre den samme øvelsen for de andre trærne skissert med denne grønne,
og vi ser at høyden av alle disse trærne er også faktisk tre.
Det er en del av det som gjør dem utarte -
at deres høyde er bare en mindre enn antall noder i hele treet.
Hvis vi ser på dette andre tre som er omkranset med rød, på den annen side,
vi ser at de mest-fjernt løvnodene er 6 og 9 -
bladene er disse nodene som ikke har barn.
Så, for å få fra rotnoden til enten 6 eller 9,
Vi har å gjøre ett hopp for å komme til 7 og deretter en andre hop for å komme til 9,
og likeledes, til bare en andre hopp fra 7 komme til 6.
Så, er høyden på dette treet over her bare 2.
Du kan gå tilbake og gjøre det for alle de andre trærne som vi tidligere diskutert
begynner med 7 og 6,
og du vil finne at høyden på alle disse trærne er også to.
>> Grunnen til at vi har snakket om bestilte binære trær
og hvorfor de er kule er fordi du kan søke gjennom dem i
en svært lik måte å søke over en sortert array.
Det er her vi snakker om å få det bedre lookup tid
over enkle lenket liste.
Med en lenket liste - hvis du ønsker å finne et bestemt element -
du er i beste fall kommer til å gjøre noen form for lineær søk
hvor du starter i begynnelsen av en liste og hop en etter en -
en node ved en node -
gjennom hele listen til du finner det du leter etter.
Mens hvis du har en binær tre som er lagret i denne hyggelig format,
du kan faktisk få mer av et binært søk skjer
hvor du splitt og hersk
og søke gjennom den riktige halvdel av treet på hvert trinn.
La oss se hvordan det fungerer.
>> Hvis vi har - igjen, gå tilbake til vårt opprinnelige treet -
vi starter på 7, har vi 3 på venstre, 9 på høyre side,
og under 3 har vi 6.
Hvis vi ønsker å søke etter nummer 6 i dette treet, ville vi begynne ved roten.
Vi vil sammenligne verdien vi leter etter, sier 6,
til verdien lagret i noden som vi for tiden ser på, 7,
finner ut at 6 er faktisk mindre enn 7, så vi ville flytte til venstre.
Hvis verdien av 6 hadde vært større enn 7, ville vi ha flyttet istedet til høyre.
Siden vi vet at - på grunn av strukturen i vårt bestilt binærtreet -
alle verdier mindre enn 7 kommer til å bli lagret på venstre side av 7,
det er ikke nødvendig å selv bry ser gjennom høyre side av treet.
Når vi flytter til venstre og vi er nå på noden som inneholder 3,
vi kan gjøre det samme sammenligning igjen der vi sammenligner 3 og 6.
Og vi finner at mens 6 - verdien vi leter etter - er større enn 3,
vi kan gå til høyre side av noden som inneholder 3.
Det er ingen venstre side her, så vi kunne ha ignorert det.
Men vi vet bare at fordi vi ser på selve treet,
og vi kan se at treet ikke har barn.
>> Det er også ganske lett å slå opp 6 i dette treet hvis vi gjør det selv som mennesker,
men la oss følge denne prosessen mekanisk som en datamaskin ville gjøre
å virkelig forstå algoritmen.
På dette punktet, er vi nå ser på en node som inneholder 6,
og vi leter etter verdien 6,
så, ja, vi har funnet den riktige noden.
Vi fant verdien 6 i treet vårt, og vi kan stoppe våre søk.
På dette punktet, avhengig av hva som skjer,
vi kan si, ja, vi har funnet verdien 6, eksisterer det i treet vårt.
Eller, hvis vi planlegger å sette inn en node eller gjøre noe, kan vi gjøre det på dette punktet.
>> La oss gjøre et par flere oppslag bare for å se hvordan dette fungerer.
La oss se på hva som skjer hvis vi skulle prøve og se opp verdien 10.
Hvis vi skulle slå opp verdien 10, vil vi begynne med roten.
Vi vil se at 10 er større enn 7, så vi vil flytte til høyre.
Vi vil komme til 9 og sammenligne 9 til 10 og se at 9 er faktisk mindre enn 10 år.
Så igjen, vi ville prøve å flytte til høyre.
Men på dette punktet, ville vi legge merke til at vi er på en null node.
Det er ingenting der. Det er ingenting der 10 skal være.
Det er der vi kan rapportere feil - at det er faktisk ingen 10 i treet.
Og til slutt, la oss gå gjennom saken der vi prøver å slå opp en i treet.
Dette er i likhet med hva som skjer hvis vi ser opp 10, unntatt i stedet for å gå til høyre,
vi kommer til å gå til venstre.
Vi starter på 7 og se at 1 er mindre enn 7, så vi beveger seg mot venstre.
Vi kommer til 3 og se at en er mindre enn 3, så igjen vi prøver å flytte til venstre.
På dette punktet har vi en null node, så igjen vi kan rapportere feil.
>> Hvis du ønsker å lære mer om binære trær,
det er en hel haug med morsomme små problemer som du kan gjøre med dem.
Jeg foreslår å praktisere tegningen ut av disse diagrammene én etter én
og følge gjennom alle de forskjellige trinnene,
fordi dette vil komme i super-hendig
ikke bare når du gjør Huffman koding oppgavesettet
men også i fremtidige kurs -
bare lære å trekke ut disse datastrukturer og tenke gjennom problemene
med penn og papir, eller i dette tilfellet, iPad og pekepenn.
>> På dette punktet skjønt, vi kommer til å gå videre for å gjøre noen kodepraksis
og faktisk spille med disse binære trær og se.
Jeg kommer til å bytte tilbake over til datamaskinen min.
For denne delen av seksjonen, i stedet for å bruke CS50 Run eller CS50 Spaces,
Jeg kommer til å bruke apparatet.
>> Følge sammen med oppgavesettet spesifikasjonen,
Jeg ser at jeg skal åpne opp maskinen,
gå til min Dropbox mappen oppretter du en mappe som heter § 7,
og deretter opprette en fil som heter binary_tree.c.
Here we go. Jeg har apparatet allerede åpen.
Jeg skal trekke opp en terminal.
Jeg kommer til å gå til Dropbox-mappen, lage en katalog som heter section7,
og se at det er helt tomt.
Nå skal jeg åpne opp binary_tree.c.
Alright. Here we go - tom fil.
>> La oss gå tilbake til spesifikasjonen.
Spesifikasjonen ber å lage en ny type definisjon
for en binær tre node som inneholder int verdier -
akkurat som de verdier som vi trakk ut i vår diagramfunksjonen før.
Vi kommer til å bruke denne standardtekst typedef at vi har gjort her
at du bør kjenne igjen fra Problem Set 5 -
hvis du gjorde hash table måte å erobre stavekontroll program.
Du bør også kjenne det fra forrige ukes delen
der vi snakket om koblede lister.
Vi har fått denne typedef av en struct node,
og vi har gitt denne struct node dette navnet på struct node forhånd
slik at vi kan deretter henvise til den siden vi ønsker å ha struct node pekere
som en del av struct vår, men vi har da omringet dette -
eller rettere sagt, vedlagt dette - i en typedef
slik at senere i koden, kan vi vise til denne struct som bare en node i stedet for en struct node.
>> Dette kommer til å være svært lik den enkeltvis-lenket liste definisjon som vi så i forrige uke.
For å gjøre dette, la oss bare begynne med å skrive ut standardteksten.
Vi vet at vi må ha et heltall,
så vil vi sette i int verdi, og deretter i stedet for å ha bare én pekeren til neste element -
som vi gjorde med enkeltvis-koblede lister -
Vi kommer til å ha venstre og høyre barn pekere.
Det er ganske enkel også - struct node * venstre barn;
og struct node * høyre barn;. Cool.
Det ser ut som en ganske god start.
La oss gå tilbake til spesifikasjonen.
>> Nå trenger vi å erklære en global node * variabel for roten av et tre.
Vi kommer til å gjøre dette globale, akkurat som vi gjorde første pekeren i vår lenket liste også global.
Dette var slik at i de funksjoner som vi skriver
Vi trenger ikke å holde passerer rundt denne roten -
selv om vi vil se at hvis du ønsker å skrive disse funksjonene rekursivt,
det kan være bedre å ikke engang passerer det rundt som en global i første omgang
og i stedet starte den lokalt på din viktigste funksjon.
Men, vi gjør det globalt for å starte.
Igjen, vil vi gi et par plasser, og jeg kommer til å erklære en node * rot.
Bare for å være sikker på at jeg ikke la dette initialisert, kommer jeg til å sette den lik null.
Nå, i den viktigste funksjonen - som vi skal skrive veldig raskt akkurat her -
int main (int argc, const char * argv []) -
og jeg kommer til å begynne å erklære min argv array som const akkurat slik at jeg vet
at disse argumentene er argumenter som jeg sannsynligvis ikke vil endre.
Hvis jeg ønsker å endre dem jeg bør nok være å lage kopier av dem.
Du vil se dette mye i kode.
Det er greit uansett. Det er greit å la den være som - utelate const hvis du ønsker.
Jeg vanligvis sette den i akkurat slik at jeg minne meg selv
at jeg sannsynligvis ikke vil endre disse argumentene.
>> Som alltid, jeg kommer til å inkludere denne avkastningen 0-linje på slutten av main.
Her vil jeg starte min rotnoden.
Som det står akkurat nå, har jeg fått en peker som er satt til null,
så den peker på noe.
For å faktisk begynne å bygge noden,
Jeg må først allokere minne for det.
Jeg kommer til å gjøre det ved å gjøre minne på haugen med malloc.
Jeg kommer til å sette root lik resultatet av malloc,
og jeg kommer til å bruke sizeof operatør å beregne størrelsen på en node.
Grunnen til at jeg bruker sizeof node i motsetning til, si,
gjøre noe som dette - malloc (4 + 4 +4) eller malloc 12 -
er fordi jeg vil at min kode for å være så kompatibelt som mulig.
Jeg ønsker å være i stand til å ta dette. C-fil, kompilere den på apparatet,
og deretter kompilere den på min 64-bit Mac -
eller på en helt annen arkitektur -
og jeg ønsker alt dette til å fungere det samme.
>> Hvis jeg gjør antagelser om størrelsen på variablene -
størrelsen på en int eller størrelsen av en peker -
da jeg også gjøre antagelser om hva slags arkitekturer
som min kode kan lykkes kompilere når du kjører.
Bruk alltid sizeof i motsetning til manuelt summere struct feltene.
Den andre grunnen er at det kan også være padding at kompilatoren setter inn i struct.
Selv bare summere de enkelte feltene er ikke noe som du vanligvis ønsker å gjøre,
så, slette den linjen.
Nå, for å virkelig klargjøre dette rotnoden,
Jeg kommer til å plugge inn verdier for hver av sine ulike felt.
For eksempel, for verdien jeg vet jeg vil initialisere til 7,
og for nå skal jeg sette den venstre barnet å være null
og retten barnet også være null. Flott!
Vi har gjort det en del av spec.
>> Spesifikasjonen ned på bunnen av side 3 ber meg om å opprette tre flere noder -
en inneholdende 3, en inneholdende 6, og en med 9 -
og deretter koble dem opp slik at det ser ut akkurat som vår trestruktur
at vi snakket om tidligere.
La oss gjøre det ganske raskt her.
Du vil se veldig raskt at jeg kommer til å begynne å skrive en haug med duplikat kode.
Jeg kommer til å opprette en node * og jeg kommer til å kalle det tre.
Jeg kommer til å sette den lik malloc (sizeof (node)).
Jeg kommer til å sette tre-> verdi = 3.
Tre -> left_child = NULL; tre -> høyre _child = NULL; også.
Det ser ganske lik initialisering roten, og det er akkurat hva
Jeg kommer til å gjøre hvis jeg begynner å initialisere 6 og 9 også.
Jeg skal gjøre det veldig raskt her - faktisk, jeg kommer til å gjøre en liten kopiere og lime,
og sørge for at jeg - alright.
Nå har jeg fått den kopiert og jeg kan gå videre og sette dette lik 6.
Du kan se at dette tar litt tid og er ikke super-effektiv.
På bare litt, vil vi skrive en funksjon som vil gjøre dette for oss.
Jeg ønsker å bytte ut dette med en 9, erstatte den med en 6.
>> Nå har vi alle våre noder opprettet og initialisert.
Vi har fått vår root settes lik 7, eller som inneholder verdien 7,
vår node inneholdende 3, vår node inneholdende 6, og vår node inneholdende 9.
På dette punktet, er alt vi trenger å gjøre ledning alt opp.
Grunnen til at jeg initialisert alle pekere til null er bare slik at jeg sørge for at
Jeg har ikke noen uinitialiserte pekere i det ved et uhell.
Og også siden, på dette punktet, jeg bare nødt til å faktisk koble nodene til hverandre -
til de som de faktisk er koblet til - jeg trenger ikke å gå gjennom og gjøre
at alle nuller er der på de riktige stedene.
>> Starter ved roten, jeg vet at roten venstre barnet er 3.
Jeg vet at roten rett barnet er 9.
Etter det den eneste andre barn som jeg har igjen å bekymre seg
er 3 rett barn, som er 6.
På dette punktet, ser det hele ganske bra.
Vi vil slette noen av disse linjene.
Nå ser alt ganske bra.
La oss gå tilbake til vår spesifikasjonen og se hva vi har å gjøre videre.
>> På dette punktet, må vi skrive en funksjon som heter 'inneholder'
med en prototype av "bool inneholder (int verdi) '.
Og denne inneholder funksjonen skal returnere true
hvis treet peker til vår globale root variabel
inneholder verdi sendt inn i funksjonen og falske ellers.
La oss gå videre og gjøre det.
Dette kommer til å bli akkurat som oppslaget som vi gjorde for hånd på iPad bare litt siden.
La oss zoome tilbake i litt og blar opp.
Vi kommer til å sette denne funksjonen rett over vår viktigste funksjon
slik at vi ikke trenger å gjøre noen form for prototyping.
Så inneholder bool (int verdi).
Det vi går. Det er vår standardtekst erklæringen.
Bare for å være sikker på at dette vil kompilere,
Jeg kommer til å gå videre og bare sette den lik return false.
Akkurat nå denne funksjonen bare ikke vil gjøre noe og alltid rapportere at
verdien som vi leter etter er ikke i treet.
>> På dette punktet, er det sannsynligvis en god idé -
siden vi har skrevet en hel haug med kode, og vi har ikke engang forsøkt å teste det ennå -
å sørge for at det hele kompilerer.
Det er et par ting som vi må gjøre for å sørge for at dette faktisk vil kompilere.
Først se om vi har brukt noen funksjoner i noen av bibliotekene som vi ennå ikke har tatt med.
Funksjonene vi har brukt så langt er malloc,
og vi har også brukt denne type - denne standardisert type som kalles 'bool' -
som er inkludert i standard bool header-fil.
Vi definitivt ønsker å inkludere standard bool.h for bool type,
og vi ønsker også å # include standard lib.h for standard bibliotekene
som inkluderer malloc, og gratis, og alt det der.
Så, zoome ut, kommer vi til å slutte.
La oss prøve og sørge for at dette faktisk gjorde kompilere.
Vi ser at det gjør det, så er vi på rett spor.
>> La oss åpne opp binary_tree.c igjen.
Det kompilerer. La oss gå ned og sørge for at vi setter noen samtaler til vår Inneholder funksjon -
bare for å være sikker på at det er alt vel og bra.
For eksempel når vi gjorde noen oppslag i treet vårt tidligere,
vi prøvde å slå opp verdiene 6, 10 og 1, og vi visste at 6 var i treet,
10 var ikke i treet, og en var ikke i treet heller.
La oss bruke disse eksempler samtaler som en måte å finne ut hvorvidt
vår inneholder funksjonen fungerer.
For å gjøre det, jeg kommer til å bruke printf funksjonen,
og vi kommer til å skrive ut resultatet av kallet til inneholder.
Jeg kommer til å sette i en streng "inneholder (% d) = fordi
vi kommer til å plugge inn den verdien som vi kommer til å se etter,
og =% s \ n "og bruke den som vår formatstrengen.
Vi bare kommer til å se - bokstavelig talt skrive ut på skjermen -
det ser ut som en funksjon.
Dette er egentlig ikke funksjonen samtalen.
Dette er bare en streng designet for å ligne en funksjon.
>> Nå kommer vi til å plugge inn verdiene.
Vi kommer til å prøve inneholder den 6.,
og hva vi skal gjøre her er å bruke den trefoldig operatør.
La oss se - inneholder 6 - så nå har jeg inneholdt 6 og hvis inneholder 6 er sant,
strengen som vi kommer til å sende til% s format karakter
kommer til å være strengen "true".
La oss bla over en liten bit.
Ellers ønsker vi å sende strengen "false" hvis inneholder 6 avkastning falske.
Dette er en litt klønete utseende, men jeg fant ut at jeg kan like godt illustrere
hva trefoldig operatøren ser ut siden vi ikke har sett det en stund.
Dette vil være en fin, praktisk måte å finne ut om vår inneholder funksjonen fungerer.
Jeg kommer til å rulle tilbake over til venstre,
og jeg kommer til å kopiere og lime inn denne linjen et par ganger.
Det endret noen av disse verdiene rundt,
så dette kommer til å være 1, og dette kommer til å være 10 år.
>> På dette punktet har vi fått en fin Inneholder funksjon.
Vi har noen tester, og vi vil se om dette fungerer.
På dette punktet har vi skrevet litt mer kode.
Tid for å slutte ut og sørge for at alt fortsatt samler.
Avslutt ut, og la oss nå prøve å lage binære treet igjen.
Vel, det ser ut som vi har fått en feil,
og vi har fått dette eksplisitt erklære bibliotek funksjon printf.
Det ser ut som vi trenger å gå inn og # include standardio.h.
Og med det, bør alt kompilere. Vi er alle gode.
La oss nå prøve å kjøre binære treet og se hva som skjer.
Her er vi,. / Binary_tree,
og vi ser det, som vi forventet -
fordi vi ikke har implementert inneholder ennå,
eller rettere sagt, har vi bare satt i return false -
Vi ser at det er nettopp tilbake usant for alle av dem,
slik at det er alle som arbeider for det meste ganske godt.
>> La oss gå tilbake og faktisk gjennomføre inneholder på dette punktet.
Jeg kommer til å rulle ned, zoome inn, og -
huske, var algoritme som vi brukte som vi startet på rotnoden
og deretter på hver node vi møter, vi gjør en sammenligning,
og basert på at sammenligning enten vi flytte til venstre barnet eller høyre barnet.
Dette kommer til å se veldig lik den binære søk koden som vi skrev tidligere i begrepet.
Når vi starter, vet vi at vi ønsker å holde på gjeldende node
at vi ser på, og gjeldende node kommer til å bli stilt i henhold til rotnoden.
Og nå, vi kommer til å holde det gående gjennom treet,
og husk at vår stoppe tilstand -
når vi faktisk jobbet gjennom eksempel hånd -
var da vi oppdaget en null node,
ikke når vi så på en null barn,
men heller når vi faktisk flyttet til en node i treet
og funnet ut at vi er på en null node.
Vi kommer til å veksle til nå er ikke lik null.
Og hva skal vi gjøre?
Vi kommer til å teste om (nå -> verdi == verdi),
da vet vi at vi faktisk har funnet noden som vi leter etter.
Så her kan vi returnere true.
Ellers, ønsker vi å se hvorvidt verdien er mindre enn verdien.
Hvis gjeldende node verdi er mindre enn verdien vi leter etter,
vi kommer til å flytte til høyre.
Så nå = nå -> right_child, og ellers kommer vi til å flytte til venstre.
nå = nå -> left_child;. Ganske enkelt.
>> Du kjenner kanskje løkken som ser svært lik denne fra
binære søk tidligere i begrepet, bortsett da var vi å gjøre med lav, middels og høy.
Her, vi må se på en gjeldende verdi,
så det er hyggelig og enkel.
La oss sørge for at denne koden fungerer.
Først, sørg for at det kompilerer. Ser ut som den gjør.
La oss prøve å kjøre den.
Og ja, skrives det ut alt som vi forventet.
Det finner 6 i treet, ikke finner 10 fordi 10 ikke er i treet,
og finner ikke en enten fordi en er heller ikke i treet.
Kule ting.
>> Alright. La oss gå tilbake til vår spesifikasjonen og se hva som skjer videre.
Nå ønsker det å legge til noen flere noder til treet vårt.
Den ønsker å legge til 5, 2 og 8, og sørge for at våre inneholder kode
fortsatt fungerer som forventet.
La oss gå gjøre det.
På dette punktet, snarere enn å gjøre det irriterende kopiere og lime igjen,
la oss skrive en funksjon for å faktisk lage en node.
Hvis vi bla nedover hele veien til main, ser vi at vi har gjort dette
svært lik kode om igjen og om igjen hver gang vi ønsker å skape en node.
>> La oss skrive en funksjon som faktisk vil bygge en node for oss og returnere det.
Jeg kommer til å kalle det build_node.
Jeg kommer til å bygge en node med en bestemt verdi.
Zoome inn her.
Det første jeg skal gjøre er å lage faktisk plass til noden på haugen.
Så node * n = malloc (sizeof (node)); n -> verdi = verdi;
og her, jeg bare kommer til å initialisere alle feltene for å være passende verdier.
Og helt til slutt, vil vi gå tilbake til vår node.
Alright. En ting å merke seg er at denne funksjonen her
kommer til å returnere en peker til minne som har vært heap-bevilget.
Hva er fint om dette er at denne noden nå -
vi må erklære den på haugen fordi hvis vi erklærte den på stakken
vi ville ikke være i stand til å gjøre det i denne funksjonen som dette.
At minnet vil gå ut av omfanget
og ville være ugyldig hvis vi prøvde å få tilgang til det senere.
Siden vi er erklære heap-minnet som er tildelt,
Vi er nødt til å ta vare på frigjør det senere
for vårt program for å ikke lekke noe minne.
Vi har vært punting på at for alt annet i koden
bare for enkelhets skyld på tiden,
men hvis du noen gang skrive en funksjon som ser slik ut
hvor du har - noen kaller det en malloc eller RealLOC inne -
du vil være sikker på at du setter en slags kommentar her oppe som sier,
hei, du vet, returnerer en heap-bevilget node initialisert med bestått i verdi.
Og så du vil være sikker på at du setter inn en slags notat som sier
den som ringer må frigjøre den returnerte minne.
På den måten, hvis noen gang går og bruker denne funksjonen,
de vet at det de får tilbake fra den funksjonen
på et tidspunkt vil trenge å bli frigjort.
>> Forutsatt at alt er vel og bra her,
vi kan gå ned i koden vår og erstatte alle disse linjene her
med samtaler til vår build node funksjon.
La oss gjøre det veldig raskt.
Den ene delen som vi ikke kommer til å erstatte er denne delen her nede
på bunnen hvor vi faktisk wire opp nodene til å peke til hverandre,
fordi at vi ikke kan gjøre i vår funksjon.
Men, la oss gjøre root = build_node (7), node * tre = build_node (3);
node * seks = build_node (6), node * ni = build_node (9);.
Og nå har vi også ønsket å legge til noder for -
node * fem = build_node (5), node * åtte = build_node (8);
og hva var den andre noden? La oss se her. Vi ønsket å også legge til en 2 -
node * to = build_node (2);.
Alright. På dette punktet, vet vi at vi har fått 7, 3, den 9, og 6
alle kablet opp riktig, men hva med 5, den 8, og 2?
Å holde alt i riktig rekkefølge,
vi vet at tre rett barnet er 6.
Så hvis vi skal legge til 5,
de 5 tilhører også i høyre side av treet hvor 3 er roten,
så 5 tilhører som venstre barn av 6.
Vi kan gjøre dette ved å si, seks -> left_child = fem;
og deretter 8 tilhører som venstre barn av 9, så ni -> left_child = åtte;
og deretter 2 er venstre barn på 3, slik at vi kan gjøre det her oppe - dig -> left_child = to;.
Hvis du ikke helt følger med på det, foreslår jeg at du trekker det ut selv.
>> Alright. La oss ta vare på denne. La oss gå ut og sørge for at det kompilerer,
og så kan vi legge inn våre inneholder samtaler.
Ser ut som alt fortsatt samler.
La oss gå inn og legge inn noen inneholder samtaler.
Igjen, jeg kommer til å gjøre en liten bit av kopiere og lime.
La oss nå søke etter 5, 8 og 2. Alright.
La oss sørge for at alt dette ser bra fortsatt. Flott! Lagre og avslutte.
Nå la oss gjøre, kompilere, og nå la oss kjøre.
Fra resultatene, ser det ut som alt fungerer like fint og godt.
Flott! Så nå har vi fått vår inneholder funksjon skrevet.
La oss gå videre og begynne å jobbe på hvordan du setter noder i treet
siden, som vi gjør det akkurat nå, ting er ikke veldig pen.
>> Hvis vi går tilbake til spesifikasjonen,
den ber oss om å skrive en funksjon som kalles inn - igjen, tilbake en bool
for hvorvidt vi kan faktisk sette noden i treet -
og deretter for å sette inn i treet er spesifisert som
det eneste argumentet til vår innsats funksjon.
Vi kommer tilbake sant hvis vi kunne faktisk sette noden som inneholder verdien i treet,
noe som betyr at vi, en, hadde nok minne,
og så to, gjorde at noden ikke allerede eksisterer i treet siden -
Husk, vi er ikke nødt til like verdier i treet, bare for å gjøre ting enkelt.
Alright. Tilbake til koden.
Åpne den opp. Zoome inn litt, så bla nedover.
La oss sette innsatsen funksjonen rett over inneholder.
Igjen, det kommer til å bli kalt bool innsats (int verdi).
Gi den litt mer plass, og deretter som en standard,
la oss sette i retur falsk helt på slutten.
Nå nede på bunnen, la oss gå videre og i stedet for manuelt å bygge noder
i hoved oss ​​selv og ledninger dem opp til å peke på hverandre som vi gjør,
vi vil stole på vår innsats funksjonen for å gjøre det.
Vi vil ikke stole på vår innsats funksjonen for å bygge hele treet fra scratch ennå,
men heller vi skal bli kvitt disse linjene - vi vil kommentere ut disse linjene -
som bygger nodene 5, 8 og 2.
Og i stedet, vil vi sette inn anrop til vår innsats funksjon
å sørge for at det faktisk fungerer.
Here we go.
>> Nå har vi kommentert ut disse linjene.
Vi har bare 7, 3, 9 og 6 i vår treet på dette punktet.
Å sørge for at dette er alt fungerer,
Vi kan zoome ut, gjør vår binære treet,
kjøre den, og vi kan se som inneholder nå forteller oss at vi er helt rett -
5, 8, og 2 er ikke lenger i treet.
Gå tilbake til koden,
og hvordan skal vi sette inn?
Husk hva vi gjorde da vi var faktisk sette 5, 8 og 2 tidligere.
Vi spilte som Plinko spill hvor vi startet ved roten,
gikk ned treet én etter én av en
før vi fant den riktige avstanden,
og da vi kablet i noden på riktig sted.
Vi kommer til å gjøre det samme.
Dette er i utgangspunktet som å skrive koden som vi brukte i inneholder funksjonen
å finne stedet hvor noden skal være,
og da er vi bare kommer til å sette noden der.
La oss begynne å gjøre det.
>> Så vi har en node * nå = root, vi bare kommer til å følge inneholder kode
før vi finner ut at det ikke fungerer helt for oss.
Vi kommer til å gå gjennom treet mens dagens elementet er ikke null,
og hvis vi finner ut at nå er verdien er lik den verdien som vi prøver å sette -
Vel, dette er en av sakene der vi ikke kunne faktisk sette noden
inn i treet fordi dette betyr at vi har en lik verdi.
Her er vi faktisk kommer til å returnere falsk.
Nå else if nå verdi er mindre enn verdien,
nå vet vi at vi flytter til høyre
fordi verdien tilhører i høyre halvdel av nå treet.
Ellers, vi kommer til å flytte til venstre.
Det er i utgangspunktet vår inneholder fungere der.
>> På dette punktet, når vi har fullført dette mens loop,
vår nå pekeren kommer til å peke mot null
Dersom funksjonen ikke allerede returnert.
Vi er derfor å ha nå på det punktet der vi ønsker å sette inn den nye noden.
Hva gjenstår er å faktisk bygge den nye noden,
som vi kan gjøre ganske enkelt.
Vi kan bruke vår super-hendig bygge node funksjon,
og noe som vi ikke gjorde tidligere -
vi bare slags tok for gitt, men nå skal vi gjøre bare for å være sikker -
Vi skal teste å sørge for at verdien returnert av ny node var faktisk
ikke null, fordi vi ikke ønsker å starte med tilgangen til minne om den er null.
Vi kan teste for å være sikker på at ny node er ikke lik null.
Eller i stedet, kan vi bare se om det faktisk er null,
og hvis det er null, så kan vi bare return false tidlig.
>> På dette punktet, må vi koble ny node i sin passende sted i treet.
Hvis vi ser tilbake på main og hvor vi var faktisk ledninger i verdier før,
Vi ser at måten vi gjorde det da vi ønsket å sette 3 i treet
ble vi vist til venstre barn av rot.
Når vi setter 9 i treet, hadde vi tilgang til riktig barn av roten.
Vi måtte ha en peker til den overordnede for å sette en ny verdi inn i treet.
Rulle opp å sette inn, er at ikke kommer til å helt fungerer her
fordi vi ikke har en forelder peker.
Hva vi ønsker å være i stand til å gjøre er, på dette punktet,
sjekk den overordnede verdi og se - vel, gosh,
hvis foreldrene verdi er mindre enn dagens verdi,
så forelderen rett barnet bør være ny node;
ellers bør den overordnede venstre barn bli den nye noden.
Men, vi har ikke denne forelderen pekeren helt ennå.
>> For å få det, er vi faktisk nødt til å spore det som vi går gjennom treet
og finne riktig sted i loop over.
Vi kan gjøre det ved å rulle tilbake til toppen av vår innsats funksjon
og sporing annen pekeren variabel kalt den overordnede.
Vi kommer til å sette den lik null i utgangspunktet,
og deretter hver gang vi går gjennom treet,
vi kommer til å sette den overordnede pekeren for å matche dagens pekeren.
Still foreldre lik nå.
Denne måten, hver gang vi går gjennom,
vi kommer til å sikre at så dagens pekeren blir økes
den overordnede pekeren følger det - bare ett nivå høyere enn dagens pekeren i treet.
At alle ser ganske bra.
>> Jeg tror det én ting som vi ønsker å justere dette bygge node retur null.
For å få bygge node å faktisk lykkes returnere null,
vi må endre den koden,
fordi her har vi aldri testet for å sørge for at malloc returnerte gyldig peker.
Så, hvis (n = NULL!), Deretter -
hvis malloc returnerte gyldig peker, så får vi initialisere det;
ellers vil vi bare gå tilbake og som vil ende opp med å returnere null for oss.
Nå er alt ser ganske bra. La oss sørge for at dette faktisk samler.
Gjør binære treet, og oh, vi har noen ting som skjer her.
>> Vi har en implisitt erklæring av funksjon bygge node.
Igjen, med disse kompilatorer, vi kommer til å starte på toppen.
Hva som må bety at jeg ringer bygge node før jeg faktisk har erklært det.
La oss gå tilbake til koden veldig raskt.
Bla nedover, og sikker nok, min innsats funksjon erklært
ovenfor bygge node funksjon,
men jeg prøver å bruke bygge node innsiden av innsatsen.
Jeg kommer til å gå inn og kopiere - og deretter lime bygge node funksjon vei opp her på toppen.
På den måten, forhåpentligvis som vil fungere. La oss gi denne en gå.
Nå er det kompilerer alt. Alt er bra.
>> Men på dette punktet har vi faktisk ikke kalt vår innsats funksjon.
Vi bare vet at det kompilerer, så la oss gå inn og sette noen samtaler i.
La oss gjøre det i vår viktigste funksjon.
Her kommentert vi ut 5, 8, og 2,
og da vi ikke wire dem opp her nede.
La oss ta noen telefoner for å sette inn,
og la oss også bruke samme type ting som vi brukte
når vi har gjort disse printf samtaler for å sikre at alt gjorde få satt inn riktig.
Jeg kommer til å kopiere og lime inn,
og i stedet for inneholder vi skal gjøre innsatsen.
Og i stedet for seks, 10 og 1, vi kommer til å bruke 5, 8 og 2.
Dette bør forhåpentligvis sette 5, 8, og 2 inn i treet.
Kompilere. Alt er bra. Nå skal vi faktisk kjøre programmet vårt.
>> Alt returnert falsk.
Så gjorde 5, 8 og 2 ikke gå, og det ser ut som inneholder ikke fant dem heller.
Hva skjer? La oss zoome ut.
Det første problemet er at innsatsen syntes å return false,
og det ser ut som det er fordi vi igjen i våre return false samtale,
og vi vil aldri returnert sant.
Vi kan sette opp dette.
Det andre problemet er nå selv om vi gjør - lagre denne, avslutter dette,
kjøre gjøre igjen, kompilere den har, og deretter kjøre den -
vi ser at noe annet skjedde her.
En 5, 8, og 2 ble fortsatt aldri funnet i treet.
Så, hva skjer?
>> La oss ta en titt på denne i koden.
La oss se om vi kan finne ut av dette.
Vi starter med den overordnede ikke er null.
Vi setter dagens pekeren lik roten pekeren,
og vi kommer til å jobbe oss ned gjennom treet.
Hvis gjeldende node ikke er null, da vet vi at vi kan flytte ned litt.
Vi setter vår overordnede pekeren til å være lik dagens pekeren,
sjekket verdi - hvis verdiene er de samme vi returnerte falsk.
Hvis verdiene er mindre vi flyttet til høyre;
ellers, flyttet vi til venstre.
Så bygger vi en node. Jeg skal zoome inn litt.
Og her kommer vi til å prøve å koble opp verdiene til å være den samme.
Hva skjer? La oss se om muligens Valgrind kan gi oss et hint.
>> Jeg liker å bruke Valgrind bare fordi Valgrind veldig raskt kjører
og forteller deg om det er noen minnefeil.
Når vi kjører Valgrind på koden,
som du kan se rett here--Valgrind./binary_tree--and trykk enter.
Du ser at vi ikke har noe minne feil, så det ser ut som alt er i orden så langt.
Vi har noen minnelekkasjer, som vi vet, fordi vi ikke er
skjer for å frigjøre noen av våre noder.
La oss prøve å kjøre GDB å se hva som faktisk skjer.
Vi vil gjøre gdb. / Binary_tree. Det startet opp helt fint.
La oss sette en pause punkt på innsatsen.
La oss kjøre.
Det ser ut som vi aldri egentlig heter innsatsen.
Det ser ut som problemet var bare at når jeg endret her nede i hoved -
alle disse printf samtaler fra inneholder -
Jeg har aldri egentlig endret disse til å ringe innsatsen.
Nå la oss gi det et forsøk. La oss kompilere.
Alle ser bra der. La oss nå prøve å kjøre den, se hva som skjer.
Alright! Alt ser ganske bra der.
>> Den siste ting å tenke på er, er det noen edge tilfeller til dette innlegget?
Og det viser seg at, vel, den ene kanten sak som er alltid interessant å tenke på
er, hva skjer hvis treet er tom og du kaller dette innlegget funksjon?
Vil det fungere? Vel, la oss gi det et forsøk.
- Binary_tree c. -
Måten vi kommer til å teste dette er, vi kommer til å gå ned til vår viktigste funksjon,
og i stedet ledninger disse nodene opp som dette,
vi bare kommer til å kommentere ut hele greia,
og i stedet for ledninger opp nodene oss selv,
Vi kan faktisk bare gå foran og slette alt dette.
Vi kommer til å gjøre alt en samtale sette inn.
Så, la oss gjøre - i stedet for 5, 8 og 2, vi kommer til å sette 7, 3, og 9.
Og så får vi også ønsker å sette inn 6 også.
Lagre. Avslutt. Gjør binære treet.
Det kompilerer alt.
Vi kan bare kjøre det som er, og se hva som skjer,
men det er også kommer til å være veldig viktig å sørge for at
Vi har ikke noen minnefeil,
siden dette er en av våre edge saker som vi vet om.
>> La oss sørge for at det fungerer godt under Valgrind,
som vi vil gjøre ved bare å kjøre Valgrind. / binary_tree.
Det ser ut som vi faktisk har en feil fra en sammenheng -
vi har denne segmentering feil.
Hva skjedde?
Valgrind forteller oss faktisk hvor det er.
Zoome ut litt.
Det ser ut som det skjer i vår innsats funksjon,
hvor vi har en ugyldig lese av størrelse 4 på innsatsen, linje 60.
La oss gå tilbake og se hva som skjer her.
Zoome ut virkelig rask.
Jeg vil være sikker på at det ikke går til kanten av skjermen, slik at vi kan se alt.
Trekke det i litt. Alright.
Bla nedover, og problemet er her.
Hva skjer hvis vi kommer ned og vår nåværende node er allerede null,
vår foreldrenoden er null, så hvis vi ser opp på toppen, akkurat her -
hvis dette mens loop aldri utfører faktisk
fordi vår nåværende verdien er null - vår rot er null så nå er null -
da våre foreldre aldri blir satt til nå eller til en gyldig verdi,
så vil foreldrene også være null.
Vi må huske å se etter at
etter den tid får vi her nede, og vi begynner å få tilgang til foreldrenes verdi.
Så, hva skjer? Vel, hvis foreldrene er null -
if (forelder == NULL) - da vet vi at
det må ikke være noe i treet.
Vi må prøve å sette det ved roten.
Vi kan gjøre det ved å bare sette root lik den nye noden.
Så på dette punktet, vet vi ikke egentlig ønsker å gå gjennom disse andre tingene.
I stedet akkurat her, kan vi gjøre enten en else-if-else,
eller vi kunne kombinere alt her oppe i en annet,
men her skal vi bare bruke andre og gjøre det på den måten.
Nå skal vi teste for å være sikker på at våre foreldre ikke er null
før da faktisk prøver å få tilgang til sine områder.
Dette vil hjelpe oss å unngå segmenteringen feil.
Så vi avslutter, zoome ut, kompilere, kjøre.
>> Ingen feil, men vi har fortsatt en haug med minnelekkasjer
fordi vi ikke fri noen av våre noder.
Men hvis vi går opp her, og vi ser på utskriften vår,
Vi ser at, vel, ser ut som alle våre innsatser var tilbake sant, noe som er bra.
Innsatsene er sanne,
og deretter de riktige inneholder samtaler er også sant.
>> Godt jobbet! Det ser ut som vi har lykkes skrevet innsatsen.
Det er alt vi har for denne ukens Problem Set-spesifikasjonen.
En morsom utfordring å tenke på er hvordan du faktisk ville gå i
og fri alle nodene i dette treet.
Vi kan gjøre så mange forskjellige måter,
men jeg skal la det opp til deg å eksperimentere,
og som en morsom utfordring, prøve og sørg for at du kan være sikker på
at dette Valgrind rapporten ga ingen feil og ingen lekkasjer.
>> Lykke til på denne ukens Huffman koding problem sett,
og vi vil se deg neste uke!
[CS50.TV]