1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Раздел 7: по-комфортно]

2
00:00:02,770 --> 00:00:05,090
[Роб Bowden] [Харвардския университет]

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
с изключение на структурата ще има две указатели.

15
00:00:47,910 --> 00:00:51,390
Има тройна дървета, които ще има три указатели,

16
00:00:51,390 --> 00:00:56,540
има N-ARY дървета, които просто трябва родово показалеца

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
съдържащи Нейт Любим номер, 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 "корен" на дървото.

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 на правото на три. "

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
Така че един нов възел с три и първоначално посочва нула.

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
Така че това, което е майка на три?

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
Потомците на корен възел ще бъде всичко в дървото,

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

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,

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
Какво не е наред, ако I - нека видим дали ще може да излезе със споразумението.

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 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, ще стигнем до три и все още можем да стигнем до 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
ако ляво и дясно са правилни, и след това обхождане там.

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 да бъде корен възел,

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
Така че продължавай, и сега ние казваме, нали, така че шест е по-малко от 7.

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

209
00:14:23,940 --> 00:14:27,340
[Student] левицата. >> Да.

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

211
00:14:33,340 --> 00:14:37,760
и след това не ... - вместо да се опитва да мисли в главата си,

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
[Student] Назад невярно? >> Да. Аз не намирам 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
Използвайки на стереотипния 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
Така че нека да поставим стереотипния тук,

240
00:16:30,380 --> 00:16:41,630
typedef структура възел и възел. Да, добре.

241
00:16:41,630 --> 00:16:44,270
Така че какви са полетата, които ние ще искате в нашия възел?

242
00:16:44,270 --> 00:16:46,520
[Student] Int и след това два указатели?

243
00:16:46,520 --> 00:16:49,700
>> Int стойност, две указатели? Как да напиша указатели?

244
00:16:49,700 --> 00:16:58,440
[Student] структура. >> Аз трябва да я увеличите инча Да, така структурата възел * оставил,

245
00:16:58,440 --> 00:17:01,320
и структура възел * прав.

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
Трябва всичко, което има, за да се определи тази рекурсивна структура.

250
00:17:25,000 --> 00:17:27,970
Добре, така че това, което нашето дърво ще изглежда.

251
00:17:27,970 --> 00:17:37,670
Ако сме направили тройна дърво, а след това може да изглежда като възел В1, В2, структура възел * b3,

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
[Student] Някой чука, опитвайки се да се измъкне.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Всеки комфортно с тяхното дърво строителство?

273
00:20:13,100 --> 00:20:15,520
[Student] Разбира се. Това не е направено. >> Всичко е наред. Ние можем само да довърша -

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
[Student] Когато дефинирате структурата, са неща, като инициализира с нещо?

279
00:20:44,410 --> 00:20:47,160
[Боудън, бр. >> Добре. Така че ще трябва да се инициализира

280
00:20:47,160 --> 00:20:50,450
[Bowden] Не Когато дефинирате, или когато обяви структура,

281
00:20:50,450 --> 00:20:55,600
не се инициализира по подразбиране, това е просто хареса, ако Вие декларирате, вътр.

282
00:20:55,600 --> 00:20:59,020
Това е точно същото нещо. Това е като всяка от отделните области

283
00:20:59,020 --> 00:21:04,460
може да има боклук стойност в него. >> И това е възможно да се определят - или да обяви структура

284
00:21:04,460 --> 00:21:07,740
начин, че да ги инициализира?

285
00:21:07,740 --> 00:21:13,200
[Bowden Да. Така че, синтаксис пряк път инициализация

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
би било девет, нула, нула.

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
всъщност трябва да знаят реда на структурата,

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 + + е надмножество на C.

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
но вие може просто да се каже, Чар * х = каквото изчистване,

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
Чар *, изчистване, каквото и да е, да се хвърли на знак *.

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
[Student] Нямам нужда да го сочен? >> Да.

324
00:23:52,170 --> 00:23:55,110
Не забравяйте, че стрелката има мълчаливо и сочен,

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

326
00:23:58,230 --> 00:24:04,300
искате да използвате. да се доберат до вътрешността на областта на структурата.

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
Всички стрелка средства, сочен това, сега съм на структура, и мога да получа тази област.

331
00:24:24,600 --> 00:24:28,040
Или се полето пряко или сочен и да получите областта -

332
00:24:28,040 --> 00:24:30,380
Предполагам, че това трябва да бъде стойност.

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

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
[Student, неразбираем] корен ще да бъде 7.

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

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, ние предлагаме за Huffman кодиране.

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

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

377
00:28:20,520 --> 00:28:22,570
>> Така че тук ние ще имат функция за инициализация

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.

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
Така че сега можем само да се обадя, че за да се изгради възел с определена стойност и нулеви указатели.

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
[Student, неразбираем] >> Да. Ако изчистване се провали, ще се върне празно.

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
[Student] е фалшива равна на нула, както и?

403
00:30:46,680 --> 00:30:51,290
[Bowden Всяко нулева стойност е фалшива.

404
00:30:51,290 --> 00:30:53,920
Така че нищожна е с нулева стойност.

405
00:30:53,920 --> 00:30:56,780
Нулата е нулева стойност. False е нулева стойност.

406
00:30:56,780 --> 00:31:02,130
Any - почти единствените две нулеви стойности са нула и нула,

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.value е нула,

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

423
00:32:14,260 --> 00:32:21,070
Така че, тъй като тя е структура, всички полета на структурата ще бъде нулеви стойности.

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
[Bowden] Или първоначалната стойност или нула.

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
с прототип на булев съдържа INT стойност. "

434
00:33:04,930 --> 00:33:08,340
Ние няма да го булев съдържа INT стойност.

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

436
00:33:15,110 --> 00:33:22,380
булев съдържа (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
може би ще искате да ФОРМАТ или нещо.

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
като има предвид, че съдържа пет корена трябва да се върне фалшиви.

445
00:33:59,390 --> 00:34:02,690
Така че да се второ неговото прилагане.

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

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 поддървета.

451
00:34:19,750 --> 00:34:24,130
Ние би трябвало да има отделна функция помощник, че recurses поддървета за нас.

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
Сега можем да самоизвиква по-лесно.

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
>> [Student] Имам един повтарящ решение. >> Добре, повтарящ се.

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
[Student] Разбира се. Така че аз временно променлива, за да получите първата възел на дървото.

462
00:35:25,780 --> 00:35:28,330
И тогава аз просто препредаден докато темп не е равно на нула,

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
след това той се връща след излизането на цикъла и връща.

469
00:35:47,330 --> 00:35:52,190
[Bowden Добре. Така че изглежда добре.

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
О, това ще да отида малко продълговата.

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
[Student] Първият от тях е, ако е вярно, нали?

485
00:37:18,550 --> 00:37:25,570
[Bowden Да. Начинът, по който винаги съм го прочете, температура се равнява на стойност, по-голяма от темп стойност,

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
[Student] Разбира се. Така че ние сме като се уверите, че дървото не е празен първо,

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
Връщане вярно, ако е така, и ако ние не самоизвиква наляво или надясно.

498
00:38:23,740 --> 00:38:25,970
Това звучи ли подходящо? >> Аха. (Споразумение)

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
Това става няколко линии, добре, увеличени в него е.

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
Ако стойността е по-малко от дърво стойност, ние искаме да самоизвиква на дървото в ляво,

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

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
[Student] True? >> Да, защото важи и за всичко,

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
Дори няма да самоизвиква допълнително съдържа установяване на ред.

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
[Студентски False. >> Да. Това е другата половина от късо съединение оценка,

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
Вместо това състояние, това никога няма да Seg вина

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

557
00:43:21,220 --> 00:43:24,000
Е, предполагам, че ако си дърво е напълно невалидни показалеца, тя все още може да Seg вина,

558
00:43:24,000 --> 00:43:26,620
но не може да Seg виновен, ако дървото е нищожна.

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
>> [Bowden] Мързел оценка е нещо отделно.

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
Така че точно сега е булев вложка (INT стойност).

599
00:46:10,470 --> 00:46:23,850
Отиваме да се промени, че да булев вложка (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
Например, ако вмъкна една, а след това аз неизбежно ще се поставите един -

611
00:47:18,640 --> 00:47:21,820
Ще промените в черно - Ще поставите 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
Всичко, което трябва да направите, е да превъртите надолу по дървото, докато не стигнем до възела

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
Така обхождане на дървото, да отбележа листа на нов възел.

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
[Student правя. >> Разбира се.

633
00:49:05,480 --> 00:49:09,200
[Student, неразбираем]

634
00:49:09,200 --> 00:49:14,390
[Other студент, неразбираем]

635
00:49:14,390 --> 00:49:18,330
[Bowden] оценявам. Добре. Искате ли да обясни?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Тъй като ние знаем, че сме били вмъкване

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

638
00:49:24,060 --> 00:49:28,070
Препредаден дървото итеративно

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
[Bowden Добре, така че не виждам един въпрос тук.

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
Сочен темп, което е неизбежно нула.

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
Ако стойността е по-голяма от каквото TEMP = темп право.

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

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
Така че родител ще бъде температура, а след това се преместя темп надолу.

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
1/2 очаква можете да използвате 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
Това, което искам да направя, е да манипулира това показалеца, за да посоча да не нула.

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
Node * корен = 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
[Student, неразбираем]

746
00:56:55,030 --> 00:57:00,000
[Bowden Да. Така че, ако (* дърво == 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
[Bowden] Така че не забравяйте, че аз съм в момента -

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

776
00:59:31,260 --> 00:59:34,140
[Bowden] Да, точно тук, нека кажем, че тази зелена стрелка

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
Сочен два пъти звучеше добре.

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

781
00:59:51,010 --> 00:59:53,210
[Student] и сочен веднъж, и след това направете стрелката по този начин?

782
00:59:53,210 --> 00:59:58,420
[Bowden] (* дърво) е сочен веднъж -> стойност

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
[Student] ли това, че се показалеца на показалеца?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Не забравяйте, че - ** tree.right е възел звезда.

799
01:01:30,940 --> 01:01:35,040
[Student, неразбираем] >> Да.

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
[Student] Може да отидем отново защо ние използваме двете указатели?

804
01:01:54,260 --> 01:01:58,220
[Bowden Да. Така че - не, можете и това решение пред

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, поставете четири в & корен.

811
01:02:30,540 --> 01:02:35,110
Какво е корен ще бъде след това?

812
01:02:35,110 --> 01:02:37,470
[Student, неразбираем] >> Да.

813
01:02:37,470 --> 01:02:41,710
Root стойност ще бъде 4.

814
01:02:41,710 --> 01:02:45,510
Root ляво ще бъде нула, корен правото ще бъде нула.

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
следене на родителя, и така да превъртите надолу по целия път.

824
01:03:26,240 --> 01:03:30,140
Сега имам родителите ми, а аз просто имам показалеца майка право на каквото.

825
01:03:30,140 --> 01:03:35,640
Вместо това, ако ние направихме това итеративно, че ще бъде една и съща идея с линия, докато.

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
[Student] Къде се върнем вярно ли е?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Това е може би точно тук.

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
[Student, неразбираем]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Мисля, че това го прави най-Dash - или какво оптимизация ниво

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
И аз ще го наречем температура, защото ние сме вече използват темп.

869
01:07:10,190 --> 01:07:17,200
Добре. Така че, ако (стойност * Temp),

870
01:07:17,200 --> 01:07:24,010
& (* ТЕМП) -> дясно

871
01:07:24,010 --> 01:07:29,250
друго TEMP = & (* Temp) -> оставяли.

872
01:07:29,250 --> 01:07:32,730
И сега, в този момент, след това, докато контур,

873
01:07:32,730 --> 01:07:36,380
Само това, защото може би е по-лесно да се мисли за итеративно от рекурсивно

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
[Student, неразбираем] >> Да.

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
Така че нека първо го направи рекурсивно и след това ще го направим итеративно.

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
[Student, неразбираем]

906
01:10:13,890 --> 01:10:18,230
Bowden] Така че, ако (дърво == NULL), тогава какво?

907
01:10:18,230 --> 01:10:22,740
[Student] връщане фалшиви.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Иначе, добре, аз не се нуждаят от друго.

909
01:10:26,160 --> 01:10:30,250
Ако ми беше друг случай база.

910
01:10:30,250 --> 01:10:32,450
Студентски] Tree стойност? >> Да.

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
Ние просто ги пресичат.

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
[Student, неразбираем] >> Да.

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
Сега нека го направим итеративно,

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
[Student] Трябва да следите на ляво и дясно в комин.

944
01:13:05,260 --> 01:13:13,710
[Bowden Да. Така че нека да го направи

945
01:13:13,710 --> 01:13:32,360
структура на списък, възел * 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
Структура = Списък, тя ще започне

949
01:13:54,350 --> 01:13:58,170
в тази структура списък.

950
01:13:58,170 --> 01:14:04,040
* Списък = NULL. Така че това ще бъде нашата свързан списък

951
01:14:04,040 --> 01:14:08,430
поддървета, че сме прескачат.

952
01:14:08,430 --> 01:14:13,800
Ние ще Traverse останало,

953
01:14:13,800 --> 01:14:17,870
но тъй като ние неизбежно трябва да се върне в правото,

954
01:14:17,870 --> 01:14:26,140
Ние ще продължим да дясната страна вътрешната структура на нашия списък.

955
01:14:26,140 --> 01:14:32,620
Тогава ще имаме new_list или структура,

956
01:14:32,620 --> 01:14:41,080
структура на списък *, 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
О, това е защо аз го исках тук. Това ще да сочи към втори списък структура.

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
освен ние просто замяна на цяло число възел *.

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
Cur се ще да покажете нещо от нашия списък.

988
01:17:11,610 --> 01:17:13,500
Така тек на равно списък->.

989
01:17:13,500 --> 01:17:20,850
И тогава списък на равно списък-> или списък-> следващия.

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
Ние обхождане - толкова дълго, колкото ние имаме нещо в нашия списък,

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
Else поставете двете ни лявото и дясното поддървета,

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
нека кажем, лявата показалеца на нашата коренът.

1014
01:19:04,250 --> 01:19:07,730
И това просто ще запази случва, ние ще свършим лупинг над всичко.

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
[Student, неразбираем]

1031
01:20:23,530 --> 01:20:27,790
[Bowden Да. Така че, ако ние имаме свързан списък,

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
Преминаващи над свързан списък, в този ред.

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
обхождане свързани нашия списък и винаги тук, предполагам,

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
Cur тогава - ние искаме структура списък * 10 е равно на списъка до.

1043
01:21:23,320 --> 01:21:29,240
Безплатно списък, списък = темп.

1044
01:21:29,240 --> 01:21:32,820
И в случаите, когато се върнем вярно, ние се нуждаем, за да превъртите

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
Така че ние сме отишли ​​от нещо, което е като три линии е трудно да се мисли за код

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
Добре. Ние сме добре. Чао!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]