[Powered by Google Translate] [7 §: More Comfortable]
[Rob Bowden] [Harvardin yliopisto]
[Tämä on CS50] [CS50.TV]
Selvä. Niin kuin sanoin email,
Tämä tulee olemaan binary-puu-intensiivinen jakso.
Mutta ei ole kovin monia kysymyksiä.
Joten aiomme yrittää vetää ulos jokaiseen kysymykseen
ja mennä kivulias yksityiskohtaisesti kaikista parhaita tapoja tehdä asioita.
Joten heti alussa, käymme läpi näytteen piirustukset binääripuita ja tavaraa.
Joten tässä, "Muista, että binääripuu on solmuja kaltaisia ​​linkitetty lista,
paitsi yhden sijasta osoittimen on kaksi: yksi vasemmalla "lapsi"
ja yksi oikea "lapsi". "
Joten binääripuu on aivan linkitetyn listan,
lukuun ottamatta struct tulee olemaan kaksi osoitinta.
On trinary puita, jotka ovat menossa on kolme osoitinta,
on N-ary puita, joka on vain yleinen osoittimen
että sinulla on sitten malloc olla niin suuria
riittävästi osoittimia kaikki mahdolliset lapsille.
Joten binääripuu sattuu olemaan vakio määrä on kaksi.
Jos haluat, voit antaa linkitetyn listan unaarinen puu,
mutta en usko, että kukaan kutsuu sitä että.
"Piirrä laatikot-ja-nuolet kaavio binääripuun solmu
sisältävät Nate suosikki numero 7, jossa jokainen lapsi osoitin on nolla. "
Niin iPad tilassa.
>> Se tulee olemaan melko yksinkertainen.
Olemme juuri menossa on solmu, minä piirtää sen neliö.
Ja minä piirtää arvojen täällä.
Joten arvo menee tänne,
ja sitten täällä meillä on vasemman osoittimen vasemmalla ja oikealla osoitin oikealla.
Ja se on erittäin paljon, joten yleissopimuksen kutsua sitä vasemmalle ja oikealle, osoitin nimiä.
Molemmat tulevat olemaan null.
Se vain on nolla, ja se on vasta null.
Okei. Joten takaisin tänne.
"Kun linkitetty lista, meillä oli vain tallentaa osoittimen
ensimmäisen solmun luettelosta, jotta muistaa koko linkitetty lista, tai koko lista.
Samoin puita, meillä on vain tallentaa osoittimen
yhteen solmuun, jotta muistaa koko puun.
Tämä solmu on calle "root" puun.
Kehitä kaaviota ennen tai piirrä uusi
niin että sinulla on laatikoita ja-nuolet kuvaus binääripuun
kanssa arvo 7, sitten 3 vasemmalle,
sitten 9 oikealla puolella, ja sitten 6 oikealla puolella on 3 ".
Katsotaan jos muistan kaiken tuon päähäni.
Joten tämä tulee olemaan meidän root täällä.
Saamme joitakin osoitin jossain, jota me soitamme root,
ja se osoittaa tämän kaveri.
Nyt tehdä uusi solmu,
mitä olemme, 3 vasemmalla?
Joten uusi solmu, jossa on 3, ja se aluksi osoittaa null.
Laitan N.
Nyt haluamme, että mennä vasemmalle 7.
Joten me muuttaa osoittimen nyt kohta tämän kaveri.
Ja me teemme samoin. Haluamme 9 tänne
joka alun perin vain sanoo null.
Me aiomme muuttaa tätä osoitin, kohta 9,
ja nyt haluamme laittaa 6 oikealle 3.
Joten se tulee - tehdä 6.
Ja kaveri osoittaa sinne.
Okei. Niin, että kaikki se pyytää meitä tekemään.
>> Nyt mennään yli joitakin terminologiaa.
Olemme jo puhuneet siitä, miten puun juurta on Ylimmässä solmu puussa.
, Joka sisältää 7. Solmujen alareunassa puun kutsutaan lehtiä.
Jokainen solmu joka juuri on nolla sen lapset on lehtiä.
Niin se on mahdollista, jos meidän binääripuu on vain yksi solmu,
että puu on lehtiä, ja se on siinä.
"Korkeus" puun on hyppyjen määrä sinun täytyy tehdä
saada ylhäältä lehtiä. "
Pääsemme, toisessa, erotus
välillä symmetrinen ja epäsymmetrinen binääripuita,
mutta nyt kokonaiskorkeus tämän puun
Sanoisin on 3, mutta jos lasketaan hyppyjen määrä
sinun täytyy tehdä saadakseen 9, niin se on oikeastaan ​​vain korkeus 2.
Juuri nyt tämä on epätasapainoinen binääripuu,
mutta me puhuimme tasapainossa, kun se saa olla merkitystä.
Joten nyt voimme puhua solmuja puu kannalta
suhteessa muihin solmuihin puussa.
Joten nyt meillä on vanhemmat, lapset, sisarukset, esivanhemmat ja jälkeläiset.
Ne ovat melko tervettä järkeä, mitä ne tarkoittavat.
Jos kysymme - sen vanhemmat.
Joten mikä on vanhempi 3?
[Opiskelijat] 7. >> Joo. Vanhempi vain olemaan mitä osoittaa sinulle.
Sitten mitä lapset 7?
[Opiskelijat] 3 ja 9. >> Joo.
Huomaa, että "lapset" tarkoittaa kirjaimellisesti lapsia,
joten 6 ei sovelleta, koska se on kuin lapsenlapsi.
Mutta jos menemme jälkeläisiä, niin mitkä ovat jälkeläisiä 7?
[Opiskelijat] 3, 6 ja 9. >> Joo.
Jälkeläisiä juurisolmun tulee olemaan kaiken puun,
paitsi ehkä juurisolmu itse, jos et halua katsoa, ​​että jälkeläinen.
Ja lopuksi, esivanhemmat, joten se on vastakkaiseen suuntaan.
Mitkä ovat esi 6?
[Opiskelijat] 3 ja 7. >> Joo. 9 ei sisälly.
Se on vain suoraa linjaa takaisin root
tulee olemaan teidän esivanhempien.
>> "Sanotaan, että binääripuu on" tilattu ", jos kunkin solmun puu,
kaikki sen jälkeläiset vasemmalla on pienempi arvoista
ja kaikki ne oikealla puolella on suuremmat arvot.
Esimerkiksi puu edellä on tilattu, mutta se ei ole ainoa mahdollinen määräsi järjestely. "
Ennen kuin pääsemme siihen,
määräsi binääripuu tunnetaan myös binäärihakupuu.
Täällä sattuvat olemaan kutsuen sitä määräsi binääripuu,
mutta en ole koskaan kuullut sitä kutsutaan tilattu binääripuu ennen,
ja tietovisa olemme paljon todennäköisemmin laittaa binäärihakupuu.
Ne ovat yksi ja sama,
ja se on tärkeää sinulle tunnistaa eron binääripuu ja binäärihakupuu.
Binääripuu on vain puu, joka osoittaa kaksi asiaa.
Jokainen solmu osoittaa kaksi asiaa.
Ei ole perusteluja siitä arvoista että se osoittaa.
Niin kuin tänne, koska se binäärihakupuu,
me tiedämme, että jos menemme jäljellä 7,
Sitten kaikki arvot että voimme mahdollisesti päästä
menemällä jäljellä 7 on oltava pienempi kuin 7.
Huomaa, että kaikki arvot alle 7 ovat 3 ja 6.
Nämä kaikki ovat vasemmalla 7.
Jos menemme oikeaan 7, kaiken pitää olla suurempi kuin 7,
joten 9 on oikeus 7, joten olemme hyviä.
Tämä ei päde binääripuu,
säännöllistä binääripuun voimme vain 3 yläosassa, 7 vasemmalle,
9 vasemmalla 7; ei ole mitään tilaaminen arvojen lainkaan.
Nyt, emme todella tehdä tämän, koska se on työläs ja tarpeeton,
mutta "yrittää tehdä niin monta tilata puita voit ajatella
käyttäen numeroita 7, 3, 9, ja 6.
Kuinka monta erillistä järjestelyt ovat siellä? Mikä on korkeus jokainen? "
>> Teemme pari, mutta tärkein ajatus on,
Tämä ei ole millään tavalla ainutlaatuinen esitys binääripuu, jotka sisältävät näitä arvoja.
Tarvitsemme vain joitakin binääripuu joka sisältää 7, 3, 6 ja 9.
Toinen mahdollinen voimassa yksi olisi juuri on 3,
mene vasemmalle ja se on 6, mene vasemmalle ja se on 7,
mene vasemmalle ja se on 9.
Se on täysin pätevä binäärihakupuu.
Se ei ole kovin hyödyllistä, koska se on aivan kuin linkitetty lista
ja kaikki nämä viitteet ovat vain null.
Mutta se on pätevä puu. Niin?
[Student] Älä arvot on enemmän oikealla?
Vai onko tämä -? >> Nämä Aioin mennä toisinpäin.
Mukana on myös - joo, katsotaanpa vaihtaa se.
9, 7, 6, 3. Hyvä saalis.
Se on vielä totella mitä binääripuu haku on tarkoitus tehdä.
Joten kaikki vasemmalle on oltava pienempi kuin minkä tahansa solmu.
Voisimme vain liikkua, eli tämä 6 ja laittaa sen tänne.
Ei, emme voi. Miksi pitää tehdä, että?
Tehdäänpä - tässä on 6, täällä on 7, 6 pistettä 3.
Tämä on edelleen voimassa binäärihakupuu.
Mikä on vialla, jos I - Katsotaan jos voin keksiä järjestely.
Joo, okei. Joten mikä on vikana puu?
Olen kai jo antanut sinulle vihjeen, että on jotain vikaa.
Miksi pitää tehdä, että?
Okei. Tämä näyttää kohtuulliselta.
Jos tarkastelemme jokaisessa solmussa, kuten 7, sitten vasemmalle 7 on 3.
Joten meillä on 3, asia oikealla 3 on 6.
Ja jos tarkastellaan 6, asia oikealla 6 on 9.
Miksi tämä ei ole kelvollinen binäärihakupuu?
[Opiskelijat] 9 on edelleen vasemmalla 7. >> Joo.
Sen täytyy olla totta, että kaikki arvot voi mahdollisesti päästä menemällä vasemmalla 7 ovat alle 7.
Jos menemme jäljellä 7, saamme 3 ja voimme vielä päästä 6,
voimme silti saada 9, mutta mentyään alle 7,
Meidän ei pitäisi voida saada numero, joka on suurempi kuin 7.
Joten tämä ei ole kelvollinen binäärihakupuu.
>> Veljeni oli todellakin haastattelu kysymys
se oli pohjimmiltaan tämä, vain koodin jopa jotain validoida
onko puu on binäärihakupuu,
ja niin ensimmäinen asia, jonka hän teki, oli vain tarkistaa
jos vasen ja oikea ovat oikein, ja sitten toistaa sinne.
Mutta et voi vain tehdä niin, sinun täytyy seurata
siitä, että nyt kun olen mennyt jäljellä 7,
kaikki tämä alipuu on oltava alle 7.
Oikea algoritmi tarvitsee seurata
ja rajojen että arvot voivat mahdollisesti kuulua sisään
Emme mene läpi niitä kaikkia.
On kiva toistumisen suhteen,
vaikka emme ole saaneet niitä, tai emme pääse niihin,
määritellään kuinka monta todellisuudessa ovat.
Joten on 14 niistä.
Ajatus siitä, miten tekisit sen matemaattisesti on kuin,
Voit valita minkä tahansa ikinen olla juurisolmu
ja sitten jos otan 7 olla juurisolmu
sitten on, sanovat, jotkut numerot voivat mennä minun vasen solmu,
ja joitakin numeroita, jotka voivat olla minun oikea solmu,
mutta jos olen N Yhteensä numeroita, niin summa voi mennä vasemmalle
korotettuna joka voi mennä oikealle on n - 1.
Niin, että jäljelle jäävät numerot, niiden on kyettävä menemään joko vasemmalle tai oikealle.
On vaikeaa, että jos laitan 3 ensimmäinen sitten kaiken on mentävä vasemmalle,
mutta jos laitan 7, niin jotkut asiat voivat mennä vasemmalle ja jotkut asiat voivat mennä oikealle.
Ja '3 ensimmäinen "Tarkoitin kaikkea voi mennä oikealle.
Se on todella, sinun täytyy vain ajatella sitä,
kuinka paljon voi mennä seuraavalle tasolle puun.
Ja se tulee ulos on 14, tai voit piirtää ne kaikki,
ja sitten saat 14.
>> Going takaisin tänne,
"Tilattu binääripuita ovat viileitä, koska voimme etsiä niitä
hyvin samalla tavalla hakemisen yli lajitellaan matriisina.
Voit tehdä niin, aloitamme juuresta ja työskentelemme alas puusta
kohti lehtiä, tarkistaa kunkin solmun arvot arvojen vastaisia ​​olemme etsimässä.
Jos nykyinen solmun arvo on pienempi kuin arvo etsimme,
menet vieressä solmun oikea lapsi.
Muuten menet solmun vasen lapsi.
Jossain vaiheessa, voit joko löytää arvo etsit, tai voit törmätä null,
arvoa osoittava ei puussa. "
Minun täytyy piirtää puun meillä oli ennen, että otan toisen.
Mutta me haluamme etsiä onko 6, 10, ja 1 ovat puussa.
Joten mitä se oli, 7, 9, 3, 6. Okei.
Numerot haluat etsiä, haluamme etsiä 6.
Miten tämä algoritmi toimii?
No, meillä on myös joitakin root osoitin meidän puu.
Ja me menisi juuri ja sanoa, on tämä arvo vastaa arvoa olemme etsimässä?
Joten etsimme 6, joten se ei ole sama.
Joten pidämme menossa, ja nyt sanomme, okei, joten 6 on alle 7.
Tarkoittaako se, että haluamme mennä vasemmalle, vai haluammeko mennä oikealle?
[Student] Vasen. >> Joo.
Se on huomattavasti helpompaa, kaikki sinun tarvitsee vain vetää yhden mahdollisen solmu puun
ja sitten älä - sen sijaan, että yrittää ajatella oman pään,
okei, jos se on vähemmän, menen vasemmalle tai mennä oikealle,
vain katsomalla tätä kuvaa, se on hyvin selvää, että minun täytyy mennä vasemmalle
jos tämä solmu on suurempi kuin arvo, joka etsin.
Joten te mennä vasemmalle, nyt olen 3.
Haluan - 3 on pienempi kuin arvo etsin, joka on 6.
Joten menemme oikealle, ja nyt minä päädy 6,
mikä on arvo etsin, joten palaan totta.
Seuraava arvo aion etsiä on 10.
Okei. Joten 10, nyt on menossa - katkaista joka - aikoo seurata juuri.
Nyt, 10 tulee olemaan suurempi kuin 7, joten haluan katsoa oikealle.
Aion tulla tänne, 10 tulee olemaan suurempi kuin 9,
joten aion haluta katsoa oikealle.
Tulen tänne, mutta täällä nyt olen null.
Mitä teen, jos osuin null?
[Student] Return väärä? >> Joo. En löytänyt 10.
1 tulee olemaan lähes identtinen tapauksessa,
paitsi se vain menee kääntää, vaan tarkastella
alas oikealle puolelle, aion katsoa alas vasemmalle puolelle.
>> Nyt mielestäni itse saada koodin.
Tässä jos - avata CS50 laite ja navigoi perille,
mutta voit myös vain tehdä sen avaruudessa.
Se on luultavasti ihanteellinen tehdä se tilaan,
koska voimme työskennellä avaruudessa.
"Ensin me tarvitsemme uuden tyyppinen määritelmä binääripuu solmu sisältää int-arvoja.
Käyttämällä boilerplate typedef alla,
luoda uuden tyyppinen määritelmä solmun binääripuu.
Jos jäät jumiin. . . "Blaa, blaa, blaa. Okei.
Joten laita boilerplate täällä,
typedef struct solmu, ja solmu. Joo, okei.
Joten mitä kenttiä aiomme haluavat meidän solmussa?
[Opiskelija] Int ja sitten kaksi osoitinta?
>> Int-arvo, kaksi osoitinta? Miten kirjoittaa viitteitä?
[Student] Struct. >> Minun pitäisi Lähennä Joo, niin struct solmu * vasemmalle,
ja struct solmu * oikealle.
Ja muistakaa keskustelua viime kerran,
että tämä ei ole mitään järkeä, tämä ei ole mitään järkeä,
Tässä ei ole mitään järkeä.
Tarvitset kaiken siellä voidakseen määritellä tämän rekursiivinen struct.
Okei, niin se mitä meidän puu tulee näyttämään.
Jos emme trinary puu, sitten solmu voisi näyttää B1, B2, struct solmu * b3,
missä b on sivuliike - itse olen enemmän kuullut vasemmalle, keskelle, oikealle, mutta mitä.
Me vain välitä binary, joten oikea, vasen.
"Nyt julistaa maailmanlaajuinen solmu * muuttuja puun juurelle."
Eli emme aio tehdä sitä.
Jotta asiat hieman vaikeampaa ja enemmän yleistynyt,
meillä ei ole maailmanlaajuinen solmu muuttuja.
Sen sijaan pääasiassa me julistaa kaikki solmun asioita,
ja se tarkoittaa, että alla, kun aloitamme käynnissä
meidän on toimintomoduuleja ja meidän insert toiminto,
sijaan meidän on toimintomoduuleja vain käyttämällä tätä maailmanlaajuista solmuun muuttuja,
aiomme olla se ottaa niin väitteen puu että haluamme käsitellä.
Ottavat globaalin muuttujan piti helpottaa asioita.
Aiomme tehdä asioita vaikeampaa.
Nyt kestää minuutin tai niin vain tehdä tällaista asiaa,
jossa sisällä tärkeimmistä haluat luoda tätä puuta, ja se on kaikki mitä haluat tehdä.
Kokeile ja rakentaa tämän puun teidän päätehtävä.
>> Okei. Joten sinun ei edes tarvitse olla rakennettu puusta koko tie vielä.
Mutta kellään jotain voisin vetää ylös
osoittaa, miten joku voisi alkaa rakentaa sellainen puu?
[Opiskelijan] Joku paukutti, yrittää saada pois.
[Bowden] Jokainen mukava niiden puukonstruktion?
[Student] Toki. Se ei ole tehnyt. >> Se on hieno. Voimme vain lopettaa -
oh, voit tallentaa sen? Hurraa.
Joten tässä olemme - Voi, olen hieman leikattu.
Olenko zoomataan?
Lähennä selaamalla ulos. >> Minulla on kysymys. >> Niin?
[Opiskelija] Kun määrität struct, ovat asioita, kuten alustettu mitään?
[Bowden] No >> Okei. Joten sinun olisi alustamaan -
[Bowden] No Kun määritellä, tai kun julistaa struct,
se ei ole alustettu oletuksena, se on aivan kuin jos julistaa int.
Se on aivan sama asia. Se on kuin jokainen sen yksittäisten kenttien
voi olla roska arvo sitä. >> Ja on mahdollista määritellä - tai julistaa struct
siten, että se tekee ne alustaa?
[Bowden] Kyllä. Joten pikakuvake alustus syntaksi
tulee näyttämään -
On kaksi tapaa voimme tehdä tämän. Mielestäni meidän pitäisi laatia sen
varmista clang tekee myös tämän.
Argumenttien järjestystä, joka tulee struct,
laitat sillä argumenttien järjestystä sisällä näitä aaltosulkeita.
Joten jos haluat alustaa sen 9 ja vasemmalle on nolla, ja sitten oikealle olla null,
olisi 9, null, null.
Vaihtoehtona on, ja toimittaja ei pidä tätä syntaksia,
ja se luulee haluan uuden lohkon,
mutta vaihtoehtona on jotain -
täällä, laitan sen uuden linjan.
Voit erikseen sanoa, unohdan tarkka syntaksi.
Joten voit nimenomaan käsitellä heitä nimeltä, ja sanoa,
. C tai. Arvo = 9,. Vasen = NULL.
Olen arvaamaan näitä on pilkkuja.
. Oikea = NULL, joten tällä tavalla ei
todella tarvitsee tietää järjestystä struct,
ja kun luet tätä, se on paljon selkeämpi
mitä arvoa on parhaillaan alustetaan.
>> Tämä sattuu olemaan yksi niistä asioista, jotka -
niin, että suurin osa, C + + on pääjoukko C.
Voit ottaa C-koodia, siirrä se yli C + +, ja se pitäisi laatia.
Tämä on yksi niistä asioista, että C + + ei tue, joten ihmiset eivät yleensä tee sitä.
En tiedä, jos se on ainoa syy, ihmiset eivät yleensä tee sitä,
mutta jos minun piti käyttää sitä tarpeen työskennellä C + +, joten en voinut käyttää tätä.
Toinen esimerkki jotain, joka ei toimi C + + on
miten malloc palauttaa "void *," teknisesti,
mutta voisitte sanoa char * x = malloc tahansa,
ja se automaattisesti valetaan char *.
Tämä automaattinen valettu ei tapahdu C + +.
Se ei kerätä, ja sinulla olisi nimenomaisesti täytyy sanoa
char *, malloc, mitä, heittää se char *.
Ei ole monia asioita, jotka C ja C + + eri mieltä,
mutta nämä ovat kaksi.
Joten me menemme tällä syntaksilla.
Mutta vaikka emme mene että syntaksi,
mikä on - voi olla vikana?
[Opiskelija] En tarvitse dereference sitä? >> Joo.
Muista, että nuoli on implisiittinen dereference,
ja niin kun me vain tekemisissä struct,
haluamme käyttää. saada aikaa kentän sisällä struct.
Ja ainoa kerta käytämme nuoli on, kun me haluamme tehdä -
hyvin, nuoli vastaa -
niinhän se olisi tarkoittanut, jos käytin nuolta.
Kaikki nuoli tarkoittaa on, dereference tätä, nyt olen struct, ja saan kenttään.
Joko saat kentän suoraan tai dereference ja saada kenttä -
Kai tämä olisi arvoa.
Mutta tässä olen tekemisissä vain struct, ei osoitin struct,
joten en voi käyttää nuoli.
Mutta tällaista asiaa voimme tehdä kaikki solmut.
Voi luoja.
Tämä on 6, 7, ja 3.
Sitten voimme perustaa sivuliikkeitä meidän puu, meillä voi olla 7 -
Meillä voi olla, sen vasemmalle pitäisi kohta 3.
Joten miten me sen teemme?
[Opiskelijat, käsittämätön] >> Joo. Osoite node3,
ja jos sinulla ei ole osoitetta, se vain ei kerätä.
Mutta muistakaa, että nämä ovat osoittimia seuraavaan solmut.
Oikeus tulisi osoittaa 9,
ja 3 olisi piste oikeus 6.
Mielestäni tämä on kaikki asetettu. Kommentteja tai kysymyksiä?
[Student, käsittämätön] root tulee olemaan 7.
Voimme vain sanoa solmu * ptr =
tai root, = & node7.
>> Meidän kannalta, aiomme olla tekemisissä insert,
joten olemme menossa halua kirjoittaa funktion lisätä tähän binaaripuun
ja insertti on väistämättä menossa soittaa malloc luoda uusi solmu tämän puun.
Joten asiat menevät sotkuinen, että jotkut solmut
Tällä hetkellä pinoon
ja muut solmut ovat menossa päätyä kasaan kun lisäämme niitä.
Tämä on täysin pätevä, mutta ainoa syy
pystymme tekemään tämän pinoon
koska se on niin keinotekoinen esimerkki siitä, että tiedämme
puu on tarkoitus olla rakennettu 7, 3, 6, 9.
Jos meillä ei ole tätä, niin meillä ei tarvitsisi malloc ensimmäinen paikka.
Kuten näemme hieman myöhemmin, meidän pitäisi malloc'ing.
Juuri nyt se on täysin järkevää laittaa pinon
mutta katsotaanpa muuttaa tämän malloc toteuttamiseen.
Joten jokainen nyt olemaan jotain
solmu * node9 = malloc (sizeof (solmu)).
Ja nyt me aiomme pitää teemme tarkastus.
jos (node9 == NULL) - En halua, että -
palaa 1, ja sitten voimme tehdä node9-> koska nyt on osoitin,
value = 6, node9-> vasen = NULL,
node9-> oikea = NULL,
ja aiomme pitää tehdä, että jokaiselle näistä solmuista.
Joten sen sijaan, katsotaanpa laita se sisällä erillisenä toimintona.
Sanotaan se solmu * build_node,
ja tämä on jossain määrin samanlainen kuin API me säätää Huffman-koodausta.
Annamme sinulle alustajan toiminnot puu
ja Deconstructor "toiminnot" niille puita ja sama metsiä.
>> Joten tässä me aiomme olla alustajan toiminto
vain rakentaa solmu meille.
Ja se tulee näyttämään melko paljon juuri näin.
Ja minä vielä olemaan laiska eikä muuttaa muuttujan nimi,
vaikka tosin node9 ole mitään järkeä enää.
Voi kai node9 arvo ei olisi ollut 6.
Nyt voimme palata node9.
Ja täällä pitäisi palata null.
Jokainen samaa mieltä build-solmun funktio?
Joten nyt voimme vain soittaa, että rakentaa mitään solmu tiettyyn arvoon ja null viitteitä.
Nyt voimme kutsua, että voimme tehdä solmu * node9 = build_node (9).
Ja tehkäämme. . .
6, 3, 7, 6, 3, 7.
Ja nyt me haluamme perustaa saman osoittimia,
paitsi nyt kaikki on jo suhteen osoittimia
joten ei enää tarvitse osoite.
Okei. Joten mikä on viimeinen asia, jonka haluan tehdä?
On virhe tarkkailun että en ole tekemässä.
Mitä rakentaa solmu paluuta?
[Student, käsittämätön] >> Joo. Jos malloc epäonnistui, se tulee palauttaa null.
Joten aion laiskasti laittaa sen tänne sen sijaan tehdä edellytys jokaiselle.
Jos (node9 == NULL tai - vielä yksinkertaisempi,
tämä vastaa vain, jos ei ole node9.
Joten jos ei node9, tai ei node6, tai ei node3, tai ei node7, palaa 1.
Ehkä meidän pitäisi tulostaa malloc epäonnistui, tai jotain.
[Student] Onko vääriä yhtä null samoin?
[Bowden] Kaikki nolla on epätosi.
Joten null on nolla.
Nolla on nolla. False on nolla.
Jokainen - melko paljon vain 2 nolla-arvot ovat nolla ja nolla,
väärä on aivan hash määritelty nollaksi.
Tämä pätee myös, jos emme julistaa globaali muuttuja.
Jos meillä oli solmu * root täällä,
Sitten - Kiva juttu globaaleja muuttujia on, että ne ovat aina alkuarvo.
Se ei ole totta toimintoja, kuinka sisällä täällä,
jos meillä on, kuten, solmu * tai solmu x.
Meillä ei ole aavistustakaan, mitä x.value, x.whatever,
tai voisimme tulostaa ne ja ne voivat olla mielivaltaisia.
Se ei ole totta globaaleja muuttujia.
Joten solmu root tai solmu x.
Oletusarvoisesti kaikki, globaali, ellei nimenomaisesti alustetaan jotain arvoa,
arvo on nolla, koska sen arvo.
Joten tässä, solmu * root, emme erikseen alustaa sitä mihinkään,
joten sen oletusarvo on nolla, joka on nolla-arvo osoittimia.
Oletusarvo x on menossa tarkoita, että x.value on nolla,
x.left on nolla, ja x.right on nolla.
Niin koska se on struct, kaikki kentät struct on nolla-arvot.
Meidän ei tarvitse käyttää sitä tässä, vaikka.
[Student] tietueet ovat erilaisia ​​kuin muut muuttujat, ja muut muuttujat ovat
roska-arvot; nämä ovat nollia?
[Bowden] Muut arvot myös. Joten x, x on nolla.
Jos se on maailmanlaajuisesti soveltamisalaa, sillä on alkuarvo. >> Okei.
[Bowden] Joko alkuarvo annoit sen tai nolla.
Mielestäni huolehtii kaiken tämän.
>> Okei. Joten seuraava osa kysymyksessä tiedustellaan,
"Nyt haluamme kirjoittaa toiminto nimeltään sisältää
jossa prototyyppi bool sisältää int arvo. "
Emme aio tehdä bool sisältää int arvo.
Meidän prototyyppi tulee näyttämään
bool sisältää (int arvo.
Ja sitten me myös menossa ohi se puu
että se olisi tarkistaa, jos se on, että arvo.
Joten solmu * puu). Okei.
Ja sitten voimme kutsua sitä jotain,
Ehkä me haluamme printf tai jotain.
Sisältää 6, meidän root.
Tämän pitäisi palauttaa yhden tai totta,
taas sisältää 5 root pitäisi palauttaa false.
Joten ota toinen toteuttaa tämän.
Voit tehdä sen joko iteratiivisesti tai rekursiivisesti.
Kiva juttu miten olemme asettaa asioita on, että
se on omiaan meidän rekursiivinen ratkaisu paljon helpompaa
kuin globaali muuttujan tavalla teki.
Koska jos meillä vain on sisältää int arvo, niin meillä ei ole mitään mahdollisuuksia recursing alas alipuut.
Meidän täytyisi olla erillinen auttaja toiminnon recurses alas alipuut meille.
Mutta koska olemme muuttaneet sen ottaa puuta argumentti,
jotka sen olisi pitänyt aina ollut ensimmäinen paikka,
Nyt voimme recurse helpommin.
Joten iteratiivinen tai rekursiivinen, menemme yli niin,
mutta näemme, että rekursiivinen päätyy melko helppoa.
Okei. Onko kellään jotain voimme työskennellä?
>> [Opiskelija] Minulla iteratiivinen ratkaisu. >> Selvä, iteratiivinen.
Okei, tämä näyttää hyvältä.
Joten, haluatko kävellä meidän läpi?
[Student] Toki. Niin otan temp muuttuja saada ensimmäinen solmu puun.
Ja sitten minä vain viedä läpi vaikka lämpötila ei ole sama null,
joten kun oli vielä puussa, luulisin.
Ja jos arvo on yhtä suuri kuin arvo, joka lämpötila on osoittaa,
niin se palauttaa tämän arvon.
Muuten se tarkistaa, jos se on oikealla puolella tai vasemmalla puolella.
Jos joskus saat tilanteeseen, jossa ei ole enää puu,
Sitten se palaa - se poistuu silmukasta ja palauttaa false.
[Bowden] Okei. Niin että tuntuu hyvältä.
Kellään mitään kommentteja mistään?
Minulla ei ole oikeellisuudesta kommentteja ollenkaan.
Ainoa mitä voimme tehdä, on tämä kaveri.
Voi, se on menossa hieman pitkähkö.
Minä korjata se ylös. Okei.
>> Jokaisen pitäisi muistaa kuinka ternäärisen toimii.
On varmasti ollut tietokilpailuja aikaisemmin
jotka antavat sinulle funktio ternäärinen toimija,
ja sanoa, kääntää tätä, tehdä jotain, joka ei käytä ternäärisen.
Joten tämä on hyvin yleinen tapaus, luulisin käyttää tertiaarisia
jos jos ehdosta asettaa muuttujan johonkin,
muuten asettaa saman muuttujan jotain muuta.
Se on jotain, että hyvin usein voidaan muuntaa tällainen asia
jos asetettu, että muuttuja tähän - tai no, on tämä totta? Sitten tämä, muuten tämä.
[Opiskelija] Ensimmäinen on, jos totta, eikö?
[Bowden] Joo. Tapa Luen aina se, temp vastaa arvo on suurempi kuin lämpötila-arvo,
Sitten tämä, muuten tämä. Se kysyy kysymyksen.
Onko se suurempi? Tee sitten ensimmäinen asia. Else tehdä toinen asia.
Olen melkein aina - paksusuolen, juuri - päähäni, luin kuin muualla.
>> Onko kellään rekursiivinen ratkaisu?
Okei. Tämän me aiomme - se voisi olla jo hyvä,
mutta me aiomme tehdä sen vielä paremmin.
Tämä on melko täsmälleen sama ajatus.
Se on vain, no, haluatko selittää?
[Student] Toki. Joten me varmista, että puu ei ole null ensin,
sillä jos puu on nolla niin se tulee palauttaa false, koska emme ole löytäneet sitä.
Ja jos siellä on vielä puussa, menemme - ensin tarkistaa, jos arvo on nykyinen solmu.
Return true jos on, ja jos ei me recurse vasemmalle tai oikealle.
Kuulostaako sopiva? >> Mm-hmm. (Sopimus)
Niin huomata, että tämä on lähes - rakenteellisesti hyvin samanlainen kuin iteratiivinen ratkaisu.
Se on vain, että sen sijaan recursing, meillä oli taas silmukka.
Ja pohja tässä tapauksessa, jossa puu ei ole yhtä null
oli ehto, jonka me puhkesi kun silmukka.
Ne ovat hyvin samankaltaisia. Mutta aiomme ottaa tämän askeleen pidemmälle.
Nyt teemme saman täällä.
Ilmoitus olemme palaamassa samaa molemmissa linjat,
paitsi yksi argumentti on erilainen.
Joten me aiomme tehdä, että tulee kolmen komponentin.
Löin vaihtoehto jotain, ja se teki symboli. Okei.
Joten aiomme palata sisältää se.
Tämä alkaa olla useita rivejä, hyvin, zoomataan se on.
Yleensä, kuten tyylillinen juttu, en usko moni
laittaa välilyönti jälkeen nuoli, mutta luulen jos olet johdonmukainen, se on hienoa.
Jos arvo on pienempi kuin puu arvo, haluamme recurse puiden vasemmalle,
muuta haluamme recurse puiden oikeassa.
Niin että oli vaihe yksi tehdä tämän näyttämään pienemmältä.
Vaihe kaksi tehdä tämän näyttämään pienemmältä -
voimme erottaa tämän useita rivejä.
Okei. Vaihe kaksi tehdä se näyttää pienempi on täällä,
joten paluu arvo vastaa puun arvo tai sisältää mitä tahansa.
>> Tämä on tärkeä asia.
En ole varma, onko hän sanoi nimenomaan luokassa,
mutta sitä kutsutaan oikosulku arviointi.
Ideana on arvo == puu arvoa.
Jos tämä on totta, niin tämä on totta, ja me haluamme "tai" että mitä on täällä.
Joten edes ajatellut mitä on täällä,
Mikä on koko lauseke aio palata?
[Student] True? >> Joo, koska totta mitään,
or'd - tai totta or'd mitään on välttämättä totta.
Niin pian näemme paluuarvo = puu-arvo,
olemme juuri menossa return true.
Ei edes aio recurse sisältää lisäksi ruodussa.
Voimme ottaa tämän askeleen pidemmälle.
Return puu ei vastaa nolla ja kaikki tämä.
Se teki yhden rivin funktio.
Tämä on myös esimerkki oikosulun arviointi.
Mutta nyt se on sama ajatus -
sijasta - joten jos puu ei ole yhtä null - tai no,
Jos puu ei yhtä suuri kuin nolla, joka on huono asia,
jos puu vastaa null, niin ensimmäinen edellytys tulee olemaan väärä.
Niin vääriä anded mitään tulee olemaan mitä?
[Student] False. >> Joo. Tämä on toinen puoli oikosulun arviointi,
jos jos puu ei yhtä null, niin emme aio edes mennä -
tai jos puu ei yhtä null, niin emme aio tehdä arvo == puun arvoa.
Olemme juuri menossa heti palauttaa false.
Mikä on tärkeää, koska jos se ei oikosulun arvioi,
Sitten jos puu ei yhtä null, tämä toinen edellytys on menossa segmenteille vika,
koska puu-> arvo dereferencing null.
Joten se siitä. Voi tehdä tätä - siirtää kerran yli.
Tämä on hyvin yleistä myös, ei tee tätä linjaa tässä,
mutta se on yhteinen asia olosuhteissa, ehkä ei täällä,
mutta jos (puu! = NULL, ja puu-> arvo == arvo), tehdä mitä tahansa.
Tämä on hyvin yleinen sairaus, jossa sen sijaan,
murtaa kahteen jossittelua, missä haluan, on puu null?
Okei, se ei ole nolla, joten nyt on puu-arvo arvoon? Tee tämä.
Sen sijaan, tämä ehto, tämä ei koskaan segmentti vian
koska se puhkeaa, jos tämä sattuu olemaan null.
No, kai jos puu on täysin virheellinen osoittimen, se voi silti segmentti vika,
mutta se ei voi seg vika jos puu on tyhjä.
Jos se olisi null, se puhkeaa ennen kuin koskaan dereferenced osoitin ensimmäinen paikka.
[Student] Onko tämä sanottu laiska arviointi?
>> [Bowden] Lazy arviointi on erillinen asia.
Laiska arviointi on enemmän kuin pyydät arvon,
pyydät laskea arvoa, eräänlainen, mutta et tarvitse sitä heti.
Joten kunnes todella tarvitset sitä, se ei ole arvioitu.
Tämä ei ole aivan sama asia, mutta Huffman PSET,
se sanoo, että me "laiskasti" kirjoittavat.
Syy teemme joka johtuu olemme todella puskurointia kirjoitus -
emme halua kirjoittaa yksittäisiä bittiä kerrallaan,
tai yksittäisiä tavuja kerralla, me vaan haluamme saada palan tavua.
Sitten kun meillä on kimpale tavua, niin me kirjoittaa sitä.
Vaikka et pyydä sitä kirjoittaa - ja fwrite ja fread tehdä sama sellainen asia.
He puskuri teidän lukee ja kirjoittaa.
Vaikka et pyydä sitä kirjoittaa heti, se luultavasti ei.
Ja voit olla varma, että asiat ovat menossa kirjoitetaan
kunnes soitat hfclose tai mikä se on,
joka sitten kertoo, okei, olen päätän tiedosto,
se tarkoittaa, että olisin parempi kirjoittaa kaikkea en ole kirjoittanut vielä.
Se ei tarvitse kirjoittaa kaiken pois
kunnes olet lopettamista, ja sitten se tarvitsee.
Joten tuon juuri laiska - se odottaa, kunnes se on tapahtua.
Tämä - ottaa 51 ja voit mennä sen tarkemmin,
koska OCaml ja kaiken 51, kaikki on rekursio.
Ei ole iteratiivinen ratkaisuja, periaatteessa.
Kaikki on rekursio, ja laiska arviointi
tulee olemaan tärkeä paljon olosuhteiden
missä, jos et laiskasti arvioi, että merkitsisi -
Esimerkki on virtoja, jotka ovat äärettömän pitkä.
Teoriassa voit ajatella luonnon numerot virta 1-2-3-4-5-6-7,
Joten laiskasti arvioitava asiat ovat kunnossa.
Jos sanon haluan kymmenes numero, niin voin arvioida jopa kymmenes numero.
Jos haluan sadas numero, niin voin arvioida jopa sadasosaan numero.
Ilman laiska arviointi, niin se tulee yrittää arvioida kaikki numerot heti.
Olet arvioidaan äärettömän monta lukua, ja se ei vain ole mahdollista.
Joten on olemassa paljon tilanteita, joissa laiska arviointi
On vain tärkeää saada asiat toimimaan.
>> Nyt haluamme kirjoittaa insertti jossa insertti tulee olemaan
Samoin muuttaa sen määritelmä.
Joten nyt on bool insert (int arvo).
Aiomme vaihtaa sen BOOL insert (int arvo, solmu * puu).
Olemme itse asiassa menossa muuttaa sitä jälleen hieman, näemme miksi.
Ja lähdetään build_node, vain pahus se,
Edellä aseta joten meidän ei tarvitse kirjoittaa funktion prototyyppi.
Joka on vihje, että aiot käyttää build_node vuonna insert.
Okei. Ota minuutti siitä.
Uskon tallentanut tarkistamista, jos haluat vetää siitä, että
tai ainakin tein nyt.
Halusin hieman taukoa ajatella logiikkaa insertin,
jos et voi ajatella sitä.
Periaatteessa, et vain koskaan lisäämällä klo lehtiä.
Kuten, jos asetan 1, niin olen väistämättä olemaan laittamalla 1 -
Muutan mustaksi - Minä oltava lisäämällä 1 täällä.
Tai jos asetan 4, haluan olla työntämällä 4 tänne.
Joten ei ole väliä mitä teet, olet menossa on työntämällä klo lehtiä.
Kaikki mitä sinun tarvitsee tehdä on toistaa alas puusta kunnes saat solmuun
että pitäisi olla solmun vanhemman uuden solmun vanhempi,
ja sitten muuttaa sen vasemmalle tai oikealle osoitin, riippuen siitä, onko
se on suurempi tai pienempi kuin nykyinen solmu.
Vaihda että osoitin osoittamaan uuteen solmuun.
Joten toistaa alas puusta, tee lehtiä pisteen uuteen solmuun.
Myös miettiä, miksi se kieltää tällaiseen tilanteeseen ennen,
jossa rakensin binääripuu, jossa se oli oikein
jos vain katseli yksi solmu,
mutta 9 oli vasemmalla 7 jos iteroida alas koko matkan.
Niin, että on mahdotonta tässä tilanteessa, koska -
ajattelevat asetat 9 tai jotain, aivan ensimmäinen solmu,
Aion nähdä 7 ja olen juuri menossa oikealle.
Joten ei ole väliä mitä teen, jos olen työntämällä menemällä lehti,
ja lehtien käyttäen sopivaa algoritmia,
se tulee olemaan minulle mahdotonta lisätä 9 vasemmalle 7
sillä heti kun osuin 7 aion mennä oikealle.
Onko kellään jotain aloittaa?
[Opiskelija] teen. >> Toki.
[Student, käsittämättömällä]
[Other opiskelija, käsittämättömällä]
[Bowden] Se arvostaa. Okei. Haluatko selittää?
>> [Student] Koska me tiedämme, että me asetat
uusien solmujen lopussa puun
Olen viedä läpi puun iteratiivisesti
kunnes sain solmun, joka osoitti null.
Ja sitten päätin laittaa sen joko oikealla tai vasemmalla puolella
Käyttämällä tätä oikeutta muuttuja, se kertoi minulle, mihin sitä.
Ja sitten, lähinnä olen juuri tehnyt, että viimeinen -
että temp solmupiste uuteen solmu, että se oli luoda,
joko vasemmalla puolella tai oikealle puolelle, riippuen siitä, mitä arvoa oikean oli.
Lopuksi otan uuden solmun arvon arvoa sen testaus.
[Bowden] Okei, joten näen yksi kysymys.
Tämä on kuin 95% matkalla sinne.
Yksi asia, että näen hyvin, ei kukaan muu näe asiaa?
Mikä on seikka, jonka mukaan ne murtautumaan ulos silmukan?
[Student] Jos lämpötila on nolla? >> Joo. Joten miten eroon silmukka jos lämpötila on nolla.
Mutta mitä teen täällä?
Minä dereference lämpötila, joka on väistämättä null.
Joten toinen asia mitä sinun tarvitsee tehdä ei ole vain seurata, kunnes lämpötila on nolla,
haluat seurata vanhemman aina.
Haluamme myös solmu * vanhempi, kai voimme pitää, että null aluksi.
Tämä tulee olemaan outo käyttäytyminen puun juurelle,
mutta saamme siihen.
Jos arvo on suurempi kuin mitä, niin temp = temp oikeassa.
Mutta ennen kuin teemme, että vanhempi = lämpötila.
Vai vanhemmat aina menossa yhtä temp? Onko näin?
Jos lämpötila ei ole nolla, niin aion liikkua alaspäin, ei väliä mitä,
solmuun, jonka lämpötila on vanhempi.
Joten vanhemman tulee olemaan temp, ja sitten siirtyä lämpötila alas.
Nyt lämpötila on nolla, mutta vanhemman viittaa vanhemman asia on null.
Joten täällä, en halua asettaa oikealle vastaa 1.
Joten muutin oikealle, joten jos oikea = 1,
ja kai myös haluavat tehdä -
Jos liikut vasemmalle, jonka haluat asettaa oikealle 0..
Tai muuten jos joskus siirtyä oikealle.
Joten oikea = 0. Jos oikea = 1,
Nyt haluamme tehdä vanhemman oikeus osoitin newnode,
muuta haluamme tehdä vanhemman vasemmalle osoittimen newnode.
Kysymyksiä tästä?
Okei. Joten tämä on tapamme - no, oikeastaan, eikä näin,
me puoli odotetaan voit käyttää build_node.
Ja sitten jos newnode vastaa null, palauttaa false.
Se siitä. Nyt, tämä on mitä odotimme sinua tekemään.
>> Tämä on mitä henkilökunta ratkaisut tekevät.
Olen eri mieltä kuin "oikea" tapa edetä siitä
mutta tämä on täysin hieno, ja se toimii.
Yksi asia, joka on hieman outoa nyt on
jos puu alkaa kuin null, me kulkea null puuhun.
Kai se riippuu siitä miten määrittelet käyttäytymistä ohimennen null puuhun.
Luulisin, että jos pyörryt in null puu,
sitten asettamalla arvon osaksi null puuhun
pitäisi vain palauttaa puu, jossa ainoa arvo on se yksi solmu.
Ihmiset samaa mieltä? Voisit, jos halusi,
Jos ohitat in null puu
ja haluat lisätä arvoa siihen, palauttaa false.
Se on jopa voit määrittää, että.
Voit tehdä ensimmäinen asia sanoin ja sitten -
hyvin, olet menossa on vaikeuksia tehdä niin, koska
Olisi helpompaa, jos meillä olisi maailmanlaajuinen osoitin asia,
mutta emme, joten jos puu on tyhjä, ei ole mitään emme voi tehdä asialle.
Voimme vain palauttaa false.
Joten aion vaihtaa insertin.
Olemme teknisesti voisi juuri muuttaa tätä täällä,
miten se iteroimalla läpi asioita,
mutta aion vaihtaa insertin ottaa solmuun ** puu.
Double viitteitä.
Mitä tämä tarkoittaa?
Sen sijaan käsitellä osoittimia solmuja,
asia aion olla manipuloimalla tämä osoitin.
Aion olla manipuloida tätä osoitinta.
Aion olla manipuloimalla osoittimia suoraan.
Tämä on järkevää, koska ajattelevat alas -
No, nyt tämä viittaa null.
Mitä haluan tehdä on manipuloida tämä osoitin osoittamaan ole null.
Haluan sen osoittamaan minun uusi solmu.
Jos minä vain seurata osoittimia minun osoittimia,
niin minun ei tarvitse seurata vanhemman osoittimen.
Voin vain seurata, onko osoitin osoittaa null,
ja jos osoitin osoittaa null,
vaihda se osoittamaan solmuun haluan.
Ja voin vaihtaa sen koska minulla on osoittimen osoitin.
Katsotaanpa tätä nyt.
Voit itse tehdä sen rekursiivisesti melko helposti.
Haluammeko tehdä niin?
Kyllä, me teemme.
>> Katsotaanpa sitä rekursiivisesti.
Ensinnäkin, mitä meidän tukikohta tapauksessa olemaan?
Lähes aina meidän tukikohta tapauksessa, mutta todellisuudessa tämä on tavallaan hankala.
First things first, jos (puu == NULL)
Taidamme juuri menossa palauttaa false.
Tämä poikkeaa teidän puu on null.
Tämä on osoitin pääkäyttäjän osoittimen ollessa null
mikä tarkoittaa, että root osoitin ei ole olemassa.
Joten täällä, jos en
solmu * - Haluan vain käyttämään tätä.
Solmu * root = NULL,
ja sitten aion soittaa insertin tekemällä jotain,
aseta 4 osaksi & root.
Niin & root, jos root on solmu *
Sitten & root tulee olemaan solmu **.
Tämä on voimassa. Tällöin puun, täällä,
puu ei ole tyhjä - tai insert.
Täällä. Puu ei ole nolla, * puu on nolla, mikä on hieno
koska jos * puu on tyhjä, niin voin manipuloida sitä
nyt osoittamaan, mitä haluan sen osoittamaan.
Mutta jos puu on tyhjä, se tarkoittaa, että olen vain tuli tänne ja sanoi null.
Tämä ei ole mitään järkeä. En voi tehdä mitään sen kanssa.
Jos puu on tyhjä, palauttaa false.
Joten olen periaatteessa jo sanonut, mitä todellinen pohja tapaus.
Ja mitä on se tulee?
[Student, käsittämättömällä]
[Bowden] Kyllä. Joten jos (* puu == NULL).
Tämä koskee tapausta tänne
jos jos minun punainen osoitin on osoitin olen keskittynyt,
niin kuin olen keskittynyt tähän osoitin, nyt olen keskittynyt tähän osoitin.
Nyt olen keskittynyt tähän osoitin.
Joten jos minun punainen osoitin, joka on minun solmu **
on aina - jos *, minun punainen osoitin, on aina nolla,
se tarkoittaa, että olen silloin olen keskittynyt osoitin, joka osoittaa -
tämä on osoitin, joka kuuluu lehtiä.
Haluan muuttaa tätä osoitin osoittamaan minun uusi solmu.
Tule takaisin tänne.
Minun newnode vain on solmu * n = build_node (arvo)
sitten n, jos n = NULL, palaa vääriä.
Else haluamme muuttaa mitä osoitin on tällä hetkellä osoittaa
nyt osoittamaan hiljattain rakennettu solmu.
Voimme todella tehdä sen täällä.
Sijaan sanoa n, sanomme * puu = jos * puu.
Jokainen ymmärtää, että? Että käsittelemällä viitteitä osoittimia,
voimme muuttaa null osoittimet osoittamaan asioita haluamme ne osoittamaan.
Se on meidän perustapaus.
>> Nyt meidän toistumisen tai meidän rekursio,
tulee olemaan hyvin samanlainen kaikille muille rekursioiden olemme tehneet.
Aiomme haluat lisätä arvoa,
ja nyt aion käyttää ternäärinen uudestaan, mutta mitä tilaamme olemaan?
Mitä me etsimme päättää haluamme mennä vasemmalle tai oikealle?
Tehdään se erillisissä vaiheissa.
Jos (arvo <) mitä?
[Opiskelija] puun arvo?
[Bowden] Muista siis, että olen tällä hetkellä -
[Opiskelijat, käsittämättömällä]
[Bowden] Joo, niin täällä sanotaan, että tämä vihreä nuoli
on esimerkki siitä, mitä puu tällä hetkellä on, on osoitin tämän osoitin.
Niin se tarkoittaa, että olen osoittimen osoittimen 3.
Dereference kahdesti kuulosti hyvältä.
Mitä teen - miten voin tehdä sen?
[Student] dereference kerran, ja tee sitten nuolta niin?
[Bowden] So (* puu) on dereference kerran -> arvo
aikoo antaa minulle arvoa solmun että olen epäsuorasti osoittaa.
Joten voin myös kirjoittaa sen ** tree.value jos haluat, että.
Joko toimii.
Jos näin on, niin haluan soittaa lisätä arvolla.
Ja mitä minun päivitetään solmu ** olemaan?
Haluan mennä vasemmalle, joten ** tree.left tulee olemaan minun vasemmalle.
Ja haluan osoitinta että asia
niin että jos vasemmalla päätyy on nollaosoittimen,
Voin muuttaa sen osoittamaan minun uusi solmu.
>> Ja toisessa tapauksessa voi olla hyvin samanlainen.
Tehdään itse tehdä, että minun ternäärisen nyt.
Aseta arvo, jos arvo <(** puu). Arvo.
Sitten haluamme päivittää ** vasemmalle,
muuta haluamme päivittää ** oikealle.
[Opiskelija] Onko jotka saavat osoitin osoitin?
[Bowden] Muista, että - ** tree.right on solmu tähti.
[Student, käsittämätön] >> Joo.
** Tree.right on näin osoitin tai jotain.
Joten ottamalla osoitin, että se antaa minulle mitä haluan
ja osoitin että kaveri.
[Student] Voisimmeko mennä uudestaan ​​miksi käytämme kaksi osoitinta?
[Bowden] Joo. Joten - no, voit, ja että ratkaisu ennen
oli tapa tehdä se tekemättä kaksi osoitinta.
Sinun täytyy pystyä ymmärtämään kahdella osoittimia,
ja tämä on puhtaampaa ratkaisu.
Huomaa myös, että mitä tapahtuu jos puu -
Mitä tapahtuu, jos root oli null? Mitä tapahtuu, jos en tee tässä tapauksessa täällä?
Joten solmu * root = NULL, aseta 4 osaksi & root.
Mikä on root olemaan tämän jälkeen?
[Student, käsittämätön] >> Joo.
Root-arvo tulee olemaan 4.
Root vasemmalle tulee olemaan null, root oikeus tulee olemaan null.
Siinä tapauksessa emme ohittaa root osoitteen,
emme voi muuttaa root.
Tapauksessa, jossa puun - missä root oli null,
meillä oli vain palauttaa false. Ei ole mitään mitä voisimme tehdä.
Emme voi lisätä solmun tyhjään puuhun.
Mutta nyt voimme, voimme vain tehdä tyhjä puu tulee yhden solmun Tree.
Joka on yleensä odotetulla tavalla, että sen pitäisi toimia.
>> Lisäksi tämä on huomattavasti lyhyempi kuin
myös pitää kirjaa vanhemman, ja niin te iteroida alas koko matkan.
Nyt minulla on vanhempieni, ja minulla on vain minun vanhemman oikeus osoitin tahansa.
Sen sijaan, jos teimme tämän iteratiivisesti, se olisi sama idea kun silmukka.
Mutta sen sijaan, käsitellä vanhempieni osoitin,
vaan minun nykyinen osoitin olisi asia
että olen suoraan muuttaa osoittamaan minun uusi solmu.
Minulla ei ole käsitellä onko se osoittaa vasemmalle.
Minulla ei ole käsitellä onko se osoittaa oikealle.
Se on vain mitä tämä osoitin on, aion asettaa sen osoittamaan minun uusi solmu.
Jokainen ymmärtää, miten se toimii?
Jos ei, miksi haluamme tehdä näin,
mutta ainakin tämä toimii ratkaisu?
[Student] Mistä me palata totta?
[Bowden] Se on luultavasti täällä.
Jos me oikein aseta se, return true.
Else, tänne menemme halua palata mitä insertin tuottoa.
>> Ja mitä erikoista tässä rekursiivinen funktio?
Se hännän rekursiivinen, niin kauan kuin me koota joidenkin optimointi,
se tunnistaa, että ja et koskaan saa pinon ylivuoto tästä,
vaikka meidän puu korkeus on 10000 tai 10000000.
[Student, käsittämättömällä]
[Bowden] Minusta se sitä Dash - tai mitä optimointi tasolla
tarvitaan hännän rekursion on tunnustettava.
Mielestäni tunnustetaan - GCC ja clang
myös erilaisia ​​merkityksiä niiden optimointi tasoille.
Haluan sanoa se DashO 2, että se tunnistaa häntä rekursio.
Mutta me - voit rakentaa kuin Fibonocci esimerkiksi tai jotain.
Se ei ole helppo testata tätä, koska se on vaikea rakentaa
binääripuu, joka on niin suuri.
Mutta joo, mielestäni se on DashO 2, että
Jos käännät kanssa DashO 2, se etsii häntä rekursio
ja optimoida se ulos.
Mennään takaisin - lisätä kirjaimellisesti viimeinen asia se tarvitsee.
Mennään takaisin insertin tänne
minne olemme menossa tekemään saman ajatuksen.
Se tulee vielä puute, ettei se pysty täysin käsittelemään
kun juuri itse on nolla, tai viimeisen merkinnän on nolla,
mutta sen sijaan käsitellä vanhemman osoitin,
Katsotaanpa soveltaa samaa logiikkaa pitää osoittimia osoittimia.
Jos täällä pidämme solmu ** nyk.,
ja meidän ei tarvitse seurata oikean enää,
mutta solmu ** nyk. = & puu.
Ja nyt meidän while-silmukka tulee olemaan taas * nyk. ei ole sama null.
Ei tarvitse seurata vanhempien enää.
Ei tarvitse seurata vasemmalle ja oikealle.
Ja minä kutsun sitä temp, koska olemme jo käytössä temp.
Okei. Joten jos (arvo> * temp),
Sitten & (* temp) -> oikea
muu temp = & (* temp) -> vasemmalle.
Ja nyt, tässä vaiheessa, tämän jälkeen, kun silmukka,
Olen vain tehdä tämän, koska ehkä se on helpompi ajatella iteratiivisesti kuin rekursiivisesti,
mutta tämän jälkeen kun silmukka,
* Temp on osoitin haluamme muuttaa.
>> Ennen meillä oli vanhempi, ja halusimme muuttaa joko vanhemman vasemmalle tai vanhempi oikealle,
mutta jos haluamme muuttaa vanhemman oikealle,
sitten * temp on vanhempi oikeassa, ja voimme muuttaa sen suoraan.
Joten täällä, voimme tehdä * temp = newnode, ja se on siinä.
Joten ilmoitus, kaikki teimme tällä oli ottaa pois riviä koodia.
Jotta seurata vanhemman kaikessa on ylimääräistä vaivaa.
Täällä, jos me vain seurata osoitin osoitin,
ja vaikka halusimme päästä eroon kaikista näistä aaltosulkeita nyt,
jotta se näyttää lyhyempi.
Tämä on nyt täsmälleen sama ratkaisu,
mutta vähemmän riviä koodia.
Kun aloitat tunnustaa tätä pätevä ratkaisu,
se on myös helpompi syynä noin kuin esimerkiksi, okei,
miksi minulla on tämä lippu int oikeassa?
Mitä se tarkoittaa? Voi, se on osoituksena, että
aina kun menen oikealle, minun täytyy asettaa se,
if menen vasemmalle minun täytyy asettaa sen nollaan.
Täällä minun ei tarvitse syytä siitä, se on vain helpompi ajatella.
Kysymyksiä?
[Student, käsittämätön] >> Joo.
Okei, joten viimeinen bitti -
Luulen yksi nopea ja helppo toiminto voimme tehdä on,
let's - yhdessä, luulisin, yrittää kirjoittaa sisältää funktion
joka ei välitä onko se binäärihakupuu.
Tämä sisältää funktion pitäisi palauttaa true
Jos missä tahansa tämän yleisen binääripuussa on arvo etsimme.
Joten ensin tehdä se rekursiivisesti ja sitten teemme sen iteratiivisesti.
Voimme oikeastaan ​​vain tehdä se yhdessä, sillä tämä tulee olemaan todella lyhyt.
>> Mitä minun perustapaus aiotaan?
[Student, käsittämättömällä]
[Bowden] So if (puu == NULL), mitä sitten?
[Student] palauttaa false.
[Bowden] Else, hyvin, en tarvitse muuta.
Jos oli minun toinen perustapaus.
[Opiskelijan] Tree arvoa? >> Joo.
Joten jos (puu-> arvo == arvo.
Ilmoitus olemme takaisin solmuun *, ei solmu ** t?
Sisältää koskaan tarvitse käyttää solmuun **
koska emme muuttaa osoittimia.
Olemme vain liikkumisesta niitä.
Jos näin tapahtuu, niin me haluamme palata totta.
Else haluamme kulkea lapsille.
Joten emme voi järkeillä siitä kaiken vasemmalla on vähemmän
ja kaiken oikealla on suurempi.
Joten mitä tilaamme olemaan täällä - tai, mitä aiomme tehdä?
[Student, käsittämätön] >> Joo.
Return sisältää (arvo, puu-> vasen)
tai sisältää (arvo, puu-> oikea). Ja siinä se.
Ja huomaa jonkin verran oikosulku arviointi,
jos jos huomaamme arvo vasen puu,
Meidän ei tarvitse katsoa oikean puun.
Tuo koko funktio.
Nyt tehdään se iteratiivisesti,
joka tulee olemaan vähemmän mukavaa.
Otamme tavallista alkua solmun * nyk. = puu.
Vaikka (nyk.! = NULL).
Nopeasti näkemään ongelman.
Jos nyk. - täällä, jos me koskaan eroon tästä,
Sitten olemme lopu asioita katsomaan, niin palauta väärä.
Jos (nyk.-> arvo == arvo), return true.
Joten nyt olemme paikassa -
emme tiedä onko meillä halua mennä vasemmalle tai oikealle.
Joten mielivaltaisesti, mennään vain vasemmalle.
Olen ilmeisesti joutunut ongelman, jossa olen täysin luopunut kaikesta -
Olen aina vain tarkistaa vasemmalle puolelle puun.
En koskaan tarkista mitään, että on oikea lapsi mitään.
Miten korjaan tämän?
[Student] Sinun pitää kirjaa vasemmalle ja oikealle pinoon.
[Bowden] Joo. Joten tehkäämme se
struct lista, solmu * n, ja sitten solmu ** seuraavaksi?
Mielestäni toimii hyvin.
Haluamme mennä yli vasemmalle tai let's - täällä.
Struct lista lista =, se tulee aloittaa
pois tässä struct lista.
* Lista = NULL. Niin, että tulee olemaan meidän linkitetty lista
ja alipuut että olemme ohitetaan.
Aiomme Traverse vasemmalle nyt,
mutta koska me väistämättä täytyy palata oikealle,
Aiomme pitää oikealla puolella sisällä meidän struct lista.
Sitten meillä on new_list tai struct,
struct lista *, new_list = malloc (sizeof (lista)).
Aion jättää virheiden tarkkailun, mutta sinun pitäisi tarkistaa, onko se null.
New_list solmu se tulee osoittamaan -
oh, siksi halusin sen tänne. Se tulee osoittamaan toiseen struct lista.
Se, miten linkitettyjä listoja työtä.
Tämä on sama kuin int linkitetty lista
paitsi me vain korvaa int solmuun *.
Se on täsmälleen sama.
Niin new_list, arvoa meidän new_list solmun,
tulee olemaan nyk.-> oikeassa.
Arvo meidän new_list-> seuraava tulee olemaan meidän alkuperäisessä luettelossa,
ja sitten me aiomme päivittää luetteloa osoittamaan new_list.
>> Nyt tarvitaan jonkinlainen tapa vetää asioita,
kuten olemme kulkeneet koko vasemman alipuun.
Nyt meidän täytyy vetää tavaraa pois,
kuten nyk. on nolla, emme halua vain palauttaa false.
Haluamme nyt vetää ulkopuolella meidän uusi luettelo.
Kätevä tapa tehdä tämä - hyvin, oikeastaan, siellä on useita tapoja tehdä tämä.
Kellään ehdotuksia?
Minne minun pitäisi tehdä tämän tai miten minun pitäisi tehdä tämän?
Meillä on vain pari minuuttia, mutta mitään ehdotuksia?
Sen sijaan - yksi tapa, eikä meidän edellytys on samalla,
mitä me nyt katsot ei ole nolla,
sijaan aiomme edelleen mennä kunnes meidän luetteloa on null.
Joten jos lista päätyy null,
Sitten olemme lopu asioita etsiä, etsiä yli.
Mutta se tarkoittaa sitä, että ensimmäinen asia listallamme on juuri menossa olla ensimmäinen solmu.
Aivan ensimmäinen asia on - meidän ei enää tarvitse nähdä sitä.
Joten lista-> n tulee meidän puu.
lista-> seuraava tulee olemaan null.
Ja nyt, kun lista ei ole yhtä null.
Nyk. aikoo vetää jotain listalta.
Joten nyk. tulee yhtä lista-> n.
Ja sitten lista on menossa yhtä lista-> n, tai luettelo-> Seuraava.
Joten jos nyk. arvo on arvo.
Nyt voimme lisätä sekä meidän oikeutemme osoitin ja meidän vasemmalle osoittimen
niin kauan kuin he eivät null.
Täällä, kai meidän olisi pitänyt tehdä, että ensimmäinen paikka.
Jos (nyk.-> oikeassa! = NULL)
Sitten aiomme lisätä, että solmun listalta.
Jos (nyk.-> vasen), tämä on hieman ylimääräistä työtä, mutta se on hieno.
Jos (nyk.-> vasen! = NULL),
ja aiomme lisätä vasemmalle meidän linkitetty lista,
ja että olisi se.
Me toistaa - niin kauan kuin meillä on jotain listalta,
meillä on toinen solmu katsoa.
Joten katsomme, että solmu,
me etukäteen lista on seuraava.
Jos tämä solmu on arvo etsimme, voimme palata totta.
Else laitat molemmat meidän vasemmalle ja oikealle alipuut,
niin kauan kuin he eivät null, meidän lista
niin että me väistämättä mennä niiden yli.
Joten jos ne eivät null,
jos meidän root osoitin osoitti kaksi asiaa,
Sitten aluksi me vedetään jotain niin lista päätyy null.
Ja sitten laitoimme kaksi asiaa takaisin, joten nyt meidän lista on kooltaan 2.
Sitten menemme silmukka takaisin ylös ja olemme juuri menossa vetämään,
Sanotaan, vasen osoitin meidän juurisolmun.
Ja että vain pitää tapahtumassa, me lopulta silmukoiden yli kaiken.
>> Huomaa, että tämä on huomattavasti monimutkaisempi
on rekursiivinen liuokseen.
Ja olen sanonut useita kertoja
että rekursiivinen ratkaisu on yleensä paljon yhteistä iteratiivinen ratkaisu.
Täällä tämä on juuri rekursiivinen ratkaisu tekee.
Ainoa muutos on se, että sen sijaan, että epäsuorasti käyttäen pinon, ohjelma pino,
kuin tapa pitää kirjaa mitä solmujen tarvitset silti käydä,
Nyt sinun on eksplisiittisesti käytettävä linkitetty lista.
Molemmissa tapauksissa olet tarkkailemalla mitä solmun on vielä käynyt.
Vuonna rekursiivinen tapauksessa se on vain helpompaa, koska pino
toteutetaan sinulle kuin ohjelma pino.
Huomaa, että tämä linkitetty lista, se on pino.
Mitä me vain laittaa pinoon
välittömästi, mitä aiomme vetää pois pinosta vierailla seuraavaksi.
Olemme myöhässä, mutta kysyttävää?
[Student, käsittämättömällä]
[Bowden] Joo. Eli jos meillä on linkitetty lista,
nykyinen tulee osoittamaan tämä kaveri,
ja nyt me vain edistämme linkitetyn listan keskittyä tämän kaveri.
Olemme liikkumisesta yli linkitetyn listan kyseisen rivin.
Ja sitten kai meidän pitäisi vapauttaa myös linkitetty lista ja juttuja
kerran ennen paluuta totta vai tarua, meidän
toistaa yli meidän linkitetty lista ja aina täällä, luulisin,
jos me nyk. oikeus ei ole sama, lisää se, joten nyt haluamme vapauttaa
nyk. koska hyvin, teimme täysin unohtaa luettelossa? Joo.
Niin, että mitä me haluamme tehdä täällä.
Missä osoitin?
Cur oli silloin - haluamme struct lista * 10 vastaa luettelon vieressä.
Ilmainen luettelo, lista = lämpötila.
Ja siinä tapauksessa, että palaamme totta, tarvitsemme iteroida
jäljellä olevan linkitetyn listan vapauttaa asioita.
Kiva juttu rekursiivinen ratkaisu on vapauttaa asioita
tarkoittaa vain popping factorings pinosta joka tapahtuu sinulle.
Joten olemme menneet jotain on kuin 3 riviä vaikeasti think noin code
jotain, joka on huomattavasti paljon enemmän vaikeasti think noin koodiriviä.
Vielä kysymyksiä?
Selvä. Olemme hyviä. Hei!
[CS50.TV]