1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [第7條：更舒適]

2
00:00:02,770 --> 00:00:05,090
羅布·鮑登] [哈佛大學]

3
00:00:05,090 --> 00:00:07,930
[這是CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
好的。所以，像我在我的電子郵件中說，

5
00:00:10,110 --> 00:00:14,060
這將是一個二進制樹密集的部分。

6
00:00:14,060 --> 00:00:16,820
但也有很多問題。

7
00:00:16,820 --> 00:00:18,920
因此，我們將嘗試並繪製出每一個問題

8
00:00:18,920 --> 00:00:25,430
進入痛苦的細節做的事情的最好方法。

9
00:00:25,430 --> 00:00:31,200
所以，在開始的時候，我們去通過二進制樹之類的東西的樣品圖紙。

10
00:00:31,200 --> 00:00:35,970
所以在這裡，“請記住，一個二進制樹有類似的鍊錶節點，

11
00:00:35,970 --> 00:00:38,150
除，而不是一個指針有兩種：一種為在左邊的'孩子'

12
00:00:38,150 --> 00:00:41,950
和一個正確的'孩子'。“

13
00:00:41,950 --> 00:00:45,630
因此，一個二進制樹就像是一個鍊錶，

14
00:00:45,630 --> 00:00:47,910
除了結構有兩個指針。

15
00:00:47,910 --> 00:00:51,390
三元樹，這將有個三分球，

16
00:00:51,390 --> 00:00:56,540
有N-叉樹，其中有一個通用的指針

17
00:00:56,540 --> 00:01:00,320
就是你必須對malloc足夠大，有

18
00:01:00,320 --> 00:01:04,840
足夠的指點所有可能的孩子。

19
00:01:04,840 --> 00:01:08,200
因此，二叉樹正好有兩個固定數量的。

20
00:01:08,200 --> 00:01:11,260
如果你願意，你可以給一個鏈接列表為一元樹，

21
00:01:11,260 --> 00:01:15,360
但我不認為任何人都需要它，。

22
00:01:15,360 --> 00:01:18,060
“畫一個方框和箭頭圖的二進制樹節點

23
00:01:18,060 --> 00:01:24,110
Nate的最喜歡的數字，7，每個孩子指針為空。“

24
00:01:24,110 --> 00:01:27,780
因此，iPad模式。

25
00:01:27,780 --> 00:01:30,280
>> 這將是非常簡單的。

26
00:01:30,280 --> 00:01:36,150
我們只是有一個節點，我會畫一個矩形。

27
00:01:36,150 --> 00:01:38,730
我會在這裡得出的值。

28
00:01:38,730 --> 00:01:41,090
因此，該值將在這裡，

29
00:01:41,090 --> 00:01:44,770
，然後在這裡我們將不得不在右邊的左指針在左，右指針。

30
00:01:44,770 --> 00:01:50,430
這是非常多，所以約定來調用它左，右，指針名。

31
00:01:50,430 --> 00:01:52,460
這些都將是空。

32
00:01:52,460 --> 00:01:57,870
這將是空的，這只會是空的。

33
00:01:57,870 --> 00:02:03,630
好吧。因此，回到這裡。

34
00:02:03,630 --> 00:02:05,700
“一個鍊錶，我們只需要存儲一個指針

35
00:02:05,700 --> 00:02:09,639
在列表中的第一個節點是為了記住整個鍊錶，或整個列表。

36
00:02:09,639 --> 00:02:11,650
同樣，樹木，我們只需要存儲一個指針

37
00:02:11,650 --> 00:02:13,420
為了記住整個樹到單個節點。

38
00:02:13,420 --> 00:02:15,980
這是卡萊節點樹的“根”。

39
00:02:15,980 --> 00:02:18,320
從之前建立在你的圖，或畫一個新的

40
00:02:18,320 --> 00:02:21,690
這樣，你有一個盒子和箭頭描繪的二叉樹

41
00:02:21,690 --> 00:02:25,730
與7的值，然後3在左，

42
00:02:25,730 --> 00:02:32,760
然後9在右邊，然後6在右側的3。“

43
00:02:32,760 --> 00:02:34,810
讓我們來看看，如果我能記得所有這一切在我的腦海。

44
00:02:34,810 --> 00:02:37,670
因此，這將是我們的根在這裡。

45
00:02:37,670 --> 00:02:41,600
的地方，我們還會有一些指針的東西，我們會打電話給根，

46
00:02:41,600 --> 00:02:45,140
它指向了這個傢伙。

47
00:02:45,140 --> 00:02:48,490
現在一個新的節點，

48
00:02:48,490 --> 00:02:52,870
我們有什麼，在左邊嗎？

49
00:02:52,870 --> 00:02:57,140
因此，一個新的節點3，並它最初指向空。

50
00:02:57,140 --> 00:02:59,190
我就把N.

51
00:02:59,190 --> 00:03:02,250
現在，我們希望去左邊的7。

52
00:03:02,250 --> 00:03:06,840
因此，我們改變這個指針指向這個傢伙。

53
00:03:06,840 --> 00:03:12,420
我們這樣做。我們希望有一個在這裡

54
00:03:12,420 --> 00:03:14,620
它最初只是說空。

55
00:03:14,620 --> 00:03:19,600
我們要改變這個指針，指向9，

56
00:03:19,600 --> 00:03:23,310
現在我們要放6到右邊的3。

57
00:03:23,310 --> 00:03:32,170
因此，它要 -  6。

58
00:03:32,170 --> 00:03:34,310
那小子將指向。

59
00:03:34,310 --> 00:03:38,320
好吧。所以，這一切都要求我們做的。

60
00:03:38,320 --> 00:03:42,770
>> 現在，讓我們多一些術語。

61
00:03:42,770 --> 00:03:46,690
我們已經討論了如何樹的根是最頂端的樹中的節點。

62
00:03:46,690 --> 00:03:54,720
一個包含7。在樹的底部的節點被稱為葉子。

63
00:03:54,720 --> 00:04:01,240
任何節點作為其子空是葉。

64
00:04:01,240 --> 00:04:03,680
因此，它是可能的，如果我們的二進制樹只是一個單一的節點，

65
00:04:03,680 --> 00:04:10,130
一棵樹是一片葉子，就是這樣。

66
00:04:10,130 --> 00:04:12,060
“”高度“的樹是你必須做的跳數

67
00:04:12,060 --> 00:04:16,620
得到從頂端到葉子。“

68
00:04:16,620 --> 00:04:18,640
我們將進入，在第二，不同的

69
00:04:18,640 --> 00:04:21,940
之間的平衡和非平衡二叉樹，

70
00:04:21,940 --> 00:04:29,470
但現在，這種樹的整體高度

71
00:04:29,470 --> 00:04:34,520
我想說的是3，但如果你的跳數計數

72
00:04:34,520 --> 00:04:39,710
你必須為了得到9，那麼它真的只是一個身高2。

73
00:04:39,710 --> 00:04:43,340
現在這是一個不平衡的二叉樹，

74
00:04:43,340 --> 00:04:49,840
但我們會談論平衡時，它得到相關的。

75
00:04:49,840 --> 00:04:52,040
所以，現在我們可以談論一棵樹的節點在條款

76
00:04:52,040 --> 00:04:54,700
相對於樹中的其他節點。

77
00:04:54,700 --> 00:04:59,730
所以，現在我們有父母，子女，兄弟姐妹，祖先和子孫。

78
00:04:59,730 --> 00:05:05,650
他們是相當普遍的意義上說，他們的意思。

79
00:05:05,650 --> 00:05:09,610
如果我們問 - 它的父母。

80
00:05:09,610 --> 00:05:12,830
那麼，什麼是3的父？

81
00:05:12,830 --> 00:05:16,090
[學生] 7。 >>呀。家長只是要分給你。

82
00:05:16,090 --> 00:05:20,510
那麼什麼是兒童的7？

83
00:05:20,510 --> 00:05:23,860
[學生] 3和9。 >>呀。

84
00:05:23,860 --> 00:05:26,460
請注意，“孩子們”的字面意思是兒童，

85
00:05:26,460 --> 00:05:31,010
所以將不適用，因為它就像一個孫子。

86
00:05:31,010 --> 00:05:35,540
不過，如果我們去的後裔，所以是什麼7的後裔？

87
00:05:35,540 --> 00:05:37,500
[學生] 3，第6和第9。 >>呀。

88
00:05:37,500 --> 00:05:42,330
根節點的後代將是樹中的一切，

89
00:05:42,330 --> 00:05:47,950
可能除了根節點，如果你不想認為的後裔。

90
00:05:47,950 --> 00:05:50,750
最後，祖先，所以它是相反的方向。

91
00:05:50,750 --> 00:05:55,740
那麼，什麼是6的祖先嗎？

92
00:05:55,740 --> 00:05:58,920
[學生] 3和7。 >>呀。 9不包括在內。

93
00:05:58,920 --> 00:06:02,520
這僅僅是直接的後裔回到根

94
00:06:02,520 --> 00:06:13,230
將是你的祖先。

95
00:06:13,230 --> 00:06:16,300
>> “我們說，一個二叉樹是”責令“如果在樹中的每個節點，

96
00:06:16,300 --> 00:06:19,530
其後代在左側有小的值

97
00:06:19,530 --> 00:06:22,890
和在右邊的所有的那些有較大的值。

98
00:06:22,890 --> 00:06:27,060
例如，上面的樹是有序的，但它不是唯一可能的有序安排。“

99
00:06:27,060 --> 00:06:30,180
在我們到達，

100
00:06:30,180 --> 00:06:36,420
有序二元樹也被稱為二叉查找樹。

101
00:06:36,420 --> 00:06:38,660
在這裡，我們要求有序二元樹，

102
00:06:38,660 --> 00:06:41,850
但我從來沒有聽到它被稱為有序二元樹前，

103
00:06:41,850 --> 00:06:46,650
一個測驗，我們更​​傾向於把二叉搜索樹。

104
00:06:46,650 --> 00:06:49,250
它們是同一個，

105
00:06:49,250 --> 00:06:54,580
重要的是你認識二叉樹和二叉搜索樹的區別。

106
00:06:54,580 --> 00:06:58,830
二叉樹只是一棵樹，兩件事情。

107
00:06:58,830 --> 00:07:02,120
每個結點兩件事情。

108
00:07:02,120 --> 00:07:06,310
有沒有推理，它指向的值。

109
00:07:06,310 --> 00:07:11,370
所以想在這裡，因為它是一個二叉搜索樹，

110
00:07:11,370 --> 00:07:14,030
我們知道，如果我們向左走7，

111
00:07:14,030 --> 00:07:16,670
然後，我們能接觸到的所有的值

112
00:07:16,670 --> 00:07:19,310
將剩下的7必須是小於7。

113
00:07:19,310 --> 00:07:24,070
請注意，所有的值小於7的第3和第6。

114
00:07:24,070 --> 00:07:26,040
這些都是7左側。

115
00:07:26,040 --> 00:07:29,020
如果我們去7的權利，一切都必須大於7，

116
00:07:29,020 --> 00:07:33,220
因此9 7是正確的，所以我們是很好的。

117
00:07:33,220 --> 00:07:36,150
這是一個不為一個二進制樹的情況下，

118
00:07:36,150 --> 00:07:40,020
一個正規的二進制樹中，我們就可以有3個在頂部，7的左側，

119
00:07:40,020 --> 00:07:47,630
9至7的左側; theres沒有的值的任何順序。

120
00:07:47,630 --> 00:07:56,140
現在，我們將不能真正做到這一點，因為它的繁瑣和不必要的，

121
00:07:56,140 --> 00:07:59,400
但“試圖吸引盡可能多的有序樹，你能想到的

122
00:07:59,400 --> 00:08:01,900
使用的數字7，3，9和6。

123
00:08:01,900 --> 00:08:06,800
有多少個不同的安排？的高度，每一個是什麼？“

124
00:08:06,800 --> 00:08:10,480
>> 我們會做一對夫婦，但其主要思想是，

125
00:08:10,480 --> 00:08:16,530
這是在沒有辦法包含這些值的二進制樹的一個唯一的表示。

126
00:08:16,530 --> 00:08:22,760
我們需要的是一些二進制樹，它含有7，3，6，和9。

127
00:08:22,760 --> 00:08:25,960
另一個可能的有效的將3根，

128
00:08:25,960 --> 00:08:30,260
去的左側和它的6，去左邊，它是7，

129
00:08:30,260 --> 00:08:32,730
去的左側和它的9。

130
00:08:32,730 --> 00:08:36,169
這是一個非常有效的二叉搜索樹。

131
00:08:36,169 --> 00:08:39,570
這是不是非常有幫助，因為它就像一個鍊錶

132
00:08:39,570 --> 00:08:43,750
所有這些指針是空的。

133
00:08:43,750 --> 00:08:48,900
但是，它是一個有效的樹。是嗎？

134
00:08:48,900 --> 00:08:51,310
[學生]值必須在正確的嗎？

135
00:08:51,310 --> 00:08:56,700
或者是這樣的 - ？ >>我的意思是這些走另一條路。

136
00:08:56,700 --> 00:09:00,960
還有 - 是的，讓我們切換，。

137
00:09:00,960 --> 00:09:07,770
9，7，6，3。良好的漁獲物。

138
00:09:07,770 --> 00:09:11,730
它仍然有，服從什麼是二進制樹搜索是應該做的。

139
00:09:11,730 --> 00:09:15,650
所以一切向左側是小於任何給定的節點。

140
00:09:15,650 --> 00:09:23,180
我們可以只動，說，這6，把它放在這裡。

141
00:09:23,180 --> 00:09:26,880
不，我們不能。我為什麼這樣做呢？

142
00:09:26,880 --> 00:09:35,350
讓我們做 - 這裡是6，7，6點到3點。

143
00:09:35,350 --> 00:09:39,290
這仍然是一個有效的二叉搜索樹。

144
00:09:39,290 --> 00:09:49,260
什麼是錯的，如果我 - 讓我們來看看，如果我能想出​​的安排。

145
00:09:49,260 --> 00:09:52,280
是啊，好吧。那麼，什麼是錯的這棵樹嗎？

146
00:09:52,280 --> 00:10:08,920
我想我已經給你一個暗示，有什麼不對的地方。

147
00:10:08,920 --> 00:10:14,430
我為什麼這樣做呢？

148
00:10:14,430 --> 00:10:18,510
好吧。這看起來很合理的。

149
00:10:18,510 --> 00:10:22,590
如果我們看一下在每個節點上，如7，然後到左邊的7 3。

150
00:10:22,590 --> 00:10:24,960
因此，我們有3個，3的權利的東西是一個6。

151
00:10:24,960 --> 00:10:27,750
如果你看的東西的權利6 6，9。

152
00:10:27,750 --> 00:10:30,910
那麼，為什麼這不是一個有效的二叉搜索樹嗎？

153
00:10:30,910 --> 00:10:36,330
[學生] 9仍是7左側。 >>呀。

154
00:10:36,330 --> 00:10:43,710
它必須是真實的，所有你所能達到的左7的值都小於7。

155
00:10:43,710 --> 00:10:49,120
如果我們向左走7，我們得到的，我們仍然可以到6，

156
00:10:49,120 --> 00:10:52,520
我們仍然可以得到為9，但通過在經歷小於7，

157
00:10:52,520 --> 00:10:55,070
我們不應該能夠得到一個數字，大於7。

158
00:10:55,070 --> 00:10:59,830
因此，這是不是一個有效的二叉搜索樹。

159
00:10:59,830 --> 00:11:02,330
>> 我哥哥其實是有一個面試問題，

160
00:11:02,330 --> 00:11:07,760
這基本上是一些東西來驗證這一點，只是代碼

161
00:11:07,760 --> 00:11:10,500
一棵樹是一個二叉搜索樹，

162
00:11:10,500 --> 00:11:13,580
所以他做的第一件事是檢查，看看

163
00:11:13,580 --> 00:11:17,020
如果左邊和右邊是正確的，然後循環。

164
00:11:17,020 --> 00:11:19,700
但你不能做到這一點，你必須跟踪

165
00:11:19,700 --> 00:11:22,550
的事實，現在，我已經走了剩下的7，

166
00:11:22,550 --> 00:11:26,340
在這個子樹中的一切必須小於7。

167
00:11:26,340 --> 00:11:28,430
正確的算法需要跟踪

168
00:11:28,430 --> 00:11:35,970
的值的範圍可能裡鑽

169
00:11:35,970 --> 00:11:38,360
通過所有這些，我們不會去。

170
00:11:38,360 --> 00:11:41,630
有一個很好的遞推關係，

171
00:11:41,630 --> 00:11:44,810
雖然我們沒有得到這些，我們不會讓那些，

172
00:11:44,810 --> 00:11:47,030
確定有多少實際上是。

173
00:11:47,030 --> 00:11:53,180
因此，有14人。

174
00:11:53,180 --> 00:11:56,020
的想法，你會怎麼做數學是一樣的，

175
00:11:56,020 --> 00:11:59,770
你可以選擇任何一個節點是根，

176
00:11:59,770 --> 00:12:03,160
然後如果我選擇7根節點，

177
00:12:03,160 --> 00:12:08,150
再有，說一些數字，可以去我的左節點，

178
00:12:08,150 --> 00:12:10,440
有一些數字，可以成為我的右節點，

179
00:12:10,440 --> 00:12:15,090
但如果我有n個總人數，然後可以去左邊的金額

180
00:12:15,090 --> 00:12:18,820
加量，可以去右邊的是N  -  1。

181
00:12:18,820 --> 00:12:26,130
因此，剩餘的數字，它們可以去的左側或右側。

182
00:12:26,130 --> 00:12:31,580
這似乎很難，如果我把第一，然後一切都去左邊，

183
00:12:31,580 --> 00:12:35,080
但如果我把7，有些事情是可以走左邊，有些事情可以去正確的。

184
00:12:35,080 --> 00:12:39,570
'3第一，我的意思是什麼都可以去正確的。

185
00:12:39,570 --> 00:12:42,350
這是真的，你就必須把它作為，

186
00:12:42,350 --> 00:12:47,980
有多少東西可以去上了一個層次的樹。

187
00:12:47,980 --> 00:12:50,420
出來是14，或您可以繪製所有的這些，

188
00:12:50,420 --> 00:12:54,650
然後你會得到14。

189
00:12:54,650 --> 00:13:01,120
>> 讓我們再回到這裡，

190
00:13:01,120 --> 00:13:03,510
非常酷，因為我們可以通過搜索“有序二叉樹

191
00:13:03,510 --> 00:13:06,910
在一個非常類似的方式來尋找在一個排序的數組。

192
00:13:06,910 --> 00:13:10,120
要做到這一點，我們從根開始和工作的方式，在樹

193
00:13:10,120 --> 00:13:13,440
向葉，檢查每個節點的值與我們正在尋找的值。

194
00:13:13,440 --> 00:13:15,810
如果當前節點的值是小於該值，我們正在尋找，

195
00:13:15,810 --> 00:13:18,050
你去下一個節點的右孩子。

196
00:13:18,050 --> 00:13:20,030
否則，你去結點的左孩子。

197
00:13:20,030 --> 00:13:22,800
在某些時候，你會發現你正在尋找的價值，你會碰到一個空，

198
00:13:22,800 --> 00:13:28,520
的價值不是在樹上。“

199
00:13:28,520 --> 00:13:32,450
我要重繪我們面前的樹，要花幾秒鐘。

200
00:13:32,450 --> 00:13:38,280
但是，我們想看看是否6，10，和1是在樹中。

201
00:13:38,280 --> 00:13:49,180
因此，它是什麼，7，9，3，6。好吧。

202
00:13:49,180 --> 00:13:52,730
你想看看這些數字，我們要查找6。

203
00:13:52,730 --> 00:13:55,440
這種算法是如何工作的？

204
00:13:55,440 --> 00:14:03,040
好了，我們也有一些到樹的根指針。

205
00:14:03,040 --> 00:14:12,460
我們會去根說，這是價值相等的價值，我們正在尋找嗎？

206
00:14:12,460 --> 00:14:15,000
因此，我們正在尋找6，所以它是不相等的。

207
00:14:15,000 --> 00:14:20,140
因此，我們繼續前進，現在我們說，好了，所以6是小於7。

208
00:14:20,140 --> 00:14:23,940
這是否意味著我們想要去的左側，我們要向右走？

209
00:14:23,940 --> 00:14:27,340
[學生]。 >>呀。

210
00:14:27,340 --> 00:14:33,340
這是明顯更容易，所有你必須做的就是畫一個可能的樹節點

211
00:14:33,340 --> 00:14:37,760
然後你不知道不知道 - 而不是試圖想在你的頭上，

212
00:14:37,760 --> 00:14:40,020
沒關係，如果它的不足，我去左邊或走右邊，

213
00:14:40,020 --> 00:14:43,030
只是在看這幅畫，這是非常清楚的，我必須去左邊

214
00:14:43,030 --> 00:14:47,700
如果此節點是大於我在尋找的值。

215
00:14:47,700 --> 00:14:52,600
所以，你去左邊，現在我在3。

216
00:14:52,600 --> 00:14:57,770
我想 -  3是不到我在尋找的價值，這是6。

217
00:14:57,770 --> 00:15:03,420
所以，我們去正確的，現在我結束了在6，

218
00:15:03,420 --> 00:15:07,380
這是我要找的，所以我返回真值。

219
00:15:07,380 --> 00:15:15,760
我要尋找的下一個值是10。

220
00:15:15,760 --> 00:15:23,230
好吧。所以，現在，10  - 切斷 - 要遵循的根本。

221
00:15:23,230 --> 00:15:27,670
如今，10個是要大於7，所以我想看看的權利。

222
00:15:27,670 --> 00:15:31,660
10我要到這裡來，是要大於9，

223
00:15:31,660 --> 00:15:34,520
所以我想看看的權利。

224
00:15:34,520 --> 00:15:42,100
我來這裡，但在這裡，現在我在空。

225
00:15:42,100 --> 00:15:44,170
我該怎麼做，如果我打空？

226
00:15:44,170 --> 00:15:47,440
[學生]：返回假的？ >>呀。我沒有找到10。

227
00:15:47,440 --> 00:15:49,800
1將是幾乎相同的情況下，

228
00:15:49,800 --> 00:15:51,950
除了它只是要翻轉，而不是尋找

229
00:15:51,950 --> 00:15:56,540
右側向下，我要看看左側。

230
00:15:56,540 --> 00:16:00,430
>> 現在，我認為我們真正的代碼。

231
00:16:00,430 --> 00:16:04,070
這裡的地方 - 打開CS50設備和導航用自己的方式，

232
00:16:04,070 --> 00:16:07,010
但你也可以做到這一點的空間。

233
00:16:07,010 --> 00:16:09,170
做到這一點的空間，這也可能是理想的，

234
00:16:09,170 --> 00:16:13,760
因為我們可以工作的空間。

235
00:16:13,760 --> 00:16:19,170
他說：“首先，我們需要一個新的類型定義一個包含int值的二進制樹節點。

236
00:16:19,170 --> 00:16:21,400
使用的typedef以下的樣板，

237
00:16:21,400 --> 00:16:24,510
創建一個新的類型定義為一個二進制樹中的節點。

238
00:16:24,510 --> 00:16:27,930
如果你被卡住。 。 。 “等等，等等，等等。好。

239
00:16:27,930 --> 00:16:30,380
因此，讓我們把這裡的樣板，

240
00:16:30,380 --> 00:16:41,630
typedef結構節點和節點。是啊，好吧。

241
00:16:41,630 --> 00:16:44,270
那麼，什麼樣的領域，我們將要在我們的節點嗎？

242
00:16:44,270 --> 00:16:46,520
[學生]：int，然後兩個指針嗎？

243
00:16:46,520 --> 00:16:49,700
>> int值，兩個指針嗎？我怎樣寫指針嗎？

244
00:16:49,700 --> 00:16:58,440
[學生]結構。 >>我要放大是啊，所以結構節點離開，

245
00:16:58,440 --> 00:17:01,320
和結構節點*。

246
00:17:01,320 --> 00:17:03,460
請記住最後一次討論，

247
00:17:03,460 --> 00:17:15,290
這是沒有意義的，這是沒有意義的，

248
00:17:15,290 --> 00:17:18,270
這是沒有意義的。

249
00:17:18,270 --> 00:17:25,000
你需要的一切，以便確定這種遞歸結構。

250
00:17:25,000 --> 00:17:27,970
好了，所以這就是我們的樹是怎麼回事的樣子。

251
00:17:27,970 --> 00:17:37,670
如果我們做了一個三叉樹，然後一個節點可能看起來像B1，B2，結構節點* B3，

252
00:17:37,670 --> 00:17:43,470
其中b是一個分支 - 其實，我更聽到它的左，中，右，但不管。

253
00:17:43,470 --> 00:17:55,610
我們關心的只是二進制，右，左。

254
00:17:55,610 --> 00:17:59,110
“現在，聲明一個全局變量為根的樹節點*。”

255
00:17:59,110 --> 00:18:01,510
因此，我們不打算這樣做。

256
00:18:01,510 --> 00:18:08,950
為了使事情變得稍微更困難，更廣義的，

257
00:18:08,950 --> 00:18:11,570
我們不會有一個全球性的節點變量。

258
00:18:11,570 --> 00:18:16,710
相反，在主，我們將宣布我們的所有節點的事情，

259
00:18:16,710 --> 00:18:20,500
這意味著，在下面，當我們開始運行

260
00:18:20,500 --> 00:18:23,130
包含函數和我們的插入功能，

261
00:18:23,130 --> 00:18:27,410
而不是我們的CONTAINS函數只是使用這一全球性的節點變量，

262
00:18:27,410 --> 00:18:34,280
我們將它作為參數樹，我們希望它來處理。

263
00:18:34,280 --> 00:18:36,650
有全局變量應該使事情變得更容易。

264
00:18:36,650 --> 00:18:42,310
我們將讓事情變得更糟糕。

265
00:18:42,310 --> 00:18:51,210
現在只需要一分鐘左右的時間做這樣的事情，

266
00:18:51,210 --> 00:18:57,690
內的主要你要創建這個樹，這就是所有你想做的事。

267
00:18:57,690 --> 00:19:04,530
嘗試和構造這棵樹在您的主要功能。

268
00:19:42,760 --> 00:19:47,610
>> 好吧。所以，你甚至不必構建了樹的整個方式。

269
00:19:47,610 --> 00:19:49,840
但是，任何人有什麼我可以拉起來

270
00:19:49,840 --> 00:20:03,130
如何開始構建這樣的樹嗎？

271
00:20:03,130 --> 00:20:08,080
[學生]：有人撞，試圖擺脫。

272
00:20:08,080 --> 00:20:13,100
鮑登]的任何舒適與自己的樹建設？

273
00:20:13,100 --> 00:20:15,520
[學生]：當然可以。它沒有這樣做。 >>這是正常的。我們就可以完成 - 

274
00:20:15,520 --> 00:20:26,860
哦，你可以將它保存嗎？萬歲。

275
00:20:26,860 --> 00:20:32,020
所以，在這裡，我們有 - 哦，我有點切斷。

276
00:20:32,020 --> 00:20:34,770
我放大？

277
00:20:34,770 --> 00:20:37,730
縮放，滾動。 >>我有一個問題。 >>呀？

278
00:20:37,730 --> 00:20:44,410
[學生]：當你定義結構，是類的東西初始化到什麼？

279
00:20:44,410 --> 00:20:47,160
[鮑登號>>好。所以，你必須初始化 - 

280
00:20:47,160 --> 00:20:50,450
[鮑登號當你定義，或當你聲明一個結構，

281
00:20:50,450 --> 00:20:55,600
未初始化默認情況下，它就像如果你聲明一個int。

282
00:20:55,600 --> 00:20:59,020
這是完全一樣的東西。這就像其各自的領域

283
00:20:59,020 --> 00:21:04,460
可以有一個垃圾的價值所在。 “和它可能的定義 - 定義了一個struct

284
00:21:04,460 --> 00:21:07,740
在一種方式，它初始化它們？

285
00:21:07,740 --> 00:21:13,200
波頓：是的。所以，快捷的初始化語法

286
00:21:13,200 --> 00:21:18,660
是怎麼回事的樣子 - 

287
00:21:18,660 --> 00:21:22,200
有兩種方法，我們可以做到這一點。我認為，我們應該編譯它

288
00:21:22,200 --> 00:21:25,840
以確保鏘也這樣做了。

289
00:21:25,840 --> 00:21:28,510
參數順序的結構，

290
00:21:28,510 --> 00:21:32,170
你把這些花括號內的參數的順序。

291
00:21:32,170 --> 00:21:35,690
所以，如果你想要初始化它9空，然後右邊是空的，

292
00:21:35,690 --> 00:21:41,570
這將是9，NULL，NULL。

293
00:21:41,570 --> 00:21:47,890
另一種方法是，編輯器不喜歡這種語法，

294
00:21:47,890 --> 00:21:50,300
認為我想要一個新的塊，

295
00:21:50,300 --> 00:22:01,800
但另一種方法是類似的東西 - 

296
00:22:01,800 --> 00:22:04,190
這裡，我把它放在一個新行。

297
00:22:04,190 --> 00:22:09,140
你可以明確地說，我忘了確切的語法。

298
00:22:09,140 --> 00:22:13,110
所以，你可以明確地解決他們的名字，並說，

299
00:22:13,110 --> 00:22:21,570
c或。值= 9，左= NULL。

300
00:22:21,570 --> 00:22:24,540
我猜這些需要逗號。

301
00:22:24,540 --> 00:22:29,110
右= NULL，所以這樣一來，你不這樣做

302
00:22:29,110 --> 00:22:33,780
確實需要知道的結構順序，

303
00:22:33,780 --> 00:22:36,650
當你讀這篇文章，它更明確

304
00:22:36,650 --> 00:22:41,920
什麼價值被初始化。

305
00:22:41,920 --> 00:22:44,080
>> 這種情況發生的事情，是一個 - 

306
00:22:44,080 --> 00:22:49,100
因此，在大多數情況下，C + +是一個C的超集

307
00:22:49,100 --> 00:22:54,160
你可以把C代碼，將其移動到C + +，和它應該編譯。

308
00:22:54,160 --> 00:22:59,570
這是一個C + +不支持的事情，這樣的人往往不這樣做。

309
00:22:59,570 --> 00:23:01,850
我不知道如果這是唯一的原因，人們往往不這樣做，

310
00:23:01,850 --> 00:23:10,540
但需要的情況下，我需要使用C + +，所以我不能使用此工作。

311
00:23:10,540 --> 00:23:14,000
另一個例子的東西，不與C + +是

312
00:23:14,000 --> 00:23:16,940
如何malloc返回一個“無效*，”從技術上說，

313
00:23:16,940 --> 00:23:20,200
但你可以說的char * x = malloc的什麼，

314
00:23:20,200 --> 00:23:22,840
它會自動轉換為char *。

315
00:23:22,840 --> 00:23:25,450
該自動轉換不會發生在C + +。

316
00:23:25,450 --> 00:23:28,150
這將無法編譯，你會明確地說

317
00:23:28,150 --> 00:23:34,510
是char *，malloc的，不管結果如何，將它轉換為一個char *。

318
00:23:34,510 --> 00:23:37,270
不會有太多的事情，C和C + +不同意，

319
00:23:37,270 --> 00:23:40,620
但這些都是兩個。

320
00:23:40,620 --> 00:23:43,120
因此，我們將用這個語法。

321
00:23:43,120 --> 00:23:46,150
但是，即使我們沒有去與語法，

322
00:23:46,150 --> 00:23:49,470
是什麼 - 可能是錯的嗎？

323
00:23:49,470 --> 00:23:52,170
[學生]：我不需要取消對它的引用？ >>呀。

324
00:23:52,170 --> 00:23:55,110
請記住，箭頭有一個隱含的間接引用，

325
00:23:55,110 --> 00:23:58,230
所以當我們只是處理與結構，

326
00:23:58,230 --> 00:24:04,300
我們要使用的。在一個領域內的結構。

327
00:24:04,300 --> 00:24:07,200
我們想要做的唯一的一次是，當我們使用箭頭 - 

328
00:24:07,200 --> 00:24:13,450
，箭頭相當於 - 

329
00:24:13,450 --> 00:24:17,020
這將意味著什麼，如果我用箭頭。

330
00:24:17,020 --> 00:24:24,600
所有的箭頭表示，取消引用此，現在我在一個結構，我可以得到該領域。

331
00:24:24,600 --> 00:24:28,040
要么領域直接或間接引用，並獲得字段 - 

332
00:24:28,040 --> 00:24:30,380
我想這應該是價值。

333
00:24:30,380 --> 00:24:33,910
但是，我在這裡只是一個結構，而不是一個結構的指針來處理，

334
00:24:33,910 --> 00:24:38,780
所以我不能使用的箭頭。

335
00:24:38,780 --> 00:24:47,510
但是，這樣的事情我們可以做的所有節點上。

336
00:24:47,510 --> 00:24:55,790
哦，我的上帝。

337
00:24:55,790 --> 00:25:09,540
這是6，7，和3。

338
00:25:09,540 --> 00:25:16,470
然後我們就可以在我們的樹，設立了分公司，我們可以有7個 - 

339
00:25:16,470 --> 00:25:21,650
我們可以有，其左應指向3。

340
00:25:21,650 --> 00:25:25,130
那麼，如何才能做到這一點呢？

341
00:25:25,130 --> 00:25:29,320
[學生，不知所云] >>呀。節點3的地址，

342
00:25:29,320 --> 00:25:34,170
，如果你沒有地址，那麼就無法編譯。

343
00:25:34,170 --> 00:25:38,190
但要記住，這些都是到下一個節點的指針。

344
00:25:38,190 --> 00:25:44,930
正確的應該點到9，

345
00:25:44,930 --> 00:25:53,330
3至6點。

346
00:25:53,330 --> 00:25:58,480
我認為這是所有設置。有任何意見或問題？

347
00:25:58,480 --> 00:26:02,060
[學生，不知所云]根正在為7。

348
00:26:02,060 --> 00:26:08,210
我們只能說節點* =

349
00:26:08,210 --> 00:26:14,160
或根，=＆node7的。

350
00:26:14,160 --> 00:26:20,730
>> 對於我們的目的，我們將要處理的插入，

351
00:26:20,730 --> 00:26:25,490
所以，我們將要編寫一個函數插入到這個二叉樹

352
00:26:25,490 --> 00:26:34,230
並插入不可避免地會調用malloc來創建一個新的節點，這棵樹。

353
00:26:34,230 --> 00:26:36,590
因此，事情會變得混亂的事實，有些節點

354
00:26:36,590 --> 00:26:38,590
當前堆棧上

355
00:26:38,590 --> 00:26:43,680
與其他節點要結束的堆，當我們插入。

356
00:26:43,680 --> 00:26:47,640
這是完全有效的，但唯一的原因

357
00:26:47,640 --> 00:26:49,600
我們能夠做到這一點的堆棧

358
00:26:49,600 --> 00:26:51,840
是因為它是一個人為的例子，我們知道

359
00:26:51,840 --> 00:26:56,360
樹應該被構造為7，3，6，9。

360
00:26:56,360 --> 00:27:02,970
如果我們不具備這一點，那麼我們就沒有對malloc擺在首位。

361
00:27:02,970 --> 00:27:06,160
正如我們將看到的晚了一點，我們應該malloc'ing。

362
00:27:06,160 --> 00:27:08,570
現在它是完全合理的，放在堆棧中，

363
00:27:08,570 --> 00:27:14,750
但讓​​我們改變一個malloc實現。

364
00:27:14,750 --> 00:27:17,160
因此，這些現在是這樣的

365
00:27:17,160 --> 00:27:24,240
的節點* node9 = malloc的（如sizeof（節點））。

366
00:27:24,240 --> 00:27:28,040
現在，我們將不得不做我們的檢查。

367
00:27:28,040 --> 00:27:34,010
（node9 == NULL） - 我不想 - 

368
00:27:34,010 --> 00:27:40,950
返回1，那麼我們就可以做node9因為現在它是一個指針，

369
00:27:40,950 --> 00:27:45,300
值= 6，node9的左= NULL，

370
00:27:45,300 --> 00:27:48,930
node9  - > = NULL，

371
00:27:48,930 --> 00:27:51,410
我們將要做到這一點，每個節點。

372
00:27:51,410 --> 00:27:57,490
所以，讓我們把它裡面的一個單獨的函數。

373
00:27:57,490 --> 00:28:00,620
讓我們叫該節點* build_node，

374
00:28:00,620 --> 00:28:09,050
這是有點類似的API，我們提供的霍夫曼編碼。

375
00:28:09,050 --> 00:28:12,730
我們為您提供的初始化函數的樹

376
00:28:12,730 --> 00:28:20,520
拆解為這些樹木和森林相同的“功能”。

377
00:28:20,520 --> 00:28:22,570
>> 所以，在這裡我們將有一個初始化函數

378
00:28:22,570 --> 00:28:25,170
只是為我們建立一個節點。

379
00:28:25,170 --> 00:28:29,320
它看起來幾乎完全一樣這是怎麼回事。

380
00:28:29,320 --> 00:28:32,230
我我什至會偷懶，不改變的變量名，

381
00:28:32,230 --> 00:28:34,380
即使node9沒有任何意義了。

382
00:28:34,380 --> 00:28:38,610
哦，，我想node9的價值不應該被6。

383
00:28:38,610 --> 00:28:42,800
現在我們可以回到node9。

384
00:28:42,800 --> 00:28:49,550
在這裡，我們應該返回null。

385
00:28:49,550 --> 00:28:52,690
每個人都同意，構建一個節點的功能嗎？

386
00:28:52,690 --> 00:28:59,780
所以，現在我們可以直接調用的任何節點，建立與給定值和空指針。

387
00:28:59,780 --> 00:29:09,750
現在，我們可以調用，我們可以做節點* node9 = build_node（9）。

388
00:29:09,750 --> 00:29:25,810
讓我們做。 。 。

389
00:29:25,810 --> 00:29:33,980
6，3，7，6，3，7。

390
00:29:33,980 --> 00:29:39,330
現在我們要設置相同的指針，

391
00:29:39,330 --> 00:29:42,470
但現在一切都已經在指針

392
00:29:42,470 --> 00:29:48,480
因此不再需要的地址。

393
00:29:48,480 --> 00:29:56,300
好吧。那麼，什麼是我想要做的最後一件事嗎？

394
00:29:56,300 --> 00:30:03,850
有一個錯誤檢查，我不這樣做。

395
00:30:03,850 --> 00:30:06,800
什麼構建節點回報嗎？

396
00:30:06,800 --> 00:30:11,660
[學生，不知所云] >>呀。如果malloc失敗，它會返回null。

397
00:30:11,660 --> 00:30:16,460
所以，我要在這裡懶洋洋地把它放下，而不是做各自的條件。

398
00:30:16,460 --> 00:30:22,320
如果（node9 == NULL，或者 - 甚至更簡單，

399
00:30:22,320 --> 00:30:28,020
這相當於只是如果不node9。

400
00:30:28,020 --> 00:30:38,310
因此，如果不node9，或不node6，或沒有節點3，或不node7，返回1。

401
00:30:38,310 --> 00:30:42,850
也許我們應該打印的malloc失敗，或某事。

402
00:30:42,850 --> 00:30:46,680
[學生]：是虛假等於NULL作為嗎？

403
00:30:46,680 --> 00:30:51,290
鮑登任何零值是假的。

404
00:30:51,290 --> 00:30:53,920
因此，null是一個零值。

405
00:30:53,920 --> 00:30:56,780
零是零值。 False是一個零值。

406
00:30:56,780 --> 00:31:02,130
任何 - 幾乎只有2個零值是空的，零，

407
00:31:02,130 --> 00:31:07,900
假的就是哈希值被定義為“0”。

408
00:31:07,900 --> 00:31:13,030
這也適用於我們聲明了全局變量。

409
00:31:13,030 --> 00:31:17,890
如果我們確實有節點*的根在這裡，

410
00:31:17,890 --> 00:31:24,150
 - 有關全局變量是很好的事情，他們總是有一個初始值。

411
00:31:24,150 --> 00:31:27,500
這是不正確的功能，在這裡，

412
00:31:27,500 --> 00:31:34,870
如果我們有，像，節點*節點x。

413
00:31:34,870 --> 00:31:37,380
我們不知道x.value，x.whatever，

414
00:31:37,380 --> 00:31:40,700
或者我們也可以打印出來，他們可以是任意的。

415
00:31:40,700 --> 00:31:44,980
這是不正確的全局變量。

416
00:31:44,980 --> 00:31:47,450
所以的節點根或節點x。

417
00:31:47,450 --> 00:31:53,410
默認情況下，這是全球的一切，如果沒有顯式初始化為某個值，

418
00:31:53,410 --> 00:31:57,390
具有零值作為其值。

419
00:31:57,390 --> 00:32:01,150
節點*根，所以在這裡，我們沒有顯式初始化它的任何事情，

420
00:32:01,150 --> 00:32:06,350
所以它的默認值將是空的，這是零值的指針。

421
00:32:06,350 --> 00:32:11,870
默認的x的值將表示x.value為零，

422
00:32:11,870 --> 00:32:14,260
x.left為空，是空x.right。

423
00:32:14,260 --> 00:32:21,070
所以，因為它是一個結構，該結構中的所有領域的零值。

424
00:32:21,070 --> 00:32:24,410
我們並不需要使用，在這裡，雖然。

425
00:32:24,410 --> 00:32:27,320
[學生]比其他變量的結構是不同的，和其它變量

426
00:32:27,320 --> 00:32:31,400
垃圾值，這些都是零？

427
00:32:31,400 --> 00:32:36,220
[鮑登其他值。因此，在x，x將是零。

428
00:32:36,220 --> 00:32:40,070
如果它在全球範圍內，它有一個初始值。 “好了。

429
00:32:40,070 --> 00:32:48,950
鮑登無論是初始值你給或零。

430
00:32:48,950 --> 00:32:53,260
我認為所有這一切負責。

431
00:32:53,260 --> 00:32:58,390
>> 好吧。所以接下來的部分是問，

432
00:32:58,390 --> 00:33:01,260
“現在，我們要編寫一個函數調用包含

433
00:33:01,260 --> 00:33:04,930
布爾的原型包含的int值。“

434
00:33:04,930 --> 00:33:08,340
我們不打算做布爾包含的int值。

435
00:33:08,340 --> 00:33:15,110
我們的原型看起來像

436
00:33:15,110 --> 00:33:22,380
包含布爾（int值。

437
00:33:22,380 --> 00:33:24,490
然後，我們也將傳遞給它的樹

438
00:33:24,490 --> 00:33:28,870
它應該被檢查，看它是否具有該值。

439
00:33:28,870 --> 00:33:38,290
因此，節點樹）。好吧。

440
00:33:38,290 --> 00:33:44,440
然後，我們可以把它喜歡的東西，

441
00:33:44,440 --> 00:33:46,090
也許我們會想printf或什麼的。

442
00:33:46,090 --> 00:33:51,040
包含6，我們的根。

443
00:33:51,040 --> 00:33:54,300
這應該返回一個或真，

444
00:33:54,300 --> 00:33:59,390
而包含5根應該返回false。

445
00:33:59,390 --> 00:34:02,690
因此，需要實現這一點。

446
00:34:02,690 --> 00:34:06,780
你可以做到這一點的迭代或遞歸。

447
00:34:06,780 --> 00:34:09,739
的方式，我們已經設置的東西是美好的事情，

448
00:34:09,739 --> 00:34:12,300
它本身的遞歸解決方案更容易

449
00:34:12,300 --> 00:34:14,719
比全局變量的方式。

450
00:34:14,719 --> 00:34:19,750
因為如果我們只是有包含的int值，那麼我們就沒有辦法搜索子樹。

451
00:34:19,750 --> 00:34:24,130
我們就必須有一個單獨的輔助函數，遞歸我們的子樹。

452
00:34:24,130 --> 00:34:29,610
但因為我們已經改變了它的樹作為參數，

453
00:34:29,610 --> 00:34:32,760
它應該一直擺在首位，

454
00:34:32,760 --> 00:34:35,710
現在我們可以遞歸更容易。

455
00:34:35,710 --> 00:34:38,960
因此，迭代或遞歸的，我們就去了兩種，

456
00:34:38,960 --> 00:34:46,139
但我們會看到，遞歸端起來是很容易的。

457
00:34:59,140 --> 00:35:02,480
好吧。有沒有人有什麼我們可以使用嗎？

458
00:35:02,480 --> 00:35:12,000
>> [學生]：我有一個迭代的解決方案。 >>所有權利，迭代。

459
00:35:12,000 --> 00:35:16,030
好吧，這看起來不錯。

460
00:35:16,030 --> 00:35:18,920
所以，想通過它我們走？

461
00:35:18,920 --> 00:35:25,780
[學生]：當然可以。所以我設置一個臨時變量來獲得的第一個節點樹。

462
00:35:25,780 --> 00:35:28,330
然後我就通過，而溫度不等於空循環，

463
00:35:28,330 --> 00:35:31,700
因此，雖然仍然在樹中，我猜。

464
00:35:31,700 --> 00:35:35,710
並且如果該值是相等的值，temp被指向

465
00:35:35,710 --> 00:35:37,640
然後它返回該值。

466
00:35:37,640 --> 00:35:40,210
否則，它會檢查，如果是上的右側或左側。

467
00:35:40,210 --> 00:35:43,400
如果你有機會的情況下，有沒有更多的樹，

468
00:35:43,400 --> 00:35:47,330
那麼它的回報 - 退出循環，返回false。

469
00:35:47,330 --> 00:35:52,190
鮑登]好吧。因此，這似乎不錯。

470
00:35:52,190 --> 00:35:58,470
在任何問題上有任何人有任何意見？

471
00:35:58,470 --> 00:36:02,400
我沒有在所有的正確意見。

472
00:36:02,400 --> 00:36:11,020
有一件事我們可以做的就是這個傢伙。

473
00:36:11,020 --> 00:36:21,660
哦，這是要去一個小稍長。

474
00:36:21,660 --> 00:36:33,460
我會解決這個問題了。好吧。

475
00:36:33,460 --> 00:36:37,150
>> 每個人都應該還記得三元工作。

476
00:36:37,150 --> 00:36:38,610
有肯定是測驗在過去

477
00:36:38,610 --> 00:36:41,170
給你一個三元運算符的功能，

478
00:36:41,170 --> 00:36:45,750
說，翻譯，做一些不使用三元。

479
00:36:45,750 --> 00:36:49,140
所以這是一個很常見的情況時，我會覺得使用三元，

480
00:36:49,140 --> 00:36:54,610
其中，如果某些條件設置一個變量的東西，

481
00:36:54,610 --> 00:36:58,580
其他設置相同的變量別的東西。

482
00:36:58,580 --> 00:37:03,390
這件事情，這樣的事情很經常可以轉化為

483
00:37:03,390 --> 00:37:14,420
在那裡設置該變量 - 或者說，好了，這是真的嗎？然後，否則這一點。

484
00:37:14,420 --> 00:37:18,550
[學生]：第一個是，如果真實的，對不對？

485
00:37:18,550 --> 00:37:25,570
鮑登]是啊。我總是看它的方式是，溫度大於等於溫度值，

486
00:37:25,570 --> 00:37:30,680
然後，否則這一點。問一個問題。

487
00:37:30,680 --> 00:37:35,200
它更大的嗎？然後做的第一件事。否則做的第二件事情。

488
00:37:35,200 --> 00:37:41,670
我幾乎總是 - 結腸，我只是 - 我的頭，我讀別的。

489
00:37:41,670 --> 00:37:47,180
>> 有沒有人有一個遞歸的解決方案嗎？

490
00:37:47,180 --> 00:37:49,670
好吧。這一次，我們要 - 它可能已經是巨大的，

491
00:37:49,670 --> 00:37:53,990
但我們要使其更好。

492
00:37:53,990 --> 00:37:58,720
這幾乎是完全相同的想法。

493
00:37:58,720 --> 00:38:03,060
好，只是，你想解釋一下嗎？

494
00:38:03,060 --> 00:38:08,340
[學生]：當然可以。因此，我們確定該樹不為空，第一，

495
00:38:08,340 --> 00:38:13,380
因為如果樹是空的，那麼它會返回false，因為我們還沒有找到它。

496
00:38:13,380 --> 00:38:19,200
如果還是有一棵樹，我們進入 - 我們首先檢查該值是當前節點。

497
00:38:19,200 --> 00:38:23,740
如果是，則返回true，如果沒有，我們遞歸向左或向右。

498
00:38:23,740 --> 00:38:25,970
這聽起來是適當的嗎？ >>嗯，嗯。 （協議）

499
00:38:25,970 --> 00:38:33,880
所以注意到這幾乎是 - 結構非常相似，迭代求解。

500
00:38:33,880 --> 00:38:38,200
只是，而不是遞歸的，我們有一個while循環。

501
00:38:38,200 --> 00:38:40,840
而基地的情況下，這裡的樹不等於空

502
00:38:40,840 --> 00:38:44,850
的條件下，我們爆發出的while循環。

503
00:38:44,850 --> 00:38:50,200
他們是非常相似的。但是，我們要進一步採取這一步。

504
00:38:50,200 --> 00:38:54,190
現在，我們做同樣的事情在這裡。

505
00:38:54,190 --> 00:38:57,680
請注意，我們正在返回同樣的事情在這些線路，

506
00:38:57,680 --> 00:39:00,220
除了一個參數是不同的。

507
00:39:00,220 --> 00:39:07,950
因此，我們要到一個三元。

508
00:39:07,950 --> 00:39:13,790
我打選項的東西，它的象徵。好吧。

509
00:39:13,790 --> 00:39:21,720
因此，我們將返回包含。

510
00:39:21,720 --> 00:39:28,030
這是多行，好，放大它。

511
00:39:28,030 --> 00:39:31,060
通常情況下，作為一個文體的事情，我不認為很多人

512
00:39:31,060 --> 00:39:38,640
加一個空格後的箭頭，但我想，如果你是一致的，它的罰款。

513
00:39:38,640 --> 00:39:44,320
如果值是小於樹的價值，我們希望在樹上左遞歸的，

514
00:39:44,320 --> 00:39:53,890
否則，我們要遞歸樹權。

515
00:39:53,890 --> 00:39:58,610
所以這是第一個步驟，使這個看起來小一些。

516
00:39:58,610 --> 00:40:02,660
這個看起來小一些的第二步 - 

517
00:40:02,660 --> 00:40:09,150
我們可以將多行。

518
00:40:09,150 --> 00:40:16,500
好吧。使它看起來更小的第二步是在這裡，

519
00:40:16,500 --> 00:40:25,860
返回值等於樹的值，或包含什麼。

520
00:40:25,860 --> 00:40:28,340
>> 這是一個重要的事情。

521
00:40:28,340 --> 00:40:30,860
我不知道，如果他在課堂上說，它明確，

522
00:40:30,860 --> 00:40:34,740
但它被稱為短路的評價。

523
00:40:34,740 --> 00:40:41,060
這裡的想法是價值==樹價值。

524
00:40:41,060 --> 00:40:49,960
如果這是真的，那麼這是真實的，我們要'或'，無論是在這裡。

525
00:40:49,960 --> 00:40:52,520
因此，無論是在這裡，甚至沒有考慮，

526
00:40:52,520 --> 00:40:55,070
整個表達式將返回是什麼？

527
00:40:55,070 --> 00:40:59,430
[學生]：真？ >>是的，因為真實的東西，

528
00:40:59,430 --> 00:41:04,990
用OR  - 或真或運算與任何必然是真實的。

529
00:41:04,990 --> 00:41:08,150
因此，只要我們看到的返回值= tree值，

530
00:41:08,150 --> 00:41:10,140
我們只是返回true。

531
00:41:10,140 --> 00:41:15,710
甚至不打算進一步遞歸包含了就行了。

532
00:41:15,710 --> 00:41:20,980
我們可以採取這一步。

533
00:41:20,980 --> 00:41:29,490
返回樹不等於空，所有的一切。

534
00:41:29,490 --> 00:41:32,650
它做了一個在線的功能。

535
00:41:32,650 --> 00:41:36,790
這也是一個例子短路評價。

536
00:41:36,790 --> 00:41:40,680
但現在，它也是同樣的想法 - 

537
00:41:40,680 --> 00:41:47,320
而不是 - 所以，如果樹不等於空 - 或者說，好，

538
00:41:47,320 --> 00:41:49,580
如果樹不等於空，這是不好的情況下，

539
00:41:49,580 --> 00:41:54,790
如果樹等於null，那麼第一個條件是假的。

540
00:41:54,790 --> 00:42:00,550
所以假“與”與什麼將是什麼？

541
00:42:00,550 --> 00:42:04,640
[學生]假。 >>呀。這是短路評價的另一半，

542
00:42:04,640 --> 00:42:10,710
如果樹不等於空，然後我們都不會，甚至去的地方 - 

543
00:42:10,710 --> 00:42:14,930
獨木等於空，那麼我們就不會做價值==樹價值。

544
00:42:14,930 --> 00:42:17,010
我們只是要立即返回false。

545
00:42:17,010 --> 00:42:20,970
這是非常重要的，因為如果沒有短路求值，

546
00:42:20,970 --> 00:42:25,860
那麼，如果樹不等於空，這第二個條件是要賽格故障，

547
00:42:25,860 --> 00:42:32,510
因為樹>的值被提領空。

548
00:42:32,510 --> 00:42:40,490
所以，就是這樣。這一點 - 一旦過了轉移。

549
00:42:40,490 --> 00:42:44,840
這是一個很常見的事情，這個沒有這一行，

550
00:42:44,840 --> 00:42:49,000
但它是一個共同的東西的條件下，也許不正確的，

551
00:42:49,000 --> 00:42:59,380
但如果（樹！= NULL，和樹>的值==值），做任何事情。

552
00:42:59,380 --> 00:43:01,560
這是一個非常常見的情況，在那裡，而不必

553
00:43:01,560 --> 00:43:06,770
要打破這個分為兩個中頻，在那裡一樣，是樹空？

554
00:43:06,770 --> 00:43:11,780
好吧，這不是空的，所以現在是樹的值等於值嗎？做到這一點。

555
00:43:11,780 --> 00:43:17,300
相反，這種情況下，這將永遠段錯誤

556
00:43:17,300 --> 00:43:21,220
因為它會破壞，如果發生這種情況是空的。

557
00:43:21,220 --> 00:43:24,000
嗯，我想，如果你的樹是完全無效的指針，它仍然可以賽格故障，

558
00:43:24,000 --> 00:43:26,620
但它不能賽格故障，如果樹是空的。

559
00:43:26,620 --> 00:43:32,900
如果是空的，這將打破之前你曾經解除引用的指針擺在首位。

560
00:43:32,900 --> 00:43:35,000
[學生]：這是所謂的懶惰的評價嗎？

561
00:43:35,000 --> 00:43:40,770
>> [鮑登]懶惰的評價是一個獨立的東西。

562
00:43:40,770 --> 00:43:49,880
懶惰的評價更像是你要求的值，

563
00:43:49,880 --> 00:43:54,270
你問計算出一個數值，種，但你並不需要它立即。

564
00:43:54,270 --> 00:43:59,040
所以，直到你真正需要它，它不評估。

565
00:43:59,040 --> 00:44:03,920
這是不完全一樣的東西，但在霍夫曼的pset，

566
00:44:03,920 --> 00:44:06,520
它說，“懶洋洋”的編寫。

567
00:44:06,520 --> 00:44:08,670
我們這樣做的原因是因為我們實際上是在緩衝寫 - 

568
00:44:08,670 --> 00:44:11,820
我們不希望在同一時間寫的各個位，

569
00:44:11,820 --> 00:44:15,450
或單個字節的時間，而不是要得到一個塊的字節。

570
00:44:15,450 --> 00:44:19,270
然後，一旦我們有一個塊的字節，然後我們將它寫出來。

571
00:44:19,270 --> 00:44:22,640
即使你問它來寫 -  FWRITE和fread做同樣的事情。

572
00:44:22,640 --> 00:44:26,260
他們緩衝的讀取和寫入操作。

573
00:44:26,260 --> 00:44:31,610
即使你要求它立即寫入，它可能不會。

574
00:44:31,610 --> 00:44:34,540
你不能確定的東西都將被寫入

575
00:44:34,540 --> 00:44:37,540
直到你調用hfclose或不管它是什麼，

576
00:44:37,540 --> 00:44:39,620
然後說，好吧，我關閉我的文件，

577
00:44:39,620 --> 00:44:43,450
這意味著更好，我寫的一切，但我沒有寫。

578
00:44:43,450 --> 00:44:45,770
它不需要編寫了

579
00:44:45,770 --> 00:44:49,010
直到您關閉該文件，​​然後需要的地方。

580
00:44:49,010 --> 00:44:56,220
所以，這只是什麼懶 - 等待，直到它發生的。

581
00:44:56,220 --> 00:44:59,990
 - 以51你將進入更詳細，

582
00:44:59,990 --> 00:45:05,470
因為OCaml和一切，一切都在51遞歸。

583
00:45:05,470 --> 00:45:08,890
有沒有迭代的解決方案，基本上。

584
00:45:08,890 --> 00:45:11,550
一切都是遞歸和懶惰的評價

585
00:45:11,550 --> 00:45:14,790
很多情況下是非常重要的

586
00:45:14,790 --> 00:45:19,920
在那裡，如果你沒有懶洋洋地評估，這將意味著 - 

587
00:45:19,920 --> 00:45:24,760
該示例是流，這是無限長。

588
00:45:24,760 --> 00:45:30,990
從理論上講，你能想到的自然數為1-2-3-4-5-6-7流，

589
00:45:30,990 --> 00:45:33,090
所以，懶洋洋地評估事情的罰款。

590
00:45:33,090 --> 00:45:37,210
如果我說我想要的第十號，然後我就可以評估的10號。

591
00:45:37,210 --> 00:45:40,300
如果我想百分之一的數量，然後我就可以評估到百分之數量。

592
00:45:40,300 --> 00:45:46,290
沒有懶惰的評價，那麼它會嘗試立即評估所有的數字。

593
00:45:46,290 --> 00:45:50,000
您正在評估無限多的數字，這是根本不可能的。

594
00:45:50,000 --> 00:45:52,080
因此，有很多情況下，懶惰的評價

595
00:45:52,080 --> 00:45:57,840
得到的東西的工作是必不可少的。

596
00:45:57,840 --> 00:46:05,260
>> 現在，我們要編寫INSERT插入將是

597
00:46:05,260 --> 00:46:08,430
同樣改變在其定義中。

598
00:46:08,430 --> 00:46:10,470
所以，現在它的布爾插入（int值）。

599
00:46:10,470 --> 00:46:23,850
我們要改變這種狀況為bool插入（int值，節點樹）。

600
00:46:23,850 --> 00:46:29,120
我們實際上會改變，再次一點，我們就會明白為什麼。

601
00:46:29,120 --> 00:46:32,210
讓我們繼續前進build_node，只為它赫克，

602
00:46:32,210 --> 00:46:36,730
上面插入，所以我們沒有寫一個函數原型。

603
00:46:36,730 --> 00:46:42,450
這是一個暗示，你將要使用build_node在插入。

604
00:46:42,450 --> 00:46:49,590
好吧。 ，一分鐘的時間。

605
00:46:49,590 --> 00:46:52,130
我想我保存的版本，如果你想拉，

606
00:46:52,130 --> 00:47:00,240
或者，至少，我現在這樣。

607
00:47:00,240 --> 00:47:04,190
我想稍作休息時間，思考的邏輯插入，

608
00:47:04,190 --> 00:47:08,750
如果你無法想起來了。

609
00:47:08,750 --> 00:47:12,860
基本上，你將永遠只能被插入的葉子。

610
00:47:12,860 --> 00:47:18,640
想，如果我插入，然後我不可避免地將要插入1  - 

611
00:47:18,640 --> 00:47:21,820
我會改以黑色 - 我會在這裡插入1。

612
00:47:21,820 --> 00:47:28,070
或者，如果我插入，我要在這裡插入4。

613
00:47:28,070 --> 00:47:32,180
所以無論你做什麼，你要插入的葉​​子。

614
00:47:32,180 --> 00:47:36,130
所有你必須做的是遍歷樹，直到你得到的節點

615
00:47:36,130 --> 00:47:40,890
這應該是節點的父節點，新節點的父節點，

616
00:47:40,890 --> 00:47:44,560
然後改變其向左或向右的指針，這取決於是否

617
00:47:44,560 --> 00:47:47,060
它是大於或小於當前節點。

618
00:47:47,060 --> 00:47:51,180
修改這個指針指向新節點。

619
00:47:51,180 --> 00:48:05,490
所以遍歷樹的葉點到新的節點。

620
00:48:05,490 --> 00:48:09,810
也覺得為什麼會禁止這類情況之前，

621
00:48:09,810 --> 00:48:17,990
我構建二叉樹，它是正確的

622
00:48:17,990 --> 00:48:19,920
如果你只看著一個單一的節點，

623
00:48:19,920 --> 00:48:24,830
但9左側7，如果你遍歷了所有的方式。

624
00:48:24,830 --> 00:48:29,770
所以在這種情況下這是不可能的，因為 - 

625
00:48:29,770 --> 00:48:32,530
想插入的東西;（9）在第一個節點，

626
00:48:32,530 --> 00:48:35,350
我會看，我只是要到正確的。

627
00:48:35,350 --> 00:48:38,490
所以不管我做什麼，如果我插入到葉，

628
00:48:38,490 --> 00:48:40,790
，並使用合適的算法的葉，

629
00:48:40,790 --> 00:48:43,130
這將是不可能的，我插入9日至7左

630
00:48:43,130 --> 00:48:48,250
因為，只要我打7，我會去的權利。

631
00:48:59,740 --> 00:49:02,070
有沒有人有東西開始？

632
00:49:02,070 --> 00:49:05,480
[學生]：我做的。 “當然可以。

633
00:49:05,480 --> 00:49:09,200
[學生，不知所云]

634
00:49:09,200 --> 00:49:14,390
[其他學生，不知所云]

635
00:49:14,390 --> 00:49:18,330
[鮑登的讚賞。好吧。要解釋？

636
00:49:18,330 --> 00:49:20,690
>> [學生]因為我們知道，我們將

637
00:49:20,690 --> 00:49:24,060
新的節點，在樹的結尾，

638
00:49:24,060 --> 00:49:28,070
我循環通過迭代樹

639
00:49:28,070 --> 00:49:31,360
直到我得到了一個節點，指出為空。

640
00:49:31,360 --> 00:49:34,220
然後，我決定把它的右側或左側

641
00:49:34,220 --> 00:49:37,420
使用此變量，它告訴我把它放在哪裡。

642
00:49:37,420 --> 00:49:41,850
然後，從本質上講，我只是做，最後 - 

643
00:49:41,850 --> 00:49:47,520
該臨時結點，它是創造新的節點，

644
00:49:47,520 --> 00:49:50,770
無論是在左側或右側，這取決於什麼值權。

645
00:49:50,770 --> 00:49:56,530
最後，我設置了新的節點值，其測試值。

646
00:49:56,530 --> 00:49:59,550
[鮑登]好了，所以我在這裡看到一個問題。

647
00:49:59,550 --> 00:50:02,050
這是95％的方式存在的。

648
00:50:02,050 --> 00:50:07,550
一個問題，我看到，沒有任何人看到一個問題嗎？

649
00:50:07,550 --> 00:50:18,400
的情況下，他們跳出循環是什麼？

650
00:50:18,400 --> 00:50:22,100
[學生]：如果temp是空的？ >>呀。因此，如何跳出循環，是如果溫度為空。

651
00:50:22,100 --> 00:50:30,220
但是，我該怎麼辦就在這裡嗎？

652
00:50:30,220 --> 00:50:35,410
我解引用的溫度，這是不可避免的空。

653
00:50:35,410 --> 00:50:39,840
因此，其他的事情，你需要做的不只是跟踪，直到溫度是空的，

654
00:50:39,840 --> 00:50:45,590
你要跟踪的父母在任何時候都。

655
00:50:45,590 --> 00:50:52,190
我們也希望*父節點，我想我們可以保持，空第一。

656
00:50:52,190 --> 00:50:55,480
這是要為根的樹有怪異的行為，

657
00:50:55,480 --> 00:50:59,210
但我們會得到的。

658
00:50:59,210 --> 00:51:03,950
如果值是大於任何，然後TEMP =臨時的權利。

659
00:51:03,950 --> 00:51:07,910
但在此之前我們做到這一點，父母溫度。

660
00:51:07,910 --> 00:51:14,500
或者父母總是平等的溫度嗎？是這樣呢？

661
00:51:14,500 --> 00:51:19,560
如果溫度不為空，然後我要向下移動，不管是什麼，

662
00:51:19,560 --> 00:51:24,030
temp是父節點。

663
00:51:24,030 --> 00:51:27,500
所以，家長會為temp，然後我謹溫度下降。

664
00:51:27,500 --> 00:51:32,410
現在的溫度是空的，但父母的事情是空的父。

665
00:51:32,410 --> 00:51:39,110
所以在這裡，我不希望設置等於1。

666
00:51:39,110 --> 00:51:41,300
所以，我移動到右側，因此，如果右= 1，

667
00:51:41,300 --> 00:51:45,130
我猜你也想這樣做 - 

668
00:51:45,130 --> 00:51:48,530
如果你移動到左邊，你要設置等於0。

669
00:51:48,530 --> 00:51:55,950
否則，如果你移動到右側。

670
00:51:55,950 --> 00:51:58,590
所以右側= 0。如果右= 1，

671
00:51:58,590 --> 00:52:04,260
現在我們要父權指針newnode，

672
00:52:04,260 --> 00:52:08,520
否則，我們想使父左指針newnode。

673
00:52:08,520 --> 00:52:16,850
該問題嗎？

674
00:52:16,850 --> 00:52:24,880
好吧。因此，這是我們的方式 - 好吧，其實不是這樣做，而是

675
00:52:24,880 --> 00:52:29,630
我們一半預計您使用build_node。

676
00:52:29,630 --> 00:52:40,450
然後，如果newnode等於null，則返回false。

677
00:52:40,450 --> 00:52:44,170
就是這樣。現在，這是我們希望你做什麼。

678
00:52:44,170 --> 00:52:47,690
>> 這是工作人員解決方案做什麼。

679
00:52:47,690 --> 00:52:52,360
我不同意這是“正確”的方式去了解它

680
00:52:52,360 --> 00:52:57,820
但是，這是完全沒有問題的，它會工作。

681
00:52:57,820 --> 00:53:02,840
有一件事，這是一個有點古怪，現在是

682
00:53:02,840 --> 00:53:08,310
如果樹為空，我們傳遞了一個空樹。

683
00:53:08,310 --> 00:53:12,650
我想這取決於你如何定義傳遞一個空樹的行為。

684
00:53:12,650 --> 00:53:15,490
我認為，如果你傳遞一個空樹，

685
00:53:15,490 --> 00:53:17,520
然後插入值到一個空的樹

686
00:53:17,520 --> 00:53:23,030
應該只返回一個唯一的價值是單個節點的樹中。

687
00:53:23,030 --> 00:53:25,830
人們同意嗎？你可以，如果你想，

688
00:53:25,830 --> 00:53:28,050
如果你傳遞一個空的樹

689
00:53:28,050 --> 00:53:31,320
你想插入值，則返回false。

690
00:53:31,320 --> 00:53:33,830
它是由你來定義。

691
00:53:33,830 --> 00:53:38,320
要我說，然後做的第一件事 - 

692
00:53:38,320 --> 00:53:40,720
好了，你打算這樣做有問題，因為

693
00:53:40,720 --> 00:53:44,090
如果我們有一個全局指針的東西，它會更容易，

694
00:53:44,090 --> 00:53:48,570
但我們沒有，所以，如果樹是空的，有什麼我們可以做的。

695
00:53:48,570 --> 00:53:50,960
我們就可以返回false。

696
00:53:50,960 --> 00:53:52,840
所以我要改變插入。

697
00:53:52,840 --> 00:53:56,540
我們在技術上可以只改變這一權利在這裡，

698
00:53:56,540 --> 00:53:58,400
它是如何遍歷的事情，

699
00:53:58,400 --> 00:54:04,530
但我要改變插入一個節點**樹。

700
00:54:04,530 --> 00:54:07,510
雙指針。

701
00:54:07,510 --> 00:54:09,710
這是什麼意思呢？

702
00:54:09,710 --> 00:54:12,330
而不是處理的節點的指針，

703
00:54:12,330 --> 00:54:16,690
我要操作的東西是這樣的指針。

704
00:54:16,690 --> 00:54:18,790
我要操縱這些指針。

705
00:54:18,790 --> 00:54:21,770
我要直接操縱指針。

706
00:54:21,770 --> 00:54:25,760
這是有道理的，因為，想想下來 - 

707
00:54:25,760 --> 00:54:33,340
好了，現在這點為空。

708
00:54:33,340 --> 00:54:38,130
我想要做的是操作這個指針指向為NOT NULL。

709
00:54:38,130 --> 00:54:40,970
我想它指向我的新節點。

710
00:54:40,970 --> 00:54:44,870
如果我只是記錄我的指針的指針，

711
00:54:44,870 --> 00:54:47,840
然後，我不需要跟踪的父指針。

712
00:54:47,840 --> 00:54:52,640
我就可以跟踪看，如果指針指向空，

713
00:54:52,640 --> 00:54:54,580
如果指針指向為null，

714
00:54:54,580 --> 00:54:57,370
將其更改為指向我想要的節點。

715
00:54:57,370 --> 00:55:00,070
我可以改變它，因為我有一個指針的指針。

716
00:55:00,070 --> 00:55:02,040
讓我們來看看這個權利。

717
00:55:02,040 --> 00:55:05,470
實際上，你可以遞歸很容易地做到這一點。

718
00:55:05,470 --> 00:55:08,080
我們要做到這一點呢？

719
00:55:08,080 --> 00:55:10,980
是的，我們做的。

720
00:55:10,980 --> 00:55:16,790
>> 讓我們來看看它遞歸。

721
00:55:16,790 --> 00:55:24,070
首先，什麼是我們的基本情況又如何呢？

722
00:55:24,070 --> 00:55:29,140
幾乎永遠是我們的基本情況，但實際上，這是一種棘手的。

723
00:55:29,140 --> 00:55:34,370
首先第一件事情，如果（樹== NULL）

724
00:55:34,370 --> 00:55:37,550
我想我們只是要返回false。

725
00:55:37,550 --> 00:55:40,460
樹是空的，這是不同的。

726
00:55:40,460 --> 00:55:44,510
這就是指針到你的根指針為null

727
00:55:44,510 --> 00:55:48,360
這意味著你的根指針不存在。

728
00:55:48,360 --> 00:55:52,390
因此，在這裡，如果我這樣做

729
00:55:52,390 --> 00:55:55,760
節點*  - 讓我們只是重複。

730
00:55:55,760 --> 00:55:58,960
節點根= NULL，

731
00:55:58,960 --> 00:56:00,730
，然後我就打電話給插入，做這樣的事情，

732
00:56:00,730 --> 00:56:04,540
和根中插入4。

733
00:56:04,540 --> 00:56:06,560
因此，根，如果根是一個節點*

734
00:56:06,560 --> 00:56:11,170
然後與根將是一個節點**。

735
00:56:11,170 --> 00:56:15,120
這是有效的。在這種情況下，樹，在這裡，

736
00:56:15,120 --> 00:56:20,120
樹不為空 - 或插入。

737
00:56:20,120 --> 00:56:24,630
在這裡。樹不空; *樹為空，這是很好

738
00:56:24,630 --> 00:56:26,680
*樹，因為如果是空的，那麼我可以操縱它

739
00:56:26,680 --> 00:56:29,210
現在指向什麼，我想它指向。

740
00:56:29,210 --> 00:56:34,750
但是，如果樹是空的，這意味著我來到這裡，說空。

741
00:56:34,750 --> 00:56:42,710
這沒有任何意義。我不能做什麼用的。

742
00:56:42,710 --> 00:56:45,540
如果樹是空的，則返回false。

743
00:56:45,540 --> 00:56:48,220
所以，我基本上已經說了我們真正的基本情況是什麼。

744
00:56:48,220 --> 00:56:50,580
那是什麼打算？

745
00:56:50,580 --> 00:56:55,030
[學生，不知所云]

746
00:56:55,030 --> 00:57:00,000
波頓：是的。所以，如果（*樹== NULL）。

747
00:57:00,000 --> 00:57:04,520
這涉及到的情況下在這裡

748
00:57:04,520 --> 00:57:09,640
我的紅色指針，如果指針，我很專注，

749
00:57:09,640 --> 00:57:12,960
我集中在這指針一樣，現在我專注於這個指針。

750
00:57:12,960 --> 00:57:15,150
現在我專注於這個指針。

751
00:57:15,150 --> 00:57:18,160
所以，如果我的紅色指針，這是我的節點**

752
00:57:18,160 --> 00:57:22,880
曾經是 - 如果*，我的紅色指針，是以往任何時候都為空，

753
00:57:22,880 --> 00:57:28,470
這意味著，我在我專注於一個指針指向的情況下 - 

754
00:57:28,470 --> 00:57:32,530
這是一個指針，屬於一片葉子。

755
00:57:32,530 --> 00:57:41,090
我想改變這個指針指向我的新節點。

756
00:57:41,090 --> 00:57:45,230
快回來。

757
00:57:45,230 --> 00:57:56,490
我的newnode將是節點* N = build_node（值）

758
00:57:56,490 --> 00:58:07,300
那麼n，如果n = NULL，則返回false。

759
00:58:07,300 --> 00:58:12,600
否則，我們要改變指針指向

760
00:58:12,600 --> 00:58:17,830
現在我們新建的節點。

761
00:58:17,830 --> 00:58:20,280
事實上，我們可以做到這一點。

762
00:58:20,280 --> 00:58:30,660
而不是說Ň，我們說* = *樹的樹。

763
00:58:30,660 --> 00:58:35,450
每個人都明白嗎？ ，處理指向指針的指針，

764
00:58:35,450 --> 00:58:40,750
我們可以改變空指針指向它們指向我們想要的東西。

765
00:58:40,750 --> 00:58:42,820
這是我們的基本情況。

766
00:58:42,820 --> 00:58:45,740
>> 現在，我們的復發，或我們的遞歸，

767
00:58:45,740 --> 00:58:51,430
將是非常相似，我們已經做了所有其他的遞歸。

768
00:58:51,430 --> 00:58:55,830
我們將要插入的值，

769
00:58:55,830 --> 00:58:59,040
現在我要再次使用三元，但我們的條件是什麼要？

770
00:58:59,040 --> 00:59:05,180
它是什麼，我們要尋找的決定，我們是否要向左走還是向右？

771
00:59:05,180 --> 00:59:07,760
讓我們這樣做在單獨的步驟。

772
00:59:07,760 --> 00:59:18,850
（值）是什麼？

773
00:59:18,850 --> 00:59:23,200
[學生]：這棵樹的價值？

774
00:59:23,200 --> 00:59:27,490
鮑登所以請記住，我目前 - 

775
00:59:27,490 --> 00:59:31,260
[學生，不知所云]

776
00:59:31,260 --> 00:59:34,140
[鮑登]是啊，所以就在這裡，讓我們說，這個綠色的箭頭

777
00:59:34,140 --> 00:59:39,050
是什麼樹目前是一個例子，是一個指針，該指針。

778
00:59:39,050 --> 00:59:46,610
因此，這意味著我是一個指針，指向一個指針，指向3。

779
00:59:46,610 --> 00:59:48,800
兩次解引用聽起來不錯。

780
00:59:48,800 --> 00:59:51,010
這是什麼 - 怎麼我做的是什麼？

781
00:59:51,010 --> 00:59:53,210
[學生]：取消引用一次，然後做箭頭？

782
00:59:53,210 --> 00:59:58,420
[鮑登]（樹）提領一次， - >值

783
00:59:58,420 --> 01:00:05,960
是想給我的價值，我間接指向的節點。

784
01:00:05,960 --> 01:00:11,980
所以我也可以寫它** tree.value的，如果你喜歡。

785
01:00:11,980 --> 01:00:18,490
無論是工作的。

786
01:00:18,490 --> 01:00:26,190
如果是這樣的話，那麼我想打電話給插入與價值。

787
01:00:26,190 --> 01:00:32,590
什麼是我更新的節點**又如何呢？

788
01:00:32,590 --> 01:00:39,440
我想往左走，所以** tree.left的將是我的左手。

789
01:00:39,440 --> 01:00:41,900
我想這東西的指針

790
01:00:41,900 --> 01:00:44,930
所以，如果左邊的結束是空指針，

791
01:00:44,930 --> 01:00:48,360
我可以修改它指向我的新節點。

792
01:00:48,360 --> 01:00:51,460
>> 其他情況下，可以是非常相似的。

793
01:00:51,460 --> 01:00:55,600
其實，我的三元現在。

794
01:00:55,600 --> 01:01:04,480
插入值，如果值<（**樹）。值。

795
01:01:04,480 --> 01:01:11,040
然後我們要更​​新我們的**的左側，

796
01:01:11,040 --> 01:01:17,030
否則，我們要更新我們的**的權利。

797
01:01:17,030 --> 01:01:22,540
[學生]：那拿到的指針的指針？

798
01:01:22,540 --> 01:01:30,940
鮑登 -  ** tree.right是節點的明星。

799
01:01:30,940 --> 01:01:35,040
[學生，不知所云] >>呀。

800
01:01:35,040 --> 01:01:41,140
** tree.right是這樣的指針或什麼的。

801
01:01:41,140 --> 01:01:45,140
因此，通過一個指向，這給了我我想要的

802
01:01:45,140 --> 01:01:50,090
那傢伙的指針。

803
01:01:50,090 --> 01:01:54,260
[學生]：我們能不能走一遍，為什麼我們使用的是兩個指針嗎？

804
01:01:54,260 --> 01:01:58,220
鮑登]是啊。所以 - 不，你可以，而且該解決方案之前

805
01:01:58,220 --> 01:02:04,540
一種方法做這件事而不做兩個指針。

806
01:02:04,540 --> 01:02:08,740
你需要能夠了解兩個指針，

807
01:02:08,740 --> 01:02:11,660
這是一個清潔的解決方案。

808
01:02:11,660 --> 01:02:16,090
另外，請注意，會發生什麼，如果我的樹 - 

809
01:02:16,090 --> 01:02:24,480
發生什麼，如果我的根目錄為空？在這裡如果我這樣做的情況下，會發生什麼情況？

810
01:02:24,480 --> 01:02:30,540
因此，節點*根= NULL，插入4到與根。

811
01:02:30,540 --> 01:02:35,110
什麼是根將是在此之後呢？

812
01:02:35,110 --> 01:02:37,470
[學生，不知所云] >>呀。

813
01:02:37,470 --> 01:02:41,710
根值是4。

814
01:02:41,710 --> 01:02:45,510
根左邊的這個是空的，根本的權利是空的。

815
01:02:45,510 --> 01:02:49,490
的情況下，我們沒有通過根地址，

816
01:02:49,490 --> 01:02:52,490
我們不能修改根。

817
01:02:52,490 --> 01:02:56,020
樹 - 根為空的情況下，

818
01:02:56,020 --> 01:02:58,410
我們剛剛返回false。我們沒有什麼可以做的。

819
01:02:58,410 --> 01:03:01,520
我們不能插入到一個空的樹節點。

820
01:03:01,520 --> 01:03:06,810
但現在我們可以到一個節點樹，我們只是一個空的樹。

821
01:03:06,810 --> 01:03:13,400
這通常是預期的方式，它應該工作。

822
01:03:13,400 --> 01:03:21,610
>> 此外，這是顯著短於

823
01:03:21,610 --> 01:03:26,240
跟踪的父母，所以你遍歷了所有的方式。

824
01:03:26,240 --> 01:03:30,140
現在，我有我的父母，我只是有我的父權的任何指針。

825
01:03:30,140 --> 01:03:35,640
相反，如果我們這樣做迭代，它會是一個while循環同樣的想法。

826
01:03:35,640 --> 01:03:38,100
但不是我的父指針處理，

827
01:03:38,100 --> 01:03:40,600
而不是我現在的指針的東西

828
01:03:40,600 --> 01:03:43,790
我直接修改指向我的新節點。

829
01:03:43,790 --> 01:03:46,090
我沒有處理，無論是指向左邊。

830
01:03:46,090 --> 01:03:48,810
我沒有處理是否指向正確的。

831
01:03:48,810 --> 01:04:00,860
這只是不管這個指針，我將其設置為指向我的新節點。

832
01:04:00,860 --> 01:04:05,740
每個人都明白它是如何工作的？

833
01:04:05,740 --> 01:04:09,460
如果沒有，為什麼我們想這樣做，這樣一來，

834
01:04:09,460 --> 01:04:14,920
但至少，這個工程作為一個解決方案？

835
01:04:14,920 --> 01:04:17,110
[學生]：我們從哪裡傳回是真的嗎？

836
01:04:17,110 --> 01:04:21,550
鮑登這很可能就在這裡。

837
01:04:21,550 --> 01:04:26,690
如果我們正確地插入，則返回true。

838
01:04:26,690 --> 01:04:32,010
否則，在這裡我們將要返回任何插入的回報。

839
01:04:32,010 --> 01:04:35,950
>> 和有關這個遞歸函數有什麼特別呢？

840
01:04:35,950 --> 01:04:43,010
這是尾遞歸的，所以只要我們編譯了一些優化，

841
01:04:43,010 --> 01:04:48,060
它會認識到，你將永遠不會得到一個堆棧溢出，

842
01:04:48,060 --> 01:04:53,230
即使我們的樹的高度1萬或10萬。

843
01:04:53,230 --> 01:04:55,630
[學生，不知所云]

844
01:04:55,630 --> 01:05:00,310
[鮑登]我認為它在短跑 - 優化級別

845
01:05:00,310 --> 01:05:03,820
需要被認可為一個尾遞歸。

846
01:05:03,820 --> 01:05:09,350
我認為它承認 -  GCC和Clang的

847
01:05:09,350 --> 01:05:12,610
也有不同的含義的優化水平。

848
01:05:12,610 --> 01:05:17,870
我想說這是達紹2，為確保它會識別尾遞歸。

849
01:05:17,870 --> 01:05:27,880
但是，我們 - 你可以構建這樣一個Fibonocci的例子或什麼的。

850
01:05:27,880 --> 01:05:30,030
這是不容易的測試，因為它是難以建立

851
01:05:30,030 --> 01:05:32,600
這麼大的一個二叉樹。

852
01:05:32,600 --> 01:05:37,140
但是，是的，我認為這是達紹2，

853
01:05:37,140 --> 01:05:40,580
如果在編譯時使用達紹2，它會尋找尾遞歸

854
01:05:40,580 --> 01:05:54,030
並優化了這一點。

855
01:05:54,030 --> 01:05:58,190
讓我們回去 - 插入從字面上它需要的最後一件事。

856
01:05:58,190 --> 01:06:04,900
讓我們回到在這裡插入

857
01:06:04,900 --> 01:06:07,840
我們要去的地方，做同樣的想法。

858
01:06:07,840 --> 01:06:14,340
它仍然有缺陷，不能夠完全處理

859
01:06:14,340 --> 01:06:17,940
當根目錄本身是空的，或在過去的項目是空的，

860
01:06:17,940 --> 01:06:20,060
但是，而不是處理與父母指針，

861
01:06:20,060 --> 01:06:27,430
讓我們應用同樣的邏輯，保持指針的指針。

862
01:06:27,430 --> 01:06:35,580
如果我們保持我們的節點**當前，

863
01:06:35,580 --> 01:06:37,860
而我們不需要跟踪了，

864
01:06:37,860 --> 01:06:47,190
但節點**當前和樹。

865
01:06:47,190 --> 01:06:54,800
現在，我們的while循環將是*電流不等於空。

866
01:06:54,800 --> 01:07:00,270
不需要跟踪的父母了。

867
01:07:00,270 --> 01:07:04,180
不要需要跟踪的左邊和右邊。

868
01:07:04,180 --> 01:07:10,190
我會打電話給它溫度，因為我們已經使用溫度。

869
01:07:10,190 --> 01:07:17,200
好吧。所以，如果（值> *溫度），

870
01:07:17,200 --> 01:07:24,010
（臨時） - >右鍵

871
01:07:24,010 --> 01:07:29,250
TEMP =＆（*溫度） - >離開。

872
01:07:29,250 --> 01:07:32,730
而現在，在這一點上，這個while循環後，

873
01:07:32,730 --> 01:07:36,380
我只能這樣做，因為也許它更容易比遞歸迭代想想，

874
01:07:36,380 --> 01:07:39,010
但這個while循環後，

875
01:07:39,010 --> 01:07:43,820
* temp是我們要改變的指針。

876
01:07:43,820 --> 01:07:48,960
>> 之前，我們的父母，我們想改變父母任何一方左或父權，

877
01:07:48,960 --> 01:07:51,310
但如果我們想改變家長的權利，

878
01:07:51,310 --> 01:07:54,550
*溫度是父母的權利，我們可以直接改變它。

879
01:07:54,550 --> 01:08:05,860
所以在這裡，我們可以做TEMP = newnode，這就是它。

880
01:08:05,860 --> 01:08:09,540
因此，通知，我們在這行代碼。

881
01:08:09,540 --> 01:08:14,770
為了保持軌道是額外的努力在所有的父。

882
01:08:14,770 --> 01:08:18,689
在這裡，如果我們只是一味地跟踪指針的指針，

883
01:08:18,689 --> 01:08:22,990
即使我們想擺脫現在所有這些大括號中，

884
01:08:22,990 --> 01:08:27,170
使它看起來更短。

885
01:08:27,170 --> 01:08:32,529
這現在是完全一樣的解決方案，

886
01:08:32,529 --> 01:08:38,210
但更少的代碼行。

887
01:08:38,210 --> 01:08:41,229
一旦你開始認識到這是一個有效的解決方案，

888
01:08:41,229 --> 01:08:43,529
它也更容易的原因有關，而不像，沒關係，

889
01:08:43,529 --> 01:08:45,779
為什麼我有這個標誌的詮釋權嗎？

890
01:08:45,779 --> 01:08:49,290
這是什麼意思呢？哦，這是表示

891
01:08:49,290 --> 01:08:51,370
我每次去正確的，我需要設置，

892
01:08:51,370 --> 01:08:53,819
否則，如果我向左走，我需要將其設置為零。

893
01:08:53,819 --> 01:09:04,060
在這裡，我沒有原因有關，它只是更容易思考的問題。

894
01:09:04,060 --> 01:09:06,710
有問題嗎？

895
01:09:06,710 --> 01:09:16,290
[學生，不知所云] >>呀。

896
01:09:16,290 --> 01:09:23,359
好了，所以在最後一位 - 

897
01:09:23,359 --> 01:09:28,080
我想一個快速和簡單的函數，我們可以做的是，

898
01:09:28,080 --> 01:09:34,910
let's  - 一起，我想嘗試寫一個包含函數

899
01:09:34,910 --> 01:09:38,899
不關心它是否是一個二叉搜索樹。

900
01:09:38,899 --> 01:09:43,770
這包含函數應返回TRUE

901
01:09:43,770 --> 01:09:58,330
如果在此二叉樹的價值是我們正在尋找的任何地方。

902
01:09:58,330 --> 01:10:02,520
因此，讓我們第一次做遞歸和迭代，我們將做到這一點。

903
01:10:02,520 --> 01:10:07,300
事實上，我們可以做起來，因為這將是非常短的。

904
01:10:07,300 --> 01:10:11,510
>> 什麼是我的基本情況又如何呢？

905
01:10:11,510 --> 01:10:13,890
[學生，不知所云]

906
01:10:13,890 --> 01:10:18,230
[鮑登]所以，​​如果（樹== NULL），然後呢？

907
01:10:18,230 --> 01:10:22,740
[學生]：返回false。

908
01:10:22,740 --> 01:10:26,160
[鮑登否則，好了，我不需要別的。

909
01:10:26,160 --> 01:10:30,250
如果是我的基本情況。

910
01:10:30,250 --> 01:10:32,450
[學生]：樹的價值呢？ >>呀。

911
01:10:32,450 --> 01:10:36,430
所以，如果（樹 - >值==值。

912
01:10:36,430 --> 01:10:39,920
請注意，我們又回到了節點*，而不是節點的**嗎？

913
01:10:39,920 --> 01:10:42,990
蘊涵永遠不會需要使用一個節點**

914
01:10:42,990 --> 01:10:45,480
因為我們沒有修改指針。

915
01:10:45,480 --> 01:10:50,540
我們只是遍歷。

916
01:10:50,540 --> 01:10:53,830
如果出現這種情況，那麼，我們要返回true。

917
01:10:53,830 --> 01:10:58,270
否則，我們要遍歷的孩子。

918
01:10:58,270 --> 01:11:02,620
因此，我們不能推理是否所有的左邊是

919
01:11:02,620 --> 01:11:05,390
的一切權利。

920
01:11:05,390 --> 01:11:09,590
那麼，什麼是我們的條件，要在這裡 - 或者說，什麼是我們該怎麼辦？

921
01:11:09,590 --> 01:11:11,840
[學生，不知所云] >>呀。

922
01:11:11,840 --> 01:11:17,400
返回包含（價值樹 - >左）

923
01:11:17,400 --> 01:11:26,860
或（價值樹 - >右）。就是這樣。

924
01:11:26,860 --> 01:11:29,080
發現有短路的評價，

925
01:11:29,080 --> 01:11:32,520
如果我們碰巧發現在左邊的樹形，

926
01:11:32,520 --> 01:11:36,820
我們永遠需要尋找正確的樹。

927
01:11:36,820 --> 01:11:40,430
這是整個函數。

928
01:11:40,430 --> 01:11:43,690
現在，讓我們做迭代，

929
01:11:43,690 --> 01:11:48,060
這將是那麼好。

930
01:11:48,060 --> 01:11:54,750
我們將採取一貫的起始節點的電流=樹。

931
01:11:54,750 --> 01:12:03,250
雖然（當前= NULL）。

932
01:12:03,250 --> 01:12:08,600
快速將看到一個問題。

933
01:12:08,600 --> 01:12:12,250
如果電流 - 在這裡，如果我們打破這個，

934
01:12:12,250 --> 01:12:16,020
然後，我們已經用完了的事情來看待，所以返回false。

935
01:12:16,020 --> 01:12:24,810
如果（當前值==值），則返回true。

936
01:12:24,810 --> 01:12:32,910
所以，現在，我們是在一個地方 - 

937
01:12:32,910 --> 01:12:36,250
我們不知道，我們是否要向左走還是向右。

938
01:12:36,250 --> 01:12:44,590
所以，隨意，讓我​​們去離開。

939
01:12:44,590 --> 01:12:47,910
顯然，我遇到一個問題，我已經完全放棄一切 - 

940
01:12:47,910 --> 01:12:50,760
我將永遠只能檢查左側的樹。

941
01:12:50,760 --> 01:12:56,050
我永遠都不會檢查任何孩子的東西是正確的。

942
01:12:56,050 --> 01:13:00,910
我該如何解決這個問題？

943
01:13:00,910 --> 01:13:05,260
[學生]：您有堆棧跟踪的左，右。

944
01:13:05,260 --> 01:13:13,710
鮑登]是啊。所以，讓我們把它

945
01:13:13,710 --> 01:13:32,360
結構列表，節點n，然後節點**嗎？

946
01:13:32,360 --> 01:13:40,240
我認為正常工作。

947
01:13:40,240 --> 01:13:45,940
我們想要去的左，或let's  - 在這裡。

948
01:13:45,940 --> 01:13:54,350
結構列表的列表=，它會開始

949
01:13:54,350 --> 01:13:58,170
出在這個結構列表。

950
01:13:58,170 --> 01:14:04,040
*列表= NULL。所以這將是我們的鍊錶

951
01:14:04,040 --> 01:14:08,430
子樹，我們已經跳過了。

952
01:14:08,430 --> 01:14:13,800
我們要遍歷現在剩下的，

953
01:14:13,800 --> 01:14:17,870
但由於我們無可避免地要回來的右側，

954
01:14:17,870 --> 01:14:26,140
我們要保持我們的結構列表內的右側。

955
01:14:26,140 --> 01:14:32,620
然後，我們，將有new_list或結構，

956
01:14:32,620 --> 01:14:41,080
結構列表，new_list的malloc（sizeof（列表）的）。

957
01:14:41,080 --> 01:14:44,920
我要忽略錯誤檢查，但你應該檢查，看它是否為NULL。

958
01:14:44,920 --> 01:14:50,540
New_list的節點，它的指向 - 

959
01:14:50,540 --> 01:14:56,890
哦，我想這就是為什麼它在這裡。要指出的第二個結構列表。

960
01:14:56,890 --> 01:15:02,380
這是多麼鍊錶的工作。

961
01:15:02,380 --> 01:15:04,810
這是相同的作為一個int鍊錶

962
01:15:04,810 --> 01:15:06,960
除了我們剛剛更換的int節點*。

963
01:15:06,960 --> 01:15:11,040
這是完全一樣的。

964
01:15:11,040 --> 01:15:15,100
所以new_list，的價值我們的new_list節點，

965
01:15:15,100 --> 01:15:19,120
會是電流>右鍵。

966
01:15:19,120 --> 01:15:24,280
我們new_list的價值 - >明年將是我們原來的名單，

967
01:15:24,280 --> 01:15:30,760
然後我們來更新我們的列表中指向new_list的。

968
01:15:30,760 --> 01:15:33,650
>> 現在，我們需要某種方式拉的東西，

969
01:15:33,650 --> 01:15:37,020
就像我們所走過的整個左子樹。

970
01:15:37,020 --> 01:15:40,480
現在我們需要把它拉出來的東西，

971
01:15:40,480 --> 01:15:43,850
如當前是空的，我們不希望只是返回false。

972
01:15:43,850 --> 01:15:50,370
我們現在要在外面拉我們新的列表。

973
01:15:50,370 --> 01:15:53,690
一種方便的方法，這樣做的 - 其實，有多種方式這樣做。

974
01:15:53,690 --> 01:15:56,680
任何人有建議嗎？

975
01:15:56,680 --> 01:15:58,790
在哪裡我應該這樣做，或者我應該這樣做嗎？

976
01:15:58,790 --> 01:16:08,010
我們只有一兩分鐘，但有什麼建議？

977
01:16:08,010 --> 01:16:14,750
相反 - 的一種方式，而不是我們的條件，同時，

978
01:16:14,750 --> 01:16:17,090
我們目前正在不為空，

979
01:16:17,090 --> 01:16:22,340
相反，我們要繼續走，直到我們的名單本身是空的。

980
01:16:22,340 --> 01:16:25,680
因此，如果我們的列表為空，

981
01:16:25,680 --> 01:16:30,680
然後我們跑出來的東西，尋找，搜尋。

982
01:16:30,680 --> 01:16:39,860
但是，這意味著在我們的名單的第一件事，只是將第一個節點。

983
01:16:39,860 --> 01:16:49,730
的第一件事是 - 我們不再需要看到的。

984
01:16:49,730 --> 01:16:58,710
所以列表 - > n將是我們的樹。

985
01:16:58,710 --> 01:17:02,860
列表 - >下一個會是空的。

986
01:17:02,860 --> 01:17:07,580
而現在名單不等於空。

987
01:17:07,580 --> 01:17:11,610
cur是要拉的東西從我們的名單。

988
01:17:11,610 --> 01:17:13,500
因此，當前要平等列表 - > N。

989
01:17:13,500 --> 01:17:20,850
，然後列出要平等列表 - > N，或列表下。

990
01:17:20,850 --> 01:17:23,480
因此，如果當前值等於值。

991
01:17:23,480 --> 01:17:28,790
現在我們可以添加我們的權利，指針和我們的左指針

992
01:17:28,790 --> 01:17:32,900
只要他們不為空。

993
01:17:32,900 --> 01:17:36,390
到這裡，我想我們應該這樣做，是擺在首位。

994
01:17:36,390 --> 01:17:44,080
如果（電流>好吧！= NULL）

995
01:17:44,080 --> 01:17:56,380
那麼，我們該節點將要插入到我們的名單。

996
01:17:56,380 --> 01:17:59,290
如果（電流左），這是一點點額外的工作，但它的罰款。

997
01:17:59,290 --> 01:18:02,690
如果（電流左！= NULL），

998
01:18:02,690 --> 01:18:14,310
我們要我們的鍊錶中插入左，

999
01:18:14,310 --> 01:18:19,700
這應該是它。

1000
01:18:19,700 --> 01:18:22,670
我們遍歷 - 只要我們有一些在我們的名單，

1001
01:18:22,670 --> 01:18:26,640
我們有另一個節點來看看。

1002
01:18:26,640 --> 01:18:28,920
因此，我們期待在該節點上，

1003
01:18:28,920 --> 01:18:31,390
我們推進我們的列表中的下一個。

1004
01:18:31,390 --> 01:18:34,060
如果該節點是我們正在尋找的價值，我們就可以返回true。

1005
01:18:34,060 --> 01:18:37,640
否則插入我們的左，右子樹，

1006
01:18:37,640 --> 01:18:40,510
只要他們不為空，進入我們的名單

1007
01:18:40,510 --> 01:18:43,120
所以，我們不可避免地走了他們。

1008
01:18:43,120 --> 01:18:45,160
所以，如果他們不為空，

1009
01:18:45,160 --> 01:18:47,950
如果我們的根指針指向兩件事情，

1010
01:18:47,950 --> 01:18:51,670
然後我們把車停在​​第一的東西，所以我們的列表為空。

1011
01:18:51,670 --> 01:18:56,890
然後我們把兩件事情回來，所以現在我們的名單是大小為2。

1012
01:18:56,890 --> 01:19:00,030
那我們是要循環，我們只是要拉，

1013
01:19:00,030 --> 01:19:04,250
比方說，我們的根結點的左指針。

1014
01:19:04,250 --> 01:19:07,730
那將只是不斷發生，我們將結束循環一切。

1015
01:19:07,730 --> 01:19:11,280
>> 請注意，這是顯著更複雜

1016
01:19:11,280 --> 01:19:14,160
在遞歸的解決方案。

1017
01:19:14,160 --> 01:19:17,260
我已經說過多次，

1018
01:19:17,260 --> 01:19:25,120
的遞歸解決方案通常有很多共同之處，與迭代求解。

1019
01:19:25,120 --> 01:19:30,820
在這裡，這是什麼做的遞歸解決方案。

1020
01:19:30,820 --> 01:19:36,740
唯一的變化是，而不是隱式地使用堆棧，程序堆棧，

1021
01:19:36,740 --> 01:19:40,840
跟踪哪些節點需要訪問的方式，

1022
01:19:40,840 --> 01:19:45,430
現在，你必須明確地使用鍊錶。

1023
01:19:45,430 --> 01:19:49,070
在這兩種情況下，你跟踪哪些節點仍然需要訪問。

1024
01:19:49,070 --> 01:19:51,790
在遞歸的情況下，它只是更容易，因為堆棧

1025
01:19:51,790 --> 01:19:57,100
你的程序堆棧來實現。

1026
01:19:57,100 --> 01:19:59,550
請注意，此鏈接的列表，這是一個堆棧。

1027
01:19:59,550 --> 01:20:01,580
無論我們只是把在堆棧上

1028
01:20:01,580 --> 01:20:09,960
我們馬上要去拉斷的堆棧訪問下。

1029
01:20:09,960 --> 01:20:14,380
我們沒時間了，但什麼問題嗎？

1030
01:20:14,380 --> 01:20:23,530
[學生，不知所云]

1031
01:20:23,530 --> 01:20:27,790
鮑登]是啊。所以，如果我們有我們的鏈接列表，

1032
01:20:27,790 --> 01:20:30,150
當前要指向這個傢伙，

1033
01:20:30,150 --> 01:20:34,690
現在我們只是推動我們的聯名單專注於這傢伙。

1034
01:20:34,690 --> 01:20:44,200
我們穿越過該行的鍊錶中。

1035
01:20:44,200 --> 01:20:51,200
然後，我想我們應該幫助我們的鍊錶之類的東西

1036
01:20:51,200 --> 01:20:53,880
前一次返回true或false，我們需要

1037
01:20:53,880 --> 01:20:57,360
我們的鍊錶遍歷，並一直在這裡，我想，

1038
01:20:57,360 --> 01:21:03,900
如果我們當前不等於，添加它，所以現在我們要釋放

1039
01:21:03,900 --> 01:21:09,600
電流，因為，我們完全忘了該列表？是啊。

1040
01:21:09,600 --> 01:21:12,880
所以，這就是我們想要做的。

1041
01:21:12,880 --> 01:21:16,730
指針在哪裡？

1042
01:21:16,730 --> 01:21:23,320
當前是 - 我們需要一個結構列表* 10等於列表旁邊。

1043
01:21:23,320 --> 01:21:29,240
免費列表，列表溫度。

1044
01:21:29,240 --> 01:21:32,820
的情況下，我們返回true，我們需要遍歷

1045
01:21:32,820 --> 01:21:37,050
在剩餘的聯繫列表中解放出來的東西。

1046
01:21:37,050 --> 01:21:39,700
美好的事情被釋放的遞歸解決方案

1047
01:21:39,700 --> 01:21:44,930
只是意味著會發生堆棧中彈出承購關閉。

1048
01:21:44,930 --> 01:21:50,720
因此，我們已經走了的東西，就像3行認為難以對代碼

1049
01:21:50,720 --> 01:21:57,520
顯著更多的東西，是很難認為有關的代碼行。

1050
01:21:57,520 --> 01:22:00,620
還有什麼問題嗎？

1051
01:22:00,620 --> 01:22:08,760
好的。我們是很好的。再見！

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