[Powered by Google Translate] [Seksyon 7] [Mas kaunti kumportableng] [Nate Hardison] [Harvard University] [Ito ay CS50.] [CS50.TV] 

Maligayang pagdating sa Seksyon 7. Salamat sa bagyo Sandy, sa halip ng pagkakaroon ng isang normal na seksyon sa linggong ito, ginagawa namin ito lakad-through, sa pamamagitan ng seksyon ng mga tanong. Ako pupunta na sumusunod na kasama ang Problema Itakda 6 Pagtutukoy, at pagpunta sa pamamagitan ng lahat ng mga katanungan sa Isang Seksyon ng mga Tanong seksyon. Kung may anumang mga katanungan, mangyaring mai-post ang mga ito sa CS50 talakayin. 

Tama. Natin makapagsimula. Sa ngayon Naghahanap ako sa pahina 3 ng Pagtutukoy Problema Set. Kami ay pagpunta sa unang simulan ang pakikipag-usap tungkol sa mga binary na puno dahil ang mag iyon ay may maraming ng kaugnayan sa problema sa set na ito linggo - Huffman Tree pag-encode. Isa ng ang unang mga istraktura ng data usapan natin ang tungkol sa CS50 ang array. Tandaan na ang isang array ay isang pagkakasunud-sunod ng mga elemento - lahat ng parehong uri - naka-imbak sa tabi mismo sa bawat isa sa memorya. Kung mayroon akong isang integer array na maaari kong iguhit gamit ang kahon-numero-integer estilo - Ipagpalagay natin na mayroon akong 5 sa unang kahon, mayroon akong 7 sa pangalawang, Mayroon akong 8, 10, at 20 sa huling kahon. Tandaan, ang dalawang talagang magandang bagay tungkol sa array na ito ay na mayroon kaming ito pare-pareho-time na access sa anumang partikular na elemento  sa array na kung alam namin sa index nito. Halimbawa, kung gusto kong i-grab ang ikatlong elemento sa array - sa index 2 gamit ang aming zero-based na sistema ng pag-i-index - Literal ko lang gawin ang isang simpleng pagkalkula ng matematika, Hop na posisyon sa array, hilahin ang 8 na nakaimbak doon, at ako ay handa na upang patakbuhin. 

Isa ng masamang bagay tungkol sa array na ito - na usapan natin ang tungkol kapag tinalakay namin naka-link listahan - ay na kung gusto ko upang ipasok ang isang elemento sa array na ito, Ako pagpunta sa gawin ang ilang mga paglilipat sa paligid. Halimbawa, ito array dito mismo sa pinagsunod-sunod pagkakasunod-sunod - pinagsunod-sunod sa pataas na pagkakasunod-sunod - 5, pagkatapos 7, pagkatapos 8, pagkatapos ay 10, at pagkatapos ay 20 - ngunit kung gusto kong ipasok ang numero 9 sa array na ito, Ako pagpunta sa may upang ilipat ang ilan sa mga elemento upang gumawa ng espasyo. Namin gumuhit ito dito. Ako pagpunta sa may upang ilipat ang 5, 7, at pagkatapos ay ang 8; lumikha ng isang agwat sa kung saan maaari ko bang ilagay ang 9, at pagkatapos ay 10 at sa 20 ay maaaring pumunta sa kanan ng 9. Ito ay uri ng isang sakit dahil sa pinakamasama-case na sitwasyon - kapag kami ay kinakailangang magpasok ng alinman sa simula o sa katapusan ng array, depende sa kung paano namin ang paglilipat - maaari naming upang ilipat ang lahat ng mga elemento na kasalukuyan naming pag-iimbak sa array. 

Kaya, kung ano ang paraan sa paligid nito? Ang paraan sa paligid na ito ay upang pumunta sa aming mga naka-link na listahan ng paraan ng kung saan - sa halip ng pag-iimbak ang mga elemento 5, 7, 8, 10, at 20 lahat ng susunod sa bawat isa sa memorya - kung ano ang aming halip ay ay-imbak ang mga ito uri ng kung saan man gusto namin upang mag-imbak ang mga ito sa mga naka-link na listahan node na ako pagguhit dito, uri ng ad hoc. At pagkatapos namin nakakonekta ang mga iyon nang magkakasama gamit ang mga susunod na mga pointer. Maaari ba akong magkaroon ng isang pointer mula 5 hanggang 7, isang pointer mula sa 7 sa 8, isang pointer mula sa 8 sa 10, at sa wakas, ang isang pointer mula sa 10 sa 20, at pagkatapos ay null pointer sa 20 na nagpapahiwatig na may walang kaliwa. Ang kalakalan-off na mayroon kami dito na ngayon kung gusto namin upang ipasok ang numero ng 9 sa aming listahan ng pinagsunod-sunod, lahat kami ay may sa gawin ay lumikha ng isang bagong node na may 9 na, wire up ang mga ito upang tumuro sa naaangkop na lugar, at pagkatapos ay muling i-wire ang 8 upang ituro down sa 9. Na medyo mabilis, ipagpalagay alam namin eksakto kung saan gusto naming ipasok ang 9. Ngunit ang kalakalan-off sa kapalit para sa ay na namin ngayon ang nawala ang hindi nagbabagong-time na access sa anumang partikular na elemento sa aming mga data ng istraktura. Halimbawa, kung gusto kong makita ang ika-apat na elemento sa naka-link na listahan, Ako pagpunta sa magsimula sa simula ng listahan at gumana ang aking paraan sa pamamagitan ng pagbibilang ng node-by-node hanggang sa mahanap ko ang ika-apat na. 

Upang makakuha ng mas mahusay na access pagganap kaysa sa isang naka-link na listahan - kundi pati na rin panatilihin ang ilang ng mga benepisyo na nagkaroon kami sa mga tuntunin ng pagpapasok ng-oras mula sa isang naka-link na listahan - isang binary tree ay kailangang gamitin ng kaunti pa sa memory. Sa partikular, sa halip ng pagkakaroon ng isang pointer sa isang binary puno node - tulad ng mga naka-link na listahan node ginagawa - kami ay upang magdagdag ng isang pangalawang pointer sa binary puno node. Sa halip na lamang pagkakaroon ng isang pointer sa susunod na elemento, kami ay pagpunta upang magkaroon ng isang pointer sa kaliwa anak at kanang bata. 

Natin gumuhit ng larawan upang makita kung ano ang na aktwal na kamukha. Muli, ako pagpunta sa gamitin ang mga kahon at arrow. Ang isang binary puno node ay magsimula sa isang simpleng kahon. Ito ay upang magkaroon ng espasyo para sa halaga, at pagkatapos din ito upang magkaroon ng espasyo para sa kaliwang bata at ang karapatan ng bata. Ako pagpunta sa label ang mga ito dito. Kami ay pagpunta sa may kaliwang anak, at pagkatapos namin ay pagpunta sa may karapatan bata. Mayroong maraming iba't ibang mga paraan ng paggawa nito. Minsan para sa space at kaginhawahan, Makikita ko aktwal na gumuhit ang mga ito tulad ng ako ginagawa dito sa ibaba kung saan ako pupunta ang halaga sa tuktok, at pagkatapos ay ang karapatan ng bata sa ibabang-kanan, at ang kaliwang bata sa ibabang-kaliwa. Pagpunta pabalik sa tuktok diagram na ito, mayroon namin ang halaga sa pinakatuktok, mayroon kaming kaliwang anak pointer, at pagkatapos ay mayroon kaming i-right-anak pointer. 

Sa Pagtutukoy Problema Set, makipag-usap namin tungkol sa pagguhit ng isang node na may isang halaga 7, at pagkatapos ng kaliwang anak pointer na null, at i-right-anak pointer na null. Maaari naming isulat ang kabisera null sa puwang para sa parehong kaliwang bata at ang karapatan ng bata, o namin maaaring gumuhit ito dayagonal slash sa pamamagitan ng bawat isa sa ang mga kahon upang ipahiwatig na ito ang null. Ako pagpunta upang gawin iyon dahil lamang na simple. Ano ang nakikita mo dito dalawang paraan ng balangkas ng isang napaka-simpleng binary puno node kung saan mayroon kaming ang halaga 7 at null pointer ng bata. 

Ang ikalawang bahagi ng aming mga detalye ng pag-uusap tungkol sa kung paano sa naka-link na listahan - Tandaan, lamang namin ay upang i-hold sa sa unang elemento sa isang listahan tandaan ang buong listahan - at din, na may isang binary puno, lamang namin upang i-hold sa isang pointer sa tree upang mapanatili ang kontrol sa ang buong istraktura ng data. Ito espesyal na elemento ng puno ay tinatawag ang root node ng puno. Halimbawa, kung ang isang node - node na ito na naglalaman ng mga halaga 7 may null kaliwa-at i-right-anak payo - ay ang tanging halaga sa aming puno, pagkatapos na ito ay ang aming na root node. Pinakadulo simula ng aming puno. Maaari naming makita na ito ng kaunti pa malinaw sa sandaling sinimulan namin ang pagdaragdag ng higit pang mga node sa aming puno. Hayaan akong makuha ang isang bagong pahina. 

Ngayon kami ay pagpunta sa gumuhit ng isang puno na may 7 sa root, at 3 sa loob ng kaliwang bata, at 9 sa loob ng tamang anak. Muli, ito ay medyo simple. Mayroon kaming 7, gumuhit ng node para sa 3, isang node para sa 9, at ako pagpunta upang itakda ang kaliwang anak pointer ng 7 upang ituro sa node na naglalaman ng 3, at i-right-anak pointer ng node na naglalaman ng 7 sa node na naglalaman ng 9. Ngayon, dahil 3 at 9 walang anumang mga bata, kami ay pagpunta upang i-set ang lahat ng kanilang mga payo sa anak null. Dito, ang root ng aming mga puno ay tumutugon sa node na naglalaman ng bilang 7. Maaari mong makita na kung ang lahat ng mayroon kami ay isang pointer sa root na node, maaari naming maglakad sa pamamagitan ng aming puno at ma-access ang parehong mga node ng bata - parehong 3 at 9. Hindi na kailangan upang mapanatili ang mga payo sa bawat solong node sa puno. Tama. Ngayon sinusubukan namin upang magdagdag ng isa pang node sa diagram na ito. Kami ay pagpunta sa magdagdag ng node na naglalaman ng 6, at kami ay pagpunta upang idagdag ito bilang ang karapatan na anak ng node na naglalaman ng 3. Upang gawin iyon, ako burahin na null pointer sa 3-node at wire ang mga ito upang tumuro sa node na naglalaman ng 6. Tama. 

Sa puntong ito, sabihin pumunta sa paglipas ng kaunting terminolohiya. Upang magsimula, ang dahilan na ito ay tinatawag na isang binary puno sa partikular na ay na ito ay may dalawang anak payo. May mga iba pang mga uri ng mga puno na may higit pang mga payo anak. Sa partikular, ang isang 'subukan' sa Problema Set 5. Mapapansin mo na sa na Subukan, mayroon kang 27 iba't ibang mga payo sa iba't ibang mga bata - isa para sa bawat isa ng 26 titik sa Ingles alpabeto, at pagkatapos ay ang 27 para sa kudlit - ito, na katulad sa isang uri ng puno. Ngunit dito, dahil ito ay binary, lamang namin ay may dalawang pointer anak. 

Bilang karagdagan sa root node na na usapan natin ang tungkol, din namin ang ibinabato sa buong term na ito 'anak.' Ano ang ibig sabihin para sa isang node sa isang bata ng isa pang node? Ito literal ay nangangahulugan na ang isang bata node ay isang anak ng isa pang node kung na ang ibang node ay may isa ng mga payo ng anak na nakatakda upang tumuro sa node na. Upang ilagay ang sa mas kongkreto mga tuntunin, kung 3 ay tulis sa pamamagitan ng isa ng mga payo sa anak ng 7, pagkatapos 3 ay isang anak ng 7. Kung kami ay upang malaman kung ano ang mga bata ng 7 - mahusay, namin makita na 7 ay may pointer sa 3 at isang pointer sa 9, kaya 9 at 3 ay ang mga anak ng 7. Siyam ay walang mga bata dahil ang mga payo sa anak ay null, at 3 ay lamang ng isang bata, 6. Anim din ay walang mga bata dahil ang parehong ng kanyang mga payo ay null, na makikita namin gumuhit ngayon. 

Bukod pa rito, hindi namin ring makipag-usap tungkol sa mga magulang ng isang partikular na node, at ito ay, bilang gusto mong asahan, ang reverse ng paglalarawan na ito ng bata. Bawat node ay isang magulang lamang - sa halip na dalawang bilang maaari mong asahan na may mga tao. Halimbawa, ang mga magulang ng 3 ay 7. Ang magulang ng 9 7, at ang magulang ng 6 ay 3. Hindi magkano dito. Mayroon din kaming mga termino upang makipag-usap tungkol sa mga grandparents at inapo, at mas pangkalahatang makipag-usap namin tungkol sa ninuno at mga kaapu-apuhan ng isang partikular na node. Ang ninuno ng isang node - o ninuno, sa halip, ng isang node - ang lahat ng node na nagsisinungaling sa path mula sa root na node. Halimbawa, kung Naghahanap ako sa node 6, pagkatapos ay ang mga ninuno ay pagpunta sa parehong 3 at 7. Ang mga ninuno ng 9, halimbawa, - kung Naghahanap ako sa node 9 - pagkatapos ay ang ninuno ng 9 7. At mga kaapu-apuhan ay eksakto ang reverse. Kung gusto kong tumingin sa lahat ng kaapu-apuhan ng 7, Mayroon akong tumingin sa lahat ng node sa ilalim nito. Kaya, mayroon akong 3, 9, at 6 lahat bilang mga kaapu-apuhan ng 7. 

Ang huling termino na namin makipag-usap tungkol sa ay ang paniwala na ito ng pagiging isang kapatid. Kapatid - uri ng sumusunod na kasama sa mga tuntunin ng pamilya - node na sa parehong antas sa tree. Kaya, 3 at 9 ay kapatid sapagkat ang mga ito sa parehong antas sa tree. Sila ay parehong magkaroon ng parehong magulang, 7. 6 ay walang mga kapatid dahil 9 ay hindi magkakaroon ng anumang mga bata. At 7 ay hindi magkakaroon ng anumang mga kapatid dahil ito ang root ng aming mga puno, at may lamang kailanman 1 ugat. Para sa 7 upang magkaroon ng mga kapatid doon ng node sa itaas 7. May magulang ng 7, kung saan 7 ay hindi na ang ugat ng puno. Pagkatapos na bagong magulang ng 7 rin upang magkaroon ng isang bata, at ang bata na pagkatapos ay ang kapatid ng 7. 

Tama. Paglipat sa. Kapag na sinimulan namin ang aming talakayan ng mga puno ng binary, usapan natin ang tungkol sa kung paano namin ay pagpunta sa gamitin ang mga ito sa makakuha ng isang kalamangan sa parehong mga array at mga naka-link na listahan. At ang paraan na kami ay pagpunta upang gawin iyon ay may ari-arian ito sa pag-order. Sinasabi namin na ang isang binary puno order, ayon sa detalye, kung para sa bawat node sa aming puno, ang lahat ng kanyang mga kaapu-apuhan sa kaliwa - ang kaliwang anak at lahat ng kaapu-apuhan kaliwang bata - magkaroon ng mas mababang mga halaga, at ang lahat ng node sa kanan - ang karapatan ng bata at ang lahat ng mga kaapu-apuhan ng karapatan bata - may node mas mataas kaysa sa halaga ng kasalukuyang node na kaming naghahanap sa. Para lamang sa mga simple, kami ay ipinapalagay na may ay hindi anumang mga duplicate na node sa aming puno. Halimbawa, sa puno hindi namin ka upang harapin ang kaso kung saan mayroon kaming ang halaga 7 sa root  at pagkatapos din namin ang halaga 7 sa ibang lugar sa tree. Sa kasong ito, mapapansin mo na ang puno na ito ay sa katunayan order. Mayroon kaming ang halaga 7 sa root. Lahat sa kaliwa ng 7 - kung ako i-undo lahat ng mga maliit na marka dito - lahat sa kaliwa ng 7 - ang 3 at ang 6 - mga halagang iyon ay parehong mas mababa sa 7, at lahat sa kanan - na lamang ito 9 - ay mas mataas kaysa sa 7. 

Na ito ay hindi lamang order puno na naglalaman ng mga halagang ito, ngunit sabihin gumuhit ng ilang higit pa sa kanila. May ay talagang isang buong grupo ng mga paraan na maaari naming gawin ito. Ako gumamit ng shorthand lamang upang panatilihing simple ang mga bagay kung saan - kaysa sa pagguhit ang buong kahon-at-arrow - Lang ako pagpunta upang gumuhit ang mga numero at magdagdag ng mga arrow sa pagkonekta sa kanila. Upang magsimula, magsulat lamang namin ang aming orihinal na puno muli kung saan nagkaroon kami 7, at pagkatapos ay 3, at pagkatapos ay 3 tulis pabalik sa kanan sa 6, at 7 nagkaroon ng karapatan ng bata na 9. Tama. Ano ang isa pang paraan na maaari naming isulat ang puno? Sa halip ng pagkakaroon ng 3 kaliwang anak ng 7, kami din ang 6 kaliwang anak ng 7, at pagkatapos ay 3 kaliwang anak ng 6. Na magiging ganito ang hitsura ito puno dito mismo kung saan Mayroon akong 7, pagkatapos 6, pagkatapos 3, at 9 sa kanan. Hindi rin namin na magkaroon ng 7 ng aming root node. Mayroon din kaming 6 ng aming root node. Ano ang gusto na hitsura? Kung kami ay upang mapanatili ang order na ari-arian, lahat sa kaliwa ng 6 na mas mababa kaysa dito. Mayroon lamang isang posibilidad, at na 3. Ngunit bilang ang karapatan na anak ng 6, mayroon kaming dalawang mga posibilidad. Una, maaari naming magkaroon ng 7 at pagkatapos ay ang 9, o maaari naming gumuhit ito - tulad ako gawin dito - kung saan mayroon kaming ang 9 bilang ang karapatan na anak ng 6, at pagkatapos ay ang 7 bilang kaliwang anak ng 9. 

Ngayon, 7 at 6 ay hindi lamang ang mga posibleng halaga para sa root. Mayroon din kaming 3 sa root. Ano ang mangyayari kung 3 sa root? Dito, ang mga bagay makakuha ng kaunti kawili-wili. Tatlong ay hindi magkaroon ng anumang mga halaga na mas mababa kaysa dito, kaya na buong kaliwang bahagi ng puno lamang null. Mayroong hindi pagpunta sa anumang doon. Sa kanan, maaari naming ilista ang mga bagay sa pataas na pagkakasunod-sunod. Maaari kaming magkaroon ng 3, pagkatapos 6, pagkatapos 7, pagkatapos 9. O, maaari naming gawin 3, pagkatapos 6, pagkatapos 9, pagkatapos 7. O, maaari naming gawin 3, pagkatapos 7, pagkatapos 6, pagkatapos 9. O, 3, 7 - aktwal na walang, hindi namin maaaring gawin ang isang 7 ito. Na ang aming isang bagay doon. Maaari naming gawin 9, at pagkatapos ay mula sa 9 kami 6 at pagkatapos ay 7. O, maaari naming gawin 3, pagkatapos 9, pagkatapos 7, at pagkatapos ay 6. 

Isang bagay upang gumuhit ang iyong pansin dito ay na ang mga puno na ito ay isang maliit na kakaiba na anyo. Sa partikular, kung tiningnan namin sa 4 na puno sa kanang bahagi - Circle ko sa kanila, narito - mga puno tumingin halos eksakto tulad ng isang naka-link na listahan. Bawat node ay may lamang ng isang bata, at kaya hindi namin magkaroon ng anuman sa mga ito tree-tulad ng istraktura na nakikita namin, halimbawa,  sa isang kabuto puno sa dito sa kaliwang ibaba. Mga puno na ito ay aktwal na tinatawag na sumama puno binary, at kami na makipag-usap tungkol sa mga ito higit pa sa hinaharap - lalo na kung kang pumunta sa tumagal ng iba pang mga kurso ng computer science. Mga puno na ito ay manghina. Ang mga ito ay hindi lubhang kapaki-pakinabang dahil, sa katunayan, ang istraktura na ito lends mismo  sa paghahanap ng mga beses na katulad ng isang naka-link na listahan. Hindi namin upang samantalahin ng dagdag na memorya - ito extrang pointer - dahil sa aming istraktura pagiging masama sa ganitong paraan. Sa halip na pumunta sa at gumuhit ang mga binary puno na may 9 sa root, na ang panghuling kaso na namin, hindi namin sa halip, sa puntong ito, na pagpunta sa makipag-usap ng kaunti tungkol sa iba pang mga termino namin gamitin kapag pakikipag-usap tungkol sa mga puno, na kung saan ay tinatawag na taas. 

Ang taas ng isang puno ay ang distansya mula sa root sa ang pinaka-malayong node, o sa halip ang bilang ng mga hops na mayroon ka upang magsimula mula sa root at pagkatapos ay magtapos sa pinaka-malayong node sa tree. Kung titingnan namin sa ilan sa mga puno na namin ang iginuhit dito mismo, maaari naming makita na kung gagawin namin ito puno sa tuktok na kaliwang sulok at simulan namin sa 3, mayroon kaming upang gumawa ng 1 hop upang makakuha ng sa 6, ang pangalawang hop upang makakuha ng sa 7, at isang third hop upang makakuha ng sa 9. Kaya, ang taas ng puno na ito ay 3. Maaari naming gawin ang parehong ehersisyo para sa iba pang mga puno na nakabalangkas na may berde na ito, at nakita namin na ang taas ng lahat ng mga puno sa katunayan 3. Iyon ay bahagi ng kung bakit ang mga ito lumubha - na ang kanilang taas ay isa lamang mas mababa kaysa sa bilang ng mga node sa buong puno. Kung titingnan namin sa iba pang mga puno na libid sa pula, sa kabilang banda, nakikita namin na ang pinaka-malayong dahon node sa 6 at ang 9 - umalis pagiging mga node na ay walang mga bata. Kaya, upang makakuha ng mula sa root node sa alinman sa 6 o sa 9, mayroon kaming upang gumawa ng isang hop upang makakuha ng sa 7 at pagkatapos ng pangalawang hop upang makakuha ng sa 9, at din, lamang ng pangalawang hop mula sa 7 upang makakuha ng sa 6. Kaya, ang taas ng puno na ito sa paglipas dito lamang 2. Maaari kang bumalik at gawin iyon para sa lahat ng iba pang mga puno na tinalakay namin dati nagsisimula na may 7 at ang 6, at makikita mo na ang taas ng lahat ng mga puno ding 2. 

Ang dahilan na namin ang pinag-uusapan ay iniutos ng binary puno at kung bakit sila ay cool ay dahil maaari kang maghanap sa pamamagitan ng mga ito sa isang katulad na paraan sa paghahanap sa paglipas ng pinagsunod-sunod na array. Ito ay kung saan namin makipag-usap tungkol sa pagkuha ng oras na pinabuting lookup sa ibabaw ng simpleng naka-link na listahan. Na may isang naka-link na listahan - kung gusto mong mahanap ang isang partikular na elemento - ikaw ay sa pinakamahusay na pagpunta sa gawin ang ilang mga uri ng linear na paghahanap kung saan simulan mo sa simula ng isang listahan at hop isa-by-isa - isang node ng isa node - sa pamamagitan ng buong listahan hanggang sa mahanap mo ang anumang naghahanap ka para sa. Sapagkat, kung mayroon kang isang binary puno na naka-imbak sa ito maganda ang format, maaari mong aktwal na makakuha ng mas maraming ng isang binary paghahanap na nangyayari sa kung saan mo hatiin at lupigin at paghahanap sa pamamagitan ng naaangkop na kalahati ng puno sa bawat hakbang. Natin makita kung paano na gumagana. 

Kung kami ay may - muli, pagpunta sa aming orihinal na puno - sisimulan namin sa 7, mayroon kaming 3 sa kaliwa, 9 sa kanan, at sa ilalim ng 3 namin ang 6. Kung gusto naming upang maghanap para sa bilang 6 sa puno, gusto namin magsimula sa root. Gusto namin ihambing ang halaga namin ang iyong hinahanap para sa, sabihin nating 6, sa halaga na naka-imbak sa node na kasalukuyan kaming naghahanap sa, 7, mahanap na 6 ay talagang mas mababa kaysa sa 7, kaya nais naming ilipat sa kaliwa. Kung ang halaga ng 6 ay mas mataas kaysa sa 7, sa halip na namin inilipat sa kanan. Dahil alam namin na - dahil sa istraktura ng aming order na puno ng binary - lahat ng ang mga halaga na mas mababa kaysa sa 7 na naka-imbak sa kaliwa ng 7, walang pangangailangan sa kahit abala naghahanap sa pamamagitan ng kanang bahagi ng puno. Kapag naming ilipat sa kaliwa at kami ngayon sa node na naglalaman ng 3, maaari naming gawin na parehong paghahambing muli kung saan Inihambing namin ang 3 at ang 6. At nakita namin na habang 6 - ang halaga na kaming naghahanap ng mga - ay mas malaki kaysa sa 3, maaari naming pumunta sa kanang bahagi ng node na naglalaman ng 3. Walang kaliwang bahagi dito, kaya kami binabalewala na. Ngunit lamang namin malaman na dahil kaming naghahanap sa tree mismo, at maaari naming makita na ang puno ay walang mga bata. 

Rin medyo madali upang maghanap 6 sa puno na ito kung ginagawa namin ito sa ating sarili bilang tao, ngunit sabihin sundin ang prosesong ito nang wala sa loob tulad ng isang computer ay gawin talagang maunawaan ang algorithm. Sa puntong ito, na namin ngayon ang iyong hinahanap sa isang node na naglalaman ng 6, at kami ay naghahanap para sa ang halaga 6, ito, sa katunayan, hindi namin natagpuan ang mga naaangkop na node. Natagpuan namin ang halaga 6 sa aming puno, at maaari naming ihinto ang aming paghahanap. Sa puntong ito, depende sa kung anong nangyayari sa, maaari naming sabihin, oo, namin natagpuan ang halaga 6, umiiral sa aming puno. O, kung kami ay pagpaplano upang magpasok ng isang node o gawin ang isang bagay, maaari naming gawin iyon sa puntong ito. 

Natin ng ilang higit pa lookup lamang upang makita kung paano ito gumagana. Tingnan natin sa kung ano ang mangyayari kung namin upang subukan at hanapin ang halaga 10. Kung kami ay upang tumingin up ang halaga 10, gusto naming magsimula sa root. Gusto naming makita na 10 ay mas mataas kaysa sa 7, kaya nais naming ilipat sa kanan. Gusto naming makakuha ng sa 9 at ihambing 9 sa 10 at makita na 9 ay talagang mas mababa sa 10. Kaya muli, nais naming subukan upang ilipat sa kanan. Ngunit sa puntong ito, gusto naming mapansin na hindi namin sa isang null node. Wala doon. May walang kung saan ang 10 ay dapat na. Ito ay kung saan maaari naming iulat pagkabigo - na may ay talagang walang 10 sa tree. At sa wakas, sabihin sa pamamagitan ng kaso na kung saan kami ay sinusubukan upang maghanap 1 sa tree. Ito ay katulad sa kung ano ang mangyayari kung tinitingnan namin hanggang 10, maliban sa halip ng pagpunta sa kanan, kami ay pagpunta upang pumunta sa kaliwa. Magsisimula kami sa 7 at makita na 1 ay mas mababa kaysa sa 7, kaya naming ilipat sa kaliwa. Makuha namin ang 3 at makita na 1 ay mas mababa sa 3, kaya muling subukan namin upang ilipat sa kaliwa. Sa puntong ito, mayroon kaming null node, kaya muli maaari naming i-ulat ang pagkabigo. 

Kung mo gusto upang matuto nang higit pa tungkol sa mga binary puno, may isang buong grupo ng mga masaya maliit na problema na maaari mong gawin sa kanila. Iminumungkahi ko ang pagsasanay sa pagguhit ng mga diagram isa-by-isa at ng pagsunod sa pamamagitan ng lahat ng ibang hakbang, dahil ito ay darating sa sobrang-madaling-gamiting hindi lamang kapag ginagawa mo ang problema Huffman pag-encode set kundi pati na rin sa hinaharap kurso - lamang ang pag-aaral kung paano upang gumuhit ng mga istraktura ng data na ito at sa tingin sa pamamagitan ng mga problema may panulat at papel o, sa kasong ito, iPad at pluma. 

Sa puntong ito bagaman, kami ay upang ilipat sa gawin ang ilang mga coding na kasanayan at aktwal na maglaro na may mga puno ng binary at makita. Ako pagpunta upang lumipat pabalik sa aking computer. Para sa bahagi ng seksyon, sa halip ng paggamit ng CS50 Run o CS50 puwang, Ako pagpunta sa gamitin ang appliance. 

Ng pagsunod kasama ang mga detalye ng Set Problema, Nakikita ko na ako dapat upang buksan ang appliance, pumunta sa aking Dropbox folder, lumikha ng isang folder na tinatawag na Seksyon 7, at pagkatapos ay lumikha ng isang file na tinatawag na binary_tree.c. Narito kami. Mayroon akong appliance na bukas. Ako pupunta makuha ang isang terminal. Ako pagpunta upang pumunta sa folder Dropbox, gumawa ng isang direktoryo na tinatawag na section7, at makita ito lubos na walang laman. Ngayon ako pagpunta upang buksan ang binary_tree.c. Tama. Narito pumunta namin - walang laman na file. 

Natin bumalik sa detalye. Detalye ng humihiling sa upang lumikha ng isang bagong uri ng kahulugan para sa isang binary puno node na naglalaman ng mga int halaga - tulad ng ang halaga na iginuhit namin sa aming balangkas bago. Kami ay pagpunta sa gamitin ang boilerplate na ito typedef na ginawa namin dito mismo na dapat mong makilala mula Problema Set 5 - kung ginawa mo ang hash na paraan ng talahanayan ng mapanakop ang programa speller. Dapat mo ring makilala ang mga ito mula sa seksyon ng huling linggo ng kung saan usapan natin ang tungkol sa mga naka-link na listahan. Mayroon kaming ang typedef na ito ng isang struct node, at Nagbigay kami ng struct node na ito ang pangalan ng struct node muna upang maaari naming sumangguni sa ito dahil lilikha kami gusto mong payo struct node bilang bahagi ng aming mga struct, ngunit pagkatapos namin libid ito - o sa halip, nakapaloob na ito - sa isang typedef sa gayon ay, mamaya sa code, maaari naming sumangguni sa struct na ito bilang lamang node sa halip ng isang struct node. 

Ito ay katulad na katulad sa isa-isa naka-link na listahan kahulugan na nakita natin noong nakaraang linggo. Upang gawin ito, sabihin lamang magsimula sa pamamagitan ng pagsusulat ang boilerplate. Alam namin na mayroon kami ng isang integer value, kaya ipapakita namin ilalagay sa int halaga, at pagkatapos ay sa halip ng pagkakaroon ng isa lamang pointer sa susunod na elemento - namin ginawa na may isa-isa-naka-link na listahan - kami ay pagpunta sa kaliwa at kanang mga payo sa anak. Na medyo simple masyadong - struct node * kaliwang anak; at struct node * kanang bata;. Cool. Na mukhang isang medyo magandang simula. Natin bumalik sa detalye. 

Ngayon ay kailangan namin upang idedeklara ang isang pandaigdigang node * variable para sa root ng isang puno. Kami ay pagpunta upang gawin ang pandaigdigang lamang tulad ng ginawa namin ang unang pointer sa aming naka-link na listahan din pandaigdigang. Ito ay na sa function na magsulat namin hindi namin upang panatilihin ang pagpasa sa paligid ng ugat na ito - kahit na makikita namin makita na kung gagawin mo nais na magsulat ng mga function na ito recursively, maaari itong maging mas mahusay na kahit hindi pumasa ito bilang isang pandaigdigang sa unang lugar at sa halip ay initialize ito nang lokal sa iyong pangunahing function na. Ngunit, makikita namin gawin ito sa buong mundo upang magsimula. Muli, makikita namin magbigay ng ilang mga puwang, at ako pagpunta upang idedeklara ng node * ugat. Lamang upang tiyakin na hindi ko iwanan ang uninitialized, Pupunta ako upang itakda ang katumbas ng null. Ngayon, sa pangunahing function na - na magpapadala kami sumulat talagang mabilis dito mismo - int pangunahing (int argc, const magpasinda * argv []) - at ako pagpunta upang simulan ang deklarasyon ng aking argv array bilang const lang kaya na alam ko ang mga argumento argumento na ako malamang na hindi nais na baguhin ang. Kung gusto kong baguhin ang mga ito ang dapat kong marahil paggawa ng mga kopya ng mga ito. Makikita mo ang marami sa code. Ang fine alinman paraan. Masarap na mag-iwan ang mga ito bilang - alisin ang const kung nais mong. Ko karaniwang ilagay ang mga ito sa loob lamang ng sa gayon na ipaalala ko sa aking sarili  na hindi ko marahil gusto mong baguhin ang mga argumento. 

Tulad ng nakasanayan, ako pagpunta sa isama ito return 0 linya sa dulo ng pangunahing. Narito, ako initialize ang aking na root node. Bilang ito nakatayo ngayon, Mayroon akong isang pointer na nakatakda sa null, kaya ng pagturo sa wala. Upang aktwal na simulan ang pagbuo ng node, Ko kailangan muna upang magtalaga ng memory para dito. Ako pagpunta sa gawin na sa pamamagitan ng paggawa ng memory sa magbunton gamit ang malloc. Ako pagpunta upang i-set ang ugat katumbas sa resulta ng malloc, at ako pagpunta upang gamitin ang sizeof operator upang makalkula ang laki ng isang node. Ang dahilan na gamitin ko sizeof node bilang kabaligtaran sa, sabihin nating, paggawa ng isang bagay tulad nito - malloc (4 + 4 +4) o malloc 12 - dahil gusto ko ang aking code sa tugma hangga't maaari. Gusto ko ito. File c, makatipon ito sa appliance, at pagkatapos ay makatipon ito sa aking 64-bit Mac - o sa isang ganap na iba't ibang mga arkitektura - at gusto ko ang lahat ng ito upang gumana sa parehong. 

Kung ako sa paggawa ng mga pagpapalagay tungkol sa laki ng mga variable - ang laki ng isang int o ang laki ng isang pointer - pagkatapos rin ako sa paggawa ng mga pagpapalagay tungkol sa mga uri ng mga architectures kung saan ang aking code ay maaaring matagumpay na makatipon kapag nagpatakbo. Palaging gamitin ang sizeof bilang kabaligtaran nang manu-mano sa summing ang mga patlang ng struct. Ang iba pang dahilan ay na maaaring may padding na tagatala Inilalagay ng sa struct. Kahit lamang summing ang mga indibidwal na mga patlang ay hindi isang bagay na karaniwan kang gustong gawin, ito, tanggalin ang linya na iyon. Ngayon, sa talagang initialize na root node na ito, Ako pagpunta sa mag-plug ng mga halaga para sa bawat isa ng mga iba't ibang mga patlang. Halimbawa, para sa halaga na alam ko na gusto kong i-initialize sa 7, at sa ngayon ako upang itakda ang kaliwang anak na null at ang karapatan ng bata sa ring maging null. Magaling! Ginawa namin na bahagi ng spec. 

Ang pagtutukoy sa ibaba ng pahina 3 ay nagtatanong sa akin upang lumikha ng tatlong higit pang mga node - isa na naglalaman ng 3, isa na naglalaman ng 6, at isa na may 9 na - at pagkatapos wire up ang mga ito kaya hitsura nang eksakto tulad ng ating puno diagram na namin ang pakikipag-usap tungkol sa dati. Natin gawin na medyo mabilis dito. Makikita mo ang talagang mabilis na ako upang simulan ang pagsusulat ng isang bungkos ng mga nauulit na code. Pupunta ako upang lumikha ng isang node * at ako pagpunta sa tumawag ito tatlong. Ako pagpunta upang itakda ang katumbas ng malloc (sizeof (node)). Ako pagpunta upang itakda ang tatlong> halaga = 3. Tatlong -> left_child = null; tatlong -> kanan _child = null; pati na rin. Na mukhang medyo katulad sa Sinisimulan ang ugat, at iyon mismo ang Ako pagpunta sa gawin kung sisimulan ko Sinisimulan ng 6 at 9 pati na rin. Ko na talagang mabilis dito - aktwal na, ako pagpunta sa gawin ang isang maliit na kopyahin at i-paste ang, at tiyakin na ako - oo.  Ngayon, ko na nakuha ko kopyahin at maaari kong magpatuloy at itakda ito katumbas ng 6. Maaari mong makita na ito ay tumatagal ng sandali at hindi super-mahusay. Sa loob lamang ng ilang sandali, makikita namin magsulat ng isang function na gawin ito para sa amin. Gusto kong palitan ito na may 9, palitan na na may 6. 

Ngayon Mayroon namin ang lahat ng aming mga node nilikha at nasimulan. Mayroon namin ang aming ugat-set katumbas ng 7, o naglalaman ng mga halaga 7, aming node naglalaman 3, ang aming node na naglalaman ng 6, at ang aming node na naglalaman 9. Sa puntong ito, ang lahat ng kami ay may sa gawin ay ang lahat ng wire up. Ang dahilan kung bakit ko nasimulan ang lahat ng mga payo sa null lamang sa gayon ay gumawa ako sigurado na Wala akong anumang uninitialized pointer sa doon sa pamamagitan ng aksidente. At din dahil, sa puntong ito, ako lamang magkaroon ng aktwal na ikonekta ang mga node sa bawat isa - sa mga na aktwal na sila ay konektado sa - hindi ko upang pumunta sa pamamagitan at gumawa siguraduhin na ang lahat ng mga nulls ay doon sa naaangkop na lugar. 

Simula sa root, alam ko na kaliwang bata ay ang root ng 3. Alam ko na ang kanang bata root 9. Pagkatapos nito, ang lamang ang iba pang mga anak na ako pakaliwa mag-alala tungkol kanang 3 anak, na 6. Sa puntong ito, ang lahat ng mukhang medyo magandang. Tatanggalin namin ang ilan sa mga linyang ito. Ngayon lahat mukhang medyo magandang. Natin bumalik sa aming mga pagtutukoy at makita kung ano ang namin ang susunod na gagawin. 

Sa puntong ito, mayroon kaming upang magsulat ng isang function na tinatawag na 'ay naglalaman ng' may ng prototype ng 'bool naglalaman ng (int value)'. At ito ay naglalaman ng function ay nagbabalik ng tunay  kung ang puno ang tulis ng aming global variable ugat  naglalaman ng halaga ang naipasa sa function at maling kung hindi man. Natin magpatuloy at gawin iyon. Ito ay eksakto tulad ng lookup na ginawa namin sa pamamagitan ng kamay sa iPad ng kaunti lamang ang nakalipas. Natin mag-zoom sa ilang sandali at mag-scroll pataas. Kami ay pagpunta sa ilagay ito function na itaas ang aming pangunahing function na sa gayon ay hindi namin upang gawin ang anumang uri ng prototyping. Kaya, bool naglalaman (int value). Doon kami. May aming boilerplate deklarasyon. Lamang upang tiyakin na ito ay makatipon, Ako sige at itakda ito katumbas ng bumalik false. Sa ngayon function na ito ay hindi gawin at laging iulat na ang halaga na kaming naghahanap ng mga hindi sa tree. 

Sa puntong ito, marahil ito ay isang magandang ideya - dahil namin ang nakasulat na isang buong grupo ng mga code at hindi pa namin kahit na sinubukan ng pagsubok ko pa ito - upang matiyak na ang lahat ng ito compiles. May ilang mga bagay na mayroon kaming gawin upang tiyakin na ito ay aktwal na makatipon. Una, tingnan kung namin ang paggamit ng anumang mga function sa anumang mga aklatan na hindi pa namin na-kasama. Ang mga pagpapaandar na ginamit namin ang sa ngayon ay malloc, at pagkatapos rin namin na paggamit ng ganitong uri - ito hindi karaniwang uri ng tinatawag na 'bool' - na kasama sa standard bool header ng file. Talagang nais namin upang isama ang standard na bool.h para sa bool uri, at gusto rin naming # include standard lib.h para sa standard na mga aklatan na ang malloc, at libre, at ang lahat ng na. Kaya, mag-zoom out, namin na umalis. Natin subukan at tiyakin na ito ay aktwal na ginawa makatipon. Nakikita namin na ito, kaya kami sa kanan track. 

Natin buksan up binary_tree.c muli. Ito compiles. Natin pumunta down at tiyakin na namin magpasok ng ilang mga tawag sa aming naglalaman ng function na - lamang upang tiyakin na na ang lahat ng mahusay at magandang. Halimbawa, kapag ginawa namin ang ilang mga lookup sa aming puno kanina, sinubukan naming hanapin ang mga halaga 6, 10, at 1, at alam namin na 6 sa tree, 10 ay hindi sa tree, at 1 ay hindi sa tree alinman. Gamitin natin ang mga tawag ng sample bilang isang paraan upang malaman kung man o hindi aming naglalaman ng function ay gumagana. Upang gawin iyon, ako pagpunta sa gamitin ang printf function na, at kami ay pagpunta upang i-print ang resulta ng tawag sa ay naglalaman ng. Ako pagpunta sa ilagay sa isang string "ay naglalaman ng (% d) = dahil  kami ay pagpunta sa plug sa ang halaga na kami ay pagpunta upang hanapin, at =% s \ n "at gamitin na bilang aming format string. Kami ay pagpunta upang makita - literal-print sa screen - kung ano ang hitsura tulad ng function na tawag. Ito ay hindi tunay ang function na tawag.  Ito ay isang string na dinisenyo upang hitsura ng isang tawag ng function na. 

Ngayon, kami ay pagpunta sa plug sa ang mga halaga. Kami ay pagpunta sa subukan naglalaman ng sa 6, at pagkatapos ay kung ano ang kami ay pagpunta sa gawin dito ay gamitin na tatluhan operator. Natin makita - naglalaman ng 6 - kaya, ngayon ko na nilalaman ng 6 at kung naglalaman ng 6 ay totoo, ang string na kami ay pagpunta sa magpadala sa format ng character ang% s ay ang string na "true". Sabihin mag-scroll sa paglipas ng ilang sandali. Kung hindi man, nais naming upang magpadala ng mga string "false" kung naglalaman ng 6 return false. Ito ay isang maliit na maloko na anyo, ngunit malaman ko maaaring ko pati na rin ilarawan kung ano ang tatluhan operator Mukhang dahil hindi namin nakita ang mga ito para sa sandali. Ito ay gandang, madaling gamiting paraan upang malaman kung gumagana ang aming naglalaman ng function ay. Pupunta ako upang mag-scroll sa kaliwa, at ako pagpunta sa kopyahin at i-paste ang linyang ito ng ilang beses. Ito ay nagbago ang ilan sa mga halagang ito sa paligid, kaya ito ay pagpunta sa 1, at ito ay pagpunta sa 10. 

Sa puntong ito Mayroon namin ang gandang function na naglalaman ng. Mayroon kaming ilang mga pagsubok, at makikita namin makita kung ito ang lahat ng mga gawa. Sa puntong ito namin ang nakasulat na ilang higit pang mga code. Oras na umalis at tiyakin na ang lahat pa rin compiles. Quit out, at ngayon sabihin subukan ang paggawa ng puno ng binary muli. Well, mukhang kami nakakuha ng isang error, at hindi na namin Mayroon ito tahasang deklarasyon sa library function na printf. Mukhang kailangan namin upang pumunta sa at # include standardio.h. At sa na, ang lahat ay dapat makatipon. Hindi namin ang lahat ng mabuti. Ngayon ipaalam sa subukan ang pagpapatakbo ng binary puno at makita kung ano ang mangyayari. Narito ang namin,. / Binary_tree, at makita namin na, bilang inaasahan namin - dahil hindi pa namin ipinatupad naglalaman pa, o sa halip, lamang namin ang ilagay sa return false - nakikita namin na lamang ito bumabalik maling para sa lahat ng mga ito, kaya na sa lahat ng nagtatrabaho para sa pinaka-bahagi may kabutihan. 

Natin bumalik at aktwal na ipatupad naglalaman sa puntong ito. Pupunta ako mag-scroll pababa, mag-zoom in, at - Tandaan, ang algorithm na ginamit namin ay na namin na nagsimula sa root node at pagkatapos ay sa bawat node na aming nakatagpo, gawin namin ang isang paghahambing, at batay sa paghahambing na namin alinman ilipat sa kaliwa anak o sa kanan anak. Ito ay pagpunta upang tumingin na halos kapareho sa code ng paghahanap ng binary na namin sinulat ni mas maaga sa ang termino. Kapag nagsimula kami off, alam namin na gusto naming upang i-hold sa sa kasalukuyang node na namin ang pagtingin sa, at ang kasalukuyang node ay pagpunta sa nasimulan sa root ang node. At ngayon, kami ay pagpunta sa patuloy na pagpunta sa pamamagitan ng puno, at tandaan na ang aming pagtigil kondisyon -  kapag aktwal na namin nagtrabaho sa pamamagitan ng halimbawa sa pamamagitan ng kamay - ay kapag kami nakatagpo ng isang null node, hindi kapag kami ay tumingin sa isang null anak, kundi kapag namin ang aktwal na inilipat sa isang node sa tree at natagpuan na hindi namin sa isang null node. Kami ay pagpunta sa umulit hanggang kuprum ay hindi katumbas ng null. At kung ano ang namin gawin? Kami ay pagpunta upang subukan kung (kuprum -> halaga == halaga), alam namin na aktwal na nalaman namin na node na kaming naghahanap ng para sa. Kaya dito, maaari naming nagbabalik ng tunay. Kung hindi man, nais namin upang makita kung o hindi ang halaga ay mas mababa kaysa sa halaga. Kung ang halaga ang kasalukuyang node ay mas mababa kaysa sa halaga kaming naghahanap para sa, kami ay pagpunta sa ilipat sa kanan. Kaya, kuprum = kuprum -> right_child; at kung hindi man, kami ay pagpunta sa ilipat sa kaliwa. kuprum = kuprum -> left_child;. Medyo simple. 

Maaaring makilala ang loop na mukhang na halos kapareho sa ito mula sa binary paghahanap nang mas maaga sa ang termino, maliban pagkatapos namin ay pagharap sa mababa, kalagitnaan, at mataas. Narito, kami na lang ay upang tumingin sa isang kasalukuyang halaga, kaya maganda at simpleng. Tiyakin nating ang code na ito ay gumagana. Una, tiyakin na ito compiles. Mukhang ginagawa nito. Natin subukang patakbuhin ito. At katunayan, mga Kopya ang lahat na aming inaasahan. Nahahanap nito 6 sa tree, hindi mahanap ang 10 dahil sa 10 hindi sa tree, at hindi mahanap 1 alinman dahil 1 Hindi rin sa tree. Cool na bagay. 

Tama. Natin bumalik sa aming mga pagtutukoy at makita kung ano ang susunod. Ngayon, nais upang magdagdag ng ilang higit pang mga node sa aming puno. Gustong idagdag 5, 2, at 8, at tiyakin na ang aming naglalaman ng code gumagana pa rin tulad ng inaasahan. Sabihin pumunta gawin iyon. Sa puntong ito, sa halip ng paggawa ng muli na nakakainis na kopya at i-paste ang, sabihin magsulat ng isang function na sa aktwal na lumikha ng isang node. Kung mag-scroll namin ang lahat ng mga paraan sa pangunahing, nakikita namin na namin ang paggawa nito katulad code nang paulit-ulit sa bawat oras na nais namin upang lumikha ng isang node. 

Natin magsulat ng isang function na aktwal na bumuo ng isang node para sa amin at ibalik ito. Ako pagpunta sa tumawag ito build_node. Ako pagpunta sa bumuo ng isang node na may partikular na halaga. Mag-zoom in dito. Ang unang bagay na ako pagpunta sa gawin ay aktwal na lumikha ng puwang para sa node sa magbunton. Kaya, node * n = malloc (sizeof (node)); n -> halaga = halaga; at pagkatapos dito, lamang ako pagpunta sa simulan ang lahat ng mga patlang sa naaangkop na halaga. At sa pinakadulo, babalik kami sa aming node. Tama. Ang isang bagay na dapat tandaan ay na ito andar dito mismo pagpunta sa ibalik ng pointer sa memory na magbunton-inilalaan. Ano ang maganda ang tungkol dito na ito node ngayon - namin na idedeklara ito sa magbunton dahil kung ipinahayag namin ito sa stack hindi namin magagawang upang gawin ito sa function na tulad nito. Memorya na gusto pumunta ng saklaw at ay hindi wasto kung sinubukan naming i-access ito sa ibang pagkakataon sa. Dahil kami ay deklarasyon magbunton-inilalaan memory, namin pagpunta sa pangangalaga ng pagbabakante ito sa ibang pagkakataon para sa aming programa upang hindi mahayag anumang memorya. Namin ang punting sa na para sa lahat ng iba pa sa code para lamang sa kapakanan simple sa oras, ngunit kung sakaling magsulat ng isang function na ganito ang hitsura kung saan mayroon kang - ilang tumawag ito malloc o realloc loob - nais mong tiyakin na inilagay mo ang ilang uri ng mga komento dito na nagsasabing, hey, alam mo, nagbabalik ng magbunton-inilalaan na node na nasimulan ang pumasa sa-in halaga. At pagkatapos ay nais mong tiyakin na inilagay mo sa ilang mga uri ng tandaan na nagsasabing tumatawag ay dapat magbakante ang ibinalik na memory. Sa ganoong paraan, kung ang isang tao man pupunta at gumagamit ng function na iyon, alam nila na kung ano ang makakuha ng bumalik sila mula sa andar sa ilang mga punto na kailangan na napalaya. 

Ipagpalagay na ang lahat ng mahusay at magandang dito, maaari naming pumunta sa aming code at palitan ang lahat ng mga linya dito mismo may mga tawag sa aming build node function na. Natin gawin na talagang mabilis. Ang isang bahagi na hindi namin upang palitan bahaging ito dito sa ilalim kung saan namin ang aktwal na wire ang node upang ituro sa bawat isa, dahil hindi namin maaaring gawin sa aming function na. Ngunit, sabihin gawin ugat = build_node (7); node * tatlong = build_node (3); node * anim = build_node (6); node * siyam = build_node (9);. At ngayon, gusto din namin magdagdag ng mga node para sa - node * limang = build_node (5); node * walong = build_node (8); at kung ano ang iba pang mga node? Natin makikita dito. Nais naming ring magdagdag ng 2 - node * dalawang = build_node (2);. Tama. Sa puntong ito, alam namin na namin ang nakuha 7, ang 3, ang 9, at ang 6 lahat ng naka-wire na naaangkop, ngunit kung ano ang tungkol sa 5, 8, at ang 2? Upang panatilihin ang lahat sa naaangkop na order, Alam namin na karapatan tatlong anak ay 6. Kaya, kung kami ay pagpunta upang idagdag ang 5, 5 din nabibilang sa kanang bahagi ng puno na kung saan ay ang root ang 3, kaya 5 nabibilang bilang kaliwang anak ng 6. Maaari naming gawin ito sa pamamagitan ng sinasabi, anim -> left_child = limang; at pagkatapos ay ang 8 nabibilang bilang kaliwang anak ng 9, kaya siyam -> left_child = walong; at pagkatapos ay 2 kaliwang anak ng 3, kaya maaari naming gawin iyon up dito - sa iyo -> left_child = dalawang;. Kung hindi mo pa masyadong sundin kasama na, iminumungkahi ko kang gumuhit ito sa iyong sarili. 

Tama. Natin i-save ang. Sabihin pumunta at tiyaking ito compiles, at pagkatapos ay maaari naming idagdag sa aming mga tawag ay naglalaman ng. Mukhang lahat pa rin compiles. Natin pumunta at idagdag sa ilang ay naglalaman ng mga tawag. Muli, ako pagpunta sa gawin ng kaunti ng kopyahin at i-paste ang. Ngayon natin maghanap para sa 5, 8, at 2. Tama. Tiyakin nating na ito lahat ng mukhang mahusay pa rin. Magaling! I-save at mag-quit. Ngayon sabihin gumawa, makatipon, at ngayon sabihin patakbuhin. Mula sa mga resulta, mukhang lahat ay gumagana lamang maganda at mahusay na. Magaling! Kaya ngayon Mayroon namin ang aming naglalaman ng function na nakasulat. Sabihin ilipat sa at simulan ang nagtatrabaho sa kung paano upang ipasok ang mga node sa puno dahil, tulad ng ginagawa namin ito ngayon, bagay ang hindi masyadong medyo. 

Kung pumunta kami pabalik sa detalye, humihiling sa amin upang magsulat ng isang function na tinatawag na isingit - muli, bumabalik ng bool man o hindi kami maaaring aktwal na ipasok ang node sa puno - at pagkatapos ay ang halaga upang ipasok sa puno ay tinukoy bilang lamang ang argumento sa aming insert function na. Kami ay nagbabalik ng tunay na kung maaaring namin sa katunayan ipasok ang node na naglalaman ng halaga sa puno, na nangangahulugan na namin, isa, may sapat na memorya, at pagkatapos ng dalawang, ang node na ay hindi na umiiral sa tree dahil - Tandaan, hindi namin ay pumunta sa na magkaroon ng duplicate na mga halaga sa tree, lamang upang gawing simple ang mga bagay. Tama. Back sa ang code. Buksan ito. Mag-zoom sa isang bit, at pagkatapos ay mag-scroll pababa. Natin ilagay ang insert function na karapatan sa itaas ay naglalaman ng. Muli, ito ay pagpunta sa tinatawag na bool insert (int value). Bigyan ito ng kaunti pa sa espasyo, at pagkatapos, bilang isang default na, ipaalam sa ay ilagay sa return false sa pinakadulo. Ngayon pababa sa ibaba, sabihin sige at sa halip ng nang manu-mano ang pagbuo ng node sa pangunahing ating sarili at ang mga kable up ang mga ito upang tumuro sa bawat isa tulad ng ginagawa namin, makikita naming umasa sa aming insert function na upang gawin iyon. Hindi namin umasa sa aming insert function na bumuo ng ang buong puno mula sa simula pa, kundi magpapadala kami mapupuksa ng mga linyang ito - we'll magkomento ang mga linyang ito - na bumuo ng ang node 5, 8, at 2. At sa halip, gagamitin namin magpasok ng mga tawag sa aming insert function na upang matiyak na na aktwal na gumagana. Narito kami. 

Na namin ngayon ang nagkomento ang mga linya na ito. Lamang kami 7, 3, 9, at 6 sa aming puno sa puntong ito. Upang tiyakin na ito ay ang lahat ng nagtatrabaho, maaari naming mag-zoom out, aming binary puno, patakbuhin ang mga ito, at maaari naming makita na naglalaman ay ngayon na nagsasabi sa amin na hindi namin lubos na karapatan - 5, 8, at 2 ay hindi na sa tree. Bumalik sa code, at kung paano namin upang ipasok? Tandaan kung ano ang ginawa namin kapag aktwal na namin ang pagpasok 5, 8, at 2 dati. Naglaro namin na Plinko laro kung saan namin na nagsimula sa root, nagpunta pababa sa puno ng isa sa pamamagitan ng isa sa pamamagitan ng isa hanggang sa nakita namin ang naaangkop na agwat, at pagkatapos namin wired sa node sa naaangkop na lugar. Kami ay pagpunta sa gawin ang parehong bagay. Ito ay isa lamang tulad ng pagsusulat ng code na ginamit namin sa ay naglalaman ng function na upang mahanap ang lugar kung saan node dapat, at pagkatapos lamang namin ay pagpunta upang ipasok ang node doon. Natin simulan ang paggawa na. 

Kaya mayroon kaming node * kuprum = ugat; lang kami sundin ay naglalaman ng code hanggang sa nakita namin na hindi ito lubos para sa amin. Kami ay pagpunta sa pumunta sa pamamagitan ng puno habang ang kasalukuyang elemento ay hindi null, at kung nakita namin ay katumbas sa halaga na kami ay sinusubukan upang ipasok ang halaga na kuprum - na rin, ito ay isa ng mga kaso kung saan ay hindi aktwal na namin ma-ipasok ang node sa puno dahil ang ibig sabihin nito ay mayroon kaming isang duplicate na halaga. Narito aktwal na kami ay pagpunta sa bumalik false. Ngayon, iba pa kung ang halaga kuprum ay mas mababa kaysa sa halaga, ngayon alam namin na ilipat namin sa kanan  dahil nabibilang sa kanang kalahati ng puno ng kuprum ang halaga. Kung hindi man, kami ay pagpunta sa ilipat sa kaliwa. Iyon ay talaga ang aming mga naglalaman ng gumana doon. 

Sa puntong ito, sa sandaling nakumpleto na namin ang habang loop na ito, aming kuprum pointer ay pagpunta sa na tumuturo sa null kung ang function ay hindi na ibinalik. Samakatuwid Nagkakaroon kami ng kuprum sa lugar kung saan nais namin upang ipasok ang bagong node. Ano ang nananatiling gawin sa aktwal na bumuo ng bagong node, kung saan maaari naming gawin medyo madali. Maaari naming gamitin ang aming super-madaling-gamiting build node function na, at isang bagay na hindi namin ginawa mas maaga - lang namin uri ng kinuha para sa ipinagkaloob ngunit gagawin namin ngayon lang masiguradong - ipapakita namin subukan upang tiyakin na ang halaga na ibinalik sa pamamagitan ng bagong node ay aktwal hindi null, dahil hindi namin nais upang simulan ang access na memorya kung ito ay null. Maaari naming subukan upang matiyak na ang bagong node ay hindi katumbas ng null. O sa halip, maaari lang namin makita kung ito talaga null, at kung ito ay null, maaari lang namin bumalik maling maaga pa. 

Sa puntong ito, mayroon kaming wire bagong node sa nito naaangkop na lugar sa tree. Kung titingnan namin pabalik sa pangunahing at kung saan kami ay talagang mga kable sa halaga bago, nakikita namin na ang paraan na aming ginagawa ito kapag gusto namin upang ilagay ang 3 sa tree namin access ang kaliwang anak ng ugat. Kapag inilalagay namin ang 9 sa tree, nagkaroon kami upang ma-access ang kanang anak ng root. Nagkaroon kami ng isang pointer sa magulang upang maglagay ng bagong halaga sa puno. Scroll-back up upang ipasok, na hindi pagpunta sa medyo gumana dito dahil hindi namin magkaroon ng isang magulang pointer. Ang gusto naming gawin ay, sa puntong ito, suriin ang halaga ng magulang at makita - mahusay, sus, kung ang halaga ng magulang ay mas mababa kaysa sa kasalukuyang halaga, pagkatapos kanang anak ng magulang ay dapat na ang bagong node; kung hindi man, kaliwang anak sa magulang ay dapat na ang bagong node. Subalit, hindi namin ito magulang pointer medyo pa. 

Upang makakuha ng ito, aktwal na kami ay pagpunta upang subaybayan ito bilang pumunta kami sa pamamagitan ng puno at hanapin ang naaangkop na lugar sa aming loop sa itaas. Maaari naming gawin iyon sa pamamagitan ng pag-scroll back up sa tuktok ng aming insert function na at pagsubaybay ng isa pang pointer variable tinatawag ang magulang. Kami ay pagpunta sa itakda ito katumbas null simula, at pagkatapos ay sa tuwing pumunta kami sa pamamagitan ng puno, kami ay pagpunta upang itakda ang pointer ng magulang upang tumugma sa kasalukuyang pointer. Itakda ang magulang katumbas sa kuprum. Sa ganitong paraan, sa bawat oras na pumunta kami sa pamamagitan ng, kami ay pagpunta upang matiyak na bilang ang kasalukuyang pointer ay nakakakuha incremented ang magulang pointer sumusunod - isang antas lamang na mas mataas kaysa sa kasalukuyang pointer sa tree. Na ang lahat ng mukhang medyo magandang. 

Tingin ko ang isang bagay na namin nais na ayusin ito bumuo ng node bumabalik null. Upang bumuo ng node sa aktwal na matagumpay na bumalik null, gagamitin namin upang baguhin ang code na iyon, dahil dito, hindi namin sinubukan upang matiyak na malloc nagbalik ng isang wastong pointer. Kaya, kung (n = null!), Pagkatapos - kung malloc nagbalik ng isang wastong pointer, makikita namin initialize ito; kung hindi man, kami lang bumalik at na bumabalik null para sa amin. Ngayon ang lahat ng mukhang medyo magandang. Natin tiyakin na ito aktwal na compiles. Puno na Magsagawa ng binary, at oh, Mayroon namin ang ilang mga bagay-bagay na pagpunta sa dito. 

Mayroon kaming isang implicit deklarasyon ng function na bumuo ng node. Muli, may mga compiler, kami ay pagpunta sa magsimula sa tuktok. Ano na dapat bang sabihin ay na ako pagtawag bumuo node bago aktwal ko na ito ipinahayag. Natin bumalik sa code talagang mabilis. Mag-scroll pababa, at bang sapat, ang aking insert function ay ipinahayag sa itaas ng mga katangian ng build node, ngunit ako sinusubukan upang gamitin ang bumuo ng node sa loob ng insert. Ako pagpunta sa pumunta sa at kopya - at pagkatapos ay i-paste ang function na build node paraan hanggang dito sa tuktok. Sa ganoong paraan, sana na gagana. Natin bigyan ito ng isa pang pumunta. Ngayon ang lahat ng ito compiles. Ang lahat ng mabuti. 

Ngunit sa puntong ito, hindi namin aktwal tinatawag na aming insert function na. Lang namin malaman na ito compiles, kaya sabihin pumunta sa at ilagay ang ilang mga tawag. Natin gawin iyon sa aming pangunahing function na. Dito, hindi namin Nagkomento ang 5, 8, at 2, at pagkatapos ay hindi namin ay wire up ang mga ito down na dito. Natin gumawa ng ilang mga tawag sa isingit, at sabihin ring gamitin ang parehong uri ng mga bagay-bagay na ginamit namin kapag ginawa namin mga printf tawag upang matiyak na ang lahat ay makapag-ipinasok maayos. Ako pagpunta sa kopyahin at i-paste, at sa halip na naglalaman kami ay pagpunta sa gawin ang insert. At sa halip ng 6, 10, at 1, kami ay pagpunta sa gamitin ang 5, 8, at 2. Ito ay dapat sana isingit 5, 8, at 2 sa puno. Makatipon. Ang lahat ng mabuti. Ngayon makikita na namin ang aktwal na patakbuhin ang aming programa. 

Lahat ibinalik maling. Kaya, 5, 8, at 2 ay hindi umalis, at mukhang naglalaman ng ay hindi makita ang mga ito sa alinman. Ano kaya ang nangyari? Natin mag-zoom out. Ang unang problema ay na insert tila bumalik false, at mukhang ito tulad na dahil iniwanan namin sa aming tawag return false, at hindi namin aktwal na ibinalik totoo. Maaari naming na-set up. Ang pangalawang problema ay, ngayon kahit na ginagawa namin - i-save ang, mag-quit ito, patakbuhin gumawa muli, ito makatipon, pagkatapos patakbuhin ito - nakikita namin na ang iba pa ay nangyari dito. Ang 5, 8, at 2 ay pa rin hindi kailanman matatagpuan sa tree. Kaya, ano ang nangyayari sa? 

Natin tingnan sa ito sa code. Natin makita kung maaari naming malaman ito. Simulan namin sa mga magulang na hindi null. Itinakda namin ang kasalukuyang pointer na katumbas sa root ang pointer, at kami ay pagpunta upang gumana ang aming paraan sa pamamagitan ng puno. Kung ang kasalukuyang node ay hindi null, pagkatapos naming malaman na maaari naming ilipat ng kaunti. Itinakda namin ang aming mga magulang pointer sa katumbas sa kasalukuyang pointer, sinuri ang halaga - kung ang mga halaga sa parehong ibinalik namin ang maling. Kung ang halaga ay mas mababa namin lumipat sa kanan; kung hindi man, kami ay inilipat sa kaliwa. Pagkatapos naming bumuo ng isang node. Kukunin ko na mag-zoom sa ilang sandali. At dito, kami ay pagpunta sa subukan sa wire up ang mga halaga sa parehong. Ano kaya ang nangyari? Natin makita kung posibleng Valgrind maaaring magbigay sa amin ng isang pahiwatig. 

Gusto ko upang gamitin Valgrind lamang dahil Valgrind talagang mabilis na tumatakbo at nagsasabi sa iyo kung mayroong anumang mga memory error. Kapag nagpatakbo namin Valgrind sa code, tulad ng maaari mong makita ang kanang here--Valgrind./binary_tree--and pindutin ang enter. Nakikita mo na hindi namin ang anumang mga error sa memorya, kaya mukhang lahat okay lang sa ngayon. Mayroon kaming ilang mga paglabas ng memorya, na alam namin, dahil hindi kami nangyayari sa magbakante anumang ng aming mga node. Natin subukang tumatakbo GDB upang makita kung ano ang aktwal na pagpunta sa. Gagawin namin ang gdb. / Binary_tree. Ito booted up lamang fine. Itakda natin ang hanay ng pahinga punto sa insert. Natin patakbuhin. Mukhang namin hindi aktwal na tinatawag na insert. Mukhang ang problema ay lamang na kapag ako ay nagbago dito sa pangunahing - lahat ng mga printf tawag mula naglalaman - Hindi ko kailanman aktwal Binago ang mga tawagan insert. Ngayon sabihin bigyan ito ng isang Subukan. Natin makatipon. Mukhang mahusay na ang lahat ng doon. Ngayon sabihin subukang patakbuhin ito, tingnan kung ano ang mangyayari. Oo! Lahat mukhang medyo magandang doon. 

Ang huling bagay na isipin ang tungkol ay, Mayroon bang anumang mga gilid kaso na ito insert? At ito ay lumiliko out na, na rin, ang isang kaso gilid na ay palaging kawili-wiling upang isipin ang tungkol ay, kung ano ang mangyayari kung ang iyong mga puno ay walang laman at tawagan mo ito ipasok ang function na? Ito gumagana? Well, sabihin subukan ito. - Binary_tree c - Ang paraan namin ay pagpunta upang subukan ito, kami ay pumunta sa aming pangunahing function na, at kaysa sa mga kable mga node tulad nito, lang kami magkomento ang buong bagay, at sa halip ng mga kable up ang node ating sarili, maaari naming aktwal lamang magpatuloy at tanggalin ang lahat ng ito. Kami ay pagpunta sa gumawa ang lahat ng tawag upang ipasok. Kaya, sabihin gawin - sa halip na 5, 8, at 2, kami ay upang ipasok 7, 3, at 9. At pagkatapos ay gagamitin din namin gusto mong magpasok ng 6 pati na rin. I-save. Mag-quit. Gumawa binary puno. Ang lahat ng ito compiles. Maaari lang namin patakbuhin ito bilang at makita kung ano ang mangyayari, ngunit din ito ng pagpunta sa talagang mahalaga upang matiyak na wala kaming anumang mga error sa memorya, dahil ito ay isa sa aming mga kaso sa gilid na alam namin tungkol sa. 

Sabihin tiyakin na ito ay gumagana nang maayos sa ilalim Valgrind, na gagawin namin sa pamamagitan ng lang tumatakbo ang Valgrind. / binary_tree. Mukhang namin sa katunayan ay may isang error mula sa isang konteksto - namin ito segmentation fault. Ano ang nangyari? Valgrind aktwal na nagsasabi sa amin kung saan ito ay. Mag-zoom out ng kaunti. Mukhang ito ang nangyayari sa aming insert function na, kung saan mayroon kaming isang di-wastong read ng laki 4 sa insert, linya 60. Natin bumalik at makita kung ano ang nangyayari sa dito. Mag-zoom out talaga mabilis. Gusto ko upang matiyak na hindi ito pumunta sa gilid ng screen upang maaari naming makita ang lahat. Hilahin na sa ilang sandali. Tama. Mag-scroll pababa, at ang problema dito mismo. Ano ang mangyayari kung makuha namin down at na null ang aming kasalukuyang node ay, aming magulang na node ay null, kaya kung tinitingnan namin sa pinakatuktok, dito mismo - kung ito habang loop hindi aktwal na executes dahil ang aming kasalukuyang halaga ay null - aming ugat ay null upang kuprum ay null - pagkatapos ay ang aming mga magulang ay hindi kailanman ay makakakuha nakatakda sa kuprum o sa isang wastong halaga, kaya, ang mga magulang ay magkakaroon din null. Kailangan naming tandaan na suriin para sa ng oras na makuha namin pababa dito, at sisimulan namin ang access sa halaga ng magulang. Kaya, ano ang mangyayari? Well, kung ang magulang ay null - kung (magulang == null) - alam namin na may hindi dapat ang anuman sa tree. Kailangan naming sinusubukan upang ipasok ito sa root. Maaari naming gawin ang mga iyon sa pamamagitan ng lang set ng root na katumbas sa bagong node. Pagkatapos sa puntong ito, hindi namin aktwal gusto mong pumunta sa pamamagitan ng iba pang mga bagay. Sa halip, dito mismo, maaari naming gawin alinman sa isang iba pa-kung tao, o maaari naming pagsamahin ang lahat dito sa isang tao, ngunit dito makikita lang namin gamitin ang tao at gawin ito na paraan. Ngayon, kami ay pagpunta upang subukan upang matiyak na ang aming mga magulang ay hindi null bago at pagkatapos na aktwal na sinusubukan upang ma-access ang mga patlang. Ito ay makakatulong sa amin na maiwasan ang segmentation fault. Kaya, namin huminto, mag-zoom out, makatipon, patakbuhin. 

Walang mga error, ngunit mayroon pa rin kaming ng grupo ng mga paglabas ng memory dahil hindi namin magbakante anumang ng aming mga node. Ngunit, kung pumunta kami dito at titingnan namin sa aming printout, nakikita namin na, well, mukhang sa lahat ng aming mga pagsingit ay bumabalik na totoo, na ay mabuti. Ang mga pagsingit ay lahat ng totoo, at pagkatapos ay ang mga naaangkop na naglalaman ng mga tawag ay totoo rin. 

Mahusay! Mukhang matagumpay naming nakasulat insert. Na ang lahat ng mayroon kami para sa Pagtutukoy ng Problema Itakda sa linggong ito. Isa masaya hamon na isipin ang tungkol sa kung paano mo aktwal na pumunta sa at libreng lahat ng node sa puno. Maaari naming gawin ito ng isang bilang ng mga iba't ibang paraan, ngunit ko bang iwan na sa iyo sa eksperimento, at bilang isang masaya hamon, subukan at tiyakin na maaari mong tiyakin na ito Valgrind ulat nagbabalik walang mga error at hindi paglabas. 

Good luck sa Huffman set na ito linggo coding problema, at kami na nakikita mo sa susunod na linggo! [CS50.TV]