1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Avsnitt 7] [mindre bekväm]

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

3
00:00:04,890 --> 00:00:07,000
[Detta är CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Välkommen till avsnitt 7.

5
00:00:09,080 --> 00:00:11,330
Tack vare orkanen Sandy,

6
00:00:11,330 --> 00:00:13,440
istället för att ha en normal del den här veckan,

7
00:00:13,440 --> 00:00:17,650
vi gör detta genomgång, genom den del av frågorna.

8
00:00:17,650 --> 00:00:22,830
Jag kommer att följa tillsammans med problemet Set 6 Specifikation,

9
00:00:22,830 --> 00:00:25,650
och går igenom alla frågor i

10
00:00:25,650 --> 00:00:27,770
En del av frågorna avsnitt.

11
00:00:27,770 --> 00:00:30,940
Om det finns några frågor,

12
00:00:30,940 --> 00:00:32,960
posta dessa på CS50 diskutera.

13
00:00:32,960 --> 00:00:35,480
>> Okej. Låt oss komma igång.

14
00:00:35,480 --> 00:00:40,780
Just nu är jag tittar på sidan 3 i problembild specifikationen.

15
00:00:40,780 --> 00:00:44,110
Vi kommer att först börja tala om binära träd

16
00:00:44,110 --> 00:00:47,850
eftersom de har en hel del relevans för denna veckas problem set -

17
00:00:47,850 --> 00:00:49,950
Huffman Tree kodning.

18
00:00:49,950 --> 00:00:55,000
En av de allra första datastrukturer vi pratade om på CS50 var matrisen.

19
00:00:55,000 --> 00:01:00,170
Kom ihåg att en array är en sekvens av element -

20
00:01:00,170 --> 00:01:04,019
alla av samma typ - lagras intill varandra i minnet.

21
00:01:04,019 --> 00:01:14,420
Om jag har ett heltal array som jag kan rita använda denna lådor-nummer-tal stil -

22
00:01:14,420 --> 00:01:20,290
Låt oss säga att jag har 5 i den första rutan, jag har 7 i den andra,

23
00:01:20,290 --> 00:01:27,760
då har jag 8, 10 och 20 i den slutliga lådan.

24
00:01:27,760 --> 00:01:33,000
Kom ihåg att två riktigt bra saker om denna array

25
00:01:33,000 --> 00:01:38,800
är att vi har denna konstant gången tillgång till en viss del

26
00:01:38,800 --> 00:01:40,500
 i arrayen om vi vet sitt index.

27
00:01:40,500 --> 00:01:44,670
Till exempel, om jag vill ta den tredje element i arrayen -

28
00:01:44,670 --> 00:01:47,870
vid index 2 med hjälp av vår noll-indexering system -

29
00:01:47,870 --> 00:01:52,220
Jag bokstavligen bara måste göra en enkel matematisk beräkning,

30
00:01:52,220 --> 00:01:56,170
hoppa till den positionen i gruppen,

31
00:01:56,170 --> 00:01:57,840
dra ut 8 som lagras där,

32
00:01:57,840 --> 00:01:59,260
och jag är bra att gå.

33
00:01:59,260 --> 00:02:03,350
>> En av de dåliga sakerna om detta array - att vi pratade om

34
00:02:03,350 --> 00:02:05,010
när vi diskuterade länkade listor -

35
00:02:05,010 --> 00:02:09,120
är att om jag vill infoga ett element i denna array

36
00:02:09,120 --> 00:02:11,090
Jag kommer att behöva göra några flytta runt.

37
00:02:11,090 --> 00:02:12,940
Till exempel denna array här

38
00:02:12,940 --> 00:02:16,850
är sorterad ordning - sorterade i stigande ordning -

39
00:02:16,850 --> 00:02:19,440
5, 7 och sedan, då 8, sedan 10, och därefter 20 -

40
00:02:19,440 --> 00:02:23,100
men om jag vill infoga numret 9 i denna array

41
00:02:23,100 --> 00:02:27,460
Jag kommer att behöva flytta vissa delar för att göra plats.

42
00:02:27,460 --> 00:02:30,440
Vi kan dra ut det här.

43
00:02:30,440 --> 00:02:35,650
Jag kommer att behöva flytta 5, den 7 och sedan 8;

44
00:02:35,650 --> 00:02:38,720
skapa en lucka där jag kan sätta 9,

45
00:02:38,720 --> 00:02:45,910
och därefter 10 och 20 kan gå till höger om 9.

46
00:02:45,910 --> 00:02:49,450
Detta är typ av en smärta eftersom det värsta scenariot -

47
00:02:49,450 --> 00:02:54,350
när vi behöver sätta in antingen i början eller i slutet

48
00:02:54,350 --> 00:02:56,040
av matrisen, beroende på hur vi flytta -

49
00:02:56,040 --> 00:02:58,850
vi kan sluta med att flytta alla element

50
00:02:58,850 --> 00:03:00,750
att vi nu lagrar i arrayen.

51
00:03:00,750 --> 00:03:03,810
>> Så, vad var det väg runt detta?

52
00:03:03,810 --> 00:03:09,260
Vägen runt detta var att gå till vår länkade-lista metod där -

53
00:03:09,260 --> 00:03:19,820
stället för att lagra elementen 5, 7, 8, 10, och 20 alla bredvid varandra i minnet -

54
00:03:19,820 --> 00:03:25,630
Vad vi istället gjorde var lagra dem slags överallt där vi ville lagra dem

55
00:03:25,630 --> 00:03:32,470
i dessa länkade-lista noder som jag drar ut här, typ av ad hoc.

56
00:03:32,470 --> 00:03:42,060
Och vi kopplas ihop dem med hjälp av dessa nästa pekare.

57
00:03:42,060 --> 00:03:44,370
Jag kan ha en pekare från 5 till 7,

58
00:03:44,370 --> 00:03:46,420
en pekare från 7 till 8,

59
00:03:46,420 --> 00:03:47,770
en pekare från 8 till 10,

60
00:03:47,770 --> 00:03:51,220
och slutligen, en pekare från 10 till 20,

61
00:03:51,220 --> 00:03:54,880
och sedan en null-pekare vid 20 indikerar att det inte finns något kvar.

62
00:03:54,880 --> 00:03:59,690
Avvägningen som vi har här

63
00:03:59,690 --> 00:04:05,360
är att nu om vi vill in numret 9 i vår sorterad lista,

64
00:04:05,360 --> 00:04:08,270
allt vi behöver göra är att skapa en ny nod med 9,

65
00:04:08,270 --> 00:04:12,290
ansluta den upp för att peka på lämplig plats,

66
00:04:12,290 --> 00:04:20,630
och därefter åter-tråd 8 till peka nedåt till 9.

67
00:04:20,630 --> 00:04:25,660
Det är ganska snabbt, förutsatt att vi vet exakt var vi vill infoga 9.

68
00:04:25,660 --> 00:04:32,610
Men avvägningen i utbyte för detta är att vi nu har förlorat konstant tid åtkomst

69
00:04:32,610 --> 00:04:36,230
till någon speciell del av vårt datastruktur.

70
00:04:36,230 --> 00:04:40,950
Till exempel, om jag vill hitta det fjärde elementet i denna länkad lista,

71
00:04:40,950 --> 00:04:43,510
Jag kommer att behöva börja från början av listan

72
00:04:43,510 --> 00:04:48,930
och arbeta mig igenom räkna nod-för-nod tills jag hittar den fjärde.

73
00:04:48,930 --> 00:04:55,870
>> För att få bättre tillgång prestanda än en länkad lista -

74
00:04:55,870 --> 00:04:59,360
men också behålla en del av de fördelar som vi hade

75
00:04:59,360 --> 00:05:01,800
i termer av insättningsregionen tid från en länkad lista -

76
00:05:01,800 --> 00:05:05,750
ett binärt träd kommer att behöva använda lite mer minne.

77
00:05:05,750 --> 00:05:11,460
I synnerhet, i stället för att bara ha en pekare i ett binärt träd nod -

78
00:05:11,460 --> 00:05:13,350
som länkade-lista nod gör -

79
00:05:13,350 --> 00:05:16,950
vi kommer att lägga till en andra pekare till den binära nod.

80
00:05:16,950 --> 00:05:19,950
Snarare än att bara ha en pekare till nästa element,

81
00:05:19,950 --> 00:05:24,420
vi kommer att ha en pekare till en vänster barn och en höger barn.

82
00:05:24,420 --> 00:05:26,560
>> Låt oss rita en bild för att se vad som faktiskt ser ut.

83
00:05:26,560 --> 00:05:31,350
Återigen, jag kommer att använda dessa rutor och pilar.

84
00:05:31,350 --> 00:05:37,150
En binär trädnod kommer att börja med bara en enkel låda.

85
00:05:37,150 --> 00:05:40,940
Det kommer att ha en plats för värdet,

86
00:05:40,940 --> 00:05:47,280
och då är det också kommer att ha ett utrymme för vänster barnet och rätt barn.

87
00:05:47,280 --> 00:05:49,280
Jag ska märka dem här.

88
00:05:49,280 --> 00:05:57,560
Vi kommer att ha den vänstra barnet, och sedan ska vi ha rätt barn.

89
00:05:57,560 --> 00:05:59,920
Det finns många olika sätt att göra detta.

90
00:05:59,920 --> 00:06:02,050
Ibland för utrymme och bekvämlighet,

91
00:06:02,050 --> 00:06:06,460
Jag ska faktiskt dra det som jag gör här på botten

92
00:06:06,460 --> 00:06:10,910
där jag kommer att ha värdet vid toppen,

93
00:06:10,910 --> 00:06:14,060
och sedan den högra barnet på nedre högra,

94
00:06:14,060 --> 00:06:16,060
och den vänstra barnet på nedre vänstra.

95
00:06:16,060 --> 00:06:20,250
Att gå tillbaka till denna övre diagram,

96
00:06:20,250 --> 00:06:22,560
Vi har värdet högst upp,

97
00:06:22,560 --> 00:06:25,560
då har vi den vänstra barnet pekare och sedan har vi rätt-barn pekare.

98
00:06:25,560 --> 00:06:30,110
>> I problembild Specification,

99
00:06:30,110 --> 00:06:33,110
Vi talar om att dra en nod som har ett värde 7,

100
00:06:33,110 --> 00:06:39,750
och sedan en vänster-barn pekare som är null, och en höger-barn pekare som är null.

101
00:06:39,750 --> 00:06:46,040
Vi kan antingen skriva kapital NULL i utrymmet för

102
00:06:46,040 --> 00:06:51,610
både vänster barnet och den högra barnet, eller vi kan dra denna diagonala snedstreck

103
00:06:51,610 --> 00:06:53,750
genom respektive ruta för att ange att det är noll.

104
00:06:53,750 --> 00:06:57,560
Jag ska göra det bara för att det är enklare.

105
00:06:57,560 --> 00:07:03,700
Det du ser här är två sätt att diagram en mycket enkel nod binärt träd

106
00:07:03,700 --> 00:07:07,960
där vi har värdet 7 och noll pekare barn.

107
00:07:07,960 --> 00:07:15,220
>> Den andra delen av vår specifikation talar om hur med länkade listor -

108
00:07:15,220 --> 00:07:18,270
kom ihåg, vi hade bara att hålla fast vid den allra första elementet i en lista

109
00:07:18,270 --> 00:07:20,270
att komma ihåg hela listan -

110
00:07:20,270 --> 00:07:26,140
och likaså, med ett binärt träd, har vi bara att hålla fast vid en pekare till trädet

111
00:07:26,140 --> 00:07:31,120
För att upprätthålla kontrollen över hela datastrukturen.

112
00:07:31,120 --> 00:07:36,150
Denna speciella del av trädet kallas rotnoden av trädet.

113
00:07:36,150 --> 00:07:43,360
Till exempel, om denna nod - denna nod innehåller värdet 7

114
00:07:43,360 --> 00:07:45,500
med noll vänster och höger barn pekare -

115
00:07:45,500 --> 00:07:47,360
var det enda värdet i vår träd,

116
00:07:47,360 --> 00:07:50,390
då detta skulle vara vår rotnoden.

117
00:07:50,390 --> 00:07:52,240
Det är början av vår träd.

118
00:07:52,240 --> 00:07:58,530
Vi kan se detta lite tydligare när vi börjar lägga till fler noder i vårt träd.

119
00:07:58,530 --> 00:08:01,510
Låt mig dra upp en ny sida.

120
00:08:01,510 --> 00:08:05,000
>> Nu ska vi dra ett träd som har 7 vid roten,

121
00:08:05,000 --> 00:08:10,920
och 3 insidan av vänstra underordnade, och 9 inuti det högra underordnade.

122
00:08:10,920 --> 00:08:13,500
Återigen, detta är ganska enkel.

123
00:08:13,500 --> 00:08:26,510
Vi har 7, rita en nod för 3, en nod för 9,

124
00:08:26,510 --> 00:08:32,150
och jag kommer att ställa den vänstra barnet pekare av 7 för att peka på noden som innehåller 3,

125
00:08:32,150 --> 00:08:37,850
och den högra barnet pekare för den nod som innehåller 7 till noden innehållande 9.

126
00:08:37,850 --> 00:08:42,419
Nu har sedan 3 och 9 inte några barn,

127
00:08:42,419 --> 00:08:48,500
vi kommer att ställa alla sina barn pekare som noll.

128
00:08:48,500 --> 00:08:56,060
Här motsvarar roten av vår träd till noden innehåller numret 7.

129
00:08:56,060 --> 00:09:02,440
Du kan se att om allt vi har är en pekare till den rotnod,

130
00:09:02,440 --> 00:09:07,330
Vi kan sedan gå igenom vår träd och öppna både underordnade noder -

131
00:09:07,330 --> 00:09:10,630
både 3 och 9.

132
00:09:10,630 --> 00:09:14,820
Du behöver inte hålla pekare till varje enskild nod i trädet.

133
00:09:14,820 --> 00:09:22,080
Okej. Nu ska vi lägga till en annan nod detta diagram.

134
00:09:22,080 --> 00:09:25,370
Vi kommer att lägga till en nod som innehåller 6,

135
00:09:25,370 --> 00:09:34,140
och vi kommer att lägga detta som den rätta barn noden innehåller 3.

136
00:09:34,140 --> 00:09:41,850
För att göra det, kommer jag att radera den null-pekare i 3-noden

137
00:09:41,850 --> 00:09:47,750
och ansluta den upp för att peka på noden innehållande 6. Okej.

138
00:09:47,750 --> 00:09:53,800
>> Vid denna punkt, låt oss gå över lite terminologi.

139
00:09:53,800 --> 00:09:58,230
Till att börja med på grund av att detta kallas ett binärt träd i synnerhet

140
00:09:58,230 --> 00:10:00,460
är att den har två underordnade pekare.

141
00:10:00,460 --> 00:10:06,020
Det finns andra typer av träd som har fler barn pekare.

142
00:10:06,020 --> 00:10:10,930
I synnerhet gjorde du en "prova" i problembild 5.

143
00:10:10,930 --> 00:10:19,310
Du kommer att märka att i det försök, hade du 27 olika pekare till olika barn -

144
00:10:19,310 --> 00:10:22,410
en för vardera av de 26 bokstäverna i det engelska alfabetet,

145
00:10:22,410 --> 00:10:25,410
och sedan den 27: e för apostrof -

146
00:10:25,410 --> 00:10:28,900
så, det är liknande en typ av träd.

147
00:10:28,900 --> 00:10:34,070
Men här, eftersom det är binära, har vi bara två barn pekare.

148
00:10:34,070 --> 00:10:37,880
>> Utöver detta rotnoden som vi talade om,

149
00:10:37,880 --> 00:10:41,470
Vi har också kastat runt denna term "barn".

150
00:10:41,470 --> 00:10:44,470
Vad betyder det för en nod är ett barn av en annan nod?

151
00:10:44,470 --> 00:10:54,060
Det betyder bokstavligen att ett barn nod är ett barn av en annan nod

152
00:10:54,060 --> 00:10:58,760
om den andra noden har en av dess underordnade pekare som att peka på denna nod.

153
00:10:58,760 --> 00:11:01,230
För att sätta detta i mer konkreta termer,

154
00:11:01,230 --> 00:11:11,170
om 3 pekas på av en av de underordnade pekare 7, då 3 är ett barn av 7.

155
00:11:11,170 --> 00:11:14,510
Om vi ​​skulle räkna ut vad barn 7 är -

156
00:11:14,510 --> 00:11:18,510
bra, ser vi att 7 har en pekare till 3 och en pekare till 9,

157
00:11:18,510 --> 00:11:22,190
så 9 och 3 är barn till 7.

158
00:11:22,190 --> 00:11:26,650
Nio har inga barn eftersom dess underordnade pekare är noll,

159
00:11:26,650 --> 00:11:30,940
och 3 har endast ett barn, 6.

160
00:11:30,940 --> 00:11:37,430
Sex har också några barn eftersom båda sina pekare är null, vilket vi kommer att dra nu.

161
00:11:37,430 --> 00:11:45,010
>> Dessutom talar vi också om föräldrarna till en viss nod,

162
00:11:45,010 --> 00:11:51,100
och detta är, som du förväntar dig, baksidan av detta barn beskrivning.

163
00:11:51,100 --> 00:11:58,620
Varje nod har endast en förälder - i stället för två som du kan förvänta dig med människor.

164
00:11:58,620 --> 00:12:03,390
Till exempel är förälder till 3 7.

165
00:12:03,390 --> 00:12:10,800
Förälder till 9 är också 7 och förälder 6 är 3. Inte mycket till det.

166
00:12:10,800 --> 00:12:15,720
Vi har också termer för att prata om morföräldrar och barnbarn,

167
00:12:15,720 --> 00:12:18,210
och mer generellt talar vi om förfäder

168
00:12:18,210 --> 00:12:20,960
och ättlingar till en viss nod.

169
00:12:20,960 --> 00:12:25,710
Den anfader en nod - eller förfäder snarare av en nod -

170
00:12:25,710 --> 00:12:32,730
är alla de noder som ligger på vägen från roten till den noden.

171
00:12:32,730 --> 00:12:36,640
Till exempel, om jag tittar på noden 6,

172
00:12:36,640 --> 00:12:46,430
då förfäderna kommer att vara både 3 och 7.

173
00:12:46,430 --> 00:12:55,310
Förfäder 9, till exempel, är - om jag tittar på noden 9 -

174
00:12:55,310 --> 00:12:59,990
då förfader 9 är bara 7.

175
00:12:59,990 --> 00:13:01,940
Och ättlingar är exakt tvärtom.

176
00:13:01,940 --> 00:13:05,430
Om jag vill titta på alla ättlingar 7,

177
00:13:05,430 --> 00:13:11,020
då måste jag titta på alla noder under den.

178
00:13:11,020 --> 00:13:16,950
Så har jag 3, 9 och 6 alla som ättlingar 7.

179
00:13:16,950 --> 00:13:24,170
>> Den sista terminen som vi pratar om är denna föreställning om att vara ett syskon.

180
00:13:24,170 --> 00:13:27,980
Syskon - typ av följa med på dessa familjen villkor -

181
00:13:27,980 --> 00:13:33,150
är noder som är på samma nivå i trädet.

182
00:13:33,150 --> 00:13:42,230
Så, 3 och 9 är syskon eftersom de är på samma nivå i trädet.

183
00:13:42,230 --> 00:13:46,190
De båda har samma överordnade, 7.

184
00:13:46,190 --> 00:13:51,400
Den 6 har inga syskon, eftersom 9 inte har några barn.

185
00:13:51,400 --> 00:13:55,540
Och 7 inte har några syskon eftersom det är grunden för vår träd,

186
00:13:55,540 --> 00:13:59,010
och det finns alltid bara 1 rot.

187
00:13:59,010 --> 00:14:02,260
För 7 att ha syskon skulle behöva vara en nod över 7.

188
00:14:02,260 --> 00:14:07,480
Det måste vara en förälder 7, i vilket fall 7 inte längre vara roten av trädet.

189
00:14:07,480 --> 00:14:10,480
Då den nya föräldern till 7 skulle också behöva ha ett barn,

190
00:14:10,480 --> 00:14:16,480
och att barnet skulle vara syskon 7.

191
00:14:16,480 --> 00:14:21,040
>> Okej. Går vidare.

192
00:14:21,040 --> 00:14:24,930
När vi började vår diskussion om binära träd,

193
00:14:24,930 --> 00:14:28,790
Vi talade om hur vi skulle använda dem för att

194
00:14:28,790 --> 00:14:32,800
få en fördel gentemot både arrayer och länkade listor.

195
00:14:32,800 --> 00:14:37,220
Och hur vi ska göra det är med denna beställning egenskap.

196
00:14:37,220 --> 00:14:41,080
Vi säger att ett binärt träd beställs, enligt specifikationen,

197
00:14:41,080 --> 00:14:45,740
om för varje nod i vår träd, alla dess ättlingar till vänster -

198
00:14:45,740 --> 00:14:48,670
det vänstra underordnade och alla vänstra barnets ättlingar -

199
00:14:48,670 --> 00:14:54,510
har mindre värden, och alla de noder på höger -

200
00:14:54,510 --> 00:14:57,770
rätt barn och alla rätt barnets ättlingar -

201
00:14:57,770 --> 00:15:02,800
har noder som är större än värdet på den aktuella noden som vi tittar på.

202
00:15:02,800 --> 00:15:07,850
Bara för enkelhetens skull kommer vi att anta att det inte finns några dubbletter noder i vårt träd.

203
00:15:07,850 --> 00:15:11,180
Till exempel i detta träd vi inte kommer att behandla ärendet

204
00:15:11,180 --> 00:15:13,680
där vi har värdet 7 vid roten

205
00:15:13,680 --> 00:15:16,720
 och sedan har vi också värdet 7 på andra håll i trädet.

206
00:15:16,720 --> 00:15:24,390
I det här fallet kommer du att märka att detta träd verkligen är beställd.

207
00:15:24,390 --> 00:15:26,510
Vi har värdet 7 vid roten.

208
00:15:26,510 --> 00:15:29,720
Allt till vänster om 7 -

209
00:15:29,720 --> 00:15:35,310
Om jag ångra alla dessa små märken här -

210
00:15:35,310 --> 00:15:40,450
allt till vänster om 7 - den 3 och 6 -

211
00:15:40,450 --> 00:15:49,410
dessa värden är båda mindre än 7, och allt till höger - som är just detta 9 -

212
00:15:49,410 --> 00:15:53,450
är större än 7.

213
00:15:53,450 --> 00:15:58,650
>> Detta är inte den enda beställt trädet innehåller dessa värden,

214
00:15:58,650 --> 00:16:03,120
men låt oss dra några fler av dem.

215
00:16:03,120 --> 00:16:05,030
Det finns faktiskt en hel drös olika sätt som vi kan göra det här.

216
00:16:05,030 --> 00:16:09,380
Jag kommer att använda en förkortning bara för att hålla det enkelt, där -

217
00:16:09,380 --> 00:16:11,520
snarare än att dra ut hela lådor-och-pilar -

218
00:16:11,520 --> 00:16:14,220
Jag ska bara dra siffrorna och lägga till pilar som förbinder dem.

219
00:16:14,220 --> 00:16:22,920
Till att börja med kommer vi bara skriva vår ursprungliga trädet igen där vi hade 7, och sedan en 3,

220
00:16:22,920 --> 00:16:25,590
och sedan 3 pekade tillbaka till höger till 6,

221
00:16:25,590 --> 00:16:30,890
och 7 hade rätt barn som var 9.

222
00:16:30,890 --> 00:16:33,860
Okej. Vad är ett annat sätt att vi kunde skriva detta träd?

223
00:16:33,860 --> 00:16:38,800
Istället för att ha 3 vara den vänstra barn 7,

224
00:16:38,800 --> 00:16:41,360
kunde vi också ha 6 vara den vänstra barn 7,

225
00:16:41,360 --> 00:16:44,470
och sedan 3 vara den vänstra barn till 6.

226
00:16:44,470 --> 00:16:48,520
Det skulle se ut så här trädet här där jag har 7,

227
00:16:48,520 --> 00:16:57,860
sedan 6, sedan 3 och en 9 till höger.

228
00:16:57,860 --> 00:17:01,490
Vi har inte heller ha 7 som vår rotnoden.

229
00:17:01,490 --> 00:17:03,860
Vi skulle också ha 6 som vår rotnoden.

230
00:17:03,860 --> 00:17:06,470
Vad skulle det se ut?

231
00:17:06,470 --> 00:17:09,230
Om vi ​​ska behålla denna beställda egendom,

232
00:17:09,230 --> 00:17:12,970
allt till vänster om 6 måste vara mindre än den.

233
00:17:12,970 --> 00:17:16,540
Det finns bara en möjlighet, och det är 3.

234
00:17:16,540 --> 00:17:19,869
Men sedan som höger barn 6, har vi två möjligheter.

235
00:17:19,869 --> 00:17:25,380
Först kunde vi ha 7 och sedan 9,

236
00:17:25,380 --> 00:17:28,850
eller vi kan dra det - som jag är på väg att göra här -

237
00:17:28,850 --> 00:17:34,790
där vi har 9 som rätt barn till den 6,

238
00:17:34,790 --> 00:17:39,050
och därefter 7 som vänstra underordnade av 9.

239
00:17:39,050 --> 00:17:44,240
>> Nu, 7 och 6 är inte de enda möjliga värden för roten.

240
00:17:44,240 --> 00:17:50,200
Vi skulle också ha 3 vara roten.

241
00:17:50,200 --> 00:17:52,240
Vad händer om 3 ligger till grund?

242
00:17:52,240 --> 00:17:54,390
Här, det blir lite intressant.

243
00:17:54,390 --> 00:17:58,440
Tre har inga värden som är mindre än det,

244
00:17:58,440 --> 00:18:02,070
så att hela vänstra sidan av trädet bara kommer att bli noll.

245
00:18:02,070 --> 00:18:03,230
Det kommer inte att bli något där.

246
00:18:03,230 --> 00:18:07,220
Till höger kan vi lista saker i stigande ordning.

247
00:18:07,220 --> 00:18:15,530
Vi kunde ha 3, sedan 6, sedan 7, sedan 9.

248
00:18:15,530 --> 00:18:26,710
Eller kan vi göra 3, sedan 6, sedan 9, sedan 7.

249
00:18:26,710 --> 00:18:35,020
Eller kan vi göra 3, sedan 7, sedan 6, sedan 9.

250
00:18:35,020 --> 00:18:40,950
Eller, 3, 7 - faktiskt inte, kan vi inte göra en 7 längre.

251
00:18:40,950 --> 00:18:43,330
Det är vår en sak där.

252
00:18:43,330 --> 00:18:54,710
Vi kan göra 9, och sedan från 9 vi kan göra 6 och därefter 7.

253
00:18:54,710 --> 00:19:06,980
Eller, kan vi göra 3, sedan 9, sedan 7 och sedan 6.

254
00:19:06,980 --> 00:19:12,490
>> En sak att uppmärksamma er på här är

255
00:19:12,490 --> 00:19:14,510
att dessa träd är lite konstig utseende.

256
00:19:14,510 --> 00:19:17,840
I synnerhet om vi tittar på de 4 träd på höger sida -

257
00:19:17,840 --> 00:19:20,930
Jag cirkel dem här -

258
00:19:20,930 --> 00:19:28,410
dessa träd ser nästan exakt ut som en länkad lista.

259
00:19:28,410 --> 00:19:32,670
Varje nod har endast ett barn,

260
00:19:32,670 --> 00:19:38,950
och så att vi inte har något av detta trädliknande struktur som vi ser, till exempel,

261
00:19:38,950 --> 00:19:44,720
 I detta ett ensamt träd över här på längst ner till vänster.

262
00:19:44,720 --> 00:19:52,490
Dessa träd är faktiskt kallas degenererade binära träd,

263
00:19:52,490 --> 00:19:54,170
och vi ska prata om dessa mer i framtiden -

264
00:19:54,170 --> 00:19:56,730
särskilt om du går på att ta andra kurser datavetenskap.

265
00:19:56,730 --> 00:19:59,670
Dessa träd är degenererade.

266
00:19:59,670 --> 00:20:03,780
De är inte mycket användbar eftersom, ja, ger denna struktur i sig

267
00:20:03,780 --> 00:20:08,060
 att lookup gånger som liknar en länkad lista.

268
00:20:08,060 --> 00:20:13,050
Vi får inte dra fördel av det extra minnet - denna extra pekare -

269
00:20:13,050 --> 00:20:18,840
på grund av vår struktur är dålig på detta sätt.

270
00:20:18,840 --> 00:20:24,700
Hellre än att gå vidare och dra ut de binära träd som har 9 vid roten,

271
00:20:24,700 --> 00:20:27,220
vilket är det sista fallet att vi skulle ha,

272
00:20:27,220 --> 00:20:32,380
vi är i stället på denna punkt, kommer att tala lite om denna andra term

273
00:20:32,380 --> 00:20:36,150
att vi använder när vi talar om träd, som kallas höjden.

274
00:20:36,150 --> 00:20:45,460
>> Höjden av ett träd är avståndet från roten till den mest avlägsen nod,

275
00:20:45,460 --> 00:20:48,370
eller snarare antalet hopp som du skulle behöva göra för att

276
00:20:48,370 --> 00:20:53,750
börja från roten och sedan hamna på den mest avlägsna nod i trädet.

277
00:20:53,750 --> 00:20:57,330
Om vi ​​tittar på några av dessa träd som vi har ritat här,

278
00:20:57,330 --> 00:21:07,870
kan vi se att om vi tar detta träd i det övre vänstra hörnet och vi börjar vid 3,

279
00:21:07,870 --> 00:21:14,510
då måste vi göra en hop för att komma till 6, en andra hop för att komma till 7,

280
00:21:14,510 --> 00:21:20,560
och en tredje hopp för att komma till 9.

281
00:21:20,560 --> 00:21:26,120
Så, är höjden av detta träd 3.

282
00:21:26,120 --> 00:21:30,640
Vi kan göra samma övning för de andra träden som beskrivs i denna gröna,

283
00:21:30,640 --> 00:21:40,100
och vi ser att höjden av alla dessa träd är också verkligen 3.

284
00:21:40,100 --> 00:21:45,230
Det är en del av det som gör dem urarta -

285
00:21:45,230 --> 00:21:53,750
att deras höjd är bara en mindre än antalet noder i hela trädet.

286
00:21:53,750 --> 00:21:58,400
Om vi ​​tittar på det här andra träd som är inringad med rött, å andra sidan,

287
00:21:58,400 --> 00:22:03,920
ser vi att de mest avlägsna lövnoder är 6 och 9 -

288
00:22:03,920 --> 00:22:06,940
bladen är de noder som inte har några barn.

289
00:22:06,940 --> 00:22:11,760
Så, för att få från rotnoden till antingen 6 eller 9,

290
00:22:11,760 --> 00:22:17,840
Vi måste göra ett hopp för att komma till 7 och sedan en andra hop för att komma till 9,

291
00:22:17,840 --> 00:22:21,240
och likaså att endast en andra hopp från 7 komma till 6.

292
00:22:21,240 --> 00:22:29,080
Så, är höjden av detta träd hit bara 2.

293
00:22:29,080 --> 00:22:35,330
Du kan gå tillbaka och göra det för alla andra träd som vi tidigare diskuterade

294
00:22:35,330 --> 00:22:37,380
börjar med 7 och 6,

295
00:22:37,480 --> 00:22:42,500
och du kommer att finna att höjden av alla dessa träd är också 2.

296
00:22:42,500 --> 00:22:46,320
>> Anledningen till att vi har pratat om beställda binära träd

297
00:22:46,320 --> 00:22:50,250
och varför de är coolt är att du kan söka igenom dem i

298
00:22:50,250 --> 00:22:53,810
ett mycket liknande sätt att söka på en sorterad array.

299
00:22:53,810 --> 00:22:58,720
Det är där vi talar om att få den bättre lookup tid

300
00:22:58,720 --> 00:23:02,730
över det länkade enkel lista.

301
00:23:02,730 --> 00:23:05,010
Med en länkad lista - om du vill hitta ett visst element -

302
00:23:05,010 --> 00:23:07,470
du är i bästa kommer att göra någon form av linjär sökning

303
00:23:07,470 --> 00:23:10,920
där du börjar i början av en lista och hop en efter en -

304
00:23:10,920 --> 00:23:12,620
en nod efter en nod -

305
00:23:12,620 --> 00:23:16,060
genom hela listan tills du hittar vad du söker efter.

306
00:23:16,060 --> 00:23:19,440
För om du har ett binärt träd som lagras i denna trevliga format

307
00:23:19,440 --> 00:23:23,300
du kan faktiskt få mer av en binär sökning pågår

308
00:23:23,300 --> 00:23:25,160
där du söndra och härska

309
00:23:25,160 --> 00:23:29,490
och sök genom lämplig halv av trädet vid varje steg.

310
00:23:29,490 --> 00:23:32,840
Låt oss se hur det fungerar.

311
00:23:32,840 --> 00:23:38,850
>> Om vi ​​har - återigen gå tillbaka till vår ursprungliga Tree -

312
00:23:38,850 --> 00:23:46,710
Vi börjar på 7, vi har 3 till vänster, 9 till höger,

313
00:23:46,710 --> 00:23:51,740
och under 3 har vi 6.

314
00:23:51,740 --> 00:24:01,880
Om vi ​​vill söka efter numret 6 i detta träd, skulle vi börja vid roten.

315
00:24:01,880 --> 00:24:08,910
Vi skulle jämföra det värde som vi letar efter, säger 6,

316
00:24:08,910 --> 00:24:12,320
till det värde som lagras i noden som vi för närvarande tittar på, 7,

317
00:24:12,320 --> 00:24:21,200
tycker att 6 är verkligen mindre än 7, så vi skulle flytta till vänster.

318
00:24:21,200 --> 00:24:25,530
Om värdet på 6 hade varit större än 7, skulle vi ha istället flyttats till höger.

319
00:24:25,530 --> 00:24:29,770
Eftersom vi vet att - på grund av strukturen i vår beställda binärt träd -

320
00:24:29,770 --> 00:24:33,910
alla värden mindre än 7 kommer att lagras till vänster om 7,

321
00:24:33,910 --> 00:24:40,520
det finns ingen anledning att ens bry tittar genom den högra sidan av trädet.

322
00:24:40,520 --> 00:24:43,780
När vi flyttar till vänster och vi är nu på noden som innehåller 3,

323
00:24:43,780 --> 00:24:48,110
vi kan göra samma jämförelse igen där vi jämför 3 och 6.

324
00:24:48,110 --> 00:24:52,430
Och vi finner att medan 6 - värdet vi letar efter - är större än 3,

325
00:24:52,430 --> 00:24:58,580
Vi kan gå till den högra sidan av noden innehåller 3.

326
00:24:58,580 --> 00:25:02,670
Det finns ingen vänster sida här, så vi kunde ha ignorerat det.

327
00:25:02,670 --> 00:25:06,510
Men vi vet bara att eftersom vi tittar på trädet självt,

328
00:25:06,510 --> 00:25:08,660
och vi kan se att trädet inte har några barn.

329
00:25:08,660 --> 00:25:13,640
>> Det är också ganska lätt att slå upp 6 i detta träd om vi gör det själva som människor,

330
00:25:13,640 --> 00:25:16,890
men låt oss följa denna process mekaniskt som en dator skulle göra

331
00:25:16,890 --> 00:25:18,620
att verkligen förstå algoritmen.

332
00:25:18,620 --> 00:25:26,200
Vid denna punkt, vi letar nu vid en nod som innehåller 6,

333
00:25:26,200 --> 00:25:29,180
och vi letar efter värdet 6,

334
00:25:29,180 --> 00:25:31,740
så, ja, vi har hittat rätt nod.

335
00:25:31,740 --> 00:25:35,070
Vi hittade värdet 6 i vårt träd och vi kan stoppa vår sökning.

336
00:25:35,070 --> 00:25:37,330
Vid denna punkt, beroende på vad som händer,

337
00:25:37,330 --> 00:25:41,870
Vi kan säga, ja, har vi funnit värdet 6, den finns i vår träd.

338
00:25:41,870 --> 00:25:47,640
Eller, om vi planerar att sätta in en nod eller göra något, kan vi göra det på denna punkt.

339
00:25:47,640 --> 00:25:53,010
>> Låt oss göra ett par fler uppslag bara för att se hur det fungerar.

340
00:25:53,010 --> 00:25:59,390
Låt oss titta på vad som händer om vi skulle försöka leta upp värdet 10.

341
00:25:59,390 --> 00:26:02,970
Om vi ​​skulle slå upp värdet 10, skulle vi börja vid roten.

342
00:26:02,970 --> 00:26:07,070
Vi skulle se att 10 är större än 7, så vi skulle flytta till höger.

343
00:26:07,070 --> 00:26:13,640
Vi skulle komma till 9 och jämföra 9 till 10 och se att 9 verkligen är mindre än 10.

344
00:26:13,640 --> 00:26:16,210
Så återigen, skulle vi försöka att flytta till höger.

345
00:26:16,210 --> 00:26:20,350
Men på denna punkt, skulle vi märka att vi är på en noll nod.

346
00:26:20,350 --> 00:26:23,080
Det finns inget där. Det finns inget där 10 ska vara.

347
00:26:23,080 --> 00:26:29,360
Det är där vi kan rapportera misslyckande - att det verkligen inte 10 i trädet.

348
00:26:29,360 --> 00:26:35,420
Och slutligen, låt oss gå igenom de fall där vi försöker slå upp 1 i trädet.

349
00:26:35,420 --> 00:26:38,790
Detta liknar vad som händer om vi ser upp 10, utom i stället för att gå till höger,

350
00:26:38,790 --> 00:26:41,260
vi kommer att gå åt vänster.

351
00:26:41,260 --> 00:26:46,170
Vi börjar vid 7 och se att 1 är mindre än 7, så vi flytta till vänster.

352
00:26:46,170 --> 00:26:51,750
Vi kommer till 3 och se att 1 är mindre än 3, så igen vi försöka att flytta till vänster.

353
00:26:51,750 --> 00:26:59,080
På denna punkt har vi en noll nod, så vi återigen kan rapportera fel.

354
00:26:59,080 --> 00:27:10,260
>> Om du vill lära dig mer om binära träd,

355
00:27:10,260 --> 00:27:14,420
Det finns en hel massa roliga problem som du kan göra med dem.

356
00:27:14,420 --> 00:27:19,450
Jag föreslår att öva ritningen av dessa diagram ett i taget

357
00:27:19,450 --> 00:27:21,910
och efter igenom alla de olika stegen,

358
00:27:21,910 --> 00:27:25,060
eftersom detta kommer i super-händig

359
00:27:25,060 --> 00:27:27,480
inte bara när du gör Huffman inställda kodning problem

360
00:27:27,480 --> 00:27:29,390
men också i framtida kurser -

361
00:27:29,390 --> 00:27:32,220
bara att lära sig att dra ut dessa datastrukturer och tänka igenom de problem

362
00:27:32,220 --> 00:27:38,000
med papper och penna, eller i det här fallet, iPad och penna.

363
00:27:38,000 --> 00:27:41,000
>> Vid denna punkt dock, vi kommer att gå vidare för att göra vissa kodning praxis

364
00:27:41,000 --> 00:27:44,870
och faktiskt spela med dessa binära träd och se.

365
00:27:44,870 --> 00:27:52,150
Jag ska gå tillbaka till min dator.

366
00:27:52,150 --> 00:27:58,480
För denna del av sektionen, istället för att använda CS50 Kör eller CS50 utrymmen,

367
00:27:58,480 --> 00:28:01,500
Jag kommer att använda apparaten.

368
00:28:01,500 --> 00:28:04,950
>> Efter tillsammans med problemet Set specifikation,

369
00:28:04,950 --> 00:28:07,740
Jag ser att jag ska öppna upp apparaten,

370
00:28:07,740 --> 00:28:11,020
gå till min Dropbox mapp, skapa en mapp som heter 7 §,

371
00:28:11,020 --> 00:28:15,730
och sedan skapa en fil som heter binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Nu kör vi. Jag har apparaten redan öppen.

373
00:28:22,050 --> 00:28:25,910
Jag ska dra upp en terminal.

374
00:28:25,910 --> 00:28:38,250
Jag ska gå till Dropbox-mappen, gör en katalog som heter section7,

375
00:28:38,250 --> 00:28:42,230
och se att det är helt tomt.

376
00:28:42,230 --> 00:28:48,860
Nu ska jag öppna binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Okej. Here we go - tom fil.

378
00:28:51,750 --> 00:28:54,330
>> Låt oss gå tillbaka till specifikationen.

379
00:28:54,330 --> 00:28:59,850
Specifikationen ber att skapa en ny typ definition

380
00:28:59,850 --> 00:29:03,080
för ett binärt träd nod innehåller int värden -

381
00:29:03,080 --> 00:29:07,110
precis de värden som vi drog ut i vår diagram innan.

382
00:29:07,110 --> 00:29:11,740
Vi kommer att använda denna standardtext typedef att vi har gjort rätt här

383
00:29:11,740 --> 00:29:14,420
att du ska känna igen från problembild 5 -

384
00:29:14,420 --> 00:29:19,190
om du gjorde det hashtabellen sättet erövra stavningskontroll programmet.

385
00:29:19,190 --> 00:29:22,540
Du bör också känna igen den från förra veckans avsnitt

386
00:29:22,540 --> 00:29:23,890
där vi pratade om länkade listor.

387
00:29:23,890 --> 00:29:27,870
Vi har denna typedef en struct nod,

388
00:29:27,870 --> 00:29:34,430
och vi har gett denna struct nod detta namn på struct nod i förväg

389
00:29:34,430 --> 00:29:39,350
så att vi sedan kan hänvisa till det eftersom vi vill ha pekare struct nod

390
00:29:39,350 --> 00:29:45,740
som en del av vår struct, men vi har sedan inringad detta -

391
00:29:45,740 --> 00:29:47,700
eller snarare bifogas detta - i en typedef

392
00:29:47,700 --> 00:29:54,600
så att senare i koden, kan vi hänvisa till denna struct som bara en nod i stället för en struct nod.

393
00:29:54,600 --> 00:30:03,120
>> Detta kommer att bli mycket lik den enskilt-länkade lista definition som vi såg förra veckan.

394
00:30:03,120 --> 00:30:20,070
För att göra detta, låt oss bara börja med att skriva ut standardtext.

395
00:30:20,070 --> 00:30:23,840
Vi vet att vi måste ha ett heltal,

396
00:30:23,840 --> 00:30:32,170
så vi sätta i int-värde, och sedan istället för att bara ha en pekare till nästa element -

397
00:30:32,170 --> 00:30:33,970
som vi gjorde med enstaka-länkade listor -

398
00:30:33,970 --> 00:30:38,110
vi kommer att ha vänster och höger barn pekare.

399
00:30:38,110 --> 00:30:42,880
Det är ganska enkelt också - struct nod * vänster barn;

400
00:30:42,880 --> 00:30:51,190
och struct nod * rätt barn,. Cool.

401
00:30:51,190 --> 00:30:54,740
Det ser ut som en ganska bra start.

402
00:30:54,740 --> 00:30:58,530
Låt oss gå tillbaka till specifikationen.

403
00:30:58,530 --> 00:31:05,030
>> Nu måste vi förklara en global variabel nod * för roten av ett träd.

404
00:31:05,030 --> 00:31:10,590
Vi kommer att göra detta globala precis som vi gjorde första pekare i vår länkad lista också globalt.

405
00:31:10,590 --> 00:31:12,690
Det var så att i de funktioner som vi skriver

406
00:31:12,690 --> 00:31:16,180
Vi behöver inte hålla passerar runt denna rot -

407
00:31:16,180 --> 00:31:19,620
Men vi får se att om du vill skriva dessa funktioner rekursivt,

408
00:31:19,620 --> 00:31:22,830
kan det vara bättre att inte ens ge det runt som en global i första hand

409
00:31:22,830 --> 00:31:28,090
och istället initiera den lokalt i din huvudsakliga funktion.

410
00:31:28,090 --> 00:31:31,960
Men vi gör det globalt att starta.

411
00:31:31,960 --> 00:31:39,920
Återigen ger vi ett par platser, och jag ska förklara en nod * rot.

412
00:31:39,920 --> 00:31:46,770
Bara för att se till att jag inte lämnar det oinitierade, kommer jag att ställa in den lika med noll.

413
00:31:46,770 --> 00:31:52,210
Nu, i huvudfunktionen - som vi ska skriva riktigt snabbt här -

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

415
00:32:00,450 --> 00:32:10,640
och jag ska börja förklara min argv array som const bara så att jag vet

416
00:32:10,640 --> 00:32:14,550
att dessa argument är argument som jag förmodligen inte vill ändra.

417
00:32:14,550 --> 00:32:18,390
Om jag vill ändra dem jag borde nog att göra kopior av dem.

418
00:32:18,390 --> 00:32:21,740
Du ser detta mycket i kod.

419
00:32:21,740 --> 00:32:25,440
Det är bra åt båda hållen. Det är bra att lämna det som - utelämna const om du vill.

420
00:32:25,440 --> 00:32:28,630
Jag lägger oftast det bara så att jag påminna mig själv

421
00:32:28,630 --> 00:32:33,650
 att jag förmodligen inte vill ändra dessa argument.

422
00:32:33,650 --> 00:32:39,240
>> Som alltid, jag ska ta med denna retur 0 rad i slutet av Main.

423
00:32:39,240 --> 00:32:45,730
Här kommer jag initiera min rotnoden.

424
00:32:45,730 --> 00:32:48,900
Som det ser ut just nu, jag har en pekare som är inställd till noll,

425
00:32:48,900 --> 00:32:52,970
så det pekar på ingenting.

426
00:32:52,970 --> 00:32:57,480
För att faktiskt börja bygga noden,

427
00:32:57,480 --> 00:32:59,250
Jag måste först allokera minne för det.

428
00:32:59,250 --> 00:33:05,910
Jag ska göra det genom att minne på heap med malloc.

429
00:33:05,910 --> 00:33:10,660
Jag ska ställa rot lika med resultatet av malloc,

430
00:33:10,660 --> 00:33:19,550
och jag kommer att använda sizeof operatören för att beräkna storleken på en nod.

431
00:33:19,550 --> 00:33:24,990
Anledningen till att jag använder sizeof nod i motsats till, säg,

432
00:33:24,990 --> 00:33:37,020
göra något så här - malloc (4 + 4 4) eller malloc 12 -

433
00:33:37,020 --> 00:33:40,820
är för att jag vill att min kod för att vara så kompatibla som möjligt.

434
00:33:40,820 --> 00:33:44,540
Jag vill kunna ta det här. C. fil, kompilera den på apparaten,

435
00:33:44,540 --> 00:33:48,820
och sedan sammanställa det på min 64-bitars Mac -

436
00:33:48,820 --> 00:33:52,040
eller på en helt annan arkitektur -

437
00:33:52,040 --> 00:33:54,640
och jag vill allt detta ska fungera lika.

438
00:33:54,640 --> 00:33:59,510
>> Om jag gör antaganden om storleken på variabler -

439
00:33:59,510 --> 00:34:02,070
storleken på en int eller storleken av en pekare -

440
00:34:02,070 --> 00:34:06,070
då jag också göra antaganden om vilka typer av arkitekturer

441
00:34:06,070 --> 00:34:10,440
som min kod kan lyckas kompilera när den körs.

442
00:34:10,440 --> 00:34:15,030
Använd alltid sizeof i motsats till manuell summera struct fälten.

443
00:34:15,030 --> 00:34:20,500
Det andra skälet är att det också kan finnas stoppning att kompilatorn sätter in struct.

444
00:34:20,500 --> 00:34:26,570
Även bara summera de enskilda fält är inte något som du normalt vill göra,

445
00:34:26,570 --> 00:34:30,340
så ta bort den raden.

446
00:34:30,340 --> 00:34:33,090
Nu, för att verkligen initiera denna rotnod,

447
00:34:33,090 --> 00:34:36,489
Jag kommer att behöva koppla in värden för alla sina olika områden.

448
00:34:36,489 --> 00:34:41,400
Till exempel, för värde jag vet att jag vill initiera till 7,

449
00:34:41,400 --> 00:34:46,920
och nu ska jag ställa den vänstra barnet att vara noll

450
00:34:46,920 --> 00:34:55,820
och det högra underordnade också vara noll. Bra!

451
00:34:55,820 --> 00:35:02,670
Vi har gjort den delen av spec.

452
00:35:02,670 --> 00:35:07,390
>> Specifikationen ner längst ner på sidan 3 ber mig att skapa ytterligare tre noder -

453
00:35:07,390 --> 00:35:10,600
en innehållande 3, en innehållande 6, och en med 9 -

454
00:35:10,600 --> 00:35:14,210
och sedan koppla dem så att det ser ut precis som vår träddiagram

455
00:35:14,210 --> 00:35:17,120
att vi pratade om tidigare.

456
00:35:17,120 --> 00:35:20,450
Låt oss göra det ganska snabbt här.

457
00:35:20,450 --> 00:35:26,270
Du ser verkligen snabbt att jag ska börja skriva en massa dubbletter kod.

458
00:35:26,270 --> 00:35:32,100
Jag ska skapa en nod * och jag kommer att kalla det tre.

459
00:35:32,100 --> 00:35:36,000
Jag ska ställa in den lika med malloc (sizeof (nod)).

460
00:35:36,000 --> 00:35:41,070
Jag ska ställa tre-> värde = 3.

461
00:35:41,070 --> 00:35:54,780
Tre -> left_child = null; tre -> höger _child = null; också.

462
00:35:54,780 --> 00:36:01,150
Det ser ganska lik initiera roten, och det är precis vad

463
00:36:01,150 --> 00:36:05,760
Jag kommer att behöva göra om jag börjar initiera 6 och 9 samt.

464
00:36:05,760 --> 00:36:20,720
Jag ska göra det riktigt snabbt här - faktiskt, jag ska göra en liten kopiera och klistra in,

465
00:36:20,720 --> 00:36:46,140
och se till att jag - okej.

466
00:36:46,470 --> 00:37:09,900
 Nu har jag det kopierade och jag kan gå vidare och ställa in lika med 6.

467
00:37:09,900 --> 00:37:14,670
Du kan se att det tar ett tag och är inte super-effektiv.

468
00:37:14,670 --> 00:37:22,610
På bara lite, vi skriver en funktion som kommer att göra detta för oss.

469
00:37:22,610 --> 00:37:32,890
Jag vill ersätta detta med en 9, ersätta den med en 6.

470
00:37:32,890 --> 00:37:37,360
>> Nu har vi alla våra noder skapas och initieras.

471
00:37:37,360 --> 00:37:41,200
Vi har vår rot satts lika med 7 eller innehåller värdet 7,

472
00:37:41,200 --> 00:37:46,510
vår nod innehåller 3, vår nod innehåller 6, och vår nod innehåller 9.

473
00:37:46,510 --> 00:37:50,390
Vid denna punkt, är allt vi har att göra tråd allt.

474
00:37:50,390 --> 00:37:53,020
Anledningen till att jag initieras alla pekare till null är bara så att jag se till att

475
00:37:53,020 --> 00:37:56,260
Jag har inte några oinitierade pekare i det av misstag.

476
00:37:56,260 --> 00:38:02,290
Och även då, vid det här laget, jag har bara att faktiskt koppla noderna till varandra -

477
00:38:02,290 --> 00:38:04,750
till de som de faktiskt är ansluten till - Jag behöver inte gå igenom och göra

478
00:38:04,750 --> 00:38:08,240
Se till att alla nollor är där på rätt plats.

479
00:38:08,240 --> 00:38:15,630
>> Börjar på roten, vet jag att roten vänstra barn är 3.

480
00:38:15,630 --> 00:38:21,250
Jag vet att roten rätt barn är 9.

481
00:38:21,250 --> 00:38:24,880
Efter det, det enda andra barn som jag har kvar att oroa

482
00:38:24,880 --> 00:38:39,080
är 3 högra barn, som är 6.

483
00:38:39,080 --> 00:38:44,670
Vid denna punkt, det ser allt ganska bra.

484
00:38:44,670 --> 00:38:54,210
Vi kommer ta bort några av dessa linjer.

485
00:38:54,210 --> 00:38:59,540
Nu allt ser ganska bra ut.

486
00:38:59,540 --> 00:39:04,240
Låt oss gå tillbaka till vår specifikation och se vad vi har att göra härnäst.

487
00:39:04,240 --> 00:39:07,610
>> På denna punkt måste vi skriva en funktion som kallas "innehåller"

488
00:39:07,610 --> 00:39:14,150
med en prototyp av "bool Innehåller (int värde)".

489
00:39:14,150 --> 00:39:17,060
Och detta innehåller funktionen kommer att återvända sann

490
00:39:17,060 --> 00:39:21,200
 Om trädet utpekas av vår globala rot variabel

491
00:39:21,200 --> 00:39:26,950
 innehåller värdet passerat in i funktionen och i annat fall false.

492
00:39:26,950 --> 00:39:29,000
Låt oss gå vidare och göra det.

493
00:39:29,000 --> 00:39:35,380
Detta kommer att bli precis som lookup som vi gjorde för hand på iPad bara lite sen.

494
00:39:35,380 --> 00:39:40,130
Låt oss zooma tillbaka lite och bläddrar uppåt.

495
00:39:40,130 --> 00:39:43,130
Vi kommer att lägga denna funktion precis ovanför vår huvudsakliga funktion

496
00:39:43,130 --> 00:39:48,990
så att vi inte behöver göra någon form av prototyper.

497
00:39:48,990 --> 00:39:55,960
Så innehåller bool (int värde).

498
00:39:55,960 --> 00:40:00,330
Där kör vi. Det är vår standardtext deklaration.

499
00:40:00,330 --> 00:40:02,900
Bara för att vara säker på att detta kommer att sammanställa,

500
00:40:02,900 --> 00:40:06,820
Jag ska gå vidare och bara ställa in den lika med returnera false.

501
00:40:06,820 --> 00:40:09,980
Just nu denna funktion bara inte kommer att göra något och alltid rapportera att

502
00:40:09,980 --> 00:40:14,010
det värde som vi letar efter inte finns i trädet.

503
00:40:14,010 --> 00:40:16,280
>> Vid det här laget är det nog en bra idé -

504
00:40:16,280 --> 00:40:19,600
eftersom vi har skrivit en hel del kod och vi har inte ens försökt att testa det ännu -

505
00:40:19,600 --> 00:40:22,590
att se till att det hela sammanställer.

506
00:40:22,590 --> 00:40:27,460
Det finns ett par saker som vi måste göra för att se till att detta verkligen kommer att sammanställa.

507
00:40:27,460 --> 00:40:33,530
Först se om vi har använt alla funktioner i alla bibliotek som vi ännu inte har inkluderat.

508
00:40:33,530 --> 00:40:37,940
De funktioner vi har använt hittills är malloc,

509
00:40:37,940 --> 00:40:43,310
och då har vi också använt denna typ - detta icke-standard typ som kallas "bool' -

510
00:40:43,310 --> 00:40:45,750
som ingår i standard bool header-fil.

511
00:40:45,750 --> 00:40:53,250
Vi vill absolut inkludera standard bool.h för bool typ,

512
00:40:53,250 --> 00:40:59,230
och vi vill också # include standard lib.h för de vanliga biblioteken

513
00:40:59,230 --> 00:41:03,530
som inkluderar malloc och gratis, och allt detta.

514
00:41:03,530 --> 00:41:08,660
Så, zooma ut, vi kommer att sluta.

515
00:41:08,660 --> 00:41:14,190
Låt oss försöka se till att detta faktiskt gjorde kompilera.

516
00:41:14,190 --> 00:41:18,150
Vi ser att det gör, så vi är på rätt spår.

517
00:41:18,150 --> 00:41:22,990
>> Vi öppnar upp binary_tree.c igen.

518
00:41:22,990 --> 00:41:34,530
Det sammanställer. Låt oss gå ner och se till att vi sätter några samtal till vår Innehåller funktion -

519
00:41:34,530 --> 00:41:40,130
bara för att se till att det är allt gott och väl.

520
00:41:40,130 --> 00:41:43,170
Till exempel när vi gjorde några sökningar i vår träd tidigare,

521
00:41:43,170 --> 00:41:48,500
vi försökte slå upp värdena 6, 10 och 1, och vi visste att 6 var i trädet,

522
00:41:48,500 --> 00:41:52,220
10 var inte i trädet, och 1 var inte i trädet heller.

523
00:41:52,220 --> 00:41:57,230
Låt oss använda dessa prov samtal som ett sätt att ta reda på huruvida

524
00:41:57,230 --> 00:41:59,880
våra Innehåller funktionen fungerar.

525
00:41:59,880 --> 00:42:05,210
För att kunna göra det, jag kommer att använda printf funktionen

526
00:42:05,210 --> 00:42:10,280
och vi kommer att skriva ut resultatet av samtalet till innehåller.

527
00:42:10,280 --> 00:42:13,280
Jag ska sätta i en sträng "innehåller (% d) = eftersom

528
00:42:13,280 --> 00:42:20,470
 vi kommer att koppla in det värde som vi ska leta efter,

529
00:42:20,470 --> 00:42:27,130
och =% s \ n "och använda det som vår formatsträng.

530
00:42:27,130 --> 00:42:30,720
Vi ska bara se - bokstavligen skriva ut på skärmen -

531
00:42:30,720 --> 00:42:32,060
vad som ser ut som en funktion samtal.

532
00:42:32,060 --> 00:42:33,580
Detta är faktiskt inte funktionsanropet.

533
00:42:33,580 --> 00:42:36,760
 Detta är bara en sträng utformad för att se ut som ett funktionsanrop.

534
00:42:36,760 --> 00:42:41,140
>> Nu ska vi koppla in värdena.

535
00:42:41,140 --> 00:42:43,580
Vi kommer att försöka innehåller den 6,

536
00:42:43,580 --> 00:42:48,340
och sedan vad vi ska göra här är att använda den ternära operatör.

537
00:42:48,340 --> 00:42:56,340
Låt oss se - innehåller 6 - så, nu har jag innehöll 6 och om innehåller 6 är sant,

538
00:42:56,340 --> 00:43:01,850
den sträng som vi ska skicka till% s format karaktär

539
00:43:01,850 --> 00:43:04,850
kommer att vara strängen "sanna".

540
00:43:04,850 --> 00:43:07,690
Låt oss rulla över lite.

541
00:43:07,690 --> 00:43:16,210
Annars vill vi skicka strängen "false" om innehåller 6 returnerar false.

542
00:43:16,210 --> 00:43:19,730
Detta är en liten fånig ut, men jag räkna jag kan lika gärna illustrera

543
00:43:19,730 --> 00:43:23,780
vad ternära operatören ser ut eftersom vi inte har sett det på ett tag.

544
00:43:23,780 --> 00:43:27,670
Detta kommer att vara en trevlig, praktiskt sätt att ta reda på om våra Innehåller funktionen fungerar.

545
00:43:27,670 --> 00:43:30,040
Jag ska rulla tillbaka över till vänster,

546
00:43:30,040 --> 00:43:39,900
och jag ska kopiera och klistra in den här raden några gånger.

547
00:43:39,900 --> 00:43:44,910
Det ändrade några av dessa värden runt,

548
00:43:44,910 --> 00:43:59,380
så detta kommer att bli 1, och detta kommer att bli 10.

549
00:43:59,380 --> 00:44:02,480
>> På denna punkt har vi en fin Innehåller funktion.

550
00:44:02,480 --> 00:44:06,080
Vi har en del tester, och vi får se om det hela fungerar.

551
00:44:06,080 --> 00:44:08,120
På denna punkt har vi skrivit lite mer kod.

552
00:44:08,120 --> 00:44:13,160
Dags att sluta upp och se till att allt fortfarande sammanställer.

553
00:44:13,160 --> 00:44:20,360
Avsluta ut, och nu ska vi försöka göra binära trädet igen.

554
00:44:20,360 --> 00:44:22,260
Tja, det verkar som vi har ett fel,

555
00:44:22,260 --> 00:44:26,930
och vi har fått detta förklara tydligt biblioteket funktionen printf.

556
00:44:26,930 --> 00:44:39,350
Det ser ut som vi måste gå in och # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Och med det, ska allt sammanställa. Vi är alla bra.

558
00:44:45,350 --> 00:44:50,420
Nu ska vi försöka köra binära träd och se vad som händer.

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

560
00:44:53,520 --> 00:44:55,190
och vi ser att, som vi förväntade oss -

561
00:44:55,190 --> 00:44:56,910
eftersom vi inte har genomfört innehåller ännu,

562
00:44:56,910 --> 00:44:59,800
eller snarare, har vi satt bara i gengäld falsk -

563
00:44:59,800 --> 00:45:03,300
ser vi att det bara återvänder falsk för dem alla,

564
00:45:03,300 --> 00:45:06,180
så det är alla arbetar för det mesta ganska bra.

565
00:45:06,180 --> 00:45:11,860
>> Låt oss gå tillbaka och faktiskt genomföra innehåller på denna punkt.

566
00:45:11,860 --> 00:45:17,490
Jag ska rulla ner, zooma in och -

567
00:45:17,490 --> 00:45:22,330
kom ihåg var den algoritm som vi använde att vi började på rotnoden

568
00:45:22,330 --> 00:45:28,010
och därefter vid varje nod som vi möter, gör vi en jämförelse,

569
00:45:28,010 --> 00:45:32,380
och baserat på denna jämförelse vi flytta antingen till vänster barnet eller till höger barnet.

570
00:45:32,380 --> 00:45:39,670
Detta kommer att se mycket lik den binära sökkoden som vi skrev tidigare i tiden.

571
00:45:39,670 --> 00:45:47,810
När vi börjar, vet vi att vi vill hålla fast vid den aktuella noden

572
00:45:47,810 --> 00:45:54,050
att vi tittar på, och den aktuella noden kommer att initieras till rotnoden.

573
00:45:54,050 --> 00:45:56,260
Och nu ska vi hålla gå igenom trädet,

574
00:45:56,260 --> 00:45:58,140
och kom ihåg att vi stoppa skick -

575
00:45:58,140 --> 00:46:01,870
 när vi faktiskt arbetade genom exemplet hand -

576
00:46:01,870 --> 00:46:03,960
var när vi stött på ett noll nod,

577
00:46:03,960 --> 00:46:05,480
inte när vi tittade på en noll barn,

578
00:46:05,480 --> 00:46:09,620
utan snarare när vi flyttade faktiskt till en nod i trädet

579
00:46:09,620 --> 00:46:12,640
och fann att vi är på en noll nod.

580
00:46:12,640 --> 00:46:20,720
Vi kommer att iterera tills nuvarande är inte lika med noll.

581
00:46:20,720 --> 00:46:22,920
Och vad ska vi göra?

582
00:46:22,920 --> 00:46:31,610
Vi kommer att testa om (nuvarande -> värde == värde),

583
00:46:31,610 --> 00:46:35,160
då vet vi att vi faktiskt har hittat den nod som vi letar efter.

584
00:46:35,160 --> 00:46:40,450
Så här kan vi återvända sant.

585
00:46:40,450 --> 00:46:49,830
Annars, vill vi se huruvida värdet är mindre än värdet.

586
00:46:49,830 --> 00:46:53,850
Om det aktuella nodens värde är mindre än det värde vi letar efter,

587
00:46:53,850 --> 00:46:57,280
vi kommer att flytta till höger.

588
00:46:57,280 --> 00:47:10,600
Så nuvarande = nuvarande -> right_child, och annars kommer vi att flytta till vänster.

589
00:47:10,600 --> 00:47:17,480
nuvarande = nuvarande -> left_child,. Ganska enkel.

590
00:47:17,480 --> 00:47:22,830
>> Du känner igen förmodligen slinga som är mycket lik detta från

591
00:47:22,830 --> 00:47:27,580
binärsökning tidigare i sikt, förutom då vi hade att göra med låg, medel och hög.

592
00:47:27,580 --> 00:47:30,000
Här har vi bara titta på ett nuvärde,

593
00:47:30,000 --> 00:47:31,930
så det är trevligt och enkelt.

594
00:47:31,930 --> 00:47:34,960
Låt oss se till att denna kod fungerar.

595
00:47:34,960 --> 00:47:42,780
Kontrollera först att det sammanställer. Ser ut som det gör.

596
00:47:42,780 --> 00:47:47,920
Låt oss försöka köra det.

597
00:47:47,920 --> 00:47:50,160
Och mycket riktigt, skriver ut allt som vi förväntade oss.

598
00:47:50,160 --> 00:47:54,320
Den finner 6 i trädet, inte hittar 10 eftersom 10 inte är i trädet,

599
00:47:54,320 --> 00:47:57,740
och hittar inte 1 antingen på grund 1 är inte heller i trädet.

600
00:47:57,740 --> 00:48:01,420
Cool stuff.

601
00:48:01,420 --> 00:48:04,470
>> Okej. Låt oss gå tillbaka till vår specifikation och se vad som händer.

602
00:48:04,470 --> 00:48:07,990
Nu vill man lägga till några fler noder till vår träd.

603
00:48:07,990 --> 00:48:11,690
Det vill lägga 5, 2 och 8, och se till att vår innehåller kod

604
00:48:11,690 --> 00:48:13,570
fortfarande fungerar som förväntat.

605
00:48:13,570 --> 00:48:14,900
Låt oss gå göra det.

606
00:48:14,900 --> 00:48:19,430
Vid denna punkt, snarare än att göra det irriterande kopiera och klistra igen,

607
00:48:19,430 --> 00:48:23,770
Låt oss skriva en funktion för att faktiskt skapa en nod.

608
00:48:23,770 --> 00:48:27,740
Om vi ​​bläddra ner hela vägen till stora, ser vi att vi har gjort detta

609
00:48:27,740 --> 00:48:31,210
mycket liknande kod om och om igen varje gång som vi vill skapa en nod.

610
00:48:31,210 --> 00:48:39,540
>> Låt oss skriva en funktion som faktiskt kommer att bygga en nod för oss och returnera den.

611
00:48:39,540 --> 00:48:41,960
Jag ska kalla det build_node.

612
00:48:41,960 --> 00:48:45,130
Jag ska bygga en nod med ett visst värde.

613
00:48:45,130 --> 00:48:51,040
Zooma in här.

614
00:48:51,040 --> 00:48:56,600
Det första jag ska göra är att skapa faktiskt utrymme för nod i högen.

615
00:48:56,600 --> 00:49:05,400
Så nod * n = malloc (sizeof (nod)), n -> värde = värde;

616
00:49:05,400 --> 00:49:14,960
och sedan här, jag ska bara initiera alla fält är lämpliga värden.

617
00:49:14,960 --> 00:49:22,500
Och i slutet kommer vi tillbaka vår nod.

618
00:49:22,500 --> 00:49:28,690
Okej. En sak att notera är att denna funktion här

619
00:49:28,690 --> 00:49:34,320
kommer att returnera en pekare till minne som har hög-allokerad.

620
00:49:34,320 --> 00:49:38,880
Vad är trevligt om detta är att denna nod nu -

621
00:49:38,880 --> 00:49:42,420
Vi måste förklara det på högen för om vi förklarade det på stacken

622
00:49:42,420 --> 00:49:45,050
skulle vi inte kunna göra det i den här funktionen så här.

623
00:49:45,050 --> 00:49:47,690
Att minnet skulle gå ut ur räckvidd

624
00:49:47,690 --> 00:49:51,590
och skulle vara ogiltig om vi försökte att komma åt den senare.

625
00:49:51,590 --> 00:49:53,500
Eftersom vi förklara heap-allokerat minne,

626
00:49:53,500 --> 00:49:55,830
vi kommer att behöva ta hand om att befria det senare

627
00:49:55,830 --> 00:49:58,530
för vårt program för att inte läcka något minne.

628
00:49:58,530 --> 00:50:01,270
Vi har punting på att för allt annat i koden

629
00:50:01,270 --> 00:50:02,880
bara för enkelhets skull på tiden,

630
00:50:02,880 --> 00:50:05,610
men om du skriver någonsin en funktion som ser ut så här

631
00:50:05,610 --> 00:50:10,370
där du har - vissa kallar det en malloc eller realloc inuti -

632
00:50:10,370 --> 00:50:14,330
du vill vara säker på att du lägger någon sorts kommentar här uppe som säger,

633
00:50:14,330 --> 00:50:29,970
Vet du returnerar en hög-allokerad nod initieras med den skickade i värde.

634
00:50:29,970 --> 00:50:33,600
Och då du vill vara säker på att du sätter i någon form av anmärkning som säger

635
00:50:33,600 --> 00:50:41,720
uppringaren måste frigöra den returnerade minnet.

636
00:50:41,720 --> 00:50:45,450
Detta sätt, om någon någonsin går och använder den funktionen,

637
00:50:45,450 --> 00:50:48,150
de vet att vad de får tillbaka från den funktionen

638
00:50:48,150 --> 00:50:50,870
vid någon punkt måste frigöras.

639
00:50:50,870 --> 00:50:53,940
>> Förutsatt att allt är gott och väl här,

640
00:50:53,940 --> 00:51:02,300
vi kan gå ner i vår kod och ersätter alla dessa rader här

641
00:51:02,300 --> 00:51:05,410
med samtal till vår bygga nod-funktion.

642
00:51:05,410 --> 00:51:08,170
Låt oss göra det riktigt snabbt.

643
00:51:08,170 --> 00:51:15,840
Å ena sidan att vi inte kommer att ersätta denna del här nere

644
00:51:15,840 --> 00:51:18,520
vid botten där vi faktiskt koppla upp noderna peka på varandra,

645
00:51:18,520 --> 00:51:21,030
eftersom att vi inte kan göra i vår funktion.

646
00:51:21,030 --> 00:51:37,400
Men låt oss göra root = build_node (7), nod * tre = build_node (3);

647
00:51:37,400 --> 00:51:47,980
nod * sex = build_node (6), nod * nio = build_node (9),.

648
00:51:47,980 --> 00:51:52,590
Och nu ville vi också att lägga noder för -

649
00:51:52,590 --> 00:52:03,530
nod * fem = build_node (5), nod * åtta = build_node (8);

650
00:52:03,530 --> 00:52:09,760
och vad som var den andra noden? Låt oss se här. Vi ville också lägga till en 2 -

651
00:52:09,760 --> 00:52:20,280
nod * två = build_node (2),.

652
00:52:20,280 --> 00:52:26,850
Okej. Vid det här laget vet vi att vi har fått 7, 3 den, den 9 och 6

653
00:52:26,850 --> 00:52:30,320
alla trådbundna upp på lämpligt sätt, men hur är det 5, den 8 och 2?

654
00:52:30,320 --> 00:52:33,550
Att hålla allt i rätt ordning,

655
00:52:33,550 --> 00:52:39,230
Vi vet att tre rätt barn är 6.

656
00:52:39,230 --> 00:52:40,890
Så om vi ska lägga till 5,

657
00:52:40,890 --> 00:52:46,670
den 5 hör också i den högra sidan av trädet varav 3 är roten,

658
00:52:46,670 --> 00:52:50,440
så 5 hör som vänster barn 6.

659
00:52:50,440 --> 00:52:58,650
Vi kan göra detta genom att säga, sex -> left_child = fem;

660
00:52:58,650 --> 00:53:10,790
och sedan 8 hör som vänster barn 9, så nio -> left_child = åtta;

661
00:53:10,790 --> 00:53:22,190
och därefter 2 är den vänstra barn 3, så att vi kan göra det här uppe - dig -> left_child = två;.

662
00:53:22,190 --> 00:53:27,730
Om du inte riktigt följa med det, föreslår jag att du drar ut det själv.

663
00:53:27,730 --> 00:53:35,660
>> Okej. Låt oss spara den här. Låt oss gå ut och se till att det sammanställer,

664
00:53:35,660 --> 00:53:40,760
och då kan vi lägga till i våra Innehåller samtal.

665
00:53:40,760 --> 00:53:44,120
Ser ut som allt fortfarande sammanställer.

666
00:53:44,120 --> 00:53:51,790
Låt oss gå in och lägg i några innehåller samtal.

667
00:53:51,790 --> 00:53:59,640
Återigen, jag ska göra lite kopiera och klistra in.

668
00:53:59,640 --> 00:54:15,860
Nu ska vi leta efter 5, 8 och 2. Okej.

669
00:54:15,860 --> 00:54:28,330
Låt oss se till att allt detta ser bra ut ändå. Bra! Spara och avsluta.

670
00:54:28,330 --> 00:54:33,220
Nu ska vi göra, sammanställa, och nu ska vi köra.

671
00:54:33,220 --> 00:54:37,540
Av resultaten ser det ut som allt fungerar bara trevligt och bra.

672
00:54:37,540 --> 00:54:41,780
Bra! Så nu har vi fått våra CONTAINS, funktion skrivs.

673
00:54:41,780 --> 00:54:46,160
Låt oss gå vidare och börja arbeta på hur du sätter noder i trädet

674
00:54:46,160 --> 00:54:50,000
eftersom, som vi gör det just nu, det är inte mycket vackra.

675
00:54:50,000 --> 00:54:52,280
>> Om vi ​​går tillbaka till specifikationen,

676
00:54:52,280 --> 00:55:00,540
det ber oss att skriva en funktion som kallas in - igen, tillbaka en bool

677
00:55:00,540 --> 00:55:04,400
för om vi kunde faktiskt in nod i trädet -

678
00:55:04,400 --> 00:55:07,710
och sedan värdet att sätta in i trädet anges som

679
00:55:07,710 --> 00:55:11,060
det enda argumentet för vår Infoga funktion.

680
00:55:11,060 --> 00:55:18,180
Vi återkommer sant om vi kunde verkligen sätta noden innehåller värdet i trädet,

681
00:55:18,180 --> 00:55:20,930
vilket innebär att vi, ett, hade tillräckligt med minne,

682
00:55:20,930 --> 00:55:24,840
och sedan två, gick det nod inte redan finns i trädet sedan -

683
00:55:24,840 --> 00:55:32,170
Kom ihåg att vi inte kommer att ha dubbla värden i trädet, bara för att göra det enkelt.

684
00:55:32,170 --> 00:55:35,590
Okej. Tillbaka till koden.

685
00:55:35,590 --> 00:55:44,240
Öppna den. Zooma in lite, rulla ned.

686
00:55:44,240 --> 00:55:47,220
Låt oss sätta insatsen fungerar precis ovanför Innehåller.

687
00:55:47,220 --> 00:55:56,360
Återigen, det kommer att kallas bool insats (int värde).

688
00:55:56,360 --> 00:56:01,840
Ge det lite mer utrymme, och sedan, som standard,

689
00:56:01,840 --> 00:56:08,870
låt oss sätta i gengäld falskt i slutet.

690
00:56:08,870 --> 00:56:22,620
Nu nere på botten, låt oss gå vidare och i stället för att manuellt bygga noderna

691
00:56:22,620 --> 00:56:27,900
i främsta oss själva och kablar upp dem för att peka på varandra som vi gör,

692
00:56:27,900 --> 00:56:30,600
vi lita på våra Infoga funktion att göra det.

693
00:56:30,600 --> 00:56:35,510
Vi kommer inte att lita på vår insats funktion för att bygga hela trädet från början ännu,

694
00:56:35,510 --> 00:56:39,970
utan vi bli av med dessa rader - we'll kommentera ut dessa rader -

695
00:56:39,970 --> 00:56:43,430
som bygger noderna 5, 8, och 2.

696
00:56:43,430 --> 00:56:55,740
Och i stället kommer vi in ​​samtal till vår insats funktion

697
00:56:55,740 --> 00:57:01,280
att se till att det faktiskt fungerar.

698
00:57:01,280 --> 00:57:05,840
Nu kör vi.

699
00:57:05,840 --> 00:57:09,300
>> Nu har vi kommenterat ut dessa linjer.

700
00:57:09,300 --> 00:57:13,700
Vi har bara 7, 3, 9, och 6 i vårt träd vid denna punkt.

701
00:57:13,700 --> 00:57:18,870
För att säkerställa att detta är alla arbetar,

702
00:57:18,870 --> 00:57:25,050
Vi kan zooma ut, göra vår binära träd,

703
00:57:25,050 --> 00:57:30,750
kör det, och vi kan se som innehåller nu säger till oss att vi är helt rätt -

704
00:57:30,750 --> 00:57:33,110
5, 8, och 2 är inte längre i trädet.

705
00:57:33,110 --> 00:57:37,960
Gå tillbaka till koden,

706
00:57:37,960 --> 00:57:41,070
och hur ska vi sätta?

707
00:57:41,070 --> 00:57:46,290
Kom ihåg vad vi gjorde när vi var faktiskt sätta 5, 8 och 2 tidigare.

708
00:57:46,290 --> 00:57:50,100
Vi spelade som Plinko spel där vi började vid roten,

709
00:57:50,100 --> 00:57:52,780
gick ner trädet en efter en efter en

710
00:57:52,780 --> 00:57:54,980
tills vi hittat rätt lucka,

711
00:57:54,980 --> 00:57:57,570
och då vi fast i noden vid lämplig plats.

712
00:57:57,570 --> 00:57:59,480
Vi ska göra samma sak.

713
00:57:59,480 --> 00:58:04,070
Detta är i princip som att skriva kod som vi använt i innehåller funktionen

714
00:58:04,070 --> 00:58:05,910
att hitta platsen där noden bör,

715
00:58:05,910 --> 00:58:10,560
och då vi bara kommer att sätta noden där.

716
00:58:10,560 --> 00:58:17,000
Låt oss börja göra det.

717
00:58:17,000 --> 00:58:24,200
>> Så vi har en nod * nuvarande = rot, vi ska bara följa innehåller kod

718
00:58:24,200 --> 00:58:26,850
tills vi tycker att det inte riktigt fungerar för oss.

719
00:58:26,850 --> 00:58:32,390
Vi kommer att gå igenom trädet medan det aktuella elementet inte är null,

720
00:58:32,390 --> 00:58:45,280
och om vi finner att nuvarande värde är lika med det värde som vi försöker infoga -

721
00:58:45,280 --> 00:58:49,600
Nåväl, detta är ett av de fall där vi inte kunde faktiskt in noden

722
00:58:49,600 --> 00:58:52,730
in i trädet, eftersom detta innebär att vi har en dubblett värde.

723
00:58:52,730 --> 00:58:59,010
Här är vi faktiskt kommer att returnera false.

724
00:58:59,010 --> 00:59:08,440
Nu, annars om nuvarande värde är mindre än värdet,

725
00:59:08,440 --> 00:59:10,930
Nu vet vi att vi flyttar till höger

726
00:59:10,930 --> 00:59:17,190
 eftersom värdet hör hemma i den högra halvan av den aktuella trädet.

727
00:59:17,190 --> 00:59:30,110
Annars kommer vi att flytta till vänster.

728
00:59:30,110 --> 00:59:37,980
Det är i princip våra Innehåller fungerar där.

729
00:59:37,980 --> 00:59:41,820
>> Vid denna punkt, när vi har slutfört detta medan slinga,

730
00:59:41,820 --> 00:59:47,350
vår nuvarande pekare kommer att peka på null

731
00:59:47,350 --> 00:59:51,540
Om funktionen inte redan tillbaka.

732
00:59:51,540 --> 00:59:58,710
Vi därför har nuvarande på den plats där vi vill infoga den nya noden.

733
00:59:58,710 --> 01:00:05,210
Vad återstår att göra är att faktiskt bygga den nya noden,

734
01:00:05,210 --> 01:00:08,480
som vi kan göra ganska enkelt.

735
01:00:08,480 --> 01:00:14,930
Vi kan använda vår super-händig bygga nod funktion,

736
01:00:14,930 --> 01:00:17,210
och något som vi inte gjorde tidigare -

737
01:00:17,210 --> 01:00:21,400
Vi bara typ av tog för givet men nu ska vi göra bara för att se -

738
01:00:21,400 --> 01:00:27,130
vi testar att se till att värdet som returneras av ny nod var faktiskt

739
01:00:27,130 --> 01:00:33,410
inte är noll, eftersom vi inte vill börja komma att minnet om det är null.

740
01:00:33,410 --> 01:00:39,910
Vi kan testa för att se till att nya noden inte är lika med noll.

741
01:00:39,910 --> 01:00:42,910
Eller istället ser vi bara om det faktiskt är noll,

742
01:00:42,910 --> 01:00:52,120
och om det är noll, då kan vi bara returnera false tidigt.

743
01:00:52,120 --> 01:00:59,090
>> På denna punkt måste vi koppla nya noden i sin rätt plats i trädet.

744
01:00:59,090 --> 01:01:03,510
Om vi ​​ser tillbaka på huvud och där vi var faktiskt ledningar i värden före,

745
01:01:03,510 --> 01:01:08,470
ser vi att det sätt som vi gjorde det när vi ville sätta 3 i trädet

746
01:01:08,470 --> 01:01:11,750
var vi åt vänster barn rot.

747
01:01:11,750 --> 01:01:14,920
När vi satte 9 i trädet, hade vi tillgång till rätt barn roten.

748
01:01:14,920 --> 01:01:21,030
Vi var tvungna att ha en pekare till den förälder för att få ett nytt värde i trädet.

749
01:01:21,030 --> 01:01:24,430
Rulla tillbaka upp för att infoga, det är kommer inte att helt arbeta här

750
01:01:24,430 --> 01:01:27,550
eftersom vi inte har en förälder pekare.

751
01:01:27,550 --> 01:01:31,650
Vad vi vill kunna göra är att på denna punkt,

752
01:01:31,650 --> 01:01:37,080
kontrollera förälderns värde och se - ja, Jisses,

753
01:01:37,080 --> 01:01:41,990
om föräldern värde är mindre än det aktuella värdet,

754
01:01:41,990 --> 01:01:54,440
då förälderns rätt barn bör vara den nya noden;

755
01:01:54,440 --> 01:02:07,280
Annars bör föräldern vänstra barnet vara den nya noden.

756
01:02:07,280 --> 01:02:10,290
Men vi har inte denna förälder pekare riktigt än.

757
01:02:10,290 --> 01:02:15,010
>> För att få det, vi kommer faktiskt att behöva följa det som vi går igenom trädet

758
01:02:15,010 --> 01:02:18,440
och hitta rätt plats i vår slinga ovan.

759
01:02:18,440 --> 01:02:26,840
Vi kan göra det genom att rulla tillbaka upp till toppen av vår insats funktion

760
01:02:26,840 --> 01:02:32,350
och spåra en annan pekare variabel som kallas förälder.

761
01:02:32,350 --> 01:02:39,340
Vi kommer att ställa in den lika med noll från början,

762
01:02:39,340 --> 01:02:43,640
och sedan varje gång vi går igenom trädet,

763
01:02:43,640 --> 01:02:51,540
vi kommer att ställa den överordnade pekaren för att matcha den aktuella pekaren.

764
01:02:51,540 --> 01:02:59,140
Ställ förälder lika med nuvarande.

765
01:02:59,140 --> 01:03:02,260
På så sätt varje gång vi går igenom,

766
01:03:02,260 --> 01:03:05,550
vi kommer att se till att så markörens aktuella blir ökas

767
01:03:05,550 --> 01:03:12,640
föräldern pekaren följer det - bara en nivå högre än den nuvarande pekaren i trädet.

768
01:03:12,640 --> 01:03:17,370
Att alla ser ganska bra ut.

769
01:03:17,370 --> 01:03:22,380
>> Jag tror att en sak som vi vill ändra är att bygga nod återvänder null.

770
01:03:22,380 --> 01:03:25,380
För att få bygga nod till faktiskt framgångsrikt returnera null,

771
01:03:25,380 --> 01:03:31,060
vi får ändra denna kod,

772
01:03:31,060 --> 01:03:37,270
för här, testade vi aldrig att se till att malloc returnerade en giltig pekare.

773
01:03:37,270 --> 01:03:53,390
Så om (n = NULL!), Sedan -

774
01:03:53,390 --> 01:03:55,250
Om malloc returnerade en giltig pekare, så vi initiera den;

775
01:03:55,250 --> 01:04:02,540
annars kommer vi tillbaka bara och som kommer att sluta återvänder null för oss.

776
01:04:02,540 --> 01:04:13,050
Nu allt ser ganska bra ut. Låt oss se till att detta faktiskt sammanställer.

777
01:04:13,050 --> 01:04:22,240
Gör binärt träd, och åh, vi har lite grejer på gång här.

778
01:04:22,240 --> 01:04:29,230
>> Vi har en implicit deklaration av funktionen bygger nod.

779
01:04:29,230 --> 01:04:31,950
Återigen, dessa kompilatorer, vi kommer att börja i toppen.

780
01:04:31,950 --> 01:04:36,380
Vad det måste betyda att jag ringer bygga noden innan jag har faktiskt förklarat det.

781
01:04:36,380 --> 01:04:37,730
Låt oss gå tillbaka till koden verkligen snabbt.

782
01:04:37,730 --> 01:04:43,510
Bläddra nedåt och säker nog, min insats funktion deklareras

783
01:04:43,510 --> 01:04:47,400
ovanför bygga noden funktionen,

784
01:04:47,400 --> 01:04:50,070
men jag försöker använda bygga nod inuti insatsen.

785
01:04:50,070 --> 01:05:06,610
Jag ska gå in och kopiera - och sedan klistra bygga vägen nod-funktion här uppe i toppen.

786
01:05:06,610 --> 01:05:11,750
På så sätt förhoppningsvis kommer att fungera. Låt oss ge detta en annan gå.

787
01:05:11,750 --> 01:05:18,920
Nu sammanställer allt. Allt är bra.

788
01:05:18,920 --> 01:05:21,640
>> Men på denna punkt har vi faktiskt inte kallas våra Infoga funktion.

789
01:05:21,640 --> 01:05:26,510
Vi bara vet att det sammanställer, så låt oss gå in och sätta några samtal i.

790
01:05:26,510 --> 01:05:28,240
Låt oss göra det i vår huvudsakliga funktion.

791
01:05:28,240 --> 01:05:32,390
Här kommenterade vi ut 5, 8 och 2,

792
01:05:32,390 --> 01:05:36,680
och då vi inte koppla dem här nere.

793
01:05:36,680 --> 01:05:41,640
Låt oss göra några samtal för att infoga,

794
01:05:41,640 --> 01:05:46,440
och låt oss också använda samma typ av saker som vi använde

795
01:05:46,440 --> 01:05:52,810
När vi gjort dessa printf samtal för att kontrollera att allt var få ordentligt.

796
01:05:52,810 --> 01:06:00,550
Jag ska kopiera och klistra in,

797
01:06:00,550 --> 01:06:12,450
och i stället för innehåller vi ska inte in.

798
01:06:12,450 --> 01:06:30,140
Och istället för 6, 10 och 1, vi kommer att använda 5, 8 och 2.

799
01:06:30,140 --> 01:06:37,320
Detta bör förhoppningsvis in 5, 8, och 2 in i trädet.

800
01:06:37,320 --> 01:06:44,050
Kompilera. Allt är bra. Nu ska vi faktiskt kör vårt program.

801
01:06:44,050 --> 01:06:47,330
>> Allt återvände falskt.

802
01:06:47,330 --> 01:06:53,830
Så, 5, 8 och 2 går inte, och det ser ut som innehåller inte hittade dem heller.

803
01:06:53,830 --> 01:06:58,890
Vad händer? Låt oss zooma ut.

804
01:06:58,890 --> 01:07:02,160
Det första problemet var att insatsen verkade återvända falsk,

805
01:07:02,160 --> 01:07:08,750
och det ser ut som beror på att vi kvar i vår avkastning falsk samtal,

806
01:07:08,750 --> 01:07:14,590
och vi aldrig återvände sant.

807
01:07:14,590 --> 01:07:17,880
Vi kan ställa upp det.

808
01:07:17,880 --> 01:07:25,290
Det andra problemet är nu även om vi gör - spara avslutar detta,

809
01:07:25,290 --> 01:07:34,530
kör make igen, har kompilera den, kör den -

810
01:07:34,530 --> 01:07:37,670
ser vi att något annat hänt här.

811
01:07:37,670 --> 01:07:42,980
Den 5, 8 och 2 var fortfarande aldrig funnit i trädet.

812
01:07:42,980 --> 01:07:44,350
Så vad händer?

813
01:07:44,350 --> 01:07:45,700
>> Låt oss ta en titt på denna i koden.

814
01:07:45,700 --> 01:07:49,790
Låt oss se om vi kan lista ut.

815
01:07:49,790 --> 01:07:57,940
Vi börjar med den förälder som inte är null.

816
01:07:57,940 --> 01:07:59,510
Vi sätter markörens aktuella lika med roten pekaren

817
01:07:59,510 --> 01:08:04,280
och vi kommer att arbeta oss ner genom trädet.

818
01:08:04,280 --> 01:08:08,650
Om den aktuella noden inte är null, så vet vi att vi kan gå ner lite.

819
01:08:08,650 --> 01:08:12,330
Vi sätter vårt moderbolag pekare att vara lika med den aktuella pekaren,

820
01:08:12,330 --> 01:08:15,420
kontrollerat värde - om värdena är samma vi återvände falskt.

821
01:08:15,420 --> 01:08:17,540
Om värdena är mindre flyttade vi till höger;

822
01:08:17,540 --> 01:08:20,399
Annars flyttade vi till vänster.

823
01:08:20,399 --> 01:08:24,220
Då kan vi bygga en nod. Jag zooma in lite.

824
01:08:24,220 --> 01:08:31,410
Och här kommer vi att försöka att koppla upp värdena vara samma.

825
01:08:31,410 --> 01:08:37,250
Vad händer? Låt oss se om det möjligen Valgrind kan ge oss en ledtråd.

826
01:08:37,250 --> 01:08:43,910
>> Jag gillar att använda Valgrind bara för att Valgrind riktigt snabbt kör

827
01:08:43,910 --> 01:08:46,729
och berättar om det finns några minnesfel.

828
01:08:46,729 --> 01:08:48,300
När vi kör Valgrind på koden,

829
01:08:48,300 --> 01:08:55,859
som ni kan se rätt here--Valgrind./binary_tree--and tryck enter.

830
01:08:55,859 --> 01:09:03,640
Du ser att vi inte hade något minne fel, så det ser ut som om allt är okej så här långt.

831
01:09:03,640 --> 01:09:07,529
Vi har några minnesläckor, som vi vet, eftersom vi inte

832
01:09:07,529 --> 01:09:08,910
händer att befria någon av våra noder.

833
01:09:08,910 --> 01:09:13,050
Låt oss försöka köra GDB att se vad som verkligen händer.

834
01:09:13,050 --> 01:09:20,010
Vi gör gdb. / Binary_tree. Det startat upp bra.

835
01:09:20,010 --> 01:09:23,670
Låt oss sätta en brytpunkt på insatsen.

836
01:09:23,670 --> 01:09:28,600
Låt oss springa.

837
01:09:28,600 --> 01:09:31,200
Det ser ut som vi aldrig kallas insatsen.

838
01:09:31,200 --> 01:09:39,410
Det ser ut som att problemet var bara att när jag bytte här nere i huvud -

839
01:09:39,410 --> 01:09:44,279
alla dessa printf samtal från innehåller -

840
01:09:44,279 --> 01:09:56,430
Jag har aldrig egentligen ändrats dessa att ringa insats.

841
01:09:56,430 --> 01:10:01,660
Nu ska vi ge det ett försök. Låt oss sammanställa.

842
01:10:01,660 --> 01:10:09,130
Alla ser bra där. Nu ska vi försöka köra det, se vad som händer.

843
01:10:09,130 --> 01:10:13,320
Okej! Allt ser ganska bra där.

844
01:10:13,320 --> 01:10:18,130
>> Den sista sak att tänka på är, finns det någon kant fall till denna insats?

845
01:10:18,130 --> 01:10:23,170
Och det visar sig att, ja, det ena kanten så att är alltid intressant att tänka på

846
01:10:23,170 --> 01:10:26,250
är, vad händer om ditt träd är tom och du kallar denna insats funktion?

847
01:10:26,250 --> 01:10:30,330
Kommer det att fungera? Nåväl, låt oss ge det ett försök.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c.. -

849
01:10:32,110 --> 01:10:35,810
Det sätt vi ska testa detta, kommer vi att gå ner till vår huvuduppgift,

850
01:10:35,810 --> 01:10:41,690
och i stället ledningar dessa noder upp så här,

851
01:10:41,690 --> 01:10:56,730
Vi kommer bara att kommentera bort hela saken,

852
01:10:56,730 --> 01:11:02,620
och i stället för ledningar upp noderna själva,

853
01:11:02,620 --> 01:11:09,400
Vi kan faktiskt bara gå vidare och ta bort allt detta.

854
01:11:09,400 --> 01:11:17,560
Vi kommer att göra allt som en uppmaning att sätta in.

855
01:11:17,560 --> 01:11:49,020
Så, låt oss göra - istället för 5, 8 och 2, kommer vi att sätta in 7, 3 och 9.

856
01:11:49,020 --> 01:11:58,440
Och sedan ska vi också vill infoga 6 också.

857
01:11:58,440 --> 01:12:05,190
Spara. Avsluta. Gör binärt träd.

858
01:12:05,190 --> 01:12:08,540
Det sammanställer alla.

859
01:12:08,540 --> 01:12:10,320
Vi kan bara köra det som är och se vad som händer,

860
01:12:10,320 --> 01:12:12,770
men det är också kommer att bli mycket viktigt att se till att

861
01:12:12,770 --> 01:12:14,740
Vi har inte några minnesfel,

862
01:12:14,740 --> 01:12:16,840
eftersom detta är en av våra kant fall som vi känner till.

863
01:12:16,840 --> 01:12:20,150
>> Låt oss se till att det fungerar bra under Valgrind,

864
01:12:20,150 --> 01:12:28,310
vilket vi kommer att göra genom att bara köra Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Det ser ut som vi verkligen har en fel från en kontext -

866
01:12:31,110 --> 01:12:33,790
vi har denna segmenteringsfel.

867
01:12:33,790 --> 01:12:36,690
Vad hände?

868
01:12:36,690 --> 01:12:41,650
Valgrind berättar faktiskt oss var det är.

869
01:12:41,650 --> 01:12:43,050
Zooma ut lite.

870
01:12:43,050 --> 01:12:46,040
Det ser ut som det händer i vår insats funktion,

871
01:12:46,040 --> 01:12:53,420
där vi har en ogiltig läsning av storlek 4 på insats, linje 60.

872
01:12:53,420 --> 01:13:03,590
Låt oss gå tillbaka och se vad som händer här.

873
01:13:03,590 --> 01:13:05,350
Zooma ut riktigt snabbt.

874
01:13:05,350 --> 01:13:14,230
Jag vill se till att det inte går till kanten av skärmen så att vi kan se allt.

875
01:13:14,230 --> 01:13:18,760
Dra det i lite. Okej.

876
01:13:18,760 --> 01:13:35,030
Bläddra nedåt och problemet är här.

877
01:13:35,030 --> 01:13:40,120
Vad händer om vi får ner och vår nuvarande nod redan är noll,

878
01:13:40,120 --> 01:13:44,010
vår överordnade noden är null, så om vi ser upp på toppen, här -

879
01:13:44,010 --> 01:13:47,340
Om detta medan slinga aldrig utför

880
01:13:47,340 --> 01:13:52,330
eftersom vår nuvarande värdet är null - vår rot är null så nuvarande är null -

881
01:13:52,330 --> 01:13:57,810
då vårt moderbolag aldrig blir inställt på nuvarande eller till ett giltigt värde,

882
01:13:57,810 --> 01:14:00,580
så kommer föräldern också null.

883
01:14:00,580 --> 01:14:03,700
Vi måste komma ihåg att kontrollera att

884
01:14:03,700 --> 01:14:08,750
när vi kommer ner hit, och vi börjar komma förälderns värde.

885
01:14:08,750 --> 01:14:13,190
Så, vad händer? Tja, om föräldern är null -

886
01:14:13,190 --> 01:14:17,990
if (förälder == null) - då vet vi att

887
01:14:17,990 --> 01:14:19,530
det får inte finnas något i trädet.

888
01:14:19,530 --> 01:14:22,030
Vi måste försöka sätta in den vid roten.

889
01:14:22,030 --> 01:14:32,570
Vi kan göra det genom att bara sätta roten lika med den nya noden.

890
01:14:32,570 --> 01:14:40,010
Sedan vid denna tidpunkt, vi faktiskt inte vill gå igenom dessa andra saker.

891
01:14:40,010 --> 01:14:44,780
Istället, just här, kan vi göra antingen en annan-if-else,

892
01:14:44,780 --> 01:14:47,610
eller vi kunde kombinera allt här uppe i ett annat,

893
01:14:47,610 --> 01:14:56,300
men här ska vi bara använda annan och göra det på det sättet.

894
01:14:56,300 --> 01:14:59,030
Nu ska vi testa att se till att vårt moderbolag inte är null

895
01:14:59,030 --> 01:15:02,160
innan dess faktiskt försöker att komma åt dess fält.

896
01:15:02,160 --> 01:15:05,330
Detta kommer att hjälpa oss undvika segmenteringsfel.

897
01:15:05,330 --> 01:15:14,740
Så vi slutade, zooma ut, sammanställa, springa.

898
01:15:14,740 --> 01:15:18,130
>> Inga fel, men vi har fortfarande en massa minnesläckor

899
01:15:18,130 --> 01:15:20,650
eftersom vi inte befria någon av våra noder.

900
01:15:20,650 --> 01:15:24,350
Men om vi går upp här och vi ser på vår utskriften,

901
01:15:24,350 --> 01:15:30,880
ser vi att, ja, ser ut som alla våra insatser återvände sant, vilket är bra.

902
01:15:30,880 --> 01:15:33,050
Insatserna är alla sanna,

903
01:15:33,050 --> 01:15:36,670
och sedan lämpliga innehåller samtal är också sant.

904
01:15:36,670 --> 01:15:41,510
>> Bra jobbat! Det ser ut som att vi har lyckats skrivit inlägg.

905
01:15:41,510 --> 01:15:47,430
Det är allt vi har för denna veckas problembild Specifikation.

906
01:15:47,430 --> 01:15:51,720
En rolig utmaning att tänka på är hur du faktiskt skulle gå i

907
01:15:51,720 --> 01:15:55,340
och fri alla noderna i trädet.

908
01:15:55,340 --> 01:15:58,830
Vi kan göra det ett antal olika sätt,

909
01:15:58,830 --> 01:16:01,930
men jag lämnar det upp till dig att experimentera,

910
01:16:01,930 --> 01:16:06,080
och som en rolig utmaning, prova och se till att du kan se

911
01:16:06,080 --> 01:16:09,490
att detta Valgrind rapport tillbaka några fel och inga läckor.

912
01:16:09,490 --> 01:16:12,880
>> Lycka till på veckans Huffmankodning problembild,

913
01:16:12,880 --> 01:16:14,380
och vi ses nästa vecka!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]