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

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

3
00:00:05,090 --> 00:00:07,930
[Hierdie is CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Alles reg. So soos ek gesê het in my e-pos,

5
00:00:10,110 --> 00:00:14,060
dit gaan om 'n binêre-boom-intensiewe afdeling.

6
00:00:14,060 --> 00:00:16,820
Maar daar is nie so baie vrae.

7
00:00:16,820 --> 00:00:18,920
So ons gaan om te probeer en te trek uit elke vraag

8
00:00:18,920 --> 00:00:25,430
en gaan in pynlike detail van al die beste maniere om dinge te doen.

9
00:00:25,430 --> 00:00:31,200
So reg aan die begin, ons gaan deur monster tekeninge van binêre bome en stuff.

10
00:00:31,200 --> 00:00:35,970
So hier is, "Onthou dat 'n binêre boom nodes soortgelyk aan dié van 'n geskakelde lys,

11
00:00:35,970 --> 00:00:38,150
behalwe in plaas van een wyser is daar twee: een vir die linkerkant se kind "

12
00:00:38,150 --> 00:00:41,950
en een vir die reg om 'kind'. "

13
00:00:41,950 --> 00:00:45,630
So 'n binêre boom is net soos 'n geskakelde lys,

14
00:00:45,630 --> 00:00:47,910
behalwe die struct gaan twee wysers te hê.

15
00:00:47,910 --> 00:00:51,390
Daar is trinary bome, wat gaan drie verwysings na,

16
00:00:51,390 --> 00:00:56,540
daar is 'n N-êre bome, wat net 'n generiese wyser

17
00:00:56,540 --> 00:01:00,320
wat jy dan hoef te malloc groot genoeg wees om

18
00:01:00,320 --> 00:01:04,840
genoeg verwysings na al die moontlike kinders.

19
00:01:04,840 --> 00:01:08,200
So binêre boom gebeur net 'n konstante aantal van twee te hê.

20
00:01:08,200 --> 00:01:11,260
As jy wil, kan jy 'n geskakelde lys as 'n Unêre boom,

21
00:01:11,260 --> 00:01:15,360
maar ek dink nie enige iemand noem dit dat.

22
00:01:15,360 --> 00:01:18,060
"Teken 'n bokse en pyle diagram van 'n binêre boom node

23
00:01:18,060 --> 00:01:24,110
met Nate se gunsteling nommer, 7, waar elke kind pointer null. "

24
00:01:24,110 --> 00:01:27,780
So iPad af.

25
00:01:27,780 --> 00:01:30,280
>> Dit gaan redelik eenvoudig te wees.

26
00:01:30,280 --> 00:01:36,150
Ons het net gaan om 'n node te hê, sal ek dit teken as 'n vierkant.

27
00:01:36,150 --> 00:01:38,730
En ek sal teken die waardes hier.

28
00:01:38,730 --> 00:01:41,090
Sodat die waarde gaan in hier,

29
00:01:41,090 --> 00:01:44,770
en dan hier af sal ons die linker muis aan die linkerkant en die regte wyser aan die regterkant.

30
00:01:44,770 --> 00:01:50,430
En dit is baie so konvensie noem dit links en regs die wyser name.

31
00:01:50,430 --> 00:01:52,460
Beide van hierdie gaan wees null.

32
00:01:52,460 --> 00:01:57,870
Dit sal net null, en dit sal wees net null.

33
00:01:57,870 --> 00:02:03,630
Okay. So terug hier.

34
00:02:03,630 --> 00:02:05,700
"Met 'n geskakelde lys, ons het net 'n wyser te stoor

35
00:02:05,700 --> 00:02:09,639
na die eerste nodus in die lys om die hele geskakelde lys om te onthou, of die hele lys.

36
00:02:09,639 --> 00:02:11,650
Net so, met bome, ons het net 'n wyser te stoor

37
00:02:11,650 --> 00:02:13,420
aan 'n enkele nodus in om die hele boom om te onthou.

38
00:02:13,420 --> 00:02:15,980
Hierdie knoop is calle die "wortel" van die boom.

39
00:02:15,980 --> 00:02:18,320
Bou op jou diagram voor of teken 'n nuwe een

40
00:02:18,320 --> 00:02:21,690
van so 'n aard dat jy 'n blok-en-pyle uitbeelding van 'n binêre boom

41
00:02:21,690 --> 00:02:25,730
met die waarde 7, dan 3 in die linkerkant,

42
00:02:25,730 --> 00:02:32,760
dan 9 aan die regterkant, en dan 6 op die reg van die 3. "

43
00:02:32,760 --> 00:02:34,810
Kom ons kyk of ek kan onthou al wat in my kop.

44
00:02:34,810 --> 00:02:37,670
So dit gaan ons wortel hier te wees.

45
00:02:37,670 --> 00:02:41,600
Ons sal 'n wyser iewers, iets wat ons sal noem wortel,

46
00:02:41,600 --> 00:02:45,140
en dit is wat verwys na hierdie man.

47
00:02:45,140 --> 00:02:48,490
Nou 'n nuwe node te maak,

48
00:02:48,490 --> 00:02:52,870
Wat moet ons doen, 3 aan die linkerkant?

49
00:02:52,870 --> 00:02:57,140
So 'n nuwe nodus met 3, en dit wys aanvanklik null.

50
00:02:57,140 --> 00:02:59,190
Ek sal net sit N.

51
00:02:59,190 --> 00:03:02,250
Nou wil ons wat gaan aan die linkerkant van 7.

52
00:03:02,250 --> 00:03:06,840
Sodat ons verander die wyser nou verwys na hierdie man.

53
00:03:06,840 --> 00:03:12,420
En ons doen dieselfde. Ons wil 'n 9 hier

54
00:03:12,420 --> 00:03:14,620
wat sê aanvanklik net null.

55
00:03:14,620 --> 00:03:19,600
Ons gaan hierdie pointer, punt te verander na 9,

56
00:03:19,600 --> 00:03:23,310
en nou wil ons 6 te sit aan die regterkant van 3.

57
00:03:23,310 --> 00:03:32,170
So dit gaan - maak 'n 6.

58
00:03:32,170 --> 00:03:34,310
En dat die man daar sal wys.

59
00:03:34,310 --> 00:03:38,320
Okay. So dis al wat dit vra om te doen.

60
00:03:38,320 --> 00:03:42,770
>> Nou, laat ons gaan oor 'n paar terminologie.

61
00:03:42,770 --> 00:03:46,690
Ons het reeds gepraat oor hoe die wortel van die boom is die top-mees nodus in die boom.

62
00:03:46,690 --> 00:03:54,720
Die een wat 7. Die nodes aan die onderkant van die boom word genoem die blare.

63
00:03:54,720 --> 00:04:01,240
Enige node wat net null as sy kinders is 'n blaar.

64
00:04:01,240 --> 00:04:03,680
So dit is moontlik, as ons binêre boom is net 'n enkele nodus,

65
00:04:03,680 --> 00:04:10,130
dat 'n boom is 'n blaar, en dit is dit.

66
00:04:10,130 --> 00:04:12,060
"Die hoogte van die boom is die getal van hoep wat jy het om te maak

67
00:04:12,060 --> 00:04:16,620
van die top na 'n blaar te kry. "

68
00:04:16,620 --> 00:04:18,640
Ons kry in 'n tweede, die verskil

69
00:04:18,640 --> 00:04:21,940
tussen gebalanseerde en ongebalanseerde binêre bome,

70
00:04:21,940 --> 00:04:29,470
maar vir nou, die totale hoogte van hierdie boom

71
00:04:29,470 --> 00:04:34,520
Ek sou sê, is 3, maar as jy die getal van hoep

72
00:04:34,520 --> 00:04:39,710
wat jy moet maak in orde te kry tot 9, dan is dit eintlik net 'n hoogte van 2.

73
00:04:39,710 --> 00:04:43,340
Reg nou is dit 'n ongebalanseerde binêre boom,

74
00:04:43,340 --> 00:04:49,840
maar ons sal gepraat oor gebalanseer wanneer dit kry om relevant te wees.

75
00:04:49,840 --> 00:04:52,040
So nou kan ons praat oor nodes in 'n boom in terme

76
00:04:52,040 --> 00:04:54,700
relatief tot die ander nodes in die boom.

77
00:04:54,700 --> 00:04:59,730
So nou het ons ouers, kinders, broers en susters, voorouers en nageslag.

78
00:04:59,730 --> 00:05:05,650
Hulle is redelik gesonde verstand, wat dit beteken.

79
00:05:05,650 --> 00:05:09,610
As ons vra - se ouers.

80
00:05:09,610 --> 00:05:12,830
So, wat is die ouer van 3?

81
00:05:12,830 --> 00:05:16,090
[Studente] 7. >> Ja. Die ouer is net gaan om te wees wat aan jou wys.

82
00:05:16,090 --> 00:05:20,510
Dan wat is die kinders van 7?

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

84
00:05:23,860 --> 00:05:26,460
Let daarop dat "kinders" beteken letterlik kinders,

85
00:05:26,460 --> 00:05:31,010
so 6 sal nie van toepassing nie, want dit is soos 'n kleinkind.

86
00:05:31,010 --> 00:05:35,540
Maar dan as ons nageslag, so wat is die afstammelinge van 7?

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

88
00:05:37,500 --> 00:05:42,330
Die afstammelinge van die wortel node gaan word alles in die boom,

89
00:05:42,330 --> 00:05:47,950
behalwe miskien die wortel node self, as jy nie wil hê dat 'n afstammeling te oorweeg.

90
00:05:47,950 --> 00:05:50,750
En laastens, voorouers, so dit is die teenoorgestelde rigting.

91
00:05:50,750 --> 00:05:55,740
So, wat is die voorouers van 6?

92
00:05:55,740 --> 00:05:58,920
[Studente] 3 en 7. >> Ja. 9 is nie ingesluit nie.

93
00:05:58,920 --> 00:06:02,520
Dis net die direkte linie terug na die wortel

94
00:06:02,520 --> 00:06:13,230
gaan julle voorvaders te wees.

95
00:06:13,230 --> 00:06:16,300
>> "Ons sê dat 'n binêre boom is" beveel "as vir elke nodus in die boom,

96
00:06:16,300 --> 00:06:19,530
al sy afstammelinge aan die linkerkant mindere waardes

97
00:06:19,530 --> 00:06:22,890
en al van die kinders aan die regterkant het 'n groter waardes.

98
00:06:22,890 --> 00:06:27,060
Byvoorbeeld, is die boom hierbo bestel maar dit is nie die enigste moontlike bestel reëling. "

99
00:06:27,060 --> 00:06:30,180
Voordat ons dat,

100
00:06:30,180 --> 00:06:36,420
'n geordende binêre boom is ook bekend as 'n binêre soekboom.

101
00:06:36,420 --> 00:06:38,660
Hier is ons gebeur noem dit 'n geordende binêre boom,

102
00:06:38,660 --> 00:06:41,850
maar ek het dit nog nooit gehoor het 'n geordende binêre boom voor,

103
00:06:41,850 --> 00:06:46,650
en op 'n quiz ons is baie meer geneig binêre soekboom te sit.

104
00:06:46,650 --> 00:06:49,250
Hulle is een en dieselfde,

105
00:06:49,250 --> 00:06:54,580
en dit is belangrik dat jy erken die onderskeid tussen binêre boom en binêre soekboom.

106
00:06:54,580 --> 00:06:58,830
'N binêre boom is net 'n boom wat aan twee dinge.

107
00:06:58,830 --> 00:07:02,120
Elke node wys twee dinge.

108
00:07:02,120 --> 00:07:06,310
Daar is geen redenasie oor die waardes wat dit dui op.

109
00:07:06,310 --> 00:07:11,370
Dus, net soos hier, want dit is 'n binêre soekboom,

110
00:07:11,370 --> 00:07:14,030
ons weet dat as ons gaan links van 7,

111
00:07:14,030 --> 00:07:16,670
dan al die waardes wat ons kan bereik

112
00:07:16,670 --> 00:07:19,310
deur te gaan links van 7 tot minder as 7.

113
00:07:19,310 --> 00:07:24,070
Let op dat al die waardes van minder as 7 is 3 en 6.

114
00:07:24,070 --> 00:07:26,040
Dit is alles aan die linkerkant van 7.

115
00:07:26,040 --> 00:07:29,020
As ons na die reg van 7, alles het meer as 7,

116
00:07:29,020 --> 00:07:33,220
so 9 is aan die reg van 7, so ons is goed.

117
00:07:33,220 --> 00:07:36,150
Dit is nie die geval vir 'n binêre boom,

118
00:07:36,150 --> 00:07:40,020
vir 'n gereelde binêre boom kan net 3 aan die bokant, 7 aan die linkerkant,

119
00:07:40,020 --> 00:07:47,630
9 aan die linkerkant van 7, is daar geen ordening van waardes hoegenaamd.

120
00:07:47,630 --> 00:07:56,140
Nou, sal ons nie eintlik dit doen, want dit is 'n vervelige en onnodige,

121
00:07:56,140 --> 00:07:59,400
maar probeer om soveel bestel bome te trek as wat jy kan dink

122
00:07:59,400 --> 00:08:01,900
deur gebruik te maak van die nommers 7, 3, 9, en 6.

123
00:08:01,900 --> 00:08:06,800
Hoeveel duidelike reëlings is daar? Wat is die hoogte van elke een? "

124
00:08:06,800 --> 00:08:10,480
>> Ons sal 'n paar doen nie, maar die hoofgedagte is,

125
00:08:10,480 --> 00:08:16,530
Dit is in geen manier om 'n unieke voorstelling van 'n binêre boom met hierdie waardes.

126
00:08:16,530 --> 00:08:22,760
Al wat ons nodig het, is sommige binêre boom wat met 7, 3, 6, en 9.

127
00:08:22,760 --> 00:08:25,960
Nog 'n moontlike geldige een sou wees die wortel 3,

128
00:08:25,960 --> 00:08:30,260
gaan aan die linkerkant, en dit is 6, gaan aan die linkerkant, en dit is 7,

129
00:08:30,260 --> 00:08:32,730
gaan na die linker-en dit is 9.

130
00:08:32,730 --> 00:08:36,169
Dit is 'n perfek geldige binêre soekboom.

131
00:08:36,169 --> 00:08:39,570
Dit is nie baie nuttig, want dit is net soos 'n geskakelde lys

132
00:08:39,570 --> 00:08:43,750
en al van hierdie wenke is net null.

133
00:08:43,750 --> 00:08:48,900
Maar dit is 'n geldige boom. Ja?

134
00:08:48,900 --> 00:08:51,310
[Studente] nie die waardes groter wees aan die regterkant?

135
00:08:51,310 --> 00:08:56,700
Of is dit? >> Hierdie ek bedoel die ander manier om te gaan.

136
00:08:56,700 --> 00:09:00,960
Daar is ook - ja, laat se skakelaar wat.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Goeie vangs.

138
00:09:07,770 --> 00:09:11,730
Dit het nog steeds om gehoorsaam te wees aan wat 'n binêre boom soek veronderstel is om te doen.

139
00:09:11,730 --> 00:09:15,650
So alles aan die linkerkant het minder wees as enige gegewe node.

140
00:09:15,650 --> 00:09:23,180
Ons kan net beweeg, sê, hierdie 6 en sit dit hier.

141
00:09:23,180 --> 00:09:26,880
Nee, ons kan nie. Hoekom hou ek om dit te doen?

142
00:09:26,880 --> 00:09:35,350
Kom ons doen - hier is 6, 7, 6 punte tot 3.

143
00:09:35,350 --> 00:09:39,290
Dit is nog steeds 'n geldige binêre soekboom.

144
00:09:39,290 --> 00:09:49,260
Wat is verkeerd as ek - laat ons sien of ek kan kom met 'n reëling.

145
00:09:49,260 --> 00:09:52,280
Ja, okay. So, wat is verkeerd met hierdie boom?

146
00:09:52,280 --> 00:10:08,920
Ek dink ek het reeds aan julle gegee het 'n wenk dat daar is iets fout met dit.

147
00:10:08,920 --> 00:10:14,430
Hoekom hou ek om dit te doen?

148
00:10:14,430 --> 00:10:18,510
Okay. Dit lyk redelik.

149
00:10:18,510 --> 00:10:22,590
As ons kyk by elke node, soos 7, dan na die linkerkant van 7 is 'n 3.

150
00:10:22,590 --> 00:10:24,960
So ons het 3, die ding aan die regterkant van 3 is 'n 6.

151
00:10:24,960 --> 00:10:27,750
En as jy kyk die ding aan die regterkant van die 6 op 6, is 'n 9.

152
00:10:27,750 --> 00:10:30,910
So hoekom is dit nie 'n geldige binêre soekboom?

153
00:10:30,910 --> 00:10:36,330
[Studente] 9 is nog steeds aan die linkerkant van 7. >> Ja.

154
00:10:36,330 --> 00:10:43,710
Dit moet waar wees dat alle waardes wat jy kan bereik deur te gaan na die linkerkant van 7 is minder as 7.

155
00:10:43,710 --> 00:10:49,120
As ons gaan links van 7, kry ons 3 en ons kan nog steeds tot 6,

156
00:10:49,120 --> 00:10:52,520
kan ons nog steeds tot 9, maar deur hulle het gegaan en minder as 7,

157
00:10:52,520 --> 00:10:55,070
moet ons nie in staat wees om te kry om 'n getal wat groter as 7.

158
00:10:55,070 --> 00:10:59,830
Dit is dus nie 'n geldige binêre soekboom.

159
00:10:59,830 --> 00:11:02,330
>> My broer eintlik het 'n onderhoud vraag

160
00:11:02,330 --> 00:11:07,760
dit was basies net kode up iets te valideer

161
00:11:07,760 --> 00:11:10,500
of 'n boom is 'n binêre soekboom,

162
00:11:10,500 --> 00:11:13,580
en so die eerste ding wat hy gedoen het was net kyk om te sien

163
00:11:13,580 --> 00:11:17,020
indien die linker en regter korrek is, en dan itereer daar.

164
00:11:17,020 --> 00:11:19,700
Maar jy kan nie net doen wat, jy het om tred te hou

165
00:11:19,700 --> 00:11:22,550
van die feit dat dit nou dat ek weg is links van 7,

166
00:11:22,550 --> 00:11:26,340
moet alles in hierdie boomstruktuur inskuif nie minder as 7.

167
00:11:26,340 --> 00:11:28,430
Die korrekte algoritme nodig het om tred te hou

168
00:11:28,430 --> 00:11:35,970
van die grense wat die waardes moontlik kan val.

169
00:11:35,970 --> 00:11:38,360
Ons sal nie deur almal van hulle.

170
00:11:38,360 --> 00:11:41,630
Daar is 'n mooi herhaling Betrokkenheid,

171
00:11:41,630 --> 00:11:44,810
alhoewel ons nog nie gekry het aan diegene, of sal ons nie vir diegene,

172
00:11:44,810 --> 00:11:47,030
definieer hoeveel daar werklik is.

173
00:11:47,030 --> 00:11:53,180
So daar is 14 van hulle.

174
00:11:53,180 --> 00:11:56,020
Die idee van hoe jy dit sou doen is wiskundig soos,

175
00:11:56,020 --> 00:11:59,770
jy kan enige een kies aan die wortel node wees,

176
00:11:59,770 --> 00:12:03,160
en dan as ek pluk 7 aan die wortel node wees,

177
00:12:03,160 --> 00:12:08,150
dan is daar, sê, 'n paar nommers wat kan gaan my linker node,

178
00:12:08,150 --> 00:12:10,440
en daar is 'n paar nommers wat kan my regter node,

179
00:12:10,440 --> 00:12:15,090
maar as ek n totaal getalle, dan is die bedrag wat aan die linkerkant kan gaan

180
00:12:15,090 --> 00:12:18,820
plus die bedrag wat gaan aan die regterkant N - 1.

181
00:12:18,820 --> 00:12:26,130
So van die oorblywende getalle, moet hulle in staat wees om te gaan na die linker-of die regterkant.

182
00:12:26,130 --> 00:12:31,580
Dit lyk moeilik dat, as ek 3 eerste dan alles het om te gaan na die linkerkant,

183
00:12:31,580 --> 00:12:35,080
maar as ek 7, dan 'n paar dinge kan gaan die linker en 'n paar dinge kan gaan aan die regterkant.

184
00:12:35,080 --> 00:12:39,570
En deur die '3 eerste "ek bedoel alles kan gaan aan die regterkant.

185
00:12:39,570 --> 00:12:42,350
Dit is regtig, jy hoef net te dink oor dit,

186
00:12:42,350 --> 00:12:47,980
hoe baie dinge kan gaan op die volgende vlak van die boom.

187
00:12:47,980 --> 00:12:50,420
En dit kom te wees 14, of jy kan trek almal van hulle,

188
00:12:50,420 --> 00:12:54,650
en dan sal jy kry 14.

189
00:12:54,650 --> 00:13:01,120
>> Gaan terug hier,

190
00:13:01,120 --> 00:13:03,510
"Gelas binêre bome is cool omdat ons deur hulle kan soek

191
00:13:03,510 --> 00:13:06,910
in 'n soortgelyke manier om oor 'n gesorteerde skikking te soek.

192
00:13:06,910 --> 00:13:10,120
Om dit te doen, het ons begin by die wortel en werk ons ​​pad die boom af

193
00:13:10,120 --> 00:13:13,440
teenoor blare, die nagaan van elke node se waardes teen die waardes wat ons op soek is na.

194
00:13:13,440 --> 00:13:15,810
As die huidige node se waarde is minder as die waarde wat ons soek,

195
00:13:15,810 --> 00:13:18,050
jy gaan langs die node se reg kind.

196
00:13:18,050 --> 00:13:20,030
Anders gaan jy na die node se linker kind.

197
00:13:20,030 --> 00:13:22,800
Op 'n sekere punt, sal jy óf die waarde wat jy op soek is na, of jy loop in 'n null,

198
00:13:22,800 --> 00:13:28,520
wat die waarde is nie in die boom. "

199
00:13:28,520 --> 00:13:32,450
Ek het die boom wat ons gehad het voordat te teken, wat sal 'n tweede.

200
00:13:32,450 --> 00:13:38,280
Maar ons wil om te kyk of 6, 10 en 1 in die boom.

201
00:13:38,280 --> 00:13:49,180
So wat dit was, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
Die nommers wat jy wil om te kyk, ons wil om te kyk 6.

203
00:13:52,730 --> 00:13:55,440
Hoe werk hierdie algoritme werk?

204
00:13:55,440 --> 00:14:03,040
Wel, ons het ook 'n paar wortel wyser na ons boom.

205
00:14:03,040 --> 00:14:12,460
En ons sal gaan na die wortel en sê, is hierdie waarde gelyk is aan die waarde wat ons op soek is na?

206
00:14:12,460 --> 00:14:15,000
So ons is op soek na 6, so dit is nie gelyk nie.

207
00:14:15,000 --> 00:14:20,140
So hou ons gaan, en nou is ons sê, okay, so 6 is minder as 7.

208
00:14:20,140 --> 00:14:23,940
Beteken dit dat ons wil om te gaan na die linkerkant, of wil ons gaan aan die regterkant?

209
00:14:23,940 --> 00:14:27,340
[Studente] links. >> Ja.

210
00:14:27,340 --> 00:14:33,340
Dit is aansienlik makliker, is al wat jy hoef te doen, trek een moontlike node van die boom

211
00:14:33,340 --> 00:14:37,760
en dan moet jy moenie - in plaas van probeer om te dink in jou kop,

212
00:14:37,760 --> 00:14:40,020
okay, as dit is minder, gaan ek aan die linkerkant of die regterkant,

213
00:14:40,020 --> 00:14:43,030
net te kyk na hierdie foto, dit is baie duidelik dat ek het om te gaan aan die linkerkant

214
00:14:43,030 --> 00:14:47,700
indien hierdie node is groter as die waarde wat ek soek.

215
00:14:47,700 --> 00:14:52,600
So gaan jy na links, nou is ek op 3.

216
00:14:52,600 --> 00:14:57,770
Ek wil - 3 is minder as die waarde wat ek soek, wat is 6.

217
00:14:57,770 --> 00:15:03,420
So gaan ons aan die regterkant, en nou het ek uiteindelik op 6,

218
00:15:03,420 --> 00:15:07,380
wat is die waarde wat ek soek, sodat ek terugkeer ware.

219
00:15:07,380 --> 00:15:15,760
Die volgende waarde wat ek gaan om te kyk vir is 10.

220
00:15:15,760 --> 00:15:23,230
Okay. So 10, nou is, gaan - uitroei dat - gaan om die wortel te volg.

221
00:15:23,230 --> 00:15:27,670
Nou, is 10 gaan wees meer as 7, so ek wil om te kyk na die regterkant.

222
00:15:27,670 --> 00:15:31,660
Ek gaan om hier te kom, 10 gaan wees groter as 9,

223
00:15:31,660 --> 00:15:34,520
so ek gaan om te wil om te kyk na die reg.

224
00:15:34,520 --> 00:15:42,100
Ek kom hier, maar hier nou is ek by null.

225
00:15:42,100 --> 00:15:44,170
Wat doen ek as ek getref null?

226
00:15:44,170 --> 00:15:47,440
[Studente] Terug vals? >> Ja. Ek het dit nie vind 10.

227
00:15:47,440 --> 00:15:49,800
1 gaan na 'n byna identiese geval te wees,

228
00:15:49,800 --> 00:15:51,950
behalwe dit is net gaan word omgekeer, in plaas van op soek

229
00:15:51,950 --> 00:15:56,540
die regte kant af, ek gaan om te kyk af aan die linkerkant.

230
00:15:56,540 --> 00:16:00,430
>> Nou dink ek ons ​​eintlik kry die kode.

231
00:16:00,430 --> 00:16:04,070
Hier is waar - die CS50 toestel oopmaak en opgevolg jou pad daar,

232
00:16:04,070 --> 00:16:07,010
maar jy kan ook net dit doen in die ruimte.

233
00:16:07,010 --> 00:16:09,170
Dit is waarskynlik ideaal om dit te doen in die ruimte,

234
00:16:09,170 --> 00:16:13,760
want ons kan werk in die ruimte.

235
00:16:13,760 --> 00:16:19,170
"Eers moet ons sal moet 'n nuwe soort definisie vir 'n binêre boom node bevat int waardes.

236
00:16:19,170 --> 00:16:21,400
Met behulp van die boiler typedef hieronder,

237
00:16:21,400 --> 00:16:24,510
die skep van 'n nuwe soort definisie vir 'n nodus in 'n binêre boom.

238
00:16:24,510 --> 00:16:27,930
As jy vashaak. . . "Blah, blah, blah. Okay.

239
00:16:27,930 --> 00:16:30,380
So laat ons die boiler hier,

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

241
00:16:41,630 --> 00:16:44,270
So, wat is die velde wat ons gaan in ons node wil?

242
00:16:44,270 --> 00:16:46,520
[Studente] Int en dan twee wysers?

243
00:16:46,520 --> 00:16:49,700
>> Int waarde, twee wysers? Hoe skryf ek die verwysings?

244
00:16:49,700 --> 00:16:58,440
[Studente] struct. >> Ek moet zoom. Ja, so struct node * links,

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

246
00:17:01,320 --> 00:17:03,460
En onthou die bespreking van die laaste tyd,

247
00:17:03,460 --> 00:17:15,290
dat dit maak nie sin nie, dit maak nie sin nie,

248
00:17:15,290 --> 00:17:18,270
dit maak nie sin nie.

249
00:17:18,270 --> 00:17:25,000
Jy moet alles wat daar in om hierdie rekursiewe struct te definieer.

250
00:17:25,000 --> 00:17:27,970
Okay, so dit is wat ons boom gaan lyk.

251
00:17:27,970 --> 00:17:37,670
As ons het 'n trinary boom, dan kan 'n nodus lyk B1, B2, struct node * b3,

252
00:17:37,670 --> 00:17:43,470
waar b 'n tak - eintlik, het meer ek dit hoor links, middel, regs, maar alles.

253
00:17:43,470 --> 00:17:55,610
Ons het net oor binêre, regs, links.

254
00:17:55,610 --> 00:17:59,110
"Nou is 'n globale node * veranderlike verklaar vir die wortel van die boom."

255
00:17:59,110 --> 00:18:01,510
So ons is nie van plan om dit te doen.

256
00:18:01,510 --> 00:18:08,950
Ten einde te maak dinge 'n bietjie meer moeilik en meer algemene,

257
00:18:08,950 --> 00:18:11,570
sal ons nie 'n globale node veranderlike.

258
00:18:11,570 --> 00:18:16,710
In plaas daarvan, in die hoof sal ons al ons node dinge verklaar,

259
00:18:16,710 --> 00:18:20,500
en dit beteken dat hieronder, wanneer ons begin loop

260
00:18:20,500 --> 00:18:23,130
ons bevat funksie en ons insert funksie,

261
00:18:23,130 --> 00:18:27,410
in plaas van ons bevat funksioneer net die gebruik van hierdie globale node veranderlike,

262
00:18:27,410 --> 00:18:34,280
gaan ons dit as 'n argument om die boom wat ons wil hê om dit te verwerk.

263
00:18:34,280 --> 00:18:36,650
Met die globale veranderlike is veronderstel om dinge makliker te maak.

264
00:18:36,650 --> 00:18:42,310
Ons gaan maak dinge moeiliker.

265
00:18:42,310 --> 00:18:51,210
Nou neem 'n minuut of so om net te doen hierdie soort van ding,

266
00:18:51,210 --> 00:18:57,690
waar binnekant van die belangrikste wat jy wil om hierdie boom te skep, en dit is al wat jy wil doen.

267
00:18:57,690 --> 00:19:04,530
Probeer en konstrueer hierdie boom in jou hooffunksie.

268
00:19:42,760 --> 00:19:47,610
>> Okay. So jy hoef nie eens die boom gebou het nog die hele manier.

269
00:19:47,610 --> 00:19:49,840
Maar iemand het iets wat ek kan trek

270
00:19:49,840 --> 00:20:03,130
om aan te toon hoe 'n mens kan begin die bou van so 'n boom?

271
00:20:03,130 --> 00:20:08,080
[Studente] Iemand se gebons, probeer om uit te kry.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Enigeen gemaklik met hul boom konstruksie?

273
00:20:13,100 --> 00:20:15,520
[Studente] Sure. Dit is nie gedoen nie. >> Dit is fyn. Ons kan net klaar -

274
00:20:15,520 --> 00:20:26,860
oh, kan jy dit stoor? Hoera.

275
00:20:26,860 --> 00:20:32,020
So hier is ons het - oh, ek is effens sny af.

276
00:20:32,020 --> 00:20:34,770
Ek vergrote?

277
00:20:34,770 --> 00:20:37,730
Zoom in, blaai. >> Ek het 'n vraag. >> Ja?

278
00:20:37,730 --> 00:20:44,410
[Studente] Wanneer jy definieer struct, is dinge soos geïnisialiseer aan enigiets?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Goed. So jy wil hê om te inisialiseer -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nr Wanneer jy definieer, of wanneer jy verklaar struct

281
00:20:50,450 --> 00:20:55,600
dit is nie geïnisialiseer nie by verstek; dit is net soos as jy 'n int verklaar.

282
00:20:55,600 --> 00:20:59,020
Dit is presies dieselfde ding. Dit is soos elkeen van sy individuele velde

283
00:20:59,020 --> 00:21:04,460
kan 'n gemors waarde in dit. >> En is dit moontlik om te definieer of te verklaar struct

284
00:21:04,460 --> 00:21:07,740
hulle in 'n manier dat dit nie inisialiseer?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ja. So, kortpad inisialisering sintaksis

286
00:21:13,200 --> 00:21:18,660
gaan lyk -

287
00:21:18,660 --> 00:21:22,200
Daar is twee maniere waarop ons dit kan doen. Ek dink ons ​​moet dit stel

288
00:21:22,200 --> 00:21:25,840
om seker te maak dat kletteren doen dit ook.

289
00:21:25,840 --> 00:21:28,510
Die volgorde van die argumente wat kom in die struct,

290
00:21:28,510 --> 00:21:32,170
jy sit as die volgorde van argumente binnekant van hierdie kode tussen krulhakies.

291
00:21:32,170 --> 00:21:35,690
So as jy wil om dit te inisialiseer tot 9 en links van nul en dan null,

292
00:21:35,690 --> 00:21:41,570
dit sou wees 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Die alternatief is, en die redakteur nie graag hierdie sintaksis,

294
00:21:47,890 --> 00:21:50,300
en dit dink ek wil 'n nuwe blok,

295
00:21:50,300 --> 00:22:01,800
maar die alternatief is iets soos -

296
00:22:01,800 --> 00:22:04,190
hier, ek sit dit op 'n nuwe reël.

297
00:22:04,190 --> 00:22:09,140
Kan jy uitdruklik sê, ek vergeet die presiese sintaksis.

298
00:22:09,140 --> 00:22:13,110
So kan jy uitdruklik spreek hulle by die naam, en sê:

299
00:22:13,110 --> 00:22:21,570
C, of ​​waarde. = 9, links = NULL.

300
00:22:21,570 --> 00:22:24,540
Ek vermoed hierdie behoefte te wees kommas.

301
00:22:24,540 --> 00:22:29,110
Regs = NULL, so hierdie manier waarop jy dit nie doen nie

302
00:22:29,110 --> 00:22:33,780
werklik nodig het om te weet van die orde van die struct,

303
00:22:33,780 --> 00:22:36,650
en wanneer jy dit te lees, dit is baie meer eksplisiet

304
00:22:36,650 --> 00:22:41,920
oor wat die waarde is geïnisialiseer.

305
00:22:41,920 --> 00:22:44,080
>> Dit gebeur om te wees een van die dinge wat -

306
00:22:44,080 --> 00:22:49,100
Dus, vir die grootste deel, C + + is 'n superstel van C.

307
00:22:49,100 --> 00:22:54,160
Jy kan C-kode, beweeg dit oor C + +, en dit moet stel.

308
00:22:54,160 --> 00:22:59,570
Dit is een van die dinge wat C + + ondersteun nie, sodat mense is geneig om dit nie te doen nie.

309
00:22:59,570 --> 00:23:01,850
Ek weet nie of dit is die enigste rede waarom mense is geneig om dit nie te doen nie,

310
00:23:01,850 --> 00:23:10,540
maar die geval waar ek nodig het om dit te gebruik wat nodig is om te werk met C + + en so ek kon nie gebruik van hierdie.

311
00:23:10,540 --> 00:23:14,000
Nog 'n voorbeeld van iets wat nie werk nie met C + + is

312
00:23:14,000 --> 00:23:16,940
hoe malloc terug 'n "void *," tegnies,

313
00:23:16,940 --> 00:23:20,200
maar jy kan net sê char * x = malloc wat ook al,

314
00:23:20,200 --> 00:23:22,840
en dit sal outomaties gewerp te word 'n char *.

315
00:23:22,840 --> 00:23:25,450
Dat outomatiese cast gebeur nie in C + +.

316
00:23:25,450 --> 00:23:28,150
Dit sou nie saamstel, en jy sal uitdruklik nodig om te sê

317
00:23:28,150 --> 00:23:34,510
char *, malloc, wat ook al, om dit te gooi na 'n char *.

318
00:23:34,510 --> 00:23:37,270
Daar is baie dinge dat C en C + + nie eens op nie,

319
00:23:37,270 --> 00:23:40,620
maar dit is twee.

320
00:23:40,620 --> 00:23:43,120
So ons gaan met hierdie sintaksis.

321
00:23:43,120 --> 00:23:46,150
Maar selfs as ons nie gaan met daardie sintaksis,

322
00:23:46,150 --> 00:23:49,470
wat kan fout wees met hierdie?

323
00:23:49,470 --> 00:23:52,170
[Studente] Ek hoef nie te dereference dit? >> Ja.

324
00:23:52,170 --> 00:23:55,110
Onthou dat die pyl het 'n implisiete dereference,

325
00:23:55,110 --> 00:23:58,230
en so wanneer ons net die hantering van 'n struct,

326
00:23:58,230 --> 00:24:04,300
ons wil gebruik. te kry op 'n veld binnekant van die struct.

327
00:24:04,300 --> 00:24:07,200
En die enigste keer wat ons gebruik pyltjie wanneer ons wil doen -

328
00:24:07,200 --> 00:24:13,450
goed, arrow is gelykstaande aan -

329
00:24:13,450 --> 00:24:17,020
dit is wat dit sou beteken het as wat ek gebruik pyl.

330
00:24:17,020 --> 00:24:24,600
Alle arrow middel dereference hierdie, nou is ek op 'n struct, en ek kan die veld kry.

331
00:24:24,600 --> 00:24:28,040
Óf die veld kry direk of dereference en kry die veld -

332
00:24:28,040 --> 00:24:30,380
Ek dink hierdie waarde moet wees.

333
00:24:30,380 --> 00:24:33,910
Maar hier is ek doen met net 'n struct, nie 'n wyser na 'n struct,

334
00:24:33,910 --> 00:24:38,780
en daarom kan ek nie gebruik maak van die pyl.

335
00:24:38,780 --> 00:24:47,510
Maar hierdie soort van ding wat ons kan doen vir al die nodes.

336
00:24:47,510 --> 00:24:55,790
Oh my God.

337
00:24:55,790 --> 00:25:09,540
Dit is 6, 7 en 3.

338
00:25:09,540 --> 00:25:16,470
Dan kan ons die opstel van die takke in ons boom, kan ons 7 -

339
00:25:16,470 --> 00:25:21,650
ons kan die linkerkant het, moet wys tot 3.

340
00:25:21,650 --> 00:25:25,130
So, hoe doen ons dit?

341
00:25:25,130 --> 00:25:29,320
[Studente, onverstaanbare] >> Ja. Die adres van node3,

342
00:25:29,320 --> 00:25:34,170
en as jy nie het adres, dan is dit sou net nie saam te stel.

343
00:25:34,170 --> 00:25:38,190
Maar onthou dat hierdie verwysings na die volgende nodes.

344
00:25:38,190 --> 00:25:44,930
Die reg behoort te wys 9,

345
00:25:44,930 --> 00:25:53,330
en 3 moet wys op die reg tot 6.

346
00:25:53,330 --> 00:25:58,480
Ek dink dit is al te stel. Enige vrae of kommentaar?

347
00:25:58,480 --> 00:26:02,060
[Student, onverstaanbaar] Die wortel gaan wees 7.

348
00:26:02,060 --> 00:26:08,210
Ons kan net sê node * ptr =

349
00:26:08,210 --> 00:26:14,160
of wortel, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Vir ons doeleindes, ons gaan om te word wat met insert,

351
00:26:20,730 --> 00:26:25,490
so ons gaan om te wil om te skryf van 'n funksie te voeg in hierdie binêre boom

352
00:26:25,490 --> 00:26:34,230
en voeg is onvermydelik gaan malloc te roep om 'n nuwe node vir hierdie boom te skep.

353
00:26:34,230 --> 00:26:36,590
So dinge gaan kry 'n slag met die feit dat 'n paar nodes

354
00:26:36,590 --> 00:26:38,590
is tans op die stapel

355
00:26:38,590 --> 00:26:43,680
en ander nodes gaan eindig op die hoop wanneer ons dit plaas.

356
00:26:43,680 --> 00:26:47,640
Dit is heeltemal geldig, maar die enigste rede

357
00:26:47,640 --> 00:26:49,600
ons is in staat om dit te doen op die stapel

358
00:26:49,600 --> 00:26:51,840
is omdat dit so 'n slinks voorbeeld wat ons ken

359
00:26:51,840 --> 00:26:56,360
die boom veronderstel is om te word gebou as 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
As ons dit nie het nie, dan sou ons nie 'malloc in die eerste plek.

361
00:27:02,970 --> 00:27:06,160
Soos ons sal 'n bietjie later sien, moet ons malloc'ing word.

362
00:27:06,160 --> 00:27:08,570
Nou is dit heel redelik op die stapel te plaas,

363
00:27:08,570 --> 00:27:14,750
maar laat ons dit verander na 'n malloc implementering.

364
00:27:14,750 --> 00:27:17,160
So elkeen van hierdie gaan nou iets soos

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

366
00:27:24,240 --> 00:27:28,040
En nou gaan ons ons check te doen.

367
00:27:28,040 --> 00:27:34,010
if (node9 == null) - ek wou nie hê dat -

368
00:27:34,010 --> 00:27:40,950
terug 1, en dan kan ons doen node9-> want nou is dit 'n wyser,

369
00:27:40,950 --> 00:27:45,300
waarde = 6, node9-> links = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> regs = NULL,

371
00:27:48,930 --> 00:27:51,410
en ons gaan te hê om dit te doen vir elk van dié nodes.

372
00:27:51,410 --> 00:27:57,490
So in plaas daarvan, laat ons dit binnekant van 'n aparte funksie.

373
00:27:57,490 --> 00:28:00,620
Kom ons noem dit node * build_node,

374
00:28:00,620 --> 00:28:09,050
en dit is ietwat soortgelyk aan die API's bied ons vir Huffman kodering.

375
00:28:09,050 --> 00:28:12,730
Ons gee jy initializer funksies vir 'n boom

376
00:28:12,730 --> 00:28:20,520
en deconstructor "funksies" vir die bome en die dieselfde vir woude.

377
00:28:20,520 --> 00:28:22,570
>> So hier gaan ons 'n initializer funksie te hê

378
00:28:22,570 --> 00:28:25,170
om net die bou van 'n node vir ons.

379
00:28:25,170 --> 00:28:29,320
En dit gaan pretty much lyk presies soos hierdie.

380
00:28:29,320 --> 00:28:32,230
En ek gaan selfs om lui te wees en nie verander nie die naam van die veranderlike,

381
00:28:32,230 --> 00:28:34,380
selfs al node9 maak geen sin nie.

382
00:28:34,380 --> 00:28:38,610
O, ek dink node9 se waarde moet nie gewees het 6.

383
00:28:38,610 --> 00:28:42,800
Nou kan ons terugkeer node9.

384
00:28:42,800 --> 00:28:49,550
En hier moet ons terugkeer null.

385
00:28:49,550 --> 00:28:52,690
Almal saam op dat die Build-a-node funksie?

386
00:28:52,690 --> 00:28:59,780
So ons kan nou net noem dat enige node met 'n gegewe waarde en null pointers te bou.

387
00:28:59,780 --> 00:29:09,750
Nou het ons dit kan noem, kan ons node * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
En laat ons dit doen. . .

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

390
00:29:33,980 --> 00:29:39,330
En nou wil ons die opstel van die dieselfde pointers,

391
00:29:39,330 --> 00:29:42,470
behalwe nou alles is reeds in terme van verwysings

392
00:29:42,470 --> 00:29:48,480
so hoef nie meer die adres van.

393
00:29:48,480 --> 00:29:56,300
Okay. So, wat is die laaste ding wat ek wil doen?

394
00:29:56,300 --> 00:30:03,850
Daar is 'n fout kontrole dat ek nie doen nie.

395
00:30:03,850 --> 00:30:06,800
Wat beteken node terugkeer bou?

396
00:30:06,800 --> 00:30:11,660
[Student, onverstaanbaar] >> Ja. As malloc het misluk, sal dit terugkeer null.

397
00:30:11,660 --> 00:30:16,460
So ek gaan te lui sit dit neer hier in plaas van die doen van 'n voorwaarde vir elkeen.

398
00:30:16,460 --> 00:30:22,320
As (node9 == NULL, of - selfs eenvoudiger,

399
00:30:22,320 --> 00:30:28,020
dit is gelykstaande aan net indien nie node9.

400
00:30:28,020 --> 00:30:38,310
So indien nie node9, of nie node6, of nie node3, of nie node7, terug 1.

401
00:30:38,310 --> 00:30:42,850
Miskien moet ons druk malloc het misluk, of iets.

402
00:30:42,850 --> 00:30:46,680
[Studente] vals is gelyk aan sowel nul?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Enige nul waarde is vals.

404
00:30:51,290 --> 00:30:53,920
So null is 'n nul waarde.

405
00:30:53,920 --> 00:30:56,780
Zero is 'n nul waarde. Vals is 'n nul waarde.

406
00:30:56,780 --> 00:31:02,130
Enige - pretty much die enigste 2 nul waardes is van nul en nul,

407
00:31:02,130 --> 00:31:07,900
vals is net hash gedefinieer as nul.

408
00:31:07,900 --> 00:31:13,030
Dit geld ook as ons globale veranderlike verklaar.

409
00:31:13,030 --> 00:31:17,890
As ons node * wortel het tot hier,

410
00:31:17,890 --> 00:31:24,150
dan - die nice ding oor globale veranderlikes is dat hulle altyd 'n aanvanklike waarde.

411
00:31:24,150 --> 00:31:27,500
Dis nie waar nie van funksies, hoe binnekant van hier,

412
00:31:27,500 --> 00:31:34,870
as ons, soos, node * of node x.

413
00:31:34,870 --> 00:31:37,380
Ons het geen idee wat x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
of ons kan druk hulle en hulle kan willekeurig wees.

415
00:31:40,700 --> 00:31:44,980
Dis nie waar nie van globale veranderlikes.

416
00:31:44,980 --> 00:31:47,450
So node wortel of node x.

417
00:31:47,450 --> 00:31:53,410
By verstek, alles wat wêreldwye, indien nie uitdruklik geïnisialiseer tot 'n sekere waarde,

418
00:31:53,410 --> 00:31:57,390
het 'n nul waarde as die waarde daarvan.

419
00:31:57,390 --> 00:32:01,150
So hier is, node * wortel, het ons nie uitdruklik inisialiseer enigiets,

420
00:32:01,150 --> 00:32:06,350
so sal sy verstek waarde van nul, wat is die nul waarde van wysers.

421
00:32:06,350 --> 00:32:11,870
Die standaard waarde van x is gaan om te beteken dat x.value is nul,

422
00:32:11,870 --> 00:32:14,260
x.left is van nul en x.right is van nul.

423
00:32:14,260 --> 00:32:21,070
So, aangesien dit 'n struct, sal al die velde van die struct nul waardes.

424
00:32:21,070 --> 00:32:24,410
Ons hoef nie hier gebruik, al is.

425
00:32:24,410 --> 00:32:27,320
[Studente] Die structs is anders as ander veranderlikes, en die ander veranderlikes

426
00:32:27,320 --> 00:32:31,400
vullis waardes, dit is nulle?

427
00:32:31,400 --> 00:32:36,220
[Bowden] ander waardes ook. So in x, x nul wees.

428
00:32:36,220 --> 00:32:40,070
As dit op wêreldwye omvang, dit het 'n aanvanklike waarde. >> Goed.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Óf die aanvanklike waarde jy het dit of nul.

430
00:32:48,950 --> 00:32:53,260
Ek dink wat sorg van al hierdie.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Sodat die volgende deel van die vraag vra,

432
00:32:58,390 --> 00:33:01,260
"Nou wil ons 'n funksie met die naam bevat te skryf

433
00:33:01,260 --> 00:33:04,930
met 'n prototipe van Bool int waarde bevat. "

434
00:33:04,930 --> 00:33:08,340
Ons is nie van plan om te doen Bool bevat int waarde.

435
00:33:08,340 --> 00:33:15,110
Ons prototipe gaan lyk

436
00:33:15,110 --> 00:33:22,380
Bool bevat (int waarde.

437
00:33:22,380 --> 00:33:24,490
En dan is ons ook gaan om die boom te slaag

438
00:33:24,490 --> 00:33:28,870
dat dit moet beheer word om te sien of dit dat die waarde.

439
00:33:28,870 --> 00:33:38,290
So node * boom). Okay.

440
00:33:38,290 --> 00:33:44,440
En dan kan ons noem dit met iets soos,

441
00:33:44,440 --> 00:33:46,090
miskien sal ons wil printf of iets.

442
00:33:46,090 --> 00:33:51,040
Bevat 6, ons wortel.

443
00:33:51,040 --> 00:33:54,300
Dit moet terugkeer, of waar,

444
00:33:54,300 --> 00:33:59,390
terwyl bevat 5 wortel moet terugkeer vals.

445
00:33:59,390 --> 00:34:02,690
So neem 'n tweede om dit te implementeer.

446
00:34:02,690 --> 00:34:06,780
Jy kan dit doen óf iteratief of rekursief.

447
00:34:06,780 --> 00:34:09,739
Die nice ding oor die manier waarop ons het dinge op wat

448
00:34:09,739 --> 00:34:12,300
dit leen hom tot ons rekursiewe oplossing baie makliker

449
00:34:12,300 --> 00:34:14,719
as die globale veranderlike manier gedoen het.

450
00:34:14,719 --> 00:34:19,750
Want as ons net int waarde bevat, dan het ons geen manier van recursing subtrees.

451
00:34:19,750 --> 00:34:24,130
Ons wil hê dat 'n aparte helper funksie wat recurses die subtrees vir ons te hê.

452
00:34:24,130 --> 00:34:29,610
Maar vandat ons het dit verander om die boom te neem as 'n argument,

453
00:34:29,610 --> 00:34:32,760
wat dit moet altyd in die eerste plek gewees het,

454
00:34:32,760 --> 00:34:35,710
nou kan ons recursief makliker.

455
00:34:35,710 --> 00:34:38,960
So iteratiewe of rekursiewe, sal ons gaan oor beide,

456
00:34:38,960 --> 00:34:46,139
maar ons sal sien dat die rekursiewe eindig baie maklik.

457
00:34:59,140 --> 00:35:02,480
Okay. Is daar iemand het iets wat ons kan werk met?

458
00:35:02,480 --> 00:35:12,000
>> [Studente] Ek het 'n iteratiewe oplossing. >> Alle reg, iteratiewe.

459
00:35:12,000 --> 00:35:16,030
Goed, dit lyk goed.

460
00:35:16,030 --> 00:35:18,920
So, wil ons om te wandel deur dit?

461
00:35:18,920 --> 00:35:25,780
[Studente] Sure. So het ek 'n temp veranderlike Die eerste nodus van die boom te kry.

462
00:35:25,780 --> 00:35:28,330
En dan het ek net Looped deur terwyl temp nie gelyk aan nul,

463
00:35:28,330 --> 00:35:31,700
Dus, terwyl was nog in die boom, dink ek.

464
00:35:31,700 --> 00:35:35,710
En as die waarde is gelyk aan die waarde wat temp wys,

465
00:35:35,710 --> 00:35:37,640
dan is dit terug daardie waarde.

466
00:35:37,640 --> 00:35:40,210
Andersins, dit kontroleer of dit as dit is aan die regterkant of die linkerkant.

467
00:35:40,210 --> 00:35:43,400
As jy al ooit 'n situasie waar daar is nie meer boom,

468
00:35:43,400 --> 00:35:47,330
dan is dit terug - dit uitgange die lus en terugkeer vals.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Goed. So dit lyk goed.

470
00:35:52,190 --> 00:35:58,470
Enigeen het enige kommentaar op enigiets?

471
00:35:58,470 --> 00:36:02,400
Ek het geen die korrektheid kommentaar at all.

472
00:36:02,400 --> 00:36:11,020
Die een ding wat ons kan doen, is hierdie man.

473
00:36:11,020 --> 00:36:21,660
Ag, gaan dit 'n bietjie langerige om te gaan.

474
00:36:21,660 --> 00:36:33,460
Ek sal regmaak wat up. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Almal moet onthou hoe drieledige werk.

476
00:36:37,150 --> 00:36:38,610
Daar het beslis in die verlede is vasvrae

477
00:36:38,610 --> 00:36:41,170
wat gee jou 'n funksie met 'n drieledige operateur,

478
00:36:41,170 --> 00:36:45,750
en sê, te vertaal, iets te doen wat nie drieledige gebruik.

479
00:36:45,750 --> 00:36:49,140
So, dit is 'n baie algemene geval van wanneer ek sou dink drieledige te gebruik,

480
00:36:49,140 --> 00:36:54,610
waar as sommige toestand 'n veranderlike na iets,

481
00:36:54,610 --> 00:36:58,580
anders dat dieselfde veranderlike na iets anders.

482
00:36:58,580 --> 00:37:03,390
Dit is iets wat baie dikwels kan omskep word in hierdie soort van ding

483
00:37:03,390 --> 00:37:14,420
waar dat die veranderlike te stel - of, wel, is dit waar? Dan is hierdie, anders.

484
00:37:14,420 --> 00:37:18,550
[Studente] Die eerste een is indien dit waar is, reg?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Ja. Die manier waarop ek dit altyd lees, temp gelyk is aan die waarde groter as temp waarde,

486
00:37:25,570 --> 00:37:30,680
dan is dit, anders. Dit is 'n vraag te vra.

487
00:37:30,680 --> 00:37:35,200
Is dit 'n groter? Doen dan die eerste ding. Anders doen die tweede ding.

488
00:37:35,200 --> 00:37:41,670
Ek word feitlik altyd - die kolon, ek het net in my kop, ek lees anders.

489
00:37:41,670 --> 00:37:47,180
>> Is daar iemand het 'n rekursiewe oplossing?

490
00:37:47,180 --> 00:37:49,670
Okay. Hierdie een wat ons gaan - dit kan reeds groot wees,

491
00:37:49,670 --> 00:37:53,990
maar ons gaan om dit nog beter te maak.

492
00:37:53,990 --> 00:37:58,720
Dit is pretty much die presies dieselfde idee.

493
00:37:58,720 --> 00:38:03,060
Dit is net goed doen wat jy wil om te verduidelik?

494
00:38:03,060 --> 00:38:08,340
[Studente] Sure. So maak ons ​​seker dat die boom nie eerste nulpunt,

495
00:38:08,340 --> 00:38:13,380
want as die boom is null dan is dit gaan om terug te keer vals omdat ons dit nog nie gevind nie.

496
00:38:13,380 --> 00:38:19,200
En as daar is nog steeds 'n boom, gaan ons in - ons eers kyk of die waarde is die huidige node.

497
00:38:19,200 --> 00:38:23,740
True terug gee as dit is, en as ons nie recursief op die linker-of regs.

498
00:38:23,740 --> 00:38:25,970
Klink dit gepas? >> Mm-hmm. (Ooreenkoms)

499
00:38:25,970 --> 00:38:33,880
So sien dat dit amper is struktureel baie soortgelyk aan die iteratiewe oplossing.

500
00:38:33,880 --> 00:38:38,200
Dit is net dat in plaas van recursing, het ons 'n while lus.

501
00:38:38,200 --> 00:38:40,840
En die basis geval hier waar die boom is nie gelyk aan nul

502
00:38:40,840 --> 00:38:44,850
was die voorwaarde waaronder ons uitgebreek het van die while lus.

503
00:38:44,850 --> 00:38:50,200
Hulle is baie soortgelyk. Maar ons gaan hierdie een stap verder te gaan.

504
00:38:50,200 --> 00:38:54,190
Nou, ons doen dieselfde ding hier.

505
00:38:54,190 --> 00:38:57,680
Kennisgewing ons die dieselfde ding in beide van hierdie lyne is die terugkeer,

506
00:38:57,680 --> 00:39:00,220
behalwe vir een argument is anders.

507
00:39:00,220 --> 00:39:07,950
So ons gaan om dit te maak in 'n drieledige.

508
00:39:07,950 --> 00:39:13,790
Ek opsie iets getref het, en dit het 'n simbool. Okay.

509
00:39:13,790 --> 00:39:21,720
So ons gaan om terug te keer bevat.

510
00:39:21,720 --> 00:39:28,030
Dit is om verskeie lyne, goed, vergrote in dit is.

511
00:39:28,030 --> 00:39:31,060
Gewoonlik, as 'n stilistiese ding, ek dink nie baie mense

512
00:39:31,060 --> 00:39:38,640
sit 'n spasie na die pyl, maar ek dink as jy konsekwent, dit is goed.

513
00:39:38,640 --> 00:39:44,320
As waarde is minder as boom waarde, ons wil recursief op die boom links,

514
00:39:44,320 --> 00:39:53,890
anders wat ons wil recursief op die boom reg.

515
00:39:53,890 --> 00:39:58,610
So dit was stap een van die maak van hierdie kyk kleiner.

516
00:39:58,610 --> 00:40:02,660
Stap twee van die maak van hierdie kyk kleiner -

517
00:40:02,660 --> 00:40:09,150
ons kan skei dit aan verskeie lyne.

518
00:40:09,150 --> 00:40:16,500
Okay. Stap twee van die maak van dit lyk kleiner is hier,

519
00:40:16,500 --> 00:40:25,860
so opbrengs waarde is gelyk aan boom waarde, of bevat wat ookal.

520
00:40:25,860 --> 00:40:28,340
>> Dit is 'n belangrike ding.

521
00:40:28,340 --> 00:40:30,860
Ek is nie seker as hy sê dit uitdruklik in die klas,

522
00:40:30,860 --> 00:40:34,740
maar dit is kortsluiting evaluering genoem.

523
00:40:34,740 --> 00:40:41,060
Die idee hier is 'n waarde == boom waarde.

524
00:40:41,060 --> 00:40:49,960
As dit waar is, dan is dit waar, en ons wil "of" dat met alles wat hier.

525
00:40:49,960 --> 00:40:52,520
So sonder om selfs te dink oor alles wat hier,

526
00:40:52,520 --> 00:40:55,070
wat is die hele uitdrukking gaan om terug te keer?

527
00:40:55,070 --> 00:40:59,430
[Studente] True? >> Ja, want waar van enigiets,

528
00:40:59,430 --> 00:41:04,990
or'd - of waar or'd met enigiets is noodwendig waar nie.

529
00:41:04,990 --> 00:41:08,150
So gou as ons sien return value = boom waarde,

530
00:41:08,150 --> 00:41:10,140
ons is maar net gaan om terug te keer waar.

531
00:41:10,140 --> 00:41:15,710
Nie eens gaan recursief bevat verder af in die lyn.

532
00:41:15,710 --> 00:41:20,980
Ons kan hierdie een stap verder te neem.

533
00:41:20,980 --> 00:41:29,490
Return boom is nie gelyk aan nul en al hierdie dinge.

534
00:41:29,490 --> 00:41:32,650
Dit maak dit 'n een-line funksie.

535
00:41:32,650 --> 00:41:36,790
Dit is ook 'n voorbeeld van 'n kortsluiting evaluering.

536
00:41:36,790 --> 00:41:40,680
Maar nou is dit dieselfde idee -

537
00:41:40,680 --> 00:41:47,320
in plaas van - so as boom is nie gelyk aan nul - of, wel,

538
00:41:47,320 --> 00:41:49,580
as die boom nie gelyk null, wat is die slegte geval,

539
00:41:49,580 --> 00:41:54,790
as die boom is gelyk aan nul is, dan is die eerste voorwaarde is gaan om vals te wees.

540
00:41:54,790 --> 00:42:00,550
So valse anded met enigiets gaan wees wat?

541
00:42:00,550 --> 00:42:04,640
[Studente] False. >> Ja. Dit is die ander helfte van die kortsluiting evaluering,

542
00:42:04,640 --> 00:42:10,710
waar as boom is nie gelyk aan nul is, dan is ons nie van plan om selfs te gaan -

543
00:42:10,710 --> 00:42:14,930
of indien boom gelyk null, dan het ons nie gaan om die waarde == boom waarde te doen.

544
00:42:14,930 --> 00:42:17,010
Ons is net gaan om onmiddellik return false.

545
00:42:17,010 --> 00:42:20,970
Wat belangrik is, want as dit nie 'n kortsluiting evalueer,

546
00:42:20,970 --> 00:42:25,860
dan as boom gelyk null, is hierdie tweede toestand gaan te seg skuld,

547
00:42:25,860 --> 00:42:32,510
omdat boom-> waarde ontwysing null.

548
00:42:32,510 --> 00:42:40,490
So dit is dit. Kan hierdie skuif weer oor.

549
00:42:40,490 --> 00:42:44,840
Dit is ook 'n baie algemene ding, nie die maak van hierdie een lyn met hierdie,

550
00:42:44,840 --> 00:42:49,000
maar dit is 'n algemene ding in omstandighede, miskien nie reg hier,

551
00:42:49,000 --> 00:42:59,380
maar as (boom = NULL, en boom-> waarde == waarde), doen wat ook al.

552
00:42:59,380 --> 00:43:01,560
Dit is 'n baie algemene toestand, waar in plaas van om

553
00:43:01,560 --> 00:43:06,770
om dit te breek in twee ifs, waar wil, is die boom null?

554
00:43:06,770 --> 00:43:11,780
Goed, dit is nie null, so nou is die boom waarde gelyk aan waarde? Doen dit.

555
00:43:11,780 --> 00:43:17,300
In plaas daarvan, het hierdie toestand, sal dit nooit seg skuld

556
00:43:17,300 --> 00:43:21,220
want dit sal breek as dit gebeur te wees null.

557
00:43:21,220 --> 00:43:24,000
Wel, ek dink as jou boom is 'n heeltemal ongeldig pointer, kan dit nog steeds seg skuld,

558
00:43:24,000 --> 00:43:26,620
maar dit kan nie seg skuld as die boom is null.

559
00:43:26,620 --> 00:43:32,900
As dit nul is, sal dit breek uit voor jy al ooit die wyser in die eerste plek be dereferenced.

560
00:43:32,900 --> 00:43:35,000
[Studente] Is hierdie sogenaamde lui evaluering?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy evaluering is 'n aparte ding.

562
00:43:40,770 --> 00:43:49,880
Lazy evaluering is meer soos jy vra vir 'n waarde,

563
00:43:49,880 --> 00:43:54,270
jy vra 'n waarde te bereken, soort van, maar jy hoef dit nie onmiddellik.

564
00:43:54,270 --> 00:43:59,040
So totdat jy dit nodig het, is dit nie geëvalueer.

565
00:43:59,040 --> 00:44:03,920
Dit is nie presies dieselfde ding, maar in die Huffman pset,

566
00:44:03,920 --> 00:44:06,520
dit sê dat ons "lui" skryf.

567
00:44:06,520 --> 00:44:08,670
Die rede waarom ons dit doen, is omdat ons eintlik die skryf buffering -

568
00:44:08,670 --> 00:44:11,820
ons wil nie individuele stukkies te skryf op 'n tyd,

569
00:44:11,820 --> 00:44:15,450
of individuele bytes op 'n tyd, ons wil plaas 'n stuk grepe te kry.

570
00:44:15,450 --> 00:44:19,270
Dan weer ons het 'n stuk van grepe, dan sal ons dit skryf.

571
00:44:19,270 --> 00:44:22,640
Selfs al is jy vra om dit te skryf - en fwrite en fread die dieselfde soort van ding doen.

572
00:44:22,640 --> 00:44:26,260
Hulle buffer jou lees en skryf.

573
00:44:26,260 --> 00:44:31,610
Selfs al is jy vra om dit onmiddellik te skryf, dit sal waarskynlik nie.

574
00:44:31,610 --> 00:44:34,540
En jy kan nie seker wees dat dinge gaan geskryf word

575
00:44:34,540 --> 00:44:37,540
totdat jy noem hfclose of wat dit ookal is,

576
00:44:37,540 --> 00:44:39,620
wat dan sê, okay, ek maak my lêer,

577
00:44:39,620 --> 00:44:43,450
dit beteken dat ek beter wil skryf alles wat ek nog nie geskryf nie.

578
00:44:43,450 --> 00:44:45,770
Dit is nie nodig om alles uit te skryf

579
00:44:45,770 --> 00:44:49,010
totdat jy die sluiting van die lêer, en dan moet dit.

580
00:44:49,010 --> 00:44:56,220
So dit is net wat lui - dit wag totdat dit gebeur.

581
00:44:56,220 --> 00:44:59,990
Dit - 51 en jy sal dit in meer detail gaan in,

582
00:44:59,990 --> 00:45:05,470
omdat OCaml en alles in 51, alles is rekursie.

583
00:45:05,470 --> 00:45:08,890
Daar is geen iteratiewe oplossings, basies.

584
00:45:08,890 --> 00:45:11,550
Alles is rekursie, en lui evaluering

585
00:45:11,550 --> 00:45:14,790
gaan belangrik wees vir 'n baie van die omstandighede

586
00:45:14,790 --> 00:45:19,920
waar, as jy nie lui nie evalueer, sou dit beteken -

587
00:45:19,920 --> 00:45:24,760
Die voorbeeld is strome, wat is oneindig lank.

588
00:45:24,760 --> 00:45:30,990
In teorie, kan jy dink van die natuurlike getalle as 'n stroom van 1-2-3-4-5-6-7

589
00:45:30,990 --> 00:45:33,090
So lui geëvalueer dinge is fyn.

590
00:45:33,090 --> 00:45:37,210
As ek sê: Ek wil die tiende nommer, dan sal ek kan evalueer tot die tiende getal.

591
00:45:37,210 --> 00:45:40,300
As ek wil die honderdste getal, dan sal ek kan evalueer tot die honderdste getal.

592
00:45:40,300 --> 00:45:46,290
Sonder lui evaluering, dan is dit gaan om te probeer om al die getalle onmiddellik te evalueer.

593
00:45:46,290 --> 00:45:50,000
Jy evaluering van oneindig baie getalle, en dit is net nie moontlik nie.

594
00:45:50,000 --> 00:45:52,080
So daar is 'n baie van die omstandighede waar lui evaluering

595
00:45:52,080 --> 00:45:57,840
is net noodsaaklik om dinge uit te werk.

596
00:45:57,840 --> 00:46:05,260
>> Nou wil ons insetsel te skryf waar insetsel gaan wees

597
00:46:05,260 --> 00:46:08,430
soortgelyke verandering in sy definisie.

598
00:46:08,430 --> 00:46:10,470
So nou is dit Bool insert (int waarde).

599
00:46:10,470 --> 00:46:23,850
Ons gaan dat Bool insert (int waarde, node * boom) te verander.

600
00:46:23,850 --> 00:46:29,120
Ons het eintlik gaan dit weer in 'n bietjie verander, sal ons sien waarom.

601
00:46:29,120 --> 00:46:32,210
En laat ons beweeg build_node, net vir die heck dit,

602
00:46:32,210 --> 00:46:36,730
hierbo te voeg, sodat ons het nie 'n funksie-prototipe te skryf.

603
00:46:36,730 --> 00:46:42,450
Wat is 'n aanduiding dat jy gaan word met behulp van build_node in insetsel.

604
00:46:42,450 --> 00:46:49,590
Okay. Neem 'n minuut vir daardie.

605
00:46:49,590 --> 00:46:52,130
Ek dink ek het die hersiening gered as jy wil om te trek uit,

606
00:46:52,130 --> 00:47:00,240
of ten minste, ek het nou.

607
00:47:00,240 --> 00:47:04,190
Ek wou 'n effense breek om te dink oor die logika van die insetsel,

608
00:47:04,190 --> 00:47:08,750
as jy nie kan dink.

609
00:47:08,750 --> 00:47:12,860
Basies, sal jy altyd net die invoeging word op die blare.

610
00:47:12,860 --> 00:47:18,640
Soos, as ek voeg 1, dan is ek onvermydelik gaan word die invoeging van 1 -

611
00:47:18,640 --> 00:47:21,820
Ek sal verander na swart - I'll word die invoeging van 1 hier.

612
00:47:21,820 --> 00:47:28,070
Of as Ek voeg 4, Ek wil die invoeging van 4 hier.

613
00:47:28,070 --> 00:47:32,180
So maak nie saak wat jy doen, jy gaan op 'n blaar word die invoeging.

614
00:47:32,180 --> 00:47:36,130
Al wat jy hoef te doen, is itereer die boom af totdat jy by die node

615
00:47:36,130 --> 00:47:40,890
wat die node se ouer, die nuwe node se ouer,

616
00:47:40,890 --> 00:47:44,560
en dan sy links of regs wyser verander, afhangende van of

617
00:47:44,560 --> 00:47:47,060
dit is groter as of minder as die huidige node.

618
00:47:47,060 --> 00:47:51,180
Verander dat wyser om te wys op jou nuwe node.

619
00:47:51,180 --> 00:48:05,490
So itereer die boom af, maak die blaar punt na die nuwe node.

620
00:48:05,490 --> 00:48:09,810
Ook dink oor die rede waarom dit verbied die tipe van situasie voor,

621
00:48:09,810 --> 00:48:17,990
waar ek die binêre boom gebou waar dit korrek was

622
00:48:17,990 --> 00:48:19,920
as jy net kyk na 'n enkele nodus,

623
00:48:19,920 --> 00:48:24,830
maar 9 was aan die linkerkant van 7 as jy al die pad af herhaalde.

624
00:48:24,830 --> 00:48:29,770
So dit is onmoontlik in hierdie scenario, aangesien

625
00:48:29,770 --> 00:48:32,530
dink oor die invoeging van 9 of iets, op die heel eerste node,

626
00:48:32,530 --> 00:48:35,350
Ek gaan 7 te sien en ek is net gaan om te gaan na die regterkant.

627
00:48:35,350 --> 00:48:38,490
So maak nie saak wat ek doen, as ek die invoeging deur te gaan na 'n blaar,

628
00:48:38,490 --> 00:48:40,790
en aan 'n blaar met behulp van die toepaslike algoritme,

629
00:48:40,790 --> 00:48:43,130
dit gaan onmoontlik wees om vir my 9 te voeg aan die linkerkant van 7

630
00:48:43,130 --> 00:48:48,250
want so gou as ek getref 7 Ek gaan om te gaan na die regterkant.

631
00:48:59,740 --> 00:49:02,070
Is daar iemand het iets om mee te begin?

632
00:49:02,070 --> 00:49:05,480
[Studente] Ek doen. >> Sure.

633
00:49:05,480 --> 00:49:09,200
[Student, onverstaanbaar]

634
00:49:09,200 --> 00:49:14,390
[Ander student, onverstaanbaar]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Dit word waardeer. Okay. Wil jy om te verduidelik?

636
00:49:18,330 --> 00:49:20,690
>> [Studente] Omdat ons weet dat ons is die invoeging van

637
00:49:20,690 --> 00:49:24,060
nuwe nodes aan die einde van die boom,

638
00:49:24,060 --> 00:49:28,070
Ek haak deur die boom iteratief

639
00:49:28,070 --> 00:49:31,360
totdat ek by 'n node wat daarop aan nul.

640
00:49:31,360 --> 00:49:34,220
En dan het ek besluit om dit te sit aan die regterkant of die linkerkant

641
00:49:34,220 --> 00:49:37,420
deur gebruik te maak van hierdie reg veranderlike, dit het vir my gesê waar om dit te sit.

642
00:49:37,420 --> 00:49:41,850
En dan, in wese, Ek het net gemaak dat dit die laaste -

643
00:49:41,850 --> 00:49:47,520
dat die temp node punt na die nuwe node dat dit skep,

644
00:49:47,520 --> 00:49:50,770
óf aan die linkerkant of aan die regterkant, afhangende van wat die waarde was reg.

645
00:49:50,770 --> 00:49:56,530
Ten slotte, ek het die nuwe node waarde tot die waarde van die toets.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okay, so ek sien een probleem hier.

647
00:49:59,550 --> 00:50:02,050
Dit is soos 95% van die manier waarop daar.

648
00:50:02,050 --> 00:50:07,550
Die een probleem wat ek sien, goed, iemand anders sien 'n probleem?

649
00:50:07,550 --> 00:50:18,400
Wat is die omstandighede waaronder hulle breek uit van die lus?

650
00:50:18,400 --> 00:50:22,100
[Studente] As temp is van nul? >> Ja. So, hoe jy breek uit van die lus is as die temp is null.

651
00:50:22,100 --> 00:50:30,220
Maar wat doen ek hier?

652
00:50:30,220 --> 00:50:35,410
Ek dereference temp, wat is onvermydelik null.

653
00:50:35,410 --> 00:50:39,840
En die ander ding wat jy hoef te doen, is nie net hou totdat die temp is null,

654
00:50:39,840 --> 00:50:45,590
jy wil om tred te hou van die ouer ten alle tye.

655
00:50:45,590 --> 00:50:52,190
Ons wil ook node * ouer, ek dink ons ​​dat by null kan hou op die eerste.

656
00:50:52,190 --> 00:50:55,480
Dit gaan vreemde gedrag te hê vir die wortel van die boom,

657
00:50:55,480 --> 00:50:59,210
maar ons sal kry.

658
00:50:59,210 --> 00:51:03,950
As waarde is groter as wat ookal, dan temp = temp reg.

659
00:51:03,950 --> 00:51:07,910
Maar voordat ons dit doen, ouer = temp.

660
00:51:07,910 --> 00:51:14,500
Of ouers is altyd gaan op gelyke temp? Is dit die geval?

661
00:51:14,500 --> 00:51:19,560
Indien temp nie null, dan gaan ek om te beweeg, maak nie saak wat,

662
00:51:19,560 --> 00:51:24,030
na 'n node waarvoor temp is die ouer.

663
00:51:24,030 --> 00:51:27,500
So ouer gaan wees temp, en dan skuif ek temp af.

664
00:51:27,500 --> 00:51:32,410
Nou temp is null, maar ouer punte aan die ouer van die ding wat null.

665
00:51:32,410 --> 00:51:39,110
So hier, ek wil nie reg te stel gelyk aan 1.

666
00:51:39,110 --> 00:51:41,300
So het ek verhuis na die reg, so as regs = 1,

667
00:51:41,300 --> 00:51:45,130
en ek dink jy wil ook om te doen -

668
00:51:45,130 --> 00:51:48,530
as jy na links beweeg, wil jy reg te stel gelyk aan 0.

669
00:51:48,530 --> 00:51:55,950
Of anders as jy ooit na regs beweeg.

670
00:51:55,950 --> 00:51:58,590
So reg = 0. As regs = 1,

671
00:51:58,590 --> 00:52:04,260
nou wil ons die ouer regs wyser newnode te maak,

672
00:52:04,260 --> 00:52:08,520
anders wil ons die ouer links wyser newnode te maak.

673
00:52:08,520 --> 00:52:16,850
Vrae oor wat?

674
00:52:16,850 --> 00:52:24,880
Okay. So, dit is die manier waarop ons - Wel, eintlik, in plaas van om dit te doen,

675
00:52:24,880 --> 00:52:29,630
Ons het half verwag jy build_node te gebruik.

676
00:52:29,630 --> 00:52:40,450
En dan as newnode gelyk aan nul, return false.

677
00:52:40,450 --> 00:52:44,170
Dit is dit. Nou, dit is wat ons verwag dat jy moet doen.

678
00:52:44,170 --> 00:52:47,690
>> Dit is wat die personeel oplossings doen.

679
00:52:47,690 --> 00:52:52,360
Ek het nie eens met hierdie as die "regte" manier gaan oor dit

680
00:52:52,360 --> 00:52:57,820
maar dit is heeltemal fyn, en dit sal werk.

681
00:52:57,820 --> 00:53:02,840
Een ding wat 'n bietjie weird reg nou is

682
00:53:02,840 --> 00:53:08,310
indien die boom begin as null, het ons in 'n null boom.

683
00:53:08,310 --> 00:53:12,650
Ek dink dit hang af van hoe jy definieer die gedrag van die wat in 'n null boom.

684
00:53:12,650 --> 00:53:15,490
Ek sou dink dat as jy slaag in 'n null boom,

685
00:53:15,490 --> 00:53:17,520
dan invoeging van die waarde in 'n null boom

686
00:53:17,520 --> 00:53:23,030
moet net terugkeer 'n boom waar die enigste waarde is dat enkele nodus.

687
00:53:23,030 --> 00:53:25,830
Moenie mense dit eens met wat? Jy kan, as jy wil,

688
00:53:25,830 --> 00:53:28,050
as jy slaag in 'n null boom

689
00:53:28,050 --> 00:53:31,320
en jy wil 'n waarde toe te voeg in dit, return false.

690
00:53:31,320 --> 00:53:33,830
Dit is aan jou om te definieer.

691
00:53:33,830 --> 00:53:38,320
Die eerste ding wat ek gesê het en dan te doen -

692
00:53:38,320 --> 00:53:40,720
Wel, jy gaan sukkel om dit te doen te hê, want

693
00:53:40,720 --> 00:53:44,090
dit makliker sou wees as ons het 'n globale wyser na die ding,

694
00:53:44,090 --> 00:53:48,570
maar ons weet nie, so as die boom is null, daar is niks wat ons daaraan kan doen nie.

695
00:53:48,570 --> 00:53:50,960
Ons kan net terugkeer vals.

696
00:53:50,960 --> 00:53:52,840
So ek gaan insetsel te verander.

697
00:53:52,840 --> 00:53:56,540
Ons tegnies kon net verander hierdie reg hier,

698
00:53:56,540 --> 00:53:58,400
hoe dit iterating oor dinge,

699
00:53:58,400 --> 00:54:04,530
maar ek gaan insetsel te verander na 'n node ** boom.

700
00:54:04,530 --> 00:54:07,510
Double wysers.

701
00:54:07,510 --> 00:54:09,710
Wat beteken dit?

702
00:54:09,710 --> 00:54:12,330
In plaas van die hantering van verwysings na nodes,

703
00:54:12,330 --> 00:54:16,690
die ding wat ek gaan manipuleer is dit wyser.

704
00:54:16,690 --> 00:54:18,790
Ek gaan om te manipuleer hierdie wyser.

705
00:54:18,790 --> 00:54:21,770
Ek gaan om te manipuleer pointers direk.

706
00:54:21,770 --> 00:54:25,760
Dit maak sin, aangesien dink oor af -

707
00:54:25,760 --> 00:54:33,340
goed, reg nou hierdie punte aan nul.

708
00:54:33,340 --> 00:54:38,130
Wat ek wil doen is manipuleer hierdie wyser om te wys nie NULL.

709
00:54:38,130 --> 00:54:40,970
Ek wil om dit te wys op my nuwe node.

710
00:54:40,970 --> 00:54:44,870
As ek net hou van wysers na my pointers,

711
00:54:44,870 --> 00:54:47,840
dan het ek nie nodig om tred te hou van 'n ouer wyser.

712
00:54:47,840 --> 00:54:52,640
Ek kan net dop om te sien of die wyser wys aan nul,

713
00:54:52,640 --> 00:54:54,580
en indien die wyser wys na NULL,

714
00:54:54,580 --> 00:54:57,370
verander dit om te verwys na die node wat ek wil hê.

715
00:54:57,370 --> 00:55:00,070
En ek kan dit verander, want ek het 'n wyser na die wyser.

716
00:55:00,070 --> 00:55:02,040
Laat hierdie reg nou sien.

717
00:55:02,040 --> 00:55:05,470
Jy kan eintlik dit doen rekursief redelik maklik.

718
00:55:05,470 --> 00:55:08,080
Wil ons dit te doen?

719
00:55:08,080 --> 00:55:10,980
Ja, ons doen.

720
00:55:10,980 --> 00:55:16,790
>> Laat ons sien dit rekursief.

721
00:55:16,790 --> 00:55:24,070
Eerstens, is wat ons basis geval gaan wees?

722
00:55:24,070 --> 00:55:29,140
Byna altyd ons basis geval, maar eintlik is dit soort moeilik.

723
00:55:29,140 --> 00:55:34,370
Eerste dinge eerste, indien (boom == null)

724
00:55:34,370 --> 00:55:37,550
Ek dink dat ons net gaan om terug te keer vals.

725
00:55:37,550 --> 00:55:40,460
Dit is verskil van jou boom null.

726
00:55:40,460 --> 00:55:44,510
Dit is die wyser na jou wortel pointer null

727
00:55:44,510 --> 00:55:48,360
wat beteken dat jou wortel wyser nie bestaan ​​nie.

728
00:55:48,360 --> 00:55:52,390
So hier, as ek dit doen

729
00:55:52,390 --> 00:55:55,760
node * - laat ons net hergebruik hierdie.

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

731
00:55:58,960 --> 00:56:00,730
en dan gaan ek voeg deur so iets te doen om te bel,

732
00:56:00,730 --> 00:56:04,540
voeg 4 in & Root.

733
00:56:04,540 --> 00:56:06,560
So & wortel, as die wortel is 'n node *

734
00:56:06,560 --> 00:56:11,170
dan & Root gaan 'n node **.

735
00:56:11,170 --> 00:56:15,120
Dit is geldig. In hierdie geval, boom, tot hier,

736
00:56:15,120 --> 00:56:20,120
boom is nie null, of voeg.

737
00:56:20,120 --> 00:56:24,630
Hier. Boom is nie null, * boom is null, wat is goed

738
00:56:24,630 --> 00:56:26,680
want as * boom is van nul, dan sal ek kan manipuleer dit

739
00:56:26,680 --> 00:56:29,210
nou verwys na wat ek wil om dit te wys.

740
00:56:29,210 --> 00:56:34,750
Maar as die boom is nul, wat beteken dat ek net hier afgekom en gesê null.

741
00:56:34,750 --> 00:56:42,710
Dit maak nie sin nie. Ek kan nie iets te doen met dit.

742
00:56:42,710 --> 00:56:45,540
As die boom is null, return false.

743
00:56:45,540 --> 00:56:48,220
So het ek basies reeds gesê wat ons werklike basis-geval is.

744
00:56:48,220 --> 00:56:50,580
En wat is dat gaan wees?

745
00:56:50,580 --> 00:56:55,030
[Student, onverstaanbaar]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ja. So as (* boom == null).

747
00:57:00,000 --> 00:57:04,520
Dit hou verband met die geval hier

748
00:57:04,520 --> 00:57:09,640
waar as my rooi wyser is om die ondeursigtigheid ek gefokus op,

749
00:57:09,640 --> 00:57:12,960
so soos ek gefokus op die wyser, nou ek gefokus op die wyser.

750
00:57:12,960 --> 00:57:15,150
Nou het ek gefokus op hierdie wyser.

751
00:57:15,150 --> 00:57:18,160
So as my rooi pointer, wat is my node **,

752
00:57:18,160 --> 00:57:22,880
ooit - indien *, my rooi pointer, is ooit null,

753
00:57:22,880 --> 00:57:28,470
wat beteken dat ek by die geval waar ek fokus op 'n wyser dat punte -

754
00:57:28,470 --> 00:57:32,530
dit is 'n wyser wat behoort aan 'n blaar.

755
00:57:32,530 --> 00:57:41,090
Ek wil hierdie wyser te verander om te wys op my nuwe node.

756
00:57:41,090 --> 00:57:45,230
Kom terug hier.

757
00:57:45,230 --> 00:57:56,490
My newnode sal net node * n = build_node (waarde)

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

759
00:58:07,300 --> 00:58:12,600
Anders wat ons wil om te verander wat die wyser tans verwys na

760
00:58:12,600 --> 00:58:17,830
tot nou toe te wys aan ons nuut gebou node.

761
00:58:17,830 --> 00:58:20,280
Ons kan eintlik hier doen.

762
00:58:20,280 --> 00:58:30,660
Plaas van sê: n, sê ons * boom = * boom.

763
00:58:30,660 --> 00:58:35,450
Almal verstaan ​​dat? Wat deur die hantering van verwysings na verwysings,

764
00:58:35,450 --> 00:58:40,750
ons kan verander null wysers om te wys op die dinge wat ons wil hê hulle om te verwys na.

765
00:58:40,750 --> 00:58:42,820
Dit is ons basis geval.

766
00:58:42,820 --> 00:58:45,740
>> Nou ons herhaling, of ons rekursie,

767
00:58:45,740 --> 00:58:51,430
gaan wees baie soortgelyk aan alle ander recursions het ons is besig.

768
00:58:51,430 --> 00:58:55,830
Ons gaan om te wil om waarde toe te voeg,

769
00:58:55,830 --> 00:58:59,040
en nou kan ek gaan drieledige om weer te gebruik nie, maar wat ons toestand gaan wees?

770
00:58:59,040 --> 00:59:05,180
Wat is dit wat ons soek om te besluit of ons wil gaan links of regs?

771
00:59:05,180 --> 00:59:07,760
Kom ons doen dit in afsonderlike stappe.

772
00:59:07,760 --> 00:59:18,850
As (waarde <) wat?

773
00:59:18,850 --> 00:59:23,200
[Studente] Die boom se waarde?

774
00:59:23,200 --> 00:59:27,490
[Bowden] So onthou dat ek op die oomblik is -

775
00:59:27,490 --> 00:59:31,260
[Studente onverstaanbaar]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Ja, so hier is, laat ons sê dat hierdie groen pyltjie

777
00:59:34,140 --> 00:59:39,050
is 'n voorbeeld van wat boom is tans, is 'n verwysing na hierdie wyser.

778
00:59:39,050 --> 00:59:46,610
So dit beteken dat ek 'n wyser na 'n wyser na 3.

779
00:59:46,610 --> 00:59:48,800
Die dereference twee keer klink goed.

780
00:59:48,800 --> 00:59:51,010
Wat ek doen - hoe doen ek dit?

781
00:59:51,010 --> 00:59:53,210
[Studente] Dereference een keer, en dan doen arrow dat die pad?

782
00:59:53,210 --> 00:59:58,420
[Bowden] (* boom) is die dereference een keer, -> waarde

783
00:59:58,420 --> 01:00:05,960
gaan gee my die waarde van die node dat ek is indirek verwys na.

784
01:00:05,960 --> 01:00:11,980
So ek kan ook skryf dit ** tree.value indien u verkies dat.

785
01:00:11,980 --> 01:00:18,490
Óf werk.

786
01:00:18,490 --> 01:00:26,190
As dit die geval is, dan wil ek noem voeg met 'n waarde.

787
01:00:26,190 --> 01:00:32,590
En wat is my opgedateer node ** gaan wees?

788
01:00:32,590 --> 01:00:39,440
Ek wil om te gaan na die linkerkant, sodat ** tree.left gaan aan my linkerkant.

789
01:00:39,440 --> 01:00:41,900
En ek wil die wyser na daardie ding

790
01:00:41,900 --> 01:00:44,930
sodat as die linkerkant eindig synde die null pointer,

791
01:00:44,930 --> 01:00:48,360
Ek kan verander om dit te wys op my nuwe node.

792
01:00:48,360 --> 01:00:51,460
>> En die ander geval kan wees baie soortgelyk.

793
01:00:51,460 --> 01:00:55,600
Kom ons eintlik dat my drieledige nou.

794
01:00:55,600 --> 01:01:04,480
Voeg waarde as waarde <(** boom). Waarde.

795
01:01:04,480 --> 01:01:11,040
Dan wil ons ons ** te werk aan die linkerkant,

796
01:01:11,040 --> 01:01:17,030
anders wat ons wil hê dat ons ** te werk aan die regterkant.

797
01:01:17,030 --> 01:01:22,540
[Studente] Beteken dit die wyser na die wyser?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Onthou dat - ** tree.right is 'n node ster.

799
01:01:30,940 --> 01:01:35,040
[Student, onverstaanbaar] >> Ja.

800
01:01:35,040 --> 01:01:41,140
** Tree.right is soos hierdie wyser of iets.

801
01:01:41,140 --> 01:01:45,140
So deur die neem van 'n wyser na daardie, gee my wat ek wil hê

802
01:01:45,140 --> 01:01:50,090
van die wyser na daardie man.

803
01:01:50,090 --> 01:01:54,260
[Studente] Kan ons gaan oor hoekom ons weer die twee wysers gebruik?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Ja. So - nee, jy kan, en dat die oplossing voor

805
01:01:58,220 --> 01:02:04,540
was 'n manier om dit te doen sonder om twee wysers.

806
01:02:04,540 --> 01:02:08,740
Jy moet in staat wees om te verstaan ​​met behulp van twee verwysings,

807
01:02:08,740 --> 01:02:11,660
en dit is 'n skoner oplossing.

808
01:02:11,660 --> 01:02:16,090
Ook kennis dat, wat gebeur as my boom -

809
01:02:16,090 --> 01:02:24,480
wat gebeur as my wortel null was? Wat gebeur as ek hierdie geval doen reg hier?

810
01:02:24,480 --> 01:02:30,540
So node * wortel = NULL, voeg 4 in & Root.

811
01:02:30,540 --> 01:02:35,110
Wat is die wortel gaan na hierdie te wees?

812
01:02:35,110 --> 01:02:37,470
[Student, onverstaanbaar] >> Ja.

813
01:02:37,470 --> 01:02:41,710
Root waarde gaan wees 4.

814
01:02:41,710 --> 01:02:45,510
Root links gaan wees null, wortel reg gaan wees null.

815
01:02:45,510 --> 01:02:49,490
In die geval waar ons nie slaag wortel adres,

816
01:02:49,490 --> 01:02:52,490
ons kan nie verander wortel skiet.

817
01:02:52,490 --> 01:02:56,020
In die geval waar die boom waar die wortel null,

818
01:02:56,020 --> 01:02:58,410
ons het net gehad het om terug te keer vals. Daar is niks wat ons kan doen nie.

819
01:02:58,410 --> 01:03:01,520
Ons kan nie reël invoeg 'n nodus in 'n leë boom.

820
01:03:01,520 --> 01:03:06,810
Maar nou kan ons, ons het net 'n leë boom in 'n een-node boom.

821
01:03:06,810 --> 01:03:13,400
Wat gewoonlik die verwagte manier waarop dit veronderstel is om te werk.

822
01:03:13,400 --> 01:03:21,610
>> Verder, dit is aansienlik korter as

823
01:03:21,610 --> 01:03:26,240
ook die dop van die ouer, en so itereer jy al die pad af.

824
01:03:26,240 --> 01:03:30,140
Nou het ek my ouers, en ek het my ouers regs wyser na die wat ookal.

825
01:03:30,140 --> 01:03:35,640
In plaas daarvan, as ons het dit gedoen iteratief, sou dit dieselfde idee met 'n while lus te wees.

826
01:03:35,640 --> 01:03:38,100
Maar in plaas van om te gaan met my ouer pointer,

827
01:03:38,100 --> 01:03:40,600
plaas my huidige wyser die ding sou wees

828
01:03:40,600 --> 01:03:43,790
dat ek direk die wysiging van om te wys op my nuwe node.

829
01:03:43,790 --> 01:03:46,090
Ek het nie te doen met of dit na links.

830
01:03:46,090 --> 01:03:48,810
Ek het nie te doen met of dit wys na regs.

831
01:03:48,810 --> 01:04:00,860
Dis net wat hierdie wyser is, ek gaan om dit te stel om te wys op my nuwe node.

832
01:04:00,860 --> 01:04:05,740
Almal verstaan ​​hoe dit werk?

833
01:04:05,740 --> 01:04:09,460
Indien nie waarom wil ons doen dit op hierdie manier,

834
01:04:09,460 --> 01:04:14,920
maar ten minste dat dit werk as 'n oplossing?

835
01:04:14,920 --> 01:04:17,110
[Studente] Waar terugkeer ons waar?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Dit is waarskynlik reg hier.

837
01:04:21,550 --> 01:04:26,690
As ons dit korrek voeg, terug waar.

838
01:04:26,690 --> 01:04:32,010
Anders, af hier is ons gaan watter insert opbrengste wil om terug te keer.

839
01:04:32,010 --> 01:04:35,950
>> En wat is spesiaal oor hierdie rekursiewe funksie?

840
01:04:35,950 --> 01:04:43,010
Dit is stert rekursiewe, so lank as wat ons stel met 'n paar optimalisatie,

841
01:04:43,010 --> 01:04:48,060
dit sal erken dat en jy sal nooit 'n stack overflow van hierdie,

842
01:04:48,060 --> 01:04:53,230
selfs as ons boom het 'n hoogte van 10.000 of 10 miljoen.

843
01:04:53,230 --> 01:04:55,630
[Student, onverstaanbaar]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Ek dink dit maak dit op Dash - of wat optimization vlak

845
01:05:00,310 --> 01:05:03,820
nodig is vir 'n stert rekursie om erken te word.

846
01:05:03,820 --> 01:05:09,350
Ek dink dit erken - GCC en kletteren

847
01:05:09,350 --> 01:05:12,610
ook verskillende betekenisse vir hul optimization vlakke.

848
01:05:12,610 --> 01:05:17,870
Ek wil om te sê dit is DashO 2, vir seker dat dit sal erken Staartrecursie.

849
01:05:17,870 --> 01:05:27,880
Maar ons - jy kan bou soos 'n Fibonocci voorbeeld of iets.

850
01:05:27,880 --> 01:05:30,030
Dit is nie maklik om te toets met hierdie, want dit is moeilik om te bou

851
01:05:30,030 --> 01:05:32,600
'n binêre boom wat so groot is.

852
01:05:32,600 --> 01:05:37,140
Maar ja, ek dink dit is DashO 2, wat

853
01:05:37,140 --> 01:05:40,580
as jy met DashO 2 stel, sal dit lyk vir Staartrecursie

854
01:05:40,580 --> 01:05:54,030
en te optimaliseer dat uit.

855
01:05:54,030 --> 01:05:58,190
Kom ons gaan terug tot - voeg is letterlik die laaste ding wat dit nodig het.

856
01:05:58,190 --> 01:06:04,900
Kom ons gaan terug na die insetsel oor hier

857
01:06:04,900 --> 01:06:07,840
waar ons gaan dieselfde idee om te doen.

858
01:06:07,840 --> 01:06:14,340
Dit sal nog steeds die fout nie in staat is om heeltemal te hanteer

859
01:06:14,340 --> 01:06:17,940
wanneer die wortel self, is van nul, of die afgelope inskrywing null,

860
01:06:17,940 --> 01:06:20,060
maar in plaas daarvan om met 'n ouer pointer,

861
01:06:20,060 --> 01:06:27,430
laat se aansoek doen om dieselfde logika van die behoud van verwysings na verwysings.

862
01:06:27,430 --> 01:06:35,580
As ons hier hou ons node ** huidige,

863
01:06:35,580 --> 01:06:37,860
en ons hoef nie om tred te hou van reg meer,

864
01:06:37,860 --> 01:06:47,190
maar node ** huidige = & boom.

865
01:06:47,190 --> 01:06:54,800
En nou is ons while lus gaan wees terwyl * huidig ​​is nie gelyk aan nul.

866
01:06:54,800 --> 01:07:00,270
Spoor van ouers hoef nie meer te hou.

867
01:07:00,270 --> 01:07:04,180
Hoef nie om tred te hou van links en regs.

868
01:07:04,180 --> 01:07:10,190
En ek sal dit noem temp, want ons reeds temp met behulp van.

869
01:07:10,190 --> 01:07:17,200
Okay. So as (waarde> * temp),

870
01:07:17,200 --> 01:07:24,010
dan & (* temp) -> reg

871
01:07:24,010 --> 01:07:29,250
anders temp = & (* temp) -> links.

872
01:07:29,250 --> 01:07:32,730
En nou, op hierdie punt, na hierdie while lus,

873
01:07:32,730 --> 01:07:36,380
Ek doen dit want miskien is dit is makliker om te dink oor iteratief as rekursief,

874
01:07:36,380 --> 01:07:39,010
maar na hierdie while lus,

875
01:07:39,010 --> 01:07:43,820
* Temp is die wyser wat ons wil verander.

876
01:07:43,820 --> 01:07:48,960
>> Voordat ons ouer, en ons wou óf ouer links of ouer reg om te verander,

877
01:07:48,960 --> 01:07:51,310
maar as ons wil ouer reg om te verander,

878
01:07:51,310 --> 01:07:54,550
* temp is ouer reg, en ons kan dit direk verander.

879
01:07:54,550 --> 01:08:05,860
So hier, kan ons doen * temp = newnode, en dit is dit.

880
01:08:05,860 --> 01:08:09,540
So kennisgewing, alles wat ons gedoen het in hierdie reëls van die kode.

881
01:08:09,540 --> 01:08:14,770
Ten einde tred te hou met die ouer in al die ekstra inspanning.

882
01:08:14,770 --> 01:08:18,689
Hier, as ons net hou van die wyser na die wyser,

883
01:08:18,689 --> 01:08:22,990
en selfs as ons wil om ontslae te raak van al hierdie krullerige draadjies nou,

884
01:08:22,990 --> 01:08:27,170
maak dat dit lyk korter.

885
01:08:27,170 --> 01:08:32,529
Dit is nou die presiese dieselfde oplossing,

886
01:08:32,529 --> 01:08:38,210
maar minder reëls van die kode.

887
01:08:38,210 --> 01:08:41,229
Sodra jy begin met die erkenning van hierdie as 'n geldige oplossing,

888
01:08:41,229 --> 01:08:43,529
dit is ook makliker om te redeneer oor as soos, okay,

889
01:08:43,529 --> 01:08:45,779
waarom het ek hierdie vlag op int reg?

890
01:08:45,779 --> 01:08:49,290
Wat beteken dit? O, is dit wat beteken dat

891
01:08:49,290 --> 01:08:51,370
elke keer as ek gaan reg, ek nodig het om dit te stel,

892
01:08:51,370 --> 01:08:53,819
anders as ek gaan links, ek nodig het om dit te stel aan nul.

893
01:08:53,819 --> 01:09:04,060
Hier, ek het nie om te redeneer oor wat, dit is net makliker om oor na te dink.

894
01:09:04,060 --> 01:09:06,710
Vrae?

895
01:09:06,710 --> 01:09:16,290
[Student, onverstaanbaar] >> Ja.

896
01:09:16,290 --> 01:09:23,359
Okay, so in die laaste bietjie -

897
01:09:23,359 --> 01:09:28,080
Ek dink 'n vinnige en maklike funksie wat ons kan doen is,

898
01:09:28,080 --> 01:09:34,910
let's - saam, dink ek, probeer en skryf 'n paragraaf bevat funksie

899
01:09:34,910 --> 01:09:38,899
wat nie omgee of dit is 'n binêre soekboom.

900
01:09:38,899 --> 01:09:43,770
Dit bevat 'n funksie waar moet terugkeer

901
01:09:43,770 --> 01:09:58,330
indien enige plek in hierdie algemene binêre boom is die waarde wat ons is op soek na.

902
01:09:58,330 --> 01:10:02,520
So laat ons eers dit rekursief doen en dan kan ons dit sal iteratief doen.

903
01:10:02,520 --> 01:10:07,300
Ons kan eintlik net doen dit saam, want dit gaan om te wees regtig kort.

904
01:10:07,300 --> 01:10:11,510
>> Wat is my base geval gaan wees?

905
01:10:11,510 --> 01:10:13,890
[Student, onverstaanbaar]

906
01:10:13,890 --> 01:10:18,230
[Bowden] So as (boom == null), wat dan?

907
01:10:18,230 --> 01:10:22,740
[Studente] Terug vals.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, goed, ek hoef nie die ander dinge.

909
01:10:26,160 --> 01:10:30,250
As was my ander basis geval.

910
01:10:30,250 --> 01:10:32,450
[Studente] Tree se waarde? >> Ja.

911
01:10:32,450 --> 01:10:36,430
So as (boom-> waarde == waarde.

912
01:10:36,430 --> 01:10:39,920
Kennisgewing ons terug is node *, nie node ** s?

913
01:10:39,920 --> 01:10:42,990
Contains sal nooit hoef te gebruik om 'n node **,

914
01:10:42,990 --> 01:10:45,480
Aangesien ons nie die wysiging van wysers.

915
01:10:45,480 --> 01:10:50,540
Ons is net kameelkoei hulle.

916
01:10:50,540 --> 01:10:53,830
As dit gebeur, dan is ons ware wil om terug te keer.

917
01:10:53,830 --> 01:10:58,270
Anders wil ons die kinders te verken.

918
01:10:58,270 --> 01:11:02,620
Ons kan dus nie redeneer oor die vraag of alles aan die linkerkant is minder

919
01:11:02,620 --> 01:11:05,390
en alles wat aan die regterkant is groter.

920
01:11:05,390 --> 01:11:09,590
So, wat is ons toestand gaan om hier te wees - of, wat gaan ons doen?

921
01:11:09,590 --> 01:11:11,840
[Student, onverstaanbaar] >> Ja.

922
01:11:11,840 --> 01:11:17,400
Return bevat (waarde, boom-> links)

923
01:11:17,400 --> 01:11:26,860
of bevat (waarde, boom-> regs). En dit is dit.

924
01:11:26,860 --> 01:11:29,080
En let op daar is 'n kortsluiting evaluering,

925
01:11:29,080 --> 01:11:32,520
waar as ons gebeur om die waarde te vind in die linker boom,

926
01:11:32,520 --> 01:11:36,820
ons nooit nodig om te kyk na die regte boom.

927
01:11:36,820 --> 01:11:40,430
Dit is die hele funksie.

928
01:11:40,430 --> 01:11:43,690
Nou kom ons doen dit iteratief,

929
01:11:43,690 --> 01:11:48,060
wat minder lekker gaan wees.

930
01:11:48,060 --> 01:11:54,750
Ons neem die gewone begin van node * huidig ​​= boom.

931
01:11:54,750 --> 01:12:03,250
Terwyl (huidige = NULL!).

932
01:12:03,250 --> 01:12:08,600
Vinnig gaan om 'n probleem op te sien.

933
01:12:08,600 --> 01:12:12,250
As die huidige - hier, as ons ooit te breek uit hierdie,

934
01:12:12,250 --> 01:12:16,020
dan het ons hardloop uit van die dinge om na te kyk, so vals terugkeer.

935
01:12:16,020 --> 01:12:24,810
As (huidige> waarde == waarde), return true.

936
01:12:24,810 --> 01:12:32,910
En nou, ons is op 'n plek -

937
01:12:32,910 --> 01:12:36,250
ons weet nie of ons wil om links of regs te gaan.

938
01:12:36,250 --> 01:12:44,590
So arbitrêr, laat ons net gaan jy links.

939
01:12:44,590 --> 01:12:47,910
Ek het natuurlik loop in 'n kwessie waar ek heeltemal alles verlaat -

940
01:12:47,910 --> 01:12:50,760
Sal ek ooit net so die linkerkant van 'n boom.

941
01:12:50,760 --> 01:12:56,050
Ek sal nooit so enigiets wat is 'n regte kind van enigiets.

942
01:12:56,050 --> 01:13:00,910
Hoe kan ek dit regmaak?

943
01:13:00,910 --> 01:13:05,260
[Studente] Jy het die spoor van die links en regs te hou in 'n stapel.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Ja. So laat ons maak dit

945
01:13:13,710 --> 01:13:32,360
struct lys, node * n, en dan node ** volgende?

946
01:13:32,360 --> 01:13:40,240
Ek dink wat goed werk.

947
01:13:40,240 --> 01:13:45,940
Ons wil om te gaan oor die linker-of let's hier.

948
01:13:45,940 --> 01:13:54,350
Struct Lys =, sal dit begin

949
01:13:54,350 --> 01:13:58,170
uit op hierdie struct lys.

950
01:13:58,170 --> 01:14:04,040
* Lys = null. So wat gaan ons geskakelde lys

951
01:14:04,040 --> 01:14:08,430
van subtrees dat ons het oorgeslaan oor.

952
01:14:08,430 --> 01:14:13,800
Ons gaan om te deurkruis nou links,

953
01:14:13,800 --> 01:14:17,870
maar omdat ons noodwendig nodig het om terug te kom na regs,

954
01:14:17,870 --> 01:14:26,140
Ons gaan die regterkant binne te hou van ons struct lys.

955
01:14:26,140 --> 01:14:32,620
Dan sal ons new_list of struct,

956
01:14:32,620 --> 01:14:41,080
struct lys *, new_list = malloc (sizeof (list)).

957
01:14:41,080 --> 01:14:44,920
Ek gaan om te ignoreer foute te kontroleer dat nie, maar jy moet nagaan om te sien as dit null.

958
01:14:44,920 --> 01:14:50,540
New_list die knoop dit gaan om te wys -

959
01:14:50,540 --> 01:14:56,890
oh, wat is die rede waarom ek wou dit hier. Dit gaan om te verwys na 'n tweede struct lys.

960
01:14:56,890 --> 01:15:02,380
Dit is net hoe geskakelde lyste werk.

961
01:15:02,380 --> 01:15:04,810
Dit is dieselfde as 'n int geskakelde lys

962
01:15:04,810 --> 01:15:06,960
behalwe ons net die vervanging van int met node *.

963
01:15:06,960 --> 01:15:11,040
Dit is presies dieselfde.

964
01:15:11,040 --> 01:15:15,100
So new_list, die waarde van ons new_list node,

965
01:15:15,100 --> 01:15:19,120
gaan word huidig-> reg.

966
01:15:19,120 --> 01:15:24,280
Die waarde van ons new_list-> Volgende gaan ons oorspronklike lys,

967
01:15:24,280 --> 01:15:30,760
en dan gaan ons ons lys by te werk om te verwys na new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nou moet ons 'n soort van manier van trek dinge,

969
01:15:33,650 --> 01:15:37,020
soos ons gekruis die hele linker boomstruktuur inskuif nie.

970
01:15:37,020 --> 01:15:40,480
Nou het ons nodig het om goed te trek uit dit,

971
01:15:40,480 --> 01:15:43,850
soos die huidige, is van nul, ons wil nie net return false.

972
01:15:43,850 --> 01:15:50,370
Ons wil nou buite trek by ons nuwe lys.

973
01:15:50,370 --> 01:15:53,690
'N maklike manier om dit te doen - goed, eintlik, is daar verskeie maniere om dit te doen.

974
01:15:53,690 --> 01:15:56,680
Enigiemand het 'n voorstel?

975
01:15:56,680 --> 01:15:58,790
Waar moet ek doen of hoe ek moet dit doen?

976
01:15:58,790 --> 01:16:08,010
Ons het net 'n paar minute, maar enige voorstelle?

977
01:16:08,010 --> 01:16:14,750
In plaas van een manier, in plaas van ons toestand terwyl

978
01:16:14,750 --> 01:16:17,090
wat ons tans op soek is nie null,

979
01:16:17,090 --> 01:16:22,340
plaas ons gaan om voort te gaan om te gaan totdat ons lys self, is van nul.

980
01:16:22,340 --> 01:16:25,680
So as ons lys eindig 'null,

981
01:16:25,680 --> 01:16:30,680
dan het ons hardloop uit van die dinge om na te kyk, om te soek oor.

982
01:16:30,680 --> 01:16:39,860
Maar dit beteken dat die eerste ding wat in ons lys is net gaan om die eerste nodus.

983
01:16:39,860 --> 01:16:49,730
Die heel eerste ding sal wees - ons nie meer nodig om te sien dat.

984
01:16:49,730 --> 01:16:58,710
So lys> n sal vir ons 'n boom wees.

985
01:16:58,710 --> 01:17:02,860
lys-> Volgende gaan wees null.

986
01:17:02,860 --> 01:17:07,580
En nou, terwyl die lys is nie gelyk aan nul.

987
01:17:07,580 --> 01:17:11,610
Cur gaan om iets te trek uit ons lys.

988
01:17:11,610 --> 01:17:13,500
So huidige gaan op gelyke lys-> n.

989
01:17:13,500 --> 01:17:20,850
En dan lys gaan op gelyke lys-> n, of lys-> Volgende.

990
01:17:20,850 --> 01:17:23,480
So as die huidige waarde gelyk is aan die waarde.

991
01:17:23,480 --> 01:17:28,790
Nou kan ons voeg ons albei reg wyser en ons links wyser

992
01:17:28,790 --> 01:17:32,900
so lank as wat hulle is nie null.

993
01:17:32,900 --> 01:17:36,390
Hier onder, ek dink ons ​​moet gedoen het nie in die eerste plek.

994
01:17:36,390 --> 01:17:44,080
As (huidige> regs = null)

995
01:17:44,080 --> 01:17:56,380
dan gaan ons dat die node in ons lys te voeg.

996
01:17:56,380 --> 01:17:59,290
As (huidig-> links), dit is 'n bietjie ekstra werk, maar dit is goed.

997
01:17:59,290 --> 01:18:02,690
As (huidig-> links = null),

998
01:18:02,690 --> 01:18:14,310
en ons gaan die linkerkant in ons geskakelde lys te voeg,

999
01:18:14,310 --> 01:18:19,700
en dat moet dit.

1000
01:18:19,700 --> 01:18:22,670
Ons itereer - so lank as wat ons iets in ons lys,

1001
01:18:22,670 --> 01:18:26,640
ons het 'n ander node om na te kyk.

1002
01:18:26,640 --> 01:18:28,920
So ons kyk op daardie node,

1003
01:18:28,920 --> 01:18:31,390
ons ons lys bevorder na die volgende een.

1004
01:18:31,390 --> 01:18:34,060
As dit node is die waarde wat ons is op soek na, kan ons terugkeer waar.

1005
01:18:34,060 --> 01:18:37,640
Anders voeg beide ons links en regs subtrees,

1006
01:18:37,640 --> 01:18:40,510
so lank as wat hulle is nie null, in ons lys

1007
01:18:40,510 --> 01:18:43,120
sodat ons onvermydelik gaan oor hulle.

1008
01:18:43,120 --> 01:18:45,160
So as hulle nie null,

1009
01:18:45,160 --> 01:18:47,950
as ons wortel wyser wys na twee dinge,

1010
01:18:47,950 --> 01:18:51,670
dan op die eerste het ons getrek iets uit sodat ons lys eindig 'null.

1011
01:18:51,670 --> 01:18:56,890
En dan het ons twee dinge terug in, so nou is ons lys van grootte 2.

1012
01:18:56,890 --> 01:19:00,030
Daarna het ons gaan loop back-up en ons net gaan om te trek,

1013
01:19:00,030 --> 01:19:04,250
laat ons sê, die linker-wyser van ons wortel node.

1014
01:19:04,250 --> 01:19:07,730
En dit sal net hou gebeur, sal ons opeindig herhaling oor alles.

1015
01:19:07,730 --> 01:19:11,280
>> Let daarop dat hierdie was aansienlik meer ingewikkeld

1016
01:19:11,280 --> 01:19:14,160
in die rekursiewe oplossing.

1017
01:19:14,160 --> 01:19:17,260
En ek het gesê verskeie kere

1018
01:19:17,260 --> 01:19:25,120
dat die rekursiewe oplossing het gewoonlik baie in gemeen met die iteratiewe oplossing.

1019
01:19:25,120 --> 01:19:30,820
Hier is dit presies wat die rekursiewe oplossing is doen.

1020
01:19:30,820 --> 01:19:36,740
Die enigste verandering is dat in plaas van implisiet gebruik van die stapel, die program stapel,

1021
01:19:36,740 --> 01:19:40,840
as jou manier van die dop van wat nodes jy nog steeds nodig om te besoek,

1022
01:19:40,840 --> 01:19:45,430
nou het jy 'n geskakelde lys te gebruik uitdruklik.

1023
01:19:45,430 --> 01:19:49,070
In beide gevalle sal jy die dop van watter node nog gedoen moet word besoek.

1024
01:19:49,070 --> 01:19:51,790
In die rekursiewe geval is dit is net makliker omdat 'n stapel

1025
01:19:51,790 --> 01:19:57,100
geïmplementeer word vir jou as die program stapel.

1026
01:19:57,100 --> 01:19:59,550
Let daarop dat hierdie geskakelde lys, is dit 'n stapel.

1027
01:19:59,550 --> 01:20:01,580
Wat ons ook al net op die stapel

1028
01:20:01,580 --> 01:20:09,960
onmiddellik wat ons gaan om af te trek die stapel na die volgende besoek.

1029
01:20:09,960 --> 01:20:14,380
Ons is uit die tyd, maar enige vrae?

1030
01:20:14,380 --> 01:20:23,530
[Student, onverstaanbaar]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Ja. So as ons ons geskakelde lys,

1032
01:20:27,790 --> 01:20:30,150
stroom gaan om te verwys na hierdie man,

1033
01:20:30,150 --> 01:20:34,690
en nou is ons is net die bevordering van ons geskakelde lys om te fokus op hierdie man.

1034
01:20:34,690 --> 01:20:44,200
Ons kameelkoei oor die geskakelde lys in daardie lyn.

1035
01:20:44,200 --> 01:20:51,200
En dan dink ek ons ​​moet ons geskakelde lys en stuff bevry

1036
01:20:51,200 --> 01:20:53,880
een keer voordat hy terugkeer waar of vals is, moet ons

1037
01:20:53,880 --> 01:20:57,360
itereer oor ons geskakelde lys en altyd af hier, dink ek,

1038
01:20:57,360 --> 01:21:03,900
as ons huidige reg is nie gelyk aan, voeg dit, so nou wil ons bevry

1039
01:21:03,900 --> 01:21:09,600
huidige omdat, goed, ons het heeltemal vergeet van die lys? Ja.

1040
01:21:09,600 --> 01:21:12,880
So dit is wat ons hier wil doen.

1041
01:21:12,880 --> 01:21:16,730
Waar is die wyser?

1042
01:21:16,730 --> 01:21:23,320
Cur was toe - ons wil na 'n struct lys * 10 is gelyk aan lys langs.

1043
01:21:23,320 --> 01:21:29,240
Gratis lys, lys = temp.

1044
01:21:29,240 --> 01:21:32,820
En in die geval waar ons terug waar is, het ons nodig het om te itereer

1045
01:21:32,820 --> 01:21:37,050
oor die res van ons geskakelde lys bevry dinge.

1046
01:21:37,050 --> 01:21:39,700
Die nice ding oor die rekursiewe oplossing is bevry dinge

1047
01:21:39,700 --> 01:21:44,930
beteken net knal factorings van die stapel af wat vir jou sal gebeur.

1048
01:21:44,930 --> 01:21:50,720
Dus het ons van iets wat is soos 3 lyne van harde-tot-dink-oor-kode gegaan

1049
01:21:50,720 --> 01:21:57,520
iets wat aansienlik baie meer hard-to-dink-oor reëls van die kode.

1050
01:21:57,520 --> 01:22:00,620
Nog meer vrae?

1051
01:22:00,620 --> 01:22:08,760
Alles reg. Ons is goed. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]