1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Дел 7: поудобно]

2
00:00:02,770 --> 00:00:05,090
[Роб Бауден] [Универзитетот Харвард]

3
00:00:05,090 --> 00:00:07,930
[Ова е CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Во ред. Значи како што реков во мојот мејл,

5
00:00:10,110 --> 00:00:14,060
ова ќе биде бинарни дрво-интензивна секција.

6
00:00:14,060 --> 00:00:16,820
Но таму не се толку многу прашања.

7
00:00:16,820 --> 00:00:18,920
Така ние ќе да се обиде да извлече секое прашање

8
00:00:18,920 --> 00:00:25,430
и да си одат на болни детали на сите од најдобрите начини на вршење на работите.

9
00:00:25,430 --> 00:00:31,200
Значи правото на почетокот, ние одиме преку примерок цртежи на бинарни дрва и работи.

10
00:00:31,200 --> 00:00:35,970
Значи тука "Запомнете дека бинарно дрво има јазли слични на оние на поврзани листа,

11
00:00:35,970 --> 00:00:38,150
освен наместо на еден покажувач постојат две: една за 'дете' на левата

12
00:00:38,150 --> 00:00:41,950
и друга за десниот 'дете' ".

13
00:00:41,950 --> 00:00:45,630
Па бинарно дрво е исто како поврзаните листа,

14
00:00:45,630 --> 00:00:47,910
освен struct се случува да имаат два покажувачи.

15
00:00:47,910 --> 00:00:51,390
Има трикомпонентните дрвја, кои ќе имаат три совети,

16
00:00:51,390 --> 00:00:56,540
постојат n-арен дрвја, кои само имаат генерички покажувачот

17
00:00:56,540 --> 00:01:00,320
што потоа треба да Примерок да биде доволно голем да имаат

18
00:01:00,320 --> 00:01:04,840
доволно совети за сите можни деца.

19
00:01:04,840 --> 00:01:08,200
Значи бинарно дрво само се случува да имаат константен број на две.

20
00:01:08,200 --> 00:01:11,260
Ако сакате, можете да даде поврзана листа како унарни дрво,

21
00:01:11,260 --> 00:01:15,360
но јас не верувам дека некој го нарекува тоа.

22
00:01:15,360 --> 00:01:18,060
"Нацртајте кутии-и-стрелките дијаграм на бинарно дрво јазол

23
00:01:18,060 --> 00:01:24,110
содржат омилен број на Nate, 7, каде што секое дете покажувачот е нула. "

24
00:01:24,110 --> 00:01:27,780
Значи iPad режим.

25
00:01:27,780 --> 00:01:30,280
>> Тоа ќе биде прилично јасна.

26
00:01:30,280 --> 00:01:36,150
Ние сме само ќе треба еден јазол, јас ќе го нацрта тоа како плоштад.

27
00:01:36,150 --> 00:01:38,730
И јас ќе подготви вредностите тука.

28
00:01:38,730 --> 00:01:41,090
Па вредност ќе одат во тука,

29
00:01:41,090 --> 00:01:44,770
а потоа надолу тука ќе имаме лево покажувачот на левата и десната покажувачот на правото.

30
00:01:44,770 --> 00:01:50,430
И тоа е многу, па конвенција да го наречеме лево и десно, на покажувачот имиња.

31
00:01:50,430 --> 00:01:52,460
И двете од овие се случува да биде нула.

32
00:01:52,460 --> 00:01:57,870
Тоа само ќе биде нула, и дека само ќе биде нула.

33
00:01:57,870 --> 00:02:03,630
Во ред. Па назад до тука.

34
00:02:03,630 --> 00:02:05,700
"Со поврзана листа, имавме само за чување покажувач

35
00:02:05,700 --> 00:02:09,639
на првиот јазол во листата со цел да се потсетиме на целиот поврзани листа, или целата листа.

36
00:02:09,639 --> 00:02:11,650
Исто така, со дрвја, ние само треба да се складира покажувачот

37
00:02:11,650 --> 00:02:13,420
на еден јазол, со цел да се потсетиме на целото дрво.

38
00:02:13,420 --> 00:02:15,980
Овој јазол е calle на "root" на дрвото.

39
00:02:15,980 --> 00:02:18,320
Изгради врз вашата дијаграм од пред или нацрта нова

40
00:02:18,320 --> 00:02:21,690
како што имате кутии-и-стрели опис на бинарно дрво

41
00:02:21,690 --> 00:02:25,730
со вредноста 7, тогаш 3 во лево,

42
00:02:25,730 --> 00:02:32,760
од 9 на десната страна, а потоа 6 на правото на 3. "

43
00:02:32,760 --> 00:02:34,810
Ајде да видиме дали можам да се сетам на сите дека во мојата глава.

44
00:02:34,810 --> 00:02:37,670
Значи ова ќе биде нашиот корен се тука.

45
00:02:37,670 --> 00:02:41,600
Ќе имаме некои покажувачот некаде, нешто што ќе го наречеме корен,

46
00:02:41,600 --> 00:02:45,140
и тоа укажува на овој човек.

47
00:02:45,140 --> 00:02:48,490
Сега да се направи нов јазол,

48
00:02:48,490 --> 00:02:52,870
она што го имаме, 3 на левата?

49
00:02:52,870 --> 00:02:57,140
Значи нов јазол со 3, и првично укажува нула.

50
00:02:57,140 --> 00:02:59,190
Јас само ќе се стави Н

51
00:02:59,190 --> 00:03:02,250
Сега ние сакаме да се направи кои одат лево од 7.

52
00:03:02,250 --> 00:03:06,840
Значи ние се промени овој покажувач до сега укажуваат на овој човек.

53
00:03:06,840 --> 00:03:12,420
И тоа го правиме истото. Сакаме 9 овде

54
00:03:12,420 --> 00:03:14,620
кој првично само вели нула.

55
00:03:14,620 --> 00:03:19,600
Ние ќе се промени овој покажувач, точка 9,

56
00:03:19,600 --> 00:03:23,310
и сега сакаме да се стави 6 до правото на 3.

57
00:03:23,310 --> 00:03:32,170
Па затоа се случува да - направи 6.

58
00:03:32,170 --> 00:03:34,310
И тоа човек ќе точка таму.

59
00:03:34,310 --> 00:03:38,320
Во ред. Значи тоа е се што бара од нас да се направи.

60
00:03:38,320 --> 00:03:42,770
>> Сега ајде да одиме над некои терминологија.

61
00:03:42,770 --> 00:03:46,690
Ние веќе разговаравме за тоа како коренот на дрвото е топ-повеќето јазол во стеблото.

62
00:03:46,690 --> 00:03:54,720
Оној кој содржи 7. Јазли на дното на дрвото се нарекуваат лисја.

63
00:03:54,720 --> 00:04:01,240
Било кој јазол кој само има нула како негови деца е лист.

64
00:04:01,240 --> 00:04:03,680
Па можно е, ако нашиот бинарно дрво е само еден јазол,

65
00:04:03,680 --> 00:04:10,130
дека дрвото е лист, и тоа е тоа.

66
00:04:10,130 --> 00:04:12,060
"На 'висина" на дрво е бројот на хмел треба да се направи

67
00:04:12,060 --> 00:04:16,620
да се добие од врвот на листот. "

68
00:04:16,620 --> 00:04:18,640
Ние ќе се влезе, во вториот, разликата

69
00:04:18,640 --> 00:04:21,940
помеѓу избалансиран и неизбалансирани бинарни дрва,

70
00:04:21,940 --> 00:04:29,470
но сега за сега, вкупната висина на ова дрво

71
00:04:29,470 --> 00:04:34,520
Јас би рекол е 3, иако, ако се брои бројот на хмел

72
00:04:34,520 --> 00:04:39,710
што треба да се направи со цел да се дојде до 9, тогаш тоа е навистина само височина од 2.

73
00:04:39,710 --> 00:04:43,340
Токму сега тоа е неурамнотежен бинарно дрво,

74
00:04:43,340 --> 00:04:49,840
но ние ќе зборуваме за рамномерен кога станува да бидат релевантни.

75
00:04:49,840 --> 00:04:52,040
Па сега можеме да зборуваме за јазли во дрво, во смисла

76
00:04:52,040 --> 00:04:54,700
во однос на други јазли во дрво.

77
00:04:54,700 --> 00:04:59,730
Така, сега имаме родители, деца, браќа и сестри, татковци, и потомци.

78
00:04:59,730 --> 00:05:05,650
Тие се прилично здрав разум, што тие значат.

79
00:05:05,650 --> 00:05:09,610
Ако ве прашаме - тоа е родители.

80
00:05:09,610 --> 00:05:12,830
Значи она што е родител на 3?

81
00:05:12,830 --> 00:05:16,090
[Студентите] 7. >> Да. Родителот е само ќе биде она што укажува на вас.

82
00:05:16,090 --> 00:05:20,510
Тогаш што се децата од 7?

83
00:05:20,510 --> 00:05:23,860
[Студентите] 3 и 9. >> Да.

84
00:05:23,860 --> 00:05:26,460
Забележете дека "децата" буквално значи децата,

85
00:05:26,460 --> 00:05:31,010
па 6 не ќе се применуваат, бидејќи тоа е како внуците.

86
00:05:31,010 --> 00:05:35,540
Но, тогаш ако одиме потомци, така што се потомци на 7?

87
00:05:35,540 --> 00:05:37,500
[Студентите] 3, 6 и 9. >> Да.

88
00:05:37,500 --> 00:05:42,330
Потомци на root јазол ќе биде сè во дрво,

89
00:05:42,330 --> 00:05:47,950
освен можеби на root јазол себе, ако не сакате да се разгледа што потомок.

90
00:05:47,950 --> 00:05:50,750
И, конечно, предци, па тоа е спротивна насока.

91
00:05:50,750 --> 00:05:55,740
Значи она што се предците на 6?

92
00:05:55,740 --> 00:05:58,920
[Студентите] 3 и 7. >> Да. 9 не е вклучен.

93
00:05:58,920 --> 00:06:02,520
Тоа е само директен лоза назад кон коренот

94
00:06:02,520 --> 00:06:13,230
ќе биде вашиот предци.

95
00:06:13,230 --> 00:06:16,300
>> "Велиме дека бинарно дрво е" нареди "ако за секој јазол во стеблото,

96
00:06:16,300 --> 00:06:19,530
сите негови потомци на левата имаат помала вредност

97
00:06:19,530 --> 00:06:22,890
и сите оние на десната имаат поголема вредност.

98
00:06:22,890 --> 00:06:27,060
На пример, дрвото погоре е наредено, но тоа не е единствениот можен нареди аранжман. "

99
00:06:27,060 --> 00:06:30,180
Пред да дојдеме до тоа,

100
00:06:30,180 --> 00:06:36,420
нареди бинарно дрво е исто така познат како бинарен за пребарување дрво.

101
00:06:36,420 --> 00:06:38,660
Еве ние се случи да биде нарекувајќи нареди бинарно дрво,

102
00:06:38,660 --> 00:06:41,850
но јас никогаш не слушнале тоа се нарекува нареди бинарно дрво пред,

103
00:06:41,850 --> 00:06:46,650
и на квиз, се многу поголеми шанси да се стави бинарни пребарување дрво.

104
00:06:46,650 --> 00:06:49,250
Тие се едно и исто,

105
00:06:49,250 --> 00:06:54,580
а тоа е важно да се признае разликата помеѓу бинарно дрво и бинарни пребарување дрво.

106
00:06:54,580 --> 00:06:58,830
А бинарно дрво е само едно дрво, што укажува на две работи.

107
00:06:58,830 --> 00:07:02,120
Секој јазол укажува на две работи.

108
00:07:02,120 --> 00:07:06,310
Нема размислување за вредностите што укажува.

109
00:07:06,310 --> 00:07:11,370
Значи се допаѓа овде, бидејќи тоа е бинарна пребарување дрво,

110
00:07:11,370 --> 00:07:14,030
ние знаеме дека ако ние одиме лево од 7,

111
00:07:14,030 --> 00:07:16,670
тогаш сите вредности што ние можеби може да достигне

112
00:07:16,670 --> 00:07:19,310
со одење лево од 7 треба да биде помал од 7.

113
00:07:19,310 --> 00:07:24,070
Забележете дека сите вредности помалку од 7 се 3 и 6.

114
00:07:24,070 --> 00:07:26,040
Тоа се сите лево од 7.

115
00:07:26,040 --> 00:07:29,020
Ако одиме на правото на 7, што треба да биде поголема од 7,

116
00:07:29,020 --> 00:07:33,220
па 9 е на правото на 7, па ние сме добри.

117
00:07:33,220 --> 00:07:36,150
Ова не е случај за бинарно дрво,

118
00:07:36,150 --> 00:07:40,020
за редовно бинарно дрво ние само може да имаат 3 на врвот, 7 лево,

119
00:07:40,020 --> 00:07:47,630
9 лево од 7; нема нарачување на вредности она.

120
00:07:47,630 --> 00:07:56,140
Сега, ние всушност не ќе го направат тоа затоа што тоа е мачна и непотребни,

121
00:07:56,140 --> 00:07:59,400
но "се обиде да привлече што поголем број нареди дрвја како што може да мислам на

122
00:07:59,400 --> 00:08:01,900
користење на броевите 7, 3, 9 и 6.

123
00:08:01,900 --> 00:08:06,800
Колку различни аранжмани постојат? Што е висината на секој од нив? "

124
00:08:06,800 --> 00:08:10,480
>> Ние ќе направиме неколку, но главната идеја е,

125
00:08:10,480 --> 00:08:16,530
ова е во никој случај не единствена претстава на бинарно дрво содржат овие вредности.

126
00:08:16,530 --> 00:08:22,760
Сите ние треба е некои бинарно дрво што содржи 7, 3, 6 и 9.

127
00:08:22,760 --> 00:08:25,960
Друга можна валидна ќе биде коренот е 3,

128
00:08:25,960 --> 00:08:30,260
оди на лево и тоа е 6, оди на лево и тоа е 7,

129
00:08:30,260 --> 00:08:32,730
оди на лево и тоа е 9.

130
00:08:32,730 --> 00:08:36,169
Тоа е совршено валидна бинарни пребарување дрво.

131
00:08:36,169 --> 00:08:39,570
Тоа не е многу корисна, бидејќи тоа е само како поврзани листа

132
00:08:39,570 --> 00:08:43,750
и сите на овие совети се само нула.

133
00:08:43,750 --> 00:08:48,900
Но, тоа е валидна дрво. Да?

134
00:08:48,900 --> 00:08:51,310
[Студентски] Не вредностите треба да биде поголема од десната?

135
00:08:51,310 --> 00:08:56,700
Или ова - >> Овие мислев да одам на друг начин.

136
00:08:56,700 --> 00:09:00,960
Постои, исто така - да, ајде да се префрлат тоа.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Добар улов.

138
00:09:07,770 --> 00:09:11,730
Таа се уште има да ги почитуваат она што бинарно дрво пребарување треба да прави.

139
00:09:11,730 --> 00:09:15,650
Па сè до левата треба да биде помал од која било дадена јазол.

140
00:09:15,650 --> 00:09:23,180
Ние може само да се движат, да речеме, оваа 6 и го ставив тука.

141
00:09:23,180 --> 00:09:26,880
Не, не можеме. Зошто го правите тоа?

142
00:09:26,880 --> 00:09:35,350
Да се ​​направи - тука е 6, тука е 7, 6 поени 3.

143
00:09:35,350 --> 00:09:39,290
Ова е сеуште валидна бинарни пребарување дрво.

144
00:09:39,290 --> 00:09:49,260
Што не е во ред ако јас - да видиме дали можам да излезе со аранжман.

145
00:09:49,260 --> 00:09:52,280
Да, во ред. Значи она што е во ред со оваа дрво?

146
00:09:52,280 --> 00:10:08,920
Претпоставувам дека веќе ви даде знак дека нешто не е во ред со него.

147
00:10:08,920 --> 00:10:14,430
Зошто го правите тоа?

148
00:10:14,430 --> 00:10:18,510
Во ред. Ова изгледа разумно.

149
00:10:18,510 --> 00:10:22,590
Ако ги погледнеме во секој јазол, како 7, а потоа на лево од 7 е 3.

150
00:10:22,590 --> 00:10:24,960
Значи имаме 3, нешто на правото на 3 е 6.

151
00:10:24,960 --> 00:10:27,750
И ако се погледне на 6, нешто на правото на 6 е 9.

152
00:10:27,750 --> 00:10:30,910
Значи, зошто е ова не е валидна бинарни пребарување дрво?

153
00:10:30,910 --> 00:10:36,330
[Студентите] 9 се уште е лево од 7. >> Да.

154
00:10:36,330 --> 00:10:43,710
Тоа мора да биде вистина дека сите вредности што веројатно може да се постигне со одење лево од 7 помалку од 7.

155
00:10:43,710 --> 00:10:49,120
Ако одиме лево од 7, ние дојдеме до 3, а ние се уште може да стигне до 6,

156
00:10:49,120 --> 00:10:52,520
ние се уште може да стигне до 9, но со тоа што помина помалку од 7,

157
00:10:52,520 --> 00:10:55,070
ние не треба да бидат способни да се стигне до бројот што е поголема од 7.

158
00:10:55,070 --> 00:10:59,830
Значи ова не е валиден бинарни пребарување дрво.

159
00:10:59,830 --> 00:11:02,330
>> Брат ми всушност имаше интервју прашање

160
00:11:02,330 --> 00:11:07,760
тоа беше во основа, само кодот од нешто да се провери

161
00:11:07,760 --> 00:11:10,500
дали дрво е бинарно пребарување дрво,

162
00:11:10,500 --> 00:11:13,580
и така првото нешто што го направив беше само да провериш

163
00:11:13,580 --> 00:11:17,020
ако лево и десно се точни, а потоа iterate таму долу.

164
00:11:17,020 --> 00:11:19,700
Но, не само да го направите тоа, вие мора да ги пратите

165
00:11:19,700 --> 00:11:22,550
на фактот дека сега дека сум отишол лево од 7,

166
00:11:22,550 --> 00:11:26,340
сè во овој поддрво смее да биде помал од 7.

167
00:11:26,340 --> 00:11:28,430
Точниот алгоритам треба да ги пратите

168
00:11:28,430 --> 00:11:35,970
на границите дека вредностите веројатно може да падне внатре

169
00:11:35,970 --> 00:11:38,360
Ние не ќе оди преку сите нив.

170
00:11:38,360 --> 00:11:41,630
Има убава повторување однос,

171
00:11:41,630 --> 00:11:44,810
иако не сме добиле оние, или ние нема да добие на оние,

172
00:11:44,810 --> 00:11:47,030
дефинирање колку таму всушност се.

173
00:11:47,030 --> 00:11:53,180
Па така постојат 14 од нив.

174
00:11:53,180 --> 00:11:56,020
Идејата за тоа како ќе го направи тоа математички е како,

175
00:11:56,020 --> 00:11:59,770
можете да изберете било само еден да биде коренот јазол,

176
00:11:59,770 --> 00:12:03,160
а потоа, ако јас земам 7 да биде root јазол,

177
00:12:03,160 --> 00:12:08,150
тогаш постојат, да речеме, некои бројки кои можат да одат биде мојата лева јазол,

178
00:12:08,150 --> 00:12:10,440
и има некои бројки кои можат да бидат моето право јазол,

179
00:12:10,440 --> 00:12:15,090
но ако имам n вкупниот број, тогаш износот што може да оди на лево

180
00:12:15,090 --> 00:12:18,820
плус износот што може да оди на правото е n - 1.

181
00:12:18,820 --> 00:12:26,130
Па на останатите броеви, тие треба да бидат во можност да одат или на лево или на десно.

182
00:12:26,130 --> 00:12:31,580
Се чини тешко, ако го ставам 3 првиот потоа се мора да оди на лево,

183
00:12:31,580 --> 00:12:35,080
но ако го ставам 7, а потоа некои работи може да тргне на лево и некои работи може да тргне кон десно.

184
00:12:35,080 --> 00:12:39,570
И со '3 прв "мислев што може да оди на десно.

185
00:12:39,570 --> 00:12:42,350
Тоа е навистина, само треба да се размислува за тоа како,

186
00:12:42,350 --> 00:12:47,980
колку работите можат да одат на следното ниво на дрвото.

187
00:12:47,980 --> 00:12:50,420
И излегува да биде 14 или може да се подготви сите од нив,

188
00:12:50,420 --> 00:12:54,650
а потоа ќе добиете 14.

189
00:12:54,650 --> 00:13:01,120
>> Кога ќе се вратам овде,

190
00:13:01,120 --> 00:13:03,510
"Нареди бинарни дрва се излади, бидејќи може да се бара преку нив

191
00:13:03,510 --> 00:13:06,910
во многу сличен начин да се бараат преку подредени низа.

192
00:13:06,910 --> 00:13:10,120
Да го стори тоа, ние започнуваме во коренот и работа на патот надолу на дрвото

193
00:13:10,120 --> 00:13:13,440
кон лисја, проверка вредности секој јазол против вредностите што барате.

194
00:13:13,440 --> 00:13:15,810
Ако вредноста на тековната јазол е помала од вредноста што го барате,

195
00:13:15,810 --> 00:13:18,050
одите до правото дете јазол.

196
00:13:18,050 --> 00:13:20,030
Во спротивно, ќе отидете на левата дете јазол.

197
00:13:20,030 --> 00:13:22,800
Во одреден момент, можете или ќе се најде вредноста што го барате, или ќе наидат на нула,

198
00:13:22,800 --> 00:13:28,520
укажува на вредноста не е во дрво. "

199
00:13:28,520 --> 00:13:32,450
Морам да ја прецрта дрвото имавме порано, дека ќе се земе втора.

200
00:13:32,450 --> 00:13:38,280
Но, ние сакаме да се погледне нагоре дали 6, 10 и 1 се во дрво.

201
00:13:38,280 --> 00:13:49,180
Значи она што беше, 7, 9, 3, 6. Во ред.

202
00:13:49,180 --> 00:13:52,730
Бројките дека сакате да го гледам нагоре, ние сакаме да се погледне до 6.

203
00:13:52,730 --> 00:13:55,440
Како функционира овој алгоритам работа?

204
00:13:55,440 --> 00:14:03,040
Па, ние исто така имаат некои корен покажувачот на нашите дрво.

205
00:14:03,040 --> 00:14:12,460
И ние ќе оди до коренот и да каже, дали е ова вредност еднаква на вредноста ние сме во потрага по?

206
00:14:12,460 --> 00:14:15,000
Па ние сме во потрага по 6, па тоа не е еднаква.

207
00:14:15,000 --> 00:14:20,140
Значи ние Продолжувам да одам, и сега ние се каже, во ред, па 6 е помалку од 7.

208
00:14:20,140 --> 00:14:23,940
Дали тоа значи дека ние сакаме да одиме на лево, или сакаме да одиме на правото?

209
00:14:23,940 --> 00:14:27,340
[Студентски] Лево. >> Да.

210
00:14:27,340 --> 00:14:33,340
Тоа е значително полесен, сите што треба да направите е да се подготви еден можен јазол на дрво

211
00:14:33,340 --> 00:14:37,760
а потоа можете don't - наместо да се обидува да се мисли во вашата глава,

212
00:14:37,760 --> 00:14:40,020
океј, ако тоа е помалку, можам да одам на лево или оди на десно,

213
00:14:40,020 --> 00:14:43,030
само гледајќи во сликата, тоа е многу јасно дека морам да одам од лево

214
00:14:43,030 --> 00:14:47,700
ако овој јазол е поголема од вредноста што јас барам.

215
00:14:47,700 --> 00:14:52,600
А ти оди кон лево, сега сум во 3.

216
00:14:52,600 --> 00:14:57,770
Сакам да - 3 е помала од вредноста барам, што е 6.

217
00:14:57,770 --> 00:15:03,420
Значи одиме право, и сега заврши во 6,

218
00:15:03,420 --> 00:15:07,380
која е вредноста Јас барам, па враќање вистина.

219
00:15:07,380 --> 00:15:15,760
Следниот вредност Одам да се погледне за е 10.

220
00:15:15,760 --> 00:15:23,230
Во ред. Па 10, сега, се случува да - отсече тоа - ќе ги следи коренот.

221
00:15:23,230 --> 00:15:27,670
Сега, 10 ќе биде поголема од 7, па сакам да се погледне на десната страна.

222
00:15:27,670 --> 00:15:31,660
Одам да дојди, 10 ќе биде поголем од 9,

223
00:15:31,660 --> 00:15:34,520
па јас сум ќе сакате да се погледне на десната страна.

224
00:15:34,520 --> 00:15:42,100
Јас доаѓам овде, но овде сега сум на нула.

225
00:15:42,100 --> 00:15:44,170
Што да правам ако јас хит нула?

226
00:15:44,170 --> 00:15:47,440
[Студентски] Врати се лажни? >> Да. Јас не најде 10.

227
00:15:47,440 --> 00:15:49,800
1 ќе биде речиси идентичен случај,

228
00:15:49,800 --> 00:15:51,950
освен тоа е само ќе треба да се превртува, наместо на гледање

229
00:15:51,950 --> 00:15:56,540
одредување на десната страна, ќе одам да се погледне надолу на левата страна.

230
00:15:56,540 --> 00:16:00,430
>> Сега мислам дека ние всушност го кодот.

231
00:16:00,430 --> 00:16:04,070
Еве каде - се отвори CS50 апаратот и да стигнете на вашиот пат таму,

232
00:16:04,070 --> 00:16:07,010
но може само така да го направи тоа во просторот.

233
00:16:07,010 --> 00:16:09,170
Тоа е веројатно идеално да го направи тоа во просторот,

234
00:16:09,170 --> 00:16:13,760
затоа што можат да работат во просторот.

235
00:16:13,760 --> 00:16:19,170
"Прво, ќе треба нов вид дефиниција за бинарно дрво јазол содржи int вредности.

236
00:16:19,170 --> 00:16:21,400
Користење на boilerplate typedef подолу,

237
00:16:21,400 --> 00:16:24,510
создаде нова дефиниција на тип за еден јазол во бинарно дрво.

238
00:16:24,510 --> 00:16:27,930
Ако ви се заглавени. . . "Бла, бла, бла. Океј.

239
00:16:27,930 --> 00:16:30,380
Значи, да се стави на boilerplate тука,

240
00:16:30,380 --> 00:16:41,630
typedef struct јазол, и куп. Да, во ред.

241
00:16:41,630 --> 00:16:44,270
Па што се области ние ќе сакаат во нашата јазол?

242
00:16:44,270 --> 00:16:46,520
[Студентски] инт а потоа две насоки?

243
00:16:46,520 --> 00:16:49,700
>> Инт вредност, два совети? Како можам да пишувам на совети?

244
00:16:49,700 --> 00:16:58,440
[Студентски] struct. >> Јас треба да зумирате внатре Да, така struct јазол * лево,

245
00:16:58,440 --> 00:17:01,320
и struct јазол * во право.

246
00:17:01,320 --> 00:17:03,460
И се сеќавам на дискусијата од последниот пат,

247
00:17:03,460 --> 00:17:15,290
дека тоа не прави никаква смисла, ова не прави никаква смисла,

248
00:17:15,290 --> 00:17:18,270
ова нема никаква смисла.

249
00:17:18,270 --> 00:17:25,000
Ви треба се таму со цел да се дефинира овој рекурзивен struct.

250
00:17:25,000 --> 00:17:27,970
Океј, па тоа е она што нашите дрво ќе изгледа.

251
00:17:27,970 --> 00:17:37,670
Ако ние не трикомпонентните дрво, а потоа еден јазол може да изгледа како Б1, Б2, struct јазол * Б3,

252
00:17:37,670 --> 00:17:43,470
каде што б е гранка - всушност, јас сум повеќе слушнав лево, средно, право, но сеедно.

253
00:17:43,470 --> 00:17:55,610
Ние само се грижат за бинарни, па десно, лево.

254
00:17:55,610 --> 00:17:59,110
"Сега се изјасни за глобалната јазол * променлива за коренот на дрвото".

255
00:17:59,110 --> 00:18:01,510
Па ние нема да го направат тоа.

256
00:18:01,510 --> 00:18:08,950
Со цел да се направат нештата малку потешко и повеќе генерализирана,

257
00:18:08,950 --> 00:18:11,570
ние нема да имаме глобална јазол променлива.

258
00:18:11,570 --> 00:18:16,710
Наместо тоа, во главниот ние ќе прогласи сите наши јазол работи,

259
00:18:16,710 --> 00:18:20,500
а тоа значи дека подолу, кога ќе почнат да оперираат

260
00:18:20,500 --> 00:18:23,130
нашите Содржи функција и нашите вметнете функција,

261
00:18:23,130 --> 00:18:27,410
наместо на нашите Содржи функционира само со користење на оваа глобална јазол променлива,

262
00:18:27,410 --> 00:18:34,280
ние ќе мора да се земе како аргумент на дрво кое сакаме да се процесира.

263
00:18:34,280 --> 00:18:36,650
Ја на глобалната променлива требаше да се направат работите полесно.

264
00:18:36,650 --> 00:18:42,310
Ние ќе се направат работите потешко.

265
00:18:42,310 --> 00:18:51,210
Сега, земи една минута или така само да се направи овој вид на работа,

266
00:18:51,210 --> 00:18:57,690
каде во внатрешноста на главниот сакате да ја креирате оваа дрво, и тоа е се што сакате да го направите.

267
00:18:57,690 --> 00:19:04,530
Обидете се и изградба на ова дрво во главната функција.

268
00:19:42,760 --> 00:19:47,610
>> Во ред. Така да дури и не мора да се гради дрвото целиот начин уште.

269
00:19:47,610 --> 00:19:49,840
Но секој има нешто што може да се повлече до

270
00:19:49,840 --> 00:20:03,130
да се покаже како еден би можела да започне изградба на таков дрво?

271
00:20:03,130 --> 00:20:08,080
[Студентски] Некој удира, обидувајќи се да излезат.

272
00:20:08,080 --> 00:20:13,100
[Бауден] Секој удобно со нивната дрво конструкција?

273
00:20:13,100 --> 00:20:15,520
[Студентски] Секако. Тоа не е направено. >> Тоа е во ред. Ние само може да се заврши -

274
00:20:15,520 --> 00:20:26,860
ох, можете да го зачувате? Ура.

275
00:20:26,860 --> 00:20:32,020
Значи тука имаме - ох, јас сум малку отсечен.

276
00:20:32,020 --> 00:20:34,770
Јас зумира?

277
00:20:34,770 --> 00:20:37,730
Зумирате, движете надвор. >> Имам едно прашање. >> Да?

278
00:20:37,730 --> 00:20:44,410
[Студентски] Кога ќе се дефинира структурата, се работи како иницијализиран на нешто?

279
00:20:44,410 --> 00:20:47,160
[Бауден] бр >> Океј. Значи вие ќе треба да се иницијализира -

280
00:20:47,160 --> 00:20:50,450
[Бауден] бр Кога ќе се дефинира, или кога ќе се изјасни за структурата,

281
00:20:50,450 --> 00:20:55,600
тоа не е иницијализиран по дифолт, тоа е исто како ако прогласи int.

282
00:20:55,600 --> 00:20:59,020
Тоа е токму истото. Тоа е како секој од своите индивидуални полиња

283
00:20:59,020 --> 00:21:04,460
може да има ѓубре вредност во неа. >> И тоа е можно да се дефинираат - или да прогласи struct

284
00:21:04,460 --> 00:21:07,740
на начин на кој тоа го прави нив ја иницијализирам?

285
00:21:07,740 --> 00:21:13,200
[Бауден] Да. Значи, кратенка иницијализација синтакса

286
00:21:13,200 --> 00:21:18,660
ќе изгледа како -

287
00:21:18,660 --> 00:21:22,200
Има два начини да го направите тоа. Мислам дека треба да го компајлирате

288
00:21:22,200 --> 00:21:25,840
да бидете сигурни ѕвекот, исто така, го прави ова.

289
00:21:25,840 --> 00:21:28,510
Редоследот на аргументи што доаѓа во структурата,

290
00:21:28,510 --> 00:21:32,170
ќе се стави како цел на аргументите во внатрешноста на овие големи загради.

291
00:21:32,170 --> 00:21:35,690
Значи, ако сакате да го иницијализирате до 9 и се остава да се ништовни и потоа десен биде нула,

292
00:21:35,690 --> 00:21:41,570
тоа ќе биде 9, нула, нула.

293
00:21:41,570 --> 00:21:47,890
Алтернативата е и уредник не му се допаѓа оваа синтакса,

294
00:21:47,890 --> 00:21:50,300
и мисли дека сакаат нов блок,

295
00:21:50,300 --> 00:22:01,800
но алтернативата е нешто како -

296
00:22:01,800 --> 00:22:04,190
тука, јас ќе ја ставам на нов ред.

297
00:22:04,190 --> 00:22:09,140
Вие експлицитно може да се каже, јас заборавам точната синтакса.

298
00:22:09,140 --> 00:22:13,110
Па можете експлицитно да им се обратиме со името, и да каже,

299
00:22:13,110 --> 00:22:21,570
. В, или. Вредност = 9. Лев = NULL.

300
00:22:21,570 --> 00:22:24,540
Јас сум Сомневајќи се овие треба да биде запирки.

301
00:22:24,540 --> 00:22:29,110
. Десно = NULL, па на овој начин не ви

302
00:22:29,110 --> 00:22:33,780
всушност треба да го знае редоследот на struct,

303
00:22:33,780 --> 00:22:36,650
и кога ќе ја читаш ова, тоа е многу поексплицитни

304
00:22:36,650 --> 00:22:41,920
за тоа што вредноста е се иницијализира да.

305
00:22:41,920 --> 00:22:44,080
>> Ова се случува да биде една од работите што -

306
00:22:44,080 --> 00:22:49,100
така, во најголем дел, C + + е superset на В

307
00:22:49,100 --> 00:22:54,160
Можете да ги преземат C код, се движи над неа, C + +, и тоа треба да се компајлира.

308
00:22:54,160 --> 00:22:59,570
Ова е една од работите што C + + не поддржува, па луѓето имаат тенденција да не го стори тоа.

309
00:22:59,570 --> 00:23:01,850
Јас не знам дали тоа е единствената причина поради која луѓето имаат тенденција да не го направи тоа,

310
00:23:01,850 --> 00:23:10,540
но случајот каде што е потребно да го користите потребни за работа со C + + и така не можев да го користите овој.

311
00:23:10,540 --> 00:23:14,000
Друг пример за нешто што не работи со C + + е

312
00:23:14,000 --> 00:23:16,940
како Примерок враќа "празнина *," технички,

313
00:23:16,940 --> 00:23:20,200
но може само да се каже char * x = Примерок што,

314
00:23:20,200 --> 00:23:22,840
и тој автоматски ќе биде фрлен во знак *.

315
00:23:22,840 --> 00:23:25,450
Тоа автоматски фрлија не се случи во C + +.

316
00:23:25,450 --> 00:23:28,150
Тоа не би ги собере, и експлицитно ќе треба да се каже

317
00:23:28,150 --> 00:23:34,510
char *, Примерок, што, за да го дадат на char *.

318
00:23:34,510 --> 00:23:37,270
Не постојат многу нешта кои C и C + + не се согласуваат за,

319
00:23:37,270 --> 00:23:40,620
но тие се две.

320
00:23:40,620 --> 00:23:43,120
Значи ќе одиме со оваа синтакса.

321
00:23:43,120 --> 00:23:46,150
Но, дури и ако ние не одиме со тој синтакса,

322
00:23:46,150 --> 00:23:49,470
она што е - може да биде во ред со тоа?

323
00:23:49,470 --> 00:23:52,170
[Студентски] Јас не треба да Dereference тоа? >> Да.

324
00:23:52,170 --> 00:23:55,110
Запомнете дека стрелката има имплицитна Dereference,

325
00:23:55,110 --> 00:23:58,230
и така кога ние сме само се занимаваат со структурата,

326
00:23:58,230 --> 00:24:04,300
ние сакаме да го користите. да се добие во областа внатрешноста на struct.

327
00:24:04,300 --> 00:24:07,200
И само тогаш користете стрелките е кога ќе сакате да го направите -

328
00:24:07,200 --> 00:24:13,450
добро, стрелката е еквивалентно на -

329
00:24:13,450 --> 00:24:17,020
тоа е она што би значело ако јас се користи стрела.

330
00:24:17,020 --> 00:24:24,600
Сите стрелка значи, Dereference тоа, сега сум на struct, и може да се добие оваа област.

331
00:24:24,600 --> 00:24:28,040
Или да добијат полето директно или Dereference и да добијат поле -

332
00:24:28,040 --> 00:24:30,380
Претпоставувам дека ова треба да биде вредност.

333
00:24:30,380 --> 00:24:33,910
Но, тука сум се занимаваат само со структурата, а не покажувач на struct,

334
00:24:33,910 --> 00:24:38,780
и затоа не можам да го користите стрелката.

335
00:24:38,780 --> 00:24:47,510
Но, овој вид на нешто што може да направи за сите јазли.

336
00:24:47,510 --> 00:24:55,790
О, Боже.

337
00:24:55,790 --> 00:25:09,540
Ова е 6, 7, и 3.

338
00:25:09,540 --> 00:25:16,470
Тогаш може да се постави гранките во нашата дрво, можеме да имаме 7 -

339
00:25:16,470 --> 00:25:21,650
Ние може да има, нејзината лева треба да укажуваат на 3.

340
00:25:21,650 --> 00:25:25,130
Па, како го правиме тоа?

341
00:25:25,130 --> 00:25:29,320
[Студентите, неразбирливо] >> Да. Адресата на node3,

342
00:25:29,320 --> 00:25:34,170
и ако не имаат адреса, тогаш тоа едноставно не би ги собере.

343
00:25:34,170 --> 00:25:38,190
Но, се сеќавам дека овие се покажувачи кон следниот јазли.

344
00:25:38,190 --> 00:25:44,930
Правото треба да укажуваат на 9,

345
00:25:44,930 --> 00:25:53,330
и 3 треба да укажуваат на правото на 6.

346
00:25:53,330 --> 00:25:58,480
Мислам дека ова е сите во собата. Било какви коментари или прашања?

347
00:25:58,480 --> 00:26:02,060
[Студент, неразбирливо] Коренот ќе биде 7.

348
00:26:02,060 --> 00:26:08,210
Ние само може да се каже јазол * кон меморија =

349
00:26:08,210 --> 00:26:14,160
или корен, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> За нашите цели, ние ќе треба да се занимаваат со вметнете,

351
00:26:20,730 --> 00:26:25,490
па ние ќе сакате да се напише функција да се вметне во оваа бинарно дрво

352
00:26:25,490 --> 00:26:34,230
и вметнете неизбежно ќе се јавите Примерок да се создаде нов јазол за ова дрво.

353
00:26:34,230 --> 00:26:36,590
Па работите се случува да добиете неуредна со фактот дека некои јазли

354
00:26:36,590 --> 00:26:38,590
се во моментов на магацинот

355
00:26:38,590 --> 00:26:43,680
и други јазли се случува да се заокружи на грамада кога ги внесете.

356
00:26:43,680 --> 00:26:47,640
Ова е совршено валидни, но единствената причина

357
00:26:47,640 --> 00:26:49,600
ние сме во можност да го направите тоа на магацинот

358
00:26:49,600 --> 00:26:51,840
е затоа што тоа е како измислена пример дека знаеме

359
00:26:51,840 --> 00:26:56,360
дрвото треба да биде изграден како 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Ако ние не го имаат ова, тогаш не би требало да Примерок на прво место.

361
00:27:02,970 --> 00:27:06,160
Како што ќе видиме малку подоцна, ние треба да се malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Токму сега тоа е совршено разумно да се стави на магацинот,

363
00:27:08,570 --> 00:27:14,750
но, ајде да го промените ова во Примерок имплементација.

364
00:27:14,750 --> 00:27:17,160
Така што секоја од овие сега ќе биде нешто како

365
00:27:17,160 --> 00:27:24,240
јазол * node9 = Примерок (sizeof (јазол)).

366
00:27:24,240 --> 00:27:28,040
И сега ние ќе треба да направите нашите чек.

367
00:27:28,040 --> 00:27:34,010
ако (node9 == NULL) - Не сакав тоа -

368
00:27:34,010 --> 00:27:40,950
врати 1, а потоа можеме да направиме node9-> затоа што сега тоа е покажувач,

369
00:27:40,950 --> 00:27:45,300
вредност = 6, node9-> лево = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> десно = NULL,

371
00:27:48,930 --> 00:27:51,410
и ние ќе мора да го стори тоа за секој од овие јазли.

372
00:27:51,410 --> 00:27:57,490
Така, наместо, да го стави во внатрешноста на посебна функција.

373
00:27:57,490 --> 00:28:00,620
Ајде да го наречеме јазол * build_node,

374
00:28:00,620 --> 00:28:09,050
и ова е донекаде сличен на API-јата ние обезбеди за Хафман кодирање.

375
00:28:09,050 --> 00:28:12,730
Ние ви даде initializer функции за дрво

376
00:28:12,730 --> 00:28:20,520
и deconstructor "функции" за оние дрвја и истото за шуми.

377
00:28:20,520 --> 00:28:22,570
>> Па еве ние ќе имаат initializer функција

378
00:28:22,570 --> 00:28:25,170
само да се изгради еден јазол за нас.

379
00:28:25,170 --> 00:28:29,320
И тоа се случува да се погледне доста точно се допаѓа ова.

380
00:28:29,320 --> 00:28:32,230
И јас сум дури и ќе се мрзливи и не го смени името на променливата,

381
00:28:32,230 --> 00:28:34,380
иако node9 не прави никаква смисла повеќе.

382
00:28:34,380 --> 00:28:38,610
О, претпоставувам вредност node9 не треба да се 6.

383
00:28:38,610 --> 00:28:42,800
Сега ние може да се врати node9.

384
00:28:42,800 --> 00:28:49,550
И тука ние треба да се врати нула.

385
00:28:49,550 --> 00:28:52,690
Секој согласуваат дека Build-A-јазол функција?

386
00:28:52,690 --> 00:28:59,780
Па сега ние само може да се јавите дека за да се изгради било кој јазол со одредена вредност и null покажувачи.

387
00:28:59,780 --> 00:29:09,750
Сега можеме да го наречеме тоа, ние може да се направи јазол * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
И нека направи. . .

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

390
00:29:33,980 --> 00:29:39,330
И сега ние сакаме да се постави истиот покажувачи,

391
00:29:39,330 --> 00:29:42,470
освен сега сè е веќе во однос на покажувачи

392
00:29:42,470 --> 00:29:48,480
па не треба адресата на.

393
00:29:48,480 --> 00:29:56,300
Во ред. Значи она што е последното нешто што сакате да го направите?

394
00:29:56,300 --> 00:30:03,850
Има грешка проверка дека јас не правам.

395
00:30:03,850 --> 00:30:06,800
Што значи да се изгради јазол возврат?

396
00:30:06,800 --> 00:30:11,660
[Студент, неразбирливо] >> Да. Ако Примерок не успеа, таа ќе се врати нула.

397
00:30:11,660 --> 00:30:16,460
Па јас одам да мрзеливо го спуштија тука наместо да прави услов за секоја од нив.

398
00:30:16,460 --> 00:30:22,320
Ако (node9 == NULL, или - уште поедноставно,

399
00:30:22,320 --> 00:30:28,020
ова е еквивалент на само ако не node9.

400
00:30:28,020 --> 00:30:38,310
Значи, ако не node9, или не node6, или не node3, или не node7, врати 1.

401
00:30:38,310 --> 00:30:42,850
Можеби и ние треба да се печати Примерок не успеа, или нешто.

402
00:30:42,850 --> 00:30:46,680
[Студентски] е лажна еднакви на нула, како?

403
00:30:46,680 --> 00:30:51,290
[Бауден] Секое нула вредност е false.

404
00:30:51,290 --> 00:30:53,920
Значи нула е нула вредност.

405
00:30:53,920 --> 00:30:56,780
Нула е нула вредност. Лажни е нула вредност.

406
00:30:56,780 --> 00:31:02,130
Секоја - доста само 2 нула вредности се ништовни и нула,

407
00:31:02,130 --> 00:31:07,900
лажни е само хаш дефинира како нула.

408
00:31:07,900 --> 00:31:13,030
Тоа важи и ако ние ја декларираат глобалната променлива.

409
00:31:13,030 --> 00:31:17,890
Ако ние не имаат јазол * корен се тука,

410
00:31:17,890 --> 00:31:24,150
тогаш - На убаво нешто за глобални променливи е дека тие секогаш имаат почетна вредност.

411
00:31:24,150 --> 00:31:27,500
Тоа не е точно на функции, како внатре од тука,

412
00:31:27,500 --> 00:31:34,870
ако имаме, како, јазол * или јазол х.

413
00:31:34,870 --> 00:31:37,380
Немаме поим што x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
или би можеле да ги испечатите и тие би можеле да бидат произволни.

415
00:31:40,700 --> 00:31:44,980
Тоа не е точно на глобални променливи.

416
00:31:44,980 --> 00:31:47,450
Значи јазол корен или јазол х.

417
00:31:47,450 --> 00:31:53,410
По дифолт, сето она што е глобален, ако не е експлицитно иницијализиран на некои вредност,

418
00:31:53,410 --> 00:31:57,390
има нула вредност како неговата вредност.

419
00:31:57,390 --> 00:32:01,150
Па еве, јазол * корен, ние не се експлицитно да се иницијализира на ништо,

420
00:32:01,150 --> 00:32:06,350
па нејзината стандардна вредност ќе биде нула, кој е нула вредност на покажувачи.

421
00:32:06,350 --> 00:32:11,870
Почетната вредност на x се случува да значи дека x.value е нула,

422
00:32:11,870 --> 00:32:14,260
x.left е нула, и x.right е нула.

423
00:32:14,260 --> 00:32:21,070
Значи, бидејќи тоа е struct, сите полиња на struct ќе биде нула вредности.

424
00:32:21,070 --> 00:32:24,410
Ние не треба да го користат тоа тука, иако.

425
00:32:24,410 --> 00:32:27,320
[Студентски] На structs се различни од другите променливи, и други променливи се

426
00:32:27,320 --> 00:32:31,400
ѓубре вредности; овие се нули?

427
00:32:31,400 --> 00:32:36,220
[Бауден] Други вредности премногу. Значи во x, x ќе биде нула.

428
00:32:36,220 --> 00:32:40,070
Ако тоа е во глобалниот опсег, таа има почетна вредност. >> Океј.

429
00:32:40,070 --> 00:32:48,950
[Бауден] Или почетна вредност ќе му го даде или нула.

430
00:32:48,950 --> 00:32:53,260
Мислам дека се грижи за сето ова.

431
00:32:53,260 --> 00:32:58,390
>> Во ред. Значи следниот дел од прашањето прашува,

432
00:32:58,390 --> 00:33:01,260
"Сега ние сакаме да се напише функција наречена содржи

433
00:33:01,260 --> 00:33:04,930
со прототип на bool содржи int вредност. "

434
00:33:04,930 --> 00:33:08,340
Ние нема да го стори bool содржи int вредност.

435
00:33:08,340 --> 00:33:15,110
Нашите прототип ќе изгледа како

436
00:33:15,110 --> 00:33:22,380
bool содржи (int вредност.

437
00:33:22,380 --> 00:33:24,490
А потоа ние сме, исто така, ќе го помине на дрвото

438
00:33:24,490 --> 00:33:28,870
дека треба да се проверуваат да видат дали има таа вредност.

439
00:33:28,870 --> 00:33:38,290
Значи јазол * дрво). Во ред.

440
00:33:38,290 --> 00:33:44,440
И тогаш можеме да го наречеме со нешто како,

441
00:33:44,440 --> 00:33:46,090
можеби ќе сакате да printf или нешто.

442
00:33:46,090 --> 00:33:51,040
Содржи 6, нашиот корен.

443
00:33:51,040 --> 00:33:54,300
Дека треба да се врати еден, или точно,

444
00:33:54,300 --> 00:33:59,390
а содржи 5 корен треба да се врати лажни.

445
00:33:59,390 --> 00:34:02,690
Значи донесе вториот за спроведување на оваа.

446
00:34:02,690 --> 00:34:06,780
Можете да го направи тоа или iteratively или рекурзивно.

447
00:34:06,780 --> 00:34:09,739
На убаво нешто за начинот на кој ние го поставите работите е тоа што

448
00:34:09,739 --> 00:34:12,300
тоа е подложна на нашите рекурзивен решение е многу полесно

449
00:34:12,300 --> 00:34:14,719
од глобалниот-променлива начин не.

450
00:34:14,719 --> 00:34:19,750
Затоа што ако ние само треба содржи int вредност, тогаш ние немаме начин на recursing надолу subtrees.

451
00:34:19,750 --> 00:34:24,130
Ние ќе мора да имаат посебна помошна функција која recurses по subtrees за нас.

452
00:34:24,130 --> 00:34:29,610
Но, бидејќи ние се промени тоа да се земе од дрвото како аргумент,

453
00:34:29,610 --> 00:34:32,760
кои треба секогаш биле на прво место,

454
00:34:32,760 --> 00:34:35,710
Сега можеме да recurse полесно.

455
00:34:35,710 --> 00:34:38,960
Па итеративен или рекурзивен, ќе одиме над двата,

456
00:34:38,960 --> 00:34:46,139
но ќе видиме дека рекурзивен завршува се прилично лесно.

457
00:34:59,140 --> 00:35:02,480
Во ред. Дали некој има нешто што може да работи со?

458
00:35:02,480 --> 00:35:12,000
>> [Студентски] Имам итеративен решение. >> Добро, итеративен.

459
00:35:12,000 --> 00:35:16,030
Океј, ова изгледа добро.

460
00:35:16,030 --> 00:35:18,920
Значи, сакате да ни помогне преку неа?

461
00:35:18,920 --> 00:35:25,780
[Студентски] Секако. Па јас се постави температура променлива да се добие првиот јазол од дрвото.

462
00:35:25,780 --> 00:35:28,330
А потоа јас само looped преку додека температура не еднакви на нула,

463
00:35:28,330 --> 00:35:31,700
па додека уште беше во дрво, претпоставувам.

464
00:35:31,700 --> 00:35:35,710
И ако вредноста е еднаква на вредноста која температура е да се покажува,

465
00:35:35,710 --> 00:35:37,640
тогаш тоа се враќа на таа вредност.

466
00:35:37,640 --> 00:35:40,210
Инаку, се проверува дали е на десната страна или на левата страна.

467
00:35:40,210 --> 00:35:43,400
Ако некогаш добиете ситуација каде што не постои повеќе дрво,

468
00:35:43,400 --> 00:35:47,330
тогаш тоа се враќа - тоа излегува на јамка и се враќа false.

469
00:35:47,330 --> 00:35:52,190
[Бауден] Во ред. Така што се чини дека е добро.

470
00:35:52,190 --> 00:35:58,470
Секој имате било какви коментари на нешто?

471
00:35:58,470 --> 00:36:02,400
Јас немам точноста коментари на сите.

472
00:36:02,400 --> 00:36:11,020
Едно нешто можеме да направиме е овој човек.

473
00:36:11,020 --> 00:36:21,660
Ох, тоа се случува да се искачам малку longish.

474
00:36:21,660 --> 00:36:33,460
Јас ќе утврдат дека до. Во ред.

475
00:36:33,460 --> 00:36:37,150
>> Секој треба да се сеќавам како троичен работи.

476
00:36:37,150 --> 00:36:38,610
Постојат дефинитивно е квизови во минатото

477
00:36:38,610 --> 00:36:41,170
кои ви даде функција со троичен оператор,

478
00:36:41,170 --> 00:36:45,750
и да каже, се преведе ова, направи нешто што не користи троичен.

479
00:36:45,750 --> 00:36:49,140
Значи ова е многу чест случај за тоа кога јас не би помислил да се користи троичен,

480
00:36:49,140 --> 00:36:54,610
каде што, ако некои услови постави променлива на нешто,

481
00:36:54,610 --> 00:36:58,580
друг во собата истата променлива на нешто друго.

482
00:36:58,580 --> 00:37:03,390
Тоа е нешто што многу често може да се трансформира во овој вид на работа

483
00:37:03,390 --> 00:37:14,420
каде што ја постави таа променлива на оваа - или, добро, дали е ова вистина? Тогаш ова, друго ова.

484
00:37:14,420 --> 00:37:18,550
[Студентски] Првиот е ако е точно, нели?

485
00:37:18,550 --> 00:37:25,570
[Бауден] Да. Начинот на кој јас секогаш го прочитате е, Temp еднаква вредност поголема од temp вредност,

486
00:37:25,570 --> 00:37:30,680
тогаш ова, друго ова. Тоа е поставување на прашање.

487
00:37:30,680 --> 00:37:35,200
Е поголема? Потоа направи првото нешто. Друг го стори Втората работа.

488
00:37:35,200 --> 00:37:41,670
Јас скоро секогаш - на дебелото црево, јас само - во мојата глава, јас ги прочитав како друго.

489
00:37:41,670 --> 00:37:47,180
>> Дали некој има рекурзивен решение?

490
00:37:47,180 --> 00:37:49,670
Во ред. Оваа една ние ќе - тоа веќе може да биде голема,

491
00:37:49,670 --> 00:37:53,990
но ние ќе се направи тоа дури и подобро.

492
00:37:53,990 --> 00:37:58,720
Ова е прилично многу исти точно идеја.

493
00:37:58,720 --> 00:38:03,060
Тоа е само, добро, сакаш да се објасни?

494
00:38:03,060 --> 00:38:08,340
[Студентски] Секако. Па ние сме си сигурен дека дрвото не е NULL прво,

495
00:38:08,340 --> 00:38:13,380
бидејќи ако дрвото е нула, тогаш тоа нема да се врати лажни, бидејќи ние не го најде.

496
00:38:13,380 --> 00:38:19,200
И ако има уште едно дрво, ние одиме во - ние прво проверете дали вредноста е моменталниот јазол.

497
00:38:19,200 --> 00:38:23,740
Враќање вистина ако е така, и ако ние не recurse на лево или десно.

498
00:38:23,740 --> 00:38:25,970
Дали тоа звучи соодветно? >> ММ-hmm. (Договор)

499
00:38:25,970 --> 00:38:33,880
Значи забележите дека ова е речиси - структурно многу слични во повторната решение.

500
00:38:33,880 --> 00:38:38,200
Тоа е само дека наместо recursing, имавме додека јамка.

501
00:38:38,200 --> 00:38:40,840
И на база случај тука каде што дрво не еднакви нула

502
00:38:40,840 --> 00:38:44,850
беше услов под кој избувна на време јамка.

503
00:38:44,850 --> 00:38:50,200
Тие се многу слични. Но, ние ќе ја искористам оваа чекор понатаму.

504
00:38:50,200 --> 00:38:54,190
Сега, ние го прават истото тука.

505
00:38:54,190 --> 00:38:57,680
Забележете ние враќање на истото во двата од овие линии,

506
00:38:57,680 --> 00:39:00,220
освен за еден аргумент е поинаква.

507
00:39:00,220 --> 00:39:07,950
Така ние ќе да се направи тоа во троичен.

508
00:39:07,950 --> 00:39:13,790
Јас хит опција нешто, а тоа го направи симбол. Во ред.

509
00:39:13,790 --> 00:39:21,720
Па ние ќе се вратат ги содржи тој.

510
00:39:21,720 --> 00:39:28,030
Ова е да успеат да бидат повеќе линии, добро, zoomed во тоа.

511
00:39:28,030 --> 00:39:31,060
Обично, како стилска работа, јас не мислам дека многу луѓе

512
00:39:31,060 --> 00:39:38,640
стави празно место по стрела, но претпоставувам дека ако сте доследни, тоа е во ред.

513
00:39:38,640 --> 00:39:44,320
Ако вредноста е помала од дрво вредност, ние сакаме да recurse на дрво лево,

514
00:39:44,320 --> 00:39:53,890
друго сакаме да recurse на дрво право.

515
00:39:53,890 --> 00:39:58,610
Значи тоа беше еден чекор од правење на ова изгледа помала.

516
00:39:58,610 --> 00:40:02,660
Чекор два за изработка на овој изглед помали -

517
00:40:02,660 --> 00:40:09,150
можеме да ја одвоиме ова на повеќе линии.

518
00:40:09,150 --> 00:40:16,500
Во ред. Чекор два прави да изгледа помала е тука,

519
00:40:16,500 --> 00:40:25,860
па вратената вредност е еднаква на дрво вредност, или содржи сеедно.

520
00:40:25,860 --> 00:40:28,340
>> Ова е важна работа.

521
00:40:28,340 --> 00:40:30,860
Не сум сигурен дали тој рече дека тоа експлицитно во класа,

522
00:40:30,860 --> 00:40:34,740
но тоа се вика краток спој евалуација.

523
00:40:34,740 --> 00:40:41,060
Идејата тука е вредноста == дрво вредност.

524
00:40:41,060 --> 00:40:49,960
Ако тоа е точно, тогаш ова е точно, и ние сакаме да 'или' дека со она што е овде.

525
00:40:49,960 --> 00:40:52,520
Па дури и без размислување за она што е овде,

526
00:40:52,520 --> 00:40:55,070
она што е на целиот израз ќе се врати?

527
00:40:55,070 --> 00:40:59,430
[Студентски] вистина? >> Да, затоа што важи и за ништо,

528
00:40:59,430 --> 00:41:04,990
or'd - или точно or'd со нешто е секогаш точно.

529
00:41:04,990 --> 00:41:08,150
Па штом гледаме повратната вредност = дрво вредност,

530
00:41:08,150 --> 00:41:10,140
ние сме само ќе се врати вистина.

531
00:41:10,140 --> 00:41:15,710
Дури и не ќе recurse понатаму содржи одредување на линија.

532
00:41:15,710 --> 00:41:20,980
Ние можеме да ја искористам оваа чекор понатаму.

533
00:41:20,980 --> 00:41:29,490
Врати дрво не еднакви нула и сето ова.

534
00:41:29,490 --> 00:41:32,650
Тоа го направи една линија функција.

535
00:41:32,650 --> 00:41:36,790
Ова е исто така пример за краток спој евалуација.

536
00:41:36,790 --> 00:41:40,680
Но, сега тоа е истата идеја -

537
00:41:40,680 --> 00:41:47,320
наместо - па ако дрво не е еднаков на нула - или, добро,

538
00:41:47,320 --> 00:41:49,580
ако дрво прави еднакви на нула, што е лош случај,

539
00:41:49,580 --> 00:41:54,790
ако дрво е еднаква на нула, тогаш првиот услов ќе биде лажна.

540
00:41:54,790 --> 00:42:00,550
Значи лажни anded со ништо нема да биде она што?

541
00:42:00,550 --> 00:42:04,640
[Студентски] Лажни. >> Да. Ова е другата половина од краток спој евалуација,

542
00:42:04,640 --> 00:42:10,710
каде што ако дрво не еднакви нула, тогаш ние нема да одат дури и -

543
00:42:10,710 --> 00:42:14,930
или ако дрво прави еднакви нула, тогаш ние не се случува да се направи вредност == дрво вредност.

544
00:42:14,930 --> 00:42:17,010
Ние сме само ќе веднаш да се врати лажни.

545
00:42:17,010 --> 00:42:20,970
Што е важно, бидејќи ако тоа не предизвикувајте краток спој оцени,

546
00:42:20,970 --> 00:42:25,860
а потоа, ако дрво прави еднакви на нула, ова вториот услов ќе секунда грешка,

547
00:42:25,860 --> 00:42:32,510
бидејќи дрво> вредност се dereferencing нула.

548
00:42:32,510 --> 00:42:40,490
Значи тоа е тоа. Може да се направи ова - префрлат еднаш завршена.

549
00:42:40,490 --> 00:42:44,840
Ова е многу честа работа, исто така, не прави оваа линија со ова,

550
00:42:44,840 --> 00:42:49,000
но тоа е заедничка работа во услови, можеби токму тука,

551
00:42:49,000 --> 00:42:59,380
но ако (дрво! = NULL, и дрво-> вредноста == вредност), го направи она што.

552
00:42:59,380 --> 00:43:01,560
Ова е многу честа состојба, каде што наместо

553
00:43:01,560 --> 00:43:06,770
да се скрши тоа во две IFS, каде се допаѓа, е дрво нула?

554
00:43:06,770 --> 00:43:11,780
Океј, тоа не е нула, па сега е дрво вредност еднаква вредност? Го направите тоа.

555
00:43:11,780 --> 00:43:17,300
Наместо тоа, оваа состојба, ова никогаш не ќе секунда грешка

556
00:43:17,300 --> 00:43:21,220
поради тоа што ќе се пробие, ако тоа се случува да биде нула.

557
00:43:21,220 --> 00:43:24,000
Па, претпоставувам дека ако вашиот дрво е сосема валиден покажувач, може уште секунда грешка,

558
00:43:24,000 --> 00:43:26,620
но тоа не може секунда грешка ако дрво е нула.

559
00:43:26,620 --> 00:43:32,900
Ако тоа се ништовни, тоа ќе се пробие пред Дали некогаш сте dereferenced покажувачот на прво место.

560
00:43:32,900 --> 00:43:35,000
[Студентски] Дали е ова т.н. мрзливи оценка?

561
00:43:35,000 --> 00:43:40,770
>> [Бауден] Lazy оценување е посебна работа.

562
00:43:40,770 --> 00:43:49,880
Мрзливи оценување е повеќе како ве праша за вредност,

563
00:43:49,880 --> 00:43:54,270
Ве молиме да се пресмета вредноста, вид, но вие не треба веднаш.

564
00:43:54,270 --> 00:43:59,040
Значи додека вие всушност треба, тоа не се оценува.

565
00:43:59,040 --> 00:44:03,920
Ова не е иста работа, но во Хафман pset,

566
00:44:03,920 --> 00:44:06,520
таа вели дека ние "мрзеливо" пишува.

567
00:44:06,520 --> 00:44:08,670
Причината поради која го направите тоа е затоа што ние сме всушност визуелниот пишуваат -

568
00:44:08,670 --> 00:44:11,820
ние не сакаме да се напише индивидуалните битови во еден момент,

569
00:44:11,820 --> 00:44:15,450
или индивидуални бајти во еден момент, ние наместо да сакате да добиете парче од бајти.

570
00:44:15,450 --> 00:44:19,270
Потоа еднаш имаме парче на бајти, тогаш ние ќе го напише.

571
00:44:19,270 --> 00:44:22,640
И покрај тоа што тој побара да се напише - и запишување и fread го стори истото вид на работа.

572
00:44:22,640 --> 00:44:26,260
Тие тампон вашиот чита и пишува.

573
00:44:26,260 --> 00:44:31,610
И покрај тоа што го побара веднаш да пишува, тоа веројатно нема.

574
00:44:31,610 --> 00:44:34,540
И не можете да бидете сигурни дека работите се случува да бидат напишани

575
00:44:34,540 --> 00:44:37,540
додека ти се јавам hfclose или што и да е,

576
00:44:37,540 --> 00:44:39,620
кои потоа вели, добро, јас сум затворање мојот датотека,

577
00:44:39,620 --> 00:44:43,450
тоа значи дека е подобро да напишете сè што не го имаат напишано уште.

578
00:44:43,450 --> 00:44:45,770
Тоа не треба да се напише се надвор

579
00:44:45,770 --> 00:44:49,010
додека не се затворање на датотека, а потоа таа треба да.

580
00:44:49,010 --> 00:44:56,220
Значи тоа е само она што мрзливи - чека се додека не мора да се случи.

581
00:44:56,220 --> 00:44:59,990
Ова - се 51 и ќе оди во тоа во повеќе детали,

582
00:44:59,990 --> 00:45:05,470
бидејќи OCaml и се што е во 51, што е рекурзија.

583
00:45:05,470 --> 00:45:08,890
Нема итеративен решенија, во основа.

584
00:45:08,890 --> 00:45:11,550
Сè што е рекурзија, и мрзливи евалуација

585
00:45:11,550 --> 00:45:14,790
ќе биде важна за многу околности

586
00:45:14,790 --> 00:45:19,920
каде што, ако не мрзеливо оцени, тоа би значело -

587
00:45:19,920 --> 00:45:24,760
На пример е струи, кои се бескрајно долго.

588
00:45:24,760 --> 00:45:30,990
Во теорија, може да се мисли на природните броеви како поток од 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Па мрзеливо оценуваат работите се во ред.

590
00:45:33,090 --> 00:45:37,210
Ако кажам сакам десеттиот број, тогаш може да се оцени до десеттиот број.

591
00:45:37,210 --> 00:45:40,300
Ако сакам стоти број, тогаш може да се оцени до стоти број.

592
00:45:40,300 --> 00:45:46,290
Без мрзливи евалуација, а потоа тоа ќе се обиде да се оцени сите броеви веднаш.

593
00:45:46,290 --> 00:45:50,000
Ти си оценување бесконечно многу броеви, и тоа не е само можно.

594
00:45:50,000 --> 00:45:52,080
Па така постојат многу околности каде мрзливи евалуација

595
00:45:52,080 --> 00:45:57,840
е само од суштинско значење за добивање на работите на работа.

596
00:45:57,840 --> 00:46:05,260
>> Сега ние сакаме да се напише вметнете каде вметнете ќе биде

597
00:46:05,260 --> 00:46:08,430
Слично менува во својата дефиниција.

598
00:46:08,430 --> 00:46:10,470
Па сега тоа е bool вметнете (int вредност).

599
00:46:10,470 --> 00:46:23,850
Ние ќе го промени тоа да bool вметнете (int вредност, јазол * дрво).

600
00:46:23,850 --> 00:46:29,120
Ние сме всушност ќе се смени тоа повторно во малку, ние ќе се види зошто.

601
00:46:29,120 --> 00:46:32,210
И ајде да се движат build_node, само за грижам за тоа,

602
00:46:32,210 --> 00:46:36,730
над вметнете па ние не треба да се напише функција прототип.

603
00:46:36,730 --> 00:46:42,450
Што е знак дека ви се случува да се користи build_node во вметнете.

604
00:46:42,450 --> 00:46:49,590
Во ред. Земете една минута за тоа.

605
00:46:49,590 --> 00:46:52,130
Мислам дека спаси ревизија ако сакате да се повлече од тоа,

606
00:46:52,130 --> 00:47:00,240
или, барем, јас не сега.

607
00:47:00,240 --> 00:47:04,190
Сакав мала пауза да се размислува за логиката на вметнете,

608
00:47:04,190 --> 00:47:08,750
ако не можете да мислам на тоа.

609
00:47:08,750 --> 00:47:12,860
Во суштина, ти само ќе бидеш вметнување на лисја.

610
00:47:12,860 --> 00:47:18,640
Како, ако вметнете 1, тогаш јас сум неизбежно ќе биде вметнување 1 -

611
00:47:18,640 --> 00:47:21,820
Ќе се смени во црно - I'll се вметнување 1 овде.

612
00:47:21,820 --> 00:47:28,070
Или ако вметнете 4, сакам да биде вметнување 4 овде.

613
00:47:28,070 --> 00:47:32,180
Значи без разлика што правиш, си оди за да се вметнување на листот.

614
00:47:32,180 --> 00:47:36,130
Се што треба да направите е да iterate одредување на дрво додека не стигнете до јазол

615
00:47:36,130 --> 00:47:40,890
што треба да биде родител на јазол, родител на нов јазол,

616
00:47:40,890 --> 00:47:44,560
а потоа го промени својот лево или десно покажувач, во зависност од тоа дали

617
00:47:44,560 --> 00:47:47,060
тоа е поголема или помала од сегашната јазол.

618
00:47:47,060 --> 00:47:51,180
Промена дека покажувачот да укаже на вашиот нов јазол.

619
00:47:51,180 --> 00:48:05,490
Значи iterate долу на дрвото, направи лист точка на новиот јазол.

620
00:48:05,490 --> 00:48:09,810
Исто така мислам за тоа зошто тој забранува тип на ситуација пред,

621
00:48:09,810 --> 00:48:17,990
каде што конструирал бинарно дрво каде што беше правилна

622
00:48:17,990 --> 00:48:19,920
ако само погледна еден јазол,

623
00:48:19,920 --> 00:48:24,830
но 9 беше лево од 7 ако потврди долу сите на патот.

624
00:48:24,830 --> 00:48:29,770
Така што е невозможно во ова сценарио, бидејќи -

625
00:48:29,770 --> 00:48:32,530
мислите за вметнување 9 или нешто; на самиот прв јазол,

626
00:48:32,530 --> 00:48:35,350
Одам да видам 7 и јас сум само ќе оди на десно.

627
00:48:35,350 --> 00:48:38,490
Значи без оглед што правам, ако сум вметнување со одење на лист,

628
00:48:38,490 --> 00:48:40,790
и на лист со помош на соодветен алгоритам,

629
00:48:40,790 --> 00:48:43,130
тоа ќе биде невозможно за мене да вметнете 9 лево од 7

630
00:48:43,130 --> 00:48:48,250
бидејќи штом ќе го погоди 7 Одам да одат на десно.

631
00:48:59,740 --> 00:49:02,070
Дали некој има нешто да се започне со?

632
00:49:02,070 --> 00:49:05,480
[Студентски] правам. >> Секако.

633
00:49:05,480 --> 00:49:09,200
[Студент, неразбирливо]

634
00:49:09,200 --> 00:49:14,390
[Други студент, неразбирливо]

635
00:49:14,390 --> 00:49:18,330
[Бауден] Тоа е добредојдена. Во ред. Сакате да се објасни?

636
00:49:18,330 --> 00:49:20,690
>> [Студентски] Бидејќи знаеме дека сме биле вметнување

637
00:49:20,690 --> 00:49:24,060
нови јазли на крајот на дрвото,

638
00:49:24,060 --> 00:49:28,070
Јас looped преку дрво iteratively

639
00:49:28,070 --> 00:49:31,360
додека не стигнав до еден јазол, која посочи на нула.

640
00:49:31,360 --> 00:49:34,220
И тогаш решив да го стави или на десната страна или на левата страна

641
00:49:34,220 --> 00:49:37,420
користење на ова право променлива, таа ми кажа каде да го стави.

642
00:49:37,420 --> 00:49:41,850
И тогаш, во суштина, јас само го направи тоа минатата -

643
00:49:41,850 --> 00:49:47,520
дека Темп јазол точка на новиот јазол дека тоа е креирање,

644
00:49:47,520 --> 00:49:50,770
или на левата страна или од десната страна, во зависност од она што вредност право беше.

645
00:49:50,770 --> 00:49:56,530
Конечно, јас во собата на нов јазол вредност на вредноста на тестирање.

646
00:49:56,530 --> 00:49:59,550
[Бауден] Океј, па гледам едно прашање тука.

647
00:49:59,550 --> 00:50:02,050
Ова е како 95% од пат таму.

648
00:50:02,050 --> 00:50:07,550
На едно прашање што гледам, добро, дали некој друг се види ова прашање?

649
00:50:07,550 --> 00:50:18,400
Што е околноста под кои тие се пробие на јамка?

650
00:50:18,400 --> 00:50:22,100
[Студентски] Ако температура е нула? >> Да. Па, како да се пробие на јамка е ако Темп е нула.

651
00:50:22,100 --> 00:50:30,220
Но, што да правам тука?

652
00:50:30,220 --> 00:50:35,410
Јас Dereference Temp, што е неизбежно нула.

653
00:50:35,410 --> 00:50:39,840
Па друга работа што треба да направите не е само да ги пратите до температура е нула,

654
00:50:39,840 --> 00:50:45,590
сакате да ги пратите на родител на сите времиња.

655
00:50:45,590 --> 00:50:52,190
Ние исто така сакаме јазол * родител, претпоставувам дека ние може да ги задржи дека во нула во прв план.

656
00:50:52,190 --> 00:50:55,480
Ова се случува да имаат чудно однесување за коренот на дрвото,

657
00:50:55,480 --> 00:50:59,210
но ние ќе дојдеме до тоа.

658
00:50:59,210 --> 00:51:03,950
Ако вредноста е поголема од она што тогаш Темп = Темп право.

659
00:51:03,950 --> 00:51:07,910
Но, пред да го направите тоа, родител = Temp.

660
00:51:07,910 --> 00:51:14,500
Или родители секогаш ќе еднаков температура? Е дека случајот?

661
00:51:14,500 --> 00:51:19,560
Ако температура не е нула, тогаш јас ќе одам да се движат надолу, без разлика што,

662
00:51:19,560 --> 00:51:24,030
на јазол за која температура е родител.

663
00:51:24,030 --> 00:51:27,500
Значи родител ќе биде Temp, а потоа се движи температура надолу.

664
00:51:27,500 --> 00:51:32,410
Сега температура е нула, но родителот укажува на родител на нешто што е нула.

665
00:51:32,410 --> 00:51:39,110
Значи тука долу, не сакате да го поставите право е еднаква на 1.

666
00:51:39,110 --> 00:51:41,300
Па јас се пресели во право, па ако правото = 1,

667
00:51:41,300 --> 00:51:45,130
и претпоставувам дека исто така, сакаат да се направи -

668
00:51:45,130 --> 00:51:48,530
ако се преселите на лево, сакате да го поставите право еднаква на 0.

669
00:51:48,530 --> 00:51:55,950
Или на друго место, ако некогаш се движи кон десно.

670
00:51:55,950 --> 00:51:58,590
Значи десно = 0. Ако десно = 1,

671
00:51:58,590 --> 00:52:04,260
сега ние сакаме да се направи родител право покажувачот newnode,

672
00:52:04,260 --> 00:52:08,520
друго сакаме да се направи родител левата покажувачот newnode.

673
00:52:08,520 --> 00:52:16,850
Прашања за тоа?

674
00:52:16,850 --> 00:52:24,880
Во ред. Значи ова е начинот на кој ние - и, всушност, наместо тоа,

675
00:52:24,880 --> 00:52:29,630
ние половина очекува да користите build_node.

676
00:52:29,630 --> 00:52:40,450
А потоа ако newnode еднаква на нула, се врати лажни.

677
00:52:40,450 --> 00:52:44,170
Тоа е тоа. Сега, ова е она што го очекуваше да се направи.

678
00:52:44,170 --> 00:52:47,690
>> Тоа е она што на вработените решенија направи.

679
00:52:47,690 --> 00:52:52,360
Јас не се согласувам со ова како "право" начин на одење за тоа

680
00:52:52,360 --> 00:52:57,820
но ова е совршено во ред и тоа ќе работи.

681
00:52:57,820 --> 00:53:02,840
Едно нешто што е малку чудно во моментов е

682
00:53:02,840 --> 00:53:08,310
ако дрвото почнува како нула, ние помине во нула дрво.

683
00:53:08,310 --> 00:53:12,650
Претпоставувам дека тоа зависи од тоа како го дефинирате однесувањето на донесување на нула дрво.

684
00:53:12,650 --> 00:53:15,490
Јас би помислил дека ако помине во нула дрво,

685
00:53:15,490 --> 00:53:17,520
потоа вметнување на вредноста во нула дрво

686
00:53:17,520 --> 00:53:23,030
само треба да се врати на дрво каде што е само вредноста е дека еден јазол.

687
00:53:23,030 --> 00:53:25,830
Дали луѓето се согласувате со тоа? Може, ако сака,

688
00:53:25,830 --> 00:53:28,050
ако помине во нула дрво

689
00:53:28,050 --> 00:53:31,320
и сакате да внесете вредност во неа, се врати лажни.

690
00:53:31,320 --> 00:53:33,830
Тоа е до вас да се дефинира тоа.

691
00:53:33,830 --> 00:53:38,320
За да го направите првото нешто што го рече, а потоа -

692
00:53:38,320 --> 00:53:40,720
Па, ви се случува да имаат проблеми да го направи тоа, затоа што

693
00:53:40,720 --> 00:53:44,090
тоа ќе биде полесно ако имавме глобалната покажувачот на работа,

694
00:53:44,090 --> 00:53:48,570
но не, па ако дрво е нула, нема ништо што можеме да направиме во врска со тоа.

695
00:53:48,570 --> 00:53:50,960
Ние само може да се врати лажни.

696
00:53:50,960 --> 00:53:52,840
Па ќе одам да се промени внесување.

697
00:53:52,840 --> 00:53:56,540
Ние технички само може да се промени ова право тука,

698
00:53:56,540 --> 00:53:58,400
како е процесирањето врз нештата,

699
00:53:58,400 --> 00:54:04,530
но јас ќе одам да се промени вметнете да се земе еден јазол ** дрво.

700
00:54:04,530 --> 00:54:07,510
Двоен совети.

701
00:54:07,510 --> 00:54:09,710
Што значи ова?

702
00:54:09,710 --> 00:54:12,330
Наместо да се занимава со покажувачи на јазли,

703
00:54:12,330 --> 00:54:16,690
нешто јас ќе одам да се манипулира е овој покажувач.

704
00:54:16,690 --> 00:54:18,790
Одам да се манипулира овој покажувач.

705
00:54:18,790 --> 00:54:21,770
Одам да се манипулира совети директно.

706
00:54:21,770 --> 00:54:25,760
Ова има смисла бидејќи, мислам за одредување на -

707
00:54:25,760 --> 00:54:33,340
Па, токму сега ова укажува на нула.

708
00:54:33,340 --> 00:54:38,130
Она што сакам да направите е да манипулира со оваа покажувачот да укаже НЕ NULL.

709
00:54:38,130 --> 00:54:40,970
Сакам да се укаже на мојот нов јазол.

710
00:54:40,970 --> 00:54:44,870
Ако јас само да ги пратите на покажувачи на мојот покажувачи,

711
00:54:44,870 --> 00:54:47,840
тогаш јас не треба да ги пратите на родител покажувач.

712
00:54:47,840 --> 00:54:52,640
Јас само да ги пратите да се види дали покажувачот се укажува на нула,

713
00:54:52,640 --> 00:54:54,580
и ако покажувачот се укажува на нула,

714
00:54:54,580 --> 00:54:57,370
промените да се укаже на јазол сакам.

715
00:54:57,370 --> 00:55:00,070
И можам да ја промените бидејќи имам покажувач на покажувач.

716
00:55:00,070 --> 00:55:02,040
Ајде да видиме ова право сега.

717
00:55:02,040 --> 00:55:05,470
Ти всушност може да го направи тоа рекурзивно прилично лесно.

718
00:55:05,470 --> 00:55:08,080
Сакаме да го направите тоа?

719
00:55:08,080 --> 00:55:10,980
Да, тоа го правиме.

720
00:55:10,980 --> 00:55:16,790
>> Ајде да го видиме рекурзивно.

721
00:55:16,790 --> 00:55:24,070
Прво, она што е нашата база случај ќе биде?

722
00:55:24,070 --> 00:55:29,140
Речиси секогаш нашата база случај, но, всушност, ова е вид на слабо.

723
00:55:29,140 --> 00:55:34,370
Првите нешта прво, ако (дрво == NULL)

724
00:55:34,370 --> 00:55:37,550
Претпоставувам дека ние сме само ќе се врати лажни.

725
00:55:37,550 --> 00:55:40,460
Ова е различно од вашето дрво се ништовни.

726
00:55:40,460 --> 00:55:44,510
Ова е покажувач кон вашиот корен покажувачот се ништовни

727
00:55:44,510 --> 00:55:48,360
што значи дека вашиот корен покажувачот не постои.

728
00:55:48,360 --> 00:55:52,390
Значи тука долу, ако го направам

729
00:55:52,390 --> 00:55:55,760
јазол * - ајде да повторна употреба ова.

730
00:55:55,760 --> 00:55:58,960
Јазол * корен = NULL,

731
00:55:58,960 --> 00:56:00,730
а потоа јас ќе одам да се јавите вметнете со нешто како,

732
00:56:00,730 --> 00:56:04,540
вметнете 4 во & корен.

733
00:56:04,540 --> 00:56:06,560
Така и корен, ако коренот е еден јазол *

734
00:56:06,560 --> 00:56:11,170
тогаш и коренот ќе биде еден јазол. **

735
00:56:11,170 --> 00:56:15,120
Ова е валиден. Во овој случај, дрвото, до тука,

736
00:56:15,120 --> 00:56:20,120
дрво не е нула - или вметнете.

737
00:56:20,120 --> 00:56:24,630
Тука. Дрво не е нула; * дрво е нула, што е во ред

738
00:56:24,630 --> 00:56:26,680
бидејќи ако * дрво е нула, тогаш може да се манипулира

739
00:56:26,680 --> 00:56:29,210
до сега укажуваат на она што го сакате тоа да се укаже.

740
00:56:29,210 --> 00:56:34,750
Но, ако дрво е нула, тоа значи дека само што дојде овде и рече нула.

741
00:56:34,750 --> 00:56:42,710
Тоа не дава никаква смисла. Јас не може да направи ништо со тоа.

742
00:56:42,710 --> 00:56:45,540
Ако дрвото е нула, се врати лажни.

743
00:56:45,540 --> 00:56:48,220
Па јас во основа веќе рече дека она што нашата вистинска база случај е.

744
00:56:48,220 --> 00:56:50,580
И што е тоа што ќе биде?

745
00:56:50,580 --> 00:56:55,030
[Студент, неразбирливо]

746
00:56:55,030 --> 00:57:00,000
[Бауден] Да. Значи, ако (* дрво == NULL).

747
00:57:00,000 --> 00:57:04,520
Ова се однесува на случајот овде

748
00:57:04,520 --> 00:57:09,640
каде што ако мојот црвен покажувачот е покажувач сум фокусирани на,

749
00:57:09,640 --> 00:57:12,960
па како јас сум фокусиран на овој покажувач, сега сум фокусиран на овој покажувач.

750
00:57:12,960 --> 00:57:15,150
Сега сум фокусиран на овој покажувач.

751
00:57:15,150 --> 00:57:18,160
Значи, ако мојот црвен покажувач, што е мојот јазол **,

752
00:57:18,160 --> 00:57:22,880
е некогаш - ако *, мојот црвен покажувач, секогаш е нула,

753
00:57:22,880 --> 00:57:28,470
тоа значи дека сум во случај кога јас сум се фокусира на покажувач кој покажува -

754
00:57:28,470 --> 00:57:32,530
ова е показател дека припаѓа на лист.

755
00:57:32,530 --> 00:57:41,090
Сакам да го промените ова покажувачот да укаже на мојот нов јазол.

756
00:57:41,090 --> 00:57:45,230
Се врати овде.

757
00:57:45,230 --> 00:57:56,490
Мој newnode само ќе биде јазол * n = build_node (вредност)

758
00:57:56,490 --> 00:58:07,300
тогаш n, ако n = NULL, се врати лажни.

759
00:58:07,300 --> 00:58:12,600
Друго што сакаме да го промени она што го покажувачот моментално укажува на

760
00:58:12,600 --> 00:58:17,830
до сега укажуваат на нашите новоизградени јазол.

761
00:58:17,830 --> 00:58:20,280
Ние всушност може да го стори тоа овде.

762
00:58:20,280 --> 00:58:30,660
Наместо да се каже n, ние велиме * дрво = доколку * дрво.

763
00:58:30,660 --> 00:58:35,450
Секој разбере тоа? Кои од кои се занимаваат со покажувачи да покажувачи,

764
00:58:35,450 --> 00:58:40,750
можеме да го промениме нула покажувачи да се укаже на работи што сакаме од нив да се укаже.

765
00:58:40,750 --> 00:58:42,820
Тоа е нашата база случај.

766
00:58:42,820 --> 00:58:45,740
>> Сега нашите повторување, или нашите рекурзија,

767
00:58:45,740 --> 00:58:51,430
ќе биде многу сличен со сите други recursions сме правеле.

768
00:58:51,430 --> 00:58:55,830
Ние ќе сакате да го внесете вредност,

769
00:58:55,830 --> 00:58:59,040
и сега ќе одам да се користи троичен повторно, но она што е нашата состојба ќе биде?

770
00:58:59,040 --> 00:59:05,180
Што е тоа што го барате да одлучи дали ние сакаме да одиме лево или десно?

771
00:59:05,180 --> 00:59:07,760
Да го сториме тоа во одделни чекори.

772
00:59:07,760 --> 00:59:18,850
Ако (вредност <) што?

773
00:59:18,850 --> 00:59:23,200
[Студентски] вредност на дрвото?

774
00:59:23,200 --> 00:59:27,490
[Бауден] Значи се сеќавам дека сум во моментов -

775
00:59:27,490 --> 00:59:31,260
[Студентите, неразбирливо]

776
00:59:31,260 --> 00:59:34,140
[Бауден] Да, па токму тука, да речеме дека оваа зелена стрелка

777
00:59:34,140 --> 00:59:39,050
е пример на она дрво во моментов е, е покажувач кон овој покажувач.

778
00:59:39,050 --> 00:59:46,610
Па тоа значи дека јас сум покажувач кон покажувач до 3.

779
00:59:46,610 --> 00:59:48,800
На Dereference двапати звучеше добро.

780
00:59:48,800 --> 00:59:51,010
Што ми - како да го направам тоа?

781
00:59:51,010 --> 00:59:53,210
[Студентски] Dereference еднаш, а потоа направи стрелките на овој начин?

782
00:59:53,210 --> 00:59:58,420
[Бауден] Значи (* дрво) е Dereference еднаш, -> вредност

783
00:59:58,420 --> 01:00:05,960
се случува да ми даде на вредноста на јазол дека јас сум индиректно укажува на.

784
01:00:05,960 --> 01:00:11,980
Па јас исто така може да напише ** tree.value ако сакате тоа.

785
01:00:11,980 --> 01:00:18,490
Или работи.

786
01:00:18,490 --> 01:00:26,190
Ако тоа е случај, тогаш сакам да се јавам вметнете со вредност.

787
01:00:26,190 --> 01:00:32,590
И што е мојот обновено јазол ** ќе биде?

788
01:00:32,590 --> 01:00:39,440
Сакам да си одам од лево, па ** tree.left се случува да ми биде лево.

789
01:00:39,440 --> 01:00:41,900
И сакам го покажувачот во тој нешто

790
01:00:41,900 --> 01:00:44,930
така што ако левата завршува се на нула покажувач,

791
01:00:44,930 --> 01:00:48,360
Можам да го менувате за да се укаже на мојот нов јазол.

792
01:00:48,360 --> 01:00:51,460
>> И друг случај може да биде многу слични.

793
01:00:51,460 --> 01:00:55,600
Да, всушност се направи дека мојот троичен во моментов.

794
01:00:55,600 --> 01:01:04,480
Внесете вредност, ако вредноста <(** дрво). Вредност.

795
01:01:04,480 --> 01:01:11,040
Потоа сакаме да обновите нашата ** на лево,

796
01:01:11,040 --> 01:01:17,030
друго сакаме да обновите нашата ** десно.

797
01:01:17,030 --> 01:01:22,540
[Студентски] Дали тоа го добиете покажувач на покажувачот?

798
01:01:22,540 --> 01:01:30,940
[Бауден] Запомнете дека - ** tree.right е еден јазол ѕвезда.

799
01:01:30,940 --> 01:01:35,040
[Студент, неразбирливо] >> Да.

800
01:01:35,040 --> 01:01:41,140
** Tree.right е вака покажувачот или нешто.

801
01:01:41,140 --> 01:01:45,140
Па со преземање на покажувачот на тоа, што ми дава она што го сакате

802
01:01:45,140 --> 01:01:50,090
на покажувачот во тој тип.

803
01:01:50,090 --> 01:01:54,260
[Студентски] можеме да одиме одново зошто ние сме со користење на два покажувачи?

804
01:01:54,260 --> 01:01:58,220
[Бауден] Да. Значи - не можеш, а тоа решение пред

805
01:01:58,220 --> 01:02:04,540
е начин да се направи тоа без да правиш две насоки.

806
01:02:04,540 --> 01:02:08,740
Вие треба да бидат способни да го разберат со помош на два покажувачи,

807
01:02:08,740 --> 01:02:11,660
и ова е почиста решение.

808
01:02:11,660 --> 01:02:16,090
Исто така, забележи дека, што се случува ако ми дрво -

809
01:02:16,090 --> 01:02:24,480
она што се случува ако мојот корен беше нула? Што се случува ако го направам овој случај токму тука?

810
01:02:24,480 --> 01:02:30,540
Значи јазол * корен = NULL, вметнете 4 во & корен.

811
01:02:30,540 --> 01:02:35,110
Што е коренот ќе биде по тоа?

812
01:02:35,110 --> 01:02:37,470
[Студент, неразбирливо] >> Да.

813
01:02:37,470 --> 01:02:41,710
Корен вредност ќе биде 4.

814
01:02:41,710 --> 01:02:45,510
Корен лево ќе биде нула, корен право ќе биде нула.

815
01:02:45,510 --> 01:02:49,490
Во случај каде што не помине корен адреса,

816
01:02:49,490 --> 01:02:52,490
ние не би можеле да менувате корен.

817
01:02:52,490 --> 01:02:56,020
Во случај кога дрвото - каде што коренот беше нула,

818
01:02:56,020 --> 01:02:58,410
ние едноставно мораше да се врати лажни. Нема ништо што можеше да стори.

819
01:02:58,410 --> 01:03:01,520
Ние не можеме да вметнете јазол во празен дрво.

820
01:03:01,520 --> 01:03:06,810
Но сега можеме, ние само се направи празен дрво во еден јазол дрво.

821
01:03:06,810 --> 01:03:13,400
Што е обично очекуваниот начин на кој што би требало да работат.

822
01:03:13,400 --> 01:03:21,610
>> Понатаму, ова е значително пократок од

823
01:03:21,610 --> 01:03:26,240
исто така, следење на родител, и за да можете iterate долу сите на патот.

824
01:03:26,240 --> 01:03:30,140
Сега имам моите родители, а јас само имам родител право покажувачот на сеедно.

825
01:03:30,140 --> 01:03:35,640
Наместо тоа, ако ние го сторивме тоа iteratively, тоа би било истата идеја со време јамка.

826
01:03:35,640 --> 01:03:38,100
Но, наместо да се занимаваат со моите родители покажувач,

827
01:03:38,100 --> 01:03:40,600
наместо тековната ми покажувачот ќе биде нешто

828
01:03:40,600 --> 01:03:43,790
дека сум директно менување на точка за мојот нов јазол.

829
01:03:43,790 --> 01:03:46,090
Јас не треба да се занимаваат со тоа дали тоа е покажувајќи кон лево.

830
01:03:46,090 --> 01:03:48,810
Јас не треба да се занимаваат со тоа дали тоа е покажувајќи кон десно.

831
01:03:48,810 --> 01:04:00,860
Тоа е само што овој покажувачот е, јас одам да го поставите да се укаже на мојот нов јазол.

832
01:04:00,860 --> 01:04:05,740
Секој разбере како тоа функционира?

833
01:04:05,740 --> 01:04:09,460
Ако не зошто ние сакаме да го направи тоа на овој начин,

834
01:04:09,460 --> 01:04:14,920
но барем дека тоа функционира како решение?

835
01:04:14,920 --> 01:04:17,110
[Студентски] Каде да се вратиме вистина?

836
01:04:17,110 --> 01:04:21,550
[Бауден] Тоа е веројатно е во право тука.

837
01:04:21,550 --> 01:04:26,690
Ако ние правилно го вметнете, враќање вистина.

838
01:04:26,690 --> 01:04:32,010
Друго, овде ние ќе сакаат да се вратат она што вметнете враќа.

839
01:04:32,010 --> 01:04:35,950
>> И, што е посебно за овој рекурзивен функција?

840
01:04:35,950 --> 01:04:43,010
Тоа е опашката рекурзивна, па додека ние се компајлира со некои оптимизација,

841
01:04:43,010 --> 01:04:48,060
тоа ќе го препознае тоа и никогаш нема да добие магацинот претекување од ова,

842
01:04:48,060 --> 01:04:53,230
дури и ако нашите дрво има висина од 10.000 или 10 милиони евра.

843
01:04:53,230 --> 01:04:55,630
[Студент, неразбирливо]

844
01:04:55,630 --> 01:05:00,310
[Бауден] Мислам дека тоа го прави во цртичка - или она што оптимизација ниво

845
01:05:00,310 --> 01:05:03,820
е потребно за опашка рекурзија да бидат признати.

846
01:05:03,820 --> 01:05:09,350
Мислам дека тоа го признава - GCC и ѕвекот

847
01:05:09,350 --> 01:05:12,610
исто така, има различни значења за оптимизација нивоа.

848
01:05:12,610 --> 01:05:17,870
Сакам да кажам тоа е DashO 2, за сигурни дека ќе ја признае опашка рекурзија.

849
01:05:17,870 --> 01:05:27,880
Но ние - вие може да се создаде како пример Fibonocci или нешто.

850
01:05:27,880 --> 01:05:30,030
Тоа не е лесно да се тестираат со ова, затоа што е тешко да се изгради

851
01:05:30,030 --> 01:05:32,600
бинарен дрво кој е толку голем.

852
01:05:32,600 --> 01:05:37,140
Но да, мислам дека е DashO 2, кој

853
01:05:37,140 --> 01:05:40,580
ако компајлира со DashO 2, тоа ќе изгледа за опашка рекурзија

854
01:05:40,580 --> 01:05:54,030
и оптимизирате тоа.

855
01:05:54,030 --> 01:05:58,190
Да се ​​вратиме на - вметнете е буквално последната работа е потребна.

856
01:05:58,190 --> 01:06:04,900
Да се ​​вратиме на вметнете овде

857
01:06:04,900 --> 01:06:07,840
каде што ние ќе го стори истото идеја.

858
01:06:07,840 --> 01:06:14,340
Таа се уште ќе имаат мааната на не можејќи да целосно да се справи со

859
01:06:14,340 --> 01:06:17,940
кога коренот себе е нула, или минатото влез е нула,

860
01:06:17,940 --> 01:06:20,060
но наместо да се занимаваат со родителот покажувач,

861
01:06:20,060 --> 01:06:27,430
ајде да се применуваат истата логика на водење на покажувачи на покажувачи.

862
01:06:27,430 --> 01:06:35,580
Ако тука ние ги одржуваме нашите јазол ** мом,

863
01:06:35,580 --> 01:06:37,860
и ние не треба да ги пратите на правото повеќе,

864
01:06:37,860 --> 01:06:47,190
но јазол ** мом = & дрво.

865
01:06:47,190 --> 01:06:54,800
А сега нашата додека јамка ќе биде додека * мом не еднакви нула.

866
01:06:54,800 --> 01:07:00,270
Не треба да ги пратите на родителите повеќе.

867
01:07:00,270 --> 01:07:04,180
Не треба да ги пратите на лево и десно.

868
01:07:04,180 --> 01:07:10,190
И јас ќе го наречеме Temp, затоа што ние сме веќе користите Темп.

869
01:07:10,190 --> 01:07:17,200
Во ред. Значи, ако (вредност> * Temp),

870
01:07:17,200 --> 01:07:24,010
тогаш и (* Temp) -> десно

871
01:07:24,010 --> 01:07:29,250
друго Темп = (* Temp) -> лево.

872
01:07:29,250 --> 01:07:32,730
И сега, во овој момент, откако тоа додека јамка,

873
01:07:32,730 --> 01:07:36,380
Јас само го направи тоа затоа можеби е полесно да се размислува за iteratively од рекурзивно,

874
01:07:36,380 --> 01:07:39,010
но по ова додека јамка,

875
01:07:39,010 --> 01:07:43,820
* Температура е покажувачот сакаме да се промени.

876
01:07:43,820 --> 01:07:48,960
>> Пред имавме родител, и сакавме да се промени или родител лево или родител право,

877
01:07:48,960 --> 01:07:51,310
но ако сакате да го промените родител право,

878
01:07:51,310 --> 01:07:54,550
потоа * температура е родител во право, а ние може да го промени директно.

879
01:07:54,550 --> 01:08:05,860
Значи тука долу, можеме да направиме * Temp = newnode, и тоа е тоа.

880
01:08:05,860 --> 01:08:09,540
Значи известување, сите ние го сторивме во овој беше извади линии на код.

881
01:08:09,540 --> 01:08:14,770
Со цел да ги пратите на родителот во сето тоа е дополнителен напор.

882
01:08:14,770 --> 01:08:18,689
Еве, ако ние само да ги пратите на покажувачот на покажувачот,

883
01:08:18,689 --> 01:08:22,990
и ако сакаме да се ослободиме од сите овие големи загради сега,

884
01:08:22,990 --> 01:08:27,170
го направите да изгледа пократко.

885
01:08:27,170 --> 01:08:32,529
Ова сега е иста решение,

886
01:08:32,529 --> 01:08:38,210
но помалку линии на код.

887
01:08:38,210 --> 01:08:41,229
Откако ќе почнете да Признавајќи го ова како добро решение,

888
01:08:41,229 --> 01:08:43,529
тоа е, исто така, полесно да се причина за од како, добро,

889
01:08:43,529 --> 01:08:45,779
Зошто имам ова знаме во int нели?

890
01:08:45,779 --> 01:08:49,290
Што значи тоа? Ох, тоа е означувајќи дека

891
01:08:49,290 --> 01:08:51,370
секој пат кога одам десно, јас треба да го поставите,

892
01:08:51,370 --> 01:08:53,819
друго, ако одам лево јас треба да го поставите на нула.

893
01:08:53,819 --> 01:09:04,060
Еве, јас не треба да се причина за тоа, тоа е само полесно да се размислува за.

894
01:09:04,060 --> 01:09:06,710
Прашања?

895
01:09:06,710 --> 01:09:16,290
[Студент, неразбирливо] >> Да.

896
01:09:16,290 --> 01:09:23,359
Океј, па во последната трошка -

897
01:09:23,359 --> 01:09:28,080
Претпоставувам еден брз и лесен функција можеме да направиме е,

898
01:09:28,080 --> 01:09:34,910
let's - заедно, претпоставувам, се обиде да напише содржи функција

899
01:09:34,910 --> 01:09:38,899
кој не му е гајле дали тоа е бинарна пребарување дрво.

900
01:09:38,899 --> 01:09:43,770
Таа содржи функција треба да се врати вистинската

901
01:09:43,770 --> 01:09:58,330
ако било каде во оваа општа бинарно дрво е вредноста што го барате.

902
01:09:58,330 --> 01:10:02,520
Значи ајде прво да го направи тоа рекурзивно, а потоа ќе го направи тоа iteratively.

903
01:10:02,520 --> 01:10:07,300
Ние можеме да всушност само го прават тоа заедно, бидејќи ова ќе биде навистина краток.

904
01:10:07,300 --> 01:10:11,510
>> Што е Мој база случај ќе биде?

905
01:10:11,510 --> 01:10:13,890
[Студент, неразбирливо]

906
01:10:13,890 --> 01:10:18,230
[Бауден] Значи, ако (дрво == NULL), тогаш што?

907
01:10:18,230 --> 01:10:22,740
[Студентски] Врати се лажни.

908
01:10:22,740 --> 01:10:26,160
[Бауден] друго, добро, јас не треба на друго место.

909
01:10:26,160 --> 01:10:30,250
Ако ми беше друга база случај.

910
01:10:30,250 --> 01:10:32,450
[Студентски] дрвото вредност? >> Да.

911
01:10:32,450 --> 01:10:36,430
Значи, ако (дрво> вредноста == вредност.

912
01:10:36,430 --> 01:10:39,920
Забележете ние сме назад кон јазол * не, јазол ** а?

913
01:10:39,920 --> 01:10:42,990
Содржи никогаш не ќе треба да користите еден јазол **,

914
01:10:42,990 --> 01:10:45,480
бидејќи ние не се менува совети.

915
01:10:45,480 --> 01:10:50,540
Ние само им traversing.

916
01:10:50,540 --> 01:10:53,830
Ако тоа се случи, тогаш ние сакаме да се врати вистина.

917
01:10:53,830 --> 01:10:58,270
Друго сакаме да напречни деца.

918
01:10:58,270 --> 01:11:02,620
Па ние не може да се причина за тоа дали се на лево е помалку

919
01:11:02,620 --> 01:11:05,390
и сè на правото е поголема.

920
01:11:05,390 --> 01:11:09,590
Значи она што е нашата состојба ќе биде тука - или, што ќе правиме?

921
01:11:09,590 --> 01:11:11,840
[Студент, неразбирливо] >> Да.

922
01:11:11,840 --> 01:11:17,400
Врати содржи (вредност, дрво> лево)

923
01:11:17,400 --> 01:11:26,860
или содржи (вредност, дрво> десно). И тоа е тоа.

924
01:11:26,860 --> 01:11:29,080
И забележите дека некои краток спој евалуација,

925
01:11:29,080 --> 01:11:32,520
каде што ако ние се случува да се најде вредноста на левата дрво,

926
01:11:32,520 --> 01:11:36,820
ние никогаш не треба да се погледне во право дрво.

927
01:11:36,820 --> 01:11:40,430
Тоа е целата функција.

928
01:11:40,430 --> 01:11:43,690
Сега ајде да го сториме тоа iteratively,

929
01:11:43,690 --> 01:11:48,060
кој се случува да биде помалку убаво.

930
01:11:48,060 --> 01:11:54,750
Ние ќе се вообичаените почетокот на јазол * мом = дрво.

931
01:11:54,750 --> 01:12:03,250
Додека (мом! = NULL).

932
01:12:03,250 --> 01:12:08,600
Брзо одење за да ја видите проблем.

933
01:12:08,600 --> 01:12:12,250
Ако мом - овде, ако некогаш се пробие на ова,

934
01:12:12,250 --> 01:12:16,020
тогаш ние ја стартувате од работите да се погледне, па се врати лажни.

935
01:12:16,020 --> 01:12:24,810
Ако (мом-> вредноста == вредност), враќање вистина.

936
01:12:24,810 --> 01:12:32,910
Па сега, ние сме на место -

937
01:12:32,910 --> 01:12:36,250
не знаеме дали ние сакаме да одиме лево или десно.

938
01:12:36,250 --> 01:12:44,590
Така произволно, ајде да одиме лево.

939
01:12:44,590 --> 01:12:47,910
Сум очигледно работи во прашање каде што сум целосно напуштени сè -

940
01:12:47,910 --> 01:12:50,760
Јас ќе само некогаш се провери од левата страна на дрво.

941
01:12:50,760 --> 01:12:56,050
Јас никогаш не ќе ги провери нешто што е право дете на ништо.

942
01:12:56,050 --> 01:13:00,910
Како можам да го надминете овој?

943
01:13:00,910 --> 01:13:05,260
[Студентски] Вие треба да ги пратите на левицата и десницата во оџак.

944
01:13:05,260 --> 01:13:13,710
[Бауден] Да. Значи, да се направи тоа

945
01:13:13,710 --> 01:13:32,360
struct листа, јазол * n, а потоа јазол ** следно?

946
01:13:32,360 --> 01:13:40,240
Мислам дека работи добро.

947
01:13:40,240 --> 01:13:45,940
Ние сакаме да одиме во текот на лево, или let's - до тука.

948
01:13:45,940 --> 01:13:54,350
Struct листа листа =, тоа ќе започне

949
01:13:54,350 --> 01:13:58,170
надвор во тоа struct листа.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Значи тоа ќе биде нашата поврзани листа

951
01:14:04,040 --> 01:14:08,430
на subtrees дека имаме прескокнат во текот.

952
01:14:08,430 --> 01:14:13,800
Ние ќе се обидеме да напречни остави сега,

953
01:14:13,800 --> 01:14:17,870
но бидејќи ние неизбежно треба да се врати на правото,

954
01:14:17,870 --> 01:14:26,140
Ние ќе го задржи на десната страна во внатрешноста на нашите struct листа.

955
01:14:26,140 --> 01:14:32,620
Тогаш ќе имаме new_list или struct,

956
01:14:32,620 --> 01:14:41,080
struct листа *, new_list = Примерок (sizeof (листа)).

957
01:14:41,080 --> 01:14:44,920
Одам да се игнорира грешка-проверка на тоа, но ќе треба да се провери да се види дали тоа е нула.

958
01:14:44,920 --> 01:14:50,540
New_list јазол се случува да се укаже -

959
01:14:50,540 --> 01:14:56,890
О, тоа е зошто јас го сакав тука. Тоа се случува да се укаже на вториот struct листа.

960
01:14:56,890 --> 01:15:02,380
Тоа е само како поврзани листи работа.

961
01:15:02,380 --> 01:15:04,810
Ова е исто како int поврзани листа

962
01:15:04,810 --> 01:15:06,960
освен ние сме само замена int со јазол *.

963
01:15:06,960 --> 01:15:11,040
Тоа е иста.

964
01:15:11,040 --> 01:15:15,100
Значи new_list, вредноста на нашите new_list јазол,

965
01:15:15,100 --> 01:15:19,120
ќе биде мом-> десно.

966
01:15:19,120 --> 01:15:24,280
Вредноста на нашите new_list-> Следниот ќе биде нашата изворна листа,

967
01:15:24,280 --> 01:15:30,760
а потоа ние ќе се ажурира нашата листа да се укаже new_list.

968
01:15:30,760 --> 01:15:33,650
>> Сега ние треба некој вид на начин на влечење работи,

969
01:15:33,650 --> 01:15:37,020
како ние ја минал целиот левата поддрво.

970
01:15:37,020 --> 01:15:40,480
Сега ние треба да се повлече нешто надвор од неа,

971
01:15:40,480 --> 01:15:43,850
како мом е нула; ние не сакаме само да се врати лажни.

972
01:15:43,850 --> 01:15:50,370
Ние сакаме да сега се повлече надвор од нашата нова листа.

973
01:15:50,370 --> 01:15:53,690
А удобен начин за тоа - и, всушност, има повеќе начини за тоа.

974
01:15:53,690 --> 01:15:56,680
Секој има сугестија?

975
01:15:56,680 --> 01:15:58,790
Каде што треба да го направите тоа или како можам да го направите ова?

976
01:15:58,790 --> 01:16:08,010
Ние имаме само неколку минути, но било сугестија?

977
01:16:08,010 --> 01:16:14,750
Наместо - еден начин, наместо нашата состојба се додека,

978
01:16:14,750 --> 01:16:17,090
она што ние сме во моментов бараат во не е нула,

979
01:16:17,090 --> 01:16:22,340
наместо ние ќе продолжиме да се оди до нашата листа се е нула.

980
01:16:22,340 --> 01:16:25,680
Значи, ако нашата листа завршува се нула,

981
01:16:25,680 --> 01:16:30,680
тогаш имаме снема нешта да барате, за пребарување преку.

982
01:16:30,680 --> 01:16:39,860
Но, тоа значи дека првата работа во нашата листа е само ќе биде првиот јазол.

983
01:16:39,860 --> 01:16:49,730
Самиот првото нешто што ќе биде - ние веќе не треба да се види тоа.

984
01:16:49,730 --> 01:16:58,710
Значи листа-> n ќе биде наш дрво.

985
01:16:58,710 --> 01:17:02,860
листа-> Следниот ќе биде нула.

986
01:17:02,860 --> 01:17:07,580
И сега, додека листата не еднакви нула.

987
01:17:07,580 --> 01:17:11,610
Мом се случува да се извлече нешто од нашата листа.

988
01:17:11,610 --> 01:17:13,500
Значи мом ќе еднаков листа-> n.

989
01:17:13,500 --> 01:17:20,850
А потоа списокот ќе еднаков листа-> n, или листа-> следната.

990
01:17:20,850 --> 01:17:23,480
Значи, ако мом вредност е еднаква вредност.

991
01:17:23,480 --> 01:17:28,790
Сега можеме да го додадете и нашето право покажувач и нашите левата покажувачот

992
01:17:28,790 --> 01:17:32,900
додека тие не се ништовни.

993
01:17:32,900 --> 01:17:36,390
Тука долу, претпоставувам дека ние треба да го направиле тоа на прво место.

994
01:17:36,390 --> 01:17:44,080
Ако (мом-> право! = NULL)

995
01:17:44,080 --> 01:17:56,380
тогаш се случува да се вметне тој јазол во нашата листа.

996
01:17:56,380 --> 01:17:59,290
Ако (мом-> лево), ова е малку дополнителна работа, но тоа е во ред.

997
01:17:59,290 --> 01:18:02,690
Ако (мом-> лево! = NULL),

998
01:18:02,690 --> 01:18:14,310
и ние ќе го вметнете лево во нашиот поврзани листа,

999
01:18:14,310 --> 01:18:19,700
и дека треба да биде тоа.

1000
01:18:19,700 --> 01:18:22,670
Ние iterate - се додека имаме нешто во нашата листа,

1001
01:18:22,670 --> 01:18:26,640
имаме друг јазол да се погледне.

1002
01:18:26,640 --> 01:18:28,920
Значи гледаме дека јазол,

1003
01:18:28,920 --> 01:18:31,390
ние ја подигнеме нашата листа на следниот.

1004
01:18:31,390 --> 01:18:34,060
Ако тој јазол е вредноста што го барате, ние може да се врати вистина.

1005
01:18:34,060 --> 01:18:37,640
Друго вметнете нашите лево и десно subtrees,

1006
01:18:37,640 --> 01:18:40,510
додека тие не се нула, во нашата листа

1007
01:18:40,510 --> 01:18:43,120
така што ние неизбежно одат над нив.

1008
01:18:43,120 --> 01:18:45,160
Значи, ако тие не беа нула,

1009
01:18:45,160 --> 01:18:47,950
ако нашиот корен покажувачот посочи две работи,

1010
01:18:47,950 --> 01:18:51,670
тогаш прво се повлече нешто надвор така и нашата листа завршува се ништовни.

1011
01:18:51,670 --> 01:18:56,890
А потоа ќе стави две работи назад, па сега нашата листа е на големината 2.

1012
01:18:56,890 --> 01:19:00,030
Потоа ние ќе јамка назад и ние сме само ќе да се повлече,

1013
01:19:00,030 --> 01:19:04,250
да речеме, на левата покажувачот на нашите root јазол.

1014
01:19:04,250 --> 01:19:07,730
И тоа само ќе го задржи случува, ние ќе се заокружи looping над сè.

1015
01:19:07,730 --> 01:19:11,280
>> Забележете дека ова е значително посложен

1016
01:19:11,280 --> 01:19:14,160
во рекурзивен решение.

1017
01:19:14,160 --> 01:19:17,260
И јас сум изјави повеќе пати

1018
01:19:17,260 --> 01:19:25,120
дека рекурзивен решение обично има многу заедничко со повторната решение.

1019
01:19:25,120 --> 01:19:30,820
Еве ова е токму она што рекурзивен решение го прави.

1020
01:19:30,820 --> 01:19:36,740
Единствената промена е во тоа што наместо имплицитно користење на магацинот, програмата оџакот,

1021
01:19:36,740 --> 01:19:40,840
како начин на следење на она што јазли се уште треба да ја посетите,

1022
01:19:40,840 --> 01:19:45,430
сега ќе мора да експлицитно се користи поврзани листа.

1023
01:19:45,430 --> 01:19:49,070
Во двата случаи ќе се следење на она што јазол уште треба да се посети.

1024
01:19:49,070 --> 01:19:51,790
Во рекурзивен случај тоа е само полесно, бидејќи магацинот

1025
01:19:51,790 --> 01:19:57,100
се спроведува за вас, како на програмата оџак.

1026
01:19:57,100 --> 01:19:59,550
Забележете дека овој поврзани листа, тоа е оџакот.

1027
01:19:59,550 --> 01:20:01,580
Што и да се само да ги ставите на магацинот

1028
01:20:01,580 --> 01:20:09,960
е веднаш она што ние ќе треба да се повлече од оџакот да ја посетите следната.

1029
01:20:09,960 --> 01:20:14,380
Ние сме надвор од времето, но било какви прашања?

1030
01:20:14,380 --> 01:20:23,530
[Студент, неразбирливо]

1031
01:20:23,530 --> 01:20:27,790
[Бауден] Да. Значи, ако ние имаме поврзани листа,

1032
01:20:27,790 --> 01:20:30,150
сегашната се случува да се укаже на овој човек,

1033
01:20:30,150 --> 01:20:34,690
а сега ние сме само унапредување на нашата поврзани листа да се фокусираат на овој човек.

1034
01:20:34,690 --> 01:20:44,200
Ние сме traversing во текот на поврзани листа во таа линија.

1035
01:20:44,200 --> 01:20:51,200
И тогаш претпоставувам дека треба да се ослободи нашите поврзани листа и работи

1036
01:20:51,200 --> 01:20:53,880
еднаш пред да се врати лажни или вистинити, ние треба да се

1037
01:20:53,880 --> 01:20:57,360
iterate преку нашиот поврзани листа и секогаш тука долу, претпоставувам,

1038
01:20:57,360 --> 01:21:03,900
ако мом право не е еднаква, таа додаде, па сега ние сакаме да се ослободи

1039
01:21:03,900 --> 01:21:09,600
мом бидејќи, сепак, не можеме целосно да заборавите за листата? Да.

1040
01:21:09,600 --> 01:21:12,880
Значи тоа е она што сакате да го направите овде.

1041
01:21:12,880 --> 01:21:16,730
Каде е покажувачот?

1042
01:21:16,730 --> 01:21:23,320
Мом тогаш беше - сакаме на struct листа * 10 е еднакво на листата следната.

1043
01:21:23,320 --> 01:21:29,240
Слободен листа, листа = Temp.

1044
01:21:29,240 --> 01:21:32,820
И во случај кога ќе се вратиме точно, ние треба да iterate

1045
01:21:32,820 --> 01:21:37,050
текот на остатокот од нашите поврзани листа ослободување работи.

1046
01:21:37,050 --> 01:21:39,700
На убаво нешто за рекурзивен решение е ослободување работи

1047
01:21:39,700 --> 01:21:44,930
само значи пукање factorings надвор од магацинот што ќе се случи за вас.

1048
01:21:44,930 --> 01:21:50,720
Значи ние си отиде од нешто што е како 3 линии на хард-да-тинк-за код

1049
01:21:50,720 --> 01:21:57,520
на нешто што е значително многу повеќе хард-да-тинк-за линии на код.

1050
01:21:57,520 --> 01:22:00,620
Други прашања?

1051
01:22:00,620 --> 01:22:08,760
Во ред. Ние сме добро. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]