[Powered by Google Translate] [7 dalis] [mažiau patogūs] [Nate Hardison] [Harvardo universiteto] [Tai CS50.] [CS50.TV] 

Sveiki atvykę į 7 skirsnyje. Dėl uragano Sandy, vietoj normalų skyrių šią savaitę, ką mes darome, tai walk-through, per klausimų skyriuje. Aš ruošiuosi po Nustatykite 6 specifikacija kartu su problema, ir išgyvena visus klausimus Klausimų skyriuje skyrius. Jei yra kokių nors klausimų, rašykite juos CS50 aptarti. 

Alright. Pradėkime. Dabar aš žiūri į problemą, specifikaciją 3 puslapiuose. Mes ketiname pirmą kartą pradėti kalbėti apie dvejetainiai medžiai nes pastarieji daug EEE šią savaitę problemą, - Huffman medis kodavimas. Vienas iš pirmųjų duomenų struktūrų, mes kalbėjome apie CS50 masyvas. Atminkite, kad masyvas yra elementų seka - visų saugomi to paties tipo - visai šalia vienas kito atmintyje. Jeigu aš turiu integer masyvas, kad galiu piešti naudojant šį dėžės numeriai sveikieji skaičiai stilių - Tarkime, turiu 5 į pirmą langelį, aš turiu 7 antrojoje, tada aš turiu 8, 10 ir 20 galutiniame lange. Atminkite, kad du tikrai gerų dalykų apie šio masyvo yra tai, kad mes turime šį pastovaus laiko prieigą prie konkretaus elemento  masyve, jei mes žinome savo indeksą. Pavyzdžiui, jei aš noriu patraukti trečiąjį elementą masyvo - indeksuoti 2 naudojant nulinės indeksavimo sistemą - Aš tiesiog tiesiog turite padaryti paprasto matematinio skaičiavimo, hop to masyve pozicijos, ištraukite 8, kuri yra saugoma, ir aš tikiu, gera eiti. 

Vienas iš blogų dalykų apie šio masyvo, kad mes kalbėjome apie kai aptarėme, susijusius sąrašus - yra tai, kad, jei noriu įterpti elementą į šio masyvo, Aš ruošiuosi daryti, kai perkeliant aplink. Pavyzdžiui, šis masyvas čia rūšiuotas tvarka yra rūšiuojami didėjimo tvarka 5, nei 7, tada 8, tada 10 ir tada 20 - bet jei aš noriu įterpti skaičių "9", į šio masyvo, Aš ruošiuosi pereiti tam tikrus elementus, siekiant padaryti vietos. Mes galime padaryti, tai iš čia. Aš ruošiuosi perkelti 5, 7, tada 8; sukurti spragą, kur aš galiu įdėti į 9, , o po to 10 ir 20 gali eiti į dešinę iš 9. Tai tipo skausmas, nes blogiausiam scenarijui - kai mes įterpti arba pradžioje arba pabaigoje masyvą, priklausomai nuo to kaip mes perkeliant mes gali baigtis pereiti visus elementus, , kad mes šiuo metu saugoti masyve. 

Taigi, kas buvo būdas išspręsti šią problemą? Aplink tokiu būdu buvo eiti į Susietos sąrašą metodas, kai , o ne saugoti elementus, 5, 7, 8, 10 ir 20 Visi šalia vienas kito atmintyje tai, ką mes, o ne darė, buvo laikyti juos natūra, kur mes norėjome juos laikyti šių susijusių sąrašą mazgų, aš parengiant čia, ad hoc pobūdžio. Ir tada mes prijungti juos kartu naudojant šiuos Çstaigose. Galiu turėti žymeklį nuo 5 iki 7, rodyklė 7 8 rodyklė nuo 8 iki 10, ir, galiausiai, rodyklė iš 10 į 20, ir tada null tuo 20 rodyklė, nurodant, kad nėra nieko kairėje. Kompromisą, kad mes turime čia tai, kad dabar, jei norime įterpti skaičių "9" į mūsų rūšiuotų sąrašą, visi mes turime padaryti, tai sukurti naują mazgas su 9, pervesti jį atkreipti į tinkamą vietą, ir tada vėl laidas 8 atkreipti į 9. Kad gana greitai, jei mes žinome tiksliai, kur mes norime įterpti 9. Tačiau kompromisą mainais už tai, kad mes dabar prarado dėl nuolatinės laiko susipažinti bet konkretaus elemento mūsų duomenų struktūros. Pavyzdžiui, jei aš noriu rasti Ketvirtasis elementas šioje susietą sąrašą, Aš ruošiuosi pradėti pačioje pradžioje sąrašo ir dirbti savo kelią per skaičiavimo mazgas mazgas, kol rasiu ketvirta. 

, Siekiant gauti geresnį našumą, nei susietos sąrašą prieigos - , bet taip pat išlaikyti kai į naudą, kad mes turėjome įterpimo laiko iš susietą sąrašą - dvejetainis medis, reikia naudoti šiek tiek daugiau atminties. Visų pirma, o ne tik vieną žymeklį, dvejetainis medis mazgas - kaip prijungto sąrašą mazgas - mes ketiname pridėti antrą žymiklį į dvejetainis medis mazgas. , O ne tik vieną žymiklį į kito elemento, mes ketiname turėti žymeklį į kairę vaiko ir teisingu vaiko. 

Leiskite atkreipti paveikslėlį, kurį norite pamatyti, ką tai iš tikrųjų atrodo. Vėlgi, aš ruošiuosi naudoti šiuos langelius ir rodyklės. Dvejetainis medis mazgas pradėsite tik paprastas lange. Jis ketina turėti vertės erdvę, ir tada jis taip pat ketina turėti erdvę kairėje vaiko ir dešiniojo vaiko. Aš ruošiuosi čia juos ženklinti. Mes ketiname kairįjį vaiką, ir tada mes ketiname turėti teisę vaiką. Yra daug įvairių būdų, kaip tai daryti. Kartais erdvės ir patogumo, Aš iš tikrųjų padaryti tai, kaip aš darau čia apačioje kur aš ruošiuosi turėti vertę viršuje ir tada vaikas apačioje, dešinėje pusėje, ir kairėje vaikas kairiajame apatiniame. Grįžtant prie šio viršų diagrama, mes turime vertę pačiame viršuje, tada mes turime kairėje ir vaikų rodyklė, ir tada mes turime vaikų dešiniuoju pelės žymeklį. 

Problemą, specifikaciją, mes kalbame apie piešimo mazgas, turi vertę, 7, ir tada kairėje vaikas rodyklę, kad yra niekinis, ir dešiniuoju pelės vaikas rodyklė yra tuščias. Mes galime parašyti kapitalo NULL erdvėje tiek kairėje, tiek vaikas ir teisę vaikui ar mes galime padaryti šį įstrižainės velniop per kiekvieną langelius, nurodyti, kad tai niekinis. Aš ruošiuosi padaryti, kad tik todėl, kad paprasčiau. , Ką jūs matote čia yra du būdai, kaip diagramų labai paprastas dvejetainis medis mazgas kur mes turime vertę 7 ir tuščių vaikų Pointeriai. 

Antroji dalis mūsų specifikacijos diskusijas apie tai, kaip, susijusius sąrašus - Nepamirškite, kad mes tik turėjo eiti į labai pirmąjį elementą į sąrašą prisiminti visą sąrašą - ir taip pat, dvejetainis medis, mes tik eiti į vienos rodyklė į medžio siekiant išlaikyti kontroliuoti visą duomenų struktūros. Šis specialus elementas iš medžio vadinama šakninis mazgas iš medžio. Pavyzdžiui, jei tai vienas mazgas - 7 vertę šis mazgas, kuriame null kairėje ir dešinėje vaikas rodykles buvo tik mūsų medžio vertė, tuomet tai būtų mūsų šakninis mazgas. Tai pati pradžia mūsų medžio. Mes galime matyti, tai šiek tiek aiškiau, kai mes pradėti pridėti daugiau mazgų mūsų medžio. Leiskite man atsigriebti naują puslapį. 

Dabar mes ketiname atkreipti medį, kuris turi 7 šaknų, ir 3 viduje iš kairės vaikui, ir 9 viduje teisinga vaiko. Vėlgi, tai yra gana paprasta. Mes turime 7, parengti už 3 mazgas, mazgas 9 ir aš ruošiuosi nustatyti kairės vaikų žymeklį 7, kad rodytų į mazgą, kuriame yra 3, ir dešiniuoju pelės vaikas mazgo mazge, kuriame 9 7, kuriame rodyklė. Dabar, nes 3 ir 9 neturite jokių vaikų, mes ketiname nustatyti savo vaiko rodykles yra niekinis. Čia, mūsų medžio šaknis atitinka mazgas, kuriame yra 7. Galite matyti, kad, jei viskas, ką turime, yra rodyklė į tą šakninis mazgas, tada mes galime eiti per mūsų medžio ir naudotis ir vaikų mazgai - tiek 3 ir 9. Nereikia išlaikyti patarimų į kiekvieną mazgą ant medžio. Alright. Dabar mes ketiname pridėti dar vieną mazgą šioje diagramoje. Mes ketiname pridėti mazgas, kuriame yra 6, ir mes ketiname pridėti šį elementą kaip teisinga vaiko mazgas, kuriame yra 3. Norėdami tai padaryti, aš ruošiuosi ištrinti, kad null žymeklį 3-mazgas ir vielos, kad rodytų į mazgą, kuriame yra 6. Alright. 

Šiuo metu, geriau patys eikime per šiek tiek terminologijos. Norėdami pradėti, tos priežasties, kad tai ir yra dvejetainis medis, visų pirma yra tai, kad dviejų vaikų patarimų. Yra ir kitų rūšių medžių, kurie turi daugiau vaikų patarimų. Visų pirma, tu "pabandyti" problemą, 5. Jūs pastebėsite, kad toje pabandyti, jums turėjo 27 skirtingų patarimų skirtingiems vaikams po vieną kiekvienai iš 26 anglų abėcėlės raidėmis, ir tada į kabutes 27 - taip, kad panašus į medžio tipo. Bet čia, nes tai dvejetainis, mes tik turime du vaikų patarimų. 

Be to, šio šakninis mazgas, kad mes kalbėjome apie, mes taip pat mesti aplink šį terminą "vaiko". Ką tai reiškia, vienas mazgas būti kito mazgo vaikas? Tai tiesiog reiškia, kad vaikas mazgas yra kitos mazgo vaikas jei tas kitas mazgas turi vieną iš savo vaikų rodykles, kad rodytų į tą mazgą. Norėdami įdėti šią nuorodą į daugiau konkrečiais terminais, jei atkreipė dėmesį į 3 dalis vienu iš vaikų rodykles 7, tada 3 yra 7 vaikas. Jeigu mes buvo išsiaiškinti, kas 7 vaikai - gerai, mes matome, kad 7 turi rodyklę į 3 ir rodyklę iki 9, taip 9 ir 3 yra 7 vaikai. Devyni neturi vaikų, nes jos vaikas patarimų yra nulis, ir 3 turi tik vieną vaiką, 6. Šeši taip pat neturi vaikų, nes abi jos rodykles null, kuriuos mes atkreipti dabar. 

Be to, mes taip pat kalbame apie tam tikro mazgo tėvų, ir tai yra, kaip jūs tikitės, šis vaikas aprašymo reverse. Kiekvienas mazgas turi tik vieną iš tėvų - vietoj dviejų, kaip galite tikėtis su žmonėmis. Pavyzdžiui, 3 tėvų yra 7. 9 iš tėvų taip pat 7 ir 6 tėvų yra 3. Ne per daug į jį. Mes taip pat turime sąlygas, kad kalbėti apie senelių ir vaikaičių, ir apskritai mes kalbame apie protėvių ir palikuonys tam tikro mazgo. Mazgas protėvis - arba protėviai, o mazgas - visų mazgų, kurie laukia kelyje nuo šaknų Šis mazgas. Pavyzdžiui, jei aš žiūriu mazgas 6, tada protėviai bus tiek 3 ir 7. 9 protėviai, pavyzdžiui, - jei aš žiūriu mazgas 9 9 protėvis yra tik 7. Ir palikuonys yra lygiai atvirkščiai. Jei aš noriu pažvelgti iš 7 palikuonių, tada aš turiu pažvelgti visi po juo mazgų. Taigi, turiu 3, 9, ir 6 bet kaip palikuonių 7. 

Galutinis terminas, kad mes kalbame apie tai sąvoka yra broliai ir seserys. Broliai ir seserys - kartu dėl šių šeimos sąlygų rūšies - yra mazgai, kurie yra tame pačiame lygyje medyje. Taigi, 3 ir 9 yra broliai ir seserys, nes jie yra tame pačiame lygyje medyje. Jie abu turi tą pačią tėvų, 7. 6 neturi brolių ir seserų, nes 9 neturi vaikų. Ir 7 broliai ir seserys neturi, nes tai mūsų medžio šaknis, ir ten tik 1 root. For 7 turi brolių ir seserų, ten turi būti virš 7 mazgas. Turėtų būti tėvų 7, 7 byla nebebūtų iš medžio šaknis. Tada, kad naujoji patronuojanti įmonė yra 7, tai taip pat turi turėti vaiką, ir kad vaikas tada būtų 7 broliai ir seserys. 

Alright. Juda. Kai mes pradėjome mūsų diskusiją dvejetainiai medžiai, mes kalbėjome apie tai, kaip mes ketiname juos naudoti siekiant įgyti pranašumą nagrinėti abu masyvai ir susietų sąrašus. Ir tai, kaip mes ketiname daryti, kad su šia užsakymo turto. Mes sakome, kad yra užsakytas, dvejetainis medis pagal specifikacijos jei kiekvieno mūsų medžio mazgas, visų savo palikuonių kairėje - kairėje vaikas ir visa kairiojo vaiko palikuonys - turi mažiau vertybes, ir visus iš dešinėje pusėje mazgų - teisę vaikui ir visų teisių vaiko palikuonys - mazgų didesnis nei dabartinės mazgo vertės, kad mes ieškome. Tiesiog paprastumo, mes ketiname daryti prielaidą, kad nėra dublikato mazgai mūsų medžio. Pavyzdžiui, šio medžio mes neketiname nagrinėti bylą kur mes turime vertę 7 šaknų  ir tada mes taip pat turi vertę 7 kitur į medį. Šiuo atveju, jūs pastebėsite, kad šis medis yra iš tikrųjų užsakė. Mes turime 7 vertę ne šaknis. Viskas į kairę nuo 7 - jei atšaukti visų šių mažai ženklų čia - viskas į kairę nuo 7 - 3 ir 6 - šios vertybės yra tiek mažiau nei 7, ir viskas į dešinę - kuris yra tik tai 9 - yra didesnis kaip 7. 

Tai ne tik užsisakyti medis, kurių sudėtyje yra šių vertybes, tačiau leiskite atkreipti keli iš jų. Yra iš tikrųjų visa krūva būdų, kad mes galime tai padaryti. Aš ruošiuosi naudoti stenografistų tik išlaikyti viskas paprasta, kur - o ne visa dėžės ir strėlės - Aš tik ketina padaryti numerius ir pridėti rodykles juos siejančios. Norėdami pradėti, mes tiesiog parašyti savo medį, kur mes turėjome 7 ir tada 3, ir tada 3 atkreipė į dešinę į 6, ir 7 turėjo teisę vaiką, kuris buvo 9. Alright. Kaip dar galima, kad galėtume rašyti šį medį? Vietoj to, kad 3 yra kairėje vaikas 7 mes taip pat gali turėti 6 yra kairėje vaikas 7 ir tada 3 kairėje vaikas iš 6. , Kad atrodytų kaip šio medžio čia, kur aš turiu 7, tada 6, tada 3, ir dešinėje 9. Mes taip pat neturi turėti 7, kaip mūsų šakninis mazgas. Mes taip pat gali turėti 6 mūsų šakninis mazgas. Ką tai atrodo? Jei mes ketiname išlaikyti tvarkingą turtą, viskas 6 kairėje turi būti mažiau, nei ji. Yra tik viena galimybė, ir tai 3. Bet tada teisinga vaikui nuo 6, turime dvi galimybes. Pirma, mes galime turėti 7 ir tada 9, ar mes galime padaryti tai, kaip aš apie padaryti čia - , kur mes turime 9 dešinėje vaiką iš 6 ir tada kairėje vaiku 9 7. 

Dabar, 7 ir 6 yra ne tik galimos reikšmės šaknų. Mes taip pat gali turėti 3 ne šaknis. Kas atsitiks, jei 3 yra ne šaknis? Čia, ko gauti šiek tiek įdomus. Trys neturi jokių vertybes, kurios yra mažiau, nei ji, kad visa kairioji pusė nuo medžio yra tik ketina, yra niekinis. Ten nebus nieko ten. Į dešinę, galėtume išvardyti dalykus, didėjančia tvarka. Galėtume turėti 3, tada 6, tada 7, tada 9. Arba mes galime padaryti 3, tada 6, tada 9, tada 7. Arba mes galime padaryti 3, tada 7, tada 6, tada 9. Arba, 3, 7 - iš tikrųjų nėra, mes negali padaryti 7 daugiau. Tai mūsų vienas dalykas ten. Mes galime padaryti, 9, ir tada iš 9 mes galime padaryti 6 ir tada 7. Arba mes galime padaryti 3, tada 9, tada 7 ir tada 6. 

Vienas dalykas, kad atkreipti jūsų dėmesį į čia kad šie medžiai yra šiek tiek keistai atrodantį. Visų pirma, jei pažvelgsime į 4 medžių dešinėje pusėje - Aš ratas, čia - šie medžiai atrodo beveik lygiai taip pat kaip susietą sąrašą. Kiekvienas mazgas turi tik vieną vaiką, ir taip mes ne turite kokių nors šio medžio tipo struktūrą, kad mes matome, pavyzdžiui,  šį vieną Lone Tree per čia apačioje kairėje. Šie medžiai yra iš tikrųjų vadinamas peraugti dvejetainiai medžiai, ir mes kalbame apie tai daugiau į ateitį - ypač jei jūs einate imtis kitų informatikos kursus. Šie medžiai yra peraugti. Jie nėra labai naudinga, nes, tiesą sakant, ši struktūra pati savaime  peržvalgos kartus panašius į susietą sąrašą. Mes negalime gauti pasinaudoti papildomos atminties - šį papildomą žymeklį nes mūsų struktūra yra blogai šiuo būdu. O ne eiti ir atkreipti dėmesį į dvejetainius medžius, kurie 9 šaknų, kuris yra galutinis, kad mes turėtume, mes vietoj to, šiuo metu, norėčiau pakalbėti šiek tiek apie šį laikotarpį , kad mes naudojame, kai kalbame apie medžius, kuris yra vadinamas aukštis. 

Iš medžio aukštis yra atstumas nuo šaknų iki labiausiai tolimoje mazgai, arba, tiksliau, apynių, kad jūs turite padaryti, siekiant pradėti nuo šaknų ir tada galų gale labiausiai tolimoje medžio mazgo. Jei pažvelgsime į kai kuriuos iš šių medžių, kad mes sudarytas čia, matome, kad, jei mes šį medį viršutiniame kairiajame kampe, ir mes pradedame ne 3, tada mes turime padaryti 1 hop patekti į 6-2.-hop gauti iki 7, ir trečioji apynių gauti į 9. Taigi, šio medžio aukštis yra 3. Mes galime padaryti tą patį pratimą kitų medžių, išdėstytų šia žaliąja, ir matome, kad visų šių medžių aukštis yra taip pat iš tikrųjų 3. Štai kas leidžia jiems peraugti dalis kad jų aukštis yra tik mažiau nei vienas visą medžio mazgų skaičių. Jei pažvelgsime į šio medžio, kuris apibrauktas raudonai, kita vertus, matome, kad labiausiai toli lapų mazgai yra 6 ir 9 - lapai, kurie yra mazgai, kad neturiu vaikų. Taigi, norint gauti nuo šaknų mazgas arba į 6 arba 9, mes turime padaryti vieną hop gauti iki 7 ir tada antrasis apynių į gauti į 9, ir taip pat, tik antras iš 7-hop gauti į 6. Taigi, šio medžio aukštis virš čia yra tik 2. Jūs galite grįžti ir padaryti, kad visų kitų medžių, kad mes aptarta anksčiau pradedant su 7 ir 6, ir jūs pamatysite, kad visų minėtų medžių aukštis yra 2. 

Priežastis, mes kalbame apie nurodė dvejetainius medžius ir kodėl jie cool, nes jūs galite ieškoti per juos labai panašus būdas ieškoti per rūšiuotų masyvo. Tai yra, kai mes kalbame apie tai, kad geresnės peržvalgos laikas per paprastą susijęs sąrašą. Su susietą sąrašą, jei norite rasti tam tikrą elementą - jūs esate geriausias ketinate daryti kažkokią linijinio paieška kai jūs pradedate sąrašo pradžioje ir apynių vienas po kito - vienas mazgas vienam mazgui - per visą sąrašą, kol rasite bet jūs ieškote. Kadangi tuo atveju, jei turite dvejetainis medis, saugomas, šis gražus formatu, jūs iš tikrųjų galite gauti daugiau dvejetainis paieškos vyksta kur jūs skaldyk ir valdyk ir paieškos per atitinkamą pusmetį kiekviename žingsnyje medžio. Pažiūrėkime, kaip tai veikia. 

Jei mes turime - vėl grįžta į mūsų pradinės medžio - mes pradedame 7, mes turime 3 kairėje, 9 dešinėje, ir po 3 mes turime 6. Jei norime ieškoti šio medžio skaičiumi 6, mes norime pradėti ne šaknis. Mes norėtume palyginti vertę, mes ieškome, tarkim, 6, vertės saugomą mazgo, kad mes šiuo metu ieško, 7, rasti, kad 6 iš tiesų mažiau kaip 7, todėl mes norime judėti į kairę. Jei vertė iš 6 buvo didesnė už 7, mes, atvirkščiai, perkelta į dešinę. Nes mes žinome, kad dėl į mūsų užsakytą dvejetainis medis struktūrą vertės yra mažiau nei 7 ketinate būti saugomi 7 kairėje, nereikia net vargintis ieško per dešinėje pusėje medžio. , Kai mes einame į kairę ir dabar mes mazgas, kuriame yra 3, mes galime padaryti tą patį palyginimą, kur mes palyginti 3 ir 6. Ir mes manome, kad nors 6 - vertė mes ieškome - yra didesnis kaip 3, mes galime eiti į mazgo dešinėje pusėje, kurioje yra 3. Nėra jokios kairėje pusėje, kad galėtume pamiršti, kad. Bet mes žinome, kad tik todėl, kad mes ieškome į medį, ir mes galime pamatyti, kad medis neturi vaikų. 

Jis taip pat yra gana lengva prižiūrėti 6 iš šio medžio, jei mes darome patys, kaip žmonės, bet tegul šį procesą mechaniškai kaip kompiuteryje būtų padaryti tikrai suprasti algoritmą. Šiuo metu, mes dabar žiūri mazgas, kuriame yra 6, ir mes ieškome vertės 6, taip, iš tiesų, mes pastebėjome atitinkamą mazgą. Mes radome 6 vertę mūsų medžio, ir mes galime sustabdyti mūsų paieškos. Šiuo metu, priklausomai nuo to, kas vyksta, mes galime pasakyti, taip, mes vertę 6, jis egzistuoja mūsų medžio. Arba, jei mes planuojame įterpti mazgas ar ką nors, mes galime padaryti, kad šiame taške. 

Padarykime keletą peržvalgų tik pamatyti, kaip tai veikia. Pažvelkime, kas atsitinka, jei mes išbandyti ir ieškoti vertę 10. Jei mes ieškoti vertę 10, mes norėtume pradėti nuo šaknų. Mes norime pamatyti, kad 10 yra didesnė už 7, todėl mes norime judėti į dešinę. Mes norime patekti į 9 ir 10 9 palyginti ir pamatyti, kad 9 iš tiesų yra mažiau nei 10. Taigi dar kartą, mes norime bandyti judėti į dešinę. Tačiau šiuo metu, mes norime pastebėti, kad mes ne nulinis mazgas. Nieko ten. Nėra nieko, kur 10 turėtų būti. Tai vieta, kur mes galime pranešti neįvykdymas - kad iš tiesų į medį 10 ne. Ir, pagaliau, eikime per tuo atveju, kai mes bandome ieškoti 1 į medį. Tai panašu, kas atsitiks, jei mes žiūrime iki 10, išskyrus tuos atvejus, o ne eiti į dešinę, mes ketiname eiti į kairę. Mes pradedame nuo 7 ir matyti, kad 1 yra mažiau nei 7, todėl mes einame į kairę. Mes gauname į 3 ir pamatyti, kad 1 yra mažesnis nei 3, todėl mes dar kartą bandyti judėti į kairę. Šiuo metu mes turime null mazgas, todėl mes vėl gali pranešti apie gedimą. 

Jei jūs norite sužinoti daugiau apie dvejetainiai medžiai, yra visa krūva įdomus mažai problemų, kad jūs galite padaryti su jais. Siūlau praktikuojančių po vieną šių diagramų ir taip per visus skirtingus etapus, , nes tai bus super patogus ne tik, kai jūs darote Huffman Kodavimo problema rinkinys bet ateityje kursų tiesiog išmokti atkreipti dėmesį į šias duomenų struktūras ir apgalvoti problemų su rašiklį ir popieriaus arba, šiuo atveju, iPad ir plunksna. 

Nors šiuo metu, mes ketiname pereiti padaryti tam tikrą kodavimo praktika ir iš tikrųjų žaisti su šių dvejetainiai medžiai ir pamatyti. Aš ketina pereiti atgal į savo kompiuterį. Šio skyriaus, o ne naudojant CS50 Vykdyti arba CS50 Spaces ", Aš ruošiuosi naudoti prietaisą. 

Kartu su problemą, specifikaciją, Matau, kad aš turėjo atverti prietaisą, eikite į mano Dropbox aplanką, sukurti aplanką, pavadintą 7 skirsnis, ir tada sukurti failą pavadinta binary_tree.c. Čia mes einame. Aš turiu prietaisas jau atidarytas. Aš ruošiuosi atsigriebti terminalą. Aš ruošiuosi eiti į Dropbox aplanką, įsitikinkite, katalogą, pavadintą section7, ir pamatyti, tai visiškai tuščias. Dabar aš ruošiuosi atverti binary_tree.c. Alright. Here we go - tuščią failą. 

Grįžkime specifikacijos. Specifikacija prašo sukurti naujo tipo apibrėžimą dvejetainis medis mazgas, kuriame yra int vertybes - kaip ir vertybių, kad atkreipė mūsų diagramų prieš. Mes ketiname naudoti Standartiniai Typedef, kad mes padarėme čia kad jūs turėtumėte suvokti problemą, 5 - jei tu maišos lentelės būdas užkariauja Speller programos. Jūs taip pat turėtų pripažinti, kad iš skyriuje praėjusią savaitę kur mes kalbėjome apie tai, susijusius sąrašus. Mes turime tai Typedef struct mazgas, ir mes Atsižvelgiant į tai struct mazgas šį struct mazgo vardą iš anksto , kad galėtume tada kreiptis į jį, nes mes nori turėti struct mazgas patarimų kaip mūsų struct, bet mes tada apsuptas tai - arba, tiksliau, uždara - Typedef taip, kad vėliau kodą, galime nuorodą į šią struct kaip tik vietoj struct mazgo mazgas. 

Tai bus labai panašus į atskirai, susietą sąrašą apibrėžimą, kad mes matėme praėjusią savaitę. Norėdami tai padaryti, tegul tiesiog pradėti rašyti iš Standartiniai. Mes žinome, kad mes turime turėti skaitinę vertę, todėl mes įdėti int vertės, ir tada, o ne turėti vieną žymiklį į kito elemento - kaip mes padarėme su atskirai susietus sąrašus mes ketiname turėti kairę ir į dešinę vaikų patarimų. Tai gana paprasta, taip pat - Struct mazgas * kairėje vaikas; ir Struct mazgas * dešinė vaikas;. Cool. Tai atrodo gana gera pradžia. Grįžkime specifikacijos. 

Dabar mes turime paskelbti pasaulinį mazgas * kintamąjį medžio šaknis. Mes ketiname padaryti tai pasaulio, kaip mes pirmą rodyklę Susietos sąrašą taip pat pasaulio. Tai buvo taip, kad funkcijų, kad mes rašome mes neturime išlaikyti einančios aplink Ši šaknis - nors mes pamatysime, kad jei jūs norite parašyti šias funkcijas rekursyviai, jis gali būti geriau net perduoti jį aplink kaip į pirmąją vietą pasaulio ir vietoj to initialize lokaliai savo pagrindinę funkciją. Tačiau, mes tai padaryti visame pasaulyje pradėti. Vėlgi, mes duosiu keletą erdvių, ir aš einu paskelbti mazgas * šaknis. Tiesiog įsitikinkite, kad aš ne palikti šį niezainicjowanymi, aš nustatyti, kad jis lygus nulis. Dabar pagrindinė funkcija - mes rašyti tikrai greitai čia - int main (int argc, const char * argv []) - ir aš ruošiuosi pradėti pripažinti savo argv masyvas kaip const tik todėl, kad aš žinau, kad šie argumentai yra argumentai, kad aš tikriausiai nenori keisti. Jei aš noriu juos pakeisti, aš tikriausiai turėtų būti padaryti jų kopijas. Jūs pamatysite šį kodą daug. Tai gerai bet kuriuo atveju. Tai gerai, palikti jį praleisti const, jei norite. Aš paprastai įdėti jį tik todėl, kad aš priminti sau,  , kad aš tikriausiai nenorite keisti šiuos argumentus. 

Kaip visada, aš ruošiuosi šį return 0 liniją pagrindinis pabaigoje. Čia, aš inicijuoti mano šakninis mazgas. , Kokia ji yra dabar, aš turiu rodyklę, kad nustatyta reikšmė NULL, todėl jis rodo nieko. Tam, kad iš tikrųjų pradėti statybos mazgas, Aš pirmiausia reikia skirti atminties. Aš ruošiuosi padaryti, kad atmintis malloc krūvos. Aš ruošiuosi nustatyti vienodas šaknis į malloc rezultatas, ir aš ruošiuosi naudoti sizeof operatoriaus mazgo dydį apskaičiuoti. Priežastis, kad aš naudoju, sizeof mazgas, o ne, tarkim, daryti kažką panašaus į tai - malloc (4 + 4 +4) arba malloc 12 - yra todėl, kad aš noriu, kad mano kodas turi būti kuo labiau suderintos. Aš noriu, kad būtų galima pasinaudoti šia C failą, kaupia jį ant prietaiso, ir kaupia jį ant mano 64-bitų "Mac - arba visiškai skirtingos architektūros ir aš noriu, kad visa tai veikia taip pat. 

Jei aš darant prielaidas apie kintamųjų dydžio int ar rodykle dydžio dydis - tada aš taip pat darant prielaidas apie architektūrų rūšių mano kodas gali sėkmingai sudaryti, kai paleisti. Sizeof visada naudoti, o ne rankiniu būdu sudedant struct laukus. Kita priežastis yra tai, kad taip pat gali būti prikimšti, kad kompiliatorius pradeda struct. Net tik sudedant atskirų laukų nėra kažkas, kad jūs paprastai nori daryti, taip, ištrinti tą eilutę. Dabar tikrai inicijuoti šį šakninis mazgas, Aš ruošiuosi turite prijungti verčių kiekvienam savo įvairių sričių. Pavyzdžiui, vertės, aš žinau, aš noriu inicijuoti iki 7, ir dabar aš ruošiuosi kairėje vaikas yra niekinis ir teisę vaikui taip pat turi būti nulinis. Puiku! Mes padarėme, kad spec dalis. 

Specifikacija 3 psl apačioje prašo manęs sukurti tris daugiau mazgų - Kurių sudėtyje yra ne daugiau kaip 3, vienas yra 6, ir vienas su 9 - ir tada pervesti juos, todėl jis atrodo lygiai taip pat kaip mūsų medžio diagrama , kad mes kalbame apie anksčiau. Darykime, kad gana greitai čia. Jūs pamatysite labai greitai, kad aš ruošiuosi pradėti rašyti pasikartojančių kodas krūva. Aš ruošiuosi sukurti mazgas * ir aš ruošiuosi jį pavadinti 3. Aš ruošiuosi nustatyti, kad jis lygus malloc (sizeof (mazgas)). Aš ruošiuosi nustatyti trys-> value = 3. Trys -> left_child = NULL, trys -> į dešinę _child = NULL, taip pat. Kad atrodo gana panašus į Inicijuojama šaknis, ir tai yra būtent tai, ko Aš ruošiuosi daryti, jei aš pradedu Inicijuojama 6 ir 9 straipsniuose, taip pat. Aš padarysiu, kad tikrai greitai čia - iš tiesų, aš padaryti šiek tiek kopijuoti ir įklijuoti, ir įsitikinkite, kad aš - viskas tvarkoj.  Dabar, aš turiu jį nukopijuoti ir aš galiu eiti į priekį ir nustatyti tai, lygus 6. Jūs galite pamatyti, kad tai trunka kurį laiką ir nėra itin efektyvus. Tik šiek tiek, mes parašyti funkciją, kuri bus tai padaryti už mus. Aš noriu pakeisti, tai su 9, pakeisti, kad su 6. 

Dabar mes turime visus mūsų mazgų sukurta ir inicializuoti. Mes turime mūsų šaknis nustatyti lygi 7, arba kurių sudėtyje yra vertę 7 mūsų mazgas, kurioje yra 3, mūsų mazgas yra 6, o mūsų mazgas yra 9. Šiuo metu, visi mes turime padaryti, yra vielos viską aukštyn. Priežastis, kodėl aš inicijuoti visų patarimų nulis yra tik todėl, kad aš įsitikinkite, kad Aš neturiu ten jokių niezainicjowanymi patarimų dėl nelaimingo atsitikimo. Ir taip pat nuo, šiuo metu, aš tik turi realiai prisijungti mazgai vienas su kitu - į tuos, kurie, kad jie iš tikrųjų susijusių Aš neturiu eiti ir padaryti tikrai, kad visi nulls ten į reikiamas vietas. 

Pradedant nuo šaknų, žinau, kad root kairėje vaikas 3. Aš žinau, kad root teisės vaikui yra 9. Po to, tik kitas vaikas, kad man liko nerimauti yra 3 teisingas vaikas, kuris yra 6. Šiuo metu, viskas atrodo gana gerai. Mes ištrinti kai kuriuos iš šių eilučių. Dabar viskas atrodo gana gerai. Grįžkime mūsų specifikacija ir pamatyti, ką mes turime daryti toliau. 

Šiuo metu, mes turime rašyti funkcija, vadinama "yra" "bool Sudėtyje yra (int vertė)" prototipas. Ir tai yra funkcija return true  jei atkreipė dėmesį į mūsų pasaulio šaknies kintamojo medis  yra vertę perėjo į funkcijos ir klaidingas kitaip. Eikime į priekį ir padaryti, kad. Tai bus lygiai taip pat kaip peržvalgos, kad mes padarėme ranka iPad truputį prieš. Tegul padidinti šiek tiek ir slinkdami aukštyn. Mes ketiname įdėti šią funkciją, tiesiai virš mūsų pagrindinė funkcija kad mes neturime daryti jokių prototipų rūšiuoti. Taigi, bool yra (int vertė). Čia mes eiti. Mūsų Standartiniai deklaracija. Tiesiog įsitikinkite, kad tai bus sudaryti, Aš ruošiuosi eiti į priekį ir tik nustatyti, kad jis lygus gražins false. Dabar ši funkcija tiesiog nebus nieko daryti ir visada teigia, kad ta vertybė, kad mes ieškome ne į medį. 

Šiuo metu, tai tikriausiai gera idėja - nes mes jau parašyta visa krūva kodo, ir mes net bandė išbandyti jį dar įsitikinti, kad visa tai rengia. Yra pora dalykų, kad mes turime padaryti, siekiant įsitikinti, kad tai iš tikrųjų sudaryti. Pirma, pamatyti, jei mes jau naudoju bet kokius bet kokių bibliotekų funkcijas, kad mes dar nėra įtrauktos. Funkcijos, mes naudojame iki šiol yra malloc, ir tada mes taip pat naudojant šio tipo - šį nestandartinį tipas vadinamas "bool' , kuris yra įtrauktas į standartinę Bool antraštės faile. Mes tikrai norite įtraukti standartinę už bool tipo bool.h, ir mes taip pat norime # include standartinę standartinių bibliotekų lib.h kad malloc ir nemokamai, ir visa tai. Taigi, nutolinti, mes ruošiamės mesti rūkyti. Pabandykime ir įsitikinti, kad tai iš tikrųjų kompiliavimo. Mes matome, kad jis, kad esame teisingame kelyje. 

Tegul atverti binary_tree.c vėl. Ji rengia. Eikime ir įsitikinkite, kad mes įterpti keletą skambučius į mūsų Sudėtyje yra funkcija - tiesiog įsitikinkite, kad viskas gerai ir gerai. Pavyzdžiui, kai mes padarėme kai kuriuos mūsų medžio paieška ir anksčiau, mes bandėme ieškoti vertes, 6, 10, ir 1, ir mes žinojome, kad 6 medyje, 10 buvo ne į medį, ir 1 ne į medį. Leiskite naudoti imties skambučius, tokiu būdu išsiaiškinti, ar mūsų Contains funkcija veikia. Tam, kad padaryti, kad aš ruošiuosi naudoti printf funkciją, ir mes ketiname atsispausdinti raginimą kuriame rezultatą. Aš ruošiuosi įdėti į eilutę "Sudėtyje yra (% d) =, nes  mes ketiname prijungti vertės, kad mes ketiname ieškoti, =% s \ n "ir naudoti, kad mūsų formato eilutę. Mes tiesiog ketiname pamatyti - tiesiog atspausdinti ekrane kas atrodo skambinimo funkcijos. Tai nėra iš tikrųjų funkcija skambinti.  Tai tik eilutė, skirta atrodyti skambinimo funkcijos. 

Dabar mes ketiname prijungti vertybėmis. Mes ketiname bandyti yra apie 6, ir po to, ką mes ketiname daryti čia yra naudoti, kad trijų komponentų operatorių. Pažiūrėkime, - yra 6 - taip, dabar aš yra 6, ir jei turi 6 yra tiesa, eilutė, kad mes ketiname siųsti% s formatas pobūdžio bus eilutė "true". Leiskite slinkti per šiek tiek. Priešingu atveju, mes norime siųsti eilutė "false", jei yra 6 False. Tai yra šiek tiek Goofy ieškote, bet aš paveikslą aš taip pat iliustruoja Ternary operatorius atrodo, nes mes nemačiau kurį laiką. Tai bus gražus, patogus būdas išsiaiškinti, ar mūsų Contains funkcija veikia. Aš ruošiuosi slinkti atgal perkelti į kairę, ir aš ruošiuosi, nukopijuokite ir įklijuokite šią eilutę kelis kartus. Pasikeitė kai kurie iš šių verčių aplink, todėl tai bus 1, o tai bus 10. 

Šiuo metu mes turime gražią Sudėtyje yra funkcija. Mes turime tam tikrus tyrimus, ir mes pamatyti, jei visa tai veikia. Šiuo metu mes parašiau šiek tiek daugiau kodą. Laikas mesti, ir įsitikinkite, kad viskas dar rengia. Mesti, o dabar pabandykime vėl dvejetainis medis. Na, atrodo, kad mes turime klaidą Ir mes turime tai aiškiai skelbiantis bibliotekos funkcija printf. Atrodo, kad mes turime eiti ir # include standardio.h. O, kad viskas turėtų sudaryti. Mes visi gerai. Dabar pabandykime paleisti dvejetainis medis, ir žiūrėsime kas atsitiks. Mes čia,. / Binary_tree ir mes matome, kad, kaip ir tikėjomės - nes mes ne įgyvendintos, yra dar arba, tiksliau, mes tiesiog įdėti Return FALSE - matome, kad ji manimi tik grįžau false juos visus, kad didžiąja dalimi visi dirba pakankamai gerai. 

Eikime atgal ir iš tikrųjų įgyvendinti yra šiuo metu. Aš ruošiuosi slinkti žemyn, padidinti, ir - atminkite, kad mes naudojamas algoritmas buvo, kad mes pradėjome šakninis mazgas , o vėliau kiekvieną mazgą, kad mes susiduriame, mes palyginti ir remiantis šio palyginimo, mes arba judėti į kairę vaikui, ar į dešinę vaikui. Tai va, atrodo labai panaši į dvejetainis paieškos kodą, kad mes parašė anksčiau termino. Kai mes pradėti žaisti, mes žinome, kad nori eiti į dabartinio mazgo , kurioje mes ir būti inicializuoti su šakninis mazgas mazgas. Ir dabar, mes ketiname nuolat išgyvena medžio, ir prisiminti, kad mūsų stabdymo sąlygą -  kai mes iš tikrųjų dirbo per pavyzdyje ranka - buvo, kai mes susidūrėme su null mazgas, kai mes pažvelgė neapibrėžta vaikui, , o tada, kai mes iš tikrųjų persikėlė į mazgo į medį ir nustatė, kad mes ne nulinis mazgas. Mes ketiname pakartoti iki dab nėra lygus NULL. Ir ką mes ketiname daryti? Mes ketiname išbandyti, jei (dab -> == vertė), tada mes žinome, kad mes iš tikrųjų surado mazgas, mes ieškome. Taigi čia, mes galime grįžti tiesa. Priešingu atveju, mes norime pamatyti, ar vertė yra mažesnė už vertę,. Jei dabartinės mazgo vertė yra mažesnė už vertę, mes ieškome, mes ketiname pereiti į dešinę. Taigi, dab = Suo -> right_child; ir kitaip, mes ketiname judėti į kairę. dab = dab -> left_child;. Gana paprasta. 

Jūs tikriausiai pripažinti kilpa, kuri atrodo labai panašus į šį dvejetainis paieškos anksčiau termino, išskyrus tada mes buvo susijusios su mažos, vidutinės ir aukštos. Čia, mes tiesiog turime pažvelgti į dabartinės vertės, todėl gražus ir paprastas. Padarykime, kad šis kodas veikia. Pirmiausia, įsitikinkite, kad ji rengia. Atrodo, kad ji veikia. Pabandykime paleisti jį. Ir iš tiesų, tai spausdina viską, kad tikėjomės. Ji nustato, 6 medyje, nemano, kad 10, nes 10 ne į medį, ir nemano, kad nors 1, nes 1 taip pat ne į medį. Cool stuff. 

Alright. Grįžkime mūsų specifikacija ir pamatyti, kas toliau. Dabar jis nori pridėti šiek tiek daugiau mazgų mūsų medžio. Jis nori pridėti 5, 2 ir 8, ir įsitikinkite, kad mūsų yra kodas vis dar veikia taip, kaip tikėtasi. Eikime daryti. Šiuo metu, o ne daro, kad erzina kopijuoti ir įklijuoti vėl, tegul parašyti funkciją, kad iš tikrųjų sukurti mazgas. Jei mes slinkti žemyn visą kelią į pagrindinį, matome, kad mes jau tai daryti labai panašus kodas vėl ir vėl kiekvieną kartą, kad mes norime sukurti mazgas. 

Tegul parašyti funkciją, kad tikrai bus statyti mazgas mums ir grąžinti jį. Aš ruošiuosi jį vadinti build_node. Aš ruošiuosi sukurti mazgas su konkrečios vertės. Padidinti čia. Pirmas dalykas, aš ruošiuosi daryti iš tikrųjų sukurti vietos krūvos mazgas. Taigi, mazgas * n = malloc (sizeof (mazgas)), n -> = vertė; ir tada čia, aš tik ketina inicijuoti visus laukus būti atitinkamas vertes. Ir pačioje pabaigoje, sugrįšime mūsų mazgas. Alright. Vienas dalykas, reikia pažymėti, kad šią funkciją čia vyksta grąžina rodyklę į atmintį, kad buvo krūva skirtos. Kas yra malonu apie tai, kad šis mazgas - mes turime paskelbti ją suderinama su bendrąja rinka. krūvą, nes jei mes paskelbė jį ant kamino mes negalėtų tai padaryti šią funkciją, kaip šis. Kad atmintis būtų išeiti iš taikymo srities ir negalioja, jei mes bandėme kreiptis į jį vėliau. Kadangi mes skelbiantis krūva skirtos atminties, mes ketiname rūpintis išlaisvinant jį vėliau mūsų programos negalėtų ištekėti bet kokią atmintį. Mes jau Punting, kad visa kita kodą tik Paprastumo dėlei metu, tačiau, jei jūs kada nors parašyti funkciją, kuri atrodo taip kur jūs turite kai ją vadina malloc arba realloc viduje - jūs norite įsitikinti, kad jūs įtraukėte kažkokią komentarų čia, kad sako, ei, juk žinot, grąžina krūva skirtos praėjo vertės inicijuotas mazgas. Ir tada jūs norite įsitikinti, kad jūs įtraukėte į kažkokiu pastabos, kad sako skambinantysis turi išlaisvinti grįžo atmintį. Tokiu būdu, jei kas nors kada nors eina, ir naudoja šią funkciją, jie žino, kad ką jie grįžti iš šios funkcijos tam tikru momentu turės būti išlaisvintas. 

Darant prielaidą, kad viskas yra gerai ir gera čia, mes galime eiti į mūsų kodą ir pakeisti visi šių eilučių čia skambučius į mūsų statyti mazgo funkcijos. Darykime, kad tikrai greitai. Viena dalis yra tai, kad mes neketiname pakeisti dalis žemyn čia apačioje, kur mes iš tikrųjų viela iki mazgai vienas su kitu, dėl to, kad mes negalime padaryti savo funkcijas. Bet, darykime root = build_node (7); mazgas * trys = build_node (3); mazgas * 6 = build_node (6); mazgas * 9 = build_node (9);. Ir dabar, mes taip pat norėjo pridėti mazgų - mazgas * 5 = build_node (5); mazgas * 8 = build_node (8); ir kas buvo kitas mazgas? Pažiūrėkime čia. Mes norėjome taip pat pridėti 2 - mazgas * 2 = build_node (2); Alright. Šiuo metu, mes žinome, kad mes turime 7, 3, 9, ir 6 visi laidinio tinkamai, bet ką galima pasakyti apie 5, 8, o 2? Išlaikyti viskas kaip pridera, mes žinome, kad 3 teisė vaikui yra 6. Taigi, jei mes ketiname pridėti 5, 5 taip pat priklauso į dešinę iš medžio, iš kurių 3 yra šaknis, taip 5 priklauso kairėje vaikui nuo 6. Mes galime tai padaryti, sakydamas: 6 -> left_child = penki; ir tada 8 priklauso kairėje vaiku 9, todėl devintų -> left_child = 8; ir tada 2 yra kairėje vaikas 3, todėl mes galime padaryti, kad čia - tave -> left_child = dvi; Jei tu ne visai sekti kartu su tuo, aš siūlau jums padaryti ją sau. 

Alright. Išsaugokime tai. Eikime ir įsitikinkite, kad ji rengia, ir tada mes galime įdėti mūsų Contains skambučius. Atrodo, viskas vis dar rengia. Eikime ir pridėti kai yra skambučius. Vėlgi, aš ruošiuosi daryti šiek tiek kopijuoti ir įklijuoti. Dabar galime ieškoti 5, 8 ir 2. Alright. Kurkime tikri, kad visa tai gerai atrodo dar. Puiku! Išsaugoti ir išeiti. Dabar padarykime, kaupti, ir dabar galime paleisti. Iš gautų rezultatų, atrodo, viskas veikia tiesiog gražus ir gerai. Puiku! Taigi dabar mes turime parašyta mūsų Contains funkciją. Pereikime ir pradėti dirbti, kaip įterpti į medį mazgų , nes, kaip mes darome tai dabar, viskas nėra labai gražus. 

Jei mes einame atgal į specifikaciją, jis klausia mums parašyti funkcija vadinama įterpti - vėl grįžta bool ar mes iš tikrųjų galėtų įterpti į medį mazgas - ir tada reikšmė, įterpti į medį, yra nurodyta kaip Vienintelis argumentas mūsų įterpti funkciją. Mes grąžina true, jei mes iš tiesų galėtų įterpti mazgo, kuriame vertę į medį, , o tai reiškia, kad mes, vienas, turėjo pakankamai atminties, ir tada du, kad mazgas nebuvo jau egzistuoja į medį, nes - Nepamirškite, kad mes neketiname turėti pasikartojančius vertybes į medį, tik kad viskas paprasta. Alright. Atgal, kad kodą. Atidarykite jį. Padidinti šiek tiek, tada slinkite žemyn. Tegul įterpimo funkciją tiesiai virš sudėtį įeina. Vėlgi, tai bus vadinama bool įterpti (int vertė). Suteikite jam šiek tiek daugiau erdvės, ir tada, kaip numatytąjį, tegul Return FALSE pačioje pabaigoje. Dabar žemyn apačioje, eikime į priekį ir, o ne rankiniu būdu pastato mazgai Pagrindinis save ir instaliacijos juos vienas su kitu, kaip mes darome, mes pasikliauti mūsų įterpti funkciją, kaip tai padaryti. Mes negali remtis mūsų įterpti funkciją, sukurti visą medį nuo nulio tik dar, , o mes atsikratyti šių eilučių - we'll pastabas iš šių linijų - kad sukurti mazgai 5, 8 ir 2. Ir vietoj to, mes įterpti skambučius į mūsų įterpti funkciją įsitikinti,, kad tai iš tiesų veikia. Čia mes einame. 

Dabar mes komentavo šias eilutes. Turime tik 7, 3, 9, ir 6 Šiuo metu mūsų medžio. Norėdami įsitikinti, kad tai yra visi dirba, mes galime nutolinti, kad mūsų dvejetainis medis, paleiskite jį ir matome, kad yra dabar mums sako, kad mes visiškai teisus - 5, 8 ir 2 nebėra į medį. Grįžti į kodą, ir kaip mes ketiname įterpti? Prisiminkite, ką mes padarėme, kai mes iš tikrųjų buvo įterpiant 5, 8 ir 2 anksčiau. Mes grojo, kad Plinko žaidimas, kur mes pradėjome ne šaknis, sumažėjo medžio vieną po vieną kol mes radome tinkamą spragą, ir tada mes laidinio mazgas ne tinkamoje vietoje. Mes ketiname padaryti tą patį. Tai iš esmės kaip rašyti kodą, kad mes panaudojome yra funkcija rasti vietoje, kur turėtų būti mazgas, ir tada mes tiesiog įterpti mazgas. Pradėkime tai daro. 

Taigi, mes turime mazgas * dab = root, mes tiesiog sekti, yra kodas kol mes suprato, kad tai ne visai dirbti pas mus. Mes ketiname eiti per medį, o dabartinis elementas nėra lygus nuliui, ir jei mes to dab vertė yra lygi vertės, kad mes bandome įterpti - gerai, tai vienas iš atvejų, kuriais mes tikrai negalėjo įterpti mazgas į medį, nes tai reiškia, kad turime pasikartojančią reikšmę. Čia mes iš tikrųjų ketiname gražins false. Dabar, dar jei dab vertė yra mažesnė nei vertės, dabar mes žinome, kad mes einame į dešinę  nes vertė priklauso dešinėje pusėje dab medžio. Priešingu atveju, mes ketiname pereiti į kairę. Tai iš esmės mūsų Contains veikti tiesiai ten. 

Šiuo metu, kai baigsime šį while cikle, mūsų dab rodyklė turi būti nukreipta į null jei ši funkcija nėra jau grįžo. Todėl mes dab toje vietoje, kur mes norime įterpti naują mazgas. Ką dar reikia padaryti, kad iš tikrųjų sukurti naują mazgas, mes galime padaryti gana lengvai. Mes galime naudoti mūsų super patogu statyti mazgo funkciją, ir kažkas, kad mes nepadarė anksčiau - Mes tiesiog rūšies laikė savaime suprantamu, bet dabar mes padaryti, tiesiog įsitikinkite, kad mes išbandyti, įsitikinti, kad iš tikrųjų buvo grąžinta reikšmė pagal naujas mazgas nėra lygus nuliui, nes mes nenorime pradėti pasiekti tą atmintį, jei jis yra niekinis. Mes galime tai patikrinti, įsitikinti, kad naujas mazgas nėra lygus NULL. Arba vietoj, mes galime tik pamatyti, jei ji iš tikrųjų yra niekinis, ir, jei jis yra niekinis, tada mes galime tik gražins false anksti. 

Šiuo metu, mes turime pervesti naują mazgas į jo tinkamoje vietoje medyje. Jei pažvelgsime atgal pagrindinis ir, jei mes iš tikrųjų vertybių laidų ir anksčiau, mes matome, kad tai, kaip mes darome tai, kai mes norėjome įdėti į medį 3 mes buvo atvertas kairįjį vaiką root. Kai mes įdėti 9 į medį, mes turėjome prieiti prie tos šaknų vaikas. Mums reikėjo žymiklį į tėvų, siekiant pradėti taikyti naują vertę į medį. SCROLLING Atgal į viršų įterpti, kad nesiruošia gana dirbti čia nes mes neturime patronuojanti žymeklį. Ką mes norime, kad būtų galima tai padaryti, yra šiuo metu, patikrinti tėvų vertę ir pamatyti, - gerai, GOSH, jei patronuojančios įmonės turto vertė yra mažesnė nei dabartinės vertės, tėvų teisė Vaikas turi būti naujas mazgas; kitaip, kairėje tėvų vaikas turėtų būti naujas mazgas. Tačiau, mes ne turėti šią patronuojančią žymeklį gana dar. 

Tam, kad jį gauti, mes iš tikrųjų ketiname jį sekti, kaip mes einame per medžio ir rasti tinkamą mūsų kilpa virš vietoje. Mes galime padaryti, kad slinkimo atgal iki mūsų įterpti funkciją viršuje ir stebėjimo kitą žymiklio kintamasis vadinamas tėvų. Mes ketiname nustatyti, kad jis lygus nulis pradžių, ir tada kiekvieną kartą, mes einame per medžio, mes ketiname nustatyti tėvų žymeklį, kad atitiktų esamą žymeklį. Nustatyti tėvų lygią dab. Tokiu būdu, kiekvieną kartą, mes einame per mes ketiname užtikrinti, kad, kaip dabartinę poziciją gauna padidinamas patronuojanti rodyklė taip - tik vienas lygis didesnis nei dabartinis rodyklė medyje. Kad visi atrodo gana gerai. 

Manau, kad vienas dalykas, kad mes norite reguliuoti tai sukurti mazgas grįžtantį null. Siekiant gauti statyti mazgas sėkmingai grąžina NULL, mes turime pakeisti tą kodą, nes čia, mes niekada išbandyti, įsitikinti, kad malloc grąžino galiojantį žymeklį. Taigi, jei (n = NULL), tada - jei malloc grąžino galiojantį žymeklį, tada mes inicijuoti; kitaip, mes tiesiog grįžti ir, galų gale grįžta null mums. Dabar viskas atrodo gana gera. Galime padaryti, kad tai iš tikrųjų kaupia. Padaryti dvejetainis medis, ir oh, mes turime kai kurių dalykų čia vyksta. 

Mes turime numanoma deklaracija funkcija kurti mazgas. Vėlgi, šių kompiliatorius, mes ketiname pradėti viršuje. Kas, kad turi reikšti, kad vadinu sukurti mazgas, aš iš tikrųjų paskelbė jį. Eikime vėl į kodą tikrai greitai. Slinkti žemyn, ir tikrai pakankamai, mano įterpti funkciją pareiškė virš build mazgo funkciją, bet aš bandau naudoti kurti mazgas viduje įdėklu. Aš ruošiuosi eiti ir kopiją - ir tada įklijuokite statyti mazgas funkcija čia viršuje. Kad taip, tikiuosi, kad veiks. Leiskite duoti kitą eiti. Dabar visa tai rengia. Viskas yra gerai. 

Tačiau šiuo metu, mes ne iš tikrųjų vadinamas mūsų įterpti funkciją. Mes tiesiog žinau, kad ji rengia, tad eikime ir įdėti kelis skambučius in Darykime, kad mūsų pagrindinė funkcija. Čia mes komentavo, 5, 8 ir 2, ir tada mes ne vielos juos čia. Galime padaryti, kai ragina įterpti, ir tegul taip pat naudoti tos pačios rūšies daiktų, kad mes naudojamas , kai mes padarėme šias printf ragina įsitikinti, kad viskas buvo gauti įdėta tinkamai. Aš ruošiuosi kopijuoti ir įklijuoti, ir vietoj yra, mes ketiname padaryti įdėklą. Ir vietoj 6, 10 ir 1, mes ketiname naudoti 5, 8 ir 2. Tai turėtų tikiuosi įterpti 5, 8 ir 2 į medį. Surinkti. Viskas yra gerai. Dabar mes iš tikrųjų paleisti mūsų programą. 

Viskas grįžo klaidinga. Taigi, 5, 8 ir 2 ne eiti, ir atrodo, kad Contains nerado arba. Kas vyksta? Leiskite nutolinti. Pirmoji problema buvo, kad įterpti atrodė, kad gražins false, ir atrodo, kaip tai todėl, kad mes palikome mūsų Return FALSE skambučio, ir mes niekada iš tikrųjų grįžo tiesa. Mes galime nustatyti, kad iki. Antroji problema yra, dabar, net jei mes darome - išsaugoti, mesti, paleisti, kad vėl, tai kaupti, tada paleiskite ją - matome, kad kažkas čia nutiko. 5, 8, ir 2 buvo dar niekada nebuvo rasta medyje. Taigi, kas vyksta? 

Paimkime pažiūrėk kode. Leiskite pamatyti, jei mes galime suprasti tai. Mes pradedame su patronuojanti nėra null. Mes nustatyti dabartinę žymeklį prilygstantį į šakninį rodyklė, ir mes ketiname dirbti savo kelią žemyn per medžio. Jei dabartinė mazgas nėra lygus nuliui, tada mes žinome, kad galime perkelti šiek tiek. Mes nustatome mūsų tėvų žymeklį turi būti lygus su dabartine rodyklė, patikrinti vertę, jei vertybės yra tos pačios, mes grįžo klaidinga. Jeigu vertės yra mažesnės, mes persikėlė į dešinę; kitaip, mes persikėlė į kairę. Tada mes sukurti mazgas. Aš padidinti šiek tiek. Ir čia mes ketiname pabandyti pervesti vertybes, yra tas pats. Kas vyksta? Leiskite pamatyti, jei galbūt Valgrind gali duoti užuominą. 

Man patinka naudoti Valgrind tik todėl, kad Valgrind tikrai greitai veikia ir jums pasakys, jei yra kokių nors atminties klaidos. Kai mes paleisti Valgrind kodą, kaip matote teisę here--Valgrind./binary_tree--and paspauskite Enter. Jūs matote, kad mes neturėjo atminties klaidos, todėl atrodo, kad viskas bus gerai iki šiol. Mes turime kai kuriuos atminties nutekėjimas, kurį mes žinome, nes mes ne vyksta išlaisvinti mūsų mazgų. Pabandykime veikia GDB pamatyti, kas iš tikrųjų vyksta. Mes padarysime gdb / binary_tree. Jis įkrautas iki tik baudą. Leiskite nustatyti pertraukos tašką įdėklu. Leiskite paleisti. Atrodo, kad mes niekada iš tikrųjų vadinamas įterpti. Atrodo, kad problema buvo tik tai, kad, kai aš pakeičiau čia pagrindinis - šių printf skambučių iš yra Aš niekada iš tikrųjų pasikeitė, skambinti įdėklą. Dabar tegul give it a try. Leiskite sudaryti. Viskas atrodo gerai. Dabar pabandykime paleisti jį, pamatyti, kas atsitiks. Sutinku! Viskas atrodo gana gerai ten. 

Galutinis dalykas, galvoti apie tai, ar yra kokių nors krašto atvejai intarpu? Ir paaiškėja, kad gerai, vienu kraštu, kad visada yra įdomu galvoti apie tai, kas atsitinka, jei jūsų medis yra tuščia ir skambinate šį įterpti funkciją? Ar jis veikia? Ką gi, give it a try. - Binary_tree c - Taip, kaip mes ketiname išbandyti šį, mes ketiname eiti į mūsų pagrindinė funkcija, ir, o ne laidų Šie mazgai panašaus į tai, mes tik ketina komentaras iš visą dalykas, ir vietoj mazgų save laidus, mes iš tikrųjų galite tiesiog eiti į priekį ir trinti visa tai. Mes ketiname, kad viskas pokalbį įterpti. Taigi, galime daryti - vietoj 5, 8 ir 2, mes ketiname įterpti 7, 3, ir 9. Ir tada mes taip pat norite įterpti 6, taip pat. Įrašyti. Baigti. Padaryti dvejetainis medis. Visa tai rengia. Mes galime tiesiog paleisti jį ir pamatyti, kas atsitiks, tačiau ji taip pat bus tikrai svarbu įsitikinti, kad mes neturime jokių atminties klaidų, , nes tai yra vienas iš mūsų krašto atvejų, kad mes žinome apie. 

Leiskite įsitikinkite, kad jis veikia gerai, pagal Valgrind kuriuos mes tiesiog veikia Valgrind / binary_tree. Atrodo, kad mes iš tikrųjų turi vieną klaidą iš vieno konteksto - mes turime šį segmentavimo kaltės. Kas atsitiko? Valgrind tikrųjų mums sako, kur ji yra. Šiek tiek nutolinti. Atrodo, kad jis vyksta mūsų įterpti funkciją, kur mes turime neteisingą paskaityti dydis 4 įdėklo, eilutė 60. Eikime atgal ir pamatyti, kas čia vyksta. Nutolinti tikrai greitai. Noriu įsitikinti, kad jis neturi eiti į ekrano kraštą, kad mes galime pamatyti viską. Traukti, kad šiek tiek. Alright. Slinkti žemyn, ir problema yra čia. Kas atsitiks, jei mes ir mūsų dabartinis mazgas yra jau null, mūsų pagrindinė mazgas yra nulis, todėl, jei mes ieškoti pačiame viršuje, čia - jei tai while cikle niekada faktiškai vykdo nes mūsų dabartinė vertė yra niekinis - mūsų šaknis yra niekinis, todėl dab yra niekinis - tada mūsų tėvų niekada pasireiškia dabartiniu arba galiojantį vertės, taip, tėvai taip pat turi būti nulinis. Mes turime prisiminti, siekiant patikrinti, ar iki to laiko mes kibti čia, ir mes pradedame gauti tėvų vertę. Taigi, kas atsitinka? Na, jei vienas iš tėvų yra niekinis - if (patronuojanti == NULL) - tada mes žinome, ten neturi būti nieko į medį. Mes turime būti bando įterpti jį į šaknis. Mes galime padaryti, kad tiesiog šaknis lygi į naujas mazgas. Tada šiuo metu, mes ne iš tikrųjų nori eiti per šių kitų dalykų. Vietoj to, čia, mes galime nors kitur, jei dar, ar mes galime derinti viską, čia dar, bet čia mes tiesiog naudoti kitur, ir tai padaryti, kad taip. Dabar mes ketiname išbandyti, ar gerai, kad mūsų tėvų nėra lygus nuliui iki to laiko iš tikrųjų bando prieiti prie savo laukus. Tai padės mums išvengti segmentavimo kaltės. Taigi, mes mesti, nutolinti, kaupti, paleisti. 

Jokių klaidų, tačiau mes vis dar turime krūva atminties nutekėjimas nes mes ne nemokamai bet mūsų mazgų. Tačiau, jei mes einame čia ir mes pažvelgti į mūsų spausdintoje medžiagoje, matome, kad gerai, atrodo, kad visi mūsų intarpais grįžta tiesa, kuri yra gera. Įdėklai yra tiesa, , o po to atitinkami Contains ragina taip pat tiesa. 

Puikus darbas! Atrodo, kad mes sėkmingai parašyta įdėklą. Štai ir viskas, mes turime šią savaitę problemą, specifikaciją. Vienas įdomus iššūkis, galvoti apie tai, kaip jūs iš tikrųjų eiti į ir nemokamai visus šio medžio mazgų. Mes galime tai padaryti daug įvairių būdų, bet aš palikti, kad iki jums eksperimentuoti, ir kaip įdomus iššūkis, pabandykite ir įsitikinkite, kad jūs galite įsitikinti, ,, kad ši Valgrind ataskaita vėl jokių klaidų ir nėra nuotėkio. 

Sėkmės šią savaitę Hafmano kodavimo problema rinkinys, ir mes Pasimatysime kitą savaitę! [CS50.TV]