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

2
00:00:02,500 --> 00:00:04,890
[Nate Хардисон] [Harvard University]

3
00:00:04,890 --> 00:00:07,000
[Это CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Добро пожаловать в раздел 7.

5
00:00:09,080 --> 00:00:11,330
Благодаря ураган Sandy,

6
00:00:11,330 --> 00:00:13,440
вместо того нормального сечения на этой неделе,

7
00:00:13,440 --> 00:00:17,650
Мы делаем это проходной, через раздел вопросов.

8
00:00:17,650 --> 00:00:22,830
Я собираюсь быть следующие Наряду с проблемой Set 6 Спецификация,

9
00:00:22,830 --> 00:00:25,650
и переживает все вопросы в

10
00:00:25,650 --> 00:00:27,770
Раздел раздела Вопросы.

11
00:00:27,770 --> 00:00:30,940
Если есть какие-либо вопросы,

12
00:00:30,940 --> 00:00:32,960
пожалуйста, напишите их на CS50 обсудить.

13
00:00:32,960 --> 00:00:35,480
>> Хорошо. Давайте начнем.

14
00:00:35,480 --> 00:00:40,780
Прямо сейчас я смотрю на стр. 3 Спецификация поставленной задачи.

15
00:00:40,780 --> 00:00:44,110
Мы идем к первому начать разговор о бинарных деревьев

16
00:00:44,110 --> 00:00:47,850
С тех есть много, имеющие отношение к проблеме набора на этой неделе -

17
00:00:47,850 --> 00:00:49,950
Кодирование Хаффмана дерева.

18
00:00:49,950 --> 00:00:55,000
Один из самых первых структур данных мы говорили о на CS50 был массива.

19
00:00:55,000 --> 00:01:00,170
Помните, что массив представляет собой последовательность элементов -

20
00:01:00,170 --> 00:01:04,019
Все же типа - хранятся рядом друг с другом в памяти.

21
00:01:04,019 --> 00:01:14,420
Если у меня есть массив целых чисел, что я могу сделать с помощью этой коробки-числа-целые стиль -

22
00:01:14,420 --> 00:01:20,290
Скажем, у меня есть 5 в первом поле, у меня 7 во второй,

23
00:01:20,290 --> 00:01:27,760
то у меня есть 8, 10, и 20 в конечном поле.

24
00:01:27,760 --> 00:01:33,000
Помните, что два действительно хороших вещей об этом массиве

25
00:01:33,000 --> 00:01:38,800
в том, что у нас есть эта постоянная времени доступ к любой конкретный элемент

26
00:01:38,800 --> 00:01:40,500
 в массиве, если мы знаем его индекс.

27
00:01:40,500 --> 00:01:44,670
Например, если я хочу, чтобы захватить третий элемент массива -

28
00:01:44,670 --> 00:01:47,870
с индексом 2, используя нашу с нуля системы -

29
00:01:47,870 --> 00:01:52,220
Я буквально только что нужно сделать простой математический расчет,

30
00:01:52,220 --> 00:01:56,170
прыгать на эту должность в массиве,

31
00:01:56,170 --> 00:01:57,840
вытащите 8, который хранится там,

32
00:01:57,840 --> 00:01:59,260
и я хорошо идти.

33
00:01:59,260 --> 00:02:03,350
>> Один из плохих вещей об этом массива - о которых мы говорили

34
00:02:03,350 --> 00:02:05,010
Когда мы обсуждали связанные списки -

35
00:02:05,010 --> 00:02:09,120
является то, что если я хочу, чтобы вставить элемент в этом массиве,

36
00:02:09,120 --> 00:02:11,090
Я собираюсь сделать некоторое перемещение вокруг.

37
00:02:11,090 --> 00:02:12,940
Например, этот массив прямо здесь

38
00:02:12,940 --> 00:02:16,850
является в определенном порядке - отсортированы в порядке возрастания -

39
00:02:16,850 --> 00:02:19,440
5, потом 7, потом 8, потом 10, а затем 20 -

40
00:02:19,440 --> 00:02:23,100
но если я хочу, чтобы вставить номер 9 в этом массиве,

41
00:02:23,100 --> 00:02:27,460
Я хочу, чтобы перенести некоторые элементы для того, чтобы освободить место.

42
00:02:27,460 --> 00:02:30,440
Мы можем сделать это здесь.

43
00:02:30,440 --> 00:02:35,650
Я собираюсь должны двигаться 5, 7, а затем 8;

44
00:02:35,650 --> 00:02:38,720
создать зазор, где я могу поставить 9,

45
00:02:38,720 --> 00:02:45,910
, а затем 10 и 20 может пойти в праве 9.

46
00:02:45,910 --> 00:02:49,450
Это своего рода боли, потому что в худшем случае -

47
00:02:49,450 --> 00:02:54,350
когда мы того, чтобы вставить либо в начале, либо в конце

48
00:02:54,350 --> 00:02:56,040
массива, в зависимости от того, как мы смещения -

49
00:02:56,040 --> 00:02:58,850
Мы могли бы в конечном итоге того, чтобы сдвинуть все элементы

50
00:02:58,850 --> 00:03:00,750
что мы в настоящее время хранение в массиве.

51
00:03:00,750 --> 00:03:03,810
>> Итак, что был способ обойти это?

52
00:03:03,810 --> 00:03:09,260
Способ обойти это был пойти в наш связанного списка метод, где -

53
00:03:09,260 --> 00:03:19,820
вместо хранения элементов 5, 7, 8, 10 и 20 все рядом друг с другом в памяти -

54
00:03:19,820 --> 00:03:25,630
Вместо того, что мы делали, было хранить их вида, где бы мы хотели, чтобы сохранить их

55
00:03:25,630 --> 00:03:32,470
В этих связанный список узлов, которые я рисую здесь, вроде специальных.

56
00:03:32,470 --> 00:03:42,060
И тогда мы соединили их вместе, используя эти следующие указатели.

57
00:03:42,060 --> 00:03:44,370
Я могу есть указатель от 5 до 7,

58
00:03:44,370 --> 00:03:46,420
Указатель от 7 до 8,

59
00:03:46,420 --> 00:03:47,770
Указатель от 8 до 10,

60
00:03:47,770 --> 00:03:51,220
И, наконец, указатель от 10 до 20,

61
00:03:51,220 --> 00:03:54,880
, а затем нулевым указателем на 20 о том, что там ничего не осталось.

62
00:03:54,880 --> 00:03:59,690
Компромисс, что мы имеем здесь

63
00:03:59,690 --> 00:04:05,360
является то, что теперь, если мы хотим, чтобы вставить номер 9 в нашей отсортированный список,

64
00:04:05,360 --> 00:04:08,270
все, что нам нужно сделать, это создать новый узел с 9,

65
00:04:08,270 --> 00:04:12,290
подключить его к точке в нужное место,

66
00:04:12,290 --> 00:04:20,630
, а затем повторно провода от 8 до точки до 9.

67
00:04:20,630 --> 00:04:25,660
Это довольно быстро, предполагая, что мы точно знаем, где мы хотим, чтобы вставить 9.

68
00:04:25,660 --> 00:04:32,610
Но компромисс в обмен на это, что мы теперь потеряли постоянное время доступа

69
00:04:32,610 --> 00:04:36,230
любой конкретный элемент в нашей структуре данных.

70
00:04:36,230 --> 00:04:40,950
Например, если я хочу найти четвертый элемент в этой связанного списка,

71
00:04:40,950 --> 00:04:43,510
Я собираюсь иметь, чтобы начать в самом начале списка

72
00:04:43,510 --> 00:04:48,930
и работает свой путь через счета узла-на-узле, пока не найду четвертый.

73
00:04:48,930 --> 00:04:55,870
>> Для того чтобы получить более широкий доступ производительность, чем связанный список -

74
00:04:55,870 --> 00:04:59,360
но и сохранить некоторые из преимуществ, которые у нас были

75
00:04:59,360 --> 00:05:01,800
В условиях введения времени от связанного списка -

76
00:05:01,800 --> 00:05:05,750
бинарное дерево будет необходимо использовать немного больше памяти.

77
00:05:05,750 --> 00:05:11,460
В частности, вместо того, чтобы просто иметь один указатель в бинарном дереве узлов -

78
00:05:11,460 --> 00:05:13,350
как связанный список узлов делает -

79
00:05:13,350 --> 00:05:16,950
Мы собираемся добавить второй указатель на двоичный узла дерева.

80
00:05:16,950 --> 00:05:19,950
Вместо того, чтобы просто иметь один указатель на следующий элемент,

81
00:05:19,950 --> 00:05:24,420
мы будем иметь указатель на левый ребенка и право ребенка.

82
00:05:24,420 --> 00:05:26,560
>> Давайте нарисуем картинку, чтобы посмотреть, что на самом деле выглядит.

83
00:05:26,560 --> 00:05:31,350
Опять же, я собираюсь использовать эти коробки и стрелы.

84
00:05:31,350 --> 00:05:37,150
Бинарный узел дерева будет начать с простой коробке.

85
00:05:37,150 --> 00:05:40,940
Это будет иметь место для значения,

86
00:05:40,940 --> 00:05:47,280
а затем он также будет иметь пространство для левого ребенка и право ребенка.

87
00:05:47,280 --> 00:05:49,280
Я буду называть их здесь.

88
00:05:49,280 --> 00:05:57,560
Мы собираемся у левая ребенка, и тогда мы будем иметь право ребенка.

89
00:05:57,560 --> 00:05:59,920
Есть много различных способов сделать это.

90
00:05:59,920 --> 00:06:02,050
Иногда для пространства и удобства,

91
00:06:02,050 --> 00:06:06,460
Я на самом деле сделать это, как я делаю здесь на дне

92
00:06:06,460 --> 00:06:10,910
где я собираюсь иметь значение в верхней части,

93
00:06:10,910 --> 00:06:14,060
, а затем правую ребенка на правой нижней,

94
00:06:14,060 --> 00:06:16,060
и левой ребенка на левой нижней.

95
00:06:16,060 --> 00:06:20,250
Возвращаясь к этой вершине диаграммы,

96
00:06:20,250 --> 00:06:22,560
у нас есть значение на самом верху,

97
00:06:22,560 --> 00:06:25,560
Затем у нас есть левый указатель ребенка, и тогда мы имеем право ребенку указатель.

98
00:06:25,560 --> 00:06:30,110
>> В спецификации поставленной задачи,

99
00:06:30,110 --> 00:06:33,110
мы говорим о разработке узла, который имеет значение 7,

100
00:06:33,110 --> 00:06:39,750
, а затем левую ребенка указатель, который является пустым, и права ребенка-указатель, который является нулевым.

101
00:06:39,750 --> 00:06:46,040
Мы можем либо написать капитала NULL в пространстве для

102
00:06:46,040 --> 00:06:51,610
как левой ребенка и право ребенка, или мы можем сделать это косая черта

103
00:06:51,610 --> 00:06:53,750
в каждом из коробки, чтобы указать, что это нулевой.

104
00:06:53,750 --> 00:06:57,560
Я собираюсь сделать это просто, потому что это проще.

105
00:06:57,560 --> 00:07:03,700
То, что вы видите здесь два способа построения диаграмм очень простой узел двоичного дерева

106
00:07:03,700 --> 00:07:07,960
где у нас есть значение 7 и нулевых указателей ребенка.

107
00:07:07,960 --> 00:07:15,220
>> Вторая часть нашей спецификации переговоры о том, как со связанными списками -

108
00:07:15,220 --> 00:07:18,270
Помните, мы только должны были держаться за первый элемент в списке

109
00:07:18,270 --> 00:07:20,270
вспомнить весь список -

110
00:07:20,270 --> 00:07:26,140
и аналогично, с бинарным деревом, мы только должны держать на одного указателя на дереве

111
00:07:26,140 --> 00:07:31,120
В целях сохранения контроля над всей структурой данных.

112
00:07:31,120 --> 00:07:36,150
Этот специальный элемент дерева называется корневым узлом дерева.

113
00:07:36,150 --> 00:07:43,360
Например, если этот узел - это узел, содержащий значение 7

114
00:07:43,360 --> 00:07:45,500
с нулевой левой и правой ребенку указатели -

115
00:07:45,500 --> 00:07:47,360
были единственной ценностью в нашем дереве,

116
00:07:47,360 --> 00:07:50,390
то это будет нашим корневым узлом.

117
00:07:50,390 --> 00:07:52,240
Это самое начало нашего дерева.

118
00:07:52,240 --> 00:07:58,530
Мы можем увидеть это немного яснее, как только мы начнем добавлять дополнительные узлы к нашему дереву.

119
00:07:58,530 --> 00:08:01,510
Позвольте мне подтянуть новую страницу.

120
00:08:01,510 --> 00:08:05,000
>> Теперь мы будем рисовать дерево, которое имеет 7 на корню,

121
00:08:05,000 --> 00:08:10,920
и 3 внутренней стороне левого ребенка, и 9 в правом ребенка.

122
00:08:10,920 --> 00:08:13,500
Опять же, это довольно просто.

123
00:08:13,500 --> 00:08:26,510
У нас есть 7, нарисовать узел 3, узел 9,

124
00:08:26,510 --> 00:08:32,150
и я собираюсь установить левый указатель ребенка от 7 до указывают на узел, содержащий 3,

125
00:08:32,150 --> 00:08:37,850
и право ребенка указатель узел, содержащий от 7 до узел, содержащий 9.

126
00:08:37,850 --> 00:08:42,419
Теперь, так как 3 и 9 не имеют детей,

127
00:08:42,419 --> 00:08:48,500
мы собираемся установить все их указатели ребенка, являются недействительными.

128
00:08:48,500 --> 00:08:56,060
Здесь корень нашего дерева соответствует узел, содержащий номер 7.

129
00:08:56,060 --> 00:09:02,440
Вы можете видеть, что если все мы имеем указатель на корневой узел,

130
00:09:02,440 --> 00:09:07,330
мы можем пройти через наше дерево и доступ как дочерние узлы -

131
00:09:07,330 --> 00:09:10,630
как 3 и 9.

132
00:09:10,630 --> 00:09:14,820
Не нужно сохранить указатели на каждом узле дерева.

133
00:09:14,820 --> 00:09:22,080
Хорошо. Теперь мы собираемся добавить еще один узел к этой схеме.

134
00:09:22,080 --> 00:09:25,370
Мы собираемся добавить узел, содержащий 6,

135
00:09:25,370 --> 00:09:34,140
и мы собираемся добавить его в качестве правого потомка узла, содержащего 3.

136
00:09:34,140 --> 00:09:41,850
Чтобы сделать это, я собираюсь стереть эту нулевого указателя в 3-узле

137
00:09:41,850 --> 00:09:47,750
и подключить его к указывала на узел, содержащий 6. Хорошо.

138
00:09:47,750 --> 00:09:53,800
>> На данный момент, давайте перейдем немного терминологии.

139
00:09:53,800 --> 00:09:58,230
Для начала, причина того, что это называется бинарное дерево, в частности,

140
00:09:58,230 --> 00:10:00,460
является то, что она имеет два указателя ребенка.

141
00:10:00,460 --> 00:10:06,020
Есть и другие виды деревьев, которые имеют больше указателей ребенка.

142
00:10:06,020 --> 00:10:10,930
В частности, вы сделали "попробовать" в проблеме Set 5.

143
00:10:10,930 --> 00:10:19,310
Вы заметите, что в этой попытке, у вас было 27 различных указателей на разные дети -

144
00:10:19,310 --> 00:10:22,410
по одному для каждой из 26 букв английского алфавита,

145
00:10:22,410 --> 00:10:25,410
, а затем 27-й по апострофа -

146
00:10:25,410 --> 00:10:28,900
так, что похож на тип дерева.

147
00:10:28,900 --> 00:10:34,070
Но здесь, так как это двоичный, у нас есть только два указателя ребенка.

148
00:10:34,070 --> 00:10:37,880
>> В дополнение к этой корневой узел, что мы говорили о том,

149
00:10:37,880 --> 00:10:41,470
Мы также бросали вокруг этого термина "ребенок".

150
00:10:41,470 --> 00:10:44,470
Что это значит для одного узла, чтобы быть потомком другого узла?

151
00:10:44,470 --> 00:10:54,060
Это буквально означает, что ребенок узел является потомком другого узла

152
00:10:54,060 --> 00:10:58,760
если другой узел имеет одну из его дочерних указатели установлены, чтобы указать на этом узле.

153
00:10:58,760 --> 00:11:01,230
Чтобы поставить это в более конкретных терминах,

154
00:11:01,230 --> 00:11:11,170
если 3, указал на одного ребенка указатели 7, затем 3 является дочерним 7.

155
00:11:11,170 --> 00:11:14,510
Если бы мы могли понять, что дети до 7 лет -

156
00:11:14,510 --> 00:11:18,510
Ну, мы видим, что 7 имеет указатель на 3 и указатель на 9,

157
00:11:18,510 --> 00:11:22,190
поэтому 9 и 3 детей 7.

158
00:11:22,190 --> 00:11:26,650
Девять детей нет, потому что его указатели ребенка являются недействительными,

159
00:11:26,650 --> 00:11:30,940
и 3 имеет только одного ребенка, 6.

160
00:11:30,940 --> 00:11:37,430
Шесть также не имеет детей, потому что оба его указатели являются недействительными, которую мы будем рисовать прямо сейчас.

161
00:11:37,430 --> 00:11:45,010
>> Кроме того, мы также говорим о родителях конкретного узла,

162
00:11:45,010 --> 00:11:51,100
и это, как и следовало ожидать, обратный этого ребенка описания.

163
00:11:51,100 --> 00:11:58,620
Каждый узел имеет только одного родителя - вместо двух, как вы могли бы ожидать с людьми.

164
00:11:58,620 --> 00:12:03,390
Например, родитель 3, 7.

165
00:12:03,390 --> 00:12:10,800
Родитель 9 также 7 и родителей 6, 3. Не так много к нему.

166
00:12:10,800 --> 00:12:15,720
У нас также есть условия, чтобы говорить о бабушек и дедушек и внуков,

167
00:12:15,720 --> 00:12:18,210
и вообще мы говорим о предках

168
00:12:18,210 --> 00:12:20,960
и потомков конкретного узла.

169
00:12:20,960 --> 00:12:25,710
Предком узла - или предков, скорее, узел -

170
00:12:25,710 --> 00:12:32,730
Все узлов, которые лежат на пути от корня до этого узла.

171
00:12:32,730 --> 00:12:36,640
Например, если я смотрю на узле 6,

172
00:12:36,640 --> 00:12:46,430
Затем предки собираются быть как 3 и 7.

173
00:12:46,430 --> 00:12:55,310
Предки 9, например, есть - если я смотрю на узле 9 -

174
00:12:55,310 --> 00:12:59,990
Затем предка из 9 находится всего в 7.

175
00:12:59,990 --> 00:13:01,940
И потомки в точности наоборот.

176
00:13:01,940 --> 00:13:05,430
Если я хочу посмотреть на все потомки 7,

177
00:13:05,430 --> 00:13:11,020
Затем я должен смотреть на все узлы под ним.

178
00:13:11,020 --> 00:13:16,950
Итак, у меня есть 3, 9 и 6, все как потомки 7.

179
00:13:16,950 --> 00:13:24,170
>> Последний термин, который мы будем говорить об это понятие бытия родного брата.

180
00:13:24,170 --> 00:13:27,980
Братья и сестры - вроде следующих вместе на этих семейных условиях -

181
00:13:27,980 --> 00:13:33,150
узлы, которые находятся на том же уровне в дереве.

182
00:13:33,150 --> 00:13:42,230
Так, 3 и 9 братьев и сестер, потому что они на том же уровне в дереве.

183
00:13:42,230 --> 00:13:46,190
Они оба имеют одного родителя, 7.

184
00:13:46,190 --> 00:13:51,400
6 не имеет братьев и сестер, потому что 9 не имеет детей.

185
00:13:51,400 --> 00:13:55,540
И 7 не имеет братьев и сестер, потому что это корень нашего дерева,

186
00:13:55,540 --> 00:13:59,010
и есть только когда-либо 1 корень.

187
00:13:59,010 --> 00:14:02,260
На 7 братьев и сестер, чтобы там должны были бы быть выше 7 узлов.

188
00:14:02,260 --> 00:14:07,480
Там должно было бы быть родителем 7, в котором случае 7 больше не будет корнем дерева.

189
00:14:07,480 --> 00:14:10,480
Затем, что новые родители из 7 также будет иметь ребенка,

190
00:14:10,480 --> 00:14:16,480
и что ребенок бы тогда брат 7.

191
00:14:16,480 --> 00:14:21,040
>> Хорошо. Двигаемся дальше.

192
00:14:21,040 --> 00:14:24,930
Когда мы начали наш разговор о бинарных деревьев,

193
00:14:24,930 --> 00:14:28,790
мы говорили о том, как мы собираемся использовать их для

194
00:14:28,790 --> 00:14:32,800
получить преимущество над обоих массивов и связанных списков.

195
00:14:32,800 --> 00:14:37,220
И то, как мы собираемся сделать это с этим заказом собственности.

196
00:14:37,220 --> 00:14:41,080
Мы говорим, что бинарное дерево упорядочен, в соответствии со спецификацией,

197
00:14:41,080 --> 00:14:45,740
если для каждого узла в дереве, все его потомки слева -

198
00:14:45,740 --> 00:14:48,670
левый ребенку, и всех потомков левой ребенка -

199
00:14:48,670 --> 00:14:54,510
имеют меньшие значения, а все узлы справа -

200
00:14:54,510 --> 00:14:57,770
права ребенка и всех потомков права ребенка -

201
00:14:57,770 --> 00:15:02,800
есть узлы больше, чем значение текущего узла, что мы смотрим.

202
00:15:02,800 --> 00:15:07,850
Просто для простоты мы будем считать, что нет никаких дублирующих узлов в нашем дереве.

203
00:15:07,850 --> 00:15:11,180
Например, в этом дереве мы не собираемся иметь дело со случаем

204
00:15:11,180 --> 00:15:13,680
где у нас есть значение 7 в корне

205
00:15:13,680 --> 00:15:16,720
 и у нас также есть значение 7 в другом месте в дерево.

206
00:15:16,720 --> 00:15:24,390
В этом случае, вы заметите, что это дерево действительно заказан.

207
00:15:24,390 --> 00:15:26,510
У нас есть значение 7 на корню.

208
00:15:26,510 --> 00:15:29,720
Все слева от 7 -

209
00:15:29,720 --> 00:15:35,310
если я отменю все эти маленькие знаки здесь -

210
00:15:35,310 --> 00:15:40,450
все, что слева от 7 - 3 и 6 -

211
00:15:40,450 --> 00:15:49,410
эти значения находятся менее чем в 7, и все, что правее - что именно это 9 -

212
00:15:49,410 --> 00:15:53,450
больше 7.

213
00:15:53,450 --> 00:15:58,650
>> Это не только упорядоченное дерево, содержащих эти значения,

214
00:15:58,650 --> 00:16:03,120
Но давайте нарисовать несколько из них.

215
00:16:03,120 --> 00:16:05,030
Существует на самом деле целая куча способов, которыми мы можем это сделать.

216
00:16:05,030 --> 00:16:09,380
Я собираюсь использовать сокращенную только, чтобы держать вещи простыми, где -

217
00:16:09,380 --> 00:16:11,520
, а не растягивая целом коробки-и-стрелки -

218
00:16:11,520 --> 00:16:14,220
Я просто хочу обратить номеров и добавить стрелки, соединяющие их.

219
00:16:14,220 --> 00:16:22,920
Для начала, мы будем просто писать свои оригинальные дерево еще раз, где у нас было 7, а затем 3,

220
00:16:22,920 --> 00:16:25,590
, а затем 3 указано обратно в праве на 6,

221
00:16:25,590 --> 00:16:30,890
и 7 имели право ребенка, который был 9.

222
00:16:30,890 --> 00:16:33,860
Хорошо. Какие еще один способ, что мы могли бы написать это дерево?

223
00:16:33,860 --> 00:16:38,800
Вместо того, чтобы быть 3 левый ребенка 7,

224
00:16:38,800 --> 00:16:41,360
Мы также могли бы быть 6 левом ребенка 7,

225
00:16:41,360 --> 00:16:44,470
, а затем 3 будет левый ребенка 6.

226
00:16:44,470 --> 00:16:48,520
Это будет выглядеть следующим образом дерево прямо здесь, где у меня 7,

227
00:16:48,520 --> 00:16:57,860
потом 6, потом 3, и 9 справа.

228
00:16:57,860 --> 00:17:01,490
Мы также не должны иметь 7, как наш корневой узел.

229
00:17:01,490 --> 00:17:03,860
Мы могли бы также иметь 6, как наш корневой узел.

230
00:17:03,860 --> 00:17:06,470
Что бы выглядеть?

231
00:17:06,470 --> 00:17:09,230
Если мы собираемся сохранить эту приказал собственности,

232
00:17:09,230 --> 00:17:12,970
все, что левее из 6 должен быть меньше, чем она.

233
00:17:12,970 --> 00:17:16,540
Там только одна возможность, и вот 3.

234
00:17:16,540 --> 00:17:19,869
Но тогда, как право ребенка из 6, у нас есть две возможности.

235
00:17:19,869 --> 00:17:25,380
Во-первых, мы могли бы 7, а затем 9,

236
00:17:25,380 --> 00:17:28,850
или мы можем сделать это - как я собираюсь сделать здесь -

237
00:17:28,850 --> 00:17:34,790
где у нас есть 9, права ребенка 6,

238
00:17:34,790 --> 00:17:39,050
, а затем 7 в качестве левого ребенком из 9.

239
00:17:39,050 --> 00:17:44,240
>> Теперь, 7 и 6 не являются единственно возможными значениями корня.

240
00:17:44,240 --> 00:17:50,200
Мы могли бы также иметь 3 быть в корне.

241
00:17:50,200 --> 00:17:52,240
Что произойдет, если 3 является в корне?

242
00:17:52,240 --> 00:17:54,390
Здесь все становится немного интереснее.

243
00:17:54,390 --> 00:17:58,440
Три не имеет никакого значения, которые меньше, чем он,

244
00:17:58,440 --> 00:18:02,070
так что вся левая сторона дерева просто будет нулевой.

245
00:18:02,070 --> 00:18:03,230
Там не будет ничего нет.

246
00:18:03,230 --> 00:18:07,220
Справа, мы могли бы перечислить вещи в порядке возрастания.

247
00:18:07,220 --> 00:18:15,530
Мы могли бы 3, то 6, то 7, то 9.

248
00:18:15,530 --> 00:18:26,710
Или, мы могли бы сделать 3, то 6, то 9, то 7.

249
00:18:26,710 --> 00:18:35,020
Или, мы могли бы сделать 3, затем 7, потом 6, потом 9.

250
00:18:35,020 --> 00:18:40,950
Или, 3, 7 - на самом деле нет, мы не можем сделать 7 больше.

251
00:18:40,950 --> 00:18:43,330
Это наша одно там.

252
00:18:43,330 --> 00:18:54,710
Мы можем сделать 9, а затем из 9 мы можем сделать 6, а затем 7.

253
00:18:54,710 --> 00:19:06,980
Или, что мы можем сделать 3, то 9, то 7, а затем 6.

254
00:19:06,980 --> 00:19:12,490
>> Одна вещь, чтобы обратить ваше внимание на здесь

255
00:19:12,490 --> 00:19:14,510
что эти деревья немного странный вид.

256
00:19:14,510 --> 00:19:17,840
В частности, если мы смотрим на 4 дерева на правой стороне -

257
00:19:17,840 --> 00:19:20,930
Я их круг, здесь -

258
00:19:20,930 --> 00:19:28,410
эти деревья выглядят почти так же, как связанный список.

259
00:19:28,410 --> 00:19:32,670
Каждый узел имеет только одного ребенка,

260
00:19:32,670 --> 00:19:38,950
и поэтому мы не должны все это древовидная структура, которую мы видим, например,

261
00:19:38,950 --> 00:19:44,720
 В этом одинокое дерево здесь на нижней левой.

262
00:19:44,720 --> 00:19:52,490
Эти деревья на самом деле называется вырожденным, бинарные деревья,

263
00:19:52,490 --> 00:19:54,170
и мы поговорим об этом подробнее в будущем -

264
00:19:54,170 --> 00:19:56,730
Особенно если вы идете на принятие других курсов по информатике.

265
00:19:56,730 --> 00:19:59,670
Эти деревья являются вырожденными.

266
00:19:59,670 --> 00:20:03,780
Они не очень полезно, потому что, действительно, эта структура поддается

267
00:20:03,780 --> 00:20:08,060
 для поиска раза похож на связанный список.

268
00:20:08,060 --> 00:20:13,050
Мы не получаем, чтобы воспользоваться дополнительной памяти - это дополнительный указатель -

269
00:20:13,050 --> 00:20:18,840
потому что наши структуры плохих таким образом.

270
00:20:18,840 --> 00:20:24,700
Вместо того, чтобы идти дальше и сделать из бинарных деревьев, которые имеют 9 на корню,

271
00:20:24,700 --> 00:20:27,220
которая является последний случай, что мы должны,

272
00:20:27,220 --> 00:20:32,380
мы вместо этого, на данный момент, поговорим немного об этом другим термином

273
00:20:32,380 --> 00:20:36,150
, которые мы используем, когда говорим о деревьях, которые называют высотой.

274
00:20:36,150 --> 00:20:45,460
>> Высота дерева это расстояние от корня до самых отдаленных узлов,

275
00:20:45,460 --> 00:20:48,370
или, вернее, количество прыжков, что вы должны сделать для того, чтобы

276
00:20:48,370 --> 00:20:53,750
начинается с корня и затем в конечном итоге на самом отдаленном узел в дереве.

277
00:20:53,750 --> 00:20:57,330
Если мы посмотрим на некоторые из этих деревьев, которые мы нарисовали прямо здесь,

278
00:20:57,330 --> 00:21:07,870
мы видим, что если мы возьмем это дерево в левом верхнем углу, и мы начинаем на 3,

279
00:21:07,870 --> 00:21:14,510
Затем мы должны сделать 1-хопа, чтобы добраться до 6, второго прыжка, чтобы добраться до 7,

280
00:21:14,510 --> 00:21:20,560
и третий хоп, чтобы добраться до 9.

281
00:21:20,560 --> 00:21:26,120
Таким образом, высота этого дерева 3.

282
00:21:26,120 --> 00:21:30,640
Мы можем сделать то же самое упражнение для других деревьев, изложенные с этой зеленой,

283
00:21:30,640 --> 00:21:40,100
и мы видим, что высота всех этих деревьев также действительно 3.

284
00:21:40,100 --> 00:21:45,230
Это часть того, что делает их вырожденные -

285
00:21:45,230 --> 00:21:53,750
что их высота составляет всего один меньше, чем количество узлов по всему дереву.

286
00:21:53,750 --> 00:21:58,400
Если мы посмотрим на этого другого дерева, что это окружение с красным, с другой стороны,

287
00:21:58,400 --> 00:22:03,920
мы видим, что наиболее удаленных узлов листьев 6 и 9 -

288
00:22:03,920 --> 00:22:06,940
листья оказываются те узлы, которые не имеют детей.

289
00:22:06,940 --> 00:22:11,760
Итак, для того, чтобы получить от корневого узла либо 6 или 9,

290
00:22:11,760 --> 00:22:17,840
мы должны сделать одно-хопа, чтобы добраться до 7, а затем второго прыжка, чтобы добраться до 9,

291
00:22:17,840 --> 00:22:21,240
и аналогично, только второго прыжка с 7, чтобы добраться до 6.

292
00:22:21,240 --> 00:22:29,080
Таким образом, высота этого дерева здесь только 2.

293
00:22:29,080 --> 00:22:35,330
Вы можете вернуться назад и сделать это для всех других деревьев, которые мы ранее обсуждали

294
00:22:35,330 --> 00:22:37,380
начиная с 7 и 6,

295
00:22:37,480 --> 00:22:42,500
и вы увидите, что высота всех этих деревьев также 2.

296
00:22:42,500 --> 00:22:46,320
>> Поэтому мы говорили о приказал бинарные деревья

297
00:22:46,320 --> 00:22:50,250
и почему они крутые, потому что вы можете искать через них в

298
00:22:50,250 --> 00:22:53,810
очень похоже на поиски более упорядоченный массив.

299
00:22:53,810 --> 00:22:58,720
Здесь мы говорим о том, что улучшение время поиска

300
00:22:58,720 --> 00:23:02,730
над простой связанный список.

301
00:23:02,730 --> 00:23:05,010
С связанный список - если вы хотите найти конкретный элемент -

302
00:23:05,010 --> 00:23:07,470
Вы в лучшем случае собирается сделать какой-то линейный поиск

303
00:23:07,470 --> 00:23:10,920
где вы начинаете в начале списка и хмеля один-на-один -

304
00:23:10,920 --> 00:23:12,620
одного узла на один узел -

305
00:23:12,620 --> 00:23:16,060
весь список, пока не найдете то, что вы ищете.

306
00:23:16,060 --> 00:23:19,440
Принимая во внимание, если у вас есть бинарное дерево, которое хранится в этом хорошем формате,

307
00:23:19,440 --> 00:23:23,300
Вы можете фактически получить больше бинарный поиск продолжается

308
00:23:23,300 --> 00:23:25,160
где вы разделяй и властвуй

309
00:23:25,160 --> 00:23:29,490
и поиска при помощи соответствующих половины деревьев на каждом шагу.

310
00:23:29,490 --> 00:23:32,840
Давайте посмотрим, как это работает.

311
00:23:32,840 --> 00:23:38,850
>> Если у нас есть - опять же, возвращаясь к нашей первоначальной дерево -

312
00:23:38,850 --> 00:23:46,710
мы начинаем в 7, у нас есть 3 слева, 9 справа,

313
00:23:46,710 --> 00:23:51,740
и под 3 имеем 6.

314
00:23:51,740 --> 00:24:01,880
Если мы хотим, чтобы найти номер 6 в этом дереве, мы бы начали в корне.

315
00:24:01,880 --> 00:24:08,910
Мы бы сравнить значение мы ищем, скажем, 6,

316
00:24:08,910 --> 00:24:12,320
со значением, хранящимся в узле, который мы в настоящее время смотрим, 7,

317
00:24:12,320 --> 00:24:21,200
обнаружите, что 6 является действительно меньше, чем 7, так что мы бы двигаться влево.

318
00:24:21,200 --> 00:24:25,530
Если значение 6 было больше, чем 7, мы бы вместо перемещается вправо.

319
00:24:25,530 --> 00:24:29,770
Поскольку мы знаем, что - благодаря структуре нашей приказал бинарном дереве -

320
00:24:29,770 --> 00:24:33,910
все значения менее 7 будут храниться слева от 7,

321
00:24:33,910 --> 00:24:40,520
нет необходимости даже беспокоиться, глядя через правую сторону дерева.

322
00:24:40,520 --> 00:24:43,780
Как только мы переходим к левой, и мы теперь на узел, содержащий 3,

323
00:24:43,780 --> 00:24:48,110
мы можем сделать то же сравнение еще раз, где мы сравниваем 3 и 6.

324
00:24:48,110 --> 00:24:52,430
И мы видим, что в то время как 6 - ценность, которую мы ищем, - это больше, чем 3,

325
00:24:52,430 --> 00:24:58,580
мы можем перейти к правой стороне узел, содержащий 3.

326
00:24:58,580 --> 00:25:02,670
Там нет левой стороне здесь, так что мы могли бы проигнорировал.

327
00:25:02,670 --> 00:25:06,510
Но мы знаем только, что, поскольку мы смотрим на само дерево,

328
00:25:06,510 --> 00:25:08,660
и мы видим, что дерево не имеет детей.

329
00:25:08,660 --> 00:25:13,640
>> Это также довольно легко найти 6 в этом дереве, если мы делаем это сами, как люди,

330
00:25:13,640 --> 00:25:16,890
Но давайте следить за этим процессом механически, как компьютер будет делать

331
00:25:16,890 --> 00:25:18,620
чтобы понять алгоритм.

332
00:25:18,620 --> 00:25:26,200
На данный момент, мы сейчас смотрим на узел, который содержит 6,

333
00:25:26,200 --> 00:25:29,180
и мы ищем значение 6,

334
00:25:29,180 --> 00:25:31,740
да, действительно, мы нашли нужный узел.

335
00:25:31,740 --> 00:25:35,070
Мы обнаружили, что значение 6 в нашем дереве, и мы можем прекратить наши поиски.

336
00:25:35,070 --> 00:25:37,330
На данный момент, в зависимости от того, что происходит,

337
00:25:37,330 --> 00:25:41,870
мы можем сказать, да, мы нашли значения 6, она существует в нашем дереве.

338
00:25:41,870 --> 00:25:47,640
Или, если мы планируем вставить узел или сделать что-то, что мы можем сделать, что в этой точке.

339
00:25:47,640 --> 00:25:53,010
>> Давайте сделаем еще пару поиска, чтобы посмотреть, как это работает.

340
00:25:53,010 --> 00:25:59,390
Давайте посмотрим, что произойдет, если мы должны были попробовать и посмотреть значение 10.

341
00:25:59,390 --> 00:26:02,970
Если бы мы искать значение 10, мы хотели бы начать с корня.

342
00:26:02,970 --> 00:26:07,070
Мы видим, что 10 больше, чем 7, поэтому мы будем двигаться вправо.

343
00:26:07,070 --> 00:26:13,640
Мы хотели попасть на 9 и сравните 9 до 10 и видим, что 9 является действительно меньше, чем 10.

344
00:26:13,640 --> 00:26:16,210
Итак, еще раз, мы будем пытаться двигаться вправо.

345
00:26:16,210 --> 00:26:20,350
Но на данный момент, мы бы заметили, что мы находимся на нулевой узел.

346
00:26:20,350 --> 00:26:23,080
Там ничего нет. Там нет ничего, где 10 должно быть.

347
00:26:23,080 --> 00:26:29,360
Это то, где мы можем сообщить неудача - что там на самом деле нет 10 в дерево.

348
00:26:29,360 --> 00:26:35,420
И, наконец, давайте пройдем случае, когда мы пытаемся найти 1 в дерево.

349
00:26:35,420 --> 00:26:38,790
Это похоже на то, что происходит, если мы посмотрим на 10, только вместо того, чтобы идти направо,

350
00:26:38,790 --> 00:26:41,260
Мы собираемся пойти налево.

351
00:26:41,260 --> 00:26:46,170
Мы начинаем в 7 и видим, что 1 меньше 7, поэтому мы двигаемся влево.

352
00:26:46,170 --> 00:26:51,750
Мы добираемся до 3 и видим, что 1 меньше, чем 3, поэтому снова мы пытаемся двигаться влево.

353
00:26:51,750 --> 00:26:59,080
На данный момент мы имеем нулевой узел, так что опять мы можем сообщить о неудаче.

354
00:26:59,080 --> 00:27:10,260
>> Если вы хотите узнать больше о бинарных деревьев,

355
00:27:10,260 --> 00:27:14,420
Есть целая куча веселья мало проблем, которые вы можете сделать с ними.

356
00:27:14,420 --> 00:27:19,450
Я предлагаю практиковать рисунок из этих диаграммах один-на-один

357
00:27:19,450 --> 00:27:21,910
и следующие через все различные шаги,

358
00:27:21,910 --> 00:27:25,060
потому что это придет в супер-удобная

359
00:27:25,060 --> 00:27:27,480
Не только тогда, когда вы делаете проблема Huffman кодирования набора

360
00:27:27,480 --> 00:27:29,390
но и в будущих курсов -

361
00:27:29,390 --> 00:27:32,220
просто научиться рисовать эти структуры данных и думаю, через проблемы

362
00:27:32,220 --> 00:27:38,000
с ручкой и бумагой, или, в данном случае, IPad и стилусом.

363
00:27:38,000 --> 00:27:41,000
>> На данный момент, однако, мы собираемся двигаться дальше, чтобы сделать некоторые практики кодирования

364
00:27:41,000 --> 00:27:44,870
а на самом деле играть с этими бинарные деревья и посмотреть.

365
00:27:44,870 --> 00:27:52,150
Я собираюсь вернуться к моему компьютеру.

366
00:27:52,150 --> 00:27:58,480
Для этой части разреза, вместо использования CS50 или CS50 Run пространства,

367
00:27:58,480 --> 00:28:01,500
Я собираюсь использовать прибор.

368
00:28:01,500 --> 00:28:04,950
>> После наряду с спецификацией поставленной задачи,

369
00:28:04,950 --> 00:28:07,740
Я вижу, что я должен открыть прибор,

370
00:28:07,740 --> 00:28:11,020
иду в папку Dropbox, создать папку с именем Раздел 7,

371
00:28:11,020 --> 00:28:15,730
, а затем создать файл с именем binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Здесь мы идем. У меня есть прибор уже открыт.

373
00:28:22,050 --> 00:28:25,910
Я собираюсь тянуть до терминала.

374
00:28:25,910 --> 00:28:38,250
Я собираюсь пойти в папку Dropbox, создайте каталог называется section7,

375
00:28:38,250 --> 00:28:42,230
и увидеть его совершенно пустым.

376
00:28:42,230 --> 00:28:48,860
Теперь я собираюсь открыть binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Хорошо. Здесь мы идем - пустой файл.

378
00:28:51,750 --> 00:28:54,330
>> Давайте вернемся к спецификации.

379
00:28:54,330 --> 00:28:59,850
Спецификация просит, чтобы создать новое определение типа

380
00:28:59,850 --> 00:29:03,080
для двоичного дерева узлов содержащие Int значения -

381
00:29:03,080 --> 00:29:07,110
так же как и ценности, которые мы обратили в нашей диаграмм раньше.

382
00:29:07,110 --> 00:29:11,740
Мы собираемся использовать этот шаблонный ЬурейеЕ, что мы сделали здесь

383
00:29:11,740 --> 00:29:14,420
что вы должны узнать из задач 5 -

384
00:29:14,420 --> 00:29:19,190
если вы сделали хэш-таблицы путем завоевания правописания программы.

385
00:29:19,190 --> 00:29:22,540
Вы должны также признать, что в разделе прошлой неделе

386
00:29:22,540 --> 00:29:23,890
где мы говорили о связанных списков.

387
00:29:23,890 --> 00:29:27,870
У нас это ЬурейеЕ из структуры узла,

388
00:29:27,870 --> 00:29:34,430
и мы дали этой структуры узла это название структуры узла заранее

389
00:29:34,430 --> 00:29:39,350
так что мы можем ссылаться на него, так как мы хотим иметь указатели структуры узла

390
00:29:39,350 --> 00:29:45,740
как часть нашей структуры, но мы тогда окружили эту -

391
00:29:45,740 --> 00:29:47,700
или, скорее, заключены этом - в ЬурейеЕ

392
00:29:47,700 --> 00:29:54,600
так что, в конце кода, мы можем обратиться к этой структуре, как только узел, а структура узла.

393
00:29:54,600 --> 00:30:03,120
>> Это будет очень похож на односвязный определение списка, который мы видели на прошлой неделе.

394
00:30:03,120 --> 00:30:20,070
Чтобы сделать это, давайте начнем с выписывая шаблона.

395
00:30:20,070 --> 00:30:23,840
Мы знаем, что мы должны иметь целое значение,

396
00:30:23,840 --> 00:30:32,170
так что мы попали в целочисленное значение, а затем вместо того, чтобы только один указатель на следующий элемент -

397
00:30:32,170 --> 00:30:33,970
как мы сделали с односвязный списков -

398
00:30:33,970 --> 00:30:38,110
Мы собираемся иметь левый и правый указатели ребенка.

399
00:30:38,110 --> 00:30:42,880
Это довольно простая тоже - структура узла * левый ребенка;

400
00:30:42,880 --> 00:30:51,190
и структура узла * Право ребенка;. Cool.

401
00:30:51,190 --> 00:30:54,740
Это выглядит как очень хороший старт.

402
00:30:54,740 --> 00:30:58,530
Давайте вернемся к спецификации.

403
00:30:58,530 --> 00:31:05,030
>> Теперь нам нужно объявить глобальную переменную * узел корневого дерева.

404
00:31:05,030 --> 00:31:10,590
Мы собираемся сделать это глобальный так же, как мы сделали первый указатель в нашем списке также связана глобальным.

405
00:31:10,590 --> 00:31:12,690
Это было так, что в функциях, которые мы пишем

406
00:31:12,690 --> 00:31:16,180
мы не должны держать проходящей вокруг этого корня -

407
00:31:16,180 --> 00:31:19,620
хотя мы увидим, что, если вы хотите написать эти функции рекурсивно,

408
00:31:19,620 --> 00:31:22,830
что может быть лучше даже не передавать его в качестве глобальной, в первую очередь

409
00:31:22,830 --> 00:31:28,090
и вместо того, инициализировать его локально в основной функцией.

410
00:31:28,090 --> 00:31:31,960
Но, мы сделаем это в глобальном масштабе для начала.

411
00:31:31,960 --> 00:31:39,920
Опять же, мы дадим пару пространств, и я собираюсь объявить корневой узел *.

412
00:31:39,920 --> 00:31:46,770
Просто чтобы убедиться, что я не оставляю этой неинициализированные, я собираюсь установить его равным нулю.

413
00:31:46,770 --> 00:31:52,210
Теперь, в основной функции - которые мы будем писать очень быстро, прямо здесь -

414
00:31:52,210 --> 00:32:00,450
Int основных (Int агдс, сопзЬ сЬаг * ARGV []) -

415
00:32:00,450 --> 00:32:10,640
и я собираюсь начать декларирование мой ARGV массива как константный просто так, что я знаю,

416
00:32:10,640 --> 00:32:14,550
что те аргументы аргументами, которые я, вероятно, не хотят изменить.

417
00:32:14,550 --> 00:32:18,390
Если я хочу изменить их, я, вероятно, следует делать их копии.

418
00:32:18,390 --> 00:32:21,740
Вы увидите это много кода.

419
00:32:21,740 --> 00:32:25,440
Это хорошо в любом случае. Это прекрасно, чтобы оставить все как - опустить сопзЬ, если вы хотите.

420
00:32:25,440 --> 00:32:28,630
Как правило, я положил его в просто так, что я напоминаю себе,

421
00:32:28,630 --> 00:32:33,650
 что я, вероятно, не хотите изменять эти аргументы.

422
00:32:33,650 --> 00:32:39,240
>> Как всегда, я собираюсь включить это возвращение 0 линию в конце основного.

423
00:32:39,240 --> 00:32:45,730
Здесь я инициализации моего корневого узла.

424
00:32:45,730 --> 00:32:48,900
Как она стоит сейчас, у меня есть указатель, который установлен в нуль,

425
00:32:48,900 --> 00:32:52,970
таким образом, это указывает на ничего.

426
00:32:52,970 --> 00:32:57,480
Для того чтобы действительно начать строительство узла,

427
00:32:57,480 --> 00:32:59,250
Я в первую очередь необходимо выделить память для него.

428
00:32:59,250 --> 00:33:05,910
Я собираюсь сделать это, сделав памяти кучи с помощью таНос.

429
00:33:05,910 --> 00:33:10,660
Я собираюсь установить корень, равный результат таНос,

430
00:33:10,660 --> 00:33:19,550
и я собираюсь использовать SizeOf оператора для расчета размера узла.

431
00:33:19,550 --> 00:33:24,990
Причина, по которой я использую SizeOf узла, в отличие от, скажем,

432
00:33:24,990 --> 00:33:37,020
делать что-то вроде этого - таНос (4 + 4 +4) или таНос 12 -

433
00:33:37,020 --> 00:33:40,820
потому что я хочу, чтобы мой код, чтобы быть совместимым насколько это возможно.

434
00:33:40,820 --> 00:33:44,540
Я хочу быть в состоянии принять это. С файлом, скомпилировать его на прибор,

435
00:33:44,540 --> 00:33:48,820
, а затем компилировать его на моем 64-разрядный Mac -

436
00:33:48,820 --> 00:33:52,040
или на совершенно другой архитектуре -

437
00:33:52,040 --> 00:33:54,640
и я хочу это все будет работать так же.

438
00:33:54,640 --> 00:33:59,510
>> Если я делаю предположения относительно размера переменных -

439
00:33:59,510 --> 00:34:02,070
Размер Int или размер указателя -

440
00:34:02,070 --> 00:34:06,070
Затем я также делает предположения о видах архитектуры

441
00:34:06,070 --> 00:34:10,440
, на котором мой код может успешно скомпилировать при запуске.

442
00:34:10,440 --> 00:34:15,030
Всегда используйте SizeOf, в отличие от ручного суммирования структура полей.

443
00:34:15,030 --> 00:34:20,500
Другая причина в том, что там может быть также обивка, что компилятор помещает в структуру.

444
00:34:20,500 --> 00:34:26,570
Даже просто суммирование отдельных полей не то, что вы обычно хотят делать,

445
00:34:26,570 --> 00:34:30,340
так, удалите эту строку.

446
00:34:30,340 --> 00:34:33,090
Теперь, чтобы действительно инициализации этого корневого узла,

447
00:34:33,090 --> 00:34:36,489
Я хочу, чтобы подключить значения для каждого из своих различных областях.

448
00:34:36,489 --> 00:34:41,400
Например, для значения Я знаю, я хочу, чтобы инициализировать до 7,

449
00:34:41,400 --> 00:34:46,920
и теперь я собираюсь установить левый ребенок будет нулевым

450
00:34:46,920 --> 00:34:55,820
и право ребенка быть нулевым. Отлично!

451
00:34:55,820 --> 00:35:02,670
Мы сделали это часть спектра.

452
00:35:02,670 --> 00:35:07,390
>> Спецификация вниз в нижней части страницы 3 спрашивает меня на создание еще трех узлов -

453
00:35:07,390 --> 00:35:10,600
одна из которых 3, одна из которых 6, и один с 9 -

454
00:35:10,600 --> 00:35:14,210
, а затем подключить их так, что выглядит точно так же, как наше дерево схема

455
00:35:14,210 --> 00:35:17,120
что речь шла о ранее.

456
00:35:17,120 --> 00:35:20,450
Давайте сделаем это очень быстро здесь.

457
00:35:20,450 --> 00:35:26,270
Вы увидите очень быстро, что я собираюсь начать писать кучу повторяющегося кода.

458
00:35:26,270 --> 00:35:32,100
Я собираюсь создать узел *, и я собираюсь называть это три.

459
00:35:32,100 --> 00:35:36,000
Я собираюсь установить его равным таНос (SizeOf (узла)).

460
00:35:36,000 --> 00:35:41,070
Я собираюсь установить три-> значение = 3.

461
00:35:41,070 --> 00:35:54,780
Три -> left_child = NULL; трех -> правой _child = NULL; также.

462
00:35:54,780 --> 00:36:01,150
Это выглядит очень похоже на инициализацию корень, и это именно то, что

463
00:36:01,150 --> 00:36:05,760
Я собираюсь нужно сделать, если я начну инициализации 6 и 9, а также.

464
00:36:05,760 --> 00:36:20,720
Я сделаю это очень быстро здесь - на самом деле, я собираюсь сделать небольшой копирования и вставки,

465
00:36:20,720 --> 00:36:46,140
и убедиться, что я - все в порядке.

466
00:36:46,470 --> 00:37:09,900
 Теперь, я получил его скопировать, и я могу пойти дальше и установить равным 6.

467
00:37:09,900 --> 00:37:14,670
Вы видите, что это занимает некоторое время, и не супер-эффективным.

468
00:37:14,670 --> 00:37:22,610
В совсем немного, мы напишем функцию, которая будет делать это за нас.

469
00:37:22,610 --> 00:37:32,890
Я хочу, чтобы заменить этим с 9, заменить, что с 6.

470
00:37:32,890 --> 00:37:37,360
>> Теперь у нас есть все наши узлы созданы и инициализированы.

471
00:37:37,360 --> 00:37:41,200
У нас есть наш корень равным 7, или содержащим значение 7,

472
00:37:41,200 --> 00:37:46,510
наш узел, содержащий 3, наш узел, содержащий 6, и наш узел, содержащий 9.

473
00:37:46,510 --> 00:37:50,390
На данный момент, все, что нам нужно сделать, это провода все вверх.

474
00:37:50,390 --> 00:37:53,020
Поэтому я инициализируются все указатели до нуля, это просто так, что я убедиться, что

475
00:37:53,020 --> 00:37:56,260
Я не есть какие-то неинициализированных указателей там случайно.

476
00:37:56,260 --> 00:38:02,290
А также, поскольку, на данный момент, у меня только есть на самом деле соединения узлов друг с другом -

477
00:38:02,290 --> 00:38:04,750
с теми, что они на самом деле связан с - я не должен идти до конца и сделать

478
00:38:04,750 --> 00:38:08,240
Убедитесь, что все нули находятся там в соответствующих местах.

479
00:38:08,240 --> 00:38:15,630
>> Начиная с корнем, я знаю, что левая ребенка корня равна 3.

480
00:38:15,630 --> 00:38:21,250
Я знаю, что права ребенка корня равна 9.

481
00:38:21,250 --> 00:38:24,880
После этого, только другой ребенок, что я оставил для беспокойства

482
00:38:24,880 --> 00:38:39,080
это право ребенку 3, которая является 6.

483
00:38:39,080 --> 00:38:44,670
На данный момент, все это выглядит довольно хорошо.

484
00:38:44,670 --> 00:38:54,210
Мы удалим некоторые из этих линий.

485
00:38:54,210 --> 00:38:59,540
Теперь все выглядит довольно хорошо.

486
00:38:59,540 --> 00:39:04,240
Давайте вернемся к нашей спецификации и посмотреть, что мы должны делать дальше.

487
00:39:04,240 --> 00:39:07,610
>> На данный момент, мы должны написать функцию, называемую 'содержит'

488
00:39:07,610 --> 00:39:14,150
с прототипом "BOOL содержит (целочисленное значение).

489
00:39:14,150 --> 00:39:17,060
И это содержит функцию собирается вернуть истинный

490
00:39:17,060 --> 00:39:21,200
 если дерево на которое указывает наша глобальная переменная корневой

491
00:39:21,200 --> 00:39:26,950
 содержит значение передается в функцию и ложь в противном случае.

492
00:39:26,950 --> 00:39:29,000
Давайте пойдем дальше и что делать.

493
00:39:29,000 --> 00:39:35,380
Это будет так же, как поиск, что мы сделали вручную на IPad просто немного назад.

494
00:39:35,380 --> 00:39:40,130
Давайте масштаб в немного, и прокрутка вверх.

495
00:39:40,130 --> 00:39:43,130
Мы собираемся поставить эту функцию прямо над нашей основной функцией

496
00:39:43,130 --> 00:39:48,990
так что мы не должны делать никаких прототипов.

497
00:39:48,990 --> 00:39:55,960
Таким образом, логический содержит (целочисленное значение).

498
00:39:55,960 --> 00:40:00,330
Там мы идем. Там наш шаблонный декларации.

499
00:40:00,330 --> 00:40:02,900
Просто чтобы убедиться, что это будет компилировать,

500
00:40:02,900 --> 00:40:06,820
Я собираюсь идти вперед и просто установить его равным вернуться ложным.

501
00:40:06,820 --> 00:40:09,980
Сейчас эта функция просто не будет делать ничего, и всегда сообщают, что

502
00:40:09,980 --> 00:40:14,010
значение, которое мы ищем не в дереве.

503
00:40:14,010 --> 00:40:16,280
>> В этот момент, вероятно, это хорошая идея -

504
00:40:16,280 --> 00:40:19,600
так как мы написали целую кучу кода, и мы даже не пытались тестирование еще -

505
00:40:19,600 --> 00:40:22,590
чтобы убедиться, что все компилируется.

506
00:40:22,590 --> 00:40:27,460
Есть несколько вещей, которые мы должны сделать, чтобы убедиться, что это будет на самом деле компиляции.

507
00:40:27,460 --> 00:40:33,530
Во-первых, увидеть, если мы используем любые функции в любой библиотеки, которые мы еще не включены.

508
00:40:33,530 --> 00:40:37,940
Функции, которые мы использовали до сих пор, таНос,

509
00:40:37,940 --> 00:40:43,310
и мы также использовали этот тип - это нестандартный тип, называемый "bool' -

510
00:40:43,310 --> 00:40:45,750
которая входит в стандартную BOOL заголовка файла.

511
00:40:45,750 --> 00:40:53,250
Мы определенно хотим включать в себя стандартные bool.h для логического типа,

512
00:40:53,250 --> 00:40:59,230
и мы также хотим # включают в себя стандартные lib.h для стандартных библиотек

513
00:40:59,230 --> 00:41:03,530
, которые включают таНос, и свободные, и все такое.

514
00:41:03,530 --> 00:41:08,660
Таким образом, масштаб, мы собираемся бросить курить.

515
00:41:08,660 --> 00:41:14,190
Давайте попробуем и убедиться, что это на самом деле сделал компиляцию.

516
00:41:14,190 --> 00:41:18,150
Мы видим, что он делает, так что мы на правильном пути.

517
00:41:18,150 --> 00:41:22,990
>> Давайте открывать binary_tree.c снова.

518
00:41:22,990 --> 00:41:34,530
Он компилирует. Давайте спустимся и убедиться, что мы вставляем несколько звонков, чтобы наша функция содержит -

519
00:41:34,530 --> 00:41:40,130
просто чтобы убедиться, что все хорошо.

520
00:41:40,130 --> 00:41:43,170
Например, когда мы сделали некоторые поиска в нашем дереве ранее,

521
00:41:43,170 --> 00:41:48,500
Мы пытались найти значения 6, 10 и 1, и мы знали, что 6 было в дереве,

522
00:41:48,500 --> 00:41:52,220
10 был не в дереве, и 1 не был в дерево либо.

523
00:41:52,220 --> 00:41:57,230
Давайте использовать эти образцы звонки как способ выяснить, является ли или нет

524
00:41:57,230 --> 00:41:59,880
наши содержит функцию работает.

525
00:41:59,880 --> 00:42:05,210
Для того, чтобы сделать это, я собираюсь использовать Е функция,

526
00:42:05,210 --> 00:42:10,280
и мы собираемся, чтобы распечатать результат вызова содержит.

527
00:42:10,280 --> 00:42:13,280
Я собираюсь поставить в строку "содержит (% D) = потому что

528
00:42:13,280 --> 00:42:20,470
 мы собираемся подключить значение, что мы собираемся искать,

529
00:42:20,470 --> 00:42:27,130
и% = с \ п "и использовать его в качестве нашего формата строки.

530
00:42:27,130 --> 00:42:30,720
Мы просто собираемся, чтобы увидеть - в буквальном смысле распечатать на экране -

531
00:42:30,720 --> 00:42:32,060
, что выглядит как вызов функции.

532
00:42:32,060 --> 00:42:33,580
Это на самом деле не вызов функции.

533
00:42:33,580 --> 00:42:36,760
 Это просто строка предназначена для выглядеть как вызов функции.

534
00:42:36,760 --> 00:42:41,140
>> Теперь, мы собираемся подключить значения.

535
00:42:41,140 --> 00:42:43,580
Мы собираемся попробовать содержит 6,

536
00:42:43,580 --> 00:42:48,340
и то, что мы собираемся сделать, так это использовать, что тройной оператор.

537
00:42:48,340 --> 00:42:56,340
Давайте посмотрим, - содержит 6 - да, теперь я содержал 6 и если содержит 6 правда,

538
00:42:56,340 --> 00:43:01,850
Строка, что мы собираемся отправить в формате характер% с

539
00:43:01,850 --> 00:43:04,850
будет строка "истина".

540
00:43:04,850 --> 00:43:07,690
Давайте выделите на немного.

541
00:43:07,690 --> 00:43:16,210
В противном случае, мы хотим послать строку "ложной", если содержит 6 возвращает ложь.

542
00:43:16,210 --> 00:43:19,730
Это немного бестолковый с виду, но я думаю, я мог бы также иллюстрируют

543
00:43:19,730 --> 00:43:23,780
что тройной оператор выглядит так как мы не видели его на некоторое время.

544
00:43:23,780 --> 00:43:27,670
Это будет хороший, удобный способ выяснить, если наши содержит функцию работает.

545
00:43:27,670 --> 00:43:30,040
Я буду прокручивать назад на левую,

546
00:43:30,040 --> 00:43:39,900
и я собираюсь скопировать и вставить эту строку несколько раз.

547
00:43:39,900 --> 00:43:44,910
Он изменил некоторые из этих ценностей по всему,

548
00:43:44,910 --> 00:43:59,380
так что это будет 1, а это будет 10.

549
00:43:59,380 --> 00:44:02,480
>> На данный момент у нас есть хорошая функция содержит.

550
00:44:02,480 --> 00:44:06,080
У нас есть несколько тестов, и мы увидим, если все это работает.

551
00:44:06,080 --> 00:44:08,120
На данный момент мы написали еще несколько коде.

552
00:44:08,120 --> 00:44:13,160
Время, чтобы выйти, и убедитесь, что все еще компилирует.

553
00:44:13,160 --> 00:44:20,360
Выйти, и теперь давайте попробуем делать бинарное дерево снова.

554
00:44:20,360 --> 00:44:22,260
Что ж, похоже, у нас есть ошибки,

555
00:44:22,260 --> 00:44:26,930
И у нас есть эта явного объявления библиотечные функции Printf.

556
00:44:26,930 --> 00:44:39,350
Похоже, что мы должны пойти и # включить standardio.h.

557
00:44:39,350 --> 00:44:45,350
И с этим, все должно компилироваться. Мы все хорошо.

558
00:44:45,350 --> 00:44:50,420
Теперь попробуйте запустить бинарное дерево и посмотреть, что происходит.

559
00:44:50,420 --> 00:44:53,520
Вот и мы,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
и мы видим, что, как мы и ожидали -

561
00:44:55,190 --> 00:44:56,910
потому что мы не реализовали содержит еще,

562
00:44:56,910 --> 00:44:59,800
или, скорее, мы просто положить в свою очередь ложными -

563
00:44:59,800 --> 00:45:03,300
мы видим, что это просто возвращение ложным для всех из них,

564
00:45:03,300 --> 00:45:06,180
Так что все рабочие, по большей части довольно хорошо.

565
00:45:06,180 --> 00:45:11,860
>> Давайте вернемся в деле осуществления и содержится в этой точке.

566
00:45:11,860 --> 00:45:17,490
Я хочу, чтобы прокрутить вниз, увеличивать, и -

567
00:45:17,490 --> 00:45:22,330
Помните, что алгоритм, который мы использовали в том, что мы начали в корневой узел

568
00:45:22,330 --> 00:45:28,010
, а затем в каждом узле с которыми мы сталкиваемся, мы делаем для сравнения,

569
00:45:28,010 --> 00:45:32,380
и на основе этого сравнения мы либо двигаться влево ребенка или права ребенка.

570
00:45:32,380 --> 00:45:39,670
Это будет выглядеть очень похоже на двоичный код поиска, который мы писали ранее в срок.

571
00:45:39,670 --> 00:45:47,810
Когда мы начинаем, мы знаем, что мы хотим провести на текущий узел

572
00:45:47,810 --> 00:45:54,050
что мы смотрим, и текущий узел будет инициализирован на корневой узел.

573
00:45:54,050 --> 00:45:56,260
И теперь, мы собираемся продолжать идти по дереву,

574
00:45:56,260 --> 00:45:58,140
и помните, что наши остановки состоянии -

575
00:45:58,140 --> 00:46:01,870
 Когда мы фактически работали на примере вручную -

576
00:46:01,870 --> 00:46:03,960
был, когда мы столкнулись с нулевой узел,

577
00:46:03,960 --> 00:46:05,480
не тогда, когда мы смотрели на нулевой ребенка,

578
00:46:05,480 --> 00:46:09,620
а когда мы действительно переехали в узел в дереве

579
00:46:09,620 --> 00:46:12,640
и обнаружил, что мы находимся на нулевой узел.

580
00:46:12,640 --> 00:46:20,720
Мы собираемся повторять, пока тока не равна нулю.

581
00:46:20,720 --> 00:46:22,920
И что мы будем делать?

582
00:46:22,920 --> 00:46:31,610
Мы собираемся проверить, если (текущ. -> значение == значение),

583
00:46:31,610 --> 00:46:35,160
Затем мы знаем, что мы на самом деле нашли узел, который мы ищем.

584
00:46:35,160 --> 00:46:40,450
Так вот, мы можем вернуться верно.

585
00:46:40,450 --> 00:46:49,830
В противном случае, мы хотим видеть или нет значение меньше, чем значение.

586
00:46:49,830 --> 00:46:53,850
Если значение текущего узла меньше, чем значение, которое мы ищем,

587
00:46:53,850 --> 00:46:57,280
мы будем двигаться вправо.

588
00:46:57,280 --> 00:47:10,600
Таким образом, текущ. = текущ. -> right_child, а в противном случае, мы будем двигаться влево.

589
00:47:10,600 --> 00:47:17,480
текущ. = текущ. -> left_child;. Довольно просто.

590
00:47:17,480 --> 00:47:22,830
>> Вы, наверное, признать цикл, который очень похож на этого от

591
00:47:22,830 --> 00:47:27,580
бинарный поиск в начале срока, за исключением то мы имеем дело с низкой, средней и высокой.

592
00:47:27,580 --> 00:47:30,000
Здесь мы просто должны посмотреть на текущее значение,

593
00:47:30,000 --> 00:47:31,930
так что это просто и красиво.

594
00:47:31,930 --> 00:47:34,960
Давайте убедиться, что этот код работает.

595
00:47:34,960 --> 00:47:42,780
Во-первых, убедитесь, что он компилирует. Похоже, что он делает.

596
00:47:42,780 --> 00:47:47,920
Давайте попробуем запустить его.

597
00:47:47,920 --> 00:47:50,160
И действительно, он печатает все, что мы ожидали.

598
00:47:50,160 --> 00:47:54,320
Он находит 6 в дереве, не найти 10, потому что 10 не в дереве,

599
00:47:54,320 --> 00:47:57,740
и не находит 1, либо потому, что 1 также не в дереве.

600
00:47:57,740 --> 00:48:01,420
Прикольных вещей.

601
00:48:01,420 --> 00:48:04,470
>> Хорошо. Давайте вернемся к нашей спецификации и посмотреть, что будет дальше.

602
00:48:04,470 --> 00:48:07,990
Теперь он хочет добавить еще несколько узлов для нашего дерева.

603
00:48:07,990 --> 00:48:11,690
Она хочет добавить 5, 2 и 8, и убедиться, что наши содержит код

604
00:48:11,690 --> 00:48:13,570
по-прежнему работает, как ожидалось.

605
00:48:13,570 --> 00:48:14,900
Давайте делать это.

606
00:48:14,900 --> 00:48:19,430
На данный момент, а не делать то, что раздражает копировать и вставлять снова,

607
00:48:19,430 --> 00:48:23,770
давайте напишем функцию, чтобы фактически создать узел.

608
00:48:23,770 --> 00:48:27,740
Если прокрутить весь путь до главного, мы видим, что мы делали это

609
00:48:27,740 --> 00:48:31,210
очень похожий код снова и снова, каждый раз, когда мы хотим создать узел.

610
00:48:31,210 --> 00:48:39,540
>> Давайте напишем функцию, которая будет реально построить узел для нас, и вернуть его.

611
00:48:39,540 --> 00:48:41,960
Я буду называть его build_node.

612
00:48:41,960 --> 00:48:45,130
Я собираюсь построить узел с определенным значением.

613
00:48:45,130 --> 00:48:51,040
Увеличить здесь.

614
00:48:51,040 --> 00:48:56,600
Первое, что я собираюсь сделать, это на самом деле создать пространство для узла в куче.

615
00:48:56,600 --> 00:49:05,400
Таким образом, узел * п = таНос (SizeOf (узла)), п -> значение = значение;

616
00:49:05,400 --> 00:49:14,960
а потом здесь, я просто хочу, чтобы инициализировать все поля, чтобы быть соответствующие значения.

617
00:49:14,960 --> 00:49:22,500
И в самом конце, мы вернем наш узел.

618
00:49:22,500 --> 00:49:28,690
Хорошо. Единственное, что следует отметить, что эта функция здесь

619
00:49:28,690 --> 00:49:34,320
собирается вернуть указатель на область памяти, которая была куче.

620
00:49:34,320 --> 00:49:38,880
Что приятно об этом является то, что этот узел сейчас -

621
00:49:38,880 --> 00:49:42,420
мы должны объявить его в куче, потому что если мы объявили его в стек

622
00:49:42,420 --> 00:49:45,050
мы не были бы в состоянии сделать это в этой функции, как это.

623
00:49:45,050 --> 00:49:47,690
Эта память будет выйти из сферы

624
00:49:47,690 --> 00:49:51,590
и были бы недействительными, если мы попытались получить доступ к нему в дальнейшем.

625
00:49:51,590 --> 00:49:53,500
Поскольку мы объявляем куче памяти,

626
00:49:53,500 --> 00:49:55,830
мы будем иметь, чтобы заботиться о освобождая его позже

627
00:49:55,830 --> 00:49:58,530
для нашей программы не утечка любой памяти.

628
00:49:58,530 --> 00:50:01,270
Мы понтировавшего на что на все остальное в коде

629
00:50:01,270 --> 00:50:02,880
только для простоты в то время,

630
00:50:02,880 --> 00:50:05,610
но если вы когда-нибудь написать функцию, которая выглядит следующим образом

631
00:50:05,610 --> 00:50:10,370
где у вас есть - некоторые называют это таНос или перераспределить внутри -

632
00:50:10,370 --> 00:50:14,330
Вы хотите, чтобы убедиться, что вы положили какой-то комментарий здесь, который говорит:

633
00:50:14,330 --> 00:50:29,970
эй, вы знаете, возвращает куче узлов инициализируется переданный в цене.

634
00:50:29,970 --> 00:50:33,600
И тогда вы хотите, чтобы убедиться, что вы положили в какой-то внимание, что говорит

635
00:50:33,600 --> 00:50:41,720
Вызывающий должен освободить вернулась память.

636
00:50:41,720 --> 00:50:45,450
Таким образом, если кто-то никогда не идет, и использует эту функцию,

637
00:50:45,450 --> 00:50:48,150
они знают, что все, что они вернутся из этой функции

638
00:50:48,150 --> 00:50:50,870
в какой-то момент нужно будет освобожден.

639
00:50:50,870 --> 00:50:53,940
>> Если предположить, что все хорошо, и здесь хорошо,

640
00:50:53,940 --> 00:51:02,300
мы можем спуститься в наш код и заменить все эти строки прямо здесь

641
00:51:02,300 --> 00:51:05,410
с призывами к нашей функции узла сборки.

642
00:51:05,410 --> 00:51:08,170
Давайте сделаем это очень быстро.

643
00:51:08,170 --> 00:51:15,840
Одна часть, что мы не собираемся заменить эта часть здесь

644
00:51:15,840 --> 00:51:18,520
на дно, где мы на самом деле соединять узлы, чтобы указывать друг на друга,

645
00:51:18,520 --> 00:51:21,030
потому что мы не можем сделать в наших функций.

646
00:51:21,030 --> 00:51:37,400
Но, давайте сделаем корень = build_node (7); узел * три = build_node (3);

647
00:51:37,400 --> 00:51:47,980
узел * шесть = build_node (6); узел * девять = build_node (9),.

648
00:51:47,980 --> 00:51:52,590
И теперь, мы также хотели бы добавить узлы -

649
00:51:52,590 --> 00:52:03,530
узел * пять = build_node (5); узел * = build_node восемь (8);

650
00:52:03,530 --> 00:52:09,760
и то, что было на другой узел? Давайте посмотрим здесь. Мы хотели бы также добавить 2 -

651
00:52:09,760 --> 00:52:20,280
* два узла = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Хорошо. На данный момент, мы знаем, что у нас есть 7, 3, 9, и 6

653
00:52:26,850 --> 00:52:30,320
Все проводные соответствующим образом, но как насчет 5, 8 и 2?

654
00:52:30,320 --> 00:52:33,550
Чтобы сохранить все в надлежащий порядок,

655
00:52:33,550 --> 00:52:39,230
Мы знаем, что право ребенку три является 6.

656
00:52:39,230 --> 00:52:40,890
Итак, если мы собираемся добавить 5,

657
00:52:40,890 --> 00:52:46,670
5 также принадлежит к правой стороне деревьев, из которых 3 является корнем,

658
00:52:46,670 --> 00:52:50,440
5 принадлежит так как левая ребенка 6.

659
00:52:50,440 --> 00:52:58,650
Мы можем сделать это, сказав, шесть -> left_child = пять;

660
00:52:58,650 --> 00:53:10,790
, а затем 8 принадлежит как левая ребенком из 9, таким образом, девять -> left_child = восемь;

661
00:53:10,790 --> 00:53:22,190
, а затем 2 является левым ребенком 3, так что мы можем сделать это здесь - Тебя -> left_child = два,.

662
00:53:22,190 --> 00:53:27,730
Если вы не совсем понимаю вместе с тем, я предлагаю вам сделать это самостоятельно.

663
00:53:27,730 --> 00:53:35,660
>> Хорошо. Давайте сохраним это. Давайте выходить на улицу и убедитесь, что он собирает,

664
00:53:35,660 --> 00:53:40,760
и тогда мы можем добавить в нашу содержит вызовы.

665
00:53:40,760 --> 00:53:44,120
Похоже, все еще компилирует.

666
00:53:44,120 --> 00:53:51,790
Давайте и добавить в некоторых содержит вызовы.

667
00:53:51,790 --> 00:53:59,640
Опять же, я собираюсь сделать немного копирования и вставки.

668
00:53:59,640 --> 00:54:15,860
Теперь давайте искать 5, 8, и 2. Хорошо.

669
00:54:15,860 --> 00:54:28,330
Давайте удостоверимся, что это все выглядит хорошо до сих пор. Отлично! Сохранить и выйти.

670
00:54:28,330 --> 00:54:33,220
Теперь давайте сделаем, компиляции, а теперь давайте работать.

671
00:54:33,220 --> 00:54:37,540
Из результатов, похоже, все работает просто приятно и хорошо.

672
00:54:37,540 --> 00:54:41,780
Отлично! Так что теперь у нас есть наши содержит функцию написано.

673
00:54:41,780 --> 00:54:46,160
Давайте двигаться дальше и начать работать на том, как вставить узлы в дерево

674
00:54:46,160 --> 00:54:50,000
, поскольку, как мы делаем это сейчас, все не очень красиво.

675
00:54:50,000 --> 00:54:52,280
>> Если мы вернемся к спецификации,

676
00:54:52,280 --> 00:55:00,540
он просит, чтобы мы написали функцию под названием вставить - опять, возвращаясь логическое

677
00:55:00,540 --> 00:55:04,400
для того или нет, мы могли фактически вставки узла в дерево -

678
00:55:04,400 --> 00:55:07,710
, а затем значение для вставки в дерево определяется как

679
00:55:07,710 --> 00:55:11,060
Единственный аргумент, чтобы наши функции вставки.

680
00:55:11,060 --> 00:55:18,180
Мы вернемся верно, если мы могли бы действительно вставить узел, содержащий значение в дереве,

681
00:55:18,180 --> 00:55:20,930
Это означает, что мы, один, имел достаточно памяти,

682
00:55:20,930 --> 00:55:24,840
, а затем два, то этот узел уже не существуют в дереве, так -

683
00:55:24,840 --> 00:55:32,170
Помните, что мы не будем иметь одинаковые значения в дереве, просто чтобы сделать вещи простыми.

684
00:55:32,170 --> 00:55:35,590
Хорошо. Перейти к коду.

685
00:55:35,590 --> 00:55:44,240
Откройте его. Увеличить немного, а потом прокрутить вниз.

686
00:55:44,240 --> 00:55:47,220
Скажем функции вставки прямо над содержит.

687
00:55:47,220 --> 00:55:56,360
Опять же, это будет называться BOOL вставки (целочисленное значение).

688
00:55:56,360 --> 00:56:01,840
Дайте ему немного больше пространства, а затем, по умолчанию,

689
00:56:01,840 --> 00:56:08,870
давайте взамен ложного в самом конце.

690
00:56:08,870 --> 00:56:22,620
Теперь вниз, на дно, давайте идти вперед и вместо того, чтобы вручную создавать узлы

691
00:56:22,620 --> 00:56:27,900
В основной себе и проводка их до указывать друг на друга, как мы делаем,

692
00:56:27,900 --> 00:56:30,600
мы полагаемся на наши функции вставки, чтобы сделать это.

693
00:56:30,600 --> 00:56:35,510
Мы не будем полагаться на наши функции вставки для сборки всего дерева с нуля, только все же,

694
00:56:35,510 --> 00:56:39,970
а мы избавиться от этих линий - МЫ закомментируйте эти строки -

695
00:56:39,970 --> 00:56:43,430
что строить узлы 5, 8 и 2.

696
00:56:43,430 --> 00:56:55,740
А вместо этого, мы вставим звонки на наш функции вставки

697
00:56:55,740 --> 00:57:01,280
чтобы убедиться, что это действительно работает.

698
00:57:01,280 --> 00:57:05,840
Здесь мы идем.

699
00:57:05,840 --> 00:57:09,300
>> Теперь мы закомментировать эти строки.

700
00:57:09,300 --> 00:57:13,700
У нас есть только 7, 3, 9 и 6 в нашей дерева в этой точке.

701
00:57:13,700 --> 00:57:18,870
Чтобы убедиться в том, что все это работает,

702
00:57:18,870 --> 00:57:25,050
мы можем уменьшить масштаб, чтобы наши бинарное дерево,

703
00:57:25,050 --> 00:57:30,750
запустить его, и мы видим, что содержится в настоящее время говорит нам, что мы совершенно правы -

704
00:57:30,750 --> 00:57:33,110
5, 8, и 2 уже не в дереве.

705
00:57:33,110 --> 00:57:37,960
Вернитесь в коде,

706
00:57:37,960 --> 00:57:41,070
и как мы собираемся вставить?

707
00:57:41,070 --> 00:57:46,290
Помните, что мы делали, когда мы были на самом деле вставка 5, 8, и 2 ранее.

708
00:57:46,290 --> 00:57:50,100
Мы играли в эту игру Plinko, где мы начали в корне,

709
00:57:50,100 --> 00:57:52,780
спустился по дереву один на один за другим

710
00:57:52,780 --> 00:57:54,980
пока мы не нашли соответствующую щель,

711
00:57:54,980 --> 00:57:57,570
и тогда мы подключены узла в соответствующем месте.

712
00:57:57,570 --> 00:57:59,480
Мы собираемся сделать то же самое.

713
00:57:59,480 --> 00:58:04,070
Это, в основном, как написание кода, который мы использовали в содержит функцию

714
00:58:04,070 --> 00:58:05,910
Чтобы найти место, где узел должен быть,

715
00:58:05,910 --> 00:58:10,560
а потом мы только собираемся, чтобы вставить узел прямо там.

716
00:58:10,560 --> 00:58:17,000
Давайте начнем это делать.

717
00:58:17,000 --> 00:58:24,200
>> Итак, мы имеем узел * текущ. = корень; мы только собираемся следовать код содержит

718
00:58:24,200 --> 00:58:26,850
пока мы не найдем, что это не совсем работа для нас.

719
00:58:26,850 --> 00:58:32,390
Мы собираемся пройти через дерево в то время как текущий элемент не является нулевым,

720
00:58:32,390 --> 00:58:45,280
и если мы обнаружим, что значение тока, равна значению, что мы пытаемся вставить -

721
00:58:45,280 --> 00:58:49,600
Ну, это один из случаев, в которых мы не могли фактически вставки узла

722
00:58:49,600 --> 00:58:52,730
в дерево, потому что это означает, что у нас есть повторяющиеся значения.

723
00:58:52,730 --> 00:58:59,010
Здесь мы на самом деле собираемся вернуться ложным.

724
00:58:59,010 --> 00:59:08,440
Теперь, иначе, если значение тока составляет менее значения,

725
00:59:08,440 --> 00:59:10,930
Теперь мы знаем, что мы двигаемся вправо

726
00:59:10,930 --> 00:59:17,190
 потому что значение принадлежит в правой половине текущ. дерева.

727
00:59:17,190 --> 00:59:30,110
В противном случае, мы будем двигаться влево.

728
00:59:30,110 --> 00:59:37,980
Это в основном наши содержит функцию прямо там.

729
00:59:37,980 --> 00:59:41,820
>> На данный момент, как только мы закончили это в то время цикла,

730
00:59:41,820 --> 00:59:47,350
шему указатель будет указывать на нуль

731
00:59:47,350 --> 00:59:51,540
если функция уже не вернулся.

732
00:59:51,540 --> 00:59:58,710
Мы поэтому имеющие текущ. в том месте, где мы хотим, чтобы вставить новый узел.

733
00:59:58,710 --> 01:00:05,210
То, что остается сделать, это на самом деле построить новый узел,

734
01:00:05,210 --> 01:00:08,480
что мы можем сделать довольно легко.

735
01:00:08,480 --> 01:00:14,930
Мы можем использовать наши супер-удобная сборка узлов функции,

736
01:00:14,930 --> 01:00:17,210
и то, что мы не делали раньше -

737
01:00:17,210 --> 01:00:21,400
мы просто какая-то считали само собой разумеющимся, но теперь мы будем делать просто чтобы убедиться -

738
01:00:21,400 --> 01:00:27,130
мы будем проверить, чтобы убедиться, что значение возвращается новый узел был на самом деле

739
01:00:27,130 --> 01:00:33,410
не нулевой, потому что мы не хотим, чтобы начать доступ к этой памяти, если оно является недействительным.

740
01:00:33,410 --> 01:00:39,910
Мы можем проверить, чтобы убедиться, что новый узел не равна нулю.

741
01:00:39,910 --> 01:00:42,910
Или вместо этого, мы можем просто посмотреть, если он на самом деле является пустым,

742
01:00:42,910 --> 01:00:52,120
и если он равен нулю, то мы можем просто вернуться ложным рано.

743
01:00:52,120 --> 01:00:59,090
>> На данный момент, мы должны подключить новый узел в свою соответствующее место в дереве.

744
01:00:59,090 --> 01:01:03,510
Если мы посмотрим на основные и где мы были на самом деле проводки в значениях раньше,

745
01:01:03,510 --> 01:01:08,470
мы видим, что то, как мы это делали, когда мы хотели поставить 3 в дерево

746
01:01:08,470 --> 01:01:11,750
Мы были доступны левом ребенка корня.

747
01:01:11,750 --> 01:01:14,920
Когда мы ставим 9 в дерево, мы должны были получить доступ к право ребенка на корню.

748
01:01:14,920 --> 01:01:21,030
Мы должны были иметь указатель на родителя для того, чтобы положить новое значение в дерево.

749
01:01:21,030 --> 01:01:24,430
Прокрутка обратно вставить, что не собирается работать здесь вполне

750
01:01:24,430 --> 01:01:27,550
потому что у нас нет предка.

751
01:01:27,550 --> 01:01:31,650
Что мы хотим быть в состоянии делать это, на данный момент,

752
01:01:31,650 --> 01:01:37,080
проверьте значение родителей и посмотреть - ну, черт возьми,

753
01:01:37,080 --> 01:01:41,990
если значение родителя меньше, чем текущее значение,

754
01:01:41,990 --> 01:01:54,440
Затем право ребенка родитель должен быть новый узел;

755
01:01:54,440 --> 01:02:07,280
В противном случае левая ребенка родитель должен быть новый узел.

756
01:02:07,280 --> 01:02:10,290
Но мы не должны этого родителя указатель совсем еще.

757
01:02:10,290 --> 01:02:15,010
>> Для того, чтобы получить его, мы фактически придется отслеживать его, как мы идем по дереву

758
01:02:15,010 --> 01:02:18,440
и найти соответствующее место в нашем цикле выше.

759
01:02:18,440 --> 01:02:26,840
Мы можем сделать это с помощью прокрутки обратно к вершине нашей функции вставки

760
01:02:26,840 --> 01:02:32,350
и отслеживания другой указатель переменной родителей.

761
01:02:32,350 --> 01:02:39,340
Мы собираемся установить его равным нулю на начальном этапе,

762
01:02:39,340 --> 01:02:43,640
, а затем каждый раз, когда мы идем по дереву,

763
01:02:43,640 --> 01:02:51,540
Мы собираемся установить родителя, чтобы соответствовать текущим указателем.

764
01:02:51,540 --> 01:02:59,140
Установить родительский равно текущ..

765
01:02:59,140 --> 01:03:02,260
Таким образом, каждый раз, когда мы пройти,

766
01:03:02,260 --> 01:03:05,550
Мы собираемся убедиться, что в качестве текущего указателя увеличивается на единицу

767
01:03:05,550 --> 01:03:12,640
родительского указатель следует за ним - просто на один уровень выше текущего указателя в дереве.

768
01:03:12,640 --> 01:03:17,370
Это все выглядит довольно хорошо.

769
01:03:17,370 --> 01:03:22,380
>> Я думаю, что одна вещь, которую мы хотим настроить это построить узел возвращается NULL.

770
01:03:22,380 --> 01:03:25,380
Для того, чтобы построить узел на самом деле успешно возвращают NULL,

771
01:03:25,380 --> 01:03:31,060
мы должны изменить этот код,

772
01:03:31,060 --> 01:03:37,270
потому что здесь, мы никогда не проверяли, чтобы убедиться, что таНос вернулся действительный указатель.

773
01:03:37,270 --> 01:03:53,390
Так что, если (п = NULL!), Затем -

774
01:03:53,390 --> 01:03:55,250
если таНос вернулся действительный указатель, то мы его инициализации;

775
01:03:55,250 --> 01:04:02,540
В противном случае мы будем просто вернуть, и что в конечном итоге возвращается NULL для нас.

776
01:04:02,540 --> 01:04:13,050
Теперь все выглядит довольно хорошо. Давайте убедиться, что это на самом деле компилирует.

777
01:04:13,050 --> 01:04:22,240
Сделать бинарное дерево, и ах, у нас есть некоторые вещи здесь происходит.

778
01:04:22,240 --> 01:04:29,230
>> У нас есть неявная декларация функции создания узла.

779
01:04:29,230 --> 01:04:31,950
Опять же, эти компиляторы, мы собираемся начать с самого верха.

780
01:04:31,950 --> 01:04:36,380
Что это должно означать, что я звоню построить узел, прежде чем я на самом деле объявлена.

781
01:04:36,380 --> 01:04:37,730
Давайте вернемся к коду очень быстро.

782
01:04:37,730 --> 01:04:43,510
Прокрутите вниз, и, конечно же, моя вставка функция объявлена

783
01:04:43,510 --> 01:04:47,400
выше функции узла сборки,

784
01:04:47,400 --> 01:04:50,070
Но я пытаюсь использовать построить узел внутри вставки.

785
01:04:50,070 --> 01:05:06,610
Я собираюсь пойти и копию - а затем вставьте функцию сборки узлов путь здесь, на самом верху.

786
01:05:06,610 --> 01:05:11,750
Таким образом, мы надеемся, что будет работать. Давайте дадим этому еще один шанс.

787
01:05:11,750 --> 01:05:18,920
Теперь все компилируется. Все это хорошо.

788
01:05:18,920 --> 01:05:21,640
>> Но на данный момент, мы на самом деле не называли наши функции вставки.

789
01:05:21,640 --> 01:05:26,510
Мы просто знаем, что он собирает, так что давайте пойдем и положить несколько звонков дюйма

790
01:05:26,510 --> 01:05:28,240
Давайте сделаем, что в наших основных функций.

791
01:05:28,240 --> 01:05:32,390
Здесь мы закомментированы 5, 8 и 2,

792
01:05:32,390 --> 01:05:36,680
и тогда мы не подключить их сюда.

793
01:05:36,680 --> 01:05:41,640
Давайте сделаем несколько звонков, чтобы вставить,

794
01:05:41,640 --> 01:05:46,440
и давайте также использовать такие же вещи, которые мы использовали

795
01:05:46,440 --> 01:05:52,810
Когда мы сделали эти Printf звонков, чтобы убедиться, что все действительно становились вставлен правильно.

796
01:05:52,810 --> 01:06:00,550
Я собираюсь копировать и вставлять,

797
01:06:00,550 --> 01:06:12,450
и вместо того, содержит мы собираемся сделать вставку.

798
01:06:12,450 --> 01:06:30,140
И вместо того, 6, 10 и 1, мы собираемся использовать 5, 8 и 2.

799
01:06:30,140 --> 01:06:37,320
Это должно, мы надеемся, вставить 5, 8, и 2 в дерево.

800
01:06:37,320 --> 01:06:44,050
Компиляция. Все это хорошо. Теперь мы будем реально работать наша программа.

801
01:06:44,050 --> 01:06:47,330
>> Все вернулись ложной.

802
01:06:47,330 --> 01:06:53,830
Так, 5, 8 и 2 не пошел, и это выглядит как Содержит не нашли их либо.

803
01:06:53,830 --> 01:06:58,890
Что происходит? Давайте масштаба.

804
01:06:58,890 --> 01:07:02,160
Первой проблемой было то, что, казалось вставки, чтобы вернуться ложным,

805
01:07:02,160 --> 01:07:08,750
и, похоже, это потому, что мы оставили в нашем возвращении ложный вызов,

806
01:07:08,750 --> 01:07:14,590
и мы никогда не вернулись правда.

807
01:07:14,590 --> 01:07:17,880
Мы можем установить, что.

808
01:07:17,880 --> 01:07:25,290
Вторая проблема в том, теперь, даже если мы делаем - сохранить это, бросить это,

809
01:07:25,290 --> 01:07:34,530
запустить сделать снова, пусть он скомпилировать, а затем запустить его -

810
01:07:34,530 --> 01:07:37,670
мы видим, что что-то еще произошло.

811
01:07:37,670 --> 01:07:42,980
5, 8, и 2 еще не нашел в дереве.

812
01:07:42,980 --> 01:07:44,350
Итак, что происходит?

813
01:07:44,350 --> 01:07:45,700
>> Давайте посмотрим на это в коде.

814
01:07:45,700 --> 01:07:49,790
Давайте посмотрим, сможем ли мы понять это.

815
01:07:49,790 --> 01:07:57,940
Начнем с родителями не быть нулевым.

816
01:07:57,940 --> 01:07:59,510
Мы устанавливаем указатель текущей равных в корневой указатель,

817
01:07:59,510 --> 01:08:04,280
и мы собираемся работать наш путь вниз по дереву.

818
01:08:04,280 --> 01:08:08,650
Если текущий узел не является нулевым, то мы знаем, что мы можем двигаться вниз немного.

819
01:08:08,650 --> 01:08:12,330
Мы устанавливаем наши родители указатель равным текущему указателю,

820
01:08:12,330 --> 01:08:15,420
проверить значение - если значения совпадают, мы вернулись ложной.

821
01:08:15,420 --> 01:08:17,540
Если значения меньше мы переехали в правую;

822
01:08:17,540 --> 01:08:20,399
В противном случае мы переехали на левый.

823
01:08:20,399 --> 01:08:24,220
Затем мы строим узла. Я увеличить немного.

824
01:08:24,220 --> 01:08:31,410
И вот, мы собираемся, чтобы попытаться подключить до значений, то же самое.

825
01:08:31,410 --> 01:08:37,250
Что происходит? Давайте посмотрим, если возможно Valgrind может дать нам подсказку.

826
01:08:37,250 --> 01:08:43,910
>> Мне нравится использовать Valgrind Valgrind только потому, что очень быстро бежит

827
01:08:43,910 --> 01:08:46,729
и говорит вам, если есть какие-либо ошибки памяти.

828
01:08:46,729 --> 01:08:48,300
Когда мы запускаем Valgrind на код,

829
01:08:48,300 --> 01:08:55,859
как вы можете видеть правый удар here--Valgrind./binary_tree--and входа.

830
01:08:55,859 --> 01:09:03,640
Вы видите, что у нас не было никаких ошибок памяти, так что похоже, все в порядке до сих пор.

831
01:09:03,640 --> 01:09:07,529
У нас есть некоторые утечки памяти, которые мы знаем, потому что мы не

832
01:09:07,529 --> 01:09:08,910
происходит, чтобы освободить любого из наших узлов.

833
01:09:08,910 --> 01:09:13,050
Давайте попробуем работает GDB, чтобы посмотреть, что происходит на самом деле.

834
01:09:13,050 --> 01:09:20,010
Мы сделаем GDB. / Binary_tree. Он загрузился нормально.

835
01:09:20,010 --> 01:09:23,670
Давайте установим точку останова на вставку.

836
01:09:23,670 --> 01:09:28,600
Давайте запустим.

837
01:09:28,600 --> 01:09:31,200
Похоже, мы никогда не называли вставки.

838
01:09:31,200 --> 01:09:39,410
Похоже, проблема была только что, когда я изменил здесь, в главном -

839
01:09:39,410 --> 01:09:44,279
Все эти Printf звонки с содержит -

840
01:09:44,279 --> 01:09:56,430
Я никогда на самом деле изменилось этих позвонить вставки.

841
01:09:56,430 --> 01:10:01,660
Теперь давайте дать ему попробовать. Давайте компиляции.

842
01:10:01,660 --> 01:10:09,130
Все выглядит хорошо там. Теперь давайте попробуем запустить его, посмотреть, что происходит.

843
01:10:09,130 --> 01:10:13,320
Хорошо! Все выглядит довольно хорошо там.

844
01:10:13,320 --> 01:10:18,130
>> Последняя вещь, чтобы думать о том, есть ли какие-то крайние случаи этой вставки?

845
01:10:18,130 --> 01:10:23,170
И получается, что, мол, одно ребро случае это всегда интересно думать о

846
01:10:23,170 --> 01:10:26,250
в том, что произойдет, если ваше дерево пусто, и вы называете это вставка функции?

847
01:10:26,250 --> 01:10:30,330
Будет ли она работать? Что ж, давайте попробуем.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree с. -

849
01:10:32,110 --> 01:10:35,810
То, как мы собираемся проверить это, мы собираемся спуститься к нашей основной функции,

850
01:10:35,810 --> 01:10:41,690
и вместо проводки этих узлах вот так,

851
01:10:41,690 --> 01:10:56,730
мы только собираемся, чтобы закомментировать всю вещь,

852
01:10:56,730 --> 01:11:02,620
и вместо проводки до узлы себе,

853
01:11:02,620 --> 01:11:09,400
мы действительно можем просто идти вперед и удалить все это.

854
01:11:09,400 --> 01:11:17,560
Мы собираемся сделать все вызов для вставки.

855
01:11:17,560 --> 01:11:49,020
Итак, давайте делать - вместо 5, 8 и 2, мы собираемся, чтобы вставить 7, 3 и 9.

856
01:11:49,020 --> 01:11:58,440
И тогда мы также хотим, чтобы вставить 6, а.

857
01:11:58,440 --> 01:12:05,190
Сохранить. Выйти. Сделать бинарное дерево.

858
01:12:05,190 --> 01:12:08,540
Это все компилируется.

859
01:12:08,540 --> 01:12:10,320
Мы можем просто запустите его как есть и посмотреть, что происходит,

860
01:12:10,320 --> 01:12:12,770
но это также будет очень важно, чтобы убедиться, что

861
01:12:12,770 --> 01:12:14,740
Мы не имеют никаких ошибок памяти,

862
01:12:14,740 --> 01:12:16,840
так как это является одним из наших крайних случаях, что мы знаем о.

863
01:12:16,840 --> 01:12:20,150
>> Давайте удостоверимся, что он хорошо работает под Valgrind,

864
01:12:20,150 --> 01:12:28,310
которые мы будем делать, просто выдав Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Похоже, у нас действительно одна ошибка из одного контекста -

866
01:12:31,110 --> 01:12:33,790
у нас есть эта ошибка сегментации.

867
01:12:33,790 --> 01:12:36,690
Что случилось?

868
01:12:36,690 --> 01:12:41,650
Valgrind на самом деле говорит нам, где он находится.

869
01:12:41,650 --> 01:12:43,050
Уменьшить немного.

870
01:12:43,050 --> 01:12:46,040
Похоже, что происходит в нашей функции вставки,

871
01:12:46,040 --> 01:12:53,420
где у нас есть недействительным чтения размером 4 на вставку, строка 60.

872
01:12:53,420 --> 01:13:03,590
Давайте вернемся и посмотрим, что здесь происходит.

873
01:13:03,590 --> 01:13:05,350
Уменьшить очень быстро.

874
01:13:05,350 --> 01:13:14,230
Я хочу, чтобы убедиться, что он не идет к краю экрана, чтобы мы могли видеть все.

875
01:13:14,230 --> 01:13:18,760
Потяните, что в немного. Хорошо.

876
01:13:18,760 --> 01:13:35,030
Прокрутите вниз, и проблема прямо здесь.

877
01:13:35,030 --> 01:13:40,120
Что произойдет, если мы спускаемся и наш текущий узел уже нулевые,

878
01:13:40,120 --> 01:13:44,010
наш родительский узел является нулевым, поэтому, если мы смотрим на самом верху, прямо здесь -

879
01:13:44,010 --> 01:13:47,340
Если это время цикла никогда не выполняется

880
01:13:47,340 --> 01:13:52,330
потому что наше текущее значение равно нулю - наш корень нулевой так текущ. является недействительным -

881
01:13:52,330 --> 01:13:57,810
Затем наши родители никогда не будет установлен в текущ. или допустимое значение,

882
01:13:57,810 --> 01:14:00,580
Таким образом, родители также будет нулевым.

883
01:14:00,580 --> 01:14:03,700
Мы должны помнить, чтобы проверить, что

884
01:14:03,700 --> 01:14:08,750
К тому времени мы приступим здесь, и мы начинаем доступ к значению родителей.

885
01:14:08,750 --> 01:14:13,190
Итак, что происходит? Ну, если родитель является нуль -

886
01:14:13,190 --> 01:14:17,990
если (== NULL родителя), - то мы знаем, что

887
01:14:17,990 --> 01:14:19,530
не должно быть ничего в дерево.

888
01:14:19,530 --> 01:14:22,030
Мы должны пытаться вставить его в корне.

889
01:14:22,030 --> 01:14:32,570
Мы можем сделать это, просто задав корень, равный новый узел.

890
01:14:32,570 --> 01:14:40,010
Тогда в этой точке мы на самом деле не хотят, чтобы пройти через эти другие вещи.

891
01:14:40,010 --> 01:14:44,780
Вместо этого, прямо здесь, мы можем сделать либо другое-если-другому,

892
01:14:44,780 --> 01:14:47,610
или мы могли бы объединить все здесь в другом,

893
01:14:47,610 --> 01:14:56,300
но здесь мы будем использовать еще и сделать это таким образом.

894
01:14:56,300 --> 01:14:59,030
Теперь, мы собираемся проверить, чтобы убедиться, что наши родители не нулевой

895
01:14:59,030 --> 01:15:02,160
до этого на самом деле пытается получить доступ к его полям.

896
01:15:02,160 --> 01:15:05,330
Это поможет нам избежать ошибки сегментации.

897
01:15:05,330 --> 01:15:14,740
Таким образом, мы бросить курить, уменьшить масштаб, компилировать, запускать.

898
01:15:14,740 --> 01:15:18,130
>> Нет ошибки, но у нас еще есть куча утечек памяти

899
01:15:18,130 --> 01:15:20,650
потому что мы не освободить любого из наших узлов.

900
01:15:20,650 --> 01:15:24,350
Но, если мы идем сюда, и мы смотрим на нашу распечатку,

901
01:15:24,350 --> 01:15:30,880
мы видим, что, ну, похоже, что все наши вставками возвращались правда, и это хорошо.

902
01:15:30,880 --> 01:15:33,050
Вставки все верно,

903
01:15:33,050 --> 01:15:36,670
, а затем соответствующие вызовы содержит, тоже верно.

904
01:15:36,670 --> 01:15:41,510
>> Хорошая работа! Похоже, мы успешно написана вставки.

905
01:15:41,510 --> 01:15:47,430
Это все, что у нас есть проблемы спецификации для набора на этой неделе.

906
01:15:47,430 --> 01:15:51,720
Одна забавная возможность подумать о том, как бы вы на самом деле идут в

907
01:15:51,720 --> 01:15:55,340
и бесплатно все узлы в этом дереве.

908
01:15:55,340 --> 01:15:58,830
Мы можем сделать это разными способами,

909
01:15:58,830 --> 01:16:01,930
но я оставлю это до вас, чтобы эксперимент,

910
01:16:01,930 --> 01:16:06,080
и как весело задачей, попробуйте и убедитесь, что вы можете убедиться,

911
01:16:06,080 --> 01:16:09,490
что этот доклад Valgrind не возвращает ошибки и утечки.

912
01:16:09,490 --> 01:16:12,880
>> Удачи на Хаффман этой неделе поставленной задачи кодирования,

913
01:16:12,880 --> 01:16:14,380
и мы будем видеть вас на следующей неделе!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]