[Powered by Google Translate] [Artikulua 7] [Less erosoa] [Nate Hardison] [Harvardeko Unibertsitateko] [Hau da CS50.] [CS50.TV] 

Ongi etorri artikulua 7. Urakanak Sandy esker, Horren ordez, aste honetan normal atal bat izatea, egiten ari gara oinez-bidez, galdera atalaren bitartez. Jarraituz batera Problema Ezarri 6 espezifikazioa noa, eta galdera guztiak igaro Galdera atal artikulua. Daude, zalantzarik izanez gero, mesedez post hauek CS50 eztabaidatzeko. 

Bale. Dezagun Hasteko. Oraintxe 3 Arazoa Set espezifikazioa nabil. Lehen hasteko zuhaitz bitar buruz hitz egiten ari gara. horiek aste honetan arazo multzo garrantzi asko aurrera Huffman Tree kodeketa. Datuak oso egitura lehen buruz hitz egin dugu CS50 array izan zen. Gogoratu array bat da elementuen sekuentzia bat berean mota guztiak - memorian gordetzen eskubidea bata bestearen ondoan. Daukat osoko array kutxak-zenbakiak-zenbaki osoko estilo hau erabiltzen dut marraz dezakete Demagun 5 daukat lehen koadroan, 7 daukat, bigarrenean, ondoren, 8, 10, eta 20 azken koadroan daukat. Gogoan izan, bi buruz array honetan gauza benetan ona dira bereziki edozein elementu sarrera konstante-denbora honetan izan dugun  array ezagutzen dugu bere indizea. Esate baterako, nahi badut array hirugarren elementu har - indizea 2 gure zero-oinarritutako indexatzeko sistema erabiliz Besterik ez literalki kalkulatzeko matematiko sinple bat egin dut, posizio hori array hop, tira han gordetzen den 8, eta onak joan naiz. 

Array honi buruz, gauza txarrak - buruz hitz egin zuen lotuta zerrendak aztertu ditugu array honetan sartzeko elementu bat sartu nahi badut, Batzuk inguruan aldatzearen egin behar dut. Esate baterako, array eskubide hau hemen ordena ordenatuko da, ordena gorakorrean antolatuta 5, ondoren, 7, 8 eta, ondoren, 10, eta, ondoren, 20 - baina kopurua 9 array honetan sartu sartu nahi dut, Elementu batzuk mugitzeko ordena espazio egin izan dut. Marraztu ahal izango dugu hemen. 5, 7 eraman behar izan dut, eta, ondoren, 8; hutsune bat sortzeko, non 9 jarri ahal izango dut, eta, ondoren, 10 eta 20 9 eskubidea. Mina baten antzeko zerbait da, izan ere, kasurik txarrenean - txertatzeko ari gara bai hasieran edo amaieran array, nola arabera aldatzearen ari gara azkenean baliteke elementu guztiak mugitzeko beharrik ari gara gaur egun array gordetzeko. 

Beraz, zer modu honen inguruan? Honen inguruan izan da gure lotutako zerrenda metodoa non joan elementu 5, 7, 8, 10, eta 20 guztiak bata bestearen ondoan memoria gordetzeko ordez - zer egin ordez dugu gorde zen lekuan gorde nahi izan dugu, mota horiek lotutako nodo zerrenda out naiz marrazten hemen, mota ad hoc. Eta gero konektatutako dugu elkarrekin erakusleak hurrengo hauek erabiliz. 5 etatik 7 erakuslea izan dezaket, 7 8 erakuslea, 8 10 erakuslea, eta, azkenik, 10-tik 20-erakuslea, eta, ondoren, 20. erakuslea null ez dagoela ezer ez ezker adieraziz. Merkataritza-off hemen dugu gaur egun kopurua 9 sartu nahi dugu gure zerrendan horrela antolatu bada, guztiak egin behar dugu sortu nodo berria 9, Wire da leku egokia seinalatu eta, ondoren, alanbre-re-8 behera seinalatu 9. Hau da, nahiko azkar, zehatz-mehatz ezagutzen dugu 9 txertatu nahi dugu non suposatuz. Baina horren truke merkataritza-off da, gaur egun galdu ditudan konstante-time sarbidea gure datu-egitura bereziki edozein elementu. Esate baterako, nahi dut laugarren elementu aurkitu lotutako zerrenda honetan, Zerrendaren hasiera-hasieratik hasi beharko dut eta lan nire nodo nodo-kontatuta bidez aurkitu dut laugarren bat arte. 

Sarbidea hobeto lotuta zerrenda baino performance - baina baita ere onurak izan dugu batzuk mantenduko Txertatze-denbora terminoak lotuta zerrenda - bitarra zuhaitz bat da, apur bat memoria gehiago erabili behar du. Hain zuzen ere, horren ordez,, zuhaitz bitar nodo bakar bat erakuslea izatea - lotutako zerrenda bezalako nodo ez bigarren erakuslea zuhaitz bitar nodo bat gehitzeko goaz. Baino erakuslea bat izatea hurrengo elementu ezker haur eta eskuineko haur baten erakuslea izan dugu. 

Dezagun irudi bat marraztuko zer esan benetan itxura ikusteko. Berriz ere, kutxak eta geziak horiek erabili dut. Zuhaitz bitarra nodo hasiko da kutxa sinple bat besterik ez. Balioa espazio bat izan da, eta gero ere Umearen ezkerreko eta eskuineko haurraren espazio bat izan behar da. Etiketatuko hemen noa. Ezkerraldean seme-alaba izan gara, eta, ondoren, eskuineko seme-alaba izan dugu. Asko daude hau egiteko modu desberdinak. Batzuetan espazioa eta erosotasuna, Actually dut marraztu dut hemen behean bezala egiten non goialdean balioa izan dut, eta, ondoren, eskuineko beheko-eskuineko haur, eta ezkerreko beheko-ezkerreko haur. Goiko diagrama honetan atzera eginez, balioa dugu, oso goian, ondoren, ezkerreko eta seme-alaben erakuslea dugu, eta, ondoren, seme-alaben eskuineko erakuslea dugu. 

Arazoa Set espezifikazioa, 7 balioa du nodo batek marrazten buruz hitz egiten dugu, eta, ondoren, seme-alaben ezkerreko erakuslea null da, eta seme-alaben eskubidea erakuslea null da. Bai idatzi ahal izango dugu hiriburua NULL espazioa bai ezkerreko haur eta eskuineko seme-alaba, edo diagonal barrarik marraztuko dela koadroen bitartez null adierazteko. Besterik ez delako hori errazagoa egin dut. Hemen ikusten duzun oso erraza binary zuhaitz nodo diagramming bi modu non balioa 7 eta null seme-erakusle dugu. 

Gure zehaztapen zerrendak lotuta buruz hitz egiten du bigarren zatia - gogoan, izan besterik ez dugu eduki elementu oso lehen zerrenda batean zerrenda osoa gogoratzeko eta, era berean, zuhaitz bitar bat, besterik ez dugu eduki bat erakuslea zuhaitz , datu egitura osoa gaineko kontrola mantentzeko. Erroko nodoa izeneko zuhaitza zuhaitzaren elementu berezi hori. Adibidez, nodo bat bada - 7 balioa duen nodoa ezkerreko eta eskuineko seme-alaben null erakusleak gure zuhaitz balio bakarra izan ziren, ondoren, hauxe da gure erroko nodoa izango litzateke. Gure zuhaitz hasieran oso da. Pixka bat ikusi ahal izango dugu argiago hasten gara gure zuhaitz nodo gehiago gehituz behin. Tira me orri berri bat. 

Orain duen erro 7 zuhaitz bat marraztu dugu, eta 3 seme-alaba ezkerrera, eta eskuineko haurraren barruan 9 barruan. Berriz ere, hau da, nahiko sinplea da. Dugu got 7, marraztu 3 nodoa, 9 nodo eta ezkerreko erakuslea 7 seme-alaben 3 nodo duten seinalatu ezartzeko noa, eta 7 9 duten nodo nodo seme-alaben eskuineko erakuslea. Orain, 3 eta 9 geroztik ez dute seme-alabak edozein beren seme-alaba erakusleak guztiak ezarri null izango dugu. Hemen, gure zuhaitz sustraia nodo kopurua 7 duten dagokio. Horretan dugun guztia ikusi ahal izango duzu root nodo horretan erakuslea bada, gure zuhaitz ibiltzeko aukera izango dugu, orduan eta bi seme-alaba nodo sartzeko bai 3 eta 9. No behar zuhaitza nodo bakar behin erakusleak mantentzeko. Bale. Nodoa beste diagrama hau gehitzeko goaz. 6 duten nodo bat gehitzeko ari gara, eta hau gehitzeko nodo 3 duten eskubidea seme-alaba gisa ari dugu. Horretarako, 3-nodo null erakuslea ezabatu noa eta Wire nodo 6 duten seinalatu. Bale. 

Puntu honetan, dezagun terminologia pixka bat baino gehiago joan. Hasteko, arrazoi hori deitzen da, bereziki, zuhaitz bitar bat da, bi seme-alaba erakusleak. Badira beste seme-alaba gehiago izan erakusleak zuhaitz mota. Hain zuzen ere, 'saiatu' Arazoa Set 5 egin duzu. Saiatu egiten dela nabarituko duzu, 27 seme-alabak hainbat erakusle izan - English alfabetoa 26 letrak bakoitzeko bat, eta, ondoren, apostrophe, 27an - beraz, zuhaitz mota bat antzekoa da. Baina, hemen, bere bitar geroztik, besterik ez dugu bi seme-alaba erakusleak. 

Hitz egiten dugun hau erroko nodoa gain, dugu, halaber, epe horren inguruan 'seme-alaba' bota Zer esan nahi du nodo nodo beste seme-alaba bat izatea esan nahi du? Esan nahi du literalki nodo umea nodoa beste ume bat da beste nodo hori bada bere seme-alaba nodo hori seinalatu erakusle bat. Hormigoizko gehiago terminoak jarri, 3 azpimarratu nahi izanez gero 7-erakusleak ume bat, eta 3 seme-alaba 7. Izan dugu irudikatu zer diren 7 seme-alabak izanez gero - ondo, 7 erakuslea 3 eta 9 erakuslea bat ikusiko dugu, beraz, 9 eta 3, 7 seme-alabak dira. Bederatzi ez du seme-alaba, bere seme-alaba erakusle dira null delako, eta 3 seme-alabaren bat, 6 ditu. Sei ere ez du seme-alabak bere erakusleak biak null, marrazteko oraintxe dugu delako. 

Horrez gain, gurasoek jakin baten nodo buruz ere hitz egin dugu, eta hau da, espero duzun bezala, deskribapen hau umearen atzealdean. Ordez bi duzun gizakiak espero dezake - nodo bakoitzak guraso bakarra du. Esate baterako, 3 gurasoaren 7. 9-gurasoa ere bada, 7, eta 6 gurasoaren 3. Ez da askoz ere. Era berean, termino, aiton-amonen eta biloben buruz hitz egin dugu, eta, oro har arbasoen buruz hitz egiten dugu eta nodo jakin baten ondorengoak. Nodo bat - arbaso edo arbasoen, baizik eta, nodo bat - erro bidea nodo hori gezurra nodo guztiak. Esate baterako, naiz nodo 6 begiratuz gero, gero, arbasoen bai 3 eta 7 izango dira. 9 arbasoak dira, adibidez, - naiz nodo 9 begiratuz gero - gero, arbaso 9 7 besterik ez da. Eta ondorengoak dira hain zuzen ere alderantziz. Nahi dut 7 ondorengoak begiratuz gero, azpian nodo guztiak begiratu behar dut. Beraz, 3, 9, eta 6 guztiak 7 ondorengoak gisa daukat. 

Final epe buruz hitz egingo dugun anaia bat izatearen ideia da. Anai-arrebak batera familiaren baldintza hauek mota zuhaitzaren maila berean dauden nodoak dira. Beraz, 3 eta 9 anai-arrebak dira zuhaitzean maila berean daudelako. Biek guraso berdina dute, 7. 6 ez du anai-arrebak 9 seme-alabak izan ez delako edozein. Eta 7 anai-arrebak ez da gure zuhaitz sustraia delako edozein eta ez da soilik inoiz 1 root. 7 anai-arrebak izatea eta bertan 7 gainetik nodo bat izan beharko lukete. 7 guraso, kasu honetan 7 ez dira zuhaitzaren root izan beharko lukete. Ondoren, gurasoaren 7 berria izango litzateke, halaber, seme-alaba bat izatea, eta seme-alabak gero, 7 anai-arreba izan. 

Bale. On mugimenduan. Gure binary zuhaitz eztabaida hasi ginen, hitz egin dugu nola erabili izan dugu irabazteko bi array eta zerrendak lotutako abantaila bat. Eta horretarako goaz modu honetan ordena jabetza da. Bitarra zuhaitz bat agindu hori esaten dugu, espezifikazioaren arabera, gure zuhaitzean nodo bakoitzean izanez gero, bere ezker aldean ondorengoak guztiak - ezkerreko haur eta ezkerretik haurraren ondorengoak guztiak balio txikiagoan izan, eta eskuineko nodo guztiak eskuineko haur eta eskuineko haur azpikoen guztiak izan nodo begira ari gara uneko nodoaren balioa baino handiagoa. Just sinpletasunagatik, ez dagoela ez dira gure zuhaitzean nodo bikoiztuak edozein bere gain hartzen dugu. Esate baterako, zuhaitz hau ez da ari gara kasuan aurre egiteko 7 balioa dugu erro non  eta, ondoren, izan ere, balioa 7 zuhaitza beste leku batean. Kasu honetan, nabarituko zuhaitz hori da, hain zuzen ere, agindu duzu. 7 balioa ditugu erro at. 7 ezkerreko Everything - desegin I marka txiki horiek guztiak galtzen hemen. 7 ezkerreko guztia - 3 eta 6 - balio horiek dira, bai 7 baino txikiagoa da, eta eskuinera dena besterik ez da hau 9 - 7 baino handiagoa da. 

Hau ez da balio hauek bakarrik agindu zuhaitza, baina dezagun marrazteko gehiago horietako batzuk. Bide hori egin ahal izango da, benetan sorta oso bat. Azkarra bat besterik ez erabiltzeko gauza sinpleak non mantentzeko noa baizik eta marrazketa osoa kutxak-eta-geziak baino Besterik ez naiz zenbakiak marraztu eta geziak lotu gehitu du. Hasteko, besterik ez dugu gure jatorrizko zuhaitz idatzi berriro 7 izan genuen, eta, ondoren, 3, eta, ondoren, 3 adierazi back 6 eskubidea, eta 7 izan zen seme-alabak izateko eskubidea 9. Bale. Zer da Zuhaitz hau ezin izan dugu idazteko beste modu bat da? Horren ordez 3 izatea ezker 7 seme-alaba izan, ere izan dugu, 6, 7 seme-alaba ezker, eta, ondoren, 3 6 seme-alaba ezker. Lukeen itxura Zuhaitz hau hemen non dut 7. gero 6, gero, 3 eta 9 eskubidea. Era berean, ez dugu erroko nodoa 7. 6 ere izan dugu gure erroko nodoa. Zer izango litzateke itxura? Ari gara agindu jabetza horri eustea nahi izanez gero, 6 ezkerraldean dena baino txikiagoa izan behar du. Aukera bakarra da, eta hori 3. Baina gero, 6 eskuineko umearen gisa, bi aukera izango ditugu. Lehenik eta behin, 7 izan dira eta, ondoren, 9 edo marraztu izan dugu, ez naiz hemen egin bezala - non 9 ditugu 6 eskuin haur bezala, eta, ondoren, 9 ezker haurraren 7. 

Orain, berriz, 7 eta 6 ez dira erro balio posible bakarra. 3 erro at ere izan dugu. Zer gertatzen da 3 erro bada? Hemen, gauzak pixka bat interesgarria. Hiru ez du balio duen edozein baino gutxiago dira, beraz, zuhaitzean dagoen ezker alboko osoa besterik ez da nulua izango. Ez da ezer izan, han joan da. Eskuinean, gauzak zerrenda izan dugu, ordena gorakorrean. 3, gero 6, gero 7 eta, ondoren, 9 izan izan dugu. Edo, 3 egin ahal izan genuen, gero 6, gero 9, ondoren, 7. Edo, 3 egin ahal izan genuen eta, ondoren, 7 eta, ondoren, 6 eta, ondoren, 9. Edo, 3, 7 - Egia esan, ez, ezin dugu 7 gehiago. Hori da gure gauza bat dago. 9 egin ahal izango dugu, eta, ondoren, 9 6 egin ahal izango dugu eta, ondoren, 7. Edo, 3 egin ahal izango dugu eta, ondoren, 9 eta, ondoren, 7, eta, ondoren, 6. 

Gauza bat da hemen, zure atentzioa zuhaitz horiek pixka bat arraro begira daude. Hain zuzen ere, eskuineko aldean 4 zuhaitz begiratzen badugu Zirkulu dut, hemen zuhaitz horiek itxura ia zehazki lotuta zerrenda bat bezala. Nodo bakoitzak seme-alaba bakarra du, eta, beraz, ez dugu ikusten dugun honetan, zuhaitz-egitura, adibidez,  hemen beheko ezkerreko zuhaitz bakarti. Zuhaitz hauek benetan izeneko endekapen binary zuhaitzak, eta gehiago horiei buruz hitz egin dugu etorkizunean batez ere, joan beste informatika ikastaroak hartzeko. Zuhaitz hauek endekapen dira. Oraindik ez dira oso erabilgarria da, hain zuzen ere, izan ere, egitura hau erabaki bera  aldiz lotuta zerrenda baten antzekoa bilatzeko. Ez dugu aprobetxatu aparteko memoria - extra erakuslea honetan baita gure egitura modu honetan gaiztoa izatea. Baino gehiago joan eta marrazteko duten bitar zuhaitzak erro 9, litzateke dugun kasuan behin betiko da, ordez gara, puntu honetan, epe hau beste pixka bat hitz egingo hori erabili dugu, zuhaitzak, altuera deitzen den buruz hitz egiten denean. 

Zuhaitz baten altuera erro gehien urrutiko nodo distantzia da, edo, hobeto esanda, Hops kopurua egin ahal izateko izango litzateke erro hasiko da, eta, ondoren, azkenean zuhaitz gehien urrutiko nodo. Zuhaitz horietako batzuk marrazten ditudan dugu hemen, begiratuz gero Zuhaitz hau hartuko dugu goiko ezkerreko izkinan eta dugun hasten gara 3, ondoren, 1 hop 6, 7 bigarren hop egin behar dugu, eta hirugarren hop 9. Beraz, zuhaitz honen altuera 3. Zuhaitz berde honekin jasotako beste ariketa bera egin ahal izango dugu, eta zuhaitz horien guztien altuera dela ere, hain zuzen ere 3 ikusiko dugu. Zerk endekapen parte - beren altuera besterik ez da zuhaitz osoa nodo kopurua baino bat gutxiago. Zuhaitz hau beste gorriz encircled, beste alde batetik begiratzen badiogu, gehien urrutiko hosto nodoak direla ikusiko dugu 6 eta 9 - uzten du, eta seme-alabak ez duten nodo. Beraz, ahal izateko, erroko nodoa bai 6 edo 9 7 hop bat egin dugu, eta, ondoren, 9 bigarren hop, eta, era berean,, 7 bakarrik hop bigarren bat 6. Beraz, Zuhaitz hau hemen altuera bakarrik 2. Atzera egin dezakezu, eta horretarako, beste zuhaitz guztiak aurrez dugun eztabaidatu 7 eta 6 hasita, aurkitu eta, zuhaitz horien guztien altuera dela ere 2 duzu. 

Arrazoia izan dugu buruz hitz egitea agindu bitar zuhaitz eta zergatik cool daudela da, horien bitartez bilatu ordenatuko array bat baino gehiago bilatzeko modu oso antzekoa. Hau da, non hitz egiten dugu lookup hobetutako denbora hori lortzeko loturiko simple zerrenda baino gehiago. Lotuta zerrenda - elementu jakin bat aurkitu nahi duzu bada - Oraindik onena bilaketa lineala nolabaiteko non hasten hop zerrenda bat eta bat-batean, hasieran bat nodo nodo bat - zerrenda osoa aurkituko duzun arte, edozein dela ere bilatzen ari zaren bidez. , Berriz, zuhaitz bitar bat hau nice formatuan gordetzen bada, benetan lor dezakezu bilaketa bitar joan non eta zatiketak konkistatzeko eta urrats bakoitzaren zuhaitz dagokion erdia bidez bilaketa. Ikus dezagun nola obrak. 

Badugu - berriro ere, gure jatorrizko zuhaitz 7, hasiko dugu, 3 dugu ezkerretik, 9 eskubidea, eta 3 azpian 6 dugu. Zuhaitz hau kopurua 6 bilatu nahi dugu bada, erroko hasteko genuke. Balioa, esan 6 bilatzen ari gara konparatu nahi dugu, ari gara gaur egun, 7 bilatzen nodo gordetako balioa, aurkituko 6 dela hain zuzen ere, 7 baino gutxiago, beraz, ezkerrera mugitu genuke. Izan ezkero 6 balioa 7 baino handiagoa, ordez genuke eskuinera eraman. Ezagutzen geroztik dugu gure agindu zuhaitz bitar egitura dela - baloreak 7 baino gutxiago 7 ezkerreko gordetzen, ez da beharrezkoa ere traba zuhaitzaren eskuinaldean bidez bilatzen da. Behin ezkerrera mugitu gara eta 3 duten nodo gara orain, konparazio hori bera egin ahal izango dugu, berriz, 3 eta 6 alderatu dugu. Balioa bilatzen ari gara - 3 baino handiagoa da, eta 6 bitartean aurkituko dugu 3 nodo duten eskuinaldean joan gaitezke. Ezkerraldean ez da hemen, beraz, ez ikusi egiten zaie genezake hori. Baina bakarrik ezagutzen dugu delako zuhaitza bera bilatzen ari gara, ikusi eta zuhaitza ez du seme-alabak ahal izango dugu. 

Gainera, nahiko erraz bilatzeko 6 Zuhaitz hau ari badugu egiten geure buruari gizakiak, baina dezagun prozesu hau jarraitu mekanikoki ordenagailu bat bezala egingo algoritmoa benetan ulertzeko. Une honetan, gaur egun ari gara nodo dituen 6 begira, eta 6 balioa bilatzen ari gara, horregatik, hain zuzen ere, aurkitu dugu nodo egokia. 6 balioa gure zuhaitz aurkitu ditugu, eta gure bilaketa gelditu ahal izango dugu. Une honetan, zer ari den gertatzen arabera, esan dezakegu, bai, aurkitu dugu 6 balioa badago, gure zuhaitzean. Edo, ari gara, zerbait, nodo bat sartu edo plangintza, hori egin ahal izango dugu puntu honetan. 

Egin dezagun pare bat gehiago bilaketak nola lan hau ikusteko. Dezagun zer gertatzen den ginen 10 balioa eta saiatu begiratu begiratu. Ginen 10 balioa bilatuko bada, erroko genuke. 10 7 baino handiagoa dela genuke, beraz, eskuinera mugitu genuke. 9 genuke eta 9 konparatu 10 eta 9 hori da, hain zuzen ere 10 baino gutxiago. Beraz, berriro ere, saiatu eskuinera eraman genuke. Baina, puntu honetan, nabarituko null nodo dugun Oraindik genuke. Ez dago ezer han. Ez dago ezer, non 10 izan behar du. Hau da, non porrot berri eman ahal izango dugu, hain zuzen ere ez dela ez zuhaitza 10. Eta, azkenik, dezagun kasu non bilatuko 1 zuhaitza saiatzen ari gara. Hau da, zer gertatzen den begiratzen dugu, bada 10,, eskuinera joan beharrean izan ezik antzekoa da, ezkerrera joan goaz. 7, hasiko gara, eta ikus 1 7 baino txikiagoa dela, eta, beraz, ezkerrera mugitu gara. 3 eta 1 3 baino txikiagoa da, beraz, berriro ezkerrera mugitu saiatu gara. Puntu honetan nodo nulua izan dugu, eta, beraz, berriro ere porrota berri eman ahal izango dugu. 

Ez gehiago ikasteko zuhaitz bitar buruz nahi baduzu, badira, haiekin egin ditzakezun arazo txiki fun sorta osoa. Marrazkia gomendatzen I praktikatzeko diagrama horiek bat-batean, eta hainbat urrats guztietan barrena jarraituz, super-erabilgarri delako etorri Huffman kodeketa arazo multzo ez denean bakarrik egiten ari zarenean baina ere ikastaro etorkizuneko - besterik gabe, nola marraztu datu-egitura horiek, eta arazoak bidez uste ikasteko luma eta paper edo, kasu honetan, iPad eta arkatzarekin. 

Nahiz eta puntu honetan, mugitzeko kodeketa praktika batzuk egin ditugu eta benetan binary zuhaitz hauekin jolastu eta ikusi. Atzera aldatzeko nire ordenagailuan zehar noa. Atalean, CS50 Run edo CS50 Espazioak ordez zati honetan, -Tresna erabili dut. 

Arazoa Set zehaztapen batera jarraituz, Tresnara ireki suposatzen dut naiz ikusten dut, joan nire Dropbox karpeta, artikulua 7 izeneko karpeta bat sortu, eta, ondoren, sortu binary_tree.c izeneko fitxategi bat. Hemen goaz. Dut-tresnaren dagoeneko irekia dago. Tira sortu terminal bat noa. Dropbox karpeta joan noa, izeneko section7 direktorioa ikusi eta erabat hutsik da. Orain en ireki binary_tree.c noa. Bale. Hemen gara - fitxategi hutsa. 

Dezagun itzuli zehaztapena. Zehaztapen eskatzen definizio mota berri bat sortzeko int balio duten zuhaitz bitar nodo balioak soilik marraztu dugu, gure aurretik diagramming atsegin dute. Boilerplate hau typedef egin ditudan dugu hemen erabili dugu Arazoa Set 5 aitortu behar duzula speller konkistatu programa hash taula modu zenuen bada. Ere aitortu behar duzu azken astean ataleko non hitz zerrendak lotuta dugu. Lortu dugu eta egitura nodo bat typedef hau, eta struct nodo hau eta egitura nodo izena aldez aurretik eman dugu Ondoren, beraz, ezin dugu ikus eta egitura nodo erakusle izan nahi dugu geroztik gure struct zati gisa, baina gero dugu encircled edo, hobeto esanda, artean - typedef batean beraz, geroago kodea, egitura hau dugu erreferentzia eta egitura nodo baten ordez nodo gisa. 

Banaka-zerrenda lotutako definizio oso antzekoa ikusi dugu azken astean izango da. Horretarako, dezagun idazten boilerplate hasteko. Osoko balioa bat izan dugula ezagutzen dugu, beraz, balio int dugu jarri, eta, ondoren, bakarrarekin erakuslea izatea hurrengo elementu ordez - , banaka-zerrendak lotutako genuen ezkerreko eta eskuineko seme-erakusle izan nahi dugu. Hori da ere - pretty simple struct nodo * ezker seme-alaba; eta egiturari nodo * eskubidea seme-alaba; Cool. Pretty good Irteeran itxura. Dezagun itzuli zehaztapena. 

Orain nodo * aldagai global bat zuhaitz baten erro aldarrikatu behar dugu. Global honetan bezala lehen erakusleak egin dugu gure zerrenda ere lotuta global goaz. Hau izan zen beraz, idazten dugun funtzioak ez dugu root honen inguruan pasatzen mantentzeko ez baduzu nahi duten funtzio hauek idazteko errekurtsiboki ikusi dugu, nahiz eta, hobea izan daiteke ere ez pasatzeko inguruan global gisa Lehenik eta behin eta horren ordez, hasieratu lokalki zure eginkizun nagusia. Baina, ez dugu globalki abiarazteko. Berriz ere, espazio pare bat eman dugu, eta * root nodo bat deklaratzen dut. Just ziurtatu ez ez dut utzi hau uninitialized egiteko, berdina noa null. Orain, funtzio nagusiak idatzi benetan azkar dugu hemen int main (int argc, eraikiak char * argv []) - eta nire argv array geratuko eraikiak hasteko besterik ez dut ezagutzen dut argumentuak duten argumentuak ziurrenik ez dut aldatu nahi dira. Nahi ditut aldatu beharko dut horietako kopiak egiten. Hau kode asko duzu. Isuna, bai modu da. Utzi - ezikusia eraikiak Nahi izanez gero, isuna da. Normalean jarri dut soilik gogorarazten dut  ziurrenik hori ez dut nahi argumentuak horiek aldatzeko. 

Beti bezala, hau da, bueltan 0 nagusiaren amaieran line noa. Hemen, nire erroko nodoa hasieratu egingo dut. Nabarmentzen oraintxe bezala, erakuslea dut ezartzeko null beraz, ez da ezer seinalatuz. Benetan hasi nodo eraikitzeko, Lehenik memoria esleitu. Horretarako zeure malloc erabiliz memoria eginez noa. Root malloc emaitza berdina ezartzeko noa, eta nodo baten tamaina kalkulatzeko sizeof operadorea erabili dut. Arrazoia erabiltzen dut sizeof nodo aurrean, esan, malloc (4 + 4 +4) edo malloc 12 - antzeko zerbait egiten ari nahi dut nire kodea ahalik eta bateragarria izan delako. C fitxategia hartzeko gai izan nahi dut, konpilatu tresnaren eta, ondoren, konpilatu nire Mac on 64-bit edo erabat desberdina arkitektura - eta hori guztia berak lan egin nahi dut. 

Dut hipotesi eginez gero, aldagai tamaina buruz int edo erakuslea tamaina tamaina - ondoren ere dut hipotesi arkitektura mota buruz nire kodea ongi konpilatu exekutatutakoan. Beti erabili sizeof eskuz struct eremu summing aurrean. Beste arrazoirik ez dagoela ere izan liteke betegarria konpilatzailea struct sartu jartzen. Nahiz eta banakako eremu summing ez da zerbait normalean egin nahi duzula, beraz, lerro hori ezabatu. Orain, benetan erroko nodoa abiarazi, Bere eremu ezberdinetako bakoitzaren balioak entxufatu izan dut. Esate baterako, balioa 7 hasieratu nahi dut ezagutzen dut, eta, orain, ezker haurraren null noa eta eskuineko seme null ere. Great! Zehaztutako zati bat egin dugu. 

Espezifikazioak page 3 behean eskatzen me hiru nodoak sortzeko - 3, 6 duten, eta bat duten 9 - eta, ondoren, Wire horiek sortu, beraz, itxura hain zuzen ere gure Zuhaitz-diagraman bezala da dugun buruz hitz egiten, aldez aurretik. Egin dezagun nahiko azkar hemen. Benetan azkar ikusten duzu naiz duten I kodea bikoiztuak sorta bat idazten hasteko. Nodo * sortu dut eta hiru dei noa. Malloc (sizeof (nodo)) berdintasuna ezartzeko noa. Hiru-> balioa ezartzean = 3 noa. Hiru -> left_child = NULL; hiru -> eskuineko _child = NULL; baita. Hori nahiko itxura root hasieratzeko antzekoa da, eta hori da zehazki zer I 6 eta 9 hasieratzean baita egin behar dut. Hori benetan azkar hemen egin dut, benetan, apur bat kopiatu eta itsatsi egin dut, eta ziurtatu dut ongi.  Orain, got dut da kopiatu eta aurrera eta 6 berdina ezarri. Hori awhile hartzen da, eta ez da super-eraginkorrak ikus dezakezu. Apur bat besterik ez, funtzio bat egingo Gurekin idatzi dugu. Hau ordezkatu nahi dut, 9, ordezkatu eta 6. 

Orain lortu dugu gure nodoak sortu eta hasieratu. Lortu dugu gure root ezarri 7 berdinak, edo 7 balioa duten, gure nodo 3 duten, gure nodo 6 duten, eta gure nodo 9 duten. Une honetan, guztiok egin behar dugu alanbre guztia sortu da. Erakusleak guztiak hasieratu dut null arrazoia da, besterik gabe, beraz, ziurtatu egiten dut. Nik ez dut hor erakusleak uninitialized edozein istripu. Eta, gainera, geroztik, puntu honetan, besterik ez dut benetan konektatzeko nodoak bata bestearen batzuk direla ari benetan konektatuta ez daukat bidez joan eta egin Ziur nuluak guztiak ez dira leku egokiak. 

Erro hasita, ezagutzen dut erro ezker seme-alabak 3. Ezagutzen dut root eskubidea seme-alabak 9. Horren ondoren, beste seme-alaba bakarrik utzi dut, kezkatu 3 eskubidea seme-alaba da, hau da, 6. Une honetan, itxura nahiko ona. Lerro hauen batzuk ezabatu egin dugu. Orain guztia itxura nahiko ona da. Dezagun gure zehaztapen itzuli eta ikusi zer hurrengoa egin behar dugu. 

Une honetan, funtzio bat deitu 'dauka' idatzi dugu dauzka boolearra (int balioa) 'prototipoa. Eta honek funtzioa da egia itzuli  Zuhaitzaren adierazi gure root aldagai global  funtzioa eta false bestela pasa balioa dauka. Dezagun aurrera eta ez dela. Zehazki lookup iPad duela pixka bat eskuz egin genuen bezala izango da. Let mapan handiago atzera pixka bat eta joan gora. Funtzio hau gure funtzio nagusia gainean jarri behar dugu beraz, ez dugu izan prototyping inolako egin. Beraz, boolearra badu (int balioa). Bertan dugu. Ez dago gure boilerplate adierazpena. Just ziurtatu hori konpilatzen egiteko, Aurretik joan eta besterik ez da ezarri berdinak false itzuli egingo naiz. Oraintxe bertan, funtzio hau ez du ezer egiten, eta beti berri bila ari garela balioa ez da zuhaitza. 

Une honetan, ideia ona izango da seguru asko idatzi dugu geroztik kodea sorta osoa, eta ez dugu, nahiz eta saiatu probatzen oraindik Ziurtatu guztiak biltzen egiteko. Egin dugula ziur hori benetan konpilatu egiteko gauza pare bat daude. Lehenik eta behin, ikusi dugu bada ez dugu oraindik sartutako edozein liburutegi edozein funtzio erabiliz. Funtzioak erabili dugu, orain arte, malloc dira, eta, ondoren, dugu mota honetako erabiliz - 'bool' izeneko estandarrak mota hau boolearra goiburu fitxategi estandarra. Boolearra mota bool.h estandarra, besteak beste, nahi dugu, behin betiko eta nahi dugu, liburutegi estandarra estandarra lib.h # malloc, eta doakoa da, eta hori guztia, besteak beste. Beraz, mapan handiago, irten dugu. Dezagun saiatu eta ziurtatu hori benetan egin konpilatzerakoan. Ez dela ikusten dugu, beraz, Oraindik eskuineko pista dugu. 

Dezagun ireki binary_tree.c berriro. Biltzen. Goazen behera eta ziurtatu deiak batzuk sartu dugun gure Contiene funtzioa zaitez guztiak ongi eta ona izan dadin. Esate baterako, bilaketak genuen gure zuhaitz lehenago, balio bilatzeko, 6, 10, eta 1 saiatu ginen, eta 6 zuhaitza zen bazekien dugu, 10 zuhaitza, ez zen eta 1 ez zen zuhaitza bai. Dezagun modu gisa erabili deiak lagin horiek irudikatu nahi ala ez lan gure Contiene funtzioa. Horretarako, printf funtzioa erabili dut, eta dei bat dauka emaitza inprimatu goaz. Kate bat jarri dut "(% d) = duelako  plug ari gara balioa bilatzen ari garela, =% s \ n ", eta erabiltzen duten gure formatu katea. Literalki inprimatu pantailan besterik ari gara ikusteko zer funtzio-dei bat itxura. Hau ez da benetan funtzio deia.  Hau da, funtzio-dei bat itxura diseinatutako kate bat. 

Orain, balioak entxufatu dugu. Dauka saiatzeko 6 goaz, eta orduan zer da hemen egin behar dugu, erabili, hirutarra adibidez operadorea. Ikus dezagun dauka 6 -, beraz, gaur egun jasotako dut 6 eta badu 6, egia da, ari garela katea% s formatu karaktere bidaltzeko katea "benetako" izango da. Dezagun pixka bat baino gehiago joan. Bestela, kate "false" bidaltzeko 6 itzultzen faltsua badu nahi dugu. Hau da, apur bat Goofy-begira, baina baita agian I ilustratzeko irudikatu dut hirutarra adibidez operadorea zer ikusi dugu, ez baita awhile for itxura. Nice, handy modu irudikatu gure Contiene funtzioa lan bada izango da. Atzera mugitzeko ezkerreko noa, eta kopiatu eta itsatsi lerro hau hainbat aldiz noa. Balio horietako batzuk aldatu ditu inguruan, beraz, hau da, 1 izan behar du, eta hori 10 izango da. 

Puntu honetan lortu dugu polit bat Contiene funtzioa. Probak batzuk lortu dugu, eta hau lan guztiak galtzen dugu. Puntu honetan zenbait gehiago kodea idatzi dugu. Denbora irten eta ziurtatu dena oraindik biltzen. Irten, eta now dezagun binary zuhaitz egiten saiatu berriro. Beno, dugu got bezala errore bat dirudi, eta lortu dugu hau esplizituki liburutegiko funtzioa geratuko printf. Behar dugu joan eta # standardio.h besteak beste, itxura. Eta hori, dena behar konpilatu. Guztiak onak gara. Orain dezagun saiatu bitar zuhaitz martxan ikusi eta zer gertatzen den. Hemen, gaude. / Binary_tree eta, espero bezala vemos dugu ez delako inplementatu dauka oraindik, edo, hobeto esanda, besterik ez dugu bueltan faltsua jarri besterik ez dela faltsua itzuli horiek guztiak ikusten dugu, beraz, hori gehienetan nahiko ondo ari da lanean. 

Dezagun atzera jo eta benetan ezartzeko puntu honetan dauka. Behera korritzeko, Handiagotzeko noa, eta - gogoan, erabiltzen dugun algoritmoa erroko nodoa hasi ginen eta, ondoren, aurkitzen dugun nodo bakoitzean, konparazio bat egiten dugu, eta konparaketa horretan oinarritzen da ezker Umearen edo haurraren eskuineko bai dugu. Binary bilaketa kodea duten lehenago idatzi dugu, epe oso antzeko itxura du. Noiz hasiko gara, uneko nodoaren eduki nahi dugun badakigu ari gara, eta uneko nodoaren erroko nodoa hasieratu. Eta, orain, zuhaitz bidez jarraitzeko goaz, eta gogoratu, gure gelditu baldintza -  Adibidez bidez benetan eskuz aritu gara lanean - nodo nulua topo egin dugu. ez begiratu null seme-alaba gara, baizik eta nodo bat dugu mugitu zuhaitza eta aurkitutako null nodo Oraindik dugu. Batetik bestera joateko ari dugu, orain arte ez da berdina null. Eta zer egin behar dugu? Probatzen ari gara bada (orain -> balioa == balioa), ondoren, benetan aurkitu ditudan nodo bila ari garela badakigu. Hortaz, hona hemen, itzultzeko egia esan daiteke. Bestela, ala ez, balioa balioa baino gutxiago ikusi nahi dugu. Uneko nodoaren balioa balioa baino txikiagoa bada bilatzen ari gara, eskuinera eraman dugu. Beraz, orain = orain -> right_child; eta bestela, ezkerrera eraman dugu. orain = orain -> left_child;. Pretty simple. 

Seguruenik ezagutzen duzu loop itxura oso antzekoa binary bilaketa terminoa lehenago, eta gero izan ezik, baxua, erdialdean, eta goi ginen aurre. Hemen, uneko balioa begiratu besterik ez dugu, beraz, atsegina eta erraza da. Dezagun ziurtatu kode hau da lan. Lehenik eta behin, ziurtatu du biltzen. Ez bezala dirudi. Dezagun saiatu exekutatzen ari da. Eta, hain zuzen ere, bistaratzen da espero dugun guztia. 6 aurkitzen da zuhaitz, ez du aurkituko 10 10 zuhaitza da ez delako, eta ez du aurkitu 1 bai 1 zuhaitza ez da ere. Cool stuff. 

Bale. Dezagun gure zehaztapen itzuli eta ikusi zer ekarriko duen etorkizunean. Orain, gure zuhaitz batzuk gehiago nodoak gehitzeko nahi du. 5, 2 eta 8 gehitu da, eta ziurtatu gure dituela kodea nahi du oraindik ere lan egiten du, espero bezala. Goazen hori egiteko. Puntu honetan, baizik eta hori gogaikarriak kopia eta itsatsi berriro egiteko baino, dezagun funtzio bat idatzi benetan nodo bat sortu. Joan gara behera bada modu nagusia, izan dugu dugun hau egiten ikusiko dugu oso antzekoa da, eta behin eta berriz nodo bat sortu nahi dugu aldi bakoitzean kodea. 

Dezagun funtzio bat izango dela benetan nodo bat eraiki Gurekin eta itzultzeko idatzi. Deitu du build_node noa. Balio jakin bat nodo bat eraiki dut. Hemen Txikiagotu. Lehenik eta behin, ez dut benetan zeure buruzko nodo espazioa sortu. Beraz, nodoak * n = malloc (sizeof (nodo)); n -> balioa = balioa; eta ondoren, hemen, besterik ez dut eremu guztiak hasieratu balio egokiak izan. Eta amaieran, gure nodo itzuli dugu. Bale. Gauza bat kontuan izan da funtzio hori eskubidea hemen erakuslea memoria que ha sido zeure-esleituriko itzuli egingo da. Zer da honi buruz nice nodo hau da gaur egun aldarrikatu zeure gainean deklaratu dugulako pila dugu ez genuke hau atsegin dute funtzio hau egin ahal izango duzu. Memoria Hori litzateke esparrua eta baliogabea izango litzateke, saiatu ginen beranduago sartzeko. Zeure-esleituriko memoria denez deklaratzen ari gara, askatzeaz geroago zaindu beharko dugu gure programa ez edozein Leak memoria. Hori izan dugu, beste guztia kodea punting sinpletasun garai hartan mesedetan, baina inoiz idatzi honen itxura duen funtzioa non duzun got batzuk deitu malloc edo idazketa barruan ziur jarri duzula comment nolabaiteko hemen dioen egin nahi baduzu, hey, badakizu, transmititutako balio hasieratu zeure esleituriko nodo bat itzultzen du. Ziur ohar dioen nolabaiteko jarri eta, ondoren, egin nahi duzun deitzaileari itzuliko memoria libratzeko behar da. Horrela, beste norbait inoiz doa bada, eta funtzio hori erabiltzen du, edozein dela ere bat atzera lortzen dute funtzio hori ezagutzen dute uneren libratuko behar dira. 

Guztiak ondo eta ona da hemen hartuta, jaitsiko gara gure kodea sartu eta lerro hauek guztiak ordezkatu hemen , gure eraikitze nodo funtzio deiak. Egin dezagun benetan azkar. Zati bat ari gara eta ez ordezkatu zati hau behera hemen behean non Wire dugu nodo bakoitzak beste seinalatu, hori delako, ezin dugu gure funtzioa. Baina, egin dezagun root = build_node (7); nodo * hiru = build_node (3); nodo * sei = build_node (6); nodo * bederatzi = build_node (9); Eta orain, nahi dugu nodoak gehitzeko = build_node (5); * bost nodo nodo * zortzi = build_node (8); eta beste nodo zer izan zen? Dezagun hemen ikus-en. Ere gehi 2 nahi dugu - nodo * bi = build_node (2); Bale. Une horretan, Behin got 7, 3, 9, eta 6 badakigu guztiak kable egokia, baina zer 5, 8, eta 2 buruz? Ordena dagokion guztia mantentzeko, badakigu, hiru eskubidea seme-alabak 6. Beraz, ari gara 5 gehitu nahi izanez gero, Gainera, 5 3 root zuhaitzaren eskuinaldean dagokio, beraz, orokorrean 5 6 ezker haurraren dagokio. Hau egin ahal izango dugu, esaten sei -> left_child = bost; eta, ondoren, 8 9 ezker haurraren dagokio, beraz, bederatzi -> left_child = zortzi; eta, ondoren, 2 3 seme-alaba ezker da, beraz, hori egin ahal izango dugu, hemen - thee -> left_child = bi; Ez baduzu nahiko jarraitu batera batera, marraztu zeure burua proposatzen dut. 

Bale. Dezagun gorde hau. Goazen eta ziurtatu du biltzen, eta, ondoren, gure Contiene deiak gehitu ahal izango dugu. Looks guztia oraindik biltzen bezala. Goazen eta zenbait dauka deiak gehitu. Berriz ere, kopia eta itsatsi pixka bat egin dut. Orain let 5, 8, eta 2 bilatzeko. Bale. Dezagun ziurtatu hori guztia oraindik ere itxura ona. Great! Gorde eta irten. Dezagun egin, konpilatu, eta now dezagun exekutatu. Emaitzak, dena besterik ez da atsegina eta ondo bezala lan begira. Great! Beraz, gaur egun, lortu dugu gure Contiene funtzioa idatzi. Dezagun mugitu eta nodoak nola sartu zuhaitza lanean hasteko urteaz geroztik ari gara, gisa egiten oraintxe, gauzak ez dira oso politak. 

Joaten gara atzera zehaztapena izanez gero, galdetzen digu izeneko funtzio bat txerta idazteko berriz, boolearra itzuli ala ez benetan izan dugu sartu nodoaren zuhaitza eta, ondoren, zuhaitza txertatzeko balioa zehaztu gure Txertatze funtzioa argumentu bakarra. Itzultzeko egia izan dugu, hain zuzen ere bada sartu nodoaren balioa duten zuhaitza, Horrek esan nahi du, dugu, bat, memoria nahikoa izan zuten, eta, ondoren, bi, nodo hori ez da dagoeneko zuhaitz geroztik dago - gogoan, ez dugu balio bikoiztuak izan zuhaitza, besterik gabe, gauza sinpleak egiteko. Bale. Kodea atzera. Ireki sortu. Pixka bat Zoom, eta gero behera joan. Dezagun txertatze-eskubidea badu, batez ere, funtzio ipini. Berriz ere, deitu behar boolearra-txertatze (int balioa) egingo da. Eman apur bat gehiago espazioa, eta, ondoren, lehenetsi gisa, dezagun oso amaieran faltsua bueltan jarri. Orain behera behealdean, dezagun aurrera, eta horren ordez, nodo eskuz eraikitzeko nagusian, geure buruari, eta horiek, kableatuaren ari gara egiten bezala beste bakoitzean seinalatu Txertatze funtzioa dugu konfiantza horretarako. Ez dugu gure Txertatze funtzioa oinarritzen hutsetik zuhaitz osoa eraikitzeko besterik gabe, baizik eta lerro hauek kentzeko dugu - we'll lerro hauen out duzu nodo 5, 8, eta 2 eraikitzen. Eta, horren ordez, deiak sartu dugu gure txertatze-funtzioa Ziurtatu hori, eta benetan funtzionatzen egiteko. Hemen goaz. 

Orain iruzkindu dugu lerro hauek. Besterik ez dugu, 7, 3, 9, eta 6 puntu honetan, gure zuhaitz. Ziur hori lan egin ahal izateko, mapan handiago ahal izango ditugu, egin gure binary zuhaitz, exekutatu, eta ikusten badu dezakegu gaur egun gurekin kontatzea Oraindik erabat eskuineko 5, 8, eta 2 ez dira jada zuhaitzean. Joan atzera kodea, eta nola sartu dugu? Gogoratu denean benetan ginen 5 txertatu, 8, eta 2 aurretik genuen. Plinko joko bat jokatu dugu, non erro hasi ginen, zuhaitz bat jaitsi ziren banan-banan dagokion hutsunea aurkitu genuen arte. eta, ondoren, kable nodoaren Leku egokia. Gauza bera egiten ari gara. Hau da, funtsean, erabiltzen dugun kodea idatziz bezala dauka funtzioa non nodo lekuen aurkitzeko, eta, ondoren, bakarrik ari gara Nodo bertan sartu. Dezagun egiten hasteko. 

Beraz, * orain = root nodo bat dugu; ari gara dauka kodea jarraitu behar du aurkituko dugu ez dela nahiko Gurekin lan egin arte. Zuhaitz bidez joan gara uneko elementua null ez da bitartean, eta jakin dugu orain horren balioa sartu nahian ari garen balioa berdina da - ondo, eta kasu horretan, ezin dugu benetan sartu nodoaren Zuhaitz sartu bikoiztuak balio bat dugu, horrek esan nahi du delako. Hemen benetan ari gara false itzuli. Orain, bestela orain balioa da balioa baino txikiagoa bada, gaur egun ezagutzen dugun eskubidea dugula mugitzen  Balio orain zuhaitz eskuineko erdia pertenece delako. Bestela, ezkerrera eraman dugu. Hori da, funtsean, gure Contiene funtziona bertan. 

Une honetan, behin amaitu dugu, berriz, begizta hau, gure orain erakuslea apuntatzen null funtzioa ez badago itzuli. Beraz, ari gara orain beharrik spot non nodo berria txertatu nahi dugu. Zer geratzen da egin behar da benetan nodo berria eraiki, egin nahiko erraz dezakegu. Gure super-handy nodo eraikitze funtzioa erabili ahal izango ditugu, eta zerbait ez dugu ez lehenago - mota besterik ez dugu ematen zuen, baina orain, ez besterik ez ziurtatu beharko dugu. probatzeko ziurtatu nodo berriak Itzulitako balioa izan zen benetan egin nahi dugu ez null, memoria sartzen da null bada hasteko ez dugu nahi duelako. Ziurtatu berri nodo null ez dela berdina probatu ahal izango dugu. Edo, horren ordez, besterik gabe, ahal izango dugu benetan bada null null bada, ondoren, besterik gabe, ahal izango dugu itzultzeko faltsua hasieran. 

Une honetan, nodo berria Wire bere zuhaitza Leku egokia dugu. Dugu atzera nagusia eta benetan ginen balioetan kableatuak baino lehen, ginen egiten 3 zuhaitza jarri nahi izan dugu, ikusiko dugu root haurren ezkerreko accessed dugu. 9 jarri dugu zuhaitza, erro haur eskubidea sartzeko egin behar izan dugu. Gurasoa erakuslea izan behar zuhaitza sartu balio berri bat jarri behar izan genuen. Itzuli korritzea sartu, ez da nahiko lan du hemen guraso erakuslea izan dugu ez delako. Zer egiteko gai izan nahi dugu, hau da, puntu honetan, gurasoaren balioa egiaztatu eta ikusi ondo, gosh gurasoaren balioa uneko balioa baino txikiagoa bada, ondoren, guraso eskubidea seme-alabak nodo berria izan behar du; bestela, gurasoa seme-alaba ezker nodo berria izan behar du. Baina, ez dugu guraso erakuslea hau nahiko oraindik. 

Horretarako, benetan ari gara jarraitzeko Zuhaitz bidez goazela eta jakin gure loop goiko toki egokia. Egin ahal izango dugu scrolling back up gure Txertatze funtzioa goian eta erakuslea beste aldagai segimendu izeneko gurasoa. Ezarri berdinak gara, hasieran null eta, ondoren, aldi bakoitzean zuhaitz bidez, guraso erakuslea uneko erakuslea etortzeko goaz. Ezarri guraso orain berdina. Horrela, garai bakoitzean zehar joaten gara, uneko erakuslea lortzen handitutako bermatzeko goaz guraso erakuslea jarraitzen du - maila bat besterik ez da zuhaitza uneko erakuslea baino handiagoa. Guztiak itxura nahiko ona da. 

Nik uste dut gauza bat egokitu nahi dugu egingo da hau nodo itzuli null eraikitzeko. Eraikitzeko nodo benetan behar bezala itzuli null, kode hori aldatu nahi dugu, hemen probatu delako, inoiz ez dugu ziur malloc baliozko erakuslea itzuli bat egiteko. Beraz, (n = NULL!), Eta ondoren malloc itzuli baliozko erakuslea gero, hasieratu dugu; bestela, besterik ez dugu itzuli eta amaituko da Gurekin null itzultzen. Orain itxura nahiko ona da. Dezagun ziurtatu hau benetan biltzen. Binary zuhaitza, eta oh, lortu dugu stuff batzuk gertatzen da hemen. 

Lortu dugu, funtzioaren adierazpen inplizitua eraikitzeko nodo. Berriz ere, Konpilatzaileak hauekin, goialdean hasten ari dugu. Zer behar duela esan nahi da naiz I eraikitzeko nodo deituz dut benetan aurretik deklaratu du. Dezagun itzuli kodea benetan azkar. Korritu behera, eta ziur aski, nire Txertatze funtzioa deklaratu eraikitze nodo funtzio batez ere, baina eraikitzeko nodo txertatze barruan erabiltzen saiatzen ari naiz. Kopia eta joan egingo naiz, eta gero, eraikitze nodo funtzio modu itsatsi hemen goialdean. Horrela, espero funtzionatuko du. Eman dezagun hau beste joan. Orain biltzen dena. Guztiak ona da. 

Baina puntu honetan, ez dugu benetan gure Txertatze funtzioa deitzen zaio. Ezagutzen dugu biltzen dela, eta, beraz, goazen, eta dei batzuk jarri sartu Egin dezagun hori gure eginkizun nagusia. Hemen, iruzkindu, 5, 8, eta 2 eta orduan ez genuen Wire horiek gora behera hemen. Egin dezagun dei batzuk txertatzeko, dezagun ere erabili stuff mota bera erabiltzen dugu printf deiak horiek egin genuen ziur dena txertatuko get zuen behar bezala egiteko. Kopiatu eta itsatsi egingo dut, eta horren ordez, badu txertatze egin dugu. Eta horren ordez, 6, 10 eta 1, 5, 8, eta 2 erabiltzen dugu. Espero sartu behar 5, 8, eta 2 zuhaitz sartu. Konpilatu. Guztiak ona da. Orain benetan dugu gure programa exekutatu. 

Dena faltsua itzuli. Beraz, 5, 8, eta 2 ez da joan, eta Contiene ez bilatu bai itxura. Zer gertatzen da? Dezagun Txikiagotu. Lehenengo arazoa zen txertatze zirudien faltsua itzultzeko, eta begiratzen dugu gure bueltan dei faltsua utzi delako bezala, eta egia esan, inoiz ez dugu itzuli egia. Ezarri ahal izango dugu. Bigarren arazoa da, nahiz eta gaur egun egiten dugun - gorde hau, irten make berriro, konpilatu da ondoren exekutatu da - beste zerbait gertatu da hemen ikusten dugu. 5, 8, eta 2 ziren oraindik, inoiz zuhaitza aurkitu. Beraz, zer gertatzen da? 

Dezagun begirada kodea. Ikus dezagun hau irudikatu bada. Gurasoa ez da nulua izanik hasiko dugu. Erakuslea uneko root erakuslea berdina ezarri dugu, eta gure lan egiteko Zuhaitz bidez goaz. Uneko nodoaren null ez bada, ondoren, behera mugitu ahal izango dugun pixka bat ezagutzen dugu. Gure guraso erakuslea dugu egungo erakuslea berdinak izan, checked balioa balioak berdinak dira faltsuak itzuli dugu. Baloreak ez dira hain eramaten bada eskubidea dugu; bestela, ezkerreko aldatu dugu. Ondoren, nodo bat eraiki dugu. Pixka bat mapan handiago dut. Eta hemen, sortu Wire saiatzeko balio berdina izan dugu. Zer gertatzen da? Ikus dezagun ziurrenik Valgrind gurekin bada aholku bat eman dezake. 

Valgrind erabili besterik ez delako Valgrind benetan azkar bidez gustatzen zait eta esaten dizu daude memoria akatsak edozein bada. Valgrind kodea exekutatzen dugu, ikusi dezakezu eskuineko here--Valgrind./binary_tree--and hit sartu. Baina ez dute memoria akatsen bat ikusten duzu, beraz, dena ongi bezala, beraz, orain arte badirudi. Dute memoria filtrazioen gara, ezagutzen egiten dugu, gara ez delako gure edozein nodo libre gertatzen ari da. Dezagun saiatu GDB exekutatzen ari da ikusteko zer ari den benetan gertatzen ari. Gdb egin dugu. / Binary_tree. Abiaraziko da isuna. Dezagun ezarri txertatze-break puntu bat. Dezagun exekutatu. Inoiz ez dugu benetan izeneko txertatze dirudi. Arazoa zen itxura besterik ez denean behera aldatu dut hemen nagusian dauka printf deiak horiek guztiak - Egia esan, inoiz ez dut aldatu hauen txertatze deitu. Eman dezagun saiatu. Dezagun konpilatu. Guztiak itxura ona dago. Dezagun saiatu exekutatzen ari da, ikusi zer gertatzen den. Bale! Everything itxura nahiko ona dago. 

Final gauza pentsatu da, daude kasu ertzean txertatze hau edozein? Eta bihurtzen da, bai, bat ertzean Kasu horretan, interesgarria da beti pentsatu da, zer gertatzen da zure zuhaitz hutsik badago, eta txertatze-funtzio hau deitu? Arituko da? Beno, dezagun ematen saiatu. - Binary_tree c. Hau probatzeko goaz, gure funtzio nagusia behera joan goaz, eta ez-kableatu nodo horiek atsegin dute hau baino, besterik ari gara gauza osoa behar duzu, eta sortu nodo geuk kableatuaren ordez, benetan ahal izango dugu aurrera, eta hori guztia ezabatu. Guztia dei bat sartu egin gara. Beraz, utzi egin beharrean, 5, 8, eta 2, 7 txertatzeko, 3, eta 9 ari dugu. Eta gero ere nahi dugu, 6 sartu baita. Gorde. Irten. Egin binary zuhaitz. Guztiak biltzen ditu. Besterik ez dugu exekutatu da, eta ikusi zer gertatzen den, baina ere benetan garrantzitsua izango da ziur egiteko ez dugu memoria akatsak hau gure ertzean kasu buruz ezagutzen dugun bat da geroztik. 

Dezagun ziurtatu ondo funtzionatzen duela Valgrind pean, Valgrind. / binary_tree exekutatu egin dugu. Hain zuzen ere, dugu bezala testuinguru bat errorea bat dirudi segmentaziuo hutsegitea dugu. Zer gertatu da? Valgrind benetan kontatzen digu, non da. Zoom out apur bat. Gure txertatze-funtzio bezala gertatzen ari dela dirudi, non tamaina 4 baliogabe bat irakurri dugu insert at line 60. Dezagun atzera jo eta ikus zer gertatzen da hemen. Txikiagotu oso azkarra da. Ziurtatu du ez duela pantailaren ertzean dugun guztia ikusi ahal izateko egin nahi dut. Pull hori pixka bat. Bale. Korritu behera, eta arazoa da hemen. Zer gertatzen da lortuko dugu behera bada, eta gaur egungo nodo nulua da dagoeneko, gure guraso nodo nulua da, beraz, oso goian, hementxe dugu - bitartean begizta hau inoiz ez da benetan bada exekutatzen gure uneko balioa null delako gure root null orain null da, beraz, gero, gure guraso inoiz ez orain edo baliozko balio bat lortzen da, Beraz, gurasoak ere izango dira null. Gogoratu behar dugu hori egiaztatu denbora hartu behar dugu hemen, eta gurasoaren balioa sartzen hasten dugu. Beraz, zer gertatzen da? Beno bada, gurasoak null (guraso == NULL) - ezagutzen dugu ez dago behar zuhaitza ezer ez izan. Saiatzen dira erro sartu behar dugu. Hori egin ahal izango dugu, root nodo berria berdina ezarriz. Ondoren, puntu honetan, ez dugu benetan nahi beste gauza hauen bidez. Horren ordez, hementxe, ez bai dugu bat, bestela-bada bestela, edo dena uztartu izan dugu hemen bat bestela, baina hemen dugu erabili, bestela, eta, era horretan egin. Orain, probatu dugu, gure guraso ziurtatu ez dela null aurretik benetan, bere eremu sartzeko saiatzen ari dela esan nahi du. Segmentaziuo hutsegitea saihesteko lagunduko digu. Beraz, dugu irten, mapan handiago, konpilatu, exekutatu. 

Akatsik ez, baina oraindik dugu memoria filtrazioen sorta bat genuen, ez delako gure edozein nodo libre. Baina, joaten gara eta hemen gure inprimaketaren dugu, ikusiko dugu, hori bai, gure txertatzen guztiak itxura egia itzuli ziren, eta hori ona da. Txertatzen dira egia, eta, ondoren, dagokion Contiene deiak ere egia da. 

Good job! Dugu bezala txertatze bezala idatzia dirudi. Hori da aste honetan Arazoa Set espezifikazioa dugun guztia. Fun erronka bat da, nola benetan joan nahi duzun pentsatu Zuhaitz hau nodo guztiak. Egin ahal izango dugu, beraz, modu ezberdinetan zenbaki bat, baina uzten dut sortu ahal izango duzu, esperimentu eta fun erronka bat bezala, saiatu eta ziurtatu ziurtatu egin daitezke Valgrind txosten hori ez akatsak eta ihesak ez itzultzen du. 

Zorte on aste honetan Huffman kodeketa arazo multzo, eta ikusiko dugu datorren astean! [CS50.TV]