1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Bölmə 7: Daha Rahat]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard Universiteti]

3
00:00:05,090 --> 00:00:07,930
[Bu CS50 edir] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Bütün hüquqlar. Belə ki, mənim e-poçt bildirib kimi

5
00:00:10,110 --> 00:00:14,060
Bu ikili ağacı intensiv bölmə olacaq.

6
00:00:14,060 --> 00:00:16,820
Amma ki, bir çox suallar var.

7
00:00:16,820 --> 00:00:18,920
Beləliklə, biz cəhd və hər bir sual çıxartmaq olacaq

8
00:00:18,920 --> 00:00:25,430
və şeyler bütün yaxşı yollarından ağrılı ətraflı daxil.

9
00:00:25,430 --> 00:00:31,200
Belə ki, sağ əvvəlində biz ikili ağac və stuff nümunəsi təsvirlər keçir.

10
00:00:31,200 --> 00:00:35,970
Belə ki, burada, "ikili ağac bağlı siyahısı oxşar qovşaqlarının ki saxla

11
00:00:35,970 --> 00:00:38,150
sol 'uşaq' üçün biri əvəzinə bir pointer istisna olmaqla iki var

12
00:00:38,150 --> 00:00:41,950
və sağ 'uşaq üçün. "

13
00:00:41,950 --> 00:00:45,630
, Yalnız bir bağlı siyahı kimi ikili ağac Belə

14
00:00:45,630 --> 00:00:47,910
bu struct başqa iki göstəricilərinə malik olur.

15
00:00:47,910 --> 00:00:51,390
Üç göstəricilərinə üçün gedir hansı trinary ağacları, var

16
00:00:51,390 --> 00:00:56,540
yalnız ümumi göstərici olan N-ary ağacları var,

17
00:00:56,540 --> 00:01:00,320
sonra üçün kifayət qədər böyük olması malloc ki,

18
00:01:00,320 --> 00:01:04,840
bütün mümkün uşaqlar üçün kifayət qədər göstəricilər.

19
00:01:04,840 --> 00:01:08,200
Belə ikili ağac yalnız iki sabit sayda olur.

20
00:01:08,200 --> 00:01:11,260
Əgər istəyirsinizsə, bir unary ağac kimi bir bağlı siyahı verə bilər

21
00:01:11,260 --> 00:01:15,360
amma hər kəs ki çağırır düşünmürəm.

22
00:01:15,360 --> 00:01:18,060
"Ikili ağac node bir qutu və oxlar diaqram Draw

23
00:01:18,060 --> 00:01:24,110
hər bir uşaq göstərici null olduğu Nate sevimli nömrə, 7,. "olan

24
00:01:24,110 --> 00:01:27,780
Belə ki, iPad rejimi.

25
00:01:27,780 --> 00:01:30,280
>> Bu olduqca sadə olacaq.

26
00:01:30,280 --> 00:01:36,150
Biz yalnız bir node var olacaq, bir kvadrat kimi çəkmək lazımdır.

27
00:01:36,150 --> 00:01:38,730
Mən burada dəyərlər çəkmək lazımdır.

28
00:01:38,730 --> 00:01:41,090
Belə ki, dəyəri, burada gedəcək

29
00:01:41,090 --> 00:01:44,770
və sonra aşağı burada sol sol göstərici və sağ sağ göstərici olacaq.

30
00:01:44,770 --> 00:01:50,430
O sol və sağ göstərici adları zəng etmək üçün konvensiya belə Və bu çox deyil.

31
00:01:50,430 --> 00:01:52,460
Bu iki null olacaq.

32
00:01:52,460 --> 00:01:57,870
Bu yalnız null olacaq, yalnız null olacaq.

33
00:01:57,870 --> 00:02:03,630
Okay. Belə ki, burada geri.

34
00:02:03,630 --> 00:02:05,700
"A bağlı siyahı, biz yalnız bir göstərici saxlamaq üçün idi

35
00:02:05,700 --> 00:02:09,639
bütün əlaqədar siyahısı və ya bütün siyahı xatırlamaq üçün siyahısında ilk node.

36
00:02:09,639 --> 00:02:11,650
Eyni zamanda, ağacları ilə, yalnız bir göstərici saxlamaq üçün

37
00:02:11,650 --> 00:02:13,420
bütün ağac xatırlamaq üçün bir node.

38
00:02:13,420 --> 00:02:15,980
Bu node ağac "root" calle edir.

39
00:02:15,980 --> 00:02:18,320
Əvvəl sizin diaqram ilə qurmaq və ya yeni bir heç-heçə

40
00:02:18,320 --> 00:02:21,690
bir ikili ağac qutuları və oxlar anlatımı var ki, bu cür

41
00:02:21,690 --> 00:02:25,730
ilə sol sonra 3 dəyəri 7,

42
00:02:25,730 --> 00:02:32,760
3 hüququnu sonra sağ 9 və sonra 6 ".

43
00:02:32,760 --> 00:02:34,810
Mən baş ki, bütün yadda bilərsiniz Bakalým.

44
00:02:34,810 --> 00:02:37,670
Belə ki, burada bizim kök qədər olacaq.

45
00:02:37,670 --> 00:02:41,600
Biz, yerdə biz kök zəng lazımdır ki, bir şey bir göstərici olacaq

46
00:02:41,600 --> 00:02:45,140
və bu oğlan işarə edir.

47
00:02:45,140 --> 00:02:48,490
İndi yeni node etmək

48
00:02:48,490 --> 00:02:52,870
biz sol, 3 nə var?

49
00:02:52,870 --> 00:02:57,140
3 yeni node Belə ki, bu ilkin null göstərir.

50
00:02:57,140 --> 00:02:59,190
Mən yalnız N. qoymaq lazımdır

51
00:02:59,190 --> 00:03:02,250
İndi 7-sola getmək etmək istəyirəm.

52
00:03:02,250 --> 00:03:06,840
Beləliklə, biz indi bu adam baxımından bu göstərici dəyişir.

53
00:03:06,840 --> 00:03:12,420
Və biz eyni. Biz burada bir 9 istəyirəm

54
00:03:12,420 --> 00:03:14,620
olan ilkin yalnız null deyir.

55
00:03:14,620 --> 00:03:19,600
Biz, 9 Bu göstərici, point dəyişiklik olacaq

56
00:03:19,600 --> 00:03:23,310
və indi 3-sağa 6 qoymaq istəyirəm.

57
00:03:23,310 --> 00:03:32,170
Belə ki, olacaq - 6 olun.

58
00:03:32,170 --> 00:03:34,310
Və oğlan orada qeyd edəcək.

59
00:03:34,310 --> 00:03:38,320
Okay. Belə ki, bütün ki, bunu bizə soruşur.

60
00:03:38,320 --> 00:03:42,770
>> İndi bəzi terminologiya üzərində gedək.

61
00:03:42,770 --> 00:03:46,690
Biz artıq ağac kökü ağac üst-ən node nə danışdı.

62
00:03:46,690 --> 00:03:54,720
Bir 7 olan. Ağac altındakı qovşaqlarının yarpaqları deyilir.

63
00:03:54,720 --> 00:04:01,240
Yalnız uşaqlar kimi null malik olan hər hansı node bir yarpaq edir.

64
00:04:01,240 --> 00:04:03,680
Belə ki, bizim binar ağacı yalnız bir node varsa, olar,

65
00:04:03,680 --> 00:04:10,130
bir ağac bir yarpaq, və ki, var.

66
00:04:10,130 --> 00:04:12,060
"Ağac The 'boyu" Siz etmək mayaotu sayı

67
00:04:12,060 --> 00:04:16,620
üst bir yarpaq almaq üçün. "

68
00:04:16,620 --> 00:04:18,640
Biz ikinci daxil fərq almaq lazımdır

69
00:04:18,640 --> 00:04:21,940
balanslı və balanssız ikili ağacları arasında,

70
00:04:21,940 --> 00:04:29,470
bu ağac, lakin indi, ümumi hündürlüyü

71
00:04:29,470 --> 00:04:34,520
I, 3 deyərdim baxmayaraq mayaotu sayını hesablayır, əgər

72
00:04:34,520 --> 00:04:39,710
Siz 9 almaq üçün etmək üçün, o, həqiqətən 2 yalnız bir boyu var.

73
00:04:39,710 --> 00:04:43,340
Hal-hazırda bu, bir balanssız ikili ağac

74
00:04:43,340 --> 00:04:49,840
o müvafiq olur, lakin biz balanslaşdırılmış danışdı lazımdır.

75
00:04:49,840 --> 00:04:52,040
Belə ki, indi biz baxımından bir ağac qovşaqlarının haqqında danışmaq olar

76
00:04:52,040 --> 00:04:54,700
ağac digər qovşaqlarının nisbətən.

77
00:04:54,700 --> 00:04:59,730
Belə ki, indi biz valideynlər, uşaqlar, qardaşlar, əcdadları və nəsilləri var.

78
00:04:59,730 --> 00:05:05,650
Onlar nə demək, olduqca ümumi mənada var.

79
00:05:05,650 --> 00:05:09,610
Biz xahiş varsa - onun valideynləri.

80
00:05:09,610 --> 00:05:12,830
Belə ki, 3 əsas nədir?

81
00:05:12,830 --> 00:05:16,090
[Tələbələr] 7. >> Bəli. Əsas yalnız işarə nə olacaq.

82
00:05:16,090 --> 00:05:20,510
Sonra 7-uşaqlar nə var?

83
00:05:20,510 --> 00:05:23,860
[Tələbələr] 3 və 9. >> Bəli.

84
00:05:23,860 --> 00:05:26,460
"Uşaq" sözü uşaqlar deməkdir edək ki,

85
00:05:26,460 --> 00:05:31,010
bir nəvə kimi, çünki 6 belə tətbiq deyil.

86
00:05:31,010 --> 00:05:35,540
Biz nəslindən getmək Lakin sonra, belə 7 nəslindən nə var?

87
00:05:35,540 --> 00:05:37,500
[Tələbələr] 3, 6 və 9. >> Bəli.

88
00:05:37,500 --> 00:05:42,330
Kök node nəsli, ağac hər şey olacaq

89
00:05:42,330 --> 00:05:47,950
istisna olmaqla, bəlkə kök node özü, bu nəslindən hesab istəmirsinizsə.

90
00:05:47,950 --> 00:05:50,750
Və nəhayət, əcdadları, belə ki, əks istiqamətdə var.

91
00:05:50,750 --> 00:05:55,740
Belə ki, 6-babalarımızın nə var?

92
00:05:55,740 --> 00:05:58,920
[Tələbələr] 3 və 7. >> Bəli. 9 daxil deyil.

93
00:05:58,920 --> 00:06:02,520
Bu, yalnız kök birbaşa övlad geri var

94
00:06:02,520 --> 00:06:13,230
Sizin əcdadları olacaq.

95
00:06:13,230 --> 00:06:16,300
>> "Biz, bir ikili ağac əgər ağac hər node üçün 'əmr' demək

96
00:06:16,300 --> 00:06:19,530
sol öz nəslindən bütün az dəyərləri var

97
00:06:19,530 --> 00:06:22,890
və sağ olanları bütün böyük dəyərləri var.

98
00:06:22,890 --> 00:06:27,060
Məsələn, yuxarıda ağac sifariş lakin yalnız sifariş təşkili deyil olunur. "

99
00:06:27,060 --> 00:06:30,180
Ki, almaq, əvvəl

100
00:06:30,180 --> 00:06:36,420
bir sifariş ikili ağac da ikili axtarış ağac kimi tanınır.

101
00:06:36,420 --> 00:06:38,660
Burada, bir sifariş ikili ağac zəng üçün baş

102
00:06:38,660 --> 00:06:41,850
amma eşitməmişik ki, bir sifariş ikili ağac əvvəl deyilən

103
00:06:41,850 --> 00:06:46,650
və viktorina biz ikili axtarış ağac qoymaq üçün daha çox ehtimal olunur.

104
00:06:46,650 --> 00:06:49,250
Onlar bir və eyni edirik

105
00:06:49,250 --> 00:06:54,580
və bu ikili ağac və ikili axtarış ağac arasında fərq tanımaq vacibdir.

106
00:06:54,580 --> 00:06:58,830
A ikili ağac bir ağac ki, iki şeyə xal.

107
00:06:58,830 --> 00:07:02,120
Hər bir node iki şeyi göstərir.

108
00:07:02,120 --> 00:07:06,310
Bu işarə edən dəyərləri haqqında heç bir ağıl yoxdur.

109
00:07:06,310 --> 00:07:11,370
Bir ikili axtarış ağacı var ildən ki, burada istəyirəm

110
00:07:11,370 --> 00:07:14,030
biz, 7 getmək əgər sol bilirik ki,

111
00:07:14,030 --> 00:07:16,670
sonra biz bəlkə çata bilər ki, dəyərlərin bütün

112
00:07:16,670 --> 00:07:19,310
7 sol gedən 7-dən az olmalıdır.

113
00:07:19,310 --> 00:07:24,070
Az 7-dən bütün dəyərlər 3 və 6 edək ki,.

114
00:07:24,070 --> 00:07:26,040
Həmin 7-sola bütün var.

115
00:07:26,040 --> 00:07:29,020
Biz 7 doğru getmək varsa, hər şey, 7-dən çox olmalıdır

116
00:07:29,020 --> 00:07:33,220
belə 9 7 hüququna, belə ki, biz yaxşı deyilik.

117
00:07:33,220 --> 00:07:36,150
Bu, ikili ağac belə deyil

118
00:07:36,150 --> 00:07:40,020
müntəzəm ikili ağac biz yalnız sol üst, 7 3 ola bilər

119
00:07:40,020 --> 00:07:47,630
7-sola 9; heç heç dəyərlər sifariş var.

120
00:07:47,630 --> 00:07:56,140
O yorucu və lazımsız çünki İndi, biz, həqiqətən, bu nə olacaq

121
00:07:56,140 --> 00:07:59,400
lakin "siz hesab edə bilər kimi bir çox əmr ağacları çəkmək üçün cəhd edin

122
00:07:59,400 --> 00:08:01,900
nömrələri 7, 3, 9 istifadə edərək, və 6.

123
00:08:01,900 --> 00:08:06,800
Fərqli tədbirlərin nə qədər var? Hər birinin hündürlüyü nədir? "

124
00:08:06,800 --> 00:08:10,480
>> Biz bir neçə edəcəyik, amma əsas ideya

125
00:08:10,480 --> 00:08:16,530
bu heç bir şəkildə bu dəyərləri olan bir ikili ağac nadir təmsil edir.

126
00:08:16,530 --> 00:08:22,760
Bəzi ikili 7 olan ağac, 3, 6, 9, biz lazım deyil.

127
00:08:22,760 --> 00:08:25,960
Digər mümkün etibarlı bir, kök 3 olardı

128
00:08:25,960 --> 00:08:30,260
sola getmək və 6 var, sol getmək və 7 var,

129
00:08:30,260 --> 00:08:32,730
sola getmək və 9 deyil.

130
00:08:32,730 --> 00:08:36,169
Bu mükəmməl etibarlı ikili axtarış ağac.

131
00:08:36,169 --> 00:08:39,570
Yalnız bir bağlı siyahı kimi, çünki çox faydalı deyil

132
00:08:39,570 --> 00:08:43,750
və bu göstəricilər bütün yalnız null var.

133
00:08:43,750 --> 00:08:48,900
Amma cari ağac. Evet?

134
00:08:48,900 --> 00:08:51,310
[Tələbə] dəyərlərinə doğru böyük olmamalıdır varmı?

135
00:08:51,310 --> 00:08:56,700
Və ya bu - >> Bu Mən başqa yol getmək idi.

136
00:08:56,700 --> 00:09:00,960
Da var - Bəli, ki, keçid imkan verir.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Yaxşı tutmaq.

138
00:09:07,770 --> 00:09:11,730
Bu hələ bir ikili ağac axtarış ehtimal olunur nə itaət var.

139
00:09:11,730 --> 00:09:15,650
Belə ki, sol üçün hər hansı bir node-dən az olmalıdır.

140
00:09:15,650 --> 00:09:23,180
Biz yalnız, demək, bu, 6 hərəkət və burada qoymaq bilər.

141
00:09:23,180 --> 00:09:26,880
Xeyr, biz bilməz. Niyə bunu saxlayırsınız?

142
00:09:26,880 --> 00:09:35,350
Nə edək - burada 6, burada 7, 3-6 xal edir.

143
00:09:35,350 --> 00:09:39,290
Bu hələ etibarlı ikili axtarış ağac.

144
00:09:39,290 --> 00:09:49,260
Mən bir tənzimləmə ilə gəlmək olar əgər in görək - Mən nə səhv.

145
00:09:49,260 --> 00:09:52,280
Bəli, tamam. Bu ağac ilə nə səhvdir?

146
00:09:52,280 --> 00:10:08,920
Mən artıq siz bu yanlış bir şey var ki, bir ipucu verdiyseniz danışarlar.

147
00:10:08,920 --> 00:10:14,430
Niyə bunu saxlayırsınız?

148
00:10:14,430 --> 00:10:18,510
Okay. Bu ağlabatan görünür.

149
00:10:18,510 --> 00:10:22,590
Biz hər node, 7 kimi, sonra 7-sola baxmaq Əgər 3.

150
00:10:22,590 --> 00:10:24,960
Beləliklə, biz 3 var, 3 sağ üçün şey bir 6.

151
00:10:24,960 --> 00:10:27,750
6 baxmaq əgər, 6 sağa şey 9 edir.

152
00:10:27,750 --> 00:10:30,910
Belə ki, niyə bu düzgün ikili axtarış ağac deyil?

153
00:10:30,910 --> 00:10:36,330
[Tələbələr] 9 7 sola davam edir. >> Bəli.

154
00:10:36,330 --> 00:10:43,710
Bu bəlkə 7-sola gedərək çata bilər bütün dəyərlərin 7-dən az olan doğru olmalıdır.

155
00:10:43,710 --> 00:10:49,120
Biz 7 sol getmək varsa, biz 3 almaq və biz hələ 6 bilərsiniz

156
00:10:49,120 --> 00:10:52,520
biz hələ, 9 almaq, lakin az 7 getdi edərək bilərsiniz

157
00:10:52,520 --> 00:10:55,070
biz 7 daha çox olan bir sıra əldə edə bilməz.

158
00:10:55,070 --> 00:10:59,830
Belə ki, bu düzgün ikili axtarış ağac deyil.

159
00:10:59,830 --> 00:11:02,330
>> Qardaşım həqiqətən müsahibə sual idi

160
00:11:02,330 --> 00:11:07,760
ki doğrulamak üçün bir şey əsasən bu, yalnız kod idi

161
00:11:07,760 --> 00:11:10,500
bir ağac bir ikili axtarış ağac, istər

162
00:11:10,500 --> 00:11:13,580
və belə etdi ilk şey yalnız yoxlamaq görmək idi

163
00:11:13,580 --> 00:11:17,020
sol və sağ doğru və əgər orada təkrarlamaq.

164
00:11:17,020 --> 00:11:19,700
Amma bunu yalnız bilməz; siz track saxlamaq

165
00:11:19,700 --> 00:11:22,550
Mən 7 sol getdi sonra indi ki,

166
00:11:22,550 --> 00:11:26,340
bu subtree hər 7-dən az olmalıdır.

167
00:11:26,340 --> 00:11:28,430
Düzgün alqoritm takip lazımdır

168
00:11:28,430 --> 00:11:35,970
dəyərlər bəlkə daxil olmaq olar ki, sınırların

169
00:11:35,970 --> 00:11:38,360
Biz onların bütün vasitəsilə getmək olmaz.

170
00:11:38,360 --> 00:11:41,630
Bir gözəl təkrar əlaqə var

171
00:11:41,630 --> 00:11:44,810
biz o kazanılmış deyil, ya da o almaq deyil, baxmayaraq ki,

172
00:11:44,810 --> 00:11:47,030
həqiqətən var necə çox müəyyən.

173
00:11:47,030 --> 00:11:53,180
Belə ki, onların 14 var.

174
00:11:53,180 --> 00:11:56,020
Bunu necə fikri riyazi, kimi

175
00:11:56,020 --> 00:11:59,770
Əgər kök node olmaq üçün hər hansı bir bir seçə bilərsiniz

176
00:11:59,770 --> 00:12:03,160
və sonra, kök node olmaq 7 seçin əgər

177
00:12:03,160 --> 00:12:08,150
sonra mənim sol node ola bilərsiniz ki, bəzi nömrələri, demək, var

178
00:12:08,150 --> 00:12:10,440
və sağ node ola bilər ki, bəzi nömrələr var,

179
00:12:10,440 --> 00:12:15,090
amma sonra ümumi sayı, sol to məbləği n əgər

180
00:12:15,090 --> 00:12:18,820
plus hüququ to məbləği n - 1.

181
00:12:18,820 --> 00:12:26,130
Belə ki, qalan nömrələri, onlar sol və ya sağ ya getmək mümkün olmalıdır.

182
00:12:26,130 --> 00:12:31,580
Bu, mən sonra ilk 3 qoymaq əgər hər şey sol getmək var ki, çətin görünür

183
00:12:31,580 --> 00:12:35,080
amma 7 qoymaq, onda bir şeyi sol bilərsiniz və bəzi şeylər sağa bilərsiniz.

184
00:12:35,080 --> 00:12:39,570
Və '3 ilk 'Mən hər şeyi doğru edə bilərsiniz deməkdir.

185
00:12:39,570 --> 00:12:42,350
Bu, həqiqətən, siz yalnız kimi, bu barədə düşünmək lazımdır

186
00:12:42,350 --> 00:12:47,980
necə bir çox şeyi ağac növbəti səviyyədə davam edə bilər.

187
00:12:47,980 --> 00:12:50,420
Və ya onların bütün cəlb edə bilər və o, 14 olduğu ortaya çıxır

188
00:12:50,420 --> 00:12:54,650
və sonra 14 almaq lazımdır.

189
00:12:54,650 --> 00:13:01,120
>> Burada geri Going,

190
00:13:01,120 --> 00:13:03,510
Biz onların vasitəsilə axtarış edə bilərsiniz, çünki "açar sözlər, ikili ağacların sərin

191
00:13:03,510 --> 00:13:06,910
bir sıralanır array üzərində axtarış çox oxşar şəkildə.

192
00:13:06,910 --> 00:13:10,120
Bunu etmək üçün, biz kök başlamaq və ağac aşağı yolumuza iş

193
00:13:10,120 --> 00:13:13,440
yarpaqları doğru, biz aradığınız dəyərlərə qarşı hər node dəyərləri yoxlanılması.

194
00:13:13,440 --> 00:13:15,810
Cari node dəyəri dəyəri az, biz, aradığınız

195
00:13:15,810 --> 00:13:18,050
Siz node hüququ uşaq yanında gedin.

196
00:13:18,050 --> 00:13:20,030
Əks halda, siz node sol uşaq gedin.

197
00:13:20,030 --> 00:13:22,800
Bəzi noktada, ya aradığınız dəyəri tapa bilərsiniz, və ya bir null daxil olacaq

198
00:13:22,800 --> 00:13:28,520
dəyəri ifadə edən ağac deyil. "

199
00:13:28,520 --> 00:13:32,450
Düşünürəm ki, biz əvvəl idi ağac yenidən müəyyən etmək üçün var, ikinci bir almaq lazımdır.

200
00:13:32,450 --> 00:13:38,280
Amma biz 6, 10, və 1 ağac olub yuxarı baxmaq istəyirəm.

201
00:13:38,280 --> 00:13:49,180
Belə ki, nə, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
Siz baxmaq istədiyiniz nömrələri, biz 6 yuxarı baxmaq istəyirəm.

203
00:13:52,730 --> 00:13:55,440
Bu necə alqoritmi çalışır?

204
00:13:55,440 --> 00:14:03,040
Bəli, biz də ağac bəzi kök göstərici var.

205
00:14:03,040 --> 00:14:12,460
Və biz kök getmək və demək istəyirəm ki, biz aradığınız dəyərinə bərabər bu dəyəri?

206
00:14:12,460 --> 00:14:15,000
Belə ki, 6 arıyorsanız, belə ki, bərabər deyil.

207
00:14:15,000 --> 00:14:20,140
Belə 6 7 az, tamam, biz davam və indi biz deyirik.

208
00:14:20,140 --> 00:14:23,940
Ki, biz sola getmək istəyirəm deməkdir, ya da sağ getmək istəyirsiniz?

209
00:14:23,940 --> 00:14:27,340
[Tələbə] Sol. >> Bəli.

210
00:14:27,340 --> 00:14:33,340
Bu xeyli asan, siz bütün ağac biri mümkün node cəlb edilir

211
00:14:33,340 --> 00:14:37,760
və sonra don't - Sizin baş düşünməyə çalışır əvəzinə,

212
00:14:37,760 --> 00:14:40,020
tamam az varsa, mən sola getmək və ya doğru getmək yoxdur

213
00:14:40,020 --> 00:14:43,030
yalnız bu şəkil baxaraq, mən sola getmək çox aydındır

214
00:14:43,030 --> 00:14:47,700
Bu node I arıyorum ki, dəyəri daha çox olsun.

215
00:14:47,700 --> 00:14:52,600
Belə ki, indi 3 deyiləm, sol gedin.

216
00:14:52,600 --> 00:14:57,770
Mən istəyirəm - 3 6 I arıyorum dəyəri azdır.

217
00:14:57,770 --> 00:15:03,420
Beləliklə, biz doğru getmək, və indi, 6 son

218
00:15:03,420 --> 00:15:07,380
I əsl qayıtmaq mən, arıyorum dəyəri edir.

219
00:15:07,380 --> 00:15:15,760
Mən baxmaq gedirəm növbəti dəyəri 10 edir.

220
00:15:15,760 --> 00:15:23,230
Okay. Kök izləmək niyyətindədir - ki, kəsmə - 10 Beləliklə, indi gedir.

221
00:15:23,230 --> 00:15:27,670
İndi 10 7 daha çox olacaq, belə ki, mən sağ baxmaq istəyirəm.

222
00:15:27,670 --> 00:15:31,660
Mən buraya gəlmək üçün gedirəm, 10, 9 daha çox olacaq

223
00:15:31,660 --> 00:15:34,520
mən sağ baxmaq istəyirəm gedirəm.

224
00:15:34,520 --> 00:15:42,100
Mən buraya gəlib, lakin burada indi null da deyiləm.

225
00:15:42,100 --> 00:15:44,170
Mən null hit əgər mən nə etməliyəm?

226
00:15:44,170 --> 00:15:47,440
[Tələbə] yalan qayıt? >> Bəli. 10 tapmadı.

227
00:15:47,440 --> 00:15:49,800
1 təxminən eyni halda olacaq,

228
00:15:49,800 --> 00:15:51,950
istisna olmaqla, yalnız Çevrilmiş olacaq; axtarır əvəzinə

229
00:15:51,950 --> 00:15:56,540
sağ aşağı, mən sol aşağı baxmaq gedirəm.

230
00:15:56,540 --> 00:16:00,430
>> İndi biz, həqiqətən kodu almaq edirəm.

231
00:16:00,430 --> 00:16:04,070
Burada - Bu CS50 cihaz açmaq və orada sizin yolu gedin

232
00:16:04,070 --> 00:16:07,010
lakin siz də yer bunu yalnız bilər.

233
00:16:07,010 --> 00:16:09,170
Bu, yəqin ki, yer bunu ideal deyil

234
00:16:09,170 --> 00:16:13,760
biz yer işləyə bilər, çünki.

235
00:16:13,760 --> 00:16:19,170
"Birinci biz int dəyərləri olan bir ikili ağac node üçün yeni tipli definition lazımdır.

236
00:16:19,170 --> 00:16:21,400
Aşağıda typedef də boilerplate istifadə edərək,

237
00:16:21,400 --> 00:16:24,510
ikili ağac bir node üçün yeni bir növü definition yaradır.

238
00:16:24,510 --> 00:16:27,930
Zorlandığınız varsa. . . "Blah, blah, blah. OK.

239
00:16:27,930 --> 00:16:30,380
Belə nin burada boilerplate qoymaq bildirin

240
00:16:30,380 --> 00:16:41,630
typedef struct node və node. Bəli, tamam.

241
00:16:41,630 --> 00:16:44,270
Belə ki, biz node istədiyiniz olacaq sahələri hansılardır?

242
00:16:44,270 --> 00:16:46,520
[Tələbə] iki göstəricilərinə sonra Int və?

243
00:16:46,520 --> 00:16:49,700
>> Int dəyəri iki göstəricilərinə? Necə göstəricilərinə yazmaq edirsiniz?

244
00:16:49,700 --> 00:16:58,440
[Tələbə] Struct. >> I, Bəli, belə struct node * yazmayıblar da zoom olmalıdır

245
00:16:58,440 --> 00:17:01,320
və struct node * hüququ.

246
00:17:01,320 --> 00:17:03,460
Və, son zaman müzakirə xatırlayıram

247
00:17:03,460 --> 00:17:15,290
Bu heç bir əhəmiyyət kəsb edir ki, bu, heç bir əhəmiyyət kəsb edir

248
00:17:15,290 --> 00:17:18,270
Bu heç bir əhəmiyyət kəsb edir.

249
00:17:18,270 --> 00:17:25,000
Siz bu recursive struct müəyyən etmək üçün orada hər şey lazımdır.

250
00:17:25,000 --> 00:17:27,970
OK, nə bizim ağac kimi baxmaq edir ki.

251
00:17:27,970 --> 00:17:37,670
Biz bir trinary ağac idi, onda bir node B1, B2, struct node * b3 kimi görünə bilər

252
00:17:37,670 --> 00:17:43,470
b filialı olduğu - əslində, mən daha çox, orta, sağ deyil, nə tərk eşitdim.

253
00:17:43,470 --> 00:17:55,610
Biz yalnız ikili qayğı, belə ki, sağ, sol.

254
00:17:55,610 --> 00:17:59,110
"İndi ağac kökü üçün qlobal node * dəyişən bəyan edir."

255
00:17:59,110 --> 00:18:01,510
Belə ki, biz bunu fikrində deyilik.

256
00:18:01,510 --> 00:18:08,950
Şeyi bir az daha çətin və daha ümumiləşdirilmiş etmək üçün,

257
00:18:08,950 --> 00:18:11,570
biz qlobal node dəyişən olmayacaq.

258
00:18:11,570 --> 00:18:16,710
Əksinə, əsas biz bütün node şeyi bəyan

259
00:18:16,710 --> 00:18:20,500
biz çalışan başlattığınızda və ki, aşağıda deməkdir

260
00:18:20,500 --> 00:18:23,130
bizim başqa funksiyası və insert funksiyası,

261
00:18:23,130 --> 00:18:27,410
yerinə şey yalnız, bu qlobal node dəyişən istifadə funksiyası

262
00:18:27,410 --> 00:18:34,280
biz emal etmək istəyirəm ki, bir arqument kimi ağac almaq üçün olacaq.

263
00:18:34,280 --> 00:18:36,650
Qlobal dəyişən olan şeyi daha asan idi.

264
00:18:36,650 --> 00:18:42,310
Biz hər şeyi daha etmək olacaq.

265
00:18:42,310 --> 00:18:51,210
İndi şey bu cür etmək yalnız bir dəqiqə və ya almaq

266
00:18:51,210 --> 00:18:57,690
içərisində əsas sizə bu ağacı yaratmaq istəyirik ki, siz istədiyiniz bütün yerləşir.

267
00:18:57,690 --> 00:19:04,530
Keçir və əsas funksiyası bu ağac tikmək.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Belə ki, hətta hələ ağac bütün yol inşa etmək yoxdur.

269
00:19:47,610 --> 00:19:49,840
Amma hər kəs mən qoparmaq bilər bir şey var

270
00:19:49,840 --> 00:20:03,130
bir belə bir ağac tikintisi başlamaq bilər necə göstərmək üçün?

271
00:20:03,130 --> 00:20:08,080
[Tələbə] Biri nin tarpıltı, çıxmaq üçün çalışırıq.

272
00:20:08,080 --> 00:20:13,100
[Bowden] onların ağac tikintisi ilə rahat kəs?

273
00:20:13,100 --> 00:20:15,520
[Tələbə] Sure. Bu işlər deyil. Bu gözəl var >>. Biz yalnız bitirmək bilər -

274
00:20:15,520 --> 00:20:26,860
oh, siz onu saxlaya bilərsiniz? Yaşasın.

275
00:20:26,860 --> 00:20:32,020
Belə ki, burada biz var - oh, mən bir az kəsmək alıram.

276
00:20:32,020 --> 00:20:34,770
Mən zoomed Am?

277
00:20:34,770 --> 00:20:37,730
Zoom həyata diyirləyin. Mən bir sual var >>. >> Evet?

278
00:20:37,730 --> 00:20:44,410
[Tələbə] Siz struct müəyyən zaman, bir şey üçün başlatılmış kimi şeylər var?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> OK. Beləliklə, siz başlamaq lazımdır -

280
00:20:47,160 --> 00:20:50,450
[Bowden] saylı bir struct siz müəyyən zaman və ya bəyan edərkən,

281
00:20:50,450 --> 00:20:55,600
bu ismarıcları başlatılmış deyil, bir int bəyan əgər yalnız kimi.

282
00:20:55,600 --> 00:20:59,020
Bu tam eyni şey. Onun fərdi sahələrində hər kimi

283
00:20:59,020 --> 00:21:04,460
bu bir zibil dəyər ola bilər. Bir struct və ya bəyan etmək - >> Və müəyyən etmək mümkündür

284
00:21:04,460 --> 00:21:07,740
Bunu bir şəkildə başlamaq?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Bəli. Belə ki, qısa başlatma sintaksis

286
00:21:13,200 --> 00:21:18,660
kimi gedir -

287
00:21:18,660 --> 00:21:22,200
Bunu iki yol var. Edirəm ki, tərtib etməlidir

288
00:21:22,200 --> 00:21:25,840
əmin cingilti etmək də bu yoxdur.

289
00:21:25,840 --> 00:21:28,510
The struct gəlir ki, dəlilləri qaydası

290
00:21:28,510 --> 00:21:32,170
Bu qıvrım aşırma daxilində dəlilləri sifarişi kimi qoydu.

291
00:21:32,170 --> 00:21:35,690
Siz 9 üçün başlamaq istəyirəm və sol Belə ki, əgər sağ, null ola null edilir və

292
00:21:35,690 --> 00:21:41,570
o, null, null 9 olardı.

293
00:21:41,570 --> 00:21:47,890
, Alternativ və redaktoru bu sintaksis kimi deyil

294
00:21:47,890 --> 00:21:50,300
və bu, yeni bir blok istəyirəm düşünür

295
00:21:50,300 --> 00:22:01,800
lakin alternativ bir şey kimi -

296
00:22:01,800 --> 00:22:04,190
burada, yeni bir xətt üzərində qoymaq lazımdır.

297
00:22:04,190 --> 00:22:09,140
Siz aydın deyə bilərsiniz, mən dəqiq sintaksis unutmayın.

298
00:22:09,140 --> 00:22:13,110
Belə ki, açıq-aydın, adı onlara müraciət və demək olar

299
00:22:13,110 --> 00:22:21,570
. C, və ya. Value = 9,. Sol = NULL.

300
00:22:21,570 --> 00:22:24,540
Mən vergülləri olmaq üçün bu ehtiyac təxmin edirəm.

301
00:22:24,540 --> 00:22:29,110
. Sağda = NULL, belə deyil, bu yolla

302
00:22:29,110 --> 00:22:33,780
faktiki olaraq, struct sifarişi bilmək lazımdır

303
00:22:33,780 --> 00:22:36,650
və bu oxu etdiyiniz zaman, daha aydın deyil

304
00:22:36,650 --> 00:22:41,920
nə dəyəri başlatılmış olunur var.

305
00:22:41,920 --> 00:22:44,080
>> Bu hər bir olur -

306
00:22:44,080 --> 00:22:49,100
belə ki, çox hissəsi üçün, C + + C bir superset edir

307
00:22:49,100 --> 00:22:54,160
Siz C + +, və tərtib etməli üzərində hərəkət, C kodu bilər.

308
00:22:54,160 --> 00:22:59,570
Bu C + + bilmir ki, hər şeyi biridir, belə ki, insanlar bunu üçün edirlər.

309
00:22:59,570 --> 00:23:01,850
Ki, insanlar bunu deyil meyli yeganə səbəbi var, mən bilmirəm

310
00:23:01,850 --> 00:23:10,540
ancaq istifadə etmək üçün lazım olduğu halda C + + və mən bu istifadə edə bilmədi ilə işləmək lazımdır.

311
00:23:10,540 --> 00:23:14,000
Ki, bir şey başqa bir misal C + + ilə iş deyil

312
00:23:14,000 --> 00:23:16,940
necə malloc, texniki, "etibarsız *" a qayıdır

313
00:23:16,940 --> 00:23:20,200
lakin yalnız, char * x = malloc nə deyə bilər

314
00:23:20,200 --> 00:23:22,840
və avtomatik olaraq bir char * üçün tökmə olunacaq.

315
00:23:22,840 --> 00:23:25,450
Bu avtomatik cast olmaz C + +.

316
00:23:25,450 --> 00:23:28,150
Tərtib deyil, və açıq-aydın demək lazımdır ki,

317
00:23:28,150 --> 00:23:34,510
char * malloc, nə olursa olsun, bir char * üçün salmaq.

318
00:23:34,510 --> 00:23:37,270
C və C + + haqqında deyiləm ki, bir çox şeyi yoxdur

319
00:23:37,270 --> 00:23:40,620
lakin bu iki.

320
00:23:40,620 --> 00:23:43,120
Beləliklə, biz bu sintaksis ilə gedəcəyəm.

321
00:23:43,120 --> 00:23:46,150
Ancaq biz sintaksis ilə getmədi, hətta,

322
00:23:46,150 --> 00:23:49,470
nə - bu yanlış ola bilər?

323
00:23:49,470 --> 00:23:52,170
[Tələbə] Mən dereference buna ehtiyac yoxdur? >> Bəli.

324
00:23:52,170 --> 00:23:55,110
, Ok bir gizli dereference ki saxla

325
00:23:55,110 --> 00:23:58,230
və biz yalnız bir struct ilə məşğul olduğunuz zaman

326
00:23:58,230 --> 00:24:04,300
biz istifadə etmək istəyirik. bu struct bir sahə daxilində əldə etmək.

327
00:24:04,300 --> 00:24:07,200
Və biz arrow istifadə yalnız vaxt biz nə istəyirik zaman -

328
00:24:07,200 --> 00:24:13,450
yaxşı arrow bərabərdir -

329
00:24:13,450 --> 00:24:17,020
ki arrow istifadə əgər demək olardı budur.

330
00:24:17,020 --> 00:24:24,600
Bütün arrow vasitələri, dereference bu, indi bir struct ilə Ben və mən sahəsində əldə edə bilərsiniz.

331
00:24:24,600 --> 00:24:28,040
Birbaşa və ya dereference sahəsində almaq və bu sahədə əldə -

332
00:24:28,040 --> 00:24:30,380
Mən bu dəyəri olmalıdır danışarlar.

333
00:24:30,380 --> 00:24:33,910
Amma burada mən, bir struct, bir struct bir pointer ilə məşğul oldum

334
00:24:33,910 --> 00:24:38,780
və mən arrow istifadə edə bilməz.

335
00:24:38,780 --> 00:24:47,510
Lakin şey bu cür biz bütün qovşaqlarının üçün nə edə bilər.

336
00:24:47,510 --> 00:24:55,790
Pərvərdigara.

337
00:24:55,790 --> 00:25:09,540
Bu 6, 7, 3-dir.

338
00:25:09,540 --> 00:25:16,470
Sonra ağac filial bilərsiniz, biz 7 ola bilər -

339
00:25:16,470 --> 00:25:21,650
biz, onun sol 3 qeyd olunmalıdır ola bilər.

340
00:25:21,650 --> 00:25:25,130
Belə ki, necə ki, biz etməliyəm?

341
00:25:25,130 --> 00:25:29,320
[Tələbələr, anlaşılmaz] >> Bəli. Node3 yerləşdiyi ünvan,

342
00:25:29,320 --> 00:25:34,170
və ünvan olmasaydı, o, yalnız tərtib deyil.

343
00:25:34,170 --> 00:25:38,190
Lakin bu növbəti qovşaqlarının to göstəricilərinə ki, xatırlayıram.

344
00:25:38,190 --> 00:25:44,930
Hüququ, 9 qeyd etməlidir

345
00:25:44,930 --> 00:25:53,330
və 3 6 hüququna qeyd edilməlidir.

346
00:25:53,330 --> 00:25:58,480
Mən bu bütün set olduğunu düşünürəm. Hər hansı bir şərh və ya sualınız?

347
00:25:58,480 --> 00:26:02,060
[Tələbə, anlaşılmaz] kök 7 olacaq.

348
00:26:02,060 --> 00:26:08,210
Biz yalnız node demək olar * Ptr =

349
00:26:08,210 --> 00:26:14,160
və ya kök, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Bizim məqsədləri üçün, biz, insert ilə məşğul olmaq üçün olacaq

351
00:26:20,730 --> 00:26:25,490
biz bu ikili ağac daxil bir funksiyası yazmaq üçün olacaq

352
00:26:25,490 --> 00:26:34,230
və insert qaçılmaz bu ağac üçün yeni node yaratmaq malloc zəng edir.

353
00:26:34,230 --> 00:26:36,590
Belə şeylər faktı ilə messy almaq üçün gedir ki, bəzi qovşaqlarının

354
00:26:36,590 --> 00:26:38,590
yığını üzərində hazırda

355
00:26:38,590 --> 00:26:43,680
və digər qovşaqlarının biz onlara daxil olduqda yığın haqqında son edir.

356
00:26:43,680 --> 00:26:47,640
Bu mükəmməl etibarlıdır, lakin yeganə səbəbi

357
00:26:47,640 --> 00:26:49,600
biz yığını bu nə edirik

358
00:26:49,600 --> 00:26:51,840
Biz bilirik ki, belə bir göstərdi Məsələn, çünki edir

359
00:26:51,840 --> 00:26:56,360
ağac 7, 3, 6, 9 kimi inşa edilməsi nəzərdə tutulur.

360
00:26:56,360 --> 00:27:02,970
Biz bu olmasaydı, onda biz ilk növbədə malloc üçün deyil.

361
00:27:02,970 --> 00:27:06,160
Biz bir az sonra görəcəksiniz ki, biz malloc'ing edilməlidir.

362
00:27:06,160 --> 00:27:08,570
Hal-hazırda o, baca qoymaq üçün mükəmməl məqbul deyil

363
00:27:08,570 --> 00:27:14,750
amma üzrə malloc həyata keçirilməsi bu dəyişdirmək imkan verir.

364
00:27:14,750 --> 00:27:17,160
Belə ki, bu hər indi bir şey kimi olacaq

365
00:27:17,160 --> 00:27:24,240
node * node9 = malloc (sizeof (node)).

366
00:27:24,240 --> 00:27:28,040
İndi biz çek var olacaq.

367
00:27:28,040 --> 00:27:34,010
(== NULL node9) əgər - Mən o istəmir -

368
00:27:34,010 --> 00:27:40,950
1 qayıtmaq, indi bir pointer, çünki biz, node9-> edə bilərsiniz

369
00:27:40,950 --> 00:27:45,300
value = 6, node9-> tərk = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> sağda = NULL,

371
00:27:48,930 --> 00:27:51,410
və biz bu qovşaqlarının hər biri üçün bunu etmək olacaq.

372
00:27:51,410 --> 00:27:57,490
Belə ki, əvəzinə isə ayrı bir funksiyası daxilində qoymaq bildirin.

373
00:27:57,490 --> 00:28:00,620
Gəlin, bu node * build_node zəng

374
00:28:00,620 --> 00:28:09,050
və bu biz Huffman coding üçün təmin API üçün bir qədər oxşardır.

375
00:28:09,050 --> 00:28:12,730
Biz ağac siz initializer funksiyaları vermək

376
00:28:12,730 --> 00:28:20,520
və deconstructor o ağacların və meşələrin üçün eyni "funksiyaları".

377
00:28:20,520 --> 00:28:22,570
>> Belə ki, burada biz initializer funksiya olacaq

378
00:28:22,570 --> 00:28:25,170
yalnız bizim üçün bir node qurmaq.

379
00:28:25,170 --> 00:28:29,320
Və məhz bu kimi olduqca çox baxmaq olacaq.

380
00:28:29,320 --> 00:28:32,230
Mən hətta tənbəl olacaq və dəyişən adının dəyişdirilməsi deyiləm

381
00:28:32,230 --> 00:28:34,380
node9 artıq heç bir əhəmiyyət kəsb edir, baxmayaraq ki,.

382
00:28:34,380 --> 00:28:38,610
Oh, mən node9 dəyəri 6 olmuşdur olmamalıdır danışarlar.

383
00:28:38,610 --> 00:28:42,800
İndi node9 ola bilər.

384
00:28:42,800 --> 00:28:49,550
Burada biz null qaytarmalıdır.

385
00:28:49,550 --> 00:28:52,690
Hər kəs ki, build-a-node funksiyası razıyam?

386
00:28:52,690 --> 00:28:59,780
Belə ki, indi biz yalnız bir dəyəri və null göstəricilərinə hər hansı node qurmaq üçün zəng edə bilərsiniz.

387
00:28:59,780 --> 00:29:09,750
İndi ki, zəng edə bilərsiniz, biz node * node9 = build_node (9) edə bilərsiniz.

388
00:29:09,750 --> 00:29:25,810
Və nin bunu bildirin. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
İndi biz, eyni göstəricilər qurmaq istəyirəm

391
00:29:39,330 --> 00:29:42,470
indi başqa hər şey göstəricilər baxımından artıq var

392
00:29:42,470 --> 00:29:48,480
belə artıq ünvanı lazımdır.

393
00:29:48,480 --> 00:29:56,300
Okay. Mən istəyirəm son şey nədir?

394
00:29:56,300 --> 00:30:03,850
Mən bunu deyiləm ki, bir səhv yoxlanılması var.

395
00:30:03,850 --> 00:30:06,800
Node qaytarılması nə qurmaq deyil?

396
00:30:06,800 --> 00:30:11,660
[Tələbə, anlaşılmaz] >> Bəli. Malloc uğursuz varsa, null qayıtmaq lazımdır.

397
00:30:11,660 --> 00:30:16,460
Mən tənbəlcəsinə əvəzinə hər şərait bunu burada yazmaq arkasýndayým.

398
00:30:16,460 --> 00:30:22,320
Əgər (node9 == NULL, və ya - hətta sadə,

399
00:30:22,320 --> 00:30:28,020
Bu yalnız əgər node9 bərabərdir.

400
00:30:28,020 --> 00:30:38,310
Əgər node9, və ya node6, və ya node3, və ya node7 Belə ki, 1 qayıtmaq.

401
00:30:38,310 --> 00:30:42,850
Bəlkə biz malloc bilmədi, və ya bir şey çap olunmalıdır.

402
00:30:42,850 --> 00:30:46,680
[Tələbə] həmçinin null bərabər yalan mı?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Hər sıfır dəyəri yalan.

404
00:30:51,290 --> 00:30:53,920
Belə null sıfır dəyəri.

405
00:30:53,920 --> 00:30:56,780
Zero sıfır dəyəri. Asma sıfır dəyəri.

406
00:30:56,780 --> 00:31:02,130
Hər hansı - olduqca çox yalnız 2 sıfır dəyərlər null və sıfır olan,

407
00:31:02,130 --> 00:31:07,900
yalan sıfır kimi müəyyən yalnız hash edir.

408
00:31:07,900 --> 00:31:13,030
Biz qlobal dəyişən bəyan halda da tətbiq edilir.

409
00:31:13,030 --> 00:31:17,890
Biz burada node * root malik idi, əgər

410
00:31:17,890 --> 00:31:24,150
sonra - qlobal dəyişənlər haqqında gözəl şey həmişə ilkin dəyər var.

411
00:31:24,150 --> 00:31:27,500
Bu funksiyaları doğru deyil, necə içərisində burada,

412
00:31:27,500 --> 00:31:34,870
biz varsa, kimi, node * və ya node x.

413
00:31:34,870 --> 00:31:37,380
Biz heç bir fikir nə x.value, x.whatever var

414
00:31:37,380 --> 00:31:40,700
və ya biz onları çap edə bilər və onlar ixtiyari ola bilər.

415
00:31:40,700 --> 00:31:44,980
Bu qlobal dəyişənlər doğru deyil.

416
00:31:44,980 --> 00:31:47,450
Belə node kök və ya node x.

417
00:31:47,450 --> 00:31:53,410
Mənim cari olaraq, qlobal ki, hər şey, əgər açıq-aydın, bəzi dəyəri başlatılmış

418
00:31:53,410 --> 00:31:57,390
onun dəyəri sıfır dəyəri var.

419
00:31:57,390 --> 00:32:01,150
Belə ki, burada node * kök, biz açıq-aydın bir şey üçün başlamaq deyil

420
00:32:01,150 --> 00:32:06,350
Beləliklə, default dəyəri göstəricilər üzrə sıfır dəyəri olan null olacaq.

421
00:32:06,350 --> 00:32:11,870
X-u mənim dəyəri x.value sıfır olduğunu demək gedir

422
00:32:11,870 --> 00:32:14,260
x.left null və x.right null edir.

423
00:32:14,260 --> 00:32:21,070
Bir struct edir, çünki struct sahələrində bütün sıfır dəyərləri olacaq.

424
00:32:21,070 --> 00:32:24,410
Biz də, burada istifadə etmək lazım deyil.

425
00:32:24,410 --> 00:32:27,320
[Tələbə] Bu structs digər dəyişənlərin fərqli və digər dəyişənlər var

426
00:32:27,320 --> 00:32:31,400
zibil dəyərlər, bu adet sıfır var?

427
00:32:31,400 --> 00:32:36,220
Çox [Bowden] Digər dəyərlər. Belə ki, X, x sıfır olacaq.

428
00:32:36,220 --> 00:32:40,070
Qlobal miqyası da varsa, bu ilkin dəyər var. Okay. >>

429
00:32:40,070 --> 00:32:48,950
[Bowden] Ya ya sıfır verdi ilkin dəyəri.

430
00:32:48,950 --> 00:32:53,260
Mən bütün bu qayğı düşünürəm.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Belə ki, sual növbəti hissəsi, xahiş

432
00:32:58,390 --> 00:33:01,260
"İndi biz ehtiva adlı funksiyası yazmaq üçün

433
00:33:01,260 --> 00:33:04,930
bool bir prototip ilə int dəyəri düzəlişlər ".

434
00:33:04,930 --> 00:33:08,340
Biz bool int dəyəri düzəlişlər etmək istəmirik.

435
00:33:08,340 --> 00:33:15,110
Bizim prototip kimi baxmaq edir

436
00:33:15,110 --> 00:33:22,380
bool (int dəyər var.

437
00:33:22,380 --> 00:33:24,490
Və biz də ağac keçmək olacaq

438
00:33:24,490 --> 00:33:28,870
bu ki, dəyəri görmek üçün yoxlanılması lazımdır.

439
00:33:28,870 --> 00:33:38,290
Belə node * ağac). Okay.

440
00:33:38,290 --> 00:33:44,440
Və sonra biz kimi bir şey ilə zəng edə bilərsiniz

441
00:33:44,440 --> 00:33:46,090
bəlkə biz printf və ya bir şey lazımdır.

442
00:33:46,090 --> 00:33:51,040
6, bizim kök ehtiva edir.

443
00:33:51,040 --> 00:33:54,300
Bir və ya doğru, geri ki,

444
00:33:54,300 --> 00:33:59,390
şey isə 5 kök yalan qaytarmalıdır.

445
00:33:59,390 --> 00:34:02,690
Belə ki, bu həyata keçirilməsi üçün ikinci almaq.

446
00:34:02,690 --> 00:34:06,780
Siz ya iteratively və ya recursively bunu edə bilərsiniz.

447
00:34:06,780 --> 00:34:09,739
Biz hər şeyi müəyyən etdik yol haqqında gözəl şey olduğunu

448
00:34:09,739 --> 00:34:12,300
daha asan bizim recursive həll özünü verir

449
00:34:12,300 --> 00:34:14,719
qlobal dəyişən yol idi artıq.

450
00:34:14,719 --> 00:34:19,750
Biz yalnız əgər int dəyəri düzəlişlər Çünki, biz subtrees aşağı recursing heç bir yol var.

451
00:34:19,750 --> 00:34:24,130
Biz bizim üçün subtrees aşağı recurses ayrı bir köməkçi funksiyası var idi.

452
00:34:24,130 --> 00:34:29,610
Amma biz değiştirdik ildən bir arqument kimi ağac etmək

453
00:34:29,610 --> 00:34:32,760
bu həmişə birinci yerdə olardım

454
00:34:32,760 --> 00:34:35,710
indi biz recurse daha asan ola bilər.

455
00:34:35,710 --> 00:34:38,960
Belə ki, iterativ ya recursive, biz həm də gedəcəyəm

456
00:34:38,960 --> 00:34:46,139
lakin biz olduqca asan olan qədər ki recursive başa görəcəksiniz.

457
00:34:59,140 --> 00:35:02,480
Okay. Hər kəs biz ilə işləyə bilər bir şey varmı?

458
00:35:02,480 --> 00:35:12,000
>> [Tələbə] Mən bir həll iterativ var. >> Bütün hüququ, iterativ.

459
00:35:12,000 --> 00:35:16,030
OK, bu yaxşı görünür.

460
00:35:16,030 --> 00:35:18,920
Belə ki, onun vasitəsilə bizə gəzmək istəyirsiniz?

461
00:35:18,920 --> 00:35:25,780
[Tələbə] Sure. Mən ağac ilk node almaq üçün bir temp dəyişən seçin.

462
00:35:25,780 --> 00:35:28,330
Və sonra mən yalnız, temp bərabər null deyil isə vasitəsilə looped

463
00:35:28,330 --> 00:35:31,700
belə ağac hələ də isə hərhalda.

464
00:35:31,700 --> 00:35:35,710
Dəyəri dəyərinə bərabər olduqda və temp, işarə edir ki,

465
00:35:35,710 --> 00:35:37,640
sonra bu dəyər qaytarır.

466
00:35:37,640 --> 00:35:40,210
O sağ və ya sol tərəfdən əgər Əks halda, bu yoxlayır.

467
00:35:40,210 --> 00:35:43,400
Əgər artıq ağac var bir vəziyyət almaq, əgər

468
00:35:43,400 --> 00:35:47,330
bu çıxışları loop və saxta qaytarır - sonra qaytarır.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. Belə ki, yaxşı görünür.

470
00:35:52,190 --> 00:35:58,470
Hər kəs bir şey haqqında hər hansı bir şərh yoxdur?

471
00:35:58,470 --> 00:36:02,400
Mən düzgün şərh yoxdur.

472
00:36:02,400 --> 00:36:11,020
Biz nə edə bilər bir şey bu adam deyil.

473
00:36:11,020 --> 00:36:21,660
Oh, bu bir az uzunsov getmək olacaq.

474
00:36:21,660 --> 00:36:33,460
Hesab edirəm ki düzəltmək lazımdır. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Hər kəs ternary necə yadda olmalıdır.

476
00:36:37,150 --> 00:36:38,610
Mütləq keçmiş var viktorina edilmişdir

477
00:36:38,610 --> 00:36:41,170
ki, bir ternary operatoru ilə bir funksiyası vermək

478
00:36:41,170 --> 00:36:45,750
və ternary istifadə etmir ki, bir şey etmək, demək bu tərcümə.

479
00:36:45,750 --> 00:36:49,140
Mən ternary istifadə edirəm Belə ki, bu bir çox halda,

480
00:36:49,140 --> 00:36:54,610
bir vəziyyət bir şey bir dəyişən təyin yerləşir əgər

481
00:36:54,610 --> 00:36:58,580
başqa başqa bir şey eyni dəyişən seçin.

482
00:36:58,580 --> 00:37:03,390
Çox tez-tez şey bu cür çevrildi bilər ki, bir şey ki,

483
00:37:03,390 --> 00:37:14,420
bu ki, dəyişən müəyyən - və ya, yaxşı, bu doğrudur? Sonra bu, başqa bu.

484
00:37:14,420 --> 00:37:18,550
[Tələbə] ilk bir doğru, sağ əgər?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Bəli. Mən həmişə oxumaq yolu, temp, temp dəyər daha çox dəyər bərabərdir

486
00:37:25,570 --> 00:37:30,680
bu, başqa bu. Bu sualı var.

487
00:37:30,680 --> 00:37:35,200
Daha çox deyilmi? Sonra ilk şey. Else ikinci şey.

488
00:37:35,200 --> 00:37:41,670
Demək olar ki, həmişə - kolonda, yalnız - başımda, mən başqa oxuyun.

489
00:37:41,670 --> 00:37:47,180
>> Hər kəs bir recursive həlli varmı?

490
00:37:47,180 --> 00:37:49,670
Okay. Biz olacaq Bu - bu artıq böyük ola bilər

491
00:37:49,670 --> 00:37:53,990
ancaq daha yaxşı olacaq.

492
00:37:53,990 --> 00:37:58,720
Bu olduqca çox eyni dəqiq fikirdir.

493
00:37:58,720 --> 00:38:03,060
Bu, yalnız var, yaxşı, siz izah etmək istəyirsiniz?

494
00:38:03,060 --> 00:38:08,340
[Tələbə] Sure. Belə ki, biz, ağac ilk null əmin edirik

495
00:38:08,340 --> 00:38:13,380
ağac null əgər onda biz bunu aşkar deyil, çünki yalan geri olacaq, çünki.

496
00:38:13,380 --> 00:38:19,200
Və ağac hələ var, biz getmək - dəyəri cari node Əgər biz ilk yoxlayın.

497
00:38:19,200 --> 00:38:23,740
Əgər doğru qayıdın və sol və ya sağ əgər biz recurse.

498
00:38:23,740 --> 00:38:25,970
Ki, səs uyğun mu? >> Mm-hmm. (Sazişi)

499
00:38:25,970 --> 00:38:33,880
Beləliklə, bu demək olar ki, qeyd - Bu iterativ həll struktur çox bənzər.

500
00:38:33,880 --> 00:38:38,200
Əvəzinə recursing, biz bir müddət loop ki, yalnız var.

501
00:38:38,200 --> 00:38:40,840
Və ağac bərabər null deyil burada əsas işi

502
00:38:40,840 --> 00:38:44,850
biz isə loop çıxdı altında vəziyyətdə idi.

503
00:38:44,850 --> 00:38:50,200
Onlar çox oxşar istəyirik. Amma bu bir addım olacaq.

504
00:38:50,200 --> 00:38:54,190
İndi biz burada eyni şey.

505
00:38:54,190 --> 00:38:57,680
Bu xətlərin həm də eyni şey qaytarılması edirik dikkat,

506
00:38:57,680 --> 00:39:00,220
başqa bir dəlil fərqlidir.

507
00:39:00,220 --> 00:39:07,950
Beləliklə, biz bir ternary o etmək olacaq.

508
00:39:07,950 --> 00:39:13,790
I seçimi bir şey təşkil edib və bu, rəmzi etdi. Okay.

509
00:39:13,790 --> 00:39:21,720
Belə ki, biz geri olacaq ki, var.

510
00:39:21,720 --> 00:39:28,030
Bu edir zoomed, yaxşı, çox xətləri olmaq olur.

511
00:39:28,030 --> 00:39:31,060
Adətən, bir üslub şey kimi, mən bir çox insanlar hesab etmirəm

512
00:39:31,060 --> 00:39:38,640
ok sonra boşluq qoyub, amma siz ardıcıl istəyirsinizsə, bu gözəl var danışarlar.

513
00:39:38,640 --> 00:39:44,320
Dəyər ağac dəyərindən az olduqda, biz ağac sol recurse istəyirəm

514
00:39:44,320 --> 00:39:53,890
başqa biz ağac sağ recurse istəyirəm.

515
00:39:53,890 --> 00:39:58,610
Belə ki, bu göz kiçik edilməsi addım idi.

516
00:39:58,610 --> 00:40:02,660
Bu göz kiçik edilməsi iki addım -

517
00:40:02,660 --> 00:40:09,150
biz çox xətləri bu ayıra bilməz.

518
00:40:09,150 --> 00:40:16,500
Okay. Bu kiçik baxmaq edilməsi Addım iki, burada

519
00:40:16,500 --> 00:40:25,860
belə geri dəyər ağac dəyər bərabərdir, və ya hər şey.

520
00:40:25,860 --> 00:40:28,340
>> Bu əhəmiyyətli bir şey.

521
00:40:28,340 --> 00:40:30,860
O sinif aşkar etdi, mən əmin deyiləm

522
00:40:30,860 --> 00:40:34,740
lakin bu qısa qapanmasına qiymətləndirilməsi deyirlər.

523
00:40:34,740 --> 00:40:41,060
Burada fikir dəyəri == ağac dəyəri.

524
00:40:41,060 --> 00:40:49,960
Doğrudur ki, bu doğrudur və biz istəyirik 'və ya' ki, burada nə ilə.

525
00:40:49,960 --> 00:40:52,520
Belə ki, hətta burada nə düşünmədən,

526
00:40:52,520 --> 00:40:55,070
geri gedən bütün ifadə nədir?

527
00:40:55,070 --> 00:40:59,430
[Tələbə] True? >> Bəli, çünki bir şey doğru,

528
00:40:59,430 --> 00:41:04,990
or'd - bir şey ilə və ya doğru or'd mütləq doğrudur.

529
00:41:04,990 --> 00:41:08,150
Belə ki, tezliklə biz geri value = ağac dəyəri bax

530
00:41:08,150 --> 00:41:10,140
biz yalnız doğru geri olacaq.

531
00:41:10,140 --> 00:41:15,710
Hətta recurse getmir daha line aşağı edir.

532
00:41:15,710 --> 00:41:20,980
Biz bu bir addım bilər.

533
00:41:20,980 --> 00:41:29,490
Arxiv ağac bərabər null və bütün bu deyil.

534
00:41:29,490 --> 00:41:32,650
Bu bir-line funksiyası etdi.

535
00:41:32,650 --> 00:41:36,790
Bu da qısa qapanma qiymətləndirilməsi nümunəsidir.

536
00:41:36,790 --> 00:41:40,680
Amma indi eyni fikirdir -

537
00:41:40,680 --> 00:41:47,320
əvəzinə - əgər ağac deyil bərabər null edir - yaxşı və ya,

538
00:41:47,320 --> 00:41:49,580
ağac bərabər null etsə, o, pis halda

539
00:41:49,580 --> 00:41:54,790
ağac null bərabərdir, onda birinci şərt yalan olacaq.

540
00:41:54,790 --> 00:42:00,550
Bir şey ilə anded Belə yalan nə olacaq?

541
00:42:00,550 --> 00:42:04,640
[Tələbə] Asma. >> Bəli. Bu, qısa qapanma qiymətləndirilməsi digər yarısı

542
00:42:04,640 --> 00:42:10,710
Ü ağac, biz hətta getmək üçün bərabər null getmir əgər -

543
00:42:10,710 --> 00:42:14,930
ağac bərabər null əgər və ya, sonra biz dəyər == ağac dəyəri nə deyil.

544
00:42:14,930 --> 00:42:17,010
Biz yalnız dərhal yalan geri olacaq.

545
00:42:17,010 --> 00:42:20,970
Qısa qapanma qiymətləndirmək deyil əgər bəri hansı, vacibdir

546
00:42:20,970 --> 00:42:25,860
ağac bərabər null əgər, sonra bu ikinci vəziyyətdə, seg günah edir

547
00:42:25,860 --> 00:42:32,510
ağac-> dəyəri null dereferencing çünki.

548
00:42:32,510 --> 00:42:40,490
Belə ki, var. Bu edə bilərsiniz - bir dəfə artıq tutulub.

549
00:42:40,490 --> 00:42:44,840
Bu, bu, bu bir xətt edilməsi deyil, həmçinin bir çox şey

550
00:42:44,840 --> 00:42:49,000
lakin burada bəlkə şəraitində ortaq bir şey deyil

551
00:42:49,000 --> 00:42:59,380
lakin (ağac! = NULL və ağac-> dəyəri == dəyəri), nə əgər.

552
00:42:59,380 --> 00:43:01,560
Bu çox ümumi vəziyyəti, harada əvəzinə olan

553
00:43:01,560 --> 00:43:06,770
iki ifs bu qırmaq, istədiyim, ağac null edir?

554
00:43:06,770 --> 00:43:11,780
OK, bu, null deyil, belə ki, indi dəyərinə bərabər ağac dəyəri? Bu etməyin.

555
00:43:11,780 --> 00:43:17,300
Bunun əvəzinə, bu vəziyyəti, bu günah seg heç vaxt

556
00:43:17,300 --> 00:43:21,220
bu null olmaq olur, əgər çıxmaq olacaq.

557
00:43:21,220 --> 00:43:24,000
Sizin ağac tamamilə etibarsız göstərici olduqda Bəli, mən tapmaq, hələ, günah seg bilər

558
00:43:24,000 --> 00:43:26,620
ağac null əgər ancaq bu günahı seg bilməz.

559
00:43:26,620 --> 00:43:32,900
Bu null Əgər siz ilk növbədə göstərici dereferenced əvvəl, çıxmaq olardı.

560
00:43:32,900 --> 00:43:35,000
[Tələbə] Bu adlandırılan tənbəl qiymətləndirilməsi mı?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy qiymətləndirilməsi ayrı bir şeydir.

562
00:43:40,770 --> 00:43:49,880
Lazy qiymətləndirmə, bir dəyər üçün xahiş daha kimi

563
00:43:49,880 --> 00:43:54,270
bir dəyəri cür hesablamaq üçün xahiş, lakin dərhal ehtiyac yoxdur.

564
00:43:54,270 --> 00:43:59,040
Siz həqiqətən ehtiyac qədər Belə ki, qiymətləndirdi deyil.

565
00:43:59,040 --> 00:44:03,920
Bu tam eyni şey deyil, lakin Huffman pset olaraq,

566
00:44:03,920 --> 00:44:06,520
biz "tənbəlcəsinə" yazmaq söyləyir.

567
00:44:06,520 --> 00:44:08,670
Biz əslində yazma buffering edirik, çünki biz bunu səbəbi -

568
00:44:08,670 --> 00:44:11,820
biz, bir zaman fərdi bit yazmaq istəmirəm

569
00:44:11,820 --> 00:44:15,450
və ya bir zamanda fərdi bytes biz əvəzinə bayt yığın almaq istəyirəm.

570
00:44:15,450 --> 00:44:19,270
Biz bayt yığın var bir dəfə sonra, sonra biz onu yazmaq lazımdır.

571
00:44:19,270 --> 00:44:22,640
Yazmaq xahiş baxmayaraq - və fwrite və fread şey eyni cür edin.

572
00:44:22,640 --> 00:44:26,260
Onlar oxuyur və yazır bufer.

573
00:44:26,260 --> 00:44:31,610
Dərhal yazmaq üçün xahiş baxmayaraq, yəqin ki, olmayacaq.

574
00:44:31,610 --> 00:44:34,540
Və şeyi yazılı olacaq əmin ola bilməz

575
00:44:34,540 --> 00:44:37,540
siz hfclose zəng və ya hər hansı qədər ki,

576
00:44:37,540 --> 00:44:39,620
sonra deyir ki, tamam, mən, mənim fayl bağlanması alıram

577
00:44:39,620 --> 00:44:43,450
Mən daha yaxşı hələ yazılı olmayan hər şey yazmaq istədiyiniz deməkdir.

578
00:44:43,450 --> 00:44:45,770
Bu, heç hər şeyi yazmaq lazımdır ki,

579
00:44:45,770 --> 00:44:49,010
Dosyayı bağlanması, sonra qədər bu lazımdır.

580
00:44:49,010 --> 00:44:56,220
Belə ki, yalnız nə tənbəl - bu baş var qədər gözləyir.

581
00:44:56,220 --> 00:44:59,990
Bu - 51 almaq və daha çox ətraflı daxil olacaq

582
00:44:59,990 --> 00:45:05,470
51 OCaml və hər şey, hər şey recursion çünki.

583
00:45:05,470 --> 00:45:08,890
Heç əsasən, həllər iterativ var.

584
00:45:08,890 --> 00:45:11,550
Hər şey recursion və tənbəl qiymətləndirmə edir

585
00:45:11,550 --> 00:45:14,790
hallarda bir çox üçün əhəmiyyətli olacaq

586
00:45:14,790 --> 00:45:19,920
siz tənbəlcəsinə qiymətləndirmək olmasaydı yerləşir ki, deməkdir -

587
00:45:19,920 --> 00:45:24,760
Məsələn sonsuz uzun olan axınları var.

588
00:45:24,760 --> 00:45:30,990
Nəzəri olaraq, siz 1-2-3-4-5-6-7 bir sel kimi təbii nömrələri hesab edə bilər

589
00:45:30,990 --> 00:45:33,090
Belə ki, tənbəlcəsinə qiymətləndirilir şey gözəl olur.

590
00:45:33,090 --> 00:45:37,210
Mən onuncu sayı istəyirsiniz, onda mən onuncu sayı qədər qiymətləndirmək olar.

591
00:45:37,210 --> 00:45:40,300
Mən yüzüncü sayı istəyirsinizsə, onda mən yüzüncü sayı qədər qiymətləndirmək olar.

592
00:45:40,300 --> 00:45:46,290
Tənbəl qiymətləndirmə olmadan, o, dərhal bütün nömrələri qiymətləndirmək üçün cəhd olacaq.

593
00:45:46,290 --> 00:45:50,000
Siz sonsuz bir çox nömrələri qiymətləndirilməsi edirik ki, yalnız mümkün deyil.

594
00:45:50,000 --> 00:45:52,080
Belə hallar çox olduğu tənbəl qiymətləndirilməsi

595
00:45:52,080 --> 00:45:57,840
şeyi işləmək yalnız vacibdir.

596
00:45:57,840 --> 00:46:05,260
>> İndi daxil olacaq yerləşir daxil yazmaq üçün

597
00:46:05,260 --> 00:46:08,430
eynilə onun müəyyən dəyişir.

598
00:46:08,430 --> 00:46:10,470
Belə ki, hazırda bu bool insert (int) dəyəri var.

599
00:46:10,470 --> 00:46:23,850
Biz bool insert (int dəyəri node * ağacı) ki, dəyişiklik olacaq.

600
00:46:23,850 --> 00:46:29,120
Biz həqiqətən bir bit bir daha dəyişiklik olacaq, biz niyə görəcəksiniz.

601
00:46:29,120 --> 00:46:32,210
Və edək, yalnız onun heck üçün build_node hərəkət

602
00:46:32,210 --> 00:46:36,730
biz bir funksiyası prototip yazmaq üçün yoxdur belə yuxarıda daxil edin.

603
00:46:36,730 --> 00:46:42,450
Hansı insert ilə build_node istifadə olacaq ki, bir ipucu edir.

604
00:46:42,450 --> 00:46:49,590
Okay. Üçün bir dəqiqə edin.

605
00:46:49,590 --> 00:46:52,130
Siz ki, çəkmək istəyirsinizsə, mən yenidən xilas edirəm

606
00:46:52,130 --> 00:47:00,240
və ya, ən azı, mən artıq idi.

607
00:47:00,240 --> 00:47:04,190
Mən, insert məntiqi düşünmək bir qədər fasilə istədi

608
00:47:04,190 --> 00:47:08,750
siz hesab edə bilər.

609
00:47:08,750 --> 00:47:12,860
Ümumiyyətlə, yalnız heç yarpaqları da daxil ediləcək.

610
00:47:12,860 --> 00:47:18,640
I 1 daxil, əgər kimi, sonra qaçılmaz 1 daxil etmək gidiyorum -

611
00:47:18,640 --> 00:47:21,820
Mən qara dəyişdirmək lazımdır - I'll burada 1 daxil edilir.

612
00:47:21,820 --> 00:47:28,070
I 4 daxil və ya, mən burada artıq 4 daxil olmaq istəyirəm.

613
00:47:28,070 --> 00:47:32,180
Heç nə fərqi Belə ki, bir yarpaq da daxil etmək olacaq.

614
00:47:32,180 --> 00:47:36,130
Siz var Bütün Siz node almaq qədər ağac aşağı təkrarlamaq deyil

615
00:47:36,130 --> 00:47:40,890
ki node ana, yeni node ana olmalıdır

616
00:47:40,890 --> 00:47:44,560
və sonra asılı olaraq, onun sağ və ya sol pointer dəyişdirmək

617
00:47:44,560 --> 00:47:47,060
bu və ya daha çox cari node az deyil.

618
00:47:47,060 --> 00:47:51,180
Yeni node qeyd etmək ki, pointer dəyişdirin.

619
00:47:51,180 --> 00:48:05,490
Belə ki, ağac aşağı təkrarlamaq yeni node üçün yarpaq point etmək.

620
00:48:05,490 --> 00:48:09,810
Həmçinin bundan əvvəl vəziyyət növü qadağan niyə düşünmək,

621
00:48:09,810 --> 00:48:17,990
doğru olduğu Mən binar ağac inşa yerləşir

622
00:48:17,990 --> 00:48:19,920
yalnız bir node baxdı, əgər

623
00:48:19,920 --> 00:48:24,830
bütün yol aşağı iterated ancaq 9 7 solunda idi.

624
00:48:24,830 --> 00:48:29,770
Belə ki, bu ssenari mümkün deyil -

625
00:48:29,770 --> 00:48:32,530
haqqında 9 və ya bir şey daxil düşünürəm; ilk node da,

626
00:48:32,530 --> 00:48:35,350
Mən 7 görmək və mən yalnız doğru getmək üçün gedirəm gedirəm.

627
00:48:35,350 --> 00:48:38,490
Belə ki, bir yarpaq gedən daxil oldum, mən nə fərqi yoxdur

628
00:48:38,490 --> 00:48:40,790
və müvafiq alqoritmi istifadə edərək, bir yarpaq üçün

629
00:48:40,790 --> 00:48:43,130
mənə 7 sol 9 daxil etmək üçün mümkün olacaq

630
00:48:43,130 --> 00:48:48,250
kimi tezliklə mən 7 hit Mən doğru getmək üçün gedirəm, çünki.

631
00:48:59,740 --> 00:49:02,070
Hər başlamaq üçün bir şey varmı?

632
00:49:02,070 --> 00:49:05,480
[Tələbə] Mən bunu. >> Sure.

633
00:49:05,480 --> 00:49:09,200
[Tələbə, anlaşılmaz]

634
00:49:09,200 --> 00:49:14,390
[Digər tələbəsı, anlaşılmaz]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Bu yüksək qiymətləndirib edir. Okay. Izah etmək istəyirsiniz?

636
00:49:18,330 --> 00:49:20,690
>> Biz daxil bilirsiniz ki, ildən [Tələbə]

637
00:49:20,690 --> 00:49:24,060
ağac sonunda yeni qovşaqlarının,

638
00:49:24,060 --> 00:49:28,070
Mən iteratively ağac vasitəsilə looped

639
00:49:28,070 --> 00:49:31,360
Mən null işarə bir node var qədər.

640
00:49:31,360 --> 00:49:34,220
Və sonra sağ və ya sol tərəfdə ya qoymaq üçün qərar

641
00:49:34,220 --> 00:49:37,420
bu hüququ dəyişən istifadə, bu yerləşir qoymaq üçün mənə.

642
00:49:37,420 --> 00:49:41,850
Və sonra, mahiyyətcə, yalnız ötən etdi -

643
00:49:41,850 --> 00:49:47,520
o yaradan ki, yeni node ki, temp node point,

644
00:49:47,520 --> 00:49:50,770
sol tərəfində və ya sağ ya dəyəri doğru nə asılı olaraq.

645
00:49:50,770 --> 00:49:56,530
Nəhayət, mən öz test dəyəri yeni node dəyəri.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okay, mən burada bir məsələ oldu.

647
00:49:59,550 --> 00:50:02,050
Bu orada yolu 95% kimi.

648
00:50:02,050 --> 00:50:07,550
Görürəm ki, bir məsələ də, hər kəsdən bir məsələ görür?

649
00:50:07,550 --> 00:50:18,400
Onlar loop çıxmaq altında hal nədir?

650
00:50:18,400 --> 00:50:22,100
[Tələbə] temp null deyil? >> Bəli. Temp null əgər Beləliklə, siz loop çıxmaq necə.

651
00:50:22,100 --> 00:50:30,220
Amma burada nə etməliyəm?

652
00:50:30,220 --> 00:50:35,410
Qaçılmaz null olan mən dereference temp.

653
00:50:35,410 --> 00:50:39,840
Beləliklə, siz nə etmək lazımdır başqa bir şey temp null qədər yalnız, track saxlamaq deyil

654
00:50:39,840 --> 00:50:45,590
bütün zaman əsas takip etmək istəyirəm.

655
00:50:45,590 --> 00:50:52,190
Biz də node * valideyn istəyirəm ki, biz null ilk ki saxlaya bilərsiniz danışarlar.

656
00:50:52,190 --> 00:50:55,480
Bu, ağac kökü üçün qəribə davranış üçün gedir

657
00:50:55,480 --> 00:50:59,210
lakin biz almaq lazımdır.

658
00:50:59,210 --> 00:51:03,950
Dəyəri nə daha böyükdür, onda temp = temp hüququ.

659
00:51:03,950 --> 00:51:07,910
Amma əvvəl ki, valideyn = temp.

660
00:51:07,910 --> 00:51:14,500
Və ya valideynlər həmişə bərabər temp gedir? Halda ki?

661
00:51:14,500 --> 00:51:19,560
Temp null deyil, onda mən, nə olursa olsun, aşağı hərəkət gedirəm

662
00:51:19,560 --> 00:51:24,030
temp ana olan bir node.

663
00:51:24,030 --> 00:51:27,500
Belə ki, valideyn temp olacaq, sonra aşağı temp hərəkət.

664
00:51:27,500 --> 00:51:32,410
İndi temp null, lakin null ki şey müəssisəyə valideyn xal.

665
00:51:32,410 --> 00:51:39,110
Belə ki, aşağı burada, mən sağ 1 bərabərdir təyin etmək istəmirəm.

666
00:51:39,110 --> 00:51:41,300
Mən, belə ki, sağ = 1, əgər sağ köçürülüb

667
00:51:41,300 --> 00:51:45,130
və mən də etmək istəyirəm tapmaq -

668
00:51:45,130 --> 00:51:48,530
Siz sol hərəkət etsəniz, 0 hüququ bərabər qurmaq istəyirik.

669
00:51:48,530 --> 00:51:55,950
Və ya başqa heç sağa hərəkət edin.

670
00:51:55,950 --> 00:51:58,590
Belə ki, sağ = 0. Sağ = 1 varsa,

671
00:51:58,590 --> 00:52:04,260
indi biz əsas sağ göstərici newnode etmək

672
00:52:04,260 --> 00:52:08,520
başqa biz valideyn sol göstərici newnode etmək istəyirəm.

673
00:52:08,520 --> 00:52:16,850
Ki Suallar?

674
00:52:16,850 --> 00:52:24,880
Okay. Beləliklə, bu yolla biz - də, faktiki olaraq, əvəzinə bu etdiyini,

675
00:52:24,880 --> 00:52:29,630
biz yarısı siz build_node istifadə gözlənilir.

676
00:52:29,630 --> 00:52:40,450
Newnode null bərabər, əgər, sonra saxta qayıtmaq.

677
00:52:40,450 --> 00:52:44,170
Ki, var. İndi bu biz nə gözlənilir budur.

678
00:52:44,170 --> 00:52:47,690
>> Bu heyət həllər nə edir.

679
00:52:47,690 --> 00:52:52,360
Mən bu barədə gedən "doğru" yolu kimi bu razı

680
00:52:52,360 --> 00:52:57,820
lakin bu gözəl gözəl və işləyəcək.

681
00:52:57,820 --> 00:53:02,840
İndi bir az qəribə doğru bir şey deyil

682
00:53:02,840 --> 00:53:08,310
ağac null kimi off başlayır, biz bir null ağac keçir.

683
00:53:08,310 --> 00:53:12,650
Mən bunu bir null ağac keçən davranışı müəyyən asılıdır danışarlar.

684
00:53:12,650 --> 00:53:15,490
Mən sizə bir null ağac keçmək əgər edirəm

685
00:53:15,490 --> 00:53:17,520
sonra null ağac daxil dəyəri daxil

686
00:53:17,520 --> 00:53:23,030
yalnız dəyər ki, bir node olduğu bir ağac qaytarmalıdır.

687
00:53:23,030 --> 00:53:25,830
Insanlar razısınızmı? Siz ola bilər, siz istəyirdi,

688
00:53:25,830 --> 00:53:28,050
Bir null ağac keçmək əgər

689
00:53:28,050 --> 00:53:31,320
və bunu bir dəyər əlavə etmək istəyirik, saxta qayıtmaq.

690
00:53:31,320 --> 00:53:33,830
Bu müəyyən qədər sizin üçün deyil.

691
00:53:33,830 --> 00:53:38,320
Mən o bildirib və ilk şey -

692
00:53:38,320 --> 00:53:40,720
çünki yaxşı, siz sorun bunu etmək olacaq

693
00:53:40,720 --> 00:53:44,090
biz şey üçün qlobal göstərici olsaydı, bu, daha asan olardı

694
00:53:44,090 --> 00:53:48,570
ağac null əgər ancaq ki, biz bu barədə nə edə heç bir şey var deyil.

695
00:53:48,570 --> 00:53:50,960
Biz yalnız yalan ola bilər.

696
00:53:50,960 --> 00:53:52,840
Mən insert dəyişdirmək üçün gedirəm.

697
00:53:52,840 --> 00:53:56,540
Biz texniki yalnız burada, bu doğru dəyişə bilər

698
00:53:56,540 --> 00:53:58,400
necə ki, şeyə iterating oldu

699
00:53:58,400 --> 00:54:04,530
amma bir node ** ağac etmək üçün daxil dəyişdirmək üçün gedirəm.

700
00:54:04,530 --> 00:54:07,510
Cüt göstəricilər.

701
00:54:07,510 --> 00:54:09,710
Bu nə deməkdir?

702
00:54:09,710 --> 00:54:12,330
Əvəzində qovşaqlarının üçün göstəricilər ilə məşğul olan,

703
00:54:12,330 --> 00:54:16,690
Mən manipulyasiya etmək gidiyorum şey bu göstəricisidir.

704
00:54:16,690 --> 00:54:18,790
Mən bu göstərici manipulyasiya üçün gedirəm.

705
00:54:18,790 --> 00:54:21,770
Mən birbaşa göstəricilərinə manipulyasiya üçün gedirəm.

706
00:54:21,770 --> 00:54:25,760
, Aşağı düşünmək ildən bu mənada edir -

707
00:54:25,760 --> 00:54:33,340
də, hazırda bu bal null üçün.

708
00:54:33,340 --> 00:54:38,130
Mən istəyirəm null deyil işaret üçün bu göstərici manipulyasiya edir.

709
00:54:38,130 --> 00:54:40,970
Mən bunu mənim yeni node qeyd etmək istəyirəm.

710
00:54:40,970 --> 00:54:44,870
Mən yalnız mənim göstəricilərinə to göstəricilərinə takip Əgər

711
00:54:44,870 --> 00:54:47,840
sonra mən bir valideyn göstərici izlemek ehtiyac yoxdur.

712
00:54:47,840 --> 00:54:52,640
Mən yalnız göstərici null işarə edir görmek üçün takip edə bilərsiniz

713
00:54:52,640 --> 00:54:54,580
və pointer işarə edir əgər null üçün

714
00:54:54,580 --> 00:54:57,370
Mən istəyirəm node qeyd etmək dəyişdirin.

715
00:54:57,370 --> 00:55:00,070
Mən göstərici bir pointer çünki Mən onu dəyişə bilərsiniz.

716
00:55:00,070 --> 00:55:02,040
Indi bu hüququ bax edək.

717
00:55:02,040 --> 00:55:05,470
Siz, həqiqətən, recursively olduqca asanlıqla bunu edə bilərsiniz.

718
00:55:05,470 --> 00:55:08,080
Biz bunu istəyirsiniz?

719
00:55:08,080 --> 00:55:10,980
Bəli, biz edirik.

720
00:55:10,980 --> 00:55:16,790
>> Nin recursively görmək edək.

721
00:55:16,790 --> 00:55:24,070
Birincisi, nə bizim əsas işi olacaq?

722
00:55:24,070 --> 00:55:29,140
Demək olar ki, həmişə bizim əsas işi, ancaq faktiki olaraq, bu çətin növ edir.

723
00:55:29,140 --> 00:55:34,370
Ilk ilk şey, əgər (ağac == NULL)

724
00:55:34,370 --> 00:55:37,550
Mən yalnız yalan qayıtmaq olacaq danışarlar.

725
00:55:37,550 --> 00:55:40,460
Bu ağac olan null fərqlidir.

726
00:55:40,460 --> 00:55:44,510
Bu kök göstərici null olan göstəricisidir

727
00:55:44,510 --> 00:55:48,360
olan kök göstərici mövcud deyil deməkdir.

728
00:55:48,360 --> 00:55:52,390
Belə ki, aşağı burada, mən əgər

729
00:55:52,390 --> 00:55:55,760
node * - nin bu təkrar edək.

730
00:55:55,760 --> 00:55:58,960
Node * root = NULL,

731
00:55:58,960 --> 00:56:00,730
və sonra mən kimi bir şey etməklə insert zəng gedirəm

732
00:56:00,730 --> 00:56:04,540
və kök daxil 4 daxil edin.

733
00:56:04,540 --> 00:56:06,560
Belə & kök, kök bir node * Əgər

734
00:56:06,560 --> 00:56:11,170
sonra və kök bir node ** olacaq.

735
00:56:11,170 --> 00:56:15,120
Bu etibarlıdır. Burada Bu halda, ağac,

736
00:56:15,120 --> 00:56:20,120
ya daxil - ağac null deyil.

737
00:56:20,120 --> 00:56:24,630
Burada. Tree null deyil; * ağac null ki, gözəl olan

738
00:56:24,630 --> 00:56:26,680
* ağac null, onda mən bu manipulyasiya bilər, çünki

739
00:56:26,680 --> 00:56:29,210
İndi mən onu qeyd etmək istəyirəm nə qeyd etmək.

740
00:56:29,210 --> 00:56:34,750
Ağac null olsa ki, mən yalnız burada gəldi və null dedi deməkdir.

741
00:56:34,750 --> 00:56:42,710
Mənada deyil. Hesab edirəm ki, bir şey edə bilməz.

742
00:56:42,710 --> 00:56:45,540
Ağac null varsa, yalan qayıtmaq.

743
00:56:45,540 --> 00:56:48,220
Mən əsasən artıq real baza halda nə dedi.

744
00:56:48,220 --> 00:56:50,580
Və nə olacaq?

745
00:56:50,580 --> 00:56:55,030
[Tələbə, anlaşılmaz]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Bəli. Belə ki, (* ağac == NULL) əgər.

747
00:57:00,000 --> 00:57:04,520
Bu burada işə aid

748
00:57:04,520 --> 00:57:09,640
mənim qırmızı göstərici göstəricisidir, mən diqqət edirəm, burada

749
00:57:09,640 --> 00:57:12,960
Mən bu göstərici diqqət alıram kimi, belə ki, indi bu göstərici diqqət edirəm.

750
00:57:12,960 --> 00:57:15,150
İndi bu göstərici diqqət edirəm.

751
00:57:15,150 --> 00:57:18,160
Belə ki, əgər mənim node ** olan mənim qırmızı göstərici,

752
00:57:18,160 --> 00:57:22,880
daim - * Əgər mənim qırmızı pointer, heç null edir

753
00:57:22,880 --> 00:57:28,470
ki, mən bir pointer işarə diqqət alıram olduğu halda am deməkdir -

754
00:57:28,470 --> 00:57:32,530
bu bir yarpaq aid bir göstəricisidir.

755
00:57:32,530 --> 00:57:41,090
Mən yeni node işaret üçün bu göstərici dəyişə istəyirəm.

756
00:57:41,090 --> 00:57:45,230
Burada geri gel.

757
00:57:45,230 --> 00:57:56,490
Mənim newnode yalnız node * n = build_node (dəyər) olacaq

758
00:57:56,490 --> 00:58:07,300
sonra n, n = NULL əgər yalan qayıtmaq.

759
00:58:07,300 --> 00:58:12,600
Else biz göstərici hazırda işarə nə dəyişdirmək istədiyiniz

760
00:58:12,600 --> 00:58:17,830
indi bizim yeni inşa node qeyd etmək.

761
00:58:17,830 --> 00:58:20,280
Biz əslində burada edə bilərsiniz.

762
00:58:20,280 --> 00:58:30,660
Əvəzində n deyərək, biz demək * ağac = * ağac əgər.

763
00:58:30,660 --> 00:58:35,450
Hər kəs başa düşürük ki? Bu göstəricilər üçün göstəricilər ilə məşğul olaraq,

764
00:58:35,450 --> 00:58:40,750
biz onları qeyd etmək istəyirəm şeyi qeyd etmək null göstəricilərinə dəyişə bilərsiniz.

765
00:58:40,750 --> 00:58:42,820
Bu bizim əsas işi var.

766
00:58:42,820 --> 00:58:45,740
>> İndi təkrar və ya bizim recursion,

767
00:58:45,740 --> 00:58:51,430
biz bunu etdik bütün digər recursions çox oxşar olacaq.

768
00:58:51,430 --> 00:58:55,830
Biz, dəyəri daxil etmək istəyirəm olacaq

769
00:58:55,830 --> 00:58:59,040
və indi mən yenə ternary istifadə gedirəm, amma nə bizim vəziyyətdə olacaq?

770
00:58:59,040 --> 00:59:05,180
Biz biz sol və ya sağ getmək istəyirəm karar üçün nə aradığınız edir?

771
00:59:05,180 --> 00:59:07,760
Ayrı-ayrı addımlar bunu edək.

772
00:59:07,760 --> 00:59:18,850
Əgər (dəyər <) nə?

773
00:59:18,850 --> 00:59:23,200
[Tələbə] Ağac dəyəri?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Mən hazırda Ben unutmayın -

775
00:59:27,490 --> 00:59:31,260
[Tələbələr, anlaşılmaz]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Bəli, belə burada, deyək ki, bu yaşıl arrow

777
00:59:34,140 --> 00:59:39,050
ağac hazırda nə Məsələn, bu göstərici bir göstəricisidir.

778
00:59:39,050 --> 00:59:46,610
Belə ki, 3-bir göstərici bir pointer am deməkdir.

779
00:59:46,610 --> 00:59:48,800
Bu dereference iki dəfə yaxşı keçdi.

780
00:59:48,800 --> 00:59:51,010
Mən nə - necə ki etməliyəm?

781
00:59:51,010 --> 00:59:53,210
[Tələbə] dəfə Dereference, sonra nə arrow yol?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Belə (* ağacı) bir dereference edir -> dəyər

783
00:59:58,420 --> 01:00:05,960
mənə dolayı işarə edirəm ki node dəyəri vermək niyyətindədir.

784
01:00:05,960 --> 01:00:11,980
Mən də sizə tercih əgər tree.value ** yaza bilərsiniz.

785
01:00:11,980 --> 01:00:18,490
Işləri Ya.

786
01:00:18,490 --> 01:00:26,190
O halda, mən dəyəri daxil zəng etmək istəyirəm.

787
01:00:26,190 --> 01:00:32,590
Nə mənim yenilənir node ** olacaq?

788
01:00:32,590 --> 01:00:39,440
Mən sol getmək istəyirəm, belə ki, ** tree.left mənim sol olacaq.

789
01:00:39,440 --> 01:00:41,900
Mən o şey üçün pointer istəyirəm

790
01:00:41,900 --> 01:00:44,930
ki, sol null göstərici olan qədər başa əgər,

791
01:00:44,930 --> 01:00:48,360
Mən yeni node qeyd etmək onu dəyişə bilərsiniz.

792
01:00:48,360 --> 01:00:51,460
>> Və digər halda çox oxşar ola bilər.

793
01:00:51,460 --> 01:00:55,600
Nin həqiqətən mənim ternary ki, hazırda edək.

794
01:00:55,600 --> 01:01:04,480
Əgər dəyər <(** ağac). Dəyəri dəyər daxil edin.

795
01:01:04,480 --> 01:01:11,040
Sonra, sol bizim ** güncellemek istəyirsinizsə

796
01:01:11,040 --> 01:01:17,030
başqa biz sağ bizim ** yeniləmək istəyirəm.

797
01:01:17,030 --> 01:01:22,540
[Tələbə] ki pointer üçün pointer almaq mı?

798
01:01:22,540 --> 01:01:30,940
[Bowden] unutmayın - ** tree.right bir node ulduz edir.

799
01:01:30,940 --> 01:01:35,040
[Tələbə, anlaşılmaz] >> Bəli.

800
01:01:35,040 --> 01:01:41,140
** Tree.right bu göstərici ya bir şey kimi.

801
01:01:41,140 --> 01:01:45,140
Belə ki, bir pointer alaraq ki, mən istədiyiniz nə mənə verir

802
01:01:45,140 --> 01:01:50,090
ki, oğlan üçün pointer edir.

803
01:01:50,090 --> 01:01:54,260
Biz iki göstəricilərinə istifadə niyə [Tələbə] biz yenidən getmək bilər?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Bəli. Belə ki, - heç əvvəl bilər və həll

805
01:01:58,220 --> 01:02:04,540
iki göstəricilərinə etmədən bunu bir yol idi.

806
01:02:04,540 --> 01:02:08,740
Siz iki göstəricilərinə istifadə anlamaq lazımdır

807
01:02:08,740 --> 01:02:11,660
və bu təmiz həll edir.

808
01:02:11,660 --> 01:02:16,090
Həmçinin, mənim ağac ne olur ki, qeyd -

809
01:02:16,090 --> 01:02:24,480
mənim kök null idi nə olur? Mən burada, bu halda bunu ne olur?

810
01:02:24,480 --> 01:02:30,540
Belə node * root = NULL, & kök daxil 4 daxil edin.

811
01:02:30,540 --> 01:02:35,110
Kök bu sonra nə olacaq?

812
01:02:35,110 --> 01:02:37,470
[Tələbə, anlaşılmaz] >> Bəli.

813
01:02:37,470 --> 01:02:41,710
Root dəyəri 4 olacaq.

814
01:02:41,710 --> 01:02:45,510
Root sol null olacaq, kök sağ null olacaq.

815
01:02:45,510 --> 01:02:49,490
Halda biz, ünvanı kök keçməyən

816
01:02:49,490 --> 01:02:52,490
biz kök dəyişdirmək bilmədi.

817
01:02:52,490 --> 01:02:56,020
Halda, burada ağac - kök null olduğu

818
01:02:56,020 --> 01:02:58,410
biz yalnız yalan qayıtmaq idi. Biz edə heç bir şey yoxdur.

819
01:02:58,410 --> 01:03:01,520
Biz boş ağac bir node ekleyemezsiniz.

820
01:03:01,520 --> 01:03:06,810
Amma indi biz, biz yalnız bir node ağac daxil boş ağac olun.

821
01:03:06,810 --> 01:03:13,400
Hansı adətən bu iş ehtimal ki, gözlənilən yoldur.

822
01:03:13,400 --> 01:03:21,610
>> Bundan əlavə, bu xeyli qısa

823
01:03:21,610 --> 01:03:26,240
həmçinin müəssisənin track saxlanılması, və siz bütün yol aşağı təkrarlamaq.

824
01:03:26,240 --> 01:03:30,140
İndi mənim valideyn var və mən yalnız hər hansı mənim ana sağ göstərici var.

825
01:03:30,140 --> 01:03:35,640
Biz iteratively bu idi əgər əvəzinə, bir müddət loop ilə eyni fikir olardı.

826
01:03:35,640 --> 01:03:38,100
Lakin əvəzinə mənim ana göstərici ilə məşğul olan,

827
01:03:38,100 --> 01:03:40,600
əvəzinə mənim cari göstərici şey olacaq

828
01:03:40,600 --> 01:03:43,790
Mən birbaşa mənim yeni node qeyd etmək değiştirmeyle edirəm ki,.

829
01:03:43,790 --> 01:03:46,090
Mən bunu sol işarə olsun ilə məşğul yoxdur.

830
01:03:46,090 --> 01:03:48,810
Mən doğru işarə olsun ilə məşğul yoxdur.

831
01:03:48,810 --> 01:04:00,860
Bu göstərici, mən yeni node qeyd etmək müəyyən etmək gidiyorum nə olursa olsun yalnız deyil.

832
01:04:00,860 --> 01:04:05,740
Hər kəs bunu necə anlamaq?

833
01:04:05,740 --> 01:04:09,460
Əgər biz niyə bu şəkildə etmək istəyirəm

834
01:04:09,460 --> 01:04:14,920
lakin ən azı bu bir həll kimi işlər?

835
01:04:14,920 --> 01:04:17,110
[Tələbə] Harada biz doğru qayıtmaq edirsiniz?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Burada yəqin ki.

837
01:04:21,550 --> 01:04:26,690
Biz doğru bu daxil edin, doğru geri.

838
01:04:26,690 --> 01:04:32,010
Else, aşağı burada daxil yekunları nə qayıtmaq istəyirəm olacaq.

839
01:04:32,010 --> 01:04:35,950
>> Və bu recursive funksiyası barədə xüsusi nedir?

840
01:04:35,950 --> 01:04:43,010
O, belə uzun bəzi optimallaşdırılması ilə tərtib kimi, recursive quyruq var

841
01:04:43,010 --> 01:04:48,060
ki, bu etiraf edəcək və bu bir yığın daşqın almaq heç vaxt

842
01:04:48,060 --> 01:04:53,230
bizim ağac 10,000 ya 10 milyon hündürlüyü belə.

843
01:04:53,230 --> 01:04:55,630
[Tələbə, anlaşılmaz]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Mən onu Daş da bunu edirəm - və ya nə optimallaşdırılması səviyyəsi

845
01:05:00,310 --> 01:05:03,820
tanınmış bir quyruq recursion üçün tələb olunur.

846
01:05:03,820 --> 01:05:09,350
Mən bunu etiraf edirəm - GCC və cingilti

847
01:05:09,350 --> 01:05:12,610
həmçinin onların optimallaşdırılması səviyyəsi üçün müxtəlif mənaları var.

848
01:05:12,610 --> 01:05:17,870
Mən onu quyruq recursion tanımaq əmin üçün DashO 2, demək istəyirəm.

849
01:05:17,870 --> 01:05:27,880
Amma biz - Bir Fibonocci Məsələn filan kimi qurmaq bilər.

850
01:05:27,880 --> 01:05:30,030
O qurmaq çətindir, çünki bu test asan deyil

851
01:05:30,030 --> 01:05:32,600
belə böyük olduğunu bir ikili ağac.

852
01:05:32,600 --> 01:05:37,140
Lakin Bəli, mən bu DashO 2, hesab

853
01:05:37,140 --> 01:05:40,580
siz DashO 2 ilə tərtib, bu quyruq recursion üçün görünür

854
01:05:40,580 --> 01:05:54,030
və optimize ki.

855
01:05:54,030 --> 01:05:58,190
Nin geri edək - daxil sözün ehtiyacı son şey.

856
01:05:58,190 --> 01:06:04,900
Buraya daxil geri edək

857
01:06:04,900 --> 01:06:07,840
biz eyni fikri nə olacaq yerləşir.

858
01:06:07,840 --> 01:06:14,340
Bu hələ tamamilə idarə edə olan deyil flaw olacaq

859
01:06:14,340 --> 01:06:17,940
kök itself null, və ya son giriş, null zaman

860
01:06:17,940 --> 01:06:20,060
əvəzində bir valideyn göstərici ilə məşğul olan,

861
01:06:20,060 --> 01:06:27,430
nin göstəricilərinə əməl göstəricilərinə eyni məntiq tətbiq edək.

862
01:06:27,430 --> 01:06:35,580
Burada Əgər biz node ** hh saxlamaq

863
01:06:35,580 --> 01:06:37,860
və biz, sağ artıq takip ehtiyac yoxdur

864
01:06:37,860 --> 01:06:47,190
lakin node ** hh = & ağac.

865
01:06:47,190 --> 01:06:54,800
İndi bizim isə loop * hh bərabər null deyil isə olacaq.

866
01:06:54,800 --> 01:07:00,270
Artıq valideynlər izlemek üçün ehtiyac yoxdur.

867
01:07:00,270 --> 01:07:04,180
Sol və sağ izlemek ehtiyac yoxdur.

868
01:07:04,180 --> 01:07:10,190
Biz artıq temp istifadə etdiyiniz, çünki mən, bu temp zəng edəcəyik.

869
01:07:10,190 --> 01:07:17,200
Okay. Beləliklə, əgər (dəyər> * temp),

870
01:07:17,200 --> 01:07:24,010
sonra və (* temp) -> sağ

871
01:07:24,010 --> 01:07:29,250
başqa temp = & (* temp) -> ayrıldı.

872
01:07:29,250 --> 01:07:32,730
İndi, bu nöqtədə bu isə loop sonra,

873
01:07:32,730 --> 01:07:36,380
Bəlkə bu barədə iteratively recursively çox düşünmək daha asandır, çünki yalnız bunu

874
01:07:36,380 --> 01:07:39,010
lakin bu isə loop sonra,

875
01:07:39,010 --> 01:07:43,820
* Temp biz dəyişdirmək istədiyiniz göstəricisidir.

876
01:07:43,820 --> 01:07:48,960
>> Əvvəl, valideyn idi və biz valideyn sol və ya valideyn sağ ya dəyişdirmək istədi

877
01:07:48,960 --> 01:07:51,310
lakin biz valideyn doğru dəyişdirmək istəyirsinizsə,

878
01:07:51,310 --> 01:07:54,550
sonra * temp valideyn sağ və biz birbaşa dəyişdirə bilərsiniz.

879
01:07:54,550 --> 01:08:05,860
Belə ki, aşağı burada, biz * temp = newnode edə bilər ki, bu.

880
01:08:05,860 --> 01:08:09,540
Bildiriş Beləliklə, biz bu idi bütün kodu xətləri çıxarmaq idi.

881
01:08:09,540 --> 01:08:14,770
Əlavə səy edir ki, bütün əsas izlemek üçün.

882
01:08:14,770 --> 01:08:18,689
Burada biz yalnız göstərici üçün pointer takip əgər,

883
01:08:18,689 --> 01:08:22,990
və biz bütün bu qıvrım aşırma qurtarmaq istəyirdi, hətta,

884
01:08:22,990 --> 01:08:27,170
bu qısa baxmaq olun.

885
01:08:27,170 --> 01:08:32,529
Bu, indi eyni həll

886
01:08:32,529 --> 01:08:38,210
lakin kodu az xətləri.

887
01:08:38,210 --> 01:08:41,229
Sonra, bir etibarlı həlli kimi tanınması başlamaq

888
01:08:41,229 --> 01:08:43,529
o, tamam, həmçinin kimi çox haqqında səbəbdən daha asandır

889
01:08:43,529 --> 01:08:45,779
niyə mən int doğru bu bayrağı var?

890
01:08:45,779 --> 01:08:49,290
Ki, nə deməkdir? Oh, bu signifying ki,

891
01:08:49,290 --> 01:08:51,370
Mən getmək hər zaman, mən müəyyən etmək lazımdır

892
01:08:51,370 --> 01:08:53,819
Mən sol Əgər başqa mən sıfıra müəyyən etmək lazımdır.

893
01:08:53,819 --> 01:09:04,060
Burada bu barədə səbəbi yoxdur, bu barədə düşünmək yalnız daha asan var.

894
01:09:04,060 --> 01:09:06,710
Suallar?

895
01:09:06,710 --> 01:09:16,290
[Tələbə, anlaşılmaz] >> Bəli.

896
01:09:16,290 --> 01:09:23,359
OK, belə ki, son bit -

897
01:09:23,359 --> 01:09:28,080
Ki, biz nə edə bilər bir tez və asan funksiyası tapmaq

898
01:09:28,080 --> 01:09:34,910
let's - birlikdə hərhalda bir funksiyası olan cəhd və yazmaq

899
01:09:34,910 --> 01:09:38,899
bir ikili axtarış ağac olub ki, qayğı deyil.

900
01:09:38,899 --> 01:09:43,770
Bu funksiya doğru qayıtmalıdırlar şey

901
01:09:43,770 --> 01:09:58,330
əgər hər hansı bu ümumi ikili ağac biz aradığınız dəyəri.

902
01:09:58,330 --> 01:10:02,520
Beləliklə, biz iteratively bunu edəcəyik sonra ilk recursively bunu bildirin və.

903
01:10:02,520 --> 01:10:07,300
Bu, həqiqətən qısa olacaq, çünki həqiqətən yalnız, o, birlikdə edə bilərsiniz.

904
01:10:07,300 --> 01:10:11,510
>> Mənim baza halda nə olacaq?

905
01:10:11,510 --> 01:10:13,890
[Tələbə, anlaşılmaz]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Beləliklə, əgər (ağac == NULL), sonra nə?

907
01:10:18,230 --> 01:10:22,740
[Tələbə] yalan qayıt.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, yaxşı, mən başqa ehtiyac yoxdur.

909
01:10:26,160 --> 01:10:30,250
Əgər mənim digər əsas işi idi.

910
01:10:30,250 --> 01:10:32,450
[Tələbə] Tree dəyəri? >> Bəli.

911
01:10:32,450 --> 01:10:36,430
Belə ki, (ağac-> dəyəri == dəyər əgər.

912
01:10:36,430 --> 01:10:39,920
Biz node ** s, node * geri deyilik edək?

913
01:10:39,920 --> 01:10:42,990
Şey, bir node ** istifadə etmək lazımdır heç vaxt

914
01:10:42,990 --> 01:10:45,480
biz göstəricilərinə değiştirmeyle deyil çünki.

915
01:10:45,480 --> 01:10:50,540
Biz yalnız onlara traversing edirik.

916
01:10:50,540 --> 01:10:53,830
Ki, olur, onda biz doğru qayıtmaq istəyirəm.

917
01:10:53,830 --> 01:10:58,270
Else biz uşaqlar axır istəyirəm.

918
01:10:58,270 --> 01:11:02,620
Beləliklə, biz sola hər şey azdır olub Səbəb bilməz

919
01:11:02,620 --> 01:11:05,390
və sağ hər şeyi böyükdür.

920
01:11:05,390 --> 01:11:09,590
Belə ki, nə bizim şəraiti burada olacaq - və ya, biz nə edəcəyik?

921
01:11:09,590 --> 01:11:11,840
[Tələbə, anlaşılmaz] >> Bəli.

922
01:11:11,840 --> 01:11:17,400
Arxiv şey (dəyər, ağac-> sol)

923
01:11:17,400 --> 01:11:26,860
və ya (dəyər, ağac-> sağ) ehtiva edir. Və bu.

924
01:11:26,860 --> 01:11:29,080
Və bəzi qısa qapanmasına qiymətləndirilməsi var bildiriş

925
01:11:29,080 --> 01:11:32,520
biz sol ağac dəyəri tapmaq üçün baş Əgər,

926
01:11:32,520 --> 01:11:36,820
doğru ağac baxmaq lazımdır heç vaxt.

927
01:11:36,820 --> 01:11:40,430
Bütün funksiyası var.

928
01:11:40,430 --> 01:11:43,690
İndi iteratively bunu edək

929
01:11:43,690 --> 01:11:48,060
az gözəl gedir.

930
01:11:48,060 --> 01:11:54,750
Biz node * hh = ağac adi start olacaq.

931
01:11:54,750 --> 01:12:03,250
Halda (hh! = NULL).

932
01:12:03,250 --> 01:12:08,600
Tez bir problem görəcəksiniz.

933
01:12:08,600 --> 01:12:12,250
Əgər hh - buradan, biz heç bu çıxmaq əgər,

934
01:12:12,250 --> 01:12:16,020
sonra baxmaq üçün şeyi tökülmək etdik, belə ki, saxta qayıtmaq.

935
01:12:16,020 --> 01:12:24,810
(Hh-> dəyəri == dəyəri), doğru geri edin.

936
01:12:24,810 --> 01:12:32,910
Beləliklə, biz bir yer var -

937
01:12:32,910 --> 01:12:36,250
biz sol və ya sağ getmək istəyirəm bilmirəm.

938
01:12:36,250 --> 01:12:44,590
Belə ki, özbaşına isə yalnız sol gedək.

939
01:12:44,590 --> 01:12:47,910
Mən açıq-aşkar mən tamamilə hər şeyi tərk etdik bir məsələ daxil etdik -

940
01:12:47,910 --> 01:12:50,760
Mən yalnız heç bir ağac sol yoxlayacaq.

941
01:12:50,760 --> 01:12:56,050
Mən heç bir hüququ uşaq bir şey yoxlamaq heç vaxt.

942
01:12:56,050 --> 01:13:00,910
Bunu nasıl düzeltirim?

943
01:13:00,910 --> 01:13:05,260
[Tələbə] Siz yığını ilə sol və sağ takip var.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Bəli. Belə ki, bu imkan

945
01:13:13,710 --> 01:13:32,360
struct siyahısı node * n, sonra node ** Növbəti?

946
01:13:32,360 --> 01:13:40,240
Mən gözəl işlər olduğunu düşünürəm.

947
01:13:40,240 --> 01:13:45,940
Qədər burada - Biz sol, və ya let's artıq getmək istəyirəm.

948
01:13:45,940 --> 01:13:54,350
Struct list list =, bu başlamaq lazımdır

949
01:13:54,350 --> 01:13:58,170
bu struct siyahısına həyata.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Belə ki, bizim bağlı siyahısı olacaq

951
01:14:04,040 --> 01:14:08,430
biz artıq atlandı ki subtrees edir.

952
01:14:08,430 --> 01:14:13,800
Biz indi tərk axır gedir

953
01:14:13,800 --> 01:14:17,870
lakin biz qaçılmaz doğru geri gəlmək lazımdır bəri,

954
01:14:17,870 --> 01:14:26,140
Biz struct siyahısı içərisində sağ saxlamaq olacaq.

955
01:14:26,140 --> 01:14:32,620
Sonra biz new_list və ya struct lazımdır

956
01:14:32,620 --> 01:14:41,080
struct list *, new_list = malloc (sizeof (siyahısı)).

957
01:14:41,080 --> 01:14:44,920
Hesab edirəm ki, səhv yoxlanılması ignore gedirəm, amma əgər bu null kontrol etməlidir.

958
01:14:44,920 --> 01:14:50,540
O qeyd olacaq node New_list -

959
01:14:50,540 --> 01:14:56,890
Mən burada bu qədər istəyirdi nə oh ki, var. Bu ikinci struct siyahısına qeyd edəcək.

960
01:14:56,890 --> 01:15:02,380
Bu siyahıları work bağlı yalnız nasıl.

961
01:15:02,380 --> 01:15:04,810
Bu int bağlı siyahısı eyni

962
01:15:04,810 --> 01:15:06,960
istisna olmaqla, biz yalnız node * ilə int əvəz edirik.

963
01:15:06,960 --> 01:15:11,040
Bu tam eyni deyil.

964
01:15:11,040 --> 01:15:15,100
Belə new_list, bizim new_list node dəyəri

965
01:15:15,100 --> 01:15:19,120
hh> hüququ olacaq.

966
01:15:19,120 --> 01:15:24,280
Bizim dəyəri new_list-> sonrakı orijinal siyahısı gedir

967
01:15:24,280 --> 01:15:30,760
və sonra new_list qeyd etmək siyahısını yeniləmək üçün olacaq.

968
01:15:30,760 --> 01:15:33,650
>> İndi çəkərək şeyi yol bir növ lazımdır

969
01:15:33,650 --> 01:15:37,020
biz bütün sol subtree keçdiyi var kimi.

970
01:15:37,020 --> 01:15:40,480
İndi biz bu məhsulları çıxarmaq lazımdır

971
01:15:40,480 --> 01:15:43,850
kimi hh null deyil, biz yalnız yalan qayıtmaq istəmirəm.

972
01:15:43,850 --> 01:15:50,370
Biz indi yeni siyahısını xaricində çəkmək istəyirəm.

973
01:15:50,370 --> 01:15:53,690
Bunu bir rahat - də, faktiki olaraq, bunu çox yolları var.

974
01:15:53,690 --> 01:15:56,680
Hər kəs bir təklif var?

975
01:15:56,680 --> 01:15:58,790
Harada bu və ya necə bunu etməlidir etməliyəm?

976
01:15:58,790 --> 01:16:08,010
Biz yalnız bir neçə dəqiqə, lakin heç bir təklif?

977
01:16:08,010 --> 01:16:14,750
Əvəzinə - bir yol əvəzinə bizim vəziyyətinin isə olmaqla,

978
01:16:14,750 --> 01:16:17,090
nə biz hazırda da arıyorsanız, null deyil

979
01:16:17,090 --> 01:16:22,340
əvəzinə biz sadalanması onu null qədər getmək davam edirik.

980
01:16:22,340 --> 01:16:25,680
Bizim siyahısı, null olan qədər başa əgər

981
01:16:25,680 --> 01:16:30,680
sonra, axtarmaq üzərində axtarış şeyi tökülmək var.

982
01:16:30,680 --> 01:16:39,860
Amma bizim siyahıda ilk şey yalnız ilk node olacaq deməkdir.

983
01:16:39,860 --> 01:16:49,730
Ilk şey olacaq - biz artıq görmək lazımdır.

984
01:16:49,730 --> 01:16:58,710
Belə siyahısı> n bizim ağac olacaq.

985
01:16:58,710 --> 01:17:02,860
list-> gələn null olacaq.

986
01:17:02,860 --> 01:17:07,580
İndi list bərabər null deyil isə.

987
01:17:07,580 --> 01:17:11,610
Cur bizim siyahıdan bir şey çəkmək niyyətindədir.

988
01:17:11,610 --> 01:17:13,500
Belə hh bərabər siyahısı> n gedir.

989
01:17:13,500 --> 01:17:20,850
Və sonra list bərabər siyahısı> n gedən, və ya siyahısı> sonrakı olunur.

990
01:17:20,850 --> 01:17:23,480
Belə ki, əgər hh dəyər dəyər bərabərdir.

991
01:17:23,480 --> 01:17:28,790
İndi bizim sağ göstərici və sol pointer də əlavə edə bilərsiniz

992
01:17:28,790 --> 01:17:32,900
kimi uzun onlar null deyilik kimi.

993
01:17:32,900 --> 01:17:36,390
Burada Down, biz etmişik lazım tapmaq ilk növbədə.

994
01:17:36,390 --> 01:17:44,080
Əgər (hh> doğru! = NULL)

995
01:17:44,080 --> 01:17:56,380
sonra biz siyahısına daxil olan node daxil edir.

996
01:17:56,380 --> 01:17:59,290
Əgər (hh> sol), bu əlavə iş bir az, ancaq gözəl var.

997
01:17:59,290 --> 01:18:02,690
Əgər (hh> sol! = NULL)

998
01:18:02,690 --> 01:18:14,310
və biz bağlıdır siyahısına sol daxil olacaq

999
01:18:14,310 --> 01:18:19,700
və bu olmalıdır.

1000
01:18:19,700 --> 01:18:22,670
Biz təkrarlamaq - kimi uzun biz siyahısına bir şey var,

1001
01:18:22,670 --> 01:18:26,640
biz baxmaq üçün başqa bir node var.

1002
01:18:26,640 --> 01:18:28,920
Beləliklə, biz ki, node baxmaq

1003
01:18:28,920 --> 01:18:31,390
biz növbəti bir siyahısını inkişaf.

1004
01:18:31,390 --> 01:18:34,060
Ki node biz aradığınız dəyəri, biz doğru ola bilər.

1005
01:18:34,060 --> 01:18:37,640
Else, həm də bizim sol və sağ subtrees daxil

1006
01:18:37,640 --> 01:18:40,510
onlar null deyilik kimi uzun kimi, bizim siyahısına daxil

1007
01:18:40,510 --> 01:18:43,120
biz istər-istəməz onlara getmək üçün.

1008
01:18:43,120 --> 01:18:45,160
Onlar null deyil, əgər

1009
01:18:45,160 --> 01:18:47,950
bizim kök göstərici iki şeyi qeyd, əgər

1010
01:18:47,950 --> 01:18:51,670
listemize null olan qədər başa belə sonra ilk biz bir şey çıxardı.

1011
01:18:51,670 --> 01:18:56,890
Və sonra biz geri iki şey qoymaq, indi listemize ölçüsü 2 edir.

1012
01:18:56,890 --> 01:19:00,030
, Sonra biz geri loop olacaq və biz yalnız çəkmək olacaq

1013
01:19:00,030 --> 01:19:04,250
nin, bizim kök node sol göstərici deyək.

1014
01:19:04,250 --> 01:19:07,730
Və yalnız baş saxlamaq lazımdır, biz hər şeyə loop çıxacağıq.

1015
01:19:07,730 --> 01:19:11,280
>> Bu daha çox mürəkkəb idi edək ki,

1016
01:19:11,280 --> 01:19:14,160
bu recursive həlli.

1017
01:19:14,160 --> 01:19:17,260
Mən neçə dəfə bildirib etdik

1018
01:19:17,260 --> 01:19:25,120
bu recursive həll adətən həlli iterativ ortaq çox var.

1019
01:19:25,120 --> 01:19:30,820
Burada bu recursive həll edir məhz budur.

1020
01:19:30,820 --> 01:19:36,740
Yalnız dəyişiklik yerine dolayısı yığını istifadə, proqram yığını deyil

1021
01:19:36,740 --> 01:19:40,840
Siz hələ müraciət etmək lazım qovşaqlarının track saxlanılması üçün yol kimi,

1022
01:19:40,840 --> 01:19:45,430
İndi aydın şəkildə bağlı siyahısını istifadə etmək lazımdır.

1023
01:19:45,430 --> 01:19:49,070
Nə node hələ ziyarət lazımdır və hər iki halda siz track saxlanılır.

1024
01:19:49,070 --> 01:19:51,790
Bu recursive halda yalnız daha asan var çünki bir yığın

1025
01:19:51,790 --> 01:19:57,100
proqram yığını kimi həyata keçirilir.

1026
01:19:57,100 --> 01:19:59,550
Bu bağlı siyahısı, bir yığın edək ki.

1027
01:19:59,550 --> 01:20:01,580
Biz yalnız yığını qoymaq olursa olsun

1028
01:20:01,580 --> 01:20:09,960
biz növbəti səfər yığını qoparmaq olacaq nə dərhal edir.

1029
01:20:09,960 --> 01:20:14,380
Biz hər hansı bir sualınız vaxt həyata istəyirik, ancaq?

1030
01:20:14,380 --> 01:20:23,530
[Tələbə, anlaşılmaz]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Bəli. Biz bağlı siyahısı var əgər,

1032
01:20:27,790 --> 01:20:30,150
cari, bu oğlan qeyd edir

1033
01:20:30,150 --> 01:20:34,690
və indi yalnız bu oğlan diqqət bizim bağlı list inkişaf edirik.

1034
01:20:34,690 --> 01:20:44,200
Biz istiqamətində bağlı list üzərində traversing edirik.

1035
01:20:44,200 --> 01:20:51,200
Və sonra biz əlaqəli siyahısı və stuff azad etməlidir tapmaq

1036
01:20:51,200 --> 01:20:53,880
bir doğru və ya yalan qaytarılması əvvəl biz ehtiyac

1037
01:20:53,880 --> 01:20:57,360
bizim bağlı list üzərində təkrarlamaq və həmişə aşağı burada, mən tapmaq

1038
01:20:57,360 --> 01:21:03,900
biz hh sağ bərabər olmadıqda, belə ki, indi biz azad etmək istəyirik, əlavə

1039
01:21:03,900 --> 01:21:09,600
hh çünki, yaxşı, biz tamamilə siyahısı unuda idi? Bəli.

1040
01:21:09,600 --> 01:21:12,880
Belə ki, biz burada etmək istəyirəm nə.

1041
01:21:12,880 --> 01:21:16,730
İmleci harada?

1042
01:21:16,730 --> 01:21:23,320
Cur idi - biz struct siyahısına * 10 növbəti liste bərabərdir istəyirəm.

1043
01:21:23,320 --> 01:21:29,240
Pulsuz siyahısı list = temp.

1044
01:21:29,240 --> 01:21:32,820
Və halda biz doğru qayıtmaq, burada biz təkrarlamaq lazımdır

1045
01:21:32,820 --> 01:21:37,050
şeyi azad bizim bağlı siyahı qalan artıq.

1046
01:21:37,050 --> 01:21:39,700
Bu recursive həlli haqqında gözəl şey şey azad edilir

1047
01:21:39,700 --> 01:21:44,930
yalnız sizin üçün nə edəcək yığını off yaratma factorings deməkdir.

1048
01:21:44,930 --> 01:21:50,720
Belə ki, hard-to-beyin haqqında kodu 3 xətt kimi bir şey olan getdi sonra

1049
01:21:50,720 --> 01:21:57,520
əhəmiyyətli dərəcədə daha çox bir şey çətin-to-hesab-haqqında kodu satır.

1050
01:21:57,520 --> 01:22:00,620
Hər hansı bir daha suallar?

1051
01:22:00,620 --> 01:22:08,760
Bütün hüquqlar. Biz yaxşı edirik. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]