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

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
Takk til orkan Sandy,

6
00:00:11,330 --> 00:00:13,440
stedet for å ha en normal seksjon denne uken,

7
00:00:13,440 --> 00:00:17,650
vi gjør dette walk-through, gjennom den delen av spørsmål.

8
00:00:17,650 --> 00:00:22,830
Jeg kommer til å følge sammen med oppgavesettet 6 Spesifikasjon,

9
00:00:22,830 --> 00:00:25,650
og gå gjennom alle spørsmålene i

10
00:00:25,650 --> 00:00:27,770
En seksjon av spørsmål delen.

11
00:00:27,770 --> 00:00:30,940
Hvis det er noen spørsmål,

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

13
00:00:32,960 --> 00:00:35,480
>> Alright. La oss komme i gang.

14
00:00:35,480 --> 00:00:40,780
Akkurat nå er jeg ser på side 3 av oppgavesettet Specification.

15
00:00:40,780 --> 00:00:44,110
Vi skal først begynne å snakke om binære trær

16
00:00:44,110 --> 00:00:47,850
siden de har mye relevans til denne ukens problem set -

17
00:00:47,850 --> 00:00:49,950
den Huffman Tre koding.

18
00:00:49,950 --> 00:00:55,000
En av de aller første datastrukturer vi snakket om på CS50 var tabellen.

19
00:00:55,000 --> 00:01:00,170
Husk at en matrise er en sekvens av elementer -

20
00:01:00,170 --> 00:01:04,019
alle av samme type - lagret rett ved siden av hverandre i minnet.

21
00:01:04,019 --> 00:01:14,420
Hvis jeg har et heltall matrise som jeg kan tegne med dette bokser-nummer-heltall stil -

22
00:01:14,420 --> 00:01:20,290
Si la oss har jeg 5 i den første boksen, jeg har 7 i den andre,

23
00:01:20,290 --> 00:01:27,760
da har jeg 8, 10, og 20 i den endelige boksen.

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

25
00:01:33,000 --> 00:01:38,800
er at vi har dette konstant tid tilgang til noen bestemt element

26
00:01:38,800 --> 00:01:40,500
 i rekken hvis vi vet sin indeks.

27
00:01:40,500 --> 00:01:44,670
For eksempel, hvis jeg ønsker å ta tak i tredje elementet i matrisen -

28
00:01:44,670 --> 00:01:47,870
på indeksen 2 ved hjelp av vår null-indeksering system -

29
00:01:47,870 --> 00:01:52,220
Jeg bokstavelig talt bare nødt til å gjøre en enkel matematisk beregning,

30
00:01:52,220 --> 00:01:56,170
hoppe til den posisjonen i matrisen,

31
00:01:56,170 --> 00:01:57,840
trekke ut 8 som er lagret der,

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

33
00:01:59,260 --> 00:02:03,350
>> En av de dårlige tingene om denne tabellen - som vi snakket om

34
00:02:03,350 --> 00:02:05,010
når vi diskuterte knyttet lister -

35
00:02:05,010 --> 00:02:09,120
er at hvis jeg ønsker å sette et element i denne matrisen,

36
00:02:09,120 --> 00:02:11,090
Jeg kommer til å gjøre noen flytter rundt.

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

38
00:02:12,940 --> 00:02:16,850
er i sortert rekkefølge - sorteres i stigende rekkefølge -

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

40
00:02:19,440 --> 00:02:23,100
men hvis jeg ønsker å sette inn tallet 9 i denne matrisen,

41
00:02:23,100 --> 00:02:27,460
Jeg kommer til å skifte noen av elementene for å gjøre plass.

42
00:02:27,460 --> 00:02:30,440
Vi kan trekke ut av dette her.

43
00:02:30,440 --> 00:02:35,650
Jeg kommer til å flytte 5, den 7, og deretter 8;

44
00:02:35,650 --> 00:02:38,720
skape et gap der jeg kan sette 9,

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

46
00:02:45,910 --> 00:02:49,450
Dette er en slags smerte fordi i verste fall -

47
00:02:49,450 --> 00:02:54,350
når vi har å sette enten i begynnelsen eller på slutten

48
00:02:54,350 --> 00:02:56,040
av tabellen, avhengig av hvor vi skifter -

49
00:02:56,040 --> 00:02:58,850
Vi kan ende opp med å skifte alle elementene

50
00:02:58,850 --> 00:03:00,750
som vi for tiden lagring i rekken.

51
00:03:00,750 --> 00:03:03,810
>> Så, hva var vei rundt dette?

52
00:03:03,810 --> 00:03:09,260
Veien rundt dette var å gå til vår koblet-liste metode der -

53
00:03:09,260 --> 00:03:19,820
stedet for å lagre elementene 5, 7, 8, 10 og 20 alle ved siden av hverandre i minne -

54
00:03:19,820 --> 00:03:25,630
hva vi i stedet gjorde var lagre dem slags uansett hvor vi ønsket å lagre dem

55
00:03:25,630 --> 00:03:32,470
i disse lenket liste noder som jeg tegner her ute, type ad hoc.

56
00:03:32,470 --> 00:03:42,060
Og da vi koblet dem sammen ved hjelp av disse neste pekere.

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

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

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

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

61
00:03:51,220 --> 00:03:54,880
og deretter en nullpeker på 20 indikerer at det er ingenting igjen.

62
00:03:54,880 --> 00:03:59,690
Trade-off som vi har her

63
00:03:59,690 --> 00:04:05,360
er at nå hvis vi ønsker å sette inn tallet 9 i vår sortert liste,

64
00:04:05,360 --> 00:04:08,270
alt vi trenger å gjøre er å opprette en ny node med 9,

65
00:04:08,270 --> 00:04:12,290
wire det opp til å peke til riktig sted,

66
00:04:12,290 --> 00:04:20,630
og deretter re-ledning 8 til peke ned til 9.

67
00:04:20,630 --> 00:04:25,660
Det er ganske fort, forutsatt at vi vet nøyaktig hvor vi vil sette inn 9.

68
00:04:25,660 --> 00:04:32,610
Men trade-off i bytte for dette er at vi nå har mistet konstant-time tilgang

69
00:04:32,610 --> 00:04:36,230
til noen bestemt element i vår datastruktur.

70
00:04:36,230 --> 00:04:40,950
For eksempel, hvis jeg ønsker å finne det fjerde elementet i denne lenket liste,

71
00:04:40,950 --> 00:04:43,510
Jeg kommer til å starte på begynnelsen av listen

72
00:04:43,510 --> 00:04:48,930
og jobbe meg gjennom telling node-by-node før jeg finner den fjerde.

73
00:04:48,930 --> 00:04:55,870
>> For å få bedre tilgang ytelse enn en lenket liste -

74
00:04:55,870 --> 00:04:59,360
men også beholde noen av fordelene som vi hadde

75
00:04:59,360 --> 00:05:01,800
i form av innsetting-tid fra en lenket liste -

76
00:05:01,800 --> 00:05:05,750
et binært tre er nødt til å bruke litt mer minne.

77
00:05:05,750 --> 00:05:11,460
Spesielt, i stedet for bare å ha en pekeren i et binært tre node -

78
00:05:11,460 --> 00:05:13,350
som den koblede-listen node gjør -

79
00:05:13,350 --> 00:05:16,950
Vi kommer til å legge en ny peker til binærtreet node.

80
00:05:16,950 --> 00:05:19,950
Snarere enn bare å ha en peker til neste element,

81
00:05:19,950 --> 00:05:24,420
Vi kommer til å ha en peker til en venstre barn og høyre barn.

82
00:05:24,420 --> 00:05:26,560
>> La oss tegne et bilde for å se hva som faktisk ser ut.

83
00:05:26,560 --> 00:05:31,350
Igjen, jeg kommer til å bruke disse bokser og piler.

84
00:05:31,350 --> 00:05:37,150
En binær tre node vil starte med bare en enkel boks.

85
00:05:37,150 --> 00:05:40,940
Det kommer til å ha en plass for verdien,

86
00:05:40,940 --> 00:05:47,280
og da er det også kommer til å ha en plass for venstre barn og høyre barnet.

87
00:05:47,280 --> 00:05:49,280
Jeg kommer til å merke dem her.

88
00:05:49,280 --> 00:05:57,560
Vi kommer til å ha venstre barnet, og da vi kommer til å ha den rette barnet.

89
00:05:57,560 --> 00:05:59,920
Det er mange forskjellige måter å gjøre dette.

90
00:05:59,920 --> 00:06:02,050
Noen ganger for plass og komfort,

91
00:06:02,050 --> 00:06:06,460
Jeg vil faktisk trekke det ut som jeg gjør her på bunnen

92
00:06:06,460 --> 00:06:10,910
hvor jeg kommer til å ha verdien på toppen,

93
00:06:10,910 --> 00:06:14,060
og deretter høyre barnet på nederst til høyre,

94
00:06:14,060 --> 00:06:16,060
og venstre barnet på nederste venstre.

95
00:06:16,060 --> 00:06:20,250
Gå tilbake til denne toppdiagrammet,

96
00:06:20,250 --> 00:06:22,560
Vi har verdien på toppen,

97
00:06:22,560 --> 00:06:25,560
så har vi den venstre barnet peker, og så har vi rett-barn pekeren.

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

99
00:06:30,110 --> 00:06:33,110
vi snakker om å tegne en node som har en verdi 7,

100
00:06:33,110 --> 00:06:39,750
og deretter en venstre-barn peker som er null, og en høyre-barn peker som er null.

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

102
00:06:46,040 --> 00:06:51,610
både venstre barnet og rett barnet, eller vi kan trekke denne diagonal strek

103
00:06:51,610 --> 00:06:53,750
gjennom hver av boksene for å indikere at det er null.

104
00:06:53,750 --> 00:06:57,560
Jeg kommer til å gjøre det bare fordi det er enklere.

105
00:06:57,560 --> 00:07:03,700
Hva du ser her er to måter å diagramfunksjonen en veldig enkel binærtreet node

106
00:07:03,700 --> 00:07:07,960
hvor vi har verdien 7 og null barn pekere.

107
00:07:07,960 --> 00:07:15,220
>> Den andre delen av våre spesifikasjoner snakker om hvordan med koblede lister -

108
00:07:15,220 --> 00:07:18,270
Husk, vi bare måtte holde på den aller første element i en liste

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

110
00:07:20,270 --> 00:07:26,140
og likeledes med en binær tre, vi bare nødt til å holde på til en peker til treet

111
00:07:26,140 --> 00:07:31,120
for å opprettholde kontroll over hele datastrukturen.

112
00:07:31,120 --> 00:07:36,150
Denne spesielt element av treet kalles rotnoden av treet.

113
00:07:36,150 --> 00:07:43,360
For eksempel, hvis denne en node - denne noden som inneholder verdien 7

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

115
00:07:45,500 --> 00:07:47,360
var den eneste verdien i treet vårt,

116
00:07:47,360 --> 00:07:50,390
da dette ville være vår rotnoden.

117
00:07:50,390 --> 00:07:52,240
Det er helt i begynnelsen av treet vårt.

118
00:07:52,240 --> 00:07:58,530
Vi kan se dette litt mer tydelig når vi begynner å legge flere noder til treet vårt.

119
00:07:58,530 --> 00:08:01,510
La meg trekke opp en ny side.

120
00:08:01,510 --> 00:08:05,000
>> Nå skal vi tegne et tre som har 7 ved roten,

121
00:08:05,000 --> 00:08:10,920
og 3 innsiden av venstre barnet, og 9 innsiden av høyre barnet.

122
00:08:10,920 --> 00:08:13,500
Igjen, dette er ganske enkel.

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 kommer til å sette venstre barnet peker på 7 for å peke på noden som inneholder 3,

125
00:08:32,150 --> 00:08:37,850
og rett-barnet pekeren til noden som inneholder 7 til noden inneholder 9.

126
00:08:37,850 --> 00:08:42,419
Nå, siden 3 og 9 ikke har noen barn,

127
00:08:42,419 --> 00:08:48,500
vi kommer til å sette alle sine barn pekere til å være null.

128
00:08:48,500 --> 00:08:56,060
Her svarer roten av treet vårt til noden som inneholder antall 7.

129
00:08:56,060 --> 00:09:02,440
Du kan se at hvis alt vi har er en peker til at rotnoden,

130
00:09:02,440 --> 00:09:07,330
Vi kan da gå gjennom treet vårt og tilgang 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
Du trenger ikke å opprettholde pekere til hver enkelt node på treet.

133
00:09:14,820 --> 00:09:22,080
Alright. Nå skal vi legge til en annen node i dette diagrammet.

134
00:09:22,080 --> 00:09:25,370
Vi kommer til å legge en node som inneholder 6,

135
00:09:25,370 --> 00:09:34,140
og vi kommer til å legge dette som retten barnet til noden som inneholder 3.

136
00:09:34,140 --> 00:09:41,850
For å gjøre det, kommer jeg til å slette den nullpeker i 3-node

137
00:09:41,850 --> 00:09:47,750
og wire det opp til å peke på noden som inneholder seks. Alright.

138
00:09:47,750 --> 00:09:53,800
>> På dette punktet, la oss gå over en liten bit av terminologi.

139
00:09:53,800 --> 00:09:58,230
Hvis du vil starte, grunnen til at dette kalles en binær tre i særdeleshet

140
00:09:58,230 --> 00:10:00,460
er at den har to barn pekere.

141
00:10:00,460 --> 00:10:06,020
Det finnes andre typer trær som har flere barn pekere.

142
00:10:06,020 --> 00:10:10,930
Spesielt, du gjorde en "prøve" i oppgave Set 5.

143
00:10:10,930 --> 00:10:19,310
Du vil merke at i det prøve, hadde du 27 forskjellige pekere til forskjellige barn -

144
00:10:19,310 --> 00:10:22,410
en for hver av de 26 bokstavene i det engelske alfabetet,

145
00:10:22,410 --> 00:10:25,410
og deretter den 27. for apostrof -

146
00:10:25,410 --> 00:10:28,900
Så, det er lik en type tre.

147
00:10:28,900 --> 00:10:34,070
Men her, siden det er binært, vi har bare to barn pekere.

148
00:10:34,070 --> 00:10:37,880
>> I tillegg til dette rotnode som vi snakket om,

149
00:10:37,880 --> 00:10:41,470
Vi har også vært å kaste rundt dette begrepet barnet.

150
00:10:41,470 --> 00:10:44,470
Hva betyr det for en node å være barn av en annen node?

151
00:10:44,470 --> 00:10:54,060
Det betyr bokstavelig talt at et barn node er et barn av en annen node

152
00:10:54,060 --> 00:10:58,760
hvis det andre node har en av sine underordnede pekere satt til å peke til den noden.

153
00:10:58,760 --> 00:11:01,230
For å sette dette inn i mer konkrete termer,

154
00:11:01,230 --> 00:11:11,170
hvis 3 fremheves av en av de underordnede pekere på 7, og deretter 3 er et barn av 7.

155
00:11:11,170 --> 00:11:14,510
Hvis vi skulle finne ut hva barn 7 er -

156
00:11:14,510 --> 00:11:18,510
vel, ser vi at 7 har en peker til 3 og en peker til 9,

157
00:11:18,510 --> 00:11:22,190
så 9 og 3 er barn av 7.

158
00:11:22,190 --> 00:11:26,650
Ni har ingen barn fordi underordnede pekere er null,

159
00:11:26,650 --> 00:11:30,940
og 3 har bare ett barn, 6.

160
00:11:30,940 --> 00:11:37,430
Seks har heller ingen barn fordi begge sine pekere er null, som vi vil trekke akkurat nå.

161
00:11:37,430 --> 00:11:45,010
>> I tillegg har vi også snakke om foreldrene til en bestemt node,

162
00:11:45,010 --> 00:11:51,100
og dette er, som du forventer, det motsatte av dette barnet beskrivelse.

163
00:11:51,100 --> 00:11:58,620
Hver node har bare én forelder - i stedet for to som du kanskje forventer med mennesker.

164
00:11:58,620 --> 00:12:03,390
For eksempel er den overordnede av 3 7.

165
00:12:03,390 --> 00:12:10,800
Foreldre av 9 er også 7, og den overordnede av 6 er 3. Ikke mye til det.

166
00:12:10,800 --> 00:12:15,720
Vi har også vilkår for å snakke om besteforeldre og barnebarn,

167
00:12:15,720 --> 00:12:18,210
og mer generelt snakker vi om forfedrene

168
00:12:18,210 --> 00:12:20,960
og etterkommere av en bestemt node.

169
00:12:20,960 --> 00:12:25,710
Stamfar en node - eller forfedre, snarere av en node -

170
00:12:25,710 --> 00:12:32,730
er alle nodene som ligger på banen fra roten til noden.

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

172
00:12:36,640 --> 00:12:46,430
da forfedrene kommer til å være både 3 og 7.

173
00:12:46,430 --> 00:12:55,310
Forfedrene til 9, for eksempel, er - hvis jeg ser på noden 9 -

174
00:12:55,310 --> 00:12:59,990
da stamfar 9 er bare 7.

175
00:12:59,990 --> 00:13:01,940
Og etterkommere er nøyaktig det motsatte.

176
00:13:01,940 --> 00:13:05,430
Hvis jeg ønsker å se på alle etterkommere av 7,

177
00:13:05,430 --> 00:13:11,020
så jeg må se på alle nodene under den.

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

179
00:13:16,950 --> 00:13:24,170
>> Den endelige begrep som vi skal snakke om er denne forestillingen om å være et søsken.

180
00:13:24,170 --> 00:13:27,980
Søsken - type følge med på disse familiemedlemmene vilkår -

181
00:13:27,980 --> 00:13:33,150
er noder som er på samme nivå i treet.

182
00:13:33,150 --> 00:13:42,230
Så, 3 og 9 er søsken fordi de er på samme nivå i treet.

183
00:13:42,230 --> 00:13:46,190
De begge har samme overordnede, 7.

184
00:13:46,190 --> 00:13:51,400
Den 6 har ingen søsken fordi 9 ikke har noen barn.

185
00:13:51,400 --> 00:13:55,540
Og 7 ikke har noen søsken fordi det er roten av treet vårt,

186
00:13:55,540 --> 00:13:59,010
og det er bare noen gang en rot.

187
00:13:59,010 --> 00:14:02,260
For 7 for å ha søsken det måtte være en node over 7.

188
00:14:02,260 --> 00:14:07,480
Det må være en forelder av 7, i hvilket tilfelle 7 ville ikke lenger være roten av treet.

189
00:14:07,480 --> 00:14:10,480
Så at ny forelder av 7 ville også ha et barn,

190
00:14:10,480 --> 00:14:16,480
og at barnet ville da være søsken av 7.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Flytte på.

192
00:14:21,040 --> 00:14:24,930
Da vi startet vår diskusjon av binære trær,

193
00:14:24,930 --> 00:14:28,790
Vi snakket om hvordan vi skulle bruke dem til

194
00:14:28,790 --> 00:14:32,800
få en fordel over begge arrays og koblede lister.

195
00:14:32,800 --> 00:14:37,220
Og måten vi skal gjøre det på er med dette bestiller eiendom.

196
00:14:37,220 --> 00:14:41,080
Vi sier at en binær treet er bestilt, i henhold til spesifikasjonen,

197
00:14:41,080 --> 00:14:45,740
hvis for hver node i treet vårt, alle sine etterkommere til venstre -

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

199
00:14:48,670 --> 00:14:54,510
har mindre verdier, og alle nodene i høyre -

200
00:14:54,510 --> 00:14:57,770
rett barnet og alle høyre barnets etterkommere -

201
00:14:57,770 --> 00:15:02,800
har noder større enn verdien av gjeldende node som vi ser på.

202
00:15:02,800 --> 00:15:07,850
Bare for enkelhet, vi kommer til å anta at det ikke er noen dupliserte noder i treet vårt.

203
00:15:07,850 --> 00:15:11,180
For eksempel, i dette treet ikke vi kommer til å behandle saken

204
00:15:11,180 --> 00:15:13,680
hvor vi har verdien 7 ved roten

205
00:15:13,680 --> 00:15:16,720
 og da har vi også ha verdi 7 andre steder i treet.

206
00:15:16,720 --> 00:15:24,390
I dette tilfellet, vil du legge merke til at dette treet er faktisk bestilt.

207
00:15:24,390 --> 00:15:26,510
Vi har verdien 7 ved roten.

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 angre alle disse små merkene 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 verdiene er begge mindre enn 7, og alt til høyre - som er nettopp dette 9 -

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

213
00:15:53,450 --> 00:15:58,650
>> Dette er ikke den eneste bestilles treet inneholder disse verdiene,

214
00:15:58,650 --> 00:16:03,120
men la oss trekke noen flere av dem.

215
00:16:03,120 --> 00:16:05,030
Det er faktisk en hel haug med måter som vi kan gjøre dette.

216
00:16:05,030 --> 00:16:09,380
Jeg kommer til å bruke en kortform bare for å holde ting enkelt hvor -

217
00:16:09,380 --> 00:16:11,520
stedet for å trekke ut hele bokser-og-piler -

218
00:16:11,520 --> 00:16:14,220
Jeg bare kommer til å trekke tallene og legge til piler som forbinder dem.

219
00:16:14,220 --> 00:16:22,920
Å starte, vi vil bare skrive vår opprinnelige treet igjen der vi hadde 7, og deretter en 3,

220
00:16:22,920 --> 00:16:25,590
og deretter 3 pekte tilbake til høyre til 6,

221
00:16:25,590 --> 00:16:30,890
og 7 hadde rett barn som var 9.

222
00:16:30,890 --> 00:16:33,860
Alright. Hva er en annen måte at vi kunne skrive dette treet?

223
00:16:33,860 --> 00:16:38,800
Stedet for å ha tre være venstre barnet av 7,

224
00:16:38,800 --> 00:16:41,360
vi kan også ha 6 være den venstre barnet av 7,

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

226
00:16:44,470 --> 00:16:48,520
Det ville se ut som dette treet rett her hvor jeg har fått 7,

227
00:16:48,520 --> 00:16:57,860
deretter 6, deretter 3, og en 9 på høyre side.

228
00:16:57,860 --> 00:17:01,490
Vi har heller ikke til å ha 7 som vår rotnoden.

229
00:17:01,490 --> 00:17:03,860
Vi kunne også ha 6 som vår rotnoden.

230
00:17:03,860 --> 00:17:06,470
Hva ville det se ut?

231
00:17:06,470 --> 00:17:09,230
Hvis vi skal opprettholde denne bestilles eiendom,

232
00:17:09,230 --> 00:17:12,970
alt til venstre for de 6 må være mindre enn den.

233
00:17:12,970 --> 00:17:16,540
Det er bare én mulighet, og det er tre.

234
00:17:16,540 --> 00:17:19,869
Men da som riktig barn av 6, har vi to muligheter.

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

236
00:17:25,380 --> 00:17:28,850
eller vi kan tegne det - som jeg er i ferd med å gjøre her -

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

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

239
00:17:39,050 --> 00:17:44,240
>> Nå, 7 og 6 er ikke de eneste mulige verdier for roten.

240
00:17:44,240 --> 00:17:50,200
Vi kunne også ha tre være på roten.

241
00:17:50,200 --> 00:17:52,240
Hva skjer hvis 3 er ved roten?

242
00:17:52,240 --> 00:17:54,390
Her, det blir litt interessant.

243
00:17:54,390 --> 00:17:58,440
Tre ikke har noen verdier som er mindre enn det,

244
00:17:58,440 --> 00:18:02,070
slik at hele venstre side av treet er bare kommer til å være null.

245
00:18:02,070 --> 00:18:03,230
Det er ikke til å være noe der.

246
00:18:03,230 --> 00:18:07,220
Til høyre kan vi liste ting i stigende rekkefølge.

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

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

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

250
00:18:35,020 --> 00:18:40,950
Eller, 3, 7 - faktisk nei, vi kan ikke gjøre en 7 lenger.

251
00:18:40,950 --> 00:18:43,330
Det er vår eneste der.

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

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

254
00:19:06,980 --> 00:19:12,490
>> En ting å trekke oppmerksomheten din til her er

255
00:19:12,490 --> 00:19:14,510
at disse trærne er litt merkelig utseende.

256
00:19:14,510 --> 00:19:17,840
Spesielt hvis vi ser på de fire trærne på høyre side -

257
00:19:17,840 --> 00:19:20,930
Jeg skal sirkle dem, her -

258
00:19:20,930 --> 00:19:28,410
disse trærne ser nesten akkurat ut som en lenket liste.

259
00:19:28,410 --> 00:19:32,670
Hver node har bare ett barn,

260
00:19:32,670 --> 00:19:38,950
og slik at vi ikke har noe av dette trelignende struktur som vi ser, for eksempel,

261
00:19:38,950 --> 00:19:44,720
 i dette en ensom treet over her nederst til venstre.

262
00:19:44,720 --> 00:19:52,490
Disse trærne er faktisk kalt degenerert binære trær,

263
00:19:52,490 --> 00:19:54,170
og vi skal snakke om disse mer i fremtiden -

264
00:19:54,170 --> 00:19:56,730
spesielt hvis du går på å ta andre informatikk kurs.

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

266
00:19:59,670 --> 00:20:03,780
De er ikke veldig nyttig fordi, ja, gir denne strukturen selv

267
00:20:03,780 --> 00:20:08,060
 å slå ganger ligner den av en lenket liste.

268
00:20:08,060 --> 00:20:13,050
Vi får ikke til å dra nytte av den ekstra minne - denne ekstra spisser -

269
00:20:13,050 --> 00:20:18,840
på grunn av strukturen vår er dårlig på denne måten.

270
00:20:18,840 --> 00:20:24,700
Snarere enn å gå på og trekke ut de binære trær som har 9 ved roten,

271
00:20:24,700 --> 00:20:27,220
som er den siste tilfelle at vi ville ha,

272
00:20:27,220 --> 00:20:32,380
vi er i stedet, på dette punktet, kommer til å snakke litt om dette andre uttrykket

273
00:20:32,380 --> 00:20:36,150
at vi bruker når vi snakker om trær, som kalles høyden.

274
00:20:36,150 --> 00:20:45,460
>> Høyden av et tre er avstanden fra roten til den mest-fjern node,

275
00:20:45,460 --> 00:20:48,370
eller snarere antall hopp som du ville ha å gjøre for å

276
00:20:48,370 --> 00:20:53,750
starte fra roten og deretter ende opp på den mest fjerntliggende node i treet.

277
00:20:53,750 --> 00:20:57,330
Hvis vi ser på noen av disse trærne som vi har trukket akkurat her,

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

279
00:21:07,870 --> 00:21:14,510
da må vi gjøre en hop for å komme til 6, en andre hopp for å komme til 7,

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

281
00:21:20,560 --> 00:21:26,120
Så, er høyden på dette treet 3.

282
00:21:26,120 --> 00:21:30,640
Vi kan gjøre den samme øvelsen for de andre trærne skissert med denne grønne,

283
00:21:30,640 --> 00:21:40,100
og vi ser at høyden av alle disse trærne er også faktisk tre.

284
00:21:40,100 --> 00:21:45,230
Det er en del av det som gjør dem utarte -

285
00:21:45,230 --> 00:21:53,750
at deres høyde er bare en mindre enn antall noder i hele treet.

286
00:21:53,750 --> 00:21:58,400
Hvis vi ser på dette andre tre som er omkranset med rød, på den annen side,

287
00:21:58,400 --> 00:22:03,920
vi ser at de mest-fjernt løvnodene er 6 og 9 -

288
00:22:03,920 --> 00:22:06,940
bladene er disse nodene som ikke har barn.

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

290
00:22:11,760 --> 00:22:17,840
Vi har å gjøre ett hopp for å komme til 7 og deretter en andre hop for å komme til 9,

291
00:22:17,840 --> 00:22:21,240
og likeledes, til bare en andre hopp fra 7 komme til 6.

292
00:22:21,240 --> 00:22:29,080
Så, er høyden på dette treet over her bare 2.

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

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

295
00:22:37,480 --> 00:22:42,500
og du vil finne at høyden på alle disse trærne er også to.

296
00:22:42,500 --> 00:22:46,320
>> Grunnen til at vi har snakket om bestilte binære trær

297
00:22:46,320 --> 00:22:50,250
og hvorfor de er kule er fordi du kan søke gjennom dem i

298
00:22:50,250 --> 00:22:53,810
en svært lik måte å søke over en sortert array.

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

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

301
00:23:02,730 --> 00:23:05,010
Med en lenket liste - hvis du ønsker å finne et bestemt element -

302
00:23:05,010 --> 00:23:07,470
du er i beste fall kommer til å gjøre noen form for lineær søk

303
00:23:07,470 --> 00:23:10,920
hvor du starter i begynnelsen av en liste og hop en etter en -

304
00:23:10,920 --> 00:23:12,620
en node ved en node -

305
00:23:12,620 --> 00:23:16,060
gjennom hele listen til du finner det du leter etter.

306
00:23:16,060 --> 00:23:19,440
Mens hvis du har en binær tre som er lagret i denne hyggelig format,

307
00:23:19,440 --> 00:23:23,300
du kan faktisk få mer av et binært søk skjer

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

309
00:23:25,160 --> 00:23:29,490
og søke gjennom den riktige halvdel av treet på hvert trinn.

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

311
00:23:32,840 --> 00:23:38,850
>> Hvis vi har - igjen, gå tilbake til vårt opprinnelige treet -

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

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

314
00:23:51,740 --> 00:24:01,880
Hvis vi ønsker å søke etter nummer 6 i dette treet, ville vi begynne ved roten.

315
00:24:01,880 --> 00:24:08,910
Vi vil sammenligne verdien vi leter etter, sier 6,

316
00:24:08,910 --> 00:24:12,320
til verdien lagret i noden som vi for tiden ser på, 7,

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

318
00:24:21,200 --> 00:24:25,530
Hvis verdien av 6 hadde vært større enn 7, ville vi ha flyttet istedet til høyre.

319
00:24:25,530 --> 00:24:29,770
Siden vi vet at - på grunn av strukturen i vårt bestilt binærtreet -

320
00:24:29,770 --> 00:24:33,910
alle verdier mindre enn 7 kommer til å bli lagret på venstre side av 7,

321
00:24:33,910 --> 00:24:40,520
det er ikke nødvendig å selv bry ser gjennom høyre side av treet.

322
00:24:40,520 --> 00:24:43,780
Når vi flytter til venstre og vi er nå på noden som inneholder 3,

323
00:24:43,780 --> 00:24:48,110
vi kan gjøre det samme sammenligning igjen der vi sammenligner 3 og 6.

324
00:24:48,110 --> 00:24:52,430
Og vi finner at mens 6 - verdien vi leter etter - er større enn 3,

325
00:24:52,430 --> 00:24:58,580
vi kan gå til høyre side av noden som inneholder 3.

326
00:24:58,580 --> 00:25:02,670
Det er ingen venstre side her, så vi kunne ha ignorert det.

327
00:25:02,670 --> 00:25:06,510
Men vi vet bare at fordi vi ser på selve treet,

328
00:25:06,510 --> 00:25:08,660
og vi kan se at treet ikke har barn.

329
00:25:08,660 --> 00:25:13,640
>> Det er også ganske lett å slå opp 6 i dette treet hvis vi gjør det selv som mennesker,

330
00:25:13,640 --> 00:25:16,890
men la oss følge denne prosessen mekanisk som en datamaskin ville gjøre

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

332
00:25:18,620 --> 00:25:26,200
På dette punktet, er vi nå ser på en node som inneholder 6,

333
00:25:26,200 --> 00:25:29,180
og vi leter etter verdien 6,

334
00:25:29,180 --> 00:25:31,740
så, ja, vi har funnet den riktige noden.

335
00:25:31,740 --> 00:25:35,070
Vi fant verdien 6 i treet vårt, og vi kan stoppe våre søk.

336
00:25:35,070 --> 00:25:37,330
På dette punktet, avhengig av hva som skjer,

337
00:25:37,330 --> 00:25:41,870
vi kan si, ja, vi har funnet verdien 6, eksisterer det i treet vårt.

338
00:25:41,870 --> 00:25:47,640
Eller, hvis vi planlegger å sette inn en node eller gjøre noe, kan vi gjøre det på dette punktet.

339
00:25:47,640 --> 00:25:53,010
>> La oss gjøre et par flere oppslag bare for å se hvordan dette fungerer.

340
00:25:53,010 --> 00:25:59,390
La oss se på hva som skjer hvis vi skulle prøve og se opp verdien 10.

341
00:25:59,390 --> 00:26:02,970
Hvis vi skulle slå opp verdien 10, vil vi begynne med roten.

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

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

344
00:26:13,640 --> 00:26:16,210
Så igjen, vi ville prøve å flytte til høyre.

345
00:26:16,210 --> 00:26:20,350
Men på dette punktet, ville vi legge merke til at vi er på en null node.

346
00:26:20,350 --> 00:26:23,080
Det er ingenting der. Det er ingenting der 10 skal være.

347
00:26:23,080 --> 00:26:29,360
Det er der vi kan rapportere feil - at det er faktisk ingen 10 i treet.

348
00:26:29,360 --> 00:26:35,420
Og til slutt, la oss gå gjennom saken der vi prøver å slå opp en i treet.

349
00:26:35,420 --> 00:26:38,790
Dette er i likhet med hva som skjer hvis vi ser opp 10, unntatt i stedet for å gå til høyre,

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

351
00:26:41,260 --> 00:26:46,170
Vi starter på 7 og se at 1 er mindre enn 7, så vi beveger seg mot venstre.

352
00:26:46,170 --> 00:26:51,750
Vi kommer til 3 og se at en er mindre enn 3, så igjen vi prøver å flytte til venstre.

353
00:26:51,750 --> 00:26:59,080
På dette punktet har vi en null node, så igjen vi kan rapportere feil.

354
00:26:59,080 --> 00:27:10,260
>> Hvis du ønsker å lære mer om binære trær,

355
00:27:10,260 --> 00:27:14,420
det er en hel haug med morsomme små problemer som du kan gjøre med dem.

356
00:27:14,420 --> 00:27:19,450
Jeg foreslår å praktisere tegningen ut av disse diagrammene én etter én

357
00:27:19,450 --> 00:27:21,910
og følge gjennom alle de forskjellige trinnene,

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

359
00:27:25,060 --> 00:27:27,480
ikke bare når du gjør Huffman koding oppgavesettet

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

361
00:27:29,390 --> 00:27:32,220
bare lære å trekke ut disse datastrukturer og tenke gjennom problemene

362
00:27:32,220 --> 00:27:38,000
med penn og papir, eller i dette tilfellet, iPad og pekepenn.

363
00:27:38,000 --> 00:27:41,000
>> På dette punktet skjønt, vi kommer til å gå videre for å gjøre noen kodepraksis

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

365
00:27:44,870 --> 00:27:52,150
Jeg kommer til å bytte tilbake over til datamaskinen min.

366
00:27:52,150 --> 00:27:58,480
For denne delen av seksjonen, i stedet for å bruke CS50 Run eller CS50 Spaces,

367
00:27:58,480 --> 00:28:01,500
Jeg kommer til å bruke apparatet.

368
00:28:01,500 --> 00:28:04,950
>> Følge sammen med oppgavesettet spesifikasjonen,

369
00:28:04,950 --> 00:28:07,740
Jeg ser at jeg skal åpne opp maskinen,

370
00:28:07,740 --> 00:28:11,020
gå til min Dropbox mappen oppretter du en mappe som heter § 7,

371
00:28:11,020 --> 00:28:15,730
og deretter opprette en fil som heter binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Here we go. Jeg har apparatet allerede åpen.

373
00:28:22,050 --> 00:28:25,910
Jeg skal trekke opp en terminal.

374
00:28:25,910 --> 00:28:38,250
Jeg kommer til å gå til Dropbox-mappen, lage en katalog som heter section7,

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

376
00:28:42,230 --> 00:28:48,860
Nå skal jeg åpne opp binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Here we go - tom fil.

378
00:28:51,750 --> 00:28:54,330
>> La oss gå tilbake til spesifikasjonen.

379
00:28:54,330 --> 00:28:59,850
Spesifikasjonen ber å lage en ny type definisjon

380
00:28:59,850 --> 00:29:03,080
for en binær tre node som inneholder int verdier -

381
00:29:03,080 --> 00:29:07,110
akkurat som de verdier som vi trakk ut i vår diagramfunksjonen før.

382
00:29:07,110 --> 00:29:11,740
Vi kommer til å bruke denne standardtekst typedef at vi har gjort her

383
00:29:11,740 --> 00:29:14,420
at du bør kjenne igjen fra Problem Set 5 -

384
00:29:14,420 --> 00:29:19,190
hvis du gjorde hash table måte å erobre stavekontroll program.

385
00:29:19,190 --> 00:29:22,540
Du bør også kjenne det fra forrige ukes delen

386
00:29:22,540 --> 00:29:23,890
der vi snakket om koblede lister.

387
00:29:23,890 --> 00:29:27,870
Vi har fått denne typedef av en struct node,

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

389
00:29:34,430 --> 00:29:39,350
slik at vi kan deretter henvise til den siden vi ønsker å ha struct node pekere

390
00:29:39,350 --> 00:29:45,740
som en del av struct vår, men vi har da omringet dette -

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

392
00:29:47,700 --> 00:29:54,600
slik at senere i koden, kan vi vise til denne struct som bare en node i stedet for en struct node.

393
00:29:54,600 --> 00:30:03,120
>> Dette kommer til å være svært lik den enkeltvis-lenket liste definisjon som vi så i forrige uke.

394
00:30:03,120 --> 00:30:20,070
For å gjøre dette, la oss bare begynne med å skrive ut standardteksten.

395
00:30:20,070 --> 00:30:23,840
Vi vet at vi må ha et heltall,

396
00:30:23,840 --> 00:30:32,170
så vil vi sette i int verdi, og deretter i stedet for å ha bare én pekeren til neste element -

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

398
00:30:33,970 --> 00:30:38,110
Vi kommer til å ha venstre og høyre barn pekere.

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

400
00:30:42,880 --> 00:30:51,190
og struct node * høyre barn;. Cool.

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

402
00:30:54,740 --> 00:30:58,530
La oss gå tilbake til spesifikasjonen.

403
00:30:58,530 --> 00:31:05,030
>> Nå trenger vi å erklære en global node * variabel for roten av et tre.

404
00:31:05,030 --> 00:31:10,590
Vi kommer til å gjøre dette globale, akkurat som vi gjorde første pekeren i vår lenket liste også global.

405
00:31:10,590 --> 00:31:12,690
Dette var slik at i de funksjoner som vi skriver

406
00:31:12,690 --> 00:31:16,180
Vi trenger ikke å holde passerer rundt denne roten -

407
00:31:16,180 --> 00:31:19,620
selv om vi vil se at hvis du ønsker å skrive disse funksjonene rekursivt,

408
00:31:19,620 --> 00:31:22,830
det kan være bedre å ikke engang passerer det rundt som en global i første omgang

409
00:31:22,830 --> 00:31:28,090
og i stedet starte den lokalt på din viktigste funksjon.

410
00:31:28,090 --> 00:31:31,960
Men, vi gjør det globalt for å starte.

411
00:31:31,960 --> 00:31:39,920
Igjen, vil vi gi et par plasser, og jeg kommer til å erklære en node * rot.

412
00:31:39,920 --> 00:31:46,770
Bare for å være sikker på at jeg ikke la dette initialisert, kommer jeg til å sette den lik null.

413
00:31:46,770 --> 00:31:52,210
Nå, i den viktigste funksjonen - som vi skal skrive veldig raskt akkurat 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 kommer til å begynne å erklære min argv array som const akkurat slik at jeg vet

416
00:32:10,640 --> 00:32:14,550
at disse argumentene er argumenter som jeg sannsynligvis ikke vil endre.

417
00:32:14,550 --> 00:32:18,390
Hvis jeg ønsker å endre dem jeg bør nok være å lage kopier av dem.

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

419
00:32:21,740 --> 00:32:25,440
Det er greit uansett. Det er greit å la den være som - utelate const hvis du ønsker.

420
00:32:25,440 --> 00:32:28,630
Jeg vanligvis sette den i akkurat slik at jeg minne meg selv

421
00:32:28,630 --> 00:32:33,650
 at jeg sannsynligvis ikke vil endre disse argumentene.

422
00:32:33,650 --> 00:32:39,240
>> Som alltid, jeg kommer til å inkludere denne avkastningen 0-linje på slutten av main.

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

424
00:32:45,730 --> 00:32:48,900
Som det står akkurat nå, har jeg fått en peker som er satt til null,

425
00:32:48,900 --> 00:32:52,970
så den peker på noe.

426
00:32:52,970 --> 00:32:57,480
For å faktisk begynne å bygge noden,

427
00:32:57,480 --> 00:32:59,250
Jeg må først allokere minne for det.

428
00:32:59,250 --> 00:33:05,910
Jeg kommer til å gjøre det ved å gjøre minne på haugen med malloc.

429
00:33:05,910 --> 00:33:10,660
Jeg kommer til å sette root lik resultatet av malloc,

430
00:33:10,660 --> 00:33:19,550
og jeg kommer til å bruke sizeof operatør å beregne størrelsen på en node.

431
00:33:19,550 --> 00:33:24,990
Grunnen til at jeg bruker sizeof node i motsetning til, si,

432
00:33:24,990 --> 00:33:37,020
gjøre noe som dette - malloc (4 + 4 +4) eller malloc 12 -

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

434
00:33:40,820 --> 00:33:44,540
Jeg ønsker å være i stand til å ta dette. C-fil, kompilere den på apparatet,

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

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

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

438
00:33:54,640 --> 00:33:59,510
>> Hvis jeg gjør antagelser om størrelsen på variablene -

439
00:33:59,510 --> 00:34:02,070
størrelsen på en int eller størrelsen av en peker -

440
00:34:02,070 --> 00:34:06,070
da jeg også gjøre antagelser om hva slags arkitekturer

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

442
00:34:10,440 --> 00:34:15,030
Bruk alltid sizeof i motsetning til manuelt summere struct feltene.

443
00:34:15,030 --> 00:34:20,500
Den andre grunnen er at det kan også være padding at kompilatoren setter inn i struct.

444
00:34:20,500 --> 00:34:26,570
Selv bare summere de enkelte feltene er ikke noe som du vanligvis ønsker å gjøre,

445
00:34:26,570 --> 00:34:30,340
så, slette den linjen.

446
00:34:30,340 --> 00:34:33,090
Nå, for å virkelig klargjøre dette rotnoden,

447
00:34:33,090 --> 00:34:36,489
Jeg kommer til å plugge inn verdier for hver av sine ulike felt.

448
00:34:36,489 --> 00:34:41,400
For eksempel, for verdien jeg vet jeg vil initialisere til 7,

449
00:34:41,400 --> 00:34:46,920
og for nå skal jeg sette den venstre barnet å være null

450
00:34:46,920 --> 00:34:55,820
og retten barnet også være null. Flott!

451
00:34:55,820 --> 00:35:02,670
Vi har gjort det en del av spec.

452
00:35:02,670 --> 00:35:07,390
>> Spesifikasjonen ned på bunnen av side 3 ber meg om å opprette tre flere noder -

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

454
00:35:10,600 --> 00:35:14,210
og deretter koble dem opp slik at det ser ut akkurat som vår trestruktur

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

456
00:35:17,120 --> 00:35:20,450
La oss gjøre det ganske raskt her.

457
00:35:20,450 --> 00:35:26,270
Du vil se veldig raskt at jeg kommer til å begynne å skrive en haug med duplikat kode.

458
00:35:26,270 --> 00:35:32,100
Jeg kommer til å opprette en node * og jeg kommer til å kalle det tre.

459
00:35:32,100 --> 00:35:36,000
Jeg kommer til å sette den lik malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Jeg kommer til å sette tre-> verdi = 3.

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

462
00:35:54,780 --> 00:36:01,150
Det ser ganske lik initialisering roten, og det er akkurat hva

463
00:36:01,150 --> 00:36:05,760
Jeg kommer til å gjøre hvis jeg begynner å initialisere 6 og 9 også.

464
00:36:05,760 --> 00:36:20,720
Jeg skal gjøre det veldig raskt her - faktisk, jeg kommer til å gjøre en liten kopiere og lime,

465
00:36:20,720 --> 00:36:46,140
og sørge for at jeg - alright.

466
00:36:46,470 --> 00:37:09,900
 Nå har jeg fått den kopiert og jeg kan gå videre og sette dette lik 6.

467
00:37:09,900 --> 00:37:14,670
Du kan se at dette tar litt tid og er ikke super-effektiv.

468
00:37:14,670 --> 00:37:22,610
På bare litt, vil vi skrive en funksjon som vil gjøre dette for oss.

469
00:37:22,610 --> 00:37:32,890
Jeg ønsker å bytte ut dette med en 9, erstatte den med en 6.

470
00:37:32,890 --> 00:37:37,360
>> Nå har vi alle våre noder opprettet og initialisert.

471
00:37:37,360 --> 00:37:41,200
Vi har fått vår root settes lik 7, eller som inneholder verdien 7,

472
00:37:41,200 --> 00:37:46,510
vår node inneholdende 3, vår node inneholdende 6, og vår node inneholdende 9.

473
00:37:46,510 --> 00:37:50,390
På dette punktet, er alt vi trenger å gjøre ledning alt opp.

474
00:37:50,390 --> 00:37:53,020
Grunnen til at jeg initialisert alle pekere til null er bare slik at jeg sørge for at

475
00:37:53,020 --> 00:37:56,260
Jeg har ikke noen uinitialiserte pekere i det ved et uhell.

476
00:37:56,260 --> 00:38:02,290
Og også siden, på dette punktet, jeg bare nødt til å faktisk koble nodene til hverandre -

477
00:38:02,290 --> 00:38:04,750
til de som de faktisk er koblet til - jeg trenger ikke å gå gjennom og gjøre

478
00:38:04,750 --> 00:38:08,240
at alle nuller er der på de riktige stedene.

479
00:38:08,240 --> 00:38:15,630
>> Starter ved roten, jeg vet at roten venstre barnet er 3.

480
00:38:15,630 --> 00:38:21,250
Jeg vet at roten rett barnet er 9.

481
00:38:21,250 --> 00:38:24,880
Etter det den eneste andre barn som jeg har igjen å bekymre seg

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

483
00:38:39,080 --> 00:38:44,670
På dette punktet, ser det hele ganske bra.

484
00:38:44,670 --> 00:38:54,210
Vi vil slette noen av disse linjene.

485
00:38:54,210 --> 00:38:59,540
Nå ser alt ganske bra.

486
00:38:59,540 --> 00:39:04,240
La oss gå tilbake til vår spesifikasjonen og se hva vi har å gjøre videre.

487
00:39:04,240 --> 00:39:07,610
>> På dette punktet, må vi skrive en funksjon som heter 'inneholder'

488
00:39:07,610 --> 00:39:14,150
med en prototype av "bool inneholder (int verdi) '.

489
00:39:14,150 --> 00:39:17,060
Og denne inneholder funksjonen skal returnere true

490
00:39:17,060 --> 00:39:21,200
 hvis treet peker til vår globale root variabel

491
00:39:21,200 --> 00:39:26,950
 inneholder verdi sendt inn i funksjonen og falske ellers.

492
00:39:26,950 --> 00:39:29,000
La oss gå videre og gjøre det.

493
00:39:29,000 --> 00:39:35,380
Dette kommer til å bli akkurat som oppslaget som vi gjorde for hånd på iPad bare litt siden.

494
00:39:35,380 --> 00:39:40,130
La oss zoome tilbake i litt og blar opp.

495
00:39:40,130 --> 00:39:43,130
Vi kommer til å sette denne funksjonen rett over vår viktigste funksjon

496
00:39:43,130 --> 00:39:48,990
slik at vi ikke trenger å gjøre noen form for prototyping.

497
00:39:48,990 --> 00:39:55,960
Så inneholder bool (int verdi).

498
00:39:55,960 --> 00:40:00,330
Det vi går. Det er vår standardtekst erklæringen.

499
00:40:00,330 --> 00:40:02,900
Bare for å være sikker på at dette vil kompilere,

500
00:40:02,900 --> 00:40:06,820
Jeg kommer til å gå videre og bare sette den lik return false.

501
00:40:06,820 --> 00:40:09,980
Akkurat nå denne funksjonen bare ikke vil gjøre noe og alltid rapportere at

502
00:40:09,980 --> 00:40:14,010
verdien som vi leter etter er ikke i treet.

503
00:40:14,010 --> 00:40:16,280
>> På dette punktet, er det sannsynligvis en god idé -

504
00:40:16,280 --> 00:40:19,600
siden vi har skrevet en hel haug med kode, og vi har ikke engang forsøkt å teste det ennå -

505
00:40:19,600 --> 00:40:22,590
å sørge for at det hele kompilerer.

506
00:40:22,590 --> 00:40:27,460
Det er et par ting som vi må gjøre for å sørge for at dette faktisk vil kompilere.

507
00:40:27,460 --> 00:40:33,530
Først se om vi har brukt noen funksjoner i noen av bibliotekene som vi ennå ikke har tatt med.

508
00:40:33,530 --> 00:40:37,940
Funksjonene vi har brukt så langt er malloc,

509
00:40:37,940 --> 00:40:43,310
og vi har også brukt denne type - denne standardisert type som kalles 'bool' -

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

511
00:40:45,750 --> 00:40:53,250
Vi definitivt ønsker å inkludere standard bool.h for bool type,

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

513
00:40:59,230 --> 00:41:03,530
som inkluderer malloc, og gratis, og alt det der.

514
00:41:03,530 --> 00:41:08,660
Så, zoome ut, kommer vi til å slutte.

515
00:41:08,660 --> 00:41:14,190
La oss prøve og sørge for at dette faktisk gjorde kompilere.

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

517
00:41:18,150 --> 00:41:22,990
>> La oss åpne opp binary_tree.c igjen.

518
00:41:22,990 --> 00:41:34,530
Det kompilerer. La oss gå ned og sørge for at vi setter noen samtaler til vår Inneholder funksjon -

519
00:41:34,530 --> 00:41:40,130
bare for å være sikker på at det er alt vel og bra.

520
00:41:40,130 --> 00:41:43,170
For eksempel når vi gjorde noen oppslag i treet vårt tidligere,

521
00:41:43,170 --> 00:41:48,500
vi prøvde å slå opp verdiene 6, 10 og 1, og vi visste at 6 var i treet,

522
00:41:48,500 --> 00:41:52,220
10 var ikke i treet, og en var ikke i treet heller.

523
00:41:52,220 --> 00:41:57,230
La oss bruke disse eksempler samtaler som en måte å finne ut hvorvidt

524
00:41:57,230 --> 00:41:59,880
vår inneholder funksjonen fungerer.

525
00:41:59,880 --> 00:42:05,210
For å gjøre det, jeg kommer til å bruke printf funksjonen,

526
00:42:05,210 --> 00:42:10,280
og vi kommer til å skrive ut resultatet av kallet til inneholder.

527
00:42:10,280 --> 00:42:13,280
Jeg kommer til å sette i en streng "inneholder (% d) = fordi

528
00:42:13,280 --> 00:42:20,470
 vi kommer til å plugge inn den verdien som vi kommer til å se etter,

529
00:42:20,470 --> 00:42:27,130
og =% s \ n "og bruke den som vår formatstrengen.

530
00:42:27,130 --> 00:42:30,720
Vi bare kommer til å se - bokstavelig talt skrive ut på skjermen -

531
00:42:30,720 --> 00:42:32,060
det ser ut som en funksjon.

532
00:42:32,060 --> 00:42:33,580
Dette er egentlig ikke funksjonen samtalen.

533
00:42:33,580 --> 00:42:36,760
 Dette er bare en streng designet for å ligne en funksjon.

534
00:42:36,760 --> 00:42:41,140
>> Nå kommer vi til å plugge inn verdiene.

535
00:42:41,140 --> 00:42:43,580
Vi kommer til å prøve inneholder den 6.,

536
00:42:43,580 --> 00:42:48,340
og hva vi skal gjøre her er å bruke den trefoldig operatør.

537
00:42:48,340 --> 00:42:56,340
La oss se - inneholder 6 - så nå har jeg inneholdt 6 og hvis inneholder 6 er sant,

538
00:42:56,340 --> 00:43:01,850
strengen som vi kommer til å sende til% s format karakter

539
00:43:01,850 --> 00:43:04,850
kommer til å være strengen "true".

540
00:43:04,850 --> 00:43:07,690
La oss bla over en liten bit.

541
00:43:07,690 --> 00:43:16,210
Ellers ønsker vi å sende strengen "false" hvis inneholder 6 avkastning falske.

542
00:43:16,210 --> 00:43:19,730
Dette er en litt klønete utseende, men jeg fant ut at jeg kan like godt illustrere

543
00:43:19,730 --> 00:43:23,780
hva trefoldig operatøren ser ut siden vi ikke har sett det en stund.

544
00:43:23,780 --> 00:43:27,670
Dette vil være en fin, praktisk måte å finne ut om vår inneholder funksjonen fungerer.

545
00:43:27,670 --> 00:43:30,040
Jeg kommer til å rulle tilbake over til venstre,

546
00:43:30,040 --> 00:43:39,900
og jeg kommer til å kopiere og lime inn denne linjen et par ganger.

547
00:43:39,900 --> 00:43:44,910
Det endret noen av disse verdiene rundt,

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

549
00:43:59,380 --> 00:44:02,480
>> På dette punktet har vi fått en fin Inneholder funksjon.

550
00:44:02,480 --> 00:44:06,080
Vi har noen tester, og vi vil se om dette fungerer.

551
00:44:06,080 --> 00:44:08,120
På dette punktet har vi skrevet litt mer kode.

552
00:44:08,120 --> 00:44:13,160
Tid for å slutte ut og sørge for at alt fortsatt samler.

553
00:44:13,160 --> 00:44:20,360
Avslutt ut, og la oss nå prøve å lage binære treet igjen.

554
00:44:20,360 --> 00:44:22,260
Vel, det ser ut som vi har fått en feil,

555
00:44:22,260 --> 00:44:26,930
og vi har fått dette eksplisitt erklære bibliotek funksjon printf.

556
00:44:26,930 --> 00:44:39,350
Det ser ut som vi trenger å gå inn og # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Og med det, bør alt kompilere. Vi er alle gode.

558
00:44:45,350 --> 00:44:50,420
La oss nå prøve å kjøre binære treet og se hva som skjer.

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 ser det, som vi forventet -

561
00:44:55,190 --> 00:44:56,910
fordi vi ikke har implementert inneholder ennå,

562
00:44:56,910 --> 00:44:59,800
eller rettere sagt, har vi bare satt i return false -

563
00:44:59,800 --> 00:45:03,300
Vi ser at det er nettopp tilbake usant for alle av dem,

564
00:45:03,300 --> 00:45:06,180
slik at det er alle som arbeider for det meste ganske godt.

565
00:45:06,180 --> 00:45:11,860
>> La oss gå tilbake og faktisk gjennomføre inneholder på dette punktet.

566
00:45:11,860 --> 00:45:17,490
Jeg kommer til å rulle ned, zoome inn, og -

567
00:45:17,490 --> 00:45:22,330
huske, var algoritme som vi brukte som vi startet på rotnoden

568
00:45:22,330 --> 00:45:28,010
og deretter på hver node vi møter, vi gjør en sammenligning,

569
00:45:28,010 --> 00:45:32,380
og basert på at sammenligning enten vi flytte til venstre barnet eller høyre barnet.

570
00:45:32,380 --> 00:45:39,670
Dette kommer til å se veldig lik den binære søk koden som vi skrev tidligere i begrepet.

571
00:45:39,670 --> 00:45:47,810
Når vi starter, vet vi at vi ønsker å holde på gjeldende node

572
00:45:47,810 --> 00:45:54,050
at vi ser på, og gjeldende node kommer til å bli stilt i henhold til rotnoden.

573
00:45:54,050 --> 00:45:56,260
Og nå, vi kommer til å holde det gående gjennom treet,

574
00:45:56,260 --> 00:45:58,140
og husk at vår stoppe tilstand -

575
00:45:58,140 --> 00:46:01,870
 når vi faktisk jobbet gjennom eksempel hånd -

576
00:46:01,870 --> 00:46:03,960
var da vi oppdaget en null node,

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

578
00:46:05,480 --> 00:46:09,620
men heller når vi faktisk flyttet til en node i treet

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

580
00:46:12,640 --> 00:46:20,720
Vi kommer til å veksle til nå er ikke lik null.

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

582
00:46:22,920 --> 00:46:31,610
Vi kommer til å teste om (nå -> verdi == verdi),

583
00:46:31,610 --> 00:46:35,160
da vet vi at vi faktisk har funnet noden som vi leter etter.

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

585
00:46:40,450 --> 00:46:49,830
Ellers, ønsker vi å se hvorvidt verdien er mindre enn verdien.

586
00:46:49,830 --> 00:46:53,850
Hvis gjeldende node verdi er mindre enn verdien vi leter etter,

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

588
00:46:57,280 --> 00:47:10,600
Så nå = nå -> right_child, og ellers kommer vi til å flytte til venstre.

589
00:47:10,600 --> 00:47:17,480
nå = nå -> left_child;. Ganske enkelt.

590
00:47:17,480 --> 00:47:22,830
>> Du kjenner kanskje løkken som ser svært lik denne fra

591
00:47:22,830 --> 00:47:27,580
binære søk tidligere i begrepet, bortsett da var vi å gjøre med lav, middels og høy.

592
00:47:27,580 --> 00:47:30,000
Her, vi må se på en gjeldende verdi,

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

594
00:47:31,930 --> 00:47:34,960
La oss sørge for at denne koden fungerer.

595
00:47:34,960 --> 00:47:42,780
Først, sørg for at det kompilerer. Ser ut som den gjør.

596
00:47:42,780 --> 00:47:47,920
La oss prøve å kjøre den.

597
00:47:47,920 --> 00:47:50,160
Og ja, skrives det ut alt som vi forventet.

598
00:47:50,160 --> 00:47:54,320
Det finner 6 i treet, ikke finner 10 fordi 10 ikke er i treet,

599
00:47:54,320 --> 00:47:57,740
og finner ikke en enten fordi en er heller ikke i treet.

600
00:47:57,740 --> 00:48:01,420
Kule ting.

601
00:48:01,420 --> 00:48:04,470
>> Alright. La oss gå tilbake til vår spesifikasjonen og se hva som skjer videre.

602
00:48:04,470 --> 00:48:07,990
Nå ønsker det å legge til noen flere noder til treet vårt.

603
00:48:07,990 --> 00:48:11,690
Den ønsker å legge til 5, 2 og 8, og sørge for at våre inneholder kode

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

605
00:48:13,570 --> 00:48:14,900
La oss gå gjøre det.

606
00:48:14,900 --> 00:48:19,430
På dette punktet, snarere enn å gjøre det irriterende kopiere og lime igjen,

607
00:48:19,430 --> 00:48:23,770
la oss skrive en funksjon for å faktisk lage en node.

608
00:48:23,770 --> 00:48:27,740
Hvis vi bla nedover hele veien til main, ser vi at vi har gjort dette

609
00:48:27,740 --> 00:48:31,210
svært lik kode om igjen og om igjen hver gang vi ønsker å skape en node.

610
00:48:31,210 --> 00:48:39,540
>> La oss skrive en funksjon som faktisk vil bygge en node for oss og returnere det.

611
00:48:39,540 --> 00:48:41,960
Jeg kommer til å kalle det build_node.

612
00:48:41,960 --> 00:48:45,130
Jeg kommer til å bygge en node med en bestemt verdi.

613
00:48:45,130 --> 00:48:51,040
Zoome inn her.

614
00:48:51,040 --> 00:48:56,600
Det første jeg skal gjøre er å lage faktisk plass til noden på haugen.

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

616
00:49:05,400 --> 00:49:14,960
og her, jeg bare kommer til å initialisere alle feltene for å være passende verdier.

617
00:49:14,960 --> 00:49:22,500
Og helt til slutt, vil vi gå tilbake til vår node.

618
00:49:22,500 --> 00:49:28,690
Alright. En ting å merke seg er at denne funksjonen her

619
00:49:28,690 --> 00:49:34,320
kommer til å returnere en peker til minne som har vært heap-bevilget.

620
00:49:34,320 --> 00:49:38,880
Hva er fint om dette er at denne noden nå -

621
00:49:38,880 --> 00:49:42,420
vi må erklære den på haugen fordi hvis vi erklærte den på stakken

622
00:49:42,420 --> 00:49:45,050
vi ville ikke være i stand til å gjøre det i denne funksjonen som dette.

623
00:49:45,050 --> 00:49:47,690
At minnet vil gå ut av omfanget

624
00:49:47,690 --> 00:49:51,590
og ville være ugyldig hvis vi prøvde å få tilgang til det senere.

625
00:49:51,590 --> 00:49:53,500
Siden vi er erklære heap-minnet som er tildelt,

626
00:49:53,500 --> 00:49:55,830
Vi er nødt til å ta vare på frigjør det senere

627
00:49:55,830 --> 00:49:58,530
for vårt program for å ikke lekke noe minne.

628
00:49:58,530 --> 00:50:01,270
Vi har vært punting på at for alt annet i koden

629
00:50:01,270 --> 00:50:02,880
bare for enkelhets skyld på tiden,

630
00:50:02,880 --> 00:50:05,610
men hvis du noen gang skrive en funksjon som ser slik ut

631
00:50:05,610 --> 00:50:10,370
hvor du har - noen kaller det en malloc eller RealLOC inne -

632
00:50:10,370 --> 00:50:14,330
du vil være sikker på at du setter en slags kommentar her oppe som sier,

633
00:50:14,330 --> 00:50:29,970
hei, du vet, returnerer en heap-bevilget node initialisert med bestått i verdi.

634
00:50:29,970 --> 00:50:33,600
Og så du vil være sikker på at du setter inn en slags notat som sier

635
00:50:33,600 --> 00:50:41,720
den som ringer må frigjøre den returnerte minne.

636
00:50:41,720 --> 00:50:45,450
På den måten, hvis noen gang går og bruker denne funksjonen,

637
00:50:45,450 --> 00:50:48,150
de vet at det de får tilbake fra den funksjonen

638
00:50:48,150 --> 00:50:50,870
på et tidspunkt vil trenge å bli frigjort.

639
00:50:50,870 --> 00:50:53,940
>> Forutsatt at alt er vel og bra her,

640
00:50:53,940 --> 00:51:02,300
vi kan gå ned i koden vår og erstatte alle disse linjene her

641
00:51:02,300 --> 00:51:05,410
med samtaler til vår build node funksjon.

642
00:51:05,410 --> 00:51:08,170
La oss gjøre det veldig raskt.

643
00:51:08,170 --> 00:51:15,840
Den ene delen som vi ikke kommer til å erstatte er denne delen her nede

644
00:51:15,840 --> 00:51:18,520
på bunnen hvor vi faktisk wire opp nodene til å peke til hverandre,

645
00:51:18,520 --> 00:51:21,030
fordi at vi ikke kan gjøre i vår funksjon.

646
00:51:21,030 --> 00:51:37,400
Men, la oss gjø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 nå har vi også ønsket å legge til noder for -

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

650
00:52:03,530 --> 00:52:09,760
og hva var den andre noden? La oss se her. Vi ønsket å også legge til 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 punktet, vet vi at vi har fått 7, 3, den 9, og 6

653
00:52:26,850 --> 00:52:30,320
alle kablet opp riktig, men hva med 5, den 8, og 2?

654
00:52:30,320 --> 00:52:33,550
Å holde alt i riktig rekkefølge,

655
00:52:33,550 --> 00:52:39,230
vi vet at tre rett barnet er 6.

656
00:52:39,230 --> 00:52:40,890
Så hvis vi skal legge til 5,

657
00:52:40,890 --> 00:52:46,670
de 5 tilhører også i høyre side av treet hvor 3 er roten,

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

659
00:52:50,440 --> 00:52:58,650
Vi kan gjøre dette ved å si, seks -> left_child = fem;

660
00:52:58,650 --> 00:53:10,790
og deretter 8 tilhører som venstre barn av 9, så ni -> left_child = åtte;

661
00:53:10,790 --> 00:53:22,190
og deretter 2 er venstre barn på 3, slik at vi kan gjøre det her oppe - dig -> left_child = to;.

662
00:53:22,190 --> 00:53:27,730
Hvis du ikke helt følger med på det, foreslår jeg at du trekker det ut selv.

663
00:53:27,730 --> 00:53:35,660
>> Alright. La oss ta vare på denne. La oss gå ut og sørge for at det kompilerer,

664
00:53:35,660 --> 00:53:40,760
og så kan vi legge inn våre inneholder samtaler.

665
00:53:40,760 --> 00:53:44,120
Ser ut som alt fortsatt samler.

666
00:53:44,120 --> 00:53:51,790
La oss gå inn og legge inn noen inneholder samtaler.

667
00:53:51,790 --> 00:53:59,640
Igjen, jeg kommer til å gjøre en liten bit av kopiere og lime.

668
00:53:59,640 --> 00:54:15,860
La oss nå søke etter 5, 8 og 2. Alright.

669
00:54:15,860 --> 00:54:28,330
La oss sørge for at alt dette ser bra fortsatt. Flott! Lagre og avslutte.

670
00:54:28,330 --> 00:54:33,220
Nå la oss gjøre, kompilere, og nå la oss kjøre.

671
00:54:33,220 --> 00:54:37,540
Fra resultatene, ser det ut som alt fungerer like fint og godt.

672
00:54:37,540 --> 00:54:41,780
Flott! Så nå har vi fått vår inneholder funksjon skrevet.

673
00:54:41,780 --> 00:54:46,160
La oss gå videre og begynne å jobbe på hvordan du setter noder i treet

674
00:54:46,160 --> 00:54:50,000
siden, som vi gjør det akkurat nå, ting er ikke veldig pen.

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

676
00:54:52,280 --> 00:55:00,540
den ber oss om å skrive en funksjon som kalles inn - igjen, tilbake en bool

677
00:55:00,540 --> 00:55:04,400
for hvorvidt vi kan faktisk sette noden i treet -

678
00:55:04,400 --> 00:55:07,710
og deretter for å sette inn i treet er spesifisert som

679
00:55:07,710 --> 00:55:11,060
det eneste argumentet til vår innsats funksjon.

680
00:55:11,060 --> 00:55:18,180
Vi kommer tilbake sant hvis vi kunne faktisk sette noden som inneholder verdien i treet,

681
00:55:18,180 --> 00:55:20,930
noe som betyr at vi, en, hadde nok minne,

682
00:55:20,930 --> 00:55:24,840
og så to, gjorde at noden ikke allerede eksisterer i treet siden -

683
00:55:24,840 --> 00:55:32,170
Husk, vi er ikke nødt til like verdier i treet, bare for å gjøre ting enkelt.

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

685
00:55:35,590 --> 00:55:44,240
Åpne den opp. Zoome inn litt, så bla nedover.

686
00:55:44,240 --> 00:55:47,220
La oss sette innsatsen funksjonen rett over inneholder.

687
00:55:47,220 --> 00:55:56,360
Igjen, det kommer til å bli kalt bool innsats (int verdi).

688
00:55:56,360 --> 00:56:01,840
Gi den litt mer plass, og deretter som en standard,

689
00:56:01,840 --> 00:56:08,870
la oss sette i retur falsk helt på slutten.

690
00:56:08,870 --> 00:56:22,620
Nå nede på bunnen, la oss gå videre og i stedet for manuelt å bygge noder

691
00:56:22,620 --> 00:56:27,900
i hoved oss ​​selv og ledninger dem opp til å peke på hverandre som vi gjør,

692
00:56:27,900 --> 00:56:30,600
vi vil stole på vår innsats funksjonen for å gjøre det.

693
00:56:30,600 --> 00:56:35,510
Vi vil ikke stole på vår innsats funksjonen for å bygge hele treet fra scratch ennå,

694
00:56:35,510 --> 00:56:39,970
men heller vi skal bli kvitt disse linjene - vi vil kommentere ut disse linjene -

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

696
00:56:43,430 --> 00:56:55,740
Og i stedet, vil vi sette inn anrop til vår innsats funksjon

697
00:56:55,740 --> 00:57:01,280
å sørge for at det faktisk fungerer.

698
00:57:01,280 --> 00:57:05,840
Here we go.

699
00:57:05,840 --> 00:57:09,300
>> Nå har vi kommentert ut disse linjene.

700
00:57:09,300 --> 00:57:13,700
Vi har bare 7, 3, 9 og 6 i vår treet på dette punktet.

701
00:57:13,700 --> 00:57:18,870
Å sørge for at dette er alt fungerer,

702
00:57:18,870 --> 00:57:25,050
Vi kan zoome ut, gjør vår binære treet,

703
00:57:25,050 --> 00:57:30,750
kjøre den, og vi kan se som inneholder nå forteller oss at vi er helt rett -

704
00:57:30,750 --> 00:57:33,110
5, 8, og 2 er ikke lenger i treet.

705
00:57:33,110 --> 00:57:37,960
Gå tilbake til koden,

706
00:57:37,960 --> 00:57:41,070
og hvordan skal vi sette inn?

707
00:57:41,070 --> 00:57:46,290
Husk hva vi gjorde da vi var faktisk sette 5, 8 og 2 tidligere.

708
00:57:46,290 --> 00:57:50,100
Vi spilte som Plinko spill hvor vi startet ved roten,

709
00:57:50,100 --> 00:57:52,780
gikk ned treet én etter én av en

710
00:57:52,780 --> 00:57:54,980
før vi fant den riktige avstanden,

711
00:57:54,980 --> 00:57:57,570
og da vi kablet i noden på riktig sted.

712
00:57:57,570 --> 00:57:59,480
Vi kommer til å gjøre det samme.

713
00:57:59,480 --> 00:58:04,070
Dette er i utgangspunktet som å skrive koden som vi brukte i inneholder funksjonen

714
00:58:04,070 --> 00:58:05,910
å finne stedet hvor noden skal være,

715
00:58:05,910 --> 00:58:10,560
og da er vi bare kommer til å sette noden der.

716
00:58:10,560 --> 00:58:17,000
La oss begynne å gjøre det.

717
00:58:17,000 --> 00:58:24,200
>> Så vi har en node * nå = root, vi bare kommer til å følge inneholder kode

718
00:58:24,200 --> 00:58:26,850
før vi finner ut at det ikke fungerer helt for oss.

719
00:58:26,850 --> 00:58:32,390
Vi kommer til å gå gjennom treet mens dagens elementet er ikke null,

720
00:58:32,390 --> 00:58:45,280
og hvis vi finner ut at nå er verdien er lik den verdien som vi prøver å sette -

721
00:58:45,280 --> 00:58:49,600
Vel, dette er en av sakene der vi ikke kunne faktisk sette noden

722
00:58:49,600 --> 00:58:52,730
inn i treet fordi dette betyr at vi har en lik verdi.

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

724
00:58:59,010 --> 00:59:08,440
Nå else if nå verdi er mindre enn verdien,

725
00:59:08,440 --> 00:59:10,930
nå vet vi at vi flytter til høyre

726
00:59:10,930 --> 00:59:17,190
 fordi verdien tilhører i høyre halvdel av nå treet.

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

728
00:59:30,110 --> 00:59:37,980
Det er i utgangspunktet vår inneholder fungere der.

729
00:59:37,980 --> 00:59:41,820
>> På dette punktet, når vi har fullført dette mens loop,

730
00:59:41,820 --> 00:59:47,350
vår nå pekeren kommer til å peke mot null

731
00:59:47,350 --> 00:59:51,540
Dersom funksjonen ikke allerede returnert.

732
00:59:51,540 --> 00:59:58,710
Vi er derfor å ha nå på det punktet der vi ønsker å sette inn den nye noden.

733
00:59:58,710 --> 01:00:05,210
Hva gjenstår er å faktisk bygge den nye noden,

734
01:00:05,210 --> 01:00:08,480
som vi kan gjøre ganske enkelt.

735
01:00:08,480 --> 01:00:14,930
Vi kan bruke vår super-hendig bygge node funksjon,

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

737
01:00:17,210 --> 01:00:21,400
vi bare slags tok for gitt, men nå skal vi gjøre bare for å være sikker -

738
01:00:21,400 --> 01:00:27,130
Vi skal teste å sørge for at verdien returnert av ny node var faktisk

739
01:00:27,130 --> 01:00:33,410
ikke null, fordi vi ikke ønsker å starte med tilgangen til minne om den er null.

740
01:00:33,410 --> 01:00:39,910
Vi kan teste for å være sikker på at ny node er ikke lik null.

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

742
01:00:42,910 --> 01:00:52,120
og hvis det er null, så kan vi bare return false tidlig.

743
01:00:52,120 --> 01:00:59,090
>> På dette punktet, må vi koble ny node i sin passende sted i treet.

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

745
01:01:03,510 --> 01:01:08,470
Vi ser at måten vi gjorde det da vi ønsket å sette 3 i treet

746
01:01:08,470 --> 01:01:11,750
ble vi vist til venstre barn av rot.

747
01:01:11,750 --> 01:01:14,920
Når vi setter 9 i treet, hadde vi tilgang til riktig barn av roten.

748
01:01:14,920 --> 01:01:21,030
Vi måtte ha en peker til den overordnede for å sette en ny verdi inn i treet.

749
01:01:21,030 --> 01:01:24,430
Rulle opp å sette inn, er at ikke kommer til å helt fungerer her

750
01:01:24,430 --> 01:01:27,550
fordi vi ikke har en forelder peker.

751
01:01:27,550 --> 01:01:31,650
Hva vi ønsker å være i stand til å gjøre er, på dette punktet,

752
01:01:31,650 --> 01:01:37,080
sjekk den overordnede verdi og se - vel, gosh,

753
01:01:37,080 --> 01:01:41,990
hvis foreldrene verdi er mindre enn dagens verdi,

754
01:01:41,990 --> 01:01:54,440
så forelderen rett barnet bør være ny node;

755
01:01:54,440 --> 01:02:07,280
ellers bør den overordnede venstre barn bli den nye noden.

756
01:02:07,280 --> 01:02:10,290
Men, vi har ikke denne forelderen pekeren helt ennå.

757
01:02:10,290 --> 01:02:15,010
>> For å få det, er vi faktisk nødt til å spore det som vi går gjennom treet

758
01:02:15,010 --> 01:02:18,440
og finne riktig sted i loop over.

759
01:02:18,440 --> 01:02:26,840
Vi kan gjøre det ved å rulle tilbake til toppen av vår innsats funksjon

760
01:02:26,840 --> 01:02:32,350
og sporing annen pekeren variabel kalt den overordnede.

761
01:02:32,350 --> 01:02:39,340
Vi kommer til å sette den lik null i utgangspunktet,

762
01:02:39,340 --> 01:02:43,640
og deretter hver gang vi går gjennom treet,

763
01:02:43,640 --> 01:02:51,540
vi kommer til å sette den overordnede pekeren for å matche dagens pekeren.

764
01:02:51,540 --> 01:02:59,140
Still foreldre lik nå.

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

766
01:03:02,260 --> 01:03:05,550
vi kommer til å sikre at så dagens pekeren blir økes

767
01:03:05,550 --> 01:03:12,640
den overordnede pekeren følger det - bare ett nivå høyere enn dagens pekeren i treet.

768
01:03:12,640 --> 01:03:17,370
At alle ser ganske bra.

769
01:03:17,370 --> 01:03:22,380
>> Jeg tror det én ting som vi ønsker å justere dette bygge node retur null.

770
01:03:22,380 --> 01:03:25,380
For å få bygge node å faktisk lykkes returnere null,

771
01:03:25,380 --> 01:03:31,060
vi må endre den koden,

772
01:03:31,060 --> 01:03:37,270
fordi her har vi aldri testet for å sørge for at malloc returnerte gyldig peker.

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

774
01:03:53,390 --> 01:03:55,250
hvis malloc returnerte gyldig peker, så får vi initialisere det;

775
01:03:55,250 --> 01:04:02,540
ellers vil vi bare gå tilbake og som vil ende opp med å returnere null for oss.

776
01:04:02,540 --> 01:04:13,050
Nå er alt ser ganske bra. La oss sørge for at dette faktisk samler.

777
01:04:13,050 --> 01:04:22,240
Gjør binære treet, og oh, vi har noen ting som skjer her.

778
01:04:22,240 --> 01:04:29,230
>> Vi har en implisitt erklæring av funksjon bygge node.

779
01:04:29,230 --> 01:04:31,950
Igjen, med disse kompilatorer, vi kommer til å starte på toppen.

780
01:04:31,950 --> 01:04:36,380
Hva som må bety at jeg ringer bygge node før jeg faktisk har erklært det.

781
01:04:36,380 --> 01:04:37,730
La oss gå tilbake til koden veldig raskt.

782
01:04:37,730 --> 01:04:43,510
Bla nedover, og sikker nok, min innsats funksjon erklært

783
01:04:43,510 --> 01:04:47,400
ovenfor bygge node funksjon,

784
01:04:47,400 --> 01:04:50,070
men jeg prøver å bruke bygge node innsiden av innsatsen.

785
01:04:50,070 --> 01:05:06,610
Jeg kommer til å gå inn og kopiere - og deretter lime bygge node funksjon vei opp her på toppen.

786
01:05:06,610 --> 01:05:11,750
På den måten, forhåpentligvis som vil fungere. La oss gi denne en gå.

787
01:05:11,750 --> 01:05:18,920
Nå er det kompilerer alt. Alt er bra.

788
01:05:18,920 --> 01:05:21,640
>> Men på dette punktet har vi faktisk ikke kalt vår innsats funksjon.

789
01:05:21,640 --> 01:05:26,510
Vi bare vet at det kompilerer, så la oss gå inn og sette noen samtaler i.

790
01:05:26,510 --> 01:05:28,240
La oss gjøre det i vår viktigste funksjon.

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

792
01:05:32,390 --> 01:05:36,680
og da vi ikke wire dem opp her nede.

793
01:05:36,680 --> 01:05:41,640
La oss ta noen telefoner for å sette inn,

794
01:05:41,640 --> 01:05:46,440
og la oss også bruke samme type ting som vi brukte

795
01:05:46,440 --> 01:05:52,810
når vi har gjort disse printf samtaler for å sikre at alt gjorde få satt inn riktig.

796
01:05:52,810 --> 01:06:00,550
Jeg kommer til å kopiere og lime inn,

797
01:06:00,550 --> 01:06:12,450
og i stedet for inneholder vi skal gjøre innsatsen.

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

799
01:06:30,140 --> 01:06:37,320
Dette bør forhåpentligvis sette 5, 8, og 2 inn i treet.

800
01:06:37,320 --> 01:06:44,050
Kompilere. Alt er bra. Nå skal vi faktisk kjøre programmet vårt.

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

802
01:06:47,330 --> 01:06:53,830
Så gjorde 5, 8 og 2 ikke gå, og det ser ut som inneholder ikke fant dem heller.

803
01:06:53,830 --> 01:06:58,890
Hva skjer? La oss zoome ut.

804
01:06:58,890 --> 01:07:02,160
Det første problemet er at innsatsen syntes å return false,

805
01:07:02,160 --> 01:07:08,750
og det ser ut som det er fordi vi igjen i våre return false samtale,

806
01:07:08,750 --> 01:07:14,590
og vi vil aldri returnert sant.

807
01:07:14,590 --> 01:07:17,880
Vi kan sette opp dette.

808
01:07:17,880 --> 01:07:25,290
Det andre problemet er nå selv om vi gjør - lagre denne, avslutter dette,

809
01:07:25,290 --> 01:07:34,530
kjøre gjøre igjen, kompilere den har, og deretter kjøre den -

810
01:07:34,530 --> 01:07:37,670
vi ser at noe annet skjedde her.

811
01:07:37,670 --> 01:07:42,980
En 5, 8, og 2 ble fortsatt aldri funnet i treet.

812
01:07:42,980 --> 01:07:44,350
Så, hva skjer?

813
01:07:44,350 --> 01:07:45,700
>> La oss ta en titt på denne i koden.

814
01:07:45,700 --> 01:07:49,790
La oss se om vi kan finne ut av dette.

815
01:07:49,790 --> 01:07:57,940
Vi starter med den overordnede ikke er null.

816
01:07:57,940 --> 01:07:59,510
Vi setter dagens pekeren lik roten pekeren,

817
01:07:59,510 --> 01:08:04,280
og vi kommer til å jobbe oss ned gjennom treet.

818
01:08:04,280 --> 01:08:08,650
Hvis gjeldende node ikke er null, da vet vi at vi kan flytte ned litt.

819
01:08:08,650 --> 01:08:12,330
Vi setter vår overordnede pekeren til å være lik dagens pekeren,

820
01:08:12,330 --> 01:08:15,420
sjekket verdi - hvis verdiene er de samme vi returnerte falsk.

821
01:08:15,420 --> 01:08:17,540
Hvis verdiene er mindre vi flyttet til høyre;

822
01:08:17,540 --> 01:08:20,399
ellers, flyttet vi til venstre.

823
01:08:20,399 --> 01:08:24,220
Så bygger vi en node. Jeg skal zoome inn litt.

824
01:08:24,220 --> 01:08:31,410
Og her kommer vi til å prøve å koble opp verdiene til å være den samme.

825
01:08:31,410 --> 01:08:37,250
Hva skjer? La oss se om muligens Valgrind kan gi oss et hint.

826
01:08:37,250 --> 01:08:43,910
>> Jeg liker å bruke Valgrind bare fordi Valgrind veldig raskt kjører

827
01:08:43,910 --> 01:08:46,729
og forteller deg om det er noen minnefeil.

828
01:08:46,729 --> 01:08:48,300
Når vi kjører Valgrind på koden,

829
01:08:48,300 --> 01:08:55,859
som du kan se rett here--Valgrind./binary_tree--and trykk enter.

830
01:08:55,859 --> 01:09:03,640
Du ser at vi ikke har noe minne feil, så det ser ut som alt er i orden så langt.

831
01:09:03,640 --> 01:09:07,529
Vi har noen minnelekkasjer, som vi vet, fordi vi ikke er

832
01:09:07,529 --> 01:09:08,910
skjer for å frigjøre noen av våre noder.

833
01:09:08,910 --> 01:09:13,050
La oss prøve å kjøre GDB å se hva som faktisk skjer.

834
01:09:13,050 --> 01:09:20,010
Vi vil gjøre gdb. / Binary_tree. Det startet opp helt fint.

835
01:09:20,010 --> 01:09:23,670
La oss sette en pause punkt på innsatsen.

836
01:09:23,670 --> 01:09:28,600
La oss kjøre.

837
01:09:28,600 --> 01:09:31,200
Det ser ut som vi aldri egentlig heter innsatsen.

838
01:09:31,200 --> 01:09:39,410
Det ser ut som problemet var bare at når jeg endret her nede i hoved -

839
01:09:39,410 --> 01:09:44,279
alle disse printf samtaler fra inneholder -

840
01:09:44,279 --> 01:09:56,430
Jeg har aldri egentlig endret disse til å ringe innsatsen.

841
01:09:56,430 --> 01:10:01,660
Nå la oss gi det et forsøk. La oss kompilere.

842
01:10:01,660 --> 01:10:09,130
Alle ser bra der. La oss nå prøve å kjøre den, se hva som skjer.

843
01:10:09,130 --> 01:10:13,320
Alright! Alt ser ganske bra der.

844
01:10:13,320 --> 01:10:18,130
>> Den siste ting å tenke på er, er det noen edge tilfeller til dette innlegget?

845
01:10:18,130 --> 01:10:23,170
Og det viser seg at, vel, den ene kanten sak som er alltid interessant å tenke på

846
01:10:23,170 --> 01:10:26,250
er, hva skjer hvis treet er tom og du kaller dette innlegget funksjon?

847
01:10:26,250 --> 01:10:30,330
Vil det fungere? Vel, la oss gi det et forsøk.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Måten vi kommer til å teste dette er, vi kommer til å gå ned til vår viktigste funksjon,

850
01:10:35,810 --> 01:10:41,690
og i stedet ledninger disse nodene opp som dette,

851
01:10:41,690 --> 01:10:56,730
vi bare kommer til å kommentere ut hele greia,

852
01:10:56,730 --> 01:11:02,620
og i stedet for ledninger opp nodene oss selv,

853
01:11:02,620 --> 01:11:09,400
Vi kan faktisk bare gå foran og slette alt dette.

854
01:11:09,400 --> 01:11:17,560
Vi kommer til å gjøre alt en samtale sette inn.

855
01:11:17,560 --> 01:11:49,020
Så, la oss gjøre - i stedet for 5, 8 og 2, vi kommer til å sette 7, 3, og 9.

856
01:11:49,020 --> 01:11:58,440
Og så får vi også ønsker å sette inn 6 også.

857
01:11:58,440 --> 01:12:05,190
Lagre. Avslutt. Gjør binære treet.

858
01:12:05,190 --> 01:12:08,540
Det kompilerer alt.

859
01:12:08,540 --> 01:12:10,320
Vi kan bare kjøre det som er, og se hva som skjer,

860
01:12:10,320 --> 01:12:12,770
men det er også kommer til å være veldig viktig å sørge for at

861
01:12:12,770 --> 01:12:14,740
Vi har ikke noen minnefeil,

862
01:12:14,740 --> 01:12:16,840
siden dette er en av våre edge saker som vi vet om.

863
01:12:16,840 --> 01:12:20,150
>> La oss sørge for at det fungerer godt under Valgrind,

864
01:12:20,150 --> 01:12:28,310
som vi vil gjøre ved bare å kjøre Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Det ser ut som vi faktisk har en feil fra en sammenheng -

866
01:12:31,110 --> 01:12:33,790
vi har denne segmentering feil.

867
01:12:33,790 --> 01:12:36,690
Hva skjedde?

868
01:12:36,690 --> 01:12:41,650
Valgrind forteller oss faktisk hvor det er.

869
01:12:41,650 --> 01:12:43,050
Zoome ut litt.

870
01:12:43,050 --> 01:12:46,040
Det ser ut som det skjer i vår innsats funksjon,

871
01:12:46,040 --> 01:12:53,420
hvor vi har en ugyldig lese av størrelse 4 på innsatsen, linje 60.

872
01:12:53,420 --> 01:13:03,590
La oss gå tilbake og se hva som skjer her.

873
01:13:03,590 --> 01:13:05,350
Zoome ut virkelig rask.

874
01:13:05,350 --> 01:13:14,230
Jeg vil være sikker på at det ikke går til kanten av skjermen, slik at vi kan se alt.

875
01:13:14,230 --> 01:13:18,760
Trekke det i litt. Alright.

876
01:13:18,760 --> 01:13:35,030
Bla nedover, og problemet er her.

877
01:13:35,030 --> 01:13:40,120
Hva skjer hvis vi kommer ned og vår nåværende node er allerede null,

878
01:13:40,120 --> 01:13:44,010
vår foreldrenoden er null, så hvis vi ser opp på toppen, akkurat her -

879
01:13:44,010 --> 01:13:47,340
hvis dette mens loop aldri utfører faktisk

880
01:13:47,340 --> 01:13:52,330
fordi vår nåværende verdien er null - vår rot er null så nå er null -

881
01:13:52,330 --> 01:13:57,810
da våre foreldre aldri blir satt til nå eller til en gyldig verdi,

882
01:13:57,810 --> 01:14:00,580
så vil foreldrene også være null.

883
01:14:00,580 --> 01:14:03,700
Vi må huske å se etter at

884
01:14:03,700 --> 01:14:08,750
etter den tid får vi her nede, og vi begynner å få tilgang til foreldrenes verdi.

885
01:14:08,750 --> 01:14:13,190
Så, hva skjer? Vel, hvis foreldrene er null -

886
01:14:13,190 --> 01:14:17,990
if (forelder == NULL) - da vet vi at

887
01:14:17,990 --> 01:14:19,530
det må ikke være noe i treet.

888
01:14:19,530 --> 01:14:22,030
Vi må prøve å sette det ved roten.

889
01:14:22,030 --> 01:14:32,570
Vi kan gjøre det ved å bare sette root lik den nye noden.

890
01:14:32,570 --> 01:14:40,010
Så på dette punktet, vet vi ikke egentlig ønsker å gå gjennom disse andre tingene.

891
01:14:40,010 --> 01:14:44,780
I stedet akkurat her, kan vi gjøre enten en else-if-else,

892
01:14:44,780 --> 01:14:47,610
eller vi kunne kombinere alt her oppe i en annet,

893
01:14:47,610 --> 01:14:56,300
men her skal vi bare bruke andre og gjøre det på den måten.

894
01:14:56,300 --> 01:14:59,030
Nå skal vi teste for å være sikker på at våre foreldre ikke er null

895
01:14:59,030 --> 01:15:02,160
før da faktisk prøver å få tilgang til sine områder.

896
01:15:02,160 --> 01:15:05,330
Dette vil hjelpe oss å unngå segmenteringen feil.

897
01:15:05,330 --> 01:15:14,740
Så vi avslutter, zoome ut, kompilere, kjøre.

898
01:15:14,740 --> 01:15:18,130
>> Ingen feil, men vi har fortsatt en haug med minnelekkasjer

899
01:15:18,130 --> 01:15:20,650
fordi vi ikke fri noen av våre noder.

900
01:15:20,650 --> 01:15:24,350
Men hvis vi går opp her, og vi ser på utskriften vår,

901
01:15:24,350 --> 01:15:30,880
Vi ser at, vel, ser ut som alle våre innsatser var tilbake sant, noe som er bra.

902
01:15:30,880 --> 01:15:33,050
Innsatsene er sanne,

903
01:15:33,050 --> 01:15:36,670
og deretter de riktige inneholder samtaler er også sant.

904
01:15:36,670 --> 01:15:41,510
>> Godt jobbet! Det ser ut som vi har lykkes skrevet innsatsen.

905
01:15:41,510 --> 01:15:47,430
Det er alt vi har for denne ukens Problem Set-spesifikasjonen.

906
01:15:47,430 --> 01:15:51,720
En morsom utfordring å tenke på er hvordan du faktisk ville gå i

907
01:15:51,720 --> 01:15:55,340
og fri alle nodene i dette treet.

908
01:15:55,340 --> 01:15:58,830
Vi kan gjøre så mange forskjellige måter,

909
01:15:58,830 --> 01:16:01,930
men jeg skal la det opp til deg å eksperimentere,

910
01:16:01,930 --> 01:16:06,080
og som en morsom utfordring, prøve og sørg for at du kan være sikker på

911
01:16:06,080 --> 01:16:09,490
at dette Valgrind rapporten ga ingen feil og ingen lekkasjer.

912
01:16:09,490 --> 01:16:12,880
>> Lykke til på denne ukens Huffman koding problem sett,

913
01:16:12,880 --> 01:16:14,380
og vi vil se deg neste uke!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]