[Powered by Google Translate] [Oddelek 7: Več Udobna] [Rob Bowden] [Harvard University] [To je CS50] [CS50.TV] V redu. Torej, kot sem že povedal v e-pošti, to se dogaja, da je binarno drevo intenzivna oddelek. Vendar pa ni, da je veliko vprašanj. Torej bomo poskušali izvleči vsako vprašanje in šel v podrobnosti, boleče vseh najboljših načinov ravnanja. Torej takoj na začetku, ko gremo skozi vzorčnih risbe binarnih dreves in podobno. Torej, tukaj, "Ne pozabite, da je binarno drevo vozlišč, podobne tistim povezan seznam, razen namesto enega kazalca obstajata dve: ena za "otroka" v levo in ena za desno "otrok". " Torej, binarno drevo je tako kot povezanega seznama, razen struct bo dva kazalca. Tam je trinary drevesa, ki bosta imela tri kazalce, obstaja N-arja drevesa, ki imajo le generično kazalec da boste potem morali malloc biti dovolj velika, da imajo dovolj kazalci na vseh možnih otrok. Torej, binarno drevo le zgodi, da imajo stalno število 2. Če želite, lahko daš povezani seznam kot unarni drevesa, ampak jaz ne mislim, kdo kliče, da. "Risanje škatle-in puščice diagram binarnega vozlišča drevesa vsebuje priljubljeno številko Nate je, 7, kjer je vsak otrok kazalec NULL. " Torej iPad način. 

To se dogaja, da je precej enostavna. Mi smo le, da bo imel vozlišče, ga bom pripraviti kot kvadrat. In jaz bom sestaviti vrednosti tukaj. Tako bo vrednost iti tja, in potem tukaj bomo imeli levi kazalec na levi in ​​desni kazalec na desni. In to je zelo veliko, tako dogovor, da ga pokličete levo in desno, kazalec imena. Oboje bo nič. To bo zgolj še nič, in da bo le null. Ok. Torej, nazaj sem. "S povezan seznam, smo imeli samo za shranjevanje kazalec na prvi vozel v seznamu, da bi se spominjali celo povezani seznam, ali celoten seznam. Prav tako, z drevesi, imamo le za shranjevanje kazalec na eno samo vozlišče, da se spomnite celotno drevo. To vozlišče je calle je "root z drevesa. Nadgraditi svoj diagram pred letom ali pripravi novega tako da imate škatle-in puščice upodobitev binarno drevo s vrednost 7, potem 3 v levo, 9 nato na desni strani, nato pa 6 na desni strani 3 ". Bomo videli, če se spomnim, da je vse v moji glavi. Torej, to se dogaja, da je naša root tukaj. Imeli bomo nekaj kazalec nekje nekaj, kar ti pravimo koren, in to kaže s tem tipom. Zdaj, da bi novo vozlišče, kaj imamo, 3 na levi? Torej, novo vozlišče s 3, in je sprva kaže nič. Jaz bom dal N. Zdaj želimo, da gredo na levi 7. Zato smo spremenili to kazalec, da se zdaj kažejo s tem tipom. In delamo isto. Želimo 9 Sprehodite se tukaj ki je na začetku samo pravi nič. Bomo spremenili to kazalec, pokažite na 9, in zdaj smo želeli dati 6 desno od 3. Torej, da se bo - narediti 6. In ta tip točko tam. Ok. Tako, da je vse, kar nam želi storiti. 

Zdaj pa gremo čez nekaj terminologije. Smo že govorili o tem, kako Koren drevesa je top-najbolj vozlišče v drevesu. Tisti, ki vsebuje 7. Vozlišča na dnu drevesa se imenujejo listi. Vsako vozlišče, ki le ima sedaj null, katerega otrok je list. Torej je mogoče, če je naš binarno drevo je samo ena vozlišče, da je drevo list, in to je to. "The" Višina "od drevesa je število hmelja moraš narediti da bi dobili od vrha do lista. " Bomo dobili v, v drugi razliko med uravnotežene in neuravnotežene dreves binarne, vendar za zdaj, je skupna višina tega drevesa Rekel bi, da je 3, čeprav, če ste štetje števila hmelja moraš narediti, da bi prišli do 9, potem je res samo višina 2. Zdaj je to neuravnoteženo binarno drevo, vendar bomo govorili o uravnoteženi, ko pride v poštev. Sedaj lahko govorimo o vozlišč v drevesu v smislu glede na druge vozlišč v drevesu. Torej, zdaj imamo starši, otroci, bratje in sestre, prednikov in potomcev. So zelo zdrava pamet, kaj pomenijo. Če se vprašamo - to je starše. Torej, kaj je matično 3? [Dijaki] 7. >> Ja. Matično se le, da bo to, kar kaže na vas. Torej, kaj so otroci 7? [Dijaki] 3 in 9. >> Ja. Obvestilo, da je "otrok" dobesedno pomeni za otroke, Tako 6 ne bi uporabljal, ker je kot vnuka. Potem pa če gremo potomce, kaj so potomci 7? [Dijaki] 3, 6 in 9. >> Ja. Potomci korenskega vozlišča se bo vse, kar je v drevesu, razen morda root vozlišča sama, če ne želite, da menijo, da je potomec. In končno, predniki, tako da je v nasprotni smeri. Torej, kaj so predniki 6? [Dijaki] 3 in 7. >> Ja. 9 ni vključena. To je samo neposredni rodu nazaj do korena se bo vaši predniki. 

"Pravimo, da je binarno drevo" naloži ", če za vsako vozlišče v drevesu, vseh njegovih potomcev na levi imajo manj vrednosti in vsi tisti na desni imajo večje vrednosti. Na primer, je drevo nad naloži, vendar to ni edina možna urejene. " Preden smo prišli do tega, naloži binarno drevo je znana tudi kot dvojiškega drevesa. Tu se zgodi, da se ga kliče urejene binarno drevo, vendar še nikoli nisem slišal, da imenuje naročiti binarno drevo pred in na kvizu smo veliko bolj verjetno, da dajo binarno iskalno drevo. Oni so eno in isto, in to je pomembno, da prepozna razliko med drevesa binarno drevo in binarno iskanje. Binarno drevo je samo drevo, ki opozarja na dve stvari. Vsako vozlišče opozarja na dve stvari. Ni razmišljanje o vrednotah, ki jih je usmerjeno k. Torej, kot sem, saj je to binarno iskalno drevo, vemo, da če bomo šli levo od 7, potem pa vse vrednosti, ki jih lahko morebiti doseže jih bo ostalo od 7 morajo biti manj kot 7. Opazili boste, da so vse vrednosti manj kot 7 so 3 in 6. Tisti, ki so vse na levi 7. Če gremo od pravice do 7, vse mora biti večja od 7, Tako 9 je na desni strani 7, tako da smo dobri. To pa ne velja za binarno drevo, za redno binarnega drevesa imamo samo 3 na vrhu, 7 na levi strani, 9 levo od 7, ni vrstni red vrednosti whatsoever. Zdaj, ne bomo dejansko to, ker je dolgočasno in nepotrebno, ampak "poskušali pripraviti čim več naročene dreves, kot si lahko misliš s številkami 7, 3, 9, 6. Koliko različni dogovori obstajajo? Kakšna je višina vsakega? " 

Naredili bomo nekaj, vendar je glavna ideja je, To nikakor ni enotna zastopanost binarno drevo, ki vsebuje te vrednosti. Vse kar potrebujete je nekaj binarno drevo, ki vsebuje 7, 3, 6 in 9. Druga možnost bi bila veljavna korenina je 3, pojdi na levo in to je 6, pojdite na levo in to je 7, pojdi na levo in je 9. To je popolnoma veljavno binarno iskalno drevo. To ni zelo koristna, saj je tako kot povezani seznam in vseh teh kazalcev so le null. Vendar je veljavna drevo. Ja? [Študent] Ali ni vrednosti, morajo biti večja na desni? Ali pa je to? - >> To sem mislil, da gredo v drugo smer. Tam je tudi - ja, dajmo izbrati to. 9, 7, 6, 3. Dober ulov. Še vedno ima ubogati, kar je binarno drevo iskanje naj storim. Torej je vse na levi strani mora biti manjši od danega vozlišča. Mi lahko samo premaknete, recimo, to 6 in ga tukaj. Ne, ne moremo. Zakaj vztrajati početje to? Naredimo - tukaj je 6, tukaj je 7, 6 točk za 3. To je še vedno veljaven dvojiško iskalno drevo. Kaj je narobe, če sem - da vidimo, če bom lahko prišel do dogovora. Ja, v redu. Torej, kaj je narobe s to drevo? Mislim, da sem že dal namig, da je nekaj narobe z njim. Zakaj vztrajati početje to? Ok. To izgleda primerna. Če pogledamo vsakega vozlišča, kot so 7, nato pa na levi strani 7 je 3. Torej imamo 3, stvar na desni strani 3 je 6. In če pogledaš na 6, stvar na desni strani 6 je 9. Torej, zakaj to ni veljavno binarno iskalno drevo? [Dijaki] 9 je še vedno na levi strani 7. >> Ja. To mora biti res, da so vse vrednosti, ki jih lahko dosežejo morda jih bo na levi strani 7 manj kot 7. Če gremo levo 7, pridemo do 3 in smo še vedno lahko prišli do 6, lahko še vedno pridete do 9, ampak s tem, ko ni več manj kot 7, da ne bi mogli priti do številke, ki je večja od 7. Torej, to ni veljavno binarno iskalno drevo. 

Moj brat je dejansko imela intervju vprašanje da je v bistvu to, samo oznaka do nečesa, da bi preverili ali drevo je dvojiško iskalno drevo zato je prva stvar, ki je storil, je le preverite, Če levo in desno so pravilne, in nato izbirajte tam. Ampak ne moreš narediti, moraš slediti dejstvo, da zdaj, ko sem šla levo od 7, vse v to drevo mora biti manjša od 7. Pravilna algoritem mora slediti V mejah, da se vrednosti lahko sodijo noter Ne bomo šli skozi vse od njih. Tam je lepo enačbe, Čeprav nismo prišel do tistih, ne bomo prišli do tistih, opredeljevanju, koliko jih je dejansko so. Tako je 14 izmed njih. Ideja o tem, kako bi to naredil matematično je všeč, lahko izberete kateri koli niti enega, da bi bil izvor vozlišče, in potem, če sem izbral 7, da je korenina vozlišče, potem so, recimo, nekaj številk, ki lahko gredo moja leva vozlišče, in da so nekatere številke, ki jih je mogoče moja pravica vozlišče, ampak če sem n skupno število, se znesek, ki se lahko obrnejo na levo plus znesek, ki se lahko obrnejo na desni je n - 1. Torej, preostalih številk, morajo imeti možnost, da bodisi iti v levo ali desno. Zdi se, da je težko, da če sem dal 3, potem pa vse, kar mora iti v levo, ampak če sem dal 7, nato pa lahko nekatere stvari gredo v levo in nekatere stvari lahko obrnejo na desni strani. In 3. 1. "Mislil sem vse, kar lahko gre v desno. To je res, boste morali razmišljati o tem, kot, koliko stvari lahko gredo na naslednjo stopnjo drevesa. In pride ven, da bo 14, ali lahko pripravi vse od njih, in potem boš dobil 14. 

Gremo nazaj, "Ž dvojiška drevesa so kul, ker lahko iščemo po njih na zelo podoben način iskanja preko razvrščenih matrike. To storite tako, začnemo pri korenu in naš način dela, navzdol po drevesu do listov, preverjanje vsako vozlišče v vrednosti nad vrednotami, ki jih iščete. Če je trenutno vozlišče je vrednost nižja od vrednosti, ki ga iščemo, greš zraven desnem vozlišča otroka. Sicer pa greš na levi vozlišča svojega otroka. Na neki točki, boste našli bodisi vrednost, ki jo iščete, ali pa boš naletel na null, označuje vrednost ni v drevesu. " Imam, da izvlečete drevo smo imeli prej, da bo trajalo. Ampak želimo pogledati, ali 6, 10 in 1 v drevo. Torej, kaj je to, 7, 9, 3, 6. Ok. Številke, ki jih želite poiskati, smo želeli poiskati 6. Kako to algoritem deluje? No, imamo tudi nekaj korenin kazalec na našem drevesu. In gremo na korenu in rekli, da je ta vrednost enaka vrednosti smo iščejo? Torej iščemo 6, tako da to ni enako. Tako smo naprej, in zdaj smo rekli, v redu, tako da je 6 manj kot 7. Ali to pomeni, da želimo iti v levo, ali pa želimo iti na desno? [Študent] levice. >> Ja. To je bistveno lažja, vse, kar morate storiti je, da pripravi eno možno vozlišče drevesa in potem Ne - namesto da mislijo v glavi, ok, če je to manj, naj grem na levi ali pa na pravico, samo gledaš te slike, to je zelo jasno, da moram iti v levo če je to vozlišče je večja od vrednosti, ki jo iščem. Torej greš na levo, zdaj sem na 3. Želim - 3 je nižja od vrednosti, ki jih iščem, kar je 6. Torej gremo na desno, zdaj pa sem na koncu na 6, ki je vrednost iščem, zato sem se vrnil res. Naslednji vrednost grem iskati je 10. Ok. Torej, 10, zdaj pa se bo - odreže, da - bodo sledili korenine. Sedaj, 10 se bo več kot 7, zato želim videti na desni. Jaz bom prišel tja, 10 se bo večja od 9, Tako bom želijo videti na desni. Prišel sem sem, vendar sem zdaj sem na null. Kaj naj storim, če sem udaril nično? [Študent] Nazaj ne drži? >> Ja. Nisem našel 10. 1 se bo skoraj identičen primer, razen tega, da se je le, da bo obrnila, namesto da bi iskali navzdol na desni strani, bom pogledal dol na levi strani. 

Zdaj mislim, da smo dejansko prišli do kode. Tukaj pa - Odprtje CS50 napravo in krmariti svojo pot tam, ampak tudi preprosto lahko to storite v prostoru. Verjetno je idealen, da to storite v prostor, ker lahko delamo v prostoru. "Najprej bomo morali z novo definicijo tipa za binarno drevo vozlišče, ki vsebuje int vrednosti. Uporaba boiler typedef spodaj ustvarite novo definicijo za tip vozlišča v binarno drevo. Če se vam zatakne. . . "Bla, bla, bla. Redu. Torej, kaj je dal boiler tukaj, typedef struct vozlišče in vozlišče. Ja, v redu. Torej, kaj so polja bomo želeli v naši vozel? [Študent] Int in nato 2 kazalci? >> Int vrednost, 2 kazalci? Kako napisati napotke? [Študent] struct. >> Moram povečati noter Ja, struct vozlišče * v levo, in struct vozlišče * desno. In ne pozabite razpravo od zadnjega obiska, da to nima smisla, to nima nobenega smisla, To nima nobenega smisla. Moraš vse tja, da bi opredelili ta rekurzivni struct. Dobro, to je tisto, kar naša drevo se bo izgledal. Če bomo naredili trinary drevo, potem bi vozlišče videti B1, B2, struct vozlišče * B3, b, kjer je podružnica - pravzaprav, sem še slišal, da levo, sredina, desno, ampak karkoli. Mi samo skrbi binarno, tako da desno, levo. "Zdaj razglaša za globalno spremenljivko * vozlišče za koren drevesa." Torej ne bova za to. Da bi se stvari nekoliko težje in bolj splošen, ne bomo imeli globalno spremenljivko vozlišča. Namesto tega v glavnem bomo prijavijo vse svoje vozlišče stvari, in to pomeni, da je spodaj, ko smo začeli izvajati Vsebuje naša naloga in naš vložek funkcija, namesto naših vsebuje delujejo samo z uporabo te svetovne vozlišča spremenljivko, bomo morali to sprejeti kot argument drevo, da želimo, da obdelati. Ob globalno spremenljivko naj bi stvari lažje. Gremo, da bi stvari težje. Sedaj vzemite minuto ali tako, da pač te stvari, , kjer v notranjosti od glavnih želite ustvariti to drevo, in to je vse, kar želite storiti. Poskusite in zgraditi to drevo v vašem glavne funkcije. 

Ok. Torej ti sploh ni treba, da so izdelani na drevesu celotno pot še ni. Toda kdo ima nekaj kar bi lahko potegnili gor pokazati, kako se bodo začeli gradnjo takšno drevo? [Študent] Nekdo razbija, poskuša priti ven. [Bowden] Kdor zadovoljni z njihovo gradnjo drevesa? [Študent] Seveda. To ni bilo storjeno. >> Je že v redu. Lahko je pravkar končal - oh, ga lahko reši? Hura. Torej, tukaj imamo - oh, sem rahlo odrezana. Sem Povečano? Povečajte, da se pomaknete ven. >> Imam vprašanje. >> Ja? [Študent] Ko določite struct, so stvari, kot initialized na kaj? [Bowden] No >> redu. Torej bi morali inicializirati - [Bowden] No Ko določite, ali ko razglasi struct, ni inicializiran privzeto, to je tako kot, če ugotovi, int. To je popolnoma ista stvar. To je tako kot vsak izmed njenih posameznih področjih lahko za smeti vrednosti v tem. >> In ali je mogoče opredeliti - ali razglasi struct na način, ki ga opravlja jim inicializirati? [Bowden] Da. Torej, tipka za inicializacijo skladnja bo izgledal - Obstaja dva načina, lahko to storijo. Mislim, da bi ga morali pripraviti in se prepričajte Jek tudi počne. Vrstni red argumentov, ki prihaja v struct, daš kot da trditev znotraj te zavite oklepaje. Torej, če želite, da se zažene do 9, levo je nična, nato pa prav nič, da bi bilo 9, null, null. Druga možnost je, in urednik ni všeč to sintakso, in misli, da želim nov blok, druga možnost pa je nekaj podobnega - Tukaj bom dal v novo vrstico. Lahko posebej poudarjati, da sem pozabila točno sintakso. Torej, lahko jih izrecno obravnavajo po imenu in rekel, . C ali. Vrednost = 9,. Levo = NULL. Ugibam, da ti morajo biti vejice. . Desno = NULL, tako da na ta način ne boste dejansko vedeti vrstni red struct, in ko berete to, je veliko bolj jasno o tem, kaj je vrednost, ki se inicializira k. 

To se zgodi, da je ena od stvari, ki - Tako, za večino del, C + + je nadgradnja C. Lahko vzamete C kodo, da se usmerijo v C + +, in bi moral prevesti. To je ena izmed stvari, da je C + + ne podpira, tako da ljudje ne bi naredil. Ne vem, če je to edini razlog, da ljudje niso za to, vendar v primeru, ko sem potreboval, da jo uporabljajo, potrebne za delo s C + + in tako nisem mogel uporabljati. Še en primer nečesa, kar ne deluje s C + +, je kako malloc vrne "void *," tehnično, vendar lahko samo rečem char * x = malloc karkoli, in bo samodejno odda v char *. To samodejno litega ne zgodi v C + +. To ne bi bilo zbrati, in vi bi morali izrecno povedati char * malloc, karkoli, da ga odda v char *. Ni veliko stvari, C in C + + se ne strinjajo o, ampak tisti dve. Torej bomo šli s to sintakso. A tudi če nismo šli s to sintakso, tisto, kar je - bi bilo narobe s tem? [Študent] Ne rabim ga dereference? >> Ja. Ne pozabite, da je puščica je implicitno dereference, in tako, ko smo ravno opravka s struct, želimo uporabiti. da se na terenu notranjosti struct. In edini čas, da uporabite puščico, ko želimo narediti - No, puščica je enaka - To je tisto, kar bi pomenilo, da če sem uporabil puščico. Vse arrow sredstva, se dereference to, zdaj pa sem na struct, in lahko dobim polje. Ali se polje neposredno ali dereference in dobili polje - Mislim, da to mora biti vrednost. Ampak tukaj sem, ki se ukvarjajo s samo struct, ne kazalec na struct, in tako ne morem uporabljati puščico. Vendar pa lahko te stvari delamo na vseh vozliščih. Oh, moj bog. To je 6, 7 in 3. Potem bomo lahko ustanovijo podružnice v našem drevesu, lahko imamo 7 - lahko bi, bi moral opozoriti na levo 3. Torej, kako bomo to naredili? [Študenti, nerazumljiv] >> Ja. Naslov vozlišče3, in če nisi imel naslov, potem to ne bi prevesti. Ampak ne pozabite, da so kazalci na naslednjih vozlišč. Pravica mora kazati na 9, in bi točko 3 o pravici do 6. Mislim, da je vse pripravljeno. Kakršne koli pripombe ali vprašanja? [Študent, nerazumljiv] korenine se bo 7. Lahko samo rečem vozlišče * ptr = ali korenina = & node7. 

Za naše namene, bomo morali ukvarjati z vložkom, Tako bomo želeli napisati funkcijo, ki jo vstavite v to binarno drevo in vložek je neizbežno, da pokličete malloc ustvariti novo vozlišče za to drevo. Stvari se bodo grdo z dejstvom, da so nekatere vozlišča Trenutno je na kupu in druga vozlišča se bo končal na kup, ko jih vstavite. To je povsem pravilna, vendar je edini razlog, smo sposobni to narediti na kupu je, ker je tak primer izmišljene, da vemo, Drevo naj bi bila zgrajena kot 7, 3, 6, 9. Če ne bi imeli tega, potem ne bi bilo treba knjižnične funkcije malloc na prvem mestu. Kot bomo videli malo kasneje, bi morali malloc'ing. Zdaj je povsem razumno, da dajo na kup, vendar naj se to spremeni v malloc izvajanje. Torej, vsak od teh je zdaj bo nekaj podobnega vozlišče * node9 = malloc (sizeof (vozlišče)). In zdaj bomo morali storiti pregled. if (node9 == NULL) - Nisem hotel, da - vrne 1, potem lahko naredimo node9-> ker zdaj je kazalec, Vrednost = 6, node9-> levo = NULL, node9-> desno = NULL, in bomo morali to storiti za vsako od teh vozlišč. Torej, namesto, kaj je dal notri v ločenem funkcije. Naj bo vozlišče * build_node, in to je nekoliko podoben API nudimo za Huffmanovo kodiranje. Mi vam initializer funkcije za drevo in deconstructor 'funkcije' za tistimi drevesi in enaka za gozdove. 

Torej, tukaj bomo imeli initializer funkcijo da samo zgraditi vozlišče za nas. In to se dogaja, da si precej natančno tako. In jaz še bo leni in ne spremenite ime spremenljivke, čeprav node9 nima nobenega smisla več. Oh, mislim, da je vrednost node9 ne bi smelo biti 6. Zdaj se lahko vrnemo node9. In tukaj bi se morali vrniti nična. Vsakdo se dogovorijo o tem graditi-vozlišče funkcijo? Torej, zdaj lahko samo pokličite, da graditi vsako vozlišče z določeno vrednostjo in ničelnih kazalci. Zdaj lahko rečemo, da lahko naredimo vozel * node9 = build_node (9). In kaj je naredil. . . 6, 3, 7, 6, 3, 7. In zdaj želimo vzpostaviti enake napotke, razen zdaj je vse že v smislu kazalcev Tako ni več treba naslov. Ok. Torej, kaj je zadnja stvar, ki jo želite narediti? Tam je do napake kontrole, da ne delam. Kaj zgraditi vozlišče vrnitev? [Študent, nerazumljiv] >> Ja. Če malloc ni uspel, se bo vrnil null. Torej bom leno dal dol, namesto da delaš pogoj za vsakega posebej. Če je (node9 == NULL, ali - še bolj enostavno, to ustreza le, če ne node9. Torej, če ne node9, ali ne node6, ali ne vozlišče3, ali ne node7, vrne 1. Mogoče bi morali natisniti malloc ni, ali kaj podobnega. [Študent] Ali lažno enako null, kot tudi? [Bowden] Vsaka vrednost nič, je napačen. Tako je sedaj null vrednost nič. Zero je vrednost nič. Neresnično je vrednost nič. Vsak - precej le 2 ničti vrednosti, so nične in nič, napačna je samo hash opredeljen kot nič. To velja tudi, če ne bomo izjavi globalno spremenljivko. Če smo imeli Koren vozlišča * tu gor, Nato - je lepo stvar o globalnih spremenljivk je, da imajo vedno začetno vrednost. To ni res funkcij, kako notranjost tukaj če imamo, kot, vozlišče ali vozlišče x *. Nimamo pojma, kaj x.value, x.whatever, ali bi jih lahko natisnete in jih lahko poljubno. To ni res globalnih spremenljivk. Torej, vozlišče koren ali vozlišče x. Privzeto je, da vse, kar je globalna, če ni izrecno initialized na neko vrednost, ima ničelno vrednost kot svojo vrednost. Torej, tukaj, vozlišče * koren, ne izrecno inicializirati na nič, tako da bo njegova privzeta vrednost null, ki je nič Vrednost kazalca. Privzeta vrednost x bo pomenilo, da x.value nič, x.left nič, in x.right je nična. Zato, ker je struct bo vsa polja v struct bo ničti vrednosti. Ni nam treba uporabiti, da sem, čeprav. [] V Študentski konstrukti so drugačni od drugih dejavnikov, in druge spremenljivke smetarska vrednote, to so ničle? [Bowden] Druge vrednosti preveč. Torej, x, x bo nič. Če je v svetovnem obsegu, da ima začetno vrednost. >> Redu. [Bowden] Ali je začetna vrednost, ki jo je dal to ali nič. Mislim, da skrbi za vse to. 

Ok. Torej, naslednjič, del vprašanja sprašuje, "Zdaj želimo, da napišete funkcijo imenovano vsebuje s prototipom bool vsebuje int vrednost. " Mi ne boš naredil int vsebuje int vrednost. Naš prototip bo izgledal bool vsebuje (int vrednost. In potem bomo tudi dogaja, da prenese to drevo da bi moralo biti preverjanje, da vidim, če je to vrednost. Torej vozlišče * drevo). Ok. In potem lahko rečemo tudi nekaj podobnega, Morda bomo želeli printf ali nekaj. Vsebuje 6, naše korenine. To je treba vrniti eno, ali resnično, ker vsebuje naj 5 koren vrne false. Torej, vzemite si sekundo časa za izvedbo tega. To lahko storite bodisi iterativno ali rekurzivno. Za lepo stvar o tem, kako smo jo določili stvari je, da to bi lahko bilo naše rekurzivni rešitvi veliko lažje kot globalno spremenljivko in kako je. Ker če imamo samo vsebuje int vrednost, potem nikakor ne rekurzivnem navzdol subtrees. Morali bi imeti ločeno funkcijo pomočnika, ki recurses določitvi subtrees za nas. Ampak, ker smo spremenili, da bi drevo kot argument, , ki naj bi bila vedno na prvem mestu, Zdaj bomo lahko recurse lažje. Zato ponavlja ali rekurzivna, bova šla skozi tako, ampak bomo videli, da je rekurzivni konča pa precej enostavno. Ok. Ali kdo ima nekaj, kar lahko skupaj z? 

[Študent] Imam iterativno rešitev. >> Redu, ponavlja. Ok, to izgleda dobro. Torej, da nas hoče hoditi po njej? [Študent] Seveda. Zato sem določene temp spremenljivko dobili prvo vozlišče drevesa. In potem sem zanko skozi medtem ko temperatura ni enaka nič, Medtem, ko je bil še v drevo, se mi zdi. In če je vrednost enaka vrednosti, ki kaže na temp, nato vrne vrednost. Drugače pa preveri, če je na desni strani ali na levi strani. Če se vam kdaj situacijo, v kateri ni več dreves, Nato se vrne - ko pride iz zanke in vrne false. [Bowden] Ok. Tako, da izgleda dobro. Vsakdo ima kakršne koli pripombe na karkoli? Nimam pravilnosti komentarjev na vse. Edina stvar, ki jo lahko naredimo je ta tip. Oh, to se dogaja, da gredo malo podolgovate. Jaz bom popraviti to izmislil. Ok. 

Vsi se morajo zavedati, kako ternarna deluje. Tam so bili zagotovo kvizov v preteklosti da vam s funkcijo trikomponentne subjekta, in pravijo, prevedi to, naredi kaj, da ne uporablja trikomponentnih. Torej, to je zelo pogost primer, ko bi mislil, da uporabite trikomponentnih, kjer je, če nekateri pogoji, določeni s spremenljivko nekaj, drugega iz te iste spremenljivke v nekaj drugega. To je nekaj, kar se zelo pogosto spremenijo v te stvari kjer je določeno, da se za to spremenljivko - ali pa je to res? Potem, pa to. [Študent] Prva je če je to res, kajne? [Bowden] Ja. Tako kot sem vedno prebral, je, temperatura je enaka vrednost, večjo od vrednosti temp, potem je to, pa to. To sprašujem. Je večja? Potem pa je prva stvar. Sicer ne drugo stvar. Sem skoraj vedno - kolona, ​​sem - v moji glavi, sem prebral, kot drugje. 

Ima kdo rekurzivna rešitev? Ok. Ta bomo - to bi že bilo super, vendar se bomo, da bi bilo še bolje. To je precej točno isto zamisel. To je samo, no, hočeš, da pojasni? [Študent] Seveda. Zato smo se prepričajte, da je drevo ni nič prvič, ker če je drevo nična, potem se dogaja, da vrne false, ker nismo našli. In če je še vedno drevo, smo šli v - najprej preveri, če je vrednost trenutnega vozla. Return true, če je, in če ne bomo recurse na levo ali desno. Ali to zveni primerno? >> Aha. (Sporazum) Torej, opazil, da je to skoraj - strukturno zelo podobni ponavljajočim rešitev. To je samo, da namesto rekurzivnem smo imeli while zanko. In osnovna tukaj, kjer drevo ni enak za nično je pogoj, pod katerim sva se razšla iz while zanko. Oni so zelo podobne. Vendar pa bomo lahko to en korak naprej. Zdaj delamo isto stvar tukaj. Obvestilo smo vračajo enako v obe smeri, razen za en argument je drugačna. Tako se bomo, da se to v ternarni. Zadel sem nekaj opcij, in to je simbol. Ok. Torej se bomo vrnili vsebuje tem. To je pridobivanje biti več vrstic, no, povečani je. Ponavadi, kot stilistični stvar, jaz ne mislim, da veliko ljudi dal prostor za puščico, ampak mislim, če ste dosledni, je to v redu. Če je vrednost nižja od vrednosti, drevesa, želimo recurse na levi strani drevesa, pa želimo recurse na desni drevo. Tako, da je prvi korak, da bi ta videz manjše. Korak 2, da bi ta videz manjši - lahko ločite na več vrstic. Ok. Korak 2 od česar je videti manjša je tukaj, Tako izračunana vrednost je enaka vrednosti drevo, ali vsebuje karkoli. 

To je pomembna stvar. Nisem prepričan, če je to izrecno povedal v razredu, vendar pa je pozval kratkega stika vrednotenje. Ideja je vrednost == drevo vrednost. Če je to res, potem je to res, in želimo "ali", da se z vse, kar je tukaj. Torej, ne da bi sploh razmišljal, kar je tukaj, kakšen je celoten izraz bo vrnil? [Študent] True? >> Ja, saj res ničesar, or'd - ali res or'd z vsem, kar je nujno res. Torej takoj, ko bomo videli vrnjeno vrednost = vrednost drevo, smo le, da bo vrnil res. Niti bo recurse nadalje vsebuje po vrsti. Mi lahko to en korak naprej. Nazaj drevo ni enak za nično in vse to. To je bilo eno vrstico funkcijo. To je tudi primer kratkega stika oceno. Zdaj pa je ista ideja - namesto da bi - tako da, če drevo ni enak nič - ali, dobro, če drevo ne enak nič, kar je slabo tako, Če drevo je enaka nič, potem je prvi pogoj, se bo napačen. Torej lažno anded s čimerkoli se bo kaj? [Študent] False. >> Ja. To je druga polovica kratkega stika ocene če, če drevo ne enaka nič, potem ne bo niti go - ali če je drevo ima enak null, potem ne bo naredil vrednost == drevo vrednost. Mi smo le, da bo nemudoma vrne false. Kar je pomembno, saj če ni kratkega stika oceni, potem, če drevo ima enak nič, ta drugi pogoj se dogaja, da krivdo SEG, ker je drevo-> vrednost Dereferenciranje null. Torej, to je to. Lahko bi to - premik enkrat več. To je zelo običajna stvar tako, da se ta ne eno vrstico s tem, ampak to je običajna stvar v razmerah, morda ni v redu, če pa (drevo! = NULL, in drevo-> vrednost == vrednost), karkoli. To je zelo pogosto stanje, kjer je namesto ob , da bi prekinil to v dveh investicijskih skladov, kjer je všeč, je drevo nična? Ok, to ni nič, tako da zdaj je drevo vrednost je enaka vrednosti? Naredite to. Namesto tega je pogoj, to ne bo nikoli seg napako ker bo prekinil, če se to zgodi, je ničen. Mislim, da če je vaš drevo je v celoti neveljavna kazalec, lahko še vedno seg napako vendar ne more seg napako, če drevo je nična. Če ne bi bilo nič, bi prekinil, preden boste kdaj dereferenced kazalec na prvem mestu. [Študent] Ali je to ti leni ocena? 

[Bowden] Lazy ocena je ločena stvar. Lazy vrednotenje je bolj kot vas za vrednost, prosite za izračun vrednosti, vrsta, vendar ga ne potrebujejo takoj. Torej, dokler ne boste dejansko potrebovali, ni ocenjena. To ni ravno isto, ampak v Huffman pset, se pravi, da smo "leno" napisati. Razlog, da to, da je zato, ker smo dejansko buffering WRITE - ne želimo, da napišete posamezne bite hkrati, ali posameznih zlogov v času, smo namesto tega želeli, da bi dobili kos bajtov. Potem ko smo kos bajte, potem bomo to napiši. Čeprav ga prosil, da napišete - in fwrite in fread storijo enako stvari. Ti varovalni svoje bere in piše. Čeprav ga prosim, da takoj napisati, da verjetno ne bo. In ne moremo biti prepričani, da gredo stvari je treba pisno dokler ne pokličeš hfclose ali karkoli že je, ki pa pravi, ok, bom zaprl svojo datoteko, to pomeni, da bi bilo bolje napisati vse, kar sem še ni bila napisana. To je ni treba pisati vse ven dokler se ne zaprete datoteko, in potem ga je treba. Torej, to je samo tisto, kar leni - počaka, dokler ta ne bo zgodilo. Ta - sprejme 51 in boš šel v to bolj podrobno, ker OCaml in vse, kar 51, je vse rekurzije. Ni iterativno rešitev, v bistvu. Vse je rekurzija, in leni ocenjevanje se bo pomembno za veliko primerih kjer, če nisi leno oceniti, bi to pomenilo - Primer je potoki, ki so neskončno dolgo. V teoriji, lahko si misliš o naravnih števil kot tok 1-2-3-4-5-6-7, Torej leno ocenili stvari so v redu. Če rečem, želim 10. številko, potem lahko ocenim do 10. številke. Če želim stoto številko, potem lahko ocenim do stote številke. Brez ocene leni, potem se dogaja, da poskušajo oceniti vse številke takoj. Saj ocenjevanje neskončno veliko številk, in to preprosto ni mogoče. Torej obstaja veliko okoliščin, kjer leni ocenjevanje je samo pomembno, da so stvari za delo. 

Zdaj želimo, da napišete vložek, kjer vložek se bo Podobno spremembo v svoji definiciji. Torej, zdaj je bool vstavi (int vrednost). Mi bomo spremenili, da bool vstavi (int vrednost, vozlišče * drevo). Mi smo dejansko dogaja, da spremenite, da spet malo, bomo videli, zakaj. In gremo build_node, samo za vraga njo, zgoraj vstavite tako da nam ni treba napisati funkcijo prototip. Kateri je namig, da si bo z uporabo build_node v vložek. Ok. Vzemite si trenutek za to. Mislim, da sem rešil z revizijo, če želite potegniti iz tega, ali vsaj, sem zdaj. Želel sem rahlo odmor za razmislek o logiki vložka, če ne moreš razmišljati o tem. V bistvu, boste le kdaj se vstavi na listi. Všeč mi je, če sem vstavil 1, potem bom zagotovo bo treba vstavljanje 1 - Jaz bom spremenite v črno - bom lahko vstavite 1 tukaj. Ali pa, če sem vstavil 4, želim, da se vstavljanje 4 tukaj. Torej, ni važno, kaj si naredil, da boš lahko vstavite na list. Vse kar morate storiti je, da izbirate z drevesa, dokler ne pridete do vozlišča da mora biti vozlišče, je eden od staršev, novega vozlišča staršev, in nato spremenite svoj levi ali desni kazalec, odvisno od tega, ali da je večja ali manjša od tekoče vozlišče. Spremenite to kazalec, da kaže na novo vozlišče. Torej izbirate z drevesa, bi krilo točko na novo vozlišče. Prav tako mislim, da o tem, zakaj prepoveduje s položajem pred kjer sem izdelana binarno drevo, kjer je bila pravilna če si samo pogledal na enem vozlišču, ampak 9 je na levi strani 7, če poudarili navzdol vse do konca. Torej, to je nemogoče v tem primeru, saj je - Razmišljam o vstavljanju 9 ali kaj podobnega, ob prvem vozlišču, Bom videl 7 in sem samo šla na desno. Torej, ni važno, kaj naj naredim, če sem ga vstavite bo lista, in listom z uporabo ustreznih algoritem, to se dogaja, da je nemogoče za mene, da vstavite 9 levo od 7 saj takoj ko sem zadel 7 bom šel desno. Ali ima kdo kaj začeti s? [Študent] jaz. >> Seveda. [Študent, nerazumljiv] [Other študent, nerazumljiv] [Bowden] je cenjen je. Ok. Želite, da pojasni? 

[Študent] Ker vemo, da smo vstavljanje nova vozlišča na koncu drevesa, Jaz zanko skozi drevesa iterativno dokler nisem prišel do vozlišča, ki opozoril na null. In potem sem se odločil, da ga proda bodisi na desni strani ali na levi strani uporabo te pravice spremenljivke, saj mi je povedal, kje je bilo. In potem, v bistvu sem na ta zadnji - da temperatura vozlišče kaže na novo vozlišče, ki je bilo ustvarjanje, bodisi na levo ali na desno stran, odvisno od tega, kaj je vrednost desno je bil. Končno sem nastavil novo vozlišče vrednost vrednosti njene testiranja. [Bowden] Ok, tako da sem videl eno vprašanje tukaj. To je tako kot 95% poti tja. Eno vprašanje, ki sem videl, no, pa še kdo drug videl težavo? Kaj so okoliščine, v katerih se iztrgajo iz zanke? [Študent] Če temperatura je nična? >> Ja. Torej, kako si iztrgajo iz zanke, če temperatura je nična. Ampak, kaj naj storim tukaj? Jaz dereference temp, ki je neizogibno null. Torej druga stvar, ki jo morate storiti je, ne le slediti, dokler temperatura je nična, želite slediti staršev v vsakem trenutku. Želimo si tudi, staršev vozlišče *, mislim, da bomo tako lažje, da je nična na prvi. To se dogaja, da imajo čudno obnašanje pri korenu drevesa, ampak bomo prišli do tega. Če je vrednost večja od česarkoli že, potem temp = temp prav. Toda preden bomo to storili, starši = temp. Ali so starši vedno bo enako temp? Je tako? Če temperatura ni nič, potem pa grem dol, da se premaknete, ni važno kaj, do vozlišča, za katere temperatura je nadrejena. Torej staršev bo v temp, potem pa sem premakniti temp navzdol. Zdaj temp nič, ampak staršev opozarja na matično stvar, ki je nična. Torej tu spodaj, ne želim, da nastavite desno enaka 1. Zato sem se preselil na desno stran, tako da, če prav = 1, in mislim, da si tudi ti želiš narediti - če premaknete v levo, ki jo želite nastaviti pravica enak 0. Ali pa, če si kdaj premakniti na desno. Torej, desno = 0. Če desno = 1, Zdaj želimo, da bi se osnovni pravo newnode kazalca, pa želimo, da bi matični levi newnode kazalca. Vprašanja o tem? Ok. Torej, to je način, - no, pravzaprav, namesto da delaš to, 1/2 mi pričakujemo, da uporabite build_node. In potem, če newnode enaka nič, vrne false. To je to. No, to je tisto, kar smo pričakovali, da narediš. 

To je tisto, kar je osebje rešitve storiti. Ne strinjam se s tem, kot "pravi" način bo o tem vendar je to popolnoma v redu in da bo delovalo. Ena stvar, ki je malo čudno, zdaj je če drevo prične za nično, se peljemo v ničelno drevo. Mislim, da je odvisno od tega, kako opredeliti obnašanja za prenos v ničelno drevo. Mislil sem, da če se boste peljali v ničelno drevo, Nato vstavite vrednosti v ničelno drevo Morala bi se vrniti drevo, kjer je edina vrednost je eno vozlišče. Ali se strinjate s tem? Lahko bi, če bi želel, če se boste peljali v ničelno drevo in želite vstaviti vrednost vanjo, vrne false. To je do vas, da določite, da. Če želite to narediti prvo stvar, kar sem rekel, in nato - No, boste imeli težave pri tem, da zaradi da bi bilo lažje, če bi imeli svetovni kazalec na stvari, vendar pa ne, tako da če je drevo nič, nič ne moremo storiti glede tega. Mi lahko samo vrne false. Torej bom zamenjati vložek. Mi lahko samo tehnično spremembo te prav tukaj, kako je ponavljanjem nad stvarmi, vendar bom zamenjati vložek, da se vozlišče ** drevo. Dvojni kazalci. Kaj to pomeni? Namesto da se ukvarjajo s kazalci v vozlišč, stvar bom lahko manipulira je to kazalec. Grem, da se manipulira ta kazalec. Grem, da se manipulira kazalce neposredno. To je smiselno, saj razmišljam o določitvi - No, sedaj to kaže na null. Kaj želim storiti, je to manipulira kazalec, da kaže ni nič. Želim, da pokažete svojo novo vozlišče. Če se le slediti svojemu kazalcev kazalcev, potem mi ni treba slediti matične kazalca. Jaz lahko samo slediti, da vidim, če je kazalec kaže na null, in če kazalec kaže na null, spremenite, da kaže na vozlišče želim. In to lahko spremeni, saj imam kazalec na kazalec. Poglejmo to prav zdaj. Lahko dejansko narediti rekurzivno precej enostavno. Ali želimo to storiti? Da, imamo. 

Poglejmo rekurzivno. Prvič, kaj je naša osnovna bo? Skoraj vedno naša osnovna, ampak dejansko je to nekako zapleteno. Prvi stvari prvi, če (drevo == NULL) Mislim, da smo le, da bo vrne false. To je drugačen od vašega drevesa čemer null. To je kazalec na korenski kazalec čemer null kar pomeni, da je vaš korenski kazalec ne obstaja. Torej tukaj, če naredim vozlišče * - kaj je pravkar ponovno to. Node * koren = NULL, in potem bom poklical vložek s tem kaj takega, vstavite v 4 in korenine. Torej & koren, če je korenina vozlišče * Nato in korenine se bo vozlišče. ** To je veljavna. V tem primeru, drevo, gor, Drevo ni nič - ali vložek. Tukaj. Drevo ni nič, * drevo nič, kar je v redu ker če * drevo je nična, potem ga lahko manipulirati za zdaj kažejo na to, kar hočem izpostaviti. Ampak, če drevo je nična, kar pomeni, da sem prišel sem in rekel nič. To nima nobenega smisla. Ne morem storiti ničesar s tem. Če drevo nič, vrne false. Tako sem v bistvu že povedal, kaj naše resnično osnovna zadeva. In kaj je to, da bo? [Študent, nerazumljiv] [Bowden] Da. Torej, če (* drevo == NULL). To se nanaša na primer tukaj če, če je moja rdeča kazalec kazalec sem osredotočen na, Tako kot sem osredotočena na ta kazalec, zdaj sem osredotočen na ta kazalec. Sedaj sem osredotočena na ta kazalec. Torej, če je moja rdeča kazalec, ki je moj vozlišče ** je kdaj - če *, moja rdeča kazalec je vedno nič, to pomeni, da sem v primeru, ko sem se osredotoča na kazalec, ki kaže - To je kazalec, ki pripada lista. Rad bi spremenil to kazalec, da kaže na mojo novo vozlišče. Pridi nazaj sem. Moj newnode bo samo vozlišče * n = build_node (vrednost) nato n, če je n = null, vrne false. Sicer želimo spremeniti tisto, kar je trenutno kazalec kaže na do sedaj kaže na našo novo zgrajenega vozlišča. Mi lahko dejansko narediti, da tukaj. Namesto da bi rekel n, pravimo drevo * = če drevesa *. Vsi razumemo, da je? Da z obravnavo kazalci na kazalce, lahko spremenite ničelne napotke opozoriti na stvari, ki jih želimo izpostaviti. To je naša osnovna. 

Zdaj naša ponovitev, ali naše rekurzija, se bo zelo podoben vsem drugim recursions smo počeli. Bomo želite vstaviti vrednosti, in zdaj bom spet uporabite trikomponentnih, ampak kaj je naš pogoj, da bo? Kaj je iščeva odločiti, ali želimo iti v levo ali desno? Storimo to v posameznih korakih. Če je (vrednost <) kaj? [Študent] The Tree je vrednost? [Bowden] Torej, ne pozabite, da sem trenutno - [Študenti, nerazumljivi] [Bowden] Ja, tukaj, recimo, da je to zelena puščica je primer tega, kar drevo je trenutno, je kazalec na ta kazalec. Torej to pomeni, da sem kazalec na kazalec na 3. The dereference dvakrat zvenel dobro. Kaj mi je - kako naj to naredim? [Študent] dereference enkrat, in naredite puščica na tak način? [Bowden] Torej (* drevo) je dereference enkrat -> vrednost se dogaja, da mi vrednost vozlišča, da sem posredno kaže. Tako lahko tudi jaz napisati ** tree.value če vam je ljubše, da. Ali deluje. Če je tako, potem vas vabim, da vstavite z vrednostjo. In kaj je moja posodobitev vozlišče ** bo? Rad bi šel na levo, tako ** tree.left se bo moja leva. In hočem kazalec na te stvari tako da če levi konča pa null kazalec, Lahko ga spremenite, da kaže na mojo novo vozlišče. 

In druga zadeva je zelo podobna. Naj dejansko narediti, da mi ternarni zdaj. Vstavljanje vrednosti, če vrednost <(** drevo). Vrednost. Potem želimo posodobiti naše ** na levo, pa želimo posodobiti naše ** desno. [Študent] Ali da se kazalec na kazalec? [Bowden] Ne pozabite, da - ** tree.right je vozlišče zvezda. [Študent, nerazumljiv] >> Ja. ** Tree.right je všeč ta kazalec ali kaj podobnega. Torej tako, da kazalec v tem, da daje vse, kar hočem od kazalca do tega tipa. [Študent] Lahko gremo znova Zato smo z uporabo dveh kazalcev? [Bowden] Ja. Torej - ne, lahko, in da je rešitev pred je način za to početje ne delam 2 kazalca. Morate biti sposobni razumeti na dva kazalca, in to je čistejša rešitev. Prav tako opazili, da se, kaj se zgodi, če drevo - Kaj se zgodi, če je bil koren null? Kaj se zgodi, če naredim to zadevo tukaj? Torej vozlišče * koren = NULL, vstavite v 4 in korenine. Kaj je koren bo po tem? [Študent, nerazumljiv] >> Ja. Root vrednost se bo 4. Root levi se bo nič, koren pravica bo nič. V primeru, da ni opravil korenine po naslovu, ne moremo spremeniti root. V primeru, ko je drevo - če je korenina je bila nič, smo imeli, da vrne false. Ničesar nismo mogli storiti. Ne moremo vstaviti vozlišče v prazno drevo. Ampak zdaj smo lahko, smo le, da prazno drevo v eno vozlišče drevesa. Ki je običajno pričakovano smer, da naj bi vse delovalo. 

Poleg tega je to bistveno krajši kot Prav tako sledenja staršev, zato si izbirate navzdol vse do konca. Zdaj imam starša, jaz pa imam samo kazalec matično pravica do česarkoli že. Namesto tega, če bomo to naredili iterativno, bi bilo isto idejo z while zanko. Toda namesto da se ukvarjajo s svojo matično kazalcem namesto da bi moj trenutni kazalec je stvar da sem neposredno spreminja točko svojega novega vozlišča. Nimam obravnavati, ali je to kaže na levo. Nimam obravnavati, ali je to kaže v desno. To je samo ne glede na to kazalec, da bom jo nastavite na točko svojega novega vozlišča. Vsi razumemo, kako deluje? Če ne, zakaj ne želimo storiti na ta način, ampak vsaj to, da ta deluje kot rešitev? [Študent] Kam bomo vrnili res? [Bowden] To je verjetno tukaj. Če smo pravilno vstavite, return true. Else, tukaj bomo želeli vrniti ne glede vstavite donose. 

In kaj je posebnega na tem rekurzivna funkcija? To je rekurzivna rep, tako dolgo, dokler bomo pripraviti z nekaj optimizacije, bo prepoznajo, da ne boste nikoli dobili Stack overflow od tega, tudi če je naš Drevo ima višino 10.000 oziroma 10 milijonov evrov. [Študent, nerazumljiv] [Bowden] Mislim, da to počne na Dash - ali kaj optimizacija ravni je potrebna za rep rekurzija, da se prizna. Mislim, da priznava - GCC in Jek Prav tako imajo različne pomene za njihove optimizacije ravni. Hočem reči, da je DashO 2, za prepričani, da bo to priznanje rep rekurzijo. Ampak - da bi lahko gradnjo kot na primer Fibonocci ali kaj podobnega. To ni enostavno preveriti s tem, ker je težko oblikovati binarno drevo, ki je tako velik. Ampak ja, mislim, da je DashO 2, ki če zbere z DashO 2, bo videti, za rekurzije repa in optimizirati, da ven. Pojdimo nazaj - vstaviti dobesedno zadnja stvar, ki jo potrebuje. Pojdimo nazaj k vložkom tukaj če bomo to isto idejo. To bo še vedno pomanjkljivost, saj ne more v celoti obravnavati ko je korenina sam nič, ali pa v preteklosti vnos je nična, toda namesto da se ukvarjajo z matično kazalcem dajmo uporabiti isto logiko vodenja napotke za kazalcev. Če tu vodijo naše vozlišče ** tren, in mi ni treba slediti desno več, vendar vozlišče ** tren = & drevo. In zdaj naša, medtem ko zanka se bo pa * tren ni enaka null. Ni treba slediti staršem več. Ali ni treba slediti levo in desno. In jaz bom to imenujemo temperatura, saj smo že uporabljate temp. Ok. Torej, če (vrednost> * temp), Nato & (* temp) -> desni še temp = & (* temp) -> levo. In zdaj, v tem trenutku, po tem while zanko, Jaz samo to morda zato, ker je lažje razmišljati o iterativno kot rekurzivno, ampak po tem, medtem ko zanke, * Temp je kazalec želimo spremeniti. 

Preden smo imeli od staršev, in mi je želel spremeniti niti matično levo ali desno starša, ampak, če želimo spremeniti matično pravico, potem * temp je nadrejena prav, in ga lahko spremenite neposredno. Torej tu spodaj, lahko naredimo * temp = newnode, in to je to. Torej, z odpovednim rokom, vsi smo v tem je vzeti vrstic kode. Da bi spremljali od staršev, v vsem, kar je dodaten napor. Tukaj, če bomo spremljali kazalec na kazalec, in tudi če bi želeli, da se znebite vseh teh zavitih oklepajih zdaj, bi bilo videti krajši. To je zdaj popolnoma enaka rešitev, vendar manj vrstic kode. Ko začnete priznava, da je to dobra rešitev, je tudi lažje razloga približno kot tako, v redu, zakaj moram to zastavo na desni int? Kaj to pomeni? Oh, to je pomenil, da vsakič, ko sem šel v redu, moram jo nastavite, pa če grem levo Moram jo nastavite na ničlo. Tukaj mi ni treba razlog za to, da je samo lažje razmišljati. Vprašanja? [Študent, nerazumljiv] >> Ja. Ok, tako da v zadnjem bit - Najbrž še ena hitra in enostavna naloga, kar lahko storimo, je, let's - skupaj, mislim, poskusite pisati vsebuje funkcijo ki ne skrbi, ali je dvojiško iskalno drevo. Ta vsebuje funkcijo je treba vrniti res Če kje v tem splošnem drevo binarno je vrednota, ki jo iščete. Torej najprej narediti rekurzivno in potem bomo to iterativno. Mi lahko dejansko samo to delamo skupaj, ker to bo res kratka. 

Kaj je moja osnovna bo treba? [Študent, nerazumljiv] [Bowden] Torej, če (drevo == NULL), kaj pa potem? [Študent] vrne false. [Bowden] Drugače, no, jaz ne potrebujem drugega. Če je bila moja druga osnovna. [Študentskih] Drevesni je vrednost? >> Ja. Torej, če (drevo-> vrednost == vrednost. Obvestilo smo spet na * vozlišče, vozlišče ni ** i? Vsebuje nikoli ne bo treba uporabiti vozlišče ** saj se ne spreminja kazalca. Mi smo jih le prečkajo. Če se to zgodi, potem smo res želeli vrniti. Sicer želimo prečkati otroke. Torej ne moremo argumentira o tem, ali je vse v levo manj in vse na desni je večja. Torej, kaj je naš pogoj, da bo tukaj - ali, kaj bomo storili? [Študent, nerazumljiv] >> Ja. Nazaj vsebuje (vrednost, drevo-> levo) ali vsebuje (vrednost, drevo-> desno). In to je to. In opazil, da je nekaj kratkega stika vrednotenje, kjer, če se zgodi, da bi našli vrednost v levem drevesu mi nikoli ni treba gledati na pravo drevo. To je celotno funkcijo. Zdaj pa to iterativno, , ki se bo manj prijetno. Mi bomo običajno začetek vozlišča * cur = dreves. Medtem ko je (tren! = NULL). Hitro bomo videli problem. Če tren - tukaj, če bomo kdaj izbruhne tega, Nato smo zmanjkalo stvari pogledati, tako vrne false. Če (tren-> vrednost == vrednost) return true. Torej, zdaj smo na mestu - Ne vemo, ali želimo iti v levo ali desno. Torej samovoljno, pojdiva levo. Očitno sem naletel na težavo, zaradi katere sem popolnoma opustila vse - Bom samo še preveriti na levi strani drevesa. Nikoli ne bo preveril vse, kar je pravica otroka ničesar. Kako to popraviti? [Študent], moraš slediti v levo in desno na kupu. [Bowden] Ja. Torej bi bilo struct seznam vozlišče * n, potem vozlišče ** naslednji? Mislim, da deluje v redu. Želimo, da gredo čez levo ali let's - tu gor. Struct = SEZNAM seznam, se bo začela se na tej struct seznam. * Seznam = NULL. Tako, da se bo naša povezani seznam od subtrees da smo preskočijo. Mi se bomo za prečkanje zdaj levo, ampak ker smo nujno potrebovali, da pridejo nazaj na desno, Gremo naprej na desni strani znotraj našega seznama struct. Potem bomo imeli new_list ali struct, struct seznam * new_list = malloc (sizeof (seznam)). Jaz bom prezreti napake kontrole, ampak bi morali preveriti, da vidim, če je nično. New_list vozlišče, da se dogaja, da kaže - oh, zato sem ga želel tukaj. To bo pomenilo, da se drugi seznam struct. To je samo, kako povezani seznami delo. To je isto kot int povezan seznam razen da smo samo zamenjava z int * vozlišča. To je popolnoma enako. Torej new_list, vrednost našega new_list vozlišče, se bo tre-> desno. Vrednost naše new_list-> next se bo naš prvotni seznam, in potem bomo posodobiti naš seznam izpostaviti new_list. 

Zdaj moramo nekakšen način vlečejo stvari, kot smo prehodil celotno levo poddrevo. Zdaj moramo vleči stvari iz njega, kot tren je nična, ne želimo, da samo vrne false. Želimo, da se zdaj vleči zunaj na naši novi seznam. Priročen način za to - no, pravzaprav, obstaja več načinov za to. Vsakdo ima predlog? Kje je treba to storiti in kako bi moral to storiti? Imamo le nekaj minut, a kakšen predlog? Namesto - en način, namesto naših razmerah pa medtem, kaj smo trenutno iščejo ni nič, namesto tega se bomo še naprej, dokler gre naš seznam sam je nična. Torej, če je naš seznam konča pa nič, potem smo zmanjkalo stvari za iskanje, da poiščete več. Toda to pomeni, da je prva stvar v našem seznamu je le, da bo treba najprej vozlišče. Prva stvar, ki bo - mi ni več treba videti. Torej, seznam-> bo n je naša drevo. seznam-> next se bo nič. In zdaj, ko seznam ni enaka null. OR bo potegniti nekaj iz našega seznama. Torej tren bo enako Seznam-> n. In potem se bo seznam enakega Seznam-> n, ali seznam-> naslednji. Torej, če tren vrednost je enaka vrednosti. Sedaj lahko dodate tako naši desni kazalec in našo levi kazalec dokler nisi nič. Tukaj, mislim, da bi morali storiti, da na prvem mestu. Če (tren-> desno! = NULL) Nato se bomo, da vstavite to vozlišče v našem seznamu. Če (tren-> levo), to je malo dodatnega dela, ampak to je v redu. Če (tren-> levi! = NULL) in bomo vstavili v levo v našo povezani seznam, in to bi moralo biti to. Mi Ponovil - dokler imamo nekaj v našem seznamu imamo še eno vozlišče na pogled. Torej, gledamo na to vozlišče, pospešimo naš seznam na naslednjega. Če je vozlišče je vrednota, ki jo iščeš, se lahko vrnemo res. Sicer vstaviti tako naši levi in ​​desni subtrees, dokler si ni nič, v našem seznamu tako da bomo neizogibno nad njimi. Torej, če ne bi bili nič, Če naša root kazalec poudaril dve stvari, potem pa smo najprej potegnil nekaj ven, da naš seznam konča pa nič. In potem smo se dve stvari nazaj, tako da zdaj naš seznam z velikostjo 2. Potem bomo zanko nazaj in mi greš samo za vleko, recimo, levi kazalec naše korenine vozlišče. In ti, ki kar naprej dogaja, da bomo na koncu zanka nad vsem. 

Vedite, da je to precej bolj zapleteno v rekurzivni rešitvi. In sem rekel večkrat da je rekurzivna rešitev ponavadi nima veliko skupnega z iterativno rešitev. Tu to je točno tisto, kar rekurzivna rešitev počne. Edina sprememba je, da namesto implicitno uporabi sklad, program za sklad, kot vaš način sledenja, kar vozlišča še vedno je treba obiskati, Zdaj boste morali uporabiti izrecno povezan seznam. V obeh primerih boste sledenja kaj vozlišče je treba še obiskal. V primeru, rekurzivni je samo lažje, ker sklad se izvaja za vas programa dimnika. Obvestilo, da je to povezano s seznama, je kup. Karkoli smo pravkar dal na kupu takoj, kaj bomo odstranite sveženj za obisk drugega. Zmanjkuje nam časa, ampak kakšno vprašanje? [Študent, nerazumljiv] [Bowden] Ja. Torej, če imamo povezan seznam, Sedanja se bo izpostaviti s tem moškim, in zdaj smo šele pospeševanja našega povezan seznam, da se osredotoči na tega tipa. Mi smo vozili v povezanem seznamu v tej vrstici. In potem mislim, da bi morali osvoboditi našo povezan seznam in stvari enkrat pred vrnitvijo v resničen ali neresničen, moramo Ponovil nad našim povezan seznam in vedno tukaj, mislim, če tren pravica ni enak, ga dodajte, zdaj želimo osvoboditi tren ker, no, pa smo povsem pozabili na seznamu? Ja. Torej, to je tisto, kar želimo na tem mestu. Kje je kazalec? OR je bil takrat - želimo, da seznam struct * 10 enak seznam naslednjo. Brezplačna seznam, seznam = temp. In v primeru, ko se vrnete smo res, pa je treba, da izbirate v preostalem našem povezanem seznamu ostane več stvari. Za lepo stvar o rekurzivnega rešitev je sprostitev stvari samo pomeni, živahen factorings off sklad, ki se bo zgodilo za vas. Tako smo šli iz nečesa, kar je podobno 3 vrstic težko razmišljati o zakoniku- nekaj, kar je pomembno še veliko več jih je težko razmišljati o tem, vrstic kode. Vse več vprašanj? V redu. Mi smo dobro. Adijo! [CS50.TV]