[Powered by Google Translate] [7.pants: ērtāku] [Robs Bowden] [Hārvarda] [Tas ir CS50] [CS50.TV] Labi. Tātad, piemēram, es teicu manu e-pastu, Tas būs bināro koku intensīva sadaļā. Bet tur nav nemaz tik daudz jautājumu. Tāpēc mēs esam gatavojas izmēģināt un izņemt katru jautājumu un iedziļināties sāpīgu detalizācijas visiem labākajiem veidiem, kā to lietas. Tik labi sākumā, mēs iet cauri izlases zīmējumiem divkāršo koku un stuff. Tātad šeit, "Atceries, ka bināro koks ir mezglu līdzīgi saistītajā sarakstā, izņemot nevis vienu rādītāju ir divi: viens par kreisi "bērns" un viens par pareizo "bērnu". " Tātad bināro koks ir tāpat kā saistīts saraksts, izņemot struct gatavojas ir divas norādes. Tur trinary koki, kas drīzumā ir trīs norādes, ir N-ary koki, kas tikko ir generic rādītāju ka jums tad ir malloc pietiekami liela, lai būtu pietiekami norādes uz visām iespējamām bērniem. Tik bināro koku vienkārši notiek, ir pastāvīgs skaits divi. Ja jūs vēlaties, jūs varat dot saistītu sarakstu kā unary koku, bet es nedomāju, ka kāds to nosauc par to. "Zīmēt kastes-un-bultas diagramma bināro koku mezglā satur Nate mīļāko numuru, 7, kur katrs bērns rādītājs ir nulle. " Tātad iPad režīmā. 

Tas būs diezgan vienkārši. Mēs esam tikai nāksies mezglu, es izdarīt to kā kvadrātu. Un es izdarīt vērtības šeit. Tā vērtība iet šeit, un tad uz leju šeit mums būs kreiso pa kreisi rādītāju un labo rādītāju uz labo pusi. Un tas ir ļoti daudz, tāpēc konvencija, lai izsauktu to pa kreisi un pa labi, rādītājs vārdi. Abi šie ir būs nulle. Tas būs tikai nulle, un tas būs tikai nulle. Labi. Tātad atpakaļ šeit. "Ar saistīts saraksts, mums bija tikai, lai uzglabātu rādītāju uz pirmo mezglu sarakstu, lai atcerēties visu saistīts saraksts, vai visu sarakstu. Tāpat ar kokiem, mums ir tikai uzglabāt rādītāju ar vienu mezglu, lai atcerēties visu koku. Šis mezgls ir calle par "saknes" no koka. Balstīties uz tavām no pirms vai izdarīt jaunu tā, ka jums ir kastes-un-bultas tēlojums bināro koku ar vērtību 7, tad 3 kreisi, tad 9 par tiesībām, 6 un pēc tam labajā pusē 3. " Redzēsim, vai es varu atcerēties visu, kas manā galvā. Tātad tas būs mūsu saknes šeit. Mums būs sava rādītāju kaut kur, kaut kas mēs saucam saknes, un tas norāda uz šo puisis. Tagad, lai padarītu jaunu mezglu, Ko mums ir, 3 pa kreisi? Tik jaunu mezglu ar 3, un tas sākotnēji norāda Null. Es ņemšu tikai izvirzīti N. Tagad mēs vēlamies, lai tas iet pa kreisi no 7. Tāpēc mēs mainīt šo rādītāju, lai tagad norādīt uz šo puisi. Un mēs paši. Mēs vēlamies 9 nekā šeit kas sākotnēji vienkārši saka null. Mēs ejam, lai mainītu šo rādītāju, norādiet uz 9, un tagad mēs vēlamies likt 6 tiesībām uz 3. Tātad tas notiek - veikt 6. Un tas puisis būs punkts tur. Labi. Tā ka viss tas mūs aicina darīt. 

Tagad iesim pa kādu terminoloģiju. Mēs jau runājām par to, kā no koka sakne ir top-visvairāk mezglu kokā. Viens satur 7. Apakšā koku mezgli sauc lapas. Jebkurā mezglā, kas tāpat ir Null, jo tās bērniem ir lapa. Tātad tas ir iespējams, ja mūsu bināro koku ir tikai viens mezgls, ka koks ir lapas, un tas arī viss. "Ar" augstums "no koka ir numurs apiņu jums ir veikt lai saņemtu no augšas uz lapu. " Mēs nokļūt, jo otrkārt, starpību starp līdzsvarotus un nesabalansēta bināro koku, bet tagad, kopējais augstums šo koku Es teiktu, ir 3, lai gan, ja jūs saskaitīt apiņu jums ir veikt, lai iegūtu līdz 9, tad tas tiešām ir tikai augstumu no 2. Tieši tagad tas ir nelīdzsvarota binārs koks, bet mēs runājām par līdzsvarots, kad tā kļūst par būtiskiem. Tātad tagad mēs varam runāt par punktiem kokā ziņā salīdzinot ar citiem mezgliem kokā. Tāpēc tagad mums ir vecāki, bērni, brāļi un māsas, senči, un pēcnācējus. Tie ir diezgan saprātīgi, ko tie nozīmē. Ja mēs jautājam - tas ir vecākiem. Tātad, kas ir no 3 mātes? [Studentiem] 7. >> Jā. Vecāks ir tikai būs ko norāda uz jums. Tad kādi ir 7 bērni? [Studenti] 3 un 9. >> Jā. Ievērojiet, ka "bērni" burtiski nozīmē bērni, tāpēc 6 netika piemērota, jo tā ir kā mazbērns. Bet tad, ja mēs ejam pēcnācējus, tā, kādi ir gada 7 pēcteči? [Studenti] 3, 6 un 9. >> Jā. No saknes mezgla pēcteči būs viss kokā, izņemot varbūt saknes mezglu pats, ja jūs nevēlaties, lai uzskatītu, ka pēcnācējs. Un visbeidzot, senči, tāpēc tas ir pretējā virzienā. Tātad, kādi ir par 6 senči? [Studenti] 3 un 7. >> Jā. 9 nav iekļauti. Tas ir tikai tiešais ciltsrakstiem atpakaļ uz saknes būs jūsu senči. 

"Mēs sakām, ka bināro koks" pasūtīts ", ja par katru mezglu koka, visi tās pēcnācēji pa kreisi ir mazāk vērtības un visi par tiesībām tiem ir lielākas vērtības. Piemēram, koku iepriekš pasūtīt, taču tas nav vienīgais iespējamais sakārtotas. " Pirms mēs nokļūt, ka, pasūtīts bināro koku ir arī pazīstams kā bināro meklēšanas koku. Šeit mēs gadās būt aicinot to sakārtotu bināro koku, bet es nekad neesmu dzirdējis to sauc pasūtīts bināro koku pirms, un uz viktorīnas mēs esam daudz vairāk varētu ievietot bināro meklēšanas koku. Viņi viens un tas pats, un tas ir svarīgi atpazīt atšķirību starp bināro koku un binārā meklēšanas koku. Binārs koks ir tikai koks, kas norāda uz divām lietām. Katrs mezgls norāda uz divām lietām. Nav par tām vērtībām, kas tas norāda uz argumentāciju. Tātad patīk vairāk nekā šeit, jo tas ir bināro meklēšanas koku, mēs zinām, ka, ja mēs aiziet pa kreisi no 7, tad visas vērtības, ko mēs varam, iespējams sasniegt ejot pa kreisi gada 7 jābūt vismaz 7. Ievērojiet, ka visi mazāk nekā 7 vērtības ir 3 un 6. Tie visi ir pa kreisi no 7. Ja mēs ejam uz tiesībām 7, viss ir lielāks par 7, tāpēc 9 ir pa labi no 7, tāpēc mēs esam labi. Šis nav gadījums bināro koku, regulāro bināro koku mēs varam vienkārši ir 3 augšā, 7 pa kreisi, 9 kreisi no 7; tur nav vērtības whatsoever pasūtīšanu. Tagad mēs faktiski darīt, jo tas ir garlaicīgs un nevajadzīgs, bet "mēģināt izdarīt tik daudz pasūtītās koki, kā jūs varat iedomāties izmantojot skaitļus 7, 3, 9, 6 un. Cik atšķirīgas kārtība ir tur? Kāda ir katras augstums? " 

Mēs darīsim pāris, bet galvenā ideja ir, tas nekādā veidā unikāla reprezentācija bināro koku satur šīs vērtības. Viss, kas mums nepieciešams, ir dažas binārs koks, kas satur 7, 3, 6, 9 un. Cits iespējams derīga viena būtu sakne ir 3, iet pa kreisi un tas ir 6, dodieties pa kreisi un tas ir 7, iet pa kreisi un tas ir 9. Tas ir pilnīgi derīgs bināro meklēšanas koku. Tas nav ļoti noderīgs, jo tas ir tāpat kā saistīts saraksts un visi šie norādes ir tikai Null. Bet tas ir derīgs koks. Yeah? [Studentu] nav vērtības ir lielāks par tiesībām? Vai tas ir -? >> Tie es gribēju iet citu ceļu. Pastāv arī - jā, pieņemsim pāriet kas. 9, 7, 6, 3. Labs loms. Tā joprojām ir jāpakļaujas kāda bināro koku meklēšana ir paredzēts darīt. Tātad viss pa kreisi, ir mazāks nekā jebkurā mezglā. Mēs varētu vienkārši pāriet, teiksim, šo 6 un nodot to šeit. Nē, mēs nevaram. Kāpēc es glabāt darot, ka? Darīsim - šeit ir 6, šeit ir 7, 6 punkti līdz 3. Tas ir vēl derīga bināro meklēšanas koku. Kas ir nepareizi, ja es - pieņemsim redzēt, ja es varētu nākt klajā ar vienošanos. Jā, labi. Tātad, kas ir nepareizi ar šo koku? Es domāju, es esmu jau devis mājienu, ka kaut kas nav kārtībā ar to. Kāpēc es glabāt darot, ka? Labi. Tas izskatās saprātīgs. Ja mēs skatāmies uz katru mezglu, piemēram, 7, tad pa kreisi no 7 ir 3. Tāpēc mums ir 3, lieta tiesībām uz 3 ir 6. Un, ja paskatās 6, lieta tiesībām uz 6 ir 9. Tad kāpēc tas nav derīgs bināro meklēšanas koku? [Studenti] 9 joprojām ir pa kreisi no 7. >> Jā. Tā ir taisnība, ka visas vērtības jūs varat iespējams sasniegt, ejot pa kreisi no 7 ir mazāk nekā 7. Ja mēs ejam pa kreisi gada 7, mēs ar 3 un mēs joprojām var saņemt līdz 6, mēs joprojām var saņemt līdz 9, bet kad viņš bija mazāks nekā 7, Mums nevajadzētu būt iespējai saņemt uz numuru, kas ir arī lielāks par 7. Tātad tas nav derīgs bināro meklēšanas koku. 

Mans brālis tiešām bija intervija jautājumu ka galvenokārt bija tas, vienkārši kods līdz kaut ko apstiprinātu vai koks ir binārs meklēšanas koks, un tā ir pirmā lieta, ko viņš darīja, bija tikai pārbaudīt, lai redzētu ja pa kreisi un pa labi, ir pareizi, un tad atkārtot tur lejā. Bet jūs varat ne tikai darīt, jums ir sekot līdzi par to, ka tagad, es esmu gājusi pa kreisi no 7, Viss šajā apakškoka jābūt mazākam par 7. Pareizs algoritms ir sekot līdzi no robežās, vērtības var, iespējams ietilpst iekšā Mēs ne iet cauri visiem no tiem. Ir jauki atkārtošanās saistība, kaut gan mēs neesam gotten tiem, vai mēs nevarēsim iegūt tiem, nosakot, cik daudz tur patiesībā ir. Tātad tur ir 14 no tiem. Par to, kā jūs varētu to darīt ideja matemātiski ir, piemēram, Jūs varat izvēlēties jebkuru nevienu būt saknes mezglu, un tad, ja es paņemu 7 par saknes mezglu, tad tur ir, teiksim, daži skaitļi, kas var noiet būt mana kreisā mezglā, un tur ir daži skaitļi, kas var būt manas tiesības mezglā, bet, ja man ir n kopskaitu, tad summa, kas var iet pa kreisi pieskaitot summu, kas var iet uz labo pusi, ir n - 1. Tātad no atlikušajiem skaitļiem, tiem jābūt iespējai doties vai nu pa kreisi vai pa labi. Šķiet grūti, ka, ja man 3 Pirmais tad viss ir iet pa kreisi, bet, ja man 7, tad dažas lietas var iet pa kreisi un dažas lietas var iet uz labo pusi. Un pēc '3 pirmais "Es gribēju viss var aiziet uz labo pusi. Tas ir ļoti, jums vienkārši ir jādomā par to, kā, cik daudz lietas var doties uz nākamo līmeni no koka. Un tas nāk, lai būtu 14 vai jūs varat izdarīt visi no tiem, un tad jūs saņemsiet 14. 

Dodas atpakaļ šeit, "Sakārtoti binārie koki ir foršs, jo mēs varam meklēt caur tiem ir ļoti līdzīgi kā meklējot pa šķiroto masīvs. Lai to izdarītu, mēs sākam pie saknes un strādāt mūsu ceļu uz leju koku uz lapām, pārbaudot katrs mezgls vērtības pret vērtībām mēs meklē. Ja pašreizējais mezgla vērtība ir mazāka par vērtību, mēs meklējam, jums iet blakus mezglu labajā bērnu. Pretējā gadījumā jums iet uz mezglu kreisajā bērnu. Kādā brīdī, jūs vai nu atrast vērtību jūs meklējat, vai jūs satikt nulli, norādot vērtību nav kokā. " Man ir, lai ievilktu koku mums bija pirms; ka ņemšu sekundē. Bet mēs gribam meklēt vai 6, 10, 1 un ir kokā. Tātad, ko tas bija, 7, 9, 3, 6. Labi. Skaitļi jūs vēlaties meklēt, mēs vēlamies meklēt 6. Kā tas algoritms darbojas? Nu, mums ir arī dažas saknes rādītāju uz mūsu koku. Un mēs varētu iet uz saknes un teikt, tas ir vērtība, kas vienāda ar vērtību mēs meklējot? Tāpēc mēs meklējam 6, tāpēc tas nav vienāds. Tātad mēs tur notiek, un tagad mēs sakām, labi, tāpēc 6 ir mazāks par 7. Vai tas nozīmē, ka mēs gribam iet pa kreisi, vai arī mēs gribam iet uz labo pusi? [Studentu] Left. >> Jā. Tas ir ievērojami vieglāk, viss, kas jums jādara, ir izdarīt vienu iespējamo mezglu no koka un tad jūs Don '- nevis mēģināt domāt ar galvu, labi, ja tas ir mazāk, es varu iet pa kreisi vai doties tiesības, tikai meklē šo attēlu, tas ir ļoti skaidrs, ka man ir jāiet pa kreisi ja tas mezgls ir lielāka nekā vērtība, kas es esmu meklē. Tātad jūs iet pa kreisi, tagad es esmu pie 3. Es gribu - 3 ir mazāka nekā vērtība Es meklēju, kas ir 6. Tāpēc mēs ejam pa labi, un tagad es galu galā pie 6, kas ir vērtība Es meklēju, lai es atgrieztos taisnība. Nākamais vērtība Es esmu gatavojas meklēt ir 10. Labi. Tātad 10, tagad, gatavojas - nogrieztu ka - gatavojas sekot saknes. Tagad, 10 būs lielāks par 7, tāpēc es gribu skatīties pa labi. Es esmu gatavojas nākt nekā šeit, 10 būs lielāks par 9, tāpēc es esmu gatavojas vēlas skatīties uz labo pusi. Es nāku nekā šeit, bet nekā šeit tagad es esmu pie null. Ko man darīt, ja es hit null? [Studentu] atgriezties viltus? >> Jā. Es neatradu 10. 1 būs gandrīz identisks gadījums, izņemot tas ir tikai būs Pagriezts, tā vietā, lai meklē leju labajā pusē, es esmu gatavojas skatīties pa kreiso flangu. 

Tagad es domāju, ka mēs faktiski nokļūt kodu. Lūk, kur - atvērt CS50 iekārtu un virzītos savu ceļu tur, bet jūs varat arī vienkārši darīt to telpā. Tas ir iespējams, ideāli to darīt telpā, jo mēs varam strādāt telpā. "Vispirms mums ir nepieciešama jauna tipa definīciju bināru koku mezglu satur int vērtības. Izmantojot Tekstveidnes typedef zemāk, izveidot jaunu tipa definīciju par mezglu bināro koku. Ja Jums ir iestrēdzis. . . "Blah, blah, blah. Labi. Tāpēc pieņemsim likts tekstveidnes šeit, typedef struktūrai mezglā, un mezglu. Jā, labi. Tātad, kādi ir lauki, mēs spēsim vēlēties mūsu mezglu? [Studentu] Int un tad divas norādes? >> Int vērtība, divas norādes? Kā es varu uzrakstīt norādes? [Studentu] struct. >> Es tuvinātu iekšā Jā, tā struktūrai mezglā * kreisi, un struktūrai mezglu * labi. Un atcerieties apspriedes no pēdējo reizi, ka šis nav jēgas, tas nav jēgas, Tas nav jēgas. Jums ir nepieciešams viss tur, lai definētu šo rekursīvas struct. Labi, lai tas, ko mūsu koks gatavojas izskatās. Ja mums bija trinary koks, tad mezglu varētu izskatīties B1, B2, struct mezglā * B3, kur b ir filiāle - patiesībā, es esmu vairāk dzirdējis tas atstāja, vidējas, labo, bet vienalga. Mēs tikai rūp binārā, tāpēc labi, pa kreisi. "Tagad atzīt globālās mezglu * mainīgo par koka saknēm." Tāpēc mēs nebrauksim, lai to izdarītu. Lai padarītu lietas nedaudz grūtāk un vairāk vispārināt mums nebūs globāla mezglu mainīgo. Tā vietā, jo galvenais mēs deklarēt visus mūsu mezglu lietas, un tas nozīmē, ka turpmāk, ja mēs sāktu darboties Mūsu Satur funkcijas un mūsu ievietot funkciju, vietā no mūsu satur funkcija tikai izmantojot šo globālo mezglā mainīgo, mēs esam nāksies to pieņemt kā arguments koku ka mēs gribam to apstrādāt. Ņemot globālā mainīgā bija paredzēts, lai padarītu lietas vieglāk. Mēs ejam, lai padarītu lietas grūtāk. Tagad ņemt minūti, vai arī tā vienkārši darīt šāda veida lieta, kur iekšpusē galvenais vēlaties izveidot šo koku, un tas ir viss, ko vēlaties darīt. Izmēģiniet un būvēt šo koku savā galvenā funkcija. 

Labi. Tātad jums nav pat jābūt konstruētām koks visu ceļu vēl. Bet kāds ir kaut ko es varētu uzvilkt lai parādītu, kā varētu sākt būvēt šādu koku? [Studentu] kāda rīvēšanās, mēģinot izkļūt. [Bowden] Ikviens apmierināti ar savu koku konstrukcijas? [Studentu] Protams. Tas nav izdarīts. >> Tas ir jauki. Mēs varam tikai pabeigt - Ak, jūs varat to saglabāt? Urā. Tāpēc šeit mēs esam - ak, es esmu nedaudz nogriezta. Es pietuvināto? Tuvinātu, ritiniet ārā. >> Man ir jautājums. >> Yeah? [Studentu] Definējot struct, ir lietas, piemēram inicializēts ar kaut ko? [Bowden] Nē >> Labi. Lai jūs būtu inicializēt - [Bowden] Nē Ja jums noteikt, vai ja jūs atzīt struct, tas nav inicializēts pēc noklusējuma, tas ir tāpat kā, ja jūs atzīt int. Tas ir tieši tas pats. Tas ir tāpat kā katrā no atsevišķiem laukiem var būt atkritumu vērtība tajā. >> Un tas ir iespējams noteikt - vai atzīt struct tādā veidā, ka tas sāktu viņiem? [Bowden] Jā. Tātad, īsceļu inicializācijas sintakse gatavojas izskatās - Ir divi veidi, kā mēs varam izdarīt. Es domāju, ka mums vajadzētu sastādīt to lai pārliecinātos šķindēt arī tas. Kārtībā argumentiem, kas nāk struct, jūs likts tik kārtībā argumentiem iekšpusē šo cirtaini lencēm. Tātad, ja jūs vēlaties, lai sāktu to 9 un pa kreisi tiks anulēts un tad pa labi būt nulle, tas būtu 9, null, null. Alternatīva ir, un redaktors nepatīk šo sintaksi, un tā domā, ka es gribu jaunu bloku, bet alternatīva ir kaut kas līdzīgs - šeit, es nolikšu to par jaunu līniju. Jūs varat skaidri pateikt, es aizmirst precīzu sintaksi. Tātad jūs varat skaidri jārisina viņus vārdā, un teikt, . C vai. Vērtība = 9. Kreisi = NULL. Es esmu guessing tie līdz komatus. . Labi = NULL, tāpēc šādā veidā jums nav tiešām ir nepieciešams zināt secību struct, un, kad jūs lasāt šo, tas ir daudz skaidrāk par to, ko vērtība ir tiek inicializēts ar. 

Tas notiek, ir viena no lietām, ka - tāpēc, lai lielākā daļa, C + + ir superset C. Jūs varat lietot C kodu, pārvietot to pa C + +, un tas būtu jāapkopo. Šī ir viena no lietām, ka C + + neatbalsta, tāpēc cilvēki nemēdz darīt. Es nezinu, ja tas ir vienīgais iemesls, cilvēki nemēdz darīt, bet gadījumā, ja man vajadzēja to izmantot jāstrādā ar C + + un tāpēc es nevarēju izmantot šo. Vēl kaut kas piemērs nedarbojas ar C + + ir Kā malloc atgriež "spēkā neesošs *," tehniski, bet jūs varētu vienkārši pateikt char * x = malloc neatkarīgi, un tas automātiski tiks nodotas uz char *. Ka automātiskā lietie nenotiek C + +. Tas nav apkopo, un jums būtu skaidri jāpasaka char *, malloc, neatkarīgi, nodot to uz char *. Nav daudz lietas, ka C un C + + vienisprātis par, bet tie ir divi. Tāpēc mēs iet ar šo sintaksi. Bet pat tad, ja mums nebūtu iet ar šo sintaksi, kāda ir - varētu būt nepareizi ar šo? [Studentu] man nav nepieciešams dereference to? >> Jā. Atcerieties, ka bulta ir netiešs dereference, un tad, kad mēs esam tikai nodarbojas ar struct, mēs vēlamies izmantot. nokļūt pie lauka iekšpusē no struct. Un tikai laika mēs izmantojam bultiņas ir, ja mēs vēlamies darīt - labi, bultiņa ir līdzvērtīga - tas, ko tas nozīmētu, ja es izmanto bultiņu. Viss bultiņa līdzekļi ir, dereference tas, tagad es esmu pie struct, un es varu saņemt lauku. Nu saņemt lauku tieši vai dereference un saņemt lauku - Es domāju, tas būtu vērtība. Bet šeit es esmu, kas nodarbojas tikai ar struct, ne rādītāju uz struct, un tāpēc es nevaru izmantot bultiņu. Bet šī veida lieta, mēs varam darīt, lai visu mezglu. Ak mans Dievs. Tas ir 6, 7, un 3. Tad mēs varam izveidot filiāles mūsu koku, mēs varam būt 7 - mēs varam būt, tās kreisajā vajadzētu norādīt uz 3. Tātad, kā mēs to darām? [Studenti, nesaprotami] >> jā. Adrese node3, un, ja Jums nav adreses, tad tas vienkārši nebūtu sastādīt. Bet atcerieties, ka tie ir norādes uz nākamo mezglu. Tiesības vajadzētu norādīt uz 9, un 3 vajadzētu norādīt uz tiesībām uz 6. Es domāju, ka tas ir visu komplektu. Jebkādus komentārus vai jautājumus? [Studentu, nesaprotami] Saknes būs 7. Mēs varam tikai teikt mezglā * PTR = vai saknes, = & node7. 

Lai mūsu mērķiem, mēs gribam būt darīšana ar ieliktni, tāpēc mēs esam gatavojas vēlas uzrakstīt funkciju, lai ievietotu šajā bināro koku un ieliktnis ir neizbēgami gatavojas aicināt malloc izveidot jaunu mezglu šo koku. Tātad lietas gatavojas saņemt netīrs ar faktu, ka daži mezgli Šobrīd uz skursteņa un citi mezgli ir gatavojas galu galā uz kaudzes, kad mēs ievietot tos. Tas ir pilnīgi derīgs, bet vienīgais iemesls mēs esam spējīgi to darīt uz skursteņa ir tāpēc, ka tas ir tik neīsts piemērs, ka mēs zinām koks ir paredzēts būt konstruēts kā 7, 3, 6, 9. Ja mums nebija tas, tad mums nebūtu malloc pirmajā vietā. Kā mēs redzēsim nedaudz vēlāk, mums būtu malloc'ing. Šobrīd tas ir pilnīgi pamatoti likt uz skursteņa, bet pieņemsim mainīt uz malloc īstenošanu. Tāpēc katra no tām ir tagad būs kaut kas līdzīgs mezglu * node9 = malloc (sizeof (mezgls)). Un tagad mēs esam nāksies darīt mūsu čeku. ja (node9 == NULL) - Es negribēju, ka - return 1, un tad mēs varam darīt node9-> jo tagad tas ir rādītājs, vērtība = 6, node9-> kreisi = NULL, node9-> labi = NULL, un mēs esam nāksies to darīt par katru no šiem punktiem. Tā vietā, pieņemsim, nodot to iekšpusē atsevišķas funkcijas. Sauksim to mezglā * build_node, un tas ir nedaudz līdzīgs API mēs sniedzam Huffman kodēšana. Mēs jums initializer funkcijas koku un deconstructor "funkcijas" tiem kokiem un par mežu pašiem. 

Tāpēc šeit mēs esam gatavojas būt initializer funkciju lai tikai veidot mezglu mums. Un tas notiek, lai izskatās diezgan daudz tieši kā šis. Un es esmu pat būs slinks un nemaina nosaukumu mainīgo, kaut node9 nav jēgas vairs. Ak, es domāju node9 vērtība nebūtu bijis 6. Tagad mēs varam atgriezties node9. Un šeit mums vajadzētu atgriezties null. Ikvienam vienoties par šo būvēt-mezglu funkciju? Tāpēc tagad mēs varam tikai zvanu, ka, lai izveidotu jebkuru mezglu ar konkrētu vērtību un Null norādes. Tagad mēs varam zvanīt, ka mēs varam darīt mezglā * node9 = build_node (9). Un pieņemsim darīt. . . 6, 3, 7, 6, 3, 7. Un tagad mēs vēlamies izveidot pašus norādes, izņemot tagad viss jau ziņā šautru tāpēc vairs nav nepieciešams adresi. Labi. Tātad, kāda ir pēdējā lieta, ko es gribu darīt? Tur kļūdu pārbaude, ka es to nedaru. Kāda būvēt mezglā atdevi? [Studentu, nesaprotami] >> Jā. Ja malloc neizdevās, tas būs atpakaļ null. Tāpēc es esmu gatavojas laiski likt to šeit, nevis darīt nosacījumu par katru. Ja (node9 == NULL, vai - vēl vienkāršāk, tas ir līdzvērtīgs tikai ja ne node9. Tātad, ja nav node9, vai nav node6, vai nav node3, vai ne node7, atgriezties 1. Varbūt mums vajadzētu drukāt malloc neizdevās, vai kaut ko. [Studentu] Vai viltus vienāds ar null, kā arī? [Bowden] Jebkura nulles vērtība ir nepatiesa. Tātad Null ir nulles vērtība. Nulle ir nulles vērtība. Viltus ir nulles vērtība. Jebkurš - diezgan daudz tikai 2 nulles vērtības ir spēkā un nulle, viltus ir tikai jaukšanas definēta kā nulle. Tas attiecas arī tad, ja mēs atzīt globālo mainīgo. Ja mums tomēr ir mezglā * saknes šeit, tad - jauka lieta par globālo mainīgo, ka viņi vienmēr ir sākotnējo vērtību. Tas nav taisnība funkciju, cik iekšā šeit, ja mums ir, piemēram, mezglu * vai mezglu x. Mums nav ne jausmas, ko x.value, x.whatever, vai mēs varētu drukāt tos un tie varētu būt patvaļīga. Tas nav taisnība globālo mainīgo. Tātad mezgls saknes vai mezglu x. Pēc noklusējuma, viss, kas ir globāls, ja nav skaidri inicializēts ar kādu vērtību, ir nulles vērtība kā tās vērtību. Tātad šeit, mezglu * saknes, mums nav skaidri inicializ tā neko, tāpēc tās noklusējuma vērtība būs nulle, kas ir nulles vērtība norādes. Noklusējuma vērtība x ir gatavojas nozīmē, ka x.value ir nulle, x.left ir nulle, un x.right ir nulle. Tāpēc, ka tas ir struktūrai, visi no struct jomās būs nulles vērtības. Mums nav nepieciešams izmantot, ka šeit, lai gan. [Studentu] Šīs structs ir savādāki nekā citiem mainīgajiem, un citi mainīgie ir atkritumu vērtības, tie ir nulles? [Bowden] Pārējās vērtības too. Tātad x, x būs nulle. Ja tas ir pie pasaules mēroga, tas ir sākotnējo vērtību. >> Labi. [Bowden] Nu sākotnējā vērtība jums iedeva vai nulle. Es domāju, ka rūpējas par visu. 

Labi. Tāpēc nākamais jautājuma daļu jautā, "Tagad mēs vēlamies, lai rakstītu funkciju sauc satur ar prototipu bool satur int vērtību. " Mums nav gatavojas darīt bool ir int vērtību. Mūsu prototips ir gatavojas izskatās bool satur (int vērtību. Un tad mēs esam arī gatavojas nodot to koku ka tas būtu pārbaudi, lai redzētu, vai tas ir šo vērtību. Tātad mezglu * koks). Labi. Un tad mēs varam zvanīt to ar kaut ko līdzīgu, varbūt mēs vēlamies printf vai kaut ko. Satur 6, mūsu saknes. Ka vajadzētu atgriezties vienu, vai taisnība, tā satur 5 sakne būtu atgriezties viltus. Tātad ņemt otrais īstenot šo. To var izdarīt, vai nu iteratīvi vai rekursīvi. Jauka lieta par to, kā mēs esam, kas lietām up ir tas, ka tas pakļauj sevi mūsu rekursīvas risinājums ir daudz vieglāk nekā pasaules mainīgo veidā izdarīja. Jo, ja mēs vienkārši ir ietverti int vērtība, tad mums nav veids, recursing leju subtrees. Mums būtu jābūt ar atsevišķu palīgs funkcija, kas recurses paredz subtrees par mums. Bet tā kā mēs esam nomainījuši veikt koku kā argumentu, kas tas būtu vienmēr ir bijis pirmajā vietā, Tagad mēs varam Recurse vieglāk. Tātad iteratīvs vai rekursīvs, mēs iet pār abiem, bet mēs redzēsim, ka rekursīvas beidzas ar to diezgan viegli. Labi. Vai kāds ir kaut ko mēs varam strādāt ar? 

[Studentu] Man iteratīvu risinājumu. >> Labi, iteratīvs. Labi, tas izskatās labi. Tātad, gribu staigāt mūs caur to? [Studentu] Protams. Tāpēc es noteikti temp mainīgo iegūt pirmo mezglu no koka. Un tad es vienkārši looped cauri, bet temperatūra nav vienāda null, tāpēc, kamēr vēl bija kokā, es domāju. Un, ja vērtība ir vienāda ar vērtību, kas temperatūra ir vērsta uz, tad tas atgriežas šo vērtību. Pretējā gadījumā tas pārbauda, ​​vai tas ir uz labo pusi, vai kreisās puses. Ja Jums kādreiz iegūt situāciju, kad tur nav daudz koku, tad tas atgriežas - tas izejām cilpu un atgriež nepatiess. [Bowden] Labi. Tā ka, šķiet labi. Kāds ir kādi komentāri par kaut ko? Man nav pareizības komentārus vispār. Viena lieta, ko mēs varam darīt, ir tas puisis. Ak, tas notiek, lai iet nedaudz gareni. Es noteikt, ka uz augšu. Labi. 

Ikvienam vajadzētu atcerēties, kā trijnieks darbi. Ir noteikti ir viktorīnu pagātnē kas jums funkcija ar trīskāršu operators, un teikt, tulkot, darīt kaut ko, kas neizmanto trīskāršo. Tātad šī ir ļoti izplatīta lieta, kad es domāju, lai izmantotu trīskāršo, ja ja daži nosacījums mainīgo uz kaut ko, cits noteikt to pašu mainīgo, lai kaut kas cits. Tas ir kaut kas ļoti bieži var tikt pārveidoti par šāda veida lieta kur noteikts, ka mainīgo šo - vai, nu, tas ir taisnība? Tad šī, vēl šis. [Studentu] Pirmais ir, ja taisnība, vai ne? [Bowden] Jā. Kā es vienmēr izlasīt to ir, temperatūra ir vienāda vērtība lielāka nekā temp vērtību, tad tas, cits to. Tas uzdodot jautājumu. Tas ir lielāks? Tad darīt to pirmā lieta. Cits to otra lieta. Es gandrīz vienmēr - kolu, es tikai - manā galvā, es izlasīju kā citur. 

Vai kāds ir rekursīvas risinājums? Labi. Šis viena mēs spēsim - tas jau var būt liels, bet mēs ejam, lai padarītu to vēl labāku. Tas ir diezgan daudz pašā precīzu ideja. Tas ir tikai labi, jūs vēlaties, lai izskaidrotu? [Studentu] Protams. Tāpēc mēs esam pārliecinoties, ka koks nav null, pirmkārt, jo, ja koks ir nulle, tad tas notiek, lai atgrieztos nepatiess, jo mēs neesam atraduši. Un, ja tur ir vēl koks, mēs iedziļināties - mēs vispirms pārbaudiet, ja vērtība ir pašreizējā mezglā. Atgriešanās taisnība, ja tā ir, un, ja ne mēs Recurse pa kreisi vai pa labi. Vai tas skaņu gadījumā? >> Mm-hmm. (Līgums) Tāpēc ievērosiet, ka tas ir gandrīz - strukturāli ļoti līdzīgs atkārtojuma risinājumu. Tas ir tikai, ka tā vietā, lai recursing, mums bija, kamēr cilpa. Un bāzes gadījums, kad koks nav vienāds null bija nosacījums, saskaņā ar kuru mēs izcēlās kamēr cilpa. Viņi ir ļoti līdzīgi. Bet mēs spēsim veikt šo vienu soli tālāk. Tagad, mēs darīt to pašu šeit. Pamanīt mēs atgriežoties vienu un to pašu gan no šīm līnijām, izņemot vienu arguments ir atšķirīgs. Tāpēc mēs esam gatavojas darīt, ka par trīskāršu. Es hit iespēju kaut ko, un tas veikts simbolu. Labi. Tāpēc mēs esam gatavojas atgriezties satur to. Tas kļūst par vairākas līnijas, labi, pietuvināto tas ir. Parasti, kā stilistisku lieta, es nedomāju, ka daudzi cilvēki likts atstarpi pēc bultiņas, bet es domāju, ja tu esi konsekventa, tas ir labi. Ja vērtība ir mazāka nekā koku vērtību, mēs vēlamies Recurse no koku pa kreisi, cits mēs vēlamies Recurse par koku tiesībām. Tāpēc, ka bija veidot šo izskatās mazāks viens solis. Otrais solis, lai šis izskatās mazāks - mēs varam atdalīt ar vairākām līnijām. Labi. Padarīt to izskatās mazākas divpakāpju ir šeit, tāpēc atgriešanās vērtība ir koka vērtību, vai satur neatkarīgi. 

Tas ir svarīga lieta. Es neesmu pārliecināts, vai viņš teica, ka tas skaidri klasē, bet tā sauc īssavienojuma novērtējums. Ideja šeit ir vērtība == koku vērtība. Ja tā ir taisnība, tad tas ir taisnība, un mēs vēlamies, lai "vai" kas ar kāda ir vairāk nekā šeit. Tātad, pat domāt par visu, nekā šeit, kāda ir visa izteiksme gatavojas atgriezties? [Studentu] True? >> Jā, jo taisnība neko, or'd - vai taisnība or'd ar jebko ir vienmēr taisnība. Tā tiklīdz mēs redzam atgriešanās vērtību = koku vērtību, mēs esam tikai gatavojas atgriezties taisnība. Nav pat gatavojas Recurse further satur leju līniju. Mēs varam veikt šo vienu soli tālāk. Atgriešanās koks nav vienāds anulēts un visu. Tas padarīja viena līnija funkcija. Tas ir arī piemērs īssavienojumu novērtējumu. Bet tagad tas ir pati ideja - vietā - tāpēc, ja koks nav vienāds null - vai, nu, ja koks nav vienāda null, kas ir slikti gadījums, ja koks vienāds Null, tad pirmais nosacījums būs nepatiesa. Tātad viltus anded ar jebko būs ko? [Studentu] Aplams. >> Jā. Tas ir otra puse īssavienojumu novērtējumu, ja ja koks nav vienāds Null, tad mēs nebrauksim, lai pat iet - vai ja koks nav vienāda null, tad mēs neesam gatavojas darīt vērtību == koku vērtība. Mēs esam tikai gatavojas nekavējoties atgriezties viltus. Kas ir svarīgi, jo, ja tā nav īssavienojumu novērtēt, tad, ja koks nav vienāda null, šis otrais nosacījums ir gatavojas SEG vaina, jo koks-> vērtību dereferencing null. Tātad tas ir kas. Var padarīt šo - novirzīt vienreiz pāri. Tas ir ļoti bieži lieta arī, nevis padarot šo par vienu līniju ar šo, bet tas ir parasta lieta apstākļos, varbūt ne tieši šeit, bet, ja (koks! = NULL, un koks-> vērtība == vērtība), darīt visu. Tas ir ļoti bieži stāvoklis, kad tā vietā, lauzt šo divās IF, kur patīk, ir koks Null? Labi, tas nav nulle, tāpēc tagad ir koks vērtība ir vienāda ar vērtību? Izdarīt. Tā vietā, šis nosacījums, tas nekad SEG vaina jo tā būs pārtraukums, ja tas notiek, ir nulle. Nu, es domāju, ja jūsu koks ir pilnīgi nederīgs rādītāju, tas joprojām var SEG vaina, bet tā nevar SEG vaina, ja koks ir nulle. Ja tas būtu nulle, tas izcelties pirms jūs kādreiz dereferenced rādītāju pirmajā vietā. [Studentu] Vai tas saucamais slinks novērtējums? 

[Bowden] Slinks vērtēšana ir atsevišķa lieta. Slinks novērtējums ir vairāk kā jūs lūgt par vērtību, jūs lūgt, lai aprēķinātu vērtību, veida, bet jums nav nepieciešams to nekavējoties. Tātad līdz brīdim, kad tiešām ir nepieciešams, tā nav novērtēta. Tas nav tieši tas pats, bet Huffman PSET, tā saka, ka mēs "laiski" rakstīt. Iemesls, kāpēc mēs darīt, ir tāpēc, ka mēs esam patiešām buffering rakstīt - Mēs nevēlamies, lai rakstīt atsevišķus bitus laikā, vai atsevišķas baiti vienlaicīgi, mēs tā vietā vēlas saņemt rieciens baitu. Tad, kad mums ir rieciens baitu, tad mēs to uzraksta. Pat ja jūs lūgt to rakstīt - un fwrite un fread darīt to pašu veida lieta. Viņi buferis savu lasa un raksta. Pat ja jūs lūgt to rakstīt uzreiz, tas, iespējams, nebūs. Un jūs varat būt pārliecināti, ka lietas notiek, kas rakstīts līdz zvanīt hfclose vai kāds tas ir, kas tad saka, labi, es esmu slēgšanas manu failu, tas nozīmē, ka es labāk rakstīt visu, man nav rakstisku vēl. Tam nav nepieciešams rakstīt viss out līdz pietuvojas failu, un tad tas ir. Tātad tas ir tikai to, ko slinks - tas gaida, kamēr tas ir noticis. Tas - ņem 51 un jūs iedziļināties to sīkāk, jo OCaml un viss 51, viss ir rekursija. Nav iteratīvs risinājumus, būtībā. Viss ir rekursija, un slinks novērtēšana būs svarīgi daudz apstākļu kur, ja Jums nav laiski novērtēt, tas nozīmētu - Piemērs ir straumes, kas ir bezgalīgi garš. Teorētiski, jūs varat domāt par dabas numuriem kā plūsmā 1-2-3-4-5-6-7, Tātad laiski novērtētie lietas ir labi. Ja es saku es gribu desmito numuru, tad es varētu novērtēt līdz desmito numuru. Ja es gribu simto numuru, tad es varētu novērtēt līdz simto numuru. Bez slinks novērtējumu, tad tas notiek, lai mēģinātu novērtēt visus numurus uzreiz. Tu esi izvērtējot bezgala daudz numurus, un tas vienkārši nav iespējams. Tātad tur ir apstākļi daudz kur slinks novērtējums ir tikai būtiska, lai iegūtu lietas darbu. 

Tagad mēs vēlamies, lai rakstītu ieliktni kur ievietot būs Tāpat mainās tā definīciju. Tātad šobrīd tas bool ieliktnis (int vērtība). Mēs ejam, lai mainītu, ka uz bool ieliktni (int vērtība, mezglu * koks). Mēs esam patiešām gatavojas mainīt, ka atkal mazliet, mēs redzēsim, kāpēc. Un pāriesim build_node, tikai heck no tā, Iepriekš ievietot tāpēc mums nav rakstīt funkcijas prototips. Kas ir mājiens, ka jūs esat būs izmantojot build_node ar ieliktņa. Labi. Paņem minūti par to. Es domāju, ka es saglabāti jāpārskata, ja jūs vēlaties, lai vilktu no tā, vai, vismaz, es darīju tagad. Es gribēju nedaudz pārtraukumu, lai padomātu par loģiku ievietot, ja jūs nevarat domāt par to. Būtībā, jums būs tikai kādreiz ievietojot pie lapām. Piemēram, ja es ievietot 1, tad es esmu neizbēgami būs ievietojot 1 - Es izmaiņas melnā - I'll būt ievietojot 1 nekā šeit. Vai, ja es ievietotu 4, es gribu būt ievietojot 4 vairāk nekā šeit. Līdz ar to nav svarīgi, ko jūs darāt, jūs esat būs ievietojot pie lapas. Viss, kas Jums jādara, ir atkārtot pa koku līdz jums mezglu kas būtu mezglā mātes, jaunā mezgla mātes, un tad mainīt savu kreiso vai labo rādītāju, atkarībā no tā, vai tas ir lielāks vai mazāks nekā pašreizējā mezglā. Mainītu šo rādītāju norādīt uz savu jauno mezglu. Tāpēc atkārtot pa koku, padarīt lapu norāda uz jaunu mezglu. Arī domāju par to, kāpēc, kas aizliedz veida situāciju pirms, kur es būvēti bināro koku, kur tas bija pareizs ja tu tikai paskatījās vienā mezglā, bet 9 bija pa kreisi no 7 Ja jūs uzsvēra leju visu ceļu. Tā ka ir neiespējami šajā scenārijā, jo - domā par ievietojot 9 vai kaut; pašu pirmo mezglu, Es esmu gatavojas, lai redzētu 7 un es esmu tikai gatavojas iet uz labo pusi. Līdz ar to nav svarīgi, ko es daru, ja es esmu ievietojot dodoties uz lapu, un uz lapu, izmantojot atbilstošu algoritmu, tas būs neiespējami man ievietot 9 pa kreisi no 7 jo tiklīdz es hit 7 Es esmu gatavojas iet uz labo pusi. Vai kāds ir kaut ko sākt? [Studentu] man. >> Protams. [Studentu, nesaprotami] [Citi students, nesaprotami] [Bowden] Tas ir appreciated. Labi. Gribu paskaidrot? 

[Studentu] Tā kā mēs zinām, ka mēs bijām ievietojot krustpunkti beigās koka, Es looped cauri koku iteratīvi līdz es saņēmu mezglu, norādīja uz null. Un tad es nolēmu nodot to vai nu uz labo pusi vai kreisajā pusē Izmantojot šīs tiesības mainīgo, tas teica man, kur likt to. Un tad, būtībā, es tikko ka pēdējo - ka temperatūra mezglā norāda uz jauno mezglu, tas bija radīt, nu kreisajā pusē vai labajā pusē, atkarībā no tā, kāda vērtība labi bija. Visbeidzot, es noteikt jauno mezglu vērtību vērtību tās testēšana. [Bowden] Labi, tāpēc es redzu vienu jautājumu šeit. Tas ir tāpat kā 95% no tur. Viens jautājums, ka es redzu, labi, vai kāds cits redzu problēmu? Kas ir apstāklis, saskaņā ar kuru tās uzliesmo no cilpas? [Studentu] Ja temperatūra ir nulle? >> Jā. Tātad, kā jūs izkļūt no cilpas ir, ja temperatūra ir nulle. Bet ko man darīt tieši šeit? Es dereference temp, kas ir neizbēgami Null. Tātad otra lieta, kas jums jādara, ir ne tikai sekot līdz temperatūra ir nulle, Jūs vēlaties, lai sekotu no mātes visu laiku. Mēs arī vēlamies mezglā * vecāks, es domāju, mēs varam saglabāt, ka null sākumā. Tas ir nāksies dīvainu uzvedību uz koka saknēm, bet mēs nokļūt, ka. Ja vērtība ir lielāka nekā kāds, tad temp = temp labi. Taču, pirms mēs to darām, vecākiem = temp. Vai vecāki vienmēr būs vienāda temp? Vai tas tā ir? Ja temperatūra nav Null, tad es esmu gatavojas pārcelties uz leju, vienalga ko, uz mezglu, par kuru temperatūra ir mātes. Tāpēc vecākiem būs temperatūra, un tad es eju temp leju. Tagad temperatūra ir nulle, bet vecāka norāda uz mātes lieta, kas ir nulle. Tātad šeit lejā, es nevēlos, lai noteikt tiesības ir vienāds ar 1. Tāpēc es pārcēlos uz labo, tāpēc, ja labi = 1, un es domāju, jūs arī vēlaties darīt - ja jūs pārvietoties pa kreisi, jūs vēlaties noteikt tiesības vienāda ar 0. Vai arī, ja jūs kādreiz pārvietot uz labo pusi. Tik labi = 0. Ja labi = 1, Tagad mēs vēlamies, lai mātes pareizo rādītāju newnode, cits mēs vēlamies, lai mātes kreiso rādītāju newnode. Jautājumi par šo? Labi. Tātad šis ir veids, kā mēs - labi, patiesībā, nevis darīt to, mēs 1/2 gaidīts jums izmantot build_node. Un tad, ja newnode vienāds Null, atgriezties viltus. Tas, ka. Tagad, tas ir tas, ko mēs gaidīts jums darīt. 

Tas ir tas, ko darbinieki risinājumi darīt. Es nepiekrītu ar to kā "pareizo" ceļu, iet par to bet tas ir pilnīgi naudas sodu, un tas strādā. Viena lieta, ka ir mazliet dīvaini šobrīd ir ja koks sāk off par spēkā, mums iet ar Null koku. Es domāju, tas atkarīgs no tā, kā jūs definētu uzvedību aizrit Null koku. Es domāju, ka, ja jums iet ar Null koku, tad ievietojot vērtību par Null kokā būtu tikai atgriezties kokā, kur vienīgā vērtība ir tā, ka viena mezglā. Vai cilvēki piekrīt, ka? Jūs varētu, ja vēlaties, ja jums iet ar Null kokā un jūs vēlaties ievietot vērtības vērā to, atgriezties viltus. Tas ir atkarīgs no jums, lai noteiktu to. Lai to izdarītu, pirmā lieta, man teica, un tad - labi, jūs gatavojas ir problēmas darot, ka, jo tas būtu vieglāk, ja mums bija pasaules rādītāju uz lieta, bet mums nav, tādēļ, ja koks ir nulle, tur neko nevar darīt par to. Mēs varam vienkārši atgriezties viltus. Tāpēc es esmu gatavojas mainīt ieliktni. Mēs tehniski varētu vienkārši mainīt šīs tiesības šeit, kā tas atkārtojot pār lietām, bet es esmu gatavojas mainīt ievietot veikt mezgla ** koku. Double norādes. Ko tas nozīmē? Nevis nodarbojas ar norādes uz mezgliem, lieta, ko es esmu būs manipulējot tas rādītājs. Es esmu būs manipulējot šo rādītāju. Es esmu būs manipulējot norādes tieši. Tas ir jēga, jo, domāju par leju - labi, tagad tas norāda uz null. Ko es gribu darīt, ir manipulēt šo rādītāju, lai norādītu uz nav null. Es vēlos, lai norādītu uz savu jauno mezglu. Ja es tikko sekot līdzi norādes uz manu norādes, tad man nav nepieciešams, lai sekotu mātes rādītāju. Es varu tikai sekot, lai redzētu, ja rādītājs ir vērsta uz null, un ja rādītājs ir vērsta uz null, mainīt to norādīt uz mezglu es gribu. Un es varu mainīt to, jo man ir rādītāju uz rādītāja. Pieņemsim redzēt šīs tiesības tagad. Jūs faktiski var darīt to rekursīvi diezgan viegli. Vai mēs gribam to darīt? Jā, mēs darām. 

Pieņemsim redzēt to rekursīvi. Pirmkārt, kāda ir mūsu bāzes scenārijs būs? Gandrīz vienmēr mūsu bāzes scenārijs, bet patiesībā, tas ir sava veida grūts. Pirmās lietas, pirmkārt, ja (koks == NULL) Es domāju, mēs esam tikai gatavojas atgriezties viltus. Tas atšķiras no jūsu koku pagaidām null. Tas ir rādītājs, lai jūsu saknes rādītājs pagaidām Null kas nozīmē, ka jūsu saknes rādītājs nav. Tātad šeit lejā, ja man mezglu * - pieņemsim tikai atkārtotu to. Mezglu * sakne = NULL, un tad es esmu dodas uz zvanu ieliktni darot kaut kas līdzīgs, ievietot 4 stājas & saknes. Tātad & sakne, ja sakne ir mezgls * Tad & sakne būs mezgla **. Tas ir derīgs. Šajā gadījumā, koks, šeit, koks nav Null - vai ievietot. Šeit. Koks nav null; * koks ir nulle, kas ir labi jo, ja * koks ir nulle, tad es varētu manipulēt ar to lai tagad norāda uz to, ko es gribu to norādīt uz. Bet, ja koks ir nulle, tas nozīmē, ka es tikko nācis šeit un teica null. Tas nav jēgas. Es nevaru darīt neko ar to. Ja koks ir Null, atgriezties viltus. Tāpēc es būtībā jau teicu, ko mūsu reālā bāzes scenārijs ir. Un kas tas būs? [Studentu, nesaprotami] [Bowden] Jā. Tātad, ja (* koks == NULL). Tas attiecas uz lietu nekā šeit ja ja mana sarkanā rādītājs ir rādītājs es esmu vērsta uz, tāpēc, piemēram, es esmu vērsta uz šo rādītāju, tagad es esmu vērsta uz šo rādītāju. Tagad es esmu vērsta uz šo rādītāju. Tātad, ja mana sarkanā rādītājs, kas ir mana mezglu **, ir kādreiz - ja *, mana sarkanā rādītājs, ir kādreiz Null, tas nozīmē, ka es esmu pie lietas, kur es esmu koncentrējoties uz rādītājs, kas norāda - Tas ir rādītājs, kas pieder lapu. Es vēlos mainīt šo rādītāju norādīt savu jauno mezglu. Atgriezties nekā šeit. Mans newnode būs tikai mezglu * n = build_node (vērtība) tad n, ja n = null, atgriezties viltus. Cits mēs gribam mainīt to, ko rādītājs pašlaik norādot uz šim norādīt uz mūsu jaunceļamā mezglā. Mēs faktiski var darīt šeit. Vietā, sakot n, mēs sakām * koks = ja * koku. Ikviens saprot, ka? Ka, risinot ar norādes uz norādes, mēs varam mainīt Null norādes norādīt uz lietām, mēs vēlamies, lai viņi norāda uz. Tas ir mūsu bāzes scenārijs. 

Tagad mūsu atkārtošanās, vai mūsu rekursija, būs ļoti līdzīga visām citām recursions mēs esam darījuši. Mēs esam gatavojas vēlaties ievietot vērtību, un tagad es esmu gatavojas izmantot trīskāršo vēlreiz, bet to, kas ir mūsu nosacījums būs? Kāda tā ir, mēs meklējam izlemt, vai mēs gribam iet pa kreisi vai pa labi? Darīsim to atsevišķos posmos. Ja (vērtība <) ko? [Studentu] koks ir vērtība? [Bowden] Tāpēc atcerieties, ka es esmu šobrīd - [Studenti, nesaprotami] [Bowden] Jā, tik labi šeit, pieņemsim, ka šī zaļā bulta ir piemērs tam, ko koks ir patlaban, ir rādītājs uz šo rādītāju. Tātad tas nozīmē, ka es esmu rādītāju uz norādi uz 3. The dereference divreiz skanēja labi. Kas man - kā es varu darīt? [Studentu] Dereference vienreiz, un tad darīt bulta, ka veidā? [Bowden] Tātad (* koks) ir dereference reizi, -> vērtība gatavojas sniegt man vērtību mezglā, ka es esmu netieši norādot uz. Lai es varētu rakstīt arī to ** tree.value ja vēlaties, ka. Nu strādā. Ja tas ir gadījumā, tad es vēlos aicināt ievietot ar vērtību. Un kāda ir mana atjaunināts mezgla ** būs? Es gribu iet pa kreisi, lai ** tree.left būs mana kreisā. Un es gribu rādītāju uz šo lietu tā, ka, ja pa kreisi beidzas ar to nulles rādītājs, Es varu mainīt to norādīt uz manu jauno mezglu. 

Un otru lietu var būt ļoti līdzīgi. Pieņemsim faktiski padarīt ka ​​mana trīskāršu tiesības tagad. Ievietot vērtību, ja vērtība <(** koks). Vērtība. Tad mēs vēlamies, lai atjauninātu mūsu ** pa kreisi, cits mēs gribam, lai atjauninātu mūsu ** pa labi. [Studentu] Vai tas iegūtu rādītāju rādītāja? [Bowden] Atcerieties, ka - ** tree.right ir mezglā zvaigzne. [Studentu, nesaprotami] >> Jā. ** Tree.right ir kā šī rādītāja vai kaut ko. Tātad, ņemot rādītāju tam, ka dod man, ko es gribu gada rādītāja uz šo puisis. [Studentu] Vai mēs aiziet atkal kāpēc mēs izmantojam divas norādes? [Bowden] Jā. Tātad - nē, jūs varat, un ka risinājums pirms bija veids, kā to dara bez darīt divas norādes. Jums ir nepieciešams, lai varētu saprast, izmantojot divus norādes, un tas ir tīrāks risinājums. Arī paziņojums, ka tas, kas notiek, ja mans koks - kas notiek, ja mana sakne ir Null? Kas notiek, ja man darīt šo lietu tieši šeit? Tātad mezglu * sakne = NULL, ievietojiet 4 stājas & saknes. Kas ir sakne būs pēc šo? [Studentu, nesaprotami] >> Jā. Sakne vērtība būs 4. Sakne kreisi būs nulle, sakņu tiesības būs nulle. Gadījumā, ja mēs neizturēja sakni pēc adreses, mēs nevarētu mainīt saknes. Gadījumā, ja koks - ja sakne ir nulle, mēs tikko bija atgriezties viltus. Tur nekas mēs varētu darīt. Mēs nevaram ievietot mezglu tukšā koku. Bet tagad mēs varam, mēs tikai veikt tukšu koku uz vienu mezglu koka. Kas parasti ir paredzamais veids, ka tas ir paredzēts strādāt. 

Turklāt, tas ir ievērojami īsāks nekā arī sekotu mātes, un tāpēc jums atkārtot leju visu ceļu. Tagad man ir mana vecākiem, un man vienkārši ir mana mātes tiesības rādītāju uz whatever. Tā vietā, ja mēs to izdarīja iteratīvi, tas lūdzu būt pati ideja ar kamēr cilpa. Bet tā vietā, lai risinātu ar manu mātes rādītājs, vietā mans pašreizējais rādītājs būtu lieta ka es esmu tieši mainīt norādīt savu jauno mezglu. Man nav jātiek galā ar to, vai tas ir vērstas virzienā pa kreisi. Man nav jātiek galā ar to, vai tas ir vērsta uz labo pusi. Tas ir tikai kāds šis rādītājs ir, es esmu gatavojas noteikt to norādīt uz savu jauno mezglu. Ikvienam jāsaprot, kā tā darbojas? Ja ne, kāpēc mēs vēlamies darīt to šādā veidā, bet vismaz, ka tas darbojas kā risinājumu? [Studentu] Ja mēs atgrieztos taisnība? [Bowden] Tas ir iespējams šeit. Ja mēs pareizi ievietojiet to, atgriešanās patiess. Cits, noteikti šeit mēs esam gatavojas vēlaties atgriezties jebkādos ievietot atdevi. 

Un, kas ir īpašs par šo rekursīvo funkciju? Tas ir astes rekursīvs, tik ilgi, kamēr mēs apkopotu ar kādu optimizāciju, tā atzīst, ka, un jūs nekad get kaudze pārplūdes no tā, pat ja mūsu koku augstums ir 10000 vai 10 miljoni. [Studentu, nesaprotami] [Bowden] Es domāju, tas to Dash - vai ko optimizācija līmenī ir nepieciešams, lai asti rekursijas jāatzīst. Es domāju, tā atzīst - GCC un šķindēt ir arī dažādas nozīmes saviem optimizācijas līmeni. Es gribu teikt, tas ir DashO 2, lai pārliecinātos, ka tas atzīst asti rekursijas. Bet mēs - tu varētu uzbūvēt, piemēram, Fibonocci piemēram, vai kaut ko. Tas nav viegli pārbaudīt ar šo, jo tas ir grūti salikt binārs koks, kas ir tik liels. Bet jā, es domāju, ka tas DashO 2, kas ja jūs sastādīt ar 2 DashO, tas būs meklēt asti rekursijas un optimizēt ka ārā. Iesim atpakaļ uz - ievietot burtiski pēdējā lieta tai ir vajadzīga. Iesim atpakaļ uz ieliktni nekā šeit kur mēs esam gatavojas darīt to pašu domu. Tas būs vēl ir slikti ir, jo nevar pilnībā rīkoties kad saknes pati ir nulle, vai pagātnes ieraksts ir nulle, bet nevis nodarbojas ar mātes rādītājs, pieņemsim piemērot tādu pašu loģiku saglabājot norādes uz norādes. Ja šeit mēs turpinām mūsu mezglā ** pašreizējo, un mums nav nepieciešams, lai sekotu tiesības vairs, bet mezglu ** pašreizējo = & koks. Un tagad mūsu kamēr cilpa būs kamēr * hronoloģija nav vienāds null. Nav nepieciešams sekot vecāku vairs. Nav nepieciešams sekot līdzi pa kreisi un pa labi. Un es aicinu to temp, jo mēs esam jau izmanto temp. Labi. Tātad, ja (vērtība> * temperatūra), tad & (* temp) -> tiesības cits temp = & (* temp) -> pa kreisi. Un tagad, šajā brīdī, kad šī kamēr cilpa, Es tikai darīt, jo varbūt tas ir vieglāk domāt par iteratīvi nekā rekursīvi, bet pēc šī kamēr cilpa, * Temp ir rādītājs mēs vēlamies mainīt. 

Pirms mums bija vecāks, un mēs vēlējāmies, lai mainītu vai nu mātes kreisi vai vecākus labi, bet, ja mēs gribam mainīt vecāku tiesības, tad * temp ir mātes tiesības, un mēs varam to mainīt tieši. Tātad šeit lejā, mēs varam darīt * temp = newnode, un tas arī viss. Tātad paziņojums, viss, ko mēs darījām, tas bija izņemt rindas kodu. Lai sekotu no mātes visu, kas ir papildu pūles. Lūk, ja mēs vienkārši sekot rādītāju uz rādītāja, un pat tad, ja mēs vēlējāmies, lai atbrīvotos no visiem šiem cirtaini bikšturi tagad, lai tas izskatās īsāks. Tas šobrīd ir tieši tāds pats risinājums, bet mazāk rindas kods. Kad jūs sākat atzīstot to kā derīgu risinājumu, tas ir arī vieglāk iemesla apmēram nekā, piemēram, labi, kāpēc man ir šī karogu int tiesības? Ko tas nozīmē? Ak, tas nozīmētu, ka Katru reizi, kad es iet labi, man ir nepieciešams, lai uzstādītu to, cits ja es eju pa kreisi man ir nepieciešams, lai uzstādītu to uz nulli. Lūk, man nav iemesla par to, tas ir tikai vieglāk domāt par. Jautājumi? [Studentu, nesaprotami] >> Jā. Labi, tāpēc pēdējā bit - Es domāju viens ātrs un vienkāršs funkciju mēs varam darīt, ir, let's - kopā, es domāju, izmēģināt un uzrakstīt satur funkcijas kas nav vienalga, vai tas ir bināro meklēšanas koku. Tas satur funkcija būtu atgriezties true ja nekur šajā vispārējā bināro koks ir vērtība, mēs meklējam. Tāpēc pieņemsim vispirms to darīt rekursīvi un tad mēs darīsim to iteratīvi. Mēs faktiski var vienkārši darīt to kopā, jo tas būs ļoti īss. 

Kāda ir mana bāzes scenārijs būs? [Studentu, nesaprotami] [Bowden] Tātad, ja (koks == NULL), tad ko? [Studentu] atgriezties viltus. [Bowden] cits, labi, man nav nepieciešams cits. Ja bija mana citu gadījumu. [Studentu] Tree vērtība? >> Jā. Tātad, ja (koks-> vērtība == vērtība. Pamanīt mēs esam atpakaļ uz mezglu *, nevis mezgls ** s? Satur nekad nepieciešams izmantot mezglu **, jo mēs neesam modificējot norādes. Mēs esam tikai šķērso tos. Ja tas notiks, tad mēs vēlamies atgriezties taisnība. Cits mēs vēlamies, lai šķērsotu bērnus. Tāpēc mēs nevaram spriest par to, vai viss pa kreisi, ir mazāks un viss pa labi ir lielāks. Tātad, kas ir mūsu nosacījums būs šeit - vai, ko mēs gatavojamies darīt? [Studentu, nesaprotami] >> Jā. Atgriešanās satur (vērtība, koks-> pa kreisi) vai satur (vērtība, koks-> pa labi). Un tas arī viss. Un paziņojums ir daži īssavienojumu novērtējumu, kur, ja mēs gadās atrast vērtību kreisajā koku, mēs nekad jāmeklē īstajā koku. Tas ir viss funkcija. Tagad pieņemsim to darīt iteratīvi, kas būs mazāk jauki. Mēs ņemšu parasto sākumu mezglu * cur = koku. Kamēr (ar pašreizējo! = NULL). Ātri gatavojas redzēt problēmu. Ja cur - šeit, ja mēs kādreiz izkļūt no šīs, tad mēs esam izsīkšanai lietas, lai apskatīt, tāpēc atgriezties viltus. Ja (paš-> vērtība == vērtība), atgriešanās patiess. Tāpēc tagad mēs esam vietā - Mēs nezinām, vai mēs gribam iet pa kreisi vai pa labi. Tātad patvaļīgi, pieņemsim tikai iet pa kreisi. Es esmu protams uzskriet jautājumu, kur es esmu pilnīgi pamesta viss - Es tikai kādreiz pārbauda kreiso pusi koku. Es nekad pārbaudīt visu, kas ir tiesības bērns neko. Kā es varu noteikt šo? [Studentu] Jums ir sekot kreisi un pa labi kaudze. [Bowden] Jā. Tāpēc pieņemsim, būtu struktūrai sarakstu, mezglu * n, un tad mezglu ** tālāk? Es domāju, ka darbojas naudas sodu. Mēs vēlamies, lai iet pa kreisi, vai let's - šeit. Struct saraksts saraksts =, tas būs sākums veic šo struct sarakstā. * Saraksta = NULL. Tāpēc, ka būs mūsu saistīts saraksts gada subtrees ka mēs esam izlaidis vairāk. Mēs gatavojamies, lai šķērsotu pa kreisi tagad, bet, jo mēs neizbēgami jānāk atpakaļ uz labo pusi, Mēs ejam, lai saglabātu labo pusi iekšā mūsu struct saraksta. Tad mums būs new_list vai struktūrai, struktūrai saraksts *, new_list = malloc (sizeof (saraksts)). Es esmu gatavojas ignorēt kļūdu pārbaudot, bet jums vajadzētu pārbaudīt, lai redzētu, ja tas ir null. New_list mezglu tas notiek, lai norādītu uz - ak, tāpēc es gribēju to šeit. Tas notiek, lai norādītu uz otro struct sarakstā. Tas ir tikai kā saistīts sarakstus darbu. Tas ir tas pats kā int saistīts saraksts izņemot mēs esam tikai aizstājot int ar mezglu *. Tas ir tieši tas pats. Tātad new_list, vērtību mūsu new_list mezglā, būs pašreizējo-> labi. Vērtība mūsu new_list-> nākamā būs mūsu sākotnējais saraksts, un tad mēs esam gatavojas atjaunināt savu sarakstu, lai norādītu uz new_list. 

Tagad mums ir nepieciešama sava veida veidā velkot lietas, kā mēs ir pārvieto visu kreisi apakškoka. Tagad mums ir nepieciešams, lai pull sīkumi no tā, tāpat hronoloģija ir Null, mēs negribam, lai tikai atgriezties viltus. Mēs vēlamies, lai tagad vilktu ārā mūsu jauno sarakstu. Ērts veids, kā to izdarīt - labi, patiesībā, tur ir vairāki veidi, kā to izdarīt. Kāds ir ieteikums? Kur man būtu jādara tas, vai un kā man būtu darīt? Mums ir tikai pāris minūtes, bet kādi ieteikumi? Vietā - vienā veidā, nevis mūsu stāvoklī ir, bet, ko mēs šobrīd meklē nav Null, vietā mēs turpināsim iet līdz mūsu saraksts pats par sevi ir nulle. Tātad, ja mūsu saraksts beidzas ar to, null, tad mēs esam izsīkšanai lietas meklēt, lai meklētu vairāk. Bet tas nozīmē, ka pirmā lieta, kas mūsu sarakstā ir tikai gatavojas būt pirmais mezgls. Pati pirmā lieta būs - mums vairs nav nepieciešams, lai redzētu, ka. Tā saraksts-> n būs mūsu koku. saraksts-> blakus būs nulle. Un tagad, kamēr saraksts nav vienāds null. Cur gatavojas pull kaut ko no mūsu saraksta. Tāpēc pašreizējo gatavojas vienlīdzīgu saraksta-> n. Un tad saraksts ir gatavojas vienlīdzīgu saraksta-> N, vai saraksta-> nākamo. Tātad, ja ar pašreizējo vērtība ir vērtība. Tagad mēs varam pievienot gan mūsu labo rādītāju un mūsu kreiso šautriņu kamēr viņi nav null. Noteikti šeit, es domāju, mēs būtu jādara, ka pirmajā vietā. Ja (paš-> labi! = NULL) tad mēs ievietot šī mezglu mūsu sarakstā. Ja (paš-> pa kreisi), tas ir mazliet papildus darbu, bet tas ir labi. Ja (paš-> kreisi! = NULL), un mēs ejam, lai ievietotu palikuši mūsu saistīts saraksts, un kas būtu tā. Mēs atkārtot - kamēr mums ir kaut kas mūsu sarakstā, Mums ir cits mezgls aplūkot. Tāpēc mēs skatāmies šo mezglu, mēs iepriekš mūsu sarakstu uz nākamo. Ja tas mezgls ir vērtība, mēs meklējam, mēs varam atgriezties taisnība. Cits ievietot gan mūsu kreiso un labo subtrees, kamēr viņi nav nulle, mūsu sarakstā lai mēs neizbēgami iet pār tiem. Tātad, ja tie nav null, ja mūsu saknes rādītājs norādīja uz divām lietām, tad vispirms mēs velk kaut kas tik mūsu saraksts beidzas ar to null. Un tad mēs ieliekam divas lietas atpakaļ, tāpēc tagad mūsu saraksts ir 2 izmēru. Tad mēs ejam uz cilpas atpakaļ uz augšu un mēs esam tikai gatavojas pull, teiksim, kreiso peles mūsu saknes mezgla. Un tas būs tikai glabāt notiek, mēs galu galā looping pāri visam. 

Ievērojiet, ka šī bija ievērojami sarežģītāks kas rekursīvs risinājumu. Un es esmu teica vairākas reizes ka rekursīvas risinājums parasti ir daudz kopīga ar iteratīvu risinājumu. Šeit tas ir tieši tas, ko rekursīvas risinājums dara. Vienīgā izmaiņa ir, ka tā vietā netieši izmantojot steku, programma kaudze, kā savu ceļu, lai sekotu, ko mezgliem jums joprojām ir nepieciešams apmeklēt, Tagad jums ir skaidri izmantot saistīto sarakstu. Abos gadījumos jums ir sekot kāda mezgla vēl ir apmeklējis. Šajā rekursīvs gadījumā tas ir tikai vieglāk, jo kaudze tiek īstenots, lai jūs kā programmas kaudze. Ievērojiet, ka šī saistīts saraksts, tas ir kaudze. Lai ko mēs tikko likts uz skursteņa uzreiz, ko mēs ejam, lai pull off kaudze apmeklēt nākamo. Mēs esam no laika, bet kādi jautājumi? [Studentu, nesaprotami] [Bowden] Jā. Tātad, ja mums ir saistīts saraksts, strāva gatavojas norādīt uz šo puisis, un tagad mēs esam tikai padziļinot mūsu saistīts saraksts koncentrēties uz šo puisis. Mēs šķērso pa saistīts saraksts šajā rindā. Un tad es domāju, mēs būtu bez mūsu saistīts saraksts un stuff reizi pirms atgriešanās patiess vai nepatiess, mums ir nepieciešams, lai atkārtot pār mūsu saistīts saraksts un vienmēr leju šeit, es domāju, ja mēs cur tiesības nav vienāds, pievienojiet to, tāpēc tagad mēs vēlamies, lai atbrīvotu cur jo, labi, vai mēs pilnīgi aizmirst par sarakstu? Yeah. Tātad tas, ko mēs vēlamies darīt šeit. Kur ir rādītājs? Cur bija tad - mēs vēlamies struct sarakstā * 10 vienāds sarakstu nākamo. Bezmaksas saraksts, saraksts = temp. Un gadījumā, ja mēs atgrieztos taisnība, mums ir nepieciešams, lai atkārtot atlikušajā mūsu saistīts saraksts atbrīvojot lietas. Jauka lieta par rekursīvas risinājums ir atbrīvot lietas nozīmē tikai popping factorings off kaudze, kas notiks par jums. Tāpēc mēs esam aizgājuši no kaut kas ir, piemēram, 3 līnijas grūti domāt, par kodu lai kaut kas ir ievērojami daudz vairāk grūti domāt-par rindas kodu. Kādi jautājumi? Labi. Mēs esam labi. Atā! [CS50.TV]