1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [第7条] [舒适]

2
00:00:02,500 --> 00:00:04,890
内特 - 哈迪森] [哈佛大学]

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
由于飓风沙地，

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
我要跟着问题设置6规格，

9
00:00:22,830 --> 00:00:25,650
和经历中的问题

10
00:00:25,650 --> 00:00:27,770
A组的问题部分。

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
Huffman树的编码。

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
然后我们使用这些next指针连接在一起的。

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
然后左子指针，该指针是空值，和一个右子节点指针为null。

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
我们的价值和空的子结点指针。

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
我要设置的左孩子指针指向的节点包含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
特别是，你做了习题集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，然后是一个孩子的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，和3的父6是。没有太多的不同。

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有没有兄弟姐妹，因为没有任何儿童。

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
孩子有权利为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
然后是左子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
我们也可以作为我们的根节点。

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
如果是在根会发生什么情况呢？

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  - 其实也没什么，我们不能做了。

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
如果我们想要搜索的数量在这棵树，我们就从根开始。

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
>> 这也很容易看在这棵树，如果我们这样做，我们自己作为人类，

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
最后，让我们通过的情况下，我们试图查找树中的。

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
不仅是当你在做的霍夫曼编码问题集

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空间的，

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文件夹，创建一个目录称为第七条第

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
我们将使用这个样板的typedef，我们在这里做了

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
我们走了这么一个结构节点的typedef，

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
或者更确切地说，附上 - 一个typedef

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
所以我们把int值，然后，而不是只是一个指针指向下一个元素 - 

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
和节点右子树。酷。

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
只是，以确保我不离开这个未初始化的，我将它设置为null。

413
00:31:46,770 --> 00:31:52,210
现在，在主要功能 - 我们会写的真的很快在这里 - 

414
00:31:52,210 --> 00:32:00,450
INT主要（INT ARGC，为const char *的argv []） - 

415
00:32:00,450 --> 00:32:10,640
我要开始我的argv数组声明为const只是让我知道

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
这是无论哪种方式。它的优良把它作为 - 省略cons​​t如果你想。

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
我要做到这一点，使内存使用malloc在堆上。

429
00:33:05,910 --> 00:33:10,660
我要设置root的malloc的结果，

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
做这样的事情 - 的malloc（4 +4 +4）或malloc 12  - 

433
00:33:37,020 --> 00:33:40,820
是因为我想我的代码是尽可能地兼容。

434
00:33:40,820 --> 00:33:44,540
我希望能够借此c文件，在设备上编译它，

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
我要创建一个节点*，我会打电话给它3。

459
00:35:32,100 --> 00:35:36,000
我将它设置为等于对malloc（如sizeof（节点））。

460
00:35:36,000 --> 00:35:41,070
我要设置三个值= 3。

461
00:35:41,070 --> 00:35:54,780
三 - > left_child = NULL; 3  - >右键_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
我初始化的指针为NULL的原因是，只是让我确保

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
“布尔包含（int值）的原型。

489
00:39:14,150 --> 00:39:17,060
这包含函数将返回true

490
00:39:17,060 --> 00:39:21,200
 如果树指出，我们在全球的根目录变量

491
00:39:21,200 --> 00:39:26,950
 包含的值传递到功能，否则返回false。

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
因此，布尔（int值）。

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
我要继续前进，就设置它等于返回false。

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
的功能，我们一直使用的是malloc的，

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的为bool类型，

512
00:40:53,250 --> 00:40:59,230
我们也希望＃标准库包括标准的lib.h

513
00:40:59,230 --> 00:41:03,530
包括malloc和自由，所有这一切。

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，我们知道在树中，

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
为了做到这一点，我要使用printf函数，

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
=％S \ n“，并用它作为我们的格式化字符串。

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
，我们将发送到％s格式字符的字符串

539
00:43:01,850 --> 00:43:04,850
将是字符串“true”。

540
00:43:04,850 --> 00:43:07,690
让我们多一点点滚动。

541
00:43:07,690 --> 00:43:16,210
否则，我们要发送的字符串“false”，如果包含6个返回false。

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
看起来我们需要去和＃include 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
或者说，我们刚刚返回false  - 

563
00:44:59,800 --> 00:45:03,300
我们可以看到，它只是返回false，所有的人，

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
所以在这里，我们可以返回true。

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
它发现树中，没有找到10，因为10是不是在树中，

599
00:47:54,320 --> 00:47:57,740
并没有发现要么是因为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
因此，节点* N =的malloc（sizeof（节点）的）; N  - >值=值;

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
，你就有了 - 有人称之为一个malloc或realloc内 - 

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
但是，让我们做根* 3 = build_node（7）;节点= build_node（3）;

647
00:51:37,400 --> 00:51:47,980
节点* 6 = build_node（6）;节点* 9 = build_node（9）;。

648
00:51:47,980 --> 00:51:52,590
而现在，我们也想添加节点 - 

649
00:51:52,590 --> 00:52:03,530
节点* 5 = build_node（5）;节点* 8 = build_node（8）;

650
00:52:03,530 --> 00:52:09,760
什么是其他节点？让我们来看看这里。我们也想添加2  - 

651
00:52:09,760 --> 00:52:20,280
节点* 2 = build_node（2）;

652
00:52:20,280 --> 00:52:26,850
好吧。在这一点上，我们知道，我们已经得到了，3，9，7和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
我们知道，3的右孩子是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
为此，我们可以说，6  - > left_child = 5;

660
00:52:58,650 --> 00:53:10,790
然后在8属于左子9，9  - > left_child = 8;

661
00:53:10,790 --> 00:53:22,190
，然后是左子3，所以我们可以做的，在这里 - 你 - > left_child = 2;

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
然后我们就可以加入我们的CONTAINS调用。

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
我们将返回true，如果我们确实可以插入到树的节点上，

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
让我们把正上方的contains插入功能。

687
00:55:47,220 --> 00:55:56,360
再次，它被称为布尔插入（int值）。

688
00:55:56,360 --> 00:56:01,840
给它多一点空间，然后，在默认情况下，

689
00:56:01,840 --> 00:56:08,870
让我们在最后返回false。

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
逐一走下树1

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
在这里，我们将返回false。

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
>> 在这一点上，我们已经完成了这个while循环，

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
不为null，因为我们不希望开始访问的内存，如果它是空的。

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
，如果它是空的，那么我们就可以返回false早。

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
我们可以看到，我们用什么方法做这件事的时候，我们希望把树中的

746
01:01:08,470 --> 01:01:11,750
我们访问的左子根。

747
01:01:11,750 --> 01:01:14,920
当我们把在树中，我们不得不访问右子树的根。

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
我们将它设置为null最初，

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
因为在这里，我们从来没有进行测试，以确保的malloc返回一个有效的指针。

773
01:03:37,270 --> 01:03:53,390
所以，如果（N = NULL），然后 - 

774
01:03:53,390 --> 01:03:55,250
如果malloc返回一个有效的指针，那么我们就对它进行初始化;

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
>> 一切都返回false。

802
01:06:47,330 --> 01:06:53,830
因此，5，8，和2没有去，和它看起来像CONTAINS没有找到他们。

803
01:06:53,830 --> 01:06:58,890
这是怎么回事呢？让我们缩小。

804
01:06:58,890 --> 01:07:02,160
第一个问题是，插入似乎返回false，

805
01:07:02,160 --> 01:07:08,750
它看起来像，这是因为我们留在我们返回false，调用，

806
01:07:08,750 --> 01:07:14,590
我们从来没有真正返回true。

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
再次运行make，编译，然后运行它 - 

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
检查的价值 - 如果值是相同的，我们返回false。

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 C  - 

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
如果从来没有真正执行这个while循环

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
相反，在这里，我们可以做一个else if-else的，

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
我们看到，嗯，看起来像我们所有的插入返回true，这是很好的。

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
>> 好运气在这一周的Huffman编码问题集

913
01:16:12,880 --> 01:16:14,380
我们会下周见！

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]