1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [§ 7] [méně komfortní]

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

3
00:00:04,890 --> 00:00:07,000
[To je CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Vítejte v § 7.

5
00:00:09,080 --> 00:00:11,330
Díky hurikánu Sandy,

6
00:00:11,330 --> 00:00:13,440
místo toho, aby normální část tento týden,

7
00:00:13,440 --> 00:00:17,650
děláme to průchozí, prostřednictvím sekce otázek.

8
00:00:17,650 --> 00:00:22,830
Budu se po spolu s Problem Set 6 Specification,

9
00:00:22,830 --> 00:00:25,650
a procházejí všechny otázky v

10
00:00:25,650 --> 00:00:27,770
Sekce Dotazy sekce.

11
00:00:27,770 --> 00:00:30,940
Pokud máte nějaké dotazy,

12
00:00:30,940 --> 00:00:32,960
prosím poslat tyto na CS50 diskutovat.

13
00:00:32,960 --> 00:00:35,480
>> Dobře. Pojďme začít.

14
00:00:35,480 --> 00:00:40,780
Právě teď se dívám na straně 3 specifikace problému Set.

15
00:00:40,780 --> 00:00:44,110
Budeme nejprve začít mluvit o binárních stromech

16
00:00:44,110 --> 00:00:47,850
protože ty mají hodně důležité pro tento týden problému set -

17
00:00:47,850 --> 00:00:49,950
Strom Huffman kódování.

18
00:00:49,950 --> 00:00:55,000
Jedním z prvních datových struktur jsme o tom mluvili na CS50 bylo pole.

19
00:00:55,000 --> 00:01:00,170
Si uvědomit, že pole je posloupnost prvků -

20
00:01:00,170 --> 00:01:04,019
všechny stejného typu - uloženy přímo vedle sebe v paměti.

21
00:01:04,019 --> 00:01:14,420
Pokud mám celé číslo pole, které mohu čerpat pomocí tohoto boxy-čísla-celá čísla styl -

22
00:01:14,420 --> 00:01:20,290
Řekněme, že mám 5 v prvním poli, mám 7 ve druhém,

23
00:01:20,290 --> 00:01:27,760
pak jsem si 8, 10, a 20 v konečném poli.

24
00:01:27,760 --> 00:01:33,000
Pamatujte si, že opravdu dva dobré věci o tomto poli

25
00:01:33,000 --> 00:01:38,800
je, že máme tuto konstantu-time přístup k jakékoli konkrétní prvek

26
00:01:38,800 --> 00:01:40,500
 v poli, pokud známe jeho index.

27
00:01:40,500 --> 00:01:44,670
Například, pokud chci chytit třetí prvek v poli -

28
00:01:44,670 --> 00:01:47,870
na indexu 2 pomocí našeho nuly indexování systému -

29
00:01:47,870 --> 00:01:52,220
Doslova jsem prostě udělat jednoduchý matematický výpočet,

30
00:01:52,220 --> 00:01:56,170
hop do této polohy v poli,

31
00:01:56,170 --> 00:01:57,840
vytáhněte 8, který je uložen tam,

32
00:01:57,840 --> 00:01:59,260
a já jsem dobré jít.

33
00:01:59,260 --> 00:02:03,350
>> Jedním ze špatných věcí na tomto poli -, že jsme o tom mluvili

34
00:02:03,350 --> 00:02:05,010
když jsme hovořili o propojených seznamů -

35
00:02:05,010 --> 00:02:09,120
je, že když chci vložit prvek do tohoto pole,

36
00:02:09,120 --> 00:02:11,090
Budu muset udělat nějaké řazení okolí.

37
00:02:11,090 --> 00:02:12,940
Například, toto pole tady

38
00:02:12,940 --> 00:02:16,850
je v tříděném pořádku - ve vzestupném pořadí -

39
00:02:16,850 --> 00:02:19,440
5, pak 7, pak 8, pak 10, a pak se 20 -

40
00:02:19,440 --> 00:02:23,100
ale když chci vložit číslo 9 do tohoto pole,

41
00:02:23,100 --> 00:02:27,460
Budu muset posunout některé prvky, aby místo.

42
00:02:27,460 --> 00:02:30,440
Můžeme čerpat tuto tady.

43
00:02:30,440 --> 00:02:35,650
Budu muset přesunout 5, 7, a pak 8;

44
00:02:35,650 --> 00:02:38,720
vytvořit mezeru, kde jsem můžete dát 9,

45
00:02:38,720 --> 00:02:45,910
a pak se 10 a 20 může jít vpravo od 9.

46
00:02:45,910 --> 00:02:49,450
To je druh bolesti, protože v nejhorším případě -

47
00:02:49,450 --> 00:02:54,350
když jsme s vložit buď na začátku a na konci

48
00:02:54,350 --> 00:02:56,040
z pole, v závislosti na tom, jak jsme posouvání -

49
00:02:56,040 --> 00:02:58,850
můžeme skončit museli posunout všechny prvky

50
00:02:58,850 --> 00:03:00,750
že se to v současné době skladování v poli.

51
00:03:00,750 --> 00:03:03,810
>> Takže, co bylo jak vyřešit tento problém?

52
00:03:03,810 --> 00:03:09,260
Cesta kolem to bylo jít do našeho Linked-seznam metoda, kde -

53
00:03:09,260 --> 00:03:19,820
místo uložení prvků 5, 7, 8, 10, a 20 všechny vedle sebe v paměti -

54
00:03:19,820 --> 00:03:25,630
to, co jsme místo toho jsem byla ukládat jim druhu tam, kde jsme chtěli uložit

55
00:03:25,630 --> 00:03:32,470
v těchto linked-seznam uzlů, které jsem kreslení tady, druh ad hoc.

56
00:03:32,470 --> 00:03:42,060
A pak jsme spojili dohromady pomocí těchto dalších ukazatelů.

57
00:03:42,060 --> 00:03:44,370
Mohu mít ukazatel z 5 na 7,

58
00:03:44,370 --> 00:03:46,420
ukazatel z 7 na 8,

59
00:03:46,420 --> 00:03:47,770
ukazatel z 8 na 10,

60
00:03:47,770 --> 00:03:51,220
a konečně, ukazatel od 10 do 20,

61
00:03:51,220 --> 00:03:54,880
a pak nulový ukazatel na 20 naznačuje, že nic nezbylo.

62
00:03:54,880 --> 00:03:59,690
Trade-off, že tu máme

63
00:03:59,690 --> 00:04:05,360
je, že teď, když chceme vložit číslo 9 do našeho seznamu seřazeny,

64
00:04:05,360 --> 00:04:08,270
všechno, co musíme udělat, je vytvořit nový uzel s 9,

65
00:04:08,270 --> 00:04:12,290
byla připojena až k bodu na příslušné místo,

66
00:04:12,290 --> 00:04:20,630
a pak re-wire 8 bodu dolů na 9.

67
00:04:20,630 --> 00:04:25,660
To je docela jednoduché, za předpokladu, že přesně víme, kam chceme vložit 9.

68
00:04:25,660 --> 00:04:32,610
Ale trade-off výměnou za to, že jsme dnes ztratili konstantní časový přístup

69
00:04:32,610 --> 00:04:36,230
pro konkrétní prvek v naší datové struktury.

70
00:04:36,230 --> 00:04:40,950
Například, pokud chci najít čtvrtý prvek v tomto propojeném seznamu,

71
00:04:40,950 --> 00:04:43,510
Budu muset začít na začátku seznamu

72
00:04:43,510 --> 00:04:48,930
a pracovat svou cestu přes počítání uzlů s-node, až najdu čtvrtém.

73
00:04:48,930 --> 00:04:55,870
>> S cílem získat lepší přístup k výkonu než propojeného seznamu -

74
00:04:55,870 --> 00:04:59,360
ale také udržet některé z výhod, které jsme měli

75
00:04:59,360 --> 00:05:01,800
pokud jde o vložení čase z propojeného seznamu -

76
00:05:01,800 --> 00:05:05,750
binární strom bude potřebovat trochu více paměti.

77
00:05:05,750 --> 00:05:11,460
Zejména, místo toho, aby jen s jednou ukazatel v binárním stromu uzlu -

78
00:05:11,460 --> 00:05:13,350
jako linked-seznamu uzel dělá -

79
00:05:13,350 --> 00:05:16,950
budeme-li přidat druhý ukazatel do binárního stromu uzel.

80
00:05:16,950 --> 00:05:19,950
Spíše než jen s jednou ukazatel na další prvek,

81
00:05:19,950 --> 00:05:24,420
budeme mít ukazatel na levé dítě a pravé dítě.

82
00:05:24,420 --> 00:05:26,560
>> Pojďme nakreslit obrázek, co to vlastně vypadá.

83
00:05:26,560 --> 00:05:31,350
Opět, budu používat tyto krabice a šípy.

84
00:05:31,350 --> 00:05:37,150
Binární strom uzel bude začít s jednoduchým krabici.

85
00:05:37,150 --> 00:05:40,940
To bude mít prostor pro hodnotu,

86
00:05:40,940 --> 00:05:47,280
a pak je to také bude mít prostor pro levé dítě a pravé dítě.

87
00:05:47,280 --> 00:05:49,280
Chystám se popsat zde.

88
00:05:49,280 --> 00:05:57,560
Budeme mít levé dítě, a pak budeme mít ten správný dítě.

89
00:05:57,560 --> 00:05:59,920
Existuje mnoho různých způsobů, jak to udělat.

90
00:05:59,920 --> 00:06:02,050
Někdy na prostor a pohodlí,

91
00:06:02,050 --> 00:06:06,460
Budu vlastně kreslit jako já tady dělám na dně

92
00:06:06,460 --> 00:06:10,910
kde budu mít hodnotu na vrcholu,

93
00:06:10,910 --> 00:06:14,060
a pak na pravé dítě na pravé dolní,

94
00:06:14,060 --> 00:06:16,060
a levou dítě na dolní-levý.

95
00:06:16,060 --> 00:06:20,250
Vraťme se zpět k tomuto nahoru diagramu,

96
00:06:20,250 --> 00:06:22,560
máme hodnotu na samém vrcholu,

97
00:06:22,560 --> 00:06:25,560
pak máme levou dítě ukazatel, a pak máme právo-dítě ukazatel.

98
00:06:25,560 --> 00:06:30,110
>> V problému Nastavit specifikace,

99
00:06:30,110 --> 00:06:33,110
Hovoříme-li o kreslení uzel, který má hodnotu 7,

100
00:06:33,110 --> 00:06:39,750
a pak levé dítě ukazatel, který je nulový, a pravým dítě ukazatel, který je prázdný.

101
00:06:39,750 --> 00:06:46,040
Můžeme buď napsat kapitálové NULL v prostoru pro

102
00:06:46,040 --> 00:06:51,610
jak levé dítě a právo dítěte, nebo můžeme čerpat tento úhlopříčka lomítko

103
00:06:51,610 --> 00:06:53,750
každým z polí naznačují, že je to null.

104
00:06:53,750 --> 00:06:57,560
Já budu dělat, že právě proto, že je to jednodušší.

105
00:06:57,560 --> 00:07:03,700
To, co vidíte tady jsou dva způsoby, jak diagramů velmi jednoduchý binární strom uzel

106
00:07:03,700 --> 00:07:07,960
kde máme hodnotu 7 a nulové podřízené uvedeme.

107
00:07:07,960 --> 00:07:15,220
>> Druhá část našich specifikace hovoří o tom, jak s lineárními seznamy -

108
00:07:15,220 --> 00:07:18,270
pamatujte, jsme měli jen držet na úplně první prvek v seznamu

109
00:07:18,270 --> 00:07:20,270
pamatovat celý seznam -

110
00:07:20,270 --> 00:07:26,140
a podobně, s binárním stromem, stačí držet na jedné ukazatel na strom

111
00:07:26,140 --> 00:07:31,120
za účelem zachování kontroly nad celou datové struktury.

112
00:07:31,120 --> 00:07:36,150
Tato speciální prvek stromu se nazývá kořen stromu.

113
00:07:36,150 --> 00:07:43,360
Například, pokud se tento uzel - to uzel obsahující hodnotu 7

114
00:07:43,360 --> 00:07:45,500
s null levé a pravé dítě ukazatelů -

115
00:07:45,500 --> 00:07:47,360
byly pouze hodnota v našem stromu,

116
00:07:47,360 --> 00:07:50,390
pak by to být náš kořenový uzel.

117
00:07:50,390 --> 00:07:52,240
Je to úplně na začátku našeho stromu.

118
00:07:52,240 --> 00:07:58,530
Vidíme to trochu jasněji, jakmile začneme přidávat další uzly náš strom.

119
00:07:58,530 --> 00:08:01,510
Dovolte mi, abych vytáhnout novou stránku.

120
00:08:01,510 --> 00:08:05,000
>> Nyní budeme kreslit strom, který má 7 u kořene,

121
00:08:05,000 --> 00:08:10,920
a 3 uvnitř levého dítěte, a 9 vnitřek pravé dítě.

122
00:08:10,920 --> 00:08:13,500
Opět, to je docela jednoduchý.

123
00:08:13,500 --> 00:08:26,510
Máme 7, nakreslete uzel 3, uzel pro 9,

124
00:08:26,510 --> 00:08:32,150
a já jdu nastavit levou dítě ukazatel 7 ukazoval na uzel obsahující 3,

125
00:08:32,150 --> 00:08:37,850
a na pravé dítě ukazatel na uzel obsahující 7 k uzlu obsahující 9.

126
00:08:37,850 --> 00:08:42,419
Nyní, od 3 a 9 nemají žádné děti,

127
00:08:42,419 --> 00:08:48,500
budeme nastavit všechny jejich podřízené ukazatele budou mít hodnotu null.

128
00:08:48,500 --> 00:08:56,060
Zde kořen našeho stromu odpovídá uzlu obsahující číslo 7.

129
00:08:56,060 --> 00:09:02,440
Můžete vidět, že pokud vše, co máme, je ukazatel na tento kořenový uzel,

130
00:09:02,440 --> 00:09:07,330
pak můžeme projít náš strom a přístup k oběma podřízené uzly -

131
00:09:07,330 --> 00:09:10,630
oba 3 a 9.

132
00:09:10,630 --> 00:09:14,820
Není třeba zachovat odkazy na jednotlivý uzel na stromě.

133
00:09:14,820 --> 00:09:22,080
Dobře. Nyní budeme přidávat další uzel tohoto schématu.

134
00:09:22,080 --> 00:09:25,370
Budeme-li přidat uzel obsahující 6,

135
00:09:25,370 --> 00:09:34,140
a budeme přidávat to jako pravé dítě uzlu obsahujícího 3.

136
00:09:34,140 --> 00:09:41,850
Chcete-li se, že budu mazat, že nulový ukazatel v 3-uzel

137
00:09:41,850 --> 00:09:47,750
byla připojena až k bodu uzlu obsahující 6. Dobře.

138
00:09:47,750 --> 00:09:53,800
>> V tomto bodě, pojďme přes trochou terminologie.

139
00:09:53,800 --> 00:09:58,230
Chcete-li začít, důvod, že tento se nazývá binární strom, zejména

140
00:09:58,230 --> 00:10:00,460
je to, že má dva podřízené ukazatele.

141
00:10:00,460 --> 00:10:06,020
Existují i ​​jiné druhy stromů, které mají více dětí ukazatele.

142
00:10:06,020 --> 00:10:10,930
Zejména, jste "vyzkoušet" v problému Set 5.

143
00:10:10,930 --> 00:10:19,310
Určitě jste si všimli, že v tomto pokusu, jste měli 27 různých ukazatelů na různé děti -

144
00:10:19,310 --> 00:10:22,410
jeden pro každou z 26 písmen v anglické abecedě,

145
00:10:22,410 --> 00:10:25,410
a pak 27. pro apostrofem -

146
00:10:25,410 --> 00:10:28,900
tak, že je podobný typ stromu.

147
00:10:28,900 --> 00:10:34,070
Ale tady, protože je to binární, máme jen dvě podřízené ukazatele.

148
00:10:34,070 --> 00:10:37,880
>> Kromě tohoto kořenového uzlu, který jsme mluvili,

149
00:10:37,880 --> 00:10:41,470
jsme také hází kolem tohoto pojmu "dítě."

150
00:10:41,470 --> 00:10:44,470
Co to znamená pro jeden uzel být dítě jiného uzlu?

151
00:10:44,470 --> 00:10:54,060
To znamená, že se doslova podřízený uzel je dítě dalšího uzlu

152
00:10:54,060 --> 00:10:58,760
pokud je toto uzel má jeden z jeho podřízených ukazatelů stanovených upozornit na tento uzel.

153
00:10:58,760 --> 00:11:01,230
K tomu, aby to do více konkrétních podmínkách,

154
00:11:01,230 --> 00:11:11,170
pokud 3 je zaměřena na jeden z dětských ukazatelů z 7, pak 3 je dítě 7.

155
00:11:11,170 --> 00:11:14,510
Pokud bychom měli přijít na to, co děti 7 arů -

156
00:11:14,510 --> 00:11:18,510
dobře, vidíme, že 7 má ukazatel na 3 a ukazatel na 9,

157
00:11:18,510 --> 00:11:22,190
tak 9 a 3 jsou děti 7.

158
00:11:22,190 --> 00:11:26,650
Devět nemá žádné děti, protože jeho podřízené ukazatele jsou null,

159
00:11:26,650 --> 00:11:30,940
a 3 má pouze jedno dítě, 6.

160
00:11:30,940 --> 00:11:37,430
Šest také nemá žádné děti, protože oba jeho ukazatelů jsou null, které budeme čerpat hned.

161
00:11:37,430 --> 00:11:45,010
>> Kromě toho jsme také mluvit o rodičích určitého uzlu,

162
00:11:45,010 --> 00:11:51,100
a to je, jak byste očekávali, opak tohoto dítěte popisu.

163
00:11:51,100 --> 00:11:58,620
Každý uzel má jen jednoho rodiče - místo dvou jak se dalo očekávat s lidmi.

164
00:11:58,620 --> 00:12:03,390
Například, mateřská 3 je 7.

165
00:12:03,390 --> 00:12:10,800
Rodič 9 je také 7, a rodič 6 je 3. Nic moc na to.

166
00:12:10,800 --> 00:12:15,720
Máme také podmínky hovořit o prarodičů a vnoučat,

167
00:12:15,720 --> 00:12:18,210
a obecněji budeme mluvit o předcích

168
00:12:18,210 --> 00:12:20,960
a potomci v konkrétním uzlu.

169
00:12:20,960 --> 00:12:25,710
Předchůdce uzlu - nebo předci, spíše o uzlu -

170
00:12:25,710 --> 00:12:32,730
jsou všechny uzly, které leží na cestě z kořene do tohoto uzlu.

171
00:12:32,730 --> 00:12:36,640
Například, když jsem při pohledu na uzlu 6,

172
00:12:36,640 --> 00:12:46,430
pak předkové se bude i 3 a 7.

173
00:12:46,430 --> 00:12:55,310
Předkové 9, například, jsou - když jsem při pohledu na uzlu 9 -

174
00:12:55,310 --> 00:12:59,990
pak předek 9 je jen 7.

175
00:12:59,990 --> 00:13:01,940
A potomci jsou přesně naopak.

176
00:13:01,940 --> 00:13:05,430
Pokud se chci podívat na všechny potomky 7,

177
00:13:05,430 --> 00:13:11,020
pak jsem se podívat na všechny uzly pod ním.

178
00:13:11,020 --> 00:13:16,950
Takže, mám 3, 9, a 6 všechny jako potomků 7.

179
00:13:16,950 --> 00:13:24,170
>> Konečný termín, který budeme mluvit, je tento pojem je sourozenec.

180
00:13:24,170 --> 00:13:27,980
Sourozenci - druh po podél těchto rodinných podmínek -

181
00:13:27,980 --> 00:13:33,150
jsou uzly, které jsou na stejné úrovni ve stromu.

182
00:13:33,150 --> 00:13:42,230
Takže, 3 a 9 jsou sourozenci, protože jsou na stejné úrovni ve stromu.

183
00:13:42,230 --> 00:13:46,190
Oba mají stejné rodiče, 7.

184
00:13:46,190 --> 00:13:51,400
Na 6 nemá žádné sourozence, protože 9 nemá žádné děti.

185
00:13:51,400 --> 00:13:55,540
A 7 nemá žádné sourozence, protože je to kořen našeho stromu,

186
00:13:55,540 --> 00:13:59,010
a tam je vždy jen 1 root.

187
00:13:59,010 --> 00:14:02,260
Na 7 mají sourozenců by muselo být uzel nad 7.

188
00:14:02,260 --> 00:14:07,480
By muselo být rodič 7, v takovém případě 7 by již kořen stromu.

189
00:14:07,480 --> 00:14:10,480
Pak, že nová mateřská 7 by také měla mít dítě,

190
00:14:10,480 --> 00:14:16,480
a že dítě by pak být sourozenec 7.

191
00:14:16,480 --> 00:14:21,040
>> Dobře. Dál.

192
00:14:21,040 --> 00:14:24,930
Když jsme začali náš rozhovor binárních stromů,

193
00:14:24,930 --> 00:14:28,790
jsme si povídali o tom, jak jsme chtěli použít k

194
00:14:28,790 --> 00:14:32,800
získat výhodu nad obou polích a vzájemně provázaných seznamů.

195
00:14:32,800 --> 00:14:37,220
A způsob, jakým budeme dělat, že je s tímto uspořádání majetku.

196
00:14:37,220 --> 00:14:41,080
Můžeme říci, že binární strom je nařízeno, v souladu se specifikací,

197
00:14:41,080 --> 00:14:45,740
pokud pro každý uzel v našem stromu, všechny jeho potomky na levé -

198
00:14:45,740 --> 00:14:48,670
vlevo dítě a všechny levé dítě potomků -

199
00:14:48,670 --> 00:14:54,510
mají menší hodnoty, a všechny uzly na pravé straně -

200
00:14:54,510 --> 00:14:57,770
právo dítě a všechny pravé dítě potomků -

201
00:14:57,770 --> 00:15:02,800
mají uzly větší než hodnota aktuálního uzlu, který se právě díváte.

202
00:15:02,800 --> 00:15:07,850
Jen pro jednoduchost, budeme předpokládat, že zde nejsou žádné duplicitní uzly v našem stromu.

203
00:15:07,850 --> 00:15:11,180
Například, v této větvi nebudeme zabývat se případem

204
00:15:11,180 --> 00:15:13,680
kde mají hodnotu 7 u kořene

205
00:15:13,680 --> 00:15:16,720
 a pak také mají hodnotu 7 jinde ve stromu.

206
00:15:16,720 --> 00:15:24,390
V tomto případě, všimnete si, že tento strom je opravdu nařídil.

207
00:15:24,390 --> 00:15:26,510
Máme hodnotu 7 v kořenovém adresáři.

208
00:15:26,510 --> 00:15:29,720
Všechno na levé straně 7 -

209
00:15:29,720 --> 00:15:35,310
když jsem zpět všechny z těchto maličkých značek zde -

210
00:15:35,310 --> 00:15:40,450
všechno vlevo od 7 - za 3 a 6 -

211
00:15:40,450 --> 00:15:49,410
tyto hodnoty jsou oba méně než 7, a vše se vpravo - což je přesně to 9 -

212
00:15:49,410 --> 00:15:53,450
je větší než 7.

213
00:15:53,450 --> 00:15:58,650
>> To však není jediným objednat strom obsahující tyto hodnoty,

214
00:15:58,650 --> 00:16:03,120
ale pojďme tomu pár dalších z nich.

215
00:16:03,120 --> 00:16:05,030
Tam je skutečně celá parta způsobů, jak to můžeme udělat.

216
00:16:05,030 --> 00:16:09,380
Budu používat těsnopis jen aby to jednoduché, pokud -

217
00:16:09,380 --> 00:16:11,520
spíše než protahoval celé krabice-a šípy -

218
00:16:11,520 --> 00:16:14,220
Já jsem prostě jít kreslit čísla a přidejte šipky je spojují.

219
00:16:14,220 --> 00:16:22,920
Chcete-li začít, prostě budeme psát naše původní strom zase tam, kde jsme měli 7, a pak 3,

220
00:16:22,920 --> 00:16:25,590
a pak 3 ukazuje směrem vpravo na 6,

221
00:16:25,590 --> 00:16:30,890
a 7 měl pravý dítě, které bylo 9.

222
00:16:30,890 --> 00:16:33,860
Dobře. Co je další způsob, jak bychom mohli napsat tento strom?

223
00:16:33,860 --> 00:16:38,800
Místo toho, aby 3 je vlevo dítě 7,

224
00:16:38,800 --> 00:16:41,360
můžeme také 6 bude levá dítě 7,

225
00:16:41,360 --> 00:16:44,470
a pak 3 musí být na levé dítětem 6.

226
00:16:44,470 --> 00:16:48,520
To by vypadat jako na tomto stromu přímo tady, kde mám 7,

227
00:16:48,520 --> 00:16:57,860
pak 6, pak 3, a 9 na pravé straně.

228
00:16:57,860 --> 00:17:01,490
My také nemusí mít 7 jako naše kořenového uzlu.

229
00:17:01,490 --> 00:17:03,860
Mohli bychom také mít 6 jako náš kořenový uzel.

230
00:17:03,860 --> 00:17:06,470
Co by to vypadat?

231
00:17:06,470 --> 00:17:09,230
Pokud budeme udržovat tuto objednanou vlastnost,

232
00:17:09,230 --> 00:17:12,970
všechno vlevo od 6 musí být menší než to.

233
00:17:12,970 --> 00:17:16,540
Je tu jen jedna možnost, a to 3.

234
00:17:16,540 --> 00:17:19,869
Ale pak jako pravé dítě 6, máme dvě možnosti.

235
00:17:19,869 --> 00:17:25,380
Za prvé, mohli bychom mít 7 a pak 9,

236
00:17:25,380 --> 00:17:28,850
nebo můžeme kreslit - jako bych chtěl dělat tady -

237
00:17:28,850 --> 00:17:34,790
kde máme 9 jako pravé dítě v 6,

238
00:17:34,790 --> 00:17:39,050
a pak 7 jako levé podřízený 9.

239
00:17:39,050 --> 00:17:44,240
>> Nyní, 7 a 6 nejsou jediné možné hodnoty pro kořen.

240
00:17:44,240 --> 00:17:50,200
Mohli bychom také 3 musí být v kořenovém adresáři.

241
00:17:50,200 --> 00:17:52,240
Co se stane, když 3 je u kořene?

242
00:17:52,240 --> 00:17:54,390
Zde, věci se trochu zajímavé.

243
00:17:54,390 --> 00:17:58,440
Tři nemá žádné hodnoty, které jsou menší než to,

244
00:17:58,440 --> 00:18:02,070
tak, že celá levá strana stromu je jen tak, že je nulový.

245
00:18:02,070 --> 00:18:03,230
Je tu nebude nic tam.

246
00:18:03,230 --> 00:18:07,220
Na pravé straně, mohli bychom uvést věci ve vzestupném pořadí.

247
00:18:07,220 --> 00:18:15,530
Mohli bychom mít 3, pak 6, pak 7, pak 9.

248
00:18:15,530 --> 00:18:26,710
Nebo bychom to mohli udělat 3, pak 6, pak 9, pak 7.

249
00:18:26,710 --> 00:18:35,020
Nebo bychom to mohli udělat 3, pak 7, pak 6, pak 9.

250
00:18:35,020 --> 00:18:40,950
Nebo, 3, 7 - vlastně ne, nemůžeme udělat 7 už.

251
00:18:40,950 --> 00:18:43,330
To je naše jediná věc tam.

252
00:18:43,330 --> 00:18:54,710
Můžeme to udělat 9, a pak z 9 můžeme udělat 6 a pak 7.

253
00:18:54,710 --> 00:19:06,980
Nebo, můžeme 3, pak 9, potom 7, a pak 6.

254
00:19:06,980 --> 00:19:12,490
>> Jedna věc je upozornit na zde

255
00:19:12,490 --> 00:19:14,510
že tyto stromy jsou trochu divný-dívat.

256
00:19:14,510 --> 00:19:17,840
Zejména, pokud se podíváme na 4 stromy na pravé straně -

257
00:19:17,840 --> 00:19:20,930
Budu obíhat je, zde -

258
00:19:20,930 --> 00:19:28,410
Tyto stromy vypadají téměř stejně jako propojeného seznamu.

259
00:19:28,410 --> 00:19:32,670
Každý uzel má pouze jedno dítě,

260
00:19:32,670 --> 00:19:38,950
a tak není k dispozici žádný z tohoto stromové struktury, které vidíme, například,

261
00:19:38,950 --> 00:19:44,720
 v této jedné osamělý strom přes tady na levém dolním rohu.

262
00:19:44,720 --> 00:19:52,490
Tyto stromy jsou vlastně jen degenerují binární stromy,

263
00:19:52,490 --> 00:19:54,170
a budeme mluvit o nich více v budoucnosti -

264
00:19:54,170 --> 00:19:56,730
zvláště pokud jdete na přijmout další kurzy informatiky.

265
00:19:56,730 --> 00:19:59,670
Tyto stromy jsou degenerované.

266
00:19:59,670 --> 00:20:03,780
Jsou to velmi užitečné, protože skutečně, tato struktura propůjčuje

267
00:20:03,780 --> 00:20:08,060
 k vyhledávání časy podobné jako propojeného seznamu.

268
00:20:08,060 --> 00:20:13,050
Nechceme se využít extra paměti - tento dodatečný ukazatel -

269
00:20:13,050 --> 00:20:18,840
protože naší struktury je špatná tímto způsobem.

270
00:20:18,840 --> 00:20:24,700
Spíše než jít dál a upozornit na binární stromy, které mají 9 u kořene,

271
00:20:24,700 --> 00:20:27,220
která je konečným případ, že by mohl být

272
00:20:27,220 --> 00:20:32,380
jsme místo, v tomto bodě, bude mluvit trochu o tomto jiný termín

273
00:20:32,380 --> 00:20:36,150
že používáme, když mluvíme o stromech, které se nazývá výška.

274
00:20:36,150 --> 00:20:45,460
>> Výška stromu je vzdálenost od kořene k nejvíce vzdálené uzlu,

275
00:20:45,460 --> 00:20:48,370
nebo spíše počet chmele, které by se, aby se za účelem

276
00:20:48,370 --> 00:20:53,750
začít od kořene a pak skončí na nejvíce vzdálené uzlu ve stromu.

277
00:20:53,750 --> 00:20:57,330
Podíváme-li se na některé z těchto stromů, které jsme vypracovány tady,

278
00:20:57,330 --> 00:21:07,870
můžeme vidět, že pokud budeme mít tento strom v levém horním rohu a začneme na 3,

279
00:21:07,870 --> 00:21:14,510
pak musíme udělat 1 hop se dostat na 6, druhá hop se dostat do 7,

280
00:21:14,510 --> 00:21:20,560
a třetí hop se dostat do 9.

281
00:21:20,560 --> 00:21:26,120
Takže, výška tohoto stromu je 3.

282
00:21:26,120 --> 00:21:30,640
Můžeme to udělat stejný výkon pro ostatní stromy uvedených s tímto zeleným,

283
00:21:30,640 --> 00:21:40,100
a vidíme, že výška všech těchto stromů je také opravdu 3.

284
00:21:40,100 --> 00:21:45,230
To je součástí toho, co dělá je zvrhlík -

285
00:21:45,230 --> 00:21:53,750
, že jejich výška je jen jeden méně než je počet uzlů v celém stromu.

286
00:21:53,750 --> 00:21:58,400
Podíváme-li se na tento druhý strom, který je obklopen s červenou, na straně druhé,

287
00:21:58,400 --> 00:22:03,920
vidíme, že nejvíce vzdálené koncové uzly jsou 6 a 9 -

288
00:22:03,920 --> 00:22:06,940
listy, což jsou uzly, které nemají žádné děti.

289
00:22:06,940 --> 00:22:11,760
Takže, aby se dostal z kořenového uzlu buď 6 nebo 9,

290
00:22:11,760 --> 00:22:17,840
musíme udělat jednu hop se dostat do 7 a pak druhý hop se dostat do 9,

291
00:22:17,840 --> 00:22:21,240
a podobně, jen druhý hop z 7 se dostat k 6.

292
00:22:21,240 --> 00:22:29,080
Takže, výška tohoto stromu sem je pouze 2.

293
00:22:29,080 --> 00:22:35,330
Můžete se vrátit zpět, a to pro všechny ostatní stromy, které jsme dříve diskutovali

294
00:22:35,330 --> 00:22:37,380
počínaje 7 a 6,

295
00:22:37,480 --> 00:22:42,500
a zjistíte, že výška všech těchto stromů je také 2.

296
00:22:42,500 --> 00:22:46,320
>> Důvod, proč jsme mluvili o nařízeno binární stromy

297
00:22:46,320 --> 00:22:50,250
a proč jsou v pohodě, je proto, že se můžete probírat ně

298
00:22:50,250 --> 00:22:53,810
velmi podobný způsob vyhledávání přes tříděném poli.

299
00:22:53,810 --> 00:22:58,720
To je místo, kde budeme mluvit o získání že lepší vyhledávání čas

300
00:22:58,720 --> 00:23:02,730
přes jednoduché propojeného seznamu.

301
00:23:02,730 --> 00:23:05,010
S propojeného seznamu - pokud chcete najít konkrétní prvek -

302
00:23:05,010 --> 00:23:07,470
jste na nejlepší dělat nějaké lineární hledání

303
00:23:07,470 --> 00:23:10,920
kde začít na začátku seznamu a hop jeden po jednom -

304
00:23:10,920 --> 00:23:12,620
jeden uzel jedním uzlem -

305
00:23:12,620 --> 00:23:16,060
celý seznam, dokud nenajdete, co hledáte.

306
00:23:16,060 --> 00:23:19,440
Vzhledem k tomu, pokud máte binární strom, který je uložen v této pěkné formátu,

307
00:23:19,440 --> 00:23:23,300
můžete skutečně dostat více binárního vyhledávání děje

308
00:23:23,300 --> 00:23:25,160
kde si rozděl a panuj

309
00:23:25,160 --> 00:23:29,490
a hledání přes odpovídající polovině stromu na každém kroku.

310
00:23:29,490 --> 00:23:32,840
Pojďme se podívat, jak to funguje.

311
00:23:32,840 --> 00:23:38,850
>> Pokud máme - opět vrací do původního stromu -

312
00:23:38,850 --> 00:23:46,710
začneme v 7, my máme 3 vlevo, 9 na pravé straně,

313
00:23:46,710 --> 00:23:51,740
a pod 3 máme 6.

314
00:23:51,740 --> 00:24:01,880
Pokud chceme vyhledat číslo 6 v tomto stromu, měli bychom začít u kořene.

315
00:24:01,880 --> 00:24:08,910
Rádi bychom tyto hodnoty jsme hledali, řekněme 6,

316
00:24:08,910 --> 00:24:12,320
na hodnotu uloženou v uzlu, který jsme v současné době při pohledu na, 7,

317
00:24:12,320 --> 00:24:21,200
zjistí, že 6 je opravdu méně než 7, a tak jsme si přesunout doleva.

318
00:24:21,200 --> 00:24:25,530
Pokud je hodnota 6 byl vyšší než 7, bychom se místo toho se pohyboval napravo.

319
00:24:25,530 --> 00:24:29,770
Vzhledem k tomu, víme, že - vzhledem ke struktuře našeho objednaného binárního stromu -

320
00:24:29,770 --> 00:24:33,910
všechny hodnoty menší než 7 se bude uložen na levé straně 7,

321
00:24:33,910 --> 00:24:40,520
není třeba, aby neobtěžoval pohledu přes pravé straně stromu.

322
00:24:40,520 --> 00:24:43,780
Jakmile jsme se přesunout doleva a my jsme nyní v uzlu obsahující 3,

323
00:24:43,780 --> 00:24:48,110
můžeme udělat stejnou srovnání zase tam, kde jsme porovnat 3 a 6.

324
00:24:48,110 --> 00:24:52,430
A my zjistíme, že zatímco 6 - hodnota, kterou hledáte - je větší než 3,

325
00:24:52,430 --> 00:24:58,580
můžeme jít na pravé straně uzlu, která obsahuje 3.

326
00:24:58,580 --> 00:25:02,670
Není levá strana tady, takže jsme mohli ignorovat, že.

327
00:25:02,670 --> 00:25:06,510
Ale my jen víme, že proto, že se díváme na strom sám,

328
00:25:06,510 --> 00:25:08,660
a my můžeme vidět, že strom nemá žádné děti.

329
00:25:08,660 --> 00:25:13,640
>> Je také docela snadné se podívat do 6 v této větvi, pokud děláme to sami jako lidé,

330
00:25:13,640 --> 00:25:16,890
ale pojďme sledovat tento proces mechanicky jako počítač udělá

331
00:25:16,890 --> 00:25:18,620
opravdu pochopit algoritmus.

332
00:25:18,620 --> 00:25:26,200
V tomto bodě, jsme nyní podíváme na uzlu, který obsahuje 6,

333
00:25:26,200 --> 00:25:29,180
a hledáme pro hodnotu 6,

334
00:25:29,180 --> 00:25:31,740
tak, opravdu, jsme našli odpovídající uzel.

335
00:25:31,740 --> 00:25:35,070
Našli jsme hodnotu 6 v našem stromu, a můžeme zastavit naše vyhledávání.

336
00:25:35,070 --> 00:25:37,330
V tomto bodě, v závislosti na tom, co se děje,

337
00:25:37,330 --> 00:25:41,870
můžeme říci, že ano, jsme našli hodnotu 6, to je v naší stromu.

338
00:25:41,870 --> 00:25:47,640
Nebo, pokud plánujeme vložit uzel, nebo dělat něco, můžeme dělat, že v tomto bodě.

339
00:25:47,640 --> 00:25:53,010
>> Pojďme udělat pár dalších vyhledávání, jen aby viděl, jak to funguje.

340
00:25:53,010 --> 00:25:59,390
Pojďme se podívat na to, co se stane, když jsme byli vyzkoušet a podívat se na hodnotu 10.

341
00:25:59,390 --> 00:26:02,970
Pokud bychom se podívali do hodnoty 10, my bychom začali u kořene.

342
00:26:02,970 --> 00:26:07,070
Měli bychom vidět, že 10 je větší než 7, tak bychom přesune doprava.

343
00:26:07,070 --> 00:26:13,640
Měli bychom dostat na 9 a porovnejte 9 do 10 a uvidíte, že 9 je opravdu méně než 10.

344
00:26:13,640 --> 00:26:16,210
Takže znovu, tak se snažíme přesunout doprava.

345
00:26:16,210 --> 00:26:20,350
Ale v tomto bodě, měli bychom si všimnout, že jsme na null uzlu.

346
00:26:20,350 --> 00:26:23,080
Tam nic není. Není nic, kde by měla být 10.

347
00:26:23,080 --> 00:26:29,360
Toto je místo, kde se může hlásit selhání -, že skutečně č. 10 ve stromu.

348
00:26:29,360 --> 00:26:35,420
A konečně, pojďme projít případě se snažíme vyhledat 1 do stromu.

349
00:26:35,420 --> 00:26:38,790
To je podobné tomu, co se stane, když se podíváme do 10, s výjimkou místo toho, aby práva,

350
00:26:38,790 --> 00:26:41,260
jsme jít doleva.

351
00:26:41,260 --> 00:26:46,170
Začneme na 7 a uvidíte, že 1 je menší než 7, tak jsme se přesunout doleva.

352
00:26:46,170 --> 00:26:51,750
Dostáváme se na 3 a uvidíte, že 1 je menší než 3, takže opět se snažíme přesunout doleva.

353
00:26:51,750 --> 00:26:59,080
V tomto bodě máme null uzel, takže opět můžeme hlásit poruchu.

354
00:26:59,080 --> 00:27:10,260
>> Pokud se chcete dozvědět více o binárních stromech,

355
00:27:10,260 --> 00:27:14,420
existuje celá parta veselých malých problémů, které můžete dělat s nimi.

356
00:27:14,420 --> 00:27:19,450
Navrhuji cvičit kresbu z těchto diagramů jeden po druhém

357
00:27:19,450 --> 00:27:21,910
a po přes všechny jednotlivé kroky,

358
00:27:21,910 --> 00:27:25,060
protože to přijde super-praktický

359
00:27:25,060 --> 00:27:27,480
nejen, když děláte kódování Huffmanova problém sadu

360
00:27:27,480 --> 00:27:29,390
ale také v budoucích kurzů -

361
00:27:29,390 --> 00:27:32,220
jen naučit, jak čerpat z těchto datových struktur a myslím, že přes problémy

362
00:27:32,220 --> 00:27:38,000
s pero a papír nebo, v tomto případě, iPad a pero.

363
00:27:38,000 --> 00:27:41,000
>> V tomto bodě ačkoli, budeme se pohybovat na udělat nějaké kódování praxi

364
00:27:41,000 --> 00:27:44,870
a skutečně si hrát s těmito binárními stromy a vidět.

365
00:27:44,870 --> 00:27:52,150
Chystám se přejít zpátky na mém počítači.

366
00:27:52,150 --> 00:27:58,480
Pro tuto část sekce, namísto použití CS50 Spustit nebo CS50 prostory,

367
00:27:58,480 --> 00:28:01,500
Budu používat spotřebič.

368
00:28:01,500 --> 00:28:04,950
>> Po společně se specifikací problému Set,

369
00:28:04,950 --> 00:28:07,740
Vidím, že mám otevřít spotřebič,

370
00:28:07,740 --> 00:28:11,020
jít do mého složky Dropbox, vytvořte složku s názvem § 7,

371
00:28:11,020 --> 00:28:15,730
a pak vytvořit soubor s názvem binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Jdeme na to. Mám spotřebič již otevřen.

373
00:28:22,050 --> 00:28:25,910
Jdu vytáhnout terminál.

374
00:28:25,910 --> 00:28:38,250
Chystám se jít do složky Dropbox, aby se adresář s názvem section7,

375
00:28:38,250 --> 00:28:42,230
a vidět, že je to úplně prázdný.

376
00:28:42,230 --> 00:28:48,860
Teď jdu otevřít binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Dobře. Jdeme - prázdný soubor.

378
00:28:51,750 --> 00:28:54,330
>> Vraťme se specifikací.

379
00:28:54,330 --> 00:28:59,850
Specifikace žádá, aby vytvořit novou definici typu

380
00:28:59,850 --> 00:29:03,080
pro binární uzel stromu obsahuje int hodnoty -

381
00:29:03,080 --> 00:29:07,110
stejně jako hodnoty, které jsme vypracovali v naší diagramů před.

382
00:29:07,110 --> 00:29:11,740
Budeme používat tento standardní text typedef, že jsme udělali tady

383
00:29:11,740 --> 00:29:14,420
že byste měli poznat z problémových Set 5 -

384
00:29:14,420 --> 00:29:19,190
pokud jste hash tabulky způsob dobývání pravopisu programu.

385
00:29:19,190 --> 00:29:22,540
Měli byste také uznat z minulého týdne oddílu

386
00:29:22,540 --> 00:29:23,890
kde jsme o tom mluvili v souvislosti seznamech.

387
00:29:23,890 --> 00:29:27,870
Máme to typedef struct z uzlu,

388
00:29:27,870 --> 00:29:34,430
a my jsme stejně Tato struktura uzlu tento název struct uzel si předem

389
00:29:34,430 --> 00:29:39,350
takže pak můžeme odkazovat se na to, protože budeme chtít mít ukazatele struct uzel

390
00:29:39,350 --> 00:29:45,740
jako součást naší struct, ale my jsme pak obklíčen to -

391
00:29:45,740 --> 00:29:47,700
nebo spíše, uzavřený toto - v typedef

392
00:29:47,700 --> 00:29:54,600
tak, že později v kódu, lze odkázat na tento struct jen jako uzel namísto struct uzel.

393
00:29:54,600 --> 00:30:03,120
>> To bude velmi podobný singly propojené definice seznamu, které jsme viděli minulý týden.

394
00:30:03,120 --> 00:30:20,070
Chcete-li to provést, pojďme začít psát se na standardizovaný.

395
00:30:20,070 --> 00:30:23,840
Víme, že musíme mít celočíselnou hodnotu,

396
00:30:23,840 --> 00:30:32,170
tak dáme do int hodnoty, a pak místo toho, aby jen jeden ukazatel na další prvek -

397
00:30:32,170 --> 00:30:33,970
jako jsme to udělali s singly vázaných seznamů -

398
00:30:33,970 --> 00:30:38,110
budeme mít levé a pravé podřízené ukazatele.

399
00:30:38,110 --> 00:30:42,880
To je docela jednoduchá také - struct node * levá dítě;

400
00:30:42,880 --> 00:30:51,190
a struct uzel * P dítě;. Cool.

401
00:30:51,190 --> 00:30:54,740
To vypadá jako docela dobrý začátek.

402
00:30:54,740 --> 00:30:58,530
Vraťme se specifikací.

403
00:30:58,530 --> 00:31:05,030
>> Nyní musíme deklarovat globální proměnné uzlu * pro kořen stromu.

404
00:31:05,030 --> 00:31:10,590
Budeme dělat to globální, stejně jako jsme udělali první ukazatel v našem propojeném seznamu i globální.

405
00:31:10,590 --> 00:31:12,690
To bylo tak, že ve funkcích, které jsme napsat

406
00:31:12,690 --> 00:31:16,180
nemáme držet procházení kolem tohoto kořene -

407
00:31:16,180 --> 00:31:19,620
když budeme vidět, že pokud si chcete napsat tyto funkce rekurzivně,

408
00:31:19,620 --> 00:31:22,830
to by mohlo být lepší ani projít kolem jako globální na prvním místě

409
00:31:22,830 --> 00:31:28,090
a místo toho inicializovat ji lokálně ve vašem hlavním funkce.

410
00:31:28,090 --> 00:31:31,960
Ale uděláme to globálně začít.

411
00:31:31,960 --> 00:31:39,920
Opět, dáme pár míst, a budu deklarovat uzlu * kořen.

412
00:31:39,920 --> 00:31:46,770
Jen aby se ujistil, že nemám nechat tento inicializována, budu ji nastavit rovná null.

413
00:31:46,770 --> 00:31:52,210
Nyní, v hlavní funkci - což budeme psát opravdu rychle přímo zde -

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

415
00:32:00,450 --> 00:32:10,640
a já začnu prohlášením své argv pole jako const jen proto, že vím,

416
00:32:10,640 --> 00:32:14,550
že tyto argumenty jsou argumenty, které jsem asi nechtějí měnit.

417
00:32:14,550 --> 00:32:18,390
Pokud chci změnit jsem jim měla být pravděpodobně dělat jejich kopie.

418
00:32:18,390 --> 00:32:21,740
Uvidíte to hodně v kódu.

419
00:32:21,740 --> 00:32:25,440
To je v pořádku tak jako tak. Je to v pořádku nechat to jako - vynechat const, pokud chcete.

420
00:32:25,440 --> 00:32:28,630
I typicky dát do jen proto, že jsem si připomínám

421
00:32:28,630 --> 00:32:33,650
 že jsem asi nechci měnit tyto argumenty.

422
00:32:33,650 --> 00:32:39,240
>> Jako vždy, budu zahrnout tento návratový 0 řádek na konci hlavní.

423
00:32:39,240 --> 00:32:45,730
Zde budu inicializovat svůj kořenový uzel.

424
00:32:45,730 --> 00:32:48,900
Jak to stojí teď, mám ukazatel, který je nastaven na hodnotu null,

425
00:32:48,900 --> 00:32:52,970
tak to ukazuje na nic.

426
00:32:52,970 --> 00:32:57,480
Aby se skutečně začít stavět uzel,

427
00:32:57,480 --> 00:32:59,250
Poprvé jsem třeba alokovat paměť pro něj.

428
00:32:59,250 --> 00:33:05,910
Já budu dělat, že tím, že paměť na haldě pomocí malloc.

429
00:33:05,910 --> 00:33:10,660
Jdu nastavit kořen rovnající se výsledku malloc,

430
00:33:10,660 --> 00:33:19,550
a budu používat sizeof operátor vypočítat velikost uzlu.

431
00:33:19,550 --> 00:33:24,990
Důvod, proč jsem použít sizeof uzel na rozdíl od, řekněme,

432
00:33:24,990 --> 00:33:37,020
něco takového - malloc (4 + 4 +4) nebo malloc 12 -

433
00:33:37,020 --> 00:33:40,820
Je tomu tak proto chci, aby můj kód, aby bylo kompatibilní, jak je to možné.

434
00:33:40,820 --> 00:33:44,540
Chci být schopen učinit takové. C soubor, zkompilovat na zařízení,

435
00:33:44,540 --> 00:33:48,820
a pak zkompilovat na mém 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
nebo na zcela jinou architekturu -

437
00:33:52,040 --> 00:33:54,640
a chci to všechno fungovat stejně.

438
00:33:54,640 --> 00:33:59,510
>> Pokud dělám předpoklady o velikosti proměnných -

439
00:33:59,510 --> 00:34:02,070
velikost int nebo velikost ukazatel -

440
00:34:02,070 --> 00:34:06,070
pak jsem také dělat předpoklady o druhy architektur

441
00:34:06,070 --> 00:34:10,440
na které můj kód lze úspěšně zkompilovat při spuštění.

442
00:34:10,440 --> 00:34:15,030
Vždy používejte sizeof na rozdíl od ručně součet struct pole.

443
00:34:15,030 --> 00:34:20,500
Dalším důvodem je to, že může být také padding, že kompilátor dává do struct.

444
00:34:20,500 --> 00:34:26,570
I jen součet jednotlivých polí není něco, co obvykle chtějí udělat,

445
00:34:26,570 --> 00:34:30,340
tak, odstraňte tento řádek.

446
00:34:30,340 --> 00:34:33,090
Teď, opravdu inicializovat kořenový uzel,

447
00:34:33,090 --> 00:34:36,489
Budu muset připojit hodnot pro každou z jeho různých oborů.

448
00:34:36,489 --> 00:34:41,400
Například pro hodnotu vím chci inicializovat až 7,

449
00:34:41,400 --> 00:34:46,920
a teď jdu nastavit doleva dítě budou mít hodnotu null

450
00:34:46,920 --> 00:34:55,820
a právo dítě také být nula. Výborně!

451
00:34:55,820 --> 00:35:02,670
Udělali jsme, že část spec.

452
00:35:02,670 --> 00:35:07,390
>> Specifikace se v dolní části stránky 3 se mě ptá, chcete-li vytvořit další tři uzly -

453
00:35:07,390 --> 00:35:10,600
z nichž jedna obsahuje 3, jeden obsahující 6, a jeden s 9 -

454
00:35:10,600 --> 00:35:14,210
a pak propojte je tak, že vypadá přesně jako náš stromovém diagramu

455
00:35:14,210 --> 00:35:17,120
že jsme mluvili o minulosti.

456
00:35:17,120 --> 00:35:20,450
Udělejme to docela rychle sem.

457
00:35:20,450 --> 00:35:26,270
Uvidíte opravdu rychle, že jsem začnu psát spoustu duplicitních kódu.

458
00:35:26,270 --> 00:35:32,100
Jdu vytvořit uzlu * a budu to nazývat tři.

459
00:35:32,100 --> 00:35:36,000
Jdu nastavit to stejné malloc (sizeof (uzel)).

460
00:35:36,000 --> 00:35:41,070
Jdu nastavit tři-> hodnota = 3.

461
00:35:41,070 --> 00:35:54,780
Tři -> left_child = NULL; tři -> P _child = NULL; stejně.

462
00:35:54,780 --> 00:36:01,150
To vypadá dost podobně jako inicializaci kořen, a to je přesně to, co

463
00:36:01,150 --> 00:36:05,760
Budu muset dělat, když začnu inicializaci 6 a 9 stejně.

464
00:36:05,760 --> 00:36:20,720
Udělám to opravdu rychle sem - vlastně, já budu dělat trochu kopírovat a vložit,

465
00:36:20,720 --> 00:36:46,140
a ujistěte se, že jsem - v pořádku.

466
00:36:46,470 --> 00:37:09,900
 Teď jsem dostal to kopírovat a můžu jít dál a nastavit rovná 6.

467
00:37:09,900 --> 00:37:14,670
Můžete vidět, že to trvá chvíli a není super-efektivní.

468
00:37:14,670 --> 00:37:22,610
V jen trochu, budeme napsat funkci, která bude dělat to pro nás.

469
00:37:22,610 --> 00:37:32,890
Chci nahradit to s 9, nahradit to s 6.

470
00:37:32,890 --> 00:37:37,360
>> Nyní máme všechny naše uzlů vytvořena a inicializována.

471
00:37:37,360 --> 00:37:41,200
Máme naše kořen položí rovny 7, nebo obsahující hodnotu 7,

472
00:37:41,200 --> 00:37:46,510
náš uzel obsahující 3, naše uzel obsahující 6, a naše uzel obsahující 9.

473
00:37:46,510 --> 00:37:50,390
V tomto bodě, vše, co musíte udělat, je drát vše až.

474
00:37:50,390 --> 00:37:53,020
Důvod, proč jsem inicializaci všech ukazatelů na hodnotu null, je jen proto, že jsem se ujistěte, že

475
00:37:53,020 --> 00:37:56,260
Nemám žádné neinicializovaná ukazatele v tu náhodou.

476
00:37:56,260 --> 00:38:02,290
A také, protože v tomto bodě, jsem jen skutečně připojit uzly navzájem -

477
00:38:02,290 --> 00:38:04,750
těm, že oni jsou vlastně spojené s - nemám projít a udělat

478
00:38:04,750 --> 00:38:08,240
zda jsou všechny nuly jsou tam na příslušných místech.

479
00:38:08,240 --> 00:38:15,630
>> Od kořene, já vím, že kořen levá dítě 3.

480
00:38:15,630 --> 00:38:21,250
Já vím, že kořen právo dítě je 9.

481
00:38:21,250 --> 00:38:24,880
Poté, pouze jiné dítě, které jsem nechal na starosti

482
00:38:24,880 --> 00:38:39,080
je 3 právo dítě, které je 6.

483
00:38:39,080 --> 00:38:44,670
V tomto okamžiku, to vše vypadá docela dobře.

484
00:38:44,670 --> 00:38:54,210
Budeme odstranit některé z těchto linek.

485
00:38:54,210 --> 00:38:59,540
Nyní vše vypadá docela dobře.

486
00:38:59,540 --> 00:39:04,240
Vraťme se k našemu specifikace a vidět to, co máme dělat dál.

487
00:39:04,240 --> 00:39:07,610
>> V tomto bodě, musíme psát volaná funkce "obsahuje"

488
00:39:07,610 --> 00:39:14,150
s prototypem "bool obsahuje (int value)".

489
00:39:14,150 --> 00:39:17,060
A tato obsahuje funkce bude vracet hodnotu true

490
00:39:17,060 --> 00:39:21,200
 jestliže strom poukázal na naší celosvětové kořenové proměnné

491
00:39:21,200 --> 00:39:26,950
 obsahuje hodnotu předán do funkce a false jinak.

492
00:39:26,950 --> 00:39:29,000
Pojďme dál a dělat, že.

493
00:39:29,000 --> 00:39:35,380
To bude přesně jako při vyhledávání, že jsme se po ruce na iPad jen trochu před.

494
00:39:35,380 --> 00:39:40,130
Pojďme přibližování se trochu a stiskněte navigační tlačítko nahoru.

495
00:39:40,130 --> 00:39:43,130
Budeme dát tuto funkci přímo nad naší hlavní funkcí

496
00:39:43,130 --> 00:39:48,990
takže nemáme dělat nějaký druh prototypování.

497
00:39:48,990 --> 00:39:55,960
Takže, bool obsahuje (int value).

498
00:39:55,960 --> 00:40:00,330
Tam jdeme. Tady je náš standardní text prohlášení.

499
00:40:00,330 --> 00:40:02,900
Jen aby se ujistil, že to bude sestavovat,

500
00:40:02,900 --> 00:40:06,820
Chystám se jít dopředu a jen nastavit rovné vrátit false.

501
00:40:06,820 --> 00:40:09,980
Právě teď tato funkce prostě nebude dělat nic a vždy hlásí, že

502
00:40:09,980 --> 00:40:14,010
hodnota, která hledáme, není ve stromu.

503
00:40:14,010 --> 00:40:16,280
>> V tomto bodě, je to asi dobrý nápad -

504
00:40:16,280 --> 00:40:19,600
protože jsme napsali spoustu kódu a my jsme se ani nesnažili vyzkoušení - dosud

505
00:40:19,600 --> 00:40:22,590
aby se ujistil, že to všechno kompiluje.

506
00:40:22,590 --> 00:40:27,460
Existuje pár věcí, které musíme udělat, aby se ujistil, že to bude skutečně kompilovat.

507
00:40:27,460 --> 00:40:33,530
Za prvé, zda jsme byli s použitím jakýchkoli funkcí v žádné knihovny, které jsme doposud nebyly zahrnuty.

508
00:40:33,530 --> 00:40:37,940
Funkce, které jsme používali doposud, jsou malloc,

509
00:40:37,940 --> 00:40:43,310
a pak jsme také používali tento typ - tento nestandardní typ zvaný "bool' -

510
00:40:43,310 --> 00:40:45,750
který je součástí standardní bool záhlaví souboru.

511
00:40:45,750 --> 00:40:53,250
Určitě chceme, aby zahrnovala standardní bool.h pro typu bool,

512
00:40:53,250 --> 00:40:59,230
a také chceme # include standardní lib.h pro standardní knihovny

513
00:40:59,230 --> 00:41:03,530
které zahrnují malloc, a bezplatné, a všechny, které.

514
00:41:03,530 --> 00:41:08,660
Takže, oddálit, jedeme ukončit.

515
00:41:08,660 --> 00:41:14,190
Pojďme zkusit a ujistěte se, že to ve skutečnosti dělal kompilace.

516
00:41:14,190 --> 00:41:18,150
Vidíme, že to dělá, tak jsme na správné cestě.

517
00:41:18,150 --> 00:41:22,990
>> Pojďme otevřít binary_tree.c znovu.

518
00:41:22,990 --> 00:41:34,530
Shrnuje. Pojďme dolů a ujistěte se, že vložíme několik hovorů do našeho obsahuje funkce -

519
00:41:34,530 --> 00:41:40,130
jen aby se ujistil, že je všechno v pořádku.

520
00:41:40,130 --> 00:41:43,170
Například, když jsme dělali nějaké vyhledávání v našem stromu dříve,

521
00:41:43,170 --> 00:41:48,500
jsme se snažili podívat do hodnoty 6, 10, a 1, a věděli jsme, že 6 je na stromě,

522
00:41:48,500 --> 00:41:52,220
10 není ve stromu, a 1 nebyl ve stromu buď.

523
00:41:52,220 --> 00:41:57,230
Pojďme použít tyto ukázkové volání jako způsob, jak zjistit, zda nebo ne

524
00:41:57,230 --> 00:41:59,880
naše obsahuje funkce pracuje.

525
00:41:59,880 --> 00:42:05,210
Aby k tomu, že, budu používat printf funkce,

526
00:42:05,210 --> 00:42:10,280
a budeme vytisknout výsledek volání obsahuje.

527
00:42:10,280 --> 00:42:13,280
Jdu dát v řetězci "obsahuje (% d) = protože

528
00:42:13,280 --> 00:42:20,470
 budeme typem hodnoty, které budeme hledat,

529
00:42:20,470 --> 00:42:27,130
a =% s \ n ", a použít jej jako náš formátovacím řetězci.

530
00:42:27,130 --> 00:42:30,720
Jsme jen tak vidět - doslova vytisknout na obrazovce -

531
00:42:30,720 --> 00:42:32,060
co vypadá jako volání funkce.

532
00:42:32,060 --> 00:42:33,580
To není vlastně volání funkce.

533
00:42:33,580 --> 00:42:36,760
 To je jen řetězec navržen tak, aby vypadal jako volání funkce.

534
00:42:36,760 --> 00:42:41,140
>> Nyní, budeme připojit hodnot.

535
00:42:41,140 --> 00:42:43,580
Budeme se snažit obsahuje na 6,

536
00:42:43,580 --> 00:42:48,340
a pak to, co budeme dělat, je zde použít tento trojice operátor.

537
00:42:48,340 --> 00:42:56,340
Pojďme se podívat - obsahuje 6 - tak, teď jsem obsahoval 6, a pokud obsahuje 6 je pravda,

538
00:42:56,340 --> 00:43:01,850
řetězec, který budeme posílat na% s formátu charakteru

539
00:43:01,850 --> 00:43:04,850
bude řetězec "true".

540
00:43:04,850 --> 00:43:07,690
Pojďme projděte trochu.

541
00:43:07,690 --> 00:43:16,210
Jinak, chceme poslat řetězec "false", pokud obsahuje 6 vrátí False.

542
00:43:16,210 --> 00:43:19,730
To je malý praštěný vyhlížející, ale podle mě bych mohl také ilustrují

543
00:43:19,730 --> 00:43:23,780
co ternární operátor vypadá, protože jsme ho ještě neviděli na chvíli.

544
00:43:23,780 --> 00:43:27,670
To bude pěkný, šikovný způsob, jak zjistit, jestli naše obsahuje funkce pracuje.

545
00:43:27,670 --> 00:43:30,040
Jdu listovat nad vlevo,

546
00:43:30,040 --> 00:43:39,900
a budu kopírovat a vložit tento řádek několikrát.

547
00:43:39,900 --> 00:43:44,910
To změnilo některé z těchto hodnot kolem,

548
00:43:44,910 --> 00:43:59,380
takže to bude 1, a to bude 10.

549
00:43:59,380 --> 00:44:02,480
>> Na tomto místě jsme dostali pěknou obsahuje funkce.

550
00:44:02,480 --> 00:44:06,080
Máme nějaké testy, a uvidíme, jestli to všechno funguje.

551
00:44:06,080 --> 00:44:08,120
V tomto bodě jsme napsali některé další kód.

552
00:44:08,120 --> 00:44:13,160
Čas ukončení, a ujistěte se, že vše, co ještě kompiluje.

553
00:44:13,160 --> 00:44:20,360
Ukončete ven, a teď pojďme zkusit dělat binární strom znovu.

554
00:44:20,360 --> 00:44:22,260
No, vypadá to, že máme chybu,

555
00:44:22,260 --> 00:44:26,930
a my jsme dostali to výslovně prohlašuje knihovny funkci printf.

556
00:44:26,930 --> 00:44:39,350
Vypadá to, že musíme jít a # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
A s tím, vše by mělo sestavit. Jsme v pohodě.

558
00:44:45,350 --> 00:44:50,420
Nyní se pojďme zkusit spustit binární strom a uvidíme, co se stane.

559
00:44:50,420 --> 00:44:53,520
Zde jsme,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
a vidíme, že, jak jsme očekávali -

561
00:44:55,190 --> 00:44:56,910
protože jsme není implementována obsahuje ještě,

562
00:44:56,910 --> 00:44:59,800
nebo spíše, že jsme jen dát na oplátku falešné -

563
00:44:59,800 --> 00:45:03,300
vidíme, že je to jen vrací false pro všechny z nich,

564
00:45:03,300 --> 00:45:06,180
tak to je vše pracuje z větší části velmi dobře.

565
00:45:06,180 --> 00:45:11,860
>> Pojďme zpět a skutečně provádět obsahuje v tomto bodě.

566
00:45:11,860 --> 00:45:17,490
Chystám se posunout dolů, přibližovat, a -

567
00:45:17,490 --> 00:45:22,330
pamatujte, algoritmus, který jsme použili je, že jsme začali na kořenový uzel

568
00:45:22,330 --> 00:45:28,010
a pak v každém uzlu, který setkáváme, děláme srovnání,

569
00:45:28,010 --> 00:45:32,380
a na základě tohoto porovnání se buď přesunout na levou dítěte nebo pravé dítě.

570
00:45:32,380 --> 00:45:39,670
To bude vypadat velmi podobně jako kód binární vyhledávání, které jsme napsali dříve v termínu.

571
00:45:39,670 --> 00:45:47,810
Když začneme, víme, že chceme držet na aktuální uzel

572
00:45:47,810 --> 00:45:54,050
že se díváme na, a je aktuální uzel se bude inicializován na kořenový uzel.

573
00:45:54,050 --> 00:45:56,260
A teď, budeme pokračovat přes strom,

574
00:45:56,260 --> 00:45:58,140
a pamatujte, že naše zastavení podmínku -

575
00:45:58,140 --> 00:46:01,870
 když my vlastně pracovali na příkladu ručně -

576
00:46:01,870 --> 00:46:03,960
bylo, když jsme se setkali s null uzel,

577
00:46:03,960 --> 00:46:05,480
ne, když jsme se dívali na null dítě,

578
00:46:05,480 --> 00:46:09,620
ale když se ve skutečnosti přesunuty do uzlu ve stromu

579
00:46:09,620 --> 00:46:12,640
a zjistil, že jsme na null uzlu.

580
00:46:12,640 --> 00:46:20,720
Budeme opakovat, než teď není rovno null.

581
00:46:20,720 --> 00:46:22,920
A co budeme dělat?

582
00:46:22,920 --> 00:46:31,610
Budeme testovat, zda (teď -> hodnota == hodnota),

583
00:46:31,610 --> 00:46:35,160
pak víme, že jsme skutečně našli uzel, který jsme hledali.

584
00:46:35,160 --> 00:46:40,450
Tak tady se můžeme vrátit true.

585
00:46:40,450 --> 00:46:49,830
Jinak, my chceme vidět, zda je hodnota nižší než hodnota.

586
00:46:49,830 --> 00:46:53,850
Pokud je aktuální uzel je hodnota nižší než hodnota, kterou hledáme,

587
00:46:53,850 --> 00:46:57,280
budeme pohybovat doprava.

588
00:46:57,280 --> 00:47:10,600
Takže, teď = teď -> right_child, a jinak, budeme se pohybovat doleva.

589
00:47:10,600 --> 00:47:17,480
cur = cur -> left_child;. Docela jednoduché.

590
00:47:17,480 --> 00:47:22,830
>> Pravděpodobně jste rozpoznat smyčku, která vypadá velmi podobně, jako tato z

591
00:47:22,830 --> 00:47:27,580
binární vyhledávací dříve v termínu, s výjimkou pak jsme se zabývali s nízkou, střední a vysokou.

592
00:47:27,580 --> 00:47:30,000
Zde, právě jsme se podívat na současné hodnotě,

593
00:47:30,000 --> 00:47:31,930
tak je to pěkný a jednoduchý.

594
00:47:31,930 --> 00:47:34,960
Pojďme ujistěte se, že tento kód funguje.

595
00:47:34,960 --> 00:47:42,780
Nejprve se ujistěte, že sestavuje. Vypadá to, že to dělá.

596
00:47:42,780 --> 00:47:47,920
Pojďme zkuste ji spustit.

597
00:47:47,920 --> 00:47:50,160
A skutečně, že vypíše vše, co jsme očekávali.

598
00:47:50,160 --> 00:47:54,320
To najde 6 ve stromu, nenajde 10, protože 10 není ve stromu,

599
00:47:54,320 --> 00:47:57,740
a nenajde 1 buď proto, že 1 to také není ve stromu.

600
00:47:57,740 --> 00:48:01,420
Vychytávky ke stažení.

601
00:48:01,420 --> 00:48:04,470
>> Dobře. Vraťme se k našemu specifikace a uvidíme, co bude dál.

602
00:48:04,470 --> 00:48:07,990
Nyní se chce přidat některé další uzly do našeho stromu.

603
00:48:07,990 --> 00:48:11,690
To chce přidat 5, 2, a 8, a ujistěte se, že naše obsahuje kód

604
00:48:11,690 --> 00:48:13,570
stále funguje podle očekávání.

605
00:48:13,570 --> 00:48:14,900
Pojďme udělat.

606
00:48:14,900 --> 00:48:19,430
V tomto bodě, spíše než dělat, že nepříjemné kopírovat a vložit znovu,

607
00:48:19,430 --> 00:48:23,770
pojďme napsat funkci skutečně vytvořit uzel.

608
00:48:23,770 --> 00:48:27,740
Pokud bychom posunout dolů celou cestu k hlavnímu, vidíme, že jsme dělali to

609
00:48:27,740 --> 00:48:31,210
velmi podobný kód znovu a znovu pokaždé, když chceme vytvořit uzel.

610
00:48:31,210 --> 00:48:39,540
>> Pojďme napsat funkci, která bude skutečně stavět na uzel pro nás a vrátit jej.

611
00:48:39,540 --> 00:48:41,960
Jdu volat to build_node.

612
00:48:41,960 --> 00:48:45,130
Chystám se stavět uzel s konkrétní hodnotu.

613
00:48:45,130 --> 00:48:51,040
Přibližte zde.

614
00:48:51,040 --> 00:48:56,600
První věc, kterou budu dělat, je skutečně vytvořit prostor pro uzel na haldy.

615
00:48:56,600 --> 00:49:05,400
Takže, uzel * n = malloc (sizeof (node)), n -> hodnota = hodnota;

616
00:49:05,400 --> 00:49:14,960
a pak je tu, Já jsem prostě jít k inicializaci všech oblastech se příslušné hodnoty.

617
00:49:14,960 --> 00:49:22,500
A na samém konci, vrátíme naše uzel.

618
00:49:22,500 --> 00:49:28,690
Dobře. Jedna věc k poznámce je, že tuto funkci přímo zde

619
00:49:28,690 --> 00:49:34,320
bude vracet ukazatel do paměti, která byla haldy přidělená.

620
00:49:34,320 --> 00:49:38,880
Co je hezké na tom je, že tento uzel nyní -

621
00:49:38,880 --> 00:49:42,420
musíme prohlásit ho na hromadu, protože pokud jsme deklarovali ji na zásobník

622
00:49:42,420 --> 00:49:45,050
bychom nebyli schopni to udělat v této funkci, jako je tato.

623
00:49:45,050 --> 00:49:47,690
Že paměť by jít mimo rozsah

624
00:49:47,690 --> 00:49:51,590
a bylo by neplatné, pokud jsme se snažili přistupovat k ní později.

625
00:49:51,590 --> 00:49:53,500
Protože jsme se prohlašuje haldy přidělené paměti,

626
00:49:53,500 --> 00:49:55,830
budeme muset postarat o uvolnění později

627
00:49:55,830 --> 00:49:58,530
pro náš program není úniku nějakou vzpomínku.

628
00:49:58,530 --> 00:50:01,270
Byli jsme plavit se na to pro všechno ostatní v kódu

629
00:50:01,270 --> 00:50:02,880
Jen pro jednoduchost v té době,

630
00:50:02,880 --> 00:50:05,610
ale pokud jste někdy napsat funkci, která vypadá takto

631
00:50:05,610 --> 00:50:10,370
kde máš - někteří říkají, že malloc nebo realloc uvnitř -

632
00:50:10,370 --> 00:50:14,330
Chcete, aby se ujistil, že jste dal nějaký komentář sem, že říká,

633
00:50:14,330 --> 00:50:29,970
hej, víš, vrátí haldy přidělených uzel inicializován s předaný v hodnotě.

634
00:50:29,970 --> 00:50:33,600
A pak chcete, aby se ujistil, že jste vložili do nějaké poznámky, které říká, že

635
00:50:33,600 --> 00:50:41,720
volající musí uvolnit vrácené paměti.

636
00:50:41,720 --> 00:50:45,450
Tak, když se někdo někdy jde a používá tuto funkci,

637
00:50:45,450 --> 00:50:48,150
vědí, že všechno, co se vrátíme z této funkce

638
00:50:48,150 --> 00:50:50,870
v určitém okamžiku bude muset být propuštěn.

639
00:50:50,870 --> 00:50:53,940
>> Za předpokladu, že je vše v pořádku a tady dobře,

640
00:50:53,940 --> 00:51:02,300
můžeme jít dolů do našeho kódu a nahradit všechny tyto řádky tady

641
00:51:02,300 --> 00:51:05,410
s voláním naší funkce uzlu sestavení.

642
00:51:05,410 --> 00:51:08,170
Pojďme udělat opravdu rychle.

643
00:51:08,170 --> 00:51:15,840
Jedna část, která nebudeme nahradit je tato část dole

644
00:51:15,840 --> 00:51:18,520
na dně, kde se ve skutečnosti drát uzly poukázat na sebe,

645
00:51:18,520 --> 00:51:21,030
protože to nemůžeme udělat v naší funkci.

646
00:51:21,030 --> 00:51:37,400
Ale pojďme udělat root = build_node (7); uzel * tři = build_node (3);

647
00:51:37,400 --> 00:51:47,980
uzel * Šest = build_node (6); uzel * Devět = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
A teď, jsme také chtěli přidat uzly pro -

649
00:51:52,590 --> 00:52:03,530
Uzel * pět = build_node (5); uzel * osm = build_node (8);

650
00:52:03,530 --> 00:52:09,760
a co byla ta druhá uzel? Pojďme se podívat, zde. Chtěli jsme také přidat 2 -

651
00:52:09,760 --> 00:52:20,280
Uzel * dvě = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Dobře. V tomto bodě, víme, že jsme dostali 7, 3, 9, a 6

653
00:52:26,850 --> 00:52:30,320
všechny zapojen správně, ale co 5, 8, a 2?

654
00:52:30,320 --> 00:52:33,550
Aby bylo vše ve správném pořadí,

655
00:52:33,550 --> 00:52:39,230
víme, že tři právo dítě je 6.

656
00:52:39,230 --> 00:52:40,890
Takže, pokud budeme přidat 5,

657
00:52:40,890 --> 00:52:46,670
5 také patří do pravé straně stromu, z nichž tři jsou kořenová,

658
00:52:46,670 --> 00:52:50,440
tak 5 patří jako levé dítě 6.

659
00:52:50,440 --> 00:52:58,650
Můžeme to udělat tím, že říká, šest -> left_child = pět;

660
00:52:58,650 --> 00:53:10,790
a pak 8 patří jak levý dítě 9, tak devět -> left_child = osm;

661
00:53:10,790 --> 00:53:22,190
a pak 2 je levý dítě 3, takže můžeme udělat, že sem - tebe -> left_child = dva;.

662
00:53:22,190 --> 00:53:27,730
Pokud jste tak docela sledovat spolu s tím, navrhuji, abyste nakreslit to sami.

663
00:53:27,730 --> 00:53:35,660
>> Dobře. Pojďme zachránit to. Pojďme ven a ujistěte se, že sestavuje,

664
00:53:35,660 --> 00:53:40,760
a pak můžeme přidat v našem obsahuje volání.

665
00:53:40,760 --> 00:53:44,120
Vypadá to, že všechno, co ještě kompiluje.

666
00:53:44,120 --> 00:53:51,790
Pojďme a přidat v některých obsahuje volání.

667
00:53:51,790 --> 00:53:59,640
Opět, budu dělat trochu kopírování a vkládání.

668
00:53:59,640 --> 00:54:15,860
Nyní pojďme hledat 5, 8, a 2. Dobře.

669
00:54:15,860 --> 00:54:28,330
Pojďme se ujistěte, že to všechno vypadá dobře ještě. Výborně! Uložit a ukončete.

670
00:54:28,330 --> 00:54:33,220
Nyní pojďme udělat, kompilovat, a teď pojďme běžet.

671
00:54:33,220 --> 00:54:37,540
Z výsledků, vypadá to, že vše funguje jen hezké a dobře.

672
00:54:37,540 --> 00:54:41,780
Výborně! Takže teď máme naše obsahuje funkce psaný.

673
00:54:41,780 --> 00:54:46,160
Pojďme dál a začít pracovat na tom, jak vložit uzlů do stromu

674
00:54:46,160 --> 00:54:50,000
neboť, jak to děláme teď, věci nejsou moc hezká.

675
00:54:50,000 --> 00:54:52,280
>> Vrátíme-li se do specifikace,

676
00:54:52,280 --> 00:55:00,540
to nás žádá, abychom napsat funkci nazvanou vložení - opět vrací bool

677
00:55:00,540 --> 00:55:04,400
o otázku, zda nebo ne bychom mohli skutečně vložit uzel do stromu -

678
00:55:04,400 --> 00:55:07,710
a pak je hodnota vložit do stromu je specifikována jako

679
00:55:07,710 --> 00:55:11,060
jediným argumentem naší vlož funkci.

680
00:55:11,060 --> 00:55:18,180
Budeme vrátí true, pokud bychom mohli skutečně vložit uzlu obsahující hodnotu do stromu,

681
00:55:18,180 --> 00:55:20,930
, což znamená, že se jeden, měl dostatek paměti,

682
00:55:20,930 --> 00:55:24,840
a pak dva, že uzel nebyl již existují ve stromu od -

683
00:55:24,840 --> 00:55:32,170
Pamatujte si, že se nebudeme mít duplicitní hodnoty ve stromu, jen aby to jednoduché.

684
00:55:32,170 --> 00:55:35,590
Dobře. Zpět do kódu.

685
00:55:35,590 --> 00:55:44,240
Otevřete ji. Zvětšit trochu, posuňte zobrazení dolů.

686
00:55:44,240 --> 00:55:47,220
Pojďme dát vložte funkci přímo nad obsahuje.

687
00:55:47,220 --> 00:55:56,360
Opět, to bude nazýván bool vložka (int value).

688
00:55:56,360 --> 00:56:01,840
Dejte mu trochu více prostoru, a pak, jako výchozí,

689
00:56:01,840 --> 00:56:08,870
pojďme dát na oplátku falešné na samém konci.

690
00:56:08,870 --> 00:56:22,620
Nyní se na dně, pojďme do toho a namísto ručně budování uzly

691
00:56:22,620 --> 00:56:27,900
v hlavním sami a zapojení je až poukázat na sobě, jako to děláme,

692
00:56:27,900 --> 00:56:30,600
budeme spoléhat na naše vlož funkci k tomu, že.

693
00:56:30,600 --> 00:56:35,510
Nebudeme spoléhat na našem vlož funkci postavit celý strom od nuly ještě ne,

694
00:56:35,510 --> 00:56:39,970
ale budeme se zbavit těchto řádků - Dáme komentář, tyto řádky -

695
00:56:39,970 --> 00:56:43,430
které budou vycházet uzly 5, 8, a 2.

696
00:56:43,430 --> 00:56:55,740
A místo toho, budeme vložit volání do našeho vlož funkci

697
00:56:55,740 --> 00:57:01,280
aby se ujistil, že skutečně funguje.

698
00:57:01,280 --> 00:57:05,840
Jdeme na to.

699
00:57:05,840 --> 00:57:09,300
>> Nyní jsme komentáři těchto řádků.

700
00:57:09,300 --> 00:57:13,700
Máme jen 7, 3, 9, a 6 v našem stromu v tomto bodě.

701
00:57:13,700 --> 00:57:18,870
Ujistěte se, že je to všechno funguje,

702
00:57:18,870 --> 00:57:25,050
můžeme oddálit, aby naše binární strom,

703
00:57:25,050 --> 00:57:30,750
spusťte jej, a my můžeme vidět, že obsahuje je nyní nám říká, že jsme úplně pravdu -

704
00:57:30,750 --> 00:57:33,110
5, 8, a 2 jsou již ve stromu.

705
00:57:33,110 --> 00:57:37,960
Jděte zpět do kódu,

706
00:57:37,960 --> 00:57:41,070
a jak se budeme vložit?

707
00:57:41,070 --> 00:57:46,290
Vzpomeňte si, co jsme dělali, když jsme byli vlastně vložení 5, 8, a 2 dříve.

708
00:57:46,290 --> 00:57:50,100
Hráli jsme tuto hru Plinko, kde jsme začali u kořene,

709
00:57:50,100 --> 00:57:52,780
šel stromu jeden po jeden po druhém

710
00:57:52,780 --> 00:57:54,980
dokud jsme nenašli odpovídající mezeru,

711
00:57:54,980 --> 00:57:57,570
a pak se zapojený v uzlu na příslušné místo.

712
00:57:57,570 --> 00:57:59,480
Chystáme se udělat to samé.

713
00:57:59,480 --> 00:58:04,070
To je v podstatě jako psaní kódu, který jsme použili v obsahuje funkce

714
00:58:04,070 --> 00:58:05,910
najít místo, kde se uzel by měl být,

715
00:58:05,910 --> 00:58:10,560
a pak jsme jen tak vložit uzel tady.

716
00:58:10,560 --> 00:58:17,000
Pojďme začít dělat, že.

717
00:58:17,000 --> 00:58:24,200
>> Takže máme uzel * teď = root, budeme jen tak sledovat obsahuje kód

718
00:58:24,200 --> 00:58:26,850
dokud nezjistíme, že to není úplně pracovat pro nás.

719
00:58:26,850 --> 00:58:32,390
Budeme procházet stromu, zatímco aktuální prvek není null,

720
00:58:32,390 --> 00:58:45,280
a pokud zjistíme, že teď je hodnota rovna hodnotě, že se snažíme vložit -

721
00:58:45,280 --> 00:58:49,600
no, to je jeden z případů, které jsme nemohli skutečně vložit uzel

722
00:58:49,600 --> 00:58:52,730
do stromu, protože to znamená, že máme duplicitní hodnotu.

723
00:58:52,730 --> 00:58:59,010
Zde jsme vlastně bude vracet false.

724
00:58:59,010 --> 00:59:08,440
Nyní, jinak jestliže CUR je hodnota nižší než hodnota,

725
00:59:08,440 --> 00:59:10,930
Nyní víme, že jsme se pohybovat k pravému

726
00:59:10,930 --> 00:59:17,190
 protože hodnota patří v pravé polovině cur stromu.

727
00:59:17,190 --> 00:59:30,110
Jinak budeme pohybovat doleva.

728
00:59:30,110 --> 00:59:37,980
To je v podstatě naše obsahuje funkce přímo tam.

729
00:59:37,980 --> 00:59:41,820
>> V tomto bodě, jakmile jsme dokončili tento while,

730
00:59:41,820 --> 00:59:47,350
náš teď ukazatel se bude ukazovat na nulu

731
00:59:47,350 --> 00:59:51,540
v případě, že funkce není již vrátil.

732
00:59:51,540 --> 00:59:58,710
Máme proto mít CUR na místě, kde chceme vložit nový uzel.

733
00:59:58,710 --> 01:00:05,210
Co je ještě třeba udělat, je skutečně stavět nový uzel,

734
01:00:05,210 --> 01:00:08,480
které můžeme udělat docela snadno.

735
01:00:08,480 --> 01:00:14,930
Můžeme použít naše super-praktický sestavení uzlu funkci,

736
01:00:14,930 --> 01:00:17,210
a něco, co jsme neudělali dříve -

737
01:00:17,210 --> 01:00:21,400
jsme tak nějak brali za samozřejmost, ale teď budeme dělat, jen aby se ujistil -

738
01:00:21,400 --> 01:00:27,130
budeme testovat, aby se ujistil, že hodnota vrácená nový uzel byl vlastně

739
01:00:27,130 --> 01:00:33,410
není null, protože nechceme začít přístupu k této paměti, pokud je null.

740
01:00:33,410 --> 01:00:39,910
Můžeme testovat, aby se ujistil, že nový uzel není rovno null.

741
01:00:39,910 --> 01:00:42,910
Nebo místo, můžeme jen zjistit, jestli to vlastně je null,

742
01:00:42,910 --> 01:00:52,120
a pokud je null, pak se můžeme jen vrátit false brzy.

743
01:00:52,120 --> 01:00:59,090
>> V tomto bodě, musíme zapojit nový uzel do jeho příslušné místo ve stromu.

744
01:00:59,090 --> 01:01:03,510
Podíváme-li se zpět na hlavní a kde jsme byli vlastně kabeláž hodnoty před,

745
01:01:03,510 --> 01:01:08,470
vidíme, že způsob, jakým jsme to dělali, když jsme chtěli dát 3 ve stromu

746
01:01:08,470 --> 01:01:11,750
byla jsme vstoupili do levé dítě kořene.

747
01:01:11,750 --> 01:01:14,920
Když dáme 9 do stromu, jsme měli přístup k správné dítě kořene.

748
01:01:14,920 --> 01:01:21,030
Měli mít ukazatel na mateřské aby dal nové hodnoty do stromu.

749
01:01:21,030 --> 01:01:24,430
Rolování zpět vložit, že to nebude úplně fungovat zde

750
01:01:24,430 --> 01:01:27,550
protože nemáme nadřazené ukazatel.

751
01:01:27,550 --> 01:01:31,650
Co chceme být schopni udělat, je, v tomto bodě,

752
01:01:31,650 --> 01:01:37,080
zjistit hodnotu rodiče a vidět - dobře, sakra,

753
01:01:37,080 --> 01:01:41,990
pokud rodiče hodnota je nižší než aktuální hodnota,

754
01:01:41,990 --> 01:01:54,440
pak mateřského právo Dítě by mělo být nový uzel;

755
01:01:54,440 --> 01:02:07,280
jinak by se rodiče levá dítě bude nový uzel.

756
01:02:07,280 --> 01:02:10,290
Ale nemáme tento mateřský ukazatel ještě dost.

757
01:02:10,290 --> 01:02:15,010
>> S cílem získat to, jsme ve skutečnosti bude muset sledovat to, jak jsme jít přes strom

758
01:02:15,010 --> 01:02:18,440
a najít vhodné místo v našem smyčce výše.

759
01:02:18,440 --> 01:02:26,840
Můžeme to udělat, že přechodem zpět na začátek našeho vlož funkce

760
01:02:26,840 --> 01:02:32,350
a sledování jiného proměnnou ukazatele volal rodiče.

761
01:02:32,350 --> 01:02:39,340
Budeme ji nastavit rovná null zpočátku,

762
01:02:39,340 --> 01:02:43,640
a pak pokaždé, když jdeme přes strom,

763
01:02:43,640 --> 01:02:51,540
budeme nastavit nadřazené ukazatel tak, aby odpovídala aktuální ukazatel.

764
01:02:51,540 --> 01:02:59,140
Nastavit rodiče rovnající se součas.

765
01:02:59,140 --> 01:03:02,260
Tímto způsobem, pokaždé, když procházíme,

766
01:03:02,260 --> 01:03:05,550
budeme k zajištění toho, současný ukazatel dostane zvýšen

767
01:03:05,550 --> 01:03:12,640
mateřská ukazatel sleduje ji - jen o jeden stupeň vyšší, než je aktuální ukazatel ve stromu.

768
01:03:12,640 --> 01:03:17,370
To vše vypadá velmi dobře.

769
01:03:17,370 --> 01:03:22,380
>> Myslím, že jedna věc, kterou budete chtít upravit, je tento build uzlu vrací null.

770
01:03:22,380 --> 01:03:25,380
S cílem získat stavět uzel skutečně úspěšně vrátit null,

771
01:03:25,380 --> 01:03:31,060
budeme muset upravit tento kód,

772
01:03:31,060 --> 01:03:37,270
protože tady jsme nikdy testovány, aby se ujistil, že malloc vrací platný ukazatel.

773
01:03:37,270 --> 01:03:53,390
Takže, pokud (n = NULL!), Pak -

774
01:03:53,390 --> 01:03:55,250
pokud malloc vrací platný ukazatel, pak budeme ji inicializovat;

775
01:03:55,250 --> 01:04:02,540
jinak budeme jen vracet, a že skončí vrací hodnotu null pro nás.

776
01:04:02,540 --> 01:04:13,050
Nyní vše vypadá docela dobře. Pojďme ujistěte se, že to ve skutečnosti sestavuje.

777
01:04:13,050 --> 01:04:22,240
Udělejte binární strom, a oh, máme nějaké věci tu děje.

778
01:04:22,240 --> 01:04:29,230
>> Máme implicitní prohlášení funkcí stavět uzel.

779
01:04:29,230 --> 01:04:31,950
Opět, s těmito kompilátory, budeme začít nahoře.

780
01:04:31,950 --> 01:04:36,380
Co to musí znamenat, že volám stavět uzel než jsem vlastně deklaroval to.

781
01:04:36,380 --> 01:04:37,730
Vraťme se ke kódu opravdu rychle.

782
01:04:37,730 --> 01:04:43,510
Přejděte dolů, a opravdu, je prohlášen za moje vložka funkce

783
01:04:43,510 --> 01:04:47,400
nad uzlu sestavení funkce,

784
01:04:47,400 --> 01:04:50,070
ale já se snažím používat sestavení uzlu uvnitř vložky.

785
01:04:50,070 --> 01:05:06,610
Chystám se jít a kopie - a pak vložte uzlu sestavení funkční až sem na vrcholu.

786
01:05:06,610 --> 01:05:11,750
Tak, doufám, že bude fungovat. Dejme to jiného jít.

787
01:05:11,750 --> 01:05:18,920
Teď to všechno kompiluje. Vše je dobré.

788
01:05:18,920 --> 01:05:21,640
>> Ale v tomto bodě, jsme ve skutečnosti jen naše vložte funkci.

789
01:05:21,640 --> 01:05:26,510
Víme jen, že to překládá, tak pojďme dovnitř a dát nějaké hovory dovnitř

790
01:05:26,510 --> 01:05:28,240
Pojďme udělat, že v naší hlavní funkce.

791
01:05:28,240 --> 01:05:32,390
Zde jsme se v komentáři 5, 8 a 2,

792
01:05:32,390 --> 01:05:36,680
a pak jsme neměli propojte je nahoru dolů sem.

793
01:05:36,680 --> 01:05:41,640
Pojďme udělat některé hovory vložit,

794
01:05:41,640 --> 01:05:46,440
a pojďme také použít stejný druh věcí, které jsme použili

795
01:05:46,440 --> 01:05:52,810
když jsme se tyto printf volání, aby se ujistil, že vše se dostat správně vložena.

796
01:05:52,810 --> 01:06:00,550
Jdu kopírovat a vložit,

797
01:06:00,550 --> 01:06:12,450
a místo obsahuje budeme dělat vložku.

798
01:06:12,450 --> 01:06:30,140
A místo 6, 10, a 1, budeme používat 5, 8, a 2.

799
01:06:30,140 --> 01:06:37,320
To by snad vložit 5, 8, a 2 do stromu.

800
01:06:37,320 --> 01:06:44,050
Kompilace. Vše je dobré. Teď budeme vlastně běží náš program.

801
01:06:44,050 --> 01:06:47,330
>> Všechno se vrátil false.

802
01:06:47,330 --> 01:06:53,830
Takže, 5, 8, a 2 nešel, a vypadá to, že obsahuje nenalezl ani.

803
01:06:53,830 --> 01:06:58,890
Co se děje? Pojďme oddálit.

804
01:06:58,890 --> 01:07:02,160
Prvním problémem bylo, že vložka se zdálo vrátit false,

805
01:07:02,160 --> 01:07:08,750
a vypadá to, že je to proto, že jsme opustili v naší zpáteční falešné volání,

806
01:07:08,750 --> 01:07:14,590
a nikdy jsme vlastně vrátil pravda.

807
01:07:14,590 --> 01:07:17,880
Můžeme nastavit, aby se.

808
01:07:17,880 --> 01:07:25,290
Druhým problémem je, teď, i když jsme to - uložte tento, ukončete to,

809
01:07:25,290 --> 01:07:34,530
příkazem make znovu, že to zkompilovat, spusťte jej -

810
01:07:34,530 --> 01:07:37,670
vidíme, že něco jiného se tady stalo.

811
01:07:37,670 --> 01:07:42,980
5, 8, a 2 byly ještě nikdy nalezeny ve stromu.

812
01:07:42,980 --> 01:07:44,350
Takže, co se děje?

813
01:07:44,350 --> 01:07:45,700
>> Pojďme se podívat na to v kódu.

814
01:07:45,700 --> 01:07:49,790
Pojďme se podívat, jestli se nám podaří to vyřešit.

815
01:07:49,790 --> 01:07:57,940
Začneme s mateřskou není null.

816
01:07:57,940 --> 01:07:59,510
Jsme-li nastavit aktuální ukazatel ve výši do kořenového ukazatel,

817
01:07:59,510 --> 01:08:04,280
a budeme pracovat naši cestu dolů přes strom.

818
01:08:04,280 --> 01:08:08,650
Pokud je aktuální uzel není null, pak víme, že se může pohybovat dolů trochu.

819
01:08:08,650 --> 01:08:12,330
My jsme nastavili nadřazené ukazatel se rovná aktuální ukazatel,

820
01:08:12,330 --> 01:08:15,420
zkontrolovat hodnotu - v případě, že hodnoty jsou stejné jsme se vrátili false.

821
01:08:15,420 --> 01:08:17,540
Pokud jsou hodnoty méně jsme se přestěhovali doprava;

822
01:08:17,540 --> 01:08:20,399
jinak, jsme se přesunuli doleva.

823
01:08:20,399 --> 01:08:24,220
Pak jsme vybudovat uzel. Budu přiblížit trochu.

824
01:08:24,220 --> 01:08:31,410
A tady, budeme se snažit zapojit do hodnoty za stejné.

825
01:08:31,410 --> 01:08:37,250
Co se děje? Pojďme se podívat, když možná Valgrind nám může dát nápovědu.

826
01:08:37,250 --> 01:08:43,910
>> Rád používám Valgrind jen proto, že Valgrind opravdu rychle běží

827
01:08:43,910 --> 01:08:46,729
a řekne vám, zda existují nějaké chyby paměti.

828
01:08:46,729 --> 01:08:48,300
Když jsme se spustit Valgrind na kód,

829
01:08:48,300 --> 01:08:55,859
jak můžete vidět přímo here--Valgrind./binary_tree--and hit Enter.

830
01:08:55,859 --> 01:09:03,640
Můžete vidět, že jsme neměli žádnou chybu paměti, takže to vypadá, že je všechno v pořádku tak daleko.

831
01:09:03,640 --> 01:09:07,529
Máme nějaké úniky paměti, která známe, protože nejsme

832
01:09:07,529 --> 01:09:08,910
děje se uvolnit některý z našich uzlů.

833
01:09:08,910 --> 01:09:13,050
Zkusme běží GDB vidět, co se vlastně děje.

834
01:09:13,050 --> 01:09:20,010
Uděláme gdb. / Binary_tree. Je zaveden až v pohodě.

835
01:09:20,010 --> 01:09:23,670
Pojďme nastavit bod zlomu na vložky.

836
01:09:23,670 --> 01:09:28,600
Pojďme běžet.

837
01:09:28,600 --> 01:09:31,200
Vypadá to, že vlastně nikdy volal vložka.

838
01:09:31,200 --> 01:09:39,410
Vypadá to, že problém byl jen, že když jsem změnil sem v hlavním -

839
01:09:39,410 --> 01:09:44,279
všechny tyto printf volání z obsahuje -

840
01:09:44,279 --> 01:09:56,430
Nikdy jsem vlastně změnil nich volat vložky.

841
01:09:56,430 --> 01:10:01,660
Nyní pojďme to zkusit. Pojďme kompilaci.

842
01:10:01,660 --> 01:10:09,130
Všechny vypadá dobře tam. Nyní se pojďme zkusit spustit to, co se stane.

843
01:10:09,130 --> 01:10:13,320
Dobře! Všechno vypadá docela dobré.

844
01:10:13,320 --> 01:10:18,130
>> Poslední věc myslet, je, existují nějaké ostří případy, na této vložky?

845
01:10:18,130 --> 01:10:23,170
A ukázalo se, že dobře, jedna hrana případ, který je vždy zajímavé přemýšlet o tom,

846
01:10:23,170 --> 01:10:26,250
je, co se stane, když váš strom je prázdná a volat tuto funkci VLOŽENÍ?

847
01:10:26,250 --> 01:10:30,330
Bude to fungovat? Dobře, pojďme to zkusit.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Způsob, jakým budeme tento test je, že budeme chodit do naší hlavní funkci,

850
01:10:35,810 --> 01:10:41,690
a spíše než vedení těchto uzlů takhle,

851
01:10:41,690 --> 01:10:56,730
jsme jen tak, aby se vyjádřil ven celou věc,

852
01:10:56,730 --> 01:11:02,620
a místo toho, aby vedení až uzly vlastními silami,

853
01:11:02,620 --> 01:11:09,400
můžeme skutečně prostě jít dopředu a odstraňte vše.

854
01:11:09,400 --> 01:11:17,560
Budeme dělat všechno volání vložit.

855
01:11:17,560 --> 01:11:49,020
Takže, pojďme udělat - místo 5, 8, a 2, budeme vložit 7, 3 a 9.

856
01:11:49,020 --> 01:11:58,440
A pak budeme také chtít vložit 6 stejně.

857
01:11:58,440 --> 01:12:05,190
Uložit. Ukončete. Udělejte binární strom.

858
01:12:05,190 --> 01:12:08,540
To vše kompiluje.

859
01:12:08,540 --> 01:12:10,320
Můžeme jen spustit tak jak je a uvidíme, co se stane,

860
01:12:10,320 --> 01:12:12,770
ale je to také bude velmi důležité, aby se ujistil, že

861
01:12:12,770 --> 01:12:14,740
nemáme žádné chyby paměti,

862
01:12:14,740 --> 01:12:16,840
neboť to je jeden z našich okrajových případů, které jsme znát.

863
01:12:16,840 --> 01:12:20,150
>> Pojďme se ujistit, že to funguje dobře pod Valgrind,

864
01:12:20,150 --> 01:12:28,310
které budeme dělat, tím právě běží Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Vypadá to, že skutečně mají jednu chybu z jednoho kontextu -

866
01:12:31,110 --> 01:12:33,790
máme tuto chybu.

867
01:12:33,790 --> 01:12:36,690
Co se stalo?

868
01:12:36,690 --> 01:12:41,650
Valgrind vlastně nám říká, kde to je.

869
01:12:41,650 --> 01:12:43,050
Oddálení trochu.

870
01:12:43,050 --> 01:12:46,040
Vypadá to, že se to děje v naší vlož funkci,

871
01:12:46,040 --> 01:12:53,420
kde máme neplatný čtení o velikosti 4 na vložky, linka 60.

872
01:12:53,420 --> 01:13:03,590
Pojďme se vrátit zpět a zjistit, co se tu děje.

873
01:13:03,590 --> 01:13:05,350
Oddálení opravdu rychle.

874
01:13:05,350 --> 01:13:14,230
Chci se ujistit, že to není na okraj obrazovky, takže můžeme vidět všechno.

875
01:13:14,230 --> 01:13:18,760
Vytáhnout, že v trochu. Dobře.

876
01:13:18,760 --> 01:13:35,030
Přejděte dolů, a problém je tady.

877
01:13:35,030 --> 01:13:40,120
Co se stane, když se dostaneme dolů a naše aktuální uzel je již null,

878
01:13:40,120 --> 01:13:44,010
naše mateřská uzel je null, takže pokud se podíváme se na samém vrcholu, tady -

879
01:13:44,010 --> 01:13:47,340
v případě, že while nikdy provede

880
01:13:47,340 --> 01:13:52,330
protože naše současná hodnota je null - náš kořen je null, takže teď je null -

881
01:13:52,330 --> 01:13:57,810
pak naše mateřská nikdy nedostane nastavena na součas nebo na platnou hodnotu,

882
01:13:57,810 --> 01:14:00,580
tak, bude rodič zároveň mít hodnotu null.

883
01:14:00,580 --> 01:14:03,700
Musíme mít na paměti, pro kontrolu, že

884
01:14:03,700 --> 01:14:08,750
v době, kdy jsme se sem dolů, a začneme přístup na hodnotu rodiče.

885
01:14:08,750 --> 01:14:13,190
Takže, co se stane? No, pokud rodič je null -

886
01:14:13,190 --> 01:14:17,990
if (rodič == NULL) - pak víme, že

887
01:14:17,990 --> 01:14:19,530
tam nesmí být nic ve stromu.

888
01:14:19,530 --> 01:14:22,030
Musíme se snažit, aby ji vložte u kořene.

889
01:14:22,030 --> 01:14:32,570
My může provést tak, že pouze nastavení kořen rovnající se nový uzel.

890
01:14:32,570 --> 01:14:40,010
Pak v tomto bodě, nemáme vlastně chceme jít přes tyto jiné.

891
01:14:40,010 --> 01:14:44,780
Místo toho, tady, můžeme udělat buď jinde-if-else,

892
01:14:44,780 --> 01:14:47,610
nebo můžeme spojit vše, co se zde v jiný,

893
01:14:47,610 --> 01:14:56,300
ale tady budeme jen používat jiný, a to tímto způsobem.

894
01:14:56,300 --> 01:14:59,030
Nyní, budeme testovat, aby se ujistil, že naše mateřská není null

895
01:14:59,030 --> 01:15:02,160
do té doby vlastně snaží přístup k jeho pole.

896
01:15:02,160 --> 01:15:05,330
To nám pomůže vyhnout se segmentation fault.

897
01:15:05,330 --> 01:15:14,740
Takže, jsme přestat, oddálit, zkompilovat, spustit.

898
01:15:14,740 --> 01:15:18,130
>> Žádné chyby, ale máme před sebou ještě spoustu úniky paměti

899
01:15:18,130 --> 01:15:20,650
protože jsme neměli uvolnit některý z našich uzlů.

900
01:15:20,650 --> 01:15:24,350
Ale, když jdeme sem a my se podívat na naši výtisk,

901
01:15:24,350 --> 01:15:30,880
vidíme, že dobře, vypadá stejně jako všechny naše vložek bylo vrací hodnotu true, což je dobré.

902
01:15:30,880 --> 01:15:33,050
Vložky jsou všechny pravdivé,

903
01:15:33,050 --> 01:15:36,670
a pak příslušné obsahuje volání platí také.

904
01:15:36,670 --> 01:15:41,510
>> Dobrá práce! Vypadá to, že jsme úspěšně zapsán vložku.

905
01:15:41,510 --> 01:15:47,430
To je všechno, co máme pro tento týden Specifikace problému Set.

906
01:15:47,430 --> 01:15:51,720
Jedna zábavná výzva přemýšlet o tom, jak byste vlastně jít

907
01:15:51,720 --> 01:15:55,340
a bez všech uzlů v tomto stromu.

908
01:15:55,340 --> 01:15:58,830
Můžeme tak učinit řadu různých způsobů,

909
01:15:58,830 --> 01:16:01,930
ale nechám, že na vás experimentovat,

910
01:16:01,930 --> 01:16:06,080
a jako zábavu výzvu, vyzkoušet a ujistěte se, že si můžete být jisti

911
01:16:06,080 --> 01:16:09,490
že tato zpráva Valgrind Nebyly nalezeny žádné chyby a žádné úniky.

912
01:16:09,490 --> 01:16:12,880
>> Hodně štěstí na tento týden Huffman kódování problému nastavení,

913
01:16:12,880 --> 01:16:14,380
a uvidíme se příští týden!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]