1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Oddelek 7] [manj udoben]

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

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

4
00:00:07,000 --> 00:00:09,080
>> Dobrodošli v oddelku 7.

5
00:00:09,080 --> 00:00:11,330
Zaradi orkana Sandy,

6
00:00:11,330 --> 00:00:13,440
namesto da bi normalno del ta teden,

7
00:00:13,440 --> 00:00:17,650
to počnemo sprehod skozi, skozi del vprašanj.

8
00:00:17,650 --> 00:00:22,830
Bom lahko po skupaj z Težava Set 6 specifikacije,

9
00:00:22,830 --> 00:00:25,650
in gre skozi vsa vprašanja v

10
00:00:25,650 --> 00:00:27,770
Oddelek oddelka vprašanja.

11
00:00:27,770 --> 00:00:30,940
Če obstajajo vprašanja,

12
00:00:30,940 --> 00:00:32,960
prosim objavite to na CS50 razpravljali.

13
00:00:32,960 --> 00:00:35,480
>> V redu. Pa začnimo.

14
00:00:35,480 --> 00:00:40,780
Zdaj sem si na strani 3 specifikaciji Problem Set.

15
00:00:40,780 --> 00:00:44,110
Bomo najprej začeli govoriti o binarnih dreves

16
00:00:44,110 --> 00:00:47,850
saj so imeli veliko težav pomembna za ta teden set -

17
00:00:47,850 --> 00:00:49,950
Drevo Huffman kodiranja.

18
00:00:49,950 --> 00:00:55,000
Ena od prvih podatkovne strukture smo govorili o CS50 je matrika.

19
00:00:55,000 --> 00:01:00,170
Ne pozabite, da je matrika zaporedje elementov -

20
00:01:00,170 --> 00:01:04,019
vse iste vrste - hranijo v neposredni bližini drug drugega v spominu.

21
00:01:04,019 --> 00:01:14,420
Če imam celoštevilsko matriko, ki jo lahko pripravi z uporabo te škatle-številke-celi števili slog -

22
00:01:14,420 --> 00:01:20,290
Recimo, da imam 5 v prvo polje, imam 7 v drugi,

23
00:01:20,290 --> 00:01:27,760
potem imam 8, 10 in 20 v zadnjem polju.

24
00:01:27,760 --> 00:01:33,000
Ne pozabite, da sta res dobre stvari o tem polju

25
00:01:33,000 --> 00:01:38,800
so, da imamo to konstantno času dostop do vseh posameznega elementa

26
00:01:38,800 --> 00:01:40,500
 v polju, če vemo, njen indeks.

27
00:01:40,500 --> 00:01:44,670
Na primer, če želim, da zgrabite tretji element v matriki -

28
00:01:44,670 --> 00:01:47,870
V indeksu 2 uporabo našega ničelnega indeksiranje sistem -

29
00:01:47,870 --> 00:01:52,220
Dobesedno sem samo narediti preprost matematični izračun,

30
00:01:52,220 --> 00:01:56,170
hop na ta položaj v matriki,

31
00:01:56,170 --> 00:01:57,840
izvlecite 8, ki je shranjena,

32
00:01:57,840 --> 00:01:59,260
in sem na dobri poti.

33
00:01:59,260 --> 00:02:03,350
>> Ena od slabih stvari o tem polju -, da smo se pogovarjali o

34
00:02:03,350 --> 00:02:05,010
ko smo razpravljali o povezanih seznamov -

35
00:02:05,010 --> 00:02:09,120
je, da če želim vstaviti element v tem polju,

36
00:02:09,120 --> 00:02:11,090
Jaz bom moral narediti nekaj premika naokoli.

37
00:02:11,090 --> 00:02:12,940
Na primer, ta niz tukaj

38
00:02:12,940 --> 00:02:16,850
v urejenih redu - razvrščene v naraščajočem vrstnem redu -

39
00:02:16,850 --> 00:02:19,440
5, nato pa 7, potem 8, nato 10 in nato 20 -

40
00:02:19,440 --> 00:02:23,100
ampak če želite vstaviti številko 9 v tem polju,

41
00:02:23,100 --> 00:02:27,460
Jaz bom moral premakniti nekaj elementov, da bi naredili prostor.

42
00:02:27,460 --> 00:02:30,440
Mi lahko izdela to tukaj.

43
00:02:30,440 --> 00:02:35,650
Jaz bom moral premakniti 5, 7, nato pa 8;

44
00:02:35,650 --> 00:02:38,720
ustvarjajo vrzel, kjer sem dal 9,

45
00:02:38,720 --> 00:02:45,910
in potem lahko 10 in 20 pojdi na desni strani 9.

46
00:02:45,910 --> 00:02:49,450
To je neke vrste bolečino, ker v najslabšem primeru -

47
00:02:49,450 --> 00:02:54,350
ko smo morali vstaviti bodisi na začetku ali na koncu

48
00:02:54,350 --> 00:02:56,040
na polje, odvisno od tega, kako bomo premika -

49
00:02:56,040 --> 00:02:58,850
lahko bi na koncu morali preusmeriti vse elemente

50
00:02:58,850 --> 00:03:00,750
da smo trenutno shranjevanje v array.

51
00:03:00,750 --> 00:03:03,810
>> Torej, kakšna je bila pot okoli tega?

52
00:03:03,810 --> 00:03:09,260
Pot okoli tega je bil, da gredo na našo povezanost seznam metode, kjer -

53
00:03:09,260 --> 00:03:19,820
Namesto shranjevanja elementov 5, 7, 8, 10 in 20 vsi zraven drugega, v spomin -

54
00:03:19,820 --> 00:03:25,630
kaj smo namesto tega pa je shranjevanje jim nekakšno kjer smo želeli, da jih shranite

55
00:03:25,630 --> 00:03:32,470
V tem povezan seznam-vozlišč, ki sem črpa tukaj vrste ad hoc.

56
00:03:32,470 --> 00:03:42,060
In potem smo jih med seboj povezane z uporabo teh naslednjih nasvetov.

57
00:03:42,060 --> 00:03:44,370
Lahko dobim kazalec od 5 do 7,

58
00:03:44,370 --> 00:03:46,420
kazalec od 7 do 8,

59
00:03:46,420 --> 00:03:47,770
kazalec od 8 do 10,

60
00:03:47,770 --> 00:03:51,220
in končno, kazalec od 10 do 20,

61
00:03:51,220 --> 00:03:54,880
in nato null kazalec na 20 kaže, da ni nič ostalo.

62
00:03:54,880 --> 00:03:59,690
Kompromis, ki ga imamo tukaj

63
00:03:59,690 --> 00:04:05,360
je, da zdaj, če želimo vstaviti številko 9 na našem seznamu razvrščeni,

64
00:04:05,360 --> 00:04:08,270
vse, kar moramo storiti, je ustvariti novo vozlišče z 9,

65
00:04:08,270 --> 00:04:12,290
ga priključite do opozarjajo na ustrezno mesto,

66
00:04:12,290 --> 00:04:20,630
in nato ponovno žica 8 s točko navzdol do 9.

67
00:04:20,630 --> 00:04:25,660
To je zelo hiter, ob predpostavki, da smo točno vedeli, kam hočemo vstaviti 9.

68
00:04:25,660 --> 00:04:32,610
Toda kompromis, v zameno za to, da smo danes izgubili stalno času dostop

69
00:04:32,610 --> 00:04:36,230
za vsako posamezno prvino v našo strukturo podatkov.

70
00:04:36,230 --> 00:04:40,950
Na primer, če želim, da bi našli četrti element v tem povezanega seznama,

71
00:04:40,950 --> 00:04:43,510
Bom moral začeti na samem začetku seznama

72
00:04:43,510 --> 00:04:48,930
in delo, svojo pot skozi vozlišča štetje-by-vozlišča, dokler ne najdem četrti.

73
00:04:48,930 --> 00:04:55,870
>> Da bi dobili boljši dostop do zmogljivosti kot povezan seznam -

74
00:04:55,870 --> 00:04:59,360
ampak tudi ohraniti nekatere prednosti, ki smo jih imeli

75
00:04:59,360 --> 00:05:01,800
v zvezi z delovnim časom vstavitve iz povezanega seznama -

76
00:05:01,800 --> 00:05:05,750
binarno drevo bo treba uporabiti malo več pomnilnika.

77
00:05:05,750 --> 00:05:11,460
Še posebej, namesto da bi samo z eno kazalec v binarnem vozlišču drevesa -

78
00:05:11,460 --> 00:05:13,350
kot povezan seznam-vozlišče ne -

79
00:05:13,350 --> 00:05:16,950
bomo dodali še en kazalec na vozlišče binarno drevo.

80
00:05:16,950 --> 00:05:19,950
Namesto, da samo z eno kazalec na naslednji element,

81
00:05:19,950 --> 00:05:24,420
bomo imeli kazalec na levi in ​​desni otroka otroka.

82
00:05:24,420 --> 00:05:26,560
>> Naj narisati sliko, da vidite, kako dejansko izgleda.

83
00:05:26,560 --> 00:05:31,350
Spet bom uporabila te škatle in puščice.

84
00:05:31,350 --> 00:05:37,150
Binarno drevo vozlišče bo začnete s preprostim polje.

85
00:05:37,150 --> 00:05:40,940
To se dogaja, da imajo prostor za vrednost,

86
00:05:40,940 --> 00:05:47,280
potem pa se tudi dogaja, da imajo prostor za levi in ​​desni otroka otroka.

87
00:05:47,280 --> 00:05:49,280
Grem, da jih tukaj.

88
00:05:49,280 --> 00:05:57,560
Bomo imeli levi otroka, nato pa se bomo, da imajo pravico otroka.

89
00:05:57,560 --> 00:05:59,920
Obstaja veliko različnih načinov za to.

90
00:05:59,920 --> 00:06:02,050
Včasih za prostor in udobje,

91
00:06:02,050 --> 00:06:06,460
Jaz bom dejansko sestavi, kot delam tukaj na dnu

92
00:06:06,460 --> 00:06:10,910
kam grem, da so vrednosti na vrhu,

93
00:06:10,910 --> 00:06:14,060
in nato desno otrok na spodnjem desnem kotu,

94
00:06:14,060 --> 00:06:16,060
in levo otrok v spodnjem levem.

95
00:06:16,060 --> 00:06:20,250
Če se vrnemo na tem vrhu diagrama,

96
00:06:20,250 --> 00:06:22,560
imamo vrednost na samem vrhu,

97
00:06:22,560 --> 00:06:25,560
potem imamo levi kazalec otrok, in potem imamo desno otrok kazalec.

98
00:06:25,560 --> 00:06:30,110
>> V opredelitvi težave Set,

99
00:06:30,110 --> 00:06:33,110
govorimo o oblikovanju vozlišče, ki ima vrednost 7,

100
00:06:33,110 --> 00:06:39,750
in potem levo otrok kazalec, da je nična in desno kazalec, da otrok je nična.

101
00:06:39,750 --> 00:06:46,040
Postanemo lahko napišete kapitala NULL v prostoru za

102
00:06:46,040 --> 00:06:51,610
tako levo otrok in pravico otrok, ali lahko pripravi to poševnico

103
00:06:51,610 --> 00:06:53,750
z vsako od polj, ki označuje, da je to nič.

104
00:06:53,750 --> 00:06:57,560
Jaz bom to storil samo zato, ker je to preprosto.

105
00:06:57,560 --> 00:07:03,700
To, kar vidite tukaj dva načina diagramov zelo preprost vozlišče binarno drevo

106
00:07:03,700 --> 00:07:07,960
kjer imamo vrednost 7 in ničelne kazalce otrok.

107
00:07:07,960 --> 00:07:15,220
>> Drugi del naših pogovorov specifikacij o tem, kako s povezanimi seznamov -

108
00:07:15,220 --> 00:07:18,270
Zapomnite si, da smo imeli samo, da imajo na zelo prvi element na seznamu

109
00:07:18,270 --> 00:07:20,270
zapomniti celoten seznam -

110
00:07:20,270 --> 00:07:26,140
in prav tako tudi z binarno drevo, imamo samo, da imajo na eni kazalec na drevo

111
00:07:26,140 --> 00:07:31,120
da bi ohranili nadzor nad celotno strukturo podatkov.

112
00:07:31,120 --> 00:07:36,150
Ta poseben element drevesa se imenuje vozlišče koren tega drevesa.

113
00:07:36,150 --> 00:07:43,360
Na primer, če je to eno vozlišče - to vozlišče, ki vsebuje vrednost 7

114
00:07:43,360 --> 00:07:45,500
s null levo in desno otrok kazalci -

115
00:07:45,500 --> 00:07:47,360
so bili edina vrednost v našem drevesu

116
00:07:47,360 --> 00:07:50,390
potem bi bila to naša root vozlišča.

117
00:07:50,390 --> 00:07:52,240
To je zelo začetek našega drevesa.

118
00:07:52,240 --> 00:07:58,530
To lahko vidimo malo bolj jasno, ko bomo začeli dodajanjem več vozlišč za naše drevo.

119
00:07:58,530 --> 00:08:01,510
Naj dvigni novo stran.

120
00:08:01,510 --> 00:08:05,000
>> Sedaj bomo narisali drevo, ki ima 7 v korenu,

121
00:08:05,000 --> 00:08:10,920
in 3 znotraj levega otroka in 9 v notranjosti pravo otroka.

122
00:08:10,920 --> 00:08:13,500
Tudi to je zelo preprosta.

123
00:08:13,500 --> 00:08:26,510
Imamo 7, pripravi vozlišče za 3, vozlišča za 9,

124
00:08:26,510 --> 00:08:32,150
in bom nastaviti levi kazalec otrok od 7 do točke na vozlišče, ki vsebuje 3,

125
00:08:32,150 --> 00:08:37,850
in pravico otroka kazalec na vozlišče, ki vsebuje 7 do vozlišča, ki vsebuje 9.

126
00:08:37,850 --> 00:08:42,419
Zdaj, ker 3 in 9 nimata otrok,

127
00:08:42,419 --> 00:08:48,500
da bomo iz vseh svojih otrok napotke za nična.

128
00:08:48,500 --> 00:08:56,060
Tu so korenine naše drevo ustreza vozlišča, ki vsebuje številko 7.

129
00:08:56,060 --> 00:09:02,440
Vidite lahko, da če vse, kar imamo, je kazalec na koren tega vozlišča,

130
00:09:02,440 --> 00:09:07,330
potem lahko sprehodite skozi naše drevo in dostop do obeh otrok vozlišč -

131
00:09:07,330 --> 00:09:10,630
tako 3 in 9.

132
00:09:10,630 --> 00:09:14,820
Ni potrebe, da ohrani napotke za vsako vozlišče v drevesu.

133
00:09:14,820 --> 00:09:22,080
V redu. Sedaj bomo dodali še eno vozlišče, s tem načrtom.

134
00:09:22,080 --> 00:09:25,370
Bomo dodali vozlišče, ki vsebuje 6,

135
00:09:25,370 --> 00:09:34,140
in bomo dodali, da je to pravi otroka vozlišča, ki vsebuje 3.

136
00:09:34,140 --> 00:09:41,850
Če želite to narediti, da bom izbrisati to null kazalec v 3-vozlišče

137
00:09:41,850 --> 00:09:47,750
in ga priključite do točke na vozlišče, ki vsebuje 6. V redu.

138
00:09:47,750 --> 00:09:53,800
>> Na tej točki, gremo v malo terminologije.

139
00:09:53,800 --> 00:09:58,230
Če želite začeti, razlog, da se to imenuje binarno drevo, zlasti

140
00:09:58,230 --> 00:10:00,460
je, da ima dva otroka kazalca.

141
00:10:00,460 --> 00:10:06,020
Obstajajo tudi druge vrste dreves, ki imajo več kazalcev za otroke.

142
00:10:06,020 --> 00:10:10,930
Še posebej si poskusil "v Set Problem 5.

143
00:10:10,930 --> 00:10:19,310
Opazili boste, da v tem poskusu, ste imeli 27 različnih kazalcev za različne otroke -

144
00:10:19,310 --> 00:10:22,410
1 za vsako od 26 črk angleške abecede,

145
00:10:22,410 --> 00:10:25,410
in nato za 27. opuščaj -

146
00:10:25,410 --> 00:10:28,900
tako, da je podoben tip drevesa.

147
00:10:28,900 --> 00:10:34,070
Ampak tukaj, saj je binarno, imamo le dva otroka kazalca.

148
00:10:34,070 --> 00:10:37,880
>> Poleg tega korenskega vozlišča, ki smo govorili,

149
00:10:37,880 --> 00:10:41,470
smo prav tako metali okoli tega pojma "otrok".

150
00:10:41,470 --> 00:10:44,470
Kaj to pomeni za eno vozlišče, da je otrok drugo vozlišče?

151
00:10:44,470 --> 00:10:54,060
To dobesedno pomeni, da je otrok vozlišča je otrok drugo vozlišče

152
00:10:54,060 --> 00:10:58,760
če ta drugi vozlišče ima eno od svojih otrok kazalcev iz točke v tem vozlišču.

153
00:10:58,760 --> 00:11:01,230
Da bi se to v bolj konkretno,

154
00:11:01,230 --> 00:11:11,170
če je 3 opozoril eden od pokazateljev 7 otrok, nato pa 3 je otrok 7.

155
00:11:11,170 --> 00:11:14,510
Če bi ugotovili, kaj otroci so 7 -

156
00:11:14,510 --> 00:11:18,510
No, bomo videli, da ima 7 kazalec na 3 in kazalec do 9,

157
00:11:18,510 --> 00:11:22,190
Tako 9 in 3 otroci 7.

158
00:11:22,190 --> 00:11:26,650
Devet nima otrok, saj so njeni otroci kazalci null,

159
00:11:26,650 --> 00:11:30,940
in 3 ima samo enega otroka, 6.

160
00:11:30,940 --> 00:11:37,430
Šest tudi nima otrok, saj bosta obe kazalcev, so nična, kar bomo pripraviti prav zdaj.

161
00:11:37,430 --> 00:11:45,010
>> Poleg tega govorimo tudi o starših posebnem vozlišču,

162
00:11:45,010 --> 00:11:51,100
in to je, kot ste pričakovali, ravno nasprotno od tega otroka opisa.

163
00:11:51,100 --> 00:11:58,620
Vsako vozlišče ima samo eden od staršev - namesto dveh, kot bi lahko pričakovali pri ljudeh.

164
00:11:58,620 --> 00:12:03,390
Na primer, matično 3 je 7.

165
00:12:03,390 --> 00:12:10,800
Matično dne 9. je 7 in je nadrejena 6 je 3. Ni veliko za to.

166
00:12:10,800 --> 00:12:15,720
Imamo tudi pogoje za pogovor o starimi starši in vnuki,

167
00:12:15,720 --> 00:12:18,210
in bolj na splošno govorimo o prednikih

168
00:12:18,210 --> 00:12:20,960
in potomci v posebnem vozlišču.

169
00:12:20,960 --> 00:12:25,710
Prednik vozlišča - ali prednikov, temveč za vozlišča -

170
00:12:25,710 --> 00:12:32,730
so vsi vozlišč, ki ležijo na poti od korena do vozlišča.

171
00:12:32,730 --> 00:12:36,640
Na primer, če gledam vozlišče 6,

172
00:12:36,640 --> 00:12:46,430
potem predniki se bodo tako 3 in 7.

173
00:12:46,430 --> 00:12:55,310
Predniki 9, na primer, so - če gledam v vozlišču 9 -

174
00:12:55,310 --> 00:12:59,990
potem je prednik 9 je samo 7.

175
00:12:59,990 --> 00:13:01,940
In potomci so ravno obratno.

176
00:13:01,940 --> 00:13:05,430
Če želim, da pogled na vse potomce 7,

177
00:13:05,430 --> 00:13:11,020
potem moram gledati na vseh vozliščih pod njo.

178
00:13:11,020 --> 00:13:16,950
Torej, imam 3, 9, 6 in vse kot potomce 7.

179
00:13:16,950 --> 00:13:24,170
>> Končni rok, da se bova pogovarjala, je ta pojem pa brat.

180
00:13:24,170 --> 00:13:27,980
Bratje in sestre - vrsta skupaj na podlagi teh družinskih pogoji -

181
00:13:27,980 --> 00:13:33,150
so vozlišča, ki so na isti ravni v drevesu.

182
00:13:33,150 --> 00:13:42,230
Torej, 3 in 9 so bratje in sestre, saj so na isti ravni v drevesu.

183
00:13:42,230 --> 00:13:46,190
Oba imata enako starša, 7.

184
00:13:46,190 --> 00:13:51,400
Za 6 nima bratov in sester, ker 9 nima otrok.

185
00:13:51,400 --> 00:13:55,540
In 7 nima bratov in sester, saj je to koren našega drevesa,

186
00:13:55,540 --> 00:13:59,010
in tam je vedno samo 1 korenina.

187
00:13:59,010 --> 00:14:02,260
Za 7 bratov in sester, da bi tam moral biti vozlišče nad 7.

188
00:14:02,260 --> 00:14:07,480
Tu bi morala biti roditelj 7, v tem primeru 7 ne bo več koren drevesa.

189
00:14:07,480 --> 00:14:10,480
Potem bi to novo matično 7 tudi imeti otroka,

190
00:14:10,480 --> 00:14:16,480
in da bo otrok potem brat od 7.

191
00:14:16,480 --> 00:14:21,040
>> V redu. Gremo naprej.

192
00:14:21,040 --> 00:14:24,930
Ko smo začeli razpravo o binarnih dreves,

193
00:14:24,930 --> 00:14:28,790
smo se pogovarjali o tem, kako smo bili, da jih uporabljajo za

194
00:14:28,790 --> 00:14:32,800
pridobiti prednost pred obema nizi in povezanih seznamov.

195
00:14:32,800 --> 00:14:37,220
In kako bomo to, da je s tem odreja premoženja.

196
00:14:37,220 --> 00:14:41,080
Pravimo, da se naloži dvojiško drevo, v skladu s specifikacijo,

197
00:14:41,080 --> 00:14:45,740
če za vsako vozlišče v našem drevesu, v vseh njegovih potomcev na levi -

198
00:14:45,740 --> 00:14:48,670
Na levi strani otrok in vsi potomci levega otroka -

199
00:14:48,670 --> 00:14:54,510
imajo manj vrednosti, in vse vozlišča na desni -

200
00:14:54,510 --> 00:14:57,770
pravice otrok in vsi potomci pravega otroka -

201
00:14:57,770 --> 00:15:02,800
imajo vozlišča večja od vrednosti trenutnega vozlišča, ki jih gledate.

202
00:15:02,800 --> 00:15:07,850
Samo za enostavnosti, bomo za domnevo, da ne obstajajo kakršne koli podvojene vozlišča v našem drevesu.

203
00:15:07,850 --> 00:15:11,180
Na primer, to drevo mi ne bo ukvarjal s tem primerom

204
00:15:11,180 --> 00:15:13,680
kjer imamo vrednost 7 v korenu

205
00:15:13,680 --> 00:15:16,720
 in potem imamo tudi vrednost 7 drugje v drevo.

206
00:15:16,720 --> 00:15:24,390
V tem primeru boste opazili, da je to drevo res naročil.

207
00:15:24,390 --> 00:15:26,510
Imamo vrednost 7 v korenu.

208
00:15:26,510 --> 00:15:29,720
Vse levo od 7 -

209
00:15:29,720 --> 00:15:35,310
če bi razveljavili vse te majhne znamk tukaj -

210
00:15:35,310 --> 00:15:40,450
vse na levi 7 - 3 in 6 -

211
00:15:40,450 --> 00:15:49,410
te vrednosti sta manj kot 7, in vse, kar na desno - kar je le to 9 -

212
00:15:49,410 --> 00:15:53,450
večja od 7.

213
00:15:53,450 --> 00:15:58,650
>> To pa ni edina naročiti drevo, ki vsebujejo te vrednote,

214
00:15:58,650 --> 00:16:03,120
vendar naj pripravi nekaj več od njih.

215
00:16:03,120 --> 00:16:05,030
Tam je dejansko cel kup načinov, da lahko to storijo.

216
00:16:05,030 --> 00:16:09,380
Bom uporabo stenografijo samo ohraniti stvari preproste, če -

217
00:16:09,380 --> 00:16:11,520
ne črpa celotna škatle-in puščice -

218
00:16:11,520 --> 00:16:14,220
Grem, da pripravi številke in dodajte puščice, ki jih povezujejo.

219
00:16:14,220 --> 00:16:22,920
Če želite začeti, bomo šele pisati našo prvotno drevo še enkrat, kjer smo imeli 7, nato 3,

220
00:16:22,920 --> 00:16:25,590
in potem 3 opozorila nazaj na desno do 6,

221
00:16:25,590 --> 00:16:30,890
in 7 je imel pravico otroka, ki je bil 9.

222
00:16:30,890 --> 00:16:33,860
V redu. Kaj je še en način, da bi lahko napisal to drevo?

223
00:16:33,860 --> 00:16:38,800
Namesto, da bi 3 z leve otrok 7,

224
00:16:38,800 --> 00:16:41,360
Lahko bi tudi imeli 6 mora biti na levi otrok 7,

225
00:16:41,360 --> 00:16:44,470
in potem 3, je levo otrok iz 6.

226
00:16:44,470 --> 00:16:48,520
To bi bilo videti, kot to drevo tukaj, kjer sem dobil 7,

227
00:16:48,520 --> 00:16:57,860
nato 6, nato pa 3 in 9 na desni strani.

228
00:16:57,860 --> 00:17:01,490
Prav tako ne bi bilo treba imeti 7, kot je naš korenski vozel.

229
00:17:01,490 --> 00:17:03,860
Lahko bi tudi 6, kot je naš korenski vozel.

230
00:17:03,860 --> 00:17:06,470
Kaj bi bilo to videti?

231
00:17:06,470 --> 00:17:09,230
Če bomo ohranili ta lastnost naročil,

232
00:17:09,230 --> 00:17:12,970
vse na levi strani 6 mora biti manjša od nje.

233
00:17:12,970 --> 00:17:16,540
Obstaja samo ena možnost, in da je 3.

234
00:17:16,540 --> 00:17:19,869
Potem pa, kot pravi otrok od 6 let, imamo dve možnosti.

235
00:17:19,869 --> 00:17:25,380
Prvič, lahko imamo 7 in potem 9,

236
00:17:25,380 --> 00:17:28,850
ali bi jo lahko sestavi - kot, da sem na tem, da tu ne -

237
00:17:28,850 --> 00:17:34,790
kjer imamo 9, kot pravi otrok od 6,

238
00:17:34,790 --> 00:17:39,050
in potem 7 kot levi otroka iz 9.

239
00:17:39,050 --> 00:17:44,240
>> Zdaj, 7 in 6, niso edine možne vrednosti za root.

240
00:17:44,240 --> 00:17:50,200
Lahko bi tudi 3 se pri korenu.

241
00:17:50,200 --> 00:17:52,240
Kaj se zgodi, če 3 je vzrok?

242
00:17:52,240 --> 00:17:54,390
Tu se stvari malo zanimivo.

243
00:17:54,390 --> 00:17:58,440
Tri nima vrednosti, ki so manjše od njega,

244
00:17:58,440 --> 00:18:02,070
tako da celoten levi strani drevesa le, da bo nična.

245
00:18:02,070 --> 00:18:03,230
Tam je ne bo nič tam.

246
00:18:03,230 --> 00:18:07,220
Na desni strani smo lahko seznam stvari v naraščajočem vrstnem redu.

247
00:18:07,220 --> 00:18:15,530
Lahko bi imeli 3, nato 6, nato 7, nato pa 9.

248
00:18:15,530 --> 00:18:26,710
Ali lahko naredimo 3, potem 6, potem 9, potem 7.

249
00:18:26,710 --> 00:18:35,020
Ali lahko naredimo 3, nato pa 7, potem 6, potem 9.

250
00:18:35,020 --> 00:18:40,950
Ali, 3, 7 - pravzaprav ne, ne moremo narediti 7 več.

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

252
00:18:43,330 --> 00:18:54,710
To lahko storimo 9, nato pa od 9 lahko storimo, 6 in 7 potem.

253
00:18:54,710 --> 00:19:06,980
Ali lahko naredimo 3, potem 9, potem 7, nato pa 6.

254
00:19:06,980 --> 00:19:12,490
>> Ena stvar, ki vas opozoriti, da je tukaj

255
00:19:12,490 --> 00:19:14,510
da ta drevesa so malo čudno izgleda.

256
00:19:14,510 --> 00:19:17,840
Še posebej, če se ozremo na 4 drevesa na desni strani -

257
00:19:17,840 --> 00:19:20,930
Jaz jih bom krog, tukaj -

258
00:19:20,930 --> 00:19:28,410
ta drevesa videti skoraj natanko tako kot povezan seznam.

259
00:19:28,410 --> 00:19:32,670
Vsako vozlišče ima samo enega otroka,

260
00:19:32,670 --> 00:19:38,950
in tako nimamo nič od tega podobno kot drevesna struktura, ki jo vidimo, na primer,

261
00:19:38,950 --> 00:19:44,720
 V tem enem posameznega drevesa tukaj na spodnji levi strani.

262
00:19:44,720 --> 00:19:52,490
Ta drevesa so dejansko izrojene binarnih dreves

263
00:19:52,490 --> 00:19:54,170
in se bova pogovorila o teh več v prihodnosti -

264
00:19:54,170 --> 00:19:56,730
še posebej, če greš na sprejmejo tudi druge tečaje računalništva.

265
00:19:56,730 --> 00:19:59,670
Ta drevesa so degenerirana.

266
00:19:59,670 --> 00:20:03,780
Oni niso zelo koristen, saj res, ta struktura je primerna

267
00:20:03,780 --> 00:20:08,060
 za iskanje čase podobno kot povezan seznam.

268
00:20:08,060 --> 00:20:13,050
Ne dobimo izkoristiti dodatne spomina - ta dodatni kazalec -

269
00:20:13,050 --> 00:20:18,840
zaradi naše zgradbe je slaba na ta način.

270
00:20:18,840 --> 00:20:24,700
Namesto da bi šel naprej in potegnili binarnih dreves, ki imajo 9 na koren,

271
00:20:24,700 --> 00:20:27,220
ki je končni primeru, da bi imeli,

272
00:20:27,220 --> 00:20:32,380
namesto tega smo v tem trenutku, bomo govorili malo o tem drugi mandat

273
00:20:32,380 --> 00:20:36,150
, ki ga uporabljamo, ko govorimo o drevesih, ki se imenuje višina.

274
00:20:36,150 --> 00:20:45,460
>> Višina drevesa je razdalja od korena do najbolj oddaljeni vozlišča,

275
00:20:45,460 --> 00:20:48,370
oziroma število hmelja, ki bi jih morali narediti, da bi se

276
00:20:48,370 --> 00:20:53,750
izhajati iz korena in nato končajo na najbolj oddaljeni vozlišče v drevesu.

277
00:20:53,750 --> 00:20:57,330
Če pogledamo nekatere od teh dreves, ki smo jih pripravijo tukaj,

278
00:20:57,330 --> 00:21:07,870
lahko vidimo, da če bomo to drevo v levem zgornjem kotu in začnemo na 3,

279
00:21:07,870 --> 00:21:14,510
potem moramo narediti 1 skok, da pridete do 6, 2. hop priti do 7,

280
00:21:14,510 --> 00:21:20,560
in tretji skok, da pridete do 9.

281
00:21:20,560 --> 00:21:26,120
Tako je višina tega drevesa je 3.

282
00:21:26,120 --> 00:21:30,640
Mi lahko storite enako nalogo za druga drevesa, opisanih v tej green,

283
00:21:30,640 --> 00:21:40,100
Opažamo, da je višina vseh teh dreves je tudi res 3.

284
00:21:40,100 --> 00:21:45,230
To je del tega, kar naredi sprevrgli -

285
00:21:45,230 --> 00:21:53,750
da je njihova višina je le ena manjše od števila vozlišč v celotnem drevesu.

286
00:21:53,750 --> 00:21:58,400
Če pogledamo to drugo drevo, ki je obkrožen z rdečo, na drugi strani,

287
00:21:58,400 --> 00:22:03,920
vidimo, da so najbolj oddaljene-leaf vozlišč sta 6 in 9 -

288
00:22:03,920 --> 00:22:06,940
listov so tisti vozlišča, ki nimajo otrok.

289
00:22:06,940 --> 00:22:11,760
Torej, da bi dobili iz korenskega vozlišča bodisi na 6 ali 9,

290
00:22:11,760 --> 00:22:17,840
imamo tudi en skok priti do 7 in nato 2. hop priti do 9,

291
00:22:17,840 --> 00:22:21,240
in prav, samo 2. hop od 7 priti do 6.

292
00:22:21,240 --> 00:22:29,080
Tako je višina tega drevesa tukaj je samo 2.

293
00:22:29,080 --> 00:22:35,330
Lahko greš nazaj in to, da za vse druge dreves, ki smo že razpravljali

294
00:22:35,330 --> 00:22:37,380
začenši s 7 in 6,

295
00:22:37,480 --> 00:22:42,500
in boste ugotovili, da je višina vseh teh dreves je 2.

296
00:22:42,500 --> 00:22:46,320
>> Razlog, da smo se pogovarjali o naloži binarnih dreves

297
00:22:46,320 --> 00:22:50,250
in zakaj si kul, ker lahko iščete po njih v

298
00:22:50,250 --> 00:22:53,810
zelo podoben način iskanja preko razvrščenih matrike.

299
00:22:53,810 --> 00:22:58,720
To je, če govorimo o že čas, da izboljšano iskanje

300
00:22:58,720 --> 00:23:02,730
nad navadno povezani seznam.

301
00:23:02,730 --> 00:23:05,010
Z povezanega seznama - če želite najti določen element -

302
00:23:05,010 --> 00:23:07,470
ste v najboljšem primeru bomo narediti neke vrste linearni iskanje

303
00:23:07,470 --> 00:23:10,920
če ste začeli na začetku seznama in hop-by-1 1 -

304
00:23:10,920 --> 00:23:12,620
eno vozlišče za eno vozlišče -

305
00:23:12,620 --> 00:23:16,060
skozi celotno seznamu, dokler ne boste našli, kar iščete.

306
00:23:16,060 --> 00:23:19,440
Ker, če imate binarno drevo, ki je shranjen v tej lepi obliki,

307
00:23:19,440 --> 00:23:23,300
lahko dejansko dobili več od binarnega iskanja dogaja

308
00:23:23,300 --> 00:23:25,160
kjer si deli in vladaj

309
00:23:25,160 --> 00:23:29,490
in iskanje z ustreznim polovici drevesa na vsakem koraku.

310
00:23:29,490 --> 00:23:32,840
Poglejmo, kako to deluje.

311
00:23:32,840 --> 00:23:38,850
>> Če imamo - spet vrača v svojo izvorno drevo -

312
00:23:38,850 --> 00:23:46,710
bomo začeli ob 7., imamo 3 na levi strani, na desni strani 9,

313
00:23:46,710 --> 00:23:51,740
in pod 3 imamo 6.

314
00:23:51,740 --> 00:24:01,880
Če želimo, da poiščete številko 6 v tem drevesu, bi začnemo pri korenu.

315
00:24:01,880 --> 00:24:08,910
Mi bi primerjali vrednosti iščemo, recimo 6,

316
00:24:08,910 --> 00:24:12,320
na vrednost, shranjeno v vozlišču, da smo trenutno proučujejo, 7,

317
00:24:12,320 --> 00:24:21,200
Ugotovijo, da je dejansko 6 manj kot 7, zato smo se selili v levo.

318
00:24:21,200 --> 00:24:25,530
Če je vrednost 6 je večja od 7, bi bile namesto tega pomika v desno.

319
00:24:25,530 --> 00:24:29,770
Ker vemo, da je - zaradi strukture naše odredi drevesa binarnem -

320
00:24:29,770 --> 00:24:33,910
vse vrednosti manj kot 7 bodo shranjeni na levi strani 7,

321
00:24:33,910 --> 00:24:40,520
ni treba niti trudile gleda skozi desni strani drevesa.

322
00:24:40,520 --> 00:24:43,780
Ko gremo v levo in smo zdaj v vozlišču, ki vsebuje 3,

323
00:24:43,780 --> 00:24:48,110
lahko storimo, da se še enkrat isto primerjavo, kjer smo primerjali 3 in 6.

324
00:24:48,110 --> 00:24:52,430
In smo ugotovili, da med 6 - večja od 3, - vrednost iščemo

325
00:24:52,430 --> 00:24:58,580
lahko gremo na desni strani vozlišča, ki vsebuje 3.

326
00:24:58,580 --> 00:25:02,670
Ni levi strani tukaj, tako da smo mogoče prezreti, da je.

327
00:25:02,670 --> 00:25:06,510
Ampak samo zato, ker vemo, da smo iskali na drevesu samega,

328
00:25:06,510 --> 00:25:08,660
in lahko vidimo, da je drevo nima otrok.

329
00:25:08,660 --> 00:25:13,640
>> Prav tako je zelo enostavno poiskati 6 tega drevesa, če delamo to sebe kot človeka,

330
00:25:13,640 --> 00:25:16,890
vendar pa si sledijo procesu mehansko kot računalnik bi naredil

331
00:25:16,890 --> 00:25:18,620
zares razumeli algoritem.

332
00:25:18,620 --> 00:25:26,200
Na tej točki smo zdaj gledaš vozlišča, ki vsebuje 6,

333
00:25:26,200 --> 00:25:29,180
in iščemo vrednost 6,

334
00:25:29,180 --> 00:25:31,740
to res, smo našli ustrezno vozlišče.

335
00:25:31,740 --> 00:25:35,070
Našli smo vrednost 6 v našem drevesu in ne moremo ustaviti naše iskanje.

336
00:25:35,070 --> 00:25:37,330
Na tej točki, glede na to, kaj se dogaja,

337
00:25:37,330 --> 00:25:41,870
lahko rečemo, da smo našli vrednost 6, obstaja v našem drevesu.

338
00:25:41,870 --> 00:25:47,640
Ali pa, če nameravate vstaviti vozlišča ali pa nekaj, kar lahko naredimo, da na tej točki.

339
00:25:47,640 --> 00:25:53,010
>> Naredimo nekaj več poizvedbe samo, da vidim kako to deluje.

340
00:25:53,010 --> 00:25:59,390
Oglejmo si, kaj se zgodi, če bi poskušali poiskati vrednosti 10.

341
00:25:59,390 --> 00:26:02,970
Če smo poiskati vrednosti 10, bi začnemo pri korenu.

342
00:26:02,970 --> 00:26:07,070
Radi bi videli, da je 10 več kot 7, zato smo se selili v desno.

343
00:26:07,070 --> 00:26:13,640
Radi bi prišli do 9 in primerjajte 9 do 10, in vidim, da je res 9 manj kot 10.

344
00:26:13,640 --> 00:26:16,210
Torej, še enkrat, bi se trudimo, da se premaknete na desno.

345
00:26:16,210 --> 00:26:20,350
Toda na tej točki, bi opazili, da smo na ničelno vozlišče.

346
00:26:20,350 --> 00:26:23,080
Tukaj ni ničesar. Ničesar ni, kjer bi morala biti 10.

347
00:26:23,080 --> 00:26:29,360
To je, če se lahko poročajo z napako - da je dejansko ne 10 v drevo.

348
00:26:29,360 --> 00:26:35,420
In končno, gremo skozi primeru, ko smo poskušali poiskati 1 v drevo.

349
00:26:35,420 --> 00:26:38,790
To je podobno, kaj se zgodi, če gledamo do 10, razen namesto da bi šel na desno,

350
00:26:38,790 --> 00:26:41,260
smo šli na levo.

351
00:26:41,260 --> 00:26:46,170
Začnemo ob 7 in videli, da je 1 manj kot 7, zato gremo na levo.

352
00:26:46,170 --> 00:26:51,750
Pridemo do 3 in videli, da je 1 manj kot 3, zato še enkrat smo poskušali premakniti na levo.

353
00:26:51,750 --> 00:26:59,080
Na tej točki moramo ničelno vozlišče, tako da bomo lahko ponovno prijaviti napako.

354
00:26:59,080 --> 00:27:10,260
>> Če bi želeli izvedeti več o binarnih dreves

355
00:27:10,260 --> 00:27:14,420
obstaja cel kup zabavno malo težav, ki jih lahko naredite z njimi.

356
00:27:14,420 --> 00:27:19,450
Predlagam prakticiranja risbo iz teh diagramov eno-by-1

357
00:27:19,450 --> 00:27:21,910
in po skozi vse različne korake,

358
00:27:21,910 --> 00:27:25,060
ker se bo to zgodilo v izjemno priročen

359
00:27:25,060 --> 00:27:27,480
ne samo, ko delaš problem kodiranja Huffman niz

360
00:27:27,480 --> 00:27:29,390
ampak tudi v prihodnjih tečajev -

361
00:27:29,390 --> 00:27:32,220
le za učenje, kako pripraviti iz te podatkovne strukture in mislim skozi težave

362
00:27:32,220 --> 00:27:38,000
z pero in papir, ali v tem primeru, iPad in pisalo.

363
00:27:38,000 --> 00:27:41,000
>> Na tej točki, čeprav, bomo naprej, da naredite nekaj kodiranja prakse

364
00:27:41,000 --> 00:27:44,870
in dejansko igrajo s temi binarnih dreves in videti.

365
00:27:44,870 --> 00:27:52,150
Grem nazaj preklopi na mojem računalniku.

366
00:27:52,150 --> 00:27:58,480
V tem delu odseka, namesto da bi uporabili CS50 Run ali CS50 Spaces,

367
00:27:58,480 --> 00:28:01,500
Bom uporabo aparata.

368
00:28:01,500 --> 00:28:04,950
>> Po skupaj s specifikacijo Problem Set,

369
00:28:04,950 --> 00:28:07,740
Vidim, da sem moral odpreti aparat,

370
00:28:07,740 --> 00:28:11,020
pojdi v mojo mapo Dropbox, ustvarite mapo, imenovano oddelek 7,

371
00:28:11,020 --> 00:28:15,730
in nato ustvarite datoteko z imenom binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Pa gremo. Imam aparat že odprta.

373
00:28:22,050 --> 00:28:25,910
Grem dvigni terminal.

374
00:28:25,910 --> 00:28:38,250
Jaz grem v mapo Dropbox, da mapi section7,

375
00:28:38,250 --> 00:28:42,230
in videti je popolnoma prazna.

376
00:28:42,230 --> 00:28:48,860
Zdaj bom odprl binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
V redu. Pa gremo - prazno datoteko.

378
00:28:51,750 --> 00:28:54,330
>> Vrniva se v specifikaciji.

379
00:28:54,330 --> 00:28:59,850
Specifikacija želi ustvariti novo opredelitev vrste

380
00:28:59,850 --> 00:29:03,080
za binarno drevo vozlišče, ki vsebuje int vrednosti -

381
00:29:03,080 --> 00:29:07,110
tako kot vrednote, ki jih puščala v naši diagramov prej.

382
00:29:07,110 --> 00:29:11,740
Mi bomo to uporabiti boiler typedef, da smo naredili prav tukaj

383
00:29:11,740 --> 00:29:14,420
da bi morali priznati iz Set Problem 5 -

384
00:29:14,420 --> 00:29:19,190
če si razpršene tabele način osvajanja programa speller.

385
00:29:19,190 --> 00:29:22,540
Prav tako bi morali prepoznati od točke prejšnjega tedna

386
00:29:22,540 --> 00:29:23,890
, kjer smo se pogovarjali o povezanih seznamih.

387
00:29:23,890 --> 00:29:27,870
Imamo to typedef struct iz vozlišča,

388
00:29:27,870 --> 00:29:34,430
in smo glede na to struct Node to ime vozlišča struct poprej

389
00:29:34,430 --> 00:29:39,350
tako da bomo lahko nato pa se nanašajo nanj, saj bomo želeli imeti kazalce vozlišče struct

390
00:29:39,350 --> 00:29:45,740
kot del naše struct, vendar smo potem obkroženo to -

391
00:29:45,740 --> 00:29:47,700
ali še bolje, obdan to - v typedef

392
00:29:47,700 --> 00:29:54,600
tako, da je pozneje v kodo lahko sklicuje na to struct kot le vozlišče namesto struct vozlišče.

393
00:29:54,600 --> 00:30:03,120
>> To bo zelo podoben posamezno povezano opredelitvijo seznama, da smo videli prejšnji teden.

394
00:30:03,120 --> 00:30:20,070
Če želite to narediti, kaj je pravkar začela s pisanjem ven boiler.

395
00:30:20,070 --> 00:30:23,840
Vemo, da moramo imeti celoštevilsko vrednost,

396
00:30:23,840 --> 00:30:32,170
tako da bomo dal v int vrednost, nato pa, namesto da bi le en kazalec na naslednji element -

397
00:30:32,170 --> 00:30:33,970
kot smo samostojno povezanih seznamov -

398
00:30:33,970 --> 00:30:38,110
bomo imeli levo in desno kazalca otrok.

399
00:30:38,110 --> 00:30:42,880
To je zelo enostavno preveč - struct vozlišče * levo otrok;

400
00:30:42,880 --> 00:30:51,190
in struct vozlišče * pravice otrok;. Kul.

401
00:30:51,190 --> 00:30:54,740
To izgleda zelo dober začetek.

402
00:30:54,740 --> 00:30:58,530
Vrniva se v specifikaciji.

403
00:30:58,530 --> 00:31:05,030
>> Zdaj moramo opredeliti globalno spremenljivko * vozlišče za koren drevesa.

404
00:31:05,030 --> 00:31:10,590
Bomo, da bo ta globalni, tako kot smo naredili 1. kazalec na našem seznamu povezana tudi globalno.

405
00:31:10,590 --> 00:31:12,690
To je bilo tako, da je v funkcijah, ki jih pišejo

406
00:31:12,690 --> 00:31:16,180
nimamo, da gre okoli tega korena -

407
00:31:16,180 --> 00:31:19,620
čeprav bomo videli, da če ne želite, da napišete svoje funkcije rekurzivno,

408
00:31:19,620 --> 00:31:22,830
da bi bilo bolje, da sploh ne dajati okoli kot globalna na prvem mestu

409
00:31:22,830 --> 00:31:28,090
in namesto tega zagnati lokalno v vašem glavne funkcije.

410
00:31:28,090 --> 00:31:31,960
Ampak, bomo to vsem svetu, da začnete.

411
00:31:31,960 --> 00:31:39,920
Spet vam bomo nekaj mest, in bom, da razglasi vozlišče koren *.

412
00:31:39,920 --> 00:31:46,770
Samo se prepričajte, da se ne pustim nezaceto, grem, da ga postavi na null.

413
00:31:46,770 --> 00:31:52,210
Zdaj, v glavnih funkcij - kar bomo napisali zelo hitro tukaj -

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

415
00:32:00,450 --> 00:32:10,640
in jaz bom za začetek razglasitvi svoj niz argv kot const samo zato, da vem,

416
00:32:10,640 --> 00:32:14,550
da te trditve so argumenti, ki najbrž ne želijo spremeniti.

417
00:32:14,550 --> 00:32:18,390
Če želim, da jih je treba spremeniti verjetno izdelavo kopije njih.

418
00:32:18,390 --> 00:32:21,740
Videli boste to veliko v kodi.

419
00:32:21,740 --> 00:32:25,440
V redu je tako ali tako. Saj je v redu, da ga pustijo kot - izpustiti konst, če želite.

420
00:32:25,440 --> 00:32:28,630
Jaz ponavadi ga v samo zato, da sem se spomnil

421
00:32:28,630 --> 00:32:33,650
 da najbrž ne želite spremeniti te trditve.

422
00:32:33,650 --> 00:32:39,240
>> Kot vedno, bom tudi to Vračilo 0 črto na koncu glavni.

423
00:32:39,240 --> 00:32:45,730
Tukaj bom inicializacijo moje korenine vozlišče.

424
00:32:45,730 --> 00:32:48,900
Ker stoji prav zdaj imam kazalec, ki je nastavljena na null,

425
00:32:48,900 --> 00:32:52,970
tako da je obrnjena na nič.

426
00:32:52,970 --> 00:32:57,480
Da bi dejansko začeli graditi vozlišče,

427
00:32:57,480 --> 00:32:59,250
Najprej je treba dodeliti pomnilnika za to.

428
00:32:59,250 --> 00:33:05,910
Jaz bom to storil tako, da spomin na kup z malloc.

429
00:33:05,910 --> 00:33:10,660
Grem iz korenin, ki je enak rezultat knjižnične funkcije malloc,

430
00:33:10,660 --> 00:33:19,550
in bom uporabljati sizeof operaterja za izračun velikosti vozlišča.

431
00:33:19,550 --> 00:33:24,990
Razlog, da sem uporabo sizeof vozlišče za razliko od, recimo,

432
00:33:24,990 --> 00:33:37,020
gre nekako takole - malloc (4 + 4 +4) ali malloc 12 -

433
00:33:37,020 --> 00:33:40,820
zato, ker hočem, da je moja koda čim bolj združljivi.

434
00:33:40,820 --> 00:33:44,540
Želim, da se bodo lahko tega C datoteko., Njihovo zbiranje na napravi,

435
00:33:44,540 --> 00:33:48,820
in jo pripravijo na moji 64-bitni Mac -

436
00:33:48,820 --> 00:33:52,040
ali na popolnoma drugačno arhitekturo -

437
00:33:52,040 --> 00:33:54,640
in želim, da vse to dela isti.

438
00:33:54,640 --> 00:33:59,510
>> Če delam predpostavke o velikosti spremenljivk -

439
00:33:59,510 --> 00:34:02,070
velikost notr ali velikost kazalca -

440
00:34:02,070 --> 00:34:06,070
potem sem tudi domnevam o vrstah arhitekture

441
00:34:06,070 --> 00:34:10,440
na katere se lahko moja koda uspešno pripravijo ob zagonu.

442
00:34:10,440 --> 00:34:15,030
Vedno uporabljajte sizeof v nasprotju z ročno seštevek struct polj.

443
00:34:15,030 --> 00:34:20,500
Drugi razlog je, da je lahko tudi podloga, da prevajalnik postavlja v struct.

444
00:34:20,500 --> 00:34:26,570
Celo tako, da se seštejejo posamezna področja, ni nekaj, kar običajno želijo storiti,

445
00:34:26,570 --> 00:34:30,340
tako, izbrišite to vrstico.

446
00:34:30,340 --> 00:34:33,090
Zdaj pa zares inicializirati to korensko vozlišče,

447
00:34:33,090 --> 00:34:36,489
Jaz bom moral priključiti vrednosti za vsako od njenih različnih področjih.

448
00:34:36,489 --> 00:34:41,400
Na primer, za vrednost, vem, da želite inicializirati do 7,

449
00:34:41,400 --> 00:34:46,920
in zdaj bom iz leve otrok je nična

450
00:34:46,920 --> 00:34:55,820
in pravico otroka, da je tudi nič. Čudovito!

451
00:34:55,820 --> 00:35:02,670
Naredili smo ta del spec.

452
00:35:02,670 --> 00:35:07,390
>> Specifikacija navzdol na dnu strani 3 me prosi, da ustvarite še tri vozlišča -

453
00:35:07,390 --> 00:35:10,600
1, ki vsebujejo 3, 1, ki vsebuje 6 in 1 z 9 -

454
00:35:10,600 --> 00:35:14,210
in jih nato žice gor, tako da izgleda natanko tako kot naši drevesnega diagrama

455
00:35:14,210 --> 00:35:17,120
da smo govorili prej.

456
00:35:17,120 --> 00:35:20,450
Naredimo to zelo hitro tukaj.

457
00:35:20,450 --> 00:35:26,270
Videli boste res hitro, da bom začel pisati kup dvojnika kode.

458
00:35:26,270 --> 00:35:32,100
Grem ustvariti vozlišče * in bom poklical tri.

459
00:35:32,100 --> 00:35:36,000
Grem jo nastavite enako malloc (sizeof (vozlišče)).

460
00:35:36,000 --> 00:35:41,070
Grem iz 3-> vrednost = 3.

461
00:35:41,070 --> 00:35:54,780
Tri -> left_child = NULL; 3 -> desni _child = NULL; tudi.

462
00:35:54,780 --> 00:36:01,150
To izgleda zelo podoben inicializacijo korenine, in to je točno to, kar

463
00:36:01,150 --> 00:36:05,760
Jaz bom moral storiti, če začnem pri inicializaciji 6 in 9, kot dobro.

464
00:36:05,760 --> 00:36:20,720
Storil bom, da res hitro tukaj - pravzaprav, bom naredil malo kopiraj in prilepi,

465
00:36:20,720 --> 00:36:46,140
in se prepričajte, da sem - v redu.

466
00:36:46,470 --> 00:37:09,900
 Zdaj pa sem dobil kopirali in lahko gredo naprej in nastavite enako 6.

467
00:37:09,900 --> 00:37:14,670
Vidite lahko, da to traja nekaj časa in ni super-učinkovita.

468
00:37:14,670 --> 00:37:22,610
V samo malo, bomo napisali funkcijo, ki bo naredil to za nas.

469
00:37:22,610 --> 00:37:32,890
Želim zamenjate z 9, da bi z zamenjavo 6.

470
00:37:32,890 --> 00:37:37,360
>> Zdaj imamo vse naše vozlišč ustvariti in inicializiran.

471
00:37:37,360 --> 00:37:41,200
Imamo naše korenine nastavi na 7 ali vsebuje vrednost 7,

472
00:37:41,200 --> 00:37:46,510
naše vozlišče, ki vsebuje 3, naše vozlišče vsebuje 6, in naše vozlišče, ki vsebuje 9.

473
00:37:46,510 --> 00:37:50,390
Na tej točki je vse, kar morate storiti je, žice vse gor.

474
00:37:50,390 --> 00:37:53,020
Razlog, da sem inicializiramo vse napotke za null le tako, da se prepričam, da

475
00:37:53,020 --> 00:37:56,260
Nimam nobenih kazalcev v nezaceto tam po naključju.

476
00:37:56,260 --> 00:38:02,290
In tudi zato, ker v tem trenutku, sem le, da dejansko povezujejo vozlišča med seboj -

477
00:38:02,290 --> 00:38:04,750
s tistimi, ki ste jih dejansko povezani z - mi ni treba iti skozi in da

478
00:38:04,750 --> 00:38:08,240
Prepričajte se, da so vsi nulls so tam na ustreznih mestih.

479
00:38:08,240 --> 00:38:15,630
>> Začnite pri korenu, vem, da je koren v levo otrok 3.

480
00:38:15,630 --> 00:38:21,250
Vem, da je koren pravica otrok je 9.

481
00:38:21,250 --> 00:38:24,880
Po tem, samo drugi otrok, ki sem jih pustil, da skrbi

482
00:38:24,880 --> 00:38:39,080
je pravica otroka je 3, kar je 6.

483
00:38:39,080 --> 00:38:44,670
Na tej točki je vse izgleda precej dobro.

484
00:38:44,670 --> 00:38:54,210
Mi bomo izbrisati nekatere od teh vrstic.

485
00:38:54,210 --> 00:38:59,540
Zdaj vse izgleda precej dobro.

486
00:38:59,540 --> 00:39:04,240
Vrnimo se na naš specifikacije in videli, kaj moramo narediti.

487
00:39:04,240 --> 00:39:07,610
>> Na tej točki moramo napisati funkcijo imenovano "vsebuje"

488
00:39:07,610 --> 00:39:14,150
s prototipom "Bool vsebuje (int vrednost)."

489
00:39:14,150 --> 00:39:17,060
In ta vsebuje funkcijo vrača res

490
00:39:17,060 --> 00:39:21,200
 Če drevo je poudaril, da z našo globalno spremenljivko korenin

491
00:39:21,200 --> 00:39:26,950
 vsebuje vrednost izrečene v funkciji in false sicer.

492
00:39:26,950 --> 00:39:29,000
Pojdimo naprej in to.

493
00:39:29,000 --> 00:39:35,380
To se bo točno tako kot lookup, da smo naredili z roko na iPad le malo pred.

494
00:39:35,380 --> 00:39:40,130
Pojdimo povečavo nazaj malo in se pomaknete navzgor.

495
00:39:40,130 --> 00:39:43,130
Bomo dal to funkcijo tik nad našo glavno funkcijo

496
00:39:43,130 --> 00:39:48,990
tako da se nam ni treba narediti kakršno koli prototipov.

497
00:39:48,990 --> 00:39:55,960
Torej, int vsebuje (int vrednost).

498
00:39:55,960 --> 00:40:00,330
Takole. Tam je boiler deklaracija.

499
00:40:00,330 --> 00:40:02,900
Samo se prepričajte, da bo to pripravijo,

500
00:40:02,900 --> 00:40:06,820
Grem, da gredo naprej in samo nastavi na vrne false.

501
00:40:06,820 --> 00:40:09,980
Zdaj je ta funkcija le ne bo naredil ničesar in vedno poročajo, da

502
00:40:09,980 --> 00:40:14,010
vrednost, ki ga iščemo, ni v drevesu.

503
00:40:14,010 --> 00:40:16,280
>> Na tej točki, je verjetno dobra ideja -

504
00:40:16,280 --> 00:40:19,600
saj smo napisali cel kup kode in nismo niti poskusili, da ga testirajo še -

505
00:40:19,600 --> 00:40:22,590
se prepričajte, da je vse pripravlja.

506
00:40:22,590 --> 00:40:27,460
Obstaja nekaj stvari, ki jih moramo storiti, da poskrbite, da se bo to dejansko pripravijo.

507
00:40:27,460 --> 00:40:33,530
Najprej poglejte, če smo bili z uporabo vseh funkcij v vseh knjižnicah, ki smo jih še niso vključene.

508
00:40:33,530 --> 00:40:37,940
Naloge, ki smo jih do sedaj so uporabljeni malloc,

509
00:40:37,940 --> 00:40:43,310
in potem smo tudi bili z uporabo te vrste - to nestandardno vrsto imenovano "bool' -

510
00:40:43,310 --> 00:40:45,750
, ki je vključena v standardni bool datoteke glavo.

511
00:40:45,750 --> 00:40:53,250
Vsekakor želimo vključiti standardne bool.h za bool tip,

512
00:40:53,250 --> 00:40:59,230
in želimo tudi # include standardni lib.h za standardne knjižnice

513
00:40:59,230 --> 00:41:03,530
da so malloc in brezplačno, in vse to.

514
00:41:03,530 --> 00:41:08,660
Torej, pomanjšati, bomo nehal.

515
00:41:08,660 --> 00:41:14,190
Poskusimo in se prepričajte, da je to dejansko storil prevesti.

516
00:41:14,190 --> 00:41:18,150
Vidimo, da je tako, da smo na pravi poti.

517
00:41:18,150 --> 00:41:22,990
>> Odprimo se binary_tree.c znova.

518
00:41:22,990 --> 00:41:34,530
To ureja. Greva dol in se prepričajte, da vstavite nekaj klicev na naš funkcijo vsebuje -

519
00:41:34,530 --> 00:41:40,130
Samo se prepričajte, da je vse lepo in prav.

520
00:41:40,130 --> 00:41:43,170
Na primer, ko smo nekatere poizvedbe v našem drevesu prej,

521
00:41:43,170 --> 00:41:48,500
smo poskušali poiskati vrednosti 6, 10 in 1, in smo vedeli, da je bil 6 v drevesu

522
00:41:48,500 --> 00:41:52,220
10 ni v drevesu in 1 ni v drevesu, bodisi.

523
00:41:52,220 --> 00:41:57,230
Izkoristimo te vzorčne klice kot način, da ugotovimo, ali ne

524
00:41:57,230 --> 00:41:59,880
Vsebuje naša funkcija deluje.

525
00:41:59,880 --> 00:42:05,210
Da bi to storili, bom uporabi printf funkcijo,

526
00:42:05,210 --> 00:42:10,280
in bomo izpisal rezultat razpisa za vsebuje.

527
00:42:10,280 --> 00:42:13,280
Bom dal v nizu "vsebuje (% d) = ker

528
00:42:13,280 --> 00:42:20,470
 bomo čep v vrednosti, ki jo bomo iskati,

529
00:42:20,470 --> 00:42:27,130
in =% s \ n "in jo uporabite kot naš obliki niza.

530
00:42:27,130 --> 00:42:30,720
Mi smo le, da bo videl - dobesedno izpiše na zaslonu -

531
00:42:30,720 --> 00:42:32,060
kar izgleda kot klic funkcije.

532
00:42:32,060 --> 00:42:33,580
To pravzaprav ni klic funkcije.

533
00:42:33,580 --> 00:42:36,760
 To je samo niz, ki je videti kot klic funkcije.

534
00:42:36,760 --> 00:42:41,140
>> Zdaj pa gremo, da priključite na vrednosti.

535
00:42:41,140 --> 00:42:43,580
Bomo poskušali vsebuje 6.,

536
00:42:43,580 --> 00:42:48,340
in kaj potem bomo tukaj storiti, je, da uporabite trikomponentne operaterja.

537
00:42:48,340 --> 00:42:56,340
Poglejmo - vsebuje 6 - tako, zdaj sem se iz 6, če vsebuje 6 je res,

538
00:42:56,340 --> 00:43:01,850
string, da bomo poslali v formatu% s značaja

539
00:43:01,850 --> 00:43:04,850
se bo niz "true".

540
00:43:04,850 --> 00:43:07,690
Naj se pomaknite čez nekaj trenutkov.

541
00:43:07,690 --> 00:43:16,210
Sicer pa želimo poslati niz "false", če vsebuje 6 vrne false.

542
00:43:16,210 --> 00:43:19,730
To je malo izgleda bedasto, vendar sem ugotovil sem lahko tudi ponazarjajo

543
00:43:19,730 --> 00:43:23,780
kaj trikomponentnih upravljavec izgleda, saj še nismo videli, za nekaj časa.

544
00:43:23,780 --> 00:43:27,670
To bo lepo, priročen način, da ugotovimo, če je naša Vsebuje funkcija deluje.

545
00:43:27,670 --> 00:43:30,040
Grem nazaj pomaknite čez levo,

546
00:43:30,040 --> 00:43:39,900
in bom kopiraj in prilepi to vrstico nekajkrat.

547
00:43:39,900 --> 00:43:44,910
To je spremenilo nekatere od teh vrednosti okoli,

548
00:43:44,910 --> 00:43:59,380
tako da to se bo 1, in to se bo 10.

549
00:43:59,380 --> 00:44:02,480
>> Na tej točki imamo lepo vsebuje funkcijo.

550
00:44:02,480 --> 00:44:06,080
Imamo nekaj testov, in bomo videli, če je to vse deluje.

551
00:44:06,080 --> 00:44:08,120
Na tej točki smo napisal nekaj več kode.

552
00:44:08,120 --> 00:44:13,160
Čas je, da zaprete, in se prepričajte, da je vse še pripravlja.

553
00:44:13,160 --> 00:44:20,360
Zaprite in zdaj probajmo tako binarno drevo znova.

554
00:44:20,360 --> 00:44:22,260
No, izgleda, da imamo napako,

555
00:44:22,260 --> 00:44:26,930
in imamo to izrecno opredeljuje, da je knjižnično funkcijo printf.

556
00:44:26,930 --> 00:44:39,350
Izgleda, da moramo iti in # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
In s tem je treba vse prevesti. Vsi smo v redu.

558
00:44:45,350 --> 00:44:50,420
Zdaj pa poskusite zagnati binarno drevo in glej kaj se zgodi.

559
00:44:50,420 --> 00:44:53,520
Tukaj smo, /. Binary_tree,

560
00:44:53,520 --> 00:44:55,190
in vidimo, da je, kot smo pričakovali -

561
00:44:55,190 --> 00:44:56,910
ker nismo izvajali vsebuje še

562
00:44:56,910 --> 00:44:59,800
ali še bolje, kar smo pravkar dal v zameno lažno -

563
00:44:59,800 --> 00:45:03,300
vidimo, da je samo vrača false, za vse,

564
00:45:03,300 --> 00:45:06,180
tako, da se vsi, ki delajo večinoma dokaj dobro.

565
00:45:06,180 --> 00:45:11,860
>> Pojdimo nazaj in dejansko izvajanje vsebuje na tej točki.

566
00:45:11,860 --> 00:45:17,490
Grem, da se pomaknete navzdol, povečanje, in -

567
00:45:17,490 --> 00:45:22,330
Zapomnite si, da je algoritem smo uporabili, da smo začeli v korenskem vozlišču

568
00:45:22,330 --> 00:45:28,010
in nato v vsakem vozlišču, da se srečamo, naredimo primerjavo,

569
00:45:28,010 --> 00:45:32,380
in na podlagi tega smo za primerjavo premaknite na levo otroka ali desno otroka.

570
00:45:32,380 --> 00:45:39,670
To bo videti zelo podobna binarno kodo iskalno da je napisal v začetku mandata.

571
00:45:39,670 --> 00:45:47,810
Ko smo začeli, smo vedeli, da želimo, da imajo na trenutno vozlišče

572
00:45:47,810 --> 00:45:54,050
da gledaš, in trenutno vozlišče se bo initialized v korensko vozlišče.

573
00:45:54,050 --> 00:45:56,260
In zdaj, gremo, da bo šel skozi drevesa,

574
00:45:56,260 --> 00:45:58,140
in ne pozabite, da je naš zavorno stanje -

575
00:45:58,140 --> 00:46:01,870
 ko smo dejansko delal na primeru z roko -

576
00:46:01,870 --> 00:46:03,960
je bilo, ko smo naleteli ničelno vozlišče,

577
00:46:03,960 --> 00:46:05,480
ne takrat, ko smo si ogledali ničelno otroka,

578
00:46:05,480 --> 00:46:09,620
ampak ko smo dejansko preselil v vozlišče v drevesu

579
00:46:09,620 --> 00:46:12,640
in ugotovili, da smo na ničelno vozlišče.

580
00:46:12,640 --> 00:46:20,720
Bomo Ponovil dokler tren ni enaka null.

581
00:46:20,720 --> 00:46:22,920
In kaj bomo storili?

582
00:46:22,920 --> 00:46:31,610
Gremo na test, če (tren -> vrednost == vrednost)

583
00:46:31,610 --> 00:46:35,160
potem vemo, da smo dejansko našli vozlišče, ki ga iščete.

584
00:46:35,160 --> 00:46:40,450
Torej, tukaj se lahko vrnemo res.

585
00:46:40,450 --> 00:46:49,830
Sicer pa bi radi videli, ali je vrednost nižja od vrednosti.

586
00:46:49,830 --> 00:46:53,850
Če je trenutno vozlišče je vrednost nižja od vrednosti, ki ga iščemo,

587
00:46:53,850 --> 00:46:57,280
bomo v desno.

588
00:46:57,280 --> 00:47:10,600
Torej, tren = tren -> right_child in drugače, bomo premakniti na levo.

589
00:47:10,600 --> 00:47:17,480
tren = tren -> left_child;. Precej enostavno.

590
00:47:17,480 --> 00:47:22,830
>> Verjetno si priznati zanko, ki je videti zelo podobna temu iz

591
00:47:22,830 --> 00:47:27,580
binarno iskanje v začetku mandata, razen takrat smo imeli opravka z nizko, srednje in visoko.

592
00:47:27,580 --> 00:47:30,000
Tukaj smo samo še pogled na sedanjo vrednost,

593
00:47:30,000 --> 00:47:31,930
Tako je lepo in preprosto.

594
00:47:31,930 --> 00:47:34,960
Naj poskrbite, da ta številka deluje.

595
00:47:34,960 --> 00:47:42,780
Najprej se prepričajte, da pripravlja. Izgleda, da ne.

596
00:47:42,780 --> 00:47:47,920
Poskusimo ga zaženete.

597
00:47:47,920 --> 00:47:50,160
In res, da natisne vse, kar smo pričakovali.

598
00:47:50,160 --> 00:47:54,320
Ugotavlja 6 v drevo, ne najde 10, ker 10 ni v drevesu

599
00:47:54,320 --> 00:47:57,740
in ne najde 1, bodisi zato, ker 1 je tudi ni v drevesu.

600
00:47:57,740 --> 00:48:01,420
Cool stvari.

601
00:48:01,420 --> 00:48:04,470
>> V redu. Vrnimo se k naši specifikacije in videli, kaj sledi.

602
00:48:04,470 --> 00:48:07,990
Zdaj pa želi dodati nekaj več vozlišč za naše drevo.

603
00:48:07,990 --> 00:48:11,690
To želi dodati 5, 2 in 8 in se prepričajte, da se naše vsebuje kodo

604
00:48:11,690 --> 00:48:13,570
še vedno deluje, kot je bilo pričakovano.

605
00:48:13,570 --> 00:48:14,900
Gremo narediti.

606
00:48:14,900 --> 00:48:19,430
Na tej točki, ne pa delaš da je siten kopiraj in prilepi še enkrat,

607
00:48:19,430 --> 00:48:23,770
dajmo napisati funkcijo, da dejansko ustvarite vozlišče.

608
00:48:23,770 --> 00:48:27,740
Če smo se pomaknite navzdol, vse do glavnega vidimo, da smo počeli to

609
00:48:27,740 --> 00:48:31,210
zelo podobna oznaka znova in znova, vsakič, da želimo ustvariti vozlišče.

610
00:48:31,210 --> 00:48:39,540
>> Naj napisati funkcijo, ki bo dejansko izgradnjo vozlišče za nas in ga vrniti.

611
00:48:39,540 --> 00:48:41,960
Jaz grem, da ga pokličete build_node.

612
00:48:41,960 --> 00:48:45,130
Jaz bom za izgradnjo vozlišče z določeno vrednostjo.

613
00:48:45,130 --> 00:48:51,040
Povečajte tukaj.

614
00:48:51,040 --> 00:48:56,600
Prva stvar, ki jo bom naredil je dejansko ustvariti prostor za vozlišče na kup.

615
00:48:56,600 --> 00:49:05,400
Torej, vozlišče * n = malloc (sizeof (vozlišče)); n -> vrednost = vrednost;

616
00:49:05,400 --> 00:49:14,960
in potem je tu, bom samo za inicializacijo vseh področjih, ki so ustrezne vrednosti.

617
00:49:14,960 --> 00:49:22,500
In čisto na koncu, bomo vrnili naše vozlišče.

618
00:49:22,500 --> 00:49:28,690
V redu. Ena stvar je tudi omeniti, da te funkcije tukaj

619
00:49:28,690 --> 00:49:34,320
vrača kazalec v spomin, da je bil kup dodeljena.

620
00:49:34,320 --> 00:49:38,880
Kaj je lepo o tem, da je ta vozel zdaj -

621
00:49:38,880 --> 00:49:42,420
moramo jo razglaša za na kup, ker če ga razglasi na kupu

622
00:49:42,420 --> 00:49:45,050
ne bi mogli storiti v tej funkciji, kot je ta.

623
00:49:45,050 --> 00:49:47,690
Ta spomin bi šel iz področja

624
00:49:47,690 --> 00:49:51,590
in bi bila neveljavna, če smo želeli priti do njih kasneje.

625
00:49:51,590 --> 00:49:53,500
Ker smo o razglasitvi kup-dodeljenega pomnilnika,

626
00:49:53,500 --> 00:49:55,830
bomo morali skrbeti za njeno osvoboditev kasneje

627
00:49:55,830 --> 00:49:58,530
za naš program, da ne pušča nobenega spomina.

628
00:49:58,530 --> 00:50:01,270
Smo bili punting na to, za vse ostalo v kodeksu

629
00:50:01,270 --> 00:50:02,880
samo zaradi enostavnosti je v času,

630
00:50:02,880 --> 00:50:05,610
ampak, če ste kdaj napisali funkcijo, ki je videti takole

631
00:50:05,610 --> 00:50:10,370
če imaš - nekateri pravijo malloc ali realloc znotraj -

632
00:50:10,370 --> 00:50:14,330
želite poskrbite, da boste dal neke vrste komentar tu gor, ki pravi,

633
00:50:14,330 --> 00:50:29,970
hej, saj veš, vrne kup dodeljena vozlišče initialized z spregledanih-vrednosti.

634
00:50:29,970 --> 00:50:33,600
In potem si želim, da poskrbite, da boste dal v neke vrste opomba, ki pravi:

635
00:50:33,600 --> 00:50:41,720
kličoči mora osvoboditi vrnil spomin.

636
00:50:41,720 --> 00:50:45,450
Na ta način, če bi kdo kdaj gre in uporablja to funkcijo,

637
00:50:45,450 --> 00:50:48,150
vedo, da vse, kar dobijo nazaj od te funkcije

638
00:50:48,150 --> 00:50:50,870
na neki točki bo treba rešiti.

639
00:50:50,870 --> 00:50:53,940
>> Ob predpostavki, da je vse lepo in prav tukaj,

640
00:50:53,940 --> 00:51:02,300
lahko gremo dol v našo kodo in zamenjavo vseh teh vrstic tukaj

641
00:51:02,300 --> 00:51:05,410
s klici na naše delovanje vozlišč izdelave.

642
00:51:05,410 --> 00:51:08,170
Naredimo to zelo hitro.

643
00:51:08,170 --> 00:51:15,840
En del, da mi ne bo nadomestil, je ta del tukaj

644
00:51:15,840 --> 00:51:18,520
na dnu, kjer smo dejansko vodnika do vozlišča s točko med seboj,

645
00:51:18,520 --> 00:51:21,030
ker to ne moremo narediti v našem delovanju.

646
00:51:21,030 --> 00:51:37,400
Ampak, kaj je naredil root = build_node (7), vozlišče * 3 = build_node (3);

647
00:51:37,400 --> 00:51:47,980
vozlišče * 6 = build_node (6), vozlišče * 9 = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
In zdaj smo želeli dodati vozlišča za -

649
00:51:52,590 --> 00:52:03,530
vozlišče * 5 = build_node (5); vozlišče * 8 = build_node (8);

650
00:52:03,530 --> 00:52:09,760
in kakšen je bil drugi vozel? Naj ogledate tukaj. Želeli smo, da dodate tudi 2 -

651
00:52:09,760 --> 00:52:20,280
vozlišče * 2 = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
V redu. Na tej točki smo vedeli, da smo dobili 7, 3, je 9, in 6

653
00:52:26,850 --> 00:52:30,320
vse žično gor pravilno, ampak kaj pa 5, 8, in 2?

654
00:52:30,320 --> 00:52:33,550
Če želite ohraniti vse, kar je v ustreznem vrstnem redu,

655
00:52:33,550 --> 00:52:39,230
vemo, da je pravica otroka 3 je 6.

656
00:52:39,230 --> 00:52:40,890
Torej, če bomo dodali 5,

657
00:52:40,890 --> 00:52:46,670
5 pripada tudi na desni strani drevesa, ki 3 je korenina,

658
00:52:46,670 --> 00:52:50,440
5 tako pripada tudi levi otroka 6.

659
00:52:50,440 --> 00:52:58,650
To lahko storimo z besedami, 6 -> left_child = 5;

660
00:52:58,650 --> 00:53:10,790
in nato 8 pripada tudi levi otroka 9, tako 9 -> left_child = 8;

661
00:53:10,790 --> 00:53:22,190
in potem 2 je na levi otrok 3, tako da lahko storimo, da tu - tebi -> left_child = 2;.

662
00:53:22,190 --> 00:53:27,730
Če niste povsem slediti skupaj s tem, predlagam, da ga potegnili sami.

663
00:53:27,730 --> 00:53:35,660
>> V redu. Rešimo to. Gremo ven in se prepričajte, da zbira,

664
00:53:35,660 --> 00:53:40,760
in potem bomo lahko dodali v naših vsebuje klice.

665
00:53:40,760 --> 00:53:44,120
Izgleda, da je vse še pripravlja.

666
00:53:44,120 --> 00:53:51,790
Pojdimo in dodate v nekaterih vsebuje klice.

667
00:53:51,790 --> 00:53:59,640
Spet bom naredil malo kopiraj in prilepi.

668
00:53:59,640 --> 00:54:15,860
Zdaj Poiščimo 5, 8 in 2. V redu.

669
00:54:15,860 --> 00:54:28,330
Naj se prepričajte, da to izgleda vse v redu vedno. Čudovito! Shrani in zapri.

670
00:54:28,330 --> 00:54:33,220
Zdaj pa, da pripravi, in zdaj gremo teči.

671
00:54:33,220 --> 00:54:37,540
Iz rezultatov, izgleda, da vse deluje samo lepo in dobro.

672
00:54:37,540 --> 00:54:41,780
Čudovito! Torej, zdaj imamo naše Vsebuje funkcija napisana.

673
00:54:41,780 --> 00:54:46,160
Gremo naprej in začeli delati na tem, kako vstaviti vozlišča v drevesu

674
00:54:46,160 --> 00:54:50,000
saj, kot smo to počeli zdaj, stvari niso zelo lepa.

675
00:54:50,000 --> 00:54:52,280
>> Če se vrnemo k specifikaciji,

676
00:54:52,280 --> 00:55:00,540
nas zahteva, da napišete funkcijo imenovano vstavite - spet vrača int

677
00:55:00,540 --> 00:55:04,400
za to, ali bi lahko dejansko vstavite vozlišče v drevesu -

678
00:55:04,400 --> 00:55:07,710
in potem je vrednost, ki jo vstavite v drevo, kot je določeno

679
00:55:07,710 --> 00:55:11,060
edini argument za naše vstaviti funkcijo.

680
00:55:11,060 --> 00:55:18,180
Vrnili se bomo res, če bi lahko dejansko vstavite vozlišča, ki vsebuje vrednost v drevo,

681
00:55:18,180 --> 00:55:20,930
kar pomeni, da je eden je imel dovolj spomina,

682
00:55:20,930 --> 00:55:24,840
nato pa dve, da se vozlišče ne obstaja že od drevesa -

683
00:55:24,840 --> 00:55:32,170
Zapomnite si, da mi ne dogaja, da imajo podvojene vrednosti v drevesu, le da bi stvari poenostavili.

684
00:55:32,170 --> 00:55:35,590
V redu. Nazaj na kodo.

685
00:55:35,590 --> 00:55:44,240
Odpri. Povečaj malo, nato pa se pomaknite navzdol.

686
00:55:44,240 --> 00:55:47,220
Naj je dal vstaviti funkcijo, tik nad vsebuje.

687
00:55:47,220 --> 00:55:56,360
Spet se dogaja, da se imenuje bool vstavi (int vrednost).

688
00:55:56,360 --> 00:56:01,840
Daj mu malo več prostora, in nato, kot privzeto

689
00:56:01,840 --> 00:56:08,870
kaj je dal v zameno lažno čisto na koncu.

690
00:56:08,870 --> 00:56:22,620
Zdaj pa dol na dnu, gremo naprej in namesto ročno gradnjo vozlišč

691
00:56:22,620 --> 00:56:27,900
v glavnem sami in jih žice do točke med seboj, kot delamo,

692
00:56:27,900 --> 00:56:30,600
bomo zanesti na vstaviti funkcijo za to.

693
00:56:30,600 --> 00:56:35,510
Ne bomo se zanesete na naše vstaviti funkcijo za izgradnjo celotno drevo iz nič še,

694
00:56:35,510 --> 00:56:39,970
ampak bomo znebili teh vrstic - Bomo zakomentirajte teh vrstic -

695
00:56:39,970 --> 00:56:43,430
ki gradijo vozlišča 5, 8 in 2.

696
00:56:43,430 --> 00:56:55,740
In namesto, bomo vstavite klicev na naš vstaviti funkcijo

697
00:56:55,740 --> 00:57:01,280
zagotoviti, da dejansko deluje.

698
00:57:01,280 --> 00:57:05,840
Pa gremo.

699
00:57:05,840 --> 00:57:09,300
>> Zdaj smo komentiral od teh vrstic.

700
00:57:09,300 --> 00:57:13,700
Imamo samo še 7, 3, 9, 6 in v našem drevesu na tej točki.

701
00:57:13,700 --> 00:57:18,870
Če se želite prepričati, da je to vse deluje,

702
00:57:18,870 --> 00:57:25,050
lahko pomanjšate, da bi naše binarno drevo,

703
00:57:25,050 --> 00:57:30,750
teči, in vidimo, da vsebuje zdaj nam govorijo, da smo popolnoma prav -

704
00:57:30,750 --> 00:57:33,110
5, 8 in 2 niso več v drevo.

705
00:57:33,110 --> 00:57:37,960
Pojdi nazaj v kodo,

706
00:57:37,960 --> 00:57:41,070
in kako se bomo vstaviti?

707
00:57:41,070 --> 00:57:46,290
Spomnite se, kaj smo naredili, ko smo dejansko vnašanje 5, 8 in 2 prej.

708
00:57:46,290 --> 00:57:50,100
Igrali smo to igro Plinko, kjer smo začeli na koren,

709
00:57:50,100 --> 00:57:52,780
znižala na drevesu enega po enega za

710
00:57:52,780 --> 00:57:54,980
dokler ne bomo našli ustrezno razliko,

711
00:57:54,980 --> 00:57:57,570
in potem žično v vozlišču na ustreznem mestu.

712
00:57:57,570 --> 00:57:59,480
Mi smo naredili isto stvar.

713
00:57:59,480 --> 00:58:04,070
To je v bistvu kot pisno kodo, ki smo jo uporabili, vsebuje funkcijo

714
00:58:04,070 --> 00:58:05,910
da bi našli mesto, kjer bi morala biti vozlišče,

715
00:58:05,910 --> 00:58:10,560
in potem greš samo vstaviti vozlišče tam.

716
00:58:10,560 --> 00:58:17,000
Začnimo s tem.

717
00:58:17,000 --> 00:58:24,200
>> Torej imamo vozlišče * tren = root, da greš samo slediti vsebuje kodo

718
00:58:24,200 --> 00:58:26,850
dokler ne bomo ugotovili, da ni čisto delo za nas.

719
00:58:26,850 --> 00:58:32,390
Mi smo šli skozi drevo, medtem ko je trenutna element ni nič,

720
00:58:32,390 --> 00:58:45,280
in če bomo ugotovili, da je tren vrednost je enaka vrednosti, ki smo ga poskušate vstaviti -

721
00:58:45,280 --> 00:58:49,600
Tudi to je eden od primerov, v katerih ne moremo dejansko vstaviti vozlišče

722
00:58:49,600 --> 00:58:52,730
v drevo, ker to pomeni, da imamo podvojeno vrednost.

723
00:58:52,730 --> 00:58:59,010
Tu smo dejansko dogaja, da vrne false.

724
00:58:59,010 --> 00:59:08,440
Zdaj pa, če je tren vrednost nižja od vrednosti,

725
00:59:08,440 --> 00:59:10,930
Zdaj vemo, da se premaknete na desno

726
00:59:10,930 --> 00:59:17,190
 ker je vrednost spada v desni polovici tren drevesa.

727
00:59:17,190 --> 00:59:30,110
V nasprotnem primeru bomo premakniti na levo.

728
00:59:30,110 --> 00:59:37,980
To je v bistvu naša Vsebuje deluje tam.

729
00:59:37,980 --> 00:59:41,820
>> Na tej točki, ko bomo končali to while zanko,

730
00:59:41,820 --> 00:59:47,350
naš tren kazalec se bo obrnjena na null

731
00:59:47,350 --> 00:59:51,540
Če je funkcija še ni vrnil.

732
00:59:51,540 --> 00:59:58,710
Mi smo zato ob CUR na mestu, kjer želite vstaviti novo vozlišče.

733
00:59:58,710 --> 01:00:05,210
Kaj je še treba storiti, je dejansko izgradnjo novega vozlišča

734
01:00:05,210 --> 01:00:08,480
kar lahko naredimo zelo enostavno.

735
01:00:08,480 --> 01:00:14,930
Mi lahko uporabite našo izjemno priročen graditi vozlišča funkcijo,

736
01:00:14,930 --> 01:00:17,210
in nekaj, kar nismo storili že prej -

737
01:00:17,210 --> 01:00:21,400
sva nekako vzel za samoumevno, zdaj pa bomo storili šele prepričati -

738
01:00:21,400 --> 01:00:27,130
bomo test, da se prepričajte, da je vrednost vrnil z novo vozlišče je bilo dejansko

739
01:00:27,130 --> 01:00:33,410
ni nič, ker ne želimo začeti do teh spomin, če je nična.

740
01:00:33,410 --> 01:00:39,910
Mi lahko test, da se prepriča, da je novo vozlišče ni enaka null.

741
01:00:39,910 --> 01:00:42,910
Ali pa namesto tega smo lahko videli, če je v resnici nič,

742
01:00:42,910 --> 01:00:52,120
in če je nična, potem lahko samo vrne false zgodaj.

743
01:00:52,120 --> 01:00:59,090
>> Na tej točki moramo žice novo vozlišče v svoje ustrezno mesto v drevesu.

744
01:00:59,090 --> 01:01:03,510
Če se ozremo nazaj na glavno in kje smo dejansko napeljava vrednosti pred

745
01:01:03,510 --> 01:01:08,470
vidimo, da je način, kako so to počeli, ko smo želeli postaviti 3 v drevo

746
01:01:08,470 --> 01:01:11,750
mi je bila naložena na levi otroka korenine.

747
01:01:11,750 --> 01:01:14,920
Ko smo se 9 na drevesu, smo imeli dostop do pravega otroka korena.

748
01:01:14,920 --> 01:01:21,030
Morali smo se kazalec na starša, da bi dal novo vrednost v drevo.

749
01:01:21,030 --> 01:01:24,430
Pomikanje nazaj vstaviti, da to ne bo delovalo čisto tukaj

750
01:01:24,430 --> 01:01:27,550
ker nimamo matično kazalec.

751
01:01:27,550 --> 01:01:31,650
Kaj želimo biti sposoben narediti je, da na tej točki,

752
01:01:31,650 --> 01:01:37,080
preverite staršev vrednosti in videti - no, bog,

753
01:01:37,080 --> 01:01:41,990
Če eden od staršev je vrednost nižja od trenutne vrednosti,

754
01:01:41,990 --> 01:01:54,440
potem bi obvladujočega pravica otrok je novo vozlišče;

755
01:01:54,440 --> 01:02:07,280
drugače, bi morala starša levo otrok bo novo vozlišče.

756
01:02:07,280 --> 01:02:10,290
Ampak, nimamo to matično kazalec še.

757
01:02:10,290 --> 01:02:15,010
>> Da bi jo dobili, smo dejansko dogaja, da so ga spremljali, ko gremo skozi drevesa

758
01:02:15,010 --> 01:02:18,440
in najti ustrezno mesto v našem zanke zgoraj.

759
01:02:18,440 --> 01:02:26,840
Mi lahko storite, da se premaknete nazaj na vrh našega vstaviti funkcijo

760
01:02:26,840 --> 01:02:32,350
in sledenje drug kazalec spremenljivka se imenuje staršev.

761
01:02:32,350 --> 01:02:39,340
Bomo ga postavi na začetku null,

762
01:02:39,340 --> 01:02:43,640
in nato vsakič, ko gremo skozi drevesa,

763
01:02:43,640 --> 01:02:51,540
bomo nastavili matično kazalec, da se ujema trenutni kazalec.

764
01:02:51,540 --> 01:02:59,140
Nastavite od staršev, ki je enaka cur.

765
01:02:59,140 --> 01:03:02,260
Tako vsakič, ko gremo skozi,

766
01:03:02,260 --> 01:03:05,550
bomo zagotovili, da se sedanji kazalec postane poveča

767
01:03:05,550 --> 01:03:12,640
osnovni kazalec ji sledi - le ena stopnja višja od trenutne kazalca v drevesu.

768
01:03:12,640 --> 01:03:17,370
To je vse izgleda precej dobro.

769
01:03:17,370 --> 01:03:22,380
>> Mislim, da je ena stvar, ki jo bomo želeli prilagoditi, je to zgraditi vozlišče vrača null.

770
01:03:22,380 --> 01:03:25,380
Da bi dobili zgraditi vozlišče, dejansko uspešno vrne null,

771
01:03:25,380 --> 01:03:31,060
bomo morali spremeniti to kodo,

772
01:03:31,060 --> 01:03:37,270
ker tukaj ne bomo nikoli preizkušeni prepričati, da se vrne malloc veljaven kazalec.

773
01:03:37,270 --> 01:03:53,390
Torej, če (n = NIČ!), Nato pa -

774
01:03:53,390 --> 01:03:55,250
če malloc vrne veljaven kazalec, nato pa ga bomo zagnati;

775
01:03:55,250 --> 01:04:02,540
sicer pa bova vrnili in da bo na koncu vrne null za nas.

776
01:04:02,540 --> 01:04:13,050
Zdaj vse izgleda precej dobro. Naj se prepričajte, to dejansko ureja.

777
01:04:13,050 --> 01:04:22,240
Naredite binarno drevo, in oh, imamo nekaj stvari se dogaja tukaj.

778
01:04:22,240 --> 01:04:29,230
>> Imamo implicitno izjavo o delovanju zgraditi vozlišče.

779
01:04:29,230 --> 01:04:31,950
Spet s temi prevajalniki, bomo začeli na vrhu.

780
01:04:31,950 --> 01:04:36,380
Kaj, da je treba reči, da kličem zgraditi vozlišče, preden sem dejansko prijavljeni.

781
01:04:36,380 --> 01:04:37,730
Pojdimo nazaj na oznako res hitro.

782
01:04:37,730 --> 01:04:43,510
Pomaknite se navzdol, in gotovo se razglasi za moje vstaviti funkcijo

783
01:04:43,510 --> 01:04:47,400
nad delovanjem gradnje vozlišča,

784
01:04:47,400 --> 01:04:50,070
vendar sem poskušal uporabiti zgraditi vozlišče znotraj vložka.

785
01:04:50,070 --> 01:05:06,610
Jaz grem v in kopije - in ga prilepite funkcije vozlišča graditi sem gor na vrhu.

786
01:05:06,610 --> 01:05:11,750
Tako, upam, da bo delovalo. Dajmo to še gre.

787
01:05:11,750 --> 01:05:18,920
Zdaj je vse pripravlja. Vse je v redu.

788
01:05:18,920 --> 01:05:21,640
>> Toda na tej točki, ki smo jih dejansko ni pozval naše vstaviti funkcijo.

789
01:05:21,640 --> 01:05:26,510
Vemo samo, da se pripravlja, da gremo v in dal nekaj klicev noter

790
01:05:26,510 --> 01:05:28,240
Naredimo to v naši glavni funkciji.

791
01:05:28,240 --> 01:05:32,390
Tu smo navedli od 5, 8 in 2,

792
01:05:32,390 --> 01:05:36,680
in potem jih nismo žice gor dol.

793
01:05:36,680 --> 01:05:41,640
Naredimo nekaj pozivov za vnos,

794
01:05:41,640 --> 01:05:46,440
in kaj je prav tako uporabiti isto vrsto stvari, ki smo jo uporabili

795
01:05:46,440 --> 01:05:52,810
ko smo te printf klicev se prepričajte, da ni vse, kar se pravilno vstavljen.

796
01:05:52,810 --> 01:06:00,550
Grem kopiranje in lepljenje,

797
01:06:00,550 --> 01:06:12,450
in namesto vsebuje bomo narediti vložek.

798
01:06:12,450 --> 01:06:30,140
In namesto, 6, 10 in 1, gremo uporabiti 5, 8 in 2.

799
01:06:30,140 --> 01:06:37,320
To naj bi, upajmo, vstavite 5, 8 in 2 v drevo.

800
01:06:37,320 --> 01:06:44,050
Prevesti. Vse je v redu. Zdaj bomo dejansko vodijo naš program.

801
01:06:44,050 --> 01:06:47,330
>> Vse se vrne false.

802
01:06:47,330 --> 01:06:53,830
Torej, 5, 8 in 2 ni šel, in izgleda, da Contains jih niso našli niti.

803
01:06:53,830 --> 01:06:58,890
Kaj se dogaja? Naj pomanjšati.

804
01:06:58,890 --> 01:07:02,160
Prvi problem je bil, da je zdelo, da vložek vrne false,

805
01:07:02,160 --> 01:07:08,750
in izgleda, da je to zato, ker smo pustili v naši vrnitvi lažni klic,

806
01:07:08,750 --> 01:07:14,590
in mi nikoli dejansko vrnil res.

807
01:07:14,590 --> 01:07:17,880
Mi lahko nastavite, da gor.

808
01:07:17,880 --> 01:07:25,290
Drugi problem je, zdaj tudi če delamo - razen tega, zaprete tako,

809
01:07:25,290 --> 01:07:34,530
Naklada bo spet moralo zbrati, nato pa ga teči -

810
01:07:34,530 --> 01:07:37,670
vidimo, da je nekaj drugega se je zgodilo.

811
01:07:37,670 --> 01:07:42,980
Za 5, 8, in 2 sta bili še nikoli našli v drevo.

812
01:07:42,980 --> 01:07:44,350
Torej, kaj se dogaja?

813
01:07:44,350 --> 01:07:45,700
>> Oglejmo si to v kodi.

814
01:07:45,700 --> 01:07:49,790
Poglejmo, če lahko to ugotovite.

815
01:07:49,790 --> 01:07:57,940
Začeli smo s starši niso nič.

816
01:07:57,940 --> 01:07:59,510
Postavili smo trenutno kazalec, ki je enak koren kazalcem

817
01:07:59,510 --> 01:08:04,280
in da bomo naš način dela, navzdol po drevesu.

818
01:08:04,280 --> 01:08:08,650
Če je trenutno vozlišče ni nič, potem vemo, da lahko gremo dol malo.

819
01:08:08,650 --> 01:08:12,330
Mi je naša matično kazalec, da je enaka trenutni kazalec,

820
01:08:12,330 --> 01:08:15,420
preverila vrednost - če sta vrednosti enaki smo se vrnili napačen.

821
01:08:15,420 --> 01:08:17,540
Če so vrednosti manj smo se preselili na desno;

822
01:08:17,540 --> 01:08:20,399
sicer pa smo se preselili v levo.

823
01:08:20,399 --> 01:08:24,220
Potem smo zgradili vozlišče. Jaz bom povečate malo.

824
01:08:24,220 --> 01:08:31,410
In tukaj bomo poskušali žice do vrednosti, ki je enaka.

825
01:08:31,410 --> 01:08:37,250
Kaj se dogaja? Bomo videli, če morda lahko Valgrind nam namig.

826
01:08:37,250 --> 01:08:43,910
>> Rad uporabljam Valgrind samo zato, ker res hitro teče Valgrind

827
01:08:43,910 --> 01:08:46,729
in vam pove, če obstajajo kakršne koli napake pomnilnika.

828
01:08:46,729 --> 01:08:48,300
Ko smo teči Valgrind na oznako,

829
01:08:48,300 --> 01:08:55,859
Kot lahko vidite desno here--Valgrind./binary_tree--and zadeti nastopiti.

830
01:08:55,859 --> 01:09:03,640
Vidiš, da nismo imeli nobene napake pomnilnika, tako da izgleda kot da je vse v redu doslej.

831
01:09:03,640 --> 01:09:07,529
Imamo nekaj spomin razpoka, ki jih poznamo, ker nismo

832
01:09:07,529 --> 01:09:08,910
dogaja se osvobodi vseh naših vozlišč.

833
01:09:08,910 --> 01:09:13,050
Poskusimo teče GDB, da vidim, kaj se dejansko dogaja.

834
01:09:13,050 --> 01:09:20,010
Naredili bomo gdb. / Binary_tree. To zažene v redu.

835
01:09:20,010 --> 01:09:23,670
Naj določi odmor točko na vložek.

836
01:09:23,670 --> 01:09:28,600
Naj teče.

837
01:09:28,600 --> 01:09:31,200
Izgleda, da ne bomo nikoli pravzaprav imenuje vložek.

838
01:09:31,200 --> 01:09:39,410
Izgleda, da je problem samo, da ko sem spremenil tukaj v glavnem -

839
01:09:39,410 --> 01:09:44,279
Vse te printf klice iz vsebuje -

840
01:09:44,279 --> 01:09:56,430
Nikoli nisem spremenila te poklicati vložek.

841
01:09:56,430 --> 01:10:01,660
Zdaj pa, da ga poskusite. Naj pripravijo.

842
01:10:01,660 --> 01:10:09,130
Vse zgleda v redu tam. Zdaj pa poskusimo to izvaja, kaj se bo zgodilo.

843
01:10:09,130 --> 01:10:13,320
V redu! Vse, kar izgleda precej dobro tam.

844
01:10:13,320 --> 01:10:18,130
>> Zadnja stvar, da razmišljajo o je, ali obstajajo kakršne koli roba primeri tega vložka?

845
01:10:18,130 --> 01:10:23,170
In izkazalo se je, da je dobro, ena stranica primer, da je vedno zanimivo, da razmišljajo o

846
01:10:23,170 --> 01:10:26,250
je, kaj se zgodi, če je vaš drevo je prazna in jo imenujemo vstaviti funkcijo?

847
01:10:26,250 --> 01:10:30,330
Bo to delovalo? No, dajmo poskusiti.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Tako bomo testirali je, da smo šli do naše glavne funkcije,

850
01:10:35,810 --> 01:10:41,690
in namesto kablov te vozle up, kot je ta,

851
01:10:41,690 --> 01:10:56,730
smo le, da bo zakomentirajte celotno stvar,

852
01:10:56,730 --> 01:11:02,620
in namesto napeljave do vozlišča sebe,

853
01:11:02,620 --> 01:11:09,400
lahko dejansko samo pojdi naprej in izbrisati vse to.

854
01:11:09,400 --> 01:11:17,560
Bomo narediti vse, kar je klic za vstavljanje.

855
01:11:17,560 --> 01:11:49,020
Torej, kaj je to - namesto 5, 8 in 2, se bomo, da vstavite 7, 3, 9.

856
01:11:49,020 --> 01:11:58,440
In potem bomo tudi želite vstaviti 6, kot tudi.

857
01:11:58,440 --> 01:12:05,190
Shrani. Končaj. Naredite binarno drevo.

858
01:12:05,190 --> 01:12:08,540
Vse pripravlja.

859
01:12:08,540 --> 01:12:10,320
Mi lahko samo teče, kot je bilo, in videli, kaj se zgodi,

860
01:12:10,320 --> 01:12:12,770
a prav tako bo zelo pomembno, da poskrbite, da

861
01:12:12,770 --> 01:12:14,740
nimamo nobenih spomin napak,

862
01:12:14,740 --> 01:12:16,840
ker je to ena od naših robnih primerov, da vemo o tem.

863
01:12:16,840 --> 01:12:20,150
>> Naj se prepričajte, da dobro deluje v okviru Valgrind,

864
01:12:20,150 --> 01:12:28,310
kar bomo storili s samo vožnjo Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Izgleda, da smo res en napake iz enega konteksta -

866
01:12:31,110 --> 01:12:33,790
imamo to Napaka pri razčlenjenosti.

867
01:12:33,790 --> 01:12:36,690
Kaj se je zgodilo?

868
01:12:36,690 --> 01:12:41,650
Valgrind dejansko ne pove, kje je.

869
01:12:41,650 --> 01:12:43,050
Pomanjšajte malo.

870
01:12:43,050 --> 01:12:46,040
Videti je, da se to dogaja v naši vstaviti funkcijo,

871
01:12:46,040 --> 01:12:53,420
kjer imamo napačno branje velikosti 4 na vložek, linija 60.

872
01:12:53,420 --> 01:13:03,590
Pojdimo nazaj in videli, kaj se dogaja tukaj.

873
01:13:03,590 --> 01:13:05,350
Pomanjšajte res hitro.

874
01:13:05,350 --> 01:13:14,230
Želim, da se prepriča, da ne gre na rob zaslona, ​​tako da lahko vidimo vse.

875
01:13:14,230 --> 01:13:18,760
Povlecite, da v malo. V redu.

876
01:13:18,760 --> 01:13:35,030
Pomaknite se navzdol in problem je tukaj.

877
01:13:35,030 --> 01:13:40,120
Kaj se zgodi, če bomo dol in naš sedanji vozlišče je že null,

878
01:13:40,120 --> 01:13:44,010
naša matična vozlišče nič, tako da, če pogledamo gor na vrhu, prav tukaj -

879
01:13:44,010 --> 01:13:47,340
če je to, medtem ko zanke nikoli dejansko izvaja

880
01:13:47,340 --> 01:13:52,330
ker naša trenutna vrednost nič - naša root je nična, tako tren ničelna -

881
01:13:52,330 --> 01:13:57,810
nato pa nas nikoli ne postane nadrejena naj bi cur ali veljavno vrednostjo,

882
01:13:57,810 --> 01:14:00,580
Tako bodo starši prav tako nična.

883
01:14:00,580 --> 01:14:03,700
Moramo se spomniti, da preverite, da

884
01:14:03,700 --> 01:14:08,750
do takrat, ko bomo prišli tja, in smo začeli dostop do strani staršev vrednost.

885
01:14:08,750 --> 01:14:13,190
Torej, kaj se zgodi? No, če je eden od staršev nič -

886
01:14:13,190 --> 01:14:17,990
če (matično == NULL) -, potem vemo, da

887
01:14:17,990 --> 01:14:19,530
pa ne sme biti nič v drevo.

888
01:14:19,530 --> 01:14:22,030
Moramo se poskuša, da ga vstavite v korenu.

889
01:14:22,030 --> 01:14:32,570
To lahko storimo le za določitev osnovnih enak novo vozlišče.

890
01:14:32,570 --> 01:14:40,010
Nato v tem trenutku pravzaprav ne želim iti skozi te druge stvari.

891
01:14:40,010 --> 01:14:44,780
Namesto, tukaj, lahko naredimo bodisi drugod po-drugega,

892
01:14:44,780 --> 01:14:47,610
ali lahko združimo vse, kar je tukaj v drugega,

893
01:14:47,610 --> 01:14:56,300
ampak tukaj bomo samo uporabo drugje in ne v to smer.

894
01:14:56,300 --> 01:14:59,030
Zdaj bomo test, da se prepričajte, da je naša matična ni nič

895
01:14:59,030 --> 01:15:02,160
pred tem se dejansko poskuša dostopati do svojih polj.

896
01:15:02,160 --> 01:15:05,330
To nam bo pomagalo preprečiti segmentacijo napake.

897
01:15:05,330 --> 01:15:14,740
Torej, smo nehal, pomanjšanje zbrati, teci.

898
01:15:14,740 --> 01:15:18,130
>> Ni napak, vendar smo še vedno imeli kup spomin razpoka

899
01:15:18,130 --> 01:15:20,650
ker nismo osvobodi vseh naših vozlišč.

900
01:15:20,650 --> 01:15:24,350
Ampak, če gremo gor in se ozremo na naše izpisa,

901
01:15:24,350 --> 01:15:30,880
vidimo, da je dobro, izgleda, da so vsi naši vložki so vračanje res, kar je dobro.

902
01:15:30,880 --> 01:15:33,050
Vložki so vse res,

903
01:15:33,050 --> 01:15:36,670
in nato ustrezne vsebuje klice tudi res.

904
01:15:36,670 --> 01:15:41,510
>> Dobro opravljeno! Izgleda, da smo uspešno pisno navodilo.

905
01:15:41,510 --> 01:15:47,430
To je vse, kar imamo za specifikacijo ta teden Problem Set.

906
01:15:47,430 --> 01:15:51,720
En zabaven izziv, da razmišljajo o tem, kako bi dejansko šel v

907
01:15:51,720 --> 01:15:55,340
in brez vseh vozlišč v tem drevesu.

908
01:15:55,340 --> 01:15:58,830
Mi lahko to stori več različnih načinov,

909
01:15:58,830 --> 01:16:01,930
ampak bom pustil, da je do vas, da eksperimentirate,

910
01:16:01,930 --> 01:16:06,080
in kot zabaven izziv, poskusite in se prepričajte, da ste lahko prepričani,

911
01:16:06,080 --> 01:16:09,490
V tem poročilu Valgrind ne vrne napake in ne pušča.

912
01:16:09,490 --> 01:16:12,880
>> Vso srečo na Huffman ta teden kodiranje nabora problemov,

913
01:16:12,880 --> 01:16:14,380
in se vidimo naslednji teden!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]