1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Часть 7: более комфортным]

2
00:00:02,770 --> 00:00:05,090
[Rob Боуден] [Harvard University]

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

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 на право 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
Я просто положил N.

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

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

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

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
и тогда вы не - вместо того, чтобы думать головой,

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
Использование шаблона ЬурейеЕ ниже,

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
ЬурейеЕ узла структуры и узлов. Да, все в порядке.

241
00:16:41,630 --> 00:16:44,270
Так что поле мы собираемся хотим в нашей узла?

242
00:16:44,270 --> 00:16:46,520
[Студент] Int, а затем два указателя?

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

244
00:16:49,700 --> 00:16:58,440
[Студент] Struct. >> Я должна увеличить масштаб Да, так что структура узла * ушел,

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
[Студент] Кто-то стук, пытаясь выбраться наружу.

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

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
чтобы убедиться, что Clang делает тоже самое.

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, NULL, NULL.

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
[Студент] Мне не нужно разыменовать это? >> Да.

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
[Студент, неразборчиво] корень будет 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, мы предлагаем для кодирования Хаффмана.

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

376
00:28:12,730 --> 00:28:20,520
деконструктор и «функции» для тех, деревья и то же самое для леса.

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

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
[Студент, неразборчиво] >> Да. Если таНос не удалось, он будет возвращать NULL.

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
[Боуден] Любое нулевое значение является ложным.

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.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
[Студент] структуры отличаются от других переменных, и другие переменные

426
00:32:27,320 --> 00:32:31,400
мусор ценностей; эти нули?

427
00:32:31,400 --> 00:32:36,220
[Боуден] Другие значения тоже. Таким образом, в х, х будет равна нулю.

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 содержит целочисленное значение ".

434
00:33:04,930 --> 00:33:08,340
Мы не собираемся делать BOOL содержит целочисленное значение.

435
00:33:08,340 --> 00:33:15,110
Наш прототип будет выглядеть

436
00:33:15,110 --> 00:33:22,380
BOOL содержит (целочисленное значение.

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
Вы можете сделать это либо итерационно или рекурсивно.

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

451
00:34:19,750 --> 00:34:24,130
Мы должны были бы иметь отдельную вспомогательную функцию, которая рекурсивно вниз поддеревья для нас.

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
>> [Студент] У меня есть решение итеративным. >> Ладно, итерационные.

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
А потом я просто петельные через время температура не равна нулю,

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
[Боуден] Хорошо. Так что кажется хорошим.

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
[Студент] Первая если это правда, не так ли?

485
00:37:18,550 --> 00:37:25,570
[Боуден] Да. То, как я всегда читал это, темп равно значение большее, чем временный значение,

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

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

501
00:38:38,200 --> 00:38:40,840
И дело здесь базу, где деревьев не равно NULL

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
[Студент] True? >> Да, потому что истинное ничего,

528
00:40:59,430 --> 00:41:04,990
соединены через ИЛИ - или истинный соединены через ИЛИ с чем обязательно верно.

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
Вернуться дерево не равна NULL и все это.

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

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
Так ложная операция AND с чем будет что?

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
потому что дерево-> значение разыменования NULL.

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
Если бы это был нулевым, это нарушило бы прежде, чем вы когда-либо разыменован указатель на первое место.

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

561
00:43:35,000 --> 00:43:40,770
>> [Боуден] Ленивые вычисления отдельная вещь.

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
Даже если вы попросите его написать - и FWRITE и 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 вставки (целочисленное значение).

599
00:46:10,470 --> 00:46:23,850
Мы собираемся изменить это BOOL вставки (целочисленное значение, узел * дерево).

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
Все, что вам нужно сделать, это итерации вниз по дереву, пока не дойдете до узла

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
[Студент] я делаю. >> Конечно.

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
Я петлю по дереву итеративно

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
Я разыменования температура, которая неизбежно нулевой.

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
Мы почти ожидал использовать 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
[Студент, неразборчиво]

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 будет просто узел * п = build_node (стоимость)

758
00:57:56,490 --> 00:58:07,300
Затем п, если п = 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
Вместо того чтобы сказать я, мы говорим * = дерево, если дерево *.

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
будет очень похож на все другие рекурсии мы делали.

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
Разыменования дважды звучало хорошо.

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
[Боуден] Таким образом, (* дерево) является разыменования один раз, -> значение

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
Также следить за родителями, и поэтому вы итерации до упора.

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
[Студент] Куда мы возвращаемся правда?

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
[Боуден] Я думаю, что он это делает на Dash - или то, что уровень оптимизации

845
01:05:00,310 --> 01:05:03,820
требуется для хвостовой рекурсии чтобы быть признанным.

846
01:05:03,820 --> 01:05:09,350
Я думаю, что он признает - GCC и Clang

847
01:05:09,350 --> 01:05:12,610
Также имеют разные значения для их уровня оптимизации.

848
01:05:12,610 --> 01:05:17,870
Я хочу сказать, что это Дашо 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
Но да, я думаю, что это Дашо 2,

853
01:05:37,140 --> 01:05:40,580
Если вы компилируете с Дашо 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
Хорошо. Так что, если (значение> * температура),

870
01:07:17,200 --> 01:07:24,010
то и (* температура) -> Право

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
Я только делаю это потому, может быть, легче думать о чем многократно рекурсивно,

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
Так давайте делать это рекурсивно, и тогда мы будем делать это повторно.

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
Мы просто через них.

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
Теперь давайте делать это многократно,

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
Структура списка узлов * 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
при этом структура списка.

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
Мы собираемся пройти осталось,

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
кроме мы просто заменив 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
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
Остальное вставить обе наши левые и правые поддеревья,

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
[Студент, неразборчиво]

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
Мы перемещения через связанный список в этой строке.

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
Таким образом, мы ушли от чего-то, что походит на 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]