[Powered by Google Translate] [Secțiunea 7] [mai puțin confortabilă] [Nate Hardison] [Universitatea Harvard] [Acest lucru este CS50.] [CS50.TV] 

Bine ați venit la secțiunea 7. Datorită uragan Sandy, în loc de a avea o secțiune normală în această săptămână, facem această plimbare-prin, prin sectiunea de intrebari. Am de gând să fie în urma împreună cu problema Set 6 Caietul de sarcini, și trece prin toate întrebările din O secțiune a secțiunii Întrebări. Dacă există orice intrebari, vă rugăm să postați-le pe CS50 Discuss. 

Bine. Să începem. Chiar acum mă uit la pagina 3 din Caietul de sarcini set de probleme. Vom începe să discutați mai întâi despre arbori binari deoarece cei care au o mulțime de relevanță pentru set de probleme din această săptămână - Arborele Huffman de codificare. Una dintre structurile de date foarte primul am vorbit despre pe CS50 a fost matrice. Amintiți-vă că o matrice este o secvență de elemente - toate de același tip - depozitate chiar lângă altul în memorie. Dacă am o matrice întreg ca pot desena folosind acest stil de cutii de-numere întregi-- Să spunem că am 5 în prima casetă, am 7 în al doilea, atunci am 8, 10, și 20 în caseta de finală. Amintiți-vă lucrurile, cei doi într-adevăr bune despre această matrice sunt că avem această acces constant în timp la orice element particular  în matrice, dacă știm indexul său. De exemplu, dacă vreau să iau al treilea element din matrice - la index 2 cu ajutorul nostru zero-based sistem de indexare - Am literalmente Trebuie doar pentru a face un calcul matematic simplu, hop la această poziție în matrice, scoate 8 care este depozitat acolo, și eu sunt bine să plec. 

Unul dintre lucrurile rele despre această matrice - despre care am vorbit atunci când am discutat de preturi legate de - este că, dacă vreau să inserați un element în această matrice, Am de gând să aibă de a face unele schimbarea în jurul valorii de. De exemplu, aceasta matrice aici este în ordine sortate - sortate în ordine crescătoare - 5, apoi 7, apoi 8, apoi 10, apoi 20 - dar dacă vreau să inserați numărul 9 în această matrice, Am de gând să aibă de a schimba unele dintre elementele pentru a face spațiu. Putem trage asta aici. Am de gând să aibă de a muta 5, 7, și apoi 8; crea o discrepanță în cazul în care pot pune 9, și apoi 10 și 20 pot merge la dreapta 9. Aceasta este un fel de durere, deoarece, în cel mai rău caz - atunci când avem de a insera fie la începutul sau la sfârșitul de matrice, în funcție de modul în care suntem deplasare - s-ar putea sfârși prin a fi nevoie să transfere toate elementele că suntem în prezent, stocarea în matrice. 

Deci, ceea ce a fost în jurul valorii de acest fel? Mod în jurul valorii de acest lucru a fost pentru a merge la metoda lista noastră legat-în cazul în care - în loc de a stoca elementele 5, 7, 8, 10, 20 și tot unul lângă celălalt în memorie - ceea ce am făcut a fost în schimb a le stoca fel de oriunde am vrut să le stocați în aceste noduri listă legat-pe care eu desen aici, un fel de ad-hoc. Și apoi i-am conectate împreună folosind aceste indicii pentru următoarele. Pot avea un pointer de la 5 la 7, un pointer la 7 la 8, un pointer la 8 la 10, și, în sfârșit, un pointer la 10 la 20, și apoi un pointer nul la 20 care indică faptul că nu este nimic stânga. Compromisul pe care le avem aici este că acum, dacă vrem să inserați numărul 9 în lista noastră de sortat, tot ce trebuie să faceți este să creați un nou nod cu 9, cabla-l până la punctul la locul potrivit, și apoi re-fir de la punctul 8 până la 9. Asta e destul de repede, presupunând că știm exact unde vrem să inserați 9. Dar compromis în schimbul pentru acest lucru este că ne-am pierdut acum acces constant în timp pentru orice element special în structura noastră de date. De exemplu, dacă vreau să găsesc al patrulea element în această listă legată, Am de gând să trebuie să înceapă de la începutul listei și de a lucra prin felul meu de numărare nod-de-nod până când am găsit patra. 

În scopul de a obține performanțe mai bune decât acces o listă legată - dar păstrează, de asemenea, câteva dintre beneficiile pe care le-am avut în ceea ce privește introducerea în timp dintr-o listă legată - un arbore binar este de gând să nevoie de a utiliza memoria un pic mai mult. În special, în loc de a avea doar un pointer într-un nod arbore binar - cum ar fi lista de legat-nod nu - vom adăuga un pointer al doilea nod arbore binar. Mai degrabă decât având în doar un pointer la elementul următor, vom avea un pointer la un copil la stânga și la dreapta un copil. 

Să deseneze o imagine pentru a vedea ce că de fapt arata ca. Din nou, am de gând să utilizeze aceste cutii și săgeți. Un nod arbore binar se va începe cu doar o cutie simpla. Se va avea un spațiu pentru valoarea, și apoi, de asemenea, va avea un spatiu pentru copilul stânga și dreapta copilului. Am de gând să-i eticheteze aici. Vom avea copilul din stânga, iar apoi vom avea dreptul copilului. Există multe moduri diferite de a face acest lucru. Uneori, pentru spațiu și confort, Voi trage de fapt ca eu fac aici, pe jos în cazul în care am de gând să aibă o valoare în partea de sus, și apoi copilul dreapta pe dreapta-jos, și copilul stânga pe stânga-jos. Revenind la această diagramă de top, avem valoare la foarte de sus, atunci avem indicatorul din stânga-copil, și apoi avem indicatorul dreapta-copil. 

În problema Specificatii Set, vorbim despre desen un nod care are o valoare de 7, și apoi un pointer la stânga-copil, care este nul, iar un indicator dreapta-copil, care este nul. Putem scrie, fie NULL capital în spațiul pentru atât copilul stânga și dreapta copil, sau putem desena această linie oblică prin fiecare dintre casetele pentru a indica faptul că e nul. Am de gând să fac asta doar pentru ca e mai simplu. Ceea ce vedeti aici sunt două modalități de a diagramelor un foarte simplu nod arbore binar în cazul în care avem valoarea 7 și pointeri nule copilului. 

A doua parte a discuțiilor noastre despre modul în specificații cu liste legate de - Amintiți-vă, am avut doar să stai la element foarte primul dintr-o listă să-și amintească întreaga listă - și, de asemenea, cu un arbore binar, trebuie doar să stai la un pointer la copac în scopul de a menține controlul asupra întregii structuri de date. Acest element special al arborelui este numit nodul rădăcină al arborelui. De exemplu, în cazul în care acest nod una - acest nod care conține valoarea 7 cu indicii nule stânga-dreapta și-copil - au fost valoare numai în copacul nostru, atunci acest lucru ar fi nodul radacina noastra. E începutul copacul nostru. Putem vedea acest mic o mai clar după ce vom începe să adăugați mai multe noduri la copacul nostru. Lasă-mă să trageți o pagină nouă. 

Acum vom desena un copac care are 7 la rădăcină, și 3 interiorul copilului stânga, și 9 în interiorul copilului drept. Din nou, acest lucru este destul de simplu. Avem 7, trage un nod pentru 3, un nod pentru 9, și am de gând să setați indicatorul din stânga-copil de 7 pentru a indica nodul care conține 3, și indicatorul dreapta copil al nodului care conține 7 la nodul care conține 9. Acum, din 3 și 9 nu au copii, vom stabili toate indicii copiilor lor să fie nul. Aici, rădăcina arborelui nostru corespunde nodul care conține numărul 7. Puteți vedea că, dacă tot ce avem este un pointer la acel nod rădăcină, putem merge apoi prin copacul nostru și accesa ambele noduri copil - 3, cât și 9. Nu este nevoie de a menține indicii pentru fiecare nod unic pe copac. Bine. Acum vom adăuga un alt nod la această schemă. Vom adăuga un nod care conține 6, și vom adăuga acest copil ca dreptul de nodul care conține 3. Pentru a face asta, am de gând să șteargă care pointer nul în 3-nodul și-l sarme pana la punctul la nodul care conține 6. Bine. 

În acest moment, să trecem peste un pic de terminologie. Pentru a începe, motivul pentru care aceasta se numește un arbore binar, în special, este faptul că are doi pointeri copil. Există alte tipuri de copaci, care au mai multe indicații copilului. În special, ai făcut-o "încerca" din seria Problema 5. Veți observa că în această încercare, ai avut 27 indicii diferite la diferiți copii - una pentru fiecare din cele 26 de litere din alfabetul englez, și apoi pentru 27 apostrof - astfel, care este similar cu un tip de copac. Dar aici, din moment binar e, avem doar doi pointeri copil. 

În plus față de acest nod rădăcină despre care am vorbit, am fost, de asemenea aruncat în jurul valorii de acest termen "copil". Ce înseamnă pentru un nod să fie un copil de un alt nod? Este literalmente înseamnă că un nod copil este un copil de un alt nod în cazul în care alt nod are una dintre indicii copil sale stabilite pentru a indica faptul că nodul. Pentru a pune acest lucru în termeni mai concreți, dacă 3 este indicat de unul dintre indicii copil de 7, apoi 3 este un copil de 7. Dacă ar fi să ne dăm seama ce copiii de la 7 sunt - ei bine, vom vedea că 7 are un pointer la 3 și un pointer la 9, deci 9 și 3 sunt copii de 7. Nouă nu are copii, deoarece indicii sai copii sunt nule, și 3 are un singur copil, 6. Șase copii nu are, de asemenea, deoarece ambele indicii sai sunt nule, pe care o vom trage chiar acum. 

În plus, vorbim, de asemenea, despre parintii unui nod special, și acest lucru este, după cum te-ai astepta, reversul acestei descrieri copil. Fiecare nod are un singur părinte - în loc de două ca s-ar putea aștepta cu oamenii. De exemplu, mamă a 3 este 7. Mamă a 9 este, de asemenea, 7, și mamă a 6 este 3. Nu de mult la ea. Avem, de asemenea termeni pentru a vorbi despre bunici și nepoți, și, în general, mai vorbim despre strămoși și descendenți ai un anumit nod. Strămoș al unui nod - sau strămoșii, mai degrabă, de un nod - sunt toate nodurile care se află pe calea de la radacina la nodul. De exemplu, dacă mă uit la nodul 6, atunci strămoșii sunt de gând să fie atât 3 și 7. Strămoșii din 9, de exemplu, sunt - dacă mă uit la nodul 9 - apoi strămoș al 9 este la doar 7. Și urmașii sunt exact invers. Dacă vreau să se uite la toate descendenți din 7, atunci am să te uiți la toate nodurile de sub el. Deci, am 3, 9, 6 și toți, ca descendenți ai 7. 

Termenul final, că vom vorbi despre această noțiune este de a fi un frate. Fratii - un fel de urma de-a lungul pe acești termeni de familie - sunt noduri care sunt la același nivel în copac. Deci, 3 și 9 sunt frații, deoarece acestea sunt la același nivel în arbore. Amândoi au același părinte, 7. Cele 6 nu are frați, deoarece 9 nu are nici un copil. Și 7 nu are nici frați, pentru că e rădăcina arborelui nostru, și nu există decât vreodată 1 radacina. Pentru 7 pentru a avea frați ar trebui să fie un nod de mai sus 7. Nu ar trebui să fie un părinte de 7, caz în care 7 nu ar mai fi rădăcina arborelui. Apoi, faptul că noua mamă din 7 ar trebui, de asemenea, să aibă un copil, și acel copil ar fi atunci fratele de 7. 

Bine. Mergem mai departe. Când am început discuția noastră de arbori binari, am vorbit despre modul în care am fost de gând să le folosească pentru a obține un avantaj în ambele tablouri si liste legate. Și modul în care ne vom face acest lucru este cu această proprietate prin care se dispune. Spunem că un arbore binar ordonat se, conform caietului de sarcini, în cazul în care pentru fiecare nod din arbore noastră, toți urmașii săi pe stânga - copilul din stânga și pentru toți urmașii copilului stanga - au valori mai mici, și toate nodurile de pe dreapta - copilului dreptul și pentru toți urmașii copilului dreptul de - au noduri mai mari decât valoarea nodului curent care ne uitam la. Doar pentru simplitate, vom presupune că nu există nici o noduri duplicate din copacul nostru. De exemplu, în acest copac nu am de gând să se ocupe de caz în cazul în care avem valoarea 7 la rădăcină  și apoi avem, de asemenea, valoarea 7 în altă parte în copac. În acest caz, veți observa că acest copac este într-adevăr comandat. Avem 7 la valoarea rădăcină. Totul la stânga din 7 - dacă am anula toate aceste mărci mici aici - totul la stânga de 7 - 3 și 6 - aceste valori sunt atât mai puțin de 7, și totul la dreapta - care este doar asta 9 - este mai mare decât 7. 

Acest lucru nu este singurul copac care conțin comandat aceste valori, dar hai sa mai trage o câteva dintre ele. Acolo este de fapt o grămadă de moduri în care putem face acest lucru. Am de gând să utilizeze o prescurtare doar pentru a menține lucrurile simple în cazul în care - mai degrabă decât să se inspire din întreaga Cutii-si-săgeți - Sunt doar de gând să tragă numerele și adăugați-le săgeți de legătură. Pentru a începe, vom scrie doar copacul nostru original, din nou, în cazul în care am avut 7, iar apoi un 3, și apoi înapoi la 3 subliniat dreptul la 6, și 7 au avut un copil care a fost drept 9. Bine. Ce e un alt mod pe care am putea scrie acest copac? În loc de a avea 3 să fie copilul din stânga din 7, am putea avea, de asemenea, să fie 6 copil de 7 stânga, și apoi 3 să fie copilul stânga 6. Asta ar arata ca acest copac chiar aici, unde am luat 7, apoi 6, apoi 3, și un 9 pe dreapta. De asemenea, nu trebuie să aibă ca nodul 7 radacina noastra. Am putea avea, de asemenea, ca nod de 6 radacina noastra. Ce-ar fi ca arata? Dacă vom menține această proprietate ordonate, totul la stânga de 6 trebuie să fie mai mică de ea. Există doar o singură posibilitate, și asta e 3. Dar, apoi ca copilul dreptul de 6, avem două posibilități. În primul rând, am putea avea 7 și apoi 9, sau am putea trage - ca sunt pe cale să fac aici - în cazul în care avem 9, copilul drept al 6, si apoi 7 ca copilul din stânga a 9. 

Acum, 7 și 6 nu sunt valorile posibile numai pentru rădăcină. Am putea avea, de asemenea, 3 fie la rădăcină. Ce se întâmplă dacă 3 este la radacina? Aici, lucrurile devin un pic interesant. Trei nu are nici o valoare, care sunt mai puțin decât, astfel încât partea stângă a întregul copac este doar de gând să fie nul. Nu va fi nimic acolo. Pentru a dreptul, am putea enumera lucrurile în ordine crescătoare. Am putea avea 3, apoi 6, apoi 7, apoi 9. Sau, am putea face 3, apoi 6, apoi 9, apoi 7. Sau, am putea face 3, apoi 7, apoi 6, apoi 9. Sau, 3, 7 - de fapt, nu, nu putem face un 7 mai. Asta e un lucru noastră acolo. Putem face 9, și apoi de la 9 putem face 6 și apoi 7. Sau, putem face 3, apoi 9, apoi 7, apoi 6. 

Un lucru să vă atrag atenția aici este că acești copaci sunt un pic ciudat. În special, dacă ne uităm la cele 4 copacii de pe partea dreapta - Le voi inconjura, aici - acești copaci arata aproape exact ca o listă legată. Fiecare nod are un singur copil, și astfel nu avem nici de această structură arborescentă pe care le vedea, de exemplu,  în acest copac singuratic o aici pe stânga jos. Acești copaci sunt de fapt numite degenera arbori binari, și vom vorbi despre acestea mai mult în viitor - mai ales dacă te duci să le ia alte cursuri de informatică. Acesti copaci sunt degenerate. Ele nu sunt foarte folositoare, deoarece, într-adevăr, această structură se pretează  pentru căutare de ori similare cu cele dintr-o listă legată. Noi nu ajung să profite de memorie suplimentar - acest indicator suplimentar - din cauza structurii noastre a fi rău în acest fel. Mai degrabă decât merge pe și de scoate copacii binare, care au 9 la rădăcină, care este ultimul caz pe care le-ar avea, suntem în schimb, în ​​acest moment, o să vorbesc un pic despre acest alt termen pe care le folosim atunci când vorbim despre copaci, care se numește înălțime. 

Înălțimea unui copac este distanta de la radacina la nodul cel mai îndepărtat, sau mai degrabă numărul de hamei, care va trebui să facă, în scopul de a începe de la rădăcină și apoi ajunge la nodul cel mai îndepărtat în copac. Dacă ne uităm la unele dintre aceste copaci pe care le-am elaborat chiar aici, putem vedea că, dacă luăm acest copac, în colțul din stânga sus și vom începe de la 3, atunci avem de a face 1 hamei pentru a ajunge la 6, un hop secunde pentru a ajunge la 7, și un hop treia pentru a ajunge la 9. Deci, înălțimea acestui arbore este de 3. Putem face acelasi exercitiu pentru alți arbori prezentate cu acest verde, și vedem că înălțimea de toate aceste copaci este, de asemenea, într-adevăr 3. Asta e parte din ceea ce le face degenerate - că înălțimea lor este doar unul mai puțin decât numărul de noduri din arbore întreg. Dacă ne uităm la acest copac de altă natură care e înconjurat cu roșu, pe de altă parte, vom vedea că nodurile cele mai îndepărtate-frunze sunt 6 și 9 - frunze fiind acele noduri care nu au copii. Deci, în scopul de a obține de la nodul rădăcină fie la 6 sau de 9, avem de a face un hop pentru a ajunge la 7 și apoi un hop secunde pentru a ajunge la 9, și, de asemenea, doar un hop a doua din 7 pentru a ajunge la 6. Deci, înălțimea acestui copac de aici este la numai 2. Puteți merge înapoi și face acest lucru pentru toate celelalte pe care le copaci discutat anterior începând cu 7 și 6, și veți găsi că înălțimea tuturor acestor arbori este de asemenea, 2. 

Motivul pentru care am vorbit despre copaci ordonate binare și de ce sunt cool este că puteți căuta prin ele, în un mod foarte asemănător cu căutarea într-o matrice sortate. Acest lucru este în cazul în care vorbim despre obtinerea acel moment de căutare îmbunătățită peste simplă listă legată. Cu o listă legată - dacă doriți să găsiți un anumit element - esti cel mai bun de gând să facă un fel de căutare liniară în cazul în care începe de la începutul unei liste și unu-hop câte unul - un nod de un nod - prin întreaga listă până când găsiți tot ce căutați. Întrucât, în cazul în care aveți un arbore binar care este stocat în acest format frumos, puteți obține de fapt, mai mult de o căutare binară se întâmplă în cazul în care vă dezbina si cucereste si cauta prin jumatatea corespunzătoare a arborelui la fiecare pas. Să vedem cum funcționează. 

Dacă avem - din nou, merge inapoi la copacul nostru originale - vom începe la 7, avem 3 pe partea stângă, 9 pe dreapta, și sub 3 avem 6. Dacă vrem să caute numărul 6 în acest copac, să începem de la rădăcină. Ne-ar compara valoarea pe care o căutăm, să zicem 6, la valoarea stocate în nodul care ne caută în prezent, 7, constată că, într-adevăr 6 este mai mic de 7, deci am muta la stânga. În cazul în care valoarea de 6 au fost mai mare de 7, ne-am fi mutat în schimb spre dreapta. Din moment ce știm că - din cauza structurii de arbore binar ordonat noastre - toate valorile mai mici de 7 vor fi depozitate la stânga din 7, nu este nevoie de a deranja chiar în căutarea prin partea dreaptă a arborelui. După ce vom trece la stânga și suntem acum la nodul care conține 3, putem face o astfel de comparație din nou aceeași în cazul în care vom compara 3 și 6. Și am găsit că în timp ce 6 - valoarea pe care o căutăm - este mai mare decât 3, putem merge la partea din dreapta a nodului conține 3. Nu e nici partea stanga aici, asa ca am putut ignora faptul că. Dar noi știm că doar pentru că ne uităm la copac în sine, și putem vedea că arborele nu are copii. 

Este, de asemenea, destul de ușor să se uite în sus 6 din acest copac, dacă facem noi înșine ca oameni, dar hai să urmați acest proces mecanic ca un calculator ar face pentru a înțelege cu adevărat algoritm. În acest moment, suntem acum se uită la un nod care conține 6, și noi suntem în căutarea pentru valoarea 6, astfel, într-adevăr, am găsit nodul corespunzător. Am găsit valoarea 6 în copacul nostru, și ne putem opri căutarea noastră. În acest moment, în funcție de ce se întâmplă, putem spune, da, am gasit valoarea 6, acesta există în copacul nostru. Sau, dacă suntem de planificare pentru a insera un nod sau de a face ceva, putem face asta în acest moment. 

Hai sa facem un cuplu mai multe căutări doar pentru a vedea cum funcționează. Să ne uităm la ce se întâmplă dacă ar fi să încercăm și privi în sus valoarea de 10. Dacă ar fi să se uite în sus valoarea 10, vom începe de la rădăcină. Ne-ar vedea că 10 este mai mare decât 7, deci am muta la dreapta. Ne-ar ajunge la 9 și compara 9 la 10 și vedea că 9 este într-adevăr mai puțin de 10. Deci, din nou, ne-ar încerca să se mute în dreapta. Dar, în acest moment, am observat că suntem la un nod nul. Nu e nimic acolo. Nu e nimic în cazul în care ar trebui să fie 10. Acest lucru este în cazul în care ne putem raporta eșec - că nu există într-adevăr, nu 10 în copac. Și, în sfârșit, să mergem prin cazul în care noi încercăm să te uiți în sus 1 din copac. Acest lucru este similar cu ceea ce se întâmplă dacă ne uităm în sus 10, cu excepția în loc de a merge la dreapta, vom merge la stânga. Vom începe de la 7 și vezi că 1 este mai mic de 7, asa ca am muta la stânga. Noi ajungem la 3 și vezi că 1 este mai mic de 3, deci vom încerca din nou, pentru a vă deplasa spre stânga. În acest moment avem un nod nul, deci din nou, ne putem raporta eșec. 

Dacă vreți să aflați mai multe despre copaci binare, există o grămadă de probleme dragute pe care le puteți face cu ele. Eu sugerez practicarea desen din aceste diagrame unu-de-unu și în urma prin toate etapele diferite, deoarece acest lucru va veni în super-îndemână nu numai atunci când faci problema Huffman set de codificare dar, de asemenea, la cursuri viitoare - doar de învățare cum să atragă în aceste structuri de date și că, prin problemele cu pix și hârtie sau, în acest caz, iPad și stylus. 

În acest moment însă, vom trece la a face unele practici de codare și să se joace de fapt, cu aceste copaci binare și a vedea. Mă duc pentru a comuta înapoi peste la calculatorul meu. Pentru această parte a secțiunii, în loc de a folosi CS50 CS50 Run sau Spaces, Am de gând să folosească aparatul. 

În urma împreună cu caietul de sarcini set de probleme, Văd că eu ar trebui să deschidă aparatul, du-te la folderul My Dropbox, creați un folder denumit secțiunea 7, și de a crea apoi un fișier numit binary_tree.c. Aici vom merge. Am aparatul deja deschis. Mă duc trage un terminal. Am de gând să merg la folderul Dropbox, face un director numit section7, si vezi e complet goală. Acum am de gând să deschidă binary_tree.c. Bine. Aici vom merge - fișier gol. 

Să ne întoarcem la caietul de sarcini. Caietul de sarcini solicită să creați o definiție de tip nou pentru un nod arbore binar care conține valori int - la fel ca valorile pe care le-au atras în diagrame noastră înainte. Vom folosi această șabloane typedef pe care le-am făcut chiar aici că ar trebui să recunoască de la Set Problema 5 - dacă ai făcut-o modalitate de a cuceri tabel hash programului abecedar. Tu ar trebui să recunoască, de asemenea, că din punctul de săptămâna trecută în cazul în care am vorbit despre listele legate. Am luat acest typedef struct nod al unui, și ne-am dat acest nod struct acest nume de nod struct în prealabil astfel încât să putem referi apoi la ea, deoarece vom dori să aibă indicii struct nod ca parte dintr-o structura noastră, dar ne-am încercuit atunci acest lucru - sau, mai degrabă, această închise - într-un typedef astfel încât, mai târziu, în cod, ne putem referi la acest struct ca doar un nod in loc de un nod struct. 

Acest lucru va fi foarte similar cu definiția lista individual-linked, care am văzut săptămâna trecută. Pentru a face acest lucru, hai să începem prin a scrie în șabloane. Știm că trebuie să avem o valoare întreagă, asa ca vom pune in valoare int, și apoi în loc de a avea doar un pointer la elementul următor - așa cum am făcut cu individual legate de preturi - vom avea pointeri stânga și dreapta copil. Asta e destul de simplu prea - struct nod * copilul din stânga; și struct nod * copil dreapta;. Mișto. Care arata ca un început destul de bun. Să ne întoarcem la caietul de sarcini. 

Acum, avem nevoie de a declara o variabilă globală * nod pentru rădăcina unui copac. Vom face acest lucru la nivel mondial ca ne-am facut indicatorul prima în lista noastră de legat, de asemenea, la nivel mondial. Acest lucru a fost, astfel încât, în funcțiile pe care le scrie noi nu trebuie să țină de întâlnire în jurul valorii de această rădăcină - deși vom vedea că, dacă doresc să se scrie aceste funcții recursiv, ar fi mai bine să nu treci chiar în jurul valorii de ca un nivel global în primul rând și inițializa în schimb, la nivel local, în funcție de dvs. principal. Dar, vom face la nivel global pentru a începe. Din nou, vom da o pereche de spații, și am de gând să declare o rădăcină * nod. Doar pentru a vă asigura că nu-mi părăsi această neinitializata, am de gând să-l setați egale cu null. Acum, în funcția de principal - pe care o vom scrie foarte repede chiar aici - int main (int argc, char * argv const []) - și am de gând să încep declarând matrice mea argv ca const doar pentru ca stiu că aceste argumente sunt argumente că, probabil, nu doriți să le modificați. Dacă vreau să-i modifice I ar trebui, probabil, face copii ale acestora. Veți vedea acest lucru un lot în cod. E bine oricum. E bine să-l lase ca - omite const, dacă doriți. Am pus-o în mod normal doar pentru ca m-am reamintesc  Probabil că eu nu vreau să modifice aceste argumente. 

Ca întotdeauna, am de gând să includă această return 0 linie la sfârșitul anului principal. Aici, voi inițializa nodul rădăcină meu. Așa cum stau lucrurile acum, am un pointer care este setat la nul, așa că e îndreptat de la nimic. În scopul de a porni efectiv construcția nodului, Prima dată am nevoie pentru a aloca memorie pentru ea. Am de gând să fac asta prin memorie pe heap folosind malloc. Am de gând să se stabilească rădăcină egală cu rezultatul malloc, și am de gând să utilizați operatorul sizeof pentru a calcula dimensiunea unui nod. Motivul pentru care am folosi sizeof nod, spre deosebire de, să zicem, a face ceva de genul asta - malloc (4 + 4 +4) sau malloc 12 - este pentru că vreau să fie codul meu cât mai compatibil. Vreau să fie în măsură să ia acest fișier C., Compilați-l pe aparat, și apoi compila-l pe pagina mea 64-biți Mac - sau pe o arhitectură complet diferită - și vreau toate astea pentru a lucra la fel. 

Dacă am face presupuneri cu privire la dimensiunea de variabile - dimensiunea unui int sau dimensiunea unui pointer - atunci am face, de asemenea, presupuneri cu privire la tipurile de arhitecturi pe care codul meu poate compila cu succes atunci când rulați. Utilizați întotdeauna sizeof, spre deosebire de însumarea manual câmpurile struct. Alt motiv este faptul că ar putea exista, de asemenea, faptul că padding compilatorul pune în struct. Chiar însumând doar câmpurile individuale nu este ceva ce vrei sa faci de obicei, astfel, ștergeți acea linie. Acum, pentru a inițializa cu adevărat acest nod rădăcină, Am de gând să aibă de a conecta valorile pentru fiecare dintre domeniile sale diferite. De exemplu, pentru valoarea știu că vreau să inițializa la 7, si de acum am de gând să setați copilul din stânga pentru a fi nul și copilul dreptul de a fi, de asemenea, nulă. Minunat! Am făcut ca o parte din spec.. 

Caietul de sarcini jos la partea de jos a paginii 3-mi cere mai mult pentru a crea trei noduri - unul conținând 3, unul conținând 6, și unul cu 9 - și sârmă, apoi le așa că arată exact ca diagrama copacul nostru că am vorbit despre anterior. Să facem asta destul de repede aici. Veți vedea foarte repede că am de gând să înceapă să scrie o grămadă de cod duplicat. Am de gând să creeze un nod * și am de gând să-l sun trei. Am de gând să-l setați egale cu malloc (sizeof (nod)). Am de gând să se stabilească trei> valoare = 3. Trei -> left_child = NULL; trei -> dreapta = NULL _child; precum și. Care arată destul de similar cu initializarea rădăcină, și asta e exact ceea ce Am de gând să aibă de a face dacă am începe inițializarea 6 și 9, precum și. Voi face asta foarte repede aici - de fapt, am de gând să fac o copie puțin și pastă, și asigurați-vă că eu - bine.  Acum, eu am copiat-o si eu pot merge mai departe și a stabilit acest egală cu 6. Puteți vedea că aceasta are un timp și nu este super-eficiente. În doar un pic, vom scrie o functie care va face acest lucru pentru noi. Vreau să le înlocuiască cu un 9, să le înlocuiască cu un 6. 

Acum avem toate nodurile noastre, creat si initializat. Avem radacina noastra setat egal cu 7, sau care conțin valoarea 7, nostru nodul care conține 3, nodul noastră conține 6, și nodul noastră conține 9. În acest moment, tot ce trebuie să faceți este totul sârmă în sus. Motivul pentru care am initializat toate indicii la zero este doar ca să mă asigur că Eu nu am nici indicii neinițializate acolo din întâmplare. Și, de asemenea, deoarece, în acest moment, am doar pentru a conecta nodurile de fapt, reciproc - pentru cei care acestea sunt de fapt conectate la - Eu nu trebuie să treacă printr-și face sigur că toate sunt valori nule acolo, în locurile corespunzătoare. 

Începând de la rădăcină, știu că copilul root stânga este 3. Știu că copilul root dreapta este 9. După aceea, singurul copil de altă natură care le-am lăsat să vă faceți griji cu privire la este copilul dreapta 3, care este de 6. În acest moment, totul pare destul de bine. Vom șterge unele dintre aceste linii. Acum totul arata destul de bine. Să ne întoarcem la caietul de sarcini nostru și să vedem ce trebuie să facem următoarea. 

În acest moment, avem de a scrie o funcție numită "conține" cu un prototip de "conține bool (int valoare)". Și aceasta conține funcție este de gând să se întoarcă adevărat  dacă arborele indicat de variabila nostru rădăcină la nivel mondial  conține valoarea trecut în funcția și false în caz contrar. Să mergem mai departe și face asta. Acest lucru va fi exact ca de căutare pe care am făcut-o de mână, pe iPad doar un pic în urmă. Hai înapoi în mări un pic și derulați în sus. Vom pune această funcție chiar deasupra funcție nostru principal astfel încât să nu trebuie să facem nici un fel de prototipuri. Deci, bool conține (int valoare). Acolo mergem. E declarația noastră șabloane. Doar pentru a vă asigura că acest lucru se va compila, Am de gând să merg mai departe și doar egală cu return false. Chiar acum această funcție pur si simplu nu va face nimic și raporta întotdeauna că valoarea pe care o căutăm pentru că nu este în copac. 

În acest moment, este probabil o idee bună - de când am scris o grămadă de cod și nu am încercat chiar testând-o inca - pentru a vă asigura că totul compilează. Există o serie de lucruri pe care trebuie să le faceți pentru a vă asigura că acest lucru se va compila, de fapt. În primul rând, a se vedea dacă am fost folosind orice funcții în orice biblioteci pe care nu le-am încă incluse. Funcțiile le-am folosit până acum sunt malloc, și apoi am fost, de asemenea folosirea acestui tip - acest tip de non-standard numită "bool' - care este inclus în fișierul standard de antet bool. Noi cu siguranta doriți să includeți bool.h standard pentru tipul de bool, iar noi, de asemenea, să includă # lib.h standard pentru bibliotecile standard de care includ malloc, și liber, și toate astea. Deci, zoom out, vom să renunțe. Să încercăm și asigurați-vă că aceasta a făcut, de fapt compilare. Vedem că o face, așa că suntem pe drumul cel bun. 

Să deschidem din nou binary_tree.c. Se compilează. Să mergem în jos și asigurați-vă că introduceți unele apeluri la funcția noastră conține - doar pentru a vă asigura că asta e tot bine și bună. De exemplu, atunci când am făcut niște căutări în copacul nostru mai devreme, am încercat să caute cele 6 valori, 10, și 1, și am știut că era în 6 copac, 10 nu a fost în copac, și 1 nu a fost în nici copac. Să folosească aceste apeluri prin sondaj, ca o modalitate de a da seama dacă este sau nu Funcția noastră conține este de lucru. În scopul de a face acest lucru, am de gând să utilizeze funcția printf, și am de gând să imprima rezultatul apelului de a conține. Am de gând să pună într-un șir "conține (% d) =, deoarece  vom conectați în valoarea pe care am de gând să caute, și =% s \ n ", și de a folosi că, în șir format noastră. Noi doar o să vezi - literalmente imprima pe ecran - ceea ce arata ca un apel de funcție. Acest lucru nu este de fapt apelul funcției.  Acesta este doar un șir conceput sa arate ca un apel de funcție. 

Acum, vom conectați în valorile. Vom încerca contine pe 6, si atunci ce vom face aici este faptul că utilizați operatorul ternar. Să vedem - conține 6 - deci, acum am cuprinse 6 și dacă conține 6 este adevărat, șir pe care am de gând să trimită la caracterul format% s va fi șirul de caractere "adevărată". Să defila peste un pic. În caz contrar, ne dorim pentru a trimite șirul de caractere "false" daca contine 6 întoarce false. Acest lucru este un pic nătărău aspect, dar m-am gândit eu s-ar putea la fel de bine ilustra ceea ce operatorul ternar arata ca, deoarece nu am văzut-o pentru o vreme. Acest lucru va fi un mod frumos, la îndemână pentru a afla dacă funcția noastră conține este de lucru. Mă duc pentru a defila înapoi peste la stânga, și am de gând să copiați și să inserați această linie de câteva ori. Mi-a schimbat unele dintre aceste valori în jurul valorii de, astfel încât aceasta va fi 1, iar acest lucru va fi 10. 

În acest moment avem un frumos funcție conține. Avem unele teste, și vom vedea dacă acest lucru toate lucrările. În acest moment am scris codul de ceva mai mult. E timpul să renunțe afară și asigurați-vă că totul încă compilează. Părăsiți afară, și acum hai să încercăm a face arbore binar din nou. Ei bine, se pare ca avem o eroare, Și avem această declarare în mod explicit funcția de bibliotecă printf. Se pare ca avem nevoie pentru a merge în și includ # standardio.h. Și cu asta, totul ar trebui să compileze. Suntem bine. Acum, haideți să încercați să rulați arbore binar și a vedea ce se întâmplă. Iată-ne, / binary_tree., și vedem că, așa cum ne-am așteptat - pentru că nu ne-am pus în aplicare conține încă, sau, mai degrabă, tocmai am pus în schimbul fals - vom vedea că e doar revenind falsă pentru toate acestea, Deci, asta e tot de lucru pentru cea mai mare parte destul de bine. 

Să ne întoarcem și să pună în aplicare de fapt, conține în acest moment. Mă duc pentru a defila în jos, zoom in, și - Amintiți-vă, algoritmul pe care am folosit a fost că am început de la nodul rădăcină și apoi la fiecare nod pe care le întâlnim, să facem o comparație, și se bazează pe faptul că compararea ne muta, fie la stânga sau la copil copilul dreapta. Acest lucru se întâmplă pentru a arata foarte similar cu cod binar de căutare pe care am scris mai devreme în termen. Când ne-am începe, știm că vrem să stai la nodul curent că ne uităm la, și nodul curent va fi inițializat la nodul rădăcină. Și acum, vom continua prin copac, și amintiți-vă că starea noastră de oprire -  când am lucrat efectiv, prin exemplul de mână - a fost atunci când am întâlnit un nod nul, nu atunci când ne-am uitat la un copil nul, ci mai degrabă atunci când am de fapt, sa mutat într-un nod în arbore si a constatat ca suntem la un nod nul. Vom repeta pana cand actuală nu este egal cu zero. Și ce vom face? Vom testa dacă (actuală -> valoare == valoare), atunci știm că am găsit de fapt, nodul pe care-l căutăm. Deci, aici, ne putem întoarce adevărat. În caz contrar, vrem să vedem dacă este sau nu este o valoare mai mică decât valoarea. Dacă valoarea nodul curent este mai mică decât valoarea căutăm, vom trece la dreapta. Deci, actuală = actuală -> right_child, și în caz contrar, vom deplasa spre stânga. actuală actuală = -> left_child;. Destul de simplu. 

Tu, probabil, recunosc bucla care arată foarte similar cu acest lucru de la binar de căutare mai devreme în termen, cu excepția atunci avem de-a face cu mijlocul anului, mici, și de înaltă. Aici, trebuie doar să se uite la o valoare actuală, asa ca e frumos si simplu. Să asigurați-vă că acest cod este de lucru. În primul rând, asigurați-vă că compilează. Se pare ca o face. Să încercați să rulați-l. Și într-adevăr, acesta imprimă tot ceea ce ne-am asteptat. Se găsește 6 în copac, nu găsiți 10, pentru că 10 nu e în copac, și nu găsiți o, fie pentru că nu e un copac, de asemenea, în. Misto chestii. 

Bine. Să ne întoarcem la caietul de sarcini nostru si sa vedem ce urmează. Acum, ea vrea sa adauge unele noduri mai multe copacul nostru. Acesta dorește să adauge 5, 2, și 8, și asigurați-vă că ne conține cod încă mai funcționează cum era de asteptat. Să mergem să facem asta. În acest moment, mai degrabă decât a face acea copie enervant si paste din nou, să scrie o funcție pentru a crea de fapt un nod. Dacă vom defila în jos tot drumul spre principal, vom vedea că am făcut acest lucru Codul foarte asemănătoare de peste si peste din nou, de fiecare dată când vrem să creați un nod. 

Să scrie o functie care va construi de fapt, un nod pentru noi și îl returnează. Am de gând să-l sun build_node. Am de gând să construiască un nod cu o anumită valoare. Măriți aici. Primul lucru pe care am de gând să faceți este să creați de fapt spațiu pentru nodul pe heap. Deci, nod * n = malloc (sizeof (nod)); n -> valoare = valoare; si apoi aici, mă duc pentru a inițializa toate domeniile pentru a fi valori corespunzătoare. Și la sfârșitul foarte, ne vom întoarce nod nostru. Bine. Un lucru de remarcat este faptul că această funcție chiar aici este de gând să se întoarcă la un pointer de memorie care a fost heap-alocate. Ce e frumos despre acest lucru este faptul că acest nod acum - trebuie să-l declare pe heap, deoarece în cazul în care l-am declarat pe stivă nu am putea să-l facă în această funcție ca asta. Ca memoria ar merge afara domeniului de aplicare și ar fi nulă în cazul în care am încercat să-l accesați mai târziu. Din moment ce se declară heap-alocate de memorie, am de gând să trebuie să aibă grijă de a elibera mai târziu pentru programul nostru să nu se scurgă nici de memorie. Am fost punting pe care pentru orice altceva în codul doar de dragul simplitate, la timp, dar dacă vreodată a scrie o funcție care arata ca acest în cazul în care v-ați luat - unii o numesc malloc sau realloc interior - doriți să vă asigurați că ați pus un fel de comentariu aici care spune, hei, stii, returnează un nod de tip heap-alocat inițializat cu valoarea pass-in. Și apoi doriți să vă asigurați că ați pus într-un fel de act de faptul că spune apelantului trebuie să elibereze memoria întors. În acest fel, dacă cineva vreodată merge și utilizează această funcție, ei știu că tot ce primesc înapoi de la această funcție la un moment dat va trebui să fie eliberat. 

Presupunând că totul este bine și bună aici, putem merge în jos în codul nostru și să înlocuiască toate aceste linii chiar aici cu apeluri la funcția noastră nod build. Să facem asta foarte repede. Pe de o parte că nu vom să înlocuiască această parte este aici jos la partea de jos unde am sârmă de fapt, până la punctul de noduri reciproc, pentru că nu putem face în funcție nostru. Dar, hai sa facem root = build_node (7); nod * = build_node trei (3); nod * = build_node șase (6); nod * = build_node nouă (9);. Și acum, am vrut, de asemenea pentru a adăuga noduri pentru - nod * Cinci = build_node (5); nod * = opt build_node (8); și ceea ce a fost alt nod? Să vedem aici. Ne-am dorit pentru a adăuga, de asemenea, un 2 - nod * doi = build_node (2);. Bine. În acest moment, știm că avem 7, 3, 9, și 6 toate cablat în mod corespunzător, dar ceea ce despre 5, 8, si 2? Pentru a păstra totul în ordine corespunzătoare, știm că dreptul copilului cei trei este de 6. Deci, dacă am de gând să adăugați 5, 5, de asemenea aparține în partea dreaptă a arborelui din care 3 este radacina, astfel 5 aparține ca copilul stânga 6. Putem face acest lucru prin a spune, de sase -> left_child = cinci; și apoi 8 aparține ca copilul stânga 9, astfel încât nouă -> left_child = opt; și apoi 2 este copilul stanga de 3, astfel încât să putem face asta aici - tine -> left_child = două;. Dacă nu ați urmat destul, împreună cu faptul că, îți sugerez să-l scoată singur. 

Bine. Să salvăm asta. Să mergem afară și asigurați-vă că compilează, și apoi putem adăuga în apelurile noastre conține. Se pare că totul încă compilează. Să mergem și să adăugați în unele conține apeluri. Din nou, am de gând să fac un pic de copy si paste. Acum, haideți să caute 5, 8, și 2. Bine. Să ne asigurăm că toate aceste încă arată bine. Minunat! Salvați și ieșiți. Acum, hai să facem, compila, și acum să ruleze. Din rezultatele, se pare ca totul este de lucru doar frumos și bine. Minunat! Deci, acum avem Contains noastre funcționa în scris. Să trecem mai departe și începe să lucreze cu privire la modul de a insera noduri în arbore deoarece, așa cum o facem acum, lucrurile nu sunt foarte drăguță. 

Dacă ne întoarcem la caietul de sarcini, ne cere să scrie o funcție numită insera - din nou, revenind o bool pentru a vedea dacă sunt sau nu am putea introduce, de fapt nod în arbore - și apoi pentru a introduce valoarea în copac este specificat ca singurul argument pentru funcția de inserare nostru. Vom reveni adevărat dacă am putea introduce într-adevăr, valoarea nodul care conține în copac, ceea ce înseamnă că noi, o, avea suficientă memorie, și apoi două, că nodul nu există deja în copac, deoarece - Amintiți-vă, nu vom avea valori duplicat în copac, doar pentru a face lucrurile simple. Bine. Înapoi la codul. Deschide-l. Mări într-un pic, apoi derulați în jos. Să punem funcția de inserare dreptul de deasupra conține. Din nou, aceasta va fi numit inserați bool (int valoare). Dă-i un pic mai mult spatiu, iar apoi, ca implicit, să pună în schimb fals, la sfârșitul foarte. Acum, in partea de jos, hai să mergem mai departe și în loc de a construi manual noduri în principal pe noi înșine și cablajul le până la punctul la altul ca și cum facem, ne vom baza pe funcția Inserare noastră de a face acest lucru. Nu ne vom baza pe funcția Inserare noastră de a construi de la zero tot arborele încă, ci mai degrabă vom scăpa de aceste linii - Vom comenta aceste linii - care construiesc cele 5 noduri, 8, și 2. Și în loc, vom insera apeluri la funcția de inserare nostru pentru a vă asigura că funcționează de fapt. Aici vom merge. 

Acum ne-am comentat aceste linii. Avem doar 7, 3, 9, și 6 în copacul nostru în acest moment. Pentru a vă asigura că acest lucru este tot de lucru, putem micșora, face copacul nostru binar, executați-l, și putem vedea că conține acum ne spune că suntem în totalitate dreptate - 5, 8, și 2 nu mai sunt în copac. Du-te înapoi în cod, și cum vom insera? Amintiți-vă ce am făcut atunci când am fost de fapt introducerea 5, 8, și 2 anterior. Am jucat acest joc Plinko unde am pornit de la rădăcină, coborât un copac de unul câte unul până când am găsit decalajul corespunzător, și apoi am cablat în nodul de la fața locului corespunzătoare. Am de gând să faci același lucru. Aceasta este, practic la fel ca scrierea codul pe care am folosit în funcția conține pentru a găsi locul în care nodul ar trebui să fie, și apoi vom merge doar pentru a insera nodul acolo. Să începem face asta. 

Deci, avem un nod * actuală = radacina; suntem doar de gând să urmeze conține codul până când vom găsi că acesta nu funcționează destul pentru noi. Vom trece prin copac în timp ce elementul curent nu este nulă, și dacă vom descoperi că valoarea actuală este egală cu valoarea pe care noi încercăm să introduceți - Ei bine, aceasta este unul din cazurile în care nu am putut insera de fapt, nodul în copac, deoarece aceasta înseamnă că avem o valoare duplicat. Aici vom fapt de gând să se întoarcă fals. Acum altceva, în cazul în care valoarea actuală este mai mică decât valoarea, Acum știm că vom trece la dreapta  deoarece valoarea aparține în jumătatea dreaptă a arborelui actuală. În caz contrar, vom deplasa spre stânga. Asta e, practic Contains noastre funcționa chiar acolo. 

În acest moment, odată ce ne-am finalizat această buclă în timp ce, indicatorul nostru actuală va fi îndreptată la zero dacă funcția nu și-a revenit deja. Avem, prin urmare, actuală la fața locului în cazul în care dorim să inserați noul nod. Ceea ce rămâne de făcut este de a construi, de fapt nou nod, pe care le putem face destul de ușor. Putem folosi nostru de super-util funcția construi nod, și ceva ce nu am făcut mai devreme - am doar un fel de a pentru totdeauna, ci acum vom face doar să vă asigurați că - vom testa pentru a vă asigura că valoarea returnată de nod nou a fost de fapt Nu null, pentru că nu vrem să înceapă accesarea că memoria în cazul în care este nulă. Putem testa pentru a vă asigura că noul nod nu este egal cu zero. Sau schimb, putem vedea doar în cazul în care de fapt este nul, și în cazul în care este nulă, atunci ne putem întoarce pur și simplu falsă devreme. 

În acest moment, avem de a firului de nod nou în locul său corespunzător în copac. Dacă ne uităm înapoi la principal și în cazul în care am fost, de fapt de cabluri în valori înainte, vom vedea că modul în care ne-au l facem atunci când ne-am dorit să pună 3 în copac a fost accesat am copilul stânga rădăcină. Când ne-am pus 9 în copac, am avut pentru a accesa copilului dreptul de rădăcină. Am avut de a avea un pointer la mamă, în scopul de a pune o valoare nouă în copac. Derulând înapoi pentru a insera, că nu va merge destul de aici pentru că nu avem un pointer-mamă. Ceea ce vrem să fie capabil să facă este, în acest moment, verifica valoarea de mamă și de a se vedea - ei bine, Doamne, dacă valoarea mamă este mai mică decât valoarea curentă, atunci copilul mamă dreapta ar trebui să fie noul nod; în caz contrar, copilul mamă stânga ar trebui să fie noul nod. Dar, noi nu avem acest pointer-mamă destul de încă. 

În scopul de a-l, de fapt, ne va trebui să-l urmărească pe măsură ce trece prin copac și de a găsi locul adecvat în buclă nostru de mai sus. Putem face asta prin derularea înapoi până la partea de sus a funcției inserați noastre și urmărirea altă variabilă pointer numit mamă. Mergem să-l setați egale cu null inițial, și apoi de fiecare dată când trecem prin copac, vom seta indicatorul mamă pentru a se potrivi indicatorul curent. Setați părinte egal cu actuală. În acest fel, de fiecare dată când trecem prin, am de gând să se asigure că, indicatorul actual devine incrementează indicatorul mamă rezultă - doar cu un nivel mai ridicat decât indicatorul actual în copac. Ca toate arata destul de bine. 

Cred ca singurul lucru pe care vom dori să reglați este acest construi nulă nod revin. În scopul de a obține construi nod pentru a reveni cu succes de fapt, null, vom avea de a modifica acest cod, deoarece aici, nu am testat pentru a se asigura că malloc returnat un pointer valid. Deci, în cazul în care (n = NULL!), Apoi - dacă malloc returnat un pointer valid, apoi ne vom initializa; în caz contrar, vom returna doar și care se va încheia la returnarea nul pentru noi. Acum, toate arata destul de bine. Să ne asigurăm că acest fapt compilează. Asigurați-arbore binar, și oh, am luat niște lucruri se întâmplă aici. 

Avem o declarație implicită a funcției construi nod. Din nou, cu aceste compilatoare, vom incepe de la partea de sus. Ceea ce trebuie să spun este că am sunat înainte de a construi nod am de fapt declarate. Să ne întoarcem la codul foarte repede. Derulați în jos, și destul de sigur, funcția mea inserați este declarată de mai sus nodul funcția construi, dar am încercat să folosească construi nod în interiorul fragmentului. Am de gând să merg în copie și - apoi lipiți funcția de a construi calea nod aici la partea de sus. În acest fel, sperăm că va funcționa. Să-i dăm această alt du-te. Acum totul compilează. Totul este bine. 

Dar, în acest moment, nu ne-am chemat de fapt, funcția noastră de inserare. Știm doar că acesta compilează, așa că hai să mergem și să pună niște telefoane inch Să facem asta în funcție nostru principal. Aici, am comentat 5, 8, și 2, și apoi nu le-am sarme pana aici. Să facem niște telefoane pentru a insera, și să utilizeze, de asemenea, același tip de lucruri pe care am folosit atunci când am făcut aceste apeluri printf pentru a vă asigura că totul a se introduce în mod corespunzător. Am de gând să copiați și să lipiți, și în loc de contine vom face inserați. Și în loc de 6, 10, și 1, vom folosi 5, 8, și 2. Acest lucru ar trebui să introducă sperăm 5, 8, și 2 în copac. Compila. Totul este bine. Acum vom rula de fapt, programul nostru. 

Totul a revenit fals. Deci, 5, 8, și 2 nu merge, si se pare ca nu conține i-au găsit, fie. Ce se întâmplă? Să micșora. Prima problemă a fost că inserați părea să se întoarcă false, si se pare ca asta e pentru că am plecat în apel întoarcerea noastră falsă, și nu ne-am întors de fapt adevărat. Noi putem realiza acest lucru. A doua problemă este, acum, chiar dacă o facem - salva acest lucru, iesi acest lucru, rulați din nou face, l-au compila, apoi rulați-l - vom vedea că ceva sa întâmplat aici. 5, 8, și 2 nu au fost niciodată încă găsite în copac. Deci, ce se întâmplă? 

Să aruncăm o privire la acest lucru în cod. Să vedem dacă ne putem da seama asta. Vom începe cu mamă nu este nul. Am stabilit indicatorul curent egal cu indicatorul rădăcină, și am de gând să lucreze drumul nostru în jos, prin copac. Dacă nodul curent nu este nul, atunci știm că ne putem muta în jos un pic. Ne-am stabilit indicatorul noastră mamă să fie egală cu indicatorul curent, verificat valoarea - în cazul în care valorile sunt aceleași ne-am întors fals. Dacă valorile sunt mai puțin ne-am mutat la dreapta; în caz contrar, ne-am mutat la stânga. Apoi, vom construi un nod. Voi mări un pic. Și aici, vom încerca să sarme pana valorile să fie la fel. Ce se întâmplă? Să vedem dacă, eventual, Valgrind ne poate da un indiciu. 

Imi place sa folosesc Valgrind Valgrind doar pentru că într-adevăr rapid rulează și vă spune dacă există erori de memorie. Când vom rula Valgrind pe cod, după cum puteți vedea hit here--Valgrind./binary_tree--and dreapta intra. Veți vedea că nu am avut nici o eroare de memorie, astfel încât se pare că totul e în regulă până acum. Avem niste scurgeri de memorie, pe care le cunosc, pentru că nu suntem se întâmplă pentru a elibera orice noduri noastre. Să încercați să rulați GDB pentru a vedea ce se întâmplă de fapt pe. Vom face gdb / binary_tree.. Acesta cizme sus chiar fin. Să stabilim un punct de întrerupere pe Inserare. Să fugi. Se pare ca n-am sunat, de fapt inserați. Se pare ca problema a fost doar că atunci când m-am schimbat aici în principal - toate aceste apeluri de la printf conține - N-am schimbat, de fapt acestea pentru a apela inserați. Acum, hai să încercăm. Să compilați. Toate arată bine acolo. Acum, haideți să încercați să rulați-l, vezi ce se întâmplă. Bine! Totul arata destul de bine acolo. 

Ultimul lucru care ne gândim este, sunt acolo orice cazuri de margine de la acest insert? Și se dovedește că, ei bine, un caz margine, care este întotdeauna interesant să ne gândim la este, ce se întâmplă dacă arborele este gol și te sun această funcție inserați? Va funcționa? Ei bine, hai să o încerc. - Binary_tree C -. Modul în care ne vom testa acest lucru este, vom merge în jos la functia nostru principal, și, mai degrabă decât de cabluri aceste noduri până în acest fel, suntem doar de gând să comentați lucru întreg, și în loc de cablare pana noduri noi înșine, de fapt, putem merge doar înainte și ștergeți toate astea. Vom face tot ceea ce un apel pentru a insera. Deci, hai sa facem - în loc de 5, 8, și 2, vom introduce 7, 3 și 9. Și apoi vom dori, de asemenea, pentru a insera 6, precum și. Salvare. Quit. Asigurați-arbore binar. Totul compilează. Ne poate rula doar ca este si sa vedem ce se intampla, dar este, de asemenea, va fi foarte important să vă asigurați că nu avem erori de memorie, deoarece aceasta este una dintre cauzele de margine noastre pe care le știu despre. 

Să asigurați-vă că acesta funcționează bine sub Valgrind, pe care o vom face prin rularea doar Valgrind / binary_tree.. Se pare că avem într-adevăr, o eroare de la un context - avem această eroare de segmentare. Ce sa întâmplat? Valgrind de fapt, ne spune unde este. Micșora un pic. Se pare că se întâmplă în funcția de inserare noastră, în cazul în care avem o citire invalid de marimea 4 la inserați, linia 60. Să ne întoarcem și să vedem ce se întâmplă pe aici. Micșora foarte repede. Vreau să vă asigurați că nu merge la marginea ecranului astfel încât să putem vedea totul. Trage că într-o pic. Bine. Derulați în jos, iar problema este chiar aici. Ce se întâmplă dacă am lua în jos și nodul nostru actual este deja nul, nod noastră mamă este nul, deci, dacă ne uităm în sus la foarte de sus, chiar aici - dacă nu această buclă în timp ce, de fapt execută pentru că valoarea noastră actuală este nul - radacina noastra este nulă atât de actuală este nulă - atunci nu se nostru părinte setat la actuală sau la o valoare validă, astfel, părinte va fi, de asemenea, nulă. Avem nevoie să ne amintim pentru a verifica faptul că de când am ajuns aici, și vom începe accesarea valoarea mamă. Deci, ce se întâmplă? Ei bine, în cazul în care părintele este nul - în cazul în care (mamă NULL ==) -, atunci știm că nu trebuie să existe nimic în copac. Trebuie să fi încercat să-l introduceți la rădăcină. Putem face asta doar prin stabilirea rădăcină egală cu nod nou. Apoi, la acest moment, nu vrem de fapt să treacă prin aceste alte lucruri. În schimb, chiar aici, putem face fie o altă-if-else, sau am putea combina totul aici, într-o altcineva, dar aici vom folosi doar altcineva și de a face în felul acesta. Acum, vom testa pentru a vă asigura că părintele nostru nu este nulă înainte de atunci, de fapt încearcă să acceseze domeniile sale. Acest lucru ne va ajuta să evite eroare de segmentare. Deci, am renuntat, zoom out, compila, fugi. 

Nu există erori, dar încă mai avem o grămadă de pierderi de memorie pentru ca nu am nici o elibera de noduri noastre. Dar, dacă mergem aici și ne uităm la imprimare noastră, vom vedea că, ei bine, se pare ca toate insertii noastre au fost returnarea adevărat, ceea ce e bine. Introduce toate sunt adevărate, și apoi apelurile corespunzătoare conține, de asemenea, sunt adevărate. 

Bună treabă! Se pare ca am scris cu succes inserați. Asta e tot ce avem pentru Caietul de sarcini din această săptămână set de probleme. O provocare distractiv să ne gândim este modul în care ar merge de fapt, în și gratuit toate nodurile din acest copac. Putem face acest lucru un număr de moduri diferite, dar voi lăsa că până la tine pentru a experimenta, și ca o provocare distracție, încercați și asigurați-vă că puteți să vă asigurați că acest raport Valgrind returnează nici o eroare si nici scurgeri. 

Mult noroc pe această săptămână Huffman problemă set de codare, și ne vedem săptămâna viitoare! [CS50.TV]