1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Část 7: Další Komfortní]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard University]

3
00:00:05,090 --> 00:00:07,930
[To je CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Dobrá. Tak jak jsem řekl ve svém e-mailu,

5
00:00:10,110 --> 00:00:14,060
to bude binární strom náročný úsek.

6
00:00:14,060 --> 00:00:16,820
Ale tam není, že mnoho otázek.

7
00:00:16,820 --> 00:00:18,920
Takže budeme se snažit a čerpat z každé otázky

8
00:00:18,920 --> 00:00:25,430
a jít do bolestné detailu všech nejlepších způsobů, jak dělat věci.

9
00:00:25,430 --> 00:00:31,200
Takže hned na začátku, jsme se projít vzorku kreseb binárních stromů a podobně.

10
00:00:31,200 --> 00:00:35,970
Tak tady, "Pamatuj si, že binární strom má uzly podobné těm propojeného seznamu,

11
00:00:35,970 --> 00:00:38,150
kromě namísto jednoho ukazatele jsou dva: jeden pro levé "dítě"

12
00:00:38,150 --> 00:00:41,950
a jeden pro pravé "dítě". "

13
00:00:41,950 --> 00:00:45,630
Takže binární strom je stejně jako propojeného seznamu,

14
00:00:45,630 --> 00:00:47,910
kromě struct bude mít dva ukazatele.

15
00:00:47,910 --> 00:00:51,390
Tam je trinary stromy, které se chystají tři ukazatele,

16
00:00:51,390 --> 00:00:56,540
tam jsou n-ární stromy, které právě mají obecný ukazatel

17
00:00:56,540 --> 00:01:00,320
že pak budou muset malloc být dostatečně velké, aby se

18
00:01:00,320 --> 00:01:04,840
dost ukazatele na všech možných dětí.

19
00:01:04,840 --> 00:01:08,200
Takže binární strom jen se stane, že konstantní množství dvou.

20
00:01:08,200 --> 00:01:11,260
Pokud chcete, můžete si dát propojeného seznamu jako unární strom,

21
00:01:11,260 --> 00:01:15,360
ale já si nemyslím, že někdo volá, že.

22
00:01:15,360 --> 00:01:18,060
"Nakreslete boxy-a-arrows diagram binárního stromu uzel

23
00:01:18,060 --> 00:01:24,110
obsahující Nate oblíbené číslo, 7, kde každé dítě ukazatel je null. "

24
00:01:24,110 --> 00:01:27,780
Takže iPad režimu.

25
00:01:27,780 --> 00:01:30,280
>> Bude to být docela jednoduché.

26
00:01:30,280 --> 00:01:36,150
Jsme prostě bude mít uzel, budu kreslit jako čtverec.

27
00:01:36,150 --> 00:01:38,730
A já budu čerpat hodnoty zde.

28
00:01:38,730 --> 00:01:41,090
Takže hodnota půjde sem,

29
00:01:41,090 --> 00:01:44,770
a pak tady dole budeme mít levé ukazatel vlevo a vpravo ukazatel vpravo.

30
00:01:44,770 --> 00:01:50,430
A to je velmi, takže je zvykem nazývat levý a pravý, ukazatel jména.

31
00:01:50,430 --> 00:01:52,460
Oba tito budou mít hodnotu null.

32
00:01:52,460 --> 00:01:57,870
To bude jen null, a že bude jen null.

33
00:01:57,870 --> 00:02:03,630
Dobře. Takže zpět sem.

34
00:02:03,630 --> 00:02:05,700
"S propojeného seznamu, jsme měli pouze k uložení ukazatele

35
00:02:05,700 --> 00:02:09,639
na prvním uzlu v seznamu za účelem pamatovat celý spojový seznam nebo celý seznam.

36
00:02:09,639 --> 00:02:11,650
Stejně tak, se stromy, máme pouze k uložení ukazatele

37
00:02:11,650 --> 00:02:13,420
na jednom uzlu, aby se pamatovat celý strom.

38
00:02:13,420 --> 00:02:15,980
Tento uzel je calle 'root' stromu.

39
00:02:15,980 --> 00:02:18,320
Stavět na diagramu z doby před nebo nakreslit nový

40
00:02:18,320 --> 00:02:21,690
tak, že máte boxy-a-arrows znázornění binárního stromu

41
00:02:21,690 --> 00:02:25,730
s hodnotu 7, pak 3 v levé,

42
00:02:25,730 --> 00:02:32,760
pak 9 na pravé straně, a pak 6 na pravé straně 3 ".

43
00:02:32,760 --> 00:02:34,810
Uvidíme, jestli si pamatuju všechno v mé hlavě.

44
00:02:34,810 --> 00:02:37,670
Tak to bude naše kořen tady.

45
00:02:37,670 --> 00:02:41,600
Dáme si ukazatel někde, něco, co budeme volat kořen,

46
00:02:41,600 --> 00:02:45,140
a to ukazuje na toho chlapa.

47
00:02:45,140 --> 00:02:48,490
Nyní se vytvořit nový uzel,

48
00:02:48,490 --> 00:02:52,870
co máme, 3 vlevo?

49
00:02:52,870 --> 00:02:57,140
Takže nový uzel s 3, a to na počátku ukazuje nulový.

50
00:02:57,140 --> 00:02:59,190
Já si jen dát N.

51
00:02:59,190 --> 00:03:02,250
Nyní chceme, aby se to jít vlevo 7.

52
00:03:02,250 --> 00:03:06,840
Tak jsme změnit tento ukazatel nyní ukazují na toho chlapa.

53
00:03:06,840 --> 00:03:12,420
A my to samé. Chceme 9 nad zde

54
00:03:12,420 --> 00:03:14,620
který zpočátku jen říká, null.

55
00:03:14,620 --> 00:03:19,600
Budeme měnit tento ukazatel, přejděte na 9,

56
00:03:19,600 --> 00:03:23,310
a nyní chceme dát 6 na pravé straně 3.

57
00:03:23,310 --> 00:03:32,170
Takže to bude - udělat 6.

58
00:03:32,170 --> 00:03:34,310
A ten chlap bude směřovat tam.

59
00:03:34,310 --> 00:03:38,320
Dobře. Tak to je vše, co je od nás žádá dělat.

60
00:03:38,320 --> 00:03:42,770
>> Teď pojďme přes některé pojmy.

61
00:03:42,770 --> 00:03:46,690
Už jsme mluvili o tom, jak kořen stromu je na nejvyšší uzel ve stromu.

62
00:03:46,690 --> 00:03:54,720
Ten obsahuje 7. Uzly v dolní části stromu se nazývají listy.

63
00:03:54,720 --> 00:04:01,240
Každý uzel, který má prostě null jako jeho děti, je list.

64
00:04:01,240 --> 00:04:03,680
Je tedy možné, pokud náš binární strom je jen jeden uzel,

65
00:04:03,680 --> 00:04:10,130
že strom je list, a to je vše.

66
00:04:10,130 --> 00:04:12,060
"" Výška "stromu je počet chmele je nutné provést

67
00:04:12,060 --> 00:04:16,620
se dostat z vrcholu do listu. "

68
00:04:16,620 --> 00:04:18,640
Dostaneme do, v druhé, rozdíl

69
00:04:18,640 --> 00:04:21,940
mezi symetrické a nesymetrické binárních stromů,

70
00:04:21,940 --> 00:04:29,470
ale nyní, celková výška tohoto stromu

71
00:04:29,470 --> 00:04:34,520
Řekl bych, že je 3, ale pokud budete počítat množství chmele

72
00:04:34,520 --> 00:04:39,710
je nutné provést tak, aby se dostat do 9, pak je to opravdu jen výška 2.

73
00:04:39,710 --> 00:04:43,340
Právě teď je to nevyvážený binární strom,

74
00:04:43,340 --> 00:04:49,840
ale budeme mluvili o vyvážené, když se dostane za relevantní.

75
00:04:49,840 --> 00:04:52,040
Takže teď můžeme mluvit o uzlů na stromě, pokud jde

76
00:04:52,040 --> 00:04:54,700
ve vztahu k ostatním uzlů stromu.

77
00:04:54,700 --> 00:04:59,730
Takže teď máme rodiče, děti, sourozenci, předky a potomci.

78
00:04:59,730 --> 00:05:05,650
Oni jsou docela zdravý rozum, co to znamená.

79
00:05:05,650 --> 00:05:09,610
Ptáme-li se - je to rodiče.

80
00:05:09,610 --> 00:05:12,830
Takže to, co je nadřazený 3?

81
00:05:12,830 --> 00:05:16,090
[Studenti] 7. Jo >>. Mateřská se jen bude, co poukazuje na tobě.

82
00:05:16,090 --> 00:05:20,510
Tak co, jsou děti 7?

83
00:05:20,510 --> 00:05:23,860
[Studenti] 3 a 9. Jo >>.

84
00:05:23,860 --> 00:05:26,460
Všimněte si, že "děti" doslova znamená děti,

85
00:05:26,460 --> 00:05:31,010
tak 6 se nepoužijí, protože je to jako vnouče.

86
00:05:31,010 --> 00:05:35,540
Ale pak, pokud půjdeme potomky, takže jaké jsou potomci 7?

87
00:05:35,540 --> 00:05:37,500
[Studenti] 3, 6 a 9. Jo >>.

88
00:05:37,500 --> 00:05:42,330
Potomci kořene bude všechno v stromu,

89
00:05:42,330 --> 00:05:47,950
snad s výjimkou kořenový uzel sám, pokud nechcete, aby zvážila, že potomek.

90
00:05:47,950 --> 00:05:50,750
A konečně, předkové, tak je to v opačném směru.

91
00:05:50,750 --> 00:05:55,740
Takže jaké jsou předky 6?

92
00:05:55,740 --> 00:05:58,920
[Studenti] 3 a 7. Jo >>. 9 není zahrnuta.

93
00:05:58,920 --> 00:06:02,520
Je to jen přímé linie zpět do kořenového adresáře

94
00:06:02,520 --> 00:06:13,230
bude vaši předkové.

95
00:06:13,230 --> 00:06:16,300
>> "Řekneme, že binární strom je" přikázal ", pokud pro každý uzel ve stromu,

96
00:06:16,300 --> 00:06:19,530
všechny jeho potomky na levé straně mají menší hodnoty

97
00:06:19,530 --> 00:06:22,890
a všechny ty, na pravé straně jsou větší hodnoty.

98
00:06:22,890 --> 00:06:27,060
Například, je strom nad objednal, ale není to jen možné objednat uspořádání. "

99
00:06:27,060 --> 00:06:30,180
Než se dostaneme k tomu,

100
00:06:30,180 --> 00:06:36,420
objednal binární strom je také známý jako binární vyhledávací strom.

101
00:06:36,420 --> 00:06:38,660
Zde se stalo, že se nazývat to objednané binární strom,

102
00:06:38,660 --> 00:06:41,850
ale nikdy jsem neslyšel, že jen objednat binární strom před,

103
00:06:41,850 --> 00:06:46,650
a na kvíz jsme mnohem častěji, aby strom binárního vyhledávání.

104
00:06:46,650 --> 00:06:49,250
Jsou jedna a ta samá,

105
00:06:49,250 --> 00:06:54,580
a to je důležité, poznáte rozdíl mezi binárním stromem a binární vyhledávací strom.

106
00:06:54,580 --> 00:06:58,830
Binární strom je jen strom, který ukazuje na dvě věci.

107
00:06:58,830 --> 00:07:02,120
Každý uzel poukazuje na dvě věci.

108
00:07:02,120 --> 00:07:06,310
Neexistuje žádný úvaha o hodnotách, které se ukazuje na.

109
00:07:06,310 --> 00:07:11,370
Tak jako tady, protože je to binární vyhledávací strom,

110
00:07:11,370 --> 00:07:14,030
víme, že když jdeme vlevo 7,

111
00:07:14,030 --> 00:07:16,670
pak všechny hodnoty, které můžeme případně dosáhnout

112
00:07:16,670 --> 00:07:19,310
tím, že jde vlevo 7 musí být menší než 7.

113
00:07:19,310 --> 00:07:24,070
Všimněte si, že všechny hodnoty menší než 7 jsou 3 a 6.

114
00:07:24,070 --> 00:07:26,040
Ti jsou na levé straně 7.

115
00:07:26,040 --> 00:07:29,020
Pokud se jít napravo 7, všechno musí být větší než 7,

116
00:07:29,020 --> 00:07:33,220
takže 9 je na pravé straně 7, takže jsme v pohodě.

117
00:07:33,220 --> 00:07:36,150
Toto není případ binárního stromu,

118
00:07:36,150 --> 00:07:40,020
pro pravidelné binárního stromu můžeme jen mají 3 nahoře, 7 na levé straně,

119
00:07:40,020 --> 00:07:47,630
9 na levé straně 7, není objednání hodnot vůbec.

120
00:07:47,630 --> 00:07:56,140
Nyní, nebudeme vlastně dělat, protože je to nudné a zbytečné,

121
00:07:56,140 --> 00:07:59,400
ale "zkusit nakreslit tolik objednané stromů, jak si můžete myslet

122
00:07:59,400 --> 00:08:01,900
pomocí čísla 7, 3, 9, a 6.

123
00:08:01,900 --> 00:08:06,800
Kolik odlišné uspořádání jsou tam? Co je výška každé z nich? "

124
00:08:06,800 --> 00:08:10,480
>> Uděláme pár, ale hlavní myšlenka je,

125
00:08:10,480 --> 00:08:16,530
To je v žádném případě jedinečné znázornění binárního stromu, který obsahuje tyto hodnoty.

126
00:08:16,530 --> 00:08:22,760
Vše co potřebujeme, je nějaký binární strom, který obsahuje 7, 3, 6 a 9.

127
00:08:22,760 --> 00:08:25,960
Dalším možným platné jeden by být kořenový je 3,

128
00:08:25,960 --> 00:08:30,260
jít doleva a je to 6, přejděte doleva a je to 7,

129
00:08:30,260 --> 00:08:32,730
jít doleva a je to 9.

130
00:08:32,730 --> 00:08:36,169
To je naprosto platný binární vyhledávací strom.

131
00:08:36,169 --> 00:08:39,570
Není to velmi užitečné, protože je to stejně jako propojeného seznamu

132
00:08:39,570 --> 00:08:43,750
a všechny tyto ukazatele jsou jen nulový.

133
00:08:43,750 --> 00:08:48,900
Ale je to platný strom. Jo?

134
00:08:48,900 --> 00:08:51,310
[Student] Ne hodnoty musí být větší na pravé straně?

135
00:08:51,310 --> 00:08:56,700
Nebo je to -? >> Ty jsem chtěl jít na druhou stranu.

136
00:08:56,700 --> 00:09:00,960
K dispozici je také - jo, pojďme přejít to.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Dobrý úlovek.

138
00:09:07,770 --> 00:09:11,730
To ještě musí poslouchat, co binární strom vyhledávání dělat.

139
00:09:11,730 --> 00:09:15,650
Takže všechno na levé straně musí být menší než daný uzel.

140
00:09:15,650 --> 00:09:23,180
Mohli bychom jen přesunout, řekněme, tato 6 a dát sem.

141
00:09:23,180 --> 00:09:26,880
Ne, nemůžeme. Proč jsem to dělat, že?

142
00:09:26,880 --> 00:09:35,350
Pojďme udělat - tady je 6, zde je 7, 6 bodů na 3.

143
00:09:35,350 --> 00:09:39,290
To je stále platný binární vyhledávací strom.

144
00:09:39,290 --> 00:09:49,260
Co je špatně, když si - uvidíme, jestli můžu přijít s uspořádáním.

145
00:09:49,260 --> 00:09:52,280
Jo, dobře. Takže to, co je špatně s tímto stromem?

146
00:09:52,280 --> 00:10:08,920
Myslím, že jsem už dal náznak, že je něco v nepořádku s ní.

147
00:10:08,920 --> 00:10:14,430
Proč jsem to dělat, že?

148
00:10:14,430 --> 00:10:18,510
Dobře. To vypadá rozumně.

149
00:10:18,510 --> 00:10:22,590
Podíváme-li se na každém uzlu, jako je 7, pak na levé straně 7 je 3.

150
00:10:22,590 --> 00:10:24,960
Takže máme 3, věc vpravo 3 je 6.

151
00:10:24,960 --> 00:10:27,750
A když se podíváte na 6, ta věc vpravo 6 je 9.

152
00:10:27,750 --> 00:10:30,910
Tak proč je to není platný binární vyhledávací strom?

153
00:10:30,910 --> 00:10:36,330
[Studenti] 9, je stále na levé straně 7. Jo >>.

154
00:10:36,330 --> 00:10:43,710
Musí to být pravda, že všechny hodnoty, které můžete případně dosáhnout tím, že půjdete na levé straně 7 arů méně než 7.

155
00:10:43,710 --> 00:10:49,120
Pokud půjdeme vlevo 7, dostaneme se 3 a stále můžeme dostat do 6,

156
00:10:49,120 --> 00:10:52,520
můžeme ještě dostat do 9, ale tím, že má pryč méně než 7,

157
00:10:52,520 --> 00:10:55,070
bychom však být schopen se dostat na číslo, které je větší než 7.

158
00:10:55,070 --> 00:10:59,830
Takže to není platný binární vyhledávací strom.

159
00:10:59,830 --> 00:11:02,330
>> Můj bratr vlastně měl rozhovor otázku

160
00:11:02,330 --> 00:11:07,760
to bylo v podstatě to, jen kód do něčeho k ověření

161
00:11:07,760 --> 00:11:10,500
zda strom je binární vyhledávací strom,

162
00:11:10,500 --> 00:11:13,580
a tak první věc, kterou udělal, bylo, jen zkontrolovat,

163
00:11:13,580 --> 00:11:17,020
v případě, že levý a pravý jsou správné, a pak iterovat tam.

164
00:11:17,020 --> 00:11:19,700
Ale nemůžeš jen to, že, budete mít neustále přehled

165
00:11:19,700 --> 00:11:22,550
na skutečnost, že teď, když jsem pryč odešel ze dne 7.,

166
00:11:22,550 --> 00:11:26,340
vše v tomto podstromu musí být menší než 7.

167
00:11:26,340 --> 00:11:28,430
Správný algoritmus potřebuje sledovat

168
00:11:28,430 --> 00:11:35,970
z mezí, které je možné hodnoty možná spadají dovnitř

169
00:11:35,970 --> 00:11:38,360
Nebudeme projít všechny z nich.

170
00:11:38,360 --> 00:11:41,630
K dispozici je pěkná opakování vztah,

171
00:11:41,630 --> 00:11:44,810
i když jsme se dostali k těm, jinak nebudeme se k těm,

172
00:11:44,810 --> 00:11:47,030
definování, kolik jich vlastně je.

173
00:11:47,030 --> 00:11:53,180
Takže tam je 14 z nich.

174
00:11:53,180 --> 00:11:56,020
Myšlenka na to, jak by to matematicky je jako,

175
00:11:56,020 --> 00:11:59,770
si můžete vybrat jeden libovolný jednoho být kořenový uzel,

176
00:11:59,770 --> 00:12:03,160
a pak, když vybrat 7 být kořenový uzel,

177
00:12:03,160 --> 00:12:08,150
pak tam jsou, řekněme, některá čísla, které mohou jít být mé levici uzel,

178
00:12:08,150 --> 00:12:10,440
a tam jsou některé čísla, která mohou být moje pravá uzel,

179
00:12:10,440 --> 00:12:15,090
ale pokud jsem n celkové počty, pak se částka, která může jít vlevo

180
00:12:15,090 --> 00:12:18,820
plus částka, která může jít vpravo je n - 1.

181
00:12:18,820 --> 00:12:26,130
Takže ze zbývajících čísel, musí být schopen jít buď doleva nebo doprava.

182
00:12:26,130 --> 00:12:31,580
Zdá se, že těžké, když jsem dal 3 první pak všechno musí jít doleva,

183
00:12:31,580 --> 00:12:35,080
ale když jsem dal 7, pak některé věci může jít vlevo a některé věci mohou jít na práva.

184
00:12:35,080 --> 00:12:39,570
A '3 první "Myslel jsem všechno může jít doprava.

185
00:12:39,570 --> 00:12:42,350
Je to opravdu, stačí přemýšlet o tom, jak,

186
00:12:42,350 --> 00:12:47,980
kolik věcí může jít na další úroveň stromu.

187
00:12:47,980 --> 00:12:50,420
A to je se, že je 14, nebo se může čerpat všechny z nich,

188
00:12:50,420 --> 00:12:54,650
a pak dostanete 14.

189
00:12:54,650 --> 00:13:01,120
>> Vraťme se zpět sem,

190
00:13:01,120 --> 00:13:03,510
"Objednané binární stromy jsou skvělé, protože můžeme hledat v nich

191
00:13:03,510 --> 00:13:06,910
velmi podobně jako vyhledávání přes tříděném poli.

192
00:13:06,910 --> 00:13:10,120
Chcete-li tak učinit, začneme u kořene a práci si cestu dolů stromu

193
00:13:10,120 --> 00:13:13,440
směrem listů, kontrola každý uzel v hodnoty na hodnoty, které jsme hledáte.

194
00:13:13,440 --> 00:13:15,810
Pokud je aktuální uzel je hodnota nižší než hodnota, kterou hledáme,

195
00:13:15,810 --> 00:13:18,050
jdete vedle uzlu pravé dítě.

196
00:13:18,050 --> 00:13:20,030
V opačném případě, půjdete do uzlu na levé dítě.

197
00:13:20,030 --> 00:13:22,800
V určitém bodě, budete buď najít hodnotu, kterou hledáte, nebo budete spouštět do null,

198
00:13:22,800 --> 00:13:28,520
označující hodnotu není ve stromu. "

199
00:13:28,520 --> 00:13:32,450
Mám k překreslení stromu jsme měli předtím, že bude trvat sekundu.

200
00:13:32,450 --> 00:13:38,280
Ale chceme se podívat do, zda 6, 10, a 1 jsou ve stromu.

201
00:13:38,280 --> 00:13:49,180
Takže, co to bylo, 7, 9, 3, 6. Dobře.

202
00:13:49,180 --> 00:13:52,730
Čísla chcete vyhledat, chceme podívat do 6.

203
00:13:52,730 --> 00:13:55,440
Jak se tento algoritmus funguje?

204
00:13:55,440 --> 00:14:03,040
No, máme také nějaké kořenový ukazatel na náš strom.

205
00:14:03,040 --> 00:14:12,460
A měli bychom jít ke kořenu a říci, je tato hodnota rovna hodnotě my hledáme?

206
00:14:12,460 --> 00:14:15,000
Takže jsme hledali 6, takže to není stejné.

207
00:14:15,000 --> 00:14:20,140
Tak jsme dál, a teď říkáme, ano, takže 6 je menší než 7.

208
00:14:20,140 --> 00:14:23,940
Znamená to, že chceme jít doleva, nebo chceme jít doprava?

209
00:14:23,940 --> 00:14:27,340
[Student] Left. Jo >>.

210
00:14:27,340 --> 00:14:33,340
Je to výrazně jednodušší, vše, co musíte udělat, je nakreslit jeden možný uzel stromu

211
00:14:33,340 --> 00:14:37,760
a pak ne - místo toho se snaží myslet v hlavě,

212
00:14:37,760 --> 00:14:40,020
v pořádku, pokud je to méně, mám jít doleva nebo jít právo,

213
00:14:40,020 --> 00:14:43,030
Jen při pohledu na tento obrázek, je to velmi jasné, že musím jít doleva

214
00:14:43,030 --> 00:14:47,700
v případě, že uzel je větší než hodnota, že jsem hledal.

215
00:14:47,700 --> 00:14:52,600
Takže jdete doleva, teď jsem na 3.

216
00:14:52,600 --> 00:14:57,770
Chci - 3, je menší, než je hodnota Hledám, což je o 6.

217
00:14:57,770 --> 00:15:03,420
Takže jdeme vpravo, a teď jsem skončil na 6,

218
00:15:03,420 --> 00:15:07,380
což je hodnota Hledám, tak jsem se vrátit true.

219
00:15:07,380 --> 00:15:15,760
Další hodnota budu hledat je 10.

220
00:15:15,760 --> 00:15:23,230
Dobře. Takže 10, nyní se chystá - odříznout, že - bude následovat kořen.

221
00:15:23,230 --> 00:15:27,670
Nyní, 10 bude větší než 7, tak se chci podívat na pravé straně.

222
00:15:27,670 --> 00:15:31,660
Chystám se jít sem, 10 bude větší než 9,

223
00:15:31,660 --> 00:15:34,520
takže budu chtít podívat na pravé straně.

224
00:15:34,520 --> 00:15:42,100
Přišel jsem sem, ale sem teď jsem na null.

225
00:15:42,100 --> 00:15:44,170
Co mám dělat, když jsem narazila null?

226
00:15:44,170 --> 00:15:47,440
[Student] Návrat false? Jo >>. Nenašel jsem 10.

227
00:15:47,440 --> 00:15:49,800
1 se bude téměř totožný případ,

228
00:15:49,800 --> 00:15:51,950
kromě toho, že to prostě bude převrácený, namísto hledání

229
00:15:51,950 --> 00:15:56,540
dolů na pravé straně, jdu se podívat dolů na levé straně.

230
00:15:56,540 --> 00:16:00,430
>> Myslím, že teď jsme vlastně dostat ke kódu.

231
00:16:00,430 --> 00:16:04,070
Tady je místo, kde - otevřít CS50 spotřebič a navigaci si cestu tam,

232
00:16:04,070 --> 00:16:07,010
ale můžete také jen to je v prostoru.

233
00:16:07,010 --> 00:16:09,170
Je to asi ideální, aby to v prostoru,

234
00:16:09,170 --> 00:16:13,760
protože mohou pracovat v prostoru.

235
00:16:13,760 --> 00:16:19,170
"Nejprve budeme potřebovat novou definici typu pro binární uzel stromu obsahuje int hodnoty.

236
00:16:19,170 --> 00:16:21,400
Použití desku spotřebiče typedef níže,

237
00:16:21,400 --> 00:16:24,510
vytvořit novou definici typu pro uzel v binárním stromu.

238
00:16:24,510 --> 00:16:27,930
Pokud narazíte. . . "Bla, bla, bla. Dobře.

239
00:16:27,930 --> 00:16:30,380
Takže pojďme dát desku spotřebiče tady,

240
00:16:30,380 --> 00:16:41,630
typedef struct uzel, a uzel. Jo, dobře.

241
00:16:41,630 --> 00:16:44,270
Takže jaké jsou pole budeme chtít v naší uzlu?

242
00:16:44,270 --> 00:16:46,520
[Student] Int a pak dva ukazatele?

243
00:16:46,520 --> 00:16:49,700
>> Int hodnota, dva ukazatele? Jak psát ukazatelů?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. >> Měl bych přiblížit dovnitř Jo, tak struct uzel * vlevo,

245
00:16:58,440 --> 00:17:01,320
a struct uzel * P.

246
00:17:01,320 --> 00:17:03,460
A pamatujte diskusi od minule,

247
00:17:03,460 --> 00:17:15,290
že toto nemá smysl, to nedává smysl,

248
00:17:15,290 --> 00:17:18,270
To nedává smysl.

249
00:17:18,270 --> 00:17:25,000
Musíte všechno tam s cílem definovat tuto rekurzivní struct.

250
00:17:25,000 --> 00:17:27,970
Dobře, tak to je to, co náš strom bude vypadat.

251
00:17:27,970 --> 00:17:37,670
Pokud bychom udělali trinary strom, pak uzel může vypadat jako b1, b2, struct uzel * b3,

252
00:17:37,670 --> 00:17:43,470
kde b je větev - vlastně, já jsem slyšel, že víc vlevo, střední, pravý, ale co.

253
00:17:43,470 --> 00:17:55,610
My jen o binární, tak doprava, doleva.

254
00:17:55,610 --> 00:17:59,110
"Teď vyhlásit globální uzel * proměnné pro kořen stromu."

255
00:17:59,110 --> 00:18:01,510
Takže my nebudeme dělat, že.

256
00:18:01,510 --> 00:18:08,950
Aby se věci poněkud obtížnější a obecnější,

257
00:18:08,950 --> 00:18:11,570
nebudeme mít globální uzlu proměnnou.

258
00:18:11,570 --> 00:18:16,710
Místo toho, v hlavní budeme deklarovat všechny naše uzlu věci,

259
00:18:16,710 --> 00:18:20,500
a to znamená, že pod, když jsme rozběhnou

260
00:18:20,500 --> 00:18:23,130
naše obsahuje funkce a náš vložka funkce,

261
00:18:23,130 --> 00:18:27,410
místo našich obsahuje funkce jen s použitím tohoto globálního uzlu proměnnou,

262
00:18:27,410 --> 00:18:34,280
budeme mít trvat jako argument stromu, který chceme, aby to zpracovat.

263
00:18:34,280 --> 00:18:36,650
S globální proměnnou měl dělat věci lépe.

264
00:18:36,650 --> 00:18:42,310
Budeme dělat věci těžší.

265
00:18:42,310 --> 00:18:51,210
Nyní trvat minutu nebo tak, aby prostě takovéhle věci,

266
00:18:51,210 --> 00:18:57,690
kde uvnitř hlavní chcete vytvořit tento strom, a to je vše, co chcete dělat.

267
00:18:57,690 --> 00:19:04,530
Zkuste a postavit se k tomuto stromu v hlavní funkci.

268
00:19:42,760 --> 00:19:47,610
>> Dobře. Takže si ani nemusíte mít postavil strom celou cestu ještě.

269
00:19:47,610 --> 00:19:49,840
Ale někdo něco, co bych mohl vytáhnout nahoru

270
00:19:49,840 --> 00:20:03,130
ukázat, jak by se dalo začít budovat takový strom?

271
00:20:03,130 --> 00:20:08,080
[Student] Někdo bouchat, snaží se dostat ven.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Každý, kdo vyhovuje jejich stromu konstrukce?

273
00:20:13,100 --> 00:20:15,520
[Student] Jasně. Je to neudělal. >> To je v pořádku. Můžeme jen dokončit -

274
00:20:15,520 --> 00:20:26,860
oh, můžete si ji uložit? Hurá.

275
00:20:26,860 --> 00:20:32,020
Takže tu máme - oh, jsem mírně oříznuté.

276
00:20:32,020 --> 00:20:34,770
Jsem přiblížení?

277
00:20:34,770 --> 00:20:37,730
Zvětšení, přejděte ven. >> Mám dotaz. Jo >>?

278
00:20:37,730 --> 00:20:44,410
[Student] Při definování struct, jsou věci jako inicializována na něco?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Dobře. Takže budete muset inicializovat -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Při definování, nebo při deklarování struct,

281
00:20:50,450 --> 00:20:55,600
není inicializován ve výchozím nastavení, je to jako když deklarovat int.

282
00:20:55,600 --> 00:20:59,020
Je to přesně totéž. Je to jako každý z jednotlivých jeho oblastech

283
00:20:59,020 --> 00:21:04,460
může mít na odpadky hodnotu v něm. >> A je možné definovat - nebo prohlásit struct

284
00:21:04,460 --> 00:21:07,740
způsobem, aby při jejím inicializovat?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ano. Takže, zkratka inicializace syntaxe

286
00:21:13,200 --> 00:21:18,660
bude vypadat -

287
00:21:18,660 --> 00:21:22,200
Existují dva způsoby, jak to udělat můžeme. Myslím, že bychom měli zkompilovat

288
00:21:22,200 --> 00:21:25,840
aby se ujistil, zvonění také to dělá.

289
00:21:25,840 --> 00:21:28,510
Pořadí argumentů, které přichází v struct,

290
00:21:28,510 --> 00:21:32,170
dáte jako pořadí argumentů uvnitř těchto složených závorek.

291
00:21:32,170 --> 00:21:35,690
Takže pokud chcete inicializovat ji 9 a odešel se null a pak doprava bude null,

292
00:21:35,690 --> 00:21:41,570
, že by bylo 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternativou je, a editor nemá rád tuto syntaxi,

294
00:21:47,890 --> 00:21:50,300
a to si myslí, že chci nový blok,

295
00:21:50,300 --> 00:22:01,800
ale alternativou je něco jako -

296
00:22:01,800 --> 00:22:04,190
tady, dám to na nový řádek.

297
00:22:04,190 --> 00:22:09,140
Můžete výslovně říci, že jsem zapomněl na přesnou syntaxi.

298
00:22:09,140 --> 00:22:13,110
Takže můžete explicitně řešit podle názvu, a říkají,

299
00:22:13,110 --> 00:22:21,570
. C, nebo. Hodnota = 9,. Left = NULL.

300
00:22:21,570 --> 00:22:24,540
Hádám, že je třeba tato pravidla čárky.

301
00:22:24,540 --> 00:22:29,110
. Doprava = NULL, takže tento způsob nemáte

302
00:22:29,110 --> 00:22:33,780
skutečně potřebují znát pořadí struct,

303
00:22:33,780 --> 00:22:36,650
a když tohle čtete, je to mnohem jednoznačnější,

304
00:22:36,650 --> 00:22:41,920
o tom, co je hodnotou inicializována.

305
00:22:41,920 --> 00:22:44,080
>> To se stane, že je jedna z věcí, které -

306
00:22:44,080 --> 00:22:49,100
tak, pro nejvíce se rozdělit, C + +, je nadmnožinou C.

307
00:22:49,100 --> 00:22:54,160
Můžete si vzít kód v C, přesuňte ji k C + +, a to by mělo sestavit.

308
00:22:54,160 --> 00:22:59,570
To je jedna z věcí, které C + + nepodporuje, takže lidé mají tendenci, aby to nedělala.

309
00:22:59,570 --> 00:23:01,850
Já nevím, jestli je to jediný důvod, proč lidé nemají tendenci dělat to,

310
00:23:01,850 --> 00:23:10,540
ale případ, kdy jsem potřeboval použít třeba pro práci s C + +, a tak jsem nemohl použít.

311
00:23:10,540 --> 00:23:14,000
Dalším příkladem něčeho, co nefunguje s C + +, je

312
00:23:14,000 --> 00:23:16,940
jak malloc vrací "void *," technicky,

313
00:23:16,940 --> 00:23:20,200
ale vy jste mohli jen říct, char * x = malloc cokoliv,

314
00:23:20,200 --> 00:23:22,840
a to bude automaticky přetypovat na char *.

315
00:23:22,840 --> 00:23:25,450
To automatické obsazení nestává v C + +.

316
00:23:25,450 --> 00:23:28,150
To by nebylo zkompilovat, a vy byste explicitně potřeba říci

317
00:23:28,150 --> 00:23:34,510
char *, malloc, co, hodit to na char *.

318
00:23:34,510 --> 00:23:37,270
Není mnoho věcí, které C a C + + neshodnou na,

319
00:23:37,270 --> 00:23:40,620
ale ty jsou dva.

320
00:23:40,620 --> 00:23:43,120
Takže půjdeme s touto syntaxí.

321
00:23:43,120 --> 00:23:46,150
Ale i když jsme nešli s tím syntaxí,

322
00:23:46,150 --> 00:23:49,470
to, co je - by mohlo být špatně s tím?

323
00:23:49,470 --> 00:23:52,170
[Student] Nepotřebuju, aby dereference to? Jo >>.

324
00:23:52,170 --> 00:23:55,110
Pamatujte si, že šipka má implicitní dereference,

325
00:23:55,110 --> 00:23:58,230
a tak, když jsme jen do činění s struct,

326
00:23:58,230 --> 00:24:04,300
chceme použít. aby se na pole uvnitř struct.

327
00:24:04,300 --> 00:24:07,200
A jediný čas používáme šipku je, když chceme udělat -

328
00:24:07,200 --> 00:24:13,450
no, šipka je ekvivalentní -

329
00:24:13,450 --> 00:24:17,020
že to, co by to znamenalo, kdyby jsem šíp.

330
00:24:17,020 --> 00:24:24,600
Všechny arrow prostředek je, dereference to, teď jsem na struct, a můžu pole.

331
00:24:24,600 --> 00:24:28,040
Buď si pole přímo, nebo dereference a získat pole -

332
00:24:28,040 --> 00:24:30,380
Myslím, že by to mělo být hodnota.

333
00:24:30,380 --> 00:24:33,910
Ale tady se zabývám jen struct, ne ukazatel na struct,

334
00:24:33,910 --> 00:24:38,780
a tak nemohu použít šipku.

335
00:24:38,780 --> 00:24:47,510
Ale tyhle věci můžeme udělat pro všechny uzly.

336
00:24:47,510 --> 00:24:55,790
Ach můj bože.

337
00:24:55,790 --> 00:25:09,540
To je 6, 7, a 3.

338
00:25:09,540 --> 00:25:16,470
Pak můžeme nastavit pobočky v náš strom, můžeme mít 7 -

339
00:25:16,470 --> 00:25:21,650
můžeme mít, že by se jeho levá ukazovat na 3.

340
00:25:21,650 --> 00:25:25,130
Tak jak to uděláme?

341
00:25:25,130 --> 00:25:29,320
[Studenti, nesrozumitelné] >> Jo. Adresa node3,

342
00:25:29,320 --> 00:25:34,170
a pokud jste neměli adresu, pak to prostě nebude sestavovat.

343
00:25:34,170 --> 00:25:38,190
Ale nezapomeňte, že se jedná o ukazatele na příštích uzlů.

344
00:25:38,190 --> 00:25:44,930
Právo by mělo ukazovat na 9,

345
00:25:44,930 --> 00:25:53,330
a 3 by měly ukazovat o právu na 6.

346
00:25:53,330 --> 00:25:58,480
Myslím, že to je vše nastaveno. Jakékoliv připomínky či dotazy?

347
00:25:58,480 --> 00:26:02,060
[Student, nesrozumitelné] Kořen bude 7.

348
00:26:02,060 --> 00:26:08,210
Můžeme jen říct, uzel * ptr =

349
00:26:08,210 --> 00:26:14,160
nebo kořen, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Pro naše účely, budeme jednat s vložkou,

351
00:26:20,730 --> 00:26:25,490
takže budeme chtít napsat funkci vložit do tohoto binárního stromu

352
00:26:25,490 --> 00:26:34,230
a vložka je nevyhnutelně bude volat malloc vytvořit nový uzel pro tohoto stromu.

353
00:26:34,230 --> 00:26:36,590
Takže věci se dostaneme chaotický s tím, že některé uzly

354
00:26:36,590 --> 00:26:38,590
jsou v současné době ve frontě

355
00:26:38,590 --> 00:26:43,680
a ostatní uzly jsou skončíme na haldě, když vložíme je.

356
00:26:43,680 --> 00:26:47,640
To je zcela v pořádku, ale pouze důvod

357
00:26:47,640 --> 00:26:49,600
jsme schopni to udělat na zásobníku

358
00:26:49,600 --> 00:26:51,840
Je tomu tak proto, že je to taková spiklenecká příklad, že víme,

359
00:26:51,840 --> 00:26:56,360
strom je má být konstruována jako 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Pokud bychom neměli, pak bychom neměli malloc na prvním místě.

361
00:27:02,970 --> 00:27:06,160
Jak uvidíme o něco později, měli bychom být malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Právě teď je to naprosto rozumné, aby na zásobníku,

363
00:27:08,570 --> 00:27:14,750
ale pojďme změnit na malloc provádění.

364
00:27:14,750 --> 00:27:17,160
Takže každý z nich se nyní bude něco jako

365
00:27:17,160 --> 00:27:24,240
uzel * node9 = malloc (sizeof (uzel)).

366
00:27:24,240 --> 00:27:28,040
A teď budeme muset udělat naši kontrolu.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Nechtěl jsem, že -

368
00:27:34,010 --> 00:27:40,950
return 1, a pak můžeme udělat node9->, protože teď je to ukazatel,

369
00:27:40,950 --> 00:27:45,300
hodnota = 6, node9-> left = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> P = NULL,

371
00:27:48,930 --> 00:27:51,410
a budeme mít k tomu, že pro každou z těchto uzlů.

372
00:27:51,410 --> 00:27:57,490
Takže místo toho, pojďme dát uvnitř samostatná funkce.

373
00:27:57,490 --> 00:28:00,620
Říkejme tomu uzel * build_node,

374
00:28:00,620 --> 00:28:09,050
a to je poněkud podobný API, které poskytujeme na Huffman kódování.

375
00:28:09,050 --> 00:28:12,730
Dáme vám inicializátor funkce pro strom

376
00:28:12,730 --> 00:28:20,520
a Deconstructor "funkce" pro ty stromy a stejné pro lesy.

377
00:28:20,520 --> 00:28:22,570
>> Takže tady budeme mít inicializátor funkci

378
00:28:22,570 --> 00:28:25,170
jen vybudovat uzel pro nás.

379
00:28:25,170 --> 00:28:29,320
A to bude vypadat skoro přesně takhle.

380
00:28:29,320 --> 00:28:32,230
A já dokonce bude líný a ne změnit název proměnné,

381
00:28:32,230 --> 00:28:34,380
i když node9 nedává smysl.

382
00:28:34,380 --> 00:28:38,610
Oh, myslím, že node9 tyto hodnota by neměla být 6.

383
00:28:38,610 --> 00:28:42,800
Nyní se můžeme vrátit node9.

384
00:28:42,800 --> 00:28:49,550
A tady bychom se měli vrátit null.

385
00:28:49,550 --> 00:28:52,690
Všichni se dohodly na tomto build-a-uzel funkce?

386
00:28:52,690 --> 00:28:59,780
Takže teď můžeme jen volat, že stavět nějaký uzel s danou hodnotou a null ukazateli.

387
00:28:59,780 --> 00:29:09,750
Nyní můžeme nazvat to, že můžeme udělat uzel * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
A pojďme udělat. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
A teď chceme nastavit stejné ukazatele,

391
00:29:39,330 --> 00:29:42,470
s výjimkou teď je všechno už z hlediska ukazatelů

392
00:29:42,470 --> 00:29:48,480
takže již není nutné adresu.

393
00:29:48,480 --> 00:29:56,300
Dobře. Takže to, co je to poslední, co chci dělat?

394
00:29:56,300 --> 00:30:03,850
Tam je pro kontrolu chyb, že jsem to dělat.

395
00:30:03,850 --> 00:30:06,800
Co stavět uzlu návrat?

396
00:30:06,800 --> 00:30:11,660
[Student, nesrozumitelné] >> Jo. Pokud malloc se nezdařilo, bude to vrátí null.

397
00:30:11,660 --> 00:30:16,460
Takže budu líně dát sem místo toho dělal podmínku pro každého.

398
00:30:16,460 --> 00:30:22,320
Pokud (node9 == NULL, nebo - ještě jednodušší,

399
00:30:22,320 --> 00:30:28,020
to je ekvivalentní jen ne-li node9.

400
00:30:28,020 --> 00:30:38,310
Takže pokud není node9, nebo ne node6, nebo ne node3, nebo ne node7, vrátí 1.

401
00:30:38,310 --> 00:30:42,850
Možná bychom měli vytisknout malloc se nezdařilo, nebo tak něco.

402
00:30:42,850 --> 00:30:46,680
[Student] Je false rovná null stejně?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Každá nenulová hodnota je false.

404
00:30:51,290 --> 00:30:53,920
Takže null je nulová hodnota.

405
00:30:53,920 --> 00:30:56,780
Zero je nulová hodnota. False je nulová hodnota.

406
00:30:56,780 --> 00:31:02,130
Jakékoliv - skoro jen 2 nulové hodnoty null a nulové,

407
00:31:02,130 --> 00:31:07,900
false je jen hash definována jako nula.

408
00:31:07,900 --> 00:31:13,030
To platí iv případě, my deklarovat globální proměnné.

409
00:31:13,030 --> 00:31:17,890
Pokud bychom měli uzlu * kořen tady,

410
00:31:17,890 --> 00:31:24,150
pak - pěkná věc, o globálních proměnných je to, že mají vždy počáteční hodnotu.

411
00:31:24,150 --> 00:31:27,500
To není pravda funkcí, jak uvnitř tady,

412
00:31:27,500 --> 00:31:34,870
máme-li, stejně jako, uzel * nebo uzel x.

413
00:31:34,870 --> 00:31:37,380
Nemáme ponětí, co x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
nebo můžeme vytisknout a mohou být libovolné.

415
00:31:40,700 --> 00:31:44,980
To není pravda, globálních proměnných.

416
00:31:44,980 --> 00:31:47,450
Takže uzel root nebo uzel x.

417
00:31:47,450 --> 00:31:53,410
Ve výchozím nastavení, vše, co je globální, není-li výslovně inicializován nějakou hodnotu,

418
00:31:53,410 --> 00:31:57,390
má nulovou hodnotu jako hodnotu.

419
00:31:57,390 --> 00:32:01,150
Tak tady, uzel * root, nemáme explicitně inicializovat k ničemu,

420
00:32:01,150 --> 00:32:06,350
tak jeho výchozí hodnota bude nulový, což je nulová hodnota ukazatelů.

421
00:32:06,350 --> 00:32:11,870
Výchozí hodnota x bude znamenat, že x.value je nulová,

422
00:32:11,870 --> 00:32:14,260
x.left je null, a x.right je null.

423
00:32:14,260 --> 00:32:21,070
Takže, protože to je struktura, budou všechny oblasti struct být nulové hodnoty.

424
00:32:21,070 --> 00:32:24,410
Nemusíme používat, že tady, ačkoli.

425
00:32:24,410 --> 00:32:27,320
[Student] jsou structs jsou jiné než jiné proměnné, a ostatní proměnné jsou

426
00:32:27,320 --> 00:32:31,400
odpadky hodnoty, jsou nuly?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Jiné hodnoty taky. Takže v x, bude x je nula.

428
00:32:36,220 --> 00:32:40,070
Pokud je to v celosvětovém rozsahu, že má počáteční hodnotu. Dobře >>.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Buď počáteční hodnota, kterou dal nebo nula.

430
00:32:48,950 --> 00:32:53,260
Myslím, že se postará o všechno.

431
00:32:53,260 --> 00:32:58,390
>> Dobře. Takže další část otázky ptá,

432
00:32:58,390 --> 00:33:01,260
"Nyní chceme napsat funkci nazvanou obsahuje

433
00:33:01,260 --> 00:33:04,930
s prototypem bool obsahuje int hodnotu. "

434
00:33:04,930 --> 00:33:08,340
Nebudeme dělat bool obsahuje int hodnotu.

435
00:33:08,340 --> 00:33:15,110
Náš prototyp bude vypadat

436
00:33:15,110 --> 00:33:22,380
bool obsahuje (int hodnota.

437
00:33:22,380 --> 00:33:24,490
A pak jsme také chystá předat strom

438
00:33:24,490 --> 00:33:28,870
, že by měl být kontroluje, zda má tuto hodnotu.

439
00:33:28,870 --> 00:33:38,290
Takže uzel * strom). Dobře.

440
00:33:38,290 --> 00:33:44,440
A pak jsme to tak dá nazvat něčím jako,

441
00:33:44,440 --> 00:33:46,090
možná budeme chtít printf nebo tak něco.

442
00:33:46,090 --> 00:33:51,040
Obsahuje 6, náš kořen.

443
00:33:51,040 --> 00:33:54,300
To by mělo vrátit jednu, nebo skutečný,

444
00:33:54,300 --> 00:33:59,390
vzhledem k tomu, obsahuje 5 kořen by se měl vrátit false.

445
00:33:59,390 --> 00:34:02,690
Tak se druhý k provedení tohoto.

446
00:34:02,690 --> 00:34:06,780
Můžete to udělat buď opakované nebo rekurzivně.

447
00:34:06,780 --> 00:34:09,739
Pěkná věc, o tom, jak jsme připravit věci je to, že

448
00:34:09,739 --> 00:34:12,300
to půjčuje sebe k našemu rekurzivní řešení mnohem jednodušší

449
00:34:12,300 --> 00:34:14,719
než globální proměnná způsobem udělal.

450
00:34:14,719 --> 00:34:19,750
Protože pokud budeme prostě muset obsahuje int hodnotu, pak máme žádný způsob, jak recursing dolů podstromy.

451
00:34:19,750 --> 00:34:24,130
Museli bychom mít samostatnou pomocnou funkci, která recurses stanoví podstromy pro nás.

452
00:34:24,130 --> 00:34:29,610
Ale od té doby jsme změnili, aby se strom jako argument,

453
00:34:29,610 --> 00:34:32,760
které by mělo vždy být na prvním místě,

454
00:34:32,760 --> 00:34:35,710
Nyní můžeme recurse snadněji.

455
00:34:35,710 --> 00:34:38,960
Takže iterativní nebo rekurzivní, půjdeme přes oba,

456
00:34:38,960 --> 00:34:46,139
ale uvidíme, že rekurzivní skončí jako bytí docela snadné.

457
00:34:59,140 --> 00:35:02,480
Dobře. Má někdo něco můžeme pracovat s?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Mám iterativní řešení. >> Dobře, iterativní.

459
00:35:12,000 --> 00:35:16,030
Dobře, to vypadá dobře.

460
00:35:16,030 --> 00:35:18,920
Takže, chtějí jít k nám přes to?

461
00:35:18,920 --> 00:35:25,780
[Student] Jasně. Tak jsem nastavit proměnnou TEMP získat první uzel stromu.

462
00:35:25,780 --> 00:35:28,330
A pak jsem prosmyčkovat, zatímco teplota se nerovná null,

463
00:35:28,330 --> 00:35:31,700
takže i když byl ještě na stromě, myslím.

464
00:35:31,700 --> 00:35:35,710
A v případě, že hodnota je rovna hodnotě, že teplota je ukazuje na,

465
00:35:35,710 --> 00:35:37,640
pak vrátí tuto hodnotu.

466
00:35:37,640 --> 00:35:40,210
V opačném případě, kontroluje, zda je to na pravé straně nebo na levé straně.

467
00:35:40,210 --> 00:35:43,400
Pokud jste někdy situaci, kdy už není strom,

468
00:35:43,400 --> 00:35:47,330
pak se vrátí - to ukončí smyčku a vrátí false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Dobře. Takže to vypadá dobře.

470
00:35:52,190 --> 00:35:58,470
Každý, kdo má nějaké připomínky na cokoli?

471
00:35:58,470 --> 00:36:02,400
Nemám korektnost připomínky vůbec.

472
00:36:02,400 --> 00:36:11,020
Jedna věc, kterou můžeme udělat, je to chlap.

473
00:36:11,020 --> 00:36:21,660
Oh, to půjde trochu podlouhlé.

474
00:36:21,660 --> 00:36:33,460
Udělám to vymyslel. Dobře.

475
00:36:33,460 --> 00:36:37,150
>> Každý by si měl uvědomit, jak trojice funguje.

476
00:36:37,150 --> 00:36:38,610
Tam určitě byla kvízů v minulosti

477
00:36:38,610 --> 00:36:41,170
které vám funkci s ternární operátor,

478
00:36:41,170 --> 00:36:45,750
a říkají, to přeložit, udělat něco, co nepoužívá třísložkových.

479
00:36:45,750 --> 00:36:49,140
Takže je to velmi běžný případ, kdy bych si použít ternární,

480
00:36:49,140 --> 00:36:54,610
kde v případě některých podmínka nastavit proměnnou na něco,

481
00:36:54,610 --> 00:36:58,580
else nastavit stejnou proměnnou na něco jiného.

482
00:36:58,580 --> 00:37:03,390
To je něco, co velmi často může být přeměněn na takovéhle věci

483
00:37:03,390 --> 00:37:14,420
kde nastavit tuto proměnnou na toto - nebo, no, je to pravda? Pak je tato, jinak to.

484
00:37:14,420 --> 00:37:18,550
[Student] První z nich je, pokud pravda, ne?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Jo. Jak jsem si vždy přečtěte je, temp rovná hodnotě větší než temp hodnota,

486
00:37:25,570 --> 00:37:30,680
pak to, jinak to. Je to pokládám otázku.

487
00:37:30,680 --> 00:37:35,200
Je to větší? Pak proveďte první věc. Else to druhá věc.

488
00:37:35,200 --> 00:37:41,670
I téměř vždy - dvojtečka, já jen - v mé hlavě, jsem četl, jak jinak.

489
00:37:41,670 --> 00:37:47,180
>> Má někdo rekurzivní řešení?

490
00:37:47,180 --> 00:37:49,670
Dobře. Tenhle budeme - to by již bylo skvělé,

491
00:37:49,670 --> 00:37:53,990
ale budeme dělat ještě lépe.

492
00:37:53,990 --> 00:37:58,720
To je docela hodně stejný přesný nápad.

493
00:37:58,720 --> 00:38:03,060
Je to jen, no, chceš vysvětlovat?

494
00:38:03,060 --> 00:38:08,340
[Student] Jasně. Takže jsme ujistěte se, že strom není null první,

495
00:38:08,340 --> 00:38:13,380
protože pokud je strom null pak to bude vrátit false, protože jsme ho nenašli.

496
00:38:13,380 --> 00:38:19,200
A pokud je to ještě strom, jdeme do - jsme nejprve zkontrolujte, zda je hodnota aktuální uzel.

497
00:38:19,200 --> 00:38:23,740
Vrací true, pokud je, a pokud ne my recurse vlevo nebo vpravo.

498
00:38:23,740 --> 00:38:25,970
Zní to vhodné? >> Mm-hmm. (Dohoda)

499
00:38:25,970 --> 00:38:33,880
Takže si všimnout, že je to téměř - strukturně velmi podobné iterativní řešení.

500
00:38:33,880 --> 00:38:38,200
Je to jen, že místo toho, aby recursing, měli jsme while.

501
00:38:38,200 --> 00:38:40,840
A základní věc tady, kde strom není stejný null

502
00:38:40,840 --> 00:38:44,850
byla podmínka, za níž jsme se rozešli z cyklu while.

503
00:38:44,850 --> 00:38:50,200
Jsou velmi podobné. Ale budeme ještě o krok dále.

504
00:38:50,200 --> 00:38:54,190
Nyní to samé zde.

505
00:38:54,190 --> 00:38:57,680
Oznámení se vracíme stejnou věc v obou těchto tratích,

506
00:38:57,680 --> 00:39:00,220
s výjimkou jeden argument je jiný.

507
00:39:00,220 --> 00:39:07,950
Takže budeme dělat, že do trojice.

508
00:39:07,950 --> 00:39:13,790
Trefil jsem možnost něco, a to dělalo symbol. Dobře.

509
00:39:13,790 --> 00:39:21,720
Takže budeme vracet obsahuje, že.

510
00:39:21,720 --> 00:39:28,030
Začíná to být více řádků, dobře, zvětšovat v něm je.

511
00:39:28,030 --> 00:39:31,060
Obvykle, jako stylistický věc, nemyslím si, že mnoho lidí

512
00:39:31,060 --> 00:39:38,640
dát prostor po šíp, ale myslím, že pokud jste v souladu, to je v pořádku.

513
00:39:38,640 --> 00:39:44,320
Pokud je hodnota nižší než hodnota stromu, chceme recurse na stromě nalevo,

514
00:39:44,320 --> 00:39:53,890
else chceme recurse na stromě vpravo.

515
00:39:53,890 --> 00:39:58,610
Takže to byl první krok učinit z tohoto pohled menší.

516
00:39:58,610 --> 00:40:02,660
Krok dva takže to pohled menší -

517
00:40:02,660 --> 00:40:09,150
můžeme oddělit to do několika řádků.

518
00:40:09,150 --> 00:40:16,500
Dobře. Krok dva, aby to vypadalo menší je tady,

519
00:40:16,500 --> 00:40:25,860
tak návratová hodnota rovna strom hodnotu, nebo obsahuje cokoliv.

520
00:40:25,860 --> 00:40:28,340
>> To je důležitá věc.

521
00:40:28,340 --> 00:40:30,860
Nejsem si jistý, jestli to řekl výslovně ve třídě,

522
00:40:30,860 --> 00:40:34,740
ale je to jen zkrat hodnocení.

523
00:40:34,740 --> 00:40:41,060
Nápad tady je hodnota == strom hodnota.

524
00:40:41,060 --> 00:40:49,960
Pokud je to pravda, pak je to pravda, a my chceme, aby "nebo", že s tím, co je tady.

525
00:40:49,960 --> 00:40:52,520
Takže bez přemýšlení, co je tady,

526
00:40:52,520 --> 00:40:55,070
to, co je celý výraz bude vrátit?

527
00:40:55,070 --> 00:40:59,430
[Student] True? >> Jo, protože pravda o ničem,

528
00:40:59,430 --> 00:41:04,990
or'd - nebo pravda or'd s ničím, je nutně pravdivé.

529
00:41:04,990 --> 00:41:08,150
Takže jakmile vidíme návratovou hodnotu = strom hodnota,

530
00:41:08,150 --> 00:41:10,140
jsme jen tak vrátit true.

531
00:41:10,140 --> 00:41:15,710
Ani jít do recurse dále obsahuje dolů řádek.

532
00:41:15,710 --> 00:41:20,980
Můžeme si vzít tento krok dále.

533
00:41:20,980 --> 00:41:29,490
Návrat strom není stejný neplatné a všechny z toho.

534
00:41:29,490 --> 00:41:32,650
To dělalo to jeden-line funkce.

535
00:41:32,650 --> 00:41:36,790
To je také příklad zkrácené vyhodnocování.

536
00:41:36,790 --> 00:41:40,680
Ale teď je to stejná myšlenka -

537
00:41:40,680 --> 00:41:47,320
místo - takže pokud strom se nerovná null - nebo, dobře,

538
00:41:47,320 --> 00:41:49,580
pokud strom se rovná null, což je těžký případ,

539
00:41:49,580 --> 00:41:54,790
pokud strom rovná null, pak první podmínka bude false.

540
00:41:54,790 --> 00:42:00,550
Takže false AND s ničím se bude co?

541
00:42:00,550 --> 00:42:04,640
[Student] False. Jo >>. To je druhá polovina zkrácené vyhodnocování,

542
00:42:04,640 --> 00:42:10,710
kde, pokud strom není rovno null, pak se nebudeme ani jít -

543
00:42:10,710 --> 00:42:14,930
nebo pokud strom má stejnou hodnotu null, pak nebudeme dělat hodnotu == strom hodnotu.

544
00:42:14,930 --> 00:42:17,010
Jsme jen tak aby se okamžitě vrátil false.

545
00:42:17,010 --> 00:42:20,970
Což je důležité, protože pokud ne zkrat vyhodnotit,

546
00:42:20,970 --> 00:42:25,860
pak pokud strom má stejnou hodnotu null, tato druhá podmínka bude k poruše seg,

547
00:42:25,860 --> 00:42:32,510
protože strom-> hodnota dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Tak to je to. Může to - posun jednou v.

549
00:42:40,490 --> 00:42:44,840
To je velmi běžná věc také, ne dělat toto jeden řádek s tím,

550
00:42:44,840 --> 00:42:49,000
ale je to běžná věc v podmínkách, možná ne tady,

551
00:42:49,000 --> 00:42:59,380
ale pokud (strom! = NULL, a strom-> value == hodnota), dělat cokoliv.

552
00:42:59,380 --> 00:43:01,560
To je velmi běžný stav, kdy místo toho, aby

553
00:43:01,560 --> 00:43:06,770
že se to do dvou IFS, kde jako je strom nulový?

554
00:43:06,770 --> 00:43:11,780
Dobře, to není null, takže teď je strom hodnota rovna hodnotě? Udělej to.

555
00:43:11,780 --> 00:43:17,300
Namísto toho, že tato podmínka, bude to nikdy seg poruchu

556
00:43:17,300 --> 00:43:21,220
protože to vypukne, pokud se to stane, že je null.

557
00:43:21,220 --> 00:43:24,000
No, myslím, že pokud váš strom je zcela neplatný ukazatel, to může ještě seg poruchu,

558
00:43:24,000 --> 00:43:26,620
ale nemůže seg poruchu, pokud strom je null.

559
00:43:26,620 --> 00:43:32,900
Kdyby to bylo null, by to zlomit, než jste někdy dereferenced ukazatel na prvním místě.

560
00:43:32,900 --> 00:43:35,000
[Student] Je to tzv. líné vyhodnocování?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Líné vyhodnocování je samostatná věc.

562
00:43:40,770 --> 00:43:49,880
Líné vyhodnocování je, jako byste požádat o hodnotu,

563
00:43:49,880 --> 00:43:54,270
ptáš vypočítat hodnotu, druh, ale nemusíte ji hned.

564
00:43:54,270 --> 00:43:59,040
Takže dokud se skutečně potřebovat, není hodnocena.

565
00:43:59,040 --> 00:44:03,920
To není úplně totéž, ale v Huffmanovo Pset,

566
00:44:03,920 --> 00:44:06,520
se říká, že jsme "líně" psát.

567
00:44:06,520 --> 00:44:08,670
Důvodem, proč děláme to proto, že jsme vlastně vyrovnávací paměti write -

568
00:44:08,670 --> 00:44:11,820
Nechceme psát jednotlivé bity v době,

569
00:44:11,820 --> 00:44:15,450
nebo jednotlivé byty v době, jsme místo toho chce dostat kus bajtů.

570
00:44:15,450 --> 00:44:19,270
Pak, jakmile budeme mít kus bajtů, pak budeme psát to.

571
00:44:19,270 --> 00:44:22,640
I když jste požádat ji psát - a fwrite a fread to stejný druh věci.

572
00:44:22,640 --> 00:44:26,260
Oni bufferu vaše čte a píše.

573
00:44:26,260 --> 00:44:31,610
I když se zeptáte to psát hned, to asi nebude.

574
00:44:31,610 --> 00:44:34,540
A můžete si být jisti, že se věci mají být zapsány

575
00:44:34,540 --> 00:44:37,540
dokud nezavoláte hfclose nebo co to je,

576
00:44:37,540 --> 00:44:39,620
který pak říká, jo, já Zavírám svůj soubor,

577
00:44:39,620 --> 00:44:43,450
to znamená, že jsem radši napsat vše, co jsem nenapsal ještě.

578
00:44:43,450 --> 00:44:45,770
To není třeba psát všechno ven

579
00:44:45,770 --> 00:44:49,010
dokud se při zavírání souboru, a pak je třeba.

580
00:44:49,010 --> 00:44:56,220
Takže to je právě to, co líný - to počká, dokud se to musí stát.

581
00:44:56,220 --> 00:44:59,990
Tento - se 51 a přejdete do něj podrobněji,

582
00:44:59,990 --> 00:45:05,470
protože OCaml a všechno v 51, vše je rekurze.

583
00:45:05,470 --> 00:45:08,890
Nejsou k dispozici žádné iterativní řešení, v podstatě.

584
00:45:08,890 --> 00:45:11,550
Všechno je rekurze, a líné vyhodnocování

585
00:45:11,550 --> 00:45:14,790
bude důležité pro mnoho okolností

586
00:45:14,790 --> 00:45:19,920
kde, pokud jste si líně vyhodnocovat, znamenalo by to -

587
00:45:19,920 --> 00:45:24,760
Příkladem je proudy, které jsou nekonečně dlouho.

588
00:45:24,760 --> 00:45:30,990
Teoreticky, můžete přemýšlet o přirozených čísel jako proud 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Takže líně vyhodnocené věci jsou v pořádku.

590
00:45:33,090 --> 00:45:37,210
Když řeknu, že chci desáté číslo, pak mohu hodnotit až na desáté číslo.

591
00:45:37,210 --> 00:45:40,300
Pokud chci sté číslo, pak mohu hodnotit až po sté číslo.

592
00:45:40,300 --> 00:45:46,290
Bez líné vyhodnocování, pak to bude snažit zhodnotit všechna čísla okamžitě.

593
00:45:46,290 --> 00:45:50,000
Jste hodnocení nekonečně mnoho čísel, a to prostě není možné.

594
00:45:50,000 --> 00:45:52,080
Takže existuje mnoho okolností, kdy líné vyhodnocování

595
00:45:52,080 --> 00:45:57,840
je jen nezbytné k získání věci do práce.

596
00:45:57,840 --> 00:46:05,260
>> Nyní chceme psát vložku, kde vložka bude

597
00:46:05,260 --> 00:46:08,430
Podobně změna v jeho definici.

598
00:46:08,430 --> 00:46:10,470
Takže teď je to bool vložka (int value).

599
00:46:10,470 --> 00:46:23,850
Budeme změnit na bool vložky (int hodnota, uzel * strom).

600
00:46:23,850 --> 00:46:29,120
Jsme vlastně bude měnit, že opět v trochu, uvidíme proč.

601
00:46:29,120 --> 00:46:32,210
A pojďme přesunout build_node, jen pro kruci to,

602
00:46:32,210 --> 00:46:36,730
nad vložte takže nemáme psát funkce prototyp.

603
00:46:36,730 --> 00:46:42,450
Což je náznak, že budete používat build_node v letáku.

604
00:46:42,450 --> 00:46:49,590
Dobře. Take minutu za to.

605
00:46:49,590 --> 00:46:52,130
Myslím, že jsem zachránil revizi, pokud chcete vytáhnout z toho,

606
00:46:52,130 --> 00:47:00,240
nebo alespoň, jsem teď.

607
00:47:00,240 --> 00:47:04,190
Chtěl jsem mírný přestávku na přemýšlení o logice vložky,

608
00:47:04,190 --> 00:47:08,750
Pokud nemůžete myslet na to.

609
00:47:08,750 --> 00:47:12,860
V podstatě, budete jen někdy vkládání na listy.

610
00:47:12,860 --> 00:47:18,640
Stejně jako, když jsem vložit 1, pak jsem nevyhnutelně bude vkládání 1 -

611
00:47:18,640 --> 00:47:21,820
Budu se změní na černou - Budu se vloží 1 sem.

612
00:47:21,820 --> 00:47:28,070
Nebo když jsem vložit 4, chci se vloží 4 sem.

613
00:47:28,070 --> 00:47:32,180
Takže bez ohledu na to, co děláte, budete se vloží na list.

614
00:47:32,180 --> 00:47:36,130
Jediné, co musíte udělat, je iteraci kácení, až se dostanete do uzlu

615
00:47:36,130 --> 00:47:40,890
které by měly být v uzlu rodič, nového uzlu rodič,

616
00:47:40,890 --> 00:47:44,560
a potom změnit jeho levé nebo pravé myši, v závislosti na tom, zda

617
00:47:44,560 --> 00:47:47,060
to je větší než nebo menší, než je aktuální uzel.

618
00:47:47,060 --> 00:47:51,180
Změna tento ukazatel poukázat na svého nového uzlu.

619
00:47:51,180 --> 00:48:05,490
Takže iterovat kácení, aby se list bod do nového uzlu.

620
00:48:05,490 --> 00:48:09,810
Také si myslím, že o tom, proč zakazuje typ situace před,

621
00:48:09,810 --> 00:48:17,990
kde jsem postavil binární strom, kde to bylo správné

622
00:48:17,990 --> 00:48:19,920
pokud jste jen podíval na jednoho uzlu,

623
00:48:19,920 --> 00:48:24,830
ale 9 byl na levé straně 7, pokud si zopakovali úplně dolů.

624
00:48:24,830 --> 00:48:29,770
Tak to je možné v tomto scénáři, protože -

625
00:48:29,770 --> 00:48:32,530
přemýšlet o vkládání 9 nebo něco, na prvním uzlu,

626
00:48:32,530 --> 00:48:35,350
Jdu vidět 7 a já jsem jen jít doprava.

627
00:48:35,350 --> 00:48:38,490
Takže bez ohledu na to, co mám dělat, když mám vložením tím, že půjdete na listu,

628
00:48:38,490 --> 00:48:40,790
a k listu pomocí vhodného algoritmu,

629
00:48:40,790 --> 00:48:43,130
to bude pro mě nemožné vložit 9 nalevo 7

630
00:48:43,130 --> 00:48:48,250
protože jakmile jsem narazila 7 jsem jít doprava.

631
00:48:59,740 --> 00:49:02,070
Má někdo něco začít?

632
00:49:02,070 --> 00:49:05,480
[Student] já. Jistě >>.

633
00:49:05,480 --> 00:49:09,200
[Student, nesrozumitelným]

634
00:49:09,200 --> 00:49:14,390
[Ostatní student, nesrozumitelným]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Je to ocenil. Dobře. Chcete vysvětlit?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Protože víme, že jsme vkládání

637
00:49:20,690 --> 00:49:24,060
nové uzly na konci stromu,

638
00:49:24,060 --> 00:49:28,070
I prosmyčkovat stromu iterativně

639
00:49:28,070 --> 00:49:31,360
dokud jsem se nedostal k uzlu, která ukazovala na nulu.

640
00:49:31,360 --> 00:49:34,220
A pak jsem se rozhodl dát ho buď na pravé straně nebo na levé straně

641
00:49:34,220 --> 00:49:37,420
tohoto práva využívají proměnné, to mi řekl, kam to dát.

642
00:49:37,420 --> 00:49:41,850
A pak, v podstatě jsem jen dělal, že poslední -

643
00:49:41,850 --> 00:49:47,520
že teplota uzel bod na nový uzel, který byl vytvářeného

644
00:49:47,520 --> 00:49:50,770
buď na levé straně, nebo na pravé straně, v závislosti na tom, co je hodnota pravý byl.

645
00:49:50,770 --> 00:49:56,530
Nakonec jsem nastavit nový uzel hodnoty na hodnotu jeho testování.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Dobře, takže vidím jeden problém tady.

647
00:49:59,550 --> 00:50:02,050
To je jako 95% cestě tam.

648
00:50:02,050 --> 00:50:07,550
Ten problém, který vidím, dobře, někdo jiný vidět problém?

649
00:50:07,550 --> 00:50:18,400
Co je okolnost, pod kterou vymanit se z smyčky?

650
00:50:18,400 --> 00:50:22,100
[Student] Pokud teplota je null? Jo >>. Tak jak se vymanit ze smyčky, je-li teplota je null.

651
00:50:22,100 --> 00:50:30,220
Ale co mám dělat tady?

652
00:50:30,220 --> 00:50:35,410
I dereference temp, který je nevyhnutelně null.

653
00:50:35,410 --> 00:50:39,840
Takže další věc, kterou musíte udělat, je nejen sledovat, dokud teplota je null,

654
00:50:39,840 --> 00:50:45,590
Chcete-li sledovat rodiče za všech okolností.

655
00:50:45,590 --> 00:50:52,190
Chceme také, aby uzel * rodiče, myslím, že můžeme mít, že při nulovém na prvním místě.

656
00:50:52,190 --> 00:50:55,480
To bude mít podivné chování pro kořen stromu,

657
00:50:55,480 --> 00:50:59,210
ale k tomu se dostaneme.

658
00:50:59,210 --> 00:51:03,950
Pokud je hodnota vyšší než cokoliv, pak temp = temp pravdu.

659
00:51:03,950 --> 00:51:07,910
Ale předtím, než to uděláme, rodič = temp.

660
00:51:07,910 --> 00:51:14,500
Nebo se rodiče vždycky stejné teploty? Je to tak?

661
00:51:14,500 --> 00:51:19,560
Pokud teplota není null, pak budu pohybovat dolů, bez ohledu na to,

662
00:51:19,560 --> 00:51:24,030
do uzlu, pro který temp je rodič.

663
00:51:24,030 --> 00:51:27,500
Takže rodiče to bude temp, a pak jsem se přesunout teplota dolů.

664
00:51:27,500 --> 00:51:32,410
Nyní teplota je null, ale rodiče poukazuje na rodiče na věc, která je null.

665
00:51:32,410 --> 00:51:39,110
Takže tady dole, nechci, aby na pravou míru se rovná 1.

666
00:51:39,110 --> 00:51:41,300
Tak jsem se pohyboval napravo, takže pokud P = 1,

667
00:51:41,300 --> 00:51:45,130
a myslím, že budete také chtít udělat -

668
00:51:45,130 --> 00:51:48,530
pokud přesunete vlevo, kterou chcete nastavit přímo rovna 0.

669
00:51:48,530 --> 00:51:55,950
Anebo, pokud jste někdy posune doprava.

670
00:51:55,950 --> 00:51:58,590
Takže vpravo = 0. Pokud vpravo = 1,

671
00:51:58,590 --> 00:52:04,260
Nyní chceme, aby se mateřský správný ukazatel newnode,

672
00:52:04,260 --> 00:52:08,520
jinak bychom chtít, aby mateřské levé ukazatel newnode.

673
00:52:08,520 --> 00:52:16,850
Otázky týkající se, že?

674
00:52:16,850 --> 00:52:24,880
Dobře. Tak tohle je způsob, jak - no, vlastně, místo toho, co děláme,

675
00:52:24,880 --> 00:52:29,630
jsme napůl očekával, můžete použít build_node.

676
00:52:29,630 --> 00:52:40,450
A pak, když newnode rovná null, vrátí false.

677
00:52:40,450 --> 00:52:44,170
To je to. Nyní, to je to, co jsme očekávali, abys udělal.

678
00:52:44,170 --> 00:52:47,690
>> To je to, co zaměstnanci řešení dělat.

679
00:52:47,690 --> 00:52:52,360
Nesouhlasím s tím, jak se "správným" způsobem bude o tom

680
00:52:52,360 --> 00:52:57,820
ale to je naprosto v pořádku a že to bude fungovat.

681
00:52:57,820 --> 00:53:02,840
Jedna věc, která je trochu divné je teď

682
00:53:02,840 --> 00:53:08,310
jestliže strom začíná za neplatné, míjíme v nulové stromu.

683
00:53:08,310 --> 00:53:12,650
Myslím, že to záleží na tom, jak definovat chování projde v nulové stromu.

684
00:53:12,650 --> 00:53:15,490
Řekl bych, že pokud omdlíte v nulové stromu,

685
00:53:15,490 --> 00:53:17,520
pak vložením hodnoty do nuly stromu

686
00:53:17,520 --> 00:53:23,030
měl prostě vrátit strom, kde jedinou hodnotou je, že jeden uzel.

687
00:53:23,030 --> 00:53:25,830
Lidé s tím souhlasíte? Dalo by se, pokud byste chtěli,

688
00:53:25,830 --> 00:53:28,050
pokud předáte null stromu

689
00:53:28,050 --> 00:53:31,320
a chcete vložit hodnotu do něj, vrátí false.

690
00:53:31,320 --> 00:53:33,830
Je na vás, abyste definovat, že.

691
00:53:33,830 --> 00:53:38,320
Chcete-li udělat první věc, kterou jsem řekl, a pak -

692
00:53:38,320 --> 00:53:40,720
dobře, budete mít potíže dělá, že, protože

693
00:53:40,720 --> 00:53:44,090
že by bylo jednodušší, kdyby jsme měli globální ukazatel na věc,

694
00:53:44,090 --> 00:53:48,570
ale nemáme, takže pokud strom je null, není nic, co může dělat, že.

695
00:53:48,570 --> 00:53:50,960
Můžeme jen vrátí false.

696
00:53:50,960 --> 00:53:52,840
Takže budu měnit vložku.

697
00:53:52,840 --> 00:53:56,540
My technicky mohl jen změnit toto právo tady,

698
00:53:56,540 --> 00:53:58,400
jak to iterace nad věcmi,

699
00:53:58,400 --> 00:54:04,530
ale budu měnit vložku, aby se uzel ** strom.

700
00:54:04,530 --> 00:54:07,510
Dvoulůžkové ukazatele.

701
00:54:07,510 --> 00:54:09,710
Co to znamená?

702
00:54:09,710 --> 00:54:12,330
Místo zabývání se ukazatelů na uzly,

703
00:54:12,330 --> 00:54:16,690
věc budu se manipulovat, je tento ukazatel.

704
00:54:16,690 --> 00:54:18,790
Budu se manipulovat tento ukazatel.

705
00:54:18,790 --> 00:54:21,770
Budu se manipulovat ukazatele přímo.

706
00:54:21,770 --> 00:54:25,760
To dává smysl, protože, myslím, že o tom se -

707
00:54:25,760 --> 00:54:33,340
dobře, teď tento bodů na hodnotu null.

708
00:54:33,340 --> 00:54:38,130
To, co chci udělat, je manipulovat tento ukazatel poukázat na NOT NULL.

709
00:54:38,130 --> 00:54:40,970
Chci, aby to poukázat na mého nového uzlu.

710
00:54:40,970 --> 00:54:44,870
Kdybych jen sledovat ukazatele na mých ukazatelů,

711
00:54:44,870 --> 00:54:47,840
pak jsem nemusíte sledovat mateřské ukazatel.

712
00:54:47,840 --> 00:54:52,640
Můžu jen sledovat, zda ukazatel ukazuje na null,

713
00:54:52,640 --> 00:54:54,580
a pokud ukazatel ukazuje na null,

714
00:54:54,580 --> 00:54:57,370
změnit, aby ukazoval na uzel chci.

715
00:54:57,370 --> 00:55:00,070
A mohu změnit to, protože mám ukazatel na ukazatel.

716
00:55:00,070 --> 00:55:02,040
Pojďme se podívat právě teď.

717
00:55:02,040 --> 00:55:05,470
Můžete si skutečně udělat rekurzivně docela snadno.

718
00:55:05,470 --> 00:55:08,080
Chceme udělat?

719
00:55:08,080 --> 00:55:10,980
Ano, máme.

720
00:55:10,980 --> 00:55:16,790
>> Pojďme se podívat, to rekurzivně.

721
00:55:16,790 --> 00:55:24,070
Za prvé, to, co je naše základna případ bude?

722
00:55:24,070 --> 00:55:29,140
Téměř vždy náš základní scénář, ale ve skutečnosti, to je trochu složitější.

723
00:55:29,140 --> 00:55:34,370
První věcí, první, if (tree == NULL)

724
00:55:34,370 --> 00:55:37,550
Myslím, že jsme jen tak vrátit false.

725
00:55:37,550 --> 00:55:40,460
To se liší od svého stromu bytí null.

726
00:55:40,460 --> 00:55:44,510
To je ukazatel na vašem kořenovém ukazatele prozatím null

727
00:55:44,510 --> 00:55:48,360
což znamená, že kořenová ukazatel neexistuje.

728
00:55:48,360 --> 00:55:52,390
Takže tady dole, když to udělám

729
00:55:52,390 --> 00:55:55,760
uzel * - řekněme znovu to.

730
00:55:55,760 --> 00:55:58,960
Node * root = NULL,

731
00:55:58,960 --> 00:56:00,730
a pak budu volat vložky tím, že dělá něco jako,

732
00:56:00,730 --> 00:56:04,540
vložit do 4 & kořene.

733
00:56:04,540 --> 00:56:06,560
Tak a kořen, pokud je kořen uzel *

734
00:56:06,560 --> 00:56:11,170
pak a kořen bude uzlu **.

735
00:56:11,170 --> 00:56:15,120
To je platné. V tomto případě, strom, tady,

736
00:56:15,120 --> 00:56:20,120
Strom není null - nebo vložka.

737
00:56:20,120 --> 00:56:24,630
Tady. Strom není nula; * strom je nulový, což je v pořádku

738
00:56:24,630 --> 00:56:26,680
protože pokud * strom je null, pak jsem si s ním manipulovat

739
00:56:26,680 --> 00:56:29,210
se nyní ukazují na to, co chci, aby to odkazovat.

740
00:56:29,210 --> 00:56:34,750
Ale pokud strom je null, to znamená, že jsem sem přijel a řekl null.

741
00:56:34,750 --> 00:56:42,710
To nedává smysl. Nemůžu nic dělat s tím.

742
00:56:42,710 --> 00:56:45,540
Pokud je strom null, vrátí false.

743
00:56:45,540 --> 00:56:48,220
Takže jsem v podstatě už řekl, co naše skutečná základna případ je.

744
00:56:48,220 --> 00:56:50,580
A co je to, že bude?

745
00:56:50,580 --> 00:56:55,030
[Student, nesrozumitelným]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ano. Takže pokud (* tree == NULL).

747
00:57:00,000 --> 00:57:04,520
To se týká případu sem

748
00:57:04,520 --> 00:57:09,640
kde, pokud má červený ukazatel je ukazatel jsem se zaměřil na,

749
00:57:09,640 --> 00:57:12,960
tak, jako bych se zaměřil na tohoto ukazatele, teď jsem se zaměřil na tomto ukazateli.

750
00:57:12,960 --> 00:57:15,150
Teď jsem se zaměřil na tomto ukazateli.

751
00:57:15,150 --> 00:57:18,160
Takže pokud má červený ukazatel, který je můj uzel **,

752
00:57:18,160 --> 00:57:22,880
je vždy - pokud *, můj červený ukazatel, je stále null,

753
00:57:22,880 --> 00:57:28,470
to znamená, že jsem v případě, kdy jsem se zaměřením na ukazatel, který ukazuje -

754
00:57:28,470 --> 00:57:32,530
to je ukazatel, který patří k listu.

755
00:57:32,530 --> 00:57:41,090
Chci změnit tento ukazatel poukázat na můj nový uzel.

756
00:57:41,090 --> 00:57:45,230
Vraťte se sem.

757
00:57:45,230 --> 00:57:56,490
Můj newnode bude jen uzel * n = build_node (hodnota)

758
00:57:56,490 --> 00:58:07,300
pak n, pokud n = NULL, vrátí false.

759
00:58:07,300 --> 00:58:12,600
Else chceme změnit to, co se ukazatel je v současné době ukazuje na

760
00:58:12,600 --> 00:58:17,830
se nyní ukazují na naší nově postavené uzlu.

761
00:58:17,830 --> 00:58:20,280
Můžeme skutečně udělat tady.

762
00:58:20,280 --> 00:58:30,660
Místo toho řekl n, říkáme, * tree = pokud * stromu.

763
00:58:30,660 --> 00:58:35,450
Všichni pochopili, že? Že jednání s ukazateli na ukazatele,

764
00:58:35,450 --> 00:58:40,750
můžeme změnit Null ukazatele poukázat na věci, které chceme, aby odkazovat.

765
00:58:40,750 --> 00:58:42,820
To je náš základní scénář.

766
00:58:42,820 --> 00:58:45,740
>> Nyní náš recidivy, nebo naše rekurze,

767
00:58:45,740 --> 00:58:51,430
bude velmi podobný všem ostatním rekurze jsme dělali.

768
00:58:51,430 --> 00:58:55,830
Budeme chtít vložit hodnotu,

769
00:58:55,830 --> 00:58:59,040
a teď budu používat ternární znovu, ale to, co je naše podmínka bude?

770
00:58:59,040 --> 00:59:05,180
Co je to, co hledáme rozhodnout, zda chceme jít doleva nebo doprava?

771
00:59:05,180 --> 00:59:07,760
Pojďme to v samostatných krocích.

772
00:59:07,760 --> 00:59:18,850
Pokud (hodnota <), co?

773
00:59:18,850 --> 00:59:23,200
[Student] Strom je hodnota?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Takže nezapomeňte, že jsem v současné době -

775
00:59:27,490 --> 00:59:31,260
[Studenti, nesrozumitelné]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Jo, tak tady, řekněme, že tato zelená šipka

777
00:59:34,140 --> 00:59:39,050
je příkladem toho, co je v současné době strom, je ukazatel na tento ukazatel.

778
00:59:39,050 --> 00:59:46,610
Takže to znamená, že jsem ukazatel na ukazatel na 3.

779
00:59:46,610 --> 00:59:48,800
The dereference dvakrát znělo to dobře.

780
00:59:48,800 --> 00:59:51,010
Co mám - jak to mám udělat, že?

781
00:59:51,010 --> 00:59:53,210
[Student] dereference jednou, a potom proveďte arrow takhle?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Tak (* strom) je dereference jednou, -> hodnota

783
00:59:58,420 --> 01:00:05,960
se chystá dát mi hodnotu uzlu, který jsem nepřímo ukazuje.

784
01:00:05,960 --> 01:00:11,980
Tak jsem si také napsat, že ** tree.value pokud si to přejete.

785
01:00:11,980 --> 01:00:18,490
Buď funguje.

786
01:00:18,490 --> 01:00:26,190
Pokud tomu tak je, pak chci zavolat vložit s hodnotou.

787
01:00:26,190 --> 01:00:32,590
A to, co je moje aktualizován uzel ** bude?

788
01:00:32,590 --> 01:00:39,440
Chci jít doleva, takže ** tree.left bude moje levá.

789
01:00:39,440 --> 01:00:41,900
A chci, aby ukazatel na té věci

790
01:00:41,900 --> 01:00:44,930
tak, že v případě, že levá nakonec je nulový ukazatel,

791
01:00:44,930 --> 01:00:48,360
Já ji upravit, aby ukazoval na můj nový uzel.

792
01:00:48,360 --> 01:00:51,460
>> A druhý případ může být velmi podobné.

793
01:00:51,460 --> 01:00:55,600
Pojďme vlastně udělat, aby mé trojice právě teď.

794
01:00:55,600 --> 01:01:04,480
Vložte hodnotu, pokud hodnota <(** strom). Hodnotu.

795
01:01:04,480 --> 01:01:11,040
Pak chceme aktualizovat naše ** doleva,

796
01:01:11,040 --> 01:01:17,030
else chceme aktualizovat naše ** vpravo.

797
01:01:17,030 --> 01:01:22,540
[Student] Znamená to, že se ukazatel na ukazatel?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Nezapomeňte, že - ** tree.right je uzel hvězda.

799
01:01:30,940 --> 01:01:35,040
[Student, nesrozumitelné] >> Jo.

800
01:01:35,040 --> 01:01:41,140
** Tree.right je jako tento ukazatel, nebo tak něco.

801
01:01:41,140 --> 01:01:45,140
Takže tím, že ukazatel na to, že mi dává to, co chci

802
01:01:45,140 --> 01:01:50,090
o ukazatel na toho chlapa.

803
01:01:50,090 --> 01:01:54,260
[Student] Mohli bychom jít znovu, proč jsme pomocí dvou ukazatelů?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Jo. Takže - ne, můžete, a že řešení před

805
01:01:58,220 --> 01:02:04,540
Byl to způsob, jak to udělat, aniž by dělali dva ukazatele.

806
01:02:04,540 --> 01:02:08,740
Musíte být schopni pochopit pomocí dvou ukazatelů,

807
01:02:08,740 --> 01:02:11,660
a to je čistší řešení.

808
01:02:11,660 --> 01:02:16,090
Všimněte si také, že to, co se stane, když můj strom -

809
01:02:16,090 --> 01:02:24,480
co se stane, když moje kořenem byly null? Co se stane, když udělám tenhle případ tady?

810
01:02:24,480 --> 01:02:30,540
Takže uzel * root = NULL, vložte 4 do & kořene.

811
01:02:30,540 --> 01:02:35,110
Co je kořen bude po tomhle?

812
01:02:35,110 --> 01:02:37,470
[Student, nesrozumitelné] >> Jo.

813
01:02:37,470 --> 01:02:41,710
Root hodnota bude 4.

814
01:02:41,710 --> 01:02:45,510
Root vlevo bude null, kořen právo bude null.

815
01:02:45,510 --> 01:02:49,490
V případě, kdy se nepřešel kořeny adresou,

816
01:02:49,490 --> 01:02:52,490
jsme nemohli měnit kořen.

817
01:02:52,490 --> 01:02:56,020
V případě, že se strom - kde root je nulový,

818
01:02:56,020 --> 01:02:58,410
jsme prostě museli vrátit false. Není nic, co bychom mohli udělat.

819
01:02:58,410 --> 01:03:01,520
Nemůžeme vložit uzel do prázdné stromu.

820
01:03:01,520 --> 01:03:06,810
Ale teď můžeme, jsme prostě udělat prázdný strom do jednoho uzlu stromu.

821
01:03:06,810 --> 01:03:13,400
Který je obvykle očekávaným způsobem, že by to mělo fungovat.

822
01:03:13,400 --> 01:03:21,610
>> Dále, což je podstatně kratší než

823
01:03:21,610 --> 01:03:26,240
také udržování přehledu o rodiče, a tak budete iterovat úplně dolů.

824
01:03:26,240 --> 01:03:30,140
Teď mám rodiče, a já jsem se svou mateřskou vpravo ukazatel na cokoliv.

825
01:03:30,140 --> 01:03:35,640
Místo toho, jestli jsme to udělali iterativně, bylo by to stejné nápad s smyčky while.

826
01:03:35,640 --> 01:03:38,100
Ale místo toho, aby se museli vypořádat s mým mateřským ukazatelem,

827
01:03:38,100 --> 01:03:40,600
místo můj současný ukazatel by věc

828
01:03:40,600 --> 01:03:43,790
že jsem se přímo mění na bod na můj nový uzel.

829
01:03:43,790 --> 01:03:46,090
Nemám se zabývat, zda je to ukázal na levé straně.

830
01:03:46,090 --> 01:03:48,810
Nemám se zabývat, zda je to směřující vpravo.

831
01:03:48,810 --> 01:04:00,860
Je to jen, co tento ukazatel je, budu ji nastavit, aby ukazoval na můj nový uzel.

832
01:04:00,860 --> 01:04:05,740
Všichni pochopili, jak to funguje?

833
01:04:05,740 --> 01:04:09,460
Pokud ne, proč to chceme udělat takhle,

834
01:04:09,460 --> 01:04:14,920
ale aspoň, že to funguje jako řešení?

835
01:04:14,920 --> 01:04:17,110
[Student] Kde se vrátíme pravda?

836
01:04:17,110 --> 01:04:21,550
[Bowden] To je asi tady.

837
01:04:21,550 --> 01:04:26,690
Pokud jsme správně vložit, vrátit true.

838
01:04:26,690 --> 01:04:32,010
Else, tady dole budeme chtít vrátit bez ohledu vkládání výnosy.

839
01:04:32,010 --> 01:04:35,950
>> A co je zvláštního na tomto rekurzivní funkce?

840
01:04:35,950 --> 01:04:43,010
Je to tail rekurzivní, tak dlouho, jak jsme kompilovat s nějakou optimalizací,

841
01:04:43,010 --> 01:04:48,060
bude si to uvědomit a nikdy se přetečení zásobníku z toho,

842
01:04:48,060 --> 01:04:53,230
i když náš strom má výšku 10.000 nebo 10 milionů.

843
01:04:53,230 --> 01:04:55,630
[Student, nesrozumitelným]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Myslím, že to dělá na Dash - nebo co úroveň optimalizace

845
01:05:00,310 --> 01:05:03,820
je vyžadováno pro koncové rekurze má být uznáno.

846
01:05:03,820 --> 01:05:09,350
Myslím, že to uznává - GCC a zvonění

847
01:05:09,350 --> 01:05:12,610
také mají různý význam pro jejich optimalizaci úrovně.

848
01:05:12,610 --> 01:05:17,870
Chci říct, že to DashO 2, pro jistotu, že budou uznávat rekurze ocasu.

849
01:05:17,870 --> 01:05:27,880
Ale my - můžete postavit jako například Fibonocci nebo tak něco.

850
01:05:27,880 --> 01:05:30,030
Není to snadné otestovat s tím, protože je těžké postavit

851
01:05:30,030 --> 01:05:32,600
binární strom, který je tak velký.

852
01:05:32,600 --> 01:05:37,140
Ale jo, myslím, že je to DashO 2, že

853
01:05:37,140 --> 01:05:40,580
pokud při kompilaci s DashO 2, bude to vypadat pro koncové rekurze

854
01:05:40,580 --> 01:05:54,030
a optimalizovat to ven.

855
01:05:54,030 --> 01:05:58,190
Pojďme zpět k - vložit to doslova poslední věc, kterou potřebuje.

856
01:05:58,190 --> 01:06:04,900
Pojďme se vrátit k vložky sem

857
01:06:04,900 --> 01:06:07,840
kde budeme dělat stejnou myšlenku.

858
01:06:07,840 --> 01:06:14,340
To bude mít stále nedostatek, že není schopen zcela zvládnout

859
01:06:14,340 --> 01:06:17,940
když kořenový sám je nulový, nebo přes vstup je nulový,

860
01:06:17,940 --> 01:06:20,060
ale místo toho se zabývá mateřské ukazatel,

861
01:06:20,060 --> 01:06:27,430
Pojďme používat stejnou logiku vedení ukazatelů na ukazatele.

862
01:06:27,430 --> 01:06:35,580
Pokud zde budeme držet naše uzel ** teď,

863
01:06:35,580 --> 01:06:37,860
a nepotřebujeme sledovat přímo už,

864
01:06:37,860 --> 01:06:47,190
ale uzel ** cur = & tree.

865
01:06:47,190 --> 01:06:54,800
A teď naše, zatímco smyčka bude zároveň * teď se nerovná null.

866
01:06:54,800 --> 01:07:00,270
Nemusíte sledovat rodičů už.

867
01:07:00,270 --> 01:07:04,180
Nemusíte sledovat pomocí levé a pravé.

868
01:07:04,180 --> 01:07:10,190
A já budu říkat temp, protože jsme již používáte temp.

869
01:07:10,190 --> 01:07:17,200
Dobře. Takže pokud (hodnota> * temp),

870
01:07:17,200 --> 01:07:24,010
pak a (* temp) -> P

871
01:07:24,010 --> 01:07:29,250
else temp = & (* temp) -> vlevo.

872
01:07:29,250 --> 01:07:32,730
A teď, v tomto okamžiku, po tomto cyklu while,

873
01:07:32,730 --> 01:07:36,380
Jen jsem to proto, že je to možná jednodušší přemýšlet o opakované, než rekurzivně,

874
01:07:36,380 --> 01:07:39,010
ale po tomto cyklu while,

875
01:07:39,010 --> 01:07:43,820
* Teplota je ukazatel chceme změnit.

876
01:07:43,820 --> 01:07:48,960
>> Než jsme měli rodiče, a chtěli jsme změnit buď mateřskou doleva nebo rodiče vpravo,

877
01:07:48,960 --> 01:07:51,310
ale pokud chceme změnit mateřské právo,

878
01:07:51,310 --> 01:07:54,550
pak * teplota je rodič pravdu, a můžeme změnit přímo.

879
01:07:54,550 --> 01:08:05,860
Takže tady dole, můžeme udělat * temp = newnode, a to je vše.

880
01:08:05,860 --> 01:08:09,540
Takže upozornění, všechno, co jsme dělali v to uzavřít řádky kódu.

881
01:08:09,540 --> 01:08:14,770
Aby bylo možné sledovat mateřské ve všech, který je další úsilí.

882
01:08:14,770 --> 01:08:18,689
Zde, pokud se jen sledovat ukazatel na ukazatel,

883
01:08:18,689 --> 01:08:22,990
a dokonce i kdybychom chtěli zbavit všech těchto složených závorek teď,

884
01:08:22,990 --> 01:08:27,170
aby to vypadalo kratší.

885
01:08:27,170 --> 01:08:32,529
To je nyní přesně stejné řešení,

886
01:08:32,529 --> 01:08:38,210
ale méně řádků kódu.

887
01:08:38,210 --> 01:08:41,229
Jakmile začnete rozpoznávat to jako platný řešení,

888
01:08:41,229 --> 01:08:43,529
je to také jednodušší uvažovat o než jako, jo,

889
01:08:43,529 --> 01:08:45,779
proč mám tento příznak na int vpravo?

890
01:08:45,779 --> 01:08:49,290
Co to znamená? Oh, to znamenat, že

891
01:08:49,290 --> 01:08:51,370
Pokaždé, když jdu pravdu, musím nastavit,

892
01:08:51,370 --> 01:08:53,819
else if I jděte doleva musím nastavit na nulu.

893
01:08:53,819 --> 01:09:04,060
Tady, nemám k důvodu o tom, že je to prostě jednodušší myslet.

894
01:09:04,060 --> 01:09:06,710
Otázky?

895
01:09:06,710 --> 01:09:16,290
[Student, nesrozumitelné] >> Jo.

896
01:09:16,290 --> 01:09:23,359
Dobře, takže v poslední bit -

897
01:09:23,359 --> 01:09:28,080
Myslím, že jedna rychlá a snadná funkce, kterou můžeme udělat, je,

898
01:09:28,080 --> 01:09:34,910
let's - spolu, myslím, vyzkoušet a napsat obsahuje funkce

899
01:09:34,910 --> 01:09:38,899
které není jedno, jestli je to binární vyhledávací strom.

900
01:09:38,899 --> 01:09:43,770
Tato obsahuje funkce by měla vrátit hodnotu true

901
01:09:43,770 --> 01:09:58,330
pokud kdekoli v tomto obecném binárním stromu je hodnota, kterou hledáte.

902
01:09:58,330 --> 01:10:02,520
Takže pojďme se nejprve to rekurzivně a pak to uděláme iterativně.

903
01:10:02,520 --> 01:10:07,300
Můžeme vlastně jen to dohromady, protože to bude opravdu málo.

904
01:10:07,300 --> 01:10:11,510
>> Co je můj základní scénář bude?

905
01:10:11,510 --> 01:10:13,890
[Student, nesrozumitelným]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Takže pokud (strom == NULL), pak co?

907
01:10:18,230 --> 01:10:22,740
[Student] Návrat false.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, dobře, já nepotřebuju else.

909
01:10:26,160 --> 01:10:30,250
Pokud byl můj druhý base-case.

910
01:10:30,250 --> 01:10:32,450
[Student] Tree hodnota? Jo >>.

911
01:10:32,450 --> 01:10:36,430
Takže pokud (tree-> value == hodnota.

912
01:10:36,430 --> 01:10:39,920
Všimněte si, že jsme zpátky do uzlu *, není uzel ** s?

913
01:10:39,920 --> 01:10:42,990
Obsahuje nikdy se nebudete muset používat uzlu **,

914
01:10:42,990 --> 01:10:45,480
protože jsme se nemění ukazatele.

915
01:10:45,480 --> 01:10:50,540
Jsme prostě najet je.

916
01:10:50,540 --> 01:10:53,830
Pokud se tak stane, pak chceme vrátit true.

917
01:10:53,830 --> 01:10:58,270
Else chceme přejít děti.

918
01:10:58,270 --> 01:11:02,620
Takže nemůžeme uvažovat o tom, zda všechno vlevo je méně

919
01:11:02,620 --> 01:11:05,390
a všechno vpravo je větší.

920
01:11:05,390 --> 01:11:09,590
Takže to, co je naše podmínka bude tady - nebo, co budeme dělat?

921
01:11:09,590 --> 01:11:11,840
[Student, nesrozumitelné] >> Jo.

922
01:11:11,840 --> 01:11:17,400
Return obsahuje (hodnota, strom-> vlevo)

923
01:11:17,400 --> 01:11:26,860
nebo obsahuje (hodnota, strom-> vpravo). A to je vše.

924
01:11:26,860 --> 01:11:29,080
A všimněte si, že je nějaký zkrat hodnocení,

925
01:11:29,080 --> 01:11:32,520
kde, pokud se stane, že najdete hodnotu v levém stromu,

926
01:11:32,520 --> 01:11:36,820
jsme nikdy nebudete muset dívat na pravém stromu.

927
01:11:36,820 --> 01:11:40,430
To je celá funkce.

928
01:11:40,430 --> 01:11:43,690
Nyní se pojďme to iterativně,

929
01:11:43,690 --> 01:11:48,060
který bude méně pěkné.

930
01:11:48,060 --> 01:11:54,750
Vezmeme obvyklé start uzlu * cur = strom.

931
01:11:54,750 --> 01:12:03,250
Zatímco (teď! = NULL).

932
01:12:03,250 --> 01:12:08,600
Rychle bude vidět problém.

933
01:12:08,600 --> 01:12:12,250
Pokud teď - tady, jestli se někdy uniknout z tohoto,

934
01:12:12,250 --> 01:12:16,020
pak jsme došly věci podívat se na, tak vrátí false.

935
01:12:16,020 --> 01:12:24,810
Pokud (teď-> value == hodnota), vrátí true.

936
01:12:24,810 --> 01:12:32,910
Takže teď jsme na místě -

937
01:12:32,910 --> 01:12:36,250
nevíme, zda chceme jít doleva nebo doprava.

938
01:12:36,250 --> 01:12:44,590
Takže libovolně, pojďme odešel.

939
01:12:44,590 --> 01:12:47,910
Já jsem samozřejmě běžet do problému, kdy jsem úplně opuštěné všechno -

940
01:12:47,910 --> 01:12:50,760
Budu vždy jen kontrolovat levou stranu stromu.

941
01:12:50,760 --> 01:12:56,050
Nikdy kontrolovat vše, co je právo dítě nic.

942
01:12:56,050 --> 01:13:00,910
Jak mohu tento problém vyřešit?

943
01:13:00,910 --> 01:13:05,260
[Student] Musíte sledovat vlevo a vpravo v zásobníku.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Jo. Takže pojďme dělat to

945
01:13:13,710 --> 01:13:32,360
struct list, uzel * n, a potom uzel ** dál?

946
01:13:32,360 --> 01:13:40,240
Myslím si, že funguje dobře.

947
01:13:40,240 --> 01:13:45,940
Chceme jít přes levé, nebo let's - tady.

948
01:13:45,940 --> 01:13:54,350
Struct = SEZNAM seznam, bude to začne

949
01:13:54,350 --> 01:13:58,170
protože na tomto struct seznamu.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Takže to bude náš propojený seznam

951
01:14:04,040 --> 01:14:08,430
z podstromů, které jsme přeskočil.

952
01:14:08,430 --> 01:14:13,800
Budeme procházet zbylo,

953
01:14:13,800 --> 01:14:17,870
ale protože jsme nutně potřebovat vrátit doprava,

954
01:14:17,870 --> 01:14:26,140
Budeme držet pravou stranu uvnitř našeho struct seznamu.

955
01:14:26,140 --> 01:14:32,620
Pak budeme mít new_list nebo struct,

956
01:14:32,620 --> 01:14:41,080
struct list *, new_list = malloc (sizeof (seznam)).

957
01:14:41,080 --> 01:14:44,920
Budu ignorovat chyba-kontrolovat, ale měli byste zkontrolovat, jestli je to null.

958
01:14:44,920 --> 01:14:50,540
New_list uzel, že to bude ukazovat na -

959
01:14:50,540 --> 01:14:56,890
oh, to je důvod, proč jsem chtěl to tady. Bude to poukázat na druhé struct seznamu.

960
01:14:56,890 --> 01:15:02,380
To je jen, jak souvisí Seznam prací.

961
01:15:02,380 --> 01:15:04,810
To je stejné jako int propojeném seznamu

962
01:15:04,810 --> 01:15:06,960
kromě jsme jen nahrazovat int s uzlem *.

963
01:15:06,960 --> 01:15:11,040
Je to úplně stejné.

964
01:15:11,040 --> 01:15:15,100
Takže new_list, hodnota naší new_list uzlu,

965
01:15:15,100 --> 01:15:19,120
bude teď-> klikněte pravým.

966
01:15:19,120 --> 01:15:24,280
Hodnota našeho new_list-> next bude náš původní seznam,

967
01:15:24,280 --> 01:15:30,760
a pak budeme aktualizovat náš seznam, aby ukazoval na new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nyní potřebujeme nějaký způsob tahání věcí,

969
01:15:33,650 --> 01:15:37,020
jak jsme projet celý levého podstromu.

970
01:15:37,020 --> 01:15:40,480
Teď musíme vytáhnout věci z toho,

971
01:15:40,480 --> 01:15:43,850
jako teď je null, nechceme jen vrátit false.

972
01:15:43,850 --> 01:15:50,370
Chceme nyní vytáhnout ven na našem novém seznamu.

973
01:15:50,370 --> 01:15:53,690
Nejvýhodnějším způsobem, jak to udělat - no, vlastně, je tu několik způsobů, jak to udělat.

974
01:15:53,690 --> 01:15:56,680
Každý, kdo má nějaký návrh?

975
01:15:56,680 --> 01:15:58,790
Kde bych měl udělat, nebo jak bych měl udělat?

976
01:15:58,790 --> 01:16:08,010
Máme jen pár minut, ale nějaké návrhy?

977
01:16:08,010 --> 01:16:14,750
Místo toho, aby - jedním způsobem, místo toho, aby náš stav je při,

978
01:16:14,750 --> 01:16:17,090
to, co jsme v současné době hledá v není null,

979
01:16:17,090 --> 01:16:22,340
místo budeme i nadále pokračovat, dokud náš seznam sám o sobě je null.

980
01:16:22,340 --> 01:16:25,680
Takže pokud náš seznam skončí jako bytí null,

981
01:16:25,680 --> 01:16:30,680
pak jsme došly věci hledat, prohledávat.

982
01:16:30,680 --> 01:16:39,860
Ale to znamená, že první věc, kterou v našem seznamu je jen tak být první uzel.

983
01:16:39,860 --> 01:16:49,730
Úplně první věc, kterou bude - jsme již třeba vidět, že.

984
01:16:49,730 --> 01:16:58,710
Takže list-> n bude náš strom.

985
01:16:58,710 --> 01:17:02,860
list-> next bude null.

986
01:17:02,860 --> 01:17:07,580
A teď, když seznam se nerovná null.

987
01:17:07,580 --> 01:17:11,610
Cur bude vytáhnout něco z našeho seznamu.

988
01:17:11,610 --> 01:17:13,500
Takže teď se chystá na rovné seznam-> n.

989
01:17:13,500 --> 01:17:20,850
A pak seznam bude rovné seznam-> n, nebo list-> next.

990
01:17:20,850 --> 01:17:23,480
Takže pokud teď hodnota se rovná hodnotě.

991
01:17:23,480 --> 01:17:28,790
Nyní můžeme přidat i naši pravou myši a naše levé ukazatel

992
01:17:28,790 --> 01:17:32,900
jak dlouho jak oni to není null.

993
01:17:32,900 --> 01:17:36,390
Tady dole, myslím, že bychom měli udělat, že na prvním místě.

994
01:17:36,390 --> 01:17:44,080
Pokud (teď-> P! = NULL)

995
01:17:44,080 --> 01:17:56,380
pak budeme vložit tento uzel do našeho seznamu.

996
01:17:56,380 --> 01:17:59,290
Pokud (teď-> vlevo), to je trochu práce navíc, ale to je v pořádku.

997
01:17:59,290 --> 01:18:02,690
Pokud (teď-> doleva! = NULL),

998
01:18:02,690 --> 01:18:14,310
a budeme vložit doleva do našeho propojeného seznamu,

999
01:18:14,310 --> 01:18:19,700
a že by měla být ono.

1000
01:18:19,700 --> 01:18:22,670
My iteraci - tak dlouho, jak budeme mít něco v našem seznamu,

1001
01:18:22,670 --> 01:18:26,640
máme další uzel na pohled.

1002
01:18:26,640 --> 01:18:28,920
Takže se podíváme v tomto uzlu,

1003
01:18:28,920 --> 01:18:31,390
jsme předem na náš seznam na příští.

1004
01:18:31,390 --> 01:18:34,060
Pokud tento uzel je hodnota, kterou hledáte, můžeme se vrátit true.

1005
01:18:34,060 --> 01:18:37,640
Else vložte obě naše levé a pravé podstromy,

1006
01:18:37,640 --> 01:18:40,510
jak dlouho jak oni to není null, do našeho seznamu

1007
01:18:40,510 --> 01:18:43,120
takže jsme nevyhnutelně jít přes ně.

1008
01:18:43,120 --> 01:18:45,160
Takže v případě, že nebyly null,

1009
01:18:45,160 --> 01:18:47,950
když náš kořen ukazatel upozornil na dvě věci,

1010
01:18:47,950 --> 01:18:51,670
pak nejprve jsme vytáhli něco tak náš seznam skončí jako bytí null.

1011
01:18:51,670 --> 01:18:56,890
A pak jsme dali dvě věci zpět, takže teď náš seznam je velikost 2.

1012
01:18:56,890 --> 01:19:00,030
Pak budeme smyčky zpět a my jen tak vytáhnout,

1013
01:19:00,030 --> 01:19:04,250
řekněme, levé ukazatel našeho kořenového uzlu.

1014
01:19:04,250 --> 01:19:07,730
A to si jen dějí, skončíme smyčky nad vším.

1015
01:19:07,730 --> 01:19:11,280
>> Všimněte si, že to bylo podstatně složitější

1016
01:19:11,280 --> 01:19:14,160
v rekurzivní řešení.

1017
01:19:14,160 --> 01:19:17,260
A já jsem řekl: vícekrát

1018
01:19:17,260 --> 01:19:25,120
že rekurzivní řešení má obvykle mnoho společného s iterativní řešení.

1019
01:19:25,120 --> 01:19:30,820
Tady je to přesně to, co rekurzivní řešení dělá.

1020
01:19:30,820 --> 01:19:36,740
Jedinou změnou je, že místo toho, aby implicitně pomocí zásobníku, program zásobník,

1021
01:19:36,740 --> 01:19:40,840
jako způsob, jak udržet přehled o tom, co uzly stále potřebujete navštívit,

1022
01:19:40,840 --> 01:19:45,430
Nyní budete muset použít propojeného seznamu.

1023
01:19:45,430 --> 01:19:49,070
V obou případech se sledování toho, co uzlu je ještě třeba navštívil.

1024
01:19:49,070 --> 01:19:51,790
V rekurzivní případě, že je to prostě jednodušší, protože zásobník

1025
01:19:51,790 --> 01:19:57,100
je implementován pro vás jako programu zásobníku.

1026
01:19:57,100 --> 01:19:59,550
Povšimněte si, že tento spojový seznam, to je zásobník.

1027
01:19:59,550 --> 01:20:01,580
Ať jsme jen dát na stack

1028
01:20:01,580 --> 01:20:09,960
je hned to, co budeme vytáhněte zásobník na návštěvu další.

1029
01:20:09,960 --> 01:20:14,380
Jsme mimo čas, ale na něco zeptat?

1030
01:20:14,380 --> 01:20:23,530
[Student, nesrozumitelným]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Jo. Takže pokud máme propojeného seznamu,

1032
01:20:27,790 --> 01:20:30,150
proud bude poukázat na toho chlapa,

1033
01:20:30,150 --> 01:20:34,690
a teď jsme jen zlepšování propojeného seznamu zaměřit se na toho chlapa.

1034
01:20:34,690 --> 01:20:44,200
Jsme křížení přes propojeného seznamu v tomto řádku.

1035
01:20:44,200 --> 01:20:51,200
A pak myslím, že bychom měli osvobodit naše propojeného seznamu a podobně

1036
01:20:51,200 --> 01:20:53,880
jednou před vrací hodnotu true nebo false, musíme

1037
01:20:53,880 --> 01:20:57,360
iteraci našeho propojeného seznamu a vždy se sem, myslím,

1038
01:20:57,360 --> 01:21:03,900
pokud bychom teď právo není rovno, přidejte jej, takže teď chceme osvobodit

1039
01:21:03,900 --> 01:21:09,600
teď, protože, no, my jsme úplně zapomenout na seznamu? Jo.

1040
01:21:09,600 --> 01:21:12,880
Takže to je to, co chceme dělat.

1041
01:21:12,880 --> 01:21:16,730
Kde je ukazatel?

1042
01:21:16,730 --> 01:21:23,320
Cur byl pak - chceme do struct seznam * 10 rovná seznam vedle.

1043
01:21:23,320 --> 01:21:29,240
Free list, list = temp.

1044
01:21:29,240 --> 01:21:32,820
A v případě, kdy se vrátí true, je třeba, abychom iteraci

1045
01:21:32,820 --> 01:21:37,050
po zbytek našeho propojeného seznamu uvolňovat věci.

1046
01:21:37,050 --> 01:21:39,700
Pěkná věc, o rekurzivní řešení je uvolnění věci

1047
01:21:39,700 --> 01:21:44,930
prostě znamená objevovat factorings ze zásobníku, který se stane pro vás.

1048
01:21:44,930 --> 01:21:50,720
Takže jsme šli z něčeho, co to jako 3 řádky těžko think-o kód

1049
01:21:50,720 --> 01:21:57,520
k něčemu, co je výrazně mnohem více tvrdý-k-si-o řádků kódu.

1050
01:21:57,520 --> 01:22:00,620
Nějaké další otázky?

1051
01:22:00,620 --> 01:22:08,760
Dobrá. Jsme v pohodě. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]