1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Seksyon 7] [Mas kaunti kumportableng]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Harvard University]

3
00:00:04,890 --> 00:00:07,000
[Ito ay CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Maligayang pagdating sa Seksyon 7.

5
00:00:09,080 --> 00:00:11,330
Salamat sa bagyo Sandy,

6
00:00:11,330 --> 00:00:13,440
sa halip ng pagkakaroon ng isang normal na seksyon sa linggong ito,

7
00:00:13,440 --> 00:00:17,650
ginagawa namin ito lakad-through, sa pamamagitan ng seksyon ng mga tanong.

8
00:00:17,650 --> 00:00:22,830
Ako pupunta na sumusunod na kasama ang Problema Itakda 6 Pagtutukoy,

9
00:00:22,830 --> 00:00:25,650
at pagpunta sa pamamagitan ng lahat ng mga katanungan sa

10
00:00:25,650 --> 00:00:27,770
Isang Seksyon ng mga Tanong seksyon.

11
00:00:27,770 --> 00:00:30,940
Kung may anumang mga katanungan,

12
00:00:30,940 --> 00:00:32,960
mangyaring mai-post ang mga ito sa CS50 talakayin.

13
00:00:32,960 --> 00:00:35,480
>> Tama. Natin makapagsimula.

14
00:00:35,480 --> 00:00:40,780
Sa ngayon Naghahanap ako sa pahina 3 ng Pagtutukoy Problema Set.

15
00:00:40,780 --> 00:00:44,110
Kami ay pagpunta sa unang simulan ang pakikipag-usap tungkol sa mga binary na puno

16
00:00:44,110 --> 00:00:47,850
dahil ang mag iyon ay may maraming ng kaugnayan sa problema sa set na ito linggo -

17
00:00:47,850 --> 00:00:49,950
Huffman Tree pag-encode.

18
00:00:49,950 --> 00:00:55,000
Isa ng ang unang mga istraktura ng data usapan natin ang tungkol sa CS50 ang array.

19
00:00:55,000 --> 00:01:00,170
Tandaan na ang isang array ay isang pagkakasunud-sunod ng mga elemento -

20
00:01:00,170 --> 00:01:04,019
lahat ng parehong uri - naka-imbak sa tabi mismo sa bawat isa sa memorya.

21
00:01:04,019 --> 00:01:14,420
Kung mayroon akong isang integer array na maaari kong iguhit gamit ang kahon-numero-integer estilo -

22
00:01:14,420 --> 00:01:20,290
Ipagpalagay natin na mayroon akong 5 sa unang kahon, mayroon akong 7 sa pangalawang,

23
00:01:20,290 --> 00:01:27,760
Mayroon akong 8, 10, at 20 sa huling kahon.

24
00:01:27,760 --> 00:01:33,000
Tandaan, ang dalawang talagang magandang bagay tungkol sa array na ito

25
00:01:33,000 --> 00:01:38,800
ay na mayroon kaming ito pare-pareho-time na access sa anumang partikular na elemento

26
00:01:38,800 --> 00:01:40,500
 sa array na kung alam namin sa index nito.

27
00:01:40,500 --> 00:01:44,670
Halimbawa, kung gusto kong i-grab ang ikatlong elemento sa array -

28
00:01:44,670 --> 00:01:47,870
sa index 2 gamit ang aming zero-based na sistema ng pag-i-index -

29
00:01:47,870 --> 00:01:52,220
Literal ko lang gawin ang isang simpleng pagkalkula ng matematika,

30
00:01:52,220 --> 00:01:56,170
Hop na posisyon sa array,

31
00:01:56,170 --> 00:01:57,840
hilahin ang 8 na nakaimbak doon,

32
00:01:57,840 --> 00:01:59,260
at ako ay handa na upang patakbuhin.

33
00:01:59,260 --> 00:02:03,350
>> Isa ng masamang bagay tungkol sa array na ito - na usapan natin ang tungkol

34
00:02:03,350 --> 00:02:05,010
kapag tinalakay namin naka-link listahan -

35
00:02:05,010 --> 00:02:09,120
ay na kung gusto ko upang ipasok ang isang elemento sa array na ito,

36
00:02:09,120 --> 00:02:11,090
Ako pagpunta sa gawin ang ilang mga paglilipat sa paligid.

37
00:02:11,090 --> 00:02:12,940
Halimbawa, ito array dito mismo

38
00:02:12,940 --> 00:02:16,850
sa pinagsunod-sunod pagkakasunod-sunod - pinagsunod-sunod sa pataas na pagkakasunod-sunod -

39
00:02:16,850 --> 00:02:19,440
5, pagkatapos 7, pagkatapos 8, pagkatapos ay 10, at pagkatapos ay 20 -

40
00:02:19,440 --> 00:02:23,100
ngunit kung gusto kong ipasok ang numero 9 sa array na ito,

41
00:02:23,100 --> 00:02:27,460
Ako pagpunta sa may upang ilipat ang ilan sa mga elemento upang gumawa ng espasyo.

42
00:02:27,460 --> 00:02:30,440
Namin gumuhit ito dito.

43
00:02:30,440 --> 00:02:35,650
Ako pagpunta sa may upang ilipat ang 5, 7, at pagkatapos ay ang 8;

44
00:02:35,650 --> 00:02:38,720
lumikha ng isang agwat sa kung saan maaari ko bang ilagay ang 9,

45
00:02:38,720 --> 00:02:45,910
at pagkatapos ay 10 at sa 20 ay maaaring pumunta sa kanan ng 9.

46
00:02:45,910 --> 00:02:49,450
Ito ay uri ng isang sakit dahil sa pinakamasama-case na sitwasyon -

47
00:02:49,450 --> 00:02:54,350
kapag kami ay kinakailangang magpasok ng alinman sa simula o sa katapusan

48
00:02:54,350 --> 00:02:56,040
ng array, depende sa kung paano namin ang paglilipat -

49
00:02:56,040 --> 00:02:58,850
maaari naming upang ilipat ang lahat ng mga elemento

50
00:02:58,850 --> 00:03:00,750
na kasalukuyan naming pag-iimbak sa array.

51
00:03:00,750 --> 00:03:03,810
>> Kaya, kung ano ang paraan sa paligid nito?

52
00:03:03,810 --> 00:03:09,260
Ang paraan sa paligid na ito ay upang pumunta sa aming mga naka-link na listahan ng paraan ng kung saan -

53
00:03:09,260 --> 00:03:19,820
sa halip ng pag-iimbak ang mga elemento 5, 7, 8, 10, at 20 lahat ng susunod sa bawat isa sa memorya -

54
00:03:19,820 --> 00:03:25,630
kung ano ang aming halip ay ay-imbak ang mga ito uri ng kung saan man gusto namin upang mag-imbak ang mga ito

55
00:03:25,630 --> 00:03:32,470
sa mga naka-link na listahan node na ako pagguhit dito, uri ng ad hoc.

56
00:03:32,470 --> 00:03:42,060
At pagkatapos namin nakakonekta ang mga iyon nang magkakasama gamit ang mga susunod na mga pointer.

57
00:03:42,060 --> 00:03:44,370
Maaari ba akong magkaroon ng isang pointer mula 5 hanggang 7,

58
00:03:44,370 --> 00:03:46,420
isang pointer mula sa 7 sa 8,

59
00:03:46,420 --> 00:03:47,770
isang pointer mula sa 8 sa 10,

60
00:03:47,770 --> 00:03:51,220
at sa wakas, ang isang pointer mula sa 10 sa 20,

61
00:03:51,220 --> 00:03:54,880
at pagkatapos ay null pointer sa 20 na nagpapahiwatig na may walang kaliwa.

62
00:03:54,880 --> 00:03:59,690
Ang kalakalan-off na mayroon kami dito

63
00:03:59,690 --> 00:04:05,360
na ngayon kung gusto namin upang ipasok ang numero ng 9 sa aming listahan ng pinagsunod-sunod,

64
00:04:05,360 --> 00:04:08,270
lahat kami ay may sa gawin ay lumikha ng isang bagong node na may 9 na,

65
00:04:08,270 --> 00:04:12,290
wire up ang mga ito upang tumuro sa naaangkop na lugar,

66
00:04:12,290 --> 00:04:20,630
at pagkatapos ay muling i-wire ang 8 upang ituro down sa 9.

67
00:04:20,630 --> 00:04:25,660
Na medyo mabilis, ipagpalagay alam namin eksakto kung saan gusto naming ipasok ang 9.

68
00:04:25,660 --> 00:04:32,610
Ngunit ang kalakalan-off sa kapalit para sa ay na namin ngayon ang nawala ang hindi nagbabagong-time na access

69
00:04:32,610 --> 00:04:36,230
sa anumang partikular na elemento sa aming mga data ng istraktura.

70
00:04:36,230 --> 00:04:40,950
Halimbawa, kung gusto kong makita ang ika-apat na elemento sa naka-link na listahan,

71
00:04:40,950 --> 00:04:43,510
Ako pagpunta sa magsimula sa simula ng listahan

72
00:04:43,510 --> 00:04:48,930
at gumana ang aking paraan sa pamamagitan ng pagbibilang ng node-by-node hanggang sa mahanap ko ang ika-apat na.

73
00:04:48,930 --> 00:04:55,870
>> Upang makakuha ng mas mahusay na access pagganap kaysa sa isang naka-link na listahan -

74
00:04:55,870 --> 00:04:59,360
kundi pati na rin panatilihin ang ilang ng mga benepisyo na nagkaroon kami

75
00:04:59,360 --> 00:05:01,800
sa mga tuntunin ng pagpapasok ng-oras mula sa isang naka-link na listahan -

76
00:05:01,800 --> 00:05:05,750
isang binary tree ay kailangang gamitin ng kaunti pa sa memory.

77
00:05:05,750 --> 00:05:11,460
Sa partikular, sa halip ng pagkakaroon ng isang pointer sa isang binary puno node -

78
00:05:11,460 --> 00:05:13,350
tulad ng mga naka-link na listahan node ginagawa -

79
00:05:13,350 --> 00:05:16,950
kami ay upang magdagdag ng isang pangalawang pointer sa binary puno node.

80
00:05:16,950 --> 00:05:19,950
Sa halip na lamang pagkakaroon ng isang pointer sa susunod na elemento,

81
00:05:19,950 --> 00:05:24,420
kami ay pagpunta upang magkaroon ng isang pointer sa kaliwa anak at kanang bata.

82
00:05:24,420 --> 00:05:26,560
>> Natin gumuhit ng larawan upang makita kung ano ang na aktwal na kamukha.

83
00:05:26,560 --> 00:05:31,350
Muli, ako pagpunta sa gamitin ang mga kahon at arrow.

84
00:05:31,350 --> 00:05:37,150
Ang isang binary puno node ay magsimula sa isang simpleng kahon.

85
00:05:37,150 --> 00:05:40,940
Ito ay upang magkaroon ng espasyo para sa halaga,

86
00:05:40,940 --> 00:05:47,280
at pagkatapos din ito upang magkaroon ng espasyo para sa kaliwang bata at ang karapatan ng bata.

87
00:05:47,280 --> 00:05:49,280
Ako pagpunta sa label ang mga ito dito.

88
00:05:49,280 --> 00:05:57,560
Kami ay pagpunta sa may kaliwang anak, at pagkatapos namin ay pagpunta sa may karapatan bata.

89
00:05:57,560 --> 00:05:59,920
Mayroong maraming iba't ibang mga paraan ng paggawa nito.

90
00:05:59,920 --> 00:06:02,050
Minsan para sa space at kaginhawahan,

91
00:06:02,050 --> 00:06:06,460
Makikita ko aktwal na gumuhit ang mga ito tulad ng ako ginagawa dito sa ibaba

92
00:06:06,460 --> 00:06:10,910
kung saan ako pupunta ang halaga sa tuktok,

93
00:06:10,910 --> 00:06:14,060
at pagkatapos ay ang karapatan ng bata sa ibabang-kanan,

94
00:06:14,060 --> 00:06:16,060
at ang kaliwang bata sa ibabang-kaliwa.

95
00:06:16,060 --> 00:06:20,250
Pagpunta pabalik sa tuktok diagram na ito,

96
00:06:20,250 --> 00:06:22,560
mayroon namin ang halaga sa pinakatuktok,

97
00:06:22,560 --> 00:06:25,560
mayroon kaming kaliwang anak pointer, at pagkatapos ay mayroon kaming i-right-anak pointer.

98
00:06:25,560 --> 00:06:30,110
>> Sa Pagtutukoy Problema Set,

99
00:06:30,110 --> 00:06:33,110
makipag-usap namin tungkol sa pagguhit ng isang node na may isang halaga 7,

100
00:06:33,110 --> 00:06:39,750
at pagkatapos ng kaliwang anak pointer na null, at i-right-anak pointer na null.

101
00:06:39,750 --> 00:06:46,040
Maaari naming isulat ang kabisera null sa puwang para sa

102
00:06:46,040 --> 00:06:51,610
parehong kaliwang bata at ang karapatan ng bata, o namin maaaring gumuhit ito dayagonal slash

103
00:06:51,610 --> 00:06:53,750
sa pamamagitan ng bawat isa sa ang mga kahon upang ipahiwatig na ito ang null.

104
00:06:53,750 --> 00:06:57,560
Ako pagpunta upang gawin iyon dahil lamang na simple.

105
00:06:57,560 --> 00:07:03,700
Ano ang nakikita mo dito dalawang paraan ng balangkas ng isang napaka-simpleng binary puno node

106
00:07:03,700 --> 00:07:07,960
kung saan mayroon kaming ang halaga 7 at null pointer ng bata.

107
00:07:07,960 --> 00:07:15,220
>> Ang ikalawang bahagi ng aming mga detalye ng pag-uusap tungkol sa kung paano sa naka-link na listahan -

108
00:07:15,220 --> 00:07:18,270
Tandaan, lamang namin ay upang i-hold sa sa unang elemento sa isang listahan

109
00:07:18,270 --> 00:07:20,270
tandaan ang buong listahan -

110
00:07:20,270 --> 00:07:26,140
at din, na may isang binary puno, lamang namin upang i-hold sa isang pointer sa tree

111
00:07:26,140 --> 00:07:31,120
upang mapanatili ang kontrol sa ang buong istraktura ng data.

112
00:07:31,120 --> 00:07:36,150
Ito espesyal na elemento ng puno ay tinatawag ang root node ng puno.

113
00:07:36,150 --> 00:07:43,360
Halimbawa, kung ang isang node - node na ito na naglalaman ng mga halaga 7

114
00:07:43,360 --> 00:07:45,500
may null kaliwa-at i-right-anak payo -

115
00:07:45,500 --> 00:07:47,360
ay ang tanging halaga sa aming puno,

116
00:07:47,360 --> 00:07:50,390
pagkatapos na ito ay ang aming na root node.

117
00:07:50,390 --> 00:07:52,240
Pinakadulo simula ng aming puno.

118
00:07:52,240 --> 00:07:58,530
Maaari naming makita na ito ng kaunti pa malinaw sa sandaling sinimulan namin ang pagdaragdag ng higit pang mga node sa aming puno.

119
00:07:58,530 --> 00:08:01,510
Hayaan akong makuha ang isang bagong pahina.

120
00:08:01,510 --> 00:08:05,000
>> Ngayon kami ay pagpunta sa gumuhit ng isang puno na may 7 sa root,

121
00:08:05,000 --> 00:08:10,920
at 3 sa loob ng kaliwang bata, at 9 sa loob ng tamang anak.

122
00:08:10,920 --> 00:08:13,500
Muli, ito ay medyo simple.

123
00:08:13,500 --> 00:08:26,510
Mayroon kaming 7, gumuhit ng node para sa 3, isang node para sa 9,

124
00:08:26,510 --> 00:08:32,150
at ako pagpunta upang itakda ang kaliwang anak pointer ng 7 upang ituro sa node na naglalaman ng 3,

125
00:08:32,150 --> 00:08:37,850
at i-right-anak pointer ng node na naglalaman ng 7 sa node na naglalaman ng 9.

126
00:08:37,850 --> 00:08:42,419
Ngayon, dahil 3 at 9 walang anumang mga bata,

127
00:08:42,419 --> 00:08:48,500
kami ay pagpunta upang i-set ang lahat ng kanilang mga payo sa anak null.

128
00:08:48,500 --> 00:08:56,060
Dito, ang root ng aming mga puno ay tumutugon sa node na naglalaman ng bilang 7.

129
00:08:56,060 --> 00:09:02,440
Maaari mong makita na kung ang lahat ng mayroon kami ay isang pointer sa root na node,

130
00:09:02,440 --> 00:09:07,330
maaari naming maglakad sa pamamagitan ng aming puno at ma-access ang parehong mga node ng bata -

131
00:09:07,330 --> 00:09:10,630
parehong 3 at 9.

132
00:09:10,630 --> 00:09:14,820
Hindi na kailangan upang mapanatili ang mga payo sa bawat solong node sa puno.

133
00:09:14,820 --> 00:09:22,080
Tama. Ngayon sinusubukan namin upang magdagdag ng isa pang node sa diagram na ito.

134
00:09:22,080 --> 00:09:25,370
Kami ay pagpunta sa magdagdag ng node na naglalaman ng 6,

135
00:09:25,370 --> 00:09:34,140
at kami ay pagpunta upang idagdag ito bilang ang karapatan na anak ng node na naglalaman ng 3.

136
00:09:34,140 --> 00:09:41,850
Upang gawin iyon, ako burahin na null pointer sa 3-node

137
00:09:41,850 --> 00:09:47,750
at wire ang mga ito upang tumuro sa node na naglalaman ng 6. Tama.

138
00:09:47,750 --> 00:09:53,800
>> Sa puntong ito, sabihin pumunta sa paglipas ng kaunting terminolohiya.

139
00:09:53,800 --> 00:09:58,230
Upang magsimula, ang dahilan na ito ay tinatawag na isang binary puno sa partikular na

140
00:09:58,230 --> 00:10:00,460
ay na ito ay may dalawang anak payo.

141
00:10:00,460 --> 00:10:06,020
May mga iba pang mga uri ng mga puno na may higit pang mga payo anak.

142
00:10:06,020 --> 00:10:10,930
Sa partikular, ang isang 'subukan' sa Problema Set 5.

143
00:10:10,930 --> 00:10:19,310
Mapapansin mo na sa na Subukan, mayroon kang 27 iba't ibang mga payo sa iba't ibang mga bata -

144
00:10:19,310 --> 00:10:22,410
isa para sa bawat isa ng 26 titik sa Ingles alpabeto,

145
00:10:22,410 --> 00:10:25,410
at pagkatapos ay ang 27 para sa kudlit -

146
00:10:25,410 --> 00:10:28,900
ito, na katulad sa isang uri ng puno.

147
00:10:28,900 --> 00:10:34,070
Ngunit dito, dahil ito ay binary, lamang namin ay may dalawang pointer anak.

148
00:10:34,070 --> 00:10:37,880
>> Bilang karagdagan sa root node na na usapan natin ang tungkol,

149
00:10:37,880 --> 00:10:41,470
din namin ang ibinabato sa buong term na ito 'anak.'

150
00:10:41,470 --> 00:10:44,470
Ano ang ibig sabihin para sa isang node sa isang bata ng isa pang node?

151
00:10:44,470 --> 00:10:54,060
Ito literal ay nangangahulugan na ang isang bata node ay isang anak ng isa pang node

152
00:10:54,060 --> 00:10:58,760
kung na ang ibang node ay may isa ng mga payo ng anak na nakatakda upang tumuro sa node na.

153
00:10:58,760 --> 00:11:01,230
Upang ilagay ang sa mas kongkreto mga tuntunin,

154
00:11:01,230 --> 00:11:11,170
kung 3 ay tulis sa pamamagitan ng isa ng mga payo sa anak ng 7, pagkatapos 3 ay isang anak ng 7.

155
00:11:11,170 --> 00:11:14,510
Kung kami ay upang malaman kung ano ang mga bata ng 7 -

156
00:11:14,510 --> 00:11:18,510
mahusay, namin makita na 7 ay may pointer sa 3 at isang pointer sa 9,

157
00:11:18,510 --> 00:11:22,190
kaya 9 at 3 ay ang mga anak ng 7.

158
00:11:22,190 --> 00:11:26,650
Siyam ay walang mga bata dahil ang mga payo sa anak ay null,

159
00:11:26,650 --> 00:11:30,940
at 3 ay lamang ng isang bata, 6.

160
00:11:30,940 --> 00:11:37,430
Anim din ay walang mga bata dahil ang parehong ng kanyang mga payo ay null, na makikita namin gumuhit ngayon.

161
00:11:37,430 --> 00:11:45,010
>> Bukod pa rito, hindi namin ring makipag-usap tungkol sa mga magulang ng isang partikular na node,

162
00:11:45,010 --> 00:11:51,100
at ito ay, bilang gusto mong asahan, ang reverse ng paglalarawan na ito ng bata.

163
00:11:51,100 --> 00:11:58,620
Bawat node ay isang magulang lamang - sa halip na dalawang bilang maaari mong asahan na may mga tao.

164
00:11:58,620 --> 00:12:03,390
Halimbawa, ang mga magulang ng 3 ay 7.

165
00:12:03,390 --> 00:12:10,800
Ang magulang ng 9 7, at ang magulang ng 6 ay 3. Hindi magkano dito.

166
00:12:10,800 --> 00:12:15,720
Mayroon din kaming mga termino upang makipag-usap tungkol sa mga grandparents at inapo,

167
00:12:15,720 --> 00:12:18,210
at mas pangkalahatang makipag-usap namin tungkol sa ninuno

168
00:12:18,210 --> 00:12:20,960
at mga kaapu-apuhan ng isang partikular na node.

169
00:12:20,960 --> 00:12:25,710
Ang ninuno ng isang node - o ninuno, sa halip, ng isang node -

170
00:12:25,710 --> 00:12:32,730
ang lahat ng node na nagsisinungaling sa path mula sa root na node.

171
00:12:32,730 --> 00:12:36,640
Halimbawa, kung Naghahanap ako sa node 6,

172
00:12:36,640 --> 00:12:46,430
pagkatapos ay ang mga ninuno ay pagpunta sa parehong 3 at 7.

173
00:12:46,430 --> 00:12:55,310
Ang mga ninuno ng 9, halimbawa, - kung Naghahanap ako sa node 9 -

174
00:12:55,310 --> 00:12:59,990
pagkatapos ay ang ninuno ng 9 7.

175
00:12:59,990 --> 00:13:01,940
At mga kaapu-apuhan ay eksakto ang reverse.

176
00:13:01,940 --> 00:13:05,430
Kung gusto kong tumingin sa lahat ng kaapu-apuhan ng 7,

177
00:13:05,430 --> 00:13:11,020
Mayroon akong tumingin sa lahat ng node sa ilalim nito.

178
00:13:11,020 --> 00:13:16,950
Kaya, mayroon akong 3, 9, at 6 lahat bilang mga kaapu-apuhan ng 7.

179
00:13:16,950 --> 00:13:24,170
>> Ang huling termino na namin makipag-usap tungkol sa ay ang paniwala na ito ng pagiging isang kapatid.

180
00:13:24,170 --> 00:13:27,980
Kapatid - uri ng sumusunod na kasama sa mga tuntunin ng pamilya -

181
00:13:27,980 --> 00:13:33,150
node na sa parehong antas sa tree.

182
00:13:33,150 --> 00:13:42,230
Kaya, 3 at 9 ay kapatid sapagkat ang mga ito sa parehong antas sa tree.

183
00:13:42,230 --> 00:13:46,190
Sila ay parehong magkaroon ng parehong magulang, 7.

184
00:13:46,190 --> 00:13:51,400
6 ay walang mga kapatid dahil 9 ay hindi magkakaroon ng anumang mga bata.

185
00:13:51,400 --> 00:13:55,540
At 7 ay hindi magkakaroon ng anumang mga kapatid dahil ito ang root ng aming mga puno,

186
00:13:55,540 --> 00:13:59,010
at may lamang kailanman 1 ugat.

187
00:13:59,010 --> 00:14:02,260
Para sa 7 upang magkaroon ng mga kapatid doon ng node sa itaas 7.

188
00:14:02,260 --> 00:14:07,480
May magulang ng 7, kung saan 7 ay hindi na ang ugat ng puno.

189
00:14:07,480 --> 00:14:10,480
Pagkatapos na bagong magulang ng 7 rin upang magkaroon ng isang bata,

190
00:14:10,480 --> 00:14:16,480
at ang bata na pagkatapos ay ang kapatid ng 7.

191
00:14:16,480 --> 00:14:21,040
>> Tama. Paglipat sa.

192
00:14:21,040 --> 00:14:24,930
Kapag na sinimulan namin ang aming talakayan ng mga puno ng binary,

193
00:14:24,930 --> 00:14:28,790
usapan natin ang tungkol sa kung paano namin ay pagpunta sa gamitin ang mga ito sa

194
00:14:28,790 --> 00:14:32,800
makakuha ng isang kalamangan sa parehong mga array at mga naka-link na listahan.

195
00:14:32,800 --> 00:14:37,220
At ang paraan na kami ay pagpunta upang gawin iyon ay may ari-arian ito sa pag-order.

196
00:14:37,220 --> 00:14:41,080
Sinasabi namin na ang isang binary puno order, ayon sa detalye,

197
00:14:41,080 --> 00:14:45,740
kung para sa bawat node sa aming puno, ang lahat ng kanyang mga kaapu-apuhan sa kaliwa -

198
00:14:45,740 --> 00:14:48,670
ang kaliwang anak at lahat ng kaapu-apuhan kaliwang bata -

199
00:14:48,670 --> 00:14:54,510
magkaroon ng mas mababang mga halaga, at ang lahat ng node sa kanan -

200
00:14:54,510 --> 00:14:57,770
ang karapatan ng bata at ang lahat ng mga kaapu-apuhan ng karapatan bata -

201
00:14:57,770 --> 00:15:02,800
may node mas mataas kaysa sa halaga ng kasalukuyang node na kaming naghahanap sa.

202
00:15:02,800 --> 00:15:07,850
Para lamang sa mga simple, kami ay ipinapalagay na may ay hindi anumang mga duplicate na node sa aming puno.

203
00:15:07,850 --> 00:15:11,180
Halimbawa, sa puno hindi namin ka upang harapin ang kaso

204
00:15:11,180 --> 00:15:13,680
kung saan mayroon kaming ang halaga 7 sa root

205
00:15:13,680 --> 00:15:16,720
 at pagkatapos din namin ang halaga 7 sa ibang lugar sa tree.

206
00:15:16,720 --> 00:15:24,390
Sa kasong ito, mapapansin mo na ang puno na ito ay sa katunayan order.

207
00:15:24,390 --> 00:15:26,510
Mayroon kaming ang halaga 7 sa root.

208
00:15:26,510 --> 00:15:29,720
Lahat sa kaliwa ng 7 -

209
00:15:29,720 --> 00:15:35,310
kung ako i-undo lahat ng mga maliit na marka dito -

210
00:15:35,310 --> 00:15:40,450
lahat sa kaliwa ng 7 - ang 3 at ang 6 -

211
00:15:40,450 --> 00:15:49,410
mga halagang iyon ay parehong mas mababa sa 7, at lahat sa kanan - na lamang ito 9 -

212
00:15:49,410 --> 00:15:53,450
ay mas mataas kaysa sa 7.

213
00:15:53,450 --> 00:15:58,650
>> Na ito ay hindi lamang order puno na naglalaman ng mga halagang ito,

214
00:15:58,650 --> 00:16:03,120
ngunit sabihin gumuhit ng ilang higit pa sa kanila.

215
00:16:03,120 --> 00:16:05,030
May ay talagang isang buong grupo ng mga paraan na maaari naming gawin ito.

216
00:16:05,030 --> 00:16:09,380
Ako gumamit ng shorthand lamang upang panatilihing simple ang mga bagay kung saan -

217
00:16:09,380 --> 00:16:11,520
kaysa sa pagguhit ang buong kahon-at-arrow -

218
00:16:11,520 --> 00:16:14,220
Lang ako pagpunta upang gumuhit ang mga numero at magdagdag ng mga arrow sa pagkonekta sa kanila.

219
00:16:14,220 --> 00:16:22,920
Upang magsimula, magsulat lamang namin ang aming orihinal na puno muli kung saan nagkaroon kami 7, at pagkatapos ay 3,

220
00:16:22,920 --> 00:16:25,590
at pagkatapos ay 3 tulis pabalik sa kanan sa 6,

221
00:16:25,590 --> 00:16:30,890
at 7 nagkaroon ng karapatan ng bata na 9.

222
00:16:30,890 --> 00:16:33,860
Tama. Ano ang isa pang paraan na maaari naming isulat ang puno?

223
00:16:33,860 --> 00:16:38,800
Sa halip ng pagkakaroon ng 3 kaliwang anak ng 7,

224
00:16:38,800 --> 00:16:41,360
kami din ang 6 kaliwang anak ng 7,

225
00:16:41,360 --> 00:16:44,470
at pagkatapos ay 3 kaliwang anak ng 6.

226
00:16:44,470 --> 00:16:48,520
Na magiging ganito ang hitsura ito puno dito mismo kung saan Mayroon akong 7,

227
00:16:48,520 --> 00:16:57,860
pagkatapos 6, pagkatapos 3, at 9 sa kanan.

228
00:16:57,860 --> 00:17:01,490
Hindi rin namin na magkaroon ng 7 ng aming root node.

229
00:17:01,490 --> 00:17:03,860
Mayroon din kaming 6 ng aming root node.

230
00:17:03,860 --> 00:17:06,470
Ano ang gusto na hitsura?

231
00:17:06,470 --> 00:17:09,230
Kung kami ay upang mapanatili ang order na ari-arian,

232
00:17:09,230 --> 00:17:12,970
lahat sa kaliwa ng 6 na mas mababa kaysa dito.

233
00:17:12,970 --> 00:17:16,540
Mayroon lamang isang posibilidad, at na 3.

234
00:17:16,540 --> 00:17:19,869
Ngunit bilang ang karapatan na anak ng 6, mayroon kaming dalawang mga posibilidad.

235
00:17:19,869 --> 00:17:25,380
Una, maaari naming magkaroon ng 7 at pagkatapos ay ang 9,

236
00:17:25,380 --> 00:17:28,850
o maaari naming gumuhit ito - tulad ako gawin dito -

237
00:17:28,850 --> 00:17:34,790
kung saan mayroon kaming ang 9 bilang ang karapatan na anak ng 6,

238
00:17:34,790 --> 00:17:39,050
at pagkatapos ay ang 7 bilang kaliwang anak ng 9.

239
00:17:39,050 --> 00:17:44,240
>> Ngayon, 7 at 6 ay hindi lamang ang mga posibleng halaga para sa root.

240
00:17:44,240 --> 00:17:50,200
Mayroon din kaming 3 sa root.

241
00:17:50,200 --> 00:17:52,240
Ano ang mangyayari kung 3 sa root?

242
00:17:52,240 --> 00:17:54,390
Dito, ang mga bagay makakuha ng kaunti kawili-wili.

243
00:17:54,390 --> 00:17:58,440
Tatlong ay hindi magkaroon ng anumang mga halaga na mas mababa kaysa dito,

244
00:17:58,440 --> 00:18:02,070
kaya na buong kaliwang bahagi ng puno lamang null.

245
00:18:02,070 --> 00:18:03,230
Mayroong hindi pagpunta sa anumang doon.

246
00:18:03,230 --> 00:18:07,220
Sa kanan, maaari naming ilista ang mga bagay sa pataas na pagkakasunod-sunod.

247
00:18:07,220 --> 00:18:15,530
Maaari kaming magkaroon ng 3, pagkatapos 6, pagkatapos 7, pagkatapos 9.

248
00:18:15,530 --> 00:18:26,710
O, maaari naming gawin 3, pagkatapos 6, pagkatapos 9, pagkatapos 7.

249
00:18:26,710 --> 00:18:35,020
O, maaari naming gawin 3, pagkatapos 7, pagkatapos 6, pagkatapos 9.

250
00:18:35,020 --> 00:18:40,950
O, 3, 7 - aktwal na walang, hindi namin maaaring gawin ang isang 7 ito.

251
00:18:40,950 --> 00:18:43,330
Na ang aming isang bagay doon.

252
00:18:43,330 --> 00:18:54,710
Maaari naming gawin 9, at pagkatapos ay mula sa 9 kami 6 at pagkatapos ay 7.

253
00:18:54,710 --> 00:19:06,980
O, maaari naming gawin 3, pagkatapos 9, pagkatapos 7, at pagkatapos ay 6.

254
00:19:06,980 --> 00:19:12,490
>> Isang bagay upang gumuhit ang iyong pansin dito ay

255
00:19:12,490 --> 00:19:14,510
na ang mga puno na ito ay isang maliit na kakaiba na anyo.

256
00:19:14,510 --> 00:19:17,840
Sa partikular, kung tiningnan namin sa 4 na puno sa kanang bahagi -

257
00:19:17,840 --> 00:19:20,930
Circle ko sa kanila, narito -

258
00:19:20,930 --> 00:19:28,410
mga puno tumingin halos eksakto tulad ng isang naka-link na listahan.

259
00:19:28,410 --> 00:19:32,670
Bawat node ay may lamang ng isang bata,

260
00:19:32,670 --> 00:19:38,950
at kaya hindi namin magkaroon ng anuman sa mga ito tree-tulad ng istraktura na nakikita namin, halimbawa,

261
00:19:38,950 --> 00:19:44,720
 sa isang kabuto puno sa dito sa kaliwang ibaba.

262
00:19:44,720 --> 00:19:52,490
Mga puno na ito ay aktwal na tinatawag na sumama puno binary,

263
00:19:52,490 --> 00:19:54,170
at kami na makipag-usap tungkol sa mga ito higit pa sa hinaharap -

264
00:19:54,170 --> 00:19:56,730
lalo na kung kang pumunta sa tumagal ng iba pang mga kurso ng computer science.

265
00:19:56,730 --> 00:19:59,670
Mga puno na ito ay manghina.

266
00:19:59,670 --> 00:20:03,780
Ang mga ito ay hindi lubhang kapaki-pakinabang dahil, sa katunayan, ang istraktura na ito lends mismo

267
00:20:03,780 --> 00:20:08,060
 sa paghahanap ng mga beses na katulad ng isang naka-link na listahan.

268
00:20:08,060 --> 00:20:13,050
Hindi namin upang samantalahin ng dagdag na memorya - ito extrang pointer -

269
00:20:13,050 --> 00:20:18,840
dahil sa aming istraktura pagiging masama sa ganitong paraan.

270
00:20:18,840 --> 00:20:24,700
Sa halip na pumunta sa at gumuhit ang mga binary puno na may 9 sa root,

271
00:20:24,700 --> 00:20:27,220
na ang panghuling kaso na namin,

272
00:20:27,220 --> 00:20:32,380
hindi namin sa halip, sa puntong ito, na pagpunta sa makipag-usap ng kaunti tungkol sa iba pang mga termino

273
00:20:32,380 --> 00:20:36,150
namin gamitin kapag pakikipag-usap tungkol sa mga puno, na kung saan ay tinatawag na taas.

274
00:20:36,150 --> 00:20:45,460
>> Ang taas ng isang puno ay ang distansya mula sa root sa ang pinaka-malayong node,

275
00:20:45,460 --> 00:20:48,370
o sa halip ang bilang ng mga hops na mayroon ka upang

276
00:20:48,370 --> 00:20:53,750
magsimula mula sa root at pagkatapos ay magtapos sa pinaka-malayong node sa tree.

277
00:20:53,750 --> 00:20:57,330
Kung titingnan namin sa ilan sa mga puno na namin ang iginuhit dito mismo,

278
00:20:57,330 --> 00:21:07,870
maaari naming makita na kung gagawin namin ito puno sa tuktok na kaliwang sulok at simulan namin sa 3,

279
00:21:07,870 --> 00:21:14,510
mayroon kaming upang gumawa ng 1 hop upang makakuha ng sa 6, ang pangalawang hop upang makakuha ng sa 7,

280
00:21:14,510 --> 00:21:20,560
at isang third hop upang makakuha ng sa 9.

281
00:21:20,560 --> 00:21:26,120
Kaya, ang taas ng puno na ito ay 3.

282
00:21:26,120 --> 00:21:30,640
Maaari naming gawin ang parehong ehersisyo para sa iba pang mga puno na nakabalangkas na may berde na ito,

283
00:21:30,640 --> 00:21:40,100
at nakita namin na ang taas ng lahat ng mga puno sa katunayan 3.

284
00:21:40,100 --> 00:21:45,230
Iyon ay bahagi ng kung bakit ang mga ito lumubha -

285
00:21:45,230 --> 00:21:53,750
na ang kanilang taas ay isa lamang mas mababa kaysa sa bilang ng mga node sa buong puno.

286
00:21:53,750 --> 00:21:58,400
Kung titingnan namin sa iba pang mga puno na libid sa pula, sa kabilang banda,

287
00:21:58,400 --> 00:22:03,920
nakikita namin na ang pinaka-malayong dahon node sa 6 at ang 9 -

288
00:22:03,920 --> 00:22:06,940
umalis pagiging mga node na ay walang mga bata.

289
00:22:06,940 --> 00:22:11,760
Kaya, upang makakuha ng mula sa root node sa alinman sa 6 o sa 9,

290
00:22:11,760 --> 00:22:17,840
mayroon kaming upang gumawa ng isang hop upang makakuha ng sa 7 at pagkatapos ng pangalawang hop upang makakuha ng sa 9,

291
00:22:17,840 --> 00:22:21,240
at din, lamang ng pangalawang hop mula sa 7 upang makakuha ng sa 6.

292
00:22:21,240 --> 00:22:29,080
Kaya, ang taas ng puno na ito sa paglipas dito lamang 2.

293
00:22:29,080 --> 00:22:35,330
Maaari kang bumalik at gawin iyon para sa lahat ng iba pang mga puno na tinalakay namin dati

294
00:22:35,330 --> 00:22:37,380
nagsisimula na may 7 at ang 6,

295
00:22:37,480 --> 00:22:42,500
at makikita mo na ang taas ng lahat ng mga puno ding 2.

296
00:22:42,500 --> 00:22:46,320
>> Ang dahilan na namin ang pinag-uusapan ay iniutos ng binary puno

297
00:22:46,320 --> 00:22:50,250
at kung bakit sila ay cool ay dahil maaari kang maghanap sa pamamagitan ng mga ito sa

298
00:22:50,250 --> 00:22:53,810
isang katulad na paraan sa paghahanap sa paglipas ng pinagsunod-sunod na array.

299
00:22:53,810 --> 00:22:58,720
Ito ay kung saan namin makipag-usap tungkol sa pagkuha ng oras na pinabuting lookup

300
00:22:58,720 --> 00:23:02,730
sa ibabaw ng simpleng naka-link na listahan.

301
00:23:02,730 --> 00:23:05,010
Na may isang naka-link na listahan - kung gusto mong mahanap ang isang partikular na elemento -

302
00:23:05,010 --> 00:23:07,470
ikaw ay sa pinakamahusay na pagpunta sa gawin ang ilang mga uri ng linear na paghahanap

303
00:23:07,470 --> 00:23:10,920
kung saan simulan mo sa simula ng isang listahan at hop isa-by-isa -

304
00:23:10,920 --> 00:23:12,620
isang node ng isa node -

305
00:23:12,620 --> 00:23:16,060
sa pamamagitan ng buong listahan hanggang sa mahanap mo ang anumang naghahanap ka para sa.

306
00:23:16,060 --> 00:23:19,440
Sapagkat, kung mayroon kang isang binary puno na naka-imbak sa ito maganda ang format,

307
00:23:19,440 --> 00:23:23,300
maaari mong aktwal na makakuha ng mas maraming ng isang binary paghahanap na nangyayari sa

308
00:23:23,300 --> 00:23:25,160
kung saan mo hatiin at lupigin

309
00:23:25,160 --> 00:23:29,490
at paghahanap sa pamamagitan ng naaangkop na kalahati ng puno sa bawat hakbang.

310
00:23:29,490 --> 00:23:32,840
Natin makita kung paano na gumagana.

311
00:23:32,840 --> 00:23:38,850
>> Kung kami ay may - muli, pagpunta sa aming orihinal na puno -

312
00:23:38,850 --> 00:23:46,710
sisimulan namin sa 7, mayroon kaming 3 sa kaliwa, 9 sa kanan,

313
00:23:46,710 --> 00:23:51,740
at sa ilalim ng 3 namin ang 6.

314
00:23:51,740 --> 00:24:01,880
Kung gusto naming upang maghanap para sa bilang 6 sa puno, gusto namin magsimula sa root.

315
00:24:01,880 --> 00:24:08,910
Gusto namin ihambing ang halaga namin ang iyong hinahanap para sa, sabihin nating 6,

316
00:24:08,910 --> 00:24:12,320
sa halaga na naka-imbak sa node na kasalukuyan kaming naghahanap sa, 7,

317
00:24:12,320 --> 00:24:21,200
mahanap na 6 ay talagang mas mababa kaysa sa 7, kaya nais naming ilipat sa kaliwa.

318
00:24:21,200 --> 00:24:25,530
Kung ang halaga ng 6 ay mas mataas kaysa sa 7, sa halip na namin inilipat sa kanan.

319
00:24:25,530 --> 00:24:29,770
Dahil alam namin na - dahil sa istraktura ng aming order na puno ng binary -

320
00:24:29,770 --> 00:24:33,910
lahat ng ang mga halaga na mas mababa kaysa sa 7 na naka-imbak sa kaliwa ng 7,

321
00:24:33,910 --> 00:24:40,520
walang pangangailangan sa kahit abala naghahanap sa pamamagitan ng kanang bahagi ng puno.

322
00:24:40,520 --> 00:24:43,780
Kapag naming ilipat sa kaliwa at kami ngayon sa node na naglalaman ng 3,

323
00:24:43,780 --> 00:24:48,110
maaari naming gawin na parehong paghahambing muli kung saan Inihambing namin ang 3 at ang 6.

324
00:24:48,110 --> 00:24:52,430
At nakita namin na habang 6 - ang halaga na kaming naghahanap ng mga - ay mas malaki kaysa sa 3,

325
00:24:52,430 --> 00:24:58,580
maaari naming pumunta sa kanang bahagi ng node na naglalaman ng 3.

326
00:24:58,580 --> 00:25:02,670
Walang kaliwang bahagi dito, kaya kami binabalewala na.

327
00:25:02,670 --> 00:25:06,510
Ngunit lamang namin malaman na dahil kaming naghahanap sa tree mismo,

328
00:25:06,510 --> 00:25:08,660
at maaari naming makita na ang puno ay walang mga bata.

329
00:25:08,660 --> 00:25:13,640
>> Rin medyo madali upang maghanap 6 sa puno na ito kung ginagawa namin ito sa ating sarili bilang tao,

330
00:25:13,640 --> 00:25:16,890
ngunit sabihin sundin ang prosesong ito nang wala sa loob tulad ng isang computer ay gawin

331
00:25:16,890 --> 00:25:18,620
talagang maunawaan ang algorithm.

332
00:25:18,620 --> 00:25:26,200
Sa puntong ito, na namin ngayon ang iyong hinahanap sa isang node na naglalaman ng 6,

333
00:25:26,200 --> 00:25:29,180
at kami ay naghahanap para sa ang halaga 6,

334
00:25:29,180 --> 00:25:31,740
ito, sa katunayan, hindi namin natagpuan ang mga naaangkop na node.

335
00:25:31,740 --> 00:25:35,070
Natagpuan namin ang halaga 6 sa aming puno, at maaari naming ihinto ang aming paghahanap.

336
00:25:35,070 --> 00:25:37,330
Sa puntong ito, depende sa kung anong nangyayari sa,

337
00:25:37,330 --> 00:25:41,870
maaari naming sabihin, oo, namin natagpuan ang halaga 6, umiiral sa aming puno.

338
00:25:41,870 --> 00:25:47,640
O, kung kami ay pagpaplano upang magpasok ng isang node o gawin ang isang bagay, maaari naming gawin iyon sa puntong ito.

339
00:25:47,640 --> 00:25:53,010
>> Natin ng ilang higit pa lookup lamang upang makita kung paano ito gumagana.

340
00:25:53,010 --> 00:25:59,390
Tingnan natin sa kung ano ang mangyayari kung namin upang subukan at hanapin ang halaga 10.

341
00:25:59,390 --> 00:26:02,970
Kung kami ay upang tumingin up ang halaga 10, gusto naming magsimula sa root.

342
00:26:02,970 --> 00:26:07,070
Gusto naming makita na 10 ay mas mataas kaysa sa 7, kaya nais naming ilipat sa kanan.

343
00:26:07,070 --> 00:26:13,640
Gusto naming makakuha ng sa 9 at ihambing 9 sa 10 at makita na 9 ay talagang mas mababa sa 10.

344
00:26:13,640 --> 00:26:16,210
Kaya muli, nais naming subukan upang ilipat sa kanan.

345
00:26:16,210 --> 00:26:20,350
Ngunit sa puntong ito, gusto naming mapansin na hindi namin sa isang null node.

346
00:26:20,350 --> 00:26:23,080
Wala doon. May walang kung saan ang 10 ay dapat na.

347
00:26:23,080 --> 00:26:29,360
Ito ay kung saan maaari naming iulat pagkabigo - na may ay talagang walang 10 sa tree.

348
00:26:29,360 --> 00:26:35,420
At sa wakas, sabihin sa pamamagitan ng kaso na kung saan kami ay sinusubukan upang maghanap 1 sa tree.

349
00:26:35,420 --> 00:26:38,790
Ito ay katulad sa kung ano ang mangyayari kung tinitingnan namin hanggang 10, maliban sa halip ng pagpunta sa kanan,

350
00:26:38,790 --> 00:26:41,260
kami ay pagpunta upang pumunta sa kaliwa.

351
00:26:41,260 --> 00:26:46,170
Magsisimula kami sa 7 at makita na 1 ay mas mababa kaysa sa 7, kaya naming ilipat sa kaliwa.

352
00:26:46,170 --> 00:26:51,750
Makuha namin ang 3 at makita na 1 ay mas mababa sa 3, kaya muling subukan namin upang ilipat sa kaliwa.

353
00:26:51,750 --> 00:26:59,080
Sa puntong ito, mayroon kaming null node, kaya muli maaari naming i-ulat ang pagkabigo.

354
00:26:59,080 --> 00:27:10,260
>> Kung mo gusto upang matuto nang higit pa tungkol sa mga binary puno,

355
00:27:10,260 --> 00:27:14,420
may isang buong grupo ng mga masaya maliit na problema na maaari mong gawin sa kanila.

356
00:27:14,420 --> 00:27:19,450
Iminumungkahi ko ang pagsasanay sa pagguhit ng mga diagram isa-by-isa

357
00:27:19,450 --> 00:27:21,910
at ng pagsunod sa pamamagitan ng lahat ng ibang hakbang,

358
00:27:21,910 --> 00:27:25,060
dahil ito ay darating sa sobrang-madaling-gamiting

359
00:27:25,060 --> 00:27:27,480
hindi lamang kapag ginagawa mo ang problema Huffman pag-encode set

360
00:27:27,480 --> 00:27:29,390
kundi pati na rin sa hinaharap kurso -

361
00:27:29,390 --> 00:27:32,220
lamang ang pag-aaral kung paano upang gumuhit ng mga istraktura ng data na ito at sa tingin sa pamamagitan ng mga problema

362
00:27:32,220 --> 00:27:38,000
may panulat at papel o, sa kasong ito, iPad at pluma.

363
00:27:38,000 --> 00:27:41,000
>> Sa puntong ito bagaman, kami ay upang ilipat sa gawin ang ilang mga coding na kasanayan

364
00:27:41,000 --> 00:27:44,870
at aktwal na maglaro na may mga puno ng binary at makita.

365
00:27:44,870 --> 00:27:52,150
Ako pagpunta upang lumipat pabalik sa aking computer.

366
00:27:52,150 --> 00:27:58,480
Para sa bahagi ng seksyon, sa halip ng paggamit ng CS50 Run o CS50 puwang,

367
00:27:58,480 --> 00:28:01,500
Ako pagpunta sa gamitin ang appliance.

368
00:28:01,500 --> 00:28:04,950
>> Ng pagsunod kasama ang mga detalye ng Set Problema,

369
00:28:04,950 --> 00:28:07,740
Nakikita ko na ako dapat upang buksan ang appliance,

370
00:28:07,740 --> 00:28:11,020
pumunta sa aking Dropbox folder, lumikha ng isang folder na tinatawag na Seksyon 7,

371
00:28:11,020 --> 00:28:15,730
at pagkatapos ay lumikha ng isang file na tinatawag na binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Narito kami. Mayroon akong appliance na bukas.

373
00:28:22,050 --> 00:28:25,910
Ako pupunta makuha ang isang terminal.

374
00:28:25,910 --> 00:28:38,250
Ako pagpunta upang pumunta sa folder Dropbox, gumawa ng isang direktoryo na tinatawag na section7,

375
00:28:38,250 --> 00:28:42,230
at makita ito lubos na walang laman.

376
00:28:42,230 --> 00:28:48,860
Ngayon ako pagpunta upang buksan ang binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Tama. Narito pumunta namin - walang laman na file.

378
00:28:51,750 --> 00:28:54,330
>> Natin bumalik sa detalye.

379
00:28:54,330 --> 00:28:59,850
Detalye ng humihiling sa upang lumikha ng isang bagong uri ng kahulugan

380
00:28:59,850 --> 00:29:03,080
para sa isang binary puno node na naglalaman ng mga int halaga -

381
00:29:03,080 --> 00:29:07,110
tulad ng ang halaga na iginuhit namin sa aming balangkas bago.

382
00:29:07,110 --> 00:29:11,740
Kami ay pagpunta sa gamitin ang boilerplate na ito typedef na ginawa namin dito mismo

383
00:29:11,740 --> 00:29:14,420
na dapat mong makilala mula Problema Set 5 -

384
00:29:14,420 --> 00:29:19,190
kung ginawa mo ang hash na paraan ng talahanayan ng mapanakop ang programa speller.

385
00:29:19,190 --> 00:29:22,540
Dapat mo ring makilala ang mga ito mula sa seksyon ng huling linggo ng

386
00:29:22,540 --> 00:29:23,890
kung saan usapan natin ang tungkol sa mga naka-link na listahan.

387
00:29:23,890 --> 00:29:27,870
Mayroon kaming ang typedef na ito ng isang struct node,

388
00:29:27,870 --> 00:29:34,430
at Nagbigay kami ng struct node na ito ang pangalan ng struct node muna

389
00:29:34,430 --> 00:29:39,350
upang maaari naming sumangguni sa ito dahil lilikha kami gusto mong payo struct node

390
00:29:39,350 --> 00:29:45,740
bilang bahagi ng aming mga struct, ngunit pagkatapos namin libid ito -

391
00:29:45,740 --> 00:29:47,700
o sa halip, nakapaloob na ito - sa isang typedef

392
00:29:47,700 --> 00:29:54,600
sa gayon ay, mamaya sa code, maaari naming sumangguni sa struct na ito bilang lamang node sa halip ng isang struct node.

393
00:29:54,600 --> 00:30:03,120
>> Ito ay katulad na katulad sa isa-isa naka-link na listahan kahulugan na nakita natin noong nakaraang linggo.

394
00:30:03,120 --> 00:30:20,070
Upang gawin ito, sabihin lamang magsimula sa pamamagitan ng pagsusulat ang boilerplate.

395
00:30:20,070 --> 00:30:23,840
Alam namin na mayroon kami ng isang integer value,

396
00:30:23,840 --> 00:30:32,170
kaya ipapakita namin ilalagay sa int halaga, at pagkatapos ay sa halip ng pagkakaroon ng isa lamang pointer sa susunod na elemento -

397
00:30:32,170 --> 00:30:33,970
namin ginawa na may isa-isa-naka-link na listahan -

398
00:30:33,970 --> 00:30:38,110
kami ay pagpunta sa kaliwa at kanang mga payo sa anak.

399
00:30:38,110 --> 00:30:42,880
Na medyo simple masyadong - struct node * kaliwang anak;

400
00:30:42,880 --> 00:30:51,190
at struct node * kanang bata;. Cool.

401
00:30:51,190 --> 00:30:54,740
Na mukhang isang medyo magandang simula.

402
00:30:54,740 --> 00:30:58,530
Natin bumalik sa detalye.

403
00:30:58,530 --> 00:31:05,030
>> Ngayon ay kailangan namin upang idedeklara ang isang pandaigdigang node * variable para sa root ng isang puno.

404
00:31:05,030 --> 00:31:10,590
Kami ay pagpunta upang gawin ang pandaigdigang lamang tulad ng ginawa namin ang unang pointer sa aming naka-link na listahan din pandaigdigang.

405
00:31:10,590 --> 00:31:12,690
Ito ay na sa function na magsulat namin

406
00:31:12,690 --> 00:31:16,180
hindi namin upang panatilihin ang pagpasa sa paligid ng ugat na ito -

407
00:31:16,180 --> 00:31:19,620
kahit na makikita namin makita na kung gagawin mo nais na magsulat ng mga function na ito recursively,

408
00:31:19,620 --> 00:31:22,830
maaari itong maging mas mahusay na kahit hindi pumasa ito bilang isang pandaigdigang sa unang lugar

409
00:31:22,830 --> 00:31:28,090
at sa halip ay initialize ito nang lokal sa iyong pangunahing function na.

410
00:31:28,090 --> 00:31:31,960
Ngunit, makikita namin gawin ito sa buong mundo upang magsimula.

411
00:31:31,960 --> 00:31:39,920
Muli, makikita namin magbigay ng ilang mga puwang, at ako pagpunta upang idedeklara ng node * ugat.

412
00:31:39,920 --> 00:31:46,770
Lamang upang tiyakin na hindi ko iwanan ang uninitialized, Pupunta ako upang itakda ang katumbas ng null.

413
00:31:46,770 --> 00:31:52,210
Ngayon, sa pangunahing function na - na magpapadala kami sumulat talagang mabilis dito mismo -

414
00:31:52,210 --> 00:32:00,450
int pangunahing (int argc, const magpasinda * argv []) -

415
00:32:00,450 --> 00:32:10,640
at ako pagpunta upang simulan ang deklarasyon ng aking argv array bilang const lang kaya na alam ko

416
00:32:10,640 --> 00:32:14,550
ang mga argumento argumento na ako malamang na hindi nais na baguhin ang.

417
00:32:14,550 --> 00:32:18,390
Kung gusto kong baguhin ang mga ito ang dapat kong marahil paggawa ng mga kopya ng mga ito.

418
00:32:18,390 --> 00:32:21,740
Makikita mo ang marami sa code.

419
00:32:21,740 --> 00:32:25,440
Ang fine alinman paraan. Masarap na mag-iwan ang mga ito bilang - alisin ang const kung nais mong.

420
00:32:25,440 --> 00:32:28,630
Ko karaniwang ilagay ang mga ito sa loob lamang ng sa gayon na ipaalala ko sa aking sarili

421
00:32:28,630 --> 00:32:33,650
 na hindi ko marahil gusto mong baguhin ang mga argumento.

422
00:32:33,650 --> 00:32:39,240
>> Tulad ng nakasanayan, ako pagpunta sa isama ito return 0 linya sa dulo ng pangunahing.

423
00:32:39,240 --> 00:32:45,730
Narito, ako initialize ang aking na root node.

424
00:32:45,730 --> 00:32:48,900
Bilang ito nakatayo ngayon, Mayroon akong isang pointer na nakatakda sa null,

425
00:32:48,900 --> 00:32:52,970
kaya ng pagturo sa wala.

426
00:32:52,970 --> 00:32:57,480
Upang aktwal na simulan ang pagbuo ng node,

427
00:32:57,480 --> 00:32:59,250
Ko kailangan muna upang magtalaga ng memory para dito.

428
00:32:59,250 --> 00:33:05,910
Ako pagpunta sa gawin na sa pamamagitan ng paggawa ng memory sa magbunton gamit ang malloc.

429
00:33:05,910 --> 00:33:10,660
Ako pagpunta upang i-set ang ugat katumbas sa resulta ng malloc,

430
00:33:10,660 --> 00:33:19,550
at ako pagpunta upang gamitin ang sizeof operator upang makalkula ang laki ng isang node.

431
00:33:19,550 --> 00:33:24,990
Ang dahilan na gamitin ko sizeof node bilang kabaligtaran sa, sabihin nating,

432
00:33:24,990 --> 00:33:37,020
paggawa ng isang bagay tulad nito - malloc (4 + 4 +4) o malloc 12 -

433
00:33:37,020 --> 00:33:40,820
dahil gusto ko ang aking code sa tugma hangga't maaari.

434
00:33:40,820 --> 00:33:44,540
Gusto ko ito. File c, makatipon ito sa appliance,

435
00:33:44,540 --> 00:33:48,820
at pagkatapos ay makatipon ito sa aking 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
o sa isang ganap na iba't ibang mga arkitektura -

437
00:33:52,040 --> 00:33:54,640
at gusto ko ang lahat ng ito upang gumana sa parehong.

438
00:33:54,640 --> 00:33:59,510
>> Kung ako sa paggawa ng mga pagpapalagay tungkol sa laki ng mga variable -

439
00:33:59,510 --> 00:34:02,070
ang laki ng isang int o ang laki ng isang pointer -

440
00:34:02,070 --> 00:34:06,070
pagkatapos rin ako sa paggawa ng mga pagpapalagay tungkol sa mga uri ng mga architectures

441
00:34:06,070 --> 00:34:10,440
kung saan ang aking code ay maaaring matagumpay na makatipon kapag nagpatakbo.

442
00:34:10,440 --> 00:34:15,030
Palaging gamitin ang sizeof bilang kabaligtaran nang manu-mano sa summing ang mga patlang ng struct.

443
00:34:15,030 --> 00:34:20,500
Ang iba pang dahilan ay na maaaring may padding na tagatala Inilalagay ng sa struct.

444
00:34:20,500 --> 00:34:26,570
Kahit lamang summing ang mga indibidwal na mga patlang ay hindi isang bagay na karaniwan kang gustong gawin,

445
00:34:26,570 --> 00:34:30,340
ito, tanggalin ang linya na iyon.

446
00:34:30,340 --> 00:34:33,090
Ngayon, sa talagang initialize na root node na ito,

447
00:34:33,090 --> 00:34:36,489
Ako pagpunta sa mag-plug ng mga halaga para sa bawat isa ng mga iba't ibang mga patlang.

448
00:34:36,489 --> 00:34:41,400
Halimbawa, para sa halaga na alam ko na gusto kong i-initialize sa 7,

449
00:34:41,400 --> 00:34:46,920
at sa ngayon ako upang itakda ang kaliwang anak na null

450
00:34:46,920 --> 00:34:55,820
at ang karapatan ng bata sa ring maging null. Magaling!

451
00:34:55,820 --> 00:35:02,670
Ginawa namin na bahagi ng spec.

452
00:35:02,670 --> 00:35:07,390
>> Ang pagtutukoy sa ibaba ng pahina 3 ay nagtatanong sa akin upang lumikha ng tatlong higit pang mga node -

453
00:35:07,390 --> 00:35:10,600
isa na naglalaman ng 3, isa na naglalaman ng 6, at isa na may 9 na -

454
00:35:10,600 --> 00:35:14,210
at pagkatapos wire up ang mga ito kaya hitsura nang eksakto tulad ng ating puno diagram

455
00:35:14,210 --> 00:35:17,120
na namin ang pakikipag-usap tungkol sa dati.

456
00:35:17,120 --> 00:35:20,450
Natin gawin na medyo mabilis dito.

457
00:35:20,450 --> 00:35:26,270
Makikita mo ang talagang mabilis na ako upang simulan ang pagsusulat ng isang bungkos ng mga nauulit na code.

458
00:35:26,270 --> 00:35:32,100
Pupunta ako upang lumikha ng isang node * at ako pagpunta sa tumawag ito tatlong.

459
00:35:32,100 --> 00:35:36,000
Ako pagpunta upang itakda ang katumbas ng malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Ako pagpunta upang itakda ang tatlong> halaga = 3.

461
00:35:41,070 --> 00:35:54,780
Tatlong -> left_child = null; tatlong -> kanan _child = null; pati na rin.

462
00:35:54,780 --> 00:36:01,150
Na mukhang medyo katulad sa Sinisimulan ang ugat, at iyon mismo ang

463
00:36:01,150 --> 00:36:05,760
Ako pagpunta sa gawin kung sisimulan ko Sinisimulan ng 6 at 9 pati na rin.

464
00:36:05,760 --> 00:36:20,720
Ko na talagang mabilis dito - aktwal na, ako pagpunta sa gawin ang isang maliit na kopyahin at i-paste ang,

465
00:36:20,720 --> 00:36:46,140
at tiyakin na ako - oo.

466
00:36:46,470 --> 00:37:09,900
 Ngayon, ko na nakuha ko kopyahin at maaari kong magpatuloy at itakda ito katumbas ng 6.

467
00:37:09,900 --> 00:37:14,670
Maaari mong makita na ito ay tumatagal ng sandali at hindi super-mahusay.

468
00:37:14,670 --> 00:37:22,610
Sa loob lamang ng ilang sandali, makikita namin magsulat ng isang function na gawin ito para sa amin.

469
00:37:22,610 --> 00:37:32,890
Gusto kong palitan ito na may 9, palitan na na may 6.

470
00:37:32,890 --> 00:37:37,360
>> Ngayon Mayroon namin ang lahat ng aming mga node nilikha at nasimulan.

471
00:37:37,360 --> 00:37:41,200
Mayroon namin ang aming ugat-set katumbas ng 7, o naglalaman ng mga halaga 7,

472
00:37:41,200 --> 00:37:46,510
aming node naglalaman 3, ang aming node na naglalaman ng 6, at ang aming node na naglalaman 9.

473
00:37:46,510 --> 00:37:50,390
Sa puntong ito, ang lahat ng kami ay may sa gawin ay ang lahat ng wire up.

474
00:37:50,390 --> 00:37:53,020
Ang dahilan kung bakit ko nasimulan ang lahat ng mga payo sa null lamang sa gayon ay gumawa ako sigurado na

475
00:37:53,020 --> 00:37:56,260
Wala akong anumang uninitialized pointer sa doon sa pamamagitan ng aksidente.

476
00:37:56,260 --> 00:38:02,290
At din dahil, sa puntong ito, ako lamang magkaroon ng aktwal na ikonekta ang mga node sa bawat isa -

477
00:38:02,290 --> 00:38:04,750
sa mga na aktwal na sila ay konektado sa - hindi ko upang pumunta sa pamamagitan at gumawa

478
00:38:04,750 --> 00:38:08,240
siguraduhin na ang lahat ng mga nulls ay doon sa naaangkop na lugar.

479
00:38:08,240 --> 00:38:15,630
>> Simula sa root, alam ko na kaliwang bata ay ang root ng 3.

480
00:38:15,630 --> 00:38:21,250
Alam ko na ang kanang bata root 9.

481
00:38:21,250 --> 00:38:24,880
Pagkatapos nito, ang lamang ang iba pang mga anak na ako pakaliwa mag-alala tungkol

482
00:38:24,880 --> 00:38:39,080
kanang 3 anak, na 6.

483
00:38:39,080 --> 00:38:44,670
Sa puntong ito, ang lahat ng mukhang medyo magandang.

484
00:38:44,670 --> 00:38:54,210
Tatanggalin namin ang ilan sa mga linyang ito.

485
00:38:54,210 --> 00:38:59,540
Ngayon lahat mukhang medyo magandang.

486
00:38:59,540 --> 00:39:04,240
Natin bumalik sa aming mga pagtutukoy at makita kung ano ang namin ang susunod na gagawin.

487
00:39:04,240 --> 00:39:07,610
>> Sa puntong ito, mayroon kaming upang magsulat ng isang function na tinatawag na 'ay naglalaman ng'

488
00:39:07,610 --> 00:39:14,150
may ng prototype ng 'bool naglalaman ng (int value)'.

489
00:39:14,150 --> 00:39:17,060
At ito ay naglalaman ng function ay nagbabalik ng tunay

490
00:39:17,060 --> 00:39:21,200
 kung ang puno ang tulis ng aming global variable ugat

491
00:39:21,200 --> 00:39:26,950
 naglalaman ng halaga ang naipasa sa function at maling kung hindi man.

492
00:39:26,950 --> 00:39:29,000
Natin magpatuloy at gawin iyon.

493
00:39:29,000 --> 00:39:35,380
Ito ay eksakto tulad ng lookup na ginawa namin sa pamamagitan ng kamay sa iPad ng kaunti lamang ang nakalipas.

494
00:39:35,380 --> 00:39:40,130
Natin mag-zoom sa ilang sandali at mag-scroll pataas.

495
00:39:40,130 --> 00:39:43,130
Kami ay pagpunta sa ilagay ito function na itaas ang aming pangunahing function na

496
00:39:43,130 --> 00:39:48,990
sa gayon ay hindi namin upang gawin ang anumang uri ng prototyping.

497
00:39:48,990 --> 00:39:55,960
Kaya, bool naglalaman (int value).

498
00:39:55,960 --> 00:40:00,330
Doon kami. May aming boilerplate deklarasyon.

499
00:40:00,330 --> 00:40:02,900
Lamang upang tiyakin na ito ay makatipon,

500
00:40:02,900 --> 00:40:06,820
Ako sige at itakda ito katumbas ng bumalik false.

501
00:40:06,820 --> 00:40:09,980
Sa ngayon function na ito ay hindi gawin at laging iulat na

502
00:40:09,980 --> 00:40:14,010
ang halaga na kaming naghahanap ng mga hindi sa tree.

503
00:40:14,010 --> 00:40:16,280
>> Sa puntong ito, marahil ito ay isang magandang ideya -

504
00:40:16,280 --> 00:40:19,600
dahil namin ang nakasulat na isang buong grupo ng mga code at hindi pa namin kahit na sinubukan ng pagsubok ko pa ito -

505
00:40:19,600 --> 00:40:22,590
upang matiyak na ang lahat ng ito compiles.

506
00:40:22,590 --> 00:40:27,460
May ilang mga bagay na mayroon kaming gawin upang tiyakin na ito ay aktwal na makatipon.

507
00:40:27,460 --> 00:40:33,530
Una, tingnan kung namin ang paggamit ng anumang mga function sa anumang mga aklatan na hindi pa namin na-kasama.

508
00:40:33,530 --> 00:40:37,940
Ang mga pagpapaandar na ginamit namin ang sa ngayon ay malloc,

509
00:40:37,940 --> 00:40:43,310
at pagkatapos rin namin na paggamit ng ganitong uri - ito hindi karaniwang uri ng tinatawag na 'bool' -

510
00:40:43,310 --> 00:40:45,750
na kasama sa standard bool header ng file.

511
00:40:45,750 --> 00:40:53,250
Talagang nais namin upang isama ang standard na bool.h para sa bool uri,

512
00:40:53,250 --> 00:40:59,230
at gusto rin naming # include standard lib.h para sa standard na mga aklatan

513
00:40:59,230 --> 00:41:03,530
na ang malloc, at libre, at ang lahat ng na.

514
00:41:03,530 --> 00:41:08,660
Kaya, mag-zoom out, namin na umalis.

515
00:41:08,660 --> 00:41:14,190
Natin subukan at tiyakin na ito ay aktwal na ginawa makatipon.

516
00:41:14,190 --> 00:41:18,150
Nakikita namin na ito, kaya kami sa kanan track.

517
00:41:18,150 --> 00:41:22,990
>> Natin buksan up binary_tree.c muli.

518
00:41:22,990 --> 00:41:34,530
Ito compiles. Natin pumunta down at tiyakin na namin magpasok ng ilang mga tawag sa aming naglalaman ng function na -

519
00:41:34,530 --> 00:41:40,130
lamang upang tiyakin na na ang lahat ng mahusay at magandang.

520
00:41:40,130 --> 00:41:43,170
Halimbawa, kapag ginawa namin ang ilang mga lookup sa aming puno kanina,

521
00:41:43,170 --> 00:41:48,500
sinubukan naming hanapin ang mga halaga 6, 10, at 1, at alam namin na 6 sa tree,

522
00:41:48,500 --> 00:41:52,220
10 ay hindi sa tree, at 1 ay hindi sa tree alinman.

523
00:41:52,220 --> 00:41:57,230
Gamitin natin ang mga tawag ng sample bilang isang paraan upang malaman kung man o hindi

524
00:41:57,230 --> 00:41:59,880
aming naglalaman ng function ay gumagana.

525
00:41:59,880 --> 00:42:05,210
Upang gawin iyon, ako pagpunta sa gamitin ang printf function na,

526
00:42:05,210 --> 00:42:10,280
at kami ay pagpunta upang i-print ang resulta ng tawag sa ay naglalaman ng.

527
00:42:10,280 --> 00:42:13,280
Ako pagpunta sa ilagay sa isang string "ay naglalaman ng (% d) = dahil

528
00:42:13,280 --> 00:42:20,470
 kami ay pagpunta sa plug sa ang halaga na kami ay pagpunta upang hanapin,

529
00:42:20,470 --> 00:42:27,130
at =% s \ n "at gamitin na bilang aming format string.

530
00:42:27,130 --> 00:42:30,720
Kami ay pagpunta upang makita - literal-print sa screen -

531
00:42:30,720 --> 00:42:32,060
kung ano ang hitsura tulad ng function na tawag.

532
00:42:32,060 --> 00:42:33,580
Ito ay hindi tunay ang function na tawag.

533
00:42:33,580 --> 00:42:36,760
 Ito ay isang string na dinisenyo upang hitsura ng isang tawag ng function na.

534
00:42:36,760 --> 00:42:41,140
>> Ngayon, kami ay pagpunta sa plug sa ang mga halaga.

535
00:42:41,140 --> 00:42:43,580
Kami ay pagpunta sa subukan naglalaman ng sa 6,

536
00:42:43,580 --> 00:42:48,340
at pagkatapos ay kung ano ang kami ay pagpunta sa gawin dito ay gamitin na tatluhan operator.

537
00:42:48,340 --> 00:42:56,340
Natin makita - naglalaman ng 6 - kaya, ngayon ko na nilalaman ng 6 at kung naglalaman ng 6 ay totoo,

538
00:42:56,340 --> 00:43:01,850
ang string na kami ay pagpunta sa magpadala sa format ng character ang% s

539
00:43:01,850 --> 00:43:04,850
ay ang string na "true".

540
00:43:04,850 --> 00:43:07,690
Sabihin mag-scroll sa paglipas ng ilang sandali.

541
00:43:07,690 --> 00:43:16,210
Kung hindi man, nais naming upang magpadala ng mga string "false" kung naglalaman ng 6 return false.

542
00:43:16,210 --> 00:43:19,730
Ito ay isang maliit na maloko na anyo, ngunit malaman ko maaaring ko pati na rin ilarawan

543
00:43:19,730 --> 00:43:23,780
kung ano ang tatluhan operator Mukhang dahil hindi namin nakita ang mga ito para sa sandali.

544
00:43:23,780 --> 00:43:27,670
Ito ay gandang, madaling gamiting paraan upang malaman kung gumagana ang aming naglalaman ng function ay.

545
00:43:27,670 --> 00:43:30,040
Pupunta ako upang mag-scroll sa kaliwa,

546
00:43:30,040 --> 00:43:39,900
at ako pagpunta sa kopyahin at i-paste ang linyang ito ng ilang beses.

547
00:43:39,900 --> 00:43:44,910
Ito ay nagbago ang ilan sa mga halagang ito sa paligid,

548
00:43:44,910 --> 00:43:59,380
kaya ito ay pagpunta sa 1, at ito ay pagpunta sa 10.

549
00:43:59,380 --> 00:44:02,480
>> Sa puntong ito Mayroon namin ang gandang function na naglalaman ng.

550
00:44:02,480 --> 00:44:06,080
Mayroon kaming ilang mga pagsubok, at makikita namin makita kung ito ang lahat ng mga gawa.

551
00:44:06,080 --> 00:44:08,120
Sa puntong ito namin ang nakasulat na ilang higit pang mga code.

552
00:44:08,120 --> 00:44:13,160
Oras na umalis at tiyakin na ang lahat pa rin compiles.

553
00:44:13,160 --> 00:44:20,360
Quit out, at ngayon sabihin subukan ang paggawa ng puno ng binary muli.

554
00:44:20,360 --> 00:44:22,260
Well, mukhang kami nakakuha ng isang error,

555
00:44:22,260 --> 00:44:26,930
at hindi na namin Mayroon ito tahasang deklarasyon sa library function na printf.

556
00:44:26,930 --> 00:44:39,350
Mukhang kailangan namin upang pumunta sa at # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
At sa na, ang lahat ay dapat makatipon. Hindi namin ang lahat ng mabuti.

558
00:44:45,350 --> 00:44:50,420
Ngayon ipaalam sa subukan ang pagpapatakbo ng binary puno at makita kung ano ang mangyayari.

559
00:44:50,420 --> 00:44:53,520
Narito ang namin,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
at makita namin na, bilang inaasahan namin -

561
00:44:55,190 --> 00:44:56,910
dahil hindi pa namin ipinatupad naglalaman pa,

562
00:44:56,910 --> 00:44:59,800
o sa halip, lamang namin ang ilagay sa return false -

563
00:44:59,800 --> 00:45:03,300
nakikita namin na lamang ito bumabalik maling para sa lahat ng mga ito,

564
00:45:03,300 --> 00:45:06,180
kaya na sa lahat ng nagtatrabaho para sa pinaka-bahagi may kabutihan.

565
00:45:06,180 --> 00:45:11,860
>> Natin bumalik at aktwal na ipatupad naglalaman sa puntong ito.

566
00:45:11,860 --> 00:45:17,490
Pupunta ako mag-scroll pababa, mag-zoom in, at -

567
00:45:17,490 --> 00:45:22,330
Tandaan, ang algorithm na ginamit namin ay na namin na nagsimula sa root node

568
00:45:22,330 --> 00:45:28,010
at pagkatapos ay sa bawat node na aming nakatagpo, gawin namin ang isang paghahambing,

569
00:45:28,010 --> 00:45:32,380
at batay sa paghahambing na namin alinman ilipat sa kaliwa anak o sa kanan anak.

570
00:45:32,380 --> 00:45:39,670
Ito ay pagpunta upang tumingin na halos kapareho sa code ng paghahanap ng binary na namin sinulat ni mas maaga sa ang termino.

571
00:45:39,670 --> 00:45:47,810
Kapag nagsimula kami off, alam namin na gusto naming upang i-hold sa sa kasalukuyang node

572
00:45:47,810 --> 00:45:54,050
na namin ang pagtingin sa, at ang kasalukuyang node ay pagpunta sa nasimulan sa root ang node.

573
00:45:54,050 --> 00:45:56,260
At ngayon, kami ay pagpunta sa patuloy na pagpunta sa pamamagitan ng puno,

574
00:45:56,260 --> 00:45:58,140
at tandaan na ang aming pagtigil kondisyon -

575
00:45:58,140 --> 00:46:01,870
 kapag aktwal na namin nagtrabaho sa pamamagitan ng halimbawa sa pamamagitan ng kamay -

576
00:46:01,870 --> 00:46:03,960
ay kapag kami nakatagpo ng isang null node,

577
00:46:03,960 --> 00:46:05,480
hindi kapag kami ay tumingin sa isang null anak,

578
00:46:05,480 --> 00:46:09,620
kundi kapag namin ang aktwal na inilipat sa isang node sa tree

579
00:46:09,620 --> 00:46:12,640
at natagpuan na hindi namin sa isang null node.

580
00:46:12,640 --> 00:46:20,720
Kami ay pagpunta sa umulit hanggang kuprum ay hindi katumbas ng null.

581
00:46:20,720 --> 00:46:22,920
At kung ano ang namin gawin?

582
00:46:22,920 --> 00:46:31,610
Kami ay pagpunta upang subukan kung (kuprum -> halaga == halaga),

583
00:46:31,610 --> 00:46:35,160
alam namin na aktwal na nalaman namin na node na kaming naghahanap ng para sa.

584
00:46:35,160 --> 00:46:40,450
Kaya dito, maaari naming nagbabalik ng tunay.

585
00:46:40,450 --> 00:46:49,830
Kung hindi man, nais namin upang makita kung o hindi ang halaga ay mas mababa kaysa sa halaga.

586
00:46:49,830 --> 00:46:53,850
Kung ang halaga ang kasalukuyang node ay mas mababa kaysa sa halaga kaming naghahanap para sa,

587
00:46:53,850 --> 00:46:57,280
kami ay pagpunta sa ilipat sa kanan.

588
00:46:57,280 --> 00:47:10,600
Kaya, kuprum = kuprum -> right_child; at kung hindi man, kami ay pagpunta sa ilipat sa kaliwa.

589
00:47:10,600 --> 00:47:17,480
kuprum = kuprum -> left_child;. Medyo simple.

590
00:47:17,480 --> 00:47:22,830
>> Maaaring makilala ang loop na mukhang na halos kapareho sa ito mula sa

591
00:47:22,830 --> 00:47:27,580
binary paghahanap nang mas maaga sa ang termino, maliban pagkatapos namin ay pagharap sa mababa, kalagitnaan, at mataas.

592
00:47:27,580 --> 00:47:30,000
Narito, kami na lang ay upang tumingin sa isang kasalukuyang halaga,

593
00:47:30,000 --> 00:47:31,930
kaya maganda at simpleng.

594
00:47:31,930 --> 00:47:34,960
Tiyakin nating ang code na ito ay gumagana.

595
00:47:34,960 --> 00:47:42,780
Una, tiyakin na ito compiles. Mukhang ginagawa nito.

596
00:47:42,780 --> 00:47:47,920
Natin subukang patakbuhin ito.

597
00:47:47,920 --> 00:47:50,160
At katunayan, mga Kopya ang lahat na aming inaasahan.

598
00:47:50,160 --> 00:47:54,320
Nahahanap nito 6 sa tree, hindi mahanap ang 10 dahil sa 10 hindi sa tree,

599
00:47:54,320 --> 00:47:57,740
at hindi mahanap 1 alinman dahil 1 Hindi rin sa tree.

600
00:47:57,740 --> 00:48:01,420
Cool na bagay.

601
00:48:01,420 --> 00:48:04,470
>> Tama. Natin bumalik sa aming mga pagtutukoy at makita kung ano ang susunod.

602
00:48:04,470 --> 00:48:07,990
Ngayon, nais upang magdagdag ng ilang higit pang mga node sa aming puno.

603
00:48:07,990 --> 00:48:11,690
Gustong idagdag 5, 2, at 8, at tiyakin na ang aming naglalaman ng code

604
00:48:11,690 --> 00:48:13,570
gumagana pa rin tulad ng inaasahan.

605
00:48:13,570 --> 00:48:14,900
Sabihin pumunta gawin iyon.

606
00:48:14,900 --> 00:48:19,430
Sa puntong ito, sa halip ng paggawa ng muli na nakakainis na kopya at i-paste ang,

607
00:48:19,430 --> 00:48:23,770
sabihin magsulat ng isang function na sa aktwal na lumikha ng isang node.

608
00:48:23,770 --> 00:48:27,740
Kung mag-scroll namin ang lahat ng mga paraan sa pangunahing, nakikita namin na namin ang paggawa nito

609
00:48:27,740 --> 00:48:31,210
katulad code nang paulit-ulit sa bawat oras na nais namin upang lumikha ng isang node.

610
00:48:31,210 --> 00:48:39,540
>> Natin magsulat ng isang function na aktwal na bumuo ng isang node para sa amin at ibalik ito.

611
00:48:39,540 --> 00:48:41,960
Ako pagpunta sa tumawag ito build_node.

612
00:48:41,960 --> 00:48:45,130
Ako pagpunta sa bumuo ng isang node na may partikular na halaga.

613
00:48:45,130 --> 00:48:51,040
Mag-zoom in dito.

614
00:48:51,040 --> 00:48:56,600
Ang unang bagay na ako pagpunta sa gawin ay aktwal na lumikha ng puwang para sa node sa magbunton.

615
00:48:56,600 --> 00:49:05,400
Kaya, node * n = malloc (sizeof (node)); n -> halaga = halaga;

616
00:49:05,400 --> 00:49:14,960
at pagkatapos dito, lamang ako pagpunta sa simulan ang lahat ng mga patlang sa naaangkop na halaga.

617
00:49:14,960 --> 00:49:22,500
At sa pinakadulo, babalik kami sa aming node.

618
00:49:22,500 --> 00:49:28,690
Tama. Ang isang bagay na dapat tandaan ay na ito andar dito mismo

619
00:49:28,690 --> 00:49:34,320
pagpunta sa ibalik ng pointer sa memory na magbunton-inilalaan.

620
00:49:34,320 --> 00:49:38,880
Ano ang maganda ang tungkol dito na ito node ngayon -

621
00:49:38,880 --> 00:49:42,420
namin na idedeklara ito sa magbunton dahil kung ipinahayag namin ito sa stack

622
00:49:42,420 --> 00:49:45,050
hindi namin magagawang upang gawin ito sa function na tulad nito.

623
00:49:45,050 --> 00:49:47,690
Memorya na gusto pumunta ng saklaw

624
00:49:47,690 --> 00:49:51,590
at ay hindi wasto kung sinubukan naming i-access ito sa ibang pagkakataon sa.

625
00:49:51,590 --> 00:49:53,500
Dahil kami ay deklarasyon magbunton-inilalaan memory,

626
00:49:53,500 --> 00:49:55,830
namin pagpunta sa pangangalaga ng pagbabakante ito sa ibang pagkakataon

627
00:49:55,830 --> 00:49:58,530
para sa aming programa upang hindi mahayag anumang memorya.

628
00:49:58,530 --> 00:50:01,270
Namin ang punting sa na para sa lahat ng iba pa sa code

629
00:50:01,270 --> 00:50:02,880
para lamang sa kapakanan simple sa oras,

630
00:50:02,880 --> 00:50:05,610
ngunit kung sakaling magsulat ng isang function na ganito ang hitsura

631
00:50:05,610 --> 00:50:10,370
kung saan mayroon kang - ilang tumawag ito malloc o realloc loob -

632
00:50:10,370 --> 00:50:14,330
nais mong tiyakin na inilagay mo ang ilang uri ng mga komento dito na nagsasabing,

633
00:50:14,330 --> 00:50:29,970
hey, alam mo, nagbabalik ng magbunton-inilalaan na node na nasimulan ang pumasa sa-in halaga.

634
00:50:29,970 --> 00:50:33,600
At pagkatapos ay nais mong tiyakin na inilagay mo sa ilang mga uri ng tandaan na nagsasabing

635
00:50:33,600 --> 00:50:41,720
tumatawag ay dapat magbakante ang ibinalik na memory.

636
00:50:41,720 --> 00:50:45,450
Sa ganoong paraan, kung ang isang tao man pupunta at gumagamit ng function na iyon,

637
00:50:45,450 --> 00:50:48,150
alam nila na kung ano ang makakuha ng bumalik sila mula sa andar

638
00:50:48,150 --> 00:50:50,870
sa ilang mga punto na kailangan na napalaya.

639
00:50:50,870 --> 00:50:53,940
>> Ipagpalagay na ang lahat ng mahusay at magandang dito,

640
00:50:53,940 --> 00:51:02,300
maaari naming pumunta sa aming code at palitan ang lahat ng mga linya dito mismo

641
00:51:02,300 --> 00:51:05,410
may mga tawag sa aming build node function na.

642
00:51:05,410 --> 00:51:08,170
Natin gawin na talagang mabilis.

643
00:51:08,170 --> 00:51:15,840
Ang isang bahagi na hindi namin upang palitan bahaging ito dito

644
00:51:15,840 --> 00:51:18,520
sa ilalim kung saan namin ang aktwal na wire ang node upang ituro sa bawat isa,

645
00:51:18,520 --> 00:51:21,030
dahil hindi namin maaaring gawin sa aming function na.

646
00:51:21,030 --> 00:51:37,400
Ngunit, sabihin gawin ugat = build_node (7); node * tatlong = build_node (3);

647
00:51:37,400 --> 00:51:47,980
node * anim = build_node (6); node * siyam = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
At ngayon, gusto din namin magdagdag ng mga node para sa -

649
00:51:52,590 --> 00:52:03,530
node * limang = build_node (5); node * walong = build_node (8);

650
00:52:03,530 --> 00:52:09,760
at kung ano ang iba pang mga node? Natin makikita dito. Nais naming ring magdagdag ng 2 -

651
00:52:09,760 --> 00:52:20,280
node * dalawang = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Tama. Sa puntong ito, alam namin na namin ang nakuha 7, ang 3, ang 9, at ang 6

653
00:52:26,850 --> 00:52:30,320
lahat ng naka-wire na naaangkop, ngunit kung ano ang tungkol sa 5, 8, at ang 2?

654
00:52:30,320 --> 00:52:33,550
Upang panatilihin ang lahat sa naaangkop na order,

655
00:52:33,550 --> 00:52:39,230
Alam namin na karapatan tatlong anak ay 6.

656
00:52:39,230 --> 00:52:40,890
Kaya, kung kami ay pagpunta upang idagdag ang 5,

657
00:52:40,890 --> 00:52:46,670
5 din nabibilang sa kanang bahagi ng puno na kung saan ay ang root ang 3,

658
00:52:46,670 --> 00:52:50,440
kaya 5 nabibilang bilang kaliwang anak ng 6.

659
00:52:50,440 --> 00:52:58,650
Maaari naming gawin ito sa pamamagitan ng sinasabi, anim -> left_child = limang;

660
00:52:58,650 --> 00:53:10,790
at pagkatapos ay ang 8 nabibilang bilang kaliwang anak ng 9, kaya siyam -> left_child = walong;

661
00:53:10,790 --> 00:53:22,190
at pagkatapos ay 2 kaliwang anak ng 3, kaya maaari naming gawin iyon up dito - sa iyo -> left_child = dalawang;.

662
00:53:22,190 --> 00:53:27,730
Kung hindi mo pa masyadong sundin kasama na, iminumungkahi ko kang gumuhit ito sa iyong sarili.

663
00:53:27,730 --> 00:53:35,660
>> Tama. Natin i-save ang. Sabihin pumunta at tiyaking ito compiles,

664
00:53:35,660 --> 00:53:40,760
at pagkatapos ay maaari naming idagdag sa aming mga tawag ay naglalaman ng.

665
00:53:40,760 --> 00:53:44,120
Mukhang lahat pa rin compiles.

666
00:53:44,120 --> 00:53:51,790
Natin pumunta at idagdag sa ilang ay naglalaman ng mga tawag.

667
00:53:51,790 --> 00:53:59,640
Muli, ako pagpunta sa gawin ng kaunti ng kopyahin at i-paste ang.

668
00:53:59,640 --> 00:54:15,860
Ngayon natin maghanap para sa 5, 8, at 2. Tama.

669
00:54:15,860 --> 00:54:28,330
Tiyakin nating na ito lahat ng mukhang mahusay pa rin. Magaling! I-save at mag-quit.

670
00:54:28,330 --> 00:54:33,220
Ngayon sabihin gumawa, makatipon, at ngayon sabihin patakbuhin.

671
00:54:33,220 --> 00:54:37,540
Mula sa mga resulta, mukhang lahat ay gumagana lamang maganda at mahusay na.

672
00:54:37,540 --> 00:54:41,780
Magaling! Kaya ngayon Mayroon namin ang aming naglalaman ng function na nakasulat.

673
00:54:41,780 --> 00:54:46,160
Sabihin ilipat sa at simulan ang nagtatrabaho sa kung paano upang ipasok ang mga node sa puno

674
00:54:46,160 --> 00:54:50,000
dahil, tulad ng ginagawa namin ito ngayon, bagay ang hindi masyadong medyo.

675
00:54:50,000 --> 00:54:52,280
>> Kung pumunta kami pabalik sa detalye,

676
00:54:52,280 --> 00:55:00,540
humihiling sa amin upang magsulat ng isang function na tinatawag na isingit - muli, bumabalik ng bool

677
00:55:00,540 --> 00:55:04,400
man o hindi kami maaaring aktwal na ipasok ang node sa puno -

678
00:55:04,400 --> 00:55:07,710
at pagkatapos ay ang halaga upang ipasok sa puno ay tinukoy bilang

679
00:55:07,710 --> 00:55:11,060
lamang ang argumento sa aming insert function na.

680
00:55:11,060 --> 00:55:18,180
Kami ay nagbabalik ng tunay na kung maaaring namin sa katunayan ipasok ang node na naglalaman ng halaga sa puno,

681
00:55:18,180 --> 00:55:20,930
na nangangahulugan na namin, isa, may sapat na memorya,

682
00:55:20,930 --> 00:55:24,840
at pagkatapos ng dalawang, ang node na ay hindi na umiiral sa tree dahil -

683
00:55:24,840 --> 00:55:32,170
Tandaan, hindi namin ay pumunta sa na magkaroon ng duplicate na mga halaga sa tree, lamang upang gawing simple ang mga bagay.

684
00:55:32,170 --> 00:55:35,590
Tama. Back sa ang code.

685
00:55:35,590 --> 00:55:44,240
Buksan ito. Mag-zoom sa isang bit, at pagkatapos ay mag-scroll pababa.

686
00:55:44,240 --> 00:55:47,220
Natin ilagay ang insert function na karapatan sa itaas ay naglalaman ng.

687
00:55:47,220 --> 00:55:56,360
Muli, ito ay pagpunta sa tinatawag na bool insert (int value).

688
00:55:56,360 --> 00:56:01,840
Bigyan ito ng kaunti pa sa espasyo, at pagkatapos, bilang isang default na,

689
00:56:01,840 --> 00:56:08,870
ipaalam sa ay ilagay sa return false sa pinakadulo.

690
00:56:08,870 --> 00:56:22,620
Ngayon pababa sa ibaba, sabihin sige at sa halip ng nang manu-mano ang pagbuo ng node

691
00:56:22,620 --> 00:56:27,900
sa pangunahing ating sarili at ang mga kable up ang mga ito upang tumuro sa bawat isa tulad ng ginagawa namin,

692
00:56:27,900 --> 00:56:30,600
makikita naming umasa sa aming insert function na upang gawin iyon.

693
00:56:30,600 --> 00:56:35,510
Hindi namin umasa sa aming insert function na bumuo ng ang buong puno mula sa simula pa,

694
00:56:35,510 --> 00:56:39,970
kundi magpapadala kami mapupuksa ng mga linyang ito - we'll magkomento ang mga linyang ito -

695
00:56:39,970 --> 00:56:43,430
na bumuo ng ang node 5, 8, at 2.

696
00:56:43,430 --> 00:56:55,740
At sa halip, gagamitin namin magpasok ng mga tawag sa aming insert function na

697
00:56:55,740 --> 00:57:01,280
upang matiyak na na aktwal na gumagana.

698
00:57:01,280 --> 00:57:05,840
Narito kami.

699
00:57:05,840 --> 00:57:09,300
>> Na namin ngayon ang nagkomento ang mga linya na ito.

700
00:57:09,300 --> 00:57:13,700
Lamang kami 7, 3, 9, at 6 sa aming puno sa puntong ito.

701
00:57:13,700 --> 00:57:18,870
Upang tiyakin na ito ay ang lahat ng nagtatrabaho,

702
00:57:18,870 --> 00:57:25,050
maaari naming mag-zoom out, aming binary puno,

703
00:57:25,050 --> 00:57:30,750
patakbuhin ang mga ito, at maaari naming makita na naglalaman ay ngayon na nagsasabi sa amin na hindi namin lubos na karapatan -

704
00:57:30,750 --> 00:57:33,110
5, 8, at 2 ay hindi na sa tree.

705
00:57:33,110 --> 00:57:37,960
Bumalik sa code,

706
00:57:37,960 --> 00:57:41,070
at kung paano namin upang ipasok?

707
00:57:41,070 --> 00:57:46,290
Tandaan kung ano ang ginawa namin kapag aktwal na namin ang pagpasok 5, 8, at 2 dati.

708
00:57:46,290 --> 00:57:50,100
Naglaro namin na Plinko laro kung saan namin na nagsimula sa root,

709
00:57:50,100 --> 00:57:52,780
nagpunta pababa sa puno ng isa sa pamamagitan ng isa sa pamamagitan ng isa

710
00:57:52,780 --> 00:57:54,980
hanggang sa nakita namin ang naaangkop na agwat,

711
00:57:54,980 --> 00:57:57,570
at pagkatapos namin wired sa node sa naaangkop na lugar.

712
00:57:57,570 --> 00:57:59,480
Kami ay pagpunta sa gawin ang parehong bagay.

713
00:57:59,480 --> 00:58:04,070
Ito ay isa lamang tulad ng pagsusulat ng code na ginamit namin sa ay naglalaman ng function na

714
00:58:04,070 --> 00:58:05,910
upang mahanap ang lugar kung saan node dapat,

715
00:58:05,910 --> 00:58:10,560
at pagkatapos lamang namin ay pagpunta upang ipasok ang node doon.

716
00:58:10,560 --> 00:58:17,000
Natin simulan ang paggawa na.

717
00:58:17,000 --> 00:58:24,200
>> Kaya mayroon kaming node * kuprum = ugat; lang kami sundin ay naglalaman ng code

718
00:58:24,200 --> 00:58:26,850
hanggang sa nakita namin na hindi ito lubos para sa amin.

719
00:58:26,850 --> 00:58:32,390
Kami ay pagpunta sa pumunta sa pamamagitan ng puno habang ang kasalukuyang elemento ay hindi null,

720
00:58:32,390 --> 00:58:45,280
at kung nakita namin ay katumbas sa halaga na kami ay sinusubukan upang ipasok ang halaga na kuprum -

721
00:58:45,280 --> 00:58:49,600
na rin, ito ay isa ng mga kaso kung saan ay hindi aktwal na namin ma-ipasok ang node

722
00:58:49,600 --> 00:58:52,730
sa puno dahil ang ibig sabihin nito ay mayroon kaming isang duplicate na halaga.

723
00:58:52,730 --> 00:58:59,010
Narito aktwal na kami ay pagpunta sa bumalik false.

724
00:58:59,010 --> 00:59:08,440
Ngayon, iba pa kung ang halaga kuprum ay mas mababa kaysa sa halaga,

725
00:59:08,440 --> 00:59:10,930
ngayon alam namin na ilipat namin sa kanan

726
00:59:10,930 --> 00:59:17,190
 dahil nabibilang sa kanang kalahati ng puno ng kuprum ang halaga.

727
00:59:17,190 --> 00:59:30,110
Kung hindi man, kami ay pagpunta sa ilipat sa kaliwa.

728
00:59:30,110 --> 00:59:37,980
Iyon ay talaga ang aming mga naglalaman ng gumana doon.

729
00:59:37,980 --> 00:59:41,820
>> Sa puntong ito, sa sandaling nakumpleto na namin ang habang loop na ito,

730
00:59:41,820 --> 00:59:47,350
aming kuprum pointer ay pagpunta sa na tumuturo sa null

731
00:59:47,350 --> 00:59:51,540
kung ang function ay hindi na ibinalik.

732
00:59:51,540 --> 00:59:58,710
Samakatuwid Nagkakaroon kami ng kuprum sa lugar kung saan nais namin upang ipasok ang bagong node.

733
00:59:58,710 --> 01:00:05,210
Ano ang nananatiling gawin sa aktwal na bumuo ng bagong node,

734
01:00:05,210 --> 01:00:08,480
kung saan maaari naming gawin medyo madali.

735
01:00:08,480 --> 01:00:14,930
Maaari naming gamitin ang aming super-madaling-gamiting build node function na,

736
01:00:14,930 --> 01:00:17,210
at isang bagay na hindi namin ginawa mas maaga -

737
01:00:17,210 --> 01:00:21,400
lang namin uri ng kinuha para sa ipinagkaloob ngunit gagawin namin ngayon lang masiguradong -

738
01:00:21,400 --> 01:00:27,130
ipapakita namin subukan upang tiyakin na ang halaga na ibinalik sa pamamagitan ng bagong node ay aktwal

739
01:00:27,130 --> 01:00:33,410
hindi null, dahil hindi namin nais upang simulan ang access na memorya kung ito ay null.

740
01:00:33,410 --> 01:00:39,910
Maaari naming subukan upang matiyak na ang bagong node ay hindi katumbas ng null.

741
01:00:39,910 --> 01:00:42,910
O sa halip, maaari lang namin makita kung ito talaga null,

742
01:00:42,910 --> 01:00:52,120
at kung ito ay null, maaari lang namin bumalik maling maaga pa.

743
01:00:52,120 --> 01:00:59,090
>> Sa puntong ito, mayroon kaming wire bagong node sa nito naaangkop na lugar sa tree.

744
01:00:59,090 --> 01:01:03,510
Kung titingnan namin pabalik sa pangunahing at kung saan kami ay talagang mga kable sa halaga bago,

745
01:01:03,510 --> 01:01:08,470
nakikita namin na ang paraan na aming ginagawa ito kapag gusto namin upang ilagay ang 3 sa tree

746
01:01:08,470 --> 01:01:11,750
namin access ang kaliwang anak ng ugat.

747
01:01:11,750 --> 01:01:14,920
Kapag inilalagay namin ang 9 sa tree, nagkaroon kami upang ma-access ang kanang anak ng root.

748
01:01:14,920 --> 01:01:21,030
Nagkaroon kami ng isang pointer sa magulang upang maglagay ng bagong halaga sa puno.

749
01:01:21,030 --> 01:01:24,430
Scroll-back up upang ipasok, na hindi pagpunta sa medyo gumana dito

750
01:01:24,430 --> 01:01:27,550
dahil hindi namin magkaroon ng isang magulang pointer.

751
01:01:27,550 --> 01:01:31,650
Ang gusto naming gawin ay, sa puntong ito,

752
01:01:31,650 --> 01:01:37,080
suriin ang halaga ng magulang at makita - mahusay, sus,

753
01:01:37,080 --> 01:01:41,990
kung ang halaga ng magulang ay mas mababa kaysa sa kasalukuyang halaga,

754
01:01:41,990 --> 01:01:54,440
pagkatapos kanang anak ng magulang ay dapat na ang bagong node;

755
01:01:54,440 --> 01:02:07,280
kung hindi man, kaliwang anak sa magulang ay dapat na ang bagong node.

756
01:02:07,280 --> 01:02:10,290
Subalit, hindi namin ito magulang pointer medyo pa.

757
01:02:10,290 --> 01:02:15,010
>> Upang makakuha ng ito, aktwal na kami ay pagpunta upang subaybayan ito bilang pumunta kami sa pamamagitan ng puno

758
01:02:15,010 --> 01:02:18,440
at hanapin ang naaangkop na lugar sa aming loop sa itaas.

759
01:02:18,440 --> 01:02:26,840
Maaari naming gawin iyon sa pamamagitan ng pag-scroll back up sa tuktok ng aming insert function na

760
01:02:26,840 --> 01:02:32,350
at pagsubaybay ng isa pang pointer variable tinatawag ang magulang.

761
01:02:32,350 --> 01:02:39,340
Kami ay pagpunta sa itakda ito katumbas null simula,

762
01:02:39,340 --> 01:02:43,640
at pagkatapos ay sa tuwing pumunta kami sa pamamagitan ng puno,

763
01:02:43,640 --> 01:02:51,540
kami ay pagpunta upang itakda ang pointer ng magulang upang tumugma sa kasalukuyang pointer.

764
01:02:51,540 --> 01:02:59,140
Itakda ang magulang katumbas sa kuprum.

765
01:02:59,140 --> 01:03:02,260
Sa ganitong paraan, sa bawat oras na pumunta kami sa pamamagitan ng,

766
01:03:02,260 --> 01:03:05,550
kami ay pagpunta upang matiyak na bilang ang kasalukuyang pointer ay nakakakuha incremented

767
01:03:05,550 --> 01:03:12,640
ang magulang pointer sumusunod - isang antas lamang na mas mataas kaysa sa kasalukuyang pointer sa tree.

768
01:03:12,640 --> 01:03:17,370
Na ang lahat ng mukhang medyo magandang.

769
01:03:17,370 --> 01:03:22,380
>> Tingin ko ang isang bagay na namin nais na ayusin ito bumuo ng node bumabalik null.

770
01:03:22,380 --> 01:03:25,380
Upang bumuo ng node sa aktwal na matagumpay na bumalik null,

771
01:03:25,380 --> 01:03:31,060
gagamitin namin upang baguhin ang code na iyon,

772
01:03:31,060 --> 01:03:37,270
dahil dito, hindi namin sinubukan upang matiyak na malloc nagbalik ng isang wastong pointer.

773
01:03:37,270 --> 01:03:53,390
Kaya, kung (n = null!), Pagkatapos -

774
01:03:53,390 --> 01:03:55,250
kung malloc nagbalik ng isang wastong pointer, makikita namin initialize ito;

775
01:03:55,250 --> 01:04:02,540
kung hindi man, kami lang bumalik at na bumabalik null para sa amin.

776
01:04:02,540 --> 01:04:13,050
Ngayon ang lahat ng mukhang medyo magandang. Natin tiyakin na ito aktwal na compiles.

777
01:04:13,050 --> 01:04:22,240
Puno na Magsagawa ng binary, at oh, Mayroon namin ang ilang mga bagay-bagay na pagpunta sa dito.

778
01:04:22,240 --> 01:04:29,230
>> Mayroon kaming isang implicit deklarasyon ng function na bumuo ng node.

779
01:04:29,230 --> 01:04:31,950
Muli, may mga compiler, kami ay pagpunta sa magsimula sa tuktok.

780
01:04:31,950 --> 01:04:36,380
Ano na dapat bang sabihin ay na ako pagtawag bumuo node bago aktwal ko na ito ipinahayag.

781
01:04:36,380 --> 01:04:37,730
Natin bumalik sa code talagang mabilis.

782
01:04:37,730 --> 01:04:43,510
Mag-scroll pababa, at bang sapat, ang aking insert function ay ipinahayag

783
01:04:43,510 --> 01:04:47,400
sa itaas ng mga katangian ng build node,

784
01:04:47,400 --> 01:04:50,070
ngunit ako sinusubukan upang gamitin ang bumuo ng node sa loob ng insert.

785
01:04:50,070 --> 01:05:06,610
Ako pagpunta sa pumunta sa at kopya - at pagkatapos ay i-paste ang function na build node paraan hanggang dito sa tuktok.

786
01:05:06,610 --> 01:05:11,750
Sa ganoong paraan, sana na gagana. Natin bigyan ito ng isa pang pumunta.

787
01:05:11,750 --> 01:05:18,920
Ngayon ang lahat ng ito compiles. Ang lahat ng mabuti.

788
01:05:18,920 --> 01:05:21,640
>> Ngunit sa puntong ito, hindi namin aktwal tinatawag na aming insert function na.

789
01:05:21,640 --> 01:05:26,510
Lang namin malaman na ito compiles, kaya sabihin pumunta sa at ilagay ang ilang mga tawag.

790
01:05:26,510 --> 01:05:28,240
Natin gawin iyon sa aming pangunahing function na.

791
01:05:28,240 --> 01:05:32,390
Dito, hindi namin Nagkomento ang 5, 8, at 2,

792
01:05:32,390 --> 01:05:36,680
at pagkatapos ay hindi namin ay wire up ang mga ito down na dito.

793
01:05:36,680 --> 01:05:41,640
Natin gumawa ng ilang mga tawag sa isingit,

794
01:05:41,640 --> 01:05:46,440
at sabihin ring gamitin ang parehong uri ng mga bagay-bagay na ginamit namin

795
01:05:46,440 --> 01:05:52,810
kapag ginawa namin mga printf tawag upang matiyak na ang lahat ay makapag-ipinasok maayos.

796
01:05:52,810 --> 01:06:00,550
Ako pagpunta sa kopyahin at i-paste,

797
01:06:00,550 --> 01:06:12,450
at sa halip na naglalaman kami ay pagpunta sa gawin ang insert.

798
01:06:12,450 --> 01:06:30,140
At sa halip ng 6, 10, at 1, kami ay pagpunta sa gamitin ang 5, 8, at 2.

799
01:06:30,140 --> 01:06:37,320
Ito ay dapat sana isingit 5, 8, at 2 sa puno.

800
01:06:37,320 --> 01:06:44,050
Makatipon. Ang lahat ng mabuti. Ngayon makikita na namin ang aktwal na patakbuhin ang aming programa.

801
01:06:44,050 --> 01:06:47,330
>> Lahat ibinalik maling.

802
01:06:47,330 --> 01:06:53,830
Kaya, 5, 8, at 2 ay hindi umalis, at mukhang naglalaman ng ay hindi makita ang mga ito sa alinman.

803
01:06:53,830 --> 01:06:58,890
Ano kaya ang nangyari? Natin mag-zoom out.

804
01:06:58,890 --> 01:07:02,160
Ang unang problema ay na insert tila bumalik false,

805
01:07:02,160 --> 01:07:08,750
at mukhang ito tulad na dahil iniwanan namin sa aming tawag return false,

806
01:07:08,750 --> 01:07:14,590
at hindi namin aktwal na ibinalik totoo.

807
01:07:14,590 --> 01:07:17,880
Maaari naming na-set up.

808
01:07:17,880 --> 01:07:25,290
Ang pangalawang problema ay, ngayon kahit na ginagawa namin - i-save ang, mag-quit ito,

809
01:07:25,290 --> 01:07:34,530
patakbuhin gumawa muli, ito makatipon, pagkatapos patakbuhin ito -

810
01:07:34,530 --> 01:07:37,670
nakikita namin na ang iba pa ay nangyari dito.

811
01:07:37,670 --> 01:07:42,980
Ang 5, 8, at 2 ay pa rin hindi kailanman matatagpuan sa tree.

812
01:07:42,980 --> 01:07:44,350
Kaya, ano ang nangyayari sa?

813
01:07:44,350 --> 01:07:45,700
>> Natin tingnan sa ito sa code.

814
01:07:45,700 --> 01:07:49,790
Natin makita kung maaari naming malaman ito.

815
01:07:49,790 --> 01:07:57,940
Simulan namin sa mga magulang na hindi null.

816
01:07:57,940 --> 01:07:59,510
Itinakda namin ang kasalukuyang pointer na katumbas sa root ang pointer,

817
01:07:59,510 --> 01:08:04,280
at kami ay pagpunta upang gumana ang aming paraan sa pamamagitan ng puno.

818
01:08:04,280 --> 01:08:08,650
Kung ang kasalukuyang node ay hindi null, pagkatapos naming malaman na maaari naming ilipat ng kaunti.

819
01:08:08,650 --> 01:08:12,330
Itinakda namin ang aming mga magulang pointer sa katumbas sa kasalukuyang pointer,

820
01:08:12,330 --> 01:08:15,420
sinuri ang halaga - kung ang mga halaga sa parehong ibinalik namin ang maling.

821
01:08:15,420 --> 01:08:17,540
Kung ang halaga ay mas mababa namin lumipat sa kanan;

822
01:08:17,540 --> 01:08:20,399
kung hindi man, kami ay inilipat sa kaliwa.

823
01:08:20,399 --> 01:08:24,220
Pagkatapos naming bumuo ng isang node. Kukunin ko na mag-zoom sa ilang sandali.

824
01:08:24,220 --> 01:08:31,410
At dito, kami ay pagpunta sa subukan sa wire up ang mga halaga sa parehong.

825
01:08:31,410 --> 01:08:37,250
Ano kaya ang nangyari? Natin makita kung posibleng Valgrind maaaring magbigay sa amin ng isang pahiwatig.

826
01:08:37,250 --> 01:08:43,910
>> Gusto ko upang gamitin Valgrind lamang dahil Valgrind talagang mabilis na tumatakbo

827
01:08:43,910 --> 01:08:46,729
at nagsasabi sa iyo kung mayroong anumang mga memory error.

828
01:08:46,729 --> 01:08:48,300
Kapag nagpatakbo namin Valgrind sa code,

829
01:08:48,300 --> 01:08:55,859
tulad ng maaari mong makita ang kanang here--Valgrind./binary_tree--and pindutin ang enter.

830
01:08:55,859 --> 01:09:03,640
Nakikita mo na hindi namin ang anumang mga error sa memorya, kaya mukhang lahat okay lang sa ngayon.

831
01:09:03,640 --> 01:09:07,529
Mayroon kaming ilang mga paglabas ng memorya, na alam namin, dahil hindi kami

832
01:09:07,529 --> 01:09:08,910
nangyayari sa magbakante anumang ng aming mga node.

833
01:09:08,910 --> 01:09:13,050
Natin subukang tumatakbo GDB upang makita kung ano ang aktwal na pagpunta sa.

834
01:09:13,050 --> 01:09:20,010
Gagawin namin ang gdb. / Binary_tree. Ito booted up lamang fine.

835
01:09:20,010 --> 01:09:23,670
Itakda natin ang hanay ng pahinga punto sa insert.

836
01:09:23,670 --> 01:09:28,600
Natin patakbuhin.

837
01:09:28,600 --> 01:09:31,200
Mukhang namin hindi aktwal na tinatawag na insert.

838
01:09:31,200 --> 01:09:39,410
Mukhang ang problema ay lamang na kapag ako ay nagbago dito sa pangunahing -

839
01:09:39,410 --> 01:09:44,279
lahat ng mga printf tawag mula naglalaman -

840
01:09:44,279 --> 01:09:56,430
Hindi ko kailanman aktwal Binago ang mga tawagan insert.

841
01:09:56,430 --> 01:10:01,660
Ngayon sabihin bigyan ito ng isang Subukan. Natin makatipon.

842
01:10:01,660 --> 01:10:09,130
Mukhang mahusay na ang lahat ng doon. Ngayon sabihin subukang patakbuhin ito, tingnan kung ano ang mangyayari.

843
01:10:09,130 --> 01:10:13,320
Oo! Lahat mukhang medyo magandang doon.

844
01:10:13,320 --> 01:10:18,130
>> Ang huling bagay na isipin ang tungkol ay, Mayroon bang anumang mga gilid kaso na ito insert?

845
01:10:18,130 --> 01:10:23,170
At ito ay lumiliko out na, na rin, ang isang kaso gilid na ay palaging kawili-wiling upang isipin ang tungkol

846
01:10:23,170 --> 01:10:26,250
ay, kung ano ang mangyayari kung ang iyong mga puno ay walang laman at tawagan mo ito ipasok ang function na?

847
01:10:26,250 --> 01:10:30,330
Ito gumagana? Well, sabihin subukan ito.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c -

849
01:10:32,110 --> 01:10:35,810
Ang paraan namin ay pagpunta upang subukan ito, kami ay pumunta sa aming pangunahing function na,

850
01:10:35,810 --> 01:10:41,690
at kaysa sa mga kable mga node tulad nito,

851
01:10:41,690 --> 01:10:56,730
lang kami magkomento ang buong bagay,

852
01:10:56,730 --> 01:11:02,620
at sa halip ng mga kable up ang node ating sarili,

853
01:11:02,620 --> 01:11:09,400
maaari naming aktwal lamang magpatuloy at tanggalin ang lahat ng ito.

854
01:11:09,400 --> 01:11:17,560
Kami ay pagpunta sa gumawa ang lahat ng tawag upang ipasok.

855
01:11:17,560 --> 01:11:49,020
Kaya, sabihin gawin - sa halip na 5, 8, at 2, kami ay upang ipasok 7, 3, at 9.

856
01:11:49,020 --> 01:11:58,440
At pagkatapos ay gagamitin din namin gusto mong magpasok ng 6 pati na rin.

857
01:11:58,440 --> 01:12:05,190
I-save. Mag-quit. Gumawa binary puno.

858
01:12:05,190 --> 01:12:08,540
Ang lahat ng ito compiles.

859
01:12:08,540 --> 01:12:10,320
Maaari lang namin patakbuhin ito bilang at makita kung ano ang mangyayari,

860
01:12:10,320 --> 01:12:12,770
ngunit din ito ng pagpunta sa talagang mahalaga upang matiyak na

861
01:12:12,770 --> 01:12:14,740
wala kaming anumang mga error sa memorya,

862
01:12:14,740 --> 01:12:16,840
dahil ito ay isa sa aming mga kaso sa gilid na alam namin tungkol sa.

863
01:12:16,840 --> 01:12:20,150
>> Sabihin tiyakin na ito ay gumagana nang maayos sa ilalim Valgrind,

864
01:12:20,150 --> 01:12:28,310
na gagawin namin sa pamamagitan ng lang tumatakbo ang Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Mukhang namin sa katunayan ay may isang error mula sa isang konteksto -

866
01:12:31,110 --> 01:12:33,790
namin ito segmentation fault.

867
01:12:33,790 --> 01:12:36,690
Ano ang nangyari?

868
01:12:36,690 --> 01:12:41,650
Valgrind aktwal na nagsasabi sa amin kung saan ito ay.

869
01:12:41,650 --> 01:12:43,050
Mag-zoom out ng kaunti.

870
01:12:43,050 --> 01:12:46,040
Mukhang ito ang nangyayari sa aming insert function na,

871
01:12:46,040 --> 01:12:53,420
kung saan mayroon kaming isang di-wastong read ng laki 4 sa insert, linya 60.

872
01:12:53,420 --> 01:13:03,590
Natin bumalik at makita kung ano ang nangyayari sa dito.

873
01:13:03,590 --> 01:13:05,350
Mag-zoom out talaga mabilis.

874
01:13:05,350 --> 01:13:14,230
Gusto ko upang matiyak na hindi ito pumunta sa gilid ng screen upang maaari naming makita ang lahat.

875
01:13:14,230 --> 01:13:18,760
Hilahin na sa ilang sandali. Tama.

876
01:13:18,760 --> 01:13:35,030
Mag-scroll pababa, at ang problema dito mismo.

877
01:13:35,030 --> 01:13:40,120
Ano ang mangyayari kung makuha namin down at na null ang aming kasalukuyang node ay,

878
01:13:40,120 --> 01:13:44,010
aming magulang na node ay null, kaya kung tinitingnan namin sa pinakatuktok, dito mismo -

879
01:13:44,010 --> 01:13:47,340
kung ito habang loop hindi aktwal na executes

880
01:13:47,340 --> 01:13:52,330
dahil ang aming kasalukuyang halaga ay null - aming ugat ay null upang kuprum ay null -

881
01:13:52,330 --> 01:13:57,810
pagkatapos ay ang aming mga magulang ay hindi kailanman ay makakakuha nakatakda sa kuprum o sa isang wastong halaga,

882
01:13:57,810 --> 01:14:00,580
kaya, ang mga magulang ay magkakaroon din null.

883
01:14:00,580 --> 01:14:03,700
Kailangan naming tandaan na suriin para sa

884
01:14:03,700 --> 01:14:08,750
ng oras na makuha namin pababa dito, at sisimulan namin ang access sa halaga ng magulang.

885
01:14:08,750 --> 01:14:13,190
Kaya, ano ang mangyayari? Well, kung ang magulang ay null -

886
01:14:13,190 --> 01:14:17,990
kung (magulang == null) - alam namin na

887
01:14:17,990 --> 01:14:19,530
may hindi dapat ang anuman sa tree.

888
01:14:19,530 --> 01:14:22,030
Kailangan naming sinusubukan upang ipasok ito sa root.

889
01:14:22,030 --> 01:14:32,570
Maaari naming gawin ang mga iyon sa pamamagitan ng lang set ng root na katumbas sa bagong node.

890
01:14:32,570 --> 01:14:40,010
Pagkatapos sa puntong ito, hindi namin aktwal gusto mong pumunta sa pamamagitan ng iba pang mga bagay.

891
01:14:40,010 --> 01:14:44,780
Sa halip, dito mismo, maaari naming gawin alinman sa isang iba pa-kung tao,

892
01:14:44,780 --> 01:14:47,610
o maaari naming pagsamahin ang lahat dito sa isang tao,

893
01:14:47,610 --> 01:14:56,300
ngunit dito makikita lang namin gamitin ang tao at gawin ito na paraan.

894
01:14:56,300 --> 01:14:59,030
Ngayon, kami ay pagpunta upang subukan upang matiyak na ang aming mga magulang ay hindi null

895
01:14:59,030 --> 01:15:02,160
bago at pagkatapos na aktwal na sinusubukan upang ma-access ang mga patlang.

896
01:15:02,160 --> 01:15:05,330
Ito ay makakatulong sa amin na maiwasan ang segmentation fault.

897
01:15:05,330 --> 01:15:14,740
Kaya, namin huminto, mag-zoom out, makatipon, patakbuhin.

898
01:15:14,740 --> 01:15:18,130
>> Walang mga error, ngunit mayroon pa rin kaming ng grupo ng mga paglabas ng memory

899
01:15:18,130 --> 01:15:20,650
dahil hindi namin magbakante anumang ng aming mga node.

900
01:15:20,650 --> 01:15:24,350
Ngunit, kung pumunta kami dito at titingnan namin sa aming printout,

901
01:15:24,350 --> 01:15:30,880
nakikita namin na, well, mukhang sa lahat ng aming mga pagsingit ay bumabalik na totoo, na ay mabuti.

902
01:15:30,880 --> 01:15:33,050
Ang mga pagsingit ay lahat ng totoo,

903
01:15:33,050 --> 01:15:36,670
at pagkatapos ay ang mga naaangkop na naglalaman ng mga tawag ay totoo rin.

904
01:15:36,670 --> 01:15:41,510
>> Mahusay! Mukhang matagumpay naming nakasulat insert.

905
01:15:41,510 --> 01:15:47,430
Na ang lahat ng mayroon kami para sa Pagtutukoy ng Problema Itakda sa linggong ito.

906
01:15:47,430 --> 01:15:51,720
Isa masaya hamon na isipin ang tungkol sa kung paano mo aktwal na pumunta sa

907
01:15:51,720 --> 01:15:55,340
at libreng lahat ng node sa puno.

908
01:15:55,340 --> 01:15:58,830
Maaari naming gawin ito ng isang bilang ng mga iba't ibang paraan,

909
01:15:58,830 --> 01:16:01,930
ngunit ko bang iwan na sa iyo sa eksperimento,

910
01:16:01,930 --> 01:16:06,080
at bilang isang masaya hamon, subukan at tiyakin na maaari mong tiyakin

911
01:16:06,080 --> 01:16:09,490
na ito Valgrind ulat nagbabalik walang mga error at hindi paglabas.

912
01:16:09,490 --> 01:16:12,880
>> Good luck sa Huffman set na ito linggo coding problema,

913
01:16:12,880 --> 01:16:14,380
at kami na nakikita mo sa susunod na linggo!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]