1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [7. jagu: mugavam]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvardi Ülikool]

3
00:00:05,090 --> 00:00:07,930
[See on CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Hea küll. Nii nagu ma ütlesin oma e-posti,

5
00:00:10,110 --> 00:00:14,060
see saab olema binaarsed-tree-intensiivne jagu.

6
00:00:14,060 --> 00:00:16,820
Aga seal ei ole, et palju küsimusi.

7
00:00:16,820 --> 00:00:18,920
Nii et me ei kavatse proovida ja venitama iga küsimus

8
00:00:18,920 --> 00:00:25,430
ja lähevad valus üksikasjalikult kõiki parimaid viise, kuidas asju teha.

9
00:00:25,430 --> 00:00:31,200
Nii et kohe alguses, me läheme läbi proovi joonised kahendpuuks ja värki.

10
00:00:31,200 --> 00:00:35,970
Nii et siin, "Pea meeles, et kahendpuu on sõlmed sarnased seotud nimekirja,

11
00:00:35,970 --> 00:00:38,150
välja arvatud ühe asemel osuti on kaks: üks vasakul "laps"

12
00:00:38,150 --> 00:00:41,950
ja üks õige "laps". "

13
00:00:41,950 --> 00:00:45,630
Nii kahendpuu on nagu seotud nimekirja,

14
00:00:45,630 --> 00:00:47,910
välja arvatud struktuure saab olema kaks suunanäitajaks.

15
00:00:47,910 --> 00:00:51,390
Seal on trinary puud, mis hakkavad olema kolm suunanäitajaks,

16
00:00:51,390 --> 00:00:56,540
on n-aarne puud, mis tuleb lihtsalt geneeriliste pointer

17
00:00:56,540 --> 00:01:00,320
et siis pead malloc olema piisavalt suured

18
00:01:00,320 --> 00:01:04,840
piisavalt viiteid, et kõik võimalikud lapsed.

19
00:01:04,840 --> 00:01:08,200
Nii kahendpuu lihtsalt juhtub olema konstantne number kaks.

20
00:01:08,200 --> 00:01:11,260
Kui soovite, võite anda lingitud nimekirja unaarsed puu,

21
00:01:11,260 --> 00:01:15,360
aga ma ei usu, et keegi seda nimetab, et.

22
00:01:15,360 --> 00:01:18,060
"Joonista kasti-ja-nooled skeem kahendpuu sõlme

23
00:01:18,060 --> 00:01:24,110
sisaldavad Nate lemmik number, 7, kus iga laps osuti on null. "

24
00:01:24,110 --> 00:01:27,780
Nii iPad režiimis.

25
00:01:27,780 --> 00:01:30,280
>> See saab olema üsna lihtne.

26
00:01:30,280 --> 00:01:36,150
Me lihtsalt läheb on sõlm, ma joonistan seda ruutu.

27
00:01:36,150 --> 00:01:38,730
Ja ma joonistan väärtused siin.

28
00:01:38,730 --> 00:01:41,090
Nii et raha läheb siia,

29
00:01:41,090 --> 00:01:44,770
ja siis siia me peame vasakule kursori vasakule ja paremale kursor paremale.

30
00:01:44,770 --> 00:01:50,430
Ja see on väga palju nii konventsiooni nimetada seda vasakule ja paremale, kursor nimed.

31
00:01:50,430 --> 00:01:52,460
Mõlemad hakkavad olema null.

32
00:01:52,460 --> 00:01:57,870
See oleks lihtsalt null, ja et oleks lihtsalt null.

33
00:01:57,870 --> 00:02:03,630
Okei. Nii tagasi siin.

34
00:02:03,630 --> 00:02:05,700
"Mis lingitud nimekiri, oli meil ainult salvestada pointer

35
00:02:05,700 --> 00:02:09,639
esimese sõlme loetelu, et mäletan kogu seotud nimekirja, või kogu nimekirja.

36
00:02:09,639 --> 00:02:11,650
Samuti puid, meil on ainult salvestada pointer

37
00:02:11,650 --> 00:02:13,420
ühe sõlme, et meeles pidada terve puu.

38
00:02:13,420 --> 00:02:15,980
See sõlm on calle "root" puu.

39
00:02:15,980 --> 00:02:18,320
Tugineda oma skeem alates enne või joonista uus

40
00:02:18,320 --> 00:02:21,690
nii, et teil on kastid ja-nooled kujutamine kahendpuu

41
00:02:21,690 --> 00:02:25,730
koos väärtus 7, siis 3 vasakule,

42
00:02:25,730 --> 00:02:32,760
siis 9 paremal, ning seejärel 6 paremal 3 ".

43
00:02:32,760 --> 00:02:34,810
Vaatame, kas ma mäletan kõike seda oma peas.

44
00:02:34,810 --> 00:02:37,670
Nii et see saab olema meie juur siin.

45
00:02:37,670 --> 00:02:41,600
Me peame mõned osuti kuhugi, midagi, mida me kutsume juur,

46
00:02:41,600 --> 00:02:45,140
ja see osutab see kutt.

47
00:02:45,140 --> 00:02:48,490
Nüüd teha uus sõlm,

48
00:02:48,490 --> 00:02:52,870
Mis meil, 3 vasakul?

49
00:02:52,870 --> 00:02:57,140
Nii et uus sõlm 3, ja see algselt toob null.

50
00:02:57,140 --> 00:02:59,190
Ma lihtsalt panna N.

51
00:02:59,190 --> 00:03:02,250
Nüüd tahame teha, et minna vasakule, 7..

52
00:03:02,250 --> 00:03:06,840
Nii et me muudame seda kursorit nüüd käsk see kutt.

53
00:03:06,840 --> 00:03:12,420
Ja me teeme sama. Tahame 9 üle siin

54
00:03:12,420 --> 00:03:14,620
mis esialgu lihtsalt ütleb null.

55
00:03:14,620 --> 00:03:19,600
Me muudame selle osuti, punkt 9,

56
00:03:19,600 --> 00:03:23,310
ja nüüd me tahame panna 6. õigus 3.

57
00:03:23,310 --> 00:03:32,170
Nii see läheb - teha 6.

58
00:03:32,170 --> 00:03:34,310
Ja see kutt on punkt seal.

59
00:03:34,310 --> 00:03:38,320
Okei. Nii et kõik see kutsub meid tegema.

60
00:03:38,320 --> 00:03:42,770
>> Nüüd lähme üle mõned terminoloogia.

61
00:03:42,770 --> 00:03:46,690
Me juba rääkisime sellest, kuidas puu juur on kõige ülemisele sõlme puu.

62
00:03:46,690 --> 00:03:54,720
Üks sisaldab 7. Sõlmede allosas puu kutsutakse lehed.

63
00:03:54,720 --> 00:04:01,240
Iga sõlme, mis lihtsalt on null kui tema lapsed on lehed.

64
00:04:01,240 --> 00:04:03,680
Seega on võimalik, kui meie kahendpuu on vaid ühe sõlme,

65
00:04:03,680 --> 00:04:10,130
et puu on lehed, ja ongi kõik.

66
00:04:10,130 --> 00:04:12,060
"" Kõrgus "puu on number humala sa pead tegema

67
00:04:12,060 --> 00:04:16,620
saada ülevalt lehed. "

68
00:04:16,620 --> 00:04:18,640
Me võtame arvesse, teises erinevus

69
00:04:18,640 --> 00:04:21,940
vahel tasakaalustatud ja tasakaalustamata kahendpuuks,

70
00:04:21,940 --> 00:04:29,470
kuid nüüd, üldkõrgus selle puu

71
00:04:29,470 --> 00:04:34,520
Ütleksin on 3, kuigi kui sa loendada humala

72
00:04:34,520 --> 00:04:39,710
sa pead tegema, et saada kuni 9, siis see on tõesti ainult kõrgus 2.

73
00:04:39,710 --> 00:04:43,340
Praegu on see tasakaalustamata kahendpuu,

74
00:04:43,340 --> 00:04:49,840
kuid me rääkisime tasakaalustatud kui ta saab olla asjakohane.

75
00:04:49,840 --> 00:04:52,040
Nii et nüüd saame rääkida tippe puu poolest

76
00:04:52,040 --> 00:04:54,700
võrreldes teiste sõlmede puu.

77
00:04:54,700 --> 00:04:59,730
Nüüd oleme vanemad, lapsed, õed-vennad, eellased, alanejad sugulased.

78
00:04:59,730 --> 00:05:05,650
Nad on päris tervet mõistust, mida need tähendavad.

79
00:05:05,650 --> 00:05:09,610
Kui me küsime - see vanemad.

80
00:05:09,610 --> 00:05:12,830
Mis on vanem 3?

81
00:05:12,830 --> 00:05:16,090
[Õpilased] 7. >> Jah. Vanem on lihtsalt saab olema, mida toob teile.

82
00:05:16,090 --> 00:05:20,510
Siis millised on lapsed 7?

83
00:05:20,510 --> 00:05:23,860
[Õpilased] 3 ja 9. >> Jah.

84
00:05:23,860 --> 00:05:26,460
Pange tähele, et "lapsed" tähendab sõna-sõnalt lastele

85
00:05:26,460 --> 00:05:31,010
nii 6 ei kohaldata, sest see on nagu lapselaps.

86
00:05:31,010 --> 00:05:35,540
Aga siis kui me läheme järeltulijad, siis millised on järeltulijad 7?

87
00:05:35,540 --> 00:05:37,500
[Õpilased] 3, 6 ja 9. >> Jah.

88
00:05:37,500 --> 00:05:42,330
Järeltulijad Juursõlme saab olema kõike puu,

89
00:05:42,330 --> 00:05:47,950
välja arvatud ehk root node ise, kui sa ei taha arvata, et järeltulija.

90
00:05:47,950 --> 00:05:50,750
Ja lõpuks, esivanemate, nii et see on vastupidises suunas.

91
00:05:50,750 --> 00:05:55,740
Millised on esivanemad 6?

92
00:05:55,740 --> 00:05:58,920
[Õpilased] 3 ja 7. >> Jah. 9 ei kuulu.

93
00:05:58,920 --> 00:06:02,520
See on lihtsalt otsene sugupuu tagasi juurte

94
00:06:02,520 --> 00:06:13,230
saab olema teie esivanemad.

95
00:06:13,230 --> 00:06:16,300
>> "Me ütleme, et kahendpuu on" tellitud "kui iga sõlme puu,

96
00:06:16,300 --> 00:06:19,530
kõik tema järeltulijad vasakul on väiksem väärtused

97
00:06:19,530 --> 00:06:22,890
ja kõik need, paremal on suuremad väärtused.

98
00:06:22,890 --> 00:06:27,060
Näiteks puu eespool on tellitud, kuid see pole ainus võimalik tellida kokkuleppel. "

99
00:06:27,060 --> 00:06:30,180
Enne saame, et

100
00:06:30,180 --> 00:06:36,420
tellida kahendpuu on tuntud ka Kahendotsingupuu.

101
00:06:36,420 --> 00:06:38,660
Siin juhtub olema nimetades seda tellida kahendpuu,

102
00:06:38,660 --> 00:06:41,850
kuid ma ei ole kunagi kuulnud ta kutsus tellitud kahendpuu enne,

103
00:06:41,850 --> 00:06:46,650
ja viktoriini oleme palju tõenäolisem, et panna Kahendotsingupuu.

104
00:06:46,650 --> 00:06:49,250
Nad on ühe ja sama,

105
00:06:49,250 --> 00:06:54,580
ja see on oluline tunnete vahet kahendpuu ja Kahendotsingupuu.

106
00:06:54,580 --> 00:06:58,830
Kahendpuu on lihtsalt puu, mis viitab kahele asjale.

107
00:06:58,830 --> 00:07:02,120
Iga sõlme viitab kahele asjale.

108
00:07:02,120 --> 00:07:06,310
Ei ole põhjendust umbes väärtusi, mis osutab ta.

109
00:07:06,310 --> 00:07:11,370
Nii meeldib siin, sest see on Kahendotsingupuu,

110
00:07:11,370 --> 00:07:14,030
me teame, et kui me läheme vasakule, 7.,

111
00:07:14,030 --> 00:07:16,670
siis kõik väärtused, et saame võimaluse jõuda

112
00:07:16,670 --> 00:07:19,310
minnes jättis 7. olema vähemalt 7.

113
00:07:19,310 --> 00:07:24,070
Pange tähele, et kõik väärtused on alla 7 on 3 ja 6.

114
00:07:24,070 --> 00:07:26,040
Need on kõik vasakule 7..

115
00:07:26,040 --> 00:07:29,020
Kui me läheme paremale, 7., kõik peab olema suurem kui 7,

116
00:07:29,020 --> 00:07:33,220
nii 9 on paremal 7, nii et me oleme head.

117
00:07:33,220 --> 00:07:36,150
See ei ole puhul kahendpuu,

118
00:07:36,150 --> 00:07:40,020
regulaarset kahendpuu saame lihtsalt on 3 ülaosas, 7 vasakule,

119
00:07:40,020 --> 00:07:47,630
9. vasakule, 7., seal ei ole järjekorda väärtused üldse.

120
00:07:47,630 --> 00:07:56,140
Nüüd me tegelikult ei tee seda, sest see on tüütu ja tarbetu,

121
00:07:56,140 --> 00:07:59,400
kuid "proovida teha nii palju tellitud puud nagu sa ei mõtle

122
00:07:59,400 --> 00:08:01,900
kasutades numbrid 7, 3, 9 ja 6.

123
00:08:01,900 --> 00:08:06,800
Mitu erinevat kord on olemas? Mis on kõrgus iga üks? "

124
00:08:06,800 --> 00:08:10,480
>> Me teeme paar, kuid peamine idee on,

125
00:08:10,480 --> 00:08:16,530
see on kuidagi unikaalne esindatuse kahendpuu sisaldab neid väärtusi.

126
00:08:16,530 --> 00:08:22,760
Kõik me vajame, on mõned kahendpuu, mis sisaldab 7, 3, 6 ja 9.

127
00:08:22,760 --> 00:08:25,960
Teine võimalik kehtiv üks oleks juur on 3,

128
00:08:25,960 --> 00:08:30,260
minna vasakule ja see on 6, minna vasakule ja see on 7,

129
00:08:30,260 --> 00:08:32,730
minna vasakule ja see on 9.

130
00:08:32,730 --> 00:08:36,169
See on täiesti kehtiva Kahendotsingupuu.

131
00:08:36,169 --> 00:08:39,570
See ei ole väga kasulik, sest see on nagu seotud nimekirja

132
00:08:39,570 --> 00:08:43,750
ja kõik need osuti on lihtsalt null.

133
00:08:43,750 --> 00:08:48,900
Aga see on kehtiv puu. Jah?

134
00:08:48,900 --> 00:08:51,310
[Student] Ärge väärtused olema suurem paremal?

135
00:08:51,310 --> 00:08:56,700
Või on see -? >> Need Tahtsin minna teist teed.

136
00:08:56,700 --> 00:09:00,960
Seal on ka - Jah, teeme minna seda.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Hea saak.

138
00:09:07,770 --> 00:09:11,730
See ikka peab alluma mida kahendpuu otsing peaks tegema.

139
00:09:11,730 --> 00:09:15,650
Nii et kõik vasakule peab olema väiksem kui mis tahes sõlme.

140
00:09:15,650 --> 00:09:23,180
Me võiksime lihtsalt liikuda, öelda, et see 6 ja pane see siia.

141
00:09:23,180 --> 00:09:26,880
Ei, me ei saa. Miks ma hoida teed seda?

142
00:09:26,880 --> 00:09:35,350
Teeme - siin on 6, siin on 7, 6 punkti 3.

143
00:09:35,350 --> 00:09:39,290
See on ikka kehtiv Kahendotsingupuu.

144
00:09:39,290 --> 00:09:49,260
Mis on valesti, kui ma - vaatame, kas ma saan tulla kokkuleppel.

145
00:09:49,260 --> 00:09:52,280
Jah, okei. Mis on valesti selle puu?

146
00:09:52,280 --> 00:10:08,920
Ma arvan, et ma olen juba andnud teile vihje, et midagi on valesti.

147
00:10:08,920 --> 00:10:14,430
Miks ma hoida teed seda?

148
00:10:14,430 --> 00:10:18,510
Okei. See näeb mõistlik.

149
00:10:18,510 --> 00:10:22,590
Kui me vaatame iga sõlme, nagu 7, siis vasakule 7 on 3.

150
00:10:22,590 --> 00:10:24,960
Nii et meil on 3 asja paremale 3 on 6.

151
00:10:24,960 --> 00:10:27,750
Ja kui te vaatate 6 asi paremal 6. on 9.

152
00:10:27,750 --> 00:10:30,910
Miks see ei kehti Kahendotsingupuu?

153
00:10:30,910 --> 00:10:36,330
[Õpilased] 9 on ikka vasakule 7.. >> Jah.

154
00:10:36,330 --> 00:10:43,710
See peab olema tõsi, et kõik väärtused saab võimaluse jõuda minnes vasakule 7. on alla 7.

155
00:10:43,710 --> 00:10:49,120
Kui me läheme vasakule, 7., saame 3 ja saame ikka kuni 6,

156
00:10:49,120 --> 00:10:52,520
saame ikka kuni 9, kuid läks alla 7,

157
00:10:52,520 --> 00:10:55,070
me ei tohiks olla võimalik saada arv, mis on suurem kui 7.

158
00:10:55,070 --> 00:10:59,830
Nii et see ei ole kehtiv Kahendotsingupuu.

159
00:10:59,830 --> 00:11:02,330
>> Minu vend tegelikult oli intervjuu küsimus

160
00:11:02,330 --> 00:11:07,760
et põhimõtteliselt oli see lihtsalt koodi üles midagi kinnitada

161
00:11:07,760 --> 00:11:10,500
kas puu on Kahendotsingupuu,

162
00:11:10,500 --> 00:11:13,580
ja nii esimene asi mis ta tegi oli lihtsalt vaadata,

163
00:11:13,580 --> 00:11:17,020
kui vasakul ja paremal on õiged, ja seejärel kinnitada, sinna alla.

164
00:11:17,020 --> 00:11:19,700
Aga sa ei saa lihtsalt teha; teil jälgida

165
00:11:19,700 --> 00:11:22,550
asjaolu, et nüüd, kui ma olen läinud vasakul 7,

166
00:11:22,550 --> 00:11:26,340
kõik siin alampuu peab olema vähemalt 7.

167
00:11:26,340 --> 00:11:28,430
Õige algoritm vajab jälgida

168
00:11:28,430 --> 00:11:35,970
piiridest, et väärtusi saab võimaluse langeda sisse

169
00:11:35,970 --> 00:11:38,360
Me ei lähe läbi kõik.

170
00:11:38,360 --> 00:11:41,630
Seal on kena kordumise suhtes,

171
00:11:41,630 --> 00:11:44,810
kuigi me ei ole muretsenud neile, või me ei saa nendele,

172
00:11:44,810 --> 00:11:47,030
määratleda, kui palju seal tegelikult on.

173
00:11:47,030 --> 00:11:53,180
Nii on 14 neist.

174
00:11:53,180 --> 00:11:56,020
Idee, kuidas te seda teha matemaatiliselt on nagu,

175
00:11:56,020 --> 00:11:59,770
saab valida mis tahes ühekordne olla root node,

176
00:11:59,770 --> 00:12:03,160
ja siis kui ma valin 7. olema root node,

177
00:12:03,160 --> 00:12:08,150
siis on, ütleme, mõned numbrid, et võib minna mu vasak lümfisõlm,

178
00:12:08,150 --> 00:12:10,440
ja seal on mõned numbrid, mis võib olla minu õigus sõlme,

179
00:12:10,440 --> 00:12:15,090
aga kui ma olen n koguarvu, siis summa, mis võib minna vasakule

180
00:12:15,090 --> 00:12:18,820
pluss summa, mis võib minna paremale on n - 1.

181
00:12:18,820 --> 00:12:26,130
Nii et ülejäänud numbrid, nad peavad suutma minna kas vasakule või paremale.

182
00:12:26,130 --> 00:12:31,580
Tundub keeruline, et kui ma panen 3 esimeses siis kõik on minna vasakule,

183
00:12:31,580 --> 00:12:35,080
aga kui ma panen 7, siis mõned asjad võivad minna vasakule ja mõned asjad võivad minna paremale.

184
00:12:35,080 --> 00:12:39,570
Ja '3 esimene "ma mõtlesin kõike võib minna paremale.

185
00:12:39,570 --> 00:12:42,350
See on tõesti, sa lihtsalt pead mõtlema nagu,

186
00:12:42,350 --> 00:12:47,980
kuidas paljud asjad võivad minna järgmisele tasandile puu.

187
00:12:47,980 --> 00:12:50,420
Ja see väljub olla 14 või saate joonistada kõik need,

188
00:12:50,420 --> 00:12:54,650
ja siis saad 14.

189
00:12:54,650 --> 00:13:01,120
>> Tulles tagasi siin,

190
00:13:01,120 --> 00:13:03,510
"Korrastatud kahendpuuks on lahe, sest me saame otsida neile

191
00:13:03,510 --> 00:13:06,910
väga sarnaselt otsides üle järjestatud massiivist.

192
00:13:06,910 --> 00:13:10,120
Selleks hakkame keskmes ja töö meie tee puu otsast alla

193
00:13:10,120 --> 00:13:13,440
suunas lehed, kontrollides iga sõlme väärtusi ELi väärtustega vastuolus me otsite.

194
00:13:13,440 --> 00:13:15,810
Kui praegune tipp väärtus on väiksem kui me otsime,

195
00:13:15,810 --> 00:13:18,050
te lähete kõrval sõlme õigust lapsele.

196
00:13:18,050 --> 00:13:20,030
Muidu lähete sõlm vasakus laps.

197
00:13:20,030 --> 00:13:22,800
Mingil hetkel, siis kas leida raha otsite, või saad joosta null,

198
00:13:22,800 --> 00:13:28,520
näidatud osutatud teenuste maksumus pole puus. "

199
00:13:28,520 --> 00:13:32,450
Ma pean ekraanigraafika puu oli meil enne; et võtan teise.

200
00:13:32,450 --> 00:13:38,280
Aga me tahame otsida kas 6, 10, ja 1 on puu.

201
00:13:38,280 --> 00:13:49,180
Nii et mis see oli, 7, 9, 3, 6. Okei.

202
00:13:49,180 --> 00:13:52,730
Numbrid, mida soovite otsida, me tahame otsida 6.

203
00:13:52,730 --> 00:13:55,440
Kuidas see algoritm toimib?

204
00:13:55,440 --> 00:14:03,040
Noh, meil on ka mõned root kursor meie puu.

205
00:14:03,040 --> 00:14:12,460
Ja me oleks minna root ja öelda, on see väärtus võrdub Me otsite?

206
00:14:12,460 --> 00:14:15,000
Nii et me otsime 6, nii see ei ole võrdne.

207
00:14:15,000 --> 00:14:20,140
Nii et me jätkame, ja nüüd me ütleme, okei, nii 6 on väiksem kui 7.

208
00:14:20,140 --> 00:14:23,940
Kas see tähendab, me tahame minna vasakule või me tahame minna eks?

209
00:14:23,940 --> 00:14:27,340
[Student] vasakule. >> Jah.

210
00:14:27,340 --> 00:14:33,340
See on tunduvalt lihtsam, kõik mida sa pead tegema, on teha üks võimalik sõlme puu

211
00:14:33,340 --> 00:14:37,760
ja siis sa ei - selle asemel, et mõelda oma peaga,

212
00:14:37,760 --> 00:14:40,020
okei, kui see on väiksem, ma lähen vasakule või minna paremale,

213
00:14:40,020 --> 00:14:43,030
lihtsalt vaadates seda pilti, siis on väga selge, et ma pean minema vasakule

214
00:14:43,030 --> 00:14:47,700
kui sõlm on suurem kui väärtus, et ma otsin.

215
00:14:47,700 --> 00:14:52,600
Nii et te lähete vasakule, nüüd olen kell 3.

216
00:14:52,600 --> 00:14:57,770
Tahan - 3 on väiksem kui ma otsin, mis on 6.

217
00:14:57,770 --> 00:15:03,420
Nii et me lähme paremale, ja nüüd ma lõpuks kell 6,

218
00:15:03,420 --> 00:15:07,380
mis on väärtus Otsin, nii et ma tagasi true.

219
00:15:07,380 --> 00:15:15,760
Järgmise väärtuse Ma lähen otsima on 10.

220
00:15:15,760 --> 00:15:23,230
Okei. Nii et 10 nüüd, läheb - ära lõigatud, et - minnes järgige juur.

221
00:15:23,230 --> 00:15:27,670
Nüüd, 10 saab olema suurem kui 7, nii et ma tahan vaadata paremale.

222
00:15:27,670 --> 00:15:31,660
Ma lähen siia tulla, 10. saab olema suurem kui 9,

223
00:15:31,660 --> 00:15:34,520
nii et ma lähen taha vaadata paremale.

224
00:15:34,520 --> 00:15:42,100
Ma tulen siia, aga siin nüüd ma olen null.

225
00:15:42,100 --> 00:15:44,170
Mida teha, kui ma tabanud null?

226
00:15:44,170 --> 00:15:47,440
[Student] Tagasi vale? >> Jah. Ma ei leia 10.

227
00:15:47,440 --> 00:15:49,800
1 saab olema peaaegu identne juhul,

228
00:15:49,800 --> 00:15:51,950
välja arvatud see lihtsalt läheb keerata, selle asemel et otsida

229
00:15:51,950 --> 00:15:56,540
ette paremal pool, ma lähen vaatan alla vasakule.

230
00:15:56,540 --> 00:16:00,430
>> Nüüd ma arvan, et me tegelikult saada koodi.

231
00:16:00,430 --> 00:16:04,070
Siin, kus - avada CS50 seade ja liikuda oma teed seal,

232
00:16:04,070 --> 00:16:07,010
kuid võite ka lihtsalt teha seda ruumi.

233
00:16:07,010 --> 00:16:09,170
See on ilmselt ideaalne teha seda ruumi,

234
00:16:09,170 --> 00:16:13,760
sest me ei tööta ruumi.

235
00:16:13,760 --> 00:16:19,170
"Esiteks me vajame uut tüüpi määratlus kahendpuu sõlme sisaldav int väärtusi.

236
00:16:19,170 --> 00:16:21,400
Kasutades trafaretset typedef allpool,

237
00:16:21,400 --> 00:16:24,510
luua uus määratlus sõlme kahendpuu.

238
00:16:24,510 --> 00:16:27,930
Kui te jänni. . . "Blaa, blaa, blaa. Okei.

239
00:16:27,930 --> 00:16:30,380
Nii et paneme trafaretset siin,

240
00:16:30,380 --> 00:16:41,630
typedef struktuure sõlm ja sõlme. Jah, okei.

241
00:16:41,630 --> 00:16:44,270
Millised on valdkonnad me ei kavatse soovite meie sõlme?

242
00:16:44,270 --> 00:16:46,520
[Student] Int ja siis kaks viiteid?

243
00:16:46,520 --> 00:16:49,700
>> Int väärtus, kaks viiteid? Kuidas kirjutada viiteid?

244
00:16:49,700 --> 00:16:58,440
[Student] struktuure. >> Ma peaks suumimiseks Jah, nii struct tipp * vasakule,

245
00:16:58,440 --> 00:17:01,320
ja struct tipp * õigus.

246
00:17:01,320 --> 00:17:03,460
Ja pidage meeles arutelu alates viimane kord,

247
00:17:03,460 --> 00:17:15,290
et see ei ole mõistlik, see ei ole mõistlik,

248
00:17:15,290 --> 00:17:18,270
see ei ole mõistlik.

249
00:17:18,270 --> 00:17:25,000
Sa pead kõike seal selleks, et määratleda see rekursiivne struct.

250
00:17:25,000 --> 00:17:27,970
Okei, nii see on, mida meie puu hakkab välja nägema.

251
00:17:27,970 --> 00:17:37,670
Kui me teeksime trinary puu, siis sõlme tunduda B1, B2, struct tipp * B3,

252
00:17:37,670 --> 00:17:43,470
kus b on filiaal - tegelikult, ma olen rohkem kuulnud seda vasakule, keskele, paremale, aga mis iganes.

253
00:17:43,470 --> 00:17:55,610
Me ainult hoolid binaarne, nii paremale, vasakule.

254
00:17:55,610 --> 00:17:59,110
"Nüüd kuulutab maailma tipp * muutuja puu juur."

255
00:17:59,110 --> 00:18:01,510
Nii et me ei kavatse seda teha.

256
00:18:01,510 --> 00:18:08,950
Selleks, et teha asju veidi keerulisemaks ja üldistatud,

257
00:18:08,950 --> 00:18:11,570
meil ei ole maailma tipp muutuja.

258
00:18:11,570 --> 00:18:16,710
Selle asemel, et peamine kuulutame me kõik meie sõlme asju,

259
00:18:16,710 --> 00:18:20,500
ja see tähendab, et allpool, kui me alata

260
00:18:20,500 --> 00:18:23,130
meie Contains funktsioon ja meie sisestada funktsiooni,

261
00:18:23,130 --> 00:18:27,410
asemel meie Contains funktsioon lihtsalt kasutades seda maailma tipp muutuja,

262
00:18:27,410 --> 00:18:34,280
me lähed on see võtta argumendina puu, mis me tahame seda töödelda.

263
00:18:34,280 --> 00:18:36,650
Võttes globaalne muutuja pidi teha asju lihtsamaks.

264
00:18:36,650 --> 00:18:42,310
Me läheme teha asju raskemaks.

265
00:18:42,310 --> 00:18:51,210
Nüüd võta minut või nii lihtsalt ei selline asi,

266
00:18:51,210 --> 00:18:57,690
kus sees peamine soovite luua see puu, ja see on kõik, mida tahame teha.

267
00:18:57,690 --> 00:19:04,530
Proovige ja ehitada see puu oma põhifunktsiooni.

268
00:19:42,760 --> 00:19:47,610
>> Okei. Nii et sa ei pea isegi on ehitatud puust terve tee veel.

269
00:19:47,610 --> 00:19:49,840
Aga kellelgi on midagi, mida ma võiks tõmba

270
00:19:49,840 --> 00:20:03,130
näidata, kuidas võiks alustada ehitamist nagu puu?

271
00:20:03,130 --> 00:20:08,080
[Student] Kellegi peksma, üritavad välja.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Igaüks rahul oma puu ehitamine?

273
00:20:13,100 --> 00:20:15,520
[Student] Muidugi. See ei teinud. >> See on hea. Me ei saa lihtsalt lõpetada -

274
00:20:15,520 --> 00:20:26,860
Oh, saad sa salvestada? Hurraa.

275
00:20:26,860 --> 00:20:32,020
Nii et siin on meil - Oh, ma olen veidi ära lõigatud.

276
00:20:32,020 --> 00:20:34,770
Kas ma suumitud?

277
00:20:34,770 --> 00:20:37,730
Suumimiseks vajutage juhtnuppu välja. >> Mul on küsimus. >> Jah?

278
00:20:37,730 --> 00:20:44,410
[Student] Kui oled määranud struct, on asjad initsialiseeritud midagi?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Okei. Nii et sa oleks initsialiseerida -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Kui oled määranud, või kui te deklareerite struct,

281
00:20:50,450 --> 00:20:55,600
see ei ole vormindatud vaikimisi, see on nagu siis, kui te deklareerite int.

282
00:20:55,600 --> 00:20:59,020
See on täpselt sama asi. See on nagu kõik selle üksikud väljad

283
00:20:59,020 --> 00:21:04,460
võib olla prügi raha ta. >> Ja kas on võimalik määratleda - või kuulutada struct

284
00:21:04,460 --> 00:21:07,740
nii, et see initsialiseerida neid?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Jah. Niisiis, otsetee initsialiseerimise süntaks

286
00:21:13,200 --> 00:21:18,660
läheb välja nägema -

287
00:21:18,660 --> 00:21:22,200
On kaks võimalust saame seda teha. Ma arvan, et me peaksime koostama selle

288
00:21:22,200 --> 00:21:25,840
veenduda rõkkama ka teeb seda.

289
00:21:25,840 --> 00:21:28,510
Selleks argumente, et tegemist on struct,

290
00:21:28,510 --> 00:21:32,170
paned nagu järjekorras argumendid sees need looksulg.

291
00:21:32,170 --> 00:21:35,690
Nii et kui sa tahad initsialiseerida ta kuni 9 ja lahkus olema null ja siis õige olema null,

292
00:21:35,690 --> 00:21:41,570
oleks 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternatiiviks on, ja toimetaja ei meeldi see süntaks,

294
00:21:47,890 --> 00:21:50,300
ja see arvab, et ma tahan uut plokki,

295
00:21:50,300 --> 00:22:01,800
kuid alternatiiv on midagi -

296
00:22:01,800 --> 00:22:04,190
siin, ma panen selle uuele reale.

297
00:22:04,190 --> 00:22:09,140
Võite selgesõnaliselt öelda, ma unustan täpne süntaks.

298
00:22:09,140 --> 00:22:13,110
Nii saab selgesõnaliselt käsitleda neid nimepidi, ja öelda,

299
00:22:13,110 --> 00:22:21,570
. C, või. Väärtus = 9. Vasak = NULL.

300
00:22:21,570 --> 00:22:24,540
Ma arvan, neid tuleb komadega.

301
00:22:24,540 --> 00:22:29,110
. Õigus = NULL, nii et see, kuidas sa ei

302
00:22:29,110 --> 00:22:33,780
tegelikult on vaja teada selleks, et struct,

303
00:22:33,780 --> 00:22:36,650
ja kui sa loed seda, see on palju selgem

304
00:22:36,650 --> 00:22:41,920
mida väärtus kuramuse initsialiseeritud.

305
00:22:41,920 --> 00:22:44,080
>> See juhtub olema üks neist asjadest, mis -

306
00:22:44,080 --> 00:22:49,100
jah, enamasti, C + + on ülemhulk C.

307
00:22:49,100 --> 00:22:54,160
Te võite võtta C-koodi, liigutada üle C + +, ja see peaks koostama.

308
00:22:54,160 --> 00:22:59,570
See on üks asju, mis C + + ei toeta, nii et inimesed kipuvad seda mitte teha.

309
00:22:59,570 --> 00:23:01,850
Ma ei tea, kas see on ainus põhjus, miks inimesed kipuvad seda mitte teha,

310
00:23:01,850 --> 00:23:10,540
kuid juhul, kui mul on vaja seda kasutada vajalikud tööd C + + ja ma ei saanud seda kasutada.

311
00:23:10,540 --> 00:23:14,000
Teine näide millestki, mis ei tööta koos C + + on

312
00:23:14,000 --> 00:23:16,940
kuidas malloc tagastab "void *," tehniliselt,

313
00:23:16,940 --> 00:23:20,200
aga sa võiksid öelda, char * x = malloc iganes,

314
00:23:20,200 --> 00:23:22,840
ja see automaatselt enamus char *.

315
00:23:22,840 --> 00:23:25,450
See automaatne valatud ei juhtu C + +.

316
00:23:25,450 --> 00:23:28,150
See ei kompileerida, ja sa selgelt vaja öelda

317
00:23:28,150 --> 00:23:34,510
char *, malloc, mis iganes, et enamus seda char *.

318
00:23:34,510 --> 00:23:37,270
Ei ole palju asju, C ja C + + on eriarvamusel,

319
00:23:37,270 --> 00:23:40,620
kuid need on kaks.

320
00:23:40,620 --> 00:23:43,120
Nii et me läheme selle süntaks.

321
00:23:43,120 --> 00:23:46,150
Aga isegi kui me ei läinud selle süntaks,

322
00:23:46,150 --> 00:23:49,470
Mis on - võib olla valesti seda?

323
00:23:49,470 --> 00:23:52,170
[Student] Ma ei pea dereference on? >> Jah.

324
00:23:52,170 --> 00:23:55,110
Pea meeles, et nool on kaudne dereference,

325
00:23:55,110 --> 00:23:58,230
ja nii kui me lihtsalt tegelevad struct,

326
00:23:58,230 --> 00:24:04,300
tahame kasutada. nöökima valdkonnas sees struct.

327
00:24:04,300 --> 00:24:07,200
Ja ainus kord me kasutame nool on siis, kui me tahame teha -

328
00:24:07,200 --> 00:24:13,450
Noh, nool on samaväärne -

329
00:24:13,450 --> 00:24:17,020
see on, mida see oleks tähendanud, kui ma kasutasin nool.

330
00:24:17,020 --> 00:24:24,600
Kõik nool abil on, dereference seda, nüüd ma olen struct, ja ma saan valdkonnas.

331
00:24:24,600 --> 00:24:28,040
Kas saan valdkonna otseselt või dereference ja saad valdkonnas -

332
00:24:28,040 --> 00:24:30,380
Ma arvan, et see peaks olema väärtus.

333
00:24:30,380 --> 00:24:33,910
Aga siin ma olen tegelevad ainult struct, ei viida struct,

334
00:24:33,910 --> 00:24:38,780
ja seega ei saa ma kasutada noolt.

335
00:24:38,780 --> 00:24:47,510
Aga selline asi, mida me teha kõik sõlmed.

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

337
00:24:55,790 --> 00:25:09,540
See on 6, 7, ja 3.

338
00:25:09,540 --> 00:25:16,470
Siis saame luua filiaale meie puu, meil on 7 -

339
00:25:16,470 --> 00:25:21,650
Me võime olla oma vasaku peaks punkt 3.

340
00:25:21,650 --> 00:25:25,130
Niisiis, kuidas me seda teeme?

341
00:25:25,130 --> 00:25:29,320
[Õpilased, arusaamatult] >> Jah. Aadress node3,

342
00:25:29,320 --> 00:25:34,170
ja kui sa ei ole aadressi, siis see lihtsalt ei kompileerida.

343
00:25:34,170 --> 00:25:38,190
Kuid pidage meeles, et need on viiteid, et järgmisel keskused.

344
00:25:38,190 --> 00:25:44,930
Õigus peab osutama 9,

345
00:25:44,930 --> 00:25:53,330
ja 3 tuleks märkida õiguse kohta 6.

346
00:25:53,330 --> 00:25:58,480
Minu arvates on see kõik komplekti. Kommentaare või küsimusi?

347
00:25:58,480 --> 00:26:02,060
[Student, arusaamatult] root saab olema 7.

348
00:26:02,060 --> 00:26:08,210
Me ei saa lihtsalt öelda sõlme * ptr =

349
00:26:08,210 --> 00:26:14,160
või juurtest, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Meie eesmärkide läheme tegelema sisestada,

351
00:26:20,730 --> 00:26:25,490
nii me ei kavatse tahan kirjutada funktsiooni lisada see kahendpuu

352
00:26:25,490 --> 00:26:34,230
ja insert ei paratamatult helistada malloc luua uus sõlm seda puud.

353
00:26:34,230 --> 00:26:36,590
Nii et asjad ei hakka räpane sellega, et mõned sõlmed

354
00:26:36,590 --> 00:26:38,590
on praegu korstnat

355
00:26:38,590 --> 00:26:43,680
ja muude sõlmede ei kavatse end sisse hunnik kui me lisada neid.

356
00:26:43,680 --> 00:26:47,640
See on täiesti õige, aga ainus põhjus

357
00:26:47,640 --> 00:26:49,600
suudame seda teha korstnat

358
00:26:49,600 --> 00:26:51,840
sest see on selline kunstlik näide, et me teame

359
00:26:51,840 --> 00:26:56,360
puu peaks olema ehitatud 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Kui me ei ole seda, siis me ei pea malloc esimese koha.

361
00:27:02,970 --> 00:27:06,160
Nagu me näeme veidi hiljem, peaksime malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Praegu on see täiesti mõistlik panna virna,

363
00:27:08,570 --> 00:27:14,750
kuid olgem muuta seda malloc rakendamist.

364
00:27:14,750 --> 00:27:17,160
Nii et kõik need on nüüd saab olema midagi sellist

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

366
00:27:24,240 --> 00:27:28,040
Ja nüüd me hakkame tegema meie kontrolli.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Ma ei tahtnud, et -

368
00:27:34,010 --> 00:27:40,950
tagasi 1, ja siis me saame teha node9-> aga nüüd on asi pointer,

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

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

371
00:27:48,930 --> 00:27:51,410
ja me kavatseme pea seda tegema iga nende sõlmede.

372
00:27:51,410 --> 00:27:57,490
Nii et selle asemel, paneme selle sees eraldi funktsioon.

373
00:27:57,490 --> 00:28:00,620
Nimetagem seda sõlme * build_node,

374
00:28:00,620 --> 00:28:09,050
ja see on mõnevõrra sarnane APIs me ette Huffman kodeerimine.

375
00:28:09,050 --> 00:28:12,730
Anname sulle initializer funktsioone puu

376
00:28:12,730 --> 00:28:20,520
ja deconstructor "funktsioonid" need puud ja sama metsad.

377
00:28:20,520 --> 00:28:22,570
>> Nii et siin me lähed on initializer funktsioon

378
00:28:22,570 --> 00:28:25,170
lihtsalt ehitada sõlm meile.

379
00:28:25,170 --> 00:28:29,320
Ja see läheb vaatama üsna täpselt niimoodi.

380
00:28:29,320 --> 00:28:32,230
Ja ma isegi saab olema laisk ja ei muuda muutuja nimi,

381
00:28:32,230 --> 00:28:34,380
kuigi node9 ei ole mõtet enam.

382
00:28:34,380 --> 00:28:38,610
Oh, ma arvan node9 väärtust ei oleks pidanud 6.

383
00:28:38,610 --> 00:28:42,800
Nüüd saame tagasi node9.

384
00:28:42,800 --> 00:28:49,550
Ja siin me peaks tagasi null.

385
00:28:49,550 --> 00:28:52,690
Igaüks kokku leppida, et build-sõlme funktsioon?

386
00:28:52,690 --> 00:28:59,780
Nii et nüüd me võime lihtsalt helistada, et ehitada ükskõik sõlm antud väärtuse ja null suunanäitajaks.

387
00:28:59,780 --> 00:29:09,750
Nüüd on võimalik helistada, et me saame teha sõlme * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Ja teeme. . .

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

390
00:29:33,980 --> 00:29:39,330
Ja nüüd me tahame luua sama suunanäitajaks,

391
00:29:39,330 --> 00:29:42,470
välja arvatud nüüd kõik on juba nii viiteid

392
00:29:42,470 --> 00:29:48,480
nii ei pea enam aadressi.

393
00:29:48,480 --> 00:29:56,300
Okei. Mis siis viimane asi, mida ma tahan teha?

394
00:29:56,300 --> 00:30:03,850
Seal on viga kontrollimise et ma ei tee.

395
00:30:03,850 --> 00:30:06,800
Mis ehitada sõlm tagasi?

396
00:30:06,800 --> 00:30:11,660
[Student, arusaamatult] >> Jah. Kui malloc ebaõnnestus, siis see tagastab null.

397
00:30:11,660 --> 00:30:16,460
Nii et ma lähen laisalt pane see alla siit asemel teeb tingimus iga.

398
00:30:16,460 --> 00:30:22,320
Kui (node9 == NULL, või - veelgi lihtsam

399
00:30:22,320 --> 00:30:28,020
see võrdub lihtsalt kui ei node9.

400
00:30:28,020 --> 00:30:38,310
Nii et kui ei node9 või mitte node6 või mitte node3 või mitte node7, return 1.

401
00:30:38,310 --> 00:30:42,850
Ehk peaksime printida malloc kukkunud, või midagi.

402
00:30:42,850 --> 00:30:46,680
[Student] Kas vale võrdne tühjaks ka?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Iga null väärtus on väär.

404
00:30:51,290 --> 00:30:53,920
Nii et null on null.

405
00:30:53,920 --> 00:30:56,780
Null on null. Väär on null.

406
00:30:56,780 --> 00:31:02,130
Kõik - päris palju ainult 2 null väärtused on null ja null,

407
00:31:02,130 --> 00:31:07,900
vale on vaid räsi määratletud nulli.

408
00:31:07,900 --> 00:31:13,030
Sama kehtib ka siis, kui me tunnistada globaalne muutuja.

409
00:31:13,030 --> 00:31:17,890
Kui meil oli sõlme * juur siin,

410
00:31:17,890 --> 00:31:24,150
siis - kena asi globaalsed muutujad on see, et neil on alati algväärtusest.

411
00:31:24,150 --> 00:31:27,500
See pole tõsi funktsioone, kuidas sees siin

412
00:31:27,500 --> 00:31:34,870
kui meil on, nagu, sõlme * või sõlme x.

413
00:31:34,870 --> 00:31:37,380
Meil pole aimugi, mida x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
või me võiks neid printida ja need võiksid olla meelevaldne.

415
00:31:40,700 --> 00:31:44,980
See pole tõsi globaalsed muutujad.

416
00:31:44,980 --> 00:31:47,450
Nii sõlme juur või sõlme x.

417
00:31:47,450 --> 00:31:53,410
Vaikimisi kõike, mis on globaalne, kui ei ole selgesõnaliselt vormindatud mõne väärtuse,

418
00:31:53,410 --> 00:31:57,390
on null, nagu selle väärtust.

419
00:31:57,390 --> 00:32:01,150
Nii et siin, sõlme * juur, me ei ole sõnaselgelt initsialiseerida ta midagi,

420
00:32:01,150 --> 00:32:06,350
nii selle vaikimisi väärtus on null, mis on null väärtusega viiteid.

421
00:32:06,350 --> 00:32:11,870
Vaikimisi väärtus x läheb tähenda, et x.value on null,

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

423
00:32:14,260 --> 00:32:21,070
Nii et kuna see on struct kõik väljad struct on null väärtused.

424
00:32:21,070 --> 00:32:24,410
Meil ei ole vaja kasutada, et siin küll.

425
00:32:24,410 --> 00:32:27,320
[Student] structs on teistsugune kui teised muutujad ja teised muutujad

426
00:32:27,320 --> 00:32:31,400
prügi väärtused, need on nullid?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Muud väärtused liiga. Nii x, x on null.

428
00:32:36,220 --> 00:32:40,070
Kui see on globaalse ulatusega, see on esialgne väärtus. >> Okei.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Kas algväärtus sa andsid see või null.

430
00:32:48,950 --> 00:32:53,260
Ma arvan, et hoolitseb see kõik.

431
00:32:53,260 --> 00:32:58,390
>> Okei. Nii et järgmine osa küsimus küsib,

432
00:32:58,390 --> 00:33:01,260
"Nüüd tahame kirjutada funktsioon nimega sisaldab

433
00:33:01,260 --> 00:33:04,930
koos prototüüp bool sisaldab int väärtust. "

434
00:33:04,930 --> 00:33:08,340
Me ei kavatse seda teha bool sisaldab int väärtust.

435
00:33:08,340 --> 00:33:15,110
Meie prototüüp hakkab välja nägema

436
00:33:15,110 --> 00:33:22,380
bool sisaldab (int väärtust.

437
00:33:22,380 --> 00:33:24,490
Ja siis me ka läheb andke seda puud

438
00:33:24,490 --> 00:33:28,870
et tuleb kontrollida, kas see on see väärtus.

439
00:33:28,870 --> 00:33:38,290
Nii sõlme * puu). Okei.

440
00:33:38,290 --> 00:33:44,440
Ja siis me nimetame seda midagi,

441
00:33:44,440 --> 00:33:46,090
äkki me tahame printf või midagi.

442
00:33:46,090 --> 00:33:51,040
Sisaldab 6, meie juurtest.

443
00:33:51,040 --> 00:33:54,300
See peaks tagastama ühe või tõsi,

444
00:33:54,300 --> 00:33:59,390
samas sisaldab 5 juur peaks tagasi false.

445
00:33:59,390 --> 00:34:02,690
Nii et mõtle hetk rakendada seda.

446
00:34:02,690 --> 00:34:06,780
Sa suudad seda teha kas korduvalt või rekursiivselt.

447
00:34:06,780 --> 00:34:09,739
Tore asi, kuidas me oleme seatud asju on see, et

448
00:34:09,739 --> 00:34:12,300
see väärib meie rekursiivne lahendus palju lihtsam

449
00:34:12,300 --> 00:34:14,719
kui globaalne muutuja viis tegid.

450
00:34:14,719 --> 00:34:19,750
Sest kui me lihtsalt peame sisaldab int väärtus, siis on meil kuidagi recursing alla subtrees.

451
00:34:19,750 --> 00:34:24,130
Me oleks pidanud olema eraldi abistaja funktsiooni, et recurses alla subtrees meile.

452
00:34:24,130 --> 00:34:29,610
Aga kuna oleme muutnud teda võtma puu argumendina,

453
00:34:29,610 --> 00:34:32,760
mida ta oleks pidanud alati olnud esimene koht,

454
00:34:32,760 --> 00:34:35,710
nüüd saame recurse kergemini.

455
00:34:35,710 --> 00:34:38,960
Nii iteratiivne või rekursiivne, läheme üle nii,

456
00:34:38,960 --> 00:34:46,139
kuid eks me näeme, et rekursiivne jõuab on üsna lihtne.

457
00:34:59,140 --> 00:35:02,480
Okei. Kas kellelgi on midagi, mida me saame töötada koos?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Mul iteratiivne lahendus. >> Olgu, iteratiivne.

459
00:35:12,000 --> 00:35:16,030
Okei, see näeb hea välja.

460
00:35:16,030 --> 00:35:18,920
Niisiis, tahan jalutada meid läbi on?

461
00:35:18,920 --> 00:35:25,780
[Student] Muidugi. Nii seadsin temp muutuja saada esimese sõlme puu.

462
00:35:25,780 --> 00:35:28,330
Ja siis ma lihtsalt looped läbi samas temp ei võrdu null,

463
00:35:28,330 --> 00:35:31,700
Niisiis, kui oli veel puu, ma arvan.

464
00:35:31,700 --> 00:35:35,710
Ja kui väärtus on võrdne väärtusega, mis temp on suunaga,

465
00:35:35,710 --> 00:35:37,640
siis ta tagastab selle väärtuse.

466
00:35:37,640 --> 00:35:40,210
Vastasel juhul kontrollib ta, kas see on paremal või vasakul poolel.

467
00:35:40,210 --> 00:35:43,400
Kui teil kunagi olukorda, kus pole rohkem puu,

468
00:35:43,400 --> 00:35:47,330
siis tagastab - see väljub silmuse ja tagastab false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okei. Nii et tundub hea.

470
00:35:52,190 --> 00:35:58,470
Igaüks on mingeid kommentaare midagi?

471
00:35:58,470 --> 00:36:02,400
Mul ei ole õigsuse kommentaarid üldse.

472
00:36:02,400 --> 00:36:11,020
Üks asi, mida me teha saame, on see kutt.

473
00:36:11,020 --> 00:36:21,660
Oh, see saab minna veidi piklikud.

474
00:36:21,660 --> 00:36:33,460
Ma teen selle ära. Okei.

475
00:36:33,460 --> 00:36:37,150
>> Igaüks peaks mäletama, kuidas kolmekomponentsete töötab.

476
00:36:37,150 --> 00:36:38,610
Seal on kindlasti olnud viktoriinid varem

477
00:36:38,610 --> 00:36:41,170
mis annavad teile funktsiooni kolmekomponentsete operaator,

478
00:36:41,170 --> 00:36:45,750
ja öelda, tõlkida see, midagi, mis ei kasuta kolmekomponentsete.

479
00:36:45,750 --> 00:36:49,140
Nii et see on väga levinud korral, kui ma arvaks, et kasutada kolmekomponentsete,

480
00:36:49,140 --> 00:36:54,610
kus kui mõned tingimus muutuja midagi,

481
00:36:54,610 --> 00:36:58,580
veel seatud, et sama muutuja midagi muud.

482
00:36:58,580 --> 00:37:03,390
See on midagi, mis väga sageli saab muuta selline asi

483
00:37:03,390 --> 00:37:14,420
kus määrata selle muutuja sellele - või, noh, see on tõsi? Siis see, muidu see.

484
00:37:14,420 --> 00:37:18,550
[Student] Esimene neist on, kui tõsi, eks?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Jah. Kuidas ma alati lugeda on, temp on võrdne väärtus on suurem kui temp väärtus,

486
00:37:25,570 --> 00:37:30,680
siis see, teine ​​see. Ta küsib küsimuse.

487
00:37:30,680 --> 00:37:35,200
Kas see suurem? Siis tehke esimene asi. Else teha teine ​​asi.

488
00:37:35,200 --> 00:37:41,670
Ma peaaegu alati - koolon, ma lihtsalt - minu peas, ma lugesin nagu teisedki.

489
00:37:41,670 --> 00:37:47,180
>> Kas kellelgi on rekursiivne lahendus?

490
00:37:47,180 --> 00:37:49,670
Okei. See üks me läheme - see võib juba olla suur,

491
00:37:49,670 --> 00:37:53,990
kuid me ei kavatse muuta see veelgi parem.

492
00:37:53,990 --> 00:37:58,720
See on päris palju sama täpne ettekujutus.

493
00:37:58,720 --> 00:38:03,060
See on lihtsalt, noh, sa tahad selgitada?

494
00:38:03,060 --> 00:38:08,340
[Student] Muidugi. Nii et me veenduge, et puu ei ole null esimene,

495
00:38:08,340 --> 00:38:13,380
sest kui puu on null siis see läheb tagasi false, sest me ei leidnud seda.

496
00:38:13,380 --> 00:38:19,200
Ja kui seal on veel puu, me minna - me kõigepealt kontrollida, kui väärtus on praeguse sõlme.

497
00:38:19,200 --> 00:38:23,740
Tagasi true, kui see on, ja kui me ei püsi arhiivi vasakul või paremal.

498
00:38:23,740 --> 00:38:25,970
Kas see hea asjakohane? >> Mm-hmm. (Leping)

499
00:38:25,970 --> 00:38:33,880
Nii märkate, et see on peaaegu - struktuurilt väga sarnane iteratiivne lahendus.

500
00:38:33,880 --> 00:38:38,200
See on lihtsalt, et selle asemel recursing, meil oli samas silmus.

501
00:38:38,200 --> 00:38:40,840
Ja tugipunkti siin, kus puud ei võrdu null

502
00:38:40,840 --> 00:38:44,850
oli olukord, milles me puhkes samas silmus.

503
00:38:44,850 --> 00:38:50,200
Nad on väga sarnased. Aga me viime selle ühe sammu edasi.

504
00:38:50,200 --> 00:38:54,190
Nüüd me teeme sama asja siin.

505
00:38:54,190 --> 00:38:57,680
Teade me jälle sama asi nii nendel liinidel,

506
00:38:57,680 --> 00:39:00,220
välja arvatud üks argument on erinev.

507
00:39:00,220 --> 00:39:07,950
Nii et me ei kavatse teha seda arvesse kolmekomponentsete.

508
00:39:07,950 --> 00:39:13,790
I hit võimalus midagi, ja see tegi sümbol. Okei.

509
00:39:13,790 --> 00:39:21,720
Nii et me ei kavatse naasta sisaldab seda.

510
00:39:21,720 --> 00:39:28,030
See hakkab olema mitu rida, noh, suumitud on.

511
00:39:28,030 --> 00:39:31,060
Tavaliselt stilistilise asi, ma ei usu paljud inimesed

512
00:39:31,060 --> 00:39:38,640
Pane ruumi pärast nool, aga ma arvan, et kui sa oled järjekindel, kõik on korras.

513
00:39:38,640 --> 00:39:44,320
Kui väärtus on väiksem kui puu väärtus, me tahame recurse puude vasakule,

514
00:39:44,320 --> 00:39:53,890
muidu me tahame recurse puude õigus.

515
00:39:53,890 --> 00:39:58,610
Nii et oli järgu muuta see otsima väiksem.

516
00:39:58,610 --> 00:40:02,660
Teine etapp muuta see otsima väiksem -

517
00:40:02,660 --> 00:40:09,150
saame lahutada selle mitmele reale.

518
00:40:09,150 --> 00:40:16,500
Okei. Teine etapp on teha näida väiksem on siin,

519
00:40:16,500 --> 00:40:25,860
nii tagastatav väärtus võrdub puu väärtus, või sisaldab mis iganes.

520
00:40:25,860 --> 00:40:28,340
>> See on oluline asi.

521
00:40:28,340 --> 00:40:30,860
Ma ei ole kindel, kas ta seda ütles selgesõnaliselt klassis,

522
00:40:30,860 --> 00:40:34,740
kuid seda nimetatakse lühis hindamine.

523
00:40:34,740 --> 00:40:41,060
Mõte on väärtus == puu väärtus.

524
00:40:41,060 --> 00:40:49,960
Kui see on tõsi, siis see on tõsi, ja me tahame "või" mis iganes on siin.

525
00:40:49,960 --> 00:40:52,520
Nii et ilma isegi mõelda mis iganes on siin,

526
00:40:52,520 --> 00:40:55,070
Mis on kogu avaldis kavatse naasta?

527
00:40:55,070 --> 00:40:59,430
[Student] tõsi? >> Jah, sest tõsi on midagi,

528
00:40:59,430 --> 00:41:04,990
or'd - või tõsi or'd midagi on tingimata tõsi.

529
00:41:04,990 --> 00:41:08,150
Nii et niipea kui me näeme tagastatav väärtus = puu väärtus,

530
00:41:08,150 --> 00:41:10,140
me lihtsalt läheb tagasi tõsi.

531
00:41:10,140 --> 00:41:15,710
Isegi ei kavatse recurse sisaldab täiendavalt sätestatakse rida.

532
00:41:15,710 --> 00:41:20,980
Me ei saa võtta see üks samm edasi.

533
00:41:20,980 --> 00:41:29,490
Tagasi puu ei võrdu null ja kõik see.

534
00:41:29,490 --> 00:41:32,650
Ta tegi seda üks rida funktsioon.

535
00:41:32,650 --> 00:41:36,790
See on ka näide lühis hindamine.

536
00:41:36,790 --> 00:41:40,680
Aga nüüd on see sama mõte -

537
00:41:40,680 --> 00:41:47,320
asemel - nii et kui puud ei võrdu null - või, noh,

538
00:41:47,320 --> 00:41:49,580
kui puu ei võrdne null, mis on halb juhul,

539
00:41:49,580 --> 00:41:54,790
kui puu võrdub null, siis esimene tingimus saab olema vale.

540
00:41:54,790 --> 00:42:00,550
Nii et vale anded midagi saab olema mida?

541
00:42:00,550 --> 00:42:04,640
[Student] False. >> Jah. See on teine ​​pool lühis hindamine,

542
00:42:04,640 --> 00:42:10,710
kus kui puu ei võrdne null, siis me ei kavatse isegi minna -

543
00:42:10,710 --> 00:42:14,930
või kui puu ei võrdne null, siis me ei kavatse teha raha == puu väärtus.

544
00:42:14,930 --> 00:42:17,010
Me lihtsalt läheb kohe tagasi false.

545
00:42:17,010 --> 00:42:20,970
Kumb on olulisem, sest kui ta ei lühis hinnata

546
00:42:20,970 --> 00:42:25,860
siis, kui puud ei võrdne null, see teine ​​tingimus läheb SEG süü,

547
00:42:25,860 --> 00:42:32,510
sest puu-> väärtus viite mahavõtmine null.

548
00:42:32,510 --> 00:42:40,490
Nii et see on. Kas teha seda - vahetustega kord üle.

549
00:42:40,490 --> 00:42:44,840
See on väga levinud asi ka, ei tee see üks Vastavalt sellele,

550
00:42:44,840 --> 00:42:49,000
aga see on tavaline asi tingimustes, võibolla mitte siin,

551
00:42:49,000 --> 00:42:59,380
aga kui (puu! = NULL, ja puu-> väärtus == väärtus), mida iganes.

552
00:42:59,380 --> 00:43:01,560
See on väga üldine seisund, kus selle asemel,

553
00:43:01,560 --> 00:43:06,770
murda kaheks IFS, kus meeldib, on puu null?

554
00:43:06,770 --> 00:43:11,780
Okei, see ei ole null, nii et nüüd on puu maksumus on võrdne väärtus? Tehke seda.

555
00:43:11,780 --> 00:43:17,300
Selle asemel, see tingimus, see ei saa kunagi seg süü

556
00:43:17,300 --> 00:43:21,220
sest see puhkeb, kui see juhtub olema null.

557
00:43:21,220 --> 00:43:24,000
Noh, ma arvan, kui teie puu on täiesti vale pointer, see saab ikka seg süü,

558
00:43:24,000 --> 00:43:26,620
kuid see ei saa seg süü, kui puu on null.

559
00:43:26,620 --> 00:43:32,900
Kui see oleks null, see murraks enne sa kunagi dereferenced kursor esimese koha.

560
00:43:32,900 --> 00:43:35,000
[Student] Kas see nn laisk hindamine?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy hindamine on eraldi asi.

562
00:43:40,770 --> 00:43:49,880
Lazy hindamine on rohkem nagu te küsite väärtus,

563
00:43:49,880 --> 00:43:54,270
te küsite väärtust arvutada, millist, aga sa ei pea seda kohe.

564
00:43:54,270 --> 00:43:59,040
Nii et kuni te tegelikult vaja, siis ei hinnata.

565
00:43:59,040 --> 00:44:03,920
See ei ole täpselt sama asi, kuid Huffman pset,

566
00:44:03,920 --> 00:44:06,520
ta ütleb, et me "laisalt" kirjutada.

567
00:44:06,520 --> 00:44:08,670
Põhjus, miks me seda teha on, sest me tegelikult puhverdusvõime kirjutada -

568
00:44:08,670 --> 00:44:11,820
me ei taha, et kirjutada üksikute bitti korraga,

569
00:44:11,820 --> 00:44:15,450
või üksikute baiti korraga, me asemel tahad tüki baiti.

570
00:44:15,450 --> 00:44:19,270
Siis kui meil on patakas baiti, siis me kirjutame selle välja.

571
00:44:19,270 --> 00:44:22,640
Kuigi te küsite seda kirjutada - ja ümbernimetamisel nimega ja fread teha sama asi.

572
00:44:22,640 --> 00:44:26,260
Nad puhverdada oma loeb ja kirjutab.

573
00:44:26,260 --> 00:44:31,610
Kuigi te küsite seda kirjutada kohe, siis ilmselt mitte.

574
00:44:31,610 --> 00:44:34,540
Ja sa ei saa olla kindel, et asjad hakkavad olema kirjutatud

575
00:44:34,540 --> 00:44:37,540
kuni helistate hfclose või mis iganes see on,

576
00:44:37,540 --> 00:44:39,620
mis siis ütleb, okei, ma sulgemise minu faili

577
00:44:39,620 --> 00:44:43,450
see tähendab, et ma parem kirjutan kõik, mida ma ei ole kirjutanud veel.

578
00:44:43,450 --> 00:44:45,770
Tal ei ole vaja kirjutada kõike välja

579
00:44:45,770 --> 00:44:49,010
kuni sulgete faili ning siis peab.

580
00:44:49,010 --> 00:44:56,220
Nii et see just see, mida laisk - ta ootab, kuni see peab juhtuma.

581
00:44:56,220 --> 00:44:59,990
See - võtta 51 ja lähete sinna üksikasjalikumalt,

582
00:44:59,990 --> 00:45:05,470
sest ocaml ja kõik 51, kõik on rekursioon.

583
00:45:05,470 --> 00:45:08,890
Puuduvad iteratiivne lahendusi, põhimõtteliselt.

584
00:45:08,890 --> 00:45:11,550
Kõik on rekursioon, ja laisk hindamine

585
00:45:11,550 --> 00:45:14,790
saab olema oluline palju asjaolusid

586
00:45:14,790 --> 00:45:19,920
kus, kui sa ei laisalt hinnata, see tähendab -

587
00:45:19,920 --> 00:45:24,760
Näiteks on ojad, mis on lõpmatult pikk.

588
00:45:24,760 --> 00:45:30,990
Teoreetiliselt sa ei mõtle füüsilised näitajad nagu oja 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Nii laisalt hinnatud asjad on ilusad.

590
00:45:33,090 --> 00:45:37,210
Kui ma ütlen, ma tahan 10. number, siis saan ma hinnata kuni 10. number.

591
00:45:37,210 --> 00:45:40,300
Kui ma tahan sajandik number, siis saan ma hinnata kuni sajandik arv.

592
00:45:40,300 --> 00:45:46,290
Ilma laisk hindamine, siis see saab püüda hinnata kõik numbrid kohe.

593
00:45:46,290 --> 00:45:50,000
Sa hindamiseks lõpmata palju numbreid ja et lihtsalt ei ole võimalik.

594
00:45:50,000 --> 00:45:52,080
Seega on palju olukordi, kus laisk hindamine

595
00:45:52,080 --> 00:45:57,840
on lihtsalt oluline, et saada asju teha.

596
00:45:57,840 --> 00:46:05,260
>> Nüüd tahame kirjutada sisestada kus insert saab olema

597
00:46:05,260 --> 00:46:08,430
Samamoodi muutub selle määratluses.

598
00:46:08,430 --> 00:46:10,470
Nii et just nüüd on see bool sisestada (int väärtus).

599
00:46:10,470 --> 00:46:23,850
Me muudame seda, et kuni bool sisestada (int väärtus, sõlme * puu).

600
00:46:23,850 --> 00:46:29,120
Me tegelikult muudame et jälle natuke, näeme miks.

601
00:46:29,120 --> 00:46:32,210
Ja liigume build_node, lihtsalt kuradit see,

602
00:46:32,210 --> 00:46:36,730
Ülaltoodud sisestada nii et me ei pea kirjutama funktsiooni prototüüp.

603
00:46:36,730 --> 00:46:42,450
Mis on vihje, et sa kavatsed kasutada build_node lisamis.

604
00:46:42,450 --> 00:46:49,590
Okei. Võtke minut eest.

605
00:46:49,590 --> 00:46:52,130
Ma arvan, et ma päästsin vaadata, kui sa tahad tõmmata sellest,

606
00:46:52,130 --> 00:47:00,240
või vähemalt ma tegin nüüd.

607
00:47:00,240 --> 00:47:04,190
Tahtsin veidi pausi mõelda loogika sisestada,

608
00:47:04,190 --> 00:47:08,750
kui te ei saa mõelda.

609
00:47:08,750 --> 00:47:12,860
Põhimõtteliselt te ainult kunagi sisestamist kell lehed.

610
00:47:12,860 --> 00:47:18,640
Nagu, kui ma sisestan 1, siis ma paratamatult tuleb lisada 1 -

611
00:47:18,640 --> 00:47:21,820
Ma muudan must - Tulen lisada 1 üle siin.

612
00:47:21,820 --> 00:47:28,070
Või kui ma sisestan 4, ma tahan olla sisestades 4 üle siin.

613
00:47:28,070 --> 00:47:32,180
Nii et ükskõik mida sa teed, sa lähed tuleb lisada kell lehed.

614
00:47:32,180 --> 00:47:36,130
Kõik, mida selleks vaja on itereerima puu otsast alla kuni jõuad sõlme

615
00:47:36,130 --> 00:47:40,890
et peaks olema sõlme vanem, uus sõlm vanem,

616
00:47:40,890 --> 00:47:44,560
ja siis muuda oma vasakule või paremale kursor sõltuvalt sellest, kas

617
00:47:44,560 --> 00:47:47,060
see on suurem või väiksem kui praegune tipp.

618
00:47:47,060 --> 00:47:51,180
Muutus et osuti juhtida teie uus sõlm.

619
00:47:51,180 --> 00:48:05,490
Nii itereerima puu otsast alla, teevad lehed käsk uus sõlm.

620
00:48:05,490 --> 00:48:09,810
Mõelge ka, miks see keelab sellisesse olukorda enne,

621
00:48:09,810 --> 00:48:17,990
kus ma ehitatud kahendpuu, kus see oli õige

622
00:48:17,990 --> 00:48:19,920
kui te ainult vaatasin ühe sõlme,

623
00:48:19,920 --> 00:48:24,830
kuid 9 oli vasakul 7, kui sa pidasid maha kogu tee.

624
00:48:24,830 --> 00:48:29,770
Nii et see on võimatu selle stsenaariumi, sest -

625
00:48:29,770 --> 00:48:32,530
arvad sisestamist 9 või midagi; päris esimese sõlme,

626
00:48:32,530 --> 00:48:35,350
Ma lähen, et näha 7 ja ma lihtsalt lähen paremale.

627
00:48:35,350 --> 00:48:38,490
Nii et ükskõik, mida ma teen, kui ma lisada minnes lehed,

628
00:48:38,490 --> 00:48:40,790
ja lehed, kasutades sobivat algoritmi,

629
00:48:40,790 --> 00:48:43,130
see saab olema võimatu mul sisestada 9. vasakul 7.

630
00:48:43,130 --> 00:48:48,250
sest niipea kui ma tabanud 7 Ma lähen paremale.

631
00:48:59,740 --> 00:49:02,070
Kas kellelgi on midagi alustada?

632
00:49:02,070 --> 00:49:05,480
[Student] mina. >> Muidugi.

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

634
00:49:09,200 --> 00:49:14,390
[Other üliõpilane, arusaamatult]

635
00:49:14,390 --> 00:49:18,330
[Bowden] See on teretulnud. Okei. Tahad seletada?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Kuna me teame, et me olime lisades

637
00:49:20,690 --> 00:49:24,060
uus sõlmede lõpus puu,

638
00:49:24,060 --> 00:49:28,070
Ma looped läbi puu iteratiivselt

639
00:49:28,070 --> 00:49:31,360
kuni ma sain sõlme, mis osutas tühjaks.

640
00:49:31,360 --> 00:49:34,220
Ja siis ma otsustasin panna see kas paremal või vasakul

641
00:49:34,220 --> 00:49:37,420
kasutavad seda õigust muutuja; ta ütles mulle, kuhu panna seda.

642
00:49:37,420 --> 00:49:41,850
Ja siis sisuliselt, ma lihtsalt tegin, et viimane -

643
00:49:41,850 --> 00:49:47,520
et temp sõlme käsk uus sõlm, et ta lõi,

644
00:49:47,520 --> 00:49:50,770
kas vasakul või paremal pool, sõltuvalt sellest, mida raha õige oli.

645
00:49:50,770 --> 00:49:56,530
Lõpuks seadsin uue sõlme väärtusega oma katse.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okei, nii et ma näen üks küsimus siin.

647
00:49:59,550 --> 00:50:02,050
See on nagu 95% teel sinna.

648
00:50:02,050 --> 00:50:07,550
Üks küsimus, mida ma näen, noh, ei keegi teine ​​näha probleemi?

649
00:50:07,550 --> 00:50:18,400
Mis on asjaolu, mille alusel nad murda läbi silmuse?

650
00:50:18,400 --> 00:50:22,100
[Student] Kui temp on null? >> Jah. Niisiis, kuidas sa murda läbi silmuse on kui temp on null.

651
00:50:22,100 --> 00:50:30,220
Aga mida ma teen siin?

652
00:50:30,220 --> 00:50:35,410
Ma dereference temp, mis on paratamatult null.

653
00:50:35,410 --> 00:50:39,840
Nii teine ​​asi, mida pead tegema, on mitte ainult jälgida kuni temp on null,

654
00:50:39,840 --> 00:50:45,590
soovite jälgida vanem kogu aeg.

655
00:50:45,590 --> 00:50:52,190
Samuti tahame sõlme * vanem, ma arvan, suudame hoida, mis on null alguses.

656
00:50:52,190 --> 00:50:55,480
See saab olema imelik käitumine just puu,

657
00:50:55,480 --> 00:50:59,210
aga me jõuame selleni.

658
00:50:59,210 --> 00:51:03,950
Kui väärtus on suurem kui mis iganes, siis temp = temp õige.

659
00:51:03,950 --> 00:51:07,910
Aga enne kui me seda teeme, vanem = temp.

660
00:51:07,910 --> 00:51:14,500
Või on vanemad alati saab võrdne temp? Kas see on nii?

661
00:51:14,500 --> 00:51:19,560
Kui temp ei ole null, siis ma lähen liiguta alla, ükskõik mida,

662
00:51:19,560 --> 00:51:24,030
et sõlm, mille temp on vanem.

663
00:51:24,030 --> 00:51:27,500
Nii et vanem saab olema temp, ja siis ma liikuda temp alla.

664
00:51:27,500 --> 00:51:32,410
Nüüd temp on null, kuid lapsevanem võrra vanem asi, mis on null.

665
00:51:32,410 --> 00:51:39,110
Nii et siin all, ma ei taha seada paremale võrdub 1.

666
00:51:39,110 --> 00:51:41,300
Nii et kolisin õige, nii et kui õige = 1,

667
00:51:41,300 --> 00:51:45,130
ja ma arvan, et sa ka tahad teha -

668
00:51:45,130 --> 00:51:48,530
kui liigutad vasakule, mille soovite seada õige võrdne 0-ga.

669
00:51:48,530 --> 00:51:55,950
Või muidu, kui sa kunagi liikuda paremale.

670
00:51:55,950 --> 00:51:58,590
Nii et õige = 0. Kui õige = 1,

671
00:51:58,590 --> 00:52:04,260
nüüd me tahame teha vanema õigus osuti newnode,

672
00:52:04,260 --> 00:52:08,520
muidu me tahame teha vanema vasakul osuti newnode.

673
00:52:08,520 --> 00:52:16,850
Küsimused, mis?

674
00:52:16,850 --> 00:52:24,880
Okei. Nii et see on viis, kuidas me - noh, tegelikult, selle asemel et teha seda,

675
00:52:24,880 --> 00:52:29,630
me poolel oodata teil kasutada build_node.

676
00:52:29,630 --> 00:52:40,450
Ja siis kui newnode võrdub null, tagastab false.

677
00:52:40,450 --> 00:52:44,170
See on tehtud. Nüüd on see, mida me ootasime, et sa teeksid.

678
00:52:44,170 --> 00:52:47,690
>> See on see, mida töötajad lahendusi teha.

679
00:52:47,690 --> 00:52:52,360
Ma ei nõustu seda "õiget" teed läheb midagi

680
00:52:52,360 --> 00:52:57,820
kuid see on täiesti trahvi ja ta töötab.

681
00:52:57,820 --> 00:53:02,840
Üks asi, mis on natuke imelik praegu on

682
00:53:02,840 --> 00:53:08,310
kui puu hakkab välja nagu null, võtame aastal null puu.

683
00:53:08,310 --> 00:53:12,650
Ma arvan, et see sõltub sellest, kuidas määratleda käitumine läbivad null puu.

684
00:53:12,650 --> 00:53:15,490
Ma arvan, et kui te kaotate aastal null puu,

685
00:53:15,490 --> 00:53:17,520
siis sisestades väärtuse null puu

686
00:53:17,520 --> 00:53:23,030
peaks lihtsalt tagasi puu otsa, kus ainult raha on see, et ühe sõlme.

687
00:53:23,030 --> 00:53:25,830
Kas inimesed nõus? Sa võid, kui sa tahad,

688
00:53:25,830 --> 00:53:28,050
kui te kaotate aastal null puu

689
00:53:28,050 --> 00:53:31,320
ja soovite lisada väärtust sinna, tagastab false.

690
00:53:31,320 --> 00:53:33,830
See on kuni teil määrata see.

691
00:53:33,830 --> 00:53:38,320
Selleks esimene asi, mida ma ütlesin ja siis -

692
00:53:38,320 --> 00:53:40,720
Noh, sa lähed on hädas seda tehes, sest

693
00:53:40,720 --> 00:53:44,090
oleks lihtsam, kui meil oleks globaalne kursor asi,

694
00:53:44,090 --> 00:53:48,570
kuid me ei ole nii, kui puu on null, ei saa me midagi teha sellest.

695
00:53:48,570 --> 00:53:50,960
Me ei saa lihtsalt tagasi false.

696
00:53:50,960 --> 00:53:52,840
Nii et ma lähen muuta sisestada.

697
00:53:52,840 --> 00:53:56,540
Me tehniliselt võiks lihtsalt muuta see siin,

698
00:53:56,540 --> 00:53:58,400
kuidas see itereerimise asjade üle,

699
00:53:58,400 --> 00:54:04,530
aga ma lähen muuta sisestada võtta sõlme ** puu.

700
00:54:04,530 --> 00:54:07,510
Double suunanäitajaks.

701
00:54:07,510 --> 00:54:09,710
Mida see tähendab?

702
00:54:09,710 --> 00:54:12,330
Selle asemel tegelevad vihjeid tippu,

703
00:54:12,330 --> 00:54:16,690
asi, mida ma lähen tuleb manipuleerides on see pointer.

704
00:54:16,690 --> 00:54:18,790
Ma lähen tuleb manipuleerides see pointer.

705
00:54:18,790 --> 00:54:21,770
Ma lähen tuleb manipuleerides osuti otse.

706
00:54:21,770 --> 00:54:25,760
See on mõistlik, sest mõtle ette -

707
00:54:25,760 --> 00:54:33,340
Noh, praegu viitab see tühjaks.

708
00:54:33,340 --> 00:54:38,130
Mida ma tahan teha, on muuta seda osuti osutada ole null.

709
00:54:38,130 --> 00:54:40,970
Ma tahan, et see käsk minu uus sõlm.

710
00:54:40,970 --> 00:54:44,870
Kui ma lihtsalt jälgida viiteid minu suunanäitajaks,

711
00:54:44,870 --> 00:54:47,840
siis ma ei vaja jälgida vanem pointer.

712
00:54:47,840 --> 00:54:52,640
Võin vaid jälgida, et näha, kui kursor on suunaga null,

713
00:54:52,640 --> 00:54:54,580
ja kui kursor on suunaga null,

714
00:54:54,580 --> 00:54:57,370
muuda see käsk sõlme tahan.

715
00:54:57,370 --> 00:55:00,070
Ja ma ei saa seda muuta kuna mul on kursor pointer.

716
00:55:00,070 --> 00:55:02,040
Vaatame seda kohe.

717
00:55:02,040 --> 00:55:05,470
Võite tegelikult teha rekursiivselt üsna kergesti.

718
00:55:05,470 --> 00:55:08,080
Kas me tahame seda teha?

719
00:55:08,080 --> 00:55:10,980
Jah, mida me teeme.

720
00:55:10,980 --> 00:55:16,790
>> Vaatame seda rekursiivselt.

721
00:55:16,790 --> 00:55:24,070
Esiteks, milline on meie tugipunkt saab olema?

722
00:55:24,070 --> 00:55:29,140
Peaaegu alati meie tugipunkt, kuid tegelikult on see omamoodi keeruline.

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

724
00:55:34,370 --> 00:55:37,550
Ma arvan, et me lihtsalt läheb tagasi false.

725
00:55:37,550 --> 00:55:40,460
See erineb oma puu on null.

726
00:55:40,460 --> 00:55:44,510
See on kursor oma juur osuti on null

727
00:55:44,510 --> 00:55:48,360
mis tähendab, et teie juure osuti ei eksisteeri.

728
00:55:48,360 --> 00:55:52,390
Nii et siin all, kui ma

729
00:55:52,390 --> 00:55:55,760
sõlme * - olgem lihtsalt uuesti seda.

730
00:55:55,760 --> 00:55:58,960
Sõlme * root = NULL,

731
00:55:58,960 --> 00:56:00,730
ja siis ma lähen helistada sisestada tehes midagi,

732
00:56:00,730 --> 00:56:04,540
paigalda 4 sisse ja juur.

733
00:56:04,540 --> 00:56:06,560
Nii ja juur, kui juur on sõlm *

734
00:56:06,560 --> 00:56:11,170
siis & root saab olema sõlme **.

735
00:56:11,170 --> 00:56:15,120
See kehtib. Sel juhul puu, siin üleval,

736
00:56:15,120 --> 00:56:20,120
puu ei ole null - või sisesta.

737
00:56:20,120 --> 00:56:24,630
Siin. Puu ei ole null, * puu on null, mis on hea

738
00:56:24,630 --> 00:56:26,680
sest kui * puu on null, siis ma saan manipuleerida seda

739
00:56:26,680 --> 00:56:29,210
et nüüd juhtida sellele, mida ma tahan osutada.

740
00:56:29,210 --> 00:56:34,750
Aga kui puu on null, mis tähendab, et ma lihtsalt tulin siia ja ütles null.

741
00:56:34,750 --> 00:56:42,710
See ei ole loogiline. Ma ei saa midagi teha sellega.

742
00:56:42,710 --> 00:56:45,540
Kui puu on null, tagastab false.

743
00:56:45,540 --> 00:56:48,220
Nii et ma põhimõtteliselt juba öelnud, mida meie tõeline tugipunkt on.

744
00:56:48,220 --> 00:56:50,580
Ja mis see saab olema?

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

746
00:56:55,030 --> 00:57:00,000
[Bowden] Jah. Nii et kui (* puu == NULL).

747
00:57:00,000 --> 00:57:04,520
See on seotud nii siia

748
00:57:04,520 --> 00:57:09,640
kus kui mu punane osuti on pointer Olen keskendunud,

749
00:57:09,640 --> 00:57:12,960
nii nagu ma olen keskendunud sellele pointer, nüüd olen keskendunud sellele kursor.

750
00:57:12,960 --> 00:57:15,150
Nüüd ma olen keskendunud sellele kursor.

751
00:57:15,150 --> 00:57:18,160
Nii et kui mu punane osuti, mis on minu sõlme **

752
00:57:18,160 --> 00:57:22,880
on kunagi - kui *, minu punane osuti, on kunagi null,

753
00:57:22,880 --> 00:57:28,470
see tähendab, et ma olen juhul, kui ma keskendudes osuti, mis näitab -

754
00:57:28,470 --> 00:57:32,530
see on osuti, mis kuulub lehed.

755
00:57:32,530 --> 00:57:41,090
Ma tahan muuta see pointer osutada minu uus sõlm.

756
00:57:41,090 --> 00:57:45,230
Tule tagasi siia.

757
00:57:45,230 --> 00:57:56,490
Minu newnode oleks lihtsalt sõlme * n = build_node (väärtus)

758
00:57:56,490 --> 00:58:07,300
siis n, kui n = NULL, tagastab false.

759
00:58:07,300 --> 00:58:12,600
Else tahame muuta seda, mis kursor parasjagu osutades

760
00:58:12,600 --> 00:58:17,830
et nüüd näidata meie vastvalminud sõlme.

761
00:58:17,830 --> 00:58:20,280
Me ei saa tegelikult teha siit.

762
00:58:20,280 --> 00:58:30,660
Selle asemel, et öelda n, ütleme * puu = kui * puu.

763
00:58:30,660 --> 00:58:35,450
Igaühel aru? See käsitledes vihjeid suunanäitajaks,

764
00:58:35,450 --> 00:58:40,750
saame muuta null viiteid osutavad asju, mida me tahame, et nad osutavad.

765
00:58:40,750 --> 00:58:42,820
See on meie tugipunkt.

766
00:58:42,820 --> 00:58:45,740
>> Nüüd on meie kordumise, või meie rekursioon,

767
00:58:45,740 --> 00:58:51,430
saab olema väga sarnased kõigi teiste recursions oleme teinud.

768
00:58:51,430 --> 00:58:55,830
Me läheme soovite lisada väärtust,

769
00:58:55,830 --> 00:58:59,040
ja nüüd ma lähen kasutada kolmekomponentsete uuesti, kuid mida on meie seisund saab olema?

770
00:58:59,040 --> 00:59:05,180
Mis on see keda me otsime, et otsustada, kas me tahame minna vasakule või paremale?

771
00:59:05,180 --> 00:59:07,760
Teeme seda eraldi samme.

772
00:59:07,760 --> 00:59:18,850
Kui (väärtus <) mida?

773
00:59:18,850 --> 00:59:23,200
[Student] puu väärtus?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Seega pidage meeles, et ma olen praegu -

775
00:59:27,490 --> 00:59:31,260
[Õpilased, arusaamatult]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Jah, nii siin, ütleme, et see roheline nool

777
00:59:34,140 --> 00:59:39,050
on näide sellest, mida puu praegu on, on viit see pointer.

778
00:59:39,050 --> 00:59:46,610
See tähendab, ma olen kursor pointer 3.

779
00:59:46,610 --> 00:59:48,800
Dereference kaks korda kõlab hästi.

780
00:59:48,800 --> 00:59:51,010
Mida ma - kuidas ma seda teen?

781
00:59:51,010 --> 00:59:53,210
[Student] dereference kord ja tehke nool, et kuidas?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Nii (* puu) on dereference kord, -> väärtus

783
00:59:58,420 --> 01:00:05,960
läheb mulle väärtus sõlme, et ma kaudselt osutavad.

784
01:00:05,960 --> 01:00:11,980
Ma võin ka kirjutada ** tree.value kui soovite, et.

785
01:00:11,980 --> 01:00:18,490
Kas töötab.

786
01:00:18,490 --> 01:00:26,190
Kui see on nii, siis ma tahan helistada sisestada väärtusega.

787
01:00:26,190 --> 01:00:32,590
Ja mis on minu uuendatud sõlme ** läheb?

788
01:00:32,590 --> 01:00:39,440
Ma tahan minna vasakule, nii ** tree.left saab olema minu vasakul.

789
01:00:39,440 --> 01:00:41,900
Ja ma tahan kursorit, et asi

790
01:00:41,900 --> 01:00:44,930
nii et kui vasakule jõuab on null pointer,

791
01:00:44,930 --> 01:00:48,360
Ma ei muuda see käsk minu uus sõlm.

792
01:00:48,360 --> 01:00:51,460
>> Ja teisel juhul võib olla väga sarnane.

793
01:00:51,460 --> 01:00:55,600
Olgem tegelikult teha, et minu kolmekomponentsete kohe.

794
01:00:55,600 --> 01:01:04,480
Sisesta väärtus kui väärtus <(** puu). Väärtus.

795
01:01:04,480 --> 01:01:11,040
Siis me tahame uuendada meie ** vasakule,

796
01:01:11,040 --> 01:01:17,030
muidu me tahame uuendada meie ** paremale.

797
01:01:17,030 --> 01:01:22,540
[Student] Kas see saame kursor pointer?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Pea meeles, et - ** tree.right on sõlm täht.

799
01:01:30,940 --> 01:01:35,040
[Student, arusaamatult] >> Jah.

800
01:01:35,040 --> 01:01:41,140
** Tree.right on nagu see pointer või midagi.

801
01:01:41,140 --> 01:01:45,140
Nii võttes kursorit, et see annab mulle, mida ma tahan

802
01:01:45,140 --> 01:01:50,090
on kursor, et kutt.

803
01:01:50,090 --> 01:01:54,260
[Student] Kas läheme jälle, miks me kasutame kahe viiteid?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Jah. Nii et - ei, saad, ja et lahendus enne

805
01:01:58,220 --> 01:02:04,540
oli viis seda teha ilma teeb kahte suunanäitajaks.

806
01:02:04,540 --> 01:02:08,740
Sa pead aru saama kahe suunanäitajaks,

807
01:02:08,740 --> 01:02:11,660
ja see on puhtam lahendus.

808
01:02:11,660 --> 01:02:16,090
Samuti märkate, et mis juhtub, kui minu puu -

809
01:02:16,090 --> 01:02:24,480
Mis juhtub, kui juur oli null? Mis juhtub, kui ma seda juhul siin?

810
01:02:24,480 --> 01:02:30,540
Nii sõlme * root = NULL, paigalda 4 sisse ja juur.

811
01:02:30,540 --> 01:02:35,110
Mis on root saab olema pärast seda?

812
01:02:35,110 --> 01:02:37,470
[Student, arusaamatult] >> Jah.

813
01:02:37,470 --> 01:02:41,710
Juur väärtus saab olema 4.

814
01:02:41,710 --> 01:02:45,510
Juur vasakule saab olema null, juure õiguse saab olema null.

815
01:02:45,510 --> 01:02:49,490
Juhul kui me ei liigu juure aadressi järgi

816
01:02:49,490 --> 01:02:52,490
me ei saa muuta root.

817
01:02:52,490 --> 01:02:56,020
Juhul kui puu - kui juur oli null,

818
01:02:56,020 --> 01:02:58,410
me lihtsalt pidin tagasi false. Ei ole midagi mida me teha saame.

819
01:02:58,410 --> 01:03:01,520
Me ei saa sisestada sõlme tühja puu.

820
01:03:01,520 --> 01:03:06,810
Aga nüüd saame, me lihtsalt tühi puu ühtseks sõlme puu.

821
01:03:06,810 --> 01:03:13,400
Mis on tavaliselt oodatava nii, et see peaks töötama.

822
01:03:13,400 --> 01:03:21,610
>> Lisaks sellele on tunduvalt lühem kui

823
01:03:21,610 --> 01:03:26,240
Samuti jälgida, vanem, ja nii sa itereerima alla kogu tee.

824
01:03:26,240 --> 01:03:30,140
Nüüd on mul mu ema, ja ma lihtsalt pean oma vanema õigus kursor iganes.

825
01:03:30,140 --> 01:03:35,640
Selle asemel, kui me tegime seda korduvalt, see oleks sama idee samas silmus.

826
01:03:35,640 --> 01:03:38,100
Aga selle asemel, et tegeleda minu vanem pointer,

827
01:03:38,100 --> 01:03:40,600
selle asemel minu praegune pointer oleks asi

828
01:03:40,600 --> 01:03:43,790
et ma otseselt muuta punkti minu uus sõlm.

829
01:03:43,790 --> 01:03:46,090
Ma ei pea tegelema kas see on suunaga paremale.

830
01:03:46,090 --> 01:03:48,810
Ma ei pea tegelema kas see on suunatud paremale.

831
01:03:48,810 --> 01:04:00,860
See on lihtsalt mida iganes see pointer on, ma lähen, et seada see käsk minu uus sõlm.

832
01:04:00,860 --> 01:04:05,740
Igaüks aru, kuidas see töötab?

833
01:04:05,740 --> 01:04:09,460
Kui ei siis miks me tahame teha seda nii,

834
01:04:09,460 --> 01:04:14,920
aga vähemalt, et see töötab nagu lahendus?

835
01:04:14,920 --> 01:04:17,110
[Student] Kui me tagasi true?

836
01:04:17,110 --> 01:04:21,550
[Bowden] See on ilmselt siin.

837
01:04:21,550 --> 01:04:26,690
Kui me õigesti sisestada see, tagastab tõsi.

838
01:04:26,690 --> 01:04:32,010
Else, siia alla läheme soovivad naasta iganes sisestada tulu.

839
01:04:32,010 --> 01:04:35,950
>> Ja mis on eriline selle rekursiivne funktsioon?

840
01:04:35,950 --> 01:04:43,010
See on saba rekursiivne, nii kaua, kui oleme kompileerida mõned optimeerimine,

841
01:04:43,010 --> 01:04:48,060
see on arusaadav, et ja te ei saa kunagi korstnat ülevoolu sellest,

842
01:04:48,060 --> 01:04:53,230
isegi kui meie puu on kõrgus 10.000 või 10 miljonit.

843
01:04:53,230 --> 01:04:55,630
[Student, arusaamatult]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Ma arvan, et see on kriips - või mida optimeerimine tasemel

845
01:05:00,310 --> 01:05:03,820
on vaja saba rekursioon olla tunnustatud.

846
01:05:03,820 --> 01:05:09,350
Ma arvan, et ta tunnustab - GCC ja rõkkama

847
01:05:09,350 --> 01:05:12,610
Samuti on erinev tähendus nende optimeerimise tase.

848
01:05:12,610 --> 01:05:17,870
Ma tahan öelda, et see DashO 2 kindlasti, et see tunneb saba rekursioon.

849
01:05:17,870 --> 01:05:27,880
Aga me - võid ehitada nagu Fibonocci näiteks või midagi.

850
01:05:27,880 --> 01:05:30,030
See ei ole lihtne test selle, sest see on raske ehitada

851
01:05:30,030 --> 01:05:32,600
kahendpuu, et on nii suur.

852
01:05:32,600 --> 01:05:37,140
Aga jah, ma arvan, et see DashO 2, et

853
01:05:37,140 --> 01:05:40,580
kui sa kompileerida koos DashO 2, siis otsima saba rekursioon

854
01:05:40,580 --> 01:05:54,030
ja optimeerida selle välja.

855
01:05:54,030 --> 01:05:58,190
Lähme tagasi - sisestage on sõna otseses mõttes viimane asi, mida ta vajab.

856
01:05:58,190 --> 01:06:04,900
Lähme tagasi sisesta siia

857
01:06:04,900 --> 01:06:07,840
kus me ei kavatse teha sama mõte.

858
01:06:07,840 --> 01:06:14,340
Seda saad veel viga, et ei olda võimelised täielikult hakkama

859
01:06:14,340 --> 01:06:17,940
kui juur ise on null, või viimase kirje on null,

860
01:06:17,940 --> 01:06:20,060
kuid selle asemel tegelevad vanem pointer,

861
01:06:20,060 --> 01:06:27,430
olgem rakendada sama loogikat hoides vihjeid suunanäitajaks.

862
01:06:27,430 --> 01:06:35,580
Kui siin me hoiame sõlme ** ub,

863
01:06:35,580 --> 01:06:37,860
ja me ei vaja jälgida õige enam

864
01:06:37,860 --> 01:06:47,190
kuid sõlme ** viim = & puu.

865
01:06:47,190 --> 01:06:54,800
Ja nüüd meie ajal ahela saab olema samas * viim ei võrdu null.

866
01:06:54,800 --> 01:07:00,270
Ei ole vaja jälgida vanemad enam.

867
01:07:00,270 --> 01:07:04,180
Ei ole vaja jälgida vasakule ja paremale.

868
01:07:04,180 --> 01:07:10,190
Ja ma nimetan seda temp, sest me juba kasutate temp.

869
01:07:10,190 --> 01:07:17,200
Okei. Nii et kui (väärtus> * temp),

870
01:07:17,200 --> 01:07:24,010
siis & (* temp) -> õigus

871
01:07:24,010 --> 01:07:29,250
muidu temp = & (* temp) -> vasakule.

872
01:07:29,250 --> 01:07:32,730
Ja nüüd, sel hetkel, pärast seda kui silmus,

873
01:07:32,730 --> 01:07:36,380
Ma ainult seda teha, sest võibolla on lihtsam mõelda iteratiivselt kui rekursiivselt,

874
01:07:36,380 --> 01:07:39,010
kuid pärast seda, kui silmus,

875
01:07:39,010 --> 01:07:43,820
* Temp on pointer me tahame muuta.

876
01:07:43,820 --> 01:07:48,960
>> Enne oli meil vanem, ja me tahtsime muuta kummagi vanema vasakule või vanem õigus,

877
01:07:48,960 --> 01:07:51,310
kuid kui me tahame muuta vanema õigus,

878
01:07:51,310 --> 01:07:54,550
siis * temp on vanem õigus, ja me ei muuda seda otse.

879
01:07:54,550 --> 01:08:05,860
Nii et siin all, me saame teha * temp = newnode, ja ongi kõik.

880
01:08:05,860 --> 01:08:09,540
Nii teate, kõik me tegime seda oli võtta rida koodi.

881
01:08:09,540 --> 01:08:14,770
Et jälgida vanem kõik, mis on täiendavaid jõupingutusi.

882
01:08:14,770 --> 01:08:18,689
Siin, kui me lihtsalt jälgida kursor pointer,

883
01:08:18,689 --> 01:08:22,990
ja isegi kui me tahtsime saada lahti kõik need looksulg nüüd,

884
01:08:22,990 --> 01:08:27,170
Tee vaata lühem.

885
01:08:27,170 --> 01:08:32,529
See on praegu täpselt sama lahendus,

886
01:08:32,529 --> 01:08:38,210
kuid vähem rida koodi.

887
01:08:38,210 --> 01:08:41,229
Kui hakkate tunnustades seda kehtiv lahendus,

888
01:08:41,229 --> 01:08:43,529
see on ka lihtsam põhjus umbes kui näeb, okei,

889
01:08:43,529 --> 01:08:45,779
miks ma pean seda lippu int eks?

890
01:08:45,779 --> 01:08:49,290
Mida see tähendab? Oh, see on see tähendaks, et

891
01:08:49,290 --> 01:08:51,370
iga kord ma lähen paremale, mul on vaja seada see,

892
01:08:51,370 --> 01:08:53,819
muidu kui ma lähen jäänud mul vaja seada nulli.

893
01:08:53,819 --> 01:09:04,060
Siin ma ei pea põhjus sellest, see on lihtsalt lihtsam mõelda.

894
01:09:04,060 --> 01:09:06,710
Küsimused?

895
01:09:06,710 --> 01:09:16,290
[Student, arusaamatult] >> Jah.

896
01:09:16,290 --> 01:09:23,359
Okei, nii et viimase natuke -

897
01:09:23,359 --> 01:09:28,080
Ma arvan, et üks kiire ja lihtne funktsioon saame teha, on,

898
01:09:28,080 --> 01:09:34,910
let's - koos, ma arvan, püüa kirjutada sisaldab funktsiooni

899
01:09:34,910 --> 01:09:38,899
mis ei hooli, kas see on Kahendotsingupuu.

900
01:09:38,899 --> 01:09:43,770
See sisaldab funktsiooni peaks tagasi tõsi

901
01:09:43,770 --> 01:09:58,330
kui kuskil sellises üldises kahendpuu on väärtus me otsime.

902
01:09:58,330 --> 01:10:02,520
So let esimene seda rekursiivselt ja siis me teeme seda korduvalt.

903
01:10:02,520 --> 01:10:07,300
Me ei saa tegelikult lihtsalt teeme seda koos, sest see saab olema tõesti lühike.

904
01:10:07,300 --> 01:10:11,510
>> Mis on minu tugipunkt saab olema?

905
01:10:11,510 --> 01:10:13,890
[Student, arusaamatult]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Nii et kui (puu == NULL), siis mida?

907
01:10:18,230 --> 01:10:22,740
[Student] Tagasi vale.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, noh, ma ei vaja muud.

909
01:10:26,160 --> 01:10:30,250
Kui oli minu teisi tugipunkti.

910
01:10:30,250 --> 01:10:32,450
[Student] Tree väärtus? >> Jah.

911
01:10:32,450 --> 01:10:36,430
Nii et kui (puu-> väärtus == väärtus.

912
01:10:36,430 --> 01:10:39,920
Teade me oleme tagasi sõlme *, mitte sõlme ** s?

913
01:10:39,920 --> 01:10:42,990
Sisaldab kunagi vaja kasutada sõlme **

914
01:10:42,990 --> 01:10:45,480
kuna me ei muuda suunanäitajaks.

915
01:10:45,480 --> 01:10:50,540
Me lihtsalt liiklevad neid.

916
01:10:50,540 --> 01:10:53,830
Kui see juhtub, siis me tahame naasta tõsi.

917
01:10:53,830 --> 01:10:58,270
Else tahame läbida lapsed.

918
01:10:58,270 --> 01:11:02,620
Nii et me ei saa arutleda selle üle, kas kõik vasakule on vähem

919
01:11:02,620 --> 01:11:05,390
ja kõike paremal on suurem.

920
01:11:05,390 --> 01:11:09,590
Mis on meie seisund saab olema siin - või Mida me nüüd teeme?

921
01:11:09,590 --> 01:11:11,840
[Student, arusaamatult] >> Jah.

922
01:11:11,840 --> 01:11:17,400
Tagasi sisaldab (väärtus, puu-> vasak)

923
01:11:17,400 --> 01:11:26,860
või sisaldab (väärtus, puu-> paremal). Ja ongi kõik.

924
01:11:26,860 --> 01:11:29,080
Ja märkate seal on mõned lühis hindamine,

925
01:11:29,080 --> 01:11:32,520
kus kui me juhtub, et leida väärtus vasak puus,

926
01:11:32,520 --> 01:11:36,820
me kunagi vaja vaadata õige puu.

927
01:11:36,820 --> 01:11:40,430
See on kogu funktsiooni.

928
01:11:40,430 --> 01:11:43,690
Nüüd teeme seda korduvalt,

929
01:11:43,690 --> 01:11:48,060
mis saab olema vähem kena.

930
01:11:48,060 --> 01:11:54,750
Võtame tavalise algust sõlme * viim = puu.

931
01:11:54,750 --> 01:12:03,250
Kuigi (viim! = NULL).

932
01:12:03,250 --> 01:12:08,600
Kiiresti näeme probleemi.

933
01:12:08,600 --> 01:12:12,250
Kui viim - siin, kui me kunagi murda läbi selle,

934
01:12:12,250 --> 01:12:16,020
siis me oleme otsa asju vaadata, nii tagastab false.

935
01:12:16,020 --> 01:12:24,810
Kui (viim-> väärtus == väärtus) tagasi true.

936
01:12:24,810 --> 01:12:32,910
Nüüd oleme kohas -

937
01:12:32,910 --> 01:12:36,250
me ei tea, kas me tahame minna vasakule või paremale.

938
01:12:36,250 --> 01:12:44,590
Nii suvaliselt, lihtsalt vasakule.

939
01:12:44,590 --> 01:12:47,910
Ma olen ilmselt tekib küsimus, kus ma olen täiesti loobunud kõigest -

940
01:12:47,910 --> 01:12:50,760
Ma ainult kunagi kontrollida vasakul puu.

941
01:12:50,760 --> 01:12:56,050
Ma ei ole kunagi näha midagi, mis on õige laps midagi.

942
01:12:56,050 --> 01:13:00,910
Kuidas seda parandada?

943
01:13:00,910 --> 01:13:05,260
[Student] Sa pead hoidma silma peal vasakule ja paremale pinu.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Jah. Nii et teeme seda

945
01:13:13,710 --> 01:13:32,360
struct nimekirja, sõlme * n ja siis sõlm ** edasi?

946
01:13:32,360 --> 01:13:40,240
Ma arvan, et toimib hästi.

947
01:13:40,240 --> 01:13:45,940
Tahame minna üle vasaku, või let's - siin.

948
01:13:45,940 --> 01:13:54,350
Struct list =, siis saad alustada

949
01:13:54,350 --> 01:13:58,170
läbi see struct nimekirja.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Nii et see saab olema meie seotud nimekirja

951
01:14:04,040 --> 01:14:08,430
kohta subtrees et oleme hüpatakse üle.

952
01:14:08,430 --> 01:14:13,800
Me Traverse jäänud nüüd,

953
01:14:13,800 --> 01:14:17,870
kuid kuna me paratamatult vaja tulla tagasi paremale,

954
01:14:17,870 --> 01:14:26,140
Me läheme hoida paremale küljele sees meie struct nimekirja.

955
01:14:26,140 --> 01:14:32,620
Siis me peame new_list või struct,

956
01:14:32,620 --> 01:14:41,080
struct nimekiri *, new_list = malloc (sizeof (nimekiri)).

957
01:14:41,080 --> 01:14:44,920
Ma lähen ignoreerida Tõrkekontroll, kuid siis tuleb vaadata, et näha, kas see on null.

958
01:14:44,920 --> 01:14:50,540
New_list sõlme see saab osutada -

959
01:14:50,540 --> 01:14:56,890
oh, sellepärast ma tahtsin seda siin üleval. See saab viidata teise struct nimekirja.

960
01:14:56,890 --> 01:15:02,380
See on lihtsalt, kuidas seotud nimekirju töö.

961
01:15:02,380 --> 01:15:04,810
See on sama, mis int seotud nimekirja

962
01:15:04,810 --> 01:15:06,960
välja arvatud me lihtsalt asendades int koos sõlme *.

963
01:15:06,960 --> 01:15:11,040
See on täpselt sama.

964
01:15:11,040 --> 01:15:15,100
Nii new_list, väärtus meie new_list sõlme,

965
01:15:15,100 --> 01:15:19,120
saab olema viim-> õigust.

966
01:15:19,120 --> 01:15:24,280
Väärtus meie new_list-> next saab olema meie esialgses nimekirjas,

967
01:15:24,280 --> 01:15:30,760
ja siis me läheme uuendama meie nimekirjas osutada new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nüüd tuleb mingi viis tõmmates asju,

969
01:15:33,650 --> 01:15:37,020
nagu me oleme liiklevad kogu vasak alampuu.

970
01:15:37,020 --> 01:15:40,480
Nüüd tuleb tõmmata asju välja,

971
01:15:40,480 --> 01:15:43,850
nagu viim on null, me ei taha lihtsalt tagasi false.

972
01:15:43,850 --> 01:15:50,370
Me tahame nüüd tõmba väljaspool meie uus nimekiri.

973
01:15:50,370 --> 01:15:53,690
Mugav viis seda teha - noh, tegelikult, seal on mitmeid viise seda teha.

974
01:15:53,690 --> 01:15:56,680
Igaüks on ettepanekuid?

975
01:15:56,680 --> 01:15:58,790
Kui ma peaks seda tegema või kuidas ma peaks seda tegema?

976
01:15:58,790 --> 01:16:08,010
Meil on ainult paar minutit, kuid mingeid ettepanekuid?

977
01:16:08,010 --> 01:16:14,750
Selle asemel, et - üks võimalus, mitte meie tingimus on samas,

978
01:16:14,750 --> 01:16:17,090
mida me praegu vaadates ei ole null,

979
01:16:17,090 --> 01:16:22,340
selle asemel me kavatseme jätkata minna kuni meie nimekirja ise on null.

980
01:16:22,340 --> 01:16:25,680
Nii et kui meie nimekirjas jõuab on null,

981
01:16:25,680 --> 01:16:30,680
siis oleme otsa asju otsima, et otsida üle.

982
01:16:30,680 --> 01:16:39,860
Aga see tähendab, et esimene asi, mida meie nimekiri on lihtsalt saab olema esimese sõlme.

983
01:16:39,860 --> 01:16:49,730
Kõige esimene asi on - me ei pea enam näha.

984
01:16:49,730 --> 01:16:58,710
Nii list-> n on meie puu.

985
01:16:58,710 --> 01:17:02,860
list-> next saab olema null.

986
01:17:02,860 --> 01:17:07,580
Ja nüüd samas nimekirjas ei võrdu null.

987
01:17:07,580 --> 01:17:11,610
Cur läheb tõmmata midagi meie nimekirjast.

988
01:17:11,610 --> 01:17:13,500
Nii viim läheb võrdne list-> n.

989
01:17:13,500 --> 01:17:20,850
Ja siis nimekiri läheb võrdne list-> n, või nimekiri-> next.

990
01:17:20,850 --> 01:17:23,480
Nii et kui viim väärtus on võrdne väärtus.

991
01:17:23,480 --> 01:17:28,790
Nüüd saate lisada nii meie õigus osuti ja meie vasak pointer

992
01:17:28,790 --> 01:17:32,900
nii kaua, kui nad ei ole null.

993
01:17:32,900 --> 01:17:36,390
Alla siin, ma arvan, et me oleks pidanud tegema, et esimene koht.

994
01:17:36,390 --> 01:17:44,080
Kui (viim-> right! = NULL)

995
01:17:44,080 --> 01:17:56,380
siis me lisada, et sõlm meie nimekirjas.

996
01:17:56,380 --> 01:17:59,290
Kui (viim-> vasak), see on natuke lisatööd, kuid kõik on korras.

997
01:17:59,290 --> 01:18:02,690
Kui (viim-> vasakule! = NULL),

998
01:18:02,690 --> 01:18:14,310
ja me kavatseme lisada vasakul meie seotud nimekirja,

999
01:18:14,310 --> 01:18:19,700
ja see peaks olema see.

1000
01:18:19,700 --> 01:18:22,670
Me itereerima - nii kaua, kui meil on midagi meie nimekirja,

1001
01:18:22,670 --> 01:18:26,640
meil on veel üks sõlm vaadata.

1002
01:18:26,640 --> 01:18:28,920
Nii et vaatame, mis sõlme,

1003
01:18:28,920 --> 01:18:31,390
meil edendada meie nimekirjas järgmise juurde.

1004
01:18:31,390 --> 01:18:34,060
Kui see sõlm on väärtus me otsime, saame tagasi true.

1005
01:18:34,060 --> 01:18:37,640
Else sisestada nii meie vasak ja parem subtrees,

1006
01:18:37,640 --> 01:18:40,510
nii kaua, kui nad ei ole null, meie nimekiri

1007
01:18:40,510 --> 01:18:43,120
nii et me paratamatult minna nende üle.

1008
01:18:43,120 --> 01:18:45,160
Nii et kui nad ei ole null,

1009
01:18:45,160 --> 01:18:47,950
kui meie juurtest osuti osutas kaks asja,

1010
01:18:47,950 --> 01:18:51,670
siis meil esimest korda tõmbas midagi välja nii meie nimekirjas jõuab on null.

1011
01:18:51,670 --> 01:18:56,890
Ja siis me paneme kaks asja tagasi, nii et nüüd meie nimekirjas on suurus 2.

1012
01:18:56,890 --> 01:19:00,030
Siis läheme silmus varundada ja me lihtsalt läheb vedama,

1013
01:19:00,030 --> 01:19:04,250
oletame, vasak osuti meie juurest sõlme.

1014
01:19:04,250 --> 01:19:07,730
Ja see muudkui juhtub; me lõpuks silmuspõletamise üle kõike.

1015
01:19:07,730 --> 01:19:11,280
>> Pange tähele, et see oli oluliselt keerulisem

1016
01:19:11,280 --> 01:19:14,160
aastal rekursiivne lahendus.

1017
01:19:14,160 --> 01:19:17,260
Ja ma olen öelnud mitu korda

1018
01:19:17,260 --> 01:19:25,120
et rekursiivne lahendus on tavaliselt palju ühist iteratiivne lahendus.

1019
01:19:25,120 --> 01:19:30,820
Siin see on täpselt, mida rekursiivne lahendus teeb.

1020
01:19:30,820 --> 01:19:36,740
Ainus muudatus on see, et selle asemel, et vaikimisi kasutades korstna programmi stack,

1021
01:19:36,740 --> 01:19:40,840
nagu oma viis jälgida, mida sõlmed ikka on vaja külastada,

1022
01:19:40,840 --> 01:19:45,430
nüüd sa pead selgesõnaliselt kasutada seotud nimekirja.

1023
01:19:45,430 --> 01:19:49,070
Mõlemal juhul te jälgida, mida sõlm tuleb veel külastatud.

1024
01:19:49,070 --> 01:19:51,790
Kui rekursiivne juhul on siis lihtsam, sest korstnat

1025
01:19:51,790 --> 01:19:57,100
rakendatakse teile kui programmi pinu.

1026
01:19:57,100 --> 01:19:59,550
Pange tähele, et see on seotud nimekirja, siis on pinu.

1027
01:19:59,550 --> 01:20:01,580
Mida me lihtsalt panna virna

1028
01:20:01,580 --> 01:20:09,960
on kohe, mida me ei kavatse peatähelepanu korstnat külastada kõrval.

1029
01:20:09,960 --> 01:20:14,380
Meil on aeg otsas, kuid mingeid küsimusi?

1030
01:20:14,380 --> 01:20:23,530
[Student, arusaamatult]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Jah. Nii et kui meil on seotud nimekirja,

1032
01:20:27,790 --> 01:20:30,150
Praegune läheb käsk see kutt,

1033
01:20:30,150 --> 01:20:34,690
ja nüüd me lihtsalt edendades seotud nimekirja keskenduda sellele mehele.

1034
01:20:34,690 --> 01:20:44,200
Me liiklevad üle lingitud nimekiri, et liin.

1035
01:20:44,200 --> 01:20:51,200
Ja siis ma arvan, et me peaks vabastama meie seotud nimekirja ja värki

1036
01:20:51,200 --> 01:20:53,880
kord naasid õige või vale, peame

1037
01:20:53,880 --> 01:20:57,360
itereerime meie lingitud nimekiri ja alati siin, ma arvan,

1038
01:20:57,360 --> 01:21:03,900
kui me viim õigus ei võrdu, lisab ta, et nüüd me tahame vabastada

1039
01:21:03,900 --> 01:21:09,600
viim sest, noh, me tegime täiesti unustada nimekirja? Jah.

1040
01:21:09,600 --> 01:21:12,880
Nii see on, mida me tahame teha siin.

1041
01:21:12,880 --> 01:21:16,730
Kus pointer?

1042
01:21:16,730 --> 01:21:23,320
Val oli siis - me tahame struct nimekiri * 10 võrdub nimekirja kõrval.

1043
01:21:23,320 --> 01:21:29,240
Tasuta nimekiri, loend = temp.

1044
01:21:29,240 --> 01:21:32,820
Ja juhul, kui me tagasi true, me peame itereerima

1045
01:21:32,820 --> 01:21:37,050
üle ülejäänud meie seotud nimekirja vabastades asju.

1046
01:21:37,050 --> 01:21:39,700
Tore asi rekursiivne lahendus on vabastamist asjad

1047
01:21:39,700 --> 01:21:44,930
tähendab lihtsalt popping factorings maha korstnat, mis juhtub teile.

1048
01:21:44,930 --> 01:21:50,720
Nii oleme läinud midagi, mis on nagu 3 rida raskesti arvan, umbes kood

1049
01:21:50,720 --> 01:21:57,520
midagi, mis on oluliselt palju rohkem hard-to-arvan-umbes rida koodi.

1050
01:21:57,520 --> 01:22:00,620
Kas veel küsimusi?

1051
01:22:00,620 --> 01:22:08,760
Hea küll. Oleme hea. Nägemist!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]