1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Artikel 7] [Minder Gerieflik]

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

3
00:00:04,890 --> 00:00:07,000
[Hierdie is CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Welkom by Artikel 7.

5
00:00:09,080 --> 00:00:11,330
Dankie te orkaan Sandy,

6
00:00:11,330 --> 00:00:13,440
in plaas van met 'n normale deel van hierdie week,

7
00:00:13,440 --> 00:00:17,650
ons om dit te doen deur-stap, deur middel van die afdeling van die vrae.

8
00:00:17,650 --> 00:00:22,830
Ek gaan word die volgende saam met die probleem Stel 6 spesifikasie,

9
00:00:22,830 --> 00:00:25,650
en gaan deur al die vrae in die

10
00:00:25,650 --> 00:00:27,770
'N Artikel VAN VRAE AFDELING.

11
00:00:27,770 --> 00:00:30,940
As daar enige vrae is,

12
00:00:30,940 --> 00:00:32,960
asseblief plaas dit op CS50 Bespreek.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Kom ons begin.

14
00:00:35,480 --> 00:00:40,780
Reg nou is ek op soek na bladsy 3 van die probleem Set spesifikasie.

15
00:00:40,780 --> 00:00:44,110
Ons gaan die eerste keer begin praat oor binêre bome

16
00:00:44,110 --> 00:00:47,850
aangesien dit 'n baie van belang is vir hierdie week se probleem stel -

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

18
00:00:49,950 --> 00:00:55,000
Een van die heel eerste datastrukture het ons gepraat oor CS50 was die skikking.

19
00:00:55,000 --> 00:01:00,170
Onthou dat 'n skikking is 'n volgorde van die elemente -

20
00:01:00,170 --> 00:01:04,019
almal van dieselfde soort - reg langs mekaar in die geheue gestoor.

21
00:01:04,019 --> 00:01:14,420
As ek 'n heelgetal skikking wat ek kan trek met behulp van hierdie bokse-nommers-heelgetalle styl -

22
00:01:14,420 --> 00:01:20,290
Kom ons sê ek het 5 in die eerste blokkie, ek het 7 in die tweede,

23
00:01:20,290 --> 00:01:27,760
dan het ek 8, 10 en 20 in die finale boks.

24
00:01:27,760 --> 00:01:33,000
Onthou, die twee baie goeie dinge oor hierdie skikking

25
00:01:33,000 --> 00:01:38,800
is dat ons hierdie konstante-time toegang tot 'n bepaalde element

26
00:01:38,800 --> 00:01:40,500
 in die skikking as ons weet dat die indeks.

27
00:01:40,500 --> 00:01:44,670
Byvoorbeeld, as ek wil hê dat die derde element in die skikking aan te gryp -

28
00:01:44,670 --> 00:01:47,870
indeks 2 deur gebruik te maak van ons zero-gebaseerde kruip -

29
00:01:47,870 --> 00:01:52,220
Ek het letterlik net 'n eenvoudige wiskundige berekening te doen,

30
00:01:52,220 --> 00:01:56,170
hop tot daardie posisie in die skikking,

31
00:01:56,170 --> 00:01:57,840
trek uit die 8 wat daar geberg word,

32
00:01:57,840 --> 00:01:59,260
en ek is goed om te gaan.

33
00:01:59,260 --> 00:02:03,350
>> Een van die slegte dinge oor hierdie skikking - dat ons het gepraat oor

34
00:02:03,350 --> 00:02:05,010
wanneer ons bespreek geskakelde lyste -

35
00:02:05,010 --> 00:02:09,120
is dat as ek wil 'n element in hierdie skikking te voeg,

36
00:02:09,120 --> 00:02:11,090
Ek gaan om te hê sommige verskuif om te doen.

37
00:02:11,090 --> 00:02:12,940
Byvoorbeeld, hierdie skikking reg hier

38
00:02:12,940 --> 00:02:16,850
in gesorteer einde - gesorteer in stygende volgorde

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

40
00:02:19,440 --> 00:02:23,100
maar as ek wil die getal 9 in te voeg in hierdie skikking,

41
00:02:23,100 --> 00:02:27,460
Ek gaan 'n paar van die elemente te skuif om plek te maak.

42
00:02:27,460 --> 00:02:30,440
Ons kan trek dit uit hier.

43
00:02:30,440 --> 00:02:35,650
Ek gaan hê om die 5, 7 beweeg, en dan die 8;

44
00:02:35,650 --> 00:02:38,720
skep 'n gaping waar ek kan die 9,

45
00:02:38,720 --> 00:02:45,910
en dan die 10 en die 20 kan gaan aan die regterkant van die 9.

46
00:02:45,910 --> 00:02:49,450
Dit is 'n soort van 'n pyn want in die ergste geval scenario -

47
00:02:49,450 --> 00:02:54,350
wanneer ons by te voeg aan die begin of aan die einde

48
00:02:54,350 --> 00:02:56,040
van die skikking, afhangende van hoe ons skuif -

49
00:02:56,040 --> 00:02:58,850
ons kan eindig met al die elemente te skuif

50
00:02:58,850 --> 00:03:00,750
dat ons tans stoor in die skikking.

51
00:03:00,750 --> 00:03:03,810
>> So, wat was die manier om hierdie?

52
00:03:03,810 --> 00:03:09,260
Die manier om hierdie was om te gaan na ons gekoppelde-lys van die metode waar -

53
00:03:09,260 --> 00:03:19,820
in plaas van die stoor van die elemente 5, 7, 8, 10 en 20 langs mekaar in die geheue -

54
00:03:19,820 --> 00:03:25,630
wat ons in plaas gedoen het, was stoor dit soort van waar ons wil om dit te stoor

55
00:03:25,630 --> 00:03:32,470
in hierdie gekoppelde-lys nodes wat ek teken hier, soort van ad hoc.

56
00:03:32,470 --> 00:03:42,060
En dan het ons verbind hulle saam gebruik van die volgende wenke.

57
00:03:42,060 --> 00:03:44,370
Ek kan 'n wyser van 5 tot 7,

58
00:03:44,370 --> 00:03:46,420
'n wyser van die 7 8,

59
00:03:46,420 --> 00:03:47,770
'n wyser uit die 8 aan die 10,

60
00:03:47,770 --> 00:03:51,220
en uiteindelik, 'n wyser van die 10 aan die 20,

61
00:03:51,220 --> 00:03:54,880
en dan 'n null wyser op die 20 wat aandui dat daar is niks links.

62
00:03:54,880 --> 00:03:59,690
Die trade-off dat ons hier

63
00:03:59,690 --> 00:04:05,360
is dat dit nou as ons wil hê dat die getal 9 in ons gesorteerde lys te voeg,

64
00:04:05,360 --> 00:04:08,270
al wat ons hoef te doen, is die skep van 'n nuwe node met 9,

65
00:04:08,270 --> 00:04:12,290
bedraad dit om te verwys na die toepaslike plek,

66
00:04:12,290 --> 00:04:20,630
en dan weer draad 8 punt af na die 9.

67
00:04:20,630 --> 00:04:25,660
Dit is redelik vinnig, met die veronderstelling dat ons presies weet waar ons wil die 9 in te voeg.

68
00:04:25,660 --> 00:04:32,610
Maar die trade-off in ruil vir hierdie is dat ons nou verloor het die konstante-time toegang

69
00:04:32,610 --> 00:04:36,230
aan 'n bepaalde element in ons data struktuur.

70
00:04:36,230 --> 00:04:40,950
Byvoorbeeld, as ek wil die vierde element in hierdie geskakelde lys te vind,

71
00:04:40,950 --> 00:04:43,510
Ek gaan te hê om te begin by die begin van die lys

72
00:04:43,510 --> 00:04:48,930
en werk my pad deur die tel van node-by-node totdat ek vind die vierde een.

73
00:04:48,930 --> 00:04:55,870
>> Ten einde beter toegang prestasie as 'n geskakelde lys te kry -

74
00:04:55,870 --> 00:04:59,360
maar behou ook sommige van die voordele wat ons gehad het

75
00:04:59,360 --> 00:05:01,800
in terme van 'n geskakelde lys van invoeging-time -

76
00:05:01,800 --> 00:05:05,750
'n binêre boom gaan 'n bietjie meer geheue nodig het om te gebruik.

77
00:05:05,750 --> 00:05:11,460
In die besonder, in plaas van net een wyser in 'n binêre boom node -

78
00:05:11,460 --> 00:05:13,350
soos die gekoppelde-lys node doen -

79
00:05:13,350 --> 00:05:16,950
ons gaan 'n tweede wyser toe te voeg tot die binêre boom node.

80
00:05:16,950 --> 00:05:19,950
Eerder as om net met 'n wyser na die volgende element,

81
00:05:19,950 --> 00:05:24,420
ons gaan 'n wyser na 'n links kind en 'n regte kind te hê.

82
00:05:24,420 --> 00:05:26,560
>> Kom ons teken 'n prent om te sien wat dit eintlik lyk soos.

83
00:05:26,560 --> 00:05:31,350
Weereens, ek gaan hierdie bokse en pyle te gebruik.

84
00:05:31,350 --> 00:05:37,150
'N binêre boom node sal begin met net 'n eenvoudige boks.

85
00:05:37,150 --> 00:05:40,940
Dit gaan om 'n ruimte te hê vir die waarde,

86
00:05:40,940 --> 00:05:47,280
en dan is dit ook gaan om 'n ruimte vir die linker kind en die regte kind te hê.

87
00:05:47,280 --> 00:05:49,280
Ek gaan hulle hier benoem.

88
00:05:49,280 --> 00:05:57,560
Ons gaan die linker kind te hê, en dan gaan die reg om kind te hê.

89
00:05:57,560 --> 00:05:59,920
Daar is baie verskillende maniere om dit te doen.

90
00:05:59,920 --> 00:06:02,050
Soms vir ruimte en gerief,

91
00:06:02,050 --> 00:06:06,460
Ek sal eintlik teken dit soos ek hier doen op die bodem

92
00:06:06,460 --> 00:06:10,910
waar ek gaan om die waarde te hê aan die bokant,

93
00:06:10,910 --> 00:06:14,060
en dan die regte kind op die onderste reg,

94
00:06:14,060 --> 00:06:16,060
en die linker kind op die linkerhand.

95
00:06:16,060 --> 00:06:20,250
Terug te gaan na die top diagram,

96
00:06:20,250 --> 00:06:22,560
ons het die waarde op die heel boonste,

97
00:06:22,560 --> 00:06:25,560
dan het ons die linker-kind pointer, en dan het ons die reg-kind-wyser.

98
00:06:25,560 --> 00:06:30,110
>> In die Problem Set spesifikasie,

99
00:06:30,110 --> 00:06:33,110
ons praat oor die teken van 'n nodus wat 'n waarde 7,

100
00:06:33,110 --> 00:06:39,750
en dan 'n linker-kind pointer wat null, en 'n regs-kind pointer wat null.

101
00:06:39,750 --> 00:06:46,040
Ons kan óf skryf kapitaal NULL in die ruimte vir

102
00:06:46,040 --> 00:06:51,610
beide die linker-kind en die regte kind, of ons kan hierdie diagonale streep trek

103
00:06:51,610 --> 00:06:53,750
deur elk van die bokse aan te dui dat dit nietig is.

104
00:06:53,750 --> 00:06:57,560
Ek gaan om dit te doen net omdat dit is makliker.

105
00:06:57,560 --> 00:07:03,700
Wat jy hier sien is twee maniere van die diagram van 'n baie eenvoudige binêre boom node

106
00:07:03,700 --> 00:07:07,960
waar ons die waarde 7 en null kind wysers.

107
00:07:07,960 --> 00:07:15,220
>> Die tweede deel van ons spesifikasie gesprekke oor hoe om met geskakelde lyste -

108
00:07:15,220 --> 00:07:18,270
Onthou, ons het net om vas te hou aan die heel eerste element in 'n lys

109
00:07:18,270 --> 00:07:20,270
die hele lys te onthou -

110
00:07:20,270 --> 00:07:26,140
en net so, met 'n binêre boom, ons het net om vas te hou aan een wyser na die boom

111
00:07:26,140 --> 00:07:31,120
ten einde beheer oor die hele data struktuur in stand te hou.

112
00:07:31,120 --> 00:07:36,150
Hierdie spesiale element van die boom is die wortel node van die boom genoem.

113
00:07:36,150 --> 00:07:43,360
Byvoorbeeld, as hierdie een node - hierdie node wat die waarde 7

114
00:07:43,360 --> 00:07:45,500
met null links-en regs-kind-wysers -

115
00:07:45,500 --> 00:07:47,360
was die enigste waarde in ons boom,

116
00:07:47,360 --> 00:07:50,390
dan sou ons wortel node.

117
00:07:50,390 --> 00:07:52,240
Dit is die begin van ons boom.

118
00:07:52,240 --> 00:07:58,530
Ons kan dit 'n bietjie meer duidelik wanneer ons begin met die toevoeging van meer nodes aan ons boom.

119
00:07:58,530 --> 00:08:01,510
Laat my trek 'n nuwe bladsy.

120
00:08:01,510 --> 00:08:05,000
>> Nou gaan ons 'n boom te trek wat 7 by die wortel,

121
00:08:05,000 --> 00:08:10,920
en 3 binnekant van die linker kind, en 9 binnekant van die regte kind.

122
00:08:10,920 --> 00:08:13,500
Weereens, dit is redelik eenvoudig.

123
00:08:13,500 --> 00:08:26,510
Ons 7 het, teken 'n node vir die 3, 'n node vir 9,

124
00:08:26,510 --> 00:08:32,150
en ek gaan die linker-kind-wyser van 7 te stel om te verwys na die nodus met 3,

125
00:08:32,150 --> 00:08:37,850
en die regs-kind wyser van die node met 7 tot die node met 9.

126
00:08:37,850 --> 00:08:42,419
Nou, sedert 3 en 9 nie enige kinders,

127
00:08:42,419 --> 00:08:48,500
ons gaan al van hul kind pointers te stel aan nul.

128
00:08:48,500 --> 00:08:56,060
Hier is die wortel van ons boom ooreenstem met die node met die getal 7.

129
00:08:56,060 --> 00:09:02,440
Jy kan sien dat as al wat ons het, is 'n wyser na die wortel node,

130
00:09:02,440 --> 00:09:07,330
dan kan ons wandel deur ons boom en toegang tot beide kind nodes -

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

132
00:09:10,630 --> 00:09:14,820
Nie nodig om wenke te handhaaf elke enkele nodus aan die boom.

133
00:09:14,820 --> 00:09:22,080
Alright. Nou gaan ons nog 'n node te voeg tot hierdie diagram.

134
00:09:22,080 --> 00:09:25,370
Ons gaan 'n node te voeg met 6,

135
00:09:25,370 --> 00:09:34,140
en ons gaan dit as die regte kind van die node met 3 te voeg.

136
00:09:34,140 --> 00:09:41,850
Om dit te doen, ek gaan daardie null pointer uit te vee in die 3-node

137
00:09:41,850 --> 00:09:47,750
en draad dit om te verwys na die nodus met 6. Alright.

138
00:09:47,750 --> 00:09:53,800
>> Op hierdie punt, laat ons gaan oor 'n bietjie van terminologie.

139
00:09:53,800 --> 00:09:58,230
Om mee te begin, die rede dat dit 'n binêre boom in die besonder genoem

140
00:09:58,230 --> 00:10:00,460
is dat dit twee kind wysers.

141
00:10:00,460 --> 00:10:06,020
Daar is ander vorme van bome wat meer kind wysers.

142
00:10:06,020 --> 00:10:10,930
In die besonder, jy het 'n "probeer" in Problem Set 5.

143
00:10:10,930 --> 00:10:19,310
Jy sal sien dat in daardie drie het 27 verskillende verwysings na verskillende kinders gehad -

144
00:10:19,310 --> 00:10:22,410
een vir elk van die 26 briewe in die Engelse alfabet,

145
00:10:22,410 --> 00:10:25,410
en dan die 27ste vir die afkappingsteken -

146
00:10:25,410 --> 00:10:28,900
So, dit is soortgelyk aan 'n tipe van die boom.

147
00:10:28,900 --> 00:10:34,070
Maar hier, omdat dit binêre, ons het net twee kind wysers.

148
00:10:34,070 --> 00:10:37,880
>> Bykomend tot hierdie wortel node wat ons oor gepraat het,

149
00:10:37,880 --> 00:10:41,470
ons het ook gooi rondom die term "kind."

150
00:10:41,470 --> 00:10:44,470
Wat beteken dit vir een node na 'n kind van 'n ander node?

151
00:10:44,470 --> 00:10:54,060
Dit beteken letterlik dat 'n kind node is 'n kind van 'n ander node

152
00:10:54,060 --> 00:10:58,760
indien daardie ander node het een van sy kind verwysings om aan te dui dat die node.

153
00:10:58,760 --> 00:11:01,230
Te stel in meer konkrete terme,

154
00:11:01,230 --> 00:11:11,170
as 3 word uitgewys deur een van die kind-wysers van 7, dan 3 is 'n kind van 7.

155
00:11:11,170 --> 00:11:14,510
As ons om uit te vind wat die kinders van 7 -

156
00:11:14,510 --> 00:11:18,510
Wel, ons sien dat 7 het 'n wyser na 3 en 'n wyser na 9,

157
00:11:18,510 --> 00:11:22,190
so 9 en 3 is die kinders van 7.

158
00:11:22,190 --> 00:11:26,650
Nege het geen kinders omdat sy kind pointers null,

159
00:11:26,650 --> 00:11:30,940
en 3 het slegs een kind, 6.

160
00:11:30,940 --> 00:11:37,430
Ses het ook geen kinders nie, want beide van sy wenke is null, wat ons nou trek.

161
00:11:37,430 --> 00:11:45,010
>> Daarbenewens het ons ook praat oor die ouers van 'n bepaalde nodus,

162
00:11:45,010 --> 00:11:51,100
en dit is, soos mens sou verwag, die omgekeerde van hierdie kind beskrywing.

163
00:11:51,100 --> 00:11:58,620
Elke node het net een ouer in plaas van twee as wat jy kan verwag met die mens.

164
00:11:58,620 --> 00:12:03,390
Byvoorbeeld, die ouer van 3 is 7.

165
00:12:03,390 --> 00:12:10,800
Die ouer van 9 is ook 7, en die ouer van 6 3. Nie veel om dit te.

166
00:12:10,800 --> 00:12:15,720
Ons het ook om te praat oor grootouers en kleinkinders,

167
00:12:15,720 --> 00:12:18,210
en meer in die algemeen praat ons oor die voorvaders

168
00:12:18,210 --> 00:12:20,960
afstammelinge van 'n bepaalde nodus.

169
00:12:20,960 --> 00:12:25,710
Die voorvader van 'n node of voorouers, eerder van 'n node -

170
00:12:25,710 --> 00:12:32,730
is al die nodes wat lê op die pad van die wortel aan daardie node.

171
00:12:32,730 --> 00:12:36,640
Byvoorbeeld, as ek soek op die node 6,

172
00:12:36,640 --> 00:12:46,430
dan is die voorvaders gaan wees beide 3 en 7.

173
00:12:46,430 --> 00:12:55,310
Die voorouers van 9, byvoorbeeld, is - as ek kyk na die node 9 -

174
00:12:55,310 --> 00:12:59,990
dan is die voorvader van 9 is net 7.

175
00:12:59,990 --> 00:13:01,940
En nageslag is presies die teenoorgestelde.

176
00:13:01,940 --> 00:13:05,430
As ek wil om te kyk na al die afstammelinge van 7,

177
00:13:05,430 --> 00:13:11,020
dan moet ek kyk na al die nodes onder dit.

178
00:13:11,020 --> 00:13:16,950
So, ek het 3, 9, en 6 as afstammelinge van 7.

179
00:13:16,950 --> 00:13:24,170
>> Die laaste kwartaal wat ons sal praat oor hierdie idee van 'n broer of suster.

180
00:13:24,170 --> 00:13:27,980
Broers en susters - soort van die volgende saam op hierdie familie-terme -

181
00:13:27,980 --> 00:13:33,150
nodes wat op dieselfde vlak in die boom.

182
00:13:33,150 --> 00:13:42,230
So, 3 en 9 is broers en susters, want hulle is op dieselfde vlak in die boom.

183
00:13:42,230 --> 00:13:46,190
Hulle het albei dieselfde ouer, 7.

184
00:13:46,190 --> 00:13:51,400
Die 6 het geen broers en susters, omdat 9 nie enige kinders.

185
00:13:51,400 --> 00:13:55,540
En 7 het geen broers en susters, want dit is die wortel van ons boom,

186
00:13:55,540 --> 00:13:59,010
en daar is altyd net 1 wortel.

187
00:13:59,010 --> 00:14:02,260
Vir 7 broers en susters te hê sou hê om 'n node bo 7.

188
00:14:02,260 --> 00:14:07,480
Daar sal 'n ouer van 7, in welke geval 7 sal nie langer die wortel van die boom te wees.

189
00:14:07,480 --> 00:14:10,480
Dan dat die nuwe ouer van 7 sal ook 'n kind te hê,

190
00:14:10,480 --> 00:14:16,480
en daardie kind sal dan die broer van 7.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Beweeg op.

192
00:14:21,040 --> 00:14:24,930
Wanneer ons begin ons bespreking van binêre bome,

193
00:14:24,930 --> 00:14:28,790
het ons gepraat oor hoe ons gaan om dit te gebruik om te

194
00:14:28,790 --> 00:14:32,800
kry 'n voordeel oor beide skikkings en geskakelde lyste.

195
00:14:32,800 --> 00:14:37,220
En die manier waarop ons gaan om dit te doen is met hierdie bestel eiendom.

196
00:14:37,220 --> 00:14:41,080
Ons sê dat 'n binêre boom bestel word, volgens die spesifikasie,

197
00:14:41,080 --> 00:14:45,740
indien vir elke node in ons boom, al sy afstammelinge aan die linkerkant -

198
00:14:45,740 --> 00:14:48,670
die linker-kind en van die linker kind se nageslag -

199
00:14:48,670 --> 00:14:54,510
mindere waardes, en al die nodusse op die reg -

200
00:14:54,510 --> 00:14:57,770
die regte kind en al van die regte kind se afstammelinge -

201
00:14:57,770 --> 00:15:02,800
nodes groter as die waarde van die huidige node wat ons is op soek na.

202
00:15:02,800 --> 00:15:07,850
Net vir eenvoud, gaan ons om te aanvaar dat daar nie enige dubbele nodes in ons boom.

203
00:15:07,850 --> 00:15:11,180
Byvoorbeeld, in hierdie boom ons nie van plan om te gaan met die saak

204
00:15:11,180 --> 00:15:13,680
waar ons die waarde 7 by die wortel

205
00:15:13,680 --> 00:15:16,720
 en dan het ons ook die waarde 7 elders in die boom.

206
00:15:16,720 --> 00:15:24,390
In hierdie geval, sal jy sien dat hierdie boom is inderdaad bestel.

207
00:15:24,390 --> 00:15:26,510
Ons het die waarde 7 by die wortel.

208
00:15:26,510 --> 00:15:29,720
Alles aan die linkerkant van 7 -

209
00:15:29,720 --> 00:15:35,310
as ek al hierdie merkies maak ongedaan hier -

210
00:15:35,310 --> 00:15:40,450
alles aan die linkerkant van 7 - 3 en die 6 -

211
00:15:40,450 --> 00:15:49,410
daardie waardes is albei minder as 7, en alles na regs - wat is net 9 -

212
00:15:49,410 --> 00:15:53,450
is groter as 7.

213
00:15:53,450 --> 00:15:58,650
>> Dit is nie die enigste bestel boom met hierdie waardes,

214
00:15:58,650 --> 00:16:03,120
maar laat ons trek 'n paar van hulle.

215
00:16:03,120 --> 00:16:05,030
Daar is eintlik 'n hele klomp van die maniere waarop ons dit kan doen.

216
00:16:05,030 --> 00:16:09,380
Ek gaan 'n snelskrif te gebruik net om dinge eenvoudig hou waar -

217
00:16:09,380 --> 00:16:11,520
eerder as teken uit die hele bokse en pyle -

218
00:16:11,520 --> 00:16:14,220
Ek gaan net om die getalle te trek en pyle verbind hulle voeg.

219
00:16:14,220 --> 00:16:22,920
Om mee te begin, sal ons net skryf ons oorspronklike boom weer waar ons 7, en dan 'n 3,

220
00:16:22,920 --> 00:16:25,590
en dan 3 wys terug na die reg aan die 6,

221
00:16:25,590 --> 00:16:30,890
en 7 het 'n reg kind wat was 9.

222
00:16:30,890 --> 00:16:33,860
Alright. Wat is 'n ander manier wat ons kan skryf hierdie boom?

223
00:16:33,860 --> 00:16:38,800
In plaas van om 3 die linker kind van 7,

224
00:16:38,800 --> 00:16:41,360
ons kan ook die 6 die linker kind van 7,

225
00:16:41,360 --> 00:16:44,470
en dan 3 die linker kind van die 6.

226
00:16:44,470 --> 00:16:48,520
Dit sal lyk soos hierdie boom hier waar ek het 7,

227
00:16:48,520 --> 00:16:57,860
dan 6, dan 3, en 'n 9 aan die regterkant.

228
00:16:57,860 --> 00:17:01,490
Ons het ook nie 7 as ons wortel node te hê.

229
00:17:01,490 --> 00:17:03,860
Ons kan ook 6 as ons wortel node.

230
00:17:03,860 --> 00:17:06,470
Wat sal dit lyk?

231
00:17:06,470 --> 00:17:09,230
As ons gaan hierdie bestel eiendom in stand te hou,

232
00:17:09,230 --> 00:17:12,970
alles aan die linkerkant van die 6 het minder as dit te wees.

233
00:17:12,970 --> 00:17:16,540
Daar is slegs een moontlikheid, en dit is 3.

234
00:17:16,540 --> 00:17:19,869
Maar dan as die reg om kind van 6, ons het twee moontlikhede.

235
00:17:19,869 --> 00:17:25,380
Eerstens, kan ons die 7 en dan die 9

236
00:17:25,380 --> 00:17:28,850
of ons kan om dit te trek nie - soos ek is op die punt om hier te doen -

237
00:17:28,850 --> 00:17:34,790
waar ons die 9 as die regte kind van die 6,

238
00:17:34,790 --> 00:17:39,050
en dan die 7 as die linker kind van die 9.

239
00:17:39,050 --> 00:17:44,240
>> Nou, 7 en 6 is nie die enigste moontlike waardes vir die wortel.

240
00:17:44,240 --> 00:17:50,200
Ons kan ook 'n 3 by die wortel.

241
00:17:50,200 --> 00:17:52,240
Wat gebeur as daar 3 is by die wortel?

242
00:17:52,240 --> 00:17:54,390
Dinge hier, 'n bietjie interessant.

243
00:17:54,390 --> 00:17:58,440
Drie nie enige waardes wat minder as dit,

244
00:17:58,440 --> 00:18:02,070
sodat die hele linkerkant van die boom is net gaan om te wees null.

245
00:18:02,070 --> 00:18:03,230
Daar is nie van plan om enigiets daar.

246
00:18:03,230 --> 00:18:07,220
Aan die regterkant, kan ons die lys van dinge in stygende orde.

247
00:18:07,220 --> 00:18:15,530
Ons kan 3, dan 6, dan 7, dan 9.

248
00:18:15,530 --> 00:18:26,710
Of, kan ons doen 3, dan 6, dan 9, dan 7.

249
00:18:26,710 --> 00:18:35,020
Of, kan ons doen 3, dan 7, dan 6, dan 9.

250
00:18:35,020 --> 00:18:40,950
Of, 3, 7 - eintlik nie, kan ons dit nie doen nie 'n 7 nie.

251
00:18:40,950 --> 00:18:43,330
Dit is ons een ding.

252
00:18:43,330 --> 00:18:54,710
Ons kan dit doen 9, en dan van die 9 ons kan doen 6 en dan 7.

253
00:18:54,710 --> 00:19:06,980
Of, kan ons doen 3, dan 9, dan 7, en dan 6.

254
00:19:06,980 --> 00:19:12,490
>> Een ding om jou aandag te vestig op hier is

255
00:19:12,490 --> 00:19:14,510
dat hierdie bome is 'n bietjie weird-looking.

256
00:19:14,510 --> 00:19:17,840
In die besonder, as ons kyk na die 4 bome aan die regterkant -

257
00:19:17,840 --> 00:19:20,930
Ek sal omkring hulle hier -

258
00:19:20,930 --> 00:19:28,410
hierdie bome lyk byna presies soos 'n geskakelde lys.

259
00:19:28,410 --> 00:19:32,670
Elke node het slegs een kind,

260
00:19:32,670 --> 00:19:38,950
En so het ons nie enige van hierdie boom-agtige struktuur wat ons sien, byvoorbeeld,

261
00:19:38,950 --> 00:19:44,720
 in hierdie een eensame boom hier op die onderste linkerkantste.

262
00:19:44,720 --> 00:19:52,490
Hierdie bome is eintlik genoem binêre bome te ontaard,

263
00:19:52,490 --> 00:19:54,170
en ons sal praat oor hierdie meer in die toekoms -

264
00:19:54,170 --> 00:19:56,730
veral as jy gaan op die ander rekenaar wetenskap kursusse te neem.

265
00:19:56,730 --> 00:19:59,670
Hierdie bome is ontaard.

266
00:19:59,670 --> 00:20:03,780
Hulle is nie baie nuttig, want, inderdaad, hierdie struktuur leen hom

267
00:20:03,780 --> 00:20:08,060
 tye soortgelyk aan dié van 'n geskakelde lys te soek.

268
00:20:08,060 --> 00:20:13,050
Ons nie om voordeel te trek uit die ekstra geheue - hierdie ekstra pointer -

269
00:20:13,050 --> 00:20:18,840
as gevolg van ons struktuur sleg op hierdie manier.

270
00:20:18,840 --> 00:20:24,700
Eerder as om op en trek uit die binêre bome wat 9 by die wortel,

271
00:20:24,700 --> 00:20:27,220
wat is die laaste geval wat ons wil hê,

272
00:20:27,220 --> 00:20:32,380
ons plaas, op hierdie punt, gaan 'n bietjie om te praat oor hierdie ander term

273
00:20:32,380 --> 00:20:36,150
wat ons gebruik wanneer hulle praat oor die bome, wat genoem word die hoogte.

274
00:20:36,150 --> 00:20:45,460
>> Die hoogte van 'n boom is die afstand vanaf die wortel tot die mees verre node,

275
00:20:45,460 --> 00:20:48,370
of eerder die getal van hoep wat jy sal moet maak ten einde

276
00:20:48,370 --> 00:20:53,750
begin van die wortel en dan uiteindelik by die mees afgeleë nodus in die boom.

277
00:20:53,750 --> 00:20:57,330
As ons kyk by sommige van hierdie bome wat ons het hier gevestig,

278
00:20:57,330 --> 00:21:07,870
kan ons sien dat as ons hierdie boom in die boonste linkerkantste hoek en ons begin by die 3,

279
00:21:07,870 --> 00:21:14,510
dan het ons 1 hop te kry om die 6 te maak, 'n tweede hop om te kry aan die 7,

280
00:21:14,510 --> 00:21:20,560
en 1/3 hop te kry tot die 9.

281
00:21:20,560 --> 00:21:26,120
So, die hoogte van hierdie boom is 3.

282
00:21:26,120 --> 00:21:30,640
Ons kan dit doen dieselfde oefening vir die ander bome wat met hierdie groen uiteengesit,

283
00:21:30,640 --> 00:21:40,100
en ons sien dat die hoogte van al hierdie bome is inderdaad ook 3.

284
00:21:40,100 --> 00:21:45,230
Dit is deel van wat maak hulle ontaard -

285
00:21:45,230 --> 00:21:53,750
dat hulle hoogte is net een minder as die aantal nodes in die hele boom.

286
00:21:53,750 --> 00:21:58,400
As ons kyk na die ander boom wat omring is met rooi, aan die ander kant,

287
00:21:58,400 --> 00:22:03,920
sien ons dat die mees verre blaar nodes is die 6 en die 9 -

288
00:22:03,920 --> 00:22:06,940
die blare die nodes wat geen kinders het.

289
00:22:06,940 --> 00:22:11,760
So, in orde te kry van die wortel node óf die 6 of 9,

290
00:22:11,760 --> 00:22:17,840
ons een hop te maak om te kry aan die 7 en dan 'n tweede hop om te kry tot die 9,

291
00:22:17,840 --> 00:22:21,240
en so ook, om net 'n tweede hop van die 7 aan die 6.

292
00:22:21,240 --> 00:22:29,080
So, die hoogte van hierdie boom hier is net 2.

293
00:22:29,080 --> 00:22:35,330
Jy kan terug gaan en doen wat vir al die ander bome wat ons voorheen bespreek

294
00:22:35,330 --> 00:22:37,380
begin met die 7 en die 6,

295
00:22:37,480 --> 00:22:42,500
en jy sal vind dat die hoogte van al die bome is ook 2.

296
00:22:42,500 --> 00:22:46,320
>> Die rede waarom ons het gepraat oor binêre bome bestel

297
00:22:46,320 --> 00:22:50,250
en hoekom hulle is cool is, want jy kan soek deur hulle in

298
00:22:50,250 --> 00:22:53,810
'n soortgelyke manier om te soek oor 'n gesorteerde skikking.

299
00:22:53,810 --> 00:22:58,720
Dit is waar ons praat oor om dat verbeterde lookup tyd

300
00:22:58,720 --> 00:23:02,730
oor die eenvoudige geskakelde lys.

301
00:23:02,730 --> 00:23:05,010
Met 'n geskakelde lys - as jy wil om 'n spesifieke element te vind -

302
00:23:05,010 --> 00:23:07,470
jy by die beste gaan om 'n soort van lineêre soek om te doen

303
00:23:07,470 --> 00:23:10,920
waar jy begin by die begin van 'n lys en hop een-vir-een -

304
00:23:10,920 --> 00:23:12,620
een knoop deur een node -

305
00:23:12,620 --> 00:23:16,060
deur die hele lys totdat jy alles wat jy op soek is na.

306
00:23:16,060 --> 00:23:19,440
AANGESIEN dat, as jy 'n binêre boom wat in hierdie mooi formaat gestoor,

307
00:23:19,440 --> 00:23:23,300
jy kan eintlik meer van 'n binêre soek op

308
00:23:23,300 --> 00:23:25,160
waar jy verdeel en oorwin

309
00:23:25,160 --> 00:23:29,490
en soek deur die toepaslike helfte van die boom by elke stap.

310
00:23:29,490 --> 00:23:32,840
Kom ons kyk hoe dit werk.

311
00:23:32,840 --> 00:23:38,850
>> As ons weer terug te gaan na ons oorspronklike boom -

312
00:23:38,850 --> 00:23:46,710
ons begin op 7, ons het 3 aan die linkerkant, 9 aan die regterkant,

313
00:23:46,710 --> 00:23:51,740
en onder die 3 het ons die 6.

314
00:23:51,740 --> 00:24:01,880
As ons wil hê om te soek na die getal 6 in hierdie boom, wil ons begin by die wortel.

315
00:24:01,880 --> 00:24:08,910
Ons wil vergelyk die waarde wat ons is op soek na, sê 6,

316
00:24:08,910 --> 00:24:12,320
die waarde wat gestoor word in die node wat ons tans op soek is na, 7,

317
00:24:12,320 --> 00:24:21,200
vind dat 6 inderdaad minder as 7, so ons wil skuif na links.

318
00:24:21,200 --> 00:24:25,530
Indien die waarde van 6 was groter as 7, sou ons plaas het na regs verskuif.

319
00:24:25,530 --> 00:24:29,770
Omdat ons weet dat as gevolg van die struktuur van ons bestel binêre boom -

320
00:24:29,770 --> 00:24:33,910
al die waardes minder as 7 geberg gaan word aan die linkerkant van 7,

321
00:24:33,910 --> 00:24:40,520
daar is geen behoefte om selfs moeite soek deur middel van die regterkant van die boom.

322
00:24:40,520 --> 00:24:43,780
Wanneer ons na links beweeg en ons is nou by die node met 3,

323
00:24:43,780 --> 00:24:48,110
kan ons weer dieselfde vergelyking doen waar ons dit vergelyk met die 3 en die 6.

324
00:24:48,110 --> 00:24:52,430
En ons vind dat, terwyl 6 - die waarde wat ons is op soek na - is groter as 3,

325
00:24:52,430 --> 00:24:58,580
ons kan gaan na die regterkant van die node met 3.

326
00:24:58,580 --> 00:25:02,670
Daar is geen linkerkant hier, sodat ons kan geïgnoreer het dat.

327
00:25:02,670 --> 00:25:06,510
Maar ons weet net dat omdat ons is op soek na die boom self,

328
00:25:06,510 --> 00:25:08,660
en ons kan sien dat die boom het nie kinders nie.

329
00:25:08,660 --> 00:25:13,640
>> Dit is ook redelik maklik om op te kyk 6 in hierdie boom as ons dit doen onsself as mense,

330
00:25:13,640 --> 00:25:16,890
maar laat ons hierdie proses volg meganies soos 'n rekenaar sou doen

331
00:25:16,890 --> 00:25:18,620
om regtig te verstaan ​​die algoritme.

332
00:25:18,620 --> 00:25:26,200
Op hierdie punt, ons is nou op soek na 'n node bevat 6,

333
00:25:26,200 --> 00:25:29,180
en ons is op soek vir die waarde 6,

334
00:25:29,180 --> 00:25:31,740
ja, inderdaad, het ons gevind dat die toepaslike node.

335
00:25:31,740 --> 00:25:35,070
Ons het gevind dat die waarde 6 in ons boom, en ons kan ons soek stop.

336
00:25:35,070 --> 00:25:37,330
Op hierdie punt, afhangende van wat gaan aan,

337
00:25:37,330 --> 00:25:41,870
ons kan sê, ja, ons die waarde 6 gevind het, dit bestaan ​​in ons boom.

338
00:25:41,870 --> 00:25:47,640
Of, as ons van plan is om 'n node te voeg of om iets te doen, kan ons dit doen op hierdie punt.

339
00:25:47,640 --> 00:25:53,010
>> Kom ons doen 'n paar soektogte net om te sien hoe dit werk.

340
00:25:53,010 --> 00:25:59,390
Kom ons kyk wat gebeur as ons was om te probeer en kyk op die waarde 10.

341
00:25:59,390 --> 00:26:02,970
As ons kyk op die waarde 10, sal ons begin by die wortel.

342
00:26:02,970 --> 00:26:07,070
Ons wil sien dat 10 groter as 7, so ons wil skuif na regs.

343
00:26:07,070 --> 00:26:13,640
Ons wil na die 9 en vergelyk 9 aan die 10 en sien dat 9 inderdaad minder as 10.

344
00:26:13,640 --> 00:26:16,210
Dit weer doen, wil ons probeer om te beweeg na regs.

345
00:26:16,210 --> 00:26:20,350
Maar op hierdie punt, wil ons sien dat ons op 'n null node.

346
00:26:20,350 --> 00:26:23,080
Daar is niks. Daar is niks waar die 10 moet wees.

347
00:26:23,080 --> 00:26:29,360
Dit is waar ons kan rapporteer mislukking - dat daar is inderdaad geen 10 in die boom.

348
00:26:29,360 --> 00:26:35,420
En ten slotte, laat ons gaan deur middel van die geval waar ons probeer om te kyk 1 in die boom.

349
00:26:35,420 --> 00:26:38,790
Dit is soortgelyk aan wat gebeur as ons kyk op 10, behalwe in plaas van gaan na regs,

350
00:26:38,790 --> 00:26:41,260
ons gaan om te gaan na die linkerkant.

351
00:26:41,260 --> 00:26:46,170
Ons begin by die 7 en sien dat 1 is minder as 7, so ons skuif na links.

352
00:26:46,170 --> 00:26:51,750
Ons kry die 3 en sien dat 1 is minder as 3, so ons probeer weer om na links te beweeg.

353
00:26:51,750 --> 00:26:59,080
Op hierdie punt het ons 'n null node, sodat ons weer kan aanmeld mislukking.

354
00:26:59,080 --> 00:27:10,260
>> As jy wil meer te leer oor binêre bome,

355
00:27:10,260 --> 00:27:14,420
daar is 'n hele klomp van die pret bietjie probleme wat jy kan doen met hulle.

356
00:27:14,420 --> 00:27:19,450
Ek raai jou aan die beoefening van die tekening van hierdie diagramme een-vir-een

357
00:27:19,450 --> 00:27:21,910
en deur al die verskillende stappe volg,

358
00:27:21,910 --> 00:27:25,060
want dit sal kom in die super-handig

359
00:27:25,060 --> 00:27:27,480
nie net wanneer jy doen die Huffman kodering probleem stel

360
00:27:27,480 --> 00:27:29,390
maar ook in die toekomstige kursusse -

361
00:27:29,390 --> 00:27:32,220
net leer hoe om te trek uit hierdie data strukture en dink deur middel van die probleme

362
00:27:32,220 --> 00:27:38,000
met pen en papier, of in hierdie geval, iPad en stylus.

363
00:27:38,000 --> 00:27:41,000
>> Op hierdie punt al, ons gaan om te beweeg op sommige kodering praktyk te doen

364
00:27:41,000 --> 00:27:44,870
en eintlik speel met hierdie binêre bome en sien.

365
00:27:44,870 --> 00:27:52,150
Ek gaan om terug te skakel na my rekenaar.

366
00:27:52,150 --> 00:27:58,480
Vir hierdie deel van die artikel, in plaas van die gebruik van CS50 Run of CS50 Ruimtes,

367
00:27:58,480 --> 00:28:01,500
Ek gaan om die toestel te gebruik.

368
00:28:01,500 --> 00:28:04,950
>> Die volgende saam met die Problem Set spesifikasie,

369
00:28:04,950 --> 00:28:07,740
Ek sien dat ek veronderstel is om oop te maak die toestel,

370
00:28:07,740 --> 00:28:11,020
gaan na my Dropbox gids, skep 'n gids met die naam van Artikel 7,

371
00:28:11,020 --> 00:28:15,730
en dan skep n lêer genaamd binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Hier gaan ons. Ek het die toestel reeds oop.

373
00:28:22,050 --> 00:28:25,910
Ek gaan trek 'n terminaal.

374
00:28:25,910 --> 00:28:38,250
Ek gaan om te gaan na die Dropbox gids, maak 'n gids met die naam section7,

375
00:28:38,250 --> 00:28:42,230
en sien dit is heeltemal leeg.

376
00:28:42,230 --> 00:28:48,860
Nou gaan ek om oop te maak binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Hier gaan ons - leeg lêer.

378
00:28:51,750 --> 00:28:54,330
>> Kom ons gaan terug na die spesifikasie.

379
00:28:54,330 --> 00:28:59,850
Die spesifikasie vra om 'n nuwe soort definisie te skep

380
00:28:59,850 --> 00:29:03,080
vir 'n binêre boom node bevat int waardes -

381
00:29:03,080 --> 00:29:07,110
net soos die waardes wat ons in ons diagram voor getrek.

382
00:29:07,110 --> 00:29:11,740
Ons gaan hierdie boiler typedef te gebruik wat ons het reg hier gedoen

383
00:29:11,740 --> 00:29:14,420
dat jy moet erken van Problem Set 5 -

384
00:29:14,420 --> 00:29:19,190
as jy het die hash tafel weg van die verowering van die speller program.

385
00:29:19,190 --> 00:29:22,540
Jy moet ook erken dit uit verlede week se artikel

386
00:29:22,540 --> 00:29:23,890
waar het ons gepraat oor geskakelde lyste.

387
00:29:23,890 --> 00:29:27,870
Ons het hierdie typedef van 'n struct node,

388
00:29:27,870 --> 00:29:34,430
en ons het hierdie struct node naam van die struct node vooraf

389
00:29:34,430 --> 00:29:39,350
sodat ons kan dan verwys na dit omdat ons sal wil struct node verwysings na

390
00:29:39,350 --> 00:29:45,740
as deel van ons struct, maar ons het dan omring -

391
00:29:45,740 --> 00:29:47,700
of liewer, ingesluit in 'n typedef

392
00:29:47,700 --> 00:29:54,600
sodat, later in die kode, kan ons verwys na hierdie struct as net 'n knoop in plaas van 'n struct node.

393
00:29:54,600 --> 00:30:03,120
>> Dit is baie soortgelyk aan die enkel-geskakelde lys definisie wat ons gesien het verlede week gaan wees.

394
00:30:03,120 --> 00:30:20,070
Om dit te doen, laat ons net begin deur die skryf van die boiler.

395
00:30:20,070 --> 00:30:23,840
Ons weet dat ons 'n heelgetal waarde te hê,

396
00:30:23,840 --> 00:30:32,170
so sal ons in 'n int waarde, en dan in plaas van net een wyser na die volgende element -

397
00:30:32,170 --> 00:30:33,970
soos ons gedoen het met 'n enkel-gekoppelde lyste -

398
00:30:33,970 --> 00:30:38,110
ons gaan links en regs kind pointers te hê.

399
00:30:38,110 --> 00:30:42,880
Dit is ook redelik eenvoudig - struct node * links kind;

400
00:30:42,880 --> 00:30:51,190
en struct node * regte kind;. Cool.

401
00:30:51,190 --> 00:30:54,740
Wat lyk soos 'n baie goeie begin.

402
00:30:54,740 --> 00:30:58,530
Kom ons gaan terug na die spesifikasie.

403
00:30:58,530 --> 00:31:05,030
>> Nou moet ons 'n globale node * veranderlike te verklaar vir die wortel van 'n boom.

404
00:31:05,030 --> 00:31:10,590
Ons gaan hierdie globale net soos ons eerste wyser in ons geskakelde lys ook 'n wêreldwye te maak.

405
00:31:10,590 --> 00:31:12,690
Dit was so dat in die funksies wat ons skryf

406
00:31:12,690 --> 00:31:16,180
ons hoef nie te hou wat rondom hierdie wortel -

407
00:31:16,180 --> 00:31:19,620
maar ons sal sien dat as jy wil om hierdie funksies te rekursief te skryf,

408
00:31:19,620 --> 00:31:22,830
dit dalk beter wees om nie eens te slaag dit rond in die eerste plek as 'n globale

409
00:31:22,830 --> 00:31:28,090
en in plaas inisialiseer dit plaaslik in jou hooffunksie.

410
00:31:28,090 --> 00:31:31,960
Maar, sal ons dit doen wêreldwyd te begin.

411
00:31:31,960 --> 00:31:39,920
Weereens, ons sal 'n paar van ruimtes, en ek gaan 'n node * wortel te verklaar.

412
00:31:39,920 --> 00:31:46,770
Net om seker te maak dat ek nie laat dit geïnitialiseerd, ek gaan om dit te gelyk stel aan nul.

413
00:31:46,770 --> 00:31:52,210
Nou, in die belangrikste funksie - wat sal ons regtig vinnig reg hier te skryf -

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

415
00:32:00,450 --> 00:32:10,640
en ek gaan om te begin verklaar my bevat SPASIES skikking as const net sodat ek weet

416
00:32:10,640 --> 00:32:14,550
daardie argumente is argumente dat ek waarskynlik nie wil verander nie.

417
00:32:14,550 --> 00:32:18,390
As ek wil om dit te verander Ek moet seker maak afskrifte van hulle.

418
00:32:18,390 --> 00:32:21,740
Jy sal sien 'n lot in die kode.

419
00:32:21,740 --> 00:32:25,440
Dis boete óf manier. Dit is goed om dit te verlaat as die const weglaat as jy wil.

420
00:32:25,440 --> 00:32:28,630
Ek gewoonlik sit dit in net so dat ek herinner myself

421
00:32:28,630 --> 00:32:33,650
 dat ek waarskynlik nie wil hê dat die argumente te verander.

422
00:32:33,650 --> 00:32:39,240
>> Soos altyd, ek gaan hierdie opgawe 0 lyn aan die einde van die hoof te sluit.

423
00:32:39,240 --> 00:32:45,730
Hierheen, ek sal inisialiseer my wortel node.

424
00:32:45,730 --> 00:32:48,900
Soos dit staan ​​op die oomblik, ek het 'n wyser wat aan nul,

425
00:32:48,900 --> 00:32:52,970
so dit is wys niks.

426
00:32:52,970 --> 00:32:57,480
Ten einde om werklik te begin met die bou van die node,

427
00:32:57,480 --> 00:32:59,250
Ek het eers geheue vir dit te ken.

428
00:32:59,250 --> 00:33:05,910
Ek gaan om dit te doen deur die geheue op die hoop, met behulp van malloc te maak.

429
00:33:05,910 --> 00:33:10,660
Ek gaan wortel gelyk aan die resultaat van malloc te stel,

430
00:33:10,660 --> 00:33:19,550
en ek gaan die sizeof operator om te gebruik om die grootte van 'n node te bereken.

431
00:33:19,550 --> 00:33:24,990
Die rede wat ek gebruik sizeof node, in teenstelling met, sê,

432
00:33:24,990 --> 00:33:37,020
om iets te doen soos hierdie - malloc (4 + 4 +4) of malloc 12 -

433
00:33:37,020 --> 00:33:40,820
is, want ek wil my kode verenigbaar as moontlik te wees.

434
00:33:40,820 --> 00:33:44,540
Ek wil in staat wees om hierdie c-lêer te neem, stel dit op die toestel,

435
00:33:44,540 --> 00:33:48,820
en dan stel dit op my 64-bis Mac -

436
00:33:48,820 --> 00:33:52,040
of op 'n heeltemal ander argitektuur -

437
00:33:52,040 --> 00:33:54,640
en ek wil dit al die dieselfde te werk.

438
00:33:54,640 --> 00:33:59,510
>> As ek maak aannames oor die grootte van veranderlikes -

439
00:33:59,510 --> 00:34:02,070
die grootte van 'n int of die grootte van 'n wyser -

440
00:34:02,070 --> 00:34:06,070
dan is ek ook die maak van aannames oor die aard van die architecture

441
00:34:06,070 --> 00:34:10,440
wat my kode suksesvol kan stel wanneer dit uitgevoer word.

442
00:34:10,440 --> 00:34:15,030
Altyd gebruik sizeof, in teenstelling met die hand die WHALM struct velde.

443
00:34:15,030 --> 00:34:20,500
Die ander rede is dat daar dalk ook padding dat die vertaler sit in die struct.

444
00:34:20,500 --> 00:34:26,570
Selfs net 'n opsomming van die individuele velde is nie iets wat jy tipies wil om dit te doen,

445
00:34:26,570 --> 00:34:30,340
so, verwyder daardie lyn.

446
00:34:30,340 --> 00:34:33,090
Nou, om werklik te inisialiseer hierdie wortel node,

447
00:34:33,090 --> 00:34:36,489
Ek gaan hê om te prop in die waardes vir elk van die verskillende velde.

448
00:34:36,489 --> 00:34:41,400
Byvoorbeeld, vir waarde Ek weet ek wil om te inisialiseer tot 7,

449
00:34:41,400 --> 00:34:46,920
en nou gaan ek te stel die linker kind te wees null

450
00:34:46,920 --> 00:34:55,820
en die reg om kind te wees null. Great!

451
00:34:55,820 --> 00:35:02,670
Ons gedoen het dat 'n deel van die spec.

452
00:35:02,670 --> 00:35:07,390
>> Die spesifikasie aan die onderkant van die bladsy 3 vra my drie nodes te skep -

453
00:35:07,390 --> 00:35:10,600
een met 3, een met 6, en een met 9 -

454
00:35:10,600 --> 00:35:14,210
en dan bedraad hulle sodat dit lyk presies soos ons boomdiagram

455
00:35:14,210 --> 00:35:17,120
dat ons oor gepraat het.

456
00:35:17,120 --> 00:35:20,450
Kom ons doen dit redelik vinnig hier.

457
00:35:20,450 --> 00:35:26,270
Jy regtig vinnig sien wat ek gaan om te begin met die skryf van 'n klomp van duplikaat-kode.

458
00:35:26,270 --> 00:35:32,100
Ek gaan 'n node te skep * en ek gaan om te noem dit drie.

459
00:35:32,100 --> 00:35:36,000
Ek gaan om dit gelyk te stel malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Ek gaan tot drie-> waarde stel = 3.

461
00:35:41,070 --> 00:35:54,780
Drie -> left_child = NULL, drie -> regs _child = NULL, asook.

462
00:35:54,780 --> 00:36:01,150
Dit lyk redelik soortgelyk aan die inisialisering van die wortel, en dit is presies wat

463
00:36:01,150 --> 00:36:05,760
Ek gaan te hê om te doen as ek begin inisialisering 6 en 9 asook.

464
00:36:05,760 --> 00:36:20,720
Ek sal doen wat regtig vinnig hier - eintlik, ek gaan 'n bietjie kopie en plak om dit te doen,

465
00:36:20,720 --> 00:36:46,140
en maak seker dat ek - alright.

466
00:36:46,470 --> 00:37:09,900
 Nou, ek het dit gekopieer en ek kan voort te gaan en stel dit gelyk aan 6.

467
00:37:09,900 --> 00:37:14,670
Jy kan sien dat dit 'n rukkie neem en is nie super-doeltreffende.

468
00:37:14,670 --> 00:37:22,610
In net 'n bietjie, sal ons skryf 'n funksie wat doen dit vir ons.

469
00:37:22,610 --> 00:37:32,890
Ek wil om dit te vervang met 'n 9 is, vervang dit met 'n 6.

470
00:37:32,890 --> 00:37:37,360
>> Nou het ons al van ons nodes geskep en geïnisialiseer.

471
00:37:37,360 --> 00:37:41,200
Ons het ons wortel stel gelyk aan 7, of met die waarde 7,

472
00:37:41,200 --> 00:37:46,510
ons node bevat 3, ons node met 6 en ons node bevat 9.

473
00:37:46,510 --> 00:37:50,390
Op hierdie punt, al wat ons moet doen, is draad alles op.

474
00:37:50,390 --> 00:37:53,020
Die rede waarom ek al die wenke geïnisialiseer aan nul is net sodat ek seker maak dat

475
00:37:53,020 --> 00:37:56,260
Ek het nie enige geïnitialiseerd pointers daar deur 'n ongeluk.

476
00:37:56,260 --> 00:38:02,290
En ook omdat, op hierdie punt, ek het net om werklik die nodusse verbind aan mekaar -

477
00:38:02,290 --> 00:38:04,750
aan die mense wat hulle eintlik verbonde aan - Ek het nie om deur te gaan en maak

478
00:38:04,750 --> 00:38:08,240
seker dat al die nulls is daar in die toepaslike plekke.

479
00:38:08,240 --> 00:38:15,630
>> Begin by die wortel, ek weet dat die wortel se links kind is 3.

480
00:38:15,630 --> 00:38:21,250
Ek weet dat die wortel se reg kind 9.

481
00:38:21,250 --> 00:38:24,880
Daarna het die enigste ander kind wat ek verlaat het om oor bekommerd te wees nie

482
00:38:24,880 --> 00:38:39,080
is 3 se reg kind, wat is 6.

483
00:38:39,080 --> 00:38:44,670
Op hierdie punt, dit lyk redelik goed.

484
00:38:44,670 --> 00:38:54,210
Ons sal verwyder sommige van hierdie lyne.

485
00:38:54,210 --> 00:38:59,540
Nou is alles lyk redelik goed.

486
00:38:59,540 --> 00:39:04,240
Kom ons gaan terug na ons spesifikasie en sien wat ons het om volgende te doen.

487
00:39:04,240 --> 00:39:07,610
>> Op hierdie punt, ons het om te skryf 'n funksie genoem "bevat"

488
00:39:07,610 --> 00:39:14,150
met 'n prototipe van 'Bool bevat (int waarde).

489
00:39:14,150 --> 00:39:17,060
En dit bevat funksie gaan om terug te keer waar

490
00:39:17,060 --> 00:39:21,200
 indien die boom wys deur ons wêreldwye wortel veranderlike

491
00:39:21,200 --> 00:39:26,950
 bevat die waarde wat geslaag is in die funksie en valse anders.

492
00:39:26,950 --> 00:39:29,000
Kom ons gaan voort en doen wat.

493
00:39:29,000 --> 00:39:35,380
Dit gaan om presies te wees soos die lookup wat ons gedoen het met die hand op die iPad net 'n bietjie gelede.

494
00:39:35,380 --> 00:39:40,130
Kom ons gaan terug zoom in 'n bietjie en scroll up.

495
00:39:40,130 --> 00:39:43,130
Ons gaan hierdie funksie reg te stel bo ons hooffunksie

496
00:39:43,130 --> 00:39:48,990
sodat ons nie enige soort van prototyping te doen.

497
00:39:48,990 --> 00:39:55,960
So, Bool bevat (int waarde).

498
00:39:55,960 --> 00:40:00,330
Daar gaan ons. Daar is ons boiler verklaring.

499
00:40:00,330 --> 00:40:02,900
Net om seker te maak dat dit sal stel,

500
00:40:02,900 --> 00:40:06,820
Ek gaan om voort te gaan en dit net gelykgestel vals om terug te keer.

501
00:40:06,820 --> 00:40:09,980
Reg nou hierdie funksie sal net nie enigiets doen en altyd rapporteer dat

502
00:40:09,980 --> 00:40:14,010
die waarde wat ons soek is nie in die boom.

503
00:40:14,010 --> 00:40:16,280
>> Op hierdie punt, is dit waarskynlik 'n goeie idee -

504
00:40:16,280 --> 00:40:19,600
want ons het 'n hele klomp van die kode geskryf en ons het nie eens probeer om dit te toets nog -

505
00:40:19,600 --> 00:40:22,590
om seker te maak dat dit alles stel.

506
00:40:22,590 --> 00:40:27,460
Daar is 'n paar van die dinge wat ons moet doen om seker te maak dat dit eintlik sal saamstel.

507
00:40:27,460 --> 00:40:33,530
Eerste, kyk of ons het al met behulp van enige funksies in enige biblioteke dat ons nog nie ingesluit nie.

508
00:40:33,530 --> 00:40:37,940
Die funksies wat ons tot dusver gebruik is malloc,

509
00:40:37,940 --> 00:40:43,310
en dan het ons ook die gebruik van hierdie tipe - hierdie nie-standaard tipe genoem 'bool' -

510
00:40:43,310 --> 00:40:45,750
wat is ingesluit in die standaard Bool header-lêer.

511
00:40:45,750 --> 00:40:53,250
Ons wil beslis standaard bool.h vir die Bool tipe in te sluit,

512
00:40:53,250 --> 00:40:59,230
en ons wil ook # include standaard lib.h vir die standaard biblioteke

513
00:40:59,230 --> 00:41:03,530
wat insluit malloc, en vry, en al wat.

514
00:41:03,530 --> 00:41:08,660
So, uitzoomen, ons gaan om te stop.

515
00:41:08,660 --> 00:41:14,190
Kom ons probeer en maak seker dat dit eintlik gedoen saamstel.

516
00:41:14,190 --> 00:41:18,150
Ons sien dat dit nie, so ons is op die regte pad.

517
00:41:18,150 --> 00:41:22,990
>> Kom ons oopmaak binary_tree.c weer.

518
00:41:22,990 --> 00:41:34,530
Dit stel. Kom ons gaan sit en maak seker dat ons voeg 'n paar oproepe vir ons bevat funksie -

519
00:41:34,530 --> 00:41:40,130
net om seker te maak dat dit is alles goed en wel.

520
00:41:40,130 --> 00:41:43,170
Byvoorbeeld, wanneer ons het 'n paar soektogte in ons boom vroeër,

521
00:41:43,170 --> 00:41:48,500
ons probeer om te kyk op die waardes 6, 10 en 1, en ons het geweet dat 6 was in die boom,

522
00:41:48,500 --> 00:41:52,220
10 in die boom was nie, en 1 was nie in die boom.

523
00:41:52,220 --> 00:41:57,230
Kom ons gebruik daardie monster oproepe as 'n manier om uit te vind of

524
00:41:57,230 --> 00:41:59,880
ons bevat funksie werk.

525
00:41:59,880 --> 00:42:05,210
Ten einde dit te doen, ek gaan die printf funksie te gebruik,

526
00:42:05,210 --> 00:42:10,280
en ons gaan uit te druk die resultaat van die oproep om te bevat.

527
00:42:10,280 --> 00:42:13,280
Ek gaan sit in 'n string "bevat (% d) = omdat

528
00:42:13,280 --> 00:42:20,470
 ons gaan prop in die waarde wat ons gaan om te kyk vir,

529
00:42:20,470 --> 00:42:27,130
en =% s \ n "en gebruik dit as ons formaat string.

530
00:42:27,130 --> 00:42:30,720
Ons is net gaan om te sien - letterlik uit te druk op die skerm -

531
00:42:30,720 --> 00:42:32,060
wat lyk soos 'n funksie oproep.

532
00:42:32,060 --> 00:42:33,580
Dit is nie eintlik die funksie oproep.

533
00:42:33,580 --> 00:42:36,760
 Dit is net 'n string wat ontwerp is om te lyk soos 'n funksie oproep.

534
00:42:36,760 --> 00:42:41,140
>> Nou gaan ons te prop in die waardes.

535
00:42:41,140 --> 00:42:43,580
Ons gaan bevat om te probeer om op 6,

536
00:42:43,580 --> 00:42:48,340
en dan wat ons gaan doen, is dat die drieledige operateur.

537
00:42:48,340 --> 00:42:56,340
Kom ons kyk - bevat 6 - ja, nou het ek vervat 6 en as bevat 6 is waar,

538
00:42:56,340 --> 00:43:01,850
die tou wat ons gaan om te stuur na die% s formaat karakter

539
00:43:01,850 --> 00:43:04,850
gaan die string "ware".

540
00:43:04,850 --> 00:43:07,690
Kom se scroll oor 'n bietjie.

541
00:43:07,690 --> 00:43:16,210
Anders, ons wil stuur die string "vals" as bevat 6 opbrengste valse.

542
00:43:16,210 --> 00:43:19,730
Dit is 'n bietjie stom-soek, maar ek figuur Ek kan net so goed illustreer

543
00:43:19,730 --> 00:43:23,780
wat die drieledige operateur lyk, aangesien ons nie gesien het nie dit vir 'n rukkie.

544
00:43:23,780 --> 00:43:27,670
Dit sal 'n mooi, handige manier om uit te vind of ons bevat funksie werk.

545
00:43:27,670 --> 00:43:30,040
Ek gaan om terug te blaai na links,

546
00:43:30,040 --> 00:43:39,900
en ek gaan hierdie lyn te kopieer en plak 'n paar keer.

547
00:43:39,900 --> 00:43:44,910
Dit verander 'n paar van hierdie waardes rond,

548
00:43:44,910 --> 00:43:59,380
so dit gaan te wees 1, en dit gaan te wees 10.

549
00:43:59,380 --> 00:44:02,480
>> Op hierdie punt het ons 'n mooi bevat funksie.

550
00:44:02,480 --> 00:44:06,080
Ons het 'n paar toetse, en ons sal sien of dit al die werke.

551
00:44:06,080 --> 00:44:08,120
Op hierdie punt het ons meer kode geskryf.

552
00:44:08,120 --> 00:44:13,160
Tyd om op te hou en maak seker dat alles steeds stel.

553
00:44:13,160 --> 00:44:20,360
Sluit uit, en laat ons nou probeer om binêre boom weer.

554
00:44:20,360 --> 00:44:22,260
Wel, dit lyk asof ons het 'n fout,

555
00:44:22,260 --> 00:44:26,930
en ons het dit het uitdruklik verklaar dat die biblioteek funksie printf.

556
00:44:26,930 --> 00:44:39,350
Dit lyk soos wat ons nodig het om in te gaan en # standardio.h sluit.

557
00:44:39,350 --> 00:44:45,350
En met dié, moet alles stel. Ons is almal goed.

558
00:44:45,350 --> 00:44:50,420
Laat ons nou probeer om binêre boom en kyk wat gebeur.

559
00:44:50,420 --> 00:44:53,520
Hier is ons, / binary_tree.

560
00:44:53,520 --> 00:44:55,190
en ons sien dat, as ons verwag -

561
00:44:55,190 --> 00:44:56,910
want ons het nie geïmplementeer nie bevat nie,

562
00:44:56,910 --> 00:44:59,800
of liewer, ons het net in return false -

563
00:44:59,800 --> 00:45:03,300
sien ons dat dit net terugkeer vir almal van hulle vals,

564
00:45:03,300 --> 00:45:06,180
so wat al die werk vir die grootste deel redelik goed.

565
00:45:06,180 --> 00:45:11,860
>> Laat se rug in te gaan en werklik uit te voer bevat op hierdie punt.

566
00:45:11,860 --> 00:45:17,490
Ek gaan om te blaai, zoom in en -

567
00:45:17,490 --> 00:45:22,330
onthou, die algoritme wat ons gebruik het, was dat ons begin by die wortel node

568
00:45:22,330 --> 00:45:28,010
en dan by elke node wat ons teëkom, het ons 'n vergelyking doen,

569
00:45:28,010 --> 00:45:32,380
en wat gebaseer is op daardie vergelyking ons óf beweeg aan die linkerkant kind of aan die regterkant kind.

570
00:45:32,380 --> 00:45:39,670
Dit gaan lyk baie soortgelyk aan die binêre soek kode wat ons geskryf het vroeër in die kwartaal.

571
00:45:39,670 --> 00:45:47,810
Wanneer ons begin, weet ons dat ons wil om vas te hou aan die huidige node

572
00:45:47,810 --> 00:45:54,050
dat ons op soek is na, en die huidige node geïnisialiseer gaan word aan die wortel node.

573
00:45:54,050 --> 00:45:56,260
En nou, ons gaan om voort te gaan deur middel van die boom,

574
00:45:56,260 --> 00:45:58,140
en onthou dat ons stop toestand -

575
00:45:58,140 --> 00:46:01,870
 wanneer ons werklik deur die voorbeeld gewerk het met die hand -

576
00:46:01,870 --> 00:46:03,960
was toe ons ondervind 'n null node,

577
00:46:03,960 --> 00:46:05,480
nie wanneer ons kyk na 'n null kind,

578
00:46:05,480 --> 00:46:09,620
maar eerder wanneer ons eintlik na 'n nodus in die boom

579
00:46:09,620 --> 00:46:12,640
en gevind dat ons op 'n null node.

580
00:46:12,640 --> 00:46:20,720
Ons gaan om te itereer totdat die huidige is nie gelyk aan nul.

581
00:46:20,720 --> 00:46:22,920
En wat gaan ons doen?

582
00:46:22,920 --> 00:46:31,610
Ons gaan om te toets of (huidige -> waarde == waarde),

583
00:46:31,610 --> 00:46:35,160
dan weet ons dat ons eintlik het die knoop gevind dat ons op soek is na.

584
00:46:35,160 --> 00:46:40,450
So hier is, kan ons terugkeer waar.

585
00:46:40,450 --> 00:46:49,830
Anders, ons wil om te sien of die waarde is minder as die waarde.

586
00:46:49,830 --> 00:46:53,850
As die huidige node se waarde is minder as die waarde wat ons soek,

587
00:46:53,850 --> 00:46:57,280
ons gaan om te beweeg na regs.

588
00:46:57,280 --> 00:47:10,600
So, huidig ​​= huidige -> right_child; en andersins, ons gaan om te skuif na links.

589
00:47:10,600 --> 00:47:17,480
huidig ​​= huidige -> left_child;. Eenvoudig.

590
00:47:17,480 --> 00:47:22,830
>> Jy het waarskynlik besef die lus wat lyk baie soortgelyk aan dié van

591
00:47:22,830 --> 00:47:27,580
binêre soek vroeër in die kwartaal nie, behalwe dan het ons te doen het met 'n lae, middel, en 'n hoë.

592
00:47:27,580 --> 00:47:30,000
Hier, ons het net om te kyk na 'n huidige waarde,

593
00:47:30,000 --> 00:47:31,930
so dit is lekker en maklik.

594
00:47:31,930 --> 00:47:34,960
Kom ons maak seker dat hierdie kode werk.

595
00:47:34,960 --> 00:47:42,780
Eerstens, maak seker dit stel. Lyk soos dit nie.

596
00:47:42,780 --> 00:47:47,920
Kom ons probeer om dit te draai.

597
00:47:47,920 --> 00:47:50,160
En inderdaad, dit druk uit alles wat ons verwag het.

598
00:47:50,160 --> 00:47:54,320
Dit vind 6 in die boom, vind nie 10 want 10 is nie in die boom,

599
00:47:54,320 --> 00:47:57,740
en dit nie vind nie 1 óf omdat 1 is ook nie in die boom.

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

601
00:48:01,420 --> 00:48:04,470
>> Alright. Kom ons gaan terug na ons spesifikasie en sien wat is volgende.

602
00:48:04,470 --> 00:48:07,990
Nou, dit wil 'n paar meer nodes te voeg aan ons boom.

603
00:48:07,990 --> 00:48:11,690
Dit wil 5, 2 en 8 te voeg, en maak seker dat ons bevat kode

604
00:48:11,690 --> 00:48:13,570
nog steeds werk soos verwag.

605
00:48:13,570 --> 00:48:14,900
Kom ons gaan doen.

606
00:48:14,900 --> 00:48:19,430
Op hierdie punt, eerder as om weer daardie irriterende kopieer en plak,

607
00:48:19,430 --> 00:48:23,770
laat skryf 'n funksie om werklik 'n node.

608
00:48:23,770 --> 00:48:27,740
As ons scroll down al die pad na die hoof, sien ons dat ons dit nou al doen

609
00:48:27,740 --> 00:48:31,210
baie soortgelyke kode oor en oor weer elke keer wat ons wil hê om 'n node te skep.

610
00:48:31,210 --> 00:48:39,540
>> Kom ons skryf 'n funksie wat eintlik 'n node bou vir ons en stuur dit terug.

611
00:48:39,540 --> 00:48:41,960
Ek gaan noem dit build_node.

612
00:48:41,960 --> 00:48:45,130
Ek gaan 'n node te bou met 'n spesifieke waarde.

613
00:48:45,130 --> 00:48:51,040
Zoom hier.

614
00:48:51,040 --> 00:48:56,600
Die eerste ding wat ek gaan doen is eintlik skep ruimte vir die node op die hoop.

615
00:48:56,600 --> 00:49:05,400
So, node * n = malloc (sizeof (node)); n -> waarde = waarde;

616
00:49:05,400 --> 00:49:14,960
en dan hier, is ek net gaan om al die velde te inisialiseer om toepaslike waardes.

617
00:49:14,960 --> 00:49:22,500
En heel aan die einde, sal ons terugkeer ons node.

618
00:49:22,500 --> 00:49:28,690
Alright. Een ding om daarop te let dat hierdie funksie is reg hier

619
00:49:28,690 --> 00:49:34,320
gaan om 'n wyser terug te keer na geheue wat hoop toegewys is.

620
00:49:34,320 --> 00:49:38,880
Wat is mooi oor hierdie is dat hierdie node nou -

621
00:49:38,880 --> 00:49:42,420
ons het dit op die hoop te verklaar, want as ons verklaar dat dit op die stapel

622
00:49:42,420 --> 00:49:45,050
sou ons nie in staat wees om dit te doen in hierdie funksie soos hierdie.

623
00:49:45,050 --> 00:49:47,690
Dat die geheue sal gaan uit van die omvang

624
00:49:47,690 --> 00:49:51,590
en ongeldig sou wees as ons probeer om dit later toegang.

625
00:49:51,590 --> 00:49:53,500
Aangesien ons hoop toegewys geheue te verklaar,

626
00:49:53,500 --> 00:49:55,830
ons gaan hê om te sorg vir bevry dit later

627
00:49:55,830 --> 00:49:58,530
vir ons program nie 'n geheue lek.

628
00:49:58,530 --> 00:50:01,270
Ons het die skrik vir alles anders in die kode

629
00:50:01,270 --> 00:50:02,880
net vir wille van eenvoud op die oomblik,

630
00:50:02,880 --> 00:50:05,610
maar as jy ooit 'n funksie wat lyk soos hierdie

631
00:50:05,610 --> 00:50:10,370
waar jy het - sommige noem dit 'n malloc of realloc binne -

632
00:50:10,370 --> 00:50:14,330
jy wil om seker te maak dat jy 'n soort van kommentaar hier wat sê,

633
00:50:14,330 --> 00:50:29,970
hey, jy weet, gee 'n hoop-toegekende node geïnisialiseer met die vraestel-in waarde.

634
00:50:29,970 --> 00:50:33,600
En dan kan jy wil om seker te maak dat jy in 'n soort van kennis wat sê

635
00:50:33,600 --> 00:50:41,720
die oproeper moet bevry die terugkeer geheue.

636
00:50:41,720 --> 00:50:45,450
Op dié manier, as iemand ooit gaan en gebruik daardie funksie,

637
00:50:45,450 --> 00:50:48,150
weet hulle dat alles wat hulle terug te kry van daardie funksie

638
00:50:48,150 --> 00:50:50,870
op 'n sekere punt sal moet word bevry.

639
00:50:50,870 --> 00:50:53,940
>> Die veronderstelling dat dit is alles goed en wel hier,

640
00:50:53,940 --> 00:51:02,300
ons kan gaan in ons kode en vervang alle van hierdie lyne hier

641
00:51:02,300 --> 00:51:05,410
met 'n oproepe na ons build node funksie.

642
00:51:05,410 --> 00:51:08,170
Kom ons doen dit regtig vinnig.

643
00:51:08,170 --> 00:51:15,840
Die een deel wat ons nie gaan om te vervang, is hierdie gedeelte af hier

644
00:51:15,840 --> 00:51:18,520
aan die onderkant waar ons eintlik bedraad die nodes om te wys aan mekaar,

645
00:51:18,520 --> 00:51:21,030
want wat ons nie kan doen in ons funksie.

646
00:51:21,030 --> 00:51:37,400
Maar, laat ons doen wortel = build_node (7); node * drie = build_node (3);

647
00:51:37,400 --> 00:51:47,980
knoop * Ses = build_node (6); node * 9 = build_node (9);

648
00:51:47,980 --> 00:51:52,590
En nou, ons wou ook nodes te voeg -

649
00:51:52,590 --> 00:52:03,530
node * Vyf = build_node (5); node * Agt = build_node (8);

650
00:52:03,530 --> 00:52:09,760
en wat was die ander node? Kom ons kyk hier. Ons wou ook 'n 2 -

651
00:52:09,760 --> 00:52:20,280
node * twee = build_node (2);

652
00:52:20,280 --> 00:52:26,850
Alright. Op hierdie punt, ons weet dat ons die 7, 3, 9, en die 6 het

653
00:52:26,850 --> 00:52:30,320
alle bedraad gepas nie, maar wat oor die 5, 8, en die 2?

654
00:52:30,320 --> 00:52:33,550
Alles in die korrekte volgorde te hou,

655
00:52:33,550 --> 00:52:39,230
ons weet dat drie se reg kind is 6.

656
00:52:39,230 --> 00:52:40,890
So, as ons gaan die 5 toe te voeg,

657
00:52:40,890 --> 00:52:46,670
die 5 behoort ook in die regterkant van die boom waarvan 3 is die wortel,

658
00:52:46,670 --> 00:52:50,440
so 5 behoort as die linker kind van 6.

659
00:52:50,440 --> 00:52:58,650
Ons kan dit doen deur te sê, ses -> left_child = vyf

660
00:52:58,650 --> 00:53:10,790
en dan die 8 behoort, so as die linker kind van 9 nege -> left_child = agt;

661
00:53:10,790 --> 00:53:22,190
en dan 2 is die linker kind van 3, sodat ons dit kan doen hier - jou -> left_child = twee;.

662
00:53:22,190 --> 00:53:27,730
As jy nie heeltemal volg nie saam met wat, ek stel voor jy trek dit uit jouself.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Kom ons behalwe hierdie. Kom ons gaan uit en maak seker dit stel,

664
00:53:35,660 --> 00:53:40,760
en dan kan ons voeg in ons bevat oproepe.

665
00:53:40,760 --> 00:53:44,120
Dit lyk asof alles nog stel.

666
00:53:44,120 --> 00:53:51,790
Laat in gaan en voeg in sommige bevat oproepe.

667
00:53:51,790 --> 00:53:59,640
Weereens, ek gaan 'n bietjie van kopieer en plak te doen.

668
00:53:59,640 --> 00:54:15,860
Laat ons nou soek vir 5, 8 en 2. Alright.

669
00:54:15,860 --> 00:54:28,330
Kom ons maak seker dat dit alles goed lyk nog steeds. Great! Stoor en sluit.

670
00:54:28,330 --> 00:54:33,220
Nou laat ons saam te stel, en nou laat loop.

671
00:54:33,220 --> 00:54:37,540
Uit die resultate, dit lyk asof alles werk net mooi en goed.

672
00:54:37,540 --> 00:54:41,780
Great! So nou het ons ons bevat funksie geskryf.

673
00:54:41,780 --> 00:54:46,160
Kom ons beweeg op en begin werk oor hoe om nodusse in die boom te voeg

674
00:54:46,160 --> 00:54:50,000
want soos ons doen dit nou, dinge is nie baie mooi.

675
00:54:50,000 --> 00:54:52,280
>> As ons terug gaan na die spesifikasie,

676
00:54:52,280 --> 00:55:00,540
dit ons vra om te skryf van 'n funksie met die naam plaas - weer, die terugkeer van 'n Bool

677
00:55:00,540 --> 00:55:04,400
of ons kan eintlik voeg die nodus in die boom -

678
00:55:04,400 --> 00:55:07,710
en dan die waarde toe te voeg in die boom word gespesifiseer as

679
00:55:07,710 --> 00:55:11,060
die enigste argument aan ons insert funksie.

680
00:55:11,060 --> 00:55:18,180
Ons sal terugkeer waar as ons inderdaad die node wat waarde kan voeg in die boom,

681
00:55:18,180 --> 00:55:20,930
wat beteken dat ons, een, genoeg geheue gehad het,

682
00:55:20,930 --> 00:55:24,840
en dan twee, het daardie node nie reeds bestaan ​​in die boom sedert -

683
00:55:24,840 --> 00:55:32,170
Onthou, ons gaan nie duplikaat waardes te hê in die boom, net om dinge eenvoudig.

684
00:55:32,170 --> 00:55:35,590
Alright. Terug na die kode.

685
00:55:35,590 --> 00:55:44,240
Oop te maak. Zoom in 'n bietjie, dan scroll down.

686
00:55:44,240 --> 00:55:47,220
Kom ons stel die insetsel funksie regs bo die bevat.

687
00:55:47,220 --> 00:55:56,360
Weereens, gaan dit genoem te word nie die Bool insert (int waarde).

688
00:55:56,360 --> 00:56:01,840
Gee dit 'n bietjie meer ruimte, en dan as 'n standaard,

689
00:56:01,840 --> 00:56:08,870
laat ons in ruil vals is heel aan die einde.

690
00:56:08,870 --> 00:56:22,620
Nou af aan die onderkant, laat ons gaan voort en in plaas van die hand die bou van die nodusse

691
00:56:22,620 --> 00:56:27,900
in die hoof onsself en bedrading hulle te wys aan mekaar soos ons dit doen,

692
00:56:27,900 --> 00:56:30,600
sal ons staatmaak op ons insert funksie om dit te doen.

693
00:56:30,600 --> 00:56:35,510
Ons sal ons nie op ons insert funksie net nog die hele boom van nuuts af te bou,

694
00:56:35,510 --> 00:56:39,970
maar eerder sal ons ontslae te raak van hierdie lyne - sal ons kommentaar uit hierdie lyne -

695
00:56:39,970 --> 00:56:43,430
wat bou die nodes 5, 8 en 2.

696
00:56:43,430 --> 00:56:55,740
En in plaas daarvan, sal ons voeg oproepe na ons insert funksie

697
00:56:55,740 --> 00:57:01,280
om seker te maak dat dit eintlik werk.

698
00:57:01,280 --> 00:57:05,840
Hier gaan ons.

699
00:57:05,840 --> 00:57:09,300
>> Nou het ons gedraai uit hierdie lyne.

700
00:57:09,300 --> 00:57:13,700
Ons het net 7, 3, 9, en 6 in ons boom op hierdie punt.

701
00:57:13,700 --> 00:57:18,870
Om seker te maak dat dit alles werk,

702
00:57:18,870 --> 00:57:25,050
ons kan uitzoomen, maak ons ​​binêre boom,

703
00:57:25,050 --> 00:57:30,750
loop dit, en ons kan sien wat die volgende bevat, is nou om ons te vertel dat ons is heeltemal reg -

704
00:57:30,750 --> 00:57:33,110
5, 8 en 2 is nie meer in die boom.

705
00:57:33,110 --> 00:57:37,960
Gaan terug in die kode,

706
00:57:37,960 --> 00:57:41,070
en hoe gaan ons te voeg?

707
00:57:41,070 --> 00:57:46,290
Onthou wat ons gedoen het toe ons eintlik 5 invoeging, 8 en 2 voorheen.

708
00:57:46,290 --> 00:57:50,100
Ons dat Plinko spel gespeel waar ons begin by die wortel,

709
00:57:50,100 --> 00:57:52,780
het die boom af een deur een vir een

710
00:57:52,780 --> 00:57:54,980
totdat ons die toepaslike gaping gevind het,

711
00:57:54,980 --> 00:57:57,570
en dan het ons bedraad in die knoop by die toepaslike plek.

712
00:57:57,570 --> 00:57:59,480
Ons gaan dieselfde ding om te doen.

713
00:57:59,480 --> 00:58:04,070
Dit is basies soos die skryf van die kode wat ons gebruik in die bevat 'n funksie

714
00:58:04,070 --> 00:58:05,910
die plek waar die knoop moet wees om te vind,

715
00:58:05,910 --> 00:58:10,560
en dan is ons net gaan om die knoop reg daar te voeg.

716
00:58:10,560 --> 00:58:17,000
Kom ons begin om dit te doen.

717
00:58:17,000 --> 00:58:24,200
>> So ons het 'n node * huidig ​​= wortel, ons is net gaan om te volg die bevat kode

718
00:58:24,200 --> 00:58:26,850
totdat ons vind dat dit nie heeltemal vir ons werk.

719
00:58:26,850 --> 00:58:32,390
Ons gaan om te gaan deur middel van die boom, terwyl die huidige element is nie null,

720
00:58:32,390 --> 00:58:45,280
en as ons vind dat die huidige se waarde is gelyk aan die waarde wat ons probeer om te steek -

721
00:58:45,280 --> 00:58:49,600
Wel, dit is een van die gevalle wat ons kan eintlik nie die node voeg

722
00:58:49,600 --> 00:58:52,730
in die boom, want dit beteken dat ons het 'n duplikaat waarde.

723
00:58:52,730 --> 00:58:59,010
Hier is ons eintlik gaan om terug te keer vals.

724
00:58:59,010 --> 00:59:08,440
Nou, anders as huidig ​​se waarde is minder as die waarde

725
00:59:08,440 --> 00:59:10,930
nou weet ons dat ons na regs beweeg

726
00:59:10,930 --> 00:59:17,190
 omdat die waarde behoort in die regter helfte van die huidige boom.

727
00:59:17,190 --> 00:59:30,110
Anders gaan ons om te beweeg na links.

728
00:59:30,110 --> 00:59:37,980
Dit is basies ons bevat funksioneer reg daar.

729
00:59:37,980 --> 00:59:41,820
>> Op hierdie punt, wanneer het ons hierdie while lus voltooi,

730
00:59:41,820 --> 00:59:47,350
ons huidige wyser gaan word verwys na nul

731
00:59:47,350 --> 00:59:51,540
indien die funksie reeds nie terug nie.

732
00:59:51,540 --> 00:59:58,710
Ons is dus met huidig ​​op die plek waar ons wil die nuwe node in te voeg.

733
00:59:58,710 --> 01:00:05,210
Wat nog gedoen moet word, is om werklik die bou van die nuwe node,

734
01:00:05,210 --> 01:00:08,480
wat ons kan redelik maklik te doen.

735
01:00:08,480 --> 01:00:14,930
Ons kan gebruik maak van ons super-handig build node funksie,

736
01:00:14,930 --> 01:00:17,210
en iets wat ons nie vroeër doen -

737
01:00:17,210 --> 01:00:21,400
ons het net soort van as vanselfsprekend aanvaar, maar nou gaan ons doen net om seker te maak -

738
01:00:21,400 --> 01:00:27,130
ons sal toets om seker te maak dat die waarde wat deur die nuwe node was eintlik

739
01:00:27,130 --> 01:00:33,410
nie null, want ons wil nie om te begin met die toegang tot hierdie geheue as dit is van nul.

740
01:00:33,410 --> 01:00:39,910
Ons kan toets om seker te maak dat die nuwe node is nie gelyk aan nul.

741
01:00:39,910 --> 01:00:42,910
Of in plaas, kan ons net kyk of dit regtig is van nul,

742
01:00:42,910 --> 01:00:52,120
en as dit is van nul is, dan kan ons net return false vroeg.

743
01:00:52,120 --> 01:00:59,090
>> Op hierdie punt, ons het nuwe node in sy toepaslike plek in die boom te bedraad.

744
01:00:59,090 --> 01:01:03,510
As ons terug kyk by die hoof en waar ons was eintlik bedrading in waardes voor,

745
01:01:03,510 --> 01:01:08,470
sien ons dat die manier waarop ons dit doen wanneer ons wou 3 in die boom te sit

746
01:01:08,470 --> 01:01:11,750
is ons toegang tot die linker kind van die wortel.

747
01:01:11,750 --> 01:01:14,920
Wanneer ons 9 in die boom, het ons 'die regte kind van die wortel gehad het om toegang te verkry tot.

748
01:01:14,920 --> 01:01:21,030
Ons het 'n wyser na die ouer te hê ten einde 'n nuwe waarde in die boom te sit.

749
01:01:21,030 --> 01:01:24,430
Blaai terug te voeg, wat nie gaan baie werk hier

750
01:01:24,430 --> 01:01:27,550
want ons het nie 'n ouer wyser.

751
01:01:27,550 --> 01:01:31,650
Wat ons wil hê om in staat wees om dit te doen, op hierdie punt,

752
01:01:31,650 --> 01:01:37,080
die ouer se waarde nagaan en sien - goed, gosh,

753
01:01:37,080 --> 01:01:41,990
indien die ouer se waarde is minder as die huidige waarde,

754
01:01:41,990 --> 01:01:54,440
dan is die ouer se reg kind moet die nuwe node;

755
01:01:54,440 --> 01:02:07,280
andersins, moet die ouer se links kind die nuwe nodus.

756
01:02:07,280 --> 01:02:10,290
Maar, ons het nie hierdie ouer wyser baie nog.

757
01:02:10,290 --> 01:02:15,010
>> Ten einde dit te kry, ons eintlik gaan om dit op te spoor as ons gaan deur middel van die boom

758
01:02:15,010 --> 01:02:18,440
en vind die toepaslike plek in ons lus hierbo.

759
01:02:18,440 --> 01:02:26,840
Ons kan dit doen deur te blaai terug na die top van ons insert funksie

760
01:02:26,840 --> 01:02:32,350
en die dop van 'n ander wyser veranderlike genoem die ouer.

761
01:02:32,350 --> 01:02:39,340
Ons gaan dit op gelyke aanvanklik ingestel op nul,

762
01:02:39,340 --> 01:02:43,640
en dan elke keer as ons gaan deur middel van die boom,

763
01:02:43,640 --> 01:02:51,540
ons gaan die ouer wyser te stel om die huidige wyser aan te pas.

764
01:02:51,540 --> 01:02:59,140
Stel ouer gelyk aan huidige.

765
01:02:59,140 --> 01:03:02,260
Op hierdie manier, elke keer wat ons gaan deur,

766
01:03:02,260 --> 01:03:05,550
ons gaan om te verseker dat as die huidige wyser kry geïnkrementeer

767
01:03:05,550 --> 01:03:12,640
die ouer wyser volg dit - net een vlak hoër as die huidige wyser in die boom.

768
01:03:12,640 --> 01:03:17,370
Dat al lyk redelik goed.

769
01:03:17,370 --> 01:03:22,380
>> Ek dink die een ding wat ons sal wil hê om aan te pas is dit bou node terugkeer null.

770
01:03:22,380 --> 01:03:25,380
In orde te kry bou node om werklik suksesvol null terugkeer,

771
01:03:25,380 --> 01:03:31,060
ons sal hê om die kode te verander,

772
01:03:31,060 --> 01:03:37,270
want hier het ons nooit getoets om seker te maak dat malloc 'n geldige wyser teruggekeer.

773
01:03:37,270 --> 01:03:53,390
So, as (n = NULL), dan

774
01:03:53,390 --> 01:03:55,250
indien malloc 'n geldige wyser terug, dan sal ons inisialiseer;

775
01:03:55,250 --> 01:04:02,540
andersins, sal ons net teruggaan en dit sal uiteindelik terugkeer null vir ons.

776
01:04:02,540 --> 01:04:13,050
Nou al lyk redelik goed. Kom ons maak seker dat dit eintlik stel.

777
01:04:13,050 --> 01:04:22,240
Maak binêre boom, en oh, ons het 'n paar dinge wat hier aangaan nie.

778
01:04:22,240 --> 01:04:29,230
>> Ons het 'n implisiete verklaring van funksie bou node.

779
01:04:29,230 --> 01:04:31,950
Weer, met hierdie samestellers, ons gaan om te begin aan die bokant.

780
01:04:31,950 --> 01:04:36,380
Wat dit moet beteken, is dat ek 'n beroep bou node voordat ek dit werklik verklaar.

781
01:04:36,380 --> 01:04:37,730
Kom ons gaan terug na die kode regtig vinnig.

782
01:04:37,730 --> 01:04:43,510
Scroll down, en seker genoeg, my insert funksie verklaar

783
01:04:43,510 --> 01:04:47,400
bo die bou node funksie,

784
01:04:47,400 --> 01:04:50,070
maar ek probeer om te gebruik node bou binnekant van insert.

785
01:04:50,070 --> 01:05:06,610
Ek gaan om te gaan in en kopieer en plak die bou node funksie pad tot hier aan die bokant.

786
01:05:06,610 --> 01:05:11,750
Op dié manier, hopelik wat sal werk. Kom ons gee dit 'n ander gaan.

787
01:05:11,750 --> 01:05:18,920
Nou is dit almal stel. Alles is goed.

788
01:05:18,920 --> 01:05:21,640
>> Maar op hierdie punt, het ons nie eintlik ons ​​insert funksie genoem.

789
01:05:21,640 --> 01:05:26,510
Ons weet net dat dit stel, so laat in gaan en sit n paar oproepe.

790
01:05:26,510 --> 01:05:28,240
Kom ons doen dit in ons belangrikste funksie.

791
01:05:28,240 --> 01:05:32,390
Hier, het ons opgemerk 5, 8 en 2,

792
01:05:32,390 --> 01:05:36,680
en dan het ons nie bedraad hulle hier neer.

793
01:05:36,680 --> 01:05:41,640
Kom ons maak 'n paar oproepe te voeg,

794
01:05:41,640 --> 01:05:46,440
en laat ons ook gebruik maak van die dieselfde soort van dinge wat ons gebruik

795
01:05:46,440 --> 01:05:52,810
wanneer ons hierdie printf oproepe gemaak om seker te maak dat alles het behoorlik te plaas.

796
01:05:52,810 --> 01:06:00,550
Ek gaan om te kopieer en plak,

797
01:06:00,550 --> 01:06:12,450
en in plaas van bevat ons gaan insetsel te doen.

798
01:06:12,450 --> 01:06:30,140
En in plaas van 6, 10 en 1, gaan ons 5, 8 en 2 te gebruik.

799
01:06:30,140 --> 01:06:37,320
Dit behoort hopelik voeg 5, 8 en 2 in die boom.

800
01:06:37,320 --> 01:06:44,050
Stel. Alles is goed. Nou het ons ons program sal eintlik loop.

801
01:06:44,050 --> 01:06:47,330
>> Alles teruggekeer vals.

802
01:06:47,330 --> 01:06:53,830
So, 5, 8 en 2 gaan nie, en dit lyk asof bevat het hulle nie vind nie óf.

803
01:06:53,830 --> 01:06:58,890
What's going on? Kom ons uitzoomen.

804
01:06:58,890 --> 01:07:02,160
Die eerste probleem was dat insetsel was om terug te keer vals,

805
01:07:02,160 --> 01:07:08,750
en dit lyk soos dit is, want ons het in ons terugkeer vals oproep,

806
01:07:08,750 --> 01:07:14,590
en ons het nooit werklik teruggekeer waar.

807
01:07:14,590 --> 01:07:17,880
Ons kan dit op.

808
01:07:17,880 --> 01:07:25,290
Die tweede probleem is nou selfs as ons dit doen - Hou hierdie, stop hierdie,

809
01:07:25,290 --> 01:07:34,530
hardloop maak weer, stel dit het, dan loop dit -

810
01:07:34,530 --> 01:07:37,670
sien ons dat daar iets anders hier gebeur.

811
01:07:37,670 --> 01:07:42,980
Die 5, 8 en 2 was nog nooit gevind in die boom.

812
01:07:42,980 --> 01:07:44,350
So, wat gaan aan?

813
01:07:44,350 --> 01:07:45,700
>> Kom ons neem 'n blik op hierdie in die kode.

814
01:07:45,700 --> 01:07:49,790
Kom ons kyk of ons kan dit uit figuur.

815
01:07:49,790 --> 01:07:57,940
Ons begin met die ouer nie null.

816
01:07:57,940 --> 01:07:59,510
Ons stel die huidige wyser gelyk aan die wortel pointer,

817
01:07:59,510 --> 01:08:04,280
en ons gaan ons manier om te werk deur middel van die boom af.

818
01:08:04,280 --> 01:08:08,650
Indien die huidige Nodus nie NULL is, dan weet ons dat ons kan beweeg 'n bietjie af.

819
01:08:08,650 --> 01:08:12,330
Ons stel ons ouer wyser te wees gelyk aan die huidige wyser,

820
01:08:12,330 --> 01:08:15,420
kyk na die waarde - as die dieselfde waardes belangrik is ons terug vals.

821
01:08:15,420 --> 01:08:17,540
Indien die waardes is minder het ons verhuis na regs;

822
01:08:17,540 --> 01:08:20,399
andersins, het ons verhuis na links.

823
01:08:20,399 --> 01:08:24,220
Dan sal ons die bou van 'n node. Ek sal zoom in 'n bietjie.

824
01:08:24,220 --> 01:08:31,410
En hier, ons gaan om te probeer om te bedraad die waardes dieselfde wees.

825
01:08:31,410 --> 01:08:37,250
What's going on? Kom ons kyk indien moontlik Valgrind kan gee vir ons 'n wenk.

826
01:08:37,250 --> 01:08:43,910
>> Ek hou van Valgrind te gebruik net omdat regtig vinnig Valgrind lopies

827
01:08:43,910 --> 01:08:46,729
en vir jou vertel as daar 'n geheue foute.

828
01:08:46,729 --> 01:08:48,300
Wanneer ons loop Valgrind op die kode,

829
01:08:48,300 --> 01:08:55,859
soos jy kan sien reg here--Valgrind./binary_tree--and druk enter.

830
01:08:55,859 --> 01:09:03,640
Jy sien dat ons nie 'n geheue fout, sodat dit lyk asof alles is goed so ver.

831
01:09:03,640 --> 01:09:07,529
Ons doen 'n paar geheue lekkasies, wat ons weet, want ons is nie

832
01:09:07,529 --> 01:09:08,910
gebeur enige van ons nodes te bevry.

833
01:09:08,910 --> 01:09:13,050
Kom ons probeer om GDB om te sien wat werklik aangaan.

834
01:09:13,050 --> 01:09:20,010
Ons sal doen gdb / binary_tree. Dit geselflaai net 'n boete.

835
01:09:20,010 --> 01:09:23,670
Kom ons stel 'n breek punt op die insetsel.

836
01:09:23,670 --> 01:09:28,600
Kom ons loop.

837
01:09:28,600 --> 01:09:31,200
Dit lyk soos ons nog nooit eintlik genoem insetsel.

838
01:09:31,200 --> 01:09:39,410
Dit lyk soos die probleem was net dat wanneer ek verander hier in hoof -

839
01:09:39,410 --> 01:09:44,279
al van hierdie printf oproepe van bevat -

840
01:09:44,279 --> 01:09:56,430
Ek het nooit werklik verander hierdie insetsel te roep.

841
01:09:56,430 --> 01:10:01,660
Nou laat ons gee dit 'n probeer. Kom ons stel.

842
01:10:01,660 --> 01:10:09,130
Alles lyk goed daar. Laat ons nou probeer om dit te draai, kyk wat gebeur.

843
01:10:09,130 --> 01:10:13,320
Alright! Alles lyk redelik goed daar.

844
01:10:13,320 --> 01:10:18,130
>> Die laaste ding om oor te dink is, is daar 'n rand gevalle tot hierdie insetsel?

845
01:10:18,130 --> 01:10:23,170
En dit blyk dat, wel, die een kant geval dit is altyd interessant om te dink oor

846
01:10:23,170 --> 01:10:26,250
is, wat gebeur as jou boom is leeg en jy noem dit insert funksie?

847
01:10:26,250 --> 01:10:30,330
Sal dit werk? Wel, laat ons gee dit 'n probeer.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c.

849
01:10:32,110 --> 01:10:35,810
Die manier waarop ons gaan om dit te toets, ons gaan om te gaan na ons hooffunksie,

850
01:10:35,810 --> 01:10:41,690
en eerder as bedrading hierdie nodes soos hierdie,

851
01:10:41,690 --> 01:10:56,730
ons is maar net gaan om kommentaar te lewer uit die hele ding,

852
01:10:56,730 --> 01:11:02,620
en in plaas van die bedrading op die nodes onsself,

853
01:11:02,620 --> 01:11:09,400
Ons kan eintlik net voort te gaan en verwyder al hierdie dinge.

854
01:11:09,400 --> 01:11:17,560
Ons gaan alles 'n oproep te voeg.

855
01:11:17,560 --> 01:11:49,020
So, laat ons doen - in plaas van 5, 8 en 2, ons gaan 7 in te voeg, 3 en 9.

856
01:11:49,020 --> 01:11:58,440
En dan sal ons ook wil 6 om so goed te voeg.

857
01:11:58,440 --> 01:12:05,190
Red. Afsluit. Maak binêre boom.

858
01:12:05,190 --> 01:12:08,540
Dit stel al nie.

859
01:12:08,540 --> 01:12:10,320
Ons kan nie net loop dit en kyk wat gebeur,

860
01:12:10,320 --> 01:12:12,770
maar dit is ook werklik belangrik gaan wees om seker te maak dat

861
01:12:12,770 --> 01:12:14,740
ons het nie 'n geheue foute,

862
01:12:14,740 --> 01:12:16,840
want dit is een van ons rand gevalle wat ons weet.

863
01:12:16,840 --> 01:12:20,150
>> Kom ons maak seker dat dit goed werk onder Valgrind,

864
01:12:20,150 --> 01:12:28,310
wat ons sal doen deur net loop Valgrind / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Dit lyk of ons inderdaad een fout van een konteks -

866
01:12:31,110 --> 01:12:33,790
ons het hierdie segmentering skuld.

867
01:12:33,790 --> 01:12:36,690
Wat het gebeur?

868
01:12:36,690 --> 01:12:41,650
Valgrind vertel ons waar dit is.

869
01:12:41,650 --> 01:12:43,050
Zoem uit 'n bietjie.

870
01:12:43,050 --> 01:12:46,040
Dit lyk soos dit gebeur in ons insert funksie,

871
01:12:46,040 --> 01:12:53,420
waar ons het 'n ongeldige lees van grootte 4 insert line 60.

872
01:12:53,420 --> 01:13:03,590
Kom ons gaan terug en kyk wat gaan hier aan.

873
01:13:03,590 --> 01:13:05,350
Zoem uit regtig vinnig.

874
01:13:05,350 --> 01:13:14,230
Ek wil om seker te maak dat dit nie gaan na die rand van die skerm, sodat ons alles kan sien.

875
01:13:14,230 --> 01:13:18,760
Trek wat in 'n bietjie. Alright.

876
01:13:18,760 --> 01:13:35,030
Scroll down, en die probleem is reg hier.

877
01:13:35,030 --> 01:13:40,120
Wat gebeur as ons af en ons huidige node is reeds null,

878
01:13:40,120 --> 01:13:44,010
ons voorgangernode null, so as ons kyk op na die heel boonste, reg hier -

879
01:13:44,010 --> 01:13:47,340
indien hierdie while lus nooit voer eintlik

880
01:13:47,340 --> 01:13:52,330
omdat ons huidige waarde null - ons wortel null, sodat die huidige is null

881
01:13:52,330 --> 01:13:57,810
dan is ons ouer nooit kry ingestel op die huidige of 'n geldige waarde,

882
01:13:57,810 --> 01:14:00,580
so, ouer sal ook null.

883
01:14:00,580 --> 01:14:03,700
Ons moet onthou om te kyk vir

884
01:14:03,700 --> 01:14:08,750
teen die tyd kry ons hier af, en ons begin met die toegang tot die ouer se waarde.

885
01:14:08,750 --> 01:14:13,190
So, wat gebeur? Wel, as die ouer is van nul -

886
01:14:13,190 --> 01:14:17,990
if (ouer == null) - dan weet ons dat

887
01:14:17,990 --> 01:14:19,530
moet daar nie iets in die boom.

888
01:14:19,530 --> 01:14:22,030
Ons moet probeer om dit te voeg by die wortel.

889
01:14:22,030 --> 01:14:32,570
Ons kan dit doen deur net die opstel van die wortel gelyk aan die nuwe node.

890
01:14:32,570 --> 01:14:40,010
Toe, op hierdie punt, het ons nie eintlik wil hê om te gaan deur middel van hierdie ander dinge.

891
01:14:40,010 --> 01:14:44,780
In plaas daarvan, reg hier, kan ons doen, hetsy 'n anders-as-anders,

892
01:14:44,780 --> 01:14:47,610
of ons kan kombineer alles hier in 'n ander,

893
01:14:47,610 --> 01:14:56,300
maar hier het ons sal net anders gebruik en dit doen.

894
01:14:56,300 --> 01:14:59,030
Nou gaan ons om te toets om seker te maak dat ons ouer nie, is van nul

895
01:14:59,030 --> 01:15:02,160
voor dan eintlik probeer om sy buiteveld om toegang te verkry tot.

896
01:15:02,160 --> 01:15:05,330
Dit sal ons help vermy die segmentering skuld.

897
01:15:05,330 --> 01:15:14,740
So, ons ophou, uitzoomen, stel, hardloop.

898
01:15:14,740 --> 01:15:18,130
>> Geen foute, maar ons het nog 'n klomp van die geheue lekkasies

899
01:15:18,130 --> 01:15:20,650
omdat ons nie vry om enige van ons nodes.

900
01:15:20,650 --> 01:15:24,350
, Maar as ons gaan hier en ons kyk na ons uitdruk,

901
01:15:24,350 --> 01:15:30,880
sien ons dat, wel, lyk soos almal van ons inserts terugkeer waar is, wat goed is.

902
01:15:30,880 --> 01:15:33,050
Die insetsels is alles waar,

903
01:15:33,050 --> 01:15:36,670
en dan die toepaslike bevat oproepe is ook waar.

904
01:15:36,670 --> 01:15:41,510
>> Goeie werk! Dit lyk soos ons het suksesvol insert geskryf.

905
01:15:41,510 --> 01:15:47,430
Dit is al wat ons het vir hierdie week se Problem Set spesifikasie.

906
01:15:47,430 --> 01:15:51,720
Een pret uitdaging om oor na te dink, is hoe jy regtig sou gaan

907
01:15:51,720 --> 01:15:55,340
en vry al die nodes in hierdie boom.

908
01:15:55,340 --> 01:15:58,830
Ons kan 'n aantal verskillende maniere om dit te doen,

909
01:15:58,830 --> 01:16:01,930
maar ek sal laat dat aan jou om te eksperimenteer,

910
01:16:01,930 --> 01:16:06,080
en as 'n prettige uitdaging, probeer en maak seker dat jy kan seker maak

911
01:16:06,080 --> 01:16:09,490
dat hierdie Valgrind verslag gee geen foute en geen lekkasies.

912
01:16:09,490 --> 01:16:12,880
>> Sterkte op hierdie week se Huffman kodering probleem stel,

913
01:16:12,880 --> 01:16:14,380
en ons sien julle volgende week!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]