[Powered by Google Translate] [7 §] [vähemmän mukavaksi] [Nate Hardison] [Harvardin yliopisto] [Tämä on CS50.] [CS50.TV] 

Tervetuloa 7 §. Kiitos hurrikaani Sandy, sen sijaan, jolla on normaali osa tällä viikolla, teemme tämän selattava läpi osa kysymyksistä. Aion Seuraamme yhdessä Harjoitus 6 Specification, ja menee läpi kaikki kysymykset § Kysymysten osan. Jos on kysyttävää, lähetä nämä on CS50 keskustella. 

Selvä. Aloitetaan. Juuri nyt olen etsimässä sivulla 3 Harjoitus Specification. Menemme ensin alkaa puhua binääripuita koska ne on paljon merkitystä tällä viikolla ongelma set - Huffman Tree koodausta. Yksi ensimmäisistä tietorakenteiden puhuimme siitä CS50 oli jono. Muista, että matriisi on sekvenssi elementtejä - kaikki samaa tyyppiä - tallennetaan aivan toistensa muistiin. Jos minulla on kokonaisluku array, että voin tehdä tällä laatikot-numerot-kokonaislukuja style - Sanotaan Minulla on 5 ensimmäiseen ruutuun, minulla 7 toiseen, Sitten minulla on 8, 10, ja 20 lopullisessa ruutuun. Muista, kaksi todella hyvää tästä array on, että meillä on tämä jatkuva-aikaisen pääsyn jokin erityinen tekijä  pakassa, jos tiedämme sen indeksi. Esimerkiksi, jos haluan napata kolmannen elementin array - klo indeksi 2 käyttämällä nolla-pohjainen indeksointijärjestelmä - Olen kirjaimellisesti vain täytyy tehdä yksinkertaisen laskutoimituksen, hop tuossa asemassa array, vedä 8, joka on tallennettu siellä, ja olen hyvä mennä. 

Yksi pahaa tästä array - että puhuimme kun keskustelimme linkitettyjä listoja - että jos haluan lisätä elementin tähän array, Aion täytyy tehdä joitakin siirtymässä ympärille. Esimerkiksi tämä joukko täällä on lajiteltu järjestyksessä - lajiteltu nousevaan järjestykseen - 5, sitten 7, sitten 8, sitten 10, sitten 20 - mutta jos haluan lisätä numero 9 tähän array, Aion pitää siirtää joitakin elementtejä, jotta tilaa. Voimme tehdä tämän täällä. Aion pitää siirtää 5, 7, ja sitten 8; luoda kuilu, jossa voin laittaa 9, ja sitten 10 ja 20 voi mennä oikealle 9. Tämä on eräänlainen kipu koska pahimmassa tapauksessa - kun meillä ollut lisätä joko alussa tai lopussa ja array, riippuen siitä, miten me Tuulen - saatamme päätyä siirtää kaikki elementit että olemme nyt tallentaminen array. 

Joten, mikä oli tapa kiertää tämä? Tapa kiertää tämä oli mennä meidän linkitetyn-lista menetelmää, jossa - sen sijaan, että tallennetaan elementtien 5, 7, 8, 10, ja 20 kaikki vierekkäin muistiin - Mitä me sen sijaan ei ollut tallentaa ne tavallaan missä halusimme tallentaa ne Näiden linkitetyn listan solmuista, jotka olen piirustus täällä, tavallaan ad hoc. Ja sitten me liittää ne yhteen näitä ensi osoittimia. Voin olla osoitin 5.-7, osoitinta 7 ja 8, osoitinta 8 10, ja lopuksi, osoitinta 10 ja 20, ja sitten nollaosoittimen klo 20 osoittaa, että ei ole mitään jäljellä. Kauppa-off, että meillä on täällä että nyt, jos haluamme lisätä numero 9 meidän järjestetty luettelo, kaikki mitä on tehtävä on luoda uusi solmu 9, lanka sen osoittamaan sopivaan paikkaan, ja sitten uudelleen johdin 8 osoittamaan alas 9. Se on aika nopea, olettaen tiedämme tarkalleen missä haluamme lisätä 9. Mutta kauppa-off vaihdossa on se, että olemme nyt menettäneet vakio-aika pääsy mihinkään tiettyyn osa meidän tietorakenne. Esimerkiksi, jos haluan löytää neljäs osa tätä linkitetty lista, Aion on aloitettava alusta luettelon ja työskennellä minun läpi laskemalla solmun-by-solmu kunnes löydän neljäs. 

Saadakseen paremman pääsyn suorituskykyä kuin linkitetty lista - mutta myös säilyttää joitakin etuja, että meillä oli suhteen lisäys-aika linkitetty lista - binääripuu on menossa tarvitse käyttää hieman enemmän muistia. Erityisesti sen sijaan, että vain ottaa yksi osoitin on binääripuun solmu - kuten linkitetyn listan solmu ei - aiomme lisätä toinen osoitin binääripuu solmu. Pikemminkin kuin vain ottaa yksi osoitin seuraavaan elementtiin, aiomme olla osoittimen vasen lapsi ja oikea lapsi. 

Katsotaanpa piirtää kuvaa nähdäksesi, mitä se todella näyttää. Jälleen aion käyttää näitä laatikoita ja nuolia. Binääripuu solmu aluksi vain yksinkertainen laatikko. Se tulee olemaan tilaa arvoa, ja sitten se myös tulee olemaan tilaa vasen lapsi ja oikea lapsi. Aion merkitä ne tänne. Aiomme olla vasen lapsi, ja sitten me aiomme olla oikea lapsi. On olemassa monia erilaisia ​​tapoja tehdä tätä. Joskus tilaa ja mukavuutta, Minä itse piirtää niin kuin olen täällä alhaalla minne olen menossa arvoa yläreunassa, ja sitten oikealle lapsen alaoikealla, ja vasen lapsi alhaalla vasemmalla. Palataan tähän alkuun kaavio, meillä arvoa huipulla, Sitten meillä on vasemman lapsen osoitin, ja sitten meillä on oikeus lapsen osoitin. 

Vuonna Harjoitus Specification, puhumme piirtämällä solmu, jonka arvo on 7, ja sitten vasen lapsi osoitin, joka on nolla, ja oikea lapsi-osoitin, joka on nolla. Voimme joko kirjoittaa pääomaa NULL tilaa Sekä vasen lapsi ja oikea lapsi, tai voimme tehdä tämän lävistäjä slash läpi jokaisen laatikot osoittavat että se on null. Aion tehdä sitä vain koska se on yksinkertaisempi. Mitä näet tässä on kaksi tapaa kaavio hyvin yksinkertainen binääripuu solmu jossa meillä on arvo 7 ja null lapsi viitteitä. 

Toinen osa eritelmän puhutaan kuinka linkitettyjä luetteloita - Muista, meillä oli vain pitää kiinni aivan ensimmäinen elementti luettelossa muistaa koko lista - ja samoin, jossa on binääripuu, meillä on vain pitää kiinni yksi osoitin puun säilyttämiseksi valvonnan koko tietorakenne. Tämä erityinen osa puun kutsutaan juurisolmu puun. Esimerkiksi, jos tämä solmu - tämä solmu sisältää arvon 7 null-vasen-ja oikea-lapsi osoittimia - olivat ainoa arvo meidän puu, niin tämä olisi meidän juurisolmun. Se on alusta meidän puu. Voimme nähdä tämän hieman selkeämmin kun alamme lisäämällä solmut meidän puuhun. Saanen vetää uuden sivun. 

Nyt aiomme tehdä puu, joka on 7 juuresta, ja 3 sisällä vasen lapsi, ja 9 sisällä oikea lapsi. Tämäkin on melko yksinkertainen. Meillä 7, piirtää solmu 3, solmu 9, ja aion asettaa vasemman lapsen osoitin 7 osoittamaan solmuun sisältävät 3, ja oikea lapsi-osoitin solmun sisältää 7 solmu, joka sisältää 9. Nyt, koska 3 ja 9 ei ole lapsia, aiomme asettaa kaikki lapsensa osoittimia olla null. Tässä juuri meidän puu vastaa solmun sisältävä numero 7. Voit nähdä, että jos kaikki meillä on osoitin, joka juurisolmu Voimme sitten kävellä läpi puiden ja käyttää sekä lapsen solmut - sekä 3 ja 9. Ei tarvitse säilyttää viitteitä jokaiseen solmuun puussa. Selvä. Nyt aiomme lisätä toisen solmun tähän kaavio. Aiomme lisätä solmun sisältää 6, ja aiomme lisätä tätä oikeutta lapsi solmu sisältää 3. Voit tehdä sen, aion poistaa että null osoitin 3-solmu ja lanka sen osoittamaan solmuun sisältää 6. Selvä. 

Tässä vaiheessa mennään yli hieman terminologiaa. Voit aloittaa, syystä, että tätä kutsutaan binääripuu erityisesti on, että se on kaksi lasta osoittimia. On olemassa muitakin puita, jotka ovat enemmän lapsi osoittimia. Erityisesti teit 'yritä' in Harjoitus 5. Huomaat, että se yrittää, teillä oli 27 eri osoittimia eri lapsille - yksi kullekin 26 kirjainten Englanti aakkoset, ja sitten 27. ja heittomerkki - niin, että se vastaa puun tyyppi. Mutta täällä, koska se on binääri, meillä on vain kaksi lasta viitteitä. 

Tämän lisäksi juurisolmu että puhuimme, olemme myös heittää noin termiä "lapsi". Mitä se tarkoittaa yhden solmun olla lapselle toisen solmun? Se tarkoittaa kirjaimellisesti että lapsi solmu on lapsi toisen solmun ja jos tämä toinen solmulla on yksi sen lapsen osoittimia asetettu osoittamaan, että solmu. Tämän toteuttamiseksi enemmän Konkreettisesti jos 3, joka on suunnattu yhden lapsen osoittimien 7, sitten 3 on lapsi 7. Jos me selvittää, mitä lapset 7 ovat - hyvin, näemme, että 7 on osoittimen 3 ja osoittimen 9, joten 9 ja 3 ovat lapsia 7. Yhdeksän ole lapsia, koska sen lapsen osoittimet ovat null, ja 3 on vain yksi lapsi, 6. Kuusi ei myöskään ole lapsia, koska sen molemmat osoittimet ovat null, jossa me tehdä juuri nyt. 

Lisäksi me myös puhumme vanhemmille tietyn solmun, ja tämä on, kuten odottaa saattaa, käänteinen tämän lapsen kuvauksen. Jokaisella solmulla on vain yksi vanhempi - kahden sijasta kuten arvata saattaa ihmisten kanssa. Esimerkiksi vanhemman 3 on 7. Vanhempi 9 on 7, ja vanhempi 6 on 3. Ei paljon se. Meillä on myös ehdot puhua isovanhemmat ja lapsenlapset, ja yleisemmin puhumme esivanhemmat ja jälkeläiset tiettyyn solmuun. Esi solmun - tai esivanhemmat, pikemminkin on solmu - ovat kaikki solmut, jotka sijaitsevat polkua juuresta, että solmu. Jos esimerkiksi Etsin solmuun 6, sitten esi-isät tulevat olemaan sekä 3 ja 7. Esi 9, esimerkiksi, ovat - jos Etsin navassa 9 - Sitten kantaisä 9 on vain 7. Ja jälkeläiset ovat täsmälleen päinvastainen. Jos haluan tarkastella kaikkia jälkeläisiä 7, Sitten minun täytyy katsoa kaikki solmut sen alapuolella. Joten, minulla on 3, 9 ja 6 kaikki jälkeläisinä 7. 

Lopullisen termi puhumme tämä käsite on sisarus. Sisarukset - eräänlainen seuraavat pitkin näiden perheiden ehdoin - ovat solmuja, jotka ovat samalla tasolla puussa. Niin, 3 ja 9 ovat sisaruksia, koska ne ovat samalla tasolla puussa. Niillä molemmilla on sama emo, 7. 6 ei ole sisaruksia, koska 9 ei ole lapsia. Ja 7 ei ole sisaruksia, koska se on juuri meidän puu, ja siellä on aina vain 1 root. 7 on sisaruksia ei pitäisi olla solmun yläpuolella 7. Siellä pitäisi olla vanhempi 7, jolloin 7 olisi enää puun juuresta. Sitten että uusi emoyhtiö 7 olisi myös oltava lapsen, ja että lapsi olisi silloin sisarus 7. 

Selvä. Liikettä. Kun aloitimme keskustelun binääripuita, puhuimme siitä, miten aiomme käyttää niitä saavat etulyöntiaseman sekä taulukot ja linkitettyjen listojen. Ja miten aiomme tehdä se on tämän tilauksen omaisuutta. Sanomme, että binääripuu on tilattu, erittelyn mukainen, jos kunkin solmun meidän puu, kaikki sen jälkeläiset vasemmalla - vasen lapsi ja kaikki vasemman lapsen jälkeläiset - on vähemmän arvot, ja kaikki solmut oikealla - oikea lapsi ja kaikki oikean lapsen jälkeläiset - on solmuja suurempi kuin arvo nykyisen solmun että me tarkastelemme. Vain yksinkertaisuuden, aiomme olettaa, että ei ole mitään päällekkäisiä solmuja meidän puu. Esimerkiksi tämä puu emme aio käsitellä asian jossa meillä on arvo 7 juuresta  ja sitten meillä on myös arvo 7 muualla puussa. Tässä tapauksessa, huomaat, että tämä puu on todellakin tilattu. Meillä on arvo 7 juuresta. Kaiken vasemmalla 7 - jos minä perua kaikki nämä pikku merkkien täällä - kaiken vasemmalla 7 - 3 ja 6 - nämä arvot ovat molemmat alle 7, ja kaiken oikealle - mikä on juuri tämä 9 - on suurempi kuin 7. 

Tämä ei ole ainoa tilattu puu, joka sisältää näitä arvoja, mutta katsotaanpa piirtää muutamia niistä. On todella koko joukko tapoja, joilla voimme tehdä tämän. Aion käyttää pika vain pitää asiat yksinkertaisina, jossa - sijaan piirustus ulos koko laatikot-ja-nuolet - Aion tehdä numeroita ja lisätä nuolia yhdistämällä ne. Voit aloittaa, me vain kirjoittaa meidän alkuperäinen Tree jälleen missä meillä oli 7, ja sitten 3, ja sitten 3 huomautti takaisin oikealle 6, ja 7 oli oikea lapsi, joka oli 9. Selvä. Mikä on toinen tapa, että voisimme kirjoittaa tämä puu? Sen sijaan, että 3 on vasen lapsi 7, Voisimme myös 6 olla vasen lapsi 7, ja sitten 3 on vasemmalla puolella lapsi 6. Se näyttää tältä puu täällä missä minulla 7, Sitten 6, sitten 3 ja 9 oikealla puolella. Emme myöskään tarvitse olla 7 meidän juurisolmun. Voisimme myös 6 meidän juurisolmun. Mikä se näyttää? Jos aiomme säilyttää tämän tilattu omaisuutta, kaiken vasemmalla puolella 6 täytyy olla pienempi kuin se. On vain yksi mahdollisuus, ja se on 3. Mutta sitten kun oikea lapsi 6, meillä on kaksi vaihtoehtoa. Ensinnäkin, meillä voisi olla 7 ja sitten 9, tai voimme tehdä sen - kuten aion tehdä täällä - jossa meillä on 9 kuin oikea lapsi 6, ja sitten 7 kuten vasen lapsi 9. 

Nyt, 7 ja 6 eivät ole ainoat mahdolliset arvot root. Voisimme myös 3 syihin. Mitä tapahtuu, jos 3 on root? Täällä asiat saavat hieman mielenkiintoinen. Kolme ei ole mitään arvoja, jotka ovat vähemmän kuin se, siten, että koko vasen puoli puu on vain olemaan nolla. Ei ei tule olemaan mitään. Oikealle, voisimme luetella asioita nousevassa järjestyksessä. Meillä voisi olla 3, sitten 6, sitten 7, sitten 9. Tai voisimme tehdä 3, sitten 6, sitten 9 ja sitten 7. Tai voisimme tehdä 3, sitten 7, sitten 6, sitten 9. Tai, 3, 7 - oikeastaan ​​mitään, emme voi tehdä 7 enää. Se on meidän yksi asia siellä. Voimme tehdä 9, ja sitten 9 voimme tehdä 6 ja sitten 7. Tai voimme tehdä 3, sitten 9, sitten 7 ja sitten 6. 

Yksi asia kiinnittää huomiota tässä että nämä puut ovat hieman oudon näköisiä. Erityisesti jos katsomme 4 puut oikealla puolella - Minä ympyrä heitä täällä - nämä puut näyttävät melkein täsmälleen kuten linkitetty lista. Kukin solmu on vain yksi lapsi, ja joten meillä ei ole mitään tämän puumainen rakenne, että me katso esimerkiksi,  tässä yksi yksinäinen puu tänne alhaalla vasemmalla. Nämä puut ovat todella kutsutaan degeneroitunut binääripuita, ja me puhumme näistä enemmän tulevaisuudessa - varsinkin jos menet ottamaan muihin tietojenkäsittelytieteen kursseja. Nämä puut ovat rappeutua. He eivät ole kovin hyödyllisiä, koska, todellakin, tämä rakenne soveltuu  lookup kertaa samanlainen kuin linkitetty lista. Emme saa hyödyntää lisämuistia - tämä extra osoitin - koska meidän rakenne on huono tällä tavalla. Sen sijaan mene ja vedä binääripuita että on 9 juuresta, mikä on viimeinen asia, että meillä olisi, olemme sen sijaan, tässä vaiheessa aio puhua hieman tästä muiden aikavälillä että käytämme puhuttaessa puita, jota kutsutaan korkeus. 

Korkeus puu on etäisyys juuresta eniten kaukana solmu, tai pikemminkin hyppyjen määrä, että sinun täytyisi tehdä, jotta alkaa juuresta ja sitten päätyvät eniten kaukana solmu puussa. Jos tarkastelemme joitakin näistä puita että olemme piirretty täällä, Voimme nähdä, että jos otamme tämän puun vasemmassa yläkulmassa ja aloitamme klo 3, Sitten meidän on tehtävä 1 hypyn päästä 6, toinen hop päästä 7, ja kolmasosa hop päästä 9. Joten, korkeus tämä puu on 3. Voimme tehdä sama harjoitus muut puut hahmotellut tätä vihreä, ja näemme, että korkeus kaikki nämä puut on todellakin 3. Se osa, mikä tekee niistä rappeutua - että niiden korkeus on vain yksi vähemmän kuin solmujen lukumäärä koko puun. Jos tarkastelemme tässä muut puu, joka on ympäröity punaisella, toisaalta, näemme, että kaikkein-kaukaisessa lehtisolmuja ovat 6 ja 9 - lehdet ovat ne solmut, joilla ei ole lapsia. Joten, jotta saada siitä juurisolmu joko 6 tai 9, Meidän täytyy tehdä yhden hypyn päästä 7 ja sitten toisen hypyn päästä 9, ja samoin, vain toisen hypyn päässä 7 päästä 6. Niin, korkeus tämän puun yli tässä vain 2. Voit mennä takaisin ja tehdä kaikkien muiden puiden että aiemmin keskusteltu aloittaen 7 ja 6, ja huomaat, että korkeuden kaikkien näiden puiden on myös 2. 

Syy olemme puhuneet tilattu binääripuita ja miksi he siistiä, koska voit etsiä niitä hyvin samalla tavalla kuin hakemisen yli lajitellaan matriisina. Tästä me puhumme saada että parempi hakuaika yli yksinkertainen linkitetty lista. Kanssa linkitetty lista - jos haluat löytää tietyn elementin - olet paras aikoo tehdä jonkinlainen lineaarinen haku missä aloitat alussa luettelon ja hop yhden by-one - yksi solmu yksi solmu - läpi koko luetteloa kunnes löydät mitä etsit. Katsoo, että jos sinulla on binääripuu, joka on tallennettu tähän kivaan, voit itse saada enemmän binäärihakupuu käynnissä missä hajoita ja hallitse ja etsiä sopiva puoli puun kussakin vaiheessa. Katsotaan miten se toimii. 

Jos meillä on - jälleen menossa takaisin meidän alkuperäiseen puuhun - aloitamme klo 7, meillä on 3 vasemmalla puolella, 9 oikealla puolella, ja alle 3 meillä 6. Jos haluamme etsiä numero 6 tässä puussa, olimme alkaa juuresta. Haluamme verrata arvo etsimme, sanovat 6, arvoon tallennetaan solmun, joka tällä hetkellä vielä katselee, 7, toteavat, että 6 on todellakin alle 7, joten olimme liikkumaan vasemmalle. Jos arvo on 6 oli ollut suurempi kuin 7, olisimme sen sijaan siirretty oikealle. Koska tiedämme, että - rakenteen vuoksi meidän määräsi binaaripuun - kaikki arvot alle 7 aiotaan varastoida vasemmalla 7, ei tarvitse edes vaivaudu etsii läpi oikealle puolelle puun. Kun olemme siirtyä vasemmalle ja olemme nyt solmu, joka sisältää 3, voimme tehdä saman vertailun jälleen missä me vertailla 3 ja 6. Ja huomaamme, että vaikka 6 - arvo etsimme - on suurempi kuin 3, voimme mennä oikealle puolelle solmu, joka sisältää 3. Ei ole vasemmalla puolella täällä, joten olisimme voineet sivuuttaa sitä. Mutta tiedämme vain, että koska me tarkastelemme puu itse, ja voimme nähdä, että puu ei ole lapsia. 

Se on myös melko helppo etsiä 6 tässä puussa, jos teemme sen itsemme ihmisille, mutta seuraamme tätä prosessia mekaanisesti kuin tietokone tekisi todella ymmärtää algoritmin. Tässä vaiheessa me nyt katsot solmu, joka sisältää 6, ja etsimme arvon 6, niin, todellakin, olemme löytäneet sopivan solmun. Löysimme arvo 6 meidän puu, ja voimme lopettaa meidän etsiä. Tässä vaiheessa mukaan, mitä on tekeillä, Voimme sanoa, kyllä, olemme löytäneet arvon 6, se on olemassa meidän puu. Tai, jos me aiot lisätä solmun tai tehdä jotain, voimme tehdä sen tässä vaiheessa. 

Tehdään pari enemmän hakuja vain nähdä, miten tämä toimii. Katsotaan mitä tapahtuu, jos olisimme yrittää etsiä arvon 10. Jos me etsiä arvo 10, alkaisimme juureen. Olimme nähdä, että 10 on suurempi kuin 7, joten olimme liikkua oikealle. Olimme päästä 9 ja vertailla 9 10 ja nähdä, että 9 on todellakin alle 10. Joten jälleen, olimme yrittää siirtyä oikealle. Mutta tässä vaiheessa, olisimme huomata, että me olemme null solmussa. Siellä ei ole mitään. Mikään jossa 10 pitäisi olla. Tämä on, jos voimme ilmoittaa vika - että on todellakin Ei 10 puussa. Ja lopuksi, mennään läpi jos yritämme etsiä 1 puussa. Tämä on samanlainen kuin mitä tapahtuu, jos etsiä 10, paitsi sen sijaan menee oikealle, aiomme mennä vasemmalle. Aloitetaan 7 ja nähdä, että 1 on pienempi kuin 7, joten liikkumaan vasemmalle. Saamme 3 ja nähdä, että 1 on pienempi kuin 3, joten jälleen yritämme siirtyä vasemmalle. Tässä vaiheessa meillä null solmun, joten jälleen voimme raportoida vika. 

Jos et halua oppia lisää binääripuita, olemassa koko joukko hauskoja pikku ongelmia, voit tehdä heidän kanssaan. Ehdotan harjoitellaan piirustuksen pois näistä kaavioiden yksi kerrallaan ja sen jälkeen läpi kaikki eri vaiheet, koska tämä tulee super-kätevää ei vain teet Huffman koodaus ongelma setti mutta myös tulevaisuudessa kursseja - vain oppia miten tehdä näitä tietorakenteita ja ajatella läpi ongelmia kynällä ja paperilla tai, tässä tapauksessa, iPad ja stylus. 

Tässä vaiheessa kuitenkin aiomme siirtyä tekemään joitakin koodaus käytännössä ja todella pelata näitä binääripuita ja nähdä. Aion siirtyä takaisin yli tietokoneeseen. Tämän osan osa, sen sijaan, että käytetään CS50 Run tai CS50 tilat, Aion käyttää laitetta. 

Jälkeen yhdessä Ongelma Set erittely, Näen, että minun pitäisi avata laitteen menen Dropbox kansioon, luo kansio nimeltä 7 §, ja sitten luoda tiedoston nimeltä binary_tree.c. Täällä mennään. Minulla laite jo auki. Aion vetää ylös terminaali. Aion mennä Dropbox kansioon, tee hakemistoon section7, ja nähdä se on täysin tyhjä. Nyt aion avata binary_tree.c. Selvä. Täällä mennään - tyhjän tiedoston. 

Mennään takaisin spesifikaation. Eritelmä pyytää luomaan uudenlaisen määritelmän varten binääripuu solmu sisältää int arvot - kuten arvot, joita me veti pois meidän kaavio ennen. Me aiomme käyttää tätä boilerplate typedef että olemme tehneet täällä että sinun pitäisi tunnistat Harjoitus 5 - jos teit hash table tapa valloittaa speller ohjelman. Sinun tulisi myös tunnistaa sen viime viikon jaksossa jossa puhuimme linkitettyjä listoja. Meillä tämä typedef of struct solmu, ja olemme antaneet tämän struct solmu tämä nimi struct solmu etukäteen jotta voimme viitata siihen, koska me haluamme olla struct solmu osoittimet osana struct, mutta olemme silloin ympäröi tätä - tai pikemminkin, suljettu tätä - typedef niin, että myöhemmin koodia, voimme viitata tähän struct kuin vain solmun sijasta struct solmu. 

Tämä tulee olemaan hyvin samanlainen yksittäin-linkitetty lista määritelmä että näimme viime viikolla. Voit tehdä tämän, haluan vain aloittaa kirjoittamisen boilerplate. Tiedämme, että meillä on oltava kokonaisluku, niin me laittaa int arvon, ja sitten sen sijaan, että vain yksi osoitin seuraavaan elementtiin - kuten teimme yksin-linkitettyjen listojen - aiomme olla vasemmalle ja oikealle lapselle viitteitä. Se on melko yksinkertainen liikaa - struct solmu * vasen lapsi; ja struct solmu * oikea lapsi;. Cool. Tuo näyttää melko hyvä alku. Mennään takaisin spesifikaation. 

Nyt meidän täytyy julistaa maailmanlaajuinen solmu * muuttuja juuri puu. Me aiomme tehdä tämän maailmanlaajuisen aivan kuten teimme ensimmäinen osoitin meidän linkitetty lista myös maailmanlaajuisesti. Tämä oli niin, että toiminnot, jotka me kirjoittaa meillä ei ole pidettävä kulkee ympärillä root - Vaikka näemme, että jos et halua kirjoittaa näitä toimintoja rekursiivisesti, se voisi olla parempi olla edes sitä tule noin globaalina ensiksi vaan alustaa sen paikallisesti omassa päätehtävä. Mutta teemme sen maailmanlaajuisesti aloittaa. Jälleen annamme pari tiloja, ja aion julistaa solmuun * root. Vain varmista, että en jätä tätä alustamattoman, aion asettaa sen yhtä null. Nyt, päätehtävä - jonka me kirjoittaa todella nopeasti täällä - int main (int argc, const char * argv []) - ja aion aloittaa julistamaan minun argv levyjärjestelmän const juuri niin että tiedän että nämä väitteet ovat väitteitä, että en luultavasti halua muokata. Jos haluan muuttaa niitä minun pitäisi luultavasti kopioita niistä. Näet paljon koodia. Se on hieno kumpaankaan suuntaan. On hienoa jättää se - jätä const jos haluat. En yleensä laita se vain niin, että muistutan itseäni  että en luultavasti halua muuttaa näitä väitteitä. 

Kuten aina, aion sisällyttää tähän return 0 linjan lopussa tärkein. Täällä, aion alustaa minun juurisolmun. Koska se on nyt, minulla osoitin, joka on asetettu nollaksi, joten se on suunnattu mitään. Jotta todella alkaa rakentaa solmu, Minun täytyy ensin varata muistia se. Aion tehdä tekemällä muisti kasaan käyttäen malloc. Aion asettaa root yhtä tulosta malloc, ja aion käyttää sizeof operaattori laskea koko solmun. Syystä, että käytän sizeof solmu toisin kuin vaikkapa tehdä jotain tällaista - malloc (4 + 4 +4) tai malloc 12 - on koska haluan koodin olla mahdollisimman yhteensopivia. Haluan pystyä ottamaan tämän. C tiedostoa, kääntää sen laitteen ja sitten koota se minun 64-bittinen Mac - tai täysin eri arkkitehtuuria - ja haluan tämän kaiken toimimaan samoin. 

Jos teen oletuksia koko muuttujien - koko int tai koko osoittimen - Sitten olen myös tehdä oletuksia erilaisia ​​arkkitehtuureja johon minun koodi voi menestyksekkäästi kääntää ajettaessa. Aina käyttää sizeof toisin kuin manuaalisesti summaamalla struct kentät. Toinen syy on se, että voi olla täyte, että kääntäjä pannaan struct. Vaikka vain yhteen yksittäiset kentät ei ole jotain, että te yleensä halua tehdä, niin, poista se rivi. Nyt todella alustamaan tätä juurisolmu Aion pitää kytkeä arvot kullekin sen eri aloilla. Esimerkiksi arvo Tiedän haluan alustaa 7, ja nyt aion asettaa vasen lapsi on null ja oikea lapsi myös null. Hienoa! Olemme tehneet että osa spec. 

Eritelmä alas alareunassa sivun 3 Joudun luoda kolme solmua - toinen sisältää 3, joista yksi sisälsi 6, ja yksi, jossa on 9 - ja sitten lanka niitä niin se näyttää täsmälleen samalta kuin meidän puukaavion että puhuimme aiemmin. Tehdään se melko nopeasti täällä. Näet todella nopeasti, että aion alkaa kirjoittaa joukko päällekkäisiä koodi. Aion luoda solmuun *, ja aion kutsua sitä kolme. Aion asettaa se yhtä malloc (sizeof (solmu)). Aion asettaa kolme> value = 3. Kolme -> left_child = NULL; kolme -> oikea _child = NULL; samoin. Se näyttää melko samanlainen alustettaessa root, ja se on juuri Aion pitää tehdä, jos aloitan alustuksen 6 ja 9 sekä. Teen sen todella nopeasti täällä - itse asiassa, aion tehdä vähän kopioi ja liitä, ja varmista, että minä - okei.  Nyt minulla on kopioitu ja voin mennä eteenpäin ja asettaa tämä vastaa 6. Voit nähdä, että tämä vie aikaa, ja ei ole super-tehokasta. Vain vähän, me kirjoittaa funktio, joka tekee tämän meille. Haluan korvata tätä 9, vaihda, että 6. 

Nyt meillä on kaikki meidän solmujen luotu ja alustettu. Meillä myös root asettaa yhtä 7 tai sisältää arvon 7, meidän solmu, joka sisältää 3, meidän solmu, joka sisältää 6, ja meidän solmu, joka sisältää 9. Tässä vaiheessa meidän täytyy tehdä, on lanka kaiken ylös. Syystä alustetaan kaikki viitteitä null on vain niin, että olen varmista, että Minulla ei ole mitään alustamattoman viitteitä sinne vahingossa. Ja myös koska tässä vaiheessa, minulla on vain todella yhdistää solmut toisiinsa - kuin ne, jotka he todella kytketty - Minun ei tarvitse käydä läpi ja tehdä Varmista, että kaikki nollat ​​ovat siellä oikeissa paikoissa. 

Alkaen juureen, tiedän että juuren vasemman lapsen on 3. Tiedän, että root oikeus lapsi on 9. Sen jälkeen, ainoa lapsi, joka minulla on jäljellä murehtia on 3: n oikea lapsi, joka on 6. Tässä vaiheessa kaikki näyttää aika hyvältä. Me poistaa joitakin näistä linjat. Nyt kaikki näyttää aika hyvältä. Mennään takaisin meidän toiveiden ja mitä meidän täytyy tehdä seuraavaksi. 

Tässä vaiheessa meidän on kirjoittaa toiminto nimeltään "sisältää" jossa prototyyppi "bool sisältää (int arvo)". Ja tämä on toiminto tulee palauttaa true  jos puu huomautti meidän globaali root muuttuja  sisältää arvon johdetaan funktio ja vääriä toisin. Mennään eteenpäin ja tehdä sitä. Tämä tulee olemaan aivan kuten haku, että teimme käsin iPad vain vähän sitten. Katsotaanpa zoomata takaisin hieman ja selaamalla ylös. Me aiomme laittaa tämä toiminto oikeutta edellä meidän päätehtävä niin että meidän ei tarvitse tehdä minkäänlaista prototyyppien. Joten, bool sisältää (int arvo). Siellä mennään. On meidän boilerplate ilmoituksen. Vain varmista, että se kokoaa, Aion mennä eteenpäin ja vain asettaa se yhtä palauttaa false. Juuri nyt tämä toiminto vain ei tehdä mitään ja aina kertoa, että arvo että etsimme ole puussa. 

Tässä vaiheessa se on luultavasti hyvä ajatus - koska olemme kirjoittanut koko joukko koodin emmekä ole edes kokeillut testata sitä vielä - varmista, että se kaikki kokoaa. On pari asiaa, jotka meidän on tehtävä varmistaa, että tämä todella kääntää. Ensinnäkin, onko olemme käyttäneet mitään toimintoja kaikissa kirjastoissa, jotka emme ole vielä mukana. Toimintoja olemme käyttäneet tähän asti ovat malloc, ja sitten olemme myös tämäntyyppisten - tämä kirjakieleen tyyppinen kutsutaan bool' - joka sisältyy standardi bool otsikkotiedosto. Haluamme ehdottomasti sisällyttää standardin bool.h varten bool tyyppi, ja haluamme myös # include standardin lib.h varten standardin kirjastot jotka sisältävät malloc, ja ilmainen, ja kaikki tämä. Joten, loitontaa, aiomme lopettaa. Kokeillaan ja varmista, että tämä oli tehnyt käännöksen. Näemme, että se tekee, niin olemme oikealla tiellä. 

Katsotaanpa avata binary_tree.c uudelleen. Se kokoaa. Mennään alas ja varmista, että lisäämme muutamia puheluita meidän on toimintomoduuleja - vain varmista, että se on ihan hyvä. Esimerkiksi kun teimme hakuja meidän puu aiemmin, Yritimme etsiä arvot 6, 10 ja 1, ja tiesimme, että 6 oli puu, 10 ei ollut puussa, ja 1 ei ollut puussa joko. Katsotaanpa käyttää näitä näyte puheluihin tapa selvittää, onko meidän Sisältää toiminto toimii. Jotta niin, että aion käyttää printf toimintoa, ja aiomme tulostaa tuloksen puhelun sisältää. Aion laittaa merkkijono "sisältää (% d) = koska  aiomme pistoke arvon että aiomme etsiä, ja =% s \ n ", ja käyttää sitä meidän muotomerkkijonoa. Olemme juuri menossa nähdä - kirjaimellisesti tulostaa ruudulla - mitä näyttää funktiokutsuna. Tämä ei ole oikeastaan ​​toimintoa puhelun.  Tämä on vain merkkijono suunniteltu näyttämään funktiokutsuna. 

Nyt aiomme kytkeä arvot. Aiomme kokeilla sisältää 6, ja sitten mitä aiomme tehdä tässä käyttää sitä ternäärisen operaattori. Katsotaanpa - sisältää 6 - niin, nyt olen sisälsi 6 ja jos sisältää 6 on totta, merkkijono aiomme lähettää% s paluukutsumäärä tulee olemaan merkkijonon "tosi". Katsotaanpa vieritä hieman. Muuten, haluamme lähettää merkkijonon "vääriä" jos sisältää 6 palaa vääriä. Tämä on hieman typerä näköinen, mutta ajattelin voisin yhtä hyvin kuvaavat mitä ternäärinen operaattori näyttää, koska emme ole nähneet sitä jonkin aikaa. Tämä on mukava, kätevä tapa selvittää, jos meidän Contains toiminto toimii. Aion siirtyä takaisin yli vasemmalle, ja aion kopioida ja liittää tämän linjan muutaman kerran. Se muutti joitakin näistä arvoista ympärillä, joten tämä tulee olemaan 1, ja tämä tulee olemaan 10. 

Tässä vaiheessa meillä kiva Contains toimintoa. Meillä on joitakin testejä, ja näemme, jos tämä kaikki toimii. Tässä vaiheessa olemme kirjoittaneet hieman koodia. Aika lopettaa pois ja varmista, että kaikki vielä kokoaa. Lopeta ulos, ja nyt yritetään tehdä binääripuu uudelleen. No, näyttää siltä meillä virhe, ja meillä tämä nimenomaisesti todetaan kirjaston funktion printf. Se näyttää meidän mennä ja # include standardio.h. Ja siitä, että kaiken pitäisi laatia. Olemme kaikki hyviä. Nyt voit kokeilla binääripuu ja katso mitä tapahtuu. Täällä me olemme,. / Binary_tree, ja näemme, että odotimme - koska emme ole toteutettu sisältää vielä tai pikemminkin olemme vain laittaa vastineeksi väärä - näemme, että se on juuri palaamassa vääriä niistä kaikista, Niin, että kaikki työskentelevät pääosin melko hyvin. 

Mennään takaisin ja todella toteuttaa sisältää tässä vaiheessa. Aion vierittää alaspäin, zoomata ja - Muista, algoritmi jota käytimme oli Aloitimme juurisolmua ja sitten jokaisessa solmussa että kohtaamme, teemme vertailua, ja perustuu siihen, että vertailun me joko siirtyä vasemmalle lapsen tai oikealle lapselle. Tämä on menossa muistuttavat hyvin binäärihakupuu koodi, joka me kirjoitti aikaisemmin aikavälillä. Kun lähdetään, me tiedämme, että me haluamme pitää kiinni nykyisestä solmuun että me tarkastelemme, ja nykyinen solmu tulee olemaan alustetaan juurisolmuun. Ja nyt, me aiomme jatkaa läpi puu, ja muista, että meidän pysäyttää kunnossa -  kun me itse työskennellyt läpi esimerkiksi käsin - oli kun törmäsimme null solmu, ei kun me katsoimme null lapsi, vaan kun me todella siirretään solmu puussa ja totesi, että me olemme null solmussa. Aiomme toistaa kunnes nyk. ei vastaa null. Ja mitä me teemme? Aiomme testata (nyk. -> arvo == arvo), tiedämme, että olemme todella löytäneet solmu, että etsimme. Joten tässä, voimme palata totta. Muussa tapauksessa, haluamme onko arvo on pienempi kuin arvo. Jos nykyinen solmun arvo on pienempi kuin arvo etsimme, aiomme siirtyä oikealle. Joten nyk. = nyk. -> right_child, ja muuten, aiomme siirtyä vasemmalle. nyk. = nyk. -> left_child;. Melko yksinkertainen. 

Olet luultavasti tunnistaa silmukka, joka näyttää hyvin samankaltainen tätä alkaen binäärihakupuu aiemmin aikavälillä, paitsi silloin olimme tekemisissä alhainen, keski ja korkea. Täällä meillä on vain katsoa käyvän arvon joten se on mukava ja yksinkertainen. Tehdään varmista tämä koodi toimii. Ensinnäkin, varmista, että se kokoaa. Näyttää se. Yritetään käynnissä se. Ja todellakin, se tulostaa kaiken odotimme. Se löytää 6 puussa, ei löydä 10, koska 10 ei puussa, ja ei löydä 1 joko koska 1 ei myöskään ole puussa. Cool stuff. 

Selvä. Mennään takaisin meidän toiveiden ja nähdä mitä seuraavaksi. Nyt se haluaa lisätä hieman solmut meidän puuhun. Se haluaa lisätä 5, 2 ja 8, ja varmista, että sisältää koodia toimii edelleen odotetusti. Mennään tekemään se. Tässä vaiheessa, eikä tee se harmittaa kopioi ja liitä uudelleen, Kirjoitetaan funktio itse luoda solmu. Jos me selaa aina tärkein, huomaamme, että olemme tehneet tätä hyvin samankaltaisia ​​koodi uudestaan ​​ja uudestaan ​​aina, että haluamme luoda solmuun. 

Kirjoitetaan funktio, joka todella rakentaa solmu meille ja palauta se. Aion kutsua sitä build_node. Aion rakentaa solmu erityinen arvo. Zoom täällä. Ensimmäinen asia aion tehdä todella luovat tilaa solmulle kasaan. Joten, solmu * n = malloc (sizeof (solmu)), n -> arvo = arvo; ja sitten täällä, olen juuri menossa alustaa kaikki kentät sopivina arvoihin. Ja aivan lopussa, palaamme meidän solmu. Selvä. Yksi asia huomata, että tämä toiminto täällä aikoo palata osoittimen muistin että on kasa kohdennettu. Mitä mukavaa tästä on se, että tämä solmu nyt - Meidän täytyy julistaa sen kasaan, sillä jos me julisti sen pinoon emme voi tehdä sitä tässä toimivat näin. Että muisti menisi pois soveltamisalasta ja olisi pätemätön, jos yritimme käyttää sitä myöhemmin. Koska olemme julistaa keko-jaettu muisti, aiomme pitää huolehtia vapauttaa myöhemmin meidän ohjelma ei vuoda mitään muistia. Olemme punting että kaikki muu koodi vain yksinkertaisuuden vuoksi tuolloin, mutta jos joskus kirjoittaa toiminto, joka näyttää tältä jossa sinulla - jotkut kutsuvat sitä malloc tai realloc sisällä - haluat varmistaa, että voit laittaa jonkinlainen kommentti täällä sanotaan, Hei, te tiedätte, palauttaa keon Kohdistamattomat solmu alustettu läpikulkevien-arvo. Ja sitten haluat varmistaa, että voit laittaa jonkinlainen huomaa, että sanoo soittaja on vapautettava takaisin muistiin. Näin, jos joku joskus menee ja käyttää tätä toimintoa, he tietävät, että mitä he saavat takaisin tämän tehtävän jossain vaiheessa täytyy vapauttaa. 

Olettaen, että kaikki on hyvin ja hyvä täällä, Voimme mennä alas meidän koodi ja korvaa kaikki nämä rivit täällä joissa vaaditaan meidän rakentaa solmuun toimintoa. Tehdään se todella nopeasti. Yksi osa, että emme aio korvata tämä osa täällä alaosassa, jossa me itse johdottaa solmut osoittavat toisiinsa, koska emme voi tehdä meidän tehtävämme. Mutta tehkäämme root = build_node (7), solmu * Kolme = build_node (3); solmu * Kuusi = build_node (6), solmu * Yhdeksän = build_node (9);. Ja nyt, halusimme myös lisätä solmuja - solmu * Viisi = build_node (5); solmu * Kahdeksan = build_node (8); ja mikä oli toinen solmu? Katsotaanpa täällä. Halusimme myös lisätä 2 - solmu * kaksi = build_node (2);. Selvä. Tässä vaiheessa tiedämme, että meillä 7, 3, 9, ja 6 kaikki johdotettu oikein, mutta entä 5, 8, ja 2? Pitää kaikki oikeassa järjestyksessä, Tiedämme, että kolme oikeus lapsen 6. Joten, jos aiomme lisätä 5, 5 kuuluu myös oikeassa reunassa puun joista 3 on juuri, niin 5 kuuluu kuin vasen lapsi 6. Voimme tehdä tämän sanomalla, kuusi -> left_child = viisi; ja sitten 8 kuuluu kuten vasen lapsi 9, joten yhdeksän -> left_child = kahdeksan; ja sitten 2 on vasen lapsi on 3, joten voimme tehdä sen täällä - sinulle -> left_child = kaksi;. Jos et ole aivan seuraa yhdessä, että sinun kannattaa piirtää sitä itse. 

Selvä. Säästetään tätä. Mennään ulos ja varmista, että se kokoaa, ja sitten voimme lisätä meidän Sisältää puhelut. Näyttää siltä, ​​että kaikki vielä kokoaa. Mennään sisään ja lisää joidenkin sisältää puhelut. Jälleen aion tehdä hieman kopioi ja liitä. Nyt etsitään 5, 8, ja 2. Selvä. Tehdään varma, että tämä kaikki näyttää hyvältä vielä. Hienoa! Tallenna ja lopeta. Nyt merkki, kääntää, ja nyt mennään juosta. Tuloksista näyttää siltä, ​​että kaikki toimii vain mukava ja hyvin. Hienoa! Joten nyt meillä meidän on toimintomoduuleja kirjoitettu. Siirrytään ja alkaa työstää miten lisätä solmut puuhun sillä, kuten teemme juuri nyt, asiat eivät ole kovin kaunis. 

Jos menemme takaisin eritelmää, Se pyytää meitä kirjoittamaan toiminto nimeltään lisätä - jälleen palaamassa bool varten vai emme voisi todella lisätä solmun puuhun - ja sitten arvo lisätä puuhun on määritetty ainoa argumentti meidän insert toimintoa. Palaamme true jos voisimme todellakin lisätä solmun sisältää arvon puuhun, mikä tarkoittaa sitä, että yksi oli riittävästi muistia, ja sitten kaksi, että solmu ei jo puussa, koska - Muista, emme aio olla päällekkäisiä arvoja puu, vain tehdä asiat yksinkertaisina. Selvä. Takaisin koodia. Avaa se. Lähennä vähän, rullaa sitten alaspäin. Laitetaan insertin toiminnon oikealla yläpuolella sisältää. Jälleen se tulee olemaan nimeltään bool insert (int arvo). Anna sille vähän enemmän tilaa, ja sitten, kuten oletus, Laitetaan vastineeksi false aivan lopussa. Nyt alas alareunassa, mennään eteenpäin ja sen sijaan käsin rakentaa solmut Tärkeimpien itseämme ja johdotus heidät osoittamaan toisiaan kuin me teemme, me luottaa meidän insert toiminto tehdä. Emme ole riippuvaisia ​​meidän insert toiminto rakentaa koko puun tyhjästä aivan vielä, vaan saamme eroon näistä linjat - we'll kommentoida näitä rivejä - että rakentaa solmut 5, 8, ja 2. Ja sen sijaan, me aseta puhelut meidän insertin toiminta varmistaa, että joka todella toimii. Täällä mennään. 

Nyt olemme kommentoineet näitä rivejä. Meillä on vain 7, 3, 9, ja 6 meidän puu tässä vaiheessa. Varmista, että tämä on kaikki työ, Voimme loitontaa, tekevät binääripuu, käyttää sitä, ja voimme nähdä, että on nyt kertoo meille, että olemme täysin oikeassa - 5, 8, ja 2 eivät ole enää puussa. Mene takaisin koodia, ja miten aiomme lisätä? Muistakaa mitä teimme, kun olimme todella lisäämällä 5, 8, ja 2 aiemmin. Soitimme että Plinko peli jossa aloitimme juuresta, meni alas puun yksi yksitellen kunnes löysimme sopivan raon, ja sitten me johdotettu solmussa sopivalla paikalla. Aiomme tehdä saman. Tämä on pohjimmiltaan kuin kirjallisesti koodin että käytimme sisältää funktion löytää paikan, jossa solmun pitäisi olla, ja sitten me vain lisätä solmuun tuolla. Aloitetaan näin. 

Joten meillä on solmu * nyk. = root; olemme juuri menossa seuraamaan sisältää koodia kunnes huomaamme, että se ei aivan toimi meille. Aiomme käydä läpi puun, kun nykyinen elementti ei ole nolla, ja jos huomaamme, että nyk. n arvo on sama arvo, yritämme lisätä - No, tämä on yksi niistä tapauksista, joissa emme voi oikeastaan ​​lisätä solmun puuhun, koska tämä tarkoittaa, että meillä on päällekkäisiä arvoa. Täällä olemme todella palaamassa vääriä. Nyt, if nyk.: n arvo on pienempi kuin arvo, Nyt tiedämme, että meidän siirtyä oikealle  koska arvo kuuluu oikeassa puolessa nyk. puu. Muuten aiomme siirtyä vasemmalle. Se on pohjimmiltaan meidän on toimintomoduuleja oikeassa. 

Tässä vaiheessa, kun olemme valmistuu tänä aikana silmukka, meidän nyk. osoitin aiotaan osoittaa null Jos toiminto ei ole jo palannut. Olemme siis ottaa nyk. paikassa, missä haluamme lisätä uusi solmu. Mitä on vielä tehtävä on todella rakentaa uuden solmun, jonka voimme tehdä melko helposti. Voimme käyttää super kätevä rakentaa solmu funktio, ja jotain, että emme tee aikaisemmin - me vain eräänlainen otti itsestäänselvyytenä, mutta nyt teemme vain varmistaa - me testata varmistaa, että arvo palauttama uusi solmu oli todella ei null, koska emme halua aloittaa päästä, että muisti jos se on tyhjä. Voimme testata varmistaa, että uusi solmu ei ole yhtä kuin nolla. Tai sen sijaan, voimme vain nähdä, jos se todella on nolla, ja jos se on tyhjä, niin voimme vain palata vääriä aikaisin. 

Tässä vaiheessa meidän on lanka uuteen solmun asianmukaisen paikalla puussa. Jos katsomme taaksepäin tärkeimmät ja missä olimme todella johdot arvot ennen, näemme, että niin teimme sen, kun halusimme laittaa 3 puussa oli meillä näytetty vasen lapsi juuren. Kun laitamme 9 puussa, meillä oli saada oikea lapsi juuren. Meidän täytyi olla osoitin vanhemman pannakseen uuden arvon puuhun. Rullaat jopa lisätä, että ei aio aivan toimi täällä koska meillä ei ole vanhemman osoitin. Mitä halutaan pystyä tekemään on, tässä vaiheessa, Tarkista vanhemman arvosta ja nähdä - hyvin, Gosh, jos vanhempi: n arvo on pienempi kuin nykyinen arvo, sitten vanhemman oikeus lapsen pitäisi olla uuden solmun; muuten vanhemman vasen lapsi olisi uusi solmu. Mutta meillä ei ole tätä vanhemman osoitin ihan vielä. 

Saadakseen sen, olemme todella täytyy seurata sitä kun käymme läpi puun ja löytää sopiva paikalla meidän silmukan yli. Voimme tehdä sen siirtymällä takaisin ylös meidän insertin toiminta ja seuranta toinen osoitin muuttuja nimeltä vanhempi. Me aiomme asettaa sen yhtä null aluksi, ja sen jälkeen joka kerta käymme läpi puu, aiomme asettaa vanhemman osoitin vastaamaan nykyistä osoitin. Aseta vanhempi vastaa nyk.. Näin joka kerta käymme läpi, aiomme varmistaa, että nykyinen osoitin muuttuu kasvatetaan Emoyhtiön osoitin seuraa sitä - vain yksi korkeampi kuin nykyiset osoitin puussa. Että kaikki näyttää aika hyvältä. 

Mielestäni yksi asia, että me haluamme muuttaa tämä rakentaa solmu palaa null. Saadakseen rakentaa solmuun todella onnistuneesti palata null, meidän täytyy muuttaa, että koodia, koska täällä, emme koskaan testattu varmistaa, että malloc palasi kelvollinen osoitin. Joten, jos (n! = NULL), sitten - jos malloc palautetaan kelvollinen osoitin, niin me alustaa sen; muuten me vain palata ja jotka päätyvät takaisin null meille. Nyt kaikki näyttää aika hyvältä. Tehkäämme että tämä todella kokoaa. Tee binääripuu, ja oi, meillä on joitakin juttuja täällä. 

Meillä implisiittinen ilmoitus toiminnon rakentaa solmun. Jälleen nämä kääntäjät, aiomme aloittaa huipulla. Mitä se täytyy tarkoittaa, että soitan rakentaa solmuun ennen kuin olen itse julisti sen. Mennään takaisin koodia todella nopeasti. Selaa alaspäin, ja totta tosiaan, minun insertti toiminto on julistettu yläpuolella rakentaa solmu funktio, mutta yritän käyttää rakentaa solmuun sisällä insertin. Aion mennä ja kopioi - ja liitä rakentaa solmu funktio asti täällä ylhäällä. Näin toivottavasti se toimii. Annetaan tämän toisen mennä. Nyt se kaikki kokoaa. Kaikki on hyvin. 

Mutta tässä vaiheessa, emme ole kutsuttu meidän insert toimintoa. Tiedämme vain, että se kokoaa, joten mennään sisään ja laittaa puhelut tuumaa Tehdään se meidän pääasiallinen tehtävä. Täällä, kommentoi out 5, 8, ja 2, ja sitten emme johdottaa niitä tänne. Tehdään muutamia puheluita lisätä, ja mennään myös käyttää samanlaisia ​​juttuja, että käytimme kun teimme nämä printf puhelut varmistaa, että kaikki eivät saa asennettu oikein. Aion kopioida ja liittää, ja sen sijaan sisältää aiomme tehdä insertin. Ja sen sijaan 6, 10, ja 1, aiomme käyttää 5, 8, ja 2. Tämä olisi toivottavasti lisätä 5, 8, ja 2 puuhun. Kokoa. Kaikki on hyvin. Nyt me todella ajaa ohjelmaamme. 

Kaikkea palasi vääriä. Joten, 5, 8, ja 2 ei mene, ja se näyttää Contains eivät löytäneet niitä. Mitä on tekeillä? Mennään loitontaa. Ensimmäinen ongelma oli, että insertti tuntui palata vääriä, ja se näyttää että koska lähdimme paluumatkalle vääriä puhelun emmekä oikeastaan ​​koskaan palannut totta. Voimme asettaa, että ylös. Toinen ongelma on, nyt vaikka teemme - pelastaa tämä, lopeta tätä, ajaa tekemään uudelleen, on se kääntää, niin suorita se - näemme, että jotain muuta täällä on tapahtunut. 5, 8, ja 2 olivat vielä koskaan löydetty puussa. Joten, mitä on tekeillä? 

Katsotaanpa katsomaan tätä koodia. Katsotaan jos voimme selvittää tämän. Aloitamme vanhemman ei ole null. Asetamme kulloisenkin sama root osoitin, ja aiomme työskennellä tiemme alas puusta. Jos nykyinen solmu ei ole nolla, niin tiedämme, että voimme liikkua alas hieman. Asetimme vanhemman osoitin vastattava nykyistä osoitin, tarkastetaan arvo - jos arvot ovat samat palasimme vääriä. Jos arvot ovat vähemmän muutimme oikealle; muuten, muutimme vasemmalle. Sitten me rakennamme solmu. Minä suurentaa hieman. Ja tässä me aiomme yrittää johdottaa arvot olla samat. Mitä on tekeillä? Katsotaan jos mahdollisesti Valgrind voi antaa meille vihjeen. 

Haluan käyttää Valgrind vain siksi Valgrind todella tyhjenee nopeasti ja kertoo onko muisti virheitä. Kun otamme Valgrind on koodi, kuten näette oikealla here--Valgrind./binary_tree--and paina enter. Huomaatte, että meillä ei ole mitään muistikuvaa virhettä, joten se näyttää kaikki on kunnossa toistaiseksi. Meillä on joitakin muistivuotoja, jonka tiedämme, koska me emme ole tapahtumassa vapauttaa kaikki meidän solmuja. Yritetään käynnissä GDB nähdä, mitä todella tapahtuu. Teemme GDB. / Binary_tree. Se käynnistetty hienosti. Katsotaanpa asettaa kulmapisteen insertti. Katsotaanpa juosta. Näyttää siltä, ​​emme koskaan oikeastaan ​​nimeltään insert. Näyttää siltä ongelma oli vain, että kun muutin tänne vuonna pääasiassa - kaikki nämä printf puhelut sisältää - En ole koskaan oikeastaan ​​muuttunut näiden soittaa insertin. Nyt antaa sille yrittää. Katsotaanpa koota. Kaikki näyttää hyvältä siellä. Nyt voit kokeilla sitä, mitä tapahtuu. Alright! Kaikki näyttää melko hyvä siellä. 

Viimeinen asia ajatella on, onko mitään reuna tapauksissa tähän lisätään? Ja näyttää siltä, ​​että hyvin, yksi reuna tapaus, joka on aina mielenkiintoista ajatella on, mitä tapahtuu, jos puu on tyhjä ja soitat tähän lisätään toiminto? Toimiiko se? No, katsotaanpa kokeilla sitä. - Binary_tree. C - Miten aiomme testata tätä, aiomme mennä alas meidän päätehtävä, ja kaapeloinnin sijaan nämä solmut näin, olemme juuri menossa kommentoida ulos koko juttu, ja johdotuksen sijasta jopa solmut itseämme, Voimme oikeastaan ​​vain mennä eteenpäin ja poistaa kaikki tämän. Aiomme tehdä kaiken puhelun lisätä. Joten, tehkäämme - sijasta 5, 8, ja 2, aiomme lisätä 7, 3, ja 9. Ja sitten me myös haluamme lisätä 6 samoin. Tallenna. Lopeta. Tee binääripuu. Kaikki kokoaa. Voimme vain ajaa se on ja mitä tapahtuu, mutta se myös tulee olemaan todella tärkeää varmistaa, että meillä ei ole mitään muisti virheitä, sillä tämä on yksi reuna tapauksissa tiedämme. 

Tehdään varmista, että se toimii hyvin Valgrind, jonka teemme vain hieman käynnissä Valgrind. / binary_tree. Se näyttää meillä todellakin on yksi virhe yhdeltä yhteydessä - meillä on tämä segmentointi vika. Mitä tapahtui? Valgrind oikeastaan ​​kertoo meille, missä se on. Pienennä hieman. Se näyttää siltä kuin se tapahtuu meidän insert-toiminto, jossa meillä on virheellinen luku on kooltaan 4: insert, rivi 60. Mennään takaisin ja nähdä, mitä on tekeillä. Pienennä todella nopeasti. Haluan varmistaa, että se ei mene näytön reunaan, jotta voimme nähdä kaiken. Vedä että hieman. Selvä. Selaa alaspäin, ja ongelma on juuri tässä. Mitä tapahtuu, jos saamme alas ja nykyinen solmu on jo tyhjä, meidän vanhempi solmu on null, niin jos katsomme ylös hyvin alkuun, täällä - Jos tämä taas silmukka koskaan suorittaa koska nykyinen arvo on nolla - meidän root on nolla niin nyk. on null - Sitten meidän vanhempi ei koskaan saa asettaa nyk. tai kelvollisen arvon, niin, vanhempi myös null. Meidän täytyy muistaa tarkistaa, että mennessä saamme tänne, ja alamme päästä vanhemman arvosta. Joten, mitä tapahtuu? No, jos vanhempi on null - jos (vanhempi == NULL) - tiedämme, että ei saa olla mitään puussa. Meidän täytyy yrittää lisätä sen juureen. Voimme tehdä sen vain asettamalla root sama uusi solmu. Sitten tässä vaiheessa, emme oikeastaan ​​halua käydä läpi näitä muita asioita. Sen sijaan täällä, voimme tehdä joko else-if-else, tai voisimme yhdistää kaiken tänne muuta, mutta täällä me vain käyttää muuta ja tehdä niin. Nyt aiomme testata varmistaa, että vanhempi ei ole nolla sitä ennen todella yrittää päästä omilla. Tämä auttaa meitä välttämään segmentointi vika. Joten me lopettaa, loitontaa, kääntää, juosta. 

Ei virheitä, mutta meillä on vielä joukko muistivuotoja koska emme vapauttamaan kaikki meidän solmuja. Mutta, jos me menemme ylös tänne ja katsomme meidän tuloste, näemme, että hyvin, näyttää kaikki meidän insertit olivat palaamassa totta, mikä on hyvä. Insertit ovat kaikki totta, ja sitten sopiva Sisältää puhelut ovat myös totta. 

Hyvää työtä! Näyttää olemme onnistuneesti kirjoitettu insertti. Siinä kaikki olemme tämän viikon Problem Set Specification. Yksi hauska haaste miettiä, miten te todella mennä ja vapaa kaikki solmut tämän puu. Voimme tehdä niin monella eri tavalla, mutta Jätän että jopa voit kokeilla, ja hauska haaste, kokeile ja varmista, että voit varmistaa että tämä Valgrind raportti palauttaa mitään virheitä eikä vuotoja. 

Onnea tämän viikon Huffman koodaus ongelma set, ja näemme ensi viikolla! [CS50.TV]