[Powered by Google Translate] [Sekcio 7] [Less Komfortaj] [Nate Hardison] [Universitato Harvard] [Jen CS50.] [CS50.TV] 

Bonvenon Sekcio 7. Danke al uragano Sandy, anstataŭ havi normalan sekcio ĉi semajno, ni faras ĉi promeno-tra, tra la sekcio de demandoj. Mi tuj iros post kune kun la problemo Ŝanĝu 6 Specification, kaj irante tra ĉiuj el la demandoj en la Al Sekcio de Demandoj sekcio. Se vi renkontas demandoj, bonvolu afiŝi tiuj sur CS50 diskuti. 

Alright. Ni komenci. Ĝuste nun mi rigardas paĝo 3 de la Problemo Ara Specification. Ni iras al unua komenci paroli pri duumaj arboj pro tio ke tiuj havas multe da graveco al ĉi tiu semajno problemo aro - la Huffman Arbo kodigo. Unu el la tre unua datumstrukturoj ni parolis pri la CS50 estis la tabelo. Memoru ke tabelo estas vico de eroj - ĉiuj de la sama tipo - stokita dekstra flanko de la alia en memoro. Se mi havas entjero tabelo, ke mi povas desegni uzante ĉi skatoloj-numerojn-entjeroj stilo - Diru Mi havas 5 en la unua skatolo, mi havas 7 en la dua, tiam mi havas 8, 10, kaj 20 en la fina skatolo. Memoru, la du vere bona aferojn pri ĉi tiu tabelo estas ke ni havas ĉi konstanta tempo aliron al iu aparta elemento  en la tabelo se ni scias lian indekso. Ekzemple, se mi volas kapti la tria elemento en la tabelo - ĉe indekso 2 uzante nian nulo-bazita indeksado sistemo - Mi laŭvorte nur devas fari simplan matematikan kalkulo, hop por tiu posteno en la tabelo, eltiri la 8 kiu stokas tie, kaj mi estas bona por iri. 

Unu el la malbonaj aferoj pri tiu tabelo - ke ni parolis pri kiam ni diskutis ligitaj listoj - estas ke se mi volas enmeti ero en ĉi tiun tabelo, Mi tuj devos fari iu movo ĉirkaŭe. Ekzemple, ĉi tabelo ĉi tie estas en ordo ordo - ordo en suprenira ordo - 5, tiam 7, tiam 8, tiam 10, kaj poste 20 - sed se mi volas enmeti la numero 9 en tiun tabelo, Mi tuj devos ŝanĝi kelkajn el la elementoj por fari spacon. Ni povas desegni tiun ĉi tie. Mi tuj devos kopii la 5, la 7, kaj tiam la 8; krei truon, kie mi povas meti la 9, kaj tiam la 10an kaj la 20an povas iri al la rajto de la 9. Tio estas speco de doloro ĉar en la plej malbona-kazo scenaro - kiam ni havi por enmeti aŭ komence aŭ fine de la tabelo, depende de kiom ni movo - ni povus fini devi ŝanĝi ĉiujn elementojn ke ni nuntempe stokante en la tabelo. 

Do, kio estis la maniero ĉirkaŭ ĉi? La vojo ĉirkaŭ ĉi estis iri al nia kunligita-listo metodo kie - anstataŭ konservi la elementoj 5, 7, 8, 10, kaj 20 ĉiuj apud la alia en memoro - kion ni anstataŭ tio estis stoki ilin ia ajn ni volis konservi ilin en ĉi tiuj ligitaj-listo nodoj kiuj mi desegnon el tie, ia ad hoc. Kaj tiam ni konektis ilin kune uzante tiujn sekva punteros. Mi povas havi puntero de 5 al la 7, puntero de la 7 al la 8, puntero de la 8 ĝis la 10, kaj fine, puntero de la 10 al la 20, kaj tiam nula puntero je la 20 indikante ke ekzistas nenio maldekstren. La komerco-off, ke ni havas ĉi tie estas ke nun, se ni volas enmeti la numero 9 en niajn ordo listo, ĉiuj ni devas fari estas krei novan nodon kun 9, telegramon gxin rekte al la adekvata loko, kaj tiam re-drato la 8 atentigi malsupren al la 9. Tio estas bela rapida, supozante ni scias precize kie ni volas enmeti la 9. Sed la komerco-off kontraŭ ĉi tiu estas ke ni nun perdis la konstanta tempo aliro al iu aparta ero en nia datumstrukturo. Ekzemple, se mi volas trovi la kvara elemento en ĉi ligillisto, Mi tuj devos starti je la komenco de la listo kaj labori mian vojon tra rakonti nodo-per-nodo ĝis mi trovos la kvaran oni. 

Por akiri pli bonan aliron agado ol ligitaj listo - sed ankaŭ konservas iujn de la profitoj kiujn ni havis en terminoj de inserción-tempo de ligitaj listo - duuma arbo tuj bezonas uzi iom pli memoro. En aparta, anstataŭ nur havi unu puntero en duuma arbo nodo - kiel la kunligita-listo nodo faras - nin tuj aldoni duan sagon al la duuma arbo nodo. Anstataŭ nur havi sagon al la sekva elemento, ni tuj havos puntero al maldekstra infano kaj dekstra infano. 

Ni desegni bildon por vidi kion tio efektive aspektas. Denove, mi tuj uzos tiujn skatolojn kaj sagojn. A duuma arbo nodo dividos kun nur simpla skatolo. Oni tuj havos spacon por la valoro, kaj tiam ĝi estas ankaŭ havos spacon por la maldekstra infano kaj la dekstra infano. Mi tuj etikedi ilin ĉi tie. Ni havos la maldekstra infano, kaj poste ni iras al rajtas infano. Estas multaj malsamaj manieroj de fari tion. Kelkfoje por spaco kaj komforto, Mi vere desegni ĝin kiel mi faras tie ĉi sur la fundo kie mi havos la valoron ĉe la supro, kaj tiam la dekstra infano sur la fundon-dekstra, kaj la maldekstra infano sur la fundon-maldekstren. Reiros al ĉi supro diagramo, ni havas la valoron je la plejsupro, tiam ni havas la maldekstra infano pointer, kaj poste ni rajtas-infano puntero. 

En la Problemo Ara Specification, ni parolas pri desegni nodo kiu havas valoro 7, kaj tiam maldekstra infano puntero kiu estas nula, kaj dekstra infano puntero kiu estas nula. Ni povas ĉu verki ĉefurbo NULL en la spaco por ambaŭ la maldekstra infano kaj la dekstra infano, aŭ ni povas desegni ĉi diagonalo oblikvo tra ĉiu el la skatoloj por indiki, ke estas nula. Mi faros tion nur ĉar tio estas pli simpla. Kion vi vidas ĉi tie estas du vojoj de diagramming tre simpla duuma arbo nodo kie ni havas la valoron 7 kaj nula infano punteros. 

La dua parto de nia specifo prelegoj pri kiel kun ligitaj listoj - memoru, ni nur devis tenadi la unua ero en listo memori la tutan liston - kaj tiel same, kun duargumenta arbo, ni nur devas tenadi unu sagon al la arbo por subteni kontrolo super la tuta datumstrukturo. Ĉi tiu speciala elemento de la arbo oni nomas la radika vertico de la arbo. Ekzemple, se ĉi tiu nodo - ĉi nodo enhavanta la valoron 7 kun nula maldekstra kaj dekstra infano punteros - estis la sola valoro de nia arbo, tiam ĉi tio estus nia radika nodo. Ĝi estas la komenco de nia arbo. Ni povas vidi ĉi iom pli klare iam ni eku aldoni pli nodoj al nia arbo. Lasu min eltiri novan paĝon. 

Nun ni iras por desegni arbon kiu havas 7, je la radika, kaj 3 ene de la maldekstra infano kaj 9 ene de la dekstra infano. Denove, tio estas bela simpla. Ni havas 7, desegni nodo por la 3, nodo por 9, kaj mi tuj metis la maldekstra infano puntero de 7 al punkto al la nodo enhavanta 3, kaj la dekstra infano puntero de la nodo enhavanta 7 al la nodo enhavanta 9. Nun, ekde 3 kaj 9 ne havas infanojn, nin tuj metis ĉiujn siajn infano punteros esti nula. Ĉi tie, la radiko de nia arbo korespondas al la nodo enhavanta la numero 7. Vi povas vidi ke se ĉiuj ni havas estas puntero al tiu radiko nodo, ni povas tiam marŝi tra niaj arbo kaj konsenti ambaŭ infanaj verticoj - ambaŭ 3 kaj 9. Neniu bezonas subteni punteros al ĉiu unuopa nodo en la arbo. Alright. Nun ni iras aldoni alian nodon al ĉi tiu figuro. Ni tuj aldonos nodo enhavanta 6, kaj ni tuj aldonu tion kiel la dekstra filo de la nodo enhavanta 3. Por fari tion, mi tuj viŝi ke nula puntero en la 3-nodon kaj telegramon gxin rekte al la nodo enhavanta 6. Alright. 

Je ĉi tiu punkto, ni transiru iomete da terminologio. Por komenci, la kialo ke ĉi nomiĝas binara arbo en aparta estas ke ĝi havas du infano punteros. Estas aliaj specoj de arboj kiu havas pli infano punteros. En aparta, vi faris 'provi' en Problemo Serio 5. Vi rimarkos ke en tiu try, vi havis 27 malsamajn punteros al malsamaj infanoj - unu por ĉiu el la 26 literoj en la angla alfabeto, kaj tiam la 27a por la apostrofo - do, jen simila al tipo de arbo. Sed ĉi tie, pro tio la duuma, ni nur havas du infano punteros. 

Aldone al ĉi tiu nodo radiko, ke ni raportis, ni ankaŭ ĵetis ĉirkaŭ ĉi termino 'infano'. Kion ĝi signifas por unu nodo esti knabo de alia nodo? Ĝi laŭvorte signifas ke infano nodo estas infano de alia nodo se tiu alia nodo havas unu el liaj infano punteros starigis al punkto al tiu nodo. Meti ĉi tion en pli konkreta terminoj, se 3 estas montradis per unu el la infano punteros de 7, tiam 3 estas infano de 7. Se ni devis eltrovi kio estas la filoj de 7 estas - bone, ni vidas ke 7 havas puntero al 3 kaj puntero al 9, tiel 9 kaj 3 estas la filoj de 7. Naŭ ne havas infanojn pro lia infano punteros estas nulaj, kaj 3 havas nur unu infanon, 6. Ses ankaŭ ne havas infanojn ĉar ambaŭ de liaj indikoj estas nulaj, kiun ni devos desegni nun. 

Aldone, ni ankaŭ parolas pri la gepatroj de aparta nodo, kaj ĉi tio estas, kiel vi atendus, la dorsflanko de tiu infano priskribo. Ĉiu vertico havas nur unu patro - anstataŭ du kiel vi eble atendas kun homoj. Ekzemple, la patro de 3 estas 7. La patro de 9 estas ankaŭ 7, kaj la patro de 6 estas 3. Ne multe por tio. Ni ankaŭ havas terminojn por raporti geavoj kaj genepoj, kaj pli ĝenerale parolas pri la prauloj kaj posteuloj de aparta nodo. La praulo de vertico - aŭ prapatroj, pli ĝuste, de nodo - estas ĉiuj de la nodoj, kiuj staras en la vojo de la radiko al tiu nodo. Ekzemple, se mi rigardas la nodo 6, tiam la prapatroj tuj esti ambaŭ 3 kaj 7. La prapatroj de 9, ekzemple, estas - se mi rigardas la nodo 9 - tiam la patro de 9 estas nur 7. Kaj posteuloj estas akurate la reverso. Se mi volas rigardi ĉiujn posteulojn de 7, tiam mi devas rigardi ĉiujn nodoj sub ĝi. Do, mi havas 3, 9, kaj 6 ĉiuj kiel posteuloj de 7. 

La fina termino kiu ni parolos pri estas ĉi nocio de estante frato. Gefratoj - speco de post kune sur tiuj familio terminoj - estas nodoj kiuj estas je la sama nivelo en la arbo. Do, 3 kaj 9 estas gefratoj, ĉar ili estas je la sama nivelo en la arbo. Ili ambaŭ havas la saman patro, 7. La 6 ne havas fratojn ĉar 9 ne havas infanojn. Kaj 7 ne havas neniun gefratoj ĉar ĝi estas la radiko de nia arbo, kaj tie estas nur iam 1 radiko. Dum 7 havi gefratoj tie devus esti nodo supre 7. Tie devus esti patro de 7, en kies kazo 7 kaj kiu ne estus la radiko de la arbo. Tiam tiu nova patro de 7 ankaŭ devus havi infanon, kaj ke infano devus tiam esti la frato de 7. 

Alright. Movante plu. Kiam ni komencis nian diskuton de duumaj arboj, ni parolis pri kiel ni tuj uzi ilin por gajni avantaĝon super ambaŭ tabeloj kaj kunligita listoj. Kaj la vojon ni tuj faros kiu estas kun ĉi ordigante proprieto. Ni diru ke duuma arbo estas ordigita laŭ la specifo, se por ĉiu nodo en nia arbo, ĉiu el liaj posteuloj maldekstre - la maldekstra infano kaj ĉiuj de la maldekstra infano posteuloj - havas malpli valoroj, kaj ĉiuj de la nodoj ĉe la dekstra - Dekstre infano kaj ĉiuj la rajton infano posteuloj - havi nodoj granda ol la valoro de la nuna nodo ke ni rigardas. Nur por simpleco, ni tuj supozi ke estas nenia duplikatajn nodoj en nia arbo. Ekzemple, en ĉi tiu arbo ni ne tuj pritrakti la kazon kie ni havas la valoron 7, je la radika  kaj tiam ni ankaŭ havas la valoron 7 aliloke en la arbo. En ĉi tiu kazo, vi rimarkos ke la arbo estas fakte ordigita. Ni havas la valoron 7, je la radiko. Ĉiu al la maldekstra de 7 - se mi malfari ĉiuj el ĉi tiuj malgranduloj markoj tie - ĉiun al la maldekstra de 7 - la 3 kaj la 6 - tiuj valoroj estas tiel malpli ol 7, kaj ĉiu al la dekstra - kiu estas ĝuste ĉi tiu 9 - estas pli granda ol 7. 

Tiu ne estas la sola ordigis arbo kiu enhavas tiujn valorojn, sed ni desegni kelkajn pli el ili. Estas vere tutan faskon da manieroj kiujn ni povas fari ĉi tion. Mi tuj uzos stenografio nur por subteni la aĵojn simpla kie - anstataŭ desegni ekster la tuta skatoloj-kaj-sagojn - Mi nur tuj desegni la numeroj kaj aldonu sagojn konektante ilin. Por komenci, ni simple skribu nian originalan arbo, kie ni havis 7, kaj tiam 3, kaj tiam 3 pinta reen al la rajto al la 6, kaj 7 havis rajton infano kiu estis 9. Alright. Kio estas alia maniero por ke ni povus skribi ĉi arbo? Anstataŭ havi 3 esti la maldekstra infano de 7, ni povus havi ankaŭ la 6 esti la maldekstra infano de 7, kaj tiam 3 esti la maldekstra infano de la 6. Tio aspektas kiel tiu arbo ĉi tie kie mi havas 7, tiam 6, tiam 3, kaj 9 dekstre. Ni ankaŭ ne devas havi 7 kiel nia radika nodo. Ni povus ankaŭ havi 6 kiel nia radika nodo. Kion tio aspektas? Se ni iras al subteni ĉi ordigis proprieto, ĉiun al la maldekstra de la 6 devas esti malpli ol tio. Estas nur unu eblo, kaj tio estas 3. Sed tiam kiel la dekstra filo de 6, ni havas du eblecojn. Unue, ni povus havi la 7 kaj poste la 9, aŭ ni povus desegni ĝin - kiel mi estas faronta tie - kie ni havas la 9 kiel la rajto infano de la 6, kaj tiam la 7 kiel la maldekstra infano de la 9. 

Nun, 7 kaj 6 ne estas la solaj eblaj valoroj por la radiko. Ni povus ankaŭ havi 3 esti je la radiko. Kio okazas se 3 estas ĉe la radiko? Ĉi tie, aĵoj iom interesa. Tri ne havas neniun valoroj kiuj estas malpli ol ĝi, por ke tuta maldekstra flanko de la arbo estas simple tuj estos nula. Tie ne iras al esti io tie. Dekstre, ni povus listigi aĵojn en suprenira ordo. Ni povus havi 3, tiam 6, tiam 7, tiam 9. Aŭ, ni povis fari 3, tiam 6, tiam 9, tiam 7. Aŭ, ni povis fari 3, tiam 7, tiam 6, tiam 9. Aŭ, 3, 7 - fakte ne, ni ne povas fari ĉirkaŭ 7 plu. Tio estas nia unu afero tie. Ni povas fari 9, kaj tiam el la 9 ni povas fari 6 kaj poste 7. Aŭ, ni povas fari 3, tiam 9, tiam 7, kaj tiam 6. 

Unu afero atentigi vin tie estas ke tiuj arboj estas iom stranga aspekto. En aparta, se ni rigardas la 4 arboj sur la dekstra flanko - Mi ĉirkaŭiri ilin, tie - tiuj arboj aspektas preskaŭ ekzakte kiel ligitaj listo. Ĉiu vertico havas nur unu infanon, kaj tiel ni ne havas iu ajn el ĉi tiu arbo-simila strukturo kiu ni vidas, ekzemple,  en ĉi tiu sola arbo super tie sur la fundo maldekstren. Tiuj arboj estas reale nomita degeneri duumaj arboj, kaj ni parolos pri tiuj pli en la estonteco - precipe se vi iras preni aliaj komputikaj kursoj. Tiuj arboj estas degenera. Ili ne estas tre utilaj ĉar, ja, tiu strukturo pruntas  al lookup fojoj simila al tiu de ligitaj listo. Ni ne komprenas utiligi la ekstra memoro - tiu ekstra puntero - pro nia strukturo esti malbona en tio. Anstataŭ daŭrigi kaj nudigos la duuma arboj kiuj havas 9, je la radika, kiu estas la lasta kazo, ke ni devus, ni estas loko, en ĉi tiu punkto, tuj parolos iomete pri tiu alia termino ke ni uzas kiam parolas pri arboj, kiu estas nomata la alteco. 

La alteco de arbo estas la distanco de la radiko ĝis la plej malproksima-nodo, aŭ pli ĝuste la nombro de lupolo, ke vi devus fari por komencos de la radiko kaj tiam finas ĉe la plej malproksima vertico en la arbo. Se ni rigardas iujn el tiuj arboj, kiujn ni desegnis ĉi tie, ni povas vidi ke se ni prenos ĉi arbo en la supra maldekstra angulo kaj ni starti je la 3, tiam ni devas fari 1 lupolo por atingi la 6, dua lupolo por atingi la 7, kaj triono lupolo por atingi la 9. Do, la alteco de ĉi tiu arbo estas 3. Ni povas fari la saman taskon pri la aliaj arboj konturita kun ĉi verda, kaj ni vidos, ke la alteco de ĉiuj el tiuj arboj estas ankaŭ ja 3. Tio estas parto de tio, kio igas ilin degeneri - ke ilia alteco estas nur unu malpli ol la nombro de nodoj en la tuta arbo. Se ni rigardas tiun aliaj arbo jen ĉirkaŭitaj per ruĝaj, aliflanke, ni vidas ke la plej malproksima folio nodoj estas la 6 kaj la 9 - la folioj estas tiuj nodoj, kiuj ne havas infanojn. Do, por preni de la radika vertico al ĉu la 6 aŭ 9, ni devas fari unu lupolo por atingi la 7 kaj poste duan lupolo por atingi la 9, kaj simile, nur dua hop de la 7 al atingi la 6. Do, la alteco de ĉi tiu arbo super tie estas nur 2. Vi povas reiri kaj fari tion por ĉiuj el la aliaj arboj, ke ni antaŭe diskutis komencante kun la 7 kaj la 6, kaj vi trovos ke la alteco de ĉiuj el tiuj arboj estas ankaŭ 2. 

La kialo ni parolis pri ordigitaj duumaj arboj kaj kial ili estas malvarmaj estas ĉar vi povas serĉi per ili en tre simila maniero serĉado super ordo tabelo. Tie estas kie ni parolas pri atingi ke plibonigitaj lookup tempo super la simpla ligitaj listo. Kun ligitaj listo - se vi volas trovi apartan elementon - vi estas en la plej bona faros ian lineara serĉo kie oni komencas komence de lerta kaj lupolo unu-por-unu - unu nodo de unu nodo - tra la tutan liston ĝis vi trovos kion ajn vi sercxas. Dum, se vi havas duuma arbo ke tio stokitaj en ĉi bela formato, vi povas reale preni pli ol duuma serĉo okazas kie vi dividu kaj venkos kaj serĉo tra la taŭga duono de la arbo je ĉiu paŝo. Ni vidu kiel tiu verkoj. 

Se ni havas - denove, tuj reen al nia originala arbo - ni starti je 7, ni havas 3 maldekstre, 9 dekstre, kaj sub la 3 havas la 6. Se ni volas serĉi la nombro 6 en tiu arbo, ni volas komenci je la radiko. Ni devus kompari la valoron ni serĉas, diru 6, al la valoro stokita en la nodo ke ni nuntempe rigardante, 7, trovi ke 6 estas ja malpli ol 7, do ni volas movi al la maldekstra. Se la valoro de 6 estis pli granda ol 7, ni estus en loko kopiis al dekstre. Ĉar ni scias, ke - pro la strukturo de nia ordigitaj duumaj arbo - ĉiuj valoroj malpli ol 7 estas tuj estos stokitaj la maldekstra de 7, ne necesas eĉ tedas rigardi tra la dekstra flanko de la arbo. Iam ni movi al la maldekstra kaj ni estas nun en la nodo enhavanta 3, ni povas fari tion saman komparon denove kie oni komparas la 3 kaj la 6. Kaj ni trovos ke dum 6 - la valoron ni serĉas - estas pli granda ol 3, ni povas iri al la dekstra flanko de la nodo enhavanta 3. Ne maldekstra flanko tie, do ni povus esti ignorata tio. Sed ni nur scias ke ĉar ni rigardas la arbo mem, kaj ni povas vidi ke la arbo ne havas infanoj. 

Estas ankaŭ bela facile serĉi 6 en ĉi tiu arbo se ni faras ĝin mem kiel homoj, sed ni sekvi tiu procezo mekanike kiel komputilo estus fari por vere kompreni la algoritmo. Je ĉi tiu punkto, ni nun rigardas nodo kiu enhavas 6, kaj ni serĉas la valoro 6, do, ja, ni trovis la taŭgan nodo. Ni trovis la valoron 6 en nia arbo, kaj ni povas halti nian serĉo. Je ĉi tiu punkto, depende de tio, kio okazas, ni povas diri, jes, ni trovis la valoron 6, ekzistas en nia arbo. Aŭ, se ni planas enmeti nodo aŭ fari ion, ni povas fari ĉe ĉi tiu punkto. 

Ni faru paro pli serĉoj nur por vidi kiel tio funkcias. Ni rigardu kio okazas se ni devis provi kaj serĉi la valoron 10. Se ni devis serĉi la valoron 10, ni devus komenci je la radiko. Ni ŝatus vidi ke 10 estas pli granda ol 7, do ni volas movi al dekstre. Ni ŝatus alveni al la 9 kaj kompari 9 al la 10 kaj vidi ke 9 estas ja malpli ol 10. Do denove, ni volas provi kopii al dekstre. Sed en ĉi tiu punkto, ni volas rimarki ke ni estas en nula nodo. Nenio tie. Nenio kie la 10 devus esti. Tie estas kie ni povas raporti fiasko - tio estas ja ne 10 en la arbo. Kaj fine, ni iru tra la kazo kie ni provas serĉi 1 en la arbo. Ĉi tio estas simila al kio okazas se ni rigardas supren 10, krom anstataŭ iri al la dekstra, ni tuj iros al la maldekstra. Ni starti je la 7 kaj vidas ke 1 estas malpli ol 7, do ni movi al la maldekstra. Ni atingos la 3 kaj vidas ke 1 estas malpli ol 3, do ni denove provas movi al la maldekstra. Je ĉi tiu punkto ni havas nula nodo, do ni denove povas raporti fiasko. 

Se vi volas lerni pli pri duumaj arboj, ekzistas tuta amaso de amuzo iom problemoj kiujn vi povas fari kun ili. Mi sugestas praktiki la desegno el tiuj diagramoj unu-por-unu kaj post tra ĉiuj malsamaj ŝtupoj, ĉar ĉi venos en super-oportuna ne nur kiam vi faras la Huffman kodigo problemo aro sed ankaŭ en estonteco kursoj - nur lerni kiel nudigos tiuj datumstrukturoj kaj pensi per la problemoj kun plumo kaj papero aŭ, en ĉi tiu kazo, iPad kaj grifelo. 

Je ĉi tiu punkto tamen, ni iras al movi sur fari iu kodigo praktiko kaj reale ludi kun tiuj binaraj arboj kaj vidi. Mi tuj ŝanĝi reen super al mia komputilo. Por ĉi tiu parto de la sekcio, anstataŭ uzi CS50 Run aŭ CS50 Spacoj, Mi tuj uzos la aparaton. 

Post kune kun la problemo Ara specifo, Mi vidas ke mi devus malfermi la aparaton, iri al mia Dropbox dosierujo, krei dosierujo nomita Sekcio 7, kaj poste krei dosieron nomatan binary_tree.c. Ĉi tie ni iru. Mi havas la aparaton jam malfermitaj. Mi iros elsxiros fina. Mi tuj iros al la Dropbox dosierujo, faru dosierujo nomita section7, kaj vidi estas tute malplena. Nun mi iros por malfermi binary_tree.c. Alright. Ĉi tie ni iru - malplena dosiero. 

Ni reiru al la specifo. La specifo petas krei novan tipon difino por duuma arbo nodo enhavanta int valoroj - same kiel la valoroj kiujn ni eltiris en nia diagramming antaŭe. Ni tuj uzos ĉi Boilerplate typedef ke ni faris ĉi tie ke vi rekonas el Problemo Serio 5 - se vi faris la hash tablo vojo de konkerantoj la Speller programo. Vi devus ankaŭ rekonas ĝin de la pasinta semajno sekcio kie ni parolis pri ligitaj listoj. Ni havas ĉi typedef de struct nodo, kaj ni donis ĉi struct nodo ĉi nomo de struct nodo antauxe tiel ke ni povas tiam referi al ĝi ekde ni volas havi struct nodo punteros kiel parto de nia struct, sed ni tiam cxirkauxis tiun - aŭ pli ĝuste, enfermita ĉi - en typedef tiel ke, poste en la kodo, ni povas raporti al ĉi struct kiel ĝuste nodo anstataŭ struct nodo. 

Ĉi tuj estos tre simila al la unuope-ligillisto difino, kiun ni vidis la pasintan semajnon. Por tion fari, ni komencu per skribanta el la Boilerplate. Ni scias, ke ni devas havi entjero valoro, do ni metos en int valoron, kaj tiam anstataŭ havi nur unu sagon al la sekva elemento - kiel ni faris kun unuope-ligitaj listoj - ni havos maldekstra kaj dekstra infano punteros. Tio estas bela simpla tro - struct nodo * maldekstra infano; kaj struct nodo * dekstra infano. Cool. Tio aspektas kiel sufiĉe bona komenco. Ni reiru al la specifo. 

Nun ni bezonas por deklari tutmonda nodo * variablo por la radiko de arbo. Ni tuj faros ĉi tutmonda samkiel ni faris unuan puntero en nia ligitaj listo ankaŭ tutmonda. Tio estis tiel ke en la funkcioj kiuj ni skribi ni ne devas subteni pasi ĉirkaŭ ĉi radikon - kvankam ni vidos, ke se vi faros volas skribi tiujn funkciojn rekursie, gxi estu pli bone eĉ ne pasi ĝin ĉirkaŭ kiel tutmonda en unua loko kaj anstataŭ pravalorizi ĝin loke en via ĉefa funkcio. Sed, ni tion faros sume por komenci. Denove, ni donos kelkajn spacoj, kaj mi iros por deklari nodo * radiko. Nur por certigi ke mi ne forlasi tiun uninitialized, mi tuj metis ĝin egala al nula. Nun, en la ĉefa funkcio - kiu ni skribas vere rapide dekstre tie - int main (int argc, const char * argv []) - kaj mi tuj komencos deklari mian argv tabelo kiel const nur tiel, ke mi scias ke tiuj argumentoj estas argumentoj, ke mi probable ne volas modifi. Se mi volas modifi ilin mi probable faris kopiojn de ili. Vi vidos ĉi multon en kodo. Ĝi estas bone ajna maniero. Ĝi estas bone lasi ĝin kiel - preterlasi la const se vi ŝatus. Mi kutime metis ĝin en nur por ke Mi memoras min  ke mi probable ne volas modifi tiujn argumentojn. 

Kiel ĉiam, mi tuj inkluzivi ĉi reveno 0 linio je la fino de ĉefa. Jen, mi pravalorizi miaj radiko nodo. Kiel ĝi staras nun, mi havas puntero ke tio starigis al nula, do ĝi estas montrante nenion. Por efektive komenci konstrui la nodo, Mi unue bezonas rezervi memoron por ĝi. Mi faros tion farante memoro sur la havaĵon uzante malloc. Mi tuj starigis radiko egala al la rezulto de malloc, kaj mi tuj uzos la sizeof operatoro por kalkuli la grandecon de nodo. La kialo, ke mi uzas sizeof nodo kontraste al, diros, faras ion kiel tiu - malloc (4 + 4 +4) aŭ malloc 12 - estas ĉar mi volas mian kodon por esti kiel kongruaj ebla. Mi volas povi preni tion. C dosiero, kompili ĝin sur la aparaton, kaj tiam kompili ĝin sur mia 64-bita Mac - aŭ tute malsama arkitekturo - kaj mi volas tiun tutan labori la sama. 

Se mi faras supozojn pri la grandeco de variabloj - la grandeco de int aŭ la grandecon de puntero - tiam Mi ankaŭ faras supozojn pri la specoj de arkitekturoj sur kiu mia kodo povas sukcese kompili kiam kuri. Ĉiam uzi sizeof kiel kontraŭ permane sumanta la struct kampoj. La alia kialo estas, ke tie povus ankaŭ esti Plenigado ke la tradukilo metas en la struct. Eĉ nur sumanta la individuaj kampoj ne estas iu kiu vi tipe volas fari, tiel, forviŝi tiun linion. Nun, por vere pravalorizi ĉi radiko nodo, Mi tuj devos ŝtopi en valoroj por ĉiu el ĝiaj malsamaj kampoj. Ekzemple, por valoro Mi scias mi volas pravalorizi al 7, kaj cxar nun mi iros al starigis la maldekstran infano esti nula kaj la dekstra infano ankaŭ esti nula. Bonega! Ni faris tiun parton de la specifon. 

La specifo malsupren sur la fundo de la paĝo 3 demandas min krei tri pli nodoj - unu enhavanta 3, unu enhavante 6, kaj unu kun 9 - kaj tiam telegramon ilin tiom ĝi aspektas precize kiel nia arbo diagramon ke ni parolis pri antaŭe. Ni faras tion sufiĉe rapide tie. Vi vidos vere rapide, ke mi tuj komencu skribi faskon da duplikatajn kodo. Mi iros por krei nodo * kaj mi iros kaj nomas ĝin tri. Mi tuj metis ĝin egala al malloc (sizeof (nodo)). Mi tuj starigis tri-> valoro = 3. Tri -> left_child = NULL; tri -> dekstre _child = NULL; tiel. Tio aspektas bela simila al inicializar la radiko, kaj tio estas ĝuste kion Mi tuj devos fari se mi komencas inicializar 6 kaj 9 tiel. Mi faros, ke vere rapide tie - vere, mi faros iom kopio kaj alglui, kaj certigi, ke mi - bona.  Nun, mi got kopiis kaj mi povas antaŭeniri kaj starigis ĉi egala al 6. Vi povas vidi ke tiu prenas iom da tempo kaj ne estas super-efika. En malmulta, ni skribi funkcio kiu faros tion por ni. Mi volas anstataŭigi ĉi kun 9, anstataŭi ke kun 6. 

Nun ni havas nian tutan nodoj kreita kaj inicializado. Ni havas nian radiko starigis egala al 7, aŭ enhavas la valoron 7, nia nodo enhavanta 3, nia nodo enhavanta 6, kaj nia nodo enhavanta 9. Je ĉi tiu punkto, ĉiuj ni devas fari estas drato ĉio supren. La kialo mi inicializado ĉiuj punteros al nula estas nur por ke mi certiĝu, ke Mi ne havas neniun uninitialized punteros tien hazarde. Kaj ankaŭ pro tio ke, en ĉi tiu punkto, mi nur devas vere kunligi la nodoj inter si - al tiuj, kiuj ili estas reale ligita al - mi ne devas iri tra kaj fari certa, ke ĉiuj nulls estas en tie en la taŭgaj lokoj. 

Ekde la radiko, mi scias, ke la radiko la maldekstra infano estas 3. Mi scias, ke la radiko la dekstra infano estas 9. Post tio, la sola alia infano, ke mi forlasis zorgi pri estas 3 la dekstra infano, kiu estas 6. Je ĉi tiu punkto, ĉio aspektas sufiĉe bone. Ni forviŝi kelkajn el tiuj linioj. Nun ĉiu rigardas sufiĉe bone. Ni reiru al nia specifo kaj vidi kion ni devas fari. 

Je ĉi tiu punkto, ni devas skribi funkcion nomita 'enhavas' kun prototipo de 'bool enhavas (int valoro)'. Kaj tiu enhavas funkcion tuj revenos vera  se la arbo montris per nia tutmonda radiko variablo  enhavas la valoron transiris en la funkcio kaj falsaj alie. Ni faru tion. Ĉi tuj estos ĝuste kiel la serĉo, kiun ni faris per mano sur la iPad malmulta antaŭe. Estu la zoom reen en iomete kaj rulumu supren. Ni tuj metis ĉi funkcio dekstra supre nia ĉefa funkcio por ke ni ne devas fari ian prototipado. Do, bool enhavas (int valoro). Tie ni iru. Jen nia Boilerplate deklaro. Nur por certigi ke tiu estos kompili, Mi tuj iros antaŭen kaj nur starigis ĝin egala reveni falsaj. Ĝuste nun tiun funkcion nur ne faros nenion kaj ĉiam informi ke la valoro kiun ni serĉas ne estas en la arbo. 

Je ĉi tiu punkto, estas probable bona ideo - ekde ni skribis tuta amaso de kodo kaj ni eĉ ne provis taksi ĝin ankoraŭ - certigi ke ĉiuj kompilas. Estas kelkaj aferoj kiujn ni devas fari por certigi ke tiu estos efektive kompili. Unue, ĉu ni estis uzante ajnan funkcioj en ajna bibliotekoj ke ni ankoraŭ ne komprenis. La funkcioj ni uzis ĝis nun estas malloc, kaj tiam ni ankaŭ uzas tiun ĉi tipon - ĉi nenorma tipo nomita 'bool' - kio estas inkluzivita en la norma bool header dosiero. Ni definitive deziras inkludi normo bool.h por la bool tipo, kaj ni ankaŭ volas # include normo lib.h por la normo bibliotekoj kiuj inkludas malloc, kaj liberaj, kaj ĉio pri tio. Do, malzomi, ni tuj forlasis. Ni provu kaj certiĝu ke ĉi efektive faris kompili. Ni vidas ke ĝi faras, do ni estas sur la ĝusta vojo. 

Ni malfermi binary_tree.c denove. Ĝi kompilas. Ni iru malsupren kaj certigi ke ni enmetu iujn alvokojn al nia enhavas funkcio - nur por certigi ke jen ĉio bone kaj bona. Ekzemple, kiam ni faris kelkajn serĉoj en nia arbo antaŭe, ni provis serĉi la valoroj 6, 10, kaj 1, kaj ni sciis ke la 6 estis en la arbo, 10 ne estis en la arbo, kaj 1 ne estis en la arbo ĉu. Ni uzas tiujn specimeno alvokoj kiel maniero por kalkuli ĉu aŭ ne nia enhavas funkcion laboras. Por fari tion, mi tuj uzos la printf funkcio, kaj ni tuj presi la rezulto de la alvoko al enhavas. Mi tuj metos en ĉeno "enhavas (% d) = pro  ni iras al plug en la valoro kiun ni iras serĉi, kaj =% s \ n "kaj uzas tiun kiel nia formato kordoj. Ni nur tuj vidi - laŭvorte presi sur la ekrano - kio aspektas kiel funkcio nomita. Tio ne estas vere la funkcio nomita.  Tiu estas nur ĉeno desegnita por aspekti kiel funkcio nomita. 

Nun, ni tuj ŝtopi en la valoroj. Ni tuj provos enhavas la 6, kaj poste, kion ni faros ĉi tie estas uzi tiun triargumenta operatoro. Ni vidu - enhavas 6 - tiel, nun mi enhavis 6 kaj se enhavas 6 estas vera, la kordo, ke ni tuj sendi al la% s formato karaktero tuj estos la ĉeno "vera". Ni rulumi pli iom. Alie, ni volas sendi la ĉeno "falsa" se enhavas 6 revenas falsaj. Tio estas iom ansera-aspekta, sed mi rigardas mi povus tiel ilustri kion la triargumenta operatoro similas ĉar ni ne vidis ĝin dum kelka tempo. Tiu estos bela, oportuna maniero por kalkuli se nia enhavas funkcion laboras. Mi iros por rulumi reen super la maldekstra, kaj mi tuj kopii kaj alglui ĉi tiun linion kelkajn fojojn. Ĝi ŝanĝis kelkajn el tiuj valoroj ĉirkaŭe, tial ĉi tiu tuj esti 1, kaj tion oni tuj estos 10. 

Je ĉi tiu punkto ni havas belan enhavas funkcio. Ni havas kelkajn provojn, kaj ni vidos se ĉi ĉiuj verkoj. Je ĉi tiu punkto ni skribas iun pli kodo. Tempo lasi eksteren kaj certigi ke ĉiu ankoraŭ kompilas. Quit eksteren, kaj nun ni provu fari duuma arbo denove. Nu, tio aspektas kiel ni havas eraron, kaj ni atingis tiun eksplicite deklari la biblioteko funkcio printf. Ĝi aspektas kiel ni devas iri en kaj # include standardio.h. Kaj kun tio, ĉiu devus kompili. Ni estas ĉiuj bonaj. Nun ni provu kurante duuma arbo kaj vidu kio okazas. Jen ni estas,. / Binary_tree, kaj ni vidas tion, kiel ni atendis - ĉar ni ne ankoraŭ realigita enhavas ankoraŭ, aŭ pli ĝuste, ni ĵus metis en reveno falsaj - ni vidas ke ĝi estas nur redoni malvera por ĉiu el ili, tiel ke tio ĉio laboras plejparte sufiĉe bone. 

Ni iru reen en kaj efektive apliki enhavas je ĉi tiu punkto. Mi iros por rulumi malsupren, zomi, kaj - memoru, la algoritmo, ke ni uzis estis ke ni komencis ĉe la radika vertico kaj tiam ĉe ĉiu nodo, ke ni renkontas, ni faru komparon, kaj surbaze de tiu komparo ni ĉu movi al la maldekstra infano aŭ dekstre infano. Tiu tuj aspektas tre simila al la duuma serĉo kodo kiu ni skribis antaŭe en la termino. Kiam ni dividi, ni scias, ke ni volas tenadi la nuna nodo ke ni rigardas, kaj la nuna nodo tuj estos inicializado al la radika vertico. Kaj nun, ni iras plu iri tra la arbo, kaj memoru, ke nia haltante kondiĉo -  kiam ni efektive laboris tra la ekzemplo mane - Estis kiam ni renkontis nula nodo, ne kiam ni rigardis nula infano, sed prefere kiam ni efektive translokiĝis al nodo en la arbo kaj trovis, ke ni estas en nula nodo. Ni tuj persisti ĝis nuna ne estas egala al nula. Kaj kion ni faros? Ni tuj testi se (nuna -> valoro == valoro), tiam ni scias ke ni vere trovis la nodo ke ni serĉas. Do jen, ni povas reveni vera. Alie, ni volas vidi, ĉu aŭ ne la valoro estas malpli ol la valoro. Se la nuna nodo valoro estas malpli ol la valoro ni serĉas, ni iras al movi al dekstre. Do, nuna = nuna -> right_child, kaj alie, ni iras al movi al la maldekstra. nuna = nuna -> left_child;. Bela simpla. 

Vi verŝajne rekoni la buklo kiun aspektas tre simila al tiu de duuma serĉo antaŭe en la termino, krom tiam ni pritraktas malalta, meze, kaj alta. Tie, ni nur devas rigardi aktualan valoron, do ĝi estas bela kaj simpla. Ni certigi ĉi tiun kodon laboras. Unue, certigu kompilas. Aspektas kiel ĝi faras. Ni provu kurante ĝin. Kaj ja, ĝi presas el ĉio, kio ni atendis. Li trovas 6 en la arbo, ne trovas 10 ĉar 10 estas ne en la arbo, kaj ne trovas 1 bone ĉar 1 estas ankaŭ ne en la arbo. Cool stuff. 

Alright. Ni reiru al nia specifo kaj vidu kio estas proksima. Nun, ĝi volas aldoni iun pli nodoj al nia arbo. Ĝi volas aldoni 5, 2, kaj 8, kaj certigi ke nia enhavas kodo ankoraŭ funkcias kiel atendita. Ni iru do that. Je ĉi tiu punkto, anstataŭ fari tion tedas kopio kaj alglui denove, ni skribu funkcio por fakte krei nodo. Se ni rulumu malsupren la tuta vojo al la ĉefa, ni vidas ke ni estis farante tiun tre simila kodo denove kaj denove ĉiufoje ke ni volas krei nodo. 

Ni skribi funkcion kiu vere konstruos nodo por ni kaj redoni ĝin. Mi iros nomi ĝin build_node. Mi iros por konstrui nodo kun aparta valoro. Zomi tie. La unua afero Mi faros fakte krei spacon por la nodo sur la monteto. Do, nodo * n = malloc (sizeof (nodo)); n -> valoro = valoro; kaj tiam ĉi tie, mi nur iras al pravalorizi ĉiuj kampoj por esti taŭga valoroj. Kaj je la fino, ni revenos nia nodo. Alright. Unu afero noti estas ke tiu funkcio ĉi tie tuj revenos puntero al memoro kiu estis amaso-destinis. Kio estas agrable pri tio estas ke tiu nodo nun - ni devas deklari gxin sur la havaĵon ĉar se ni deklaras ĝin sur la stako ni ne povos fari ĝin en tiu funkcio kiel ĉi tio. Tiu memoro irus el atingo kaj estus nevalida se ni provis aliri ĝin poste. Ekde ni deklari amason-asignitaj memoro, tuj devas prizorgi liberigante ĝin poste por nia programo ne filtri ajna memoro. Ni estis punting en tiu por ĉio alia en la kodo nur por simpleco, kalkaj en la momento, sed se vi iam skribi funkcion kiu similas tiun kie vi havas - iuj nomas ĝin malloc aŭ realloc interne - vi volas certigi ke vi metis ian komenton ĉi tien kiu diras, hey, vi scias, denove amason-asignitaj nodo inicializado kun la pasinta-en valoro. Kaj tiam vi volas certigi ke vi metis en ia noto kiu diras la telefonanto devas liberigi la memoron revenis. Tiun vojon, se iu iam iras kaj uzas tiun funkcion, ili scias, ke kion ajn ili reiros de tiu funkcio en iu momento bezonos esti liberigita. 

Supozante ke cxio estas bone kaj bonajn tie, ni povas iri en nian kodon kaj anstataŭu ĉiujn el tiuj linioj ĉi tie kun alvokoj al nia build nodo funkcio. Ni faras tion vere rapide. La parto kiu ni ne tuj anstataŭigi estas tiu parto cxi tie ĉe la malsupro, kie ni fakte telegramon ĝis la nodoj noti al si, ĉar ni ne povas fari en nia funkcio. Sed, ni faru radiko = build_node (7); nodo * tri = build_node (3); nodo * ses = build_node (6); nodo * naŭ = build_node (9);. Kaj nun, ni ankaŭ volis aldoni nodoj por - nodo * kvin = build_node (5); nodo * ok = build_node (8); kaj kio estis la alia vertico? Vidu ĉi tie. Ni volis ankaŭ aldoni 2 - nodo * du = build_node (2);. Alright. Je ĉi tiu punkto, ni scias ke ni havas la 7, la 3, la 9, kaj la 6 ĉiuj telegramis supren taŭge, sed kio pri la 5, la 8, kaj la 2? Teni ĉion en la taŭgan ordon, ni scias ke tri la dekstra infano estas 6. Do, se ni tuj aldonu la 5, la 5 ankaŭ apartenas en la dekstra flanko de la arbo de kiuj 3 estas la radiko, tiel 5 apartenas la maldekstra infano de 6. Ni povas fari ĉi tion dirante, ses -> left_child = kvin; kaj tiam la 8 apartenas la maldekstra infano de 9, do naŭ -> left_child = ok; kaj poste 2 estas la maldekstra infano de 3, do ni povas fari tion ĝis tie - vi -> left_child = du;. Se vi ne sufiĉe sekvi kune kun tio, mi sugestas al vi desegni ĝin vi mem. 

Alright. Ni savu ĉi. Ni eliros kaj certigi kompilas, kaj tiam ni povas aldoni en nia enhavas alvokoj. Aspektas kiel ĉiu ankoraŭ kompilas. Ni iru en kaj aldoni en iu enhavas alvokoj. Denove, mi faros iom de kopio kaj pasto. Nun estu la serĉo por 5, 8, kaj 2. Alright. Ni certigu ke ĉi ĉiuj aspektas bone ankoraŭ. Bonega! Gardi kaj quit. Nun ni faru, kompili, kaj nun ni kuras. El la rezultoj, ĝi aspektas kiel cxio funkcias nur bela kaj bone. Bonega! Do nun ni havas niajn enhavas funkcion skribita. Ni movi sur kaj komenci labori pri kiel enmeti nodoj en la arbo pro tio ke, kiel ni faras ĝin nun, aĵoj ne estas tre bela. 

Se ni reiru al la specifo, ĝi petas al ni skribi funkcion nomita insertar - denove, revenante al bool cxar se ne ni povus efektive enŝovu la nodo en la arbo - kaj tiam la valoro por enmeti en la arbo estas specifita kiel la sola argumento por nia insert funkcio. Ni revenos vera se ni povus ja enmetas la nodo enhavanta valoro al la arbo, kio signifas, ke ni, unu, havis sufiĉan memoron, kaj poste du, kiu nodo ne jam ekzistas en la arbo ekde - memoru, ni ne tuj havas duplikatajn valoroj en la arbo, nur por fari aĵojn simpla. Alright. Back al la kodo. Malfermu ĝin. Zoom en iom, tiam rulumu malsupren. Ni metis la insert funkcio dekstra super la enhavas. Denove, ĝi tuj nomos bool insert (int valoro). Donu ĝin iom pli da spaco, kaj tiam, kiel defaŭlta, ni metas en reveno falsa al la fino. Nun malsupren sur la fundo, ni iru antaŭen kaj anstataŭ permane konstrui la nodoj en ĉefa nin kaj cableado ilin atentigi al la alia kiel ni faras, ni fidas niajn insert funkcio por fari tion. Ni ne fidi niajn insert funkcio por konstrui la tuta arbo de nulo nur ankoraŭ, sed prefere ni forigi tiujn liniojn - we'll comment el tiuj linioj - ke konstrui la nodoj 5, 8, kaj 2. Kaj anstataŭe, ni enŝovu alvokoj al nia insert funkcio por certiĝi ke tiu fakte funkcias. Ĉi tie ni iru. 

Nun ni diris ĉi tiujn liniojn. Ni nur havas 7, 3, 9, kaj 6 en nia arbo ĉe ĉi tiu punkto. Por certigi ke ĉi tio ĉiuj laboras, ni povas malzomi, fari nian duuma arbo, ruli ĝin, kaj ni povas vidi ke ĝi enhavas nun diras al ni ke ni tute rajtas - 5, 8, kaj 2 jam ne en la arbo. Iru returne en la kodo, kaj kiel ni tuj enigi? Memoru, kion ni faris kiam ni efektive enmeto 5, 8, kaj 2 antaŭe. Ni ludis tiun Plinko ludo kie ni komencis ĉe la radiko, malsupreniris la arbo unu post la alia per unu gxis ni trovis la taŭgan breĉo, kaj poste ni telegramis en la nodo ĉe la taŭga loko. Ni faros la samon. Tio estas esence kiel skribi la kodon kiun ni uzas en la enhavas funkcio trovi la lokon, kie la nodo devas esti, kaj tiam ni ĵus tuj enigi la nodo prava. Ni komencu fari tion. 

Do ni havas nodo * nuna = radiko; ni nur tuj sekvu la enhavas kodo ĝis ni trovos ke ĝi ne sufiĉe laboras por ni. Ni tuj iros tra la arbo dum la aktuala elemento ne estas nulaj, kaj se ni trovas ke nuna valoro egalas al la valoro kiu ni provas enmeti - bone, tio estas unu el la kazoj en kiuj oni ne povis reale enŝovu la nodo en la arbo ĉar ĉi signifas ke ni havas duplikatajn valoro. Jen ni fakte tuj revenos falsaj. Nun, alie se nuna valoro estas malpli ol valoro, nun ni scias ke ni movi al la dekstra  ĉar la valoro apartenas en la dekstra duono de la nuna arbo. Alie, ni iras al movi al la maldekstra. Tio estas esence nia enhavas funkcii ĝuste tie. 

Je ĉi tiu punkto, iam ni kompletigis ĉi dum ciklo, nia nuna puntero tuj estos montrante al nula se la funkcio ne jam revenis. Ni do havi nuna ĉe la loko, kie ni volas enmeti la novan nodo. Kio restas farenda estas reale konstrui la nova nodo, kion ni povas fari belajn facile. Ni povas uzi nian super-oportuna build nodo funkcio, kaj iu kiun ni ne faris pli frue - ni nur ia prenis por donita sed nun ni faros nur por certigi - ni testi por certigi ke la valoro revenis por nova nodo estis vere ne nula, ĉar ni ne volas komenci alirante kiun memoro se ĝi estas nula. Ni povas provi certigi ke nova nodo estas ne egala al nula. Aŭ male, ni povas nur vidi, ĉu ĝi vere estas nula, kaj se estas nula, tiam ni povas nur redoni malvera frue. 

Je ĉi tiu punkto, ni devas telegramon nova nodo en lia taŭga loko en la arbo. Se ni retrorigardas al la ĉefa kaj kie ni estis vere cableado en valoroj antaŭ, ni vidas ke la vojo ni faris ĝin kiam ni volis meti 3 en la arbo Estis ni Montrita la maldekstra infano de radiko. Kiam ni metas 9 en la arbo, ni devis aliri al la dekstra infano de la radiko. Ni devis havi sagon al la patro por enmeti novan valoron en la arbo. Movo reen ĝis enigi, ke ne estas tuj tute labori tie ĉar ni ne havas patro puntero. Kion ni volas por povi fari estas, en ĉi tiu punkto, kontrolu la gepatroj valoro kaj rigardu - nu, ho, se la gepatroj valoro estas malpli ol la aktuala valoro, tiam la patro la dekstra infano devus esti la nova vertico; se ne, la patro de maldekstra infano devus esti la nova nodo. Sed, ni ne havas tiun patro puntero sufiĉe ankoraŭ. 

Por akiri ĝin, ni fakte tuj devos sekvi ĝin kiel ni iru tra la arbo kaj trovi la taŭgan lokon en nia ciklo supre. Ni povas fari tion per movo reen sur la supron de nia insert funkcio kaj sekvado alia puntero variablo nomata patro. Ni tuj starigis ĝin egala al nula komence, kaj tiam ĉiu tempo ni iru tra la arbo, nin tuj fiksis la patro puntero por kongrui la nuna puntero. Ŝanĝu patro egala al nuna. Tiel, ĉiu tempo ni trairi, ni iras por certigi ke la nuna puntero gets incremented la patro puntero sekvas - nur unu nivelo pli alta ol la aktuala puntero en la arbo. Ke ĉiuj aspektas sufiĉe bone. 

Mi kredas la sola afero ke ni volas ĝustigi estas ĉi konstruos nodo reveni nula. Por akiri konstrui nodo por fakte sukcese revenos nula, ni devos modifi tiu kodo, ĉar tie, ni neniam provis certigi ke malloc revenis validan puntero. Do, se (n! = NULL), tiam - se malloc revenis validan pointer, tiam ni pravalorizi ĝin; alie, ni simple reveni kaj kiu finos reveni nula por ni. Kaj cxio aspektas sufiĉe bone. Ni certigi ĉi reale kompilas. Faru duuma arbo, kaj ho, ni havas kelkajn aĵojn okazas tie. 

Ni havas implicitan deklaron de funkcio konstrui nodo. Denove, kun ĉi tiuj tradukiloj, ni tuj komencos je la supro. Kion tio devas signifi estas ke mi vokas konstrui nodo antaux mi reale deklaris ĝin. Ni reiru al la kodo vere rapide. Rulumu malsupren, kaj vi pravis, mia insert funkcio estas deklarita super la muntaĵo nodo funkcio, sed mi provas uzi konstrui nodo ene de insert. Mi tuj iros kaj kopio - kaj tiam almeti la muntaĵo nodo funkcio vojo ĉi tien al la pinto. Tiu vojo, mi esperas ke ĝi funkcios. Ni donu tiun alian iri. Nun ĉiuj kompilas. Ĉiuj estas bona. 

Sed en ĉi tiu punkto, ni ne vere nomas nian insert funkcio. Ni nur scias, ke ĝi kompilas, do ni iros kaj metis kelkajn alvokojn in Ni faras tion en nia ĉefa funkcio. Tie, ni diris el 5, 8, kaj 2, kaj tiam ni ne telegramon ilin cxi tie. Ni faras iujn alvokojn por enigi, kaj ni ankaux uzas la saman specon de aĵoj kiujn ni uzas kiam ni faris tiujn printf alvokoj por certigi ke cxio ne get insertos konvene. Mi tuj kopii kaj alglui, kaj anstataŭ enhavas ni tuj faros insert. Kaj anstataŭ 6, 10, kaj 1, ni tuj uzos 5, 8, kaj 2. Tiu devus espereble enmeti 5, 8, kaj 2 en la arbo. Kompili. Ĉiuj estas bona. Nun ni vere kuras nia programo. 

Ĉiu revenis falsaj. Do, 5, 8, kaj 2 ne iru, kaj ĝi similas enhavas ne trovis ilin ankaŭ ne. Kio okazas? Ni malzomi. La unua problemo estis ke insert ŝajnis reveni falsa, kaj ĝi similas ke estas ĉar ni forlasis en nia reveno falsa alvoko, kaj ni neniam vere revenis vera. Ni povas difini, ke ĝis. La dua problemo estas, nun, eĉ se ni devas fari - krom tio, quit ĉi, kuri fari denove, ili ĝin kompili, tiam kuras ĝi - ni vidas ke io okazis tie. La 5, 8, kaj 2 estis ankoraŭ neniam trovis en la arbo. Do, kio okazas? 

Ni rigardu tiun en la kodo. Ni vidu se ni povas kompreni ĉi tion. Ni komencu per la patro ne esti nulaj. Ni starigis la nunan puntero egala al la radiko pointer, kaj ni iras por labori nian vojon tra la arbo. Se la nuna nodo estas ne nula, tiam ni scios, ke ni povas movi malsupren iomete. Ni metis niajn patro puntero esti egala al la nuna pointer, kontrolis la valoro - se la valoroj estas samaj ni revenis falsaj. Se la valoroj estas malpli ni translokiĝis al la dekstra; alie, ni translokiĝis al la maldekstra. Tiam ni konstruos nodo. Mi zomi iomete. Kaj tie, ni provos telegramon ĝis la valoroj esti la sama. Kio okazas? Ni vidu se eble Valgrind povas doni al ni aludo. 

Mi ŝatas uzi Valgrind nur ĉar Valgrind vere rapide kuras kaj diras al vi se estas iu memoro eraroj. Kiam ni kuras Valgrind en la kodo, kiel vi povas vidi dekstre here--Valgrind./binary_tree--and sukceson eniri. Vi vidas ke ni ne havis neniun memoro eraro, tiel ĝi aspektas kiel cxio estas bone ĝis nun. Ni ja havas iujn memoro fugoj, kiun ni konas, ĉar ni ne estas okazas liberigi iun el niaj nodoj. Ni provu kurante GDB vidi kio reale okazas. Ni faros gdb. / Binary_tree. Ĝi booted supren nur fajna. Ni starigis ripozon punkto sur insert. Ni kuras. Ĝi aspektas kiel ni neniam vere nomas insert. Ĝi aspektas kiel la problemo estis nur, ke kiam mi ŝanĝis cxi tie en ĉefa - ĉiuj el tiuj printf alvokoj de enhavas - Mi neniam vere ŝanĝiĝis tiuj nomi insert. Nun ni doni try. Ni kompili. Ĉiuj aspektas bona tie. Nun ni provu kurante ĝin, vidu kio okazas. Alright! Ĉio aspektas sufiĉe bona tie. 

La fina afero pensi estas, estas tie neniu eĝo kazoj al ĉi insert? Kaj ĝi rezultas ke, nu, la unu rando kazo kiu estas ĉiam interese pensi estas, kio okazas se via arbo estas malplena kaj vi nomas tiun insert funkcio? Ĉu ĝi funkcias? Nu, ni provu. - Binary_tree. C - La vojo ni iros por provi ĉi estas, ni tuj iru al nia ĉefa funkcio, kaj anstataŭ cableado tiuj nodoj ĉe kiel ĉi tiu, ni ĵus tuj diros el la tuta afero, kaj anstataŭ cableado ĝis la nodoj ni mem, ni povas reale nur antaŭeniri kaj forviŝi ĉion ĉi. Ni tuj faros ĉiu alvoko por enmeti. Do, ni faru - anstataŭ 5, 8, kaj 2, ni tuj enigi 7, 3, kaj 9. Kaj tiam ni ankaŭ volas enmeti 6 tiel. Savi. Quit. Faru duuma arbo. Ĉiu kompilas. Ni povas nur funkcii kiel estas kaj vidi kio okazas, sed ĝi estas ankaŭ tuj estos vere grava por certigi ke ni ne havas ajnan memoro eraroj, ekde ĉi tiu estas unu el niaj rando kazoj, ke ni scias pri. 

Ni certigas, ke ĝi funkcias bone sub Valgrind, kiuj ni faros por nur kurante Valgrind. / binary_tree. Ĝi aspektas kiel ni ja havas unu eraro de unu kunteksto - ni havas ĉi segmentación kulpo. Kio okazis? Valgrind fakte diras al ni kie ĝi estas. Malzomi iomete. Ĝi aspektas kiel ĝi okazas en nia insert funkcio, kie ni havas nevalidan legu de grandeco 4, je insert, linio 60. Ni iru tien kaj vidu kio okazas tie. Malzomi vere rapida. Mi volas certigi ke ne iras al la rando de la ekrano tiel ni povas vidi ĉion. Tiri ke en iom. Alright. Rulumu malsupren, kaj la problemo estas ĝuste ĉi tie. Kio okazas se ni preni malsupren kaj nia nuna nodo estas jam nula, nia patro nodo estas nula, do se ni rigardas supren al la plejsupro, ĉi tie - se ĉi tiu dum buklo neniam reale ekzekutas cxar nia aktuala valoro estas nula - nia radiko estas nula do nuna estas nula - tiam nia patro neniam prenas starigis al nuna aŭ validan valoron, tiel, patro ankaŭ estos nula. Ni devas memori por kontroli por ke por kiam ni atingos cxi tie, kaj ni komencu alirante la gepatroj valoro. Do, kio okazas? Nu, se la patro estas nula - if (patro == NULL) - tiam ni scias ke tie ne devas esti io en la arbo. Ni devas klopodi por enigi ĝin en la radiko. Ni povas fari tion per nur opcio la radiko egala al la nova nodo. Tiam je ĉi tiu punkto, ni ne vere volas iri tra tiuj aliaj aĵoj. Anstataŭe, ĉi tie, ni povas fari ĉu alia-se-alian, aŭ ni povus kombini ĉio ĉi tien en alia, sed tie ni simple uzu pli kaj fari ĝin tiel. Nun, ni tuj provi certigi ke nia patro ne estas nula antaux tiam efektive provas aliri liaj kampoj. Tio helpos nin eviti la segmentación kulpo. Do, ni forlasis, malzomi, kompili, kuri. 

Neniu eraroj, sed ni ankoraŭ havas faskon da memoro fugoj ĉar ni ne liberigi iun el niaj nodoj. Sed, se ni iros tien, kaj ni rigardu nian printaĵo, ni vidas ke, nu, aspektas kiel ĉiuj niaj enmetas estis revenantaj vera, kio estas bona. La enmetas estas ĉiuj veraj, kaj tiam la taŭga enhavas alvokoj estas ankaŭ vera. 

Bonan laboron! Ĝi aspektas kiel ni sukcese skribita insert. Tio estas ĉio ni havas por ĉi tiu semajno Problemo Ara Specification. Unu amuza defio pensi estas kiel vi reale iros kaj libera ĉiuj nodoj en ĉi tiu arbo. Ni povas fari ĝin nombro de malsamaj manieroj, sed mi lasos tion al vi sperti, kaj kiel amuza defio, provu kaj certiĝu ke vi povas certigi ke ĉi Valgrind raporto revenas sen eraroj kaj neniu filtras. 

Bonŝancon en ĉi tiu semajno Huffman kodigo problemo aro, kaj ni vidos vin venontsemajne! [CS50.TV]