[Powered by Google Translate] [7. jagu: mugavam] [Rob Bowden] [Harvardi Ülikool] [See on CS50] [CS50.TV] Hea küll. Nii nagu ma ütlesin oma e-posti, see saab olema binaarsed-tree-intensiivne jagu. Aga seal ei ole, et palju küsimusi. Nii et me ei kavatse proovida ja venitama iga küsimus ja lähevad valus üksikasjalikult kõiki parimaid viise, kuidas asju teha. Nii et kohe alguses, me läheme läbi proovi joonised kahendpuuks ja värki. Nii et siin, "Pea meeles, et kahendpuu on sõlmed sarnased seotud nimekirja, välja arvatud ühe asemel osuti on kaks: üks vasakul "laps" ja üks õige "laps". " Nii kahendpuu on nagu seotud nimekirja, välja arvatud struktuure saab olema kaks suunanäitajaks. Seal on trinary puud, mis hakkavad olema kolm suunanäitajaks, on n-aarne puud, mis tuleb lihtsalt geneeriliste pointer et siis pead malloc olema piisavalt suured piisavalt viiteid, et kõik võimalikud lapsed. Nii kahendpuu lihtsalt juhtub olema konstantne number kaks. Kui soovite, võite anda lingitud nimekirja unaarsed puu, aga ma ei usu, et keegi seda nimetab, et. "Joonista kasti-ja-nooled skeem kahendpuu sõlme sisaldavad Nate lemmik number, 7, kus iga laps osuti on null. " Nii iPad režiimis. 

See saab olema üsna lihtne. Me lihtsalt läheb on sõlm, ma joonistan seda ruutu. Ja ma joonistan väärtused siin. Nii et raha läheb siia, ja siis siia me peame vasakule kursori vasakule ja paremale kursor paremale. Ja see on väga palju nii konventsiooni nimetada seda vasakule ja paremale, kursor nimed. Mõlemad hakkavad olema null. See oleks lihtsalt null, ja et oleks lihtsalt null. Okei. Nii tagasi siin. "Mis lingitud nimekiri, oli meil ainult salvestada pointer esimese sõlme loetelu, et mäletan kogu seotud nimekirja, või kogu nimekirja. Samuti puid, meil on ainult salvestada pointer ühe sõlme, et meeles pidada terve puu. See sõlm on calle "root" puu. Tugineda oma skeem alates enne või joonista uus nii, et teil on kastid ja-nooled kujutamine kahendpuu koos väärtus 7, siis 3 vasakule, siis 9 paremal, ning seejärel 6 paremal 3 ". Vaatame, kas ma mäletan kõike seda oma peas. Nii et see saab olema meie juur siin. Me peame mõned osuti kuhugi, midagi, mida me kutsume juur, ja see osutab see kutt. Nüüd teha uus sõlm, Mis meil, 3 vasakul? Nii et uus sõlm 3, ja see algselt toob null. Ma lihtsalt panna N. Nüüd tahame teha, et minna vasakule, 7.. Nii et me muudame seda kursorit nüüd käsk see kutt. Ja me teeme sama. Tahame 9 üle siin mis esialgu lihtsalt ütleb null. Me muudame selle osuti, punkt 9, ja nüüd me tahame panna 6. õigus 3. Nii see läheb - teha 6. Ja see kutt on punkt seal. Okei. Nii et kõik see kutsub meid tegema. 

Nüüd lähme üle mõned terminoloogia. Me juba rääkisime sellest, kuidas puu juur on kõige ülemisele sõlme puu. Üks sisaldab 7. Sõlmede allosas puu kutsutakse lehed. Iga sõlme, mis lihtsalt on null kui tema lapsed on lehed. Seega on võimalik, kui meie kahendpuu on vaid ühe sõlme, et puu on lehed, ja ongi kõik. "" Kõrgus "puu on number humala sa pead tegema saada ülevalt lehed. " Me võtame arvesse, teises erinevus vahel tasakaalustatud ja tasakaalustamata kahendpuuks, kuid nüüd, üldkõrgus selle puu Ütleksin on 3, kuigi kui sa loendada humala sa pead tegema, et saada kuni 9, siis see on tõesti ainult kõrgus 2. Praegu on see tasakaalustamata kahendpuu, kuid me rääkisime tasakaalustatud kui ta saab olla asjakohane. Nii et nüüd saame rääkida tippe puu poolest võrreldes teiste sõlmede puu. Nüüd oleme vanemad, lapsed, õed-vennad, eellased, alanejad sugulased. Nad on päris tervet mõistust, mida need tähendavad. Kui me küsime - see vanemad. Mis on vanem 3? [Õpilased] 7. >> Jah. Vanem on lihtsalt saab olema, mida toob teile. Siis millised on lapsed 7? [Õpilased] 3 ja 9. >> Jah. Pange tähele, et "lapsed" tähendab sõna-sõnalt lastele nii 6 ei kohaldata, sest see on nagu lapselaps. Aga siis kui me läheme järeltulijad, siis millised on järeltulijad 7? [Õpilased] 3, 6 ja 9. >> Jah. Järeltulijad Juursõlme saab olema kõike puu, välja arvatud ehk root node ise, kui sa ei taha arvata, et järeltulija. Ja lõpuks, esivanemate, nii et see on vastupidises suunas. Millised on esivanemad 6? [Õpilased] 3 ja 7. >> Jah. 9 ei kuulu. See on lihtsalt otsene sugupuu tagasi juurte saab olema teie esivanemad. 

"Me ütleme, et kahendpuu on" tellitud "kui iga sõlme puu, kõik tema järeltulijad vasakul on väiksem väärtused ja kõik need, paremal on suuremad väärtused. Näiteks puu eespool on tellitud, kuid see pole ainus võimalik tellida kokkuleppel. " Enne saame, et tellida kahendpuu on tuntud ka Kahendotsingupuu. Siin juhtub olema nimetades seda tellida kahendpuu, kuid ma ei ole kunagi kuulnud ta kutsus tellitud kahendpuu enne, ja viktoriini oleme palju tõenäolisem, et panna Kahendotsingupuu. Nad on ühe ja sama, ja see on oluline tunnete vahet kahendpuu ja Kahendotsingupuu. Kahendpuu on lihtsalt puu, mis viitab kahele asjale. Iga sõlme viitab kahele asjale. Ei ole põhjendust umbes väärtusi, mis osutab ta. Nii meeldib siin, sest see on Kahendotsingupuu, me teame, et kui me läheme vasakule, 7., siis kõik väärtused, et saame võimaluse jõuda minnes jättis 7. olema vähemalt 7. Pange tähele, et kõik väärtused on alla 7 on 3 ja 6. Need on kõik vasakule 7.. Kui me läheme paremale, 7., kõik peab olema suurem kui 7, nii 9 on paremal 7, nii et me oleme head. See ei ole puhul kahendpuu, regulaarset kahendpuu saame lihtsalt on 3 ülaosas, 7 vasakule, 9. vasakule, 7., seal ei ole järjekorda väärtused üldse. Nüüd me tegelikult ei tee seda, sest see on tüütu ja tarbetu, kuid "proovida teha nii palju tellitud puud nagu sa ei mõtle kasutades numbrid 7, 3, 9 ja 6. Mitu erinevat kord on olemas? Mis on kõrgus iga üks? " 

Me teeme paar, kuid peamine idee on, see on kuidagi unikaalne esindatuse kahendpuu sisaldab neid väärtusi. Kõik me vajame, on mõned kahendpuu, mis sisaldab 7, 3, 6 ja 9. Teine võimalik kehtiv üks oleks juur on 3, minna vasakule ja see on 6, minna vasakule ja see on 7, minna vasakule ja see on 9. See on täiesti kehtiva Kahendotsingupuu. See ei ole väga kasulik, sest see on nagu seotud nimekirja ja kõik need osuti on lihtsalt null. Aga see on kehtiv puu. Jah? [Student] Ärge väärtused olema suurem paremal? Või on see -? >> Need Tahtsin minna teist teed. Seal on ka - Jah, teeme minna seda. 9, 7, 6, 3. Hea saak. See ikka peab alluma mida kahendpuu otsing peaks tegema. Nii et kõik vasakule peab olema väiksem kui mis tahes sõlme. Me võiksime lihtsalt liikuda, öelda, et see 6 ja pane see siia. Ei, me ei saa. Miks ma hoida teed seda? Teeme - siin on 6, siin on 7, 6 punkti 3. See on ikka kehtiv Kahendotsingupuu. Mis on valesti, kui ma - vaatame, kas ma saan tulla kokkuleppel. Jah, okei. Mis on valesti selle puu? Ma arvan, et ma olen juba andnud teile vihje, et midagi on valesti. Miks ma hoida teed seda? Okei. See näeb mõistlik. Kui me vaatame iga sõlme, nagu 7, siis vasakule 7 on 3. Nii et meil on 3 asja paremale 3 on 6. Ja kui te vaatate 6 asi paremal 6. on 9. Miks see ei kehti Kahendotsingupuu? [Õpilased] 9 on ikka vasakule 7.. >> Jah. See peab olema tõsi, et kõik väärtused saab võimaluse jõuda minnes vasakule 7. on alla 7. Kui me läheme vasakule, 7., saame 3 ja saame ikka kuni 6, saame ikka kuni 9, kuid läks alla 7, me ei tohiks olla võimalik saada arv, mis on suurem kui 7. Nii et see ei ole kehtiv Kahendotsingupuu. 

Minu vend tegelikult oli intervjuu küsimus et põhimõtteliselt oli see lihtsalt koodi üles midagi kinnitada kas puu on Kahendotsingupuu, ja nii esimene asi mis ta tegi oli lihtsalt vaadata, kui vasakul ja paremal on õiged, ja seejärel kinnitada, sinna alla. Aga sa ei saa lihtsalt teha; teil jälgida asjaolu, et nüüd, kui ma olen läinud vasakul 7, kõik siin alampuu peab olema vähemalt 7. Õige algoritm vajab jälgida piiridest, et väärtusi saab võimaluse langeda sisse Me ei lähe läbi kõik. Seal on kena kordumise suhtes, kuigi me ei ole muretsenud neile, või me ei saa nendele, määratleda, kui palju seal tegelikult on. Nii on 14 neist. Idee, kuidas te seda teha matemaatiliselt on nagu, saab valida mis tahes ühekordne olla root node, ja siis kui ma valin 7. olema root node, siis on, ütleme, mõned numbrid, et võib minna mu vasak lümfisõlm, ja seal on mõned numbrid, mis võib olla minu õigus sõlme, aga kui ma olen n koguarvu, siis summa, mis võib minna vasakule pluss summa, mis võib minna paremale on n - 1. Nii et ülejäänud numbrid, nad peavad suutma minna kas vasakule või paremale. Tundub keeruline, et kui ma panen 3 esimeses siis kõik on minna vasakule, aga kui ma panen 7, siis mõned asjad võivad minna vasakule ja mõned asjad võivad minna paremale. Ja '3 esimene "ma mõtlesin kõike võib minna paremale. See on tõesti, sa lihtsalt pead mõtlema nagu, kuidas paljud asjad võivad minna järgmisele tasandile puu. Ja see väljub olla 14 või saate joonistada kõik need, ja siis saad 14. 

Tulles tagasi siin, "Korrastatud kahendpuuks on lahe, sest me saame otsida neile väga sarnaselt otsides üle järjestatud massiivist. Selleks hakkame keskmes ja töö meie tee puu otsast alla suunas lehed, kontrollides iga sõlme väärtusi ELi väärtustega vastuolus me otsite. Kui praegune tipp väärtus on väiksem kui me otsime, te lähete kõrval sõlme õigust lapsele. Muidu lähete sõlm vasakus laps. Mingil hetkel, siis kas leida raha otsite, või saad joosta null, näidatud osutatud teenuste maksumus pole puus. " Ma pean ekraanigraafika puu oli meil enne; et võtan teise. Aga me tahame otsida kas 6, 10, ja 1 on puu. Nii et mis see oli, 7, 9, 3, 6. Okei. Numbrid, mida soovite otsida, me tahame otsida 6. Kuidas see algoritm toimib? Noh, meil on ka mõned root kursor meie puu. Ja me oleks minna root ja öelda, on see väärtus võrdub Me otsite? Nii et me otsime 6, nii see ei ole võrdne. Nii et me jätkame, ja nüüd me ütleme, okei, nii 6 on väiksem kui 7. Kas see tähendab, me tahame minna vasakule või me tahame minna eks? [Student] vasakule. >> Jah. See on tunduvalt lihtsam, kõik mida sa pead tegema, on teha üks võimalik sõlme puu ja siis sa ei - selle asemel, et mõelda oma peaga, okei, kui see on väiksem, ma lähen vasakule või minna paremale, lihtsalt vaadates seda pilti, siis on väga selge, et ma pean minema vasakule kui sõlm on suurem kui väärtus, et ma otsin. Nii et te lähete vasakule, nüüd olen kell 3. Tahan - 3 on väiksem kui ma otsin, mis on 6. Nii et me lähme paremale, ja nüüd ma lõpuks kell 6, mis on väärtus Otsin, nii et ma tagasi true. Järgmise väärtuse Ma lähen otsima on 10. Okei. Nii et 10 nüüd, läheb - ära lõigatud, et - minnes järgige juur. Nüüd, 10 saab olema suurem kui 7, nii et ma tahan vaadata paremale. Ma lähen siia tulla, 10. saab olema suurem kui 9, nii et ma lähen taha vaadata paremale. Ma tulen siia, aga siin nüüd ma olen null. Mida teha, kui ma tabanud null? [Student] Tagasi vale? >> Jah. Ma ei leia 10. 1 saab olema peaaegu identne juhul, välja arvatud see lihtsalt läheb keerata, selle asemel et otsida ette paremal pool, ma lähen vaatan alla vasakule. 

Nüüd ma arvan, et me tegelikult saada koodi. Siin, kus - avada CS50 seade ja liikuda oma teed seal, kuid võite ka lihtsalt teha seda ruumi. See on ilmselt ideaalne teha seda ruumi, sest me ei tööta ruumi. "Esiteks me vajame uut tüüpi määratlus kahendpuu sõlme sisaldav int väärtusi. Kasutades trafaretset typedef allpool, luua uus määratlus sõlme kahendpuu. Kui te jänni. . . "Blaa, blaa, blaa. Okei. Nii et paneme trafaretset siin, typedef struktuure sõlm ja sõlme. Jah, okei. Millised on valdkonnad me ei kavatse soovite meie sõlme? [Student] Int ja siis kaks viiteid? >> Int väärtus, kaks viiteid? Kuidas kirjutada viiteid? [Student] struktuure. >> Ma peaks suumimiseks Jah, nii struct tipp * vasakule, ja struct tipp * õigus. Ja pidage meeles arutelu alates viimane kord, et see ei ole mõistlik, see ei ole mõistlik, see ei ole mõistlik. Sa pead kõike seal selleks, et määratleda see rekursiivne struct. Okei, nii see on, mida meie puu hakkab välja nägema. Kui me teeksime trinary puu, siis sõlme tunduda B1, B2, struct tipp * B3, kus b on filiaal - tegelikult, ma olen rohkem kuulnud seda vasakule, keskele, paremale, aga mis iganes. Me ainult hoolid binaarne, nii paremale, vasakule. "Nüüd kuulutab maailma tipp * muutuja puu juur." Nii et me ei kavatse seda teha. Selleks, et teha asju veidi keerulisemaks ja üldistatud, meil ei ole maailma tipp muutuja. Selle asemel, et peamine kuulutame me kõik meie sõlme asju, ja see tähendab, et allpool, kui me alata meie Contains funktsioon ja meie sisestada funktsiooni, asemel meie Contains funktsioon lihtsalt kasutades seda maailma tipp muutuja, me lähed on see võtta argumendina puu, mis me tahame seda töödelda. Võttes globaalne muutuja pidi teha asju lihtsamaks. Me läheme teha asju raskemaks. Nüüd võta minut või nii lihtsalt ei selline asi, kus sees peamine soovite luua see puu, ja see on kõik, mida tahame teha. Proovige ja ehitada see puu oma põhifunktsiooni. 

Okei. Nii et sa ei pea isegi on ehitatud puust terve tee veel. Aga kellelgi on midagi, mida ma võiks tõmba näidata, kuidas võiks alustada ehitamist nagu puu? [Student] Kellegi peksma, üritavad välja. [Bowden] Igaüks rahul oma puu ehitamine? [Student] Muidugi. See ei teinud. >> See on hea. Me ei saa lihtsalt lõpetada - Oh, saad sa salvestada? Hurraa. Nii et siin on meil - Oh, ma olen veidi ära lõigatud. Kas ma suumitud? Suumimiseks vajutage juhtnuppu välja. >> Mul on küsimus. >> Jah? [Student] Kui oled määranud struct, on asjad initsialiseeritud midagi? [Bowden] No >> Okei. Nii et sa oleks initsialiseerida - [Bowden] No Kui oled määranud, või kui te deklareerite struct, see ei ole vormindatud vaikimisi, see on nagu siis, kui te deklareerite int. See on täpselt sama asi. See on nagu kõik selle üksikud väljad võib olla prügi raha ta. >> Ja kas on võimalik määratleda - või kuulutada struct nii, et see initsialiseerida neid? [Bowden] Jah. Niisiis, otsetee initsialiseerimise süntaks läheb välja nägema - On kaks võimalust saame seda teha. Ma arvan, et me peaksime koostama selle veenduda rõkkama ka teeb seda. Selleks argumente, et tegemist on struct, paned nagu järjekorras argumendid sees need looksulg. Nii et kui sa tahad initsialiseerida ta kuni 9 ja lahkus olema null ja siis õige olema null, oleks 9, null, null. Alternatiiviks on, ja toimetaja ei meeldi see süntaks, ja see arvab, et ma tahan uut plokki, kuid alternatiiv on midagi - siin, ma panen selle uuele reale. Võite selgesõnaliselt öelda, ma unustan täpne süntaks. Nii saab selgesõnaliselt käsitleda neid nimepidi, ja öelda, . C, või. Väärtus = 9. Vasak = NULL. Ma arvan, neid tuleb komadega. . Õigus = NULL, nii et see, kuidas sa ei tegelikult on vaja teada selleks, et struct, ja kui sa loed seda, see on palju selgem mida väärtus kuramuse initsialiseeritud. 

See juhtub olema üks neist asjadest, mis - jah, enamasti, C + + on ülemhulk C. Te võite võtta C-koodi, liigutada üle C + +, ja see peaks koostama. See on üks asju, mis C + + ei toeta, nii et inimesed kipuvad seda mitte teha. Ma ei tea, kas see on ainus põhjus, miks inimesed kipuvad seda mitte teha, kuid juhul, kui mul on vaja seda kasutada vajalikud tööd C + + ja ma ei saanud seda kasutada. Teine näide millestki, mis ei tööta koos C + + on kuidas malloc tagastab "void *," tehniliselt, aga sa võiksid öelda, char * x = malloc iganes, ja see automaatselt enamus char *. See automaatne valatud ei juhtu C + +. See ei kompileerida, ja sa selgelt vaja öelda char *, malloc, mis iganes, et enamus seda char *. Ei ole palju asju, C ja C + + on eriarvamusel, kuid need on kaks. Nii et me läheme selle süntaks. Aga isegi kui me ei läinud selle süntaks, Mis on - võib olla valesti seda? [Student] Ma ei pea dereference on? >> Jah. Pea meeles, et nool on kaudne dereference, ja nii kui me lihtsalt tegelevad struct, tahame kasutada. nöökima valdkonnas sees struct. Ja ainus kord me kasutame nool on siis, kui me tahame teha - Noh, nool on samaväärne - see on, mida see oleks tähendanud, kui ma kasutasin nool. Kõik nool abil on, dereference seda, nüüd ma olen struct, ja ma saan valdkonnas. Kas saan valdkonna otseselt või dereference ja saad valdkonnas - Ma arvan, et see peaks olema väärtus. Aga siin ma olen tegelevad ainult struct, ei viida struct, ja seega ei saa ma kasutada noolt. Aga selline asi, mida me teha kõik sõlmed. Oh jumal. See on 6, 7, ja 3. Siis saame luua filiaale meie puu, meil on 7 - Me võime olla oma vasaku peaks punkt 3. Niisiis, kuidas me seda teeme? [Õpilased, arusaamatult] >> Jah. Aadress node3, ja kui sa ei ole aadressi, siis see lihtsalt ei kompileerida. Kuid pidage meeles, et need on viiteid, et järgmisel keskused. Õigus peab osutama 9, ja 3 tuleks märkida õiguse kohta 6. Minu arvates on see kõik komplekti. Kommentaare või küsimusi? [Student, arusaamatult] root saab olema 7. Me ei saa lihtsalt öelda sõlme * ptr = või juurtest, = & node7. 

Meie eesmärkide läheme tegelema sisestada, nii me ei kavatse tahan kirjutada funktsiooni lisada see kahendpuu ja insert ei paratamatult helistada malloc luua uus sõlm seda puud. Nii et asjad ei hakka räpane sellega, et mõned sõlmed on praegu korstnat ja muude sõlmede ei kavatse end sisse hunnik kui me lisada neid. See on täiesti õige, aga ainus põhjus suudame seda teha korstnat sest see on selline kunstlik näide, et me teame puu peaks olema ehitatud 7, 3, 6, 9. Kui me ei ole seda, siis me ei pea malloc esimese koha. Nagu me näeme veidi hiljem, peaksime malloc'ing. Praegu on see täiesti mõistlik panna virna, kuid olgem muuta seda malloc rakendamist. Nii et kõik need on nüüd saab olema midagi sellist sõlme * node9 = malloc (sizeof (node)). Ja nüüd me hakkame tegema meie kontrolli. if (node9 == NULL) - Ma ei tahtnud, et - tagasi 1, ja siis me saame teha node9-> aga nüüd on asi pointer, väärtus = 6, node9-> left = NULL, node9-> right = NULL, ja me kavatseme pea seda tegema iga nende sõlmede. Nii et selle asemel, paneme selle sees eraldi funktsioon. Nimetagem seda sõlme * build_node, ja see on mõnevõrra sarnane APIs me ette Huffman kodeerimine. Anname sulle initializer funktsioone puu ja deconstructor "funktsioonid" need puud ja sama metsad. 

Nii et siin me lähed on initializer funktsioon lihtsalt ehitada sõlm meile. Ja see läheb vaatama üsna täpselt niimoodi. Ja ma isegi saab olema laisk ja ei muuda muutuja nimi, kuigi node9 ei ole mõtet enam. Oh, ma arvan node9 väärtust ei oleks pidanud 6. Nüüd saame tagasi node9. Ja siin me peaks tagasi null. Igaüks kokku leppida, et build-sõlme funktsioon? Nii et nüüd me võime lihtsalt helistada, et ehitada ükskõik sõlm antud väärtuse ja null suunanäitajaks. Nüüd on võimalik helistada, et me saame teha sõlme * node9 = build_node (9). Ja teeme. . . 6, 3, 7, 6, 3, 7. Ja nüüd me tahame luua sama suunanäitajaks, välja arvatud nüüd kõik on juba nii viiteid nii ei pea enam aadressi. Okei. Mis siis viimane asi, mida ma tahan teha? Seal on viga kontrollimise et ma ei tee. Mis ehitada sõlm tagasi? [Student, arusaamatult] >> Jah. Kui malloc ebaõnnestus, siis see tagastab null. Nii et ma lähen laisalt pane see alla siit asemel teeb tingimus iga. Kui (node9 == NULL, või - veelgi lihtsam see võrdub lihtsalt kui ei node9. Nii et kui ei node9 või mitte node6 või mitte node3 või mitte node7, return 1. Ehk peaksime printida malloc kukkunud, või midagi. [Student] Kas vale võrdne tühjaks ka? [Bowden] Iga null väärtus on väär. Nii et null on null. Null on null. Väär on null. Kõik - päris palju ainult 2 null väärtused on null ja null, vale on vaid räsi määratletud nulli. Sama kehtib ka siis, kui me tunnistada globaalne muutuja. Kui meil oli sõlme * juur siin, siis - kena asi globaalsed muutujad on see, et neil on alati algväärtusest. See pole tõsi funktsioone, kuidas sees siin kui meil on, nagu, sõlme * või sõlme x. Meil pole aimugi, mida x.value, x.whatever, või me võiks neid printida ja need võiksid olla meelevaldne. See pole tõsi globaalsed muutujad. Nii sõlme juur või sõlme x. Vaikimisi kõike, mis on globaalne, kui ei ole selgesõnaliselt vormindatud mõne väärtuse, on null, nagu selle väärtust. Nii et siin, sõlme * juur, me ei ole sõnaselgelt initsialiseerida ta midagi, nii selle vaikimisi väärtus on null, mis on null väärtusega viiteid. Vaikimisi väärtus x läheb tähenda, et x.value on null, x.left on null, ja x.right on null. Nii et kuna see on struct kõik väljad struct on null väärtused. Meil ei ole vaja kasutada, et siin küll. [Student] structs on teistsugune kui teised muutujad ja teised muutujad prügi väärtused, need on nullid? [Bowden] Muud väärtused liiga. Nii x, x on null. Kui see on globaalse ulatusega, see on esialgne väärtus. >> Okei. [Bowden] Kas algväärtus sa andsid see või null. Ma arvan, et hoolitseb see kõik. 

Okei. Nii et järgmine osa küsimus küsib, "Nüüd tahame kirjutada funktsioon nimega sisaldab koos prototüüp bool sisaldab int väärtust. " Me ei kavatse seda teha bool sisaldab int väärtust. Meie prototüüp hakkab välja nägema bool sisaldab (int väärtust. Ja siis me ka läheb andke seda puud et tuleb kontrollida, kas see on see väärtus. Nii sõlme * puu). Okei. Ja siis me nimetame seda midagi, äkki me tahame printf või midagi. Sisaldab 6, meie juurtest. See peaks tagastama ühe või tõsi, samas sisaldab 5 juur peaks tagasi false. Nii et mõtle hetk rakendada seda. Sa suudad seda teha kas korduvalt või rekursiivselt. Tore asi, kuidas me oleme seatud asju on see, et see väärib meie rekursiivne lahendus palju lihtsam kui globaalne muutuja viis tegid. Sest kui me lihtsalt peame sisaldab int väärtus, siis on meil kuidagi recursing alla subtrees. Me oleks pidanud olema eraldi abistaja funktsiooni, et recurses alla subtrees meile. Aga kuna oleme muutnud teda võtma puu argumendina, mida ta oleks pidanud alati olnud esimene koht, nüüd saame recurse kergemini. Nii iteratiivne või rekursiivne, läheme üle nii, kuid eks me näeme, et rekursiivne jõuab on üsna lihtne. Okei. Kas kellelgi on midagi, mida me saame töötada koos? 

[Student] Mul iteratiivne lahendus. >> Olgu, iteratiivne. Okei, see näeb hea välja. Niisiis, tahan jalutada meid läbi on? [Student] Muidugi. Nii seadsin temp muutuja saada esimese sõlme puu. Ja siis ma lihtsalt looped läbi samas temp ei võrdu null, Niisiis, kui oli veel puu, ma arvan. Ja kui väärtus on võrdne väärtusega, mis temp on suunaga, siis ta tagastab selle väärtuse. Vastasel juhul kontrollib ta, kas see on paremal või vasakul poolel. Kui teil kunagi olukorda, kus pole rohkem puu, siis tagastab - see väljub silmuse ja tagastab false. [Bowden] Okei. Nii et tundub hea. Igaüks on mingeid kommentaare midagi? Mul ei ole õigsuse kommentaarid üldse. Üks asi, mida me teha saame, on see kutt. Oh, see saab minna veidi piklikud. Ma teen selle ära. Okei. 

Igaüks peaks mäletama, kuidas kolmekomponentsete töötab. Seal on kindlasti olnud viktoriinid varem mis annavad teile funktsiooni kolmekomponentsete operaator, ja öelda, tõlkida see, midagi, mis ei kasuta kolmekomponentsete. Nii et see on väga levinud korral, kui ma arvaks, et kasutada kolmekomponentsete, kus kui mõned tingimus muutuja midagi, veel seatud, et sama muutuja midagi muud. See on midagi, mis väga sageli saab muuta selline asi kus määrata selle muutuja sellele - või, noh, see on tõsi? Siis see, muidu see. [Student] Esimene neist on, kui tõsi, eks? [Bowden] Jah. Kuidas ma alati lugeda on, temp on võrdne väärtus on suurem kui temp väärtus, siis see, teine ​​see. Ta küsib küsimuse. Kas see suurem? Siis tehke esimene asi. Else teha teine ​​asi. Ma peaaegu alati - koolon, ma lihtsalt - minu peas, ma lugesin nagu teisedki. 

Kas kellelgi on rekursiivne lahendus? Okei. See üks me läheme - see võib juba olla suur, kuid me ei kavatse muuta see veelgi parem. See on päris palju sama täpne ettekujutus. See on lihtsalt, noh, sa tahad selgitada? [Student] Muidugi. Nii et me veenduge, et puu ei ole null esimene, sest kui puu on null siis see läheb tagasi false, sest me ei leidnud seda. Ja kui seal on veel puu, me minna - me kõigepealt kontrollida, kui väärtus on praeguse sõlme. Tagasi true, kui see on, ja kui me ei püsi arhiivi vasakul või paremal. Kas see hea asjakohane? >> Mm-hmm. (Leping) Nii märkate, et see on peaaegu - struktuurilt väga sarnane iteratiivne lahendus. See on lihtsalt, et selle asemel recursing, meil oli samas silmus. Ja tugipunkti siin, kus puud ei võrdu null oli olukord, milles me puhkes samas silmus. Nad on väga sarnased. Aga me viime selle ühe sammu edasi. Nüüd me teeme sama asja siin. Teade me jälle sama asi nii nendel liinidel, välja arvatud üks argument on erinev. Nii et me ei kavatse teha seda arvesse kolmekomponentsete. I hit võimalus midagi, ja see tegi sümbol. Okei. Nii et me ei kavatse naasta sisaldab seda. See hakkab olema mitu rida, noh, suumitud on. Tavaliselt stilistilise asi, ma ei usu paljud inimesed Pane ruumi pärast nool, aga ma arvan, et kui sa oled järjekindel, kõik on korras. Kui väärtus on väiksem kui puu väärtus, me tahame recurse puude vasakule, muidu me tahame recurse puude õigus. Nii et oli järgu muuta see otsima väiksem. Teine etapp muuta see otsima väiksem - saame lahutada selle mitmele reale. Okei. Teine etapp on teha näida väiksem on siin, nii tagastatav väärtus võrdub puu väärtus, või sisaldab mis iganes. 

See on oluline asi. Ma ei ole kindel, kas ta seda ütles selgesõnaliselt klassis, kuid seda nimetatakse lühis hindamine. Mõte on väärtus == puu väärtus. Kui see on tõsi, siis see on tõsi, ja me tahame "või" mis iganes on siin. Nii et ilma isegi mõelda mis iganes on siin, Mis on kogu avaldis kavatse naasta? [Student] tõsi? >> Jah, sest tõsi on midagi, or'd - või tõsi or'd midagi on tingimata tõsi. Nii et niipea kui me näeme tagastatav väärtus = puu väärtus, me lihtsalt läheb tagasi tõsi. Isegi ei kavatse recurse sisaldab täiendavalt sätestatakse rida. Me ei saa võtta see üks samm edasi. Tagasi puu ei võrdu null ja kõik see. Ta tegi seda üks rida funktsioon. See on ka näide lühis hindamine. Aga nüüd on see sama mõte - asemel - nii et kui puud ei võrdu null - või, noh, kui puu ei võrdne null, mis on halb juhul, kui puu võrdub null, siis esimene tingimus saab olema vale. Nii et vale anded midagi saab olema mida? [Student] False. >> Jah. See on teine ​​pool lühis hindamine, kus kui puu ei võrdne null, siis me ei kavatse isegi minna - või kui puu ei võrdne null, siis me ei kavatse teha raha == puu väärtus. Me lihtsalt läheb kohe tagasi false. Kumb on olulisem, sest kui ta ei lühis hinnata siis, kui puud ei võrdne null, see teine ​​tingimus läheb SEG süü, sest puu-> väärtus viite mahavõtmine null. Nii et see on. Kas teha seda - vahetustega kord üle. See on väga levinud asi ka, ei tee see üks Vastavalt sellele, aga see on tavaline asi tingimustes, võibolla mitte siin, aga kui (puu! = NULL, ja puu-> väärtus == väärtus), mida iganes. See on väga üldine seisund, kus selle asemel, murda kaheks IFS, kus meeldib, on puu null? Okei, see ei ole null, nii et nüüd on puu maksumus on võrdne väärtus? Tehke seda. Selle asemel, see tingimus, see ei saa kunagi seg süü sest see puhkeb, kui see juhtub olema null. Noh, ma arvan, kui teie puu on täiesti vale pointer, see saab ikka seg süü, kuid see ei saa seg süü, kui puu on null. Kui see oleks null, see murraks enne sa kunagi dereferenced kursor esimese koha. [Student] Kas see nn laisk hindamine? 

[Bowden] Lazy hindamine on eraldi asi. Lazy hindamine on rohkem nagu te küsite väärtus, te küsite väärtust arvutada, millist, aga sa ei pea seda kohe. Nii et kuni te tegelikult vaja, siis ei hinnata. See ei ole täpselt sama asi, kuid Huffman pset, ta ütleb, et me "laisalt" kirjutada. Põhjus, miks me seda teha on, sest me tegelikult puhverdusvõime kirjutada - me ei taha, et kirjutada üksikute bitti korraga, või üksikute baiti korraga, me asemel tahad tüki baiti. Siis kui meil on patakas baiti, siis me kirjutame selle välja. Kuigi te küsite seda kirjutada - ja ümbernimetamisel nimega ja fread teha sama asi. Nad puhverdada oma loeb ja kirjutab. Kuigi te küsite seda kirjutada kohe, siis ilmselt mitte. Ja sa ei saa olla kindel, et asjad hakkavad olema kirjutatud kuni helistate hfclose või mis iganes see on, mis siis ütleb, okei, ma sulgemise minu faili see tähendab, et ma parem kirjutan kõik, mida ma ei ole kirjutanud veel. Tal ei ole vaja kirjutada kõike välja kuni sulgete faili ning siis peab. Nii et see just see, mida laisk - ta ootab, kuni see peab juhtuma. See - võtta 51 ja lähete sinna üksikasjalikumalt, sest ocaml ja kõik 51, kõik on rekursioon. Puuduvad iteratiivne lahendusi, põhimõtteliselt. Kõik on rekursioon, ja laisk hindamine saab olema oluline palju asjaolusid kus, kui sa ei laisalt hinnata, see tähendab - Näiteks on ojad, mis on lõpmatult pikk. Teoreetiliselt sa ei mõtle füüsilised näitajad nagu oja 1-2-3-4-5-6-7, Nii laisalt hinnatud asjad on ilusad. Kui ma ütlen, ma tahan 10. number, siis saan ma hinnata kuni 10. number. Kui ma tahan sajandik number, siis saan ma hinnata kuni sajandik arv. Ilma laisk hindamine, siis see saab püüda hinnata kõik numbrid kohe. Sa hindamiseks lõpmata palju numbreid ja et lihtsalt ei ole võimalik. Seega on palju olukordi, kus laisk hindamine on lihtsalt oluline, et saada asju teha. 

Nüüd tahame kirjutada sisestada kus insert saab olema Samamoodi muutub selle määratluses. Nii et just nüüd on see bool sisestada (int väärtus). Me muudame seda, et kuni bool sisestada (int väärtus, sõlme * puu). Me tegelikult muudame et jälle natuke, näeme miks. Ja liigume build_node, lihtsalt kuradit see, Ülaltoodud sisestada nii et me ei pea kirjutama funktsiooni prototüüp. Mis on vihje, et sa kavatsed kasutada build_node lisamis. Okei. Võtke minut eest. Ma arvan, et ma päästsin vaadata, kui sa tahad tõmmata sellest, või vähemalt ma tegin nüüd. Tahtsin veidi pausi mõelda loogika sisestada, kui te ei saa mõelda. Põhimõtteliselt te ainult kunagi sisestamist kell lehed. Nagu, kui ma sisestan 1, siis ma paratamatult tuleb lisada 1 - Ma muudan must - Tulen lisada 1 üle siin. Või kui ma sisestan 4, ma tahan olla sisestades 4 üle siin. Nii et ükskõik mida sa teed, sa lähed tuleb lisada kell lehed. Kõik, mida selleks vaja on itereerima puu otsast alla kuni jõuad sõlme et peaks olema sõlme vanem, uus sõlm vanem, ja siis muuda oma vasakule või paremale kursor sõltuvalt sellest, kas see on suurem või väiksem kui praegune tipp. Muutus et osuti juhtida teie uus sõlm. Nii itereerima puu otsast alla, teevad lehed käsk uus sõlm. Mõelge ka, miks see keelab sellisesse olukorda enne, kus ma ehitatud kahendpuu, kus see oli õige kui te ainult vaatasin ühe sõlme, kuid 9 oli vasakul 7, kui sa pidasid maha kogu tee. Nii et see on võimatu selle stsenaariumi, sest - arvad sisestamist 9 või midagi; päris esimese sõlme, Ma lähen, et näha 7 ja ma lihtsalt lähen paremale. Nii et ükskõik, mida ma teen, kui ma lisada minnes lehed, ja lehed, kasutades sobivat algoritmi, see saab olema võimatu mul sisestada 9. vasakul 7. sest niipea kui ma tabanud 7 Ma lähen paremale. Kas kellelgi on midagi alustada? [Student] mina. >> Muidugi. [Student, arusaamatult] [Other üliõpilane, arusaamatult] [Bowden] See on teretulnud. Okei. Tahad seletada? 

[Student] Kuna me teame, et me olime lisades uus sõlmede lõpus puu, Ma looped läbi puu iteratiivselt kuni ma sain sõlme, mis osutas tühjaks. Ja siis ma otsustasin panna see kas paremal või vasakul kasutavad seda õigust muutuja; ta ütles mulle, kuhu panna seda. Ja siis sisuliselt, ma lihtsalt tegin, et viimane - et temp sõlme käsk uus sõlm, et ta lõi, kas vasakul või paremal pool, sõltuvalt sellest, mida raha õige oli. Lõpuks seadsin uue sõlme väärtusega oma katse. [Bowden] Okei, nii et ma näen üks küsimus siin. See on nagu 95% teel sinna. Üks küsimus, mida ma näen, noh, ei keegi teine ​​näha probleemi? Mis on asjaolu, mille alusel nad murda läbi silmuse? [Student] Kui temp on null? >> Jah. Niisiis, kuidas sa murda läbi silmuse on kui temp on null. Aga mida ma teen siin? Ma dereference temp, mis on paratamatult null. Nii teine ​​asi, mida pead tegema, on mitte ainult jälgida kuni temp on null, soovite jälgida vanem kogu aeg. Samuti tahame sõlme * vanem, ma arvan, suudame hoida, mis on null alguses. See saab olema imelik käitumine just puu, aga me jõuame selleni. Kui väärtus on suurem kui mis iganes, siis temp = temp õige. Aga enne kui me seda teeme, vanem = temp. Või on vanemad alati saab võrdne temp? Kas see on nii? Kui temp ei ole null, siis ma lähen liiguta alla, ükskõik mida, et sõlm, mille temp on vanem. Nii et vanem saab olema temp, ja siis ma liikuda temp alla. Nüüd temp on null, kuid lapsevanem võrra vanem asi, mis on null. Nii et siin all, ma ei taha seada paremale võrdub 1. Nii et kolisin õige, nii et kui õige = 1, ja ma arvan, et sa ka tahad teha - kui liigutad vasakule, mille soovite seada õige võrdne 0-ga. Või muidu, kui sa kunagi liikuda paremale. Nii et õige = 0. Kui õige = 1, nüüd me tahame teha vanema õigus osuti newnode, muidu me tahame teha vanema vasakul osuti newnode. Küsimused, mis? Okei. Nii et see on viis, kuidas me - noh, tegelikult, selle asemel et teha seda, me poolel oodata teil kasutada build_node. Ja siis kui newnode võrdub null, tagastab false. See on tehtud. Nüüd on see, mida me ootasime, et sa teeksid. 

See on see, mida töötajad lahendusi teha. Ma ei nõustu seda "õiget" teed läheb midagi kuid see on täiesti trahvi ja ta töötab. Üks asi, mis on natuke imelik praegu on kui puu hakkab välja nagu null, võtame aastal null puu. Ma arvan, et see sõltub sellest, kuidas määratleda käitumine läbivad null puu. Ma arvan, et kui te kaotate aastal null puu, siis sisestades väärtuse null puu peaks lihtsalt tagasi puu otsa, kus ainult raha on see, et ühe sõlme. Kas inimesed nõus? Sa võid, kui sa tahad, kui te kaotate aastal null puu ja soovite lisada väärtust sinna, tagastab false. See on kuni teil määrata see. Selleks esimene asi, mida ma ütlesin ja siis - Noh, sa lähed on hädas seda tehes, sest oleks lihtsam, kui meil oleks globaalne kursor asi, kuid me ei ole nii, kui puu on null, ei saa me midagi teha sellest. Me ei saa lihtsalt tagasi false. Nii et ma lähen muuta sisestada. Me tehniliselt võiks lihtsalt muuta see siin, kuidas see itereerimise asjade üle, aga ma lähen muuta sisestada võtta sõlme ** puu. Double suunanäitajaks. Mida see tähendab? Selle asemel tegelevad vihjeid tippu, asi, mida ma lähen tuleb manipuleerides on see pointer. Ma lähen tuleb manipuleerides see pointer. Ma lähen tuleb manipuleerides osuti otse. See on mõistlik, sest mõtle ette - Noh, praegu viitab see tühjaks. Mida ma tahan teha, on muuta seda osuti osutada ole null. Ma tahan, et see käsk minu uus sõlm. Kui ma lihtsalt jälgida viiteid minu suunanäitajaks, siis ma ei vaja jälgida vanem pointer. Võin vaid jälgida, et näha, kui kursor on suunaga null, ja kui kursor on suunaga null, muuda see käsk sõlme tahan. Ja ma ei saa seda muuta kuna mul on kursor pointer. Vaatame seda kohe. Võite tegelikult teha rekursiivselt üsna kergesti. Kas me tahame seda teha? Jah, mida me teeme. 

Vaatame seda rekursiivselt. Esiteks, milline on meie tugipunkt saab olema? Peaaegu alati meie tugipunkt, kuid tegelikult on see omamoodi keeruline. First things first, kui (puu == NULL) Ma arvan, et me lihtsalt läheb tagasi false. See erineb oma puu on null. See on kursor oma juur osuti on null mis tähendab, et teie juure osuti ei eksisteeri. Nii et siin all, kui ma sõlme * - olgem lihtsalt uuesti seda. Sõlme * root = NULL, ja siis ma lähen helistada sisestada tehes midagi, paigalda 4 sisse ja juur. Nii ja juur, kui juur on sõlm * siis & root saab olema sõlme **. See kehtib. Sel juhul puu, siin üleval, puu ei ole null - või sisesta. Siin. Puu ei ole null, * puu on null, mis on hea sest kui * puu on null, siis ma saan manipuleerida seda et nüüd juhtida sellele, mida ma tahan osutada. Aga kui puu on null, mis tähendab, et ma lihtsalt tulin siia ja ütles null. See ei ole loogiline. Ma ei saa midagi teha sellega. Kui puu on null, tagastab false. Nii et ma põhimõtteliselt juba öelnud, mida meie tõeline tugipunkt on. Ja mis see saab olema? [Student, arusaamatult] [Bowden] Jah. Nii et kui (* puu == NULL). See on seotud nii siia kus kui mu punane osuti on pointer Olen keskendunud, nii nagu ma olen keskendunud sellele pointer, nüüd olen keskendunud sellele kursor. Nüüd ma olen keskendunud sellele kursor. Nii et kui mu punane osuti, mis on minu sõlme ** on kunagi - kui *, minu punane osuti, on kunagi null, see tähendab, et ma olen juhul, kui ma keskendudes osuti, mis näitab - see on osuti, mis kuulub lehed. Ma tahan muuta see pointer osutada minu uus sõlm. Tule tagasi siia. Minu newnode oleks lihtsalt sõlme * n = build_node (väärtus) siis n, kui n = NULL, tagastab false. Else tahame muuta seda, mis kursor parasjagu osutades et nüüd näidata meie vastvalminud sõlme. Me ei saa tegelikult teha siit. Selle asemel, et öelda n, ütleme * puu = kui * puu. Igaühel aru? See käsitledes vihjeid suunanäitajaks, saame muuta null viiteid osutavad asju, mida me tahame, et nad osutavad. See on meie tugipunkt. 

Nüüd on meie kordumise, või meie rekursioon, saab olema väga sarnased kõigi teiste recursions oleme teinud. Me läheme soovite lisada väärtust, ja nüüd ma lähen kasutada kolmekomponentsete uuesti, kuid mida on meie seisund saab olema? Mis on see keda me otsime, et otsustada, kas me tahame minna vasakule või paremale? Teeme seda eraldi samme. Kui (väärtus <) mida? [Student] puu väärtus? [Bowden] Seega pidage meeles, et ma olen praegu - [Õpilased, arusaamatult] [Bowden] Jah, nii siin, ütleme, et see roheline nool on näide sellest, mida puu praegu on, on viit see pointer. See tähendab, ma olen kursor pointer 3. Dereference kaks korda kõlab hästi. Mida ma - kuidas ma seda teen? [Student] dereference kord ja tehke nool, et kuidas? [Bowden] Nii (* puu) on dereference kord, -> väärtus läheb mulle väärtus sõlme, et ma kaudselt osutavad. Ma võin ka kirjutada ** tree.value kui soovite, et. Kas töötab. Kui see on nii, siis ma tahan helistada sisestada väärtusega. Ja mis on minu uuendatud sõlme ** läheb? Ma tahan minna vasakule, nii ** tree.left saab olema minu vasakul. Ja ma tahan kursorit, et asi nii et kui vasakule jõuab on null pointer, Ma ei muuda see käsk minu uus sõlm. 

Ja teisel juhul võib olla väga sarnane. Olgem tegelikult teha, et minu kolmekomponentsete kohe. Sisesta väärtus kui väärtus <(** puu). Väärtus. Siis me tahame uuendada meie ** vasakule, muidu me tahame uuendada meie ** paremale. [Student] Kas see saame kursor pointer? [Bowden] Pea meeles, et - ** tree.right on sõlm täht. [Student, arusaamatult] >> Jah. ** Tree.right on nagu see pointer või midagi. Nii võttes kursorit, et see annab mulle, mida ma tahan on kursor, et kutt. [Student] Kas läheme jälle, miks me kasutame kahe viiteid? [Bowden] Jah. Nii et - ei, saad, ja et lahendus enne oli viis seda teha ilma teeb kahte suunanäitajaks. Sa pead aru saama kahe suunanäitajaks, ja see on puhtam lahendus. Samuti märkate, et mis juhtub, kui minu puu - Mis juhtub, kui juur oli null? Mis juhtub, kui ma seda juhul siin? Nii sõlme * root = NULL, paigalda 4 sisse ja juur. Mis on root saab olema pärast seda? [Student, arusaamatult] >> Jah. Juur väärtus saab olema 4. Juur vasakule saab olema null, juure õiguse saab olema null. Juhul kui me ei liigu juure aadressi järgi me ei saa muuta root. Juhul kui puu - kui juur oli null, me lihtsalt pidin tagasi false. Ei ole midagi mida me teha saame. Me ei saa sisestada sõlme tühja puu. Aga nüüd saame, me lihtsalt tühi puu ühtseks sõlme puu. Mis on tavaliselt oodatava nii, et see peaks töötama. 

Lisaks sellele on tunduvalt lühem kui Samuti jälgida, vanem, ja nii sa itereerima alla kogu tee. Nüüd on mul mu ema, ja ma lihtsalt pean oma vanema õigus kursor iganes. Selle asemel, kui me tegime seda korduvalt, see oleks sama idee samas silmus. Aga selle asemel, et tegeleda minu vanem pointer, selle asemel minu praegune pointer oleks asi et ma otseselt muuta punkti minu uus sõlm. Ma ei pea tegelema kas see on suunaga paremale. Ma ei pea tegelema kas see on suunatud paremale. See on lihtsalt mida iganes see pointer on, ma lähen, et seada see käsk minu uus sõlm. Igaüks aru, kuidas see töötab? Kui ei siis miks me tahame teha seda nii, aga vähemalt, et see töötab nagu lahendus? [Student] Kui me tagasi true? [Bowden] See on ilmselt siin. Kui me õigesti sisestada see, tagastab tõsi. Else, siia alla läheme soovivad naasta iganes sisestada tulu. 

Ja mis on eriline selle rekursiivne funktsioon? See on saba rekursiivne, nii kaua, kui oleme kompileerida mõned optimeerimine, see on arusaadav, et ja te ei saa kunagi korstnat ülevoolu sellest, isegi kui meie puu on kõrgus 10.000 või 10 miljonit. [Student, arusaamatult] [Bowden] Ma arvan, et see on kriips - või mida optimeerimine tasemel on vaja saba rekursioon olla tunnustatud. Ma arvan, et ta tunnustab - GCC ja rõkkama Samuti on erinev tähendus nende optimeerimise tase. Ma tahan öelda, et see DashO 2 kindlasti, et see tunneb saba rekursioon. Aga me - võid ehitada nagu Fibonocci näiteks või midagi. See ei ole lihtne test selle, sest see on raske ehitada kahendpuu, et on nii suur. Aga jah, ma arvan, et see DashO 2, et kui sa kompileerida koos DashO 2, siis otsima saba rekursioon ja optimeerida selle välja. Lähme tagasi - sisestage on sõna otseses mõttes viimane asi, mida ta vajab. Lähme tagasi sisesta siia kus me ei kavatse teha sama mõte. Seda saad veel viga, et ei olda võimelised täielikult hakkama kui juur ise on null, või viimase kirje on null, kuid selle asemel tegelevad vanem pointer, olgem rakendada sama loogikat hoides vihjeid suunanäitajaks. Kui siin me hoiame sõlme ** ub, ja me ei vaja jälgida õige enam kuid sõlme ** viim = & puu. Ja nüüd meie ajal ahela saab olema samas * viim ei võrdu null. Ei ole vaja jälgida vanemad enam. Ei ole vaja jälgida vasakule ja paremale. Ja ma nimetan seda temp, sest me juba kasutate temp. Okei. Nii et kui (väärtus> * temp), siis & (* temp) -> õigus muidu temp = & (* temp) -> vasakule. Ja nüüd, sel hetkel, pärast seda kui silmus, Ma ainult seda teha, sest võibolla on lihtsam mõelda iteratiivselt kui rekursiivselt, kuid pärast seda, kui silmus, * Temp on pointer me tahame muuta. 

Enne oli meil vanem, ja me tahtsime muuta kummagi vanema vasakule või vanem õigus, kuid kui me tahame muuta vanema õigus, siis * temp on vanem õigus, ja me ei muuda seda otse. Nii et siin all, me saame teha * temp = newnode, ja ongi kõik. Nii teate, kõik me tegime seda oli võtta rida koodi. Et jälgida vanem kõik, mis on täiendavaid jõupingutusi. Siin, kui me lihtsalt jälgida kursor pointer, ja isegi kui me tahtsime saada lahti kõik need looksulg nüüd, Tee vaata lühem. See on praegu täpselt sama lahendus, kuid vähem rida koodi. Kui hakkate tunnustades seda kehtiv lahendus, see on ka lihtsam põhjus umbes kui näeb, okei, miks ma pean seda lippu int eks? Mida see tähendab? Oh, see on see tähendaks, et iga kord ma lähen paremale, mul on vaja seada see, muidu kui ma lähen jäänud mul vaja seada nulli. Siin ma ei pea põhjus sellest, see on lihtsalt lihtsam mõelda. Küsimused? [Student, arusaamatult] >> Jah. Okei, nii et viimase natuke - Ma arvan, et üks kiire ja lihtne funktsioon saame teha, on, let's - koos, ma arvan, püüa kirjutada sisaldab funktsiooni mis ei hooli, kas see on Kahendotsingupuu. See sisaldab funktsiooni peaks tagasi tõsi kui kuskil sellises üldises kahendpuu on väärtus me otsime. So let esimene seda rekursiivselt ja siis me teeme seda korduvalt. Me ei saa tegelikult lihtsalt teeme seda koos, sest see saab olema tõesti lühike. 

Mis on minu tugipunkt saab olema? [Student, arusaamatult] [Bowden] Nii et kui (puu == NULL), siis mida? [Student] Tagasi vale. [Bowden] Else, noh, ma ei vaja muud. Kui oli minu teisi tugipunkti. [Student] Tree väärtus? >> Jah. Nii et kui (puu-> väärtus == väärtus. Teade me oleme tagasi sõlme *, mitte sõlme ** s? Sisaldab kunagi vaja kasutada sõlme ** kuna me ei muuda suunanäitajaks. Me lihtsalt liiklevad neid. Kui see juhtub, siis me tahame naasta tõsi. Else tahame läbida lapsed. Nii et me ei saa arutleda selle üle, kas kõik vasakule on vähem ja kõike paremal on suurem. Mis on meie seisund saab olema siin - või Mida me nüüd teeme? [Student, arusaamatult] >> Jah. Tagasi sisaldab (väärtus, puu-> vasak) või sisaldab (väärtus, puu-> paremal). Ja ongi kõik. Ja märkate seal on mõned lühis hindamine, kus kui me juhtub, et leida väärtus vasak puus, me kunagi vaja vaadata õige puu. See on kogu funktsiooni. Nüüd teeme seda korduvalt, mis saab olema vähem kena. Võtame tavalise algust sõlme * viim = puu. Kuigi (viim! = NULL). Kiiresti näeme probleemi. Kui viim - siin, kui me kunagi murda läbi selle, siis me oleme otsa asju vaadata, nii tagastab false. Kui (viim-> väärtus == väärtus) tagasi true. Nüüd oleme kohas - me ei tea, kas me tahame minna vasakule või paremale. Nii suvaliselt, lihtsalt vasakule. Ma olen ilmselt tekib küsimus, kus ma olen täiesti loobunud kõigest - Ma ainult kunagi kontrollida vasakul puu. Ma ei ole kunagi näha midagi, mis on õige laps midagi. Kuidas seda parandada? [Student] Sa pead hoidma silma peal vasakule ja paremale pinu. [Bowden] Jah. Nii et teeme seda struct nimekirja, sõlme * n ja siis sõlm ** edasi? Ma arvan, et toimib hästi. Tahame minna üle vasaku, või let's - siin. Struct list =, siis saad alustada läbi see struct nimekirja. * List = NULL. Nii et see saab olema meie seotud nimekirja kohta subtrees et oleme hüpatakse üle. Me Traverse jäänud nüüd, kuid kuna me paratamatult vaja tulla tagasi paremale, Me läheme hoida paremale küljele sees meie struct nimekirja. Siis me peame new_list või struct, struct nimekiri *, new_list = malloc (sizeof (nimekiri)). Ma lähen ignoreerida Tõrkekontroll, kuid siis tuleb vaadata, et näha, kas see on null. New_list sõlme see saab osutada - oh, sellepärast ma tahtsin seda siin üleval. See saab viidata teise struct nimekirja. See on lihtsalt, kuidas seotud nimekirju töö. See on sama, mis int seotud nimekirja välja arvatud me lihtsalt asendades int koos sõlme *. See on täpselt sama. Nii new_list, väärtus meie new_list sõlme, saab olema viim-> õigust. Väärtus meie new_list-> next saab olema meie esialgses nimekirjas, ja siis me läheme uuendama meie nimekirjas osutada new_list. 

Nüüd tuleb mingi viis tõmmates asju, nagu me oleme liiklevad kogu vasak alampuu. Nüüd tuleb tõmmata asju välja, nagu viim on null, me ei taha lihtsalt tagasi false. Me tahame nüüd tõmba väljaspool meie uus nimekiri. Mugav viis seda teha - noh, tegelikult, seal on mitmeid viise seda teha. Igaüks on ettepanekuid? Kui ma peaks seda tegema või kuidas ma peaks seda tegema? Meil on ainult paar minutit, kuid mingeid ettepanekuid? Selle asemel, et - üks võimalus, mitte meie tingimus on samas, mida me praegu vaadates ei ole null, selle asemel me kavatseme jätkata minna kuni meie nimekirja ise on null. Nii et kui meie nimekirjas jõuab on null, siis oleme otsa asju otsima, et otsida üle. Aga see tähendab, et esimene asi, mida meie nimekiri on lihtsalt saab olema esimese sõlme. Kõige esimene asi on - me ei pea enam näha. Nii list-> n on meie puu. list-> next saab olema null. Ja nüüd samas nimekirjas ei võrdu null. Cur läheb tõmmata midagi meie nimekirjast. Nii viim läheb võrdne list-> n. Ja siis nimekiri läheb võrdne list-> n, või nimekiri-> next. Nii et kui viim väärtus on võrdne väärtus. Nüüd saate lisada nii meie õigus osuti ja meie vasak pointer nii kaua, kui nad ei ole null. Alla siin, ma arvan, et me oleks pidanud tegema, et esimene koht. Kui (viim-> right! = NULL) siis me lisada, et sõlm meie nimekirjas. Kui (viim-> vasak), see on natuke lisatööd, kuid kõik on korras. Kui (viim-> vasakule! = NULL), ja me kavatseme lisada vasakul meie seotud nimekirja, ja see peaks olema see. Me itereerima - nii kaua, kui meil on midagi meie nimekirja, meil on veel üks sõlm vaadata. Nii et vaatame, mis sõlme, meil edendada meie nimekirjas järgmise juurde. Kui see sõlm on väärtus me otsime, saame tagasi true. Else sisestada nii meie vasak ja parem subtrees, nii kaua, kui nad ei ole null, meie nimekiri nii et me paratamatult minna nende üle. Nii et kui nad ei ole null, kui meie juurtest osuti osutas kaks asja, siis meil esimest korda tõmbas midagi välja nii meie nimekirjas jõuab on null. Ja siis me paneme kaks asja tagasi, nii et nüüd meie nimekirjas on suurus 2. Siis läheme silmus varundada ja me lihtsalt läheb vedama, oletame, vasak osuti meie juurest sõlme. Ja see muudkui juhtub; me lõpuks silmuspõletamise üle kõike. 

Pange tähele, et see oli oluliselt keerulisem aastal rekursiivne lahendus. Ja ma olen öelnud mitu korda et rekursiivne lahendus on tavaliselt palju ühist iteratiivne lahendus. Siin see on täpselt, mida rekursiivne lahendus teeb. Ainus muudatus on see, et selle asemel, et vaikimisi kasutades korstna programmi stack, nagu oma viis jälgida, mida sõlmed ikka on vaja külastada, nüüd sa pead selgesõnaliselt kasutada seotud nimekirja. Mõlemal juhul te jälgida, mida sõlm tuleb veel külastatud. Kui rekursiivne juhul on siis lihtsam, sest korstnat rakendatakse teile kui programmi pinu. Pange tähele, et see on seotud nimekirja, siis on pinu. Mida me lihtsalt panna virna on kohe, mida me ei kavatse peatähelepanu korstnat külastada kõrval. Meil on aeg otsas, kuid mingeid küsimusi? [Student, arusaamatult] [Bowden] Jah. Nii et kui meil on seotud nimekirja, Praegune läheb käsk see kutt, ja nüüd me lihtsalt edendades seotud nimekirja keskenduda sellele mehele. Me liiklevad üle lingitud nimekiri, et liin. Ja siis ma arvan, et me peaks vabastama meie seotud nimekirja ja värki kord naasid õige või vale, peame itereerime meie lingitud nimekiri ja alati siin, ma arvan, kui me viim õigus ei võrdu, lisab ta, et nüüd me tahame vabastada viim sest, noh, me tegime täiesti unustada nimekirja? Jah. Nii see on, mida me tahame teha siin. Kus pointer? Val oli siis - me tahame struct nimekiri * 10 võrdub nimekirja kõrval. Tasuta nimekiri, loend = temp. Ja juhul, kui me tagasi true, me peame itereerima üle ülejäänud meie seotud nimekirja vabastades asju. Tore asi rekursiivne lahendus on vabastamist asjad tähendab lihtsalt popping factorings maha korstnat, mis juhtub teile. Nii oleme läinud midagi, mis on nagu 3 rida raskesti arvan, umbes kood midagi, mis on oluliselt palju rohkem hard-to-arvan-umbes rida koodi. Kas veel küsimusi? Hea küll. Oleme hea. Nägemist! [CS50.TV]