1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Deel 7: Meer Comfortabele]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard University]

3
00:00:05,090 --> 00:00:07,930
[Dit is CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Oke. Dus zoals ik al zei in mijn e-mail,

5
00:00:10,110 --> 00:00:14,060
Dit wordt een binaire boom intensief sectie.

6
00:00:14,060 --> 00:00:16,820
Maar er zijn niet zo veel vragen.

7
00:00:16,820 --> 00:00:18,920
Dus we gaan proberen en uit te trekken elke vraag

8
00:00:18,920 --> 00:00:25,430
en ga in pijnlijke details van de beste manieren om dingen te doen.

9
00:00:25,430 --> 00:00:31,200
Dus meteen aan het begin, we gaan door monster tekeningen van binaire bomen en zo.

10
00:00:31,200 --> 00:00:35,970
Dus hier, "Vergeet niet dat een binaire boom knooppunten vergelijkbaar met die van een gekoppelde lijst heeft,

11
00:00:35,970 --> 00:00:38,150
behalve in plaats van een wijzer zijn er twee: een voor 'kind' van de linker

12
00:00:38,150 --> 00:00:41,950
en een voor het rechter 'kind'. "

13
00:00:41,950 --> 00:00:45,630
Dus een binaire boom is net als een gelinkte lijst,

14
00:00:45,630 --> 00:00:47,910
met uitzondering van de struct gaat om twee pointers hebben.

15
00:00:47,910 --> 00:00:51,390
Er is trinary bomen, die zullen drie wijzers hebben,

16
00:00:51,390 --> 00:00:56,540
er zijn N-aire bomen, die gewoon een generieke pointer

17
00:00:56,540 --> 00:01:00,320
dat dan moet je malloc groot genoeg om

18
00:01:00,320 --> 00:01:04,840
genoeg verwijzingen naar alle mogelijke kinderen.

19
00:01:04,840 --> 00:01:08,200
Dus binaire boom toevallig een constant aantal van twee.

20
00:01:08,200 --> 00:01:11,260
Als je wilt, kun je een gelinkte lijst als een unaire boom,

21
00:01:11,260 --> 00:01:15,360
maar ik denk niet dat iemand noemt het dat.

22
00:01:15,360 --> 00:01:18,060
"Teken een dozen-en-pijlen diagram van een binaire boom knooppunt

23
00:01:18,060 --> 00:01:24,110
met favoriete nummer Nate's, 7, waar elk kind pointer nul is. "

24
00:01:24,110 --> 00:01:27,780
Dus iPad-modus.

25
00:01:27,780 --> 00:01:30,280
>> Het zal behoorlijk eenvoudig.

26
00:01:30,280 --> 00:01:36,150
We gaan gewoon naar een knooppunt heb, zal ik tekenen als een vierkant.

27
00:01:36,150 --> 00:01:38,730
En ik zal de aandacht van de waarden in hier.

28
00:01:38,730 --> 00:01:41,090
Dus de waarde moet hierin,

29
00:01:41,090 --> 00:01:44,770
en hier beneden we de linker aanwijzer links en rechts pointer rechts.

30
00:01:44,770 --> 00:01:50,430
En het is heel erg zelfs conventie noem het links en rechts, de aanwijzer namen.

31
00:01:50,430 --> 00:01:52,460
Beide zullen worden null.

32
00:01:52,460 --> 00:01:57,870
Dat is gewoon zal nul zijn, en dat zal gewoon null zijn.

33
00:01:57,870 --> 00:02:03,630
Oke. Dus terug naar hier.

34
00:02:03,630 --> 00:02:05,700
"Met een gekoppelde lijst, we moesten een pointer op te slaan

35
00:02:05,700 --> 00:02:09,639
het eerste knooppunt in de lijst om het geheel gekoppelde lijst of de hele lijst onthouden.

36
00:02:09,639 --> 00:02:11,650
Ook met bomen, we hoeven alleen maar een pointer op te slaan

37
00:02:11,650 --> 00:02:13,420
een knooppunt om de hele boom herinneren.

38
00:02:13,420 --> 00:02:15,980
Dit knooppunt is calle de 'root' van de boom.

39
00:02:15,980 --> 00:02:18,320
Voort te bouwen op uw diagram van voor of teken een nieuwe

40
00:02:18,320 --> 00:02:21,690
zo dat je een dozen-en-pijlen afbeelding van een binaire boom hebben

41
00:02:21,690 --> 00:02:25,730
met de waarde 7 dan 3 in de linker,

42
00:02:25,730 --> 00:02:32,760
daarna 9 rechts en vervolgens 6 rechts van de 3 '.

43
00:02:32,760 --> 00:02:34,810
Laten we eens kijken of ik kan dat allemaal niet vergeten in mijn hoofd.

44
00:02:34,810 --> 00:02:37,670
Dus dit gaat onze wortels hier zijn.

45
00:02:37,670 --> 00:02:41,600
We hebben een aantal aanwijzer ergens, iets wat we noemen wortel,

46
00:02:41,600 --> 00:02:45,140
en het is te wijzen op deze kerel.

47
00:02:45,140 --> 00:02:48,490
Nu om een ​​nieuw knooppunt te maken,

48
00:02:48,490 --> 00:02:52,870
wat hebben we, 3 aan de linkerkant?

49
00:02:52,870 --> 00:02:57,140
Zodat een nieuw knooppunt met 3 en aanvankelijk wijst null.

50
00:02:57,140 --> 00:02:59,190
Ik leg N.

51
00:02:59,190 --> 00:03:02,250
Nu willen we dat gaan aan de linkerkant van 7.

52
00:03:02,250 --> 00:03:06,840
Dus we veranderen pointer naar nu wijzen op deze kerel.

53
00:03:06,840 --> 00:03:12,420
En we doen hetzelfde. We willen een 9 hier

54
00:03:12,420 --> 00:03:14,620
die in eerste instantie gewoon zegt null.

55
00:03:14,620 --> 00:03:19,600
We gaan deze pointer, punt wijzigen tot en met 9,

56
00:03:19,600 --> 00:03:23,310
en nu willen we tot en met 6 maken aan het recht van 3.

57
00:03:23,310 --> 00:03:32,170
Dus het gaat om - een 6.

58
00:03:32,170 --> 00:03:34,310
En die man zal wijzen daar.

59
00:03:34,310 --> 00:03:38,320
Oke. Dus dat is alles wat het ons vraagt.

60
00:03:38,320 --> 00:03:42,770
>> Laten we nu gaan over een aantal terminologie.

61
00:03:42,770 --> 00:03:46,690
We hebben al gesproken over hoe de wortel van de boom is de bovenste knoop in de boom.

62
00:03:46,690 --> 00:03:54,720
Degene met 7. De knooppunten aan de onderkant van de boom worden genoemd de bladeren.

63
00:03:54,720 --> 00:04:01,240
Elke node die net heeft null als kinderen is een blad.

64
00:04:01,240 --> 00:04:03,680
Zo is het mogelijk, als onze binaire boom is slechts een knooppunt,

65
00:04:03,680 --> 00:04:10,130
dat een boom is een blad, en dat is het.

66
00:04:10,130 --> 00:04:12,060
"De 'hoogte' van de boom is het aantal hops die je moet maken

67
00:04:12,060 --> 00:04:16,620
te krijgen van de top tot een blad. "

68
00:04:16,620 --> 00:04:18,640
We krijgen in, in een tweede, het verschil

69
00:04:18,640 --> 00:04:21,940
tussen gebalanceerde en ongebalanceerde binaire bomen,

70
00:04:21,940 --> 00:04:29,470
maar voor nu, de totale hoogte van deze boom

71
00:04:29,470 --> 00:04:34,520
Ik zou zeggen is 3, maar als je telt het aantal hops

72
00:04:34,520 --> 00:04:39,710
die je moet maken om te krijgen tot 9, dan is het eigenlijk alleen maar een hoogte van 2.

73
00:04:39,710 --> 00:04:43,340
Op dit moment is dit een onevenwichtige binaire boom,

74
00:04:43,340 --> 00:04:49,840
maar we zullen het over een evenwichtige wanneer het wordt relevant te zijn.

75
00:04:49,840 --> 00:04:52,040
Dus nu kunnen we praten over knopen in een boom in termen

76
00:04:52,040 --> 00:04:54,700
opzichte van de andere knooppunten in de boom.

77
00:04:54,700 --> 00:04:59,730
Dus nu hebben we ouders, kinderen, broers en zussen, voorouders en nakomelingen.

78
00:04:59,730 --> 00:05:05,650
Ze zijn redelijk gezond verstand, wat ze betekenen.

79
00:05:05,650 --> 00:05:09,610
Als we vragen - het is ouders.

80
00:05:09,610 --> 00:05:12,830
Dus wat is de moedermaatschappij van 3?

81
00:05:12,830 --> 00:05:16,090
[Studenten] 7. >> Ja. De ouder wordt gewoon gaat worden welke punten voor jou.

82
00:05:16,090 --> 00:05:20,510
En wat zijn de kinderen van 7?

83
00:05:20,510 --> 00:05:23,860
[Studenten] 3 en 9. >> Ja.

84
00:05:23,860 --> 00:05:26,460
Merk op dat "kinderen" letterlijk kinderen betekent,

85
00:05:26,460 --> 00:05:31,010
dus 6 niet van toepassing, want het is net een kleinkind.

86
00:05:31,010 --> 00:05:35,540
Maar dan als we nakomelingen, dus wat zijn de afstammelingen van 7?

87
00:05:35,540 --> 00:05:37,500
[Studenten] 3, 6 en 9. >> Ja.

88
00:05:37,500 --> 00:05:42,330
De afstammelingen van de wortel gaat alles in de boom,

89
00:05:42,330 --> 00:05:47,950
behalve misschien de root node zelf, als je niet wilt dat een afstammeling te overwegen.

90
00:05:47,950 --> 00:05:50,750
En tot slot, voorouders, dus het is de tegenovergestelde richting.

91
00:05:50,750 --> 00:05:55,740
Dus wat zijn de voorouders van 6?

92
00:05:55,740 --> 00:05:58,920
[Studenten] 3 en 7. >> Ja. 9 is niet inbegrepen.

93
00:05:58,920 --> 00:06:02,520
Het is gewoon de directe afstamming terug naar de wortel

94
00:06:02,520 --> 00:06:13,230
gaat worden uw voorouders.

95
00:06:13,230 --> 00:06:16,300
>> "We zeggen dat een binaire boom is 'besteld' als voor elk knooppunt in de boom,

96
00:06:16,300 --> 00:06:19,530
al zijn nakomelingen links hebben minder waarden

97
00:06:19,530 --> 00:06:22,890
en alle aan de juiste hebben hogere waarden.

98
00:06:22,890 --> 00:06:27,060
Zo wordt de boom boven besteld worden maar het is niet de enige mogelijke geordende. "

99
00:06:27,060 --> 00:06:30,180
Voordat we naar die,

100
00:06:30,180 --> 00:06:36,420
een geordende binaire boom wordt ook wel een binaire zoekboom.

101
00:06:36,420 --> 00:06:38,660
Hier hebben we toevallig noemde het een geordende binaire boom,

102
00:06:38,660 --> 00:06:41,850
maar ik heb nooit gehoord dat het wel een geordende binaire boom voor,

103
00:06:41,850 --> 00:06:46,650
en op een quiz zijn we veel meer kans om binaire zoekboom te zetten.

104
00:06:46,650 --> 00:06:49,250
Ze zijn een en dezelfde,

105
00:06:49,250 --> 00:06:54,580
en het is belangrijk dat u herkent het onderscheid tussen binaire boom en binaire zoekboom.

106
00:06:54,580 --> 00:06:58,830
Een binaire boom is slechts een boom die naar twee dingen.

107
00:06:58,830 --> 00:07:02,120
Elk knooppunt wijst op twee dingen.

108
00:07:02,120 --> 00:07:06,310
Er is geen redenering over de waarden die het verwijst.

109
00:07:06,310 --> 00:07:11,370
Dus hier graag over, want het is een binaire zoekboom,

110
00:07:11,370 --> 00:07:14,030
We weten dat als we naar links van 7,

111
00:07:14,030 --> 00:07:16,670
dan alle waarden die we kunnen eventueel bereiken

112
00:07:16,670 --> 00:07:19,310
door naar links 7 hebben minder dan 7.

113
00:07:19,310 --> 00:07:24,070
Merk op dat alle waarden lager dan 7 zijn 3 en 6.

114
00:07:24,070 --> 00:07:26,040
Deze zijn links van 7.

115
00:07:26,040 --> 00:07:29,020
Als we naar rechts van 7, alles groter dan 7,

116
00:07:29,020 --> 00:07:33,220
dus 9 is aan de rechterkant van 7, dus we zijn goed.

117
00:07:33,220 --> 00:07:36,150
Dit is niet het geval voor een binaire boom,

118
00:07:36,150 --> 00:07:40,020
een regelmatige binaire boom we gewoon 3 boven, 7 naar links,

119
00:07:40,020 --> 00:07:47,630
9 links van 7, er is geen volgorde van waarden dan ook.

120
00:07:47,630 --> 00:07:56,140
Nu zullen we niet echt doen, want het is vervelend en onnodig,

121
00:07:56,140 --> 00:07:59,400
maar "proberen om zo veel besteld bomen trekken als je maar kunt bedenken

122
00:07:59,400 --> 00:08:01,900
met de cijfers 7, 3, 9 en 6.

123
00:08:01,900 --> 00:08:06,800
Hoeveel verschillende regelingen zijn er? Wat is de hoogte van elke? "

124
00:08:06,800 --> 00:08:10,480
>> We doen een paar, maar het belangrijkste idee is,

125
00:08:10,480 --> 00:08:16,530
dit is geenszins een unieke representatie van een binaire boom die deze waarden.

126
00:08:16,530 --> 00:08:22,760
Alles wat we nodig hebben is een aantal binaire boom die 7 bevat, 3, 6, en 9.

127
00:08:22,760 --> 00:08:25,960
Een andere mogelijke geldig zou zijn de wortel is 3,

128
00:08:25,960 --> 00:08:30,260
naar links en het is 6 naar links en het is 7,

129
00:08:30,260 --> 00:08:32,730
naar links en het is 9.

130
00:08:32,730 --> 00:08:36,169
Dat is een volkomen geldige binaire zoekboom.

131
00:08:36,169 --> 00:08:39,570
Het is niet erg behulpzaam, want het is net als een gekoppelde lijst

132
00:08:39,570 --> 00:08:43,750
en al deze pointers zijn gewoon null.

133
00:08:43,750 --> 00:08:48,900
Maar het is geldig boom. Ja?

134
00:08:48,900 --> 00:08:51,310
[Student] Niet de waarden groter te zijn aan de rechterkant?

135
00:08:51,310 --> 00:08:56,700
Of is dit -? >> Deze bedoelde ik de andere kant op te gaan.

136
00:08:56,700 --> 00:09:00,960
Er is ook - ja, laten we wisselen dat.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Goede vangst.

138
00:09:07,770 --> 00:09:11,730
Het heeft nog steeds te gehoorzamen wat een binaire boom zoekopdracht verondersteld wordt te doen.

139
00:09:11,730 --> 00:09:15,650
Dus alles naar links moet minder dan een bepaald knooppunt.

140
00:09:15,650 --> 00:09:23,180
We konden gewoon bewegen, zeggen, dit 6 en hier zet het.

141
00:09:23,180 --> 00:09:26,880
Nee, dat kunnen we niet. Waarom moet ik blijven doen?

142
00:09:26,880 --> 00:09:35,350
Laten we het doen - hier is 6, hier is 7, 6 punten 3.

143
00:09:35,350 --> 00:09:39,290
Dit is nog steeds een geldige binaire zoekboom.

144
00:09:39,290 --> 00:09:49,260
Wat is er mis als ik - laten we eens kijken of ik kan komen met een regeling.

145
00:09:49,260 --> 00:09:52,280
Ja, oke. Dus wat is er mis met deze boom?

146
00:09:52,280 --> 00:10:08,920
Ik denk dat ik heb al gegeven je een hint dat er iets mis mee is.

147
00:10:08,920 --> 00:10:14,430
Waarom moet ik blijven doen?

148
00:10:14,430 --> 00:10:18,510
Oke. Dit ziet er redelijk.

149
00:10:18,510 --> 00:10:22,590
Als we kijken naar elk knooppunt, zoals 7, dan naar links 7 is 3.

150
00:10:22,590 --> 00:10:24,960
Dus we 3 hebben, het ding aan de rechterkant van 3 is een 6.

151
00:10:24,960 --> 00:10:27,750
En als je kijkt naar 6, het ding aan de rechterkant van 6 is een 9.

152
00:10:27,750 --> 00:10:30,910
Dus waarom is dit geen geldige binaire zoekboom?

153
00:10:30,910 --> 00:10:36,330
[Studenten] 9 nog links van 7. >> Ja.

154
00:10:36,330 --> 00:10:43,710
Het moet zo dat alle waarden kan eventueel bereiken door naar links van 7 minder dan 7.

155
00:10:43,710 --> 00:10:49,120
Als we naar links van 7 komen we bij 3 en we kunnen nog steeds tot 6,

156
00:10:49,120 --> 00:10:52,520
we kunnen nog steeds tot 9, maar door zijn gegaan minder dan 7,

157
00:10:52,520 --> 00:10:55,070
we niet in staat om naar een getal dat groter is dan 7.

158
00:10:55,070 --> 00:10:59,830
Dus dit is geen geldige binaire zoekboom.

159
00:10:59,830 --> 00:11:02,330
>> Mijn broer had eigenlijk een interview vraag

160
00:11:02,330 --> 00:11:07,760
dat in principe was dit, net code iets om te valideren

161
00:11:07,760 --> 00:11:10,500
of een boom is een binaire zoekboom,

162
00:11:10,500 --> 00:11:13,580
en dus het eerste wat hij deed was gewoon controleren om te zien

163
00:11:13,580 --> 00:11:17,020
als de linker en rechter juist zijn, en dan is er iterate beneden.

164
00:11:17,020 --> 00:11:19,700
Maar je kunt niet zomaar doen, je moet bijhouden

165
00:11:19,700 --> 00:11:22,550
van het feit dat nu ik ben gegaan links van 7,

166
00:11:22,550 --> 00:11:26,340
alles in deze substructuur moet lager zijn dan 7.

167
00:11:26,340 --> 00:11:28,430
De juiste algoritme moet bijhouden

168
00:11:28,430 --> 00:11:35,970
van de grenzen die de waarden eventueel kan vallen binnen

169
00:11:35,970 --> 00:11:38,360
We zullen niet gaan door alle van hen.

170
00:11:38,360 --> 00:11:41,630
Er is een mooi herhaling relatie,

171
00:11:41,630 --> 00:11:44,810
hoewel we nog niet gekregen om deze, of zullen we niet krijgen op die,

172
00:11:44,810 --> 00:11:47,030
het definiëren van hoeveel het er zijn.

173
00:11:47,030 --> 00:11:53,180
Er zijn 14 daarvan.

174
00:11:53,180 --> 00:11:56,020
Het idee van hoe je het zou doen is het wiskundig als,

175
00:11:56,020 --> 00:11:59,770
u kunt kiezen uit een willekeurige enkele ene naar de root node zijn,

176
00:11:59,770 --> 00:12:03,160
en dan als ik kies 7 tot en met de root-node zijn,

177
00:12:03,160 --> 00:12:08,150
dan zijn er, laten we zeggen, een aantal nummers die kunnen gaan worden mijn linker knooppunt,

178
00:12:08,150 --> 00:12:10,440
en er zijn een aantal nummers die kunnen mijn rechter knooppunt te zijn,

179
00:12:10,440 --> 00:12:15,090
maar als ik heb n totale aantallen, dan is het bedrag dat kan naar links

180
00:12:15,090 --> 00:12:18,820
vermeerderd met het bedrag dat u naar de juiste is n - 1.

181
00:12:18,820 --> 00:12:26,130
Zodat de overige getallen, ze kunnen ofwel naar links of rechts.

182
00:12:26,130 --> 00:12:31,580
Het lijkt moeilijk, dat, als ik 3 dan eerst alles moet gaan naar links,

183
00:12:31,580 --> 00:12:35,080
maar als ik 7 zet, dan sommige dingen kunnen gaan het de linker-en sommige dingen kunnen gaan naar rechts.

184
00:12:35,080 --> 00:12:39,570
En door '3 eerste 'Ik meende alles wat kan gaan naar rechts.

185
00:12:39,570 --> 00:12:42,350
Het is echt, je moet gewoon zo denken,

186
00:12:42,350 --> 00:12:47,980
hoeveel dingen kunnen gaan op het volgende niveau van de boom.

187
00:12:47,980 --> 00:12:50,420
En het komt te zijn 14, of u kunt tekenen ze allemaal,

188
00:12:50,420 --> 00:12:54,650
en dan krijg je 14.

189
00:12:54,650 --> 00:13:01,120
>> Terug te gaan hier,

190
00:13:01,120 --> 00:13:03,510
"Geordende binaire bomen zijn cool, want we kunnen zoeken door hen

191
00:13:03,510 --> 00:13:06,910
in een zeer vergelijkbare manier om te zoeken op een gesorteerde array.

192
00:13:06,910 --> 00:13:10,120
Om dit te doen, we beginnen bij de wortel en werken onze weg naar beneden de boom

193
00:13:10,120 --> 00:13:13,440
in de richting van bladeren, het controleren van elk knooppunt van de waarden ten opzichte van de waarden die wij zoekt.

194
00:13:13,440 --> 00:13:15,810
Als de huidige knooppunt lager is dan de waarde die we zoeken,

195
00:13:15,810 --> 00:13:18,050
ga je naast het knooppunt juiste kind.

196
00:13:18,050 --> 00:13:20,030
Anders, ga je naar de linkerkant van de node kind.

197
00:13:20,030 --> 00:13:22,800
Op een gegeven moment, zult u vinden, hetzij de waarde die u zoekt, of kom je in een null,

198
00:13:22,800 --> 00:13:28,520
met vermelding van de waarde is niet in de boom. "

199
00:13:28,520 --> 00:13:32,450
Ik moet de boom hadden we eerder opnieuw te tekenen, dat duurt een seconde.

200
00:13:32,450 --> 00:13:38,280
Maar we willen opzoeken of 6, 10, en 1 in de boom.

201
00:13:38,280 --> 00:13:49,180
Dus wat was, 7, 9, 3, 6. Oke.

202
00:13:49,180 --> 00:13:52,730
De nummers die u wilt opzoeken, we willen kijken met 6.

203
00:13:52,730 --> 00:13:55,440
Hoe werkt dit algoritme zijn werk?

204
00:13:55,440 --> 00:14:03,040
Nou, we hebben ook een aantal wortel pointer naar onze boom.

205
00:14:03,040 --> 00:14:12,460
En we zouden gaan naar de wortel en zeggen: is deze waarde gelijk aan de waarde die we zoekt?

206
00:14:12,460 --> 00:14:15,000
Dus we zijn op zoek naar 6, dus het is niet gelijk.

207
00:14:15,000 --> 00:14:20,140
Dus we blijven gaan, en nu zeggen we, oke, dus 6 is minder dan 7.

208
00:14:20,140 --> 00:14:23,940
Betekent dat dat we willen gaan naar links, of willen we naar de juiste?

209
00:14:23,940 --> 00:14:27,340
[Student] Links. >> Ja.

210
00:14:27,340 --> 00:14:33,340
Het is veel eenvoudiger, alles wat je hoeft te doen trekken een mogelijke knooppunt van de boom

211
00:14:33,340 --> 00:14:37,760
en dan moet je Niet doen - in plaats van te proberen om te denken in je hoofd,

212
00:14:37,760 --> 00:14:40,020
oke, als het minder, ga ik naar links of naar rechts,

213
00:14:40,020 --> 00:14:43,030
gewoon op zoek naar deze foto, het is heel duidelijk dat ik moet naar links

214
00:14:43,030 --> 00:14:47,700
indien dit knooppunt groter is dan de waarde die ik zoek.

215
00:14:47,700 --> 00:14:52,600
Dus ga je naar links, nu ben ik op 3.

216
00:14:52,600 --> 00:14:57,770
Ik wil - 3 kleiner is dan de waarde Ik ben op zoek naar, dat is 6.

217
00:14:57,770 --> 00:15:03,420
Dus gaan we naar rechts, en nu heb ik uiteindelijk op 6,

218
00:15:03,420 --> 00:15:07,380
Dit is de waarde Ik ben op zoek naar, dus ik terug waar.

219
00:15:07,380 --> 00:15:15,760
De volgende waarde ik ga op zoek naar is 10.

220
00:15:15,760 --> 00:15:23,230
Oke. Dus 10, nu gaat - afgesneden dat - naar de wortel te volgen.

221
00:15:23,230 --> 00:15:27,670
Nu, 10 zal groter zijn dan 7, dus ik wil kijken naar rechts.

222
00:15:27,670 --> 00:15:31,660
Ik ga hier naartoe te komen, wordt 10 zal groter zijn dan 9,

223
00:15:31,660 --> 00:15:34,520
dus ik ga naar willen kijken naar rechts.

224
00:15:34,520 --> 00:15:42,100
Ik kom hier, maar hier nu ben ik op null.

225
00:15:42,100 --> 00:15:44,170
Wat moet ik doen als ik geraakt null?

226
00:15:44,170 --> 00:15:47,440
[Student] Terug vals? >> Ja. Ik vind helemaal niet 10.

227
00:15:47,440 --> 00:15:49,800
1 wordt een vrijwel identieke geval,

228
00:15:49,800 --> 00:15:51,950
behalve dat het gewoon gaat worden omgedraaid, in plaats van naar

229
00:15:51,950 --> 00:15:56,540
aan de rechterzijde, ik ga naar beneden kijken de linkerkant.

230
00:15:56,540 --> 00:16:00,430
>> Nu denk ik dat we ook echt om te code.

231
00:16:00,430 --> 00:16:04,070
Hier is waar - het openstellen van de CS50 apparaat en er uw weg,

232
00:16:04,070 --> 00:16:07,010
maar je kunt ook gewoon doen in de ruimte.

233
00:16:07,010 --> 00:16:09,170
Het is waarschijnlijk ideaal om het te doen in de ruimte,

234
00:16:09,170 --> 00:16:13,760
want we kunnen werken in de ruimte.

235
00:16:13,760 --> 00:16:19,170
"Eerst zullen we een nieuw type definitie voor een binaire boom knooppunt met int-waarden.

236
00:16:19,170 --> 00:16:21,400
Met de standaardtekst typedef hieronder

237
00:16:21,400 --> 00:16:24,510
een nieuw type definitie van een knooppunt in een binaire boom.

238
00:16:24,510 --> 00:16:27,930
Als je vast komt te zitten. . . "Bla, bla, bla. Oke.

239
00:16:27,930 --> 00:16:30,380
Dus laten we hier zet de standaardtekst,

240
00:16:30,380 --> 00:16:41,630
typedef struct knoop en knoop. Ja, oke.

241
00:16:41,630 --> 00:16:44,270
Dus wat zijn de velden gaan we willen in ons knoop?

242
00:16:44,270 --> 00:16:46,520
[Student] Int en dan twee pointers?

243
00:16:46,520 --> 00:16:49,700
>> Int waarde, twee pointers? Hoe schrijf ik de pointers?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. >> Ik zoomen Ja, dus struct knoop * links,

245
00:16:58,440 --> 00:17:01,320
en struct knoop * rechts.

246
00:17:01,320 --> 00:17:03,460
En vergeet niet de discussie van de vorige keer,

247
00:17:03,460 --> 00:17:15,290
dat dit geen zin heeft, dit heeft geen zin,

248
00:17:15,290 --> 00:17:18,270
Dit heeft geen zin.

249
00:17:18,270 --> 00:17:25,000
Je moet alles wat er om deze recursieve struct te definiëren.

250
00:17:25,000 --> 00:17:27,970
Oke, dus dat is wat onze boom gaat zien.

251
00:17:27,970 --> 00:17:37,670
Als we een trinary boom, dan een knoop eruit zou kunnen zien b1, b2, struct knoop * b3,

252
00:17:37,670 --> 00:17:43,470
waarbij b een tak - in feite, heb ik meer gehoord links, midden, rechts, maar wat dan ook.

253
00:17:43,470 --> 00:17:55,610
We hebben alleen de zorg over binaire, dus rechts, links.

254
00:17:55,610 --> 00:17:59,110
"Nu verklaren een wereldwijde knooppunt * variabele voor de wortel van de boom."

255
00:17:59,110 --> 00:18:01,510
Dus we gaan niet om dat te doen.

256
00:18:01,510 --> 00:18:08,950
Om dingen iets moeilijker en meer algemeen,

257
00:18:08,950 --> 00:18:11,570
zullen we niet over een wereldwijde knooppunt variabele.

258
00:18:11,570 --> 00:18:16,710
In plaats daarvan, in de belangrijkste zullen we verklaren al onze knooppunt dingen,

259
00:18:16,710 --> 00:18:20,500
en dat betekent dat hieronder, als we vertoond

260
00:18:20,500 --> 00:18:23,130
onze Bevat functie en onze insert-functie,

261
00:18:23,130 --> 00:18:27,410
in plaats van onze bevat functiebouwstenen alleen met behulp van deze wereldwijde knooppunt variabele,

262
00:18:27,410 --> 00:18:34,280
we gaan om het te laten nemen als argument de boom die we willen dat het te verwerken.

263
00:18:34,280 --> 00:18:36,650
Het hebben van de globale variabele moest dingen makkelijker te maken.

264
00:18:36,650 --> 00:18:42,310
We gaan om dingen moeilijker.

265
00:18:42,310 --> 00:18:51,210
Neem nu een minuut of zo om dat te doen dit soort dingen,

266
00:18:51,210 --> 00:18:57,690
waar binnen van de belangrijkste u wilt deze boom te maken, en dat is alles wat je wilt doen.

267
00:18:57,690 --> 00:19:04,530
Probeer en de bouw van deze boom in uw belangrijkste functie.

268
00:19:42,760 --> 00:19:47,610
>> Oke. Dus je hoeft niet eens te hebben gebouwd de boom de hele weg nog niet.

269
00:19:47,610 --> 00:19:49,840
Maar iemand nog iets wat ik zou kunnen optrekken

270
00:19:49,840 --> 00:20:03,130
om te laten zien hoe men zou kunnen beginnen bouwen zoals een boom?

271
00:20:03,130 --> 00:20:08,080
[Student] Iemand bonzen, in een poging om eruit te komen.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Iedereen comfortabel met hun boom bouw?

273
00:20:13,100 --> 00:20:15,520
[Student] Tuurlijk. Het is nog niet klaar. >> Het is prima. We kunnen gewoon afmaken -

274
00:20:15,520 --> 00:20:26,860
oh, kunt u het opslaan? Hooray.

275
00:20:26,860 --> 00:20:32,020
Hier hebben we dus - oh, ik ben een beetje afgesneden.

276
00:20:32,020 --> 00:20:34,770
Ben ik ingezoomd?

277
00:20:34,770 --> 00:20:37,730
Zoom in, bladeren uit. >> Ik heb een vraag. >> Ja?

278
00:20:37,730 --> 00:20:44,410
[Student] Wanneer u struct te definiëren, zijn dingen als geïnitialiseerd iets?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Nee. >> Oke. Dus je zou moeten initialiseren -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nee Bij het definiëren, of wanneer u verklaren een struct,

281
00:20:50,450 --> 00:20:55,600
het is niet geïnitialiseerd standaard, het is net als wanneer u verklaart een int.

282
00:20:55,600 --> 00:20:59,020
Het is precies hetzelfde. Het is net als elk van de afzonderlijke velden

283
00:20:59,020 --> 00:21:04,460
kan een vuilnis waarde in. >> En is het mogelijk om te bepalen - of te verklaren een struct

284
00:21:04,460 --> 00:21:07,740
zodanig dat het wel initialiseren?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ja. Dus, snelkoppeling initialisatie syntaxis

286
00:21:13,200 --> 00:21:18,660
gaat uitzien -

287
00:21:18,660 --> 00:21:22,200
Er zijn twee manieren waarop we dit kunnen doen. Ik denk dat we het te compileren

288
00:21:22,200 --> 00:21:25,840
om ervoor te zorgen Clang ook doet.

289
00:21:25,840 --> 00:21:28,510
De volgorde van argumenten die komt in de struct,

290
00:21:28,510 --> 00:21:32,170
zet je als de volgorde van argumenten binnenkant van deze accolades.

291
00:21:32,170 --> 00:21:35,690
Dus als je wilt om het te initialiseren tot 9 en links worden nul en dan rechts nul,

292
00:21:35,690 --> 00:21:41,570
het zou 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Het alternatief is, en de editor houdt niet van deze syntaxis,

294
00:21:47,890 --> 00:21:50,300
en hij denkt dat ik wil een nieuw blok,

295
00:21:50,300 --> 00:22:01,800
maar het alternatief is zoiets als -

296
00:22:01,800 --> 00:22:04,190
hier, ik zet het op een nieuwe regel.

297
00:22:04,190 --> 00:22:09,140
U kunt expliciet zeggen, ik vergeet de exacte syntax.

298
00:22:09,140 --> 00:22:13,110
Zo kunt u expliciet aandacht besteden aan hun naam, en zeggen:

299
00:22:13,110 --> 00:22:21,570
C. Of. Waarde = 9,. Links = NULL.

300
00:22:21,570 --> 00:22:24,540
Ik gok dat deze moeten worden komma's.

301
00:22:24,540 --> 00:22:29,110
. Rechts = NULL, dus op deze manier je dat niet doet

302
00:22:29,110 --> 00:22:33,780
eigenlijk nodig om de volgorde van de struct kennen,

303
00:22:33,780 --> 00:22:36,650
en als je dit leest, het is veel explicieter

304
00:22:36,650 --> 00:22:41,920
over wat de waarde er wordt geïnitialiseerd op.

305
00:22:41,920 --> 00:22:44,080
>> Dit gebeurt als een van de dingen die -

306
00:22:44,080 --> 00:22:49,100
dus voor het grootste deel, C + + is een superset van C.

307
00:22:49,100 --> 00:22:54,160
U kunt C-code, verplaats deze naar C + +, en het moet compileren.

308
00:22:54,160 --> 00:22:59,570
Dit is een van de dingen die C + + niet ondersteunt, zodat mensen niet geneigd zijn om het te doen.

309
00:22:59,570 --> 00:23:01,850
Ik weet niet of dat is de enige reden waarom mensen de neiging om het niet te doen,

310
00:23:01,850 --> 00:23:10,540
maar de zaak waar ik moest om het te gebruiken die nodig zijn om te werken met C + + en dus kon ik niet gebruiken.

311
00:23:10,540 --> 00:23:14,000
Een ander voorbeeld van iets dat niet werkt met C + + is

312
00:23:14,000 --> 00:23:16,940
hoe malloc geeft een "void *," technisch,

313
00:23:16,940 --> 00:23:20,200
maar je kon gewoon zeggen char * x = malloc wat dan ook,

314
00:23:20,200 --> 00:23:22,840
en het zal automatisch worden geworpen om een ​​char *.

315
00:23:22,840 --> 00:23:25,450
Dat automatische cast gebeurt niet in C + +.

316
00:23:25,450 --> 00:23:28,150
Dat zou niet compileren, en je zou expliciet moeten zeggen

317
00:23:28,150 --> 00:23:34,510
char *, malloc, wat dan ook, om het te werpen naar een char *.

318
00:23:34,510 --> 00:23:37,270
Er zijn niet veel dingen die C en C + + het oneens zijn over,

319
00:23:37,270 --> 00:23:40,620
maar dat zijn twee.

320
00:23:40,620 --> 00:23:43,120
Dus we zullen gaan met deze syntax.

321
00:23:43,120 --> 00:23:46,150
Maar zelfs als we niet gaan met dat syntaxis,

322
00:23:46,150 --> 00:23:49,470
wat is - kan het mis met deze?

323
00:23:49,470 --> 00:23:52,170
[Student] Ik hoef niet te dereference het? >> Ja.

324
00:23:52,170 --> 00:23:55,110
Vergeet niet dat de pijl een impliciete dereference heeft,

325
00:23:55,110 --> 00:23:58,230
en dus als we gewoon te maken met een struct,

326
00:23:58,230 --> 00:24:04,300
we willen gebruiken. te krijgen op een veld binnenkant van de struct.

327
00:24:04,300 --> 00:24:07,200
En de enige keer dat we gebruik maken van pijl is wanneer we willen doen -

328
00:24:07,200 --> 00:24:13,450
goed pijl gelijk aan -

329
00:24:13,450 --> 00:24:17,020
dat is wat het zou betekenen als ik pijl.

330
00:24:17,020 --> 00:24:24,600
Alle pijl middelen is, dereference dit, nu ben ik in een struct, en ik kan het veld te krijgen.

331
00:24:24,600 --> 00:24:28,040
Ofwel krijgen het veld direct of dereference en krijg het veld -

332
00:24:28,040 --> 00:24:30,380
Ik denk dat dit zou moeten zijn waarde.

333
00:24:30,380 --> 00:24:33,910
Maar hier ik te maken heb met slechts een struct, niet een pointer naar een struct,

334
00:24:33,910 --> 00:24:38,780
en dus kan ik geen gebruik maken van de pijl.

335
00:24:38,780 --> 00:24:47,510
Maar dit soort dingen we kunnen doen voor alle knooppunten.

336
00:24:47,510 --> 00:24:55,790
Oh mijn 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 kunnen we het opzetten van de vestigingen in onze boom, kunnen we 7 -

339
00:25:16,470 --> 00:25:21,650
we hebben, moet de linkerkant verwijzen naar 3.

340
00:25:21,650 --> 00:25:25,130
Dus hoe doen we dat?

341
00:25:25,130 --> 00:25:29,320
[Studenten, onverstaanbaar] >> Ja. Het adres van node3,

342
00:25:29,320 --> 00:25:34,170
en als je niet-adres hebben, dan is het gewoon niet samen te stellen.

343
00:25:34,170 --> 00:25:38,190
Maar vergeet niet dat deze zijn verwijzingen naar de volgende knooppunten.

344
00:25:38,190 --> 00:25:44,930
Het recht moet verwijzen naar 9,

345
00:25:44,930 --> 00:25:53,330
en 3 moet erop rechts tot 6.

346
00:25:53,330 --> 00:25:58,480
Ik denk dat dit is helemaal klaar. Eventuele opmerkingen of vragen?

347
00:25:58,480 --> 00:26:02,060
[Student, onverstaanbaar] De wortel gaat worden 7.

348
00:26:02,060 --> 00:26:08,210
We kunnen alleen maar zeggen knooppunt * ptr =

349
00:26:08,210 --> 00:26:14,160
of wortel, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Voor onze doeleinden, gaan we te maken hebben met insert,

351
00:26:20,730 --> 00:26:25,490
dus we gaan een functie wilt invoegen in deze binaire boom schrijven

352
00:26:25,490 --> 00:26:34,230
en insert is onvermijdelijk zal malloc bellen om een ​​nieuw knooppunt voor deze boom te creëren.

353
00:26:34,230 --> 00:26:36,590
Dus dingen gaan rommelig te krijgen met het feit dat sommige knooppunten

354
00:26:36,590 --> 00:26:38,590
zijn op de stapel

355
00:26:38,590 --> 00:26:43,680
en andere knooppunten gaan om te eindigen op de heap als we invoegen.

356
00:26:43,680 --> 00:26:47,640
Dit is volkomen geldig, maar de enige reden

357
00:26:47,640 --> 00:26:49,600
zijn we in staat om dit te doen op de stapel

358
00:26:49,600 --> 00:26:51,840
is omdat het zo'n gekunstelde voorbeeld dat we kennen

359
00:26:51,840 --> 00:26:56,360
de boom moet worden uitgevoerd als 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Als we niet over dit, dan zouden we niet te malloc in de eerste plaats.

361
00:27:02,970 --> 00:27:06,160
Als we een beetje later te zien, moeten we malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Op dit moment is het volkomen redelijk om op de stapel gelegd,

363
00:27:08,570 --> 00:27:14,750
maar laten we dit te wijzigen in een malloc implementatie.

364
00:27:14,750 --> 00:27:17,160
Dus elk van deze gaat nu iets als

365
00:27:17,160 --> 00:27:24,240
knooppunt * node9 = malloc (sizeof (node)).

366
00:27:24,240 --> 00:27:28,040
En nu gaan we te hebben om ons in te checken doen.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Ik wilde niet dat -

368
00:27:34,010 --> 00:27:40,950
return 1, en dan kunnen we doen node9-> want nu is het een pointer,

369
00:27:40,950 --> 00:27:45,300
value = 6, node9-> links = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> rechts = NULL,

371
00:27:48,930 --> 00:27:51,410
en we gaan te hebben om dat te doen voor elk van deze knooppunten.

372
00:27:51,410 --> 00:27:57,490
Dus in plaats daarvan laten we binnen zet het een aparte functie.

373
00:27:57,490 --> 00:28:00,620
Laten we het knooppunt * build_node,

374
00:28:00,620 --> 00:28:09,050
en dit is enigszins vergelijkbaar met de API we voorzien Huffman codering.

375
00:28:09,050 --> 00:28:12,730
Wij geven u initializer functies voor een boom

376
00:28:12,730 --> 00:28:20,520
en Deconstructor "functies" voor die bomen en hetzelfde voor de bossen.

377
00:28:20,520 --> 00:28:22,570
>> Dus hier gaan we een initializer functie hebben

378
00:28:22,570 --> 00:28:25,170
gewoon bouwen van een knooppunt voor ons.

379
00:28:25,170 --> 00:28:29,320
En het gaat vrij veel precies hetzelfde uitzien als deze.

380
00:28:29,320 --> 00:28:32,230
En ik ben zelfs gaan worden lui en niet de naam van de variabele,

381
00:28:32,230 --> 00:28:34,380
ook al node9 heeft geen zin meer.

382
00:28:34,380 --> 00:28:38,610
Oh, ik denk dat node9 de waarde niet had mogen worden 6.

383
00:28:38,610 --> 00:28:42,800
Nu kunnen we terugkeren node9.

384
00:28:42,800 --> 00:28:49,550
En hier moeten we terug null.

385
00:28:49,550 --> 00:28:52,690
Iedereen mee eens build-a-node functie?

386
00:28:52,690 --> 00:28:59,780
Dus nu kunnen we gewoon bellen dat aan een knooppunt met een bepaalde waarde en null pointers te bouwen.

387
00:28:59,780 --> 00:29:09,750
Nu kunnen we dat noemen, kunnen we doen knooppunt * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
En laten we het 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 nu willen we het opzetten van de zelfde pointers,

391
00:29:39,330 --> 00:29:42,470
behalve nu alles is al in termen van pointers

392
00:29:42,470 --> 00:29:48,480
dus niet meer nodig het adres van.

393
00:29:48,480 --> 00:29:56,300
Oke. Dus wat is het laatste wat ik wil doen?

394
00:29:56,300 --> 00:30:03,850
Er is een fout controle dat ik niet doe.

395
00:30:03,850 --> 00:30:06,800
Wat betekent bouwen knooppunt terug?

396
00:30:06,800 --> 00:30:11,660
[Student, onverstaanbaar] >> Ja. Als malloc is mislukt, keert hij terug null.

397
00:30:11,660 --> 00:30:16,460
Dus ik ga lui zet het hier beneden in plaats van het doen van een voorwaarde voor elk.

398
00:30:16,460 --> 00:30:22,320
Als (node9 == NULL, of - nog eenvoudiger,

399
00:30:22,320 --> 00:30:28,020
Dit komt neer op slechts indien niet node9.

400
00:30:28,020 --> 00:30:38,310
Als niet node9 of niet node6 of niet node3 of niet node7 terug 1.

401
00:30:38,310 --> 00:30:42,850
Misschien moeten we af te drukken malloc is mislukt, of zoiets.

402
00:30:42,850 --> 00:30:46,680
[Student] Is valse gelijk aan ook null?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Elke nul is false.

404
00:30:51,290 --> 00:30:53,920
Dus null is een nul waarde.

405
00:30:53,920 --> 00:30:56,780
Zero is een nulwaarde. False is een nul waarde.

406
00:30:56,780 --> 00:31:02,130
Elke - zo ongeveer de enige twee nul-waarden zijn nul en nul,

407
00:31:02,130 --> 00:31:07,900
vals is net hash gedefinieerd als nul.

408
00:31:07,900 --> 00:31:13,030
Dat geldt ook als we verklaren globale variabele.

409
00:31:13,030 --> 00:31:17,890
Als we hadden knooppunt * wortel hier,

410
00:31:17,890 --> 00:31:24,150
dan - het mooie van globale variabelen is dat ze altijd een initiële waarde.

411
00:31:24,150 --> 00:31:27,500
Dat is niet waar van functies, hoe de binnenkant van hier,

412
00:31:27,500 --> 00:31:34,870
als we, net als, knooppunt of knooppunt * x.

413
00:31:34,870 --> 00:31:37,380
We hebben geen idee wat x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
of we kunnen ze afdrukken en ze zouden kunnen zijn willekeurig.

415
00:31:40,700 --> 00:31:44,980
Dat is niet het geval voor globale variabelen.

416
00:31:44,980 --> 00:31:47,450
Dus knooppunt wortel of knooppunt x.

417
00:31:47,450 --> 00:31:53,410
Standaard alles wat globale, zo niet expliciet geïnitialiseerd op een bepaalde waarde,

418
00:31:53,410 --> 00:31:57,390
een nulwaarde als waarde.

419
00:31:57,390 --> 00:32:01,150
Dus hier, knoop * wortel, hebben we niet expliciet initialiseren om iets,

420
00:32:01,150 --> 00:32:06,350
zodat de standaardwaarde nul, de nulwaarde van pointers.

421
00:32:06,350 --> 00:32:11,870
De standaard waarde van x gaat betekenen dat x.value nul is,

422
00:32:11,870 --> 00:32:14,260
x.left null is, en x.right is null.

423
00:32:14,260 --> 00:32:21,070
Dus omdat het een struct worden alle velden van de struct nul waarden.

424
00:32:21,070 --> 00:32:24,410
We hoeven niet om dat hier te gebruiken, dat wel.

425
00:32:24,410 --> 00:32:27,320
[Student] De structs anders zijn dan andere variabelen, en de andere variabelen

426
00:32:27,320 --> 00:32:31,400
vuilnis waarden, dit zijn nullen?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Andere waarden ook. Dus in x, zal x nul.

428
00:32:36,220 --> 00:32:40,070
Als het op mondiaal bereik, het heeft een initiële waarde. >> Oke.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Ofwel de initiële waarde die u gaf het of nul.

430
00:32:48,950 --> 00:32:53,260
Ik denk dat zorgt voor dit alles.

431
00:32:53,260 --> 00:32:58,390
>> Oke. Dus het volgende deel van de vraag gaat het erom,

432
00:32:58,390 --> 00:33:01,260
"Nu willen we een functie genaamd bevat schrijven

433
00:33:01,260 --> 00:33:04,930
met een prototype van bool bevat int waarde. "

434
00:33:04,930 --> 00:33:08,340
We zijn niet van plan om te doen bool bevat int waarde.

435
00:33:08,340 --> 00:33:15,110
Ons prototype eruit komt te zien als

436
00:33:15,110 --> 00:33:22,380
bool bevat (int waarde.

437
00:33:22,380 --> 00:33:24,490
En dan zijn we ook gaan doorgeven van de boom

438
00:33:24,490 --> 00:33:28,870
dat moet worden controleren of zij die waarde.

439
00:33:28,870 --> 00:33:38,290
Dus knoop * boom). Oke.

440
00:33:38,290 --> 00:33:44,440
En dan kunnen we noemen het met iets als,

441
00:33:44,440 --> 00:33:46,090
we misschien willen printf of zoiets.

442
00:33:46,090 --> 00:33:51,040
Bevat 6, onze wortel.

443
00:33:51,040 --> 00:33:54,300
Dat moet een keer terug, of waar,

444
00:33:54,300 --> 00:33:59,390
terwijl bevat 5 root moet return false.

445
00:33:59,390 --> 00:34:02,690
Dus neem even de tijd om dit te implementeren.

446
00:34:02,690 --> 00:34:06,780
Je kunt het zowel iteratief of recursief.

447
00:34:06,780 --> 00:34:09,739
Het leuke aan de manier waarop we opgezet dingen is dat

448
00:34:09,739 --> 00:34:12,300
leent zich onze recursieve oplossing gemakkelijker

449
00:34:12,300 --> 00:34:14,719
dan de global-variabele manier deed.

450
00:34:14,719 --> 00:34:19,750
Want als we alleen maar bevat int waarde, dan hebben we geen enkele manier recursing beneden substructuren.

451
00:34:19,750 --> 00:34:24,130
We zouden een aparte helper functie die recurses beneden de substructuren voor ons hebben.

452
00:34:24,130 --> 00:34:29,610
Maar sinds we het veranderd om de boom te nemen als een argument,

453
00:34:29,610 --> 00:34:32,760
waarin zij moeten altijd zijn in de eerste plaats,

454
00:34:32,760 --> 00:34:35,710
Nu kunnen we recurse gemakkelijker.

455
00:34:35,710 --> 00:34:38,960
Dus iteratieve of recursieve, gaan we over beide,

456
00:34:38,960 --> 00:34:46,139
maar we zullen zien dat recursieve eindigt als vrij eenvoudig.

457
00:34:59,140 --> 00:35:02,480
Oke. Heeft iemand iets dat we kunnen samenwerken?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Ik heb een iteratieve oplossing. >> Oke, iteratief.

459
00:35:12,000 --> 00:35:16,030
Oke, dit ziet er goed uit.

460
00:35:16,030 --> 00:35:18,920
Dus, wil je ons er doorheen lopen?

461
00:35:18,920 --> 00:35:25,780
[Student] Tuurlijk. Dus ik stel een temp variabele om het eerste knooppunt van de boom te krijgen.

462
00:35:25,780 --> 00:35:28,330
En dan ga ik gewoon doorgelust terwijl temp is niet gelijk aan nul,

463
00:35:28,330 --> 00:35:31,700
dus terwijl nog in de boom, denk ik.

464
00:35:31,700 --> 00:35:35,710
En als de waarde gelijk is aan de waarde die temp wordt verwezen,

465
00:35:35,710 --> 00:35:37,640
dan is die waarde geretourneerd.

466
00:35:37,640 --> 00:35:40,210
Anders wordt er gecontroleerd of het aan de rechter-of de linkerkant.

467
00:35:40,210 --> 00:35:43,400
Als je ooit een situatie waarin er geen meer boom,

468
00:35:43,400 --> 00:35:47,330
dan is het terug - ze uit de lus en false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Oke. Dus dat lijkt goed.

470
00:35:52,190 --> 00:35:58,470
Iemand enig commentaar op alles?

471
00:35:58,470 --> 00:36:02,400
Ik heb geen correctheid commentaar op alle.

472
00:36:02,400 --> 00:36:11,020
Het enige wat we kunnen doen is deze kerel.

473
00:36:11,020 --> 00:36:21,660
Oh, het gaat om een ​​beetje vrij lange gaan.

474
00:36:21,660 --> 00:36:33,460
Ik maak dat op. Oke.

475
00:36:33,460 --> 00:36:37,150
>> Iedereen moet zich herinneren hoe ternaire werkt.

476
00:36:37,150 --> 00:36:38,610
Er hebben zeker quizzen in het verleden

477
00:36:38,610 --> 00:36:41,170
dat geeft je een functie met een ternaire operator,

478
00:36:41,170 --> 00:36:45,750
en zeggen: vertalen dit, doe iets dat niet gebruikt ternaire.

479
00:36:45,750 --> 00:36:49,140
Dus dit is een veel voorkomende geval van als ik zou denken aan ternaire te gebruiken,

480
00:36:49,140 --> 00:36:54,610
waar als enige voorwaarde een variabele om iets,

481
00:36:54,610 --> 00:36:58,580
anders ingesteld dat dezelfde variabele naar iets anders.

482
00:36:58,580 --> 00:37:03,390
Dat is iets dat heel vaak kan worden omgezet in dit soort dingen

483
00:37:03,390 --> 00:37:14,420
waar ingesteld die variabele aan deze - of, nou ja, is dit waar? Dan is dit, anders dit.

484
00:37:14,420 --> 00:37:18,550
[Student] De eerste is als het waar is, toch?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Ja. De manier waarop ik lees altijd het is, temp is gelijk aan waarde groter dan temp waarde,

486
00:37:25,570 --> 00:37:30,680
Dan, anders deze. Het is een vraag.

487
00:37:30,680 --> 00:37:35,200
Is het groter? Doe dan het eerste. Anders doen het tweede ding.

488
00:37:35,200 --> 00:37:41,670
Ik heb bijna altijd - de dikke darm, ik - in mijn hoofd, ik lees als anders.

489
00:37:41,670 --> 00:37:47,180
>> Heeft iemand een recursieve oplossing?

490
00:37:47,180 --> 00:37:49,670
Oke. Deze gaan we - het zou al geweldig zijn,

491
00:37:49,670 --> 00:37:53,990
maar we gaan het nog beter.

492
00:37:53,990 --> 00:37:58,720
Dit is vrij veel het zelfde nauwkeurige idee.

493
00:37:58,720 --> 00:38:03,060
Het is gewoon, nou ja, wil je het uitleggen?

494
00:38:03,060 --> 00:38:08,340
[Student] Tuurlijk. Dus we ervoor te zorgen dat de boom niet wordt eerst null,

495
00:38:08,340 --> 00:38:13,380
want als de boom null is, het gaat om terug te keren vals, want we hebben het niet gevonden.

496
00:38:13,380 --> 00:38:19,200
En als er nog steeds een boom, gaan we in op - we eerst controleren of de waarde is de huidige knooppunt.

497
00:38:19,200 --> 00:38:23,740
Return true als het is, en als we niet recursief aan de linker of rechter.

498
00:38:23,740 --> 00:38:25,970
Klinkt dat juist? >> Mm-hmm. (Overeenkomst)

499
00:38:25,970 --> 00:38:33,880
Dus merken dat dit bijna is - structureel zeer vergelijkbaar met de iteratieve oplossing.

500
00:38:33,880 --> 00:38:38,200
Het is gewoon dat in plaats van recursing, we een while-lus had.

501
00:38:38,200 --> 00:38:40,840
En het basisscenario hier, waar boom is niet gelijk aan nul

502
00:38:40,840 --> 00:38:44,850
was de voorwaarde waaronder wij uitbrak van de while-lus.

503
00:38:44,850 --> 00:38:50,200
Ze zijn zeer vergelijkbaar. Maar we gaan nog een stap verder te nemen.

504
00:38:50,200 --> 00:38:54,190
Nu doen we hetzelfde hier.

505
00:38:54,190 --> 00:38:57,680
Let op dat we hetzelfde in beide van deze lijnen terug te keren,

506
00:38:57,680 --> 00:39:00,220
behalve een argument verschilt.

507
00:39:00,220 --> 00:39:07,950
Dus we gaan die te maken in een ternair.

508
00:39:07,950 --> 00:39:13,790
Ik raakte optie iets, en het maakte een symbool. Oke.

509
00:39:13,790 --> 00:39:21,720
Dus we gaan om terug te keren bevat dat.

510
00:39:21,720 --> 00:39:28,030
Dit wordt aan het worden meerdere regels, goed, ingezoomd is.

511
00:39:28,030 --> 00:39:31,060
Meestal als een stilistische ding, ik denk niet dat veel mensen

512
00:39:31,060 --> 00:39:38,640
Zet een spatie na de pijl, maar ik denk dat als je consequent, het is prima.

513
00:39:38,640 --> 00:39:44,320
Als de waarde lager is dan de boom waarde, we willen recurse op boom links,

514
00:39:44,320 --> 00:39:53,890
wat we willen recurse op boom rechts.

515
00:39:53,890 --> 00:39:58,610
Dus dat was de eerste stap van het maken van deze look kleiner.

516
00:39:58,610 --> 00:40:02,660
Stap twee van het maken van deze look kleinere -

517
00:40:02,660 --> 00:40:09,150
we scheiden dit meerdere lijnen.

518
00:40:09,150 --> 00:40:16,500
Oke. Stap twee van waardoor het lijkt kleiner is hier,

519
00:40:16,500 --> 00:40:25,860
dus return waarde is gelijk aan boom-waarde, of bevat wat dan ook.

520
00:40:25,860 --> 00:40:28,340
>> Dit is een belangrijk ding.

521
00:40:28,340 --> 00:40:30,860
Ik weet niet zeker of hij zei dat het expliciet in de klas,

522
00:40:30,860 --> 00:40:34,740
maar het heet kortsluiting evaluatie.

523
00:40:34,740 --> 00:40:41,060
Het idee hier is waarde == boom waarde.

524
00:40:41,060 --> 00:40:49,960
Als dat waar is, dan is dit waar is, en we willen 'of' dat met wat hier is voorbij.

525
00:40:49,960 --> 00:40:52,520
Dus zonder zelfs te denken over wat er hier,

526
00:40:52,520 --> 00:40:55,070
wat is de volledige uitdrukking te gaan om terug te keren?

527
00:40:55,070 --> 00:40:59,430
[Student] Waar? >> Ja, omdat ware van alles,

528
00:40:59,430 --> 00:41:04,990
or'd - of ware or'd met iets is noodzakelijk waar.

529
00:41:04,990 --> 00:41:08,150
Dus zodra we return value = boom waarde te zien,

530
00:41:08,150 --> 00:41:10,140
we gaan gewoon om terug te keren waar.

531
00:41:10,140 --> 00:41:15,710
Niet eens gaan recurse bevat verder langs de lijn.

532
00:41:15,710 --> 00:41:20,980
We kunnen nog een stap verder.

533
00:41:20,980 --> 00:41:29,490
Terug boom is niet gelijk aan nul en dit alles.

534
00:41:29,490 --> 00:41:32,650
Dat maakte het een een-lijn-functie.

535
00:41:32,650 --> 00:41:36,790
Dit is een voorbeeld van kortsluiting evalueren.

536
00:41:36,790 --> 00:41:40,680
Maar nu is het hetzelfde idee -

537
00:41:40,680 --> 00:41:47,320
in plaats van - dus als boom is niet gelijk aan nul - of, nou ja,

538
00:41:47,320 --> 00:41:49,580
als boom doet gelijk null, dat is het slechte geval is,

539
00:41:49,580 --> 00:41:54,790
Als tree is gelijk nul, dan is de eerste voorwaarde zal zijn vals.

540
00:41:54,790 --> 00:42:00,550
Dus valse ge-AND met iets gaat worden wat?

541
00:42:00,550 --> 00:42:04,640
[Student] False. >> Ja. Dit is de andere helft van kortsluiting evaluatie,

542
00:42:04,640 --> 00:42:10,710
waar als boom niet gelijk nul, dan zijn we niet van plan om eens te gaan -

543
00:42:10,710 --> 00:42:14,930
of als boom doet gelijk null, dan zijn we niet van plan om waarde == boom waarde te doen.

544
00:42:14,930 --> 00:42:17,010
We gaan gewoon meteen return false.

545
00:42:17,010 --> 00:42:20,970
Dat is belangrijk, want als het deed geen kortsluiting te evalueren,

546
00:42:20,970 --> 00:42:25,860
dan als boom doet gelijk null is, wordt deze tweede voorwaarde gaat seg schuld,

547
00:42:25,860 --> 00:42:32,510
omdat boom-> waarde wordt dereferentie null.

548
00:42:32,510 --> 00:42:40,490
Dus dat is dat. Kan dit - verschuiven een keer over.

549
00:42:40,490 --> 00:42:44,840
Dit is een veel voorkomend geval ook, verzin dit niet een lijn met deze,

550
00:42:44,840 --> 00:42:49,000
maar het is een gemeenschappelijk ding in omstandigheden, misschien niet hier,

551
00:42:49,000 --> 00:42:59,380
maar als (boom! = NULL, en boom-> waarde == waarde), doen wat.

552
00:42:59,380 --> 00:43:01,560
Dit is een veel voorkomende aandoening, waarbij in plaats van

553
00:43:01,560 --> 00:43:06,770
deze te breken in twee mitsen, waar wil, is de boom null?

554
00:43:06,770 --> 00:43:11,780
Oke, het is niet null is, dus nu is de boom waarde gelijk aan waarde? Doe dit.

555
00:43:11,780 --> 00:43:17,300
In plaats daarvan, deze voorwaarde, zal dit nooit seg fout

556
00:43:17,300 --> 00:43:21,220
want het zal breken als dit gebeurt op null zijn.

557
00:43:21,220 --> 00:43:24,000
Nou, ik denk dat als je boom is een volledig ongeldig pointer, kan het nog steeds seg schuld,

558
00:43:24,000 --> 00:43:26,620
maar het kan niet seg fout als boom is null.

559
00:43:26,620 --> 00:43:32,900
Als het null, zou het uitbreken voordat je ooit dereferentie de aanwijzer in de eerste plaats.

560
00:43:32,900 --> 00:43:35,000
[Student] Is dit zogenaamde lazy evaluatie?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy evaluatie is een apart ding.

562
00:43:40,770 --> 00:43:49,880
Lazy evaluatie is meer als je vraagt ​​voor een waarde,

563
00:43:49,880 --> 00:43:54,270
u vragen om een ​​waarde, een soort van te berekenen, maar je hoeft niet meteen nodig hebt.

564
00:43:54,270 --> 00:43:59,040
Dus totdat u daadwerkelijk nodig hebt, is het niet geëvalueerd.

565
00:43:59,040 --> 00:44:03,920
Dit is niet precies hetzelfde, maar in de Huffman PSET,

566
00:44:03,920 --> 00:44:06,520
het zegt dat we "lui" te schrijven.

567
00:44:06,520 --> 00:44:08,670
De reden dat we dat doen is omdat we eigenlijk het bufferen van de schrijf -

568
00:44:08,670 --> 00:44:11,820
we niet willen afzonderlijke stukjes schrijven tegelijk

569
00:44:11,820 --> 00:44:15,450
of individuele bytes op een moment, dat we in plaats daarvan willen een stuk van bytes te krijgen.

570
00:44:15,450 --> 00:44:19,270
Dan een keer hebben we een stuk van bytes, dan zullen we schrijven het uit.

571
00:44:19,270 --> 00:44:22,640
Ook al heb je vragen er een te schrijven - en fwrite en fread doen hetzelfde soort dingen.

572
00:44:22,640 --> 00:44:26,260
Ze bufferen je leest en schrijft.

573
00:44:26,260 --> 00:44:31,610
Ook al heb je vragen om onmiddelijk te schrijven, zal het waarschijnlijk niet.

574
00:44:31,610 --> 00:44:34,540
En je kunt er niet zeker van dat de dingen zullen worden geschreven

575
00:44:34,540 --> 00:44:37,540
totdat u hfclose of wat het ook is,

576
00:44:37,540 --> 00:44:39,620
die dan zegt, oke, ik sluit mijn dossier,

577
00:44:39,620 --> 00:44:43,450
dat betekent dat ik maar beter schrijf alles wat ik nog niet geschreven.

578
00:44:43,450 --> 00:44:45,770
Het is niet nodig om alles uit te schrijven

579
00:44:45,770 --> 00:44:49,010
totdat u het sluiten van het bestand, en dan moet het.

580
00:44:49,010 --> 00:44:56,220
Dus dat is precies wat lui - het wacht totdat het moet gebeuren.

581
00:44:56,220 --> 00:44:59,990
Deze - neem 51 en je zult in het gaan in meer detail,

582
00:44:59,990 --> 00:45:05,470
omdat OCaml en alles in 51, alles is recursie.

583
00:45:05,470 --> 00:45:08,890
Er zijn geen iteratieve oplossingen in principe,.

584
00:45:08,890 --> 00:45:11,550
Alles is recursie, en lazy evaluatie

585
00:45:11,550 --> 00:45:14,790
zal belangrijk voor veel omstandigheden

586
00:45:14,790 --> 00:45:19,920
waar, als je niet lui te evalueren, zou dat betekenen -

587
00:45:19,920 --> 00:45:24,760
Het voorbeeld stromen, die oneindig lang.

588
00:45:24,760 --> 00:45:30,990
In theorie kunt u denken aan de natuurlijke getallen als een stroom van 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Dus lui geëvalueerd dingen zijn prima.

590
00:45:33,090 --> 00:45:37,210
Als ik zeg dat ik wil dat de tiende nummer, dan kan ik tot evalueren om de tiende nummer.

591
00:45:37,210 --> 00:45:40,300
Als ik wil het honderdste nummer, dan kan ik tot evalueren om de honderdste nummer.

592
00:45:40,300 --> 00:45:46,290
Zonder lazy evaluatie, dan is het gaan proberen om onmiddellijk te evalueren alle nummers.

593
00:45:46,290 --> 00:45:50,000
Je evalueren van oneindig veel getallen, en dat is gewoon niet mogelijk.

594
00:45:50,000 --> 00:45:52,080
Dus er zijn veel omstandigheden waarin lazy evaluatie

595
00:45:52,080 --> 00:45:57,840
is gewoon van essentieel belang om het verkrijgen van dingen om te werken.

596
00:45:57,840 --> 00:46:05,260
>> Nu willen we insert schrijven waar insert gaat worden

597
00:46:05,260 --> 00:46:08,430
eveneens veranderen in de definitie ervan.

598
00:46:08,430 --> 00:46:10,470
Dus nu is het bool inzetstuk (int waarde).

599
00:46:10,470 --> 00:46:23,850
We gaan dat veranderen naar bool insert (int waarde, knoop * boom).

600
00:46:23,850 --> 00:46:29,120
We zijn eigenlijk gaat dat weer veranderen in een beetje, zullen we zien waarom.

601
00:46:29,120 --> 00:46:32,210
En laten we gaan build_node, alleen voor de deurklink van het,

602
00:46:32,210 --> 00:46:36,730
boven te plaatsen zodat we niet een functie prototype te schrijven.

603
00:46:36,730 --> 00:46:42,450
Dat is een hint dat je gaat worden met behulp van build_node in insert.

604
00:46:42,450 --> 00:46:49,590
Oke. Neem een ​​minuut voor.

605
00:46:49,590 --> 00:46:52,130
Ik denk dat ik gered van de herziening als je wilt trekken van dat,

606
00:46:52,130 --> 00:47:00,240
of, in ieder geval, ik heb nu.

607
00:47:00,240 --> 00:47:04,190
Ik wilde een lichte pauze om na te denken over de logica van insert,

608
00:47:04,190 --> 00:47:08,750
als je niet kunt denken.

609
00:47:08,750 --> 00:47:12,860
In principe, zal u alleen ooit het invoegen op bladeren.

610
00:47:12,860 --> 00:47:18,640
Zoals, als ik plaats 1, dan ga ik onvermijdelijk zal worden invoegen 1 -

611
00:47:18,640 --> 00:47:21,820
Ik zal wijzigen in zwart - Ik zal worden het plaatsen van een hier.

612
00:47:21,820 --> 00:47:28,070
Of als ik plaats 4, Ik wil graag het invoegen van 4 hier.

613
00:47:28,070 --> 00:47:32,180
Dus niet uit wat je doet, je gaat te plaatsen op een blad.

614
00:47:32,180 --> 00:47:36,130
Het enige wat je hoeft te doen is herhalen uit de boom totdat je bij het knooppunt

615
00:47:36,130 --> 00:47:40,890
dat moet het knooppunt ouder, de nieuwe node ouder te zijn,

616
00:47:40,890 --> 00:47:44,560
en wijzig de linker of rechter cursor naargelang

617
00:47:44,560 --> 00:47:47,060
Het is groter dan of kleiner dan het huidige knooppunt.

618
00:47:47,060 --> 00:47:51,180
Verandering die wijzer om te verwijzen naar uw nieuwe knooppunt.

619
00:47:51,180 --> 00:48:05,490
Dus herhalen de boom, maakt het blad verwijzen naar de nieuwe node.

620
00:48:05,490 --> 00:48:09,810
Denk ook aan waarom dat verbiedt de aard van de situatie voor,

621
00:48:09,810 --> 00:48:17,990
waar ik bouwde de binaire boom waar het was juist

622
00:48:17,990 --> 00:48:19,920
als je alleen maar gekeken naar een enkele knoop,

623
00:48:19,920 --> 00:48:24,830
maar 9 was aan de linkerkant van 7 als u herhaald helemaal naar beneden.

624
00:48:24,830 --> 00:48:29,770
Dus dat is onmogelijk in dit scenario, omdat -

625
00:48:29,770 --> 00:48:32,530
denk over het invoegen van 9 of iets, helemaal aan het eerste knooppunt,

626
00:48:32,530 --> 00:48:35,350
Ik ga tot en met 7 zien en ik ga gewoon naar rechts.

627
00:48:35,350 --> 00:48:38,490
Dus niet uit wat ik doe, als ik het invoegen door te gaan naar een blad,

628
00:48:38,490 --> 00:48:40,790
en een blad met de juiste algoritme,

629
00:48:40,790 --> 00:48:43,130
het gaat om het onmogelijk voor mij om 9 voegt u aan de linkerkant van 7

630
00:48:43,130 --> 00:48:48,250
want zodra ik 7 raakte ik ga naar rechts.

631
00:48:59,740 --> 00:49:02,070
Heeft iemand iets om mee te beginnen?

632
00:49:02,070 --> 00:49:05,480
[Student] ik doe. >> Tuurlijk.

633
00:49:05,480 --> 00:49:09,200
[Student, onverstaanbaar]

634
00:49:09,200 --> 00:49:14,390
[Andere student, onverstaanbaar]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Het is gewaardeerd. Oke. Wil je uitleggen?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Omdat we weten dat we het plaatsen van

637
00:49:20,690 --> 00:49:24,060
nieuwe knooppunten aan het einde van de boom,

638
00:49:24,060 --> 00:49:28,070
Ik doorgelust de boom iteratief

639
00:49:28,070 --> 00:49:31,360
tot ik op een knooppunt dat wees op null.

640
00:49:31,360 --> 00:49:34,220
En toen besloot ik om ofwel zet het op de rechter-of de linkerkant

641
00:49:34,220 --> 00:49:37,420
van dit recht gebruik variabele, het zei me waar deze te plaatsen.

642
00:49:37,420 --> 00:49:41,850
En dan, in wezen, ik maakte dat laatste -

643
00:49:41,850 --> 00:49:47,520
dat temp knooppunt naar het nieuwe knooppunt dat het creëren,

644
00:49:47,520 --> 00:49:50,770
hetzij links of rechts, afhankelijk van de waarde gelijk.

645
00:49:50,770 --> 00:49:56,530
Tot slot wil ik u de nieuwe node waarde aan de waarde van de testen.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Oke, dus ik zie hier een probleem.

647
00:49:59,550 --> 00:50:02,050
Dit is als 95% van de heenweg.

648
00:50:02,050 --> 00:50:07,550
Het enige probleem dat ik zie, nou ja, heeft iemand anders ziet een probleem?

649
00:50:07,550 --> 00:50:18,400
Wat is de omstandigheid waaronder zij uit te breken van de lus?

650
00:50:18,400 --> 00:50:22,100
[Student] Als temp null is? >> Ja. Dus hoe je uit te breken van de lus is als temp is null.

651
00:50:22,100 --> 00:50:30,220
Maar wat moet ik doen hier?

652
00:50:30,220 --> 00:50:35,410
Ik dereference temp, dat is onvermijdelijk null.

653
00:50:35,410 --> 00:50:39,840
Dus het andere wat je hoeft te doen is niet alleen bij te houden totdat temp null is,

654
00:50:39,840 --> 00:50:45,590
u wilt bijhouden van de moedermaatschappij te allen tijde.

655
00:50:45,590 --> 00:50:52,190
We hebben ook knoop * ouder willen, ik denk dat we kunnen die ervoor zorgen dat op nul op het eerste.

656
00:50:52,190 --> 00:50:55,480
Dit gaat raar gedrag voor de wortel van de boom,

657
00:50:55,480 --> 00:50:59,210
maar we krijgen dat.

658
00:50:59,210 --> 00:51:03,950
Als de waarde groter is dan wat dan ook, dan is temp = temp rechts.

659
00:51:03,950 --> 00:51:07,910
Maar voordat we dat doen, ouder = temp.

660
00:51:07,910 --> 00:51:14,500
Of zijn ouders altijd gaan om een ​​gelijke temp? Is dat het geval?

661
00:51:14,500 --> 00:51:19,560
Als temp niet null is, dan ga ik naar beneden, wat er ook gebeurt,

662
00:51:19,560 --> 00:51:24,030
een knooppunt waarvoor temp het ouder.

663
00:51:24,030 --> 00:51:27,500
Dus ouder gaat worden temp, en dan ga ik verhuizen temp beneden.

664
00:51:27,500 --> 00:51:32,410
Nu temp null is, maar ouder wijst op de ouder van het ding dat null is.

665
00:51:32,410 --> 00:51:39,110
Dus hier beneden, ik wil niet in te stellen rechts is gelijk aan 1.

666
00:51:39,110 --> 00:51:41,300
Dus ik naar rechts verplaatst, dus als rechts = 1,

667
00:51:41,300 --> 00:51:45,130
en ik denk dat je ook wilt doen -

668
00:51:45,130 --> 00:51:48,530
als u verhuist naar links, die u wilt instellen recht gelijk aan 0.

669
00:51:48,530 --> 00:51:55,950
Of anders als je ooit naar rechts te verplaatsen.

670
00:51:55,950 --> 00:51:58,590
Dus rechts = 0. Als rechts = 1,

671
00:51:58,590 --> 00:52:04,260
Nu willen we de ouders recht pointer newnode te maken,

672
00:52:04,260 --> 00:52:08,520
anders willen we de ouders linker pointer newnode te maken.

673
00:52:08,520 --> 00:52:16,850
Vragen over zeggen?

674
00:52:16,850 --> 00:52:24,880
Oke. Dus dit is de manier waarop we - nou ja, eigenlijk, in plaats van dit te doen,

675
00:52:24,880 --> 00:52:29,630
we half verwacht dat je build_node gebruiken.

676
00:52:29,630 --> 00:52:40,450
En dan, als newnode gelijk is aan null, false retourneren.

677
00:52:40,450 --> 00:52:44,170
Dat is dat. Nu, dit is wat we verwacht je te doen.

678
00:52:44,170 --> 00:52:47,690
>> Dit is wat de medewerkers oplossingen te doen.

679
00:52:47,690 --> 00:52:52,360
Ik ben het oneens met dit als de "juiste" manier te gaan over het

680
00:52:52,360 --> 00:52:57,820
maar dit is perfect in orde en het zal werken.

681
00:52:57,820 --> 00:53:02,840
Een ding dat is een beetje raar op dit moment is

682
00:53:02,840 --> 00:53:08,310
als de boom begint als null, passeren we in een null-boom.

683
00:53:08,310 --> 00:53:12,650
Ik denk dat het hangt af van hoe definieer je het gedrag van het passeren in een null-boom.

684
00:53:12,650 --> 00:53:15,490
Ik zou denken dat als je pas in een null-boom,

685
00:53:15,490 --> 00:53:17,520
dan het plaatsen van de waarde in een null boom

686
00:53:17,520 --> 00:53:23,030
moet gewoon terug een boom waar de enige waarde is dat enkel knooppunt.

687
00:53:23,030 --> 00:53:25,830
Hebben mensen het daarmee eens? Je zou, als je wilde,

688
00:53:25,830 --> 00:53:28,050
als je langs in een null-boom

689
00:53:28,050 --> 00:53:31,320
en u wilt een waarde in te voegen in het, return false.

690
00:53:31,320 --> 00:53:33,830
Het is aan jou om te bepalen dat.

691
00:53:33,830 --> 00:53:38,320
Om het eerste wat ik zei en dan doen -

692
00:53:38,320 --> 00:53:40,720
goed, je gaat om problemen om dat te doen hebben, omdat

693
00:53:40,720 --> 00:53:44,090
Het zou makkelijker zijn als we een globale pointer naar het ding,

694
00:53:44,090 --> 00:53:48,570
maar we weten niet, dus als boom is null, er is niets wat we kunnen doen over.

695
00:53:48,570 --> 00:53:50,960
We kunnen gewoon return false.

696
00:53:50,960 --> 00:53:52,840
Dus ik ga naar insert te veranderen.

697
00:53:52,840 --> 00:53:56,540
We technisch zou hier gewoon veranderen van dit recht,

698
00:53:56,540 --> 00:53:58,400
hoe het itereren over de dingen,

699
00:53:58,400 --> 00:54:04,530
maar ik ga insert te veranderen naar een knooppunt te nemen ** boom.

700
00:54:04,530 --> 00:54:07,510
Dubbele pointers.

701
00:54:07,510 --> 00:54:09,710
Wat betekent dit?

702
00:54:09,710 --> 00:54:12,330
In plaats van omgaan met verwijzingen naar knooppunten,

703
00:54:12,330 --> 00:54:16,690
het ding dat ik ga worden manipuleren is deze pointer.

704
00:54:16,690 --> 00:54:18,790
Ik ga te manipuleren deze pointer.

705
00:54:18,790 --> 00:54:21,770
Ik ga te manipuleren pointers direct.

706
00:54:21,770 --> 00:54:25,760
Dit is logisch aangezien, na te denken over down -

707
00:54:25,760 --> 00:54:33,340
goed, nu wijst dit op null.

708
00:54:33,340 --> 00:54:38,130
Wat ik wil doen is te manipuleren deze pointer te wijzen op niet null.

709
00:54:38,130 --> 00:54:40,970
Ik wil dat het wijzen op mijn nieuwe knooppunt.

710
00:54:40,970 --> 00:54:44,870
Als ik gewoon bijhouden van pointers naar mijn pointers,

711
00:54:44,870 --> 00:54:47,840
dan heb ik niet nodig om bij te houden van een ouder pointer.

712
00:54:47,840 --> 00:54:52,640
Ik kan gewoon bijhouden om te zien of de wijzer wijst naar null,

713
00:54:52,640 --> 00:54:54,580
en als de wijzer wijst naar null,

714
00:54:54,580 --> 00:54:57,370
wijzigen om te wijzen op het knooppunt ik wil.

715
00:54:57,370 --> 00:55:00,070
En ik kan veranderen want ik heb een verwijzing naar de aanwijzer.

716
00:55:00,070 --> 00:55:02,040
Laten we dit nu zien.

717
00:55:02,040 --> 00:55:05,470
Je kunt eigenlijk doen recursief vrij gemakkelijk.

718
00:55:05,470 --> 00:55:08,080
Willen we dat doen?

719
00:55:08,080 --> 00:55:10,980
Ja, we doen.

720
00:55:10,980 --> 00:55:16,790
>> Laten we recursief zien.

721
00:55:16,790 --> 00:55:24,070
Ten eerste, wat is ons basisscenario gaan worden?

722
00:55:24,070 --> 00:55:29,140
Bijna altijd ons basisscenario, maar eigenlijk is dit soort van lastig.

723
00:55:29,140 --> 00:55:34,370
First things first, if (boom == NULL)

724
00:55:34,370 --> 00:55:37,550
Ik denk dat we gaan gewoon om terug te keren vals.

725
00:55:37,550 --> 00:55:40,460
Dit is anders dan uw boom wordt null.

726
00:55:40,460 --> 00:55:44,510
Dit is de pointer naar je root pointer wordt null

727
00:55:44,510 --> 00:55:48,360
wat betekent dat je root pointer bestaat niet.

728
00:55:48,360 --> 00:55:52,390
Dus hier beneden, als ik dat doe

729
00:55:52,390 --> 00:55:55,760
knooppunt * - laten we deze opnieuw te gebruiken.

730
00:55:55,760 --> 00:55:58,960
Node * root = NULL,

731
00:55:58,960 --> 00:56:00,730
en dan ga ik naar insert oproepen door iets te doen, zoals,

732
00:56:00,730 --> 00:56:04,540
plaats 4 in & wortel.

733
00:56:04,540 --> 00:56:06,560
So & wortel, als root is een knooppunt *

734
00:56:06,560 --> 00:56:11,170
Vervolgens & wortel gaat worden een knooppunt **.

735
00:56:11,170 --> 00:56:15,120
Dit geldt. In dit geval boom hier,

736
00:56:15,120 --> 00:56:20,120
boom is niet null - of insert.

737
00:56:20,120 --> 00:56:24,630
Hier. Boom is niet nul; * boom is null, wat fijn is

738
00:56:24,630 --> 00:56:26,680
want als * boom is null, dan kan ik manipuleren

739
00:56:26,680 --> 00:56:29,210
Tot nu toe wijzen op wat ik wil dat het wijzen.

740
00:56:29,210 --> 00:56:34,750
Maar als boom is null, dat betekent dat ik net hier neer en zei: null.

741
00:56:34,750 --> 00:56:42,710
Dat is niet logisch. Ik kan niets doen met die.

742
00:56:42,710 --> 00:56:45,540
Als boom is null, false retourneren.

743
00:56:45,540 --> 00:56:48,220
Dus ik eigenlijk al gezegd wat onze echte basisscenario is.

744
00:56:48,220 --> 00:56:50,580
En wat is dat zal worden?

745
00:56:50,580 --> 00:56:55,030
[Student, onverstaanbaar]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ja. Dus als (* boom == NULL).

747
00:57:00,000 --> 00:57:04,520
Dit heeft betrekking op het geval hier

748
00:57:04,520 --> 00:57:09,640
waar als mijn rode wijzer is de pointer Ik ben gericht op,

749
00:57:09,640 --> 00:57:12,960
dus zoals ik ben gericht op deze wijzer, nu ben ik gericht op deze wijzer.

750
00:57:12,960 --> 00:57:15,150
Nu ben ik gericht op deze wijzer.

751
00:57:15,150 --> 00:57:18,160
Dus als mijn rode wijzer, dat is mijn knoop **,

752
00:57:18,160 --> 00:57:22,880
is ooit - als *, mijn rode wijzer, is altijd null,

753
00:57:22,880 --> 00:57:28,470
dat betekent dat ik op het geval dat ik mij op een pointer die verwijst -

754
00:57:28,470 --> 00:57:32,530
Dit is een pointer die behoort tot een blad.

755
00:57:32,530 --> 00:57:41,090
Ik wil deze pointer veranderen om te wijzen op mijn nieuwe knooppunt.

756
00:57:41,090 --> 00:57:45,230
Kom terug hier.

757
00:57:45,230 --> 00:57:56,490
Mijn newnode zal gewoon knooppunt * n = build_node (waarde)

758
00:57:56,490 --> 00:58:07,300
dan n, als n = NULL, return false.

759
00:58:07,300 --> 00:58:12,600
Wat we willen veranderen wat de aanwijzer op dit moment wijst naar

760
00:58:12,600 --> 00:58:17,830
Tot nu toe wijzen op onze nieuw gebouwde node.

761
00:58:17,830 --> 00:58:20,280
We kunnen eigenlijk doen dat hier.

762
00:58:20,280 --> 00:58:30,660
In plaats van te zeggen n, wij zeggen * boom = als * boom.

763
00:58:30,660 --> 00:58:35,450
Iedereen begrijpt dat? Dat door het omgaan met verwijzingen naar pointers,

764
00:58:35,450 --> 00:58:40,750
we kunnen veranderen null pointers te wijzen op dingen die we willen dat ze wijzen op.

765
00:58:40,750 --> 00:58:42,820
Dat is ons basisscenario.

766
00:58:42,820 --> 00:58:45,740
>> Nu onze recidief, of onze recursie,

767
00:58:45,740 --> 00:58:51,430
gaat worden zeer vergelijkbaar met alle andere recursies we hebben gedaan.

768
00:58:51,430 --> 00:58:55,830
We gaan willen waarde in te voegen,

769
00:58:55,830 --> 00:58:59,040
en nu ga ik om opnieuw te gebruiken ternair, maar wat is onze toestand gaat worden?

770
00:58:59,040 --> 00:59:05,180
Hoe is het we zoeken om te beslissen of we willen gaan links of rechts?

771
00:59:05,180 --> 00:59:07,760
Laten we het doen in afzonderlijke stappen.

772
00:59:07,760 --> 00:59:18,850
Als (waarde <) wat?

773
00:59:18,850 --> 00:59:23,200
[Student] De boom waarde?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Dus herinner me dat ik op dit moment ben -

775
00:59:27,490 --> 00:59:31,260
[Studenten, onverstaanbaar]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Ja, dus hier, laten we zeggen dat dit groene pijl

777
00:59:34,140 --> 00:59:39,050
is een voorbeeld van wat momenteel boom, is een aanwijzing voor deze pointer.

778
00:59:39,050 --> 00:59:46,610
Dus dat betekent dat ik ben een pointer naar een pointer naar 3.

779
00:59:46,610 --> 00:59:48,800
De dereference twee keer goed klonk.

780
00:59:48,800 --> 00:59:51,010
Wat moet ik - hoe doe ik dat?

781
00:59:51,010 --> 00:59:53,210
[Student] dereference een keer, en dan doen pijl die manier?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Dus (* boom) is het dereference keer -> waarde

783
00:59:58,420 --> 01:00:05,960
gaat geven mij de waarde van de node die ik indirect ben wijst.

784
01:00:05,960 --> 01:00:11,980
Dus ik kan ook schrijven ** tree.value als u liever dat.

785
01:00:11,980 --> 01:00:18,490
Ofwel werkt.

786
01:00:18,490 --> 01:00:26,190
Als dat het geval is, dan wil ik bellen met waarde in te voegen.

787
01:00:26,190 --> 01:00:32,590
En wat is mijn bijgewerkte knooppunt ** gaat worden?

788
01:00:32,590 --> 01:00:39,440
Ik wil naar links, dus ** tree.left wordt mijn linkerhand.

789
01:00:39,440 --> 01:00:41,900
En ik wil de aanwijzer naar dat ding

790
01:00:41,900 --> 01:00:44,930
zodat als de linker eindigt in de null pointer,

791
01:00:44,930 --> 01:00:48,360
Ik kan het aanpassen om te verwijzen naar mijn nieuwe knooppunt.

792
01:00:48,360 --> 01:00:51,460
>> En het andere geval kunnen erg lijken.

793
01:00:51,460 --> 01:00:55,600
Laten we eigenlijk maken dat mijn ternaire nu.

794
01:00:55,600 --> 01:01:04,480
Steek waarde als de waarde <(** boom). Waarde.

795
01:01:04,480 --> 01:01:11,040
Dan willen we onze ** updaten naar links,

796
01:01:11,040 --> 01:01:17,030
wat we willen onze ** updaten naar rechts.

797
01:01:17,030 --> 01:01:22,540
[Student] Heeft de pointer die naar de pointer?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Vergeet niet dat - ** tree.right is een knooppunt 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 als deze pointer of iets dergelijks.

801
01:01:41,140 --> 01:01:45,140
Dus door het nemen van een pointer naar dat, dat geeft me wat ik wil

802
01:01:45,140 --> 01:01:50,090
van de pointer naar die kerel.

803
01:01:50,090 --> 01:01:54,260
[Student] Kunnen we nog eens herhalen waarom we met de twee pointers?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Ja. Dus - nee, je kunt, en die oplossing voor

805
01:01:58,220 --> 01:02:04,540
was een manier om het te doen zonder te doen twee pointers.

806
01:02:04,540 --> 01:02:08,740
Je moet in staat zijn om te begrijpen met behulp van twee pointers,

807
01:02:08,740 --> 01:02:11,660
en dit is een schonere oplossing.

808
01:02:11,660 --> 01:02:16,090
Merk ook op dat, wat gebeurt er als mijn boom -

809
01:02:16,090 --> 01:02:24,480
wat gebeurt er als mijn root was null? Wat gebeurt er als ik dit geval hier?

810
01:02:24,480 --> 01:02:30,540
Dus knoop * root = NULL, plaats 4 in & wortel.

811
01:02:30,540 --> 01:02:35,110
Wat wortel gaat worden na dit?

812
01:02:35,110 --> 01:02:37,470
[Student, onverstaanbaar] >> Ja.

813
01:02:37,470 --> 01:02:41,710
Root waarde gaat worden 4.

814
01:02:41,710 --> 01:02:45,510
Root links gaat worden null is, wordt wortel recht gaat null zijn.

815
01:02:45,510 --> 01:02:49,490
In het geval dat we niet voorbij wortel op adres,

816
01:02:49,490 --> 01:02:52,490
we konden niet wijzigen wortel.

817
01:02:52,490 --> 01:02:56,020
In het geval waar de boom - waarbij root was null,

818
01:02:56,020 --> 01:02:58,410
we moesten om terug te keren vals. Er is niets wat we konden doen.

819
01:02:58,410 --> 01:03:01,520
We kunnen een knooppunt niet invoegen in een lege boom.

820
01:03:01,520 --> 01:03:06,810
Maar nu we kunnen, we gewoon een lege boom te maken in een een-knooppunt boom.

821
01:03:06,810 --> 01:03:13,400
Dat is meestal de verwachte manier waarop het zou moeten werken.

822
01:03:13,400 --> 01:03:21,610
>> Bovendien is dit aanzienlijk korter dan

823
01:03:21,610 --> 01:03:26,240
Ook het bijhouden van de ouder, en dus moet je herhalen helemaal naar beneden.

824
01:03:26,240 --> 01:03:30,140
Nu heb ik mijn ouders, en ik heb mijn ouders recht aanwijzer naar het wat dan ook.

825
01:03:30,140 --> 01:03:35,640
In plaats daarvan, als we dat dit iteratief, zou het hetzelfde idee met een lus while.

826
01:03:35,640 --> 01:03:38,100
Maar in plaats van dat te maken met mijn ouders wijzer,

827
01:03:38,100 --> 01:03:40,600
in plaats daarvan mijn huidige pointer zou de zaak zijn

828
01:03:40,600 --> 01:03:43,790
dat ik direct aanpassen om te verwijzen naar mijn nieuwe knooppunt.

829
01:03:43,790 --> 01:03:46,090
Ik heb niet te maken hebben met de vraag of het is dat naar links wijst.

830
01:03:46,090 --> 01:03:48,810
Ik heb niet te maken hebben met de vraag of het is naar rechts.

831
01:03:48,810 --> 01:04:00,860
Het is gewoon wat deze pointer is, ik ga in te stellen om te wijzen op mijn nieuwe knooppunt.

832
01:04:00,860 --> 01:04:05,740
Iedereen begrijpt hoe het werkt?

833
01:04:05,740 --> 01:04:09,460
Indien niet, waarom willen we het op deze manier,

834
01:04:09,460 --> 01:04:14,920
maar in ieder geval dat dit werkt als een oplossing?

835
01:04:14,920 --> 01:04:17,110
[Student] Waar we terug waar?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Dat is waarschijnlijk hier.

837
01:04:21,550 --> 01:04:26,690
Als we op de juiste plaats hem terug waar.

838
01:04:26,690 --> 01:04:32,010
Else, hier beneden gaan we willen wat insert rendement terug te keren.

839
01:04:32,010 --> 01:04:35,950
>> En wat is speciaal aan deze recursieve functie?

840
01:04:35,950 --> 01:04:43,010
Het is staart recursieve, dus zolang we samen te stellen met een aantal optimalisatie,

841
01:04:43,010 --> 01:04:48,060
het zal erkennen dat en je zal een stack overflow nooit van dit,

842
01:04:48,060 --> 01:04:53,230
zelfs indien de boom een ​​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] Ik denk dat het doet het op Dash - of wat optimalisatie niveau

845
01:05:00,310 --> 01:05:03,820
is vereist voor een staart recursie wordt herkend.

846
01:05:03,820 --> 01:05:09,350
Ik denk dat het herkent - GCC en Clang

847
01:05:09,350 --> 01:05:12,610
Ook hebben verschillende betekenissen voor hun optimalisatie niveaus.

848
01:05:12,610 --> 01:05:17,870
Ik wil zeggen dat het DashO 2, zeker dat het zal staart recursie herkennen.

849
01:05:17,870 --> 01:05:27,880
Maar we - je zou kunnen bouwen als een Fibonocci voorbeeld of iets dergelijks.

850
01:05:27,880 --> 01:05:30,030
Het is niet gemakkelijk om te testen met dit, want het is moeilijk te bouwen om

851
01:05:30,030 --> 01:05:32,600
een binaire boom die is zo groot.

852
01:05:32,600 --> 01:05:37,140
Maar ja, ik denk dat het DashO 2, dat

853
01:05:37,140 --> 01:05:40,580
als je compileren met DashO 2, zal hij op zoek naar de staart recursie

854
01:05:40,580 --> 01:05:54,030
en het optimaliseren van dat uit.

855
01:05:54,030 --> 01:05:58,190
Laten we terug gaan naar - plaats is letterlijk het laatste wat het nodig heeft.

856
01:05:58,190 --> 01:06:04,900
Laten we terug gaan naar de insert hier

857
01:06:04,900 --> 01:06:07,840
waar gaan we hetzelfde idee te doen.

858
01:06:07,840 --> 01:06:14,340
Het zal nog steeds de fout van het niet kunnen om volledig te behandelen

859
01:06:14,340 --> 01:06:17,940
wanneer de root zelf null is, of het verleden vermelding is null,

860
01:06:17,940 --> 01:06:20,060
maar in plaats van het omgaan met een ouder wijzer,

861
01:06:20,060 --> 01:06:27,430
Laten we dezelfde logica van het houden van pointers van toepassing op pointers.

862
01:06:27,430 --> 01:06:35,580
Als hier houden we onze knooppunt ** huidig,

863
01:06:35,580 --> 01:06:37,860
en we hoeven niet bij te houden meer goed,

864
01:06:37,860 --> 01:06:47,190
maar knooppunt ** huidig ​​= & boom.

865
01:06:47,190 --> 01:06:54,800
En nu onze while lus gaat worden, terwijl * huidig ​​is niet gelijk aan nul.

866
01:06:54,800 --> 01:07:00,270
Heb geen behoefte om bij te houden van de ouders niet meer te houden.

867
01:07:00,270 --> 01:07:04,180
Hoeven niet bij te houden van links en rechts.

868
01:07:04,180 --> 01:07:10,190
En ik noem het temp, omdat we al gebruik van temp.

869
01:07:10,190 --> 01:07:17,200
Oke. Dus als (waarde> * temp),

870
01:07:17,200 --> 01:07:24,010
Vervolgens & (* temp) -> rechts

871
01:07:24,010 --> 01:07:29,250
anders temp = & (* temp) -> links.

872
01:07:29,250 --> 01:07:32,730
En nu, op dit punt, terwijl na deze lus,

873
01:07:32,730 --> 01:07:36,380
Ik doe dit omdat misschien is het makkelijker om na te denken over iteratief dan recursief,

874
01:07:36,380 --> 01:07:39,010
maar na deze while-lus,

875
01:07:39,010 --> 01:07:43,820
* Temp is de aanwijzer we willen veranderen.

876
01:07:43,820 --> 01:07:48,960
>> Voordat we hadden ouder, en we wilden een van de ouders links of ouder naar rechts te wijzigen,

877
01:07:48,960 --> 01:07:51,310
maar als we willen ouder recht te wijzigen,

878
01:07:51,310 --> 01:07:54,550
dan * temp is ouder recht, en we kunnen direct veranderen.

879
01:07:54,550 --> 01:08:05,860
Dus hier beneden, kunnen we doen * temp = newnode, en dat is het.

880
01:08:05,860 --> 01:08:09,540
Dus aankondiging, alles wat we deden in dit was het afsluiten van regels code.

881
01:08:09,540 --> 01:08:14,770
Om bij te houden van de moedermaatschappij in alles wat extra inspanning.

882
01:08:14,770 --> 01:08:18,689
Hier, als we gewoon spoor van de aanwijzer te houden om de aanwijzer,

883
01:08:18,689 --> 01:08:22,990
en zelfs als we wilden nu te ontdoen van al deze accolades,

884
01:08:22,990 --> 01:08:27,170
zodat het lijkt korter.

885
01:08:27,170 --> 01:08:32,529
Dit is nu precies dezelfde oplossing,

886
01:08:32,529 --> 01:08:38,210
maar minder regels code.

887
01:08:38,210 --> 01:08:41,229
Als je eenmaal begint herkennen dit als een geldige oplossing,

888
01:08:41,229 --> 01:08:43,529
het is ook makkelijker om te redeneren over dan op, oke,

889
01:08:43,529 --> 01:08:45,779
waarom ik deze vlag hebben op int toch?

890
01:08:45,779 --> 01:08:49,290
Wat betekent dat? Oh, het is aan te geven dat

891
01:08:49,290 --> 01:08:51,370
elke keer als ik ga rechts, ik moet het in te stellen,

892
01:08:51,370 --> 01:08:53,819
anders als ik ga linksaf Ik moet het op nul te zetten.

893
01:08:53,819 --> 01:09:04,060
Hier, ik heb geen reden om over dat, het is gewoon makkelijker om na te denken over.

894
01:09:04,060 --> 01:09:06,710
Vragen?

895
01:09:06,710 --> 01:09:16,290
[Student, onverstaanbaar] >> Ja.

896
01:09:16,290 --> 01:09:23,359
Oke, dus in het laatste stuk -

897
01:09:23,359 --> 01:09:28,080
Ik denk dat een snelle en makkelijke functie die we kunnen doen is,

898
01:09:28,080 --> 01:09:34,910
let's - samen, denk ik, probeer en schrijf een bevat de functie

899
01:09:34,910 --> 01:09:38,899
die niet uit of het een binaire zoekboom.

900
01:09:38,899 --> 01:09:43,770
Deze bevat functie moet true retourneren

901
01:09:43,770 --> 01:09:58,330
Als ergens in deze algemene binaire boom is de waarde die we zoeken.

902
01:09:58,330 --> 01:10:02,520
Dus laten we eerst recursief te doen en dan zullen we het iteratief te doen.

903
01:10:02,520 --> 01:10:07,300
We kunnen eigenlijk alleen maar het samen doen, want dit gaat echt kort.

904
01:10:07,300 --> 01:10:11,510
>> Wat is mijn basisscenario gaat worden?

905
01:10:11,510 --> 01:10:13,890
[Student, onverstaanbaar]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Dus als (boom == NULL), wat dan?

907
01:10:18,230 --> 01:10:22,740
[Student] Terug vals.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, nou ja, ik hoef het anders.

909
01:10:26,160 --> 01:10:30,250
Als was mijn andere base case.

910
01:10:30,250 --> 01:10:32,450
[Student] Tree waarde? >> Ja.

911
01:10:32,450 --> 01:10:36,430
Dus als (boom-> waarde == waarde.

912
01:10:36,430 --> 01:10:39,920
Merk op dat we weer terug bij knooppunt * niet, knoop ** s?

913
01:10:39,920 --> 01:10:42,990
Bevat zal nooit meer een knooppunt ** te gebruiken,

914
01:10:42,990 --> 01:10:45,480
omdat we niet wijzigen pointers.

915
01:10:45,480 --> 01:10:50,540
We zijn net doorkruisen ze.

916
01:10:50,540 --> 01:10:53,830
Als dat gebeurt, dan willen we return true.

917
01:10:53,830 --> 01:10:58,270
Else willen we de kinderen doorkruisen.

918
01:10:58,270 --> 01:11:02,620
Dus we kunnen niet redeneren over de vraag of alles naar links is minder

919
01:11:02,620 --> 01:11:05,390
en alles aan de rechterkant is groter.

920
01:11:05,390 --> 01:11:09,590
Dus wat is onze toestand gaat om hier te zijn - of, wat gaan we 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-> rechts). En dat is het.

924
01:11:26,860 --> 01:11:29,080
En let er enige kortsluiting evaluatie,

925
01:11:29,080 --> 01:11:32,520
waar als we toevallig de waarde in de linker boom te vinden,

926
01:11:32,520 --> 01:11:36,820
we nooit moeten kijken naar de juiste boom.

927
01:11:36,820 --> 01:11:40,430
Dat is de hele functie.

928
01:11:40,430 --> 01:11:43,690
Nu laten we het doen iteratief,

929
01:11:43,690 --> 01:11:48,060
die zal minder leuk.

930
01:11:48,060 --> 01:11:54,750
We nemen de gebruikelijke start van knooppunt * huidig ​​= boom.

931
01:11:54,750 --> 01:12:03,250
Terwijl (huidig! = NULL).

932
01:12:03,250 --> 01:12:08,600
Snel naar een probleem te zien.

933
01:12:08,600 --> 01:12:12,250
Als huidig ​​- hier, als we ooit uit te breken van deze,

934
01:12:12,250 --> 01:12:16,020
dan hebben we opraken van de dingen om naar te kijken, dus return false.

935
01:12:16,020 --> 01:12:24,810
Als (huidig-> waarde == waarde), return true.

936
01:12:24,810 --> 01:12:32,910
Dus nu zijn we op een plek -

937
01:12:32,910 --> 01:12:36,250
we weten niet of we willen gaan naar links of rechts.

938
01:12:36,250 --> 01:12:44,590
Dus willekeurig, laten we gewoon gaan verlaten.

939
01:12:44,590 --> 01:12:47,910
Ik heb natuurlijk lopen in een probleem waar ik volledig heb opgegeven alles -

940
01:12:47,910 --> 01:12:50,760
Ik zal alleen maar Controleer de linkerkant van een boom.

941
01:12:50,760 --> 01:12:56,050
Ik zal nooit controleren alles wat een recht kind van alles.

942
01:12:56,050 --> 01:13:00,910
Hoe kan ik dit oplossen?

943
01:13:00,910 --> 01:13:05,260
[Student] Je moet weg van de linker en rechter houden in een stapel.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Ja. Dus laten we het

945
01:13:13,710 --> 01:13:32,360
struct lijst, knooppunt * n, en dan knoop ** volgende stap?

946
01:13:32,360 --> 01:13:40,240
Ik denk dat werkt prima.

947
01:13:40,240 --> 01:13:45,940
We willen gaan over de linker, of let's - hier.

948
01:13:45,940 --> 01:13:54,350
Struct lijst list =, zal het beginnen met

949
01:13:54,350 --> 01:13:58,170
uit bij deze struct lijst.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Dus dat gaat ons gelinkte lijst te zijn

951
01:14:04,040 --> 01:14:08,430
van substructuren die we hebben overgeslagen.

952
01:14:08,430 --> 01:14:13,800
We gaan nu Traverse links,

953
01:14:13,800 --> 01:14:17,870
maar omdat we onvermijdelijk terug hoeft te komen aan het recht,

954
01:14:17,870 --> 01:14:26,140
We gaan de goede kant binnen te houden van onze struct lijst.

955
01:14:26,140 --> 01:14:32,620
Dan hebben we new_list of struct,

956
01:14:32,620 --> 01:14:41,080
struct lijst *, new_list = malloc (sizeof (lijst)).

957
01:14:41,080 --> 01:14:44,920
Ik ga om te negeren foutcontrole dat, maar je moet controleren als het null zien.

958
01:14:44,920 --> 01:14:50,540
New_list het knooppunt dat het gaat om te wijzen op -

959
01:14:50,540 --> 01:14:56,890
oh, dat is waarom ik wilde het hier. Het zal wijzen op een tweede struct lijst.

960
01:14:56,890 --> 01:15:02,380
Dat is gewoon hoe gelinkte lijsten werken.

961
01:15:02,380 --> 01:15:04,810
Dit is hetzelfde als een verbonden lijst int

962
01:15:04,810 --> 01:15:06,960
behalve dat we gewoon te vervangen int met node *.

963
01:15:06,960 --> 01:15:11,040
Het is precies hetzelfde.

964
01:15:11,040 --> 01:15:15,100
Dus new_list, de waarde van onze new_list knooppunt,

965
01:15:15,100 --> 01:15:19,120
gaat worden cur-> rechts.

966
01:15:19,120 --> 01:15:24,280
De waarde van onze new_list-> volgende gaat onze oorspronkelijke lijst te zijn,

967
01:15:24,280 --> 01:15:30,760
en dan gaan we onze lijst bij te werken om te wijzen op new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nu moeten we een soort van manier zijn om dingen,

969
01:15:33,650 --> 01:15:37,020
zoals we hebben doorkruist de hele linker deelboom.

970
01:15:37,020 --> 01:15:40,480
Nu moeten we dingen te trekken uit het,

971
01:15:40,480 --> 01:15:43,850
zoals huidig ​​is null, we willen niet alleen return false.

972
01:15:43,850 --> 01:15:50,370
We willen nu buiten te trekken in onze nieuwe lijst.

973
01:15:50,370 --> 01:15:53,690
Een handige manier om dit te doen - nou ja, eigenlijk is er meerdere manieren om dit te doen.

974
01:15:53,690 --> 01:15:56,680
Iemand een suggestie?

975
01:15:56,680 --> 01:15:58,790
Waar moet ik dit doen of hoe moet ik dit doen?

976
01:15:58,790 --> 01:16:08,010
We hebben maar een paar minuten, maar het even welke suggesties?

977
01:16:08,010 --> 01:16:14,750
In plaats van - een manier plaats van onze voorwaarde is, terwijl

978
01:16:14,750 --> 01:16:17,090
wat we momenteel op zoek naar niet null is,

979
01:16:17,090 --> 01:16:22,340
in plaats daarvan gaan we verder te gaan tot onze lijst zelf is null.

980
01:16:22,340 --> 01:16:25,680
Dus als onze lijst eindigt als null,

981
01:16:25,680 --> 01:16:30,680
dan hebben we uitgeput van dingen te zoeken, om te zoeken over.

982
01:16:30,680 --> 01:16:39,860
Maar dat betekent dat het eerste wat in onze lijst slechts gaat om het eerste knooppunt zijn.

983
01:16:39,860 --> 01:16:49,730
Het allereerste wat zal zijn - we niet meer nodig om dat te zien.

984
01:16:49,730 --> 01:16:58,710
Dus list-> n zal onze boom.

985
01:16:58,710 --> 01:17:02,860
list-> volgende gaat worden null.

986
01:17:02,860 --> 01:17:07,580
En nu, terwijl de lijst is niet gelijk aan nul.

987
01:17:07,580 --> 01:17:11,610
Cur gaat iets te trekken uit onze lijst.

988
01:17:11,610 --> 01:17:13,500
Dus huidig ​​gaat gelijk list-> n.

989
01:17:13,500 --> 01:17:20,850
En dan de lijst gaat gelijk list-> n, of de lijst-> volgende.

990
01:17:20,850 --> 01:17:23,480
Dus als huidig ​​waarde is gelijk aan waarde.

991
01:17:23,480 --> 01:17:28,790
Nu kunnen we toevoegen zowel ons recht aanwijzer en onze linker pointer

992
01:17:28,790 --> 01:17:32,900
zolang ze niet null zijn.

993
01:17:32,900 --> 01:17:36,390
Hier beneden, ik denk dat we moeten dat hebben gedaan in de eerste plaats.

994
01:17:36,390 --> 01:17:44,080
Als (huidig-> rechts! = NULL)

995
01:17:44,080 --> 01:17:56,380
dan gaan we die knoop te voegen aan onze lijst.

996
01:17:56,380 --> 01:17:59,290
Als (huidig-> links), dit is een beetje extra werk, maar het is prima.

997
01:17:59,290 --> 01:18:02,690
Als (huidig-> links! = NULL),

998
01:18:02,690 --> 01:18:14,310
en we gaan naar links in te voegen in onze verbonden lijst,

999
01:18:14,310 --> 01:18:19,700
en dat moet het.

1000
01:18:19,700 --> 01:18:22,670
We herhalen - zolang we iets in onze lijst,

1001
01:18:22,670 --> 01:18:26,640
we hebben een ander knooppunt naar te kijken.

1002
01:18:26,640 --> 01:18:28,920
Dus we kijken naar dat knooppunt,

1003
01:18:28,920 --> 01:18:31,390
we vooraf onze lijst naar de volgende.

1004
01:18:31,390 --> 01:18:34,060
Als dat knooppunt is de waarde die we zoeken, kunnen we return true.

1005
01:18:34,060 --> 01:18:37,640
Else plaatst zowel onze links en rechts substructuren,

1006
01:18:37,640 --> 01:18:40,510
zolang ze niet null zijn, aan onze lijst

1007
01:18:40,510 --> 01:18:43,120
zodat we onvermijdelijk gaan over hen.

1008
01:18:43,120 --> 01:18:45,160
Dus als ze niet null,

1009
01:18:45,160 --> 01:18:47,950
als onze wortel wijzer wees naar twee dingen,

1010
01:18:47,950 --> 01:18:51,670
dan we in eerste instantie trok iets uit zodat onze lijst eindigt als null.

1011
01:18:51,670 --> 01:18:56,890
En dan zetten we twee dingen terug in, dus nu onze lijst is van maat 2.

1012
01:18:56,890 --> 01:19:00,030
Dan gaan we naar lus een back-up en we gaan gewoon te trekken,

1013
01:19:00,030 --> 01:19:04,250
laten we zeggen, de linker wijzer van onze root node.

1014
01:19:04,250 --> 01:19:07,730
En dat zal gewoon blijven gebeuren, we zullen uiteindelijk een lus over alles.

1015
01:19:07,730 --> 01:19:11,280
>> Merk op dat dit aanzienlijk gecompliceerder

1016
01:19:11,280 --> 01:19:14,160
in de recursieve oplossing.

1017
01:19:14,160 --> 01:19:17,260
En ik heb gezegd meerdere keren

1018
01:19:17,260 --> 01:19:25,120
de recursieve oplossing gewoonlijk veel gemeen met de iteratieve oplossing.

1019
01:19:25,120 --> 01:19:30,820
Hier dit is precies wat de recursieve oplossing aan het doen is.

1020
01:19:30,820 --> 01:19:36,740
De enige verandering is dat in plaats van impliciet gebruik van de stapel, het programma stack,

1021
01:19:36,740 --> 01:19:40,840
als uw manier van het bijhouden van wat knooppunten moet je nog om te bezoeken,

1022
01:19:40,840 --> 01:19:45,430
nu moet je expliciet gebruik van een gelinkte lijst.

1023
01:19:45,430 --> 01:19:49,070
In beide gevallen bent u het bijhouden van wat knooppunt nog moet worden bezocht.

1024
01:19:49,070 --> 01:19:51,790
In het recursieve geval het is gewoon makkelijker, omdat een stapel

1025
01:19:51,790 --> 01:19:57,100
is geïmplementeerd voor u als het programma stack.

1026
01:19:57,100 --> 01:19:59,550
Merk op dat deze verbonden lijst is een stapel.

1027
01:19:59,550 --> 01:20:01,580
Wat we gewoon op de stapel gelegd

1028
01:20:01,580 --> 01:20:09,960
is meteen wat we gaan te trekken uit de stapel naar de volgende te bezoeken.

1029
01:20:09,960 --> 01:20:14,380
We hebben geen tijd meer, maar vragen?

1030
01:20:14,380 --> 01:20:23,530
[Student, onverstaanbaar]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Ja. Dus als we onze gekoppelde lijst,

1032
01:20:27,790 --> 01:20:30,150
stroom gaat verwijzen naar deze man,

1033
01:20:30,150 --> 01:20:34,690
en nu zijn we gewoon het bevorderen van onze gelinkte lijst te richten op deze kerel.

1034
01:20:34,690 --> 01:20:44,200
We doorkruisen boven het gekoppelde lijst in die lijn.

1035
01:20:44,200 --> 01:20:51,200
En dan denk ik dat we moeten onze gelinkte lijst en dat soort dingen vrij

1036
01:20:51,200 --> 01:20:53,880
een keer voordat hij terugkeerde waar of onwaar, moeten we

1037
01:20:53,880 --> 01:20:57,360
itereren over onze gelinkte lijst en altijd hier beneden, denk ik,

1038
01:20:57,360 --> 01:21:03,900
Als we huidig ​​recht is niet gelijk aan, toevoegen, dus nu willen we bevrijden

1039
01:21:03,900 --> 01:21:09,600
huidig ​​omdat, nou ja, hebben we helemaal vergeten over de lijst? Ja.

1040
01:21:09,600 --> 01:21:12,880
Dus dat is wat we willen doen hier.

1041
01:21:12,880 --> 01:21:16,730
Waar is de pointer?

1042
01:21:16,730 --> 01:21:23,320
Cur was toen - we willen een struct lijst * 10 gelijk is aan de lijst volgende.

1043
01:21:23,320 --> 01:21:29,240
Vrije lijst, list = temp.

1044
01:21:29,240 --> 01:21:32,820
En in het geval waar we true retourneren, moeten we herhalen

1045
01:21:32,820 --> 01:21:37,050
over de rest van ons gelinkte lijst bevrijden dingen.

1046
01:21:37,050 --> 01:21:39,700
Het leuke van de recursieve oplossing is het vrijmaken van zaken

1047
01:21:39,700 --> 01:21:44,930
betekent gewoon knallen factorings uit de stapel die zal gebeuren voor je.

1048
01:21:44,930 --> 01:21:50,720
Dus we zijn gegaan van iets dat is net als 3 regels van hard-to-denken-over-code

1049
01:21:50,720 --> 01:21:57,520
om iets dat is aanzienlijk veel meer hard-aan-denken-over regels code.

1050
01:21:57,520 --> 01:22:00,620
Nog meer vragen?

1051
01:22:00,620 --> 01:22:08,760
Oke. We zijn goed. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]