1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Časť 7: Ďalšie 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 ako som povedal vo svojom e-mailu,

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

6
00:00:14,060 --> 00:00:16,820
Ale tam nie je, že mnoho otázok.

7
00:00:16,820 --> 00:00:18,920
Takže budeme sa snažiť a čerpať z každej otázky

8
00:00:18,920 --> 00:00:25,430
a ísť do bolestné detailu všetkých najlepších spôsobov, ako robiť veci.

9
00:00:25,430 --> 00:00:31,200
Takže hneď na začiatku, sme sa prejsť vzorky kresieb binárnych stromov a podobne.

10
00:00:31,200 --> 00:00:35,970
Tak tu, "Pamätaj si, že binárny strom má uzly podobné tým prepojeného zoznamu,

11
00:00:35,970 --> 00:00:38,150
okrem namiesto jedného ukazovatele sú dva: jeden pre ľavé "dieťa"

12
00:00:38,150 --> 00:00:41,950
a jeden pre pravé "dieťa". "

13
00:00:41,950 --> 00:00:45,630
Takže binárny strom je rovnako ako prepojeného zoznamu,

14
00:00:45,630 --> 00:00:47,910
okrem struct bude mať dva ukazovatele.

15
00:00:47,910 --> 00:00:51,390
Tam je trinary stromy, ktoré sa chystajú tri ukazovatele,

16
00:00:51,390 --> 00:00:56,540
tam sú n-árne stromy, ktoré práve majú všeobecný ukazovateľ

17
00:00:56,540 --> 00:01:00,320
, Ktoré potom musia malloc byť dostatočne veľké, aby sa

18
00:01:00,320 --> 00:01:04,840
dosť ukazovatele na všetkých možných detí.

19
00:01:04,840 --> 00:01:08,200
Takže binárne strom len sa stane, že konštantné množstvo dvoch.

20
00:01:08,200 --> 00:01:11,260
Ak chcete, môžete si dať prepojeného zoznamu ako unární strom,

21
00:01:11,260 --> 00:01:15,360
ale ja si nemyslím, že niekto volá, že.

22
00:01:15,360 --> 00:01:18,060
"Nakreslite boxy-a-arrows diagram binárneho stromu uzol

23
00:01:18,060 --> 00:01:24,110
obsahujúce Nate obľúbené číslo, 7, kde každé dieťa ukazovateľ 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 byť celkom jednoduché.

26
00:01:30,280 --> 00:01:36,150
Sme jednoducho bude mať uzol, budem kresliť ako štvorec.

27
00:01:36,150 --> 00:01:38,730
A ja budem čerpať hodnoty tu.

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 potom tu dole budeme mať ľavej ukazovateľ vľavo a vpravo ukazovateľ vpravo.

30
00:01:44,770 --> 00:01:50,430
A to je veľmi, takže je zvykom nazývať ľavý a pravý, ukazovateľ mená.

31
00:01:50,430 --> 00:01:52,460
Obaja títo budú mať hodnotu null.

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

33
00:01:57,870 --> 00:02:03,630
Dobre. Takže späť sem.

34
00:02:03,630 --> 00:02:05,700
"S prepojeného zoznamu, sme mali iba na uloženie ukazovatele

35
00:02:05,700 --> 00:02:09,639
na prvom uzla v zozname za účelom pamätať celý spájať zoznam alebo celý zoznam.

36
00:02:09,639 --> 00:02:11,650
Rovnako tak, sa stromy, máme iba na uloženie ukazovatele

37
00:02:11,650 --> 00:02:13,420
na jednom uzle, aby sa pamätať celý strom.

38
00:02:13,420 --> 00:02:15,980
Tento uzol je calle ďalej len "koreň" stromu.

39
00:02:15,980 --> 00:02:18,320
Stavať na diagrame z obdobia pred alebo nakresliť nový

40
00:02:18,320 --> 00:02:21,690
tak, že máte boxy-a-arrows znázornenie binárneho stromu

41
00:02:21,690 --> 00:02:25,730
s hodnotu 7, potom 3 v ľavej,

42
00:02:25,730 --> 00:02:32,760
potom 9 na pravej strane, a potom 6 na pravej strane 3 ".

43
00:02:32,760 --> 00:02:34,810
Uvidíme, či si pamätám všetko v mojej hlave.

44
00:02:34,810 --> 00:02:37,670
Tak to bude naša koreň tu.

45
00:02:37,670 --> 00:02:41,600
Dáme si ukazovateľ niekde, niečo, čo budeme volať koreň,

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

47
00:02:45,140 --> 00:02:48,490
Teraz sa vytvoriť nový uzol,

48
00:02:48,490 --> 00:02:52,870
čo máme, 3 vľavo?

49
00:02:52,870 --> 00:02:57,140
Takže nový uzol s 3, a to na začiatku ukazuje nulový.

50
00:02:57,140 --> 00:02:59,190
Ja si len dať N.

51
00:02:59,190 --> 00:03:02,250
Teraz chceme, aby sa to ísť vľavo 7.

52
00:03:02,250 --> 00:03:06,840
Tak sme zmeniť tento ukazovateľ teraz ukazujú na toho chlapa.

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

54
00:03:12,420 --> 00:03:14,620
ktorý spočiatku len hovorí, null.

55
00:03:14,620 --> 00:03:19,600
Budeme meniť tento ukazovateľ, prejdite na 9,

56
00:03:19,600 --> 00:03:23,310
a teraz chceme dať 6 na pravej strane 3.

57
00:03:23,310 --> 00:03:32,170
Takže to bude - urobiť 6.

58
00:03:32,170 --> 00:03:34,310
A ten chlap bude smerovať tam.

59
00:03:34,310 --> 00:03:38,320
Dobre. Tak to je všetko, čo je od nás žiada robiť.

60
00:03:38,320 --> 00:03:42,770
>> Teraz poďme cez niektoré pojmy.

61
00:03:42,770 --> 00:03:46,690
Už sme hovorili o tom, ako koreň stromu je na najvyššej uzol v strome.

62
00:03:46,690 --> 00:03:54,720
Z ktorých jedna obsahuje 7. Uzly v dolnej časti stromu sa nazývajú listy.

63
00:03:54,720 --> 00:04:01,240
Každý uzol, ktorý má jednoducho null ako jeho deti, je list.

64
00:04:01,240 --> 00:04:03,680
Je teda možné, ak náš binárny strom je len jeden uzol,

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

66
00:04:10,130 --> 00:04:12,060
"The" Výška "stromu je počet chmeľu je nutné vykonať

67
00:04:12,060 --> 00:04:16,620
sa dostať z vrcholu do listu. "

68
00:04:16,620 --> 00:04:18,640
Dostaneme do, v druhej, na rozdiel

69
00:04:18,640 --> 00:04:21,940
medzi symetrické a nesymetrické binárnych stromov,

70
00:04:21,940 --> 00:04:29,470
ale teraz, celková výška tohto stromu

71
00:04:29,470 --> 00:04:34,520
Povedal by som, že je 3, ale ak budete počítať množstvo chmeľu

72
00:04:34,520 --> 00:04:39,710
je nutné vykonať tak, aby sa dostať do 9, potom je to naozaj len výška 2.

73
00:04:39,710 --> 00:04:43,340
Práve teraz je to nevyvážený binárny strom,

74
00:04:43,340 --> 00:04:49,840
ale budeme hovorili o vyvážené, keď sa dostane za relevantné.

75
00:04:49,840 --> 00:04:52,040
Takže teraz môžeme hovoriť o uzlov na strome, pokiaľ ide

76
00:04:52,040 --> 00:04:54,700
vo vzťahu k ostatným uzlov stromu.

77
00:04:54,700 --> 00:04:59,730
Takže teraz máme rodičia, deti, súrodenci, predkov a potomkovia.

78
00:04:59,730 --> 00:05:05,650
Oni sú celkom zdravý rozum, čo to znamená.

79
00:05:05,650 --> 00:05:09,610
Pýtame Ak sa - je to rodičia.

80
00:05:09,610 --> 00:05:12,830
Takže to, čo je nadradený 3?

81
00:05:12,830 --> 00:05:16,090
[Študenti] 7. Jo >>. Rodič len bude, čo poukazuje na tebe.

82
00:05:16,090 --> 00:05:20,510
Tak čo, sú deti 7?

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

84
00:05:23,860 --> 00:05:26,460
Všimnite si, že "deti" doslova znamená deti,

85
00:05:26,460 --> 00:05:31,010
tak 6 sa nepoužijú, pretože je to ako vnúča.

86
00:05:31,010 --> 00:05:35,540
Ale potom, keď pôjdeme potomkov, takže aké sú potomkovia 7?

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

88
00:05:37,500 --> 00:05:42,330
Potomkovia koreňa bude všetko v stromu,

89
00:05:42,330 --> 00:05:47,950
snáď s výnimkou koreňový uzol sám, ak nechcete, aby zvážila, že potomok.

90
00:05:47,950 --> 00:05:50,750
A konečne, predkovia, tak je to v opačnom smere.

91
00:05:50,750 --> 00:05:55,740
Takže aké sú predkami 6?

92
00:05:55,740 --> 00:05:58,920
[Študenti] 3 a 7. Jo >>. 9 nie je zahrnutá.

93
00:05:58,920 --> 00:06:02,520
Je to len priame línie späť do koreňového adresára

94
00:06:02,520 --> 00:06:13,230
bude vaši predkovia.

95
00:06:13,230 --> 00:06:16,300
>> "Povieme, že binárny strom je" prikázal ", ak pre každý uzol v strome,

96
00:06:16,300 --> 00:06:19,530
všetky jeho potomkov na ľavej strane majú menšie hodnoty

97
00:06:19,530 --> 00:06:22,890
a všetky tie, na pravej strane sú väčšie hodnoty.

98
00:06:22,890 --> 00:06:27,060
Napríklad, je strom nad objednal, ale nie je to len možné objednať usporiadanie. "

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

100
00:06:30,180 --> 00:06:36,420
objednal binárne strom je tiež známy ako binárny vyhľadávací strom.

101
00:06:36,420 --> 00:06:38,660
Tu sa stalo, že sa nazývať to objednané binárne strom,

102
00:06:38,660 --> 00:06:41,850
ale nikdy som nepočul, že len objednať binárny strom pred,

103
00:06:41,850 --> 00:06:46,650
a na kvíz sme oveľa častejšie, aby strom binárneho vyhľadávania.

104
00:06:46,650 --> 00:06:49,250
Sú jedna a tá istá,

105
00:06:49,250 --> 00:06:54,580
a to je dôležité, spoznáte rozdiel medzi binárnym stromom a binárne vyhľadávacie strom.

106
00:06:54,580 --> 00:06:58,830
Binárne strom je len strom, ktorý ukazuje na dve veci.

107
00:06:58,830 --> 00:07:02,120
Každý uzol poukazuje na dve veci.

108
00:07:02,120 --> 00:07:06,310
Neexistuje žiadny úvaha o hodnotách, ktoré sa ukazuje na.

109
00:07:06,310 --> 00:07:11,370
Tak ako tu, pretože je to binárny vyhľadávací strom,

110
00:07:11,370 --> 00:07:14,030
vieme, že keď ideme vľavo 7,

111
00:07:14,030 --> 00:07:16,670
potom všetky hodnoty, ktoré môžeme prípadne dosiahnuť

112
00:07:16,670 --> 00:07:19,310
tým, že ide vľavo 7 musí byť menší ako 7.

113
00:07:19,310 --> 00:07:24,070
Všimnite si, že všetky hodnoty menšie ako 7 sú 3 a 6.

114
00:07:24,070 --> 00:07:26,040
Tí sú na ľavej strane 7.

115
00:07:26,040 --> 00:07:29,020
Ak pôjdeme na pravej strane 7, všetko musí byť väčšia ako 7,

116
00:07:29,020 --> 00:07:33,220
takže 9 je na pravej strane 7, takže sme v pohode.

117
00:07:33,220 --> 00:07:36,150
Toto nie je prípad binárneho stromu,

118
00:07:36,150 --> 00:07:40,020
pre pravidelné binárneho stromu môžeme len majú 3 v hornej, 7 na ľavej strane,

119
00:07:40,020 --> 00:07:47,630
9 na ľavej strane 7, nie je objednanie hodnôt vôbec.

120
00:07:47,630 --> 00:07:56,140
Teraz, nebudeme vlastne robiť, pretože je to nudné a zbytočné,

121
00:07:56,140 --> 00:07:59,400
ale "skúsiť nakresliť toľko objednaný stromov, ako si môžete myslieť

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

123
00:08:01,900 --> 00:08:06,800
Koľko odlišné usporiadanie sú tam? Aká je výška každej z nich? "

124
00:08:06,800 --> 00:08:10,480
>> Urobíme pár, ale hlavná myšlienka je,

125
00:08:10,480 --> 00:08:16,530
To je v žiadnom prípade jedinečné znázornenie binárneho stromu, ktorý obsahuje tieto hodnoty.

126
00:08:16,530 --> 00:08:22,760
Všetko čo potrebujeme, je nejaký binárny strom, ktorý obsahuje 7, 3, 6 a 9.

127
00:08:22,760 --> 00:08:25,960
Ďalším možným platná jeden by koreň je 3,

128
00:08:25,960 --> 00:08:30,260
prejsť na ľavej strane a je to 6, prejsť na ľavej strane a je to 7,

129
00:08:30,260 --> 00:08:32,730
ísť doľava a je to 9.

130
00:08:32,730 --> 00:08:36,169
To je úplne platný binárny vyhľadávací strom.

131
00:08:36,169 --> 00:08:39,570
Nie je to veľmi užitočné, pretože je to rovnako ako prepojeného zoznamu

132
00:08:39,570 --> 00:08:43,750
a všetky tieto ukazovatele sú len 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
[Študent] Nie hodnoty musia byť väčšie na pravej strane?

135
00:08:51,310 --> 00:08:56,700
Alebo je to -? >> Tie som chcel ísť inou cestou.

136
00:08:56,700 --> 00:09:00,960
K dispozícii je tiež - jo, poďme prejsť to.

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

138
00:09:07,770 --> 00:09:11,730
To ešte musí počúvať, čo binárny strom vyhľadávania robiť.

139
00:09:11,730 --> 00:09:15,650
Takže všetko na ľavej strane musí byť menšia ako daný uzol.

140
00:09:15,650 --> 00:09:23,180
Mohli by sme len presunúť, povedzme, táto 6 a dať sem.

141
00:09:23,180 --> 00:09:26,880
Nie, nemôžeme. Prečo som to robiť, že?

142
00:09:26,880 --> 00:09:35,350
Poďme urobiť - tu je 6, tu je 7, 6 bodov na 3.

143
00:09:35,350 --> 00:09:39,290
To je stále platný binárny vyhľadávací strom.

144
00:09:39,290 --> 00:09:49,260
Čo je zle, keď si - uvidíme, či môžem prísť s usporiadaním.

145
00:09:49,260 --> 00:09:52,280
Jo, dobre. Takže to, čo je zle s týmto stromom?

146
00:09:52,280 --> 00:10:08,920
Myslím, že som už dal náznak, že je niečo v neporiadku s ňou.

147
00:10:08,920 --> 00:10:14,430
Prečo som to robiť, že?

148
00:10:14,430 --> 00:10:18,510
Dobre. To vyzerá rozumne.

149
00:10:18,510 --> 00:10:22,590
Ak sa pozrieme na každom uzle, ako je 7, potom na ľavej strane 7 je 3.

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

151
00:10:24,960 --> 00:10:27,750
A keď sa pozriete na 6, vec vpravo 6 je 9.

152
00:10:27,750 --> 00:10:30,910
Tak prečo je to nie je platný binárny vyhľadávací strom?

153
00:10:30,910 --> 00:10:36,330
[Študenti] 9, je stále na ľavej strane 7. Jo >>.

154
00:10:36,330 --> 00:10:43,710
Musí to byť pravda, že všetky hodnoty, ktoré môžete prípadne dosiahnuť tým, že pôjdete na ľavej strane 7 árov menej ako 7.

155
00:10:43,710 --> 00:10:49,120
Ak pôjdeme vľavo 7, dostaneme sa 3 a stále môžeme dostať do 6,

156
00:10:49,120 --> 00:10:52,520
môžeme ešte dostať do 9, ale tým, že má preč menej ako 7,

157
00:10:52,520 --> 00:10:55,070
by sme však byť schopný sa dostať na číslo, ktoré je väčšie ako 7.

158
00:10:55,070 --> 00:10:59,830
Takže to nie je platný binárny vyhľadávací strom.

159
00:10:59,830 --> 00:11:02,330
>> Môj brat vlastne mal rozhovor otázku

160
00:11:02,330 --> 00:11:07,760
to bolo v podstate to, len kód do niečoho na overenie

161
00:11:07,760 --> 00:11:10,500
či strom je binárny vyhľadávací strom,

162
00:11:10,500 --> 00:11:13,580
a tak prvá vec, ktorú urobil, bolo, len skontrolovať,

163
00:11:13,580 --> 00:11:17,020
ak vľavo a vpravo sú správne, a potom určiť iteráciou tam.

164
00:11:17,020 --> 00:11:19,700
Ale nemôžeš len to, že, budete mať neustále prehľad

165
00:11:19,700 --> 00:11:22,550
na skutočnosť, že teraz, keď som preč odišiel zo 7.,

166
00:11:22,550 --> 00:11:26,340
všetko v tomto podstrome musí byť menší ako 7.

167
00:11:26,340 --> 00:11:28,430
Správna algoritmus potrebuje sledovať

168
00:11:28,430 --> 00:11:35,970
z medzí, ktoré je možné hodnoty možná spadajú dovnútra

169
00:11:35,970 --> 00:11:38,360
Nebudeme prejsť všetky z nich.

170
00:11:38,360 --> 00:11:41,630
K dispozícii je pekná opakovanie vzťah,

171
00:11:41,630 --> 00:11:44,810
aj keď sme sa dostali k tým, inak nebudeme sa k tým,

172
00:11:44,810 --> 00:11:47,030
definovanie, koľko ich vlastne 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šlienka na to, ako by to matematicky je ako,

175
00:11:56,020 --> 00:11:59,770
si môžete vybrať jeden ľubovoľný jedného byť koreňový uzol,

176
00:11:59,770 --> 00:12:03,160
a potom, keď vybrať 7 byť koreňový uzol,

177
00:12:03,160 --> 00:12:08,150
potom tam sú, povedzme, niektoré čísla, ktoré môžu ísť byť mojej ľavici uzol,

178
00:12:08,150 --> 00:12:10,440
a tam sú niektoré čísla, ktoré môžu byť moja pravá uzol,

179
00:12:10,440 --> 00:12:15,090
ale ak som n celkové počty, potom sa suma, ktorá môže ísť vľavo

180
00:12:15,090 --> 00:12:18,820
plus suma, ktorá môže ísť vpravo je n - 1.

181
00:12:18,820 --> 00:12:26,130
Takže zo zostávajúcich čísel, musí byť schopný ísť buď doľava alebo doprava.

182
00:12:26,130 --> 00:12:31,580
Zdá sa, že ťažké, keď som dal 3 prvej potom všetko musí ísť doľava,

183
00:12:31,580 --> 00:12:35,080
ale keď som dal 7, potom niektoré veci môže ísť vľavo a niektoré veci môžu ísť na práva.

184
00:12:35,080 --> 00:12:39,570
A '3 prvý "Myslel som všetko môže ísť doprava.

185
00:12:39,570 --> 00:12:42,350
Je to naozaj, stačí premýšľať o tom, ako,

186
00:12:42,350 --> 00:12:47,980
koľko vecí môže ísť na ďalšiu úroveň stromu.

187
00:12:47,980 --> 00:12:50,420
A to je sa, že je 14, alebo sa môže čerpať všetky z nich,

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

189
00:12:54,650 --> 00:13:01,120
>> Vráťme sa späť sem,

190
00:13:01,120 --> 00:13:03,510
"Objednaný binárne stromy sú skvelé, pretože môžeme hľadať v nich

191
00:13:03,510 --> 00:13:06,910
veľmi podobne ako vyhľadávanie cez triedenom poli.

192
00:13:06,910 --> 00:13:10,120
Ak chcete tak urobiť, začneme pri koreni a prácu si cestu dole stromu

193
00:13:10,120 --> 00:13:13,440
smerom listov, kontrola každý uzol v hodnoty na hodnoty, ktoré sme hľadáte.

194
00:13:13,440 --> 00:13:15,810
Ak je aktuálna uzol je hodnota nižšia ako hodnota, ktorú hľadáme,

195
00:13:15,810 --> 00:13:18,050
idete vedľa uzla pravej dieťa.

196
00:13:18,050 --> 00:13:20,030
V opačnom prípade, pôjdete do uzla na ľavej dieťa.

197
00:13:20,030 --> 00:13:22,800
V určitom bode, budete buď nájsť hodnotu, ktorú hľadáte, alebo budete spúšťať do null,

198
00:13:22,800 --> 00:13:28,520
označujúce hodnotu nie je v strome. "

199
00:13:28,520 --> 00:13:32,450
Mám k prekreslenie stromu sme mali predtým, že bude trvať sekundu.

200
00:13:32,450 --> 00:13:38,280
Ale chceme sa pozrieť do, či 6, 10, a 1 sú v strome.

201
00:13:38,280 --> 00:13:49,180
Takže, čo to bolo, 7, 9, 3, 6. Dobre.

202
00:13:49,180 --> 00:13:52,730
Čísla chcete vyhľadať, chceme pozrieť do 6.

203
00:13:52,730 --> 00:13:55,440
Ako sa tento algoritmus funguje?

204
00:13:55,440 --> 00:14:03,040
No, máme aj nejaké koreňový ukazovateľ na náš strom.

205
00:14:03,040 --> 00:14:12,460
A mali by sme ísť ku koreňu a povedať, je táto hodnota rovná hodnote my hľadáme?

206
00:14:12,460 --> 00:14:15,000
Takže sme hľadali 6, takže to nie je rovnaké.

207
00:14:15,000 --> 00:14:20,140
Tak sme ďalej, a teraz hovoríme, áno, takže 6 je menší ako 7.

208
00:14:20,140 --> 00:14:23,940
Znamená to, že chceme ísť doľava, alebo chceme ísť doprava?

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

210
00:14:27,340 --> 00:14:33,340
Je to výrazne jednoduchšie, všetko, čo musíte urobiť, je nakresliť jeden možný uzol stromu

211
00:14:33,340 --> 00:14:37,760
a potom nie - namiesto toho sa snaží myslieť v hlave,

212
00:14:37,760 --> 00:14:40,020
v poriadku, ak je to menej, mám ísť doľava alebo ísť právo,

213
00:14:40,020 --> 00:14:43,030
Len pri pohľade na tento obrázok, je to veľmi jasné, že musím ísť doľava

214
00:14:43,030 --> 00:14:47,700
v prípade, že uzol je väčšia ako hodnota, že som hľadal.

215
00:14:47,700 --> 00:14:52,600
Takže idete doľava, teraz som na 3.

216
00:14:52,600 --> 00:14:57,770
Chcem - 3, je menšia, než je hodnota Hľadám, čo je o 6.

217
00:14:57,770 --> 00:15:03,420
Takže ideme vpravo, a teraz som skončil na 6,

218
00:15:03,420 --> 00:15:07,380
čo je hodnota Hľadám, tak som sa vrátiť true.

219
00:15:07,380 --> 00:15:15,760
Ďalšie hodnota budem hľadať je 10.

220
00:15:15,760 --> 00:15:23,230
Dobre. Takže 10, teraz sa chystá - odrezať, že - bude nasledovať koreň.

221
00:15:23,230 --> 00:15:27,670
Teraz, 10 bude väčší ako 7, tak sa chcem pozrieť na pravej strane.

222
00:15:27,670 --> 00:15:31,660
Chystám sa ísť sem, 10 bude väčší ako 9,

223
00:15:31,660 --> 00:15:34,520
takže budem chcieť pozrieť na pravej strane.

224
00:15:34,520 --> 00:15:42,100
Prišiel som sem, ale sem teraz som na null.

225
00:15:42,100 --> 00:15:44,170
Čo mám robiť, keď som narazila null?

226
00:15:44,170 --> 00:15:47,440
[Študent] Návrat false? Jo >>. Nenašiel som 10.

227
00:15:47,440 --> 00:15:49,800
1 sa bude takmer totožný prípad,

228
00:15:49,800 --> 00:15:51,950
okrem toho, že to jednoducho bude prevrátený, namiesto hľadania

229
00:15:51,950 --> 00:15:56,540
dole na pravej strane, idem sa pozrieť dolu na ľavej strane.

230
00:15:56,540 --> 00:16:00,430
>> Myslím, že teraz sme vlastne dostať ku kódu.

231
00:16:00,430 --> 00:16:04,070
Tu je miesto, kde - otvoriť CS50 spotrebič a navigáciu si cestu tam,

232
00:16:04,070 --> 00:16:07,010
ale môžete tiež len to je v priestore.

233
00:16:07,010 --> 00:16:09,170
Je to asi ideálne, aby to v priestore,

234
00:16:09,170 --> 00:16:13,760
pretože môžu pracovať v priestore.

235
00:16:13,760 --> 00:16:19,170
"Najprv budeme potrebovať novú definíciu typu pre binárne uzol stromu obsahuje int hodnoty.

236
00:16:19,170 --> 00:16:21,400
Použitie dosku spotrebiče typedef nižšie,

237
00:16:21,400 --> 00:16:24,510
vytvoriť novú definíciu typu pre uzol v binárnom stromu.

238
00:16:24,510 --> 00:16:27,930
Ak narazíte. . . "Bla, bla, bla. Dobre.

239
00:16:27,930 --> 00:16:30,380
Takže poďme dať dosku spotrebiče tu,

240
00:16:30,380 --> 00:16:41,630
typedef struct uzol, a uzol. Jo, dobre.

241
00:16:41,630 --> 00:16:44,270
Takže aké sú polia budeme chcieť v našej uzla?

242
00:16:44,270 --> 00:16:46,520
[Študent] Int a potom dva ukazovatele?

243
00:16:46,520 --> 00:16:49,700
>> Int hodnota, dva ukazovatele? Ako písať ukazovateľov?

244
00:16:49,700 --> 00:16:58,440
[Študent] Struct. >> Mal by som priblížiť dovnútra Jo, tak struct uzol * vľavo,

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

246
00:17:01,320 --> 00:17:03,460
A pamätajte diskusiu od minule,

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

248
00:17:15,290 --> 00:17:18,270
To nedáva zmysel.

249
00:17:18,270 --> 00:17:25,000
Musíte všetko, čo sa s cieľom definovať túto rekurzívne struct.

250
00:17:25,000 --> 00:17:27,970
Dobre, tak to je to, čo náš strom bude vyzerať.

251
00:17:27,970 --> 00:17:37,670
Ak by sme urobili trinary strom, potom uzol môže vyzerať ako b1, b2, struct uzol * b3,

252
00:17:37,670 --> 00:17:43,470
kde b je vetva - vlastne, ja som počul, že viac vľavo, stredný, pravý, ale čo.

253
00:17:43,470 --> 00:17:55,610
My len o binárny, tak doprava, doľava.

254
00:17:55,610 --> 00:17:59,110
"Teraz vyhlásiť globálne uzol * premenné pre koreň stromu."

255
00:17:59,110 --> 00:18:01,510
Takže my nebudeme robiť, že.

256
00:18:01,510 --> 00:18:08,950
Aby sa veci trochu ťažšie a všeobecnejšie,

257
00:18:08,950 --> 00:18:11,570
nebudeme mať globálny uzla premennú.

258
00:18:11,570 --> 00:18:16,710
Namiesto toho, v hlavnej budeme deklarovať všetky naše uzla veci,

259
00:18:16,710 --> 00:18:20,500
a to znamená, že pod, keď sme rozbehnú

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

261
00:18:23,130 --> 00:18:27,410
miesto našich obsahuje funkcie len s použitím tohto globálneho uzla premennú,

262
00:18:27,410 --> 00:18:34,280
budeme mať trvať ako argument na strom, ktorý chceme, aby to spracovať.

263
00:18:34,280 --> 00:18:36,650
S globálne premennú mal robiť veci lepšie.

264
00:18:36,650 --> 00:18:42,310
Budeme robiť veci ťažšie.

265
00:18:42,310 --> 00:18:51,210
Teraz trvať minútu alebo tak, aby jednoducho takéto veci,

266
00:18:51,210 --> 00:18:57,690
kde vo vnútri hlavnej chcete vytvoriť tento strom, a to je všetko, čo chcete robiť.

267
00:18:57,690 --> 00:19:04,530
Skúste a postaviť sa k tomuto stromu v hlavnej funkcii.

268
00:19:42,760 --> 00:19:47,610
>> Dobre. Takže si ani nemusíte mať postavil strom celú cestu ešte.

269
00:19:47,610 --> 00:19:49,840
Ale niekto niečo, čo by som mohol vytiahnuť hore

270
00:19:49,840 --> 00:20:03,130
ukázať, ako by sa dalo začať budovať taký strom?

271
00:20:03,130 --> 00:20:08,080
[Študent] Niekto búchať, snaží sa dostať von.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Každý, kto vyhovuje ich stromu konštrukcia?

273
00:20:13,100 --> 00:20:15,520
[Študent] Jasne. Je to neurobil. >> To je v poriadku. Môžeme len dokončiť -

274
00:20:15,520 --> 00:20:26,860
oh, môžete si ju uložiť? Hurá.

275
00:20:26,860 --> 00:20:32,020
Takže tu máme - oh, som mierne orezané.

276
00:20:32,020 --> 00:20:34,770
Som priblíženie?

277
00:20:34,770 --> 00:20:37,730
Zväčšenie, prejdite von. >> Mám dotaz. Jo >>?

278
00:20:37,730 --> 00:20:44,410
[Študent] Pri definovaní struct, sú veci ako inicializovaná na niečo?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Dobre. Takže budete musieť inicializovať -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Pri definovaní, alebo pri deklarovaní struct,

281
00:20:50,450 --> 00:20:55,600
nie je inicializovaný v predvolenom nastavení, je to ako keď deklarovať int.

282
00:20:55,600 --> 00:20:59,020
Je to presne to isté. Je to ako každý z jednotlivých jeho oblastiach

283
00:20:59,020 --> 00:21:04,460
môže mať na odpadky hodnotu v ňom. >> A je možné definovať - ​​alebo vyhlásiť struct

284
00:21:04,460 --> 00:21:07,740
spôsobom, aby pri jej inicializovať?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Áno. Takže, skratka inicializácia syntaxe

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

287
00:21:18,660 --> 00:21:22,200
Existujú dva spôsoby, ako to urobiť môžeme. Myslím, že by sme mali skompilovať

288
00:21:22,200 --> 00:21:25,840
aby sa ubezpečil, zvonenie tiež to robí.

289
00:21:25,840 --> 00:21:28,510
Poradie argumentov, ktoré prichádza v struct,

290
00:21:28,510 --> 00:21:32,170
dáte ako poradie argumentov vnútri týchto zložených zátvoriek.

291
00:21:32,170 --> 00:21:35,690
Takže ak chcete inicializovať ju 9 a odišiel sa null a potom doprava bude null,

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

293
00:21:41,570 --> 00:21:47,890
Alternatívou je, a editor nemá rád túto syntax,

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

295
00:21:50,300 --> 00:22:01,800
ale alternatívou je niečo ako -

296
00:22:01,800 --> 00:22:04,190
tu, dám to na nový riadok.

297
00:22:04,190 --> 00:22:09,140
Môžete výslovne povedať, že som zabudol presnú syntax.

298
00:22:09,140 --> 00:22:13,110
Takže môžete explicitne riešiť podľa názvu, a hovoria,

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

300
00:22:21,570 --> 00:22:24,540
Hádam, že je potrebné tieto pravidlá čiarky.

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

302
00:22:29,110 --> 00:22:33,780
skutočne potrebujú poznať poradí struct,

303
00:22:33,780 --> 00:22:36,650
a keď toto čítate, je to oveľa jednoznačnejšie,

304
00:22:36,650 --> 00:22:41,920
o tom, čo je hodnota je inicializovaná.

305
00:22:41,920 --> 00:22:44,080
>> To sa stane, že je jedna z vecí, ktoré -

306
00:22:44,080 --> 00:22:49,100
tak, pre najviac sa rozdeliť, C + +, je nadmnožinou C.

307
00:22:49,100 --> 00:22:54,160
Môžete si vziať kód v C, presuňte ju do C + +, a to by malo zostaviť.

308
00:22:54,160 --> 00:22:59,570
To je jedna z vecí, ktoré C + + nepodporuje, takže ľudia nemajú tendenciu robiť.

309
00:22:59,570 --> 00:23:01,850
Ja neviem, či to je jediný dôvod, prečo ľudia nemajú tendenciu robiť to,

310
00:23:01,850 --> 00:23:10,540
ale prípad, kedy som potreboval použiť napríklad pre prácu s C + +, a tak som nemohol použiť.

311
00:23:10,540 --> 00:23:14,000
Ďalším príkladom niečoho, čo nefunguje s C + +, je

312
00:23:14,000 --> 00:23:16,940
ako malloc vracia "void *," technicky,

313
00:23:16,940 --> 00:23:20,200
ale vy ste mohli len povedať, char * x = malloc čokoľvek,

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é obsadenie nestáva v C + +.

316
00:23:25,450 --> 00:23:28,150
To by nebolo skompilovať, a vy by ste explicitne potreba povedať

317
00:23:28,150 --> 00:23:34,510
char *, malloc, čokoľvek, aby vrci char *.

318
00:23:34,510 --> 00:23:37,270
Nie je veľa vecí, ktoré C a C + + nezhodnú na,

319
00:23:37,270 --> 00:23:40,620
ale tie sú dva.

320
00:23:40,620 --> 00:23:43,120
Takže pôjdeme s touto syntaxou.

321
00:23:43,120 --> 00:23:46,150
Ale aj keď sme nešli s tým syntaxou,

322
00:23:46,150 --> 00:23:49,470
to, čo je - by mohlo byť zle s tým?

323
00:23:49,470 --> 00:23:52,170
[Študent] Ja nemusíte dereferencia to? Jo >>.

324
00:23:52,170 --> 00:23:55,110
Pamätajte si, že šípka má implicitné dereferencia,

325
00:23:55,110 --> 00:23:58,230
a tak, keď sme len do činenia s struct,

326
00:23:58,230 --> 00:24:04,300
chceme použiť. aby sa na pole vnútri struct.

327
00:24:04,300 --> 00:24:07,200
A len čas používame šípku je, keď chceme urobiť -

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

329
00:24:13,450 --> 00:24:17,020
že to, čo by to znamenalo, keby som šíp.

330
00:24:17,020 --> 00:24:24,600
Všetky arrow prostriedok je, dereferencia to, teraz som na struct, a môžem pole.

331
00:24:24,600 --> 00:24:28,040
Buď si pole priamo, alebo dereferencia a získať pole -

332
00:24:28,040 --> 00:24:30,380
Myslím, že by to malo byť hodnota.

333
00:24:30,380 --> 00:24:33,910
Ale tu sa zaoberám len struct, nie ukazovateľ na struct,

334
00:24:33,910 --> 00:24:38,780
a tak nemôžem použiť šípku.

335
00:24:38,780 --> 00:24:47,510
Ale tieto veci môžeme urobiť pre všetky 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
Potom môžeme nastaviť pobočky v náš strom, môžeme mať 7 -

339
00:25:16,470 --> 00:25:21,650
môžeme mať, že by sa jeho ľavá ukazovať na 3.

340
00:25:21,650 --> 00:25:25,130
Tak ako to urobíme?

341
00:25:25,130 --> 00:25:29,320
[Študenti, nezrozumiteľné] >> Jo. Sídlo node3,

342
00:25:29,320 --> 00:25:34,170
a ak ste nemali adresu, potom to jednoducho nebude zostavovať.

343
00:25:34,170 --> 00:25:38,190
Ale nezabudnite, že sa jedná o ukazovatele na najbližších uzlov.

344
00:25:38,190 --> 00:25:44,930
Pravé smerové 9,

345
00:25:44,930 --> 00:25:53,330
a 3 by mali ukazovať o práve na 6.

346
00:25:53,330 --> 00:25:58,480
Myslím, že to je všetko nastavené. Akékoľvek pripomienky či otázky?

347
00:25:58,480 --> 00:26:02,060
[Študent, nezrozumiteľné] Koreň bude 7.

348
00:26:02,060 --> 00:26:08,210
Môžeme len povedať, uzol * ptr =

349
00:26:08,210 --> 00:26:14,160
alebo koreň, = & node7.

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

351
00:26:20,730 --> 00:26:25,490
takže budeme chcieť napísať funkciu vložiť do tohto binárneho stromu

352
00:26:25,490 --> 00:26:34,230
a vložka je nevyhnutne bude volať malloc vytvoriť nový uzol pre tohto stromu.

353
00:26:34,230 --> 00:26:36,590
Tak sa veci dostať chaotický s tým, že niektoré uzly

354
00:26:36,590 --> 00:26:38,590
sú v súčasnej dobe vo fronte

355
00:26:38,590 --> 00:26:43,680
a ostatné uzly sú skončíme na halde, keď vložíme ich.

356
00:26:43,680 --> 00:26:47,640
To je úplne v poriadku, ale iba dôvod

357
00:26:47,640 --> 00:26:49,600
sme schopní to urobiť na zásobníku

358
00:26:49,600 --> 00:26:51,840
Je tomu tak preto, že je to taká sprisahanecké príklad, že vieme,

359
00:26:51,840 --> 00:26:56,360
strom má byť konštruované ako 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Ak by sme nemali, potom by sme nemali malloc na prvom mieste.

361
00:27:02,970 --> 00:27:06,160
Ako uvidíme o niečo neskôr, mali by sme byť malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Práve teraz je to úplne rozumné, aby na zásobníku,

363
00:27:08,570 --> 00:27:14,750
ale poďme zmeniť na malloc realizáciu.

364
00:27:14,750 --> 00:27:17,160
Takže každý z nich sa teraz bude niečo ako

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

366
00:27:24,240 --> 00:27:28,040
A teraz budeme musieť urobiť našu kontrolu.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Nechcel som, že -

368
00:27:34,010 --> 00:27:40,950
return 1, a potom môžeme urobiť node9->, pretože teraz je to ukazovateľ,

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 mať k tomu, že pre každú z týchto uzlov.

372
00:27:51,410 --> 00:27:57,490
Takže namiesto toho, poďme dať vnútri samostatná funkcia.

373
00:27:57,490 --> 00:28:00,620
Hovorme tomu uzol * build_node,

374
00:28:00,620 --> 00:28:09,050
a to je trochu podobný API, ktoré poskytujeme na Huffman kódovanie.

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

376
00:28:12,730 --> 00:28:20,520
a Deconstructor "funkcie" pre tie stromy a rovnaké pre lesy.

377
00:28:20,520 --> 00:28:22,570
>> Takže tu budeme mať inicializátor funkciu

378
00:28:22,570 --> 00:28:25,170
len vybudovať uzol pre nás.

379
00:28:25,170 --> 00:28:29,320
A to bude vyzerať skoro presne takto.

380
00:28:29,320 --> 00:28:32,230
A ja dokonca bude lenivý a nie zmeniť názov premennej,

381
00:28:32,230 --> 00:28:34,380
aj keď node9 nedáva zmysel.

382
00:28:34,380 --> 00:28:38,610
Oh, myslím, že node9 tieto hodnota by nemala byť 6.

383
00:28:38,610 --> 00:28:42,800
Teraz sa môžeme vrátiť node9.

384
00:28:42,800 --> 00:28:49,550
A tu by sme sa mali vrátiť null.

385
00:28:49,550 --> 00:28:52,690
Všetci sa dohodli na tomto build-a-uzol funkcie?

386
00:28:52,690 --> 00:28:59,780
Takže teraz môžeme len volať, že k vytvoreniu ľubovoľného uzla s danou hodnotou a null ukazovateľmi.

387
00:28:59,780 --> 00:29:09,750
Teraz môžeme nazvať to, že môžeme urobiť uzol * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
A poďme urobiť. . .

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 teraz chceme nastaviť rovnaké ukazovatele,

391
00:29:39,330 --> 00:29:42,470
s výnimkou teraz je všetko už z hľadiska ukazovateľov

392
00:29:42,470 --> 00:29:48,480
takže už nie je nutné adresu.

393
00:29:48,480 --> 00:29:56,300
Dobre. Takže to, čo je to posledné, čo chcem robiť?

394
00:29:56,300 --> 00:30:03,850
Tam je pre kontrolu chýb, že som to robiť.

395
00:30:03,850 --> 00:30:06,800
Čo stavať uzla návrat?

396
00:30:06,800 --> 00:30:11,660
[Študent, nezrozumiteľné] >> Jo. Ak malloc zlyhalo, bude to vráti null.

397
00:30:11,660 --> 00:30:16,460
Takže budem lenivo dať sem namiesto toho robil podmienku pre každého.

398
00:30:16,460 --> 00:30:22,320
Ak (node9 == NULL, alebo - ešte jednoduchšie,

399
00:30:22,320 --> 00:30:28,020
to je ekvivalentná len ak nie node9.

400
00:30:28,020 --> 00:30:38,310
Takže ak nie je node9, alebo nie node6, alebo nie node3, alebo nie node7, vráti 1.

401
00:30:38,310 --> 00:30:42,850
Možno by sme mali vytlačiť malloc zlyhalo, alebo tak niečo.

402
00:30:42,850 --> 00:30:46,680
[Študent] Je false rovná null rovnako?

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
Akékoľvek - skoro len 2 nulovej hodnoty null a nulové,

407
00:31:02,130 --> 00:31:07,900
false je len hash definovaná ako nula.

408
00:31:07,900 --> 00:31:13,030
To platí aj v prípade, my deklarovať globálne premenné.

409
00:31:13,030 --> 00:31:17,890
Ak by sme mali uzla * koreň tu,

410
00:31:17,890 --> 00:31:24,150
potom - za pekná vec, o globálnych premenných je to, že majú vždy počiatočnú hodnotu.

411
00:31:24,150 --> 00:31:27,500
To nie je pravda funkcií, ako vo vnútri tu,

412
00:31:27,500 --> 00:31:34,870
ak máme, rovnako ako, uzol * alebo uzol x.

413
00:31:34,870 --> 00:31:37,380
Nemáme poňatia, čo x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
alebo môžeme vytlačiť a môžu byť ľubovoľné.

415
00:31:40,700 --> 00:31:44,980
To nie je pravda, globálnych premenných.

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

417
00:31:47,450 --> 00:31:53,410
V predvolenom nastavení, všetko, čo je globálny, ak nie je výslovne inicializovaný nejakú hodnotu,

418
00:31:53,410 --> 00:31:57,390
má nulovú hodnotu ako hodnotu.

419
00:31:57,390 --> 00:32:01,150
Tak tu, uzol * root, nemáme explicitne inicializovať k ničomu,

420
00:32:01,150 --> 00:32:06,350
tak jeho východisková hodnota bude nulový, čo je nulová hodnota ukazovateľov.

421
00:32:06,350 --> 00:32:11,870
Predvolená hodnota x bude znamenať, ž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, pretože to je štruktúra, budú všetky oblasti struct byť nulové hodnoty.

424
00:32:21,070 --> 00:32:24,410
Nemusíme používať, že tu, hoci.

425
00:32:24,410 --> 00:32:27,320
[Študent] Tieto structs sú iné ako iné premenné, a ostatné premenné sú

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

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

428
00:32:36,220 --> 00:32:40,070
Ak je to v celosvetovom rozsahu, že má počiatočnú hodnotu. Dobre >>.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Buď počiatočná hodnota si ho alebo nula.

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

431
00:32:53,260 --> 00:32:58,390
>> Dobre. Takže ďalšiu časť otázky pýta,

432
00:32:58,390 --> 00:33:01,260
"Teraz chceme napísať funkciu nazvanú obsahuje

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

434
00:33:04,930 --> 00:33:08,340
Nebudeme robiť bool obsahuje int hodnotu.

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

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

437
00:33:22,380 --> 00:33:24,490
A potom sme tiež chystá odovzdať mu strom

438
00:33:24,490 --> 00:33:28,870
, Že by mal byť kontroluje, či má túto hodnotu.

439
00:33:28,870 --> 00:33:38,290
Takže uzol * strom). Dobre.

440
00:33:38,290 --> 00:33:44,440
A potom sme to tak dá nazvať niečím ako,

441
00:33:44,440 --> 00:33:46,090
možno budeme chcieť printf alebo tak niečo.

442
00:33:46,090 --> 00:33:51,040
Obsahuje 6, náš koreň.

443
00:33:51,040 --> 00:33:54,300
To by malo vrátiť jednu, alebo skutočný,

444
00:33:54,300 --> 00:33:59,390
vzhľadom k tomu, obsahuje 5 koreň by sa mal vrátiť false.

445
00:33:59,390 --> 00:34:02,690
Tak sa druhý na vykonanie tohto.

446
00:34:02,690 --> 00:34:06,780
Môžete to urobiť buď opakované alebo rekurzívne.

447
00:34:06,780 --> 00:34:09,739
Dobrá vec na tom, ako sme pripraviť veci je to, že

448
00:34:09,739 --> 00:34:12,300
to požičiava seba k nášmu rekurzívne riešenie oveľa jednoduchšie

449
00:34:12,300 --> 00:34:14,719
ako globálna premenná spôsobom urobil.

450
00:34:14,719 --> 00:34:19,750
Pretože ak budeme jednoducho musieť obsahuje int hodnotu, potom máme žiadny spôsob, ako recursing dole podstromy.

451
00:34:19,750 --> 00:34:24,130
Museli by sme mať samostatnú pomocnú funkciu, ktorá recurses stanovuje podstromy pre nás.

452
00:34:24,130 --> 00:34:29,610
Ale od tej doby sme zmenili, aby sa strom ako argument,

453
00:34:29,610 --> 00:34:32,760
ktoré by malo vždy byť na prvom mieste,

454
00:34:32,760 --> 00:34:35,710
Teraz môžeme recurse ľahšie.

455
00:34:35,710 --> 00:34:38,960
Takže iteratívny alebo rekurzívne, pôjdeme cez oba,

456
00:34:38,960 --> 00:34:46,139
ale uvidíme, že rekurzívne skončí ako bytia celkom jednoduché.

457
00:34:59,140 --> 00:35:02,480
Dobre. Má niekto niečo môžeme pracovať s?

458
00:35:02,480 --> 00:35:12,000
>> [Študent] Mám iteratívny riešenie. >> Dobre, iteratívny.

459
00:35:12,000 --> 00:35:16,030
Dobre, to vyzerá dobre.

460
00:35:16,030 --> 00:35:18,920
Takže, chcú ísť k nám cez to?

461
00:35:18,920 --> 00:35:25,780
[Študent] Jasne. Tak som nastaviť premennú TEMP získať prvý uzol stromu.

462
00:35:25,780 --> 00:35:28,330
A potom som prosmyčkovat, zatiaľ čo teplota sa nerovná null,

463
00:35:28,330 --> 00:35:31,700
takže aj keď bol ešte na strome, myslím.

464
00:35:31,700 --> 00:35:35,710
A v prípade, že hodnota je rovná hodnote, že teplota je ukazuje na,

465
00:35:35,710 --> 00:35:37,640
potom vráti túto hodnotu.

466
00:35:37,640 --> 00:35:40,210
V opačnom prípade, kontroluje, či je to na pravej strane alebo na ľavej strane.

467
00:35:40,210 --> 00:35:43,400
Ak ste niekedy situáciu, keď už nie je strom,

468
00:35:43,400 --> 00:35:47,330
potom sa vráti - to ukončí slučku a vráti false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Dobre. Takže to vyzerá dobre.

470
00:35:52,190 --> 00:35:58,470
Každý, kto má nejaké pripomienky na čokoľvek?

471
00:35:58,470 --> 00:36:02,400
Nemám korektnosť pripomienky vôbec.

472
00:36:02,400 --> 00:36:11,020
Jedna vec, ktorú môžeme urobiť, je to chlap.

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

474
00:36:21,660 --> 00:36:33,460
Urobím to vymyslel. Dobre.

475
00:36:33,460 --> 00:36:37,150
>> Každý by si mal uvedomiť, ako trojica funguje.

476
00:36:37,150 --> 00:36:38,610
Tam určite bola kvízov v minulosti

477
00:36:38,610 --> 00:36:41,170
ktoré vám funkciu s ternárnu operátor,

478
00:36:41,170 --> 00:36:45,750
a hovoria, to preložiť, urobiť niečo, čo nepoužíva trojzložkových.

479
00:36:45,750 --> 00:36:49,140
Takže je to veľmi bežný prípad, kedy by som si použiť ternárnu,

480
00:36:49,140 --> 00:36:54,610
kde v prípade niektorých podmienka nastaviť premennú na niečo,

481
00:36:54,610 --> 00:36:58,580
else nastaviť rovnakú premennú na niečo iné.

482
00:36:58,580 --> 00:37:03,390
To je niečo, čo veľmi často môže byť premenený na takéto veci

483
00:37:03,390 --> 00:37:14,420
kde nastaviť túto premennú na toto - alebo, no, je to pravda? Potom je táto, inak to.

484
00:37:14,420 --> 00:37:18,550
[Študent] Prvá z nich je, ak pravda, nie?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Jo. Spôsob, akým som vždy čítal, je teplota rovná hodnote väčšia ako temp hodnota,

486
00:37:25,570 --> 00:37:30,680
potom to, inak to. Je to pokladám otázku.

487
00:37:30,680 --> 00:37:35,200
Je to väčšie? Potom vykonajte prvá vec. Else to druhá vec.

488
00:37:35,200 --> 00:37:41,670
Aj takmer vždy - dvojbodka, ja len - v mojej hlave, som čítal, ako inak.

489
00:37:41,670 --> 00:37:47,180
>> Má niekto rekurzívne riešenie?

490
00:37:47,180 --> 00:37:49,670
Dobre. Tento budeme - to by už bolo skvelé,

491
00:37:49,670 --> 00:37:53,990
ale budeme robiť ešte lepšie.

492
00:37:53,990 --> 00:37:58,720
To je docela veľa rovnaký presný nápad.

493
00:37:58,720 --> 00:38:03,060
Je to len, no, chceš vysvetľovať?

494
00:38:03,060 --> 00:38:08,340
[Študent] Jasne. Takže sme uistite sa, že strom nie je null prvý,

495
00:38:08,340 --> 00:38:13,380
pretože ak je strom null potom to bude vrátiť false, pretože sme ho nenašli.

496
00:38:13,380 --> 00:38:19,200
A ak je to ešte strom, ideme do - sme najprv skontrolujte, či je hodnota aktuálnej uzol.

497
00:38:19,200 --> 00:38:23,740
Vracia true, ak je, a ak nie my recurse vľavo alebo vpravo.

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

499
00:38:25,970 --> 00:38:33,880
Takže si všimnúť, že je to takmer - štruktúrne veľmi podobné iteratívny riešenie.

500
00:38:33,880 --> 00:38:38,200
Je to len, že namiesto toho, aby recursing, mali sme while.

501
00:38:38,200 --> 00:38:40,840
A základné prípad, kedy strom nie je rovnaký null

502
00:38:40,840 --> 00:38:44,850
bola podmienka, za ktorej sme sa rozišli z cyklu while.

503
00:38:44,850 --> 00:38:50,200
Sú veľmi podobné. Ale budeme ešte o krok ďalej.

504
00:38:50,200 --> 00:38:54,190
Teraz to isté tu.

505
00:38:54,190 --> 00:38:57,680
Oznámenie sa vraciame rovnakú vec v oboch týchto tratiach,

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

507
00:39:00,220 --> 00:39:07,950
Takže budeme robiť, že do trojice.

508
00:39:07,950 --> 00:39:13,790
Trafil som možnosť niečo, a to robilo symbol. Dobre.

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

510
00:39:21,720 --> 00:39:28,030
Začína to byť viac riadkov, dobre, zväčšovať v ňom je.

511
00:39:28,030 --> 00:39:31,060
Obvykle, ako štylistický vec, nemyslím si, že veľa ľudí

512
00:39:31,060 --> 00:39:38,640
dať priestor po šíp, ale myslím, že ak ste v súlade, to je v poriadku.

513
00:39:38,640 --> 00:39:44,320
Ak je hodnota nižšia ako hodnota stromu, chceme recurse na strome naľavo,

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

515
00:39:53,890 --> 00:39:58,610
Takže to bol prvý krok urobiť z tohto pohľad menšie.

516
00:39:58,610 --> 00:40:02,660
Krok dva takže to pohľad menšie -

517
00:40:02,660 --> 00:40:09,150
môžeme oddeliť to do niekoľkých riadkov.

518
00:40:09,150 --> 00:40:16,500
Dobre. Krok dva, aby to vyzeralo menšie je tu,

519
00:40:16,500 --> 00:40:25,860
tak návratová hodnota rovná strom hodnotu, alebo obsahuje čokoľvek.

520
00:40:25,860 --> 00:40:28,340
>> To je dôležitá vec.

521
00:40:28,340 --> 00:40:30,860
Nie som si istý, či to povedal výslovne v triede,

522
00:40:30,860 --> 00:40:34,740
ale je to len skrat hodnotenie.

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

524
00:40:41,060 --> 00:40:49,960
Ak je to pravda, potom je to pravda, a my chceme, aby "alebo", že s tým, čo je tu.

525
00:40:49,960 --> 00:40:52,520
Takže bez premýšľania, čo je tu,

526
00:40:52,520 --> 00:40:55,070
to, čo je celý výraz bude vrátiť?

527
00:40:55,070 --> 00:40:59,430
[Študent] True? >> Jo, pretože pravda o ničom,

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

529
00:41:04,990 --> 00:41:08,150
Takže akonáhle vidíme návratovú hodnotu = strom hodnota,

530
00:41:08,150 --> 00:41:10,140
sme len tak vrátiť true.

531
00:41:10,140 --> 00:41:15,710
Ani ísť do recurse ďalej obsahuje dole riadok.

532
00:41:15,710 --> 00:41:20,980
Môžeme si vziať tento krok ďalej.

533
00:41:20,980 --> 00:41:29,490
Návrat strom nie je rovnaký neplatné a všetky z toho.

534
00:41:29,490 --> 00:41:32,650
To robilo to jeden-line funkcie.

535
00:41:32,650 --> 00:41:36,790
To je tiež príklad skrátené vyhodnocovanie.

536
00:41:36,790 --> 00:41:40,680
Ale teraz je to rovnaká myšlienka -

537
00:41:40,680 --> 00:41:47,320
miesto - takže ak strom sa nerovná null - alebo, dobre,

538
00:41:47,320 --> 00:41:49,580
ak strom sa rovná null, čo je ťažký prípad,

539
00:41:49,580 --> 00:41:54,790
ak strom rovná null, potom prvou podmienkou bude false.

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

541
00:42:00,550 --> 00:42:04,640
[Študent] False. Jo >>. To je druhá polovica skrátené vyhodnocovanie,

542
00:42:04,640 --> 00:42:10,710
kde, ak strom nie je rovné null, potom sa nebudeme ani ísť -

543
00:42:10,710 --> 00:42:14,930
alebo ak strom má rovnakú hodnotu null, potom nebudeme robiť hodnotu == strom hodnotu.

544
00:42:14,930 --> 00:42:17,010
Sme len tak aby sa okamžite vrátil false.

545
00:42:17,010 --> 00:42:20,970
Čo je dôležité, pretože ak nie skrat vyhodnotiť,

546
00:42:20,970 --> 00:42:25,860
potom ak strom má rovnakú hodnotu null, táto druhá podmienka bude k poruche seg,

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

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

549
00:42:40,490 --> 00:42:44,840
To je veľmi bežná vec tiež, nie robiť toto jeden riadok s tým,

550
00:42:44,840 --> 00:42:49,000
ale je to bežná vec v podmienkach, možno nie tu,

551
00:42:49,000 --> 00:42:59,380
ale ak (strom! = NULL, a strom-> value == hodnota), robiť čokoľvek.

552
00:42:59,380 --> 00:43:01,560
To je veľmi bežný stav, kedy namiesto toho, aby

553
00:43:01,560 --> 00:43:06,770
že sa to do dvoch IFS, kde ako je strom nulový?

554
00:43:06,770 --> 00:43:11,780
Dobre, to nie je null, tak teraz je to strom hodnota rovná hodnote? Urob to.

555
00:43:11,780 --> 00:43:17,300
Namiesto toho, že táto podmienka, bude to nikdy seg poruchu

556
00:43:17,300 --> 00:43:21,220
pretože to vypukne, ak sa to stane, že je null.

557
00:43:21,220 --> 00:43:24,000
No, myslím, že ak váš strom je úplne neplatný ukazovateľ, to môže ešte seg poruchu,

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

559
00:43:26,620 --> 00:43:32,900
Keby to bolo null, by to zlomiť, ako ste niekedy dereferenced ukazovateľ na prvom mieste.

560
00:43:32,900 --> 00:43:35,000
[Študent] Je to tzv lenivej vyhodnocovanie?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lenivé vyhodnocovanie je samostatná vec.

562
00:43:40,770 --> 00:43:49,880
Lenivé vyhodnocovanie je, ako by ste požiadať o hodnotu,

563
00:43:49,880 --> 00:43:54,270
pýtaš vypočítať hodnotu, druh, ale nemusíte ju hneď.

564
00:43:54,270 --> 00:43:59,040
Takže kým sa skutočne potrebovať, nie je hodnotená.

565
00:43:59,040 --> 00:44:03,920
To nie je úplne to isté, ale v Huffmanovo Pset,

566
00:44:03,920 --> 00:44:06,520
sa hovorí, že sme "lenivo" písať.

567
00:44:06,520 --> 00:44:08,670
Dôvod, prečo sme to urobiť, je preto, že sme vlastne vyrovnávacej pamäte write -

568
00:44:08,670 --> 00:44:11,820
Nechceme písať jednotlivé bity v čase,

569
00:44:11,820 --> 00:44:15,450
alebo jednotlivé byty v dobe, sme namiesto toho chce dostať kus bajtov.

570
00:44:15,450 --> 00:44:19,270
Potom, akonáhle budeme mať kus bajtov, potom budeme písať to.

571
00:44:19,270 --> 00:44:22,640
Aj keď ste požiadať ju písať - a fwrite a fread to rovnaký druh veci.

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

573
00:44:26,260 --> 00:44:31,610
Aj keď sa spýtate to písať hneď, to asi nebude.

574
00:44:31,610 --> 00:44:34,540
A môžete si byť istí, že sa veci majú byť zapísané

575
00:44:34,540 --> 00:44:37,540
kým nezavoláte hfclose alebo čo to je,

576
00:44:37,540 --> 00:44:39,620
ktorý potom hovorí, jo, ja Zatváram svoj súbor,

577
00:44:39,620 --> 00:44:43,450
to znamená, že som radšej napísať všetko, čo som nenapísal ešte.

578
00:44:43,450 --> 00:44:45,770
To nie je potrebné písať všetko von

579
00:44:45,770 --> 00:44:49,010
kým sa pri zatváraní súboru, a potom je treba.

580
00:44:49,010 --> 00:44:56,220
Takže to je práve to, čo lenivý - to počká, kým sa to musí stať.

581
00:44:56,220 --> 00:44:59,990
Tento - sa 51 a prejdete do neho podrobnejšie,

582
00:44:59,990 --> 00:45:05,470
pretože OCaml a všetko v 51, všetko je rekurzia.

583
00:45:05,470 --> 00:45:08,890
Nie sú k dispozícii žiadne iteratívny riešenie, v podstate.

584
00:45:08,890 --> 00:45:11,550
Všetko je rekurzia, a lenivé vyhodnocovanie

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

586
00:45:14,790 --> 00:45:19,920
kde, ak ste si lenivo vyhodnocovať, znamenalo by to -

587
00:45:19,920 --> 00:45:24,760
Príkladom je prúdy, ktoré sú nekonečne dlho.

588
00:45:24,760 --> 00:45:30,990
Teoreticky, môžete premýšľať o prirodzených čísel ako prúd 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Takže lenivo vyhodnotené veci sú v poriadku.

590
00:45:33,090 --> 00:45:37,210
Keď poviem, že chcem desiatej číslo, potom môžem hodnotiť až na desiate číslo.

591
00:45:37,210 --> 00:45:40,300
Ak chcem sté číslo, potom môžem hodnotiť až po sté číslo.

592
00:45:40,300 --> 00:45:46,290
Bez lenivé vyhodnocovanie, potom to bude snažiť zhodnotiť všetky čísla okamžite.

593
00:45:46,290 --> 00:45:50,000
Ste hodnotenie nekonečne veľa čísel, a to jednoducho nie je možné.

594
00:45:50,000 --> 00:45:52,080
Takže existuje veľa okolností, kedy lenivé vyhodnocovanie

595
00:45:52,080 --> 00:45:57,840
je len nevyhnutné na získanie veci do práce.

596
00:45:57,840 --> 00:46:05,260
>> Teraz chceme písať vložku, kde vložka bude

597
00:46:05,260 --> 00:46:08,430
Podobne zmena v jeho definícii.

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

599
00:46:10,470 --> 00:46:23,850
Budeme zmeniť na bool vložky (int hodnota, uzol * strom).

600
00:46:23,850 --> 00:46:29,120
Sme vlastne bude meniť, že opäť v trochu, uvidíme prečo.

601
00:46:29,120 --> 00:46:32,210
A poďme presunúť build_node, len pre kruci to,

602
00:46:32,210 --> 00:46:36,730
nad vložte takže nemáme písať funkcie prototyp.

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

604
00:46:42,450 --> 00:46:49,590
Dobre. Take minútu za to.

605
00:46:49,590 --> 00:46:52,130
Myslím, že som zachránil revíziu, ak chcete vytiahnuť z toho,

606
00:46:52,130 --> 00:47:00,240
alebo aspoň, som teraz.

607
00:47:00,240 --> 00:47:04,190
Chcel som mierny prestávku na premýšľanie o logike vložky,

608
00:47:04,190 --> 00:47:08,750
Ak nemôžete myslieť na to.

609
00:47:08,750 --> 00:47:12,860
V podstate, budete len niekedy vkladanie na listy.

610
00:47:12,860 --> 00:47:18,640
Rovnako ako, keď som vložiť 1, potom som nevyhnutne bude vkladanie 1 -

611
00:47:18,640 --> 00:47:21,820
Budem sa zmení na čiernu - Budem sa vloží 1 sem.

612
00:47:21,820 --> 00:47:28,070
Alebo keď som vložiť 4, chcem sa vloží 4 sem.

613
00:47:28,070 --> 00:47:32,180
Takže bez ohľadu na to, čo robíte, budete sa vloží na list.

614
00:47:32,180 --> 00:47:36,130
Jediné, čo musíte urobiť, je iterácii výrub, až sa dostanete do uzla

615
00:47:36,130 --> 00:47:40,890
ktoré by mali byť v uzle rodič, nového uzla rodič,

616
00:47:40,890 --> 00:47:44,560
a potom zmeniť jeho ľavej alebo pravej myši, v závislosti na tom, či

617
00:47:44,560 --> 00:47:47,060
to je väčšia než alebo menšie, než je aktuálna uzol.

618
00:47:47,060 --> 00:47:51,180
Zmena tento ukazovateľ poukázať na svojho nového uzla.

619
00:47:51,180 --> 00:48:05,490
Takže určiť iteráciou výrub, aby sa list bod nového uzla.

620
00:48:05,490 --> 00:48:09,810
Tiež si myslím, že o tom, prečo zakazuje typ situácie pred,

621
00:48:09,810 --> 00:48:17,990
kde som postavil binárny strom, kde to bolo správne

622
00:48:17,990 --> 00:48:19,920
ak ste len pozrel na jedného uzla,

623
00:48:19,920 --> 00:48:24,830
ale 9 bol na ľavej strane 7, ak si zopakovali úplne dole.

624
00:48:24,830 --> 00:48:29,770
Tak to je možné v tomto scenári, pretože -

625
00:48:29,770 --> 00:48:32,530
premýšľať o vkladanie 9 alebo niečo, na prvom uzla,

626
00:48:32,530 --> 00:48:35,350
Idem vidieť 7 a ja som len ísť doprava.

627
00:48:35,350 --> 00:48:38,490
Takže bez ohľadu na to, čo mám robiť, keď mám vložením tým, že pôjdete na liste,

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

629
00:48:40,790 --> 00:48:43,130
to bude pre mňa nemožné vložiť 9 naľavo 7

630
00:48:43,130 --> 00:48:48,250
pretože akonáhle som narazila 7 som ísť doprava.

631
00:48:59,740 --> 00:49:02,070
Má niekto niečo začať?

632
00:49:02,070 --> 00:49:05,480
[Študent] ja. Iste >>.

633
00:49:05,480 --> 00:49:09,200
[Študent, nezrozumiteľným]

634
00:49:09,200 --> 00:49:14,390
[Ostatné študent, nezrozumiteľným]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Je to ocenil. Dobre. Chcete vysvetliť?

636
00:49:18,330 --> 00:49:20,690
>> [Študent] Pretože vieme, že sme vkladanie

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

638
00:49:24,060 --> 00:49:28,070
Aj prosmyčkovat stromu iteratívne

639
00:49:28,070 --> 00:49:31,360
kým som sa nedostal k uzlu, ktorá ukazovala na nulu.

640
00:49:31,360 --> 00:49:34,220
A potom som sa rozhodol dať ho buď na pravej strane alebo na ľavej strane

641
00:49:34,220 --> 00:49:37,420
tohto práva využívajú premenné, to mi povedal, kam to dať.

642
00:49:37,420 --> 00:49:41,850
A potom, v podstate som len robil, že posledný -

643
00:49:41,850 --> 00:49:47,520
že teplota uzol bod na nový uzol, ktorý bol vytváraného

644
00:49:47,520 --> 00:49:50,770
buď na ľavej strane, alebo na pravej strane, v závislosti na tom, čo je hodnota práv bol.

645
00:49:50,770 --> 00:49:56,530
Nakoniec som nastaviť nový uzol hodnoty na hodnotu jeho testovanie.

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

647
00:49:59,550 --> 00:50:02,050
To je ako 95% ceste tam.

648
00:50:02,050 --> 00:50:07,550
Jeden problém, ktorý vidím, dobre, niekto iný vidieť problém?

649
00:50:07,550 --> 00:50:18,400
Čo je okolnosť, pod ktorou vymaniť sa z slučky?

650
00:50:18,400 --> 00:50:22,100
[Študent] Ak teplota je null? Jo >>. Tak ako sa vymaniť zo slučky, ak je teplota je null.

651
00:50:22,100 --> 00:50:30,220
Ale čo mám robiť tu?

652
00:50:30,220 --> 00:50:35,410
Aj dereferencia temp, ktorý je nevyhnutne null.

653
00:50:35,410 --> 00:50:39,840
Takže ďalšia vec, ktorú musíte urobiť, je nielen sledovať, kým teplota je null,

654
00:50:39,840 --> 00:50:45,590
Ak chcete sledovať rodičia za všetkých okolností.

655
00:50:45,590 --> 00:50:52,190
Chceme tiež, aby uzol * rodičia, myslím, že môžeme mať, že pri nulovom na prvom mieste.

656
00:50:52,190 --> 00:50:55,480
To bude mať podivné správanie pre koreň stromu,

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

658
00:50:59,210 --> 00:51:03,950
Ak je hodnota vyššia než čokoľvek, potom temp = temp pravdu.

659
00:51:03,950 --> 00:51:07,910
Ale predtým, než to urobíme, rodič = temp.

660
00:51:07,910 --> 00:51:14,500
Alebo sa rodičia vždy rovnaké teploty? Je to tak?

661
00:51:14,500 --> 00:51:19,560
Ak teplota nie je null, potom budem pohybovať dole, bez ohľadu na to,

662
00:51:19,560 --> 00:51:24,030
do uzla, pre ktorý temp je rodič.

663
00:51:24,030 --> 00:51:27,500
Takže rodičia to bude temp, a potom som sa presunúť teplota dole.

664
00:51:27,500 --> 00:51:32,410
Teraz teplota je null, ale rodičia poukazuje na rodičov na vec, ktorá je null.

665
00:51:32,410 --> 00:51:39,110
Takže tu dole, nechcem, aby na pravú mieru sa rovná 1.

666
00:51:39,110 --> 00:51:41,300
Tak som sa pohyboval napravo, takže ak P = 1,

667
00:51:41,300 --> 00:51:45,130
a myslím, že budete tiež chcieť urobiť -

668
00:51:45,130 --> 00:51:48,530
ak presuniete vľavo, ktorú chcete nastaviť priamo rovná 0.

669
00:51:48,530 --> 00:51:55,950
Alebo, ak ste niekedy posunie doprava.

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

671
00:51:58,590 --> 00:52:04,260
Teraz chceme, aby sa materský správny ukazovateľ newnode,

672
00:52:04,260 --> 00:52:08,520
inak by sme chcieť, aby materské ľavej ukazovateľ newnode.

673
00:52:08,520 --> 00:52:16,850
Otázky týkajúce sa, že?

674
00:52:16,850 --> 00:52:24,880
Dobre. Tak toto je spôsob, ako - no, vlastne, miesto toho, čo robíme,

675
00:52:24,880 --> 00:52:29,630
sme napoly očakával, môžete použiť build_node.

676
00:52:29,630 --> 00:52:40,450
A potom, keď newnode rovná null, vráti false.

677
00:52:40,450 --> 00:52:44,170
To je to. Teraz, to je to, čo sme očakávali, aby si urobil.

678
00:52:44,170 --> 00:52:47,690
>> To je to, čo zamestnanci riešenie robiť.

679
00:52:47,690 --> 00:52:52,360
Nesúhlasím s tým, ako "správne" spôsob, ako ísť na to

680
00:52:52,360 --> 00:52:57,820
ale to je úplne v poriadku a že to bude fungovať.

681
00:52:57,820 --> 00:53:02,840
Jedna vec, ktorá je trochu divné je teraz

682
00:53:02,840 --> 00:53:08,310
ak strom začína za neplatné, míňame v nulovej stromu.

683
00:53:08,310 --> 00:53:12,650
Myslím, že to záleží na tom, ako definovať správanie prejde v nulovej stromu.

684
00:53:12,650 --> 00:53:15,490
Povedal by som, že ak omdliete v nulovej stromu,

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

686
00:53:17,520 --> 00:53:23,030
mal jednoducho vrátiť strom, kde jedinou hodnotou je, že jeden uzol.

687
00:53:23,030 --> 00:53:25,830
Ľudia s tým súhlasíte? Dalo by sa, ak by ste chceli,

688
00:53:25,830 --> 00:53:28,050
ak predáte null stromu

689
00:53:28,050 --> 00:53:31,320
a chcete vložiť hodnotu do neho, vráti false.

690
00:53:31,320 --> 00:53:33,830
Je na vás, aby ste definovať, že.

691
00:53:33,830 --> 00:53:38,320
Ak chcete urobiť prvá vec, ktorú som povedal, a potom -

692
00:53:38,320 --> 00:53:40,720
dobre, budete mať ťažkosti robí, že, pretože

693
00:53:40,720 --> 00:53:44,090
že by bolo jednoduchšie, keby sme mali globálny ukazovateľ na vec,

694
00:53:44,090 --> 00:53:48,570
ale nemáme, takže ak strom je null, nie je nič, čo môže robiť, že.

695
00:53:48,570 --> 00:53:50,960
Môžeme len vráti false.

696
00:53:50,960 --> 00:53:52,840
Takže budem meniť vložku.

697
00:53:52,840 --> 00:53:56,540
My technicky mohol len zmeniť toto právo tu,

698
00:53:56,540 --> 00:53:58,400
ako to iterácia nad vecami,

699
00:53:58,400 --> 00:54:04,530
ale budem meniť vložku, aby sa uzol ** strom.

700
00:54:04,530 --> 00:54:07,510
Dvojlôžkové ukazovatele.

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

702
00:54:09,710 --> 00:54:12,330
Miesto zaoberanie sa ukazovateľov na uzly,

703
00:54:12,330 --> 00:54:16,690
čo budem sa manipulovať, je tento ukazovateľ.

704
00:54:16,690 --> 00:54:18,790
Budem sa manipulovať tento ukazovateľ.

705
00:54:18,790 --> 00:54:21,770
Budem sa manipulovať ukazovatele priamo.

706
00:54:21,770 --> 00:54:25,760
To dáva zmysel, pretože, myslím, že o tom sa -

707
00:54:25,760 --> 00:54:33,340
dobre, teraz tento bodov na hodnotu null.

708
00:54:33,340 --> 00:54:38,130
To, čo chcem urobiť, je manipulovať tento ukazovateľ poukázať na NOT NULL.

709
00:54:38,130 --> 00:54:40,970
Chcem, aby to poukázať na môj nový uzol.

710
00:54:40,970 --> 00:54:44,870
Keby som len sledovať ukazovatele na mojich ukazovateľov,

711
00:54:44,870 --> 00:54:47,840
potom som nemusíte sledovať materskej ukazovateľ.

712
00:54:47,840 --> 00:54:52,640
Môžem len sledovať, či je ukazovateľ ukazuje na null,

713
00:54:52,640 --> 00:54:54,580
a ak ukazovateľ ukazuje na null,

714
00:54:54,580 --> 00:54:57,370
zmeniť, aby ukazoval na uzol chcem.

715
00:54:57,370 --> 00:55:00,070
A môžem zmeniť to, pretože mám ukazovateľ na ukazovateľ.

716
00:55:00,070 --> 00:55:02,040
Poďme sa pozrieť práve teraz.

717
00:55:02,040 --> 00:55:05,470
Môžete si skutočne urobiť rekurzívne celkom ľahko.

718
00:55:05,470 --> 00:55:08,080
Chceme urobiť?

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

720
00:55:10,980 --> 00:55:16,790
>> Poďme sa pozrieť, to rekurzívne.

721
00:55:16,790 --> 00:55:24,070
Po prvé, to, čo je naša základňa prípad bude?

722
00:55:24,070 --> 00:55:29,140
Takmer vždy náš základný scenár, ale v skutočnosti, to je trochu zložitejšie.

723
00:55:29,140 --> 00:55:34,370
Prvé vecí, prvý, if (tree == NULL)

724
00:55:34,370 --> 00:55:37,550
Myslím, že sme len tak vrátiť false.

725
00:55:37,550 --> 00:55:40,460
To sa líši od svojho stromu bytia null.

726
00:55:40,460 --> 00:55:44,510
To je ukazovateľ na vašom koreňovom ukazovatele zatiaľ null

727
00:55:44,510 --> 00:55:48,360
čo znamená, že koreňová ukazovateľ neexistuje.

728
00:55:48,360 --> 00:55:52,390
Takže tu dole, keď to urobím

729
00:55:52,390 --> 00:55:55,760
uzol * - povedzme znovu to.

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

731
00:55:58,960 --> 00:56:00,730
a potom budem volať vložky tým, že robí niečo ako,

732
00:56:00,730 --> 00:56:04,540
vložiť do 4 & koreňa.

733
00:56:04,540 --> 00:56:06,560
Tak a koreň, ak je koreň uzol *

734
00:56:06,560 --> 00:56:11,170
potom a koreň bude uzla **.

735
00:56:11,170 --> 00:56:15,120
To je platné. V tomto prípade, strom, tu,

736
00:56:15,120 --> 00:56:20,120
Strom nie je null - alebo vložka.

737
00:56:20,120 --> 00:56:24,630
Tu. Strom nie je nula, * strom je nulový, čo je v poriadku

738
00:56:24,630 --> 00:56:26,680
pretože ak * strom je null, potom som si s ním manipulovať

739
00:56:26,680 --> 00:56:29,210
Doteraz poukázať na to, čo chcem, aby to odkazovať.

740
00:56:29,210 --> 00:56:34,750
Ale ak strom je null, to znamená, že som sem prišiel a povedal null.

741
00:56:34,750 --> 00:56:42,710
To nedáva zmysel. Nemôžem nič robiť s tým.

742
00:56:42,710 --> 00:56:45,540
Ak je strom null, vráti false.

743
00:56:45,540 --> 00:56:48,220
Takže som v podstate už povedal, čo naša skutočná základňa prípad je.

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

745
00:56:50,580 --> 00:56:55,030
[Študent, nezrozumiteľným]

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

747
00:57:00,000 --> 00:57:04,520
To sa týka prípadu sem

748
00:57:04,520 --> 00:57:09,640
kde, ak má červený ukazovateľ je ukazovateľ som sa zameral na,

749
00:57:09,640 --> 00:57:12,960
tak, ako by som sa zameral na tohto ukazovateľa, teraz som sa zameral na tomto ukazovateli.

750
00:57:12,960 --> 00:57:15,150
Teraz som sa zameral na tomto ukazovateli.

751
00:57:15,150 --> 00:57:18,160
Takže ak má červený ukazovateľ, ktorý je môj uzol **,

752
00:57:18,160 --> 00:57:22,880
je vždy - ak *, môj červený ukazovateľ, je stále null,

753
00:57:22,880 --> 00:57:28,470
to znamená, že som v prípade, kedy som so zameraním na ukazovateľ, ktorý ukazuje -

754
00:57:28,470 --> 00:57:32,530
to je ukazovateľ, ktorý patrí k listu.

755
00:57:32,530 --> 00:57:41,090
Chcem zmeniť tento ukazovateľ aby ukazoval na môj nový uzol.

756
00:57:41,090 --> 00:57:45,230
Vráťte sa sem.

757
00:57:45,230 --> 00:57:56,490
Môj newnode bude len uzol * n = build_node (hodnota)

758
00:57:56,490 --> 00:58:07,300
potom n, ak n = NULL, vráti false.

759
00:58:07,300 --> 00:58:12,600
Else chceme zmeniť to, čo sa ukazovateľ je v súčasnej dobe ukazuje na

760
00:58:12,600 --> 00:58:17,830
sa teraz ukazujú na našej novo postavené uzla.

761
00:58:17,830 --> 00:58:20,280
Môžeme skutočne urobiť tu.

762
00:58:20,280 --> 00:58:30,660
Namiesto toho povedal n, hovoríme, * tree = ak * stromu.

763
00:58:30,660 --> 00:58:35,450
Všetci pochopili, že? Že rokovania s ukazovateľmi na ukazovatele,

764
00:58:35,450 --> 00:58:40,750
môžeme zmeniť Null ukazovatele poukázať na veci, ktoré chceme, aby odkazovať.

765
00:58:40,750 --> 00:58:42,820
To je náš základný scenár.

766
00:58:42,820 --> 00:58:45,740
>> Teraz náš recidívy, alebo naše rekurzia,

767
00:58:45,740 --> 00:58:51,430
bude veľmi podobný všetkým ostatným rekurzia sme robili.

768
00:58:51,430 --> 00:58:55,830
Budeme chcieť vložiť hodnotu,

769
00:58:55,830 --> 00:58:59,040
a teraz budem používať ternárnu znova, ale to, čo je naša podmienka bude?

770
00:58:59,040 --> 00:59:05,180
Čo je to, čo hľadáme rozhodnúť, či chceme ísť doľava alebo doprava?

771
00:59:05,180 --> 00:59:07,760
Poďme to v samostatných krokoch.

772
00:59:07,760 --> 00:59:18,850
Ak (hodnota <), čo?

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

774
00:59:23,200 --> 00:59:27,490
[Bowden] Takže nezabudnite, že som v súčasnej dobe -

775
00:59:27,490 --> 00:59:31,260
[Študenti, nezrozumiteľné]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Jo, tak tu, povedzme, že táto zelená šípka

777
00:59:34,140 --> 00:59:39,050
je príkladom toho, čo je v súčasnej dobe strom, je ukazovateľ na tento ukazovateľ.

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

779
00:59:46,610 --> 00:59:48,800
The dereferencia dvakrát znelo to dobre.

780
00:59:48,800 --> 00:59:51,010
Čo mám - ako to mám urobiť, že?

781
00:59:51,010 --> 00:59:53,210
[Študent] dereferencia raz, a potom vykonajte arrow takto?

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

783
00:59:58,420 --> 01:00:05,960
bude mi hodnotu uzla, ktorý som nepriamo ukazuje.

784
01:00:05,960 --> 01:00:11,980
Tak som si tiež napísať, že ** tree.value ak si to prajete.

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

786
01:00:18,490 --> 01:00:26,190
Ak tomu tak je, potom chcem zavolať vložiť s hodnotou.

787
01:00:26,190 --> 01:00:32,590
A to, čo je moje aktualizovaný uzol ** bude?

788
01:00:32,590 --> 01:00:39,440
Chcem ísť doľava, takže ** tree.left bude moja ľavá.

789
01:00:39,440 --> 01:00:41,900
A chcem, aby ukazovateľ na tej veci

790
01:00:41,900 --> 01:00:44,930
tak, že v prípade, že ľavá nakoniec je nulová ukazovateľ,

791
01:00:44,930 --> 01:00:48,360
Ja ju upraviť, aby ukazoval na môj nový uzol.

792
01:00:48,360 --> 01:00:51,460
>> A druhý prípad môže byť veľmi podobné.

793
01:00:51,460 --> 01:00:55,600
Poďme vlastne urobiť, aby moje trojica práve teraz.

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

795
01:01:04,480 --> 01:01:11,040
Potom chceme aktualizovať naše ** doľava,

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

797
01:01:17,030 --> 01:01:22,540
[Študent] Znamená to, že sa ukazovateľ na ukazovateľ?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Nezabudnite, že - ** tree.right je uzol hviezda.

799
01:01:30,940 --> 01:01:35,040
[Študent, nezrozumiteľné] >> Jo.

800
01:01:35,040 --> 01:01:41,140
** Tree.right je ako tento ukazovateľ, alebo tak niečo.

801
01:01:41,140 --> 01:01:45,140
Takže tým, že ukazovateľ na to, že mi dáva to, čo chcem

802
01:01:45,140 --> 01:01:50,090
o ukazovateľ na toho chlapa.

803
01:01:50,090 --> 01:01:54,260
[Študent] Mohli by sme ísť znovu, prečo sme pomocou dvoch ukazovateľov?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Jo. Takže - nie, môžete, a že riešenie pred

805
01:01:58,220 --> 01:02:04,540
Bol to spôsob, ako to urobiť bez toho, aby robili dva ukazovatele.

806
01:02:04,540 --> 01:02:08,740
Musíte byť schopní pochopiť pomocou dvoch ukazovateľov,

807
01:02:08,740 --> 01:02:11,660
a to je čistejšie riešenie.

808
01:02:11,660 --> 01:02:16,090
Všimnite si tiež, že to, čo sa stane, keď môj strom -

809
01:02:16,090 --> 01:02:24,480
čo sa stane, keď moja koreňom boli null? Čo sa stane, keď urobím tento prípad tu?

810
01:02:24,480 --> 01:02:30,540
Takže uzol * root = NULL, vložte 4 do & koreňa.

811
01:02:30,540 --> 01:02:35,110
Čo je koreň bude po tomhle?

812
01:02:35,110 --> 01:02:37,470
[Študent, nezrozumiteľné] >> Jo.

813
01:02:37,470 --> 01:02:41,710
Root hodnota bude 4.

814
01:02:41,710 --> 01:02:45,510
Root vľavo bude null, koreň právo bude null.

815
01:02:45,510 --> 01:02:49,490
V prípade, kedy sa neprešiel korene adresou,

816
01:02:49,490 --> 01:02:52,490
sme nemohli meniť koreň.

817
01:02:52,490 --> 01:02:56,020
V prípade, že sa strom - kde root je nulový,

818
01:02:56,020 --> 01:02:58,410
sme jednoducho museli vrátiť false. Nie je nič, čo by sme mohli urobiť.

819
01:02:58,410 --> 01:03:01,520
Nemôžeme vložiť uzol do prázdnej stromu.

820
01:03:01,520 --> 01:03:06,810
Ale teraz môžeme, sme jednoducho urobiť prázdny strom do jedného uzla stromu.

821
01:03:06,810 --> 01:03:13,400
Ktorý je obvykle očakávaným spôsobom, že by to malo fungovať.

822
01:03:13,400 --> 01:03:21,610
>> Ďalej, čo je podstatne kratšia ako

823
01:03:21,610 --> 01:03:26,240
tiež udržiavanie prehľadu o rodičov, a tak budete určiť iteráciou úplne dole.

824
01:03:26,240 --> 01:03:30,140
Teraz mám rodičia, a ja som so svojou materskou vpravo ukazovateľ na čokoľvek.

825
01:03:30,140 --> 01:03:35,640
Namiesto toho, či sme to urobili iteratívne, bolo by to rovnaká myšlienka s slučky while.

826
01:03:35,640 --> 01:03:38,100
Ale namiesto toho, aby sa museli vysporiadať s mojím materským ukazovateľom,

827
01:03:38,100 --> 01:03:40,600
miesto môj súčasný ukazovateľ by vec

828
01:03:40,600 --> 01:03:43,790
že som sa priamo mení na bod na môj nový uzol.

829
01:03:43,790 --> 01:03:46,090
Nemám sa zaoberať, či je to ukázal na ľavej strane.

830
01:03:46,090 --> 01:03:48,810
Nemám sa zaoberať, či je to orientovaná napravo.

831
01:03:48,810 --> 01:04:00,860
Je to len, čo tento ukazovateľ je, budem ju nastaviť, aby ukazoval na môj nový uzol.

832
01:04:00,860 --> 01:04:05,740
Všetci pochopili, ako to funguje?

833
01:04:05,740 --> 01:04:09,460
Ak nie, prečo to chceme urobiť takto,

834
01:04:09,460 --> 01:04:14,920
ale aspoň, že to funguje ako riešenie?

835
01:04:14,920 --> 01:04:17,110
[Študent] Kde sa vrátime pravda?

836
01:04:17,110 --> 01:04:21,550
[Bowden] To je asi tu.

837
01:04:21,550 --> 01:04:26,690
Ak sme správne vložiť, vrátiť true.

838
01:04:26,690 --> 01:04:32,010
Else, tu dole budeme chcieť vrátiť bez ohľadu vkladanie výnosy.

839
01:04:32,010 --> 01:04:35,950
>> A čo je zvláštne na tomto rekurzívne funkcie?

840
01:04:35,950 --> 01:04:43,010
Je to tail rekurzívne, tak dlho, ako sme kompilovat s nejakou optimalizáciou,

841
01:04:43,010 --> 01:04:48,060
bude si to uvedomiť a nikdy sa pretečeniu zásobníka z toho,

842
01:04:48,060 --> 01:04:53,230
aj keď náš strom má výšku 10.000 alebo 10 miliónov.

843
01:04:53,230 --> 01:04:55,630
[Študent, nezrozumiteľným]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Myslím, že to robí na Dash - alebo čo úroveň optimalizácie

845
01:05:00,310 --> 01:05:03,820
je vyžadované pre koncové rekurzia má byť uznané.

846
01:05:03,820 --> 01:05:09,350
Myslím, že to uznáva - GCC a zvonenie

847
01:05:09,350 --> 01:05:12,610
tiež majú rôzny význam pre ich optimalizáciu úrovne.

848
01:05:12,610 --> 01:05:17,870
Chcem povedať, že to Dash 2, pre istotu, že budú uznávať rekurzia chvosta.

849
01:05:17,870 --> 01:05:27,880
Ale my - môžete postaviť ako napríklad Fibonocci alebo tak niečo.

850
01:05:27,880 --> 01:05:30,030
Nie je to ľahké otestovať s tým, pretože je ťažké postaviť

851
01:05:30,030 --> 01:05:32,600
binárny strom, ktorý je tak veľký.

852
01:05:32,600 --> 01:05:37,140
Ale jo, myslím, že je to Dash 2, že

853
01:05:37,140 --> 01:05:40,580
ak pri kompilácii s Dash 2, bude to vyzerať pre koncových rekurzia

854
01:05:40,580 --> 01:05:54,030
a optimalizovať to von.

855
01:05:54,030 --> 01:05:58,190
Poďme späť k - vložiť to doslova posledná vec, ktorú potrebuje.

856
01:05:58,190 --> 01:06:04,900
Poďme sa vrátiť k vložky sem

857
01:06:04,900 --> 01:06:07,840
kde budeme robiť rovnakú myšlienku.

858
01:06:07,840 --> 01:06:14,340
To bude mať stále nedostatok, že nie je schopný úplne zvládnuť

859
01:06:14,340 --> 01:06:17,940
keď koreň sám je nulový, alebo cez vstup je nulový,

860
01:06:17,940 --> 01:06:20,060
ale namiesto toho sa zaoberá materskej ukazovateľ,

861
01:06:20,060 --> 01:06:27,430
Poďme používať rovnakú logiku vedenie ukazovateľov na ukazovatele.

862
01:06:27,430 --> 01:06:35,580
Ak tu budeme držať naše uzol ** teraz,

863
01:06:35,580 --> 01:06:37,860
a nepotrebujeme sledovať priamo už,

864
01:06:37,860 --> 01:06:47,190
ale uzol ** cur = & tree.

865
01:06:47,190 --> 01:06:54,800
A teraz naše, kým slučka bude zároveň * teraz sa nerovná null.

866
01:06:54,800 --> 01:07:00,270
Nemusíte sledovať rodičov už.

867
01:07:00,270 --> 01:07:04,180
Nemusíte sledovať pomocou ľavej a pravej.

868
01:07:04,180 --> 01:07:10,190
A ja budem hovoriť temp, pretože sme už používate temp.

869
01:07:10,190 --> 01:07:17,200
Dobre. Takže ak (hodnota> * temp),

870
01:07:17,200 --> 01:07:24,010
potom a (* temp) -> P

871
01:07:24,010 --> 01:07:29,250
else temp = & (* temp) -> vľavo.

872
01:07:29,250 --> 01:07:32,730
A teraz, v tomto okamihu, po tomto cykle while,

873
01:07:32,730 --> 01:07:36,380
Len som to preto, že je to možno jednoduchšie premýšľať o opakované, ako rekurzívne,

874
01:07:36,380 --> 01:07:39,010
ale po tomto cykle while,

875
01:07:39,010 --> 01:07:43,820
* Teplota je ukazovateľ chceme zmeniť.

876
01:07:43,820 --> 01:07:48,960
>> Než sme mali rodičia, a chceli sme zmeniť buď materskú doľava alebo rodičia vpravo,

877
01:07:48,960 --> 01:07:51,310
ale ak chceme zmeniť materskej právo,

878
01:07:51,310 --> 01:07:54,550
potom * teplota je rodič pravdu, a môžeme zmeniť priamo.

879
01:07:54,550 --> 01:08:05,860
Takže tu dole, môžeme urobiť * temp = newnode, a to je všetko.

880
01:08:05,860 --> 01:08:09,540
Takže upozornenie, všetko, čo sme robili v to uzavrieť riadky kódu.

881
01:08:09,540 --> 01:08:14,770
V záujme sledovať rodičia vo všetkom, čo je ďalšie úsilie.

882
01:08:14,770 --> 01:08:18,689
Tu, ak sa len sledovať ukazovateľ na ukazovateľ,

883
01:08:18,689 --> 01:08:22,990
a dokonca aj keby sme chceli zbaviť všetkých týchto zložených zátvoriek teraz,

884
01:08:22,990 --> 01:08:27,170
aby to vyzeralo kratšia.

885
01:08:27,170 --> 01:08:32,529
To je teraz presne rovnaké riešenie,

886
01:08:32,529 --> 01:08:38,210
ale menej riadkov kódu.

887
01:08:38,210 --> 01:08:41,229
Akonáhle začnete rozpoznávať to ako platný riešenie,

888
01:08:41,229 --> 01:08:43,529
je to tiež jednoduchšie uvažovať o než ako, jo,

889
01:08:43,529 --> 01:08:45,779
prečo mám tento príznak na int vpravo?

890
01:08:45,779 --> 01:08:49,290
Čo to znamená? Oh, to znamenať, že

891
01:08:49,290 --> 01:08:51,370
Zakaždým, keď idem pravdu, musím nastaviť,

892
01:08:51,370 --> 01:08:53,819
else if Aj choďte doľava musím nastaviť na nulu.

893
01:08:53,819 --> 01:09:04,060
Tu, nemám na dôvod, prečo o tom, že je to proste jednoduchšie myslieť.

894
01:09:04,060 --> 01:09:06,710
Otázky?

895
01:09:06,710 --> 01:09:16,290
[Študent, nezrozumiteľné] >> Jo.

896
01:09:16,290 --> 01:09:23,359
Dobre, takže v poslednej bit -

897
01:09:23,359 --> 01:09:28,080
Myslím, že jedna rýchla a jednoduchá funkcia, ktorú môžeme urobiť, je,

898
01:09:28,080 --> 01:09:34,910
rokov 's - spolu, myslím, vyskúšať a napísať obsahuje funkcie

899
01:09:34,910 --> 01:09:38,899
ktoré nie je jedno, či je to binárny vyhľadávací strom.

900
01:09:38,899 --> 01:09:43,770
Táto obsahuje funkcie by mala vrátiť hodnotu true

901
01:09:43,770 --> 01:09:58,330
ak kdekoľvek v tomto všeobecnom binárnom stromu je hodnota, ktorú hľadáte.

902
01:09:58,330 --> 01:10:02,520
Takže poďme sa najprv to rekurzívne a potom to urobíme iteratívne.

903
01:10:02,520 --> 01:10:07,300
Môžeme vlastne len to dohromady, pretože to bude naozaj málo.

904
01:10:07,300 --> 01:10:11,510
>> Čo je môj základný scenár bude?

905
01:10:11,510 --> 01:10:13,890
[Študent, nezrozumiteľným]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Takže ak (strom == NULL), potom čo?

907
01:10:18,230 --> 01:10:22,740
[Študent] Návrat false.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, dobre, ja nepotrebujem else.

909
01:10:26,160 --> 01:10:30,250
Ak bol môj druhý base-case.

910
01:10:30,250 --> 01:10:32,450
[Študent] Tree hodnota? Jo >>.

911
01:10:32,450 --> 01:10:36,430
Takže ak (tree-> value == hodnota.

912
01:10:36,430 --> 01:10:39,920
Všimnite si, že sme späť do uzla *, nie je uzol ** s?

913
01:10:39,920 --> 01:10:42,990
Obsahuje nikdy sa nebudete musieť používať uzla **,

914
01:10:42,990 --> 01:10:45,480
pretože sme sa nemení ukazovatele.

915
01:10:45,480 --> 01:10:50,540
Sme jednoducho nabehnúť je.

916
01:10:50,540 --> 01:10:53,830
Ak sa tak stane, potom chceme vrátiť true.

917
01:10:53,830 --> 01:10:58,270
Else chceme prejsť deti.

918
01:10:58,270 --> 01:11:02,620
Takže nemôžeme uvažovať o tom, či všetko vľavo je menej

919
01:11:02,620 --> 01:11:05,390
a všetko vpravo je väčšia.

920
01:11:05,390 --> 01:11:09,590
Takže to, čo je naša podmienka bude tu - alebo, čo budeme robiť?

921
01:11:09,590 --> 01:11:11,840
[Študent, nezrozumiteľné] >> Jo.

922
01:11:11,840 --> 01:11:17,400
Return obsahuje (hodnota, strom-> vľavo)

923
01:11:17,400 --> 01:11:26,860
alebo obsahuje (hodnota, strom-> vpravo). A to je všetko.

924
01:11:26,860 --> 01:11:29,080
A všimnite si, že je nejaký skrat hodnotenie,

925
01:11:29,080 --> 01:11:32,520
kde, ak sa stane, že nájdete hodnotu v ľavom stromu,

926
01:11:32,520 --> 01:11:36,820
sme nikdy nebudete musieť pozerať na pravom stromu.

927
01:11:36,820 --> 01:11:40,430
To je celá funkcie.

928
01:11:40,430 --> 01:11:43,690
Teraz sa poďme to iteratívne,

929
01:11:43,690 --> 01:11:48,060
ktorý bude menej pekné.

930
01:11:48,060 --> 01:11:54,750
Vezmeme obvyklé štart uzla * cur = Strom.

931
01:11:54,750 --> 01:12:03,250
Kým (teď! = NULL).

932
01:12:03,250 --> 01:12:08,600
Rýchlo bude vidieť problém.

933
01:12:08,600 --> 01:12:12,250
Pokiaľ teraz - tu, či sa niekedy uniknúť z tohto,

934
01:12:12,250 --> 01:12:16,020
potom sme došli veci pozrieť sa na, tak vráti false.

935
01:12:16,020 --> 01:12:24,810
Ak (teraz-> value == hodnota), vráti true.

936
01:12:24,810 --> 01:12:32,910
Takže teraz sme na mieste -

937
01:12:32,910 --> 01:12:36,250
nevieme, či chceme ísť doľava alebo doprava.

938
01:12:36,250 --> 01:12:44,590
So ľubovoľne, poďme odišiel.

939
01:12:44,590 --> 01:12:47,910
Ja som samozrejme bežať do problému, kedy som úplne opustené všetko -

940
01:12:47,910 --> 01:12:50,760
Budem vždy len kontrolovať ľavú stranu stromu.

941
01:12:50,760 --> 01:12:56,050
Nikdy kontrolovať všetko, čo je právo dieťaťa na čokoľvek.

942
01:12:56,050 --> 01:13:00,910
Ako môžem tento problém vyriešiť?

943
01:13:00,910 --> 01:13:05,260
[Študent] Musíte sledovať vľavo a vpravo v zásobníku.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Jo. Takže poďme robiť to

945
01:13:13,710 --> 01:13:32,360
struct list, uzol * n, a potom uzol ** ďalej?

946
01:13:32,360 --> 01:13:40,240
Myslím si, že funguje dobre.

947
01:13:40,240 --> 01:13:45,940
Chceme ísť cez ľavé, alebo rokov 's - tu.

948
01:13:45,940 --> 01:13:54,350
Struct = zoznam zoznam, bude to začne

949
01:13:54,350 --> 01:13:58,170
pretože na tomto struct zozname.

950
01:13:58,170 --> 01:14:04,040
* Listy = NULL. Takže to bude náš prepojený zoznam

951
01:14:04,040 --> 01:14:08,430
z podstromu, ktoré sme preskočil.

952
01:14:08,430 --> 01:14:13,800
Budeme prechádzať zostalo,

953
01:14:13,800 --> 01:14:17,870
ale pretože sme nutne potrebovať vrátiť doprava,

954
01:14:17,870 --> 01:14:26,140
Budeme držať pravú stranu vo vnútri nášho struct zoznamu.

955
01:14:26,140 --> 01:14:32,620
Potom budeme mať new_list alebo struct,

956
01:14:32,620 --> 01:14:41,080
struct list *, new_list = malloc (sizeof (zoznam)).

957
01:14:41,080 --> 01:14:44,920
Budem ignorovať chyba-kontrolovať, ale mali by ste skontrolovať, či je to null.

958
01:14:44,920 --> 01:14:50,540
New_list uzol, že to bude ukazovať na -

959
01:14:50,540 --> 01:14:56,890
oh, to je dôvod, prečo som chcel to tu. Bude to poukázať na druhej struct zozname.

960
01:14:56,890 --> 01:15:02,380
To je len, ako lineárnymi zoznamy prácu.

961
01:15:02,380 --> 01:15:04,810
To je rovnaké ako int prepojenom zoznamu

962
01:15:04,810 --> 01:15:06,960
okrem sme len nahradiť int s uzlom *.

963
01:15:06,960 --> 01:15:11,040
Je to úplne rovnaké.

964
01:15:11,040 --> 01:15:15,100
So new_list, hodnota našej new_list uzla,

965
01:15:15,100 --> 01:15:19,120
bude teraz-> kliknite pravým.

966
01:15:19,120 --> 01:15:24,280
Hodnota nášho new_list-> next bude náš pôvodný zoznam,

967
01:15:24,280 --> 01:15:30,760
a potom budeme aktualizovať náš zoznam, aby ukazoval na new_list.

968
01:15:30,760 --> 01:15:33,650
>> Teraz potrebujeme nejaký spôsob ťahanie vecí,

969
01:15:33,650 --> 01:15:37,020
ako sme prejsť celý ľavého podstrome.

970
01:15:37,020 --> 01:15:40,480
Teraz musíme vytiahnuť veci z toho,

971
01:15:40,480 --> 01:15:43,850
ako teraz je null, nechceme len vrátiť false.

972
01:15:43,850 --> 01:15:50,370
Chceme teraz vytiahnuť von na našom novom zozname.

973
01:15:50,370 --> 01:15:53,690
Najvýhodnejším spôsobom, ako to urobiť - no, vlastne, je tu niekoľko spôsobov, ako to urobiť.

974
01:15:53,690 --> 01:15:56,680
Každý, kto má nejaký návrh?

975
01:15:56,680 --> 01:15:58,790
Kde by som mal urobiť, alebo ako by som mal urobiť?

976
01:15:58,790 --> 01:16:08,010
Máme len pár minút, ale nejaké návrhy?

977
01:16:08,010 --> 01:16:14,750
Namiesto toho, aby - jedným spôsobom, namiesto toho, aby náš stav je pri,

978
01:16:14,750 --> 01:16:17,090
to, čo sme v súčasnej dobe hľadá v nie je null,

979
01:16:17,090 --> 01:16:22,340
miesto budeme fungovať ďalej, kým náš zoznam sám o sebe je null.

980
01:16:22,340 --> 01:16:25,680
Takže ak náš zoznam skončí ako bytia null,

981
01:16:25,680 --> 01:16:30,680
potom sme došli veci hľadať, prehľadávať.

982
01:16:30,680 --> 01:16:39,860
To však znamená, že prvé, čo v našom zozname je len tak byť prvý uzol.

983
01:16:39,860 --> 01:16:49,730
Úplne prvá vec, ktorú bude - sme už treba vidieť, že.

984
01:16:49,730 --> 01:16:58,710
So 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 teraz, keď zoznam sa nerovná null.

987
01:17:07,580 --> 01:17:11,610
Cur sa chystá vytiahnuť niečo z nášho zoznamu.

988
01:17:11,610 --> 01:17:13,500
Takže teraz sa chystá na rovnej zoznam-> n

989
01:17:13,500 --> 01:17:20,850
A potom zoznam bude na rovné zoznam-> n, alebo list-> next.

990
01:17:20,850 --> 01:17:23,480
Takže ak teraz hodnota sa rovná hodnote.

991
01:17:23,480 --> 01:17:28,790
Teraz môžeme pridať aj našu pravú myši a naše ľavej ukazovateľ

992
01:17:28,790 --> 01:17:32,900
ako dlho ako oni to nie je null.

993
01:17:32,900 --> 01:17:36,390
Tu dole, myslím, že by sme mali urobiť, že v prvom rade.

994
01:17:36,390 --> 01:17:44,080
Ak (teraz-> P! = NULL)

995
01:17:44,080 --> 01:17:56,380
potom budeme vložiť tento uzol do nášho zoznamu.

996
01:17:56,380 --> 01:17:59,290
Ak (teraz-> vľavo), to je trochu práce navyše, ale je to v poriadku.

997
01:17:59,290 --> 01:18:02,690
Ak (teraz-> doľava! = NULL),

998
01:18:02,690 --> 01:18:14,310
a budeme vložiť ľavej do nášho prepojeného zoznamu,

999
01:18:14,310 --> 01:18:19,700
a že by mali byť, že.

1000
01:18:19,700 --> 01:18:22,670
My iteráciu - tak dlho, ako budeme mať niečo v našom zozname,

1001
01:18:22,670 --> 01:18:26,640
máme ďalší uzol na pohľad.

1002
01:18:26,640 --> 01:18:28,920
Takže sa pozrieme v tomto uzle,

1003
01:18:28,920 --> 01:18:31,390
sme vopred na náš zoznam k ďalšiemu.

1004
01:18:31,390 --> 01:18:34,060
Ak tento uzol je hodnota, ktorú hľadáte, môžeme sa vrátiť true.

1005
01:18:34,060 --> 01:18:37,640
Else vložte obe naše ľavej a pravej podstromu,

1006
01:18:37,640 --> 01:18:40,510
ako dlho ako oni to nie je null, do nášho zoznamu

1007
01:18:40,510 --> 01:18:43,120
takže sme nevyhnutne ísť cez ne.

1008
01:18:43,120 --> 01:18:45,160
Takže ak neboli null,

1009
01:18:45,160 --> 01:18:47,950
keď náš koreň ukazovateľ upozornil na dve veci,

1010
01:18:47,950 --> 01:18:51,670
potom najprv sme vytiahli niečo tak náš zoznam skončí ako bytia null.

1011
01:18:51,670 --> 01:18:56,890
A potom sme dali dve veci späť, takže teraz náš zoznam je veľkosť 2.

1012
01:18:56,890 --> 01:19:00,030
Potom budeme slučky späť a my len tak vytiahnuť,

1013
01:19:00,030 --> 01:19:04,250
povedzme, ľavá ukazovateľ nášho koreňového uzla.

1014
01:19:04,250 --> 01:19:07,730
A to si len dejú, skončíme slučky nad všetkým.

1015
01:19:07,730 --> 01:19:11,280
>> Všimnite si, že to bolo podstatne zložitejšie

1016
01:19:11,280 --> 01:19:14,160
v rekurzívne riešenie.

1017
01:19:14,160 --> 01:19:17,260
A ja som povedal: viackrát

1018
01:19:17,260 --> 01:19:25,120
že rekurzívne riešenie má zvyčajne veľa spoločného s iteratívny riešenie.

1019
01:19:25,120 --> 01:19:30,820
Tu je to presne to, čo rekurzívne riešenie robí.

1020
01:19:30,820 --> 01:19:36,740
Jedinou zmenou je, že namiesto toho, aby implicitne pomocou zásobníka, zásobník programu,

1021
01:19:36,740 --> 01:19:40,840
ako spôsob, ako udržať sledovať, čo uzly, stále potrebujete navštíviť,

1022
01:19:40,840 --> 01:19:45,430
Teraz budete musieť použiť prepojeného zoznamu.

1023
01:19:45,430 --> 01:19:49,070
V oboch prípadoch sa vedenie sledovať, čo uzla musí ešte byť navštívené.

1024
01:19:49,070 --> 01:19:51,790
V rekurzívne prípade, že je to proste jednoduchšie, pretože zásobník

1025
01:19:51,790 --> 01:19:57,100
je implementovaný pre vás ako programu zásobníka.

1026
01:19:57,100 --> 01:19:59,550
Všimnite si, že tento spájať zoznam, to je zásobník.

1027
01:19:59,550 --> 01:20:01,580
Či sme len dať na stack

1028
01:20:01,580 --> 01:20:09,960
je hneď to, čo budeme vytiahnite zásobník na návštevu ďalší.

1029
01:20:09,960 --> 01:20:14,380
Sme z času, ale nejaké otázky?

1030
01:20:14,380 --> 01:20:23,530
[Študent, nezrozumiteľným]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Jo. Takže ak máme prepojeného zoznamu,

1032
01:20:27,790 --> 01:20:30,150
prúd bude poukázať na toho chlapa,

1033
01:20:30,150 --> 01:20:34,690
a teraz sme len zlepšovaniu našich prepojeného zoznamu zamerať sa na toho chlapa.

1034
01:20:34,690 --> 01:20:44,200
Sme tu pojazdom nad prepojeného zoznamu v tomto riadku.

1035
01:20:44,200 --> 01:20:51,200
A potom myslím, že by sme mali oslobodiť naše prepojeného zoznamu a podobne

1036
01:20:51,200 --> 01:20:53,880
raz pred vracia hodnotu true alebo false, musíme

1037
01:20:53,880 --> 01:20:57,360
iterácii nášho prepojeného zoznamu a vždy sa sem, myslím,

1038
01:20:57,360 --> 01:21:03,900
ak by sme teraz právo nie je rovné, pridajte ho, takže teraz chceme oslobodiť

1039
01:21:03,900 --> 01:21:09,600
teraz, pretože, no, my sme úplne zabudnúť na zozname? Jo.

1040
01:21:09,600 --> 01:21:12,880
Takže to je to, čo chceme robiť.

1041
01:21:12,880 --> 01:21:16,730
Kde je ukazovateľ?

1042
01:21:16,730 --> 01:21:23,320
Cur bol potom - chceme do struct zoznam * 10 rovná zoznam vedľa.

1043
01:21:23,320 --> 01:21:29,240
Free listy, listy = temp.

1044
01:21:29,240 --> 01:21:32,820
A v prípade, kedy sa vráti true, je potrebné, aby sme iterácii

1045
01:21:32,820 --> 01:21:37,050
po zvyšok nášho prepojeného zoznamu uvoľňovať veci.

1046
01:21:37,050 --> 01:21:39,700
Pekná vec, o rekurzívne riešenie je uvoľnenie veci

1047
01:21:39,700 --> 01:21:44,930
jednoducho znamená objavovať factorings zo zásobníka, ktorý bude diať za vás.

1048
01:21:44,930 --> 01:21:50,720
Takže sme išli z niečoho, čo to ako 3 riadky ťažko think-o kód

1049
01:21:50,720 --> 01:21:57,520
k niečomu, čo je výrazne oveľa viac tvrdý-k-si-o riadkov kódu.

1050
01:21:57,520 --> 01:22:00,620
Nejaké ďalšie otázky?

1051
01:22:00,620 --> 01:22:08,760
Dobrá. Sme dobrí. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]