1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Afsnit 7] [mindre behagelig]

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

3
00:00:04,890 --> 00:00:07,000
[Dette er CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Velkommen til § 7.

5
00:00:09,080 --> 00:00:11,330
Takket være orkanen Sandy,

6
00:00:11,330 --> 00:00:13,440
stedet for at have en normal afsnit denne uge,

7
00:00:13,440 --> 00:00:17,650
vi gør dette walk-through, gennem den del af spørgsmålene.

8
00:00:17,650 --> 00:00:22,830
Jeg har tænkt mig at være efter sammen med det Problem Set 6 Specifikation

9
00:00:22,830 --> 00:00:25,650
og går gennem alle spørgsmålene i

10
00:00:25,650 --> 00:00:27,770
En sektion af spørgsmål sektion.

11
00:00:27,770 --> 00:00:30,940
Hvis der er nogen spørgsmål,

12
00:00:30,940 --> 00:00:32,960
bedes du sende disse på CS50 diskutere.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Lad os komme i gang.

14
00:00:35,480 --> 00:00:40,780
Lige nu er jeg kigger på side 3 i Problem Set Specification.

15
00:00:40,780 --> 00:00:44,110
Vi vil først begynde at tale om binære træer

16
00:00:44,110 --> 00:00:47,850
eftersom de har en masse relevans for denne uges problem sæt -

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

18
00:00:49,950 --> 00:00:55,000
En af de allerførste datastrukturer vi talte om på CS50 var array.

19
00:00:55,000 --> 00:01:00,170
Husk, at et array er en sekvens af elementer -

20
00:01:00,170 --> 00:01:04,019
alle af samme type - lagret lige ved siden af ​​hinanden i hukommelsen.

21
00:01:04,019 --> 00:01:14,420
Hvis jeg har et heltal array, jeg kan tegne ved hjælp af denne æsker-numre-heltal stil -

22
00:01:14,420 --> 00:01:20,290
Lad os sige, at jeg har 5 i den første boks, jeg har 7 i den anden,

23
00:01:20,290 --> 00:01:27,760
så har jeg 8, 10 og 20 i den sidste boks.

24
00:01:27,760 --> 00:01:33,000
Husk, at to virkelig gode ting om dette array

25
00:01:33,000 --> 00:01:38,800
er, at vi har denne konstant-time adgang til nogen bestemt element

26
00:01:38,800 --> 00:01:40,500
 i array, hvis vi kender dens indeks.

27
00:01:40,500 --> 00:01:44,670
For eksempel, hvis jeg ønsker at få fat det tredje element i array -

28
00:01:44,670 --> 00:01:47,870
på indeks 2 ved hjælp af vores nul-baseret indeksering system -

29
00:01:47,870 --> 00:01:52,220
Jeg bogstaveligt talt bare nødt til at gøre en simpel matematisk beregning,

30
00:01:52,220 --> 00:01:56,170
hop til denne position i sættet,

31
00:01:56,170 --> 00:01:57,840
trække de 8, der er gemt der,

32
00:01:57,840 --> 00:01:59,260
og jeg er god til at gå.

33
00:01:59,260 --> 00:02:03,350
>> En af de dårlige ting om dette array - som vi talte om

34
00:02:03,350 --> 00:02:05,010
da vi diskuterede hægtede lister -

35
00:02:05,010 --> 00:02:09,120
er, at hvis jeg ønsker at indsætte et element i denne array,

36
00:02:09,120 --> 00:02:11,090
Jeg har tænkt mig at have at gøre nogle flytte rundt.

37
00:02:11,090 --> 00:02:12,940
For eksempel, array denne ret her

38
00:02:12,940 --> 00:02:16,850
er i sorteret orden - sorteret i stigende rækkefølge -

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

40
00:02:19,440 --> 00:02:23,100
men hvis jeg ønsker at indsætte nummer 9 i denne array,

41
00:02:23,100 --> 00:02:27,460
Jeg har tænkt mig at skulle flytte nogle af de elementer, for at gøre plads.

42
00:02:27,460 --> 00:02:30,440
Vi kan trække dette ud her.

43
00:02:30,440 --> 00:02:35,650
Jeg har tænkt mig at skulle flytte 5, 7, og derefter 8;

44
00:02:35,650 --> 00:02:38,720
skabe et hul, hvor jeg kan sætte 9,

45
00:02:38,720 --> 00:02:45,910
og derefter 10 og 20 kan gå til højre for 9.

46
00:02:45,910 --> 00:02:49,450
Det er lidt af en smerte, fordi i det værst tænkelige scenario -

47
00:02:49,450 --> 00:02:54,350
når vi skulle indsætte enten i begyndelsen eller slutningen

48
00:02:54,350 --> 00:02:56,040
af arrayet, vi afhængigt af hvordan er forskydning -

49
00:02:56,040 --> 00:02:58,850
vi kan ende med at skulle flytte alle de elementer

50
00:02:58,850 --> 00:03:00,750
at vi i øjeblikket er lagring i array.

51
00:03:00,750 --> 00:03:03,810
>> Så hvad var den måde omkring dette?

52
00:03:03,810 --> 00:03:09,260
Den måde omkring dette var at gå til vores linkede-list metode, hvor -

53
00:03:09,260 --> 00:03:19,820
stedet for at lagre de elementer 5, 7, 8, 10 og 20 alle ved siden af ​​hinanden i hukommelsen -

54
00:03:19,820 --> 00:03:25,630
hvad vi i stedet gjorde var gemme dem slags overalt, hvor vi ønskede at gemme dem

55
00:03:25,630 --> 00:03:32,470
i disse sammenkædede-liste noder, som jeg trækker ud her, slags ad hoc.

56
00:03:32,470 --> 00:03:42,060
Og så har vi forbandt dem sammen ved hjælp af disse næste pointers.

57
00:03:42,060 --> 00:03:44,370
Jeg kan have en pointer fra 5 til 7,

58
00:03:44,370 --> 00:03:46,420
en pointer fra 7 til 8,

59
00:03:46,420 --> 00:03:47,770
en pointer fra 8 til 10,

60
00:03:47,770 --> 00:03:51,220
og endelig en pointer fra 10 til 20,

61
00:03:51,220 --> 00:03:54,880
og derefter en null-pointer på 20 angiver, at der ikke er noget til venstre.

62
00:03:54,880 --> 00:03:59,690
Det trade-off, vi har her

63
00:03:59,690 --> 00:04:05,360
er, at nu, hvis vi ønsker at indsætte nummer 9 i vores sorteret liste,

64
00:04:05,360 --> 00:04:08,270
alt, hvad vi skal gøre, er at oprette en ny node med 9,

65
00:04:08,270 --> 00:04:12,290
wire det op til at pege på det relevante sted,

66
00:04:12,290 --> 00:04:20,630
og derefter re-wire på 8 til at pege ned til 9.

67
00:04:20,630 --> 00:04:25,660
Det er temmelig hurtigt, antager vi ved præcis, hvor vi ønsker at indsætte 9.

68
00:04:25,660 --> 00:04:32,610
Men trade-off i bytte for dette er, at vi nu har mistet den konstante-time adgang

69
00:04:32,610 --> 00:04:36,230
til nogen særlig del af vores datastruktur.

70
00:04:36,230 --> 00:04:40,950
For eksempel, hvis jeg ønsker at finde den fjerde element i denne linkede liste

71
00:04:40,950 --> 00:04:43,510
Jeg har tænkt mig at skulle starte ved begyndelsen af ​​listen

72
00:04:43,510 --> 00:04:48,930
og arbejde mig igennem tælle node-by-node, indtil jeg finder den fjerde.

73
00:04:48,930 --> 00:04:55,870
>> For at få bedre adgang ydeevne end en sammenkædet liste -

74
00:04:55,870 --> 00:04:59,360
men også bevarer nogle af de fordele, som vi havde

75
00:04:59,360 --> 00:05:01,800
i form af indsættelse-tid fra en sammenkædet liste -

76
00:05:01,800 --> 00:05:05,750
et binært træ vil være nødvendigt at bruge lidt mere hukommelse.

77
00:05:05,750 --> 00:05:11,460
Især i stedet for bare at have en pointer i et binært træ node -

78
00:05:11,460 --> 00:05:13,350
som den sammenkædede liste node gør -

79
00:05:13,350 --> 00:05:16,950
vi kommer til at tilføje endnu en pointer til den binære træknude.

80
00:05:16,950 --> 00:05:19,950
Snarere end blot at have en markør til den næste element,

81
00:05:19,950 --> 00:05:24,420
vi skal have en pointer til en venstre barn og en højre barn.

82
00:05:24,420 --> 00:05:26,560
>> Lad os tegne et billede at se, hvad der rent faktisk ser ud.

83
00:05:26,560 --> 00:05:31,350
Igen, jeg vil bruge disse kasser og pile.

84
00:05:31,350 --> 00:05:37,150
Et binært træ node vil starte med blot et enkelt kasse.

85
00:05:37,150 --> 00:05:40,940
Det kommer til at have en plads til den værdi,

86
00:05:40,940 --> 00:05:47,280
og så er det også kommer til at have en plads til venstre barn og højre barn.

87
00:05:47,280 --> 00:05:49,280
Jeg har tænkt mig at mærke dem her.

88
00:05:49,280 --> 00:05:57,560
Vi kommer til at have den venstre barn, og så vil vi have ret barn.

89
00:05:57,560 --> 00:05:59,920
Der er mange forskellige måder at gøre dette.

90
00:05:59,920 --> 00:06:02,050
Nogle gange for plads og bekvemmelighed,

91
00:06:02,050 --> 00:06:06,460
Jeg vil faktisk trække det ligesom jeg gør her på bunden

92
00:06:06,460 --> 00:06:10,910
hvor jeg har tænkt mig at få værdien i toppen,

93
00:06:10,910 --> 00:06:14,060
og derefter den højre barn på nederste højre,

94
00:06:14,060 --> 00:06:16,060
og venstre barn nederst til venstre.

95
00:06:16,060 --> 00:06:20,250
Går tilbage til denne øverste diagram

96
00:06:20,250 --> 00:06:22,560
Vi har værdien øverst,

97
00:06:22,560 --> 00:06:25,560
så har vi den venstre barn pointer, og så har vi ret-barn pointer.

98
00:06:25,560 --> 00:06:30,110
>> I Problem Set Specification,

99
00:06:30,110 --> 00:06:33,110
vi taler om at tegne en node, der har en værdi 7,

100
00:06:33,110 --> 00:06:39,750
og derefter en venstre-barn pointer, der er null, og en højre-barn pointer, der er null.

101
00:06:39,750 --> 00:06:46,040
Vi kan enten skrive kapital NULL i rummet for

102
00:06:46,040 --> 00:06:51,610
både venstre barn og højre barn, eller vi kan trække denne diagonal skråstreg

103
00:06:51,610 --> 00:06:53,750
gennem hver af kasserne for at angive, at det er null.

104
00:06:53,750 --> 00:06:57,560
Jeg har tænkt mig at gøre, at bare fordi det er nemmere.

105
00:06:57,560 --> 00:07:03,700
Hvad du ser her er to måder diagrambaseret en meget simpel binær træknude

106
00:07:03,700 --> 00:07:07,960
hvor vi har værdien 7 og null barn pointers.

107
00:07:07,960 --> 00:07:15,220
>> Den anden del af vores specifikation taler om, hvordan med hægtede lister -

108
00:07:15,220 --> 00:07:18,270
husk, havde vi kun at holde fast i den allerførste element i en liste

109
00:07:18,270 --> 00:07:20,270
at huske hele listen -

110
00:07:20,270 --> 00:07:26,140
og ligeledes med et binært træ, har vi kun at holde fast i en pegepind til træet

111
00:07:26,140 --> 00:07:31,120
for at opretholde kontrol over hele datastruktur.

112
00:07:31,120 --> 00:07:36,150
Denne særlige element i træet kaldes rodknuden i træet.

113
00:07:36,150 --> 00:07:43,360
For eksempel, hvis denne ene node - dette knudepunkt indeholder værdien 7

114
00:07:43,360 --> 00:07:45,500
med null venstre-og højre-barn pointers -

115
00:07:45,500 --> 00:07:47,360
var den eneste værdi i vores træ,

116
00:07:47,360 --> 00:07:50,390
så ville det være vores rodnoden.

117
00:07:50,390 --> 00:07:52,240
Det er begyndelsen af ​​vores træ.

118
00:07:52,240 --> 00:07:58,530
Vi kan se det lidt mere klart, når vi begynder at tilføje flere noder til vores træ.

119
00:07:58,530 --> 00:08:01,510
Lad mig trække op en ny side.

120
00:08:01,510 --> 00:08:05,000
>> Nu vil vi tegne et træ, der har 7 ved roden,

121
00:08:05,000 --> 00:08:10,920
og 3 indersiden af ​​venstre barn, og 9 indersiden af ​​højre barn.

122
00:08:10,920 --> 00:08:13,500
Igen, dette er ret simpelt.

123
00:08:13,500 --> 00:08:26,510
Vi har 7, tegne en node for 3, en node for 9,

124
00:08:26,510 --> 00:08:32,150
og jeg har tænkt mig at sætte venstre-barn pointer på 7 til at pege på det knudepunkt, der indeholder 3,

125
00:08:32,150 --> 00:08:37,850
og højre barnets pointer af knudepunktet indeholdende 7 til knudepunktet indeholdende 9.

126
00:08:37,850 --> 00:08:42,419
Nu behøver siden 3 og 9 ikke har nogen børn,

127
00:08:42,419 --> 00:08:48,500
vi kommer til at indstille alle deres barn pegepinde til at være null.

128
00:08:48,500 --> 00:08:56,060
Her roden af ​​vores træ svarer til knudepunktet indeholder tallet 7.

129
00:08:56,060 --> 00:09:02,440
Du kan se, at hvis vi alle har, er en pegepind til at roden node,

130
00:09:02,440 --> 00:09:07,330
vi kan så gå igennem vores træ og adgang til begge barn noder -

131
00:09:07,330 --> 00:09:10,630
både 3 og 9.

132
00:09:10,630 --> 00:09:14,820
Ingen grund til at opretholde henvisninger til hver enkelt node på træet.

133
00:09:14,820 --> 00:09:22,080
Alright. Nu vil vi tilføje en anden node til dette diagram.

134
00:09:22,080 --> 00:09:25,370
Vi vil tilføje en node indeholdende 6,

135
00:09:25,370 --> 00:09:34,140
og vi vil tilføje dette som højre barn af node indeholdende 3.

136
00:09:34,140 --> 00:09:41,850
For at gøre dette, vil jeg slette, at null-pointer i 3-node

137
00:09:41,850 --> 00:09:47,750
og wire det op til at pege på det knudepunkt indeholdende 6. Alright.

138
00:09:47,750 --> 00:09:53,800
>> På dette tidspunkt, lad os gå over en lille smule af terminologi.

139
00:09:53,800 --> 00:09:58,230
For at starte, årsagen til, at dette kaldes et binært træ i særdeleshed

140
00:09:58,230 --> 00:10:00,460
er, at det har to underordnede pointers.

141
00:10:00,460 --> 00:10:06,020
Der er andre typer af træer, der har flere børn pointers.

142
00:10:06,020 --> 00:10:10,930
Især gjorde du en 'prøve' i Problem Set 5.

143
00:10:10,930 --> 00:10:19,310
Du vil bemærke, at i denne prøve, du havde 27 forskellige henvisninger til forskellige børn -

144
00:10:19,310 --> 00:10:22,410
en for hver af de 26 bogstaver i det engelske alfabet,

145
00:10:22,410 --> 00:10:25,410
og derefter den 27. til apostrof -

146
00:10:25,410 --> 00:10:28,900
så, det er ligner en type træ.

147
00:10:28,900 --> 00:10:34,070
Men her, da det er binære, vi kun har to børn pointers.

148
00:10:34,070 --> 00:10:37,880
>> Ud over dette rod node, som vi talte om,

149
00:10:37,880 --> 00:10:41,470
vi har også været at smide omkring dette begreb 'barn'.

150
00:10:41,470 --> 00:10:44,470
Hvad betyder det for en knude at være et barn af en anden node?

151
00:10:44,470 --> 00:10:54,060
Det bogstaveligt betyder, at et barn node er et barn af en anden node

152
00:10:54,060 --> 00:10:58,760
hvis det andet knudepunkt har en af ​​underordnede pointers indstillet til at pege på det pågældende knudepunkt.

153
00:10:58,760 --> 00:11:01,230
For at sætte dette i mere konkrete termer,

154
00:11:01,230 --> 00:11:11,170
hvis 3 bliver peget på af en af ​​barnets pointers på 7, så 3 er et barn på 7.

155
00:11:11,170 --> 00:11:14,510
Hvis vi skulle finde ud af, hvad børnene på 7 er -

156
00:11:14,510 --> 00:11:18,510
godt, vi se, at 7 har en pointer til 3 og en pegepind til 9,

157
00:11:18,510 --> 00:11:22,190
så 9 og 3 er børn af 7.

158
00:11:22,190 --> 00:11:26,650
Ni har ingen børn, fordi dens barn pointers er null,

159
00:11:26,650 --> 00:11:30,940
og 3 har kun ét barn, 6.

160
00:11:30,940 --> 00:11:37,430
Seks har heller ingen børn, fordi begge sine pointers er null, som vi vil trække lige nu.

161
00:11:37,430 --> 00:11:45,010
>> Desuden har vi også tale om forældre til en bestemt node,

162
00:11:45,010 --> 00:11:51,100
og det er, som du ville forvente, det modsatte af dette barn beskrivelse.

163
00:11:51,100 --> 00:11:58,620
Hver node har kun én forælder - i stedet for to, som man kunne forvente med mennesker.

164
00:11:58,620 --> 00:12:03,390
For eksempel er moderselskab for 3 7.

165
00:12:03,390 --> 00:12:10,800
Den forælder af 9 er også 7, og forælder til 6 er 3. Ikke meget til det.

166
00:12:10,800 --> 00:12:15,720
Vi har også vilkår at snakke om bedsteforældre og børnebørn,

167
00:12:15,720 --> 00:12:18,210
og mere generelt taler vi om forfædrene

168
00:12:18,210 --> 00:12:20,960
og efterkommere af et bestemt knudepunkt.

169
00:12:20,960 --> 00:12:25,710
Den forfader til en knude - eller forfædre, snarere af en knude -

170
00:12:25,710 --> 00:12:32,730
er alle de knudepunkter, der ligger på vejen fra roden til det pågældende knudepunkt.

171
00:12:32,730 --> 00:12:36,640
For eksempel, hvis jeg ser på knudepunktet 6

172
00:12:36,640 --> 00:12:46,430
derefter forfædre vil være både 3 og 7.

173
00:12:46,430 --> 00:12:55,310
Forfædrene til 9, for eksempel, er - hvis jeg kigger på knudepunktet 9 -

174
00:12:55,310 --> 00:12:59,990
så stamfader til 9 er kun 7.

175
00:12:59,990 --> 00:13:01,940
Og efterkommere er præcis det modsatte.

176
00:13:01,940 --> 00:13:05,430
Hvis jeg ønsker at se på alle de efterkommere af 7,

177
00:13:05,430 --> 00:13:11,020
så er jeg nødt til at se på alle knuder under den.

178
00:13:11,020 --> 00:13:16,950
Så jeg har 3, 9 og 6 alle som efterkommere af 7.

179
00:13:16,950 --> 00:13:24,170
>> Den endelige udtryk, som vi vil tale om, er dette begreb om at være en søskende.

180
00:13:24,170 --> 00:13:27,980
Søskende - slags følge med på disse familie vilkår -

181
00:13:27,980 --> 00:13:33,150
er noder, der er på samme niveau i træet.

182
00:13:33,150 --> 00:13:42,230
Så, 3 og 9 er søskende, fordi de er på samme niveau i træet.

183
00:13:42,230 --> 00:13:46,190
De har begge den samme forælder, 7.

184
00:13:46,190 --> 00:13:51,400
De 6 har ingen søskende, fordi 9 ikke har nogen børn.

185
00:13:51,400 --> 00:13:55,540
Og 7 har ikke nogen søskende, fordi det er roden til vores træ,

186
00:13:55,540 --> 00:13:59,010
og der er altid kun 1 root.

187
00:13:59,010 --> 00:14:02,260
For 7 har søskende der skulle være et knudepunkt over 7.

188
00:14:02,260 --> 00:14:07,480
Der skulle være en forælder på 7, i hvilket tilfælde 7 ville ikke længere være roden af ​​træet.

189
00:14:07,480 --> 00:14:10,480
Så det nye moderselskab 7 vil også nødt til at få et barn,

190
00:14:10,480 --> 00:14:16,480
og at barnet ville så være søskende til 7.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Flytning af.

192
00:14:21,040 --> 00:14:24,930
Da vi startede vores diskussion af binære træer,

193
00:14:24,930 --> 00:14:28,790
vi talte om, hvordan vi skulle bruge dem til at

194
00:14:28,790 --> 00:14:32,800
opnå en fordel over begge arrays og hægtede lister.

195
00:14:32,800 --> 00:14:37,220
Og den måde, vi kommer til at gøre det på er med denne bestilling ejendom.

196
00:14:37,220 --> 00:14:41,080
Vi siger, at et binært træ er bestilt ifølge beskrivelsen

197
00:14:41,080 --> 00:14:45,740
Hvis for hvert knudepunkt i vores træ, alle dens efterkommere til venstre -

198
00:14:45,740 --> 00:14:48,670
den venstre barn og alle venstre barnets efterkommere -

199
00:14:48,670 --> 00:14:54,510
har mindre værdier, og alle de noder på højre -

200
00:14:54,510 --> 00:14:57,770
den rigtige barn og alle højre barnets efterkommere -

201
00:14:57,770 --> 00:15:02,800
har knuder større end værdien af ​​den aktuelle node, som vi kigger på.

202
00:15:02,800 --> 00:15:07,850
Bare for enkelhed, vil vi antage, at der ikke er nogen dubletter knuder i vores træ.

203
00:15:07,850 --> 00:15:11,180
For eksempel har vi i dette træ kommer ikke til at behandle sagen

204
00:15:11,180 --> 00:15:13,680
hvor vi har værdien 7 ved roden

205
00:15:13,680 --> 00:15:16,720
 og så har vi også værdien 7 andre steder i træet.

206
00:15:16,720 --> 00:15:24,390
I dette tilfælde, vil du bemærke, at dette træ faktisk er bestilt.

207
00:15:24,390 --> 00:15:26,510
Vi har værdien 7 ved roden.

208
00:15:26,510 --> 00:15:29,720
Alt til venstre for 7 -

209
00:15:29,720 --> 00:15:35,310
hvis jeg fortryde alle disse små mærker her -

210
00:15:35,310 --> 00:15:40,450
Alt til venstre for 7 - 3 og 6 -

211
00:15:40,450 --> 00:15:49,410
disse værdier er begge mindre end 7, og alt til højre - der er bare denne 9 -

212
00:15:49,410 --> 00:15:53,450
er større end syv.

213
00:15:53,450 --> 00:15:58,650
>> Dette er ikke den eneste bestilte træ indeholdende disse værdier,

214
00:15:58,650 --> 00:16:03,120
men lad os trække et par mere af dem.

215
00:16:03,120 --> 00:16:05,030
Der er faktisk en hel bunke af måder, vi kan gøre dette.

216
00:16:05,030 --> 00:16:09,380
Jeg har tænkt mig at bruge en forkortelse bare for at holde tingene simple hvor -

217
00:16:09,380 --> 00:16:11,520
snarere end at trække ud hele æsker-og-pile -

218
00:16:11,520 --> 00:16:14,220
Jeg skal bare til at trække tallene og tilføje pile forbinder dem.

219
00:16:14,220 --> 00:16:22,920
Hvis du vil starte, vi vil bare skrive vores oprindelige træ igen, hvor vi havde 7 og derefter en 3,

220
00:16:22,920 --> 00:16:25,590
og derefter 3 pegede tilbage til højre til 6,

221
00:16:25,590 --> 00:16:30,890
og 7 havde en højre barn, der var 9.

222
00:16:30,890 --> 00:16:33,860
Alright. Hvad er en anden måde, at vi kunne skrive dette træ?

223
00:16:33,860 --> 00:16:38,800
I stedet for 3 være den venstre barn 7,

224
00:16:38,800 --> 00:16:41,360
kunne vi også have 6 være den venstre barn på 7,

225
00:16:41,360 --> 00:16:44,470
og derefter 3 være den venstre barn af 6.

226
00:16:44,470 --> 00:16:48,520
Det ville ligne dette træ lige her, hvor jeg har fået 7,

227
00:16:48,520 --> 00:16:57,860
derefter 6, derefter 3 og 9 til højre.

228
00:16:57,860 --> 00:17:01,490
Vi har også behøver ikke at have 7 som vores root node.

229
00:17:01,490 --> 00:17:03,860
Vi kunne også have 6 som vores root node.

230
00:17:03,860 --> 00:17:06,470
Hvad ville det se ud?

231
00:17:06,470 --> 00:17:09,230
Hvis vi skal fastholde denne bestilt ejendom,

232
00:17:09,230 --> 00:17:12,970
alt til venstre for 6 skal være mindre end det.

233
00:17:12,970 --> 00:17:16,540
Der er kun én mulighed, og det er 3.

234
00:17:16,540 --> 00:17:19,869
Men så som højre barn på 6, har vi to muligheder.

235
00:17:19,869 --> 00:17:25,380
Først kunne vi have 7 og derefter 9,

236
00:17:25,380 --> 00:17:28,850
eller vi kunne tegne det - ligesom jeg er ved at gøre her -

237
00:17:28,850 --> 00:17:34,790
hvor vi har 9 som højre barn af 6,

238
00:17:34,790 --> 00:17:39,050
og derefter 7 som venstre barn af 9.

239
00:17:39,050 --> 00:17:44,240
>> Nu, 7 og 6 er ikke de eneste mulige værdier for roden.

240
00:17:44,240 --> 00:17:50,200
Vi kunne også have 3 være årsagen.

241
00:17:50,200 --> 00:17:52,240
Hvad sker der, hvis 3 er ved roden?

242
00:17:52,240 --> 00:17:54,390
Her tingene bliver en lille smule interessant.

243
00:17:54,390 --> 00:17:58,440
Tre ikke har nogen værdier, der er mindre end det,

244
00:17:58,440 --> 00:18:02,070
så at hele venstre side af træet er bare at være null.

245
00:18:02,070 --> 00:18:03,230
Der kommer ikke til at være noget der.

246
00:18:03,230 --> 00:18:07,220
Til højre, kunne vi nævne tingene i stigende rækkefølge.

247
00:18:07,220 --> 00:18:15,530
Vi kunne have 3, derefter 6 og derefter 7, så 9.

248
00:18:15,530 --> 00:18:26,710
Eller, kunne vi gøre 3, derefter 6, derefter 9, derefter 7.

249
00:18:26,710 --> 00:18:35,020
Eller, kunne vi gøre 3, derefter 7, derefter 6, derefter 9.

250
00:18:35,020 --> 00:18:40,950
Eller, 3, 7 - faktisk nej, kan vi ikke gøre en 7 længere.

251
00:18:40,950 --> 00:18:43,330
Det er vores eneste ting der.

252
00:18:43,330 --> 00:18:54,710
Vi kan gøre 9, og derefter fra 9 vi kan gøre 6 og derefter 7.

253
00:18:54,710 --> 00:19:06,980
Eller kan vi gøre 3, derefter 9, derefter 7, og derefter 6.

254
00:19:06,980 --> 00:19:12,490
>> Én ting er at henlede Deres opmærksomhed på her er

255
00:19:12,490 --> 00:19:14,510
at disse træer er lidt mærkeligt udseende.

256
00:19:14,510 --> 00:19:17,840
I Hvis vi især ser på 4 træer på højre side -

257
00:19:17,840 --> 00:19:20,930
Jeg vil cirkle dem, her -

258
00:19:20,930 --> 00:19:28,410
disse træer ser næsten præcis som en linket liste.

259
00:19:28,410 --> 00:19:32,670
Hvert knudepunkt har kun et barn,

260
00:19:32,670 --> 00:19:38,950
og så har vi ikke noget af dette træ-lignende struktur, som vi ser, for eksempel,

261
00:19:38,950 --> 00:19:44,720
 i dette ene Lone Tree herovre på den nederste venstre.

262
00:19:44,720 --> 00:19:52,490
Disse træer er faktisk kaldes degenererede binære træer,

263
00:19:52,490 --> 00:19:54,170
og vi vil tale om disse mere i fremtiden -

264
00:19:54,170 --> 00:19:56,730
især hvis du gå på at tage andre datalogikurser.

265
00:19:56,730 --> 00:19:59,670
Disse træer er degenereret.

266
00:19:59,670 --> 00:20:03,780
De er ikke meget nyttigt, fordi, ja, denne struktur egner sig

267
00:20:03,780 --> 00:20:08,060
 at slå gange svarende til den for en forbundet liste.

268
00:20:08,060 --> 00:20:13,050
Vi får ikke at drage fordel af den ekstra hukommelse - denne ekstra pointer -

269
00:20:13,050 --> 00:20:18,840
på grund af vores struktur er dårlig på denne måde.

270
00:20:18,840 --> 00:20:24,700
Snarere end at gå på og trække ud de binære træer, der har 9 ved roden,

271
00:20:24,700 --> 00:20:27,220
som er den sidste sag, som vi ville have,

272
00:20:27,220 --> 00:20:32,380
vi er i stedet, på dette tidspunkt, vil tale lidt om dette andet udtryk

273
00:20:32,380 --> 00:20:36,150
at vi bruger når vi taler om træer, som kaldes højden.

274
00:20:36,150 --> 00:20:45,460
>> Højden af ​​et træ er afstanden fra roden til den mest fjerntliggende knudepunkt,

275
00:20:45,460 --> 00:20:48,370
eller snarere antallet af humle, som du ville have at gøre med henblik på at

276
00:20:48,370 --> 00:20:53,750
starte fra roden og derefter ender på det mest for fjern node i træet.

277
00:20:53,750 --> 00:20:57,330
Hvis vi ser på nogle af disse træer, som vi har tegnet lige her,

278
00:20:57,330 --> 00:21:07,870
Vi kan se, at hvis vi tager dette træ i øverste venstre hjørne, og vi starter på 3,

279
00:21:07,870 --> 00:21:14,510
så er vi nødt til at gøre 1 hop for at komme til 6, en anden hop for at komme til 7,

280
00:21:14,510 --> 00:21:20,560
og en tredje hop at komme til 9.

281
00:21:20,560 --> 00:21:26,120
Således, at højden af ​​dette træ er 3.

282
00:21:26,120 --> 00:21:30,640
Vi kan gøre det samme øvelse for de andre træer, der er skitseret i denne grønne,

283
00:21:30,640 --> 00:21:40,100
og vi kan se, at højden af ​​alle disse træer er også virkelig 3.

284
00:21:40,100 --> 00:21:45,230
Det er en del af hvad der gør dem degenerere -

285
00:21:45,230 --> 00:21:53,750
at deres højde er blot en mindre end antallet af knudepunkter i hele træet.

286
00:21:53,750 --> 00:21:58,400
Hvis vi ser på dette andet træ, der er omgivet med røde, på den anden side,

287
00:21:58,400 --> 00:22:03,920
vi se, at de mest fjerntliggende blad noder er 6 og 9 -

288
00:22:03,920 --> 00:22:06,940
bladene er de knuder, der ikke har børn.

289
00:22:06,940 --> 00:22:11,760
Så for at komme fra rodnoden til enten 6 eller 9,

290
00:22:11,760 --> 00:22:17,840
vi gøre en hop at komme til 7 og derefter en anden hop at komme til 9,

291
00:22:17,840 --> 00:22:21,240
og ligeledes, at kun en anden hop fra 7 komme til 6.

292
00:22:21,240 --> 00:22:29,080
Så højden af ​​dette træ herovre er kun 2.

293
00:22:29,080 --> 00:22:35,330
Du kan gå tilbage og gøre det for alle de andre træer, som vi tidligere diskuterede

294
00:22:35,330 --> 00:22:37,380
begyndende med 7 og 6,

295
00:22:37,480 --> 00:22:42,500
og du vil opdage, at højden af ​​alle disse træer er også 2.

296
00:22:42,500 --> 00:22:46,320
>> Grunden til at vi har talt om bestilt binære træer

297
00:22:46,320 --> 00:22:50,250
og hvorfor de er cool, fordi du kan søge igennem dem i

298
00:22:50,250 --> 00:22:53,810
en meget lignende måde at søge over et ordnet array.

299
00:22:53,810 --> 00:22:58,720
Det er her, vi taler om at få det bedre lookup tid

300
00:22:58,720 --> 00:23:02,730
over den enkle forbundet liste.

301
00:23:02,730 --> 00:23:05,010
Med en sammenkædet liste - hvis du ønsker at finde et bestemt element -

302
00:23:05,010 --> 00:23:07,470
du er i bedste fald kommer til at gøre en slags lineær søgning

303
00:23:07,470 --> 00:23:10,920
hvor du starter i begyndelsen af ​​en liste og hop én efter én -

304
00:23:10,920 --> 00:23:12,620
en knude ved et knudepunkt -

305
00:23:12,620 --> 00:23:16,060
gennem hele listen, indtil du finder det, du søger efter.

306
00:23:16,060 --> 00:23:19,440
Betragtninger, hvis du har et binært træ, der er lagret i denne nice format,

307
00:23:19,440 --> 00:23:23,300
du kan faktisk få mere af en binær søgning foregår

308
00:23:23,300 --> 00:23:25,160
hvor du del og hersk

309
00:23:25,160 --> 00:23:29,490
og søgning via passende halvdel af træet i hvert trin.

310
00:23:29,490 --> 00:23:32,840
Lad os se, hvordan det fungerer.

311
00:23:32,840 --> 00:23:38,850
>> Hvis vi har - igen, gå tilbage til vores oprindelige træ -

312
00:23:38,850 --> 00:23:46,710
vi starter kl 7, vi har 3 på venstre, 9 til højre,

313
00:23:46,710 --> 00:23:51,740
og under 3 vi har 6.

314
00:23:51,740 --> 00:24:01,880
Hvis vi ønsker at søge efter nummer 6 i dette træ, ville vi starte ved roden.

315
00:24:01,880 --> 00:24:08,910
Vi ville sammenligne den værdi, vi leder efter, siger 6,

316
00:24:08,910 --> 00:24:12,320
til værdien lagret i knude som vi i øjeblikket ser på, 7,

317
00:24:12,320 --> 00:24:21,200
finder, at 6 er faktisk mindre end 7, så vi ville flytte til venstre.

318
00:24:21,200 --> 00:24:25,530
Hvis værdien af ​​6 havde været større end 7, ville vi have i stedet flyttet til højre.

319
00:24:25,530 --> 00:24:29,770
Da vi ved, at - på grund af strukturen i vores bestilte binært træ -

320
00:24:29,770 --> 00:24:33,910
alle værdier mindre end 7 vil blive gemt til venstre for 7,

321
00:24:33,910 --> 00:24:40,520
der er ingen grund til engang gider kigge gennem højre side af træet.

322
00:24:40,520 --> 00:24:43,780
Når vi flytter til venstre, og vi er nu ved knudepunktet indeholdende 3,

323
00:24:43,780 --> 00:24:48,110
vi kan gøre det samme sammenligning igen, hvor vi sammenligner 3 og 6.

324
00:24:48,110 --> 00:24:52,430
Og vi finder, at mens 6 - den værdi, vi leder efter - er større end 3,

325
00:24:52,430 --> 00:24:58,580
vi kan gå til højre side af knudepunktet indeholdende 3.

326
00:24:58,580 --> 00:25:02,670
Der er ingen venstre side her, så vi kunne have ignoreret det.

327
00:25:02,670 --> 00:25:06,510
Men vi ved kun, at fordi vi ser på selve træet,

328
00:25:06,510 --> 00:25:08,660
og vi kan se, at træet har ingen børn.

329
00:25:08,660 --> 00:25:13,640
>> Det er også ret nemt at slå op 6 i dette træ, hvis vi gør det os selv som mennesker,

330
00:25:13,640 --> 00:25:16,890
men lad os følge denne proces mekanisk som en computer ville gøre

331
00:25:16,890 --> 00:25:18,620
for virkelig at forstå algoritmen.

332
00:25:18,620 --> 00:25:26,200
På dette tidspunkt er vi nu ser på en node, der indeholder 6,

333
00:25:26,200 --> 00:25:29,180
og vi leder efter værdien 6,

334
00:25:29,180 --> 00:25:31,740
så, ja, vi har fundet den rette node.

335
00:25:31,740 --> 00:25:35,070
Vi fandt værdien 6 i vores træ, og vi kan stoppe vores søgning.

336
00:25:35,070 --> 00:25:37,330
På dette tidspunkt, afhængigt af hvad der foregår

337
00:25:37,330 --> 00:25:41,870
kan vi sige, ja, vi har fundet værdien 6, det eksisterer i vores træ.

338
00:25:41,870 --> 00:25:47,640
Eller, hvis vi planlægger at indsætte en node eller gøre noget, kan vi gøre det på dette tidspunkt.

339
00:25:47,640 --> 00:25:53,010
>> Lad os gøre et par flere opslag bare for at se hvordan det virker.

340
00:25:53,010 --> 00:25:59,390
Lad os se på, hvad der sker, hvis vi skulle forsøge at slå op værdien 10.

341
00:25:59,390 --> 00:26:02,970
Hvis vi skulle se op værdien 10, ville vi starte ved roden.

342
00:26:02,970 --> 00:26:07,070
Vi ville se, at 10 er større end 7, så vi ville flytte til højre.

343
00:26:07,070 --> 00:26:13,640
Vi ville komme til 9 og sammenligne 9 til 10 og se, at 9 er faktisk mindre end 10.

344
00:26:13,640 --> 00:26:16,210
Så igen, ville vi forsøge at flytte til højre.

345
00:26:16,210 --> 00:26:20,350
Men på dette punkt, ville vi opdage, at vi er på en null knudepunkt.

346
00:26:20,350 --> 00:26:23,080
Der er ikke noget der. Der er ikke noget, hvor 10 bør være.

347
00:26:23,080 --> 00:26:29,360
Det er her, vi kan rapportere fejl - at der rent faktisk er nr. 10 i træet.

348
00:26:29,360 --> 00:26:35,420
Og endelig, lad os gå igennem det tilfælde, hvor vi forsøger at slå op 1 i træet.

349
00:26:35,420 --> 00:26:38,790
Dette svarer til, hvad der sker, hvis vi ser op 10, undtagen i stedet for at gå til højre,

350
00:26:38,790 --> 00:26:41,260
vi kommer til at gå til venstre.

351
00:26:41,260 --> 00:26:46,170
Vi starter på 7 og se, at 1 er mindre end 7, så vi flytter til venstre.

352
00:26:46,170 --> 00:26:51,750
Vi får til 3 og se, at 1 er mindre end 3, så vi igen forsøger at flytte til venstre.

353
00:26:51,750 --> 00:26:59,080
På dette tidspunkt har vi en null knude, så vi igen kan rapportere fejl.

354
00:26:59,080 --> 00:27:10,260
>> Hvis du ønsker at lære mere om binære træer,

355
00:27:10,260 --> 00:27:14,420
Der er en hel masse sjove små problemer, som du kan gøre med dem.

356
00:27:14,420 --> 00:27:19,450
Jeg foreslår udøvelse af tegningen af ​​disse diagrammer en efter en

357
00:27:19,450 --> 00:27:21,910
og efter gennem alle de forskellige trin,

358
00:27:21,910 --> 00:27:25,060
da dette vil komme i super-handy

359
00:27:25,060 --> 00:27:27,480
ikke kun når du laver Huffman kodning problem sæt

360
00:27:27,480 --> 00:27:29,390
men også i fremtidige kurser -

361
00:27:29,390 --> 00:27:32,220
bare lære at trække ud disse datastrukturer og tænke igennem de problemer

362
00:27:32,220 --> 00:27:38,000
med pen og papir eller i dette tilfælde, og iPad stylus.

363
00:27:38,000 --> 00:27:41,000
>> På dette tidspunkt selv, vi kommer til at gå videre til at gøre nogle kodning praksis

364
00:27:41,000 --> 00:27:44,870
og faktisk spille med disse binære træer og se.

365
00:27:44,870 --> 00:27:52,150
Jeg har tænkt mig at skifte tilbage til min computer.

366
00:27:52,150 --> 00:27:58,480
For denne del af strækningen, i stedet for at bruge CS50 Run eller CS50 Spaces,

367
00:27:58,480 --> 00:28:01,500
Jeg har tænkt mig at bruge apparatet.

368
00:28:01,500 --> 00:28:04,950
>> Efter sammen med Problem Set specifikation,

369
00:28:04,950 --> 00:28:07,740
Jeg kan se, at jeg skulle åbne apparatet,

370
00:28:07,740 --> 00:28:11,020
gå til min Dropbox mappe, skal du oprette en mappe kaldet § 7,

371
00:28:11,020 --> 00:28:15,730
og derefter oprette en fil kaldet binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Her går vi. Jeg har apparatet allerede åben.

373
00:28:22,050 --> 00:28:25,910
Jeg har tænkt mig trække op en terminal.

374
00:28:25,910 --> 00:28:38,250
Jeg har tænkt mig at gå til Dropbox mappe, lave en mappe kaldet section7,

375
00:28:38,250 --> 00:28:42,230
og se, det er helt tom.

376
00:28:42,230 --> 00:28:48,860
Nu jeg har tænkt mig at åbne op binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Her går vi - tom fil.

378
00:28:51,750 --> 00:28:54,330
>> Lad os gå tilbage til specifikationen.

379
00:28:54,330 --> 00:28:59,850
Specifikationen anmoder om at skabe en ny type definition

380
00:28:59,850 --> 00:29:03,080
et binært træ node indeholdende int værdier -

381
00:29:03,080 --> 00:29:07,110
ligesom de værdier, som vi trak i vores diagrammer før.

382
00:29:07,110 --> 00:29:11,740
Vi vil bruge denne standardtekst typedef, at vi har gjort lige her

383
00:29:11,740 --> 00:29:14,420
at du skal genkende fra Problem Set 5 -

384
00:29:14,420 --> 00:29:19,190
hvis du gjorde det hash tabel måde at erobre speller program.

385
00:29:19,190 --> 00:29:22,540
Du bør også genkende det fra sidste uges afsnit

386
00:29:22,540 --> 00:29:23,890
hvor vi talte om hægtede lister.

387
00:29:23,890 --> 00:29:27,870
Vi har fået dette typedef af en struct node,

388
00:29:27,870 --> 00:29:34,430
og vi har givet denne struct node dette navn på struct node forhånd

389
00:29:34,430 --> 00:29:39,350
så vi kan så henvise til det, da vi ønsker at have struct node pointers

390
00:29:39,350 --> 00:29:45,740
som en del af vores struct, men vi har da omringede dette -

391
00:29:45,740 --> 00:29:47,700
eller rettere indesluttet dette - i en typedef

392
00:29:47,700 --> 00:29:54,600
således at senere i koden, kan vi henvise til denne struct som bare en knude i stedet for en struct node.

393
00:29:54,600 --> 00:30:03,120
>> Dette vil være meget lig den enkeltvis-linkede liste definition, som vi så i sidste uge.

394
00:30:03,120 --> 00:30:20,070
For at gøre dette, lad os bare starte med at skrive ud standardtekst.

395
00:30:20,070 --> 00:30:23,840
Vi ved, at vi skal have en heltalsværdi,

396
00:30:23,840 --> 00:30:32,170
så vi vil sætte i int værdi, og så i stedet for at have bare en pointer til den næste element -

397
00:30:32,170 --> 00:30:33,970
som vi gjorde med enkeltvis-linked lister -

398
00:30:33,970 --> 00:30:38,110
vi bliver nødt til venstre og højre barn pointers.

399
00:30:38,110 --> 00:30:42,880
Det er temmelig simpelt også - struct node * venstre barn;

400
00:30:42,880 --> 00:30:51,190
og struct node * rigtige barn. Cool.

401
00:30:51,190 --> 00:30:54,740
Det ligner en ganske god start.

402
00:30:54,740 --> 00:30:58,530
Lad os gå tilbage til specifikationen.

403
00:30:58,530 --> 00:31:05,030
>> Nu skal vi til at erklære en global node * variabel for roden af ​​et træ.

404
00:31:05,030 --> 00:31:10,590
Vi vil gøre dette globale ligesom vi gjorde første pointerjustering i vores linkede liste også globalt.

405
00:31:10,590 --> 00:31:12,690
Det var så at i de funktioner, som vi skriver

406
00:31:12,690 --> 00:31:16,180
Vi behøver ikke at holde passerer omkring dette rod -

407
00:31:16,180 --> 00:31:19,620
selvom vi vil se, at hvis du ønsker at skrive disse funktioner rekursivt,

408
00:31:19,620 --> 00:31:22,830
Det kan være bedre at ikke engang passere den rundt som en global i første omgang

409
00:31:22,830 --> 00:31:28,090
og i stedet initialisere det lokalt i din primære funktion.

410
00:31:28,090 --> 00:31:31,960
Men, vil vi gøre det på globalt plan at starte.

411
00:31:31,960 --> 00:31:39,920
Igen, vil vi give et par rum, og jeg har tænkt mig at erklære en node * rod.

412
00:31:39,920 --> 00:31:46,770
Blot for at sørge for, at jeg ikke forlade dette initialiseret, vil jeg sætte den lig med nul.

413
00:31:46,770 --> 00:31:52,210
Nu, i hovedfunktion - som vi vil skrive virkelig hurtigt lige her -

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
og jeg har tænkt mig at begynde at erklære min argv array som const bare så jeg ved,

416
00:32:10,640 --> 00:32:14,550
at disse argumenter er argumenter, som jeg sandsynligvis ikke vil ændre.

417
00:32:14,550 --> 00:32:18,390
Hvis jeg ønsker at ændre dem jeg burde nok være at gøre kopier af dem.

418
00:32:18,390 --> 00:32:21,740
Du vil se denne meget i kode.

419
00:32:21,740 --> 00:32:25,440
Det er fint begge veje. Det er fint at lade det være som - udelade const, hvis du ønsker.

420
00:32:25,440 --> 00:32:28,630
Jeg typisk sætte det i bare så minder jeg mig selv

421
00:32:28,630 --> 00:32:33,650
 at jeg sandsynligvis ikke ønsker at ændre disse argumenter.

422
00:32:33,650 --> 00:32:39,240
>> Som altid, vil jeg medtage denne return 0 linje i slutningen af ​​main.

423
00:32:39,240 --> 00:32:45,730
Her vil jeg initialisere min rodnoden.

424
00:32:45,730 --> 00:32:48,900
Som det ser ud lige nu, jeg har en pointer, der er sat til nul,

425
00:32:48,900 --> 00:32:52,970
så det peger på noget.

426
00:32:52,970 --> 00:32:57,480
For rent faktisk at begynde at opbygge den knude,

427
00:32:57,480 --> 00:32:59,250
Jeg skal først tildele hukommelse til det.

428
00:32:59,250 --> 00:33:05,910
Jeg har tænkt mig at gøre det ved at gøre hukommelse på heapen ved hjælp af malloc.

429
00:33:05,910 --> 00:33:10,660
Jeg har tænkt mig at sætte rod lig med resultatet af malloc,

430
00:33:10,660 --> 00:33:19,550
og jeg har tænkt mig at bruge sizeof operatør til at beregne størrelsen af ​​en node.

431
00:33:19,550 --> 00:33:24,990
Grunden til at jeg bruger sizeof node i modsætning til, sige,

432
00:33:24,990 --> 00:33:37,020
gør noget som dette - malloc (4 + 4 +4) eller malloc 12 -

433
00:33:37,020 --> 00:33:40,820
er fordi jeg vil have min kode til at være så kompatibelt som muligt.

434
00:33:40,820 --> 00:33:44,540
Jeg ønsker at være i stand til at tage denne. C. fil, kompilere det på apparatet,

435
00:33:44,540 --> 00:33:48,820
og derefter kompilere det på min 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
eller på et helt andet arkitektur -

437
00:33:52,040 --> 00:33:54,640
og jeg ønsker alt dette til at arbejde det samme.

438
00:33:54,640 --> 00:33:59,510
>> Hvis jeg gør antagelser om størrelsen af ​​variabler -

439
00:33:59,510 --> 00:34:02,070
størrelsen af ​​en int eller størrelsen af ​​en pegepind -

440
00:34:02,070 --> 00:34:06,070
så er jeg også at gøre antagelser om, hvilke former for arkitekturer

441
00:34:06,070 --> 00:34:10,440
som min kode kan lykkes at kompilere når de kører.

442
00:34:10,440 --> 00:34:15,030
Brug altid sizeof i modsætning til manuelt at summere struct felter.

443
00:34:15,030 --> 00:34:20,500
Den anden grund er, at der også kan være polstring at compileren lægger i struct.

444
00:34:20,500 --> 00:34:26,570
Selv bare summere de enkelte områder er ikke noget, du typisk vil gøre,

445
00:34:26,570 --> 00:34:30,340
så skal du slette denne linje.

446
00:34:30,340 --> 00:34:33,090
Nu, for virkelig at initialisere denne rod node,

447
00:34:33,090 --> 00:34:36,489
Jeg har tænkt mig at skulle tilslutte værdier for hver af de forskellige felter.

448
00:34:36,489 --> 00:34:41,400
For eksempel, for værdi jeg ved, at jeg vil initialisere til 7

449
00:34:41,400 --> 00:34:46,920
og for nu jeg har tænkt mig at sætte venstre barn til at være null

450
00:34:46,920 --> 00:34:55,820
og højre barn også være nul. Great!

451
00:34:55,820 --> 00:35:02,670
Vi har gjort denne del af spec.

452
00:35:02,670 --> 00:35:07,390
>> Specifikationen ned i bunden af ​​side 3 beder mig om at oprette tre flere knuder -

453
00:35:07,390 --> 00:35:10,600
en indeholdende 3, en indeholdende 6, og en med 9 -

454
00:35:10,600 --> 00:35:14,210
og derefter wire dem op, så det ser ud præcis som vores trædiagram

455
00:35:14,210 --> 00:35:17,120
at vi talte om tidligere.

456
00:35:17,120 --> 00:35:20,450
Lad os gøre det ret hurtigt her.

457
00:35:20,450 --> 00:35:26,270
Du vil se virkelig hurtigt, at jeg har tænkt mig at begynde at skrive en masse dobbelt kode.

458
00:35:26,270 --> 00:35:32,100
Jeg har tænkt mig at oprette en node * og jeg har tænkt mig at kalde det tre.

459
00:35:32,100 --> 00:35:36,000
Jeg har tænkt mig at sætte det lig med malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Jeg har tænkt mig at sætte tre-> værdi = 3.

461
00:35:41,070 --> 00:35:54,780
Tre -> left_child = NULL; tre -> højre _child = NULL; så godt.

462
00:35:54,780 --> 00:36:01,150
Det ser temmelig ligner initialisere roden, og det er præcis, hvad

463
00:36:01,150 --> 00:36:05,760
Jeg har tænkt mig at gøre, hvis jeg starter initialisering 6 og 9 samt.

464
00:36:05,760 --> 00:36:20,720
Jeg vil gøre det virkelig hurtigt her - faktisk, jeg vil gøre lidt kopiere og indsætte,

465
00:36:20,720 --> 00:36:46,140
og sørg for, at I - okay.

466
00:36:46,470 --> 00:37:09,900
 Nu har jeg fået det kopieret, og jeg kan gå videre og indstille denne lig med 6.

467
00:37:09,900 --> 00:37:14,670
Du kan se, at det tager et stykke tid og er ikke super-effektiv.

468
00:37:14,670 --> 00:37:22,610
På bare en lille smule, vil vi skrive en funktion, der vil gøre dette for os.

469
00:37:22,610 --> 00:37:32,890
Jeg ønsker at erstatte dette med en 9, erstatte det med en 6.

470
00:37:32,890 --> 00:37:37,360
>> Nu har vi alle vores knudepunkter skabt og initialiseret.

471
00:37:37,360 --> 00:37:41,200
Vi har fået vores rod sat lig med 7, eller indeholder værdien 7,

472
00:37:41,200 --> 00:37:46,510
vores node indeholdende 3, vores node indeholdende 6, og vores node indeholdende 9.

473
00:37:46,510 --> 00:37:50,390
På dette tidspunkt, er alt hvad vi behøver at gøre wire hele op.

474
00:37:50,390 --> 00:37:53,020
Grunden til at jeg initialiseres alle pegepinde til null er bare så at jeg sørge for, at

475
00:37:53,020 --> 00:37:56,260
Jeg har ikke nogen startværdi pejlemærker i der ved et uheld.

476
00:37:56,260 --> 00:38:02,290
Og også siden, på dette tidspunkt, jeg kun har til rent faktisk at forbinde noder til hinanden -

477
00:38:02,290 --> 00:38:04,750
til dem, at de faktisk er tilsluttet - Jeg behøver ikke at gå igennem og gøre

478
00:38:04,750 --> 00:38:08,240
sikker på, at alle nuller er derinde i de relevante steder.

479
00:38:08,240 --> 00:38:15,630
>> Start ved roden, jeg ved, at roden venstre barn er 3.

480
00:38:15,630 --> 00:38:21,250
Jeg ved, at roden ret barn er 9.

481
00:38:21,250 --> 00:38:24,880
Efter dette, den eneste Barn, jeg har tilbage at bekymre sig om

482
00:38:24,880 --> 00:38:39,080
er 3 ret barn, hvilket er 6.

483
00:38:39,080 --> 00:38:44,670
På dette tidspunkt, det hele ser temmelig godt.

484
00:38:44,670 --> 00:38:54,210
Vi vil slette nogle af disse linjer.

485
00:38:54,210 --> 00:38:59,540
Nu er alt ser godt ud.

486
00:38:59,540 --> 00:39:04,240
Lad os gå tilbage til vores specifikationer og se, hvad vi skal gøre næste.

487
00:39:04,240 --> 00:39:07,610
>> På dette punkt har vi at skrive en kaldet funktionen 'indeholder'

488
00:39:07,610 --> 00:39:14,150
med en prototype af "bool Indeholder (int værdi) '.

489
00:39:14,150 --> 00:39:17,060
Og det indeholder funktionen vil returnere sandt

490
00:39:17,060 --> 00:39:21,200
 hvis træet peget på af vores globale rod variabel

491
00:39:21,200 --> 00:39:26,950
 indeholder den værdi, der sendes ind i funktionen og falsk ellers.

492
00:39:26,950 --> 00:39:29,000
Lad os gå videre og gøre det.

493
00:39:29,000 --> 00:39:35,380
Dette vil være præcis som det opslag, som vi gjorde ved hånden på iPad bare en lille smule siden.

494
00:39:35,380 --> 00:39:40,130
Lad os ind i en lille smule og rulle op.

495
00:39:40,130 --> 00:39:43,130
Vi vil sætte denne funktion lige over vores vigtigste funktion

496
00:39:43,130 --> 00:39:48,990
så vi ikke behøver at gøre nogen form for prototyping.

497
00:39:48,990 --> 00:39:55,960
Så bool indeholder (int værdi).

498
00:39:55,960 --> 00:40:00,330
Der vi går. Der er vores standardtekst erklæring.

499
00:40:00,330 --> 00:40:02,900
Blot for at sørge for, at dette vil kompilere,

500
00:40:02,900 --> 00:40:06,820
Jeg har tænkt mig at gå videre og bare sætte den lig returnere falsk.

501
00:40:06,820 --> 00:40:09,980
Lige nu denne funktion vil bare ikke gøre noget, og altid rapportere, at

502
00:40:09,980 --> 00:40:14,010
den værdi, vi leder efter, er ikke i træet.

503
00:40:14,010 --> 00:40:16,280
>> På dette tidspunkt er det nok en god ide -

504
00:40:16,280 --> 00:40:19,600
siden vi har skrevet en hel bunke af kode, og vi har ikke engang prøvet at teste det endnu -

505
00:40:19,600 --> 00:40:22,590
at sikre, at det hele kompilerer.

506
00:40:22,590 --> 00:40:27,460
Der er et par ting, som vi skal gøre for at sikre, at dette rent faktisk vil kompilere.

507
00:40:27,460 --> 00:40:33,530
Først se, om vi har brugt alle funktioner i nogen biblioteker, som vi endnu ikke har medtaget.

508
00:40:33,530 --> 00:40:37,940
De funktioner, vi har brugt hidtil er malloc,

509
00:40:37,940 --> 00:40:43,310
og så har vi også brugt denne type - denne ikke-standard type kaldet 'bool' -

510
00:40:43,310 --> 00:40:45,750
som er inkluderet i standard bool header fil.

511
00:40:45,750 --> 00:40:53,250
Vi vil helt sikkert inkludere standard bool.h for den bool type,

512
00:40:53,250 --> 00:40:59,230
og vi ønsker også at # include standard lib.h for standard biblioteker

513
00:40:59,230 --> 00:41:03,530
der omfatter malloc, og gratis, og alt dette.

514
00:41:03,530 --> 00:41:08,660
Så zoome ud, vi kommer til at holde op.

515
00:41:08,660 --> 00:41:14,190
Lad os forsøge at sikre, at dette rent faktisk gjorde kompilere.

516
00:41:14,190 --> 00:41:18,150
Vi ser, at det gør det, så vi er på rette spor.

517
00:41:18,150 --> 00:41:22,990
>> Lad os åbne binary_tree.c igen.

518
00:41:22,990 --> 00:41:34,530
Det kompilerer. Lad os gå ned og sørg for, at vi indsætter nogle opkald til vores indeholder funktionsmoduler -

519
00:41:34,530 --> 00:41:40,130
bare for at sørge for, at det er alt sammen meget godt.

520
00:41:40,130 --> 00:41:43,170
For eksempel, når vi gjorde nogle opslag i vores træ tidligere

521
00:41:43,170 --> 00:41:48,500
vi forsøgte at slå værdierne op 6, 10 og 1, og vi vidste, at 6 var i træet,

522
00:41:48,500 --> 00:41:52,220
10 var ikke i træet, og 1 var ikke i træet enten.

523
00:41:52,220 --> 00:41:57,230
Lad os bruge disse eksempler opkald som en måde at finde ud af, om eller ej

524
00:41:57,230 --> 00:41:59,880
vores Indeholder funktion er aktiveret.

525
00:41:59,880 --> 00:42:05,210
For at gøre det, vil jeg bruge printf funktion,

526
00:42:05,210 --> 00:42:10,280
og vi kommer til at udskrive resultatet af indkaldelsen til indeholder.

527
00:42:10,280 --> 00:42:13,280
Jeg har tænkt mig at sætte i en streng "indeholder (% d) = fordi

528
00:42:13,280 --> 00:42:20,470
 vi kommer til at tilslutte den værdi, vi vil kigge efter,

529
00:42:20,470 --> 00:42:27,130
og =% s \ n "og bruge det som vores formatstreng.

530
00:42:27,130 --> 00:42:30,720
Vi vil bare se - bogstaveligt talt udskrive på skærmen -

531
00:42:30,720 --> 00:42:32,060
hvad der ligner et funktionskald.

532
00:42:32,060 --> 00:42:33,580
Det er faktisk ikke den funktion opkald.

533
00:42:33,580 --> 00:42:36,760
 Dette er blot en streng designet til at ligne en funktion opkald.

534
00:42:36,760 --> 00:42:41,140
>> Nu vil vi tilslutte værdierne.

535
00:42:41,140 --> 00:42:43,580
Vi vil prøve indeholder den 6,

536
00:42:43,580 --> 00:42:48,340
og derefter hvad vi vil gøre her er at bruge det ternære operatør.

537
00:42:48,340 --> 00:42:56,340
Lad os se - indeholder 6 - ja, nu har jeg indeholdt 6, og hvis indeholder 6 er sandt,

538
00:42:56,340 --> 00:43:01,850
den streng, som vi vil sende til% s format karakter

539
00:43:01,850 --> 00:43:04,850
bliver strengen "true".

540
00:43:04,850 --> 00:43:07,690
Lad os rulle over en lille smule.

541
00:43:07,690 --> 00:43:16,210
Ellers ønsker vi at sende strengen "falsk", hvis indeholder 6 returnerer falsk.

542
00:43:16,210 --> 00:43:19,730
Dette er en lille goofy udseende, men jeg regner med jeg kan lige så godt illustrere

543
00:43:19,730 --> 00:43:23,780
hvad den ternære operatør ser ud, da vi ikke har set det for en stund.

544
00:43:23,780 --> 00:43:27,670
Dette vil være en pæn, smart måde at finde ud af, om vores Indeholder funktion er aktiveret.

545
00:43:27,670 --> 00:43:30,040
Jeg har tænkt mig at rulle tilbage over til venstre,

546
00:43:30,040 --> 00:43:39,900
og jeg har tænkt mig at kopiere og indsætte denne linje et par gange.

547
00:43:39,900 --> 00:43:44,910
Det ændrede nogle af disse værdier omkring,

548
00:43:44,910 --> 00:43:59,380
så dette vil være 1, og dette vil være 10.

549
00:43:59,380 --> 00:44:02,480
>> På dette tidspunkt har vi en pæn indeholder funktionsmoduler.

550
00:44:02,480 --> 00:44:06,080
Vi har nogle tests, og vi vil se, hvis dette alle værker.

551
00:44:06,080 --> 00:44:08,120
På dette tidspunkt har vi skrevet nogle mere kode.

552
00:44:08,120 --> 00:44:13,160
Tid til at forlade ud og sørg for, at alt stadig kompilerer.

553
00:44:13,160 --> 00:44:20,360
Afslut ud, og lad os nu prøve at lave binært træ igen.

554
00:44:20,360 --> 00:44:22,260
Tja, det ser ud til vi har fået en fejl,

555
00:44:22,260 --> 00:44:26,930
Og vi har dette udtrykkeligt erklærer biblioteksfunktionen printf.

556
00:44:26,930 --> 00:44:39,350
Det ser ud til vi skal gå ind og # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Og med dette, burde alt kompilere. Vi er alle gode.

558
00:44:45,350 --> 00:44:50,420
Lad os nu prøve at køre binært træ og se hvad der sker.

559
00:44:50,420 --> 00:44:53,520
Her er vi,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
og vi kan se, at som vi forventede -

561
00:44:55,190 --> 00:44:56,910
fordi vi ikke har gennemført indeholder endnu,

562
00:44:56,910 --> 00:44:59,800
eller rettere, vi har lige sat i return false -

563
00:44:59,800 --> 00:45:03,300
vi se, at det bare er tilbage falsk for dem alle,

564
00:45:03,300 --> 00:45:06,180
så er alt arbejder for det meste temmelig godt.

565
00:45:06,180 --> 00:45:11,860
>> Lad os gå tilbage i og faktisk gennemfører indeholder på dette punkt.

566
00:45:11,860 --> 00:45:17,490
Jeg har tænkt mig at rulle ned, zoome ind, og -

567
00:45:17,490 --> 00:45:22,330
husk, den algoritme, som vi brugte var, at vi startede på rodnoden

568
00:45:22,330 --> 00:45:28,010
og derefter ved hvert knudepunkt, som vi støder på, gør vi en sammenligning,

569
00:45:28,010 --> 00:45:32,380
og baseret på denne sammenligning vi enten bevæge sig mod venstre barn eller højre barn.

570
00:45:32,380 --> 00:45:39,670
Dette kommer til at se meget ligner den binære søgekoden, som vi skrev tidligere i udtrykket.

571
00:45:39,670 --> 00:45:47,810
Når vi starter, ved vi, at vi ønsker at holde fast i den aktuelle node

572
00:45:47,810 --> 00:45:54,050
at vi kigger på, og den aktuelle node vil blive initialiseret til roden node.

573
00:45:54,050 --> 00:45:56,260
Og nu vil vi holde gå gennem træet,

574
00:45:56,260 --> 00:45:58,140
og husk, at vi stopper tilstand -

575
00:45:58,140 --> 00:46:01,870
 når vi faktisk arbejdede gennem eksempel med hånden -

576
00:46:01,870 --> 00:46:03,960
var, da vi stødte på en null knude,

577
00:46:03,960 --> 00:46:05,480
ikke når vi kiggede på en null barn,

578
00:46:05,480 --> 00:46:09,620
men når vi faktisk flyttet til et knudepunkt i træet

579
00:46:09,620 --> 00:46:12,640
og fandt, at vi er på en null knudepunkt.

580
00:46:12,640 --> 00:46:20,720
Vi kommer til at gentage indtil cur ikke er lig med nul.

581
00:46:20,720 --> 00:46:22,920
Og hvad skal vi gøre?

582
00:46:22,920 --> 00:46:31,610
Vi kommer til at teste, om (nuværende -> værdi == værdi),

583
00:46:31,610 --> 00:46:35,160
så ved vi, at vi faktisk har fundet den knude, som vi leder efter.

584
00:46:35,160 --> 00:46:40,450
Så her kan vi returnere sandt.

585
00:46:40,450 --> 00:46:49,830
Ellers ønsker vi at se, om eller ikke værdien er mindre end værdien.

586
00:46:49,830 --> 00:46:53,850
Hvis den aktuelle node værdi er mindre end den værdi, vi leder efter,

587
00:46:53,850 --> 00:46:57,280
vi kommer til at flytte til højre.

588
00:46:57,280 --> 00:47:10,600
Så nuværende = nuværende -> right_child, og ellers vil vi flytte til venstre.

589
00:47:10,600 --> 00:47:17,480
cur = cur -> left_child. Temmelig enkel.

590
00:47:17,480 --> 00:47:22,830
>> Du kender måske den løkke, ligner meget det fra

591
00:47:22,830 --> 00:47:27,580
binær søgning tidligere i udtrykket, undtagen da vi havde at gøre med lav, middel og høj.

592
00:47:27,580 --> 00:47:30,000
Her har vi bare nødt til at se på en aktuel værdi,

593
00:47:30,000 --> 00:47:31,930
så det er rart og enkel.

594
00:47:31,930 --> 00:47:34,960
Lad os sørge for denne kode virker.

595
00:47:34,960 --> 00:47:42,780
Først sørg for at det kompilerer. Ligner det gør.

596
00:47:42,780 --> 00:47:47,920
Lad os prøve at køre det.

597
00:47:47,920 --> 00:47:50,160
Og ja, den udskriver alt, hvad vi forventede.

598
00:47:50,160 --> 00:47:54,320
Den finder 6 i træet, ikke finder 10, fordi 10 ikke er i træet,

599
00:47:54,320 --> 00:47:57,740
og ikke finder 1 enten fordi 1 er heller ikke i træet.

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

601
00:48:01,420 --> 00:48:04,470
>> Alright. Lad os gå tilbage til vores specifikationer og se, hvad der bliver det næste.

602
00:48:04,470 --> 00:48:07,990
Nu er det ønsker at tilføje nogle flere knuder til vores træ.

603
00:48:07,990 --> 00:48:11,690
Den ønsker at tilføje 5, 2, og 8, og sørg for, at vores indeholder kode

604
00:48:11,690 --> 00:48:13,570
stadig fungerer som forventet.

605
00:48:13,570 --> 00:48:14,900
Lad os gå gøre det.

606
00:48:14,900 --> 00:48:19,430
På dette tidspunkt, i stedet for at gøre det irriterende kopiere og indsætte igen

607
00:48:19,430 --> 00:48:23,770
lad os skrive en funktion til rent faktisk at oprette en node.

608
00:48:23,770 --> 00:48:27,740
Hvis vi rulle ned hele vejen til main, kan vi se, at vi har gjort dette

609
00:48:27,740 --> 00:48:31,210
meget ens kode igen og igen hver gang, at vi ønsker at skabe en node.

610
00:48:31,210 --> 00:48:39,540
>> Lad os skrive en funktion, der rent faktisk vil bygge en node for os og returnere det.

611
00:48:39,540 --> 00:48:41,960
Jeg har tænkt mig at kalde det build_node.

612
00:48:41,960 --> 00:48:45,130
Jeg har tænkt mig at bygge en node med en bestemt værdi.

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

614
00:48:51,040 --> 00:48:56,600
Den første ting jeg har tænkt mig at gøre, er faktisk at skabe plads til node på heapen.

615
00:48:56,600 --> 00:49:05,400
Så node * n = malloc (sizeof (node)), n -> value = værdi;

616
00:49:05,400 --> 00:49:14,960
og så her, jeg bare at initialisere alle felterne for at være passende værdier.

617
00:49:14,960 --> 00:49:22,500
Og til allersidst, vil vi returnere vores node.

618
00:49:22,500 --> 00:49:28,690
Alright. Én ting at bemærke er, at denne funktion lige her

619
00:49:28,690 --> 00:49:34,320
kommer til at returnere en pointer til hukommelsen, der har været heap-tildelte.

620
00:49:34,320 --> 00:49:38,880
Hvad er nice om dette er, at denne knude nu -

621
00:49:38,880 --> 00:49:42,420
vi er nødt til at erklære den på heapen, fordi hvis vi erklærede det på stakken

622
00:49:42,420 --> 00:49:45,050
ville vi ikke være i stand til at gøre det i denne funktion som denne.

623
00:49:45,050 --> 00:49:47,690
Denne hukommelse ville gå ud af rækkevidde

624
00:49:47,690 --> 00:49:51,590
og ville være ugyldig, hvis vi forsøgte at få adgang til det senere.

625
00:49:51,590 --> 00:49:53,500
Da vi erklære heap-allokeret hukommelse,

626
00:49:53,500 --> 00:49:55,830
vi er nødt til at tage sig af at befri den senere

627
00:49:55,830 --> 00:49:58,530
for vores program til ikke lække nogen hukommelse.

628
00:49:58,530 --> 00:50:01,270
Vi har punting på, at der for alt andet i koden

629
00:50:01,270 --> 00:50:02,880
kun for nemheds skyld på det tidspunkt,

630
00:50:02,880 --> 00:50:05,610
men hvis du nogensinde skrive en funktion, der ligner denne

631
00:50:05,610 --> 00:50:10,370
hvor du har fået - nogle kalder det en malloc eller realloc inde -

632
00:50:10,370 --> 00:50:14,330
du vil være sikker på, at du lægger en slags kommentar heroppe der siger,

633
00:50:14,330 --> 00:50:29,970
hey, du ved, returnerer en bunke-tildelte node initialiseret med de beståede-i værdi.

634
00:50:29,970 --> 00:50:33,600
Og så du vil være sikker på, at du lægger i en slags notat, der siger

635
00:50:33,600 --> 00:50:41,720
opkalderen skal befri den returnerede hukommelse.

636
00:50:41,720 --> 00:50:45,450
På den måde, hvis nogen nogensinde går og bruger denne funktion,

637
00:50:45,450 --> 00:50:48,150
de ved, at uanset hvad de kommer tilbage fra denne funktion

638
00:50:48,150 --> 00:50:50,870
på et tidspunkt skal frigøres.

639
00:50:50,870 --> 00:50:53,940
>> Antages det, at alt er vel og godt her,

640
00:50:53,940 --> 00:51:02,300
vi kan gå ned i vores kode og erstatte alle disse linjer lige her

641
00:51:02,300 --> 00:51:05,410
med opkald til vores build node-funktionen.

642
00:51:05,410 --> 00:51:08,170
Lad os gøre det virkelig hurtigt.

643
00:51:08,170 --> 00:51:15,840
Den ene del, som vi ikke kommer til at erstatte, er denne del hernede

644
00:51:15,840 --> 00:51:18,520
ved bunden, hvor vi faktisk wire op knudepunkterne til at pege på hinanden,

645
00:51:18,520 --> 00:51:21,030
fordi at vi ikke kan gøre i vores funktion.

646
00:51:21,030 --> 00:51:37,400
Men, lad os gøre root = build_node (7); node * tre = build_node (3);

647
00:51:37,400 --> 00:51:47,980
node * seks = build_node (6), node * ni = build_node (9).

648
00:51:47,980 --> 00:51:52,590
Og nu har vi også ønsket at tilføje noder til -

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

650
00:52:03,530 --> 00:52:09,760
og hvad var den anden knude? Lad os se her. Vi ønskede også at tilføje en 2 -

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

652
00:52:20,280 --> 00:52:26,850
Alright. På dette tidspunkt ved vi, at vi har fået den 7, 3, 9, og 6

653
00:52:26,850 --> 00:52:30,320
alle kabelførte passende op, men hvad med 5, 8 og 2?

654
00:52:30,320 --> 00:52:33,550
For at holde alt i den rigtige rækkefølge,

655
00:52:33,550 --> 00:52:39,230
Vi ved, at tre ret barn er 6.

656
00:52:39,230 --> 00:52:40,890
Så hvis vi kommer til at tilføje 5,

657
00:52:40,890 --> 00:52:46,670
de 5 også hører til i den højre side af træet, hvoraf 3 er roden,

658
00:52:46,670 --> 00:52:50,440
så 5 hører som venstre barn af 6.

659
00:52:50,440 --> 00:52:58,650
Vi kan gøre dette ved at sige, seks -> left_child = fem;

660
00:52:58,650 --> 00:53:10,790
og derefter 8 hører som venstre barn 9, så ni -> left_child = otte;

661
00:53:10,790 --> 00:53:22,190
og derefter 2 er den venstre barn af 3, så vi kan gøre det op her - Dig -> left_child = to;.

662
00:53:22,190 --> 00:53:27,730
Hvis du ikke helt følge med det, jeg foreslår, at du trækker det ud selv.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Lad os gemme det. Lad os gå ud og sørg for at det kompilerer,

664
00:53:35,660 --> 00:53:40,760
og så kan vi tilføje i vores Indeholder opkald.

665
00:53:40,760 --> 00:53:44,120
Ligner alt stadig kompilerer.

666
00:53:44,120 --> 00:53:51,790
Lad os gå ind og tilføje i nogle indeholder opkald.

667
00:53:51,790 --> 00:53:59,640
Igen, jeg vil gøre en lille smule af kopiere og indsætte.

668
00:53:59,640 --> 00:54:15,860
Lad os nu søge efter 5, 8 og 2. Alright.

669
00:54:15,860 --> 00:54:28,330
Lad os sørge for, at alt dette ser godt ud endnu. Great! Gem og afslut.

670
00:54:28,330 --> 00:54:33,220
Nu lad os gøre, kompilere, og lad os nu køre.

671
00:54:33,220 --> 00:54:37,540
Ud fra resultaterne ser det ud som alt fungerer bare rart og godt.

672
00:54:37,540 --> 00:54:41,780
Great! Så nu har vi fået vores indeholder funktionsmoduler skrevet.

673
00:54:41,780 --> 00:54:46,160
Lad os gå videre og begynde at arbejde på, hvordan man indsætter noder i træet

674
00:54:46,160 --> 00:54:50,000
siden, da vi gør det lige nu, er tingene ikke meget smuk.

675
00:54:50,000 --> 00:54:52,280
>> Hvis vi går tilbage til specifikationen,

676
00:54:52,280 --> 00:55:00,540
det beder os om at skrive en funktion kaldet indsætte - igen, returnerer en bool

677
00:55:00,540 --> 00:55:04,400
for, hvorvidt vi faktisk kunne indsætte node i træet -

678
00:55:04,400 --> 00:55:07,710
og derefter den værdi der skal indsættes i træet er angivet som

679
00:55:07,710 --> 00:55:11,060
det eneste argument til vores Indsæt funktion.

680
00:55:11,060 --> 00:55:18,180
Vi vil vende tilbage sandt, hvis vi rent faktisk kunne indsætte den knude, der indeholder værdi ind i træet,

681
00:55:18,180 --> 00:55:20,930
hvilket betyder, at vi, den ene havde nok hukommelse,

682
00:55:20,930 --> 00:55:24,840
og derefter to, havde denne node ikke allerede eksisterer i træet siden -

683
00:55:24,840 --> 00:55:32,170
Husk, vi ikke vil have dublerede værdier i træet, bare for at gøre tingene simple.

684
00:55:32,170 --> 00:55:35,590
Alright. Back til koden.

685
00:55:35,590 --> 00:55:44,240
Åben den op. Zoom ind på en smule, derefter rulle ned.

686
00:55:44,240 --> 00:55:47,220
Lad os sætte indsatsen funktionen lige over indeholder.

687
00:55:47,220 --> 00:55:56,360
Igen, det kommer til at hedde bool insert (int værdi).

688
00:55:56,360 --> 00:56:01,840
Giv det lidt mere plads, og derefter, som en standard,

689
00:56:01,840 --> 00:56:08,870
lad os sætte i return false til allersidst.

690
00:56:08,870 --> 00:56:22,620
Nu nede i bunden, lad os gå videre og i stedet for manuelt at bygge knudepunkterne

691
00:56:22,620 --> 00:56:27,900
i main os selv og ledninger dem op til at pege på hinanden som vi gør,

692
00:56:27,900 --> 00:56:30,600
vi stole på vores insert funktion til at gøre det.

693
00:56:30,600 --> 00:56:35,510
Vi vil ikke stole på vores insert funktion til at bygge hele træet fra bunden endnu,

694
00:56:35,510 --> 00:56:39,970
men snarere vi slippe af med disse linjer - we'll udkommentere disse linjer -

695
00:56:39,970 --> 00:56:43,430
der bygger knudepunkterne 5, 8 og 2.

696
00:56:43,430 --> 00:56:55,740
Og i stedet, vil vi indsætte opkald til vores insert funktion

697
00:56:55,740 --> 00:57:01,280
at sikre, at der rent faktisk virker.

698
00:57:01,280 --> 00:57:05,840
Her går vi.

699
00:57:05,840 --> 00:57:09,300
>> Nu har vi kommenteret ud disse linjer.

700
00:57:09,300 --> 00:57:13,700
Vi har kun 7, 3, 9 og 6 i vores træ på dette punkt.

701
00:57:13,700 --> 00:57:18,870
For at sikre at dette er alle arbejder,

702
00:57:18,870 --> 00:57:25,050
vi kan zoome ud, gøre vores binært træ,

703
00:57:25,050 --> 00:57:30,750
køre det, og vi kan se, der indeholder nu fortæller os, at vi er helt rigtigt -

704
00:57:30,750 --> 00:57:33,110
5, 8 og 2 ikke længere i træet.

705
00:57:33,110 --> 00:57:37,960
Gå tilbage ind i koden,

706
00:57:37,960 --> 00:57:41,070
og hvordan skal vi indsætte?

707
00:57:41,070 --> 00:57:46,290
Husk, hvad vi gjorde, da vi var faktisk indsætte 5, 8 og 2 tidligere.

708
00:57:46,290 --> 00:57:50,100
Vi spillede som Plinko spil, hvor vi startede ved roden,

709
00:57:50,100 --> 00:57:52,780
gik ned i træet én efter én efter én

710
00:57:52,780 --> 00:57:54,980
indtil vi fandt det passende hul,

711
00:57:54,980 --> 00:57:57,570
og så har vi kablet i knudepunktet på det rette sted.

712
00:57:57,570 --> 00:57:59,480
Vi vil gøre det samme.

713
00:57:59,480 --> 00:58:04,070
Dette er dybest set ligesom at skrive den kode, som vi brugte i indeholder funktionen

714
00:58:04,070 --> 00:58:05,910
at finde det sted, hvor noden skal være,

715
00:58:05,910 --> 00:58:10,560
og så er vi bare at indsætte node lige der.

716
00:58:10,560 --> 00:58:17,000
Lad os begynde at gøre det.

717
00:58:17,000 --> 00:58:24,200
>> Så vi har en node * cur = rod, vi er bare at følge den indeholder kode

718
00:58:24,200 --> 00:58:26,850
indtil vi finder, at det ikke helt virker for os.

719
00:58:26,850 --> 00:58:32,390
Vi vil gå gennem træet, mens det aktuelle element ikke er nul,

720
00:58:32,390 --> 00:58:45,280
og hvis vi opdager, at nuværende værdi er lig med den værdi, som vi forsøger at indsætte -

721
00:58:45,280 --> 00:58:49,600
godt, det er en af ​​de sager, hvor vi ikke kunne faktisk indsætte node

722
00:58:49,600 --> 00:58:52,730
ind i træet, fordi det betyder, at vi har en dobbelt værdi.

723
00:58:52,730 --> 00:58:59,010
Her vil vi faktisk kommer til at returnere falsk.

724
00:58:59,010 --> 00:59:08,440
Nu, ellers hvis nuværende værdi er mindre end værdien,

725
00:59:08,440 --> 00:59:10,930
nu ved vi, at vi flytter til højre

726
00:59:10,930 --> 00:59:17,190
 fordi værdien hører til i den højre halvdel af cur træet.

727
00:59:17,190 --> 00:59:30,110
Ellers vil vi flytte til venstre.

728
00:59:30,110 --> 00:59:37,980
Det er dybest set vores indeholder funktionsmoduler lige der.

729
00:59:37,980 --> 00:59:41,820
>> På dette tidspunkt, vi engang har fuldført denne while-løkken,

730
00:59:41,820 --> 00:59:47,350
vores nuværende pointer vil blive pege på null

731
00:59:47,350 --> 00:59:51,540
hvis funktionen ikke allerede vendt tilbage.

732
00:59:51,540 --> 00:59:58,710
Vi derfor har cur på det sted, hvor vi ønsker at indsætte den nye node.

733
00:59:58,710 --> 01:00:05,210
Hvad mangler at blive gjort, er at faktisk bygge det nye knudepunkt,

734
01:00:05,210 --> 01:00:08,480
som vi kan gøre temmelig nemt.

735
01:00:08,480 --> 01:00:14,930
Vi kan bruge vores super-handy build node-funktion,

736
01:00:14,930 --> 01:00:17,210
og noget, som vi ikke gjorde tidligere -

737
01:00:17,210 --> 01:00:21,400
vi bare slags tog for givet, men nu skal vi gøre blot at sørge for -

738
01:00:21,400 --> 01:00:27,130
vi vil teste for at sikre, at værdien returneret af ny knude var faktisk

739
01:00:27,130 --> 01:00:33,410
ikke null, fordi vi ikke ønsker at begynde at få adgang til denne hukommelse, hvis det er nul.

740
01:00:33,410 --> 01:00:39,910
Vi kan teste for at sikre, at ny node ikke er lig med nul.

741
01:00:39,910 --> 01:00:42,910
Eller i stedet, kan vi bare se, om det rent faktisk er nul,

742
01:00:42,910 --> 01:00:52,120
og hvis det er nul, så kan vi bare returnere falsk tidligt.

743
01:00:52,120 --> 01:00:59,090
>> På dette tidspunkt er vi nødt til wire ny knude i sit passende sted i træet.

744
01:00:59,090 --> 01:01:03,510
Hvis vi ser tilbage på main og hvor vi faktisk var ledninger i værdier før,

745
01:01:03,510 --> 01:01:08,470
vi se, at den måde, vi gjorde det, da vi ønskede at sætte 3 i træet

746
01:01:08,470 --> 01:01:11,750
blev vi åbnede venstre barn af roden.

747
01:01:11,750 --> 01:01:14,920
Når vi sætter 9 i træet, havde vi at få adgang til højre barn af roden.

748
01:01:14,920 --> 01:01:21,030
Vi skulle have en pointer til den forælder, for at sætte en ny værdi ind i træet.

749
01:01:21,030 --> 01:01:24,430
Rulning tilbage op til at indsætte, er det ikke kommer til at helt at arbejde her

750
01:01:24,430 --> 01:01:27,550
fordi vi ikke har en forælder pointer.

751
01:01:27,550 --> 01:01:31,650
Hvad vi ønsker at være i stand til at gøre, er, på dette tidspunkt,

752
01:01:31,650 --> 01:01:37,080
kontrollere forældrenes værdi og se - ja, gosh,

753
01:01:37,080 --> 01:01:41,990
hvis forældrenes værdi er mindre end den aktuelle værdi,

754
01:01:41,990 --> 01:01:54,440
så den forælder ret barn skulle være den nye knude;

755
01:01:54,440 --> 01:02:07,280
ellers skal den forælder venstre barn være den nye node.

756
01:02:07,280 --> 01:02:10,290
Men vi har ikke denne forælder pointer helt endnu.

757
01:02:10,290 --> 01:02:15,010
>> For at få det, vi faktisk nødt til at spore det, som vi går igennem træet

758
01:02:15,010 --> 01:02:18,440
og finde den rette plads i vores løkke ovenfor.

759
01:02:18,440 --> 01:02:26,840
Det kan vi gøre ved at rulle tilbage op til toppen af ​​vores insert funktion

760
01:02:26,840 --> 01:02:32,350
og sporing anden pointer variabel kaldet moderselskabet.

761
01:02:32,350 --> 01:02:39,340
Vi kommer til at indstille det lig nul i første omgang,

762
01:02:39,340 --> 01:02:43,640
og derefter hver gang vi går igennem træet,

763
01:02:43,640 --> 01:02:51,540
vi kommer til at indstille den forælder pointer til at matche den aktuelle pointer.

764
01:02:51,540 --> 01:02:59,140
Indstil forælder lig med cur.

765
01:02:59,140 --> 01:03:02,260
Denne måde, hver gang vi går igennem,

766
01:03:02,260 --> 01:03:05,550
vi vil sikre, at da den nuværende pointer bliver inkrementeres

767
01:03:05,550 --> 01:03:12,640
moderselskabet pointer følger det - bare et niveau højere end det aktuelle pointer i træet.

768
01:03:12,640 --> 01:03:17,370
At alle ser temmelig godt.

769
01:03:17,370 --> 01:03:22,380
>> Jeg tror, ​​den ene ting, vi har lyst til at justere er dette bygge knude tilbage null.

770
01:03:22,380 --> 01:03:25,380
For at få opbygge node til rent faktisk held returnere null,

771
01:03:25,380 --> 01:03:31,060
vi bliver nødt til at ændre denne kode,

772
01:03:31,060 --> 01:03:37,270
fordi her, vi aldrig testes for at sikre, at malloc returnerede en gyldig pointer.

773
01:03:37,270 --> 01:03:53,390
Så hvis (n = NULL!), Derefter -

774
01:03:53,390 --> 01:03:55,250
hvis malloc returnerede en gyldig pointer, så vil vi initialisere det;

775
01:03:55,250 --> 01:04:02,540
ellers vil vi bare vende tilbage, og det vil ende med at vende tilbage null for os.

776
01:04:02,540 --> 01:04:13,050
Nu er alle ser temmelig godt. Lad os sørge for dette faktisk kompilerer.

777
01:04:13,050 --> 01:04:22,240
Gør binært træ, og åh, vi har nogle ting der foregår her.

778
01:04:22,240 --> 01:04:29,230
>> Vi har fået en implicit erklæring af funktionen bygge node.

779
01:04:29,230 --> 01:04:31,950
Igen med disse compilere, vil vi starte på toppen.

780
01:04:31,950 --> 01:04:36,380
Hvad der må betyde, er, at jeg ringer bygge node, før jeg rent faktisk har erklæret det.

781
01:04:36,380 --> 01:04:37,730
Lad os gå tilbage til den kode virkelig hurtigt.

782
01:04:37,730 --> 01:04:43,510
Rul ned, og ganske rigtigt, min insert funktion der er erklæret

783
01:04:43,510 --> 01:04:47,400
over build node-funktionen,

784
01:04:47,400 --> 01:04:50,070
men jeg forsøger at bruge bygge node inde i indsatsen.

785
01:04:50,070 --> 01:05:06,610
Jeg har tænkt mig at gå ind og kopiere - og derefter indsætte build node-funktionen heroppe på toppen.

786
01:05:06,610 --> 01:05:11,750
På den måde forhåbentlig, der vil arbejde. Lad os give dette en anden gå.

787
01:05:11,750 --> 01:05:18,920
Nu er det hele kompilerer. Alt er godt.

788
01:05:18,920 --> 01:05:21,640
>> Men på dette punkt, har vi faktisk ikke kaldt vores Indsæt funktion.

789
01:05:21,640 --> 01:05:26,510
Vi skal bare vide, at det kompilerer, så lad os gå ind og sætte nogle opkald i.

790
01:05:26,510 --> 01:05:28,240
Lad os gøre det i vores vigtigste funktion.

791
01:05:28,240 --> 01:05:32,390
Her vi udkommenteret 5, 8 og 2,

792
01:05:32,390 --> 01:05:36,680
og så vi ikke wire dem op hernede.

793
01:05:36,680 --> 01:05:41,640
Lad os foretage nogle opkald for at indsætte,

794
01:05:41,640 --> 01:05:46,440
og lad os også bruge den samme slags ting, som vi brugte

795
01:05:46,440 --> 01:05:52,810
når vi gjorde disse printf opkald for at sikre, at alt fik indsat korrekt.

796
01:05:52,810 --> 01:06:00,550
Jeg har tænkt mig at kopiere og indsætte,

797
01:06:00,550 --> 01:06:12,450
og i stedet for indeholder vi vil gøre indsatsen.

798
01:06:12,450 --> 01:06:30,140
Og i stedet for 6, 10, og 1, vi kommer til at bruge 5, 8 og 2.

799
01:06:30,140 --> 01:06:37,320
Dette vil forhåbentlig indsætte 5, 8 og 2 ind i træet.

800
01:06:37,320 --> 01:06:44,050
Kompiler. Alt er godt. Nu vil vi faktisk køre vores program.

801
01:06:44,050 --> 01:06:47,330
>> Alt returneres falsk.

802
01:06:47,330 --> 01:06:53,830
Så har 5, 8 og 2 ikke gå, og det ser ud som indeholder ikke fandt dem heller.

803
01:06:53,830 --> 01:06:58,890
Hvad sker der? Lad os zoome ud.

804
01:06:58,890 --> 01:07:02,160
Det første problem var, at indsatsen syntes at returnere falsk,

805
01:07:02,160 --> 01:07:08,750
og det ser ud det er fordi vi forlod i vores tilbagevenden falsk opkald,

806
01:07:08,750 --> 01:07:14,590
og vi har faktisk aldrig returneres sandt.

807
01:07:14,590 --> 01:07:17,880
Vi kan sætte det op.

808
01:07:17,880 --> 01:07:25,290
Det andet problem er, nu, selv om vi gør - gemme dette, skal du afslutte dette,

809
01:07:25,290 --> 01:07:34,530
køre make igen, har det kompilere, derefter køre det -

810
01:07:34,530 --> 01:07:37,670
vi se, at noget andet er sket her.

811
01:07:37,670 --> 01:07:42,980
The 5, 8 og 2 blev fortsat aldrig fundet i træet.

812
01:07:42,980 --> 01:07:44,350
Så, hvad sker der?

813
01:07:44,350 --> 01:07:45,700
>> Lad os tage et kig på dette i koden.

814
01:07:45,700 --> 01:07:49,790
Lad os se om vi kan finde ud af dette.

815
01:07:49,790 --> 01:07:57,940
Vi starter med den forælder ikke er null.

816
01:07:57,940 --> 01:07:59,510
Vi sætter den aktuelle pointer svarende til roden pointer,

817
01:07:59,510 --> 01:08:04,280
og vi vil arbejde vores vej ned gennem træet.

818
01:08:04,280 --> 01:08:08,650
Hvis den aktuelle node ikke er nul, så ved vi, at vi kan bevæge os ned en lille smule.

819
01:08:08,650 --> 01:08:12,330
Vi sætter vores moderselskab pointer at være lig med den aktuelle pointer,

820
01:08:12,330 --> 01:08:15,420
kontrolleret værdien - hvis værdierne er de samme vi vendte tilbage falsk.

821
01:08:15,420 --> 01:08:17,540
Hvis værdierne er mindre vi flyttede til højre;

822
01:08:17,540 --> 01:08:20,399
ellers, vi flyttet til venstre.

823
01:08:20,399 --> 01:08:24,220
Så bygger vi en node. Jeg vil zoome ind en lille smule.

824
01:08:24,220 --> 01:08:31,410
Og her vil vi forsøge at wire værdierne op til at være den samme.

825
01:08:31,410 --> 01:08:37,250
Hvad sker der? Lad os se om evt Valgrind kan give os et praj.

826
01:08:37,250 --> 01:08:43,910
>> Jeg kan godt lide at bruge Valgrind bare fordi Valgrind virkelig hurtigt kører

827
01:08:43,910 --> 01:08:46,729
og fortæller dig, hvis der er nogen hukommelsesfejl.

828
01:08:46,729 --> 01:08:48,300
Når vi kører Valgrind på koden,

829
01:08:48,300 --> 01:08:55,859
som du kan se til højre here--Valgrind./binary_tree--and tryk enter.

830
01:08:55,859 --> 01:09:03,640
Du ser, at vi ikke har nogen hukommelse fejl, så det ligner alt er okay indtil videre.

831
01:09:03,640 --> 01:09:07,529
Vi har nogle memory leaks, som vi ved, fordi vi ikke er

832
01:09:07,529 --> 01:09:08,910
sker at befri nogen af ​​vores noder.

833
01:09:08,910 --> 01:09:13,050
Lad os prøve at køre GDB at se, hvad der rent faktisk sker.

834
01:09:13,050 --> 01:09:20,010
Vi laver gdb. / Binary_tree. Det startet op fint.

835
01:09:20,010 --> 01:09:23,670
Lad os sætte en break point på insert.

836
01:09:23,670 --> 01:09:28,600
Lad os køre.

837
01:09:28,600 --> 01:09:31,200
Det ser ud som vi faktisk aldrig kaldt insert.

838
01:09:31,200 --> 01:09:39,410
Det ligner problemet var bare, at når jeg skiftede ned her i main -

839
01:09:39,410 --> 01:09:44,279
alle disse printf opkald fra indeholder -

840
01:09:44,279 --> 01:09:56,430
Jeg faktisk aldrig skiftet disse ringe indsats.

841
01:09:56,430 --> 01:10:01,660
Nu lad os give det en chance. Lad os kompilere.

842
01:10:01,660 --> 01:10:09,130
Alle ser godt dér. Lad os nu prøve at køre det, se hvad der sker.

843
01:10:09,130 --> 01:10:13,320
Okay! Alt ser temmelig godt dér.

844
01:10:13,320 --> 01:10:18,130
>> Den sidste ting at tænke på er, er der nogen kant sager til denne indsats?

845
01:10:18,130 --> 01:10:23,170
Og det viser sig, at, ja, det ene kant sag, der er altid interessant at tænke på

846
01:10:23,170 --> 01:10:26,250
er, hvad der sker, hvis dit træ er tom, og du kalder denne insert funktion?

847
01:10:26,250 --> 01:10:30,330
Vil det virke? Nå, lad os give det en chance.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Den måde, vi kommer til at teste dette er, vi kommer til at gå ned til vores vigtigste funktion,

850
01:10:35,810 --> 01:10:41,690
og i stedet for ledningsføring disse knudepunkter op som dette,

851
01:10:41,690 --> 01:10:56,730
vi bare vil kommentere ud hele ting,

852
01:10:56,730 --> 01:11:02,620
og i stedet for kabler op knudepunkterne os selv,

853
01:11:02,620 --> 01:11:09,400
Vi kan faktisk bare gå videre og slette alt dette.

854
01:11:09,400 --> 01:11:17,560
Vi vil gøre alt et opkald for at indsætte.

855
01:11:17,560 --> 01:11:49,020
Så lad os gøre - i stedet for 5, 8 og 2, vil vi indsætte 7, 3, og 9.

856
01:11:49,020 --> 01:11:58,440
Og så vil vi også ønsker at indsætte 6 samt.

857
01:11:58,440 --> 01:12:05,190
Gem. Afslut. Gør binært træ.

858
01:12:05,190 --> 01:12:08,540
Det hele kompilerer.

859
01:12:08,540 --> 01:12:10,320
Vi kan bare køre det som det er, og se hvad der sker,

860
01:12:10,320 --> 01:12:12,770
men det er også vil være virkelig vigtigt at sikre, at

861
01:12:12,770 --> 01:12:14,740
vi ikke har nogen hukommelse fejl,

862
01:12:14,740 --> 01:12:16,840
da dette er et af vores edge sager, vi kender til.

863
01:12:16,840 --> 01:12:20,150
>> Lad os sørge for, at det fungerer godt under Valgrind,

864
01:12:20,150 --> 01:12:28,310
som vi vil gøre ved bare at køre Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Det ser ud til at vi faktisk har en fejl fra én sammenhæng -

866
01:12:31,110 --> 01:12:33,790
vi har denne segmentering fejl.

867
01:12:33,790 --> 01:12:36,690
Hvad er der sket?

868
01:12:36,690 --> 01:12:41,650
Valgrind faktisk fortæller os, hvor det er.

869
01:12:41,650 --> 01:12:43,050
Zoom ud en lille smule.

870
01:12:43,050 --> 01:12:46,040
Det ser ud som det sker i vores insert funktion,

871
01:12:46,040 --> 01:12:53,420
hvor vi har et ugyldigt læst af størrelse 4 ved insert, linie 60.

872
01:12:53,420 --> 01:13:03,590
Lad os gå tilbage og se, hvad der foregår her.

873
01:13:03,590 --> 01:13:05,350
Zoom ud virkelig hurtig.

874
01:13:05,350 --> 01:13:14,230
Jeg vil være sikker på, at det ikke går ud til kanten af ​​skærmen, så vi kan se alt.

875
01:13:14,230 --> 01:13:18,760
Træk, at der i en lille smule. Alright.

876
01:13:18,760 --> 01:13:35,030
Rul ned, og problemet er lige her.

877
01:13:35,030 --> 01:13:40,120
Hvad sker der, hvis vi får ned og vores nuværende node er allerede null,

878
01:13:40,120 --> 01:13:44,010
vores moderselskab node er null, så hvis vi ser op på toppen, lige her -

879
01:13:44,010 --> 01:13:47,340
hvis denne while-løkke faktisk aldrig udfører

880
01:13:47,340 --> 01:13:52,330
fordi vores nuværende værdi er null - vores rod er nul så cur er null -

881
01:13:52,330 --> 01:13:57,810
så vores moderselskab aldrig bliver sat til cur eller til en gyldig værdi,

882
01:13:57,810 --> 01:14:00,580
så vil forældrene også være null.

883
01:14:00,580 --> 01:14:03,700
Vi skal huske at tjekke for det

884
01:14:03,700 --> 01:14:08,750
med den tid, vi kommer herned, og vi begynder at få adgang til moderselskabets værdi.

885
01:14:08,750 --> 01:14:13,190
Så, hvad sker der? Tja, hvis moderselskabet er null -

886
01:14:13,190 --> 01:14:17,990
if (forælder == NULL) - så ved vi, at

887
01:14:17,990 --> 01:14:19,530
der må ikke være noget i træet.

888
01:14:19,530 --> 01:14:22,030
Vi skal forsøge at indsætte det ved roden.

889
01:14:22,030 --> 01:14:32,570
Det kan vi gøre ved blot at sætte rod lig med den nye node.

890
01:14:32,570 --> 01:14:40,010
Så på dette punkt, vi faktisk ikke ønsker at gå gennem disse andre ting.

891
01:14:40,010 --> 01:14:44,780
I stedet, lige her, kan vi gøre enten en else-if-else,

892
01:14:44,780 --> 01:14:47,610
eller vi kunne kombinere alt op her i en ellers,

893
01:14:47,610 --> 01:14:56,300
men her vil vi bare bruge andet og gøre det på den måde.

894
01:14:56,300 --> 01:14:59,030
Nu vil vi teste for at sikre, at vores moderselskab ikke er nul

895
01:14:59,030 --> 01:15:02,160
inden da faktisk forsøger at få adgang til sine marker.

896
01:15:02,160 --> 01:15:05,330
Dette vil hjælpe os til at undgå segmenteringsfejl.

897
01:15:05,330 --> 01:15:14,740
Så vi holde op, zoome ud, kompilere, løbe.

898
01:15:14,740 --> 01:15:18,130
>> Ingen fejl, men vi har stadig en masse memory leaks

899
01:15:18,130 --> 01:15:20,650
fordi vi ikke befri nogen af ​​vores noder.

900
01:15:20,650 --> 01:15:24,350
Men hvis vi går op her, og vi ser på vores udskrift,

901
01:15:24,350 --> 01:15:30,880
vi se, at, ja, ligner alle vores insertioner blev tilbage sand, hvilket er godt.

902
01:15:30,880 --> 01:15:33,050
Skærene er alle sande,

903
01:15:33,050 --> 01:15:36,670
og derefter de relevante indeholder opkald er også sandt.

904
01:15:36,670 --> 01:15:41,510
>> Godt arbejde! Det ser ud som vi med succes har skrevet insert.

905
01:15:41,510 --> 01:15:47,430
Det er alt vi har for denne uges Problem Set Specification.

906
01:15:47,430 --> 01:15:51,720
En sjov udfordring at tænke på er, hvordan du rent faktisk ville gå i

907
01:15:51,720 --> 01:15:55,340
og fri alle knuder i dette træ.

908
01:15:55,340 --> 01:15:58,830
Vi kan gøre en række forskellige måder,

909
01:15:58,830 --> 01:16:01,930
men jeg vil overlade det op til dig at eksperimentere,

910
01:16:01,930 --> 01:16:06,080
og som en sjov udfordring, så prøv og sørg for, at du kan sørge for

911
01:16:06,080 --> 01:16:09,490
at denne Valgrind rapporten returnerer ingen fejl og ingen utætheder.

912
01:16:09,490 --> 01:16:12,880
>> Held og lykke på denne uges Huffman kodning problem sæt,

913
01:16:12,880 --> 01:16:14,380
og vi vil se dig i næste uge!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]