1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [§ 7] [Vähem Mugav]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Harvardi Ülikool]

3
00:00:04,890 --> 00:00:07,000
[See on CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Tere tulemast 7. jagu.

5
00:00:09,080 --> 00:00:11,330
Tänu orkaani Sandy,

6
00:00:11,330 --> 00:00:13,440
selle asemel tavaline osa sel nädalal

7
00:00:13,440 --> 00:00:17,650
me teeme seda läbikäidav, läbi osa küsimustele.

8
00:00:17,650 --> 00:00:22,830
Ma lähen pärast koos Ülesanded 6 spetsifikatsiooniga,

9
00:00:22,830 --> 00:00:25,650
ja läbimas kõik küsimused

10
00:00:25,650 --> 00:00:27,770
Osas Küsimuste osa.

11
00:00:27,770 --> 00:00:30,940
Kui on mingeid küsimusi,

12
00:00:30,940 --> 00:00:32,960
palun kirjuta need edasi CS50 arutada.

13
00:00:32,960 --> 00:00:35,480
>> Olgu. Alustuseks.

14
00:00:35,480 --> 00:00:40,780
Just nüüd ma vaatan, lk 3 Ülesanded spetsifikatsioon.

15
00:00:40,780 --> 00:00:44,110
Me läheme esimese hakata rääkima kahendpuuks

16
00:00:44,110 --> 00:00:47,850
kuna need on palju tähtsust sel nädalal lahendamist -

17
00:00:47,850 --> 00:00:49,950
Huffman Tree kodeeringus.

18
00:00:49,950 --> 00:00:55,000
Üks esimesi andmestruktuurid me rääkisime edasi CS50 oli massiiv.

19
00:00:55,000 --> 00:01:00,170
Pea meeles, et massiiv on jada elemendid -

20
00:01:00,170 --> 00:01:04,019
kõik sama tüüpi - salvestatud õige üksteise kõrval mällu.

21
00:01:04,019 --> 00:01:14,420
Kui mul on täisarv massiivis, et saan juhtida kasutades seda kastid-numbrid-täisarvud stiil -

22
00:01:14,420 --> 00:01:20,290
Oletame, et mul on 5 esimeses kastis, mul on 7 teiseks

23
00:01:20,290 --> 00:01:27,760
siis on mul 8, 10 ja 20 viimases kasti.

24
00:01:27,760 --> 00:01:33,000
Pea meeles, et need kaks väga häid asju selle massiivi

25
00:01:33,000 --> 00:01:38,800
on, et meil on see pidev tööajaga juurdepääsu mõni konkreetne element

26
00:01:38,800 --> 00:01:40,500
 aastal massiivi kui me teame oma indeks.

27
00:01:40,500 --> 00:01:44,670
Näiteks kui ma tahan haarata kolmas element massiivi -

28
00:01:44,670 --> 00:01:47,870
kell indeks 2 kasutades meie nullpõhise indekseerimise süsteemi -

29
00:01:47,870 --> 00:01:52,220
Ma sõna otseses mõttes lihtsalt teha lihtne matemaatiline arvutus,

30
00:01:52,220 --> 00:01:56,170
hop selle positsiooni massiiv,

31
00:01:56,170 --> 00:01:57,840
tõmmake 8, ladustatakse seal,

32
00:01:57,840 --> 00:01:59,260
ja ma olen hea minna.

33
00:01:59,260 --> 00:02:03,350
>> Üks halbu asju selle massiivi - et me rääkisime

34
00:02:03,350 --> 00:02:05,010
kui me arutasime seotud loetelud -

35
00:02:05,010 --> 00:02:09,120
on see, et kui ma tahan lisada element selle massiivi

36
00:02:09,120 --> 00:02:11,090
Ma lähen tegema mõned vahepeal liigutada.

37
00:02:11,090 --> 00:02:12,940
Näiteks see massiiv siin

38
00:02:12,940 --> 00:02:16,850
on järjestatud järjekorras - sortida tõusvas järjestuses -

39
00:02:16,850 --> 00:02:19,440
5, siis 7, siis 8, siis 10 ja siis 20 -

40
00:02:19,440 --> 00:02:23,100
aga kui ma tahan lisada number 9 sinna massiivi

41
00:02:23,100 --> 00:02:27,460
Ma pean minema mõned elemendid, et teha ruumi.

42
00:02:27,460 --> 00:02:30,440
Saame selle siin.

43
00:02:30,440 --> 00:02:35,650
Ma pean liikuma 5, 7, ja siis 8;

44
00:02:35,650 --> 00:02:38,720
luua lõhe, kus ma saan panna 9,

45
00:02:38,720 --> 00:02:45,910
ja siis 10 ja 20 ei saa minna paremale 9.

46
00:02:45,910 --> 00:02:49,450
See on selline valu, sest halvimal juhul -

47
00:02:49,450 --> 00:02:54,350
kui meil oli lisada kas alguses või lõpus

48
00:02:54,350 --> 00:02:56,040
massiiv, sõltuvalt sellest, kuidas me minnes -

49
00:02:56,040 --> 00:02:58,850
me võiksime lõpuks võttes suunata kõik elemendid

50
00:02:58,850 --> 00:03:00,750
et me praegu hoidmiseks massiivi.

51
00:03:00,750 --> 00:03:03,810
>> Niisiis, milline oli võimalus seda?

52
00:03:03,810 --> 00:03:09,260
Teistpidi oli see, et minna meie viidatumad nimekirja meetod, kus -

53
00:03:09,260 --> 00:03:19,820
asemel ladustamiseks elemendid 5, 7, 8, 10 ja 20 kõik üksteise kõrval mälu -

54
00:03:19,820 --> 00:03:25,630
mida me selle asemel tegi, oli hoida neid omamoodi kus iganes me tahame hoida neid

55
00:03:25,630 --> 00:03:32,470
nendes viidatumad nimekirja tippu, mida ma joonistan siia, selline ad hoc.

56
00:03:32,470 --> 00:03:42,060
Ja siis me ühendatud neid koos kasutades neid järgmisel lähtekohtadeks.

57
00:03:42,060 --> 00:03:44,370
Võin olla osuti 5 kuni 7,

58
00:03:44,370 --> 00:03:46,420
pointer alates 7 kuni 8,

59
00:03:46,420 --> 00:03:47,770
pointer alates 8 kuni 10,

60
00:03:47,770 --> 00:03:51,220
ja lõpuks, pointer alates 10 kuni 20,

61
00:03:51,220 --> 00:03:54,880
ja siis null pointer 20. viitab sellele, et seal on midagi vasakule.

62
00:03:54,880 --> 00:03:59,690
Kompromiss, mis meil siin

63
00:03:59,690 --> 00:04:05,360
on see, et nüüd, kui me tahame, et sisestada number 9 meie järjestatud nimekirja,

64
00:04:05,360 --> 00:04:08,270
kõik me peame tegema, on luua uus sõlm 9,

65
00:04:08,270 --> 00:04:12,290
traat see üles märkida sobiv koht,

66
00:04:12,290 --> 00:04:20,630
ja siis uuesti juhe 8 punkti alla 9.

67
00:04:20,630 --> 00:04:25,660
See on päris kiire, eeldades, me teame täpselt, kus me tahame lisada 9.

68
00:04:25,660 --> 00:04:32,610
Aga kompromiss vastutasuks on see, et oleme nüüd kadunud pidev tööajaga juurdepääsu

69
00:04:32,610 --> 00:04:36,230
et mõni konkreetne element meie andmestruktuur.

70
00:04:36,230 --> 00:04:40,950
Näiteks kui ma tahan leida neljanda elemendi käesolevas seotud nimekirja,

71
00:04:40,950 --> 00:04:43,510
Ma pean alustama alguses nimekirja

72
00:04:43,510 --> 00:04:48,930
ja töö mu teed läbi lugedes sõlme kaupa sõlme kuni leian neljas.

73
00:04:48,930 --> 00:04:55,870
>> Selleks, et saada parem juurdepääs jõudlust kui lingitud nimekiri -

74
00:04:55,870 --> 00:04:59,360
kuid säilitavad ka mõningaid eeliseid, et meil oli

75
00:04:59,360 --> 00:05:01,800
poolest sisestamise aja alates lingitud nimekiri -

76
00:05:01,800 --> 00:05:05,750
kahendpuu läheb vaja kasutada natuke rohkem mälu.

77
00:05:05,750 --> 00:05:11,460
Eelkõige asemel lihtsalt võttes kursorit kahendpuu tipp -

78
00:05:11,460 --> 00:05:13,350
nagu investeerimisriskiga-list sõlme ei -

79
00:05:13,350 --> 00:05:16,950
me kavatseme lisada teine ​​kursor kahendpuu sõlme.

80
00:05:16,950 --> 00:05:19,950
Selle asemel, et lihtsalt võttes kursor järgmisele element,

81
00:05:19,950 --> 00:05:24,420
me lähed on kursor vasakule laps ja õigus lapse.

82
00:05:24,420 --> 00:05:26,560
>> Joonistame pildil, et näha, milline see tegelikult välja näeb.

83
00:05:26,560 --> 00:05:31,350
Jällegi, ma lähen kasutada neid karpe ja nooled.

84
00:05:31,350 --> 00:05:37,150
Kahendpuu tipp alustad lihtsalt kast.

85
00:05:37,150 --> 00:05:40,940
See saab olema ruumi väärtus,

86
00:05:40,940 --> 00:05:47,280
ja siis see ka läheb on ruumi vasakul laps ja õigus lapse.

87
00:05:47,280 --> 00:05:49,280
Ma lähen märgistama siin.

88
00:05:49,280 --> 00:05:57,560
Me läheme pea vasakule laps, ja siis me lähed on õigus laps.

89
00:05:57,560 --> 00:05:59,920
Seal on palju erinevaid viise.

90
00:05:59,920 --> 00:06:02,050
Mõnikord ruumi ja mugavuse

91
00:06:02,050 --> 00:06:06,460
Ma tegelikult joonistada nagu ma siin teen alt

92
00:06:06,460 --> 00:06:10,910
kus ma lähen on väärtus ülaosas,

93
00:06:10,910 --> 00:06:14,060
ja siis õige laps põhjale paremas,

94
00:06:14,060 --> 00:06:16,060
ja vasakule lapse alt vasakule.

95
00:06:16,060 --> 00:06:20,250
Tulles tagasi selle ülemine diagramm

96
00:06:20,250 --> 00:06:22,560
meil väärtus tipus,

97
00:06:22,560 --> 00:06:25,560
siis on meil vasaku laps pointer, ja siis on meil õigus-lapse pointer.

98
00:06:25,560 --> 00:06:30,110
>> Aastal Ülesanded spetsifikatsioon,

99
00:06:30,110 --> 00:06:33,110
me räägime joonistus sõlme, mis on väärtus 7,

100
00:06:33,110 --> 00:06:39,750
ja siis vasakule ja lapse osuti, mis on null, ja õigus-lapse osuti, mis on null.

101
00:06:39,750 --> 00:06:46,040
Me võime kirjutada kapitali NULL ruumis jaoks

102
00:06:46,040 --> 00:06:51,610
nii vasak laps ja õigus lapse või saame teha seda diagonaal kaldkriipsuga

103
00:06:51,610 --> 00:06:53,750
kaudu iga kastid näitavad, et see on null.

104
00:06:53,750 --> 00:06:57,560
Ma lähen tegema, et lihtsalt sellepärast, et on lihtsam.

105
00:06:57,560 --> 00:07:03,700
Mida sa näed siin on kaks võimalust skeemide väga lihtne kahendpuu sõlme

106
00:07:03,700 --> 00:07:07,960
kus meil on väärtus 7 ja null laps suunanäitajaks.

107
00:07:07,960 --> 00:07:15,220
>> Teine osa meie spetsifikatsioon räägib, kuidas koos seotud loetelud -

108
00:07:15,220 --> 00:07:18,270
Pea meeles, et meil oli ainult kinni hoida kõige esimene element nimekirja

109
00:07:18,270 --> 00:07:20,270
meeles pidada kogu nimekiri -

110
00:07:20,270 --> 00:07:26,140
ja samamoodi koos kahendpuu, meil on ainult kinni hoida ühte kursorit puu

111
00:07:26,140 --> 00:07:31,120
et säilitada kontrolli kogu andmestruktuuri.

112
00:07:31,120 --> 00:07:36,150
See spetsiaalne element puu nimetatakse root node puu.

113
00:07:36,150 --> 00:07:43,360
Näiteks kui üks sõlm - see sõlm sisaldab Maksumus 7

114
00:07:43,360 --> 00:07:45,500
koos null vasakul ja paremal laps suunanäitajaks -

115
00:07:45,500 --> 00:07:47,360
olid ainult väärtus meie puu,

116
00:07:47,360 --> 00:07:50,390
siis see oleks meie juurest sõlme.

117
00:07:50,390 --> 00:07:52,240
See on algusest peale meie puu.

118
00:07:52,240 --> 00:07:58,530
Me näeme seda veidi selgemalt kui me alustada lisades rohkem sõlmede meie puu.

119
00:07:58,530 --> 00:08:01,510
Las ma tõmba uus lehekülg.

120
00:08:01,510 --> 00:08:05,000
>> Nüüd me ei kavatse teha puu, mis on 7 keskmes,

121
00:08:05,000 --> 00:08:10,920
ja 3 sees vasakul laps, ja 9 seest õigus laps.

122
00:08:10,920 --> 00:08:13,500
Jällegi, see on üsna lihtne.

123
00:08:13,500 --> 00:08:26,510
Meil 7, joonistada sõlm 3, sõlm 9,

124
00:08:26,510 --> 00:08:32,150
ja ma lähen seatud vasak-lapse osuti 7. osutada sõlm sisaldab 3,

125
00:08:32,150 --> 00:08:37,850
ja õigus-lapse pointer sõlme sisaldavad 7 sõlme sisaldab 9.

126
00:08:37,850 --> 00:08:42,419
Nüüd, kuna 3 ja 9 ei ole ka lapsi,

127
00:08:42,419 --> 00:08:48,500
me ei kavatse seada kõik oma lapse suunanäitajaks olla null.

128
00:08:48,500 --> 00:08:56,060
Siin just meie puu vastab sõlme sisaldav number 7.

129
00:08:56,060 --> 00:09:02,440
Te näete, et kui kõik meil on viit, et root node,

130
00:09:02,440 --> 00:09:07,330
saame siis kõndida läbi meie puu-ja juurdepääsu nii tütartippu -

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

132
00:09:10,630 --> 00:09:14,820
Pole vaja säilitada viiteid iga sõlme puul.

133
00:09:14,820 --> 00:09:22,080
Olgu. Nüüd me ei kavatse lisada veel sõlme sellele diagramm.

134
00:09:22,080 --> 00:09:25,370
Me läheme lisada sõlm sisaldab 6

135
00:09:25,370 --> 00:09:34,140
ja me kavatseme lisada see nagu õige laps sõlm sisaldab 3.

136
00:09:34,140 --> 00:09:41,850
Selleks, et ma lähen kustutan selle null pointer 3-sõlme

137
00:09:41,850 --> 00:09:47,750
ja traat see üles osutada sõlm sisaldab 6. Olgu.

138
00:09:47,750 --> 00:09:53,800
>> Sel hetkel, lähme üle natuke terminoloogia.

139
00:09:53,800 --> 00:09:58,230
Et alustada, põhjusel, et seda nimetatakse kahendpuu eriti

140
00:09:58,230 --> 00:10:00,460
on see, et tal on kaks last suunanäitajaks.

141
00:10:00,460 --> 00:10:06,020
Seal on muud liiki puid, mis on rohkem lapse suunanäitajaks.

142
00:10:06,020 --> 00:10:10,930
Eelkõige sa tegid "proovida" on Ülesanded nr 5.

143
00:10:10,930 --> 00:10:19,310
Märkad, et sellisel proovida, siis tuli 27 erinevat viiteid erinevatele lastele -

144
00:10:19,310 --> 00:10:22,410
üks iga 26 tähte inglise tähestik,

145
00:10:22,410 --> 00:10:25,410
ja siis 27. kohta ülakoma -

146
00:10:25,410 --> 00:10:28,900
nii, mis on sarnane puuliik.

147
00:10:28,900 --> 00:10:34,070
Aga siin, sest see on binaarne, meil on ainult kaks last suunanäitajaks.

148
00:10:34,070 --> 00:10:37,880
>> Lisaks sellele Juursõlme et me rääkisime,

149
00:10:37,880 --> 00:10:41,470
Samuti oleme viskamine selle ümber mõiste "laps".

150
00:10:41,470 --> 00:10:44,470
Mis see tähendab ühe sõlme olla laps teise sõlme?

151
00:10:44,470 --> 00:10:54,060
Ta sõna otseses mõttes tähendab, et laps sõlm on laps teise sõlme

152
00:10:54,060 --> 00:10:58,760
kui see teine ​​sõlm on üks tema laps vihjeid seatud osutavad, et sõlme.

153
00:10:58,760 --> 00:11:01,230
Plaanide elluviimiseks Konkreetsemalt öeldes

154
00:11:01,230 --> 00:11:11,170
kui 3 osutas ühe lapse suunanäitajaks, 7., siis 3 on lapse 7..

155
00:11:11,170 --> 00:11:14,510
Kui olime aru saada, mida lapsed 7. on -

156
00:11:14,510 --> 00:11:18,510
Noh, me näeme, et 7 on kursor 3 ja kursor 9,

157
00:11:18,510 --> 00:11:22,190
nii 9 ja 3 on lapsed 7.

158
00:11:22,190 --> 00:11:26,650
Üheksa tal ei ole lapsi, sest tema laps osuti on null,

159
00:11:26,650 --> 00:11:30,940
ja 3 on ainult üks laps, 6.

160
00:11:30,940 --> 00:11:37,430
Kuus on ka lapsi ei ole, sest nii tema lähtekohtadeks on null, mis me teha just praegu.

161
00:11:37,430 --> 00:11:45,010
>> Lisaks on meil ka rääkida vanematele eriti sõlme,

162
00:11:45,010 --> 00:11:51,100
ja see on, nagu te tahaks oodata, vastupidi selle lapse kirjeldus.

163
00:11:51,100 --> 00:11:58,620
Igal tipul on vaid üks vanem - kahe asemel nagu oleksite võinud inimestega.

164
00:11:58,620 --> 00:12:03,390
Näiteks lapsevanem 3 on 7.

165
00:12:03,390 --> 00:12:10,800
Vanem 9. on ka 7 ja vanem 6. on 3. Mitte palju ta.

166
00:12:10,800 --> 00:12:15,720
Meil on ka mõttes rääkida vanavanemad ja lapselapsed,

167
00:12:15,720 --> 00:12:18,210
ja üldisemalt rääkides esivanemad

168
00:12:18,210 --> 00:12:20,960
ja järeltulijad eriti sõlme.

169
00:12:20,960 --> 00:12:25,710
Esivanem sõlme - või esivanemad, pigem on sõlm -

170
00:12:25,710 --> 00:12:32,730
on kõik sõlmed, mis asuvad teed juurest selle sõlme.

171
00:12:32,730 --> 00:12:36,640
Näiteks kui ma vaatan sõlme 6

172
00:12:36,640 --> 00:12:46,430
Seejärel esivanemad ei kavatse olla nii 3 ja 7.

173
00:12:46,430 --> 00:12:55,310
Esivanemad 9, näiteks on - kui ma vaatan sõlme 9 -

174
00:12:55,310 --> 00:12:59,990
siis esivanem 9. on vaid 7.

175
00:12:59,990 --> 00:13:01,940
Ja järeltulijad on täpselt vastupidine.

176
00:13:01,940 --> 00:13:05,430
Kui ma tahan vaadata kõiki järeltulijad 7,

177
00:13:05,430 --> 00:13:11,020
siis ma pean vaatama kõiki tippe all.

178
00:13:11,020 --> 00:13:16,950
Nii, mul on 3, 9 ja 6 kõik nagu järeltulijad 7.

179
00:13:16,950 --> 00:13:24,170
>> Lõpptähtaeg et me räägime on see mõiste on vend.

180
00:13:24,170 --> 00:13:27,980
Õed-vennad - omamoodi pärast mööda neid pere mõttes -

181
00:13:27,980 --> 00:13:33,150
on sõlmed, mis on samal tasemel puus.

182
00:13:33,150 --> 00:13:42,230
Niisiis, 3 ja 9 on õed-vennad, sest nad on samal tasemel puus.

183
00:13:42,230 --> 00:13:46,190
Nad mõlemad on sama emaettevõtja, 7.

184
00:13:46,190 --> 00:13:51,400
6 ei ole õdesid-vendi, sest 9 ei ole ka lapsi.

185
00:13:51,400 --> 00:13:55,540
Ja 7 ei ole õdesid-vendi, sest see on just meie puu,

186
00:13:55,540 --> 00:13:59,010
ja seal on ainult kunagi 1 root.

187
00:13:59,010 --> 00:14:02,260
7 on õed-vennad seal peaks olema sõlme üle 7.

188
00:14:02,260 --> 00:14:07,480
Seal peaks olema vanem, 7., mispuhul 7 oleks enam puu juur.

189
00:14:07,480 --> 00:14:10,480
Siis, et uus vanem, 7. oleks ka olla laps,

190
00:14:10,480 --> 00:14:16,480
ja et laps oleks siis vend 7..

191
00:14:16,480 --> 00:14:21,040
>> Olgu. Liigume edasi.

192
00:14:21,040 --> 00:14:24,930
Kui me alustasime meie arutelu kahendpuuks,

193
00:14:24,930 --> 00:14:28,790
me rääkisime sellest, kuidas me ei kavatse neid kasutada

194
00:14:28,790 --> 00:14:32,800
saada eelise nii massiivid ja lingitud nimekirjad.

195
00:14:32,800 --> 00:14:37,220
Ja kuidas me teeme, mis on selle tellimise vara.

196
00:14:37,220 --> 00:14:41,080
Me ütleme, et kahendpuu tellitakse vastavalt spetsifikatsioonile,

197
00:14:41,080 --> 00:14:45,740
kui iga sõlme meie puu, kõik tema järeltulijad vasakul -

198
00:14:45,740 --> 00:14:48,670
vasak laps ja kõik vasakule lapse järeltulijad -

199
00:14:48,670 --> 00:14:54,510
on vähem väärtusi, ja kõik sõlmed paremal -

200
00:14:54,510 --> 00:14:57,770
õigus lapse ja kõik õige lapse järeltulijad -

201
00:14:57,770 --> 00:15:02,800
on sõlmede suurem väärtus aktiivse sõlme, et me vaatame.

202
00:15:02,800 --> 00:15:07,850
Lihtsalt lihtsus, me eeldada, et seal ei ole nodes meie puu.

203
00:15:07,850 --> 00:15:11,180
Näiteks sellel puul me ei hakka tegelema puhul

204
00:15:11,180 --> 00:15:13,680
kus meil on väärtus 7 keskmes

205
00:15:13,680 --> 00:15:16,720
 ja siis meil on ka väärtus 7 mujal puu.

206
00:15:16,720 --> 00:15:24,390
Sellisel juhul märkad, et see puu on tõepoolest tellinud.

207
00:15:24,390 --> 00:15:26,510
Meil on väärtus 7 keskmes.

208
00:15:26,510 --> 00:15:29,720
Kõik vasakul 7. -

209
00:15:29,720 --> 00:15:35,310
kui ma tagasi võtta kõik need väikesed märgid siin -

210
00:15:35,310 --> 00:15:40,450
kõik vasakule 7 - 3 ja 6 -

211
00:15:40,450 --> 00:15:49,410
need väärtused on nii alla 7, ja kõik paremale - mis on just see 9 -

212
00:15:49,410 --> 00:15:53,450
on suurem kui 7.

213
00:15:53,450 --> 00:15:58,650
>> See ei ole ainult tellitud puu sisaldavad need väärtused,

214
00:15:58,650 --> 00:16:03,120
kuid Joonistame veel mõned neist.

215
00:16:03,120 --> 00:16:05,030
Seal on tegelikult terve hulk võimalusi, et me saame sellega hakkama.

216
00:16:05,030 --> 00:16:09,380
Ma lähen kasutada stenografisti lihtsalt hoida asjad lihtsad, kus -

217
00:16:09,380 --> 00:16:11,520
mitte joonistus välja terve kasti-ja-nooled -

218
00:16:11,520 --> 00:16:14,220
Ma lihtsalt juhtida numbrid ja lisada nooli ühendab neid.

219
00:16:14,220 --> 00:16:22,920
Et alustada, me lihtsalt kirjutada meie originaalse puu uuesti kus meil oli 7 ja seejärel 3,

220
00:16:22,920 --> 00:16:25,590
ja siis 3 märkis tagasi õigus 6

221
00:16:25,590 --> 00:16:30,890
ja 7 oli õigus lapsele, et oli 9.

222
00:16:30,890 --> 00:16:33,860
Olgu. Mis on teine ​​võimalus, et me võiks kirjutada selle puu?

223
00:16:33,860 --> 00:16:38,800
Selle asemel, et 3 oleks vasakul laps 7,

224
00:16:38,800 --> 00:16:41,360
me oleks võinud ka 6 olla vasakul laps 7,

225
00:16:41,360 --> 00:16:44,470
ja siis 3 oleks vasakul laps 6.

226
00:16:44,470 --> 00:16:48,520
See näeks välja selline puu siinsamas, kus ma sain 7,

227
00:16:48,520 --> 00:16:57,860
siis 6, siis 3 ja 9 õige.

228
00:16:57,860 --> 00:17:01,490
Samuti ei pea olema 7-le meie juurest sõlme.

229
00:17:01,490 --> 00:17:03,860
Võiksime ka 6 nagu meie juurest sõlme.

230
00:17:03,860 --> 00:17:06,470
Mis oleks sinu arvates on?

231
00:17:06,470 --> 00:17:09,230
Kui me tahame säilitada seda tellida vara,

232
00:17:09,230 --> 00:17:12,970
kõik vasakule 6 peab olema väiksem kui see.

233
00:17:12,970 --> 00:17:16,540
Seal on ainult üks võimalus, ja see on 3.

234
00:17:16,540 --> 00:17:19,869
Aga siis kui õige laps 6, meil on kaks võimalust.

235
00:17:19,869 --> 00:17:25,380
Esiteks, me võiks olla 7 ja siis 9,

236
00:17:25,380 --> 00:17:28,850
või me võime teha seda - nagu ma olen umbes teha siin -

237
00:17:28,850 --> 00:17:34,790
kus meil on 9, kui õige laps 6

238
00:17:34,790 --> 00:17:39,050
ja siis 7-vasakule laps 9.

239
00:17:39,050 --> 00:17:44,240
>> Nüüd, 7 ja 6 ei ole võimalik ainult väärtused juur.

240
00:17:44,240 --> 00:17:50,200
Võiksime ka 3 olla root.

241
00:17:50,200 --> 00:17:52,240
Mis juhtub, kui 3 on keskmes?

242
00:17:52,240 --> 00:17:54,390
Siin asjad natuke huvitav.

243
00:17:54,390 --> 00:17:58,440
Kolm ei ole mingit väärtust, mis on väiksem kui see,

244
00:17:58,440 --> 00:18:02,070
nii et kogu vasak pool puud on lihtsalt saab olema null.

245
00:18:02,070 --> 00:18:03,230
Seal ei kavatse olla midagi seal.

246
00:18:03,230 --> 00:18:07,220
Paremale, me võime üles loetleda asjad tõusvas järjekorras.

247
00:18:07,220 --> 00:18:15,530
Meil võiks olla 3, siis 6, siis 7, siis 9.

248
00:18:15,530 --> 00:18:26,710
Või me võiksime teha 3, siis 6, siis 9, siis 7.

249
00:18:26,710 --> 00:18:35,020
Või me võiksime teha 3, siis 7, siis 6, siis 9.

250
00:18:35,020 --> 00:18:40,950
Või, 3, 7 - tegelikult ei, me ei saa 7 enam.

251
00:18:40,950 --> 00:18:43,330
See on meie üks asi seal.

252
00:18:43,330 --> 00:18:54,710
Me saame seda teha 9, ja siis 9 me saame teha 6 ja seejärel 7.

253
00:18:54,710 --> 00:19:06,980
Või saame 3, siis 9, siis 7 ja seejärel 6.

254
00:19:06,980 --> 00:19:12,490
>> Üks asi juhtida teie tähelepanu siin

255
00:19:12,490 --> 00:19:14,510
et need puud on natuke imelik ilmega.

256
00:19:14,510 --> 00:19:17,840
Eriti kui me vaatame 4 puud paremal -

257
00:19:17,840 --> 00:19:20,930
Ma ringi neid, siin -

258
00:19:20,930 --> 00:19:28,410
need puud näevad välja peaaegu täpselt nagu seotud nimekirja.

259
00:19:28,410 --> 00:19:32,670
Igal tipul on vaid üks laps,

260
00:19:32,670 --> 00:19:38,950
ja nii me ei ole sellest midagi puu-like struktuur, mida me näeme, näiteks

261
00:19:38,950 --> 00:19:44,720
 Käesolevas üks üksik puu siin all vasakul.

262
00:19:44,720 --> 00:19:52,490
Need puud on tegelikult nn degenereerunud kahendpuuks,

263
00:19:52,490 --> 00:19:54,170
ja me räägime neist tulevikus rohkem -

264
00:19:54,170 --> 00:19:56,730
eriti kui sa lähed võtma teiste infotehnoloogia kursusi.

265
00:19:56,730 --> 00:19:59,670
Need puud on mandunud.

266
00:19:59,670 --> 00:20:03,780
Nad ei ole väga kasulik, sest tõesti, seda struktuuri sobiv

267
00:20:03,780 --> 00:20:08,060
 lookup korda sarnane seotud nimekirja.

268
00:20:08,060 --> 00:20:13,050
Me ei saa ära extra mälu - see pildi pointer -

269
00:20:13,050 --> 00:20:18,840
sest meie struktuur on halb sel viisil.

270
00:20:18,840 --> 00:20:24,700
Selle asemel, et minna ja venitama kahendpuuks et on 9 keskmes,

271
00:20:24,700 --> 00:20:27,220
mis on viimane juhtum, et meil oleks,

272
00:20:27,220 --> 00:20:32,380
me oleme selle asemel, sel hetkel, räägi natuke selle muu termin

273
00:20:32,380 --> 00:20:36,150
et me kasutame rääkides puud, mida nimetatakse kõrgus.

274
00:20:36,150 --> 00:20:45,460
>> Kõrgus puu on vahemaa juurest kõige-kauge sõlme,

275
00:20:45,460 --> 00:20:48,370
või pigem arvu humal, mida oleks võinud teha, et

276
00:20:48,370 --> 00:20:53,750
alustada juurest ja siis lõpuks kõige-kauge sõlme puu.

277
00:20:53,750 --> 00:20:57,330
Kui me vaatame mõned neist puud, et oleme tõmmatud siin,

278
00:20:57,330 --> 00:21:07,870
näeme, et kui me võtame selle puu ülemises vasakus nurgas ja hakkame kell 3,

279
00:21:07,870 --> 00:21:14,510
siis on meil teha 1 hüppe saada 6, teine ​​hop saada 7,

280
00:21:14,510 --> 00:21:20,560
ja kolmanda hüppe saada 9.

281
00:21:20,560 --> 00:21:26,120
Niisiis, kõrgus see puu on 3.

282
00:21:26,120 --> 00:21:30,640
Me võime teha sama harjutus teised puud kirjeldatud käesoleva roheline,

283
00:21:30,640 --> 00:21:40,100
ja me näeme, et kõrgus on kõik need puud on ka tõepoolest 3.

284
00:21:40,100 --> 00:21:45,230
See on osa sellest, mis teeb neid degenereerunud -

285
00:21:45,230 --> 00:21:53,750
et nende kõrgus on vaid üks väiksem arv tippe kogu puu.

286
00:21:53,750 --> 00:21:58,400
Kui me vaatame seda muu puu, mis on piirati punane, teiselt poolt,

287
00:21:58,400 --> 00:22:03,920
näeme, et kõige kauges tipud on 6 ja 9 -

288
00:22:03,920 --> 00:22:06,940
jätab olid need sõlmed, mis ei ole lapsi.

289
00:22:06,940 --> 00:22:11,760
Nii, et saada root node kas 6 või 9

290
00:22:11,760 --> 00:22:17,840
meil teha ühe hüppe, et saada 7 ja siis teise hüppe saada 9,

291
00:22:17,840 --> 00:22:21,240
ja samuti, ainult teine ​​hüpe 7, et saada 6.

292
00:22:21,240 --> 00:22:29,080
Niisiis, kõrgus see puu siin on ainult 2.

293
00:22:29,080 --> 00:22:35,330
Võite minna tagasi ja teha, et kõik teised puud, mis me varem arutatud

294
00:22:35,330 --> 00:22:37,380
alustades 7 ja 6,

295
00:22:37,480 --> 00:22:42,500
ja leiad, et kõrgus kõik need puud on ka 2.

296
00:22:42,500 --> 00:22:46,320
>> Põhjus, miks me oleme rääkinud tellitud kahendpuuks

297
00:22:46,320 --> 00:22:50,250
ja miks nad on lahedad, sest saate otsida neid

298
00:22:50,250 --> 00:22:53,810
väga sarnaselt otsides üle järjestatud massiivist.

299
00:22:53,810 --> 00:22:58,720
See on koht, kus me räägime saada, et parem lookup aeg

300
00:22:58,720 --> 00:23:02,730
üle lihtne seotud nimekirja.

301
00:23:02,730 --> 00:23:05,010
Mis lingitud nimekiri - kui soovite leida konkreetne element -

302
00:23:05,010 --> 00:23:07,470
sa oled parim teen mingi lineaarne otsing

303
00:23:07,470 --> 00:23:10,920
kui hakkate alguses nimekiri ja hop ühe poolt-üks -

304
00:23:10,920 --> 00:23:12,620
ühe sõlme ühe sõlme -

305
00:23:12,620 --> 00:23:16,060
läbi kogu nimekiri kuni leiad mida iganes te otsite.

306
00:23:16,060 --> 00:23:19,440
Arvestades, kui teil on kahendpuu, mis on salvestatud selles kena formaadis,

307
00:23:19,440 --> 00:23:23,300
tegelikult võite saada rohkem binaarne otsing toimub

308
00:23:23,300 --> 00:23:25,160
kus sa jaga ja valitse

309
00:23:25,160 --> 00:23:29,490
ja otsida sobiv poole puu igal sammul.

310
00:23:29,490 --> 00:23:32,840
Vaatame, kuidas see toimib.

311
00:23:32,840 --> 00:23:38,850
>> Kui meil on - jälle läheb tagasi meie algse puu -

312
00:23:38,850 --> 00:23:46,710
alustame kell 7, meil on 3 vasakul, 9 paremal

313
00:23:46,710 --> 00:23:51,740
ja all 3, siis 6.

314
00:23:51,740 --> 00:24:01,880
Kui tahame otsida number 6 see puu, me tahaks alustada keskmes.

315
00:24:01,880 --> 00:24:08,910
Meil oleks võrrelda väärtust me otsime, ütleme 6

316
00:24:08,910 --> 00:24:12,320
kuni väärtust salvestatud sõlme, et me praegu vaadates, 7,

317
00:24:12,320 --> 00:24:21,200
leiavad, et 6 on tõepoolest vähem kui 7, nii et me tahaks liikuda vasakule.

318
00:24:21,200 --> 00:24:25,530
Kui väärtus 6. olnud suurem kui 7, oleksime selle asemel liigutada paremale.

319
00:24:25,530 --> 00:24:29,770
Kuna me teame, et - tänu struktuuri meie tellitud kahendpuu -

320
00:24:29,770 --> 00:24:33,910
kõik väärtused alla 7 ei kavatse hoida vasakul 7,

321
00:24:33,910 --> 00:24:40,520
pole vaja isegi vaeva otsides paremal pool puud.

322
00:24:40,520 --> 00:24:43,780
Kui me liikuda vasakule ja me oleme nüüd sõlme, mis sisaldavad 3,

323
00:24:43,780 --> 00:24:48,110
me saame teha, et sama võrdlus uuesti, kui me võrdleme 3 ja 6.

324
00:24:48,110 --> 00:24:52,430
Ja me leiame, et kuigi 6 - raha me otsime - on suurem kui 3,

325
00:24:52,430 --> 00:24:58,580
saame minna paremale küljele sõlme sisaldab 3.

326
00:24:58,580 --> 00:25:02,670
Pole vasakul siin, nii et me oleks võinud eirata seda.

327
00:25:02,670 --> 00:25:06,510
Aga me teame ainult, et kuna me vaatleme puu ise,

328
00:25:06,510 --> 00:25:08,660
ja näeme, et puul on lapsed.

329
00:25:08,660 --> 00:25:13,640
>> See on ka üsna lihtne otsida 6 seda puud, kui me teeme seda ise inimestele,

330
00:25:13,640 --> 00:25:16,890
kuid olgem selle protsessi mehhaaniliselt nagu arvuti teeks

331
00:25:16,890 --> 00:25:18,620
tõesti mõista algoritm.

332
00:25:18,620 --> 00:25:26,200
Sel hetkel, me oleme nüüd vaadates sõlme, mis sisaldab 6

333
00:25:26,200 --> 00:25:29,180
ja me otsime väärtus 6,

334
00:25:29,180 --> 00:25:31,740
jah, tõepoolest, me leidsime sobiva sõlme.

335
00:25:31,740 --> 00:25:35,070
Leidsime väärtus 6 meie puust ja saame lõpetada meie otsingumootorit.

336
00:25:35,070 --> 00:25:37,330
Sel hetkel, sõltuvalt, mis toimub,

337
00:25:37,330 --> 00:25:41,870
võime öelda, jah, oleme leidnud väärtus 6, see eksisteerib meie puu.

338
00:25:41,870 --> 00:25:47,640
Või kui me plaanite lisada sõlme või midagi, mida me teha saame, et selles punktis.

339
00:25:47,640 --> 00:25:53,010
>> Teeme veel paar otsingud lihtsalt näha, kuidas see toimib.

340
00:25:53,010 --> 00:25:59,390
Vaatame, mis juhtub, kui me proovida ja otsida väärtus 10.

341
00:25:59,390 --> 00:26:02,970
Kui me otsida väärtus 10, me hakkaks keskmes.

342
00:26:02,970 --> 00:26:07,070
Tahame näha, et 10 on suurem kui 7, nii et me tahaks liikuda paremale.

343
00:26:07,070 --> 00:26:13,640
Soovime saada 9 ja võrrelge 9. 10 ja vaata, et 9 on tõepoolest alla 10.

344
00:26:13,640 --> 00:26:16,210
Nii et taas, me tahaks proovida liikuda paremale.

345
00:26:16,210 --> 00:26:20,350
Aga sel hetkel, me tahaks teada, et me oleme null sõlme.

346
00:26:20,350 --> 00:26:23,080
Seal pole midagi. Ei ole midagi, kus 10 peaks olema.

347
00:26:23,080 --> 00:26:29,360
See on koht, kus saame aru jätmine - et tegelikkuses ei ole 10 puud.

348
00:26:29,360 --> 00:26:35,420
Ja lõpuks, lähme läbi juhul, kui me üritame üles otsima 1 puu.

349
00:26:35,420 --> 00:26:38,790
See on sarnane, mis juhtub kui me vaatame kuni 10, välja arvatud asemel läheb paremale,

350
00:26:38,790 --> 00:26:41,260
me läheme vasakule.

351
00:26:41,260 --> 00:26:46,170
Alustame kell 7 ja näha, et 1 on väiksem kui 7, nii et me liigume vasakule.

352
00:26:46,170 --> 00:26:51,750
Saame 3 ja näha, et 1 on väiksem kui 3, siis jälle püüame liikuda vasakule.

353
00:26:51,750 --> 00:26:59,080
Sel hetkel on meil null sõlme, nii et jälle saame aru rike.

354
00:26:59,080 --> 00:27:10,260
>> Kui sa tahad rohkem teada kahendpuuks,

355
00:27:10,260 --> 00:27:14,420
seal on terve hulk lõbus vähe probleeme, mida saate teha nendega.

356
00:27:14,420 --> 00:27:19,450
Pakun praktiseerivad joonistus välja neist skeemidest ühe poolt-üks

357
00:27:19,450 --> 00:27:21,910
ja pärast läbi kõik erinevad astmed,

358
00:27:21,910 --> 00:27:25,060
sest see tulla super-mugav

359
00:27:25,060 --> 00:27:27,480
mitte ainult kui sa teed Huffman kodeering probleem komplekt

360
00:27:27,480 --> 00:27:29,390
vaid ka tulevaste kursused -

361
00:27:29,390 --> 00:27:32,220
lihtsalt õppida, kuidas juhtida läbi neid andmestruktuure ja mõelda läbi probleemide

362
00:27:32,220 --> 00:27:38,000
pliiatsi ja paberi või sel juhul, iPad ja pliiatsiga.

363
00:27:38,000 --> 00:27:41,000
>> Sel hetkel aga, me läheme edasi liikuda, et teha mõned kodeerimine tava

364
00:27:41,000 --> 00:27:44,870
ja tegelikult mängida neid kahendpuuks ja vaata.

365
00:27:44,870 --> 00:27:52,150
Ma lähen, et minna tagasi üle minu arvuti.

366
00:27:52,150 --> 00:27:58,480
Selle osa jagu, selle asemel CS50 Run või CS50 Spaces,

367
00:27:58,480 --> 00:28:01,500
Ma lähen kasutage seadet.

368
00:28:01,500 --> 00:28:04,950
>> Pärast koos Ülesanded spetsifikatsioon,

369
00:28:04,950 --> 00:28:07,740
Ma näen, et ma peaksin avama seadme

370
00:28:07,740 --> 00:28:11,020
lähen oma Dropbox kausta luua kausta nimega 7. jagu,

371
00:28:11,020 --> 00:28:15,730
ja siis looge fail nimega binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Läheb lahti. Mul aparaat juba avatud.

373
00:28:22,050 --> 00:28:25,910
Ma lähen tõmba terminal.

374
00:28:25,910 --> 00:28:38,250
Ma lähen minema Dropbox kausta teha kataloogi nimega section7,

375
00:28:38,250 --> 00:28:42,230
ja vaata, et see on täiesti tühi.

376
00:28:42,230 --> 00:28:48,860
Nüüd ma lähen avama binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Olgu. Läheb lahti - tühi fail.

378
00:28:51,750 --> 00:28:54,330
>> Lähme tagasi spetsifikatsioon.

379
00:28:54,330 --> 00:28:59,850
Spetsifikatsioon küsib uue tüübi definitsioon

380
00:28:59,850 --> 00:29:03,080
jaoks kahendpuu sõlme sisaldav int väärtusi -

381
00:29:03,080 --> 00:29:07,110
nagu väärtused, mida me juhtis tähelepanu meie skeemide enne.

382
00:29:07,110 --> 00:29:11,740
Me ei kavatse kasutada seda trafaretset typedef et me oleme teinud siin

383
00:29:11,740 --> 00:29:14,420
et sa peaksid tunnustama alates Ülesanded 5 -

384
00:29:14,420 --> 00:29:19,190
kui sa hash tabelis viis vallutavad speller programmile.

385
00:29:19,190 --> 00:29:22,540
Sa peaksid ka tunda seda eelmise nädala jagu

386
00:29:22,540 --> 00:29:23,890
kus me rääkisime seotud nimekirju.

387
00:29:23,890 --> 00:29:27,870
Meil see typedef on struct tipp,

388
00:29:27,870 --> 00:29:34,430
ja me andsime selle struct tipp see nimi struct tipp eelnevalt

389
00:29:34,430 --> 00:29:39,350
nii et saame siis nimetavad seda kuna me tahame struct tipp viiteid

390
00:29:39,350 --> 00:29:45,740
Osana meie struct, kuid me oleme siis ümbritseb seda -

391
00:29:45,740 --> 00:29:47,700
või pigem kinnine seda - typedef

392
00:29:47,700 --> 00:29:54,600
nii et hiljem kood, saame tähistada seda struct kui lihtsalt sõlme asemel struct tipp.

393
00:29:54,600 --> 00:30:03,120
>> See saab olema väga sarnane üksikult seotud nimekirja määratlus, et me nägime eelmisel nädalal.

394
00:30:03,120 --> 00:30:20,070
Selleks, lähme lihtsalt alustada kirjalikult esitatud trafaretset.

395
00:30:20,070 --> 00:30:23,840
Me teame, et meil peab olema täisarv,

396
00:30:23,840 --> 00:30:32,170
nii me panna int väärtus, ja siis selle asemel, et lihtsalt üks kursor järgmisele element -

397
00:30:32,170 --> 00:30:33,970
nagu tegime koos üksikult seotud nimekirju -

398
00:30:33,970 --> 00:30:38,110
me lähed on vasak ja parem laps suunanäitajaks.

399
00:30:38,110 --> 00:30:42,880
See on päris lihtne ka - struct tipp * vasak laps;

400
00:30:42,880 --> 00:30:51,190
ja struct tipp * õigus lapse. Lahe.

401
00:30:51,190 --> 00:30:54,740
See näeb välja nagu päris hea algus.

402
00:30:54,740 --> 00:30:58,530
Lähme tagasi spetsifikatsioon.

403
00:30:58,530 --> 00:31:05,030
>> Nüüd tuleb tunnistada maailma tipp * muutuja puu juurt.

404
00:31:05,030 --> 00:31:10,590
Me kavatseme teha selles maailmas nagu me esmajärjekorras osuti meie seotud nimekirja ka globaalne.

405
00:31:10,590 --> 00:31:12,690
See oli nii, et neid funktsioone, mis me kirjutame

406
00:31:12,690 --> 00:31:16,180
me ei pea hoidma kulgeb ümber selle juur -

407
00:31:16,180 --> 00:31:19,620
kuigi me näeme, et kui sa tahad kirjutada neid funktsioone rekursiivselt,

408
00:31:19,620 --> 00:31:22,830
see võib olla parem isegi mitte andke seda ümber globaalse esimese koha

409
00:31:22,830 --> 00:31:28,090
ja selle asemel initsialiseerida seda kohapeal oma põhifunktsiooni.

410
00:31:28,090 --> 00:31:31,960
Aga me teeme seda kogu maailmas, et alustada.

411
00:31:31,960 --> 00:31:39,920
Jällegi anname paar ruumid, ja ma lähen kuulutada sõlme * juur.

412
00:31:39,920 --> 00:31:46,770
Lihtsalt veendumaks, et ma ei jäta seda uninitialized, ma lähen, et seada see võrdub null.

413
00:31:46,770 --> 00:31:52,210
Nüüd, mille peamine ülesanne - mis me kirjutame tõesti kiiresti siin -

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
ja ma lähen alustada kuulutatakse minu argv array const lihtsalt nii, et ma tean

416
00:32:10,640 --> 00:32:14,550
et need argumendid on argumendid, et ma ilmselt ei taha muuta.

417
00:32:14,550 --> 00:32:18,390
Kui ma tahan neid muuta ma peaks ilmselt tegemist nende koopiad.

418
00:32:18,390 --> 00:32:21,740
Näete seda palju koodi.

419
00:32:21,740 --> 00:32:25,440
See on hea ükskõik kummale poole. See on hea, et jätta see - jätta const, kui soovite.

420
00:32:25,440 --> 00:32:28,630
Ma tavaliselt pannakse see lihtsalt nii, et ma meelde endale

421
00:32:28,630 --> 00:32:33,650
 et ma ilmselt ei taha muuta need argumendid.

422
00:32:33,650 --> 00:32:39,240
>> Nagu alati, ma lähen lisada see return 0 liini lõpus peamine.

423
00:32:39,240 --> 00:32:45,730
Siin ma initsialiseerida minu juurest sõlme.

424
00:32:45,730 --> 00:32:48,900
Praegusel kujul just nüüd, mul on osuti, mis on seatud null,

425
00:32:48,900 --> 00:32:52,970
nii see osutavad midagi.

426
00:32:52,970 --> 00:32:57,480
Et tegelikult alustada hoone sõlme,

427
00:32:57,480 --> 00:32:59,250
Ma kõigepealt mälu eraldada see.

428
00:32:59,250 --> 00:33:05,910
Ma lähen tegema, et tehes mälu hunnik kasutades malloc.

429
00:33:05,910 --> 00:33:10,660
Ma lähen määratud juur võrdne tulemus malloc,

430
00:33:10,660 --> 00:33:19,550
ja ma lähen kasutada sizeof operaator arvutada suurus sõlme.

431
00:33:19,550 --> 00:33:24,990
Põhjusel, et ma kasutan sizeof sõlme asemel, ütleme,

432
00:33:24,990 --> 00:33:37,020
teeme midagi sellist - malloc (4 + 4 +4) või malloc 12 -

433
00:33:37,020 --> 00:33:40,820
on, sest ma tahan, et mu eeskiri peaks olema ühilduv kui võimalik.

434
00:33:40,820 --> 00:33:44,540
Ma tahan, et oleks võimalik seda. C faili kompileerida seadmele

435
00:33:44,540 --> 00:33:48,820
ja seejärel kompileerida see minu 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
või hoopis arhitektuur -

437
00:33:52,040 --> 00:33:54,640
ja ma tahan, et see kõik töötama sama.

438
00:33:54,640 --> 00:33:59,510
>> Kui ma olen tegemise eeldusi suurus muutujad -

439
00:33:59,510 --> 00:34:02,070
suurus int või suuruse pointer -

440
00:34:02,070 --> 00:34:06,070
siis ma ka teha oletusi selle kohta, milliseid arhitektuur

441
00:34:06,070 --> 00:34:10,440
millest minu koodi saab edukalt koostada, kui joosta.

442
00:34:10,440 --> 00:34:15,030
Kasutage alati sizeof erinevalt käsitsi liidetakse struct valdkondades.

443
00:34:15,030 --> 00:34:20,500
Teine põhjus on see, et seal võiks olla ka polster et tõlkija lastavate struct.

444
00:34:20,500 --> 00:34:26,570
Isegi lihtsalt summeerides üksikute andmeväljade ei ole midagi, mida sa tavaliselt tahad teha,

445
00:34:26,570 --> 00:34:30,340
jah, kustutage see rida.

446
00:34:30,340 --> 00:34:33,090
Nüüd, tõesti initsialiseerida see Juursõlme,

447
00:34:33,090 --> 00:34:36,489
Ma pean ühendada väärtused iga selle erinevates valdkondades.

448
00:34:36,489 --> 00:34:41,400
Näiteks väärtuse Ma tean, ma tahan initsialiseerida kuni 7,

449
00:34:41,400 --> 00:34:46,920
ja nüüd ma lähen seatud vasakul laps olla null

450
00:34:46,920 --> 00:34:55,820
ja õigus lapsel olla ka null. Suurepärane!

451
00:34:55,820 --> 00:35:02,670
Oleme teinud selles osas spec.

452
00:35:02,670 --> 00:35:07,390
>> Spetsifikatsioon alla allosas lehekülg 3 küsib minult, et luua veel kolm tippu -

453
00:35:07,390 --> 00:35:10,600
üks sisaldab 3, üks sisaldab 6 ja üks 9 -

454
00:35:10,600 --> 00:35:14,210
ja siis juhe nad nii see näeb välja täpselt nagu meie puudiagramm

455
00:35:14,210 --> 00:35:17,120
et me rääkisime varem.

456
00:35:17,120 --> 00:35:20,450
Teeme seda päris kiiresti siin.

457
00:35:20,450 --> 00:35:26,270
Näete tõesti kiiresti, et ma lähen alustada kirjalikult hunnik dubleeritud koodi.

458
00:35:26,270 --> 00:35:32,100
Ma lähen luua sõlme * ja ma kutsun seda kolm.

459
00:35:32,100 --> 00:35:36,000
Ma lähen, et seada see võrdne malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Ma lähen püstitas kolm-> väärtus = 3.

461
00:35:41,070 --> 00:35:54,780
Kolm -> left_child = NULL; 3 -> õigus _child = NULL; samuti.

462
00:35:54,780 --> 00:36:01,150
See tundub üsna sarnane initsialiseerimisel juure, ja see on täpselt see, mida

463
00:36:01,150 --> 00:36:05,760
Ma lähen tegema, kui ma hakkan initsialiseerimisel 6 ja 9 ka.

464
00:36:05,760 --> 00:36:20,720
Ma teen seda tõesti kiiresti siin - tegelikult, ma teen natuke kopeeri ja kleebi

465
00:36:20,720 --> 00:36:46,140
ja veenduge, et I - igav.

466
00:36:46,470 --> 00:37:09,900
 Nüüd on mul see kopeerida ja võin minna ja seada see võrdub 6.

467
00:37:09,900 --> 00:37:14,670
Te näete, et see võtab natuke aega ja ei ole super-efektiivne.

468
00:37:14,670 --> 00:37:22,610
Vaid natuke, me kirjutame funktsiooni, et teeb seda meie eest.

469
00:37:22,610 --> 00:37:32,890
Ma tahan selle asendada 9, asendada, et koos 6.

470
00:37:32,890 --> 00:37:37,360
>> Nüüd on meil kõik meie keskuste loomist ja vormindatud.

471
00:37:37,360 --> 00:37:41,200
Meil meie juure määratud väärtus 7, või sisaldab väärtus 7,

472
00:37:41,200 --> 00:37:46,510
meie sõlm sisaldab 3, meie sõlm sisaldab 6, ja meie sõlm sisaldab 9.

473
00:37:46,510 --> 00:37:50,390
Sel hetkel, kõik me peame tegema, on traadi kõik üles.

474
00:37:50,390 --> 00:37:53,020
Põhjus, miks ma vormindatud kõik suunanäitajaks tühjaks on lihtsalt nii, et ma veenduge, et

475
00:37:53,020 --> 00:37:56,260
Mul ei ole ühtegi uninitialized osuti sinna juhuslikult.

476
00:37:56,260 --> 00:38:02,290
Ja ka, sest sel hetkel, mul on ainult tegelikult ühendada sõlmed omavahel -

477
00:38:02,290 --> 00:38:04,750
need, mis nad tegelikult ühendatud - ma ei pea minema läbi ja teeb

478
00:38:04,750 --> 00:38:08,240
Kontrollige, et kõik nulls on seal selleks ettenähtud kohtades.

479
00:38:08,240 --> 00:38:15,630
>> Algusega kell juur, ma tean, et juur vasak laps on 3.

480
00:38:15,630 --> 00:38:21,250
Ma tean, et juur on õigus laps on 9.

481
00:38:21,250 --> 00:38:24,880
Pärast seda, vaid teine ​​laps, et olen jäänud muretsema

482
00:38:24,880 --> 00:38:39,080
on 3 õigust last, mis on 6.

483
00:38:39,080 --> 00:38:44,670
Sel hetkel, see kõik tundub päris hea.

484
00:38:44,670 --> 00:38:54,210
Me neid kustutada ridu.

485
00:38:54,210 --> 00:38:59,540
Nüüd kõik tundub päris hea.

486
00:38:59,540 --> 00:39:04,240
Lähme tagasi meie spetsifikatsioon ja vaata, mis me peame tegema järgmisena.

487
00:39:04,240 --> 00:39:07,610
>> Sel hetkel, oleme kirjutada funktsioon nimega "sisaldab"

488
00:39:07,610 --> 00:39:14,150
koos prototüüp "bool sisaldab (int väärtus)".

489
00:39:14,150 --> 00:39:17,060
Ja see sisaldab funktsiooni läheb tagasi true

490
00:39:17,060 --> 00:39:21,200
 kui puu osutas Meie globaalne juure muutuja

491
00:39:21,200 --> 00:39:26,950
 sisaldab väärtust läks funktsioon ja vale teisiti.

492
00:39:26,950 --> 00:39:29,000
Lähme edasi ja tee seda.

493
00:39:29,000 --> 00:39:35,380
See saab olema täpselt nagu lookup, et me tegime käsitsi iPad natuke tagasi.

494
00:39:35,380 --> 00:39:40,130
Teeme uuesti suurendate natuke ja liikuge üles.

495
00:39:40,130 --> 00:39:43,130
Me paneme selle funktsiooni paremal kohal meie põhiülesanne

496
00:39:43,130 --> 00:39:48,990
nii et me ei pea tegema mingit prototüübid.

497
00:39:48,990 --> 00:39:55,960
Niisiis, bool sisaldab (int väärtus).

498
00:39:55,960 --> 00:40:00,330
Nii juba läheb. Seal on meie trafaretset deklaratsiooni.

499
00:40:00,330 --> 00:40:02,900
Lihtsalt veenduge, et see kogub,

500
00:40:02,900 --> 00:40:06,820
Ma lähen edasi minna ja lihtsalt pani võrdne tagasi false.

501
00:40:06,820 --> 00:40:09,980
Praegu see funktsioon lihtsalt ei tee midagi ja alati aru, et

502
00:40:09,980 --> 00:40:14,010
väärtus, mida me otsime ei ole puu.

503
00:40:14,010 --> 00:40:16,280
>> Sel hetkel, see on ilmselt hea mõte -

504
00:40:16,280 --> 00:40:19,600
kuna me oleme kirjutanud terve hunnik koodi ja me ei ole isegi proovinud testib seda veel -

505
00:40:19,600 --> 00:40:22,590
veenduda, et see kõik koostab.

506
00:40:22,590 --> 00:40:27,460
On paar asja, mida me peame tegema, veendumaks, et see on tegelikult kompileerida.

507
00:40:27,460 --> 00:40:33,530
Esiteks, kas me olen kasutanud mingeid muid funktsioone, mis tahes raamatukogude et me ei ole veel lisatud.

508
00:40:33,530 --> 00:40:37,940
Funktsioonide oleme kasutanud siiani on malloc,

509
00:40:37,940 --> 00:40:43,310
ja siis oleme ka kasutanud seda tüüpi - see ebastandartne tüüp nimega "bool' -

510
00:40:43,310 --> 00:40:45,750
mis on standardvarustuses bool header fail.

511
00:40:45,750 --> 00:40:53,250
Me kindlasti tahame lisada standard bool.h jaoks bool tüüpi,

512
00:40:53,250 --> 00:40:59,230
ja tahame ka # include standard lib.h jaoks standard raamatukogud

513
00:40:59,230 --> 00:41:03,530
mis sisaldavad malloc ja tasuta, ja kõik see.

514
00:41:03,530 --> 00:41:08,660
Nii, zoom out, me ei kavatse loobuda.

515
00:41:08,660 --> 00:41:14,190
Proovime ja veenduge, et see tegelikult ei kompileerida.

516
00:41:14,190 --> 00:41:18,150
Me näeme, et see, et me oleme õigel teel.

517
00:41:18,150 --> 00:41:22,990
>> Avame kuni binary_tree.c uuesti.

518
00:41:22,990 --> 00:41:34,530
Ta koostab. Lähme alla ja veenduge, et me lisada mõned kõned meie Contains funktsioon -

519
00:41:34,530 --> 00:41:40,130
lihtsalt veenduda, et kõik on hästi ja hea.

520
00:41:40,130 --> 00:41:43,170
Näiteks, kui me tegime mõned otsingud oma puu varem

521
00:41:43,170 --> 00:41:48,500
üritasime otsida väärtuste 6, 10 ja 1, ja me teadsime, et 6 oli puu,

522
00:41:48,500 --> 00:41:52,220
10 ei olnud puust ja 1 oli mitte puus kas.

523
00:41:52,220 --> 00:41:57,230
Olgem kasutada neid proovi kõned viis aru saada, kas

524
00:41:57,230 --> 00:41:59,880
meie Contains funktsioon töötab.

525
00:41:59,880 --> 00:42:05,210
Selleks, et ma lähen kasutada printf funktsiooni,

526
00:42:05,210 --> 00:42:10,280
ja me lähme välja printida tulemus üleskutse sisaldab.

527
00:42:10,280 --> 00:42:13,280
Ma lähen panna stringi "sisaldab (% d) = sest

528
00:42:13,280 --> 00:42:20,470
 me lähme pistik väärtus, et me ei kavatse otsida,

529
00:42:20,470 --> 00:42:27,130
ja =% s \ n "ja kasutada seda kui meie stringi.

530
00:42:27,130 --> 00:42:30,720
Me lihtsalt näeme - sõna otseses mõttes välja printida ekraanil -

531
00:42:30,720 --> 00:42:32,060
mis näeb välja nagu funktsioon kõne.

532
00:42:32,060 --> 00:42:33,580
See ei ole tegelikult funktsioon kõne.

533
00:42:33,580 --> 00:42:36,760
 See on lihtsalt string kavandatud sarnanema funktsioon kõne.

534
00:42:36,760 --> 00:42:41,140
>> Nüüd me ei kavatse ühendada väärtused.

535
00:42:41,140 --> 00:42:43,580
Me läheme proovida sisaldab 6

536
00:42:43,580 --> 00:42:48,340
ja siis me teeme siin kasutada, et kolmekomponentsete operaator.

537
00:42:48,340 --> 00:42:56,340
Vaatame - sisaldab 6 - nii, nüüd olen sisaldas 6 ja kui sisaldab 6 on tõsi,

538
00:42:56,340 --> 00:43:01,850
string, mis me kavatseme saata% s formaat iseloomu

539
00:43:01,850 --> 00:43:04,850
saab olema string "true".

540
00:43:04,850 --> 00:43:07,690
Olgem leidke üle natuke.

541
00:43:07,690 --> 00:43:16,210
Muidu me tahame saata stringi "vale" kui sisaldab 6 naaseb vale.

542
00:43:16,210 --> 00:43:19,730
See on veidi tobe välimusega, kuid ma kujutan ma võin ka illustreerivad

543
00:43:19,730 --> 00:43:23,780
mida kolmekomponentsete operaator välja näeb, sest me pole seda näinud mõnda aega.

544
00:43:23,780 --> 00:43:27,670
See on kena, mugav viis aru saada, kui meie Contains funktsioon töötab.

545
00:43:27,670 --> 00:43:30,040
Ma lähen tagasi kerima üle vasakule,

546
00:43:30,040 --> 00:43:39,900
ja ma lähen kopeeri ja kleebi see joon paar korda.

547
00:43:39,900 --> 00:43:44,910
See muutis mõned nende väärtuste ümber,

548
00:43:44,910 --> 00:43:59,380
nii et see saab olema 1 ja see saab olema 10.

549
00:43:59,380 --> 00:44:02,480
>> Sel hetkel on meil kena Contains funktsioon.

550
00:44:02,480 --> 00:44:06,080
Meil on mõned testid, ja me näeme, kui see kõik toimib.

551
00:44:06,080 --> 00:44:08,120
Sel hetkel oleme kirjutanud mõned rohkem kood.

552
00:44:08,120 --> 00:44:13,160
Aeg loobuda välja ja veenduge, et kõik ikka kogub.

553
00:44:13,160 --> 00:44:20,360
Lõpeta ära, ja nüüd proovime teha kahendpuu uuesti.

554
00:44:20,360 --> 00:44:22,260
Noh, tundub, et meil viga,

555
00:44:22,260 --> 00:44:26,930
Ja meil seda selgesõnaliselt kuulutab raamatukogu funktsiooni printf.

556
00:44:26,930 --> 00:44:39,350
Tundub, et me peame minema ja # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Ja, et kõik peaksid koostama. Oleme kõik hea.

558
00:44:45,350 --> 00:44:50,420
Nüüd proovime töötab kahendpuu ja vaata, mis juhtub.

559
00:44:50,420 --> 00:44:53,520
Siin me oleme. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
ja me näeme, et me ootasime -

561
00:44:55,190 --> 00:44:56,910
sest me ei ole rakendanud sisaldab veel,

562
00:44:56,910 --> 00:44:59,800
või õigemini, me oleme lihtsalt panna tagasi false -

563
00:44:59,800 --> 00:45:03,300
me näeme, et see on lihtsalt jälle vale neile kõigile,

564
00:45:03,300 --> 00:45:06,180
Nii et kõik töötavad enamasti üsna hästi.

565
00:45:06,180 --> 00:45:11,860
>> Lähme tagasi ja tegelikult rakendada sisaldab selles punktis.

566
00:45:11,860 --> 00:45:17,490
Ma lähen liikuge allapoole suurendada, ja -

567
00:45:17,490 --> 00:45:22,330
Pea meeles, et algoritm, mida me kasutada oli, et alustasime kell Juursõlme

568
00:45:22,330 --> 00:45:28,010
ja siis iga sõlme, et kohtame, me teeme võrdluse

569
00:45:28,010 --> 00:45:32,380
ja selle põhjal võrdlus me kas minna vasakule lapse või paremale laps.

570
00:45:32,380 --> 00:45:39,670
See läheb väga sarnased binaarne otsing kood, mis me kirjutasime varem perspektiivis.

571
00:45:39,670 --> 00:45:47,810
Kui me alustad, me teame, et me tahame säilitada oma aktiivse sõlme

572
00:45:47,810 --> 00:45:54,050
et me vaatame, ja praegune tipp saab olema initsialiseeritud Juursõlme.

573
00:45:54,050 --> 00:45:56,260
Ja nüüd, me ei kavatse hoida läbimas puud

574
00:45:56,260 --> 00:45:58,140
ja pidage meeles, et meie peatumine tingimus -

575
00:45:58,140 --> 00:46:01,870
 kui me tegelikult töötatud kaudu näiteks käsitsi -

576
00:46:01,870 --> 00:46:03,960
oli siis, kui oleme kohanud null sõlme,

577
00:46:03,960 --> 00:46:05,480
mitte siis, kui me vaatasime null laps,

578
00:46:05,480 --> 00:46:09,620
vaid siis, kui me tegelikult kolis sõlme puu

579
00:46:09,620 --> 00:46:12,640
ja leidis, et me oleme null sõlme.

580
00:46:12,640 --> 00:46:20,720
Me läheme itereerima kuni viim ei võrdu tühjaks.

581
00:46:20,720 --> 00:46:22,920
Ja mida me teeme?

582
00:46:22,920 --> 00:46:31,610
Me läheme testida, kui (viim -> väärtus == väärtus),

583
00:46:31,610 --> 00:46:35,160
siis me teame, et me oleme tegelikult leitud sõlme, et me otsime.

584
00:46:35,160 --> 00:46:40,450
Nii et siin, me saame naasta tõsi.

585
00:46:40,450 --> 00:46:49,830
Muidu me tahame näha, kas väärtus on väiksem kui väärtus.

586
00:46:49,830 --> 00:46:53,850
Kui praegune tipp väärtus on väiksem kui me otsime,

587
00:46:53,850 --> 00:46:57,280
me hakkame liikuma paremale.

588
00:46:57,280 --> 00:47:10,600
Nii viim = viim -> right_child; ja teisiti, me ei kavatse liikuda vasakule.

589
00:47:10,600 --> 00:47:17,480
viim = viim -> left_child;. Päris lihtne.

590
00:47:17,480 --> 00:47:22,830
>> Sa ilmselt tunda silmus, mis näeb välja väga sarnane sellele alates

591
00:47:22,830 --> 00:47:27,580
Kahendotsingupuu varem mõiste, välja arvatud siis me tegelesime madal, keskmine ja kõrge.

592
00:47:27,580 --> 00:47:30,000
Siin me lihtsalt peame vaatama jooksva väärtusega,

593
00:47:30,000 --> 00:47:31,930
nii et see on kena ja lihtne.

594
00:47:31,930 --> 00:47:34,960
Teeme kindel, et see kood töötab.

595
00:47:34,960 --> 00:47:42,780
Esiteks, veenduge, et see kogub. Paistab, et see teeb.

596
00:47:42,780 --> 00:47:47,920
Proovime läbiviimist.

597
00:47:47,920 --> 00:47:50,160
Ja tõepoolest, see prindib välja kõik, mida me lootsime.

598
00:47:50,160 --> 00:47:54,320
Ta leiab 6 puud, ei leia 10, sest 10 pole puus,

599
00:47:54,320 --> 00:47:57,740
ja ei leia 1 kas sest 1 on ka mitte puus.

600
00:47:57,740 --> 00:48:01,420
Lahe värk.

601
00:48:01,420 --> 00:48:04,470
>> Olgu. Lähme tagasi meie spetsifikatsioon ja vaata, mis edasi.

602
00:48:04,470 --> 00:48:07,990
Nüüd ta tahab lisada veel mõned sõlmed meie puu.

603
00:48:07,990 --> 00:48:11,690
Ta tahab lisada 5, 2 ja 8, ning veenduda, et meie sisaldab koodi

604
00:48:11,690 --> 00:48:13,570
töötab ootuspäraselt.

605
00:48:13,570 --> 00:48:14,900
Lähme teha.

606
00:48:14,900 --> 00:48:19,430
Sel hetkel, mitte tehes, et tüütu kopeeri ja kleebi uuesti,

607
00:48:19,430 --> 00:48:23,770
olgem kirjutada funktsioon tegelikult luua sõlme.

608
00:48:23,770 --> 00:48:27,740
Kui me kerige kõik viis peamist näeme, et me oleme seda teinud juba

609
00:48:27,740 --> 00:48:31,210
väga sarnane koodi ikka ja jälle iga kord, kui me tahame luua sõlme.

610
00:48:31,210 --> 00:48:39,540
>> Olgem kirjutada funktsioon, mis tegelikult ehitada sõlm meile ja tagastab selle.

611
00:48:39,540 --> 00:48:41,960
Ma kutsun seda build_node.

612
00:48:41,960 --> 00:48:45,130
Ma lähen üles ehitada sõlm eriline väärtus.

613
00:48:45,130 --> 00:48:51,040
Vähenda siin.

614
00:48:51,040 --> 00:48:56,600
Esimene asi, mida ma lähen tegema, on tegelikult luua ruumi sõlme hunnik.

615
00:48:56,600 --> 00:49:05,400
Niisiis, sõlme * n = malloc (sizeof (node)); n -> väärtus = väärtus;

616
00:49:05,400 --> 00:49:14,960
ja siis siin, ma lihtsalt läheb initsialiseerida kõik väljad olema sobivad väärtused.

617
00:49:14,960 --> 00:49:22,500
Ja päris lõpus, me tagasi meie sõlme.

618
00:49:22,500 --> 00:49:28,690
Olgu. Üks asi on tähele panna, et see funktsioon siin

619
00:49:28,690 --> 00:49:34,320
läheb tagasi pointer mälu, mis on olnud hunnik jaotatud.

620
00:49:34,320 --> 00:49:38,880
Mis on tore on see, et see sõlm nüüd -

621
00:49:38,880 --> 00:49:42,420
meil kuulutada see hunnik, sest kui me kuulutasime selle kohta virna

622
00:49:42,420 --> 00:49:45,050
me ei saa seda teha selle funktsiooni niimoodi.

623
00:49:45,050 --> 00:49:47,690
See mälu peaks minema ulatus

624
00:49:47,690 --> 00:49:51,590
ja oleks vale, kui me püüdsime seda kasutada hiljem.

625
00:49:51,590 --> 00:49:53,500
Kuna me kuulutame hunnik jaotatud mälu,

626
00:49:53,500 --> 00:49:55,830
me peame hoolitsema vabastades ta hiljem

627
00:49:55,830 --> 00:49:58,530
meie programm ei leki mingit mälu.

628
00:49:58,530 --> 00:50:01,270
Oleme olnud punting kohta, et kõik muu kood

629
00:50:01,270 --> 00:50:02,880
lihtsalt lihtsuse huvides ajal,

630
00:50:02,880 --> 00:50:05,610
aga kui sa kunagi kirjutada funktsioon, mis näeb välja selline

631
00:50:05,610 --> 00:50:10,370
kus sul - mõned kutsuvad seda malloc või RealLOC sees -

632
00:50:10,370 --> 00:50:14,330
sa tahad teha kindel, et paned mingi kommentaar siia üles, mis ütleb,

633
00:50:14,330 --> 00:50:29,970
hei, sa tead, tagastab hunnik jaotatud sõlme käivitub edasikanduvad väärtus.

634
00:50:29,970 --> 00:50:33,600
Ja siis sa tahad teha kindel, et paned mingi märkus, mis ütleb,

635
00:50:33,600 --> 00:50:41,720
helistaja peab vabastama tagastatakse mälu.

636
00:50:41,720 --> 00:50:45,450
Nii, kui keegi kunagi läheb ja kasutab seda funktsiooni,

637
00:50:45,450 --> 00:50:48,150
nad teavad, et mida iganes nad saavad tagasi selle funktsiooni

638
00:50:48,150 --> 00:50:50,870
mingil hetkel tuleb vabastada.

639
00:50:50,870 --> 00:50:53,940
>> Eeldades, et kõik on hästi ja hea siin,

640
00:50:53,940 --> 00:51:02,300
saame minna meie koodi ja asendada kõik need read siin

641
00:51:02,300 --> 00:51:05,410
koos kõnesid meie build sõlme funktsiooni.

642
00:51:05,410 --> 00:51:08,170
Teeme seda tõesti kiiresti.

643
00:51:08,170 --> 00:51:15,840
Ühelt poolt, et me ei kavatse asendada see osa siin all

644
00:51:15,840 --> 00:51:18,520
allosas, kus me tegelikult juhtmetega ühendada sõlmed osutada üksteisele

645
00:51:18,520 --> 00:51:21,030
sest et me ei saa seda teha meie funktsioon.

646
00:51:21,030 --> 00:51:37,400
Aga teeme root = build_node (7); sõlme * 3 = build_node (3);

647
00:51:37,400 --> 00:51:47,980
sõlme * 6 = build_node (6); sõlme * 9 = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
Ja nüüd on meil ka soovis lisada sõlmpunktid -

649
00:51:52,590 --> 00:52:03,530
sõlme * 5 = build_node (5); sõlme * 8 = build_node (8);

650
00:52:03,530 --> 00:52:09,760
ja milline oli teiste sõlme? Vaatame siin. Tahtsime lisada ka 2 -

651
00:52:09,760 --> 00:52:20,280
sõlme * kaks = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Olgu. Sel hetkel, me teame, et meil on 7, 3, 9 ja 6

653
00:52:26,850 --> 00:52:30,320
kõik wired up nõuetekohaselt, kuid kuidas 5, 8, ja 2?

654
00:52:30,320 --> 00:52:33,550
Hoida kõike õiges järjekorras,

655
00:52:33,550 --> 00:52:39,230
me teame, et kolm on õige laps on 6.

656
00:52:39,230 --> 00:52:40,890
Niisiis, kui me kavatseme lisada 5

657
00:52:40,890 --> 00:52:46,670
5 Samuti kuulub paremal pool puud, millest 3 on root,

658
00:52:46,670 --> 00:52:50,440
nii 5 kuulub nii vasakul lapse 6.

659
00:52:50,440 --> 00:52:58,650
Me saame seda teha, öeldes, kuus -> left_child = 5;

660
00:52:58,650 --> 00:53:10,790
ja siis 8 kuulub nii vasak laps 9, seega 9 -> left_child = 8;

661
00:53:10,790 --> 00:53:22,190
ja siis 2 on vasak laps on 3, nii et me saame teha, et siin üleval - sind -> left_child = kaks;.

662
00:53:22,190 --> 00:53:27,730
Kui sa ei ole päris jälgida koos, et ma soovitan teil teha seda ise.

663
00:53:27,730 --> 00:53:35,660
>> Olgu. Olgem salvestada. Lähme välja ja veenduge, et see kogub,

664
00:53:35,660 --> 00:53:40,760
ja siis me saame lisada meie Contains kõned.

665
00:53:40,760 --> 00:53:44,120
Paistab kõike veel koostab.

666
00:53:44,120 --> 00:53:51,790
Lähme ja lisada mõned sisaldab kõned.

667
00:53:51,790 --> 00:53:59,640
Jällegi, ma teen natuke kopeeri ja kleebi.

668
00:53:59,640 --> 00:54:15,860
Nüüd Otsime 5, 8, ja 2. Olgu.

669
00:54:15,860 --> 00:54:28,330
Teeme kindlaks, et see kõik tundub hea ikka. Suurepärane! Salvestamist ja sulgemist.

670
00:54:28,330 --> 00:54:33,220
Nüüd teeme, kompileerida, ja nüüd lähme jooksma.

671
00:54:33,220 --> 00:54:37,540
Alates tulemusi, tundub kõik töötab lihtsalt kena ja hästi.

672
00:54:37,540 --> 00:54:41,780
Suurepärane! Nii et nüüd on meil meie Contains funktsiooni kirjutatud.

673
00:54:41,780 --> 00:54:46,160
Liigume edasi ja alustada tööd, kuidas lisada sõlmede puusse

674
00:54:46,160 --> 00:54:50,000
sest nagu me teeme seda kohe, asjad ei ole väga ilus.

675
00:54:50,000 --> 00:54:52,280
>> Kui me tagasi minna spetsifikatsioon,

676
00:54:52,280 --> 00:55:00,540
küsib ta meile kirjutada funktsiooni nimetatakse lisada - jällegi tagasi bool

677
00:55:00,540 --> 00:55:04,400
jaoks, kas me võiks tegelikult lisada sõlme puusse -

678
00:55:04,400 --> 00:55:07,710
ja siis väärtust lisada puu on märgitud kui

679
00:55:07,710 --> 00:55:11,060
ainus argument meie sisestada funktsiooni.

680
00:55:11,060 --> 00:55:18,180
We will return true kui saaksime tõepoolest sisestada sõlme sisaldav väärtus puusse,

681
00:55:18,180 --> 00:55:20,930
mis tähendab, et me üks, oli piisavalt mälu,

682
00:55:20,930 --> 00:55:24,840
ja siis kaks, et sõlm varem ei olnud, puus alates -

683
00:55:24,840 --> 00:55:32,170
Pea meeles, et me ei kavatse on duplikaatväärtusi puus, vaid teha asjad lihtsad.

684
00:55:32,170 --> 00:55:35,590
Olgu. Tagasi kood.

685
00:55:35,590 --> 00:55:44,240
Tee lahti. Suurenda natuke, seejärel kerige.

686
00:55:44,240 --> 00:55:47,220
Paneme sisestada funktsioon õigus eespool sisaldab.

687
00:55:47,220 --> 00:55:56,360
Jällegi, see saab nimetada bool sisestada (int väärtus).

688
00:55:56,360 --> 00:56:01,840
Anna talle veidi rohkem ruumi, ja siis, kui vaikimisi

689
00:56:01,840 --> 00:56:08,870
paneme vastutasuks vale päris lõpus.

690
00:56:08,870 --> 00:56:22,620
Nüüd alumises otsas, lähme edasi ja selle asemel, et käsitsi hoone tippu

691
00:56:22,620 --> 00:56:27,900
peamistes end ja juhtmestik neid juhtida üksteisele nagu me teeme,

692
00:56:27,900 --> 00:56:30,600
me toetume insertfunktsioonide teha.

693
00:56:30,600 --> 00:56:35,510
Me ei kasuta meie sisestada funktsiooni ehitada kogu puu nullist lihtsalt veel,

694
00:56:35,510 --> 00:56:39,970
vaid me vabaneda neid ridu - we'll kommenteeri välja need read -

695
00:56:39,970 --> 00:56:43,430
et ehitada sõlmede 5, 8, ja 2.

696
00:56:43,430 --> 00:56:55,740
Ja selle asemel, me lisada kõnede meie insertfunktsioonide

697
00:56:55,740 --> 00:57:01,280
veenduda, et see tõesti töötab.

698
00:57:01,280 --> 00:57:05,840
Läheb lahti.

699
00:57:05,840 --> 00:57:09,300
>> Nüüd oleme välja kommenteerida neid ridu.

700
00:57:09,300 --> 00:57:13,700
Meil on ainult 7, 3, 9 ja 6 meie puu selles punktis.

701
00:57:13,700 --> 00:57:18,870
Veendumaks, et see kõik töötab,

702
00:57:18,870 --> 00:57:25,050
saame suumimiseks muuta meie kahendpuu,

703
00:57:25,050 --> 00:57:30,750
käivitada, ja näeme, mis sisaldab nüüd ütleb meile, et me oleme täiesti õigus -

704
00:57:30,750 --> 00:57:33,110
5, 8, ja 2 ei ole enam puu.

705
00:57:33,110 --> 00:57:37,960
Mine tagasi kood,

706
00:57:37,960 --> 00:57:41,070
ja kuidas me lisada?

707
00:57:41,070 --> 00:57:46,290
Pea meeles, mida me tegime kui olime tegelikult lisades 5, 8, ja 2. varem.

708
00:57:46,290 --> 00:57:50,100
Me mängisime et Plinko mäng, kus hakkasime keskmes,

709
00:57:50,100 --> 00:57:52,780
langes puu ükshaaval ühe

710
00:57:52,780 --> 00:57:54,980
kuni leidsime sobiva lõhe,

711
00:57:54,980 --> 00:57:57,570
ja siis me traadiga sõlme sobival kohapeal.

712
00:57:57,570 --> 00:57:59,480
Me teeme sama asja.

713
00:57:59,480 --> 00:58:04,070
See on põhimõtteliselt nagu kirjalikult koodi, mida me kasutada sisaldab funktsiooni

714
00:58:04,070 --> 00:58:05,910
leida kohapeal, kus sõlme peaks olema,

715
00:58:05,910 --> 00:58:10,560
ja siis me lihtsalt läheb lisada sõlm seal.

716
00:58:10,560 --> 00:58:17,000
Alustame tee.

717
00:58:17,000 --> 00:58:24,200
>> Nii et meil on sõlm * viim = root; me lihtsalt läheb järgida sisaldab koodi

718
00:58:24,200 --> 00:58:26,850
kuni me leiame, et see ei ole päris töö meile.

719
00:58:26,850 --> 00:58:32,390
Me läheme läbi puu, kuid praeguses element ei ole null,

720
00:58:32,390 --> 00:58:45,280
ja kui leiame, et viim väärtus on võrdne väärtus, et me üritame lisada -

721
00:58:45,280 --> 00:58:49,600
Noh, see on üks juhtumeid, kus me ei saanud tegelikult sisestada sõlme

722
00:58:49,600 --> 00:58:52,730
puusse, sest see tähendab, et meil on dubleeritud väärtus.

723
00:58:52,730 --> 00:58:59,010
Siin me oleme tegelikult läheb tagasi false.

724
00:58:59,010 --> 00:59:08,440
Nüüd teine, kui viim väärtus on väiksem kui väärtus,

725
00:59:08,440 --> 00:59:10,930
Nüüd me teame, et me liigume paremale

726
00:59:10,930 --> 00:59:17,190
 sest väärtusest kuulub paremal pool viim puu.

727
00:59:17,190 --> 00:59:30,110
Vastasel korral me ei kavatse liikuda vasakule.

728
00:59:30,110 --> 00:59:37,980
See on põhimõtteliselt meie Contains toimima seal.

729
00:59:37,980 --> 00:59:41,820
>> Sel hetkel, kui me oleme valmis seda samas silmus,

730
00:59:41,820 --> 00:59:47,350
meie viim osuti läheb osutades tühjaks

731
00:59:47,350 --> 00:59:51,540
kui funktsioon ei ole juba tagastatud.

732
00:59:51,540 --> 00:59:58,710
Me Seega võttes viim kohas, kus me tahame lisada uus tipp.

733
00:59:58,710 --> 01:00:05,210
Mida veel teha on tegelikult ehitada uus sõlm,

734
01:00:05,210 --> 01:00:08,480
mis me saame teha üsna kergesti.

735
01:00:08,480 --> 01:00:14,930
Me saame kasutada meie super-mugav ehitada sõlm funktsiooni,

736
01:00:14,930 --> 01:00:17,210
ja midagi, mida me ei teinud varem -

737
01:00:17,210 --> 01:00:21,400
me lihtsalt selline pidasin enesestmõistetavaks, aga nüüd me teeme lihtsalt veenduda -

738
01:00:21,400 --> 01:00:27,130
me testida veendumaks, et tagastatav väärtus uus sõlm oli tegelikult

739
01:00:27,130 --> 01:00:33,410
ei ole null, sest me ei taha, et alustada tutvumise et mälu, kui see on null.

740
01:00:33,410 --> 01:00:39,910
Meil saab katsetada veendumaks, et uus sõlm ei ole võrdne null.

741
01:00:39,910 --> 01:00:42,910
Või selle asemel, saame lihtsalt näha, kui ta tegelikult on null,

742
01:00:42,910 --> 01:00:52,120
ja kui see on null, siis saame lihtsalt tagasi false alguses.

743
01:00:52,120 --> 01:00:59,090
>> Sel hetkel on meil juhe uus sõlm sisse oma asjakohaseid kohapeal puu.

744
01:00:59,090 --> 01:01:03,510
Kui me vaatame tagasi peamine ja kus me olime tegelikult juhtmestik väärtused enne,

745
01:01:03,510 --> 01:01:08,470
näeme, et kuidas me teeme seda, kui me tahtsime panna 3 puus

746
01:01:08,470 --> 01:01:11,750
oli meil ligi vasakul laps juur.

747
01:01:11,750 --> 01:01:14,920
Kui me paneme 9 puu oli meil pääseda õige laps juur.

748
01:01:14,920 --> 01:01:21,030
Me pidime olema kursor lapsevanem, et luua uut väärtust puusse.

749
01:01:21,030 --> 01:01:24,430
Kerimine varundada lisada, et ei kavatse päris töö siin

750
01:01:24,430 --> 01:01:27,550
sest meil ei ole vanem pointer.

751
01:01:27,550 --> 01:01:31,650
Mida me tahame, et oleks võimalik teha on, sel hetkel,

752
01:01:31,650 --> 01:01:37,080
kontrollida emaettevõtte raha ja vaata - Nojah,

753
01:01:37,080 --> 01:01:41,990
kui vanema väärtus on väiksem kui praegune väärtus,

754
01:01:41,990 --> 01:01:54,440
siis lapsevanema õigust lapse peaks olema uus sõlm;

755
01:01:54,440 --> 01:02:07,280
teisiti, vanema vasakul laps peaks olema uus sõlm.

756
01:02:07,280 --> 01:02:10,290
Aga meil ei ole selle vanema osuti veel.

757
01:02:10,290 --> 01:02:15,010
>> Selleks, et seda saada, me tegelikult läheb on jälgida seda nagu me minna läbi puu

758
01:02:15,010 --> 01:02:18,440
ja leida sobiv kohapeal meie silmus üle.

759
01:02:18,440 --> 01:02:26,840
Me saame teha, et kerides tagasi üles tippu meie insertfunktsioonide

760
01:02:26,840 --> 01:02:32,350
ja jälgivad veel pointer muutuja nimega vanem.

761
01:02:32,350 --> 01:02:39,340
Me läheme, et seada see võrdub null esialgu

762
01:02:39,340 --> 01:02:43,640
ja siis iga kord kui me minna läbi puu,

763
01:02:43,640 --> 01:02:51,540
me ei kavatse seada vanem osuti mängu praegune pointer.

764
01:02:51,540 --> 01:02:59,140
Määra vanema võrdne viim.

765
01:02:59,140 --> 01:03:02,260
Nii, iga kord kui läheme läbi,

766
01:03:02,260 --> 01:03:05,550
me kavatseme tagada, et kui praegune pointer saab suurendatakse

767
01:03:05,550 --> 01:03:12,640
vanem osuti sellele järgneb - ainult üks tase kõrgem kui praegune pointer puus.

768
01:03:12,640 --> 01:03:17,370
See kõik tundub päris hea.

769
01:03:17,370 --> 01:03:22,380
>> Ma arvan, et üks asi, mis me tahame, et kohandada see ehitada sõlm tagasi null.

770
01:03:22,380 --> 01:03:25,380
Selleks, et saada ehitada sõlm tegelikult edukalt naasta null,

771
01:03:25,380 --> 01:03:31,060
me peame muutma, et kood,

772
01:03:31,060 --> 01:03:37,270
sest siin me kunagi katsetada veendumaks, et malloc tagastatakse kehtiv pointer.

773
01:03:37,270 --> 01:03:53,390
Seega, kui (n! = NULL), siis -

774
01:03:53,390 --> 01:03:55,250
kui malloc tagastatakse kehtiv pointer, siis me algväärtustamiseks;

775
01:03:55,250 --> 01:04:02,540
Muidu me lihtsalt tagasi ja et lõpuks jälle null meile.

776
01:04:02,540 --> 01:04:13,050
Nüüd kõik tundub päris hea. Teeme kindel, et see tegelikult koostab.

777
01:04:13,050 --> 01:04:22,240
Tee kahendpuu, ja oh, meil on mõned asjad siin toimub.

778
01:04:22,240 --> 01:04:29,230
>> Meil kaudne deklaratsiooni funktsioon ehitada sõlme.

779
01:04:29,230 --> 01:04:31,950
Jällegi, nende koostajad, me ei kavatse alustada ülaosas.

780
01:04:31,950 --> 01:04:36,380
Mida see peab tähendama, et ma helistan ehitada sõlm enne, kui ma olen tegelikult kuulutanud.

781
01:04:36,380 --> 01:04:37,730
Lähme tagasi koodi tõesti kiiresti.

782
01:04:37,730 --> 01:04:43,510
Liikuge alla ja jumala eest, minu sisestada funktsioon on välja kuulutatud

783
01:04:43,510 --> 01:04:47,400
Ülaltoodud ehitada sõlm funktsiooni,

784
01:04:47,400 --> 01:04:50,070
aga ma üritan kasutada ehitada sõlm sees sisestada.

785
01:04:50,070 --> 01:05:06,610
Ma lähen minema ja koopia - ja kleebi ehitada sõlm funktsiooni teel siiapoole ülaosas.

786
01:05:06,610 --> 01:05:11,750
Nii, loodetavasti see töötab. Anname selle teise minna.

787
01:05:11,750 --> 01:05:18,920
Nüüd on kõik koostab. Kõik on hea.

788
01:05:18,920 --> 01:05:21,640
>> Aga sel hetkel, me ei ole tegelikult nimetatakse meie sisestada funktsiooni.

789
01:05:21,640 --> 01:05:26,510
Me lihtsalt teame, et ta koostab, nii lähme sisse ja panna mõned kõned sisse

790
01:05:26,510 --> 01:05:28,240
Teeme seda meie peamine ülesanne.

791
01:05:28,240 --> 01:05:32,390
Siin me välja kommenteerida 5, 8, ja 2.

792
01:05:32,390 --> 01:05:36,680
ja siis me ei traat neid siin all.

793
01:05:36,680 --> 01:05:41,640
Teeme mõned kõned sisestada,

794
01:05:41,640 --> 01:05:46,440
ja olgem ka kasutada sama liiki asju, mida me kasutada

795
01:05:46,440 --> 01:05:52,810
kui me tegime need printf nõuab veenduda, et kõik ei saa õigesti sisestatud.

796
01:05:52,810 --> 01:06:00,550
Ma lähen kopeeri ja kleebi,

797
01:06:00,550 --> 01:06:12,450
ja selle asemel sisaldab me teeme sisestada.

798
01:06:12,450 --> 01:06:30,140
Ja selle asemel, 6, 10 ja 1, me ei kavatse kasutada 5, 8, ja 2.

799
01:06:30,140 --> 01:06:37,320
See peaks loodetavasti sisestada 5, 8, ja 2. puusse.

800
01:06:37,320 --> 01:06:44,050
Koostage. Kõik on hea. Nüüd me tegelikult kulgema meie programm.

801
01:06:44,050 --> 01:06:47,330
>> Kõik tagastatud vale.

802
01:06:47,330 --> 01:06:53,830
Niisiis, 5, 8, ja 2 ei läinud, ja tundub Contains ei leia neid kas.

803
01:06:53,830 --> 01:06:58,890
Mis toimub? Lähme välja suumida.

804
01:06:58,890 --> 01:07:02,160
Esimene probleem oli see, et sisestada tundus tagastab false,

805
01:07:02,160 --> 01:07:08,750
ja tundub, et sellepärast me lahkusime meie tagasipöördumine vale kõne

806
01:07:08,750 --> 01:07:14,590
ja me tegelikult kunagi tagasi tõsi.

807
01:07:14,590 --> 01:07:17,880
Me ei saa seda seadistan.

808
01:07:17,880 --> 01:07:25,290
Teine probleem on, nüüd isegi kui me teeme - päästa see, sulgege see,

809
01:07:25,290 --> 01:07:34,530
kulgema teha uuesti, on see kompileerida, siis kestab see -

810
01:07:34,530 --> 01:07:37,670
näeme, et midagi juhtus.

811
01:07:37,670 --> 01:07:42,980
5, 8, ja 2 olid ikka kunagi leitud puu.

812
01:07:42,980 --> 01:07:44,350
Niisiis, mis toimub?

813
01:07:44,350 --> 01:07:45,700
>> Võtame pilk selle koodi.

814
01:07:45,700 --> 01:07:49,790
Vaatame, kas me saame näitaja seda.

815
01:07:49,790 --> 01:07:57,940
Alustame vanem ei ole null.

816
01:07:57,940 --> 01:07:59,510
Seame praegune pointer võrdne juur pointer,

817
01:07:59,510 --> 01:08:04,280
ja me ei kavatse tööd meie tee ette läbi puu.

818
01:08:04,280 --> 01:08:08,650
Kui praegune tipp ei ole null, siis me teame, et me saame liikuda veidi allapoole.

819
01:08:08,650 --> 01:08:12,330
Me seame meie vanem osuti olema võrdne praeguse pointer,

820
01:08:12,330 --> 01:08:15,420
kontrollitud väärtus - kui väärtused on samad me tagasi vale.

821
01:08:15,420 --> 01:08:17,540
Kui väärtused on vähem kolisime õigus;

822
01:08:17,540 --> 01:08:20,399
muidu liikusime vasakule.

823
01:08:20,399 --> 01:08:24,220
Siis me ehitame sõlme. Ma suumida natuke.

824
01:08:24,220 --> 01:08:31,410
Ja siin me läheme proovida juhe üles väärtused olema samad.

825
01:08:31,410 --> 01:08:37,250
Mis toimub? Vaatame, kui võimalik Valgrind võib anda meile vihje.

826
01:08:37,250 --> 01:08:43,910
>> Mulle meeldib kasutada Valgrind lihtsalt sellepärast Valgrind tõesti kiiresti jookseb

827
01:08:43,910 --> 01:08:46,729
ja ütleb, kas on mingeid mälu vead.

828
01:08:46,729 --> 01:08:48,300
Kui võtame Valgrind edasi kood,

829
01:08:48,300 --> 01:08:55,859
nagu näete paremal here--Valgrind./binary_tree--and vajuta enter.

830
01:08:55,859 --> 01:09:03,640
Sa näed, et meil ei olnud mingit mälu viga, nii et tundub, et kőik on korras siiani.

831
01:09:03,640 --> 01:09:07,529
Meil on mõned mälu lekkeid, mida me teame, sest me ei ole

832
01:09:07,529 --> 01:09:08,910
juhtub, et vabastada kõik meie tipud.

833
01:09:08,910 --> 01:09:13,050
Proovime töötab GDB et näha, mis tegelikult toimub.

834
01:09:13,050 --> 01:09:20,010
Me teeme gdb. / Binary_tree. See käivitatud just fine.

835
01:09:20,010 --> 01:09:23,670
Laseme murdepunkt kohta sisestada.

836
01:09:23,670 --> 01:09:28,600
Lähme sõitma.

837
01:09:28,600 --> 01:09:31,200
Tundub, et me kunagi tegelikult nimetatakse sisestada.

838
01:09:31,200 --> 01:09:39,410
Tundub, et probleem oli lihtsalt selles, et kui ma muutsin siia alla peamine -

839
01:09:39,410 --> 01:09:44,279
kõik need printf kõnesid sisaldab -

840
01:09:44,279 --> 01:09:56,430
Ma pole kunagi tegelikult muutunud need helistada sisestada.

841
01:09:56,430 --> 01:10:01,660
Vaatame nüüd seda proovida. Olgem koguma.

842
01:10:01,660 --> 01:10:09,130
Kõik tundub hea seal. Nüüd proovime töötab see, vaata, mis juhtub.

843
01:10:09,130 --> 01:10:13,320
Olgu! Kõik tundub päris hea seal.

844
01:10:13,320 --> 01:10:18,130
>> Viimane asi, mida mõelda on, on olemas serv juhtudel sellele lisada?

845
01:10:18,130 --> 01:10:23,170
Ja selgub, et, noh, üks serv puhul, mis on alati huvitav mõelda

846
01:10:23,170 --> 01:10:26,250
on, mis juhtub, kui teie puu on tühi ja te nimetate seda sisestada funktsiooni?

847
01:10:26,250 --> 01:10:30,330
Kas see töötab? Noh, seda proovida.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree. C -

849
01:10:32,110 --> 01:10:35,810
Kuidas me kavatseme seda testida on, me läheme alla, et meie peamine ülesanne,

850
01:10:35,810 --> 01:10:41,690
ja mitte juhtmestik need sõlmed üles nagu see,

851
01:10:41,690 --> 01:10:56,730
me lihtsalt läheb kommenteerida läbi kogu asi,

852
01:10:56,730 --> 01:11:02,620
ja selle asemel, juhtmestik kuni sõlmed ise,

853
01:11:02,620 --> 01:11:09,400
saame tegelikult lihtsalt minna ja kustutada see kõik.

854
01:11:09,400 --> 01:11:17,560
Me kavatseme teha kõik kõne lisada.

855
01:11:17,560 --> 01:11:49,020
Nii, teeme - asemel 5, 8, ja 2., me lisada 7, 3 ja 9.

856
01:11:49,020 --> 01:11:58,440
Ja siis ka soovite lisada 6 ning.

857
01:11:58,440 --> 01:12:05,190
Salvesta. Lõpeta. Tee kahendpuu.

858
01:12:05,190 --> 01:12:08,540
See kõik koostab.

859
01:12:08,540 --> 01:12:10,320
Me ei saa lihtsalt kasutada seda nagu on ja vaata, mis juhtub,

860
01:12:10,320 --> 01:12:12,770
aga see on ka saab olema väga oluline veenduda, et

861
01:12:12,770 --> 01:12:14,740
meil ei ole mingit mälu vead,

862
01:12:14,740 --> 01:12:16,840
sest see on üks meie serv juhtudel, et me teame.

863
01:12:16,840 --> 01:12:20,150
>> Teeme kindel, et see töötab hästi Valgrind,

864
01:12:20,150 --> 01:12:28,310
mis me teeme lihtsalt kulgeb Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Paistab, et meil on tõepoolest üks viga ühest kontekstis -

866
01:12:31,110 --> 01:12:33,790
meil on see killustatust süü.

867
01:12:33,790 --> 01:12:36,690
Mis juhtus?

868
01:12:36,690 --> 01:12:41,650
Valgrind tegelikult ütleb meile kus see on.

869
01:12:41,650 --> 01:12:43,050
Vähenda veidi.

870
01:12:43,050 --> 01:12:46,040
Tundub, et see toimub meie sisestada funktsiooni,

871
01:12:46,040 --> 01:12:53,420
kus meil on kehtetu lugenud suurus 4 juures sisestada, liin 60.

872
01:12:53,420 --> 01:13:03,590
Lähme tagasi ja vaata, mis siin toimub.

873
01:13:03,590 --> 01:13:05,350
Vähenda tõesti kiire.

874
01:13:05,350 --> 01:13:14,230
Ma tahan veenduda, et see ei lähe ekraani serval, et saaksime näha kõike.

875
01:13:14,230 --> 01:13:18,760
Pull, et natuke. Olgu.

876
01:13:18,760 --> 01:13:35,030
Liikuge alla ja probleem on siin.

877
01:13:35,030 --> 01:13:40,120
Mis juhtub, kui me pikali ja meie praegune tipp on juba null,

878
01:13:40,120 --> 01:13:44,010
meie vanem sõlme on null, nii et kui me vaatame üles tipus, siin -

879
01:13:44,010 --> 01:13:47,340
kui samas silmus kunagi tegelikult täidab

880
01:13:47,340 --> 01:13:52,330
sest meie praegune väärtus on null - meie juured on null nii viim on null -

881
01:13:52,330 --> 01:13:57,810
siis meie ema kunagi saab seadistada viim või kehtiva väärtuse,

882
01:13:57,810 --> 01:14:00,580
nii, ema on samuti null.

883
01:14:00,580 --> 01:14:03,700
Peame meeles pidama, et kontrollida, et

884
01:14:03,700 --> 01:14:08,750
selleks ajaks saame siia alla, ja hakkame tutvumise vanema väärtus.

885
01:14:08,750 --> 01:14:13,190
Niisiis, mis juhtub? Noh, kui vanem on null -

886
01:14:13,190 --> 01:14:17,990
if (vanem == NULL) - siis me teame, et

887
01:14:17,990 --> 01:14:19,530
ei tohiks olla midagi puus.

888
01:14:19,530 --> 01:14:22,030
Meil tuleb püüda lisab selle juur.

889
01:14:22,030 --> 01:14:32,570
Me saame teha, et just millega juur võrdne uus sõlm.

890
01:14:32,570 --> 01:14:40,010
Siis sel hetkel, me tegelikult ei taha minna läbi need muud asjad.

891
01:14:40,010 --> 01:14:44,780
Selle asemel, just siin, me saame teha kas mujal kui-teine,

892
01:14:44,780 --> 01:14:47,610
või me võiksime ühendada kõik üles siin muud,

893
01:14:47,610 --> 01:14:56,300
kuid siin me lihtsalt kasutada mujal ja seda sel viisil.

894
01:14:56,300 --> 01:14:59,030
Nüüd me ei kavatse katsetada veendumaks, et meie vanem ei ole null

895
01:14:59,030 --> 01:15:02,160
enne siis tegelikult püüab kasutada oma valdkondades.

896
01:15:02,160 --> 01:15:05,330
See aitab meil vältida killustatust süü.

897
01:15:05,330 --> 01:15:14,740
Niisiis, me quit, zoom out, koostada, käivitada.

898
01:15:14,740 --> 01:15:18,130
>> Vigu ei, aga meil on veel hunnik mälu lekked

899
01:15:18,130 --> 01:15:20,650
sest me ei vabastaks kõik meie tipud.

900
01:15:20,650 --> 01:15:24,350
Aga kui me läheme siia ja me vaatame meie väljatrükk,

901
01:15:24,350 --> 01:15:30,880
näeme, et, noh, paistab meie kõigi lisab olid tagasi tõsi, mis on hea.

902
01:15:30,880 --> 01:15:33,050
Lisab kõik õige,

903
01:15:33,050 --> 01:15:36,670
ja siis sobiv Contains kõned on ka tõsi.

904
01:15:36,670 --> 01:15:41,510
>> Hea töö! Tundub, et me oleme edukalt kirjutatud sisestada.

905
01:15:41,510 --> 01:15:47,430
See on kõik, mis meil on selle nädala Ülesanded spetsifikatsioon.

906
01:15:47,430 --> 01:15:51,720
Üks lõbus väljakutse mõelda, kuidas sa tegelikult minna

907
01:15:51,720 --> 01:15:55,340
ja tasuta kõik sõlmed seda puud.

908
01:15:55,340 --> 01:15:58,830
Me saame seda teha mitmel erineval viisil,

909
01:15:58,830 --> 01:16:01,930
aga ma jätan selle kuni teil eksperimenteerida,

910
01:16:01,930 --> 01:16:06,080
ja kui lõbus väljakutse, proovige ja veenduge, et teil võib olla kindel,

911
01:16:06,080 --> 01:16:09,490
et see Valgrind aruanne ei tagasta mingit vead ja lekked.

912
01:16:09,490 --> 01:16:12,880
>> Õnn nädala Huffman kodeerimine lahendamist,

913
01:16:12,880 --> 01:16:14,380
ja me näeme järgmisel nädalal!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]