1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Seksyon 7: Higit pang Maginhawa]

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

3
00:00:05,090 --> 00:00:07,930
[Ito ay CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Ayos lang. Kaya tulad ng sinabi ko sa aking email,

5
00:00:10,110 --> 00:00:14,060
ito ay isang binary-puno-intensive na seksyon.

6
00:00:14,060 --> 00:00:16,820
Ngunit may mga hindi na maraming mga katanungan.

7
00:00:16,820 --> 00:00:18,920
Kaya kami ay pagpunta sa subukan at gumuhit ang bawat tanong

8
00:00:18,920 --> 00:00:25,430
at pumunta sa masakit detalye ng lahat ng mga pinakamahusay na paraan ng paggawa ng mga bagay.

9
00:00:25,430 --> 00:00:31,200
Kaya sa simula, pumunta kami sa pamamagitan ng mga guhit sample ng binary na puno at mga bagay-bagay.

10
00:00:31,200 --> 00:00:35,970
Kaya dito, "Tandaan na ang isang binary tree node katulad sa mga naka-link na listahan,

11
00:00:35,970 --> 00:00:38,150
maliban sa halip ng isang pointer dalawa: isa para sa 'bata' sa kaliwa

12
00:00:38,150 --> 00:00:41,950
at isa para sa tamang 'anak'. "

13
00:00:41,950 --> 00:00:45,630
Kaya isang binary puno ay tulad ng isang naka-link na listahan,

14
00:00:45,630 --> 00:00:47,910
maliban sa struct ay pagpunta sa dalawang payo.

15
00:00:47,910 --> 00:00:51,390
Mayroong trinary mga puno, na tatlong payo,

16
00:00:51,390 --> 00:00:56,540
may N-ary puno, na lamang ay may generic na pointer

17
00:00:56,540 --> 00:01:00,320
mong mag-malloc sa malaki sapat na upang magkaroon ng

18
00:01:00,320 --> 00:01:04,840
sapat na payo sa lahat ng posibleng mga bata.

19
00:01:04,840 --> 00:01:08,200
Kaya binary puno ang mangyayari sa isang pare-pareho ang bilang ng dalawang.

20
00:01:08,200 --> 00:01:11,260
Kung gusto mo, maaari kang magbigay ng isang naka-link na listahan bilang isang unary puno,

21
00:01:11,260 --> 00:01:15,360
ngunit hindi sa tingin ko tawag ito ng sinuman na.

22
00:01:15,360 --> 00:01:18,060
"Gumuhit ng isang kahon-at-arrow diagram ng isang binary puno node

23
00:01:18,060 --> 00:01:24,110
naglalaman Nate ng paboritong numero, 7, kung saan ang bawat bata pointer ay null. "

24
00:01:24,110 --> 00:01:27,780
Kaya iPad mode.

25
00:01:27,780 --> 00:01:30,280
>> Ito ay medyo direkta.

26
00:01:30,280 --> 00:01:36,150
Lamang namin ay pagpunta sa magkaroon ng isang node, makikita ko gumuhit ang mga ito bilang isang parisukat.

27
00:01:36,150 --> 00:01:38,730
At makikita kong iguhit ang mga halaga sa dito.

28
00:01:38,730 --> 00:01:41,090
Kaya ang halaga ay pumunta sa dito,

29
00:01:41,090 --> 00:01:44,770
at pagkatapos ay down na dito ipapakita namin sa kaliwang pointer sa kaliwa at sa kanan pointer sa kanan.

30
00:01:44,770 --> 00:01:50,430
At ito ay napaka upang convention na tumawag ito kaliwa at kanang, ang mga pangalan ng pointer.

31
00:01:50,430 --> 00:01:52,460
Pareho sa mga ito ay pagpunta sa maging null.

32
00:01:52,460 --> 00:01:57,870
Na lamang null, at iyon ay null lamang.

33
00:01:57,870 --> 00:02:03,630
Okay. -Back Kaya dito.

34
00:02:03,630 --> 00:02:05,700
"Sa isang naka-link na listahan, lamang namin ay upang mag-imbak ng pointer

35
00:02:05,700 --> 00:02:09,639
sa unang node sa listahan upang matandaan ang buong-link listahan, o ang buong listahan.

36
00:02:09,639 --> 00:02:11,650
Gayundin, na may mga puno, lamang namin upang mag-imbak ng pointer

37
00:02:11,650 --> 00:02:13,420
sa isang solong node upang matandaan ang buong puno.

38
00:02:13,420 --> 00:02:15,980
Node na ito ay Calle ng 'ugat' ng puno.

39
00:02:15,980 --> 00:02:18,320
Bumuo ng sa iyong diagram mula bago o gumuhit ng isang bagong isa

40
00:02:18,320 --> 00:02:21,690
tulad na mayroon ka ng isang kahon-at-arrow paglalarawan ng isang binary puno

41
00:02:21,690 --> 00:02:25,730
na may halaga 7, pagkatapos 3 sa kaliwa,

42
00:02:25,730 --> 00:02:32,760
pagkatapos 9 sa kanan, at pagkatapos ay 6 sa kanan ng 3. "

43
00:02:32,760 --> 00:02:34,810
Natin makita kung ang maaari kong tandaan ang lahat ng na sa aking ulo.

44
00:02:34,810 --> 00:02:37,670
Kaya ito ay na ang aming ugat dito.

45
00:02:37,670 --> 00:02:41,600
Magkakaroon kami ng ilang pointer sa isang lugar, isang bagay na kailangan namin tawagan ang ugat,

46
00:02:41,600 --> 00:02:45,140
at ito na tumuturo sa ito tao.

47
00:02:45,140 --> 00:02:48,490
Ngayon upang gumawa ng isang bagong node,

48
00:02:48,490 --> 00:02:52,870
kung ano ang namin, 3 sa kaliwa?

49
00:02:52,870 --> 00:02:57,140
Kaya ang isang bagong node na may 3, at simula POINTS null.

50
00:02:57,140 --> 00:02:59,190
Kukunin ko na lang ilagay N.

51
00:02:59,190 --> 00:03:02,250
Ngayon nais namin na pumunta sa kaliwa ng 7.

52
00:03:02,250 --> 00:03:06,840
Kaya naming baguhin ang pointer na ito sa ngayon tumuturo sa tao na ito.

53
00:03:06,840 --> 00:03:12,420
At ginagawa namin ang parehong. Gusto naming 9 sa paglipas dito

54
00:03:12,420 --> 00:03:14,620
kung saan simula lang sabi null.

55
00:03:14,620 --> 00:03:19,600
Kami ay pagpunta upang baguhin ang pointer, point sa 9,

56
00:03:19,600 --> 00:03:23,310
at ngayon ay nais naming ilagay 6 sa kanan ng 3.

57
00:03:23,310 --> 00:03:32,170
Kaya pagpunta sa - gumawa ng 6.

58
00:03:32,170 --> 00:03:34,310
At tao na magtuturo doon.

59
00:03:34,310 --> 00:03:38,320
Okay. Kaya na ito ang lahat ng nagtatanong sa amin upang gawin.

60
00:03:38,320 --> 00:03:42,770
>> Ngayon sabihin higit sa ilang mga terminolohiya.

61
00:03:42,770 --> 00:03:46,690
Uusapang namin na tungkol sa kung paano ang ugat ng puno pinakataas na node sa tree.

62
00:03:46,690 --> 00:03:54,720
Ang isa na naglalaman ng 7. Ang mga node sa ilalim ng puno ay tinatawag na ang mga dahon.

63
00:03:54,720 --> 00:04:01,240
Anumang node na lang may null dahil ang mga anak ay isang dahon.

64
00:04:01,240 --> 00:04:03,680
Kaya ito ay posible, kung ang aming puno ng binary ay lamang ng isang solong node,

65
00:04:03,680 --> 00:04:10,130
na ang puno ng dahon, at na ito.

66
00:04:10,130 --> 00:04:12,060
"Ang 'taas' ng puno ay ang bilang ng mga hops na mayroon kang upang gumawa ng

67
00:04:12,060 --> 00:04:16,620
upang makakuha ng mula sa tuktok ng dahon. "

68
00:04:16,620 --> 00:04:18,640
Namin, sa isang segundo, ang pagkakaiba

69
00:04:18,640 --> 00:04:21,940
sa pagitan ng mga balanseng at hindi balanseng puno ng binary,

70
00:04:21,940 --> 00:04:29,470
ngunit sa ngayon, ang kabuuang taas ng puno na ito

71
00:04:29,470 --> 00:04:34,520
Gusto ko sabihin ay 3, kahit na kung ikaw bilangin ang bilang ng mga hops

72
00:04:34,520 --> 00:04:39,710
mayroon kang upang makakuha ng hanggang 9, pagkatapos ito ay talagang lamang ng isang taas ng 2.

73
00:04:39,710 --> 00:04:43,340
Sa ngayon ito ay isang hindi balanseng puno ng binary,

74
00:04:43,340 --> 00:04:49,840
ngunit usapan natin ang tungkol balanseng kapag ito ay nakakakuha ng may-katuturan.

75
00:04:49,840 --> 00:04:52,040
Kaya ngayon maaari naming makipag-usap tungkol sa mga node sa isang puno sa mga tuntunin

76
00:04:52,040 --> 00:04:54,700
may kaugnayan sa iba pang mga node sa tree.

77
00:04:54,700 --> 00:04:59,730
Kaya ngayon mayroon kami ng mga magulang, mga anak, kapatid, ninuno, at kaapu-apuhan.

78
00:04:59,730 --> 00:05:05,650
Ang mga ito ay medyo karaniwang kahulugan, kung ano ang ibig sabihin nila.

79
00:05:05,650 --> 00:05:09,610
Kung hinihiling namin - ito ay mga magulang.

80
00:05:09,610 --> 00:05:12,830
Kaya ano ang magulang ng 3?

81
00:05:12,830 --> 00:05:16,090
[Mag-aaral] 7. >> Oo. Ang magulang ay pagpunta sa kung ano ang mga punto sa iyo.

82
00:05:16,090 --> 00:05:20,510
Pagkatapos ano ang ang mga bata ng 7?

83
00:05:20,510 --> 00:05:23,860
[Mag-aaral] 3 at 9. >> Oo.

84
00:05:23,860 --> 00:05:26,460
Pansinin na ang mga "bata" literal ay nangangahulugan ng mga bata,

85
00:05:26,460 --> 00:05:31,010
kaya 6 hindi angkop, dahil ito ay tulad ng isang apo.

86
00:05:31,010 --> 00:05:35,540
Ngunit kung pumunta kami ng mga kaapu-apuhan, kaya kung ano ang mga kaapu-apuhan ng 7?

87
00:05:35,540 --> 00:05:37,500
[Mag-aaral] 3, 6 at 9. >> Oo.

88
00:05:37,500 --> 00:05:42,330
Ang mga kaapu-apuhan ng root node na ang lahat sa tree,

89
00:05:42,330 --> 00:05:47,950
maliban siguro sa root node mismo, kung hindi mo nais na isaalang-alang na ang isang inapo.

90
00:05:47,950 --> 00:05:50,750
At sa wakas, ninuno, kaya ito ng kabaligtaran direksyon.

91
00:05:50,750 --> 00:05:55,740
Kaya ano ang mga ninuno ng 6?

92
00:05:55,740 --> 00:05:58,920
[Mag-aaral] 3 at 7. >> Oo. 9 ay hindi kasama.

93
00:05:58,920 --> 00:06:02,520
Ito ay direktang likod ng angkan sa root

94
00:06:02,520 --> 00:06:13,230
ay pagpunta sa ang iyong mga ninuno.

95
00:06:13,230 --> 00:06:16,300
>> "Sabihin namin na ang isang binary puno ay 'order' kung para sa bawat node sa tree,

96
00:06:16,300 --> 00:06:19,530
ang lahat ng kanyang mga kaapu-apuhan sa kaliwa ay may mas mababang halaga

97
00:06:19,530 --> 00:06:22,890
at ang lahat ng mga sa kanan may mas malaki halaga.

98
00:06:22,890 --> 00:06:27,060
Halimbawa, ang tree sa itaas ay order ngunit ito ay hindi ang tanging posibleng order arrangement. "

99
00:06:27,060 --> 00:06:30,180
Bago namin na,

100
00:06:30,180 --> 00:06:36,420
isang order na puno ng binary ay kilala rin bilang isang binary puno ng paghahanap.

101
00:06:36,420 --> 00:06:38,660
Narito namin mangyari na pagtawag sa isang order na puno ng binary,

102
00:06:38,660 --> 00:06:41,850
ngunit hindi ko narinig na tinatawag na ito ng isang order na puno ng binary bago,

103
00:06:41,850 --> 00:06:46,650
at sa pagsusulit namin mas malamang na ilagay ang binary paghahanap puno.

104
00:06:46,650 --> 00:06:49,250
Ang mga ito ay isa at sa parehong,

105
00:06:49,250 --> 00:06:54,580
at mahalagang makilala mo ang pagkakaiba sa pagitan ng binary puno at puno ng binary paghahanap.

106
00:06:54,580 --> 00:06:58,830
Isang puno ng binary ay isang puno na ang mga puntos sa dalawang bagay.

107
00:06:58,830 --> 00:07:02,120
Node bawat POINTS sa dalawang bagay.

108
00:07:02,120 --> 00:07:06,310
Walang pagdadahilan tungkol sa mga halaga na punto upang.

109
00:07:06,310 --> 00:07:11,370
Kaya gusto sa paglipas dito, dahil ito ay isang binary puno ng paghahanap,

110
00:07:11,370 --> 00:07:14,030
alam namin na kung pumunta iniwanan namin ng 7,

111
00:07:14,030 --> 00:07:16,670
pagkatapos ang lahat ng halaga na maaari naming posibleng maabot

112
00:07:16,670 --> 00:07:19,310
sa pamamagitan ng pagpunta sa kaliwa ng 7 ay may mas mababa sa 7.

113
00:07:19,310 --> 00:07:24,070
Pansinin na ang lahat ng mga halaga mas mababa kaysa sa 7 3 at 6.

114
00:07:24,070 --> 00:07:26,040
Iyon ang lahat sa kaliwa ng 7.

115
00:07:26,040 --> 00:07:29,020
Kung pumunta kami sa kanan ng 7, ang lahat ay may upang maging mas malaki kaysa sa 7,

116
00:07:29,020 --> 00:07:33,220
kaya 9 sa kanan ng 7, kaya hindi namin magandang.

117
00:07:33,220 --> 00:07:36,150
Ay hindi ito ang kaso para sa isang binary puno,

118
00:07:36,150 --> 00:07:40,020
para sa isang regular na binary puno lang namin 3 sa tuktok, 7 sa kaliwa,

119
00:07:40,020 --> 00:07:47,630
9 sa kaliwa ng 7, walang pag-order ng halaga ng anumang.

120
00:07:47,630 --> 00:07:56,140
Ngayon, hindi aktwal na namin gawin ito dahil ito ay nakakapagod at hindi kinakailangang,

121
00:07:56,140 --> 00:07:59,400
ngunit "subukan upang gumuhit ng maraming mga order na puno bilang maaari mong isipin ng

122
00:07:59,400 --> 00:08:01,900
gamit ang mga numero 7, 3, 9, at 6.

123
00:08:01,900 --> 00:08:06,800
Gaano karaming mga natatanging arrangement doon? Ano ang taas ng bawat isa? "

124
00:08:06,800 --> 00:08:10,480
>> Gagawin namin ang ilang, ngunit ang pangunahing ideya ay,

125
00:08:10,480 --> 00:08:16,530
ito ay hindi sa anumang paraan ng isang natatanging representasyon ng isang binary puno na naglalaman ng mga halagang ito.

126
00:08:16,530 --> 00:08:22,760
Ang kailangan namin ay ilang binary puno na naglalaman ng 7, 3, 6, at 9.

127
00:08:22,760 --> 00:08:25,960
Isa pang posibleng wastong isa ay magiging root ng 3,

128
00:08:25,960 --> 00:08:30,260
pumunta sa kaliwa at 6, pumunta sa kaliwa at 7,

129
00:08:30,260 --> 00:08:32,730
pumunta sa kaliwa at 9.

130
00:08:32,730 --> 00:08:36,169
Iyon ay isang perpektong wastong puno ng binary paghahanap.

131
00:08:36,169 --> 00:08:39,570
Ito ay hindi kapaki-pakinabang, dahil ito ay tulad ng isang naka-link na listahan

132
00:08:39,570 --> 00:08:43,750
at ang lahat ng mga payo lamang null.

133
00:08:43,750 --> 00:08:48,900
Ngunit ito ay isang wastong puno. Oo?

134
00:08:48,900 --> 00:08:51,310
[Mag-aaral] Huwag ang mga halaga na mas malaki sa kanan?

135
00:08:51,310 --> 00:08:56,700
O ay ito -? >> Mga ko nilalayong upang pumunta sa iba pang mga paraan.

136
00:08:56,700 --> 00:09:00,960
Mayroon ding - oo, sabihin lumipat na.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Magandang catch.

138
00:09:07,770 --> 00:09:11,730
Ay mayroon pa ring sumunod sa kung ano ang isang puno ng paghahanap ng binary ay dapat gawin.

139
00:09:11,730 --> 00:09:15,650
Kaya lahat sa kaliwa ay may upang maging mas mababa kaysa sa anumang ibinigay na node.

140
00:09:15,650 --> 00:09:23,180
Maaaring ilipat lang namin, sabihin, ito 6 at ilagay ito dito.

141
00:09:23,180 --> 00:09:26,880
Hindi, hindi namin maaari. Bakit ako patuloy na paggawa na?

142
00:09:26,880 --> 00:09:35,350
Natin gawin - dito ay 6, dito ay 7, 6 na puntos sa 3.

143
00:09:35,350 --> 00:09:39,290
Pa rin na ito ay isang may-bisang puno ng binary paghahanap.

144
00:09:39,290 --> 00:09:49,260
Ano ang mali kung ako - sabihin makita kung maaari kong darating up na may-aayos.

145
00:09:49,260 --> 00:09:52,280
Oo, okay. Kaya kung ano ang mali sa puno na ito?

146
00:09:52,280 --> 00:10:08,920
Hulaan ko Ibinigay ko sa iyo ng isang pahiwatig na may sira dito.

147
00:10:08,920 --> 00:10:14,430
Bakit ako patuloy na paggawa na?

148
00:10:14,430 --> 00:10:18,510
Okay. Ito mukhang makatwirang.

149
00:10:18,510 --> 00:10:22,590
Kung titingnan namin sa bawat node, tulad ng 7, pagkatapos sa kaliwa ng 7 ay isang 3.

150
00:10:22,590 --> 00:10:24,960
Kaya mayroon kaming 3, ang mga bagay sa kanan ng 3 6.

151
00:10:24,960 --> 00:10:27,750
At kung titingnan mo sa 6, ang mga bagay sa kanan ng 6 9.

152
00:10:27,750 --> 00:10:30,910
Kaya bakit ito ay hindi isang wastong puno ng binary paghahanap?

153
00:10:30,910 --> 00:10:36,330
[Mag-aaral] 9 pa rin sa kaliwa ng 7. >> Oo.

154
00:10:36,330 --> 00:10:43,710
Dapat ito ay totoo na ang lahat ng mga halaga na maaari mong posibleng maabot sa pamamagitan ng pagpunta sa kaliwa ng 7 ay mas mababa kaysa sa 7.

155
00:10:43,710 --> 00:10:49,120
Kung pumunta kami kaliwa ng 7, namin sa 3 at maaari pa rin namin ng 6 na,

156
00:10:49,120 --> 00:10:52,520
Maaari pa rin namin hanggang 9, ngunit sa pamamagitan ng pag-nawala mas mababa kaysa sa 7,

157
00:10:52,520 --> 00:10:55,070
Hindi namin ay dapat na magagawang upang makakuha ng sa isang numero na mas malaki kaysa sa 7.

158
00:10:55,070 --> 00:10:59,830
Kaya ito ay hindi isang wastong puno ng binary paghahanap.

159
00:10:59,830 --> 00:11:02,330
>> Aking kapatid na lalaki na aktwal na ay nagkaroon ng isang pakikipanayam na tanong

160
00:11:02,330 --> 00:11:07,760
na talaga ito, lamang code up ng isang bagay na upang mapatunayan

161
00:11:07,760 --> 00:11:10,500
kung ang isang puno ay isang binary puno ng paghahanap,

162
00:11:10,500 --> 00:11:13,580
at kaya ang unang bagay na ginawa niya ay lamang suriin upang makita

163
00:11:13,580 --> 00:11:17,020
kung ang kaliwa at kanang ay tama, at pagkatapos ay umulit pababa doon.

164
00:11:17,020 --> 00:11:19,700
Ngunit hindi lamang mo maaaring gawin iyon, mayroon kang upang subaybayan

165
00:11:19,700 --> 00:11:22,550
ng katotohanan na ngayon na nawala ko na kaliwa ng 7,

166
00:11:22,550 --> 00:11:26,340
lahat sa ito subtree ay dapat na mas mababa kaysa sa 7.

167
00:11:26,340 --> 00:11:28,430
Ang tamang algorithm ay kailangang subaybayan

168
00:11:28,430 --> 00:11:35,970
ng hangganan na ang mga halaga ay maaaring posibleng mahulog.

169
00:11:35,970 --> 00:11:38,360
Hindi namin ay pumunta sa pamamagitan ng lahat ng mga ito.

170
00:11:38,360 --> 00:11:41,630
May ay isang magaling na may kaugnayan sa pag-ulit,

171
00:11:41,630 --> 00:11:44,810
bagaman hindi namin nakuha sa mga, o hindi namin makakuha ng sa mga,

172
00:11:44,810 --> 00:11:47,030
pagtukoy kung gaano karaming mga may aktwal ay.

173
00:11:47,030 --> 00:11:53,180
Kaya may mga 14 sa kanila.

174
00:11:53,180 --> 00:11:56,020
Ang ideya ng kung paano mo gawin ito ay mathematically ay tulad,

175
00:11:56,020 --> 00:11:59,770
maaari kang pumili ng anumang solong root node,

176
00:11:59,770 --> 00:12:03,160
at pagkatapos ay kung pumili ako ng 7 root node,

177
00:12:03,160 --> 00:12:08,150
pagkatapos ay may, sabihin nating, ilang numero na maaaring pumunta sa aking kaliwang node,

178
00:12:08,150 --> 00:12:10,440
at may mga ilang numero na maaaring maging ang aking karapatan node,

179
00:12:10,440 --> 00:12:15,090
ngunit kung ako n kabuuang numero, pagkatapos ay ang halaga na maaaring pumunta sa kaliwa

180
00:12:15,090 --> 00:12:18,820
kasama ang halaga na maaaring pumunta sa kanan n - 1.

181
00:12:18,820 --> 00:12:26,130
Kaya ng natitirang mga numero, mayroon silang sa alinman sa kaliwa o kanan.

182
00:12:26,130 --> 00:12:31,580
Mukhang mahirap na, kung ko bang ilagay ang 3 unang pagkatapos ang lahat ay may upang pumunta sa kaliwa,

183
00:12:31,580 --> 00:12:35,080
ngunit kung ko bang ilagay ang 7, ang ilang mga bagay na maaaring pumunta sa kaliwa at ang ilang mga bagay na maaari pumunta sa kanan.

184
00:12:35,080 --> 00:12:39,570
At sa pamamagitan ng '3 unang 'nilalayong ko ang lahat ay maaaring pumunta sa kanan.

185
00:12:39,570 --> 00:12:42,350
Talaga, ikaw lang ay mag-isip tungkol sa ito bilang,

186
00:12:42,350 --> 00:12:47,980
kung gaano karaming mga bagay ay maaaring pumunta sa susunod na antas ng puno.

187
00:12:47,980 --> 00:12:50,420
At ito ay na 14, o maaari kang gumuhit ang lahat ng mga ito,

188
00:12:50,420 --> 00:12:54,650
at pagkatapos ay makakakuha ka ng 14.

189
00:12:54,650 --> 00:13:01,120
>> Pagpunta bumalik dito,

190
00:13:01,120 --> 00:13:03,510
"-Order ng mga binary puno ng mga cool na dahil maaari naming maghanap sa kanila

191
00:13:03,510 --> 00:13:06,910
sa isang katulad na paraan sa paghahanap sa paglipas ng pinagsunod-sunod na array.

192
00:13:06,910 --> 00:13:10,120
Upang gawin ito, kami magsimula sa root at gumana ang aming paraan pababa sa puno

193
00:13:10,120 --> 00:13:13,440
patungo sa mga dahon, pagsuri ng mga halaga sa bawat node laban sa halaga na kami ay naghahanap para sa.

194
00:13:13,440 --> 00:13:15,810
Kung ang halaga ang kasalukuyang node ay mas mababa kaysa sa halaga kaming naghahanap para sa,

195
00:13:15,810 --> 00:13:18,050
pumunta ka sa tabi ng karapatan ang bata node.

196
00:13:18,050 --> 00:13:20,030
Kung hindi man, pumunta ka sa kaliwang bata ang node.

197
00:13:20,030 --> 00:13:22,800
Sa ilang mga punto, makikita mo ang alinman mahanap ang halaga na naghahanap ka ng, o makikita mo tumakbo sa isang null,

198
00:13:22,800 --> 00:13:28,520
nagpapahiwatig ang halaga hindi sa tree. "

199
00:13:28,520 --> 00:13:32,450
Mayroon akong redraw tree nagkaroon kami dati, na kailangan kumuha ng isang segundo.

200
00:13:32,450 --> 00:13:38,280
Ngunit nais naming maghanap kung 6, 10, at 1 sa tree.

201
00:13:38,280 --> 00:13:49,180
Kaya kung ano ito ay, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
Ang mga numero na nais mong upang tumingin up, gusto naming maghanap 6.

203
00:13:52,730 --> 00:13:55,440
Paano ito algorithm trabaho?

204
00:13:55,440 --> 00:14:03,040
Well, kami din ng ilang ugat pointer sa aming puno.

205
00:14:03,040 --> 00:14:12,460
At gusto namin pumunta sa root at sabihin, ay ang halaga na katumbas sa halaga na kami ay naghahanap para sa?

206
00:14:12,460 --> 00:14:15,000
Kaya namin ang hinahanap para sa 6, kaya ito ay hindi katumbas.

207
00:14:15,000 --> 00:14:20,140
Kaya palaging kami makapupunta, at ngayon sinasabi namin, okay, kaya 6 ay mas mababa kaysa sa 7.

208
00:14:20,140 --> 00:14:23,940
Ba na ibig sabihin gusto namin upang pumunta sa kaliwa, o nais namin upang pumunta sa kanan?

209
00:14:23,940 --> 00:14:27,340
[Mag-aaral] Kaliwa. >> Oo.

210
00:14:27,340 --> 00:14:33,340
Ito ay makabuluhang mas madali, lahat ng kailangan mong gawin ay gumuhit ng isang posibleng node ng puno

211
00:14:33,340 --> 00:14:37,760
at pagkatapos mo don't - sa halip na sinusubukan na tingin sa iyong ulo,

212
00:14:37,760 --> 00:14:40,020
okay, kung ito ay mas mababa, ako pumunta sa kaliwa o pumunta sa kanan,

213
00:14:40,020 --> 00:14:43,030
lamang ng pagtingin sa ang larawang ito, napakalinaw na mayroon akong pumunta sa kaliwa

214
00:14:43,030 --> 00:14:47,700
kung ang node na ito ay mas mataas kaysa sa halaga na Naghahanap ako.

215
00:14:47,700 --> 00:14:52,600
Kaya pumunta sa kaliwa, ngayon ako sa 3.

216
00:14:52,600 --> 00:14:57,770
Gusto kong - 3 ay mas mababa kaysa sa halaga Naghahanap ako, na 6.

217
00:14:57,770 --> 00:15:03,420
Kaya pumunta kami sa kanan, at ngayon ko magtapos sa 6,

218
00:15:03,420 --> 00:15:07,380
na ang halaga Naghahanap ako, kaya bumalik ako ng totoo.

219
00:15:07,380 --> 00:15:15,760
Ang susunod na halaga ako pagpunta upang hanapin 10.

220
00:15:15,760 --> 00:15:23,230
Okay. Kaya 10, ngayon, ay pagpunta sa - putol na - pagpunta sa sundin ang mga ugat.

221
00:15:23,230 --> 00:15:27,670
Ngayon, 10 ay pagpunta sa mas malaki kaysa sa 7, kaya gusto kong tumingin sa kanan.

222
00:15:27,670 --> 00:15:31,660
Ako pagpunta sa darating sa paglipas dito, 10 na mas malaki kaysa 9,

223
00:15:31,660 --> 00:15:34,520
kaya ako pagpunta sa gusto upang tumingin sa kanan.

224
00:15:34,520 --> 00:15:42,100
Dumating ako sa paglipas dito, ngunit sa paglipas dito ngayon ako sa null.

225
00:15:42,100 --> 00:15:44,170
Ano ang gagawin ko kung ako pindutin null?

226
00:15:44,170 --> 00:15:47,440
[Mag-aaral] Bumalik maling? >> Oo. Hindi ko mahanap 10.

227
00:15:47,440 --> 00:15:49,800
1 ay isang halos katulad na kaso,

228
00:15:49,800 --> 00:15:51,950
maliban lamang na Binaligtad, sa halip na naghahanap

229
00:15:51,950 --> 00:15:56,540
pababa sa kanang bahagi, ako pagpunta sa tumingin sa kaliwang bahagi.

230
00:15:56,540 --> 00:16:00,430
>> Ngayon ko sa tingin namin aktwal na makakuha ng code.

231
00:16:00,430 --> 00:16:04,070
Narito ang kung saan - buksan ang CS50 appliance at i-navigate ang iyong paraan doon,

232
00:16:04,070 --> 00:16:07,010
ngunit maaari mo ring lamang gawin ito sa espasyo.

233
00:16:07,010 --> 00:16:09,170
Marahil ito ay perpekto upang gawin ito sa espasyo,

234
00:16:09,170 --> 00:16:13,760
dahil maaari naming gumagana sa puwang.

235
00:16:13,760 --> 00:16:19,170
"Una kakailanganin naming ang isang bagong uri ng kahulugan para sa isang binary puno node na naglalaman ng mga int halaga.

236
00:16:19,170 --> 00:16:21,400
Gamit ang boilerplate typedef sa ibaba,

237
00:16:21,400 --> 00:16:24,510
lumikha ng isang bagong kahulugan ng uri para sa isang node sa isang binary puno.

238
00:16:24,510 --> 00:16:27,930
Kung hindi ka makaalis. . . "Blah, blah, blah. Okay.

239
00:16:27,930 --> 00:16:30,380
Kaya sabihin ilagay ang boilerplate dito,

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

241
00:16:41,630 --> 00:16:44,270
Kaya ano ang mga field na kami ay pagpunta sa gusto sa aming node?

242
00:16:44,270 --> 00:16:46,520
[Mag-aaral] int at pagkatapos ay dalawang payo?

243
00:16:46,520 --> 00:16:49,700
>> Int halaga, dalawang payo? Paano ko isulat ang payo?

244
00:16:49,700 --> 00:16:58,440
[Mag-aaral] Struct. >> Ang dapat kong mag-zoom in Oo, kaya struct node * pakaliwa,

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

246
00:17:01,320 --> 00:17:03,460
At tandaan ang talakayan mula sa huling beses,

247
00:17:03,460 --> 00:17:15,290
na ito ay hindi gumagawa ng mga kahulugan, ito ay hindi gumagawa ng mga kahulugan,

248
00:17:15,290 --> 00:17:18,270
ito ay hindi gumagawa ng mga kahulugan.

249
00:17:18,270 --> 00:17:25,000
Kailangan mo ang lahat doon upang tukuyin ito recursive struct.

250
00:17:25,000 --> 00:17:27,970
Okay, sa gayon ay ang kung ano ang aming puno ay pagpunta sa hitsura.

251
00:17:27,970 --> 00:17:37,670
Kung ginawa namin ng trinary puno, pagkatapos node ay maaaring magmukhang B1, B2, struct node * B3,

252
00:17:37,670 --> 00:17:43,470
kung saan b ay isang branch - aktwal na, ko na mas narinig ito pakaliwa, gitna, kanan, ngunit kahit anong.

253
00:17:43,470 --> 00:17:55,610
Lamang namin pakialam tungkol sa binary, kaya karapatan, ang natitira.

254
00:17:55,610 --> 00:17:59,110
"Ngayon ay ipinapahayag ng pandaigdigang node * variable para sa ugat ng puno."

255
00:17:59,110 --> 00:18:01,510
Kaya hindi namin upang gawin iyon.

256
00:18:01,510 --> 00:18:08,950
Upang gumawa ng mga bagay bahagyang mas mahirap at mas pangkalahatan,

257
00:18:08,950 --> 00:18:11,570
hindi namin ay may isang global variable node.

258
00:18:11,570 --> 00:18:16,710
Sa halip, sa pangunahing ay ipinapahayag namin ang lahat ng aming mga node bagay,

259
00:18:16,710 --> 00:18:20,500
at na nangangahulugan na sa ibaba, kapag nagsimula kami tumatakbo

260
00:18:20,500 --> 00:18:23,130
aming naglalaman ng function na at ang aming insert function na,

261
00:18:23,130 --> 00:18:27,410
sa halip ng aming mga naglalaman ng function na lang gamit ang global variable node,

262
00:18:27,410 --> 00:18:34,280
kami ay pagpunta sa tumagal ng isang argumento sa puno na gusto naming i-proseso.

263
00:18:34,280 --> 00:18:36,650
Ang pagkakaroon ang global variable ay dapat upang gumawa ng mga bagay madali.

264
00:18:36,650 --> 00:18:42,310
Kami ay pagpunta upang gumawa ng mga bagay mas mahirap.

265
00:18:42,310 --> 00:18:51,210
Ngayon, kumuha nang isang minuto o higit pa upang gawin ito uri ng bagay,

266
00:18:51,210 --> 00:18:57,690
kung saan sa loob ng pangunahing nais mong upang likhain ang tree, at na ang lahat ng gusto mong gawin.

267
00:18:57,690 --> 00:19:04,530
Subukan at bumuo ng mga ito puno sa iyong pangunahing function na.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Kaya hindi mo kahit na itinayo puno ang buong paraan.

269
00:19:47,610 --> 00:19:49,840
Ngunit sinuman ay may isang bagay na maaari kong makuha ang

270
00:19:49,840 --> 00:20:03,130
upang ipakita kung paano maaaring isa magsimulang bumuo ng tulad ng isang puno?

271
00:20:03,130 --> 00:20:08,080
[Mag-aaral] ng banging May, sinusubukan upang makakuha ng out.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Sinuman ay kumportable sa kanilang puno construction?

273
00:20:13,100 --> 00:20:15,520
[Mag-aaral] Oo naman. Hindi tapos na ito. >> Masarap na ito. Maaari lang namin matapos -

274
00:20:15,520 --> 00:20:26,860
oh, maaari mong i-save ang mga ito? Yehey.

275
00:20:26,860 --> 00:20:32,020
Kaya dito mayroon kaming - oh, bahagyang ako cut off.

276
00:20:32,020 --> 00:20:34,770
Ako naka-zoom in?

277
00:20:34,770 --> 00:20:37,730
Mag-zoom in, mag-scroll. >> Mayroon akong tanong. >> Oo?

278
00:20:37,730 --> 00:20:44,410
[Mag-aaral] Kapag mong tukuyin struct, ang mga bagay tulad ng nasimulan sa anumang bagay?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No. >> Okay. Kaya nais mong simulan ang -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Kapag mong tukuyin, o kapag ikaw ay ipinapahayag struct,

281
00:20:50,450 --> 00:20:55,600
hindi ito nasimulan sa pamamagitan ng default; lang ito i kung ikaw idedeklara ang isang int.

282
00:20:55,600 --> 00:20:59,020
Ito ay eksakto ang parehong bagay. Ito ay tulad ng bawat isa ng mga indibidwal na mga patlang

283
00:20:59,020 --> 00:21:04,460
ay maaaring magkaroon ng isang halaga ng basura sa loob nito. >> At ay posible upang tukuyin - o idedeklara ng struct

284
00:21:04,460 --> 00:21:07,740
sa isang paraan na ito initialize ang mga ito?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Oo. Kaya, shortcut Pinasimulan syntax

286
00:21:13,200 --> 00:21:18,660
ay pagpunta sa hitsura -

287
00:21:18,660 --> 00:21:22,200
Mayroong dalawang mga paraan na maaari naming gawin ito. Tingin ko dapat namin makatipon ito

288
00:21:22,200 --> 00:21:25,840
upang matiyak na kumalatong din ito.

289
00:21:25,840 --> 00:21:28,510
Ang pagkakasunud-sunod ng mga argument na ay sa struct,

290
00:21:28,510 --> 00:21:32,170
inilagay mo bilang ang pagkakasunud-sunod ng mga argumento sa loob ng mga kulot tirante.

291
00:21:32,170 --> 00:21:35,690
Kaya kung nais mong i-initialize ito sa 9 at ang natitira ay walang bisa at pagkatapos karapatan null,

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

293
00:21:41,570 --> 00:21:47,890
Alternatibo ay, at editor ay hindi gusto ang syntax na ito,

294
00:21:47,890 --> 00:21:50,300
at sa tingin nito ay Gusto ko ng isang bagong bloke,

295
00:21:50,300 --> 00:22:01,800
ngunit alternatibo ay isang bagay tulad ng -

296
00:22:01,800 --> 00:22:04,190
dito, makikita ko bang ilagay ang mga ito sa isang bagong linya.

297
00:22:04,190 --> 00:22:09,140
Maaari mong tahasang sabihin, nakalimutan ko ang eksaktong syntax.

298
00:22:09,140 --> 00:22:13,110
Sa gayon maaari mong tahasang tugunan ang mga ito sa pamamagitan ng pangalan, at sabihin,

299
00:22:13,110 --> 00:22:21,570
C, o. Halaga = 9,. Kaliwang = null.

300
00:22:21,570 --> 00:22:24,540
Ako paghula mga pangangailangan upang maging ng mga kuwit.

301
00:22:24,540 --> 00:22:29,110
. Karapatan = null, upang sa ganitong paraan hindi mo gusto

302
00:22:29,110 --> 00:22:33,780
aktwal na kailangan upang malaman ang pagkakasunod-sunod ng struct,

303
00:22:33,780 --> 00:22:36,650
at kung binabasa mo ito, mas tahasang

304
00:22:36,650 --> 00:22:41,920
tungkol sa kung ano ang halaga ay nasimulan sa.

305
00:22:41,920 --> 00:22:44,080
>> Ito ang mangyayari na ang isa sa mga bagay na -

306
00:22:44,080 --> 00:22:49,100
kaya, para sa pinaka-bahagi, C + + ay isang superset ng C.

307
00:22:49,100 --> 00:22:54,160
Maaari mong gawin ang C code, ilipat ito sa C + +, at dapat itong makatipon.

308
00:22:54,160 --> 00:22:59,570
Ito ay isa ng ang mga bagay na C + + ay hindi sumusuporta, kaya mga tao malamang hindi na gawin ito.

309
00:22:59,570 --> 00:23:01,850
Hindi ko alam kung iyon lamang ang dahilan na mga tao malamang hindi na gawin ito,

310
00:23:01,850 --> 00:23:10,540
ngunit ang kaso kung saan kailangan ko upang gamitin ito na kinakailangan upang gumana sa C + + at kaya hindi ko itong gamitin.

311
00:23:10,540 --> 00:23:14,000
Ang isa pang halimbawa ng isang bagay na ay hindi gumagana sa C + + ay

312
00:23:14,000 --> 00:23:16,940
kung paano ang malloc nagbabalik ng "walang bisa *," technically,

313
00:23:16,940 --> 00:23:20,200
ngunit maaari mong sabihin na ang magpasinda * x = malloc anumang,

314
00:23:20,200 --> 00:23:22,840
at ito ay awtomatikong maging cast sa isang pansamantalang trabaho *.

315
00:23:22,840 --> 00:23:25,450
Na awtomatikong cast ay hindi mangyayari sa C + +.

316
00:23:25,450 --> 00:23:28,150
Na hindi makatipon, at nais mong tahasang kailangang sabihin

317
00:23:28,150 --> 00:23:34,510
magpasinda *, malloc, anumang, upang pinalayas ang mga ito sa isang pansamantalang trabaho *.

318
00:23:34,510 --> 00:23:37,270
May mga hindi maraming bagay na C at C + + hindi sumasang-ayon sa,

319
00:23:37,270 --> 00:23:40,620
ngunit ang mga dalawang.

320
00:23:40,620 --> 00:23:43,120
Kaya kami gamit ang syntax na ito.

321
00:23:43,120 --> 00:23:46,150
Ngunit kahit na hindi namin na syntax,

322
00:23:46,150 --> 00:23:49,470
kung ano ang - ay maaaring maging mali na ito?

323
00:23:49,470 --> 00:23:52,170
[Mag-aaral] hindi ko kailangang dereference ito? >> Oo.

324
00:23:52,170 --> 00:23:55,110
Tandaan na ang arrow sa ay may implicit dereference,

325
00:23:55,110 --> 00:23:58,230
at kaya kapag lamang kami pagharap sa isang struct,

326
00:23:58,230 --> 00:24:04,300
gusto naming gamitin. upang makakuha ng sa isang patlang sa loob ng struct.

327
00:24:04,300 --> 00:24:07,200
At lamang ang oras na ginagamit namin arrow kapag gusto naming gawin -

328
00:24:07,200 --> 00:24:13,450
mahusay, arrow ay katumbas -

329
00:24:13,450 --> 00:24:17,020
na kung ano ito nilalayong kung ginamit ko ang arrow.

330
00:24:17,020 --> 00:24:24,600
Maraming arrow ay nangangahulugan, ang dereference ito, ngayon ako sa isang struct, at maaari ko bang makuha ang patlang.

331
00:24:24,600 --> 00:24:28,040
Alinman makuha ang patlang nang direkta o dereference at makuha ang field -

332
00:24:28,040 --> 00:24:30,380
Hulaan ko ito ay dapat na halaga.

333
00:24:30,380 --> 00:24:33,910
Ngunit dito ako pagharap sa lamang struct, hindi isang pointer sa isang struct,

334
00:24:33,910 --> 00:24:38,780
at kaya hindi ko maaaring gamitin ang mga arrow.

335
00:24:38,780 --> 00:24:47,510
Ngunit ang ganitong uri ng bagay ang maaari naming gawin para sa lahat ng mga node.

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

337
00:24:55,790 --> 00:25:09,540
Ito ay 6, 7, at 3.

338
00:25:09,540 --> 00:25:16,470
Pagkatapos ay maaari naming mag-set up ang mga sangay sa aming puno, maaari kaming magkaroon ng 7 -

339
00:25:16,470 --> 00:25:21,650
maaari naming, ang kanyang kaliwa dapat tumuro sa 3.

340
00:25:21,650 --> 00:25:25,130
Kaya kung paano namin gawin iyon?

341
00:25:25,130 --> 00:25:29,320
[Mag-aaral, hindi maintindihan] >> Oo. Ang address ng node3,

342
00:25:29,320 --> 00:25:34,170
at kung hindi ka magkaroon ng address, pagkatapos ito ay hindi makatipon.

343
00:25:34,170 --> 00:25:38,190
Ngunit tandaan na ang mga payo sa sa susunod na node.

344
00:25:38,190 --> 00:25:44,930
Ang karapatang dapat tumuro 9,

345
00:25:44,930 --> 00:25:53,330
at 3 dapat tumuro sa kanan hanggang 6.

346
00:25:53,330 --> 00:25:58,480
Tingin ko ito ay ang lahat ng set. Anumang mga komento o katanungan?

347
00:25:58,480 --> 00:26:02,060
[Mag-aaral, hindi maintindihan] ugat ay pagpunta sa 7.

348
00:26:02,060 --> 00:26:08,210
Maaari lang namin sabihin node * ptr =

349
00:26:08,210 --> 00:26:14,160
o ugat, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Para sa aming mga layuning pang-, kami ay pagpunta sa pagharap sa insert,

351
00:26:20,730 --> 00:26:25,490
kaya namin ay pagpunta sa gusto mong magsulat ng isang function na upang ipasok sa ito binary puno

352
00:26:25,490 --> 00:26:34,230
at ipasok ang tiyak na tumawag ng malloc upang lumikha ng isang bagong node para sa puno.

353
00:26:34,230 --> 00:26:36,590
Kaya bagay ay pagpunta upang makakuha ng magulo ang katotohanan na ang ilang mga node

354
00:26:36,590 --> 00:26:38,590
ay kasalukuyang sa stack

355
00:26:38,590 --> 00:26:43,680
at iba pang mga node ay pagpunta upang tapusin up sa magbunton kapag namin isingit ang mga ito.

356
00:26:43,680 --> 00:26:47,640
Ito ay perpektong wasto, ngunit ang tanging dahilan

357
00:26:47,640 --> 00:26:49,600
hindi namin magagawang upang gawin ito sa stack

358
00:26:49,600 --> 00:26:51,840
ay dahil ito ay isang contrived halimbawa na alam namin

359
00:26:51,840 --> 00:26:56,360
puno ay dapat na itinayo bilang 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Kung hindi namin ginawa ito, hindi namin ay magkakaroon sa malloc sa unang lugar.

361
00:27:02,970 --> 00:27:06,160
Bilang makita namin ng kaunti mamaya, dapat naming malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Sa ngayon perpektong makatwirang upang ilagay sa stack,

363
00:27:08,570 --> 00:27:14,750
ngunit sabihin baguhin ito sa isang pagpapatupad ng malloc.

364
00:27:14,750 --> 00:27:17,160
Kaya ang bawat isa sa mga ito ay ngayon pagpunta sa isang bagay tulad ng

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

366
00:27:24,240 --> 00:27:28,040
At ngayon kami ay pagpunta sa gawin ang aming check.

367
00:27:28,040 --> 00:27:34,010
kung ang (node9 == null) - Hindi ko nais na -

368
00:27:34,010 --> 00:27:40,950
bumalik 1, at pagkatapos ay maaari naming gawin node9-> dahil ngayon ang isang pointer,

369
00:27:40,950 --> 00:27:45,300
halaga = 6, node9-> pakaliwa = null,

370
00:27:45,300 --> 00:27:48,930
node9-> kanan = null,

371
00:27:48,930 --> 00:27:51,410
at kami ay pagpunta upang gawin iyon para sa bawat isa ng mga node.

372
00:27:51,410 --> 00:27:57,490
Sa halip, sabihin ilagay ito sa loob ng isang hiwalay na function na.

373
00:27:57,490 --> 00:28:00,620
Sabihin tumawag ito node * build_node,

374
00:28:00,620 --> 00:28:09,050
at ito ay medyo katulad sa mga API na nagbibigay kami para sa Huffman coding.

375
00:28:09,050 --> 00:28:12,730
Kami magbibigay sa iyo ng initializer function para sa isang puno

376
00:28:12,730 --> 00:28:20,520
at deconstructor "function" para sa mga puno at ang parehong para sa kagubatan.

377
00:28:20,520 --> 00:28:22,570
>> Kaya dito kami ay pagpunta sa magkaroon ng isang function na initializer

378
00:28:22,570 --> 00:28:25,170
upang bumuo ng isang node para sa amin.

379
00:28:25,170 --> 00:28:29,320
At ito upang tumingin medyo mas eksakto tulad nito.

380
00:28:29,320 --> 00:28:32,230
At kahit ako na maging tamad at hindi baguhin ang pangalan ng variable,

381
00:28:32,230 --> 00:28:34,380
kahit node9 ginagawang walang kahulugan na ito.

382
00:28:34,380 --> 00:28:38,610
Oh, hulaan ko node9 ang halaga ay hindi dapat 6.

383
00:28:38,610 --> 00:28:42,800
Ngayon ay maaari naming ibalik ang node9.

384
00:28:42,800 --> 00:28:49,550
At dito dapat namin bumalik null.

385
00:28:49,550 --> 00:28:52,690
Ang bawat tao'y sumasang-ayon sa na build-a-node function na?

386
00:28:52,690 --> 00:28:59,780
Kaya ngayon namin lamang tumawag na upang bumuo ng anumang node sa isang ibinigay na halaga at null pointer.

387
00:28:59,780 --> 00:29:09,750
Ngayon ay maaari naming tumawag na, maaari naming gawin node * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
At sabihin gawin. . .

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

390
00:29:33,980 --> 00:29:39,330
At ngayon, gusto naming i-set up ang parehong mga payo,

391
00:29:39,330 --> 00:29:42,470
maliban ngayon ang lahat na sa mga tuntunin ng pointer

392
00:29:42,470 --> 00:29:48,480
kaya hindi na kailangan ang address ng.

393
00:29:48,480 --> 00:29:56,300
Okay. Kaya kung ano ang huling bagay na gusto kong gawin?

394
00:29:56,300 --> 00:30:03,850
Mayroong isang error-checking na hindi ako ginagawa.

395
00:30:03,850 --> 00:30:06,800
Ano ang bumuo ng node return?

396
00:30:06,800 --> 00:30:11,660
[Mag-aaral, hindi maintindihan] >> Oo. Kung Nabigo ang malloc, bumalik null.

397
00:30:11,660 --> 00:30:16,460
Kaya ako pagpunta sa lazily ilagay ito dito sa halip ng paggawa ng isang kundisyon para sa bawat.

398
00:30:16,460 --> 00:30:22,320
Kung (node9 == null, o - kahit simple,

399
00:30:22,320 --> 00:30:28,020
ito ay katumbas lamang kung hindi node9.

400
00:30:28,020 --> 00:30:38,310
Kaya kung hindi node9, o hindi node6, o hindi node3, o hindi node7, bumalik 1.

401
00:30:38,310 --> 00:30:42,850
Siguro dapat naming i-print ang malloc Nabigo, o isang bagay na.

402
00:30:42,850 --> 00:30:46,680
[Mag-aaral] Ay maling katumbas null pati na rin?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Anumang zero na halaga ay hindi.

404
00:30:51,290 --> 00:30:53,920
Kaya null ay zero na halaga.

405
00:30:53,920 --> 00:30:56,780
Zero ay isang zero na halaga. Maling ay isang zero na halaga.

406
00:30:56,780 --> 00:31:02,130
Anumang - medyo mas lamang ang 2 zero na halaga null at zero,

407
00:31:02,130 --> 00:31:07,900
hindi totoo ay hash tinukoy bilang zero.

408
00:31:07,900 --> 00:31:13,030
Na nalalapat din kung namin idineklara global variable.

409
00:31:13,030 --> 00:31:17,890
Kung ginawa namin node * ugat dito,

410
00:31:17,890 --> 00:31:24,150
pagkatapos - ang magaling na bagay tungkol sa mga pangkalahatang variable ay na sila ay laging magkaroon ng isang paunang halaga.

411
00:31:24,150 --> 00:31:27,500
Na hindi totoo ng mga function, kung paano sa loob ng dito,

412
00:31:27,500 --> 00:31:34,870
kung kami ay may, tulad ng, node * o node x.

413
00:31:34,870 --> 00:31:37,380
Wala kaming ideya kung ano ang x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
o maaari naming i-print ang mga ito at maaari nilang arbitrary.

415
00:31:40,700 --> 00:31:44,980
Iyan ay hindi totoo ng mga pangkalahatang variable.

416
00:31:44,980 --> 00:31:47,450
Kaya node ugat o node x.

417
00:31:47,450 --> 00:31:53,410
Sa pamamagitan ng default, ang lahat ng global, kung hindi tahasang nasimulan sa ilang mga halaga,

418
00:31:53,410 --> 00:31:57,390
ay may zero na halaga bilang halaga nito.

419
00:31:57,390 --> 00:32:01,150
Kaya dito, node * ugat, hindi namin tahasang initialize ito sa anumang bagay,

420
00:32:01,150 --> 00:32:06,350
kaya ang kanyang default na halaga ay null, na ang zero na halaga ng mga payo.

421
00:32:06,350 --> 00:32:11,870
Ang default na halaga ng x ay nangangahulugan na x.value ay zero,

422
00:32:11,870 --> 00:32:14,260
x.left ay null, at ay null ang x.right.

423
00:32:14,260 --> 00:32:21,070
Kaya dahil ito ay isang struct, ang lahat ng mga field ng struct zero na halaga.

424
00:32:21,070 --> 00:32:24,410
Hindi namin kailangang gamitin na dito, bagaman.

425
00:32:24,410 --> 00:32:27,320
[Mag-aaral] Ang mga structs ay naiiba kaysa sa iba pang mga variable, at ang iba pang mga variable ay

426
00:32:27,320 --> 00:32:31,400
basura halaga; ito ay zero?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Iba pang mga halaga. Kaya sa x, x ay zero.

428
00:32:36,220 --> 00:32:40,070
Kung sa pandaigdigang saklaw, ito ay isang paunang halaga. >> Okay.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Alinman ang paunang halaga na ibinigay mo ito o zero.

430
00:32:48,950 --> 00:32:53,260
Tingin ko na tumatagal ng pag-aalaga ng lahat ng ito.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Kaya ang susunod na bahagi ng tanong nagtatanong,

432
00:32:58,390 --> 00:33:01,260
"Ngayon gusto naming magsulat ng isang function na tinatawag na naglalaman ng

433
00:33:01,260 --> 00:33:04,930
na may prototype ng bool naglalaman ng int na halaga. "

434
00:33:04,930 --> 00:33:08,340
Hindi namin gawin bool naglalaman int halaga.

435
00:33:08,340 --> 00:33:15,110
Aming prototype ay pagpunta sa hitsura

436
00:33:15,110 --> 00:33:22,380
bool naglalaman (int halaga.

437
00:33:22,380 --> 00:33:24,490
At pagkatapos din kami upang pumasa ito sa puno

438
00:33:24,490 --> 00:33:28,870
na dapat ito ng pagsuri upang makita kung ito ay may halagang iyon.

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

440
00:33:38,290 --> 00:33:44,440
At pagkatapos ay maaari naming tumawag ang mga ito sa isang bagay tulad ng,

441
00:33:44,440 --> 00:33:46,090
siguro namin nais sa printf o isang bagay.

442
00:33:46,090 --> 00:33:51,040
Naglalaman ng 6, ang aming mga ugat.

443
00:33:51,040 --> 00:33:54,300
Na dapat bumalik, o totoo,

444
00:33:54,300 --> 00:33:59,390
kung saan ay naglalaman ng 5 ugat dapat bumalik false.

445
00:33:59,390 --> 00:34:02,690
Kaya kumuha ng isang segundo upang ipatupad ang.

446
00:34:02,690 --> 00:34:06,780
Maaari mong gawin ito sa alinman iteratively o recursively.

447
00:34:06,780 --> 00:34:09,739
Ang magaling na bagay tungkol sa paraan itinakda namin ang mga bagay-bagay ay na

448
00:34:09,739 --> 00:34:12,300
lends mismo sa aming recursive solusyon mas madali

449
00:34:12,300 --> 00:34:14,719
sa ang global variable na paraan ginawa.

450
00:34:14,719 --> 00:34:19,750
Dahil kung lamang namin naglalaman ng int na halaga, pagkatapos ay mayroon kaming walang paraan ng recursing pababa subtrees.

451
00:34:19,750 --> 00:34:24,130
Gusto naming magkaroon ng isang hiwalay na function ng lingkod na recurses ang ang mga subtrees para sa amin.

452
00:34:24,130 --> 00:34:29,610
Ngunit dahil binago namin ito sa tree bilang isang argument,

453
00:34:29,610 --> 00:34:32,760
na dapat na palaging ito sa unang lugar,

454
00:34:32,760 --> 00:34:35,710
ngayon maaari naming recurse mas madali.

455
00:34:35,710 --> 00:34:38,960
Kaya umuulit o recursive, ipagpapatuloy namin sa paglipas ng parehong,

456
00:34:38,960 --> 00:34:46,139
ngunit gagamitin namin makita na recursive dulo up medyo madali.

457
00:34:59,140 --> 00:35:02,480
Okay. Ba ang sinuman ng isang bagay na maaari naming?

458
00:35:02,480 --> 00:35:12,000
>> [Mag-aaral] Mayroon akong isang umuulit solusyon. >> Lahat ng karapatan, umuulit.

459
00:35:12,000 --> 00:35:16,030
Okay, mukhang mahusay na ito.

460
00:35:16,030 --> 00:35:18,920
Kaya, nais na maglakad sa amin sa pamamagitan nito?

461
00:35:18,920 --> 00:35:25,780
[Mag-aaral] Oo naman. Kaya ba akong magtakda ng Temp variable upang makuha ang unang node ng puno.

462
00:35:25,780 --> 00:35:28,330
At pagkatapos ko lang looped sa pamamagitan habang Temp hindi katumbas null,

463
00:35:28,330 --> 00:35:31,700
kaya habang ay pa rin sa tree, hulaan ko.

464
00:35:31,700 --> 00:35:35,710
At kung ang halaga ay katumbas ng ang halaga na Temp ay tumuturo sa,

465
00:35:35,710 --> 00:35:37,640
pagkatapos ay nagbalik ng halagang iyon.

466
00:35:37,640 --> 00:35:40,210
Kung hindi man, sumusuri kung ito ay sa kanang bahagi o sa kaliwang bahagi.

467
00:35:40,210 --> 00:35:43,400
Kung sakaling makakuha ng isang sitwasyon kung saan mayroong hindi hihigit puno,

468
00:35:43,400 --> 00:35:47,330
ito nagbabalik - labasan loop at nagbabalik ng maling.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. Kaya na mukhang mabuti.

470
00:35:52,190 --> 00:35:58,470
Sinuman ay may anumang mga komento sa anumang?

471
00:35:58,470 --> 00:36:02,400
Mayroon akong walang mga komento sa kawastuhan sa lahat.

472
00:36:02,400 --> 00:36:11,020
Ang isang bagay na maaari naming gawin ay ang tao na ito.

473
00:36:11,020 --> 00:36:21,660
Oh, ito ay pagpunta sa pumunta ng kaunti longish.

474
00:36:21,660 --> 00:36:33,460
Ako maayos na up. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Ang bawat tao'y dapat tandaan kung paano tatluhan gumagana.

476
00:36:37,150 --> 00:36:38,610
Nagkaroon ng tiyak na mga pagsusulit sa nakaraan

477
00:36:38,610 --> 00:36:41,170
na nagbibigay sa iyo ng isang function na may isang tatluhan operator,

478
00:36:41,170 --> 00:36:45,750
at sabihin, isalin ito, gawin ang isang bagay na hindi gumagamit ng tatluhan.

479
00:36:45,750 --> 00:36:49,140
Kaya ito ay isang napaka-karaniwang kaso ng kapag Gusto ko tingin na gamitin ang tatluhan,

480
00:36:49,140 --> 00:36:54,610
kung saan kung ang ilang mga kundisyon na magtakda ng isang variable sa isang bagay,

481
00:36:54,610 --> 00:36:58,580
tao nakatakda na parehong variable sa iba pa.

482
00:36:58,580 --> 00:37:03,390
Iyon ay isang bagay na lubhang madalas maaaring transformed sa ganitong uri ng bagay

483
00:37:03,390 --> 00:37:14,420
kung saan-set na variable na ito - o, mahusay, ay ito tunay? Pagkatapos ito, iba pa ito.

484
00:37:14,420 --> 00:37:18,550
[Mag-aaral] Ang unang isa ay kung totoo, i-right?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Oo. Ang paraan ko laging basahin ito ay, Temp katumbas ng halaga na mas mataas kaysa sa Temp halaga,

486
00:37:25,570 --> 00:37:30,680
pagkatapos ito, iba pa ito. Ito na humihiling ng isang tanong.

487
00:37:30,680 --> 00:37:35,200
Ito mas malaki? Pagkatapos gawin ang unang bagay. Iba Pa gawin ang ikalawang bagay.

488
00:37:35,200 --> 00:37:41,670
Ko halos palaging - tutuldok ang, ko lang - sa aking ulo, basahin ko bilang tao.

489
00:37:41,670 --> 00:37:47,180
>> Ba ang sinuman magkaroon ng isang recursive na solusyon?

490
00:37:47,180 --> 00:37:49,670
Okay. Ito kami ay pagpunta sa - ito na maging mahusay,

491
00:37:49,670 --> 00:37:53,990
ngunit kami ay pagpunta upang gawin itong mas mahusay.

492
00:37:53,990 --> 00:37:58,720
Ito ay medyo magkano ang parehong eksaktong ideya.

493
00:37:58,720 --> 00:38:03,060
Lang, na rin, ang gusto mong ipaliwanag?

494
00:38:03,060 --> 00:38:08,340
[Mag-aaral] Oo naman. Kaya kami ay siguraduhin na ang puno ay hindi null unang,

495
00:38:08,340 --> 00:38:13,380
dahil kung puno ay null ito upang bumalik false dahil hindi pa namin ito natagpuan.

496
00:38:13,380 --> 00:38:19,200
At kung mayroong pa rin puno, kami pumunta sa - muna namin suriin kung ang halaga ay ang kasalukuyang node.

497
00:38:19,200 --> 00:38:23,740
Nagbabalik ng tunay na kung ito ay, at kung hindi namin recurse sa kaliwa o kanan.

498
00:38:23,740 --> 00:38:25,970
Ba ng tunog na naaangkop? >> MM-Hmm. (Kasunduan)

499
00:38:25,970 --> 00:38:33,880
Kaya mapapansin na ito ay halos - structurally na halos kapareho sa umuulit solusyon.

500
00:38:33,880 --> 00:38:38,200
Lang na sa halip na recursing, nagkaroon kami ng isang habang loop.

501
00:38:38,200 --> 00:38:40,840
At ang base kaso dito kung saan puno ay hindi katumbas null

502
00:38:40,840 --> 00:38:44,850
ang kondisyon sa ilalim kung saan namin sinira ng loop habang.

503
00:38:44,850 --> 00:38:50,200
Ang mga ito ay halos katulad na. Ngunit hindi namin ay pagpunta sa isang hakbang karagdagang.

504
00:38:50,200 --> 00:38:54,190
Ngayon, gawin namin ang parehong bagay dito.

505
00:38:54,190 --> 00:38:57,680
Mapansin kami bumabalik ang parehong bagay sa parehong mga linyang ito,

506
00:38:57,680 --> 00:39:00,220
maliban sa isang argument ay naiiba.

507
00:39:00,220 --> 00:39:07,950
Kaya kami upang gawing na sa isang tatluhan.

508
00:39:07,950 --> 00:39:13,790
Pindutin ko ang pagpipilian ng isang bagay, at gumawa ng simbolo. Okay.

509
00:39:13,790 --> 00:39:21,720
Kaya kami upang bumalik ay naglalaman na.

510
00:39:21,720 --> 00:39:28,030
Ito ay pagkuha sa maramihang mga linya, well, naka-zoom in ito ay.

511
00:39:28,030 --> 00:39:31,060
Karaniwan, bilang isang pangkakanyahan bagay, hindi ko sa tingin maraming tao

512
00:39:31,060 --> 00:39:38,640
maglagay ng puwang pagkatapos ng arrow, ngunit hulaan ko kung ikaw ay pare-pareho, fine.

513
00:39:38,640 --> 00:39:44,320
Kung ang halaga ay mas mababa kaysa sa halaga ng puno, gusto naming recurse sa kaliwa ng puno,

514
00:39:44,320 --> 00:39:53,890
tao gusto naming recurse sa puno karapatan.

515
00:39:53,890 --> 00:39:58,610
Kaya na hakbang isa ng hitsura ito mas maliit.

516
00:39:58,610 --> 00:40:02,660
Hakbang dalawa ng hitsura ito mas maliit -

517
00:40:02,660 --> 00:40:09,150
namin paghiwalayin ito sa maramihang mga linya.

518
00:40:09,150 --> 00:40:16,500
Okay. Hakbang dalawang ng paggawa ng tumingin ito mas maliit dito,

519
00:40:16,500 --> 00:40:25,860
kaya ang return halaga ay katumbas ng puno halaga, o naglalaman ng anumang.

520
00:40:25,860 --> 00:40:28,340
>> Ito ay isang mahalagang bagay.

521
00:40:28,340 --> 00:40:30,860
Hindi ako sigurado kung sinabi niya ito tahasang sa klase,

522
00:40:30,860 --> 00:40:34,740
ngunit ito ay tinatawag na maikling-circuit pagsusuri.

523
00:40:34,740 --> 00:40:41,060
Ang ideya dito ay halaga == puno value.

524
00:40:41,060 --> 00:40:49,960
Kung iyon ay totoo, ito ay totoo, at gusto naming 'o' na sa anumang ay sa paglipas dito.

525
00:40:49,960 --> 00:40:52,520
Kaya walang kahit iniisip tungkol sa anumang ay sa paglipas dito,

526
00:40:52,520 --> 00:40:55,070
kung ano ang buong expression ng pagpunta upang bumalik?

527
00:40:55,070 --> 00:40:59,430
[Mag-aaral] True? >> Oo, dahil totoo ng anumang bagay na,

528
00:40:59,430 --> 00:41:04,990
ay kinakailangang totoo or'd - o totoo or'd may anumang.

529
00:41:04,990 --> 00:41:08,150
Ito sa lalong madaling makita namin ang return halaga = puno halaga,

530
00:41:08,150 --> 00:41:10,140
lang kami nagbabalik ng tunay.

531
00:41:10,140 --> 00:41:15,710
Hindi kahit pagpunta sa recurse karagdagang naglalaman ang linya.

532
00:41:15,710 --> 00:41:20,980
Namin sa isang hakbang karagdagang.

533
00:41:20,980 --> 00:41:29,490
Bumalik puno hindi katumbas null at lahat ng ito.

534
00:41:29,490 --> 00:41:32,650
Ginawa ito ng isang linya function na.

535
00:41:32,650 --> 00:41:36,790
Din ito ay isang halimbawa ng maikling-circuit pagsusuri.

536
00:41:36,790 --> 00:41:40,680
Ngunit ngayon ito ay ang parehong ideya -

537
00:41:40,680 --> 00:41:47,320
sa halip na - kaya kung puno hindi katumbas null - o, well,

538
00:41:47,320 --> 00:41:49,580
kung puno ang katumbas null, na ang masamang kaso,

539
00:41:49,580 --> 00:41:54,790
kung puno katumbas null, pagkatapos ang unang kondisyon ay pagpunta sa maling.

540
00:41:54,790 --> 00:42:00,550
Kaya maling anded may anumang ay pagpunta sa kung ano ang?

541
00:42:00,550 --> 00:42:04,640
[Mag-aaral] Maling. >> Oo. Ito ang iba pang kalahati ng maikling-circuit pagsusuri,

542
00:42:04,640 --> 00:42:10,710
kung saan kung ang puno ay hindi katumbas null, pagkatapos hindi namin ay pagpunta sa kahit pumunta -

543
00:42:10,710 --> 00:42:14,930
o kung puno ang katumbas null, pagkatapos hindi namin ay pagpunta sa gawin ang halaga == puno halaga.

544
00:42:14,930 --> 00:42:17,010
Lamang kami upang agad na bumalik ang maling.

545
00:42:17,010 --> 00:42:20,970
Na kung saan ay mahalaga, dahil kung ito ay hindi maikling-circuit suriin,

546
00:42:20,970 --> 00:42:25,860
pagkatapos kung puno ang katumbas null, ang ikalawang kondisyon ay pagpunta sa seg kasalanan,

547
00:42:25,860 --> 00:42:32,510
dahil ang tree-> halaga dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Kaya na na. Ito - shift sabay-sabay sa paglipas.

549
00:42:40,490 --> 00:42:44,840
Ito ay isang napaka-karaniwang bagay din, hindi ito isang linya na ito,

550
00:42:44,840 --> 00:42:49,000
ngunit sa isang karaniwang bagay sa mga kondisyon, maaaring hindi dito mismo,

551
00:42:49,000 --> 00:42:59,380
ngunit kung (puno! = null, at tree-> halaga == halaga), gawin ang anumang.

552
00:42:59,380 --> 00:43:01,560
Ito ay isang napaka-karaniwang mga kondisyon, kung saan sa halip ng pagkakaroon ng

553
00:43:01,560 --> 00:43:06,770
buksan ito sa dalawang ifs, kung saan gusto, tree null?

554
00:43:06,770 --> 00:43:11,780
Okay, hindi null, kaya ngayon tree halaga na katumbas ng halaga? Gawin ito.

555
00:43:11,780 --> 00:43:17,300
Sa halip, ang kondisyon na ito, ito ay hindi kailanman seg fault

556
00:43:17,300 --> 00:43:21,220
dahil ito ay masira kung ito ang mangyayari null.

557
00:43:21,220 --> 00:43:24,000
Well, hulaan ko kung ang iyong puno ay isang ganap na di-wastong pointer, maaari pa rin itong seg kasalanan,

558
00:43:24,000 --> 00:43:26,620
ngunit hindi ito maaaring seg kasalanan kung puno ay null.

559
00:43:26,620 --> 00:43:32,900
Kung ito ay null, masira kung bago ka kailanman dereferenced pointer sa unang lugar.

560
00:43:32,900 --> 00:43:35,000
[Mag-aaral] ba itong tinatawag na tamad na pagsusuri?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy pagsusuri ay isang hiwalay na bagay.

562
00:43:40,770 --> 00:43:49,880
Lazy pagsusuri ay higit na katulad ng magtanong para sa isang halaga,

563
00:43:49,880 --> 00:43:54,270
hihilingin sa iyo na kalkulahin ang halaga, uri ng, ngunit hindi mo na kailangan ito agad.

564
00:43:54,270 --> 00:43:59,040
Kaya hanggang sa iyong aktwal na kailangan ito, ito ay hindi sinusuri.

565
00:43:59,040 --> 00:44:03,920
Na ito ay hindi eksakto ang parehong bagay, ngunit sa Huffman pset,

566
00:44:03,920 --> 00:44:06,520
sinasabi nito na namin "lazily" magsulat.

567
00:44:06,520 --> 00:44:08,670
Ang dahilan na gawin namin na dahil aktwal kami buffering ang pagpapawalang -

568
00:44:08,670 --> 00:44:11,820
hindi namin nais na isulat ang mga indibidwal na piraso sa isang pagkakataon,

569
00:44:11,820 --> 00:44:15,450
o mga indibidwal na byte sa isang pagkakataon, gusto namin sa halip upang makakuha ng isang tipak ng mga byte.

570
00:44:15,450 --> 00:44:19,270
Pagkatapos sandaling mayroon kaming isang tipak ng mga byte, pagkatapos magpapadala kami sumulat ito.

571
00:44:19,270 --> 00:44:22,640
Kahit na, hinihiling mo ito upang magsulat - at fwrite at fread gawin ang parehong uri ng bagay.

572
00:44:22,640 --> 00:44:26,260
Sila buffer ang iyong bumabasa at nagsusulat.

573
00:44:26,260 --> 00:44:31,610
Kahit mong hilingin ito sa sumulat kaagad, marahil ito ay hindi.

574
00:44:31,610 --> 00:44:34,540
At hindi ka maaaring maging sigurado na ang mga bagay ay pagpunta sa na nakasulat

575
00:44:34,540 --> 00:44:37,540
hanggang sa tawagan ka hfclose o anumang ito ay,

576
00:44:37,540 --> 00:44:39,620
na pagkatapos sabi, okay, ako isara ang aking file,

577
00:44:39,620 --> 00:44:43,450
na nangangahulugan na Gusto ko mas mahusay na isulat ang lahat ng hindi isinulat ko pa.

578
00:44:43,450 --> 00:44:45,770
Ito ay hindi kailangang isulat ang lahat

579
00:44:45,770 --> 00:44:49,010
hanggang sa ikaw ay isara ang file, at pagkatapos ay kailangang.

580
00:44:49,010 --> 00:44:56,220
Kaya na lang kung ano ang tamad - naghihintay ito hanggang sa ito ay may mangyari.

581
00:44:56,220 --> 00:44:59,990
Ito - tumagal 51 at pupunta ka sa ito nang mas detalyado,

582
00:44:59,990 --> 00:45:05,470
dahil OCaml at lahat sa 51, ang lahat ay recursion.

583
00:45:05,470 --> 00:45:08,890
Walang mga umuulit ang mga solusyon, talaga.

584
00:45:08,890 --> 00:45:11,550
Lahat ay recursion, at tamad na pagsusuri

585
00:45:11,550 --> 00:45:14,790
ay magiging mahalaga para sa maraming mga pangyayari

586
00:45:14,790 --> 00:45:19,920
kung saan, kung hindi mo lazily suriin, na ibig sabihin -

587
00:45:19,920 --> 00:45:24,760
Ang halimbawa sa stream, na walang hanggan mahaba.

588
00:45:24,760 --> 00:45:30,990
Sa teorya, maaari mong isipin ng natural na mga numero bilang isang stream ng 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Kaya lazily sinusuri bagay ay pinong.

590
00:45:33,090 --> 00:45:37,210
Kung sabihin ko gusto ko ang ikasampung numero, maaari kong suriin up sa ikasampu numero.

591
00:45:37,210 --> 00:45:40,300
Kung gusto ko ang daan numero, pagkatapos ay maaari kong suriin hanggang sa daan bilang.

592
00:45:40,300 --> 00:45:46,290
Nang walang tamad pagsusuri, pagkatapos ito ay pagpunta sa subukan upang pag-aralan ang lahat ng mga numero agad.

593
00:45:46,290 --> 00:45:50,000
Ka pagsusuri ng walang hanggan maraming mga numero, at ito lamang ay hindi posible.

594
00:45:50,000 --> 00:45:52,080
Kaya may maraming ng mga pangyayari kung saan ang tamad pagsusuri

595
00:45:52,080 --> 00:45:57,840
ay mahalaga sa pagkuha ng mga bagay upang gumana.

596
00:45:57,840 --> 00:46:05,260
>> Ngayon gusto namin na magsulat ng insert kung saan ang insert ay magiging

597
00:46:05,260 --> 00:46:08,430
katulad pagbabago sa kahulugan.

598
00:46:08,430 --> 00:46:10,470
Kaya ngayon bool insert (int value).

599
00:46:10,470 --> 00:46:23,850
Kami ay pagpunta upang baguhin na sa bool insert (int value, node * puno).

600
00:46:23,850 --> 00:46:29,120
Aktwal kami upang baguhin na muli sa isang bit, makikita namin makita kung bakit.

601
00:46:29,120 --> 00:46:32,210
At hayaan ang ilipat ang build_node, para sa ano ba nito,

602
00:46:32,210 --> 00:46:36,730
isingit sa itaas kaya hindi namin upang magsulat ng isang function prototype.

603
00:46:36,730 --> 00:46:42,450
Na isang pahiwatig ka na gamit build_node sa insert.

604
00:46:42,450 --> 00:46:49,590
Okay. Kumuha nang isang minuto para sa.

605
00:46:49,590 --> 00:46:52,130
Tingin ko ko nai-save na ang rebisyon kung gusto mong hilahin mula sa,

606
00:46:52,130 --> 00:47:00,240
o, hindi bababa sa, ginawa ko ngayon.

607
00:47:00,240 --> 00:47:04,190
Gusto ko ang isang bahagyang break na mag-isip tungkol sa logic ng insert,

608
00:47:04,190 --> 00:47:08,750
kung hindi ka makapag-isip nito.

609
00:47:08,750 --> 00:47:12,860
Talaga, ay mo lamang kailanman ay pagpasok sa dahon.

610
00:47:12,860 --> 00:47:18,640
Tulad ng, kung isingit ko 1, pagkatapos hindi maaaring hindi ako pagpunta sa pagpasok 1 -

611
00:47:18,640 --> 00:47:21,820
Ko babaguhin ang itim - I'll-pagpasok ng 1 sa paglipas dito.

612
00:47:21,820 --> 00:47:28,070
O kung isingit ko 4, gusto kong pagpasok 4 sa paglipas dito.

613
00:47:28,070 --> 00:47:32,180
Kaya hindi mahalaga kung ano ang ginagawa mo, ka pagpunta sa pagpasok sa isang dahon.

614
00:47:32,180 --> 00:47:36,130
Ang kailangan mo lang gawin ay umulit pababa sa puno hanggang sa makuha mo sa node

615
00:47:36,130 --> 00:47:40,890
na dapat magulang ang node, magulang ang bagong node,

616
00:47:40,890 --> 00:47:44,560
at pagkatapos ay baguhin ang kaliwa o kanang pointer, depende sa kung

617
00:47:44,560 --> 00:47:47,060
ito ay mas malaki kaysa sa o mas mababa kaysa sa kasalukuyang node.

618
00:47:47,060 --> 00:47:51,180
Baguhin na pointer upang tumuro sa iyong bagong node.

619
00:47:51,180 --> 00:48:05,490
Kaya umulit pababa sa puno, gawin ang mga punto ng dahon sa bagong node.

620
00:48:05,490 --> 00:48:09,810
Din isipin ang tungkol sa kung bakit na forbids ang uri ng mga sitwasyon bago,

621
00:48:09,810 --> 00:48:17,990
kung saan binuo ko ang binary puno kung saan ito ay tama

622
00:48:17,990 --> 00:48:19,920
kung mo lamang tumingin sa isang solong node,

623
00:48:19,920 --> 00:48:24,830
ngunit 9 ay sa kaliwa ng 7 kung iterated mo ang lahat ng mga paraan.

624
00:48:24,830 --> 00:48:29,770
Sa gayon ay imposible sa sitwasyong ito, dahil -

625
00:48:29,770 --> 00:48:32,530
tingin tungkol sa pagpasok 9 o isang bagay, sa unang node,

626
00:48:32,530 --> 00:48:35,350
Ako pagpunta upang makita 7 at ako pagpunta sa pumunta sa kanan.

627
00:48:35,350 --> 00:48:38,490
Kaya hindi mahalaga kung ano ang ginagawa ko, kung ako pagpasok sa pamamagitan ng pagpunta sa isang dahon,

628
00:48:38,490 --> 00:48:40,790
at sa dahon gamit ang naaangkop na algorithm,

629
00:48:40,790 --> 00:48:43,130
ito ay magiging imposible para sa akin upang ipasok ang 9 sa kaliwa ng 7

630
00:48:43,130 --> 00:48:48,250
dahil sa lalong madaling pindutin ko ng 7 ako pagpunta sa pumunta sa kanan.

631
00:48:59,740 --> 00:49:02,070
Ba ang sinuman magkaroon ng isang bagay upang magsimula sa?

632
00:49:02,070 --> 00:49:05,480
[Mag-aaral] ko. >> Oo naman.

633
00:49:05,480 --> 00:49:09,200
[Estudyante, hindi maintindihan]

634
00:49:09,200 --> 00:49:14,390
[Iba pang mga mag-aaral, hindi maintindihan]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Ito ay pinapahalagahan. Okay. Nais upang ipaliwanag?

636
00:49:18,330 --> 00:49:20,690
>> [Mag-aaral] Dahil alam namin na namin ang pagpasok

637
00:49:20,690 --> 00:49:24,060
bagong node sa dulo ng puno,

638
00:49:24,060 --> 00:49:28,070
Looped ko sa pamamagitan ng tree iteratively

639
00:49:28,070 --> 00:49:31,360
hanggang Nakatanggap ako sa isang node na tulis sa null.

640
00:49:31,360 --> 00:49:34,220
At pagkatapos ko nagpasya upang ilagay ito sa kanang bahagi o sa kaliwang bahagi

641
00:49:34,220 --> 00:49:37,420
gamit sa karapatang ito na variable; sinabi ito sa akin kung saan upang ilagay ito.

642
00:49:37,420 --> 00:49:41,850
At pagkatapos, mahalagang, ko lang ginawa na huling -

643
00:49:41,850 --> 00:49:47,520
na punto ng Temp node sa bagong node na ito ay paglikha,

644
00:49:47,520 --> 00:49:50,770
alinman sa kaliwang bahagi o sa kanang bahagi, depende sa kung ano ang halaga ay.

645
00:49:50,770 --> 00:49:56,530
Sa wakas, ako magse-set ang bagong mga halaga ng node sa ang halaga ng mga pagsubok.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okay, kaya ko bang makita ang isang isyu dito.

647
00:49:59,550 --> 00:50:02,050
Ito ay tulad ng 95% ng paraan doon.

648
00:50:02,050 --> 00:50:07,550
Ang isang isyu na nakikita ko, well, ang sinumang iba pa makita ang isang isyu?

649
00:50:07,550 --> 00:50:18,400
Ano ang pangyayari sa ilalim kung saan masira sila ng loop?

650
00:50:18,400 --> 00:50:22,100
[Mag-aaral] Kung Temp ay null? >> Oo. Kaya kung paano mo baliin ng loop kung Temp ay null.

651
00:50:22,100 --> 00:50:30,220
Ngunit ano ang gagawin ko dito?

652
00:50:30,220 --> 00:50:35,410
Ko dereference Temp, na kung saan ay hindi maaaring hindi null.

653
00:50:35,410 --> 00:50:39,840
Kaya ang iba pang mga bagay na kailangan mong gawin ay hindi lamang subaybayan hanggang sa Temp ay null,

654
00:50:39,840 --> 00:50:45,590
na nais mong subaybayan ng magulang sa lahat ng oras.

655
00:50:45,590 --> 00:50:52,190
Gusto din namin node * magulang, hulaan ko maaari naming panatilihin na sa null sa unang.

656
00:50:52,190 --> 00:50:55,480
Ito ay kakaiba pag-uugali para sa ugat ng puno,

657
00:50:55,480 --> 00:50:59,210
ngunit gagamitin namin iyon.

658
00:50:59,210 --> 00:51:03,950
Kung ang halaga ay mas malaki kaysa sa anumang, pagkatapos Temp = Temp karapatan.

659
00:51:03,950 --> 00:51:07,910
Ngunit bago mo ito gawin namin na, magulang = Temp.

660
00:51:07,910 --> 00:51:14,500
O mga magulang na palaging pagpunta sa pantay na Temp? Ay na ang kaso?

661
00:51:14,500 --> 00:51:19,560
Kung Temp ay hindi null, pagkatapos ay ako pagpunta upang ilipat pababa, kahit na ano,

662
00:51:19,560 --> 00:51:24,030
sa isang node kung saan ang Temp ng magulang.

663
00:51:24,030 --> 00:51:27,500
Kaya magulang ang nangyayari na ang Temp, at pagkatapos ay ilipat ko Temp pababa.

664
00:51:27,500 --> 00:51:32,410
Ngayon Temp ay null, ngunit ang mga magulang ng mga puntos sa ang magulang ng bagay na null.

665
00:51:32,410 --> 00:51:39,110
Kaya down na dito, hindi ko nais upang i-set sa katumbas ng 1.

666
00:51:39,110 --> 00:51:41,300
Kaya ko inilipat sa kanan, kaya kung kanan = 1,

667
00:51:41,300 --> 00:51:45,130
at hulaan ko gusto mo ring gawin -

668
00:51:45,130 --> 00:51:48,530
kung ilipat mo sa kaliwa, nais mong i-set sa katumbas ng 0.

669
00:51:48,530 --> 00:51:55,950
O tao kung sakaling ilipat sa kanan.

670
00:51:55,950 --> 00:51:58,590
Kaya kanan = 0. Kung ito ay tama = 1,

671
00:51:58,590 --> 00:52:04,260
ngayon ay nais namin ang magulang na karapatan pointer newnode,

672
00:52:04,260 --> 00:52:08,520
tao gusto naming magulang kaliwa newnode pointer.

673
00:52:08,520 --> 00:52:16,850
Mga tanong sa na?

674
00:52:16,850 --> 00:52:24,880
Okay. Kaya ito ay ang paraan namin - na rin, aktwal na, sa halip ng paggawa nito,

675
00:52:24,880 --> 00:52:29,630
namin kalahati inaasahan mong gamitin build_node.

676
00:52:29,630 --> 00:52:40,450
At pagkatapos ay kung newnode katumbas null, bumalik false.

677
00:52:40,450 --> 00:52:44,170
Na iyon. Ngayon, ito ay kung ano ang aming inaasahan mong gawin.

678
00:52:44,170 --> 00:52:47,690
>> Ito ay kung ano ang mga kawani solusyon gawin.

679
00:52:47,690 --> 00:52:52,360
Hindi sumasang-ayon ako na ito bilang ang "karapatan" na paraan ng pagpunta tungkol dito

680
00:52:52,360 --> 00:52:57,820
ngunit ito ay perpektong pinong at ito gumagana.

681
00:52:57,820 --> 00:53:02,840
Isang bagay na isang maliit na kakaiba na ngayon ay

682
00:53:02,840 --> 00:53:08,310
kung puno ay nagsisimula off bilang null, kami ay pumasa sa isang null puno.

683
00:53:08,310 --> 00:53:12,650
Hulaan ko ito ay depende sa kung paano mo tukuyin ang pag-uugali ng pagpasa sa isang null puno.

684
00:53:12,650 --> 00:53:15,490
Gusto ko isipin na kung pumasa ka sa isang null puno,

685
00:53:15,490 --> 00:53:17,520
pagkatapos pagpasok ng halaga sa isang null puno

686
00:53:17,520 --> 00:53:23,030
dapat lamang na ibalik ang isang puno kung saan ang tanging halaga ay ang solong node.

687
00:53:23,030 --> 00:53:25,830
Mga tao sumasang-ayon sa na? Maaari mong, kung gusto mo,

688
00:53:25,830 --> 00:53:28,050
kung pumasa ka sa isang null puno

689
00:53:28,050 --> 00:53:31,320
at gusto mong magpasok ng isang halaga sa ito, bumalik false.

690
00:53:31,320 --> 00:53:33,830
Ito ay hanggang sa iyo upang tukuyin iyon.

691
00:53:33,830 --> 00:53:38,320
Upang gawin ang unang bagay na sinabi ko at pagkatapos -

692
00:53:38,320 --> 00:53:40,720
maayos, ikaw ay pagpunta sa may problema sa paggawa na, dahil

693
00:53:40,720 --> 00:53:44,090
magiging mas madali kung nagkaroon kami ng pandaigdigang pointer sa bagay,

694
00:53:44,090 --> 00:53:48,570
ngunit hindi namin, kaya kung puno ay null, mayroong walang maaari naming gawin tungkol na.

695
00:53:48,570 --> 00:53:50,960
Maaari lang namin bumalik false.

696
00:53:50,960 --> 00:53:52,840
Kaya ako pagpunta sa baguhin ang insert.

697
00:53:52,840 --> 00:53:56,540
Namin technically ay maaaring baguhin lamang ito dito mismo,

698
00:53:56,540 --> 00:53:58,400
kung paano ito iterating sa paglipas ng mga bagay,

699
00:53:58,400 --> 00:54:04,530
ngunit ako pagpunta upang baguhin ang insert tumagal ng isang node ** puno.

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

701
00:54:07,510 --> 00:54:09,710
Ano ang ibig sabihin nito?

702
00:54:09,710 --> 00:54:12,330
Sa halip ng pagharap sa mga payo sa node,

703
00:54:12,330 --> 00:54:16,690
ang bagay na ako pupunta na manipulating ang pointer na ito.

704
00:54:16,690 --> 00:54:18,790
Ako pagpunta sa manipulating ito pointer.

705
00:54:18,790 --> 00:54:21,770
Ako pagpunta sa manipulating payo nang direkta.

706
00:54:21,770 --> 00:54:25,760
Ito ay gumagawa ng kahulugan dahil, isipin ang tungkol pababa -

707
00:54:25,760 --> 00:54:33,340
na rin, ngayon ang puntos na ito sa null.

708
00:54:33,340 --> 00:54:38,130
Kung ano ang nais kong gawin ay manipulahin ang pointer upang ituro na hindi null.

709
00:54:38,130 --> 00:54:40,970
Gusto ko ito upang tumuro sa aking bagong node.

710
00:54:40,970 --> 00:54:44,870
Kung ko lang subaybayan ng mga payo sa aking mga payo,

711
00:54:44,870 --> 00:54:47,840
hindi ko kailangan upang subaybayan ng isang pointer ng magulang.

712
00:54:47,840 --> 00:54:52,640
Maaari ko lang subaybayan upang makita kung ang pointer ay tumuturo sa null,

713
00:54:52,640 --> 00:54:54,580
at kung ang pointer ang ay tumuturo sa null,

714
00:54:54,580 --> 00:54:57,370
baguhin ito upang tumuro sa node na gusto ko.

715
00:54:57,370 --> 00:55:00,070
At maaari ba akong baguhin ito dahil mayroon akong isang pointer sa pointer.

716
00:55:00,070 --> 00:55:02,040
Natin makita sa karapatang ito ngayon.

717
00:55:02,040 --> 00:55:05,470
Maaari mong aktwal na gawin ito recursively medyo madali.

718
00:55:05,470 --> 00:55:08,080
Namin nais upang gawin iyon?

719
00:55:08,080 --> 00:55:10,980
Oo, gawin namin.

720
00:55:10,980 --> 00:55:16,790
>> Natin makita ito recursively.

721
00:55:16,790 --> 00:55:24,070
Una, kung ano ang aming base kaso magiging?

722
00:55:24,070 --> 00:55:29,140
Halos palaging aming base kaso; pero sa totoo, ito uri ng nakakalito.

723
00:55:29,140 --> 00:55:34,370
Unang bagay unang, kung (puno == null)

724
00:55:34,370 --> 00:55:37,550
Hulaan ko lang kami upang bumalik false.

725
00:55:37,550 --> 00:55:40,460
Ito ay naiiba mula sa iyong puno pagiging null.

726
00:55:40,460 --> 00:55:44,510
Ito ang pointer sa iyong root pointer pagiging null

727
00:55:44,510 --> 00:55:48,360
na nangangahulugan na ang iyong root pointer ay hindi umiiral.

728
00:55:48,360 --> 00:55:52,390
Kaya pababa dito, kung gawin ko

729
00:55:52,390 --> 00:55:55,760
node * - sabihin lamang muling gamitin ito.

730
00:55:55,760 --> 00:55:58,960
Node * ugat = null,

731
00:55:58,960 --> 00:56:00,730
at pagkatapos ay ako pagpunta upang tawagan ang insert sa pamamagitan ng paggawa ng isang bagay tulad ng,

732
00:56:00,730 --> 00:56:04,540
isingit ang 4 sa & ugat.

733
00:56:04,540 --> 00:56:06,560
Kaya at ugat, kung ang ugat ay isang node *

734
00:56:06,560 --> 00:56:11,170
at ugat ay pagpunta sa isang node **.

735
00:56:11,170 --> 00:56:15,120
Ito ay wasto. Sa kasong ito, puno, hanggang dito,

736
00:56:15,120 --> 00:56:20,120
puno ay hindi null - o insert.

737
00:56:20,120 --> 00:56:24,630
Dito. Tree ay null Hindi; * puno null, na fine

738
00:56:24,630 --> 00:56:26,680
dahil kung ang * puno ay null, pagkatapos ko manipulahin ito

739
00:56:26,680 --> 00:56:29,210
sa ngayon na tumuturo sa kung ano ang gusto ko ito upang tumuro sa.

740
00:56:29,210 --> 00:56:34,750
Ngunit kung ang puno ay null, ibig sabihin ko lang bumaba dito at sinabi null.

741
00:56:34,750 --> 00:56:42,710
Na hindi magkaroon ng kahulugan. Hindi ko maaaring gawin na iyon.

742
00:56:42,710 --> 00:56:45,540
Kung ang puno ay null, bumalik false.

743
00:56:45,540 --> 00:56:48,220
Kaya ko talaga na sinabi kung ano ang aming real base kaso.

744
00:56:48,220 --> 00:56:50,580
At kung ano ang na magiging?

745
00:56:50,580 --> 00:56:55,030
[Estudyante, hindi maintindihan]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Oo. Kaya kung (* puno == null).

747
00:57:00,000 --> 00:57:04,520
Ito ay nauugnay sa ang kaso sa dito

748
00:57:04,520 --> 00:57:09,640
kung saan kung ang aking pulang pointer ang pointer ako nakatuon sa,

749
00:57:09,640 --> 00:57:12,960
kaya tulad ako nakatutok sa pointer na ito, ngayon ako nakatutok sa pointer na ito.

750
00:57:12,960 --> 00:57:15,150
Ngayon ako nakatutok sa pointer na ito.

751
00:57:15,150 --> 00:57:18,160
Kaya kung ang aking pulang pointer, na ang aking node **,

752
00:57:18,160 --> 00:57:22,880
ay kailanman - kung *, ang aking pulang pointer, kailanman null,

753
00:57:22,880 --> 00:57:28,470
na nangangahulugan na ako sa kaso na kung saan ako tumututok sa isang pointer na mga puntos -

754
00:57:28,470 --> 00:57:32,530
ito ay isang pointer na nabibilang sa isang dahon.

755
00:57:32,530 --> 00:57:41,090
Gusto kong baguhin ang pointer na ito upang tumuro sa aking bagong node.

756
00:57:41,090 --> 00:57:45,230
Bumalik sa paglipas dito.

757
00:57:45,230 --> 00:57:56,490
Aking newnode lamang node * n = build_node (halaga)

758
00:57:56,490 --> 00:58:07,300
pagkatapos n, kung n = null, bumalik ang maling.

759
00:58:07,300 --> 00:58:12,600
Iba Pa nais namin upang baguhin kung ano ang pointer ay kasalukuyang tumuturo sa

760
00:58:12,600 --> 00:58:17,830
sa ngayon na ituro sa aming bagong binuo node.

761
00:58:17,830 --> 00:58:20,280
Maaari naming talagang gawin iyon dito.

762
00:58:20,280 --> 00:58:30,660
Sa halip na sinasabi n, sinasabi namin * puno = kung * puno.

763
00:58:30,660 --> 00:58:35,450
Ang bawat tao'y maunawaan na? Na sa pamamagitan ng pagharap sa mga payo sa payo,

764
00:58:35,450 --> 00:58:40,750
Maaari naming baguhin ang null pointer upang tumuro sa mga bagay na gusto naming ang mga ito upang tumuro sa.

765
00:58:40,750 --> 00:58:42,820
Na aming base kaso.

766
00:58:42,820 --> 00:58:45,740
>> Ngayon ang aming pag-ulit, o sa aming recursion,

767
00:58:45,740 --> 00:58:51,430
ay na halos kapareho sa lahat ng iba pang mga recursions namin ang ginagawa.

768
00:58:51,430 --> 00:58:55,830
Kami ay pagpunta sa nais upang ipasok ang halaga,

769
00:58:55,830 --> 00:58:59,040
at ngayon ako pagpunta sa gamitin ang tatluhan muli, ngunit kung ano ang aming kalagayan upang maging?

770
00:58:59,040 --> 00:59:05,180
Ano ang iyong hinahanap namin upang magpasya kung nais namin upang pumunta kaliwa o kanan?

771
00:59:05,180 --> 00:59:07,760
Natin gawin ito sa hiwalay na mga hakbang.

772
00:59:07,760 --> 00:59:18,850
Kung (halaga <) ano?

773
00:59:18,850 --> 00:59:23,200
[Mag-aaral] Ang halagang puno?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Kaya tandaan na ako ay kasalukuyang -

775
00:59:27,490 --> 00:59:31,260
[Mga mag-aaral, hindi maintindihan]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Oo, kaya dito mismo, sabihin nating na berdeng arrow na ito

777
00:59:34,140 --> 00:59:39,050
ay isang halimbawa ng kung ano ang puno kasalukuyang, ay isang pointer na ito pointer.

778
00:59:39,050 --> 00:59:46,610
Sa gayon ay nangangahulugan na Ako ay isang pointer sa isang pointer sa 3.

779
00:59:46,610 --> 00:59:48,800
Dereference ang nang dalawang beses tunog magandang.

780
00:59:48,800 --> 00:59:51,010
Ano ang gagawin ko - paano ko na?

781
00:59:51,010 --> 00:59:53,210
[Mag-aaral] Dereference isang beses, at pagkatapos ay gawin ang arrow na paraan?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Kaya (* tree) sabay-sabay ang dereference, -> halaga

783
00:59:58,420 --> 01:00:05,960
pagpunta sa ninyo akong bigyan ng halaga ng node na hindi direktang ako na tumuturo sa.

784
01:00:05,960 --> 01:00:11,980
Kaya ko ring sumulat ang mga ito ** tree.value kung gusto mo na.

785
01:00:11,980 --> 01:00:18,490
Alinman sa gumagana.

786
01:00:18,490 --> 01:00:26,190
Kung iyon ang kaso, pagkatapos ay gusto kong tumawag isingit na may halaga.

787
01:00:26,190 --> 01:00:32,590
At kung ano ang aking-update node ** magiging?

788
01:00:32,590 --> 01:00:39,440
Gusto kong pumunta sa kaliwa, kaya ** tree.left pagpunta sa aking kaliwa.

789
01:00:39,440 --> 01:00:41,900
At gusto ko ang pointer sa bagay na iyon

790
01:00:41,900 --> 01:00:44,930
upang kung ang kaliwa ang nagtatapos up null pointer,

791
01:00:44,930 --> 01:00:48,360
Maaari kong baguhin ito upang tumuro sa aking bagong node.

792
01:00:48,360 --> 01:00:51,460
>> At sa iba pang mga kaso ay maaaring maging katulad na katulad.

793
01:00:51,460 --> 01:00:55,600
Natin gumawa ng aktwal na ang aking tatluhan ngayon.

794
01:00:55,600 --> 01:01:04,480
Ipasok ang halaga ng kung halaga <(** tree). Halaga.

795
01:01:04,480 --> 01:01:11,040
Pagkatapos nais naming upang i-update ang aming mga ** sa kaliwa,

796
01:01:11,040 --> 01:01:17,030
tao gusto naming upang i-update ang aming mga ** sa kanan.

797
01:01:17,030 --> 01:01:22,540
[Mag-aaral] ba na makuha ang pointer sa pointer?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Tandaan na - ** ang tree.right ay isang node star.

799
01:01:30,940 --> 01:01:35,040
[Mag-aaral, hindi maintindihan] >> Oo.

800
01:01:35,040 --> 01:01:41,140
** Tree.right tulad nito pointer o isang bagay.

801
01:01:41,140 --> 01:01:45,140
Kaya sa pamamagitan ng pagkuha ng isang pointer iyon, na nagbibigay sa akin kung ano ang gusto kong

802
01:01:45,140 --> 01:01:50,090
ng pointer na tao.

803
01:01:50,090 --> 01:01:54,260
[Mag-aaral] ma kami muli kung bakit kami ay gumagamit ng dalawang mga payo?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Oo. Kaya - walang, maaari mo, at na solusyon bago

805
01:01:58,220 --> 01:02:04,540
ay isang paraan na gawin ito nang hindi ginagawa ng dalawang payo.

806
01:02:04,540 --> 01:02:08,740
Kailangan mo upang maunawaan gamit ang dalawang payo,

807
01:02:08,740 --> 01:02:11,660
at ito ay isang mas malinis na solusyon.

808
01:02:11,660 --> 01:02:16,090
Gayundin, mapapansin na, kung ano ang mangyayari kung ang aking puno -

809
01:02:16,090 --> 01:02:24,480
kung ano ang mangyayari kung ang aking mga ugat ay null? Ano ang mangyayari kung gawin ko ito kaso dito mismo?

810
01:02:24,480 --> 01:02:30,540
Kaya node * ugat = null, ipasok 4 sa & ugat.

811
01:02:30,540 --> 01:02:35,110
Ano ang ugat matapos ang?

812
01:02:35,110 --> 01:02:37,470
[Mag-aaral, hindi maintindihan] >> Oo.

813
01:02:37,470 --> 01:02:41,710
Root halaga na 4.

814
01:02:41,710 --> 01:02:45,510
Root kaliwa null, ugat karapatan ay null.

815
01:02:45,510 --> 01:02:49,490
Sa kaso kung saan hindi namin ay pumasa root ayon sa address,

816
01:02:49,490 --> 01:02:52,490
hindi namin maaaring baguhin ang ugat.

817
01:02:52,490 --> 01:02:56,020
Sa kaso kung saan ang tree - kung saan ugat ay null,

818
01:02:56,020 --> 01:02:58,410
lamang namin ay may upang bumalik false. May walang kami.

819
01:02:58,410 --> 01:03:01,520
Hindi namin maaaring magpasok ng isang node sa isang walang laman na puno.

820
01:03:01,520 --> 01:03:06,810
Ngunit ngayon ng aming makakaya; lang namin gumawa ng isang walang laman na puno sa isang one-node puno.

821
01:03:06,810 --> 01:03:13,400
Na kung saan ay karaniwang inaasahang paraan na ito ay dapat na gumana.

822
01:03:13,400 --> 01:03:21,610
>> Bukod dito, ito ay makabuluhang mas maikli sa

823
01:03:21,610 --> 01:03:26,240
pinapanatili pagsubaybay ng magulang, at kaya umulit ang lahat ng mga paraan.

824
01:03:26,240 --> 01:03:30,140
Ngayon ko ang aking mga magulang, at ko na lang ay ang aking pointer ng karapatan ng magulang sa anumang.

825
01:03:30,140 --> 01:03:35,640
Sa halip, kung ginawa namin ito iteratively, ito ay ang parehong ideya na may isang habang loop.

826
01:03:35,640 --> 01:03:38,100
Ngunit sa halip na humarap sa aking magulang pointer,

827
01:03:38,100 --> 01:03:40,600
sa halip ang aking kasalukuyang pointer ay ang bagay

828
01:03:40,600 --> 01:03:43,790
na direktang ako pagbabago upang tumuro sa aking bagong node.

829
01:03:43,790 --> 01:03:46,090
Hindi ako humarap sa kung ito ay nakaturo sa kaliwa.

830
01:03:46,090 --> 01:03:48,810
Hindi ako humarap sa kung ito ay na nakaturo sa kanan.

831
01:03:48,810 --> 01:04:00,860
Lang anumang pointer na ito, ako pagpunta sa itakda ito upang tumuro sa aking bagong node.

832
01:04:00,860 --> 01:04:05,740
Ang bawat tao'y maunawaan kung paano ito gumagana?

833
01:04:05,740 --> 01:04:09,460
Kung hindi bakit gusto naming gawin ito sa ganitong paraan,

834
01:04:09,460 --> 01:04:14,920
ngunit hindi bababa sa na ito gumagana bilang isang solusyon?

835
01:04:14,920 --> 01:04:17,110
[Mag-aaral] Saan kami nagbabalik ng tunay?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Iyon ay marahil dito mismo.

837
01:04:21,550 --> 01:04:26,690
Kung tama namin ipasok ito, nagbabalik ng tunay.

838
01:04:26,690 --> 01:04:32,010
Iba Pa, pababa dito kami ay pagpunta sa nais upang bumalik anumang mga babalik insert.

839
01:04:32,010 --> 01:04:35,950
>> At kung ano ang mga espesyal na tungkol ito recursive function na?

840
01:04:35,950 --> 01:04:43,010
Buntot recursive, kaya hangga't namin makatipon may ilang optimization,

841
01:04:43,010 --> 01:04:48,060
ito kinikilala mo na at hindi mo na makakuha ng isang stack overflow mula sa,

842
01:04:48,060 --> 01:04:53,230
kahit na kung ang aming puno ay may taas ng 10,000 o 10 milyong.

843
01:04:53,230 --> 01:04:55,630
[Estudyante, hindi maintindihan]

844
01:04:55,630 --> 01:05:00,310
[Bowden] sa tingin ko ito ginagawa ito sa Dash - o kung ano-optimize antas

845
01:05:00,310 --> 01:05:03,820
ay kinakailangan para sa isang buntot recursion na makikilala.

846
01:05:03,820 --> 01:05:09,350
Tingin ko ito kinikilala - GCC at kumalatong

847
01:05:09,350 --> 01:05:12,610
din ng iba't ibang mga kahulugan para sa kanilang mga antas ng pag-optimize.

848
01:05:12,610 --> 01:05:17,870
Gusto kong sabihin ito DashO 2, para sigurado na makilala ang buntot recursion.

849
01:05:17,870 --> 01:05:27,880
Ngunit hindi namin - maaari kang bumuo ng tulad ng isang halimbawa ng Fibonocci o isang bagay.

850
01:05:27,880 --> 01:05:30,030
Hindi madaling subukan na ito, dahil ito ay mahirap upang makabuo

851
01:05:30,030 --> 01:05:32,600
isang binary puno na kaya malaki.

852
01:05:32,600 --> 01:05:37,140
Ngunit oo, tingin ko ito DashO 2, na

853
01:05:37,140 --> 01:05:40,580
kung ikaw makatipon may DashO 2, hanapin buntot recursion

854
01:05:40,580 --> 01:05:54,030
at i-optimize na out.

855
01:05:54,030 --> 01:05:58,190
Natin bumalik sa - magpasok ng literal ang huling bagay na kailangan nito.

856
01:05:58,190 --> 01:06:04,900
Sabihin bumalik sa insert sa paglipas dito

857
01:06:04,900 --> 01:06:07,840
kung saan kami ay pagpunta sa gawin ang parehong ideya.

858
01:06:07,840 --> 01:06:14,340
Pa rin ito ng kasiraan ng hindi ganap na pangasiwaan ang

859
01:06:14,340 --> 01:06:17,940
kapag ang root mismo null, o sa nakalipas na entry ay null,

860
01:06:17,940 --> 01:06:20,060
ngunit sa halip ng pagharap sa isang pointer magulang,

861
01:06:20,060 --> 01:06:27,430
sabihin ilapat ang parehong lohika ng pagpapanatiling pointer sa mga payo.

862
01:06:27,430 --> 01:06:35,580
Kung dito namin panatilihin ang aming node ** kuprum,

863
01:06:35,580 --> 01:06:37,860
at hindi namin kailangan upang subaybayan ang mga ito mismo,

864
01:06:37,860 --> 01:06:47,190
ngunit node ** kuprum = & tree.

865
01:06:47,190 --> 01:06:54,800
At ngayon ang aming habang loop ay na habang ang * kuprum hindi katumbas null.

866
01:06:54,800 --> 01:07:00,270
Huwag kailangang subaybayan ng mga magulang.

867
01:07:00,270 --> 01:07:04,180
Huwag kailangan upang subaybayan ang mga kaliwa at kanang.

868
01:07:04,180 --> 01:07:10,190
At makikita ko tumawag ito Temp, dahil na namin ginagamit Temp.

869
01:07:10,190 --> 01:07:17,200
Okay. Kaya kung (halaga> * Temp),

870
01:07:17,200 --> 01:07:24,010
pagkatapos & (* Temp) -> kanan

871
01:07:24,010 --> 01:07:29,250
tao Temp = & (* Temp) -> pakaliwa.

872
01:07:29,250 --> 01:07:32,730
At ngayon, sa puntong ito, pagkatapos ito loop habang,

873
01:07:32,730 --> 01:07:36,380
Ko lang gawin ito dahil maaaring ito madaling mag-isip tungkol sa iteratively kaysa recursively,

874
01:07:36,380 --> 01:07:39,010
ngunit pagkatapos na ito habang loop,

875
01:07:39,010 --> 01:07:43,820
* Temp ang pointer na gusto naming baguhin.

876
01:07:43,820 --> 01:07:48,960
>> Bago nagkaroon kami ng magulang, at gusto naming baguhin ang alinman sa kaliwa ng magulang o karapatan ng magulang,

877
01:07:48,960 --> 01:07:51,310
ngunit kung gusto naming palitan ang karapatan ng magulang,

878
01:07:51,310 --> 01:07:54,550
* Temp ang karapatan ng magulang, at maaari naming baguhin ang mga ito nang direkta.

879
01:07:54,550 --> 01:08:05,860
Kaya pababa dito, maaari naming gawin * Temp = newnode, at na ito.

880
01:08:05,860 --> 01:08:09,540
Kaya notice, ang lahat ng ginawa namin sa ay kumuha ng linya ng code.

881
01:08:09,540 --> 01:08:14,770
Upang subaybayan ng mga magulang sa lahat na ang karagdagang mga pagsusumikap.

882
01:08:14,770 --> 01:08:18,689
Dito, kung lamang namin subaybayan ng pointer sa pointer,

883
01:08:18,689 --> 01:08:22,990
at kahit na gusto namin upang makakuha ng mapupuksa ng lahat ng mga kulot tirante ngayon,

884
01:08:22,990 --> 01:08:27,170
hitsura nito ay magiging mas maikli.

885
01:08:27,170 --> 01:08:32,529
Ito ngayon ay ang eksaktong parehong solusyon,

886
01:08:32,529 --> 01:08:38,210
ngunit mas kaunting mga linya ng code.

887
01:08:38,210 --> 01:08:41,229
Sa sandaling simulan mo ang pagkilala ito bilang isang wastong solusyon,

888
01:08:41,229 --> 01:08:43,529
ring madali sa dahilan tungkol kaysa tulad, okay,

889
01:08:43,529 --> 01:08:45,779
kung bakit ko ito bandila sa int karapatan?

890
01:08:45,779 --> 01:08:49,290
Ano ang na ibig sabihin nito? Oh, ito signifying na

891
01:08:49,290 --> 01:08:51,370
tuwing pumupunta ako sa kanan, kailangan ko upang i-set ang mga ito,

892
01:08:51,370 --> 01:08:53,819
tao kung pumunta ako sa kaliwa kailangan ko upang i-set ito sa zero.

893
01:08:53,819 --> 01:09:04,060
Dito, hindi ko kailangang dahilan tungkol na, lang madali upang isipin ang tungkol.

894
01:09:04,060 --> 01:09:06,710
Mga tanong?

895
01:09:06,710 --> 01:09:16,290
[Mag-aaral, hindi maintindihan] >> Oo.

896
01:09:16,290 --> 01:09:23,359
Okay, kaya sa huling sandali -

897
01:09:23,359 --> 01:09:28,080
Ako hulaan ang isang mabilis at madaling function na maaari naming gawin ay,

898
01:09:28,080 --> 01:09:34,910
let's - magkasama, hulaan ko, subukan at magsulat ng mga naglalaman ng function na

899
01:09:34,910 --> 01:09:38,899
na hindi pakialam kung ito ay isang binary puno ng paghahanap.

900
01:09:38,899 --> 01:09:43,770
Ito ay naglalaman ng function na ay dapat bumalik totoo

901
01:09:43,770 --> 01:09:58,330
kung saanman sa pangkalahatang puno ng binary ay ang halaga na kaming naghahanap ng mga.

902
01:09:58,330 --> 01:10:02,520
Kaya sabihin muna gawin ito recursively at pagkatapos ay namin gawin ito iteratively.

903
01:10:02,520 --> 01:10:07,300
Maaari naming aktwal lamang gawin ito nang magkasama, dahil ito ay talagang maikling.

904
01:10:07,300 --> 01:10:11,510
>> Ano ang aking base kaso pagpunta na?

905
01:10:11,510 --> 01:10:13,890
[Estudyante, hindi maintindihan]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Kaya kung (puno == null), pagkatapos ay kung ano?

907
01:10:18,230 --> 01:10:22,740
[Mag-aaral] Bumalik maling.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Iba Pa, well, hindi ko kailangan ang pang tao.

909
01:10:26,160 --> 01:10:30,250
Kung aking iba pang mga kaso base.

910
01:10:30,250 --> 01:10:32,450
[Mag-aaral] Tree ng halaga? >> Oo.

911
01:10:32,450 --> 01:10:36,430
Kaya kung (tree-> halaga == halaga.

912
01:10:36,430 --> 01:10:39,920
Mapansin kami pabalik sa node *, hindi node ** s?

913
01:10:39,920 --> 01:10:42,990
Ay naglalaman ng hindi kailanman kailangang gumamit ng node **,

914
01:10:42,990 --> 01:10:45,480
dahil hindi namin ang pagbabago ng mga payo.

915
01:10:45,480 --> 01:10:50,540
Lang kami traversing kanila.

916
01:10:50,540 --> 01:10:53,830
Kung nangyari iyon, gusto naming nagbabalik ng tunay.

917
01:10:53,830 --> 01:10:58,270
Iba Pa nais naming sa pagbagtas sa mga bata.

918
01:10:58,270 --> 01:11:02,620
Kaya hindi namin maaaring dahilan tungkol sa kung ang lahat sa kaliwa ay mas

919
01:11:02,620 --> 01:11:05,390
at lahat sa kanan ay mas malaki.

920
01:11:05,390 --> 01:11:09,590
Kaya ano ang aming kundisyon na dito - o, kung ano ang namin gawin?

921
01:11:09,590 --> 01:11:11,840
[Mag-aaral, hindi maintindihan] >> Oo.

922
01:11:11,840 --> 01:11:17,400
Bumalik naglalaman (halaga, puno-> kaliwa)

923
01:11:17,400 --> 01:11:26,860
o naglalaman ng (halaga, puno-> kanan). At na ito.

924
01:11:26,860 --> 01:11:29,080
At mapansin may ilang maiikling circuit pagsusuri,

925
01:11:29,080 --> 01:11:32,520
kung saan kung mangyari namin upang mahanap ang halaga sa kaliwang puno,

926
01:11:32,520 --> 01:11:36,820
hindi namin kailangan upang tumingin sa kanang puno.

927
01:11:36,820 --> 01:11:40,430
Iyon ang buong function na.

928
01:11:40,430 --> 01:11:43,690
Ngayon sabihin gawin ito iteratively,

929
01:11:43,690 --> 01:11:48,060
na na mas magaling.

930
01:11:48,060 --> 01:11:54,750
Kukunin namin ang karaniwang simula ng node * kuprum = puno.

931
01:11:54,750 --> 01:12:03,250
Habang (kuprum! = Null).

932
01:12:03,250 --> 01:12:08,600
Mabilis na pagpunta upang makita ang isang problema.

933
01:12:08,600 --> 01:12:12,250
Kung kuprum - dito, kung namin kailanman masira ito,

934
01:12:12,250 --> 01:12:16,020
pagkatapos kami maubusan ng mga bagay upang tumingin sa, kaya bumalik false.

935
01:12:16,020 --> 01:12:24,810
Kung (kuprum-> halaga == halaga), nagbabalik ng tunay.

936
01:12:24,810 --> 01:12:32,910
Sa ngayon, hindi namin sa isang lugar -

937
01:12:32,910 --> 01:12:36,250
hindi namin alam kung gusto namin upang pumunta pakaliwa o pakanan.

938
01:12:36,250 --> 01:12:44,590
Sa mang, sabihin pumunta lamang sa kaliwa.

939
01:12:44,590 --> 01:12:47,910
Malinaw naman ako ay tumatakbo sa isang isyu kung saan ganap ko ang inabandunang lahat -

940
01:12:47,910 --> 01:12:50,760
Ako lamang kailanman suriin ang kaliwang bahagi ng isang puno.

941
01:12:50,760 --> 01:12:56,050
Hindi ko lagyan ng anumang bagay na kanang bata ng anumang bagay na.

942
01:12:56,050 --> 01:13:00,910
Paano ko ito aayusin?

943
01:13:00,910 --> 01:13:05,260
[Mag-aaral] Mayroon kang upang subaybayan ang kaliwa at kanang sa isang stack.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Oo. Kaya sabihin gawin itong

945
01:13:13,710 --> 01:13:32,360
struct listahan, node * n, at pagkatapos node ** susunod?

946
01:13:32,360 --> 01:13:40,240
Tingin ko na gumagana fine.

947
01:13:40,240 --> 01:13:45,940
Gusto naming upang pumunta sa kaliwa, o let's - up dito.

948
01:13:45,940 --> 01:13:54,350
Struct listahan = listahan, ito ay simulan

949
01:13:54,350 --> 01:13:58,170
sa struct listahan na ito.

950
01:13:58,170 --> 01:14:04,040
* Listahan = null. Kaya na na ang aming naka-link na listahan

951
01:14:04,040 --> 01:14:08,430
ng mga subtrees na namin nilaktawan sa paglipas ng.

952
01:14:08,430 --> 01:14:13,800
Kami ay pagpunta sa pagbagtas sa kaliwa ngayon,

953
01:14:13,800 --> 01:14:17,870
ngunit dahil hindi maaaring hindi namin kailangan upang bumalik sa kanan,

954
01:14:17,870 --> 01:14:26,140
Kami ay pagpunta upang panatilihin ang kanang bahagi sa loob ng aming mga listahan ng struct.

955
01:14:26,140 --> 01:14:32,620
Pagkatapos ay kakailanganin naming new_list o struct,

956
01:14:32,620 --> 01:14:41,080
struct listahan *, new_list = malloc (sizeof (listahan)).

957
01:14:41,080 --> 01:14:44,920
Pupunta ako upang balewalain ang error-check na, ngunit dapat mong suriin upang makita kung ito ay null.

958
01:14:44,920 --> 01:14:50,540
New_list ang node na ito upang tumuro sa -

959
01:14:50,540 --> 01:14:56,890
oh, na kung bakit gusto ko ito dito. Ito ay upang tumuro sa isang pangalawang listahan ng struct.

960
01:14:56,890 --> 01:15:02,380
Iyon lang kung paano link ang listahan ng trabaho.

961
01:15:02,380 --> 01:15:04,810
Ito ay ang parehong bilang isang int link na listahan

962
01:15:04,810 --> 01:15:06,960
maliban lang kami pinapalitan int node *.

963
01:15:06,960 --> 01:15:11,040
Ito ay eksakto ang parehong.

964
01:15:11,040 --> 01:15:15,100
Kaya new_list, ang halaga ng aming new_list node,

965
01:15:15,100 --> 01:15:19,120
ay na kuprum-> kanan.

966
01:15:19,120 --> 01:15:24,280
Ang halaga ng aming new_list-> susunod na ang aming orihinal na listahan,

967
01:15:24,280 --> 01:15:30,760
at pagkatapos kami ay i-update ang aming listahan upang tumuro sa new_list.

968
01:15:30,760 --> 01:15:33,650
>> Ngayon kailangan namin ng ilang uri ng paraan ng paghila bagay,

969
01:15:33,650 --> 01:15:37,020
tulad namin na traversed ang buong kaliwang subtree.

970
01:15:37,020 --> 01:15:40,480
Ngayon ay kailangan namin upang hilahin ang mga bagay nito,

971
01:15:40,480 --> 01:15:43,850
tulad kuprum null, hindi namin nais na lamang bumalik sa maling.

972
01:15:43,850 --> 01:15:50,370
Gusto naming ngayon hilahin labas sa aming bagong listahan.

973
01:15:50,370 --> 01:15:53,690
Isang maginhawang paraan ng paggawa nito - maayos, aktwal na, may maramihang mga paraan ng paggawa nito.

974
01:15:53,690 --> 01:15:56,680
Sinuman ay isang mungkahi?

975
01:15:56,680 --> 01:15:58,790
Saan ko dapat gawin ito o kung paano dapat kong gawin ito?

976
01:15:58,790 --> 01:16:08,010
Lamang kami ng ilang minuto, ngunit ang anumang mga mungkahi?

977
01:16:08,010 --> 01:16:14,750
Sa halip na - isang paraan, sa halip ng aming kundisyon pagiging habang,

978
01:16:14,750 --> 01:16:17,090
kung ano Kasalukuyan kaming naghahanap sa ay hindi null,

979
01:16:17,090 --> 01:16:22,340
sa halip namin ay pagpunta upang magpatuloy upang pumunta hanggang ang aming listahan mismo ay null.

980
01:16:22,340 --> 01:16:25,680
Kaya kung ang aming listahan ay nagtatapos pagiging null,

981
01:16:25,680 --> 01:16:30,680
pagkatapos namin maubusan ng mga bagay upang tumingin para sa, upang maghanap sa.

982
01:16:30,680 --> 01:16:39,860
Ngunit na ay nangangahulugan na ang unang bagay na sa aming listahan ay lamang ang unang node.

983
01:16:39,860 --> 01:16:49,730
Ang unang bagay ay - hindi na namin kailangan upang makita na.

984
01:16:49,730 --> 01:16:58,710
Kaya listahan-> n ay ang aming puno.

985
01:16:58,710 --> 01:17:02,860
listahan-> susunod ay pagpunta sa maging null.

986
01:17:02,860 --> 01:17:07,580
At ngayon habang listahan ay hindi katumbas null.

987
01:17:07,580 --> 01:17:11,610
Cur ay pagpunta upang hilahin ng isang bagay mula sa aming listahan.

988
01:17:11,610 --> 01:17:13,500
Kaya kuprum ay pagpunta sa pantay na listahan-> n.

989
01:17:13,500 --> 01:17:20,850
At pagkatapos ay listahan ng pagpunta sa pantay na listahan-> n, o listahan-> susunod.

990
01:17:20,850 --> 01:17:23,480
Kaya kung kuprum halaga ay katumbas ng halaga.

991
01:17:23,480 --> 01:17:28,790
Ngayon ay maaari naming magdagdag ng parehong ang aming karapatan pointer at ang aming kaliwa pointer

992
01:17:28,790 --> 01:17:32,900
hangga't hindi null.

993
01:17:32,900 --> 01:17:36,390
Down dito, hulaan ko dapat naming gawin na sa unang lugar.

994
01:17:36,390 --> 01:17:44,080
Kung (na kuprum> karapatan! = Null)

995
01:17:44,080 --> 01:17:56,380
pagkatapos namin ipasok na node sa aming listahan.

996
01:17:56,380 --> 01:17:59,290
Kung (kuprum-> kaliwa), ito ay isang maliit na bit ng dagdag na trabaho, ngunit ito ay pinong.

997
01:17:59,290 --> 01:18:02,690
Kung (kuprum-> kaliwa! = Null),

998
01:18:02,690 --> 01:18:14,310
at kami ay pagpunta upang ipasok ang pakaliwa sa aming listahan ng link,

999
01:18:14,310 --> 01:18:19,700
at na dapat ito.

1000
01:18:19,700 --> 01:18:22,670
Namin umulit - hangga't mayroon kaming isang bagay sa aming listahan,

1001
01:18:22,670 --> 01:18:26,640
kami ay may isa pang node tingnan.

1002
01:18:26,640 --> 01:18:28,920
Kaya tinitingnan namin na node,

1003
01:18:28,920 --> 01:18:31,390
advance namin ang aming listahan sa susunod na.

1004
01:18:31,390 --> 01:18:34,060
Kung ang node na ay ang halaga na kaming naghahanap ng mga, maaari naming nagbabalik ng tunay.

1005
01:18:34,060 --> 01:18:37,640
Iba Pa isingit ang aming parehong kaliwa at kanang subtrees,

1006
01:18:37,640 --> 01:18:40,510
hangga't hindi null, sa aming listahan

1007
01:18:40,510 --> 01:18:43,120
sa gayon ay hindi maaaring hindi namin pumunta sa ibabaw ng mga ito.

1008
01:18:43,120 --> 01:18:45,160
Kaya kung sila ay hindi null,

1009
01:18:45,160 --> 01:18:47,950
kung ang aming ugat pointer tulis sa dalawang bagay,

1010
01:18:47,950 --> 01:18:51,670
sa unang nakuha namin ang isang bagay kung gayon ang aming listahan ay nagtatapos pagiging null.

1011
01:18:51,670 --> 01:18:56,890
At pagkatapos ay inilalagay namin ang dalawang bagay pabalik sa, kaya ngayon ang aming listahan ng laki 2.

1012
01:18:56,890 --> 01:19:00,030
Pagkatapos kami ay pagpunta sa loop-back up at lang kami upang hilahin,

1013
01:19:00,030 --> 01:19:04,250
sabihin nating, ang kaliwang pointer ng aming mga root node.

1014
01:19:04,250 --> 01:19:07,730
At na kailangan lamang panatilihin ang nangyayari, ipapadala namin sa looping sa paglipas ng lahat.

1015
01:19:07,730 --> 01:19:11,280
>> Pansinin na ito ay makabuluhang mas komplikado

1016
01:19:11,280 --> 01:19:14,160
sa recursive solusyon.

1017
01:19:14,160 --> 01:19:17,260
At ako sinabi nang maraming beses

1018
01:19:17,260 --> 01:19:25,120
na ang recursive solusyon ay karaniwang may mas sa karaniwan na may solusyon ang umuulit.

1019
01:19:25,120 --> 01:19:30,820
Narito ito ay eksakto kung ano ang recursive solusyon ay ginagawa.

1020
01:19:30,820 --> 01:19:36,740
Ang tanging pagbabago ay ang sa halip na nang kataon lamang gamit ang stack, ang mga programa ng stack,

1021
01:19:36,740 --> 01:19:40,840
bilang iyong paraan ng pagpapanatiling ng track kung ano ang node kailangan mo pa ring bisitahin,

1022
01:19:40,840 --> 01:19:45,430
ngayon mayroon kang tahasang gumamit ng isang naka-link na listahan.

1023
01:19:45,430 --> 01:19:49,070
Sa parehong mga kaso ikaw ay pinapanatiling subaybayan ang kung ano node pa rin kailangang binisita.

1024
01:19:49,070 --> 01:19:51,790
Sa recursive kaso lang madali dahil may isang stack

1025
01:19:51,790 --> 01:19:57,100
ay ipinapatupad para sa iyo bilang ng stack ng programa.

1026
01:19:57,100 --> 01:19:59,550
Pansinin na ito ay naka-link na listahan, ito ay isang stack.

1027
01:19:59,550 --> 01:20:01,580
Anuman lang namin ilagay sa ang stack

1028
01:20:01,580 --> 01:20:09,960
ay agad kung ano ang namin ang pagpunta sa mga pull off ang stack upang bisitahin ang susunod.

1029
01:20:09,960 --> 01:20:14,380
Humihingi kami ng oras, ngunit ang anumang mga katanungan?

1030
01:20:14,380 --> 01:20:23,530
[Estudyante, hindi maintindihan]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Oo. Kaya kung mayroon namin ang aming naka-link listahan,

1032
01:20:27,790 --> 01:20:30,150
kasalukuyang upang ituro sa tao na ito,

1033
01:20:30,150 --> 01:20:34,690
at ngayon lamang namin ang pagsulong ng aming naka-link na listahan mag-focus sa tao na ito.

1034
01:20:34,690 --> 01:20:44,200
Traversing Kami ay sa ibabaw ng naka-link na listahan sa na linya.

1035
01:20:44,200 --> 01:20:51,200
At pagkatapos ay hulaan ko dapat magbakante namin ang aming naka-link na listahan at mga bagay-bagay

1036
01:20:51,200 --> 01:20:53,880
isang beses bago bumalik true o false, kailangan namin

1037
01:20:53,880 --> 01:20:57,360
umulit sa aming listahan ng link at laging down na dito, hulaan ko,

1038
01:20:57,360 --> 01:21:03,900
kung namin kuprum ay hindi katumbas ng, idagdag ito, kaya ngayon ay gusto naming magbakante

1039
01:21:03,900 --> 01:21:09,600
kuprum dahil, well, ay namin ganap na kalimutan tungkol sa listahan? Oo.

1040
01:21:09,600 --> 01:21:12,880
Kaya na kung ano ang gusto naming gawin dito.

1041
01:21:12,880 --> 01:21:16,730
Nasaan ang pointer?

1042
01:21:16,730 --> 01:21:23,320
Cur ay pagkatapos - gusto namin sa isang listahan ng struct * 10 katumbas ng listahan ng susunod.

1043
01:21:23,320 --> 01:21:29,240
Libreng listahan, listahan = Temp.

1044
01:21:29,240 --> 01:21:32,820
At sa kaso kung saan bumalik kami totoo, hindi namin kailangan upang umulit

1045
01:21:32,820 --> 01:21:37,050
sa ibabaw ng natitira sa aming mga naka-link na listahan pagbabakante bagay.

1046
01:21:37,050 --> 01:21:39,700
Ang gandang bagay tungkol sa recursive solusyon pagbabakante bagay

1047
01:21:39,700 --> 01:21:44,930
lamang ay nangangahulugan na ang popping factorings off ang stack na mangyari para sa iyo.

1048
01:21:44,930 --> 01:21:50,720
Kaya kami nawala mula sa isang bagay na tulad ng 3 linya ng hard-to-tingin-tungkol code

1049
01:21:50,720 --> 01:21:57,520
sa isang bagay na makabuluhang maraming iba pang mga hard-sa-tingin-tungkol sa mga linya ng code.

1050
01:21:57,520 --> 01:22:00,620
Anumang higit pang mga tanong?

1051
01:22:00,620 --> 01:22:08,760
Ayos lang. Humihingi kami ng mabuti. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]