1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [§ 7: Mer komfortabelt]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard University]

3
00:00:05,090 --> 00:00:07,930
[Dette er CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
OK. Så som jeg sa i min e-post,

5
00:00:10,110 --> 00:00:14,060
dette kommer til å være et binært-tree-intensive delen.

6
00:00:14,060 --> 00:00:16,820
Men det er ikke så mange spørsmål.

7
00:00:16,820 --> 00:00:18,920
Så vi kommer til å prøve og trekke ut hvert spørsmål

8
00:00:18,920 --> 00:00:25,430
og gå inn i smertefulle detalj av alle de beste måtene å gjøre ting på.

9
00:00:25,430 --> 00:00:31,200
Så helt i begynnelsen, går vi gjennom eksempler tegninger av binære trær og sånt.

10
00:00:31,200 --> 00:00:35,970
Så her: "Husk at en binær treet har noder som ligner på en lenket liste,

11
00:00:35,970 --> 00:00:38,150
bortsett fra i stedet for en pekeren er det to: en for venstre 'barn'

12
00:00:38,150 --> 00:00:41,950
og en for høyre 'barn'. "

13
00:00:41,950 --> 00:00:45,630
Så en binærtreet er akkurat som en lenket liste,

14
00:00:45,630 --> 00:00:47,910
bortsett struct kommer til å ha to pekere.

15
00:00:47,910 --> 00:00:51,390
Det er trinary trær, som kommer til å ha tre pekere,

16
00:00:51,390 --> 00:00:56,540
det er N-ær trær, som bare har en generisk peker

17
00:00:56,540 --> 00:01:00,320
at du må da malloc å være store nok til å ha

18
00:01:00,320 --> 00:01:04,840
nok pekere til alle mulige barn.

19
00:01:04,840 --> 00:01:08,200
Så binærtreet skjer bare for å ha et konstant antall av to.

20
00:01:08,200 --> 00:01:11,260
Hvis du vil, kan du gi en lenket liste som unary tre,

21
00:01:11,260 --> 00:01:15,360
men jeg tror ikke noen kaller det det.

22
00:01:15,360 --> 00:01:18,060
"Tegn en bokser-og-piler diagram av et binært tre node

23
00:01:18,060 --> 00:01:24,110
inneholder Nate favoritt nummer, 7, der hvert barn pekeren er null. "

24
00:01:24,110 --> 00:01:27,780
Så iPad-modus.

25
00:01:27,780 --> 00:01:30,280
>> Det kommer til å være ganske grei.

26
00:01:30,280 --> 00:01:36,150
Vi bare skal ha en node, vil jeg tegne det som en firkant.

27
00:01:36,150 --> 00:01:38,730
Og jeg vil trekke verdiene her.

28
00:01:38,730 --> 00:01:41,090
Så verdien vil gå inn her,

29
00:01:41,090 --> 00:01:44,770
og deretter ned her vi vil ha den venstre pekeren til venstre og høyre peker til høyre.

30
00:01:44,770 --> 00:01:50,430
Og det er veldig mye så konvensjon for å kalle det venstre og høyre, pekeren navn.

31
00:01:50,430 --> 00:01:52,460
Begge disse kommer til å være null.

32
00:01:52,460 --> 00:01:57,870
Det vil bare være null, og det vil bare være null.

33
00:01:57,870 --> 00:02:03,630
Okay. Så tilbake til her.

34
00:02:03,630 --> 00:02:05,700
"Med en lenket liste, vi bare måtte lagre en peker

35
00:02:05,700 --> 00:02:09,639
til den første noden i listen for å huske hele lenket liste, eller hele listen.

36
00:02:09,639 --> 00:02:11,650
Likeledes med trær, vi bare nødt til å lagre en peker

37
00:02:11,650 --> 00:02:13,420
til en enkelt node for å huske hele treet.

38
00:02:13,420 --> 00:02:15,980
Denne noden er calle de 'root' av treet.

39
00:02:15,980 --> 00:02:18,320
Bygge på diagrammet fra før eller tegne en ny

40
00:02:18,320 --> 00:02:21,690
slik at du har en bokser-og-piler skildring av et binært tre

41
00:02:21,690 --> 00:02:25,730
med verdien 7, deretter 3 i venstre,

42
00:02:25,730 --> 00:02:32,760
deretter 9 på høyre, og deretter 6 på høyre side av den 3 ".

43
00:02:32,760 --> 00:02:34,810
La oss se om jeg kan huske alle som i hodet mitt.

44
00:02:34,810 --> 00:02:37,670
Så dette kommer til å bli vår root opp her.

45
00:02:37,670 --> 00:02:41,600
Vi vil ha noen pekeren et sted, noe som vi kaller rot,

46
00:02:41,600 --> 00:02:45,140
og den peker til denne fyren.

47
00:02:45,140 --> 00:02:48,490
Nå for å lage en ny node,

48
00:02:48,490 --> 00:02:52,870
hva har vi, 3 på venstre?

49
00:02:52,870 --> 00:02:57,140
Så en ny node med 3, og det i utgangspunktet peker null.

50
00:02:57,140 --> 00:02:59,190
Jeg vil bare sette N.

51
00:02:59,190 --> 00:03:02,250
Nå ønsker vi å gjøre det gå til venstre for 7.

52
00:03:02,250 --> 00:03:06,840
Så vi endre denne pekeren til nå peker til denne fyren.

53
00:03:06,840 --> 00:03:12,420
Og vi gjør det samme. Vi ønsker en 9 over her

54
00:03:12,420 --> 00:03:14,620
som i utgangspunktet bare sier null.

55
00:03:14,620 --> 00:03:19,600
Vi kommer til å endre denne pekeren, pek på 9,

56
00:03:19,600 --> 00:03:23,310
og nå ønsker vi å sette 6 til høyre for tre.

57
00:03:23,310 --> 00:03:32,170
Så det kommer til å - lage en 6.

58
00:03:32,170 --> 00:03:34,310
Og at fyren vil peke dit.

59
00:03:34,310 --> 00:03:38,320
Okay. Så det er alt det ber oss om å gjøre.

60
00:03:38,320 --> 00:03:42,770
>> Nå la oss gå over noen terminologi.

61
00:03:42,770 --> 00:03:46,690
Vi har allerede snakket om hvordan roten av treet er den øverste node i treet.

62
00:03:46,690 --> 00:03:54,720
Den ene inneholder 7. Nodene nederst av treet kalles bladene.

63
00:03:54,720 --> 00:04:01,240
Enhver node som bare har null som sine barn er et blad.

64
00:04:01,240 --> 00:04:03,680
Så det er mulig, hvis vår binære treet er bare en enkelt node,

65
00:04:03,680 --> 00:04:10,130
at et tre er et blad, og det er det.

66
00:04:10,130 --> 00:04:12,060
"The 'høyde' av treet er antall hopp du har å gjøre

67
00:04:12,060 --> 00:04:16,620
å komme fra toppen til et blad. "

68
00:04:16,620 --> 00:04:18,640
Vi får inn, i et sekund, forskjellen

69
00:04:18,640 --> 00:04:21,940
mellom balanserte og ubalanserte binære trær,

70
00:04:21,940 --> 00:04:29,470
men for nå, den totale høyden av dette treet

71
00:04:29,470 --> 00:04:34,520
Jeg vil si er tre, men hvis du teller antall hopp

72
00:04:34,520 --> 00:04:39,710
du har å gjøre for å få til 9, så det er egentlig bare en høyde på 2.

73
00:04:39,710 --> 00:04:43,340
Akkurat nå er dette en ubalansert binærtreet,

74
00:04:43,340 --> 00:04:49,840
men vi vil snakket om balanse når den blir å være relevant.

75
00:04:49,840 --> 00:04:52,040
Så nå kan vi snakke om noder i et tre i form

76
00:04:52,040 --> 00:04:54,700
i forhold til de andre nodene i treet.

77
00:04:54,700 --> 00:04:59,730
Så nå har vi foreldre, barn, søsken, forfedre, og etterkommere.

78
00:04:59,730 --> 00:05:05,650
De er ganske sunn fornuft, hva de mener.

79
00:05:05,650 --> 00:05:09,610
Hvis vi spør - det er foreldre.

80
00:05:09,610 --> 00:05:12,830
Så hva er morselskap for 3?

81
00:05:12,830 --> 00:05:16,090
[Studenter] 7. >> Ja. Den av foreldrene er bare kommer til å være hva poeng til deg.

82
00:05:16,090 --> 00:05:20,510
Så hva er barn av 7?

83
00:05:20,510 --> 00:05:23,860
[Studenter] 3 og 9. >> Ja.

84
00:05:23,860 --> 00:05:26,460
Legg merke til at "barn" betyr bokstavelig barn,

85
00:05:26,460 --> 00:05:31,010
så 6 ville ikke gjelde, fordi det er som et barnebarn.

86
00:05:31,010 --> 00:05:35,540
Men så hvis vi går etterkommere, så hva er etterkommere av 7?

87
00:05:35,540 --> 00:05:37,500
[Studenter] 3, 6 og 9. >> Ja.

88
00:05:37,500 --> 00:05:42,330
Etterkommere av rotnoden kommer til å være alt i treet,

89
00:05:42,330 --> 00:05:47,950
bortsett fra kanskje rotnoden selv, hvis du ikke ønsker å tenke på at en etterkommer.

90
00:05:47,950 --> 00:05:50,750
Og til slutt, forfedre, så det er motsatt retning.

91
00:05:50,750 --> 00:05:55,740
Så hva er forfedrene til 6?

92
00:05:55,740 --> 00:05:58,920
[Studenter] 3 og 7. >> Ja. 9 er ikke inkludert.

93
00:05:58,920 --> 00:06:02,520
Det er bare den direkte linjen tilbake til roten

94
00:06:02,520 --> 00:06:13,230
kommer til å være deres forfedre.

95
00:06:13,230 --> 00:06:16,300
>> "Vi sier at en binær tre er" bestilt "hvis for hver node i treet,

96
00:06:16,300 --> 00:06:19,530
alle sine etterkommere på venstre har mindre verdier

97
00:06:19,530 --> 00:06:22,890
og alle de på høyre har større verdier.

98
00:06:22,890 --> 00:06:27,060
For eksempel er treet over bestilte, men det er ikke den eneste mulige bestilles arrangement. "

99
00:06:27,060 --> 00:06:30,180
Før vi kommer til det,

100
00:06:30,180 --> 00:06:36,420
en ordnet binærtreet er også kjent som et binært søketre.

101
00:06:36,420 --> 00:06:38,660
Her har vi tilfeldigvis kalle det et ordnet binærtreet,

102
00:06:38,660 --> 00:06:41,850
men jeg har aldri hørt det kalt en ordnet binærtreet før,

103
00:06:41,850 --> 00:06:46,650
og på en quiz er vi mye mer sannsynlig å sette binært søketre.

104
00:06:46,650 --> 00:06:49,250
De er en og samme,

105
00:06:49,250 --> 00:06:54,580
og det er viktig at du kjenner skillet mellom binære treet og binært søketre.

106
00:06:54,580 --> 00:06:58,830
En binær treet er bare et tre som peker på to ting.

107
00:06:58,830 --> 00:07:02,120
Hver node peker på to ting.

108
00:07:02,120 --> 00:07:06,310
Det er ingen resonnement om de verdiene som den peker til.

109
00:07:06,310 --> 00:07:11,370
Så liker over her, siden det er et binært søketre,

110
00:07:11,370 --> 00:07:14,030
Vi vet at hvis vi går igjen på 7,

111
00:07:14,030 --> 00:07:16,670
så alle de verdier som vi kan muligens nå

112
00:07:16,670 --> 00:07:19,310
ved å gå til venstre av 7 må være mindre enn 7.

113
00:07:19,310 --> 00:07:24,070
Legg merke til at alle de verdier som er mindre enn 7 er 3 og 6.

114
00:07:24,070 --> 00:07:26,040
De er alle til venstre for 7.

115
00:07:26,040 --> 00:07:29,020
Hvis vi går til høyre for 7, har alt å være større enn 7,

116
00:07:29,020 --> 00:07:33,220
så 9 er til høyre for 7, så vi bra.

117
00:07:33,220 --> 00:07:36,150
Dette er ikke tilfelle for et binært tre,

118
00:07:36,150 --> 00:07:40,020
for en vanlig binær tre kan vi bare 3 øverst, 7 til venstre,

119
00:07:40,020 --> 00:07:47,630
9 til venstre for 7, det er ingen bestilling av verdier overhodet.

120
00:07:47,630 --> 00:07:56,140
Nå vil vi faktisk ikke gjør dette fordi det er kjedelig og unødvendig,

121
00:07:56,140 --> 00:07:59,400
men "prøve å trekke så mange bestilte trær som du kan tenke på

122
00:07:59,400 --> 00:08:01,900
ved hjelp av tallene 7, 3, 9, og 6.

123
00:08:01,900 --> 00:08:06,800
Hvor mange forskjellige arrangementer er det? Hva er høyden av hver av dem? "

124
00:08:06,800 --> 00:08:10,480
>> Vi vil gjøre et par, men hovedideen er,

125
00:08:10,480 --> 00:08:16,530
dette er på ingen måte en unik representasjon av et binært tre som inneholder disse verdiene.

126
00:08:16,530 --> 00:08:22,760
Alt vi trenger er noen binærtreet som inneholder 7, 3, 6, og 9.

127
00:08:22,760 --> 00:08:25,960
En annen mulig gyldig en ville være roten er 3,

128
00:08:25,960 --> 00:08:30,260
gå til venstre, og det er 6, gå til venstre, og det er 7,

129
00:08:30,260 --> 00:08:32,730
gå til venstre, og det er 9.

130
00:08:32,730 --> 00:08:36,169
Det er en helt gyldig binært søketre.

131
00:08:36,169 --> 00:08:39,570
Det er ikke veldig nyttig, fordi det er akkurat som en lenket liste

132
00:08:39,570 --> 00:08:43,750
og alle disse pekerne er bare null.

133
00:08:43,750 --> 00:08:48,900
Men det er en gyldig treet. Ja?

134
00:08:48,900 --> 00:08:51,310
[Student] Ikke verdiene må være større på høyre?

135
00:08:51,310 --> 00:08:56,700
Eller er dette -? >> Disse Jeg mente å gå den andre veien.

136
00:08:56,700 --> 00:09:00,960
Det er også - ja, la oss slå det.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. God fangst.

138
00:09:07,770 --> 00:09:11,730
Det har fortsatt å adlyde hva et binært tre søk er ment å gjøre.

139
00:09:11,730 --> 00:09:15,650
Så alt til venstre må være mindre enn en gitt node.

140
00:09:15,650 --> 00:09:23,180
Vi kan bare flytte, si, dette 6 og sette det her.

141
00:09:23,180 --> 00:09:26,880
Nei, det kan vi ikke. Hvorfor får jeg gjøre det?

142
00:09:26,880 --> 00:09:35,350
La oss gjøre - her er 6, her er 7, 6 poeng til 3.

143
00:09:35,350 --> 00:09:39,290
Dette er fortsatt en gyldig binært søketre.

144
00:09:39,290 --> 00:09:49,260
Hva er galt hvis jeg - la oss se om jeg kan komme opp med en ordning.

145
00:09:49,260 --> 00:09:52,280
Ja, ok. Så hva er galt med dette treet?

146
00:09:52,280 --> 00:10:08,920
Jeg har vel allerede gitt deg et hint om at det er noe galt med den.

147
00:10:08,920 --> 00:10:14,430
Hvorfor får jeg gjøre det?

148
00:10:14,430 --> 00:10:18,510
Okay. Dette ser rimelig.

149
00:10:18,510 --> 00:10:22,590
Hvis vi ser på hver node, som 7, deretter til venstre av 7 er en 3.

150
00:10:22,590 --> 00:10:24,960
Så vi har 3, er det ting til høyre for 3 en 6.

151
00:10:24,960 --> 00:10:27,750
Og hvis man ser på 6, er det ting til høyre for 6 a 9.

152
00:10:27,750 --> 00:10:30,910
Så hvorfor er ikke dette en gyldig binært søketre?

153
00:10:30,910 --> 00:10:36,330
[Studenter] 9 er fortsatt til venstre for 7. >> Ja.

154
00:10:36,330 --> 00:10:43,710
Det må være sant at alle verdier kan muligens nå ved å gå til venstre for 7 er mindre enn 7.

155
00:10:43,710 --> 00:10:49,120
Hvis vi går igjen på 7, får vi til 3, og vi kan fortsatt komme til 6,

156
00:10:49,120 --> 00:10:52,520
Vi kan fortsatt komme til 9, men ved å ha gått mindre enn 7,

157
00:10:52,520 --> 00:10:55,070
Vi bør ikke være i stand til å få til et tall som er større enn 7.

158
00:10:55,070 --> 00:10:59,830
Så dette er ikke en gyldig binært søketre.

159
00:10:59,830 --> 00:11:02,330
>> Min bror hadde egentlig et intervju spørsmål

160
00:11:02,330 --> 00:11:07,760
som var utgangspunktet dette, bare koden opp noe å validere

161
00:11:07,760 --> 00:11:10,500
om et tre er et binært søketre,

162
00:11:10,500 --> 00:11:13,580
og så det første han gjorde var bare sjekke for å se

163
00:11:13,580 --> 00:11:17,020
hvis venstre og høyre er riktig, og deretter veksle der nede.

164
00:11:17,020 --> 00:11:19,700
Men du kan ikke bare gjøre det, du må holde styr

165
00:11:19,700 --> 00:11:22,550
av det faktum at nå som jeg har gått igjen på 7,

166
00:11:22,550 --> 00:11:26,340
alt i denne subtre må være mindre enn 7.

167
00:11:26,340 --> 00:11:28,430
Den korrekte algoritme må holde rede

168
00:11:28,430 --> 00:11:35,970
av de grenser som verdiene kan muligens falle igjen

169
00:11:35,970 --> 00:11:38,360
Vi vil ikke gå gjennom dem alle.

170
00:11:38,360 --> 00:11:41,630
Det er en fin tilbakefall forhold,

171
00:11:41,630 --> 00:11:44,810
selv om vi ikke har fått til disse, eller vi vil ikke komme til dem,

172
00:11:44,810 --> 00:11:47,030
definere hvor mange det faktisk er.

173
00:11:47,030 --> 00:11:53,180
Så det er 14 av dem.

174
00:11:53,180 --> 00:11:56,020
Ideen om hvordan du vil gjøre det er matematisk like,

175
00:11:56,020 --> 00:11:59,770
du kan plukke noen eneste en å være rotnoden,

176
00:11:59,770 --> 00:12:03,160
og hvis jeg plukker 7 for å være rotnoden,

177
00:12:03,160 --> 00:12:08,150
så er det, sier noen tall som kan gå være min venstre node,

178
00:12:08,150 --> 00:12:10,440
og det er noen tall som kan være min høyre node,

179
00:12:10,440 --> 00:12:15,090
men hvis jeg har n totale tallene, og beløpet som kan gå til venstre

180
00:12:15,090 --> 00:12:18,820
pluss beløpet som kan gå til høyre er n - 1.

181
00:12:18,820 --> 00:12:26,130
Så av de gjenværende tall, må de være i stand til å gå enten til venstre eller høyre.

182
00:12:26,130 --> 00:12:31,580
Det virker vanskelig at hvis jeg legger 3 første så alt må gå til venstre,

183
00:12:31,580 --> 00:12:35,080
men hvis jeg legger 7, så noen ting kan gå til venstre og noen ting kan gå til høyre.

184
00:12:35,080 --> 00:12:39,570
Og ved '3 første "mente jeg alt kan gå til høyre.

185
00:12:39,570 --> 00:12:42,350
Det er veldig, du må bare tenke på det som,

186
00:12:42,350 --> 00:12:47,980
hvor mange ting kan gå på neste nivå i treet.

187
00:12:47,980 --> 00:12:50,420
Og det kommer ut for å være 14, eller du kan tegne dem alle,

188
00:12:50,420 --> 00:12:54,650
og da vil du få 14.

189
00:12:54,650 --> 00:13:01,120
>> Kommer tilbake hit,

190
00:13:01,120 --> 00:13:03,510
"Bestilte binære trær er kult fordi vi kan søke gjennom dem

191
00:13:03,510 --> 00:13:06,910
i en svært lik måte å søke over en sortert array.

192
00:13:06,910 --> 00:13:10,120
For å gjøre dette, starter vi ved roten og jobbe oss ned treet

193
00:13:10,120 --> 00:13:13,440
mot blader, sjekke hver node verdier mot verdiene vi søker etter.

194
00:13:13,440 --> 00:13:15,810
Hvis gjeldende node verdi er mindre enn verdien vi leter etter,

195
00:13:15,810 --> 00:13:18,050
du går ved siden av noden rett barnet.

196
00:13:18,050 --> 00:13:20,030
Ellers går du til nodens venstre barn.

197
00:13:20,030 --> 00:13:22,800
På et tidspunkt, vil du enten finne verdien du leter etter, eller du kjører inn i en null,

198
00:13:22,800 --> 00:13:28,520
indikerer verdien ikke er i treet. "

199
00:13:28,520 --> 00:13:32,450
Jeg må tegne treet vi hadde før, det tar et sekund.

200
00:13:32,450 --> 00:13:38,280
Men vi ønsker å se opp om 6, 10, og en er i treet.

201
00:13:38,280 --> 00:13:49,180
Så hva det var, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
Numrene du ønsker å slå opp, ønsker vi å se opp 6.

203
00:13:52,730 --> 00:13:55,440
Hvordan denne algoritmen arbeid?

204
00:13:55,440 --> 00:14:03,040
Vel, vi har også noen rot pekeren til treet vårt.

205
00:14:03,040 --> 00:14:12,460
Og vi ville gå til roten og si, er denne verdien lik verdien vi leter etter?

206
00:14:12,460 --> 00:14:15,000
Så vi leter etter seks, så det er ikke like.

207
00:14:15,000 --> 00:14:20,140
Så vi holde det gående, og nå sier vi, ok, så 6 er mindre enn 7.

208
00:14:20,140 --> 00:14:23,940
Betyr det at vi ønsker å gå til venstre, eller ønsker vi å gå til høyre?

209
00:14:23,940 --> 00:14:27,340
[Student] Venstre. >> Ja.

210
00:14:27,340 --> 00:14:33,340
Det er betydelig enklere, er å tegne alt du trenger å gjøre en mulig node av treet

211
00:14:33,340 --> 00:14:37,760
og deretter lkke - i stedet for å prøve å tenke i hodet ditt,

212
00:14:37,760 --> 00:14:40,020
orden, hvis det er mindre, går jeg til venstre eller gå rett,

213
00:14:40,020 --> 00:14:43,030
bare se på dette bildet, er det helt klart at jeg må gå til venstre

214
00:14:43,030 --> 00:14:47,700
Hvis denne noden er større enn verdien som jeg leter etter.

215
00:14:47,700 --> 00:14:52,600
Slik at du går til venstre, nå er jeg på 3.

216
00:14:52,600 --> 00:14:57,770
Jeg vil - 3 er mindre enn verdien jeg ser etter, som er 6.

217
00:14:57,770 --> 00:15:03,420
Så vi går til høyre, og nå ender jeg opp på 6,

218
00:15:03,420 --> 00:15:07,380
som er verdien jeg leter etter, så jeg kommer tilbake sant.

219
00:15:07,380 --> 00:15:15,760
Den neste verdien jeg kommer til å se etter er 10 år.

220
00:15:15,760 --> 00:15:23,230
Okay. Så 10, nå, kommer til å - avskåret det - kommer til å følge roten.

221
00:15:23,230 --> 00:15:27,670
Nå er 10 kommer til å være større enn 7, så jeg ønsker å se til høyre.

222
00:15:27,670 --> 00:15:31,660
Jeg kommer til å komme hit, er 10 kommer til å være større enn 9,

223
00:15:31,660 --> 00:15:34,520
så jeg kommer til å ønske å se til høyre.

224
00:15:34,520 --> 00:15:42,100
Jeg kom hit, men over her nå er jeg på null.

225
00:15:42,100 --> 00:15:44,170
Hva gjør jeg hvis jeg treffer null?

226
00:15:44,170 --> 00:15:47,440
[Student] return false? >> Ja. Jeg fant ikke 10.

227
00:15:47,440 --> 00:15:49,800
1 kommer til å være et nesten identisk sak,

228
00:15:49,800 --> 00:15:51,950
bortsett fra det er bare kommer til å bli snudd, i stedet for å se

229
00:15:51,950 --> 00:15:56,540
ned på høyre side, jeg kommer til å se ned på venstre side.

230
00:15:56,540 --> 00:16:00,430
>> Nå tror jeg vi faktisk får til koden.

231
00:16:00,430 --> 00:16:04,070
Her er der - åpne opp CS50 apparatet og navigere deg der,

232
00:16:04,070 --> 00:16:07,010
men du kan også bare gjøre det i rommet.

233
00:16:07,010 --> 00:16:09,170
Det er sannsynligvis ideelt å gjøre det i rommet,

234
00:16:09,170 --> 00:16:13,760
fordi vi kan arbeide i verdensrommet.

235
00:16:13,760 --> 00:16:19,170
"Først vil vi trenge en ny type definisjon for et binært tre node inneholder int verdier.

236
00:16:19,170 --> 00:16:21,400
Bruke standardtekst typedef nedenfor,

237
00:16:21,400 --> 00:16:24,510
opprette en ny type definisjon for en node i et binært tre.

238
00:16:24,510 --> 00:16:27,930
Hvis du står fast. . . "Blah, blah, blah. Okay.

239
00:16:27,930 --> 00:16:30,380
Så la oss sette standardteksten her,

240
00:16:30,380 --> 00:16:41,630
typedef struct node, og node. Ja, ok.

241
00:16:41,630 --> 00:16:44,270
Så hva er de feltene vi kommer til å ønske i node vårt?

242
00:16:44,270 --> 00:16:46,520
[Student] Int og deretter to pekere?

243
00:16:46,520 --> 00:16:49,700
>> Int verdi, to pekere? Hvordan skriver jeg pekere?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. >> Jeg skal zoome inn Ja, så struct node * venstre,

245
00:16:58,440 --> 00:17:01,320
og struct node * rett.

246
00:17:01,320 --> 00:17:03,460
Og husk diskusjonen fra forrige gang,

247
00:17:03,460 --> 00:17:15,290
at dette gir ingen mening, gjør dette ingen mening,

248
00:17:15,290 --> 00:17:18,270
Dette gir ingen mening.

249
00:17:18,270 --> 00:17:25,000
Du trenger alt det for å definere denne rekursiv struct.

250
00:17:25,000 --> 00:17:27,970
Ok, så det er hva våre tre kommer til å se ut.

251
00:17:27,970 --> 00:17:37,670
Hvis vi gjorde en trinary tre, deretter en node kan se ut B1, B2, struct node * b3,

252
00:17:37,670 --> 00:17:43,470
der b er en gren - faktisk har jeg mer hørt det igjen, midten, høyre, men uansett.

253
00:17:43,470 --> 00:17:55,610
Vi bare bryr seg om binære, så rett, igjen.

254
00:17:55,610 --> 00:17:59,110
"Nå erklærer en global node * variabel for roten av treet."

255
00:17:59,110 --> 00:18:01,510
Så vi ikke kommer til å gjøre det.

256
00:18:01,510 --> 00:18:08,950
For å gjøre ting litt vanskeligere og mer generalisert,

257
00:18:08,950 --> 00:18:11,570
Vi vil ikke ha en global node variabel.

258
00:18:11,570 --> 00:18:16,710
I stedet, main vil vi erklære alle våre node ting,

259
00:18:16,710 --> 00:18:20,500
og det betyr at under, når vi begynner å kjøre

260
00:18:20,500 --> 00:18:23,130
vår inneholder funksjonen og vår innsats funksjon,

261
00:18:23,130 --> 00:18:27,410
i stedet for vår inneholder fungerer bare ved hjelp av denne globale node variabel,

262
00:18:27,410 --> 00:18:34,280
vi kommer til å ha det ta som et argument treet som vi ønsker den skal behandle.

263
00:18:34,280 --> 00:18:36,650
Å ha den globale variabelen var ment å gjøre ting enklere.

264
00:18:36,650 --> 00:18:42,310
Vi kommer til å gjøre ting vanskeligere.

265
00:18:42,310 --> 00:18:51,210
Nå tar et minutt eller så å bare gjøre denne typen ting,

266
00:18:51,210 --> 00:18:57,690
hvor innsiden av hoved du ønsker å opprette dette treet, og det er alt du ønsker å gjøre.

267
00:18:57,690 --> 00:19:04,530
Prøv og konstruere dette treet i din viktigste funksjon.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Så du trenger ikke engang å ha bygget treet hele veien ennå.

269
00:19:47,610 --> 00:19:49,840
Men noen har noe jeg kunne trekke opp

270
00:19:49,840 --> 00:20:03,130
å vise hvordan man kan begynne å konstruere et slikt tre?

271
00:20:03,130 --> 00:20:08,080
[Student] Noens banging, prøver å komme seg ut.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Alle komfortabel med sin tre konstruksjon?

273
00:20:13,100 --> 00:20:15,520
[Student] Sure. Det er ikke gjort. >> Det er greit. Vi kan bare fullføre -

274
00:20:15,520 --> 00:20:26,860
oh, kan du lagre det? Hurra.

275
00:20:26,860 --> 00:20:32,020
Så her har vi - oh, jeg er litt avskåret.

276
00:20:32,020 --> 00:20:34,770
Jeg zoomet inn?

277
00:20:34,770 --> 00:20:37,730
Zoome inn, bla ut. >> Jeg har et spørsmål. >> Ja?

278
00:20:37,730 --> 00:20:44,410
[Student] Når du definerer struct, er ting som initialiseres til noe?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Nei >> Ok. Så du ville ha til å initialisere -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nei Når du definerer, eller når du deklarerer en struct,

281
00:20:50,450 --> 00:20:55,600
det er ikke initialisert som standard, det er akkurat som om du erklærer en int.

282
00:20:55,600 --> 00:20:59,020
Det er akkurat det samme. Det er som hver av de enkelte felt

283
00:20:59,020 --> 00:21:04,460
kan ha en søppel verdi i den. >> Og er det mulig å definere - eller å erklære en struct

284
00:21:04,460 --> 00:21:07,740
på en måte som det gjør initialisere dem?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ja. Så snarvei initialisering syntaks

286
00:21:13,200 --> 00:21:18,660
kommer til å se ut som -

287
00:21:18,660 --> 00:21:22,200
Det er to måter vi kan gjøre dette. Jeg tror vi bør samle det

288
00:21:22,200 --> 00:21:25,840
å sørge for at Clang også gjør dette.

289
00:21:25,840 --> 00:21:28,510
Den rekkefølgen som argumentene som kommer i struct,

290
00:21:28,510 --> 00:21:32,170
du setter som rekkefølgen av argumenter innsiden av disse klammeparentes.

291
00:21:32,170 --> 00:21:35,690
Så hvis du ønsker å initialisere den til 9 og venstre bli null og deretter til høyre være null,

292
00:21:35,690 --> 00:21:41,570
det ville være 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternativet er, og redaktøren liker ikke denne syntaksen,

294
00:21:47,890 --> 00:21:50,300
og det tror jeg vil ha en ny blokk,

295
00:21:50,300 --> 00:22:01,800
men alternativet er noe som -

296
00:22:01,800 --> 00:22:04,190
her, vil jeg sette den på en ny linje.

297
00:22:04,190 --> 00:22:09,140
Du kan eksplisitt si, jeg glemmer den eksakte syntaks.

298
00:22:09,140 --> 00:22:13,110
Så du kan eksplisitt løse dem ved navn, og sier:

299
00:22:13,110 --> 00:22:21,570
. C, eller. Verdi = 9,. Venstre = NULL.

300
00:22:21,570 --> 00:22:24,540
Jeg gjetter disse må være komma.

301
00:22:24,540 --> 00:22:29,110
. Høyre = NULL, så denne måten du ikke

302
00:22:29,110 --> 00:22:33,780
egentlig trenger å vite rekkefølgen på struct,

303
00:22:33,780 --> 00:22:36,650
og når du leser dette, er det mye mer eksplisitt

304
00:22:36,650 --> 00:22:41,920
om hva verdien som blir initialisert til.

305
00:22:41,920 --> 00:22:44,080
>> Dette skjer for å være en av de tingene som -

306
00:22:44,080 --> 00:22:49,100
så, for det meste, C + + er et overordnet sett C.

307
00:22:49,100 --> 00:22:54,160
Du kan ta C-kode, flytte den over til C + +, og det bør utarbeide.

308
00:22:54,160 --> 00:22:59,570
Dette er en av de tingene som C + + ikke støtter, slik at folk har en tendens til ikke å gjøre det.

309
00:22:59,570 --> 00:23:01,850
Jeg vet ikke om det er den eneste grunnen til at folk har en tendens til ikke å gjøre det,

310
00:23:01,850 --> 00:23:10,540
men saken der jeg trengte å bruke den trengte å jobbe med C + + og så jeg ikke kunne bruke dette.

311
00:23:10,540 --> 00:23:14,000
Et annet eksempel på noe som ikke fungerer med C + + er

312
00:23:14,000 --> 00:23:16,940
hvordan malloc returnerer en "void *," teknisk,

313
00:23:16,940 --> 00:23:20,200
men du kan bare si char * x = malloc uansett,

314
00:23:20,200 --> 00:23:22,840
og den vil automatisk bli kastet til en char *.

315
00:23:22,840 --> 00:23:25,450
At automatisk cast skjer ikke i C + +.

316
00:23:25,450 --> 00:23:28,150
Det ville ikke kompilere, og du vil eksplisitt trenger å si

317
00:23:28,150 --> 00:23:34,510
char *, malloc, uansett, å kaste den til en char *.

318
00:23:34,510 --> 00:23:37,270
Det er ikke mange ting som C og C + + er uenige om,

319
00:23:37,270 --> 00:23:40,620
men de er to.

320
00:23:40,620 --> 00:23:43,120
Så vi vil gå med denne syntaksen.

321
00:23:43,120 --> 00:23:46,150
Men selv om vi ikke gå med på at syntaks,

322
00:23:46,150 --> 00:23:49,470
hva er - kan være galt med dette?

323
00:23:49,470 --> 00:23:52,170
[Student] Jeg trenger ikke å dereference det? >> Ja.

324
00:23:52,170 --> 00:23:55,110
Husk at pilen har en implisitt dereferanse,

325
00:23:55,110 --> 00:23:58,230
og så når vi bare gjøre med en struct,

326
00:23:58,230 --> 00:24:04,300
vi ønsker å bruke. å få på en felt innsiden av struct.

327
00:24:04,300 --> 00:24:07,200
Og den eneste gangen vi bruker pil er når vi ønsker å gjøre -

328
00:24:07,200 --> 00:24:13,450
vel, er arrow tilsvarer -

329
00:24:13,450 --> 00:24:17,020
det er hva det ville ha betydd hvis jeg brukte pil.

330
00:24:17,020 --> 00:24:24,600
Alle pilen betyr er, dereferanse dette, nå er jeg på en struct, og jeg kan få feltet.

331
00:24:24,600 --> 00:24:28,040
Enten få feltet direkte eller dereferanse og få felt -

332
00:24:28,040 --> 00:24:30,380
Jeg antar at dette bør være verdi.

333
00:24:30,380 --> 00:24:33,910
Men her jeg arbeider med bare en struct, ikke en peker til en struct,

334
00:24:33,910 --> 00:24:38,780
og så jeg kan ikke bruke pilen.

335
00:24:38,780 --> 00:24:47,510
Men denne typen ting vi kan gjøre for alle noder.

336
00:24:47,510 --> 00:24:55,790
Herregud.

337
00:24:55,790 --> 00:25:09,540
Dette er 6, 7 og 3.

338
00:25:09,540 --> 00:25:16,470
Da kan vi sette opp avdelinger i treet vårt, kan vi ha 7 -

339
00:25:16,470 --> 00:25:21,650
Vi kan ha, bør dens venstre peke til tre.

340
00:25:21,650 --> 00:25:25,130
Så hvordan gjør vi det?

341
00:25:25,130 --> 00:25:29,320
[Studenter, uforståelig] >> Ja. Adressen til node3,

342
00:25:29,320 --> 00:25:34,170
og hvis du ikke har adresse, så det bare ikke ville kompilere.

343
00:25:34,170 --> 00:25:38,190
Men husk at disse er pekere til de neste noder.

344
00:25:38,190 --> 00:25:44,930
Retten skal peke til 9,

345
00:25:44,930 --> 00:25:53,330
og 3 skal peke på høyre til 6.

346
00:25:53,330 --> 00:25:58,480
Jeg tror dette er alle satt. Eventuelle kommentarer eller spørsmål?

347
00:25:58,480 --> 00:26:02,060
[Student, uforståelig] Roten skal være 7.

348
00:26:02,060 --> 00:26:08,210
Vi kan bare si node * ptr =

349
00:26:08,210 --> 00:26:14,160
eller rot, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> For vårt formål, vi kommer til å være håndtere insert,

351
00:26:20,730 --> 00:26:25,490
så vi kommer til å ønske å skrive en funksjon for å sette inn dette binærtreet

352
00:26:25,490 --> 00:26:34,230
og innsatsen er uunngåelig kommer til å ringe malloc å opprette en ny node for dette treet.

353
00:26:34,230 --> 00:26:36,590
Så ting kommer til å bli rotete med det faktum at noen noder

354
00:26:36,590 --> 00:26:38,590
er for tiden på stakken

355
00:26:38,590 --> 00:26:43,680
og andre noder kommer til å ende opp på haugen når vi setter dem.

356
00:26:43,680 --> 00:26:47,640
Dette er helt gyldig, men den eneste grunnen

357
00:26:47,640 --> 00:26:49,600
vi er i stand til å gjøre dette på stakken

358
00:26:49,600 --> 00:26:51,840
er fordi det er en så contrived eksempel på at vi vet

359
00:26:51,840 --> 00:26:56,360
treet er ment å være konstruert som 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Hvis vi ikke har dette, så vi ikke ville ha til malloc i første omgang.

361
00:27:02,970 --> 00:27:06,160
Som vi skal se litt senere, bør vi malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Akkurat nå er det helt rimelig å sette på stakken,

363
00:27:08,570 --> 00:27:14,750
men la oss endre dette til en malloc gjennomføring.

364
00:27:14,750 --> 00:27:17,160
Slik at hver av disse er nå kommer til å være noe som

365
00:27:17,160 --> 00:27:24,240
node * node9 = malloc (sizeof (node)).

366
00:27:24,240 --> 00:27:28,040
Og nå er vi nødt til å gjøre vår sjekk.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Jeg ønsker ikke at -

368
00:27:34,010 --> 00:27:40,950
returnere 1, og da kan vi gjøre node9-> fordi nå er det en peker,

369
00:27:40,950 --> 00:27:45,300
value = 6, node9-> venstre = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> høyre = NULL,

371
00:27:48,930 --> 00:27:51,410
og vi er nødt til å gjøre det for hver av disse nodene.

372
00:27:51,410 --> 00:27:57,490
Så i stedet, la oss si det på innsiden av en egen funksjon.

373
00:27:57,490 --> 00:28:00,620
La oss kalle det node * build_node,

374
00:28:00,620 --> 00:28:09,050
og dette er noe som ligner på APIer vi sørge for Huffman koding.

375
00:28:09,050 --> 00:28:12,730
Vi gir deg initializer funksjoner for et tre

376
00:28:12,730 --> 00:28:20,520
og Deconstructor "funksjoner" for disse trærne, og det samme for skog.

377
00:28:20,520 --> 00:28:22,570
>> Så her vi kommer til å ha en initializer funksjon

378
00:28:22,570 --> 00:28:25,170
å bare bygge en node for oss.

379
00:28:25,170 --> 00:28:29,320
Og det kommer til å se ganske mye akkurat som dette.

380
00:28:29,320 --> 00:28:32,230
Og jeg selv kommer til å være lat og ikke endre navnet på variabelen,

381
00:28:32,230 --> 00:28:34,380
selv om node9 gir ingen mening lenger.

382
00:28:34,380 --> 00:28:38,610
Oh, I guess node9 verdi ikke skulle ha vært seks.

383
00:28:38,610 --> 00:28:42,800
Nå kan vi gå tilbake node9.

384
00:28:42,800 --> 00:28:49,550
Og her vi bør gå tilbake null.

385
00:28:49,550 --> 00:28:52,690
Alle er enige om at build-a-node funksjon?

386
00:28:52,690 --> 00:28:59,780
Så nå kan vi bare kalle det å bygge noen node med en gitt verdi og null pekere.

387
00:28:59,780 --> 00:29:09,750
Nå kan vi kalle det, kan vi gjøre node * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Og la oss gjøre. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
Og nå ønsker vi å sette opp de samme pekere,

391
00:29:39,330 --> 00:29:42,470
bortsett fra nå alt er allerede i form av pekere

392
00:29:42,470 --> 00:29:48,480
så ikke lenger trenger adressen.

393
00:29:48,480 --> 00:29:56,300
Okay. Så hva er det siste jeg ønsker å gjøre?

394
00:29:56,300 --> 00:30:03,850
Det er en feilkontroll som jeg ikke gjør.

395
00:30:03,850 --> 00:30:06,800
Hva bygger node retur?

396
00:30:06,800 --> 00:30:11,660
[Student, uforståelig] >> Ja. Hvis malloc mislyktes, vil den komme tilbake null.

397
00:30:11,660 --> 00:30:16,460
Så jeg kommer til å lazily sette det ned her i stedet for å gjøre en betingelse for hver.

398
00:30:16,460 --> 00:30:22,320
If (node9 == NULL, eller - enda enklere,

399
00:30:22,320 --> 00:30:28,020
Dette tilsvarer bare hvis ikke node9.

400
00:30:28,020 --> 00:30:38,310
Så hvis ikke node9, eller ikke node6, eller ikke node3, eller ikke node7, tilbake 1.

401
00:30:38,310 --> 00:30:42,850
Kanskje vi bør skrive malloc mislyktes, eller noe.

402
00:30:42,850 --> 00:30:46,680
[Student] Er falsk lik null også?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Enhver null verdi er falsk.

404
00:30:51,290 --> 00:30:53,920
Så null er en null verdi.

405
00:30:53,920 --> 00:30:56,780
Zero er et null. Falsk er en nullverdi.

406
00:30:56,780 --> 00:31:02,130
Noen - ganske mye bare 2 null verdier er null og null,

407
00:31:02,130 --> 00:31:07,900
falsk er bare hash definert som null.

408
00:31:07,900 --> 00:31:13,030
Dette gjelder også hvis vi erklærer global variabel.

409
00:31:13,030 --> 00:31:17,890
Hvis vi hadde node * rot her oppe,

410
00:31:17,890 --> 00:31:24,150
da - den fine ting om globale variabler er at de alltid har en initial verdi.

411
00:31:24,150 --> 00:31:27,500
Det er ikke sant av funksjoner, hvor innsiden av her,

412
00:31:27,500 --> 00:31:34,870
hvis vi har, som, node * eller node x.

413
00:31:34,870 --> 00:31:37,380
Vi har ingen anelse om hva x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
eller vi kan skrive dem ut, og de kan være vilkårlig.

415
00:31:40,700 --> 00:31:44,980
Det er ikke sant av globale variabler.

416
00:31:44,980 --> 00:31:47,450
Så node rot eller node x.

417
00:31:47,450 --> 00:31:53,410
Som standard, alt som er global, hvis ikke eksplisitt initialisert til en viss verdi,

418
00:31:53,410 --> 00:31:57,390
har null verdi som verdi.

419
00:31:57,390 --> 00:32:01,150
Så her, node * rot, har vi ikke eksplisitt initialisere den til noe,

420
00:32:01,150 --> 00:32:06,350
så standardverdien vil være null, som er det null verdi av pekere.

421
00:32:06,350 --> 00:32:11,870
Standardverdien av x kommer til å bety at x.value er null,

422
00:32:11,870 --> 00:32:14,260
x.left er null, og x.right er null.

423
00:32:14,260 --> 00:32:21,070
Så siden det er en struct, vil alle feltene i struct være nullverdier.

424
00:32:21,070 --> 00:32:24,410
Vi trenger ikke å bruke den her, skjønt.

425
00:32:24,410 --> 00:32:27,320
[Student] De structs er annerledes enn andre variabler, og de andre variablene er

426
00:32:27,320 --> 00:32:31,400
søppel verdier, disse er nuller?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Andre verdier også. Så i x, vil x være null.

428
00:32:36,220 --> 00:32:40,070
Hvis det er på global omfang, har det en initial verdi. >> Ok.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Enten den opprinnelige verdien du gav den eller null.

430
00:32:48,950 --> 00:32:53,260
Jeg tror det tar seg av alt dette.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Så den neste delen av spørsmålet spør,

432
00:32:58,390 --> 00:33:01,260
"Nå ønsker vi å skrive en funksjon som heter inneholder

433
00:33:01,260 --> 00:33:04,930
med en prototype av bool inneholder int verdi. "

434
00:33:04,930 --> 00:33:08,340
Vi kommer ikke til å gjøre bool inneholder int verdi.

435
00:33:08,340 --> 00:33:15,110
Vår prototype kommer til å se ut som

436
00:33:15,110 --> 00:33:22,380
bool inneholder (int verdi.

437
00:33:22,380 --> 00:33:24,490
Og så er vi også kommer til å passere det treet

438
00:33:24,490 --> 00:33:28,870
at det bør sjekke for å se om det har den verdien.

439
00:33:28,870 --> 00:33:38,290
Så node * tree). Okay.

440
00:33:38,290 --> 00:33:44,440
Og så kan vi kalle det med noe sånt som,

441
00:33:44,440 --> 00:33:46,090
kanskje vi ønsker å printf eller noe.

442
00:33:46,090 --> 00:33:51,040
Inneholder 6, vår rot.

443
00:33:51,040 --> 00:33:54,300
Det burde returnere en eller sant,

444
00:33:54,300 --> 00:33:59,390
mens inneholder 5 root skal returnere false.

445
00:33:59,390 --> 00:34:02,690
Så ta et sekund å gjennomføre dette.

446
00:34:02,690 --> 00:34:06,780
Du kan gjøre det enten iterativt eller rekursivt.

447
00:34:06,780 --> 00:34:09,739
Det fine med måten vi har satt opp ting er at

448
00:34:09,739 --> 00:34:12,300
det gir seg til vår rekursiv løsning mye enklere

449
00:34:12,300 --> 00:34:14,719
enn den globale variable måte gjorde.

450
00:34:14,719 --> 00:34:19,750
Fordi hvis vi bare har inneholder int verdi, så vi har ingen måte å recursing ned undertreene.

451
00:34:19,750 --> 00:34:24,130
Vi må ha en egen hjelper funksjon som recurses ned undertrær for oss.

452
00:34:24,130 --> 00:34:29,610
Men siden vi har endret det til å ta treet som et argument,

453
00:34:29,610 --> 00:34:32,760
som det bør har alltid vært i første omgang,

454
00:34:32,760 --> 00:34:35,710
Nå kan vi Recurse lettere.

455
00:34:35,710 --> 00:34:38,960
Så iterativ eller rekursive, vil vi gå over begge,

456
00:34:38,960 --> 00:34:46,139
men vi får se at rekursive ender opp med å bli ganske lett.

457
00:34:59,140 --> 00:35:02,480
Okay. Har noen noe vi kan jobbe med?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Jeg har en iterativ løsning. >> Greit, iterativ.

459
00:35:12,000 --> 00:35:16,030
Ok, ser dette bra.

460
00:35:16,030 --> 00:35:18,920
Så, ønsker å lede oss gjennom det?

461
00:35:18,920 --> 00:35:25,780
[Student] Sure. Så jeg satt en temp variabel å få den første noden i treet.

462
00:35:25,780 --> 00:35:28,330
Og da jeg bare sløyfe mens temp ikke lik null,

463
00:35:28,330 --> 00:35:31,700
så mens var fortsatt i treet, antar jeg.

464
00:35:31,700 --> 00:35:35,710
Og hvis verdi er lik den verdi som temp peker til,

465
00:35:35,710 --> 00:35:37,640
da den returnerer den verdien.

466
00:35:37,640 --> 00:35:40,210
Ellers sjekker den om det er på høyre eller venstre side.

467
00:35:40,210 --> 00:35:43,400
Hvis du noen gang får en situasjon der det ikke er mer tre,

468
00:35:43,400 --> 00:35:47,330
så det returnerer - det kommer loopen og returnerer false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. Så det virker bra.

470
00:35:52,190 --> 00:35:58,470
Noen som har noen kommentarer til noe?

471
00:35:58,470 --> 00:36:02,400
Jeg har ingen korrekthet kommentarer i det hele tatt.

472
00:36:02,400 --> 00:36:11,020
Det eneste vi kan gjøre er denne fyren.

473
00:36:11,020 --> 00:36:21,660
Å, det kommer til å gå litt ovale.

474
00:36:21,660 --> 00:36:33,460
Jeg skal fikse det opp. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Alle bør huske hvordan trefoldig fungerer.

476
00:36:37,150 --> 00:36:38,610
Det har definitivt vært quizer i det siste

477
00:36:38,610 --> 00:36:41,170
som gir deg en funksjon med en trefoldig operatør,

478
00:36:41,170 --> 00:36:45,750
og si, oversette dette, gjør noe som ikke bruker trefoldig.

479
00:36:45,750 --> 00:36:49,140
Så dette er en veldig vanlig tilfelle av når jeg ville tenke å bruke trefoldig,

480
00:36:49,140 --> 00:36:54,610
der hvis noen betingelse sette en variabel til noe,

481
00:36:54,610 --> 00:36:58,580
andre satt den samme variabelen til noe annet.

482
00:36:58,580 --> 00:37:03,390
Det er noe som svært ofte kan bli forvandlet til denne typen ting

483
00:37:03,390 --> 00:37:14,420
der satt den variabelen til dette - eller, vel, er dette sant? Da er dette, annet denne.

484
00:37:14,420 --> 00:37:18,550
[Student] Den første er hvis det er sant, ikke sant?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. Slik jeg alltid lest det er, lik temp verdi større enn temp verdi,

486
00:37:25,570 --> 00:37:30,680
så dette, annet denne. Det er stille et spørsmål.

487
00:37:30,680 --> 00:37:35,200
Er det større? Deretter må du gjøre det første. Andre gjøre andre ting.

488
00:37:35,200 --> 00:37:41,670
Jeg nesten alltid - tykktarmen, jeg bare - i hodet mitt, jeg leste som ellers.

489
00:37:41,670 --> 00:37:47,180
>> Har noen en rekursiv løsning?

490
00:37:47,180 --> 00:37:49,670
Okay. Dette skal vi - det kan allerede være stor,

491
00:37:49,670 --> 00:37:53,990
men vi kommer til å gjøre det enda bedre.

492
00:37:53,990 --> 00:37:58,720
Dette er ganske mye de samme idé.

493
00:37:58,720 --> 00:38:03,060
Det er bare, vel, vil du forklare?

494
00:38:03,060 --> 00:38:08,340
[Student] Sure. Så vi å sørge for at treet ikke er null først,

495
00:38:08,340 --> 00:38:13,380
fordi hvis treet er null så det kommer til å returnere falsk fordi vi ikke har funnet det.

496
00:38:13,380 --> 00:38:19,200
Og hvis det er fortsatt et tre, går vi inn i - vi først sjekke om det er den gjeldende node.

497
00:38:19,200 --> 00:38:23,740
Returnere true hvis det er, og hvis ikke vi Recurse på venstre eller høyre.

498
00:38:23,740 --> 00:38:25,970
Høres det riktig? >> Mm-hmm. (Avtalen)

499
00:38:25,970 --> 00:38:33,880
Så merke til at dette er nesten - strukturelt veldig lik den iterativ løsning.

500
00:38:33,880 --> 00:38:38,200
Det er bare at i stedet for recursing, hadde vi en stund loop.

501
00:38:38,200 --> 00:38:40,840
Og base case her hvor tre er ikke lik null

502
00:38:40,840 --> 00:38:44,850
var tilstanden under som vi brøt ut av mens loop.

503
00:38:44,850 --> 00:38:50,200
De er veldig like. Men vi kommer til å ta dette ett skritt videre.

504
00:38:50,200 --> 00:38:54,190
Nå gjør vi det samme her.

505
00:38:54,190 --> 00:38:57,680
Legg merke til vi er tilbake det samme i begge disse linjene,

506
00:38:57,680 --> 00:39:00,220
med unntak av én argument er annerledes.

507
00:39:00,220 --> 00:39:07,950
Så vi kommer til å gjøre det til en trefoldig.

508
00:39:07,950 --> 00:39:13,790
Jeg traff alternativ noe, og det gjorde et symbol. Okay.

509
00:39:13,790 --> 00:39:21,720
Så vi kommer til å returnere inneholder det.

510
00:39:21,720 --> 00:39:28,030
Dette blir å være flere linjer, vel, zoomet inn det er.

511
00:39:28,030 --> 00:39:31,060
Vanligvis, som et stilistisk ting, tror jeg ikke mange mennesker

512
00:39:31,060 --> 00:39:38,640
sette et mellomrom etter pilen, men jeg antar at hvis du er konsekvent, det er greit.

513
00:39:38,640 --> 00:39:44,320
Hvis verdien er mindre enn tre verdi, ønsker vi å Recurse på treet til venstre,

514
00:39:44,320 --> 00:39:53,890
annet vi ønsker å Recurse på treet rett.

515
00:39:53,890 --> 00:39:58,610
Så det var trinn en til å gjøre dette ser mindre.

516
00:39:58,610 --> 00:40:02,660
Trinn to for å gjøre dette ser mindre -

517
00:40:02,660 --> 00:40:09,150
Vi kan skille dette til flere linjer.

518
00:40:09,150 --> 00:40:16,500
Okay. Trinn to for å gjøre det ser mindre er her,

519
00:40:16,500 --> 00:40:25,860
så returverdi lik tre verdi, eller som inneholder hva.

520
00:40:25,860 --> 00:40:28,340
>> Dette er en viktig ting.

521
00:40:28,340 --> 00:40:30,860
Jeg er ikke sikker på om han sa det eksplisitt i klassen,

522
00:40:30,860 --> 00:40:34,740
men det heter kortslutning evaluering.

523
00:40:34,740 --> 00:40:41,060
Ideen her er verdi == tre verdi.

524
00:40:41,060 --> 00:40:49,960
Hvis det er sant, så er dette sant, og vi ønsker å 'eller' det med alt som er over her.

525
00:40:49,960 --> 00:40:52,520
Så uten engang å tenke på det som er over her,

526
00:40:52,520 --> 00:40:55,070
hva er hele uttrykket kommer til å returnere?

527
00:40:55,070 --> 00:40:59,430
[Student] True? >> Ja, fordi sann av noe,

528
00:40:59,430 --> 00:41:04,990
or'd - eller sann or'd med noe er nødvendigvis sant.

529
00:41:04,990 --> 00:41:08,150
Så så snart vi ser returverdi = tre verdi,

530
00:41:08,150 --> 00:41:10,140
vi bare kommer til å returnere true.

531
00:41:10,140 --> 00:41:15,710
Ikke engang tenkt å Recurse inneholder ytterligere ned linjen.

532
00:41:15,710 --> 00:41:20,980
Vi kan ta dette ett skritt videre.

533
00:41:20,980 --> 00:41:29,490
Tilbake treet ikke lik null, og alt dette.

534
00:41:29,490 --> 00:41:32,650
Det gjorde det en en-linje funksjon.

535
00:41:32,650 --> 00:41:36,790
Dette er også et eksempel på kortslutning evaluering.

536
00:41:36,790 --> 00:41:40,680
Men nå er det den samme ideen -

537
00:41:40,680 --> 00:41:47,320
i stedet for - så hvis treet ikke lik null - eller, vel,

538
00:41:47,320 --> 00:41:49,580
hvis treet ikke lik null, som er det dårlig sak,

539
00:41:49,580 --> 00:41:54,790
hvis treet er lik null, så den første betingelsen kommer til å være falsk.

540
00:41:54,790 --> 00:42:00,550
Så falske anded med noe kommer til å være hva?

541
00:42:00,550 --> 00:42:04,640
[Student] False. >> Ja. Dette er den andre halvparten av kortslutning evaluering,

542
00:42:04,640 --> 00:42:10,710
der hvis treet ikke lik null, da vi ikke kommer til å selv gå -

543
00:42:10,710 --> 00:42:14,930
eller hvis treet ikke lik null, da vi ikke kommer til å gjøre verdien == tre verdi.

544
00:42:14,930 --> 00:42:17,010
Vi bare kommer til å umiddelbart returnere falsk.

545
00:42:17,010 --> 00:42:20,970
Som er viktig, siden hvis det ikke kortslutning vurdere,

546
00:42:20,970 --> 00:42:25,860
så hvis treet ikke lik null, er denne andre betingelsen skal SEG utsette,

547
00:42:25,860 --> 00:42:32,510
fordi tree-> verdi dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Så det er det. Kan gjøre dette - skifte en gang over.

549
00:42:40,490 --> 00:42:44,840
Dette er en veldig vanlig ting også, ikke gjør dette en tråd med dette

550
00:42:44,840 --> 00:42:49,000
men det er en vanlig ting i forhold, kanskje ikke akkurat her,

551
00:42:49,000 --> 00:42:59,380
men hvis (tre! = NULL, og tre-> verdi == verdi), gjøre hva.

552
00:42:59,380 --> 00:43:01,560
Dette er en svært vanlig tilstand, der i stedet for å ha

553
00:43:01,560 --> 00:43:06,770
å bryte denne inn i to ifs, der liker, er treet null?

554
00:43:06,770 --> 00:43:11,780
Ok, det er ikke null, så nå er det tre verdi lik verdi? Gjør dette.

555
00:43:11,780 --> 00:43:17,300
I stedet denne tilstanden, vil dette aldri SEG feil

556
00:43:17,300 --> 00:43:21,220
fordi det vil bryte ut dersom dette skjer for å være null.

557
00:43:21,220 --> 00:43:24,000
Vel, jeg antar at hvis treet er en helt ugyldig peker, kan det fortsatt SEG feil,

558
00:43:24,000 --> 00:43:26,620
men det kan ikke SEG feil hvis treet er null.

559
00:43:26,620 --> 00:43:32,900
Hvis det var null, ville det bryte ut før du noensinne derefereres pekeren i første omgang.

560
00:43:32,900 --> 00:43:35,000
[Student] Er dette kalles lat evaluering?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy evaluering er en egen ting.

562
00:43:40,770 --> 00:43:49,880
Lat evaluering er mer som du ber om en verdi,

563
00:43:49,880 --> 00:43:54,270
du be om å beregne en verdi, type, men du trenger ikke det umiddelbart.

564
00:43:54,270 --> 00:43:59,040
Så før du faktisk trenger det, er det ikke evaluert.

565
00:43:59,040 --> 00:44:03,920
Dette er ikke akkurat det samme, men i Huffman pset,

566
00:44:03,920 --> 00:44:06,520
det står at vi "dovent" skriver.

567
00:44:06,520 --> 00:44:08,670
Grunnen til at vi gjør det er fordi vi faktisk bufring skrive -

568
00:44:08,670 --> 00:44:11,820
Vi ønsker ikke å skrive individuelle biter av gangen,

569
00:44:11,820 --> 00:44:15,450
eller individuelle bytes gangen, vi i stedet ønsker å få en del av bytes.

570
00:44:15,450 --> 00:44:19,270
Så når vi har en del av bytes, så får vi skrive det ut.

571
00:44:19,270 --> 00:44:22,640
Selv om du ber om det å skrive - og fwrite og fread gjøre det samme slags ting.

572
00:44:22,640 --> 00:44:26,260
De buffer din leser og skriver.

573
00:44:26,260 --> 00:44:31,610
Selv om du spør om det å skrive med en gang, det vil sannsynligvis ikke.

574
00:44:31,610 --> 00:44:34,540
Og du kan ikke være sikker på at ting kommer til å bli skrevet

575
00:44:34,540 --> 00:44:37,540
før du ringer hfclose eller hva det er,

576
00:44:37,540 --> 00:44:39,620
som deretter sier, ok, jeg lukker filen min,

577
00:44:39,620 --> 00:44:43,450
det betyr at jeg hadde bedre skrive alt jeg har ikke skrevet ennå.

578
00:44:43,450 --> 00:44:45,770
Det har ikke trenger å skrive alt ut

579
00:44:45,770 --> 00:44:49,010
til du lukker filen, og da er det behov for.

580
00:44:49,010 --> 00:44:56,220
Så det er akkurat hva lat - det venter til det har å skje.

581
00:44:56,220 --> 00:44:59,990
Dette - ta 51 og du vil gå inn i det i mer detalj,

582
00:44:59,990 --> 00:45:05,470
fordi OCaml og alt i 51, er alt rekursjon.

583
00:45:05,470 --> 00:45:08,890
Det er ingen iterativ løsninger, i utgangspunktet.

584
00:45:08,890 --> 00:45:11,550
Alt er rekursjon, og lat evaluering

585
00:45:11,550 --> 00:45:14,790
kommer til å være viktig for mange omstendigheter

586
00:45:14,790 --> 00:45:19,920
der, hvis du ikke dovent evaluere, ville det bety -

587
00:45:19,920 --> 00:45:24,760
Eksempelet er bekker, som er uendelig lang.

588
00:45:24,760 --> 00:45:30,990
I teorien kan du tenke på de naturlige tall som en strøm av 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Så dovent evaluert ting er bra.

590
00:45:33,090 --> 00:45:37,210
Hvis jeg sier jeg vil ha den tiende nummer, så jeg kan vurdere opp til tiende nummeret.

591
00:45:37,210 --> 00:45:40,300
Hvis jeg vil hundrede nummer, så jeg kan vurdere opp til hundredel nummer.

592
00:45:40,300 --> 00:45:46,290
Uten lat evaluering, så det kommer til å prøve å evaluere alle tall umiddelbart.

593
00:45:46,290 --> 00:45:50,000
Du evaluerer uendelig mange tall, og det er bare ikke mulig.

594
00:45:50,000 --> 00:45:52,080
Så det er mange tilfeller der lat evaluering

595
00:45:52,080 --> 00:45:57,840
er bare viktig for å få ting til å fungere.

596
00:45:57,840 --> 00:46:05,260
>> Nå ønsker vi å skrive innlegget der innsatsen skal være

597
00:46:05,260 --> 00:46:08,430
tilsvarende endring i definisjonen.

598
00:46:08,430 --> 00:46:10,470
Så akkurat nå er det bool innsats (int verdi).

599
00:46:10,470 --> 00:46:23,850
Vi kommer til å endre det til bool innsats (int verdi, node * treet).

600
00:46:23,850 --> 00:46:29,120
Vi faktisk kommer til å endre det igjen i en bit, vil vi se hvorfor.

601
00:46:29,120 --> 00:46:32,210
Og la oss flytte build_node, bare for pokker av det,

602
00:46:32,210 --> 00:46:36,730
ovenfor setter så vi ikke trenger å skrive en funksjon prototype.

603
00:46:36,730 --> 00:46:42,450
Som er et hint om at du kommer til å bruke build_node i innsatsen.

604
00:46:42,450 --> 00:46:49,590
Okay. Ta et minutt for det.

605
00:46:49,590 --> 00:46:52,130
Jeg tror jeg reddet revisjonen hvis du ønsker å trekke fra det,

606
00:46:52,130 --> 00:47:00,240
eller i det minste, jeg gjorde nå.

607
00:47:00,240 --> 00:47:04,190
Jeg ønsket en liten pause for å tenke på logikk innsatsen,

608
00:47:04,190 --> 00:47:08,750
hvis du ikke kan tenke på det.

609
00:47:08,750 --> 00:47:12,860
I utgangspunktet vil du bare bli lagt på bladene.

610
00:47:12,860 --> 00:47:18,640
Som, hvis jeg setter en, så jeg uunngåelig kommer til å bli lagt 1 -

611
00:47:18,640 --> 00:47:21,820
Jeg kommer til å endre til sort - Jeg skal bli lagt en over her.

612
00:47:21,820 --> 00:47:28,070
Eller hvis jeg setter 4, vil jeg bli lagt 4 over her.

613
00:47:28,070 --> 00:47:32,180
Så uansett hva du gjør, du kommer til å bli lagt på et blad.

614
00:47:32,180 --> 00:47:36,130
Alt du trenger å gjøre er iterate ned treet til du kommer til noden

615
00:47:36,130 --> 00:47:40,890
som bør være noden overordnede, den nye nodens forelder,

616
00:47:40,890 --> 00:47:44,560
og deretter endrer sin venstre eller høyre pekeren, avhengig av om

617
00:47:44,560 --> 00:47:47,060
den er større enn eller mindre enn den gjeldende node.

618
00:47:47,060 --> 00:47:51,180
Endre det pekeren å peke på den nye noden.

619
00:47:51,180 --> 00:48:05,490
Så iterate ned treet, gjør bladet peker til den nye noden.

620
00:48:05,490 --> 00:48:09,810
Også tenke på hvorfor det forbyr den type situasjon før,

621
00:48:09,810 --> 00:48:17,990
der jeg bygget det binære treet der det var riktig

622
00:48:17,990 --> 00:48:19,920
hvis du bare så på en enkelt node,

623
00:48:19,920 --> 00:48:24,830
men 9 var til venstre for 7 hvis du iterated ned hele veien.

624
00:48:24,830 --> 00:48:29,770
Så det er umulig i dette scenariet, siden -

625
00:48:29,770 --> 00:48:32,530
tenker på å sette inn 9 eller noe, på den aller første noden,

626
00:48:32,530 --> 00:48:35,350
Jeg kommer til å se 7 og jeg bare kommer til å gå til høyre.

627
00:48:35,350 --> 00:48:38,490
Så uansett hva jeg gjør, hvis jeg setter inn ved å gå til et blad,

628
00:48:38,490 --> 00:48:40,790
og til et blad ved hjelp av riktig algoritme,

629
00:48:40,790 --> 00:48:43,130
det kommer til å være umulig for meg å sette 9 til venstre for 7

630
00:48:43,130 --> 00:48:48,250
fordi så snart jeg traff 7 jeg kommer til å gå til høyre.

631
00:48:59,740 --> 00:49:02,070
Har noen noe å starte med?

632
00:49:02,070 --> 00:49:05,480
[Student] jeg gjør. >> Ja.

633
00:49:05,480 --> 00:49:09,200
[Student, uforståelig]

634
00:49:09,200 --> 00:49:14,390
[Other student, uforståelig]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Det er verdsatt. Okay. Vil du forklare?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Siden vi vet at vi setter

637
00:49:20,690 --> 00:49:24,060
nye noder på slutten av treet,

638
00:49:24,060 --> 00:49:28,070
Jeg løkke gjennom treet iterativt

639
00:49:28,070 --> 00:49:31,360
før jeg kom til en node som pekte til null.

640
00:49:31,360 --> 00:49:34,220
Og da jeg bestemte meg for å sette det enten på høyre eller venstre side

641
00:49:34,220 --> 00:49:37,420
bruker denne retten variabel, det fortalte meg hvor du vil plassere den.

642
00:49:37,420 --> 00:49:41,850
Og så, i hovedsak, jeg bare gjort det siste -

643
00:49:41,850 --> 00:49:47,520
at temp node peker til den nye noden som det var å skape,

644
00:49:47,520 --> 00:49:50,770
enten på venstre eller på høyre side, avhengig av hva verdien høyre var.

645
00:49:50,770 --> 00:49:56,530
Slutt stiller jeg den nye noden verdien til verdien av testingen sin.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Ok, så jeg ser ett problem her.

647
00:49:59,550 --> 00:50:02,050
Dette er som 95% av veien dit.

648
00:50:02,050 --> 00:50:07,550
Det eneste problemet jeg ser, vel, ikke se noen andre et problem?

649
00:50:07,550 --> 00:50:18,400
Hva er det forhold under hvilke de skal bryte ut av loopen?

650
00:50:18,400 --> 00:50:22,100
[Student] Hvis temp er null? >> Ja. Så hvordan kan du bryte ut av loopen er hvis temp er null.

651
00:50:22,100 --> 00:50:30,220
Men hva gjør jeg her?

652
00:50:30,220 --> 00:50:35,410
Jeg dereferanse temp, som er uunngåelig null.

653
00:50:35,410 --> 00:50:39,840
Så den andre tingen du trenger å gjøre er ikke bare å holde styr før temp er null,

654
00:50:39,840 --> 00:50:45,590
du ønsker å holde styr på den overordnede til alle tider.

655
00:50:45,590 --> 00:50:52,190
Vi ønsker også node * forelder, tror jeg vi kan holde det på null først.

656
00:50:52,190 --> 00:50:55,480
Dette kommer til å ha rar oppførsel for roten av treet,

657
00:50:55,480 --> 00:50:59,210
men vi kommer til det.

658
00:50:59,210 --> 00:51:03,950
Hvis verdien er større enn hva, så temp = temp rett.

659
00:51:03,950 --> 00:51:07,910
Men før vi gjør det, foreldre = temp.

660
00:51:07,910 --> 00:51:14,500
Eller er foreldre alltid kommer til å like temp? Er det tilfelle?

661
00:51:14,500 --> 00:51:19,560
Hvis temp er ikke null, så jeg kommer til å flytte ned, uansett hva,

662
00:51:19,560 --> 00:51:24,030
til en node som temp er morselskap.

663
00:51:24,030 --> 00:51:27,500
Så foreldre kommer til å bli temp, og da jeg flytter temp ned.

664
00:51:27,500 --> 00:51:32,410
Nå temp er null, men foreldre peker den overordnede av det som er null.

665
00:51:32,410 --> 00:51:39,110
Så her nede, jeg ønsker ikke å rette tilsvarer 1.

666
00:51:39,110 --> 00:51:41,300
Så flyttet jeg til høyre, så hvis høyre = 1,

667
00:51:41,300 --> 00:51:45,130
og jeg antar du også ønsker å gjøre -

668
00:51:45,130 --> 00:51:48,530
hvis du flytter til venstre, vil du sette rett lik 0..

669
00:51:48,530 --> 00:51:55,950
Eller annet hvis du skulle flytte til høyre.

670
00:51:55,950 --> 00:51:58,590
Så rett = 0. Hvis høyre = 1,

671
00:51:58,590 --> 00:52:04,260
nå ønsker vi å gjøre den overordnede rett pekeren newnode,

672
00:52:04,260 --> 00:52:08,520
annet vi ønsker å gjøre den overordnede venstre pekeren newnode.

673
00:52:08,520 --> 00:52:16,850
Spørsmål om det?

674
00:52:16,850 --> 00:52:24,880
Okay. Så dette er måten vi - vel, egentlig, i stedet for å gjøre dette,

675
00:52:24,880 --> 00:52:29,630
vi halvparten forventet du å bruke build_node.

676
00:52:29,630 --> 00:52:40,450
Og så hvis newnode lik null, returnerer false.

677
00:52:40,450 --> 00:52:44,170
Det er det. Nå, dette er hva vi forventet at du skal gjøre.

678
00:52:44,170 --> 00:52:47,690
>> Dette er hva de ansatte løsningene.

679
00:52:47,690 --> 00:52:52,360
Jeg er uenig med dette som den "riktige" måten å gå om det

680
00:52:52,360 --> 00:52:57,820
men dette er helt greit, og det vil fungere.

681
00:52:57,820 --> 00:53:02,840
En ting som er litt rart akkurat nå er

682
00:53:02,840 --> 00:53:08,310
Hvis treet begynner som null, passerer vi et null tre.

683
00:53:08,310 --> 00:53:12,650
Jeg antar det avhenger av hvordan du definerer oppførselen til bestått i en null tre.

684
00:53:12,650 --> 00:53:15,490
Jeg vil tro at hvis du passerer i en null tre,

685
00:53:15,490 --> 00:53:17,520
deretter sette verdien til en null tre

686
00:53:17,520 --> 00:53:23,030
bør bare returnere et tre der den eneste verdien er at én node.

687
00:53:23,030 --> 00:53:25,830
Folk er enig med det? Du kan, hvis du ville,

688
00:53:25,830 --> 00:53:28,050
hvis du passerer i en null tre

689
00:53:28,050 --> 00:53:31,320
og du vil sette inn en verdi i det, return false.

690
00:53:31,320 --> 00:53:33,830
Det er opp til deg å definere det.

691
00:53:33,830 --> 00:53:38,320
For å gjøre det første jeg sa og da -

692
00:53:38,320 --> 00:53:40,720
vel, du kommer til å ha problemer med å gjøre det, fordi

693
00:53:40,720 --> 00:53:44,090
det ville være lettere om vi hadde en global peker til ting,

694
00:53:44,090 --> 00:53:48,570
men vi ikke, så hvis treet er null, er det ingenting vi kan gjøre med det.

695
00:53:48,570 --> 00:53:50,960
Vi kan bare returnere false.

696
00:53:50,960 --> 00:53:52,840
Så jeg kommer til å endre innsatsen.

697
00:53:52,840 --> 00:53:56,540
Vi teknisk kunne bare endre dette her,

698
00:53:56,540 --> 00:53:58,400
hvordan det gjentar over ting,

699
00:53:58,400 --> 00:54:04,530
men jeg kommer til å endre innsatsen for å ta en node ** treet.

700
00:54:04,530 --> 00:54:07,510
Doble pekere.

701
00:54:07,510 --> 00:54:09,710
Hva betyr dette?

702
00:54:09,710 --> 00:54:12,330
I stedet for å håndtere med pekere til noder,

703
00:54:12,330 --> 00:54:16,690
tingen jeg kommer til å være manipulere er denne pekeren.

704
00:54:16,690 --> 00:54:18,790
Jeg kommer til å være manipulere denne pekeren.

705
00:54:18,790 --> 00:54:21,770
Jeg kommer til å være manipulere pekere direkte.

706
00:54:21,770 --> 00:54:25,760
Dette er fornuftig siden, tenk ned -

707
00:54:25,760 --> 00:54:33,340
vel, akkurat nå dette peker til null.

708
00:54:33,340 --> 00:54:38,130
Hva jeg vil gjøre er å manipulere denne pekeren å peke på ikke null.

709
00:54:38,130 --> 00:54:40,970
Jeg vil at det skal peke til min nye node.

710
00:54:40,970 --> 00:54:44,870
Hvis jeg bare holde styr på pekere til mine pekere,

711
00:54:44,870 --> 00:54:47,840
så jeg ikke trenger å holde styr på en forelder pekeren.

712
00:54:47,840 --> 00:54:52,640
Jeg kan bare holde styr for å se om pekeren peker til null,

713
00:54:52,640 --> 00:54:54,580
og hvis pekeren peker til null,

714
00:54:54,580 --> 00:54:57,370
endre det til å peke på noden jeg ønsker.

715
00:54:57,370 --> 00:55:00,070
Og jeg kan endre det siden jeg har en peker til pekeren.

716
00:55:00,070 --> 00:55:02,040
La oss se på dette akkurat nå.

717
00:55:02,040 --> 00:55:05,470
Du kan faktisk gjøre det rekursivt ganske enkelt.

718
00:55:05,470 --> 00:55:08,080
Ønsker vi å gjøre det?

719
00:55:08,080 --> 00:55:10,980
Ja, det gjør vi.

720
00:55:10,980 --> 00:55:16,790
>> La oss se det rekursivt.

721
00:55:16,790 --> 00:55:24,070
Først, er hva våre base case kommer til å bli?

722
00:55:24,070 --> 00:55:29,140
Nesten alltid vår base case, men faktisk er dette slags kinkig.

723
00:55:29,140 --> 00:55:34,370
First things first, if (tre == NULL)

724
00:55:34,370 --> 00:55:37,550
Jeg antar vi bare kommer til å returnere falsk.

725
00:55:37,550 --> 00:55:40,460
Dette er forskjellig fra treet blir null.

726
00:55:40,460 --> 00:55:44,510
Dette er pekeren til root pekeren blir null

727
00:55:44,510 --> 00:55:48,360
noe som betyr at root pekeren ikke eksisterer.

728
00:55:48,360 --> 00:55:52,390
Så her nede, hvis jeg gjør

729
00:55:52,390 --> 00:55:55,760
node * - la oss bare bruke denne.

730
00:55:55,760 --> 00:55:58,960
Node * root = NULL,

731
00:55:58,960 --> 00:56:00,730
og da kommer jeg til å ringe innsatsen ved å gjøre noe sånt,

732
00:56:00,730 --> 00:56:04,540
Sett 4 inn og rot.

733
00:56:04,540 --> 00:56:06,560
Så & rot, hvis rot er en node *

734
00:56:06,560 --> 00:56:11,170
da og rot kommer til å være en node **.

735
00:56:11,170 --> 00:56:15,120
Dette er gyldig. I dette tilfellet, treet, opp her,

736
00:56:15,120 --> 00:56:20,120
Treet er ikke null - eller innsats.

737
00:56:20,120 --> 00:56:24,630
Her. Treet er ikke null; * treet er null, noe som er bra

738
00:56:24,630 --> 00:56:26,680
fordi hvis * treet er null, så jeg kan manipulere det

739
00:56:26,680 --> 00:56:29,210
til nå peke på hva jeg vil den skal peke til.

740
00:56:29,210 --> 00:56:34,750
Men hvis treet er null, betyr det at jeg bare kom ned hit og sa null.

741
00:56:34,750 --> 00:56:42,710
Det gir ikke mening. Jeg kan ikke gjøre noe med det.

742
00:56:42,710 --> 00:56:45,540
Hvis treet er null, returnerer false.

743
00:56:45,540 --> 00:56:48,220
Så jeg i utgangspunktet allerede sagt hva vår virkelige base case er.

744
00:56:48,220 --> 00:56:50,580
Og hva kommer det til å bli?

745
00:56:50,580 --> 00:56:55,030
[Student, uforståelig]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ja. Så hvis (* tre == NULL).

747
00:57:00,000 --> 00:57:04,520
Dette relaterer seg til saken over her

748
00:57:04,520 --> 00:57:09,640
der hvis min røde pekeren er pekeren jeg fokusert på,

749
00:57:09,640 --> 00:57:12,960
så liker jeg fokusert på denne pekeren, nå er jeg fokusert på denne pekeren.

750
00:57:12,960 --> 00:57:15,150
Nå er jeg fokusert på denne pekeren.

751
00:57:15,150 --> 00:57:18,160
Så hvis min røde pekeren, som er min node **,

752
00:57:18,160 --> 00:57:22,880
er noensinne - hvis *, min røde pekeren, er stadig null,

753
00:57:22,880 --> 00:57:28,470
det betyr at jeg er på saken hvor jeg fokuserer på en peker som peker -

754
00:57:28,470 --> 00:57:32,530
dette er en peker som tilhører et blad.

755
00:57:32,530 --> 00:57:41,090
Jeg ønsker å endre denne pekeren å peke på min nye node.

756
00:57:41,090 --> 00:57:45,230
Kom tilbake hit.

757
00:57:45,230 --> 00:57:56,490
Min newnode vil bare være node * n = build_node (verdi)

758
00:57:56,490 --> 00:58:07,300
deretter n, hvis n = NULL, return false.

759
00:58:07,300 --> 00:58:12,600
Annet vi ønsker å endre hva pekeren nå peker til

760
00:58:12,600 --> 00:58:17,830
til nå peke til vår nybygde node.

761
00:58:17,830 --> 00:58:20,280
Vi kan faktisk gjøre det her.

762
00:58:20,280 --> 00:58:30,660
Stedet for å si n, sier vi * treet = hvis * treet.

763
00:58:30,660 --> 00:58:35,450
Alle forstår det? Som ved å dele med pekere til pekere,

764
00:58:35,450 --> 00:58:40,750
Vi kan endre null pekere til å peke på ting vi vil at de skal peke til.

765
00:58:40,750 --> 00:58:42,820
Det er vår base case.

766
00:58:42,820 --> 00:58:45,740
>> Nå vår tilbakefall, eller vår rekursjon,

767
00:58:45,740 --> 00:58:51,430
kommer til å være svært lik alle andre rekursjoner vi har gjort.

768
00:58:51,430 --> 00:58:55,830
Vi kommer til å ønske å sette verdi,

769
00:58:55,830 --> 00:58:59,040
og nå skal jeg bruke trefoldig igjen, men hva er vår tilstand skal være?

770
00:58:59,040 --> 00:59:05,180
Hva er det vi leter etter for å avgjøre om vi ønsker å gå til venstre eller høyre?

771
00:59:05,180 --> 00:59:07,760
La oss gjøre det i separate trinn.

772
00:59:07,760 --> 00:59:18,850
Hvis (verdi <) hva?

773
00:59:18,850 --> 00:59:23,200
[Student] Treets verdi?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Så husk at jeg er for tiden -

775
00:59:27,490 --> 00:59:31,260
[Studenter, uforståelige]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, så akkurat her, la oss si at dette grønn pil

777
00:59:34,140 --> 00:59:39,050
er et eksempel på hva treet øyeblikket er, er en peker til denne pekeren.

778
00:59:39,050 --> 00:59:46,610
Så det betyr at jeg er en peker til en peker til tre.

779
00:59:46,610 --> 00:59:48,800
Den dereferanse to ganger hørtes bra.

780
00:59:48,800 --> 00:59:51,010
Hva gjør jeg - hvordan gjør jeg det?

781
00:59:51,010 --> 00:59:53,210
[Student] dereferanse gang, og gjør deretter pilen på den måten?

782
00:59:53,210 --> 00:59:58,420
[Bowden] So (* tree) er dereferanse gang, -> verdi

783
00:59:58,420 --> 01:00:05,960
kommer til å gi meg verdien av noden som jeg indirekte peker til.

784
01:00:05,960 --> 01:00:11,980
Så jeg kan også skrive det ** tree.value hvis du foretrekker det.

785
01:00:11,980 --> 01:00:18,490
Enten fungerer.

786
01:00:18,490 --> 01:00:26,190
Hvis det er tilfelle, så vil jeg kalle inn med verdi.

787
01:00:26,190 --> 01:00:32,590
Og hva er min oppdaterte node ** kommer til å bli?

788
01:00:32,590 --> 01:00:39,440
Jeg ønsker å gå til venstre, så ** tree.left kommer til å være min venstre.

789
01:00:39,440 --> 01:00:41,900
Og jeg vil at pekeren skal den tingen

790
01:00:41,900 --> 01:00:44,930
slik at hvis venstre ender opp med å bli nullpeker,

791
01:00:44,930 --> 01:00:48,360
Jeg kan endre det til å peke på min nye node.

792
01:00:48,360 --> 01:00:51,460
>> Og det andre tilfellet kan være svært like.

793
01:00:51,460 --> 01:00:55,600
La oss faktisk gjøre at trefoldig min akkurat nå.

794
01:00:55,600 --> 01:01:04,480
Sett verdi hvis verdi <(** tree). Verdi.

795
01:01:04,480 --> 01:01:11,040
Så vi ønsker å oppdatere våre ** til venstre,

796
01:01:11,040 --> 01:01:17,030
annet vi ønsker å oppdatere våre ** til høyre.

797
01:01:17,030 --> 01:01:22,540
[Student] Blir at pekeren til pekeren?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Husk at - ** tree.right er en node stjerne.

799
01:01:30,940 --> 01:01:35,040
[Student, uforståelig] >> Ja.

800
01:01:35,040 --> 01:01:41,140
** Tree.right er som denne pekeren eller noe.

801
01:01:41,140 --> 01:01:45,140
Så ved å ta en peker til det, gir det meg hva jeg vil

802
01:01:45,140 --> 01:01:50,090
av pekeren til den fyren.

803
01:01:50,090 --> 01:01:54,260
[Student] Kan vi gå over igjen hvorfor vi bruker de to pekere?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Så - Nei, det kan du, og at løsningen før

805
01:01:58,220 --> 01:02:04,540
var en måte å gjøre det uten å gjøre to pekere.

806
01:02:04,540 --> 01:02:08,740
Du må være i stand til å forstå ved hjelp av to pekere,

807
01:02:08,740 --> 01:02:11,660
og dette er et renere løsning.

808
01:02:11,660 --> 01:02:16,090
Legg også merke til det, hva skjer hvis mitt tre -

809
01:02:16,090 --> 01:02:24,480
hva skjer hvis min root var null? Hva skjer hvis jeg gjør denne saken her?

810
01:02:24,480 --> 01:02:30,540
Så node * root = NULL, sett 4 inn og rot.

811
01:02:30,540 --> 01:02:35,110
Hva er roten kommer til å være etter dette?

812
01:02:35,110 --> 01:02:37,470
[Student, uforståelig] >> Ja.

813
01:02:37,470 --> 01:02:41,710
Root verdi kommer til å være 4.

814
01:02:41,710 --> 01:02:45,510
Root venstre skal være null, er roten til høyre kommer til å være null.

815
01:02:45,510 --> 01:02:49,490
I tilfellet hvor vi ikke pass rot etter adresse,

816
01:02:49,490 --> 01:02:52,490
vi kunne ikke endre rot.

817
01:02:52,490 --> 01:02:56,020
I tilfellet hvor treet - hvor rot var null,

818
01:02:56,020 --> 01:02:58,410
vi bare måtte returnere falsk. Det er ingenting vi kan gjøre.

819
01:02:58,410 --> 01:03:01,520
Vi kan ikke sette inn en node i et tomt tre.

820
01:03:01,520 --> 01:03:06,810
Men nå kan vi, vi bare gjør en tom tre inn i et node treet.

821
01:03:06,810 --> 01:03:13,400
Som vanligvis er forventet måte at det er ment å fungere.

822
01:03:13,400 --> 01:03:21,610
>> Videre er dette vesentlig kortere enn

823
01:03:21,610 --> 01:03:26,240
også holde styr på den overordnede, og slik at du iterate ned hele veien.

824
01:03:26,240 --> 01:03:30,140
Nå har jeg mine foreldre, og jeg må bare mine foreldre rett pekeren til uansett.

825
01:03:30,140 --> 01:03:35,640
I stedet, hvis vi gjorde dette iterativt, ville det være det samme ideen med en stund loop.

826
01:03:35,640 --> 01:03:38,100
Men i stedet for å måtte forholde seg til mine foreldre pekeren,

827
01:03:38,100 --> 01:03:40,600
i stedet min nåværende pekeren ville være tingen

828
01:03:40,600 --> 01:03:43,790
at jeg direkte endre å peke på min nye node.

829
01:03:43,790 --> 01:03:46,090
Jeg trenger ikke å forholde seg til om den peker til venstre.

830
01:03:46,090 --> 01:03:48,810
Jeg trenger ikke å forholde seg til om den peker mot høyre.

831
01:03:48,810 --> 01:04:00,860
Det er akkurat hva denne pekeren er, kommer jeg til å sette den til å peke på min nye node.

832
01:04:00,860 --> 01:04:05,740
Alle forstår hvordan det fungerer?

833
01:04:05,740 --> 01:04:09,460
Hvis ikke, hvorfor vi ønsker å gjøre det på denne måten,

834
01:04:09,460 --> 01:04:14,920
men i det minste at dette fungerer som en løsning?

835
01:04:14,920 --> 01:04:17,110
[Student] Hvor får vi tilbake sant?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Det er nok rett her.

837
01:04:21,550 --> 01:04:26,690
Hvis vi riktig sett den, return true.

838
01:04:26,690 --> 01:04:32,010
Else, her nede vi kommer til å ønske å gå tilbake uansett insert avkastning.

839
01:04:32,010 --> 01:04:35,950
>> Og hva er spesielt med denne rekursive funksjonen?

840
01:04:35,950 --> 01:04:43,010
Det er halen rekursive, så så lenge vi kompilere med noen optimalisering,

841
01:04:43,010 --> 01:04:48,060
det vil gjenkjenne det og du vil aldri få en stack overflow fra dette,

842
01:04:48,060 --> 01:04:53,230
selv om vår treet har en høyde på 10.000 eller 10 millioner kroner.

843
01:04:53,230 --> 01:04:55,630
[Student, uforståelig]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Jeg tror det gjør det på Dash - eller hva optimalisering nivå

845
01:05:00,310 --> 01:05:03,820
er nødvendig for en hale rekursjon å bli gjenkjent.

846
01:05:03,820 --> 01:05:09,350
Jeg tror det anerkjenner - GCC og Clang

847
01:05:09,350 --> 01:05:12,610
også ha forskjellige betydninger for deres optimalisering nivåer.

848
01:05:12,610 --> 01:05:17,870
Jeg vil si det er 2 DashO, for at det vil anerkjenne halen rekursjon.

849
01:05:17,870 --> 01:05:27,880
Men vi - du kan konstruere som en Fibonocci eksempel eller noe.

850
01:05:27,880 --> 01:05:30,030
Det er ikke lett å teste med dette, fordi det er vanskelig å lage

851
01:05:30,030 --> 01:05:32,600
et binært tre som er så stor.

852
01:05:32,600 --> 01:05:37,140
Men ja, jeg tror det er 2 DashO, som

853
01:05:37,140 --> 01:05:40,580
Hvis du kompilere med DashO 2, vil det se etter halen rekursjon

854
01:05:40,580 --> 01:05:54,030
og optimalisere det ut.

855
01:05:54,030 --> 01:05:58,190
La oss gå tilbake til - sett er bokstavelig talt det siste den trenger.

856
01:05:58,190 --> 01:06:04,900
La oss gå tilbake til innsatsen over her

857
01:06:04,900 --> 01:06:07,840
hvor vi kommer til å gjøre den samme ideen.

858
01:06:07,840 --> 01:06:14,340
Det vil fortsatt ha feil av ikke å kunne helt håndtere

859
01:06:14,340 --> 01:06:17,940
når roten selv er null, eller det siste oppføringen er null,

860
01:06:17,940 --> 01:06:20,060
men i stedet for å håndtere en forelder peker,

861
01:06:20,060 --> 01:06:27,430
la oss bruke den samme logikken holde pekere til pekere.

862
01:06:27,430 --> 01:06:35,580
Hvis det her vi holder vår node ** nå,

863
01:06:35,580 --> 01:06:37,860
og vi trenger ikke å holde styr på riktig lenger,

864
01:06:37,860 --> 01:06:47,190
men node ** nå = & tre.

865
01:06:47,190 --> 01:06:54,800
Og nå vår mens loop kommer til å være mens * nå ikke lik null.

866
01:06:54,800 --> 01:07:00,270
Trenger ikke å holde styr på foreldrene lenger.

867
01:07:00,270 --> 01:07:04,180
Trenger ikke å holde styr på venstre og høyre.

868
01:07:04,180 --> 01:07:10,190
Og jeg vil kalle det temp, fordi vi allerede bruker temp.

869
01:07:10,190 --> 01:07:17,200
Okay. Så hvis (verdi> * temp),

870
01:07:17,200 --> 01:07:24,010
da & (* temp) -> høyre

871
01:07:24,010 --> 01:07:29,250
ellers temp = & (* temp) -> venstre.

872
01:07:29,250 --> 01:07:32,730
Og nå, på dette punktet, etter dette mens loop,

873
01:07:32,730 --> 01:07:36,380
Jeg bare gjør dette fordi kanskje det er lettere å tenke iterativt enn rekursivt,

874
01:07:36,380 --> 01:07:39,010
men etter dette mens loop,

875
01:07:39,010 --> 01:07:43,820
* Temp er pekeren vi ønsker å endre.

876
01:07:43,820 --> 01:07:48,960
>> Før vi hadde foreldre, og vi ønsket å endre en av foreldrene til venstre eller forelder høyre,

877
01:07:48,960 --> 01:07:51,310
men hvis vi ønsker å endre overordnede høyre,

878
01:07:51,310 --> 01:07:54,550
deretter * temp er foreldre rett, og vi kan endre det direkte.

879
01:07:54,550 --> 01:08:05,860
Så her nede, kan vi gjøre * temp = newnode, og det er det.

880
01:08:05,860 --> 01:08:09,540
Så varsel, var alt vi gjorde i dette ta ut linjer med kode.

881
01:08:09,540 --> 01:08:14,770
For å holde styr på den overordnede i alt som er ekstra innsats.

882
01:08:14,770 --> 01:08:18,689
Her, hvis vi bare holde styr på pekeren til pekeren,

883
01:08:18,689 --> 01:08:22,990
og selv om vi ønsket å kvitte seg med alle disse klammeparentes nå,

884
01:08:22,990 --> 01:08:27,170
at det ser kortere.

885
01:08:27,170 --> 01:08:32,529
Dette er nå nøyaktig samme løsning,

886
01:08:32,529 --> 01:08:38,210
men færre linjer med kode.

887
01:08:38,210 --> 01:08:41,229
Når du begynner å gjenkjenne dette som en gyldig løsning,

888
01:08:41,229 --> 01:08:43,529
det er også lettere å resonnere om enn liker, ok,

889
01:08:43,529 --> 01:08:45,779
hvorfor har jeg denne flagget på int rett?

890
01:08:45,779 --> 01:08:49,290
Hva betyr det? Å, det er et tegn på at

891
01:08:49,290 --> 01:08:51,370
hver gang jeg går rett, jeg trenger å sette den,

892
01:08:51,370 --> 01:08:53,819
annet hvis jeg går dro jeg trenger å sette den til null.

893
01:08:53,819 --> 01:09:04,060
Her har jeg ikke til grunn om det, det er bare lettere å tenke på.

894
01:09:04,060 --> 01:09:06,710
Spørsmål?

895
01:09:06,710 --> 01:09:16,290
[Student, uforståelig] >> Ja.

896
01:09:16,290 --> 01:09:23,359
Ok, så i den siste bit -

897
01:09:23,359 --> 01:09:28,080
Jeg antar en rask og enkel funksjon vi kan gjøre er,

898
01:09:28,080 --> 01:09:34,910
let's - sammen, antar jeg, prøve og skrive en inneholder funksjon

899
01:09:34,910 --> 01:09:38,899
som bryr seg ikke om det er et binært søketre.

900
01:09:38,899 --> 01:09:43,770
Dette inneholder funksjonen skal returnere true

901
01:09:43,770 --> 01:09:58,330
hvis hvor som helst i denne generelle binære treet er verdien vi leter etter.

902
01:09:58,330 --> 01:10:02,520
Så la oss først gjøre det rekursivt og så får vi gjøre det iterativt.

903
01:10:02,520 --> 01:10:07,300
Vi kan faktisk bare gjøre det sammen, fordi dette kommer til å bli veldig kort.

904
01:10:07,300 --> 01:10:11,510
>> Hva er min base case kommer til å bli?

905
01:10:11,510 --> 01:10:13,890
[Student, uforståelig]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Så hvis (treet == NULL), hva så?

907
01:10:18,230 --> 01:10:22,740
[Student] return false.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, vel, jeg trenger ikke det andre.

909
01:10:26,160 --> 01:10:30,250
Hvis var min andre base case.

910
01:10:30,250 --> 01:10:32,450
[Student] Tre verdi? >> Ja.

911
01:10:32,450 --> 01:10:36,430
Så hvis (tree-> verdi == verdi.

912
01:10:36,430 --> 01:10:39,920
Legg merke til vi er tilbake til node *, ikke node ** s?

913
01:10:39,920 --> 01:10:42,990
Inneholder vil aldri trenger å bruke en node **,

914
01:10:42,990 --> 01:10:45,480
siden vi ikke endrer pekere.

915
01:10:45,480 --> 01:10:50,540
Vi bare krysser dem.

916
01:10:50,540 --> 01:10:53,830
Hvis det skjer, så vi ønsker å returnere true.

917
01:10:53,830 --> 01:10:58,270
Annet vi ønsker å traversere barna.

918
01:10:58,270 --> 01:11:02,620
Så vi kan ikke resonnere om hvorvidt alt til venstre er mindre

919
01:11:02,620 --> 01:11:05,390
og alt til høyre er større.

920
01:11:05,390 --> 01:11:09,590
Så hva er vår tilstand kommer til å være her - eller, hva skal vi gjøre?

921
01:11:09,590 --> 01:11:11,840
[Student, uforståelig] >> Ja.

922
01:11:11,840 --> 01:11:17,400
Return inneholder (verdi, tree-> venstre)

923
01:11:17,400 --> 01:11:26,860
eller inneholder (verdi, tree-> høyre). Og det er det.

924
01:11:26,860 --> 01:11:29,080
Og legg merke til at det er noen kortslutning evaluering,

925
01:11:29,080 --> 01:11:32,520
der hvis vi måtte finne verdien i venstre treet,

926
01:11:32,520 --> 01:11:36,820
vi aldri trenger å se på høyre treet.

927
01:11:36,820 --> 01:11:40,430
Det er hele funksjonen.

928
01:11:40,430 --> 01:11:43,690
Nå la oss gjøre det iterativt,

929
01:11:43,690 --> 01:11:48,060
som kommer til å bli mindre hyggelig.

930
01:11:48,060 --> 01:11:54,750
Vi tar den vanlige starten av node * nå = treet.

931
01:11:54,750 --> 01:12:03,250
Mens (nå! = NULL).

932
01:12:03,250 --> 01:12:08,600
Raskt kommer til å se et problem.

933
01:12:08,600 --> 01:12:12,250
Hvis nå - her ute, hvis vi noen gang bryte ut av dette,

934
01:12:12,250 --> 01:12:16,020
så vi har kjørt ut av ting å se på, så return false.

935
01:12:16,020 --> 01:12:24,810
Hvis (nå-> verdi == verdi), return true.

936
01:12:24,810 --> 01:12:32,910
Så nå er vi på et sted -

937
01:12:32,910 --> 01:12:36,250
Vi vet ikke om vi ønsker å gå til venstre eller høyre.

938
01:12:36,250 --> 01:12:44,590
Så vilkårlig, la oss bare gå til venstre.

939
01:12:44,590 --> 01:12:47,910
Jeg har tydeligvis kjørt inn i et problem der jeg har helt forlatt alt -

940
01:12:47,910 --> 01:12:50,760
Jeg vil bare noensinne sjekker venstre side av et tre.

941
01:12:50,760 --> 01:12:56,050
Jeg vil aldri se noe som er en riktig barn av noe.

942
01:12:56,050 --> 01:13:00,910
Hvordan fikser jeg dette?

943
01:13:00,910 --> 01:13:05,260
[Student] Du må holde styr på venstre og høyre i en stabel.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Så la oss gjøre det

945
01:13:13,710 --> 01:13:32,360
struct listen, node * n, og deretter node ** neste?

946
01:13:32,360 --> 01:13:40,240
Jeg tror det fungerer fint.

947
01:13:40,240 --> 01:13:45,940
Vi ønsker å gå over til venstre, eller let's - her oppe.

948
01:13:45,940 --> 01:13:54,350
Struct Ønskeliste =, vil den starte

949
01:13:54,350 --> 01:13:58,170
ut på dette struct listen.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Så det kommer til å bli vår lenket liste

951
01:14:04,040 --> 01:14:08,430
av undertreene som vi har hoppet over.

952
01:14:08,430 --> 01:14:13,800
Vi kommer til å traversere igjen nå,

953
01:14:13,800 --> 01:14:17,870
men siden vi uunngåelig må komme tilbake til høyre,

954
01:14:17,870 --> 01:14:26,140
Vi kommer til å holde høyre side inne i vår struct liste.

955
01:14:26,140 --> 01:14:32,620
Da vil vi ha new_list eller struct,

956
01:14:32,620 --> 01:14:41,080
struct listen *, new_list = malloc (sizeof (liste)).

957
01:14:41,080 --> 01:14:44,920
Jeg kommer til å ignorere feil-sjekking det, men du bør sjekke for å se om det er null.

958
01:14:44,920 --> 01:14:50,540
New_list noden det kommer til å peke på -

959
01:14:50,540 --> 01:14:56,890
oh, det er derfor jeg ønsket det opp her. Det kommer til å peke på en annen struct liste.

960
01:14:56,890 --> 01:15:02,380
Det er bare hvordan koblet lister arbeid.

961
01:15:02,380 --> 01:15:04,810
Dette er det samme som en int lenket liste

962
01:15:04,810 --> 01:15:06,960
bortsett vi bare erstatte int med node *.

963
01:15:06,960 --> 01:15:11,040
Det er akkurat det samme.

964
01:15:11,040 --> 01:15:15,100
Så new_list, verdien av vår new_list node,

965
01:15:15,100 --> 01:15:19,120
kommer til å være nå-> høyre.

966
01:15:19,120 --> 01:15:24,280
Verdien av vår new_list-> neste kommer til å bli vår opprinnelige liste,

967
01:15:24,280 --> 01:15:30,760
og vi kommer til å oppdatere vår liste for å peke på new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nå trenger vi en slags måte å trekke ting,

969
01:15:33,650 --> 01:15:37,020
som vi har krysset hele venstre subtre.

970
01:15:37,020 --> 01:15:40,480
Nå må vi trekke ting ut av det,

971
01:15:40,480 --> 01:15:43,850
som nå er null, vi ønsker ikke å bare returnere false.

972
01:15:43,850 --> 01:15:50,370
Vi ønsker å nå trekke utenfor på vår nye liste.

973
01:15:50,370 --> 01:15:53,690
En praktisk måte å gjøre dette - vel, egentlig, det er flere måter å gjøre dette.

974
01:15:53,690 --> 01:15:56,680
Alle som har et forslag?

975
01:15:56,680 --> 01:15:58,790
Hvor jeg skal gjøre dette eller hvordan jeg skal gjøre dette?

976
01:15:58,790 --> 01:16:08,010
Vi har bare et par minutter, men noen forslag?

977
01:16:08,010 --> 01:16:14,750
I stedet for - en vei, i stedet for tilstanden vår tilværelse stund,

978
01:16:14,750 --> 01:16:17,090
hva vi for øyeblikket ser på er ikke null,

979
01:16:17,090 --> 01:16:22,340
stedet vi kommer til å fortsette å gå til vår liste seg selv er null.

980
01:16:22,340 --> 01:16:25,680
Så hvis vår liste ender opp som null,

981
01:16:25,680 --> 01:16:30,680
da har vi kjørt ut av ting å se etter, for å søke over.

982
01:16:30,680 --> 01:16:39,860
Men det betyr at det første i vår liste er bare kommer til å være den første noden.

983
01:16:39,860 --> 01:16:49,730
Den aller første vil være - vi ikke lenger trenger å se det.

984
01:16:49,730 --> 01:16:58,710
Så list-> n vil være vår treet.

985
01:16:58,710 --> 01:17:02,860
list-> neste kommer til å bli null.

986
01:17:02,860 --> 01:17:07,580
Og nå mens listen er ikke lik null.

987
01:17:07,580 --> 01:17:11,610
Cur kommer til å trekke noe fra vår liste.

988
01:17:11,610 --> 01:17:13,500
Så nå kommer til å like liste-> n.

989
01:17:13,500 --> 01:17:20,850
Og så listen kommer til å like liste-> n, eller liste-> neste.

990
01:17:20,850 --> 01:17:23,480
Så hvis nå verdi lik verdi.

991
01:17:23,480 --> 01:17:28,790
Nå kan vi legge til både vår rett pekeren og vår venstre pekeren

992
01:17:28,790 --> 01:17:32,900
så lenge de ikke er null.

993
01:17:32,900 --> 01:17:36,390
Her nede, tror jeg vi burde ha gjort det i første omgang.

994
01:17:36,390 --> 01:17:44,080
Hvis (nå-> høyre! = NULL)

995
01:17:44,080 --> 01:17:56,380
så vi kommer til å sette noden til listen vår.

996
01:17:56,380 --> 01:17:59,290
Hvis (nå-> venstre), dette er litt ekstra arbeid, men det er greit.

997
01:17:59,290 --> 01:18:02,690
Hvis (nå-> venstre! = NULL),

998
01:18:02,690 --> 01:18:14,310
og vi kommer til å sette venstre inn vår lenket liste,

999
01:18:14,310 --> 01:18:19,700
og det bør være det.

1000
01:18:19,700 --> 01:18:22,670
Vi iterate - så lenge vi har noe i vår liste,

1001
01:18:22,670 --> 01:18:26,640
Vi har en annen node å se på.

1002
01:18:26,640 --> 01:18:28,920
Så vi ser på den noden,

1003
01:18:28,920 --> 01:18:31,390
vi fremme vår liste til den neste.

1004
01:18:31,390 --> 01:18:34,060
Hvis det node er den verdien vi leter etter, kan vi returnere true.

1005
01:18:34,060 --> 01:18:37,640
Else setter både våre venstre og høyre undertreene,

1006
01:18:37,640 --> 01:18:40,510
så lenge de ikke er null, i vår liste

1007
01:18:40,510 --> 01:18:43,120
slik at vi uunngåelig gå over dem.

1008
01:18:43,120 --> 01:18:45,160
Så hvis de ikke var null,

1009
01:18:45,160 --> 01:18:47,950
hvis vår root pekeren pekte på to ting,

1010
01:18:47,950 --> 01:18:51,670
så ved første vi dro noe ut så vår liste ender opp som null.

1011
01:18:51,670 --> 01:18:56,890
Og da vi satt to ting igjen, så nå vår liste er av størrelse 2.

1012
01:18:56,890 --> 01:19:00,030
Så vi kommer til å sløyfe tilbake opp og vi bare kommer til å trekke,

1013
01:19:00,030 --> 01:19:04,250
la oss si, den venstre peker på vår rotnoden.

1014
01:19:04,250 --> 01:19:07,730
Og det vil bare holde skjer, vi vil ende opp looping over alt.

1015
01:19:07,730 --> 01:19:11,280
>> Legg merke til at dette var betydelig mer komplisert

1016
01:19:11,280 --> 01:19:14,160
i den rekursive løsningen.

1017
01:19:14,160 --> 01:19:17,260
Og jeg har sagt flere ganger

1018
01:19:17,260 --> 01:19:25,120
at den rekursive løsningen har vanligvis mye til felles med iterativ løsning.

1019
01:19:25,120 --> 01:19:30,820
Her er dette nøyaktig hva den rekursive løsningen gjør.

1020
01:19:30,820 --> 01:19:36,740
Den eneste forandringen er at i stedet for å bruke implisitt stabelen, programmet stakken,

1021
01:19:36,740 --> 01:19:40,840
som din måte å holde styr på hva noder du fortsatt trenger å besøke,

1022
01:19:40,840 --> 01:19:45,430
nå må du eksplisitt bruke en lenket liste.

1023
01:19:45,430 --> 01:19:49,070
I begge tilfeller er du holde styr på hva node fortsatt trenger å bli besøkt.

1024
01:19:49,070 --> 01:19:51,790
I den rekursive fall er det bare enklere fordi en stabel

1025
01:19:51,790 --> 01:19:57,100
er implementert for deg som programmet stabelen.

1026
01:19:57,100 --> 01:19:59,550
Legg merke til at dette er også koblet listen, er det en stabel.

1027
01:19:59,550 --> 01:20:01,580
Uansett hva vi bare sette på stakken

1028
01:20:01,580 --> 01:20:09,960
er umiddelbart hva vi kommer til å trekke av stabelen å gå til neste.

1029
01:20:09,960 --> 01:20:14,380
Vi har ikke mer tid, men noen spørsmål?

1030
01:20:14,380 --> 01:20:23,530
[Student, uforståelig]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Så hvis vi har vår lenket liste,

1032
01:20:27,790 --> 01:20:30,150
strøm kommer til å peke til denne fyren,

1033
01:20:30,150 --> 01:20:34,690
og nå er vi bare fremme våre lenket liste å fokusere på denne fyren.

1034
01:20:34,690 --> 01:20:44,200
Vi krysser over lenket liste i den linjen.

1035
01:20:44,200 --> 01:20:51,200
Og da jeg tror vi bør frigjøre vår lenket liste og sånt

1036
01:20:51,200 --> 01:20:53,880
gang før retur sant eller usant, må vi

1037
01:20:53,880 --> 01:20:57,360
iterere over vår lenket liste og alltid her nede, tror jeg,

1038
01:20:57,360 --> 01:21:03,900
hvis vi nå rett er ikke lik, legge det, så nå ønsker vi å frigjøre

1039
01:21:03,900 --> 01:21:09,600
nå fordi, vel, vi helt glemmer om listen? Ja.

1040
01:21:09,600 --> 01:21:12,880
Så det er det vi ønsker å gjøre her.

1041
01:21:12,880 --> 01:21:16,730
Hvor er pekeren?

1042
01:21:16,730 --> 01:21:23,320
Cur var da - vi ønsker til en struct liste * 10 lik liste neste.

1043
01:21:23,320 --> 01:21:29,240
Gratis liste, list = temp.

1044
01:21:29,240 --> 01:21:32,820
Og i tilfelle hvor vi return true, trenger vi å veksle

1045
01:21:32,820 --> 01:21:37,050
over resten av vår lenket liste frigjør ting.

1046
01:21:37,050 --> 01:21:39,700
Det fine med den rekursive løsningen er å frigjøre ting

1047
01:21:39,700 --> 01:21:44,930
betyr bare spratt factorings av stabelen som vil skje for deg.

1048
01:21:44,930 --> 01:21:50,720
Så vi har gått fra noe som er som 3 linjer med hard-to-tenke-om koden

1049
01:21:50,720 --> 01:21:57,520
til noe som er betydelig mange flere vanskelige å tenke-om linjer med kode.

1050
01:21:57,520 --> 01:22:00,620
Noen flere spørsmål?

1051
01:22:00,620 --> 01:22:08,760
OK. Vi er gode. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]