1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Phần 7: thoải mái hơn]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Đại học Harvard]

3
00:00:05,090 --> 00:00:07,930
[Đây là CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Được rồi. Vì vậy, như tôi đã nói trong email của tôi,

5
00:00:10,110 --> 00:00:14,060
điều này là có được một phần nhị phân cây thâm canh.

6
00:00:14,060 --> 00:00:16,820
Tuy nhiên, không phải là rất nhiều câu hỏi.

7
00:00:16,820 --> 00:00:18,920
Vì vậy, chúng tôi sẽ cố gắng và rút ra mỗi câu hỏi

8
00:00:18,920 --> 00:00:25,430
và đi vào chi tiết đau đớn của tất cả các cách thực hiện tốt nhất.

9
00:00:25,430 --> 00:00:31,200
Vì vậy, ngay từ đầu, chúng tôi đi qua các bản vẽ mẫu của cây nhị phân và các công cụ.

10
00:00:31,200 --> 00:00:35,970
Vì vậy, ở đây, "Hãy nhớ rằng một cây nhị phân có các nút tương tự như những người của một danh sách liên kết,

11
00:00:35,970 --> 00:00:38,150
ngoại trừ thay vì một con trỏ có hai: một cho 'con' bên trái

12
00:00:38,150 --> 00:00:41,950
và một cho đứa trẻ phải ".

13
00:00:41,950 --> 00:00:45,630
Vì vậy, một cây nhị phân giống như một danh sách liên kết,

14
00:00:45,630 --> 00:00:47,910
ngoại trừ cấu trúc là sẽ có hai con trỏ.

15
00:00:47,910 --> 00:00:51,390
Có cây trinary, mà sẽ có ba con trỏ,

16
00:00:51,390 --> 00:00:56,540
có cây N-ary, mà chỉ có một con trỏ chung chung

17
00:00:56,540 --> 00:01:00,320
mà sau đó bạn phải malloc để có đủ lớn để có

18
00:01:00,320 --> 00:01:04,840
con trỏ đủ để tất cả các trẻ em có thể.

19
00:01:04,840 --> 00:01:08,200
Vì vậy, cây nhị phân chỉ xảy ra để có một hằng số của hai.

20
00:01:08,200 --> 00:01:11,260
Nếu bạn muốn, bạn có thể cho một danh sách liên kết như là một cây unary,

21
00:01:11,260 --> 00:01:15,360
nhưng tôi không nghĩ rằng bất cứ ai gọi nó mà.

22
00:01:15,360 --> 00:01:18,060
"Vẽ một sơ đồ hộp và mũi tên của một nút cây nhị phân

23
00:01:18,060 --> 00:01:24,110
có chứa số yêu thích của Nate, 7, nơi mỗi con trỏ con là null. "

24
00:01:24,110 --> 00:01:27,780
Vì vậy, iPad chế độ.

25
00:01:27,780 --> 00:01:30,280
>> Nó sẽ là khá đơn giản.

26
00:01:30,280 --> 00:01:36,150
Chúng tôi chỉ cần đi để có một nút, tôi sẽ vẽ nó như một hình vuông.

27
00:01:36,150 --> 00:01:38,730
Và tôi sẽ rút ra những giá trị ở đây.

28
00:01:38,730 --> 00:01:41,090
Vì vậy, giá trị sẽ đi ở đây,

29
00:01:41,090 --> 00:01:44,770
và sau đó xuống đây chúng tôi sẽ có con trỏ bên trái bên trái và con trỏ bên phải bên phải.

30
00:01:44,770 --> 00:01:50,430
Và nó là rất nhiều để quy ước để gọi nó là trái và phải, tên con trỏ.

31
00:01:50,430 --> 00:01:52,460
Cả hai sẽ được null.

32
00:01:52,460 --> 00:01:57,870
Điều đó sẽ chỉ là vô giá trị, và đó sẽ chỉ là vô giá trị.

33
00:01:57,870 --> 00:02:03,630
Okay. Vì vậy, sao ở đây.

34
00:02:03,630 --> 00:02:05,700
"Với một danh sách liên kết, chúng tôi chỉ có để lưu trữ một con trỏ

35
00:02:05,700 --> 00:02:09,639
nút đầu tiên trong danh sách để nhớ những danh sách liên kết toàn bộ, hoặc tất cả danh sách.

36
00:02:09,639 --> 00:02:11,650
Tương tự như vậy, với cây xanh, chúng tôi chỉ có để lưu trữ một con trỏ

37
00:02:11,650 --> 00:02:13,420
một nút duy nhất để nhớ toàn bộ cây.

38
00:02:13,420 --> 00:02:15,980
Nút này calle 'root' của cây.

39
00:02:15,980 --> 00:02:18,320
Xây dựng dựa trên sơ đồ của bạn từ trước hoặc vẽ một cái mới

40
00:02:18,320 --> 00:02:21,690
như vậy mà bạn có một mô tả hộp và mũi tên của một cây nhị phân

41
00:02:21,690 --> 00:02:25,730
với các giá trị 7, sau đó 3 ở bên trái,

42
00:02:25,730 --> 00:02:32,760
sau đó 9 ở bên phải, và sau đó 6 trên bên phải của 3 ".

43
00:02:32,760 --> 00:02:34,810
Hãy xem nếu tôi có thể nhớ tất cả những điều đó trong đầu tôi.

44
00:02:34,810 --> 00:02:37,670
Vì vậy, đây sẽ là root của chúng tôi ở đây.

45
00:02:37,670 --> 00:02:41,600
Chúng tôi sẽ có một số con trỏ một nơi nào đó, một cái gì đó mà chúng ta sẽ gọi gốc,

46
00:02:41,600 --> 00:02:45,140
và nó chỉ với anh chàng này.

47
00:02:45,140 --> 00:02:48,490
Bây giờ để làm một nút mới,

48
00:02:48,490 --> 00:02:52,870
chúng ta có gì, 3 ở bên trái?

49
00:02:52,870 --> 00:02:57,140
Vì vậy, một nút mới có 3, và ban đầu nó chỉ vô giá trị.

50
00:02:57,140 --> 00:02:59,190
Tôi sẽ chỉ đưa N.

51
00:02:59,190 --> 00:03:02,250
Bây giờ chúng tôi muốn làm đó đi đến bên trái của 7.

52
00:03:02,250 --> 00:03:06,840
Vì vậy, chúng tôi thay đổi con trỏ trỏ đến anh chàng này.

53
00:03:06,840 --> 00:03:12,420
Và chúng tôi làm như vậy. Chúng tôi muốn có một 9 trên đây

54
00:03:12,420 --> 00:03:14,620
mà ban đầu chỉ nói null.

55
00:03:14,620 --> 00:03:19,600
Chúng tôi sẽ thay đổi con trỏ này, điểm đến 9,

56
00:03:19,600 --> 00:03:23,310
và bây giờ chúng tôi muốn đặt 6 đến bên phải của 3.

57
00:03:23,310 --> 00:03:32,170
Vì vậy, nó sẽ làm cho một 6.

58
00:03:32,170 --> 00:03:34,310
Và đó chàng sẽ chỉ ở đó.

59
00:03:34,310 --> 00:03:38,320
Okay. Vì vậy, đó là tất cả nó đòi hỏi chúng ta phải làm gì.

60
00:03:38,320 --> 00:03:42,770
>> Bây giờ chúng ta hãy đi qua một số thuật ngữ.

61
00:03:42,770 --> 00:03:46,690
Chúng tôi đã nói về gốc rễ của cây là nút trên cùng trong cây.

62
00:03:46,690 --> 00:03:54,720
Điều chứa 7. Các nút ở dưới cùng của cây được gọi là lá.

63
00:03:54,720 --> 00:04:01,240
Bất cứ nút nào mà chỉ cần có null như con của nó là một chiếc lá.

64
00:04:01,240 --> 00:04:03,680
Vì vậy, nó là có thể, nếu cây nhị phân của chúng tôi chỉ là một nút duy nhất,

65
00:04:03,680 --> 00:04:10,130
một cây là một chiếc lá, và đó là nó.

66
00:04:10,130 --> 00:04:12,060
"'Chiều cao của cây là số lượng hoa bia bạn có để làm

67
00:04:12,060 --> 00:04:16,620
để có được từ trên một chiếc lá. "

68
00:04:16,620 --> 00:04:18,640
Chúng tôi sẽ nhận được vào, trong một giây, sự khác biệt

69
00:04:18,640 --> 00:04:21,940
giữa các cây nhị phân cân bằng và không cân bằng,

70
00:04:21,940 --> 00:04:29,470
nhưng bây giờ, chiều cao tổng thể của cây này

71
00:04:29,470 --> 00:04:34,520
Tôi sẽ nói là 3, mặc dù nếu bạn đếm số bước nhảy

72
00:04:34,520 --> 00:04:39,710
bạn phải thực hiện để có được đến 9, sau đó nó thực sự chỉ là một chiều cao của 2.

73
00:04:39,710 --> 00:04:43,340
Ngay bây giờ đây là một cây nhị phân không cân bằng,

74
00:04:43,340 --> 00:04:49,840
nhưng chúng tôi sẽ nói về cân bằng khi nó được cho là có liên quan.

75
00:04:49,840 --> 00:04:52,040
Vì vậy, bây giờ chúng tôi có thể nói về các nút trong một cây về

76
00:04:52,040 --> 00:04:54,700
liên quan đến các nút khác trong cây.

77
00:04:54,700 --> 00:04:59,730
Vì vậy, bây giờ chúng tôi có bố mẹ, con, anh, chị, em ruột, ông bà tổ tiên và con cháu.

78
00:04:59,730 --> 00:05:05,650
Họ là khá phổ biến ý nghĩa, ý nghĩa của chúng.

79
00:05:05,650 --> 00:05:09,610
Nếu chúng ta hỏi - cha mẹ của nó.

80
00:05:09,610 --> 00:05:12,830
Vì vậy, cha mẹ của 3 là gì?

81
00:05:12,830 --> 00:05:16,090
[Sinh viên] 7. >> Yeah. Phụ huynh chỉ cần đi được những gì cho bạn.

82
00:05:16,090 --> 00:05:20,510
Sau đó, trẻ em của 7 là gì?

83
00:05:20,510 --> 00:05:23,860
[Sinh viên] 3 và 9. >> Yeah.

84
00:05:23,860 --> 00:05:26,460
Chú ý rằng "trẻ em" có nghĩa là trẻ em,

85
00:05:26,460 --> 00:05:31,010
để 6 sẽ không áp dụng, vì nó giống như một đứa cháu.

86
00:05:31,010 --> 00:05:35,540
Nhưng sau đó nếu chúng ta đi con cháu, vì vậy con cháu của 7 là gì?

87
00:05:35,540 --> 00:05:37,500
[Sinh viên] 3, 6 và 9. >> Yeah.

88
00:05:37,500 --> 00:05:42,330
Các con cháu của nút gốc là có được tất cả mọi thứ trong cây,

89
00:05:42,330 --> 00:05:47,950
ngoại trừ nút gốc riêng của mình, nếu bạn không muốn xem xét rằng một hậu duệ.

90
00:05:47,950 --> 00:05:50,750
Và cuối cùng, tổ tiên, vì vậy đó là hướng ngược lại.

91
00:05:50,750 --> 00:05:55,740
Vì vậy, các tổ tiên của 6 là gì?

92
00:05:55,740 --> 00:05:58,920
[Sinh viên] 3 và 7. >> Yeah. 9 không bao gồm.

93
00:05:58,920 --> 00:06:02,520
Nó chỉ trở lại dòng dõi trực tiếp vào thư mục gốc

94
00:06:02,520 --> 00:06:13,230
sẽ được tổ tiên của bạn.

95
00:06:13,230 --> 00:06:16,300
>> "Chúng tôi nói rằng một cây nhị phân được 'đặt hàng' nếu cho mỗi nút trong cây,

96
00:06:16,300 --> 00:06:19,530
tất cả các hậu duệ của nó ở bên trái có giá trị thấp hơn

97
00:06:19,530 --> 00:06:22,890
và tất cả những người ở bên phải có giá trị lớn.

98
00:06:22,890 --> 00:06:27,060
Ví dụ, cây ở trên được yêu cầu mà nó không phải là sự sắp xếp chỉ có thể ra lệnh. "

99
00:06:27,060 --> 00:06:30,180
Trước khi chúng tôi nhận được để mà,

100
00:06:30,180 --> 00:06:36,420
một cây nhị phân ra lệnh cũng được biết đến như là một cây tìm kiếm nhị phân.

101
00:06:36,420 --> 00:06:38,660
Ở đây chúng ta gọi đó là một cây nhị phân ra lệnh,

102
00:06:38,660 --> 00:06:41,850
nhưng tôi đã không bao giờ nghe nói nó được gọi là một cây nhị phân ra lệnh trước khi,

103
00:06:41,850 --> 00:06:46,650
và một bài kiểm tra, chúng tôi có rất nhiều khả năng để đưa cây tìm kiếm nhị phân.

104
00:06:46,650 --> 00:06:49,250
Họ là một và giống nhau,

105
00:06:49,250 --> 00:06:54,580
và điều quan trọng là bạn nhận ra sự khác biệt giữa cây nhị phân và cây tìm kiếm nhị phân.

106
00:06:54,580 --> 00:06:58,830
Một cây nhị phân chỉ là một cây mà điểm đến hai điều.

107
00:06:58,830 --> 00:07:02,120
Mỗi nút chỉ vào hai điều.

108
00:07:02,120 --> 00:07:06,310
Không có lý luận về những giá trị mà nó trỏ tới.

109
00:07:06,310 --> 00:07:11,370
Do đó, như ở đây, vì nó là một cây tìm kiếm nhị phân,

110
00:07:11,370 --> 00:07:14,030
chúng ta biết rằng nếu chúng tôi đi bên trái của 7,

111
00:07:14,030 --> 00:07:16,670
sau đó tất cả các giá trị mà chúng ta có thể có thể đạt được

112
00:07:16,670 --> 00:07:19,310
bằng cách đi bên trái của 7 có thể ít hơn 7.

113
00:07:19,310 --> 00:07:24,070
Chú ý rằng tất cả các giá trị nhỏ hơn 7 là 3 và 6.

114
00:07:24,070 --> 00:07:26,040
Đó là tất cả ở phía bên trái của 7.

115
00:07:26,040 --> 00:07:29,020
Nếu chúng tôi đi đến bên phải của 7, tất cả mọi thứ có thể lớn hơn 7,

116
00:07:29,020 --> 00:07:33,220
nên 9 là quyền của 7, vì vậy chúng tôi đang tốt.

117
00:07:33,220 --> 00:07:36,150
Đây không phải là trường hợp cho một cây nhị phân,

118
00:07:36,150 --> 00:07:40,020
cho một cây nhị phân thông thường, chúng tôi chỉ có thể có 3 ở đầu, 7 bên trái,

119
00:07:40,020 --> 00:07:47,630
9 bên trái của 7, không có thứ tự của các giá trị nào.

120
00:07:47,630 --> 00:07:56,140
Bây giờ, chúng tôi sẽ không thực sự làm được điều này bởi vì nó tẻ nhạt và không cần thiết,

121
00:07:56,140 --> 00:07:59,400
nhưng "cố gắng rút ra cây ra lệnh như nhiều như bạn có thể nghĩ

122
00:07:59,400 --> 00:08:01,900
bằng cách sử dụng số 7, 3, 9, và 6.

123
00:08:01,900 --> 00:08:06,800
Có bao nhiêu thỏa thuận riêng biệt? Chiều cao của mỗi người là gì? "

124
00:08:06,800 --> 00:08:10,480
>> Chúng tôi sẽ làm một vài, nhưng ý tưởng chính là,

125
00:08:10,480 --> 00:08:16,530
điều này là không có cách nào một đại diện duy nhất của một cây nhị phân có chứa các giá trị.

126
00:08:16,530 --> 00:08:22,760
Tất cả chúng ta cần là một số cây nhị phân chứa 7, 3, 6, và 9.

127
00:08:22,760 --> 00:08:25,960
Khác có thể hợp lệ sẽ là một trong gốc là 3,

128
00:08:25,960 --> 00:08:30,260
đi bên trái và đó là 6, đi về bên trái và nó là 7,

129
00:08:30,260 --> 00:08:32,730
đi bên trái và đó là 9.

130
00:08:32,730 --> 00:08:36,169
Đó là một cây nhị phân tìm kiếm hoàn toàn hợp lệ.

131
00:08:36,169 --> 00:08:39,570
Đó không phải là rất hữu ích, bởi vì nó chỉ giống như một danh sách liên kết

132
00:08:39,570 --> 00:08:43,750
và tất cả các con trỏ chỉ là vô giá trị.

133
00:08:43,750 --> 00:08:48,900
Nhưng nó là một cây hợp lệ. Yeah?

134
00:08:48,900 --> 00:08:51,310
[Sinh viên không phải là các giá trị phải lớn hơn bên phải?

135
00:08:51,310 --> 00:08:56,700
Hoặc là điều này? >> Những tôi có nghĩa là đi theo con đường khác.

136
00:08:56,700 --> 00:09:00,960
Ngoài ra còn có - yeah, chúng ta hãy chuyển sang các.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Catch.

138
00:09:07,770 --> 00:09:11,730
Nó vẫn còn phải tuân theo một cây nhị phân tìm kiếm là phải làm.

139
00:09:11,730 --> 00:09:15,650
Vì vậy, tất cả mọi thứ bên trái có thể ít hơn so với bất kỳ nút nào.

140
00:09:15,650 --> 00:09:23,180
Chúng tôi chỉ có thể di chuyển, nói, này 6 và đặt nó ở đây.

141
00:09:23,180 --> 00:09:26,880
Không, chúng tôi không thể. Tại sao tôi làm điều đó?

142
00:09:26,880 --> 00:09:35,350
Hãy làm - đây là 6, ở đây là 7, 6 điểm 3.

143
00:09:35,350 --> 00:09:39,290
Điều này vẫn còn là một cây nhị phân tìm kiếm hợp lệ.

144
00:09:39,290 --> 00:09:49,260
Điều gì là sai nếu tôi - chúng ta hãy xem nếu tôi có thể đến với một sự sắp xếp.

145
00:09:49,260 --> 00:09:52,280
Yeah, okay. Vì vậy, những gì là sai với cây này?

146
00:09:52,280 --> 00:10:08,920
Tôi đoán tôi đã đưa cho bạn một gợi ý rằng có cái gì đó sai trái với nó.

147
00:10:08,920 --> 00:10:14,430
Tại sao tôi làm điều đó?

148
00:10:14,430 --> 00:10:18,510
Okay. Điều này có vẻ hợp lý.

149
00:10:18,510 --> 00:10:22,590
Nếu chúng ta nhìn tại mỗi nút, giống như 7, sau đó đến bên trái của 7 là một 3.

150
00:10:22,590 --> 00:10:24,960
Vì vậy, chúng tôi có 3 điều ở bên phải của 3 là một 6.

151
00:10:24,960 --> 00:10:27,750
Và nếu bạn nhìn vào 6, điều ở bên phải của 6 là một 9.

152
00:10:27,750 --> 00:10:30,910
Vậy tại sao không phải là một cây nhị phân tìm kiếm hợp lệ?

153
00:10:30,910 --> 00:10:36,330
[Sinh viên] 9 vẫn còn để bên trái của 7. >> Yeah.

154
00:10:36,330 --> 00:10:43,710
Nó phải là sự thật rằng tất cả các giá trị mà bạn có thể có thể đạt được bằng cách bên trái của 7 ít hơn 7.

155
00:10:43,710 --> 00:10:49,120
Nếu chúng ta đi bên trái của 7, chúng tôi nhận được đến 3 và chúng ta vẫn có thể nhận được đến 6,

156
00:10:49,120 --> 00:10:52,520
chúng ta vẫn có thể nhận được đến 9, nhưng đã ít hơn 7,

157
00:10:52,520 --> 00:10:55,070
chúng ta không nên có thể nhận được một số lớn hơn 7.

158
00:10:55,070 --> 00:10:59,830
Vì vậy, đây không phải là một cây nhị phân tìm kiếm hợp lệ.

159
00:10:59,830 --> 00:11:02,330
>> Anh trai tôi thực sự đã có một câu hỏi phỏng vấn

160
00:11:02,330 --> 00:11:07,760
đã được cơ bản này, chỉ cần mã lên một cái gì đó để xác nhận

161
00:11:07,760 --> 00:11:10,500
cho dù một cây là một cây tìm kiếm nhị phân,

162
00:11:10,500 --> 00:11:13,580
và do đó, điều đầu tiên anh làm là chỉ cần kiểm tra xem

163
00:11:13,580 --> 00:11:17,020
nếu bên trái và bên phải là chính xác, và sau đó lặp lại ở đó.

164
00:11:17,020 --> 00:11:19,700
Nhưng bạn có thể không chỉ làm điều đó, bạn phải theo dõi

165
00:11:19,700 --> 00:11:22,550
thực tế rằng bây giờ tôi đã đi bên trái của 7,

166
00:11:22,550 --> 00:11:26,340
tất cả mọi thứ trong subtree này phải nhỏ hơn 7.

167
00:11:26,340 --> 00:11:28,430
Thuật toán chính xác cần phải theo dõi

168
00:11:28,430 --> 00:11:35,970
các giới hạn rằng các giá trị có thể có thể rơi.

169
00:11:35,970 --> 00:11:38,360
Chúng tôi sẽ không đi qua tất cả chúng.

170
00:11:38,360 --> 00:11:41,630
Có một mối quan hệ tái phát tốt đẹp,

171
00:11:41,630 --> 00:11:44,810
mặc dù chúng tôi đã không nhận những người, hoặc chúng tôi sẽ không nhận được với những người,

172
00:11:44,810 --> 00:11:47,030
xác định có bao nhiêu thực sự đang có.

173
00:11:47,030 --> 00:11:53,180
Vì vậy, có 14 người trong số họ.

174
00:11:53,180 --> 00:11:56,020
Ý tưởng về cách bạn sẽ làm điều đó toán học là như thế,

175
00:11:56,020 --> 00:11:59,770
bạn có thể chọn bất kỳ một trong duy nhất để được nút gốc,

176
00:11:59,770 --> 00:12:03,160
và sau đó nếu tôi chọn 7 là nút gốc,

177
00:12:03,160 --> 00:12:08,150
sau đó có, nói rằng, một số con số mà có thể đi được nút bên trái của tôi,

178
00:12:08,150 --> 00:12:10,440
và có một số con số đó có thể là nút phải của tôi,

179
00:12:10,440 --> 00:12:15,090
nhưng nếu tôi có n tổng số, sau đó số tiền mà có thể đi về bên trái

180
00:12:15,090 --> 00:12:18,820
cộng với số tiền mà có thể đi bên phải là n - 1.

181
00:12:18,820 --> 00:12:26,130
Vì vậy, các số còn lại, họ có để có thể đi một trong hai bên trái hoặc bên phải.

182
00:12:26,130 --> 00:12:31,580
Có vẻ như khó khăn đó, nếu tôi đặt 3 đầu tiên sau đó tất cả mọi thứ để đi đến bên trái,

183
00:12:31,580 --> 00:12:35,080
nhưng nếu tôi đặt 7, sau đó một số điều có thể đi bên trái và một số thứ có thể đi bên phải.

184
00:12:35,080 --> 00:12:39,570
'3 Đầu tiên, tôi có nghĩa là tất cả mọi thứ có thể đi bên phải.

185
00:12:39,570 --> 00:12:42,350
Nó thực sự, bạn chỉ cần có để suy nghĩ về nó như là,

186
00:12:42,350 --> 00:12:47,980
bao nhiêu thứ có thể đi vào cấp độ tiếp theo của cây.

187
00:12:47,980 --> 00:12:50,420
Và nó đi kèm là 14, hoặc bạn có thể vẽ tất cả trong số họ,

188
00:12:50,420 --> 00:12:54,650
và sau đó bạn sẽ nhận được 14.

189
00:12:54,650 --> 00:13:01,120
>> Trở lại ở đây,

190
00:13:01,120 --> 00:13:03,510
"Cây nhị phân theo thứ tự là mát mẻ bởi vì chúng ta có thể tìm kiếm thông qua họ

191
00:13:03,510 --> 00:13:06,910
một cách rất tương tự như tìm kiếm trên một mảng được sắp xếp.

192
00:13:06,910 --> 00:13:10,120
Để làm như vậy, chúng tôi bắt đầu từ gốc và làm việc theo cách của chúng tôi xuống cây

193
00:13:10,120 --> 00:13:13,440
đối với lá, kiểm tra giá trị của mỗi nút chống lại các giá trị mà chúng ta đang tìm kiếm.

194
00:13:13,440 --> 00:13:15,810
Nếu nút hiện tại giá trị thấp hơn giá trị, chúng tôi đang tìm kiếm,

195
00:13:15,810 --> 00:13:18,050
bạn đi bên cạnh con phải của nút.

196
00:13:18,050 --> 00:13:20,030
Nếu không, bạn đi đến con trái của nút.

197
00:13:20,030 --> 00:13:22,800
Tại một số điểm, bạn sẽ tìm thấy những giá trị mà bạn đang tìm kiếm, hoặc bạn sẽ chạy vào một null,

198
00:13:22,800 --> 00:13:28,520
cho thấy giá trị không phải trong cây. "

199
00:13:28,520 --> 00:13:32,450
Tôi phải vẽ lại cây chúng tôi đã có trước đây, mà sẽ mất một giây.

200
00:13:32,450 --> 00:13:38,280
Nhưng chúng tôi muốn tìm xem 6, 10, và 1 trong cây.

201
00:13:38,280 --> 00:13:49,180
Vì vậy, nó là cái gì, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
Những con số mà bạn muốn tìm kiếm, chúng tôi muốn tìm kiếm 6.

203
00:13:52,730 --> 00:13:55,440
Thuật toán này như thế nào làm việc?

204
00:13:55,440 --> 00:14:03,040
Vâng, chúng tôi cũng có một số con trỏ gốc cây của chúng tôi.

205
00:14:03,040 --> 00:14:12,460
Và chúng ta sẽ đi đến gốc và nói, là giá trị này bằng giá trị mà chúng ta đang tìm kiếm?

206
00:14:12,460 --> 00:14:15,000
Vì vậy, chúng tôi đang tìm kiếm 6, do đó, nó không bằng.

207
00:14:15,000 --> 00:14:20,140
Vì vậy, chúng tôi tiếp tục đi, và bây giờ chúng ta nói, okay, vì vậy 6 là ít hơn 7.

208
00:14:20,140 --> 00:14:23,940
Điều đó có nghĩa là chúng tôi muốn đi bên trái, hoặc làm chúng tôi muốn đi bên phải?

209
00:14:23,940 --> 00:14:27,340
[Sinh viên] Left. >> Yeah.

210
00:14:27,340 --> 00:14:33,340
Đó là dễ dàng hơn đáng kể, tất cả những gì bạn phải làm là vẽ một nút có thể có của cây

211
00:14:33,340 --> 00:14:37,760
và sau đó bạn đừng thay vì cố gắng suy nghĩ trong đầu của bạn,

212
00:14:37,760 --> 00:14:40,020
okay, nếu nó ít hơn, để tôi đi sang bên trái hoặc bên phải,

213
00:14:40,020 --> 00:14:43,030
chỉ cần nhìn vào bức ảnh này, nó rất rõ ràng rằng tôi phải đi về bên trái

214
00:14:43,030 --> 00:14:47,700
nếu nút này lớn hơn giá trị mà tôi đang tìm kiếm.

215
00:14:47,700 --> 00:14:52,600
Vì vậy, bạn đi sang bên trái, bây giờ tôi đang ở mức 3.

216
00:14:52,600 --> 00:14:57,770
Tôi muốn - 3 là ít hơn giá trị tôi đang tìm kiếm, mà là 6.

217
00:14:57,770 --> 00:15:03,420
Vì vậy, chúng tôi đi bên phải, và bây giờ tôi kết thúc lúc 6,

218
00:15:03,420 --> 00:15:07,380
đó là giá trị tôi đang tìm kiếm, vì vậy tôi trở lại đúng.

219
00:15:07,380 --> 00:15:15,760
Giá trị tiếp theo tôi sẽ đi tìm là 10.

220
00:15:15,760 --> 00:15:23,230
Okay. Vì vậy, 10, bây giờ, - cắt - sẽ thực hiện theo các gốc.

221
00:15:23,230 --> 00:15:27,670
Bây giờ, 10 sẽ được lớn hơn 7, vì vậy tôi muốn nhìn bên phải.

222
00:15:27,670 --> 00:15:31,660
Tôi sẽ đến đây, 10 là có được lớn hơn 9,

223
00:15:31,660 --> 00:15:34,520
vì vậy tôi sẽ muốn nhìn bên phải.

224
00:15:34,520 --> 00:15:42,100
Tôi đi qua ở đây, nhưng ở đây bây giờ tôi đang ở vô giá trị.

225
00:15:42,100 --> 00:15:44,170
Tôi phải làm gì nếu tôi nhấn vô giá trị?

226
00:15:44,170 --> 00:15:47,440
[Sinh viên] Quay trở lại sai? >> Yeah. Tôi không tìm thấy 10.

227
00:15:47,440 --> 00:15:49,800
1 được sẽ là một trường hợp gần như giống hệt nhau,

228
00:15:49,800 --> 00:15:51,950
ngoại trừ nó chỉ cần đi được lộn, thay vì tìm kiếm

229
00:15:51,950 --> 00:15:56,540
xuống phía bên phải, tôi sẽ nhìn xuống phía bên trái.

230
00:15:56,540 --> 00:16:00,430
>> Bây giờ tôi nghĩ rằng chúng tôi thực sự có được mã.

231
00:16:00,430 --> 00:16:04,070
Đây là nơi mở thiết bị CS50 và điều hướng theo cách của bạn,

232
00:16:04,070 --> 00:16:07,010
nhưng bạn cũng có thể làm điều đó trong không gian.

233
00:16:07,010 --> 00:16:09,170
Đây có thể là lý tưởng để làm điều đó trong không gian,

234
00:16:09,170 --> 00:16:13,760
bởi vì chúng ta có thể làm việc trong không gian.

235
00:16:13,760 --> 00:16:19,170
"Trước tiên, chúng tôi sẽ cần một định nghĩa kiểu mới cho một nút cây nhị phân chứa các giá trị int.

236
00:16:19,170 --> 00:16:21,400
Sử dụng các boilerplate typedef dưới đây,

237
00:16:21,400 --> 00:16:24,510
tạo ra một định nghĩa kiểu mới cho một nút trong một cây nhị phân.

238
00:16:24,510 --> 00:16:27,930
Nếu bạn gặp khó khăn. . . "Blah, blah, blah. Okay.

239
00:16:27,930 --> 00:16:30,380
Vì vậy, chúng ta hãy đặt boilerplate đây,

240
00:16:30,380 --> 00:16:41,630
typedef struct node, và nút. Yeah, okay.

241
00:16:41,630 --> 00:16:44,270
Vì vậy, các lĩnh vực mà chúng tôi sẽ muốn trong nút của chúng tôi là gì?

242
00:16:44,270 --> 00:16:46,520
[Sinh viên] Int và sau đó hai con trỏ?

243
00:16:46,520 --> 00:16:49,700
>> Int giá trị, hai con trỏ? Làm thế nào để viết các con trỏ?

244
00:16:49,700 --> 00:16:58,440
[Sinh viên] Struct. >> Tôi nên phóng to. Yeah, vì vậy struct node * còn lại,

245
00:16:58,440 --> 00:17:01,320
và struct node bên phải *.

246
00:17:01,320 --> 00:17:03,460
Và hãy nhớ rằng các cuộc thảo luận từ lần cuối cùng,

247
00:17:03,460 --> 00:17:15,290
rằng điều này làm cho không có ý nghĩa, điều này làm cho không có ý nghĩa,

248
00:17:15,290 --> 00:17:18,270
điều này làm cho không có ý nghĩa.

249
00:17:18,270 --> 00:17:25,000
Bạn cần phải có tất cả mọi thứ để xác định cấu trúc đệ quy này.

250
00:17:25,000 --> 00:17:27,970
Được rồi, vì vậy đó là những gì cây của chúng tôi sẽ trông giống như.

251
00:17:27,970 --> 00:17:37,670
Nếu chúng ta làm một cây trinary, sau đó một nút có thể trông như b2, b1, struct node * b3,

252
00:17:37,670 --> 00:17:43,470
trong đó b là một chi nhánh - trên thực tế, tôi đã hơn nghe trái, giữa, phải, nhưng bất cứ điều gì.

253
00:17:43,470 --> 00:17:55,610
Chúng tôi chỉ quan tâm về nhị phân, do đó, phải, trái.

254
00:17:55,610 --> 00:17:59,110
"Bây giờ khai báo một biến node * toàn cầu cho thư mục gốc của cây".

255
00:17:59,110 --> 00:18:01,510
Vì vậy, chúng tôi sẽ không làm điều đó.

256
00:18:01,510 --> 00:18:08,950
Để thực hiện những điều hơi khó khăn hơn và tổng quát hơn,

257
00:18:08,950 --> 00:18:11,570
chúng tôi sẽ không có một nút biến toàn cầu.

258
00:18:11,570 --> 00:18:16,710
Thay vào đó, chính chúng ta sẽ khai báo tất cả các nút điều của chúng tôi,

259
00:18:16,710 --> 00:18:20,500
và điều đó có nghĩa là dưới đây, khi chúng tôi bắt đầu chạy

260
00:18:20,500 --> 00:18:23,130
Chứa chức năng và chức năng chèn của chúng tôi,

261
00:18:23,130 --> 00:18:27,410
thay vì Chứa của chúng tôi chức năng chỉ bằng cách sử dụng nút biến toàn cầu này,

262
00:18:27,410 --> 00:18:34,280
chúng ta sẽ có nó như là một đối số cây mà chúng ta muốn nó để xử lý.

263
00:18:34,280 --> 00:18:36,650
Có các biến toàn cầu được cho là để làm cho mọi việc dễ dàng hơn.

264
00:18:36,650 --> 00:18:42,310
Chúng ta sẽ làm cho những điều khó hơn.

265
00:18:42,310 --> 00:18:51,210
Bây giờ mất một phút hoặc lâu hơn để chỉ làm điều này loại điều,

266
00:18:51,210 --> 00:18:57,690
bên trong của chính bạn muốn để tạo ra cây này, và đó là tất cả những gì bạn muốn làm.

267
00:18:57,690 --> 00:19:04,530
Hãy thử và xây dựng cây này trong chức năng chính của bạn.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Vì vậy, bạn thậm chí không có đã xây dựng cây cách toàn bộ.

269
00:19:47,610 --> 00:19:49,840
Nhưng bất cứ ai có một cái gì đó tôi có thể kéo lên

270
00:19:49,840 --> 00:20:03,130
để hiển thị như thế nào người ta có thể bắt đầu xây dựng một cây như vậy?

271
00:20:03,130 --> 00:20:08,080
[Sinh viên] của ai đó đập, cố gắng để có được ra ngoài.

272
00:20:08,080 --> 00:20:13,100
Bowden] Bất cứ ai cũng thoải mái với xây dựng cây của họ?

273
00:20:13,100 --> 00:20:15,520
[Sinh viên] Chắc chắn. Nó không phải thực hiện. >> Đó là tốt. Chúng tôi chỉ có thể kết thúc

274
00:20:15,520 --> 00:20:26,860
oh, bạn có thể lưu nó? Hoan hô.

275
00:20:26,860 --> 00:20:32,020
Vì vậy, ở đây chúng tôi có - oh, tôi hơi cắt.

276
00:20:32,020 --> 00:20:34,770
Tôi phóng to?

277
00:20:34,770 --> 00:20:37,730
Phóng to, di chuyển ra ngoài. >> Tôi có một câu hỏi. >> Yeah?

278
00:20:37,730 --> 00:20:44,410
[Sinh viên] Khi bạn xác định cấu trúc, những thứ như khởi tạo để bất cứ điều gì?

279
00:20:44,410 --> 00:20:47,160
Bowden] số >> Okay. Vì vậy, bạn sẽ phải khởi tạo -

280
00:20:47,160 --> 00:20:50,450
[Bowden] số Khi bạn xác định, hoặc khi bạn khai báo một cấu trúc,

281
00:20:50,450 --> 00:20:55,600
nó không được khởi tạo theo mặc định, nó giống như nếu bạn khai báo một int.

282
00:20:55,600 --> 00:20:59,020
Đó là chính xác những điều tương tự. Nó giống như mỗi người trong các lĩnh vực cá nhân của mình

283
00:20:59,020 --> 00:21:04,460
có thể có một giá trị rác trong nó. >> Và là nó có thể để xác định hoặc tuyên bố một struct

284
00:21:04,460 --> 00:21:07,740
trong một cách mà nó không khởi tạo cho họ?

285
00:21:07,740 --> 00:21:13,200
[Bowden]. Vì vậy, cú pháp khởi tạo shortcut

286
00:21:13,200 --> 00:21:18,660
sẽ trông giống như -

287
00:21:18,660 --> 00:21:22,200
Có hai cách chúng ta có thể làm điều này. Tôi nghĩ chúng ta nên biên dịch nó

288
00:21:22,200 --> 00:21:25,840
Clang chắc chắn cũng làm điều này.

289
00:21:25,840 --> 00:21:28,510
Thứ tự của các đối số trong đó có cấu trúc,

290
00:21:28,510 --> 00:21:32,170
bạn đặt như là thứ tự của các đối số bên trong các dấu ngoặc nhọn.

291
00:21:32,170 --> 00:21:35,690
Vì vậy, nếu bạn muốn khởi tạo nó đến 9 và để lại được vô giá trị và sau đó phải được null,

292
00:21:35,690 --> 00:21:41,570
nó sẽ là 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Cách khác là, và biên tập viên không thích cú pháp này,

294
00:21:47,890 --> 00:21:50,300
và nó nghĩ rằng tôi muốn có một khối mới,

295
00:21:50,300 --> 00:22:01,800
nhưng thay thế là một cái gì đó như

296
00:22:01,800 --> 00:22:04,190
ở đây, tôi sẽ đặt nó trên một dòng mới.

297
00:22:04,190 --> 00:22:09,140
Bạn có thể nói một cách rõ ràng, tôi quên cú pháp chính xác.

298
00:22:09,140 --> 00:22:13,110
Vì vậy, bạn rõ ràng có thể giải quyết chúng theo tên, và nói,

299
00:22:13,110 --> 00:22:21,570
C, hoặc giá trị. = 9, trái = NULL.

300
00:22:21,570 --> 00:22:24,540
Tôi đoán những cần phải có dấu phẩy.

301
00:22:24,540 --> 00:22:29,110
Bên phải = NULL, do đó, cách này, bạn không

302
00:22:29,110 --> 00:22:33,780
thực sự cần phải biết thứ tự của cấu trúc,

303
00:22:33,780 --> 00:22:36,650
và khi bạn đang đọc này, nó rõ ràng hơn rất nhiều

304
00:22:36,650 --> 00:22:41,920
về những gì giá trị đang được khởi tạo.

305
00:22:41,920 --> 00:22:44,080
>> Điều này xảy ra là một trong những điều mà -

306
00:22:44,080 --> 00:22:49,100
như vậy, đối với hầu hết các phần, C + + là một superset của C.

307
00:22:49,100 --> 00:22:54,160
Bạn có thể lấy mã C, di chuyển nó trên C + +, và nó nên biên dịch.

308
00:22:54,160 --> 00:22:59,570
Đây là một trong những điều mà C + + không hỗ trợ, do đó, người dân có xu hướng không để làm điều đó.

309
00:22:59,570 --> 00:23:01,850
Tôi không biết nếu đó là lý do duy nhất người dân có xu hướng không để làm điều đó,

310
00:23:01,850 --> 00:23:10,540
nhưng trường hợp mà tôi cần thiết để sử dụng nó cần thiết để làm việc với C + + và vì vậy tôi không thể sử dụng.

311
00:23:10,540 --> 00:23:14,000
Một ví dụ khác của một cái gì đó không làm việc với C + + là

312
00:23:14,000 --> 00:23:16,940
cách malloc trả về một "void *", về mặt kỹ thuật,

313
00:23:16,940 --> 00:23:20,200
nhưng bạn chỉ có thể nói char * x bất cứ điều gì malloc =

314
00:23:20,200 --> 00:23:22,840
và nó sẽ tự động được đúc vào một char *.

315
00:23:22,840 --> 00:23:25,450
Đó là diễn viên tự động không xảy ra trong C + +.

316
00:23:25,450 --> 00:23:28,150
Điều đó sẽ không biên dịch, và bạn rõ ràng sẽ cần phải nói

317
00:23:28,150 --> 00:23:34,510
char * malloc, bất cứ điều gì, bỏ nó vào một char *.

318
00:23:34,510 --> 00:23:37,270
Không có nhiều điều rằng C và C + + không đồng ý về,

319
00:23:37,270 --> 00:23:40,620
mà còn cả hai.

320
00:23:40,620 --> 00:23:43,120
Vì vậy, chúng ta sẽ đến với cú pháp này.

321
00:23:43,120 --> 00:23:46,150
Nhưng ngay cả khi chúng tôi đã không đi với cú pháp đó,

322
00:23:46,150 --> 00:23:49,470
những gì là - có thể là sai với điều này?

323
00:23:49,470 --> 00:23:52,170
[Sinh viên] Tôi không cần phải tới đích của nó? >> Yeah.

324
00:23:52,170 --> 00:23:55,110
Hãy nhớ rằng mũi tên có một dereference ngầm,

325
00:23:55,110 --> 00:23:58,230
và do đó, khi chúng ta chỉ đối phó với một cấu trúc,

326
00:23:58,230 --> 00:24:04,300
chúng tôi muốn sử dụng. để có được ở một bên trong các trường của cấu trúc.

327
00:24:04,300 --> 00:24:07,200
Và thời gian duy nhất mà chúng tôi sử dụng mũi tên là khi chúng ta muốn làm -

328
00:24:07,200 --> 00:24:13,450
cũng, mũi tên tương đương với

329
00:24:13,450 --> 00:24:17,020
đó là những gì nó sẽ có nghĩa là nếu tôi sử dụng mũi tên.

330
00:24:17,020 --> 00:24:24,600
Tất cả các phương mũi tên, dereference này, bây giờ tôi đang ở một cấu trúc, và tôi có thể nhận được các lĩnh vực.

331
00:24:24,600 --> 00:24:28,040
Hoặc là có được lĩnh vực trực tiếp hoặc dereference và lĩnh vực -

332
00:24:28,040 --> 00:24:30,380
Tôi đoán này nên được giá trị.

333
00:24:30,380 --> 00:24:33,910
Nhưng ở đây tôi đang đối phó với một cấu trúc, không phải là một con trỏ đến một cấu trúc,

334
00:24:33,910 --> 00:24:38,780
và vì vậy tôi không thể sử dụng mũi tên.

335
00:24:38,780 --> 00:24:47,510
Tuy nhiên, các loại điều này chúng ta có thể làm cho tất cả các nút.

336
00:24:47,510 --> 00:24:55,790
Lạy Chúa tôi.

337
00:24:55,790 --> 00:25:09,540
Đây là 6, 7, và 3.

338
00:25:09,540 --> 00:25:16,470
Sau đó, chúng ta có thể thiết lập các chi nhánh trong cây của chúng tôi, chúng tôi có thể có 7 -

339
00:25:16,470 --> 00:25:21,650
chúng ta có thể có, bên trái của nó nên chỉ đến 3.

340
00:25:21,650 --> 00:25:25,130
Vì vậy, làm thế nào để chúng ta làm điều đó?

341
00:25:25,130 --> 00:25:29,320
[Sinh viên, không thể hiểu] >> Vâng. Địa chỉ của node3,

342
00:25:29,320 --> 00:25:34,170
và nếu bạn không có địa chỉ, sau đó nó chỉ sẽ không biên dịch.

343
00:25:34,170 --> 00:25:38,190
Nhưng hãy nhớ rằng đây là những con trỏ đến các hạch tiếp theo.

344
00:25:38,190 --> 00:25:44,930
Quyền nên chỉ đến 9,

345
00:25:44,930 --> 00:25:53,330
và 3 điểm trên bên phải đến 6.

346
00:25:53,330 --> 00:25:58,480
Tôi nghĩ rằng đây là tất cả các thiết lập. Bất kỳ ý kiến ​​hoặc câu hỏi?

347
00:25:58,480 --> 00:26:02,060
[Sinh viên, không thể hiểu] Gốc này sẽ là 7.

348
00:26:02,060 --> 00:26:08,210
Chúng tôi chỉ có thể nói node * ptr =

349
00:26:08,210 --> 00:26:14,160
hoặc root = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Đối với mục đích của chúng ta, chúng ta sẽ được giao dịch với chèn,

351
00:26:20,730 --> 00:26:25,490
do đó, chúng ta sẽ muốn viết một chức năng để chèn vào cây nhị phân này

352
00:26:25,490 --> 00:26:34,230
và chèn chắc chắn sẽ gọi malloc để tạo ra một nút mới cho cây.

353
00:26:34,230 --> 00:26:36,590
Vì vậy, mọi thứ đang đi để có được lộn xộn với thực tế rằng một số nút

354
00:26:36,590 --> 00:26:38,590
Hiện tại trên stack

355
00:26:38,590 --> 00:26:43,680
và các nút khác sẽ kết thúc trên heap khi chúng ta chèn chúng.

356
00:26:43,680 --> 00:26:47,640
Điều này là hoàn toàn hợp lệ, nhưng lý do duy nhất

357
00:26:47,640 --> 00:26:49,600
chúng tôi có thể làm điều này trên stack

358
00:26:49,600 --> 00:26:51,840
là bởi vì nó là một ví dụ contrived mà chúng ta biết

359
00:26:51,840 --> 00:26:56,360
cây là vụ phải được xây dựng như là 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Nếu chúng ta không có điều này, thì chúng ta sẽ không phải malloc ở nơi đầu tiên.

361
00:27:02,970 --> 00:27:06,160
Như chúng ta sẽ thấy một chút sau đó, chúng ta nên malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Ngay bây giờ nó hoàn toàn hợp lý để đưa vào ngăn xếp,

363
00:27:08,570 --> 00:27:14,750
nhưng hãy để thay đổi điều này với thực hiện malloc.

364
00:27:14,750 --> 00:27:17,160
Vì vậy, mỗi trong số này sẽ là một cái gì đó như

365
00:27:17,160 --> 00:27:24,240
nút * node9 = malloc (sizeof (node)).

366
00:27:24,240 --> 00:27:28,040
Và bây giờ chúng ta sẽ phải làm kiểm tra của chúng tôi.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Tôi không muốn điều đó -

368
00:27:34,010 --> 00:27:40,950
trở về 1, và sau đó chúng ta có thể làm node9-> bởi vì bây giờ nó là một con trỏ,

369
00:27:40,950 --> 00:27:45,300
giá trị = 6, node9-> trái = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> bên phải = NULL,

371
00:27:48,930 --> 00:27:51,410
và chúng ta sẽ phải làm điều đó cho mỗi người trong số những nút.

372
00:27:51,410 --> 00:27:57,490
Vì vậy, thay vào đó, hãy đặt nó bên trong một chức năng riêng biệt.

373
00:27:57,490 --> 00:28:00,620
Hãy gọi nó là node * build_node,

374
00:28:00,620 --> 00:28:09,050
và điều này là hơi tương tự như các API của chúng tôi cung cấp cho mã hóa Huffman.

375
00:28:09,050 --> 00:28:12,730
Chúng tôi cung cấp cho bạn chức năng khởi tạo cho một cây

376
00:28:12,730 --> 00:28:20,520
và deconstructor "chức năng" cho những cây và giống nhau đối với rừng.

377
00:28:20,520 --> 00:28:22,570
>> Vì vậy, ở đây chúng tôi đang đi để có một chức năng khởi tạo

378
00:28:22,570 --> 00:28:25,170
chỉ cần xây dựng một nút cho chúng tôi.

379
00:28:25,170 --> 00:28:29,320
Và nó sẽ nhìn khá nhiều chính xác như thế này.

380
00:28:29,320 --> 00:28:32,230
Và tôi thậm chí sẽ được lười biếng và không thay đổi tên của biến,

381
00:28:32,230 --> 00:28:34,380
mặc dù node9 làm cho không có ý nghĩa nữa.

382
00:28:34,380 --> 00:28:38,610
Ồ, tôi đoán giá trị của node9 không cần phải có được 6.

383
00:28:38,610 --> 00:28:42,800
Bây giờ chúng ta có thể trở lại node9.

384
00:28:42,800 --> 00:28:49,550
Và ở đây chúng ta nên trở về null.

385
00:28:49,550 --> 00:28:52,690
Mọi người đều đồng ý rằng chức năng xây dựng một nút?

386
00:28:52,690 --> 00:28:59,780
Vì vậy, bây giờ chúng tôi chỉ có thể gọi đó là xây dựng bất kỳ nút với một giá trị nhất định và con trỏ null.

387
00:28:59,780 --> 00:29:09,750
Bây giờ chúng ta có thể gọi đó, chúng ta có thể làm nút * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Và chúng ta hãy làm. . .

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

390
00:29:33,980 --> 00:29:39,330
Và bây giờ chúng tôi muốn thiết lập các con trỏ,

391
00:29:39,330 --> 00:29:42,470
ngoại trừ bây giờ tất cả mọi thứ đã về của các con trỏ

392
00:29:42,470 --> 00:29:48,480
vì vậy không còn cần địa chỉ của.

393
00:29:48,480 --> 00:29:56,300
Okay. Vì vậy, điều cuối cùng tôi muốn làm là những gì?

394
00:29:56,300 --> 00:30:03,850
Có một kiểm tra lỗi mà tôi không làm.

395
00:30:03,850 --> 00:30:06,800
Những gì không xây dựng trở lại nút?

396
00:30:06,800 --> 00:30:11,660
[Sinh viên, không thể hiểu] >> Vâng. Nếu malloc không thành công, nó sẽ trả về null.

397
00:30:11,660 --> 00:30:16,460
Vì vậy, tôi sẽ uể oải đặt nó xuống ở đây thay vì làm một điều kiện cho mỗi.

398
00:30:16,460 --> 00:30:22,320
Nếu (node9 == NULL, hoặc thậm chí đơn giản,

399
00:30:22,320 --> 00:30:28,020
điều này là tương đương với chỉ nếu không node9.

400
00:30:28,020 --> 00:30:38,310
Vì vậy, nếu không node9, hoặc không node6, hoặc không node3, hoặc không node7, trở về 1.

401
00:30:38,310 --> 00:30:42,850
Có lẽ chúng ta nên in malloc không thành công, hoặc một cái gì đó.

402
00:30:42,850 --> 00:30:46,680
[Sinh viên giả bằng vô giá trị cũng?

403
00:30:46,680 --> 00:30:51,290
Bowden] Bất kỳ giá trị bằng không là sai.

404
00:30:51,290 --> 00:30:53,920
Vì vậy, null là một giá trị bằng không.

405
00:30:53,920 --> 00:30:56,780
Zero là một giá trị bằng không. Dối là một giá trị bằng không.

406
00:30:56,780 --> 00:31:02,130
Bất kỳ khá nhiều 2 giá trị không chỉ là vô giá trị và không,

407
00:31:02,130 --> 00:31:07,900
sai là chỉ băm được định nghĩa như là số không.

408
00:31:07,900 --> 00:31:13,030
Điều đó cũng được áp dụng nếu chúng ta khai báo biến toàn cầu.

409
00:31:13,030 --> 00:31:17,890
Nếu chúng ta đã có gốc * nút lên ở đây,

410
00:31:17,890 --> 00:31:24,150
sau đó - điều tốt đẹp về các biến toàn cầu là họ luôn luôn có một giá trị ban đầu.

411
00:31:24,150 --> 00:31:27,500
Điều đó không đúng chức năng, làm thế nào bên trong đây,

412
00:31:27,500 --> 00:31:34,870
nếu chúng ta có, như thế, node * hoặc nút x.

413
00:31:34,870 --> 00:31:37,380
Chúng tôi không có ý tưởng những gì x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
hoặc chúng tôi có thể in ra và họ có thể được tùy ý.

415
00:31:40,700 --> 00:31:44,980
Đó là không đúng sự thật của các biến toàn cầu.

416
00:31:44,980 --> 00:31:47,450
Nút gốc hoặc nút x.

417
00:31:47,450 --> 00:31:53,410
Theo mặc định, tất cả mọi thứ đó là toàn cầu, nếu không rõ ràng khởi tạo một số giá trị,

418
00:31:53,410 --> 00:31:57,390
có một giá trị số không như giá trị của nó.

419
00:31:57,390 --> 00:32:01,150
Vì vậy, ở đây, node * gốc, chúng tôi không rõ ràng khởi tạo nó bất cứ điều gì,

420
00:32:01,150 --> 00:32:06,350
do đó, giá trị mặc định của nó sẽ được null, đó là giá trị số không của con trỏ.

421
00:32:06,350 --> 00:32:11,870
Giá trị mặc định của x được sẽ có nghĩa là x.value là số không,

422
00:32:11,870 --> 00:32:14,260
x.left là null, và là null x.right.

423
00:32:14,260 --> 00:32:21,070
Vì vậy, kể từ khi nó là một cấu trúc, tất cả các lĩnh vực của cấu trúc sẽ là không có giá trị.

424
00:32:21,070 --> 00:32:24,410
Chúng tôi không cần phải sử dụng điều đó ở đây, mặc dù.

425
00:32:24,410 --> 00:32:27,320
[Sinh viên] cấu trúc khác nhau hơn so với các biến số khác, và các biến khác

426
00:32:27,320 --> 00:32:31,400
các giá trị rác, đây là những số không?

427
00:32:31,400 --> 00:32:36,220
[Bowden] giá trị khác. Vì vậy, trong x, x sẽ bằng không.

428
00:32:36,220 --> 00:32:40,070
Nếu đó là ở phạm vi toàn cầu, nó có một giá trị ban đầu. >> Okay.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Hoặc là giá trị ban đầu bạn đã cho nó hay không.

430
00:32:48,950 --> 00:32:53,260
Tôi nghĩ rằng sẽ chăm sóc của tất cả những điều này.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Vì vậy, phần tiếp theo của câu hỏi yêu cầu,

432
00:32:58,390 --> 00:33:01,260
"Bây giờ chúng ta muốn viết một chức năng được gọi là có chứa

433
00:33:01,260 --> 00:33:04,930
với một nguyên mẫu của bool chứa giá trị int. "

434
00:33:04,930 --> 00:33:08,340
Chúng tôi sẽ không làm bool chứa giá trị int.

435
00:33:08,340 --> 00:33:15,110
Nguyên mẫu của chúng tôi là sẽ trông giống như

436
00:33:15,110 --> 00:33:22,380
bool chứa (giá trị int.

437
00:33:22,380 --> 00:33:24,490
Và sau đó chúng tôi cũng sẽ vượt qua nó là cây

438
00:33:24,490 --> 00:33:28,870
rằng nó phải được kiểm tra để xem nếu nó có giá trị đó.

439
00:33:28,870 --> 00:33:38,290
Do vậy, node * cây). Okay.

440
00:33:38,290 --> 00:33:44,440
Và sau đó chúng ta có thể gọi nó với một cái gì đó như,

441
00:33:44,440 --> 00:33:46,090
có lẽ chúng ta sẽ muốn printf hoặc một cái gì đó.

442
00:33:46,090 --> 00:33:51,040
Có 6, rễ của chúng tôi.

443
00:33:51,040 --> 00:33:54,300
Điều đó sẽ trở lại, hoặc đúng,

444
00:33:54,300 --> 00:33:59,390
trong khi đó có 5 gốc nên trả về false.

445
00:33:59,390 --> 00:34:02,690
Vì vậy, mất một giây để thực hiện điều này.

446
00:34:02,690 --> 00:34:06,780
Bạn có thể làm điều đó, hoặc lặp đi lặp lại hoặc đệ quy.

447
00:34:06,780 --> 00:34:09,739
Những điều tốt đẹp về cách mà chúng ta đã thiết lập những điều là

448
00:34:09,739 --> 00:34:12,300
nó vay chính nó để giải pháp đệ quy của chúng tôi dễ dàng hơn nhiều

449
00:34:12,300 --> 00:34:14,719
hơn so với cách biến toàn cầu.

450
00:34:14,719 --> 00:34:19,750
Bởi vì nếu chúng ta chỉ có chứa giá trị int, sau đó chúng tôi không có cách nào recursing xuống subtrees.

451
00:34:19,750 --> 00:34:24,130
Chúng tôi sẽ phải có một chức năng trợ giúp riêng biệt mà recurses xuống subtrees cho chúng tôi.

452
00:34:24,130 --> 00:34:29,610
Nhưng kể từ khi chúng tôi đã thay đổi nó để có những cây như một tham số,

453
00:34:29,610 --> 00:34:32,760
mà nó phải luôn luôn có được ở nơi đầu tiên,

454
00:34:32,760 --> 00:34:35,710
bây giờ chúng ta có thể recurse dễ dàng hơn.

455
00:34:35,710 --> 00:34:38,960
Vì vậy, lặp đi lặp lại hoặc đệ quy, chúng tôi sẽ đi qua cả hai,

456
00:34:38,960 --> 00:34:46,139
nhưng chúng ta sẽ thấy rằng kết thúc đệ quy lên được khá dễ dàng.

457
00:34:59,140 --> 00:35:02,480
Okay. Có ai có một cái gì đó chúng ta có thể làm việc với?

458
00:35:02,480 --> 00:35:12,000
>> [Sinh viên] Tôi đã có một giải pháp lặp. >> Tất cả phải, lặp đi lặp lại.

459
00:35:12,000 --> 00:35:16,030
Được rồi, đây có vẻ tốt.

460
00:35:16,030 --> 00:35:18,920
Vì vậy, muốn đi bộ chúng tôi thông qua nó?

461
00:35:18,920 --> 00:35:25,780
[Sinh viên] Chắc chắn. Vì vậy, tôi thiết lập một biến temp để có được nút đầu tiên của cây.

462
00:35:25,780 --> 00:35:28,330
Và sau đó tôi chỉ looped thông qua trong khi tạm thời không null bằng,

463
00:35:28,330 --> 00:35:31,700
do đó, trong khi vẫn còn trong cây, tôi đoán.

464
00:35:31,700 --> 00:35:35,710
Và nếu giá trị bằng với giá trị tạm thời đang trỏ đến,

465
00:35:35,710 --> 00:35:37,640
sau đó nó sẽ trả về giá trị đó.

466
00:35:37,640 --> 00:35:40,210
Nếu không, nó sẽ kiểm tra nếu nó trên bên phải hay bên trái.

467
00:35:40,210 --> 00:35:43,400
Nếu bạn đã bao giờ có được một tình huống mà không có cây hơn,

468
00:35:43,400 --> 00:35:47,330
sau đó nó sẽ trả về nó thoát ra khỏi vòng lặp và trả về false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. Vì vậy, đó có vẻ tốt.

470
00:35:52,190 --> 00:35:58,470
Bất cứ ai có bất kỳ ý kiến ​​về bất cứ điều gì?

471
00:35:58,470 --> 00:36:02,400
Tôi không có ý kiến ​​đúng đắn ở tất cả.

472
00:36:02,400 --> 00:36:11,020
Một trong những điều chúng ta có thể làm là anh chàng này.

473
00:36:11,020 --> 00:36:21,660
Ồ, nó sẽ đi một hơi dài chút.

474
00:36:21,660 --> 00:36:33,460
Tôi sẽ sửa chữa mà lên. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Mọi người nên nhớ ternary hoạt động như thế nào.

476
00:36:37,150 --> 00:36:38,610
Đã chắc chắn có được câu đố trong quá khứ

477
00:36:38,610 --> 00:36:41,170
cung cấp cho bạn một chức năng với một nhà điều hành ternary,

478
00:36:41,170 --> 00:36:45,750
và nói, dịch này, làm một cái gì đó mà không sử dụng ternary.

479
00:36:45,750 --> 00:36:49,140
Vì vậy, đây là một trường hợp rất phổ biến khi tôi sẽ nghĩ đến việc sử dụng ternary,

480
00:36:49,140 --> 00:36:54,610
nơi mà nếu một số điều kiện thiết lập một biến đến một cái gì đó,

481
00:36:54,610 --> 00:36:58,580
khác thiết lập mà cùng một biến cái gì khác.

482
00:36:58,580 --> 00:37:03,390
Đó là một cái gì đó rất thường xuyên có thể được chuyển đổi thành các loại điều này

483
00:37:03,390 --> 00:37:14,420
, nơi đặt biến này - hoặc, tốt, điều này là đúng? Sau đó, khác này.

484
00:37:14,420 --> 00:37:18,550
[Sinh viên] Người đầu tiên là nếu đúng sự thật, đúng không?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. Tôi luôn luôn đọc nó, tạm thời bằng giá trị lớn hơn giá trị tạm thời,

486
00:37:25,570 --> 00:37:30,680
sau đó điều này, người nào khác. Nó hỏi một câu hỏi.

487
00:37:30,680 --> 00:37:35,200
Nó phải cao? Sau đó làm việc đầu tiên. Khác làm điều thứ hai.

488
00:37:35,200 --> 00:37:41,670
Tôi gần như luôn luôn - đại tràng, tôi chỉ - trong đầu tôi, tôi đọc là khác.

489
00:37:41,670 --> 00:37:47,180
>> Có ai có một giải pháp đệ quy?

490
00:37:47,180 --> 00:37:49,670
Okay. Điều này chúng ta sẽ nó đã có thể là tuyệt vời,

491
00:37:49,670 --> 00:37:53,990
nhưng chúng tôi sẽ làm cho nó tốt hơn.

492
00:37:53,990 --> 00:37:58,720
Này là khá nhiều cùng một ý tưởng chính xác.

493
00:37:58,720 --> 00:38:03,060
Nó chỉ là, tốt, bạn có muốn giải thích?

494
00:38:03,060 --> 00:38:08,340
[Sinh viên] Chắc chắn. Vì vậy, chúng tôi đảm bảo rằng cây không null đầu tiên,

495
00:38:08,340 --> 00:38:13,380
bởi vì nếu cây là null thì nó sẽ trả về false vì chúng ta đã không tìm thấy nó.

496
00:38:13,380 --> 00:38:19,200
Và nếu vẫn còn có một cái cây, chúng tôi đi vào - đầu tiên chúng ta kiểm tra nếu giá trị là nút hiện tại.

497
00:38:19,200 --> 00:38:23,740
Trả lại đúng sự thật nếu nó là, và nếu không recurse chúng tôi ở bên trái hoặc bên phải.

498
00:38:23,740 --> 00:38:25,970
Mà âm thanh thích hợp? >> Mm-hmm. (Hiệp định)

499
00:38:25,970 --> 00:38:33,880
Vì vậy, nhận thấy rằng điều này gần như là cấu trúc rất giống với các giải pháp lặp đi lặp lại.

500
00:38:33,880 --> 00:38:38,200
Nó chỉ là thay vì recursing, chúng tôi đã có một vòng lặp while.

501
00:38:38,200 --> 00:38:40,840
Và trường hợp cơ sở ở đây, nơi cây nào không null bằng

502
00:38:40,840 --> 00:38:44,850
là điều kiện theo đó chúng tôi đã nổ ra của vòng lặp while.

503
00:38:44,850 --> 00:38:50,200
Chúng tôi rất giống nhau. Nhưng chúng tôi sẽ phải mất thêm một bước này.

504
00:38:50,200 --> 00:38:54,190
Bây giờ, chúng tôi làm điều tương tự ở đây.

505
00:38:54,190 --> 00:38:57,680
Nhận thấy chúng ta đang quay trở lại điều tương tự trong cả hai của những dòng này,

506
00:38:57,680 --> 00:39:00,220
ngoại trừ một đối số là khác nhau.

507
00:39:00,220 --> 00:39:07,950
Vì vậy, chúng ta sẽ làm cho rằng vào một ternary.

508
00:39:07,950 --> 00:39:13,790
Tôi nhấn một cái gì đó tùy chọn, và nó được thực hiện một biểu tượng. Okay.

509
00:39:13,790 --> 00:39:21,720
Vì vậy, chúng ta sẽ quay trở lại chứa đó.

510
00:39:21,720 --> 00:39:28,030
Đây là nhận được nhiều dòng, tốt, phóng to nó.

511
00:39:28,030 --> 00:39:31,060
Thông thường, như là một điều phong cách, tôi không nghĩ rằng nhiều người

512
00:39:31,060 --> 00:39:38,640
đặt một không gian sau khi mũi tên, nhưng tôi đoán nếu bạn là nhất quán, đó là tiền phạt.

513
00:39:38,640 --> 00:39:44,320
Nếu giá trị thấp hơn giá trị cây, chúng tôi muốn để recurse bên trái cây,

514
00:39:44,320 --> 00:39:53,890
khác chúng tôi muốn để recurse bên phải cây.

515
00:39:53,890 --> 00:39:58,610
Vì vậy, đó là một bước làm cho cái nhìn nhỏ hơn.

516
00:39:58,610 --> 00:40:02,660
Bước hai làm cho cái nhìn nhỏ hơn -

517
00:40:02,660 --> 00:40:09,150
chúng ta có thể tách biệt này cho nhiều dòng.

518
00:40:09,150 --> 00:40:16,500
Okay. Bước hai làm cho nó trông nhỏ hơn là ở đây,

519
00:40:16,500 --> 00:40:25,860
do đó, giá trị trả về bằng giá trị cây, hoặc có chứa bất cứ điều gì.

520
00:40:25,860 --> 00:40:28,340
>> Đây là một điều quan trọng.

521
00:40:28,340 --> 00:40:30,860
Tôi không chắc chắn nếu ông nói nó rõ ràng trong các lớp học,

522
00:40:30,860 --> 00:40:34,740
nhưng nó được gọi là đánh giá ngắn mạch.

523
00:40:34,740 --> 00:40:41,060
Ý tưởng ở đây là giá trị == cây giá trị.

524
00:40:41,060 --> 00:40:49,960
Nếu điều đó đúng, thì đây là sự thật, và chúng tôi muốn "hoặc" chúng ta với bất cứ điều gì ở đây.

525
00:40:49,960 --> 00:40:52,520
Vì vậy, mà không cần suy nghĩ về bất cứ điều gì ở đây,

526
00:40:52,520 --> 00:40:55,070
sẽ trả lại toàn bộ biểu thức là gì?

527
00:40:55,070 --> 00:40:59,430
[Sinh viên] Đúng? >> Yeah, bởi vì thực sự của bất cứ điều gì,

528
00:40:59,430 --> 00:41:04,990
or'd or'd hoặc đúng với bất cứ điều gì là nhất thiết phải đúng.

529
00:41:04,990 --> 00:41:08,150
Vì vậy, ngay khi chúng tôi nhìn thấy giá trị trả về = giá trị cây,

530
00:41:08,150 --> 00:41:10,140
chúng ta chỉ cần đi để trở về đúng.

531
00:41:10,140 --> 00:41:15,710
Thậm chí không để recurse tiếp tục chứa xuống dòng.

532
00:41:15,710 --> 00:41:20,980
Chúng ta có thể thêm một bước này.

533
00:41:20,980 --> 00:41:29,490
Quay trở lại cây nào không null bằng nhau và tất cả những điều này.

534
00:41:29,490 --> 00:41:32,650
Nó làm cho nó một chức năng một dòng.

535
00:41:32,650 --> 00:41:36,790
Đây cũng là một ví dụ về đánh giá ngắn mạch.

536
00:41:36,790 --> 00:41:40,680
Nhưng bây giờ nó là ý tưởng tương tự -

537
00:41:40,680 --> 00:41:47,320
thay vì - vì vậy nếu cây không null bằng - hoặc, tốt,

538
00:41:47,320 --> 00:41:49,580
nếu cây vô giá trị bằng, đó là trường hợp xấu,

539
00:41:49,580 --> 00:41:54,790
nếu cây bằng null, sau đó điều kiện đầu tiên sẽ là sai lầm.

540
00:41:54,790 --> 00:42:00,550
Vì vậy, giả ANDed với bất cứ điều gì là có được những gì?

541
00:42:00,550 --> 00:42:04,640
[Sinh viên] False. >> Yeah. Đây là nửa kia của đánh giá ngắn mạch,

542
00:42:04,640 --> 00:42:10,710
nếu cây không bằng vô giá trị, sau đó chúng tôi sẽ không thậm chí đi -

543
00:42:10,710 --> 00:42:14,930
hoặc nếu cây vô giá trị bằng, sau đó chúng tôi sẽ không làm giá trị == cây giá trị.

544
00:42:14,930 --> 00:42:17,010
Chúng tôi sẽ ngay lập tức quay trở lại sai.

545
00:42:17,010 --> 00:42:20,970
Đó là quan trọng, vì nếu nó đã không ngắn mạch đánh giá các

546
00:42:20,970 --> 00:42:25,860
sau đó nếu cây vô giá trị bằng, điều kiện thứ hai này sẽ seg lỗi,

547
00:42:25,860 --> 00:42:32,510
bởi vì cây-> giá trị được dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Vì vậy, đó là điều đó. Có thể làm cho thay đổi một lần trong suốt.

549
00:42:40,490 --> 00:42:44,840
Đây là một điều rất phổ biến cũng có, không làm điều này một dòng với điều này,

550
00:42:44,840 --> 00:42:49,000
nhưng đó là một điều phổ biến trong điều kiện, có thể không đúng ở đây,

551
00:42:49,000 --> 00:42:59,380
nhưng nếu (cây NULL =, và cây-> giá trị == giá trị), làm bất cứ điều gì.

552
00:42:59,380 --> 00:43:01,560
Đây là một tình trạng rất phổ biến, thay vì phải

553
00:43:01,560 --> 00:43:06,770
để phá vỡ thành hai ifs, thích, là null cây?

554
00:43:06,770 --> 00:43:11,780
Được rồi, nó không phải null, vì vậy bây giờ là giá trị cây bằng giá trị? Làm điều này.

555
00:43:11,780 --> 00:43:17,300
Thay vào đó, điều kiện này, điều này sẽ không bao giờ seg lỗi

556
00:43:17,300 --> 00:43:21,220
bởi vì nó sẽ phá vỡ nếu điều này xảy ra được null.

557
00:43:21,220 --> 00:43:24,000
Vâng, tôi đoán nếu cây của bạn hoàn toàn là một con trỏ không hợp lệ, nó vẫn có thể seg lỗi,

558
00:43:24,000 --> 00:43:26,620
nhưng nó không thể seg lỗi nếu cây là null.

559
00:43:26,620 --> 00:43:32,900
Nếu nó là null, nó sẽ phá vỡ trước khi bạn dereferenced con trỏ ở nơi đầu tiên.

560
00:43:32,900 --> 00:43:35,000
[Sinh viên này gọi là đánh giá lười biếng?

561
00:43:35,000 --> 00:43:40,770
>> Bowden] Lazy đánh giá là một điều riêng biệt.

562
00:43:40,770 --> 00:43:49,880
Lười biếng đánh giá là giống như bạn yêu cầu một giá trị,

563
00:43:49,880 --> 00:43:54,270
bạn yêu cầu để tính toán một giá trị, loại, nhưng bạn không cần nó ngay lập tức.

564
00:43:54,270 --> 00:43:59,040
Vì vậy, cho đến khi bạn thực sự cần nó, nó không phải là đánh giá.

565
00:43:59,040 --> 00:44:03,920
Đây không phải là chính xác những điều tương tự, nhưng trong pset Huffman,

566
00:44:03,920 --> 00:44:06,520
nó nói rằng chúng ta "lười biếng" viết.

567
00:44:06,520 --> 00:44:08,670
Lý do chúng tôi làm điều đó là vì chúng ta đang thực sự đệm viết

568
00:44:08,670 --> 00:44:11,820
chúng tôi không muốn để viết các bit riêng lẻ tại một thời điểm,

569
00:44:11,820 --> 00:44:15,450
hoặc byte cá nhân tại một thời điểm, chúng tôi thay vì muốn có được một đoạn byte.

570
00:44:15,450 --> 00:44:19,270
Sau đó, một khi chúng ta có một đoạn byte, sau đó chúng tôi sẽ viết nó ra.

571
00:44:19,270 --> 00:44:22,640
Mặc dù bạn yêu cầu nó để viết và fwrite và fread làm cùng một loại điều.

572
00:44:22,640 --> 00:44:26,260
Họ đệm đọc và viết.

573
00:44:26,260 --> 00:44:31,610
Mặc dù bạn yêu cầu nó để viết ngay lập tức, nó có thể sẽ không.

574
00:44:31,610 --> 00:44:34,540
Và bạn không thể chắc chắn rằng mọi thứ sẽ phải được viết

575
00:44:34,540 --> 00:44:37,540
cho đến khi bạn gọi hfclose hoặc bất cứ điều gì nó là,

576
00:44:37,540 --> 00:44:39,620
sau đó nói, không sao, tôi đang đóng tập tin của tôi,

577
00:44:39,620 --> 00:44:43,450
điều đó có nghĩa là tôi muốn viết tốt hơn tất cả mọi thứ tôi đã không viết.

578
00:44:43,450 --> 00:44:45,770
Nó không có cần phải viết ra tất cả mọi thứ

579
00:44:45,770 --> 00:44:49,010
cho đến khi bạn đóng file, và sau đó nó cần.

580
00:44:49,010 --> 00:44:56,220
Vì vậy, đó chỉ là những gì lười biếng - nó chờ đợi cho đến khi nó đã xảy ra.

581
00:44:56,220 --> 00:44:59,990
- Lấy 51 và bạn sẽ đi vào chi tiết hơn,

582
00:44:59,990 --> 00:45:05,470
vì OCaml và tất cả mọi thứ trong 51, tất cả mọi thứ là đệ quy.

583
00:45:05,470 --> 00:45:08,890
Không có lặp đi lặp lại các giải pháp, về cơ bản.

584
00:45:08,890 --> 00:45:11,550
Tất cả mọi thứ là đệ quy, và đánh giá lười biếng

585
00:45:11,550 --> 00:45:14,790
sẽ là quan trọng cho rất nhiều hoàn cảnh

586
00:45:14,790 --> 00:45:19,920
ở đâu, nếu bạn không lazily đánh giá, mà có nghĩa -

587
00:45:19,920 --> 00:45:24,760
Ví dụ là suối, là dài vô hạn.

588
00:45:24,760 --> 00:45:30,990
Về lý thuyết, bạn có thể nghĩ các số tự nhiên như là một dòng của 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Vì vậy, lười biếng đánh giá là tốt.

590
00:45:33,090 --> 00:45:37,210
Nếu tôi nói rằng tôi muốn số thứ mười, sau đó tôi có thể đánh giá lên đến số thứ mười.

591
00:45:37,210 --> 00:45:40,300
Nếu tôi muốn số trăm, sau đó tôi có thể đánh giá lên đến số trăm.

592
00:45:40,300 --> 00:45:46,290
Nếu không có đánh giá lười biếng, sau đó nó sẽ cố gắng để đánh giá tất cả các con số ngay lập tức.

593
00:45:46,290 --> 00:45:50,000
Bạn đang đánh giá số lượng vô hạn, và đó là điều không thể.

594
00:45:50,000 --> 00:45:52,080
Vì vậy, có rất nhiều trường hợp đánh giá lười biếng

595
00:45:52,080 --> 00:45:57,840
chỉ là điều cần thiết để nhận được những điều để làm việc.

596
00:45:57,840 --> 00:46:05,260
>> Bây giờ chúng ta muốn viết chèn nơi chèn là có được

597
00:46:05,260 --> 00:46:08,430
tương tự như thay đổi trong định nghĩa của nó.

598
00:46:08,430 --> 00:46:10,470
Vì vậy, ngay bây giờ nó bool chèn (int giá trị).

599
00:46:10,470 --> 00:46:23,850
Chúng ta sẽ thay đổi điều đó để chèn bool (int giá trị, node * cây).

600
00:46:23,850 --> 00:46:29,120
Chúng tôi đang thực sự sẽ thay đổi điều đó một lần nữa trong một chút, chúng ta sẽ thấy lý do tại sao.

601
00:46:29,120 --> 00:46:32,210
Và chúng ta hãy di chuyển build_node, chỉ cần cho các heck của nó,

602
00:46:32,210 --> 00:46:36,730
trên chèn vì vậy chúng tôi không cần phải viết một mẫu thử nghiệm chức năng.

603
00:46:36,730 --> 00:46:42,450
Đó là một gợi ý rằng bạn sẽ được sử dụng build_node trong chèn.

604
00:46:42,450 --> 00:46:49,590
Okay. Hãy dành một phút cho điều đó.

605
00:46:49,590 --> 00:46:52,130
Tôi nghĩ rằng tôi đã lưu các sửa đổi nếu bạn muốn kéo từ đó,

606
00:46:52,130 --> 00:47:00,240
hoặc, ít nhất, tôi đã làm ngay bây giờ.

607
00:47:00,240 --> 00:47:04,190
Tôi muốn nghỉ ngơi một chút để suy nghĩ về logic chèn,

608
00:47:04,190 --> 00:47:08,750
nếu bạn không thể nghĩ về nó.

609
00:47:08,750 --> 00:47:12,860
Về cơ bản, bạn sẽ chỉ bao giờ được chèn tại lá.

610
00:47:12,860 --> 00:47:18,640
Giống như, nếu tôi chèn 1, sau đó tôi chắc chắn sẽ được chèn 1 -

611
00:47:18,640 --> 00:47:21,820
Tôi sẽ thay đổi sang màu đen - sẽ được chèn 1 trên đây.

612
00:47:21,820 --> 00:47:28,070
Hoặc nếu tôi chèn 4, tôi muốn được chèn 4 trên đây.

613
00:47:28,070 --> 00:47:32,180
Vì vậy, không có vấn đề gì bạn làm, bạn sẽ được chèn vào một chiếc lá.

614
00:47:32,180 --> 00:47:36,130
Tất cả những gì bạn phải làm là lặp xuống cây cho đến khi bạn nhận được để nút

615
00:47:36,130 --> 00:47:40,890
đó phải là của nút cha, nút mới của cha mẹ,

616
00:47:40,890 --> 00:47:44,560
và sau đó thay đổi con trỏ của nó sang trái hoặc phải, tùy thuộc vào việc

617
00:47:44,560 --> 00:47:47,060
nó lớn hơn hoặc ít hơn so với các nút hiện tại.

618
00:47:47,060 --> 00:47:51,180
Thay đổi con trỏ để trỏ đến nút mới của bạn.

619
00:47:51,180 --> 00:48:05,490
Vì vậy, lặp xuống cây, làm cho điểm lá để các nút mới.

620
00:48:05,490 --> 00:48:09,810
Cũng nghĩ về lý do tại sao mà cấm các loại tình hình trước khi,

621
00:48:09,810 --> 00:48:17,990
nơi mà tôi xây dựng cây nhị phân mà nó là chính xác

622
00:48:17,990 --> 00:48:19,920
nếu bạn chỉ nhìn một nút duy nhất,

623
00:48:19,920 --> 00:48:24,830
nhưng 9 là bên trái của 7 nếu bạn lặp tất cả các cách.

624
00:48:24,830 --> 00:48:29,770
Vì vậy, đó là không thể trong kịch bản này, kể từ khi

625
00:48:29,770 --> 00:48:32,530
nghĩ về chèn 9 hoặc một cái gì đó, tại nút đầu tiên,

626
00:48:32,530 --> 00:48:35,350
Tôi sẽ xem 7 và tôi chỉ cần đi bên phải.

627
00:48:35,350 --> 00:48:38,490
Vì vậy, không quan trọng những gì tôi làm, nếu tôi chèn bằng cách đi một lá,

628
00:48:38,490 --> 00:48:40,790
và một chiếc lá bằng cách sử dụng các thuật toán thích hợp,

629
00:48:40,790 --> 00:48:43,130
nó sẽ là không thể cho tôi để chèn 9 đến bên trái của 7

630
00:48:43,130 --> 00:48:48,250
bởi vì ngay sau khi tôi nhấn 7 tôi sẽ đi về bên phải.

631
00:48:59,740 --> 00:49:02,070
Có ai có một cái gì đó để bắt đầu?

632
00:49:02,070 --> 00:49:05,480
[Sinh viên] tôi làm. >> Chắc chắn rồi.

633
00:49:05,480 --> 00:49:09,200
[Sinh viên, không thể hiểu]

634
00:49:09,200 --> 00:49:14,390
[Sinh viên, không thể hiểu]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Nó được đánh giá cao. Okay. Muốn giải thích?

636
00:49:18,330 --> 00:49:20,690
>> [Sinh viên] Kể từ khi chúng ta biết rằng chúng tôi đã được chèn

637
00:49:20,690 --> 00:49:24,060
các nút mới vào cuối của cây,

638
00:49:24,060 --> 00:49:28,070
Tôi looped thông qua cây lặp đi lặp lại

639
00:49:28,070 --> 00:49:31,360
cho đến khi tôi có một nút chỉ để null.

640
00:49:31,360 --> 00:49:34,220
Và sau đó tôi đã quyết định để đặt nó hoặc bên phải hay bên trái

641
00:49:34,220 --> 00:49:37,420
bằng cách sử dụng biến này, nó nói với tôi nơi để đặt nó.

642
00:49:37,420 --> 00:49:41,850
Và sau đó, về cơ bản, tôi chỉ cần thực hiện mà cuối cùng -

643
00:49:41,850 --> 00:49:47,520
rằng nút tạm thời trỏ đến nút mới mà nó đã được tạo ra,

644
00:49:47,520 --> 00:49:50,770
hoặc là ở phía bên trái hoặc bên phải, tùy thuộc vào những gì giá trị.

645
00:49:50,770 --> 00:49:56,530
Cuối cùng, tôi thiết lập giá trị nút mới vào giá trị của thử nghiệm của nó.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Được rồi, vì vậy tôi thấy một vấn đề ở đây.

647
00:49:59,550 --> 00:50:02,050
Điều này cũng giống như 95% của con đường đó.

648
00:50:02,050 --> 00:50:07,550
Một vấn đề mà tôi thấy, tốt, không ai khác nhìn thấy một vấn đề?

649
00:50:07,550 --> 00:50:18,400
Hoàn cảnh, theo đó họ thoát ra khỏi vòng lặp là gì?

650
00:50:18,400 --> 00:50:22,100
[Sinh viên] Nếu temp là null? >> Yeah. Vì vậy, làm thế nào bạn thoát ra khỏi vòng lặp nếu tạm thời là null.

651
00:50:22,100 --> 00:50:30,220
Nhưng tôi phải làm gì phải ở đây?

652
00:50:30,220 --> 00:50:35,410
Tôi dereference temp, mà chắc chắn là vô giá trị.

653
00:50:35,410 --> 00:50:39,840
Vì vậy, điều khác bạn cần làm không phải là chỉ cần theo dõi cho đến khi temp là null,

654
00:50:39,840 --> 00:50:45,590
bạn muốn theo dõi của cha mẹ ở tất cả các lần.

655
00:50:45,590 --> 00:50:52,190
Chúng tôi cũng muốn cha mẹ * nút, tôi đoán chúng ta có thể giữ cho rằng tại vô giá trị lần đầu tiên.

656
00:50:52,190 --> 00:50:55,480
Điều này sẽ có hành vi lạ cho thư mục gốc của cây,

657
00:50:55,480 --> 00:50:59,210
nhưng chúng tôi sẽ nhận được để mà.

658
00:50:59,210 --> 00:51:03,950
Nếu giá trị lớn hơn bất cứ điều gì, sau đó tạm thời = temp đúng.

659
00:51:03,950 --> 00:51:07,910
Nhưng trước khi chúng tôi làm điều đó, cha mẹ = temp.

660
00:51:07,910 --> 00:51:14,500
Hoặc là cha mẹ vẫn luôn sẽ tạm thời bằng? Có đúng như vậy không?

661
00:51:14,500 --> 00:51:19,560
Nếu tạm thời không phải là null, sau đó tôi sẽ di chuyển xuống, không có vấn đề gì,

662
00:51:19,560 --> 00:51:24,030
đến một nút mà tạm thời là cha mẹ.

663
00:51:24,030 --> 00:51:27,500
Vì vậy, cha mẹ sẽ là tạm thời, và sau đó tôi di chuyển tạm thời xuống.

664
00:51:27,500 --> 00:51:32,410
Bây giờ tạm thời là null, nhưng phụ huynh để phụ huynh trong những điều đó là null.

665
00:51:32,410 --> 00:51:39,110
Vì vậy, ở đây, tôi không muốn để thiết lập bằng 1.

666
00:51:39,110 --> 00:51:41,300
Vì vậy, tôi chuyển sang bên phải, do đó, nếu bên phải = 1,

667
00:51:41,300 --> 00:51:45,130
và tôi đoán bạn cũng muốn làm -

668
00:51:45,130 --> 00:51:48,530
nếu bạn di chuyển sang bên trái, bạn muốn thiết lập bằng 0.

669
00:51:48,530 --> 00:51:55,950
Hoặc người nào khác nếu bạn di chuyển sang phải.

670
00:51:55,950 --> 00:51:58,590
Vì vậy, ngay = 0. Nếu bên phải = 1,

671
00:51:58,590 --> 00:52:04,260
bây giờ chúng tôi muốn làm cho cha mẹ con trỏ phải newnode,

672
00:52:04,260 --> 00:52:08,520
khác, chúng tôi muốn làm cho cha mẹ con trỏ trái newnode.

673
00:52:08,520 --> 00:52:16,850
Câu hỏi về điều đó?

674
00:52:16,850 --> 00:52:24,880
Okay. Vì vậy, đây là cách chúng ta tốt, thực sự, thay vì làm điều này,

675
00:52:24,880 --> 00:52:29,630
chúng tôi một nửa dự kiến ​​bạn sử dụng build_node.

676
00:52:29,630 --> 00:52:40,450
Và sau đó nếu newnode bằng null, trả về false.

677
00:52:40,450 --> 00:52:44,170
Đó là điều đó. Bây giờ, đây là những gì chúng ta mong đợi bạn làm.

678
00:52:44,170 --> 00:52:47,690
>> Đây là những gì các giải pháp nhân viên làm.

679
00:52:47,690 --> 00:52:52,360
Tôi không đồng ý với điều này như là cách "đúng" đi về nó

680
00:52:52,360 --> 00:52:57,820
nhưng điều này là hoàn toàn tốt đẹp và nó sẽ làm việc.

681
00:52:57,820 --> 00:53:02,840
Một điều đó là một chút quyền tại

682
00:53:02,840 --> 00:53:08,310
nếu cây bắt đầu như là null, chúng tôi vượt qua trong một cây null.

683
00:53:08,310 --> 00:53:12,650
Tôi đoán nó phụ thuộc vào cách bạn định nghĩa hành vi của đi qua trong một cây null.

684
00:53:12,650 --> 00:53:15,490
Tôi sẽ nghĩ rằng nếu bạn vượt qua trong một cây null,

685
00:53:15,490 --> 00:53:17,520
sau đó chèn giá trị vào một cây null

686
00:53:17,520 --> 00:53:23,030
chỉ phải trả lại một cây nơi mà các giá trị duy nhất là nút duy nhất.

687
00:53:23,030 --> 00:53:25,830
Mọi người đồng ý với điều đó? Bạn có thể, nếu bạn muốn,

688
00:53:25,830 --> 00:53:28,050
nếu bạn vượt qua trong một cây null

689
00:53:28,050 --> 00:53:31,320
và bạn muốn chèn một giá trị vào nó, trả về false.

690
00:53:31,320 --> 00:53:33,830
Đó là vào bạn để xác định điều đó.

691
00:53:33,830 --> 00:53:38,320
Để làm được điều đầu tiên tôi nói và sau đó -

692
00:53:38,320 --> 00:53:40,720
tốt, bạn sẽ gặp khó khăn khi làm điều đó, bởi vì

693
00:53:40,720 --> 00:53:44,090
nó sẽ dễ dàng hơn nếu chúng ta có một con trỏ toàn cầu để điều,

694
00:53:44,090 --> 00:53:48,570
nhưng chúng tôi không, vì vậy nếu cây là vô giá trị, có gì chúng ta có thể làm về điều đó.

695
00:53:48,570 --> 00:53:50,960
Chúng tôi chỉ có thể trả về false.

696
00:53:50,960 --> 00:53:52,840
Vì vậy, tôi sẽ thay đổi chèn.

697
00:53:52,840 --> 00:53:56,540
Chúng tôi về mặt kỹ thuật chỉ có thể thay đổi quyền này ở đây,

698
00:53:56,540 --> 00:53:58,400
làm thế nào nó lặp lại về những điều,

699
00:53:58,400 --> 00:54:04,530
nhưng tôi sẽ thay đổi chèn vào một nút ** cây.

700
00:54:04,530 --> 00:54:07,510
Đôi con trỏ.

701
00:54:07,510 --> 00:54:09,710
Điều này có nghĩa là gì?

702
00:54:09,710 --> 00:54:12,330
Thay vì đối phó với con trỏ đến các nút,

703
00:54:12,330 --> 00:54:16,690
điều tôi sẽ được thao tác này là con trỏ.

704
00:54:16,690 --> 00:54:18,790
Tôi sẽ được thao tác con trỏ này.

705
00:54:18,790 --> 00:54:21,770
Tôi sẽ được thao tác với con trỏ trực tiếp.

706
00:54:21,770 --> 00:54:25,760
Điều này là do, suy nghĩ về xuống -

707
00:54:25,760 --> 00:54:33,340
tốt, ngay bây giờ điều này dẫn đến giá trị null.

708
00:54:33,340 --> 00:54:38,130
Những gì tôi muốn làm là thao tác này con trỏ để trỏ đến không vô giá trị.

709
00:54:38,130 --> 00:54:40,970
Tôi muốn nó để trỏ đến nút mới của tôi.

710
00:54:40,970 --> 00:54:44,870
Nếu tôi chỉ theo dõi của các con trỏ đến con trỏ của tôi,

711
00:54:44,870 --> 00:54:47,840
sau đó tôi không cần phải theo dõi của một con trỏ mẹ.

712
00:54:47,840 --> 00:54:52,640
Tôi chỉ có thể theo dõi xem con trỏ đang trỏ đến null,

713
00:54:52,640 --> 00:54:54,580
và nếu con trỏ trỏ null,

714
00:54:54,580 --> 00:54:57,370
thay đổi nó để trỏ đến các nút tôi muốn.

715
00:54:57,370 --> 00:55:00,070
Và tôi có thể thay đổi kể từ khi tôi có một con trỏ đến con trỏ.

716
00:55:00,070 --> 00:55:02,040
Hãy xem này ngay bây giờ.

717
00:55:02,040 --> 00:55:05,470
Bạn thực sự có thể làm điều đó đệ quy khá dễ dàng.

718
00:55:05,470 --> 00:55:08,080
Chúng ta muốn làm điều đó?

719
00:55:08,080 --> 00:55:10,980
Có, chúng tôi làm.

720
00:55:10,980 --> 00:55:16,790
>> Hãy xem nó đệ quy.

721
00:55:16,790 --> 00:55:24,070
Đầu tiên, trường hợp cơ sở của chúng tôi sẽ làm gì?

722
00:55:24,070 --> 00:55:29,140
Hầu như luôn luôn trường hợp cơ sở của chúng tôi, nhưng trên thực tế, đây là loại phức tạp.

723
00:55:29,140 --> 00:55:34,370
Trước tiên, nếu (cây == NULL)

724
00:55:34,370 --> 00:55:37,550
Tôi đoán chúng tôi chỉ sẽ trả về false.

725
00:55:37,550 --> 00:55:40,460
Điều này là khác nhau từ cây là vô giá trị của bạn.

726
00:55:40,460 --> 00:55:44,510
Đây là con trỏ đến con trỏ gốc của bạn đang được null

727
00:55:44,510 --> 00:55:48,360
có nghĩa là con trỏ gốc của bạn không tồn tại.

728
00:55:48,360 --> 00:55:52,390
Vì vậy, xuống đây, nếu tôi làm

729
00:55:52,390 --> 00:55:55,760
node * - chúng ta hãy tái sử dụng.

730
00:55:55,760 --> 00:55:58,960
Node * root = NULL,

731
00:55:58,960 --> 00:56:00,730
và sau đó tôi sẽ gọi chèn bằng cách làm một cái gì đó như,

732
00:56:00,730 --> 00:56:04,540
chèn 4 vào & gốc.

733
00:56:04,540 --> 00:56:06,560
So & root, nếu thư mục gốc là một nút *

734
00:56:06,560 --> 00:56:11,170
sau đó & gốc là có được một ** nút.

735
00:56:11,170 --> 00:56:15,120
Điều này là hợp lệ. Trong trường hợp này, cây, lên đây,

736
00:56:15,120 --> 00:56:20,120
cây không phải là null - hoặc chèn.

737
00:56:20,120 --> 00:56:24,630
Ở đây. Cây là không null * cây là vô giá trị, mà là tốt

738
00:56:24,630 --> 00:56:26,680
bởi vì nếu cây * là null, sau đó tôi có thể thao tác nó

739
00:56:26,680 --> 00:56:29,210
đến nay chỉ những gì tôi muốn nó để trỏ đến.

740
00:56:29,210 --> 00:56:34,750
Nhưng nếu cây là vô giá trị, có nghĩa là tôi chỉ cần đến đây và nói vô giá trị.

741
00:56:34,750 --> 00:56:42,710
Điều đó không có ý nghĩa. Tôi không thể làm bất cứ điều gì với điều đó.

742
00:56:42,710 --> 00:56:45,540
Nếu cây là null, trả về false.

743
00:56:45,540 --> 00:56:48,220
Vì vậy, về cơ bản tôi đã nói những gì trường hợp cơ sở thực của chúng tôi là.

744
00:56:48,220 --> 00:56:50,580
Và đó là những gì được?

745
00:56:50,580 --> 00:56:55,030
[Sinh viên, không thể hiểu]

746
00:56:55,030 --> 00:57:00,000
[Bowden]. Vì vậy, nếu (* cây == NULL).

747
00:57:00,000 --> 00:57:04,520
Điều này liên quan đến các trường hợp trên đây

748
00:57:04,520 --> 00:57:09,640
nếu con trỏ màu đỏ của tôi là con trỏ tôi đang tập trung vào,

749
00:57:09,640 --> 00:57:12,960
như tôi đang tập trung vào con trỏ này, bây giờ tôi đang tập trung vào con trỏ này.

750
00:57:12,960 --> 00:57:15,150
Bây giờ tôi đang tập trung vào con trỏ này.

751
00:57:15,150 --> 00:57:18,160
Vì vậy, nếu con trỏ màu đỏ của tôi, mà là ** nút,

752
00:57:18,160 --> 00:57:22,880
bao giờ hết - nếu *, con trỏ màu đỏ của tôi, bao giờ là vô giá trị,

753
00:57:22,880 --> 00:57:28,470
điều đó có nghĩa là tôi đang ở trường hợp mà tôi đang tập trung vào một con trỏ trỏ -

754
00:57:28,470 --> 00:57:32,530
đây là một con trỏ thuộc về một chiếc lá.

755
00:57:32,530 --> 00:57:41,090
Tôi muốn thay đổi con trỏ để trỏ đến nút mới của tôi.

756
00:57:41,090 --> 00:57:45,230
Trở lại ở đây.

757
00:57:45,230 --> 00:57:56,490
Newnode của tôi sẽ chỉ được node * n = build_node (giá trị)

758
00:57:56,490 --> 00:58:07,300
sau đó n, nếu n = NULL, trả về false.

759
00:58:07,300 --> 00:58:12,600
Khác, chúng tôi muốn thay đổi những gì con trỏ trỏ đến

760
00:58:12,600 --> 00:58:17,830
trỏ đến nút mới được xây dựng của chúng tôi.

761
00:58:17,830 --> 00:58:20,280
Chúng tôi thực sự có thể làm điều đó ở đây.

762
00:58:20,280 --> 00:58:30,660
Thay vì nói n, chúng ta nói * cây = nếu * cây.

763
00:58:30,660 --> 00:58:35,450
Mọi người đều hiểu rằng? Đó là bằng cách giao dịch với các con trỏ để trỏ,

764
00:58:35,450 --> 00:58:40,750
chúng ta có thể thay đổi con trỏ null để trỏ đến những điều chúng tôi muốn họ để trỏ đến.

765
00:58:40,750 --> 00:58:42,820
Đó là trường hợp cơ sở của chúng tôi.

766
00:58:42,820 --> 00:58:45,740
>> Bây giờ chúng tôi tái phát, hoặc đệ quy của chúng tôi,

767
00:58:45,740 --> 00:58:51,430
sẽ là rất tương tự như tất cả các recursions khác chúng tôi đã làm.

768
00:58:51,430 --> 00:58:55,830
Chúng tôi sẽ muốn để chèn giá trị,

769
00:58:55,830 --> 00:58:59,040
và bây giờ tôi sẽ sử dụng ternary một lần nữa, nhưng tình trạng của chúng tôi sẽ làm gì?

770
00:58:59,040 --> 00:59:05,180
Đó là những gì chúng tôi đang tìm kiếm để quyết định xem chúng ta muốn đi sang trái hoặc phải?

771
00:59:05,180 --> 00:59:07,760
Hãy làm điều đó trong các bước riêng biệt.

772
00:59:07,760 --> 00:59:18,850
Nếu (giá trị <)?

773
00:59:18,850 --> 00:59:23,200
[Sinh viên] giá trị của cây?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Vì vậy, hãy nhớ rằng tôi là hiện nay -

775
00:59:27,490 --> 00:59:31,260
[Sinh viên, không thể hiểu]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, vì vậy ngay tại đây, chúng ta hãy nói rằng mũi tên màu xanh lá cây này

777
00:59:34,140 --> 00:59:39,050
là một ví dụ về cây hiện nay là gì, là một con trỏ đến con trỏ này.

778
00:59:39,050 --> 00:59:46,610
Vì vậy, điều đó có nghĩa là tôi là một con trỏ đến một con trỏ đến 3.

779
00:59:46,610 --> 00:59:48,800
Dereference hai lần nghe có vẻ tốt.

780
00:59:48,800 --> 00:59:51,010
Những gì tôi - làm thế nào để tôi làm điều đó?

781
00:59:51,010 --> 00:59:53,210
[Sinh viên] tham chiếu đến một lần, và sau đó mũi tên làm theo cách đó?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Vì vậy, (cây) dereference một lần, -> giá trị

783
00:59:58,420 --> 01:00:05,960
sẽ đưa cho tôi giá trị của các nút mà tôi đang gián tiếp chỉ ra.

784
01:00:05,960 --> 01:00:11,980
Vì vậy, tôi cũng có thể viết nó ** tree.value nếu bạn thích điều đó.

785
01:00:11,980 --> 01:00:18,490
Hoặc là công trình.

786
01:00:18,490 --> 01:00:26,190
Nếu đó là trường hợp, sau đó tôi muốn gọi chèn có giá trị.

787
01:00:26,190 --> 01:00:32,590
Và nút của tôi cập nhật được những gì ** sẽ được?

788
01:00:32,590 --> 01:00:39,440
Tôi muốn đi bên trái, vì vậy ** tree.left là có được trái của tôi.

789
01:00:39,440 --> 01:00:41,900
Và tôi muốn con trỏ để điều đó

790
01:00:41,900 --> 01:00:44,930
do đó nếu bên trái kết thúc lên được con trỏ null,

791
01:00:44,930 --> 01:00:48,360
Tôi có thể sửa đổi nó để trỏ đến nút mới của tôi.

792
01:00:48,360 --> 01:00:51,460
>> Và các trường hợp khác có thể rất giống nhau.

793
01:00:51,460 --> 01:00:55,600
Hãy để thực sự làm cho ternary của tôi ngay bây giờ.

794
01:00:55,600 --> 01:01:04,480
Chèn giá trị nếu giá trị <(** cây). Giá trị.

795
01:01:04,480 --> 01:01:11,040
Sau đó, chúng tôi muốn để cập nhật ** của chúng tôi sang bên trái,

796
01:01:11,040 --> 01:01:17,030
khác, chúng tôi muốn để cập nhật ** bên phải.

797
01:01:17,030 --> 01:01:22,540
[Sinh viên] mà có được con trỏ đến con trỏ?

798
01:01:22,540 --> 01:01:30,940
[Bowden Hãy nhớ rằng - ** tree.right là một ngôi sao nút.

799
01:01:30,940 --> 01:01:35,040
[Sinh viên, không thể hiểu] >> Vâng.

800
01:01:35,040 --> 01:01:41,140
** Tree.right là như thế này con trỏ hoặc một cái gì đó.

801
01:01:41,140 --> 01:01:45,140
Vì vậy, bằng cách tham gia một con trỏ vào đó, điều đó mang lại cho tôi những gì tôi muốn

802
01:01:45,140 --> 01:01:50,090
của con trỏ để anh chàng đó.

803
01:01:50,090 --> 01:01:54,260
[Sinh viên] chúng ta có thể đi qua một lần nữa lý do tại sao chúng tôi đang sử dụng hai con trỏ?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Vì vậy, - không có, bạn có thể, và giải pháp đó trước khi

805
01:01:58,220 --> 01:02:04,540
là một cách để làm việc đó mà không làm hai con trỏ.

806
01:02:04,540 --> 01:02:08,740
Bạn cần để có thể hiểu được bằng cách sử dụng hai con trỏ,

807
01:02:08,740 --> 01:02:11,660
và đây là một giải pháp sạch hơn.

808
01:02:11,660 --> 01:02:16,090
Ngoài ra, lưu ý rằng, những gì sẽ xảy ra nếu cây của tôi -

809
01:02:16,090 --> 01:02:24,480
điều gì sẽ xảy ra nếu thư mục gốc của tôi là vô giá trị? Điều gì sẽ xảy ra nếu tôi làm trường hợp này ngay tại đây không?

810
01:02:24,480 --> 01:02:30,540
Vì vậy, node * gốc = NULL, chèn 4 vào & gốc.

811
01:02:30,540 --> 01:02:35,110
Gốc được sẽ làm gì sau này?

812
01:02:35,110 --> 01:02:37,470
[Sinh viên, không thể hiểu] >> Vâng.

813
01:02:37,470 --> 01:02:41,710
Gốc giá trị là 4.

814
01:02:41,710 --> 01:02:45,510
Gốc bên trái sẽ được null, root quyền sẽ được null.

815
01:02:45,510 --> 01:02:49,490
Trong trường hợp chúng tôi đã không vượt qua gốc theo địa chỉ,

816
01:02:49,490 --> 01:02:52,490
chúng ta không thể sửa đổi root.

817
01:02:52,490 --> 01:02:56,020
Trong trường hợp cây gốc là vô giá trị,

818
01:02:56,020 --> 01:02:58,410
chúng tôi chỉ phải trả về false. Không có gì chúng ta có thể làm.

819
01:02:58,410 --> 01:03:01,520
Chúng tôi không thể chèn một nút vào một cây rỗng.

820
01:03:01,520 --> 01:03:06,810
Nhưng bây giờ chúng ta có thể, chúng ta chỉ cần thực hiện một cây đổ vào một cây một nút.

821
01:03:06,810 --> 01:03:13,400
Mà thường là cách dự kiến ​​rằng nó là nghĩa vụ phải làm việc.

822
01:03:13,400 --> 01:03:21,610
>> Hơn nữa, điều này là đáng kể ngắn hơn

823
01:03:21,610 --> 01:03:26,240
cũng theo dõi của cha mẹ, và do đó bạn lặp lại tất cả các cách.

824
01:03:26,240 --> 01:03:30,140
Bây giờ tôi có cha mẹ của tôi, và tôi chỉ có con trỏ phải cha mẹ của tôi bất cứ điều gì.

825
01:03:30,140 --> 01:03:35,640
Thay vào đó, nếu chúng ta đã làm điều này lặp đi lặp lại, nó muốn được cùng ý tưởng với một vòng lặp trong khi.

826
01:03:35,640 --> 01:03:38,100
Nhưng thay vì phải đối phó với con trỏ cha mẹ của tôi,

827
01:03:38,100 --> 01:03:40,600
thay vì con trỏ hiện tại của tôi sẽ là điều

828
01:03:40,600 --> 01:03:43,790
mà tôi đang trực tiếp sửa đổi để trỏ đến nút mới của tôi.

829
01:03:43,790 --> 01:03:46,090
Tôi không có để đối phó với cho dù đó là chỉ bên trái.

830
01:03:46,090 --> 01:03:48,810
Tôi không có để đối phó với cho dù đó là chỉ bên phải.

831
01:03:48,810 --> 01:04:00,860
Nó chỉ là bất cứ điều gì con trỏ này, tôi sẽ thiết lập nó để trỏ đến nút mới của tôi.

832
01:04:00,860 --> 01:04:05,740
Mọi người đều hiểu nó hoạt động như thế nào?

833
01:04:05,740 --> 01:04:09,460
Nếu không tại sao chúng ta muốn làm điều đó theo cách này,

834
01:04:09,460 --> 01:04:14,920
nhưng ít nhất đó công trình này như là một giải pháp?

835
01:04:14,920 --> 01:04:17,110
[Sinh viên] Nơi nào chúng ta trở lại đúng sự thật?

836
01:04:17,110 --> 01:04:21,550
Bowden] Đó có thể là ngay tại đây.

837
01:04:21,550 --> 01:04:26,690
Nếu chúng ta một cách chính xác chèn nó, trả lại đúng sự thật.

838
01:04:26,690 --> 01:04:32,010
Khác, xuống đây chúng ta sẽ muốn quay trở lại trả về chèn bất cứ điều gì.

839
01:04:32,010 --> 01:04:35,950
>> Và những gì đặc biệt về chức năng này đệ quy?

840
01:04:35,950 --> 01:04:43,010
Đó là đệ quy đuôi, như vậy miễn là chúng tôi biên dịch với một số tối ưu,

841
01:04:43,010 --> 01:04:48,060
nó sẽ nhận ra điều đó và bạn sẽ không bao giờ nhận được một chồng tràn từ này,

842
01:04:48,060 --> 01:04:53,230
ngay cả khi cây của chúng tôi có độ cao 10.000 hoặc 10 triệu.

843
01:04:53,230 --> 01:04:55,630
[Sinh viên, không thể hiểu]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Tôi nghĩ rằng nó có phải nó Dash - hoặc những gì tối ưu hóa mức độ

845
01:05:00,310 --> 01:05:03,820
là cần thiết cho một đệ quy đuôi để được công nhận.

846
01:05:03,820 --> 01:05:09,350
Tôi nghĩ rằng nó nhận ra - GCC và Clang

847
01:05:09,350 --> 01:05:12,610
cũng có ý nghĩa khác nhau cho các mức độ tối ưu hóa của họ.

848
01:05:12,610 --> 01:05:17,870
Tôi muốn nói đó là 2 DashO, chắc chắn rằng nó sẽ nhận ra đệ quy đuôi.

849
01:05:17,870 --> 01:05:27,880
Nhưng chúng ta - bạn có thể xây dựng giống như một ví dụ Fibonocci hoặc một cái gì đó.

850
01:05:27,880 --> 01:05:30,030
Nó không phải dễ dàng để thử nghiệm với điều này, bởi vì rất khó để xây dựng

851
01:05:30,030 --> 01:05:32,600
một cây nhị phân đó là quá lớn.

852
01:05:32,600 --> 01:05:37,140
Nhưng yeah, tôi nghĩ rằng đó là 2 DashO,

853
01:05:37,140 --> 01:05:40,580
nếu bạn biên dịch với DashO 2, nó sẽ tìm kiếm đệ quy đuôi

854
01:05:40,580 --> 01:05:54,030
và tối ưu hóa mà ra.

855
01:05:54,030 --> 01:05:58,190
Hãy quay trở lại - chèn nghĩa là điều cuối cùng cần thiết.

856
01:05:58,190 --> 01:06:04,900
Hãy quay trở lại để chèn ở đây

857
01:06:04,900 --> 01:06:07,840
nơi mà chúng tôi đang đi để làm cùng một ý tưởng.

858
01:06:07,840 --> 01:06:14,340
Nó vẫn sẽ có lỗ hổng không thể hoàn toàn xử lý

859
01:06:14,340 --> 01:06:17,940
khi người chủ là null, hoặc nhập cảnh qua là null,

860
01:06:17,940 --> 01:06:20,060
nhưng thay vì đối phó với một con trỏ cha mẹ,

861
01:06:20,060 --> 01:06:27,430
hãy áp dụng cùng một logic của con trỏ giữ cho con trỏ.

862
01:06:27,430 --> 01:06:35,580
Nếu ở đây chúng tôi giữ nút của chúng tôi ** hiện,

863
01:06:35,580 --> 01:06:37,860
và chúng tôi không cần phải theo dõi nữa,

864
01:06:37,860 --> 01:06:47,190
nhưng nút ** hiện = & cây.

865
01:06:47,190 --> 01:06:54,800
Và bây giờ vòng lặp trong khi của chúng tôi là có được trong khi * hiện không null bằng.

866
01:06:54,800 --> 01:07:00,270
Bạn không cần phải theo dõi của cha mẹ nữa.

867
01:07:00,270 --> 01:07:04,180
Bạn không cần phải theo dõi của trái và bên phải.

868
01:07:04,180 --> 01:07:10,190
Và tôi sẽ gọi nó là tạm thời, bởi vì chúng tôi đã sử dụng tạm thời.

869
01:07:10,190 --> 01:07:17,200
Okay. Vì vậy, nếu (giá trị> * temp),

870
01:07:17,200 --> 01:07:24,010
sau đó & (* temp) -> quyền

871
01:07:24,010 --> 01:07:29,250
khác temp = & (* temp) -> còn lại.

872
01:07:29,250 --> 01:07:32,730
Và bây giờ, thời điểm này, sau khi vòng lặp trong khi,

873
01:07:32,730 --> 01:07:36,380
Tôi chỉ làm điều này bởi vì có thể nó dễ dàng hơn để suy nghĩ về lặp đi lặp lại hơn đệ quy,

874
01:07:36,380 --> 01:07:39,010
nhưng sau khi vòng lặp trong khi,

875
01:07:39,010 --> 01:07:43,820
* Temp là con trỏ chúng ta muốn thay đổi.

876
01:07:43,820 --> 01:07:48,960
>> Trước khi chúng tôi đã có cha mẹ, và chúng tôi muốn thay đổi trái cha hoặc mẹ hoặc phải cha mẹ,

877
01:07:48,960 --> 01:07:51,310
nhưng nếu chúng ta muốn thay đổi quyền cha mẹ,

878
01:07:51,310 --> 01:07:54,550
sau đó * temp là cha mẹ phải, và chúng ta có thể thay đổi trực tiếp.

879
01:07:54,550 --> 01:08:05,860
Vì vậy, ở đây, chúng ta có thể làm * temp = newnode, và đó là nó.

880
01:08:05,860 --> 01:08:09,540
Vì vậy, thông báo, tất cả những gì chúng ta đã làm trong này là đưa ra dòng mã.

881
01:08:09,540 --> 01:08:14,770
Để theo dõi của cha mẹ trong tất cả là nỗ lực thêm.

882
01:08:14,770 --> 01:08:18,689
Ở đây, nếu chúng ta chỉ theo dõi của con trỏ đến con trỏ,

883
01:08:18,689 --> 01:08:22,990
và thậm chí nếu chúng tôi muốn để có được loại bỏ tất cả các dấu ngoặc nhọn,

884
01:08:22,990 --> 01:08:27,170
làm cho nó trông ngắn hơn.

885
01:08:27,170 --> 01:08:32,529
Điều này bây giờ là cùng một giải pháp chính xác,

886
01:08:32,529 --> 01:08:38,210
nhưng ít dòng mã.

887
01:08:38,210 --> 01:08:41,229
Một khi bạn bắt đầu nhận ra điều này như là một giải pháp hợp lệ,

888
01:08:41,229 --> 01:08:43,529
nó cũng dễ dàng hơn về lý do như, được rồi,

889
01:08:43,529 --> 01:08:45,779
tại sao tôi có lá cờ này ở bên phải int?

890
01:08:45,779 --> 01:08:49,290
Điều đó có nghĩa là gì? Ồ, nó báo hiệu rằng

891
01:08:49,290 --> 01:08:51,370
mỗi khi tôi đi ngay, tôi cần phải đặt nó,

892
01:08:51,370 --> 01:08:53,819
khác nếu tôi đi để lại tôi cần phải đặt nó không.

893
01:08:53,819 --> 01:09:04,060
Ở đây, tôi không có lý do về điều đó, nó chỉ là dễ dàng hơn để suy nghĩ về.

894
01:09:04,060 --> 01:09:06,710
Câu hỏi?

895
01:09:06,710 --> 01:09:16,290
[Sinh viên, không thể hiểu] >> Vâng.

896
01:09:16,290 --> 01:09:23,359
Được rồi, do đó, trong các bit cuối cùng -

897
01:09:23,359 --> 01:09:28,080
Tôi đoán một cách nhanh chóng và dễ dàng chức năng chúng ta có thể làm là,

898
01:09:28,080 --> 01:09:34,910
let's - cùng, tôi đoán, thử và viết có chứa chức năng

899
01:09:34,910 --> 01:09:38,899
mà không quan tâm cho dù đó là một cây tìm kiếm nhị phân.

900
01:09:38,899 --> 01:09:43,770
Này bao gồm các chức năng nên trở lại đúng sự thật

901
01:09:43,770 --> 01:09:58,330
nếu bất cứ nơi nào trong cây nhị phân này nói chung là các giá trị mà chúng ta đang tìm kiếm.

902
01:09:58,330 --> 01:10:02,520
Vì vậy, hãy đầu tiên làm cho nó đệ quy và sau đó chúng tôi sẽ làm điều đó lặp đi lặp lại.

903
01:10:02,520 --> 01:10:07,300
Chúng ta có thể thực sự chỉ làm điều đó với nhau, bởi vì điều này là có được thực sự ngắn.

904
01:10:07,300 --> 01:10:11,510
>> Trường hợp cơ sở của tôi là gì được không?

905
01:10:11,510 --> 01:10:13,890
[Sinh viên, không thể hiểu]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Vì vậy, nếu (cây == NULL), sau đó những gì?

907
01:10:18,230 --> 01:10:22,740
[Sinh viên] Quay trở lại sai.

908
01:10:22,740 --> 01:10:26,160
[Bowden] khac, tốt, tôi không cần gì khác.

909
01:10:26,160 --> 01:10:30,250
Nếu là trường hợp cơ sở khác của tôi.

910
01:10:30,250 --> 01:10:32,450
[Sinh viên] Tree của giá trị? >> Yeah.

911
01:10:32,450 --> 01:10:36,430
Vì vậy, nếu (cây-> giá trị == giá trị.

912
01:10:36,430 --> 01:10:39,920
Chú ý chúng tôi đang trở lại nút *, không phải nút ** s?

913
01:10:39,920 --> 01:10:42,990
Chứa sẽ không bao giờ cần phải sử dụng một ** nút,

914
01:10:42,990 --> 01:10:45,480
vì chúng tôi không thay đổi con trỏ.

915
01:10:45,480 --> 01:10:50,540
Chúng tôi chỉ đi qua chúng.

916
01:10:50,540 --> 01:10:53,830
Nếu điều đó xảy ra, sau đó chúng tôi muốn để trở về đúng.

917
01:10:53,830 --> 01:10:58,270
Khác, chúng tôi muốn đi qua các con.

918
01:10:58,270 --> 01:11:02,620
Vì vậy, chúng ta không thể lý luận về việc liệu tất cả mọi thứ bên trái là ít

919
01:11:02,620 --> 01:11:05,390
và tất cả mọi thứ bên phải là lớn hơn.

920
01:11:05,390 --> 01:11:09,590
Vì vậy, điều kiện của chúng tôi là những gì sẽ ở đây - hoặc, những gì chúng ta sẽ làm gì?

921
01:11:09,590 --> 01:11:11,840
[Sinh viên, không thể hiểu] >> Vâng.

922
01:11:11,840 --> 01:11:17,400
Quay lại chứa (giá trị, cây bên trái)

923
01:11:17,400 --> 01:11:26,860
hoặc có chứa (giá trị, cây-> phải). Và đó là nó.

924
01:11:26,860 --> 01:11:29,080
Và nhận thấy có một số đánh giá ngắn mạch,

925
01:11:29,080 --> 01:11:32,520
nơi mà nếu chúng xảy ra để tìm giá trị ở cây bên trái,

926
01:11:32,520 --> 01:11:36,820
chúng tôi không bao giờ cần phải nhìn vào cây bên phải.

927
01:11:36,820 --> 01:11:40,430
Đó là toàn bộ chức năng.

928
01:11:40,430 --> 01:11:43,690
Bây giờ chúng ta hãy làm điều đó lặp đi lặp lại,

929
01:11:43,690 --> 01:11:48,060
đó là sẽ được tốt đẹp ít.

930
01:11:48,060 --> 01:11:54,750
Chúng ta sẽ bắt đầu thông thường của hiện node = cây.

931
01:11:54,750 --> 01:12:03,250
Trong khi (hiện = NULL).

932
01:12:03,250 --> 01:12:08,600
Sẽ nhanh chóng thấy một vấn đề.

933
01:12:08,600 --> 01:12:12,250
Nếu hiện ra ở đây, nếu chúng ta đã bao giờ thoát ra khỏi điều này,

934
01:12:12,250 --> 01:12:16,020
sau đó chúng tôi đã chạy ra khỏi những điều để xem xét, trả về false.

935
01:12:16,020 --> 01:12:24,810
Nếu (hiện-> giá trị == giá trị), trở lại đúng sự thật.

936
01:12:24,810 --> 01:12:32,910
Vì vậy, bây giờ, chúng ta đang ở một nơi -

937
01:12:32,910 --> 01:12:36,250
chúng tôi không biết liệu chúng tôi muốn đi sang trái hoặc phải.

938
01:12:36,250 --> 01:12:44,590
Vì vậy, tùy tiện, chúng ta hãy đi lại.

939
01:12:44,590 --> 01:12:47,910
Tôi đã rõ ràng là chạy vào một vấn đề mà tôi đã hoàn toàn bị bỏ rơi tất cả mọi thứ -

940
01:12:47,910 --> 01:12:50,760
Tôi sẽ chỉ bao giờ kiểm tra phía bên trái của một cái cây.

941
01:12:50,760 --> 01:12:56,050
Tôi sẽ không bao giờ kiểm tra bất cứ điều gì mà là một đứa trẻ bên phải của bất cứ điều gì.

942
01:12:56,050 --> 01:13:00,910
Làm thế nào để sửa lỗi này?

943
01:13:00,910 --> 01:13:05,260
[Sinh viên] Bạn có theo dõi bên trái và bên phải trong một ngăn xếp.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Vì vậy, hãy làm cho nó

945
01:13:13,710 --> 01:13:32,360
cấu trúc danh sách, node * n, và sau đó nút ** tiếp theo?

946
01:13:32,360 --> 01:13:40,240
Tôi nghĩ rằng hoạt động tốt.

947
01:13:40,240 --> 01:13:45,940
Chúng tôi muốn đi qua bên trái, hoặc let's lên ở đây.

948
01:13:45,940 --> 01:13:54,350
Struct = danh sách danh sách, nó sẽ bắt đầu

949
01:13:54,350 --> 01:13:58,170
trong cấu trúc danh sách này.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Vì vậy, đó sẽ là danh sách liên kết của chúng tôi

951
01:14:04,040 --> 01:14:08,430
subtrees mà chúng ta đã bỏ qua.

952
01:14:08,430 --> 01:14:13,800
Chúng tôi sẽ đi qua còn lại bây giờ,

953
01:14:13,800 --> 01:14:17,870
nhưng kể từ khi chúng tôi chắc chắn cần phải quay trở lại bên phải,

954
01:14:17,870 --> 01:14:26,140
Chúng tôi sẽ tiếp tục ở bên phải trong danh sách cấu trúc của chúng tôi.

955
01:14:26,140 --> 01:14:32,620
Sau đó, chúng tôi sẽ có hoặc struct new_list,

956
01:14:32,620 --> 01:14:41,080
struct list * new_list = malloc (sizeof (danh sách)).

957
01:14:41,080 --> 01:14:44,920
Tôi sẽ bỏ qua lỗi kiểm tra, nhưng bạn nên kiểm tra để xem nếu nó là vô giá trị.

958
01:14:44,920 --> 01:14:50,540
New_list nút nó sẽ để trỏ đến -

959
01:14:50,540 --> 01:14:56,890
oh, đó là lý do tại sao tôi muốn nó lên đây. Nó sẽ để trỏ đến một danh sách cấu trúc thứ hai.

960
01:14:56,890 --> 01:15:02,380
Đó chỉ là cách các danh sách liên kết công việc.

961
01:15:02,380 --> 01:15:04,810
Điều này tương tự như là một danh sách liên kết int

962
01:15:04,810 --> 01:15:06,960
ngoại trừ chúng ta chỉ cần thay thế int * nút.

963
01:15:06,960 --> 01:15:11,040
Nó chính xác như nhau.

964
01:15:11,040 --> 01:15:15,100
Vì vậy, new_list, giá trị của nút new_list của chúng tôi,

965
01:15:15,100 --> 01:15:19,120
sẽ hiện ngay.

966
01:15:19,120 --> 01:15:24,280
Giá trị của chúng tôi new_list-> tiếp theo là có được danh sách ban đầu của chúng tôi,

967
01:15:24,280 --> 01:15:30,760
và sau đó chúng tôi sẽ cập nhật danh sách của chúng tôi để trỏ đến new_list.

968
01:15:30,760 --> 01:15:33,650
>> Bây giờ chúng tôi cần một số loại của cách điều kéo,

969
01:15:33,650 --> 01:15:37,020
như chúng ta đã đi qua bên trái toàn bộ cây con.

970
01:15:37,020 --> 01:15:40,480
Bây giờ chúng ta cần công cụ để kéo ra khỏi nó,

971
01:15:40,480 --> 01:15:43,850
như hiện null; chúng tôi không muốn chỉ cần trả về false.

972
01:15:43,850 --> 01:15:50,370
Chúng tôi muốn đến nay kéo bên ngoài danh sách mới của chúng tôi.

973
01:15:50,370 --> 01:15:53,690
Một cách thuận tiện để làm điều này, trên thực tế, có nhiều cách để làm điều này.

974
01:15:53,690 --> 01:15:56,680
Bất cứ ai cũng có một đề nghị?

975
01:15:56,680 --> 01:15:58,790
Tôi nên làm điều này hoặc làm thế nào tôi nên làm điều này?

976
01:15:58,790 --> 01:16:08,010
Chúng tôi chỉ có một vài phút, nhưng bất cứ đề nghị?

977
01:16:08,010 --> 01:16:14,750
Thay vì một cách, thay vì tình trạng của chúng tôi là trong khi đó,

978
01:16:14,750 --> 01:16:17,090
những gì chúng tôi hiện đang xem xét không phải là null,

979
01:16:17,090 --> 01:16:22,340
thay vào đó, chúng ta sẽ tiếp tục đi cho đến khi danh sách của chúng tôi chính nó là null.

980
01:16:22,340 --> 01:16:25,680
Vì vậy, nếu danh sách của chúng tôi kết thúc đang được null,

981
01:16:25,680 --> 01:16:30,680
sau đó chúng tôi đã chạy ra khỏi những điều để tìm, để tìm kiếm trên.

982
01:16:30,680 --> 01:16:39,860
Nhưng điều đó có nghĩa rằng điều đầu tiên trong danh sách của chúng tôi là chỉ cần đi sẽ làm nút đầu tiên.

983
01:16:39,860 --> 01:16:49,730
Điều đầu tiên sẽ được - chúng ta không còn cần phải thấy rằng.

984
01:16:49,730 --> 01:16:58,710
Vì vậy, danh sách> n sẽ là cây của chúng tôi.

985
01:16:58,710 --> 01:17:02,860
list-> tiếp theo sẽ được null.

986
01:17:02,860 --> 01:17:07,580
Và bây giờ, trong khi danh sách không phải là null bằng.

987
01:17:07,580 --> 01:17:11,610
Cur sẽ kéo một cái gì đó từ danh sách của chúng tôi.

988
01:17:11,610 --> 01:17:13,500
Vì vậy, hiện đang đi vào danh sách> bằng n.

989
01:17:13,500 --> 01:17:20,850
Và sau đó danh sách sẽ vào danh sách> bằng n, hoặc danh sách-> tiếp theo.

990
01:17:20,850 --> 01:17:23,480
Vì vậy, nếu hiện giá trị bằng giá trị.

991
01:17:23,480 --> 01:17:28,790
Bây giờ chúng ta có thể thêm cả con trỏ quyền của chúng ta và con trỏ trái của chúng tôi

992
01:17:28,790 --> 01:17:32,900
miễn là chúng tôi không phải là null.

993
01:17:32,900 --> 01:17:36,390
Xuống đây, tôi đoán chúng ta nên đã làm điều đó ở nơi đầu tiên.

994
01:17:36,390 --> 01:17:44,080
Nếu (hiện> bên phải = NULL!)

995
01:17:44,080 --> 01:17:56,380
sau đó chúng ta sẽ để chèn nút vào danh sách của chúng tôi.

996
01:17:56,380 --> 01:17:59,290
Nếu (hiện-> bên trái), đây là một chút công việc phụ, nhưng nó tốt.

997
01:17:59,290 --> 01:18:02,690
Nếu (hiện-> trái = NULL!)

998
01:18:02,690 --> 01:18:14,310
và chúng tôi sẽ để chèn phía bên trái vào danh sách liên kết của chúng tôi,

999
01:18:14,310 --> 01:18:19,700
và đó nên được nó.

1000
01:18:19,700 --> 01:18:22,670
Chúng tôi lặp đi lặp lại - miễn là chúng ta có một cái gì đó trong danh sách của chúng tôi,

1001
01:18:22,670 --> 01:18:26,640
chúng tôi có một nút khác để xem xét.

1002
01:18:26,640 --> 01:18:28,920
Vì vậy, chúng ta nhìn vào nút đó,

1003
01:18:28,920 --> 01:18:31,390
chúng ta tiến danh sách của chúng tôi đến tiếp theo.

1004
01:18:31,390 --> 01:18:34,060
Nếu nút đó là giá trị mà chúng ta đang tìm kiếm, chúng tôi có thể trở lại đúng sự thật.

1005
01:18:34,060 --> 01:18:37,640
Khác chèn cả hai chúng tôi subtrees trái và bên phải,

1006
01:18:37,640 --> 01:18:40,510
miễn là họ không phải là null, vào danh sách của chúng tôi

1007
01:18:40,510 --> 01:18:43,120
để chúng ta chắc đã đi qua chúng.

1008
01:18:43,120 --> 01:18:45,160
Vì vậy, nếu họ không phải là vô giá trị,

1009
01:18:45,160 --> 01:18:47,950
nếu con trỏ gốc của chúng tôi chỉ ra hai điều,

1010
01:18:47,950 --> 01:18:51,670
sau đó lần đầu tiên chúng tôi kéo một cái gì đó ra khỏi danh sách của chúng tôi kết thúc đang được null.

1011
01:18:51,670 --> 01:18:56,890
Và sau đó chúng tôi đặt hai điều trở lại, vì vậy bây giờ danh sách của chúng tôi là kích thước 2.

1012
01:18:56,890 --> 01:19:00,030
Sau đó, chúng tôi đang đi để lặp trở lại và chúng tôi chỉ cần đi để kéo,

1013
01:19:00,030 --> 01:19:04,250
hãy nói, con trỏ bên trái của nút gốc của chúng tôi.

1014
01:19:04,250 --> 01:19:07,730
Và đó sẽ chỉ tiếp tục xảy ra, chúng ta sẽ kết thúc vòng lặp qua tất cả mọi thứ.

1015
01:19:07,730 --> 01:19:11,280
>> Chú ý rằng điều này là phức tạp hơn đáng kể

1016
01:19:11,280 --> 01:19:14,160
trong các giải pháp đệ quy.

1017
01:19:14,160 --> 01:19:17,260
Và tôi đã nói nhiều lần

1018
01:19:17,260 --> 01:19:25,120
rằng các giải pháp đệ quy thường có nhiều điểm chung với các giải pháp lặp.

1019
01:19:25,120 --> 01:19:30,820
Ở đây là chính xác những gì các giải pháp đệ quy là làm.

1020
01:19:30,820 --> 01:19:36,740
Sự thay đổi duy nhất là thay vì ngầm bằng cách sử dụng ngăn xếp, ngăn xếp chương trình,

1021
01:19:36,740 --> 01:19:40,840
như cách của bạn theo dõi những nút bạn vẫn cần phải truy cập,

1022
01:19:40,840 --> 01:19:45,430
bây giờ bạn phải sử dụng một cách rõ ràng một danh sách liên kết.

1023
01:19:45,430 --> 01:19:49,070
Trong cả hai trường hợp bạn đang theo dõi những gì nút vẫn cần phải được truy cập.

1024
01:19:49,070 --> 01:19:51,790
Trong trường hợp đệ quy nó chỉ dễ dàng hơn bởi vì một chồng

1025
01:19:51,790 --> 01:19:57,100
được thực hiện cho bạn, như ngăn xếp chương trình.

1026
01:19:57,100 --> 01:19:59,550
Chú ý rằng danh sách liên kết này, nó là một ngăn xếp.

1027
01:19:59,550 --> 01:20:01,580
Bất cứ điều gì chúng ta chỉ cần đặt trên stack

1028
01:20:01,580 --> 01:20:09,960
là ngay lập tức những gì chúng ta sẽ để kéo ra khỏi ngăn xếp đến thăm tiếp theo.

1029
01:20:09,960 --> 01:20:14,380
Chúng tôi đang trên thời gian, nhưng bất kỳ câu hỏi nào?

1030
01:20:14,380 --> 01:20:23,530
[Sinh viên, không thể hiểu]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Vì vậy, nếu chúng ta có danh sách liên kết của chúng tôi,

1032
01:20:27,790 --> 01:20:30,150
hiện nay là để trỏ đến anh chàng này,

1033
01:20:30,150 --> 01:20:34,690
và bây giờ chúng tôi chỉ tiến danh sách liên kết của chúng tôi tập trung vào anh chàng này.

1034
01:20:34,690 --> 01:20:44,200
Chúng tôi đang đi qua trong danh sách liên kết trong dòng đó.

1035
01:20:44,200 --> 01:20:51,200
Và sau đó tôi nghĩ chúng ta nên miễn phí danh sách liên kết của chúng tôi và các công cụ

1036
01:20:51,200 --> 01:20:53,880
một lần trước khi quay trở lại đúng hay sai, chúng ta cần

1037
01:20:53,880 --> 01:20:57,360
lặp trên danh sách liên kết của chúng tôi và luôn luôn xuống đây, tôi đoán,

1038
01:20:57,360 --> 01:21:03,900
nếu chúng tôi hiện phải là không bằng, thêm nó, vì vậy bây giờ chúng tôi muốn giải phóng

1039
01:21:03,900 --> 01:21:09,600
hiện bởi vì, tốt, chúng tôi đã hoàn toàn quên về danh sách? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Vì vậy, đó là những gì chúng tôi muốn làm ở đây.

1041
01:21:12,880 --> 01:21:16,730
Trường hợp của con trỏ?

1042
01:21:16,730 --> 01:21:23,320
Cur là sau đó - chúng tôi muốn đến một danh sách struct * 10 bằng danh sách tiếp theo.

1043
01:21:23,320 --> 01:21:29,240
Danh sách miễn phí, danh sách = temp.

1044
01:21:29,240 --> 01:21:32,820
Và trong trường hợp nơi mà chúng tôi trả lại sự thật, chúng ta cần để lặp

1045
01:21:32,820 --> 01:21:37,050
hơn phần còn lại của danh sách liên kết của chúng tôi giải phóng những thứ.

1046
01:21:37,050 --> 01:21:39,700
Những điều tốt đẹp về các giải pháp đệ quy được giải phóng những thứ

1047
01:21:39,700 --> 01:21:44,930
chỉ có nghĩa là factorings popping ra khỏi ngăn xếp sẽ xảy ra cho bạn.

1048
01:21:44,930 --> 01:21:50,720
Vì vậy, chúng tôi đã đi từ một cái gì đó giống như 3 dòng khó khăn để suy nghĩ về mã

1049
01:21:50,720 --> 01:21:57,520
cái gì đó là đáng kể nhiều khó suy nghĩ về dòng mã.

1050
01:21:57,520 --> 01:22:00,620
Bất kỳ câu hỏi?

1051
01:22:00,620 --> 01:22:08,760
Được rồi. Chúng tôi đang tốt. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]