1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Odjeljak 7] [Manje Ugodno]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Sveučilište Harvard]

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

4
00:00:07,000 --> 00:00:09,080
>> Dobrodošli na odsjeku sedam.

5
00:00:09,080 --> 00:00:11,330
Zahvaljujući uragan Sandy

6
00:00:11,330 --> 00:00:13,440
umjesto da normalan dio ovaj tjedan,

7
00:00:13,440 --> 00:00:17,650
radimo to prolazna, kroz dio pitanja.

8
00:00:17,650 --> 00:00:22,830
Ja ću biti sljedeće zajedno s problemom Set 6 Specifikacija,

9
00:00:22,830 --> 00:00:25,650
i prolazi kroz sva pitanja u

10
00:00:25,650 --> 00:00:27,770
Odsjek Pitanja dijelu.

11
00:00:27,770 --> 00:00:30,940
Ako postoje bilo kakva pitanja,

12
00:00:30,940 --> 00:00:32,960
molimo objaviti na CS50 raspravljati.

13
00:00:32,960 --> 00:00:35,480
>> Dobro,. Počnimo.

14
00:00:35,480 --> 00:00:40,780
Trenutno sam u potrazi na stranici 3. specifikacija problema Set.

15
00:00:40,780 --> 00:00:44,110
Idemo prvo početi govoriti o binarnih stabala

16
00:00:44,110 --> 00:00:47,850
od onih koji imaju puno važnosti za ovotjednom problema setu -

17
00:00:47,850 --> 00:00:49,950
kodiranje Huffman stablo.

18
00:00:49,950 --> 00:00:55,000
Jedan od prvih struktura podataka razgovarali smo o na CS50 je niz.

19
00:00:55,000 --> 00:01:00,170
Imajte na umu da je niz je niz elemenata -

20
00:01:00,170 --> 00:01:04,019
sve iste vrste - pohranjeni tik jedna do druge u memoriji.

21
00:01:04,019 --> 00:01:14,420
Ako imam cijeli niz koji sam može izvući koristi ovu kutije-brojevi-integers stil -

22
00:01:14,420 --> 00:01:20,290
Recimo imam 5 u prvom kutiji, imam sedam u drugom,

23
00:01:20,290 --> 00:01:27,760
onda sam 8, 10 i 20 u zadnjoj kutiji.

24
00:01:27,760 --> 00:01:33,000
Podsjetimo, dvije stvarno dobre stvari o tom obilju

25
00:01:33,000 --> 00:01:38,800
su da imamo ovu konstanta-time pristup bilo kojeg elementa

26
00:01:38,800 --> 00:01:40,500
 u nizu, ako znamo svoj indeks.

27
00:01:40,500 --> 00:01:44,670
Na primjer, ako želim da zgrabite treći element u nizu -

28
00:01:44,670 --> 00:01:47,870
na indeksu 2 pomoću naše nula-based indeksni sustav -

29
00:01:47,870 --> 00:01:52,220
Doslovno sam samo morati napraviti jednostavan matematički izračun,

30
00:01:52,220 --> 00:01:56,170
hop na toj poziciji u polju,

31
00:01:56,170 --> 00:01:57,840
izvucite 8 koja je tamo pohranjena,

32
00:01:57,840 --> 00:01:59,260
i ja sam dobar to ići.

33
00:01:59,260 --> 00:02:03,350
>> Jedna od loših stvari o tom obilju - da smo razgovarali o tome

34
00:02:03,350 --> 00:02:05,010
kada smo razgovarali vezane liste -

35
00:02:05,010 --> 00:02:09,120
je da ako želim umetnuti element u ovom nizu,

36
00:02:09,120 --> 00:02:11,090
Ja ću morati napraviti neke kreće oko.

37
00:02:11,090 --> 00:02:12,940
Na primjer, ovo polje ovdje

38
00:02:12,940 --> 00:02:16,850
je u sortiraju bi - sortirani uzlaznim redoslijedom -

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

40
00:02:19,440 --> 00:02:23,100
ali ako želim umetnuti broj 9 u ovom polju,

41
00:02:23,100 --> 00:02:27,460
Ja ću morati prebaciti neke od elemenata kako bi prostor.

42
00:02:27,460 --> 00:02:30,440
Možemo nacrtati ovo ovdje.

43
00:02:30,440 --> 00:02:35,650
Ja ću morati premjestiti 5, 7, i onda 8;

44
00:02:35,650 --> 00:02:38,720
stvoriti jaz gdje mogu staviti 9,

45
00:02:38,720 --> 00:02:45,910
i onda 10 i 20 može ići desno od devet.

46
00:02:45,910 --> 00:02:49,450
To je vrsta boli, jer u najgorem slučaju -

47
00:02:49,450 --> 00:02:54,350
kada imamo umetnuti bilo na početku ili na kraju

48
00:02:54,350 --> 00:02:56,040
od polja, ovisno o tome koliko smo kreće -

49
00:02:56,040 --> 00:02:58,850
možemo završiti s prebaciti sve elemente

50
00:02:58,850 --> 00:03:00,750
trenutno radimo na čuvanje u polju.

51
00:03:00,750 --> 00:03:03,810
>> Dakle, ono što je bio način oko ovoga?

52
00:03:03,810 --> 00:03:09,260
Način oko ovoga je da ide na naš linked-list metoda gdje -

53
00:03:09,260 --> 00:03:19,820
umjesto spremanja elemente 5, 7, 8, 10 i 20 sve pored drugoga u sjećanju -

54
00:03:19,820 --> 00:03:25,630
ono što smo umjesto toga nije bio pohraniti ih vrsta gdje god smo htjeli da ih pohraniti

55
00:03:25,630 --> 00:03:32,470
u tim povezana-popis čvorova koje crtam ovdje, kakav ad hoc.

56
00:03:32,470 --> 00:03:42,060
I onda smo ih spojiti zajedno pomoću ovih sljedećoj naputke.

57
00:03:42,060 --> 00:03:44,370
Mogu imati pokazivač od 5 do 7,

58
00:03:44,370 --> 00:03:46,420
pokazivač od 7. do 8,

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

60
00:03:47,770 --> 00:03:51,220
i na kraju, pokazivač od 10 do 20,

61
00:03:51,220 --> 00:03:54,880
i onda null pointer na 20 što pokazuje da nema ništa lijevo.

62
00:03:54,880 --> 00:03:59,690
Trgovinski-off koji imamo ovdje

63
00:03:59,690 --> 00:04:05,360
je da sada, ako želimo umetnuti broj 9 u našoj sortirati popis,

64
00:04:05,360 --> 00:04:08,270
sve što morate učiniti je stvoriti novi čvor s 9,

65
00:04:08,270 --> 00:04:12,290
ga spojiti do točke na odgovarajuće mjesto,

66
00:04:12,290 --> 00:04:20,630
a zatim ponovno žice 8 ukazati do 9.

67
00:04:20,630 --> 00:04:25,660
To je prilično brzo, pod pretpostavkom da znamo točno gdje želimo umetnuti devet.

68
00:04:25,660 --> 00:04:32,610
No, trade-off, u zamjenu za to da sada smo izgubili konstanta-time pristup

69
00:04:32,610 --> 00:04:36,230
za određeni element u našoj strukture podataka.

70
00:04:36,230 --> 00:04:40,950
Na primjer, ako želim pronaći četvrti element u ovom povezanom popisu,

71
00:04:40,950 --> 00:04:43,510
Ja ću morati početi na samom početku popisa

72
00:04:43,510 --> 00:04:48,930
i raditi svoj put kroz računajući čvor-by-čvor dok sam pronaći četvrti jednom.

73
00:04:48,930 --> 00:04:55,870
>> Kako bi dobili bolji pristup performanse od povezane liste -

74
00:04:55,870 --> 00:04:59,360
ali i zadržati neke od prednosti koje smo imali

75
00:04:59,360 --> 00:05:01,800
u smislu unosa vremenu iz povezane liste -

76
00:05:01,800 --> 00:05:05,750
binarno stablo će se morati koristiti malo više memorije.

77
00:05:05,750 --> 00:05:11,460
Konkretno, umjesto da samo imaju jedan pokazivač u binarnom stablu čvor -

78
00:05:11,460 --> 00:05:13,350
kao linked-liste čvor ne -

79
00:05:13,350 --> 00:05:16,950
idemo dodati drugi pokazivač binarnog stabla čvor.

80
00:05:16,950 --> 00:05:19,950
Umjesto da samo ima jedan pokazivač na sljedeći element,

81
00:05:19,950 --> 00:05:24,420
idemo imati pokazivač na lijevoj djeteta i pravo djeteta.

82
00:05:24,420 --> 00:05:26,560
>> Ajmo nacrtati sliku kako bi vidjeli što to zapravo izgleda.

83
00:05:26,560 --> 00:05:31,350
Opet, ja ću koristiti ove kutije i strijele.

84
00:05:31,350 --> 00:05:37,150
Binarno stablo čvor će krenuti sa samo jednostavnim kutiji.

85
00:05:37,150 --> 00:05:40,940
To će imati prostor za vrijednosti,

86
00:05:40,940 --> 00:05:47,280
i onda to također će imati prostora za lijevu djeteta i pravo djeteta.

87
00:05:47,280 --> 00:05:49,280
Ja ću ih označiti ovdje.

88
00:05:49,280 --> 00:05:57,560
Mi ćemo imati lijevu dijete, a onda ćemo imati pravo dijete.

89
00:05:57,560 --> 00:05:59,920
Postoji mnogo različitih načina ovo.

90
00:05:59,920 --> 00:06:02,050
Ponekad za prostor i praktičnost,

91
00:06:02,050 --> 00:06:06,460
Ja sam zapravo ću ga izvući kao radim ovdje na dnu

92
00:06:06,460 --> 00:06:10,910
gdje ću imati vrijednost na vrhu,

93
00:06:10,910 --> 00:06:14,060
i onda pravo djeteta na donjem desnom,

94
00:06:14,060 --> 00:06:16,060
i lijevo dijete na donjem lijevom.

95
00:06:16,060 --> 00:06:20,250
Vraćajući se ovom gornjem dijagramu,

96
00:06:20,250 --> 00:06:22,560
imamo vrijednost na samom vrhu,

97
00:06:22,560 --> 00:06:25,560
onda imamo lijevo-dijete pokazivač, a zatim imamo pravo-dijete pokazivač.

98
00:06:25,560 --> 00:06:30,110
>> U specifikaciji Problem Set,

99
00:06:30,110 --> 00:06:33,110
govorimo o izradi čvor koji ima vrijednost 7,

100
00:06:33,110 --> 00:06:39,750
i onda lijevo-dijete pokazivač da je nula, a desno dijete pokazivač koji je null.

101
00:06:39,750 --> 00:06:46,040
Mi može pisati kapitala NULL u prostoru za

102
00:06:46,040 --> 00:06:51,610
i lijevo dijete i pravo dijete, ili možemo izvući ovu dijagonale crtu

103
00:06:51,610 --> 00:06:53,750
kroz svaki od kutije pokazuju da je ništavan.

104
00:06:53,750 --> 00:06:57,560
Ja ću učiniti da samo zato što je jednostavnije.

105
00:06:57,560 --> 00:07:03,700
Ono što vidite ovdje su dva načina dijagrama vrlo jednostavan čvor binarnog stabla

106
00:07:03,700 --> 00:07:07,960
gdje imamo vrijednost 7 i null dijete upućuje.

107
00:07:07,960 --> 00:07:15,220
>> Drugi dio naših specifikacija razgovora o tome s povezanim listama -

108
00:07:15,220 --> 00:07:18,270
zapamtite, samo mi morali držati na prvi element u popisu

109
00:07:18,270 --> 00:07:20,270
zapamtiti cijeli popis -

110
00:07:20,270 --> 00:07:26,140
a isto tako, s binarno stablo, imamo samo držati na jednom pokazivač na stablu

111
00:07:26,140 --> 00:07:31,120
kako bi zadržali kontrolu nad cijelom strukturom podataka.

112
00:07:31,120 --> 00:07:36,150
Ova posebna element stabla se zove korijen čvor stabla.

113
00:07:36,150 --> 00:07:43,360
Na primjer, ako je to jedan čvor - to čvor koji sadrži vrijednost 7

114
00:07:43,360 --> 00:07:45,500
s null lijeve i desne pokazivače dijete -

115
00:07:45,500 --> 00:07:47,360
bili jedina vrijednost u našem stablu,

116
00:07:47,360 --> 00:07:50,390
onda će to biti naša čvor korijen.

117
00:07:50,390 --> 00:07:52,240
To je vrlo početak našeg stabla.

118
00:07:52,240 --> 00:07:58,530
Možemo vidjeti ovo malo jasnije kada ćemo početi dodavanjem više čvorova našem stablu.

119
00:07:58,530 --> 00:08:01,510
Dopustite mi podići novu stranicu.

120
00:08:01,510 --> 00:08:05,000
>> Sada ćemo izvući stablo koje ima sedam u korijenu,

121
00:08:05,000 --> 00:08:10,920
i 3 unutar lijevog djeteta, i 9 unutrašnju stranu desnog djeteta.

122
00:08:10,920 --> 00:08:13,500
Opet, to je prilično jednostavan.

123
00:08:13,500 --> 00:08:26,510
Imamo sedam, nacrtati čvor za tri, čvor za 9,

124
00:08:26,510 --> 00:08:32,150
i ja ću postaviti lijevo-dijete pokazivač od 7 do točke do čvora sadrži tri,

125
00:08:32,150 --> 00:08:37,850
i desno dijete pokazivač čvora sadrži sedam do čvora sadrži devet.

126
00:08:37,850 --> 00:08:42,419
Sada, budući da tri i devet nemaju djecu,

127
00:08:42,419 --> 00:08:48,500
idemo postaviti sve svoje dijete upućuje biti nula.

128
00:08:48,500 --> 00:08:56,060
Evo, korijen našeg stabla odgovara čvor koji sadrži broj 7.

129
00:08:56,060 --> 00:09:02,440
Možete vidjeti da ako je sve što imamo je pokazivač na taj čvor korijena,

130
00:09:02,440 --> 00:09:07,330
tada možemo prošetati kroz naš stabla i pristupiti oba djeteta čvorova -

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

132
00:09:10,630 --> 00:09:14,820
Nema potrebe za održavanje upućuje na svaki čvor na stablu.

133
00:09:14,820 --> 00:09:22,080
Dobro,. Sada ćemo dodati još jedan čvor na ovom dijagramu.

134
00:09:22,080 --> 00:09:25,370
Mi ćemo dodati čvor koji sadrži 6,

135
00:09:25,370 --> 00:09:34,140
a mi ćemo dodati to kao pravo dijete čvora sadrži tri.

136
00:09:34,140 --> 00:09:41,850
Da bi to učinili, ja ću izbrisati taj null pokazivač u 3-čvor

137
00:09:41,850 --> 00:09:47,750
i spojiti se ukazati na čvoru sadrži šest. Dobro,.

138
00:09:47,750 --> 00:09:53,800
>> U ovom trenutku, idemo preko malo terminologije.

139
00:09:53,800 --> 00:09:58,230
Za početak, razlog da se to zove binarno stablo posebice

140
00:09:58,230 --> 00:10:00,460
je da ima dva djeteta upućuje.

141
00:10:00,460 --> 00:10:06,020
Postoje i druge vrste drveća koje imaju više djece naputke.

142
00:10:06,020 --> 00:10:10,930
Konkretno, jesi 'probati' u problem Set 5.

143
00:10:10,930 --> 00:10:19,310
Primijetit ćete da je u tom pokušaju, što je 27 različitih upućuje na različite djece -

144
00:10:19,310 --> 00:10:22,410
jedan za svaki od 26 slova u engleske abecede,

145
00:10:22,410 --> 00:10:25,410
, a zatim 27. za apostrofa -

146
00:10:25,410 --> 00:10:28,900
tako, da je slična vrsti drveta.

147
00:10:28,900 --> 00:10:34,070
Ali ovdje, jer to je binarni, imamo samo dva djeteta upućuje.

148
00:10:34,070 --> 00:10:37,880
>> Osim toga korijen čvor koji smo govorili,

149
00:10:37,880 --> 00:10:41,470
mi smo također je bacio oko ovog pojma 'dijete'.

150
00:10:41,470 --> 00:10:44,470
Što to znači za jedan čvor da se dijete drugog čvora?

151
00:10:44,470 --> 00:10:54,060
To doslovno znači da čvor dijete je dijete drugog čvora

152
00:10:54,060 --> 00:10:58,760
ako je ta druga čvor ima jednu od svojih dječjih upućuje postavljene ukazati na tom čvoru.

153
00:10:58,760 --> 00:11:01,230
Da bi se to u više konkretnim uvjetima,

154
00:11:01,230 --> 00:11:11,170
ako je ukazao na tri strane jednog djeteta upućuje na sedam, a zatim tri je dijete sedam.

155
00:11:11,170 --> 00:11:14,510
Ako bismo shvatiti što djeca 7 su -

156
00:11:14,510 --> 00:11:18,510
dobro, vidjet ćemo da 7 ima pokazivač na tri i upustvo na devet,

157
00:11:18,510 --> 00:11:22,190
pa 9 i 3 su djeca 7.

158
00:11:22,190 --> 00:11:26,650
Devet nema djece, jer njeni dijete pokazivače su nula,

159
00:11:26,650 --> 00:11:30,940
i 3 ima samo jedno dijete, šest.

160
00:11:30,940 --> 00:11:37,430
Šest također nema djece, jer obje njegove naputke su null, koje ćemo izvući upravo sada.

161
00:11:37,430 --> 00:11:45,010
>> Osim toga, mi također govoriti o roditeljima određenog čvora,

162
00:11:45,010 --> 00:11:51,100
i to je, kao što očekujete, suprotno od ovog djeteta opisa.

163
00:11:51,100 --> 00:11:58,620
Svaki čvor ima samo jednog roditelja - umjesto dva kao što ste mogli očekivati ​​s ljudima.

164
00:11:58,620 --> 00:12:03,390
Na primjer, roditelj tri je sedam.

165
00:12:03,390 --> 00:12:10,800
Roditelj od 9 je također sedam, a roditelj 6 je tri. Nije puno za njega.

166
00:12:10,800 --> 00:12:15,720
Također imamo uvjete za razgovor o djedova i unučadi,

167
00:12:15,720 --> 00:12:18,210
i općenito govorimo o precima

168
00:12:18,210 --> 00:12:20,960
i potomci određenom čvoru.

169
00:12:20,960 --> 00:12:25,710
Predak od čvora - ili preci, bolje rečeno, od čvora -

170
00:12:25,710 --> 00:12:32,730
su svi čvorovi koji se nalaze na putu od korijena do tog čvora.

171
00:12:32,730 --> 00:12:36,640
Na primjer, ako gledam čvora 6,

172
00:12:36,640 --> 00:12:46,430
onda preci će biti i tri i sedam.

173
00:12:46,430 --> 00:12:55,310
Preci 9, na primjer, su - ako gledam čvora 9 -

174
00:12:55,310 --> 00:12:59,990
onda predak 9 je samo sedam.

175
00:12:59,990 --> 00:13:01,940
A potomci su upravo obrnuta.

176
00:13:01,940 --> 00:13:05,430
Ako želim da pogledate sve od potomaka 7,

177
00:13:05,430 --> 00:13:11,020
onda moram gledati na sve čvorove ispod njega.

178
00:13:11,020 --> 00:13:16,950
Dakle, imam 3, 9 i 6 sve kao potomaka sedam.

179
00:13:16,950 --> 00:13:24,170
>> Konačni termin koji ćemo govoriti o je taj pojam kao sestru.

180
00:13:24,170 --> 00:13:27,980
Braća - vrste nakon zajedno na tim obiteljskim uvjetima -

181
00:13:27,980 --> 00:13:33,150
su čvorovi koji su na istoj razini u stablo.

182
00:13:33,150 --> 00:13:42,230
Dakle, 3 i 9 su braća i sestre, jer su na istoj razini u stablo.

183
00:13:42,230 --> 00:13:46,190
Obojica imaju isti roditelj, sedam.

184
00:13:46,190 --> 00:13:51,400
U 6 nema braće i sestara, jer devet nema djece.

185
00:13:51,400 --> 00:13:55,540
I sedam nema braće i sestara, jer je korijen našeg stabla,

186
00:13:55,540 --> 00:13:59,010
i tu je uvijek samo jedan korijen.

187
00:13:59,010 --> 00:14:02,260
Za sedam braće i sestara imati tu bi trebala biti čvor iznad sedam.

188
00:14:02,260 --> 00:14:07,480
Tu bi trebala biti roditelj 7, u kojem slučaju 7 više ne bi korijen stabla.

189
00:14:07,480 --> 00:14:10,480
Zatim taj novi roditelj 7 će također imati dijete,

190
00:14:10,480 --> 00:14:16,480
i da dijete tada će biti sestru sedam.

191
00:14:16,480 --> 00:14:21,040
>> Dobro,. Premještanje na.

192
00:14:21,040 --> 00:14:24,930
Kad smo započeli našu raspravu binarnih stabala,

193
00:14:24,930 --> 00:14:28,790
smo razgovarali o tome kako da ćemo ih koristiti za

194
00:14:28,790 --> 00:14:32,800
dobiti prednost nad oba polja i povezane liste.

195
00:14:32,800 --> 00:14:37,220
A način na koji ćemo učiniti da je s ovim naručivanja imovine.

196
00:14:37,220 --> 00:14:41,080
Kažemo da binarno stablo je naredio, prema specifikaciji,

197
00:14:41,080 --> 00:14:45,740
ako za svaki čvor u našem stablu, svim svojim potomcima na lijevo -

198
00:14:45,740 --> 00:14:48,670
lijevo dijete, a sve s lijeve strane djeteta potomaka -

199
00:14:48,670 --> 00:14:54,510
imaju manje vrijednosti, a sve od čvorova na desnoj strani -

200
00:14:54,510 --> 00:14:57,770
pravo djeteta, a sve pravo djeteta potomaka -

201
00:14:57,770 --> 00:15:02,800
imati čvorove veće od vrijednosti tekućeg čvora da smo u potrazi na.

202
00:15:02,800 --> 00:15:07,850
Samo zbog jednostavnosti, idemo pretpostaviti da ne postoje nikakvi duple čvorove u našem stablu.

203
00:15:07,850 --> 00:15:11,180
Na primjer, u ovom stablu nećemo se baviti s tim slučajem

204
00:15:11,180 --> 00:15:13,680
gdje imamo vrijednost 7 u korijenu

205
00:15:13,680 --> 00:15:16,720
 i onda mi također imaju vrijednost 7 drugdje u stablo.

206
00:15:16,720 --> 00:15:24,390
U ovom slučaju, primijetit ćete da je to stablo doista naredio.

207
00:15:24,390 --> 00:15:26,510
Imamo vrijednost 7 u korijenu.

208
00:15:26,510 --> 00:15:29,720
Sve na lijevoj 7 -

209
00:15:29,720 --> 00:15:35,310
ako sam poništiti sve od tih malih maraka ovdje -

210
00:15:35,310 --> 00:15:40,450
sve s lijeve strane 7 - 3 i 6 -

211
00:15:40,450 --> 00:15:49,410
te vrijednosti su manje od sedam, a sve kako bi desno - što je upravo to 9 -

212
00:15:49,410 --> 00:15:53,450
je veći od 7.

213
00:15:53,450 --> 00:15:58,650
>> Ovo nije jedini naredio stablo sadrži ove vrijednosti,

214
00:15:58,650 --> 00:16:03,120
ali ajmo izvući malo više od njih.

215
00:16:03,120 --> 00:16:05,030
Tu je zapravo cijela hrpa načina na koje možemo to učiniti.

216
00:16:05,030 --> 00:16:09,380
Ja ću koristiti stenogram samo držati jednostavne stvari gdje -

217
00:16:09,380 --> 00:16:11,520
nego izvlači cijeli kutije-i-strelice -

218
00:16:11,520 --> 00:16:14,220
Samo ću izvući brojeve i dodati strelice ih povezuju.

219
00:16:14,220 --> 00:16:22,920
Za početak, samo ćemo pisati svoju izvornu stablo opet gdje smo imali sedam, a zatim tri,

220
00:16:22,920 --> 00:16:25,590
i od 3 ukazao natrag na pravo na 6,

221
00:16:25,590 --> 00:16:30,890
i 7 imao pravo djeteta koje je devet.

222
00:16:30,890 --> 00:16:33,860
Dobro,. Što je još jedan način na koji smo mogli napisati ovo drvo?

223
00:16:33,860 --> 00:16:38,800
Umjesto tri biti lijevo dijete od 7,

224
00:16:38,800 --> 00:16:41,360
mi također mogli imati šest biti lijevo dijete od 7,

225
00:16:41,360 --> 00:16:44,470
i onda 3 biti lijevo dijete od šest.

226
00:16:44,470 --> 00:16:48,520
To će izgledati ovako stabla ovdje gdje sam dobio 7,

227
00:16:48,520 --> 00:16:57,860
zatim 6, a zatim 3 i 9 na desnoj strani.

228
00:16:57,860 --> 00:17:01,490
Mi također ne moraju imati 7 kao naš korijen čvor.

229
00:17:01,490 --> 00:17:03,860
Također smo mogli imati šest kao naš korijen čvor.

230
00:17:03,860 --> 00:17:06,470
Što bi to izgledati?

231
00:17:06,470 --> 00:17:09,230
Ako ćemo zadržati ovaj naredio imovine,

232
00:17:09,230 --> 00:17:12,970
sve do lijevo od 6 mora biti manji od njega.

233
00:17:12,970 --> 00:17:16,540
Postoji samo jedna mogućnost, a to je tri.

234
00:17:16,540 --> 00:17:19,869
Ali onda kao pravi dijete 6, imamo dvije mogućnosti.

235
00:17:19,869 --> 00:17:25,380
Prvo, mogli smo imati sedam, a zatim devet,

236
00:17:25,380 --> 00:17:28,850
ili smo mogli izvući - kao što sam o to učiniti ovdje -

237
00:17:28,850 --> 00:17:34,790
gdje imamo 9 kao pravo dijete od 6,

238
00:17:34,790 --> 00:17:39,050
a zatim 7 kao lijeve dijete od 9 godina.

239
00:17:39,050 --> 00:17:44,240
>> Sada, 7 i 6 nisu samo moguće vrijednosti za korijen.

240
00:17:44,240 --> 00:17:50,200
Također smo mogli imati tri biti u korijenu.

241
00:17:50,200 --> 00:17:52,240
Što će se dogoditi ako 3 je u korijenu?

242
00:17:52,240 --> 00:17:54,390
Evo, stvari se malo zanimljivo.

243
00:17:54,390 --> 00:17:58,440
Tri nema nikakve vrijednosti koje su manje od njega,

244
00:17:58,440 --> 00:18:02,070
tako da cijela lijeva strana stablo samo će biti nula.

245
00:18:02,070 --> 00:18:03,230
Tu neće biti ništa tamo.

246
00:18:03,230 --> 00:18:07,220
Za pravo, mogli smo popis stvari u uzlaznom redoslijedu.

247
00:18:07,220 --> 00:18:15,530
Mi smo mogli imati tri, a zatim 6, a zatim sedam, a zatim devet.

248
00:18:15,530 --> 00:18:26,710
Ili, mogli bismo napraviti tri, zatim šest, zatim devet, zatim sedam.

249
00:18:26,710 --> 00:18:35,020
Ili, mogli bismo napraviti tri, zatim sedam, zatim šest, zatim devet.

250
00:18:35,020 --> 00:18:40,950
Ili, 3, 7 - zapravo nema, ne možemo napraviti sedam više.

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

252
00:18:43,330 --> 00:18:54,710
Mi možemo učiniti devet, a zatim od devet možemo učiniti šest, a zatim sedam.

253
00:18:54,710 --> 00:19:06,980
Ili, možemo napraviti 3, a zatim 9, a zatim 7, a zatim 6.

254
00:19:06,980 --> 00:19:12,490
>> Jedna stvar za privući vašu pažnju ovdje

255
00:19:12,490 --> 00:19:14,510
da ova stabla su malo čudan.

256
00:19:14,510 --> 00:19:17,840
Konkretno, ako ćemo gledati na četiri stabla na desnoj strani -

257
00:19:17,840 --> 00:19:20,930
Ja ću ih obići, ovdje -

258
00:19:20,930 --> 00:19:28,410
ova stabla izgledaju gotovo točno kao povezane liste.

259
00:19:28,410 --> 00:19:32,670
Svaki čvor ima samo jedno dijete,

260
00:19:32,670 --> 00:19:38,950
pa mi nemamo bilo koju od ove stablo poput strukture koje vidimo, na primjer,

261
00:19:38,950 --> 00:19:44,720
 u tom jednom usamljenom stablu ovamo na dnu lijevo.

262
00:19:44,720 --> 00:19:52,490
Ove stabla su zapravo zove izrod binarnih stabala,

263
00:19:52,490 --> 00:19:54,170
pa ćemo razgovarati o tim više u budućnosti -

264
00:19:54,170 --> 00:19:56,730
pogotovo ako idete na poduzeti druge tečajeve informatike.

265
00:19:56,730 --> 00:19:59,670
Ove stabla su izrod.

266
00:19:59,670 --> 00:20:03,780
Oni nisu vrlo koristan, jer, doista, ova struktura posuđuje sama

267
00:20:03,780 --> 00:20:08,060
 na traženje puta slične onoj povezane liste.

268
00:20:08,060 --> 00:20:13,050
Mi ne bi iskoristiti dodatne memorije - ovaj dodatni pokazivač -

269
00:20:13,050 --> 00:20:18,840
zbog naše strukture biti loše na ovaj način.

270
00:20:18,840 --> 00:20:24,700
Umjesto ići na i izvući binarnih stabala koja imaju devet u korijenu,

271
00:20:24,700 --> 00:20:27,220
koja je konačna slučaj da imamo,

272
00:20:27,220 --> 00:20:32,380
mi smo umjesto toga, u ovom trenutku, ide na razgovor malo o ovom drugom roku

273
00:20:32,380 --> 00:20:36,150
da mi koristimo kada govorimo o stablima, koji se zove visina.

274
00:20:36,150 --> 00:20:45,460
>> Visina stabla je udaljenost od korijena do najviše dalekoj čvora,

275
00:20:45,460 --> 00:20:48,370
odnosno broj skokova da bi trebala napraviti kako bi se

276
00:20:48,370 --> 00:20:53,750
početi od korijena i onda završiti na najviše dalekoj čvor u stablu.

277
00:20:53,750 --> 00:20:57,330
Ako gledamo na neke od tih stabala koje smo izvučeni ovdje,

278
00:20:57,330 --> 00:21:07,870
možemo vidjeti da ako uzmemo ovo drvo u gornjem lijevom kutu, a mi početi na tri,

279
00:21:07,870 --> 00:21:14,510
onda moramo napraviti jedan skok doći do 6, drugi hop doći do sedam,

280
00:21:14,510 --> 00:21:20,560
i trećina hop doći do devet.

281
00:21:20,560 --> 00:21:26,120
Dakle, visina ovog stabla je tri.

282
00:21:26,120 --> 00:21:30,640
Mi možemo učiniti istu vježbu za drugim stabala navedenih u ovom zelenom,

283
00:21:30,640 --> 00:21:40,100
i vidimo da je visina svih tih stabala je također istina 3.

284
00:21:40,100 --> 00:21:45,230
To je dio onoga što ih čini izrod -

285
00:21:45,230 --> 00:21:53,750
da je njihova visina je samo jedan manje od broja čvorova u cijelom stablu.

286
00:21:53,750 --> 00:21:58,400
Ako gledamo na ovom drugom stablu koji je okružen s crvenom, s druge strane,

287
00:21:58,400 --> 00:22:03,920
vidimo da su najviše udaljene list čvorovi su 6 i 9 -

288
00:22:03,920 --> 00:22:06,940
ostavlja se ti čvorovi koje nemaju djecu.

289
00:22:06,940 --> 00:22:11,760
Dakle, kako bi se iz korijena čvor na bilo 6 ili 9,

290
00:22:11,760 --> 00:22:17,840
moramo napraviti jedan skok doći do 7, a zatim drugi hop doći do 9,

291
00:22:17,840 --> 00:22:21,240
i isto tako, samo drugi hop od sedam doći do šest.

292
00:22:21,240 --> 00:22:29,080
Dakle, visina ovog stabla ovdje je samo 2.

293
00:22:29,080 --> 00:22:35,330
Možete se vratiti i to za sve ostale stabala koje smo ranije razgovarali

294
00:22:35,330 --> 00:22:37,380
s početkom u 7 i 6,

295
00:22:37,480 --> 00:22:42,500
i vidjet ćete da je visina svih tih stabala je također dva.

296
00:22:42,500 --> 00:22:46,320
>> Razlog što smo govorili o naručio binarnih stabala

297
00:22:46,320 --> 00:22:50,250
i zašto su cool jer možete pretraživati ​​kroz njih u

298
00:22:50,250 --> 00:22:53,810
vrlo sličan način u potrazi preko sortirani niz.

299
00:22:53,810 --> 00:22:58,720
Ovo je mjesto gdje govorimo o dobivanju taj poboljšani pretraživanja vremena

300
00:22:58,720 --> 00:23:02,730
preko jednostavnog povezane liste.

301
00:23:02,730 --> 00:23:05,010
Uz povezane liste - ako želite pronaći određeni element -

302
00:23:05,010 --> 00:23:07,470
ti si u najboljem će učiniti nekakvu linearnog pretraživanja

303
00:23:07,470 --> 00:23:10,920
gdje se na početku popisa i hop jedan po jedan -

304
00:23:10,920 --> 00:23:12,620
jedan čvor po jedan čvor -

305
00:23:12,620 --> 00:23:16,060
kroz cijeli popis dok ne pronađete ono što ste tražili.

306
00:23:16,060 --> 00:23:19,440
Budući da, ako imate binarnog stabla koji je pohranjen u ovoj lijepoj formatu,

307
00:23:19,440 --> 00:23:23,300
zapravo možete dobiti više od binarnog pretraživanja događa

308
00:23:23,300 --> 00:23:25,160
gdje ste podijeli pa vladaj

309
00:23:25,160 --> 00:23:29,490
i traži kroz odgovarajuće polovice stabla na svakom koraku.

310
00:23:29,490 --> 00:23:32,840
Idemo vidjeti kako se to radi.

311
00:23:32,840 --> 00:23:38,850
>> Ako imamo - opet, ide natrag u naš originalni stabla -

312
00:23:38,850 --> 00:23:46,710
smo započeli u 7, imamo 3 na lijevoj strani, 9 na desnoj strani,

313
00:23:46,710 --> 00:23:51,740
i ispod 3 imamo šest.

314
00:23:51,740 --> 00:24:01,880
Ako želimo tražiti broj 6 u ovoj stabla, da ćemo započeti u korijenu.

315
00:24:01,880 --> 00:24:08,910
Želimo usporediti vrijednost smo u potrazi za, recimo 6,

316
00:24:08,910 --> 00:24:12,320
na vrijednost pohranjena u čvoru koji mi trenutno gledamo, 7,

317
00:24:12,320 --> 00:24:21,200
Smatraju da je doista šest manje od 7, tako da bismo se presele na lijevoj strani.

318
00:24:21,200 --> 00:24:25,530
Ako je vrijednost 6 bio veći od sedam, što bi umjesto toga su se preselili u desno.

319
00:24:25,530 --> 00:24:29,770
Budući da znamo da je - s obzirom na strukturu našeg naredio binarno stablo -

320
00:24:29,770 --> 00:24:33,910
sve vrijednosti manje od 7 će biti pohranjeni na lijevoj 7,

321
00:24:33,910 --> 00:24:40,520
nema potrebe da se čak i gnjaviti gleda kroz desnoj strani stabla.

322
00:24:40,520 --> 00:24:43,780
Nakon što smo se presele na lijevoj strani, a mi smo sada na čvoru sadrži tri,

323
00:24:43,780 --> 00:24:48,110
možemo učiniti da istu usporedbu opet gdje smo usporedili tri i šest.

324
00:24:48,110 --> 00:24:52,430
I mi smo pronašli da dok 6 - vrijednost tražimo - veći od 3,

325
00:24:52,430 --> 00:24:58,580
možemo ići na desnoj strani čvor sadrži tri.

326
00:24:58,580 --> 00:25:02,670
Nema lijeva strana ovdje, tako da smo mogli ignorirati to.

327
00:25:02,670 --> 00:25:06,510
No, mi samo znamo da zato tražimo na samog stabla,

328
00:25:06,510 --> 00:25:08,660
i možemo vidjeti da je stablo nema djece.

329
00:25:08,660 --> 00:25:13,640
>> To je također prilično lako gledati 6 u ovom stablu ako radimo to sami kao ljudi,

330
00:25:13,640 --> 00:25:16,890
ali ajmo slijediti ovaj proces mehanički poput računala će učiniti

331
00:25:16,890 --> 00:25:18,620
stvarno razumjeti algoritam.

332
00:25:18,620 --> 00:25:26,200
U ovom trenutku, mi smo sada gleda na čvoru koji sadrži 6,

333
00:25:26,200 --> 00:25:29,180
i mi smo u potrazi za vrijednost 6,

334
00:25:29,180 --> 00:25:31,740
tako je, doista, pronašli smo odgovarajući čvor.

335
00:25:31,740 --> 00:25:35,070
Našli smo vrijednost 6 u našem stablu, a možemo prestati tražiti.

336
00:25:35,070 --> 00:25:37,330
U ovom trenutku, ovisno o tome što se događa,

337
00:25:37,330 --> 00:25:41,870
možemo reći, da smo našli vrijednost 6, to postoji u našem stablu.

338
00:25:41,870 --> 00:25:47,640
Ili, ako ćemo planira umetnuti čvor ili učiniti nešto, što možemo učiniti da se u ovom trenutku.

339
00:25:47,640 --> 00:25:53,010
>> Učinimo par više dohvate samo da vidim kako to ide.

340
00:25:53,010 --> 00:25:59,390
Pogledajmo što se događa ako smo probati i pogledati vrijednost 10.

341
00:25:59,390 --> 00:26:02,970
Ako smo bili pogledati vrijednost 10, što bi početi u korijenu.

342
00:26:02,970 --> 00:26:07,070
Želimo vidjeti da 10 je veći od 7, tako da bismo se presele na desno.

343
00:26:07,070 --> 00:26:13,640
Želimo doći do devet i usporedite 9 do 10 i vidjeti da je 9 doista manje od 10.

344
00:26:13,640 --> 00:26:16,210
Pa opet, mi bismo pokušati pomaknuti udesno.

345
00:26:16,210 --> 00:26:20,350
No, u ovom trenutku, mi bismo primijetiti da smo na null čvor.

346
00:26:20,350 --> 00:26:23,080
Tu nema ništa. Nema ništa gdje 10 bi trebao biti.

347
00:26:23,080 --> 00:26:29,360
Ovo je mjesto gdje možemo prijaviti neuspjeh - da je zaista ne 10 u stablo.

348
00:26:29,360 --> 00:26:35,420
I na kraju, idemo kroz slučaj gdje smo pokušavate pogledati jedan u stablo.

349
00:26:35,420 --> 00:26:38,790
To je slično onome što se događa ako ćemo gledati do 10, osim umjesto da ide desno,

350
00:26:38,790 --> 00:26:41,260
idemo ići na lijevoj strani.

351
00:26:41,260 --> 00:26:46,170
Krećemo u 7 i vidjeti da je jedan manje od 7, tako da smo se presele na lijevoj strani.

352
00:26:46,170 --> 00:26:51,750
Mi smo dobili na tri i vidjeti da je jedan manje od tri, pa opet ćemo pokušati da se presele na lijevoj strani.

353
00:26:51,750 --> 00:26:59,080
U ovom trenutku imamo null čvor, tako da opet možemo prijaviti neuspjeh.

354
00:26:59,080 --> 00:27:10,260
>> Ako želite saznati više o binarnih stabala,

355
00:27:10,260 --> 00:27:14,420
postoje cijela hrpa zabavnih malih problema koje možete učiniti s njima.

356
00:27:14,420 --> 00:27:19,450
Predlažem trenirao crtež iz ovih dijagrama jedan po jedan

357
00:27:19,450 --> 00:27:21,910
i nakon kroz sve različite korake,

358
00:27:21,910 --> 00:27:25,060
jer to će doći u super-zgodan

359
00:27:25,060 --> 00:27:27,480
ne samo kada radite problema Huffman encoding set

360
00:27:27,480 --> 00:27:29,390
ali iu budućim tečajevima -

361
00:27:29,390 --> 00:27:32,220
samo učenje kako izvući ove strukture podataka i misliti kroz probleme

362
00:27:32,220 --> 00:27:38,000
s olovku i papir ili, u ovom slučaju, iPad i olovka.

363
00:27:38,000 --> 00:27:41,000
>> U ovom trenutku ipak, idemo da se presele na napraviti neke praksu kodiranja

364
00:27:41,000 --> 00:27:44,870
i zapravo igraju s ovih binarnih stabala i vidjeti.

365
00:27:44,870 --> 00:27:52,150
Ja ću se vratiti preko moje računalo.

366
00:27:52,150 --> 00:27:58,480
Za ovaj dio članka, umjesto korištenja CS50 CS50 Run ili prostora,

367
00:27:58,480 --> 00:28:01,500
Ja ću koristiti aparat.

368
00:28:01,500 --> 00:28:04,950
>> Nakon zajedno sa specifikacijom Problem Set,

369
00:28:04,950 --> 00:28:07,740
Vidim da sam trebao otvoriti aparat,

370
00:28:07,740 --> 00:28:11,020
ići na moj Dropbox mapu, stvoriti mapu pod nazivom Odjeljak 7,

371
00:28:11,020 --> 00:28:15,730
, a zatim stvoriti datoteku pod nazivom binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Ovdje ćemo ići. Imam aparat već otvoren.

373
00:28:22,050 --> 00:28:25,910
Idem podići terminal.

374
00:28:25,910 --> 00:28:38,250
Ja idem na Dropbox mapu, napraviti direktorij pod nazivom section7,

375
00:28:38,250 --> 00:28:42,230
i vidjeti da je potpuno prazna.

376
00:28:42,230 --> 00:28:48,860
Sada ću otvoriti binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Dobro,. Ovdje ćemo ići - praznu datoteku.

378
00:28:51,750 --> 00:28:54,330
>> Vratimo se na specifikaciji.

379
00:28:54,330 --> 00:28:59,850
Specifikacija pita za stvaranje novog tipa definiciju

380
00:28:59,850 --> 00:29:03,080
za binarnom stablu čvor koji sadrži int vrijednosti -

381
00:29:03,080 --> 00:29:07,110
baš kao i vrijednostima koje smo izvukao u naš dijagrame prije.

382
00:29:07,110 --> 00:29:11,740
Mi ćemo koristiti ovaj predloženi typedef da smo učinili ovdje

383
00:29:11,740 --> 00:29:14,420
koji bi trebali prepoznati iz problema Set 5 -

384
00:29:14,420 --> 00:29:19,190
ako nisi ljestve stol način osvajanje Speller programa.

385
00:29:19,190 --> 00:29:22,540
Vi bi također trebali prepoznati ga iz prošlotjednog dijelu

386
00:29:22,540 --> 00:29:23,890
gdje smo razgovarali o povezanim listama.

387
00:29:23,890 --> 00:29:27,870
Moramo to typedef struct od čvora,

388
00:29:27,870 --> 00:29:34,430
a mi smo dati ovaj struct node ovo ime struct čvora unaprijed

389
00:29:34,430 --> 00:29:39,350
tako da mi onda može odnositi na njega jer ćemo želite imati pokazivače struct čvor

390
00:29:39,350 --> 00:29:45,740
kao dio naše struct, ali smo onda sam okružen ovo -

391
00:29:45,740 --> 00:29:47,700
odnosno, prilaže ovo - u typedef

392
00:29:47,700 --> 00:29:54,600
tako da, kasnije u kodu, možemo se odnose na ovaj struct samo kao čvor umjesto struct čvora.

393
00:29:54,600 --> 00:30:03,120
>> To će biti vrlo sličan pojedinačno-linked list definiciji da smo vidjeli prošli tjedan.

394
00:30:03,120 --> 00:30:20,070
Da biste to učinili, neka je samo započeti pisanje predloženi.

395
00:30:20,070 --> 00:30:23,840
Mi znamo da moramo imati cjelobrojne vrijednosti

396
00:30:23,840 --> 00:30:32,170
pa ćemo staviti u int vrijednosti, a zatim, umjesto da samo jedan pokazivač na sljedeći element -

397
00:30:32,170 --> 00:30:33,970
kao što smo učinili s pojedinačno povezanih s popisa -

398
00:30:33,970 --> 00:30:38,110
idemo imati lijevo i desno dijete upućuje.

399
00:30:38,110 --> 00:30:42,880
To je prilično jednostavan previše - struct node * lijevo dijete;

400
00:30:42,880 --> 00:30:51,190
i rekonstruirati čvor * desno dijete;. Cool.

401
00:30:51,190 --> 00:30:54,740
To izgleda kao prilično dobar početak.

402
00:30:54,740 --> 00:30:58,530
Vratimo se na specifikaciji.

403
00:30:58,530 --> 00:31:05,030
>> Sada trebamo proglasiti globalnu varijablu čvor * za korijen stabla.

404
00:31:05,030 --> 00:31:10,590
Mi ćemo napraviti ovo globalno baš kao što smo napravili prvi pokazivač u našem povezane liste i globalne.

405
00:31:10,590 --> 00:31:12,690
To je bilo tako da je u funkcijama koje smo napisali

406
00:31:12,690 --> 00:31:16,180
ne morate se držati prolazi oko tog korijena -

407
00:31:16,180 --> 00:31:19,620
iako ćemo vidjeti da ako ne želite pisati ove funkcije rekurzivno,

408
00:31:19,620 --> 00:31:22,830
to bi moglo biti bolje da nije ni to zaobići kao globalni na prvom mjestu

409
00:31:22,830 --> 00:31:28,090
i umjesto da ga inicijalizirati lokalno u glavnom funkciji.

410
00:31:28,090 --> 00:31:31,960
No, mi ćemo to učiniti na globalnoj razini za početak.

411
00:31:31,960 --> 00:31:39,920
Opet, mi ćemo dati nekoliko mjesta, a ja ću proglasiti čvor * korijen.

412
00:31:39,920 --> 00:31:46,770
Samo kako bi bili sigurni da ne ostavljaju to nepokrenute, ja ću ga postaviti jednaka null.

413
00:31:46,770 --> 00:31:52,210
Sada, u glavnoj funkciji - koji ćemo pisati stvarno brzo ovdje -

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

415
00:32:00,450 --> 00:32:10,640
i ja ću početi proglašenja moj argv lepezu kao const samo tako da znam

416
00:32:10,640 --> 00:32:14,550
da su ti argumenti su argumenti da sam vjerojatno ne žele mijenjati.

417
00:32:14,550 --> 00:32:18,390
Ako želim ih mijenjati i vjerojatno bi trebao biti stvaranje kopije.

418
00:32:18,390 --> 00:32:21,740
Vidjet ćete to puno u kodu.

419
00:32:21,740 --> 00:32:25,440
To je u redu bilo koji način. To je u redu da ga ostavite kao - izostaviti const ako želite.

420
00:32:25,440 --> 00:32:28,630
Ja obično ga staviti u samo tako da sam se podsjetiti

421
00:32:28,630 --> 00:32:33,650
 da sam vjerojatno ne želite mijenjati te tvrdnje.

422
00:32:33,650 --> 00:32:39,240
>> Kao i uvijek, ja ću uključiti ovu povratnu 0 crtu na kraju glavni.

423
00:32:39,240 --> 00:32:45,730
Evo, ja ću inicijalizirati moj čvor korijen.

424
00:32:45,730 --> 00:32:48,900
Kao što stoji upravo sada, imam pokazivač koji je postavljen na nulu,

425
00:32:48,900 --> 00:32:52,970
tako da je ukazujući na ništa.

426
00:32:52,970 --> 00:32:57,480
Da bi se zapravo početi izgradnja čvora,

427
00:32:57,480 --> 00:32:59,250
Prvi put sam je potrebno alocirati memoriju za njega.

428
00:32:59,250 --> 00:33:05,910
Ja ću učiniti da izradi sjećanje na hrpu pomoću malloc.

429
00:33:05,910 --> 00:33:10,660
Ja ću postaviti korijen jednak rezultat malloc,

430
00:33:10,660 --> 00:33:19,550
a ja ću koristiti sizeof operatora za izračunavanje veličine čvora.

431
00:33:19,550 --> 00:33:24,990
Razlog zbog kojeg sam koristiti sizeof čvor, za razliku od, recimo,

432
00:33:24,990 --> 00:33:37,020
radiš nešto ovako - malloc (4 + 4 +4) ili malloc 12 -

433
00:33:37,020 --> 00:33:40,820
je zato što želim da moja koda biti kompatibilan moguće.

434
00:33:40,820 --> 00:33:44,540
Želim biti u mogućnosti iskoristiti ovu. C datoteku, prevesti ga na aparatu,

435
00:33:44,540 --> 00:33:48,820
, a zatim ga prevesti na mom 64-bitni Mac -

436
00:33:48,820 --> 00:33:52,040
ili na potpuno različitoj arhitekturi -

437
00:33:52,040 --> 00:33:54,640
i želim to sve raditi isto.

438
00:33:54,640 --> 00:33:59,510
>> Ako sam stvaranje pretpostavki o veličini varijabli -

439
00:33:59,510 --> 00:34:02,070
veličina int ili veličini pokazivač -

440
00:34:02,070 --> 00:34:06,070
onda sam i stvaranje pretpostavki o vrstama arhitekture

441
00:34:06,070 --> 00:34:10,440
na kojoj moj broj uspješno može sastaviti kada pokrenuti.

442
00:34:10,440 --> 00:34:15,030
Uvijek koristite sizeof za razliku od ručno zbrajanjem struct polja.

443
00:34:15,030 --> 00:34:20,500
Drugi razlog je da postoji također može biti padding da je prevodilac stavlja u struct.

444
00:34:20,500 --> 00:34:26,570
Čak i samo zbrajanjem pojedinačnih polja nije nešto što se obično žele učiniti,

445
00:34:26,570 --> 00:34:30,340
tako, izbrisati tu liniju.

446
00:34:30,340 --> 00:34:33,090
Sada, stvarno inicijalizirati ovaj čvor korijen,

447
00:34:33,090 --> 00:34:36,489
Ja ću morati priključiti u vrijednosti za svaki od svojih različitih područja.

448
00:34:36,489 --> 00:34:41,400
Na primjer, za vrijednost znam želim inicijalizirati na sedam,

449
00:34:41,400 --> 00:34:46,920
i za sada ću postaviti lijevo dijete biti nula

450
00:34:46,920 --> 00:34:55,820
i desno dijete također biti nula. Sjajno!

451
00:34:55,820 --> 00:35:02,670
Učinili smo taj dio specifikacija.

452
00:35:02,670 --> 00:35:07,390
>> Specifikacija dolje na dnu stranice 3 me pita za stvaranje tri više čvorova -

453
00:35:07,390 --> 00:35:10,600
jedan sadrži tri, jedan sadrži šest, a jedan sa 9 -

454
00:35:10,600 --> 00:35:14,210
i onda ih spojiti gore tako da izgleda baš kao naš stabla dijagrama

455
00:35:14,210 --> 00:35:17,120
da smo pričali o ranije.

456
00:35:17,120 --> 00:35:20,450
Ajmo to prilično brzo ovdje.

457
00:35:20,450 --> 00:35:26,270
Vidjet ćete stvarno brzo, da ću početi pisati hrpa duple koda.

458
00:35:26,270 --> 00:35:32,100
Ja ću stvoriti čvor * a ja ću ga nazvati tri.

459
00:35:32,100 --> 00:35:36,000
Ja ću ga postaviti jednaka malloc (sizeof (čvor)).

460
00:35:36,000 --> 00:35:41,070
Ja ću postaviti tri-> value = 3.

461
00:35:41,070 --> 00:35:54,780
Tri -> left_child = NULL; tri -> desno _child = NULL; kao dobro.

462
00:35:54,780 --> 00:36:01,150
To izgleda prilično slično inicijalizacije korijen, a to je upravo ono što

463
00:36:01,150 --> 00:36:05,760
Ja ću morati učiniti ako počnem inicijalizacije 6 i 9 kao dobro.

464
00:36:05,760 --> 00:36:20,720
Učinit ću to jako brzo ovdje - zapravo, ja ću učiniti malo kopirati i zalijepiti,

465
00:36:20,720 --> 00:36:46,140
i pobrinite se da sam - u redu.

466
00:36:46,470 --> 00:37:09,900
 Sada, ja sam dobio ga kopirati, a ja mogu ići naprijed i postaviti to jednako šest.

467
00:37:09,900 --> 00:37:14,670
Možete vidjeti da to traje neko vrijeme i nije super-učinkovit.

468
00:37:14,670 --> 00:37:22,610
U samo malo, mi ćemo napisati funkciju koja će to učiniti za nas.

469
00:37:22,610 --> 00:37:32,890
Želim zamijeniti ovaj sa 9, zamijenite da sa šest.

470
00:37:32,890 --> 00:37:37,360
>> Sada imamo sve naše čvorova stvorio i inicijalizirana.

471
00:37:37,360 --> 00:37:41,200
Imamo naš korijen postavljen jednak 7, ili sadrže vrijednost 7,

472
00:37:41,200 --> 00:37:46,510
naš čvor koji sadrži tri, naš čvor koji sadrži šest, a naš čvor koji sadrži devet.

473
00:37:46,510 --> 00:37:50,390
U ovom trenutku, sve što morate učiniti je žica sve gore.

474
00:37:50,390 --> 00:37:53,020
Razlog zbog kojeg sam inicijalizira sve upućuje na nulu je samo tako da sam siguran da bi

475
00:37:53,020 --> 00:37:56,260
Nemam nikakve nepokrenute upućuje u tu slučajno.

476
00:37:56,260 --> 00:38:02,290
I također, jer je, u ovom trenutku, samo sam se zapravo povezivanje čvorova međusobno -

477
00:38:02,290 --> 00:38:04,750
za one koji su zapravo povezani - Nemam proći i napraviti

478
00:38:04,750 --> 00:38:08,240
sigurni da su svi ugašenih su tamo na odgovarajućim mjestima.

479
00:38:08,240 --> 00:38:15,630
>> Počevši u korijenu, znam da je u korijenu je lijevo dijete je tri.

480
00:38:15,630 --> 00:38:21,250
Znam da je korijen pravo dijete je devet.

481
00:38:21,250 --> 00:38:24,880
Nakon toga, jedino drugo dijete koje sam ostavila brinuti

482
00:38:24,880 --> 00:38:39,080
je 3 pravo dijete, koji je 6.

483
00:38:39,080 --> 00:38:44,670
U ovom trenutku, to sve izgleda prilično dobro.

484
00:38:44,670 --> 00:38:54,210
Mi ćemo izbrisati neke od tih linija.

485
00:38:54,210 --> 00:38:59,540
Sada sve izgleda prilično dobro.

486
00:38:59,540 --> 00:39:04,240
Vratimo se našoj specifikaciji i vidjeti što moramo učiniti sljedeći.

487
00:39:04,240 --> 00:39:07,610
>> U ovom trenutku, moramo napisati funkcija zove 'sadrži'

488
00:39:07,610 --> 00:39:14,150
sa prototip "bool sadrži (int vrijednost) '.

489
00:39:14,150 --> 00:39:17,060
A to sadrži funkciju koja će povratak istina

490
00:39:17,060 --> 00:39:21,200
 ako je stablo ukazao na naše globalne korijena varijabla

491
00:39:21,200 --> 00:39:26,950
 sadrži vrijednost prošao u funkciji i lažno drugi način.

492
00:39:26,950 --> 00:39:29,000
Idemo naprijed i učiniti.

493
00:39:29,000 --> 00:39:35,380
To će biti točno kao lookup da smo napravili rukom na ipad samo malo prije.

494
00:39:35,380 --> 00:39:40,130
Idemo povećavanje natrag u malo i pomaknite se gore.

495
00:39:40,130 --> 00:39:43,130
Mi idemo staviti tu funkciju točno iznad naše glavne funkcije

496
00:39:43,130 --> 00:39:48,990
tako da ne moramo raditi bilo kakve prototipa.

497
00:39:48,990 --> 00:39:55,960
Dakle, bool sadrži (int vrijednost).

498
00:39:55,960 --> 00:40:00,330
Tu ćemo ići. Tu je naš predloženi deklaracija.

499
00:40:00,330 --> 00:40:02,900
Samo kako bi bili sigurni da će to sastaviti,

500
00:40:02,900 --> 00:40:06,820
Ja ću ići naprijed i samo ga postaviti jednaka povratak false.

501
00:40:06,820 --> 00:40:09,980
Upravo sada je ova funkcija jednostavno neće učiniti ništa i uvijek navode da

502
00:40:09,980 --> 00:40:14,010
vrijednost da smo u potrazi za nije u stablu.

503
00:40:14,010 --> 00:40:16,280
>> U ovom trenutku, to je vjerojatno dobra ideja -

504
00:40:16,280 --> 00:40:19,600
otkako smo napisali hrpu koda i nismo ni pokušali to testiranje još -

505
00:40:19,600 --> 00:40:22,590
kako bi bili sigurni da je sve to sastavlja.

506
00:40:22,590 --> 00:40:27,460
Postoji nekoliko stvari koje moramo učiniti kako bi bili sigurni da će se to sastaviti.

507
00:40:27,460 --> 00:40:33,530
Prvo, vidjeti ako smo koristili sve funkcije u bilo knjižnicama koje još nismo uključeni.

508
00:40:33,530 --> 00:40:37,940
Funkcije koje smo koristili do sada su malloc,

509
00:40:37,940 --> 00:40:43,310
i onda smo također bio koristeći ovu vrstu - ovo nije standardna tip zove 'bool' -

510
00:40:43,310 --> 00:40:45,750
koja je uključena u standardnu ​​bool datoteku zaglavlja.

511
00:40:45,750 --> 00:40:53,250
Mi svakako želimo uključiti standardni bool.h za bool tipa,

512
00:40:53,250 --> 00:40:59,230
i mi također želimo # uključuju standardni lib.h za standardne knjižnicama

513
00:40:59,230 --> 00:41:03,530
da su malloc i free, i sve to.

514
00:41:03,530 --> 00:41:08,660
Dakle, zoom out, idemo prestati.

515
00:41:08,660 --> 00:41:14,190
Pokušajmo i pobrinite se da je to zapravo učinio sastaviti.

516
00:41:14,190 --> 00:41:18,150
Mi vidimo da to radi, tako da smo na pravom putu.

517
00:41:18,150 --> 00:41:22,990
>> Ajmo otvoriti binary_tree.c opet.

518
00:41:22,990 --> 00:41:34,530
To sastavlja. Idemo dolje i uvjerite se da smo ubaciti neke pozive na našoj sadrži funkcije -

519
00:41:34,530 --> 00:41:40,130
samo da bi bili sigurni da je to sve dobro i dobro.

520
00:41:40,130 --> 00:41:43,170
Na primjer, kada smo radili neke dohvate u našem stablu ranije,

521
00:41:43,170 --> 00:41:48,500
pokušali smo potražiti vrijednosti 6, 10 i 1, a znali smo da je šest u stablu,

522
00:41:48,500 --> 00:41:52,220
10 nije bio u stablo, a jedan nije bio u stablo bilo.

523
00:41:52,220 --> 00:41:57,230
Ajmo koristiti one primjere pozive kao način shvatiti da li ili ne

524
00:41:57,230 --> 00:41:59,880
Sadrži naša funkcija radi.

525
00:41:59,880 --> 00:42:05,210
Da bi to učinili, ja ću koristiti printf funkciju,

526
00:42:05,210 --> 00:42:10,280
i da ćemo ispisati rezultat poziva da sadrži.

527
00:42:10,280 --> 00:42:13,280
Ja ću staviti u nizu "sadrži (% d) = jer

528
00:42:13,280 --> 00:42:20,470
 idemo na plug u vrijednosti koje ćemo tražiti,

529
00:42:20,470 --> 00:42:27,130
i =% s \ n ", i koristiti kao naše format string.

530
00:42:27,130 --> 00:42:30,720
Mi smo samo ćemo vidjeti - doslovno ispisati na zaslonu -

531
00:42:30,720 --> 00:42:32,060
ono što izgleda kao funkcija poziva.

532
00:42:32,060 --> 00:42:33,580
To nije zapravo funkcija poziva.

533
00:42:33,580 --> 00:42:36,760
 Ovo je samo niz dizajniran da izgledaju kao funkcija poziva.

534
00:42:36,760 --> 00:42:41,140
>> Sada, idemo priključiti u vrijednosti.

535
00:42:41,140 --> 00:42:43,580
Mi ćemo pokušati sadrži na šest,

536
00:42:43,580 --> 00:42:48,340
i onda što ćemo učiniti ovdje je koristiti taj ternarni operator.

537
00:42:48,340 --> 00:42:56,340
Hajdemo vidjeti - sadrži 6 - pa, sada sam sadržavao 6, a ako sadrži šest je istina,

538
00:42:56,340 --> 00:43:01,850
string da ćemo poslati na% s formatu karaktera

539
00:43:01,850 --> 00:43:04,850
će biti niz "pravi".

540
00:43:04,850 --> 00:43:07,690
Ajmo pomicanje preko malo.

541
00:43:07,690 --> 00:43:16,210
Inače, želimo poslati string "lažni" ako sadrži 6 false.

542
00:43:16,210 --> 00:43:19,730
Ovo je malo glup izgleda, ali pretpostavljam da sam možda kao dobro ilustriraju

543
00:43:19,730 --> 00:43:23,780
što je ternarni operator izgleda jer nismo ga vidjeli za neko vrijeme.

544
00:43:23,780 --> 00:43:27,670
To će biti lijepo, zgodan način da se shvatiti ako naša Sadrži funkcija radi.

545
00:43:27,670 --> 00:43:30,040
Idem za pomicanje natrag preko lijeve strane,

546
00:43:30,040 --> 00:43:39,900
i ja ću kopirati i zalijepiti ovaj redak nekoliko puta.

547
00:43:39,900 --> 00:43:44,910
To je promijenilo neke od tih vrijednosti oko,

548
00:43:44,910 --> 00:43:59,380
tako da će to biti jedan, a to će biti 10.

549
00:43:59,380 --> 00:44:02,480
>> U ovom trenutku imamo lijepu sadrži funkciju.

550
00:44:02,480 --> 00:44:06,080
Imamo neke testove, pa ćemo vidjeti ako se to sve funkcionira.

551
00:44:06,080 --> 00:44:08,120
U ovom trenutku smo napisana još malo koda.

552
00:44:08,120 --> 00:44:13,160
Vrijeme je za otkaz van i pobrinite se da je sve još uvijek sastavlja.

553
00:44:13,160 --> 00:44:20,360
Prestanite se, a sada idemo pokušati što binarnog stabla opet.

554
00:44:20,360 --> 00:44:22,260
Pa, to izgleda kao da smo dobili pogrešku,

555
00:44:22,260 --> 00:44:26,930
a mi smo dobili to izričito izjavljuje knjižnice funkciju printf.

556
00:44:26,930 --> 00:44:39,350
To izgleda kao moramo otići i # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
A uz to, sve bi trebalo sastaviti. Mi smo svi dobro.

558
00:44:45,350 --> 00:44:50,420
Sada ćemo pokušati trčanje binarnog stabla i vidjeti što se događa.

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

560
00:44:53,520 --> 00:44:55,190
i vidimo da je, kao što smo i očekivali -

561
00:44:55,190 --> 00:44:56,910
jer nismo proveli sadrži još,

562
00:44:56,910 --> 00:44:59,800
odnosno, upravo smo stavili u zamjenu lažne -

563
00:44:59,800 --> 00:45:03,300
vidimo da je to samo vraća false za sve njih,

564
00:45:03,300 --> 00:45:06,180
tako da je sve radio za najveći dio prilično dobro.

565
00:45:06,180 --> 00:45:11,860
>> Idemo natrag u, a zapravo provesti sadrži u ovom trenutku.

566
00:45:11,860 --> 00:45:17,490
Idem za pomicanje prema dolje, zumiranje, i -

567
00:45:17,490 --> 00:45:22,330
zapamtite, algoritam koji smo koristili bio je da smo krenuli na korijen čvor

568
00:45:22,330 --> 00:45:28,010
i onda na svakom čvoru koji susrećemo, radimo usporedbu,

569
00:45:28,010 --> 00:45:32,380
i na temelju te usporedbe mi ili premjestiti na lijevu dijete ili na pravo dijete.

570
00:45:32,380 --> 00:45:39,670
To će izgledati vrlo slično kod binarnog pretraživanja koja smo pisali ranije u pojam.

571
00:45:39,670 --> 00:45:47,810
Kada smo krenuti, znamo da želimo držati na trenutnom čvoru

572
00:45:47,810 --> 00:45:54,050
da smo gleda, a trenutni čvor će biti inicijalizirane na korijenski čvor.

573
00:45:54,050 --> 00:45:56,260
A sada, idemo da ide kroz stabla,

574
00:45:56,260 --> 00:45:58,140
i zapamtite da je naš uvjet zaustavljanja -

575
00:45:58,140 --> 00:46:01,870
 kad smo zapravo radili kroz primjer rukom -

576
00:46:01,870 --> 00:46:03,960
bio je kada smo naišli null čvor,

577
00:46:03,960 --> 00:46:05,480
Ne kad smo gledali null djeteta,

578
00:46:05,480 --> 00:46:09,620
nego kad smo zapravo preselili na čvoru u stablo

579
00:46:09,620 --> 00:46:12,640
i pronašao da smo na null čvor.

580
00:46:12,640 --> 00:46:20,720
Mi ćemo ponoviti do sad nije jednaka null.

581
00:46:20,720 --> 00:46:22,920
I što ćemo učiniti?

582
00:46:22,920 --> 00:46:31,610
Mi ćemo testirati ako (sad -> vrijednost == vrijednost),

583
00:46:31,610 --> 00:46:35,160
onda znamo da smo zapravo našli čvor koji smo tražili.

584
00:46:35,160 --> 00:46:40,450
Dakle, ovdje, možemo se vratiti istina.

585
00:46:40,450 --> 00:46:49,830
Inače, želimo vidjeti hoće li ili ne je vrijednost manja od vrijednosti.

586
00:46:49,830 --> 00:46:53,850
Ako je trenutni čvora vrijednost manja od vrijednosti tražimo,

587
00:46:53,850 --> 00:46:57,280
idemo da se presele na desnoj strani.

588
00:46:57,280 --> 00:47:10,600
Dakle, sad = sad -> right_child, i inače, idemo da se presele na lijevoj strani.

589
00:47:10,600 --> 00:47:17,480
sad = sad -> left_child;. Prilično jednostavan.

590
00:47:17,480 --> 00:47:22,830
>> Vi vjerojatno prepoznati petlju koja izgleda vrlo slično tome od

591
00:47:22,830 --> 00:47:27,580
binarno pretraživanje ranije u roku, osim onda smo se bave niski, srednji i visoki.

592
00:47:27,580 --> 00:47:30,000
Evo, samo moramo gledati na trenutnu vrijednost,

593
00:47:30,000 --> 00:47:31,930
pa to je lijepo i jednostavno.

594
00:47:31,930 --> 00:47:34,960
Ajmo pobrinite se to kod radi.

595
00:47:34,960 --> 00:47:42,780
Prvo, pobrinite se da sastavlja. Izgleda kao da radi.

596
00:47:42,780 --> 00:47:47,920
Pokušajmo ga izvodi.

597
00:47:47,920 --> 00:47:50,160
I doista, to ispisuje sve što smo očekivali.

598
00:47:50,160 --> 00:47:54,320
On pronalazi 6 u stablo, ne može pronaći 10 jer 10 nije u stablu,

599
00:47:54,320 --> 00:47:57,740
i ne može pronaći jedan ili zbog jednog je također nije u stablu.

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

601
00:48:01,420 --> 00:48:04,470
>> Dobro,. Vratimo se našoj specifikaciji i vidjeti što je sljedeće.

602
00:48:04,470 --> 00:48:07,990
Sada, ona želi dodati neke više čvorova na našem stablu.

603
00:48:07,990 --> 00:48:11,690
Ona želi dodati 5, 2 i 8, i pobrinite se da su naši sadrži kod

604
00:48:11,690 --> 00:48:13,570
još uvijek radi kao što se očekuje.

605
00:48:13,570 --> 00:48:14,900
Hajdemo to učiniti.

606
00:48:14,900 --> 00:48:19,430
U ovom trenutku, umjesto da radi dosadne kopirati i zalijepiti opet,

607
00:48:19,430 --> 00:48:23,770
ajmo napisati funkciju da zapravo stvoriti čvor.

608
00:48:23,770 --> 00:48:27,740
Ako mi se pomaknite prema dolje sve do glavne, vidimo da smo radili ovaj

609
00:48:27,740 --> 00:48:31,210
vrlo slična kod iznova i iznova svaki put da želimo stvoriti čvor.

610
00:48:31,210 --> 00:48:39,540
>> Ajmo napisati funkciju koja će zapravo izgraditi čvor za nas i vratiti ga.

611
00:48:39,540 --> 00:48:41,960
Ja ću ga nazvati build_node.

612
00:48:41,960 --> 00:48:45,130
Ja ću izgraditi čvor s određenom vrijednosti.

613
00:48:45,130 --> 00:48:51,040
Povećavanje ovdje.

614
00:48:51,040 --> 00:48:56,600
Prva stvar ću učiniti zapravo stvoriti prostor za čvor na hrpi.

615
00:48:56,600 --> 00:49:05,400
Dakle, čvor * n = malloc (sizeof (čvor)), n -> vrijednost = vrijednost;

616
00:49:05,400 --> 00:49:14,960
i onda ovdje, ja samo idem za vraćanje svih polja biti odgovarajuće vrijednosti.

617
00:49:14,960 --> 00:49:22,500
I na samom kraju, vratit ćemo našu čvor.

618
00:49:22,500 --> 00:49:28,690
Dobro,. Jedna stvar je imati na umu da se ove funkcije ovdje

619
00:49:28,690 --> 00:49:34,320
će se vratiti pokazivač na memoriju koja je bila gomila-izdvojila.

620
00:49:34,320 --> 00:49:38,880
Što je lijepo o tome da je ovaj čvor sada -

621
00:49:38,880 --> 00:49:42,420
moramo ga proglasiti na hrpi, jer ako smo ga proglasio na stog

622
00:49:42,420 --> 00:49:45,050
ne bismo bili u mogućnosti to učiniti u ovoj funkciji kao što je ovaj.

623
00:49:45,050 --> 00:49:47,690
To sjećanje bi otići iz djelokruga

624
00:49:47,690 --> 00:49:51,590
i da će biti nevažeći ako smo pokušali pristupiti kasnije.

625
00:49:51,590 --> 00:49:53,500
Budući da smo progla gomila-dodijeljenog memorije,

626
00:49:53,500 --> 00:49:55,830
ćemo morati brinuti ga oslobađajući kasnije

627
00:49:55,830 --> 00:49:58,530
za naš program ne propuštati bilo sjećanje.

628
00:49:58,530 --> 00:50:01,270
Mi smo bili na punting da za sve ostalo u kodu

629
00:50:01,270 --> 00:50:02,880
Upravo zbog jednostavnosti miloga na vrijeme,

630
00:50:02,880 --> 00:50:05,610
ali ako ste ikada napisati funkciju koja izgleda ovako

631
00:50:05,610 --> 00:50:10,370
gdje imaš - neki ga zovu malloc ili realloc iznutra -

632
00:50:10,370 --> 00:50:14,330
Želite li biti sigurni da ste stavili nekakvu komentaru ovdje da kaže,

633
00:50:14,330 --> 00:50:29,970
hej, znate, vraća gomila-dodijeljeno čvor pokrenutog s položen-u vrijednosti.

634
00:50:29,970 --> 00:50:33,600
I onda želite da biste bili sigurni da ste stavili u nekakvu napomenu da kaže

635
00:50:33,600 --> 00:50:41,720
pozivatelj mora osloboditi vratio pamćenje.

636
00:50:41,720 --> 00:50:45,450
Na taj način, ako netko ikad ide i koristi tu funkciju,

637
00:50:45,450 --> 00:50:48,150
oni znaju da ono što su dobili natrag iz tog funkcije

638
00:50:48,150 --> 00:50:50,870
u nekom trenutku će morati biti oslobođen.

639
00:50:50,870 --> 00:50:53,940
>> Uz pretpostavku da je sve dobro i dobro ovdje,

640
00:50:53,940 --> 00:51:02,300
možemo ići dolje u našem kodu i zamijeniti sve te linije ovdje

641
00:51:02,300 --> 00:51:05,410
s pozivima na naš graditi čvor funkciji.

642
00:51:05,410 --> 00:51:08,170
Ajmo to jako brzo.

643
00:51:08,170 --> 00:51:15,840
Onaj dio koji ne idemo zamijeniti je ovaj dio ovdje dolje

644
00:51:15,840 --> 00:51:18,520
na dnu gdje smo zapravo žice do čvorova ukazati da jedni druge,

645
00:51:18,520 --> 00:51:21,030
jer to ne možemo učiniti u našoj funkciji.

646
00:51:21,030 --> 00:51:37,400
Ali, hajdemo to korijen = build_node (7); čvor * tri = build_node (3);

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

648
00:51:47,980 --> 00:51:52,590
I sada, mi smo također željeli dodati čvorova za -

649
00:51:52,590 --> 00:52:03,530
čvor * Pet = build_node (5); čvor * osam = build_node (8);

650
00:52:03,530 --> 00:52:09,760
a što je bio drugi čvor? Hajdemo vidjeti ovdje. Željeli smo također dodati 2 -

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

652
00:52:20,280 --> 00:52:26,850
Dobro,. U ovom trenutku, mi znamo da smo dobili 7, 3, 9, i 6

653
00:52:26,850 --> 00:52:30,320
sve ožičen na odgovarajući način, ali ono što o 5, 8, te dva?

654
00:52:30,320 --> 00:52:33,550
Da bi sve u odgovarajućem redoslijedu,

655
00:52:33,550 --> 00:52:39,230
znamo da tri pravo dijete je šest.

656
00:52:39,230 --> 00:52:40,890
Dakle, ako ćemo dodati 5,

657
00:52:40,890 --> 00:52:46,670
je 5 također spada u desnoj strani stabla od kojih tri je korijen,

658
00:52:46,670 --> 00:52:50,440
tako pet pripada kao lijevi dijete od 6 godina.

659
00:52:50,440 --> 00:52:58,650
Možemo to učiniti govoreći, šest -> left_child = pet;

660
00:52:58,650 --> 00:53:10,790
a zatim 8 pripada kao lijevi dijete od 9., tako devet -> left_child = osam;

661
00:53:10,790 --> 00:53:22,190
i onda 2 je lijevo dijete od tri, tako da možemo učiniti da se ovdje - ti -> left_child = dva;.

662
00:53:22,190 --> 00:53:27,730
Ako niste sasvim pratiti uz to, ja predlažem da ga izvući iz sebe.

663
00:53:27,730 --> 00:53:35,660
>> Dobro,. Ajmo spasiti ovu. Idemo van i pobrinite se izrađuje,

664
00:53:35,660 --> 00:53:40,760
i onda možemo dodati u našim sadrži pozive.

665
00:53:40,760 --> 00:53:44,120
Izgleda kao da je sve još uvijek sastavlja.

666
00:53:44,120 --> 00:53:51,790
Idemo u i dodati u nekim sadrži pozive.

667
00:53:51,790 --> 00:53:59,640
Opet, ja ću učiniti malo kopirati i zalijepiti.

668
00:53:59,640 --> 00:54:15,860
Sada ćemo potražiti 5, 8, i dva. Dobro,.

669
00:54:15,860 --> 00:54:28,330
Ajmo pobrinite se da sve ovo izgleda dobro i dalje. Sjajno! Spremite i zatvorite.

670
00:54:28,330 --> 00:54:33,220
Sada ćemo napraviti, sastaviti, a sada idemo pokrenuti.

671
00:54:33,220 --> 00:54:37,540
Iz rezultata, to izgleda kao sve radi samo lijepo i dobro.

672
00:54:37,540 --> 00:54:41,780
Sjajno! Tako sada imamo naše Sadrži funkcije napisano.

673
00:54:41,780 --> 00:54:46,160
Idemo dalje i početi raditi na tome da ubacite čvorova u stablu

674
00:54:46,160 --> 00:54:50,000
jer, kao što smo to radili upravo sada, stvari nisu jako lijepa.

675
00:54:50,000 --> 00:54:52,280
>> Ako se vratimo na specifikaciji,

676
00:54:52,280 --> 00:55:00,540
to od nas traži da napisati funkciju zove umetanje - opet, vraća bool

677
00:55:00,540 --> 00:55:04,400
za li ili ne bismo mogli umetnuti čvor u stablu -

678
00:55:04,400 --> 00:55:07,710
i onda je vrijednost za umetanje u stablo je naveden kao

679
00:55:07,710 --> 00:55:11,060
jedini argument za našu insert funkciji.

680
00:55:11,060 --> 00:55:18,180
Mi ćemo se vratiti true ako smo doista mogao umetnuti čvor koji sadrži vrijednost u stablu,

681
00:55:18,180 --> 00:55:20,930
što znači da smo, jednom, imao dovoljno memorije,

682
00:55:20,930 --> 00:55:24,840
i onda dva, da čvor nije već postoji u stablu od -

683
00:55:24,840 --> 00:55:32,170
zapamtite, nećemo imati dvostruke vrijednosti u stablo, samo da bi se stvari jednostavno.

684
00:55:32,170 --> 00:55:35,590
Dobro,. Povratak u kodu.

685
00:55:35,590 --> 00:55:44,240
Otvorite ga prema gore. Zoom malo, zatim se pomaknite prema dolje.

686
00:55:44,240 --> 00:55:47,220
Ajmo staviti umetak funkciju desno iznad sadrži.

687
00:55:47,220 --> 00:55:56,360
Opet, to će biti pozvani bool umetak (int vrijednost).

688
00:55:56,360 --> 00:56:01,840
Daj mu malo više prostora, a zatim, kao defaultu,

689
00:56:01,840 --> 00:56:08,870
ajmo staviti u zamjenu lažnom na samom kraju.

690
00:56:08,870 --> 00:56:22,620
Sada dolje na dnu, idemo naprijed i umjesto ručno izgradnju čvorova

691
00:56:22,620 --> 00:56:27,900
u glavni sebe te ih ožičenje do točke da jedni druge kao što smo radili,

692
00:56:27,900 --> 00:56:30,600
ćemo se osloniti na naše insert funkciju za to.

693
00:56:30,600 --> 00:56:35,510
Nećemo se osloniti na naše insert funkciji izgraditi cijeli stablo od nule samo još,

694
00:56:35,510 --> 00:56:39,970
nego ćemo dobiti osloboditi od tih linija - hrapavi komentirati iz ovih redaka -

695
00:56:39,970 --> 00:56:43,430
da izgrade čvorove 5, 8, i dva.

696
00:56:43,430 --> 00:56:55,740
A umjesto toga, mi ćemo ubaciti pozive na naše umetanje funkcije

697
00:56:55,740 --> 00:57:01,280
kako bi bili sigurni da je to zapravo radi.

698
00:57:01,280 --> 00:57:05,840
Ovdje ćemo ići.

699
00:57:05,840 --> 00:57:09,300
>> Sada smo komentirali iz ove linije.

700
00:57:09,300 --> 00:57:13,700
Mi imamo samo 7, 3, 9 i 6 u našem stablu u ovom trenutku.

701
00:57:13,700 --> 00:57:18,870
Da biste bili sigurni da je to sve radi,

702
00:57:18,870 --> 00:57:25,050
možemo smanjivanje, čine naš binarno stablo,

703
00:57:25,050 --> 00:57:30,750
ga pokrenuti, a možemo vidjeti da sadrži sada nam govori da smo potpuno u pravu -

704
00:57:30,750 --> 00:57:33,110
5, 8, te dva više nisu u stablo.

705
00:57:33,110 --> 00:57:37,960
Idi natrag u kodu,

706
00:57:37,960 --> 00:57:41,070
i kako ćemo umetnuti?

707
00:57:41,070 --> 00:57:46,290
Sjetite se što smo učinili kada smo zapravo umetanjem 5, 8, i dva ranije.

708
00:57:46,290 --> 00:57:50,100
Igrali smo tu Plinko igru ​​gdje smo počeli u korijenu,

709
00:57:50,100 --> 00:57:52,780
siđe stabla jedan po jedan po jedan

710
00:57:52,780 --> 00:57:54,980
dok smo pronašli odgovarajuću prazninu,

711
00:57:54,980 --> 00:57:57,570
i onda smo poslali u čvor na odgovarajuće mjesto.

712
00:57:57,570 --> 00:57:59,480
Mi ćemo učiniti istu stvar.

713
00:57:59,480 --> 00:58:04,070
To je u osnovi kao pisanje koda koji smo koristili u sadrži funkciju

714
00:58:04,070 --> 00:58:05,910
pronaći mjesto gdje je čvor bi trebao biti,

715
00:58:05,910 --> 00:58:10,560
i onda smo tek idući umetnuti čvor tamo.

716
00:58:10,560 --> 00:58:17,000
Počnimo da radi.

717
00:58:17,000 --> 00:58:24,200
>> Dakle, imamo čvor * cur = korijen, a mi samo ćeš slijediti sadrži kod

718
00:58:24,200 --> 00:58:26,850
dok smo da se to ne sasvim rade za nas.

719
00:58:26,850 --> 00:58:32,390
Mi ćemo ići kroz stabla, dok je trenutni element nije nula,

720
00:58:32,390 --> 00:58:45,280
i ako utvrdimo da cur je vrijednost jednaka vrijednosti koje smo pokušava ubaciti -

721
00:58:45,280 --> 00:58:49,600
dobro, ovo je jedan od slučajeva u kojima smo zapravo ne može umetnuti čvor

722
00:58:49,600 --> 00:58:52,730
u stablo, jer to znači da imamo duple vrijednosti.

723
00:58:52,730 --> 00:58:59,010
Ovdje mi zapravo idemo vratiti false.

724
00:58:59,010 --> 00:59:08,440
Sada, drugo, ako sad je vrijednost manja od vrijednosti,

725
00:59:08,440 --> 00:59:10,930
Sada znamo da se presele u desno

726
00:59:10,930 --> 00:59:17,190
 jer je vrijednost pripada u desnoj polovici sadašnje stanje stabla.

727
00:59:17,190 --> 00:59:30,110
Inače, mi smo idući u premjestiti na lijevoj strani.

728
00:59:30,110 --> 00:59:37,980
To je u osnovi naše Sadrži funkcionirati tamo.

729
00:59:37,980 --> 00:59:41,820
>> U ovom trenutku, nakon što smo završili ovaj while petlja,

730
00:59:41,820 --> 00:59:47,350
naša sad pokazivač će se ukazuje na nulu

731
00:59:47,350 --> 00:59:51,540
ako je funkcija još nije vratio.

732
00:59:51,540 --> 00:59:58,710
Stoga nailazite cur na mjestu gdje želimo umetnuti novi čvor.

733
00:59:58,710 --> 01:00:05,210
Što još treba učiniti je da zapravo izgraditi novi čvor,

734
01:00:05,210 --> 01:00:08,480
što možemo učiniti prilično lako.

735
01:00:08,480 --> 01:00:14,930
Možemo koristiti naše super-zgodan graditi funkciju čvora,

736
01:00:14,930 --> 01:00:17,210
i nešto što nismo ranije -

737
01:00:17,210 --> 01:00:21,400
samo mi nekako uzeo zdravo za gotovo, ali sada ćemo učiniti samo da bi bili sigurni -

738
01:00:21,400 --> 01:00:27,130
ćemo testirati kako bi bili sigurni da je vrijednost koju vraća novi čvor je zapravo

739
01:00:27,130 --> 01:00:33,410
nije null, jer ne želimo početi pristup da memoriju ako je null.

740
01:00:33,410 --> 01:00:39,910
Možemo testirati kako bi bili sigurni da novi čvor nije jednaka null.

741
01:00:39,910 --> 01:00:42,910
Ili umjesto toga, mi samo možemo vidjeti ako to je zapravo null,

742
01:00:42,910 --> 01:00:52,120
i ako je nula, onda možemo samo povratak false rano.

743
01:00:52,120 --> 01:00:59,090
>> U ovom trenutku, moramo spojiti novi čvor u svojoj odgovarajuće mjesto u stablo.

744
01:00:59,090 --> 01:01:03,510
Ako se osvrnemo na glavna i gdje smo bili zapravo ožičenje u vrijednosti prije,

745
01:01:03,510 --> 01:01:08,470
vidimo da je način na koji smo to čine kad smo htjeli staviti tri u stablo

746
01:01:08,470 --> 01:01:11,750
bio mi pogledana lijevu dijete korijena.

747
01:01:11,750 --> 01:01:14,920
Kad smo stavili 9 u stablo, morali smo pristupili pravo djeteta korijena.

748
01:01:14,920 --> 01:01:21,030
Morali smo imati pokazivač na roditelja kako bi se stavili novu vrijednost u stablo.

749
01:01:21,030 --> 01:01:24,430
Pomicanje natrag do umetnuti, da ne ide na prilično raditi ovdje

750
01:01:24,430 --> 01:01:27,550
jer mi nemamo pokazivač roditelj.

751
01:01:27,550 --> 01:01:31,650
Ono što mi želimo biti u mogućnosti to učiniti je, u ovom trenutku,

752
01:01:31,650 --> 01:01:37,080
provjerite roditelja vrijednost i vidjeti - dobro, bože,

753
01:01:37,080 --> 01:01:41,990
Ako roditelj je vrijednost manja od trenutne vrijednosti,

754
01:01:41,990 --> 01:01:54,440
Tada je roditeljsko pravo dijete treba biti novi čvor;

755
01:01:54,440 --> 01:02:07,280
inače, roditelj je lijevo dijete treba biti novi čvor.

756
01:02:07,280 --> 01:02:10,290
Ali, mi nemamo taj pokazivač roditelj još.

757
01:02:10,290 --> 01:02:15,010
>> Da bi ga dobili, mi zapravo idemo da su ga pratili kao što smo proći kroz stablo

758
01:02:15,010 --> 01:02:18,440
i pronaći odgovarajući mjesto u našoj petlji iznad.

759
01:02:18,440 --> 01:02:26,840
Mi možemo učiniti da do pomicanja natrag na vrh našeg umetanje funkcije

760
01:02:26,840 --> 01:02:32,350
i praćenje drugog pokazivača varijablu naziva roditelja.

761
01:02:32,350 --> 01:02:39,340
Mi ćemo ga postaviti jednaka null početku,

762
01:02:39,340 --> 01:02:43,640
i onda svaki put kad smo proći kroz stabla,

763
01:02:43,640 --> 01:02:51,540
idemo postaviti roditelj pokazivač odgovara trenutni pokazivač.

764
01:02:51,540 --> 01:02:59,140
Postavite roditelj jednak valutama.

765
01:02:59,140 --> 01:03:02,260
Na taj način, svaki put kad smo proći,

766
01:03:02,260 --> 01:03:05,550
idemo kako bi se osiguralo da kao trenutni pokazivač gets incremented

767
01:03:05,550 --> 01:03:12,640
roditelj pokazivač ga slijedi - samo jedan stupanj viša od trenutne pokazivačem u stablo.

768
01:03:12,640 --> 01:03:17,370
To sve izgleda prilično dobro.

769
01:03:17,370 --> 01:03:22,380
>> Mislim da je jedna stvar koju ćemo željeti prilagoditi je to izgraditi čvor vraća null.

770
01:03:22,380 --> 01:03:25,380
Da bi dobili izgraditi čvor zapravo uspješno vratiti null,

771
01:03:25,380 --> 01:03:31,060
ćemo morati mijenjati taj kod,

772
01:03:31,060 --> 01:03:37,270
jer ovdje, mi nikada ne testira kako bi bili sigurni da malloc vratio valjanu pokazivač.

773
01:03:37,270 --> 01:03:53,390
Dakle, ako je (n = NULL!), A zatim -

774
01:03:53,390 --> 01:03:55,250
ako malloc vratio valjanu pokazivač, onda ćemo ga inicijalizirati;

775
01:03:55,250 --> 01:04:02,540
inače, samo ćemo se vratiti i da će završiti vraća null za nas.

776
01:04:02,540 --> 01:04:13,050
Sada sve izgleda prilično dobro. Ajmo pazite ovo zapravo sastavlja.

777
01:04:13,050 --> 01:04:22,240
Napravite binarnog stabla, i oh, imamo neke stvari se ovdje događa.

778
01:04:22,240 --> 01:04:29,230
>> Imamo implicitna deklaracija funkcije izgraditi čvor.

779
01:04:29,230 --> 01:04:31,950
Opet, s tim prevodiocima, idemo početi na vrhu.

780
01:04:31,950 --> 01:04:36,380
Što da mora značiti da sam pozivom izgraditi čvor prije nego što sam zapravo sam ga proglasio.

781
01:04:36,380 --> 01:04:37,730
Vratimo se kod jako brzo.

782
01:04:37,730 --> 01:04:43,510
Pomaknite se prema dolje, i siguran dosta, moj umetak funkcija je proglašen

783
01:04:43,510 --> 01:04:47,400
iznad funkciju graditi čvor,

784
01:04:47,400 --> 01:04:50,070
ali ja sam pokušava koristiti graditi čvor unutar umetka.

785
01:04:50,070 --> 01:05:06,610
Ja idem u i primjerak - a zatim zalijepiti funkcije graditi čvor put ovdje na vrhu.

786
01:05:06,610 --> 01:05:11,750
Na taj način, nadamo se da će raditi. Dajmo ovaj drugi ići.

787
01:05:11,750 --> 01:05:18,920
Sada sve to sastavlja. Sve je dobro.

788
01:05:18,920 --> 01:05:21,640
>> No, u ovom trenutku, nismo zapravo zove naš umetnuti funkciju.

789
01:05:21,640 --> 01:05:26,510
Mi samo znamo da je to sastavlja, pa ajmo i staviti neke pozive u.

790
01:05:26,510 --> 01:05:28,240
Učinimo da u našem glavnom funkciji.

791
01:05:28,240 --> 01:05:32,390
Ovdje smo komentirali od 5, 8 i 2,

792
01:05:32,390 --> 01:05:36,680
i onda smo ih nije spojiti se ovdje dolje.

793
01:05:36,680 --> 01:05:41,640
Ajmo napraviti neki pozivi za umetanje,

794
01:05:41,640 --> 01:05:46,440
i ajmo također koristiti istu vrstu stvari koje smo koristili

795
01:05:46,440 --> 01:05:52,810
kad smo napravili ove printf pozive kako bi bili sigurni da je sve nije se pravilno umetnuta.

796
01:05:52,810 --> 01:06:00,550
Ja ću kopirati i zalijepiti,

797
01:06:00,550 --> 01:06:12,450
i umjesto sadrži ćemo učiniti umetak.

798
01:06:12,450 --> 01:06:30,140
I umjesto 6, 10, i jedan, idemo koristiti 5, 8 i 2.

799
01:06:30,140 --> 01:06:37,320
Ovaj nadamo trebao ubaciti 5, 8 i 2 u stablo.

800
01:06:37,320 --> 01:06:44,050
Sastaviti. Sve je dobro. Sada smo zapravo ćete pokrenuti naš program.

801
01:06:44,050 --> 01:06:47,330
>> Sve se vratio lažna.

802
01:06:47,330 --> 01:06:53,830
Dakle, pet, osam, a dva ne ide, a izgleda da ne sadrži ni pronaći ih bilo.

803
01:06:53,830 --> 01:06:58,890
Što se događa? Ajmo smanjivanje.

804
01:06:58,890 --> 01:07:02,160
Prvi problem je da umetnite činilo da se vrati false,

805
01:07:02,160 --> 01:07:08,750
i to izgleda kao da je to zato što smo otišli u našem povratku lažnog poziva,

806
01:07:08,750 --> 01:07:14,590
a mi nikada zapravo vratio istina.

807
01:07:14,590 --> 01:07:17,880
Možemo postaviti da gore.

808
01:07:17,880 --> 01:07:25,290
Drugi problem je, sada čak i ako to učinimo - spasiti to, prestati to,

809
01:07:25,290 --> 01:07:34,530
pokrenuti učiniti opet, to su sastaviti, a zatim ga pokrenuti -

810
01:07:34,530 --> 01:07:37,670
vidimo da se nešto drugo dogodilo ovdje.

811
01:07:37,670 --> 01:07:42,980
The 5, 8 i dvoje još nikada nisu pronađena u stablo.

812
01:07:42,980 --> 01:07:44,350
Dakle, ono što se događa?

813
01:07:44,350 --> 01:07:45,700
>> Ajmo pogledati ovo u kodu.

814
01:07:45,700 --> 01:07:49,790
Hajdemo vidjeti možemo li to shvatiti.

815
01:07:49,790 --> 01:07:57,940
Mi smo započeli s roditelj ne bude nula.

816
01:07:57,940 --> 01:07:59,510
Postavili smo trenutni pokazivač jednak korijena pokazivač,

817
01:07:59,510 --> 01:08:04,280
i idemo raditi svoj put prema dolje kroz stabla.

818
01:08:04,280 --> 01:08:08,650
Ako je trenutni čvor nije null, onda znamo da možemo kretati prema dolje malo.

819
01:08:08,650 --> 01:08:12,330
Postavili smo našu roditelj pokazivač biti jednaka trenutnoj pokazivač,

820
01:08:12,330 --> 01:08:15,420
Provjerio vrijednost - ako su iste vrijednosti i vratili smo se lažna.

821
01:08:15,420 --> 01:08:17,540
Ako su vrijednosti manje preselili smo se u pravo;

822
01:08:17,540 --> 01:08:20,399
inače, preselili smo se na lijevoj strani.

823
01:08:20,399 --> 01:08:24,220
Onda smo izgraditi čvor. Ja ću povećavanje malo.

824
01:08:24,220 --> 01:08:31,410
I ovdje, mi ćemo pokušati spojiti do vrijednosti biti isti.

825
01:08:31,410 --> 01:08:37,250
Što se događa? Idemo vidjeti ako eventualno Valgrind nam može dati savjet.

826
01:08:37,250 --> 01:08:43,910
>> Volim koristiti Valgrind samo zato Valgrind stvarno brzo pokreće

827
01:08:43,910 --> 01:08:46,729
i kaže vam, ako postoje bilo kakve memorije pogreške.

828
01:08:46,729 --> 01:08:48,300
Kada smo pokrenuli Valgrind na kodu,

829
01:08:48,300 --> 01:08:55,859
kao što možete vidjeti upravo hit here--Valgrind./binary_tree--and ući.

830
01:08:55,859 --> 01:09:03,640
Možete vidjeti da nismo imali nikakve memorijsku pogrešku, tako da izgleda kao da je sve u redu do sada.

831
01:09:03,640 --> 01:09:07,529
Imamo neke memory leaks, koje znamo, jer nismo

832
01:09:07,529 --> 01:09:08,910
događa se osloboditi bilo koji od naših čvorova.

833
01:09:08,910 --> 01:09:13,050
Pokušajmo trčanje gdb vidjeti što se zapravo događa.

834
01:09:13,050 --> 01:09:20,010
Učinit ćemo gdb. / Binary_tree. To dignut gore sasvim u redu.

835
01:09:20,010 --> 01:09:23,670
Ajmo postaviti break na umetkom.

836
01:09:23,670 --> 01:09:28,600
Ajmo pokrenuti.

837
01:09:28,600 --> 01:09:31,200
Izgleda mi nikada zapravo zove umetak.

838
01:09:31,200 --> 01:09:39,410
Izgleda da je problem bio samo da kad sam promijenio ovdje dolje u glavni -

839
01:09:39,410 --> 01:09:44,279
sve ove printf pozive iz sadrži -

840
01:09:44,279 --> 01:09:56,430
Nikad nisam zapravo promijenio to nazvati umetak.

841
01:09:56,430 --> 01:10:01,660
Sada ćemo dati ga probati. Ajmo sastaviti.

842
01:10:01,660 --> 01:10:09,130
Sve izgleda dobro tamo. Sada ćemo pokušati trčanje, vidjeti što se događa.

843
01:10:09,130 --> 01:10:13,320
Redu! Sve izgleda prilično dobro tamo.

844
01:10:13,320 --> 01:10:18,130
>> Konačna stvar razmišljati o je, postoje li rub slučajeva na ovim umetkom?

845
01:10:18,130 --> 01:10:23,170
I ispada da, dobro, jedan rub slučaj da je uvijek zanimljivo razmišljati o

846
01:10:23,170 --> 01:10:26,250
je, što se događa ako vaš stablo je prazno i ​​to nazivamo umetnuti funkciju?

847
01:10:26,250 --> 01:10:30,330
Hoće li raditi? Pa, neka je dati ga probati.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Način da ćemo ovaj test je, idemo ići dolje na naš glavni funkciji,

850
01:10:35,810 --> 01:10:41,690
i umjesto elektroinstalacija ove čvorova ovako,

851
01:10:41,690 --> 01:10:56,730
samo mi ćemo komentirati van cijelu stvar,

852
01:10:56,730 --> 01:11:02,620
i umjesto žica do čvorova i nas samih,

853
01:11:02,620 --> 01:11:09,400
zapravo možemo samo ići naprijed i izbrisati sve ovo.

854
01:11:09,400 --> 01:11:17,560
Mi ćemo učiniti sve što je poziv za umetanje.

855
01:11:17,560 --> 01:11:49,020
Dakle, ajmo napraviti - umjesto 5, 8 i 2, idemo umetnuti 7, 3 i 9.

856
01:11:49,020 --> 01:11:58,440
A onda ćemo također želite umetnuti 6 kao dobro.

857
01:11:58,440 --> 01:12:05,190
Spremi. Prestani. Napravite binarnog stabla.

858
01:12:05,190 --> 01:12:08,540
To sve sastavlja.

859
01:12:08,540 --> 01:12:10,320
Mi samo možemo pokrenuti ga kao što je i vidjeti što se događa,

860
01:12:10,320 --> 01:12:12,770
ali to je također će biti jako važno kako bi bili sigurni da

861
01:12:12,770 --> 01:12:14,740
mi nemamo nikakve pogreške memorije,

862
01:12:14,740 --> 01:12:16,840
jer je to jedan od naših rubnih slučajeva za koje znamo o tome.

863
01:12:16,840 --> 01:12:20,150
>> Ajmo pobrinite se da dobro radi pod Valgrind,

864
01:12:20,150 --> 01:12:28,310
što ćemo učiniti samo trčanje Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Čini se kao da smo doista imaju jednu pogrešku iz jednog konteksta -

866
01:12:31,110 --> 01:12:33,790
imamo ovu segmentacije grešku.

867
01:12:33,790 --> 01:12:36,690
Što se dogodilo?

868
01:12:36,690 --> 01:12:41,650
Valgrind zapravo govori nam gdje je.

869
01:12:41,650 --> 01:12:43,050
Udalji malo.

870
01:12:43,050 --> 01:12:46,040
To izgleda kao da se događa u našem insert funkciji,

871
01:12:46,040 --> 01:12:53,420
gdje smo nevažeći pročitati veličine 4 na umetkom, linija 60.

872
01:12:53,420 --> 01:13:03,590
Ajmo se vratiti i vidjeti što se ovdje događa.

873
01:13:03,590 --> 01:13:05,350
Udalji stvarno brzo.

874
01:13:05,350 --> 01:13:14,230
Želim da biste bili sigurni da se ne ide do ruba zaslona tako da možemo vidjeti sve.

875
01:13:14,230 --> 01:13:18,760
Povucite da u malo. Dobro,.

876
01:13:18,760 --> 01:13:35,030
Pomaknite se prema dolje, a problem je upravo ovdje.

877
01:13:35,030 --> 01:13:40,120
Što će se dogoditi ako smo dobili dolje i naš trenutni čvor je već null,

878
01:13:40,120 --> 01:13:44,010
naš roditelj čvor null, pa ako ćemo gledati gore na samom vrhu, upravo ovdje -

879
01:13:44,010 --> 01:13:47,340
ako je to while petlja nikad zapravo izvršava

880
01:13:47,340 --> 01:13:52,330
jer je naša trenutna vrijednost je null - naš korijen null pa sad je null -

881
01:13:52,330 --> 01:13:57,810
onda naš roditelj nikada ne dobiva postavljen na valutama ili s važećom vrijednosti,

882
01:13:57,810 --> 01:14:00,580
tako, roditelj će također biti nula.

883
01:14:00,580 --> 01:14:03,700
Trebamo se sjetiti da provjerite da

884
01:14:03,700 --> 01:14:08,750
u vrijeme kada smo dobili ovdje dolje, i možemo početi pristup roditelja na vrijednosti.

885
01:14:08,750 --> 01:14:13,190
Dakle, što se događa? Pa, ako roditelj null -

886
01:14:13,190 --> 01:14:17,990
if (roditelj == NULL) - onda znamo da je

887
01:14:17,990 --> 01:14:19,530
ne smije biti ništa u stablo.

888
01:14:19,530 --> 01:14:22,030
Moramo biti težak da ga umetnuti u korijenu.

889
01:14:22,030 --> 01:14:32,570
Mi možemo učiniti da samo postavljanje korijen jednak novog čvora.

890
01:14:32,570 --> 01:14:40,010
Zatim u ovom trenutku, mi zapravo ne želite proći kroz tih drugih stvari.

891
01:14:40,010 --> 01:14:44,780
Umjesto toga, ovdje, možemo napraviti bilo drugo-ako-drugo,

892
01:14:44,780 --> 01:14:47,610
ili smo mogli kombinirati sve do ovdje u drugi,

893
01:14:47,610 --> 01:14:56,300
ali ovdje ćemo samo koristiti drugi i učiniti ga na taj način.

894
01:14:56,300 --> 01:14:59,030
Sada, idemo testirati kako bi bili sigurni da je naš roditelj nije null

895
01:14:59,030 --> 01:15:02,160
prije toga zapravo pokušava pristupiti polja.

896
01:15:02,160 --> 01:15:05,330
To će nam pomoći da se izbjegne segmentacije grešku.

897
01:15:05,330 --> 01:15:14,740
Dakle, mi otkaz, smanjivanje, sastaviti, pokrenuti.

898
01:15:14,740 --> 01:15:18,130
>> Nema pogreške, ali još uvijek imamo hrpu memorijskih curenja

899
01:15:18,130 --> 01:15:20,650
jer mi nije bilo osloboditi od naših čvorova.

900
01:15:20,650 --> 01:15:24,350
Ali, ako idemo do ovdje i gledamo naše ispisa,

901
01:15:24,350 --> 01:15:30,880
vidimo da, dobro, izgleda kao i svi naši umetcima su se vraćali istina, što je dobro.

902
01:15:30,880 --> 01:15:33,050
Pločice su sve istina,

903
01:15:33,050 --> 01:15:36,670
, a zatim odgovarajući sadrži pozivi su također istina.

904
01:15:36,670 --> 01:15:41,510
>> Dobar posao! Čini se kao da smo uspješno sam napisao umetak.

905
01:15:41,510 --> 01:15:47,430
To je sve što imamo za ovotjednom specifikacija problema Set.

906
01:15:47,430 --> 01:15:51,720
Jedan zabavan izazov da razmišljaju o tome kako bi zapravo ići u

907
01:15:51,720 --> 01:15:55,340
i bez svih čvorova u ovom stablu.

908
01:15:55,340 --> 01:15:58,830
Mi možemo učiniti tako veliki broj različitih načina,

909
01:15:58,830 --> 01:16:01,930
ali ja ću ostaviti da do vas pokusa,

910
01:16:01,930 --> 01:16:06,080
i kao zabava izazov, probajte i uvjerite se da možete biti sigurni

911
01:16:06,080 --> 01:16:09,490
da je ovo izvješće Valgrind vraća bez greške i nema curenja.

912
01:16:09,490 --> 01:16:12,880
>> Sretno na ovotjednom Huffman ovo kodiranje problema setu,

913
01:16:12,880 --> 01:16:14,380
pa ćemo vidjeti sljedeći tjedan!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]