1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Kafli 7] [Minna Comfortable]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Harvard University]

3
00:00:04,890 --> 00:00:07,000
[Þetta er CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Velkomin á kafla 7.

5
00:00:09,080 --> 00:00:11,330
Þökk sé fellibyl Sandy,

6
00:00:11,330 --> 00:00:13,440
í stað þess að hafa venjulegan kafla þessa viku,

7
00:00:13,440 --> 00:00:17,650
við erum að gera þetta ganga í gegnum, í gegnum hluta af spurningum.

8
00:00:17,650 --> 00:00:22,830
Ég ætla að fylgja ásamt Vandamál Set 6 texta,

9
00:00:22,830 --> 00:00:25,650
og fara í gegnum allar spurninga í

10
00:00:25,650 --> 00:00:27,770
Hluti af spurningum kafla.

11
00:00:27,770 --> 00:00:30,940
Ef það eru einhverjar spurningar,

12
00:00:30,940 --> 00:00:32,960
vinsamlegast senda þetta á CS50 ræða.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Við skulum byrja.

14
00:00:35,480 --> 00:00:40,780
Núna er ég að horfa á síðu 3 af Set Vandamál Specification.

15
00:00:40,780 --> 00:00:44,110
Við ætlum fyrst að byrja að tala um tvöfaldur tré

16
00:00:44,110 --> 00:00:47,850
síðan þeir hafa a einhver fjöldi af máli við vandamál setja þessa viku -

17
00:00:47,850 --> 00:00:49,950
að Huffman Tree kóðun.

18
00:00:49,950 --> 00:00:55,000
Einn af fyrstu gögn uppbygging við ræddum um á CS50 var array.

19
00:00:55,000 --> 00:01:00,170
Mundu að fylki er röð atriða -

20
00:01:00,170 --> 00:01:04,019
öll af sömu tegund - geymd við hliðina á hvor öðru í minni.

21
00:01:04,019 --> 00:01:14,420
Ef ég er með heiltölu fylki sem ég get teiknað nota box-númer-heiltölur stíl -

22
00:01:14,420 --> 00:01:20,290
Við skulum segja að ég hef 5 í fyrsta reitinn, ég 7 í öðrum,

23
00:01:20,290 --> 00:01:27,760
þá hef ég 8, 10 og 20 í síðasta reitinn.

24
00:01:27,760 --> 00:01:33,000
Mundu, tveir mjög góðir hlutir um þetta fylki

25
00:01:33,000 --> 00:01:38,800
er að við höfum þessa föstu-tíma aðgang að tilteknum þáttur

26
00:01:38,800 --> 00:01:40,500
 í fylkinu ef við vitum vísitölu.

27
00:01:40,500 --> 00:01:44,670
Til dæmis, ef ég vil grípa þriðja þáttur í fylkinu -

28
00:01:44,670 --> 00:01:47,870
á vísitölu 2 með núll-undirstaða flokkun kerfi okkar -

29
00:01:47,870 --> 00:01:52,220
Ég bókstaflega bara að gera einfalda stærðfræði útreikninga,

30
00:01:52,220 --> 00:01:56,170
step í þeirri stöðu í fylking,

31
00:01:56,170 --> 00:01:57,840
draga út 8 sem er geymd þar,

32
00:01:57,840 --> 00:01:59,260
og ég er gott að fara.

33
00:01:59,260 --> 00:02:03,350
>> Einn af the slæmur hlutur óður í this array - sem við ræddum um

34
00:02:03,350 --> 00:02:05,010
þegar við ræddum tengd listum -

35
00:02:05,010 --> 00:02:09,120
er að ef ég vil setja stak í þessu fylki,

36
00:02:09,120 --> 00:02:11,090
Ég ætla að gera nokkrar að færast.

37
00:02:11,090 --> 00:02:12,940
Til dæmis, þetta fylki hérna

38
00:02:12,940 --> 00:02:16,850
er raðað röð - raðað í hækkandi röð -

39
00:02:16,850 --> 00:02:19,440
5, svo 7, svo 8, síðan 10, og svo 20 -

40
00:02:19,440 --> 00:02:23,100
en ef ég vil að setja númer 9 í þessu fylki,

41
00:02:23,100 --> 00:02:27,460
Ég ætla að hafa til að skipta sumir af þeim þáttum til að gera pláss.

42
00:02:27,460 --> 00:02:30,440
Við getum draga þetta út hér.

43
00:02:30,440 --> 00:02:35,650
Ég ætla að hafa til að færa 5, 7, og þá 8;

44
00:02:35,650 --> 00:02:38,720
búa til gjá þar sem ég get sett 9,

45
00:02:38,720 --> 00:02:45,910
og þá 10 og 20 getur farið til hægri á 9.

46
00:02:45,910 --> 00:02:49,450
Þetta er góður af sársauka vegna þess að í versta falli -

47
00:02:49,450 --> 00:02:54,350
þegar við erum að þurfa að setja annað hvort í upphafi eða við lok

48
00:02:54,350 --> 00:02:56,040
um fjölda, eftir því hvernig við erum að breytast -

49
00:02:56,040 --> 00:02:58,850
við might endir upp að þurfa að skipta öllum þeim þáttum

50
00:02:58,850 --> 00:03:00,750
sem við erum nú að geyma í fylki.

51
00:03:00,750 --> 00:03:03,810
>> Svo, hvað var hátt í kringum þetta?

52
00:03:03,810 --> 00:03:09,260
Leiðin í kringum þetta var að fara að tengd-lista aðferð okkar þar -

53
00:03:09,260 --> 00:03:19,820
í stað þess að geyma þá þætti 5, 7, 8, 10 og 20 alla hliðina á hvor aðra í minni -

54
00:03:19,820 --> 00:03:25,630
hvað við staðinn gerði var geymt þá eins konar hvar við vildum að geyma þá

55
00:03:25,630 --> 00:03:32,470
í þessum ítengdu lista hnúður sem ég er að teikna út hér, eins konar tilfallandi.

56
00:03:32,470 --> 00:03:42,060
Og þá erum tengd þá saman með þessum næsta ábendingum.

57
00:03:42,060 --> 00:03:44,370
Ég get haft músina frá 5 til 7,

58
00:03:44,370 --> 00:03:46,420
bendi frá 7 til 8,

59
00:03:46,420 --> 00:03:47,770
bendi frá 8 til 10,

60
00:03:47,770 --> 00:03:51,220
og að lokum, bendi frá 10 til 20,

61
00:03:51,220 --> 00:03:54,880
og þá a null músina á 20 gefur til kynna að það er ekkert eftir.

62
00:03:54,880 --> 00:03:59,690
Málamiðlun sem við höfum hér

63
00:03:59,690 --> 00:04:05,360
er það nú ef við viljum setja númer 9 í raðaða listanum okkar,

64
00:04:05,360 --> 00:04:08,270
allt sem við þurfum að gera er að búa til nýjan hnút með 9,

65
00:04:08,270 --> 00:04:12,290
vír það upp til að benda á viðeigandi stað,

66
00:04:12,290 --> 00:04:20,630
og þá með tilvísun til-vír 8 að benda niður í 9.

67
00:04:20,630 --> 00:04:25,660
Það er nokkuð hratt, miðað við vitum nákvæmlega hvar við viljum að setja 9.

68
00:04:25,660 --> 00:04:32,610
En málamiðlun í skiptum fyrir þessu er að við höfum nú misst föstu-tíma aðgang

69
00:04:32,610 --> 00:04:36,230
einhverju tilteknu frumefni í gögn uppbygging okkar.

70
00:04:36,230 --> 00:04:40,950
Til dæmis, ef ég vil að finna fjórða þáttur í tengda listanum,

71
00:04:40,950 --> 00:04:43,510
Ég ætla að hafa til að byrja í upphafi á listanum

72
00:04:43,510 --> 00:04:48,930
og vinna leið minni í gegnum talningu hnút-með-hnút þangað til ég finna fjórða einn.

73
00:04:48,930 --> 00:04:55,870
>> Í því skyni að fá betri aðgang árangur en í tengda listanum -

74
00:04:55,870 --> 00:04:59,360
en einnig halda sumir af the hagur sem við höfðum

75
00:04:59,360 --> 00:05:01,800
hvað er sett í tíma úr tengda listanum -

76
00:05:01,800 --> 00:05:05,750
tvöfaldur tré er að fara að þurfa að nota aðeins meira minni.

77
00:05:05,750 --> 00:05:11,460
Einkum, í stað þess bara að hafa einn músina í tvíundartrés hnút -

78
00:05:11,460 --> 00:05:13,350
eins og tengda-lista hnút gerir -

79
00:05:13,350 --> 00:05:16,950
við erum að fara að bæta við annarri bendi til tvöfaldur tré hnút.

80
00:05:16,950 --> 00:05:19,950
Frekar en bara að hafa eitt bendi á næsta þátt,

81
00:05:19,950 --> 00:05:24,420
við erum að fara að hafa músina til vinstri barns og rétt barns.

82
00:05:24,420 --> 00:05:26,560
>> Við skulum teikna mynd til að sjá hvað það raunverulega lítur út.

83
00:05:26,560 --> 00:05:31,350
Aftur, ég ætla að nota þessa reiti og örvar.

84
00:05:31,350 --> 00:05:37,150
A tvöfaldur tré hnút verður að byrja leikinn með bara einfaldur kassi.

85
00:05:37,150 --> 00:05:40,940
Það er að fara að hafa pláss fyrir gildi,

86
00:05:40,940 --> 00:05:47,280
og þá er líka að fara að hafa pláss fyrir vinstra barn og hægra barn.

87
00:05:47,280 --> 00:05:49,280
Ég ætla að merkja þau hér.

88
00:05:49,280 --> 00:05:57,560
Við ætlum að hafa vinstri barnið, og þá ætlum við að hafa rétt barn.

89
00:05:57,560 --> 00:05:59,920
Það eru til margar mismunandi leiðir til að gera þetta.

90
00:05:59,920 --> 00:06:02,050
Stundum um pláss og þægindi,

91
00:06:02,050 --> 00:06:06,460
Ég í raun draga það eins og ég er að gera hér á botn

92
00:06:06,460 --> 00:06:10,910
þar sem ég ætla að hafa gildi efst,

93
00:06:10,910 --> 00:06:14,060
og svo rétt barnið á neðst til hægri,

94
00:06:14,060 --> 00:06:16,060
og vinstri barn á botn-vinstri.

95
00:06:16,060 --> 00:06:20,250
Fara aftur í þessum efstu myndinni,

96
00:06:20,250 --> 00:06:22,560
við höfum gildi á the mjög toppur,

97
00:06:22,560 --> 00:06:25,560
þá höfum við vinstri-barn músina, og þá höfum við rétt barns músina.

98
00:06:25,560 --> 00:06:30,110
>> Í Set Vandamál við notkun lyfsins,

99
00:06:30,110 --> 00:06:33,110
við tölum um að teikna hnút sem hefur gildi 7,

100
00:06:33,110 --> 00:06:39,750
og þá vinstri-barn músina sem er núll, og réttur barns músina sem er núll.

101
00:06:39,750 --> 00:06:46,040
Við getum annað hvort skrifað höfuðborg NULL í rými fyrir

102
00:06:46,040 --> 00:06:51,610
bæði vinstri barn og rétt barnið, eða við getum draga þessa ská skástrik

103
00:06:51,610 --> 00:06:53,750
gegnum hvert reitina til að benda að það er núll.

104
00:06:53,750 --> 00:06:57,560
Ég ætla að gera það bara vegna þess að það er einfaldara.

105
00:06:57,560 --> 00:07:03,700
Það sem þú sérð hér eru tvær leiðir diagramming mjög einfalt tvíundartré hnút

106
00:07:03,700 --> 00:07:07,960
þar sem við höfum gildið 7 og núll ábendingum barn.

107
00:07:07,960 --> 00:07:15,220
>> Seinni hluti af viðræðum skilgreining okkar um hvernig við tengd listum -

108
00:07:15,220 --> 00:07:18,270
Mundu, við höfðum aðeins að halda á fyrstu frumefni í lista

109
00:07:18,270 --> 00:07:20,270
að muna alla lista -

110
00:07:20,270 --> 00:07:26,140
og sömuleiðis, með tvöfaldur tré, höfum við aðeins að halda eitt bendi á tré

111
00:07:26,140 --> 00:07:31,120
í því skyni að hafa stjórn á öllu gögn uppbygging.

112
00:07:31,120 --> 00:07:36,150
Þetta sérstaka þáttur í tré er kallað rót hnút í trénu.

113
00:07:36,150 --> 00:07:43,360
Til dæmis, ef einn hnút - þessi hnútur inniheldur gildið 7

114
00:07:43,360 --> 00:07:45,500
með núll vinstri-og hægri-barn ábendingum -

115
00:07:45,500 --> 00:07:47,360
voru aðeins gildi í trénu okkar,

116
00:07:47,360 --> 00:07:50,390
þá myndi þetta vera rót hnút okkar.

117
00:07:50,390 --> 00:07:52,240
Það er mjög upphafi tré okkar.

118
00:07:52,240 --> 00:07:58,530
Við sjáum þetta aðeins betur þegar við byrjum að bæta fleiri hnúta til tré okkar.

119
00:07:58,530 --> 00:08:01,510
Leyfðu mér að draga upp nýja síðu.

120
00:08:01,510 --> 00:08:05,000
>> Nú ætlum við að teikna tré sem hefur 7 í rót,

121
00:08:05,000 --> 00:08:10,920
og 3 inni vinstri barnsins og 9 inni í hægri barnsins.

122
00:08:10,920 --> 00:08:13,500
Aftur, þetta er frekar einfalt.

123
00:08:13,500 --> 00:08:26,510
Við höfum fengið 7, draga hnút fyrir 3, hnút í 9,

124
00:08:26,510 --> 00:08:32,150
og ég ætla að láta vinstri-barns músina yfir 7 til að benda á hnút sem inniheldur 3,

125
00:08:32,150 --> 00:08:37,850
og rétt barns músina í hnút sem inniheldur 7 til hnúturinn inniheldur 9.

126
00:08:37,850 --> 00:08:42,419
Nú, síðan 3 og 9 hafa engar börn,

127
00:08:42,419 --> 00:08:48,500
við erum að fara að setja alla ábendingum barnið þeirra til að vera núll.

128
00:08:48,500 --> 00:08:56,060
Hér rót trésins okkar samsvarar hnúturinn inniheldur númer 7.

129
00:08:56,060 --> 00:09:02,440
Þú getur séð að ef allt sem við höfum er bendi til að rót hnút,

130
00:09:02,440 --> 00:09:07,330
við getum þá gengið í gegnum tré okkar og aðgang bæði barn hnúður -

131
00:09:07,330 --> 00:09:10,630
bæði 3 og 9.

132
00:09:10,630 --> 00:09:14,820
Engin þörf á að viðhalda ábendingum til sérhver einn hnút á trénu.

133
00:09:14,820 --> 00:09:22,080
Alright. Nú ætlum við að bæta við öðru hnút á þetta línurit.

134
00:09:22,080 --> 00:09:25,370
Við ætlum að bæta við hnút inniheldur 6,

135
00:09:25,370 --> 00:09:34,140
og við erum að fara að bæta þetta sem rétt barnsins á hnút inniheldur 3.

136
00:09:34,140 --> 00:09:41,850
Til að gera það, ég ætla að eyða að núll músina í 3-hnút

137
00:09:41,850 --> 00:09:47,750
og vír það upp til að benda á hnút inniheldur 6. Alright.

138
00:09:47,750 --> 00:09:53,800
>> Á þessum tímapunkti, við skulum fara yfir smá hugtakanotkun.

139
00:09:53,800 --> 00:09:58,230
Til að byrja, Ástæðan fyrir því að þetta er kallað tvöfaldur tré einkum

140
00:09:58,230 --> 00:10:00,460
er að það hefur tvö börn ábendingum.

141
00:10:00,460 --> 00:10:06,020
Það eru aðrar tegundir af trjám sem hafa fleiri barn ábendingum.

142
00:10:06,020 --> 00:10:10,930
Sérstaklega fannst þér a 'reyna' í Set Vandamál 5.

143
00:10:10,930 --> 00:10:19,310
Þú munt taka eftir því að á að reyna, var að 27 mismunandi ábendingum til mismunandi börn -

144
00:10:19,310 --> 00:10:22,410
einn fyrir hverja 26 stafi í enska stafrófið,

145
00:10:22,410 --> 00:10:25,410
og þá 27 í úrfellingarmerki -

146
00:10:25,410 --> 00:10:28,900
svo, það er svipað og að gerð tré.

147
00:10:28,900 --> 00:10:34,070
En hér, þar sem tvöfaldur það, höfum við aðeins tvö börn ábendingum.

148
00:10:34,070 --> 00:10:37,880
>> Í viðbót við þetta rót hnút sem við ræddum um,

149
00:10:37,880 --> 00:10:41,470
við höfum einnig verið að kasta í kringum þetta hugtak "barn."

150
00:10:41,470 --> 00:10:44,470
Hvað þýðir það að einn hnút að vera barn annars hnút?

151
00:10:44,470 --> 00:10:54,060
Það þýðir bókstaflega að barnið tengipunktur er barn annars hnút

152
00:10:54,060 --> 00:10:58,760
Ef að annar hnútur er eitt af ábendingum barn hennar sett til að benda á það hnút.

153
00:10:58,760 --> 00:11:01,230
Til að setja þetta í fleiri steypu skilmálum,

154
00:11:01,230 --> 00:11:11,170
Ef 3 er bent á af einum barnið ábendingum um 7, þá er 3 barn 7.

155
00:11:11,170 --> 00:11:14,510
Ef við vorum að reikna út hvað börn 7 eru -

156
00:11:14,510 --> 00:11:18,510
Jæja, sjáum við að 7 hefur músina til 3 og bendi til 9

157
00:11:18,510 --> 00:11:22,190
svo 9 og 3 eru börn 7.

158
00:11:22,190 --> 00:11:26,650
Níu eru ekki börn því börn ábendingum þess eru null,

159
00:11:26,650 --> 00:11:30,940
og 3 hefur aðeins eitt barn, 6.

160
00:11:30,940 --> 00:11:37,430
Sex hefur líka ekki börn vegna þess að báðir ábendingum hennar eru null, sem við munum draga núna.

161
00:11:37,430 --> 00:11:45,010
>> Auk þess tölum við líka um foreldra tilteknum hnút,

162
00:11:45,010 --> 00:11:51,100
og þetta er, eins og þú vilt búast við, hið gagnstæða þessa barns lýsingu.

163
00:11:51,100 --> 00:11:58,620
Hver hnútur hefur einungis einn foreldri - í stað tveggja eins og þú might búast við mönnum.

164
00:11:58,620 --> 00:12:03,390
Til dæmis, foreldri 3 er 7.

165
00:12:03,390 --> 00:12:10,800
Foreldri 9 er 7, og foreldri 6 er 3. Ekki mikið að því.

166
00:12:10,800 --> 00:12:15,720
Við höfum einnig skilmála að tala um afa og barnabörn,

167
00:12:15,720 --> 00:12:18,210
og almennt við tölum um forfeður

168
00:12:18,210 --> 00:12:20,960
og afkomendur tiltekins hnút.

169
00:12:20,960 --> 00:12:25,710
Forfeður hnút - eða forfeður, heldur, á hnút -

170
00:12:25,710 --> 00:12:32,730
eru öllum hnúður sem liggja á leið frá rót til að hnút.

171
00:12:32,730 --> 00:12:36,640
Til dæmis, ef ég er að horfa á hnúturinn 6,

172
00:12:36,640 --> 00:12:46,430
þá forfeður eru að fara að vera bæði 3 og 7.

173
00:12:46,430 --> 00:12:55,310
Forfeður 9, td eru - ef ég er að horfa á hnúturinn 9 -

174
00:12:55,310 --> 00:12:59,990
þá er forfeður 9 bara 7.

175
00:12:59,990 --> 00:13:01,940
Og afkomendur eru einmitt hið gagnstæða.

176
00:13:01,940 --> 00:13:05,430
Ef ég vil horfa á alla niðjum 7,

177
00:13:05,430 --> 00:13:11,020
þá verð ég að líta á allar hnúður undir honum.

178
00:13:11,020 --> 00:13:16,950
Svo hef ég 3, 9 og 6 allt sem afkomendur 7.

179
00:13:16,950 --> 00:13:24,170
>> Endanleg orð sem við munum tala um er þetta hugmynd af því að vera systkini.

180
00:13:24,170 --> 00:13:27,980
Systkini - konar fylgja eftir á þessum fjölskyldu skilmálum -

181
00:13:27,980 --> 00:13:33,150
er hnúður sem eru á sama stigi í trénu.

182
00:13:33,150 --> 00:13:42,230
Svo eru 3 og 9 systkini vegna þess að þeir eru á sama stigi í trénu.

183
00:13:42,230 --> 00:13:46,190
Þeir báðir hafa sama foreldri, 7.

184
00:13:46,190 --> 00:13:51,400
The 6 hefur engin systkini því 9 er ekki börn.

185
00:13:51,400 --> 00:13:55,540
Og 7 hjartarskinn ekki hafa allir systkini því að það er rót trésins okkar,

186
00:13:55,540 --> 00:13:59,010
og það er bara alltaf 1 rót.

187
00:13:59,010 --> 00:14:02,260
Fyrir 7 hafa systkini þar þyrfti að vera hnútur yfir 7.

188
00:14:02,260 --> 00:14:07,480
Það þyrfti að vera foreldri 7, en þá 7 væri ekki lengur vera rót trésins.

189
00:14:07,480 --> 00:14:10,480
Þá að nýju foreldri 7 myndu einnig að eignast barn,

190
00:14:10,480 --> 00:14:16,480
og að barnið væri þá systkini af 7.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Flutningur á.

192
00:14:21,040 --> 00:14:24,930
Þegar við byrjuðum umræðu um tré tvöfaldur,

193
00:14:24,930 --> 00:14:28,790
Við ræddum um hvernig við ætluðum að nota þá til að

194
00:14:28,790 --> 00:14:32,800
fá forskot á bæði fylki og tengist listum.

195
00:14:32,800 --> 00:14:37,220
Og hvernig ætlum við að gera það er með þessa röðun eign.

196
00:14:37,220 --> 00:14:41,080
Við segjum að tvöfaldur tré er skipað, samkvæmt forskrift,

197
00:14:41,080 --> 00:14:45,740
ef fyrir hvern hnút í tré okkar, allir afkomendur hennar á vinstri -

198
00:14:45,740 --> 00:14:48,670
vinstri barnið og alla niðja Vinstrihreyfingin barnsins -

199
00:14:48,670 --> 00:14:54,510
hafa minni gildi, og öll hnúður á hægri -

200
00:14:54,510 --> 00:14:57,770
rétt barn og öllum niðjum Rétturinn barnsins -

201
00:14:57,770 --> 00:15:02,800
hafa hnúta meiri en verðmæti núverandi hnút sem við erum að horfa á.

202
00:15:02,800 --> 00:15:07,850
Bara fyrir einfaldleika, við erum að fara að gera ráð fyrir að það eru ekki allir afrit hnútar í trénu okkar.

203
00:15:07,850 --> 00:15:11,180
Til dæmis, í þessu tré sem við erum ekki að fara að takast á við að ræða

204
00:15:11,180 --> 00:15:13,680
þar sem við höfum gildið 7 á rót

205
00:15:13,680 --> 00:15:16,720
 og þá höfum við einnig gildi 7 annars staðar í trénu.

206
00:15:16,720 --> 00:15:24,390
Í þessu tilfelli, þú munt taka eftir því að þetta tré er örugglega pantað.

207
00:15:24,390 --> 00:15:26,510
Við höfum gildi 7 í rót.

208
00:15:26,510 --> 00:15:29,720
Allt til vinstri á 7 -

209
00:15:29,720 --> 00:15:35,310
ef ég losa allar þessar litlu merki hér -

210
00:15:35,310 --> 00:15:40,450
allt til vinstri 7 - 3 og 6 -

211
00:15:40,450 --> 00:15:49,410
þessi gildi eru bæði minni en 7 og allt til hægri - sem er bara þetta 9 -

212
00:15:49,410 --> 00:15:53,450
er meiri en 7.

213
00:15:53,450 --> 00:15:58,650
>> Þetta er ekki einungis pantað tré með þessi gildi,

214
00:15:58,650 --> 00:16:03,120
en við skulum draga nokkrar fleiri af þeim.

215
00:16:03,120 --> 00:16:05,030
Það er í raun allt fullt af leiðir að við getum gert þetta.

216
00:16:05,030 --> 00:16:09,380
Ég ætla að nota skammstöfun bara að halda hlutum einfalt þar -

217
00:16:09,380 --> 00:16:11,520
frekar en að draga út alla reiti-og-örvum -

218
00:16:11,520 --> 00:16:14,220
Ég ætla bara að fara að draga númer og bæta örvum tengja þá.

219
00:16:14,220 --> 00:16:22,920
Til að byrja, við verðum bara að skrifa upprunalega tré okkar aftur þar sem við áttum 7, og svo a 3,

220
00:16:22,920 --> 00:16:25,590
og svo 3 benti aftur til hægri til 6,

221
00:16:25,590 --> 00:16:30,890
og 7 var rétt barn sem var 9.

222
00:16:30,890 --> 00:16:33,860
Alright. Hvað er önnur leið sem við gætum skrifað þetta tré?

223
00:16:33,860 --> 00:16:38,800
Í stað þess að hafa 3 vera vinstri barn 7,

224
00:16:38,800 --> 00:16:41,360
við gætum líka hafa 6 vera vinstri barn 7,

225
00:16:41,360 --> 00:16:44,470
og 3 vera vinstri barn 6.

226
00:16:44,470 --> 00:16:48,520
Það myndi líta út eins og þessu tré hérna þar sem ég hef fengið 7,

227
00:16:48,520 --> 00:16:57,860
þá 6, svo 3, og 9 til hægri.

228
00:16:57,860 --> 00:17:01,490
Við einnig þurfa ekki að hafa 7 og hnút rót okkar.

229
00:17:01,490 --> 00:17:03,860
Við gætum líka hafa 6 og hnút rót okkar.

230
00:17:03,860 --> 00:17:06,470
Hvað myndi það líta út?

231
00:17:06,470 --> 00:17:09,230
Ef við erum að fara að halda þessari panta eign,

232
00:17:09,230 --> 00:17:12,970
allt til vinstri við 6 þarf að vera minna en það.

233
00:17:12,970 --> 00:17:16,540
Það er aðeins einn möguleiki og það er 3.

234
00:17:16,540 --> 00:17:19,869
En þá eins og hægri barn 6, höfum við tvo möguleika.

235
00:17:19,869 --> 00:17:25,380
Fyrst, gætum við hafa 7 og síðan 9,

236
00:17:25,380 --> 00:17:28,850
eða við getum draga það - eins og ég er að fara að gera hér -

237
00:17:28,850 --> 00:17:34,790
þar sem við höfum 9 og hægra barn á 6,

238
00:17:34,790 --> 00:17:39,050
og þá 7 og vinstri barn í 9.

239
00:17:39,050 --> 00:17:44,240
>> Nú eru 7 og 6 ekki aðeins mögulegt gildi fyrir rót.

240
00:17:44,240 --> 00:17:50,200
Við gætum líka hafa 3 verið á the rót.

241
00:17:50,200 --> 00:17:52,240
Hvað gerist ef 3 er í rót?

242
00:17:52,240 --> 00:17:54,390
Hér fá hlutina svolítið áhugavert.

243
00:17:54,390 --> 00:17:58,440
Þrír hjartarskinn ekki hafa allir gildi sem eru minni en það,

244
00:17:58,440 --> 00:18:02,070
svo að allt vinstra megin á trénu er bara að fara að vera null.

245
00:18:02,070 --> 00:18:03,230
Það er ekki að fara að vera neitt þarna.

246
00:18:03,230 --> 00:18:07,220
Til hægri, gætum við lista það í hækkandi röð.

247
00:18:07,220 --> 00:18:15,530
Við gætum hafa 3, þá 6, þá 7 og síðan 9.

248
00:18:15,530 --> 00:18:26,710
Eða getum við gert 3, þá 6, svo 9, þá 7.

249
00:18:26,710 --> 00:18:35,020
Eða getum við gert 3, þá 7, þá 6, þá 9.

250
00:18:35,020 --> 00:18:40,950
Eða, 3, 7 - í raun ekki, við getum ekki gert 7 aftur.

251
00:18:40,950 --> 00:18:43,330
Það er eitt okkar þar.

252
00:18:43,330 --> 00:18:54,710
Við getum gert 9, og síðan úr 9 við getum gert 6 og síðan 7.

253
00:18:54,710 --> 00:19:06,980
Eða getum við gert 3, þá 9, þá 7 og síðan 6.

254
00:19:06,980 --> 00:19:12,490
>> Eitt sem þarf að vekja athygli á hér er

255
00:19:12,490 --> 00:19:14,510
að þessi tré eru svolítið skrítið-útlit.

256
00:19:14,510 --> 00:19:17,840
Einkum, ef við skoðum 4 tré hægra megin -

257
00:19:17,840 --> 00:19:20,930
Ég umlykja þá, hér -

258
00:19:20,930 --> 00:19:28,410
Þessi tré líta næstum nákvæmlega eins og tengda lista.

259
00:19:28,410 --> 00:19:32,670
Hver hnútur hefur aðeins eitt barn,

260
00:19:32,670 --> 00:19:38,950
og svo við höfum ekkert af þessu tré-eins og uppbygging sem við sjáum til dæmis,

261
00:19:38,950 --> 00:19:44,720
 í einu einn tré hérna á neðst til vinstri.

262
00:19:44,720 --> 00:19:52,490
Þessi tré eru í raun kölluð úrkynjuðu tvöfaldur tré,

263
00:19:52,490 --> 00:19:54,170
og við munum tala um þetta meira í framtíðinni -

264
00:19:54,170 --> 00:19:56,730
sérstaklega ef þú ferð að taka önnur tölvunarfræði námskeið.

265
00:19:56,730 --> 00:19:59,670
Þessi tré eru degenerate.

266
00:19:59,670 --> 00:20:03,780
Þeir eru ekki mjög gagnlegur því, örugglega, þessi uppbygging lánar sig

267
00:20:03,780 --> 00:20:08,060
 að fletta sinnum svipuð í tengda listanum.

268
00:20:08,060 --> 00:20:13,050
Við fæ ekki að taka kostur af the auka minni - þetta auka músina -

269
00:20:13,050 --> 00:20:18,840
vegna uppbyggingu okkar að vera slæmt á þennan hátt.

270
00:20:18,840 --> 00:20:24,700
Frekar en að fara á og draga út tvöfaldur tré sem hafa 9 í rót,

271
00:20:24,700 --> 00:20:27,220
sem er það sem kemur síðas mál sem við hefðum,

272
00:20:27,220 --> 00:20:32,380
við erum í staðinn, á þessum tímapunkti, að fara að tala svolítið um þetta önnur orð

273
00:20:32,380 --> 00:20:36,150
sem við notum þegar að tala um tré sem er kölluð hæð.

274
00:20:36,150 --> 00:20:45,460
>> Hæð tré er fjarlægð frá rót til mest fjarlæg hnút,

275
00:20:45,460 --> 00:20:48,370
eða frekar fjölda hops sem þú þyrftir að gera til þess að

276
00:20:48,370 --> 00:20:53,750
byrja frá rót og svo endað á mest fjarlæg hnút í trénu.

277
00:20:53,750 --> 00:20:57,330
Ef við lítum á sumir af þessum trjám sem við höfum dregið hérna,

278
00:20:57,330 --> 00:21:07,870
sjáum við að ef við tökum þetta tré í efst í vinstra horninu og við byrjum á 3,

279
00:21:07,870 --> 00:21:14,510
þá verðum við að gera 1 step til fá til the 6, annað step til að komast að 7,

280
00:21:14,510 --> 00:21:20,560
og þriðja step til að komast að 9.

281
00:21:20,560 --> 00:21:26,120
Svo hæð þessu tré er 3.

282
00:21:26,120 --> 00:21:30,640
Við getum gert sömu æfingar fyrir önnur tré lýst með þessum græna,

283
00:21:30,640 --> 00:21:40,100
og við sjáum að hæð öllum þessum trjám er líka örugglega 3.

284
00:21:40,100 --> 00:21:45,230
Það er hluti af því sem gerir þá úrkynjuðu -

285
00:21:45,230 --> 00:21:53,750
að hæð þeirra er bara einn minna en fjöldi hnúta í allt tréð.

286
00:21:53,750 --> 00:21:58,400
Ef við horfum á þetta öðrum tré sem er kringum með rauðu, á hinn bóginn,

287
00:21:58,400 --> 00:22:03,920
sjáum við að mest fjarlæg blaða hnútar eru 6 og 9 -

288
00:22:03,920 --> 00:22:06,940
blöðin að þeir hnútar sem hafa ekki börn.

289
00:22:06,940 --> 00:22:11,760
Svo, í því skyni að fá úr rót hnút í annaðhvort 6 eða 9,

290
00:22:11,760 --> 00:22:17,840
við verðum að gera eitt step til að komast að 7 og svo annað step til að komast að 9,

291
00:22:17,840 --> 00:22:21,240
og sömuleiðis, bara annað step frá 7 til að komast í 6.

292
00:22:21,240 --> 00:22:29,080
Svo hæð þessu tré hérna er aðeins 2.

293
00:22:29,080 --> 00:22:35,330
Þú getur farið til baka og gera það fyrir öllum öðrum trjám sem við ræddum áður

294
00:22:35,330 --> 00:22:37,380
hefst með 7 og 6,

295
00:22:37,480 --> 00:22:42,500
og þú munt komast að því að hæð af öllum þeim trjám er líka 2.

296
00:22:42,500 --> 00:22:46,320
>> Ástæðan sem við höfum verið að tala um að panta tvöfaldur tré

297
00:22:46,320 --> 00:22:50,250
og hvers vegna þeir eru kúl er vegna þess að þú getur leitað í þeim

298
00:22:50,250 --> 00:22:53,810
mjög svipaðan hátt og leita yfir raðað fylki.

299
00:22:53,810 --> 00:22:58,720
Þetta er þar sem við tölum um að fá að bæta útlit tíma

300
00:22:58,720 --> 00:23:02,730
yfir þeirri einföldu tengda listanum.

301
00:23:02,730 --> 00:23:05,010
Með tengda listanum - ef þú vilt að finna ákveðna hluti -

302
00:23:05,010 --> 00:23:07,470
þú ert í besta falli að fara að gera einhvers konar línuleg leit

303
00:23:07,470 --> 00:23:10,920
þar sem þú byrjar í upphafi lista og step einn-við-einum -

304
00:23:10,920 --> 00:23:12,620
einn hnút eftir einum hnút -

305
00:23:12,620 --> 00:23:16,060
gegnum allt listann þar til þú finnur það sem þú ert að leita að.

306
00:23:16,060 --> 00:23:19,440
Teknu tilliti til, ef þú hafa a tvöfaldur tré sem er geymd í þessum fallegu sniði,

307
00:23:19,440 --> 00:23:23,300
þú getur í raun að fá meira af tvöfaldur leit að fara á

308
00:23:23,300 --> 00:23:25,160
þar sem þú skiptir og sigra

309
00:23:25,160 --> 00:23:29,490
og leita í gegnum viðeigandi hluta af trénu á hverju skrefi.

310
00:23:29,490 --> 00:23:32,840
Við skulum sjá hvernig það virkar.

311
00:23:32,840 --> 00:23:38,850
>> Ef við höfum - aftur, fara aftur í upprunalegt tré okkar -

312
00:23:38,850 --> 00:23:46,710
við byrjum á 7, höfum við 3 til vinstri, 9 til hægri,

313
00:23:46,710 --> 00:23:51,740
og undir 3 við höfum 6.

314
00:23:51,740 --> 00:24:01,880
Ef við viljum að leita að númer 6 í þessu tré, viljum við byrja á rót.

315
00:24:01,880 --> 00:24:08,910
Við viljum bera gildi sem við erum að leita að, segja 6,

316
00:24:08,910 --> 00:24:12,320
að verðmæti geymd í hnút sem við erum nú að leita á, 7,

317
00:24:12,320 --> 00:24:21,200
finna að 6 er örugglega minna en 7, svo að við myndum fara til vinstri.

318
00:24:21,200 --> 00:24:25,530
Ef verðmæti 6 hefði verið meira en 7, við viljum hafa í stað flutt til hægri.

319
00:24:25,530 --> 00:24:29,770
Þar sem við vitum að - vegna uppbyggingu pantaði tvíundartré okkar -

320
00:24:29,770 --> 00:24:33,910
öll gildi minna en 7 eru að fara að geyma til vinstri á 7,

321
00:24:33,910 --> 00:24:40,520
Það er engin þörf á að einu sinni nenna að horfa í gegnum hægra megin á trénu.

322
00:24:40,520 --> 00:24:43,780
Þegar við förum til vinstri og við erum nú í hnút sem inniheldur 3,

323
00:24:43,780 --> 00:24:48,110
Við getum gert það sama samanburð aftur þar sem við bera saman 3 og 6.

324
00:24:48,110 --> 00:24:52,430
Og við komumst að því á meðan 6 - gildi sem við erum að leita að - er meira en 3,

325
00:24:52,430 --> 00:24:58,580
við getum farið á hægri hlið hnút inniheldur 3.

326
00:24:58,580 --> 00:25:02,670
Það er enginn vinstri hlið hér, þannig að við gætum hafa hunsað það.

327
00:25:02,670 --> 00:25:06,510
En við vitum bara að vegna þess að við erum að horfa á tréð sjálft,

328
00:25:06,510 --> 00:25:08,660
og við getum séð að tré hefur ekki börn.

329
00:25:08,660 --> 00:25:13,640
>> Það er líka mjög auðvelt að líta upp 6 í þessu tré ef við erum að gera það okkur eins og menn,

330
00:25:13,640 --> 00:25:16,890
en við skulum fylgja þessu ferli vélrænt eins og tölva myndi gera

331
00:25:16,890 --> 00:25:18,620
að raunverulega skilja reiknirit.

332
00:25:18,620 --> 00:25:26,200
Á þessum tímapunkti, við erum nú að horfa á hnút sem inniheldur 6,

333
00:25:26,200 --> 00:25:29,180
og við erum að leita að verðmæti 6,

334
00:25:29,180 --> 00:25:31,740
svo, reyndar höfum við fundið viðeigandi hnút.

335
00:25:31,740 --> 00:25:35,070
Við fundum gildi 6 í trénu okkar, og við getum hætt leit okkar.

336
00:25:35,070 --> 00:25:37,330
Á þessum tímapunkti, allt eftir hvað er að gerast,

337
00:25:37,330 --> 00:25:41,870
við getum sagt, já, við höfum fundið gildi 6, er það í trénu okkar.

338
00:25:41,870 --> 00:25:47,640
Eða, ef við erum að skipuleggja að setja hnút eða gera eitthvað, getum við gert það á þessum tímapunkti.

339
00:25:47,640 --> 00:25:53,010
>> Gerum nokkrar fleiri vélarheiti bara að sjá hvernig þetta virkar.

340
00:25:53,010 --> 00:25:59,390
Við skulum líta á hvað gerist ef við vorum að reyna að líta upp gildi 10.

341
00:25:59,390 --> 00:26:02,970
Ef við værum að leita að verðmæti 10, við viljum byrja á rót.

342
00:26:02,970 --> 00:26:07,070
Við myndum sjá að 10 er meira en 7, svo að við myndum fara til hægri.

343
00:26:07,070 --> 00:26:13,640
Við viljum fá að 9 og bera 9 til 10 og sjá að 9 er örugglega minna en 10.

344
00:26:13,640 --> 00:26:16,210
Svo aftur, viljum við reyna að fara til hægri.

345
00:26:16,210 --> 00:26:20,350
En á þessum tímapunkti, myndum við taka eftir því að við erum á núll hnút.

346
00:26:20,350 --> 00:26:23,080
Það er ekkert þarna. Það er ekkert þar sem 10 ætti að vera.

347
00:26:23,080 --> 00:26:29,360
Þetta er þar sem við getum tilkynnt bilun - að það er örugglega ekki 10 í trénu.

348
00:26:29,360 --> 00:26:35,420
Og að lokum, við skulum fara í gegnum er að ræða þar sem við erum að reyna að horfa upp 1 í trénu.

349
00:26:35,420 --> 00:26:38,790
Þetta er svipað og það sem gerist ef við skoðum allt 10, nema í stað þess að fara til hægri,

350
00:26:38,790 --> 00:26:41,260
við erum að fara að fara til vinstri.

351
00:26:41,260 --> 00:26:46,170
Við byrjum á 7 og sjá að 1 er minna en 7, svo við færa til vinstri.

352
00:26:46,170 --> 00:26:51,750
Við fáum til 3 og sjá að 1 er minna en 3, svo aftur við að reyna að færa til vinstri.

353
00:26:51,750 --> 00:26:59,080
Á þessum tímapunkti sem við höfum núll hnút, svo aftur getum við tilkynna bilun.

354
00:26:59,080 --> 00:27:10,260
>> Ef þú vilt læra meira um tvöfaldur tré,

355
00:27:10,260 --> 00:27:14,420
það eru allt fullt af skemmtilegur lítill vandamál sem þú getur gert með þeim.

356
00:27:14,420 --> 00:27:19,450
Ég legg til að æfa að teikna út af þessum teikningum einn-við-einum

357
00:27:19,450 --> 00:27:21,910
og fylgja í gegnum allar mismunandi skrefum,

358
00:27:21,910 --> 00:27:25,060
vegna þess að þetta kemur í frábær-vel

359
00:27:25,060 --> 00:27:27,480
ekki aðeins þegar þú ert að gera Huffman kóðun vandamál setja

360
00:27:27,480 --> 00:27:29,390
heldur einnig í framtíðinni námskeið -

361
00:27:29,390 --> 00:27:32,220
bara að læra hvernig á að draga úr þessum gögn uppbygging og hugsa um vandamál

362
00:27:32,220 --> 00:27:38,000
með penna og pappír eða, í þessu tilfelli, iPad og stíll.

363
00:27:38,000 --> 00:27:41,000
>> Á þessum tímapunkti þó, við erum að fara að fara að gera sumir erfðaskrá æfa

364
00:27:41,000 --> 00:27:44,870
og í raun að spila með þessum tveimur trjám og sjá.

365
00:27:44,870 --> 00:27:52,150
Ég ætla að skipta aftur yfir í tölvuna mína.

366
00:27:52,150 --> 00:27:58,480
Í þessum hluta kafla, í stað þess að nota CS50 hlaupa eða CS50 rýmum

367
00:27:58,480 --> 00:28:01,500
Ég ætla að nota tæki.

368
00:28:01,500 --> 00:28:04,950
>> Eftir ásamt Set Vandamál forskrift,

369
00:28:04,950 --> 00:28:07,740
Ég sé að ég er ætlast til að opna tækið,

370
00:28:07,740 --> 00:28:11,020
fara Dropbox möppunni skaltu búa til möppu sem heitir kafla 7,

371
00:28:11,020 --> 00:28:15,730
og þá að búa til skrá sem kallast binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Hér förum. Ég hef fengið tækið þegar opinn.

373
00:28:22,050 --> 00:28:25,910
Ég ætla draga upp útstöð.

374
00:28:25,910 --> 00:28:38,250
Ég ætla að fara í Dropbox möppuna, gera möppu sem heitir section7,

375
00:28:38,250 --> 00:28:42,230
og sjá það er alveg tómt.

376
00:28:42,230 --> 00:28:48,860
Nú ætla ég að opna binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Hér förum - tómur skrá.

378
00:28:51,750 --> 00:28:54,330
>> Förum aftur til texta.

379
00:28:54,330 --> 00:28:59,850
Forskriftin biður að búa til nýja tegund skilgreiningu

380
00:28:59,850 --> 00:29:03,080
fyrir tvíundartrés hnút inniheldur int gildi -

381
00:29:03,080 --> 00:29:07,110
bara eins og þeim gildum sem við dró út í diagramming okkar áður.

382
00:29:07,110 --> 00:29:11,740
Við ætlum að nota þessa boilerplate typedef að við höfum gert hérna

383
00:29:11,740 --> 00:29:14,420
að þú ættir að þekkja úr Set Vandamál 5 -

384
00:29:14,420 --> 00:29:19,190
ef þú gerðir kjötkássa borð leið sigra Speller program.

385
00:29:19,190 --> 00:29:22,540
Þú ættir einnig að viðurkenna það af hluta síðustu viku

386
00:29:22,540 --> 00:29:23,890
þar sem við ræddum um tengd listum.

387
00:29:23,890 --> 00:29:27,870
Við höfum fengið þetta typedef á strúktúrinn hnút,

388
00:29:27,870 --> 00:29:34,430
og við höfum gefið þetta struct node þetta nafn hnút strúktúrinn fyrirfram

389
00:29:34,430 --> 00:29:39,350
þannig að við getum þá átt við það þar sem við munum vilja að strúktúr hnút ábendingum

390
00:29:39,350 --> 00:29:45,740
sem hluta af struct okkar, en við höfum þá lægi þetta -

391
00:29:45,740 --> 00:29:47,700
eða frekar, fylgir þetta - í typedef

392
00:29:47,700 --> 00:29:54,600
þannig að seinna í kóðanum, getum við átt við þennan strúktúr sem bara hnút í stað strúktúrinn hnút.

393
00:29:54,600 --> 00:30:03,120
>> Þetta er að fara að vera mjög svipað og ein sér-tengda lista skilgreiningu sem við sáum í síðustu viku.

394
00:30:03,120 --> 00:30:20,070
Til að gera þetta, við skulum bara byrja á því að skrifa út boilerplate.

395
00:30:20,070 --> 00:30:23,840
Við vitum að við verðum að hafa integer,

396
00:30:23,840 --> 00:30:32,170
þannig að við setjum í int gildi, og þá í stað þess að hafa bara einn bendi á næsta þátt -

397
00:30:32,170 --> 00:30:33,970
eins og við gerðum með ein sér-tengdum listum -

398
00:30:33,970 --> 00:30:38,110
við erum að fara að hafa vinstri og hægri barn ábendingum.

399
00:30:38,110 --> 00:30:42,880
Það er frekar einfalt líka - struct hnút * vinstri barn;

400
00:30:42,880 --> 00:30:51,190
og strúktúr hnút * rétt barn,. Cool.

401
00:30:51,190 --> 00:30:54,740
Það lítur út eins og nokkuð góð byrjun.

402
00:30:54,740 --> 00:30:58,530
Förum aftur til texta.

403
00:30:58,530 --> 00:31:05,030
>> Nú þurfum við að lýsa því yfir á heimsvísu hnút * breytu fyrir rót á tré.

404
00:31:05,030 --> 00:31:10,590
Við ætlum að gera þetta heimsvísu eins og við gert fyrstu músina í tengda listanum okkar einnig alþjóðlegt.

405
00:31:10,590 --> 00:31:12,690
Þetta var svo að í aðgerðum sem við skrifa

406
00:31:12,690 --> 00:31:16,180
við þurfum ekki að halda liggur um þetta rót -

407
00:31:16,180 --> 00:31:19,620
þó að við munum sjá að ef þú vilt að skrifa þessar aðgerðir endurkvæmt,

408
00:31:19,620 --> 00:31:22,830
það gæti verið betra að ekki einu sinni gefa það í kring eins og a alheims í fyrsta sæti

409
00:31:22,830 --> 00:31:28,090
og í staðinn frumstilla það á staðnum í aðal virka.

410
00:31:28,090 --> 00:31:31,960
En við munum gera það á heimsvísu að byrja.

411
00:31:31,960 --> 00:31:39,920
Aftur, munum við gefa nokkur rými og ég ætla að lýsa yfir hnút * rót.

412
00:31:39,920 --> 00:31:46,770
Bara til að vera viss um að ég leyfi þetta ekki forsniðinn, ætla ég að setja það jafnt null.

413
00:31:46,770 --> 00:31:52,210
Nú, í meginvirkni - sem við munum skrifa mjög hratt hérna -

414
00:31:52,210 --> 00:32:00,450
INT helstu (int argc, const char * argv []) -

415
00:32:00,450 --> 00:32:10,640
og ég ætla að byrja að lýsa argv array mitt sem const bara svo að ég veit

416
00:32:10,640 --> 00:32:14,550
að þessi rök eru rök sem ég sennilega vilja ekki að breyta.

417
00:32:14,550 --> 00:32:18,390
Ef ég vil að breyta þeim að ég ætti líklega að gera afrit af þeim.

418
00:32:18,390 --> 00:32:21,740
Þú munt sjá þetta mikið í kóða.

419
00:32:21,740 --> 00:32:25,440
Það er allt í lagi annar hvor vegur. Það er í lagi að skilja það sem - sleppt const ef þú vilt.

420
00:32:25,440 --> 00:32:28,630
Ég setti oftast það bara svo að ég minna mig

421
00:32:28,630 --> 00:32:33,650
 sem ég sennilega vil ekki breyta þeim rök.

422
00:32:33,650 --> 00:32:39,240
>> Eins og alltaf, ég ætla að láta þetta aftur 0 línu í lok aðal.

423
00:32:39,240 --> 00:32:45,730
Hér mun ég frumstilla rót hnút minn.

424
00:32:45,730 --> 00:32:48,900
Eins og það stendur núna, hef ég fékk músina sem er stillt á núll,

425
00:32:48,900 --> 00:32:52,970
þannig að það er að benda á neitt.

426
00:32:52,970 --> 00:32:57,480
Til að í raun að byrja að byggja upp hnút,

427
00:32:57,480 --> 00:32:59,250
Ég þarf fyrst að úthluta minni fyrir það.

428
00:32:59,250 --> 00:33:05,910
Ég ætla að gera það með því að gera minni á hrúga með malloc.

429
00:33:05,910 --> 00:33:10,660
Ég ætla að setja rót jafn niðurstöðu malloc,

430
00:33:10,660 --> 00:33:19,550
og ég ætla að nota sizeof rekstraraðila til að reikna út stærð á hnút.

431
00:33:19,550 --> 00:33:24,990
Ástæðan fyrir því að ég nota sizeof hnút í stað þess að segja,

432
00:33:24,990 --> 00:33:37,020
að gera eitthvað eins og þetta - malloc (4 + 4 +4) eða malloc 12 -

433
00:33:37,020 --> 00:33:40,820
er vegna þess að ég vil kóða mína til að vera eins samhæft og kostur er.

434
00:33:40,820 --> 00:33:44,540
Mig langar að vera fær um að taka þessa. C skrá, þýða það á tækinu,

435
00:33:44,540 --> 00:33:48,820
og þýða það á 64-bita Mac minn -

436
00:33:48,820 --> 00:33:52,040
eða á algjörlega mismunandi arkitektúr -

437
00:33:52,040 --> 00:33:54,640
og ég vil þetta allt til að vinna sama.

438
00:33:54,640 --> 00:33:59,510
>> Ef ég er að gera ályktanir um stærð breytur -

439
00:33:59,510 --> 00:34:02,070
stærð heiltala eða stærð bendill -

440
00:34:02,070 --> 00:34:06,070
þá er ég líka að gera ályktanir um hvers konar arkitektúr

441
00:34:06,070 --> 00:34:10,440
sem númerið mitt getur tekist saman þegar hlaupa.

442
00:34:10,440 --> 00:34:15,030
Alltaf nota sizeof öfugt við handvirkt toppur á strúktúr sviðum.

443
00:34:15,030 --> 00:34:20,500
Hin ástæðan er sú að það gæti líka verið padding að þýðandinn setur í strúktúr.

444
00:34:20,500 --> 00:34:26,570
Jafnvel bara toppur á einstökum sviðum er ekki eitthvað sem þú vilt að jafnaði að gera,

445
00:34:26,570 --> 00:34:30,340
Svo eyða þessi lína.

446
00:34:30,340 --> 00:34:33,090
Nú, til að virkilega frumstilla þennan rót hnút,

447
00:34:33,090 --> 00:34:36,489
Ég ætla að hafa til að stinga í gildi fyrir hverja ýmsum sviðum þess.

448
00:34:36,489 --> 00:34:41,400
Til dæmis, fyrir gildi sem ég veit að ég vil að frumstilla til 7,

449
00:34:41,400 --> 00:34:46,920
og nú ætla ég að setja vinstri barnið að vera null

450
00:34:46,920 --> 00:34:55,820
og rétt barnið einnig að vera null. Great!

451
00:34:55,820 --> 00:35:02,670
Við höfum gert að hluti af sérstakur.

452
00:35:02,670 --> 00:35:07,390
>> Forskriftin niður neðst á síðu 3 biður mig að búa til þrjú fleiri hnúta -

453
00:35:07,390 --> 00:35:10,600
ein með 3, einn með 6, og einn með 9 -

454
00:35:10,600 --> 00:35:14,210
og vír þá upp þannig lítur það nákvæmlega eins og skýringarmynd tré okkar

455
00:35:14,210 --> 00:35:17,120
að við vorum að tala um áður.

456
00:35:17,120 --> 00:35:20,450
Við skulum gera það mjög hratt hér.

457
00:35:20,450 --> 00:35:26,270
Þú munt sjá mjög fljótt að ég ætla að byrja að skrifa fullt af afrit kóða.

458
00:35:26,270 --> 00:35:32,100
Ég ætla að búa til hnút * og ég ætla að kalla það þrír.

459
00:35:32,100 --> 00:35:36,000
Ég ætla að setja það jafn malloc (sizeof (hnút)).

460
00:35:36,000 --> 00:35:41,070
Ég ætla að setja þriggja> gildi = 3.

461
00:35:41,070 --> 00:35:54,780
Three -> left_child = NULL, þrír -> hægri _child = NULL, eins og heilbrigður.

462
00:35:54,780 --> 00:36:01,150
Það lítur mjög svipað Frumstilli rót, og það er einmitt það sem

463
00:36:01,150 --> 00:36:05,760
Ég ætla að gera ef ég byrja Frumstilli 6 og 9 eins og heilbrigður.

464
00:36:05,760 --> 00:36:20,720
Ég mun gera það mjög fljótt hér - reyndar, ég ætla að gera smá afrit og líma,

465
00:36:20,720 --> 00:36:46,140
og ganga úr skugga um að ég - allt í lagi.

466
00:36:46,470 --> 00:37:09,900
 Nú hef ég fengið það afritað og ég get farið á undan og setja þetta jafnt 6.

467
00:37:09,900 --> 00:37:14,670
Þú getur séð að það tekur stutta stund og er ekki Super-duglegur.

468
00:37:14,670 --> 00:37:22,610
Í réttlátur a lítill hluti, munum við skrifa fall sem vilja gera þetta fyrir okkur.

469
00:37:22,610 --> 00:37:32,890
Mig langar til að skipta þetta með 9, í stað þessi með 6.

470
00:37:32,890 --> 00:37:37,360
>> Nú höfum við fengið alla tengipunkta okkar til og frumstillt.

471
00:37:37,360 --> 00:37:41,200
Við höfum fengið rót okkar sett jafn 7 eða inniheldur gildið 7,

472
00:37:41,200 --> 00:37:46,510
hnút okkar inniheldur 3, hnút okkar inniheldur 6, og hnút okkar inniheldur 9.

473
00:37:46,510 --> 00:37:50,390
Á þessum tímapunkti, allt sem við þurfum að gera er að víra allt upp.

474
00:37:50,390 --> 00:37:53,020
The ástæða ÉG frumstilla allar ábendingar til að null er bara þannig að ég vera viss um að

475
00:37:53,020 --> 00:37:56,260
Ég hef engar forsniðinn ábendingum á það fyrir tilviljun.

476
00:37:56,260 --> 00:38:02,290
Og líka þar, á þessum tímapunkti, ég hef bara til raunverulega tengja hnúður við hvert annað -

477
00:38:02,290 --> 00:38:04,750
við þær að þær séu í raun tengd við - ég þarf ekki að fara í gegnum og gera

478
00:38:04,750 --> 00:38:08,240
úr skugga um að öll nulls eru þarna í viðeigandi stöðum.

479
00:38:08,240 --> 00:38:15,630
>> Byrjar á rót, veit ég að vinstri barn sem rót er 3.

480
00:38:15,630 --> 00:38:21,250
Ég veit að rétt barn í rót er 9.

481
00:38:21,250 --> 00:38:24,880
Eftir það, það eina sem barn sem ég hef eftir að hafa áhyggjur af

482
00:38:24,880 --> 00:38:39,080
er rétt barn 3, sem er 6.

483
00:38:39,080 --> 00:38:44,670
Á þessum tímapunkti, það lítur allt mjög gott.

484
00:38:44,670 --> 00:38:54,210
Við munum eyða einhverjum af þessum línum.

485
00:38:54,210 --> 00:38:59,540
Nú lítur allt nokkuð gott.

486
00:38:59,540 --> 00:39:04,240
Við skulum fara aftur til forskriftir okkar og sjá hvað við þurfum að gera næst.

487
00:39:04,240 --> 00:39:07,610
>> Á þessum tímapunkti verðum við að skrifa fall sem kallast 'inniheldur'

488
00:39:07,610 --> 00:39:14,150
með frumgerð af "bool inniheldur (int gildi)".

489
00:39:14,150 --> 00:39:17,060
Og þetta inniheldur virka er að fara að skila satt

490
00:39:17,060 --> 00:39:21,200
 ef tréð benti á af alþjóðlegum rót breytu okkar

491
00:39:21,200 --> 00:39:26,950
 inniheldur gildi liðin í aðgerð og ósönn annars.

492
00:39:26,950 --> 00:39:29,000
Við skulum fara á undan og gera það.

493
00:39:29,000 --> 00:39:35,380
Þetta er að fara að vera nákvæmlega eins og útlit sem við gerðum af hendi á iPad bara svolítið síðan.

494
00:39:35,380 --> 00:39:40,130
Skulum súmma aftur í smá og fletta upp.

495
00:39:40,130 --> 00:39:43,130
Við erum að fara að setja þessa aðgerð rétt fyrir ofan meginvirkni okkar

496
00:39:43,130 --> 00:39:48,990
þannig að við þurfum ekki að gera hvers konar frumgerð.

497
00:39:48,990 --> 00:39:55,960
Svo, bool inniheldur (int gildi).

498
00:39:55,960 --> 00:40:00,330
Svona. Það er boilerplate yfirlýsingu okkar.

499
00:40:00,330 --> 00:40:02,900
Bara til að vera viss um að þetta mun þýða,

500
00:40:02,900 --> 00:40:06,820
Ég ætla að fara á undan og bara setja það jafnt return false.

501
00:40:06,820 --> 00:40:09,980
Núna þessi aðgerð bara ekki gera neitt og alltaf að tilkynna það

502
00:40:09,980 --> 00:40:14,010
verðmæti sem við erum að leita að er ekki í tré.

503
00:40:14,010 --> 00:40:16,280
>> Á þessum tímapunkti, er það líklega góð hugmynd -

504
00:40:16,280 --> 00:40:19,600
þar sem við höfum skrifað í heild búnt af kóða og við höfum ekki einu sinni reynt að prófa það enn -

505
00:40:19,600 --> 00:40:22,590
að ganga úr skugga um að það safnar öllum.

506
00:40:22,590 --> 00:40:27,460
There ert a par af hlutum sem við þurfum að gera til að tryggja að þetta mun í raun þýða.

507
00:40:27,460 --> 00:40:33,530
Í fyrsta lagi hvort við höfum verið að nota einhverjar aðgerðir í öllum bókasöfnum sem við höfum enn ekki innifalin.

508
00:40:33,530 --> 00:40:37,940
Þær aðgerðir sem við höfum notað hingað til eru malloc,

509
00:40:37,940 --> 00:40:43,310
og svo höfum við líka verið að nota þessa tegund - þetta nonstandard tegund kallast "bool' -

510
00:40:43,310 --> 00:40:45,750
sem er að finna í stöðluðu bool haus skrá.

511
00:40:45,750 --> 00:40:53,250
Við viljum örugglega að fela staðall bool.h fyrir bool tegund,

512
00:40:53,250 --> 00:40:59,230
og við viljum einnig að # include staðall lib.h fyrir staðall bókasöfn

513
00:40:59,230 --> 00:41:03,530
sem eru malloc og frjáls, og allt það.

514
00:41:03,530 --> 00:41:08,660
Svo, minnka, við erum að fara að hætta.

515
00:41:08,660 --> 00:41:14,190
Við skulum reyna að ganga úr skugga um að þetta raunverulega gerði safna.

516
00:41:14,190 --> 00:41:18,150
Við sjáum að það er, þannig að við erum á réttri leið.

517
00:41:18,150 --> 00:41:22,990
>> Við skulum opna binary_tree.c aftur.

518
00:41:22,990 --> 00:41:34,530
Það safnar. Við skulum fara niður og tryggja að við að setja nokkur símtöl til Inniheldur virka okkar -

519
00:41:34,530 --> 00:41:40,130
bara til að vera viss um að það er allt vel og gott.

520
00:41:40,130 --> 00:41:43,170
Til dæmis, þegar við gerðum nokkur vélarheiti í trénu okkar fyrr,

521
00:41:43,170 --> 00:41:48,500
við reyndum að leita upp þau gildi 6, 10 og 1, og við vissum að 6 væri í trénu,

522
00:41:48,500 --> 00:41:52,220
10 var ekki á trénu, og 1 var ekki í trénu heldur.

523
00:41:52,220 --> 00:41:57,230
Við skulum nota þau dæmi um símtöl sem leið til að reikna út hvort

524
00:41:57,230 --> 00:41:59,880
Inniheldur virka okkar er að vinna.

525
00:41:59,880 --> 00:42:05,210
Til að gera það, ég ætla að nota printf virka,

526
00:42:05,210 --> 00:42:10,280
og við erum að fara að prenta út niðurstöðu að hringja til að geyma.

527
00:42:10,280 --> 00:42:13,280
Ég ætla að setja í streng "inniheldur (% d) = vegna

528
00:42:13,280 --> 00:42:20,470
 við erum að fara að stinga í gildi sem við erum að fara að leita að,

529
00:42:20,470 --> 00:42:27,130
og =% s \ n "og nota það sem band snið okkar.

530
00:42:27,130 --> 00:42:30,720
Við erum bara að fara að sjá - bókstaflega prenta út á skjáinn -

531
00:42:30,720 --> 00:42:32,060
það lítur út eins og virka símtalinu.

532
00:42:32,060 --> 00:42:33,580
Þetta er í raun ekki að virka símtalinu.

533
00:42:33,580 --> 00:42:36,760
 Þetta er bara strengur hannað til að líta út eins og virka símtalinu.

534
00:42:36,760 --> 00:42:41,140
>> Nú erum við að fara að stinga á þeim gildum.

535
00:42:41,140 --> 00:42:43,580
Við ætlum að reyna finna á 6,

536
00:42:43,580 --> 00:42:48,340
og þá er það sem við erum að fara að gera hér nota þessi ternary rekstraraðila.

537
00:42:48,340 --> 00:42:56,340
Við skulum sjá - inniheldur 6 - svo nú er ég búin að finna 6 og ef inniheldur 6 er satt,

538
00:42:56,340 --> 00:43:01,850
band sem við ætlum að senda til snið staf í% s

539
00:43:01,850 --> 00:43:04,850
er að fara til vera the band "true".

540
00:43:04,850 --> 00:43:07,690
Við skulum fletta yfir smá.

541
00:43:07,690 --> 00:43:16,210
Annars viljum við senda band "false" Ef inniheldur 6 False.

542
00:43:16,210 --> 00:43:19,730
Þetta er svolítið Guffi-útlit, en ég reikna að ég gæti eins vel að sýna

543
00:43:19,730 --> 00:43:23,780
hvað ternary rekstraraðili lítur út þar sem við höfum ekki séð það um hríð.

544
00:43:23,780 --> 00:43:27,670
Þetta verður gaman, handlaginn leið til að reikna út ef inniheldur virka okkar er að vinna.

545
00:43:27,670 --> 00:43:30,040
Ég ætla að fletta aftur yfir til vinstri,

546
00:43:30,040 --> 00:43:39,900
og ég ætla að afrita og líma þessa línu nokkrum sinnum.

547
00:43:39,900 --> 00:43:44,910
Það breytti sum af þessum gildum í kring,

548
00:43:44,910 --> 00:43:59,380
þannig að þetta er að fara að vera 1, og þetta er að fara að vera 10.

549
00:43:59,380 --> 00:44:02,480
>> Á þessum tímapunkti sem við höfum fengið gott Inniheldur virka.

550
00:44:02,480 --> 00:44:06,080
Við höfum fengið nokkur próf, og við munum sjá hvort þetta virkar allt.

551
00:44:06,080 --> 00:44:08,120
Á þessum tímapunkti sem við höfum skrifað nokkrar fleiri kóða.

552
00:44:08,120 --> 00:44:13,160
Tími til að hætta út og ganga úr skugga um að allt enn safnar.

553
00:44:13,160 --> 00:44:20,360
Hætta út og nú skulum reyna að gera tvöfaldur tré aftur.

554
00:44:20,360 --> 00:44:22,260
Jæja, það lítur út eins og við höfum fengið villu,

555
00:44:22,260 --> 00:44:26,930
og við höfum fengið þetta lýsa skýrt bókasafn virka printf.

556
00:44:26,930 --> 00:44:39,350
Það lítur út eins og við þurfum að fara í og ​​# include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Og með því að, allt ætti að þýða. Við erum öll góð.

558
00:44:45,350 --> 00:44:50,420
Nú skulum reyna að keyra tvöfaldur tré og sjá hvað gerist.

559
00:44:50,420 --> 00:44:53,520
Hér erum við,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
og við sjáum að, eins og við gerðum ráð fyrir -

561
00:44:55,190 --> 00:44:56,910
vegna þess að við höfum ekki innleitt inniheldur enn,

562
00:44:56,910 --> 00:44:59,800
eða öllu heldur, höfum við bara sett í staðinn falskur -

563
00:44:59,800 --> 00:45:03,300
sjáum við að það er bara aftur rangt fyrir þeim öllum,

564
00:45:03,300 --> 00:45:06,180
svo það er allt að vinna að mestu leyti nokkuð vel.

565
00:45:06,180 --> 00:45:11,860
>> Förum aftur í og ​​í raun að framkvæma eru á þessum tímapunkti.

566
00:45:11,860 --> 00:45:17,490
Ég ætla að fletta niður, súmma inn og -

567
00:45:17,490 --> 00:45:22,330
Mundu að reiknirit sem við notuðum var að við byrjuðum á rót hnút

568
00:45:22,330 --> 00:45:28,010
og þá á hvern hnút sem við lendum í, gera við samanburð,

569
00:45:28,010 --> 00:45:32,380
og byggt á þeirri samanburði við færa annaðhvort vinstri barn eða hægri barn.

570
00:45:32,380 --> 00:45:39,670
Þetta er að fara að líta mjög svipað leit tvöfaldur kóða sem við skrifaði áðan í tíma.

571
00:45:39,670 --> 00:45:47,810
Þegar við byrjum á, við vitum að við viljum halda í núverandi hnút

572
00:45:47,810 --> 00:45:54,050
sem við erum að horfa á, og núverandi hnút er að fara að frumstilla að rót hnút.

573
00:45:54,050 --> 00:45:56,260
Og nú erum við að fara að halda áfram í gegnum tré,

574
00:45:56,260 --> 00:45:58,140
og muna að okkar stífla ástand -

575
00:45:58,140 --> 00:46:01,870
 þegar við gekk reyndar í gegnum dæmi af hendi -

576
00:46:01,870 --> 00:46:03,960
var þegar við rakst á núll hnút,

577
00:46:03,960 --> 00:46:05,480
ekki þegar við skoðuðum núll barn,

578
00:46:05,480 --> 00:46:09,620
heldur þegar við fluttum reyndar í hnút í trénu

579
00:46:09,620 --> 00:46:12,640
og komist að því að við erum á núll hnút.

580
00:46:12,640 --> 00:46:20,720
Við ætlum að iterate þar nú er ekki jafn null.

581
00:46:20,720 --> 00:46:22,920
Og hvað ætlum við að gera?

582
00:46:22,920 --> 00:46:31,610
Við ætlum að prófa hvort (nú -> gildi == gildi),

583
00:46:31,610 --> 00:46:35,160
þá vitum við að við höfum í raun og veru fundið hnút sem við erum að leita að.

584
00:46:35,160 --> 00:46:40,450
Svo hér, getum við aftur satt.

585
00:46:40,450 --> 00:46:49,830
Annars viljum við sjá hvort gildið er minna en gildið.

586
00:46:49,830 --> 00:46:53,850
Ef gildi núverandi Hnútur er minna en gildið sem við erum að leita að,

587
00:46:53,850 --> 00:46:57,280
við erum að fara að flytja til hægri.

588
00:46:57,280 --> 00:47:10,600
Svo, nú = nú -> right_child, og annað, við erum að fara að flytja til vinstri.

589
00:47:10,600 --> 00:47:17,480
nú = nú -> left_child;. Pretty einfalt.

590
00:47:17,480 --> 00:47:22,830
>> Þú kannast líklega lykkjunnar sem lítur mjög svipað og þetta frá

591
00:47:22,830 --> 00:47:27,580
tvöfaldur leita fyrr í tíma, nema þá vorum við að takast á við lítil miðjan og hár.

592
00:47:27,580 --> 00:47:30,000
Hér höfum við bara að horfa á núverandi gildi,

593
00:47:30,000 --> 00:47:31,930
svo það er gott og einfalt.

594
00:47:31,930 --> 00:47:34,960
Við skulum vera viss um þetta virki.

595
00:47:34,960 --> 00:47:42,780
Fyrst skaltu ganga úr skugga um að það safnar. Útlit eins og það er.

596
00:47:42,780 --> 00:47:47,920
Við skulum reyna að keyra það.

597
00:47:47,920 --> 00:47:50,160
Og reyndar prentar það út allt sem við gerðum ráð fyrir.

598
00:47:50,160 --> 00:47:54,320
Það finnur 6 í trénu, er ekki að finna 10 því 10 er ekki í trénu,

599
00:47:54,320 --> 00:47:57,740
og finnur ekki 1 heldur því 1 er líka ekki á trénu.

600
00:47:57,740 --> 00:48:01,420
Flott efni.

601
00:48:01,420 --> 00:48:04,470
>> Alright. Við skulum fara aftur til forskriftir okkar og sjá hvað er næst.

602
00:48:04,470 --> 00:48:07,990
Nú vill það að bæta við fleiri hnútar í tré okkar.

603
00:48:07,990 --> 00:48:11,690
Það vill til að bæta við 5, 2 og 8, og að tryggja að okkar inniheldur kóða

604
00:48:11,690 --> 00:48:13,570
enn virkar eins og búast mætti.

605
00:48:13,570 --> 00:48:14,900
Við skulum fara að gera það.

606
00:48:14,900 --> 00:48:19,430
Á þessum tímapunkti, frekar en að gera það pirrandi að afrita og líma aftur,

607
00:48:19,430 --> 00:48:23,770
við skulum skrifa fall í raun að búa til hnút.

608
00:48:23,770 --> 00:48:27,740
Ef við fletta niður alla leið að helstu, sjáum við að við höfum verið að gera þetta

609
00:48:27,740 --> 00:48:31,210
mjög svipuð númerið aftur og aftur í hvert sinn sem við viljum búa til hnút.

610
00:48:31,210 --> 00:48:39,540
>> Við skulum skrifa fall sem mun í raun byggja upp hnút fyrir okkur og skila.

611
00:48:39,540 --> 00:48:41,960
Ég ætla að kalla það build_node.

612
00:48:41,960 --> 00:48:45,130
Ég ætla að byggja upp hnút með tilteknu gildi.

613
00:48:45,130 --> 00:48:51,040
Þysja inn hér.

614
00:48:51,040 --> 00:48:56,600
Það fyrsta sem ég ætla að gera er í raun að búa til pláss fyrir hnút á hrúga.

615
00:48:56,600 --> 00:49:05,400
Svo hnút * n = malloc (sizeof (hnút)), n -> gildi = gildi;

616
00:49:05,400 --> 00:49:14,960
og svo hér, ég er bara að fara að frumstilla öllum sviðum til að vera viðeigandi gildi.

617
00:49:14,960 --> 00:49:22,500
Og aftast, munum við aftur hnút okkar.

618
00:49:22,500 --> 00:49:28,690
Alright. Eitt að hafa í huga er að þetta virka hérna

619
00:49:28,690 --> 00:49:34,320
er að fara að skila bendi á minni sem hefur verið hrúga-úthlutað.

620
00:49:34,320 --> 00:49:38,880
Hvað er gott um þetta er að þessi hnútur núna -

621
00:49:38,880 --> 00:49:42,420
við verðum að lýsa því á hrúga því ef við lýst því á mánudaginn

622
00:49:42,420 --> 00:49:45,050
myndum við ekki vera fær um að gera það í þessa aðgerð svona.

623
00:49:45,050 --> 00:49:47,690
Þessi minni myndi fara út af umfangi

624
00:49:47,690 --> 00:49:51,590
og væri ógild ef við reyndum að nálgast það síðar.

625
00:49:51,590 --> 00:49:53,500
Þar sem við erum að lýsa hrúga-úthlutað minni,

626
00:49:53,500 --> 00:49:55,830
við erum að fara til verða að gæta frjáls það seinna

627
00:49:55,830 --> 00:49:58,530
fyrir áætlun okkar að ekki leka allir minni.

628
00:49:58,530 --> 00:50:01,270
Við höfum verið að punting á að fyrir allt annað í kóða

629
00:50:01,270 --> 00:50:02,880
bara fyrir sakir einfaldleika er á þeim tíma,

630
00:50:02,880 --> 00:50:05,610
en ef þú skrifar alltaf fall sem lítur svona út

631
00:50:05,610 --> 00:50:10,370
þar sem þú hefur fengið - sumir kalla það malloc eða realloc inni -

632
00:50:10,370 --> 00:50:14,330
þú vilt ganga úr skugga um að þú setur einhvers konar athugasemd hérna sem segir,

633
00:50:14,330 --> 00:50:29,970
hey, þú veist, skilar hrúga-úthlutað hnút frumstilla með liðin-í gildi.

634
00:50:29,970 --> 00:50:33,600
Og þá þú vilt vera viss um að þú settir í einhverskonar miða sem segir

635
00:50:33,600 --> 00:50:41,720
hringir að losa skilað minni.

636
00:50:41,720 --> 00:50:45,450
Þannig ef einhver alltaf fer og notar að virka,

637
00:50:45,450 --> 00:50:48,150
Þeir vita að það sem þeir fá til baka úr þeim virka

638
00:50:48,150 --> 00:50:50,870
á einhverjum tímapunkti verður að vera leystur.

639
00:50:50,870 --> 00:50:53,940
>> Miðað við að allt er vel og gott hér,

640
00:50:53,940 --> 00:51:02,300
við getum farið niður í númerið okkar og skipta öllum þessum línum hérna

641
00:51:02,300 --> 00:51:05,410
með símtöl til okkar byggja hnút virka.

642
00:51:05,410 --> 00:51:08,170
Við skulum gera það mjög hratt.

643
00:51:08,170 --> 00:51:15,840
Sá hluti sem við erum ekki að fara að skipta er þessi hluti hérna

644
00:51:15,840 --> 00:51:18,520
neðst þar sem við víra í raun upp hnúður til að benda á hvort annað,

645
00:51:18,520 --> 00:51:21,030
vegna þess að við getum ekki verið að gera aðgerð okkar.

646
00:51:21,030 --> 00:51:37,400
En við skulum gera rót = build_node (7), hnútur * þrír = build_node (3);

647
00:51:37,400 --> 00:51:47,980
hnút * sex = build_node (6), hnútur * níu = build_node (9),.

648
00:51:47,980 --> 00:51:52,590
Og nú, við vildum líka að bæta við hnúta fyrir -

649
00:51:52,590 --> 00:52:03,530
hnút * fimm = build_node (5), hnútur * átta = build_node (8);

650
00:52:03,530 --> 00:52:09,760
og hvað var hinn hnút? Við skulum sjá hér. Við vildum einnig bæta við 2 -

651
00:52:09,760 --> 00:52:20,280
hnút * tveir = build_node (2),.

652
00:52:20,280 --> 00:52:26,850
Alright. Á þessum tímapunkti, við vitum að við höfum fengið 7, 3, 9, og 6

653
00:52:26,850 --> 00:52:30,320
allt hlerunarbúnað upp á viðeigandi hátt, en hvað um 5, 8, og 2?

654
00:52:30,320 --> 00:52:33,550
Til að halda öllu í góðu horfi,

655
00:52:33,550 --> 00:52:39,230
Vér vitum, að réttur barn THREE er 6.

656
00:52:39,230 --> 00:52:40,890
Svo ef við ætlum að bæta við 5,

657
00:52:40,890 --> 00:52:46,670
The 5 tilheyrir einnig í hægra megin á trénu sem 3 er rót,

658
00:52:46,670 --> 00:52:50,440
svo 5 tilheyrir sem vinstri barn 6.

659
00:52:50,440 --> 00:52:58,650
Við getum gert þetta með því að segja, sex -> left_child = fimm;

660
00:52:58,650 --> 00:53:10,790
og þá 8 tilheyrir sem vinstri barn 9, svo níu -> left_child = átta;

661
00:53:10,790 --> 00:53:22,190
og þá er 2 vinstri barn 3, svo að við getum gert það upp hér - þér -> left_child = tveir,.

662
00:53:22,190 --> 00:53:27,730
Ef þú hefur ekki alveg fylgst með því, ég legg til að þú draga það út sjálfur.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Við skulum spara þetta. Við skulum fara út og ganga úr skugga um að það safnar,

664
00:53:35,660 --> 00:53:40,760
og þá getum við bætt á Inniheldur símtöl okkar.

665
00:53:40,760 --> 00:53:44,120
Útlit eins og allt enn safnar.

666
00:53:44,120 --> 00:53:51,790
Við skulum fara inn og bæta við í sumum inniheldur símtöl.

667
00:53:51,790 --> 00:53:59,640
Aftur, ég ætla að gera a lítill hluti af afrita og líma.

668
00:53:59,640 --> 00:54:15,860
Nú skulum leita að 5, 8 og 2. Alright.

669
00:54:15,860 --> 00:54:28,330
Við skulum vera viss um að þetta allt lítur vel út enn. Great! Vista og hætta.

670
00:54:28,330 --> 00:54:33,220
Nú skulum gera, safna saman, og nú skulum hlaupa.

671
00:54:33,220 --> 00:54:37,540
Frá niðurstöðum, það útlit eins og allt er að vinna bara gott og vel.

672
00:54:37,540 --> 00:54:41,780
Great! Svo nú höfum við fengið Contains okkar virka skrifað.

673
00:54:41,780 --> 00:54:46,160
Við skulum fara og byrja að vinna á hvernig á að setja hnúta í trénu

674
00:54:46,160 --> 00:54:50,000
þar sem við erum að gera það núna, er það ekki mjög fallegt.

675
00:54:50,000 --> 00:54:52,280
>> Ef við förum aftur til forskriftir,

676
00:54:52,280 --> 00:55:00,540
það biður okkur að skrifa fall sem kallast setja - aftur, aftur a bool

677
00:55:00,540 --> 00:55:04,400
um hvort eða ekki að við gætum í raun að setja hnút í tré -

678
00:55:04,400 --> 00:55:07,710
og þá gildi að setja inn í tré greinist

679
00:55:07,710 --> 00:55:11,060
eina rök til að setja virka okkar.

680
00:55:11,060 --> 00:55:18,180
Við munum koma aftur við ef við gætum örugglega setja hnút innihalda gildi í trénu,

681
00:55:18,180 --> 00:55:20,930
sem þýðir að við, einn, haft nóg minni,

682
00:55:20,930 --> 00:55:24,840
og síðan tvær að hnúturinn var ekki þegar til staðar í tré frá -

683
00:55:24,840 --> 00:55:32,170
Mundu, við erum ekki að fara að hafa afrit gildi í trénu, bara til að gera hlutina einfalt.

684
00:55:32,170 --> 00:55:35,590
Alright. Aftur til kóðann.

685
00:55:35,590 --> 00:55:44,240
Opnaðu það upp. Zoom í smá, þá fletta niður.

686
00:55:44,240 --> 00:55:47,220
Við skulum setja setja inn virka rétt fyrir ofan inniheldur.

687
00:55:47,220 --> 00:55:56,360
Aftur, það er að fara að vera kölluð bool setja (int gildi).

688
00:55:56,360 --> 00:56:01,840
Gefðu það svolítið meira pláss, og þá, eins og sjálfgefið,

689
00:56:01,840 --> 00:56:08,870
skulum setja á return false aftast.

690
00:56:08,870 --> 00:56:22,620
Nú neðst, við skulum fara á undan og í stað þess að handvirkt byggja hnúður

691
00:56:22,620 --> 00:56:27,900
í helstu okkur og tengi þá upp til að benda á hvert annað eins og við erum að gera,

692
00:56:27,900 --> 00:56:30,600
við munum treysta á virka setja inn okkar að gera það.

693
00:56:30,600 --> 00:56:35,510
Við munum ekki treysta á virka setja inn okkar að byggja allt tré frá grunni bara enn,

694
00:56:35,510 --> 00:56:39,970
heldur að við munum losna við þessar línur - we'll athugasemd út þessar línur -

695
00:56:39,970 --> 00:56:43,430
sem byggja hnúður 5, 8 og 2.

696
00:56:43,430 --> 00:56:55,740
Og í staðinn munum við setja símtöl til að setja virka okkar

697
00:56:55,740 --> 00:57:01,280
að ganga úr skugga um að það virkar.

698
00:57:01,280 --> 00:57:05,840
Hér förum.

699
00:57:05,840 --> 00:57:09,300
>> Nú höfum við athugasemd út þessar línur.

700
00:57:09,300 --> 00:57:13,700
Við höfum aðeins 7, 3, 9 og 6 á trénu okkar á þessum tímapunkti.

701
00:57:13,700 --> 00:57:18,870
Til að ganga úr skugga um að þetta er allt að vinna,

702
00:57:18,870 --> 00:57:25,050
getum við minnka, gera tvöfaldur tré okkar,

703
00:57:25,050 --> 00:57:30,750
keyra hana, og við getum séð að innihalda er nú að segja okkur að við erum algerlega rétt -

704
00:57:30,750 --> 00:57:33,110
5, 8, og 2 eru ekki lengur í trénu.

705
00:57:33,110 --> 00:57:37,960
Fara aftur í kóða,

706
00:57:37,960 --> 00:57:41,070
og hvernig eigum við að fara að setja inn?

707
00:57:41,070 --> 00:57:46,290
Mundu það sem við gerðum þegar við vorum í raun að setja 5, 8 og 2 áður.

708
00:57:46,290 --> 00:57:50,100
Við spiluðum að Plinko leikur þar sem við byrjuðum á rót,

709
00:57:50,100 --> 00:57:52,780
fór niður tré eitt af eitt og eitt

710
00:57:52,780 --> 00:57:54,980
þar til við höfum fundið viðeigandi bilið,

711
00:57:54,980 --> 00:57:57,570
og þá erum við hlerunarbúnað í hnút á viðeigandi stað.

712
00:57:57,570 --> 00:57:59,480
Við ætlum að gera það sama.

713
00:57:59,480 --> 00:58:04,070
Þetta er í grundvallaratriðum eins og að skrifa kóðann sem við notuðum í inniheldur virka

714
00:58:04,070 --> 00:58:05,910
að finna stað þar sem hnúturinn að vera,

715
00:58:05,910 --> 00:58:10,560
og þá erum við bara að fara að setja hnút þarna.

716
00:58:10,560 --> 00:58:17,000
Við skulum byrja að gera það.

717
00:58:17,000 --> 00:58:24,200
>> Þannig að við höfum hnút * nú = rót, við erum bara að fara að fylgja inniheldur kóða

718
00:58:24,200 --> 00:58:26,850
til við komumst að því að það er ekki alveg að vinna fyrir okkur.

719
00:58:26,850 --> 00:58:32,390
Við ætlum að fara í gegnum tré meðan núverandi þátturinn er ekki núll,

720
00:58:32,390 --> 00:58:45,280
og ef við finnum gildi sem nú er jafnt gildi sem við erum að reyna að setja -

721
00:58:45,280 --> 00:58:49,600
Jæja, þetta er eitt af þeim tilvikum þar sem við gátum ekki raunverulega setja hnút

722
00:58:49,600 --> 00:58:52,730
í tré vegna þess að þetta þýðir að við erum með afrit gildi.

723
00:58:52,730 --> 00:58:59,010
Hér erum við í raun að fara að skila falskur.

724
00:58:59,010 --> 00:59:08,440
Nú, annars ef gildi nú er minna en gildi,

725
00:59:08,440 --> 00:59:10,930
Nú vitum við að við að færa til hægri

726
00:59:10,930 --> 00:59:17,190
 því gildið tilheyrir í hægri hluta gjaldmiðli tré.

727
00:59:17,190 --> 00:59:30,110
Annars erum við að fara að flytja til vinstri.

728
00:59:30,110 --> 00:59:37,980
Það er í grundvallaratriðum Contains okkar virka rétt þar.

729
00:59:37,980 --> 00:59:41,820
>> Á þessum tímapunkti, þegar við höfum lokið þessu while lykkju,

730
00:59:41,820 --> 00:59:47,350
nú músina okkar er að fara að benda á að null

731
00:59:47,350 --> 00:59:51,540
hvort aðgerðin hefur ekki nú þegar skilað.

732
00:59:51,540 --> 00:59:58,710
Við erum því með veik á stað þar sem við viljum að setja nýjan hnút.

733
00:59:58,710 --> 01:00:05,210
Hvað þarf að gera er að í raun byggja nýjan hnút,

734
01:00:05,210 --> 01:00:08,480
sem við getum gert nokkuð auðveldlega.

735
01:00:08,480 --> 01:00:14,930
Við getum notað frábær handlaginn byggja hnút okkar virka,

736
01:00:14,930 --> 01:00:17,210
og eitthvað sem við vissum ekki fyrr -

737
01:00:17,210 --> 01:00:21,400
við bara svona tók sem sjálfsagðan hlut, en nú munum við ekki bara að ganga úr skugga um -

738
01:00:21,400 --> 01:00:27,130
við munum prófa að ganga úr skugga um að gildi aftur með nýja hnút var í raun

739
01:00:27,130 --> 01:00:33,410
ekki null, vegna þess að við viljum ekki að byrja aðgang að minni ef það er núll.

740
01:00:33,410 --> 01:00:39,910
Við getum prófað til að tryggja að nýr hnútur er ekki jafnt og null.

741
01:00:39,910 --> 01:00:42,910
Eða í staðinn, getum við bara sjá hvort það er í raun núll,

742
01:00:42,910 --> 01:00:52,120
og ef það er núll, þá getum við bara aftur falskur snemma.

743
01:00:52,120 --> 01:00:59,090
>> Á þessum tímapunkti verðum við að vírinn nýjan hnút í viðeigandi stað hennar í trénu.

744
01:00:59,090 --> 01:01:03,510
Ef við lítum til baka á aðal og þar sem við vorum í raun raflögn í gildi áður,

745
01:01:03,510 --> 01:01:08,470
sjáum við hvernig við vorum að gera það þegar við vildum að setja 3 í trénu

746
01:01:08,470 --> 01:01:11,750
var við að nálgast vinstra barn rót.

747
01:01:11,750 --> 01:01:14,920
Þegar við setja 9 í trénu, við þurftum að fá aðgang að rétt barn rót.

748
01:01:14,920 --> 01:01:21,030
Við þurftum að hafa músina til foreldris í því skyni að setja inn nýtt gildi í tré.

749
01:01:21,030 --> 01:01:24,430
Fletta aftur upp að setja inn, það er ekki að fara að alveg að vinna hérna

750
01:01:24,430 --> 01:01:27,550
vegna þess að við höfum ekki foreldri músina.

751
01:01:27,550 --> 01:01:31,650
Það sem við viljum vera fær um að gera er að, á þessum tímapunkti,

752
01:01:31,650 --> 01:01:37,080
athuga gildi foreldris og sjá - og, nei,

753
01:01:37,080 --> 01:01:41,990
Ef gildi foreldris er minna en núverandi gildi,

754
01:01:41,990 --> 01:01:54,440
þá rétt barn foreldris skal nýja hnút;

755
01:01:54,440 --> 01:02:07,280
Annars vinstri barn foreldris ætti að vera nýr hnútur.

756
01:02:07,280 --> 01:02:10,290
En höfum við ekki þetta foreldri músina alveg enn.

757
01:02:10,290 --> 01:02:15,010
>> Til þess að fá það, við erum í raun að fara að fylgjast með því sem við förum í gegnum tré

758
01:02:15,010 --> 01:02:18,440
og finna viðeigandi stað í lykkju okkar ofan.

759
01:02:18,440 --> 01:02:26,840
Við getum gert það með því að fletta aftur upp að ofan virka setja inn okkar

760
01:02:26,840 --> 01:02:32,350
og rekja aðra músina breytu kallast foreldri.

761
01:02:32,350 --> 01:02:39,340
Við erum að fara að setja það jafnt null upphafi,

762
01:02:39,340 --> 01:02:43,640
og þá í hvert skipti sem við förum í gegnum tré,

763
01:02:43,640 --> 01:02:51,540
við erum að fara að setja foreldri músina til að passa við núverandi músina.

764
01:02:51,540 --> 01:02:59,140
Setja foreldri jafn gjald.

765
01:02:59,140 --> 01:03:02,260
This vegur, í hvert sinn sem við förum í gegnum,

766
01:03:02,260 --> 01:03:05,550
við erum að fara til að tryggja að þegar núverandi bendill fær incremented

767
01:03:05,550 --> 01:03:12,640
foreldri bendillinn segir það - bara eitt stig hærra en núverandi músina í trénu.

768
01:03:12,640 --> 01:03:17,370
Það allt lítur mjög vel út.

769
01:03:17,370 --> 01:03:22,380
>> Ég held að það eina sem við munum vilja til að stilla er þetta byggja hnút koma aftur null.

770
01:03:22,380 --> 01:03:25,380
Til þess að fá að byggja hnút í raun tekist aftur null,

771
01:03:25,380 --> 01:03:31,060
við verðum að breyta því kóða,

772
01:03:31,060 --> 01:03:37,270
því hér, prófað við aldrei að ganga úr skugga um að malloc skilaði gilt músina.

773
01:03:37,270 --> 01:03:53,390
Svo, ef (n = NULL!), Þá -

774
01:03:53,390 --> 01:03:55,250
ef malloc skilaði gilt músina, þá munum við að frumstilla hana,

775
01:03:55,250 --> 01:04:02,540
Annars munum við bara aftur og það mun á endanum aftur null fyrir okkur.

776
01:04:02,540 --> 01:04:13,050
Nú lítur allt mjög vel út. Við skulum vera viss um þetta í raun vinnur.

777
01:04:13,050 --> 01:04:22,240
Gera tvöfaldur tré, og ó, að við höfum fengið smá dót að fara á hér.

778
01:04:22,240 --> 01:04:29,230
>> Við höfum fengið óbeina yfirlýsingu um virka byggja hnút.

779
01:04:29,230 --> 01:04:31,950
Aftur með þessar vistþýðendur, við erum að fara að byrja á toppnum.

780
01:04:31,950 --> 01:04:36,380
Hvað það að þýða að ég er að hringja byggja hnút áður en ég hef reyndar lýst því.

781
01:04:36,380 --> 01:04:37,730
Við skulum fara aftur til kóðann virkilega fljótt.

782
01:04:37,730 --> 01:04:43,510
Flettu niður, og viss nógur, setja virka minn er lýst

783
01:04:43,510 --> 01:04:47,400
ofan byggja hnút virka,

784
01:04:47,400 --> 01:04:50,070
en ég er að reyna að nota byggja hnút inni insert.

785
01:04:50,070 --> 01:05:06,610
Ég ætla að fara í og ​​afrita - og þá líma byggja hnút virka leið upp hér að ofan.

786
01:05:06,610 --> 01:05:11,750
Þannig vonandi sem vilja vinna. Við skulum gefa þessu annað fara.

787
01:05:11,750 --> 01:05:18,920
Nú safnar það allt. Allt er gott.

788
01:05:18,920 --> 01:05:21,640
>> En á þessum tímapunkti, höfum við í raun ekki kallað Insert function okkar.

789
01:05:21,640 --> 01:05:26,510
Við vitum bara að það safnar, þannig að við skulum fara í og ​​setja nokkur símtöl inn

790
01:05:26,510 --> 01:05:28,240
Við skulum gera það í meginvirkni okkar.

791
01:05:28,240 --> 01:05:32,390
Hér, sagði við út 5, 8, og 2,

792
01:05:32,390 --> 01:05:36,680
og þá erum við ekki þráð þá upp hérna.

793
01:05:36,680 --> 01:05:41,640
Við skulum gera nokkrar símtöl til að setja,

794
01:05:41,640 --> 01:05:46,440
og við skulum líka nota sams konar efni sem við notuðum

795
01:05:46,440 --> 01:05:52,810
þegar við gert þessar printf símtöl til að tryggja að allt var að fá sett rétt.

796
01:05:52,810 --> 01:06:00,550
Ég ætla að afrita og líma,

797
01:06:00,550 --> 01:06:12,450
og í stað þess að finna að við erum að fara að gera Insert.

798
01:06:12,450 --> 01:06:30,140
Og í stað 6, 10, og 1, þá ætlum við að nota 5, 8 og 2.

799
01:06:30,140 --> 01:06:37,320
Þetta ætti vonandi að setja 5, 8 og 2 í tré.

800
01:06:37,320 --> 01:06:44,050
Safna saman. Allt er gott. Nú munum við í raun að keyra kerfi okkar.

801
01:06:44,050 --> 01:06:47,330
>> Allt skilaði rangar.

802
01:06:47,330 --> 01:06:53,830
Svo, 5, 8, og 2 ekki fara, og það lítur út eins Inniheldur ekki finna þá heldur.

803
01:06:53,830 --> 01:06:58,890
Hvað er að gerast? Við skulum súmma út.

804
01:06:58,890 --> 01:07:02,160
Fyrsta vandamálið var að setja virtist aftur rangt,

805
01:07:02,160 --> 01:07:08,750
og það lítur út eins og það er vegna þess að við fórum í staðinn okkar rangar símtali

806
01:07:08,750 --> 01:07:14,590
og við aldrei aftur satt.

807
01:07:14,590 --> 01:07:17,880
Við getum sett það upp.

808
01:07:17,880 --> 01:07:25,290
Annað vandamál er, nú jafnvel ef við gerum - vista þetta, hætta þessu,

809
01:07:25,290 --> 01:07:34,530
hlaupa að aftur, hafa þýða það, þá hlaupa það -

810
01:07:34,530 --> 01:07:37,670
sjáum við að eitthvað annað gerðist hér.

811
01:07:37,670 --> 01:07:42,980
The 5, 8, og 2 voru samt aldrei finna í trénu.

812
01:07:42,980 --> 01:07:44,350
Svo, hvað er að gerast?

813
01:07:44,350 --> 01:07:45,700
>> Við skulum taka a líta á þetta í reglunum.

814
01:07:45,700 --> 01:07:49,790
Við skulum sjá hvort við getum fundið þetta út.

815
01:07:49,790 --> 01:07:57,940
Við byrjum með foreldri ekki vera null.

816
01:07:57,940 --> 01:07:59,510
Við setjum núverandi bendilinn jafn rót músina,

817
01:07:59,510 --> 01:08:04,280
og við erum að fara að vinna okkur niður í gegnum tré.

818
01:08:04,280 --> 01:08:08,650
Ef núverandi hnút er ekki núll, þá vitum við að við getum flutt niður svolítið.

819
01:08:08,650 --> 01:08:12,330
Við setjum foreldri músina okkar til að vera jöfn núverandi músina,

820
01:08:12,330 --> 01:08:15,420
skoðaði gildi - ef gildin eru þau sömu við aftur rangar.

821
01:08:15,420 --> 01:08:17,540
Ef gildin eru minni fluttum við til hægri;

822
01:08:17,540 --> 01:08:20,399
Annars flutti við til vinstri.

823
01:08:20,399 --> 01:08:24,220
Þá erum við að byggja upp hnút. Ég stækka smá.

824
01:08:24,220 --> 01:08:31,410
Og hér erum við að fara að reyna að vírinn upp gildi að vera sú sama.

825
01:08:31,410 --> 01:08:37,250
Hvað er að gerast? Við skulum sjá hvort hugsanlega Valgrind getur gefið okkur vísbendingu.

826
01:08:37,250 --> 01:08:43,910
>> Ég vil nota Valgrind bara vegna Valgrind raun hleypur

827
01:08:43,910 --> 01:08:46,729
og segir þér ef það eru einhverjar minni villur.

828
01:08:46,729 --> 01:08:48,300
Þegar við hlaupum Valgrind á kóða,

829
01:08:48,300 --> 01:08:55,859
eins og þú sérð rétt here--Valgrind./binary_tree--and högg inn.

830
01:08:55,859 --> 01:09:03,640
Þú sérð að við vildum ekki hafa allir minni villa, þannig að það lítur út eins og allt er í lagi svo langt.

831
01:09:03,640 --> 01:09:07,529
Við gera hafa sumir minni lekur, sem við þekkjum, vegna þess að við erum ekki

832
01:09:07,529 --> 01:09:08,910
gerast til að losa eitthvað af hnúður okkar.

833
01:09:08,910 --> 01:09:13,050
Við skulum reyna að keyra gdb til að sjá hvað er í raun að gerast.

834
01:09:13,050 --> 01:09:20,010
Við munum gera gdb. / Binary_tree. Það stígvélum upp bara fínt.

835
01:09:20,010 --> 01:09:23,670
Við skulum setja brjóta lið á Insert.

836
01:09:23,670 --> 01:09:28,600
Við skulum hlaupa.

837
01:09:28,600 --> 01:09:31,200
Það lítur út eins og við aldrei kallað setja.

838
01:09:31,200 --> 01:09:39,410
Það lítur út eins og að vandamálið var bara að þegar ég breytt niður í aðal -

839
01:09:39,410 --> 01:09:44,279
allar þessar printf símtöl frá inniheldur -

840
01:09:44,279 --> 01:09:56,430
Ég hef aldrei raunverulega breytt þetta til að hringja inn.

841
01:09:56,430 --> 01:10:01,660
Nú skulum við gefa það a reyna. Við skulum taka saman.

842
01:10:01,660 --> 01:10:09,130
Allt lítur vel út þar. Nú skulum reyna að keyra það, sjá hvað gerist.

843
01:10:09,130 --> 01:10:13,320
Alright! Allt lítur nokkuð það gott.

844
01:10:13,320 --> 01:10:18,130
>> Endanleg hlutur til að hugsa um er, eru einhverjar brún tilvikum á þessu setja inn?

845
01:10:18,130 --> 01:10:23,170
Og það kemur í ljós að vel, sá brún ef það er alltaf áhugavert að hugsa um

846
01:10:23,170 --> 01:10:26,250
er, hvað gerist ef tré er tómur og þú kallar þetta setja inn virka?

847
01:10:26,250 --> 01:10:30,330
Mun það virka? Jæja, við skulum gefa það a reyna.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Leiðin sem við erum að fara að prófa þetta er, við erum að fara niður í virkni okkar,

850
01:10:35,810 --> 01:10:41,690
og frekar en raflögn þessa tengipunkta upp svona,

851
01:10:41,690 --> 01:10:56,730
við erum bara að fara að tjá sig út um allt hlutur,

852
01:10:56,730 --> 01:11:02,620
og í stað þess að raflögn upp hnúður sjálf,

853
01:11:02,620 --> 01:11:09,400
getum við í raun bara að fara á undan og eyða þessu öllu.

854
01:11:09,400 --> 01:11:17,560
Við ætlum að gera allt hringja til að setja inn.

855
01:11:17,560 --> 01:11:49,020
Svo skulum við gera - í stað 5, 8, og 2, við erum að fara að setja inn 7, 3 og 9.

856
01:11:49,020 --> 01:11:58,440
Og þá munum við einnig vilja til að setja 6 eins og heilbrigður.

857
01:11:58,440 --> 01:12:05,190
Vista. Hætta. Gerðu tvöfaldur tré.

858
01:12:05,190 --> 01:12:08,540
Það safnar öllum.

859
01:12:08,540 --> 01:12:10,320
Við getum bara hlaupa það er eins og sjá hvað gerist,

860
01:12:10,320 --> 01:12:12,770
en það er líka að fara að vera mjög mikilvægt að ganga úr skugga um að

861
01:12:12,770 --> 01:12:14,740
Við höfum engar minni villur,

862
01:12:14,740 --> 01:12:16,840
þar sem þetta er eitt af þeim tilvikum brún okkar sem við vitum um.

863
01:12:16,840 --> 01:12:20,150
>> Við skulum vera viss um að það virkar vel á Valgrind,

864
01:12:20,150 --> 01:12:28,310
sem við munum gera við bara að keyra Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Það lítur út eins og við höfum örugglega eina villu úr einu samhengi -

866
01:12:31,110 --> 01:12:33,790
við höfum þetta skiptingu kenna.

867
01:12:33,790 --> 01:12:36,690
Hvað gerðist?

868
01:12:36,690 --> 01:12:41,650
Valgrind segir reyndar okkur hvar það er.

869
01:12:41,650 --> 01:12:43,050
Minnka svolítið.

870
01:12:43,050 --> 01:12:46,040
Það lítur út eins og það er að gerast í aðgerð setja inn okkar,

871
01:12:46,040 --> 01:12:53,420
þar sem við höfum ógilt lesa af stærð 4 á insert, lína 60.

872
01:12:53,420 --> 01:13:03,590
Við skulum fara til baka og sjá hvað er að gerast hér.

873
01:13:03,590 --> 01:13:05,350
Minnka mjög fljótur.

874
01:13:05,350 --> 01:13:14,230
Ég vil vera viss um að það er ekki að fara að brún skjásins þannig að við getum séð allt.

875
01:13:14,230 --> 01:13:18,760
Dragðu að í smá. Alright.

876
01:13:18,760 --> 01:13:35,030
Flettu niður og vandamálið er hérna.

877
01:13:35,030 --> 01:13:40,120
Hvað gerist ef við fá niður og núverandi hnút okkar er þegar núll,

878
01:13:40,120 --> 01:13:44,010
foreldri hnút okkar er núll, þannig að ef við horfum upp á mjög toppur, hérna -

879
01:13:44,010 --> 01:13:47,340
Ef þetta á meðan lykkja aldrei framkvæmir

880
01:13:47,340 --> 01:13:52,330
vegna núverandi gildi okkar er núll - rót okkar er núll svo nú er núll -

881
01:13:52,330 --> 01:13:57,810
þá foreldri okkar aldrei fær sett gjald eða gilt gildi,

882
01:13:57,810 --> 01:14:00,580
svo, foreldri verður einnig null.

883
01:14:00,580 --> 01:14:03,700
Við þurfum að muna að athuga fyrir það

884
01:14:03,700 --> 01:14:08,750
Þegar við fá niður hér og við byrjum að fá aðgang að gildi foreldris.

885
01:14:08,750 --> 01:14:13,190
Svo, hvað gerist? Jæja, ef foreldri er núll -

886
01:14:13,190 --> 01:14:17,990
if (foreldri == NULL) - þá vitum við að

887
01:14:17,990 --> 01:14:19,530
Það má ekki vera neitt í trénu.

888
01:14:19,530 --> 01:14:22,030
Við verðum að reyna að setja það á the rót.

889
01:14:22,030 --> 01:14:32,570
Við getum gert það með því bara að setja rót jafnt nýja hnút.

890
01:14:32,570 --> 01:14:40,010
Þá á þessum tímapunkti, er það ekki raunverulega vilja til að fara í gegnum þessar annars.

891
01:14:40,010 --> 01:14:44,780
Þess í stað, hérna, getum við gert annaðhvort annað-hvort-annað,

892
01:14:44,780 --> 01:14:47,610
eða við gætum sameina allt upp hér er annað,

893
01:14:47,610 --> 01:14:56,300
en hér við verðum bara að nota annað og gera það þannig.

894
01:14:56,300 --> 01:14:59,030
Nú ætlum við að prófa að tryggja að foreldri okkar er ekki null

895
01:14:59,030 --> 01:15:02,160
áður en þá í raun að reyna að fá aðgang viðfangsefnum hennar.

896
01:15:02,160 --> 01:15:05,330
Þetta mun hjálpa okkur að koma í veg fyrir skiptingu kenna.

897
01:15:05,330 --> 01:15:14,740
Svo, við hætta, minnka, safna saman, hlaupa.

898
01:15:14,740 --> 01:15:18,130
>> Engin villa, en við höfum samt fullt af leka minni

899
01:15:18,130 --> 01:15:20,650
vegna þess að við vissum ekki að losa eitthvað af hnúður okkar.

900
01:15:20,650 --> 01:15:24,350
En ef við förum hér upp og við lítum á útprentun okkar,

901
01:15:24,350 --> 01:15:30,880
sjáum við að vel lítur, eins og öll sett inn okkar voru aftur satt, sem er gott.

902
01:15:30,880 --> 01:15:33,050
The sett er allt satt,

903
01:15:33,050 --> 01:15:36,670
og síðan viðeigandi inniheldur símtöl eru einnig satt.

904
01:15:36,670 --> 01:15:41,510
>> Gott starf! Það lítur út eins og við höfum tekist skrifað inn.

905
01:15:41,510 --> 01:15:47,430
Það er allt sem við höfum fyrir Problem Set Specification þessari viku.

906
01:15:47,430 --> 01:15:51,720
Ein skemmtileg áskorun að hugsa um er hvernig þú myndi reyndar fara í

907
01:15:51,720 --> 01:15:55,340
og frjáls öllum hnúður í þessu tré.

908
01:15:55,340 --> 01:15:58,830
Við getum gert það í mörgum mismunandi vegu,

909
01:15:58,830 --> 01:16:01,930
en ég skal fara að allt að þér að prófa,

910
01:16:01,930 --> 01:16:06,080
og sem gaman áskorun, reyna að ganga úr skugga um að þú getur gengið úr skugga

911
01:16:06,080 --> 01:16:09,490
að Valgrind skýrslu skilar engar villur og enginn leki.

912
01:16:09,490 --> 01:16:12,880
>> Gangi þér vel á þessari viku Huffman kóðun vandamál setja,

913
01:16:12,880 --> 01:16:14,380
og við munum sjá þig í næstu viku!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]