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]