1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Avsnitt 7: Bekvämare]

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

3
00:00:05,090 --> 00:00:07,930
[Detta är CS50] [CS50.TV]

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

5
00:00:10,110 --> 00:00:14,060
Detta kommer att bli en binär-träd-intensiva delen.

6
00:00:14,060 --> 00:00:16,820
Men det finns inte så många frågor.

7
00:00:16,820 --> 00:00:18,920
Så vi ska försöka dra ut varje fråga

8
00:00:18,920 --> 00:00:25,430
och gå in smärtsamma detalj alla de bästa sätten att göra saker.

9
00:00:25,430 --> 00:00:31,200
Så rätt från början, går vi igenom prov ritningar av binära träd och grejer.

10
00:00:31,200 --> 00:00:35,970
Så här: "Kom ihåg att ett binärt träd har noder som liknar en länkad lista,

11
00:00:35,970 --> 00:00:38,150
utom i stället för en pekare finns två: en för vänster "barn"

12
00:00:38,150 --> 00:00:41,950
och en för höger "barn". "

13
00:00:41,950 --> 00:00:45,630
Så ett binärt träd är precis som en länkad lista,

14
00:00:45,630 --> 00:00:47,910
utom struct kommer att få två pekare.

15
00:00:47,910 --> 00:00:51,390
Det finns trinary träd, som kommer att ha tre pekare,

16
00:00:51,390 --> 00:00:56,540
Det finns N-ari träd, som bara har en generisk pekare

17
00:00:56,540 --> 00:01:00,320
att du har sedan malloc vara stor nog att ha

18
00:01:00,320 --> 00:01:04,840
tillräckligt pekare till alla möjliga barn.

19
00:01:04,840 --> 00:01:08,200
Så binärt träd råkar bara ha ett konstant antal två.

20
00:01:08,200 --> 00:01:11,260
Om du vill kan du ge en länkad lista som unär träd,

21
00:01:11,260 --> 00:01:15,360
men jag tror inte att någon kallar det så.

22
00:01:15,360 --> 00:01:18,060
"Rita en lådor-och-pilar diagram över ett binärt träd nod

23
00:01:18,060 --> 00:01:24,110
innehåller Nates favoritnummer, 7, där varje barn pekare är null. "

24
00:01:24,110 --> 00:01:27,780
Så iPad läge.

25
00:01:27,780 --> 00:01:30,280
>> Det kommer att bli ganska enkelt.

26
00:01:30,280 --> 00:01:36,150
Vi bara kommer att ha en nod, jag drar det som en kvadrat.

27
00:01:36,150 --> 00:01:38,730
Och jag drar värdena här.

28
00:01:38,730 --> 00:01:41,090
Så värdet kommer att gå in här,

29
00:01:41,090 --> 00:01:44,770
och sedan ner hit kommer vi att ha den vänstra pekaren till vänster och höger pekaren till höger.

30
00:01:44,770 --> 00:01:50,430
Och det är väldigt mycket så konvention att kalla det vänster och höger, namnen pekaren.

31
00:01:50,430 --> 00:01:52,460
Båda dessa kommer att vara noll.

32
00:01:52,460 --> 00:01:57,870
Som bara kommer att bli noll, och det kommer bara vara noll.

33
00:01:57,870 --> 00:02:03,630
Okej. Så tillbaka till här.

34
00:02:03,630 --> 00:02:05,700
"Med en länkad lista, hade vi bara att lagra en pekare

35
00:02:05,700 --> 00:02:09,639
till den första noden i listan för att komma ihåg hela länkade listan, eller hela listan.

36
00:02:09,639 --> 00:02:11,650
Likaså med träd, har vi bara lagra en pekare

37
00:02:11,650 --> 00:02:13,420
till en enda nod för att minnas hela trädet.

38
00:02:13,420 --> 00:02:15,980
Denna nod är calle den "roten" av trädet.

39
00:02:15,980 --> 00:02:18,320
Bygg på diagrammet från före eller rita en ny

40
00:02:18,320 --> 00:02:21,690
så att du har en lådor-och-pilar skildring av ett binärt träd

41
00:02:21,690 --> 00:02:25,730
med värdet 7, sedan 3 i den vänstra,

42
00:02:25,730 --> 00:02:32,760
sedan 9 till höger, och sedan 6 till höger om 3. "

43
00:02:32,760 --> 00:02:34,810
Låt oss se om jag kan komma ihåg allt detta i mitt huvud.

44
00:02:34,810 --> 00:02:37,670
Så detta kommer att vara vår rot här uppe.

45
00:02:37,670 --> 00:02:41,600
Vi kommer att ha en viss pekare någonstans, något som vi kallar rot,

46
00:02:41,600 --> 00:02:45,140
och det är att peka på den här killen.

47
00:02:45,140 --> 00:02:48,490
Nu för att göra en ny nod,

48
00:02:48,490 --> 00:02:52,870
Vad har vi, 3 på vänster?

49
00:02:52,870 --> 00:02:57,140
Så en ny nod med 3, och det först pekar noll.

50
00:02:57,140 --> 00:02:59,190
Jag ska bara sätta N.

51
00:02:59,190 --> 00:03:02,250
Nu vill vi göra som går till vänster om 7.

52
00:03:02,250 --> 00:03:06,840
Så vi ändra pekaren till nu peka på den här killen.

53
00:03:06,840 --> 00:03:12,420
Och vi gör samma sak. Vi vill ha en 9 hit

54
00:03:12,420 --> 00:03:14,620
som initialt bara säger null.

55
00:03:14,620 --> 00:03:19,600
Vi kommer att ändra denna pekare, peka på 9,

56
00:03:19,600 --> 00:03:23,310
och nu vill vi sätta 6 till höger om 3.

57
00:03:23,310 --> 00:03:32,170
Så det kommer att - göra en 6.

58
00:03:32,170 --> 00:03:34,310
Och den killen kommer att peka dit.

59
00:03:34,310 --> 00:03:38,320
Okej. Så det är allt ber oss att göra.

60
00:03:38,320 --> 00:03:42,770
>> Nu ska vi gå igenom några terminologi.

61
00:03:42,770 --> 00:03:46,690
Vi pratade redan om hur trädets rot är den översta noden i trädet.

62
00:03:46,690 --> 00:03:54,720
Den som innehåller 7. Noderna vid botten av trädet kallas bladen.

63
00:03:54,720 --> 00:04:01,240
Varje nod som bara har noll som sina barn är ett löv.

64
00:04:01,240 --> 00:04:03,680
Så det är möjligt, om vår binära träd är bara en enda nod,

65
00:04:03,680 --> 00:04:10,130
att ett träd är ett löv, och det är det.

66
00:04:10,130 --> 00:04:12,060
"Den" höjd "av trädet är antalet hopp du måste göra

67
00:04:12,060 --> 00:04:16,620
att ta sig från toppen till ett löv. "

68
00:04:16,620 --> 00:04:18,640
Vi ska komma in i en andra, skillnaden

69
00:04:18,640 --> 00:04:21,940
mellan balanserade och obalanserade binära träd,

70
00:04:21,940 --> 00:04:29,470
men nu, den totala höjden av detta träd

71
00:04:29,470 --> 00:04:34,520
Jag skulle vilja säga är 3, men om man räknar antalet hopp

72
00:04:34,520 --> 00:04:39,710
du måste göra för att få till 9, då är det egentligen bara en höjd av 2.

73
00:04:39,710 --> 00:04:43,340
Just nu är detta en obalanserad binärt träd,

74
00:04:43,340 --> 00:04:49,840
men vi pratade om balanserad när det kommer till att vara relevanta.

75
00:04:49,840 --> 00:04:52,040
Så nu kan vi tala om noder i ett träd i termer

76
00:04:52,040 --> 00:04:54,700
förhållande till de andra noderna i trädet.

77
00:04:54,700 --> 00:04:59,730
Så nu har vi föräldrar, barn, syskon, förfäder och ättlingar.

78
00:04:59,730 --> 00:05:05,650
De är ganska sunt förnuft, vad de betyder.

79
00:05:05,650 --> 00:05:09,610
Om vi ​​frågar - det är föräldrar.

80
00:05:09,610 --> 00:05:12,830
Så vad är förälder till 3?

81
00:05:12,830 --> 00:05:16,090
[Studenter] 7. >> Ja. Den förälder bara kommer att vara vad pekar till dig.

82
00:05:16,090 --> 00:05:20,510
Vad är barn 7?

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

84
00:05:23,860 --> 00:05:26,460
Observera att "barn" bokstavligen betyder barn,

85
00:05:26,460 --> 00:05:31,010
så 6 skulle inte gälla, eftersom det är som ett barnbarn.

86
00:05:31,010 --> 00:05:35,540
Men om vi går ättlingar, så vad är ättlingar till 7?

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

88
00:05:37,500 --> 00:05:42,330
Ättlingar till rotnoden kommer att vara allt i trädet,

89
00:05:42,330 --> 00:05:47,950
utom kanske rotnoden själv, om du inte vill att anse att en ättling.

90
00:05:47,950 --> 00:05:50,750
Och slutligen, förfäder, så det är i motsatt riktning.

91
00:05:50,750 --> 00:05:55,740
Så vad är förfäder till 6?

92
00:05:55,740 --> 00:05:58,920
[Studenter] 3 och 7. >> Ja. 9 ingår inte.

93
00:05:58,920 --> 00:06:02,520
Det är bara den direkta släktlinje tillbaka till roten

94
00:06:02,520 --> 00:06:13,230
kommer att bli dina förfäder.

95
00:06:13,230 --> 00:06:16,300
>> "Vi säger att en binär träd" beställs "om för varje nod i trädet,

96
00:06:16,300 --> 00:06:19,530
alla sina ättlingar till vänster har mindre värden

97
00:06:19,530 --> 00:06:22,890
och alla de på rätt ha större värden.

98
00:06:22,890 --> 00:06:27,060
Till exempel trädet ovanför beställt men det är inte den enda möjliga beställt arrangemang. "

99
00:06:27,060 --> 00:06:30,180
Innan vi kommer till det,

100
00:06:30,180 --> 00:06:36,420
en ordnad binär träd är också känd som en binärt sökträd.

101
00:06:36,420 --> 00:06:38,660
Här har vi råkar kalla det en ordnad binärt träd,

102
00:06:38,660 --> 00:06:41,850
men jag har aldrig hört det kallas en ordnad binärt träd innan,

103
00:06:41,850 --> 00:06:46,650
och på en frågesport vi är mycket mer benägna att sätta binära sökträd.

104
00:06:46,650 --> 00:06:49,250
De är en och samma,

105
00:06:49,250 --> 00:06:54,580
och det är viktigt att du känner igen skillnaden mellan binära träd och binära sökträd.

106
00:06:54,580 --> 00:06:58,830
En binär träd är bara ett träd som pekar på två saker.

107
00:06:58,830 --> 00:07:02,120
Varje nod pekar på två saker.

108
00:07:02,120 --> 00:07:06,310
Det finns ingen resonemang om de värderingar som den pekar på.

109
00:07:06,310 --> 00:07:11,370
Så vill hit, eftersom det är ett binärt sökträd,

110
00:07:11,370 --> 00:07:14,030
Vi vet att om vi går till vänster om 7,

111
00:07:14,030 --> 00:07:16,670
då alla de värden som vi kan möjligen nå

112
00:07:16,670 --> 00:07:19,310
genom att gå till vänster om 7 måste vara mindre än 7.

113
00:07:19,310 --> 00:07:24,070
Lägg märke till att alla värden är mindre än 7 är 3 och 6.

114
00:07:24,070 --> 00:07:26,040
De är alla till vänster om 7.

115
00:07:26,040 --> 00:07:29,020
Om vi ​​går till höger om 7, har allt att vara större än 7,

116
00:07:29,020 --> 00:07:33,220
så 9 är till höger om 7, så vi är bra.

117
00:07:33,220 --> 00:07:36,150
Detta är inte fallet för ett binärt träd,

118
00:07:36,150 --> 00:07:40,020
för en vanlig binär träd kan vi bara ha 3 upptill, 7 till vänster,

119
00:07:40,020 --> 00:07:47,630
9 till vänster om 7, det finns ingen beställning av värden som helst.

120
00:07:47,630 --> 00:07:56,140
Nu kommer vi faktiskt inte göra detta eftersom det är jobbigt och onödigt,

121
00:07:56,140 --> 00:07:59,400
men "försök att dra så många beställda träd som du kan tänka dig

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

123
00:08:01,900 --> 00:08:06,800
Hur många distinkta arrangemang finns det? Vad är höjden av varje? "

124
00:08:06,800 --> 00:08:10,480
>> Vi gör ett par, men huvudtanken är,

125
00:08:10,480 --> 00:08:16,530
Detta är på intet sätt en unik representation av ett binärt träd som innehåller dessa värden.

126
00:08:16,530 --> 00:08:22,760
Allt vi behöver är lite binärt träd som innehåller 7, 3, 6 och 9.

127
00:08:22,760 --> 00:08:25,960
En annan möjlig giltigt skulle vara roten är 3,

128
00:08:25,960 --> 00:08:30,260
gå till vänster och det är 6, gå till vänster och det är 7,

129
00:08:30,260 --> 00:08:32,730
gå till vänster och det är 9.

130
00:08:32,730 --> 00:08:36,169
Det är ett fullvärdigt binärt sökträd.

131
00:08:36,169 --> 00:08:39,570
Det är inte till stor hjälp, eftersom det är precis som en länkad lista

132
00:08:39,570 --> 00:08:43,750
och alla dessa pekare är bara noll.

133
00:08:43,750 --> 00:08:48,900
Men det är en giltig träd. Ja?

134
00:08:48,900 --> 00:08:51,310
[Student] Inte värdena vara större på höger?

135
00:08:51,310 --> 00:08:56,700
Eller är det -? >> De jag menade att gå åt andra hållet.

136
00:08:56,700 --> 00:09:00,960
Det finns också - ja, låt oss byta det.

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

138
00:09:07,770 --> 00:09:11,730
Det har fortfarande lyda vad en binär träd sökning är tänkt att göra.

139
00:09:11,730 --> 00:09:15,650
Så allt till vänster måste vara mindre än en given nod.

140
00:09:15,650 --> 00:09:23,180
Vi kan bara flytta, säga, detta 6 och lägga den här.

141
00:09:23,180 --> 00:09:26,880
Nej, det kan vi inte. Varför får jag göra det?

142
00:09:26,880 --> 00:09:35,350
Låt oss göra - här är 6, här är 7, 6 punkter till 3.

143
00:09:35,350 --> 00:09:39,290
Detta är fortfarande ett giltigt binärt sökträd.

144
00:09:39,290 --> 00:09:49,260
Vad är det för fel om jag - låt oss se om jag kan komma med ett arrangemang.

145
00:09:49,260 --> 00:09:52,280
Ja, okej. Så vad är fel med det här trädet?

146
00:09:52,280 --> 00:10:08,920
Jag antar att jag redan har gett dig en vink om att det är något fel med det.

147
00:10:08,920 --> 00:10:14,430
Varför får jag göra det?

148
00:10:14,430 --> 00:10:18,510
Okej. Detta ser rimligt.

149
00:10:18,510 --> 00:10:22,590
Om vi ​​tittar på varje nod, såsom 7, sedan till vänster om 7 är en 3.

150
00:10:22,590 --> 00:10:24,960
Så vi har 3, är den sak till höger om 3 a 6.

151
00:10:24,960 --> 00:10:27,750
Och om man tittar på 6, är saken till höger om 6 a 9.

152
00:10:27,750 --> 00:10:30,910
Så varför är detta inte ett giltigt binärt sökträd?

153
00:10:30,910 --> 00:10:36,330
[Studenter] 9 är fortfarande till vänster om 7. >> Ja.

154
00:10:36,330 --> 00:10:43,710
Det måste vara sant att alla värden som du kan möjligen nå genom att gå till vänster om 7 är mindre än 7.

155
00:10:43,710 --> 00:10:49,120
Om vi ​​går till vänster om 7 får vi till 3 och vi kan fortfarande få till 6,

156
00:10:49,120 --> 00:10:52,520
vi kan fortfarande få till 9, men genom att ha gått mindre än 7,

157
00:10:52,520 --> 00:10:55,070
Vi bör inte kunna få till ett antal som är större än 7.

158
00:10:55,070 --> 00:10:59,830
Så detta är inte en giltig binärt sökträd.

159
00:10:59,830 --> 00:11:02,330
>> Min bror hade faktiskt en intervju fråga

160
00:11:02,330 --> 00:11:07,760
som var i princip detta, bara kod upp något för att validera

161
00:11:07,760 --> 00:11:10,500
om ett träd är ett binärt sökträd,

162
00:11:10,500 --> 00:11:13,580
och så det första han gjorde var bara kontrollera

163
00:11:13,580 --> 00:11:17,020
Om vänster och höger är korrekta, och sedan iterera nere.

164
00:11:17,020 --> 00:11:19,700
Men du kan inte bara göra det, du måste hålla reda

165
00:11:19,700 --> 00:11:22,550
det faktum att nu när jag har gått till vänster om 7,

166
00:11:22,550 --> 00:11:26,340
allt i denna underträdet måste vara mindre än 7.

167
00:11:26,340 --> 00:11:28,430
Den korrekta algoritmen måste hålla reda

168
00:11:28,430 --> 00:11:35,970
av gränserna att värdena möjligen kan falla i.

169
00:11:35,970 --> 00:11:38,360
Vi kommer inte att gå igenom dem alla.

170
00:11:38,360 --> 00:11:41,630
Det finns en trevlig upprepning relation,

171
00:11:41,630 --> 00:11:44,810
Även om vi inte har kommit till dem, annars kommer vi inte att få dem,

172
00:11:44,810 --> 00:11:47,030
definiera hur många det egentligen är.

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

174
00:11:53,180 --> 00:11:56,020
Idén om hur du skulle göra det är matematiskt som,

175
00:11:56,020 --> 00:11:59,770
Du kan välja en enda en som rotnoden,

176
00:11:59,770 --> 00:12:03,160
och sedan om jag plockar 7 är rotnoden,

177
00:12:03,160 --> 00:12:08,150
då det finns, säger vissa siffror som kan gå bli min vänstra nod,

178
00:12:08,150 --> 00:12:10,440
och det finns några siffror som kan vara min högra nod,

179
00:12:10,440 --> 00:12:15,090
men om jag har n totala antalet, då det belopp som kan gå till vänster

180
00:12:15,090 --> 00:12:18,820
plus det belopp som kan gå till höger N - 1.

181
00:12:18,820 --> 00:12:26,130
Så av de återstående siffrorna, måste de kunna gå antingen till vänster eller till höger.

182
00:12:26,130 --> 00:12:31,580
Det verkar svårt att om jag sätter 3 först sedan allt måste gå till vänster,

183
00:12:31,580 --> 00:12:35,080
men om jag sätter 7, så vissa saker kan gå vänster och vissa saker kan gå till höger.

184
00:12:35,080 --> 00:12:39,570
Och med '3 första "jag menade allt kan gå åt höger.

185
00:12:39,570 --> 00:12:42,350
Det är verkligen, du måste bara tänka på det som,

186
00:12:42,350 --> 00:12:47,980
hur många saker kan gå på nästa nivå i trädet.

187
00:12:47,980 --> 00:12:50,420
Och det kommer ut att vara 14, eller så kan du rita dem alla,

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

189
00:12:54,650 --> 00:13:01,120
>> Gå tillbaka hit,

190
00:13:01,120 --> 00:13:03,510
"Beställda binära träd är cool eftersom vi kan söka igenom dem

191
00:13:03,510 --> 00:13:06,910
på ett mycket liknande sätt att söka på en sorterad array.

192
00:13:06,910 --> 00:13:10,120
För att göra det, börjar vi vid roten och arbeta oss ned trädet

193
00:13:10,120 --> 00:13:13,440
mot löv, kontroll varje nod värderingar mot de värden vi söker.

194
00:13:13,440 --> 00:13:15,810
Om det aktuella nodens värde är mindre än det värde vi letar efter,

195
00:13:15,810 --> 00:13:18,050
du går bredvid nodens högra barn.

196
00:13:18,050 --> 00:13:20,030
Annars går du till nodens vänstra barn.

197
00:13:20,030 --> 00:13:22,800
Vid något tillfälle hittar du antingen värdet du söker, eller du kommer att stöta på en nolla,

198
00:13:22,800 --> 00:13:28,520
anger värdet är inte i trädet. "

199
00:13:28,520 --> 00:13:32,450
Jag måste rita trädet vi hade tidigare, det tar en sekund.

200
00:13:32,450 --> 00:13:38,280
Men vi vill slå upp om 6, 10 och 1 i trädet.

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

202
00:13:49,180 --> 00:13:52,730
De nummer du vill slå upp, vill vi slå upp 6.

203
00:13:52,730 --> 00:13:55,440
Hur fungerar denna algoritm arbete?

204
00:13:55,440 --> 00:14:03,040
Tja, vi har också några rot pekare till vårt träd.

205
00:14:03,040 --> 00:14:12,460
Och vi skulle gå till roten och säga, är detta värde lika med det värde vi söker efter?

206
00:14:12,460 --> 00:14:15,000
Så vi letar efter 6, så det är inte lika.

207
00:14:15,000 --> 00:14:20,140
Så vi fortsätta, och nu säger vi, okej, så 6 är mindre än 7.

208
00:14:20,140 --> 00:14:23,940
Betyder det att vi vill gå åt vänster, eller vill vi gå till höger?

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

210
00:14:27,340 --> 00:14:33,340
Det är betydligt lättare, är rita allt du behöver göra en möjlig nod i trädet

211
00:14:33,340 --> 00:14:37,760
och sedan inte - istället för att försöka tänka i huvudet,

212
00:14:37,760 --> 00:14:40,020
Okej, om det är mindre, går jag åt vänster eller gå till höger,

213
00:14:40,020 --> 00:14:43,030
bara tittar på den här bilden, det är mycket tydligt att jag måste gå till vänster

214
00:14:43,030 --> 00:14:47,700
Om denna nod är större än det värde som jag letar efter.

215
00:14:47,700 --> 00:14:52,600
Så du går till vänster, nu är jag på 3.

216
00:14:52,600 --> 00:14:57,770
Jag vill - 3 är mindre än värdet jag söker, vilket är 6.

217
00:14:57,770 --> 00:15:03,420
Så vi gå till höger, och nu har jag hamnar på 6,

218
00:15:03,420 --> 00:15:07,380
vilket är det värde som jag letar efter, så jag återkommer sant.

219
00:15:07,380 --> 00:15:15,760
Nästa värde jag ska leta efter är 10.

220
00:15:15,760 --> 00:15:23,230
Okej. Så 10, nu kommer att - avskuren att - kommer att följa roten.

221
00:15:23,230 --> 00:15:27,670
Nu är 10 kommer att vara större än 7, så jag vill se till höger.

222
00:15:27,670 --> 00:15:31,660
Jag kommer att komma hit är 10 kommer att vara större än 9,

223
00:15:31,660 --> 00:15:34,520
så jag kommer att vilja se till höger.

224
00:15:34,520 --> 00:15:42,100
Jag kom hit, men hit nu är jag på noll.

225
00:15:42,100 --> 00:15:44,170
Vad gör jag om jag slog noll?

226
00:15:44,170 --> 00:15:47,440
[Student] Tillbaka falskt? >> Ja. Jag hittade inte 10.

227
00:15:47,440 --> 00:15:49,800
1 kommer att bli en nästan identisk fall,

228
00:15:49,800 --> 00:15:51,950
förutom att det är bara att vändas, istället för att titta

229
00:15:51,950 --> 00:15:56,540
ner till höger, ska jag titta ner till vänster.

230
00:15:56,540 --> 00:16:00,430
>> Nu tror jag att vi faktiskt få till koden.

231
00:16:00,430 --> 00:16:04,070
Här är där - öppna CS50 apparaten och navigera dig fram dit,

232
00:16:04,070 --> 00:16:07,010
men du kan också bara göra det i utrymmet.

233
00:16:07,010 --> 00:16:09,170
Det är nog perfekt att göra det i det utrymme,

234
00:16:09,170 --> 00:16:13,760
eftersom vi kan arbeta i utrymmet.

235
00:16:13,760 --> 00:16:19,170
"Först ska vi behöva en ny typ definition ett binärt träd nod innehåller int värden.

236
00:16:19,170 --> 00:16:21,400
Använda standardtext typedef nedan,

237
00:16:21,400 --> 00:16:24,510
skapa en ny typ definition för en nod i ett binärt träd.

238
00:16:24,510 --> 00:16:27,930
Om du fastnar. . . "Bla, bla, bla. Okej.

239
00:16:27,930 --> 00:16:30,380
Så låt oss sätta standardtext här,

240
00:16:30,380 --> 00:16:41,630
typedef struct nod, och noden. Ja, okej.

241
00:16:41,630 --> 00:16:44,270
Så vad är de områden vi kommer att ha i vår nod?

242
00:16:44,270 --> 00:16:46,520
[Student] Int och därefter två pekare?

243
00:16:46,520 --> 00:16:49,700
>> Int värde, två pekare? Hur skriver jag pekare?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. >> Jag zooma in Ja, så struct nod * vänster,

245
00:16:58,440 --> 00:17:01,320
och struct nod * rätt.

246
00:17:01,320 --> 00:17:03,460
Och kom ihåg diskussionen från förra gången,

247
00:17:03,460 --> 00:17:15,290
att detta är meningslöst, gör ingen mening,

248
00:17:15,290 --> 00:17:18,270
detta är meningslöst.

249
00:17:18,270 --> 00:17:25,000
Du behöver allt det för att definiera denna rekursiva struktur.

250
00:17:25,000 --> 00:17:27,970
Okej, så det är vad vi trädet kommer att se ut.

251
00:17:27,970 --> 00:17:37,670
Om vi ​​gjorde en trinary träd, sedan en nod kan se ut b1, b2, struct nod * b3,

252
00:17:37,670 --> 00:17:43,470
där b är en gren - faktiskt, jag har mer hört det vänster, mitten, höger, men oavsett.

253
00:17:43,470 --> 00:17:55,610
Vi bara bryr sig om binär, så rätt, vänster.

254
00:17:55,610 --> 00:17:59,110
"Nu deklarerar en global variabel nod * för roten av trädet."

255
00:17:59,110 --> 00:18:01,510
Så vi inte kommer att göra det.

256
00:18:01,510 --> 00:18:08,950
För att göra saker och ting lite svårare och mer allmänt,

257
00:18:08,950 --> 00:18:11,570
Vi kommer inte att ha en global nod variabel.

258
00:18:11,570 --> 00:18:16,710
Istället för stora kommer vi att förklara alla våra nod saker,

259
00:18:16,710 --> 00:18:20,500
och det betyder att nedan när vi börjar köra

260
00:18:20,500 --> 00:18:23,130
våra Innehåller funktion och vår insats funktion,

261
00:18:23,130 --> 00:18:27,410
istället för våra CONTAINS, funktion bara använda denna globala nod variabel,

262
00:18:27,410 --> 00:18:34,280
vi kommer att få det ta som argument trädet som vi vill att det ska bearbeta.

263
00:18:34,280 --> 00:18:36,650
Med den globala variabeln skulle göra det lättare.

264
00:18:36,650 --> 00:18:42,310
Vi kommer att göra saker svårare.

265
00:18:42,310 --> 00:18:51,210
Nu tar en minut eller så att bara göra den här sortens saker,

266
00:18:51,210 --> 00:18:57,690
där insidan av huvud du vill skapa detta träd, och det är allt du vill göra.

267
00:18:57,690 --> 00:19:04,530
Prova och konstruera detta träd i din huvudsakliga funktion.

268
00:19:42,760 --> 00:19:47,610
>> Okej. Så du behöver inte ens ha konstruerat trädet hela vägen ännu.

269
00:19:47,610 --> 00:19:49,840
Men någon har något jag kunde dra upp

270
00:19:49,840 --> 00:20:03,130
att visa hur man kan börja bygga ett sådant träd?

271
00:20:03,130 --> 00:20:08,080
[Student] Någons banka, försöker få ut.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Alla bekväm med deras träd konstruktion?

273
00:20:13,100 --> 00:20:15,520
[Student] Visst. Det är inte gjort. >> Det är bra. Vi kan bara avsluta -

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

275
00:20:26,860 --> 00:20:32,020
Så här har vi - Åh, jag lite avskurna.

276
00:20:32,020 --> 00:20:34,770
Jag zoomat in?

277
00:20:34,770 --> 00:20:37,730
Zooma in genom att bläddra ut. >> Jag har en fråga. >> Ja?

278
00:20:37,730 --> 00:20:44,410
[Student] När du definierar struct, är saker som initieras till något?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Nej >> Okej. Så du måste initiera -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Nej När du definierar eller när du deklarerar en struct,

281
00:20:50,450 --> 00:20:55,600
det är inte initieras som standard, det är precis som om du deklarerar en int.

282
00:20:55,600 --> 00:20:59,020
Det är exakt samma sak. Det är som alla sina enskilda fält

283
00:20:59,020 --> 00:21:04,460
kan ha ett skräp värde i det. >> Och är det möjligt att definiera - eller att förklara en struktur

284
00:21:04,460 --> 00:21:07,740
på ett sådant sätt att den gör initiera dem?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ja. Så genväg initiering syntax

286
00:21:13,200 --> 00:21:18,660
kommer att se ut -

287
00:21:18,660 --> 00:21:22,200
Det finns två sätt vi kan göra det här. Jag tycker vi ska sammanställa den

288
00:21:22,200 --> 00:21:25,840
att se till att klang också gör detta.

289
00:21:25,840 --> 00:21:28,510
Ordningen på argumenten som kommer i struct,

290
00:21:28,510 --> 00:21:32,170
du sätter som ordningen av argument inom dessa klammerparenteser.

291
00:21:32,170 --> 00:21:35,690
Så om du vill att initiera den till 9 och vänster vara NULL och högerklicka vara noll,

292
00:21:35,690 --> 00:21:41,570
skulle det vara 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternativet är, och redaktören inte gillar denna syntax,

294
00:21:47,890 --> 00:21:50,300
och det tror jag vill ha ett nytt block,

295
00:21:50,300 --> 00:22:01,800
men alternativet är något som -

296
00:22:01,800 --> 00:22:04,190
Här ska jag lägga den på en ny rad.

297
00:22:04,190 --> 00:22:09,140
Du uttryckligen säga, jag glömmer den exakta syntaxen.

298
00:22:09,140 --> 00:22:13,110
Så du kan explicit ta dem vid namn och säga,

299
00:22:13,110 --> 00:22:21,570
. C eller. Värde = 9,. Vänster = NULL.

300
00:22:21,570 --> 00:22:24,540
Jag gissar dessa måste vara kommatecken.

301
00:22:24,540 --> 00:22:29,110
. Höger = NULL, så detta sätt behöver du inte

302
00:22:29,110 --> 00:22:33,780
faktiskt behöver veta ordningen för struct,

303
00:22:33,780 --> 00:22:36,650
och när du läser detta, det är mycket tydligare

304
00:22:36,650 --> 00:22:41,920
om vad värdet är som initieras till.

305
00:22:41,920 --> 00:22:44,080
>> Det råkar vara en av de saker som -

306
00:22:44,080 --> 00:22:49,100
så, för det mesta, C + + är ett superset av C.

307
00:22:49,100 --> 00:22:54,160
Du kan ta C-kod, flytta den till C + +, och det bör sammanställa.

308
00:22:54,160 --> 00:22:59,570
Detta är en av de saker som C + + inte stöder, så att folk tenderar att inte göra det.

309
00:22:59,570 --> 00:23:01,850
Jag vet inte om det är den enda anledningen människor tenderar att inte göra det,

310
00:23:01,850 --> 00:23:10,540
men fallet där jag behövde använda den behövde för att arbeta med C + + och så jag inte kunde använda det.

311
00:23:10,540 --> 00:23:14,000
Ett annat exempel på något som inte fungerar med C + + är

312
00:23:14,000 --> 00:23:16,940
hur malloc returnerar ett "tomrum *," tekniskt,

313
00:23:16,940 --> 00:23:20,200
men du kan bara säga char * x = malloc helst,

314
00:23:20,200 --> 00:23:22,840
och det kommer automatiskt att kastas till en char *.

315
00:23:22,840 --> 00:23:25,450
Det automatiska rösterna inte hända i C + +.

316
00:23:25,450 --> 00:23:28,150
Det skulle inte kompilera, och du skulle uttryckligen måste säga

317
00:23:28,150 --> 00:23:34,510
char *, malloc, vad som helst, för att kasta den till en char *.

318
00:23:34,510 --> 00:23:37,270
Det finns inte många saker som C och C + + inte håller på,

319
00:23:37,270 --> 00:23:40,620
men de är två.

320
00:23:40,620 --> 00:23:43,120
Så vi ska gå med denna syntax.

321
00:23:43,120 --> 00:23:46,150
Men även om vi inte gick med den syntax,

322
00:23:46,150 --> 00:23:49,470
vad är - kan vara fel med det?

323
00:23:49,470 --> 00:23:52,170
[Student] Jag behöver inte dereference det? >> Ja.

324
00:23:52,170 --> 00:23:55,110
Kom ihåg att pilen har en implicit dereference,

325
00:23:55,110 --> 00:23:58,230
och så när vi bara göra med en struktur,

326
00:23:58,230 --> 00:24:04,300
vi vill använda. att komma åt ett fält inne i struct.

327
00:24:04,300 --> 00:24:07,200
Och den enda gången vi använder pil är när vi vill göra -

328
00:24:07,200 --> 00:24:13,450
bra, är pilen motsvarar -

329
00:24:13,450 --> 00:24:17,020
det är vad det skulle ha inneburit att jag använt pil.

330
00:24:17,020 --> 00:24:24,600
Allt pil betyder är, dereference detta, nu är jag på en struct, och jag kan få på fältet.

331
00:24:24,600 --> 00:24:28,040
Antingen får fältet direkt eller dereference och få fältet -

332
00:24:28,040 --> 00:24:30,380
Jag antar att detta borde vara värde.

333
00:24:30,380 --> 00:24:33,910
Men här jag har att göra med bara en struct, inte en pekare till en struct,

334
00:24:33,910 --> 00:24:38,780
så jag kan inte använda pilen.

335
00:24:38,780 --> 00:24:47,510
Men den här sortens saker vi kan göra för alla noder.

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

337
00:24:55,790 --> 00:25:09,540
Detta är 6, 7, och 3.

338
00:25:09,540 --> 00:25:16,470
Då kan vi ställa upp filialer i vår träd, kan vi 7 -

339
00:25:16,470 --> 00:25:21,650
vi kan ha, bör dess vänstra peka till 3.

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

341
00:25:25,130 --> 00:25:29,320
[Studenter, obegripligt] >> yeah. Adressen till node3,

342
00:25:29,320 --> 00:25:34,170
och om du inte har adress, då det bara inte skulle kompilera.

343
00:25:34,170 --> 00:25:38,190
Men kom ihåg att detta är pekare till nästa noder.

344
00:25:38,190 --> 00:25:44,930
Den rätt bör peka på 9,

345
00:25:44,930 --> 00:25:53,330
och 3 skall peka på rätt till 6.

346
00:25:53,330 --> 00:25:58,480
Jag tror att det är redo. Några kommentarer eller frågor?

347
00:25:58,480 --> 00:26:02,060
[Student, obegripligt] Roten kommer att bli 7.

348
00:26:02,060 --> 00:26:08,210
Vi kan bara säga nod * PTR =

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

350
00:26:14,160 --> 00:26:20,730
>> För våra syften kommer vi att göra med insats,

351
00:26:20,730 --> 00:26:25,490
så vi kommer att vilja skriva en funktion för att infoga i denna binära träd

352
00:26:25,490 --> 00:26:34,230
och insatsen oundvikligen kommer att ringa malloc för att skapa en ny nod för detta träd.

353
00:26:34,230 --> 00:26:36,590
Så det kommer att bli rörigt med det faktum att vissa noder

354
00:26:36,590 --> 00:26:38,590
närvarande på stacken

355
00:26:38,590 --> 00:26:43,680
och andra noder kommer att hamna på högen när vi sätter dem.

356
00:26:43,680 --> 00:26:47,640
Det är helt giltigt, men den enda anledningen

357
00:26:47,640 --> 00:26:49,600
vi kan göra detta på stacken

358
00:26:49,600 --> 00:26:51,840
är att det är en så krystat exempel som vi vet

359
00:26:51,840 --> 00:26:56,360
trädet är tänkt att konstrueras som 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Om vi ​​inte hade det, så skulle vi inte behöva malloc i första hand.

361
00:27:02,970 --> 00:27:06,160
Som vi ser lite senare, bör vi malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Just nu är det helt rimligt att sätta på stacken,

363
00:27:08,570 --> 00:27:14,750
men låt oss ändra detta till en malloc genomförande.

364
00:27:14,750 --> 00:27:17,160
Så alla dessa kommer nu att bli något liknande

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

366
00:27:24,240 --> 00:27:28,040
Och nu ska vi få göra vår kontroll.

367
00:27:28,040 --> 00:27:34,010
if (node9 == null) - Jag ville inte att -

368
00:27:34,010 --> 00:27:40,950
tillbaka 1, och då kan vi göra node9-> för nu är det en pekare,

369
00:27:40,950 --> 00:27:45,300
värde = 6, node9-> vänster = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> höger = NULL,

371
00:27:48,930 --> 00:27:51,410
och vi kommer att behöva göra det för var och en av dessa noder.

372
00:27:51,410 --> 00:27:57,490
Så istället, låt oss uttrycka det inuti en separat funktion.

373
00:27:57,490 --> 00:28:00,620
Låt oss kalla det nod * build_node,

374
00:28:00,620 --> 00:28:09,050
och detta är något liknar API ger vi för Huffmankodning.

375
00:28:09,050 --> 00:28:12,730
Vi ger dig initierare funktioner för ett träd

376
00:28:12,730 --> 00:28:20,520
och Deconstructor "funktioner" för dessa träd och samma för skogarna.

377
00:28:20,520 --> 00:28:22,570
>> Så här ska vi ha en initierare funktion

378
00:28:22,570 --> 00:28:25,170
att bara bygga en nod för oss.

379
00:28:25,170 --> 00:28:29,320
Och det kommer att se ut ganska precis så här.

380
00:28:29,320 --> 00:28:32,230
Och jag ens kommer att vara lata och inte ändra namnet på variabeln,

381
00:28:32,230 --> 00:28:34,380
trots node9 är ingen mening längre.

382
00:28:34,380 --> 00:28:38,610
Åh, jag antar node9 värde borde inte ha varit 6.

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

384
00:28:42,800 --> 00:28:49,550
Och här bör vi returnera null.

385
00:28:49,550 --> 00:28:52,690
Alla är överens om att bygg-en-nod funktion?

386
00:28:52,690 --> 00:28:59,780
Så nu kan vi bara kalla det för att bygga en nod med ett givet värde och noll pekare.

387
00:28:59,780 --> 00:29:09,750
Nu kan vi kalla det, kan vi göra nod * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Och låt oss göra. . .

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

390
00:29:33,980 --> 00:29:39,330
Och nu vill vi skapa samma pekare,

391
00:29:39,330 --> 00:29:42,470
utom nu allt är redan i form av pekare

392
00:29:42,470 --> 00:29:48,480
så behöver inte längre adressen.

393
00:29:48,480 --> 00:29:56,300
Okej. Så vad är det sista jag vill göra?

394
00:29:56,300 --> 00:30:03,850
Det finns en felkontroll som jag inte gör.

395
00:30:03,850 --> 00:30:06,800
Vad bygger nod tillbaka?

396
00:30:06,800 --> 00:30:11,660
[Student, obegripligt] >> Ja. Om malloc misslyckades, det ska returnera null.

397
00:30:11,660 --> 00:30:16,460
Så jag ska lättjefullt lägga ner hit istället för att göra en förutsättning för varje.

398
00:30:16,460 --> 00:30:22,320
Om (node9 == NULL, eller - ännu enklare,

399
00:30:22,320 --> 00:30:28,020
Detta motsvarar bara om inte node9.

400
00:30:28,020 --> 00:30:38,310
Så om inte node9 eller inte node6 eller inte node3, eller inte node7, returnera 1.

401
00:30:38,310 --> 00:30:42,850
Vi kanske bör skriva ut malloc misslyckades, eller något.

402
00:30:42,850 --> 00:30:46,680
[Student] är falskt lika med noll också?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Alla nollvärde är falsk.

404
00:30:51,290 --> 00:30:53,920
Så null är ett nollvärde.

405
00:30:53,920 --> 00:30:56,780
Noll är ett nollvärde. Falskt är ett nollvärde.

406
00:30:56,780 --> 00:31:02,130
Varje - ganska mycket bara 2 noll värden är noll och noll,

407
00:31:02,130 --> 00:31:07,900
falskt är bara hash definieras som noll.

408
00:31:07,900 --> 00:31:13,030
Detta gäller även om vi deklarerar global variabel.

409
00:31:13,030 --> 00:31:17,890
Om vi ​​hade rotnoden * här uppe,

410
00:31:17,890 --> 00:31:24,150
då - det fina med globala variabler är att de alltid har ett initialt värde.

411
00:31:24,150 --> 00:31:27,500
Det är inte sant funktioner, hur insidan av här,

412
00:31:27,500 --> 00:31:34,870
om vi har, liksom, nod * eller x noden.

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

414
00:31:37,380 --> 00:31:40,700
eller vi kunde skriva ut dem och de kan vara godtyckligt.

415
00:31:40,700 --> 00:31:44,980
Det är inte sant för globala variabler.

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

417
00:31:47,450 --> 00:31:53,410
Som standard, allt som är global, om inte uttryckligen initialiseras till något värde,

418
00:31:53,410 --> 00:31:57,390
har ett nollvärde som dess värde.

419
00:31:57,390 --> 00:32:01,150
Så här, nod * rot vi inte uttryckligen initiera den till något,

420
00:32:01,150 --> 00:32:06,350
så standardvärdet är noll, vilket är nollvärdet av pekare.

421
00:32:06,350 --> 00:32:11,870
Det förvalda värdet på x kommer att betyda att x.value är noll,

422
00:32:11,870 --> 00:32:14,260
x.left är null, och x.right är null.

423
00:32:14,260 --> 00:32:21,070
Så eftersom det är en struct kommer alla fälten i struct vara nollvärden.

424
00:32:21,070 --> 00:32:24,410
Vi behöver inte använda det här, men.

425
00:32:24,410 --> 00:32:27,320
[Student] De structs är annorlunda än andra variabler, och de andra variablerna är

426
00:32:27,320 --> 00:32:31,400
sopor värden, dessa är nollor?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Andra värden också. Så i x, kommer x att vara noll.

428
00:32:36,220 --> 00:32:40,070
Om det är på global räckvidd, har den ett initialt värde. >> Okej.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Antingen ursprungliga värdet du gav det eller noll.

430
00:32:48,950 --> 00:32:53,260
Jag tror att tar hand om allt detta.

431
00:32:53,260 --> 00:32:58,390
>> Okej. Så nästa del av frågan frågar

432
00:32:58,390 --> 00:33:01,260
"Nu vill vi skriva en funktion som kallas innehåller

433
00:33:01,260 --> 00:33:04,930
med en prototyp av bool innehåller int värde. "

434
00:33:04,930 --> 00:33:08,340
Vi kommer inte att göra bool innehåller int värde.

435
00:33:08,340 --> 00:33:15,110
Vår prototyp kommer att se ut

436
00:33:15,110 --> 00:33:22,380
bool innehåller (int värde.

437
00:33:22,380 --> 00:33:24,490
Och då vi också kommer att passera den trädet

438
00:33:24,490 --> 00:33:28,870
att det bör kontrollera att se om den har värdet.

439
00:33:28,870 --> 00:33:38,290
Så nod * träd). Okej.

440
00:33:38,290 --> 00:33:44,440
Och då kan vi kalla det med något som,

441
00:33:44,440 --> 00:33:46,090
kanske vi kommer att vilja printf eller något.

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

443
00:33:51,040 --> 00:33:54,300
Det skulle återvända en eller sann,

444
00:33:54,300 --> 00:33:59,390
medan innehåller 5 rot ska returnera false.

445
00:33:59,390 --> 00:34:02,690
Så ta en sekund för att genomföra detta.

446
00:34:02,690 --> 00:34:06,780
Du kan göra det antingen iterativt eller rekursivt.

447
00:34:06,780 --> 00:34:09,739
Det fina med hur vi har ställt upp saker är att

448
00:34:09,739 --> 00:34:12,300
det lämpar sig för vår rekursiva lösning mycket enklare

449
00:34:12,300 --> 00:34:14,719
än det globala variabel sätt gjorde.

450
00:34:14,719 --> 00:34:19,750
För om vi bara har innehåller int värde, så har vi inget sätt att recursing ner underträd.

451
00:34:19,750 --> 00:34:24,130
Vi skulle behöva ha en separat hjälpare funktion som recurses ner underträd för oss.

452
00:34:24,130 --> 00:34:29,610
Men eftersom vi har ändrat den för att ta trädet som ett argument,

453
00:34:29,610 --> 00:34:32,760
som det borde ha varit alltid i första hand,

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

455
00:34:35,710 --> 00:34:38,960
Så iterativ eller rekursiv, kommer vi att gå över båda,

456
00:34:38,960 --> 00:34:46,139
men vi får se till att rekursiva hamnar är ganska lätt.

457
00:34:59,140 --> 00:35:02,480
Okej. Har någon något vi kan arbeta med?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Jag har en iterativ lösning. >> Okej, iterativ.

459
00:35:12,000 --> 00:35:16,030
Okej, här ser bra ut.

460
00:35:16,030 --> 00:35:18,920
Så vill gå oss igenom det?

461
00:35:18,920 --> 00:35:25,780
[Student] Visst. Så jag satt en temp variabel för att få den första noden i trädet.

462
00:35:25,780 --> 00:35:28,330
Och sedan jag loopas bara genom medan temp inte är lika null,

463
00:35:28,330 --> 00:35:31,700
så medan var fortfarande i trädet, antar jag.

464
00:35:31,700 --> 00:35:35,710
Och om värdet är lika med det värde som temp pekar på,

465
00:35:35,710 --> 00:35:37,640
då det returnerar värdet.

466
00:35:37,640 --> 00:35:40,210
Annars kontrollerar det om det är på höger eller vänster sida.

467
00:35:40,210 --> 00:35:43,400
Om du någonsin få en situation där det inte finns någon mer träd,

468
00:35:43,400 --> 00:35:47,330
då återgår - den lämnar slingan och returnerar false.

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

470
00:35:52,190 --> 00:35:58,470
Någon har några synpunkter på något?

471
00:35:58,470 --> 00:36:02,400
Jag har ingen korrekthet kommentarer alls.

472
00:36:02,400 --> 00:36:11,020
Det enda vi kan göra är den här killen.

473
00:36:11,020 --> 00:36:21,660
Åh, det kommer att gå lite långsträckta.

474
00:36:21,660 --> 00:36:33,460
Jag fixar upp det. Okej.

475
00:36:33,460 --> 00:36:37,150
>> Alla borde komma ihåg hur ternära fungerar.

476
00:36:37,150 --> 00:36:38,610
Det har definitivt varit frågesporter i det förflutna

477
00:36:38,610 --> 00:36:41,170
som ger dig en funktion med en ternär operatör,

478
00:36:41,170 --> 00:36:45,750
och säga, översätter detta, göra något som inte använder ternära.

479
00:36:45,750 --> 00:36:49,140
Så detta är en mycket vanlig fråga om när jag skulle tro att använda ternära,

480
00:36:49,140 --> 00:36:54,610
där om någon villkoret en variabel till något,

481
00:36:54,610 --> 00:36:58,580
annars satt samma variabel till något annat.

482
00:36:58,580 --> 00:37:03,390
Det är något som mycket ofta kan omvandlas till något sådant

483
00:37:03,390 --> 00:37:14,420
där satt den variabeln på detta - eller, ja, är detta sant? Då är detta, annars här.

484
00:37:14,420 --> 00:37:18,550
[Student] Den första är om detta är sant, eller hur?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Ja. Det sätt jag alltid läsa det är lika temp värde större än temp värde,

486
00:37:25,570 --> 00:37:30,680
då detta, annars här. Det ställer en fråga.

487
00:37:30,680 --> 00:37:35,200
Är det större? Gör sedan det första. Annan göra den andra saken.

488
00:37:35,200 --> 00:37:41,670
Jag nästan alltid - tjocktarmen, jag bara - i mitt huvud, läste jag som annars.

489
00:37:41,670 --> 00:37:47,180
>> Har någon en rekursiv lösning?

490
00:37:47,180 --> 00:37:49,670
Okej. Den här ska vi - det kan redan vara stora,

491
00:37:49,670 --> 00:37:53,990
men vi kommer att göra det ännu bättre.

492
00:37:53,990 --> 00:37:58,720
Detta är ganska mycket exakt samma idé.

493
00:37:58,720 --> 00:38:03,060
Det är bara, ja, vill du förklara?

494
00:38:03,060 --> 00:38:08,340
[Student] Visst. Så vi ser till att trädet inte är null först,

495
00:38:08,340 --> 00:38:13,380
för om trädet är null så det kommer att returnera false, eftersom vi inte har hittat det.

496
00:38:13,380 --> 00:38:19,200
Och om det finns fortfarande ett träd, går vi in ​​i - vi först kontrollera om värdet är den aktuella noden.

497
00:38:19,200 --> 00:38:23,740
Returnerar sant om det är, och om inte vi recurse på vänster eller höger.

498
00:38:23,740 --> 00:38:25,970
Låter det lämpligt? >> Mm-hmm. (Avtalet)

499
00:38:25,970 --> 00:38:33,880
Så märker att detta är nästan - strukturellt mycket lik den iterativa lösningen.

500
00:38:33,880 --> 00:38:38,200
Det är bara att istället för att recursing, hade vi en while-slinga.

501
00:38:38,200 --> 00:38:40,840
Och basfallet här där träd inte lika null

502
00:38:40,840 --> 00:38:44,850
var villkoret under vilket vi bröt ur while-slingan.

503
00:38:44,850 --> 00:38:50,200
De är mycket lika. Men vi kommer att ta detta ett steg längre.

504
00:38:50,200 --> 00:38:54,190
Nu gör vi samma sak här.

505
00:38:54,190 --> 00:38:57,680
Notera att vi tillbaka samma sak i båda dessa linjer,

506
00:38:57,680 --> 00:39:00,220
förutom ett argument är annorlunda.

507
00:39:00,220 --> 00:39:07,950
Så vi kommer att göra det till en ternär.

508
00:39:07,950 --> 00:39:13,790
Jag slog alternativet något, och det gjorde en symbol. Okej.

509
00:39:13,790 --> 00:39:21,720
Så vi kommer att återvända innehåller det.

510
00:39:21,720 --> 00:39:28,030
Detta är att få vara flera rader, väl, zoomade in det.

511
00:39:28,030 --> 00:39:31,060
Vanligtvis en stilistisk sak, jag tror inte många människor

512
00:39:31,060 --> 00:39:38,640
sätta ett mellanslag efter pilen, men jag antar att om du är konsekvent, det är bra.

513
00:39:38,640 --> 00:39:44,320
Om värdet är mindre än träd värde vill vi recurse på träd vänster,

514
00:39:44,320 --> 00:39:53,890
annat vi vill recurse på träd höger.

515
00:39:53,890 --> 00:39:58,610
Så det var steg ett att göra denna look mindre.

516
00:39:58,610 --> 00:40:02,660
Steg två för att göra denna look mindre -

517
00:40:02,660 --> 00:40:09,150
vi kan skilja denna till flera rader.

518
00:40:09,150 --> 00:40:16,500
Okej. Steg två för att göra det ser mindre är här,

519
00:40:16,500 --> 00:40:25,860
så returvärde lika träd värde, eller innehåller vad som helst.

520
00:40:25,860 --> 00:40:28,340
>> Detta är en viktig sak.

521
00:40:28,340 --> 00:40:30,860
Jag är inte säker på om han sa det uttryckligen i klassen,

522
00:40:30,860 --> 00:40:34,740
men det kallas kortslutning utvärdering.

523
00:40:34,740 --> 00:40:41,060
Tanken här är värde == träd värde.

524
00:40:41,060 --> 00:40:49,960
Om det är sant, då detta är sant, och vi vill "eller" att med det som är här borta.

525
00:40:49,960 --> 00:40:52,520
Så utan att ens tänka på det som är här borta,

526
00:40:52,520 --> 00:40:55,070
vad är hela uttrycket kommer att återvända?

527
00:40:55,070 --> 00:40:59,430
[Student] sant? >> Ja, eftersom gäller något,

528
00:40:59,430 --> 00:41:04,990
or'd - eller sann or'd med något är nödvändigtvis sant.

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

530
00:41:08,150 --> 00:41:10,140
Vi kommer bara att återvända sant.

531
00:41:10,140 --> 00:41:15,710
Inte ens gå till recurse längre innehåller fram.

532
00:41:15,710 --> 00:41:20,980
Vi kan ta detta ett steg längre.

533
00:41:20,980 --> 00:41:29,490
Return träd inte lika null och allt detta.

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

535
00:41:32,650 --> 00:41:36,790
Detta är också ett exempel på kortslutning utvärdering.

536
00:41:36,790 --> 00:41:40,680
Men nu är det samma idé -

537
00:41:40,680 --> 00:41:47,320
istället för - så om träd inte är lika null - eller, ja,

538
00:41:47,320 --> 00:41:49,580
Om trädet inte lika null, vilket är den dåliga fallet,

539
00:41:49,580 --> 00:41:54,790
Om tree lika null, då det första villkoret kommer att vara falsk.

540
00:41:54,790 --> 00:42:00,550
Så falsk-behandlas med något kommer att bli vad?

541
00:42:00,550 --> 00:42:04,640
[Student] Falskt. >> Ja. Detta är den andra halvan av kortslutning utvärdering,

542
00:42:04,640 --> 00:42:10,710
där om trädet inte lika null, då vi inte kommer att ens gå -

543
00:42:10,710 --> 00:42:14,930
eller om träd gör lika null, då vi inte kommer att göra värde == träd värde.

544
00:42:14,930 --> 00:42:17,010
Vi ska bara omedelbart returnera false.

545
00:42:17,010 --> 00:42:20,970
Vilket är viktigt, eftersom om det inte kortslutning utvärdera,

546
00:42:20,970 --> 00:42:25,860
sedan om träd gör lika noll, är detta andra villkor kommer att seg fel,

547
00:42:25,860 --> 00:42:32,510
eftersom träd-> värde dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Så det är det. Kan göra detta - flytta en gång över.

549
00:42:40,490 --> 00:42:44,840
Detta är en mycket vanlig sak också, inte gör detta en linje med detta,

550
00:42:44,840 --> 00:42:49,000
men det är en gemensam sak i förhållanden, kanske inte just här,

551
00:42:49,000 --> 00:42:59,380
men om (träd! = NULL, och träd-> värde == värde), gör vad som helst.

552
00:42:59,380 --> 00:43:01,560
Detta är ett mycket vanligt tillstånd, där i stället för att ha

553
00:43:01,560 --> 00:43:06,770
att bryta detta i två IFS, där vill, är trädet noll?

554
00:43:06,770 --> 00:43:11,780
Okej, det är inte noll, så nu är trädet lika med värdet? Gör så här.

555
00:43:11,780 --> 00:43:17,300
Istället detta villkor kommer detta segment aldrig fel

556
00:43:17,300 --> 00:43:21,220
eftersom det kommer att bryta ut om detta råkar vara noll.

557
00:43:21,220 --> 00:43:24,000
Tja, jag antar att om ditt träd är en helt ogiltig pekare, kan det seg fortfarande fel,

558
00:43:24,000 --> 00:43:26,620
men det kan inte seg fel om träd är null.

559
00:43:26,620 --> 00:43:32,900
Om det var noll, skulle det bryta ut innan du någonsin dereferenced pekaren i första hand.

560
00:43:32,900 --> 00:43:35,000
[Student] kallas detta lata utvärdering?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lat evaluering är en separat sak.

562
00:43:40,770 --> 00:43:49,880
Lat evaluering är mer som du ber om ett värde,

563
00:43:49,880 --> 00:43:54,270
du ber att beräkna ett värde, typ av, men du behöver inte omedelbart.

564
00:43:54,270 --> 00:43:59,040
Så tills du faktiskt behöver det, är det inte utvärderas.

565
00:43:59,040 --> 00:44:03,920
Det är inte exakt samma sak, men i Huffman pset,

566
00:44:03,920 --> 00:44:06,520
står det att vi "slött" skriva.

567
00:44:06,520 --> 00:44:08,670
Anledningen till att vi gör det beror på att vi faktiskt buffra skriva -

568
00:44:08,670 --> 00:44:11,820
Vi vill inte skriva enskilda bitar i taget,

569
00:44:11,820 --> 00:44:15,450
eller enskilda byte i taget, vill vi istället få en bit av byte.

570
00:44:15,450 --> 00:44:19,270
Sen när vi har en bit av byte, så vi ska skriva ut det.

571
00:44:19,270 --> 00:44:22,640
Även om du ber den att skriva - och fwrite och fread göra samma saker.

572
00:44:22,640 --> 00:44:26,260
De buffert dina läser och skriver.

573
00:44:26,260 --> 00:44:31,610
Även om du be den att skriva direkt, kommer det förmodligen inte.

574
00:44:31,610 --> 00:44:34,540
Och du kan inte vara säker på att saker och ting kommer att skrivas

575
00:44:34,540 --> 00:44:37,540
tills du anropar hfclose eller vad det är,

576
00:44:37,540 --> 00:44:39,620
som sedan säger, okej, jag stänger min fil,

577
00:44:39,620 --> 00:44:43,450
det betyder att jag bättre skulle skriva allt jag har inte skrivit än.

578
00:44:43,450 --> 00:44:45,770
Det har inget behov av att skriva ut allt

579
00:44:45,770 --> 00:44:49,010
tills du stänger filen och den behöver.

580
00:44:49,010 --> 00:44:56,220
Så det är precis vad lat - det väntar tills det har att hända.

581
00:44:56,220 --> 00:44:59,990
Detta - ta 51 och du kommer att gå in i det mer i detalj,

582
00:44:59,990 --> 00:45:05,470
eftersom OCaml och allt 51, allt rekursion.

583
00:45:05,470 --> 00:45:08,890
Det finns inga iterativa lösningar, i princip.

584
00:45:08,890 --> 00:45:11,550
Allt är rekursion, och lata utvärdering

585
00:45:11,550 --> 00:45:14,790
kommer att vara viktigt för många omständigheter

586
00:45:14,790 --> 00:45:19,920
där, om du inte lättjefullt utvärdera, skulle det betyda -

587
00:45:19,920 --> 00:45:24,760
Exemplet är strömmar, som är oändligt lång.

588
00:45:24,760 --> 00:45:30,990
I teorin kan du tänka på de naturliga talen som en ström av 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Så lättjefullt utvärderas saker är bra.

590
00:45:33,090 --> 00:45:37,210
Om jag säger att jag vill den tionde numret, så jag kan bedöma upp till den tionde numret.

591
00:45:37,210 --> 00:45:40,300
Om jag vill ha hundrade numret, så jag kan bedöma upp till hundrade numret.

592
00:45:40,300 --> 00:45:46,290
Utan lat utvärdering, då det kommer att försöka utvärdera alla nummer omedelbart.

593
00:45:46,290 --> 00:45:50,000
Du utvärderar oändligt många siffror, och det är bara inte möjligt.

594
00:45:50,000 --> 00:45:52,080
Så det finns en hel del omständigheter där lat utvärdering

595
00:45:52,080 --> 00:45:57,840
är bara viktigt för att få saker och ting att fungera.

596
00:45:57,840 --> 00:46:05,260
>> Nu vill vi skriva insats där insatsen kommer att vara

597
00:46:05,260 --> 00:46:08,430
liknande förändras i sin definition.

598
00:46:08,430 --> 00:46:10,470
Så just nu är det bool insats (int värde).

599
00:46:10,470 --> 00:46:23,850
Vi kommer att ändra det till bool insats (int värde, nod * träd).

600
00:46:23,850 --> 00:46:29,120
Vi har faktiskt kommer att ändra på det igen i lite, vi får se varför.

601
00:46:29,120 --> 00:46:32,210
Och låt oss gå build_node, bara för fan av det,

602
00:46:32,210 --> 00:46:36,730
ovan in så att vi inte behöver skriva en funktion prototyp.

603
00:46:36,730 --> 00:46:42,450
Vilket är en fingervisning om att du kommer att använda build_node i insatsen.

604
00:46:42,450 --> 00:46:49,590
Okej. Ta en minut för det.

605
00:46:49,590 --> 00:46:52,130
Jag tror att jag räddade en översyn om du vill dra från det,

606
00:46:52,130 --> 00:47:00,240
eller åtminstone gjorde jag nu.

607
00:47:00,240 --> 00:47:04,190
Jag ville ha en liten paus för att tänka på logik insatsen,

608
00:47:04,190 --> 00:47:08,750
om du inte kan tänka på det.

609
00:47:08,750 --> 00:47:12,860
I grund och botten kommer du alltid bara vara sätta på bladen.

610
00:47:12,860 --> 00:47:18,640
Som, om jag sätter en så jag oundvikligen kommer att sätta 1 -

611
00:47:18,640 --> 00:47:21,820
Jag ska ändra till svart - Jag ska vara sätta 1 här.

612
00:47:21,820 --> 00:47:28,070
Eller om jag sätter 4, jag vill bli sätta 4 här.

613
00:47:28,070 --> 00:47:32,180
Så oavsett vad du gör, du kommer att sätta på ett löv.

614
00:47:32,180 --> 00:47:36,130
Allt du behöver göra är att upprepa ned trädet tills du kommer till noden

615
00:47:36,130 --> 00:47:40,890
som bör vara nodens förälder den nya nodens förälder,

616
00:47:40,890 --> 00:47:44,560
och sedan ändra sin vänstra eller högra pekare, beroende på om

617
00:47:44,560 --> 00:47:47,060
det är större än eller mindre än den aktuella noden.

618
00:47:47,060 --> 00:47:51,180
Ändra den pekare att peka på din nya noden.

619
00:47:51,180 --> 00:48:05,490
Så iterera ner trädet, gör bladet pekar på den nya noden.

620
00:48:05,490 --> 00:48:09,810
Också tänka på varför som förbjuder den typ av situation före,

621
00:48:09,810 --> 00:48:17,990
där jag konstruerade det binära trädet där det var riktigt

622
00:48:17,990 --> 00:48:19,920
Om du såg bara en enda nod,

623
00:48:19,920 --> 00:48:24,830
men 9 var till vänster om 7 om du upprepade ner hela vägen.

624
00:48:24,830 --> 00:48:29,770
Så det är omöjligt i detta scenario, eftersom -

625
00:48:29,770 --> 00:48:32,530
tycker om sätter 9 eller något, vid den allra första noden,

626
00:48:32,530 --> 00:48:35,350
Jag ska se 7 och jag ska bara gå till höger.

627
00:48:35,350 --> 00:48:38,490
Så oavsett vad jag gör, om jag sätter genom att gå till ett löv,

628
00:48:38,490 --> 00:48:40,790
och till ett löv med lämplig algoritm,

629
00:48:40,790 --> 00:48:43,130
det kommer att vara omöjligt för mig att sätta 9 till vänster om 7

630
00:48:43,130 --> 00:48:48,250
eftersom så fort jag slog 7 Jag ska gå till höger.

631
00:48:59,740 --> 00:49:02,070
Har någon något att börja med?

632
00:49:02,070 --> 00:49:05,480
[Student] jag gör. >> Visst.

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

634
00:49:09,200 --> 00:49:14,390
[Annan student, obegripligt]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Det är uppskattat. Okej. Vill förklara?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Eftersom vi vet att vi sätter

637
00:49:20,690 --> 00:49:24,060
nya noder i slutet av trädet,

638
00:49:24,060 --> 00:49:28,070
Jag loopas trädet iterativt

639
00:49:28,070 --> 00:49:31,360
tills jag kom till en nod som pekade på null.

640
00:49:31,360 --> 00:49:34,220
Och då bestämde jag mig för att uttrycka det antingen på höger eller vänster sida

641
00:49:34,220 --> 00:49:37,420
med denna rätt variabel, det berättade var att sätta den.

642
00:49:37,420 --> 00:49:41,850
Och sedan, i huvudsak gjorde jag just det sista -

643
00:49:41,850 --> 00:49:47,520
att temp nod pekar på nya noden att den skapade,

644
00:49:47,520 --> 00:49:50,770
antingen på vänster eller på höger sida, beroende på vad värdet rätt var.

645
00:49:50,770 --> 00:49:56,530
Slutligen ställer jag den nya noden värdet till värdet av sin testning.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okej, så jag ser en fråga här.

647
00:49:59,550 --> 00:50:02,050
Det är som 95% av vägen dit.

648
00:50:02,050 --> 00:50:07,550
Den enda fråga som jag ser, ja, ser någon annan ett problem?

649
00:50:07,550 --> 00:50:18,400
Vad är den omständighet under vilken de bryter ut på slingan?

650
00:50:18,400 --> 00:50:22,100
[Student] Om temp är noll? >> Ja. Så hur du bryta sig ut ur loopen är om temp är noll.

651
00:50:22,100 --> 00:50:30,220
Men vad gör jag här?

652
00:50:30,220 --> 00:50:35,410
Jag dereference temp, vilket är oundvikligt noll.

653
00:50:35,410 --> 00:50:39,840
Så en annan sak du behöver göra är inte bara hålla reda tills temp är noll,

654
00:50:39,840 --> 00:50:45,590
du vill hålla reda på föräldern vid alla tidpunkter.

655
00:50:45,590 --> 00:50:52,190
Vi vill också överordnade noden *, jag antar att vi kan hålla det vid noll i början.

656
00:50:52,190 --> 00:50:55,480
Detta kommer att få konstiga beteende för roten av trädet,

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

658
00:50:59,210 --> 00:51:03,950
Om värdet är större än vad som helst, så temp = temp höger.

659
00:51:03,950 --> 00:51:07,910
Men innan vi gör det, förälder = temp.

660
00:51:07,910 --> 00:51:14,500
Eller är föräldrar kommer alltid till lika temp? Är det så?

661
00:51:14,500 --> 00:51:19,560
Om temp inte är null, så jag ska gå ner, oavsett vad,

662
00:51:19,560 --> 00:51:24,030
till en nod som temp är moderbolag.

663
00:51:24,030 --> 00:51:27,500
Så förälder kommer att vara temp och sedan jag flytta temp ner.

664
00:51:27,500 --> 00:51:32,410
Nu temp är null, men pekar förälder förälder till det som är noll.

665
00:51:32,410 --> 00:51:39,110
Så här nere, jag vill inte ställa rätt lika med 1.

666
00:51:39,110 --> 00:51:41,300
Så jag flyttade till höger, så om höger = 1,

667
00:51:41,300 --> 00:51:45,130
och jag antar att du också vill göra -

668
00:51:45,130 --> 00:51:48,530
om du flyttar till vänster, vill du ställa rätt lika med 0.

669
00:51:48,530 --> 00:51:55,950
Eller så om du flyttar någonsin till höger.

670
00:51:55,950 --> 00:51:58,590
Så rätt = 0. Om höger = 1,

671
00:51:58,590 --> 00:52:04,260
nu vill vi göra den förälder rätt pekaren newnode,

672
00:52:04,260 --> 00:52:08,520
annat vi vill göra den förälder vänster pekaren newnode.

673
00:52:08,520 --> 00:52:16,850
Frågor på det?

674
00:52:16,850 --> 00:52:24,880
Okej. Så detta är hur vi - ja, faktiskt, istället för att göra detta,

675
00:52:24,880 --> 00:52:29,630
vi förväntade oss halv dig att använda build_node.

676
00:52:29,630 --> 00:52:40,450
Och sedan om newnode lika null returnera false.

677
00:52:40,450 --> 00:52:44,170
Det är det. Nu är detta vad vi förväntat dig att göra.

678
00:52:44,170 --> 00:52:47,690
>> Detta är vad de anställda lösningarna gör.

679
00:52:47,690 --> 00:52:52,360
Jag håller inte med detta som "rätt" sätt att gå om det

680
00:52:52,360 --> 00:52:57,820
men detta är helt bra och det kommer att fungera.

681
00:52:57,820 --> 00:53:02,840
En sak som är lite konstigt just nu är

682
00:53:02,840 --> 00:53:08,310
Om trädet börjar som null, passerar vi en null träd.

683
00:53:08,310 --> 00:53:12,650
Jag antar att det beror på hur du definierar beteende som passerar i en null träd.

684
00:53:12,650 --> 00:53:15,490
Jag skulle tro att om du i en null träd,

685
00:53:15,490 --> 00:53:17,520
sedan sätter värdet till en null träd

686
00:53:17,520 --> 00:53:23,030
ska bara returnera ett träd där det enda värdet är att enda nod.

687
00:53:23,030 --> 00:53:25,830
Har folk håller med om det? Du kan, om du vill,

688
00:53:25,830 --> 00:53:28,050
Om du passerar i en null träd

689
00:53:28,050 --> 00:53:31,320
och du vill infoga ett värde i det, returnera false.

690
00:53:31,320 --> 00:53:33,830
Det är upp till dig att bestämma det.

691
00:53:33,830 --> 00:53:38,320
För att göra det första jag sa och sedan -

692
00:53:38,320 --> 00:53:40,720
bra, du kommer att ha svårt att göra det, eftersom

693
00:53:40,720 --> 00:53:44,090
det skulle vara lättare om vi hade en global pekare till sak,

694
00:53:44,090 --> 00:53:48,570
men vi inte, så om trädet är noll, det finns inget vi kan göra åt det.

695
00:53:48,570 --> 00:53:50,960
Vi kan bara returnera false.

696
00:53:50,960 --> 00:53:52,840
Så jag ska byta insats.

697
00:53:52,840 --> 00:53:56,540
Vi tekniskt kan bara ändra denna rätt här,

698
00:53:56,540 --> 00:53:58,400
hur det iteration över saker,

699
00:53:58,400 --> 00:54:04,530
men jag ska byta insats för att ta en nod ** träd.

700
00:54:04,530 --> 00:54:07,510
Dubbla pekare.

701
00:54:07,510 --> 00:54:09,710
Vad betyder det här?

702
00:54:09,710 --> 00:54:12,330
Istället för att hantera pekare till noderna,

703
00:54:12,330 --> 00:54:16,690
det jag tänker att manipulera är pekare.

704
00:54:16,690 --> 00:54:18,790
Jag kommer att manipulera denna pekare.

705
00:54:18,790 --> 00:54:21,770
Jag kommer att manipulera pekare direkt.

706
00:54:21,770 --> 00:54:25,760
Detta är logiskt eftersom fundera ned -

707
00:54:25,760 --> 00:54:33,340
ja, just nu tyder detta på null.

708
00:54:33,340 --> 00:54:38,130
Vad jag vill göra är att manipulera denna pekare att peka på inte null.

709
00:54:38,130 --> 00:54:40,970
Jag vill att det ska peka på min nya noden.

710
00:54:40,970 --> 00:54:44,870
Om jag bara hålla koll på pekare till mina pekare,

711
00:54:44,870 --> 00:54:47,840
så jag behöver inte hålla reda på en förälder pekare.

712
00:54:47,840 --> 00:54:52,640
Jag kan bara hålla reda för att se om pekaren pekar på null,

713
00:54:52,640 --> 00:54:54,580
och om pekaren pekar på null,

714
00:54:54,580 --> 00:54:57,370
ändra den för att peka på noden jag vill.

715
00:54:57,370 --> 00:55:00,070
Och jag kan ändra det eftersom jag har en pekare till pekare.

716
00:55:00,070 --> 00:55:02,040
Låt oss se detta just nu.

717
00:55:02,040 --> 00:55:05,470
Du kan faktiskt göra det rekursivt ganska enkelt.

718
00:55:05,470 --> 00:55:08,080
Vill vi göra det?

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

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

721
00:55:16,790 --> 00:55:24,070
Först, vad vår bas fall kommer att bli?

722
00:55:24,070 --> 00:55:29,140
Nästan alltid vår bas fallet, men egentligen, är denna typ av knepigt.

723
00:55:29,140 --> 00:55:34,370
Första saker först, om (träd == NULL)

724
00:55:34,370 --> 00:55:37,550
Jag antar att vi bara ska returnera false.

725
00:55:37,550 --> 00:55:40,460
Detta skiljer sig från ditt träd är noll.

726
00:55:40,460 --> 00:55:44,510
Detta är pekaren till ditt root pekaren är noll

727
00:55:44,510 --> 00:55:48,360
vilket innebär att ditt root pekaren inte existerar.

728
00:55:48,360 --> 00:55:52,390
Så här nere, om jag gör

729
00:55:52,390 --> 00:55:55,760
nod * - låt oss bara återanvända det.

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

731
00:55:58,960 --> 00:56:00,730
och då ska jag ringa insats genom att göra något liknande,

732
00:56:00,730 --> 00:56:04,540
Sätt 4 i och rot.

733
00:56:04,540 --> 00:56:06,560
Så och rot, om rot är en nod *

734
00:56:06,560 --> 00:56:11,170
då och rot kommer att vara en nod **.

735
00:56:11,170 --> 00:56:15,120
Detta är giltigt. I detta fall, träd, upp här,

736
00:56:15,120 --> 00:56:20,120
träd är inte null - eller insats.

737
00:56:20,120 --> 00:56:24,630
Här. Träd är inte null; * träd är null, vilket är bra

738
00:56:24,630 --> 00:56:26,680
för om * trädet är noll, så jag kan manipulera det

739
00:56:26,680 --> 00:56:29,210
att nu peka på vad jag vill att det ska peka på.

740
00:56:29,210 --> 00:56:34,750
Men om trädet är noll, innebär att jag bara kom hit och sa noll.

741
00:56:34,750 --> 00:56:42,710
Det är inte vettigt. Jag kan inte göra något med det.

742
00:56:42,710 --> 00:56:45,540
Om trädet är null returnera false.

743
00:56:45,540 --> 00:56:48,220
Så jag i princip redan sagt vad vår verkliga basfallet är.

744
00:56:48,220 --> 00:56:50,580
Och vad är det kommer att bli?

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

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ja. Så om (* träd == NULL).

747
00:57:00,000 --> 00:57:04,520
Detta gäller fallet hit

748
00:57:04,520 --> 00:57:09,640
där om min röda visaren är pekaren jag fokuserat på,

749
00:57:09,640 --> 00:57:12,960
så som jag fokuserat på denna pekare, nu är jag fokuserad på denna pekare.

750
00:57:12,960 --> 00:57:15,150
Nu är jag fokuserad på denna pekare.

751
00:57:15,150 --> 00:57:18,160
Så om min röda visare, som är min nod **,

752
00:57:18,160 --> 00:57:22,880
är någonsin - om *, min röda visare, är någonsin noll,

753
00:57:22,880 --> 00:57:28,470
det betyder att jag är på det fall jag fokusera på en pekare som pekar -

754
00:57:28,470 --> 00:57:32,530
Detta är en pekare som hör till ett löv.

755
00:57:32,530 --> 00:57:41,090
Jag vill ändra denna pekare att peka på min nya noden.

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

757
00:57:45,230 --> 00:57:56,490
Min newnode kommer bara att vara nod * n = build_node (värde)

758
00:57:56,490 --> 00:58:07,300
sedan n, om n = NULL, returnera false.

759
00:58:07,300 --> 00:58:12,600
Annars vill vi ändra på det pekaren för närvarande pekar på

760
00:58:12,600 --> 00:58:17,830
att nu peka på vår nybyggda nod.

761
00:58:17,830 --> 00:58:20,280
Vi kan faktiskt göra det här.

762
00:58:20,280 --> 00:58:30,660
Istället för att säga n säger vi * träd = om * träd.

763
00:58:30,660 --> 00:58:35,450
Alla förstår att? Det genom att behandla pekare till pekare,

764
00:58:35,450 --> 00:58:40,750
Vi kan ändra null pekare att peka på saker som vi vill att de ska peka på.

765
00:58:40,750 --> 00:58:42,820
Det är vår bas fallet.

766
00:58:42,820 --> 00:58:45,740
>> Nu vår återkommande, eller vår rekursion,

767
00:58:45,740 --> 00:58:51,430
kommer att bli mycket lik alla andra rekursioner Vi har gjort.

768
00:58:51,430 --> 00:58:55,830
Vi kommer att vilja sätta värde,

769
00:58:55,830 --> 00:58:59,040
och nu ska jag använda ternära igen, men vad vårt tillstånd kommer att bli?

770
00:58:59,040 --> 00:59:05,180
Vad är det vi letar efter för att avgöra om vi vill gå åt vänster eller höger?

771
00:59:05,180 --> 00:59:07,760
Låt oss göra det i separata steg.

772
00:59:07,760 --> 00:59:18,850
Om (värde <) vad?

773
00:59:18,850 --> 00:59:23,200
[Student] Trädets värde?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Så kom ihåg att jag är närvarande -

775
00:59:27,490 --> 00:59:31,260
[Studenter, obegripliga]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Ja, så här, låt oss säga att detta gröna pilen

777
00:59:34,140 --> 00:59:39,050
är ett exempel på vad träd närvarande är, är en pekare till denna pekare.

778
00:59:39,050 --> 00:59:46,610
Så det betyder att jag är en pekare till en pekare till 3.

779
00:59:46,610 --> 00:59:48,800
Den dereference lät två gånger bra.

780
00:59:48,800 --> 00:59:51,010
Vad gör jag - hur gör jag det?

781
00:59:51,010 --> 00:59:53,210
[Student] dereference gång och gör sedan pil på det sättet?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Så (* träd) är dereference gång -> värde

783
00:59:58,420 --> 01:00:05,960
kommer att ge mig värdet av den nod som jag indirekt är pekar på.

784
01:00:05,960 --> 01:00:11,980
Så jag kan också skriva det ** tree.value om du föredrar det.

785
01:00:11,980 --> 01:00:18,490
Antingen fungerar.

786
01:00:18,490 --> 01:00:26,190
Om så är fallet, då jag vill ringa in med värde.

787
01:00:26,190 --> 01:00:32,590
Och vad är min uppdaterade nod ** kommer att bli?

788
01:00:32,590 --> 01:00:39,440
Jag vill gå till vänster, så ** tree.left kommer att bli min vänstra.

789
01:00:39,440 --> 01:00:41,900
Och jag vill pekaren till det där

790
01:00:41,900 --> 01:00:44,930
så att om vänster slutar vara null pekaren,

791
01:00:44,930 --> 01:00:48,360
Jag kan ändra den för att peka på min nya noden.

792
01:00:48,360 --> 01:00:51,460
>> Och det andra fallet kan vara mycket lika.

793
01:00:51,460 --> 01:00:55,600
Låt oss faktiskt göra att min ternära just nu.

794
01:00:55,600 --> 01:01:04,480
Sätt värde om värde <(** träd). Värde.

795
01:01:04,480 --> 01:01:11,040
Sen vill vi uppdatera våra ** till vänster,

796
01:01:11,040 --> 01:01:17,030
annat vi vill uppdatera våra ** till höger.

797
01:01:17,030 --> 01:01:22,540
[Student] Blir att pekaren till pekaren?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Kom ihåg att - ** tree.right är en nod stjärna.

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

800
01:01:35,040 --> 01:01:41,140
** Tree.right är så här pekare eller något.

801
01:01:41,140 --> 01:01:45,140
Så genom att ta en pekare till det, ger det mig vad jag vill ha

802
01:01:45,140 --> 01:01:50,090
av pekaren till den killen.

803
01:01:50,090 --> 01:01:54,260
[Student] Kan vi gå igen varför vi använder två pekare?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Ja. Så - nej, det kan du, och den lösningen före

805
01:01:58,220 --> 01:02:04,540
var ett sätt att göra det utan att göra två pekare.

806
01:02:04,540 --> 01:02:08,740
Du måste kunna förstå att använda två pekare,

807
01:02:08,740 --> 01:02:11,660
och detta är en renare lösning.

808
01:02:11,660 --> 01:02:16,090
Också märke till att, vad händer om mitt träd -

809
01:02:16,090 --> 01:02:24,480
Vad händer om min rot var noll? Vad händer om jag gör det här fallet här?

810
01:02:24,480 --> 01:02:30,540
Så nod * root = NULL, sätt 4 i och rot.

811
01:02:30,540 --> 01:02:35,110
Vad rot kommer att vara efter detta?

812
01:02:35,110 --> 01:02:37,470
[Student, obegripligt] >> Ja.

813
01:02:37,470 --> 01:02:41,710
Root värde kommer att bli 4.

814
01:02:41,710 --> 01:02:45,510
Root vänster kommer att bli noll, är roten till höger kommer att bli noll.

815
01:02:45,510 --> 01:02:49,490
I fallet där vi inte klarade rot efter adress,

816
01:02:49,490 --> 01:02:52,490
vi kunde inte ändra root.

817
01:02:52,490 --> 01:02:56,020
I det fall då trädet - där rot var noll,

818
01:02:56,020 --> 01:02:58,410
Vi hade bara att returnera false. Det finns inget vi kan göra.

819
01:02:58,410 --> 01:03:01,520
Vi kan inte sätta en nod i en tom träd.

820
01:03:01,520 --> 01:03:06,810
Men nu kan vi, vi bara göra en tom träd i en en-nod träd.

821
01:03:06,810 --> 01:03:13,400
Som vanligtvis är den förväntade sätt som det är tänkt att fungera.

822
01:03:13,400 --> 01:03:21,610
>> Dessutom är detta betydligt kortare än

823
01:03:21,610 --> 01:03:26,240
också hålla reda på förälder och så du iterera ner hela vägen.

824
01:03:26,240 --> 01:03:30,140
Nu har jag min förälder och jag har min pekare förälder rätt till vad som helst.

825
01:03:30,140 --> 01:03:35,640
Istället, om vi gjorde detta iterativt, det skulle vara samma idé med en while-slinga.

826
01:03:35,640 --> 01:03:38,100
Men istället för att behöva handskas med mina föräldrar pekare,

827
01:03:38,100 --> 01:03:40,600
istället min nuvarande pekare skulle vara något

828
01:03:40,600 --> 01:03:43,790
att jag direkt ändra för att peka på min nya noden.

829
01:03:43,790 --> 01:03:46,090
Jag behöver inte ta itu med om det pekar åt vänster.

830
01:03:46,090 --> 01:03:48,810
Jag behöver inte ta itu med om det pekar åt höger.

831
01:03:48,810 --> 01:04:00,860
Det är bara vad denna pekare är, jag kommer att ställa in den att peka på min nya noden.

832
01:04:00,860 --> 01:04:05,740
Alla förstå hur det fungerar?

833
01:04:05,740 --> 01:04:09,460
Om inte, varför vill vi göra det här sättet,

834
01:04:09,460 --> 01:04:14,920
men åtminstone att detta fungerar som en lösning?

835
01:04:14,920 --> 01:04:17,110
[Student] Var återvänder vi sant?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Det är förmodligen här.

837
01:04:21,550 --> 01:04:26,690
Om vi ​​rätt in den, return true.

838
01:04:26,690 --> 01:04:32,010
Annars här nere vi kommer att vilja återvända oavsett insats tillbaka.

839
01:04:32,010 --> 01:04:35,950
>> Och vad är speciellt med denna rekursiv funktion?

840
01:04:35,950 --> 01:04:43,010
Det är svansen rekursiv, så länge vi sammanställa med viss optimering,

841
01:04:43,010 --> 01:04:48,060
Det kommer att erkänna det och du kommer aldrig att få en stack overflow från detta,

842
01:04:48,060 --> 01:04:53,230
även om vår träd har en höjd av 10.000 eller 10 miljoner.

843
01:04:53,230 --> 01:04:55,630
[Student, obegripligt]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Jag tror att det gör det på Dash - eller vad optimeringsnivå

845
01:05:00,310 --> 01:05:03,820
krävs för en svans rekursion skall erkännas.

846
01:05:03,820 --> 01:05:09,350
Jag tror att det känner igen - GCC och klang

847
01:05:09,350 --> 01:05:12,610
också ha olika betydelser för sina optimering nivåer.

848
01:05:12,610 --> 01:05:17,870
Jag vill säga att det är DashO 2, för säker på att det kommer att erkänna svansen rekursion.

849
01:05:17,870 --> 01:05:27,880
Men vi - du kan bygga som en Fibonocci exempel eller något.

850
01:05:27,880 --> 01:05:30,030
Det är inte lätt att testa med detta, eftersom det är svårt att konstruera

851
01:05:30,030 --> 01:05:32,600
ett binärt träd som är så stor.

852
01:05:32,600 --> 01:05:37,140
Men ja, jag tror det är DashO 2, som

853
01:05:37,140 --> 01:05:40,580
Om du kompilerar med DashO 2, kommer det att leta efter svansen rekursion

854
01:05:40,580 --> 01:05:54,030
och optimera den ut.

855
01:05:54,030 --> 01:05:58,190
Låt oss gå tillbaka till - sätta är bokstavligen det sista den behöver.

856
01:05:58,190 --> 01:06:04,900
Låt oss gå tillbaka till insatsen hit

857
01:06:04,900 --> 01:06:07,840
där vi ska göra samma idé.

858
01:06:07,840 --> 01:06:14,340
Det kommer fortfarande att ha fel att inte kunna att helt hantera

859
01:06:14,340 --> 01:06:17,940
när roten själv är null, eller de senaste posten är null

860
01:06:17,940 --> 01:06:20,060
men i stället för att hantera en förälder pekare,

861
01:06:20,060 --> 01:06:27,430
låt oss tillämpa samma logik hålla pekare till pekare.

862
01:06:27,430 --> 01:06:35,580
Om vi ​​här hålla våra nod ** nuvarande,

863
01:06:35,580 --> 01:06:37,860
och vi behöver inte hålla reda på just längre,

864
01:06:37,860 --> 01:06:47,190
men nod ** nuvarande = & träd.

865
01:06:47,190 --> 01:06:54,800
Och nu vår while-slinga kommer att vara när * nuvarande inte lika null.

866
01:06:54,800 --> 01:07:00,270
Behöver inte hålla reda på föräldrarnas längre.

867
01:07:00,270 --> 01:07:04,180
Behöver inte hålla reda på vänster och höger.

868
01:07:04,180 --> 01:07:10,190
Och jag kallar det temp, eftersom vi redan använder temp.

869
01:07:10,190 --> 01:07:17,200
Okej. Så om (värde> * temp),

870
01:07:17,200 --> 01:07:24,010
då och (* temp) -> höger

871
01:07:24,010 --> 01:07:29,250
annars temp = & (* temp) -> vänster.

872
01:07:29,250 --> 01:07:32,730
Och nu, vid denna tidpunkt, efter denna while-slinga,

873
01:07:32,730 --> 01:07:36,380
Jag gör bara detta eftersom det kanske är lättare att tänka iterativt än rekursivt,

874
01:07:36,380 --> 01:07:39,010
men efter detta samtidigt slinga,

875
01:07:39,010 --> 01:07:43,820
* Temp är pekaren vill vi ändra på.

876
01:07:43,820 --> 01:07:48,960
>> Innan vi hade förälder, och vi ville ändra någon av föräldrarna vänster eller förälder höger,

877
01:07:48,960 --> 01:07:51,310
men om vi vill förändra förälder höger,

878
01:07:51,310 --> 01:07:54,550
då * temp är moderbolag rätt, och vi kan ändra det direkt.

879
01:07:54,550 --> 01:08:05,860
Så här nere, kan vi göra * temp = newnode, och det är det.

880
01:08:05,860 --> 01:08:09,540
Så varsel, var allt vi gjorde i detta ta ut rader kod.

881
01:08:09,540 --> 01:08:14,770
För att hålla koll på den förälder i allt som är extra ansträngning.

882
01:08:14,770 --> 01:08:18,689
Här, om vi bara hålla reda på pekaren till pekaren,

883
01:08:18,689 --> 01:08:22,990
och även om vi ville bli av med alla dessa klammerparenteser nu,

884
01:08:22,990 --> 01:08:27,170
att det ser kortare.

885
01:08:27,170 --> 01:08:32,529
Detta är nu exakt samma lösning,

886
01:08:32,529 --> 01:08:38,210
men färre rader kod.

887
01:08:38,210 --> 01:08:41,229
När du börjar känna igen detta som en giltig lösning,

888
01:08:41,229 --> 01:08:43,529
Det är också lättare att resonera om än liknande, okej,

889
01:08:43,529 --> 01:08:45,779
varför har jag denna flagga på int rätt?

890
01:08:45,779 --> 01:08:49,290
Vad betyder det? Åh, det vilket innebär att

891
01:08:49,290 --> 01:08:51,370
varje gång jag går till höger, måste jag ställa in den,

892
01:08:51,370 --> 01:08:53,819
annars om jag går lämnade jag måste ställa den till noll.

893
01:08:53,819 --> 01:09:04,060
Här behöver jag inte resonera om det, det är bara lättare att tänka på.

894
01:09:04,060 --> 01:09:06,710
Frågor?

895
01:09:06,710 --> 01:09:16,290
[Student, obegripligt] >> Ja.

896
01:09:16,290 --> 01:09:23,359
Okej, så i den sista biten -

897
01:09:23,359 --> 01:09:28,080
Jag antar att en snabb och enkel funktion som vi kan göra är,

898
01:09:28,080 --> 01:09:34,910
let's - tillsammans, antar jag, försöka skriva en innehåller funktion

899
01:09:34,910 --> 01:09:38,899
som inte bryr sig om det är en binärt sökträd.

900
01:09:38,899 --> 01:09:43,770
Detta innehåller funktionen ska returnera sant

901
01:09:43,770 --> 01:09:58,330
om någonstans i denna allmänna binära träd är det värde som vi letar efter.

902
01:09:58,330 --> 01:10:02,520
Så låt oss först göra det rekursivt och sedan kommer vi att göra det iterativt.

903
01:10:02,520 --> 01:10:07,300
Vi kan faktiskt bara göra det tillsammans, eftersom detta kommer att bli riktigt kort.

904
01:10:07,300 --> 01:10:11,510
>> Vad är min basfall kommer att?

905
01:10:11,510 --> 01:10:13,890
[Student, obegripligt]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Så om (träd == NULL), vad?

907
01:10:18,230 --> 01:10:22,740
[Student] returnera false.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, ja, jag behöver inte mer.

909
01:10:26,160 --> 01:10:30,250
Om var min andra basfallet.

910
01:10:30,250 --> 01:10:32,450
[Student] Träd värde? >> Ja.

911
01:10:32,450 --> 01:10:36,430
Så om (träd-> värde == värde.

912
01:10:36,430 --> 01:10:39,920
Notera att vi är tillbaka till nod *, inte nod ** s?

913
01:10:39,920 --> 01:10:42,990
Innehåller kommer aldrig behöva använda en nod **,

914
01:10:42,990 --> 01:10:45,480
eftersom vi inte ändrar pekare.

915
01:10:45,480 --> 01:10:50,540
Vi bara korsa dem.

916
01:10:50,540 --> 01:10:53,830
Om det händer, då vi vill återvända sant.

917
01:10:53,830 --> 01:10:58,270
Annars vill vi korsa barnen.

918
01:10:58,270 --> 01:11:02,620
Så vi kan inte resonera om huruvida allt till vänster är mindre

919
01:11:02,620 --> 01:11:05,390
och allt till höger är större.

920
01:11:05,390 --> 01:11:09,590
Så vad är vårt tillstånd kommer att vara här - eller, vad ska vi göra?

921
01:11:09,590 --> 01:11:11,840
[Student, obegripligt] >> Ja.

922
01:11:11,840 --> 01:11:17,400
Return innehåller (värde, träd-> vänster)

923
01:11:17,400 --> 01:11:26,860
eller innehåller (värde, träd-> höger). Och det är det.

924
01:11:26,860 --> 01:11:29,080
Och märker att det finns en viss kortslutning utvärdering,

925
01:11:29,080 --> 01:11:32,520
där om vi råkar hitta värdet i den vänstra trädet,

926
01:11:32,520 --> 01:11:36,820
vi behöver aldrig att titta på rätt träd.

927
01:11:36,820 --> 01:11:40,430
Det är hela funktionen.

928
01:11:40,430 --> 01:11:43,690
Nu ska vi göra det iterativt,

929
01:11:43,690 --> 01:11:48,060
som kommer att vara mindre trevligt.

930
01:11:48,060 --> 01:11:54,750
Vi tar den vanliga start nod * nuvarande = träd.

931
01:11:54,750 --> 01:12:03,250
Medan (nuvarande! = Null).

932
01:12:03,250 --> 01:12:08,600
Snabbt kommer att se ett problem.

933
01:12:08,600 --> 01:12:12,250
Om nuvarande - här ute, om vi någonsin bryta detta,

934
01:12:12,250 --> 01:12:16,020
då vi har slut på saker att titta på, så returnera false.

935
01:12:16,020 --> 01:12:24,810
Om (valu-> värde == värde), return true.

936
01:12:24,810 --> 01:12:32,910
Så nu är vi på en plats -

937
01:12:32,910 --> 01:12:36,250
Vi vet inte om vi vill gå åt vänster eller höger.

938
01:12:36,250 --> 01:12:44,590
Så godtyckligt, låt oss bara gå till vänster.

939
01:12:44,590 --> 01:12:47,910
Jag har naturligtvis stött på en fråga där jag har helt övergiven allt -

940
01:12:47,910 --> 01:12:50,760
Jag kommer alltid bara kontrollera den vänstra sidan av ett träd.

941
01:12:50,760 --> 01:12:56,050
Jag kommer aldrig kontrollera något som är en rätt barn någonting.

942
01:12:56,050 --> 01:13:00,910
Hur åtgärdar jag det?

943
01:13:00,910 --> 01:13:05,260
[Student] Du måste hålla koll på vänster och höger i en stapel.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Ja. Så låt oss göra det

945
01:13:13,710 --> 01:13:32,360
struct listan nod * n och sedan noden ** härnäst?

946
01:13:32,360 --> 01:13:40,240
Jag tror att fungerar bra.

947
01:13:40,240 --> 01:13:45,940
Vi vill gå över till vänster, eller let's - här uppe.

948
01:13:45,940 --> 01:13:54,350
Struct listan list = kommer det börja

949
01:13:54,350 --> 01:13:58,170
ut på detta struct lista.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Så det kommer att bli vår länkad lista

951
01:14:04,040 --> 01:14:08,430
av underträd som vi har hoppas över.

952
01:14:08,430 --> 01:14:13,800
Vi kommer att korsa kvar nu,

953
01:14:13,800 --> 01:14:17,870
men eftersom vi oundvikligen måste komma tillbaka till höger,

954
01:14:17,870 --> 01:14:26,140
Vi kommer att hålla till höger innanför vår struct lista.

955
01:14:26,140 --> 01:14:32,620
Då kommer vi att ha new_list eller struct,

956
01:14:32,620 --> 01:14:41,080
struct lista *, new_list = malloc (sizeof (lista)).

957
01:14:41,080 --> 01:14:44,920
Jag ska ignorera felkontroll det, men du bör kontrollera om det är noll.

958
01:14:44,920 --> 01:14:50,540
New_list noden det kommer att peka på -

959
01:14:50,540 --> 01:14:56,890
åh, det är därför jag ville ha det här uppe. Det kommer att peka på en andra struktur lista.

960
01:14:56,890 --> 01:15:02,380
Det är bara hur länkade listor arbete.

961
01:15:02,380 --> 01:15:04,810
Detta är detsamma som en länkad lista int

962
01:15:04,810 --> 01:15:06,960
utom vi bara ersätta int med nod *.

963
01:15:06,960 --> 01:15:11,040
Det är exakt samma.

964
01:15:11,040 --> 01:15:15,100
Så new_list, värdet av vår new_list nod,

965
01:15:15,100 --> 01:15:19,120
kommer att vara valuta-> höger.

966
01:15:19,120 --> 01:15:24,280
Värdet av vår new_list-> nästa kommer att bli vår ursprungliga listan,

967
01:15:24,280 --> 01:15:30,760
och då ska vi uppdatera vår lista att peka på new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nu behöver vi något slags sätt att dra saker,

969
01:15:33,650 --> 01:15:37,020
som vi har passerat hela vänstra underträd.

970
01:15:37,020 --> 01:15:40,480
Nu måste vi dra saker ur det,

971
01:15:40,480 --> 01:15:43,850
Liksom nuvarande är null, vi vill inte bara returnera false.

972
01:15:43,850 --> 01:15:50,370
Vi vill nu dra utanför på vår nya lista.

973
01:15:50,370 --> 01:15:53,690
Ett bekvämt sätt att göra detta - ja, faktiskt, det finns flera olika sätt att göra detta.

974
01:15:53,690 --> 01:15:56,680
Någon har ett förslag?

975
01:15:56,680 --> 01:15:58,790
Där jag borde göra det eller hur jag ska göra det?

976
01:15:58,790 --> 01:16:08,010
Vi har bara ett par minuter, men några förslag?

977
01:16:08,010 --> 01:16:14,750
Istället för - en väg, i stället för vår kondition är under,

978
01:16:14,750 --> 01:16:17,090
vad vi nu tittar på är inte noll,

979
01:16:17,090 --> 01:16:22,340
istället ska vi fortsätta att gå tills vår lista sig är noll.

980
01:16:22,340 --> 01:16:25,680
Så om vår lista hamnar är noll,

981
01:16:25,680 --> 01:16:30,680
då har vi slut på saker att leta efter, för att söka över.

982
01:16:30,680 --> 01:16:39,860
Men det betyder att det första i vår lista bara kommer att bli den första noden.

983
01:16:39,860 --> 01:16:49,730
Det allra första kommer att vara - vi behöver inte längre se det.

984
01:16:49,730 --> 01:16:58,710
Så list-> n kommer att vara vår träd.

985
01:16:58,710 --> 01:17:02,860
list-> nästa kommer att bli noll.

986
01:17:02,860 --> 01:17:07,580
Och nu när listan inte lika null.

987
01:17:07,580 --> 01:17:11,610
Cur kommer att dra något från vår lista.

988
01:17:11,610 --> 01:17:13,500
Så nuvarande kommer att lika lista-> n.

989
01:17:13,500 --> 01:17:20,850
Och sedan lista kommer att lika lista-> n, eller lista-> nästa.

990
01:17:20,850 --> 01:17:23,480
Så om nuvarande värde är lika värde.

991
01:17:23,480 --> 01:17:28,790
Nu kan vi lägga till både vår rätt pekare och vår vänstra pekare

992
01:17:28,790 --> 01:17:32,900
så länge de inte är noll.

993
01:17:32,900 --> 01:17:36,390
Här nere, jag antar att vi borde ha gjort det i första hand.

994
01:17:36,390 --> 01:17:44,080
Om (valu-> höger! = Null)

995
01:17:44,080 --> 01:17:56,380
då kommer vi att sätta in den noden i vår lista.

996
01:17:56,380 --> 01:17:59,290
Om (valu-> vänster), här är lite extra arbete, men det är bra.

997
01:17:59,290 --> 01:18:02,690
Om (valu-> vänster! = Null),

998
01:18:02,690 --> 01:18:14,310
och vi kommer att sätta in vänster i vår länkad lista,

999
01:18:14,310 --> 01:18:19,700
och det borde vara det.

1000
01:18:19,700 --> 01:18:22,670
Vi iterera - så länge vi har något i vår lista,

1001
01:18:22,670 --> 01:18:26,640
vi har en annan nod att titta på.

1002
01:18:26,640 --> 01:18:28,920
Så vi tittar på den noden,

1003
01:18:28,920 --> 01:18:31,390
Vi avancera vår lista till nästa.

1004
01:18:31,390 --> 01:18:34,060
Om den noden är det värde som vi letar efter, kan vi återvända sant.

1005
01:18:34,060 --> 01:18:37,640
Annars sätter både våra vänster och höger underträd,

1006
01:18:37,640 --> 01:18:40,510
så länge de inte är noll, i vår lista

1007
01:18:40,510 --> 01:18:43,120
så att vi går oundvikligen över dem.

1008
01:18:43,120 --> 01:18:45,160
Så om de inte är null,

1009
01:18:45,160 --> 01:18:47,950
om vår rot pekare pekade på två saker,

1010
01:18:47,950 --> 01:18:51,670
då först drog vi något så vår lista slutar som null.

1011
01:18:51,670 --> 01:18:56,890
Och då vi sätter två saker tillbaka, så nu vår lista är storlek 2.

1012
01:18:56,890 --> 01:19:00,030
Sen ska vi slinga tillbaka och vi ska bara dra,

1013
01:19:00,030 --> 01:19:04,250
låt oss säga, den vänstra pekaren vår rotnoden.

1014
01:19:04,250 --> 01:19:07,730
Och det kommer bara fortsätta hända, vi kommer att sluta loopa över allt.

1015
01:19:07,730 --> 01:19:11,280
>> Observera att detta var betydligt mer komplicerat

1016
01:19:11,280 --> 01:19:14,160
i den rekursiva lösningen.

1017
01:19:14,160 --> 01:19:17,260
Och jag har sagt flera gånger

1018
01:19:17,260 --> 01:19:25,120
att den rekursiva lösningen har vanligtvis mycket gemensamt med den iterativa lösningen.

1019
01:19:25,120 --> 01:19:30,820
Här är det precis vad den rekursiva lösningen gör.

1020
01:19:30,820 --> 01:19:36,740
Den enda förändringen är att istället för att implicit använder stacken, programmet stacken,

1021
01:19:36,740 --> 01:19:40,840
som ditt sätt att hålla koll på vad noder du fortfarande behöver besöka,

1022
01:19:40,840 --> 01:19:45,430
nu måste du explicit använda en länkad lista.

1023
01:19:45,430 --> 01:19:49,070
I båda fallen är att hålla reda på vad nod fortfarande måste besökas.

1024
01:19:49,070 --> 01:19:51,790
I den rekursiva fallet är det bara lättare eftersom en stapel

1025
01:19:51,790 --> 01:19:57,100
genomförs för dig som programmet stacken.

1026
01:19:57,100 --> 01:19:59,550
Observera att detta länkad lista, är det en stapel.

1027
01:19:59,550 --> 01:20:01,580
Vad vi lägger bara på stacken

1028
01:20:01,580 --> 01:20:09,960
är omedelbart vad vi ska dra av stapeln för att besöka nästa.

1029
01:20:09,960 --> 01:20:14,380
Vi för sent, men några frågor?

1030
01:20:14,380 --> 01:20:23,530
[Student, obegripligt]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Ja. Så om vi har vår länkad lista,

1032
01:20:27,790 --> 01:20:30,150
ström kommer att peka på den här killen,

1033
01:20:30,150 --> 01:20:34,690
och nu är vi bara föra vår länkad lista att fokusera på den här killen.

1034
01:20:34,690 --> 01:20:44,200
Vi korsar över det länkade listan i den linjen.

1035
01:20:44,200 --> 01:20:51,200
Och då jag antar att vi borde befria vår länkad lista och sånt

1036
01:20:51,200 --> 01:20:53,880
gång innan han återvände sant eller falskt, måste vi

1037
01:20:53,880 --> 01:20:57,360
iterera över vår länkad lista och alltid här nere, antar jag,

1038
01:20:57,360 --> 01:21:03,900
Om vi ​​nuvarande rätt är inte lika med, lägga det, så nu vill vi frigöra

1039
01:21:03,900 --> 01:21:09,600
nuvarande eftersom bra, vi glömmer helt om listan? Ja.

1040
01:21:09,600 --> 01:21:12,880
Så det är vad vi vill göra här.

1041
01:21:12,880 --> 01:21:16,730
Var är pekaren?

1042
01:21:16,730 --> 01:21:23,320
Cur var då - vi vill en struct lista * 10 är lika med listan nästa.

1043
01:21:23,320 --> 01:21:29,240
Gratis listan, lista = temp.

1044
01:21:29,240 --> 01:21:32,820
Och i de fall där vi återvänder sant, behöver vi iterera

1045
01:21:32,820 --> 01:21:37,050
under resten av vår länkad lista befria saker.

1046
01:21:37,050 --> 01:21:39,700
Det fina med den rekursiva lösningen frigör saker

1047
01:21:39,700 --> 01:21:44,930
betyder bara poppar factorings utanför stapeln som kommer att hända för dig.

1048
01:21:44,930 --> 01:21:50,720
Så vi har gått från något som är som 3 rader svåra att tänka-om kod

1049
01:21:50,720 --> 01:21:57,520
till något som är betydligt många fler svåra att tänka-om rader kod.

1050
01:21:57,520 --> 01:22:00,620
Några fler frågor?

1051
01:22:00,620 --> 01:22:08,760
Okej. Vi är bra. Hej!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]