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

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 sagde i min e-mail,

5
00:00:10,110 --> 00:00:14,060
Dette vil være et binært-tree-intensiv afdeling.

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

7
00:00:16,820 --> 00:00:18,920
Så vi vil forsøge at trække ud hvert spørgsmål

8
00:00:18,920 --> 00:00:25,430
og gå ind i smertefulde detaljer alle de bedste måder at gøre tingene på.

9
00:00:25,430 --> 00:00:31,200
Så lige i starten, går vi igennem prøve tegninger af binære træer og kram.

10
00:00:31,200 --> 00:00:35,970
Så her, "Husk, at et binært træ har knuder svarende til dem, en linket liste,

11
00:00:35,970 --> 00:00:38,150
undtagen i stedet for en pointer der er to: én for det venstre "barn"

12
00:00:38,150 --> 00:00:41,950
og én til højre "barn". "

13
00:00:41,950 --> 00:00:45,630
Så et binært træ er ligesom en linket liste,

14
00:00:45,630 --> 00:00:47,910
undtagen struct vil have to pointere.

15
00:00:47,910 --> 00:00:51,390
Der er ternær træer, som kommer til at have tre pegepinde,

16
00:00:51,390 --> 00:00:56,540
Der er N-ære træer, som blot har en generisk pointer

17
00:00:56,540 --> 00:01:00,320
at du derefter nødt til at allokere at være store nok til at have

18
00:01:00,320 --> 00:01:04,840
nok henvisninger til alle de mulige børn.

19
00:01:04,840 --> 00:01:08,200
Så binært træ bare tilfældigvis har et konstant antal af to.

20
00:01:08,200 --> 00:01:11,260
Hvis du vil, kan du give en sammenkædet liste som en Monadiske træ,

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

22
00:01:15,360 --> 00:01:18,060
"Tegn en æsker-og-pile diagram af et binært træ knude

23
00:01:18,060 --> 00:01:24,110
indeholdende Nate yndlings nummer, 7, hvor hvert barn pointer er null. "

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

25
00:01:27,780 --> 00:01:30,280
>> Det kommer til at være temmelig ligetil.

26
00:01:30,280 --> 00:01:36,150
Vi vil bare have en node, vil jeg trække det som en firkant.

27
00:01:36,150 --> 00:01:38,730
Og jeg vil tegne værdierne i her.

28
00:01:38,730 --> 00:01:41,090
Så værdien vil gå i her,

29
00:01:41,090 --> 00:01:44,770
og derefter ned her vil vi have den venstre markøren på venstre og højre markøren til højre.

30
00:01:44,770 --> 00:01:50,430
Og det er meget så konvention at kalde det venstre og højre, markøren navne.

31
00:01:50,430 --> 00:01:52,460
Begge disse vil 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å tilbage til her.

34
00:02:03,630 --> 00:02:05,700
"Med et sammenkædet liste, havde vi kun at gemme en pegepind

35
00:02:05,700 --> 00:02:09,639
til det første emne i listen for at huske det hele linkede liste, eller hele listen.

36
00:02:09,639 --> 00:02:11,650
Ligeledes med træer, har vi kun til at gemme en pegepind

37
00:02:11,650 --> 00:02:13,420
til en enkelt knude for at huske hele træet.

38
00:02:13,420 --> 00:02:15,980
Denne node er calle den 'root' af træet.

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

40
00:02:18,320 --> 00:02:21,690
sådan at du har en æsker-og-pile skildring af et binært træ

41
00:02:21,690 --> 00:02:25,730
med værdien 7 og derefter 3 i venstre,

42
00:02:25,730 --> 00:02:32,760
derefter 9 til højre, og derefter 6 på højre side af 3 ".

43
00:02:32,760 --> 00:02:34,810
Lad os se om jeg kan huske alt dette i mit hoved.

44
00:02:34,810 --> 00:02:37,670
Så det vil være vores rod op her.

45
00:02:37,670 --> 00:02:41,600
Vi har nogle pointer eller andet sted, noget, som vi vil kalde rod,

46
00:02:41,600 --> 00:02:45,140
og den peger mod denne fyr.

47
00:02:45,140 --> 00:02:48,490
Nu at lave en ny knude,

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

49
00:02:52,870 --> 00:02:57,140
Så en ny knude med 3, og det i første omgang peger null.

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

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

52
00:03:02,250 --> 00:03:06,840
Så vi ændre denne pointer til nu pege på denne fyr.

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

54
00:03:12,420 --> 00:03:14,620
som oprindeligt bare siger null.

55
00:03:14,620 --> 00:03:19,600
Vi vil ændre denne pointer, peg på 9,

56
00:03:19,600 --> 00:03:23,310
og vi ønsker nu at sætte 6 til højre for 3.

57
00:03:23,310 --> 00:03:32,170
Så det kommer til at - gøre en 6.

58
00:03:32,170 --> 00:03:34,310
Og den fyr vil pege dér.

59
00:03:34,310 --> 00:03:38,320
Okay. Så det er alt det beder os om at gøre.

60
00:03:38,320 --> 00:03:42,770
>> Lad os nu gå over nogle terminologi.

61
00:03:42,770 --> 00:03:46,690
Vi har allerede talt om, hvordan roden af ​​træet er det øverste knude i træet.

62
00:03:46,690 --> 00:03:54,720
Den ene indeholdende 7. Knudepunkterne i bunden af ​​træet kaldes bladene.

63
00:03:54,720 --> 00:04:01,240
Enhver knude der bare har nul som sine børn, er et blad.

64
00:04:01,240 --> 00:04:03,680
Så det er muligt, hvis vores binært træ er blot en enkelt node,

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

66
00:04:10,130 --> 00:04:12,060
"Den 'højde' af træet er antallet af humle du har at gøre

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

68
00:04:16,620 --> 00:04:18,640
Vi vil komme ind i en anden, forskellen

69
00:04:18,640 --> 00:04:21,940
mellem balancerede og ubalancerede binære træer,

70
00:04:21,940 --> 00:04:29,470
men for nu, den samlede højde af dette træ

71
00:04:29,470 --> 00:04:34,520
Jeg ville sige, er 3, selv hvis man tæller antallet af humle

72
00:04:34,520 --> 00:04:39,710
du nødt til at gøre for at komme til 9, så er det virkelig kun en højde på 2.

73
00:04:39,710 --> 00:04:43,340
Lige nu er det et ubalanceret binært træ,

74
00:04:43,340 --> 00:04:49,840
men vi vil talte om balanceret når det kommer til at være relevant.

75
00:04:49,840 --> 00:04:52,040
Så nu kan vi tale om knudepunkter i et træ i form

76
00:04:52,040 --> 00:04:54,700
i forhold til de andre knuder i træet.

77
00:04:54,700 --> 00:04:59,730
Så nu har vi forældre, børn, søskende, forfædre og efterkommere.

78
00:04:59,730 --> 00:05:05,650
De er temmelig sund fornuft, hvad de betyder.

79
00:05:05,650 --> 00:05:09,610
Hvis vi spørger - det er forældre.

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

81
00:05:12,830 --> 00:05:16,090
[Studerende] 7. >> Yeah. Moderselskabet er bare at være, hvad peger på dig.

82
00:05:16,090 --> 00:05:20,510
Så hvad er de børn af 7?

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

84
00:05:23,860 --> 00:05:26,460
Bemærk, at "børn" bogstaveligt betyder børn,

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

86
00:05:31,010 --> 00:05:35,540
Men så hvis vi går efterkommere, så hvad er efterkommere af 7?

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

88
00:05:37,500 --> 00:05:42,330
Efterkommerne af roden node bliver alt i træet,

89
00:05:42,330 --> 00:05:47,950
undtagen måske rodnoden selv, hvis du ikke ønsker at overveje at en efterkommer.

90
00:05:47,950 --> 00:05:50,750
Og endelig forfædre, så det er den modsatte retning.

91
00:05:50,750 --> 00:05:55,740
Så hvad er de forfædre 6?

92
00:05:55,740 --> 00:05:58,920
[Studerende] 3 og 7. >> Yeah. 9 er ikke inkluderet.

93
00:05:58,920 --> 00:06:02,520
Det er bare den direkte afstamning tilbage til roden

94
00:06:02,520 --> 00:06:13,230
bliver dine forfædre.

95
00:06:13,230 --> 00:06:16,300
>> "Vi siger, at et binært træ er» bestilt «, hvis for hver node i træet,

96
00:06:16,300 --> 00:06:19,530
alle sine efterkommere til venstre har mindre værdier

97
00:06:19,530 --> 00:06:22,890
og alle af dem til højre har større værdier.

98
00:06:22,890 --> 00:06:27,060
For eksempel er træet oven bestilt, men det er ikke den eneste mulige bestilte 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ært træ er også kendt som en binær søgning træ.

101
00:06:36,420 --> 00:06:38,660
Her er vi tilfældigvis være at kalde det en ordnet binært træ,

102
00:06:38,660 --> 00:06:41,850
men jeg har aldrig hørt det kaldt en bestilt binært træ før,

103
00:06:41,850 --> 00:06:46,650
og på en quiz vi er meget mere tilbøjelige til at sætte binær søgning træ.

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

105
00:06:49,250 --> 00:06:54,580
og det er vigtigt, at du erkender forskellen mellem binært træ og binær søgning træ.

106
00:06:54,580 --> 00:06:58,830
Et binært træ er blot et træ, der peger på to ting.

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

108
00:07:02,120 --> 00:07:06,310
Der er ingen begrundelse om de værdier, den peger på.

109
00:07:06,310 --> 00:07:11,370
Så gerne her over, da det er et binært søgetræ,

110
00:07:11,370 --> 00:07:14,030
vi ved, at hvis vi går tilbage af 7,

111
00:07:14,030 --> 00:07:16,670
så alle de værdier, som vi overhovedet kan nå

112
00:07:16,670 --> 00:07:19,310
ved at gå tilbage på 7 være mindre end 7.

113
00:07:19,310 --> 00:07:24,070
Bemærk, at alle værdier mindre end 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øjre for 7, alt skal være større end 7,

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

117
00:07:33,220 --> 00:07:36,150
Dette er ikke tilfældet for et binært træ,

118
00:07:36,150 --> 00:07:40,020
for en regelmæssig binært træ kan vi bare 3 i toppen, 7 mod venstre,

119
00:07:40,020 --> 00:07:47,630
9 til venstre på 7, og der er ingen bestilling af værdier overhovedet.

120
00:07:47,630 --> 00:07:56,140
Nu vil vi faktisk ikke gøre dette, fordi det er kedeligt og unødvendigt,

121
00:07:56,140 --> 00:07:59,400
men "forsøge at trække så mange bestilte træer, som du kan tænke på

122
00:07:59,400 --> 00:08:01,900
med numrene 7, 3, 9 og 6.

123
00:08:01,900 --> 00:08:06,800
Hvor mange forskellige arrangementer er der? Hvad er højden af ​​hver enkelt? "

124
00:08:06,800 --> 00:08:10,480
>> Vi vil gøre et par, men det vigtigste idé er,

125
00:08:10,480 --> 00:08:16,530
Dette er på ingen måde en unik repræsentation af et binært træ, der indeholder disse værdier.

126
00:08:16,530 --> 00:08:22,760
Alt, hvad vi behøver, er nogle binært træ, der indeholder 7, 3, 6 og 9.

127
00:08:22,760 --> 00:08:25,960
En anden mulig gyldigt ville være roden 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 ni.

130
00:08:32,730 --> 00:08:36,169
Det er en perfekt gyldig binær søgning træ.

131
00:08:36,169 --> 00:08:39,570
Det er ikke meget nyttigt, fordi det er ligesom en linket liste

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

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

134
00:08:48,900 --> 00:08:51,310
[Student] Må ikke værdierne er nødt til at være større på højre?

135
00:08:51,310 --> 00:08:56,700
Eller er det -? >> Disse Jeg mente at gå den anden vej.

136
00:08:56,700 --> 00:09:00,960
Der er også - Ja, lad os skifte 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 skal stadig at adlyde, hvad et binært træ søgning er meningen at gøre.

139
00:09:11,730 --> 00:09:15,650
Så alt til venstre skal være mindre end en given node.

140
00:09:15,650 --> 00:09:23,180
Vi kunne bare flytte, siger, denne 6 og sætte det her.

141
00:09:23,180 --> 00:09:26,880
Nej, vi kan ikke. Hvorfor skal jeg holde gør det?

142
00:09:26,880 --> 00:09:35,350
Lad os gøre - her er 6, her er 7, 6 point til 3.

143
00:09:35,350 --> 00:09:39,290
Det er stadig et gyldigt binær søgning træ.

144
00:09:39,290 --> 00:09:49,260
Hvad er der galt, hvis jeg - lad os se om jeg kan komme op med et arrangement.

145
00:09:49,260 --> 00:09:52,280
Ja, okay. Så hvad er der galt med dette træ?

146
00:09:52,280 --> 00:10:08,920
Jeg tror, ​​jeg har allerede givet dig en antydning af, at der er noget galt med det.

147
00:10:08,920 --> 00:10:14,430
Hvorfor skal jeg holde gør det?

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

149
00:10:18,510 --> 00:10:22,590
Hvis vi ser på hver knude, såsom 7 og derefter til venstre for 7 er en 3.

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

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

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

153
00:10:30,910 --> 00:10:36,330
[Studerende] 9 er stadig til venstre på 7. >> Yeah.

154
00:10:36,330 --> 00:10:43,710
Det må være sandt, at alle værdier, du kan muligvis nå ved at gå til venstre for 7 er mindre end 7.

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

156
00:10:49,120 --> 00:10:52,520
vi kan stadig komme til 9, men ved at have gået mindre end 7,

157
00:10:52,520 --> 00:10:55,070
bør vi ikke være i stand til at komme til et tal, der er større end 7.

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

159
00:10:59,830 --> 00:11:02,330
>> Min bror havde faktisk et interview spørgsmål

160
00:11:02,330 --> 00:11:07,760
Det var dybest set det, bare kode op noget at validere

161
00:11:07,760 --> 00:11:10,500
hvorvidt et træ er et binært søgetræ,

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

163
00:11:13,580 --> 00:11:17,020
hvis venstre og højre er korrekte, og derefter gentage dernede.

164
00:11:17,020 --> 00:11:19,700
Men du kan ikke bare gøre det, du er nødt til at holde styr

165
00:11:19,700 --> 00:11:22,550
af det faktum, at nu hvor jeg har gået tilbage på 7,

166
00:11:22,550 --> 00:11:26,340
alt i denne undertræ skal være mindre end 7.

167
00:11:26,340 --> 00:11:28,430
Den korrekte algoritme skal holde styr

168
00:11:28,430 --> 00:11:35,970
af grænserne, at værdierne muligvis kan falde i.

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

170
00:11:38,360 --> 00:11:41,630
Der er en nice gentagelse forhold,

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

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

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

174
00:11:53,180 --> 00:11:56,020
Tanken om, hvordan du ville gøre det matematisk er ligesom,

175
00:11:56,020 --> 00:11:59,770
du kan vælge et enkelt til at være roden node,

176
00:11:59,770 --> 00:12:03,160
og derefter, hvis jeg vælger 7 for at være roden node,

177
00:12:03,160 --> 00:12:08,150
så er der, siger, nogle numre, der kan gå være min venstre knude,

178
00:12:08,150 --> 00:12:10,440
og der er nogle tal, der kan være min højre knude,

179
00:12:10,440 --> 00:12:15,090
men hvis jeg har N Total tal, så det beløb, som kan gå til venstre

180
00:12:15,090 --> 00:12:18,820
plus det beløb, der kan gå til højre er n - 1.

181
00:12:18,820 --> 00:12:26,130
Så for de resterende tal, skal de være i stand til at gå enten til venstre eller højre.

182
00:12:26,130 --> 00:12:31,580
Det synes vanskeligt at hvis jeg sætter 3 først derefter alt har til at gå til venstre,

183
00:12:31,580 --> 00:12:35,080
men hvis jeg sætter 7, så nogle ting kan gå til venstre og nogle ting kan gå til højre.

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

185
00:12:39,570 --> 00:12:42,350
Det er virkelig, du bare nødt til at tænke på det som,

186
00:12:42,350 --> 00:12:47,980
hvor mange ting kan gå på det næste niveau af træet.

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

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

189
00:12:54,650 --> 00:13:01,120
>> Gå tilbage her,

190
00:13:01,120 --> 00:13:03,510
"Ordnet binære træer er cool, fordi vi kan søge igennem dem

191
00:13:03,510 --> 00:13:06,910
på en meget lignende måde at søge over et ordnet array.

192
00:13:06,910 --> 00:13:10,120
For at gøre det, vi starter ved roden og arbejde vores vej ned i træet

193
00:13:10,120 --> 00:13:13,440
mod blade,. kontrol med hvert nodens værdier mod de værdier, vi søger efter

194
00:13:13,440 --> 00:13:15,810
Hvis den aktuelle node værdi er mindre end den værdi, vi leder efter,

195
00:13:15,810 --> 00:13:18,050
du går ud for node ret barn.

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

197
00:13:20,030 --> 00:13:22,800
På et tidspunkt, vil du enten finde den værdi, du leder efter, eller du vil løbe ind i en null,

198
00:13:22,800 --> 00:13:28,520
angiver værdien er ikke i træet. "

199
00:13:28,520 --> 00:13:32,450
Jeg er nødt til at gentegne træet, vi havde før, det vil tage et sekund.

200
00:13:32,450 --> 00:13:38,280
Men vi ønsker at slå op, om 6, 10, og 1 er i træet.

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

202
00:13:49,180 --> 00:13:52,730
De numre, du ønsker at slå op, vi ønsker at se op 6.

203
00:13:52,730 --> 00:13:55,440
Hvordan virker denne algoritme arbejde?

204
00:13:55,440 --> 00:14:03,040
Nå, har vi også nogle rod pointer til vores træ.

205
00:14:03,040 --> 00:14:12,460
Og vi ville gå til roden og sige, er denne værdi svarende til den værdi, vi leder efter?

206
00:14:12,460 --> 00:14:15,000
Så vi leder efter 6, så det er ikke lige.

207
00:14:15,000 --> 00:14:20,140
Så vi holde ud, og nu siger vi, okay, så 6 er mindre end 7.

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

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

210
00:14:27,340 --> 00:14:33,340
Det er betydeligt lettere, er alt du skal gøre tegne en mulig knude af træet

211
00:14:33,340 --> 00:14:37,760
og derefter du lad være - i stedet for at forsøge at tænke i dit hoved,

212
00:14:37,760 --> 00:14:40,020
okay, hvis det er mindre, går jeg til venstre eller gå til højre,

213
00:14:40,020 --> 00:14:43,030
bare at kigge på dette billede, er det meget tydeligt, at jeg er nødt til at gå til venstre

214
00:14:43,030 --> 00:14:47,700
hvis dette knudepunkt er større end den værdi, som jeg leder efter.

215
00:14:47,700 --> 00:14:52,600
Så du går til venstre, nu er jeg ved 3.

216
00:14:52,600 --> 00:14:57,770
Jeg vil gerne - 3 er mindre end værdien jeg leder efter, hvilket er 6.

217
00:14:57,770 --> 00:15:03,420
Så vi går til højre, og nu jeg ender ved 6,

218
00:15:03,420 --> 00:15:07,380
som er værdien jeg leder efter, så jeg vender tilbage sandt.

219
00:15:07,380 --> 00:15:15,760
Den næste værdi jeg har tænkt mig at kigge efter, er 10.

220
00:15:15,760 --> 00:15:23,230
Okay. Så 10,, nu vil - afbrød det - kommer til at følge roden.

221
00:15:23,230 --> 00:15:27,670
Nu er 10 vil være større end 7, så jeg ønsker at se til højre.

222
00:15:27,670 --> 00:15:31,660
Jeg har tænkt mig at komme herover, er 10 bliver større end 9,

223
00:15:31,660 --> 00:15:34,520
så jeg har tænkt mig at ønsker at se til højre.

224
00:15:34,520 --> 00:15:42,100
Jeg kommer herover, men herovre nu er jeg ved null.

225
00:15:42,100 --> 00:15:44,170
Hvad gør jeg, hvis jeg ramte null?

226
00:15:44,170 --> 00:15:47,440
[Student] Tilbage falsk? >> Yeah. Jeg fandt ikke 10.

227
00:15:47,440 --> 00:15:49,800
1 bliver et næsten identisk fald,

228
00:15:49,800 --> 00:15:51,950
undtagen det bare kommer til at blive vendt, i stedet for at kigge

229
00:15:51,950 --> 00:15:56,540
ned i højre side, jeg kommer til at se ned langs venstre side.

230
00:15:56,540 --> 00:16:00,430
>> Nu tror jeg, vi rent faktisk får at kode.

231
00:16:00,430 --> 00:16:04,070
Her er hvor - åbne op for CS50 apparatet og navigere din vej,

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

233
00:16:07,010 --> 00:16:09,170
Det er sandsynligvis ideel til at gøre det i rummet,

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

235
00:16:13,760 --> 00:16:19,170
"Først vil vi brug for en ny type definition for et binært træ node indeholder int værdier.

236
00:16:19,170 --> 00:16:21,400
Brug af standardteksten typedef nedenfor,

237
00:16:21,400 --> 00:16:24,510
oprette en ny type definition for en node i et binært træ.

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

239
00:16:27,930 --> 00:16:30,380
Så lad os sætte standardtekst her,

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

241
00:16:41,630 --> 00:16:44,270
Så hvad er de felter, vi gerne vil have i vores knude?

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

243
00:16:46,520 --> 00:16:49,700
>> Int. value, to pointere? Hvordan kan jeg skrive pointers?

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

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

246
00:17:01,320 --> 00:17:03,460
Og husk diskussionen fra sidste gang,

247
00:17:03,460 --> 00:17:15,290
at dette giver ingen mening, det giver ingen mening,

248
00:17:15,290 --> 00:17:18,270
dette giver ingen mening.

249
00:17:18,270 --> 00:17:25,000
Du har brug for alt, hvad der med henblik på at definere dette rekursiv struct.

250
00:17:25,000 --> 00:17:27,970
Okay, så det er hvad vores træ kommer til at se ud.

251
00:17:27,970 --> 00:17:37,670
Hvis vi gjorde en ternær træ, så et knudepunkt kunne se ud B1, B2, struct node * b3,

252
00:17:37,670 --> 00:17:43,470
hvor b er en gren - faktisk har jeg mere hørt det venstre, midt, højre, men uanset hvad.

253
00:17:43,470 --> 00:17:55,610
Vi har kun bekymrer sig om binær, så højre, venstre.

254
00:17:55,610 --> 00:17:59,110
"Nu erklærer en global node * variabel for roden af ​​træet."

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

256
00:18:01,510 --> 00:18:08,950
For at gøre tingene lidt vanskeligere og mere generaliseret,

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

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

259
00:18:16,710 --> 00:18:20,500
og det betyder, at nedenfor, når vi begynder at køre

260
00:18:20,500 --> 00:18:23,130
vores indeholder funktionsmoduler og vores insert funktion,

261
00:18:23,130 --> 00:18:27,410
i stedet for vore indeholder funktionsmoduler bare at bruge denne globale node variabel,

262
00:18:27,410 --> 00:18:34,280
vi bliver nødt til det tage som et argument træet, som vi ønsker det skal behandle.

263
00:18:34,280 --> 00:18:36,650
Under den globale variabel skulle gøre tingene lettere.

264
00:18:36,650 --> 00:18:42,310
Vi kommer til at gøre tingene sværere.

265
00:18:42,310 --> 00:18:51,210
Nu tage et minut eller så at bare gøre den slags ting,

266
00:18:51,210 --> 00:18:57,690
hvor indersiden af ​​main du vil oprette dette træ, og det er alt du ønsker at gøre.

267
00:18:57,690 --> 00:19:04,530
Prøv og konstruere dette træ i din primære funktion.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Så du behøver ikke engang at have beregnet træet hele vejen endnu.

269
00:19:47,610 --> 00:19:49,840
Men nogen der har noget jeg kunne trække op

270
00:19:49,840 --> 00:20:03,130
at vise, hvordan man kan begynde at bygge et sådant træ?

271
00:20:03,130 --> 00:20:08,080
[Student] Nogen banging, forsøger at komme ud.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Enhver komfortable med deres træ konstruktion?

273
00:20:13,100 --> 00:20:15,520
[Student] Sure. Det er ikke sket. >> Det er okay. Vi kan bare færdig -

274
00:20:15,520 --> 00:20:26,860
åh, kan du gemme den? Hurra.

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

276
00:20:32,020 --> 00:20:34,770
Er jeg zoomet ind?

277
00:20:34,770 --> 00:20:37,730
Zoom ind ved at rulle ud. >> Jeg har et spørgsmål. >> Ja?

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

279
00:20:44,410 --> 00:20:47,160
[Bowden] Nej >> Okay. Så du ville have til at initialisere -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nej Når du definerer, eller når du erklærer en struct,

281
00:20:50,450 --> 00:20:55,600
det er ikke initialiseret som standard, det er ligesom, hvis du erklærer en int.

282
00:20:55,600 --> 00:20:59,020
Det er nøjagtig det samme. Det er ligesom hver af dens individuelle felter

283
00:20:59,020 --> 00:21:04,460
kan have en skraldespand værdi i det. >> Og er det muligt at definere - eller at erklære en struct

284
00:21:04,460 --> 00:21:07,740
på en sådan måde, at det gør initialisere dem?

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

286
00:21:13,200 --> 00:21:18,660
kommer til at se ud -

287
00:21:18,660 --> 00:21:22,200
Der er to måder, vi kan gøre dette. Jeg synes, vi skal kompilere det

288
00:21:22,200 --> 00:21:25,840
at sikre Dunk også gør det.

289
00:21:25,840 --> 00:21:28,510
Rækkefølgen af ​​argumenter, der kommer i struct,

290
00:21:28,510 --> 00:21:32,170
du lægger som rækkefølgen af ​​argumenter indersiden af ​​disse krøllede parenteser.

291
00:21:32,170 --> 00:21:35,690
Så hvis du ønsker at initialisere den til 9 og overlades null og derefter til højre være null,

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

293
00:21:41,570 --> 00:21:47,890
Alternativet er, og redaktøren kan ikke lide denne syntaks,

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

295
00:21:50,300 --> 00:22:01,800
men alternativet er noget lignende -

296
00:22:01,800 --> 00:22:04,190
her, vil jeg sætte det på en ny linje.

297
00:22:04,190 --> 00:22:09,140
Du kan udtrykkeligt sige, jeg glemmer den nøjagtige syntaks.

298
00:22:09,140 --> 00:22:13,110
Så du kan tage eksplicit stilling til dem ved navn, og sige,

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

300
00:22:21,570 --> 00:22:24,540
Jeg kan gætte disse skal være kommaer.

301
00:22:24,540 --> 00:22:29,110
. Højre = NULL, så denne måde behøver du ikke

302
00:22:29,110 --> 00:22:33,780
rent faktisk har brug for at vide rækkefølgen af ​​struct,

303
00:22:33,780 --> 00:22:36,650
og når du læser dette, er det meget mere eksplicit

304
00:22:36,650 --> 00:22:41,920
hvad værdien der bliver initialiseret til.

305
00:22:41,920 --> 00:22:44,080
>> Dette sker for at være en af ​​de ting, -

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

307
00:22:49,100 --> 00:22:54,160
Du kan tage C-kode, skal du flytte det over til C + +, og det bør udarbejde.

308
00:22:54,160 --> 00:22:59,570
Dette er en af ​​de ting, C + + understøtter ikke, så folk har en tendens til ikke at gøre det.

309
00:22:59,570 --> 00:23:01,850
Jeg ved ikke, om det er den eneste grund til folk har en tendens til ikke at gøre det,

310
00:23:01,850 --> 00:23:10,540
men det tilfælde, hvor jeg behov for at bruge det nødvendigt at arbejde med C + + og så kunne jeg ikke bruge det.

311
00:23:10,540 --> 00:23:14,000
Et andet eksempel på noget, der ikke fungerer sammen 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 sige char * x = malloc uanset hvad,

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

315
00:23:22,840 --> 00:23:25,450
Denne automatiske cast sker ikke i C + +.

316
00:23:25,450 --> 00:23:28,150
Det ville ikke kompilere, og du vil eksplicit nødt til at sige

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

318
00:23:34,510 --> 00:23:37,270
Der 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 syntaks.

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

322
00:23:46,150 --> 00:23:49,470
hvad er - kunne være galt med det?

323
00:23:49,470 --> 00:23:52,170
[Student] Jeg behøver ikke at dereference det? >> Yeah.

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

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

326
00:23:58,230 --> 00:24:04,300
vi ønsker at bruge. at få på et felt inde i struct.

327
00:24:04,300 --> 00:24:07,200
Og den eneste gang vi bruger pil er, når vi ønsker at gøre -

328
00:24:07,200 --> 00:24:13,450
godt, pil svarer til -

329
00:24:13,450 --> 00:24:17,020
det er, hvad det ville have betydet, hvis jeg brugte pil.

330
00:24:17,020 --> 00:24:24,600
Alle pil betyder er, dereference dette, nu er jeg på en struct, og jeg kan få feltet.

331
00:24:24,600 --> 00:24:28,040
Enten får feltet direkte eller dereference og få marken -

332
00:24:28,040 --> 00:24:30,380
Jeg tror det skulle være værdi.

333
00:24:30,380 --> 00:24:33,910
Men her jeg beskæftiger sig med blot en struct, ikke en pointer til en struct,

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

335
00:24:38,780 --> 00:24:47,510
Men den slags ting, vi kan gøre for alle noder.

336
00:24:47,510 --> 00:24:55,790
Åh min Gud.

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

338
00:25:09,540 --> 00:25:16,470
Så kan vi oprette filialer i vores træ, kan vi have 7 -

339
00:25:16,470 --> 00:25:21,650
vi kan have, bør dens venstre pege på 3.

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

341
00:25:25,130 --> 00:25:29,320
[Studerende, uforståelig] >> Yeah. Adressen på node3,

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

343
00:25:34,170 --> 00:25:38,190
Men husk, at det er henvisninger til de næste noder.

344
00:25:38,190 --> 00:25:44,930
Den ret bør pege på 9,

345
00:25:44,930 --> 00:25:53,330
og 3 skal pege på retten til 6.

346
00:25:53,330 --> 00:25:58,480
Jeg tror, ​​det er alle indstillet. Eventuelle kommentarer eller spørgsmål?

347
00:25:58,480 --> 00:26:02,060
[Studerende, uforståelig] Roden bliver 7.

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

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

350
00:26:14,160 --> 00:26:20,730
>> Til vores formål vil vi beskæftige sig med indsatsen,

351
00:26:20,730 --> 00:26:25,490
så vil vi ønsker at skrive en funktion til at indsætte i denne binært træ

352
00:26:25,490 --> 00:26:34,230
og indsatsen er uundgåeligt vil kalde malloc at oprette en ny node for dette træ.

353
00:26:34,230 --> 00:26:36,590
Så tingene kommer til at få rodet med det faktum, at nogle knuder

354
00:26:36,590 --> 00:26:38,590
er i øjeblikket på stakken

355
00:26:38,590 --> 00:26:43,680
og andre knudepunkter kommer til at ende op på den bunke, når vi indsætter dem.

356
00:26:43,680 --> 00:26:47,640
Det er helt i orden, men den eneste grund

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

358
00:26:49,600 --> 00:26:51,840
er fordi det er sådan en konstrueret eksempel, som vi kender

359
00:26:51,840 --> 00:26:56,360
træet formodes at være konstrueret som 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Hvis vi ikke havde det, så ville vi ikke behøver at allokere i første omgang.

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

362
00:27:06,160 --> 00:27:08,570
Lige nu er det helt rimeligt at lægge på stakken,

363
00:27:08,570 --> 00:27:14,750
men lad os ændre det til en malloc gennemførelse.

364
00:27:14,750 --> 00:27:17,160
Så hver af disse er nu vil være noget i retning af

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

366
00:27:24,240 --> 00:27:28,040
Og nu vi er nødt til at gøre vores kontrol.

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

368
00:27:34,010 --> 00:27:40,950
returnere 1, og så kan vi gøre node9-> fordi nu er det en pointer,

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øjre = NULL,

371
00:27:48,930 --> 00:27:51,410
og vi bliver nødt til at gøre det for hver af disse knudepunkter.

372
00:27:51,410 --> 00:27:57,490
Så i stedet, lad os sige det inde i en separat funktion.

373
00:27:57,490 --> 00:28:00,620
Lad os kalde det node * build_node,

374
00:28:00,620 --> 00:28:09,050
og det er noget der ligner det API'er vi sørge for Huffman kodning.

375
00:28:09,050 --> 00:28:12,730
Vi giver dig initializer funktioner for et træ

376
00:28:12,730 --> 00:28:20,520
og Deconstructor "funktioner" for de træer og det samme for skovene.

377
00:28:20,520 --> 00:28:22,570
>> Så her vil vi have en startværdi funktion

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

379
00:28:25,170 --> 00:28:29,320
Og det kommer til at se temmelig meget nøjagtigt som dette.

380
00:28:29,320 --> 00:28:32,230
Og jeg selv kommer til at være doven og ikke ændre navnet på den variabel,

381
00:28:32,230 --> 00:28:34,380
selv om node9 meningsløst længere.

382
00:28:34,380 --> 00:28:38,610
Åh, jeg gætte node9 værdi ikke skulle have været 6.

383
00:28:38,610 --> 00:28:42,800
Nu kan vi vende tilbage node9.

384
00:28:42,800 --> 00:28:49,550
Og her bør vi vende tilbage null.

385
00:28:49,550 --> 00:28:52,690
Alle er enige om, at Build-A-node funktion?

386
00:28:52,690 --> 00:28:59,780
Så nu kan vi bare kalde det at bygge en node med en bestemt værdi, og null-pegepinde.

387
00:28:59,780 --> 00:29:09,750
Nu kan vi kalde det, kan vi gøre node * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Og lad os gø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 nu ønsker vi at etablere de samme pejlemærker,

391
00:29:39,330 --> 00:29:42,470
undtagen nu alt er allerede i form af pegepinde

392
00:29:42,470 --> 00:29:48,480
så ikke længere brug for adressen på.

393
00:29:48,480 --> 00:29:56,300
Okay. Så hvad er den sidste ting, jeg ønsker at gøre?

394
00:29:56,300 --> 00:30:03,850
Der er en fejlkontrol, at jeg ikke gør.

395
00:30:03,850 --> 00:30:06,800
Hvad betyder bygge knude afkast?

396
00:30:06,800 --> 00:30:11,660
[Studerende, uforståelig] >> Yeah. Hvis malloc mislykkedes, vil den vende tilbage null.

397
00:30:11,660 --> 00:30:16,460
Så jeg har tænkt mig at lazily sætte den ned her i stedet for at gøre en betingelse for hver.

398
00:30:16,460 --> 00:30:22,320
Hvis (node9 == NULL, eller - endnu nemmere,

399
00:30:22,320 --> 00:30:28,020
dette svarer til blot 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, returnere 1.

401
00:30:38,310 --> 00:30:42,850
Måske skulle vi udskrive malloc fejlede, eller noget.

402
00:30:42,850 --> 00:30:46,680
[Student] Er falsk lig med nul så godt?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Enhver nulværdi er falsk.

404
00:30:51,290 --> 00:30:53,920
Så null er en værdi på nul.

405
00:30:53,920 --> 00:30:56,780
Nul er en nulværdi. False er en nul værdi.

406
00:30:56,780 --> 00:31:02,130
Enhver - temmelig de kun 2 nulværdier er nul og nul,

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

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

409
00:31:13,030 --> 00:31:17,890
Hvis vi havde node * rod op her,

410
00:31:17,890 --> 00:31:24,150
derefter - den pæne ting om globale variabler er, at de altid har en indledende værdi.

411
00:31:24,150 --> 00:31:27,500
Det er ikke sandt af funktioner, hvor indersiden af ​​her,

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

413
00:31:34,870 --> 00:31:37,380
Vi har ingen idé om, hvad x.value, x.whatever,

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

415
00:31:40,700 --> 00:31:44,980
Det er ikke tilfældet for globale variable.

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

417
00:31:47,450 --> 00:31:53,410
Som standard, alt det, der er global, hvis ikke udtrykkeligt initialiseret til en vis værdi,

418
00:31:53,410 --> 00:31:57,390
har en værdi på nul som sin værdi.

419
00:31:57,390 --> 00:32:01,150
Så her, node * rod, vi ikke udtrykkeligt initialisere det til noget,

420
00:32:01,150 --> 00:32:06,350
så dens standardværdi vil blive nulstillet, der er nulværdi af pointere.

421
00:32:06,350 --> 00:32:11,870
Standardværdien af ​​x vil betyde, at x.value er nul,

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å da det er en struct, vil alle felterne i struct være nulværdier.

424
00:32:21,070 --> 00:32:24,410
Vi behøver ikke at bruge det her, selv om.

425
00:32:24,410 --> 00:32:27,320
[Student] De struct er anderledes end andre variabler, og de andre variabler er

426
00:32:27,320 --> 00:32:31,400
skrald værdier, disse er nuller?

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

428
00:32:36,220 --> 00:32:40,070
Hvis det er på globalt omfang, det har en initial værdi. >> Okay.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Enten den oprindelige værdi, du gav det eller nul.

430
00:32:48,950 --> 00:32:53,260
Jeg tror, ​​der tager sig af alt dette.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Så den næste del af spørgsmålet oplyst,

432
00:32:58,390 --> 00:33:01,260
"Nu vil vi skrive en funktion kaldet indeholder

433
00:33:01,260 --> 00:33:04,930
med en prototype af bool indeholder int værdi. "

434
00:33:04,930 --> 00:33:08,340
Vi vil ikke gøre bool indeholder int værdi.

435
00:33:08,340 --> 00:33:15,110
Vores prototype kommer til at ligne

436
00:33:15,110 --> 00:33:22,380
bool indeholder (int værdi.

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

438
00:33:24,490 --> 00:33:28,870
at det skulle kontrollere om det har denne værdi.

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

440
00:33:38,290 --> 00:33:44,440
Og så kan vi kalde det med noget lignende,

441
00:33:44,440 --> 00:33:46,090
måske vil vi gerne printf eller noget.

442
00:33:46,090 --> 00:33:51,040
Indeholder 6, vores rod.

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

444
00:33:54,300 --> 00:33:59,390
hvorimod indeholder 5 root bør vende tilbage falsk.

445
00:33:59,390 --> 00:34:02,690
Så tag et sekund at gennemføre denne.

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

447
00:34:06,780 --> 00:34:09,739
Det gode ved den måde, vi har sat tingene op, er, at

448
00:34:09,739 --> 00:34:12,300
den egner sig til vores rekursiv løsning meget lettere

449
00:34:12,300 --> 00:34:14,719
end den globale variabel måde gjorde.

450
00:34:14,719 --> 00:34:19,750
For hvis vi bare har indeholder int værdi, så vi har ingen mulighed for rekursiv ned undertræer.

451
00:34:19,750 --> 00:34:24,130
Vi skulle have en separat hjælpefunktion, der recurses ned undertræer for os.

452
00:34:24,130 --> 00:34:29,610
Men da vi har ændret det til at tage træet som et argument,

453
00:34:29,610 --> 00:34:32,760
som det burde have altid været i første omgang,

454
00:34:32,760 --> 00:34:35,710
Nu kan vi recurse lettere.

455
00:34:35,710 --> 00:34:38,960
Så iterative eller rekursiv, vil vi gå over både,

456
00:34:38,960 --> 00:34:46,139
men vi vil se, at rekursive ender med at blive ganske let.

457
00:34:59,140 --> 00:35:02,480
Okay. Er der nogen der har noget, vi kan arbejde med?

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

459
00:35:12,000 --> 00:35:16,030
Okay, det ser godt ud.

460
00:35:16,030 --> 00:35:18,920
Så ønsker at gå os gennem det?

461
00:35:18,920 --> 00:35:25,780
[Student] Sure. Så jeg satte en temp variabel at få den første node i træet.

462
00:35:25,780 --> 00:35:28,330
Og så vil jeg bare sløjfes igennem, mens temp ikke er lig nul,

463
00:35:28,330 --> 00:35:31,700
så mens stadig var i træet, tror jeg.

464
00:35:31,700 --> 00:35:35,710
Og hvis værdien er lig med den værdi, temp peger på,

465
00:35:35,710 --> 00:35:37,640
så det returnerer den værdi.

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

467
00:35:40,210 --> 00:35:43,400
Hvis du nogensinde får en situation, hvor der ikke er mere træ,

468
00:35:43,400 --> 00:35:47,330
så det vender tilbage - den kommer ud af løkken og returnerer falsk.

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

470
00:35:52,190 --> 00:35:58,470
Nogen der har nogen kommentarer til noget?

471
00:35:58,470 --> 00:36:02,400
Jeg har ingen rigtighed kommentarer overhovedet.

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

473
00:36:11,020 --> 00:36:21,660
Åh, det kommer til at gå en lille aflang.

474
00:36:21,660 --> 00:36:33,460
Jeg ordner det op. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Alle bør huske, hvordan ternære virker.

476
00:36:37,150 --> 00:36:38,610
Der har helt klart været quizzer i fortiden

477
00:36:38,610 --> 00:36:41,170
der giver dig en funktion med en ternær operatør,

478
00:36:41,170 --> 00:36:45,750
og sige, oversætte dette, gøre noget, der ikke bruger ternære.

479
00:36:45,750 --> 00:36:49,140
Så dette er en meget almindelig sag, når jeg ville synes at bruge ternære,

480
00:36:49,140 --> 00:36:54,610
hvor hvis nogen betingelse en variabel til noget,

481
00:36:54,610 --> 00:36:58,580
ellers indstillet, at samme variabel til noget andet.

482
00:36:58,580 --> 00:37:03,390
Det er noget, som meget ofte kan omdannes til denne slags ting

483
00:37:03,390 --> 00:37:14,420
hvor indstille denne variabel til dette - eller godt, er det sandt? Så er dette, ellers dette.

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

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. Den måde jeg altid læse det er, temp lig værdi større end temp værdi,

486
00:37:25,570 --> 00:37:30,680
derefter dette, ellers dette. Det er at stille et spørgsmål.

487
00:37:30,680 --> 00:37:35,200
Er det større? Så gør den første ting. Else gøre den anden ting.

488
00:37:35,200 --> 00:37:41,670
Jeg har næsten altid - i tyktarmen, jeg bare - i mit hoved, læste jeg som andre steder.

489
00:37:41,670 --> 00:37:47,180
>> Er der nogen der har en rekursiv løsning?

490
00:37:47,180 --> 00:37:49,670
Okay. Denne ene vil vi - det kunne allerede være stor,

491
00:37:49,670 --> 00:37:53,990
men vi vil gøre det endnu bedre.

492
00:37:53,990 --> 00:37:58,720
Dette er stort set den samme nøjagtige idé.

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

494
00:38:03,060 --> 00:38:08,340
[Student] Sure. Så vi laver sikker på, at træet ikke er nul først,

495
00:38:08,340 --> 00:38:13,380
fordi hvis træet er null så det kommer til at returnere falsk, fordi vi ikke har fundet det.

496
00:38:13,380 --> 00:38:19,200
Og hvis der er stadig et træ, vi går ind i - vi først kontrollere, hvis værdien er den aktuelle node.

497
00:38:19,200 --> 00:38:23,740
Returnerer sand, hvis den er, og hvis vi ikke recurse til venstre eller højre.

498
00:38:23,740 --> 00:38:25,970
Lyder det passende? >> Mm-hmm. (Aftalen)

499
00:38:25,970 --> 00:38:33,880
Så bemærke, at det er næsten - strukturelt meget lig den iterative løsning.

500
00:38:33,880 --> 00:38:38,200
Det er bare at i stedet for rekursiv havde vi en while-løkke.

501
00:38:38,200 --> 00:38:40,840
Og basen tilfældet her, hvor træ ikke er lig nul

502
00:38:40,840 --> 00:38:44,850
var en situation, hvor vi brød ud af while-løkken.

503
00:38:44,850 --> 00:38:50,200
De er meget ens. Men vi vil tage dette et skridt videre.

504
00:38:50,200 --> 00:38:54,190
Nu gør vi det samme her.

505
00:38:54,190 --> 00:38:57,680
Bemærk vi tilbage det samme i begge disse linjer,

506
00:38:57,680 --> 00:39:00,220
undtagen for ét argument er anderledes.

507
00:39:00,220 --> 00:39:07,950
Så vi vil gøre det til en ternær.

508
00:39:07,950 --> 00:39:13,790
Jeg ramte option noget, og det gjorde et symbol. Okay.

509
00:39:13,790 --> 00:39:21,720
Så vi vil vende tilbage indeholder det.

510
00:39:21,720 --> 00:39:28,030
Dette bliver at være flere linjer, ja, zoomet ind det er.

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

512
00:39:31,060 --> 00:39:38,640
sætte et mellemrum efter pilen, men jeg gætte, hvis du er konsekvent, det er fint.

513
00:39:38,640 --> 00:39:44,320
Hvis værdi er mindre end træ værdi, vi ønsker at recurse på træ til venstre,

514
00:39:44,320 --> 00:39:53,890
ellers vil vi recurse på træ til højre.

515
00:39:53,890 --> 00:39:58,610
Så det var første skridt i at gøre dette look mindre.

516
00:39:58,610 --> 00:40:02,660
Trin to af gøre dette look mindre -

517
00:40:02,660 --> 00:40:09,150
vi kan adskille dette til flere linier.

518
00:40:09,150 --> 00:40:16,500
Okay. Trin to af gør det ser mindre er her,

519
00:40:16,500 --> 00:40:25,860
så returværdi lig træ værdi, eller indeholder uanset.

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

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

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

523
00:40:34,740 --> 00:40:41,060
Idéen her er værdi == træ værdi.

524
00:40:41,060 --> 00:40:49,960
Hvis det er sandt, så er det sandt, og vi ønsker at 'eller' at med det, der er herovre.

525
00:40:49,960 --> 00:40:52,520
Så uden at tænke over hvad der er herovre,

526
00:40:52,520 --> 00:40:55,070
hvad er hele udtrykket vil vende tilbage?

527
00:40:55,070 --> 00:40:59,430
[Student] True? >> Ja, fordi sand af noget,

528
00:40:59,430 --> 00:41:04,990
or'd - eller ægte or'd med noget er nødvendigvis sandt.

529
00:41:04,990 --> 00:41:08,150
Så snart vi ser returværdi = træ værdi,

530
00:41:08,150 --> 00:41:10,140
Vi vil bare returnere sandt.

531
00:41:10,140 --> 00:41:15,710
Ikke engang gå til recurse indeholder yderligere ned på linjen.

532
00:41:15,710 --> 00:41:20,980
Vi kan tage et skridt videre.

533
00:41:20,980 --> 00:41:29,490
Return træ ikke er lig nul, og alt dette.

534
00:41:29,490 --> 00:41:32,650
Det gjorde det til en one-line funktion.

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 nu er det den samme idé -

537
00:41:40,680 --> 00:41:47,320
i stedet for - så hvis træet ikke er lig nul - eller, ja,

538
00:41:47,320 --> 00:41:49,580
hvis træet ikke lig nul, hvilket er slemt tilfælde,

539
00:41:49,580 --> 00:41:54,790
hvis træet er lig nul, så den første betingelse vil være falsk.

540
00:41:54,790 --> 00:42:00,550
Så falsk anded med noget kommer til at være, hvad?

541
00:42:00,550 --> 00:42:04,640
[Student] Falsk. >> Yeah. Dette er den anden halvdel af kortslutning evaluering,

542
00:42:04,640 --> 00:42:10,710
hvor, hvis træet ikke lige null, så vi ikke kommer til at selv gå -

543
00:42:10,710 --> 00:42:14,930
eller hvis træet ikke lige null, så vi ikke kommer til at gøre værdi == tree værdi.

544
00:42:14,930 --> 00:42:17,010
Vi vil bare straks returnere falsk.

545
00:42:17,010 --> 00:42:20,970
Hvilket er vigtigt, fordi hvis det gjorde ikke kortslutte evaluere,

546
00:42:20,970 --> 00:42:25,860
så hvis træet ikke lige null, er denne anden betingelse vil seg fejl,

547
00:42:25,860 --> 00:42:32,510
fordi træ-> værdi dereferere null.

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

549
00:42:40,490 --> 00:42:44,840
Dette er en meget almindelig ting også, ikke at gøre denne ene linje med dette,

550
00:42:44,840 --> 00:42:49,000
men det er en fælles ting i forhold, måske ikke lige her,

551
00:42:49,000 --> 00:42:59,380
men hvis (træ! = NULL, og træ-> værdi == værdi), gør hvad.

552
00:42:59,380 --> 00:43:01,560
Dette er en meget almindelig tilstand, hvor i stedet for at

553
00:43:01,560 --> 00:43:06,770
at bryde denne i to hvis'er, hvor gerne, er træet null?

554
00:43:06,770 --> 00:43:11,780
Okay, det er ikke null, så nu er træet værdi svarende til værdi? Gør dette.

555
00:43:11,780 --> 00:43:17,300
I stedet er denne betingelse, vil dette aldrig seg fejl

556
00:43:17,300 --> 00:43:21,220
fordi det vil bryde ud, hvis dette sker for at være nul.

557
00:43:21,220 --> 00:43:24,000
Tja, jeg gætte, hvis dit træ er en helt ugyldig pointer, kan det stadig seg fejl,

558
00:43:24,000 --> 00:43:26,620
men det kan ikke seg skyld, hvis træet er null.

559
00:43:26,620 --> 00:43:32,900
Hvis det var null, ville det bryde ud, før du nogensinde derefererede markøren i første omgang.

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

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

562
00:43:40,770 --> 00:43:49,880
Lazy evaluering er mere som du beder om en værdi,

563
00:43:49,880 --> 00:43:54,270
du bede om at beregne en værdi, slags, men du behøver ikke det samme.

564
00:43:54,270 --> 00:43:59,040
Så indtil du rent faktisk har brug for det, er det ikke vurderes.

565
00:43:59,040 --> 00:44:03,920
Det er ikke nøjagtigt det samme, men i Huffman Pset,

566
00:44:03,920 --> 00:44:06,520
den siger, at vi "dovent" skrive.

567
00:44:06,520 --> 00:44:08,670
Grunden til vi gør det er, fordi vi rent faktisk er at pufre skrive -

568
00:44:08,670 --> 00:44:11,820
vi ønsker ikke at skrive individuelle bits ad gangen,

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

570
00:44:15,450 --> 00:44:19,270
Så når vi har en luns af bytes, så vil vi skrive det ud.

571
00:44:19,270 --> 00:44:22,640
Selvom du beder den om at skrive - og fwrite og fread gøre det samme slags ting.

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

573
00:44:26,260 --> 00:44:31,610
Selvom man bede den om at skrive det samme, er det sandsynligvis ikke.

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

575
00:44:34,540 --> 00:44:37,540
indtil du ringer hfclose eller hvad det er,

576
00:44:37,540 --> 00:44:39,620
som derefter siger, okay, jeg lukker min fil,

577
00:44:39,620 --> 00:44:43,450
det betyder at jeg hellere skrive alt det, jeg har ikke skrevet endnu.

578
00:44:43,450 --> 00:44:45,770
Det har ingen grund til at skrive alt ud

579
00:44:45,770 --> 00:44:49,010
indtil du lukker filen, og så skal det.

580
00:44:49,010 --> 00:44:56,220
Så det er bare hvad doven - det venter, indtil det skal ske.

581
00:44:56,220 --> 00:44:59,990
Dette - at tage 51 og du vil gå ind i det mere detaljeret,

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

583
00:45:05,470 --> 00:45:08,890
Der er ingen iterative løsninger, dybest set.

584
00:45:08,890 --> 00:45:11,550
Alt er rekursion, og doven evaluering

585
00:45:11,550 --> 00:45:14,790
vil være vigtig for mange omstændigheder

586
00:45:14,790 --> 00:45:19,920
hvor, hvis du ikke dovent vurdere, ville det betyde -

587
00:45:19,920 --> 00:45:24,760
Eksemplet er strømme, som er uendeligt lange.

588
00:45:24,760 --> 00:45:30,990
I teorien kan du tænke på de naturlige tal som en strøm af 1-2-3-4-5-6-7,

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

590
00:45:33,090 --> 00:45:37,210
Hvis jeg siger, at jeg vil have den tiende nummer, så jeg kan vurdere op til det tiende nummer.

591
00:45:37,210 --> 00:45:40,300
Hvis jeg vil have det hundrededel nummer, så jeg kan vurdere op til det hundrededel nummer.

592
00:45:40,300 --> 00:45:46,290
Uden doven evaluering, er det så kommer til at forsøge at evaluere alle numre med det samme.

593
00:45:46,290 --> 00:45:50,000
Du evaluerer uendeligt mange tal, og det er bare ikke muligt.

594
00:45:50,000 --> 00:45:52,080
Så der er en masse tilfælde, hvor doven evaluering

595
00:45:52,080 --> 00:45:57,840
er bare vigtigt for at få tingene til at fungere.

596
00:45:57,840 --> 00:46:05,260
>> Nu ønsker vi at skrive insert hvor indsatsen vil være

597
00:46:05,260 --> 00:46:08,430
ligeledes ændre sig i sin definition.

598
00:46:08,430 --> 00:46:10,470
Så lige nu er det bool insert (int værdi).

599
00:46:10,470 --> 00:46:23,850
Vi vil ændre det til bool insert (int værdi, node * træ).

600
00:46:23,850 --> 00:46:29,120
Vi faktisk kommer til at ændre det igen i en smule, vil vi se hvorfor.

601
00:46:29,120 --> 00:46:32,210
Og lad os gå build_node, bare for dælen af ​​det,

602
00:46:32,210 --> 00:46:36,730
ovenfor indsætte så vi ikke behøver at skrive en funktion prototype.

603
00:46:36,730 --> 00:46:42,450
Hvilket er en antydning af, at du skal bruge build_node i indsatsen.

604
00:46:42,450 --> 00:46:49,590
Okay. Tag et minut til det.

605
00:46:49,590 --> 00:46:52,130
Jeg tror, ​​jeg har gemt revisionen, hvis du ønsker at trække fra,

606
00:46:52,130 --> 00:47:00,240
eller i det mindste, hvad jeg nu.

607
00:47:00,240 --> 00:47:04,190
Jeg ønskede en lille pause til at tænke over logikken i indsatsen,

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

609
00:47:08,750 --> 00:47:12,860
Dybest set, vil du altid kun være indsættelse af blade.

610
00:47:12,860 --> 00:47:18,640
Ligesom, hvis jeg indsætter 1, så er jeg uundgåeligt vil være at indsætte 1 -

611
00:47:18,640 --> 00:47:21,820
Jeg skifter til sort - æ være at indsætte 1 herovre.

612
00:47:21,820 --> 00:47:28,070
Eller hvis jeg indsætter 4, jeg ønsker at blive indsætte 4 herovre.

613
00:47:28,070 --> 00:47:32,180
Så uanset hvad du gør, er du nødt til at indsætte på et blad.

614
00:47:32,180 --> 00:47:36,130
Alt du skal gøre er at gentage ned i træet, indtil du kommer til knudepunktet

615
00:47:36,130 --> 00:47:40,890
der bør være knudens forælder, den nye node forælder,

616
00:47:40,890 --> 00:47:44,560
og derefter ændre sin venstre eller højre markør, afhængigt af om

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

618
00:47:47,060 --> 00:47:51,180
Ændre denne pegepind til at pege på din nye node.

619
00:47:51,180 --> 00:48:05,490
Så gentage ned i træet, at bladet peger på det nye knudepunkt.

620
00:48:05,490 --> 00:48:09,810
Også tænke over, hvorfor der forbyder den type situation før,

621
00:48:09,810 --> 00:48:17,990
hvor jeg bygget det binære træ, hvor det var korrekt

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

623
00:48:19,920 --> 00:48:24,830
men 9 var til venstre for 7 Hvis du gentog ned hele vejen.

624
00:48:24,830 --> 00:48:29,770
Så det er umuligt i dette scenario, da -

625
00:48:29,770 --> 00:48:32,530
tænker på at indsætte 9 eller noget, i det første emne,

626
00:48:32,530 --> 00:48:35,350
Jeg har tænkt mig at se 7 og jeg bare tænkt mig at gå til højre.

627
00:48:35,350 --> 00:48:38,490
Så uanset hvad jeg gør, hvis jeg indsætter ved at gå til et blad,

628
00:48:38,490 --> 00:48:40,790
og et blad ved hjælp af en passende algoritme,

629
00:48:40,790 --> 00:48:43,130
det vil være umuligt for mig at indsætte 9 til venstre på 7

630
00:48:43,130 --> 00:48:48,250
fordi så snart jeg ramte 7 Jeg har tænkt mig at gå til højre.

631
00:48:59,740 --> 00:49:02,070
Er der nogen der har noget at starte med?

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

633
00:49:05,480 --> 00:49:09,200
[Studerende, 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 værdsat. Okay. Vil du forklare?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Da vi ved, at vi var at indsætte

637
00:49:20,690 --> 00:49:24,060
nye knudepunkter i slutningen af ​​træet,

638
00:49:24,060 --> 00:49:28,070
Jeg sløjfes igennem træet iterativt

639
00:49:28,070 --> 00:49:31,360
indtil jeg fik til et knudepunkt, der pegede til null.

640
00:49:31,360 --> 00:49:34,220
Og så besluttede jeg mig for at sige det enten på højre eller venstre side

641
00:49:34,220 --> 00:49:37,420
benytter denne ret variabel, og det fortalte mig, hvor til at sætte det.

642
00:49:37,420 --> 00:49:41,850
Og så væsentlige, jeg har lige lavet det sidste -

643
00:49:41,850 --> 00:49:47,520
at temp node peger på det nye knudepunkt, at det skabte,

644
00:49:47,520 --> 00:49:50,770
enten på venstre side eller højre side, alt efter hvad værdien højre var.

645
00:49:50,770 --> 00:49:56,530
Endelig jeg indstille den nye node værdi til værdien af ​​sin test.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okay, så jeg ser et spørgsmål her.

647
00:49:59,550 --> 00:50:02,050
Det er ligesom 95% af vejen.

648
00:50:02,050 --> 00:50:07,550
Den ene spørgsmål, som jeg ser, ja, er der nogen andre se et problem?

649
00:50:07,550 --> 00:50:18,400
Hvad er den omstændighed, hvorunder de bryder ud af løkken?

650
00:50:18,400 --> 00:50:22,100
[Student] Hvis temp er null? >> Yeah. Så hvordan du bryde ud af løkken er, hvis temp er null.

651
00:50:22,100 --> 00:50:30,220
Men hvad gør jeg lige her?

652
00:50:30,220 --> 00:50:35,410
Jeg dereference temp, hvilket er uundgåeligt null.

653
00:50:35,410 --> 00:50:39,840
Så den anden ting du skal gøre, er ikke bare holde styr indtil temp er nul,

654
00:50:39,840 --> 00:50:45,590
der skal holde styr på den forælder på alle tidspunkter.

655
00:50:45,590 --> 00:50:52,190
Vi ønsker også node * forælder, jeg tror vi kan holde denne på nul i første omgang.

656
00:50:52,190 --> 00:50:55,480
Dette vil have underlige adfærd for roden af ​​træet,

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

658
00:50:59,210 --> 00:51:03,950
Hvis værdi er større end hvad, så temp = temp højre.

659
00:51:03,950 --> 00:51:07,910
Men før vi gør det, forælder = temp.

660
00:51:07,910 --> 00:51:14,500
Eller er forældre altid vil lige temp? Er det tilfældet?

661
00:51:14,500 --> 00:51:19,560
Hvis temp ikke er nul, så jeg har tænkt mig at flytte ned, uanset hvad,

662
00:51:19,560 --> 00:51:24,030
til et knudepunkt, hvor temp er moderselskab.

663
00:51:24,030 --> 00:51:27,500
Så forælder kommer til at være temp, og så flytter jeg temp ned.

664
00:51:27,500 --> 00:51:32,410
Nu temp er nul, men forældre peger på moderselskab ting, der er null.

665
00:51:32,410 --> 00:51:39,110
Så hernede, jeg ikke ønsker at indstille højre er lig med 1.

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

667
00:51:41,300 --> 00:51:45,130
og jeg gætter du også ønsker at gøre -

668
00:51:45,130 --> 00:51:48,530
hvis du flytter til venstre, du ønsker at indstille højre lig med 0.

669
00:51:48,530 --> 00:51:55,950
Eller også, hvis du nogensinde gå til højre.

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

671
00:51:58,590 --> 00:52:04,260
Nu ønsker vi at gøre den forælder rigtige pointer newnode,

672
00:52:04,260 --> 00:52:08,520
ellers vil vi gøre den forælder venstre pointer newnode.

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

674
00:52:16,850 --> 00:52:24,880
Okay. Så dette er den måde, vi - ja, faktisk, i stedet for at gøre dette,

675
00:52:24,880 --> 00:52:29,630
vi halvdelen forventes at bruge build_node.

676
00:52:29,630 --> 00:52:40,450
Og så hvis newnode lig nul, returnerer falsk.

677
00:52:40,450 --> 00:52:44,170
Det er det. Nu, dette er hvad vi forventede dig at gøre.

678
00:52:44,170 --> 00:52:47,690
>> Det er, hvad de ansatte løsninger gør.

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

680
00:52:52,360 --> 00:52:57,820
men det er helt fint, og det vil virke.

681
00:52:57,820 --> 00:53:02,840
En ting, der er lidt underligt lige nu er

682
00:53:02,840 --> 00:53:08,310
hvis træet starter som null, vi passere i en null-træ.

683
00:53:08,310 --> 00:53:12,650
Jeg gætter det afhænger af, hvordan du definerer opførsel passere i en null træ.

684
00:53:12,650 --> 00:53:15,490
Jeg vil tro, at hvis du sender en null træ,

685
00:53:15,490 --> 00:53:17,520
derefter indsætte værdien i en null træ

686
00:53:17,520 --> 00:53:23,030
skal bare returnere et træ, hvor den eneste værdi, er, at en enkelt node.

687
00:53:23,030 --> 00:53:25,830
Må folk enig i det? Du kunne, hvis man ville,

688
00:53:25,830 --> 00:53:28,050
hvis du sender en null træ

689
00:53:28,050 --> 00:53:31,320
og du ønsker at indsætte en værdi i det, returnere falsk.

690
00:53:31,320 --> 00:53:33,830
Det er op til dig at definere det.

691
00:53:33,830 --> 00:53:38,320
For at gøre det første, jeg sagde, og derefter -

692
00:53:38,320 --> 00:53:40,720
godt, er du nødt til at have problemer med at gøre det, fordi

693
00:53:40,720 --> 00:53:44,090
det ville være lettere, hvis vi havde en global pointer til de ting,

694
00:53:44,090 --> 00:53:48,570
men vi ved ikke, så hvis træet er nul, er der intet vi kan gøre ved det.

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

696
00:53:50,960 --> 00:53:52,840
Så jeg har tænkt mig at ændre indsatsen.

697
00:53:52,840 --> 00:53:56,540
Vi teknisk kunne blot ændre denne ret her,

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

699
00:53:58,400 --> 00:54:04,530
men jeg har tænkt mig at ændre indsatsen til at tage en node ** træ.

700
00:54:04,530 --> 00:54:07,510
Dobbelte pointers.

701
00:54:07,510 --> 00:54:09,710
Hvad betyder dette?

702
00:54:09,710 --> 00:54:12,330
Stedet for at behandle pegepinde til knudepunkter,

703
00:54:12,330 --> 00:54:16,690
de ting, jeg har tænkt mig at manipulere er denne pointer.

704
00:54:16,690 --> 00:54:18,790
Jeg har tænkt mig at blive manipulere denne pointer.

705
00:54:18,790 --> 00:54:21,770
Jeg har tænkt mig at blive manipulere pointers direkte.

706
00:54:21,770 --> 00:54:25,760
Dette giver mening, da tænke ned -

707
00:54:25,760 --> 00:54:33,340
godt, lige nu tyder det til null.

708
00:54:33,340 --> 00:54:38,130
Hvad jeg ønsker, er at manipulere denne pegepind til at pege på ikke null.

709
00:54:38,130 --> 00:54:40,970
Jeg vil have det til at pege på min nye node.

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

711
00:54:44,870 --> 00:54:47,840
så behøver jeg ikke at holde styr på en forælder pointer.

712
00:54:47,840 --> 00:54:52,640
Jeg kan bare holde styr at se, om markøren peger til null,

713
00:54:52,640 --> 00:54:54,580
og hvis markøren peger til null,

714
00:54:54,580 --> 00:54:57,370
ændre det til at pege på den knude, jeg ønsker.

715
00:54:57,370 --> 00:55:00,070
Og jeg kan ændre det, da jeg har en pointer til pointer.

716
00:55:00,070 --> 00:55:02,040
Lad os se det lige nu.

717
00:55:02,040 --> 00:55:05,470
Du kan faktisk gøre det rekursivt temmelig nemt.

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

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

720
00:55:10,980 --> 00:55:16,790
>> Lad os se det rekursivt.

721
00:55:16,790 --> 00:55:24,070
For det første er hvad vores base case vil være?

722
00:55:24,070 --> 00:55:29,140
Næsten altid vores base case, men faktisk, det er lidt tricky.

723
00:55:29,140 --> 00:55:34,370
Første ting først, hvis (træ == NULL)

724
00:55:34,370 --> 00:55:37,550
Jeg gætter vi bare vil vende tilbage falsk.

725
00:55:37,550 --> 00:55:40,460
Dette er forskelligt fra dit træ er null.

726
00:55:40,460 --> 00:55:44,510
Dette er markøren til dit rod pointer er null

727
00:55:44,510 --> 00:55:48,360
hvilket betyder, at din rod pointer ikke eksisterer.

728
00:55:48,360 --> 00:55:52,390
Så hernede, hvis jeg gør

729
00:55:52,390 --> 00:55:55,760
node * - lad os bare genbruge det.

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

731
00:55:58,960 --> 00:56:00,730
og så jeg har tænkt mig at kalde indsatsen ved at gøre noget lignende,

732
00:56:00,730 --> 00:56:04,540
indsætte 4 ind & rod.

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

734
00:56:06,560 --> 00:56:11,170
derefter & rod vil være et knudepunkt **.

735
00:56:11,170 --> 00:56:15,120
Dette er gyldig. I dette tilfælde, træ, op her,

736
00:56:15,120 --> 00:56:20,120
træ ikke er nul - eller indsats.

737
00:56:20,120 --> 00:56:24,630
Her. Tree er ikke null; * træ er nul, hvilket er fint

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

739
00:56:26,680 --> 00:56:29,210
nu pege på, hvad jeg vil have det til at pege på.

740
00:56:29,210 --> 00:56:34,750
Men hvis træet er null, det betyder, at jeg bare kom herned og sagde null.

741
00:56:34,750 --> 00:56:42,710
Det giver ikke mening. Jeg kan ikke gøre noget med det.

742
00:56:42,710 --> 00:56:45,540
Hvis træet er nul, returnerer falsk.

743
00:56:45,540 --> 00:56:48,220
Så jeg dybest set allerede sagt, hvad vores virkelige base case er.

744
00:56:48,220 --> 00:56:50,580
Og hvad er det kommer til at være?

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

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

747
00:57:00,000 --> 00:57:04,520
Det drejer sig om sagen herovre

748
00:57:04,520 --> 00:57:09,640
hvor hvis min røde pointer er markøren jeg fokuseret på,

749
00:57:09,640 --> 00:57:12,960
så ligesom jeg fokuseret på dette pointer, nu er jeg fokuseret på denne pegepind.

750
00:57:12,960 --> 00:57:15,150
Nu er jeg fokuseret på denne pegepind.

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

752
00:57:18,160 --> 00:57:22,880
er nogensinde - hvis *, min røde viser, er altid null,

753
00:57:22,880 --> 00:57:28,470
det betyder, at jeg er på det tilfælde, hvor jeg fokuserer på en pegepind, der peger -

754
00:57:28,470 --> 00:57:32,530
dette er en pegepind, der hører til et blad.

755
00:57:32,530 --> 00:57:41,090
Jeg ønsker at ændre denne pegepind til at pege på min nye node.

756
00:57:41,090 --> 00:57:45,230
Kom tilbage herovre.

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

758
00:57:56,490 --> 00:58:07,300
så n, hvis n = NULL, returnere falsk.

759
00:58:07,300 --> 00:58:12,600
Else vi ønsker at ændre, hvad markøren er i øjeblikket peger på

760
00:58:12,600 --> 00:58:17,830
nu henvise til vores nybyggede node.

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

762
00:58:20,280 --> 00:58:30,660
I stedet for at sige n, siger vi * træ = hvis * træ.

763
00:58:30,660 --> 00:58:35,450
Alle forstår, at? At ved at behandle med pointere til pointere,

764
00:58:35,450 --> 00:58:40,750
vi kan ændre null-pegepinde til at pege på ting, vi ønsker dem til at pege på.

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

766
00:58:42,820 --> 00:58:45,740
>> Nu er vores tilbagefald, eller vores rekursion,

767
00:58:45,740 --> 00:58:51,430
vil være meget lig alle andre rekursioner vi har gjort.

768
00:58:51,430 --> 00:58:55,830
Vi vil ønsker at indsætte værdi,

769
00:58:55,830 --> 00:58:59,040
og nu vil jeg bruge ternære igen, men hvad er vores betingelse vil være?

770
00:58:59,040 --> 00:59:05,180
Hvad er det vi leder efter til at beslutte, om vi ønsker at gå til venstre eller højre?

771
00:59:05,180 --> 00:59:07,760
Lad os gøre det i separate trin.

772
00:59:07,760 --> 00:59:18,850
Hvis (værdi <) hvad?

773
00:59:18,850 --> 00:59:23,200
[Student] Træets værdi?

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

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

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, så lige her, lad os sige, at det grønne pil

777
00:59:34,140 --> 00:59:39,050
er et eksempel på det træ øjeblikket er, er en pointer til den pointer.

778
00:59:39,050 --> 00:59:46,610
Så det betyder, at jeg er en pegepind til en pegepind til 3.

779
00:59:46,610 --> 00:59:48,800
Den dereference to gange lød godt.

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

781
00:59:51,010 --> 00:59:53,210
[Student] Dereference én gang, og derefter gøre pil på den måde?

782
00:59:53,210 --> 00:59:58,420
[Bowden] So (* træ) er dereference en gang, -> værdi

783
00:59:58,420 --> 01:00:05,960
vil give mig værdien af ​​den node, som jeg indirekte jeg peger på.

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

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

786
01:00:18,490 --> 01:00:26,190
Hvis det er tilfældet, så vil jeg kalde indsætte med værdi.

787
01:00:26,190 --> 01:00:32,590
Og hvad er min opdateret node ** kommer til at være?

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

789
01:00:39,440 --> 01:00:41,900
Og jeg vil bevæge markøren, at ting

790
01:00:41,900 --> 01:00:44,930
således at hvis venstre ender med at blive nulhenvisning,

791
01:00:44,930 --> 01:00:48,360
Jeg kan ændre det til at pege på min nye node.

792
01:00:48,360 --> 01:00:51,460
>> Og det andet tilfælde kan være meget ens.

793
01:00:51,460 --> 01:00:55,600
Lad os faktisk gøre, at min ternære lige nu.

794
01:00:55,600 --> 01:01:04,480
Indsæt værdi, hvis værdi <(** træ). Værdi.

795
01:01:04,480 --> 01:01:11,040
Så vi ønsker at opdatere vores ** til venstre,

796
01:01:11,040 --> 01:01:17,030
ellers vil vi opdatere vores ** til højre.

797
01:01:17,030 --> 01:01:22,540
[Student] Betyder det få markøren til pointer?

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

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

800
01:01:35,040 --> 01:01:41,140
** Tree.right er ligesom denne pointer eller noget.

801
01:01:41,140 --> 01:01:45,140
Så ved at tage en pegepind til det, giver det mig, hvad jeg vil

802
01:01:45,140 --> 01:01:50,090
af markøren til den fyr.

803
01:01:50,090 --> 01:01:54,260
[Student] Kunne vi gå igen, hvorfor vi bruger de to pointere?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Så - nej, du kan, og at løsningen før

805
01:01:58,220 --> 01:02:04,540
var en måde at gøre det uden at gøre to pointere.

806
01:02:04,540 --> 01:02:08,740
Du skal være i stand til at forstå ved hjælp af to pointere,

807
01:02:08,740 --> 01:02:11,660
og dette er en renere løsning.

808
01:02:11,660 --> 01:02:16,090
Bemærk også, at, hvad sker der, hvis mit træ -

809
01:02:16,090 --> 01:02:24,480
hvad sker der hvis min rod var null? Hvad sker der, hvis jeg gør denne sag lige her?

810
01:02:24,480 --> 01:02:30,540
Så node * root = NULL, skal du indsætte 4 ind & rod.

811
01:02:30,540 --> 01:02:35,110
Hvad er root vil være efter dette?

812
01:02:35,110 --> 01:02:37,470
[Studerende, uforståelig] >> Yeah.

813
01:02:37,470 --> 01:02:41,710
Root værdi vil være 4.

814
01:02:41,710 --> 01:02:45,510
Root venstre bliver null, er root ret vil være null.

815
01:02:45,510 --> 01:02:49,490
I tilfælde, hvor vi ikke gik igennem rod efter adresse,

816
01:02:49,490 --> 01:02:52,490
Vi kunne ikke ændre rod.

817
01:02:52,490 --> 01:02:56,020
I det tilfælde, hvor træet - hvor rod var null,

818
01:02:56,020 --> 01:02:58,410
havde vi blot at returnere falsk. Der er intet vi kunne gøre.

819
01:02:58,410 --> 01:03:01,520
Vi kan ikke indsætte en node i en tom træ.

820
01:03:01,520 --> 01:03:06,810
Men nu kan vi, vi skal bare lave en tom træ ind i en et-node træ.

821
01:03:06,810 --> 01:03:13,400
Hvilket er normalt den forventede måde, at det er meningen at arbejde.

822
01:03:13,400 --> 01:03:21,610
>> Endvidere er betydeligt kortere end

823
01:03:21,610 --> 01:03:26,240
også at holde styr på den forælder, og så du gentage ned hele vejen.

824
01:03:26,240 --> 01:03:30,140
Nu har jeg mine forældre, og jeg bare har mine forældre ret pointer til hvad som helst.

825
01:03:30,140 --> 01:03:35,640
I stedet, hvis vi gjorde dette iterativt, ville det være den samme idé med en while-løkke.

826
01:03:35,640 --> 01:03:38,100
Men i stedet for at skulle beskæftige sig med min overordnede pointer,

827
01:03:38,100 --> 01:03:40,600
i stedet min nuværende pointer ville være den ting

828
01:03:40,600 --> 01:03:43,790
at jeg direkte er ved at ændre til at pege på min nye node.

829
01:03:43,790 --> 01:03:46,090
Jeg behøver ikke at beskæftige sig med, om den peger mod venstre.

830
01:03:46,090 --> 01:03:48,810
Jeg behøver ikke at beskæftige sig med, om den peger mod højre.

831
01:03:48,810 --> 01:04:00,860
Det er bare hvad denne pointer er, vil jeg sætte den til at pege på min nye node.

832
01:04:00,860 --> 01:04:05,740
Alle forstå hvordan det virker?

833
01:04:05,740 --> 01:04:09,460
Hvis ikke hvorfor vi ønsker at gøre det på denne måde,

834
01:04:09,460 --> 01:04:14,920
men i det mindste at det fungerer som en løsning?

835
01:04:14,920 --> 01:04:17,110
[Student] Hvor skal vi returnere sandt?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Det er nok lige her.

837
01:04:21,550 --> 01:04:26,690
Hvis vi rigtigt indsætte det, returnere sandt.

838
01:04:26,690 --> 01:04:32,010
Else, hernede vil vi ønsker at vende tilbage uanset insert afkast.

839
01:04:32,010 --> 01:04:35,950
>> Og hvad er specielt ved denne rekursiv funktion?

840
01:04:35,950 --> 01:04:43,010
Det er halerekursive, så længe vi kompilere med nogle optimering,

841
01:04:43,010 --> 01:04:48,060
det vil erkende det, og du vil aldrig få en stak overflow fra dette,

842
01:04:48,060 --> 01:04:53,230
selvom vores træ har en højde på 10.000 eller 10 mio.

843
01:04:53,230 --> 01:04:55,630
[Studerende, uforståelig]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Jeg tror det gør det på Dash - eller hvad optimering niveau

845
01:05:00,310 --> 01:05:03,820
er nødvendig for en hale rekursion at blive genkendt.

846
01:05:03,820 --> 01:05:09,350
Jeg tror, ​​det anerkender - GCC og Dunk

847
01:05:09,350 --> 01:05:12,610
også have forskellige betydninger for deres optimering niveauer.

848
01:05:12,610 --> 01:05:17,870
Jeg vil sige, det er DashO 2, for sikker på, at det vil genkende hale rekursion.

849
01:05:17,870 --> 01:05:27,880
Men vi - du kunne konstruere som en Fibonocci eksempel eller noget.

850
01:05:27,880 --> 01:05:30,030
Det er ikke nemt at teste med dette, fordi det er svært at konstruere

851
01:05:30,030 --> 01:05:32,600
et binært træ, der er så stort.

852
01:05:32,600 --> 01:05:37,140
Men ja, jeg synes det er DashO 2, at

853
01:05:37,140 --> 01:05:40,580
hvis du kompilerer med DashO 2, vil den kigge efter hale rekursion

854
01:05:40,580 --> 01:05:54,030
og optimere det ud.

855
01:05:54,030 --> 01:05:58,190
Lad os gå tilbage til - indsæt er bogstaveligt talt det sidste, den har brug for.

856
01:05:58,190 --> 01:06:04,900
Lad os gå tilbage til indsatsen over her

857
01:06:04,900 --> 01:06:07,840
hvor vi vil gøre det samme idé.

858
01:06:07,840 --> 01:06:14,340
Det vil stadig have fejl af ikke at kunne helt klare

859
01:06:14,340 --> 01:06:17,940
når roden selv er nul, eller den tidligere post er nul,

860
01:06:17,940 --> 01:06:20,060
men i stedet for at behandle en forælder pointer,

861
01:06:20,060 --> 01:06:27,430
lad os anvende den samme logik holder henvisninger til pegepinde.

862
01:06:27,430 --> 01:06:35,580
Hvis her vi holder vores node ** cur,

863
01:06:35,580 --> 01:06:37,860
og vi har ikke brug for at holde styr på højre længere,

864
01:06:37,860 --> 01:06:47,190
men node ** nuværende = & træ.

865
01:06:47,190 --> 01:06:54,800
Og nu er vores while-løkke bliver mens * cur ikke er lig nul.

866
01:06:54,800 --> 01:07:00,270
Behøver ikke at holde styr på forældre længere.

867
01:07:00,270 --> 01:07:04,180
Behøver ikke at holde styr på venstre og højre.

868
01:07:04,180 --> 01:07:10,190
Og jeg vil kalde det temp, fordi vi allerede bruger temp.

869
01:07:10,190 --> 01:07:17,200
Okay. Så hvis (værdi> * temp),

870
01:07:17,200 --> 01:07:24,010
derefter & (* temp) -> højre

871
01:07:24,010 --> 01:07:29,250
ellers temp = & (* temp) -> til venstre.

872
01:07:29,250 --> 01:07:32,730
Og nu, på dette tidspunkt, efter denne while-løkken

873
01:07:32,730 --> 01:07:36,380
Jeg kun gøre det, fordi det måske er nemmere at tænke iterativt end rekursivt,

874
01:07:36,380 --> 01:07:39,010
men efter denne while-løkken,

875
01:07:39,010 --> 01:07:43,820
* Temp er markøren vi ønsker at ændre.

876
01:07:43,820 --> 01:07:48,960
>> Før vi havde forælder, og vi ønskede at ændre begge forældre til venstre eller forælder til højre,

877
01:07:48,960 --> 01:07:51,310
men hvis vi ønsker at ændre forælder ret,

878
01:07:51,310 --> 01:07:54,550
derefter * temp er forælder til højre, og vi kan ændre det direkte.

879
01:07:54,550 --> 01:08:05,860
Så hernede, kan vi gøre * temp = newnode, og det er det.

880
01:08:05,860 --> 01:08:09,540
Så varsel, var alle vi gjorde i denne tage ud linjer kode.

881
01:08:09,540 --> 01:08:14,770
For at holde styr på den forælder i alt det ekstra indsats.

882
01:08:14,770 --> 01:08:18,689
Her, hvis vi bare holde styr på markøren til markøren,

883
01:08:18,689 --> 01:08:22,990
og selv hvis vi ønskede at slippe af med alle disse krøllede parenteser nu,

884
01:08:22,990 --> 01:08:27,170
gøre det ser kortere.

885
01:08:27,170 --> 01:08:32,529
Det er nu nøjagtig den samme løsning,

886
01:08:32,529 --> 01:08:38,210
men færre linjer kode.

887
01:08:38,210 --> 01:08:41,229
Når du begynder at anerkende dette som en gyldig løsning,

888
01:08:41,229 --> 01:08:43,529
Det er også lettere at ræsonnere om end lignende, okay,

889
01:08:43,529 --> 01:08:45,779
hvorfor skal jeg dette flag på int ret?

890
01:08:45,779 --> 01:08:49,290
Hvad betyder det? Åh, det signalerer, at

891
01:08:49,290 --> 01:08:51,370
hver gang jeg går til højre, jeg er nødt til at indstille det,

892
01:08:51,370 --> 01:08:53,819
ellers hvis jeg går forlod jeg er nødt til at sætte den til nul.

893
01:08:53,819 --> 01:09:04,060
Her behøver jeg ikke at ræsonnere over det, det er bare nemmere at tænke over.

894
01:09:04,060 --> 01:09:06,710
Spørgsmål?

895
01:09:06,710 --> 01:09:16,290
[Studerende, uforståelig] >> Yeah.

896
01:09:16,290 --> 01:09:23,359
Okay, så i den sidste bit -

897
01:09:23,359 --> 01:09:28,080
Jeg gætte en hurtig og nem funktion, vi kan gøre, er,

898
01:09:28,080 --> 01:09:34,910
let's - sammen, tror jeg, så prøv og skrive en indeholder funktion

899
01:09:34,910 --> 01:09:38,899
der er ligeglad om det er en binær søgning træ.

900
01:09:38,899 --> 01:09:43,770
Denne indeholder funktion skal returnere true

901
01:09:43,770 --> 01:09:58,330
hvis overalt i denne generelle binært træ er den værdi, vi leder efter.

902
01:09:58,330 --> 01:10:02,520
Så lad os først gøre det rekursivt, og så vil vi gøre det iterativt.

903
01:10:02,520 --> 01:10:07,300
Vi kan faktisk bare gøre det sammen, fordi det vil være meget kort.

904
01:10:07,300 --> 01:10:11,510
>> Hvad er min base case vil blive?

905
01:10:11,510 --> 01:10:13,890
[Studerende, uforståelig]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Så hvis (træ == NULL), hvad så?

907
01:10:18,230 --> 01:10:22,740
[Student] Tilbage falsk.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, ja, jeg har ikke brug for andet.

909
01:10:26,160 --> 01:10:30,250
Hvis var min anden base case.

910
01:10:30,250 --> 01:10:32,450
[Student] Tree værdi? >> Yeah.

911
01:10:32,450 --> 01:10:36,430
Så hvis (træ-> værdi == værdi.

912
01:10:36,430 --> 01:10:39,920
Bemærk vi er tilbage til node *, ikke node ** s?

913
01:10:39,920 --> 01:10:42,990
Indeholder vil aldrig bruge en node **,

914
01:10:42,990 --> 01:10:45,480
da vi ikke ændrer pointers.

915
01:10:45,480 --> 01:10:50,540
Vi bare gennemkører dem.

916
01:10:50,540 --> 01:10:53,830
Hvis det sker, så vil vi returnere sandt.

917
01:10:53,830 --> 01:10:58,270
Else ønsker vi at krydse børnene.

918
01:10:58,270 --> 01:11:02,620
Så vi kan ikke ræsonnere om, hvorvidt alt til venstre er mindre

919
01:11:02,620 --> 01:11:05,390
og alt til højre er større.

920
01:11:05,390 --> 01:11:09,590
Så hvad er vores betingelse vil være her - eller hvad skal vi gøre?

921
01:11:09,590 --> 01:11:11,840
[Studerende, uforståelig] >> Yeah.

922
01:11:11,840 --> 01:11:17,400
Return indeholder (værdi, træ-> venstre)

923
01:11:17,400 --> 01:11:26,860
eller indeholder (værdi, træ-> højre). Og det er det.

924
01:11:26,860 --> 01:11:29,080
Og mærke der er en vis kortslutning evaluering,

925
01:11:29,080 --> 01:11:32,520
hvor, hvis vi tilfældigvis finde værdien i det venstre træ,

926
01:11:32,520 --> 01:11:36,820
vi aldrig nødt til at se på det rigtige træ.

927
01:11:36,820 --> 01:11:40,430
Det er den samlede funktion.

928
01:11:40,430 --> 01:11:43,690
Lad os nu gøre det iterativt,

929
01:11:43,690 --> 01:11:48,060
der vil være mindre rart.

930
01:11:48,060 --> 01:11:54,750
Vi tager den sædvanlige start node * cur = træ.

931
01:11:54,750 --> 01:12:03,250
Mens (nuværende! = NULL).

932
01:12:03,250 --> 01:12:08,600
Hurtigt kommer til at se et problem.

933
01:12:08,600 --> 01:12:12,250
Hvis cur - herude, hvis vi nogensinde bryde ud af dette,

934
01:12:12,250 --> 01:12:16,020
så vi har kørt ud af ting at se på, så returnere falsk.

935
01:12:16,020 --> 01:12:24,810
Hvis (aktu-> værdi == værdi) returnere sandt.

936
01:12:24,810 --> 01:12:32,910
Så nu er vi på et sted -

937
01:12:32,910 --> 01:12:36,250
Vi ved ikke, om vi ønsker at gå til venstre eller højre.

938
01:12:36,250 --> 01:12:44,590
Så vilkårligt, lad os bare gå til venstre.

939
01:12:44,590 --> 01:12:47,910
Jeg har selvfølgelig løbe ind i et problem, hvor jeg har fuldstændig forladt alt -

940
01:12:47,910 --> 01:12:50,760
Jeg vil altid kun tjek venstre side af et træ.

941
01:12:50,760 --> 01:12:56,050
Jeg vil aldrig se noget, der er en ret barn af noget.

942
01:12:56,050 --> 01:13:00,910
Hvordan kan jeg løse dette?

943
01:13:00,910 --> 01:13:05,260
[Student] Du er nødt til at holde styr på den venstre og højre i en stak.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Så lad os gøre det

945
01:13:13,710 --> 01:13:32,360
struct liste, node * n, og derefter node ** næste?

946
01:13:32,360 --> 01:13:40,240
Jeg tror, ​​der virker fint.

947
01:13:40,240 --> 01:13:45,940
Vi ønsker at gå over til venstre, eller let's - heroppe.

948
01:13:45,940 --> 01:13:54,350
Struct List List =, vil det starte

949
01:13:54,350 --> 01:13:58,170
på nuværende struct liste.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Så det kommer til at blive vores linkede liste

951
01:14:04,040 --> 01:14:08,430
af undertræer som vi har sprunget over.

952
01:14:08,430 --> 01:14:13,800
Vi kommer til at gennemkrydse tilbage nu,

953
01:14:13,800 --> 01:14:17,870
men da vi uundgåeligt nødt til at komme tilbage til højre,

954
01:14:17,870 --> 01:14:26,140
Vi kommer til at holde den højre side inde i vores struct liste.

955
01:14:26,140 --> 01:14:32,620
Så må vi have new_list eller struct,

956
01:14:32,620 --> 01:14:41,080
struct liste *, new_list = malloc (sizeof (liste)).

957
01:14:41,080 --> 01:14:44,920
Jeg har tænkt mig at ignorere fejlsøgning det, men du bør tjekke for at se om det er null.

958
01:14:44,920 --> 01:14:50,540
New_list node det vil pege på -

959
01:14:50,540 --> 01:14:56,890
åh, det er derfor jeg ville have det op her. Det kommer til at pege på en anden struct liste.

960
01:14:56,890 --> 01:15:02,380
Det er bare hvordan forbundet lister arbejde.

961
01:15:02,380 --> 01:15:04,810
Dette er det samme som en int forbundet liste

962
01:15:04,810 --> 01:15:06,960
bortset fra at vi lige er erstatter int med node *.

963
01:15:06,960 --> 01:15:11,040
Det er nøjagtig det samme.

964
01:15:11,040 --> 01:15:15,100
Så new_list, værdien af ​​vores new_list node,

965
01:15:15,100 --> 01:15:19,120
bliver cur-> højre.

966
01:15:19,120 --> 01:15:24,280
Værdien af ​​vores new_list-> næste bliver vores oprindelige liste,

967
01:15:24,280 --> 01:15:30,760
og så vil vi opdatere vores liste til at pege på new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nu har vi brug for en slags måde at trække tingene,

969
01:15:33,650 --> 01:15:37,020
ligesom vi har krydset hele venstre undertræ.

970
01:15:37,020 --> 01:15:40,480
Nu skal vi til at trække ting ud af det,

971
01:15:40,480 --> 01:15:43,850
ligesom cur er null; vi ikke bare ønsker at returnere falsk.

972
01:15:43,850 --> 01:15:50,370
Vi vil nu trække udenfor på vores nye liste.

973
01:15:50,370 --> 01:15:53,690
En bekvem måde at gøre dette - ja, faktisk er der flere måder at gøre dette.

974
01:15:53,690 --> 01:15:56,680
Nogen der har et forslag?

975
01:15:56,680 --> 01:15:58,790
Hvor jeg skulle gøre dette eller hvordan jeg skal gøre dette?

976
01:15:58,790 --> 01:16:08,010
Vi har kun et par minutter, men nogen forslag?

977
01:16:08,010 --> 01:16:14,750
I stedet for - en måde, i stedet for vores betingelse er, medens,

978
01:16:14,750 --> 01:16:17,090
hvad vi i øjeblikket ser på, er ikke nul,

979
01:16:17,090 --> 01:16:22,340
i stedet vil vi fortsætte med at gå, indtil vores liste i sig selv er null.

980
01:16:22,340 --> 01:16:25,680
Så hvis vores liste ender med at blive null,

981
01:16:25,680 --> 01:16:30,680
så har vi løber tør for ting at kigge efter, for at søge over.

982
01:16:30,680 --> 01:16:39,860
Men det betyder, at den første ting på vores liste bare vil være den første knude.

983
01:16:39,860 --> 01:16:49,730
Den allerførste ting vil være - vi ikke længere behøver at se det.

984
01:16:49,730 --> 01:16:58,710
Så list-> n vil være vores træ.

985
01:16:58,710 --> 01:17:02,860
list-> næste bliver null.

986
01:17:02,860 --> 01:17:07,580
Og nu mens liste er ikke lig nul.

987
01:17:07,580 --> 01:17:11,610
Cur vil trække noget fra vores liste.

988
01:17:11,610 --> 01:17:13,500
Så cur vil lige liste-> n.

989
01:17:13,500 --> 01:17:20,850
Og så liste kommer til at lige liste-> n, eller liste-> næste.

990
01:17:20,850 --> 01:17:23,480
Så hvis cur værdi er lig værdi.

991
01:17:23,480 --> 01:17:28,790
Nu kan vi tilføje både vores højre pointer og vores venstre pointer

992
01:17:28,790 --> 01:17:32,900
så længe de ikke er null.

993
01:17:32,900 --> 01:17:36,390
Hernede, tror jeg, vi skulle have gjort det i første omgang.

994
01:17:36,390 --> 01:17:44,080
Hvis (aktu-> højre! = NULL)

995
01:17:44,080 --> 01:17:56,380
så vil vi indsætte denne knude i vores liste.

996
01:17:56,380 --> 01:17:59,290
Hvis (aktu-> venstre), dette er en lille smule ekstra arbejde, men det er fint.

997
01:17:59,290 --> 01:18:02,690
Hvis (aktu-> venstre! = NULL),

998
01:18:02,690 --> 01:18:14,310
og vi vil indsætte venstre ind i vores linkede liste,

999
01:18:14,310 --> 01:18:19,700
og det skal være det.

1000
01:18:19,700 --> 01:18:22,670
Vi gentage - så længe vi har noget i vores liste,

1001
01:18:22,670 --> 01:18:26,640
vi har en anden node at se på.

1002
01:18:26,640 --> 01:18:28,920
Så vi ser på det knudepunkt,

1003
01:18:28,920 --> 01:18:31,390
vi fremme vores liste til den næste.

1004
01:18:31,390 --> 01:18:34,060
Hvis dette knudepunkt er den værdi, vi leder efter, kan vi returnere sandt.

1005
01:18:34,060 --> 01:18:37,640
Else indsætte både vores venstre og højre undertræer,

1006
01:18:37,640 --> 01:18:40,510
så længe de ikke er null, ind i vores liste

1007
01:18:40,510 --> 01:18:43,120
således at vi uundgåeligt 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 vores rod pointer pegede på to ting,

1010
01:18:47,950 --> 01:18:51,670
så først vi trak noget ud, så vores liste ender med at være null.

1011
01:18:51,670 --> 01:18:56,890
Og så sætter vi to ting tilbage, så nu er vores liste er af størrelse 2.

1012
01:18:56,890 --> 01:19:00,030
Så vi kommer til at sløjfe tilbage op, og vi vil bare trække,

1013
01:19:00,030 --> 01:19:04,250
lad os sige, den venstre pointer af vores rod node.

1014
01:19:04,250 --> 01:19:07,730
Og det bliver bare holde sker, og vi ender looping over alting.

1015
01:19:07,730 --> 01:19:11,280
>> Bemærk, at dette var signifikant mere kompliceret

1016
01:19:11,280 --> 01:19:14,160
i den rekursive opløsning.

1017
01:19:14,160 --> 01:19:17,260
Og jeg har sagt flere gange

1018
01:19:17,260 --> 01:19:25,120
at den rekursive løsning normalt har meget til fælles med den iterative løsning.

1019
01:19:25,120 --> 01:19:30,820
Her er det præcis, hvad den rekursive løsning gør.

1020
01:19:30,820 --> 01:19:36,740
Den eneste ændring er, at i stedet for implicit at bruge stakken, programmet stakken,

1021
01:19:36,740 --> 01:19:40,840
som din måde at holde styr på, hvad emner, du stadig nødt til at besøge,

1022
01:19:40,840 --> 01:19:45,430
nu er du nødt til eksplicit bruge en sammenkædet liste.

1023
01:19:45,430 --> 01:19:49,070
I begge tilfælde er du holde styr på, hvad knude stadig mangler at blive besøgt.

1024
01:19:49,070 --> 01:19:51,790
I det rekursive tilfælde er det bare lettere, fordi en stak

1025
01:19:51,790 --> 01:19:57,100
er implementeret for dig som programmet stakken.

1026
01:19:57,100 --> 01:19:59,550
Bemærk, at dette er forbundet liste, er en stabel.

1027
01:19:59,550 --> 01:20:01,580
Uanset hvad vi lige har lagt på stakken

1028
01:20:01,580 --> 01:20:09,960
er det samme, hvad vi kommer til at trække ud stakken for at besøge næste.

1029
01:20:09,960 --> 01:20:14,380
Vi har ikke mere tid, men nogen spørgsmål?

1030
01:20:14,380 --> 01:20:23,530
[Studerende, uforståelig]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Så hvis vi har vores linkede liste,

1032
01:20:27,790 --> 01:20:30,150
strøm kommer til at pege på denne fyr,

1033
01:20:30,150 --> 01:20:34,690
og nu er vi bare uddybe vort linkede liste at fokusere på denne fyr.

1034
01:20:34,690 --> 01:20:44,200
Vi gennemkører over den linkede liste i denne linje.

1035
01:20:44,200 --> 01:20:51,200
Og så jeg tror vi skal frigøre vores linkede liste og kram

1036
01:20:51,200 --> 01:20:53,880
en gang før han vendte tilbage sandt eller falsk, er vi nødt til

1037
01:20:53,880 --> 01:20:57,360
gentage over vores linkede liste og altid hernede, tror jeg,

1038
01:20:57,360 --> 01:21:03,900
hvis vi cur ret er ikke lig med, tilføje det, så nu vil vi befri

1039
01:21:03,900 --> 01:21:09,600
cur fordi, ja, vi helt glemmer listen? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Så det er hvad vi ønsker at gøre her.

1041
01:21:12,880 --> 01:21:16,730
Hvor er den pointer?

1042
01:21:16,730 --> 01:21:23,320
Cur var dengang - vi vil en struct liste * 10 lig liste næste.

1043
01:21:23,320 --> 01:21:29,240
Free liste, list = temp.

1044
01:21:29,240 --> 01:21:32,820
Og i de tilfælde, hvor vi vender tilbage sandt, har vi brug for at gentage

1045
01:21:32,820 --> 01:21:37,050
over resten af ​​vores linkede liste befri ting.

1046
01:21:37,050 --> 01:21:39,700
Det gode ved den rekursive løsning er at frigive tingene

1047
01:21:39,700 --> 01:21:44,930
betyder blot, popping factorings fra stakken, som vil ske for dig.

1048
01:21:44,930 --> 01:21:50,720
Så vi er gået fra noget, der er ligesom 3 linjer er svære at tænke-om kode

1049
01:21:50,720 --> 01:21:57,520
til noget, der er betydeligt mange flere svære at tænke-om linjer kode.

1050
01:21:57,520 --> 01:22:00,620
Flere spørgsmå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]