[Powered by Google Translate] [Secțiunea 7: mai confortabil]
[Rob Bowden] [Universitatea Harvard]
[Acest lucru este CS50] [CS50.TV]
Bine. Deci, așa cum am spus în email-ul meu,
acest lucru este mergi la a fi o secțiune binar-tree-intensiv.
Dar nu sunt atât de multe întrebări.
Deci, vom încerca să scoată fiecare întrebare
și du-te în detalii dureroase a tuturor cele mai bune moduri de a face lucruri.
Deci, chiar de la început, vom trece prin desene eșantion de copaci binare si alte chestii.
Deci, aici, "Amintiți-vă că un arbore binar are noduri similare cu cele ale unei liste legate,
cu excepția loc de un pointer sunt două: una pentru "copil" din stânga
și unul pentru dreptul de "copil". "
Deci, un arbore binar este la fel ca o listă legat,
cu excepția struct va avea doi pointeri.
E copaci trinary, care urmează să aibă trei indicii,
există N-are copaci, care au doar un pointer generic
că trebuie apoi să malloc să fie suficient de mare pentru a avea
Pointeri suficiente pentru toți copiii posibile.
Deci, arbore binar doar se întâmplă să aibă un număr constant de doi.
Dacă doriți, puteți da o listă legat ca un copac unară,
dar nu cred că cineva îl numește asta.
"Desenați o diagramă Cutii-si-săgeți a unui nod arbore binar
conținând numărul de preferat lui Nate, 7, în cazul în care fiecare copil indicatorul este nulă. "
Deci, iPad modul.
>> O să fie destul de simplu.
Suntem doar de gând să aibă un nod, voi trage ca un pătrat.
Și eu voi trage valorile aici.
Deci, valoarea va merge aici,
și apoi în jos aici, vom avea indicatorul stânga pe stânga și dreapta pe indicatorul din dreapta.
Și este foarte mult, astfel convenție să-l numesc stânga și dreapta, numele indicatorului.
Ambele dintre acestea sunt de gând să fie nul.
Asta va fi doar nulă, și că va fi doar nul.
Bine. Deci, înapoi la aici.
"Cu o listă legată, am avut doar pentru a stoca un pointer
la primul nod din lista, pentru a aminti întreaga listă legată, sau intreaga lista.
De asemenea, cu copaci, avem doar pentru a stoca un pointer
la un singur nod, în scopul de a aminti copac întreg.
Acest nod este Calle "rădăcina" din copac.
Să se bazeze pe diagrama dvs. din înainte de a desena sau de unul nou
astfel că aveți o descriere Cutii-si-săgeți de un copac binar
cu valoarea 7, apoi 3 în stânga,
apoi 9 pe dreapta, și apoi 6 pe dreapta 3. "
Să vedem dacă îmi amintesc toate că, în capul meu.
Deci, acest lucru se va fi radacina noastra aici.
Vom avea niște indicatorul undeva, ceva ce vom numi rădăcină,
și se indică spre acest tip.
Acum, pentru a face un nou nod,
ceea ce avem, 3 pe partea stângă?
Deci, un nou nod cu 3, și-l amintește inițial nule.
Voi pune doar N.
Acum vrem să facem ca merge la stânga 7.
Deci, vom schimba acest indicator pentru a indica acum la acest tip.
Și noi facem la fel. Ne dorim un 9 pe aici
care, inițial, doar spune nul.
Vom schimba acest indicator, punctul 9,
și acum vrem să 6 la dreapta de 3.
Deci, o să - face un 6.
Și că tipul va indica acolo.
Bine. Deci, asta e tot ce ne cere să facem.
>> Acum hai să mergem peste unele terminologia.
Am vorbit deja despre modul în rădăcina arborelui este nodul cel mai de sus în copac.
Unul conținând 7. Nodurile de la partea de jos a arborelui se numesc frunze.
Orice nod care are la fel ca și copiii săi nulă este o frunză.
Deci, este posibil, în cazul în care copacul nostru binar este doar un singur nod,
că un copac este o frunză, și asta e tot.
"" Înălțime "a arborelui este numărul de hamei trebuie să facă
pentru a obține din partea de sus a unei frunze. "
Vom intra in, într-un al doilea, diferența
între copaci echilibrate și neechilibrate binare,
dar pentru moment, înălțimea totală a acestui copac
Aș spune că este de 3, desi daca te numeri numărul de hamei
trebuie să facă, în scopul de a ajunge la 9, atunci este într-adevăr doar o înălțime de 2.
Chiar acum aceasta este un arbore binar dezechilibrat,
dar vom vorbit despre echilibrată atunci când acesta devine a fi relevant.
Deci, acum putem vorbi despre nodurile într-un copac din punct de vedere
în raport cu alte noduri din arbore.
Deci, acum avem părinți, copii, frați, strămoși, și a descendenților.
Ele sunt destul de comune sens, ceea ce înseamnă acestea.
Dacă ne întrebați - parintii sai.
Deci, ce este mamă a 3?
[Studenții] 7. Da >>. Mamă este doar de gând să fie ceea ce arată spre tine.
Atunci de ce sunt copiii de la 7?
Elevii [] 3 și 9. Da >>.
Observați că "copiii" înseamnă, literal, copii,
deci 6 nu s-ar aplica, pentru că e ca un nepot.
Dar, apoi, dacă mergem descendenți, astfel încât ceea ce sunt descendenții 7?
[Studenții] 3, 6 și 9. Da >>.
Descendenți ai nodului radacina va fi totul în copac,
cu excepția, poate nodul rădăcină în sine, în cazul în care nu doriți să ia în considerare faptul că un descendent.
Și, în cele din urmă, strămoșii, așa că e în direcția opusă.
Deci, ce sunt strămoșii din 6?
Elevii [] 3 și 7. Da >>. 9 nu este inclus.
E doar înapoi linia directa la rădăcină
va fi strămoșii dumneavoastră.
>> "Noi spunem că un arbore binar este" comandat ", în cazul în care pentru fiecare nod din arbore,
toti descendentii sai de pe partea stângă au valori mai mici
și toate cele de pe dreapta au valori mai mari.
De exemplu, arborele de mai sus este ordonat, dar nu e posibilă doar aranjament ordonat. "
Înainte de a ajunge la faptul că,
un arbore binar ordonat este, de asemenea, cunoscut ca un arbore binar de căutare.
Aici se întâmplă să fie numindu-l un arbore binar ordonat,
dar nu am auzit numit un arbore binar ordonat înainte,
și pe un test suntem mult mai probabil să afișezi arbore binar de căutare.
Sunt unul și același,
și este important să recunoaștem distincția între arbore binar și arbore binar de căutare.
Un arbore binar este doar un copac care indică spre două lucruri.
Fiecare nod indică două lucruri.
Nu există nici raționamentul cu privire la valorile pe care le puncte la.
Deci, ca aici, din moment ce este un arbore binar de căutare,
știm că dacă vom merge plecat din 7,
atunci toate valorile pe care le pot atinge, eventual,
de a merge mai rămas din 7 trebuie să fie mai mică de 7.
Observați că toate valorile sunt mai puțin de 7 3 și 6.
Acestea sunt toate la stânga 7.
Dacă mergem la dreptul de 7, tot ceea ce trebuie să fie mai mare de 7,
9 este atât de la dreapta din 7, deci suntem bine.
Acest lucru nu este cazul pentru un arbore binar,
pentru un arbore binar regulat, putem avea doar 3 la partea de sus, 7 la stânga,
9 la stânga 7; nu există nici un fel de ordonare a valorilor.
Acum, nu vom face de fapt acest lucru pentru că e plictisitor și inutil,
dar "încearcă să atragă cât mai multe copaci ordonate după cum puteți gândi
folosind 7 numere, 3, 9, și 6.
Câte acorduri distincte sunt acolo? Care este înălțimea de fiecare? "
>> Vom face un cuplu, dar ideea principală este,
aceasta este în nici un fel o reprezentare unică a unui arbore binar care conține aceste valori.
Tot ce avem nevoie este un arbore binar care conține 7, 3, 6, și 9.
Un altul ar fi posibil, valabilă radacina este 3,
du-te la stânga și e 6, du-te la stânga și este 7,
du-te la stânga și e 9.
Acesta este un perfect valabil arbore binar de căutare.
Nu e de mare ajutor, pentru ca este la fel ca o listă legată
și toate aceste indicii sunt doar nule.
Dar este un copac validă. Da?
[Student] Nu valorile trebuie să fie mai mare pe dreapta?
Sau este aceasta -? Acestea >> Am vrut să merg în altă parte.
Există, de asemenea - Da, hai să comutați asta.
9, 7, 6, 3. Bine captură.
Ea mai are încă să asculte ceea ce un arbore binar de căutare ar trebui să facă.
Deci, totul pentru a stânga trebuie să fie mai mică decât orice nod dat.
Am putea muta doar, să zicem, acest 6 și pune-l aici.
Nu, nu putem. De ce am continui sa faci asta?
Să facem - aici este de 6, aici este de 7, 6 puncte la 3.
Acest lucru este valabil încă un arbore binar de căutare.
Ce este greșit în cazul în care I - Să văd dacă pot veni cu un aranjament.
Da, bine. Deci, ce este în neregulă cu acest copac?
Cred că am dat deja un indiciu că există ceva în neregulă cu ea.
De ce am continui sa faci asta?
Bine. Acest lucru pare rezonabil.
Dacă ne uităm la fiecare nod, cum ar fi 7, apoi la stânga 7 este un 3.
Deci avem 3, lucru de dreapta de 3 este un 6.
Și dacă te uiți la 6, lucru de dreapta 6 este un 9.
Deci, de ce nu este aceasta o adresă de arbore binar de căutare?
Elevii [] 9 este încă la stânga 7. Da >>.
Acesta trebuie să fie adevărat că toate valorile pe care le poate ajunge, eventual, de a merge la stânga din 7 sunt mai puțin de 7.
Dacă mergem plecat din 7, ajungem la 3 și putem obține încă la 6,
putem obține încă la 9, dar prin ce a trecut mai puțin de 7,
nu ar trebui să fie în măsură pentru a ajunge la un număr care este mai mare decât 7.
Deci, acest lucru nu este valabil un arbore binar de căutare.
>> Fratele meu a avut de fapt o întrebare de interviu
care a fost practic acest lucru, pur și simplu cod ceva pentru a valida
dacă un copac este un arbore binar de căutare,
și astfel primul lucru pe care la făcut a fost doar verificați pentru a vedea
în cazul în care stânga și dreapta sunt corecte, iar apoi repeta acolo.
Dar tu nu poți face asta doar, trebuie să țină evidența
de faptul că acum că am plecat plecat din 7,
totul în acest subarbore trebuie să fie mai mică de 7.
Algoritmul corectă trebuie să țină evidența
de limitele pe care valorile pot cădea, eventual inch
Noi nu va trece prin toate.
Există o relație frumoasă recurență,
deși nu am ajuns la cei, sau nu vom ajunge la cei,
definirea cât de multe sunt de fapt.
Deci, există 14 dintre ele.
Ideea de modul în care v-ați putea face matematic este ca,
puteți alege orice unul singur pentru a fi nodul rădăcină,
și apoi, dacă am alege 7 pentru a fi nodul rădăcină,
atunci există, să zicem, unele numere care pot merge fi nodul meu stâng,
și există unele numere care pot fi nodul meu drept,
dar dacă n-am numărul total, atunci suma care poate merge la stânga
plus suma care poate merge la dreapta este n - 1.
Deci, din numerele rămase, acestea trebuie să fie în măsură de a merge, fie la stânga sau la dreapta.
Se pare dificil ca, în cazul în care am pus 3 primul, apoi totul trebuie să meargă la stânga,
dar daca am pus 7, atunci unele lucruri pot merge la stânga și unele lucruri pot merge la dreapta.
Și prin '3 'început, am vrut tot ce pot merge la dreapta.
E adevarat, trebuie doar să se gândească la ea ca,
cât de multe lucruri pot merge la următorul nivel al arborelui.
Și iese să fie 14; sau puteti desena toate acestea,
și apoi veți obține 14.
>> Mergând înapoi aici,
"Copaci ordonate binare sunt cool, deoarece putem căuta prin intermediul lor
într-un mod foarte asemănător cu căutarea într-o matrice sortate.
Pentru a face acest lucru, vom începe de la rădăcină și să lucreze drumul nostru în jos copac
spre frunze, verificarea valorilor fiecare nod împotriva valorilor pe care le căutați.
Dacă valoarea nodul curent este mai mică decât valoarea căutăm,
te duci lângă copilului nodul are dreptate.
În caz contrar, te duci la copil nodului din stânga.
La un moment dat, veți găsi fie valoarea pe care îl căutați pentru, sau vei alerga intr-o nulă,
indicând valoarea nu e în copac. "
Trebuie să aspira copac am avut-o înainte, că va lua o secundă.
Dar vrem să se uite în sus dacă 6, 10, și 1 sunt în copac.
Deci, ceea ce a fost, 7, 9, 3, 6. Bine.
Numerele pe care doriți să te uiți în sus, vrem să te uiți în sus 6.
Cum functioneaza acest algoritm?
Ei bine, avem, de asemenea, unele indicatorul rădăcină la copacul nostru.
Și ne-ar merge la rădăcină și să spunem, această valoare este egală cu valoarea pe care o căutați?
Deci, suntem în căutarea de 6, asa ca nu e egal.
Deci, vom continua, iar acum spunem, ok, deci 6 este mai mică de 7.
Asta înseamnă că vrem să mergem la stânga, sau nu vrem să mergem la dreapta?
[Student] Left. Da >>.
E mult mai ușor, tot ce trebuie să faceți este să atragă un nod posibilă copac
si apoi nu - în loc de a încerca să se gândească în capul tău,
ok, daca e mai putin, nu mă duc la stânga sau la dreapta du-te,
doar se uită la această imagine, este foarte clar că trebuie să mă duc la stânga
în cazul în care acest nod este mai mare decât valoarea pe care îl caut.
Deci, te duci la stânga, acum sunt la 3.
Vreau să - 3 este mai mică decât valoarea caut, care este de 6.
Deci, mergem la dreapta, iar acum am ajuns la 6,
care este valoarea caut, așa că am întoarce adevărat.
Valoarea viitoare am de gând să caute este de 10.
Bine. Deci 10, acum, este de gând să - taie, care - de gând să urmeze rădăcină.
Acum, 10 va fi mai mare de 7, așa că vreau să te uiți la dreapta.
Am de gând să vin aici, 10 va fi mai mare de 9,
așa că am de gând să doriți să te uiți la dreapta.
Am venit aici, dar aici, acum eu sunt la null.
Ce trebuie să fac dacă am lovit nulă?
[Student] Înapoi fals? Da >>. Nu am găsit 10.
1 este de gând să fie un caz aproape identic,
cu excepția faptului că e doar de gând să fie oglindită, în loc de a privi
pe partea dreapta, am de gând să se uite în jos în partea stângă.
>> Acum cred că vom ajunge de fapt la codul.
Iată unde - deschide aparatul și să navigați CS50-ți de drum acolo,
dar tu chiar poti face, de asemenea, că în spațiu.
Este, probabil, ideal pentru a face acest lucru în spațiu,
deoarece putem lucra în spațiu.
"În primul rând avem nevoie de o definiție de tip nou pentru un nod arbore binar care conține valori int.
Utilizarea șabloane typedef de mai jos,
creați o definiție de tip nou pentru un nod într-un arbore binar.
Dacă te blochezi. . . "Bla, bla, bla. Bine.
Așa că hai să punem șabloane aici,
typedef struct nod, nod și. Da, bine.
Deci, ce sunt domeniile am de gând să doriți în nodul nostru?
[Student] Int și apoi doi pointeri?
Int >> valoare, doi pointeri? Cum pot scrie indicii?
[Student] Struct. Ar trebui să >> zoom inch Da, așa nod struct * a plecat,
și struct nod * dreapta.
Și amintiți-vă discuția din ultimul timp,
că acest lucru nu are sens, acest lucru nu are sens,
acest lucru nu are sens.
Ai nevoie de tot ce există, în scopul de a defini acest struct recursiv.
Ok, deci asta e ceea ce copacul nostru va arăta.
Dacă am un copac trinary, apoi un nod s-ar putea arata ca B1, B2, B3 struct nod *,
unde b este o ramură - de fapt, am mai auzit-o la stânga, mijloc, dreapta, dar indiferent.
Ne pasă doar despre binar, deci dreapta, stânga.
"Acum, să declare o variabilă globală * nod pentru rădăcina arborelui."
Deci, nu vom face asta.
În scopul de a face lucrurile puțin mai dificil și mai generalizate,
nu vom avea o variabilă globală nod.
În schimb, în ​​principal ne vom declara toate lucrurile noduri,
și asta înseamnă că de mai jos, atunci când vom începe să ruleze
Funcția noastră conține și funcția noastră inserați,
Conține în loc de noastre funcționează doar folosind această variabilă nod la nivel mondial,
am de gând să-l ia ca avea un argument copac pe care ne-o dorim pentru a procesa.
Având în variabila globală a fost trebuia să facă lucrurile mai ușor.
Vom face lucrurile mai greu.
Acum, ia un minut sau cam asa ceva doar pentru a face acest tip de lucru,
în cazul în care în interiorul principal pe care doriți să creați acest copac, și asta e tot ce vrei să faci.
Încercați și construi acest arbore în funcția principală.
>> Bine. Deci, nu trebuie nici măcar să fi construit arborele tot drumul încă.
Dar oricine are ceva ce ar putea trage în sus
pentru a arăta modul în care s-ar putea începe construirea un astfel de copac?
[Student] Cineva trage, încercând să iasă.
[Bowden] Oricine confortabil, cu construcții de copac lor?
[Student] Sigur. Nu e gata. >> E bine. Putem termina doar -
oh, poți să-l salvezi? Ura.
Deci aici avem - Oh, mă taie ușor off.
Sunt mărită?
Măriți, derulați afară. >> Am o întrebare. Da >>?
[Student] Când definiți struct, sunt lucruri cum ar fi inițializat la ceva?
[Bowden] Nr >> Bine. Deci, va trebui să se inițializeze -
[Bowden] Nr Când definiți, sau atunci când declară un struct,
nu este inițializată în mod implicit, e la fel ca în cazul în care ați declara un int.
E exact acelasi lucru. E ca și cum fiecare dintre domeniile sale individuale
poate avea o valoare de gunoi în ea. Și >> este posibil să se definească - sau pentru a declara o struct
într-un mod care le face inițializa?
[Bowden] Da. Deci, comenzi rapide de inițializare sintaxă
este de gând să arate -
Sunt două moduri prin care putem face acest lucru. Cred că ar trebui să-l compilați
pentru a face să răsune-vă că, de asemenea, face acest lucru.
Pentru a argumentelor care vine în struct,
ai pus ca ordinea de argumente în interiorul acestor acolade.
Deci, dacă doriți să-l inițializa la 9 și a lăsat să fie nul și apoi să fie nul dreapta,
ar fi 9, null, null.
Alternativa este, iar editorul nu îi place această sintaxă,
și crede că vreau un bloc nou,
dar alternativa este ceva de genul -
aici, am să-l pun pe o linie nouă.
Poti spune în mod explicit, am uitat sintaxa exactă.
Deci, vă puteți adresa în mod explicit le pe nume, și spune,
C, sau. Valoare. = 9, stânga =. NULL.
Bănuiesc că acestea ar trebui să fie virgule.
. Dreapta = NULL, deci acest mod nu
de fapt, trebuie să știe ordinea de struct,
și atunci când sunteți de lectură acest lucru, este mult mai explicite
despre ceea ce este valoarea fiind pregătit pentru a.
>> Acest lucru se întâmplă să fie unul din lucrurile pe care -
astfel, pentru cea mai mare parte, C + + este un superset a lui C.
Puteți să luați cod C, mutați-l la C + +, și ar trebui să compileze.
Acesta este unul dintre lucrurile pe care C + + nu acceptă, astfel încât oamenii au tendința de a nu-l face.
Nu știu dacă asta e singurul motiv pentru care oamenii au tendința de a nu-l face,
dar cazul în care am nevoie să-l folosească necesare pentru a lucra cu C + + si asa nu am putut folosi asta.
Un alt exemplu de ceva care nu funcționează cu C + + este
cum malloc returnează un "void *," punct de vedere tehnic,
dar ai putea spune doar char * x = indiferent de malloc,
și va fi în mod automat pentru a arunca un char *.
Asta exprimate automată nu se întâmplă în C + +.
Asta nu s-ar compila, și v-ar trebui să spun în mod explicit
char *, malloc, oricare ar fi, să-l arunce într-o char *.
Nu sunt multe lucruri pe care C și C + + nu sunt de acord cu privire,
dar acestea sunt două.
Deci, vom merge cu această sintaxă.
Dar, chiar dacă nu ne-am dus cu sintaxa,
ceea ce este - ar putea fi în neregulă cu asta?
[Student] nu am nevoie să-l dereference? Da >>.
Amintiți-vă că săgeata are un dereference implicită,
și așa că atunci când suntem doar de-a face cu o struct,
vrem sa folosim. pentru a ajunge la o în interiorul câmpului de struct.
Și singura dată când am folosi săgeata este atunci când vrem să facem -
bine, săgeata este echivalent cu -
asta e ceea ce ar fi însemnat dacă am folosit săgeată.
Toate mijloacele săgeata este, dereference asta, acum eu sunt la o struct, și eu pot obține teren.
Obține fie direct în câmp sau dereference și pentru a obține teren -
Cred că acest lucru ar trebui să fie o valoare.
Dar aici am de-a face doar cu o struct, nu un pointer la o structura,
și deci nu pot folosi săgeată.
Dar acest fel de lucru pe care îl putem face pentru toate nodurile.
Oh, Doamne.
Acest lucru este de 6, 7, și 3.
Atunci putem configura sucursale în copacul nostru, putem avea 7 -
Putem avea, stanga ar trebui să arate la 3.
Deci, cum facem asta?
[Elevii, neinteligibil] >> Da. Adresa de node3,
și dacă nu aveți adresa, atunci pur și simplu nu s-ar compila.
Dar amintiți-vă că acestea sunt pointeri la nodurile următoare.
Drept ar trebui să arate la 9,
și 3 ar trebui să arate pe dreapta la 6.
Cred că asta este totul setat. Orice comentarii sau întrebări?
[Student, neinteligibil] rădăcină va fi 7.
Noi putem spune doar nod * ptr =
sau rădăcină, = & node7.
>> Pentru scopurile noastre, vom fi de-a face cu inserție,
așa că de gând să doriți să scrie o funcție pentru a insera în acest arbore binar
și inserția este inevitabil va suna malloc pentru a crea un nod nou pentru acest copac.
Deci, lucrurile sunt mergi la a lua murdar cu faptul că unele noduri
sunt în prezent pe stivă
și alte noduri de gând să se încheie pe movila atunci când le introduceți.
Acest lucru este perfect valabil, dar singurul motiv
suntem capabili să facă acest lucru pe stivă
se datorează faptului că este un astfel de exemplu contrived că știm
copac ar trebui să fie construite în așa fel 7, 3, 6, 9.
Dacă nu am avea acest lucru, atunci nu ne-ar trebui să malloc în primul rând.
După cum vom vedea un pic mai târziu, ar trebui să ne malloc'ing.
Chiar acum e perfect rezonabil pentru a pune în stivă,
dar hai să schimbăm acest lucru să o implementare malloc.
Deci, fiecare dintre acestea este acum va fi ceva de genul
nod * node9 = malloc (sizeof (nod)).
Și acum vom avea de a face check nostru.
în cazul în care (node9 == NULL) - N-am vrut asta -
întoarcă 1, și apoi putem face node9-> pentru ca acum e un pointer,
valoare = 6, node9-> left = NULL,
node9-> dreapta = NULL,
și am de gând să aibă de a face acest lucru, pentru fiecare dintre aceste noduri.
Deci, în loc, să-l pună în interiorul unei funcții separate.
Să-i spunem nod * build_node,
și acest lucru este oarecum similar cu API-uri noi oferim pentru codare Huffman.
Noi vă oferim funcții de inițializare pentru un copac
și Deconstructor "funcții" pentru acele copaci și aceleași pentru pădurilor.
>> Deci, aici vom avea o funcție de inițializare
pentru a construi doar un nod pentru noi.
Și se va arata destul de mult exact ca asta.
Iar eu chiar o să fie leneș și nu schimbați numele variabilei,
chiar dacă node9 are nici un sens mai.
Oh, cred că valoarea node9 nu ar fi fost 6.
Acum ne putem întoarce node9.
Și aici ar trebui să ne intoarce null.
Toata lumea de acord cu faptul că funcția Build-a-nod?
Deci, acum putem apela doar că pentru a construi orice nod cu o anumită valoare și pointeri nule.
Acum putem spune așa, putem face nod * node9 = build_node (9).
Și să facem. . .
6, 3, 7, 6, 3, 7.
Și acum vrem să înființeze pointerii aceleași,
cu excepția acum totul e deja în termeni de pointeri
astfel încât nu mai este nevoie de adresa.
Bine. Deci, ce e ultimul lucru pe care vreau să fac?
E o eroare de verificare pe care eu nu fac.
Ce înseamnă a construi retur nod?
[Student, neinteligibil] >> Da. În cazul în care nu a reușit malloc, aceasta va intoarce null.
Așa că am de gând să-l alene aici jos în loc de a face o condiție pentru fiecare.
În cazul în care (node9 == NULL, sau - mai simplu,
acest lucru este echivalent cu doar dacă nu node9.
Deci, dacă nu node9, sau nu node6, sau nu node3, sau nu node7, întoarce 1.
Poate că ar trebui să imprimați malloc nu a reușit, sau ceva de genul.
[Student] este fals: egal cu zero, precum și?
[Bowden] Orice valoare zero este falsă.
Deci, nul este o valoare zero.
Zero este o valoare zero. Fals este o valoare zero.
Orice - destul de mult de la numai 2 valori zero sunt nule și zero,
fals este la fel de distribuire definit ca zero.
Asta se aplică și dacă noi declarăm variabila globala.
Dacă am fi avut * rădăcină nodul aici,
apoi - lucru frumos despre variabile globale este că ei au întotdeauna o valoare inițială.
Asta nu e adevărat de funcții, cum în interiorul aici,
daca avem, cum ar fi *, nod sau nod x.
Nu avem nici o idee despre ceea ce x.value, x.whatever,
sau am putea să le imprimați și acestea ar putea fi arbitrară.
Asta nu-i adevărat de variabile globale.
Deci, radacina nod sau nod x.
În mod implicit, tot ceea ce este la nivel mondial, în cazul în care nu este explicit inițializat la o anumită valoare,
are o valoare zero ca valoare.
Deci, aici, radacina nod *, noi nu inițializa în mod explicit la ceva,
astfel încât valoarea sa implicită va fi nul, care este valoarea de zero de pointeri.
Valoarea implicită a lui x este de gând să înseamnă că x.value este zero,
x.left este nul, iar x.right este nul.
Deci, din moment ce este o struct, toate domeniile de struct va fi zero valori.
Nu avem nevoie să utilizați că aici, deși.
[Student] Cele struct sunt diferite de alte variabile, precum și alte variabile sunt
Valorile de gunoi, acestea sunt zerouri?
[Bowden] Alte valori prea. Deci, în x, x va fi zero.
Dacă e de la domeniul de aplicare la nivel mondial, aceasta are o valoare inițială. Bine >>.
[Bowden] Fie valoarea inițială pe care ați dat-o sau zero.
Cred că are grijă de toate astea.
>> Bine. Deci, următoarea parte a întrebării solicită,
"Acum vrem să scrie o funcție numită conține
cu un prototip de bool conține o valoare int. "
Noi nu suntem de gând să faci bool conține o valoare int.
Prototip nostru este de gând să arate
bool conține (valoare int.
Și apoi vom merge, de asemenea, să-l dați copac
că aceasta ar trebui să fie de verificare pentru a vedea dacă acesta are ca valoare.
Deci, nod * copac). Bine.
Și apoi putem să-l numim cu ceva de genul,
poate vom dori să printf sau ceva.
Conține 6, radacina noastra.
Asta ar trebui să se întoarcă unul, sau adevărat,
întrucât conține 5 rădăcină ar trebui să se întoarcă fals.
Astfel încât să ia un al doilea să pună în aplicare acest lucru.
Poti sa o faci, fie iterativ sau recursiv.
Cel mai frumos lucru despre modul în care ne-am stabilit lucrurile este faptul că
acesta se pretează la soluția noastră recursivă mult mai ușor
decât modul global-variabilă a făcut.
Pentru că dacă avem doar conține o valoare int, atunci avem nici un fel de recursiune jos subarbori.
Ne-ar trebui să aibă o funcție de ajutor separat care recurses stabilire a subarbori pentru noi.
Dar din moment ce ne-am schimbat-l să ia copac ca un argument,
care ar trebui să au fost întotdeauna în primul rând,
acum putem recurse mai ușor.
Deci, iterativ sau recursiv, vom trece peste atât,
dar vom vedea care se termină prin a fi recursive destul de usor.
Bine. Are cineva ceva ce putem lucra cu?
>> [Student] Am o soluție iterativ. >> Regulă, iterativ.
Bine, asta arata bine.
Deci, vrei să ne plimbăm prin ea?
[Student] Sigur. Asa ca am stabilit o variabilă temp pentru a obține primul nod al arborelui.
Și apoi am buclă prin temperatură nu, nu în timp ce nul egal,
astfel încât în ​​timp ce era încă în copac, cred.
Și dacă valoarea este egală cu valoarea pe care temperatura este îndreptat spre,
apoi revine ca valoare.
În caz contrar, se verifică dacă e pe partea dreapta sau stanga.
Dacă aveți vreodată o situație în care nu există nici un copac mai mult,
apoi revine - iese bucla si returneaza false.
[Bowden] Ok. Deci, care pare bun.
Oricine are nici un comentariu la ceva?
Nu am nici un comentariu de corectitudine, la toate.
Singurul lucru putem face este tipul ăsta.
Oh, o să meargă un pic alungit.
Voi rezolva asta. Bine.
>> Toată lumea ar trebui să ne amintim cum funcționează ternară.
Au fost cu siguranță teste în trecut
care vă oferă o funcție cu un operator ternar,
și spune, traduce aceasta, face ceva ce nu utilizează ternară.
Deci, acesta este un caz foarte comun de când mi-ar gândi să folosească ternare,
în cazul în care în cazul în care unele condiția stabilită o variabilă la ceva,
stabilit altceva care aceeași variabilă la altceva.
Asta e ceva ce foarte frecvent poate fi transformat în acest fel de lucru
în cazul în care variabila stabilit că la acest lucru - sau, ei bine, e adevărat? Apoi, acest, altceva asta.
[Student] Prima dintre ele este dacă este adevărat, nu?
[Bowden] Da. Modul în care am citit-o întotdeauna este, de temperatură este egală cu valoare mai mare decât valoarea temp,
atunci aceasta, altceva asta. A pune o întrebare.
Este mai mare? Atunci fă primul lucru. Face altceva doilea lucru.
Am aproape întotdeauna - colon, eu doar - în capul meu, am citit ca altcineva.
>> Are cineva o soluție recursiv?
Bine. Aceasta vom - ar putea fi deja mare,
dar vom face chiar mai bine.
Acest lucru este destul de mult exact aceeasi idee.
E doar, de bine, vrei să explici?
[Student] Sigur. Deci suntem asigurându-vă că arborele nu este NULL în primul rând,
pentru că dacă arborele este nulă, atunci o să se întoarcă falsă, deoarece nu am găsit-o.
Și dacă există încă un copac, mergem în - vom verifica mai întâi dacă valoarea este nodul curent.
Return true dacă este, și dacă nu am recurse la stânga sau la dreapta.
Sună caz? >> Mm-hmm. (Acord)
Deci, observăm că acest lucru este aproape - structural foarte similar cu soluția iterativ.
E doar că, în loc de recursiune, am avut o buclă în timp ce.
Și scenariul de bază aici, în cazul în care arborele nu null egal
a fost condiția în care ne-am despartit din bucla timp.
Sunt foarte asemanatoare. Dar vom lua acest pas mai departe.
Acum, facem același lucru aici.
Observați ne intoarcem același lucru în ambele linii,
cu excepția unui singur argument este diferit.
Deci, vom face ca într-un ternar.
Am lovit ceva opțiune, și a făcut un simbol. Bine.
Deci, vom reveni conține asta.
Acest lucru este obtinerea a fi mai multe linii, bine, mărită este.
De obicei, ca un lucru stilistic, nu cred că mulți oameni
pune un spațiu după săgeată, dar cred că dacă ești consecvent, e în regulă.
Dacă valoarea este mai mică decât valoarea copac, dorim să recurse la stânga copac,
altceva vrem să recurse la dreapta copac.
Așa că a fost un pas de a face acest aspect mai mici.
Pasul doi a face acest aspect mai mici -
putem separa acest lucru mai multe linii.
Bine. Pasul doi de a face sa arate mai mic este aici,
astfel încât valoarea este egală cu valoarea de retur copac, sau conține orice.
>> Acesta este un lucru important.
Nu sunt sigur dacă el a spus că în mod explicit în clasă,
dar se numește scurt-circuit de evaluare.
Ideea aici este valoarea == valoare copac.
Dacă acest lucru este adevărat, atunci acest lucru este adevărat, și vrem să "sau" care cu ceea ce este aici.
Deci, fără măcar să ne gândim cu privire la tot ce este aici,
ceea ce este expresia întregii gând să se întoarcă?
[Student] Adevărat? >> Da, pentru că adevărata de nimic,
or'd - or'd sau cu nimic adevărat este neapărat adevărat.
Asa ca imediat ce vom vedea valoare de retur = valoarea copac,
suntem doar de gând să se întoarcă adevărat.
Nici măcar nu o să recurse în continuare conține în jos linie.
Ne putem lua acest pas mai departe.
Rentabilitatea copac nu nul egală și toate astea.
Ea a făcut-o o functie de o linie.
Acest lucru este, de asemenea, un exemplu de scurt-circuit de evaluare.
Dar acum e aceeași idee -
în loc de - asa ca daca arborele nu nul egală - sau, ei bine,
în cazul în care nu copac nul egal, ceea ce este cazul rea,
în cazul în care este egal cu zero copac, apoi prima condiție va fi falsă.
Deci, fals anded cu orice va fi ce?
[Student] Fals. Da >>. Aceasta este cealaltă jumătate a scurt-circuitului de evaluare,
în cazul în care în cazul în care nu copac null nu este egal, atunci nu suntem de gând să meargă chiar -
sau în cazul în care nu copac nul egal, atunci nu vom face value == valoare copac.
Suntem doar de gând să se întoarcă imediat false.
Ceea ce este important, deoarece în cazul în care aceasta nu a scurt-circuit a evalua,
apoi, dacă nu copac null egal, această a doua condiție este de gând să vina seg,
deoarece copac-> valoare este nulă dereferencing.
Deci asta e. Poate face acest lucru - o dată trecerea peste.
Acesta este un lucru foarte comun, de asemenea, nu face asta singură linie cu acest lucru,
dar este un lucru comun în condiții, poate nu chiar aici,
dar dacă (copac = NULL,! și copac-> valoare == valoare), face orice.
Aceasta este o condiție foarte frecvente, în cazul în care în loc de a avea
pentru a sparge această în două FI, în cazul în care doriți, este nul copac?
Bine, nu e nul, asa ca acum este o valoare egală cu valoarea copac? Face acest lucru.
În schimb, această condiție, aceasta nu va SEG vina
pentru că va izbucni în cazul în care acest lucru se întâmplă să fie nul.
Ei bine, cred că în cazul în care arborele este un pointer invalid complet, acesta poate SEG încă vina,
dar nu poate SEG vina în cazul în care copacul este nulă.
Dacă ar fi fost nule, s-ar rupe înainte de ai dereferenced vreodată indicatorul în primul rând.
[Student] Este aceasta evaluare numita leneș?
>> Evaluarea [Bowden] Lazy este un lucru separat.
Evaluarea leneș este mai mult ca să vă întreb pentru o valoare,
vă întreb pentru a calcula o valoare, un fel de, dar nu ai nevoie de ea imediat.
Deci, până când de fapt nevoie de ea, nu este evaluată.
Acest lucru nu este exact același lucru, dar în PSET Huffman,
se spune că noi "alene" scrie.
Motivul pentru care face acest lucru este pentru că suntem, de fapt tamponare scriere -
nu vrem să scrie biți individuali la un moment dat,
sau bytes individuale la un moment dat, am în schimb doriți să obțineți o bucată de octeți.
Apoi, după ce vom avea o bucată de octeți, atunci vom scrie.
Chiar dacă ai cere să scrie - și fwrite si fread facă același tip de lucru.
Ei tampon citește și scrie.
Chiar dacă ai cere să scrie imediat, probabil că nu va fi.
Și nu poți fi sigur că lucrurile se vor fi scris
până când apelați hfclose sau orice ar fi,
care apoi spune, bine, eu sunt de închidere dosarul meu,
înseamnă că aș scrie mai bine tot ceea ce nu am scris încă.
Ea nu are nevoie să scrie totul
până când se închid fișierul, și apoi trebuie să.
Deci, asta e doar ceea ce leneș - se așteaptă până când acesta are să se întâmple.
Acest lucru - să ia 51 și veți intra în el, în mai multe detalii,
deoarece OCaml și totul în 51, totul este recursivitate.
Nu există nici o iterativ solutii, practic.
Totul este recursivitate, leneș și evaluare
va fi important pentru o mulțime de împrejurări
în cazul în care, în cazul în care nu ați evalua leneș, asta ar însemna -
Exemplu este fluxuri, care sunt infinit de lungi.
În teorie, vă puteți gândi la numerele naturale, ca un flux de 1-2-3-4-5-6-7,
Deci, lucrurile sunt bine evaluate alene.
Dacă eu spun că vreau numărul zecelea, atunci pot evalua până la numărul zecea.
Dacă vreau numărul suta, atunci pot evalua până la numărul suta.
Fara evaluare leneș, atunci va încerca să evalueze toate numerele imediat.
Te evaluarea numere infinit de multe, și că nu e doar posibil.
Deci, există o mulțime de situații în care leneș de evaluare
este doar esențial pentru obținerea lucrurile să funcționeze.
>> Acum vrem să scrie inserați în cazul în care se introduce o să fie
În mod similar schimbarea în definiția sa.
Deci, acum e inserați bool (valoare int).
Vom schimba asta pentru a insera bool (int valoare, nod copac *).
Suntem de fapt, se va schimba din nou într-un pic, vom vedea de ce.
Și haideți să mutați build_node, doar pentru placerea de a se,
de mai sus se introduce așa că nu trebuie să scrie un prototip funcție.
Care este un indiciu că ai de gând să fie utilizând build_node în inserare.
Bine. Ia un minut pentru asta.
Cred că am salvat de revizuire în cazul în care doriți să trageți din faptul că,
sau, cel puțin, am făcut-o acum.
Am vrut o pauză ușoară să se gândească la logica Inserare,
în cazul în care nu se poate gândi la ea.
Practic, va fi doar introducerea vreodată la frunze.
Ca, daca am introduce 1, apoi am de gând să fie în mod inevitabil inserarea 1 -
Voi schimba la negru - Voi fi inserarea 1 aici.
Sau dacă am introduce 4, vreau să fie inserarea 4 aici.
Deci, indiferent de ceea ce faci, ai de gând să fie introducerea la o frunză.
Tot ce trebuie să faceți este să itera în jos arborele până când ajunge la nodul
care ar trebui să fie mamă nodului, nodul părinte nou,
și modificați apoi indicatorul sa stânga sau la dreapta, în funcție de
e mai mare sau mai mică decât nodul curent.
Modificarea că indicatorul pentru a indica nodul nou.
Deci, repeta jos copac, face punctul de frunze la nod nou.
De asemenea, cred despre motivul pentru care interzice tip de situație înainte,
în cazul în care am construit arborele binar în cazul în care acesta a fost actualizată
Dacă ați uitat doar la un singur nod,
dar 9 a fost la stânga din 7, dacă reiterat în jos tot drumul.
Deci, asta e imposibil în acest scenariu, deoarece -
cred ca introducerea aproximativ 9 sau ceva, iar la nodul prima,
Mă duc să văd 7 și Mă duc să meargă la dreapta.
Deci, indiferent de ceea ce fac, dacă am introduce prin a merge la o frunză,
și să o frunză folosind algoritmul corespunzător,
că va fi imposibil pentru mine pentru a insera 9 la stânga din 7
pentru ca imediat ce m-am lovit 7 am de gând să merg la dreapta.
Are cineva ceva pentru a începe cu?
[Student] fac. Sigur >>.
[Student, neinteligibil]
[Alt student, neinteligibil]
[Bowden] E apreciat. Bine. Vrei să explici?
>> [Student] Din moment ce știm că am fost inserarea
noduri noi la sfârșitul arborelui,
Am o buclă prin copac iterativ
până când am ajuns la un nod care a indicat zero.
Și apoi m-am decis să-l pună fie pe partea dreapta sau stanga
folosirea acestui drept variabilă, ea mi-a spus unde să-l puneți.
Și apoi, în esență, am facut asta ultima -
acel nod punct temp la nod nou, care a fost crearea,
fie pe partea stângă sau pe partea dreaptă, în funcție de ceea ce a fost corect valoarea.
În cele din urmă, am setat valoarea nod nou la valoarea de testare sale.
[Bowden] Ok, deci văd o problemă aici.
Acest lucru este la fel ca 95% din drum acolo.
Problemă pe care am vedea, ei bine, nu oricine altcineva vedea o problemă?
Care este împrejurarea în care acestea iesi din bucla?
[Student] Dacă temperatura este nul? Da >>. Deci, cum ai rupe din bucla este dacă temperatura este nulă.
Dar ce fac aici?
Am temp dereference, care este în mod inevitabil nulă.
Deci, un alt lucru ce trebuie sa faci este sa tii nu doar piesa pana cand temperatura este nul,
doriți să urmăriți mamă în orice moment.
Ne dorim, de asemenea, * nodul părinte, cred că putem păstra ca la nul la început.
Acest lucru se întâmplă pentru a avea un comportament ciudat pentru rădăcina arborelui,
dar vom ajunge la asta.
Dacă valoarea este mai mare decât orice, atunci temperatura = temp dreapta.
Dar, inainte de a face asta, mamă = temp.
Sau sunt părinții întotdeauna de gând să temperatura egal? Este faptul că cazul?
În cazul în care temperatura nu este nul, atunci am de gând să vă deplasa în jos, indiferent de ce,
la un nod pentru care temperatura este mamă.
Deci, mamă va fi temp, iar apoi m-am muta în jos temp.
Acum, temperatura este nul, dar subliniază mamă la mamă de lucru care este nul.
Deci aici, nu vreau să setați adică dreapta 1.
Așa că m-am mutat la dreapta, așa că, dacă dreapta = 1,
si cred ca tu, de asemenea, doriți să faceți -
în cazul în care vă mutați la stânga, pe care doriți să setați dreptul egal cu 0.
Sau altceva dacă vă mutați vreodată la dreapta.
Deci, dreapta = 0. În cazul în care dreapta = 1,
acum vrem să newnode mamă indicatorul dreapta,
altceva vrem sa facem newnode mamă indicatorul la stânga.
Întrebări cu privire la asta?
Bine. Deci, acesta este modul în care noi - ei bine, de fapt, în loc de a face acest lucru,
am așteptat o jumătate să utilizați build_node.
Și apoi, dacă este egal cu newnode nulă, return false.
Asta e asta. Acum, aceasta este ceea ce ne-am așteptat să faci.
>> Aceasta este ceea ce soluțiile de personal fac.
Nu sunt de acord cu acest lucru ca "dreptul" de a merge cu privire la aceasta
dar acest lucru este perfect în regulă și va funcționa.
Un lucru care e un pic ciudat acum este
în cazul în care arborele începe nul, vom trece într-un copac nul.
Cred că depinde de modul în care definesc comportamentul trece într-un copac nul.
Mi-ar crede că dacă treci într-un copac nul,
apoi introducerea valoare într-un copac nul
ar trebui să se întoarcă la doar un copac în cazul în care valoarea este ca singur nod.
Oamenii sunt de acord cu asta? Ai putea, dacă ai vrut,
daca treci într-un copac nul
și doriți să inserați o valoare în ea, intoarce false.
E de până la tine pentru a defini asta.
Pentru a face primul lucru pe care I-am spus și apoi -
bine, ai de gând să faci asta avea probleme, deoarece
ar fi mai ușor dacă am avea un pointer la nivel mondial la lucru,
dar noi nu, deci, dacă copac este nul, nu e nimic ce putem face despre asta.
Ne putem întoarce pur și simplu false.
Așa că am de gând să schimbe inserați.
Am punct de vedere tehnic ar putea schimba asta chiar aici,
cum se iterarea peste lucruri,
dar am de gând să schimbe inserați pentru a lua un nod ** copac.
Pointeri duble.
Ce înseamnă?
În loc de a face cu pointeri la noduri,
lucru pe care am de gând să fie manipularea este acest indicator.
Am de gând să fie manipularea acestui indicator.
Am de gând să fie manipularea pointeri direct.
Acest lucru are sens, deoarece, gândiți-vă -
Ei bine, acum aceste puncte la zero.
Ceea ce vreau să fac este să manipuleze acest pointer la punctul de a nu null.
Vreau să subliniez la nodul noua mea.
Dacă aș ține doar evidența pointeri la pointeri mele,
atunci nu am nevoie pentru a urmări un pointer-mamă.
Eu pot păstra doar piesa pentru a vedea dacă indicatorul este orientată la nul,
și dacă indicatorul este orientată la nul,
schimba-l la punctul de a nodului vreau.
Și eu pot schimba, deoarece am un pointer la pointer.
Să vedem acum acest drept.
Puteți face de fapt recursiv destul de ușor.
Nu vrem să facem asta?
Da, avem.
>> Să-l vedem recursiv.
În primul rând, ceea ce este cazul nostru de bază va fi?
Aproape întotdeauna cazul nostru de bază, dar, de fapt, acest lucru este un fel de complicat.
Primul lucru, în cazul în care (arbore == NULL)
Cred că suntem doar de gând să se întoarcă fals.
Acest lucru este diferit de zero copac fiind.
Acesta este indicatorul la indicatorul rădăcină fiind nulă
ceea ce înseamnă că indicatorul de root nu exista.
Deci aici, dacă fac
* nod - să reutilizeze asta.
Nod * root = NULL,
si apoi am de gând să sun introduce de a face ceva de genul,
introduceți 4 în & rădăcină.
Deci & rădăcină, în cazul în care rădăcina este un nod *
atunci si radacina va fi un nod **.
Acest lucru este valabil. În acest caz, copac, aici,
copac nu este nulă - sau inserați.
Aici. Arborele nu este nulă; copac * este nul, ceea ce este bine
pentru că dacă copac * este nul, atunci pot să-l manipula
pentru a indica acum la ceea ce vreau să subliniez.
Dar dacă copac este nulă, înseamnă că am venit aici și a spus nul.
Asta nu are nici un sens. Eu nu pot face nimic cu asta.
Dacă arborele este nul, return false.
Așa că am spus deja, practic ceea ce cazul nostru de bază reală este.
Și ce este că va fi?
[Student, neinteligibil]
[Bowden] Da. Deci, în cazul în care (* arbore == NULL).
Acest lucru se referă la cazul aici
în cazul în care în cazul în care indicatorul meu rosu este indicatorul eu axat pe,
asa ca am concentrat pe acest indicator, acum am concentrat pe acest indicator.
Acum, eu sunt concentrat pe acest indicator.
Deci, dacă indicatorul meu rosu, care este nod ** mele,
este tot - în cazul în care *, indicatorul meu rosu, este mereu nul,
asta înseamnă că eu sunt la cazul în care mă concentrându-se pe un pointer care puncte -
aceasta este un pointer care aparține o frunză.
Vreau să schimbe acest indicator pentru a indica nodul noua mea.
Vino înapoi aici.
Newnode mea va fi doar nod * n = build_node (valoare)
apoi n, dacă n = NULL, întoarce false.
Altceva vrem sa schimbam ceea ce indicatorul este în prezent indică spre
pentru a indica acum la nodul nostru recent construit.
Putem face asta de fapt aici.
În loc de a spune n, spunem * = copac, dacă copac *.
Toată lumea înțelege că? Că prin a face cu pointeri la pointeri,
putem schimba pointeri nule pentru a indica lucruri pe care doriți să le indice.
Asta e cazul nostru de bază.
>> Acum ne recurență, sau recursivitate nostru,
va fi foarte similar cu toate celelalte recursions am făcut.
Am de gând să doriți să inserați o valoare,
și acum am de gând să folosească ternare din nou, dar ceea ce este condiția noastră va fi?
Ce este aceasta suntem în căutarea pentru a decide dacă vrem să mergem la stânga sau la dreapta?
Hai să o facem în etape separate.
În cazul în care (valoare <) ce?
[Student] valoarea de copac?
[Bowden] Deci, amintiți-vă că eu sunt în prezent -
[Elevii, neinteligibile]
[Bowden] Da, asa de bine aici, să spunem că această săgeată verde
este un exemplu de ceea ce copac este, în prezent, este un pointer la acest indicator.
Asta înseamnă că eu sunt un pointer la un pointer la 3.
Dereference de două ori suna bine.
Ce am - cum fac asta?
[Student] dereference o dată, și apoi face săgeata în acest fel?
[Bowden] Deci (arbore *) este dereference o dată, -> valoarea
este de gând să-mi dea valoarea nodului pe care am indirect arătând spre.
Deci, eu pot scrie, de asemenea, l ** tree.value, dacă preferați asta.
Fie funcționează.
În cazul în care este cazul, atunci vreau să sun insera cu valoare.
Și ceea ce este nodul meu completa ** va fi?
Vreau să merg la stânga, astfel încât tree.left ** va fi stânga mea.
Și vreau să indicatorul chestia aia
astfel că, dacă stânga se termină prin a fi pointer nul,
Pot să-l modifica pentru a indica nodul noua mea.
>> Și alt caz poate fi foarte asemănătoare.
Să facem de fapt, că ternar mea chiar acum.
Introduceți valoarea dacă valoarea <(** copac). Valoare.
Apoi ne-am dori pentru a actualiza ** noastre la stânga,
altceva vrem să actualizați ** noastre la dreapta.
[Student] se obține că indicatorul la indicatorul?
[Bowden] Amintiți-vă că - ** tree.right este o stea nod.
[Student, neinteligibil] >> Da.
** Tree.right este ca acest indicator sau ceva de genul.
Deci, prin luarea un pointer la asta, dă-mi ceea ce vreau
de pointer la tipul ăla.
[Student] Putem trece peste din nou de ce suntem folosind doi pointeri?
[Bowden] Da. Deci - nu, poți, și că soluția înainte de
a fost o modalitate de a face aceasta fără a face doi pointeri.
Ai nevoie să fie în măsură să înțeleagă folosind doi pointeri,
și aceasta este o soluție mai curat.
De asemenea, observați că, în ceea ce se întâmplă în cazul în care copacul meu -
ce se întâmplă dacă rădăcina mea a fost nulă? Ce se întâmplă dacă fac acest caz aici?
Deci, nod * root = NULL, introduceți 4 în & rădăcină.
Ce se rădăcină va fi după asta?
[Student, neinteligibil] >> Da.
Valoarea rădăcină va fi 4.
Stânga rădăcină va fi nulă, dreptul de rădăcină va fi nul.
În cazul în care nu am trecut prin adresa rădăcină,
nu am putut modifica rădăcină.
În cazul în care copacul - în cazul în care rădăcina a fost nul,
tocmai am avut să se întoarcă false. Nu e nimic de făcut.
Noi nu putem introduce un nod într-un arbore gol.
Dar acum putem, vom face doar un copac gol într-un copac de un nod.
Care este, de obicei, modul preconizat, care ar trebui sa lucreze.
>> În plus, acest lucru este semnificativ mai mică decât
asemenea ține cont de mamă, și așa voi repeta în jos tot drumul.
Acum am părinților mei, și am doar indicatorul dreptul meu părinte la orice.
În schimb, dacă am făcut asta iterativ, ar fi aceeași idee, cu o buclă în timp ce.
Dar, în loc de a avea de a face cu indicatorul părinților mei,
în schimb indicatorul mea actuală ar fi lucrul
că eu sunt direct modificarea pentru a indica nodul noua mea.
Eu nu am de a face cu dacă este îndreptat spre stânga.
Eu nu am de a face cu dacă este îndreptat spre dreapta.
E doar ce acest indicator este, am de gând să-l setați pentru a indica nodul noua mea.
Toată lumea înțelege cum funcționează?
Dacă nu de ce vrem să facem în felul acesta,
dar cel puțin că aceasta funcționează ca o soluție?
[Student] În cazul în care nu ne întoarcem adevărat?
[Bowden] Asta e, probabil, chiar aici.
Dacă am introduce în mod corect că, return true.
Altfel, aici jos vom dori să se întoarcă indiferent de inserare se întoarce.
>> Si ceea ce este special la această funcție recursivă?
E coada recursiv, atâta timp cât vom compila cu unele de optimizare,
se va recunoaște faptul că și niciodată nu se va obține o depășire stivă de acest lucru,
chiar dacă arborele nostru are o înălțime de 10.000 sau 10 milioane de euro.
[Student, neinteligibil]
[Bowden] Cred că o face la Dash - sau ce nivel de optimizare
este necesar pentru o recursivitate coadă să fie recunoscut.
Cred că recunoaște - CCG și zăngănit
au, de asemenea, înțelesuri diferite pentru niveluri de optimizare lor.
Vreau să spun că e DashO 2, sigur că acesta va recunoaște recursivitate coadă.
Dar noi - ai putea construi ca un exemplu Fibonocci sau ceva.
Nu e ușor pentru a testa cu acest lucru, pentru că este dificil de a construi
un arbore binar care este atât de mare.
Dar da, cred că e DashO 2, care
dacă doriți să compilați cu DashO 2, acesta va căuta recursivitate coadă
și a optimiza asta.
Să mergem înapoi la - insera e literalmente ultimul lucru de care are nevoie.
Să ne întoarcem la inserați aici
în cazul în care vom face aceeași idee.
Va avea în continuare defect de a nu fi capabil să se ocupe în întregime
atunci când rădăcina în sine este nulă, sau intrarea trecut este nulă,
dar în loc de a face cu un pointer-mamă,
să se aplice aceeași logică de pointeri păstrare la pointeri.
Dacă ținem aici nod nostru ** actuală,
si nu avem nevoie pentru a urmări mai corect,
dar nod ** actuală = & copac.
Și acum, în timp ce bucla nostru este de gând să fie în același timp actuală * nu nul egal.
Nu am nevoie pentru a ține evidența părinți mai.
Nu trebuie să țină evidența la stânga și la dreapta.
Și eu voi numi temperatură, pentru că suntem deja utilizați temp.
Bine. Deci, dacă (valoarea> * temp),
atunci & (* temp) -> dreapta
altceva temp = & (* temp) -> plecat.
Și acum, în acest moment, după această buclă în timp ce,
Am face acest lucru doar pentru că poate e mai ușor să ne gândim decât iterativ recursiv,
dar după această buclă în timp ce,
* Temperatura este indicatorul vrem să se schimbe.
>> Înainte de a avea mamă, și am vrut să schimbe, fie la stânga mamă sau mamă dreapta,
dar dacă vrem să schimbăm dreapta-mamă,
atunci temperatura * are dreptate părinte, și ne poate schimba în mod direct.
Deci aici, putem face * temp = newnode, și asta e tot.
Deci notificare, tot ce am făcut în acest lucru a fost scoate de linii de cod.
În scopul de a ține evidența mamă în tot ceea ce este un efort suplimentar.
Aici, dacă păstrăm doar evidenta pointer la pointer,
și chiar dacă am vrut să scape de toate aceste acolade acum,
face să arate mai scurt.
Acest lucru este acum solutia exact aceeași,
dar mai putine linii de cod.
Odată ce ați începe să recunoască acest lucru ca pe o soluție viabilă,
este, de asemenea, mai ușor de motiv, decât ca despre, bine,
de ce nu am acest indicator la dreapta int?
Ce înseamnă asta? Oh, e semnificând faptul că
de fiecare dată când mă duc dreptate, am nevoie să-l setați,
altceva dacă mă duc plecat am nevoie pentru a seta la zero.
Aici, nu am un motiv sa cu privire la faptul că, e doar mai ușor să se gândească.
Întrebări?
[Student, neinteligibil] >> Da.
Ok, deci în ultimul bit -
Cred că o funcție ușor și rapid, ce putem face este,
hai - împreună, cred, încercați și de a scrie o funcție conține
care nu-i pasă dacă este un arbore binar de căutare.
Această funcție ar trebui să se întoarcă conține adevărat
în cazul în care nicăieri în acest arbore binar generală este valoarea pe care o căutăm.
Deci, hai sa o facem prima recursiv si apoi vom face iterativ.
Putem de fapt, nu doar împreună, deoarece aceasta va fi foarte scurt.
>> Ceea ce este cazul meu de bază va fi?
[Student, neinteligibil]
[Bowden] Deci, dacă (arbore == NULL), atunci ce?
[Student] întoarce FALSE.
[Bowden] Altele, ei bine, nu am nevoie de altceva.
Dacă a fost cazul meu de bază altele.
[Student] Arborele lui valoare? Da >>.
Deci, în cazul în care (arbore-> valoare == valoare.
Observați ne-am întors la * nodul nu, nod ** e?
Conține nu va trebui să utilizați un nod **,
din moment ce nu se modifica pointeri.
Noi doar le traversează.
În cazul în care acest lucru se întâmplă, atunci vrem să se întoarcă adevărat.
Altceva vrem să traverseze copiilor.
Deci, nu putem gândi cu privire la posibilitatea ca totul sa stanga este mai puțin
și totul a dreapta este mai mare.
Deci, ceea ce se condiția noastră va fi aici - sau, ce vom face?
[Student, neinteligibil] >> Da.
Rentabilitatea conține (valoare, arbore-> stânga)
sau conține (valoare, copac-> dreapta). Și asta e tot.
Și observați există unele evaluare scurt-circuit,
în cazul în care, dacă se întâmplă să aflăm valoarea din copac stânga,
Noi nu trebuie să se uite la copac dreapta.
Asta e funcția intreaga.
Acum, hai să o facem iterativ,
care va fi mai puțin frumos.
Vom lua startul de obicei de nod * actuală = copac.
În timp ce (actuală = NULL!).
Rapid de gând să văd o problemă.
Dacă actuală - aici, dacă ne rupe vreodată de acest lucru,
apoi ne-am alerga afară de lucruri să se uite la, întoarce așa fals.
În cazul în care (actuală-> valoare == valoare), return true.
Deci, acum, suntem la un loc -
nu știm dacă vrem să mergem la stânga sau la dreapta.
Deci arbitrar, să mergem tocmai a plecat.
Am rula în mod evident, o problemă în cazul în care le-am abandonat complet totul -
Voi verifica doar vreodată partea stângă de un copac.
Eu nu va verifica ceva care este un copil dreptul de nimic.
Cum pot remedia acest lucru?
[Student] Trebuie să țină evidența stânga și dreapta într-o stivă.
[Bowden] Da. Așa că hai să-l
struct lista, nodul N *, iar apoi nod ** viitoare?
Cred că merge bine.
Vrem să mergem pe stanga, sau hai - aici.
Struct = jos lista, va începe
, în această listă struct.
* Lista = NULL. Așa că va fi lista noastră de legat
de subarbori pe care le-am sarit peste.
Vom traversa stânga acum,
dar din moment ce inevitabil trebuie să se întoarcă la dreapta,
Mergem să păstreze partea dreaptă în interiorul listei noastre struct.
Apoi vom avea new_list sau struct,
struct lista *, new_list = malloc (sizeof (lista)).
Am de gând să ignore erori verificarea asta, dar ar trebui să verificați pentru a vedea dacă e nul.
New_list nodul se va indica -
oh, de aceea l-am vrut aici. O să indice o listă struct secunde.
Asta e doar modul în care locul de muncă legate de preturi.
Acest lucru este la fel ca o listă legată int
cu excepția suntem doar inlocuirea int cu * nod.
Este exact la fel.
Deci new_list, valoarea nodului new_list noastre,
va fi actuală-> dreapta.
Valoarea noastre new_list-> lângă va fi lista noastră inițială,
și apoi vom actualiza lista noastră pentru a indica new_list.
>> Acum avem nevoie de un fel de fel de lucruri de tragere,
ca și cum ne-am străbătut întregul subarbore stânga.
Acum, avem nevoie pentru a scoate lucrurile din ea,
ca actuală este nulă, noi nu vrem să se întoarcă doar false.
Dorim să trageți acum în afara de la lista noastră de nou.
Un mod convenabil de a face acest lucru - ei bine, de fapt, nu e mai multe moduri de a face acest lucru.
Oricine are o sugestie?
În cazul în care ar trebui să fac asta sau cum ar trebui să fac asta?
Avem doar câteva minute, dar orice sugestii?
În loc de - un fel, în loc de starea noastră fiind în timp ce,
ceea ce ne caută în prezent nu este nulă,
în schimb vom continua să meargă până la lista noastră de sine este nulă.
Deci, în cazul în care lista noastră se termină prin a fi nulă,
apoi ne-am alerga afară de lucruri pentru a căuta, de a căuta peste.
Dar asta înseamnă că primul lucru in lista noastra este doar de gând să fie primul nod.
Primul lucru va fi - nu mai avem nevoie pentru a vedea asta.
Deci lista-> n va fi copacul nostru.
lista-> lângă va fi nul.
Și acum în timp ce lista nu nul egal.
Actuală este de gând să trage ceva din lista noastră.
Deci actuală este de gând să egal lista-> n.
Și apoi lista este de gând să egal lista-> n, sau lista-> urmator.
Deci, în cazul în care valoarea actuală este egală cu valoarea.
Acum putem adăuga ambele noastre indicatorul dreapta și stânga noastră indicatorul
atâta timp cât acestea nu sunt nule.
Aici, cred că ar trebui să fi făcut ca, în primul rând.
În cazul în care (actuală-> dreapta = NULL!)
atunci vom insera acel nod în lista noastră.
În cazul în care (actuală-> stânga), aceasta este un pic de muncă suplimentară, dar e în regulă.
În cazul în care (actuală-> stînga = NULL!),
și vom introduce în lista noastră de stânga legat,
și că ar trebui să fie.
Noi itera - atâta timp cât avem ceva în lista noastră,
avem un alt nod să se uite la.
Deci ne uităm la acel nod,
am avansa lista noastră de la următoarea.
În cazul în care nodul este valoarea pe care o căutăm, ne putem întoarce adevărat.
Introduce altceva ambele subarbori noastre stânga și la dreapta,
atâta timp cât acestea nu sunt nule, în lista noastră
astfel încât să putem merge în mod inevitabil asupra lor.
Deci, dacă acestea nu au fost nule,
în cazul în care indicatorul nostru de rădăcină a indicat două lucruri,
apoi la prima am scos ceva atât de lista noastră de sfârșește prin a fi nulă.
Și apoi am pus două lucruri înapoi în, așa că acum lista noastră este de dimensiuni 2.
Apoi mergem la bucla înapoi și suntem doar de gând să trageți,
să zicem, indicatorul stângă a nodului radacina noastra.
Și că voi păstra doar se întâmplă, vom ajunge looping peste tot.
>> Observați că aceasta a fost semnificativ mai complicat
în soluția recursivă.
Și am spus de mai multe ori
că soluția recursivă, de obicei, are multe în comun cu iterativ soluție.
Aici acest lucru este exact ceea ce soluția este de a face recursiv.
Singura schimbare este că în loc de a folosi implicit stiva, stivă programul,
ca felul tău de a ține evidența a ceea ce nodurile pe care încă mai trebuie să viziteze,
acum va trebui să utilizați în mod explicit o listă legat.
În ambele cazuri, se ține evidența a ceea ce nod trebuie încă să fie vizitate.
În cazul recursiv e doar mai ușor, deoarece o stivă
este pus în aplicare pentru tine, ca stiva programului.
Observați că această listă legată, aceasta este o stivă.
Orice am doar pus pe stivă
este imediat ceea ce am de gând să scoate teancul pentru a vizita următoare.
Nu mai avem timp, dar orice întrebări?
[Student, neinteligibil]
[Bowden] Da. Deci, dacă avem lista noastră de legat,
curentă este de gând să indice tipul ăsta,
iar acum suntem avanseaza doar lista noastră de legat să se concentreze pe tipul ăsta.
Ne traversează peste lista legat în acea linie.
Și atunci cred că ar trebui să ne eliberăm lista noastră de legat și chestii
o dată înainte de a reveni adevărate sau false, trebuie să ne
itera peste lista noastră de legătură și mereu aici, cred,
dacă actuală dreptul de a nu este egal cu, se adaugă, așa că acum vrem să eliberăm
actuală pentru că, ei bine, am uitat complet despre lista? Da.
Deci, asta e ceea ce vrem să facem aici.
Unde e indicatorul?
Actuală a fost atunci - vrem să o listă struct * 10 este egal cu lista următoare.
Lista gratuită, lista = temp.
Și, în cazul în care ne vom întoarce adevărat, avem nevoie de a repeta
peste restul listei noastre legate eliberarea lucruri.
Cel mai frumos lucru despre soluția recursivă este eliberarea lucruri
înseamnă doar factorings popping off stiva, care se va întâmpla pentru tine.
Deci, am trecut de la ceva care e ca 3 linii de hard-la-think-despre codul
pentru ceva care este semnificativ mai multe greu-de-cred-despre linii de cod.
Orice mai multe întrebări?
Bine. Suntem bine. Pa!
[CS50.TV]