[Powered by Google Translate] [§ 7] [menej komfortné] [Nate Hardison] [Harvard University] [To je CS50.] [CS50.TV] 

Vitajte v § 7. Vďaka hurikánu Sandy, namiesto toho, aby normálne časť tento týždeň, robíme to priechodná, prostredníctvom sekcie otázok. Budem sa po spolu s Problem Set 6 Specification, a prechádzajú všetky otázky v Sekcie Otázky sekcie. Ak máte nejaké otázky, prosím poslať tieto na CS50 diskutovať. 

Dobre. Poďme začať. Práve teraz sa pozerám na strane 3 špecifikácia problému Set. Budeme najprv začať hovoriť o binárnych stromoch pretože tie majú veľa dôležité pre tento týždeň problému set - Strom Huffman kódovanie. Jedným z prvých dátových štruktúr sme o tom hovorili na CS50 bolo pole. Si uvedomiť, že pole je postupnosť prvkov - všetky rovnakého typu - uložené priamo vedľa seba v pamäti. Ak mám celé číslo poľa, ktoré môžem čerpať pomocou tohto boxy-čísla-celé čísla štýl - Povedzme, že mám 5 v prvom poli, mám 7 v druhom, potom som si 8, 10, a 20 v konečnom poli. Nezabudnite, naozaj dva dobré veci o tomto poli je, že máme túto konštantu-time prístup k akejkoľvek konkrétnej prvok  v poli, ak poznáme jeho index. Napríklad, ak chcem chytiť tretí prvok v poli - na indexe 2 pomocou nášho nuly indexovanie systému - Doslova som jednoducho urobiť jednoduchý matematický výpočet, hop do tejto polohy v poli, vytiahnite 8, ktorý je uložený tam, a ja som dobré ísť. 

Jedným zo zlých vecí na tomto poli -, že sme o tom hovorili keď sme hovorili o prepojených zoznamov - je, že keď chcem vložiť prvok do tohto poľa, Budem musieť urobiť nejaké radenie okolí. Napríklad, toto pole tu je v triedenom poriadku - vo vzostupnom poradí - 5, potom 7, potom 8, potom 10, a potom sa 20 - ale keď chcem vložiť číslo 9 do tohto poľa, Budem musieť posunúť niektoré prvky, aby miesto. Môžeme čerpať túto tu. Budem musieť presunúť 5, 7, a potom 8; vytvoriť medzeru, kde som môžete dať 9, a potom 10 a 20 môže ísť na pravej strane 9. To je druh bolesti, pretože v najhoršom prípade - keď sme s vložiť buď na začiatku a na konci z poľa, v závislosti na tom, ako sme posúvanie - môžeme skončiť museli posunúť všetky prvky že sa to v súčasnej dobe skladovania v poli. 

Takže, čo bolo ako vyriešiť tento problém? Cesta okolo to bolo ísť do nášho Linked-zoznam metóda, kde - miesto uloženia prvkov 5, 7, 8, 10, a 20 všetky vedľa seba v pamäti - to, čo sme namiesto toho som bola ukladať im druhu tam, kde sme chceli uložiť v týchto linked-zoznam uzlov, ktoré som kreslenie tu, druh ad hoc. A potom sme spojili dohromady pomocou týchto ďalších ukazovateľov. Môžem mať ukazovateľ z 5 na 7, ukazovateľ z 7 na 8, ukazovateľ z 8 na 10, a konečne, ukazovateľ od 10 do 20, a potom nulový ukazovateľ na 20 naznačuje, že nič nezostalo. Trade-off, že tu máme je, že teraz chceme vložiť číslo 9 do nášho zoznamu zoradené, všetko, čo musíme urobiť, je vytvoriť nový uzol s 9, bola pripojená až k bodu na príslušné miesto, a potom sa znova drôt 8 ukazoval dole do 9.. To je celkom jednoduché, za predpokladu, že presne vieme, kam chceme vložiť 9. Ale trade-off výmenou za to, že sme dnes stratili konštantný časový prístup pre konkrétny prvok v našej dátovej štruktúry. Napríklad, ak chcem nájsť štvrtý prvok v tomto prepojenom zozname, Budem musieť začať na začiatku zoznamu a pracovať svoju cestu cez počítanie uzlov s-node, až nájdem štvrtom. 

S cieľom získať lepší prístup k výkonu ako prepojeného zoznamu - ale aj udržať niektoré z výhod, ktoré sme mali pokiaľ ide o vloženie čase z prepojeného zoznamu - binárny strom bude potrebovať trochu viac pamäte. Najmä, namiesto toho, aby len s jednou ukazovateľ v binárnom stromu uzla - ako linked-zozname uzol robí - budeme chcete pridať druhý ukazovateľ do binárneho stromu uzol. Skôr než len s jednou ukazovateľ na ďalší prvok, budeme mať ukazovateľ na ľavej dieťa a pravej dieťa. 

Poďme nakresliť obrázok, čo to vlastne vyzerá. Opäť, budem používať tieto krabice a šípy. Binárne strom uzol bude začať s jednoduchým krabici. To bude mať priestor pre hodnotu, a potom je to tiež bude mať priestor pre ľavé dieťa a pravej dieťa. Chystám sa popísať tu. Budeme mať ľavej dieťa, a potom budeme mať ten správny dieťa. Existuje mnoho rôznych spôsobov, ako to urobiť. Niekedy na priestor a pohodlie, Budem vlastne kresliť ako ja tu robím na dne kde budem mať hodnotu na vrchole, a potom na pravej dieťa na pravej dolnej, a vľavo dieťa na dole vľavo. Vráťme sa späť k tomuto hore diagramu, máme hodnotu na samom vrchole, potom máme na ľavej dieťa ukazovateľ, a potom máme právo-dieťa ukazovateľ. 

V problému Nastaviť špecifikácie, Ak hovoríme o kreslenie uzol, ktorý má hodnotu 7, a potom ľavej dieťa ukazovateľ, ktorý je nulový, a pravým dieťa ukazovateľ, ktorý je prázdny. Môžeme buď napísať kapitálové NULL v priestore pre ako ľavej dieťa a právo dieťaťa, alebo môžeme čerpať tento uhlopriečka lomítko každým z polí naznačujú, že je to null. Ja budem robiť, že práve preto, že je to jednoduchšie. To, čo vidíte tu sú dva spôsoby, ako diagramov veľmi jednoduchý binárny strom uzol kde máme hodnotu 7 a nulové podriadené uvedieme. 

Druhá časť našich špecifikácia hovorí o tom, ako s lineárnymi zoznamy - pamätajte, sme mali len držať na úplne prvý prvok v zozname pamätať celý zoznam - a podobne, s binárneho stromu, máme len držať na jednej ukazovateľ na strom za účelom zachovania kontroly nad celou dátové štruktúry. Táto špeciálna prvok stromu sa nazýva koreň stromu. Napríklad, ak sa tento uzol - to uzol obsahujúci hodnotu 7 s null ľavej a pravej dieťa ukazovateľov - boli iba hodnota v našom stromu, potom by to byť náš koreňový uzol. Je to úplne na začiatku nášho stromu. Vidíme to trochu jasnejšie, akonáhle začneme pridávať ďalšie uzly náš strom. Dovoľte mi, aby som vytiahnuť novú stránku. 

Teraz budeme kresliť strom, ktorý má 7 pri koreni, a 3 vnútri ľavého dieťaťa, a 9 vnútro pravé dieťa. Opäť, to je celkom jednoduchý. Máme 7, nakreslite uzol 3, uzol pre 9, a ja idem nastaviť ľavú dieťa ukazovateľ 7 ukazoval na uzol obsahujúci 3, a pravej dieťa ukazovateľ na uzol obsahujúci 7 k uzla obsahujúce 9. Teraz, od 3 a 9 nemajú žiadne deti, budeme nastaviť všetky ich podriadené ukazovatele budú mať hodnotu null. Tu, koreň našej stromu zodpovedá uzla obsahujúce číslo 7. Môžete vidieť, že ak všetko, čo máme, je ukazovateľ na tento koreňový uzol, potom môžeme prejsť náš strom a prístup k obom podriadené uzly - obaja 3 a 9. Nie je potrebné zachovať odkazy na jednotlivý uzol na strome. Dobre. Teraz budeme pridávať ďalšie uzol na tomto schéme. Budeme chcete pridať uzol obsahujúci 6, a budeme pridávať to ako pravé dieťa uzla obsahujúceho 3. Ak sa chcete, že budem mazať, že nulový ukazovateľ v 3-uzol bola pripojená až k bodu na uzol obsahujúci 6. Dobre. 

V tomto bode, poďme cez trochou terminológie. Ak chcete začať, dôvod, že tento sa nazýva binárny strom, najmä je to, že má dva podriadené ukazovatele. Existujú aj iné druhy stromov, ktoré majú viac detí ukazovatele. Najmä, ste "vyskúšať" v probléme Set 5. Určite ste si všimli, že v tomto pokuse, ste mali 27 rôznych ukazovateľov na rôzne deti - jeden pre každú z 26 písmen v anglickej abecede, a potom 27. pre apostrof - tak, že je podobný typ stromu. Ale tu, pretože je to binárny, máme len dve podriadené ukazovatele. 

Okrem tohto koreňového uzla, ktorý sme hovorili, sme tiež hádže okolo tohto pojmu "dieťa." Čo to znamená pre jeden uzol, aby sa dieťa iného uzla? To znamená, že sa doslova podriadený uzol je dieťa ďalšieho uzla ak je toto uzol má jeden z jeho podriadených ukazovateľov stanovených upozorniť na tento uzol. K tomu, aby to do viac konkrétnych podmienkach, ak 3 je zameraná na jeden z detských ukazovateľov z 7, potom 3 je dieťa 7. Ak by sme mali prísť na to, čo deti 7 árov - dobre, vidíme, že 7 má ukazovateľ na 3 a ukazovateľ na 9, tak 9 a 3 sú deti 7. Deväť nemá žiadne deti, pretože jeho podriadené ukazovatele sú null, a 3 má iba jedno dieťa, 6. Šesť tiež nemá žiadne deti, pretože oba jeho ukazovateľov sú null, ktoré budeme čerpať hneď. 

Okrem toho sme tiež hovoriť o rodičoch určitého uzla, a to je, ako by ste očakávali, opak tohto dieťaťa popisu. Každý uzol má len jedného rodiča - namiesto dvoch ako sa dalo očakávať s ľuďmi. Napríklad, nadradený 3 je 7. Rodič 9 je taktiež 7, a rodič 6 je 3. Nič moc na to. Máme tiež podmienky hovoriť o starých rodičov a vnúčat, a všeobecnejšie budeme hovoriť o predkoch a potomkovia v konkrétnom uzle. Predchodca uzla - alebo predkovia, skôr o uzle - sú všetky uzly, ktoré leží na ceste od koreňa k tomuto uzlu. Napríklad, keď som pri pohľade na uzla 6, potom predkovia sa bude aj 3 a 7. Predkovia 9, napríklad, sú - keď som pri pohľade na uzla 9 - potom predok 9 je len 7. A potomkovia sú presne naopak. Ak sa chcem pozrieť na všetky potomkov 7, potom som sa pozrieť na všetky uzly pod ním. Takže, mám 3, 9, a 6 všetky ako potomkov 7. 

Konečný termín, ktorý budeme hovoriť, je tento pojem je súrodenec. Súrodenci - druh po pozdĺž týchto rodinných podmienok - sú uzly, ktoré sú na rovnakej úrovni vo stromu. Takže, 3 a 9 sú súrodenci, pretože sú na rovnakej úrovni vo stromu. Obaja majú rovnaké rodičia, 7. 6 nemá žiadne súrodenca, pretože 9 nemá žiadne deti. A 7 nemá žiadne súrodenca, pretože je to koreň nášho stromu, a tam je vždy len 1 root. Na 7 majú súrodencov by muselo byť uzol nad 7. Tam by mal byť rodič 7, v takom prípade 7 by už byť koreňom stromu. Potom, že nová materská 7 by tiež mala mať dieťa, a že dieťa by potom byť súrodenec 7. 

Dobre. Ďalej. Keď sme začali náš rozhovor binárnych stromov, sme sa rozprávali o tom, ako sme chceli použiť na získať výhodu nad oboch poliach a vzájomne previazaných zoznamov. A spôsob, akým budeme robiť, že je s týmto usporiadanie majetku. Môžeme povedať, že binárny strom je nariadené, v súlade so špecifikáciou, ak pre každý uzol v našom stromu, všetky jeho potomkov vľavo - ľavej dieťa a všetky ľavej dieťa potomkov - majú menšie hodnoty, a všetky uzly na pravej strane - právo dieťa a všetky pravé dieťa potomkov - majú uzly väčšia ako hodnota aktuálneho uzla, ktorý sa práve pozeráte. Len pre jednoduchosť, budeme predpokladať, že tu nie sú žiadne duplicitné uzly v našom stromu. Napríklad, v tejto vetve nebudeme zaoberať sa prípadom kde majú hodnotu 7 pri koreni  a potom tiež majú hodnotu 7 inde vo stromu. V tomto prípade, všimnete si, že tento strom je naozaj nariadil. Máme hodnotu 7 v koreňovom adresári. Všetko na ľavej strane 7 - keď som späť všetky z týchto maličkých značiek tu - všetko vľavo 7 - 3 a 6 - tieto hodnoty sú obaja menej ako 7, a všetko vpravo - čo je presne to 9 - je väčšia ako 7. 

To však nie je jediným objednať strom obsahujúce tieto hodnoty, ale poďme tomu pár ďalších z nich. Tam je skutočne celá partia spôsobov, ako to môžeme urobiť. Budem používať tesnopis len aby to jednoduché, ak - skôr než preťahoval celé krabice-a šípy - Ja som jednoducho ísť kresliť čísla a pridajte šípky je spájajú. Ak chcete začať, jednoducho budeme písať naše pôvodné strom zase tam, kde sme mali 7, a potom 3, a potom 3 ukazuje smerom vpravo na 6, a 7 mal právo dieťaťa, ktoré bolo 9. Dobre. Čo je ďalší spôsob, ako by sme mohli napísať tento strom? Namiesto toho, aby 3 je vľavo dieťa 7, môžeme tiež 6 bude ľavá dieťa 7, a potom 3 musí byť na ľavej dieťaťom 6. To by vyzerať ako na tomto stromu priamo tu, kde mám 7, potom 6, potom 3, a 9 na pravej strane. My tiež nemusí mať 7 ako naše koreňového uzla. Mohli by sme tiež mať 6 ako náš koreňový uzol. Čo by to vyzerať? Ak budeme udržiavať túto objednanú vlastnosť, všetko vľavo od 6 musí byť menší než to. Je tu len jedna možnosť, a to 3. Ale potom ako pravé dieťa 6, máme dve možnosti. Po prvé, mohli by sme mať 7 a potom 9, alebo môžeme kresliť - ako by som chcel robiť tu - kde máme 9 ako pravé dieťa v 6, a potom sa 7 ako ľavé podriadený 9. 

Teraz, 7 a 6 nie sú jediné možné hodnoty pre koreň. Mohli by sme tiež 3 musí byť v koreňovom adresári. Čo sa stane, keď 3 je pri koreni? Tu, veci sa trochu zaujímavé. Tri nemá žiadne hodnoty, ktoré sú menšie ako to, tak, že celá ľavá strana stromu je len tak, že je nulový. Je tu nebude nič tam. Na pravej strane, mohli by sme uviesť veci vo vzostupnom poradí. Mohli by sme mať 3, potom 6, potom 7, potom 9. Alebo by sme to mohli urobiť 3, potom 6, potom 9, potom 7. Alebo by sme to mohli urobiť 3, potom 7, potom 6, potom 9. Alebo, 3, 7 - vlastne nie, nemôžeme urobiť 7 už. To je naša jediná vec tam. Môžeme to urobiť 9, a potom z 9 môžeme urobiť 6 a potom 7. Alebo, môžeme 3, potom 9, potom 7, a potom 6. 

Jedna vec je upozorniť na tu že tieto stromy sú trochu divný-pozerať. Najmä, ak sa pozrieme na 4 stromy na pravej strane - Budem obiehať je, tu - Tieto stromy vyzerajú takmer rovnako ako prepojeného zoznamu. Každý uzol má iba jedno dieťa, a tak nie je k dispozícii žiadny z tohto stromovej štruktúry, ktoré vidíme, napríklad,  v tejto jednej osamelý strom cez tu na ľavom dolnom rohu. Tieto stromy sú vlastne len degenerujú binárne stromy, a budeme hovoriť o nich viac v budúcnosti - najmä ak idete na prijať ďalšie kurzy informatiky. Tieto stromy sú degenerované. Sú to veľmi užitočné, pretože skutočne, táto štruktúra prepožičiava  k vyhľadávaniu časy podobné ako prepojeného zoznamu. Nechceme sa využiť extra pamäte - tento dodatočný ukazovateľ - pretože našej štruktúry je zlá týmto spôsobom. Skôr než ísť ďalej a upozorniť na binárne stromy, ktoré majú 9 pri koreni, ktorá je konečným prípad, že by mohol byť sme miesto, v tomto bode, bude hovoriť trochu o tomto iný termín že používame, keď hovoríme o stromoch, ktoré sa nazýva výška. 

Výška stromu je vzdialenosť od koreňa k najviac vzdialené uzla, alebo skôr počet chmeľu, ktoré by sa, aby sa za účelom začať od koreňa a potom skončí na najviac vzdialené uzla v strome. Ak sa pozrieme na niektoré z týchto stromov, ktoré sme vypracovali tu, môžeme vidieť, že ak budeme mať tento strom v ľavom hornom rohu a začneme na 3, potom musíme urobiť 1 hop sa dostať na 6, druhá hop sa dostať do 7, a tretia hop sa dostať do 9. Takže, výška tohto stromu je 3. Môžeme to urobiť rovnaký výkon pre ostatné stromy uvedených s týmto zeleným, a vidíme, že výška všetkých týchto stromov je tiež naozaj 3. To je súčasťou toho, čo robí je zvrhlík - , Že ich výška je len jeden menej ako je počet uzlov v celom stromu. Ak sa pozrieme na tento druhý strom, ktorý je obklopený s červenou, na strane druhej, vidíme, že najviac vzdialené koncové uzly sú 6 a 9 - listy, čo sú uzly, ktoré nemajú žiadne deti. Takže, aby sa dostal z koreňového uzla buď 6 alebo 9, musíme urobiť jednu hop sa dostať na 7 a potom druhé hop sa dostať do 9, a podobne, len druhý hop z 7 sa dostať k 6. Takže, výška tohto stromu sem je iba 2. Môžete sa vrátiť späť, a to pre všetky ostatné stromy, ktoré sme predtým diskutovali počínajúc 7 a 6, a zistíte, že výška všetkých týchto stromov je tiež 2. 

Dôvod, prečo sme hovorili o nariadené binárne stromy a prečo sú v pohode, je preto, že sa môžete preberať ne veľmi podobný spôsob vyhľadávania cez triedenom poli. To je miesto, kde budeme hovoriť o získanie že lepšie vyhľadávanie čas cez jednoduché prepojeného zoznamu. S prepojeného zoznamu - ak chcete nájsť konkrétny prvok - ste na najlepšie robiť nejaké lineárne hľadanie kde začať na začiatku zoznamu a hop jeden po jednom - jeden uzol jedným uzlom - celý zoznam, kým nenájdete, čo hľadáte. Vzhľadom k tomu, ak máte binárny strom, ktorý je uložený v tejto peknej formáte, môžete skutočne dostať viac binárneho vyhľadávania deje kde si rozdeľ a panuj a hľadanie cez zodpovedajúce polovici stromu na každom kroku. Poďme sa pozrieť, ako to funguje. 

Ak máme - opäť vracia do pôvodného stromu - začneme v 7, my máme 3 vľavo, 9 na pravej strane, a pod 3 máme 6. Ak chceme vyhľadať číslo 6 v tomto stromu, mali by sme začať u koreňa. Radi by sme tieto hodnoty sme hľadali, povedzme 6, na hodnotu uloženú v uzle, ktorý sme teraz pri pohľade na, 7, zistí, že 6 je naozaj menej ako 7, a tak sme si presunúť doľava. Ak je hodnota 6 bol vyšší ako 7, by sme sa namiesto toho sa pohyboval napravo. Vzhľadom k tomu, vieme, že - vzhľadom k štruktúre našej objednaného binárneho stromu - všetky hodnoty menšie ako 7 sa bude uložený vľavo 7, nie je potrebné, aby neobťažoval pohľade cez pravej strane stromu. Akonáhle sme sa presunúť doľava a my sme teraz v uzle obsahujúce 3, môžeme urobiť rovnakú porovnaniu zase tam, kde sme porovnať 3 a 6. A my zistíme, že zatiaľ čo 6 - hodnota, ktorú hľadáte - je väčší ako 3, môžeme ísť na pravej strane uzla, ktorá obsahuje 3. Nie je ľavá strana tu, takže sme mohli ignorovať, že. Ale my len vieme, že preto, že sa pozeráme na strom sám, a my môžeme vidieť, že strom nemá žiadne deti. 

Je tiež celkom ľahké sa pozrieť do 6 v tejto vetve, ak robíme to sami ako ľudia, ale poďme sledovať tento proces mechanicky ako počítač urobí naozaj pochopiť algoritmus. V tomto bode, sme teraz pozrieme na uzle, ktorý obsahuje 6, a hľadáme pre hodnotu 6, tak, naozaj, sme našli zodpovedajúce uzol. Našli sme hodnotu 6 v našom stromu, a môžeme zastaviť naše vyhľadávanie. V tomto bode, v závislosti na tom, čo sa deje, môžeme povedať, že áno, sme našli hodnotu 6, to je v našej stromu. Alebo, ak plánujeme vložiť uzol, alebo robiť niečo, môžeme robiť, že v tomto bode. 

Poďme urobiť pár ďalších vyhľadávania, len aby videl, ako to funguje. Poďme sa pozrieť na to, čo sa stane, keď sme boli vyskúšať a pozrieť sa na hodnotu 10. Ak by sme sa pozreli do hodnoty 10, my by sme začali pri koreni. Mali by sme vidieť, že 10 je väčšie ako 7, tak by sme presunie doprava. Mali by sme dostať na 9 a porovnajte 9 do 10 a uvidíte, že 9 je naozaj menej ako 10. Takže znova, tak sa snažíme presunúť doprava. Ale v tomto bode, mali by sme si všimnúť, že sme na null uzla. Tam nič nie je. Nie je nič, kde by mala byť 10. Toto je miesto, kde sa môže hlásiť zlyhanie -, že skutočne č 10 vo stromu. A konečne, poďme prejsť prípade sa snažíme vyhľadať 1 do stromu. To je podobné tomu, čo sa stane, keď sa pozrieme do 10, s výnimkou namiesto toho, aby práva, sme ísť doľava. Začneme na 7 a vidieť, že 1 je menšie ako 7, tak sa pohybovať doľava. Dostávame sa 3 a uvidíte, že 1 je menší ako 3, takže opäť sa snažíme presunúť doľava. V tomto bode máme null uzol, takže opäť môžeme hlásiť poruchu. 

Ak sa chcete dozvedieť viac o binárnych stromoch, existuje celá partia veselých malých problémov, ktoré môžete robiť s nimi. Navrhujem cvičiť kresbu z týchto diagramov jeden po druhom a po cez všetky jednotlivé kroky, pretože to príde super-praktický nielen, keď robíte kódovanie Huffmanova problém sadu ale aj v budúcich kurzov - len naučiť, ako čerpať z týchto dátových štruktúr a myslím, že cez problémy s pero a papier alebo, v tomto prípade, iPad a pero. 

V tomto bode hoci, budeme sa pohybovať na urobiť nejaké kódovanie praxi a skutočne si hrať s týmito binárnymi stromami a vidieť. Chystám sa prejsť späť na mojom počítači. Pre túto časť sekcie, namiesto použitia CS50 Spustiť alebo CS50 priestory, Budem používať spotrebič. 

Po spoločne so špecifikáciou problému Set, Vidím, že mám otvoriť spotrebič, ísť do môjho priečinka Dropbox, vytvorte priečinok s názvom § 7, a potom vytvoriť súbor s názvom binary_tree.c. Ideme na to. Mám spotrebič už otvorený. Idem vytiahnuť terminál. Chystám sa ísť do priečinka Dropbox, aby sa adresár s názvom section7, a vidieť, že je to úplne prázdny. Teraz idem otvoriť binary_tree.c. Dobre. Ideme - prázdny súbor. 

Vráťme sa špecifikácií. Špecifikácie žiada vytvorenie novej definícii typu pre binárne uzol stromu obsahuje int hodnoty - rovnako ako hodnoty, ktoré sme vypracovali v našej diagramov pred. Budeme používať tento štandardný text typedef, že sme urobili tu že by ste mali poznať z problémových Set 5 - ak ste hash tabuľky spôsob dobývania pravopisu programu. Mali by ste tiež uznať z minulého týždňa oddielu kde sme o tom hovorili v súvislosti zoznamoch. Máme to typedef struct z uzla, a my sme rovnako Táto štruktúra uzla tento názov struct uzol si vopred takže potom môžeme odkazovať sa na to, pretože budeme chcieť mať ukazovatele struct uzol ako súčasť našej struct, ale my sme potom obkľúčený to - alebo skôr, uzavretý toto - v typedef tak, že neskôr v kóde, možno odkázať na tento struct len ​​ako uzol namiesto struct uzol. 

To bude veľmi podobný single prepojené definície zoznamu, ktoré sme videli minulý týždeň. Ak to chcete, nech to jednoducho začať písať sa na štandardizovaný. Vieme, že musíme mať celočíselnú hodnotu, tak dáme do int hodnoty, a potom namiesto toho, aby len jeden ukazovateľ na ďalší prvok - ako sme to urobili s single viazaných zoznamov - budeme mať ľavej a pravej podriadené ukazovatele. To je docela jednoduchá tiež - struct node * ľavá dieťa; a struct uzol * P dieťa;. Cool. To vyzerá ako celkom dobrý začiatok. Vráťme sa špecifikácií. 

Teraz musíme deklarovať globálne premenné uzla * pre koreň stromu. Budeme robiť to globálne, rovnako ako sme urobili prvý ukazovateľ v našom prepojenom zozname aj globálne. To bolo tak, že vo funkciách, ktoré sme napísať nemáme držať prechádzanie okolo tohto koreňa - keď budeme vidieť, že ak si chcete napísať tieto funkcie rekurzívne, to by mohlo byť lepšie ani prejsť okolo ako globálny na prvom mieste a namiesto toho inicializovať ju lokálne vo vašom hlavnom funkcie. Ale urobíme to globálne začať. Opäť, dáme pár miest, a budem deklarovať uzla * koreň. Len aby sa ubezpečil, že nemám nechať tento inicializovaná, budem ju nastaviť rovná null. Teraz, v hlavnej funkcii - ktoré budeme písať naozaj rýchlo priamo tu - int main (int argc, char * ArGV []) - a ja začnem vyhlásením svoje ArGV pole ako const len ​​preto, že viem, že tieto argumenty sú argumenty, ktoré som asi nechcú meniť. Ak chcem zmeniť som im mala byť pravdepodobne robiť ich kópie. Uvidíte to veľa v kóde. To je v poriadku tak ako tak. Je to v poriadku nechať to ako - vynechať const, ak chcete. Aj typicky dať do len preto, že som si pripomínam  že som asi nechcem meniť tieto argumenty. 

Ako vždy, budem zahrnúť tento návratový 0 riadok na konci hlavnej. Tu budem inicializovať svoj koreňový uzol. Ako to stojí teraz, mám ukazovateľ, ktorý je nastavený na hodnotu null, tak to ukazuje na nič. Aby sa skutočne začať stavať uzol, Prvýkrát som potrebné alokovať pamäť pre neho. Ja budem robiť, že tým, že pamäť na halde pomocou malloc. Idem nastaviť koreň rovnajúcu sa výsledku malloc, a budem používať sizeof operátor vypočítať veľkosť uzla. Dôvod, prečo som použiť sizeof uzol na rozdiel od, povedzme, niečo také - malloc (4 + 4 +4) alebo malloc 12 - Je tomu tak preto chcem, aby môj kód, aby bolo kompatibilné, ako je to možné. Chcem byť schopný urobiť také. C súbor, skompilovať na zariadenia, a potom skompilovať na mojom 64-bit Mac - alebo na úplne inú architektúru - a chcem to všetko fungovať rovnako. 

Ak robím predpoklady o veľkosti premenných - veľkosť int alebo veľkosť ukazovateľ - potom som tiež robiť predpoklady o druhy architektúr na ktoré môj kód je možné úspešne skompilovať pri spustení. Vždy používajte sizeof na rozdiel od ručne súčet struct poľa. Ďalším dôvodom je to, že môže byť aj padding, že kompilátor dáva do struct. I len súčet jednotlivých polí nie je niečo, čo zvyčajne chcú urobiť, tak, odstráňte tento riadok. Teraz, naozaj inicializovať koreňový uzol, Budem musieť pripojiť hodnôt pre každú z jeho rôznych odborov. Napríklad pre hodnotu viem chcem inicializovať až 7, a teraz idem nastaviť doľava dieťa budú mať hodnotu null a právo dieťa tiež byť null. Výborne! Urobili sme, že časť špec. 

Špecifikácie sa v dolnej časti stránky 3 sa ma pýta, ak chcete vytvoriť ďalšie tri uzly - z ktorých jedna obsahuje 3, jeden obsahujúci 6, a jeden s 9 - a potom prepojte je tak, že vyzerá presne ako náš stromovom diagrame že sme hovorili o minulosti. Urobme to celkom rýchlo sem. Uvidíte naozaj rýchlo, že som začnem písať veľa duplicitných kódu. Idem vytvoriť uzla * a budem to nazývať tri. Idem nastaviť to rovnaké malloc (sizeof (uzol)). Idem nastaviť tri-> hodnota = 3. Tri -> left_child = NULL; tri -> P _child = NULL; rovnako. To vyzerá dosť podobne ako inicializáciu koreň, a to je presne to, čo Budem musieť robiť, keď začnem inicializáciu 6 a 9 rovnako. Urobím to naozaj rýchlo sem - vlastne, ja budem robiť trochu kopírovať a vložiť, a uistite sa, že som - v poriadku.  Teraz som dostal to kopírovať a môžem ísť ďalej a nastaviť rovná 6. Môžete vidieť, že to trvá chvíľu a nie je super-efektívne. V len trochu, budeme napísať funkciu, ktorá bude robiť to pre nás. Chcem nahradiť to s 9, nahradiť to s 6. 

Teraz máme všetky naše uzlov vytvorená a inicializovaná. Máme naše koreň položí rovné 7, alebo obsahujúce hodnotu 7, náš uzol obsahujúci 3, naše uzol obsahujúci 6, a naše uzol obsahujúci 9. V tomto bode, všetko, čo musíte urobiť, je drôt všetko až. Dôvod, prečo som inicializácii všetkých ukazovateľov na hodnotu null, je len preto, že som sa uistite, že Nemám žiadne neinicializovaný ukazovatele v tú náhodou. A tiež, pretože v tomto bode, som len skutočne pripojiť uzly navzájom - tým, že oni sú vlastne spojené s - nemám prejsť a urobiť či sú všetky nuly sú tam na príslušných miestach. 

Od koreňa, ja viem, že koreň ľavá dieťa 3. Ja viem, že koreň právo dieťa je 9. Potom, jediný ďalšie dieťa, ktoré som nechal robiť starosti je 3 právo dieťa, ktoré je 6. V tomto okamihu, to všetko vyzerá celkom dobre. Budeme odstrániť niektoré z týchto liniek. Teraz všetko vyzerá celkom dobre. Vráťme sa k nášmu špecifikácie a vidieť to, čo máme robiť ďalej. 

V tomto bode, musíme písať volané funkcie "obsahuje" s prototypom "bool obsahuje (int value)". A táto obsahuje funkcie bude vracať hodnotu true  ak strom poukázal na našej celosvetovej koreňovej premenné  obsahuje hodnotu odovzdaný do funkcie a false inak. Poďme ďalej a robiť, že. To bude presne ako pri vyhľadávaní, že sme sa po ruke na iPad len trochu pred. Poďme približovanie sa trochu a stlačte posúvacie tlačidlo nahor. Budeme dať túto funkciu priamo nad našou hlavnou funkciou takže nemáme robiť nejaký druh prototypovania. Takže, bool obsahuje (int value). Tam ideme. Tu je náš štandardný text vyhlásenia. Len aby sa ubezpečil, že to bude zostavovať, Chystám sa ísť dopredu a len nastaviť rovné vrátiť false. Práve teraz táto funkcia jednoducho nebude robiť nič a vždy hlási, že hodnota, ktorá hľadáme, nie je v strome. 

V tomto bode, je to asi dobrý nápad - pretože sme napísali veľa kódu a my sme sa ani nesnažili vyskúšanie - doteraz aby sa ubezpečil, že to všetko kompiluje. Existuje pár vecí, ktoré musíme urobiť, aby sa ubezpečil, že to bude skutočne kompilovať. Po prvé, či sme boli s použitím akýchkoľvek funkcií v žiadnej knižnice, ktoré sme doteraz neboli zahrnuté. Funkcie, ktoré sme používali doteraz, sú malloc, a potom sme tiež používali tento typ - tento neštandardný typ zvaný "bool '- ktorý je súčasťou štandardnej bool hlavičke súboru. Určite chceme, aby zahŕňala štandardné bool.h pre typu bool, a tiež chceme, aby # include štandardné lib.h pre štandardné knižnice ktoré zahŕňajú malloc, a bezplatné, a všetky, ktoré. Takže, oddialiť, ideme ukončiť. Poďme skúsiť a uistite sa, že to v skutočnosti robil kompilácie. Vidíme, že to robí, tak sme na správnej ceste. 

Poďme otvoriť binary_tree.c znova. Zhŕňa. Poďme dole a uistite sa, že vložíme niekoľko hovorov do nášho obsahuje funkcie - len aby sa ubezpečil, že je všetko v poriadku. Napríklad, keď sme robili nejaké vyhľadávanie v našom stromu skôr, sme sa snažili pozrieť do hodnoty 6, 10, a 1, a vedeli sme, že 6 je na strome, 10 nie je v strome, a 1 nebol vo stromu buď. Poďme použiť tieto ukážkovej volanie ako spôsob, ako zistiť, či alebo nie naše obsahuje funkcie pracuje. Aby k tomu, že, budem používať printf funkcie, a budeme vytlačiť výsledok volania obsahuje. Idem dať v reťazci "obsahuje (% d) = pretože  budeme typom hodnoty, ktoré budeme hľadať, a =% s \ n ", a použiť ho ako náš formátovacom reťazci. Sme len tak vidieť - doslova vytlačiť na obrazovke - čo vyzerá ako volanie funkcie. To nie je v skutočnosti volanie funkcie.  To je len reťazec navrhnutý tak, aby vyzeral ako volanie funkcie. 

Teraz, budeme pripojiť hodnôt. Budeme sa snažiť obsahuje na 6, a potom to, čo budeme robiť, je tu použiť tento trojica operátor. Poďme sa pozrieť - obsahuje 6 - tak, teraz som obsahoval 6, a ak obsahuje 6 je pravda, reťazec, ktorý budeme posielať na% s formátu charakteru bude reťazec "true". Poďme prejdite trochu. Inak, chceme poslať reťazec "false", ak obsahuje 6 vráti False. To je malý praštěná vyzerajúce, ale podľa mňa by som mohol tiež ilustrujú čo ternárnu operátor vyzerá, pretože sme ho ešte nevideli na chvíľu. To bude pekný, šikovný spôsob, ako zistiť, či naše obsahuje funkcie pracuje. Idem listovať nad vľavo, a budem kopírovať a vložiť tento riadok niekoľkokrát. To zmenilo niektoré z týchto hodnôt okolo, takže to bude 1, a to bude 10. 

Na tomto mieste sme dostali peknú obsahuje funkcie. Máme nejaké testy, a uvidíme, či to všetko funguje. V tomto bode sme napísali niektoré ďalšie kód. Čas ukončenia, a uistite sa, že všetko, čo ešte kompiluje. Ukončite von, a teraz poďme skúsiť robiť binárne strom znova. No, vyzerá to, že máme chybu, a my sme dostali to výslovne prehlasuje knižnice funkciu printf. Vyzerá to, že musíme ísť a # include standardio.h. A s tým, všetko by malo zostaviť. Sme v pohode. Teraz sa poďme skúsiť spustiť binárny strom a uvidíme, čo sa stane. Tu sme,. / Binary_tree, a vidíme, že, ako sme očakávali - pretože sme nie je implementovaná obsahuje ešte, alebo skôr, že sme len dať na oplátku falošné - vidíme, že je to len vracia false pre všetky z nich, tak to je všetko pracuje z väčšej časti veľmi dobre. 

Poďme späť a skutočne vykonávať obsahuje v tomto bode. Chystám sa posunúť dole, približovať, a - Pamätajte si, že algoritmus, ktorý sme použili je, že sme začali na koreňový uzol a potom v každom uzle, ktorý stretávame, robíme porovnanie, a na základe tohto porovnania sa buď presunúť na ľavú dieťaťa alebo pravej dieťa. To bude vyzerať veľmi podobne ako kód binárne vyhľadávanie, ktoré sme napísali skôr v termíne. Keď začneme, vieme, že chceme držať na aktuálne uzol že sa pozeráme na, a je aktuálne uzol sa bude inicializovaný na koreňový uzol. A teraz, budeme pokračovať cez strom, a pamätajte, že naše zastavenie podmienku -  keď my vlastne pracovali na príklade ručne - bolo, keď sme sa stretli s null uzol, nie, keď sme sa pozerali na null dieťa, ale keď sa v skutočnosti presunuté do uzla v strome a zistil, že sme na null uzla. Budeme opakovať, ako teraz nie je rovné null. A čo budeme robiť? Budeme testovať, či (teraz -> hodnota == hodnota), potom vieme, že sme skutočne našli uzol, ktorý sme hľadali. Tak tu sa môžeme vrátiť true. Inak, my chceme vidieť, či je hodnota nižšia ako hodnota. Ak je aktuálna uzol je hodnota nižšia ako hodnota, ktorú hľadáme, budeme pohybovať doprava. Takže, teraz = teraz -> right_child, a inak, budeme sa pohybovať doľava. cur = cur -> left_child;. Celkom jednoduché. 

Pravdepodobne ste rozpoznať slučku, ktorá vyzerá veľmi podobne, ako táto z binárne vyhľadávacie predtým v termíne, s výnimkou potom sme sa zaoberali s nízkou, strednou a vysokou. Tu, práve sme sa pozrieť na súčasnej hodnote, tak je to pekný a jednoduchý. Poďme uistite sa, že tento kód funguje. Najprv sa uistite, že zostavuje. Vyzerá to, že to robí. Poďme skúste ju spustiť. A skutočne, že vypíše všetko, čo sme očakávali. To nájde 6 v strome, nenájde 10, pretože 10 nie je v strome, a nenájde 1 buď preto, že 1 to tiež nie je v strome. Vychytávky na stiahnutie. 

Dobre. Vráťme sa k nášmu špecifikácie a uvidíme, čo bude ďalej. Teraz sa chce pridať niektoré ďalšie uzly do nášho stromu. To chce pridať 5, 2, a 8, a uistite sa, že naše obsahuje kód stále funguje podľa očakávania. Poďme urobiť. V tomto bode, skôr než robiť, že nepríjemné kopírovať a vložiť znova, poďme napísať funkciu skutočne vytvoriť uzol. Ak by sme posunúť dole celú cestu k hlavnému, vidíme, že sme robili to veľmi podobný kód znovu a znovu zakaždým, keď chceme vytvoriť uzol. 

Poďme napísať funkciu, ktorá bude skutočne stavať na uzol pre nás a vrátiť ho. Idem volať to build_node. Chystám sa stavať uzol s konkrétnu hodnotu. Priblížte tu. Prvá vec, ktorú budem robiť, je skutočne vytvoriť priestor pre uzol na haldy. Takže, uzol * n = malloc (sizeof (node)), n -> hodnota = hodnota; a potom je tu, Ja som jednoducho ísť k inicializácii všetkých oblastiach sa príslušné hodnoty. A na samom konci, vrátime naše uzol. Dobre. Jedna vec k poznámke je, že túto funkciu priamo tu bude vracať ukazovateľ do pamäte, ktorá bola haldy pridelená. Čo je pekné na tom je, že tento uzol teraz - musíme vyhlásiť ju na hromadu, pretože ak sme deklarovali ju na zásobník by sme neboli schopní to urobiť v tejto funkcii, ako je táto. Že pamäť by ísť mimo rozsah a bolo by neplatné, ak sme sa snažili pristupovať k nej neskôr. Pretože sme sa prehlasuje haldy pridelené pamäte, budeme musieť postarať o uvoľnenie neskôr pre náš program nie je úniku nejakú spomienku. Boli sme plaviť sa na to pre všetko ostatné v kóde Len pre jednoduchosť v tej dobe, ale ak ste niekedy napísať funkciu, ktorá vyzerá takto kde máš - niektorí hovoria, že malloc alebo realloc vnútri - Chcete, aby sa ubezpečil, že ste dal nejaký komentár sem, že hovorí, hej, vieš, vráti haldy pridelených uzol inicializovaný s odovzdaný v hodnote. A potom chcete, aby sa ubezpečil, že ste vložili do nejakej poznámky, ktoré hovorí, že volajúci musí uvoľniť vrátenej pamäte. Tak, keď sa niekto niekedy ide a používa túto funkciu, vedia, že všetko, čo sa vrátime z tejto funkcie v určitom okamihu bude musieť byť prepustený. 

Za predpokladu, že je všetko v poriadku a tu dobre, môžeme ísť dole do nášho kódu a nahradiť všetky tieto riadky tu s volaním našej funkcie uzla zostavenie. Poďme urobiť naozaj rýchlo. Jedna časť, ktorá nebudeme nahradiť je táto časť dole na dne, kde sa v skutočnosti drôt uzly poukázať na sebe, pretože to nemôžeme urobiť v našej funkcii. Ale poďme urobiť root = build_node (7); uzol * tri = build_node (3); uzol * Šesť = build_node (6); uzol * Deväť = build_node (9);. A teraz, sme tiež chceli pridať uzly pre - Uzol * päť = build_node (5); uzol * osem = build_node (8); a čo bola tá druhá uzol? Poďme sa pozrieť, tu. Chceli sme tiež pridať 2 - Uzol * dve = build_node (2);. Dobre. V tomto bode, vieme, že sme dostali 7, 3, 9, a 6 všetky zapojený správne, ale čo o 5, 8, a 2? Aby bolo všetko v správnom poradí, vieme, že tri právo dieťa je 6. Takže, ak budeme pridať 5, s 5 tiež patrí do pravej strane stromu, z ktorých 3 je koreňom, tak 5 patrí ako ľavé dieťa 6. Môžeme to urobiť tým, že hovorí, šesť -> left_child = päť; a potom 8 patria ako ľavý dieťa 9, tak deväť -> left_child = osem; a potom 2 je ľavý dieťa 3, takže môžeme urobiť, že sem - teba -> left_child = dva;. Ak ste tak celkom sledovať spolu s tým, navrhujem, aby ste nakresliť to sami. 

Dobre. Poďme zachrániť to. Poďme von a uistite sa, že zostavuje, a potom môžeme pridať v našom obsahuje volanie. Vyzerá ako všetko, čo ešte kompiluje. Poďme a pridať v niektorých obsahuje volanie. Opäť, budem robiť trochu kopírovanie a vkladanie. Teraz poďme hľadať 5, 8, a 2. Dobre. Poďme sa uistite, že to všetko vyzerá dobre ešte. Výborne! Uložiť a ukončite. Teraz poďme urobiť, kompilovať, a teraz poďme bežať. Z výsledkov, vyzerá to, že všetko funguje len pekné a dobre. Výborne! Takže teraz máme naše obsahuje funkcie písaný. Poďme ďalej a začať pracovať na tom, ako vložiť uzlov do stromu pretože, ako to robíme teraz, veci nie sú moc pekná. 

Ak sa vrátime do špecifikácie, to nás žiada, aby sme napísať funkciu nazvanú vloženia - opäť vracia bool o otázku, či alebo nie by sme mohli skutočne vložiť uzol do stromu - a potom je hodnota vložiť do stromu je špecifikovaná ako jediným argumentom našej vlož funkciu. Budeme vráti true, ak by sme mohli skutočne vložiť uzla obsahujúce hodnotu do stromu, , Čo znamená, že sa jeden, mal dostatok pamäte, a potom dva, že uzol nebol už existujú vo stromu od - Pamätajte si, že sa nebudeme mať duplicitné hodnoty v strome, len aby to jednoduché. Dobre. Späť do kódu. Otvorte ju. Zväčšiť trochu, posuňte zobrazenie dolu. Poďme dať vložte funkciu priamo nad obsahuje. Opäť, to bude nazývaný bool vložka (int value). Dajte mu trochu viac priestoru, a potom, ako predvolené, poďme dať na oplátku falošné na samom konci. Teraz sa na dne, poďme do toho a namiesto ručne budovanie uzly v hlavnom sami a zapojenie je až do bodu k sebe, ako to robíme, budeme spoliehať na naše vlož funkciu k tomu, že. Nebudeme sa spoliehať na našom vlož funkciu postaviť celý strom od nuly ešte nie, ale budeme sa zbaviť týchto riadkov - Dáme komentár, tieto riadky - ktoré budú vychádzať uzly 5, 8, a 2. A namiesto toho, budeme vložiť volania do nášho vlož funkciu aby sa ubezpečil, že skutočne funguje. Ideme na to. 

Teraz sme komentármi týchto riadkov. Máme len 7, 3, 9, a 6 v našom stromu v tomto bode. Uistite sa, že je to všetko funguje, môžeme oddialiť, aby naše binárne strom, spustite ho, a my môžeme vidieť, že obsahuje je teraz nám hovorí, že sme úplne pravdu - 5, 8, a 2 sú už v strome. Choďte späť do kódu, a ako sa budeme vložiť? Spomeňte si, čo sme robili, keď sme boli vlastne vloženie 5, 8, a 2 skôr. Hrali sme túto hru plienky, kde sme začali pri koreni, šiel stromu jeden po jeden po druhom kým sme nenašli zodpovedajúce medzeru, a potom sa zapojený v uzle na príslušné miesto. Chystáme sa urobiť to isté. To je v podstate ako písanie kódu, ktorý sme použili v obsahuje funkcie nájsť miesto, kde má byť uzol, a potom sme len tak vložiť uzol tu. Poďme začať robiť, že. 

Takže máme uzol * teraz = root, budeme len tak nasledovať obsahuje kód kým nezistíme, že to nie je úplne pracovať pre nás. Budeme prechádzať stromu, zatiaľ čo aktuálny prvok nie je null, a ak zistíme, že teraz je hodnota rovná hodnote, že sa snažíme vložiť - dobre, to je jeden z prípadov, v ktorých sme nemohli skutočne vložiť uzol do stromu, pretože to znamená, že máme duplicitné hodnotu. Tu sme vlastne bude vracať false. Teraz, inak ak CUR je hodnota nižšia ako hodnota, Teraz vieme, že sa presunieme do pravej  pretože hodnota patrí v pravej polovici cur stromu. Inak budeme pohybovať doľava. To je v podstate naša obsahuje funkcie priamo tam. 

V tomto bode, akonáhle sme dokončili tento while, náš teraz ukazovateľ sa bude ukazovať na nulu v prípade, že funkcia nie je už vrátila. Máme preto mať CUR na mieste, kde chceme vložiť nový uzol. Čo je ešte potrebné urobiť, je skutočne stavať nový uzol, ktoré môžeme urobiť celkom ľahko. Môžeme použiť naše super-praktický zostavenie uzla funkciu, a niečo, čo sme neurobili skôr - sme tak nejako brali za samozrejmosť, ale teraz budeme robiť, len aby sa ubezpečil - budeme testovať, aby ubezpečil, že hodnota vrátená nový uzol bol vlastne nie je null, pretože nechceme začať prístupu k tejto pamäte, ak je null. Môžeme testovať, aby sa ubezpečil, že nový uzol nie je rovné null. Alebo miesto, môžeme len zistiť, či to vlastne je null, a ak je null, potom sa môžeme len vrátiť false čoskoro. 

V tomto bode, musíme zapojiť nový uzol do jeho príslušné miesto v strome. Ak sa pozrieme späť na hlavnú a kde sme boli vlastne kabeláž hodnoty pred, vidíme, že spôsob, akým sme to robili, keď sme chceli dať 3 vo stromu bola sme vstúpili do ľavej dieťa koreňa. Keď dáme 9 do stromu, sme mali prístup k správnej dieťa koreňa. Mali mať ukazovateľ na materskej aby dal nové hodnoty do stromu. Rolovanie späť vložiť, že to nebude úplne fungovať tu pretože nemáme nadradené ukazovateľ. Čo chceme byť schopní urobiť, je, v tomto bode, zistiť hodnotu rodičia a vidieť - dobre, sakra, ak rodičia hodnota je nižšia ako aktuálna hodnota, potom materského právo dieťa by mal byť nový uzol; inak by sa rodičia ľavá dieťa bude nový uzol. Ale nemáme tento materský ukazovateľ ešte dosť. 

S cieľom získať to, sme v skutočnosti bude musieť sledovať to, ako sme ísť cez strom a nájsť vhodné miesto v našom slučke vyššie. Môžeme to urobiť, že prechodom späť na začiatok nášho vlož funkcie a sledovanie iného premennú ukazovatele volal rodičia. Budeme ju nastaviť rovná null spočiatku, a potom zakaždým, keď ideme cez strom, budeme nastaviť nadradené ukazovateľ tak, aby zodpovedala aktuálnej ukazovateľ. Nastaviť rodičia rovnajúcu sa súčas. Týmto spôsobom, zakaždým, keď prechádzame, budeme na zabezpečenie toho, súčasný ukazovateľ dostane zvýšený materská ukazovateľ sleduje ju - len o jeden stupeň vyššia, než je aktuálna ukazovateľ vo stromu. To všetko vyzerá veľmi dobre. 

Myslím, že jedna vec, ktorú budete chcieť upraviť, je tento build uzla vracia null. S cieľom získať stavať uzol skutočne úspešne vrátiť null, budeme musieť upraviť tento kód, pretože tu sme nikdy testované, aby sa ubezpečil, že malloc vracia platný ukazovateľ. Takže, ak (n = NULL!), Pak - ak malloc vracia platný ukazovateľ, potom budeme ju inicializovať; inak budeme len vracať, a že skončí vracia hodnotu null pre nás. Teraz všetko vyzerá celkom dobre. Poďme uistite sa, že to v skutočnosti zostavuje. Urobte binárne strom, a oh, máme nejaké veci tu deje. 

Máme implicitné vyhlásenie funkcií stavať uzol. Opäť, s týmito kompilátory, budeme začať na vrchole. Čo to musí znamenať, že volám stavať uzol než som vlastne deklaroval to. Vráťme sa ku kódu naozaj rýchlo. Prejdite nadol, a naozaj, je vyhlásený za moje vložka funkcie nad uzla zostavenie funkcie, ale ja sa snažím používať zostavenie uzla vo vnútri vložky. Chystám sa ísť a kópie - a potom vložte uzla zostavenie funkčnej až sem na vrchole. Tak, dúfam, že bude fungovať. Dajme to iného ísť. Teraz to všetko kompiluje. Všetko je dobré. 

Ale v tomto bode, sme v skutočnosti len naša vložte funkciu. Vieme len, že to prekladá, tak poďme dovnútra a dať nejaké hovory dovnútra Poďme urobiť, že v našej hlavnej funkcie. Tu sme sa v komentári 5, 8 a 2, a potom sme nemali prepojte je hore dole sem. Poďme urobiť niektoré hovory vložiť, a poďme tiež použiť rovnaký druh vecí, ktoré sme použili keď sme sa tieto printf volanie, aby sa ubezpečil, že všetko sa dostať správne vložená. Idem kopírovať a vložiť, a miesto obsahuje budeme robiť vložku. A miesto 6, 10, a 1, budeme používať 5, 8, a 2. To by snáď vložiť 5, 8, a 2 do stromu. Kompilácie. Všetko je dobré. Teraz budeme vlastne beží náš program. 

Všetko sa vrátil false. Takže, 5, 8, a 2 nešiel, a vyzerá to, že obsahuje nenašiel ani. Čo sa deje? Poďme oddialiť. Prvým problémom bolo, že vložka sa zdalo vrátiť false, a vyzerá to, že je to preto, že sme opustili v našej spiatočnej falošné volanie, a nikdy sme vlastne vrátil pravda. Môžeme nastaviť, aby sa. Druhým problémom je, teraz, aj keď sme to - uložte tento, ukončite to, príkazom make znovu, že to skompilovať, spustite ho - vidíme, že niečo iné sa tu stalo. The 5, 8, a 2 boli ešte nikdy nájdené v strome. Takže, čo sa deje? 

Poďme sa pozrieť na to v kóde. Poďme sa pozrieť, či sa nám podarí to vyriešiť. Začneme s materskou nie je null. Sme chcete nastaviť aktuálnu ukazovateľ vo výške do koreňového ukazovateľ, a budeme pracovať našu cestu dole cez strom. Ak je aktuálny uzol nie je null, potom vieme, že sa môže pohybovať dole trochu. My sme nastavili nadradené ukazovateľ sa rovná aktuálnej ukazovateľ, skontrolovať hodnotu - v prípade, že hodnoty sú rovnaké sme sa vrátili false. Ak sú hodnoty menej sme sa pohyboval napravo; inak, sme sa presunuli doľava. Potom sme vybudovať uzol. Budem priblížiť trochu. A tu, budeme sa snažiť zapojiť do hodnoty byť rovnaký. Čo sa deje? Poďme sa pozrieť, keď možno Valgrind nám môže dať nápovedu. 

Rád používam Valgrind len preto, že Valgrind naozaj rýchlo beží a povie vám, či existujú nejaké chyby pamäte. Keď sme sa spustiť Valgrind na kód, ako môžete vidieť priamo here--Valgrind./binary_tree--and hit Enter. Môžete vidieť, že sme nemali žiadnu chybu pamäte, takže to vyzerá, že je všetko v poriadku tak ďaleko. Máme nejaké úniky pamäte, ktorá poznáme, pretože nie sme deje sa uvoľniť niektorý z našich uzlov. Skúsme beží GDB vidieť, čo sa vlastne deje. Urobíme gdb. / Binary_tree. Je zavedený až v pohode. Poďme nastaviť bod zlomu na vložky. Poďme bežať. Vyzerá to, že vlastne nikdy volal vložka. Vyzerá to, že problém bol len, že keď som zmenil sem v hlavnom - všetky tieto printf volaní z obsahuje - Nikdy som vlastne zmenil nich volať vložky. Teraz poďme to skúsiť. Poďme kompiláciu. Všetky vyzerá dobre tam. Teraz sa poďme skúsiť spustiť to, čo sa stane. Dobre! Všetko vyzerá celkom dobré. 

Posledná vec myslieť, je, existujú nejaké ostrie prípady, na tejto vložky? A ukázalo sa, že, no, jedna hrana prípad, ktorý je vždy zaujímavé premýšľať o tom, je, čo sa stane, keď váš strom je prázdna a volať túto funkciu VLOŽENIE? Bude to fungovať? Dobre, poďme to skúsiť. - Binary_tree c - Spôsob, akým budeme tento test je, že budeme chodiť do našej hlavnú funkciu, a skôr než vedenie týchto uzlov takhle, sme len tak zakomentovat celú vec, a namiesto toho, aby vedenie až uzly vlastnými silami, môžeme skutočne jednoducho ísť dopredu a odstráňte všetko. Budeme robiť všetko volanie vložiť. Takže, poďme urobiť - miesto 5, 8, a 2, budeme vložiť 7, 3 a 9. A potom budeme tiež chcieť vložiť 6 rovnako. Uložiť. Ukončite. Urobte binárne strom. To všetko kompiluje. Môžeme len spustiť tak ako je a uvidíme, čo sa stane, ale je to tiež bude veľmi dôležité, aby sa ubezpečil, že nemáme žiadne chyby pamäti, pretože to je jeden z našich okrajových prípadov, ktoré sme poznať. 

Poďme sa uistiť, že to funguje dobre pod Valgrind, ktoré budeme robiť, tým práve beží Valgrind. / binary_tree. Vyzerá to, že skutočne majú jednu chybu z jedného kontextu - máme túto chybu. Čo sa stalo? Valgrind vlastne nám hovorí, kde to je. Oddialenie trochu. Vyzerá to, že sa to deje v našej vložiť funkciu, kde máme neplatný čítanie o veľkosti 4 na vložky, linka 60. Poďme sa vrátiť späť a zistiť, čo sa tu deje. Oddialenie naozaj rýchlo. Chcem sa uistiť, že to nie je na okraj obrazovky, takže môžeme vidieť všetko. Vytiahnuť, že v trochu. Dobre. Prejdite nadol, a problém je tu. Čo sa stane, keď sa dostaneme dole a naše aktuálne uzol je už null, naša materská uzol je null, takže ak sa pozrieme sa na samom vrchole, tu - v prípade, že while nikdy vykoná pretože naša súčasná hodnota je null - náš koreň je null, takže teraz je null - potom naša materská nikdy nedostane nastavená na súčas alebo na platnú hodnotu, tak, bude rodič zároveň mať hodnotu null. Musíme mať na pamäti, pre kontrolu, že v čase, keď sme sa sem dolu, a začneme prístup na hodnotu rodičia. Takže, čo sa stane? No, ak rodič je null - if (rodič == NULL) - potom vieme, že tam nesmie byť nič v strome. Musíme sa snažiť vložiť pri koreni. My môže vykonať tak, že iba nastavenie koreň rovnajúcu sa nový uzol. Potom v tomto bode, nemáme vlastne chceme ísť cez tieto iné. Namiesto toho, tu, môžeme urobiť buď inde-if-else, alebo môžeme spojiť všetko, čo sa tu v iný, ale tu budeme len používať iný, a to týmto spôsobom. Teraz, budeme testovať, aby ubezpečil, že naša materská nie je null do tej doby vlastne snaží prístup k jeho pole. To nám pomôže vyhnúť sa Segmentation fault. Takže, sme prestať, oddialiť, skompilovať, spustiť. 

Žiadne chyby, ale máme pred sebou ešte veľa úniky pamäte pretože sme nemali uvoľniť niektorý z našich uzlov. Ale, keď ideme sem a my sa pozrieť na našu výtlačok, vidíme, že dobre, vyzerá rovnako ako všetky naše vložiek bolo vracia hodnotu true, čo je dobré. Vložky sú všetky pravdivé, a potom príslušné obsahuje volanie platí tiež. 

Dobrá práce! Vyzerá to, že sme úspešne zapísaný vložku. To je všetko, čo máme pre tento týždeň Špecifikácia problému Set. Jedna zábavná výzva premýšľať o tom, ako by ste vlastne ísť a bez všetkých uzlov v tomto stromu. Môžeme tak urobiť množstvo rôznych spôsobov, ale nechám, že na vás experimentovať, a ako zábavu výzvu, vyskúšať a uistite sa, že si môžete byť istí že táto správa Valgrind Neboli nájdené žiadne chyby a žiadne úniky. 

Veľa šťastia na tento týždeň Huffman kódovanie problému nastavenia, a uvidíme sa budúci týždeň! [CS50.TV]