[Powered by Google Translate] [§ 7] [Vähem Mugav] [Nate Hardison] [Harvardi Ülikool] [See on CS50.] [CS50.TV] 

Tere tulemast 7. jagu. Tänu orkaani Sandy, selle asemel tavaline osa sel nädalal me teeme seda läbikäidav, läbi osa küsimustele. Ma lähen pärast koos Ülesanded 6 spetsifikatsiooniga, ja läbimas kõik küsimused Osas Küsimuste osa. Kui on mingeid küsimusi, palun kirjuta need edasi CS50 arutada. 

Olgu. Alustuseks. Just nüüd ma vaatan, lk 3 Ülesanded spetsifikatsioon. Me läheme esimese hakata rääkima kahendpuuks kuna need on palju tähtsust sel nädalal lahendamist - Huffman Tree kodeeringus. Üks esimesi andmestruktuurid me rääkisime edasi CS50 oli massiiv. Pea meeles, et massiiv on jada elemendid - kõik sama tüüpi - salvestatud õige üksteise kõrval mällu. Kui mul on täisarv massiivis, et saan juhtida kasutades seda kastid-numbrid-täisarvud stiil - Oletame, et mul on 5 esimeses kastis, mul on 7 teiseks siis on mul 8, 10 ja 20 viimases kasti. Pea meeles, et need kaks väga häid asju selle massiivi on, et meil on see pidev tööajaga juurdepääsu mõni konkreetne element  aastal massiivi kui me teame oma indeks. Näiteks kui ma tahan haarata kolmas element massiivi - kell indeks 2 kasutades meie nullpõhise indekseerimise süsteemi - Ma sõna otseses mõttes lihtsalt teha lihtne matemaatiline arvutus, hop selle positsiooni massiiv, tõmmake 8, ladustatakse seal, ja ma olen hea minna. 

Üks halbu asju selle massiivi - et me rääkisime kui me arutasime seotud loetelud - on see, et kui ma tahan lisada element selle massiivi Ma lähen tegema mõned vahepeal liigutada. Näiteks see massiiv siin on järjestatud järjekorras - sortida tõusvas järjestuses - 5, siis 7, siis 8, siis 10 ja siis 20 - aga kui ma tahan lisada number 9 sinna massiivi Ma pean minema mõned elemendid, et teha ruumi. Saame selle siin. Ma pean liikuma 5, 7, ja siis 8; luua lõhe, kus ma saan panna 9, ja siis 10 ja 20 ei saa minna paremale 9. See on selline valu, sest halvimal juhul - kui meil oli lisada kas alguses või lõpus massiiv, sõltuvalt sellest, kuidas me minnes - me võiksime lõpuks võttes suunata kõik elemendid et me praegu hoidmiseks massiivi. 

Niisiis, milline oli võimalus seda? Teistpidi oli see, et minna meie viidatumad nimekirja meetod, kus - asemel ladustamiseks elemendid 5, 7, 8, 10 ja 20 kõik üksteise kõrval mälu - mida me selle asemel tegi, oli hoida neid omamoodi kus iganes me tahame hoida neid nendes viidatumad nimekirja tippu, mida ma joonistan siia, selline ad hoc. Ja siis me ühendatud neid koos kasutades neid järgmisel lähtekohtadeks. Võin olla osuti 5 kuni 7, pointer alates 7 kuni 8, pointer alates 8 kuni 10, ja lõpuks, pointer alates 10 kuni 20, ja siis null pointer 20. viitab sellele, et seal on midagi vasakule. Kompromiss, mis meil siin on see, et nüüd, kui me tahame, et sisestada number 9 meie järjestatud nimekirja, kõik me peame tegema, on luua uus sõlm 9, traat see üles märkida sobiv koht, ja siis uuesti juhe 8 punkti alla 9. See on päris kiire, eeldades, me teame täpselt, kus me tahame lisada 9. Aga kompromiss vastutasuks on see, et oleme nüüd kadunud pidev tööajaga juurdepääsu et mõni konkreetne element meie andmestruktuur. Näiteks kui ma tahan leida neljanda elemendi käesolevas seotud nimekirja, Ma pean alustama alguses nimekirja ja töö mu teed läbi lugedes sõlme kaupa sõlme kuni leian neljas. 

Selleks, et saada parem juurdepääs jõudlust kui lingitud nimekiri - kuid säilitavad ka mõningaid eeliseid, et meil oli poolest sisestamise aja alates lingitud nimekiri - kahendpuu läheb vaja kasutada natuke rohkem mälu. Eelkõige asemel lihtsalt võttes kursorit kahendpuu tipp - nagu investeerimisriskiga-list sõlme ei - me kavatseme lisada teine ​​kursor kahendpuu sõlme. Selle asemel, et lihtsalt võttes kursor järgmisele element, me lähed on kursor vasakule laps ja õigus lapse. 

Joonistame pildil, et näha, milline see tegelikult välja näeb. Jällegi, ma lähen kasutada neid karpe ja nooled. Kahendpuu tipp alustad lihtsalt kast. See saab olema ruumi väärtus, ja siis see ka läheb on ruumi vasakul laps ja õigus lapse. Ma lähen märgistama siin. Me läheme pea vasakule laps, ja siis me lähed on õigus laps. Seal on palju erinevaid viise. Mõnikord ruumi ja mugavuse Ma tegelikult joonistada nagu ma siin teen alt kus ma lähen on väärtus ülaosas, ja siis õige laps põhjale paremas, ja vasakule lapse alt vasakule. Tulles tagasi selle ülemine diagramm meil väärtus tipus, siis on meil vasaku laps pointer, ja siis on meil õigus-lapse pointer. 

Aastal Ülesanded spetsifikatsioon, me räägime joonistus sõlme, mis on väärtus 7, ja siis vasakule ja lapse osuti, mis on null, ja õigus-lapse osuti, mis on null. Me võime kirjutada kapitali NULL ruumis jaoks nii vasak laps ja õigus lapse või saame teha seda diagonaal kaldkriipsuga kaudu iga kastid näitavad, et see on null. Ma lähen tegema, et lihtsalt sellepärast, et on lihtsam. Mida sa näed siin on kaks võimalust skeemide väga lihtne kahendpuu sõlme kus meil on väärtus 7 ja null laps suunanäitajaks. 

Teine osa meie spetsifikatsioon räägib, kuidas koos seotud loetelud - Pea meeles, et meil oli ainult kinni hoida kõige esimene element nimekirja meeles pidada kogu nimekiri - ja samamoodi koos kahendpuu, meil on ainult kinni hoida ühte kursorit puu et säilitada kontrolli kogu andmestruktuuri. See spetsiaalne element puu nimetatakse root node puu. Näiteks kui üks sõlm - see sõlm sisaldab Maksumus 7 koos null vasakul ja paremal laps suunanäitajaks - olid ainult väärtus meie puu, siis see oleks meie juurest sõlme. See on algusest peale meie puu. Me näeme seda veidi selgemalt kui me alustada lisades rohkem sõlmede meie puu. Las ma tõmba uus lehekülg. 

Nüüd me ei kavatse teha puu, mis on 7 keskmes, ja 3 sees vasakul laps, ja 9 seest õigus laps. Jällegi, see on üsna lihtne. Meil 7, joonistada sõlm 3, sõlm 9, ja ma lähen seatud vasak-lapse osuti 7. osutada sõlm sisaldab 3, ja õigus-lapse pointer sõlme sisaldavad 7 sõlme sisaldab 9. Nüüd, kuna 3 ja 9 ei ole ka lapsi, me ei kavatse seada kõik oma lapse suunanäitajaks olla null. Siin just meie puu vastab sõlme sisaldav number 7. Te näete, et kui kõik meil on viit, et root node, saame siis kõndida läbi meie puu-ja juurdepääsu nii tütartippu - nii 3 ja 9. Pole vaja säilitada viiteid iga sõlme puul. Olgu. Nüüd me ei kavatse lisada veel sõlme sellele diagramm. Me läheme lisada sõlm sisaldab 6 ja me kavatseme lisada see nagu õige laps sõlm sisaldab 3. Selleks, et ma lähen kustutan selle null pointer 3-sõlme ja traat see üles osutada sõlm sisaldab 6. Olgu. 

Sel hetkel, lähme üle natuke terminoloogia. Et alustada, põhjusel, et seda nimetatakse kahendpuu eriti on see, et tal on kaks last suunanäitajaks. Seal on muud liiki puid, mis on rohkem lapse suunanäitajaks. Eelkõige sa tegid "proovida" on Ülesanded nr 5. Märkad, et sellisel proovida, siis tuli 27 erinevat viiteid erinevatele lastele - üks iga 26 tähte inglise tähestik, ja siis 27. kohta ülakoma - nii, mis on sarnane puuliik. Aga siin, sest see on binaarne, meil on ainult kaks last suunanäitajaks. 

Lisaks sellele Juursõlme et me rääkisime, Samuti oleme viskamine selle ümber mõiste "laps". Mis see tähendab ühe sõlme olla laps teise sõlme? Ta sõna otseses mõttes tähendab, et laps sõlm on laps teise sõlme kui see teine ​​sõlm on üks tema laps vihjeid seatud osutavad, et sõlme. Plaanide elluviimiseks Konkreetsemalt öeldes kui 3 osutas ühe lapse suunanäitajaks, 7., siis 3 on lapse 7.. Kui olime aru saada, mida lapsed 7. on - Noh, me näeme, et 7 on kursor 3 ja kursor 9, nii 9 ja 3 on lapsed 7. Üheksa tal ei ole lapsi, sest tema laps osuti on null, ja 3 on ainult üks laps, 6. Kuus on ka lapsi ei ole, sest nii tema lähtekohtadeks on null, mis me teha just praegu. 

Lisaks on meil ka rääkida vanematele eriti sõlme, ja see on, nagu te tahaks oodata, vastupidi selle lapse kirjeldus. Igal tipul on vaid üks vanem - kahe asemel nagu oleksite võinud inimestega. Näiteks lapsevanem 3 on 7. Vanem 9. on ka 7 ja vanem 6. on 3. Mitte palju ta. Meil on ka mõttes rääkida vanavanemad ja lapselapsed, ja üldisemalt rääkides esivanemad ja järeltulijad eriti sõlme. Esivanem sõlme - või esivanemad, pigem on sõlm - on kõik sõlmed, mis asuvad teed juurest selle sõlme. Näiteks kui ma vaatan sõlme 6 Seejärel esivanemad ei kavatse olla nii 3 ja 7. Esivanemad 9, näiteks on - kui ma vaatan sõlme 9 - siis esivanem 9. on vaid 7. Ja järeltulijad on täpselt vastupidine. Kui ma tahan vaadata kõiki järeltulijad 7, siis ma pean vaatama kõiki tippe all. Nii, mul on 3, 9 ja 6 kõik nagu järeltulijad 7. 

Lõpptähtaeg et me räägime on see mõiste on vend. Õed-vennad - omamoodi pärast mööda neid pere mõttes - on sõlmed, mis on samal tasemel puus. Niisiis, 3 ja 9 on õed-vennad, sest nad on samal tasemel puus. Nad mõlemad on sama emaettevõtja, 7. 6 ei ole õdesid-vendi, sest 9 ei ole ka lapsi. Ja 7 ei ole õdesid-vendi, sest see on just meie puu, ja seal on ainult kunagi 1 root. 7 on õed-vennad seal peaks olema sõlme üle 7. Seal peaks olema vanem, 7., mispuhul 7 oleks enam puu juur. Siis, et uus vanem, 7. oleks ka olla laps, ja et laps oleks siis vend 7.. 

Olgu. Liigume edasi. Kui me alustasime meie arutelu kahendpuuks, me rääkisime sellest, kuidas me ei kavatse neid kasutada saada eelise nii massiivid ja lingitud nimekirjad. Ja kuidas me teeme, mis on selle tellimise vara. Me ütleme, et kahendpuu tellitakse vastavalt spetsifikatsioonile, kui iga sõlme meie puu, kõik tema järeltulijad vasakul - vasak laps ja kõik vasakule lapse järeltulijad - on vähem väärtusi, ja kõik sõlmed paremal - õigus lapse ja kõik õige lapse järeltulijad - on sõlmede suurem väärtus aktiivse sõlme, et me vaatame. Lihtsalt lihtsus, me eeldada, et seal ei ole nodes meie puu. Näiteks sellel puul me ei hakka tegelema puhul kus meil on väärtus 7 keskmes  ja siis meil on ka väärtus 7 mujal puu. Sellisel juhul märkad, et see puu on tõepoolest tellinud. Meil on väärtus 7 keskmes. Kõik vasakul 7. - kui ma tagasi võtta kõik need väikesed märgid siin - kõik vasakule 7 - 3 ja 6 - need väärtused on nii alla 7, ja kõik paremale - mis on just see 9 - on suurem kui 7. 

See ei ole ainult tellitud puu sisaldavad need väärtused, kuid Joonistame veel mõned neist. Seal on tegelikult terve hulk võimalusi, et me saame sellega hakkama. Ma lähen kasutada stenografisti lihtsalt hoida asjad lihtsad, kus - mitte joonistus välja terve kasti-ja-nooled - Ma lihtsalt juhtida numbrid ja lisada nooli ühendab neid. Et alustada, me lihtsalt kirjutada meie originaalse puu uuesti kus meil oli 7 ja seejärel 3, ja siis 3 märkis tagasi õigus 6 ja 7 oli õigus lapsele, et oli 9. Olgu. Mis on teine ​​võimalus, et me võiks kirjutada selle puu? Selle asemel, et 3 oleks vasakul laps 7, me oleks võinud ka 6 olla vasakul laps 7, ja siis 3 oleks vasakul laps 6. See näeks välja selline puu siinsamas, kus ma sain 7, siis 6, siis 3 ja 9 õige. Samuti ei pea olema 7-le meie juurest sõlme. Võiksime ka 6 nagu meie juurest sõlme. Mis oleks sinu arvates on? Kui me tahame säilitada seda tellida vara, kõik vasakule 6 peab olema väiksem kui see. Seal on ainult üks võimalus, ja see on 3. Aga siis kui õige laps 6, meil on kaks võimalust. Esiteks, me võiks olla 7 ja siis 9, või me võime teha seda - nagu ma olen umbes teha siin - kus meil on 9, kui õige laps 6 ja siis 7-vasakule laps 9. 

Nüüd, 7 ja 6 ei ole võimalik ainult väärtused juur. Võiksime ka 3 olla root. Mis juhtub, kui 3 on keskmes? Siin asjad natuke huvitav. Kolm ei ole mingit väärtust, mis on väiksem kui see, nii et kogu vasak pool puud on lihtsalt saab olema null. Seal ei kavatse olla midagi seal. Paremale, me võime üles loetleda asjad tõusvas järjekorras. Meil võiks olla 3, siis 6, siis 7, siis 9. Või me võiksime teha 3, siis 6, siis 9, siis 7. Või me võiksime teha 3, siis 7, siis 6, siis 9. Või, 3, 7 - tegelikult ei, me ei saa 7 enam. See on meie üks asi seal. Me saame seda teha 9, ja siis 9 me saame teha 6 ja seejärel 7. Või saame 3, siis 9, siis 7 ja seejärel 6. 

Üks asi juhtida teie tähelepanu siin et need puud on natuke imelik ilmega. Eriti kui me vaatame 4 puud paremal - Ma ringi neid, siin - need puud näevad välja peaaegu täpselt nagu seotud nimekirja. Igal tipul on vaid üks laps, ja nii me ei ole sellest midagi puu-like struktuur, mida me näeme, näiteks  Käesolevas üks üksik puu siin all vasakul. Need puud on tegelikult nn degenereerunud kahendpuuks, ja me räägime neist tulevikus rohkem - eriti kui sa lähed võtma teiste infotehnoloogia kursusi. Need puud on mandunud. Nad ei ole väga kasulik, sest tõesti, seda struktuuri sobiv  lookup korda sarnane seotud nimekirja. Me ei saa ära extra mälu - see pildi pointer - sest meie struktuur on halb sel viisil. Selle asemel, et minna ja venitama kahendpuuks et on 9 keskmes, mis on viimane juhtum, et meil oleks, me oleme selle asemel, sel hetkel, räägi natuke selle muu termin et me kasutame rääkides puud, mida nimetatakse kõrgus. 

Kõrgus puu on vahemaa juurest kõige-kauge sõlme, või pigem arvu humal, mida oleks võinud teha, et alustada juurest ja siis lõpuks kõige-kauge sõlme puu. Kui me vaatame mõned neist puud, et oleme tõmmatud siin, näeme, et kui me võtame selle puu ülemises vasakus nurgas ja hakkame kell 3, siis on meil teha 1 hüppe saada 6, teine ​​hop saada 7, ja kolmanda hüppe saada 9. Niisiis, kõrgus see puu on 3. Me võime teha sama harjutus teised puud kirjeldatud käesoleva roheline, ja me näeme, et kõrgus on kõik need puud on ka tõepoolest 3. See on osa sellest, mis teeb neid degenereerunud - et nende kõrgus on vaid üks väiksem arv tippe kogu puu. Kui me vaatame seda muu puu, mis on piirati punane, teiselt poolt, näeme, et kõige kauges tipud on 6 ja 9 - jätab olid need sõlmed, mis ei ole lapsi. Nii, et saada root node kas 6 või 9 meil teha ühe hüppe, et saada 7 ja siis teise hüppe saada 9, ja samuti, ainult teine ​​hüpe 7, et saada 6. Niisiis, kõrgus see puu siin on ainult 2. Võite minna tagasi ja teha, et kõik teised puud, mis me varem arutatud alustades 7 ja 6, ja leiad, et kõrgus kõik need puud on ka 2. 

Põhjus, miks me oleme rääkinud tellitud kahendpuuks ja miks nad on lahedad, sest saate otsida neid väga sarnaselt otsides üle järjestatud massiivist. See on koht, kus me räägime saada, et parem lookup aeg üle lihtne seotud nimekirja. Mis lingitud nimekiri - kui soovite leida konkreetne element - sa oled parim teen mingi lineaarne otsing kui hakkate alguses nimekiri ja hop ühe poolt-üks - ühe sõlme ühe sõlme - läbi kogu nimekiri kuni leiad mida iganes te otsite. Arvestades, kui teil on kahendpuu, mis on salvestatud selles kena formaadis, tegelikult võite saada rohkem binaarne otsing toimub kus sa jaga ja valitse ja otsida sobiv poole puu igal sammul. Vaatame, kuidas see toimib. 

Kui meil on - jälle läheb tagasi meie algse puu - alustame kell 7, meil on 3 vasakul, 9 paremal ja all 3, siis 6. Kui tahame otsida number 6 see puu, me tahaks alustada keskmes. Meil oleks võrrelda väärtust me otsime, ütleme 6 kuni väärtust salvestatud sõlme, et me praegu vaadates, 7, leiavad, et 6 on tõepoolest vähem kui 7, nii et me tahaks liikuda vasakule. Kui väärtus 6. olnud suurem kui 7, oleksime selle asemel liigutada paremale. Kuna me teame, et - tänu struktuuri meie tellitud kahendpuu - kõik väärtused alla 7 ei kavatse hoida vasakul 7, pole vaja isegi vaeva otsides paremal pool puud. Kui me liikuda vasakule ja me oleme nüüd sõlme, mis sisaldavad 3, me saame teha, et sama võrdlus uuesti, kui me võrdleme 3 ja 6. Ja me leiame, et kuigi 6 - raha me otsime - on suurem kui 3, saame minna paremale küljele sõlme sisaldab 3. Pole vasakul siin, nii et me oleks võinud eirata seda. Aga me teame ainult, et kuna me vaatleme puu ise, ja näeme, et puul on lapsed. 

See on ka üsna lihtne otsida 6 seda puud, kui me teeme seda ise inimestele, kuid olgem selle protsessi mehhaaniliselt nagu arvuti teeks tõesti mõista algoritm. Sel hetkel, me oleme nüüd vaadates sõlme, mis sisaldab 6 ja me otsime väärtus 6, jah, tõepoolest, me leidsime sobiva sõlme. Leidsime väärtus 6 meie puust ja saame lõpetada meie otsingumootorit. Sel hetkel, sõltuvalt, mis toimub, võime öelda, jah, oleme leidnud väärtus 6, see eksisteerib meie puu. Või kui me plaanite lisada sõlme või midagi, mida me teha saame, et selles punktis. 

Teeme veel paar otsingud lihtsalt näha, kuidas see toimib. Vaatame, mis juhtub, kui me proovida ja otsida väärtus 10. Kui me otsida väärtus 10, me hakkaks keskmes. Tahame näha, et 10 on suurem kui 7, nii et me tahaks liikuda paremale. Soovime saada 9 ja võrrelge 9. 10 ja vaata, et 9 on tõepoolest alla 10. Nii et taas, me tahaks proovida liikuda paremale. Aga sel hetkel, me tahaks teada, et me oleme null sõlme. Seal pole midagi. Ei ole midagi, kus 10 peaks olema. See on koht, kus saame aru jätmine - et tegelikkuses ei ole 10 puud. Ja lõpuks, lähme läbi juhul, kui me üritame üles otsima 1 puu. See on sarnane, mis juhtub kui me vaatame kuni 10, välja arvatud asemel läheb paremale, me läheme vasakule. Alustame kell 7 ja näha, et 1 on väiksem kui 7, nii et me liigume vasakule. Saame 3 ja näha, et 1 on väiksem kui 3, siis jälle püüame liikuda vasakule. Sel hetkel on meil null sõlme, nii et jälle saame aru rike. 

Kui sa tahad rohkem teada kahendpuuks, seal on terve hulk lõbus vähe probleeme, mida saate teha nendega. Pakun praktiseerivad joonistus välja neist skeemidest ühe poolt-üks ja pärast läbi kõik erinevad astmed, sest see tulla super-mugav mitte ainult kui sa teed Huffman kodeering probleem komplekt vaid ka tulevaste kursused - lihtsalt õppida, kuidas juhtida läbi neid andmestruktuure ja mõelda läbi probleemide pliiatsi ja paberi või sel juhul, iPad ja pliiatsiga. 

Sel hetkel aga, me läheme edasi liikuda, et teha mõned kodeerimine tava ja tegelikult mängida neid kahendpuuks ja vaata. Ma lähen, et minna tagasi üle minu arvuti. Selle osa jagu, selle asemel CS50 Run või CS50 Spaces, Ma lähen kasutage seadet. 

Pärast koos Ülesanded spetsifikatsioon, Ma näen, et ma peaksin avama seadme lähen oma Dropbox kausta luua kausta nimega 7. jagu, ja siis looge fail nimega binary_tree.c. Läheb lahti. Mul aparaat juba avatud. Ma lähen tõmba terminal. Ma lähen minema Dropbox kausta teha kataloogi nimega section7, ja vaata, et see on täiesti tühi. Nüüd ma lähen avama binary_tree.c. Olgu. Läheb lahti - tühi fail. 

Lähme tagasi spetsifikatsioon. Spetsifikatsioon küsib uue tüübi definitsioon jaoks kahendpuu sõlme sisaldav int väärtusi - nagu väärtused, mida me juhtis tähelepanu meie skeemide enne. Me ei kavatse kasutada seda trafaretset typedef et me oleme teinud siin et sa peaksid tunnustama alates Ülesanded 5 - kui sa hash tabelis viis vallutavad speller programmile. Sa peaksid ka tunda seda eelmise nädala jagu kus me rääkisime seotud nimekirju. Meil see typedef on struct tipp, ja me andsime selle struct tipp see nimi struct tipp eelnevalt nii et saame siis nimetavad seda kuna me tahame struct tipp viiteid Osana meie struct, kuid me oleme siis ümbritseb seda - või pigem kinnine seda - typedef nii et hiljem kood, saame tähistada seda struct kui lihtsalt sõlme asemel struct tipp. 

See saab olema väga sarnane üksikult seotud nimekirja määratlus, et me nägime eelmisel nädalal. Selleks, lähme lihtsalt alustada kirjalikult esitatud trafaretset. Me teame, et meil peab olema täisarv, nii me panna int väärtus, ja siis selle asemel, et lihtsalt üks kursor järgmisele element - nagu tegime koos üksikult seotud nimekirju - me lähed on vasak ja parem laps suunanäitajaks. See on päris lihtne ka - struct tipp * vasak laps; ja struct tipp * õigus lapse. Lahe. See näeb välja nagu päris hea algus. Lähme tagasi spetsifikatsioon. 

Nüüd tuleb tunnistada maailma tipp * muutuja puu juurt. Me kavatseme teha selles maailmas nagu me esmajärjekorras osuti meie seotud nimekirja ka globaalne. See oli nii, et neid funktsioone, mis me kirjutame me ei pea hoidma kulgeb ümber selle juur - kuigi me näeme, et kui sa tahad kirjutada neid funktsioone rekursiivselt, see võib olla parem isegi mitte andke seda ümber globaalse esimese koha ja selle asemel initsialiseerida seda kohapeal oma põhifunktsiooni. Aga me teeme seda kogu maailmas, et alustada. Jällegi anname paar ruumid, ja ma lähen kuulutada sõlme * juur. Lihtsalt veendumaks, et ma ei jäta seda uninitialized, ma lähen, et seada see võrdub null. Nüüd, mille peamine ülesanne - mis me kirjutame tõesti kiiresti siin - int main (int argc, const char * argv []) - ja ma lähen alustada kuulutatakse minu argv array const lihtsalt nii, et ma tean et need argumendid on argumendid, et ma ilmselt ei taha muuta. Kui ma tahan neid muuta ma peaks ilmselt tegemist nende koopiad. Näete seda palju koodi. See on hea ükskõik kummale poole. See on hea, et jätta see - jätta const, kui soovite. Ma tavaliselt pannakse see lihtsalt nii, et ma meelde endale  et ma ilmselt ei taha muuta need argumendid. 

Nagu alati, ma lähen lisada see return 0 liini lõpus peamine. Siin ma initsialiseerida minu juurest sõlme. Praegusel kujul just nüüd, mul on osuti, mis on seatud null, nii see osutavad midagi. Et tegelikult alustada hoone sõlme, Ma kõigepealt mälu eraldada see. Ma lähen tegema, et tehes mälu hunnik kasutades malloc. Ma lähen määratud juur võrdne tulemus malloc, ja ma lähen kasutada sizeof operaator arvutada suurus sõlme. Põhjusel, et ma kasutan sizeof sõlme asemel, ütleme, teeme midagi sellist - malloc (4 + 4 +4) või malloc 12 - on, sest ma tahan, et mu eeskiri peaks olema ühilduv kui võimalik. Ma tahan, et oleks võimalik seda. C faili kompileerida seadmele ja seejärel kompileerida see minu 64-bit Mac - või hoopis arhitektuur - ja ma tahan, et see kõik töötama sama. 

Kui ma olen tegemise eeldusi suurus muutujad - suurus int või suuruse pointer - siis ma ka teha oletusi selle kohta, milliseid arhitektuur millest minu koodi saab edukalt koostada, kui joosta. Kasutage alati sizeof erinevalt käsitsi liidetakse struct valdkondades. Teine põhjus on see, et seal võiks olla ka polster et tõlkija lastavate struct. Isegi lihtsalt summeerides üksikute andmeväljade ei ole midagi, mida sa tavaliselt tahad teha, jah, kustutage see rida. Nüüd, tõesti initsialiseerida see Juursõlme, Ma pean ühendada väärtused iga selle erinevates valdkondades. Näiteks väärtuse Ma tean, ma tahan initsialiseerida kuni 7, ja nüüd ma lähen seatud vasakul laps olla null ja õigus lapsel olla ka null. Suurepärane! Oleme teinud selles osas spec. 

Spetsifikatsioon alla allosas lehekülg 3 küsib minult, et luua veel kolm tippu - üks sisaldab 3, üks sisaldab 6 ja üks 9 - ja siis juhe nad nii see näeb välja täpselt nagu meie puudiagramm et me rääkisime varem. Teeme seda päris kiiresti siin. Näete tõesti kiiresti, et ma lähen alustada kirjalikult hunnik dubleeritud koodi. Ma lähen luua sõlme * ja ma kutsun seda kolm. Ma lähen, et seada see võrdne malloc (sizeof (node)). Ma lähen püstitas kolm-> väärtus = 3. Kolm -> left_child = NULL; 3 -> õigus _child = NULL; samuti. See tundub üsna sarnane initsialiseerimisel juure, ja see on täpselt see, mida Ma lähen tegema, kui ma hakkan initsialiseerimisel 6 ja 9 ka. Ma teen seda tõesti kiiresti siin - tegelikult, ma teen natuke kopeeri ja kleebi ja veenduge, et I - igav.  Nüüd on mul see kopeerida ja võin minna ja seada see võrdub 6. Te näete, et see võtab natuke aega ja ei ole super-efektiivne. Vaid natuke, me kirjutame funktsiooni, et teeb seda meie eest. Ma tahan selle asendada 9, asendada, et koos 6. 

Nüüd on meil kõik meie keskuste loomist ja vormindatud. Meil meie juure määratud väärtus 7, või sisaldab väärtus 7, meie sõlm sisaldab 3, meie sõlm sisaldab 6, ja meie sõlm sisaldab 9. Sel hetkel, kõik me peame tegema, on traadi kõik üles. Põhjus, miks ma vormindatud kõik suunanäitajaks tühjaks on lihtsalt nii, et ma veenduge, et Mul ei ole ühtegi uninitialized osuti sinna juhuslikult. Ja ka, sest sel hetkel, mul on ainult tegelikult ühendada sõlmed omavahel - need, mis nad tegelikult ühendatud - ma ei pea minema läbi ja teeb Kontrollige, et kõik nulls on seal selleks ettenähtud kohtades. 

Algusega kell juur, ma tean, et juur vasak laps on 3. Ma tean, et juur on õigus laps on 9. Pärast seda, vaid teine ​​laps, et olen jäänud muretsema on 3 õigust last, mis on 6. Sel hetkel, see kõik tundub päris hea. Me neid kustutada ridu. Nüüd kõik tundub päris hea. Lähme tagasi meie spetsifikatsioon ja vaata, mis me peame tegema järgmisena. 

Sel hetkel, oleme kirjutada funktsioon nimega "sisaldab" koos prototüüp "bool sisaldab (int väärtus)". Ja see sisaldab funktsiooni läheb tagasi true  kui puu osutas Meie globaalne juure muutuja  sisaldab väärtust läks funktsioon ja vale teisiti. Lähme edasi ja tee seda. See saab olema täpselt nagu lookup, et me tegime käsitsi iPad natuke tagasi. Teeme uuesti suurendate natuke ja liikuge üles. Me paneme selle funktsiooni paremal kohal meie põhiülesanne nii et me ei pea tegema mingit prototüübid. Niisiis, bool sisaldab (int väärtus). Nii juba läheb. Seal on meie trafaretset deklaratsiooni. Lihtsalt veenduge, et see kogub, Ma lähen edasi minna ja lihtsalt pani võrdne tagasi false. Praegu see funktsioon lihtsalt ei tee midagi ja alati aru, et väärtus, mida me otsime ei ole puu. 

Sel hetkel, see on ilmselt hea mõte - kuna me oleme kirjutanud terve hunnik koodi ja me ei ole isegi proovinud testib seda veel - veenduda, et see kõik koostab. On paar asja, mida me peame tegema, veendumaks, et see on tegelikult kompileerida. Esiteks, kas me olen kasutanud mingeid muid funktsioone, mis tahes raamatukogude et me ei ole veel lisatud. Funktsioonide oleme kasutanud siiani on malloc, ja siis oleme ka kasutanud seda tüüpi - see ebastandartne tüüp nimega "bool' - mis on standardvarustuses bool header fail. Me kindlasti tahame lisada standard bool.h jaoks bool tüüpi, ja tahame ka # include standard lib.h jaoks standard raamatukogud mis sisaldavad malloc ja tasuta, ja kõik see. Nii, zoom out, me ei kavatse loobuda. Proovime ja veenduge, et see tegelikult ei kompileerida. Me näeme, et see, et me oleme õigel teel. 

Avame kuni binary_tree.c uuesti. Ta koostab. Lähme alla ja veenduge, et me lisada mõned kõned meie Contains funktsioon - lihtsalt veenduda, et kõik on hästi ja hea. Näiteks, kui me tegime mõned otsingud oma puu varem üritasime otsida väärtuste 6, 10 ja 1, ja me teadsime, et 6 oli puu, 10 ei olnud puust ja 1 oli mitte puus kas. Olgem kasutada neid proovi kõned viis aru saada, kas meie Contains funktsioon töötab. Selleks, et ma lähen kasutada printf funktsiooni, ja me lähme välja printida tulemus üleskutse sisaldab. Ma lähen panna stringi "sisaldab (% d) = sest  me lähme pistik väärtus, et me ei kavatse otsida, ja =% s \ n "ja kasutada seda kui meie stringi. Me lihtsalt näeme - sõna otseses mõttes välja printida ekraanil - mis näeb välja nagu funktsioon kõne. See ei ole tegelikult funktsioon kõne.  See on lihtsalt string kavandatud sarnanema funktsioon kõne. 

Nüüd me ei kavatse ühendada väärtused. Me läheme proovida sisaldab 6 ja siis me teeme siin kasutada, et kolmekomponentsete operaator. Vaatame - sisaldab 6 - nii, nüüd olen sisaldas 6 ja kui sisaldab 6 on tõsi, string, mis me kavatseme saata% s formaat iseloomu saab olema string "true". Olgem leidke üle natuke. Muidu me tahame saata stringi "vale" kui sisaldab 6 naaseb vale. See on veidi tobe välimusega, kuid ma kujutan ma võin ka illustreerivad mida kolmekomponentsete operaator välja näeb, sest me pole seda näinud mõnda aega. See on kena, mugav viis aru saada, kui meie Contains funktsioon töötab. Ma lähen tagasi kerima üle vasakule, ja ma lähen kopeeri ja kleebi see joon paar korda. See muutis mõned nende väärtuste ümber, nii et see saab olema 1 ja see saab olema 10. 

Sel hetkel on meil kena Contains funktsioon. Meil on mõned testid, ja me näeme, kui see kõik toimib. Sel hetkel oleme kirjutanud mõned rohkem kood. Aeg loobuda välja ja veenduge, et kõik ikka kogub. Lõpeta ära, ja nüüd proovime teha kahendpuu uuesti. Noh, tundub, et meil viga, Ja meil seda selgesõnaliselt kuulutab raamatukogu funktsiooni printf. Tundub, et me peame minema ja # include standardio.h. Ja, et kõik peaksid koostama. Oleme kõik hea. Nüüd proovime töötab kahendpuu ja vaata, mis juhtub. Siin me oleme. / Binary_tree, ja me näeme, et me ootasime - sest me ei ole rakendanud sisaldab veel, või õigemini, me oleme lihtsalt panna tagasi false - me näeme, et see on lihtsalt jälle vale neile kõigile, Nii et kõik töötavad enamasti üsna hästi. 

Lähme tagasi ja tegelikult rakendada sisaldab selles punktis. Ma lähen liikuge allapoole suurendada, ja - Pea meeles, et algoritm, mida me kasutada oli, et alustasime kell Juursõlme ja siis iga sõlme, et kohtame, me teeme võrdluse ja selle põhjal võrdlus me kas minna vasakule lapse või paremale laps. See läheb väga sarnased binaarne otsing kood, mis me kirjutasime varem perspektiivis. Kui me alustad, me teame, et me tahame säilitada oma aktiivse sõlme et me vaatame, ja praegune tipp saab olema initsialiseeritud Juursõlme. Ja nüüd, me ei kavatse hoida läbimas puud ja pidage meeles, et meie peatumine tingimus -  kui me tegelikult töötatud kaudu näiteks käsitsi - oli siis, kui oleme kohanud null sõlme, mitte siis, kui me vaatasime null laps, vaid siis, kui me tegelikult kolis sõlme puu ja leidis, et me oleme null sõlme. Me läheme itereerima kuni viim ei võrdu tühjaks. Ja mida me teeme? Me läheme testida, kui (viim -> väärtus == väärtus), siis me teame, et me oleme tegelikult leitud sõlme, et me otsime. Nii et siin, me saame naasta tõsi. Muidu me tahame näha, kas väärtus on väiksem kui väärtus. Kui praegune tipp väärtus on väiksem kui me otsime, me hakkame liikuma paremale. Nii viim = viim -> right_child; ja teisiti, me ei kavatse liikuda vasakule. viim = viim -> left_child;. Päris lihtne. 

Sa ilmselt tunda silmus, mis näeb välja väga sarnane sellele alates Kahendotsingupuu varem mõiste, välja arvatud siis me tegelesime madal, keskmine ja kõrge. Siin me lihtsalt peame vaatama jooksva väärtusega, nii et see on kena ja lihtne. Teeme kindel, et see kood töötab. Esiteks, veenduge, et see kogub. Paistab, et see teeb. Proovime läbiviimist. Ja tõepoolest, see prindib välja kõik, mida me lootsime. Ta leiab 6 puud, ei leia 10, sest 10 pole puus, ja ei leia 1 kas sest 1 on ka mitte puus. Lahe värk. 

Olgu. Lähme tagasi meie spetsifikatsioon ja vaata, mis edasi. Nüüd ta tahab lisada veel mõned sõlmed meie puu. Ta tahab lisada 5, 2 ja 8, ning veenduda, et meie sisaldab koodi töötab ootuspäraselt. Lähme teha. Sel hetkel, mitte tehes, et tüütu kopeeri ja kleebi uuesti, olgem kirjutada funktsioon tegelikult luua sõlme. Kui me kerige kõik viis peamist näeme, et me oleme seda teinud juba väga sarnane koodi ikka ja jälle iga kord, kui me tahame luua sõlme. 

Olgem kirjutada funktsioon, mis tegelikult ehitada sõlm meile ja tagastab selle. Ma kutsun seda build_node. Ma lähen üles ehitada sõlm eriline väärtus. Vähenda siin. Esimene asi, mida ma lähen tegema, on tegelikult luua ruumi sõlme hunnik. Niisiis, sõlme * n = malloc (sizeof (node)); n -> väärtus = väärtus; ja siis siin, ma lihtsalt läheb initsialiseerida kõik väljad olema sobivad väärtused. Ja päris lõpus, me tagasi meie sõlme. Olgu. Üks asi on tähele panna, et see funktsioon siin läheb tagasi pointer mälu, mis on olnud hunnik jaotatud. Mis on tore on see, et see sõlm nüüd - meil kuulutada see hunnik, sest kui me kuulutasime selle kohta virna me ei saa seda teha selle funktsiooni niimoodi. See mälu peaks minema ulatus ja oleks vale, kui me püüdsime seda kasutada hiljem. Kuna me kuulutame hunnik jaotatud mälu, me peame hoolitsema vabastades ta hiljem meie programm ei leki mingit mälu. Oleme olnud punting kohta, et kõik muu kood lihtsalt lihtsuse huvides ajal, aga kui sa kunagi kirjutada funktsioon, mis näeb välja selline kus sul - mõned kutsuvad seda malloc või RealLOC sees - sa tahad teha kindel, et paned mingi kommentaar siia üles, mis ütleb, hei, sa tead, tagastab hunnik jaotatud sõlme käivitub edasikanduvad väärtus. Ja siis sa tahad teha kindel, et paned mingi märkus, mis ütleb, helistaja peab vabastama tagastatakse mälu. Nii, kui keegi kunagi läheb ja kasutab seda funktsiooni, nad teavad, et mida iganes nad saavad tagasi selle funktsiooni mingil hetkel tuleb vabastada. 

Eeldades, et kõik on hästi ja hea siin, saame minna meie koodi ja asendada kõik need read siin koos kõnesid meie build sõlme funktsiooni. Teeme seda tõesti kiiresti. Ühelt poolt, et me ei kavatse asendada see osa siin all allosas, kus me tegelikult juhtmetega ühendada sõlmed osutada üksteisele sest et me ei saa seda teha meie funktsioon. Aga teeme root = build_node (7); sõlme * 3 = build_node (3); sõlme * 6 = build_node (6); sõlme * 9 = build_node (9);. Ja nüüd on meil ka soovis lisada sõlmpunktid - sõlme * 5 = build_node (5); sõlme * 8 = build_node (8); ja milline oli teiste sõlme? Vaatame siin. Tahtsime lisada ka 2 - sõlme * kaks = build_node (2);. Olgu. Sel hetkel, me teame, et meil on 7, 3, 9 ja 6 kõik wired up nõuetekohaselt, kuid kuidas 5, 8, ja 2? Hoida kõike õiges järjekorras, me teame, et kolm on õige laps on 6. Niisiis, kui me kavatseme lisada 5 5 Samuti kuulub paremal pool puud, millest 3 on root, nii 5 kuulub nii vasakul lapse 6. Me saame seda teha, öeldes, kuus -> left_child = 5; ja siis 8 kuulub nii vasak laps 9, seega 9 -> left_child = 8; ja siis 2 on vasak laps on 3, nii et me saame teha, et siin üleval - sind -> left_child = kaks;. Kui sa ei ole päris jälgida koos, et ma soovitan teil teha seda ise. 

Olgu. Olgem salvestada. Lähme välja ja veenduge, et see kogub, ja siis me saame lisada meie Contains kõned. Paistab kõike veel koostab. Lähme ja lisada mõned sisaldab kõned. Jällegi, ma teen natuke kopeeri ja kleebi. Nüüd Otsime 5, 8, ja 2. Olgu. Teeme kindlaks, et see kõik tundub hea ikka. Suurepärane! Salvestamist ja sulgemist. Nüüd teeme, kompileerida, ja nüüd lähme jooksma. Alates tulemusi, tundub kõik töötab lihtsalt kena ja hästi. Suurepärane! Nii et nüüd on meil meie Contains funktsiooni kirjutatud. Liigume edasi ja alustada tööd, kuidas lisada sõlmede puusse sest nagu me teeme seda kohe, asjad ei ole väga ilus. 

Kui me tagasi minna spetsifikatsioon, küsib ta meile kirjutada funktsiooni nimetatakse lisada - jällegi tagasi bool jaoks, kas me võiks tegelikult lisada sõlme puusse - ja siis väärtust lisada puu on märgitud kui ainus argument meie sisestada funktsiooni. We will return true kui saaksime tõepoolest sisestada sõlme sisaldav väärtus puusse, mis tähendab, et me üks, oli piisavalt mälu, ja siis kaks, et sõlm varem ei olnud, puus alates - Pea meeles, et me ei kavatse on duplikaatväärtusi puus, vaid teha asjad lihtsad. Olgu. Tagasi kood. Tee lahti. Suurenda natuke, seejärel kerige. Paneme sisestada funktsioon õigus eespool sisaldab. Jällegi, see saab nimetada bool sisestada (int väärtus). Anna talle veidi rohkem ruumi, ja siis, kui vaikimisi paneme vastutasuks vale päris lõpus. Nüüd alumises otsas, lähme edasi ja selle asemel, et käsitsi hoone tippu peamistes end ja juhtmestik neid juhtida üksteisele nagu me teeme, me toetume insertfunktsioonide teha. Me ei kasuta meie sisestada funktsiooni ehitada kogu puu nullist lihtsalt veel, vaid me vabaneda neid ridu - we'll kommenteeri välja need read - et ehitada sõlmede 5, 8, ja 2. Ja selle asemel, me lisada kõnede meie insertfunktsioonide veenduda, et see tõesti töötab. Läheb lahti. 

Nüüd oleme välja kommenteerida neid ridu. Meil on ainult 7, 3, 9 ja 6 meie puu selles punktis. Veendumaks, et see kõik töötab, saame suumimiseks muuta meie kahendpuu, käivitada, ja näeme, mis sisaldab nüüd ütleb meile, et me oleme täiesti õigus - 5, 8, ja 2 ei ole enam puu. Mine tagasi kood, ja kuidas me lisada? Pea meeles, mida me tegime kui olime tegelikult lisades 5, 8, ja 2. varem. Me mängisime et Plinko mäng, kus hakkasime keskmes, langes puu ükshaaval ühe kuni leidsime sobiva lõhe, ja siis me traadiga sõlme sobival kohapeal. Me teeme sama asja. See on põhimõtteliselt nagu kirjalikult koodi, mida me kasutada sisaldab funktsiooni leida kohapeal, kus sõlme peaks olema, ja siis me lihtsalt läheb lisada sõlm seal. Alustame tee. 

Nii et meil on sõlm * viim = root; me lihtsalt läheb järgida sisaldab koodi kuni me leiame, et see ei ole päris töö meile. Me läheme läbi puu, kuid praeguses element ei ole null, ja kui leiame, et viim väärtus on võrdne väärtus, et me üritame lisada - Noh, see on üks juhtumeid, kus me ei saanud tegelikult sisestada sõlme puusse, sest see tähendab, et meil on dubleeritud väärtus. Siin me oleme tegelikult läheb tagasi false. Nüüd teine, kui viim väärtus on väiksem kui väärtus, Nüüd me teame, et me liigume paremale  sest väärtusest kuulub paremal pool viim puu. Vastasel korral me ei kavatse liikuda vasakule. See on põhimõtteliselt meie Contains toimima seal. 

Sel hetkel, kui me oleme valmis seda samas silmus, meie viim osuti läheb osutades tühjaks kui funktsioon ei ole juba tagastatud. Me Seega võttes viim kohas, kus me tahame lisada uus tipp. Mida veel teha on tegelikult ehitada uus sõlm, mis me saame teha üsna kergesti. Me saame kasutada meie super-mugav ehitada sõlm funktsiooni, ja midagi, mida me ei teinud varem - me lihtsalt selline pidasin enesestmõistetavaks, aga nüüd me teeme lihtsalt veenduda - me testida veendumaks, et tagastatav väärtus uus sõlm oli tegelikult ei ole null, sest me ei taha, et alustada tutvumise et mälu, kui see on null. Meil saab katsetada veendumaks, et uus sõlm ei ole võrdne null. Või selle asemel, saame lihtsalt näha, kui ta tegelikult on null, ja kui see on null, siis saame lihtsalt tagasi false alguses. 

Sel hetkel on meil juhe uus sõlm sisse oma asjakohaseid kohapeal puu. Kui me vaatame tagasi peamine ja kus me olime tegelikult juhtmestik väärtused enne, näeme, et kuidas me teeme seda, kui me tahtsime panna 3 puus oli meil ligi vasakul laps juur. Kui me paneme 9 puu oli meil pääseda õige laps juur. Me pidime olema kursor lapsevanem, et luua uut väärtust puusse. Kerimine varundada lisada, et ei kavatse päris töö siin sest meil ei ole vanem pointer. Mida me tahame, et oleks võimalik teha on, sel hetkel, kontrollida emaettevõtte raha ja vaata - Nojah, kui vanema väärtus on väiksem kui praegune väärtus, siis lapsevanema õigust lapse peaks olema uus sõlm; teisiti, vanema vasakul laps peaks olema uus sõlm. Aga meil ei ole selle vanema osuti veel. 

Selleks, et seda saada, me tegelikult läheb on jälgida seda nagu me minna läbi puu ja leida sobiv kohapeal meie silmus üle. Me saame teha, et kerides tagasi üles tippu meie insertfunktsioonide ja jälgivad veel pointer muutuja nimega vanem. Me läheme, et seada see võrdub null esialgu ja siis iga kord kui me minna läbi puu, me ei kavatse seada vanem osuti mängu praegune pointer. Määra vanema võrdne viim. Nii, iga kord kui läheme läbi, me kavatseme tagada, et kui praegune pointer saab suurendatakse vanem osuti sellele järgneb - ainult üks tase kõrgem kui praegune pointer puus. See kõik tundub päris hea. 

Ma arvan, et üks asi, mis me tahame, et kohandada see ehitada sõlm tagasi null. Selleks, et saada ehitada sõlm tegelikult edukalt naasta null, me peame muutma, et kood, sest siin me kunagi katsetada veendumaks, et malloc tagastatakse kehtiv pointer. Seega, kui (n! = NULL), siis - kui malloc tagastatakse kehtiv pointer, siis me algväärtustamiseks; Muidu me lihtsalt tagasi ja et lõpuks jälle null meile. Nüüd kõik tundub päris hea. Teeme kindel, et see tegelikult koostab. Tee kahendpuu, ja oh, meil on mõned asjad siin toimub. 

Meil kaudne deklaratsiooni funktsioon ehitada sõlme. Jällegi, nende koostajad, me ei kavatse alustada ülaosas. Mida see peab tähendama, et ma helistan ehitada sõlm enne, kui ma olen tegelikult kuulutanud. Lähme tagasi koodi tõesti kiiresti. Liikuge alla ja jumala eest, minu sisestada funktsioon on välja kuulutatud Ülaltoodud ehitada sõlm funktsiooni, aga ma üritan kasutada ehitada sõlm sees sisestada. Ma lähen minema ja koopia - ja kleebi ehitada sõlm funktsiooni teel siiapoole ülaosas. Nii, loodetavasti see töötab. Anname selle teise minna. Nüüd on kõik koostab. Kõik on hea. 

Aga sel hetkel, me ei ole tegelikult nimetatakse meie sisestada funktsiooni. Me lihtsalt teame, et ta koostab, nii lähme sisse ja panna mõned kõned sisse Teeme seda meie peamine ülesanne. Siin me välja kommenteerida 5, 8, ja 2. ja siis me ei traat neid siin all. Teeme mõned kõned sisestada, ja olgem ka kasutada sama liiki asju, mida me kasutada kui me tegime need printf nõuab veenduda, et kõik ei saa õigesti sisestatud. Ma lähen kopeeri ja kleebi, ja selle asemel sisaldab me teeme sisestada. Ja selle asemel, 6, 10 ja 1, me ei kavatse kasutada 5, 8, ja 2. See peaks loodetavasti sisestada 5, 8, ja 2. puusse. Koostage. Kõik on hea. Nüüd me tegelikult kulgema meie programm. 

Kõik tagastatud vale. Niisiis, 5, 8, ja 2 ei läinud, ja tundub Contains ei leia neid kas. Mis toimub? Lähme välja suumida. Esimene probleem oli see, et sisestada tundus tagastab false, ja tundub, et sellepärast me lahkusime meie tagasipöördumine vale kõne ja me tegelikult kunagi tagasi tõsi. Me ei saa seda seadistan. Teine probleem on, nüüd isegi kui me teeme - päästa see, sulgege see, kulgema teha uuesti, on see kompileerida, siis kestab see - näeme, et midagi juhtus. 5, 8, ja 2 olid ikka kunagi leitud puu. Niisiis, mis toimub? 

Võtame pilk selle koodi. Vaatame, kas me saame näitaja seda. Alustame vanem ei ole null. Seame praegune pointer võrdne juur pointer, ja me ei kavatse tööd meie tee ette läbi puu. Kui praegune tipp ei ole null, siis me teame, et me saame liikuda veidi allapoole. Me seame meie vanem osuti olema võrdne praeguse pointer, kontrollitud väärtus - kui väärtused on samad me tagasi vale. Kui väärtused on vähem kolisime õigus; muidu liikusime vasakule. Siis me ehitame sõlme. Ma suumida natuke. Ja siin me läheme proovida juhe üles väärtused olema samad. Mis toimub? Vaatame, kui võimalik Valgrind võib anda meile vihje. 

Mulle meeldib kasutada Valgrind lihtsalt sellepärast Valgrind tõesti kiiresti jookseb ja ütleb, kas on mingeid mälu vead. Kui võtame Valgrind edasi kood, nagu näete paremal here--Valgrind./binary_tree--and vajuta enter. Sa näed, et meil ei olnud mingit mälu viga, nii et tundub, et kőik on korras siiani. Meil on mõned mälu lekkeid, mida me teame, sest me ei ole juhtub, et vabastada kõik meie tipud. Proovime töötab GDB et näha, mis tegelikult toimub. Me teeme gdb. / Binary_tree. See käivitatud just fine. Laseme murdepunkt kohta sisestada. Lähme sõitma. Tundub, et me kunagi tegelikult nimetatakse sisestada. Tundub, et probleem oli lihtsalt selles, et kui ma muutsin siia alla peamine - kõik need printf kõnesid sisaldab - Ma pole kunagi tegelikult muutunud need helistada sisestada. Vaatame nüüd seda proovida. Olgem koguma. Kõik tundub hea seal. Nüüd proovime töötab see, vaata, mis juhtub. Olgu! Kõik tundub päris hea seal. 

Viimane asi, mida mõelda on, on olemas serv juhtudel sellele lisada? Ja selgub, et, noh, üks serv puhul, mis on alati huvitav mõelda on, mis juhtub, kui teie puu on tühi ja te nimetate seda sisestada funktsiooni? Kas see töötab? Noh, seda proovida. - Binary_tree. C - Kuidas me kavatseme seda testida on, me läheme alla, et meie peamine ülesanne, ja mitte juhtmestik need sõlmed üles nagu see, me lihtsalt läheb kommenteerida läbi kogu asi, ja selle asemel, juhtmestik kuni sõlmed ise, saame tegelikult lihtsalt minna ja kustutada see kõik. Me kavatseme teha kõik kõne lisada. Nii, teeme - asemel 5, 8, ja 2., me lisada 7, 3 ja 9. Ja siis ka soovite lisada 6 ning. Salvesta. Lõpeta. Tee kahendpuu. See kõik koostab. Me ei saa lihtsalt kasutada seda nagu on ja vaata, mis juhtub, aga see on ka saab olema väga oluline veenduda, et meil ei ole mingit mälu vead, sest see on üks meie serv juhtudel, et me teame. 

Teeme kindel, et see töötab hästi Valgrind, mis me teeme lihtsalt kulgeb Valgrind. / binary_tree. Paistab, et meil on tõepoolest üks viga ühest kontekstis - meil on see killustatust süü. Mis juhtus? Valgrind tegelikult ütleb meile kus see on. Vähenda veidi. Tundub, et see toimub meie sisestada funktsiooni, kus meil on kehtetu lugenud suurus 4 juures sisestada, liin 60. Lähme tagasi ja vaata, mis siin toimub. Vähenda tõesti kiire. Ma tahan veenduda, et see ei lähe ekraani serval, et saaksime näha kõike. Pull, et natuke. Olgu. Liikuge alla ja probleem on siin. Mis juhtub, kui me pikali ja meie praegune tipp on juba null, meie vanem sõlme on null, nii et kui me vaatame üles tipus, siin - kui samas silmus kunagi tegelikult täidab sest meie praegune väärtus on null - meie juured on null nii viim on null - siis meie ema kunagi saab seadistada viim või kehtiva väärtuse, nii, ema on samuti null. Peame meeles pidama, et kontrollida, et selleks ajaks saame siia alla, ja hakkame tutvumise vanema väärtus. Niisiis, mis juhtub? Noh, kui vanem on null - if (vanem == NULL) - siis me teame, et ei tohiks olla midagi puus. Meil tuleb püüda lisab selle juur. Me saame teha, et just millega juur võrdne uus sõlm. Siis sel hetkel, me tegelikult ei taha minna läbi need muud asjad. Selle asemel, just siin, me saame teha kas mujal kui-teine, või me võiksime ühendada kõik üles siin muud, kuid siin me lihtsalt kasutada mujal ja seda sel viisil. Nüüd me ei kavatse katsetada veendumaks, et meie vanem ei ole null enne siis tegelikult püüab kasutada oma valdkondades. See aitab meil vältida killustatust süü. Niisiis, me quit, zoom out, koostada, käivitada. 

Vigu ei, aga meil on veel hunnik mälu lekked sest me ei vabastaks kõik meie tipud. Aga kui me läheme siia ja me vaatame meie väljatrükk, näeme, et, noh, paistab meie kõigi lisab olid tagasi tõsi, mis on hea. Lisab kõik õige, ja siis sobiv Contains kõned on ka tõsi. 

Hea töö! Tundub, et me oleme edukalt kirjutatud sisestada. See on kõik, mis meil on selle nädala Ülesanded spetsifikatsioon. Üks lõbus väljakutse mõelda, kuidas sa tegelikult minna ja tasuta kõik sõlmed seda puud. Me saame seda teha mitmel erineval viisil, aga ma jätan selle kuni teil eksperimenteerida, ja kui lõbus väljakutse, proovige ja veenduge, et teil võib olla kindel, et see Valgrind aruanne ei tagasta mingit vead ja lekked. 

Õnn nädala Huffman kodeerimine lahendamist, ja me näeme järgmisel nädalal! [CS50.TV]