[Powered by Google Translate] [7. szakasz: További Kényelmes] [Rob Bowden] [Harvard Egyetem] [Ez CS50] [CS50.TV] Rendben van. Szóval, mint mondtam az én e-mail, ez lesz egy bináris-fa-intenzív szakasz. De nincs sok kérdés. Szóval megyünk próbálni, és dolgozzon ki minden kérdésre és bemegy fájdalmas részletesen minden a legjobb módja a dolgok. Így rögtön az elején, mi megy keresztül mintán rajzok bináris fák, meg ilyesmi. Tehát itt, "Emlékezz arra, hogy a bináris fa van csomópont hasonló csatolt lista kivéve egy helyett két mutató: az egyik a bal oldali "gyermek" és egy a jobb "gyermek". " Tehát egy bináris fa olyan, mint egy láncolt lista, kivéve a struct lesz két mutató. Van trinary fákat, amelyek majd három mutató, vannak N-áris fák, amelyek csak egy általános mutató hogy majd kell malloc nem elégséges ahhoz, hogy a elegendő mutatókat valamennyi a lehetséges gyermek. Így bináris fa épp, hogy egy állandó számú kettő. Ha azt szeretné, hogy egy láncolt lista, mint egy egyváltozós fa, de nem hiszem, hogy bárki nevezi ezt. "Rajzolj egy doboz-és-nyilak diagram egy bináris fa csomópont tartalmazó Nate kedvenc száma, 7, ahol minden gyermek mutató null. " Szóval iPad mód. 

Ez lesz nagyon egyszerű. Mi csak megy, hogy egy csomópont, fogom felhívni, mint egy négyzet. És én felhívni az értékek itt. Tehát ez az érték megy itt, majd le itt lesz a bal oldali kurzort a bal és a jobb mutatót a jobb oldalon. És ez nagyon is egyezményt hívni balra és jobbra, a mutató nevek. Mindkét lesznek null. Ez csak úgy lesz a null, és ez csak úgy lesz a null. Oké. Tehát vissza ide. "A láncolt lista, csak kellett tárolni egy mutató Az első csomópont a lista, hogy emlékezzen a teljes láncolt lista, vagy az egész listát. Hasonlóképpen, a fák, csak el kell tárolni egy mutató egyetlen node annak érdekében, hogy emlékezzen az egész fa. Ez a csomópont calle a 'root' a fa. Építsd fel a diagram előtti vagy rajzolj egy újat úgy, hogy van egy doboz-és nyilak ábrázolása egy bináris fa az az érték 7, majd a 3-ban a bal, akkor 9 a jobb oldalon, majd a jobb oldalon 6 a 3 ". Lássuk emlékszem minden, hogy a fejemben. Szóval ez lesz a mi gyökér itt. Majd néhány mutató valahol, valami, hívjuk root, és ez mutató ezt a fickót. Most, hogy egy új csomópont, mi van, 3 a bal oldalon? Tehát egy új csomópontot, 3, és ez kezdetben mutat null. Én az imént N. Most szeretnénk, hogy győződjön meg, hogy menjen balra 7. Tehát változtatni ez a mutató, hogy most pont ezzel a fickóval. És mi nem ugyanaz. Szeretnénk egy 9 ide amely kezdetben csak mondja null. Mi fog változni ez a mutató, mutasson a 9, és most szeretnénk, hogy 6 a jobb a 3. Szóval ez lesz -, hogy a 6. És ez a fickó pont ott. Oké. Szóval ez az egész azt kéri tőlünk. 

Most menjünk át néhány terminológiát. Már beszéltünk arról, hogy a gyökér a fa a legfelső csomópont a fában. Az egyik, mely 7. A csomópontok alján a fa nevezzük a leveleket. Minden olyan csomópont, amely csak azt, null, mint a gyermekek egy levél. Így lehetséges, ha a bináris fa csak egy csomópont, hogy a fa egy levél, és ennyi. "A" magassága "a fa az ugrások számát meg kell tenni hogy a felső a levél. " Fogunk bejutni, a második, a különbség között kiegyensúlyozott és kiegyensúlyozatlan bináris fák, de most, a teljes magassága a fa Azt mondanám, hogy a 3, de ha számít az ugrások számát meg kell tenni annak érdekében, hogy 9, akkor ez tényleg csak a magassága, 2. Most ez egy kiegyensúlyozatlan bináris fa, de mi beszéltünk kiegyensúlyozott amikor megkapja relevánsnak. Tehát most beszélhetünk csomópontok egy fa szempontjából képest más csomópontok a fán. Így most már a szülők, gyermekek, testvérek, ősök és leszármazottak. Ezek elég a józan ész, hogy mit jelent. Ha azt kérdezzük - ez a szülők. Tehát mi a szülő a 3? [Diákok] 7. >> Igen. A szülő csak lesz, amit mutat az Ön számára. Akkor mi a gyermekei 7? [Diákok] 3 és 9. >> Igen. Figyeljük meg, hogy a "gyermek" szó szerint azt jelenti gyermekek, így a 6. nem kell alkalmazni, mert ez olyan, mint egy unoka. De aztán, ha megyünk leszármazottai, tehát mi a leszármazottai 7? [Hallgatók] 3, 6 és 9. >> Igen. A leszármazottai a gyökér csomópont lesz mindent a fa, kivéve talán a gyökér csomópont is, ha nem akarja, hogy fontolja meg, hogy egy leszármazottja. És végül, ősök, így az ellenkező irányba. Tehát mi az ősei 6? [Diákok] 3 és 7. >> Igen. 9 nem tartalmazza. Ez csak a közvetlen vonal vissza a gyökér lesz az ősei. 

"Azt mondjuk, hogy a bináris fa" megrendelt ", ha minden egyes csomópont a fában, valamennyi leszármazottai, a bal oldalon van kisebb értékek és az összes közül a jobb oldalon nagyobb értékeket. Például a fa fenti sorrendben, de ez nem az egyetlen lehetséges megrendelt megállapodás. " Mielőtt nekilátnánk az, hogy a rendezett bináris fa is ismert, mint egy bináris keresési fa. Itt történik meg kell nevezni egy rendezett bináris fa, de én még soha nem hallottam, hogy úgynevezett sorrendben bináris fa előtt, és egy kvíz vagyunk sokkal valószínűbb, hogy terjesszen bináris keresési fa. Ők egy és ugyanaz, és ez fontos, hogy ismeri a különbséget a bináris fa és bináris keresési fa. A bináris fa csak egy fa, amely rámutat arra, hogy két dolgot. Minden csomópont mutat két dolgot. Nincs érvelés az értékeket, hogy mutat. Tehát mint ide, mivel ez egy bináris keresési fa, tudjuk, hogy ha megyünk balra 7, akkor az összes értéket, hogy mi lehet esetleg elérni mellett haladó bal 7 már, hogy kevésbé, mint 7. Figyeljük meg, hogy minden az érték kisebb, mint 7 Összesen 3 és 6. Ezek mind a bal oldalon 7. Ha elmegyünk jobbra 7, mindennek nagyobb, mint 7, így a 9. jobbra 7, tehát vagyunk jó. Ez nem az eset egy bináris fa, a rendszeres bináris fa tudjuk csak van 3 a tetején, 7 balra, 9 balra 7, nincs rendelési értékek nélkül. Nos, akkor valójában nem ezt, mert unalmas és felesleges, de "próbálja felhívni annyi Beszerezzük fák tudsz gondolni használatával a számok 7, 3, 9, és 6. Hány különböző szabályok vannak? Mi a magassága mindegyik? " 

Majd csinál egy pár, de az alapötlet az, ez semmiképpen sem egy egyedülálló ábrázolása egy bináris fa tartalmazó ezeket az értékeket. Már csak néhány bináris fa, amely 7, 3, 6, és 9. Egy másik lehetséges érvényesnek lenne a gyökér 3, menj a balra és ez 6, menj balra, és ez 7, menj a balra és ez 9. Ez egy teljesen érvényes bináris keresési fa. Ez nem túl hasznos, mert olyan, mint egy láncolt lista és mind ezek pointerek csak nulla. De ez egy érvényes fa. Igen? [Student] Nem az értékek nagyobb lesz a jobb? Vagy ez -? Ezek >> akartam menni a másik irányba. Ott is - igen, hadd kapcsolja azt. 9, 7, 6, 3. Jó fogás. Azt még meg kell engedelmeskedni, amit egy bináris fa keresés kéne csinálni. Tehát minden balra is kisebb lesz, mint bármelyik adott csomópont. Mi is csak mozogni, mondjuk, ezt a 6 és tedd ide. Nem, nem tudjuk. Miért csinálom ezt? Csináljuk - itt 6, itt 7, 6 pont 3-ra. Ez még mindig egy érvényes bináris kereső fa. Mi lehet a baj, ha én - lássuk, ha tudok jönni egy megállapodás. Ja, oké. Szóval, mi a baj ezzel a fa? Azt hiszem, már adott egy tippet, hogy valami baj van vele. Miért csinálom ezt? Oké. Ez úgy néz ki ésszerű. Ha megnézzük az egyes csomópont, mint a 7, majd a bal oldalon a 7. 3. Tehát 3, a dolog, hogy a jog a 3. 6. És ha megnézi 6, a dolog, hogy a jog a 6. 9. Akkor miért ez nem érvényes bináris kereső fa? [Diákok] 9 továbbra is a bal oldalon 7. >> Igen. Meg kell, hogy igaz legyen, hogy minden értéket akkor esetleg megközelíthető megy a bal 7-kevesebb mint 7. Ha elmegyünk balra 7, megkapjuk a 3, és mi még mindig 6, mi még mindig 9, de miután elment kevesebb, mint 7, nem kellene tudni, hogy egy sor, ami 7-nél nagyobb. Tehát ez nem érvényes bináris keresési fa. 

A bátyám tényleg volt egy interjú kérdés hogy alapvetően ez, csak kódot valamit érvényesíteni hogy egy fa egy bináris keresési fa, és így az első dolga volt, csak nézze meg, ha a bal és jobb helyességét, majd navigálhat odalent. De nem lehet csak megtenni, meg kell követni Az a tény, hogy most, hogy elment balra 7, mindent a részfa kisebbnek kell lennie, mint 7. A helyes algoritmust kell követni A határait, hogy az értékek lehet esetleg esik be Nem megyünk végig őket. Van egy szép kiújulás kapcsolatban, bár nem ütött e, vagy mi nem fog ezen, meghatározza, hogy hány van valójában. Tehát vannak közülük 14. Az ötlet, hogy hogyan kellene csinálni, mint matematikailag, akkor vedd egyetlen egyet a gyökér csomópontot, és ha vehetem 7, hogy a gyökér csomópont, akkor van, mondjuk, néhány szám, hogy mehet az én bal csomópont, és vannak számok, hogy lehet a jobb csomópont, de ha már n összes számát, akkor az összeg, hogy mehet a bal plusz az az összeg, lehet menni a jog n - 1. Így a többi szám, akkor képeseknek kell lenniük, hogy menjen vagy balra vagy jobbra a. Úgy tűnik, nehéz, hogy ha tettem 3 első, majd mindennek menni balra, de ha feltettem 7, majd néhány dolog megy a bal és a néhány dolgot lehet menni jobbra. És '3 első "Úgy értem, mindent lehet menni jobbra. Ez tényleg, csak meg kell gondolni azt, mennyi mindent lehet menni a következő szintre a fa. És ez jön ki, hogy 14, vagy tudod felhívni mindet, és akkor kapsz 14. 

Megy vissza, "Rendezett bináris fák jó, mert tudunk keresni rajtuk keresztül egy nagyon hasonló módon történő keresést egy rendezett tömbben. Ehhez kezdjük a gyökér és a munka az utat lefelé a fáról irányába levelek, ellenőrzése minden csomópont értékek ellen az értékeket fogunk keresni. Ha az aktuális csomópont értéke kisebb, mint az érték keresünk, mész mellett a csomópont jobb gyermeke. Ellenkező esetben, ha megy a csomópont bal gyermekét. Egy bizonyos ponton, akkor sem találja az értéket, amit keres, vagy akkor befut egy null, feltüntetve az értéket nem a fán. " Nekem van, hogy dolgozza át a fa volt azelőtt, hogy elviszem egy pillanatra. De mi szeretnénk nézni, hogy a 6, 10, és 1 a fán. Szóval, mi volt, 7, 9, 3, 6. Oké. A számok szeretnénk nézni, azt akarjuk, hogy felnézzen 6. Hogyan működik ez az algoritmus működik? Nos, mi is van néhány gyökér pointer a fa. És mi megy a gyökér, és azt mondják, ez az érték megegyezik az érték amit keresett? Tehát keresünk 6, így ez nem egyenlő. Tehát menj, és most azt mondjuk, rendben, így a 6 kevesebb, mint 7. Ez azt jelenti, azt akarom, hogy a bal, vagy akarunk menni a jobb? [Student] Bal. >> Igen. Ez jelentősen megkönnyítette, mindössze annyit kell tennie, hogy dolgozzon egy lehetséges csomópont a fa és akkor nem - ahelyett, hogy úgy gondolja, a fejedben, oké, ha ez kevesebb, akkor megyek a balra vagy menjen jobbra, csak néztem ezt a képet, nagyon világos, hogy el kell mennem a bal ha ez a csomópont nagyobb, mint az érték, amit én keresek. Szóval menj balra, most én vagyok a 3. Azt akarom, hogy - 3 kisebb, mint az érték keresem, amely 6. Tehát menj jobbra, és most végül 6, amelynek az értéke keresem, úgyhogy vissza igaz. A következő érték fogok keresni a 10. Oké. Akkor 10, most fog - vágja le, hogy - fogja követni a gyökér. Most, 10 lesz, 7-nél nagyobb, ezért szeretném, hogy vizsgálja meg a jobb oldalon. Megyek, hogy jöjjön ide, 10 lesz 9-nél nagyobb, úgyhogy megyek akarom nézni a jobb oldalon. Azért jöttem ide, de itt most én vagyok a null. Mit tegyek, ha megüt null? [Student] Vissza hamis? >> Igen. Én nem találtam 10. 1 lesz a közel azonos esetben, kivéve, ez csak lesz tükrözött, ahelyett, le a jobb oldalon, fogok lenézni a bal oldalon. 

Most azt gondolom, hogy valóban kap a kódot. Itt ahol - megnyitja a CS50 készüléket és navigálhat az utat oda, de akkor is csak csinálni a térben. Ez talán Ideális kell csinálni a térben, mert tudunk dolgozni a térben. "Először is szükségünk lesz egy új típusú meghatározni egy bináris fa csomópontot tartalmazó int értékeket. A boilerplate typedef alábbi hozzon létre egy új típus definíció egy csomópont egy bináris fa. Ha elakad. . . "Bla, bla, bla. Oké. Szóval fel a boilerplate itt, typedef struct csomópont, és a csomópont. Ja, oké. Tehát mi a mezőket fogunk kívánt a csomópont? [Student] Int, majd két mutató? Int >> érték, két mutató? Hogyan lehet írni a mutató? [Student] Struct. >> Kéne Nagyítás Igen, struct node * balra, és struct node * van. És ne feledd, a vita a múlt idő, hogy ennek nincs semmi értelme, ennek nincs semmi értelme, Ennek semmi értelme. Be kell mindent annak érdekében, hogy meghatározzák e rekurzív struktúra. Oké, szóval ez az, amit a mi fa fog kinézni. Ha volt egy trinary fát, majd egy csomópont nézhet b1, b2, struct node * b3, ahol b egy ága - valójában, már több, hallottam balra, középre, jobbra, de mindegy. Csak érdekel bináris, ezért jobb, bal. "Most állapítsa globális node * változót a gyökér a fa." Szóval nem fogunk csinálni. Annak érdekében, hogy a dolgok kicsit nehezebbé és generalizált, nem lesz egy globális csomópont változót. Ehelyett, a fő fogjuk nyilvánítja minden csomópont dolgokat, és ez azt jelenti, hogy az alatt, amikor elkezdenek megjelenni a Tartalom funkciót és a betét funkció, ahelyett, hogy a Tartalom funkciót csak használ a globális csomópont változó, megyünk oda, hogy azt tegyen érvként a fa, hogy azt akarjuk, hogy feldolgozni. Tekintettel a globális változót kellett volna, hogy a dolgok könnyebb. Megyünk, hogy a dolgok nehezebb. Most egy percet, vagy úgy, hogy csak ezt a fajta dolog, ahol a belső fő szeretne létrehozni ezt a fát, és ez minden, amit akarok. Próbáld ki, és építeni ezt a fát a fő funkciója. 

Oké. Szóval nem is kell, hogy épített a fa az egész út még. De bárki valamit tudtam felhúzni hogy hogyan lehetne kezdeni építése egy ilyen fát? [Student] Valaki dörömböl, próbál kijutni. [Bowden] Bárki kényelmes a fa építése? [Student] Persze. Ez nem történt meg. >> Semmi gond. Mi is csak befejezni - Ó, tudod menteni? Hurrá. Tehát itt van - oh, én kicsit vágva. Én vagyok nagyított? Nagyítás, lapozzunk ki. >> Lenne egy kérdésem. >> Igen? [Student] Ha meg struct vannak dolgok, mint inicializálva valamit? [Bowden] Nem >> Oké. Szóval volna inicializálni - [Bowden] Nem Ha meg, vagy ha a struct nyilvánítja, nem inicializálja alapértelmezés szerint ez ugyanúgy, mint ha állapítsa int. Ez pontosan ugyanaz a dolog. Ez olyan, mint minden, az egyes területek lehet egy szemetet értékkel benne. >> És ez lehet határozni - vagy nyilvánítsa a struct oly módon, hogy ez egyáltalán inicializálni őket? [Bowden] Igen. Szóval, shortcut inicializálása szintaxis fog kinézni - Van két módon meg tudjuk csinálni. Azt hiszem, meg kell fordítani, hogy hogy győződjön meg arról csenget is teszi ezt. Az, hogy érvek, hogy jön a struct, tetted, mint a sorrendben az érvek belül e kapcsos zárójelek. Tehát, ha szeretné elindítani, hogy a 9. és balra lehet null majd jobb lesz null, lenne 9, null, null. Az alternatíva, és a szerkesztő nem tetszik ez a szintaktikai, és azt hiszi, szeretnék egy új blokk, de az alternatíva valami hasonló - itt, teszem azt egy új sort. Ön kifejezetten mondani, elfelejtettem a pontos szintaxist. Így kifejezetten foglalkozzanak ezekkel nevét, és azt mondja: . C vagy. Value = 9. Jobbra = NULL. Gondolom ezeket kell vessző. . Jobbra = NULL, tehát így nem teszed ténylegesen tudni sorrendben a struct, és ha ezt olvasod, akkor sokkal több explicit arról, hogy mi az érték ez alatt inicializálódik. 

Ez történik, hogy az egyik dolog, hogy - így van, a legtöbb esetben, a C + + felülbírálja a C. Elviheti C kód, helyezze át a C + +, és meg kell fordítani. Ez az egyik dolog, hogy a C + + nem támogatja, így az emberek inkább nem csinálni. Nem tudom, ha ez az egyetlen ok, amiért az emberek inkább nem csinálni, de ha szükséges, az I. használni kellett dolgozni C + +, és így nem tudtam használni ezt. Egy másik példa a valamit, ami nem működik a C + + hogyan malloc függvény a "void *", technikailag, de akkor csak annyit char * x = malloc bármi, és ez automatikusan leadott egy char *. Ez az automatikus leadott nem történik meg a C + +. Ez ugyanis nem fordul le, és akkor kifejezetten kell mondania char *, malloc, mindegy, hogy a leadott, hogy a char *. Nem sok mindent, hogy a C és a C + + nem értenek egyet, de ezek kettő. Akkor megyünk ezzel a szintaxissal. De még ha nem megy, hogy a szintaxis, ami - lehet baj ezzel? [Student] Nem kell dereference ez? >> Igen. Ne feledje, hogy a nyíl van egy implicit dereference, és így amikor mi csak foglalkozik a struct, szeretnénk használni. hogy egy terület belsejében a struct. És az egyetlen alkalommal, amikor használja nyíl, amikor akarunk csinálni - jól, nyíl megegyezik a - ez az, ami azt jelentette volna, ha én használt nyíl. Minden nyíl segítségével is, dereference ezt, most én vagyok egy struct, és tudok a területen. Vagy kap a területen közvetlenül vagy dereference és kap a területen - Azt hiszem, ezt kell értéket. De itt van dolgom csak egy struct, nem egy mutatót egy struct, , és így nem tudom használni a nyíl. De ez a fajta dolog, amit tehetünk az összes csomópont. Ó, istenem. Ez a 6., 7., és 3. Akkor létre az ágak a fa, mi lehet a 7 - tudjuk már, tőle balra kell mutatnia 3-ra. Szóval hogyan lehet csinálni? [Diákok, érthetetlen] >> Igen. A címe node3, és ha nem volt címe, akkor csak nem fordul. De ne feledjük, hogy ezek a mutatók a következő csomópontok. A jobb kell mutatnia 9, és 3 kell mutatnia a jobb 6-ra. Azt hiszem, ez minden. Bármilyen észrevétele vagy kérdése? [Diák, érthetetlen] A root lesz 7. Mi lehet mondjuk node * ptr = vagy root, = & node7. 

A mi céljainkra, fogunk foglalkozni betéttel, így fogunk akar írni egy függvényt beilleszteni ebbe a bináris fa és betét elkerülhetetlenül fog hívni malloc hozzon létre egy új csomópontot ezt a fát. Tehát a dolgok, hogy rendetlen a tényt, hogy egyes csomópontok Jelenleg a verem és más csomópontok fog végül a heap, amikor be őket. Ez tökéletesen érvényes, de az egyetlen oka képesek vagyunk ezt a stack azért van, mert ez egy ilyen kitalált példa, hogy tudjuk, a fa kellene felépíteni, 7, 3, 6, 9. Ha nem ezt, akkor nem kell malloc az első helyen. Mint látni fogjuk egy kicsit később, akkor kell malloc'ing. Most ez teljesen ésszerű fektetni a stack, de változtassuk meg, hogy ez egy malloc végrehajtását. Tehát mindegyik most lesz valami hasonló node * node9 = malloc (sizeof (node)). És most mi lesz, hogy meg kell csinálni a csekket. if (node9 == NULL) - Nem akartam, hogy - vissza 1, majd tehetünk node9->, mert most ez a mutató, value = 6, node9-> bal = NULL, node9-> jobb = NULL, és mi lesz, hogy meg kell tennie, hogy minden egyes ilyen csomópontok. Tehát ahelyett, mondjuk belsejében egy külön funkció. Nevezzük meg node * build_node, és ez némileg hasonlít az API-k nyújtunk Huffman-kódolással. Adunk inicializáló funkciók egy fa és deconstructor "funkciók" azon fák és ugyanazt az erdők. 

Tehát itt fogunk van egy inicializáló függvény hogy csak építeni egy node számunkra. És ez fog kinézni nagyjából pontosan olyan, mint ez. És én még lesz lusta, és nem változtatja meg a nevét, a változó, bár node9 nincs értelme többé. Oh, azt hiszem node9 értékét nem kellett volna 6. Most már vissza node9. És itt vissza kell null. Mindenki egyetért, hogy a build-a-node funkció? Így most már csak hívja, hogy építeni minden csomópont egy adott érték és null mutatók. Most már meg tudjuk hívni, hogy meg tudjuk csinálni node * node9 = build_node (9). És csináljuk. . . 6, 3, 7, 6, 3, 7. És most szeretnénk létrehozni ugyanazt a mutatók, kivéve most már minden a szempontból mutatók így már nincs szükség a címét. Oké. Szóval, mi volt az utolsó dolog, amit akarok? Van egy hiba ellenőrzésére, hogy én nem csinálok. Mit épít csomópont vissza? [Diák, érthetetlen] >> Igen. Ha malloc sikertelen, akkor az vissza null. Szóval fogom lustán tedd le ide, ahelyett, hogy a feltétel minden. Ha a (node9 == NULL, vagy - még egyszerűbb, ez egyenértékű azzal, hogy csak ha nem node9. Szóval, ha nem node9, vagy nem node6, vagy nem node3, vagy nem node7, vissza 1. Talán meg kellene nyomtatni malloc sikertelen, vagy valami ilyesmi. [Diák] A false egyenlő: null is? [Bowden] A nulla érték hamis. Tehát null nulla érték. Zero nulla érték. Hamis nulla érték. Bármely - nagyjából csak 2 nulla értékek null és a nulla, false éppen hash definiált nulla. Ez azt is érvényes, ha teszünk nyilvánítja globális változót. Ha tényleg van node * gyökér itt, akkor - a szép dolog globális változók, hogy mindig van egy kezdeti értéket. Ez nem igaz a funkciók, hogy belül van, ha van, mint az, node * vagy csomópont x. Fogalmunk sincs, mi x.value, x.whatever, vagy mi lehet nyomtatni őket, és ők lehetnek önkényes. Ez nem igaz, a globális változók. Szóval gyökér csomópont vagy csomópont x. Alapértelmezés szerint mindent, ami a globális, ha nem kifejezetten inicializálja valamilyen érték, nulla értéket az értékét. Tehát itt, node * root, nem kifejezetten inicializálni el semmit, így az alapértelmezett érték null lesz, amely a nulla érték mutatók. Az alapértelmezett érték az x fogja jelenti, hogy x.value nulla, x.left null, és x.right null. Tehát mivel ez egy struct, minden területen a struct nulla értékeket. Nem kell használni, hogy itt, mégis. [Student] A Struktúrák vannak más, mint a többi változót, és a többi változó szemeteskocsi értékeket; ezek nullák? [Bowden] egyéb értékek is. Tehát x, x nulla lesz. Ha ez a globális hatókörű, van egy kezdeti értéket. >> Oké. [Bowden] Vagy a kezdeti érték adtad, vagy nulla. Úgy gondolom, hogy gondoskodik mindezt. 

Oké. Így a következő része a kérdés arra irányul, "Most szeretnénk levelet nevezett funkció tartalmaz egy prototípus bool tartalmaz int értéket. " Mi nem fog csinálni bool tartalmaz int értéket. A prototípust fog kinézni bool tartalmaz (int értéket. És akkor mi is fog múlni, hogy a fa hogy meg kellene ellenőrzi, hogy ha van az érték. Szóval node * fa). Oké. És akkor nevezhetjük azt valami ilyesmi, talán mi szeretnénk printf vagy valami. Tartalmaz 6, a root. Ezt vissza kell adnia egy, vagy igaz, mivel tartalmaz 5 gyökér vissza kell hamis. Tehát, hogy egy második végrehajtásához. Meg tudod csinálni vagy iteratív vagy rekurzív. A szép dolog, ahogy mi is be a dolgokat, hogy a ez alkalmas arra, hogy a rekurzív megoldás sokkal könnyebb mint a globális változó módon tette. Mert ha csak azt tartalmazza int értéket, akkor nincs módja rekurzív lefelé részfák. Azt kell, hogy legyen egy külön segítő funkció recurses megállapításáról részfákat számunkra. De mivel mi már megváltoztatta, hogy a fa, mint egy érvet, azt meg mindig is az első helyen, Most tudjuk recurse könnyebben. Szóval iteratív vagy rekurzív, megyünk át mindkettőt, de majd meglátjuk, hogy a rekurzív végül is nagyon egyszerű. Oké. Van valakinek valami, tudunk dolgozni? 

[Student] Van egy iteratív megoldást. >> Rendben, iteratív. Oké, ez jól néz ki. Szóval, akarsz járni nekünk ez? [Student] Persze. Szóval beállítani temp változót, hogy az első csomópont a fa. Aztán körhurkolt míg temp nem egyenlő null, így amíg még a fa, azt hiszem. És ha az érték megegyezik az értékre, temp re mutat rá, majd visszatér az értéket. Ellenkező esetben, ellenőrzi, ha ez a jobb oldalon, vagy a bal oldalon. Ha valaha is olyan helyzetben, amikor nincs több fa, majd visszatér - kilép a hurok, és visszatér hamis. [Bowden] Oké. Szóval úgy tűnik, jó. Bárki bármilyen észrevétele van a semmit? Nekem nincs korrektség Megjegyzés egyáltalán. Az egyetlen dolog, amit tehetünk, ez a fickó. Oh, ez fog menni egy kicsit hosszúkás. Megcsinálom, hogy akár. Oké. 

Mindenkinek meg kell emlékezni, hogyan háromkomponensű működik. Voltak határozottan nem vetélkedők a múltban hogy kapsz egy funkciót egy háromkomponensű üzemeltető, és azt mondják, fordítsd le ezt, tenni valamit, hogy nem használja a hármas. Tehát ez egy nagyon gyakori eset, amikor azt hiszem, hogy használni háromkomponensű, ahol ha néhány feltétel egy változó valami, másnak állítja be, hogy ugyanazt a változót valami másra. Ez valami, ami nagyon gyakran lehet alakítani ezt a fajta dolog amennyiben állítja be, hogy a változó e - vagy, nos, ez igaz? Aztán ez, különben ezt. [Student] Az első, hogy ha igaz, ugye? [Bowden] Igen. Ahogy én mindig olvassa el azt, hőm egyenlő értéke nagyobb, mint temp érték, akkor ez, különben ezt. Ez feltettem egy kérdést. Ez a nagyobb? Ezután hajtsa végre az első dolog. Különben nem a másik dolog. Én szinte mindig - a vastagbél, csak - a fejemben, olvastam, mint más. 

Van valakinek egy rekurzív megoldás? Oké. Ez fogjuk - ez lehet már nagy, de mi lesz, hogy még jobb. Ez nagyjából pontosan ugyanolyan ötlet. Ez csak, nos, nem akarsz megmagyarázni? [Student] Persze. Szóval meggyőződve arról, hogy a fa nem null az első, mert ha a fa null akkor fog visszatérni hamis, mert még nem találtam meg. És ha van még egy fa, akkor menj be - először ellenőrizze, hogy az érték a jelenlegi csomópont. Vissza igaz, ha van, és ha nem is recurse a balra vagy jobbra. Hangzik megfelelő? >> Mm-hmm. (Megállapodás) Így észleli, hogy ez szinte - szerkezetileg nagyon hasonló az iteratív oldathoz. Csak hogy ahelyett, hogy rekurzív, volt egy while ciklus. És az alapeset itt, ahol fa nem egyenlő null volt a feltétel, amelyhez kitört a while ciklus. Ők nagyon hasonló. De mi lesz, hogy ezt egy lépéssel tovább. Most már nem ugyanaz a dolog itt. Figyeljük meg mi vissza ugyanaz mindkét vonalak, kivéve egy argumentum eltérő. Így fogunk tenni, hogy egy hármas. Megütöttem opciót valamit, és tett egy szimbólum. Oké. Szóval megyünk vissza, hogy tartalmaz. Ez kezd, hogy több vonal, nos, nagyított benne van. Általában, mint stilisztikai dolog, nem hiszem, sok ember hogy egy szóköz után a nyilat, de azt hiszem, ha következetes, ez rendben van. Ha az érték kisebb, mint fa érték, szeretnénk recurse a fa balra, mást akarunk recurse a fa van. Szóval ez volt az első lépés az, hogy ezt meg kisebb. Második lépés, hogy ezt meg kisebb - tudjuk elkülöníteni, hogy ez több sorban is. Oké. Step kettő így néz kisebb itt, így visszatérési értéke megegyezik fa értéke, illetve tartalmaz bármi. 

Ez egy fontos dolog. Nem vagyok biztos benne, hogy azt mondta, hogy kifejezetten az osztályban, de ez az úgynevezett rövidre értékelés. Az elképzelés itt az érték == fa értékét. Ha ez igaz, akkor ez igaz, és azt akarjuk, hogy "vagy", amely, bármilyen vége van. Így anélkül, hogy gondolkodás nélkül vége van, mi a teljes kifejezés megy vissza? [Student] Igaz? >> Igen, mert igaz semmit, or'd - vagy valós or'd bármi szükségszerűen igaz. Tehát amint látjuk visszatérési érték = fa érték, mi csak megy vissza igaz. Nem is megy recurse tartalmazza továbbá le a pályáról. Mi ezt egy lépéssel tovább. Return fa nem egyenlő null, és ezt az egészet. Ez tette egy sor funkciót. Ez is egy példa rövidzárlat értékelés. De most ez ugyanaz a gondolat - helyett - így a fa nem egyenlő null - vagy, nos, a fa nem egyenlő nulla, ami a rossz eset, ha a fa értéke null, akkor az első feltétel lesz hamis. Tehát hamis anded bármi lesz mi? [Student] False. >> Igen. Ez a másik fele rövidzárlat értékelés, ahol ha fa nem egyenlő nulla, akkor nem fogunk még menni - vagy ha a fa nem egyenlő null, akkor nem fogunk csinálni érték == fa értékét. Mi csak megy, hogy azonnal térjen vissza hamis. Ami azért fontos, mert ha nem rövidzárlat értékeli, majd ha a fa nem egyenlő null, ezt a második feltételt fog seg hiba mert a fa-> érték dereferencing null. Szóval ennyi. Lehet, hogy ez a - műszak egyszer vége. Ez egy nagyon gyakori dolog is, nem tesz ez összhangban, de ez egy közös dolog a körülmények, talán nem itt, de ha (fa! = NULL, és a fa-> érték == érték), nem mindegy. Ez egy nagyon gyakori állapot, ahol ahelyett, hogy törni ezt a két IFS, ha tetszik, a fa null? Oké, ez nem nulla, így most a fa értéke egyenlő értéknek? Tedd ezt. Ehelyett ez a feltétel, ez soha nem fog seg hiba mert kitörni, ha ez történetesen null. Nos, azt hiszem, ha a fa teljesen érvénytelen mutató, akkor is seg hiba, de nem seg hiba, ha a fa null. Ha ez nulla, akkor tör ki, mielőtt még másolunk a mutatót az első helyen. [Diák] Ez úgynevezett lusta értékelést? 

[Bowden] Lazy értékelés külön dolog. Lazy értékelés több hasonlót kérsz egy értéket, kérsz kiszámításához érték, fajta, de nem kell azonnal. Szóval, amíg ténylegesen szüksége van rá, nem vizsgálták. Ez nem pontosan ugyanaz a dolog, de a Huffman Pset, azt mondja, hogy mi "lustán" írni. Ennek az az oka, hogy mi, mert mi tulajdonképpen puffer az írás - nem akarunk írni egyes bitek egy időben, vagy egyéni byte egy időben, mi inkább szeretnénk, hogy egy darab bájt. Aztán egyszer van egy darab bájt, aztán írjuk ki. Annak ellenére, hogy kérje meg, hogy írjon - és fwrite és fread nem ugyanaz a fajta dolog. A puffer meg olvas és ír. Annak ellenére, hogy kérje meg, hogy írjon azonnal, akkor valószínűleg nem fog. És nem biztos, hogy a dolgok lesznek írva amíg nem hívja hfclose vagy akármi is az, amelyek aztán azt mondja, oké, én bezárása a fájl, azt jelenti, hogy én jobban írni mindent nem írtam még. Azt nem kell írni mindent amíg közelednek a fájlt, és akkor kell. Szóval ez az, amit lusta - megvárja, amíg meg kell történnie. Ez - hogy 51 és akkor megy bele részletesen, mert OCaml és minden 51, minden rekurziót. Nincsenek iteratív megoldások, alapvetően. Minden rekurzió, és lusta értékelés lesz fontos a sok esetben ahol, ha nem lustán értékeli, ez azt jelentené - A példa folyamok, melyek végtelen hosszú. Elméletileg, akkor gondolom, a természetes számok, mint a patak 1-2-3-4-5-6-7, Szóval lustán értékelt dolgok rendben vannak. Ha azt mondom, hogy akarjuk, hogy a 10. számot, akkor én is értékeli fel a 10. számot. Ha azt szeretné, hogy a századik számot, akkor én is értékeli fel a századik számot. Nélkül lusta értékelés, akkor ez lesz, hogy megpróbálja értékelni az összes szám azonnal. Te értékelése végtelen sok szám, és ez egyszerűen nem lehetséges. Tehát van egy csomó esetben, ha lusta értékelés csak elengedhetetlen a dolgok dolgozni. 

Most szeretnénk írni, ahol a betét betét lesz hasonlóan változó a meghatározás. Így most ez bool betét (int érték). Mi fog változni, hogy a lapka bool (int érték, node * fa). Mi tényleg meg fog változni, hogy ismét egy kicsit, majd meglátjuk, miért. És menjünk build_node, csak a fene azt, felett helyezze így nem kell írni egy függvény prototípus. Ami egy tipp, hogy fogsz használni build_node a betét. Oké. Vegyünk egy percet erre. Azt hiszem, megmentette a felülvizsgálni, ha azt szeretnénk, hogy húzza meg, hogy a vagy legalábbis, én most. Szerettem volna egy kis szünetet, hogy úgy gondolja, a logika betét ha nem gondol rá. Alapvetően, ha csak valaha is beilleszteni a levelek. Mint, ha be 1, akkor én elkerülhetetlenül lesz beilleszteni 1 - Majd váltson fekete - leszek beilleszteni 1 ide. Vagy ha beilleszteni 4, azt akarom, hogy 4 beilleszteni ide. Tehát nem számít, mit teszel, te leszel beilleszteni egy levél. Mindössze annyit kell tennie, hogy navigálhat le a fát, amíg nem kap a csomópont hogy kell a csomópont szülő, az új csomópont szülő, majd változtassa meg a balra vagy jobbra mutató, attól függően, hogy ez kisebb vagy nagyobb, mint a jelenlegi csomópont. Változás, hogy a mutató arra utalnak, hogy az új csomópont. Tehát ismételget le a fáról, hogy a levél pont az új csomópontot. Szintén gondolj, hogy miért tiltja az ilyen helyzetekben előtt, ahol épített a bináris fa, ahol helyes volt ha csak ránézett egy csomópont, de 9 volt, a bal oldalon 7 Ha megismételte le az összes utat. Szóval ez lehetetlen ebben a forgatókönyvben, hiszen - gondolnak beszúrásával 9, vagy valami, az első csomópont, Megyek, hogy 7-es és én csak menni jobbra. Tehát nem számít, hogy mit tegyek, ha én behelyezésénél megy, egy levél, és egy levél a megfelelő algoritmus, ez lesz lehetetlen számomra, hogy helyezze be a 9 bal 7 mert amint elütöttem 7 Én megyek jobbra. Csinál akárki volna valamit kezdeni? [Student] én. >> Persze. [Diák, érthetetlen] [Other diák, érthetetlen] [Bowden] Ez értékelik. Oké. Szeretne megmagyarázni? 

[Student] Mivel tudjuk, hogy mi volt behelyezése új csomópontok végén a fa, Én hurkolt át a fa iteratív amíg kaptam egy csomópont, amely rámutatott null. És akkor úgy döntöttem, hogy azt akár a jobb oldalon, vagy a bal oldalon használja ezt a jogot a változó, azt mondta nekem, hogy hol tegye. És aztán, lényegében csak tenni, hogy az utolsó - hogy a temp csomópont pont az új csomópont, hogy azt létre, akár a bal oldalon, vagy a jobb oldalon, attól függően, hogy milyen értéket helyes volt. Végül, én meg az új csomópont értéket a értékét tesztelés. [Bowden] Oké, akkor látom, egy kérdés van. Ez olyan, mint 95%-a az út ott. Az egyetlen kérdés, hogy látom, nos, nem másnak látni egy kérdés? Mi az a körülmény, amely alapján törnek ki a hurok? [Student] Ha a hőmérséklet nulla? >> Igen. Szóval, hogyan tör ki a hurkot, ha temp null. De mit tegyek itt? I dereference temp, ami elkerülhetetlenül null. Szóval a másik dolog, amit meg kell tennie, hogy nem csak nyomon követni, amíg temp null, szeretné nyomon követni a szülő minden alkalommal. Mi is szeretnénk, node * szülő, azt hiszem, meg tudjuk tartani, hogy null elején. Ez megy, hogy furcsa viselkedést a gyökér a fa, de mi lesz erre. Ha az érték nagyobb, mint bármi, akkor temp = temp van. De mielőtt ezt tesszük, szülő = temp. Vagy a szülők mindig lesz egyenlő temp? Ez a helyzet? Ha a hőmérséklet nem nulla, akkor megyek lejjebb, nem számít, mit, olyan csomópont, amely hőmérséklet a szülő. Szóval szülő lesz temp, aztán mozogni temp lefelé. Most temp null, de rámutat arra, hogy szülő a szülő a dolog, hogy null. Tehát itt, nem akarom beállítani jobbra értéke 1. Szóval költözött a jobb, tehát ha jobbra = 1, és azt hiszem, te is szeretnél csinálni - ha mozog balra, szeretné beállítani jobbra 0-val egyenlő. Vagy ha valaha is mozog jobbra. Szóval jobb = 0. Ha jobbra = 1, Most azt szeretnénk, hogy a szülő megfelelő mutató newnode, más, amit szeretnénk, hogy az anyavállalat balra mutató newnode. Kérdések az? Oké. Tehát ez az út is - nos, valójában, ahelyett, hogy ezt, mi 1/2 várható használatát build_node. És aztán, ha newnode egyenlő null vissza hamis. Ez azt. Nos, ez az, amit vártunk tőled. 

Ez az, amit az alkalmazott megoldásokat csinálni. Nem értek egyet ezzel a "megfelelő" módon megy róla de ez teljesen rendben van, és működni fog. Egy dolog, hogy ez egy kicsit furcsa most is ha a fa indul a null, átadjuk egy null fa. Azt hiszem, ez attól függ, hogyan határozza meg a viselkedését halad egy null fa. Azt gondolom, hogy ha átmegy egy null fa, majd helyezze az érték egy null fa kéne vissza egy fát, ahol az egyetlen érték, hogy egyetlen csomópont. Embereknek Egyetért ezzel? Azt tudta, ha akarod, ha át egy null fa és a beszúrni kívánt értéket bele, vissza hamis. Ez rajtad múlik, hogy meghatározza, hogy az. Ehhez az első dolog, amit mondtam, és akkor - nos, akkor fogsz gondot csinál, mert könnyebb lenne, ha lenne egy globális mutatót a dolog, de nem, így ha a fa null, ott semmit sem tehetünk róla. Mi is csak vissza hamis. Szóval meg fog változni betéttel. Mi technikailag is csak megváltoztatni ezt itt, hogyan is iterációjával dolgok felett, de fogom változtatni betét, hogy egy csomópont ** fa. Dupla mutatók. Mit jelent ez? Ahelyett, hogy foglalkozik mutatókat csomópontok, a dolog, fogok is manipulálni ez a mutató. Megyek, hogy manipulálni ez a mutató. Megyek, hogy manipulálni mutatókat közvetlenül. Ez logikus is, hiszen gondoljon le - Nos, most ezt a pontot null. Amit én akarok, manipulálni ez a mutató, hogy pont nem nulla. Azt akarom, hogy pont az én új csomópontot. Ha csak nyomon követni a mutatókat a mutatók, akkor nem kell nyomon követni a szülő mutató. Én is csak nyomon követni, hogy ha a mutató mutat null, és ha a mutató mutat null, változtassa meg, hogy pont a csomópont akarok. És tudom megváltoztatni, mivel van egy mutatót a mutatót. Nézzük meg ezt most. Tudod valójában csinálni rekurzívan elég könnyen. Nem akarunk ilyet? Igen, mi. 

Lássuk rekurzívan. Először is, mi a alapeset lesz? Szinte mindig a bázis esetében, de valójában ez a fajta trükkös. Először is, ha a (fa == NULL) Azt hiszem, mi csak megy vissza hamis. Ez eltér a fa, hogy null. Ez a mutató a gyökér, hogy null pointer ami azt jelenti, hogy a root mutató nem létezik. Tehát itt, ha én nem node * - nézzük csak újra ezt. Node * root = NULL, majd fogom hívni betét csinál valami ilyesmi, be a 4. és root. Szóval és gyökér, ha a gyökér csomópont * akkor és gyökér lesz egy csomópont **. Ez érvényes. Ebben az esetben a fa, fel itt, fa nem null - vagy betét. Tessék. Fa nem null; * fa null, ami rendben van mert ha * fa null, akkor én is manipulálni Most hova mutasson a mit akarok, hogy mutasson. De ha a fa null, azt jelenti, hogy csak azért jöttem ide, és azt mondta: null. Ennek nincs értelme. Nem tudok mit kezdeni vele. Ha a fa null vissza hamis. Szóval alapvetően már mondtam, mi a valódi alap eset. És mi az, hogy lesz? [Diák, érthetetlen] [Bowden] Igen. Tehát, ha (* fa == NULL). Ez arra az esetre vonatkozik ide ahol ha a piros mutató a mutató Én összpontosított, így, mint én összpontosított ez a mutató, most én vagyok összpontosított ez a mutató. Most elsősorban erre mutató. Tehát, ha a piros mutató, ami az én csomópont **, valaha is - ha *, a piros mutató, valaha is null, azt jelenti, hogy én vagyok az a helyzet, ha én vagyok összpontosítva pointer, amely pontok - ez egy olyan mutató, amely tartozik a levél. Szeretném megváltoztatni ezt a mutatót, hogy pont az új csomópont. Gyere vissza ide. Erre newnode majd csak lesz node * n = build_node (érték) akkor n, ha n = NULL vissza hamis. Különben meg akarjuk változtatni, amit a mutató jelenleg mutat hogy most pont a mi újonnan épült csomópont. Mi valóban csinálni itt. Ahelyett, hogy n, mondjuk * fa * = ha fa. Mindenki érti ezt? Ez a szó mutatókat mutatók, meg tudjuk változtatni null mutatók arra utalnak, hogy a dolgokat akarjuk, hogy mutasson. Ez a mi alapeset. 

Most a kiújulás, vagy a mi rekurzió, lesz nagyon hasonló az összes többi recursions voltunk csinál. Elmegyünk a beszúrni kívánt értéket, és most fogom használni hármas újra, de mi a feltétele lesz? Mi is keresünk annak eldöntésére, hogy akarunk menni balra vagy jobbra? Csináljuk külön lépéseket. Ha (értéke <) mi? [Student] A fa értéke? [Bowden] Úgy emlékszem, hogy én vagyok jelenleg - [Diákok, érthetetlen] [Bowden] Igen, itt van, mondjuk, hogy ez a zöld nyíl egy példa arra, milyen fa jelenleg, egy mutató a mutató. Tehát ez azt jelenti, én vagyok a mutató egy mutató a 3. A dereference kétszer jól hangzott. Mit - hogyan tudom ezt? [Student] dereference egyszer, majd tegye arrow így? [Bowden] So (* fa) a dereference egyszer -> értéke fog adni nekem az érték a csomópont, hogy én vagyok közvetve mutat. Szóval én is írni ** tree.value, ha azt szeretné, hogy. Vagy működik. Ha ez a helyzet, akkor azt akarom, hogy hívja be az értéket. És mi van az én frissítik csomópont ** lesz? Azt akarom, hogy a baloldalt, így ** tree.left lesz a bal oldalon. És azt akarjuk, hogy a mutató a dolog hogy ha a bal végül is a null pointer, Én lehet módosítani, hogy mutasson az új csomópont. 

És a másik esetben is nagyon hasonló. Nézzük ténylegesen, hogy az én háromkomponensű most. Helyezze be az értéket, ha értéke <(** fa). Értéket. Aztán szeretnénk frissíteni a ** a baloldalt, mást szeretnénk frissíteni a ** jobbra. [Student] Ez azt kap a mutatót a mutató? [Bowden] Emlékezz arra, hogy - ** tree.right egy csomópont csillag. [Diák, érthetetlen] >> Igen. ** Tree.right olyan, mint ez a mutató, vagy valami. Így azáltal, hogy egy mutatót, hogy ez ad nekem, amit akarok A mutató a fickó. [Student] Mehetünk újra, hogy miért használ a két mutató? [Bowden] Igen. Így - nem, csak tudod, és ezt a megoldást, mielőtt volt a módja, hogy anélkül, hogy 2 mutatók. Be kell, hogy képes legyen megérteni, hogy a két mutató, és ez egy tisztább megoldás. Emellett észre, hogy mi történik, ha a fa - mi történik, ha a root volt null? Mi történik, ha nem ebben az esetben itt? Szóval node * root = NULL, helyezze a 4. és root. Mi gyökér lesz ezután? [Diák, érthetetlen] >> Igen. Root érték lesz 4. Root balra lesz null a root jogot lesz null. Abban az esetben, ha már nem felelt meg a gyökér a cím, nem tudtunk módosítani root. Abban az esetben, ha a fa - ahol gyökér volt null, mi csak vissza kellett térnie hamis. Semmit sem tehetünk. Nem tudjuk beilleszteni a csomópont egy üres fa. De most már tudjuk, mi csak, hogy egy üres fát egy csomópont fa. Ami általában a várt módon, hogy úgy kéne dolgozni. 

Továbbá, ez jóval rövidebb, mint is nyomon követi az anyavállalat, és így navigálhat le az összes utat. Most már a szüleim, és én csak az én szülő joga mutató az bármi. Ehelyett, ha ezt tette iteratív, lenne, ugyanezt a gondolatot egy while ciklus. De ahelyett, hogy foglalkozni szüleim mutató, ehelyett a jelenlegi mutató lenne a dolog hogy én közvetlenül módosítja, hogy pont az új csomópont. Nem kell foglalkozni, hogy ez mutat a bal oldalon. Nem kell foglalkozni, hogy ez jobbra mutató. Csak amit ez a mutató az, fogom beállítani, hogy mutasson az új csomópont. Mindenki érti, hogyan működik? Ha nem, miért akarunk csinálni így, de legalább ez működik, mint a megoldás? [Student] Hol vissza igaz? [Bowden] Ez valószínűleg igaza van. Ha helyesen tegye vissza igaz. Else, ide megyünk vissza akar térni, amit betét visszatér. 

És mi van a különleges ebben a rekurzív függvény? Ez farok rekurzív, így ameddig fordítani némi optimalizálás, akkor felismeri azt, és soha nem lesz egy halom túlcsordulás e, akkor is, ha a fa van magassága 10.000 vagy 10 millió. [Diák, érthetetlen] [Bowden] Azt hiszem, ez azt Dash - vagy mi optimalizálási szint szükség van a farok rekurziót el kell ismerni. Azt hiszem, elismeri - GCC és csenget is különböző jelentéssel való optimalizálás szintjét. Azt akarom mondani, hogy ez DashO 2, biztos, hogy felismeri farok rekurziót. De - meg tudná építeni, mint egy Fibonocci példa, vagy valami. Ez nem könnyű tesztelni ezt, mert nehéz építeni egy bináris fa, amely olyan nagy. De igen, azt hiszem, ez DashO 2, azaz ha fordítasz DashO 2, hogy fog kinézni a farok rekurzió és optimalizálja, hogy ki. Menjünk vissza - be szó szerint az utolsó dolog, amire szüksége van. Menjünk vissza a betétet ide hová megyünk, hogy tegyék ugyanezt a gondolatot. Ez lesz még a hibája az, hogy nem tudja teljes mértékben kezelni ha a gyökér maga null, vagy a múlt bejegyzés null, de ahelyett, hogy foglalkozik a szülő mutató, nézzük alkalmazzák ugyanazt a logikát tartása mutatókat mutatók. Ha itt tartjuk node ** akt, , és nem kell nyomon követni a jog többé, de node ** cur = & fa. És most mi while ciklus lesz, míg * akt nem egyenlő null. Nem kell, hogy nyomon követhesse a szülők többé. Nem kell nyomon követni a balra és jobbra. És én hívom temp, mert mi már használja temp. Oké. Tehát, ha (érték> * temp), akkor & (* temp) -> jobb más temp = & (* temp) -> balra. És most, ezen a ponton, ezt követően pedig hurok, Én csak ezt azért, mert talán könnyebb gondolkodni iteratív módon, mint a rekurzív de miután ez a while ciklus, * Temp a mutató akarunk változtatni. 

Mielőtt volt szülő, és azt akartuk változtatni bármelyik szülő balra vagy jobbra szülő, de ha meg akarjuk változtatni szülő jobb, akkor * temp van szülő joga, és meg tudjuk változtatni közvetlenül. Tehát itt, meg tudjuk csinálni * temp = newnode, és ennyi. Szóval hirdetmény minden, amit tett ez vegye ki sornyi kódot. Annak érdekében, hogy nyomon követhesse a szülő minden, ami további erőfeszítéseket igényel. Itt, ha csak nyomon követi a mutatót a mutatót, és még ha azt akartuk, hogy megszabaduljon az összes ilyen kapcsos zárójelek most, azt a látszatot rövidebb. Ez most pontosan ugyanaz a megoldás, de kevesebb sornyi kódot. Miután elkezdte felismerve ezt érvényes megoldás, ez is könnyebb, mint a hasonló okból mintegy, oké, miért van ez a flag at int ugye? Mit jelent ez? Oh, ez jelezve, hogy minden alkalommal, amikor elindulsz jobbra, azt kell beállítani, else if elmegyek maradt azt kell beállítani, hogy nulla. Itt nem kell ok, arról, hogy ez csak könnyebb gondolkodni. Kérdései vannak? [Diák, érthetetlen] >> Igen. Oké, az utolsó bit - Azt hiszem, egy gyors és egyszerű a funkció, amit tehetünk az, let's - együtt, azt hiszem, próbálja levelet tartalmaz függvényt ami nem érdekli, hogy ez egy bináris keresési fa. Ez tartalmazza a függvény visszatérési értéke true Ha bárhol az általános bináris fa az érték keresünk. Úgyhogy első csináljuk rekurzívan aztán megcsináljuk iteratív. Mi lehet valójában csak együtt csináljuk, mert ez lesz nagyon rövid. 

Mi az én alapeset lesz? [Diák, érthetetlen] [Bowden] Tehát, ha (fa == NULL), akkor mi van? [Student] Vissza hamis. [Bowden] Else, nos, nem kell a mást. Ha az volt a másik alapeset. [Student] Tree érték? >> Igen. Tehát, ha (fa-> érték == értéket. Figyeljük meg vagyunk vissza node *, nem node ** s? Tartalom soha nem kell használni a node **, mivel mi nem módosítja mutatók. Mi csak áthaladó őket. Ha ez megtörténik, akkor vissza akarnak térni igaz. Else szeretnénk keresztezik a gyerekeket. Tehát nem lehet érvelni arról, hogy mindent a bal kevésbé és minden jobbra nagyobb. Szóval, mi a feltétele lesz itt - vagy, mit fogunk csinálni? [Diák, érthetetlen] >> Igen. Return tartalmaz (érték, fa-> bal) illetve tartalmaz (érték, fa-> jobbra). És ennyi. És észre némi rövidzárlat-értékelés, ahol ha úgy látjuk, az értéket a bal oldali fa, soha nem kell nézni a jobb fa. Ez a teljes funkció. Most csináljuk iteratív, ami lesz kevésbé szép. Elvisszük a szokásos kezdete node * cur = fa. Míg a (akt! = NULL). Gyorsan fog látni a problémát. Ha akt - itt, ha valaha is kitörni ebből, akkor már elfogy a dolog, hogy nézd meg, így vissza hamis. Ha az (akt-> érték == érték), vissza igaz. Tehát most vagyunk egy helyen - nem tudjuk, hogy akarunk menni balra vagy jobbra. Szóval önkényesen, menjünk balra. Én nyilvánvalóan befut olyan kérdés, ahol én már teljesen felhagyott mindent - Én mindig csak ellenőrzi a bal oldalán egy fa. Soha nem fogom ellenőrizni semmit, hogy joga van a gyermek semmit. Hogyan tudom kijavítani ezt? [Student] Meg kell nyomon követni a jobb és a bal egy verem. [Bowden] Igen. Szóval hogy ez struct lista node * n, majd a node ** a következő lépés? Úgy gondolom, hogy jól működik. Azt akarom, hogy a bal, vagy let's - itt. Struct lista list =, akkor kezdjük ki ez a struct listát. * List = NULL. Annak érdekében, hogy ez lesz a mi linkelt lista A részfák hogy már átugorja. Fogunk bejárására balra most de mivel elkerülhetetlenül kell, hogy térjen vissza a jobb, Megyünk, hogy a jobb oldali belső mi struct lista. Akkor mi lesz new_list vagy struct, struct lista *, new_list = malloc (sizeof (lista)). Megyek mellőzni hibaellenőrző, de ellenőrizni kell, hogy ha ez a null. New_list a csomópontot, hogy fog mutatni - oh, ezért szerettem volna itt. Ez lesz, hogy pont egy második struct lista. Ez csak az, hogy hogyan kapcsolódik listák munkát. Ez ugyanaz, mint egy int láncolt lista kivéve, mi csak helyébe int a node *. Ez pontosan ugyanaz. Szóval new_list az érték a mi new_list csomópont, lesz akt-> jobbra. Az érték a mi new_list-> next lesz az eredeti listán, majd fogjuk frissíteni a listát, hogy pont new_list. 

Most arra van szükség valamilyen módon húzza a dolgokat, mint már áthaladt az egész bal oldali részfa. Most arra van szükség, hogy húzza cucc belőle, mint akt null, mi nem akarjuk, hogy csak vissza hamis. Azt akarjuk, hogy most húzni ezen kívül meg az új lista. Egy kényelmes módja ennek - nos, valóban, van több lehetőség kínálkozik. Bárki van egy javaslatom? Hol kell csinálni ezt, vagy hogyan kellene ezt csinálni? Már csak egy pár percig, de a javaslatok? Helyett - egy út, ahelyett a mi feltétel, míg, amit éppen nézi most nem nulla, ehelyett fogunk tovább menni, amíg a lista önmagában null. Tehát, ha a lista végül is null, akkor már elfogyott a dolgokat keresni, a keresés vége. De ez azt jelenti, hogy az első dolog, a mi listán csak megy, hogy az első csomópontot. A legelső dolog lesz - már nem kell látni. Szóval list-> n lesz a fa. list-> következő lesz null. És most, míg a lista nem egyenlő null. Cur fog húzni valamit a listából. Szóval akt fog egyenlő list-> n. És akkor a lista megy egyenlő lista-> n, vagy a lista-> next. Tehát, ha akt értéke megegyezik értéket. Most hozzá mind a jobb mutató és a bal mutató mindaddig, amíg ők nem null. Itt lent, azt hiszem, meg kellett volna tenni, hogy az első helyen. Ha az (akt-> jobb! = NULL) akkor fogjuk beszúrni a csomópont a mi listáját. Ha az (akt-> balra), ez egy kis extra munkát, de ez rendben van. Ha az (akt-> balra! = NULL), és megyünk be a bal oldalon a mi láncolt lista, és hogy kell azt. Mi ismételget - mindaddig, amíg van valami a listán, van egy másik csomópont nézni. Szóval nézzük, hogy a csomópont, mi előre A lista a következő egy. Ha ez a csomópont az értéket keresünk, akkor vissza igaz. Else be mind a bal és jobb oldali részfa, mindaddig, amíg ők nem nulla, a mi lista azért, hogy elkerülhetetlenül menjen át őket. Tehát, ha nem volt null, ha a gyökér pointer mutatott két dolgot, majd először húzta ki valamit így a lista végül is null. És akkor teszünk két dolgot vissza, így most a lista a 2-es méret. Aztán megyünk loop vissza, és mi csak fog húzni, mondjuk, a bal mutató a mi gyökér csomópont. És ez akkor csak tartsa történik, és mi a végén hurok mindent. 

Vegyük észre, hogy ez lényegesen bonyolultabb A rekurzív megoldás. És azt is mondtam többször hogy a rekurzív megoldás általában sok közös az iteratív megoldás. Itt pontosan ez az, amit a rekurzív megoldás csinál. Az egyetlen változás az, hogy ahelyett, hogy hallgatólagosan a stack, a program verem, mint a módja, hogy nyomon követhetőek, amit csomópont még mindig szükség van, hogy látogassa meg, most már kifejezetten használni linkelt listát. Mindkét esetben a nyomon követése, hogy mi csomópont kell még látogatható. Abban az esetben, rekurzív ez csak könnyebb, mert egy halom valósul meg az Ön számára, mint a program verem. Vegyük észre, hogy ez a láncolt lista, ez egy verem. Bármit is csak tedd a verem azonnal mit fogunk, hogy húzza le a köteget, hogy látogassa meg a következő. Elfogyott az idő, de a kérdése? [Diák, érthetetlen] [Bowden] Igen. Tehát, ha már a linkelt lista, áram fog mutatni ez a fickó, és most mi csak haladnak a linkelt listát, hogy összpontosítson ezt a fickót. Mi áthaladó át a csatolt lista a sorban. És akkor azt hiszem, meg kell szabadítani a linkelt lista és a cucc egyszer, mielőtt visszatért igaz vagy hamis, meg kell iterációkhoz a láncolt lista, és mindig itt, azt hiszem, ha akt jog nem egyenlő, add meg, így most szeretnénk felszabadítani akt, mert, nos, nem vagyunk teljesen felejtsd el a listát? Yeah. Szóval ez az, amit akarunk itt csinálni. Hol van a mutató? Cur volt akkor - azt akarjuk, hogy egy struct lista * 10 egyenlő melletti listában. Free lista list = temp. És abban az esetben, ha visszatérünk igaz, mi kell megismételni át a fennmaradó mi linkelt lista felszabadítása dolgokat. A szép dolog a rekurzív megoldás felszabadítja a dolgokat csak azt jelenti, popping factorings ki a stack, amely meg fog történni az Ön számára. Így már eltűnt valami, ami olyan, mint 3 sornyi nehezen hiszem, körülbelül kód valami, ami lényegesen több a nehezen hiszem, körülbelül sornyi kódot. Van még kérdés? Rendben van. Jók vagyunk. Viszlát! [CS50.TV]