[Powered by Google Translate] [Seksyon 7] [Mwens Alèz]
[Nate Hardison] [Inivèsite Harvard]
[Sa a se CS50.] [CS50.TV]
>> Byenveni nan Seksyon 7.
Mèsi a siklòn Sandy,
olye pou yo gen yon seksyon nòmal semèn sa a,
n ap fè sa a mache-a, atravè seksyon an nan kesyon.
Mwen pral yo dwe swiv ansanm ak Pwoblèm nan Fikse 6 Specification,
ak ale atravè tout tout kesyon yo ki nan la
Yon seksyon nan seksyon Kesyon.
Si gen nenpòt kesyon,
tanpri poste sa yo sou CS50 diskite.
>> Byen. Se pou nou jwenn te kòmanse.
Kounye a, m ap gade paj 3 nan Specification a Set Pwoblèm.
Nou pwal premye kòmanse pale osijè pye bwa binè
depi moun ki gen yon anpil nan enpòtans nan seri pwoblèm yo semenn sa a -
kodaj a Tree Huffman.
Youn nan estrikti yo done trè premye nou te pale de sou CS50 te etalaj la.
Sonje ke yon etalaj lan se yon sekans nan eleman -
tout kalite nan menm - ki estoke dwa pwochen nan chak lòt nan memwa.
Si mwen gen yon etalaj nonb antye relatif ki mwen ka trase lè l sèvi avèk sa a style bwat-nimewo-nonm antye relatif -
Se pou nou di mwen gen 5 nan premye bwat la, mwen gen 7 an dezyèm lan,
Lè sa a, mwen gen 8, 10, ak 20 nan ti bwat la final la.
Sonje byen, de la reyèlman bon bagay sou sa a etalaj
yo se ke nou gen aksè sa a konstan-fwa nan nenpòt ki eleman an patikilye
nan etalaj la si nou konnen endèks li yo.
Pou egzanp, si mwen vle gen tan pwan eleman nan twazyèm nan etalaj la -
nan endèks 2 lè l sèvi avèk sistèm zewo ki baze sou Indexing nou yo -
Mwen literalman jis gen nan fè yon senp kalkil matematik,
hop ak sa yo ki pozisyon nan etalaj la,
rale mete deyò 8 sa a, ki estoke a,
epi mwen bon yo ale.
>> Youn nan bagay ki move sou sa a etalaj - ke nou te pale osijè de
lè nou diskite lye lis -
se ke si mwen vle insert yon eleman nan sa a etalaj,
Mwen pral gen fè kèk déplacement alantou.
Pou egzanp, sa a etalaj dwa isit la
se nan Ranje lòd - Ranje nan lòd moute -
5, Lè sa a, 7, Lè sa a, 8, Lè sa a, 10, ak Lè sa a, 20 -
Men, si mwen vle insert nimewo a 9 nan sa a etalaj,
Mwen pral gen chanjman kèk nan eleman yo nan lòd fè espas.
Nou ka desine sa a soti isit la.
Mwen pral gen pou avanse pou 5 an, 7 la, ak Lè sa a, 8 la;
kreye yon espas kote mwen ka mete 9 la,
ak Lè sa a, 10 ak 20 an ka ale nan a dwat a 9 an.
Sa a se kalite yon doulè paske nan senaryo ki pi mal la-ka -
lè n ap gen yo insert swa nan kòmansman an oswa nan fen a
nan etalaj la, depann sou ki jan n ap déplacement -
nou ta ka fini gen chanjman tout nan eleman yo
kounye a ke nou ap estoke nan etalaj la.
>> Se konsa, sa ki te fason nan alantou sa a?
Fason nan alantou sa a te pou yo ale nan lye-lis metòd nou an kote -
olye pou yo estoke eleman yo 5, 7, 8, 10, ak 20 tout pwochen nan chak lòt nan memwa -
ki sa nou olye t 'te sere yo kalite tout kote nou te vle estoke yo
nan sa yo nœuds lis lye-ki mwen desen soti isit la, kalite komisyon hoc.
Lè sa a, nou konekte yo ansanm lè l sèvi avèk sa yo endikasyon kap vini an.
Mwen ka gen yon konsèy soti nan 5 a 7 an,
yon konsèy, nan lè 7 a 8 an,
yon konsèy de 8 a 10 an,
epi finalman, yon konsèy ki sòti nan 10 a 20 an a,
ak Lè sa a, yon konsèy nil a 20 an ki endike ke pa gen anyen gòch.
Komès-off la nou genyen isit la
se ke kounye a si nou vle insert nimewo a 9 nan Ranje lis nou an,
tout sa nou dwe fè se kreye yon ne nouvo ak 9,
WIRE l 'kanpe nan pwen nan plas la ki apwopriye,
ak Lè sa a, re-fil 8 nan nan pwen desann nan 9 lan.
Sa a se trè vit, an konsideran nou konnen egzakteman ki kote nou vle insert 9 la.
Men, komès-off la an echanj pou sa a se ke nou te kounye a pèdi aksè a konstan-fwa
nan nenpòt ki eleman an patikilye nan estrikti done nou an.
Pou egzanp, si mwen vle jwenn eleman nan katriyèm nan lis sa a lye,
Mwen pral gen kòmanse nan kòmansman la anpil nan lis la
ak travay fason mwen an nan konte ne-pa-ne, jouk tan mwen jwenn youn nan katriyèm.
>> Yo nan lòd yo jwenn pi bon pèfòmans aksè pase yon lis lye -
men tou kenbe kèk nan benefis sa yo ke nou te gen
an tèm de tan ensèsyon-nan yon lis lye -
yon pye bwa binè ki pral bezwen sèvi ak yon ti kras pi plis memwa.
An patikilye, olye pou yo jis yo gen yon konsèy nan yon ne pyebwa binè -
tankou lis la lye-ne fè sa ki -
nou pral ajoute yon konsèy dezyèm ne nan pyebwa binè.
Olye ke sèlman yo gen yon konsèy eleman kap vini an,
nou pwal gen yon konsèy nan yon pitit gòch ak yon timoun dwat.
>> Se pou nou desine yon foto yo wè sa ki ki aktyèlman sanble.
Yon fwa ankò, mwen pral sèvi ak sa yo bwat ak kèk flèch.
Yon ne pyebwa binè pral kòmanse an ak jis nan ti kare yon senp.
Li nan pral gen yon espas pou valè a,
ak Lè sa a, li la tou pral gen yon espas pou timoun nan bò gòch ak pitit la dwat.
Mwen pral mete lejann sou yo isit la.
Nou pral fè timoun nan bò gòch, ak Lè sa a, nou pral kontinye fè timoun nan dwa.
Gen anpil diferan fason pou fè sa.
Pafwa pou espas ak konvenyans,
Mwen pral aktyèlman rale l 'tankou mwen ap fè isit la sou anba a
kote mwen pral gen menm valè a nan tèt la,
ak Lè sa a, timoun nan dwa sou anba dwa-a,
ak timoun nan bò gòch anba bò gòch la.
Ale tounen nan dyagram sa a tèt,
nou gen valè a nan tèt la anpil,
Lè sa a, nou gen konsèy gòch la-pitit, ak Lè sa a, nou gen konsèy nan dwa ak timoun.
>> Nan Specification a Set Pwoblèm,
nou pale sou desen yon ne ki gen yon valè 7,
ak Lè sa a, yon konsèy gòch-timoun ki nil, ak yon konsèy dwat-timoun ki nil.
Nou ka swa ekri nil kapital yo nan espas yo pou
tou de timoun nan bò gòch ak pitit an dwa, oubyen nou ka trase sa a koupe dyagonal
nan chak nan bwat yo pou montre pou ke li nan nil.
Mwen pral fè sa senpleman paske sa a, se pi senp.
Kisa ou wè isit la yo se de fason nan diagramming yon binè ne trè senp pyebwa
kote nou gen valè a 7 ak endikasyon pitit nil.
>> Pati nan dezyèm nan chita pale spesifikasyon nou sou ki jan ak lye lis -
sonje, nou sèlman te gen nan kenbe fèm nan fè eleman an trè premye nan yon lis
sonje lis la tout antye -
ak menm jan an tou, ak yon pyebwa binè, nou gen sèlman yo kenbe fèm nan fè yon sèl konsèy bò pyebwa ki
nan lòd yo kenbe kontwòl sou estrikti nan done tout antye.
Sa a eleman espesyal nan pye bwa a yo rele ne nan rasin nan pyebwa sa a.
Pou egzanp, si sa a ne yon sèl - sa a ne ki gen valè a 7
avèk endikasyon nil gòch-yo ak pitit dwa--
te valè a sèlman nan pyebwa nou yo,
Lè sa a, sa a ta ka ne rasin nou an.
Li nan kòmansman la anpil nan pyebwa nou yo.
Nou ka wè sa a ti kras yon pi klè yon fwa nou kòmanse ajoute plis nœuds bò pyebwa nou yo.
Kite m 'rale moute yon paj nouvo.
>> Koulye a, nou ap ale nan desine yon pye bwa ki gen 7 nan rasin la,
ak 3 andedan timoun nan bò gòch, ak 9 andedan timoun nan dwa.
Yon fwa ankò, sa a se trè senp.
Nou gen 7, trase yon ne pou 3 an, yon ne pou 9,
ak mwen pral mete konsèy gòch la-pitit de 7 a lonje dwèt sou ne la, ki gen 3,
ak konsèy nan dwa-pitit nan ne la, ki gen 7 a ne la, ki gen 9.
Koulye a, depi 3 ak 9 pa gen okenn timoun yo,
nou pwal mete tout endikasyon pitit yo nan pral nil.
Isit la, rasin lan pyebwa nou koresponn ak ne la, ki gen nimewo a 7.
Ou ka wè si tout nou gen se yon konsèy ak sa yo ki ne rasin,
nou ka Lè sa a, mache nan pyebwa nou yo ak jwenn tou de nœuds pitit -
tou de 3 ak 9.
Pa gen bezwen kenbe endikasyon nan chak ne sèl sou pyebwa sa a.
Byen. Koulye a, nou ap ale nan ajoute yon lòt ne dyagram sa a.
Nou pral ajoute yon ne ki gen 6,
e nou pral ajoute sa a kòm timoun nan dwa a ne la, ki gen 3.
Pou fè sa, mwen pral efase ke konsèy nil nan 3 ne la-
ak fil li jiska lonje dwèt sou ne la, ki gen 6. Byen.
>> Nan pwen sa a, se pou yo ale sou yon ti kras nan tèminoloji.
Pou yo kòmanse, rezon ki fè yo rele sa yon pyebwa binè an patikilye
se ke li gen de pwent timoun.
Gen lòt kalite pye bwa ki gen plis endikasyon timoun.
An patikilye, nou te fè yon 'eseye' nan Set Pwoblèm 5.
Ou ap remake ke nan ki eseye, ou te gen 27 endikasyon diferan bay timoun diferan -
yon sèl pou chak nan 26 lèt yo ki nan alfabè a lang angle,
ak Lè sa a, 27th a pou apostwòf la -
se konsa, sa a, se menm jan ak yon kalite pyebwa.
Men, isit la, depi binè li a, nou sèlman gen de pwent timoun.
>> Anplis sa a ne rasin ke nou te pale osijè de,
nou te tou yo te voye bò kote tèm sa a 'timoun ou ye.
Kisa sa vle di pou yon ne yo dwe yon pitit nan yon lòt ne?
Li literalman vle di ke yon ne timoun se yon timoun nan yon lòt ne
si sa ne lòt la gen youn nan pwent pitit li yo mete nan pwen ak sa yo ki ne.
Pou mete sa a nan plis tèm konkrè,
si 3 Yo pwente pa youn nan pwent yo pitit nan 7, lè sa a 3 se yon pitit 7.
Si nou te konnen sa ki timoun yo nan 7 yo se -
byen, nou wè ke 7 an gen yon konsèy nan 3 ak yon konsèy a 9,
Se konsa 9 ak 3 se timoun yo nan 7.
Nèf pa gen okenn timoun yo paske endikasyon pitit li yo ki ap nil,
ak 3 gen sèlman yon timoun, 6.
Sis tou pa gen okenn timoun yo paske tou de pwent li yo ki ap nil, ki nou pral trase kounye a.
>> Anplis de sa, nou menm tou nou pale sou paran yo nan yon ne an patikilye,
ak sa a se, menm jan ou ta atann, reverse sa a deskripsyon timoun.
Chak ne la gen sèlman youn nan paran yo - olye pou yo de kòm ou ta ka atann ak moun.
Pou egzanp, paran an nan 3 se 7.
Paran an nan 9 tou se 7, epi paran an nan 6 se 3. Pa anpil li.
Nou genyen tou tèm pale sou granparan ak pitit pitit,
ak plis ankò jeneralman nou pale de zansèt yo
ak pitit pitit nan yon ne an patikilye.
Zansèt a nan yon ne - oswa zansèt, olye, nan yon ne -
yo tout nan nœuds yo ki kouche sou chemen an soti nan rasin lan ak sa yo ki ne.
Pou egzanp, si m ap gade 6 a ne,
Lè sa a, zansèt yo ap pral fè tou de 3 ak 7.
Zansèt yo nan 9, pou egzanp, se - si m ap gade 9 nan ne -
Lè sa a, zansèt a nan 9 se jis 7.
Ak pitit pitit yo se egzakteman do a.
Si m 'vle fè yon gade nan tout pitit pitit yo nan 7,
Lè sa a, mwen gen fè yon gade nan tout nœuds yo anba li a.
Se konsa, mwen gen 3, 9, ak 6 tout kòm pitit ak pitit pitit 7.
>> Tèm nan final ke nou pral pale sou sa a nosyon ki se yon frè oswa sè.
Frè ak Sè - kalite swiv ansanm sou tèm sa yo fanmi -
yo se nœuds ki nan menm nivo nan pyebwa sa a.
Se konsa,, 3 ak 9 se frè ak sè yo paske yo te nan menm nivo nan pyebwa sa a.
Yo tou de gen paran an menm, 7.
6 la pa gen okenn frè ak sè paske 9 pa gen okenn timoun yo.
Ak 7 pa gen okenn frè ak sè paske li nan rasin nan pyebwa nou yo,
ak gen nan sèlman tout tan 1 rasin.
Pou 7 a gen frè ak sè ke ta dwe gen yon ne pi wo a 7.
Gen ta dwe yon paran nan 7, nan ka sa a 7 pa ta rasin nan pyebwa sa a.
Lè sa a, ki nouvo paran nan 7 ta tou gen gen yon timoun,
e ke pitit ta Lè sa a, dwe frè ak sè a nan 7.
>> Byen. Deplase sou.
Lè nou te kòmanse discussion nou nan pyebwa binè,
nou te pale sou fason nou te ale nan sèvi ak yo nan
jwenn yon avantaj sou tou de ranje e li bay lis lye.
Ak fason an ke nou ap pwal fè sa se ak pwopriyete sa a kòmande.
Nou di ke se yon pye bwa binè te bay lòd, dapre spesifikasyon la,
si pou chak ne nan pyebwa nou yo, tout pitit pitit li yo sou bò gòch la -
timoun nan bò gòch ak tout pitit pitit pitit gòch la a -
gen pi piti valè, ak tout nœuds yo sou bò dwat la -
timoun nan dwa ak tout pitit pitit pitit an dwa a -
gen nœuds pi gran pase valè a ne aktyèl la ke nou ap chèche a.
Jis pou senplisite, nou ap ale nan asime ke pa gen okenn nœuds kopi nan pyebwa nou yo.
Pou egzanp, nan pye bwa sa a nou pa ale fè fas ak ka a
kote nou gen valè a 7 nan rasin lan
ak Lè sa a, nou menm tou nou gen menm valè a 7 lòt kote nan pyebwa sa a.
Nan ka sa a, ou pral avi ke se pye bwa sa a tout bon òdone.
Nou gen valè a 7 nan rasin lan.
Tout nan kite nan 7 -
si mwen defèt tout moun sa yo mak ti kras isit la -
tout bagay sa yo bò gòch la nan 7 - 3 an ak 6 an -
valè sa yo, yo toulède yo mwens pase 7, ak tout bagay sa yo dwa pou - ki se jis sa a 9 -
se pi gran pase 7.
>> Sa a se pa pye bwa a sèlman te bay lòd ki gen valè sa yo,
Men, kite a trase yon pi plis kèk nan yo.
Gen se aktyèlman yon pakèt antye nan fason ke nou ka fè sa.
Mwen pral sèvi ak yon steno jis kenbe bagay sa senp kote -
olye ke desen soti tout la bwat-ak-flèch -
Mwen jis ale nan trase nimewo yo epi ajoute flèch ki konekte yo.
Pou yo kòmanse, nou pral jis ekri pyebwa orijinal nou an ankò kote nou te gen 7yèm, ak Lè sa a, yon 3,
ak Lè sa a, 3 pwente tounen sou bò dwat la a 6 an,
ak 7 te gen yon pitit dwa sa yo ki te 9.
Byen. Ki sa ki nan yon lòt fason ke nou ta ka ekri pye bwa sa a?
Olye pou yo gen 3 dwe timoun nan gòch nan 7,
nou ta ka tou gen 6 a rete toujou la timoun nan gòch nan 7,
ak Lè sa a, 3 pou timoun nan bò gòch nan 6 a.
Sa ta sanble pye bwa sa a isit la kote mwen te gen 7,
Lè sa a, 6, Lè sa a, 3, ak yon 9 sou bò dwat la.
Nou menm tou nou pa bezwen gen 7 kòm ne rasin nou an.
Nou ta ka tou gen 6 kòm ne rasin nou an.
Ki sa ki ta ki sanble?
Si nou ap ale nan kenbe pwopriyete sa a te bay lòd,
tout bagay sa yo bò gòch la nan 6 la gen li dwe mwens pase l '.
Genyen sèlman yon sèl posiblite, ak sa a, se 3.
Men, Lè sa a, kòm timoun nan dwa a 6, nou gen de posiblite yo.
Premyèman, nou te kapab gen 7 an ak Lè sa a, 9 la,
oubyen nou te kapab rale l '- tankou m pral fè isit la -
kote nou gen 9 an kòm timoun nan dwa nan 6 a,
ak Lè sa a, 7 an kòm timoun nan bò gòch nan 9 lan.
>> Koulye a, 7 ak 6 yo pa valè yo sèlman posib pou rasin lan.
Nou ta ka tou gen 3 fèt nan rasin lan.
Kisa kap rive si 3 se nan rasin lan?
Isit la, bagay sa yo jwenn yon ti jan ki enteresan.
Twa pa gen okenn valè ki pi piti pase li,
pou ke tout bò gòch nan pyebwa a se jis ale nan pral nil.
Gen pa k ap pase yo dwe anyen la.
Sou bò dwat la, nou te kapab lis bagay sa yo nan moute lòd.
Nou te kapab gen 3, Lè sa a, 6, Lè sa a, 7, Lè sa a, 9.
Oswa, nou ta ka fè 3, Lè sa a, 6, Lè sa a, 9, Lè sa a, 7.
Oswa, nou ta ka fè 3, Lè sa a, 7, Lè sa a, 6, Lè sa a, 9.
Oswa, 3, 7 - aktyèlman pa gen okenn, nou pa kapab fè yon 7 ankò.
Sa a se yon bagay nou la.
Nou ka fè 9, ak Lè sa a, soti nan 9 a nou ka fè 6 ak Lè sa a, 7.
Oswa, nou ka fè 3, Lè sa a, 9, Lè sa a, 7yèm, ak Lè sa a, 6.
>> Youn nan bagay trase atansyon ou a isit la se
ke sa yo pye bwa yo se yon ti kras etranj-ap chèche.
An patikilye, si nou gade nan 4 pyebwa yo sou bò dwat la -
Mwen pral sèkle yo, isit la -
pyebwa sa yo gade prèske egzakteman menm jan ak yon lis lye.
Chak ne la gen sèlman yon timoun,
epi pou nou pa gen nenpòt nan estrikti sa a pye bwa-tankou sa nou wè, pou egzanp,
nan yon sèl sa a pye bwa Lone sou isit la sou bò gòch anba a.
Pyebwa sa yo yo aktyèlman rele bonjan pyebwa binè,
epi n ap pale sou sa yo plis nan lavni an -
espesyalman si ou ale nan pran kou lòt syans òdinatè.
Pyebwa sa yo se bonjan.
Yo ap pa trè itil paske, tout bon, estrikti sa a prèt tèt li
Passage fwa menm jan ak sa yon lis lye.
Nou pa pran pran avantaj nan memwa siplemantè a - sa a konsèy siplemantè -
paske nan estrikti nou an ke yo te move nan fason sa.
Olye de ale sou yo ak sou trase soti pyebwa yo binè ki gen 9 nan rasin la,
ki se ka a final ke nou ta genyen,
nou ap olye de sa, nan pwen sa a, pral pale yon ti kras sou tèm sa a lòt
ke nou itilize lè w ap pale sou pye bwa, ki te rele wotè a.
>> Wotè nan yon pyebwa se distans ki soti nan rasin nan ne la ki pi-byen lwen,
ou pito ki kantite so ke ou ta gen fè yo nan lòd yo
kòmanse soti nan rasin lan ak Lè sa a, fini nan ne la ki pi-byen lwen nan pyebwa sa a.
Si nou gade nan kèk nan pyebwa sa yo ke nou te trase dwa isit la,
nou ka wè ke si nou pran pye bwa sa a nan kwen gòch anwo ak nou kòmanse a 3 an,
Lè sa a, nou gen fè 1 hop pou li ale nan 6 an, yon hop dezyèm pou li ale nan 7 la,
ak yon hop twazyèm pou li ale nan 9 lan.
Se konsa, wotè a nan pyebwa sa a se 3.
Nou ka fè egzèsis an menm pou pyebwa yo lòt souliye ak sa-a vèt,
e nou wè ke wotè nan tout moun sa yo pyebwa tou se tout bon 3.
Sa a se yon pati nan sa ki fè yo bonjan -
ki wotè yo se jis yon pi piti pase kantite nœuds nan pyebwa a tout antye.
Si nou gade nan pye bwa sa a lòt ki nan antoure ak wouj, sou la lòt bò,
nou wè ke nœuds yo fèy pi-byen lwen yo se 6 la ak 9 la -
kite a ke yo te sa yo nœuds ke pa gen okenn timoun yo.
Se konsa, nan lòd jwenn soti nan ne an rasin swa 6 a oswa 9 la,
nou dwe fè yon sèl hop pou li ale nan 7 a ak Lè sa a, yon hop dezyèm pou li ale nan 9 la,
ak menm jan an tou, se sèlman yon hop dezyèm, nan lè 7 a pou li ale nan 6 a.
Se konsa, wotè a nan pyebwa sa a sou isit la se sèlman 2.
Ou ka ale retounen lakay yo epi fè sa pou tout nan pyebwa yo, lòt ke nou te diskite anvan
kòmanse ak 7 an ak 6 an,
epi ou ap jwenn ki wotè nan tout nan tout sa yo pyebwa tou se 2.
>> Rezon ki fè nou ve yo te ap pale de bay lòd pyebwa binè
epi poukisa yo ap fre a se paske ou kapab fè rechèch nan yo nan
yon fason anpil menm jan ak chèche sou yon etalaj Ranje.
Sa a se kote nou pale sou kesyon pran tan sa a Passage amelyore
sou senp lis la lye.
Avèk yon lis lye - si ou vle jwenn yon eleman an patikilye -
w ap nan pi bon pral fè kèk sòt de rechèch lineyè
ki kote ou kòmanse nan kòmansman an nan yon lis ak hop youn-pa-youn -
yon sèl ne pa youn ne -
nan lis la tout antye jiskaske ou jwenn kèlkeswa sa w ap chèche pou.
Lè nou konsidere ke, si ou gen yon pye bwa binè ki nan ki estoke nan fòma sa a bèl,
ou ka aktyèlman jwenn plis nan yon rechèch binè ale sou
ki kote ou separe ak konkeri
ak rechèch nan mwatye ki apwopriye a nan pye bwa a nan chak etap.
Ann gade pou wè ki jan sa travay.
>> Si nou gen - ankò, pral tounen nan pyebwa orijinal nou yo -
nou kòmanse a 7, nou gen 3 sou bò gòch la, 9 sou bò dwat la,
ak anba 3 a nou gen 6 an.
Si nou vle pou fè rechèch pou nimewo 6 la nan pye bwa sa a, nou ta kòmanse nan rasin lan.
Nou ta konpare valè an ke nou ap chèche pou yo, di, 6,
valè a ki estoke nan ne an ke nou ap kounye a chèche a, 7,
jwenn ke 6 se vre mwens pase 7, se konsa nou ta deplase li nan yon bò gòch li.
Si te valè a nan 6 te pi gran pase 7, nou ta gen olye demenaje ale rete nan bò dwat la.
Depi nou konnen ke - akòz estrikti nan te bay lòd pyebwa binè nou yo -
tout valè yo a mwens pase 7 yo ale nan dwe estoke nan kite nan 7,
gen nan pa gen bezwen menm bezwen deranje kap nan bò dwat la pyebwa sa a.
Yon fwa nou deplase a gòch la ak nou ap kounye a nan ne la, ki gen 3,
nou ka fè sa konparezon menm ankò kote nou konpare 3 an ak 6 an.
Ak nou jwenn ke pandan y ap 6 - valè a nou ap chèche pou - se pi plis pase 3,
nou ka ale nan bò dwat la ne la, ki gen 3.
Gen nan pa gen bò gòch isit la, se konsa nou te ka genyen inyore sa.
Men, nou ka konnen sèlman ke paske nou menm nou ap chèche nan pye bwa a li menm,
epi nou ka wè ke pyebwa a pa gen okenn timoun yo.
>> Li la tou trè fasil yo gade jiska 6 an pye bwa sa a si n ap fè li tèt nou kòm moun,
Men, kite a swiv pwosesis sa a mekanikman tankou yon òdinatè ta fè
reyèlman konprann algorithm a.
Nan pwen sa a, nou ap kounye a kap nan yon ne ki gen 6,
epi nou ap chèche pou valè a 6,
se konsa, vrèman vre, nou te jwenn ne ki apwopriye a.
Nou jwenn valè a 6 nan pyebwa nou, epi nou ka sispann rechèch nou an.
Nan pwen sa a, depann sou sa ki ap pase,
nou ka di, wi, nou te jwenn valè a 6, li egziste nan pyebwa nou yo.
Oswa, si nou ap planifye yo insert yon ne oswa fè yon bagay, nou ka fè sa nan pwen sa.
>> Se pou nou fè yon koup plis rchèrch jis yo wè ki jan sa a travay.
Se pou yo gade nan ki sa ki rive si nou te eseye ak gade moute valè a 10.
Si nou te yo gade jiska valè a 10, nou ta kòmanse nan rasin lan.
Nou ta wè ke 10 se pi gran pase 7, se konsa nou ta deplase a dwat la.
Nou ta jwenn a 9 la epi konpare 9 a 10 an ak wè ke 9 se vre mwens pase 10.
Se konsa, ankò, nou ta eseye pou avanse pou pi a dwat la.
Men, nan pwen sa a, nou ta remake ke nou ap nan yon ne nil.
Pa gen anyen la a. Pa gen anyen ki kote 10 nan yo ta dwe.
Sa a se kote nou ka rapòte echèk - ke gen se vre pa gen okenn 10 nan pyebwa sa a.
Epi finalman, se pou yo ale nan ka a kote nou ap eseye yo gade jiska 1 nan pyebwa sa a.
Sa a se menm jan ak sa k ap pase si nou gade moute 10, eksepte olye pou yo ale sou bò dwat la,
nou pral pou yo ale nan bò gòch li.
Nou kòmanse nan 7 a ak wè ke 1 se mwens pase 7, konsa nou deplase li nan yon bò gòch li.
Nou jwenn nan 3 a ak wè ke 1 se mwens pase 3, kifè, ankò nou eseye pou yo avanse pou bò gòch li.
Nan pwen sa a nou gen yon ne nil, se konsa ankò nou ka rapòte echèk.
>> Si ou vle aprann plis sou pye bwa binè,
gen tout yon seri nan pwoblèm plezi ti kras ke ou ka fè avèk yo.
Mwen sijere pratike desen an soti nan dyagram sa yo youn-pa-youn
epi suiv nan tout etap yo diferan,
paske sa a ap vini nan super sou la men-
pa sèlman lè w ap fè kodaj mete nan pwoblèm Huffman
men tou nan kou lavni -
jis pou aprann jan pou trase soti estrikti sa yo done ak panse atravè pwoblèm yo
yo ak plim ak papye, oubyen, nan ka sa a, iPad ak dyaman.
>> Nan pwen sa a menm si, nou pral pou avanse pou sou fè kèk pratik kodaj
ak aktyèlman jwe ak pyebwa sa yo binè ak wè.
Mwen pral chanje tounen sou nan òdinatè mwen an.
Pou pati sa a nan seksyon an, olye pou yo lè l sèvi avèk CS50 Run oswa CS50 Espas,
Mwen pral sèvi ak aparèy la.
>> Apre ansanm ak spesifikasyon la Set Pwoblèm,
Mwen wè ke mwen sipoze louvri moute aparèy la,
ale nan folder Dropbox m 'yo, kreye yon folder rele Seksyon 7,
ak Lè sa a, kreye yon dosye rele binary_tree.c.
Isit la nou ale. Mwen te gen aparèy la deja louvri.
Mwen pral rale moute yon tèminal.
Mwen pral pou yo ale nan folder nan Dropbox, fè yon anyè rele section7,
epi wè li nan totalman vid.
Koulye a, mwen pral louvri moute binary_tree.c.
Byen. Isit la nou ale - vid dosye-a.
>> Se pou nou tounen nan spesifikasyon la.
Spesifikasyon la mande yo kreye yon definisyon kalite nouvo
pou yon ne pyebwa binè ki gen valè Int -
jis tankou valè sa yo ke nou te trase soti nan diagramming nou an avan.
Nou pral itilize sa a boilerplate tipedèf ke nou te fè isit la
ke ou ta dwe rekonèt nan Set Pwoblèm 5 -
si ou te fè wout la tab regle nan viktwa pwogram nan ortograf.
Ou ta dwe tou rekonèt li nan seksyon semèn pase a nan
kote nou te pale osijè de lye lis.
Nou gen sa a tipedèf nan yon ne struct,
e nou te bay sa a ne struct non sa a ne struct davans
pou nou ka Lè sa a, gade nan li depi nou pral vle gen endikasyon ne struct
kòm yon pati nan struct nou an, men nou te Lè sa a, antoure sa a -
ou pito, fèmen sa a - nan yon tipedèf
pou ke, pita nan kòd la, nou ka al gade nan sa a struct kòm jis ne yon olye de yon ne struct.
>> Sa a se pral fè anpil menm jan ak definisyon an lis separeman ki lye ak ke nou te wè semèn pase a.
Pou fè sa, kite la jis kòmanse pa ekri soti boilerplate la.
Nou konnen nou gen gen yon valè nonb antye relatif,
se konsa nou pral mete an valè Int, ak Lè sa a, olye pou yo gen sèlman yon sèl konsèy eleman nan pwochen -
tankou nou te fè ak separeman ki lye ak lis -
nou pwal gen endikasyon kite la ak dwa timoun.
Sa a se trè senp twò - struct ne pitit * gòch;
ak struct ne * dwa timoun;. Fre.
Ki sanble yon kòmansman trè bon.
Se pou nou tounen nan spesifikasyon la.
>> Koulye a, nou bezwen deklare yon ne mondyal varyab * pou rasin lan yon pye bwa.
Nou pwal fè sa a mondyal jis tankou nou te fè premye konsèy nan lye lis nou an tou mondyal.
Sa a te tèlman ke nan fonksyon sa yo ke nou ekri
nou pa gen kenbe pase alantou sa a rasin -
menm si nou pral wè ke si ou fè vle ekri sa yo fonksyon recursive,
li ta ka pi bon pa menm pase l 'nan kòm yon mondyal an plas an premye
ak olye inisyalize li lokalman nan fonksyon prensipal ou an.
Men, nou pwal fè li globalman yo kòmanse.
Yon fwa ankò, nou pral bay yon koup la espas, ak mwen pral deklare yon rasin * ne.
Jis asire w ke mwen pa kite sa-a uninitialized, mwen pral mete l 'egal a nil.
Koulye a, nan fonksyon prensipal - ki nou pral ekri vrèman byen vit dwa isit la -
int prensipal (Int arg, Konstitisyon Char * argv []) -
ak mwen pral kòmanse deklare etalaj argv mwen kòm Konstitisyon jis pou m 'konnen
ki sa yo agiman yo se agiman ke mwen pwobableman pa vle modifye.
Si m 'vle li modifye yo mwen ta pwobableman ap fè kopi yo.
Ou pral wè sa a yon anpil nan kòd.
Li nan amann swa fason. Li nan amann yo kite li kòm - retire okenn pati konstitisyon an si ou ta renmen.
Mwen tipikman mete l 'nan jis pou m' fè sonje tèt mwen
ke mwen pwobableman pa vle modifye sa yo agiman.
>> Kòm toujou, mwen pral gen ladan yo sa a retou 0 liy nan fen prensipal la.
Isit la, mwen pral inisyalize ne rasin m 'yo.
Kòm li vle di kounye a, mwen te gen yon konsèy ki nan mete nil,
Se konsa, li lonje dwèt nan pa gen anyen.
Yo nan lòd yo aktyèlman kòmanse bati ne la,
M 'premye bezwen asiyen memwa pou li a.
Mwen pral fè sa pa fè memwa sou pil wòch la lè l sèvi avèk malok.
Mwen pral mete rasin egal a rezilta a nan malok,
ak mwen pral sèvi ak operatè a sizof kalkile gwosè a nan yon ne.
Rezon ki fè mwen sèvi ak sizof ne kòm opoze a, di,
fè yon bagay tankou sa a - malok (4 + 4 +4) oswa malok 12 -
se paske mwen vle kòd mwen yo dwe kòm konpatib ke posib.
Mwen vle pou kapab pran sa a. C ranpli, konpile l 'sou aparèy la,
epi konpile l 'sou 64-bit Mac mwen an -
oswa sou yon achitekti konplètman diferan -
e mwen vle sa a tout moun nan travay menm bagay la.
>> Si mwen fè panse de gwosè a nan varyab -
gwosè a nan yon int oswa gwosè a nan yon konsèy -
Lè sa a, mwen tou fè sipozisyon sou kalite ki nan architectures
ki te sou kòd mwen ka avèk siksè konpile lè kouri.
Toujou itilize sizof tankou yo te opoze a manuelman adisyon jaden yo struct.
Rezon ki fè lòt la se ke gen ta ka tou pou kouvèti ki du a mete nan struct la.
Menm jis adisyon jaden yo endividyèl se pa yon bagay ke ou tipikman vle fè a,
se konsa, efase ke liy.
Koulye a, reyèlman inisyalize sa a ne rasin,
Mwen pral oblije ploge nan valè pou chak nan jaden diferan li yo.
Pou egzanp, pou valè Mwen konnen mwen vle inisyalize a 7,
ak pou kounye a mwen pral mete timoun nan bò gòch yo dwe nil
ak pitit an dwa tou pral nil. Gwo!
Nou te fè pati sa a nan espèk a.
>> Spesifikasyon la desann nan fon an nan paj 3 mande m 'yo kreye twa plis nœuds -
yon sèl ki gen 3, yon sèl ki gen 6, ak yon sèl ak 9 -
ak Lè sa a, fil elektrik yo moute pou li sanble egzakteman menm jan ak dyagram pyebwa nou
ke nou te pale de deja a.
Se pou nou fè sa byen vit isit la.
Ou pral wè vrèman byen vit ke mwen pral kòmanse ekri yon pakèt moun sou kòd kopi.
Mwen pral kreye yon * ne ak mwen pral rele li twa.
Mwen pral mete l 'egal a malok (sizof (ne)).
Mwen pral mete twa-> valè = 3.
Twa -> left_child = nil; twa -> dwa _child = nil; kòm byen.
Ki sanble trè sanblab yo inisyalizin rasin lan, ak sa a, se ekzakteman ki sa
Mwen pral oblije fè si mwen kòmanse inisyalizin 6 ak 9 kòm byen.
M pral fè sa vrèman byen vit isit la - aktyèlman, mwen pral fè yon kopi ti kras ak keratin,
ak asire w ke mwen - byen.
Koulye a, mwen te gen li kopye e mwen ka ale pi devan epi mete sa egal a 6.
Ou ka wè ke sa a pran ti tan epi li pa super-efikas.
Nan jis ti jan yon ti kras, nou pral ekri yon fonksyon ki pral fè sa a pou nou.
Mwen vle ranplase sa a ak yon 9, ranplase sa ki gen yon 6.
>> Koulye a, nou te gen tout nœuds nou kreye epi inisyalizèd.
Nou gen rasin nou mete egal a 7, oswa ki gen valè a 7,
ne nou ki gen 3, ne nou ki gen 6, epi ne nou ki gen 9.
Nan pwen sa a, tout sa nou dwe fè se tout bagay fil leve.
Rezon ki fè mwen inisyalizèd tout endikasyon yo nan nil se jis pou m 'fè si ke
Mwen pa gen okenn endikasyon uninitialized an gen pa aksidan.
Epi tou li depi, nan pwen sa a, mwen gen sèlman yo aktyèlman konekte nœuds yo nan chak lòt -
nan sa yo ke yo ap aktyèlman konekte nan - Mwen pa gen yo ale nan, epi fè
asire w ke tout nulls yo se nan la nan kote ki apwopriye yo.
>> Kòmanse nan rasin lan, mwen konnen ke pitit gòch rasin lan se 3.
Mwen konnen ke pitit dwa rasin lan a se 9.
Apre sa, se sèlman lòt timoun nan ke mwen te kite enkyete sou
se pitit dwa 3 a, ki se 6.
Nan pwen sa a, li tout sanble trè bon.
Nou pral efase kèk nan liy sa yo.
Koulye a, tout bagay sanble trè bon.
Se pou nou tounen nan spesifikasyon nou yo ak wè sa ki nou gen yo dwe fè pwochen.
>> Nan pwen sa a, nou gen yo ekri yon fonksyon rele 'gen'
ak yon pwototip nan 'konprann bouleen (Int valè)'.
Lè sa a gen fonksyon ki pral retounen vre
si pye bwa a pwente ke varyab mondyal rasin nou
gen valè a te pase nan fonksyon an ak fo otreman.
Se pou nou ale pi devan epi fè sa.
Sa a se pral fè egzakteman menm jan ak Passage a ke nou te fè nan men sou iPad a jis yon ti jan de sa.
A Se pou rale tounen nan yon ti jan ak woulo liv la.
Nou pral mete sa a fonksyon dwa pi wo a fonksyon prensipal nou an
pou nou pa bezwen fè nenpòt ki sòt de Prototype.
Se konsa, bouleen gen (Int valè).
Gen nou ale. Genyen nan deklarasyon boilerplate nou an.
Jis asire w ke sa a pral konpile,
Mwen pral ale pi devan ak jis mete l 'egal a retounen fo.
Kounye a sa a fonksyon jis pa pral fè anyen ak toujou rapòte ke
valè a ke nou ap chèche pou se pa nan pyebwa sa a.
>> Nan pwen sa a, li la pwobableman yon bon lide -
depi nou te ekri yon pakèt antye nan kòd epi nou pa gen menm te eseye tès li ankò -
asire w ke li tout compiles.
Gen yon koup de bagay sa yo ke nou gen pou fè pou asire w ke sa a pral aktyèlman konpile.
Premyèman, wè si nou ve yo te lè l sèvi avèk nenpòt ki fonksyon nan nenpòt bibliyotèk ke nou pa gen ankò enkli ladan li.
Fonksyon yo nou te itilize byen lwen tèlman yo se malok,
ak Lè sa a, nou te tou yo te lè l sèvi avèk sa a ki kalite - sa a ki kalite san estanda rele 'bool' -
ki se enkli nan dosye a estanda header bouleen.
Nou definitivman vle gen ladan estanda bool.h pou di ki kalite a bouleen,
ak nou menm tou nou vle # enkli estanda lib.h pou bibliyotèk yo estanda
ki gen ladan malok, ak gratis, epi nan tout sa.
Se konsa, rale soti, nou pwal kite fimen.
Ann eseye ak asire w ke sa sa a aktyèlman te fè konpile.
Nou wè ke li fè sa, se konsa nou ap sou track dwat la.
>> Se pou nou louvri moute binary_tree.c ankò.
Li compiles. Ann al desann, epi fè sèten ke nou insert kèk apèl fonksyone konprann nou yo -
jis asire w ke ki nan tout sa byen epi li bon.
Pou egzanp, lè nou te fè kèk rchèrch nan pyebwa nou pi bonè,
nou te eseye yo gade jiska valè yo 6, 10, ak 1, epi nou te konnen ke 6 te nan pyebwa a,
10 pa t 'nan pye bwa a, ak 1 pa t' nan pye bwa a swa.
Se pou nou sèvi ak apèl sa yo echantiyon yo kòm yon fason kalkile si ou pa
fonksyon konprann nou an ap travay.
Yo nan lòd yo fè sa, mwen pral sèvi avèk fonksyon an printf,
epi nou ap ale nan enprime soti rezilta nan apèl la gen.
Mwen pral mete nan yon fisèl "gen (% d) = paske
nou pwal ploge nan valè a ke nou ap ale nan gade pou li a,
ak =% s \ n "epi sèvi ak sa kòm fisèl fòma nou an.
Nou jis ap pral wè - literalman enprime soti sou ekran an -
sa ki sanble yon apèl fonksyon.
Sa a se pa aktyèlman rele nan fonksyon.
Sa a se jis yon fisèl ki fèt yo gade tankou yon apèl fonksyon.
>> Koulye a, nou ap ale nan ploge nan valè yo.
Nou pral eseye gen sou 6,
ak Lè sa a, sa n ap pral fè isit la se sèvi ak ke operatè tèrsyèr.
Ann wè - gen 6 - se konsa, koulye a, mwen te genyen 6 ak si gen 6 an se laverite,
fisèl la ke nou ap ale nan voye bay karaktè fòma% nan yo
a pwal fisèl la "vre".
Se pou nou woulo liv sou yon ti kras.
Sinon, nou vle voye fisèl la "fo" si gen 6 retounen fo.
Sa a se yon ti kras so-ap chèche, men mwen kalkile mwen ta ka kòm byen ilistre
ki sa operatè a tèrsyèr sanble depi nou pa t 'wè li pou ti tan.
Sa se va yon bèl, sou la men fason yo detèminen si fonksyon konprann nou an ap travay.
Mwen pral woulo liv tounen sou bò goch la,
ak mwen pral fè kopi ak keratin liy sa a yon fwa kèk.
Li chanje kèk nan valè sa yo otou,
kidonk sa a se pral 1, ak sa a ki pral gen 10.
>> Nan pwen sa a nou te gen yon bèl konprann fonksyon.
Nou te gen kèk tès yo, epi nou pral wè si sa a tout travay.
Nan pwen sa a nou te ekri kèk plis kòd.
Tan kite fimen deyò epi yo asire w ke tout bagay toujou compiles.
Kite soti, epi kounye a kite a eseye fè pyebwa binè ankò.
Oke, li sanble nou te gen yon erè,
epi nou te gen sa a klèman deklare fonksyon bibliyotèk la printf.
Li sanble ke nou bezwen ale nan ak # enkli standardio.h.
Se avèk sa, tout bagay ta dwe konpile. Nou tout se bon.
Koulye a, kite nan eseye kouri binè pye bwa yo epi wè kisa k ap rive.
Isit la nou ye a,. / Binary_tree,
e nou wè ke, menm jan nou espere -
paske nou pa te aplike gen ankò,
oswa olye, nou te jis mete an retou fo -
nou wè ke li jis retounen fo pou tout nan yo,
Se konsa se te tout ap travay pou pati ki pi san patipri byen.
>> Ann al tounen nan ak aktyèlman aplike gen nan pwen sa.
Mwen pral desann, rale nan, ak -
sonje, algorithm a ke nou te itilize ke nou te kòmanse nan ne an rasin
ak Lè sa a, nan chak ne ke nou rankontre, nou fè yon konparezon,
ak ki baze sou ki konparezon nou swa deplase li nan yon timoun nan gòch la oswa ak pitit la dwat.
Sa a se pral gade trè menm jan ak kòd la rechèch binè ke nou te ekri byen bonè nan tèm nan.
Lè nou kòmanse desann, nou konnen ke nou vle kenbe fèm nan fè ne aktyèl la
ke nou ap chèche a, ak ne li ye kounye a yo pral inisyalizèd ne nan rasin.
Epi, koulye a, nou pwal kenbe ale atravè tout pyebwa a,
epi sonje ke kondisyon kanpe nou yo -
lè nou aktyèlman te travay nan egzanp lan nan men -
se te lè nou rankontre yon ne nil,
pa lè nou te gade yon timoun nil,
men pito lè nou aktyèlman demenaje ale rete nan yon ne nan pye bwa a
epi li te jwenn ke nou se nan yon ne nil.
Nou pral répétèr jouk akt se pa egal a nil.
E kisa nou pral fè?
Nou pral teste si (akt -> valè == valè),
Lè sa a, nou konnen ke nou te aktyèlman te jwenn ne a ke nou ap chèche pou.
Se konsa, isit la, nou ka retounen vre.
Sinon, nou ta renmen wè si wi ou non valè a se mwens pase valè li a.
Si valè ne yo ye a se mwens pase valè an ke nou ap chèche pou yo,
nou pral pou avanse pou pi a dwat la.
Se konsa, akt = akt -> right_child; ak otreman, nou pwal pou yo avanse pou bò gòch li.
akt = akt -> left_child;. Trè senp.
>> Ou pwobableman rekonèt riban an ki sanble anpil menm jan ak sa a soti nan
rechèch binè pi bonè nan tèm nan, eksepte Lè sa a, nou te fè fas ak nan mitan ki ba,, ak segondè.
Isit la, nou jis gen gade nan yon valè ye kounye a,
Se konsa li bèl ak senp.
Se pou nou asire ou ke sa a kòd ap travay.
Premyèman, asire w ke li compiles. Sanble li fè sa.
Ann eseye kouri li.
Ak tout bon, li simagri soti tout bagay ke nou espere.
Li jwenn 6 nan pye bwa a, pa jwenn 10 paske 10 se pa nan pyebwa a,
epi yo pa jwenn 1, swa paske 1 la tou pa nan pyebwa sa a.
Cool bagay.
>> Byen. Se pou nou tounen nan spesifikasyon nou yo ak wè sa ki nan pwochen.
Koulye a, li vle ajoute kèk plis nœuds bò pyebwa nou yo.
Li vle ajoute 5, 2, ak 8yèm ane, ak asire w ke nou gen kòd
toujou ap travay jan yo espere.
Ann al fè sa.
Nan pwen sa a, olye ke fè sa kopi annwiyeu ak keratin ankò,
kite a ekri yon fonksyon aktyèlman kreye yon ne.
Si nou desann tout wout la prensipal yo, nou wè ke nou te toujou ap fè sa a
anpil menm jan kòd sou yo ak sou ankò chak fwa ke nou vle kreye yon ne.
>> Se pou nou ekri yon fonksyon ki pral konstwi aktyèlman yon ne pou nou epi retounen li.
Mwen pral rele li build_node.
Mwen pral bati yon ne ki gen yon valè patikilye.
Rale nan isit la.
Premye bagay mwen pral fè se aktyèlman kreye espas pou ne la sou pil la.
Se konsa, ne * n = malok (sizof (ne)); n -> valè = valè;
ak Lè sa a, isit la, mwen jis ale nan inisyalize tout jaden yo yo dwe valè ki apwopriye yo.
Ak nan fen a trè, nou pral retounen ne nou an.
Byen. Youn nan bagay a nòt la ki fonksyon sa a isit la
ki pral retounen yon konsèy memwa ki te pil-affecte.
Ki sa ki nan bon sou sa a se ke sa a ne kounye a -
nou dwe deklare l 'sou pil wòch la, paske si nou te deklare l' sou chemine a
nou pa ta dwe ka fè l 'nan sa a fonksyon tankou sa a.
Sa memwa ta ale soti nan dimansyon
ak ta dwe valab si nou te eseye gen aksè a li pita sou.
Depi nou yo deklare pil-affecte memwa,
nou pral dwe pran swen nan libere li pita
pou pwogram nou an pa genyen fuit nenpòt memwa.
Nou te ap punting sou sa pou Tout Lòt Bagay nan kòd la
jis pou dedomajman pou senplisite a nan moman an,
Men, si ou te janm ekri yon fonksyon ki sanble tankou sa a
kote ou te gen - kèk rele li yon malok oswa realloc andedan -
ou vle asire w ke ou mete kèk sòt de kòmantè moute isit la ki di,
hey, ou konnen, retounen yon ne pil-affecte inisyalizèd ak valè an te pase-a.
Lè sa a, ou vle asire w ke ou mete nan kèk sòt de nòt ki di
moun kap rele a dwe libere memwa a retounen.
Nan fason sa a, si yon moun tout tan ale epi li sèvi ak sa fonksyon,
yo konnen tou sa yo gen pou retounen nan sa fonksyon
nan kèk pwen pral bezwen dwe libere.
>> Nou asime ke tout bagay byen epi li bon isit la,
nou ka ale desann nan kòd nou yo ak ranplase tout nan liy sa yo isit la
ak apèl fonksyone bati ne nou an.
Se pou nou fè sa vrèman byen vit.
Pati nan yon sèl ke nou pa ap ale nan ranplase se nan pati sa a desann isit la
nan pati anba a kote nou aktyèlman WIRE moute nœuds yo nan pwen nan chak lòt,
paske nou pa ka fè nan fonksyon nou an.
Men, kite a fè rasin = build_node (7); ne * twa = build_node (3);
ne * sis = build_node (6); ne * nèf = build_node (9);.
Epi, koulye a, nou menm tou nou te vle ajoute nœuds pou -
ne * senk = build_node (5); ne * uit = build_node (8);
ak ki sa ki te ne lòt yo? Ann wè isit la. Nou te vle tou ajoute yon 2 -
ne * de = build_node (2);.
Byen. Nan pwen sa a, nou konnen ke nou te gen 7 an, 3 an, 9 la, ak 6 an
tout câblé moute kòmsadwa, men sa ki sou 5 an, 8 la, ak 2 a?
Pou kenbe tout bagay yo nan lòd ki apwopriye a,
nou konnen ke pitit dwa twa a se 6.
Se konsa, si nou pwal ajoute 5 an,
5 a tou ki dwe nan bò dwat la pyebwa ki fè moun ki 3 se rasin lan,
Se konsa 5 ki dwe kòm timoun nan gòch nan 6.
Nou ka fè sa a lè li di, sis -> left_child = senk;
ak Lè sa a, 8 la ki dwe kòm timoun nan bò gòch nan 9, se konsa nèf -> left_child = uit;
ak Lè sa a, 2 a se timoun nan bò gòch nan 3, konsa nou ka fè sa moute isit la - ou -> left_child = de;.
Si ou pa t 'byen swiv ansanm ak sa, mwen sijere ou rale yo mete deyò tèt ou.
>> Byen. Se pou nou sove sa a. Ann al deyò epi yo asire w ke li compiles,
ak Lè sa a, nou ka ajoute nan konprann apèl nou yo.
Sanble tout bagay toujou compiles.
Ann al nan epi ajoute nan kèk gen apèl.
Yon fwa ankò, mwen pral fè yon ti kras nan kopi ak keratin.
Koulye a, kite l 'nan rechèch pou 5 8,, epi 2. Byen.
Se pou nou asire w ke sa a tout moun sanble bon toujou. Gwo! Save ak kite fimen.
Koulye a, kite a fè, konpile, ak kounye a kite a kouri.
Soti nan rezilta yo, li sanble tout bagay ap travay jis bèl ak byen.
Gwo! Se konsa, kounye a nou te gen konprann nou fonksyon ekri.
Kite yo deplase sou yo ak sou kòmanse travay sou ki jan yo insert nœuds nan pye bwa a
depi, jan n ap fè li kounye a, bagay yo pa trè bèl.
>> Si nou tounen nan spesifikasyon la,
li mande nou yo ekri yon fonksyon rele insert - ankò, retounen yon bouleen
pou si ou pa nou te ka aktyèlman insert ne la nan pye bwa a -
ak Lè sa a, se valè a insert nan pye bwa a ki espesifye kòm
agiman la sèlman nan fonksyon insert nou an.
Nou pral retounen vre si nou te ka tout bon insert ne valè a ki gen nan pyebwa a,
ki vle di ke nou menm, yon sèl, te gen ase memwa,
ak Lè sa a, de, ki ne pa t 'deja egziste nan pyebwa a depi -
sonje, nou pa yo ale nan yo gen valè kopi nan pye bwa a, jis fè bagay sa yo ki senp.
Byen. Retounen nan kòd la.
Louvri li. Zoom nan yon ti jan, lè sa a desann.
Ann mete fonksyon an insert dwa pi wo a konprann yo.
Yon fwa ankò, li pral yo dwe rele bouleen insert (Int valè).
Ba li yon ti kras pi plis espas, ak lè sa a, kòm yon default,
kite a mete an retou fo nan fen an trè.
Koulye a, desann nan pati anba a, se pou yo ale pi devan ak olye pou yo manyèlman bati nœuds yo
nan prensipal tèt nou ak fil elektrik yo moute nan pwen nan chak lòt tankou n ap fè,
nou pral konte sou fonksyon insert nou fè sa.
Nou pa pral konte sou fonksyon insert nou yo bati pyebwa a tout antye nan grafouyen jis ankò,
men pito nou pral debarase m de liy sa yo - we'll kòmantè soti liy sa yo -
ki bati nœuds yo 5, 8, ak 2.
Ak olye de sa, nou pral insert apèl fonksyone insert nou
asire w ke ki aktyèlman ap travay.
Isit la nou ale.
>> Koulye a, nou te kòmante soti liy sa yo.
Nou sèlman gen 7, 3, 9, ak 6 nan pyebwa nou an nan pwen sa a.
Pou fè sèten ke sa a se tout travay,
nou ka rale soti, fè pyebwa binè nou an,
kouri li, epi nou ka wè ke gen se kounye a di nou ke nou se totalman dwa -
5, 8, ak 2 yo pa nan pyebwa sa a.
Ale tounen nan kòd la,
ak ki jan nou pral insert?
Sonje sa nou te fè sa lè nou te aktyèlman mete 5, 8, ak 2 deja a.
Nou jwe jwèt sa Plinko kote nou te kòmanse nan rasin la,
desann yon sèl nan pyebwa pa youn pa youn
jiskaske nou jwenn diferans ki apwopriye a,
ak Lè sa a, nou branche nan ne an nan plas la ki apwopriye yo.
Nou pwal fè menm bagay la.
Sa a se fondamantalman tankou ekri kòd la ke nou te itilize nan gen nan fonksyon
jwenn plas nan kote ne a ta dwe,
ak Lè sa a, nou ap jis pral insert ne an dwa a.
Se pou nou kòmanse fè sa.
>> Se konsa, nou gen yon ne * akt = rasin; nou ap jis pral swiv gen kòd sa a
jiskaske nou jwenn ke li pa byen travay pou nou.
Nou pral yo ale nan pye bwa a pandan y ap eleman aktyèl la se pa nil,
epi si nou jwenn valè ki akt a ki egal a valè a ke nou ap eseye insert -
byen, sa a se youn nan ka yo nan ki nou pa t 'kapab aktyèlman insert ne la
nan pye bwa a paske sa vle di nou gen yon valè kopi.
Isit la nou ap aktyèlman pral retounen fo.
Koulye a, lòt bagay si valè akt a se mwens pase valè li,
kounye a nou konnen ke nou deplase a dwat a
paske valè a ki dwe nan mwatye nan dwa nan pyebwa a akt.
Sinon, nou pwal pou yo avanse pou bò gòch li.
Sa a se fondamantalman konprann nou fonksyone ki la a.
>> Nan pwen sa a, yon fwa nou te ranpli sa a pandan y ap riban,
konsèy akt nou yo pral montre nil
si fonksyon an pa te deja retounen.
Nou ap Se poutèt sa gen akt nan plas la kote nou vle insert ne nan nouvo.
Ki sa ki rete yo dwe fè se konstwi aktyèlman ne nan nouvo,
ki nou ka fè bèl fasil.
Nou ka sèvi avèk fonksyon super-sou la men nou ne bati,
ak yon bagay ke nou pa t 'fè pi bonè -
nou jis kalite te pran pou yo akòde men kounye a nou pwal fè jis asire ou ke -
nou pral teste a asire w ke valè a tounen pa ne nouvo te aktyèlman
pa nil, paske nou pa vle kòmanse aksè ki memwa si li se nil.
Nou ka fè tès a asire w ke ne nouvo se pa egal a nil.
Oswa olye de sa, nou ka jis wè si li aktyèlman se nil,
ak si li se nil, lè sa a nou ka jis retounen fo bonè.
>> Nan pwen sa a, nou gen nan pwent fil nouvo ne nan plas ki apwopriye li yo nan pyebwa sa a.
Si nou gade tounen nan prensipal ak ki kote nou te aktyèlman fil elektrik nan valè anvan,
nou wè ke fason an nou te fè li lè nou te vle mete 3 nan pye bwa a
te nou jwenn aksè timoun nan gòch nan rasin.
Lè nou mete 9 nan pye bwa a, nou te gen gen aksè a timoun nan dwa a rasin lan.
Nou te gen gen yon konsèy bay paran an yo nan lòd yo mete yon valè nouvo nan pyebwa sa a.
Defile tounen jiska insert, ki pa a pral byen travay isit la
paske nou pa gen yon konsèy paran yo.
Ki sa nou vle pou kapab fè se, nan pwen sa a,
tcheke valè paran an ak wè - byen, bondye papa,
si valè paran an a se mwens pase valè aktyèl la,
Lè sa a, dwa timoun paran an ta dwe ne nan nouvo;
otreman, bò gòch pitit paran an ta dwe ne nan nouvo.
Men, nou pa gen sa a konsèy paran byen ankò.
>> Yo nan lòd yo jwenn li, n ap aktyèlman pral fè yo swiv li kòm nou ale nan pye bwa a
epi jwenn plas ki apwopriye a nan riban nou pi wo a.
Nou ka fè sa pa defile tounen moute nan tèt la nan fonksyon insert nou
ak swiv yon lòt varyab konsèy rele paran an.
Nou pral mete l 'egal a nil okòmansman,
ak Lè sa a, chak fwa nou ale nan pye bwa a,
nou pwal mete konsèy paran an matche ak konsèy aktyèl la.
Fikse paran egal a akt.
Fason sa a, chak fwa nou ale nan,
nou pwal asire ke kòm konsèy aktyèl la vin enkremante
konsèy paran an swiv li - jis yon nivo pi wo pase konsèy aktyèl la nan pye bwa an.
Ke tout sanble trè bon.
>> Mwen panse ke bagay la yon sèl ke nou pral vle ajiste sa a bati ne retounen nil.
Yo nan lòd jwenn bati ne aktyèlman avèk siksè retounen nil,
nou pral oblije modifye ki kòd,
paske isit la, nou pa janm fè tès a asire w ke malok tounen yon konsèy ki valid.
Se konsa, si (n = nil!), Lè sa a -
si malok tounen yon konsèy ki valab, Lè sa a, nou pral inisyalize li;
otreman, nou pral jis retounen ak ki pral fini retounen nil pou nou.
Koulye a, tout sanble trè bon. Se pou nou asire ou ke sa sa a aktyèlman compiles.
Fè pyebwa binè, ak oh, nou te gen kèk bagay pral sou isit la.
>> Nou gen yon deklarasyon enplisit nan fonksyon bati ne.
Yon fwa ankò, ak sa yo konpilateur, nou pwal kòmanse nan tèt la.
Ki sa ki ki dwe vle di se ke m ap rele bati ne mwen anvan m 'te aktyèlman te deklare li.
Se pou nou tounen nan kòd la reyèlman byen vit.
Scroll down, ak asire w ase, se fonksyon insert mwen te deklare
pi wo a fonksyon an ne bati,
men mwen m 'ap eseye sèvi ak bati ne anndan insert.
Mwen pral ale nan ak kopi - ak Lè sa a, keratin ne wout la fonksyon bati isit la nan tèt la.
Nan fason sa a, èspere ke sa pwal mache. Se pou nou bay sa a yon lòt ale.
Kounye a li tout compiles. Tout se yon bon bagay.
>> Men, nan pwen sa a, nou pa gen aktyèlman rele fonksyon insert nou an.
Nou jis konnen ke li compiles, se konsa kite yo ale nan epi li mete kèk apèl pous
Se pou nou fè sa nan yon fonksyon prensipal nou an.
Isit la, nou kòmante soti 5, 8, ak 2,
ak Lè sa a, nou pa t 'WIRE yo moute desann isit la.
Se pou nou fè kèk apèl insert,
e kite yo sèvi tou ak kalite a menm nan bagay ke nou itilize
lè nou te fè sa yo apèl printf a asire w ke tout bagay t 'jwenn eleman byen.
Mwen pral voye yon kopi bay ak keratin,
ak olye pou yo gen nou ap pral fè insert.
Ak olye pou yo 6 10,, ak 1, nou pwal sèvi ak 5, 8, ak 2.
Sa a ta dwe èspere ke insert 5, 8, ak 2 nan pyebwa sa a.
Sanble tout. Tout se yon bon bagay. Koulye a, nou pral aktyèlman kouri pwogram nou an.
>> Tout tounen fo.
Se konsa,, 5, 8, ak 2 pa t 'ale, epi li sanble pa gen t' kapab jwenn yo pou yo swa.
Kisa ki ale sou? Se pou nou rale soti.
Pwoblèm nan premye te ke insert te sanble ke yo retounen fo,
ak li sanble sa a, se paske nou te kite nan rele retounen nou fo,
epi nou pa janm aktyèlman tounen vre.
Nou ka mete ki moute.
Pwoblèm nan dezyèm se, kounye a menm si nou fè - sove sa a, kite sa a,
kouri fè ankò, te li konpile, lè sa a kouri li -
nou wè ke yon lòt bagay ki te pase isit la.
5 nan, 8, ak 2 yo te toujou pa janm yo te jwenn nan pyebwa sa a.
Se konsa, sa k ap pase sou?
>> Se pou nou pran yon gade nan sa a nan kòd la.
Se pou nou wè si nou ka figi sa a soti.
Nou kòmanse avèk paran an pa ke yo te nil.
Nou mete konsèy aktyèl la egal a konsèy nan rasin,
e nou pral nan travay wout nou desann nan pyebwa sa a.
Si ne aktyèl la se pa nil, lè sa a nou konnen ke nou ka deplase desann yon ti jan.
Nou mete konsèy paran nou an yo dwe egal a konsèy aktyèl la,
tcheke valè a - si valè yo se menm bagay la nou tounen fo.
Si valè yo yo gen mwens nou demenaje ale rete nan dwa a;
otreman, nou demenaje ale rete nan bò gòch li.
Lè sa a, nou bati yon ne. Mwen pral rale nan yon ti jan.
Ak isit la, nou pwal pou yo eseye WIRE moute valè yo yo dwe menm bagay la.
Kisa ki ale sou? Ann wè si posib Valgrind ka ban nou yon allusion.
>> Mwen renmen itilize Valgrind jis paske Valgrind vrèman byen vit kouri
epi li di ou si gen nenpòt ki erè memwa.
Lè nou kouri Valgrind sou kòd la,
kòm ou kapab wè dwa frape here--Valgrind./binary_tree--and antre.
Ou wè ke nou pa t 'gen nenpòt erè memwa, se konsa li sanble tankou tout bagay nan oke byen lwen tèlman.
Nou fè gen kèk fwit memwa, ki nou konnen, paske nou pa
pase libere nenpòt nan nœuds nou an.
Ann eseye kouri gdb yo wè sa ki la aktyèlman pral sou.
Nou pral fè gdb. / Binary_tree. Li demare moute jis anfòm.
Se pou nou mete yon pwen repo nan sipleman.
Se pou nou kouri.
Li sanble ke nou pa janm aktyèlman rele insert.
Li sanble ke pwoblèm nan te jis ke lè mwen chanje desann isit la nan prensipal -
tout moun sa yo apèl printf soti nan gen -
Mwen pa janm aktyèlman chanje sa yo yo rele insert.
Koulye a, kite a bay li yon eseye. Se pou nou konpile.
Tout sanble bon la. Koulye a, kite nan eseye kouri li, wè sa ki rive.
Oke! Tout sanble trè bon la.
>> Bagay la final bezwen panse osijè de se, èske genyen kèk ka kwen sa a insert?
Epi li sanble ke, byen, ka a kwen youn ki se toujou enteresan panse osijè de
se, ki sa ki pral rive si pyebwa ou ki vid e san ou rele sa a fonksyon insert?
Èske li travay? Oke, kite la bay li yon eseye.
- Binary_tree c. -
Nan fason nou ap ale nan teste sa a se, nou pwal desann ale nan fonksyon prensipal nou an,
ak olye ke fil elektrik sa yo nœuds moute tankou sa a,
Nou jis ap pral fè kòmantè soti bagay la an antye,
ak olye pou yo fil elektrik moute nœuds yo tèt nou,
nou ka aktyèlman jis ale pi devan epi efase tout bagay sa yo.
Nou pwal fè tout bagay yon apèl insert.
Se konsa, kite a fè - olye pou yo 5, 8, ak 2, nou ap ale nan insert 7, 3, ak 9.
Lè sa a, nou pral vle tou insert 6 kòm byen.
Sove. Kite fimen. Fè pyebwa binè.
Li tout compiles.
Nou ka jis kouri li kòm se ak wè sa ki rive,
men li la tou pral fè vrèman enpòtan a asire w ke
nou pa gen nenpòt ki erè memwa,
depi sa a se youn nan ka kwen nou an ke nou konnen sou yo.
>> Se pou nou asire w ke li travay byen anba Valgrind,
ki n ap fè pa jis kouri Valgrind. / binary_tree.
Li sanble ke nou menm se gen yon sèl erè soti nan yon kontèks -
nou gen sa a fòt segmentation.
Ki sa ki te pase?
Valgrind aktyèlman di nou ki kote li ye.
Rale soti yon ti jan.
Li sanble tankou li k ap pase nan fonksyon insert nou an,
kote nou gen yon Read envalid nan gwosè 4 nan insert, liy 60.
Ann al retounen lakay yo epi wè sa k ap pase sou isit la.
Rale soti vrèman rapid.
Mwen vle asire w ke li pa ale nan kwen an nan ekran an pou nou ka wè tout bagay.
Rale ke nan yon ti jan. Byen.
Scroll down, ak pwoblèm nan se dwa isit la.
Kisa k ap pase si nou jwenn desann ak ne nou an ki ajou a deja nil,
ne paran nou an se nil, kidonk si nou gade moute nan anpil tèt, isit la nan dwa -
si sa a riban pandan y ap pa janm aktyèlman ègzekutra
paske valè aktyèl nou an, se nil - rasin nou an, se nil konsa akt se nil -
Lè sa a, paran nou an pa janm vin mete akt oswa nan yon valè ki valab,
se konsa, paran ap tou ap nil.
Nou bezwen sonje yo tcheke pou ki
pa tan an nou jwenn desann isit la, epi nou kòmanse gen aksè nan valè paran an.
Se konsa, sa k ap pase? Byen, si paran an se nil -
si (paran == nil) - Lè sa a, nou konnen ke
gen pa dwe anyen nan pyebwa sa a.
Nou dwe eseye insert li nan rasin lan.
Nou ka fè sa pa jis mete rasin lan egal a ne a nouvo.
Lè sa a, nan pwen sa a, nou pa aktyèlman vle ale nan tout bagay sa yo ak lòt.
Olye de sa, dwa isit la, nou ka fè swa yon lòt bagay-si-lòt bagay,
oswa nou te ka konbine tout bagay moute isit la nan yon lòt bagay,
men isit la nou pral jis itilize lòt moun, e fè li fason sa.
Koulye a, nou ap ale nan teste a asire w ke paran nou an se pa nil
anvan Lè sa a, aktyèlman ap eseye gen aksè a jaden li yo.
Sa a ap ede nou evite fay la segmentation.
Se konsa, nou kite fimen, rale soti, konpile, kouri.
>> Pa gen erè, men nou toujou gen yon pakèt moun sou fwit memwa
paske nou pa t 'libere nenpòt nan nœuds nou an.
Men, si n 'al jwenn moute isit la epi nou gade kopi enprime nou an,
nou wè ke, byen, sanble tout mete anndan nou yo te retounen vre, ki se bon.
Mete anndan yo, yo tout verite a,
ak Lè sa a, konprann ki apwopriye apèl yo se verite tou.
>> Bon travay! Li sanble ke nou te avèk siksè ekri insert.
Sa a tout nou gen pou Specification Set Pwoblèm semèn sa a la.
Youn nan defi plezi panse sou ki jan pou ou ta aktyèlman ale nan
ak gratis nan tout nœuds yo nan pyebwa sa a.
Nou ka fè sa yon nimewo nan diferan fason,
men m ap kite sa jiska ou eksperyans,
epi kòm yon defi plezi, eseye, epi fè sèten ke ou ka asire ou ke
ki rapò sa a Valgrind retounen pa gen okenn erè e pa gen fwit.
>> Bon chans sou Huffman seri semèn sa a nan pwoblèm kodaj,
epi n ap wè ou semèn pwochen!
[CS50.TV]