1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [§ 7] [menej 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
>> Vitajte v § 7.

5
00:00:09,080 --> 00:00:11,330
Vďaka hurikánu Sandy,

6
00:00:11,330 --> 00:00:13,440
namiesto toho, aby normálne časť tento týždeň,

7
00:00:13,440 --> 00:00:17,650
robíme to priechodná, prostredníctvom sekcie otázok.

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

9
00:00:22,830 --> 00:00:25,650
a prechádzajú všetky otázky v

10
00:00:25,650 --> 00:00:27,770
Sekcie Otázky sekcie.

11
00:00:27,770 --> 00:00:30,940
Ak máte nejaké otázky,

12
00:00:30,940 --> 00:00:32,960
prosím poslať tieto na CS50 diskutovať.

13
00:00:32,960 --> 00:00:35,480
>> Dobre. Poďme začať.

14
00:00:35,480 --> 00:00:40,780
Práve teraz sa pozerám na strane 3 špecifikácia problému Set.

15
00:00:40,780 --> 00:00:44,110
Budeme najprv začať hovoriť o binárnych stromoch

16
00:00:44,110 --> 00:00:47,850
pretože tie majú veľa dôležité pre tento týždeň problému set -

17
00:00:47,850 --> 00:00:49,950
Strom Huffman kódovanie.

18
00:00:49,950 --> 00:00:55,000
Jedným z prvých dátových štruktúr sme o tom hovorili na CS50 bolo pole.

19
00:00:55,000 --> 00:01:00,170
Si uvedomiť, že pole je postupnosť prvkov -

20
00:01:00,170 --> 00:01:04,019
všetky rovnakého typu - uložené priamo vedľa seba v pamäti.

21
00:01:04,019 --> 00:01:14,420
Ak mám celé číslo poľa, ktoré môžem čerpať pomocou tohto boxy-čísla-celé čísla štýl -

22
00:01:14,420 --> 00:01:20,290
Povedzme, že mám 5 v prvom poli, mám 7 v druhom,

23
00:01:20,290 --> 00:01:27,760
potom som si 8, 10, a 20 v konečnom poli.

24
00:01:27,760 --> 00:01:33,000
Nezabudnite, naozaj dva dobré veci o tomto poli

25
00:01:33,000 --> 00:01:38,800
je, že máme túto konštantu-time prístup k akejkoľvek konkrétnej prvok

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

27
00:01:40,500 --> 00:01:44,670
Napríklad, ak chcem chytiť tretí prvok v poli -

28
00:01:44,670 --> 00:01:47,870
na indexe 2 pomocou nášho nuly indexovanie systému -

29
00:01:47,870 --> 00:01:52,220
Doslova som jednoducho urobiť jednoduchý matematický výpočet,

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

31
00:01:56,170 --> 00:01:57,840
vytiahnite 8, ktorý je uložený tam,

32
00:01:57,840 --> 00:01:59,260
a ja som dobré ísť.

33
00:01:59,260 --> 00:02:03,350
>> Jedným zo zlých vecí na tomto poli -, že sme o tom hovorili

34
00:02:03,350 --> 00:02:05,010
keď sme hovorili o prepojených zoznamov -

35
00:02:05,010 --> 00:02:09,120
je, že keď chcem vložiť prvok do tohto poľa,

36
00:02:09,120 --> 00:02:11,090
Budem musieť urobiť nejaké radenie okolí.

37
00:02:11,090 --> 00:02:12,940
Napríklad, toto pole tu

38
00:02:12,940 --> 00:02:16,850
je v triedenom poriadku - vo vzostupnom poradí -

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

40
00:02:19,440 --> 00:02:23,100
ale keď chcem vložiť číslo 9 do tohto poľa,

41
00:02:23,100 --> 00:02:27,460
Budem musieť posunúť niektoré prvky, aby miesto.

42
00:02:27,460 --> 00:02:30,440
Môžeme čerpať túto tu.

43
00:02:30,440 --> 00:02:35,650
Budem musieť presunúť 5, 7, a potom 8;

44
00:02:35,650 --> 00:02:38,720
vytvoriť medzeru, kde som môžete dať 9,

45
00:02:38,720 --> 00:02:45,910
a potom 10 a 20 môže ísť na pravej strane 9.

46
00:02:45,910 --> 00:02:49,450
To je druh bolesti, pretože v najhoršom prípade -

47
00:02:49,450 --> 00:02:54,350
keď sme s vložiť buď na začiatku a na konci

48
00:02:54,350 --> 00:02:56,040
z poľa, v závislosti na tom, ako sme posúvanie -

49
00:02:56,040 --> 00:02:58,850
môžeme skončiť museli posunúť všetky prvky

50
00:02:58,850 --> 00:03:00,750
že sa to v súčasnej dobe skladovania v poli.

51
00:03:00,750 --> 00:03:03,810
>> Takže, čo bolo ako vyriešiť tento problém?

52
00:03:03,810 --> 00:03:09,260
Cesta okolo to bolo ísť do nášho Linked-zoznam metóda, kde -

53
00:03:09,260 --> 00:03:19,820
miesto uloženia prvkov 5, 7, 8, 10, a 20 všetky vedľa seba v pamäti -

54
00:03:19,820 --> 00:03:25,630
to, čo sme namiesto toho som bola ukladať im druhu tam, kde sme chceli uložiť

55
00:03:25,630 --> 00:03:32,470
v týchto linked-zoznam uzlov, ktoré som kreslenie tu, druh ad hoc.

56
00:03:32,470 --> 00:03:42,060
A potom sme spojili dohromady pomocou týchto ďalších ukazovateľov.

57
00:03:42,060 --> 00:03:44,370
Môžem mať ukazovateľ z 5 na 7,

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

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

60
00:03:47,770 --> 00:03:51,220
a konečne, ukazovateľ od 10 do 20,

61
00:03:51,220 --> 00:03:54,880
a potom nulový ukazovateľ na 20 naznačuje, že nič nezostalo.

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 teraz chceme vložiť číslo 9 do nášho zoznamu zoradené,

64
00:04:05,360 --> 00:04:08,270
všetko, čo musíme urobiť, je vytvoriť nový uzol s 9,

65
00:04:08,270 --> 00:04:12,290
bola pripojená až k bodu na príslušné miesto,

66
00:04:12,290 --> 00:04:20,630
a potom sa znova drôt 8 ukazoval dole do 9..

67
00:04:20,630 --> 00:04:25,660
To je celkom jednoduché, za predpokladu, že presne vieme, kam chceme vložiť 9.

68
00:04:25,660 --> 00:04:32,610
Ale trade-off výmenou za to, že sme dnes stratili konštantný časový prístup

69
00:04:32,610 --> 00:04:36,230
pre konkrétny prvok v našej dátovej štruktúry.

70
00:04:36,230 --> 00:04:40,950
Napríklad, ak chcem nájsť štvrtý prvok v tomto prepojenom zozname,

71
00:04:40,950 --> 00:04:43,510
Budem musieť začať na začiatku zoznamu

72
00:04:43,510 --> 00:04:48,930
a pracovať svoju cestu cez počítanie uzlov s-node, až nájdem štvrtom.

73
00:04:48,930 --> 00:04:55,870
>> S cieľom získať lepší prístup k výkonu ako prepojeného zoznamu -

74
00:04:55,870 --> 00:04:59,360
ale aj udržať niektoré z výhod, ktoré sme mali

75
00:04:59,360 --> 00:05:01,800
pokiaľ ide o vloženie čase z prepojeného zoznamu -

76
00:05:01,800 --> 00:05:05,750
binárny strom bude potrebovať trochu viac pamäte.

77
00:05:05,750 --> 00:05:11,460
Najmä, namiesto toho, aby len s jednou ukazovateľ v binárnom stromu uzla -

78
00:05:11,460 --> 00:05:13,350
ako linked-zozname uzol robí -

79
00:05:13,350 --> 00:05:16,950
budeme chcete pridať druhý ukazovateľ do binárneho stromu uzol.

80
00:05:16,950 --> 00:05:19,950
Skôr než len s jednou ukazovateľ na ďalší prvok,

81
00:05:19,950 --> 00:05:24,420
budeme mať ukazovateľ na ľavej dieťa a pravej dieťa.

82
00:05:24,420 --> 00:05:26,560
>> Poďme nakresliť obrázok, čo to vlastne vyzerá.

83
00:05:26,560 --> 00:05:31,350
Opäť, budem používať tieto krabice a šípy.

84
00:05:31,350 --> 00:05:37,150
Binárne strom uzol bude začať s jednoduchým krabici.

85
00:05:37,150 --> 00:05:40,940
To bude mať priestor pre hodnotu,

86
00:05:40,940 --> 00:05:47,280
a potom je to tiež bude mať priestor pre ľavé dieťa a pravej dieťa.

87
00:05:47,280 --> 00:05:49,280
Chystám sa popísať tu.

88
00:05:49,280 --> 00:05:57,560
Budeme mať ľavej dieťa, a potom budeme mať ten správny dieťa.

89
00:05:57,560 --> 00:05:59,920
Existuje mnoho rôznych spôsobov, ako to urobiť.

90
00:05:59,920 --> 00:06:02,050
Niekedy na priestor a pohodlie,

91
00:06:02,050 --> 00:06:06,460
Budem vlastne kresliť ako ja tu robím na dne

92
00:06:06,460 --> 00:06:10,910
kde budem mať hodnotu na vrchole,

93
00:06:10,910 --> 00:06:14,060
a potom na pravej dieťa na pravej dolnej,

94
00:06:14,060 --> 00:06:16,060
a vľavo dieťa na dole vľavo.

95
00:06:16,060 --> 00:06:20,250
Vráťme sa späť k tomuto hore diagramu,

96
00:06:20,250 --> 00:06:22,560
máme hodnotu na samom vrchole,

97
00:06:22,560 --> 00:06:25,560
potom máme na ľavej dieťa ukazovateľ, a potom máme právo-dieťa ukazovateľ.

98
00:06:25,560 --> 00:06:30,110
>> V problému Nastaviť špecifikácie,

99
00:06:30,110 --> 00:06:33,110
Ak hovoríme o kreslenie uzol, ktorý má hodnotu 7,

100
00:06:33,110 --> 00:06:39,750
a potom ľavej dieťa ukazovateľ, ktorý je nulový, a pravým dieťa ukazovateľ, ktorý je prázdny.

101
00:06:39,750 --> 00:06:46,040
Môžeme buď napísať kapitálové NULL v priestore pre

102
00:06:46,040 --> 00:06:51,610
ako ľavej dieťa a právo dieťaťa, alebo môžeme čerpať tento uhloprieč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
Ja budem robiť, že práve preto, že je to jednoduchšie.

105
00:06:57,560 --> 00:07:03,700
To, čo vidíte tu sú dva spôsoby, ako diagramov veľmi jednoduchý binárny strom uzol

106
00:07:03,700 --> 00:07:07,960
kde máme hodnotu 7 a nulové podriadené uvedieme.

107
00:07:07,960 --> 00:07:15,220
>> Druhá časť našich špecifikácia hovorí o tom, ako s lineárnymi zoznamy -

108
00:07:15,220 --> 00:07:18,270
pamätajte, sme mali len držať na úplne prvý prvok v zozname

109
00:07:18,270 --> 00:07:20,270
pamätať celý zoznam -

110
00:07:20,270 --> 00:07:26,140
a podobne, s binárneho stromu, máme len držať na jednej ukazovateľ na strom

111
00:07:26,140 --> 00:07:31,120
za účelom zachovania kontroly nad celou dátové štruktúry.

112
00:07:31,120 --> 00:07:36,150
Táto špeciálna prvok stromu sa nazýva koreň stromu.

113
00:07:36,150 --> 00:07:43,360
Napríklad, ak sa tento uzol - to uzol obsahujúci hodnotu 7

114
00:07:43,360 --> 00:07:45,500
s null ľavej a pravej dieťa ukazovateľov -

115
00:07:45,500 --> 00:07:47,360
boli iba hodnota v našom stromu,

116
00:07:47,360 --> 00:07:50,390
potom by to byť náš koreňový uzol.

117
00:07:50,390 --> 00:07:52,240
Je to úplne na začiatku nášho stromu.

118
00:07:52,240 --> 00:07:58,530
Vidíme to trochu jasnejšie, akonáhle začneme pridávať ďalšie uzly náš strom.

119
00:07:58,530 --> 00:08:01,510
Dovoľte mi, aby som vytiahnuť novú stránku.

120
00:08:01,510 --> 00:08:05,000
>> Teraz budeme kresliť strom, ktorý má 7 pri koreni,

121
00:08:05,000 --> 00:08:10,920
a 3 vnútri ľavého dieťaťa, a 9 vnútro pravé dieťa.

122
00:08:10,920 --> 00:08:13,500
Opäť, to je celkom jednoduchý.

123
00:08:13,500 --> 00:08:26,510
Máme 7, nakreslite uzol 3, uzol pre 9,

124
00:08:26,510 --> 00:08:32,150
a ja idem nastaviť ľavú dieťa ukazovateľ 7 ukazoval na uzol obsahujúci 3,

125
00:08:32,150 --> 00:08:37,850
a pravej dieťa ukazovateľ na uzol obsahujúci 7 k uzla obsahujúce 9.

126
00:08:37,850 --> 00:08:42,419
Teraz, od 3 a 9 nemajú žiadne deti,

127
00:08:42,419 --> 00:08:48,500
budeme nastaviť všetky ich podriadené ukazovatele budú mať hodnotu null.

128
00:08:48,500 --> 00:08:56,060
Tu, koreň našej stromu zodpovedá uzla obsahujúce číslo 7.

129
00:08:56,060 --> 00:09:02,440
Môžete vidieť, že ak všetko, čo máme, je ukazovateľ na tento koreňový uzol,

130
00:09:02,440 --> 00:09:07,330
potom môžeme prejsť náš strom a prístup k obom podriadené uzly -

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

132
00:09:10,630 --> 00:09:14,820
Nie je potrebné zachovať odkazy na jednotlivý uzol na strome.

133
00:09:14,820 --> 00:09:22,080
Dobre. Teraz budeme pridávať ďalšie uzol na tomto schéme.

134
00:09:22,080 --> 00:09:25,370
Budeme chcete pridať uzol obsahujúci 6,

135
00:09:25,370 --> 00:09:34,140
a budeme pridávať to ako pravé dieťa uzla obsahujúceho 3.

136
00:09:34,140 --> 00:09:41,850
Ak sa chcete, že budem mazať, že nulový ukazovateľ v 3-uzol

137
00:09:41,850 --> 00:09:47,750
bola pripojená až k bodu na uzol obsahujúci 6. Dobre.

138
00:09:47,750 --> 00:09:53,800
>> V tomto bode, poďme cez trochou terminológie.

139
00:09:53,800 --> 00:09:58,230
Ak chcete začať, dôvod, že tento sa nazýva binárny strom, najmä

140
00:09:58,230 --> 00:10:00,460
je to, že má dva podriadené ukazovatele.

141
00:10:00,460 --> 00:10:06,020
Existujú aj iné druhy stromov, ktoré majú viac detí ukazovatele.

142
00:10:06,020 --> 00:10:10,930
Najmä, ste "vyskúšať" v probléme Set 5.

143
00:10:10,930 --> 00:10:19,310
Určite ste si všimli, že v tomto pokuse, ste mali 27 rôznych ukazovateľov na rôzne deti -

144
00:10:19,310 --> 00:10:22,410
jeden pre každú z 26 písmen v anglickej abecede,

145
00:10:22,410 --> 00:10:25,410
a potom 27. pre apostrof -

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 tu, pretože je to binárny, máme len dve podriadené ukazovatele.

148
00:10:34,070 --> 00:10:37,880
>> Okrem tohto koreňového uzla, ktorý sme hovorili,

149
00:10:37,880 --> 00:10:41,470
sme tiež hádže okolo tohto pojmu "dieťa."

150
00:10:41,470 --> 00:10:44,470
Čo to znamená pre jeden uzol, aby sa dieťa iného uzla?

151
00:10:44,470 --> 00:10:54,060
To znamená, že sa doslova podriadený uzol je dieťa ďalšieho uzla

152
00:10:54,060 --> 00:10:58,760
ak je toto uzol má jeden z jeho podriadených ukazovateľov stanovených upozorniť na tento uzol.

153
00:10:58,760 --> 00:11:01,230
K tomu, aby to do viac konkrétnych podmienkach,

154
00:11:01,230 --> 00:11:11,170
ak 3 je zameraná na jeden z detských ukazovateľov z 7, potom 3 je dieťa 7.

155
00:11:11,170 --> 00:11:14,510
Ak by sme mali prísť na to, čo deti 7 árov -

156
00:11:14,510 --> 00:11:18,510
dobre, vidíme, že 7 má ukazovateľ na 3 a ukazovateľ na 9,

157
00:11:18,510 --> 00:11:22,190
tak 9 a 3 sú deti 7.

158
00:11:22,190 --> 00:11:26,650
Deväť nemá žiadne deti, pretože jeho podriadené ukazovatele sú null,

159
00:11:26,650 --> 00:11:30,940
a 3 má iba jedno dieťa, 6.

160
00:11:30,940 --> 00:11:37,430
Šesť tiež nemá žiadne deti, pretože oba jeho ukazovateľov sú null, ktoré budeme čerpať hneď.

161
00:11:37,430 --> 00:11:45,010
>> Okrem toho sme tiež hovoriť o rodičoch určitého uzla,

162
00:11:45,010 --> 00:11:51,100
a to je, ako by ste očakávali, opak tohto dieťaťa popisu.

163
00:11:51,100 --> 00:11:58,620
Každý uzol má len jedného rodiča - namiesto dvoch ako sa dalo očakávať s ľuďmi.

164
00:11:58,620 --> 00:12:03,390
Napríklad, nadradený 3 je 7.

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

166
00:12:10,800 --> 00:12:15,720
Máme tiež podmienky hovoriť o starých rodičov a vnúčat,

167
00:12:15,720 --> 00:12:18,210
a všeobecnejšie budeme hovoriť o predkoch

168
00:12:18,210 --> 00:12:20,960
a potomkovia v konkrétnom uzle.

169
00:12:20,960 --> 00:12:25,710
Predchodca uzla - alebo predkovia, skôr o uzle -

170
00:12:25,710 --> 00:12:32,730
sú všetky uzly, ktoré leží na ceste od koreňa k tomuto uzlu.

171
00:12:32,730 --> 00:12:36,640
Napríklad, keď som pri pohľade na uzla 6,

172
00:12:36,640 --> 00:12:46,430
potom predkovia sa bude aj 3 a 7.

173
00:12:46,430 --> 00:12:55,310
Predkovia 9, napríklad, sú - keď som pri pohľade na uzla 9 -

174
00:12:55,310 --> 00:12:59,990
potom predok 9 je len 7.

175
00:12:59,990 --> 00:13:01,940
A potomkovia sú presne naopak.

176
00:13:01,940 --> 00:13:05,430
Ak sa chcem pozrieť na všetky potomkov 7,

177
00:13:05,430 --> 00:13:11,020
potom som sa pozrieť na všetky uzly pod ním.

178
00:13:11,020 --> 00:13:16,950
Takže, mám 3, 9, a 6 všetky ako potomkov 7.

179
00:13:16,950 --> 00:13:24,170
>> Konečný termín, ktorý budeme hovoriť, je tento pojem je súrodenec.

180
00:13:24,170 --> 00:13:27,980
Súrodenci - druh po pozdĺž týchto rodinných podmienok -

181
00:13:27,980 --> 00:13:33,150
sú uzly, ktoré sú na rovnakej úrovni vo stromu.

182
00:13:33,150 --> 00:13:42,230
Takže, 3 a 9 sú súrodenci, pretože sú na rovnakej úrovni vo stromu.

183
00:13:42,230 --> 00:13:46,190
Obaja majú rovnaké rodičia, 7.

184
00:13:46,190 --> 00:13:51,400
6 nemá žiadne súrodenca, pretože 9 nemá žiadne deti.

185
00:13:51,400 --> 00:13:55,540
A 7 nemá žiadne súrodenca, pretože je to koreň nášho stromu,

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

187
00:13:59,010 --> 00:14:02,260
Na 7 majú súrodencov by muselo byť uzol nad 7.

188
00:14:02,260 --> 00:14:07,480
Tam by mal byť rodič 7, v takom prípade 7 by už byť koreňom stromu.

189
00:14:07,480 --> 00:14:10,480
Potom, že nová materská 7 by tiež mala mať dieťa,

190
00:14:10,480 --> 00:14:16,480
a že dieťa by potom byť súrodenec 7.

191
00:14:16,480 --> 00:14:21,040
>> Dobre. Ďalej.

192
00:14:21,040 --> 00:14:24,930
Keď sme začali náš rozhovor binárnych stromov,

193
00:14:24,930 --> 00:14:28,790
sme sa rozprávali o tom, ako sme chceli použiť na

194
00:14:28,790 --> 00:14:32,800
získať výhodu nad oboch poliach a vzájomne previazaných zoznamov.

195
00:14:32,800 --> 00:14:37,220
A spôsob, akým budeme robiť, že je s týmto usporiadanie majetku.

196
00:14:37,220 --> 00:14:41,080
Môžeme povedať, že binárny strom je nariadené, v súlade so špecifikáciou,

197
00:14:41,080 --> 00:14:45,740
ak pre každý uzol v našom stromu, všetky jeho potomkov vľavo -

198
00:14:45,740 --> 00:14:48,670
ľavej dieťa a všetky ľavej dieťa potomkov -

199
00:14:48,670 --> 00:14:54,510
majú menšie hodnoty, a všetky uzly na pravej strane -

200
00:14:54,510 --> 00:14:57,770
právo dieťa a všetky pravé dieťa potomkov -

201
00:14:57,770 --> 00:15:02,800
majú uzly väčšia ako hodnota aktuálneho uzla, ktorý sa práve pozeráte.

202
00:15:02,800 --> 00:15:07,850
Len pre jednoduchosť, budeme predpokladať, že tu nie sú žiadne duplicitné uzly v našom stromu.

203
00:15:07,850 --> 00:15:11,180
Napríklad, v tejto vetve nebudeme zaoberať sa prípadom

204
00:15:11,180 --> 00:15:13,680
kde majú hodnotu 7 pri koreni

205
00:15:13,680 --> 00:15:16,720
 a potom tiež majú hodnotu 7 inde vo stromu.

206
00:15:16,720 --> 00:15:24,390
V tomto prípade, všimnete si, že tento strom je naozaj nariadil.

207
00:15:24,390 --> 00:15:26,510
Máme hodnotu 7 v koreňovom adresári.

208
00:15:26,510 --> 00:15:29,720
Všetko na ľavej strane 7 -

209
00:15:29,720 --> 00:15:35,310
keď som späť všetky z týchto maličkých značiek tu -

210
00:15:35,310 --> 00:15:40,450
všetko vľavo 7 - 3 a 6 -

211
00:15:40,450 --> 00:15:49,410
tieto hodnoty sú obaja menej ako 7, a všetko vpravo - čo je presne to 9 -

212
00:15:49,410 --> 00:15:53,450
je väčšia ako 7.

213
00:15:53,450 --> 00:15:58,650
>> To však nie je jediným objednať strom obsahujúce tieto hodnoty,

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

215
00:16:03,120 --> 00:16:05,030
Tam je skutočne celá partia spôsobov, ako to môžeme urobiť.

216
00:16:05,030 --> 00:16:09,380
Budem používať tesnopis len aby to jednoduché, ak -

217
00:16:09,380 --> 00:16:11,520
skôr než preťahoval celé krabice-a šípy -

218
00:16:11,520 --> 00:16:14,220
Ja som jednoducho ísť kresliť čísla a pridajte šípky je spájajú.

219
00:16:14,220 --> 00:16:22,920
Ak chcete začať, jednoducho budeme písať naše pôvodné strom zase tam, kde sme mali 7, a potom 3,

220
00:16:22,920 --> 00:16:25,590
a potom 3 ukazuje smerom vpravo na 6,

221
00:16:25,590 --> 00:16:30,890
a 7 mal právo dieťaťa, ktoré bolo 9.

222
00:16:30,890 --> 00:16:33,860
Dobre. Čo je ďalší spôsob, ako by sme mohli napísať tento strom?

223
00:16:33,860 --> 00:16:38,800
Namiesto toho, aby 3 je vľavo dieťa 7,

224
00:16:38,800 --> 00:16:41,360
môžeme tiež 6 bude ľavá dieťa 7,

225
00:16:41,360 --> 00:16:44,470
a potom 3 musí byť na ľavej dieťaťom 6.

226
00:16:44,470 --> 00:16:48,520
To by vyzerať ako na tomto stromu priamo tu, kde mám 7,

227
00:16:48,520 --> 00:16:57,860
potom 6, potom 3, a 9 na pravej strane.

228
00:16:57,860 --> 00:17:01,490
My tiež nemusí mať 7 ako naše koreňového uzla.

229
00:17:01,490 --> 00:17:03,860
Mohli by sme tiež mať 6 ako náš koreňový uzol.

230
00:17:03,860 --> 00:17:06,470
Čo by to vyzerať?

231
00:17:06,470 --> 00:17:09,230
Ak budeme udržiavať túto objednanú vlastnosť,

232
00:17:09,230 --> 00:17:12,970
všetko vľavo od 6 musí byť menší než to.

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

234
00:17:16,540 --> 00:17:19,869
Ale potom ako pravé dieťa 6, máme dve možnosti.

235
00:17:19,869 --> 00:17:25,380
Po prvé, mohli by sme mať 7 a potom 9,

236
00:17:25,380 --> 00:17:28,850
alebo môžeme kresliť - ako by som chcel robiť tu -

237
00:17:28,850 --> 00:17:34,790
kde máme 9 ako pravé dieťa v 6,

238
00:17:34,790 --> 00:17:39,050
a potom sa 7 ako ľavé podriadený 9.

239
00:17:39,050 --> 00:17:44,240
>> Teraz, 7 a 6 nie sú jediné možné hodnoty pre koreň.

240
00:17:44,240 --> 00:17:50,200
Mohli by sme tiež 3 musí byť v koreňovom adresári.

241
00:17:50,200 --> 00:17:52,240
Čo sa stane, keď 3 je pri koreni?

242
00:17:52,240 --> 00:17:54,390
Tu, veci sa trochu zaujímavé.

243
00:17:54,390 --> 00:17:58,440
Tri nemá žiadne hodnoty, ktoré sú menšie ako to,

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

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

246
00:18:03,230 --> 00:18:07,220
Na pravej strane, mohli by sme uviesť veci vo vzostupnom poradí.

247
00:18:07,220 --> 00:18:15,530
Mohli by sme mať 3, potom 6, potom 7, potom 9.

248
00:18:15,530 --> 00:18:26,710
Alebo by sme to mohli urobiť 3, potom 6, potom 9, potom 7.

249
00:18:26,710 --> 00:18:35,020
Alebo by sme to mohli urobiť 3, potom 7, potom 6, potom 9.

250
00:18:35,020 --> 00:18:40,950
Alebo, 3, 7 - vlastne nie, nemôžeme urobiť 7 už.

251
00:18:40,950 --> 00:18:43,330
To je naša jediná vec tam.

252
00:18:43,330 --> 00:18:54,710
Môžeme to urobiť 9, a potom z 9 môžeme urobiť 6 a potom 7.

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

254
00:19:06,980 --> 00:19:12,490
>> Jedna vec je upozorniť na tu

255
00:19:12,490 --> 00:19:14,510
že tieto stromy sú trochu divný-pozerať.

256
00:19:14,510 --> 00:19:17,840
Najmä, ak sa pozrieme na 4 stromy na pravej strane -

257
00:19:17,840 --> 00:19:20,930
Budem obiehať je, tu -

258
00:19:20,930 --> 00:19:28,410
Tieto stromy vyzerajú takmer rovnako ako prepojeného zoznamu.

259
00:19:28,410 --> 00:19:32,670
Každý uzol má iba jedno dieťa,

260
00:19:32,670 --> 00:19:38,950
a tak nie je k dispozícii žiadny z tohto stromovej štruktúry, ktoré vidíme, napríklad,

261
00:19:38,950 --> 00:19:44,720
 v tejto jednej osamelý strom cez tu na ľavom dolnom rohu.

262
00:19:44,720 --> 00:19:52,490
Tieto stromy sú vlastne len degenerujú binárne stromy,

263
00:19:52,490 --> 00:19:54,170
a budeme hovoriť o nich viac v budúcnosti -

264
00:19:54,170 --> 00:19:56,730
najmä ak idete na prijať ďalšie kurzy informatiky.

265
00:19:56,730 --> 00:19:59,670
Tieto stromy sú degenerované.

266
00:19:59,670 --> 00:20:03,780
Sú to veľmi užitočné, pretože skutočne, táto štruktúra prepožičiava

267
00:20:03,780 --> 00:20:08,060
 k vyhľadávaniu časy podobné ako prepojeného zoznamu.

268
00:20:08,060 --> 00:20:13,050
Nechceme sa využiť extra pamäte - tento dodatočný ukazovateľ -

269
00:20:13,050 --> 00:20:18,840
pretože našej štruktúry je zlá týmto spôsobom.

270
00:20:18,840 --> 00:20:24,700
Skôr než ísť ďalej a upozorniť na binárne stromy, ktoré majú 9 pri koreni,

271
00:20:24,700 --> 00:20:27,220
ktorá je konečným prípad, že by mohol byť

272
00:20:27,220 --> 00:20:32,380
sme miesto, v tomto bode, bude hovoriť trochu o tomto iný termín

273
00:20:32,380 --> 00:20:36,150
že používame, keď hovoríme o stromoch, ktoré sa nazýva výška.

274
00:20:36,150 --> 00:20:45,460
>> Výška stromu je vzdialenosť od koreňa k najviac vzdialené uzla,

275
00:20:45,460 --> 00:20:48,370
alebo skôr počet chmeľu, ktoré by sa, aby sa za účelom

276
00:20:48,370 --> 00:20:53,750
začať od koreňa a potom skončí na najviac vzdialené uzla v strome.

277
00:20:53,750 --> 00:20:57,330
Ak sa pozrieme na niektoré z týchto stromov, ktoré sme vypracovali tu,

278
00:20:57,330 --> 00:21:07,870
môžeme vidieť, že ak budeme mať tento strom v ľavom hornom rohu a začneme na 3,

279
00:21:07,870 --> 00:21:14,510
potom musíme urobiť 1 hop sa dostať na 6, druhá hop sa dostať do 7,

280
00:21:14,510 --> 00:21:20,560
a tretia hop sa dostať do 9.

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

282
00:21:26,120 --> 00:21:30,640
Môžeme to urobiť rovnaký výkon pre 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šetkých týchto stromov je tiež naozaj 3.

284
00:21:40,100 --> 00:21:45,230
To je súčasťou toho, čo robí je zvrhlík -

285
00:21:45,230 --> 00:21:53,750
, Že ich výška je len jeden menej ako je počet uzlov v celom stromu.

286
00:21:53,750 --> 00:21:58,400
Ak sa pozrieme na tento druhý strom, ktorý je obklopený s červenou, na strane druhej,

287
00:21:58,400 --> 00:22:03,920
vidíme, že najviac vzdialené koncové uzly sú 6 a 9 -

288
00:22:03,920 --> 00:22:06,940
listy, čo sú uzly, ktoré nemajú žiadne deti.

289
00:22:06,940 --> 00:22:11,760
Takže, aby sa dostal z koreňového uzla buď 6 alebo 9,

290
00:22:11,760 --> 00:22:17,840
musíme urobiť jednu hop sa dostať na 7 a potom druhé hop sa dostať do 9,

291
00:22:17,840 --> 00:22:21,240
a podobne, len druhý hop z 7 sa dostať k 6.

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

293
00:22:29,080 --> 00:22:35,330
Môžete sa vrátiť späť, a to pre všetky ostatné stromy, ktoré sme predtým diskutovali

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

295
00:22:37,480 --> 00:22:42,500
a zistíte, že výška všetkých týchto stromov je tiež 2.

296
00:22:42,500 --> 00:22:46,320
>> Dôvod, prečo sme hovorili o nariadené binárne stromy

297
00:22:46,320 --> 00:22:50,250
a prečo sú v pohode, je preto, že sa môžete preberať ne

298
00:22:50,250 --> 00:22:53,810
veľmi podobný spôsob vyhľadávania cez triedenom poli.

299
00:22:53,810 --> 00:22:58,720
To je miesto, kde budeme hovoriť o získanie že lepšie vyhľadávanie čas

300
00:22:58,720 --> 00:23:02,730
cez jednoduché prepojeného zoznamu.

301
00:23:02,730 --> 00:23:05,010
S prepojeného zoznamu - ak chcete nájsť konkrétny prvok -

302
00:23:05,010 --> 00:23:07,470
ste na najlepšie robiť nejaké lineárne hľadanie

303
00:23:07,470 --> 00:23:10,920
kde začať na začiatku zoznamu a hop jeden po jednom -

304
00:23:10,920 --> 00:23:12,620
jeden uzol jedným uzlom -

305
00:23:12,620 --> 00:23:16,060
celý zoznam, kým nenájdete, čo hľadáte.

306
00:23:16,060 --> 00:23:19,440
Vzhľadom k tomu, ak máte binárny strom, ktorý je uložený v tejto peknej formáte,

307
00:23:19,440 --> 00:23:23,300
môžete skutočne dostať viac binárneho vyhľadávania deje

308
00:23:23,300 --> 00:23:25,160
kde si rozdeľ a panuj

309
00:23:25,160 --> 00:23:29,490
a hľadanie cez zodpovedajúce polovici stromu na každom kroku.

310
00:23:29,490 --> 00:23:32,840
Poďme sa pozrieť, ako to funguje.

311
00:23:32,840 --> 00:23:38,850
>> Ak máme - opäť vracia do pôvodného stromu -

312
00:23:38,850 --> 00:23:46,710
začneme v 7, my máme 3 vľavo, 9 na pravej strane,

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

314
00:23:51,740 --> 00:24:01,880
Ak chceme vyhľadať číslo 6 v tomto stromu, mali by sme začať u koreňa.

315
00:24:01,880 --> 00:24:08,910
Radi by sme tieto hodnoty sme hľadali, povedzme 6,

316
00:24:08,910 --> 00:24:12,320
na hodnotu uloženú v uzle, ktorý sme teraz pri pohľade na, 7,

317
00:24:12,320 --> 00:24:21,200
zistí, že 6 je naozaj menej ako 7, a tak sme si presunúť doľava.

318
00:24:21,200 --> 00:24:25,530
Ak je hodnota 6 bol vyšší ako 7, by sme sa namiesto toho sa pohyboval napravo.

319
00:24:25,530 --> 00:24:29,770
Vzhľadom k tomu, vieme, že - vzhľadom k štruktúre našej objednaného binárneho stromu -

320
00:24:29,770 --> 00:24:33,910
všetky hodnoty menšie ako 7 sa bude uložený vľavo 7,

321
00:24:33,910 --> 00:24:40,520
nie je potrebné, aby neobťažoval pohľade cez pravej strane stromu.

322
00:24:40,520 --> 00:24:43,780
Akonáhle sme sa presunúť doľava a my sme teraz v uzle obsahujúce 3,

323
00:24:43,780 --> 00:24:48,110
môžeme urobiť rovnakú porovnaniu zase tam, kde sme porovnať 3 a 6.

324
00:24:48,110 --> 00:24:52,430
A my zistíme, že zatiaľ čo 6 - hodnota, ktorú hľadáte - je väčší ako 3,

325
00:24:52,430 --> 00:24:58,580
môžeme ísť na pravej strane uzla, ktorá obsahuje 3.

326
00:24:58,580 --> 00:25:02,670
Nie je ľavá strana tu, takže sme mohli ignorovať, že.

327
00:25:02,670 --> 00:25:06,510
Ale my len vieme, že preto, že sa pozeráme na strom sám,

328
00:25:06,510 --> 00:25:08,660
a my môžeme vidieť, že strom nemá žiadne deti.

329
00:25:08,660 --> 00:25:13,640
>> Je tiež celkom ľahké sa pozrieť do 6 v tejto vetve, ak robíme to sami ako ľudia,

330
00:25:13,640 --> 00:25:16,890
ale poďme sledovať tento proces mechanicky ako počítač urobí

331
00:25:16,890 --> 00:25:18,620
naozaj pochopiť algoritmus.

332
00:25:18,620 --> 00:25:26,200
V tomto bode, sme teraz pozrieme na uzle, ktorý obsahuje 6,

333
00:25:26,200 --> 00:25:29,180
a hľadáme pre hodnotu 6,

334
00:25:29,180 --> 00:25:31,740
tak, naozaj, sme našli zodpovedajúce uzol.

335
00:25:31,740 --> 00:25:35,070
Našli sme hodnotu 6 v našom stromu, a môžeme zastaviť naše vyhľadávanie.

336
00:25:35,070 --> 00:25:37,330
V tomto bode, v závislosti na tom, čo sa deje,

337
00:25:37,330 --> 00:25:41,870
môžeme povedať, že áno, sme našli hodnotu 6, to je v našej stromu.

338
00:25:41,870 --> 00:25:47,640
Alebo, ak plánujeme vložiť uzol, alebo robiť niečo, môžeme robiť, že v tomto bode.

339
00:25:47,640 --> 00:25:53,010
>> Poďme urobiť pár ďalších vyhľadávania, len aby videl, ako to funguje.

340
00:25:53,010 --> 00:25:59,390
Poďme sa pozrieť na to, čo sa stane, keď sme boli vyskúšať a pozrieť sa na hodnotu 10.

341
00:25:59,390 --> 00:26:02,970
Ak by sme sa pozreli do hodnoty 10, my by sme začali pri koreni.

342
00:26:02,970 --> 00:26:07,070
Mali by sme vidieť, že 10 je väčšie ako 7, tak by sme presunie doprava.

343
00:26:07,070 --> 00:26:13,640
Mali by sme dostať na 9 a porovnajte 9 do 10 a uvidíte, že 9 je naozaj menej ako 10.

344
00:26:13,640 --> 00:26:16,210
Takže znova, tak sa snažíme presunúť doprava.

345
00:26:16,210 --> 00:26:20,350
Ale v tomto bode, mali by sme si všimnúť, že sme na null uzla.

346
00:26:20,350 --> 00:26:23,080
Tam nič nie je. Nie je nič, kde by mala byť 10.

347
00:26:23,080 --> 00:26:29,360
Toto je miesto, kde sa môže hlásiť zlyhanie -, že skutočne č 10 vo stromu.

348
00:26:29,360 --> 00:26:35,420
A konečne, poďme prejsť prípade sa snažíme vyhľadať 1 do stromu.

349
00:26:35,420 --> 00:26:38,790
To je podobné tomu, čo sa stane, keď sa pozrieme do 10, s výnimkou namiesto toho, aby práva,

350
00:26:38,790 --> 00:26:41,260
sme ísť doľava.

351
00:26:41,260 --> 00:26:46,170
Začneme na 7 a vidieť, že 1 je menšie ako 7, tak sa pohybovať doľava.

352
00:26:46,170 --> 00:26:51,750
Dostávame sa 3 a uvidíte, že 1 je menší ako 3, takže opäť sa snažíme presunúť doľava.

353
00:26:51,750 --> 00:26:59,080
V tomto bode máme null uzol, takže opäť môžeme hlásiť poruchu.

354
00:26:59,080 --> 00:27:10,260
>> Ak sa chcete dozvedieť viac o binárnych stromoch,

355
00:27:10,260 --> 00:27:14,420
existuje celá partia veselých malých problémov, ktoré môžete robiť s nimi.

356
00:27:14,420 --> 00:27:19,450
Navrhujem cvičiť kresbu z týchto diagramov jeden po druhom

357
00:27:19,450 --> 00:27:21,910
a po cez všetky jednotlivé kroky,

358
00:27:21,910 --> 00:27:25,060
pretože to príde super-praktický

359
00:27:25,060 --> 00:27:27,480
nielen, keď robíte kódovanie Huffmanova problém sadu

360
00:27:27,480 --> 00:27:29,390
ale aj v budúcich kurzov -

361
00:27:29,390 --> 00:27:32,220
len naučiť, ako čerpať z týchto dátových štruktúr a myslím, že cez problémy

362
00:27:32,220 --> 00:27:38,000
s pero a papier alebo, v tomto prípade, iPad a pero.

363
00:27:38,000 --> 00:27:41,000
>> V tomto bode hoci, budeme sa pohybovať na urobiť nejaké kódovanie praxi

364
00:27:41,000 --> 00:27:44,870
a skutočne si hrať s týmito binárnymi stromami a vidieť.

365
00:27:44,870 --> 00:27:52,150
Chystám sa prejsť späť na mojom počítači.

366
00:27:52,150 --> 00:27:58,480
Pre túto časť sekcie, namiesto použitia CS50 Spustiť alebo CS50 priestory,

367
00:27:58,480 --> 00:28:01,500
Budem používať spotrebič.

368
00:28:01,500 --> 00:28:04,950
>> Po spoločne so špecifikáciou problému Set,

369
00:28:04,950 --> 00:28:07,740
Vidím, že mám otvoriť spotrebič,

370
00:28:07,740 --> 00:28:11,020
ísť do môjho priečinka Dropbox, vytvorte priečinok s názvom § 7,

371
00:28:11,020 --> 00:28:15,730
a potom vytvoriť súbor s názvom binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Ideme na to. Mám spotrebič už otvorený.

373
00:28:22,050 --> 00:28:25,910
Idem vytiahnuť terminál.

374
00:28:25,910 --> 00:28:38,250
Chystám sa ísť do priečinka Dropbox, aby sa adresár s názvom section7,

375
00:28:38,250 --> 00:28:42,230
a vidieť, že je to úplne prázdny.

376
00:28:42,230 --> 00:28:48,860
Teraz idem otvoriť binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Dobre. Ideme - prázdny súbor.

378
00:28:51,750 --> 00:28:54,330
>> Vráťme sa špecifikácií.

379
00:28:54,330 --> 00:28:59,850
Špecifikácie žiada vytvorenie novej definícii typu

380
00:28:59,850 --> 00:29:03,080
pre binárne uzol stromu obsahuje int hodnoty -

381
00:29:03,080 --> 00:29:07,110
rovnako ako hodnoty, ktoré sme vypracovali v našej diagramov pred.

382
00:29:07,110 --> 00:29:11,740
Budeme používať tento štandardný text typedef, že sme urobili tu

383
00:29:11,740 --> 00:29:14,420
že by ste mali poznať z problémových Set 5 -

384
00:29:14,420 --> 00:29:19,190
ak ste hash tabuľky spôsob dobývania pravopisu programu.

385
00:29:19,190 --> 00:29:22,540
Mali by ste tiež uznať z minulého týždňa oddielu

386
00:29:22,540 --> 00:29:23,890
kde sme o tom hovorili v súvislosti zoznamoch.

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

388
00:29:27,870 --> 00:29:34,430
a my sme rovnako Táto štruktúra uzla tento názov struct uzol si vopred

389
00:29:34,430 --> 00:29:39,350
takže potom môžeme odkazovať sa na to, pretože budeme chcieť mať ukazovatele struct uzol

390
00:29:39,350 --> 00:29:45,740
ako súčasť našej struct, ale my sme potom obkľúčený to -

391
00:29:45,740 --> 00:29:47,700
alebo skôr, uzavretý toto - v typedef

392
00:29:47,700 --> 00:29:54,600
tak, že neskôr v kóde, možno odkázať na tento struct len ​​ako uzol namiesto struct uzol.

393
00:29:54,600 --> 00:30:03,120
>> To bude veľmi podobný single prepojené definície zoznamu, ktoré sme videli minulý týždeň.

394
00:30:03,120 --> 00:30:20,070
Ak to chcete, nech to jednoducho začať písať sa na štandardizovaný.

395
00:30:20,070 --> 00:30:23,840
Vieme, že musíme mať celočíselnú hodnotu,

396
00:30:23,840 --> 00:30:32,170
tak dáme do int hodnoty, a potom namiesto toho, aby len jeden ukazovateľ na ďalší prvok -

397
00:30:32,170 --> 00:30:33,970
ako sme to urobili s single viazaných zoznamov -

398
00:30:33,970 --> 00:30:38,110
budeme mať ľavej a pravej podriadené ukazovatele.

399
00:30:38,110 --> 00:30:42,880
To je docela jednoduchá tiež - struct node * ľavá dieťa;

400
00:30:42,880 --> 00:30:51,190
a struct uzol * P dieťa;. Cool.

401
00:30:51,190 --> 00:30:54,740
To vyzerá ako celkom dobrý začiatok.

402
00:30:54,740 --> 00:30:58,530
Vráťme sa špecifikácií.

403
00:30:58,530 --> 00:31:05,030
>> Teraz musíme deklarovať globálne premenné uzla * pre koreň stromu.

404
00:31:05,030 --> 00:31:10,590
Budeme robiť to globálne, rovnako ako sme urobili prvý ukazovateľ v našom prepojenom zozname aj globálne.

405
00:31:10,590 --> 00:31:12,690
To bolo tak, že vo funkciách, ktoré sme napísať

406
00:31:12,690 --> 00:31:16,180
nemáme držať prechádzanie okolo tohto koreňa -

407
00:31:16,180 --> 00:31:19,620
keď budeme vidieť, že ak si chcete napísať tieto funkcie rekurzívne,

408
00:31:19,620 --> 00:31:22,830
to by mohlo byť lepšie ani prejsť okolo ako globálny na prvom mieste

409
00:31:22,830 --> 00:31:28,090
a namiesto toho inicializovať ju lokálne vo vašom hlavnom funkcie.

410
00:31:28,090 --> 00:31:31,960
Ale urobíme to globálne začať.

411
00:31:31,960 --> 00:31:39,920
Opäť, dáme pár miest, a budem deklarovať uzla * koreň.

412
00:31:39,920 --> 00:31:46,770
Len aby sa ubezpečil, že nemám nechať tento inicializovaná, budem ju nastaviť rovná null.

413
00:31:46,770 --> 00:31:52,210
Teraz, v hlavnej funkcii - ktoré budeme písať naozaj rýchlo priamo tu -

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 ja začnem vyhlásením svoje ArGV pole ako const len ​​preto, že viem,

416
00:32:10,640 --> 00:32:14,550
že tieto argumenty sú argumenty, ktoré som asi nechcú meniť.

417
00:32:14,550 --> 00:32:18,390
Ak chcem zmeniť som im mala byť pravdepodobne robiť ich kópie.

418
00:32:18,390 --> 00:32:21,740
Uvidíte to veľa v kóde.

419
00:32:21,740 --> 00:32:25,440
To je v poriadku tak ako tak. Je to v poriadku nechať to ako - vynechať const, ak chcete.

420
00:32:25,440 --> 00:32:28,630
Aj typicky dať do len preto, že som si pripomínam

421
00:32:28,630 --> 00:32:33,650
 že som asi nechcem meniť tieto argumenty.

422
00:32:33,650 --> 00:32:39,240
>> Ako vždy, budem zahrnúť tento návratový 0 riadok na konci hlavnej.

423
00:32:39,240 --> 00:32:45,730
Tu budem inicializovať svoj koreňový uzol.

424
00:32:45,730 --> 00:32:48,900
Ako to stojí teraz, mám ukazovateľ, ktorý je nastavený na hodnotu null,

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

426
00:32:52,970 --> 00:32:57,480
Aby sa skutočne začať stavať uzol,

427
00:32:57,480 --> 00:32:59,250
Prvýkrát som potrebné alokovať pamäť pre neho.

428
00:32:59,250 --> 00:33:05,910
Ja budem robiť, že tým, že pamäť na halde pomocou malloc.

429
00:33:05,910 --> 00:33:10,660
Idem nastaviť koreň rovnajúcu sa výsledku malloc,

430
00:33:10,660 --> 00:33:19,550
a budem používať sizeof operátor vypočítať veľkosť uzla.

431
00:33:19,550 --> 00:33:24,990
Dôvod, prečo som použiť sizeof uzol na rozdiel od, povedzme,

432
00:33:24,990 --> 00:33:37,020
niečo také - malloc (4 + 4 +4) alebo malloc 12 -

433
00:33:37,020 --> 00:33:40,820
Je tomu tak preto chcem, aby môj kód, aby bolo kompatibilné, ako je to možné.

434
00:33:40,820 --> 00:33:44,540
Chcem byť schopný urobiť také. C súbor, skompilovať na zariadenia,

435
00:33:44,540 --> 00:33:48,820
a potom skompilovať na mojom 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
alebo na úplne inú architektúru -

437
00:33:52,040 --> 00:33:54,640
a chcem to všetko fungovať rovnako.

438
00:33:54,640 --> 00:33:59,510
>> Ak robím predpoklady o veľkosti premenných -

439
00:33:59,510 --> 00:34:02,070
veľkosť int alebo veľkosť ukazovateľ -

440
00:34:02,070 --> 00:34:06,070
potom som tiež robiť predpoklady o druhy architektúr

441
00:34:06,070 --> 00:34:10,440
na ktoré môj kód je možné úspešne skompilovať pri spustení.

442
00:34:10,440 --> 00:34:15,030
Vždy používajte sizeof na rozdiel od ručne súčet struct poľa.

443
00:34:15,030 --> 00:34:20,500
Ďalším dôvodom je to, že môže byť aj padding, že kompilátor dáva do struct.

444
00:34:20,500 --> 00:34:26,570
I len súčet jednotlivých polí nie je niečo, čo zvyčajne chcú urobiť,

445
00:34:26,570 --> 00:34:30,340
tak, odstráňte tento riadok.

446
00:34:30,340 --> 00:34:33,090
Teraz, naozaj inicializovať koreňový uzol,

447
00:34:33,090 --> 00:34:36,489
Budem musieť pripojiť hodnôt pre každú z jeho rôznych odborov.

448
00:34:36,489 --> 00:34:41,400
Napríklad pre hodnotu viem chcem inicializovať až 7,

449
00:34:41,400 --> 00:34:46,920
a teraz idem nastaviť doľava dieťa budú mať hodnotu null

450
00:34:46,920 --> 00:34:55,820
a právo dieťa tiež byť null. Výborne!

451
00:34:55,820 --> 00:35:02,670
Urobili sme, že časť špec.

452
00:35:02,670 --> 00:35:07,390
>> Špecifikácie sa v dolnej časti stránky 3 sa ma pýta, ak chcete vytvoriť ďalšie tri uzly -

453
00:35:07,390 --> 00:35:10,600
z ktorých jedna obsahuje 3, jeden obsahujúci 6, a jeden s 9 -

454
00:35:10,600 --> 00:35:14,210
a potom prepojte je tak, že vyzerá presne ako náš stromovom diagrame

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

456
00:35:17,120 --> 00:35:20,450
Urobme to celkom rýchlo sem.

457
00:35:20,450 --> 00:35:26,270
Uvidíte naozaj rýchlo, že som začnem písať veľa duplicitných kódu.

458
00:35:26,270 --> 00:35:32,100
Idem vytvoriť uzla * a budem to nazývať tri.

459
00:35:32,100 --> 00:35:36,000
Idem nastaviť to rovnaké malloc (sizeof (uzol)).

460
00:35:36,000 --> 00:35:41,070
Idem nastaviť tri-> hodnota = 3.

461
00:35:41,070 --> 00:35:54,780
Tri -> left_child = NULL; tri -> P _child = NULL; rovnako.

462
00:35:54,780 --> 00:36:01,150
To vyzerá dosť podobne ako inicializáciu koreň, a to je presne to, čo

463
00:36:01,150 --> 00:36:05,760
Budem musieť robiť, keď začnem inicializáciu 6 a 9 rovnako.

464
00:36:05,760 --> 00:36:20,720
Urobím to naozaj rýchlo sem - vlastne, ja budem robiť trochu kopírovať a vložiť,

465
00:36:20,720 --> 00:36:46,140
a uistite sa, že som - v poriadku.

466
00:36:46,470 --> 00:37:09,900
 Teraz som dostal to kopírovať a môžem ísť ďalej a nastaviť rovná 6.

467
00:37:09,900 --> 00:37:14,670
Môžete vidieť, že to trvá chvíľu a nie je super-efektívne.

468
00:37:14,670 --> 00:37:22,610
V len trochu, budeme napísať funkciu, ktorá bude robiť to pre nás.

469
00:37:22,610 --> 00:37:32,890
Chcem nahradiť to s 9, nahradiť to s 6.

470
00:37:32,890 --> 00:37:37,360
>> Teraz máme všetky naše uzlov vytvorená a inicializovaná.

471
00:37:37,360 --> 00:37:41,200
Máme naše koreň položí rovné 7, alebo obsahujúce hodnotu 7,

472
00:37:41,200 --> 00:37:46,510
náš uzol obsahujúci 3, naše uzol obsahujúci 6, a naše uzol obsahujúci 9.

473
00:37:46,510 --> 00:37:50,390
V tomto bode, všetko, čo musíte urobiť, je drôt všetko až.

474
00:37:50,390 --> 00:37:53,020
Dôvod, prečo som inicializácii všetkých ukazovateľov na hodnotu null, je len preto, že som sa uistite, že

475
00:37:53,020 --> 00:37:56,260
Nemám žiadne neinicializovaný ukazovatele v tú náhodou.

476
00:37:56,260 --> 00:38:02,290
A tiež, pretože v tomto bode, som len skutočne pripojiť uzly navzájom -

477
00:38:02,290 --> 00:38:04,750
tým, že oni sú vlastne spojené s - nemám prejsť a urobiť

478
00:38:04,750 --> 00:38:08,240
či sú všetky nuly sú tam na príslušných miestach.

479
00:38:08,240 --> 00:38:15,630
>> Od koreňa, ja viem, že koreň ľavá dieťa 3.

480
00:38:15,630 --> 00:38:21,250
Ja viem, že koreň právo dieťa je 9.

481
00:38:21,250 --> 00:38:24,880
Potom, jediný ďalšie dieťa, ktoré som nechal robiť starosti

482
00:38:24,880 --> 00:38:39,080
je 3 právo dieťa, ktoré je 6.

483
00:38:39,080 --> 00:38:44,670
V tomto okamihu, to všetko vyzerá celkom dobre.

484
00:38:44,670 --> 00:38:54,210
Budeme odstrániť niektoré z týchto liniek.

485
00:38:54,210 --> 00:38:59,540
Teraz všetko vyzerá celkom dobre.

486
00:38:59,540 --> 00:39:04,240
Vráťme sa k nášmu špecifikácie a vidieť to, čo máme robiť ďalej.

487
00:39:04,240 --> 00:39:07,610
>> V tomto bode, musíme písať volané funkcie "obsahuje"

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

489
00:39:14,150 --> 00:39:17,060
A táto obsahuje funkcie bude vracať hodnotu true

490
00:39:17,060 --> 00:39:21,200
 ak strom poukázal na našej celosvetovej koreňovej premenné

491
00:39:21,200 --> 00:39:26,950
 obsahuje hodnotu odovzdaný do funkcie a false inak.

492
00:39:26,950 --> 00:39:29,000
Poďme ďalej a robiť, že.

493
00:39:29,000 --> 00:39:35,380
To bude presne ako pri vyhľadávaní, že sme sa po ruke na iPad len trochu pred.

494
00:39:35,380 --> 00:39:40,130
Poďme približovanie sa trochu a stlačte posúvacie tlačidlo nahor.

495
00:39:40,130 --> 00:39:43,130
Budeme dať túto funkciu priamo nad našou hlavnou funkciou

496
00:39:43,130 --> 00:39:48,990
takže nemáme robiť nejaký druh prototypovania.

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 ideme. Tu je náš štandardný text vyhlásenia.

499
00:40:00,330 --> 00:40:02,900
Len aby sa ubezpečil, že to bude zostavovať,

500
00:40:02,900 --> 00:40:06,820
Chystám sa ísť dopredu a len nastaviť rovné vrátiť false.

501
00:40:06,820 --> 00:40:09,980
Práve teraz táto funkcia jednoducho nebude robiť nič a vždy hlási, že

502
00:40:09,980 --> 00:40:14,010
hodnota, ktorá hľadáme, nie je v strome.

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

504
00:40:16,280 --> 00:40:19,600
pretože sme napísali veľa kódu a my sme sa ani nesnažili vyskúšanie - doteraz

505
00:40:19,600 --> 00:40:22,590
aby sa ubezpečil, že to všetko kompiluje.

506
00:40:22,590 --> 00:40:27,460
Existuje pár vecí, ktoré musíme urobiť, aby sa ubezpečil, že to bude skutočne kompilovať.

507
00:40:27,460 --> 00:40:33,530
Po prvé, či sme boli s použitím akýchkoľvek funkcií v žiadnej knižnice, ktoré sme doteraz neboli zahrnuté.

508
00:40:33,530 --> 00:40:37,940
Funkcie, ktoré sme používali doteraz, sú malloc,

509
00:40:37,940 --> 00:40:43,310
a potom sme tiež používali tento typ - tento neštandardný typ zvaný "bool '-

510
00:40:43,310 --> 00:40:45,750
ktorý je súčasťou štandardnej bool hlavičke súboru.

511
00:40:45,750 --> 00:40:53,250
Určite chceme, aby zahŕňala štandardné bool.h pre typu bool,

512
00:40:53,250 --> 00:40:59,230
a tiež chceme, aby # include štandardné lib.h pre štandardné knižnice

513
00:40:59,230 --> 00:41:03,530
ktoré zahŕňajú malloc, a bezplatné, a všetky, ktoré.

514
00:41:03,530 --> 00:41:08,660
Takže, oddialiť, ideme ukončiť.

515
00:41:08,660 --> 00:41:14,190
Poďme skúsiť a uistite sa, že to v skutočnosti robil kompilácie.

516
00:41:14,190 --> 00:41:18,150
Vidíme, že to robí, tak sme na správnej ceste.

517
00:41:18,150 --> 00:41:22,990
>> Poďme otvoriť binary_tree.c znova.

518
00:41:22,990 --> 00:41:34,530
Zhŕňa. Poďme dole a uistite sa, že vložíme niekoľko hovorov do nášho obsahuje funkcie -

519
00:41:34,530 --> 00:41:40,130
len aby sa ubezpečil, že je všetko v poriadku.

520
00:41:40,130 --> 00:41:43,170
Napríklad, keď sme robili nejaké vyhľadávanie v našom stromu skôr,

521
00:41:43,170 --> 00:41:48,500
sme sa snažili pozrieť do hodnoty 6, 10, a 1, a vedeli sme, že 6 je na strome,

522
00:41:48,500 --> 00:41:52,220
10 nie je v strome, a 1 nebol vo stromu buď.

523
00:41:52,220 --> 00:41:57,230
Poďme použiť tieto ukážkovej volanie ako spôsob, ako zistiť, či alebo nie

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

525
00:41:59,880 --> 00:42:05,210
Aby k tomu, že, budem používať printf funkcie,

526
00:42:05,210 --> 00:42:10,280
a budeme vytlačiť výsledok volania obsahuje.

527
00:42:10,280 --> 00:42:13,280
Idem dať v reťazci "obsahuje (% d) = pretože

528
00:42:13,280 --> 00:42:20,470
 budeme typom hodnoty, ktoré budeme hľadať,

529
00:42:20,470 --> 00:42:27,130
a =% s \ n ", a použiť ho ako náš formátovacom reťazci.

530
00:42:27,130 --> 00:42:30,720
Sme len tak vidieť - doslova vytlačiť na obrazovke -

531
00:42:30,720 --> 00:42:32,060
čo vyzerá ako volanie funkcie.

532
00:42:32,060 --> 00:42:33,580
To nie je v skutočnosti volanie funkcie.

533
00:42:33,580 --> 00:42:36,760
 To je len reťazec navrhnutý tak, aby vyzeral ako volanie funkcie.

534
00:42:36,760 --> 00:42:41,140
>> Teraz, budeme pripojiť hodnôt.

535
00:42:41,140 --> 00:42:43,580
Budeme sa snažiť obsahuje na 6,

536
00:42:43,580 --> 00:42:48,340
a potom to, čo budeme robiť, je tu použiť tento trojica operátor.

537
00:42:48,340 --> 00:42:56,340
Poďme sa pozrieť - obsahuje 6 - tak, teraz som obsahoval 6, a ak obsahuje 6 je pravda,

538
00:42:56,340 --> 00:43:01,850
reťazec, ktorý budeme posielať na% s formátu charakteru

539
00:43:01,850 --> 00:43:04,850
bude reťazec "true".

540
00:43:04,850 --> 00:43:07,690
Poďme prejdite trochu.

541
00:43:07,690 --> 00:43:16,210
Inak, chceme poslať reťazec "false", ak obsahuje 6 vráti False.

542
00:43:16,210 --> 00:43:19,730
To je malý praštěná vyzerajúce, ale podľa mňa by som mohol tiež ilustrujú

543
00:43:19,730 --> 00:43:23,780
čo ternárnu operátor vyzerá, pretože sme ho ešte nevideli na chvíľu.

544
00:43:23,780 --> 00:43:27,670
To bude pekný, šikovný spôsob, ako zistiť, či naše obsahuje funkcie pracuje.

545
00:43:27,670 --> 00:43:30,040
Idem listovať nad vľavo,

546
00:43:30,040 --> 00:43:39,900
a budem kopírovať a vložiť tento riadok niekoľkokrát.

547
00:43:39,900 --> 00:43:44,910
To zmenilo niektoré z týchto hodnôt okolo,

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 mieste sme dostali peknú obsahuje funkcie.

550
00:44:02,480 --> 00:44:06,080
Máme nejaké testy, a uvidíme, či to všetko funguje.

551
00:44:06,080 --> 00:44:08,120
V tomto bode sme napísali niektoré ďalšie kód.

552
00:44:08,120 --> 00:44:13,160
Čas ukončenia, a uistite sa, že všetko, čo ešte kompiluje.

553
00:44:13,160 --> 00:44:20,360
Ukončite von, a teraz poďme skúsiť robiť binárne strom znova.

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

555
00:44:22,260 --> 00:44:26,930
a my sme dostali to výslovne prehlasuje knižnice funkciu printf.

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

557
00:44:39,350 --> 00:44:45,350
A s tým, všetko by malo zostaviť. Sme v pohode.

558
00:44:45,350 --> 00:44:50,420
Teraz sa poďme skúsiť spustiť binárny strom a uvidíme, čo sa stane.

559
00:44:50,420 --> 00:44:53,520
Tu sme,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
a vidíme, že, ako sme očakávali -

561
00:44:55,190 --> 00:44:56,910
pretože sme nie je implementovaná obsahuje ešte,

562
00:44:56,910 --> 00:44:59,800
alebo skôr, že sme len dať na oplátku falošné -

563
00:44:59,800 --> 00:45:03,300
vidíme, že je to len vracia false pre všetky z nich,

564
00:45:03,300 --> 00:45:06,180
tak to je všetko pracuje z väčšej časti veľmi dobre.

565
00:45:06,180 --> 00:45:11,860
>> Poďme späť a skutočne vykonávať obsahuje v tomto bode.

566
00:45:11,860 --> 00:45:17,490
Chystám sa posunúť dole, približovať, a -

567
00:45:17,490 --> 00:45:22,330
Pamätajte si, že algoritmus, ktorý sme použili je, že sme začali na koreňový uzol

568
00:45:22,330 --> 00:45:28,010
a potom v každom uzle, ktorý stretávame, robíme porovnanie,

569
00:45:28,010 --> 00:45:32,380
a na základe tohto porovnania sa buď presunúť na ľavú dieťaťa alebo pravej dieťa.

570
00:45:32,380 --> 00:45:39,670
To bude vyzerať veľmi podobne ako kód binárne vyhľadávanie, ktoré sme napísali skôr v termíne.

571
00:45:39,670 --> 00:45:47,810
Keď začneme, vieme, že chceme držať na aktuálne uzol

572
00:45:47,810 --> 00:45:54,050
že sa pozeráme na, a je aktuálne uzol sa bude inicializovaný na koreňový uzol.

573
00:45:54,050 --> 00:45:56,260
A teraz, budeme pokračovať cez strom,

574
00:45:56,260 --> 00:45:58,140
a pamätajte, že naše zastavenie podmienku -

575
00:45:58,140 --> 00:46:01,870
 keď my vlastne pracovali na príklade ručne -

576
00:46:01,870 --> 00:46:03,960
bolo, keď sme sa stretli s null uzol,

577
00:46:03,960 --> 00:46:05,480
nie, keď sme sa pozerali na null dieťa,

578
00:46:05,480 --> 00:46:09,620
ale keď sa v skutočnosti presunuté do uzla v strome

579
00:46:09,620 --> 00:46:12,640
a zistil, že sme na null uzla.

580
00:46:12,640 --> 00:46:20,720
Budeme opakovať, ako teraz nie je rovné null.

581
00:46:20,720 --> 00:46:22,920
A čo budeme robiť?

582
00:46:22,920 --> 00:46:31,610
Budeme testovať, či (teraz -> hodnota == hodnota),

583
00:46:31,610 --> 00:46:35,160
potom vieme, že sme skutočne našli uzol, ktorý sme hľadali.

584
00:46:35,160 --> 00:46:40,450
Tak tu sa môžeme vrátiť true.

585
00:46:40,450 --> 00:46:49,830
Inak, my chceme vidieť, či je hodnota nižšia ako hodnota.

586
00:46:49,830 --> 00:46:53,850
Ak je aktuálna uzol je hodnota nižšia ako hodnota, ktorú hľadáme,

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

588
00:46:57,280 --> 00:47:10,600
Takže, teraz = teraz -> right_child, a inak, budeme sa pohybovať doľava.

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

590
00:47:17,480 --> 00:47:22,830
>> Pravdepodobne ste rozpoznať slučku, ktorá vyzerá veľmi podobne, ako táto z

591
00:47:22,830 --> 00:47:27,580
binárne vyhľadávacie predtým v termíne, s výnimkou potom sme sa zaoberali s nízkou, strednou a vysokou.

592
00:47:27,580 --> 00:47:30,000
Tu, práve sme sa pozrieť na súčasnej hodnote,

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

594
00:47:31,930 --> 00:47:34,960
Poďme uistite sa, že tento kód funguje.

595
00:47:34,960 --> 00:47:42,780
Najprv sa uistite, že zostavuje. Vyzerá to, že to robí.

596
00:47:42,780 --> 00:47:47,920
Poďme skúste ju spustiť.

597
00:47:47,920 --> 00:47:50,160
A skutočne, že vypíše všetko, čo sme očakávali.

598
00:47:50,160 --> 00:47:54,320
To nájde 6 v strome, nenájde 10, pretože 10 nie je v strome,

599
00:47:54,320 --> 00:47:57,740
a nenájde 1 buď preto, že 1 to tiež nie je v strome.

600
00:47:57,740 --> 00:48:01,420
Vychytávky na stiahnutie.

601
00:48:01,420 --> 00:48:04,470
>> Dobre. Vráťme sa k nášmu špecifikácie a uvidíme, čo bude ďalej.

602
00:48:04,470 --> 00:48:07,990
Teraz sa chce pridať niektoré ďalšie uzly do nášho stromu.

603
00:48:07,990 --> 00:48:11,690
To chce pridať 5, 2, a 8, a uistite sa, že naše obsahuje kód

604
00:48:11,690 --> 00:48:13,570
stále funguje podľa očakávania.

605
00:48:13,570 --> 00:48:14,900
Poďme urobiť.

606
00:48:14,900 --> 00:48:19,430
V tomto bode, skôr než robiť, že nepríjemné kopírovať a vložiť znova,

607
00:48:19,430 --> 00:48:23,770
poďme napísať funkciu skutočne vytvoriť uzol.

608
00:48:23,770 --> 00:48:27,740
Ak by sme posunúť dole celú cestu k hlavnému, vidíme, že sme robili to

609
00:48:27,740 --> 00:48:31,210
veľmi podobný kód znovu a znovu zakaždým, keď chceme vytvoriť uzol.

610
00:48:31,210 --> 00:48:39,540
>> Poďme napísať funkciu, ktorá bude skutočne stavať na uzol pre nás a vrátiť ho.

611
00:48:39,540 --> 00:48:41,960
Idem volať to build_node.

612
00:48:41,960 --> 00:48:45,130
Chystám sa stavať uzol s konkrétnu hodnotu.

613
00:48:45,130 --> 00:48:51,040
Priblížte tu.

614
00:48:51,040 --> 00:48:56,600
Prvá vec, ktorú budem robiť, je skutočne vytvoriť priestor pre uzol na haldy.

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

616
00:49:05,400 --> 00:49:14,960
a potom je tu, Ja som jednoducho ísť k inicializácii všetkých oblastiach sa príslušné hodnoty.

617
00:49:14,960 --> 00:49:22,500
A na samom konci, vrátime naše uzol.

618
00:49:22,500 --> 00:49:28,690
Dobre. Jedna vec k poznámke je, že túto funkciu priamo tu

619
00:49:28,690 --> 00:49:34,320
bude vracať ukazovateľ do pamäte, ktorá bola haldy pridelená.

620
00:49:34,320 --> 00:49:38,880
Čo je pekné na tom je, že tento uzol teraz -

621
00:49:38,880 --> 00:49:42,420
musíme vyhlásiť ju na hromadu, pretože ak sme deklarovali ju na zásobník

622
00:49:42,420 --> 00:49:45,050
by sme neboli schopní to urobiť v tejto funkcii, ako je táto.

623
00:49:45,050 --> 00:49:47,690
Že pamäť by ísť mimo rozsah

624
00:49:47,690 --> 00:49:51,590
a bolo by neplatné, ak sme sa snažili pristupovať k nej neskôr.

625
00:49:51,590 --> 00:49:53,500
Pretože sme sa prehlasuje haldy pridelené pamäte,

626
00:49:53,500 --> 00:49:55,830
budeme musieť postarať o uvoľnenie neskôr

627
00:49:55,830 --> 00:49:58,530
pre náš program nie je úniku nejakú spomienku.

628
00:49:58,530 --> 00:50:01,270
Boli sme plaviť sa na to pre všetko ostatné v kóde

629
00:50:01,270 --> 00:50:02,880
Len pre jednoduchosť v tej dobe,

630
00:50:02,880 --> 00:50:05,610
ale ak ste niekedy napísať funkciu, ktorá vyzerá takto

631
00:50:05,610 --> 00:50:10,370
kde máš - niektorí hovoria, že malloc alebo realloc vnútri -

632
00:50:10,370 --> 00:50:14,330
Chcete, aby sa ubezpečil, že ste dal nejaký komentár sem, že hovorí,

633
00:50:14,330 --> 00:50:29,970
hej, vieš, vráti haldy pridelených uzol inicializovaný s odovzdaný v hodnote.

634
00:50:29,970 --> 00:50:33,600
A potom chcete, aby sa ubezpečil, že ste vložili do nejakej poznámky, ktoré hovorí, že

635
00:50:33,600 --> 00:50:41,720
volajúci musí uvoľniť vrátenej pamäte.

636
00:50:41,720 --> 00:50:45,450
Tak, keď sa niekto niekedy ide a používa túto funkciu,

637
00:50:45,450 --> 00:50:48,150
vedia, že všetko, čo sa vrátime z tejto funkcie

638
00:50:48,150 --> 00:50:50,870
v určitom okamihu bude musieť byť prepustený.

639
00:50:50,870 --> 00:50:53,940
>> Za predpokladu, že je všetko v poriadku a tu dobre,

640
00:50:53,940 --> 00:51:02,300
môžeme ísť dole do nášho kódu a nahradiť všetky tieto riadky tu

641
00:51:02,300 --> 00:51:05,410
s volaním našej funkcie uzla zostavenie.

642
00:51:05,410 --> 00:51:08,170
Poďme urobiť naozaj rýchlo.

643
00:51:08,170 --> 00:51:15,840
Jedna časť, ktorá nebudeme nahradiť je táto časť dole

644
00:51:15,840 --> 00:51:18,520
na dne, kde sa v skutočnosti drôt uzly poukázať na sebe,

645
00:51:18,520 --> 00:51:21,030
pretože to nemôžeme urobiť v našej funkcii.

646
00:51:21,030 --> 00:51:37,400
Ale poďme urobiť root = build_node (7); uzol * tri = build_node (3);

647
00:51:37,400 --> 00:51:47,980
uzol * Šesť = build_node (6); uzol * Deväť = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
A teraz, sme tiež chceli pridať uzly pre -

649
00:51:52,590 --> 00:52:03,530
Uzol * päť = build_node (5); uzol * osem = build_node (8);

650
00:52:03,530 --> 00:52:09,760
a čo bola tá druhá uzol? Poďme sa pozrieť, tu. Chceli sme tiež pridať 2 -

651
00:52:09,760 --> 00:52:20,280
Uzol * dve = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Dobre. V tomto bode, vieme, že sme dostali 7, 3, 9, a 6

653
00:52:26,850 --> 00:52:30,320
všetky zapojený správne, ale čo o 5, 8, a 2?

654
00:52:30,320 --> 00:52:33,550
Aby bolo všetko v správnom poradí,

655
00:52:33,550 --> 00:52:39,230
vieme, že tri právo dieťa je 6.

656
00:52:39,230 --> 00:52:40,890
Takže, ak budeme pridať 5,

657
00:52:40,890 --> 00:52:46,670
s 5 tiež patrí do pravej strane stromu, z ktorých 3 je koreňom,

658
00:52:46,670 --> 00:52:50,440
tak 5 patrí ako ľavé dieťa 6.

659
00:52:50,440 --> 00:52:58,650
Môžeme to urobiť tým, že hovorí, šesť -> left_child = päť;

660
00:52:58,650 --> 00:53:10,790
a potom 8 patria ako ľavý dieťa 9, tak deväť -> left_child = osem;

661
00:53:10,790 --> 00:53:22,190
a potom 2 je ľavý dieťa 3, takže môžeme urobiť, že sem - teba -> left_child = dva;.

662
00:53:22,190 --> 00:53:27,730
Ak ste tak celkom sledovať spolu s tým, navrhujem, aby ste nakresliť to sami.

663
00:53:27,730 --> 00:53:35,660
>> Dobre. Poďme zachrániť to. Poďme von a uistite sa, že zostavuje,

664
00:53:35,660 --> 00:53:40,760
a potom môžeme pridať v našom obsahuje volanie.

665
00:53:40,760 --> 00:53:44,120
Vyzerá ako všetko, čo ešte kompiluje.

666
00:53:44,120 --> 00:53:51,790
Poďme a pridať v niektorých obsahuje volanie.

667
00:53:51,790 --> 00:53:59,640
Opäť, budem robiť trochu kopírovanie a vkladanie.

668
00:53:59,640 --> 00:54:15,860
Teraz poďme hľadať 5, 8, a 2. Dobre.

669
00:54:15,860 --> 00:54:28,330
Poďme sa uistite, že to všetko vyzerá dobre ešte. Výborne! Uložiť a ukončite.

670
00:54:28,330 --> 00:54:33,220
Teraz poďme urobiť, kompilovať, a teraz poďme bežať.

671
00:54:33,220 --> 00:54:37,540
Z výsledkov, vyzerá to, že všetko funguje len pekné a dobre.

672
00:54:37,540 --> 00:54:41,780
Výborne! Takže teraz máme naše obsahuje funkcie písaný.

673
00:54:41,780 --> 00:54:46,160
Poďme ďalej a začať pracovať na tom, ako vložiť uzlov do stromu

674
00:54:46,160 --> 00:54:50,000
pretože, ako to robíme teraz, veci nie sú moc pekná.

675
00:54:50,000 --> 00:54:52,280
>> Ak sa vrátime do špecifikácie,

676
00:54:52,280 --> 00:55:00,540
to nás žiada, aby sme napísať funkciu nazvanú vloženia - opäť vracia bool

677
00:55:00,540 --> 00:55:04,400
o otázku, či alebo nie by sme mohli skutočne vložiť uzol do stromu -

678
00:55:04,400 --> 00:55:07,710
a potom je hodnota vložiť do stromu je špecifikovaná ako

679
00:55:07,710 --> 00:55:11,060
jediným argumentom našej vlož funkciu.

680
00:55:11,060 --> 00:55:18,180
Budeme vráti true, ak by sme mohli skutočne vložiť uzla obsahujúce hodnotu do stromu,

681
00:55:18,180 --> 00:55:20,930
, Čo znamená, že sa jeden, mal dostatok pamäte,

682
00:55:20,930 --> 00:55:24,840
a potom dva, že uzol nebol už existujú vo stromu od -

683
00:55:24,840 --> 00:55:32,170
Pamätajte si, že sa nebudeme mať duplicitné hodnoty v strome, len aby to jednoduché.

684
00:55:32,170 --> 00:55:35,590
Dobre. Späť do kódu.

685
00:55:35,590 --> 00:55:44,240
Otvorte ju. Zväčšiť trochu, posuňte zobrazenie dolu.

686
00:55:44,240 --> 00:55:47,220
Poďme dať vložte funkciu priamo nad obsahuje.

687
00:55:47,220 --> 00:55:56,360
Opäť, to bude nazývaný bool vložka (int value).

688
00:55:56,360 --> 00:56:01,840
Dajte mu trochu viac priestoru, a potom, ako predvolené,

689
00:56:01,840 --> 00:56:08,870
poďme dať na oplátku falošné na samom konci.

690
00:56:08,870 --> 00:56:22,620
Teraz sa na dne, poďme do toho a namiesto ručne budovanie uzly

691
00:56:22,620 --> 00:56:27,900
v hlavnom sami a zapojenie je až do bodu k sebe, ako to robíme,

692
00:56:27,900 --> 00:56:30,600
budeme spoliehať na naše vlož funkciu k tomu, že.

693
00:56:30,600 --> 00:56:35,510
Nebudeme sa spoliehať na našom vlož funkciu postaviť celý strom od nuly ešte nie,

694
00:56:35,510 --> 00:56:39,970
ale budeme sa zbaviť týchto riadkov - Dáme komentár, tieto riadky -

695
00:56:39,970 --> 00:56:43,430
ktoré budú vychádzať uzly 5, 8, a 2.

696
00:56:43,430 --> 00:56:55,740
A namiesto toho, budeme vložiť volania do nášho vlož funkciu

697
00:56:55,740 --> 00:57:01,280
aby sa ubezpečil, že skutočne funguje.

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

699
00:57:05,840 --> 00:57:09,300
>> Teraz sme komentármi týchto riadkov.

700
00:57:09,300 --> 00:57:13,700
Máme len 7, 3, 9, a 6 v našom stromu v tomto bode.

701
00:57:13,700 --> 00:57:18,870
Uistite sa, že je to všetko funguje,

702
00:57:18,870 --> 00:57:25,050
môžeme oddialiť, aby naše binárne strom,

703
00:57:25,050 --> 00:57:30,750
spustite ho, a my môžeme vidieť, že obsahuje je teraz nám hovorí, že sme úplne pravdu -

704
00:57:30,750 --> 00:57:33,110
5, 8, a 2 sú už v strome.

705
00:57:33,110 --> 00:57:37,960
Choďte späť do kódu,

706
00:57:37,960 --> 00:57:41,070
a ako sa budeme vložiť?

707
00:57:41,070 --> 00:57:46,290
Spomeňte si, čo sme robili, keď sme boli vlastne vloženie 5, 8, a 2 skôr.

708
00:57:46,290 --> 00:57:50,100
Hrali sme túto hru plienky, kde sme začali pri koreni,

709
00:57:50,100 --> 00:57:52,780
šiel stromu jeden po jeden po druhom

710
00:57:52,780 --> 00:57:54,980
kým sme nenašli zodpovedajúce medzeru,

711
00:57:54,980 --> 00:57:57,570
a potom sa zapojený v uzle na príslušné miesto.

712
00:57:57,570 --> 00:57:59,480
Chystáme sa urobiť to isté.

713
00:57:59,480 --> 00:58:04,070
To je v podstate ako písanie kódu, ktorý sme použili v obsahuje funkcie

714
00:58:04,070 --> 00:58:05,910
nájsť miesto, kde má byť uzol,

715
00:58:05,910 --> 00:58:10,560
a potom sme len tak vložiť uzol tu.

716
00:58:10,560 --> 00:58:17,000
Poďme začať robiť, že.

717
00:58:17,000 --> 00:58:24,200
>> Takže máme uzol * teraz = root, budeme len tak nasledovať obsahuje kód

718
00:58:24,200 --> 00:58:26,850
kým nezistíme, že to nie je úplne pracovať pre nás.

719
00:58:26,850 --> 00:58:32,390
Budeme prechádzať stromu, zatiaľ čo aktuálny prvok nie je null,

720
00:58:32,390 --> 00:58:45,280
a ak zistíme, že teraz je hodnota rovná hodnote, že sa snažíme vložiť -

721
00:58:45,280 --> 00:58:49,600
dobre, to je jeden z prípadov, v ktorých sme nemohli skutočne vložiť uzol

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

723
00:58:52,730 --> 00:58:59,010
Tu sme vlastne bude vracať false.

724
00:58:59,010 --> 00:59:08,440
Teraz, inak ak CUR je hodnota nižšia ako hodnota,

725
00:59:08,440 --> 00:59:10,930
Teraz vieme, že sa presunieme do pravej

726
00:59:10,930 --> 00:59:17,190
 pretože hodnota patrí v pravej polovici cur stromu.

727
00:59:17,190 --> 00:59:30,110
Inak budeme pohybovať doľava.

728
00:59:30,110 --> 00:59:37,980
To je v podstate naša obsahuje funkcie priamo tam.

729
00:59:37,980 --> 00:59:41,820
>> V tomto bode, akonáhle sme dokončili tento while,

730
00:59:41,820 --> 00:59:47,350
náš teraz ukazovateľ sa bude ukazovať na nulu

731
00:59:47,350 --> 00:59:51,540
v prípade, že funkcia nie je už vrátila.

732
00:59:51,540 --> 00:59:58,710
Máme preto mať CUR na mieste, kde chceme vložiť nový uzol.

733
00:59:58,710 --> 01:00:05,210
Čo je ešte potrebné urobiť, je skutočne stavať nový uzol,

734
01:00:05,210 --> 01:00:08,480
ktoré môžeme urobiť celkom ľahko.

735
01:00:08,480 --> 01:00:14,930
Môžeme použiť naše super-praktický zostavenie uzla funkciu,

736
01:00:14,930 --> 01:00:17,210
a niečo, čo sme neurobili skôr -

737
01:00:17,210 --> 01:00:21,400
sme tak nejako brali za samozrejmosť, ale teraz budeme robiť, len aby sa ubezpečil -

738
01:00:21,400 --> 01:00:27,130
budeme testovať, aby ubezpečil, že hodnota vrátená nový uzol bol vlastne

739
01:00:27,130 --> 01:00:33,410
nie je null, pretože nechceme začať prístupu k tejto pamäte, ak je null.

740
01:00:33,410 --> 01:00:39,910
Môžeme testovať, aby sa ubezpečil, že nový uzol nie je rovné null.

741
01:00:39,910 --> 01:00:42,910
Alebo miesto, môžeme len zistiť, či to vlastne je null,

742
01:00:42,910 --> 01:00:52,120
a ak je null, potom sa môžeme len vrátiť false čoskoro.

743
01:00:52,120 --> 01:00:59,090
>> V tomto bode, musíme zapojiť nový uzol do jeho príslušné miesto v strome.

744
01:00:59,090 --> 01:01:03,510
Ak sa pozrieme späť na hlavnú a kde sme boli vlastne kabeláž hodnoty pred,

745
01:01:03,510 --> 01:01:08,470
vidíme, že spôsob, akým sme to robili, keď sme chceli dať 3 vo stromu

746
01:01:08,470 --> 01:01:11,750
bola sme vstúpili do ľavej dieťa koreňa.

747
01:01:11,750 --> 01:01:14,920
Keď dáme 9 do stromu, sme mali prístup k správnej dieťa koreňa.

748
01:01:14,920 --> 01:01:21,030
Mali mať ukazovateľ na materskej aby dal nové hodnoty do stromu.

749
01:01:21,030 --> 01:01:24,430
Rolovanie späť vložiť, že to nebude úplne fungovať tu

750
01:01:24,430 --> 01:01:27,550
pretože nemáme nadradené ukazovateľ.

751
01:01:27,550 --> 01:01:31,650
Čo chceme byť schopní urobiť, je, v tomto bode,

752
01:01:31,650 --> 01:01:37,080
zistiť hodnotu rodičia a vidieť - dobre, sakra,

753
01:01:37,080 --> 01:01:41,990
ak rodičia hodnota je nižšia ako aktuálna hodnota,

754
01:01:41,990 --> 01:01:54,440
potom materského právo dieťa by mal byť nový uzol;

755
01:01:54,440 --> 01:02:07,280
inak by sa rodičia ľavá dieťa bude nový uzol.

756
01:02:07,280 --> 01:02:10,290
Ale nemáme tento materský ukazovateľ ešte dosť.

757
01:02:10,290 --> 01:02:15,010
>> S cieľom získať to, sme v skutočnosti bude musieť sledovať to, ako sme ísť cez strom

758
01:02:15,010 --> 01:02:18,440
a nájsť vhodné miesto v našom slučke vyššie.

759
01:02:18,440 --> 01:02:26,840
Môžeme to urobiť, že prechodom späť na začiatok nášho vlož funkcie

760
01:02:26,840 --> 01:02:32,350
a sledovanie iného premennú ukazovatele volal rodičia.

761
01:02:32,350 --> 01:02:39,340
Budeme ju nastaviť rovná null spočiatku,

762
01:02:39,340 --> 01:02:43,640
a potom zakaždým, keď ideme cez strom,

763
01:02:43,640 --> 01:02:51,540
budeme nastaviť nadradené ukazovateľ tak, aby zodpovedala aktuálnej ukazovateľ.

764
01:02:51,540 --> 01:02:59,140
Nastaviť rodičia rovnajúcu sa súčas.

765
01:02:59,140 --> 01:03:02,260
Týmto spôsobom, zakaždým, keď prechádzame,

766
01:03:02,260 --> 01:03:05,550
budeme na zabezpečenie toho, súčasný ukazovateľ dostane zvýšený

767
01:03:05,550 --> 01:03:12,640
materská ukazovateľ sleduje ju - len o jeden stupeň vyššia, než je aktuálna ukazovateľ vo stromu.

768
01:03:12,640 --> 01:03:17,370
To všetko vyzerá veľmi dobre.

769
01:03:17,370 --> 01:03:22,380
>> Myslím, že jedna vec, ktorú budete chcieť upraviť, je tento build uzla vracia null.

770
01:03:22,380 --> 01:03:25,380
S cieľom získať stavať uzol skutočne úspešne vrátiť null,

771
01:03:25,380 --> 01:03:31,060
budeme musieť upraviť tento kód,

772
01:03:31,060 --> 01:03:37,270
pretože tu sme nikdy testované, aby sa ubezpečil, že malloc vracia platný ukazovateľ.

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

774
01:03:53,390 --> 01:03:55,250
ak malloc vracia platný ukazovateľ, potom budeme ju inicializovať;

775
01:03:55,250 --> 01:04:02,540
inak budeme len vracať, a že skončí vracia hodnotu null pre nás.

776
01:04:02,540 --> 01:04:13,050
Teraz všetko vyzerá celkom dobre. Poďme uistite sa, že to v skutočnosti zostavuje.

777
01:04:13,050 --> 01:04:22,240
Urobte binárne strom, a oh, máme nejaké veci tu deje.

778
01:04:22,240 --> 01:04:29,230
>> Máme implicitné vyhlásenie funkcií stavať uzol.

779
01:04:29,230 --> 01:04:31,950
Opäť, s týmito kompilátory, budeme začať na vrchole.

780
01:04:31,950 --> 01:04:36,380
Čo to musí znamenať, že volám stavať uzol než som vlastne deklaroval to.

781
01:04:36,380 --> 01:04:37,730
Vráťme sa ku kódu naozaj rýchlo.

782
01:04:37,730 --> 01:04:43,510
Prejdite nadol, a naozaj, je vyhlásený za moje vložka funkcie

783
01:04:43,510 --> 01:04:47,400
nad uzla zostavenie funkcie,

784
01:04:47,400 --> 01:04:50,070
ale ja sa snažím používať zostavenie uzla vo vnútri vložky.

785
01:04:50,070 --> 01:05:06,610
Chystám sa ísť a kópie - a potom vložte uzla zostavenie funkčnej až sem na vrchole.

786
01:05:06,610 --> 01:05:11,750
Tak, dúfam, že bude fungovať. Dajme to iného ísť.

787
01:05:11,750 --> 01:05:18,920
Teraz to všetko kompiluje. Všetko je dobré.

788
01:05:18,920 --> 01:05:21,640
>> Ale v tomto bode, sme v skutočnosti len naša vložte funkciu.

789
01:05:21,640 --> 01:05:26,510
Vieme len, že to prekladá, tak poďme dovnútra a dať nejaké hovory dovnútra

790
01:05:26,510 --> 01:05:28,240
Poďme urobiť, že v našej hlavnej funkcie.

791
01:05:28,240 --> 01:05:32,390
Tu sme sa v komentári 5, 8 a 2,

792
01:05:32,390 --> 01:05:36,680
a potom sme nemali prepojte je hore dole sem.

793
01:05:36,680 --> 01:05:41,640
Poďme urobiť niektoré hovory vložiť,

794
01:05:41,640 --> 01:05:46,440
a poďme tiež použiť rovnaký druh vecí, ktoré sme použili

795
01:05:46,440 --> 01:05:52,810
keď sme sa tieto printf volanie, aby sa ubezpečil, že všetko sa dostať správne vložená.

796
01:05:52,810 --> 01:06:00,550
Idem kopírovať a vložiť,

797
01:06:00,550 --> 01:06:12,450
a miesto obsahuje budeme robiť vložku.

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

799
01:06:30,140 --> 01:06:37,320
To by snáď vložiť 5, 8, a 2 do stromu.

800
01:06:37,320 --> 01:06:44,050
Kompilácie. Všetko je dobré. Teraz budeme vlastne beží náš program.

801
01:06:44,050 --> 01:06:47,330
>> Všetko sa vrátil false.

802
01:06:47,330 --> 01:06:53,830
Takže, 5, 8, a 2 nešiel, a vyzerá to, že obsahuje nenašiel ani.

803
01:06:53,830 --> 01:06:58,890
Čo sa deje? Poďme oddialiť.

804
01:06:58,890 --> 01:07:02,160
Prvým problémom bolo, že vložka sa zdalo vrátiť false,

805
01:07:02,160 --> 01:07:08,750
a vyzerá to, že je to preto, že sme opustili v našej spiatočnej falošné volanie,

806
01:07:08,750 --> 01:07:14,590
a nikdy sme vlastne vrátil pravda.

807
01:07:14,590 --> 01:07:17,880
Môžeme nastaviť, aby sa.

808
01:07:17,880 --> 01:07:25,290
Druhým problémom je, teraz, aj keď sme to - uložte tento, ukončite to,

809
01:07:25,290 --> 01:07:34,530
príkazom make znovu, že to skompilovať, spustite ho -

810
01:07:34,530 --> 01:07:37,670
vidíme, že niečo iné sa tu stalo.

811
01:07:37,670 --> 01:07:42,980
The 5, 8, a 2 boli ešte nikdy nájdené v strome.

812
01:07:42,980 --> 01:07:44,350
Takže, čo sa deje?

813
01:07:44,350 --> 01:07:45,700
>> Poďme sa pozrieť na to v kóde.

814
01:07:45,700 --> 01:07:49,790
Poďme sa pozrieť, či sa nám podarí to vyriešiť.

815
01:07:49,790 --> 01:07:57,940
Začneme s materskou nie je null.

816
01:07:57,940 --> 01:07:59,510
Sme chcete nastaviť aktuálnu ukazovateľ vo výške do koreňového ukazovateľ,

817
01:07:59,510 --> 01:08:04,280
a budeme pracovať našu cestu dole cez strom.

818
01:08:04,280 --> 01:08:08,650
Ak je aktuálny uzol nie je null, potom vieme, že sa môže pohybovať dole trochu.

819
01:08:08,650 --> 01:08:12,330
My sme nastavili nadradené ukazovateľ sa rovná aktuálnej ukazovateľ,

820
01:08:12,330 --> 01:08:15,420
skontrolovať hodnotu - v prípade, že hodnoty sú rovnaké sme sa vrátili false.

821
01:08:15,420 --> 01:08:17,540
Ak sú hodnoty menej sme sa pohyboval napravo;

822
01:08:17,540 --> 01:08:20,399
inak, sme sa presunuli doľava.

823
01:08:20,399 --> 01:08:24,220
Potom sme vybudovať uzol. Budem priblížiť trochu.

824
01:08:24,220 --> 01:08:31,410
A tu, budeme sa snažiť zapojiť do hodnoty byť rovnaký.

825
01:08:31,410 --> 01:08:37,250
Čo sa deje? Poďme sa pozrieť, keď možno Valgrind nám môže dať nápovedu.

826
01:08:37,250 --> 01:08:43,910
>> Rád používam Valgrind len preto, že Valgrind naozaj rýchlo beží

827
01:08:43,910 --> 01:08:46,729
a povie vám, či existujú nejaké chyby pamäte.

828
01:08:46,729 --> 01:08:48,300
Keď sme sa spustiť Valgrind na kód,

829
01:08:48,300 --> 01:08:55,859
ako môžete vidieť priamo here--Valgrind./binary_tree--and hit Enter.

830
01:08:55,859 --> 01:09:03,640
Môžete vidieť, že sme nemali žiadnu chybu pamäte, takže to vyzerá, že je všetko v poriadku tak ďaleko.

831
01:09:03,640 --> 01:09:07,529
Máme nejaké úniky pamäte, ktorá poznáme, pretože nie sme

832
01:09:07,529 --> 01:09:08,910
deje sa uvoľniť niektorý z našich uzlov.

833
01:09:08,910 --> 01:09:13,050
Skúsme beží GDB vidieť, čo sa vlastne deje.

834
01:09:13,050 --> 01:09:20,010
Urobíme gdb. / Binary_tree. Je zavedený až v pohode.

835
01:09:20,010 --> 01:09:23,670
Poďme nastaviť bod zlomu na vložky.

836
01:09:23,670 --> 01:09:28,600
Poďme bežať.

837
01:09:28,600 --> 01:09:31,200
Vyzerá to, že vlastne nikdy volal vložka.

838
01:09:31,200 --> 01:09:39,410
Vyzerá to, že problém bol len, že keď som zmenil sem v hlavnom -

839
01:09:39,410 --> 01:09:44,279
všetky tieto printf volaní z obsahuje -

840
01:09:44,279 --> 01:09:56,430
Nikdy som vlastne zmenil nich volať vložky.

841
01:09:56,430 --> 01:10:01,660
Teraz poďme to skúsiť. Poďme kompiláciu.

842
01:10:01,660 --> 01:10:09,130
Všetky vyzerá dobre tam. Teraz sa poďme skúsiť spustiť to, čo sa stane.

843
01:10:09,130 --> 01:10:13,320
Dobre! Všetko vyzerá celkom dobré.

844
01:10:13,320 --> 01:10:18,130
>> Posledná vec myslieť, je, existujú nejaké ostrie prípady, na tejto vložky?

845
01:10:18,130 --> 01:10:23,170
A ukázalo sa, že, no, jedna hrana prípad, ktorý je vždy zaujímavé premýšľať o tom,

846
01:10:23,170 --> 01:10:26,250
je, čo sa stane, keď váš strom je prázdna a volať túto funkciu VLOŽENIE?

847
01:10:26,250 --> 01:10:30,330
Bude to fungovať? Dobre, poďme to skúsiť.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c -

849
01:10:32,110 --> 01:10:35,810
Spôsob, akým budeme tento test je, že budeme chodiť do našej hlavnú funkciu,

850
01:10:35,810 --> 01:10:41,690
a skôr než vedenie týchto uzlov takhle,

851
01:10:41,690 --> 01:10:56,730
sme len tak zakomentovat celú vec,

852
01:10:56,730 --> 01:11:02,620
a namiesto toho, aby vedenie až uzly vlastnými silami,

853
01:11:02,620 --> 01:11:09,400
môžeme skutočne jednoducho ísť dopredu a odstráňte všetko.

854
01:11:09,400 --> 01:11:17,560
Budeme robiť všetko volanie vložiť.

855
01:11:17,560 --> 01:11:49,020
Takže, poďme urobiť - miesto 5, 8, a 2, budeme vložiť 7, 3 a 9.

856
01:11:49,020 --> 01:11:58,440
A potom budeme tiež chcieť vložiť 6 rovnako.

857
01:11:58,440 --> 01:12:05,190
Uložiť. Ukončite. Urobte binárne strom.

858
01:12:05,190 --> 01:12:08,540
To všetko kompiluje.

859
01:12:08,540 --> 01:12:10,320
Môžeme len spustiť tak ako je a uvidíme, čo sa stane,

860
01:12:10,320 --> 01:12:12,770
ale je to tiež bude veľmi dôležité, aby sa ubezpečil, že

861
01:12:12,770 --> 01:12:14,740
nemáme žiadne chyby pamäti,

862
01:12:14,740 --> 01:12:16,840
pretože to je jeden z našich okrajových prípadov, ktoré sme poznať.

863
01:12:16,840 --> 01:12:20,150
>> Poďme sa uistiť, že to funguje dobre pod Valgrind,

864
01:12:20,150 --> 01:12:28,310
ktoré budeme robiť, tým práve beží Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Vyzerá to, že skutočne majú jednu chybu z jedného kontextu -

866
01:12:31,110 --> 01:12:33,790
máme túto chybu.

867
01:12:33,790 --> 01:12:36,690
Čo sa stalo?

868
01:12:36,690 --> 01:12:41,650
Valgrind vlastne nám hovorí, kde to je.

869
01:12:41,650 --> 01:12:43,050
Oddialenie trochu.

870
01:12:43,050 --> 01:12:46,040
Vyzerá to, že sa to deje v našej vložiť funkciu,

871
01:12:46,040 --> 01:12:53,420
kde máme neplatný čítanie o veľkosti 4 na vložky, linka 60.

872
01:12:53,420 --> 01:13:03,590
Poďme sa vrátiť späť a zistiť, čo sa tu deje.

873
01:13:03,590 --> 01:13:05,350
Oddialenie naozaj rýchlo.

874
01:13:05,350 --> 01:13:14,230
Chcem sa uistiť, že to nie je na okraj obrazovky, takže môžeme vidieť všetko.

875
01:13:14,230 --> 01:13:18,760
Vytiahnuť, že v trochu. Dobre.

876
01:13:18,760 --> 01:13:35,030
Prejdite nadol, a problém je tu.

877
01:13:35,030 --> 01:13:40,120
Čo sa stane, keď sa dostaneme dole a naše aktuálne uzol je už null,

878
01:13:40,120 --> 01:13:44,010
naša materská uzol je null, takže ak sa pozrieme sa na samom vrchole, tu -

879
01:13:44,010 --> 01:13:47,340
v prípade, že while nikdy vykoná

880
01:13:47,340 --> 01:13:52,330
pretože naša súčasná hodnota je null - náš koreň je null, takže teraz je null -

881
01:13:52,330 --> 01:13:57,810
potom naša materská nikdy nedostane nastavená na súčas alebo na platnú hodnotu,

882
01:13:57,810 --> 01:14:00,580
tak, bude rodič zároveň mať hodnotu null.

883
01:14:00,580 --> 01:14:03,700
Musíme mať na pamäti, pre kontrolu, že

884
01:14:03,700 --> 01:14:08,750
v čase, keď sme sa sem dolu, a začneme prístup na hodnotu rodičia.

885
01:14:08,750 --> 01:14:13,190
Takže, čo sa stane? No, ak rodič je null -

886
01:14:13,190 --> 01:14:17,990
if (rodič == NULL) - potom vieme, že

887
01:14:17,990 --> 01:14:19,530
tam nesmie byť nič v strome.

888
01:14:19,530 --> 01:14:22,030
Musíme sa snažiť vložiť pri koreni.

889
01:14:22,030 --> 01:14:32,570
My môže vykonať tak, že iba nastavenie koreň rovnajúcu sa nový uzol.

890
01:14:32,570 --> 01:14:40,010
Potom v tomto bode, nemáme vlastne chceme ísť cez tieto iné.

891
01:14:40,010 --> 01:14:44,780
Namiesto toho, tu, môžeme urobiť buď inde-if-else,

892
01:14:44,780 --> 01:14:47,610
alebo môžeme spojiť všetko, čo sa tu v iný,

893
01:14:47,610 --> 01:14:56,300
ale tu budeme len používať iný, a to týmto spôsobom.

894
01:14:56,300 --> 01:14:59,030
Teraz, budeme testovať, aby ubezpečil, že naša materská nie je null

895
01:14:59,030 --> 01:15:02,160
do tej doby vlastne snaží prístup k jeho pole.

896
01:15:02,160 --> 01:15:05,330
To nám pomôže vyhnúť sa Segmentation fault.

897
01:15:05,330 --> 01:15:14,740
Takže, sme prestať, oddialiť, skompilovať, spustiť.

898
01:15:14,740 --> 01:15:18,130
>> Žiadne chyby, ale máme pred sebou ešte veľa úniky pamäte

899
01:15:18,130 --> 01:15:20,650
pretože sme nemali uvoľniť niektorý z našich uzlov.

900
01:15:20,650 --> 01:15:24,350
Ale, keď ideme sem a my sa pozrieť na našu výtlačok,

901
01:15:24,350 --> 01:15:30,880
vidíme, že dobre, vyzerá rovnako ako všetky naše vložiek bolo vracia hodnotu true, čo je dobré.

902
01:15:30,880 --> 01:15:33,050
Vložky sú všetky pravdivé,

903
01:15:33,050 --> 01:15:36,670
a potom príslušné obsahuje volanie platí tiež.

904
01:15:36,670 --> 01:15:41,510
>> Dobrá práce! Vyzerá to, že sme úspešne zapísaný vložku.

905
01:15:41,510 --> 01:15:47,430
To je všetko, čo máme pre tento týždeň Špecifikácia problému Set.

906
01:15:47,430 --> 01:15:51,720
Jedna zábavná výzva premýšľať o tom, ako by ste vlastne ísť

907
01:15:51,720 --> 01:15:55,340
a bez všetkých uzlov v tomto stromu.

908
01:15:55,340 --> 01:15:58,830
Môžeme tak urobiť množstvo rôznych spôsobov,

909
01:15:58,830 --> 01:16:01,930
ale nechám, že na vás experimentovať,

910
01:16:01,930 --> 01:16:06,080
a ako zábavu výzvu, vyskúšať a uistite sa, že si môžete byť istí

911
01:16:06,080 --> 01:16:09,490
že táto správa Valgrind Neboli nájdené žiadne chyby a žiadne úniky.

912
01:16:09,490 --> 01:16:12,880
>> Veľa šťastia na tento týždeň Huffman kódovanie problému nastavenia,

913
01:16:12,880 --> 01:16:14,380
a uvidíme sa budúci týždeň!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]