[Powered by Google Translate] [Sekcio 7: Pli Vasta] [Rob Bowden] [Universitato Harvard] [Jen CS50] [CS50.TV] Bone. Do kiel mi diris en mia retpoŝto, ĉi tiu tuj estos duuma arbo-intensivaj sekcio. Sed estas ne, ke multaj demandoj. Do ni provos kaj nudigos ĉiu demando kaj iru al dolora detalo de ĉiuj bonaj manieroj de fari tion. Do ĝuste en la komenco, ni iru tra specimeno desegnoj de duumaj arboj kaj aĵoj. Do jen, "Memoru ke duuma arbo havas nodoj simila al tiuj de ligitaj listo, krom anstataŭ unu puntero estas du: unu por la maldekstra 'infano' kaj unu por la rajto 'infano'. " Do duuma arbo estas simple kiel ligillisto, krom la struct tuj havos du punteros. Estas trinary arboj, kiuj estas tuj havas tri punteros, estas N-_ary_ arboj, kiuj nur devas genérico puntero ke vi tiam devas malloc esti sufiĉe granda por havi sufiĉe punteros al ĉiuj eblaj infanoj. Do duuma arbo ĝuste okazas havi konstantan numeron de du. Se vi volas, vi povas doni ligillisto kiel unuloka arbo, sed mi ne kredas al neniu nomas ĝin tiel. "Desegnu skatoloj-kaj-sagojn diagramon de binara arbo nodo enhavanta Nate preferataj numeron, 7, kie ĉiu infano puntero estas nula. " Do iPad modo. 

Ĝi tuj estos bela simpla. Ni nur havos nodo, mi desegnas ĝin kiel kvadrato. Kaj mi desegni la valorojn en ĉi tie. Do la valoro iros en tie, kaj tiam ĉi tie ni havos la maldekstra puntero sur la maldekstra kaj la dekstra puntero dekstre. Kaj estas tre tiom konvencio nomi ĝin maldekstren kaj dekstren la puntero nomoj. Ambaŭ tuj estos nula. Tio nur estas nula, kaj tio nur esti nula. Okay. Do apogi ĉi tien. "Kun ligitaj listo, ni nur devis stoki puntero al la unua nodo en la listo por memori la tuta ligitaj listo, aŭ la tuta listo. Same, kun arboj, ni nur devas stoki puntero al sola nodo por memori la tuta arbo. Ĉi nodo estas strato la 'radikon' el la arbo. Konstruu sur via diagramon de antaŭ aŭ desegni nova tia, ke vi havas skatolojn-kaj-sagojn priskribo de duuma arbo kun la la valoron 7, tiam 3 en la maldekstra, tiam 9 sur la dekstra, kaj tiam 6 dekstre de la 3. " Ni vidu se mi povas memori ĉiuj, ke en mia kapo. Do tiu tuj estos nia radiko tien. Ni havas iom puntero ie, iu kiun ni vokos radiko, kaj ĝin indikante ĉi ulo. Nun fari novan nodo, Kion ni havas, 3 en la maldekstra? Do nova nodo kun 3, kaj ĝi komence notas nula. Mi ĵus metis N. Nun ni volas fari tiu iru al la maldekstra de 7. Do ni ŝanĝi ĉi puntero nun notas al ĉi ulo. Kaj ni fari same. Ni volas 9 pli tie kiu komence nur diras nula. Ni tuj ŝanĝos ĉi pointer, punkto al 9, kaj nun ni volas meti 6 al la rajto de 3. Do tuj - fari 6. Kaj tiu ulo notos tie. Okay. Do jen ĉio petas al ni fari. 

Nun ni iru super iu terminaro. Ni jam parolis pri kiel la radiko de la arbo estas la supre-pli nodo en la arbo. Tiu, kiu enhavis 7. La nodoj ĉe la malsupro de la arbo estas nomitaj la folioj. Ajna nodo kiu nur havas nula kiel liaj filoj estas folio. Do ĝi estas ebla, se nia duuma arbo estas nur simpla nodo, ke arbo estas folio, kaj tio estas ĝi. "La 'alteco' de la arbo estas la nombro de lupolo vi devas fari akiri de la supro al folio. " Ni ricevos en, en dua, la diferenco inter ekvilibrigita kaj desequilibradas duumaj arboj, sed nuntempe, la tuta alteco de ĉi tiu arbo Mi dirus estas 3, kvankam se oni kalkulu la numeron de lupolo vi devas fari por atingi al 9, tiam ĝi estas vere nur altecon de 2. Ĝuste nun ĉi tiu estas desequilibrado duuma arbo, sed ni parolis pri ekvilibra kiam alvenas al esti grava. Do nun ni povas paroli pri nodoj en arbo en terminoj relativa al la aliaj nodoj en la arbo. Do nun ni havas gepatrojn, infanojn, gefratoj, prapatroj, kaj posteuloj. Ili estas belaj komuna senco, kion ili signifas. Se ni petas - tio la gepatroj. Do kio estas la patro de 3? [Studentoj] 7. >> Jes. La patro estas ĝuste tuj estos kio notas al vi. Do kion estas la infanoj de 7? [Studentoj] 3 kaj 9. >> Jes. Rimarku ke "infanoj" laŭvorte signifas infanoj, tiel 6 ne apliki, ĉar ĝi estas kiel pranepo. Sed tiam, se ni iros posteuloj, do kio estas la posteuloj de 7? [Studentoj] 3, 6 kaj 9. >> Jes. La posteuloj de la radika vertico tuj estos ĉio en la arbo, krom eble la radika vertico mem, se vi ne volas konsideri ke posteulo. Kaj fine, prapatroj, do tio estas la kontraŭa direkto. Do kio estas la prapatroj de 6? [Studentoj] 3 kaj 7. >> Jes. 9 ne estas inkluditaj. Estas nur la rekta kasto reen al la radiko tuj estos viaj prapatroj. 

"Ni diros ke duuma arbo estas 'ordigitaj' se por ĉiu nodo en la arbo, ĉiuj liaj posteuloj maldekstre havas malpli valoroj kaj ĉiuj sur la dekstra havas pli granda valoroj. Ekzemple, la arbo super estas ordigita sed ĝi ne estas la sola ebla ordigita aranĝo. " Antaŭ ol ni atingos tion, ordigita duuma arbo estas konata ankaŭ kiel duuma serĉarbo. Ĉi tie ni okazi esti nomante ĝin ordigita duuma arbo, sed mi neniam aŭdis ĝin nomis ordita duuma arbo antaŭe, kaj sur kvizon ni estas multe pli emas meti duuma serĉarbo. Ili estas unu kaj la sama, kaj gravas vin rekoni la distingon inter duuma arbo kaj duuma serĉarbo. A duuma arbo estas nur arbo kiu antaŭ du aĵojn. Ĉiu nodo notas al du aĵoj. Ne estas rezonado pri la valoroj kiuj notas al. Do kiel ĉi tie, ĉar ĝi estas duuma serĉo arbo, Ni scias, ke se ni iros restis el 7, tiam ĉiuj el la valoroj kiujn ni povas eble atingi irante restis el 7 devas esti malpli ol 7. Rimarku ke ĉiuj valoroj malpli ol 7 estas 3 kaj 6. Tiuj estas ĉiuj maldekstre de 7. Se ni iras al la dekstra de 7, ĉio devas esti pli granda ol 7, tiel 9 estas dekstre de 7, tial ni estas bonaj. Ĉi tiu ne estas la kazo por duuma arbo, por regula duuma arbo povas nur havi 3 ĉe la supro, 7 al la maldekstra, 9 al la maldekstra de 7; ne estas ordo de valoroj ajn. Nun, ni ne vere faras tion, ĉar ĝi estas teda kaj nenecesa, sed "provi desegni multajn ordigis arboj kiel vi povas pensi pri uzante la numeroj 7, 3, 9, kaj 6. Kiom da distingaj aranĝoj estas tie? Kio estas la alteco de ĉiu tiu? " 

Ni faros paro, sed la ĉefa ideo estas, ĉi estas neniel unika prezento de duuma arbo kiu enhavas tiujn valorojn. Ĉiuj ni bezonas estas iuj duuma arbo kiu enhavas 7, 3, 6, kaj 9. Alia ebla valida tiu estus la radiko estas 3, iru al la maldekstra kaj ĝi estas 6, iru al la maldekstra kaj estas 7, iri al la maldekstra kaj estas 9. Tio estas perfekte valida duuma serĉarbo. Ne tre helpema, ĉar ĝi estas nur kiel ligitaj listo kaj ĉiuj el tiuj indikoj estas nur nula. Sed ĝi estas valida arbo. Yeah? [Studenta] Do ne la valorojn devas esti pli granda ĉe la dekstra? Aŭ ĉu tio -? >> Tiuj Mi intencis iri al la alia vojo. Ekzistas ankaux - jes, ni ŝanĝos tion. 9, 7, 6, 3. Bonan catch. Ĝi ankoraŭ devas obei kion duuma arbo serĉo supozas fari. Do ĉio al la maldekstra devas esti malpli ol iu donita vertico. Ni povus simple movi, diru, ĉi 6 kaj metis ĝin ĉi tie. Ne, ni ne povas. Kial mi daŭre fari tion? Ni do - jen 6, tie estas 7, 6 poentojn al 3. Ĉi tiu estas ankoraŭ valida duuma serĉarbo. Kio estas erara se mi - ni vidu se mi povas veni supren kun aranĝo. Yeah, okay. Do kio estas malbone en ĉi tiu arbo? Mi supozas Mi jam donis al vi aludo, ke estas io malĝusta kun ĝi. Kial mi daŭre fari tion? Okay. Ĉi aspektas racia. Se ni rigardas ĉiu nodo, kiel 7, tiam al la maldekstra de 7 estas 3. Do ni havas 3, la aĵo kiu estas dekstre de 3 estas 6. Kaj se vi rigardas 6, la afero dekstre de 6 estas 9. Do kial estas ĉi ne estas valida duuma serĉo arbo? [Studentoj] 9 estas ankoraŭ al la maldekstra de 7. >> Jes. Ĝi devas esti vera, ke ĉiuj valoroj povas eble atingi irante al la maldekstra de 7 estas malpli ol 7. Se ni iras restis el 7, ni atingos 3 kaj ni povas ankoraŭ atingos 6, ni povas ankoraŭ ricevi al 9, sed por esti irinta malpli ol 7, ni ne povos alveni al cifero kiu estas pli granda ol 7. Do tiu estas ne valida duuma serĉarbo. 

Mia frato efektive havis intervjuon demando kiu estis esence tion, nur kodo ion por validigi ĉu arbo estas duuma serĉo arbo, kaj do la unua kiu faris estis nur kontroli por vidi se la maldekstra kaj dekstra estas ĝustaj, kaj tiam persisti tie malsupre. Sed vi povas ne nur fari tion, vi devas konservi trako de la fakto ke nun ke mi foriris restis el 7, ĉio en ĉi subárbol devas esti malpli ol 7. La ĝentila algoritmo bezonas konservi trako de la baroj ke la valoroj povas eble falos in Ni ne iros tra ĉiuj el ili. Estas bela rekursieca rilato, kvankam ni ne alvenis al tiuj, aux ni ne atingos tiujn, difinanta kiom tie efektive estas. Do estas 14 el ili. La ideo pri kiel vi farus matematike estas kiel, vi povas elekti ajnan sola unu al esti la radiko nodo, kaj poste, se mi elektas 7 esti la radiko nodo, tiam estas, ekzemple, iuj nombroj kiu povas iri estos mia maldekstra nodo, kaj tie estas kelkaj nombroj kiuj povas esti mia dekstra nodo, sed se mi n tuta nombroj, tiam la kvanto kiu povas iri al la maldekstra plus la kvanto kiu povas iri al la rajto estas n - 1. Do el la ceteraj nombroj, ili devas povi iri ĉu al la maldekstra aŭ la dekstra. Ŝajnas malfacile, ke se mi metis 3 unuaj tiam ĉio devas iri al la maldekstra, sed se mi metis 7, tiam iuj aferoj povas iri la la maldekstra kaj iuj aĵoj povas iri al la rajto. Kaj por '3 unue 'I meant ĉiu povas iri al la rajto. Estas vere, vi nur devas pensi pri ĝi kiel, kiom da aferoj povas iri la sekvantan nivelon de la arbo. Kaj temas esti 14; aŭ vi povas desegni ĉiuj ili, kaj poste vi ricevos 14. 

Reiros tien, "Mastro duumaj arboj estas cool ĉar ni povas serĉi per ili en tre simila maniero serĉado super ordo tabelo. Por tion fari, ni komencu en la radiko kaj labori nia vojo laŭ la arbo al folioj, kontrolanta ĉiu nodo de valoroj kontraŭ la valoroj ni sercxas. Se la nuna nodo valoro estas malpli ol la valoro ni serĉas, vi iros apud la nodo la dekstra infano. Alie, vi iru al la nodo la maldekstra infano. En iu momento, vi jam estas trovi la valoro kiun vi serĉas, vi kuros en nula, indikante la valoro ne estas en la arbo. " Mi devas redesegni la arbo ni havis antaŭe; ke prenos duan. Sed ni volas serĉi ĉu 6, 10, kaj 1 estas en la arbo. Do kio estis, 7, 9, 3, 6. Okay. La nombroj vi volas rigardi supren, ni volas serĉi 6. Kiel funkcias tiu algoritmo laboro? Nu, ni ankaŭ havas iun radikon puntero al nia arbo. Kaj ni irus al la radiko kaj diru, estas tiu valoro egalas al la valoro ni sercxas? Do ni serĉas 6, tiel ĝi ne estas egalaj. Do ni observu tuj, kaj nun ni diras, bone, do 6 estas malpli ol 7. Ĉu tio signifas ke ni volas iri al la maldekstra, aŭ ĉu ni volas iri al la dekstra? [Studenta] Maldekstra. >> Jes. Estas signife pli facila, ĉiuj vi devas fari estas desegni unu ebla nodo de la arbo kaj tiam vi ne batu - anstataŭ klopodi pensi en via kapo, estas bone, se ĝi estas malpli, mi iros maldekstren aŭ iri dekstren, nur rigardante ĉi tiun foton, estas tre klara, ke mi devas iri al la maldekstra se ĉi tiu nodo estas pli granda ol la valoro kiu Mi serĉas. Do vi iras al la maldekstra, nun mi estas ĉe 3. Mi volas - 3 estas malpli ol la valoro Mi serĉas, kiu estas 6. Do ni iru al la dekstra, kaj nun mi finas je 6, kiu estas la valoro Mi serĉas, do mi revenos vera. La sekvan valoron mi iros serĉi estas 10. Okay. Do 10, nun, tuj - ekstermigxos tiu - tuj sekvu la radiko. Nun, 10 tuj estos pli granda ol 7, do mi volas rigardi al la rajto. Mi tuj venos ĉi tien, 10 tuj estos pli granda ol 9, do mi tuj volas rigardi al la rajto. Mi venis ĉi tien, sed ĉi tien nun mi estas ĉe nula. Kion mi faru se mi batis nula? [Studenta] Reveno falsa? >> Jes. Mi ne trovis 10. 1 tuj estos preskaŭ identa kazo, krom ĝi estas ĝuste tuj estos spegulita; anstataŭ serĉi malsupren la dekstra flanko, mi tuj rigardos la maldekstra flanko. 

Nun mi kredas ke ni fakte atingos kodo. Jen kie - malfermi la CS50 aparaton kaj navigi vian vojon tie, sed vi povas ankaŭ simple fari ĝin en la spaco. Estas probable ideala por fari ĝin en la spaco, ĉar ni povas labori en la spaco. "Unue ni bezonas novan tipon difino por duuma arbo nodo enhavanta int valoroj. Uzante la Boilerplate typedef sube, krei novan tipon difino por nodo en duuma arbo. Se vi pusxis. . . "Bla, bla, bla. Okay. Do ni metis la Boilerplate tie, typedef struct nodo, kaj nodo. Yeah, okay. Do kio estas la kampoj ni tuj volas en nia nodo? [Studenta] Mez kaj tiam du punteros? >> Mez valoro, du punteros? Kiel mi skribas la punteros? [Studenta] struct. >> Mi devus zoom in Yeah, do struct nodo * restis, kaj struct nodo * pravas. Kaj memoru la diskuto de la lasta fojo, ke tio ne havas senson, ĉi ne havas senson, ĉi ne havas senson. Vi bezonas cxion tie por difini ĉi rekursie struct. Okay, do tio estas kion niaj arbo tuj aspekti. Se ni faris trinary arbo, tiam nodo povus aspekti b1, b2, struct nodo * b3, kie b estas branĉo - fakte, mi pli aŭdas, ĝi forlasis mezo, rajto, sed kion ajn. Ni nur zorgas pri duuma, do bone, forlasis. "Nun deklari tutmonda nodo * variablo por la radiko de la arbo." Do ni ne faros tion. Por fari tion, iomete pli malfacila kaj pli ĝeneraligita, ni ne havas suman nodo variablo. Anstataŭe, en ĉefa ni rakontu pri cxiuj niaj nodo aferojn, kaj tio signifas ke sube, kiam ni komencos kuri nia enhavas funkcion kaj nia insert funkcio, anstataŭ nia enhavas funkcion nur uzante tiun tutmondan nodo variablo, ni havos ĝin prenu kiel argumento al la arbo, ke ni volas procesi. Havante la malloka variablo devis fari tion facile. Ni tuj faros tion pli malfacila. Nun prenu unu minuto aŭ tiel al nur fari ĉi tiajn aferojn, kie ene de ĉefa vi volas krei ĉi arbo, kaj jen ĉio vi volas fari. Provu kaj konstrui ĉi arbo en via ĉefa funkcio. 

Okay. Do, vi eĉ ne devos esti konstruinta la arbo en la tuta vojo ankoraŭ. Sed neniu havas ion mi povus tiri supren por montri kiel oni povas komenci konstrui tian arbon? [Studenta] Iu de banging, klopodante eliri. [Bowden] Anyone komforta kun sia arbo konstruo? [Studenta] Certe. Tio ne faris. >> Estas fajna. Ni povas nur fini - ho, vi povas konservi ĝin? Hura. Do jen ni havas - ho, mi iomete ekstermigxos. Mi zoomed en? Zomi, rulumi eksteren. >> Mi havas demandon. >> Jes? [Studenta] Kiam vi difinas struct, estas aĵoj kiel inicializado al nenio? [Bowden] No >> Bone. Do vi devus pravalorizi - [Bowden] No Kiam vi difinas, aŭ kiam vi deklaras struct, ĝi ne inicializado defaŭlte; ĝi estas ĵus kiel se vi rakontos al int. Estas ĝuste la sama aĵo. Estas kiel ĉiu el ĝiaj individuaj kampoj povas havi rubo valoron en ĝi. >> Kaj ĉu eblas difini - aŭ por deklari struct en maniero, ke ĝi pravalorizi ilin? [Bowden] Jes. Do, ŝparvojo inicialización sintakso tuj aspekti - Ekzistas du manieroj povas fari ĉi tion. Mi kredas ke ni devus kompili ĝin certigi Clang ankaŭ faras tion. La ordo de argumentoj kiu venas en la struct, vi metis al la ordo de argumentoj ene de tiuj buklaj krampoj. Do se vi volas pravalorizi ĝin al 9 kaj lasis esti nulaj kaj tiam dekstre esti nula, estus 9, nula, nula. La alternativo estas, kaj la redaktoro ne ŝatas tiun sintakson, kaj ĝi kredas mi volas novan blokon, sed la alternativo estas io kiel - ĉi tie, mi metos ĝin sur nova linio. Vi povas eksplicite diras, mi forgesas la ĝusta sintakso. Do vi povas eksplicite trakti ilin laŭnome, kaj diru: . C, aux. Valoro = 9,. Maldekstra = NULL. Mi konjektas tiuj bezonon esti komoj. . Dekstra = NULL, do tiamaniere vi ne vere bezonas scii la ordon de la struct, kaj kiam vi legas ĉi tion, ĝi estas multe pli eksplicita pri kio la valoro de esti inicializado al. 

Ĉi tio okazas al esti unu el la aĵoj kiuj - tiel, plejparte, C + + estas superaro de C. Vi povas preni C-kodo, movi ĝin al C + +, kaj ĝi devus kompili. Tiu estas unu el la aĵoj kiuj C + + ne ebligas, do homoj emas ne fari ĝin. Mi ne scias se tio estas la sola kialo homoj inklinas ne fari ĝin, sed la kazo kie mi bezonis uzi ĝin bezonas por labori per C + + kaj do mi ne povis uzi tiun. Alia ekzemplo de iu kiu ne funkcias kun C + + estas kiom malloc redonas "void *," teknike, sed vi povus nur diri char * x = malloc ajn, kaj ĝi estos aŭtomate estos jxetitaj al char *. Ke aŭtomata cast ne okazas en C + +. Tio ne kompili, kaj vi eksplicite devas eldiri char *, malloc, kion ajn, por elpeli ĝin al char *. Ne estas multaj aĵoj kiuj C kaj C + + malakordo plu, sed tiuj estas du. Do ni iros kun multaj lingvoj. Sed eĉ se ni ne iros kun tiu sintakso, kio estas - eble malbona tio? [Studenta] Mi ne bezonas dereference ĝin? >> Jes. Memoru ke la sago havas implicitan dereference, kaj tiel, kiam ni simple temas pri struct, ni volas uzi. akiri en kampo ene de la struct. Kaj la sola tempo ni uzas sago estas kiam ni volas fari - bone, sago estas ekvivalento al - Tio estas kio ĝi estus signifinta se mi uzis sago. Ĉiuj sagoj duona, dereference ĉi, nun mi estas ĉe struct, kaj mi povas ricevi la kampo. Ĉu akiri la kampo rekte aŭ dereference kaj akiri la kampo - Mi supozas ĉi devus esti valoro. Sed ĉi tie mi pritraktas nur struct, ne puntero al struct, kaj tial mi ne povas uzi la sago. Sed ĉi tiaj aferoj ni povas fari por ĉiuj nodoj. Ho mia Dio. Tiu estas 6, 7, kaj 3. Tiam ni povas starigi la branĉoj en nia arbo, ni povas havi 7 - ni povas esti, ĝia maldekstra devus celi 3. Nu do kiel ni faros tion? [Studentoj, nekomprenebla] >> Jes. La adreso de node3, kaj se vi ne havas adreson, tiam simple ne kompili. Sed memoru, ke tiuj estas punteros al la sekvanta nodoj. La rajto devus celi 9, kaj 3 devus celi la rajton 6. Mi kredas ke tiu estas la tuta aro. Ajna komentoj aŭ demandoj? [Studento, nekomprenebla] La radiko tuj estos 7. Ni povas nur diri nodo * ptr = aŭ radiko, = & node7. 

Por nia celo, ni tuj estos pritraktas insert, do ni tuj volas skribi funkcion por enmeti en tiun duuma arbo kaj insert estas neeviteble tuj voki malloc krei novan nodon por ĉi arbo. Do tion tuj akiri senorda kun la fakto ke iuj nodoj estas nuntempe en la stako kaj aliaj nodoj tuj finos la amason kiam ni enmetas ilin. Ĉi tiu estas perfekte valida, sed la sola kialo ni povas fari tion en la stako estas ĉar ĝi estas tia elpensita ekzemplo kiu ni scias la arbo estas supozata esti konstruita kiel 7, 3, 6, 9. Se ni ne havas tiun, tiam ni ne devus malloc en la unua loko. Kiel ni vidos iom poste, ni devus esti malloc'ing. Ĝuste nun ĝi estas perfekte racia meti sur la pilo, sed ni ŝanĝos ĉi tion al malloc efektivigo. Do ĉiu el tiuj estas nun tuj estos iu kiel nodo * node9 = malloc (sizeof (nodo)). Kaj nun ni tuj devas fari nian ĉeko. if (node9 == NULL) - Mi ne volis ke - revenu 1, kaj tiam ni povos fari node9-> ĉar nun ĝi estas puntero, valoro = 6, node9-> lasis = NULL, node9-> dekstra = NULL, kaj ni tuj devas fari tion por ĉiu el tiuj nodoj. Do anstataŭe, ni metis ĝin interne de aparta funkcio. Ni nomas ĝin nodo * build_node, kaj ĉi tiu estas iom simila al la API ni ofertas por Huffman kodigo. Ni donas vin initializer funkcioj por arbo kaj deconstructor "funkcioj" por tiuj arboj kaj la sama por arbaroj. 

Do jen ni tuj havos initializer funkcio justaj konstrui nodo por ni. Kaj tuj vidu preskaux precize kiel ĉi tio. Kaj mi eĉ tuj estos pigra kaj ne ŝanĝas la nomon de la variablo, kvankam node9 ne havas senson plu. Ho, mi supozas node9 valoro ne devus esti 6. Nun ni povas reveni node9. Kaj ĉi tie ni devas reveni nula. Ĉiuj konsentas en tiu muntaĵo-a-nodo funkcio? Do nun ni povas simple nomas tion konstrui ajna nodo kun donita valoro kaj nula punteros. Nun ni povas nomi tion, ni povas fari nodon * node9 = build_node (9). Kaj ni faru. . . 6, 3, 7, 6, 3, 7. Kaj nun ni volas starigi la saman punteros, krom nun ĉiu estas jam en terminoj de punteros tial ne plu bezonas la adreson de. Okay. Do kio estas la lasta afero mi volas fari? Estas eraro-kontrolanta ke mi ne faras. Kion konstrui nodo reveno? [Studento, nekomprenebla] >> Jes. Se malloc malsukcesis, ĝi revenos nula. Do mi tuj pigre metis ĝin ĉi tie anstataŭ fari kondiĉo por ĉiu. If (node9 == NULL, aŭ - eĉ pli simpla, ĉi tiu estas ekvivalento al nur se ne node9. Do, se ne node9, aŭ ne node6, aŭ ne node3, aŭ ne node7, revenu 1. Eble ni devus presi malloc malsukcesis, aŭ io. [Studenta] Is falsa egala al nula tiel? [Bowden] Ajna nula valoro estas falsaj. Do nula estas nulo valoro. Nulo estas nulo valoro. Falsa estas nulo valoro. Ajna - preskaux la sola 2 nulo valoroj estas nulaj kaj nulo, falsa estas nur hash difinita kiel nulo. Tio ankaŭ validas se ni deklarus malloka variablo. Se ni faris havas nodo * radiko tien, tiam - la bela afero pri tutmonda variabloj estas, ke ili ĉiam havas komencan valoron. Tio ne validas por la funkcioj, kiel interne de ĉi tie, se ni havas, kiel, nodo * aŭ nodo x. Ni ne havas ideon kion x.value, x.whatever, aŭ ni povus presi ilin kaj ili povis esti arbitra. Tio ne validas por la tutmonda variabloj. Do nodo radiko aŭ nodo x. Implicite, ĉio tio estas tutmonda, se ne eksplicite inicializado al iu valoro, havas nula valoro kiel ĝia valoro. Do jen, nodo * radiko, ni ne eksplicite pravalorizi ĝin al nenion, do ĝia defaŭlta valoro estos nula, kiu estas la nula valoro de punteros. La defaŭlta valoro de x tuj signifas ke x.value estas nulo, x.left estas nula, kaj x.right estas nula. Do pro tio ke estas struct, ĉiuj el la kampoj de la struct estos nulo valoroj. Ni ne bezonas uzi tiun ĉi tie, tamen. [Studenta] La structs estas malsamaj ol aliaj variabloj, kaj la aliaj variabloj estas rubo valoroj; tiuj estas nuloj? [Bowden] Aliaj valoroj tro. Do en x, x estos nulo. Se estas al suma amplekso, ĝi havas komencan valoron. >> Bone. [Bowden] Aŭ la komenca valoro Vi donis ĝin aŭ nulo. Mi kredas ke ĝi atentas ĉiujn ĉi. 

Okay. Do la sekva parto de la demando petas, "Nun ni volas skribi funkcio nomita enhavas kun prototipo de bool enhavas int valoro. " Ni ne faros bool enhavas int valoro. Nia prototipo tuj aspekti bool enhavas (int valoro. Kaj tiam ni ankaŭ tuj pasi ĝin la arbo kiun ĝi devus esti kontrolanta por vidi se ĝi havas tiun valoron. Do nodo * arbo). Okay. Kaj tiam ni povas nomi ĝin per io kiel, eble ni volos printf aŭ iu. Enhavas 6, nia radiko. Tio devus reveni, aŭ vera, dum enhavas 5 radiko devus reveni falsaj. Do prenu la duan apliki ĉi. Vi povas fari tion aŭ ripete aŭ rekursie. La belan afero pri la maniero ni starigis aĵojn estas ke ĝi pruntas al nia rekursie solvo multe pli simpla ol la tutmonda-variablo maniero faris. Ĉar se ni nur devas enhavas int valoro, tiam ni ne havas manieron de recursing malsupren subárboles. Ni devus havi apartan helpanto funkcio kiu recurses malsupren la subárboles por ni. Sed ĉar ni ŝanĝis ĝin por porti la arbon kiel argumento, kiuj devus esti ĉiam en la unua loko, nun ni povas recurse pli facile. Do ripeta aŭ rekursie, ni transiru ambaŭ, sed ni vidos ke rekursie finas esti sufiĉe facila. Okay. Ĉu iu havas ion ni povas laboro kun? 

[Studenta] Mi havas ripeta solvo. >> Bone, ripeta. Konsentite, ĉi aspektas bona. Do, volas promeni ni per ĝi? [Studenta] Certe. Do mi metis temp variablo por akiri la unua nodo de la arbo. Kaj tiam mi nur looped tra dum temp ne egala nula, tiel dum estis ankoraŭ en la arbo, mi supozas. Kaj se la valoro egalas al la valoro kiu temp notas al, tiam ĝi redonas tiun valoron. Alie, ĝi kontrolas se estas cxe la dekstra flanko aŭ la maldekstra flanko. Se vi iam ricevi situacio kie mankas pli arbo, tiam li revenas - ĝi eliroj la ciklo kaj revenas falsaj. [Bowden] Okay. Do kiu ŝajnas bona. Iu havas komentoj pri io? Mi havas neniun praveco komentojn ĉe ĉiuj. La unu afero ni povas fari estas ĉi ulo. Ho, ĝi estas tuj iros iom longish. Mi havigos ke ĝis. Okay. 

Ĉiuj devus memori kiom triargumenta funkcias. Tie ili definitive estis kvizojn en la estinteco ke al vi funkcio kun triargumenta operatoro, kaj diru traduki ĉi tion, faru ion, kiu ne uzas triargumenta. Do ĉi tiu estas tre komuna kazo de kiam mi pensus uzi triargumenta, kie se iu kondiĉo establis variablo al iu, alie agordi tiu sama variablo por io alia. Tio estas iu kiu tre ofte povas esti konvertita enen ĉi tiaj aferoj kie establis ke variablo al tio - aŭ, bone, tio validas? Tiam ĉi, alie tion ĉi. [Studenta] La unua estas, se vera, ĉu ne? [Bowden] Yeah. La maniero Mi ĉiam legas estas, temp egalas valoron pli granda ol temp valoro, tiam ĉi, alie tion ĉi. Oni demandas demandon. Ĉu granda? Poste faru la unuan aferon. Else do la dua afero. Mi preskaŭ ĉiam - la dupunkto, mi nur - en mia kapo, mi legis kiel alia. 

Ĉu iu havas rekursia solvo? Okay. Ĉi tiu nin tuj - ĝi povus jam esti granda, sed ni tuj faros eĉ pli bona. Ĉi tiu estas preskaux la samo ĝustan ideon. Estas nur, nu, ĉu vi volas klarigi? [Studenta] Certe. Do ni certigante ke la arbo estas ne nula unua, ĉar se la arbo estas nula tiam tuj revenos malvera ĉar ni ne trovis ĝin. Kaj se estas ankoraŭ arbo, ni iru en - ni unue kontroli, ĉu la valoro estas la nuna nodo. Reveno vera se ĝi estas, kaj se ni ne recurse sur la maldekstra aŭ dekstra. Ĉu tio sonas taŭga? >> MM-hmm. (Akordo) Do rimarki ke ĉi tio estas preskaŭ - strukture tre simila al la ripeta solvo. Estas nur ke anstataŭ recursing, ni havis dum ciklo. Kaj la bazo ĉi tie kie arbo ne egala nula estis la kondiĉo sub kiu ni rompis el la dum ciklo. Ili estas tre similaj. Sed ni tuj por preni tiun unu paŝon. Nun, ni faros la samon ĉi tie. Rimarku ni reveni al la sama afero en ambaŭ el ĉi tiuj linioj, krom unu argumento estas malsama. Do ni tuj faros ke en triargumenta. Mi batis eblo ion, kaj tio faris simbolo. Okay. Do ni tuj revenos enhavas tion. Ĉi farigxas multnombraj linioj, nu, zoomed en ĝi estas. Kutime, kiel stila afero, mi ne pensas multaj homoj metu spacon post la sago, sed mi supozas, se vi estas kohera, estas fajna. Se valoro estas malpli ol arbo valoro, ni volas recurse sur arbo maldekstren, alie ni volas recurse sur arbo dekstre. Por ke estis paŝo unu el farante ĉi rigardo pli malgranda. Paŝo du de fari ĉi rigardo pli malgranda - ni povas apartigi tion al multnombraj linioj. Okay. Paŝo du de farante ĝi aspektos pli malgranda estas ĉi tie, tial reveno valoro egalas arbo valoron, nek enhavas ajn. 

Tio estas grava afero. Mi ne certas, ĉu li diris eksplicite en klaso, sed ĝi estas nomata mallonga cirkvito pritakso. La ideo cxi tie estas valoro == arbo valoron. Se tio estas vera, tiam ĉi tiu estas vera, kaj ni volas 'aŭ' kiu kun kio ajn super tie. Do eĉ sen pensi kio ajn ĉi tie, kio estas la tuta esprimo tuj revenos? [Studenta] Vera? >> Jes, ĉar veran de io, or'd - aŭ vera or'd kun nenio estas bezone vera. Tuj, kiam ni vidas reveno valoro = arbo valoron, ni ĵus tuj revenos vera. Eĉ tuj recurse plu enhavas laŭ la linio. Ni povas preni ĉi unu paŝon. Reiri arbo ne egala nula kaj ĉiuj tion ĉi. Ĝi faris ĝin unu-linia funkcio. Tiu estas ankaŭ ekzemplo de mallonga cirkvito pritakso. Sed nun ĝi estas la sama ideo - anstataŭ - do se arbo ne egala nula - aŭ, bone, se arbo faras egalaj nula, kiu estas la malbona kazo, se arbo egalas nula, tiam la unua kondiĉo tuj estos falsaj. Do falsa anded kun nenio tuj estos kio? [Studenta] Falsa. >> Jes. Tio estas la alia duono de mallonga cirkvito pritakso, kie se arbo ne egala nula, tiam ni ne tuj eĉ iri - aŭ se arbo faras egalaj nula, tiam ni ne faros valoro == arbo valoron. Ni nur tuj tuj revenos falsaj. Kio estas grava, ĉar se tio ne mallonga cirkvito taksi, tiam se arbo faras egalaj nula, tiu dua kondiĉo tuj seg kulpo, ĉar arbo-> valoro estas dereferencing nula. Do jen tiel. Povas fari ĉi - ŝanĝi iam finita. Ĉi tiu estas tre komuna afero, ne farante ĉi tiu linio kun tio, sed estas komuna aĵo en kondiĉoj, eble ne rajtas ĉi tie, sed se (arbo! = NULL, kaj arbo-> valoro == valoro), faru kion ajn. Ĉi tiu estas tre komuna kondiĉo, kie anstataŭ havi rompi tiun en du IFS, kie kiel, estas la arbo nula? Okay, ne nula, tial nun estas la arbo valoro egalas al valoro? Fari ĉi tion. Anstataŭe, ĉi tiu kondiĉo, ĉi tio neniam seg kulpo ĉar rompos, ĉu ĉi tio okazas al esti nula. Nu, mi supozas se via arbo estas tute nevalida pointer, ĝi povas ankoraŭ seg kulpo, sed ĝi ne povas seg kulpo se arbo estas nula. Se estis nula, tio rompus antaux vi iam dereferenced la puntero en la unua loko. [Studenta] Is this nomita pigra pritakso? 

[Bowden] Lazy pritakso estas aparta afero. Pigra pritakso estas pli kiel vi peti valoron, vi demandos al kalkuli valoron, speco de, sed vi ne bezonas ĝin tuj. Do ĝis vi vere bezonas ĝin, tio ne estas taksita. Tio ne estas ekzakte la sama afero, sed en la kodigo pset, diras, ke ni "pigre" skribi. La kialo ni faru tion estas ĉar ni vere buffering la skribo - ni ne volas skribi individuajn bitojn samtempe, aŭ individuaj bitokoj samtempe, ni anstataŭ volas eron de bajtoj. Tiam fojon ni havas eron de bajtoj, tiam ni skribi ĝin. Kvankam vi demandas ĝin por skribi - kaj fwrite kaj fread fari same tiaj aferoj. Ili buffer vian legas kaj skribas. Kvankam vi demandas ĝin skribi tuj, ĝi probable ne estos. Kaj vi ne povas esti certa, ke la vojo por esti skribita ĝis vi nomas hfclose aŭ kio ajn ĝi estas, kiuj tiam diras, bone, mi fermas mian dosieron, kiu signifu mi prefere skribu ĉion, kion mi ne skribis ankoraŭ. Ĝi ne bezonas skribi cxion ekster ĝis vi fermas la dosiero, kaj poste ĝi bezonas. Do tio estas nur kion pigra - ĝi atendas ĝis ĝi devas okazi. Ĉi - prenu 51 kaj vi iros en ĝin pli detale, ĉar Ocaml kaj ĉiu en 51, ĉiu estas rekursio. Ne estas ripeta solvojn, esence. Ĉiu estas rekursio kaj pigra pritakso tuj estos gravaj por multaj cirkonstancoj kie, se vi ne pigre taksi, kiu signifus - La ekzemplo estas riveretoj, kiuj estas malfinie longa. En teorio, vi povas pensi pri la naturaj nombroj kiel la kurento de 1-2-3-4-5-6-7, Do pigre taksita aĵoj estas fajna. Se mi diras Mi volas la deka numero, tiam mi povas taksi ĝis la deka cifero. Se mi volas la centa numero, tiam mi povas taksi ĝis la centa numero. Sen pigra pritakso, tiam tuj provas taksi ĉiuj nombroj tuj. Vi taksi malfinie multaj nombroj, kaj tio estas ĝuste ne eblas. Estas do multaj cirkonstancoj kie pigra pritakso estas nur esenca por atingi tion por labori. 

Ni nun volas skribi insert kie insert tuj estos simile ŝanĝanta en lia difino. Do nun estas bool insert (int valoro). Ni tuj ŝanĝu tion al bool insert (int valoro, nodo * arbo). Ni efektive tuj ŝanĝi tion denove en iom, ni vidos kial. Kaj estu la movi build_node, nur por la heck pri tio, supre enmeti do ni ne devas skribi funkcion prototipo. Kiu estas aludo, ke vi tuj estos uzante build_node en insert. Okay. Prenu unu minuto por tio. Mi kredas ke mi savis la revizio se vi volas tiri el tio, aŭ, almenaŭ, mi faris nun. Mi volis iomete ripozon por pensi pri la logiko de insert, se vi ne povas pensi pri ĝi. Esence, vi nur iam esti enmeto en folioj. Kiel, se mi enmetas 1, tiam mi nepre tuj estos enmeto 1 - Mi ŝanĝos al nigra - I'll esti enmeto 1 pli tie. Aŭ se mi enmetas 4, mi volas esti enmeto 4 pli tie. Do ne gravas kion vi faras, vi tuj estos enmeto en folio. Vi nur devas fari estas persisti malsupren de la arbo ĝis vi atingos la nodo kiuj devus esti la nodo patro, la nova nodo patro, kaj poste ŝanĝi lian maldekstran aŭ dekstren pointer, depende de ĉu ĝi estas pli granda ol aŭ malpli ol la aktuala nodo. Ŝanĝi tion puntero atentigi al via nova nodo. Do persisti malsupren de la arbo, fari la folio punkto al la nova nodo. Ankaŭ pensas ke kial malpermesas la tipo de situacio antaŭ, kie mi konstruis la duuma arbo kie estis ĝentila se vi nur rigardis unu nodo, sed 9 estis ĉe la maldekstra de 7 se vi ripetis cxiujn vojo. Por ke estas neebla en ĉi tiu scenejo, ĉar - kredas pri enmeto 9 aŭ io; ke je la unua nodo, Mi iros vidi 7 kaj mi simple tuj iros al dekstre. Do ne gravas, kion mi faru, se mi enmeto irante al folio, kaj folion per la taŭga algoritmo, ĝi tuj estos neebla por mi enŝovu 9 al la maldekstra el 7 ĉar kiam mi batis 7 Mi tuj iros dekstren. Ĉu iu havas ion por starti kun? [Studenta] I do. >> Certe. [Studento, nekomprenebla] [Aliaj studento, nekomprenebla] [Bowden] Oni estimis. Okay. Volas klarigi? 

[Studenta] Ĉar ni scias, ke ni estis la enmeto novaj nodoj je la fino de la arbo, Mi looped tra la arbo iterativamente ĝis mi alvenis al nodo kiu notis al nula. Kaj poste mi decidis meti ĝin ĉu sur la dekstra flanko aŭ la maldekstra flanko uzante tiun rajton variablo; rakontis al mi kie meti ĝin. Kaj poste, esence, mi nur faris tiun lastan - ke temp nodo punkto al la nova vertico ke ĝi kreas, ĉu sur la maldekstra flanko aŭ ĉe la dekstra flanko, depende de tio, kion la valoro dekstra estis. Fine, mi starigis la novan nodon valoro al la valoro de lia provoj. [Bowden] Konsentite, tiel mi vidas unu afero ĉi tie. Ĉi tio estas kiel 95% de la vojo. La demando kiun mi vidas, nu, ne iu alia vidis afero? Kio estas la cirkonstanco sub kiuj ili rompas el la ciklo? [Studenta] Se temp estas nula? >> Jes. Do kiel vi rompi la buklo estas se temp estas nula. Sed kion mi faru ĉi tie? Mi dereference temp, kiu estas neeviteble nula. Do la alia afero vi bezonas fari, estas ne nur konservi trako ĝis temp estas nula, vi volas konservi trako de la patro en ĉiu momento. Ni ankaŭ volas nodo * patro, mi supozas ke ni povas subteni ke en nula en komenco. Tiu tuj havos stranga konduto por la radiko de la arbo, sed ni ricevos por tio. Se valoro estas pli granda ol kion ajn, tiam temp = temp pravas. Sed antaŭ ol ni faras tion, patro = temp. Aŭ gepatrojn ĉiam tuj egala temp? Ĉu tio estas la kazo? Se temp ne nula, tiam mi iros por movi malsupren, negrave kio, al nodo por kiu temp estas la patro. Do patro tuj estos temp, kaj tiam mi movi temp sube. Nun temp estas nula, sed patro poentojn al la patro de la aĵo kiu estas nula. Do ĉi tie, mi ne volas meti dekstra egalas 1. Do mi kopiis al la dekstra, do se dekstra = 1, kaj mi supozas ke vi ankaŭ volas fari - se vi movas al la maldekstra, vi volas agordi dekstra egala al 0. Alie se vi iam kopii al dekstre. So right = 0. Se dekstra = 1, nun ni deziras fari la patro dekstra puntero newnode, alie ni volas fari la patro maldekstra puntero newnode. Demandojn sur tio? Okay. Do ĉi tiu estas la vojo ni - nu, efektive, anstataŭ fari tion, ni duono atendis vin uzi build_node. Kaj tiam se newnode egalas nula, revenu falsaj. Tio estas tio. Nun, ĉi tiu estas kion ni atendas vin por fari. 

Ĉi tio estas kion la bastonon solvoj fari. Mi malkonsentas kun tiu, la "rajto" vojo de tuj pri tio sed ĉi tiu estas perfekte fajna kaj ĝi funkcios. Unu afero, ke estas iom stranga nun estas se la arbo dividu kiel nula, oni pasas en nula arbo. Mi supozas ke dependas de kiel vi difinas la konduton de pasi en nula arbo. Mi pensus ke se vi pasas en nula arbo, tiam la enmeto de la valoro en nula arbo devus simple resendas arbo kie la sola valoro estas, ke simpla nodo. Ĉu homoj konsentas kun tiu? Vi povus, se vi volas, se vi pasas en nula arbo kaj vi volas enmeti valoron en ĝin, revenu falsaj. Ĝi dependas de vi por difini tion. Por fari la unuan aferon mi diris kaj tiam - bone, vi havos problemojn fari tion, ĉar estus pli facile se ni havis suman sagon al la afero, sed ni ne, do se arbo estas nula, tie estas nenio ni povas fari pri tio. Ni povas nur redoni malvera. Do mi tuj ŝanĝos insert. Ni teknike povus simple ŝanĝi ĉi tie ĉi, kiel ĝi estas ripetanta super aĵoj, sed mi tuj ŝanĝos insert preni nodo ** arbo. Duobla punteros. Kion tio signifas? Anstataŭ trakti punteros al nodoj, la afero mi tuj iros manipulanta estas ĉi puntero. Mi tuj iros manipulanta ĉi puntero. Mi tuj iros manipulanta punteros rekte. Tiu makes sense ekde, pensi malsupren - nu, nun ĉi punktoj al nula. Kion mi volas fari estas manipuli ĉi puntero atentigi ke ne nula. Mi volas atentigi al mia nova nodo. Se mi ĝuste konservi trako de punteros al mia punteros, tiam mi ne bezonas konservi trako de patro puntero. Mi povas nur kontroli kiu faras por vidi se la puntero notas al nula, kaj se la puntero notas al nula, ŝanĝi ĝin al punkto al la nodo mi volas. Kaj mi povas ŝanĝi ĝin ĉar mi havas sagon al la puntero. Ni vidas ĉi nun. Vi povas vere fari ĝin rekursie bela facile. Ĉu ni volas fari tion? Jes, ni faros. 

Ni vidas rekursie. Unue, kio nia bazo kazo tuj estos? Preskaŭ ĉiam nia bazo kazo, sed efektive, tiu estas speco de malfacila. Unuaj aferoj unue, se (arbo == NULL) Mi supozas ni ĵus tuj revenos falsaj. Tiu estas malsama de via arbo esti nula. Ĉi tiu estas la puntero al via radika puntero esti nula kio signifas, ke via radika puntero ne ekzistas. Do ĉi tie, se mi faras nodo * - ni simple reuzas tion. Nodo * radiko = NULL, kaj tiam mi iros nomi insert farante ion kiel, enŝovu 4 en & radiko. Do & radiko, se radiko estas nodo * tiam & radiko tuj estos nodo **. Ĉi tio estas valida. En ĉi tiu kazo, arbo, tien, arbo estas ne nulaj - aŭ insert. Jen. Arbo estas ne nulaj; * arbo estas nula, kiu estas fajna ĉar se * arbo estas nula, tiam mi povas manipuli ĝin nun notas, kion mi volas atentigi al. Sed se arbo estas nula, kiu signifu mi nur venis ĉi tien kaj diris nula. Tio ne havas sencon. Mi ne povas fari ion kun tiu. Se arbo estas nula, revenu falsaj. Do mi esence jam diris kion niaj reala bazo kazo estas. Kaj kio estas tiu tuj estos? [Studento, nekomprenebla] [Bowden] Jes. Do, se (* arbo == NULL). Tiu rilatas al la kazo ĉi tien kie se mia ruĝa puntero estas la puntero Mi centris en, tiel kiel mi centris en ĉi pointer, nun mi centris en ĉi puntero. Nun mi centris en ĉi puntero. Do, se miaj ruĝaj pointer, kiu estas mia nodo **, estas iam - se *, mia ruĝa pointer, estas iam nula, tio signifas, ke mi estas la kazo kie mi enfokusigante puntero ke punktoj - ĉi tiu estas puntero kiu apartenas al folio. Mi volas ŝanĝi ĉi puntero atentigi al mia nova nodo. Revenu ĉi tien. Mia newnode estos nur esti nodo * n = build_node (valoro) tiam n, se n = NULL, revenu falsaj. Alie ni volas ŝanĝi kion la puntero nuntempe montrante nun notas al nia nove konstruita nodo. Ni povas vere fari tion tie ĉi. Anstataŭ diri n, ni diru * arbo = se * arbo. Cxiu komprenas tion? Ke per kontraktanta kun indikoj al punteros, ni povas ŝanĝi nula punteros atentigi al tio ni volas ilin atentigi al. Tio estas nia bazo kazo. 

Nun nia rekursieca, aŭ nia rekursio, tuj estos tre simila al ĉiuj aliaj recursions ni estis farante. Ni tuj volas enmeti valoron, kaj nun mi tuj uzos triargumenta denove, sed kio estas nia kondiĉo tuj estos? Kio estas tio ni serĉas por decidi ĉu ni volas iri maldekstra aŭ dekstra? Ni faru tion en apartaj paŝoj. If (valoro <) kio? [Studenta] La arbo valoron? [Bowden] Do memoru, ke mi estas aktuale - [Studentoj, nekomprenebla] [Bowden] Yeah, do ĉi tie, diru ke tiu verda sago estas ekzemplo de tio, kion arbo aktuale estas, estas puntero al ĉi puntero. Do tio signifas Mi estas puntero al puntero al 3. La dereference dufoje sonis bona. Kion mi - kiel mi faru tion? [Studenta] Dereference fojon, kaj tiam fari sago kiun vojon? [Bowden] So (* arbo) estas la dereference fojon, -> valoro tuj donu al mi la valoron de la nodo ke mi nerekte montrante. Do mi povas ankaŭ skribi ĝin ** tree.value se vi preferas tion. Ĉu funkcias. Se tio estas la kazo, tiam mi volas nomi enmeti per valoro. Kaj kio estas mia ĝisdatigita nodo ** tuj estos? Mi volas iri al la maldekstra, do ** tree.left tuj estos mia maldekstra. Kaj mi volas ke la referenco al tiu afero tiel ke se la maldekstra finas esti la nula pointer, Mi povas modifi ĝin rekte al mia nova nodo. 

Kaj la alia kazo povas esti tre similaj. Ni efektive faras ke mia triargumenta nun. Enmetu valoron se valoro <(** arbo). Valoro. Tiam ni volas ĝisdatigi nian ** al la maldekstra, alie ni volas ĝisdatigi nian ** dekstre. [Studenta] Ĉu tio akiri la sagon al la puntero? [Bowden] Memoru ke - ** tree.right estas nodo stelo. [Studento, nekomprenebla] >> Jes. ** Tree.right estas kiel ĉi tiu puntero aŭ iu. Do per prenante puntero al tiu, kiu donas al mi kion mi volas de la puntero al tiu ulo. [Studenta] Could ni transiru denove kial oni uzas la du punteros? [Bowden] Yeah. Do - ne, vi povas, kaj ke solvo antaux Estis maniero fari ĝin sen fari du punteros. Vi bezonas por povi kompreni uzante du punteros, kaj ĉi tiu estas pli pura solvo. Ankaŭ, rimarki ke, kio okazas se mia arbo - kio okazas se mia radikon estis nula? Kio okazas se mi faras ĉi kazo ĉi tie? Do nodo * radiko = NULL, enŝovu 4 en & radiko. Kio estas radiko tuj estos post tio? [Studento, nekomprenebla] >> Jes. Radiko valoro tuj estos 4. Radiko maldekstra tuj estos nula, radiko dekstra tuj estos nula. En la kazo kie ni ne pasis radiko de adreson, ni ne povis modifi radikon. En la kazo kie la arbo - kie radiko estis nula, ni simple devis reveni falsaj. Nenio ni povus fari. Ni ne povas insertar nodo en malplenan arbo. Sed nun ni povas; ni simple malplena arbo en unu-nodo arbo. Kiu estas kutime la atendita formo kiu ĝi estas supozeble funkcias. 

Plue, tiu estas signife pli mallonga ol Ankaŭ konservanta trako de la patro, kaj tiel vi persisti malsupren la tuta vojo. Nun mi havas mian patro, kaj mi simple havas mian patro dekstra puntero al la kiom. Anstataŭe, se ni tion faris ripete, ĝi estus la sama ideo kun dum ciklo. Sed anstataŭ devi trakti kun mia patro pointer, anstataŭ mia nuna puntero estus la afero ke mi rekte modifi atentigi al mia nova nodo. Mi ne devas trakti ĉu ĝi estas montrante al la maldekstra. Mi ne devas trakti ĉu ĝi estas montranta dekstren. Estas nur ajn ĉi puntero estas, mi iros, por restarigi gxin rekte al mia nova nodo. Cxiu komprenas kiel ĝi funkcias? Se ne kial ni volas fari ĝin tiel, sed almenaŭ tiu ĉi verkoj kiel solvo? [Studenta] Kie ni revenos vera? [Bowden] Tio probable ĉi tie. Se ni ĝuste enmeti ĝin, revenas vera. Else, suben jen ni tuj volas reveni ajn insert revenas. 

Kaj kio estas speciala pri tiu rekursia funkcio? Estas vosto rekursie, do tiel longe kiel ni kompilos kun iuj optimumigo, ĝin rekonos, ke kaj vi neniam ricevas pilo superflui de ĉi tio, eĉ se nia arbo havas altecon de 10.000 aŭ 10 milionoj. [Studento, nekomprenebla] [Bowden] Mi opinias, ke ghi en Dash - aŭ kio optimumigo nivelo estas necesa por voston rekursio esti rekonita. Mi kredas ke rekonas - GCC kaj Clang ankaŭ havas malsamajn signifojn por ilia optimumigo niveloj. Mi volas diri ke estas DashO 2, por certigi ke ĝi rekonos vosto rekursio. Sed ni - vi povus konstrui kiel Fibonocci ekzemplo aŭ iu. Ne facile testi kun ĉi tio, ĉar ĝi estas malfacile konstrui duuma arbo kiu tiom granda. Sed jes, mi kredas ke estas DashO 2, kiu se vi kompili kun DashO 2, ĝi serĉos vosto rekursio kaj optimizar ke eksteren. Ni reiru al - enigi estas laŭvorte la lasta afero kiun ĝi bezonas. Ni reiru al la insert tien kie ni tuj faros la saman ideon. Ĝi devos ankoraŭ havas la difekton de ne povi tute manipuli kiam la radiko mem estas nula, aŭ la pasinteco eniro estas nula, sed anstataŭ kontraktanta kun patro pointer, ni apliku la saman logikon de gardi punteros al punteros. Se tie ni plenumas nian nodo ** nuna, kaj ni ne bezonas konservi trako de rajto plu, sed nodo ** nuna = & arbo. Kaj nun nia dum buklo tuj estos dum * nuna ne egala nula. Ne necesas konservi trako de gepatroj plu. Ne necesas konservi trako de maldekstra kaj dekstra. Kaj mi nomas ĝin temp, ĉar ni jam uzas temp. Okay. Do, se (valoro> * temp), tiam & (* temp) -> dekstre alie temp = & (* temp) -> maldekstra. Kaj nun, je ĉi tiu punkto, post ĉi tiu dum ciklo, Mi nur faras ĉi tion ĉar eble pli facilas pensi iterativamente ol rekursie, sed post ĉi dum ciklo, * Temp estas la puntero ni volas ŝanĝi. 

Antaŭ ol ni havis patro, kaj ni volis ŝanĝi ĉu patro maldekstra aŭ dekstra patro, sed se ni volas ŝanĝi patro pravas, tiam * temp estas patro estas prava, kaj ni povas ŝanĝi ĝin rekte. Do cxi tie, ni povas fari * temp = newnode, kaj tio estas ĝi. Do rimarki, ĉiuj ni faris en ĉi estis forprenu linioj de kodo. Por konservi trako de la patro en cxio, kio estas plia peno. Jen, se ni nur konservi trako de la sagon al la puntero, kaj eĉ se ni volis forigi ĉiujn ĉi tiujn frizita krampoj nun, fari ĝin rigardi pli mallonga. Tiu nun estas la ĝusta sama solvo, sed malpli linioj de kodo. Kiam vi komencos rekonante tion kiel validan solvo, ĝi estas ankaŭ pli facile rezoni pri pli ol kiel, bone, kial mi havas tiun flagon ĉe int dekstra? Kion tio signifas? Ho, ĝi estas kia ĉiufoje mi iros dekstren, mi bezonas por meti ĝin, alie, se mi iros lasis Mi bezonas meti ĝin al nulo. Ĉi tie, mi ne havas rezoni pri tio, temas nur pli facile pripensi. Demandoj? [Studento, nekomprenebla] >> Jes. Konsentite, tial en la lasta iom - Mi supozas oni rapida kaj facila funkcio ni povas fari estas, let's - kune, mi supozas, provu kaj skribu enhavas funkcio kiu ne zorgas ĉu ĝi estas duargumenta serĉo arbo. Tiu enhavas funkcion devus reveni vera se ie ajn en ĉi tiu ĝenerala duuma arbo estas la valoro, ni serĉas. Do ni unue faru ĝin rekursie kaj poste ni faros ĝin ripete. Ni povas vere nur tion kune, ĉar ĉi tiu tuj estos vere mallonga. 

Kio estas mia bazo kazo tuj estos? [Studento, nekomprenebla] [Bowden] Do, se (arbo == NULL), tiam kio? [Studenta] Reveno falsaj. [Bowden] Else, nu, mi ne bezonas la alian. Se estis mia alia bazo kazo. [Studenta] Tree valoro? >> Jes. Do, se (arbo-> valoro == valoro. Rimarku ni reen al nodo *, ne nodo ** j? Enhavas neniam devas uzi nodo **, ĉar ni ne modifas punteros. Ni nur trairante ilin. Se tio okazas, tiam ni volas reveni vera. Alie ni volas trairi la infanoj. Do ni ne povas rezoni pri tio, ĉu ĉio al la maldekstra estas malpli kaj ĉiu al dekstre estas granda. Do kio estas nia kondiĉo tuj estos tie - aŭ, kion ni tuj fari? [Studento, nekomprenebla] >> Jes. Reiri enhavas (valoro, arbo-> maldekstre) aŭ enhavas (valoro, arbo-> dekstre). Kaj tio estas ĝi. Kaj rimarki ekzistas iu mallonga cirkvito pritakso, kie se ni hazarde trovis la valoron en la maldekstra arbo, ni neniam devas rigardi la dekstra arbo. Tio estas la tuta funkcio. Nun ni faru ĝin ripete, kiu iras al esti malpli agrabla. Ni prenos la kutima komenco de nodo * nuna = arbo. Dum (nuna! = NULL). Rapide tuj vidas problemon. Se nuna - ĉi tie, se ni iam rompos el tio ĉi tiam ni ne plu havas aferojn por rigardi, do reveni falsaj. If (nuna-> valoro == valoro), revenu vera. Do nun ni estas en loko - ni ne scias, ĉu ni volas iri maldekstren aŭ dekstren. Do arbitre, ni nur iri lasis. Mi evidente kolizios afero kie mi tute forlasis cxion - Mi nur iam kontroli la maldekstra flanko de arbo. Mi neniam kontroli ion kiu estas dekstra filo de io. Kiel mi ripari tion? [Studenta] Oni devas konservi trako de la maldekstra kaj dekstra en pilo. [Bowden] Yeah. Do ni faru ĝin struct listo, nodo * n, kaj tiam nodo ** poste? Mi kredas, ke funkcias bone. Ni volas iri super la maldekstra, aŭ let's - ĝis ĉi tie. Struct listo listo =, ĝi devos komenci tra ĉi struct listo. * Listo = NULL. Por ke tuj estos nia ligillisto de subárboles ke ni saltis super. Ni iras al Traverse forlasis nun, sed ĉar ni neeviteble bezonas reveni al la dekstra, Ni tuj observas la dekstra flanko interne de nia struct listo. Tiam ni devos new_list aŭ struct, struct listo *, new_list = malloc (sizeof (listo)). Mi tuj ignori eraro-kontroladon tion, sed vi devus kontroli por vidi se la nula. New_list la nodo ĝi tuj indikas - ho, jen kial mi volis ĝin ĉi tie. Ĝi okazas al punkto al dua struct listo. Tio estas, kiom ligitaj lertaj laboro. Ĉi tiu estas la sama kiel int ligitaj listo krom ni nur anstataŭante int kun nodo *. Estas precize la sama. Do new_list, la valoro de nia new_list nodo, tuj estos nuna-> dekstren. La valoro de nia new_list-> sekva tuj estos nia originala listo, kaj poste ni iras al ĝisdatigi nian liston al punkto al new_list. 

Nun ni bezonas ian vojon de tirante aferojn, kiel ni trairis la tutan maldekstran subárbol. Nun ni bezonas tiri stuff el ĝi, kiel nuna estas nula; ni ne volas ĝuste redoni malvera. Ni volas nun tiri ekstere ĉe nia nova listo. Al oportuna maniero por tion fari - nu, efektive, ekzistas plurajn manierojn por fari tion. Ĉiu havas sugeston? Kie mi faru tiun aŭ kiel mi faru tion? Ni havas nur post kelkaj minutoj, sed neniu sugestojn? Anstataŭ - unu formo, anstataŭ nia kondiĉo esti dum, kion ni nuntempe rigardas ne nula, anstataŭ ni tuj daŭre iras ĝis nia listo mem estas nula. Do, se nia listo finas esti nula, tiam ni elĉerpas de aĵoj por serĉi, serĉo finiĝis. Sed tio signifas, ke la unua afero en nia listo estas nur tuj estos la unua nodo. La unua afero estos - ni ne plu bezonas vidi tion. Do listo-> n estos nia arbo. Listo-> sekva tuj estos nula. Kaj nun dum listo ne egala nula. Nuna tuj tiri ion de nia listo. Do nuna tuj egala listo-> n. Kaj poste listo tuj egala listo-> n, aŭ listo-> proksima. Do se nuna valoro egalas valoron. Nun ni povas aldoni ambaŭ niaj dekstra puntero kaj nia maldekstra puntero tiel longe kiel ili ne estas nula. Cxi tie, mi supozas ke ni devus fari ke en la unua loko. If (nuna-> dekstren! = NULL) tiam tuj enigi ke nodo en nian liston. If (nuna-> maldekstra), ĉi tiu estas iom da ekstra laboro, sed ĝi estas fajna. If (nuna-> maldekstra! = NULL), kaj ni tuj enigi la maldekstra en niajn ligitaj listo, kaj tio estu ĝi. Ni persisti - kondiĉe ke ni havas ion en nia listo, ni havos alian nodon por rigardi. Do ni rigardas ke nodo, ni antaŭi nia listo por la proksima. Se tio nodo estas la valoro, ni serĉas, ni povas reveni vera. Else enmeti ambaŭ nia maldekstra kaj dekstra subárboles, tiel longe kiel ili ne estas nulaj, en nian liston por ke ni neeviteble transiros ilin. Do, se ili ne estis nula, se niaj radiko puntero indikis du aferojn, tiam unue ni tiris ion tiel nia listo finas esti nula. Kaj tiam ni metas du aferoj denove en, do nun nia listo estas de amplekso 2. Tiam ni iras por buklo back up kaj ni nur povos tion, diru, la maldekstra puntero de nia radiko nodo. Kaj tio estos ĝuste teni okazas; ni finos looping super ĉio. 

Rimarku, ke tio signife pli komplika en la rekursia solvo. Kaj mi diris plurajn fojojn ke la rekursia solvo kutime havas multon komunan kun la ripeta solvo. Jen ĉi tiu estas ekzakte kion la rekursia solvo faras. La sola ŝanĝo estas ke anstataŭ implice uzante la pilo, la programo pilo, kiel via vojo de konservanta trako de kio nodoj vi ankoraŭ bezonas por viziti, nun vi devas eksplicite uzas ligillisto. En ambaŭ kazoj vi konservanta trako de kio nodo ankoraŭ bezonas esti vizitis. En la rekursiaj kazo estas nur pli facile ĉar pilo estas implementado por vi kiel la programo pilo. Rimarku ke ĉi ligitaj listo, ĝi estas pilo. Kion ajn ni nur metis en la stako Estas tuj kion ni tuj detiri la pilo viziti proksima. Ni estas el tempo, sed demandojn? [Studento, nekomprenebla] [Bowden] Yeah. Do, se ni havas niajn ligillisto, nuna tuj atentigi al ĉi ulo, kaj nun ni nur antaŭis nian ligillisto centri en ĉi tiu viro. Ni lauxiris tra la ligitaj listo en tiu linio. Kaj tiam mi supozas ke ni devus liberigi nian ligillisto kaj stuff fojon antaŭ reveni vera aŭ malvera, ni bezonas persisti super niaj ligitaj listo kaj ĉiam cxi tie, mi supozas, se ni nuna rajto estas ne egala al, aldoni, do nun ni volas liberigi nuna ĉar, nu, ni ne tute forgesi pri la listo? Yeah. Do jen kion ni volas fari ĉi tie. Kie estas la puntero? Nuna estis tiam - ni volas al struct listo * 10 egalas listo proksima. Libera listo, listo = temp. Kaj en la kazo kie ni revenos vera, ni bezonas ankaŭ persisti super la resto de nia ligillisto liberigante aĵoj. La belan afero pri la rekursiaj solvo estas liberigi aĵoj nur signifas krevi factorings ekstere la stako kiu okazos por vi. Do ni iris de iu kiu estas kiel 3 linioj de malmola-al-pensas-pri kodo al iu kiu estas signife multaj pli malmola-al-pensas-sur linioj de kodo. Plu demandoj? Bone. Ni estas bona. Ĝis! [CS50.TV]