1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Oddelek 7: Več Udobna]

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
V redu. Torej, kot sem že povedal v e-pošti,

5
00:00:10,110 --> 00:00:14,060
to se dogaja, da je binarno drevo intenzivna oddelek.

6
00:00:14,060 --> 00:00:16,820
Vendar pa ni, da je veliko vprašanj.

7
00:00:16,820 --> 00:00:18,920
Torej bomo poskušali izvleči vsako vprašanje

8
00:00:18,920 --> 00:00:25,430
in šel v podrobnosti, boleče vseh najboljših načinov ravnanja.

9
00:00:25,430 --> 00:00:31,200
Torej takoj na začetku, ko gremo skozi vzorčnih risbe binarnih dreves in podobno.

10
00:00:31,200 --> 00:00:35,970
Torej, tukaj, "Ne pozabite, da je binarno drevo vozlišč, podobne tistim povezan seznam,

11
00:00:35,970 --> 00:00:38,150
razen namesto enega kazalca obstajata dve: ena za "otroka" v levo

12
00:00:38,150 --> 00:00:41,950
in ena za desno "otrok". "

13
00:00:41,950 --> 00:00:45,630
Torej, binarno drevo je tako kot povezanega seznama,

14
00:00:45,630 --> 00:00:47,910
razen struct bo dva kazalca.

15
00:00:47,910 --> 00:00:51,390
Tam je trinary drevesa, ki bosta imela tri kazalce,

16
00:00:51,390 --> 00:00:56,540
obstaja N-arja drevesa, ki imajo le generično kazalec

17
00:00:56,540 --> 00:01:00,320
da boste potem morali malloc biti dovolj velika, da imajo

18
00:01:00,320 --> 00:01:04,840
dovolj kazalci na vseh možnih otrok.

19
00:01:04,840 --> 00:01:08,200
Torej, binarno drevo le zgodi, da imajo stalno število 2.

20
00:01:08,200 --> 00:01:11,260
Če želite, lahko daš povezani seznam kot unarni drevesa,

21
00:01:11,260 --> 00:01:15,360
ampak jaz ne mislim, kdo kliče, da.

22
00:01:15,360 --> 00:01:18,060
"Risanje škatle-in puščice diagram binarnega vozlišča drevesa

23
00:01:18,060 --> 00:01:24,110
vsebuje priljubljeno številko Nate je, 7, kjer je vsak otrok kazalec NULL. "

24
00:01:24,110 --> 00:01:27,780
Torej iPad način.

25
00:01:27,780 --> 00:01:30,280
>> To se dogaja, da je precej enostavna.

26
00:01:30,280 --> 00:01:36,150
Mi smo le, da bo imel vozlišče, ga bom pripraviti kot kvadrat.

27
00:01:36,150 --> 00:01:38,730
In jaz bom sestaviti vrednosti tukaj.

28
00:01:38,730 --> 00:01:41,090
Tako bo vrednost iti tja,

29
00:01:41,090 --> 00:01:44,770
in potem tukaj bomo imeli levi kazalec na levi in ​​desni kazalec na desni.

30
00:01:44,770 --> 00:01:50,430
In to je zelo veliko, tako dogovor, da ga pokličete levo in desno, kazalec imena.

31
00:01:50,430 --> 00:01:52,460
Oboje bo nič.

32
00:01:52,460 --> 00:01:57,870
To bo zgolj še nič, in da bo le null.

33
00:01:57,870 --> 00:02:03,630
Ok. Torej, nazaj sem.

34
00:02:03,630 --> 00:02:05,700
"S povezan seznam, smo imeli samo za shranjevanje kazalec

35
00:02:05,700 --> 00:02:09,639
na prvi vozel v seznamu, da bi se spominjali celo povezani seznam, ali celoten seznam.

36
00:02:09,639 --> 00:02:11,650
Prav tako, z drevesi, imamo le za shranjevanje kazalec

37
00:02:11,650 --> 00:02:13,420
na eno samo vozlišče, da se spomnite celotno drevo.

38
00:02:13,420 --> 00:02:15,980
To vozlišče je calle je "root z drevesa.

39
00:02:15,980 --> 00:02:18,320
Nadgraditi svoj diagram pred letom ali pripravi novega

40
00:02:18,320 --> 00:02:21,690
tako da imate škatle-in puščice upodobitev binarno drevo

41
00:02:21,690 --> 00:02:25,730
s vrednost 7, potem 3 v levo,

42
00:02:25,730 --> 00:02:32,760
9 nato na desni strani, nato pa 6 na desni strani 3 ".

43
00:02:32,760 --> 00:02:34,810
Bomo videli, če se spomnim, da je vse v moji glavi.

44
00:02:34,810 --> 00:02:37,670
Torej, to se dogaja, da je naša root tukaj.

45
00:02:37,670 --> 00:02:41,600
Imeli bomo nekaj kazalec nekje nekaj, kar ti pravimo koren,

46
00:02:41,600 --> 00:02:45,140
in to kaže s tem tipom.

47
00:02:45,140 --> 00:02:48,490
Zdaj, da bi novo vozlišče,

48
00:02:48,490 --> 00:02:52,870
kaj imamo, 3 na levi?

49
00:02:52,870 --> 00:02:57,140
Torej, novo vozlišče s 3, in je sprva kaže nič.

50
00:02:57,140 --> 00:02:59,190
Jaz bom dal N.

51
00:02:59,190 --> 00:03:02,250
Zdaj želimo, da gredo na levi 7.

52
00:03:02,250 --> 00:03:06,840
Zato smo spremenili to kazalec, da se zdaj kažejo s tem tipom.

53
00:03:06,840 --> 00:03:12,420
In delamo isto. Želimo 9 Sprehodite se tukaj

54
00:03:12,420 --> 00:03:14,620
ki je na začetku samo pravi nič.

55
00:03:14,620 --> 00:03:19,600
Bomo spremenili to kazalec, pokažite na 9,

56
00:03:19,600 --> 00:03:23,310
in zdaj smo želeli dati 6 desno od 3.

57
00:03:23,310 --> 00:03:32,170
Torej, da se bo - narediti 6.

58
00:03:32,170 --> 00:03:34,310
In ta tip točko tam.

59
00:03:34,310 --> 00:03:38,320
Ok. Tako, da je vse, kar nam želi storiti.

60
00:03:38,320 --> 00:03:42,770
>> Zdaj pa gremo čez nekaj terminologije.

61
00:03:42,770 --> 00:03:46,690
Smo že govorili o tem, kako Koren drevesa je top-najbolj vozlišče v drevesu.

62
00:03:46,690 --> 00:03:54,720
Tisti, ki vsebuje 7. Vozlišča na dnu drevesa se imenujejo listi.

63
00:03:54,720 --> 00:04:01,240
Vsako vozlišče, ki le ima sedaj null, katerega otrok je list.

64
00:04:01,240 --> 00:04:03,680
Torej je mogoče, če je naš binarno drevo je samo ena vozlišče,

65
00:04:03,680 --> 00:04:10,130
da je drevo list, in to je to.

66
00:04:10,130 --> 00:04:12,060
"The" Višina "od drevesa je število hmelja moraš narediti

67
00:04:12,060 --> 00:04:16,620
da bi dobili od vrha do lista. "

68
00:04:16,620 --> 00:04:18,640
Bomo dobili v, v drugi razliko

69
00:04:18,640 --> 00:04:21,940
med uravnotežene in neuravnotežene dreves binarne,

70
00:04:21,940 --> 00:04:29,470
vendar za zdaj, je skupna višina tega drevesa

71
00:04:29,470 --> 00:04:34,520
Rekel bi, da je 3, čeprav, če ste štetje števila hmelja

72
00:04:34,520 --> 00:04:39,710
moraš narediti, da bi prišli do 9, potem je res samo višina 2.

73
00:04:39,710 --> 00:04:43,340
Zdaj je to neuravnoteženo binarno drevo,

74
00:04:43,340 --> 00:04:49,840
vendar bomo govorili o uravnoteženi, ko pride v poštev.

75
00:04:49,840 --> 00:04:52,040
Sedaj lahko govorimo o vozlišč v drevesu v smislu

76
00:04:52,040 --> 00:04:54,700
glede na druge vozlišč v drevesu.

77
00:04:54,700 --> 00:04:59,730
Torej, zdaj imamo starši, otroci, bratje in sestre, prednikov in potomcev.

78
00:04:59,730 --> 00:05:05,650
So zelo zdrava pamet, kaj pomenijo.

79
00:05:05,650 --> 00:05:09,610
Če se vprašamo - to je starše.

80
00:05:09,610 --> 00:05:12,830
Torej, kaj je matično 3?

81
00:05:12,830 --> 00:05:16,090
[Dijaki] 7. >> Ja. Matično se le, da bo to, kar kaže na vas.

82
00:05:16,090 --> 00:05:20,510
Torej, kaj so otroci 7?

83
00:05:20,510 --> 00:05:23,860
[Dijaki] 3 in 9. >> Ja.

84
00:05:23,860 --> 00:05:26,460
Obvestilo, da je "otrok" dobesedno pomeni za otroke,

85
00:05:26,460 --> 00:05:31,010
Tako 6 ne bi uporabljal, ker je kot vnuka.

86
00:05:31,010 --> 00:05:35,540
Potem pa če gremo potomce, kaj so potomci 7?

87
00:05:35,540 --> 00:05:37,500
[Dijaki] 3, 6 in 9. >> Ja.

88
00:05:37,500 --> 00:05:42,330
Potomci korenskega vozlišča se bo vse, kar je v drevesu,

89
00:05:42,330 --> 00:05:47,950
razen morda root vozlišča sama, če ne želite, da menijo, da je potomec.

90
00:05:47,950 --> 00:05:50,750
In končno, predniki, tako da je v nasprotni smeri.

91
00:05:50,750 --> 00:05:55,740
Torej, kaj so predniki 6?

92
00:05:55,740 --> 00:05:58,920
[Dijaki] 3 in 7. >> Ja. 9 ni vključena.

93
00:05:58,920 --> 00:06:02,520
To je samo neposredni rodu nazaj do korena

94
00:06:02,520 --> 00:06:13,230
se bo vaši predniki.

95
00:06:13,230 --> 00:06:16,300
>> "Pravimo, da je binarno drevo" naloži ", če za vsako vozlišče v drevesu,

96
00:06:16,300 --> 00:06:19,530
vseh njegovih potomcev na levi imajo manj vrednosti

97
00:06:19,530 --> 00:06:22,890
in vsi tisti na desni imajo večje vrednosti.

98
00:06:22,890 --> 00:06:27,060
Na primer, je drevo nad naloži, vendar to ni edina možna urejene. "

99
00:06:27,060 --> 00:06:30,180
Preden smo prišli do tega,

100
00:06:30,180 --> 00:06:36,420
naloži binarno drevo je znana tudi kot dvojiškega drevesa.

101
00:06:36,420 --> 00:06:38,660
Tu se zgodi, da se ga kliče urejene binarno drevo,

102
00:06:38,660 --> 00:06:41,850
vendar še nikoli nisem slišal, da imenuje naročiti binarno drevo pred

103
00:06:41,850 --> 00:06:46,650
in na kvizu smo veliko bolj verjetno, da dajo binarno iskalno drevo.

104
00:06:46,650 --> 00:06:49,250
Oni so eno in isto,

105
00:06:49,250 --> 00:06:54,580
in to je pomembno, da prepozna razliko med drevesa binarno drevo in binarno iskanje.

106
00:06:54,580 --> 00:06:58,830
Binarno drevo je samo drevo, ki opozarja na dve stvari.

107
00:06:58,830 --> 00:07:02,120
Vsako vozlišče opozarja na dve stvari.

108
00:07:02,120 --> 00:07:06,310
Ni razmišljanje o vrednotah, ki jih je usmerjeno k.

109
00:07:06,310 --> 00:07:11,370
Torej, kot sem, saj je to binarno iskalno drevo,

110
00:07:11,370 --> 00:07:14,030
vemo, da če bomo šli levo od 7,

111
00:07:14,030 --> 00:07:16,670
potem pa vse vrednosti, ki jih lahko morebiti doseže

112
00:07:16,670 --> 00:07:19,310
jih bo ostalo od 7 morajo biti manj kot 7.

113
00:07:19,310 --> 00:07:24,070
Opazili boste, da so vse vrednosti manj kot 7 so 3 in 6.

114
00:07:24,070 --> 00:07:26,040
Tisti, ki so vse na levi 7.

115
00:07:26,040 --> 00:07:29,020
Če gremo od pravice do 7, vse mora biti večja od 7,

116
00:07:29,020 --> 00:07:33,220
Tako 9 je na desni strani 7, tako da smo dobri.

117
00:07:33,220 --> 00:07:36,150
To pa ne velja za binarno drevo,

118
00:07:36,150 --> 00:07:40,020
za redno binarnega drevesa imamo samo 3 na vrhu, 7 na levi strani,

119
00:07:40,020 --> 00:07:47,630
9 levo od 7, ni vrstni red vrednosti whatsoever.

120
00:07:47,630 --> 00:07:56,140
Zdaj, ne bomo dejansko to, ker je dolgočasno in nepotrebno,

121
00:07:56,140 --> 00:07:59,400
ampak "poskušali pripraviti čim več naročene dreves, kot si lahko misliš

122
00:07:59,400 --> 00:08:01,900
s številkami 7, 3, 9, 6.

123
00:08:01,900 --> 00:08:06,800
Koliko različni dogovori obstajajo? Kakšna je višina vsakega? "

124
00:08:06,800 --> 00:08:10,480
>> Naredili bomo nekaj, vendar je glavna ideja je,

125
00:08:10,480 --> 00:08:16,530
To nikakor ni enotna zastopanost binarno drevo, ki vsebuje te vrednosti.

126
00:08:16,530 --> 00:08:22,760
Vse kar potrebujete je nekaj binarno drevo, ki vsebuje 7, 3, 6 in 9.

127
00:08:22,760 --> 00:08:25,960
Druga možnost bi bila veljavna korenina je 3,

128
00:08:25,960 --> 00:08:30,260
pojdi na levo in to je 6, pojdite na levo in to je 7,

129
00:08:30,260 --> 00:08:32,730
pojdi na levo in je 9.

130
00:08:32,730 --> 00:08:36,169
To je popolnoma veljavno binarno iskalno drevo.

131
00:08:36,169 --> 00:08:39,570
To ni zelo koristna, saj je tako kot povezani seznam

132
00:08:39,570 --> 00:08:43,750
in vseh teh kazalcev so le null.

133
00:08:43,750 --> 00:08:48,900
Vendar je veljavna drevo. Ja?

134
00:08:48,900 --> 00:08:51,310
[Študent] Ali ni vrednosti, morajo biti večja na desni?

135
00:08:51,310 --> 00:08:56,700
Ali pa je to? - >> To sem mislil, da gredo v drugo smer.

136
00:08:56,700 --> 00:09:00,960
Tam je tudi - ja, dajmo izbrati to.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Dober ulov.

138
00:09:07,770 --> 00:09:11,730
Še vedno ima ubogati, kar je binarno drevo iskanje naj storim.

139
00:09:11,730 --> 00:09:15,650
Torej je vse na levi strani mora biti manjši od danega vozlišča.

140
00:09:15,650 --> 00:09:23,180
Mi lahko samo premaknete, recimo, to 6 in ga tukaj.

141
00:09:23,180 --> 00:09:26,880
Ne, ne moremo. Zakaj vztrajati početje to?

142
00:09:26,880 --> 00:09:35,350
Naredimo - tukaj je 6, tukaj je 7, 6 točk za 3.

143
00:09:35,350 --> 00:09:39,290
To je še vedno veljaven dvojiško iskalno drevo.

144
00:09:39,290 --> 00:09:49,260
Kaj je narobe, če sem - da vidimo, če bom lahko prišel do dogovora.

145
00:09:49,260 --> 00:09:52,280
Ja, v redu. Torej, kaj je narobe s to drevo?

146
00:09:52,280 --> 00:10:08,920
Mislim, da sem že dal namig, da je nekaj narobe z njim.

147
00:10:08,920 --> 00:10:14,430
Zakaj vztrajati početje to?

148
00:10:14,430 --> 00:10:18,510
Ok. To izgleda primerna.

149
00:10:18,510 --> 00:10:22,590
Če pogledamo vsakega vozlišča, kot so 7, nato pa na levi strani 7 je 3.

150
00:10:22,590 --> 00:10:24,960
Torej imamo 3, stvar na desni strani 3 je 6.

151
00:10:24,960 --> 00:10:27,750
In če pogledaš na 6, stvar na desni strani 6 je 9.

152
00:10:27,750 --> 00:10:30,910
Torej, zakaj to ni veljavno binarno iskalno drevo?

153
00:10:30,910 --> 00:10:36,330
[Dijaki] 9 je še vedno na levi strani 7. >> Ja.

154
00:10:36,330 --> 00:10:43,710
To mora biti res, da so vse vrednosti, ki jih lahko dosežejo morda jih bo na levi strani 7 manj kot 7.

155
00:10:43,710 --> 00:10:49,120
Če gremo levo 7, pridemo do 3 in smo še vedno lahko prišli do 6,

156
00:10:49,120 --> 00:10:52,520
lahko še vedno pridete do 9, ampak s tem, ko ni več manj kot 7,

157
00:10:52,520 --> 00:10:55,070
da ne bi mogli priti do številke, ki je večja od 7.

158
00:10:55,070 --> 00:10:59,830
Torej, to ni veljavno binarno iskalno drevo.

159
00:10:59,830 --> 00:11:02,330
>> Moj brat je dejansko imela intervju vprašanje

160
00:11:02,330 --> 00:11:07,760
da je v bistvu to, samo oznaka do nečesa, da bi preverili

161
00:11:07,760 --> 00:11:10,500
ali drevo je dvojiško iskalno drevo

162
00:11:10,500 --> 00:11:13,580
zato je prva stvar, ki je storil, je le preverite,

163
00:11:13,580 --> 00:11:17,020
Če levo in desno so pravilne, in nato izbirajte tam.

164
00:11:17,020 --> 00:11:19,700
Ampak ne moreš narediti, moraš slediti

165
00:11:19,700 --> 00:11:22,550
dejstvo, da zdaj, ko sem šla levo od 7,

166
00:11:22,550 --> 00:11:26,340
vse v to drevo mora biti manjša od 7.

167
00:11:26,340 --> 00:11:28,430
Pravilna algoritem mora slediti

168
00:11:28,430 --> 00:11:35,970
V mejah, da se vrednosti lahko sodijo noter

169
00:11:35,970 --> 00:11:38,360
Ne bomo šli skozi vse od njih.

170
00:11:38,360 --> 00:11:41,630
Tam je lepo enačbe,

171
00:11:41,630 --> 00:11:44,810
Čeprav nismo prišel do tistih, ne bomo prišli do tistih,

172
00:11:44,810 --> 00:11:47,030
opredeljevanju, koliko jih je dejansko so.

173
00:11:47,030 --> 00:11:53,180
Tako je 14 izmed njih.

174
00:11:53,180 --> 00:11:56,020
Ideja o tem, kako bi to naredil matematično je všeč,

175
00:11:56,020 --> 00:11:59,770
lahko izberete kateri koli niti enega, da bi bil izvor vozlišče,

176
00:11:59,770 --> 00:12:03,160
in potem, če sem izbral 7, da je korenina vozlišče,

177
00:12:03,160 --> 00:12:08,150
potem so, recimo, nekaj številk, ki lahko gredo moja leva vozlišče,

178
00:12:08,150 --> 00:12:10,440
in da so nekatere številke, ki jih je mogoče moja pravica vozlišče,

179
00:12:10,440 --> 00:12:15,090
ampak če sem n skupno število, se znesek, ki se lahko obrnejo na levo

180
00:12:15,090 --> 00:12:18,820
plus znesek, ki se lahko obrnejo na desni je n - 1.

181
00:12:18,820 --> 00:12:26,130
Torej, preostalih številk, morajo imeti možnost, da bodisi iti v levo ali desno.

182
00:12:26,130 --> 00:12:31,580
Zdi se, da je težko, da če sem dal 3, potem pa vse, kar mora iti v levo,

183
00:12:31,580 --> 00:12:35,080
ampak če sem dal 7, nato pa lahko nekatere stvari gredo v levo in nekatere stvari lahko obrnejo na desni strani.

184
00:12:35,080 --> 00:12:39,570
In 3. 1. "Mislil sem vse, kar lahko gre v desno.

185
00:12:39,570 --> 00:12:42,350
To je res, boste morali razmišljati o tem, kot,

186
00:12:42,350 --> 00:12:47,980
koliko stvari lahko gredo na naslednjo stopnjo drevesa.

187
00:12:47,980 --> 00:12:50,420
In pride ven, da bo 14, ali lahko pripravi vse od njih,

188
00:12:50,420 --> 00:12:54,650
in potem boš dobil 14.

189
00:12:54,650 --> 00:13:01,120
>> Gremo nazaj,

190
00:13:01,120 --> 00:13:03,510
"Ž dvojiška drevesa so kul, ker lahko iščemo po njih

191
00:13:03,510 --> 00:13:06,910
na zelo podoben način iskanja preko razvrščenih matrike.

192
00:13:06,910 --> 00:13:10,120
To storite tako, začnemo pri korenu in naš način dela, navzdol po drevesu

193
00:13:10,120 --> 00:13:13,440
do listov, preverjanje vsako vozlišče v vrednosti nad vrednotami, ki jih iščete.

194
00:13:13,440 --> 00:13:15,810
Če je trenutno vozlišče je vrednost nižja od vrednosti, ki ga iščemo,

195
00:13:15,810 --> 00:13:18,050
greš zraven desnem vozlišča otroka.

196
00:13:18,050 --> 00:13:20,030
Sicer pa greš na levi vozlišča svojega otroka.

197
00:13:20,030 --> 00:13:22,800
Na neki točki, boste našli bodisi vrednost, ki jo iščete, ali pa boš naletel na null,

198
00:13:22,800 --> 00:13:28,520
označuje vrednost ni v drevesu. "

199
00:13:28,520 --> 00:13:32,450
Imam, da izvlečete drevo smo imeli prej, da bo trajalo.

200
00:13:32,450 --> 00:13:38,280
Ampak želimo pogledati, ali 6, 10 in 1 v drevo.

201
00:13:38,280 --> 00:13:49,180
Torej, kaj je to, 7, 9, 3, 6. Ok.

202
00:13:49,180 --> 00:13:52,730
Številke, ki jih želite poiskati, smo želeli poiskati 6.

203
00:13:52,730 --> 00:13:55,440
Kako to algoritem deluje?

204
00:13:55,440 --> 00:14:03,040
No, imamo tudi nekaj korenin kazalec na našem drevesu.

205
00:14:03,040 --> 00:14:12,460
In gremo na korenu in rekli, da je ta vrednost enaka vrednosti smo iščejo?

206
00:14:12,460 --> 00:14:15,000
Torej iščemo 6, tako da to ni enako.

207
00:14:15,000 --> 00:14:20,140
Tako smo naprej, in zdaj smo rekli, v redu, tako da je 6 manj kot 7.

208
00:14:20,140 --> 00:14:23,940
Ali to pomeni, da želimo iti v levo, ali pa želimo iti na desno?

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

210
00:14:27,340 --> 00:14:33,340
To je bistveno lažja, vse, kar morate storiti je, da pripravi eno možno vozlišče drevesa

211
00:14:33,340 --> 00:14:37,760
in potem Ne - namesto da mislijo v glavi,

212
00:14:37,760 --> 00:14:40,020
ok, če je to manj, naj grem na levi ali pa na pravico,

213
00:14:40,020 --> 00:14:43,030
samo gledaš te slike, to je zelo jasno, da moram iti v levo

214
00:14:43,030 --> 00:14:47,700
če je to vozlišče je večja od vrednosti, ki jo iščem.

215
00:14:47,700 --> 00:14:52,600
Torej greš na levo, zdaj sem na 3.

216
00:14:52,600 --> 00:14:57,770
Želim - 3 je nižja od vrednosti, ki jih iščem, kar je 6.

217
00:14:57,770 --> 00:15:03,420
Torej gremo na desno, zdaj pa sem na koncu na 6,

218
00:15:03,420 --> 00:15:07,380
ki je vrednost iščem, zato sem se vrnil res.

219
00:15:07,380 --> 00:15:15,760
Naslednji vrednost grem iskati je 10.

220
00:15:15,760 --> 00:15:23,230
Ok. Torej, 10, zdaj pa se bo - odreže, da - bodo sledili korenine.

221
00:15:23,230 --> 00:15:27,670
Sedaj, 10 se bo več kot 7, zato želim videti na desni.

222
00:15:27,670 --> 00:15:31,660
Jaz bom prišel tja, 10 se bo večja od 9,

223
00:15:31,660 --> 00:15:34,520
Tako bom želijo videti na desni.

224
00:15:34,520 --> 00:15:42,100
Prišel sem sem, vendar sem zdaj sem na null.

225
00:15:42,100 --> 00:15:44,170
Kaj naj storim, če sem udaril nično?

226
00:15:44,170 --> 00:15:47,440
[Študent] Nazaj ne drži? >> Ja. Nisem našel 10.

227
00:15:47,440 --> 00:15:49,800
1 se bo skoraj identičen primer,

228
00:15:49,800 --> 00:15:51,950
razen tega, da se je le, da bo obrnila, namesto da bi iskali

229
00:15:51,950 --> 00:15:56,540
navzdol na desni strani, bom pogledal dol na levi strani.

230
00:15:56,540 --> 00:16:00,430
>> Zdaj mislim, da smo dejansko prišli do kode.

231
00:16:00,430 --> 00:16:04,070
Tukaj pa - Odprtje CS50 napravo in krmariti svojo pot tam,

232
00:16:04,070 --> 00:16:07,010
ampak tudi preprosto lahko to storite v prostoru.

233
00:16:07,010 --> 00:16:09,170
Verjetno je idealen, da to storite v prostor,

234
00:16:09,170 --> 00:16:13,760
ker lahko delamo v prostoru.

235
00:16:13,760 --> 00:16:19,170
"Najprej bomo morali z novo definicijo tipa za binarno drevo vozlišče, ki vsebuje int vrednosti.

236
00:16:19,170 --> 00:16:21,400
Uporaba boiler typedef spodaj

237
00:16:21,400 --> 00:16:24,510
ustvarite novo definicijo za tip vozlišča v binarno drevo.

238
00:16:24,510 --> 00:16:27,930
Če se vam zatakne. . . "Bla, bla, bla. Redu.

239
00:16:27,930 --> 00:16:30,380
Torej, kaj je dal boiler tukaj,

240
00:16:30,380 --> 00:16:41,630
typedef struct vozlišče in vozlišče. Ja, v redu.

241
00:16:41,630 --> 00:16:44,270
Torej, kaj so polja bomo želeli v naši vozel?

242
00:16:44,270 --> 00:16:46,520
[Študent] Int in nato 2 kazalci?

243
00:16:46,520 --> 00:16:49,700
>> Int vrednost, 2 kazalci? Kako napisati napotke?

244
00:16:49,700 --> 00:16:58,440
[Študent] struct. >> Moram povečati noter Ja, struct vozlišče * v levo,

245
00:16:58,440 --> 00:17:01,320
in struct vozlišče * desno.

246
00:17:01,320 --> 00:17:03,460
In ne pozabite razpravo od zadnjega obiska,

247
00:17:03,460 --> 00:17:15,290
da to nima smisla, to nima nobenega smisla,

248
00:17:15,290 --> 00:17:18,270
To nima nobenega smisla.

249
00:17:18,270 --> 00:17:25,000
Moraš vse tja, da bi opredelili ta rekurzivni struct.

250
00:17:25,000 --> 00:17:27,970
Dobro, to je tisto, kar naša drevo se bo izgledal.

251
00:17:27,970 --> 00:17:37,670
Če bomo naredili trinary drevo, potem bi vozlišče videti B1, B2, struct vozlišče * B3,

252
00:17:37,670 --> 00:17:43,470
b, kjer je podružnica - pravzaprav, sem še slišal, da levo, sredina, desno, ampak karkoli.

253
00:17:43,470 --> 00:17:55,610
Mi samo skrbi binarno, tako da desno, levo.

254
00:17:55,610 --> 00:17:59,110
"Zdaj razglaša za globalno spremenljivko * vozlišče za koren drevesa."

255
00:17:59,110 --> 00:18:01,510
Torej ne bova za to.

256
00:18:01,510 --> 00:18:08,950
Da bi se stvari nekoliko težje in bolj splošen,

257
00:18:08,950 --> 00:18:11,570
ne bomo imeli globalno spremenljivko vozlišča.

258
00:18:11,570 --> 00:18:16,710
Namesto tega v glavnem bomo prijavijo vse svoje vozlišče stvari,

259
00:18:16,710 --> 00:18:20,500
in to pomeni, da je spodaj, ko smo začeli izvajati

260
00:18:20,500 --> 00:18:23,130
Vsebuje naša naloga in naš vložek funkcija,

261
00:18:23,130 --> 00:18:27,410
namesto naših vsebuje delujejo samo z uporabo te svetovne vozlišča spremenljivko,

262
00:18:27,410 --> 00:18:34,280
bomo morali to sprejeti kot argument drevo, da želimo, da obdelati.

263
00:18:34,280 --> 00:18:36,650
Ob globalno spremenljivko naj bi stvari lažje.

264
00:18:36,650 --> 00:18:42,310
Gremo, da bi stvari težje.

265
00:18:42,310 --> 00:18:51,210
Sedaj vzemite minuto ali tako, da pač te stvari,

266
00:18:51,210 --> 00:18:57,690
, kjer v notranjosti od glavnih želite ustvariti to drevo, in to je vse, kar želite storiti.

267
00:18:57,690 --> 00:19:04,530
Poskusite in zgraditi to drevo v vašem glavne funkcije.

268
00:19:42,760 --> 00:19:47,610
>> Ok. Torej ti sploh ni treba, da so izdelani na drevesu celotno pot še ni.

269
00:19:47,610 --> 00:19:49,840
Toda kdo ima nekaj kar bi lahko potegnili gor

270
00:19:49,840 --> 00:20:03,130
pokazati, kako se bodo začeli gradnjo takšno drevo?

271
00:20:03,130 --> 00:20:08,080
[Študent] Nekdo razbija, poskuša priti ven.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Kdor zadovoljni z njihovo gradnjo drevesa?

273
00:20:13,100 --> 00:20:15,520
[Študent] Seveda. To ni bilo storjeno. >> Je že v redu. Lahko je pravkar končal -

274
00:20:15,520 --> 00:20:26,860
oh, ga lahko reši? Hura.

275
00:20:26,860 --> 00:20:32,020
Torej, tukaj imamo - oh, sem rahlo odrezana.

276
00:20:32,020 --> 00:20:34,770
Sem Povečano?

277
00:20:34,770 --> 00:20:37,730
Povečajte, da se pomaknete ven. >> Imam vprašanje. >> Ja?

278
00:20:37,730 --> 00:20:44,410
[Študent] Ko določite struct, so stvari, kot initialized na kaj?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> redu. Torej bi morali inicializirati -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Ko določite, ali ko razglasi struct,

281
00:20:50,450 --> 00:20:55,600
ni inicializiran privzeto, to je tako kot, če ugotovi, int.

282
00:20:55,600 --> 00:20:59,020
To je popolnoma ista stvar. To je tako kot vsak izmed njenih posameznih področjih

283
00:20:59,020 --> 00:21:04,460
lahko za smeti vrednosti v tem. >> In ali je mogoče opredeliti - ali razglasi struct

284
00:21:04,460 --> 00:21:07,740
na način, ki ga opravlja jim inicializirati?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Da. Torej, tipka za inicializacijo skladnja

286
00:21:13,200 --> 00:21:18,660
bo izgledal -

287
00:21:18,660 --> 00:21:22,200
Obstaja dva načina, lahko to storijo. Mislim, da bi ga morali pripraviti

288
00:21:22,200 --> 00:21:25,840
in se prepričajte Jek tudi počne.

289
00:21:25,840 --> 00:21:28,510
Vrstni red argumentov, ki prihaja v struct,

290
00:21:28,510 --> 00:21:32,170
daš kot da trditev znotraj te zavite oklepaje.

291
00:21:32,170 --> 00:21:35,690
Torej, če želite, da se zažene do 9, levo je nična, nato pa prav nič,

292
00:21:35,690 --> 00:21:41,570
da bi bilo 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Druga možnost je, in urednik ni všeč to sintakso,

294
00:21:47,890 --> 00:21:50,300
in misli, da želim nov blok,

295
00:21:50,300 --> 00:22:01,800
druga možnost pa je nekaj podobnega -

296
00:22:01,800 --> 00:22:04,190
Tukaj bom dal v novo vrstico.

297
00:22:04,190 --> 00:22:09,140
Lahko posebej poudarjati, da sem pozabila točno sintakso.

298
00:22:09,140 --> 00:22:13,110
Torej, lahko jih izrecno obravnavajo po imenu in rekel,

299
00:22:13,110 --> 00:22:21,570
. C ali. Vrednost = 9,. Levo = NULL.

300
00:22:21,570 --> 00:22:24,540
Ugibam, da ti morajo biti vejice.

301
00:22:24,540 --> 00:22:29,110
. Desno = NULL, tako da na ta način ne boste

302
00:22:29,110 --> 00:22:33,780
dejansko vedeti vrstni red struct,

303
00:22:33,780 --> 00:22:36,650
in ko berete to, je veliko bolj jasno

304
00:22:36,650 --> 00:22:41,920
o tem, kaj je vrednost, ki se inicializira k.

305
00:22:41,920 --> 00:22:44,080
>> To se zgodi, da je ena od stvari, ki -

306
00:22:44,080 --> 00:22:49,100
Tako, za večino del, C + + je nadgradnja C.

307
00:22:49,100 --> 00:22:54,160
Lahko vzamete C kodo, da se usmerijo v C + +, in bi moral prevesti.

308
00:22:54,160 --> 00:22:59,570
To je ena izmed stvari, da je C + + ne podpira, tako da ljudje ne bi naredil.

309
00:22:59,570 --> 00:23:01,850
Ne vem, če je to edini razlog, da ljudje niso za to,

310
00:23:01,850 --> 00:23:10,540
vendar v primeru, ko sem potreboval, da jo uporabljajo, potrebne za delo s C + + in tako nisem mogel uporabljati.

311
00:23:10,540 --> 00:23:14,000
Še en primer nečesa, kar ne deluje s C + +, je

312
00:23:14,000 --> 00:23:16,940
kako malloc vrne "void *," tehnično,

313
00:23:16,940 --> 00:23:20,200
vendar lahko samo rečem char * x = malloc karkoli,

314
00:23:20,200 --> 00:23:22,840
in bo samodejno odda v char *.

315
00:23:22,840 --> 00:23:25,450
To samodejno litega ne zgodi v C + +.

316
00:23:25,450 --> 00:23:28,150
To ne bi bilo zbrati, in vi bi morali izrecno povedati

317
00:23:28,150 --> 00:23:34,510
char * malloc, karkoli, da ga odda v char *.

318
00:23:34,510 --> 00:23:37,270
Ni veliko stvari, C in C + + se ne strinjajo o,

319
00:23:37,270 --> 00:23:40,620
ampak tisti dve.

320
00:23:40,620 --> 00:23:43,120
Torej bomo šli s to sintakso.

321
00:23:43,120 --> 00:23:46,150
A tudi če nismo šli s to sintakso,

322
00:23:46,150 --> 00:23:49,470
tisto, kar je - bi bilo narobe s tem?

323
00:23:49,470 --> 00:23:52,170
[Študent] Ne rabim ga dereference? >> Ja.

324
00:23:52,170 --> 00:23:55,110
Ne pozabite, da je puščica je implicitno dereference,

325
00:23:55,110 --> 00:23:58,230
in tako, ko smo ravno opravka s struct,

326
00:23:58,230 --> 00:24:04,300
želimo uporabiti. da se na terenu notranjosti struct.

327
00:24:04,300 --> 00:24:07,200
In edini čas, da uporabite puščico, ko želimo narediti -

328
00:24:07,200 --> 00:24:13,450
No, puščica je enaka -

329
00:24:13,450 --> 00:24:17,020
To je tisto, kar bi pomenilo, da če sem uporabil puščico.

330
00:24:17,020 --> 00:24:24,600
Vse arrow sredstva, se dereference to, zdaj pa sem na struct, in lahko dobim polje.

331
00:24:24,600 --> 00:24:28,040
Ali se polje neposredno ali dereference in dobili polje -

332
00:24:28,040 --> 00:24:30,380
Mislim, da to mora biti vrednost.

333
00:24:30,380 --> 00:24:33,910
Ampak tukaj sem, ki se ukvarjajo s samo struct, ne kazalec na struct,

334
00:24:33,910 --> 00:24:38,780
in tako ne morem uporabljati puščico.

335
00:24:38,780 --> 00:24:47,510
Vendar pa lahko te stvari delamo na vseh vozliščih.

336
00:24:47,510 --> 00:24:55,790
Oh, moj bog.

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

338
00:25:09,540 --> 00:25:16,470
Potem bomo lahko ustanovijo podružnice v našem drevesu, lahko imamo 7 -

339
00:25:16,470 --> 00:25:21,650
lahko bi, bi moral opozoriti na levo 3.

340
00:25:21,650 --> 00:25:25,130
Torej, kako bomo to naredili?

341
00:25:25,130 --> 00:25:29,320
[Študenti, nerazumljiv] >> Ja. Naslov vozlišče3,

342
00:25:29,320 --> 00:25:34,170
in če nisi imel naslov, potem to ne bi prevesti.

343
00:25:34,170 --> 00:25:38,190
Ampak ne pozabite, da so kazalci na naslednjih vozlišč.

344
00:25:38,190 --> 00:25:44,930
Pravica mora kazati na 9,

345
00:25:44,930 --> 00:25:53,330
in bi točko 3 o pravici do 6.

346
00:25:53,330 --> 00:25:58,480
Mislim, da je vse pripravljeno. Kakršne koli pripombe ali vprašanja?

347
00:25:58,480 --> 00:26:02,060
[Študent, nerazumljiv] korenine se bo 7.

348
00:26:02,060 --> 00:26:08,210
Lahko samo rečem vozlišče * ptr =

349
00:26:08,210 --> 00:26:14,160
ali korenina = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Za naše namene, bomo morali ukvarjati z vložkom,

351
00:26:20,730 --> 00:26:25,490
Tako bomo želeli napisati funkcijo, ki jo vstavite v to binarno drevo

352
00:26:25,490 --> 00:26:34,230
in vložek je neizbežno, da pokličete malloc ustvariti novo vozlišče za to drevo.

353
00:26:34,230 --> 00:26:36,590
Stvari se bodo grdo z dejstvom, da so nekatere vozlišča

354
00:26:36,590 --> 00:26:38,590
Trenutno je na kupu

355
00:26:38,590 --> 00:26:43,680
in druga vozlišča se bo končal na kup, ko jih vstavite.

356
00:26:43,680 --> 00:26:47,640
To je povsem pravilna, vendar je edini razlog,

357
00:26:47,640 --> 00:26:49,600
smo sposobni to narediti na kupu

358
00:26:49,600 --> 00:26:51,840
je, ker je tak primer izmišljene, da vemo,

359
00:26:51,840 --> 00:26:56,360
Drevo naj bi bila zgrajena kot 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Če ne bi imeli tega, potem ne bi bilo treba knjižnične funkcije malloc na prvem mestu.

361
00:27:02,970 --> 00:27:06,160
Kot bomo videli malo kasneje, bi morali malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Zdaj je povsem razumno, da dajo na kup,

363
00:27:08,570 --> 00:27:14,750
vendar naj se to spremeni v malloc izvajanje.

364
00:27:14,750 --> 00:27:17,160
Torej, vsak od teh je zdaj bo nekaj podobnega

365
00:27:17,160 --> 00:27:24,240
vozlišče * node9 = malloc (sizeof (vozlišče)).

366
00:27:24,240 --> 00:27:28,040
In zdaj bomo morali storiti pregled.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Nisem hotel, da -

368
00:27:34,010 --> 00:27:40,950
vrne 1, potem lahko naredimo node9-> ker zdaj je kazalec,

369
00:27:40,950 --> 00:27:45,300
Vrednost = 6, node9-> levo = NULL,

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

371
00:27:48,930 --> 00:27:51,410
in bomo morali to storiti za vsako od teh vozlišč.

372
00:27:51,410 --> 00:27:57,490
Torej, namesto, kaj je dal notri v ločenem funkcije.

373
00:27:57,490 --> 00:28:00,620
Naj bo vozlišče * build_node,

374
00:28:00,620 --> 00:28:09,050
in to je nekoliko podoben API nudimo za Huffmanovo kodiranje.

375
00:28:09,050 --> 00:28:12,730
Mi vam initializer funkcije za drevo

376
00:28:12,730 --> 00:28:20,520
in deconstructor 'funkcije' za tistimi drevesi in enaka za gozdove.

377
00:28:20,520 --> 00:28:22,570
>> Torej, tukaj bomo imeli initializer funkcijo

378
00:28:22,570 --> 00:28:25,170
da samo zgraditi vozlišče za nas.

379
00:28:25,170 --> 00:28:29,320
In to se dogaja, da si precej natančno tako.

380
00:28:29,320 --> 00:28:32,230
In jaz še bo leni in ne spremenite ime spremenljivke,

381
00:28:32,230 --> 00:28:34,380
čeprav node9 nima nobenega smisla več.

382
00:28:34,380 --> 00:28:38,610
Oh, mislim, da je vrednost node9 ne bi smelo biti 6.

383
00:28:38,610 --> 00:28:42,800
Zdaj se lahko vrnemo node9.

384
00:28:42,800 --> 00:28:49,550
In tukaj bi se morali vrniti nična.

385
00:28:49,550 --> 00:28:52,690
Vsakdo se dogovorijo o tem graditi-vozlišče funkcijo?

386
00:28:52,690 --> 00:28:59,780
Torej, zdaj lahko samo pokličite, da graditi vsako vozlišče z določeno vrednostjo in ničelnih kazalci.

387
00:28:59,780 --> 00:29:09,750
Zdaj lahko rečemo, da lahko naredimo vozel * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
In kaj je naredil. . .

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

390
00:29:33,980 --> 00:29:39,330
In zdaj želimo vzpostaviti enake napotke,

391
00:29:39,330 --> 00:29:42,470
razen zdaj je vse že v smislu kazalcev

392
00:29:42,470 --> 00:29:48,480
Tako ni več treba naslov.

393
00:29:48,480 --> 00:29:56,300
Ok. Torej, kaj je zadnja stvar, ki jo želite narediti?

394
00:29:56,300 --> 00:30:03,850
Tam je do napake kontrole, da ne delam.

395
00:30:03,850 --> 00:30:06,800
Kaj zgraditi vozlišče vrnitev?

396
00:30:06,800 --> 00:30:11,660
[Študent, nerazumljiv] >> Ja. Če malloc ni uspel, se bo vrnil null.

397
00:30:11,660 --> 00:30:16,460
Torej bom leno dal dol, namesto da delaš pogoj za vsakega posebej.

398
00:30:16,460 --> 00:30:22,320
Če je (node9 == NULL, ali - še bolj enostavno,

399
00:30:22,320 --> 00:30:28,020
to ustreza le, če ne node9.

400
00:30:28,020 --> 00:30:38,310
Torej, če ne node9, ali ne node6, ali ne vozlišče3, ali ne node7, vrne 1.

401
00:30:38,310 --> 00:30:42,850
Mogoče bi morali natisniti malloc ni, ali kaj podobnega.

402
00:30:42,850 --> 00:30:46,680
[Študent] Ali lažno enako null, kot tudi?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Vsaka vrednost nič, je napačen.

404
00:30:51,290 --> 00:30:53,920
Tako je sedaj null vrednost nič.

405
00:30:53,920 --> 00:30:56,780
Zero je vrednost nič. Neresnično je vrednost nič.

406
00:30:56,780 --> 00:31:02,130
Vsak - precej le 2 ničti vrednosti, so nične in nič,

407
00:31:02,130 --> 00:31:07,900
napačna je samo hash opredeljen kot nič.

408
00:31:07,900 --> 00:31:13,030
To velja tudi, če ne bomo izjavi globalno spremenljivko.

409
00:31:13,030 --> 00:31:17,890
Če smo imeli Koren vozlišča * tu gor,

410
00:31:17,890 --> 00:31:24,150
Nato - je lepo stvar o globalnih spremenljivk je, da imajo vedno začetno vrednost.

411
00:31:24,150 --> 00:31:27,500
To ni res funkcij, kako notranjost tukaj

412
00:31:27,500 --> 00:31:34,870
če imamo, kot, vozlišče ali vozlišče x *.

413
00:31:34,870 --> 00:31:37,380
Nimamo pojma, kaj x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
ali bi jih lahko natisnete in jih lahko poljubno.

415
00:31:40,700 --> 00:31:44,980
To ni res globalnih spremenljivk.

416
00:31:44,980 --> 00:31:47,450
Torej, vozlišče koren ali vozlišče x.

417
00:31:47,450 --> 00:31:53,410
Privzeto je, da vse, kar je globalna, če ni izrecno initialized na neko vrednost,

418
00:31:53,410 --> 00:31:57,390
ima ničelno vrednost kot svojo vrednost.

419
00:31:57,390 --> 00:32:01,150
Torej, tukaj, vozlišče * koren, ne izrecno inicializirati na nič,

420
00:32:01,150 --> 00:32:06,350
tako da bo njegova privzeta vrednost null, ki je nič Vrednost kazalca.

421
00:32:06,350 --> 00:32:11,870
Privzeta vrednost x bo pomenilo, da x.value nič,

422
00:32:11,870 --> 00:32:14,260
x.left nič, in x.right je nična.

423
00:32:14,260 --> 00:32:21,070
Zato, ker je struct bo vsa polja v struct bo ničti vrednosti.

424
00:32:21,070 --> 00:32:24,410
Ni nam treba uporabiti, da sem, čeprav.

425
00:32:24,410 --> 00:32:27,320
[] V Študentski konstrukti so drugačni od drugih dejavnikov, in druge spremenljivke

426
00:32:27,320 --> 00:32:31,400
smetarska vrednote, to so ničle?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Druge vrednosti preveč. Torej, x, x bo nič.

428
00:32:36,220 --> 00:32:40,070
Če je v svetovnem obsegu, da ima začetno vrednost. >> Redu.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Ali je začetna vrednost, ki jo je dal to ali nič.

430
00:32:48,950 --> 00:32:53,260
Mislim, da skrbi za vse to.

431
00:32:53,260 --> 00:32:58,390
>> Ok. Torej, naslednjič, del vprašanja sprašuje,

432
00:32:58,390 --> 00:33:01,260
"Zdaj želimo, da napišete funkcijo imenovano vsebuje

433
00:33:01,260 --> 00:33:04,930
s prototipom bool vsebuje int vrednost. "

434
00:33:04,930 --> 00:33:08,340
Mi ne boš naredil int vsebuje int vrednost.

435
00:33:08,340 --> 00:33:15,110
Naš prototip bo izgledal

436
00:33:15,110 --> 00:33:22,380
bool vsebuje (int vrednost.

437
00:33:22,380 --> 00:33:24,490
In potem bomo tudi dogaja, da prenese to drevo

438
00:33:24,490 --> 00:33:28,870
da bi moralo biti preverjanje, da vidim, če je to vrednost.

439
00:33:28,870 --> 00:33:38,290
Torej vozlišče * drevo). Ok.

440
00:33:38,290 --> 00:33:44,440
In potem lahko rečemo tudi nekaj podobnega,

441
00:33:44,440 --> 00:33:46,090
Morda bomo želeli printf ali nekaj.

442
00:33:46,090 --> 00:33:51,040
Vsebuje 6, naše korenine.

443
00:33:51,040 --> 00:33:54,300
To je treba vrniti eno, ali resnično,

444
00:33:54,300 --> 00:33:59,390
ker vsebuje naj 5 koren vrne false.

445
00:33:59,390 --> 00:34:02,690
Torej, vzemite si sekundo časa za izvedbo tega.

446
00:34:02,690 --> 00:34:06,780
To lahko storite bodisi iterativno ali rekurzivno.

447
00:34:06,780 --> 00:34:09,739
Za lepo stvar o tem, kako smo jo določili stvari je, da

448
00:34:09,739 --> 00:34:12,300
to bi lahko bilo naše rekurzivni rešitvi veliko lažje

449
00:34:12,300 --> 00:34:14,719
kot globalno spremenljivko in kako je.

450
00:34:14,719 --> 00:34:19,750
Ker če imamo samo vsebuje int vrednost, potem nikakor ne rekurzivnem navzdol subtrees.

451
00:34:19,750 --> 00:34:24,130
Morali bi imeti ločeno funkcijo pomočnika, ki recurses določitvi subtrees za nas.

452
00:34:24,130 --> 00:34:29,610
Ampak, ker smo spremenili, da bi drevo kot argument,

453
00:34:29,610 --> 00:34:32,760
, ki naj bi bila vedno na prvem mestu,

454
00:34:32,760 --> 00:34:35,710
Zdaj bomo lahko recurse lažje.

455
00:34:35,710 --> 00:34:38,960
Zato ponavlja ali rekurzivna, bova šla skozi tako,

456
00:34:38,960 --> 00:34:46,139
ampak bomo videli, da je rekurzivni konča pa precej enostavno.

457
00:34:59,140 --> 00:35:02,480
Ok. Ali kdo ima nekaj, kar lahko skupaj z?

458
00:35:02,480 --> 00:35:12,000
>> [Študent] Imam iterativno rešitev. >> Redu, ponavlja.

459
00:35:12,000 --> 00:35:16,030
Ok, to izgleda dobro.

460
00:35:16,030 --> 00:35:18,920
Torej, da nas hoče hoditi po njej?

461
00:35:18,920 --> 00:35:25,780
[Študent] Seveda. Zato sem določene temp spremenljivko dobili prvo vozlišče drevesa.

462
00:35:25,780 --> 00:35:28,330
In potem sem zanko skozi medtem ko temperatura ni enaka nič,

463
00:35:28,330 --> 00:35:31,700
Medtem, ko je bil še v drevo, se mi zdi.

464
00:35:31,700 --> 00:35:35,710
In če je vrednost enaka vrednosti, ki kaže na temp,

465
00:35:35,710 --> 00:35:37,640
nato vrne vrednost.

466
00:35:37,640 --> 00:35:40,210
Drugače pa preveri, če je na desni strani ali na levi strani.

467
00:35:40,210 --> 00:35:43,400
Če se vam kdaj situacijo, v kateri ni več dreves,

468
00:35:43,400 --> 00:35:47,330
Nato se vrne - ko pride iz zanke in vrne false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Ok. Tako, da izgleda dobro.

470
00:35:52,190 --> 00:35:58,470
Vsakdo ima kakršne koli pripombe na karkoli?

471
00:35:58,470 --> 00:36:02,400
Nimam pravilnosti komentarjev na vse.

472
00:36:02,400 --> 00:36:11,020
Edina stvar, ki jo lahko naredimo je ta tip.

473
00:36:11,020 --> 00:36:21,660
Oh, to se dogaja, da gredo malo podolgovate.

474
00:36:21,660 --> 00:36:33,460
Jaz bom popraviti to izmislil. Ok.

475
00:36:33,460 --> 00:36:37,150
>> Vsi se morajo zavedati, kako ternarna deluje.

476
00:36:37,150 --> 00:36:38,610
Tam so bili zagotovo kvizov v preteklosti

477
00:36:38,610 --> 00:36:41,170
da vam s funkcijo trikomponentne subjekta,

478
00:36:41,170 --> 00:36:45,750
in pravijo, prevedi to, naredi kaj, da ne uporablja trikomponentnih.

479
00:36:45,750 --> 00:36:49,140
Torej, to je zelo pogost primer, ko bi mislil, da uporabite trikomponentnih,

480
00:36:49,140 --> 00:36:54,610
kjer je, če nekateri pogoji, določeni s spremenljivko nekaj,

481
00:36:54,610 --> 00:36:58,580
drugega iz te iste spremenljivke v nekaj drugega.

482
00:36:58,580 --> 00:37:03,390
To je nekaj, kar se zelo pogosto spremenijo v te stvari

483
00:37:03,390 --> 00:37:14,420
kjer je določeno, da se za to spremenljivko - ali pa je to res? Potem, pa to.

484
00:37:14,420 --> 00:37:18,550
[Študent] Prva je če je to res, kajne?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Ja. Tako kot sem vedno prebral, je, temperatura je enaka vrednost, večjo od vrednosti temp,

486
00:37:25,570 --> 00:37:30,680
potem je to, pa to. To sprašujem.

487
00:37:30,680 --> 00:37:35,200
Je večja? Potem pa je prva stvar. Sicer ne drugo stvar.

488
00:37:35,200 --> 00:37:41,670
Sem skoraj vedno - kolona, ​​sem - v moji glavi, sem prebral, kot drugje.

489
00:37:41,670 --> 00:37:47,180
>> Ima kdo rekurzivna rešitev?

490
00:37:47,180 --> 00:37:49,670
Ok. Ta bomo - to bi že bilo super,

491
00:37:49,670 --> 00:37:53,990
vendar se bomo, da bi bilo še bolje.

492
00:37:53,990 --> 00:37:58,720
To je precej točno isto zamisel.

493
00:37:58,720 --> 00:38:03,060
To je samo, no, hočeš, da pojasni?

494
00:38:03,060 --> 00:38:08,340
[Študent] Seveda. Zato smo se prepričajte, da je drevo ni nič prvič,

495
00:38:08,340 --> 00:38:13,380
ker če je drevo nična, potem se dogaja, da vrne false, ker nismo našli.

496
00:38:13,380 --> 00:38:19,200
In če je še vedno drevo, smo šli v - najprej preveri, če je vrednost trenutnega vozla.

497
00:38:19,200 --> 00:38:23,740
Return true, če je, in če ne bomo recurse na levo ali desno.

498
00:38:23,740 --> 00:38:25,970
Ali to zveni primerno? >> Aha. (Sporazum)

499
00:38:25,970 --> 00:38:33,880
Torej, opazil, da je to skoraj - strukturno zelo podobni ponavljajočim rešitev.

500
00:38:33,880 --> 00:38:38,200
To je samo, da namesto rekurzivnem smo imeli while zanko.

501
00:38:38,200 --> 00:38:40,840
In osnovna tukaj, kjer drevo ni enak za nično

502
00:38:40,840 --> 00:38:44,850
je pogoj, pod katerim sva se razšla iz while zanko.

503
00:38:44,850 --> 00:38:50,200
Oni so zelo podobne. Vendar pa bomo lahko to en korak naprej.

504
00:38:50,200 --> 00:38:54,190
Zdaj delamo isto stvar tukaj.

505
00:38:54,190 --> 00:38:57,680
Obvestilo smo vračajo enako v obe smeri,

506
00:38:57,680 --> 00:39:00,220
razen za en argument je drugačna.

507
00:39:00,220 --> 00:39:07,950
Tako se bomo, da se to v ternarni.

508
00:39:07,950 --> 00:39:13,790
Zadel sem nekaj opcij, in to je simbol. Ok.

509
00:39:13,790 --> 00:39:21,720
Torej se bomo vrnili vsebuje tem.

510
00:39:21,720 --> 00:39:28,030
To je pridobivanje biti več vrstic, no, povečani je.

511
00:39:28,030 --> 00:39:31,060
Ponavadi, kot stilistični stvar, jaz ne mislim, da veliko ljudi

512
00:39:31,060 --> 00:39:38,640
dal prostor za puščico, ampak mislim, če ste dosledni, je to v redu.

513
00:39:38,640 --> 00:39:44,320
Če je vrednost nižja od vrednosti, drevesa, želimo recurse na levi strani drevesa,

514
00:39:44,320 --> 00:39:53,890
pa želimo recurse na desni drevo.

515
00:39:53,890 --> 00:39:58,610
Tako, da je prvi korak, da bi ta videz manjše.

516
00:39:58,610 --> 00:40:02,660
Korak 2, da bi ta videz manjši -

517
00:40:02,660 --> 00:40:09,150
lahko ločite na več vrstic.

518
00:40:09,150 --> 00:40:16,500
Ok. Korak 2 od česar je videti manjša je tukaj,

519
00:40:16,500 --> 00:40:25,860
Tako izračunana vrednost je enaka vrednosti drevo, ali vsebuje karkoli.

520
00:40:25,860 --> 00:40:28,340
>> To je pomembna stvar.

521
00:40:28,340 --> 00:40:30,860
Nisem prepričan, če je to izrecno povedal v razredu,

522
00:40:30,860 --> 00:40:34,740
vendar pa je pozval kratkega stika vrednotenje.

523
00:40:34,740 --> 00:40:41,060
Ideja je vrednost == drevo vrednost.

524
00:40:41,060 --> 00:40:49,960
Če je to res, potem je to res, in želimo "ali", da se z vse, kar je tukaj.

525
00:40:49,960 --> 00:40:52,520
Torej, ne da bi sploh razmišljal, kar je tukaj,

526
00:40:52,520 --> 00:40:55,070
kakšen je celoten izraz bo vrnil?

527
00:40:55,070 --> 00:40:59,430
[Študent] True? >> Ja, saj res ničesar,

528
00:40:59,430 --> 00:41:04,990
or'd - ali res or'd z vsem, kar je nujno res.

529
00:41:04,990 --> 00:41:08,150
Torej takoj, ko bomo videli vrnjeno vrednost = vrednost drevo,

530
00:41:08,150 --> 00:41:10,140
smo le, da bo vrnil res.

531
00:41:10,140 --> 00:41:15,710
Niti bo recurse nadalje vsebuje po vrsti.

532
00:41:15,710 --> 00:41:20,980
Mi lahko to en korak naprej.

533
00:41:20,980 --> 00:41:29,490
Nazaj drevo ni enak za nično in vse to.

534
00:41:29,490 --> 00:41:32,650
To je bilo eno vrstico funkcijo.

535
00:41:32,650 --> 00:41:36,790
To je tudi primer kratkega stika oceno.

536
00:41:36,790 --> 00:41:40,680
Zdaj pa je ista ideja -

537
00:41:40,680 --> 00:41:47,320
namesto da bi - tako da, če drevo ni enak nič - ali, dobro,

538
00:41:47,320 --> 00:41:49,580
če drevo ne enak nič, kar je slabo tako,

539
00:41:49,580 --> 00:41:54,790
Če drevo je enaka nič, potem je prvi pogoj, se bo napačen.

540
00:41:54,790 --> 00:42:00,550
Torej lažno anded s čimerkoli se bo kaj?

541
00:42:00,550 --> 00:42:04,640
[Študent] False. >> Ja. To je druga polovica kratkega stika ocene

542
00:42:04,640 --> 00:42:10,710
če, če drevo ne enaka nič, potem ne bo niti go -

543
00:42:10,710 --> 00:42:14,930
ali če je drevo ima enak null, potem ne bo naredil vrednost == drevo vrednost.

544
00:42:14,930 --> 00:42:17,010
Mi smo le, da bo nemudoma vrne false.

545
00:42:17,010 --> 00:42:20,970
Kar je pomembno, saj če ni kratkega stika oceni,

546
00:42:20,970 --> 00:42:25,860
potem, če drevo ima enak nič, ta drugi pogoj se dogaja, da krivdo SEG,

547
00:42:25,860 --> 00:42:32,510
ker je drevo-> vrednost Dereferenciranje null.

548
00:42:32,510 --> 00:42:40,490
Torej, to je to. Lahko bi to - premik enkrat več.

549
00:42:40,490 --> 00:42:44,840
To je zelo običajna stvar tako, da se ta ne eno vrstico s tem,

550
00:42:44,840 --> 00:42:49,000
ampak to je običajna stvar v razmerah, morda ni v redu,

551
00:42:49,000 --> 00:42:59,380
če pa (drevo! = NULL, in drevo-> vrednost == vrednost), karkoli.

552
00:42:59,380 --> 00:43:01,560
To je zelo pogosto stanje, kjer je namesto ob

553
00:43:01,560 --> 00:43:06,770
, da bi prekinil to v dveh investicijskih skladov, kjer je všeč, je drevo nična?

554
00:43:06,770 --> 00:43:11,780
Ok, to ni nič, tako da zdaj je drevo vrednost je enaka vrednosti? Naredite to.

555
00:43:11,780 --> 00:43:17,300
Namesto tega je pogoj, to ne bo nikoli seg napako

556
00:43:17,300 --> 00:43:21,220
ker bo prekinil, če se to zgodi, je ničen.

557
00:43:21,220 --> 00:43:24,000
Mislim, da če je vaš drevo je v celoti neveljavna kazalec, lahko še vedno seg napako

558
00:43:24,000 --> 00:43:26,620
vendar ne more seg napako, če drevo je nična.

559
00:43:26,620 --> 00:43:32,900
Če ne bi bilo nič, bi prekinil, preden boste kdaj dereferenced kazalec na prvem mestu.

560
00:43:32,900 --> 00:43:35,000
[Študent] Ali je to ti leni ocena?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy ocena je ločena stvar.

562
00:43:40,770 --> 00:43:49,880
Lazy vrednotenje je bolj kot vas za vrednost,

563
00:43:49,880 --> 00:43:54,270
prosite za izračun vrednosti, vrsta, vendar ga ne potrebujejo takoj.

564
00:43:54,270 --> 00:43:59,040
Torej, dokler ne boste dejansko potrebovali, ni ocenjena.

565
00:43:59,040 --> 00:44:03,920
To ni ravno isto, ampak v Huffman pset,

566
00:44:03,920 --> 00:44:06,520
se pravi, da smo "leno" napisati.

567
00:44:06,520 --> 00:44:08,670
Razlog, da to, da je zato, ker smo dejansko buffering WRITE -

568
00:44:08,670 --> 00:44:11,820
ne želimo, da napišete posamezne bite hkrati,

569
00:44:11,820 --> 00:44:15,450
ali posameznih zlogov v času, smo namesto tega želeli, da bi dobili kos bajtov.

570
00:44:15,450 --> 00:44:19,270
Potem ko smo kos bajte, potem bomo to napiši.

571
00:44:19,270 --> 00:44:22,640
Čeprav ga prosil, da napišete - in fwrite in fread storijo enako stvari.

572
00:44:22,640 --> 00:44:26,260
Ti varovalni svoje bere in piše.

573
00:44:26,260 --> 00:44:31,610
Čeprav ga prosim, da takoj napisati, da verjetno ne bo.

574
00:44:31,610 --> 00:44:34,540
In ne moremo biti prepričani, da gredo stvari je treba pisno

575
00:44:34,540 --> 00:44:37,540
dokler ne pokličeš hfclose ali karkoli že je,

576
00:44:37,540 --> 00:44:39,620
ki pa pravi, ok, bom zaprl svojo datoteko,

577
00:44:39,620 --> 00:44:43,450
to pomeni, da bi bilo bolje napisati vse, kar sem še ni bila napisana.

578
00:44:43,450 --> 00:44:45,770
To je ni treba pisati vse ven

579
00:44:45,770 --> 00:44:49,010
dokler se ne zaprete datoteko, in potem ga je treba.

580
00:44:49,010 --> 00:44:56,220
Torej, to je samo tisto, kar leni - počaka, dokler ta ne bo zgodilo.

581
00:44:56,220 --> 00:44:59,990
Ta - sprejme 51 in boš šel v to bolj podrobno,

582
00:44:59,990 --> 00:45:05,470
ker OCaml in vse, kar 51, je vse rekurzije.

583
00:45:05,470 --> 00:45:08,890
Ni iterativno rešitev, v bistvu.

584
00:45:08,890 --> 00:45:11,550
Vse je rekurzija, in leni ocenjevanje

585
00:45:11,550 --> 00:45:14,790
se bo pomembno za veliko primerih

586
00:45:14,790 --> 00:45:19,920
kjer, če nisi leno oceniti, bi to pomenilo -

587
00:45:19,920 --> 00:45:24,760
Primer je potoki, ki so neskončno dolgo.

588
00:45:24,760 --> 00:45:30,990
V teoriji, lahko si misliš o naravnih števil kot tok 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Torej leno ocenili stvari so v redu.

590
00:45:33,090 --> 00:45:37,210
Če rečem, želim 10. številko, potem lahko ocenim do 10. številke.

591
00:45:37,210 --> 00:45:40,300
Če želim stoto številko, potem lahko ocenim do stote številke.

592
00:45:40,300 --> 00:45:46,290
Brez ocene leni, potem se dogaja, da poskušajo oceniti vse številke takoj.

593
00:45:46,290 --> 00:45:50,000
Saj ocenjevanje neskončno veliko številk, in to preprosto ni mogoče.

594
00:45:50,000 --> 00:45:52,080
Torej obstaja veliko okoliščin, kjer leni ocenjevanje

595
00:45:52,080 --> 00:45:57,840
je samo pomembno, da so stvari za delo.

596
00:45:57,840 --> 00:46:05,260
>> Zdaj želimo, da napišete vložek, kjer vložek se bo

597
00:46:05,260 --> 00:46:08,430
Podobno spremembo v svoji definiciji.

598
00:46:08,430 --> 00:46:10,470
Torej, zdaj je bool vstavi (int vrednost).

599
00:46:10,470 --> 00:46:23,850
Mi bomo spremenili, da bool vstavi (int vrednost, vozlišče * drevo).

600
00:46:23,850 --> 00:46:29,120
Mi smo dejansko dogaja, da spremenite, da spet malo, bomo videli, zakaj.

601
00:46:29,120 --> 00:46:32,210
In gremo build_node, samo za vraga njo,

602
00:46:32,210 --> 00:46:36,730
zgoraj vstavite tako da nam ni treba napisati funkcijo prototip.

603
00:46:36,730 --> 00:46:42,450
Kateri je namig, da si bo z uporabo build_node v vložek.

604
00:46:42,450 --> 00:46:49,590
Ok. Vzemite si trenutek za to.

605
00:46:49,590 --> 00:46:52,130
Mislim, da sem rešil z revizijo, če želite potegniti iz tega,

606
00:46:52,130 --> 00:47:00,240
ali vsaj, sem zdaj.

607
00:47:00,240 --> 00:47:04,190
Želel sem rahlo odmor za razmislek o logiki vložka,

608
00:47:04,190 --> 00:47:08,750
če ne moreš razmišljati o tem.

609
00:47:08,750 --> 00:47:12,860
V bistvu, boste le kdaj se vstavi na listi.

610
00:47:12,860 --> 00:47:18,640
Všeč mi je, če sem vstavil 1, potem bom zagotovo bo treba vstavljanje 1 -

611
00:47:18,640 --> 00:47:21,820
Jaz bom spremenite v črno - bom lahko vstavite 1 tukaj.

612
00:47:21,820 --> 00:47:28,070
Ali pa, če sem vstavil 4, želim, da se vstavljanje 4 tukaj.

613
00:47:28,070 --> 00:47:32,180
Torej, ni važno, kaj si naredil, da boš lahko vstavite na list.

614
00:47:32,180 --> 00:47:36,130
Vse kar morate storiti je, da izbirate z drevesa, dokler ne pridete do vozlišča

615
00:47:36,130 --> 00:47:40,890
da mora biti vozlišče, je eden od staršev, novega vozlišča staršev,

616
00:47:40,890 --> 00:47:44,560
in nato spremenite svoj levi ali desni kazalec, odvisno od tega, ali

617
00:47:44,560 --> 00:47:47,060
da je večja ali manjša od tekoče vozlišče.

618
00:47:47,060 --> 00:47:51,180
Spremenite to kazalec, da kaže na novo vozlišče.

619
00:47:51,180 --> 00:48:05,490
Torej izbirate z drevesa, bi krilo točko na novo vozlišče.

620
00:48:05,490 --> 00:48:09,810
Prav tako mislim, da o tem, zakaj prepoveduje s položajem pred

621
00:48:09,810 --> 00:48:17,990
kjer sem izdelana binarno drevo, kjer je bila pravilna

622
00:48:17,990 --> 00:48:19,920
če si samo pogledal na enem vozlišču,

623
00:48:19,920 --> 00:48:24,830
ampak 9 je na levi strani 7, če poudarili navzdol vse do konca.

624
00:48:24,830 --> 00:48:29,770
Torej, to je nemogoče v tem primeru, saj je -

625
00:48:29,770 --> 00:48:32,530
Razmišljam o vstavljanju 9 ali kaj podobnega, ob prvem vozlišču,

626
00:48:32,530 --> 00:48:35,350
Bom videl 7 in sem samo šla na desno.

627
00:48:35,350 --> 00:48:38,490
Torej, ni važno, kaj naj naredim, če sem ga vstavite bo lista,

628
00:48:38,490 --> 00:48:40,790
in listom z uporabo ustreznih algoritem,

629
00:48:40,790 --> 00:48:43,130
to se dogaja, da je nemogoče za mene, da vstavite 9 levo od 7

630
00:48:43,130 --> 00:48:48,250
saj takoj ko sem zadel 7 bom šel desno.

631
00:48:59,740 --> 00:49:02,070
Ali ima kdo kaj začeti s?

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

633
00:49:05,480 --> 00:49:09,200
[Študent, nerazumljiv]

634
00:49:09,200 --> 00:49:14,390
[Other študent, nerazumljiv]

635
00:49:14,390 --> 00:49:18,330
[Bowden] je cenjen je. Ok. Želite, da pojasni?

636
00:49:18,330 --> 00:49:20,690
>> [Študent] Ker vemo, da smo vstavljanje

637
00:49:20,690 --> 00:49:24,060
nova vozlišča na koncu drevesa,

638
00:49:24,060 --> 00:49:28,070
Jaz zanko skozi drevesa iterativno

639
00:49:28,070 --> 00:49:31,360
dokler nisem prišel do vozlišča, ki opozoril na null.

640
00:49:31,360 --> 00:49:34,220
In potem sem se odločil, da ga proda bodisi na desni strani ali na levi strani

641
00:49:34,220 --> 00:49:37,420
uporabo te pravice spremenljivke, saj mi je povedal, kje je bilo.

642
00:49:37,420 --> 00:49:41,850
In potem, v bistvu sem na ta zadnji -

643
00:49:41,850 --> 00:49:47,520
da temperatura vozlišče kaže na novo vozlišče, ki je bilo ustvarjanje,

644
00:49:47,520 --> 00:49:50,770
bodisi na levo ali na desno stran, odvisno od tega, kaj je vrednost desno je bil.

645
00:49:50,770 --> 00:49:56,530
Končno sem nastavil novo vozlišče vrednost vrednosti njene testiranja.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Ok, tako da sem videl eno vprašanje tukaj.

647
00:49:59,550 --> 00:50:02,050
To je tako kot 95% poti tja.

648
00:50:02,050 --> 00:50:07,550
Eno vprašanje, ki sem videl, no, pa še kdo drug videl težavo?

649
00:50:07,550 --> 00:50:18,400
Kaj so okoliščine, v katerih se iztrgajo iz zanke?

650
00:50:18,400 --> 00:50:22,100
[Študent] Če temperatura je nična? >> Ja. Torej, kako si iztrgajo iz zanke, če temperatura je nična.

651
00:50:22,100 --> 00:50:30,220
Ampak, kaj naj storim tukaj?

652
00:50:30,220 --> 00:50:35,410
Jaz dereference temp, ki je neizogibno null.

653
00:50:35,410 --> 00:50:39,840
Torej druga stvar, ki jo morate storiti je, ne le slediti, dokler temperatura je nična,

654
00:50:39,840 --> 00:50:45,590
želite slediti staršev v vsakem trenutku.

655
00:50:45,590 --> 00:50:52,190
Želimo si tudi, staršev vozlišče *, mislim, da bomo tako lažje, da je nična na prvi.

656
00:50:52,190 --> 00:50:55,480
To se dogaja, da imajo čudno obnašanje pri korenu drevesa,

657
00:50:55,480 --> 00:50:59,210
ampak bomo prišli do tega.

658
00:50:59,210 --> 00:51:03,950
Če je vrednost večja od česarkoli že, potem temp = temp prav.

659
00:51:03,950 --> 00:51:07,910
Toda preden bomo to storili, starši = temp.

660
00:51:07,910 --> 00:51:14,500
Ali so starši vedno bo enako temp? Je tako?

661
00:51:14,500 --> 00:51:19,560
Če temperatura ni nič, potem pa grem dol, da se premaknete, ni važno kaj,

662
00:51:19,560 --> 00:51:24,030
do vozlišča, za katere temperatura je nadrejena.

663
00:51:24,030 --> 00:51:27,500
Torej staršev bo v temp, potem pa sem premakniti temp navzdol.

664
00:51:27,500 --> 00:51:32,410
Zdaj temp nič, ampak staršev opozarja na matično stvar, ki je nična.

665
00:51:32,410 --> 00:51:39,110
Torej tu spodaj, ne želim, da nastavite desno enaka 1.

666
00:51:39,110 --> 00:51:41,300
Zato sem se preselil na desno stran, tako da, če prav = 1,

667
00:51:41,300 --> 00:51:45,130
in mislim, da si tudi ti želiš narediti -

668
00:51:45,130 --> 00:51:48,530
če premaknete v levo, ki jo želite nastaviti pravica enak 0.

669
00:51:48,530 --> 00:51:55,950
Ali pa, če si kdaj premakniti na desno.

670
00:51:55,950 --> 00:51:58,590
Torej, desno = 0. Če desno = 1,

671
00:51:58,590 --> 00:52:04,260
Zdaj želimo, da bi se osnovni pravo newnode kazalca,

672
00:52:04,260 --> 00:52:08,520
pa želimo, da bi matični levi newnode kazalca.

673
00:52:08,520 --> 00:52:16,850
Vprašanja o tem?

674
00:52:16,850 --> 00:52:24,880
Ok. Torej, to je način, - no, pravzaprav, namesto da delaš to,

675
00:52:24,880 --> 00:52:29,630
1/2 mi pričakujemo, da uporabite build_node.

676
00:52:29,630 --> 00:52:40,450
In potem, če newnode enaka nič, vrne false.

677
00:52:40,450 --> 00:52:44,170
To je to. No, to je tisto, kar smo pričakovali, da narediš.

678
00:52:44,170 --> 00:52:47,690
>> To je tisto, kar je osebje rešitve storiti.

679
00:52:47,690 --> 00:52:52,360
Ne strinjam se s tem, kot "pravi" način bo o tem

680
00:52:52,360 --> 00:52:57,820
vendar je to popolnoma v redu in da bo delovalo.

681
00:52:57,820 --> 00:53:02,840
Ena stvar, ki je malo čudno, zdaj je

682
00:53:02,840 --> 00:53:08,310
če drevo prične za nično, se peljemo v ničelno drevo.

683
00:53:08,310 --> 00:53:12,650
Mislim, da je odvisno od tega, kako opredeliti obnašanja za prenos v ničelno drevo.

684
00:53:12,650 --> 00:53:15,490
Mislil sem, da če se boste peljali v ničelno drevo,

685
00:53:15,490 --> 00:53:17,520
Nato vstavite vrednosti v ničelno drevo

686
00:53:17,520 --> 00:53:23,030
Morala bi se vrniti drevo, kjer je edina vrednost je eno vozlišče.

687
00:53:23,030 --> 00:53:25,830
Ali se strinjate s tem? Lahko bi, če bi želel,

688
00:53:25,830 --> 00:53:28,050
če se boste peljali v ničelno drevo

689
00:53:28,050 --> 00:53:31,320
in želite vstaviti vrednost vanjo, vrne false.

690
00:53:31,320 --> 00:53:33,830
To je do vas, da določite, da.

691
00:53:33,830 --> 00:53:38,320
Če želite to narediti prvo stvar, kar sem rekel, in nato -

692
00:53:38,320 --> 00:53:40,720
No, boste imeli težave pri tem, da zaradi

693
00:53:40,720 --> 00:53:44,090
da bi bilo lažje, če bi imeli svetovni kazalec na stvari,

694
00:53:44,090 --> 00:53:48,570
vendar pa ne, tako da če je drevo nič, nič ne moremo storiti glede tega.

695
00:53:48,570 --> 00:53:50,960
Mi lahko samo vrne false.

696
00:53:50,960 --> 00:53:52,840
Torej bom zamenjati vložek.

697
00:53:52,840 --> 00:53:56,540
Mi lahko samo tehnično spremembo te prav tukaj,

698
00:53:56,540 --> 00:53:58,400
kako je ponavljanjem nad stvarmi,

699
00:53:58,400 --> 00:54:04,530
vendar bom zamenjati vložek, da se vozlišče ** drevo.

700
00:54:04,530 --> 00:54:07,510
Dvojni kazalci.

701
00:54:07,510 --> 00:54:09,710
Kaj to pomeni?

702
00:54:09,710 --> 00:54:12,330
Namesto da se ukvarjajo s kazalci v vozlišč,

703
00:54:12,330 --> 00:54:16,690
stvar bom lahko manipulira je to kazalec.

704
00:54:16,690 --> 00:54:18,790
Grem, da se manipulira ta kazalec.

705
00:54:18,790 --> 00:54:21,770
Grem, da se manipulira kazalce neposredno.

706
00:54:21,770 --> 00:54:25,760
To je smiselno, saj razmišljam o določitvi -

707
00:54:25,760 --> 00:54:33,340
No, sedaj to kaže na null.

708
00:54:33,340 --> 00:54:38,130
Kaj želim storiti, je to manipulira kazalec, da kaže ni nič.

709
00:54:38,130 --> 00:54:40,970
Želim, da pokažete svojo novo vozlišče.

710
00:54:40,970 --> 00:54:44,870
Če se le slediti svojemu kazalcev kazalcev,

711
00:54:44,870 --> 00:54:47,840
potem mi ni treba slediti matične kazalca.

712
00:54:47,840 --> 00:54:52,640
Jaz lahko samo slediti, da vidim, če je kazalec kaže na null,

713
00:54:52,640 --> 00:54:54,580
in če kazalec kaže na null,

714
00:54:54,580 --> 00:54:57,370
spremenite, da kaže na vozlišče želim.

715
00:54:57,370 --> 00:55:00,070
In to lahko spremeni, saj imam kazalec na kazalec.

716
00:55:00,070 --> 00:55:02,040
Poglejmo to prav zdaj.

717
00:55:02,040 --> 00:55:05,470
Lahko dejansko narediti rekurzivno precej enostavno.

718
00:55:05,470 --> 00:55:08,080
Ali želimo to storiti?

719
00:55:08,080 --> 00:55:10,980
Da, imamo.

720
00:55:10,980 --> 00:55:16,790
>> Poglejmo rekurzivno.

721
00:55:16,790 --> 00:55:24,070
Prvič, kaj je naša osnovna bo?

722
00:55:24,070 --> 00:55:29,140
Skoraj vedno naša osnovna, ampak dejansko je to nekako zapleteno.

723
00:55:29,140 --> 00:55:34,370
Prvi stvari prvi, če (drevo == NULL)

724
00:55:34,370 --> 00:55:37,550
Mislim, da smo le, da bo vrne false.

725
00:55:37,550 --> 00:55:40,460
To je drugačen od vašega drevesa čemer null.

726
00:55:40,460 --> 00:55:44,510
To je kazalec na korenski kazalec čemer null

727
00:55:44,510 --> 00:55:48,360
kar pomeni, da je vaš korenski kazalec ne obstaja.

728
00:55:48,360 --> 00:55:52,390
Torej tukaj, če naredim

729
00:55:52,390 --> 00:55:55,760
vozlišče * - kaj je pravkar ponovno to.

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

731
00:55:58,960 --> 00:56:00,730
in potem bom poklical vložek s tem kaj takega,

732
00:56:00,730 --> 00:56:04,540
vstavite v 4 in korenine.

733
00:56:04,540 --> 00:56:06,560
Torej & koren, če je korenina vozlišče *

734
00:56:06,560 --> 00:56:11,170
Nato in korenine se bo vozlišče. **

735
00:56:11,170 --> 00:56:15,120
To je veljavna. V tem primeru, drevo, gor,

736
00:56:15,120 --> 00:56:20,120
Drevo ni nič - ali vložek.

737
00:56:20,120 --> 00:56:24,630
Tukaj. Drevo ni nič, * drevo nič, kar je v redu

738
00:56:24,630 --> 00:56:26,680
ker če * drevo je nična, potem ga lahko manipulirati

739
00:56:26,680 --> 00:56:29,210
za zdaj kažejo na to, kar hočem izpostaviti.

740
00:56:29,210 --> 00:56:34,750
Ampak, če drevo je nična, kar pomeni, da sem prišel sem in rekel nič.

741
00:56:34,750 --> 00:56:42,710
To nima nobenega smisla. Ne morem storiti ničesar s tem.

742
00:56:42,710 --> 00:56:45,540
Če drevo nič, vrne false.

743
00:56:45,540 --> 00:56:48,220
Tako sem v bistvu že povedal, kaj naše resnično osnovna zadeva.

744
00:56:48,220 --> 00:56:50,580
In kaj je to, da bo?

745
00:56:50,580 --> 00:56:55,030
[Študent, nerazumljiv]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Da. Torej, če (* drevo == NULL).

747
00:57:00,000 --> 00:57:04,520
To se nanaša na primer tukaj

748
00:57:04,520 --> 00:57:09,640
če, če je moja rdeča kazalec kazalec sem osredotočen na,

749
00:57:09,640 --> 00:57:12,960
Tako kot sem osredotočena na ta kazalec, zdaj sem osredotočen na ta kazalec.

750
00:57:12,960 --> 00:57:15,150
Sedaj sem osredotočena na ta kazalec.

751
00:57:15,150 --> 00:57:18,160
Torej, če je moja rdeča kazalec, ki je moj vozlišče **

752
00:57:18,160 --> 00:57:22,880
je kdaj - če *, moja rdeča kazalec je vedno nič,

753
00:57:22,880 --> 00:57:28,470
to pomeni, da sem v primeru, ko sem se osredotoča na kazalec, ki kaže -

754
00:57:28,470 --> 00:57:32,530
To je kazalec, ki pripada lista.

755
00:57:32,530 --> 00:57:41,090
Rad bi spremenil to kazalec, da kaže na mojo novo vozlišče.

756
00:57:41,090 --> 00:57:45,230
Pridi nazaj sem.

757
00:57:45,230 --> 00:57:56,490
Moj newnode bo samo vozlišče * n = build_node (vrednost)

758
00:57:56,490 --> 00:58:07,300
nato n, če je n = null, vrne false.

759
00:58:07,300 --> 00:58:12,600
Sicer želimo spremeniti tisto, kar je trenutno kazalec kaže na

760
00:58:12,600 --> 00:58:17,830
do sedaj kaže na našo novo zgrajenega vozlišča.

761
00:58:17,830 --> 00:58:20,280
Mi lahko dejansko narediti, da tukaj.

762
00:58:20,280 --> 00:58:30,660
Namesto da bi rekel n, pravimo drevo * = če drevesa *.

763
00:58:30,660 --> 00:58:35,450
Vsi razumemo, da je? Da z obravnavo kazalci na kazalce,

764
00:58:35,450 --> 00:58:40,750
lahko spremenite ničelne napotke opozoriti na stvari, ki jih želimo izpostaviti.

765
00:58:40,750 --> 00:58:42,820
To je naša osnovna.

766
00:58:42,820 --> 00:58:45,740
>> Zdaj naša ponovitev, ali naše rekurzija,

767
00:58:45,740 --> 00:58:51,430
se bo zelo podoben vsem drugim recursions smo počeli.

768
00:58:51,430 --> 00:58:55,830
Bomo želite vstaviti vrednosti,

769
00:58:55,830 --> 00:58:59,040
in zdaj bom spet uporabite trikomponentnih, ampak kaj je naš pogoj, da bo?

770
00:58:59,040 --> 00:59:05,180
Kaj je iščeva odločiti, ali želimo iti v levo ali desno?

771
00:59:05,180 --> 00:59:07,760
Storimo to v posameznih korakih.

772
00:59:07,760 --> 00:59:18,850
Če je (vrednost <) kaj?

773
00:59:18,850 --> 00:59:23,200
[Študent] The Tree je vrednost?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Torej, ne pozabite, da sem trenutno -

775
00:59:27,490 --> 00:59:31,260
[Študenti, nerazumljivi]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Ja, tukaj, recimo, da je to zelena puščica

777
00:59:34,140 --> 00:59:39,050
je primer tega, kar drevo je trenutno, je kazalec na ta kazalec.

778
00:59:39,050 --> 00:59:46,610
Torej to pomeni, da sem kazalec na kazalec na 3.

779
00:59:46,610 --> 00:59:48,800
The dereference dvakrat zvenel dobro.

780
00:59:48,800 --> 00:59:51,010
Kaj mi je - kako naj to naredim?

781
00:59:51,010 --> 00:59:53,210
[Študent] dereference enkrat, in naredite puščica na tak način?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Torej (* drevo) je dereference enkrat -> vrednost

783
00:59:58,420 --> 01:00:05,960
se dogaja, da mi vrednost vozlišča, da sem posredno kaže.

784
01:00:05,960 --> 01:00:11,980
Tako lahko tudi jaz napisati ** tree.value če vam je ljubše, da.

785
01:00:11,980 --> 01:00:18,490
Ali deluje.

786
01:00:18,490 --> 01:00:26,190
Če je tako, potem vas vabim, da vstavite z vrednostjo.

787
01:00:26,190 --> 01:00:32,590
In kaj je moja posodobitev vozlišče ** bo?

788
01:00:32,590 --> 01:00:39,440
Rad bi šel na levo, tako ** tree.left se bo moja leva.

789
01:00:39,440 --> 01:00:41,900
In hočem kazalec na te stvari

790
01:00:41,900 --> 01:00:44,930
tako da če levi konča pa null kazalec,

791
01:00:44,930 --> 01:00:48,360
Lahko ga spremenite, da kaže na mojo novo vozlišče.

792
01:00:48,360 --> 01:00:51,460
>> In druga zadeva je zelo podobna.

793
01:00:51,460 --> 01:00:55,600
Naj dejansko narediti, da mi ternarni zdaj.

794
01:00:55,600 --> 01:01:04,480
Vstavljanje vrednosti, če vrednost <(** drevo). Vrednost.

795
01:01:04,480 --> 01:01:11,040
Potem želimo posodobiti naše ** na levo,

796
01:01:11,040 --> 01:01:17,030
pa želimo posodobiti naše ** desno.

797
01:01:17,030 --> 01:01:22,540
[Študent] Ali da se kazalec na kazalec?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Ne pozabite, da - ** tree.right je vozlišče zvezda.

799
01:01:30,940 --> 01:01:35,040
[Študent, nerazumljiv] >> Ja.

800
01:01:35,040 --> 01:01:41,140
** Tree.right je všeč ta kazalec ali kaj podobnega.

801
01:01:41,140 --> 01:01:45,140
Torej tako, da kazalec v tem, da daje vse, kar hočem

802
01:01:45,140 --> 01:01:50,090
od kazalca do tega tipa.

803
01:01:50,090 --> 01:01:54,260
[Študent] Lahko gremo znova Zato smo z uporabo dveh kazalcev?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Ja. Torej - ne, lahko, in da je rešitev pred

805
01:01:58,220 --> 01:02:04,540
je način za to početje ne delam 2 kazalca.

806
01:02:04,540 --> 01:02:08,740
Morate biti sposobni razumeti na dva kazalca,

807
01:02:08,740 --> 01:02:11,660
in to je čistejša rešitev.

808
01:02:11,660 --> 01:02:16,090
Prav tako opazili, da se, kaj se zgodi, če drevo -

809
01:02:16,090 --> 01:02:24,480
Kaj se zgodi, če je bil koren null? Kaj se zgodi, če naredim to zadevo tukaj?

810
01:02:24,480 --> 01:02:30,540
Torej vozlišče * koren = NULL, vstavite v 4 in korenine.

811
01:02:30,540 --> 01:02:35,110
Kaj je koren bo po tem?

812
01:02:35,110 --> 01:02:37,470
[Študent, nerazumljiv] >> Ja.

813
01:02:37,470 --> 01:02:41,710
Root vrednost se bo 4.

814
01:02:41,710 --> 01:02:45,510
Root levi se bo nič, koren pravica bo nič.

815
01:02:45,510 --> 01:02:49,490
V primeru, da ni opravil korenine po naslovu,

816
01:02:49,490 --> 01:02:52,490
ne moremo spremeniti root.

817
01:02:52,490 --> 01:02:56,020
V primeru, ko je drevo - če je korenina je bila nič,

818
01:02:56,020 --> 01:02:58,410
smo imeli, da vrne false. Ničesar nismo mogli storiti.

819
01:02:58,410 --> 01:03:01,520
Ne moremo vstaviti vozlišče v prazno drevo.

820
01:03:01,520 --> 01:03:06,810
Ampak zdaj smo lahko, smo le, da prazno drevo v eno vozlišče drevesa.

821
01:03:06,810 --> 01:03:13,400
Ki je običajno pričakovano smer, da naj bi vse delovalo.

822
01:03:13,400 --> 01:03:21,610
>> Poleg tega je to bistveno krajši kot

823
01:03:21,610 --> 01:03:26,240
Prav tako sledenja staršev, zato si izbirate navzdol vse do konca.

824
01:03:26,240 --> 01:03:30,140
Zdaj imam starša, jaz pa imam samo kazalec matično pravica do česarkoli že.

825
01:03:30,140 --> 01:03:35,640
Namesto tega, če bomo to naredili iterativno, bi bilo isto idejo z while zanko.

826
01:03:35,640 --> 01:03:38,100
Toda namesto da se ukvarjajo s svojo matično kazalcem

827
01:03:38,100 --> 01:03:40,600
namesto da bi moj trenutni kazalec je stvar

828
01:03:40,600 --> 01:03:43,790
da sem neposredno spreminja točko svojega novega vozlišča.

829
01:03:43,790 --> 01:03:46,090
Nimam obravnavati, ali je to kaže na levo.

830
01:03:46,090 --> 01:03:48,810
Nimam obravnavati, ali je to kaže v desno.

831
01:03:48,810 --> 01:04:00,860
To je samo ne glede na to kazalec, da bom jo nastavite na točko svojega novega vozlišča.

832
01:04:00,860 --> 01:04:05,740
Vsi razumemo, kako deluje?

833
01:04:05,740 --> 01:04:09,460
Če ne, zakaj ne želimo storiti na ta način,

834
01:04:09,460 --> 01:04:14,920
ampak vsaj to, da ta deluje kot rešitev?

835
01:04:14,920 --> 01:04:17,110
[Študent] Kam bomo vrnili res?

836
01:04:17,110 --> 01:04:21,550
[Bowden] To je verjetno tukaj.

837
01:04:21,550 --> 01:04:26,690
Če smo pravilno vstavite, return true.

838
01:04:26,690 --> 01:04:32,010
Else, tukaj bomo želeli vrniti ne glede vstavite donose.

839
01:04:32,010 --> 01:04:35,950
>> In kaj je posebnega na tem rekurzivna funkcija?

840
01:04:35,950 --> 01:04:43,010
To je rekurzivna rep, tako dolgo, dokler bomo pripraviti z nekaj optimizacije,

841
01:04:43,010 --> 01:04:48,060
bo prepoznajo, da ne boste nikoli dobili Stack overflow od tega,

842
01:04:48,060 --> 01:04:53,230
tudi če je naš Drevo ima višino 10.000 oziroma 10 milijonov evrov.

843
01:04:53,230 --> 01:04:55,630
[Študent, nerazumljiv]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Mislim, da to počne na Dash - ali kaj optimizacija ravni

845
01:05:00,310 --> 01:05:03,820
je potrebna za rep rekurzija, da se prizna.

846
01:05:03,820 --> 01:05:09,350
Mislim, da priznava - GCC in Jek

847
01:05:09,350 --> 01:05:12,610
Prav tako imajo različne pomene za njihove optimizacije ravni.

848
01:05:12,610 --> 01:05:17,870
Hočem reči, da je DashO 2, za prepričani, da bo to priznanje rep rekurzijo.

849
01:05:17,870 --> 01:05:27,880
Ampak - da bi lahko gradnjo kot na primer Fibonocci ali kaj podobnega.

850
01:05:27,880 --> 01:05:30,030
To ni enostavno preveriti s tem, ker je težko oblikovati

851
01:05:30,030 --> 01:05:32,600
binarno drevo, ki je tako velik.

852
01:05:32,600 --> 01:05:37,140
Ampak ja, mislim, da je DashO 2, ki

853
01:05:37,140 --> 01:05:40,580
če zbere z DashO 2, bo videti, za rekurzije repa

854
01:05:40,580 --> 01:05:54,030
in optimizirati, da ven.

855
01:05:54,030 --> 01:05:58,190
Pojdimo nazaj - vstaviti dobesedno zadnja stvar, ki jo potrebuje.

856
01:05:58,190 --> 01:06:04,900
Pojdimo nazaj k vložkom tukaj

857
01:06:04,900 --> 01:06:07,840
če bomo to isto idejo.

858
01:06:07,840 --> 01:06:14,340
To bo še vedno pomanjkljivost, saj ne more v celoti obravnavati

859
01:06:14,340 --> 01:06:17,940
ko je korenina sam nič, ali pa v preteklosti vnos je nična,

860
01:06:17,940 --> 01:06:20,060
toda namesto da se ukvarjajo z matično kazalcem

861
01:06:20,060 --> 01:06:27,430
dajmo uporabiti isto logiko vodenja napotke za kazalcev.

862
01:06:27,430 --> 01:06:35,580
Če tu vodijo naše vozlišče ** tren,

863
01:06:35,580 --> 01:06:37,860
in mi ni treba slediti desno več,

864
01:06:37,860 --> 01:06:47,190
vendar vozlišče ** tren = & drevo.

865
01:06:47,190 --> 01:06:54,800
In zdaj naša, medtem ko zanka se bo pa * tren ni enaka null.

866
01:06:54,800 --> 01:07:00,270
Ni treba slediti staršem več.

867
01:07:00,270 --> 01:07:04,180
Ali ni treba slediti levo in desno.

868
01:07:04,180 --> 01:07:10,190
In jaz bom to imenujemo temperatura, saj smo že uporabljate temp.

869
01:07:10,190 --> 01:07:17,200
Ok. Torej, če (vrednost> * temp),

870
01:07:17,200 --> 01:07:24,010
Nato & (* temp) -> desni

871
01:07:24,010 --> 01:07:29,250
še temp = & (* temp) -> levo.

872
01:07:29,250 --> 01:07:32,730
In zdaj, v tem trenutku, po tem while zanko,

873
01:07:32,730 --> 01:07:36,380
Jaz samo to morda zato, ker je lažje razmišljati o iterativno kot rekurzivno,

874
01:07:36,380 --> 01:07:39,010
ampak po tem, medtem ko zanke,

875
01:07:39,010 --> 01:07:43,820
* Temp je kazalec želimo spremeniti.

876
01:07:43,820 --> 01:07:48,960
>> Preden smo imeli od staršev, in mi je želel spremeniti niti matično levo ali desno starša,

877
01:07:48,960 --> 01:07:51,310
ampak, če želimo spremeniti matično pravico,

878
01:07:51,310 --> 01:07:54,550
potem * temp je nadrejena prav, in ga lahko spremenite neposredno.

879
01:07:54,550 --> 01:08:05,860
Torej tu spodaj, lahko naredimo * temp = newnode, in to je to.

880
01:08:05,860 --> 01:08:09,540
Torej, z odpovednim rokom, vsi smo v tem je vzeti vrstic kode.

881
01:08:09,540 --> 01:08:14,770
Da bi spremljali od staršev, v vsem, kar je dodaten napor.

882
01:08:14,770 --> 01:08:18,689
Tukaj, če bomo spremljali kazalec na kazalec,

883
01:08:18,689 --> 01:08:22,990
in tudi če bi želeli, da se znebite vseh teh zavitih oklepajih zdaj,

884
01:08:22,990 --> 01:08:27,170
bi bilo videti krajši.

885
01:08:27,170 --> 01:08:32,529
To je zdaj popolnoma enaka rešitev,

886
01:08:32,529 --> 01:08:38,210
vendar manj vrstic kode.

887
01:08:38,210 --> 01:08:41,229
Ko začnete priznava, da je to dobra rešitev,

888
01:08:41,229 --> 01:08:43,529
je tudi lažje razloga približno kot tako, v redu,

889
01:08:43,529 --> 01:08:45,779
zakaj moram to zastavo na desni int?

890
01:08:45,779 --> 01:08:49,290
Kaj to pomeni? Oh, to je pomenil, da

891
01:08:49,290 --> 01:08:51,370
vsakič, ko sem šel v redu, moram jo nastavite,

892
01:08:51,370 --> 01:08:53,819
pa če grem levo Moram jo nastavite na ničlo.

893
01:08:53,819 --> 01:09:04,060
Tukaj mi ni treba razlog za to, da je samo lažje razmišljati.

894
01:09:04,060 --> 01:09:06,710
Vprašanja?

895
01:09:06,710 --> 01:09:16,290
[Študent, nerazumljiv] >> Ja.

896
01:09:16,290 --> 01:09:23,359
Ok, tako da v zadnjem bit -

897
01:09:23,359 --> 01:09:28,080
Najbrž še ena hitra in enostavna naloga, kar lahko storimo, je,

898
01:09:28,080 --> 01:09:34,910
let's - skupaj, mislim, poskusite pisati vsebuje funkcijo

899
01:09:34,910 --> 01:09:38,899
ki ne skrbi, ali je dvojiško iskalno drevo.

900
01:09:38,899 --> 01:09:43,770
Ta vsebuje funkcijo je treba vrniti res

901
01:09:43,770 --> 01:09:58,330
Če kje v tem splošnem drevo binarno je vrednota, ki jo iščete.

902
01:09:58,330 --> 01:10:02,520
Torej najprej narediti rekurzivno in potem bomo to iterativno.

903
01:10:02,520 --> 01:10:07,300
Mi lahko dejansko samo to delamo skupaj, ker to bo res kratka.

904
01:10:07,300 --> 01:10:11,510
>> Kaj je moja osnovna bo treba?

905
01:10:11,510 --> 01:10:13,890
[Študent, nerazumljiv]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Torej, če (drevo == NULL), kaj pa potem?

907
01:10:18,230 --> 01:10:22,740
[Študent] vrne false.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Drugače, no, jaz ne potrebujem drugega.

909
01:10:26,160 --> 01:10:30,250
Če je bila moja druga osnovna.

910
01:10:30,250 --> 01:10:32,450
[Študentskih] Drevesni je vrednost? >> Ja.

911
01:10:32,450 --> 01:10:36,430
Torej, če (drevo-> vrednost == vrednost.

912
01:10:36,430 --> 01:10:39,920
Obvestilo smo spet na * vozlišče, vozlišče ni ** i?

913
01:10:39,920 --> 01:10:42,990
Vsebuje nikoli ne bo treba uporabiti vozlišče **

914
01:10:42,990 --> 01:10:45,480
saj se ne spreminja kazalca.

915
01:10:45,480 --> 01:10:50,540
Mi smo jih le prečkajo.

916
01:10:50,540 --> 01:10:53,830
Če se to zgodi, potem smo res želeli vrniti.

917
01:10:53,830 --> 01:10:58,270
Sicer želimo prečkati otroke.

918
01:10:58,270 --> 01:11:02,620
Torej ne moremo argumentira o tem, ali je vse v levo manj

919
01:11:02,620 --> 01:11:05,390
in vse na desni je večja.

920
01:11:05,390 --> 01:11:09,590
Torej, kaj je naš pogoj, da bo tukaj - ali, kaj bomo storili?

921
01:11:09,590 --> 01:11:11,840
[Študent, nerazumljiv] >> Ja.

922
01:11:11,840 --> 01:11:17,400
Nazaj vsebuje (vrednost, drevo-> levo)

923
01:11:17,400 --> 01:11:26,860
ali vsebuje (vrednost, drevo-> desno). In to je to.

924
01:11:26,860 --> 01:11:29,080
In opazil, da je nekaj kratkega stika vrednotenje,

925
01:11:29,080 --> 01:11:32,520
kjer, če se zgodi, da bi našli vrednost v levem drevesu

926
01:11:32,520 --> 01:11:36,820
mi nikoli ni treba gledati na pravo drevo.

927
01:11:36,820 --> 01:11:40,430
To je celotno funkcijo.

928
01:11:40,430 --> 01:11:43,690
Zdaj pa to iterativno,

929
01:11:43,690 --> 01:11:48,060
, ki se bo manj prijetno.

930
01:11:48,060 --> 01:11:54,750
Mi bomo običajno začetek vozlišča * cur = dreves.

931
01:11:54,750 --> 01:12:03,250
Medtem ko je (tren! = NULL).

932
01:12:03,250 --> 01:12:08,600
Hitro bomo videli problem.

933
01:12:08,600 --> 01:12:12,250
Če tren - tukaj, če bomo kdaj izbruhne tega,

934
01:12:12,250 --> 01:12:16,020
Nato smo zmanjkalo stvari pogledati, tako vrne false.

935
01:12:16,020 --> 01:12:24,810
Če (tren-> vrednost == vrednost) return true.

936
01:12:24,810 --> 01:12:32,910
Torej, zdaj smo na mestu -

937
01:12:32,910 --> 01:12:36,250
Ne vemo, ali želimo iti v levo ali desno.

938
01:12:36,250 --> 01:12:44,590
Torej samovoljno, pojdiva levo.

939
01:12:44,590 --> 01:12:47,910
Očitno sem naletel na težavo, zaradi katere sem popolnoma opustila vse -

940
01:12:47,910 --> 01:12:50,760
Bom samo še preveriti na levi strani drevesa.

941
01:12:50,760 --> 01:12:56,050
Nikoli ne bo preveril vse, kar je pravica otroka ničesar.

942
01:12:56,050 --> 01:13:00,910
Kako to popraviti?

943
01:13:00,910 --> 01:13:05,260
[Študent], moraš slediti v levo in desno na kupu.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Ja. Torej bi bilo

945
01:13:13,710 --> 01:13:32,360
struct seznam vozlišče * n, potem vozlišče ** naslednji?

946
01:13:32,360 --> 01:13:40,240
Mislim, da deluje v redu.

947
01:13:40,240 --> 01:13:45,940
Želimo, da gredo čez levo ali let's - tu gor.

948
01:13:45,940 --> 01:13:54,350
Struct = SEZNAM seznam, se bo začela

949
01:13:54,350 --> 01:13:58,170
se na tej struct seznam.

950
01:13:58,170 --> 01:14:04,040
* Seznam = NULL. Tako, da se bo naša povezani seznam

951
01:14:04,040 --> 01:14:08,430
od subtrees da smo preskočijo.

952
01:14:08,430 --> 01:14:13,800
Mi se bomo za prečkanje zdaj levo,

953
01:14:13,800 --> 01:14:17,870
ampak ker smo nujno potrebovali, da pridejo nazaj na desno,

954
01:14:17,870 --> 01:14:26,140
Gremo naprej na desni strani znotraj našega seznama struct.

955
01:14:26,140 --> 01:14:32,620
Potem bomo imeli new_list ali struct,

956
01:14:32,620 --> 01:14:41,080
struct seznam * new_list = malloc (sizeof (seznam)).

957
01:14:41,080 --> 01:14:44,920
Jaz bom prezreti napake kontrole, ampak bi morali preveriti, da vidim, če je nično.

958
01:14:44,920 --> 01:14:50,540
New_list vozlišče, da se dogaja, da kaže -

959
01:14:50,540 --> 01:14:56,890
oh, zato sem ga želel tukaj. To bo pomenilo, da se drugi seznam struct.

960
01:14:56,890 --> 01:15:02,380
To je samo, kako povezani seznami delo.

961
01:15:02,380 --> 01:15:04,810
To je isto kot int povezan seznam

962
01:15:04,810 --> 01:15:06,960
razen da smo samo zamenjava z int * vozlišča.

963
01:15:06,960 --> 01:15:11,040
To je popolnoma enako.

964
01:15:11,040 --> 01:15:15,100
Torej new_list, vrednost našega new_list vozlišče,

965
01:15:15,100 --> 01:15:19,120
se bo tre-> desno.

966
01:15:19,120 --> 01:15:24,280
Vrednost naše new_list-> next se bo naš prvotni seznam,

967
01:15:24,280 --> 01:15:30,760
in potem bomo posodobiti naš seznam izpostaviti new_list.

968
01:15:30,760 --> 01:15:33,650
>> Zdaj moramo nekakšen način vlečejo stvari,

969
01:15:33,650 --> 01:15:37,020
kot smo prehodil celotno levo poddrevo.

970
01:15:37,020 --> 01:15:40,480
Zdaj moramo vleči stvari iz njega,

971
01:15:40,480 --> 01:15:43,850
kot tren je nična, ne želimo, da samo vrne false.

972
01:15:43,850 --> 01:15:50,370
Želimo, da se zdaj vleči zunaj na naši novi seznam.

973
01:15:50,370 --> 01:15:53,690
Priročen način za to - no, pravzaprav, obstaja več načinov za to.

974
01:15:53,690 --> 01:15:56,680
Vsakdo ima predlog?

975
01:15:56,680 --> 01:15:58,790
Kje je treba to storiti in kako bi moral to storiti?

976
01:15:58,790 --> 01:16:08,010
Imamo le nekaj minut, a kakšen predlog?

977
01:16:08,010 --> 01:16:14,750
Namesto - en način, namesto naših razmerah pa medtem,

978
01:16:14,750 --> 01:16:17,090
kaj smo trenutno iščejo ni nič,

979
01:16:17,090 --> 01:16:22,340
namesto tega se bomo še naprej, dokler gre naš seznam sam je nična.

980
01:16:22,340 --> 01:16:25,680
Torej, če je naš seznam konča pa nič,

981
01:16:25,680 --> 01:16:30,680
potem smo zmanjkalo stvari za iskanje, da poiščete več.

982
01:16:30,680 --> 01:16:39,860
Toda to pomeni, da je prva stvar v našem seznamu je le, da bo treba najprej vozlišče.

983
01:16:39,860 --> 01:16:49,730
Prva stvar, ki bo - mi ni več treba videti.

984
01:16:49,730 --> 01:16:58,710
Torej, seznam-> bo n je naša drevo.

985
01:16:58,710 --> 01:17:02,860
seznam-> next se bo nič.

986
01:17:02,860 --> 01:17:07,580
In zdaj, ko seznam ni enaka null.

987
01:17:07,580 --> 01:17:11,610
OR bo potegniti nekaj iz našega seznama.

988
01:17:11,610 --> 01:17:13,500
Torej tren bo enako Seznam-> n.

989
01:17:13,500 --> 01:17:20,850
In potem se bo seznam enakega Seznam-> n, ali seznam-> naslednji.

990
01:17:20,850 --> 01:17:23,480
Torej, če tren vrednost je enaka vrednosti.

991
01:17:23,480 --> 01:17:28,790
Sedaj lahko dodate tako naši desni kazalec in našo levi kazalec

992
01:17:28,790 --> 01:17:32,900
dokler nisi nič.

993
01:17:32,900 --> 01:17:36,390
Tukaj, mislim, da bi morali storiti, da na prvem mestu.

994
01:17:36,390 --> 01:17:44,080
Če (tren-> desno! = NULL)

995
01:17:44,080 --> 01:17:56,380
Nato se bomo, da vstavite to vozlišče v našem seznamu.

996
01:17:56,380 --> 01:17:59,290
Če (tren-> levo), to je malo dodatnega dela, ampak to je v redu.

997
01:17:59,290 --> 01:18:02,690
Če (tren-> levi! = NULL)

998
01:18:02,690 --> 01:18:14,310
in bomo vstavili v levo v našo povezani seznam,

999
01:18:14,310 --> 01:18:19,700
in to bi moralo biti to.

1000
01:18:19,700 --> 01:18:22,670
Mi Ponovil - dokler imamo nekaj v našem seznamu

1001
01:18:22,670 --> 01:18:26,640
imamo še eno vozlišče na pogled.

1002
01:18:26,640 --> 01:18:28,920
Torej, gledamo na to vozlišče,

1003
01:18:28,920 --> 01:18:31,390
pospešimo naš seznam na naslednjega.

1004
01:18:31,390 --> 01:18:34,060
Če je vozlišče je vrednota, ki jo iščeš, se lahko vrnemo res.

1005
01:18:34,060 --> 01:18:37,640
Sicer vstaviti tako naši levi in ​​desni subtrees,

1006
01:18:37,640 --> 01:18:40,510
dokler si ni nič, v našem seznamu

1007
01:18:40,510 --> 01:18:43,120
tako da bomo neizogibno nad njimi.

1008
01:18:43,120 --> 01:18:45,160
Torej, če ne bi bili nič,

1009
01:18:45,160 --> 01:18:47,950
Če naša root kazalec poudaril dve stvari,

1010
01:18:47,950 --> 01:18:51,670
potem pa smo najprej potegnil nekaj ven, da naš seznam konča pa nič.

1011
01:18:51,670 --> 01:18:56,890
In potem smo se dve stvari nazaj, tako da zdaj naš seznam z velikostjo 2.

1012
01:18:56,890 --> 01:19:00,030
Potem bomo zanko nazaj in mi greš samo za vleko,

1013
01:19:00,030 --> 01:19:04,250
recimo, levi kazalec naše korenine vozlišče.

1014
01:19:04,250 --> 01:19:07,730
In ti, ki kar naprej dogaja, da bomo na koncu zanka nad vsem.

1015
01:19:07,730 --> 01:19:11,280
>> Vedite, da je to precej bolj zapleteno

1016
01:19:11,280 --> 01:19:14,160
v rekurzivni rešitvi.

1017
01:19:14,160 --> 01:19:17,260
In sem rekel večkrat

1018
01:19:17,260 --> 01:19:25,120
da je rekurzivna rešitev ponavadi nima veliko skupnega z iterativno rešitev.

1019
01:19:25,120 --> 01:19:30,820
Tu to je točno tisto, kar rekurzivna rešitev počne.

1020
01:19:30,820 --> 01:19:36,740
Edina sprememba je, da namesto implicitno uporabi sklad, program za sklad,

1021
01:19:36,740 --> 01:19:40,840
kot vaš način sledenja, kar vozlišča še vedno je treba obiskati,

1022
01:19:40,840 --> 01:19:45,430
Zdaj boste morali uporabiti izrecno povezan seznam.

1023
01:19:45,430 --> 01:19:49,070
V obeh primerih boste sledenja kaj vozlišče je treba še obiskal.

1024
01:19:49,070 --> 01:19:51,790
V primeru, rekurzivni je samo lažje, ker sklad

1025
01:19:51,790 --> 01:19:57,100
se izvaja za vas programa dimnika.

1026
01:19:57,100 --> 01:19:59,550
Obvestilo, da je to povezano s seznama, je kup.

1027
01:19:59,550 --> 01:20:01,580
Karkoli smo pravkar dal na kupu

1028
01:20:01,580 --> 01:20:09,960
takoj, kaj bomo odstranite sveženj za obisk drugega.

1029
01:20:09,960 --> 01:20:14,380
Zmanjkuje nam časa, ampak kakšno vprašanje?

1030
01:20:14,380 --> 01:20:23,530
[Študent, nerazumljiv]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Ja. Torej, če imamo povezan seznam,

1032
01:20:27,790 --> 01:20:30,150
Sedanja se bo izpostaviti s tem moškim,

1033
01:20:30,150 --> 01:20:34,690
in zdaj smo šele pospeševanja našega povezan seznam, da se osredotoči na tega tipa.

1034
01:20:34,690 --> 01:20:44,200
Mi smo vozili v povezanem seznamu v tej vrstici.

1035
01:20:44,200 --> 01:20:51,200
In potem mislim, da bi morali osvoboditi našo povezan seznam in stvari

1036
01:20:51,200 --> 01:20:53,880
enkrat pred vrnitvijo v resničen ali neresničen, moramo

1037
01:20:53,880 --> 01:20:57,360
Ponovil nad našim povezan seznam in vedno tukaj, mislim,

1038
01:20:57,360 --> 01:21:03,900
če tren pravica ni enak, ga dodajte, zdaj želimo osvoboditi

1039
01:21:03,900 --> 01:21:09,600
tren ker, no, pa smo povsem pozabili na seznamu? Ja.

1040
01:21:09,600 --> 01:21:12,880
Torej, to je tisto, kar želimo na tem mestu.

1041
01:21:12,880 --> 01:21:16,730
Kje je kazalec?

1042
01:21:16,730 --> 01:21:23,320
OR je bil takrat - želimo, da seznam struct * 10 enak seznam naslednjo.

1043
01:21:23,320 --> 01:21:29,240
Brezplačna seznam, seznam = temp.

1044
01:21:29,240 --> 01:21:32,820
In v primeru, ko se vrnete smo res, pa je treba, da izbirate

1045
01:21:32,820 --> 01:21:37,050
v preostalem našem povezanem seznamu ostane več stvari.

1046
01:21:37,050 --> 01:21:39,700
Za lepo stvar o rekurzivnega rešitev je sprostitev stvari

1047
01:21:39,700 --> 01:21:44,930
samo pomeni, živahen factorings off sklad, ki se bo zgodilo za vas.

1048
01:21:44,930 --> 01:21:50,720
Tako smo šli iz nečesa, kar je podobno 3 vrstic težko razmišljati o zakoniku-

1049
01:21:50,720 --> 01:21:57,520
nekaj, kar je pomembno še veliko več jih je težko razmišljati o tem, vrstic kode.

1050
01:21:57,520 --> 01:22:00,620
Vse več vprašanj?

1051
01:22:00,620 --> 01:22:08,760
V redu. Mi smo dobro. Adijo!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]