[Powered by Google Translate] [Sadaļa 7] [mazāk apmierināti] [Nate Hardison] [Hārvarda] [Tas ir CS50.] [CS50.TV] 

Laipni lūdzam likuma 7. Pateicoties viesuļvētru Sandy, vietā, normālas sadaļā šonedēļ, mēs darām šī arkveida, izmantojot sadaļā jautājumiem. Es esmu būs pēc kopā ar problēmu Set 6 specifikācijas, un iet cauri visiem minētajos jautājumos Nodaļa Jautājumi sadaļā. Ja ir kādi jautājumi, lūdzu, pēc tās uz CS50 apspriest. 

Alright. Pieņemsim sāktu. Šobrīd es esmu meklē no problēmas Set specifikācijā 3 lpp. Mēs ejam, lai vispirms sākt runāt par bināro koku jo tiem ir daudz svarīgas šīs nedēļas problēmu kopumu - Huffman Tree kodējumu. Viens no pašiem pirmajiem datu struktūrām, mēs runājām arī par CS50 bija masīvs. Atcerieties, ka masīvs ir secība elementi - visi tā paša tipa - uzglabā blakus viens otram atmiņā. Ja man ir veselu virkni, ka es varu izdarīt, izmantojot šo kastes numuriem-integers stilā - Pieņemsim, ka man ir 5 pirmajā ailē, man ir 7 otrajā, tad man ir 8, 10, 20 un galīgajā lodziņā. Atcerieties, ka divi patiešām labas lietas par šo masīva ir, ka mums ir šī konstante laika piekļuvi kādu konkrētu elementu  masīvā, ja mēs zinām savu indeksu. Piemēram, ja es vēlos, lai greifers trešo elementu masīvs - pie indeksu 2, izmantojot mūsu nulles balstītu indeksēšanas sistēma - Es burtiski vienkārši ir darīt vienkāršu matemātisku aprēķinu, hop uz šo pozīciju masīvā, izvelciet 8, ka tur glabājas, un es esmu labi iet. 

Viens no sliktas lietas par šo masīva - ka mēs runājām kad mēs apspriedām saistīti saraksti - ir tas, ka, ja es gribu, lai ievietotu elementu šajā masīvs, Es esmu nāksies darīt kādu novirzot apkārt. Piemēram, šis masīvs tieši šeit ir sakārtoti secībā - sakārtoti augošā secībā - 5, tad 7, tad 8, tad 10, 20 un tad - bet, ja es gribu ievietot numuru 9 šajā masīvs, Es esmu nāksies novirzīt dažus elementus, lai padarītu telpu. Mēs varam izdarīt šo šeit. Es esmu nāksies pārvietoties 5, 7, un tad 8; izveidot trūkumu, ja es varētu likt 9, un tad 10 un 20 var iet pa labi no 9 mēnešu. Tas ir sava veida sāpes, jo sliktākajā scenārijā - kad mēs esam ņemot ievietot vai nu sākumā vai beigās masīva, atkarībā no tā, kā mēs esam novirzot - mēs varētu galu galā, kam novirzīt visus elementus ka mēs pašlaik uzglabājot masīvā. 

Tātad, kāda bija ap šādā veidā? Ap šādā veidā bija doties uz mūsu Linked-saraksts metode kur - vietā, lai uzglabātu elementus 5, 7, 8, 10 un 20 visi blakus viens otram atmiņā - ko mēs tā vietā bija tika glabāt tos veida, kur mēs vēlējāmies, lai saglabātu tos Šajās Linked-sarakstā mezglu, ko es esmu zīmēšanas šeit, veida ad hoc. Un tad mēs savienotas kopā, izmantojot šīs nākamajai norādes. Es varu būt rādītāju 5-7 The, rādītājs no 7 līdz 8, rādītājs no 8 līdz 10 jaunajām dalībvalstīm, un visbeidzot, rādītājs no 10 jaunajām dalībvalstīm līdz 20 vienībām, un tad null rādītājs pie 20 vienībām, norādot, ka tur nekas pa kreisi. Kompromiss, kas mums šeit ir ir tas, ka tagad, ja mēs vēlamies ievietot numuru 9 mūsu sakārtoti sarakstā, viss, kas mums ir jādara, ir izveidot jaunu mezglu ar 9, vadu to līdz norādīt uz atbilstošu vietu, un pēc tam atkārtoti vadu 8 norādīt līdz 9 mēnešu. Tas ir diezgan ātri, pieņemot mēs zinām, kur tieši mēs vēlamies ievietot 9. Bet kompromiss apmaiņā tas, ka mēs esam tagad zaudējuši pastāvīga laika piekļuvi uz kādu konkrētu elementu mūsu datu struktūru. Piemēram, ja es vēlos, lai atrastu ceturto elements šajā saistītajā sarakstā, Es esmu nāksies sākt jau pašā sākumā saraksta un strādāt manu ceļu cauri skaitīšanas mezglā-by-mezglā līdz es atrast ceturtais. 

Lai iegūtu labāku piekļuvi sniegumu nekā saistīts saraksts - bet arī saglabāt dažas no priekšrocībām, kas mums bija izteiksmē ievietošanas laika no saistītajā sarakstā - binārs koks gatavojas nepieciešams izmantot mazliet vairāk atmiņas. Jo īpaši, nevis tikai ar vienu rādītāju bināru koku mezglu - piemēram Linked-sarakstā mezglu dara - mēs esam gatavojas pievienot otru rādītāju uz bināro koku mezglā. Nevis tikai ar vienu rādītāju uz nākamo elementu, mēs esam nāksies rādītāju uz kreiso bērnu un pareizā bērnu. 

Pieņemsim uzzīmēt, lai redzētu, kas patiesībā izskatās. Atkal, es esmu gatavojas izmantot šīs kastes un bultas. Binārs koks mezgls sākt ar pavisam vienkāršu kastē. Tas notiek, lai būtu telpu vērtību, un tad tas ir arī nāksies telpu kreisajā bērnu un labo bērnu. Es esmu gatavojas marķēt tos šeit. Mēs ejam, lai būtu kreiso bērnu, un tad mēs ejam, lai ir tiesības bērnu. Ir daudz dažādi veidi, kā to izdarīt. Dažreiz telpu un ērtības, Es tiešām izdarīt to kā es esmu dara šeit apakšā kur es esmu nāksies vērtību augšā, un tad tiesības bērns uz grunts labi, un kreiso bērns uz apakšējā kreisajā. Dodas atpakaļ uz šo top diagrammu, Mums ir vērtība pašā augšā, tad mums ir kreisās bērnu rādītāju, un tad mums ir tiesības un bērnu rādītāju. 

Jo problēma Set specifikāciju, mēs runājam par zīmēšanas mezglu, kas ir vērtība 7, un tad kreisās bērns rādītājs, kas ir spēkā, un labo bērns rādītājs, kas ir nulle. Mēs varam vai nu rakstīt kapitāla NULL telpā uz gan kreisajā bērns un labi bērnam, vai arī mēs varam izdarīt šo slīpsvītra caur katru no kastes, lai norādītu, ka tā ir null. Es esmu gatavojas darīt, ka tikai tāpēc, ka ir vienkāršāk. Ko jūs redzat šeit ir divi veidi, kā diagrammu ļoti vienkāršu bināru koku mezglu kur mums ir vērtība 7 un Null bērnu norādes. 

Otrā daļa no mūsu parametri runā par to, kā ar saistītas sarakstiem - Atcerieties, mums bija tikai turēt uz pašu pirmo elementu sarakstā atcerēties visu sarakstu - un tāpat, ar bināru koku, mums ir tikai turēt uz vienu rādītāju uz koku lai saglabātu kontroli pār visu datu struktūru. Šis īpašais elements koka sauc sakne mezgla koka. Piemēram, ja tas viens mezgls - tas mezgls satur vērtību 7 ar Null kreisās un labās bērnu šautru - bija vienīgais vērtību mūsu koku, tad tas būtu mūsu saknes mezgla. Tas ir pats sākums mūsu koku. Mēs varam redzēt šo mazliet precīzāk, tiklīdz mēs sākt pievienot vairāk mezglu mūsu koku. Ļaujiet man uzvilkt jaunu lapu. 

Tagad mēs esam gatavojas izdarīt koks, kas ir 7 saknē, un 3 iekšpusē kreisajā bērnu, un 9 iekšpusē labajā bērnu. Atkal, tas ir diezgan vienkārši. Mēs esam ieguvuši 7, izdarīt mezglu 3, mezglā 9, un es esmu gatavojas noteikt kreiso bērnu rādītāju no 7, lai norādītu uz mezglā ir 3, un tiesības bērna rādītājs no mezgla ar 7 uz mezglu, kas satur 9. Tagad, jo 3 un 9 nav nekādas bērnus, mēs esam gatavojas noteikt visas savas bērnu norādes būt nulle. Lūk, mūsu koka sakne atbilst mezglu satur numuru 7. Jūs varat redzēt, ka, ja viss, kas mums ir, ir rādītājs uz šo saknes mezgla, tad mēs varam staigāt pa mūsu koku un piekļūt gan bērnu mezgliem - gan 3 un 9. Nav nepieciešams, lai uzturētu norādes uz katru mezglu uz koku. Alright. Tagad mēs esam gatavojas pievienot citu mezglu, lai šīs shēmas. Mēs ejam, lai pievienotu mezglu satur 6, un mēs esam gatavojas pievienot to kā labo bērns mezglā satur 3. Lai to izdarītu, es esmu gatavojas dzēst šo null rādītāju 3-mezglu un vadu to līdz norādīt uz mezglu, kas satur 6. Alright. 

Šajā brīdī, iesim pa mazliet terminoloģiju. Lai sāktu, tāpēc, ka tas ir sauc bināro koku jo īpaši ir tas, ka ir divas bērnu norādes. Ir arī citi veidi, koku, kas ir vairāk bērnu norādes. Jo īpaši, jūs "izmēģināt", kas Problem Set 5. Jūs pamanīsiet, ka šajā izmēģināt, jums bija 27 dažādas norādes uz dažādiem bērniem - viens katrai no 26 burtiem angļu alfabētā, un tad 27. par apostrofam - tā, ka ir līdzīga tipa koka. Bet šeit, jo tas ir bināro, mums ir tikai divas bērnu norādes. 

Papildus šim saknes mezgla ka mēs runājām par, mēs esam arī throwing ap šī termina "bērns". Ko tas nozīmē viens mezgls būtu bērns citu mezglu? Tas burtiski nozīmē, ka bērns mezgls ir bērns citu mezglu ja cits mezgls ir viens no tās bērnu norādes, kas, lai norādītu uz šo mezglu. Lai to īstenotu vēl konkrēti, ja 3 norādīja uz viena no bērnu norādes 7, tad 3 ir bērns gada 7. Ja mēs izdomāt ko gada 7 bērni - labi, mēs redzam, ka 7 ir rādītāju uz 3 un rādītāju uz 9, tik 9 un 3 ir bērni 7. Deviņi nav bērni, jo tās bērnam norādes ir Null, un 3 ir tikai viens bērns, 6. Seši nav arī bērni, jo gan tās norādes ir nulle, ko mēs izdarīt jau tagad. 

Bez tam, mēs arī runājam par konkrētu mezglu vecākiem, un tas ir, kā jūs gaidījāt, reversā šī bērna aprakstu. Katrs mezgls ir tikai viens no vecākiem - nevis divi, kā jūs varētu gaidīt ar cilvēkiem. Piemēram, no 3 mātes ir 7. Gada 9 vecākiem ir arī 7 un 6 vecākiem ir 3. Nav daudz uz to. Mums ir arī terminus, lai runātu par vecvecākiem un mazbērniem, un vispār mēs runājam par senčiem un pēcnācēji konkrētā mezglā. Sencis mezglu - vai senči, drīzāk, no mezgla - ir visi mezglu, kas atrodas uz ceļa no saknes uz šo mezglu. Piemēram, ja es esmu meklē mezglu 6, tad senči ir būs gan 3 līdz 7. No 9 senči, piemēram, ir - ja es esmu meklē mezglu 9 - tad gada 9 sencis ir tikai 7. Un pēcnācēji ir tieši otrādi. Ja es gribu, lai apskatīt visu par 7 pēcnācējiem, tad man ir jāskatās uz visu zem tā mezgliem. Tātad, man ir 3, 9, 6 un visi kā pēcteči 7. 

Galīgā termiņa, ka mēs runājam par to ir šis jēdziens ir brālis. Vecvecākus - veida seko līdzi šiem ģimenes nosacījumiem - ir mezgli, kas ir tajā pašā līmenī koku. Tātad, 3 un 9 ir brāļi un māsas, jo tie ir tajā pašā līmenī koku. Viņiem abiem ir tādas pašas mātes, 7. 6 nav brāļi un māsas, jo 9 Vai nav bērnu. Un 7 nav nekādas vecvecākus, jo tas ir galvenais mūsu koku, un tur ir tikai kādreiz 1 sakne. 7 līdz būt vecvecākus tur būtu jābūt mezglā virs 7. Tur būtu jābūt vecākiem par 7, jo tādā gadījumā 7 vairs nebūs sakne no koka. Tad ka jaunā mātes gada 7 būtu arī jābūt ar bērnu, un ka bērns tad būtu sibling gada 7. 

Alright. Pārvietojas on. Kad mēs sākām mūsu diskusija par bināro koku, Mēs runājām par to, kā mēs gatavojamies izmantot tos, lai iegūt priekšrocības pār gan masīvu un saistīto saraksti. Un kā mēs esam gatavojas darīt, ir ar šo pasūtīšanas īpašumu. Mēs sakām, ka bināro koks ir pasūtīts, saskaņā ar specifikāciju, ja par katru mezglu mūsu koku, visi tās pēcnācēji, no kreisās - kreisi bērns un visa kreisā bērna pēctečiem - ir mazāk vērtības un visu uz tiesībām mezglu - tiesības bērnam un visas tiesības bērna pēctečiem - ir mezglu lielākas nekā vērtība pašreizējās mezglā ka mēs esam meklē. Tikai pēc vienkāršības, mēs esam gatavojas pieņemt, ka tajā nav dublēt mezgli mūsu koku. Piemēram, šajā kokā mēs nebrauksim, lai risinātu ar lietu kur mums ir vērtība 7 pie saknes  un tad mums ir arī vērtība 7 citur koku. Šajā gadījumā, jūs pamanīsiet, ka šis koks ir patiesi pasūtīts. Mums ir vērtība 7 pie saknes. Viss pa kreisi no 7 - ja es atsaukt visus šos maz zīmju šeit - viss pa kreisi no 7 - 3 un 6 - šīs vērtības ir gan mazāk nekā 7, un viss pa labi - kas ir tikai šāda 9 - ir lielāks par 7. 

Tas ir ne tikai lika koks satur šīs vērtības, bet pieņemsim izdarīt vēl dažus no tiem. Ir tiešām viss ķekars veidiem, ka mēs varam darīt. Es esmu gatavojas izmantot stenogrāfija tikai, lai saglabātu lietas vienkārši, ja - nevis zīmēšanas veic visa kastes-un-bultiņām - Es esmu tikai gatavojas izdarīt numurus un pievienot bultas, kas tos savieno. Lai sāktu, mēs vienkārši uzrakstīt savu sākotnējo koku atkal, ja mums bija 7, un tad 3, un tad 3 norādīja atpakaļ uz tiesībām uz 6, un 7 bija tiesības bērns, kas bija 9. Alright. Kas ir vēl viens veids, ka mēs varētu uzrakstīt šo koku? Vietā, 3 kurām kreiso bērns 7, mēs varētu arī būt 6 kurām kreiso bērns 7, un tad 3 kurām kreiso bērns 6. Tas izskatās šī koka tepat kur man 7, tad 6, tad 3, un par tiesībām 9. Mēs arī nav jābūt ar 7 kā mūsu saknes mezgla. Mēs varētu arī būt 6 kā mūsu saknes mezgla. Kas būtu, ka izskatās? Ja mēs spēsim saglabāt šo pasūtīts īpašumu, viss pa kreisi no 6, ir mazāks nekā to. Ir tikai viena iespēja, un tas ir 3. Bet tad kā labo bērns 6, mums ir divas iespējas. Pirmkārt, mēs varētu būt 7 un tad 9, vai mēs varētu izdarīt to - piemēram, es esmu par to darīt šeit - kur mums ir 9 kā labo bērns 6, un tad 7, kā kreisajā bērnu 9 mēnešu. 

Tagad, 7 un 6 ir ne tikai iespējamās vērtības saknes. Mēs varētu arī ir 3 būt saknes. Kas notiek, ja 3 ir pie saknes? Lūk, lietas iegūt mazliet interesanti. Trīs nav nekādas vērtības, kas ir mazāk nekā to, lai viss kreisajā pusē koks ir tikai būs nulle. Tur nav būs kaut tur. Pa labi, mēs varētu saraksts lietas augošā secībā. Mēs varētu būt 3, 6 tad, tad 7, tad 9. Vai mēs varētu darīt 3, tad 6, tad 9, tad līdz 7. Vai mēs varētu darīt 3, tad 7, tad 6, tad 9. Vai, 3, 7 - patiesībā nē, mēs nevaram darīt 7 vairs. Tas ir mūsu viena lieta tur. Mēs varam darīt 9, un tad no 9 mēs varam darīt 6 un tad līdz 7. Vai arī mēs varam darīt 3, tad 9, tad 7, un tad 6. 

Viena lieta, lai pievērstu Jūsu uzmanību šeit ir ka šie koki ir mazliet dīvaini izskata. Jo īpaši, ja mēs skatāmies uz 4 kokiem labajā pusē - Es aplis viņiem, šeit - šie koki izskatās gandrīz tieši tāpat saistītajā sarakstā. Katrs mezgls ir tikai viens bērns, un tāpēc mums nav kāds no šīs koka līdzīgu struktūru, ka mēs redzam, piemēram,  šajā vienā vientuļo koku nekā šeit uz apakšējā kreisajā pusē. Šie koki ir faktiski aicināja izvirst bināro koku, un mēs runājam par šiem vairāk nākotnē - it īpaši, ja jūs doties uz veikt citus datorzinātņu kursus. Šie koki ir izdzimtenis. Viņi nav ļoti noderīgs, jo, protams, šī struktūra pakļauj sevi  lai uzmeklēšanas reizes līdzīgi tā saistītajā sarakstā. Mums nav nokļūt izmantot papildu atmiņu - šo papildu rādītāju - jo mūsu struktūras ir slikti šādā veidā. Nevis iet un izņemt bināro koku, kas ir 9 saknē, kas ir pēdējais gadījums, ka mēs būtu, mēs esam vietā, šajā brīdī, gatavojas runāt mazliet par šo citu terminu ka mēs izmantojam, runājot par kokiem, ko sauc augstums. 

Par koku augstums ir attālums no saknes līdz visvairāk tālā mezglā, vai drīzāk skaitu apiņu, kas jums būs darīt, lai sākas no saknes, un tad galu galā pie visvairāk tālā mezglu koku. Ja mēs apskatīt dažus no šiem kokiem, ka mēs esam izdarīt tieši šeit, mēs varam redzēt, ka, ja mēs šo koku augšējā kreisajā stūrī, un mēs sākam pie 3, tad mums ir, lai 1 hop nokļūt 6, otrs hop nokļūt līdz 7, un trešo hop nokļūt 9 mēnešu. Tātad, šī koka augstums ir 3. Mēs varam darīt to pašu izmantot citu kokiem izklāstīti ar šo zaļo, un mēs redzam, ka no visiem šiem kokiem augstums ir arī patiešām 3. Tas ir daļa, kas padara viņus deģenerāts - ka to augstums ir tikai viens mazāks nekā skaits mezglu visu koku. Ja mēs skatāmies uz šo citu koku, kas ir apņemta ar sarkanu, no otras puses, mēs redzam, ka lielākā daļa tālā lapu mezgli ir 6, 9 - atstāj šo ziņu mezgli, kurām nav bērnu. Tātad, lai iegūtu no saknes mezgla nu 6 vai 9, mums ir, lai viens apiņu nokļūt līdz 7 un tad otro hop nokļūt 9, un tāpat, tikai otrais apiņu no 7 līdz nokļūt 6. Tātad, no šī koka augstums nekā šeit ir tikai 2. Jūs varat doties atpakaļ un darīt, ka visi citi koki, ka mēs iepriekš apspriests sākot ar 7, 6, un jūs atradīsiet, ka no visiem šiem kokiem augstums ir arī 2. 

Iemesls, kāpēc mēs esam runājuši par pasūtīts bināro koku un kāpēc viņi foršs, jo jūs varat meklēt, izmantojot tām ļoti līdzīgi kā meklējot pa šķiroto masīvs. Tas ir, ja mēs runājam par kļūst, ka uzlabota uzmeklēšanas laiks pār vienkāršu saistīts saraksts. Ar saistīts saraksts - ja jūs vēlaties atrast konkrētu elementu - Jūs esat pie vislabāk gatavojas darīt kaut kādas lineārās meklēšanas kur jūs sākat sākumā saraksta un apiņu vienu pēc otras - viens mezgls ar vienu mezglu - pa visu sarakstu, līdz jūs atradīsiet ko jūs meklējat. Tā kā, ja jums ir bināro koku, kas glabājas šajā jauka formātā, Jūs faktiski var iegūt vairāk par bināro meklēšanu notiek kur tu skaldi un valdi un meklēt, izmantojot atbilstošu pusē koku pie katra soļa. Let 's redzēt, kā kas darbojas. 

Ja mums ir - atkal dodas atpakaļ uz mūsu sākotnējā koku - Mēs sākas 7, mums ir 3 pa kreisi, 9 par tiesībām, un zem 3 Mums ir 6. Ja mēs gribam, lai meklētu numuru 6 šajā kokā, mēs gribētu sākt saknē. Mēs varētu salīdzināt vērtību mēs meklējam, teiksim 6, ar vērtību glabājas mezglā, ka mēs pašlaik meklē, 7, Ierīce 6 ir patiešām mazāk nekā 7, tāpēc mēs gribētu pārcelties uz kreiso pusi. Ja gada 6 vērtība bija lielāka nekā 7, mēs būtu tā vietā pārvietots pa labi. Jo mēs zinām, ka - sakarā ar struktūru mūsu pasūtīto bināro koku - visas vērtības mazāk nekā 7 gatavojas glabāt pa kreisi no 7, nav nepieciešams pat apnikt meklē caur labajā pusē no koka. Kad mēs pāriet uz kreiso pusi, un mēs esam tagad pie mezglā ir 3, mēs varam darīt to pašu salīdzinājumu atkal, ja mēs salīdzinām 3 un 6. Un mēs redzam, ka, lai gan 6 - vērtība, mēs meklējam - ir lielāks par 3, mēs varam iet uz labo pusi mezglu satur 3. Nav kreisā puse šeit, lai mēs varētu neņemt vērā to. Bet mēs tikai zinām, ka tāpēc, ka mēs esam apskatot koku pati, un mēs varam redzēt, ka koks nav bērni. 

Tas ir arī diezgan viegli uzmeklēt 6 Šajā kokā, ja mēs darām to sevi par cilvēkiem, bet pieņemsim sekot šim procesam mehāniski, piemēram, datoru varētu darīt lai tiešām saprastu algoritmu. Šajā brīdī, mēs šobrīd meklē mezglu, kas satur 6, un mēs meklējam vērtību 6, tik tiešām, mēs esam atraduši piemērotu mezglā. Mēs atradām vērtība 6 mūsu koku, un mēs varam apturēt mūsu meklēšanu. Šajā brīdī, atkarībā no tā, kas notiek, mēs varam teikt, jā, mēs esam atraduši vērtību 6, tā pastāv mūsu koku. Vai, ja mēs plānojam ievietot mezglu vai darīt kaut ko, mēs varam darīt, ka šajā brīdī. 

Darīsim pāris vairāk lookups tikai, lai redzētu, kā tas darbojas. Apskatīsim, kas notiek, ja mēs mēģinātu meklēt vērtību 10. Ja mēs meklēt vērtību 10, mēs varētu sākt saknē. Mēs gribētu redzēt, ka 10 ir lielāks par 7, tāpēc mēs gribētu pārcelties uz labo pusi. Mēs gribētu nokļūt 9 mēnešu un salīdzināt 9-10 AND redzēt, ka 9 patiešām mazāk nekā 10. Tātad vēlreiz, mēs gribētu mēģināt pāriet uz labo pusi. Bet šajā brīdī, mēs paziņojums, ka mēs esam pie Null mezglā. Tur nekā nav. Tur nekas, kur 10 jābūt. Tas ir, ja mēs varam ziņot neveiksmi - ka patiešām nav kokā 10. Un visbeidzot, iesim cauri ja mēs cenšamies meklēt 1 no koka. Tas ir līdzīgi tam, kas notiek, ja mēs skatāmies uz augšu 10, izņemot nevis doties pa labi, mēs gatavojamies iet pa kreisi. Mēs sākas 7 un redzēt, ka 1 ir mazāks nekā 7, tāpēc mēs pāriet uz kreiso pusi. Mēs nokļūt 3 un redzēt, ka 1 ir mazāks par 3, lai atkal mēs cenšamies, lai pārvietotos pa kreisi. Šajā brīdī mums ir null mezglā, lai atkal mēs varam ziņot neveiksmi. 

Ja jūs vēlaties uzzināt vairāk par bināro koku, tur ir viss ķekars fun maz problēmas, kas jūs varat darīt ar tiem. Es iesaku praktizē zīmējumu no šīm diagrammām vienu pēc otras un pēc caur visiem dažādos posmos, jo tas nāk super-ērts ne tikai tad, kad jūs darāt Huffman kodēšanas problēmu kopumu bet arī turpmākās kursos - tikai mācīties, kā izdarīt šos datu struktūras un domāt ar problēmām ar pildspalvu un papīru vai, šajā gadījumā, iPad un spalvai. 

Šajā brīdī, lai gan, mēs spēsim virzīties uz darīt kādu kodēšanas praksi un faktiski spēlē ar šiem bināriem kokiem un redzēt. Es esmu gatavojas pāriet atpakaļ uz manu datoru. Šajā daļā sadaļā, nevis izmantojot CS50 Run vai CS50 Spaces, Es esmu gatavojas izmantot ierīci. 

Pēc kopā ar šo problēmu Set specifikāciju, Es redzu, ka es esmu vajadzēja atvērt ierīci, dodieties uz manu Dropbox mapi, izveidot mapi sauc 7.pants, un pēc tam izveidot failu sauc binary_tree.c. Šeit mēs iet. Man ierīce jau ir atvērts. Es esmu gatavojas uzvilkt terminālu. Es iešu uz Dropbox mapi, lai direktoriju sauc section7, un redzu, tas ir pilnīgi tukšs. Tagad es esmu gatavojas atvērt binary_tree.c. Alright. Šeit mēs aiziet - tukšu failu. 

Iesim atpakaļ uz specifikācijai. Specifikācija prasa izveidot jaunu tipa definīciju par bināro koku mezglu satur int vērtības - tāpat kā vērtības, kas mums izvilka jo mūsu diagrammu iepriekš. Mēs ejam, lai izmantotu šo tekstveidnes typedef ka mēs esam darījuši šeit ka jums vajadzētu atpazīt no Problem Set 5 - ja jūs hash tabulas ceļu iekarošana Speller programmā. Jums vajadzētu arī atzīt to no pagājušās nedēļas sadaļā kur mēs runājām par saistītas sarakstiem. Mēs esam ieguvuši šo typedef no struct mezglā, un mēs esam dota šī struct mezglā šo vārdu struct mezglā pirms tam rūpīgi lai mēs varētu tad uz to, jo mēs vēlamies, lai būtu struct mezglā norādes kā daļu no mūsu struct, bet mēs esam tam apkārt šo - vai drīzāk, liktas šo - jo typedef tā ka, vēlāk kodu, mēs varam atsaukties uz šo struct kā tikai mezglu, nevis struct mezglā. 

Tas būs ļoti līdzīgs atsevišķi saistītās saraksta definīcijas, ka mēs redzējām pagājušajā nedēļā. Lai to izdarītu, pieņemsim tikai sākt ar izrakstīšanas tekstveidnes. Mēs zinām, ka mums ir jābūt veselam skaitlim vērtība, tāpēc mēs nodot int vērtību, un pēc tam tā vietā, tikai vienu rādītāju uz nākamo elementu - kā mēs to darījām ar atsevišķi saistītiem sarakstiem - mēs ejam, lai būtu labi un kreisi bērnu norādes. Tas ir diezgan vienkārši pārāk - struct mezglā * kreisi bērns; un struktūrai mezglu * labi bērns;. Atdzist. Tas izskatās diezgan labs sākums. Iesim atpakaļ uz specifikācijai. 

Tagad mums ir nepieciešams deklarēt globāla mezglu * mainīgo, lai saknes koku. Mēs ejam, lai padarītu šo globālo tāpat kā mēs tos vispirms rādītāju mūsu saistīts sarakstā arī pasaules. Tas bija tā, ka funkcijas, ko mēs rakstīt mums nav, lai saglabātu iet ap šo sakni - gan mēs redzēsim, ka, ja jūs vēlaties rakstīt šīs funkcijas rekursīvi, tas varētu būt labāk, lai nav pat iet tā apkārt kā globāla pirmajā vietā un tā vietā sāktu to lokāli savā galvenā funkcija. Bet, mēs darīsim to globāli, lai sāktu. Atkal, mēs sniegsim pāris telpās, un es esmu gatavojas pasludināt mezglu * saknes. Tikai, lai pārliecinātos, ka man nav atstāt šajā neinicializēts, es esmu gatavojas noteikt to vienāds ar null. Tagad, galvenā funkcija - ko mēs rakstīt ļoti ātri šeit - int galvenais (int argc, const char * argv []) - un es esmu gatavojas sākt deklarējot savu argv masīvs kā const tikai tāpēc, ka es zinu ka šie argumenti ir argumenti, ka es, iespējams, nevēlas mainīt. Ja es gribu, lai tos grozīt man būtu iespējams padarīt to kopijas. Jūs redzēt šo partiju kodu. Tas ir jauki, vai nu veidā. Tas ir jauki, lai atstāt to kā - neveikt const ja vēlaties. Es parasti likt to tikai tāpēc, ka es sev atgādinu  ka es, iespējams, nevēlaties mainīt šos argumentus. 

Kā vienmēr, es esmu gatavojas iekļaut šo atpakaļ 0 līnijas beigās galvenais. Lūk, es sāktu savu saknes mezgla. Kā tas ir tagad, es esam ieguvuši rādītāju, kas ir iestatīts uz null, tāpēc tas ir pavērsts neko. Lai faktiski sākt ēkas mezglā, Man vispirms ir piešķirt atmiņu par to. Es esmu gatavojas darīt, ka, veicot atmiņas par kaudzes, izmantojot malloc. Es esmu gatavojas noteikt saknes vienāds ar rezultātu malloc, un es esmu gatavojas izmantot sizeof operators aprēķina lielumu mezglā. Iemesls, ka es izmantot sizeof mezgla pretstatā, teiksim, kaut kas līdzīgs šim - malloc (4 + 4 +4) vai malloc 12 - ir tāpēc, ka es vēlos, lai mana koda būt iespējamā savienojamība. Es gribu, lai varētu izmantot šo. C failu, apkopo to uz ierīces, un tad sastādīt to par manu 64-bit Mac - vai uz pavisam citu arhitektūru - un es gribu šo visu darbu pats. 

Ja es esmu padarot pieņēmumus par lielumu mainīgie - lielumu int vai par rādītāju lielumu - tad es esmu arī izdarīt pieņēmumus par to arhitektūru veidiem par kuru mans kods var veiksmīgi sastādīt kad rādīt. Vienmēr izmantot sizeof pretstatā manuāli summējot struct laukus. Otrs iemesls ir tas, ka tur varētu būt arī polsterējums, ka kompilators liek uz struct. Pat tikai summējot atsevišķu lauku nav kaut kas jūs parasti vēlas darīt, tāpēc, izdzēsiet šo līniju. Tagad, lai patiešām sāktu šo saknes mezgla, Es esmu nāksies plug vērtības katrā no dažādām jomām. Piemēram, par vērtību es zinu, es gribu, lai sāktu 7, un tagad es esmu gatavojas noteikt kreisi bērnam būt Null un tiesības bērnam arī būt nulle. Lieliski! Mēs esam darījuši, ka daļa no spec. 

Specifikācija leju apakšā 3 lapas man prasa, lai radītu vēl trīs mezglus - viens, kas satur 3, viens, kas satur 6, viens un 9 - un tad stiepļu tos uz augšu, lai tas izskatās tieši tāpat kā mūsu koku diagrammu ka mēs runājām par agrāk. Darīsim ka diezgan ātri šeit. Jūs redzēsiet patiešām ātri, ka es esmu gatavojas sākt rakstīt ķekars dublikātu kodu. Es esmu gatavojas izveidot mezglu * un es esmu gatavojas saukt trīs. Es esmu gatavojas noteikt to vienāds ar malloc (sizeof (mezgls)). Es esmu gatavojas noteikt triju> Value = 3. Trīs -> left_child = NULL; trīs -> labo _child = NULL; kā arī. Kas izskatās diezgan līdzīgs inicializēšana saknes, un tas ir tieši tas, ko Es esmu nāksies darīt, ja es sāktu inicializējot 6 un 9, kā arī. Es darīšu, ka tiešām ātri šeit - patiesībā, es esmu gatavojas darīt nedaudz kopēt un ielīmēt, un pārliecinieties, ka es - alright.  Tagad man to nokopēt un es varētu iet uz priekšu un noteikt šī vienāds ar 6. Jūs varat redzēt, ka tas aizņem awhile un nav super-efektīvas. Tikai mazliet, mēs rakstīt funkciju, kas to dara par mums. Es gribu, lai aizstātu šo ar 9, nomainiet ka ar 6. 

Tagad mēs esam ieguvuši visas mūsu mezglu izveidota un inicializēts. Mēs esam ieguvuši mūsu saknes noteikts vienāds ar 7, vai satur vērtību 7, Mūsu mezglā ir 3, mūsu mezgls satur 6, un mūsu mezglu, kas satur 9. Šajā brīdī, viss, kas mums ir jādara, ir stieples viss uz augšu. Iemesls es inicializēts visas norādes uz null, ir tikai tāpēc, ka es pārliecinos, ka Man nav nekādas neinicializēts norādes ar tur nejauši. Un arī tā, šajā brīdī, man ir tikai faktiski savienotu mezglu ar otru - uz tiem, kas viņi patiesībā savienotas - Man nav iet cauri un padarīt pārliecinieties, ka visas nulls ir tur piemērotās vietās. 

Sākot saknē, es zinu, ka sakne ir kreisā bērns ir 3. Es zinu, ka sakne tiesības bērns ir 9. Pēc tam, vienīgais bērns, kas man ir pa kreisi, lai jāuztraucas par ir 3 tiesības bērns, kas ir 6. Šajā brīdī, tas viss izskatās diezgan labi. Mēs izdzēstu dažas no šīm līnijām. Tagad viss izskatās diezgan labi. Iesim atpakaļ uz mūsu specifikācijām un redzēt, kas mums ir jādara nākamo. 

Šajā brīdī, mums ir rakstīt sauc funkciju "satur" ar prototipu "bool satur (int vērtība)". Un tas satur funkcija ir gatavojas atgriezties true  ja koku mūsu globālo saknes mainīgā norādīja  satur vērtību pārgāja funkciju un viltus citādi. Iesim uz priekšu un darīt. Tas būs tieši tāpat lookup ka mums bija ar roku uz iPad tikai nedaudz atpakaļ. Pieņemsim tuvinātu atpakaļ mazliet un ritiniet uz augšu. Mēs ejam, lai šo funkciju tieši virs mūsu galvenā funkcija tāpēc, ka mums nav jādara jebkādu prototipu. Tātad, bool satur (int vērtība). Tur mums iet. Tur ir mūsu tekstveidnes deklarācija. Tikai, lai pārliecinātos, ka tas apkopo, Es iešu uz priekšu un vienkārši noteikt to vienāds atgriezties viltus. Tieši tagad šī funkcija vienkārši nevar darīt neko, un vienmēr ziņo, ka vērtību, ko mēs meklējam, nav kokā. 

Šajā brīdī, tas ir iespējams, laba ideja - jo mēs esam rakstiski visu ķekars kodu un mums nav pat mēģinājuši testēšana vēl - lai pārliecinātos, ka tas viss apkopo. Ir lietas, kas mums ir jādara, lai pārliecinātos, ka tas patiešām apkopo pāris. Pirmkārt, vai mēs esam izmantojuši kādas funkcijas jebkuros bibliotēkās, ka mēs vēl neesam iekļauti. Funkcijas mēs esam, ko līdz šim ir malloc, un tad mēs esam arī izmanto šāda veida - šo nestandarta veida sauc par "bool' - kas ir iekļauta standarta bool header failu. Mēs noteikti vēlamies iekļaut standarta bool.h par bool tipa, un mēs arī vēlamies # ietvert standarta lib.h par standarta bibliotēkām kas ietver malloc un bezmaksas, un visi no tā. Tātad, zoom out, mēs ejam, lai izietu. Pamēģināsim un pārliecinieties, ka tas tiešām bija sastādīt. Mēs redzam, ka tas tā ir, tāpēc mēs esam uz pareizā ceļa. 

Pieņemsim atvērt binary_tree.c atkal. Tā apkopo. Iesim uz leju un pārliecinieties, ka mēs ievietot dažas zvanus uz mūsu Satur funkciju - tikai, lai pārliecinātos, ka viss ir labi un labs. Piemēram, ja mēs kādu lookups mūsu koku agrāk, mēs mēģināja uzzināt vērtības 6, 10, 1 un, un mēs zinājām, ka 6 bija kokā, 10 bija nevis no koka, un 1 nebija kokā nu. Pieņemsim izmantot šos paraugus zvanus, kā veids, lai noskaidrotu, vai nav Mūsu Satur funkcija darbojas. Lai to izdarītu, es esmu gatavojas izmantot printf funkciju, un mēs esam gatavojas izdrukāt rezultātu aicinājumu satur. Es esmu gatavojas īstenot virkni "satur (% d) = jo  mēs ejam uz kontaktdakšu vērtībā ka mēs ejam meklēt, un =% s \ n "un izmantot to kā mūsu formāta virknes. Mēs esam tikai gatavojas, lai redzētu - burtiski izdrukāt uz ekrāna - kāda izskatās funkciju zvanu. Tas nav reāli funkcija zvans.  Tas ir tikai virkne paredzēti, lai izskatās funkciju zvanu. 

Tagad mēs esam gatavojas plug vērtībām. Mēs ejam, lai mēģinātu satur gada 6, un tad ko mēs gatavojamies darīt, šeit ir izmantot šo trīskāršo operators. Pieņemsim redzēt - satur 6 - tāpēc, tagad es esmu iekļauts 6 un ja ir 6 ir taisnība, virkne, kas mēs esam gatavojas sūtīt uz% s formātā rakstura būs virkne "patiess". Pieņemsim ritināt pa mazliet. Pretējā gadījumā mēs vēlamies, lai nosūtītu virkne "viltus", ja ir 6 atdevi viltus. Tas ir maz dumjš izskata, bet es skaitlis es varētu arī ilustrētu ko trīskāršo operators izskatās, jo mēs neesam redzējuši to awhile. Tas būs jauks, ērts veids, lai noskaidrotu, vai mūsu Satur funkcija darbojas. Es esmu gatavojas ritināt atpakaļ pāri pa kreisi, un es esmu gatavojas kopēt un ielīmēt šo līniju pāris reizes. Tas mainīja dažas no šīm vērtībām apkārt, tāpēc šī būs 1, un tas būs 10. 

Šajā brīdī mēs esam ieguvuši jauku satur funkciju. Mēs esam ieguvuši dažas pārbaudes, un mēs redzēsim, ja tas viss darbojas. Šajā brīdī mēs esam rakstiski dažas vairāk kodu. Laiks atmest, un pārliecinieties, ka viss vēl apkopo. Atmest, un tagad pieņemsim mēģināt padarīt bināro koku vēlreiz. Nu, izskatās, ka mēs esam ieguvuši kļūda, un mēs esam ieguvuši šo skaidri deklarējot bibliotēkas funkciju printf. Izskatās, ka mums ir nepieciešams, lai iet un # ietvert standardio.h. Un ar to, viss būtu jāapkopo. Mēs visi esam labi. Tagad pamēģināsim darbojas bināro koku un redzēt, kas notiek. Šeit mēs esam,. / Binary_tree, un mēs redzam, ka, kā mēs gaidīts - jo mēs esam nav īstenots satur vēl, vai drīzāk, mēs esam tikai likts pretī viltus - mēs redzam, ka tā ir tikai atgriežas viltus visiem tiem, lai viss strādā lielākoties diezgan labi. 

Iesim atpakaļ un faktiski īstenot satur šajā brīdī. Es esmu gatavojas, lai ritinātu uz leju, tuvinātu, un - atcerieties, algoritms, ka mēs izmantojām bija tas, ka mēs sākām pie saknes mezgla un tad katrā mezglā ka mēs saskaramies, mēs salīdzinājumu, un, pamatojoties uz šo salīdzinājumu, mēs vai nu pāriet uz kreiso bērnam vai uz labo bērnam. Tas ir gatavojas izskatās ļoti līdzīgi bināro meklēšanas kodu, kas mums rakstīja agrāk termiņā. Kad mēs sāktu, mēs zinām, ka mēs vēlamies, lai turēt uz pašreizējo mezglu ka mēs esam apskatot, un pašreizējā mezglā tiks inicializēts uz saknes mezgla. Un tagad mēs esam gatavojas glabāt iet caur koku, un atcerēties, ka mūsu apstāšanās nosacījumu -  kad mēs faktiski strādāja ar piemēru ar roku - bija, kad mēs saskārāmies ar null mezglā, nevis kad mēs paskatījās Null bērnu, bet, kad mēs faktiski pārcēlās uz mezglu kokā un konstatēja, ka mēs esam pie Null mezglā. Mēs ejam, lai atkārtot līdz hronoloģija nav vienāds ar null. Un ko mēs darīsim? Mēs ejam, lai pārbaudītu, vai (ar pašreizējo -> vērtība == vērtība), tad mēs zinām, ka mēs esam faktiski konstatēts mezglu ka mēs meklējam. Tātad šeit mēs varam atgriezties taisnība. Pretējā gadījumā mēs gribam redzēt, vai vērtība ir mazāka par vērtību. Ja pašreizējais mezgla vērtība ir mazāka par vērtību, mēs meklējam, mēs esam gatavojas pārcelties uz labo pusi. Tātad, cur = cur -> right_child, un citādi, mēs ejam, lai pārvietotos pa kreisi. cur = cur -> left_child;. Diezgan vienkārši. 

Jūs, iespējams, atzīst cilpa, kas izskatās ļoti līdzīgs šim no binārā meklēšana agrāk termiņā, izņemot tad mēs būtu darīšana ar zemu, vidēja un augsta. Lūk, mums vienkārši ir apskatīt pašreizējo vērtību, tāpēc tas ir jauki un vienkārši. Pārliecināsimies šis kods strādā. Pirmkārt, pārliecinieties, ka tā apkopo. Izskatās, ka tas dara. Mēģināsim rādīt to. Un tiešām, tas izdrukā visu, kas mums gaidāms. Tā konstatē 6 kokā, nav atrast 10, jo 10 nav kokā, un neatrod 1 nu, jo 1 arī nav kokā. Cool stuff. 

Alright. Iesim atpakaļ uz mūsu specifikācijām un redzēt, ko tālāk. Tagad tā vēlas pievienot dažas vairāk punktus, mūsu koku. Tā vēlas, lai pievienotu 5, 2, 8 un, un pārliecinieties, ka mūsu ir kods joprojām darbojas, kā paredzēts. Iesim darīt. Šajā brīdī, nevis darot, ka kaitinošas kopēt un ielīmēt atkal, pieņemsim uzrakstīt funkciju, lai faktiski izveidotu mezglu. Ja mēs ritiniet uz leju visu ceļu uz galveno, mēs redzam, ka mēs esam darot ļoti līdzīgs kods atkal un atkal katru reizi, ka mēs vēlamies, lai izveidotu mezglu. 

Pieņemsim uzrakstīt funkciju, kas būs faktiski veidot mezglu mums un atpakaļ. Es esmu gatavojas saukt build_node. Es esmu gatavojas būvēt mezglu ar īpašu vērtību. Tuvinātu šeit. Pirmā lieta, es esmu gatavojas darīt, ir faktiski izveidot telpu mezgla uz kaudzes. Tātad, mezglu * n = malloc (sizeof (mezgls)), n -> vērtība = vērtība; un tad šeit, es esmu tikai gatavojas, lai sāktu visu no jomām būtu atbilstošas ​​vērtības. Un pašās beigās, mēs atgrieztos mūsu mezglā. Alright. Viena lieta ir tas, ka šo funkciju tieši šeit gatavojas atgriezties rādītāju uz atmiņu, kas ir kaudze-piešķirta. Kas ir jauka par šo ir tas, ka šis mezgls tagad - mums ir atzīt to par kaudzes, jo, ja mēs deklarēta to skursteņa mēs nevarētu to darīt šo funkciju kā šis. Ka atmiņas varētu aiziet no jomas un būtu nederīgs, ja mēs centāmies, lai piekļūtu to vēlāk. Tā kā mēs esam paziņojot kaudze-piešķirto atmiņu, mēs nāksies rūpēties par atbrīvojot to vēlāk mūsu programmā nav noplūdes nekādas atmiņas. Mēs esam punting par ka viss pārējais kodu tikai Vienkāršības labad laikā, bet, ja jūs kādreiz uzrakstīt funkciju, kas izskatās šādi kur jūs esat ieguvuši - daži to sauc malloc vai realloc iekšā - Jūs vēlaties pārliecināties, ka jūs varat ievietot sava veida komentāru šeit, kas saka, hey, jūs zināt, atgriež kaudze iedalītas mezglu inicializēts ar neuzskaitītu-vērtības. Un tad jūs vēlaties, lai pārliecinātos, ka jūs nodot kaut kādas piezīmes, kas saka zvanītājs jāatbrīvo atgriezto atmiņu. Tādā veidā, ja kāds kādreiz iet un izmanto šo funkciju, viņi zina, ka neatkarīgi viņi saņem atpakaļ no šī funkcija kādā brīdī būs nepieciešams atbrīvot. 

Pieņemot, ka viss ir labi un labs šeit, mēs varam iet uz leju mūsu kodu un aizstāt visus šos līniju tieši šeit ar zvaniem uz mūsu būvēt mezgla funkciju. Darīsim kas tiešām ātri. No vienas puses, ka mēs nebrauksim, lai aizstātu ir šī daļa noteikti šeit apakšā, kur mēs faktiski vadi līdz mezglus norādīt uz otru, tāpēc, ka mēs nevaram darīt mūsu funkcija. Bet, pieņemsim do saknes = build_node (7); mezglā * trīs = build_node (3); mezglu * Sešu = build_node (6); mezglā * 9 = build_node (9);. Un tagad mēs arī vēlējāmies, lai pievienotu mezglu - mezglu * Pieci = build_node (5); mezglā * 8 = build_node (8); un kāda bija citu mezglu? Pieņemsim redzēt šeit. Mēs vēlējāmies, lai arī pievienot 2 - mezglu * divi = build_node (2);. Alright. Šajā brīdī, mēs zinām, ka mēs esam ieguvuši 7, 3, 9, un 6 visu vadu uz augšu pareizi, bet kas par 5, 8 un 2? Saglabāt visu atbilstošā kārtībā, Mēs zinām, ka trīs tiesības bērns ir 6. Tātad, ja mēs ejam, lai pievienotu 5, 5 arī pieder pareizajā pusē koka, no kuriem 3 ir saknes, tā 5 pieder kā kreisajā bērns gada 6. Mēs varam darīt, sakot, sešus -> left_child = pieciem; un tad 8 pieder kā kreisajā bērns gada 9, tā nine -> left_child = astoņi; un tad 2 ir kreisā bērns no 3, lai mēs varam darīt, ka šeit - tev -> left_child = divi;. Ja Jums nav gluži sekot kopā ar to, ka es jums iesakām izdarīt to ārā pats. 

Alright. Pieņemsim glābt šo. Iesim ārā un pārliecinieties, ka tā apkopo, un tad mēs varam pievienot mūsu satur zvaniem. Izskatās viss vēl apkopo. Iesim un pievienot dažas satur zvanus. Atkal, es esmu gatavojas darīt mazliet kopēt un ielīmēt. Tagad meklēt 5, 8, un 2. Alright. Pieņemsim pārliecinieties, ka tas viss izskatās labi vēl. Lieliski! Saglabāt un atmest. Tagad pieņemsim, apkopot, un tagad pieņemsim darboties. No rezultātiem, izskatās, ka viss strādā tikai jauki un labi. Lieliski! Tāpēc tagad mēs esam ieguvuši mūsu Satur funkcija rakstīts. Pieņemsim pāriet un sākt strādāt, kā ievietot mezglu kokā jo, kā mēs darām to jau tagad, lietas nav ļoti skaists. 

Ja mēs ejam atpakaļ uz specifikāciju, tā lūdz mūs uzrakstīt funkciju sauc ievietot - atkal atgriežas bool par to, vai mēs patiešām varētu ievietot mezglu kokā - un tad vērtība ir iekļaut koku ir norādīts kā vienīgais arguments, lai mūsu ievietot funkciju. Mēs atgriezīsimies taisnība, ja mēs patiesi varētu ievietot mezglu satur vērtību kokā, kas nozīmē, ka mēs, viens, bija pietiekami daudz atmiņas, un tad divas, ka mezgls nav jau kokā, jo - Atcerieties, mēs neesam nāksies dublikātus kokā, tikai, lai lietas vienkārši. Alright. Atpakaļ uz kodu. Atveriet to. Tuvināt mazliet, tad ritiniet uz leju. Palūkosimies ievietot funkciju tieši virs satur. Atkal, tas notiek, lai varētu saukt bool ieliktnis (int vērtība). Dodiet tai nedaudz vairāk vietas, un pēc tam, kā noklusējuma pieņemsim likts pretī viltus pašās beigās. Tagad leju apakšā, iesim uz priekšu un nevis manuāli ēkas mezglus galvenajā sevi un elektroinstalācijas tos norādīt uz otru, piemēram, mēs darām, mēs paļauties uz mūsu ievietot funkciju, lai to izdarītu. Mēs ne paļauties uz mūsu ievietot funkciju, lai izveidotu visu koku no nulles tikai vēl, bet mēs atbrīvoties no šīm līnijām - we'll komentēt šo līniju - ka veidot mezglu 5, 8, un 2. Un tā vietā, mēs ievietot zvanu uz mūsu ievietot funkciju lai pārliecinātos, ka tas patiešām darbojas. Šeit mēs iet. 

Tagad mēs esam komentēja šos līnijas. Mums ir tikai 7, 3, 9, 6 un mūsu kokā šajā brīdī. Lai pārliecinātos, ka tas ir viss strādā, mēs varam zoom out, lai mūsu bināro koku, palaist to, un mēs varam redzēt, ka ir tagad stāsta mums, ka mēs esam pilnīgi taisnība - 5, 8, 2 un vairs kokā. Iet atpakaļ uz kodu, un kā mēs gatavojamies, lai ievietotu? Atcerēties, ko mēs darījām, kad mēs faktiski Ievietojot 5, 8, 2 un iepriekš. Mēs spēlējām ka Plinko spēle, kur mēs sākām pie saknes, gāja pa koku pa vienam pa vienam līdz mēs atradām piemērotu plaisu, un tad mēs vadu no mezglā atbilstošā vietā. Mēs ejam, lai darīt to pašu. Tas ir būtībā tāpat rakstot kodu, ka mēs izmantojām satur funkcijas lai atrastu vietas, kur mezglā jābūt, un tad mēs esam tikai gatavojas ievietot mezglu tiesības tur. Sāksim darām. 

Tātad mums ir mezglu * cur = saknes, mēs esam tikai gatavojas sekot satur kodu līdz mēs redzam, ka tas nav gluži strādā mums. Mēs ejam, lai iet cauri koku bet pašreizējais elements nav nulle, un ja mēs redzam, ka ar pašreizējo vērtība ir vienāda ar vērtību, ko mēs esam mēģina ievietot - labi, šis ir viens no gadījumiem, kad mēs varētu faktiski nav ievietot mezglu kokā, jo tas nozīmē, ka mums ir dublikātu vērtību. Šeit mēs esam patiešām gatavojas atgriezties viltus. Tagad, cits ja CUR vērtība ir mazāka nekā vērtība, Tagad mēs zinām, ka mēs virzāmies uz labo  jo vērtība pieder pareizajā pusē cur koku. Pretējā gadījumā mēs spēsim virzīties uz kreiso pusi. Tas būtībā mūsu Satur darbotos labi tur. 

Šajā brīdī, kad mēs esam izgājuši šo kamēr cilpa, Mūsu pašreizējo rādītājs ir būs norādot uz null ja funkcija jau nav atgriezies. Mēs esam tādēļ, kam cur pie vietas, kur mēs gribam, lai ievietotu jaunu mezglu. Kas jāpaveic, ir faktiski veidot jaunu mezglu, ko mēs varam darīt diezgan viegli. Mēs varam izmantot mūsu super ērts būvēt mezgla funkciju, un kaut kas mums nav jādara agrāk - Mēs tikko veida ņēma par pašsaprotamu, bet tagad mēs darīsim tikai, lai pārliecinātos - mēs pārbaudīt, lai pārliecinātos, ka atgriezto vērtību jaunu mezglu bija patiešām nav null, jo mēs nevēlamies, lai sāktu piekļuvi šai atmiņu, ja tas ir nulle. Mēs varam pārbaudīt, lai pārliecinātos, ka jaunais mezgls nav vienāds ar null. Vai vietā, mēs varam tikai redzēt, ja tas tiešām ir nulle, un ja tas ir nulle, tad mēs varam vienkārši atgriezties viltus agri. 

Šajā brīdī, mums ir vadu jaunu mezglu savā piemērotā vietā kokā. Ja mēs atskatāmies uz galveno un kur mēs faktiski bija elektroinstalācijas vērtībām pirms, mēs redzam, ka veids, kā mēs darām to, kad mēs vēlējāmies īstenot 3 kokā Tika mēs piekļūt kreiso bērns saknes. Kad mēs 9 kokā, mums bija, lai piekļūtu tiesības bērns saknes. Mums bija jābūt rādītāju uz vecākiem, lai likt jaunu vērtību kokā. Ritinot atpakaļ uz augšu, lai ievietotu, ka nav gatavojas gluži darbs šeit jo mums nav mātes rādītāju. Ko mēs gribam, lai varētu darīt, ir, šajā brīdī, pārbaudiet vecāku vērtības un redzēt - labi, ak Dievs, Ja vecāks vērtība ir mazāka nekā pašreizējā vērtība, Tad vecāku tiesībām bērnam vajadzētu būt jaunais mezgls; citādi, vecāku kreisā bērnam jābūt jaunu mezglu. Bet, mums nav šo vecāku rādītāju diezgan yet. 

Lai saņemtu to, mēs esam patiešām nāksies izsekot to, kā mums iet cauri koku un atrast piemērotu vietu mūsu cilpa iepriekš. Mēs varam darīt, ritinot atpakaļ uz augšu uz augšu mūsu ievietot funkciju un uzskaites citu rādītāju mainīgo sauc mātes. Mēs ejam, lai uzstādītu to vienāda null sākotnēji, un tad katru reizi, kad mēs iet cauri koku, mēs esam gatavojas noteikt mātes rādītāju saskaņot pašreizējo rādītāju. Uzstādīt vecākiem vienāds ar cur. Tādā veidā, katru reizi mēs iet cauri, mēs spēsim nodrošināt, ka pašreizējais rādītājs kļūst pieaudzis mātes rādītājs izriet tas - tikai vienu līmeni augstāks nekā pašreizējā rādītāja kokā. Tas viss izskatās diezgan labi. 

Es domāju, ka viena lieta, ka mēs gribam, lai pielāgotu tas būvēt mezglā atgriežas null. Lai iegūtu veidotu mezglu faktiski veiksmīgi atgriezties null, mums nāksies mainīt šo kodu, jo šeit, mēs nekad nav pārbaudīta, lai pārliecinātos, ka malloc atgriezies derīgu rādītāju. Tātad, ja (n = NULL!), Tad - ja malloc atgriezās derīgu rādītāju, tad mēs sāktu to; Pretējā gadījumā mēs vienkārši atgriezties un ka galu galā atgriežas null mums. Tagad viss izskatās diezgan labi. Pārliecināsimies tas patiesībā apkopo. Padarīt bināro koku, un oh, mēs esam ieguvuši dažas lietas notiek šeit. 

Mēs esam ieguvuši netiešs deklarācija funkciju būvēt mezglā. Atkal, ar šiem kompilatori, mēs esam gatavojas sākt augšpusē. Ko tas jāsaprot, ka es esmu aicinot veidot mezglu, pirms es esmu faktiski atzina to. Iesim atpakaļ uz kodu tiešām ātri. Ritiniet uz leju, un tik tiešām, mans ieliktnis funkcija tiek deklarēta virs būvēt mezgla funkciju, bet es cenšos izmantot veidot mezglu iekšā ieliktņa. Es esmu gatavojas iet un kopēt - un pēc tam ielīmējiet būvēt mezgla funkciju ceļu augšup šeit augšā. Tādā veidā, cerams, ka būs darbs. Dosim tas vēl iet. Tagad tas viss apkopo. Viss ir labi. 

Bet šajā brīdī, mēs esam faktiski nav saukta mūsu ievietot funkciju. Mēs tikai zinām, ka tā apkopo, tāpēc pieņemsim iet un nodot dažus zvanus iekšā Darīsim, ka mūsu galvenā funkcija. Lūk, mēs komentēja, 5, 8, un 2, un tad mēs neesam stiepļu tos uz augšu uz leju šeit. Pieņemsim veikt dažas prasa ievietot, un pieņemsim arī izmantot to pašu veida stuff, ka mēs izmantojām kad mēs, šos printf zvanus, lai pārliecinātos, ka viss did get ievietota pareizi. Es esmu gatavojas kopēt un ielīmēt, un tā vietā, satur mēs gatavojamies darīt ieliktni. Un nevis 6, 10, 1 un, mēs spēsim izmantot 5, 8, un 2. Tas būtu cerams ievietot 5, 8, 2 un kokā. Sastādīt. Viss ir labi. Tagad mēs faktiski vadīt mūsu programmu. 

Viss atgriezās nepatiesa. Tātad, 5, 8, 2 un nav iet, un tas izskatās Satur nav atrast tos vai nu. Kas notiek? Pieņemsim attālinātu. Pirmā problēma bija tā, ka ievietot šķita atgriezties viltus, un izskatās, ka tas tāpēc, ka mēs atstāt mūsu atgriešanās viltus zvanu, un mēs nekad faktiski atgriezās taisnība. Mēs varam noteikt, ka uz augšu. Otra problēma ir, tagad pat ja mēs darām - glābt šo, atmest šo, palaist padarīt atkal, ir tas apkopot, tad palaist to - mēs redzam, ka kaut kas cits noticis šeit. 5, 8, 2 un joprojām nekad nav atrasts kokā. Tātad, kas notiek? 

Pieņemsim to apskatīt šo kodu. Redzēsim, vai mēs varam izrēķināt šo out. Mēs sākam ar vecākiem nav Null. Mēs noteikti pašreizējo rādītāju, kas vienāds ar saknes rādītājs, un mēs esam gatavojas strādāt mūsu ceļu uz leju caur koku. Ja pašreizējā mezglā nav Null, tad mēs zinām, ka mēs varam virzīties uz leju mazliet. Mēs, kas mūsu mātes rādītāju ir vienāda ar pašreizējo rādītāju, pārbauda vērtības - ja vērtības ir pašas mēs atgriezās nepatiesa. Ja vērtības ir mazāk mēs pārcēlās uz labo; citādi, mēs pārcēlās uz kreiso pusi. Tad mēs veidot mezglu. Es tuvinātu mazliet. Un šeit mēs esam gatavojas izmēģināt, lai vadi līdz vērtības, ir tādi paši. Kas notiek? Redzēsim, vai, iespējams, Valgrind var dot mums mājienu. 

Man patīk izmantot Valgrind tikai tāpēc Valgrind tiešām ātri skrien un stāsta jums, ja ir kādas atmiņas kļūdas. Kad mēs palaist Valgrind uz kodu, kā jūs varat redzēt labo here--Valgrind./binary_tree--and hit ienākt. Tu redzi, ka mums nav nekādas atmiņas kļūda, tāpēc tas izskatās viss ir labi līdz šim. Mums ir dažas atmiņas noplūdes, ko mēs zinām, jo ​​mēs neesam notiek, lai atbrīvotu kādu no mūsu mezgliem. Pamēģināsim darbojas gdb lai redzētu, kas patiesībā notiek. Mēs darīsim gdb / binary_tree.. Tā booted tikai naudas sodu. Pieņemsim noteikt lūzuma punkts par ieliktņa. Pieņemsim darboties. Izskatās, ka mēs nekad faktiski aicināja ieliktnis. Izskatās, problēma bija tikai, ka tad, kad es mainīja noteikti šeit galvenā - Visu šo printf zvaniem no satur - Es nekad tiešām mainījusies zvanīt ieliktni. Tagad pieņemsim pamēģināt. Pieņemsim apkopot. Viss izskatās labi tur. Tagad pamēģināsim darbojas tā, redzēt, kas notiek. Alright! Viss izskatās diezgan labi tur. 

Pēdējā lieta, domāt par ir, vai pastāv kādi malu gadījumi šajā ieliktni? Un izrādās, ka, labi, viena mala lieta, kas vienmēr ir interesanti domāt par ir, kas notiek, ja jūsu koks ir tukša un jūs nosaukt šo ievietot funkciju? Vai tas darbojas? Nu, pieņemsim pamēģināt. - Binary_tree c -. Veids, kā mēs ejam, lai pārbaudītu to, mēs gatavojamies iet uz leju, lai mūsu galvenā funkcija, un nevis vadu šiem mezgliem up kā šis, mēs esam tikai gatavojas komentēt visa lieta, un tā vietā, elektroinstalācijas līdz mezgliem sevi, mēs faktiski var vienkārši iet uz priekšu un dzēst visu. Mēs ejam, lai viss zvanu, lai ievietotu. Tātad, pieņemsim do - nevis 5, 8, 2 un, mēs ejam, lai ievietotu 7, 3, 9 un. Un tad mēs arī vēlamies, lai ievietotu 6, kā arī. Saglabāt. Atmest. Padarīt bināro koku. Tas viss apkopo. Mēs varam tikai palaist to kā ir, un redzēt, kas notiek, bet tas arī būs ļoti svarīgi, lai pārliecinātos, ka mums nav nekādas atmiņas kļūdas, jo tas ir viens no mūsu malas gadījumu ka mēs zinām par. 

Pieņemsim pārliecinieties, ka tā darbojas arī zem Valgrind, ko mēs darīsim, tikai rādīt Valgrind. / binary_tree. Izskatās, ka mēs patiešām ir viena kļūda no vienā kontekstā - mums ir šis segmentāciju vaina. Kas notika? Valgrind patiesībā stāsta mums, kur tā ir. Zoom out mazliet. Izskatās, ka tas, kas notiek mūsu ievietot funkciju, kur mums ir nederīgs palasīt 4 Platība pie ieliktni, līnija 60. Iesim atpakaļ un redzēt, kas notiek šeit. Tāliniet tiešām ātri. Es gribu, lai pārliecinātos, ka tas nav iet uz ekrāna malā, lai mēs varētu redzēt visu. Pull ka mazliet. Alright. Ritiniet uz leju, un problēma ir tieši šeit. Kas notiek, ja mēs uz leju un mūsu pašreizējā mezglā jau ir nulle, Mūsu mātes mezglā ir nulle, tāpēc, ja mēs skatāmies uz augšu pie ļoti top, tieši šeit - ja tas savukārt cilpa nekad faktiski izpilda jo mūsu pašreizējā vērtība ir Null - mūsu saknes ir spēkā tik hronoloģija ir nulle - tad mūsu mātes nekad izpaužas iestatīts uz cur vai derīga vērtība, tāpēc, vecākiem būs arī nulle. Mums ir nepieciešams atcerēties, lai pārbaudītu, ka ar laiku mēs noteikti šeit, un mēs sākam piekļūstot vecāku vērtību. Tātad, kas notiek? Nu, ja vecāks ir Null - ja (mātes == NULL) - tad mēs zinām, ka nedrīkst būt kaut kas kokā. Mums ir jābūt mēģināt ievietot to saknē. Mēs varam darīt, tikai nosakot saknes vienāds ar jauno mezglu. Tad šajā brīdī, mēs faktiski gribam iet caur šīm citām lietām. Tā vietā, tieši šeit, mēs varam darīt, vai nu citur, ja-cits, vai mēs varētu apvienot visu, šeit cits, bet šeit mēs tikai izmantot citur, un darīt to, ka veidā. Tagad mēs esam gatavojas izmēģināt, lai pārliecinātos, ka mūsu vecākiem nav Null Pirms tam faktiski cenšas piekļūt saviem laukiem. Tas mums palīdzēs izvairīties no segmentācijas vaina. Tātad, mēs atmest, zoom out, apkopot, vadīt. 

Nekādas kļūdas, taču mums vēl ir ķekars atmiņas noplūdes jo mēs neesam brīvi kādu no mūsu mezgliem. Bet, ja mēs ejam uz augšu šeit, un mēs skatāmies uz mūsu izdrukas, mēs redzam, ka, labi, izskatās visi mūsu ieliktņiem tika atgriežas taisnība, kas ir labs. Šie ieliktņi ir taisnība, un tad attiecīgi satur zvani ir arī taisnība. 

Labs darbs! Izskatās, ka mēs esam veiksmīgi rakstīts ieliktni. Tas ir viss, kas mums ir šīs nedēļas Problem Set specifikācijā. Viens fun izaicinājums domāt par ir, kā jūs tiešām iet un bez visas šīs koku mezgliem. Mēs varam darīt vairākas dažādos veidos, bet es ņemšu atvaļinājumu, ka līdz jums, lai eksperimentētu, un kā jautru izaicinājums, izmēģināt un pārliecināties, ka jūs varat pārliecināties ka šis Valgrind ziņojumā nedeva kļūdas un nav noplūdes. 

Good luck par šīs nedēļas Huffman kodēšanas problēmu kopumu, un mēs redzēt jūs nākamajā nedēļā! [CS50.TV]