1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Phần 7] [Ít thoải mái]

2
00:00:02,500 --> 00:00:04,890
[Nate hardison] [Đại học Harvard]

3
00:00:04,890 --> 00:00:07,000
[Đây là CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Chào mừng bạn đến với Mục 7.

5
00:00:09,080 --> 00:00:11,330
Nhờ bão Sandy,

6
00:00:11,330 --> 00:00:13,440
thay vì có một phần bình thường trong tuần này,

7
00:00:13,440 --> 00:00:17,650
chúng tôi đang làm điều này đi bộ qua, thông qua phần câu hỏi.

8
00:00:17,650 --> 00:00:22,830
Tôi sẽ đi theo cùng với Vấn Đề Đặt 6 Đặc điểm kỹ thuật,

9
00:00:22,830 --> 00:00:25,650
và đi qua tất cả các câu hỏi trong

10
00:00:25,650 --> 00:00:27,770
Một mục các câu hỏi phần.

11
00:00:27,770 --> 00:00:30,940
Nếu có bất kỳ câu hỏi nào,

12
00:00:30,940 --> 00:00:32,960
xin vui lòng gửi những ngày CS50 bàn.

13
00:00:32,960 --> 00:00:35,480
>> Được rồi. Hãy bắt đầu.

14
00:00:35,480 --> 00:00:40,780
Ngay bây giờ tôi đang tìm kiếm tại trang 3 của Problem Set Đặc điểm kỹ thuật.

15
00:00:40,780 --> 00:00:44,110
Chúng ta sẽ bắt đầu nói về cây nhị phân

16
00:00:44,110 --> 00:00:47,850
từ những người có rất nhiều liên quan để thiết lập vấn đề trong tuần này -

17
00:00:47,850 --> 00:00:49,950
Cây Huffman mã hóa.

18
00:00:49,950 --> 00:00:55,000
Một trong những cấu trúc dữ liệu đầu tiên chúng tôi nói chuyện về CS50 là các mảng.

19
00:00:55,000 --> 00:01:00,170
Hãy nhớ rằng một mảng là một chuỗi các phần tử -

20
00:01:00,170 --> 00:01:04,019
tất cả cùng loại - được lưu trữ ngay bên cạnh nhau trong bộ nhớ.

21
00:01:04,019 --> 00:01:14,420
Nếu tôi có một mảng số nguyên mà tôi có thể vẽ bằng cách sử dụng phong cách này hộp số số nguyên -

22
00:01:14,420 --> 00:01:20,290
Hãy nói rằng tôi có 5 trong hộp đầu tiên, tôi có 7 trong lần thứ hai,

23
00:01:20,290 --> 00:01:27,760
sau đó tôi có 8, 10, và 20 trong hộp cuối cùng.

24
00:01:27,760 --> 00:01:33,000
Hãy nhớ rằng, cả hai thực sự điều tốt về mảng này

25
00:01:33,000 --> 00:01:38,800
là chúng ta đã có thời gian truy cập thường xuyên để bất kỳ yếu tố cụ thể

26
00:01:38,800 --> 00:01:40,500
 trong mảng nếu chúng ta biết chỉ số của nó.

27
00:01:40,500 --> 00:01:44,670
Ví dụ, nếu tôi muốn lấy phần tử thứ ba trong mảng -

28
00:01:44,670 --> 00:01:47,870
chỉ số 2 bằng cách sử dụng hệ thống lập chỉ mục của chúng tôi không dựa trên -

29
00:01:47,870 --> 00:01:52,220
Tôi nghĩa là chỉ cần có để làm một phép tính toán học đơn giản,

30
00:01:52,220 --> 00:01:56,170
nhảy đến vị trí trong mảng,

31
00:01:56,170 --> 00:01:57,840
kéo ra 8 được lưu trữ ở đó,

32
00:01:57,840 --> 00:01:59,260
và tôi là tốt để đi.

33
00:01:59,260 --> 00:02:03,350
>> Một trong những điều xấu về mảng này mà chúng tôi nói chuyện về

34
00:02:03,350 --> 00:02:05,010
khi chúng ta thảo luận về danh sách liên kết -

35
00:02:05,010 --> 00:02:09,120
là nếu tôi muốn chèn một phần tử vào mảng này,

36
00:02:09,120 --> 00:02:11,090
Tôi sẽ phải làm một số thay đổi xung quanh.

37
00:02:11,090 --> 00:02:12,940
Ví dụ, mảng này ngay tại đây

38
00:02:12,940 --> 00:02:16,850
theo thứ tự sắp xếp được sắp xếp theo thứ tự tăng dần

39
00:02:16,850 --> 00:02:19,440
5, sau đó 7, sau đó 8, sau đó 10, và 20 -

40
00:02:19,440 --> 00:02:23,100
nhưng nếu tôi muốn chèn số 9 vào mảng này,

41
00:02:23,100 --> 00:02:27,460
Tôi sẽ phải thay đổi một số trong những yếu tố để làm cho không gian.

42
00:02:27,460 --> 00:02:30,440
Chúng ta có thể rút ra điều này ở đây.

43
00:02:30,440 --> 00:02:35,650
Tôi sẽ phải di chuyển 5, 7, và sau đó là 8;

44
00:02:35,650 --> 00:02:38,720
tạo ra một khoảng cách nơi tôi có thể đặt 9,

45
00:02:38,720 --> 00:02:45,910
và sau đó là 10 và 20 có thể đi bên phải của 9.

46
00:02:45,910 --> 00:02:49,450
Đây là loại đau đớn bởi vì trong trường hợp xấu nhất -

47
00:02:49,450 --> 00:02:54,350
khi chúng tôi đang có để chèn hoặc ở đầu hoặc ở cuối

48
00:02:54,350 --> 00:02:56,040
của mảng, tùy thuộc vào cách chúng ta đang chuyển -

49
00:02:56,040 --> 00:02:58,850
chúng ta có thể kết thúc phải thay đổi tất cả các yếu tố

50
00:02:58,850 --> 00:03:00,750
chúng tôi hiện đang lưu trữ trong mảng.

51
00:03:00,750 --> 00:03:03,810
>> Vì vậy, khoảng cách này là những gì?

52
00:03:03,810 --> 00:03:09,260
Khoảng cách này là để đi đến phương pháp danh sách liên kết của chúng tôi, nơi

53
00:03:09,260 --> 00:03:19,820
thay vì lưu trữ các yếu tố 5, 7, 8, 10, và 20 tất cả các cạnh nhau trong bộ nhớ -

54
00:03:19,820 --> 00:03:25,630
những gì chúng ta thay vì đã được lưu trữ chúng loại ở bất cứ nơi nào chúng tôi muốn để lưu trữ chúng

55
00:03:25,630 --> 00:03:32,470
trong danh sách liên kết các nút này tôi rút ra ở đây, loại đặc biệt.

56
00:03:32,470 --> 00:03:42,060
Và sau đó chúng tôi kết nối chúng lại với nhau bằng cách sử dụng các con trỏ tiếp theo.

57
00:03:42,060 --> 00:03:44,370
Tôi có thể có một con trỏ từ 5 đến 7,

58
00:03:44,370 --> 00:03:46,420
một con trỏ từ 7 đến 8,

59
00:03:46,420 --> 00:03:47,770
một con trỏ từ 8 với 10,

60
00:03:47,770 --> 00:03:51,220
và cuối cùng, một con trỏ từ 10 đến 20,

61
00:03:51,220 --> 00:03:54,880
và sau đó một con trỏ null tại 20 chỉ ra rằng không có gì trái.

62
00:03:54,880 --> 00:03:59,690
Thương mại-off mà chúng ta có ở đây

63
00:03:59,690 --> 00:04:05,360
là bây giờ nếu chúng ta muốn chèn số 9 vào danh sách được sắp xếp của chúng tôi,

64
00:04:05,360 --> 00:04:08,270
tất cả chúng ta phải làm là tạo ra một nút mới với 9,

65
00:04:08,270 --> 00:04:12,290
dây nó lên để trỏ đến nơi thích hợp,

66
00:04:12,290 --> 00:04:20,630
và sau đó lại dây 8 chỉ với 9.

67
00:04:20,630 --> 00:04:25,660
Đó là khá nhanh, giả sử chúng ta biết chính xác nơi chúng ta muốn chèn 9.

68
00:04:25,660 --> 00:04:32,610
Tuy nhiên, thương mại-off trong trao đổi cho điều này là chúng ta đã mất thời gian truy cập thường xuyên

69
00:04:32,610 --> 00:04:36,230
bất kỳ yếu tố đặc biệt trong cấu trúc dữ liệu của chúng tôi.

70
00:04:36,230 --> 00:04:40,950
Ví dụ, nếu tôi muốn tìm các phần tử thứ tư trong danh sách liên kết này,

71
00:04:40,950 --> 00:04:43,510
Tôi sẽ phải bắt đầu vào lúc bắt đầu của danh sách

72
00:04:43,510 --> 00:04:48,930
và làm việc theo cách của mình thông qua tính node-by-nút cho đến khi tôi tìm thấy thứ tư.

73
00:04:48,930 --> 00:04:55,870
>> Để có được hiệu suất truy cập tốt hơn so với một danh sách liên kết -

74
00:04:55,870 --> 00:04:59,360
mà còn giữ lại một số những lợi ích mà chúng tôi đã có

75
00:04:59,360 --> 00:05:01,800
về thời gian chèn từ một danh sách liên kết -

76
00:05:01,800 --> 00:05:05,750
một cây nhị phân sẽ cần phải sử dụng bộ nhớ nhiều hơn một chút.

77
00:05:05,750 --> 00:05:11,460
Đặc biệt, thay vì chỉ có một con trỏ trong một nút cây nhị phân -

78
00:05:11,460 --> 00:05:13,350
như danh sách liên kết nút không -

79
00:05:13,350 --> 00:05:16,950
chúng ta sẽ thêm một con trỏ thứ hai để các nút cây nhị phân.

80
00:05:16,950 --> 00:05:19,950
Thay vì chỉ có một con trỏ trỏ tới phần tử tiếp theo,

81
00:05:19,950 --> 00:05:24,420
chúng ta sẽ có một con trỏ đến một con trái và một đứa trẻ phải.

82
00:05:24,420 --> 00:05:26,560
>> Chúng ta hãy vẽ một hình ảnh để xem những gì mà thực sự trông giống như.

83
00:05:26,560 --> 00:05:31,350
Một lần nữa, tôi sẽ sử dụng các hộp và mũi tên.

84
00:05:31,350 --> 00:05:37,150
Một nút cây nhị phân sẽ bắt đầu với một hộp đơn giản.

85
00:05:37,150 --> 00:05:40,940
Nó sẽ có một không gian cho các giá trị,

86
00:05:40,940 --> 00:05:47,280
và sau đó nó cũng sẽ có một không gian cho con trái và con phải.

87
00:05:47,280 --> 00:05:49,280
Tôi sẽ đánh giá chúng ở đây.

88
00:05:49,280 --> 00:05:57,560
Chúng tôi sẽ có con trái, và sau đó chúng ta sẽ có các con phải.

89
00:05:57,560 --> 00:05:59,920
Có nhiều cách khác nhau để làm điều này.

90
00:05:59,920 --> 00:06:02,050
Đôi khi cho không gian và tiện lợi,

91
00:06:02,050 --> 00:06:06,460
Tôi thực sự sẽ vẽ nó giống như tôi đang làm ở đây trên dưới cùng

92
00:06:06,460 --> 00:06:10,910
nơi tôi sẽ có giá trị ở đầu trang,

93
00:06:10,910 --> 00:06:14,060
và sau đó các con phải trên dưới cùng bên phải,

94
00:06:14,060 --> 00:06:16,060
và con trái phía dưới bên trái.

95
00:06:16,060 --> 00:06:20,250
Trở lại đầu trang sơ đồ này,

96
00:06:20,250 --> 00:06:22,560
chúng tôi có giá trị ở đầu,

97
00:06:22,560 --> 00:06:25,560
sau đó chúng tôi có con trỏ con trái, và sau đó chúng tôi có con trỏ bên phải con.

98
00:06:25,560 --> 00:06:30,110
>> Trong Vấn đề Set Đặc điểm kỹ thuật,

99
00:06:30,110 --> 00:06:33,110
chúng ta nói về vẽ một nút có giá trị 7,

100
00:06:33,110 --> 00:06:39,750
và sau đó một con trỏ con trái là null, và một con trỏ phải con là null.

101
00:06:39,750 --> 00:06:46,040
Chúng ta có thể viết NULL vốn trong không gian

102
00:06:46,040 --> 00:06:51,610
cả con trái và con phải, hoặc chúng tôi có thể vẽ các dấu gạch chéo chéo

103
00:06:51,610 --> 00:06:53,750
thông qua mỗi hộp để cho biết rằng đó là vô giá trị.

104
00:06:53,750 --> 00:06:57,560
Tôi sẽ làm điều đó chỉ vì đó là đơn giản.

105
00:06:57,560 --> 00:07:03,700
Những gì bạn thấy ở đây là hai cách biểu đồ cây nhị phân một nút rất đơn giản

106
00:07:03,700 --> 00:07:07,960
nơi chúng tôi có giá trị 7 và con trỏ con vô giá trị.

107
00:07:07,960 --> 00:07:15,220
>> Phần thứ hai của các cuộc đàm phán đặc điểm kỹ thuật của chúng tôi về việc làm thế nào với danh sách liên kết -

108
00:07:15,220 --> 00:07:18,270
nhớ rằng, chúng tôi chỉ có để giữ cho các yếu tố đầu tiên trong một danh sách

109
00:07:18,270 --> 00:07:20,270
nhớ toàn bộ danh sách -

110
00:07:20,270 --> 00:07:26,140
và tương tự, với một cây nhị phân, chúng tôi chỉ có để giữ cho một con trỏ cây

111
00:07:26,140 --> 00:07:31,120
để duy trì kiểm soát toàn bộ cấu trúc dữ liệu.

112
00:07:31,120 --> 00:07:36,150
Yếu tố đặc biệt của cây này được gọi là nút gốc của cây.

113
00:07:36,150 --> 00:07:43,360
Ví dụ, nếu một nút - nút này có chứa các giá trị 7

114
00:07:43,360 --> 00:07:45,500
với con trỏ null trái và quyền trẻ em -

115
00:07:45,500 --> 00:07:47,360
là giá trị duy nhất trong cây của chúng tôi,

116
00:07:47,360 --> 00:07:50,390
thì đây sẽ là nút của chúng tôi gốc.

117
00:07:50,390 --> 00:07:52,240
Đó là sự khởi đầu của cây của chúng tôi.

118
00:07:52,240 --> 00:07:58,530
Chúng ta có thể thấy điều này một chút rõ ràng hơn khi chúng ta bắt đầu thêm các nút hơn cây của chúng tôi.

119
00:07:58,530 --> 00:08:01,510
Hãy để tôi kéo lên một trang mới.

120
00:08:01,510 --> 00:08:05,000
>> Bây giờ chúng ta sẽ vẽ một cây có 7 tại gốc,

121
00:08:05,000 --> 00:08:10,920
và 3 bên trong của con trái, và bên trong 9 của các con phải.

122
00:08:10,920 --> 00:08:13,500
Một lần nữa, điều này là khá đơn giản.

123
00:08:13,500 --> 00:08:26,510
Chúng tôi đã có 7, vẽ một nút cho 3, một nút cho 9,

124
00:08:26,510 --> 00:08:32,150
và tôi sẽ thiết lập con trỏ trái con của 7 để trỏ đến các nút có chứa 3,

125
00:08:32,150 --> 00:08:37,850
và con trỏ con phải của nút chứa 7 đến nút có chứa 9.

126
00:08:37,850 --> 00:08:42,419
Bây giờ, kể từ 3 và 9 không có bất kỳ trẻ em,

127
00:08:42,419 --> 00:08:48,500
chúng ta sẽ thiết lập tất cả các con trỏ của con em mình được null.

128
00:08:48,500 --> 00:08:56,060
Ở đây, các gốc cây của chúng tôi tương ứng với các nút có chứa số 7.

129
00:08:56,060 --> 00:09:02,440
Bạn có thể thấy rằng nếu tất cả chúng ta có là một con trỏ đến nút gốc đó,

130
00:09:02,440 --> 00:09:07,330
sau đó chúng tôi có thể đi bộ qua cây của chúng tôi và truy cập cả hai nút con -

131
00:09:07,330 --> 00:09:10,630
cả 3 và 9.

132
00:09:10,630 --> 00:09:14,820
Không cần để duy trì con trỏ cho mỗi nút duy nhất trên cây.

133
00:09:14,820 --> 00:09:22,080
Được rồi. Bây giờ chúng ta sẽ thêm một nút để sơ đồ này.

134
00:09:22,080 --> 00:09:25,370
Chúng ta sẽ thêm một nút chứa 6,

135
00:09:25,370 --> 00:09:34,140
và chúng ta sẽ thêm này như là các con phải của nút chứa 3.

136
00:09:34,140 --> 00:09:41,850
Để làm điều đó, tôi sẽ để xóa con trỏ null trong 3-nút

137
00:09:41,850 --> 00:09:47,750
và dây nó lên để trỏ đến các nút chứa 6. Được rồi.

138
00:09:47,750 --> 00:09:53,800
>> Tại thời điểm này, chúng ta hãy đi qua một chút thuật ngữ.

139
00:09:53,800 --> 00:09:58,230
Để bắt đầu, lý do rằng điều này được gọi là cây nhị phân đặc biệt

140
00:09:58,230 --> 00:10:00,460
là nó có hai con trỏ con.

141
00:10:00,460 --> 00:10:06,020
Có nhiều loại cây khác có con trỏ con hơn.

142
00:10:06,020 --> 00:10:10,930
Đặc biệt, bạn đã làm một 'thử' trong 5 Set vấn đề.

143
00:10:10,930 --> 00:10:19,310
Bạn sẽ nhận thấy rằng trong thử đó, bạn đã có 27 con trỏ khác nhau cho trẻ em khác nhau -

144
00:10:19,310 --> 00:10:22,410
một cho mỗi người trong số 26 chữ cái trong bảng chữ cái tiếng Anh,

145
00:10:22,410 --> 00:10:25,410
và sau đó là 27 dấu lược

146
00:10:25,410 --> 00:10:28,900
vậy, đó là tương tự như một loại cây.

147
00:10:28,900 --> 00:10:34,070
Nhưng ở đây, kể từ nhị phân của nó, chúng tôi chỉ có hai con trỏ con.

148
00:10:34,070 --> 00:10:37,880
>> Ngoài nút gốc này mà chúng ta đã nói,

149
00:10:37,880 --> 00:10:41,470
chúng tôi cũng đã được ném xung quanh thuật ngữ này 'đứa trẻ'.

150
00:10:41,470 --> 00:10:44,470
Cho một nút là một đứa con của một nút khác có nghĩa là gì?

151
00:10:44,470 --> 00:10:54,060
Nó theo nghĩa đen có nghĩa là một nút con là một đứa con của một nút khác

152
00:10:54,060 --> 00:10:58,760
nếu đó là nút khác có một con trỏ con của nó thiết lập để trỏ đến nút đó.

153
00:10:58,760 --> 00:11:01,230
Để đưa điều này vào điều kiện cụ thể hơn,

154
00:11:01,230 --> 00:11:11,170
nếu 3 được trỏ đến bởi một số các con trỏ con của 7, 3 là một đứa trẻ 7.

155
00:11:11,170 --> 00:11:14,510
Nếu chúng ta tìm ra những gì trẻ em của 7

156
00:11:14,510 --> 00:11:18,510
tốt, chúng tôi thấy rằng 7 có một con trỏ đến 3 và một con trỏ đến 9,

157
00:11:18,510 --> 00:11:22,190
do đó, 9 và 3 là con cái của 7.

158
00:11:22,190 --> 00:11:26,650
Chín không có con vì con trỏ của nó đứa trẻ là vô giá trị,

159
00:11:26,650 --> 00:11:30,940
và 3 chỉ có một đứa con, 6.

160
00:11:30,940 --> 00:11:37,430
Sáu cũng không có con vì cả hai con trỏ của nó là null, mà chúng ta sẽ rút ra ngay bây giờ.

161
00:11:37,430 --> 00:11:45,010
>> Ngoài ra, chúng tôi cũng nói về cha mẹ của một nút cụ thể,

162
00:11:45,010 --> 00:11:51,100
và điều này là, như bạn mong muốn, ngược này mô tả con.

163
00:11:51,100 --> 00:11:58,620
Mỗi nút chỉ có một mẹ - thay vì hai như bạn mong đợi với con người.

164
00:11:58,620 --> 00:12:03,390
Ví dụ, phụ huynh của 3 là 7.

165
00:12:03,390 --> 00:12:10,800
Phụ huynh của 9 cũng là 7, và phụ huynh của 6 3. Không nhiều đến nó.

166
00:12:10,800 --> 00:12:15,720
Chúng tôi cũng có điều kiện để nói về ông bà nội, ông bà ngoại và cháu,

167
00:12:15,720 --> 00:12:18,210
và nói chung chúng ta nói về ông bà tổ tiên,

168
00:12:18,210 --> 00:12:20,960
và con cháu của một nút cụ thể.

169
00:12:20,960 --> 00:12:25,710
Tổ tiên của một nút hoặc tổ tiên, chứ không phải của một nút -

170
00:12:25,710 --> 00:12:32,730
là tất cả các nút nằm trên con đường từ gốc đến nút đó.

171
00:12:32,730 --> 00:12:36,640
Ví dụ, nếu tôi đang tìm kiếm tại nút 6,

172
00:12:36,640 --> 00:12:46,430
sau đó tổ tiên sẽ là 3 và 7.

173
00:12:46,430 --> 00:12:55,310
Tổ tiên của 9, ví dụ, nếu tôi đang tìm kiếm tại nút 9 -

174
00:12:55,310 --> 00:12:59,990
sau đó tổ tiên của 9 chỉ là 7.

175
00:12:59,990 --> 00:13:01,940
Và con cháu là chính xác ngược lại.

176
00:13:01,940 --> 00:13:05,430
Nếu tôi muốn nhìn vào tất cả các con cháu của 7,

177
00:13:05,430 --> 00:13:11,020
sau đó tôi phải nhìn vào tất cả các nút bên dưới nó.

178
00:13:11,020 --> 00:13:16,950
Vì vậy, tôi có 3, 9, và 6 tất cả như con cháu của 7.

179
00:13:16,950 --> 00:13:24,170
>> Thời hạn cuối cùng mà chúng ta sẽ nói về khái niệm này là một người anh em.

180
00:13:24,170 --> 00:13:27,980
Anh chị em ruột - loại theo các điều khoản trong gia đình -

181
00:13:27,980 --> 00:13:33,150
là các nút có cùng cấp trong cây.

182
00:13:33,150 --> 00:13:42,230
Vì vậy, 3 và 9 là anh chị em bởi vì họ có cùng cấp trong cây.

183
00:13:42,230 --> 00:13:46,190
Cả hai đều có cùng cha mẹ, 7.

184
00:13:46,190 --> 00:13:51,400
6 không có anh chị em ruột vì 9 không có con cái.

185
00:13:51,400 --> 00:13:55,540
Và 7 không có anh chị em nào bởi vì đó là gốc rễ của cây của chúng tôi,

186
00:13:55,540 --> 00:13:59,010
và có duy nhất 1 root.

187
00:13:59,010 --> 00:14:02,260
Đối với 7 có anh chị em có phải là một nút trên 7.

188
00:14:02,260 --> 00:14:07,480
Sẽ có thể là cha mẹ của 7, trong đó Trường hợp 7 sẽ không còn là gốc rễ của cây.

189
00:14:07,480 --> 00:14:10,480
Sau đó, phụ huynh mới 7 cũng sẽ phải có một đứa con,

190
00:14:10,480 --> 00:14:16,480
và rằng con sau đó sẽ là anh, chị, em ruột của 7.

191
00:14:16,480 --> 00:14:21,040
>> Được rồi. Di chuyển trên.

192
00:14:21,040 --> 00:14:24,930
Khi chúng tôi bắt đầu cuộc thảo luận của chúng ta về cây nhị phân,

193
00:14:24,930 --> 00:14:28,790
chúng tôi nói chuyện về làm thế nào chúng ta sẽ sử dụng chúng để

194
00:14:28,790 --> 00:14:32,800
đạt được một lợi thế hơn cả hai mảng và danh sách liên kết.

195
00:14:32,800 --> 00:14:37,220
Và cách chúng tôi sẽ làm điều đó với khách sạn đặt hàng.

196
00:14:37,220 --> 00:14:41,080
Chúng ta nói rằng một cây nhị phân là ra lệnh, theo các đặc điểm kỹ thuật,

197
00:14:41,080 --> 00:14:45,740
nếu cho mỗi nút trong cây của chúng tôi, tất cả các hậu duệ của nó ở bên trái -

198
00:14:45,740 --> 00:14:48,670
con trái và tất cả các con cháu của con trái -

199
00:14:48,670 --> 00:14:54,510
có giá trị thấp hơn, và tất cả các nút trên bên phải -

200
00:14:54,510 --> 00:14:57,770
các con phải và tất cả các con cháu của các con phải -

201
00:14:57,770 --> 00:15:02,800
có các nút lớn hơn giá trị của nút hiện tại mà chúng tôi đang tìm kiếm.

202
00:15:02,800 --> 00:15:07,850
Chỉ cần cho đơn giản, chúng ta sẽ giả định rằng không có bất kỳ các nút trùng lặp trong cây của chúng tôi.

203
00:15:07,850 --> 00:15:11,180
Ví dụ, trong cây này chúng tôi sẽ không để đối phó với các trường hợp

204
00:15:11,180 --> 00:15:13,680
nơi chúng tôi có giá trị 7 ở gốc

205
00:15:13,680 --> 00:15:16,720
 và sau đó chúng tôi cũng có giá trị 7 ở những nơi khác trong cây.

206
00:15:16,720 --> 00:15:24,390
Trong trường hợp này, bạn sẽ nhận thấy rằng cây này thực sự là ra lệnh.

207
00:15:24,390 --> 00:15:26,510
Chúng tôi có giá trị 7 rễ cây.

208
00:15:26,510 --> 00:15:29,720
Tất cả mọi thứ để bên trái của 7 -

209
00:15:29,720 --> 00:15:35,310
nếu tôi lùi lại tất cả các nhãn hiệu nhỏ ở đây -

210
00:15:35,310 --> 00:15:40,450
tất cả mọi thứ để bên trái của 7 - 3 và 6 -

211
00:15:40,450 --> 00:15:49,410
những giá trị được cả hai ít hơn 7, và tất cả mọi thứ bên phải - mà chỉ là nay 9 -

212
00:15:49,410 --> 00:15:53,450
là lớn hơn 7.

213
00:15:53,450 --> 00:15:58,650
>> Đây không phải là cái cây chỉ đặt hàng có chứa các giá trị,

214
00:15:58,650 --> 00:16:03,120
nhưng chúng ta hãy vẽ một vài trong số họ.

215
00:16:03,120 --> 00:16:05,030
Có thật sự là một bó toàn bộ cách chúng tôi có thể làm điều này.

216
00:16:05,030 --> 00:16:09,380
Tôi sẽ sử dụng một cách viết tắt chỉ để giữ cho mọi thứ đơn giản, nơi

217
00:16:09,380 --> 00:16:11,520
chứ không phải vẽ ra toàn bộ hộp và mũi tên -

218
00:16:11,520 --> 00:16:14,220
Tôi chỉ cần đi để vẽ các con số và thêm vào mũi tên kết nối chúng.

219
00:16:14,220 --> 00:16:22,920
Để bắt đầu, chúng tôi sẽ chỉ viết gốc cây của chúng tôi một lần nữa, nơi chúng tôi đã có 7, và sau đó một 3,

220
00:16:22,920 --> 00:16:25,590
và sau đó 3 chỉ ở bên phải với 6,

221
00:16:25,590 --> 00:16:30,890
và 7 có một đứa con bên phải là 9.

222
00:16:30,890 --> 00:16:33,860
Được rồi. Một cách khác mà chúng ta có thể viết cây này là gì?

223
00:16:33,860 --> 00:16:38,800
Thay vì phải 3 là con trái của 7,

224
00:16:38,800 --> 00:16:41,360
chúng ta cũng có thể có 6 là con trái của 7

225
00:16:41,360 --> 00:16:44,470
và sau đó 3 là con trái của 6.

226
00:16:44,470 --> 00:16:48,520
Điều đó sẽ trông giống như cây này ở đây, nơi tôi đã có 7,

227
00:16:48,520 --> 00:16:57,860
sau đó 6, sau đó 3, và 9 bên phải.

228
00:16:57,860 --> 00:17:01,490
Chúng tôi cũng không cần phải có 7 là nút gốc của chúng tôi.

229
00:17:01,490 --> 00:17:03,860
Chúng tôi cũng có thể có 6 nút gốc của chúng tôi.

230
00:17:03,860 --> 00:17:06,470
Những gì mà sẽ trông như thế nào?

231
00:17:06,470 --> 00:17:09,230
Nếu chúng ta sẽ phải duy trì tài sản ra lệnh,

232
00:17:09,230 --> 00:17:12,970
tất cả mọi thứ để bên trái của 6 có thể ít hơn.

233
00:17:12,970 --> 00:17:16,540
Có người chỉ có một khả năng, và đó là 3.

234
00:17:16,540 --> 00:17:19,869
Nhưng sau đó là các con phải của 6, chúng tôi có hai khả năng.

235
00:17:19,869 --> 00:17:25,380
Đầu tiên, chúng ta có thể có số 7 và sau đó 9,

236
00:17:25,380 --> 00:17:28,850
hoặc chúng ta có thể rút ra nó giống như tôi về để làm ở đây -

237
00:17:28,850 --> 00:17:34,790
nơi chúng tôi có 9 như các con phải của 6,

238
00:17:34,790 --> 00:17:39,050
và sau đó 7 là con trái của 9.

239
00:17:39,050 --> 00:17:44,240
>> Bây giờ, 7 và 6 không phải là giá trị chỉ có thể cho người chủ.

240
00:17:44,240 --> 00:17:50,200
Chúng tôi cũng có thể có 3 gốc.

241
00:17:50,200 --> 00:17:52,240
Điều gì sẽ xảy ra nếu 3 là ở gốc?

242
00:17:52,240 --> 00:17:54,390
Ở đây, những thứ có được một chút thú vị.

243
00:17:54,390 --> 00:17:58,440
Ba không có bất kỳ giá trị ít hơn,

244
00:17:58,440 --> 00:18:02,070
sao cho toàn bộ bên trái của cây là chỉ cần đi được null.

245
00:18:02,070 --> 00:18:03,230
Không có được bất cứ điều gì ở đó.

246
00:18:03,230 --> 00:18:07,220
Bên phải, chúng ta có thể liệt kê những thứ theo thứ tự tăng dần.

247
00:18:07,220 --> 00:18:15,530
Chúng tôi có thể có 3, sau đó 6, sau đó 7, sau đó 9.

248
00:18:15,530 --> 00:18:26,710
Hoặc, chúng ta có thể làm 3, sau đó 6, sau đó 9, sau đó 7.

249
00:18:26,710 --> 00:18:35,020
Hoặc, chúng ta có thể làm 3, sau đó 7, sau đó 6, sau đó 9.

250
00:18:35,020 --> 00:18:40,950
Hoặc, 3, 7 - thực sự không có, chúng tôi không thể làm một 7 nữa.

251
00:18:40,950 --> 00:18:43,330
Đó là một điều chúng tôi có.

252
00:18:43,330 --> 00:18:54,710
Chúng ta có thể làm 9, và sau đó từ 9, chúng tôi có thể làm 6 và sau đó 7.

253
00:18:54,710 --> 00:19:06,980
Hoặc, chúng ta có thể làm 3, sau đó 9, sau đó 7, và sau đó 6.

254
00:19:06,980 --> 00:19:12,490
>> Một trong những điều thu hút sự chú ý của bạn ở đây là

255
00:19:12,490 --> 00:19:14,510
rằng những cây có một chút lạ nhìn.

256
00:19:14,510 --> 00:19:17,840
Đặc biệt, nếu chúng ta nhìn vào 4 cây ở bên phải -

257
00:19:17,840 --> 00:19:20,930
Tôi sẽ vòng tròn, ở đây -

258
00:19:20,930 --> 00:19:28,410
những cây này trông gần như chính xác giống như một danh sách liên kết.

259
00:19:28,410 --> 00:19:32,670
Mỗi nút chỉ có một con,

260
00:19:32,670 --> 00:19:38,950
và vì vậy chúng tôi không có bất kỳ cấu trúc này giống như cây mà chúng ta thấy, ví dụ,

261
00:19:38,950 --> 00:19:44,720
 trong cây duy nhất ở đây trên dưới cùng bên trái.

262
00:19:44,720 --> 00:19:52,490
Những cây này đang thực sự được gọi là thoái hóa cây nhị phân,

263
00:19:52,490 --> 00:19:54,170
và chúng ta sẽ nói về những nhiều hơn trong tương lai -

264
00:19:54,170 --> 00:19:56,730
đặc biệt là nếu bạn đi vào để có các khóa học khoa học máy tính khác.

265
00:19:56,730 --> 00:19:59,670
Những cây này thoái hóa.

266
00:19:59,670 --> 00:20:03,780
Chúng không phải là rất hữu ích bởi vì, thực tế, cấu trúc này vay chính nó

267
00:20:03,780 --> 00:20:08,060
 để tra cứu thời gian tương tự như của một danh sách liên kết.

268
00:20:08,060 --> 00:20:13,050
Chúng tôi không nhận được để tận dụng lợi thế của bộ nhớ thêm con trỏ này thêm

269
00:20:13,050 --> 00:20:18,840
vì cấu trúc của chúng tôi là theo cách này.

270
00:20:18,840 --> 00:20:24,700
Thay vì đi vào và rút ra cây nhị phân có 9 ở gốc,

271
00:20:24,700 --> 00:20:27,220
đó là trường hợp cuối cùng mà chúng ta sẽ có,

272
00:20:27,220 --> 00:20:32,380
Thay vào đó, chúng tôi, vào thời điểm này, sẽ nói một chút về thuật ngữ này khác

273
00:20:32,380 --> 00:20:36,150
mà chúng tôi sử dụng khi nói về cây, được gọi là chiều cao.

274
00:20:36,150 --> 00:20:45,460
>> Chiều cao của cây là khoảng cách từ gốc đến nút xa nhất,

275
00:20:45,460 --> 00:20:48,370
hay đúng hơn là số lượng hoa bia mà bạn sẽ phải thực hiện để

276
00:20:48,370 --> 00:20:53,750
bắt đầu từ gốc và sau đó kết thúc tại nút xa nhất trong cây.

277
00:20:53,750 --> 00:20:57,330
Nếu chúng ta nhìn tại một số các cây mà chúng tôi đã rút ra ngay tại đây,

278
00:20:57,330 --> 00:21:07,870
chúng ta có thể thấy rằng nếu chúng ta lấy cây này ở góc trên bên trái và chúng tôi bắt đầu tại 3,

279
00:21:07,870 --> 00:21:14,510
thì chúng ta phải làm cho 1 hop để có được với 6, hop thứ hai để có được đến 7,

280
00:21:14,510 --> 00:21:20,560
và một bước nhảy thứ ba để có được có tới 9.

281
00:21:20,560 --> 00:21:26,120
Vì vậy, chiều cao của cây này là 3.

282
00:21:26,120 --> 00:21:30,640
Chúng tôi có thể làm các bài tập tương tự cho các cây nêu với màu xanh lá cây này,

283
00:21:30,640 --> 00:21:40,100
và chúng ta thấy rằng chiều cao của tất cả những cây này cũng là thực sự 3.

284
00:21:40,100 --> 00:21:45,230
Đó là một phần của những gì làm cho họ thoái hóa -

285
00:21:45,230 --> 00:21:53,750
chiều cao của họ chỉ là một trong ít hơn số lượng các nút trong cây.

286
00:21:53,750 --> 00:21:58,400
Nếu chúng ta nhìn vào cây này khác bao vây với màu đỏ, mặt khác,

287
00:21:58,400 --> 00:22:03,920
chúng ta thấy rằng các nút lá xa nhất là 6 và 9 -

288
00:22:03,920 --> 00:22:06,940
lá là những nút không có con.

289
00:22:06,940 --> 00:22:11,760
Vì vậy, để có được từ nút gốc hoặc 6 hoặc 9,

290
00:22:11,760 --> 00:22:17,840
chúng ta phải làm một hop để có được đến 7 và sau đó hop một lần thứ hai để có được có tới 9,

291
00:22:17,840 --> 00:22:21,240
và tương tự, chỉ có một bước nhảy thứ hai từ 7 với 6.

292
00:22:21,240 --> 00:22:29,080
Vì vậy, chiều cao của cây này ở đây là chỉ có 2.

293
00:22:29,080 --> 00:22:35,330
Bạn có thể quay trở lại và làm điều đó cho tất cả các loại cây khác mà chúng tôi đã thảo luận

294
00:22:35,330 --> 00:22:37,380
bắt đầu với 7 và 6,

295
00:22:37,480 --> 00:22:42,500
và bạn sẽ thấy rằng chiều cao của tất cả những cây này cũng có 2.

296
00:22:42,500 --> 00:22:46,320
>> Lý do chúng tôi đã nói về ra lệnh cho cây nhị phân

297
00:22:46,320 --> 00:22:50,250
và lý do tại sao họ đang mát mẻ là bởi vì bạn có thể tìm kiếm thông qua chúng trong

298
00:22:50,250 --> 00:22:53,810
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.

299
00:22:53,810 --> 00:22:58,720
Đây là nơi mà chúng ta nói về nhận được rằng thời gian tra cứu cải tiến

300
00:22:58,720 --> 00:23:02,730
trên danh sách liên kết đơn giản.

301
00:23:02,730 --> 00:23:05,010
Với một danh sách liên kết - nếu bạn muốn tìm thấy một yếu tố cụ thể -

302
00:23:05,010 --> 00:23:07,470
bạn đang ở tốt nhất sẽ làm một số loại tìm kiếm tuyến tính

303
00:23:07,470 --> 00:23:10,920
nơi bạn bắt đầu vào lúc bắt đầu của một danh sách và một-by-hop

304
00:23:10,920 --> 00:23:12,620
một nút bằng một nút -

305
00:23:12,620 --> 00:23:16,060
thông qua toàn bộ danh sách cho đến khi bạn tìm thấy bất cứ điều gì bạn đang tìm kiếm.

306
00:23:16,060 --> 00:23:19,440
Trong khi đó, nếu bạn có một cây nhị phân được lưu trữ trong định dạng tốt đẹp này,

307
00:23:19,440 --> 00:23:23,300
bạn thực sự có thể nhận được nhiều hơn một tìm kiếm nhị phân

308
00:23:23,300 --> 00:23:25,160
nơi bạn chia và chinh phục

309
00:23:25,160 --> 00:23:29,490
và tìm kiếm thông qua một nửa thích hợp của cây ở mỗi bước.

310
00:23:29,490 --> 00:23:32,840
Chúng ta hãy xem làm thế nào mà.

311
00:23:32,840 --> 00:23:38,850
>> Nếu chúng ta có - một lần nữa, sẽ trở lại cây ban đầu của chúng tôi -

312
00:23:38,850 --> 00:23:46,710
chúng tôi bắt đầu vào lúc 7, chúng tôi có 3 bên trái, 9 bên phải,

313
00:23:46,710 --> 00:23:51,740
và dưới 3 thì chúng tôi có 6.

314
00:23:51,740 --> 00:24:01,880
Nếu chúng ta muốn tìm kiếm số 6 trong cây này, chúng tôi muốn bắt đầu ở gốc.

315
00:24:01,880 --> 00:24:08,910
Chúng tôi sẽ so sánh các giá trị mà chúng ta đang tìm kiếm, nói 6,

316
00:24:08,910 --> 00:24:12,320
với giá trị được lưu trữ trong các nút mà chúng ta đang nhìn vào, 7,

317
00:24:12,320 --> 00:24:21,200
thấy rằng 6 thực sự là ít hơn 7, vì vậy chúng tôi muốn di chuyển sang bên trái.

318
00:24:21,200 --> 00:24:25,530
Nếu giá trị của 6 đã lớn hơn 7, chúng tôi sẽ thay vì di chuyển về bên phải.

319
00:24:25,530 --> 00:24:29,770
Vì chúng ta biết rằng do cấu trúc của cây nhị phân ra lệnh cho chúng tôi -

320
00:24:29,770 --> 00:24:33,910
tất cả các giá trị nhỏ hơn 7 được sẽ được lưu trữ bên trái của 7

321
00:24:33,910 --> 00:24:40,520
không cần phải bận tâm tìm kiếm thông qua phía bên phải của cây.

322
00:24:40,520 --> 00:24:43,780
Một khi chúng tôi di chuyển sang bên trái và chúng tôi tại các nút có chứa 3,

323
00:24:43,780 --> 00:24:48,110
chúng ta có thể làm điều đó so sánh cùng một lần nữa chúng ta so sánh 3 và 6.

324
00:24:48,110 --> 00:24:52,430
Và chúng ta thấy rằng trong khi 6 - giá trị mà chúng ta đang tìm kiếm - lớn hơn 3,

325
00:24:52,430 --> 00:24:58,580
chúng ta có thể đi về phía bên phải của nút chứa 3.

326
00:24:58,580 --> 00:25:02,670
Không có bên trái ở đây, vì vậy chúng ta có thể bỏ qua mà.

327
00:25:02,670 --> 00:25:06,510
Nhưng chúng tôi chỉ biết rằng bởi vì chúng tôi đang tìm kiếm bản thân cây,

328
00:25:06,510 --> 00:25:08,660
và chúng tôi có thể thấy rằng cây không có con.

329
00:25:08,660 --> 00:25:13,640
>> Nó cũng khá dễ dàng để tìm kiếm 6 trong cây này nếu chúng ta đang làm việc đó mình như con người,

330
00:25:13,640 --> 00:25:16,890
nhưng chúng ta hãy theo dõi quá trình này máy móc như một máy tính sẽ làm gì

331
00:25:16,890 --> 00:25:18,620
để thực sự hiểu các thuật toán.

332
00:25:18,620 --> 00:25:26,200
Tại thời điểm này, chúng tôi hiện đang tìm kiếm tại một nút có 6,

333
00:25:26,200 --> 00:25:29,180
và chúng tôi đang tìm kiếm giá trị 6,

334
00:25:29,180 --> 00:25:31,740
như vậy, quả thật vậy, chúng tôi đã tìm thấy các nút thích hợp.

335
00:25:31,740 --> 00:25:35,070
Chúng tôi đã tìm thấy giá trị 6 cây của chúng tôi, và chúng tôi có thể ngừng tìm kiếm của chúng tôi.

336
00:25:35,070 --> 00:25:37,330
Tại thời điểm này, tùy thuộc vào những gì đang xảy ra,

337
00:25:37,330 --> 00:25:41,870
chúng ta có thể nói, có, chúng tôi đã tìm thấy giá trị 6, nó tồn tại trong cây của chúng tôi.

338
00:25:41,870 --> 00:25:47,640
Hoặc, nếu chúng tôi đang lập kế hoạch để chèn một nút hoặc làm điều gì đó, chúng ta có thể làm điều đó vào thời điểm này.

339
00:25:47,640 --> 00:25:53,010
>> Hãy làm tra cứu một vài chi tiết chỉ để xem cách làm việc này.

340
00:25:53,010 --> 00:25:59,390
Chúng ta hãy nhìn vào những gì sẽ xảy ra nếu chúng ta cố gắng và tìm kiếm các giá trị 10.

341
00:25:59,390 --> 00:26:02,970
Nếu chúng ta để tìm kiếm giá trị 10, chúng ta sẽ bắt đầu từ gốc.

342
00:26:02,970 --> 00:26:07,070
Chúng tôi thấy rằng 10 là lớn hơn 7, vì vậy chúng tôi muốn di chuyển sang phải.

343
00:26:07,070 --> 00:26:13,640
Chúng tôi nhận được có tới 9 và so sánh 9 với 10 và thấy rằng 9 thực sự là ít hơn 10.

344
00:26:13,640 --> 00:26:16,210
Vì vậy, một lần nữa, chúng tôi sẽ cố gắng để di chuyển sang bên phải.

345
00:26:16,210 --> 00:26:20,350
Tuy nhiên, vào thời điểm này, chúng tôi nhận thấy rằng chúng ta đang ở một nút null.

346
00:26:20,350 --> 00:26:23,080
Không có gì ở đó. Không có gì nơi 10 nên.

347
00:26:23,080 --> 00:26:29,360
Đây là nơi mà chúng tôi có thể báo cáo thất bại - có thực sự là không 10 trong cây.

348
00:26:29,360 --> 00:26:35,420
Và cuối cùng, chúng ta hãy đi qua các trường hợp, nơi chúng tôi đang cố gắng để tìm kiếm 1 trong cây.

349
00:26:35,420 --> 00:26:38,790
Điều này tương tự như những gì sẽ xảy ra nếu chúng ta nhìn lên 10, ngoại trừ thay vì đi bên phải,

350
00:26:38,790 --> 00:26:41,260
chúng ta sẽ đi bên trái.

351
00:26:41,260 --> 00:26:46,170
Chúng tôi bắt đầu tại 7 và thấy rằng 1 là ít hơn 7, do đó, chúng tôi di chuyển sang bên trái.

352
00:26:46,170 --> 00:26:51,750
Chúng tôi nhận được cho 3 và thấy rằng 1 là ít hơn 3, vì vậy một lần nữa, chúng tôi cố gắng để di chuyển sang bên trái.

353
00:26:51,750 --> 00:26:59,080
Tại thời điểm này chúng tôi có một nút null, vì vậy một lần nữa chúng tôi có thể báo cáo thất bại.

354
00:26:59,080 --> 00:27:10,260
>> Nếu bạn muốn tìm hiểu thêm về cây nhị phân,

355
00:27:10,260 --> 00:27:14,420
có một bó toàn bộ các vấn đề thú vị mà bạn có thể làm gì với chúng.

356
00:27:14,420 --> 00:27:19,450
Tôi đề nghị thực hành vẽ các sơ đồ này một-by-

357
00:27:19,450 --> 00:27:21,910
và thông qua tất cả các bước khác nhau sau đây,

358
00:27:21,910 --> 00:27:25,060
vì điều này sẽ đến trong siêu tiện dụng

359
00:27:25,060 --> 00:27:27,480
không chỉ khi bạn đang thực hiện bộ vấn đề mã hóa Huffman

360
00:27:27,480 --> 00:27:29,390
mà còn trong các khóa học trong tương lai -

361
00:27:29,390 --> 00:27:32,220
chỉ học tập làm thế nào để rút ra những cấu trúc dữ liệu và suy nghĩ thông qua các vấn đề

362
00:27:32,220 --> 00:27:38,000
với bút và giấy hoặc, trong trường hợp này iPad, và bút stylus.

363
00:27:38,000 --> 00:27:41,000
>> Tại thời điểm này mặc dù, chúng ta sẽ chuyển sang làm một số thực hành mã hóa

364
00:27:41,000 --> 00:27:44,870
và thực sự chơi với những cây nhị phân và xem.

365
00:27:44,870 --> 00:27:52,150
Tôi sẽ chuyển về cho máy tính của tôi.

366
00:27:52,150 --> 00:27:58,480
Đối với phần này của phần, thay vì sử dụng CS50 Run hoặc CS50 Spaces,

367
00:27:58,480 --> 00:28:01,500
Tôi sẽ sử dụng thiết bị.

368
00:28:01,500 --> 00:28:04,950
>> Sau đây cùng với các đặc điểm kỹ thuật Set vấn đề,

369
00:28:04,950 --> 00:28:07,740
Tôi thấy rằng tôi là nghĩa vụ phải mở các thiết bị,

370
00:28:07,740 --> 00:28:11,020
đi vào thư mục Dropbox của tôi, tạo ra một thư mục có tên là Mục 7,

371
00:28:11,020 --> 00:28:15,730
và sau đó tạo ra một tập tin gọi binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Ở đây chúng tôi đi. Tôi đã có thiết bị đã được mở.

373
00:28:22,050 --> 00:28:25,910
Tôi sẽ kéo lên một thiết bị đầu cuối.

374
00:28:25,910 --> 00:28:38,250
Tôi sẽ đi vào thư mục Dropbox, làm cho một thư mục gọi là section7,

375
00:28:38,250 --> 00:28:42,230
và thấy nó hoàn toàn trống rỗng.

376
00:28:42,230 --> 00:28:48,860
Bây giờ tôi sẽ để mở ra binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Được rồi. Ở đây chúng tôi đi - tập tin rỗng.

378
00:28:51,750 --> 00:28:54,330
>> Hãy để quay trở lại với các đặc điểm kỹ thuật.

379
00:28:54,330 --> 00:28:59,850
Đặc điểm kỹ thuật yêu cầu để tạo ra một định nghĩa kiểu mới

380
00:28:59,850 --> 00:29:03,080
cho một nút cây nhị phân chứa các giá trị int -

381
00:29:03,080 --> 00:29:07,110
giống như các giá trị mà chúng ta rút ra trong biểu đồ của chúng tôi trước khi.

382
00:29:07,110 --> 00:29:11,740
Chúng ta sẽ sử dụng boilerplate này typedef mà chúng tôi đã thực hiện ngay tại đây

383
00:29:11,740 --> 00:29:14,420
mà bạn nên nhận ra từ 5 Set Vấn đề -

384
00:29:14,420 --> 00:29:19,190
nếu bạn đã làm theo cách bảng băm của chương trình chinh phục speller.

385
00:29:19,190 --> 00:29:22,540
Bạn cũng nên nhận ra nó từ phần cuối cùng của tuần

386
00:29:22,540 --> 00:29:23,890
nơi mà chúng tôi nói chuyện về danh sách liên kết.

387
00:29:23,890 --> 00:29:27,870
Chúng tôi đã có này typedef của một nút struct,

388
00:29:27,870 --> 00:29:34,430
và chúng tôi đã cho nút này struct tên của nút struct trước

389
00:29:34,430 --> 00:29:39,350
để chúng ta có thể đề cập đến nó kể từ khi chúng tôi sẽ muốn có con trỏ nút struct

390
00:29:39,350 --> 00:29:45,740
như là một phần của cấu trúc của chúng tôi, nhưng sau đó chúng tôi đã bị bao vây này -

391
00:29:45,740 --> 00:29:47,700
hay đúng hơn, kèm theo này - trong một typedef

392
00:29:47,700 --> 00:29:54,600
do đó, sau này trong mã, chúng ta có thể tham khảo cấu trúc này như là một nút thay vì một nút struct.

393
00:29:54,600 --> 00:30:03,120
>> Điều này là có được rất giống với định nghĩa danh sách liên kết đơn lẻ mà chúng ta nhìn thấy tuần trước.

394
00:30:03,120 --> 00:30:20,070
Để làm điều này, chúng ta hãy bắt đầu bằng cách viết ra các boilerplate.

395
00:30:20,070 --> 00:30:23,840
Chúng ta biết rằng chúng ta phải có một giá trị số nguyên,

396
00:30:23,840 --> 00:30:32,170
do đó, chúng tôi sẽ đưa vào giá trị int, và sau đó thay vì chỉ là một con trỏ trỏ tới phần tử tiếp theo -

397
00:30:32,170 --> 00:30:33,970
như chúng ta đã làm với các danh sách liên kết đơn lẻ -

398
00:30:33,970 --> 00:30:38,110
chúng ta sẽ có con trỏ con trái và bên phải.

399
00:30:38,110 --> 00:30:42,880
Đó là khá đơn giản quá - struct nút con bên trái;

400
00:30:42,880 --> 00:30:51,190
và struct node * quyền trẻ em; Cool.

401
00:30:51,190 --> 00:30:54,740
Điều đó có vẻ như một sự khởi đầu khá tốt.

402
00:30:54,740 --> 00:30:58,530
Hãy để quay trở lại với các đặc điểm kỹ thuật.

403
00:30:58,530 --> 00:31:05,030
>> Bây giờ chúng ta cần phải khai báo một biến node * toàn cầu cho gốc rễ của một cái cây.

404
00:31:05,030 --> 00:31:10,590
Chúng ta sẽ làm cho toàn cầu giống như chúng ta đã thực hiện con trỏ đầu tiên trong danh sách liên kết của chúng tôi cũng toàn cầu.

405
00:31:10,590 --> 00:31:12,690
Điều này là để các chức năng mà chúng tôi viết

406
00:31:12,690 --> 00:31:16,180
chúng tôi không cần phải đi qua xung quanh gốc này -

407
00:31:16,180 --> 00:31:19,620
mặc dù chúng ta sẽ thấy rằng nếu bạn muốn để viết các chức năng đệ quy,

408
00:31:19,620 --> 00:31:22,830
nó có thể là tốt hơn để không vượt qua nó xung quanh như một toàn cầu ở nơi đầu tiên

409
00:31:22,830 --> 00:31:28,090
và thay vào đó khởi tạo nó tại địa phương trong chức năng chính của bạn.

410
00:31:28,090 --> 00:31:31,960
Tuy nhiên, chúng tôi sẽ làm nó trên toàn cầu để bắt đầu.

411
00:31:31,960 --> 00:31:39,920
Một lần nữa, chúng tôi sẽ cung cấp cho một vài không gian, và tôi sẽ tuyên bố một gốc * nút.

412
00:31:39,920 --> 00:31:46,770
Chỉ để chắc chắn rằng tôi không để lại điều này chưa được khởi tạo, tôi sẽ để thiết lập nó bằng giá trị null.

413
00:31:46,770 --> 00:31:52,210
Bây giờ, trong các chức năng chính - mà chúng ta sẽ viết thực sự nhanh chóng ngay tại đây -

414
00:31:52,210 --> 00:32:00,450
int main (int argc, char * argv []) -

415
00:32:00,450 --> 00:32:10,640
và tôi sẽ bắt đầu khai báo mảng argv của tôi như là const chỉ vì vậy mà tôi biết

416
00:32:10,640 --> 00:32:14,550
những đối số lập luận rằng tôi có lẽ không muốn thay đổi.

417
00:32:14,550 --> 00:32:18,390
Nếu tôi muốn thay đổi chúng tôi có lẽ nên được bản sao của chúng.

418
00:32:18,390 --> 00:32:21,740
Bạn sẽ thấy điều này rất nhiều trong mã.

419
00:32:21,740 --> 00:32:25,440
Đó là một trong hai cách. Đó là tốt để nó như bỏ qua const nếu bạn muốn.

420
00:32:25,440 --> 00:32:28,630
Tôi thường đặt nó trong chỉ để cho tôi nhắc nhở bản thân mình

421
00:32:28,630 --> 00:32:33,650
 rằng tôi có lẽ không muốn để chỉnh sửa những đối số.

422
00:32:33,650 --> 00:32:39,240
>> Như mọi khi, tôi sẽ bao gồm dòng return 0 ở cuối chính.

423
00:32:39,240 --> 00:32:45,730
Ở đây, tôi sẽ khởi tạo nút gốc của tôi.

424
00:32:45,730 --> 00:32:48,900
Vì nó đứng ngay bây giờ, tôi đã có một con trỏ được thiết lập để null,

425
00:32:48,900 --> 00:32:52,970
do đó, nó chỉ ở không có gì.

426
00:32:52,970 --> 00:32:57,480
Để thực sự bắt đầu xây dựng các nút,

427
00:32:57,480 --> 00:32:59,250
Lần đầu tiên tôi cần phải cấp phát bộ nhớ cho nó.

428
00:32:59,250 --> 00:33:05,910
Tôi sẽ làm điều đó bằng cách làm cho bộ nhớ trên heap sử dụng malloc.

429
00:33:05,910 --> 00:33:10,660
Tôi sẽ thiết lập gốc bằng kết quả của malloc,

430
00:33:10,660 --> 00:33:19,550
và tôi sẽ sử dụng toán tử sizeof để tính toán kích thước của một nút.

431
00:33:19,550 --> 00:33:24,990
Lý do mà tôi sử dụng sizeof nút như trái ngược với, nói,

432
00:33:24,990 --> 00:33:37,020
làm một cái gì đó như thế này - malloc (4 + 4 +4) hay malloc 12 -

433
00:33:37,020 --> 00:33:40,820
là vì tôi muốn mã của tôi để được như tương thích càng tốt.

434
00:33:40,820 --> 00:33:44,540
Tôi muốn để có thể lấy file này c, biên dịch nó trên thiết bị,

435
00:33:44,540 --> 00:33:48,820
và sau đó biên dịch nó trên 64-bit máy Mac của tôi -

436
00:33:48,820 --> 00:33:52,040
hoặc trên một kiến ​​trúc hoàn toàn khác nhau -

437
00:33:52,040 --> 00:33:54,640
và tôi muốn tất cả điều này làm việc như nhau.

438
00:33:54,640 --> 00:33:59,510
>> Nếu tôi là làm cho các giả định về kích thước của các biến

439
00:33:59,510 --> 00:34:02,070
kích thước của một int hoặc kích thước của một con trỏ -

440
00:34:02,070 --> 00:34:06,070
sau đó tôi cũng làm cho các giả định về các loại kiến ​​trúc

441
00:34:06,070 --> 00:34:10,440
mã của tôi có thể biên dịch thành công khi chạy.

442
00:34:10,440 --> 00:34:15,030
Luôn luôn sử dụng sizeof như trái ngược với tự tổng hợp các lĩnh vực struct.

443
00:34:15,030 --> 00:34:20,500
Một lý do khác là có cũng có thể là đệm mà trình biên dịch đặt vào cấu trúc.

444
00:34:20,500 --> 00:34:26,570
Thậm chí chỉ cần tổng hợp các lĩnh vực cá nhân không phải là một cái gì đó mà bạn thường muốn làm,

445
00:34:26,570 --> 00:34:30,340
như vậy, xóa dòng đó.

446
00:34:30,340 --> 00:34:33,090
Bây giờ, để thực sự khởi tạo nút gốc này,

447
00:34:33,090 --> 00:34:36,489
Tôi sẽ phải cắm vào giá trị cho mỗi lĩnh vực khác nhau của nó.

448
00:34:36,489 --> 00:34:41,400
Ví dụ, giá trị tôi biết tôi muốn khởi tạo đến 7,

449
00:34:41,400 --> 00:34:46,920
và bây giờ tôi sẽ đặt con trái được null

450
00:34:46,920 --> 00:34:55,820
và các con phải cũng được null. Great!

451
00:34:55,820 --> 00:35:02,670
Chúng tôi đã làm điều đó một phần của spec.

452
00:35:02,670 --> 00:35:07,390
>> Các đặc điểm kỹ thuật xuống ở dưới cùng của trang 3 yêu cầu tôi để tạo ra thêm ba nút -

453
00:35:07,390 --> 00:35:10,600
có chứa 3, chứa 6, và một với 9 -

454
00:35:10,600 --> 00:35:14,210
và sau đó dây chúng vì vậy nó trông giống hệt như sơ đồ cây của chúng tôi

455
00:35:14,210 --> 00:35:17,120
rằng chúng tôi đã nói về trước đó.

456
00:35:17,120 --> 00:35:20,450
Hãy làm điều đó khá nhanh chóng.

457
00:35:20,450 --> 00:35:26,270
Bạn sẽ thấy thực sự nhanh chóng rằng tôi sẽ để bắt đầu viết một loạt các mã trùng lặp.

458
00:35:26,270 --> 00:35:32,100
Tôi sẽ tạo ra một nút * và tôi sẽ gọi nó ba.

459
00:35:32,100 --> 00:35:36,000
Tôi sẽ thiết lập nó bằng malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Tôi sẽ thiết lập ba-> giá trị = 3.

461
00:35:41,070 --> 00:35:54,780
Ba -> left_child = NULL; ba> phải _child = NULL; là tốt.

462
00:35:54,780 --> 00:36:01,150
Điều đó có vẻ khá tương tự như khởi tạo thư mục gốc, và đó là chính xác những gì

463
00:36:01,150 --> 00:36:05,760
Tôi sẽ phải làm gì nếu tôi bắt đầu khởi tạo là 6 và 9 cũng.

464
00:36:05,760 --> 00:36:20,720
Tôi sẽ làm điều đó thực sự nhanh chóng ở đây - trên thực tế, tôi sẽ làm việc sao chép và dán ít,

465
00:36:20,720 --> 00:36:46,140
và làm cho chắc chắn rằng I - ổn.

466
00:36:46,470 --> 00:37:09,900
 Bây giờ, tôi đã nhận nó sao chép và tôi có thể đi trước và thiết lập này bằng 6.

467
00:37:09,900 --> 00:37:14,670
Bạn có thể thấy rằng điều này mất một thời gian và không phải là siêu hiệu quả.

468
00:37:14,670 --> 00:37:22,610
Trong một chút ít, chúng tôi sẽ viết một chức năng mà sẽ làm điều này cho chúng tôi.

469
00:37:22,610 --> 00:37:32,890
Tôi muốn thay thế này với một 9, thay thế với một 6.

470
00:37:32,890 --> 00:37:37,360
>> Bây giờ chúng ta đã có tất cả các nút của chúng tôi được tạo ra và khởi tạo.

471
00:37:37,360 --> 00:37:41,200
Chúng tôi đã có gốc rễ của chúng tôi thiết lập bằng 7, hoặc có chứa các giá trị 7,

472
00:37:41,200 --> 00:37:46,510
nút của chúng tôi có 3 nút của chúng tôi chứa 6, và nút của chúng tôi có chứa 9.

473
00:37:46,510 --> 00:37:50,390
Tại thời điểm này, tất cả chúng ta phải làm là dây điện tất cả mọi thứ.

474
00:37:50,390 --> 00:37:53,020
Lý do tôi khởi tạo tất cả các con trỏ để null là chỉ để cho tôi đảm bảo rằng

475
00:37:53,020 --> 00:37:56,260
Tôi không có bất kỳ con trỏ uninitialized trong đó do tai nạn.

476
00:37:56,260 --> 00:38:02,290
Và cũng kể từ thời điểm này, tôi chỉ có thực sự kết nối các nút với nhau -

477
00:38:02,290 --> 00:38:04,750
những người mà họ đang thực sự kết nối với - Tôi không phải đi qua và làm cho

478
00:38:04,750 --> 00:38:08,240
chắc chắn rằng tất cả các giá trị tương ứng là ở các vị trí thích hợp.

479
00:38:08,240 --> 00:38:15,630
>> Bắt đầu từ gốc rễ, tôi biết rằng con trái của gốc là 3.

480
00:38:15,630 --> 00:38:21,250
Tôi biết rằng con phải của gốc là 9.

481
00:38:21,250 --> 00:38:24,880
Sau đó, chỉ có một đứa trẻ mà tôi đã để lại phải lo lắng về

482
00:38:24,880 --> 00:38:39,080
là con bên phải 3, là 6.

483
00:38:39,080 --> 00:38:44,670
Tại thời điểm này, tất cả trông khá tốt.

484
00:38:44,670 --> 00:38:54,210
Chúng tôi sẽ xóa một số của những dòng này.

485
00:38:54,210 --> 00:38:59,540
Bây giờ tất cả mọi thứ có vẻ khá tốt.

486
00:38:59,540 --> 00:39:04,240
Hãy quay trở lại đặc điểm kỹ thuật của chúng tôi và xem những gì chúng ta phải làm gì tiếp theo.

487
00:39:04,240 --> 00:39:07,610
>> Tại thời điểm này, chúng ta phải viết một chức năng được gọi là 'chứa'

488
00:39:07,610 --> 00:39:14,150
với một nguyên mẫu của 'chứa bool (int giá trị).

489
00:39:14,150 --> 00:39:17,060
Và điều này có chức năng là để trở về đúng

490
00:39:17,060 --> 00:39:21,200
 nếu cây được trỏ đến bởi biến gốc toàn cầu của chúng tôi

491
00:39:21,200 --> 00:39:26,950
 chứa giá trị được thông qua vào các chức năng và sai khác.

492
00:39:26,950 --> 00:39:29,000
Hãy cho đi trước và làm điều đó.

493
00:39:29,000 --> 00:39:35,380
Điều này là có được chính xác như tra cứu mà chúng tôi đã làm bằng tay trên iPad chỉ là một chút trước.

494
00:39:35,380 --> 00:39:40,130
Hãy thu nhỏ lại một chút và di chuyển lên.

495
00:39:40,130 --> 00:39:43,130
Chúng ta sẽ đặt chức năng này ngay trên chức năng chính của chúng tôi

496
00:39:43,130 --> 00:39:48,990
do đó chúng tôi không phải làm bất kỳ loại công nghệ tạo mẫu.

497
00:39:48,990 --> 00:39:55,960
Vì vậy, bool chứa (int giá trị).

498
00:39:55,960 --> 00:40:00,330
Hiện chúng tôi đi. Có khai báo boilerplate của chúng tôi.

499
00:40:00,330 --> 00:40:02,900
Chỉ để chắc chắn rằng điều này sẽ biên dịch,

500
00:40:02,900 --> 00:40:06,820
Tôi sẽ đi trước và chỉ cần đặt nó bằng trả về false.

501
00:40:06,820 --> 00:40:09,980
Hiện tại chức năng này sẽ không làm bất cứ điều gì và luôn luôn báo cáo rằng

502
00:40:09,980 --> 00:40:14,010
giá trị mà chúng tôi đang tìm kiếm không phải là trong cây.

503
00:40:14,010 --> 00:40:16,280
>> Tại thời điểm này, nó có thể là một ý tưởng tốt -

504
00:40:16,280 --> 00:40:19,600
kể từ khi chúng tôi đã viết một bó toàn bộ các mã và chúng tôi thậm chí đã cố gắng thử nghiệm nó chưa -

505
00:40:19,600 --> 00:40:22,590
để đảm bảo rằng tất cả các biên dịch.

506
00:40:22,590 --> 00:40:27,460
Có một vài điều mà chúng ta phải làm gì để đảm bảo rằng điều này sẽ thực sự biên dịch.

507
00:40:27,460 --> 00:40:33,530
Trước tiên, hãy xem nếu chúng ta đã sử dụng bất kỳ chức năng trong bất kỳ thư viện mà chúng tôi đã chưa có.

508
00:40:33,530 --> 00:40:37,940
Các chức năng chúng tôi đã sử dụng cho đến nay là malloc,

509
00:40:37,940 --> 00:40:43,310
và sau đó chúng tôi cũng đã được sử dụng loại - loại không tiêu chuẩn được gọi là 'bool' -

510
00:40:43,310 --> 00:40:45,750
được bao gồm trong các tập tin tiêu đề chuẩn bool.

511
00:40:45,750 --> 00:40:53,250
Chúng tôi chắc chắn muốn bao gồm bool.h tiêu chuẩn cho các loại bool,

512
00:40:53,250 --> 00:40:59,230
và chúng tôi cũng muốn # bao gồm lib.h tiêu chuẩn cho các thư viện tiêu chuẩn

513
00:40:59,230 --> 00:41:03,530
bao gồm malloc, và miễn phí, và tất cả những điều đó.

514
00:41:03,530 --> 00:41:08,660
Vì vậy, thu nhỏ, chúng ta sẽ bỏ thuốc lá.

515
00:41:08,660 --> 00:41:14,190
Hãy thử và làm cho chắc chắn rằng điều này thực sự đã làm biên dịch.

516
00:41:14,190 --> 00:41:18,150
Chúng tôi thấy rằng nó không có gì, vì vậy chúng tôi đang đi đúng hướng.

517
00:41:18,150 --> 00:41:22,990
>> Hãy để mở binary_tree.c một lần nữa.

518
00:41:22,990 --> 00:41:34,530
Nó biên dịch. Chúng ta hãy đi xuống và làm cho chắc chắn rằng chúng ta chèn thêm một số cuộc gọi đến chức năng Chứa của chúng tôi -

519
00:41:34,530 --> 00:41:40,130
chỉ để chắc chắn rằng đó là tất cả tốt và tốt.

520
00:41:40,130 --> 00:41:43,170
Ví dụ, khi chúng tôi đã làm một số tra cứu trong cây của chúng tôi trước đó,

521
00:41:43,170 --> 00:41:48,500
chúng tôi đã cố gắng để tìm kiếm 6 giá trị, 10, và 1, và chúng tôi biết rằng 6 trong cây,

522
00:41:48,500 --> 00:41:52,220
10 là không trong cây, và 1 lần trong cây.

523
00:41:52,220 --> 00:41:57,230
Hãy sử dụng những cuộc gọi mẫu như một cách để tìm ra hay không

524
00:41:57,230 --> 00:41:59,880
chức năng Chứa của chúng tôi đang làm việc.

525
00:41:59,880 --> 00:42:05,210
Để làm điều đó, tôi sẽ sử dụng chức năng printf,

526
00:42:05,210 --> 00:42:10,280
và chúng tôi sẽ để in ra các kết quả của các cuộc gọi đến có chứa.

527
00:42:10,280 --> 00:42:13,280
Tôi sẽ đặt trong một chuỗi chứa (% d) = vì

528
00:42:13,280 --> 00:42:20,470
 chúng ta sẽ cắm vào giá trị mà chúng tôi đang đi tìm,

529
00:42:20,470 --> 00:42:27,130
=% s \ n "và sử dụng như là một chuỗi định dạng của chúng tôi.

530
00:42:27,130 --> 00:42:30,720
Chúng tôi chỉ cần đi để thấy - theo nghĩa đen in ra trên màn hình -

531
00:42:30,720 --> 00:42:32,060
những gì trông giống như một cuộc gọi chức năng.

532
00:42:32,060 --> 00:42:33,580
Điều này là không thực sự các cuộc gọi chức năng.

533
00:42:33,580 --> 00:42:36,760
 Đây chỉ là một chuỗi được thiết kế để trông giống như một cuộc gọi chức năng.

534
00:42:36,760 --> 00:42:41,140
>> Bây giờ, chúng ta sẽ cắm vào các giá trị.

535
00:42:41,140 --> 00:42:43,580
Chúng tôi sẽ cố gắng chứa ngày 6,

536
00:42:43,580 --> 00:42:48,340
và sau đó những gì chúng tôi đang làm ở đây là sử dụng mà nhà điều hành ternary.

537
00:42:48,340 --> 00:42:56,340
Hãy xem - có 6 - vì vậy, bây giờ tôi đã có 6 và nếu có 6 là sự thật,

538
00:42:56,340 --> 00:43:01,850
chuỗi đó chúng ta sẽ gửi ký tự định dạng% s

539
00:43:01,850 --> 00:43:04,850
là có được chuỗi "true".

540
00:43:04,850 --> 00:43:07,690
Hãy di chuyển trên một chút.

541
00:43:07,690 --> 00:43:16,210
Nếu không, chúng tôi muốn gửi chuỗi "false" nếu nó bao gồm 6 trả về false.

542
00:43:16,210 --> 00:43:19,730
Đây là một chút ngu ngốc nhìn, nhưng tôi con số tôi cũng có thể minh họa

543
00:43:19,730 --> 00:43:23,780
nhà điều hành ternary vẻ như kể từ khi chúng tôi đã không nhìn thấy nó cho một lúc.

544
00:43:23,780 --> 00:43:27,670
Đây sẽ là một, đẹp, tiện dụng cách nào để tìm ra nếu chức năng Chứa của chúng tôi đang làm việc.

545
00:43:27,670 --> 00:43:30,040
Tôi sẽ di chuyển trở lại bên trái,

546
00:43:30,040 --> 00:43:39,900
và tôi sẽ để sao chép và dán dòng này một vài lần.

547
00:43:39,900 --> 00:43:44,910
Nó đã thay đổi một số các giá trị xung quanh,

548
00:43:44,910 --> 00:43:59,380
vì vậy đây là có được 1, và điều này sẽ là 10.

549
00:43:59,380 --> 00:44:02,480
>> Tại thời điểm này chúng tôi đã có một chức năng Chứa tốt đẹp.

550
00:44:02,480 --> 00:44:06,080
Chúng tôi đã có một số bài kiểm tra, và chúng tôi sẽ xem nếu điều này tất cả các công trình.

551
00:44:06,080 --> 00:44:08,120
Tại thời điểm này, chúng tôi đã viết một số mã hơn.

552
00:44:08,120 --> 00:44:13,160
Thời gian bỏ ra và đảm bảo rằng tất cả mọi thứ vẫn biên dịch.

553
00:44:13,160 --> 00:44:20,360
Bỏ ra, và bây giờ chúng ta hãy cố gắng làm cho cây nhị phân một lần nữa.

554
00:44:20,360 --> 00:44:22,260
Vâng, có vẻ như chúng tôi đã có một lỗi,

555
00:44:22,260 --> 00:44:26,930
và chúng tôi đã bị này một cách rõ ràng tuyên bố chức năng thư viện printf.

556
00:44:26,930 --> 00:44:39,350
Có vẻ như chúng ta cần đi vào và # bao gồm standardio.h.

557
00:44:39,350 --> 00:44:45,350
Và với điều đó, tất cả mọi thứ cần biên dịch. Chúng tôi tất cả đều tốt.

558
00:44:45,350 --> 00:44:50,420
Bây giờ chúng ta hãy thử chạy cây nhị phân và xem những gì sẽ xảy ra.

559
00:44:50,420 --> 00:44:53,520
Ở đây chúng ta, / binary_tree,

560
00:44:53,520 --> 00:44:55,190
và chúng ta thấy rằng, như chúng ta mong đợi -

561
00:44:55,190 --> 00:44:56,910
bởi vì chúng tôi đã không thực hiện có được nêu ra,

562
00:44:56,910 --> 00:44:59,800
hay đúng hơn, chúng tôi đã chỉ cần đặt lại sai

563
00:44:59,800 --> 00:45:03,300
chúng tôi thấy rằng nó chỉ trở về sai cho tất cả chúng,

564
00:45:03,300 --> 00:45:06,180
do đó tất cả đều làm việc cho hầu hết các phần khá tốt.

565
00:45:06,180 --> 00:45:11,860
>> Chúng ta hãy trở lại và thực sự thực hiện có vào thời điểm này.

566
00:45:11,860 --> 00:45:17,490
Tôi sẽ di chuyển xuống, phóng to, và -

567
00:45:17,490 --> 00:45:22,330
hãy nhớ rằng, các thuật toán mà chúng tôi sử dụng là chúng tôi bắt đầu tại nút gốc

568
00:45:22,330 --> 00:45:28,010
và sau đó tại mỗi nút mà chúng ta gặp phải, chúng tôi làm một so sánh,

569
00:45:28,010 --> 00:45:32,380
và trên cơ sở đó so sánh chúng tôi di chuyển con trái hoặc các con phải.

570
00:45:32,380 --> 00:45:39,670
Điều này sẽ trông rất giống với mã tìm kiếm nhị phân mà chúng tôi đã viết trước đó trong thời gian.

571
00:45:39,670 --> 00:45:47,810
Khi chúng tôi bắt đầu, chúng tôi biết rằng chúng tôi muốn để giữ cho các nút hiện tại

572
00:45:47,810 --> 00:45:54,050
mà chúng tôi đang tìm kiếm, và các nút hiện tại sẽ được khởi tạo nút gốc.

573
00:45:54,050 --> 00:45:56,260
Và bây giờ, chúng ta sẽ tiếp tục đi qua cây,

574
00:45:56,260 --> 00:45:58,140
và nhớ rằng điều kiện của chúng tôi dừng lại -

575
00:45:58,140 --> 00:46:01,870
 khi chúng tôi thực sự làm việc thông qua các ví dụ bằng tay -

576
00:46:01,870 --> 00:46:03,960
là khi chúng tôi gặp phải một nút null,

577
00:46:03,960 --> 00:46:05,480
không phải khi chúng ta nhìn một đứa trẻ null,

578
00:46:05,480 --> 00:46:09,620
mà là khi chúng ta thực sự di chuyển với một nút trong cây

579
00:46:09,620 --> 00:46:12,640
và thấy rằng chúng ta đang ở một nút null.

580
00:46:12,640 --> 00:46:20,720
Chúng ta sẽ lặp đi lặp lại cho đến khi hiện không bằng vô giá trị.

581
00:46:20,720 --> 00:46:22,920
Và chúng tôi sẽ làm gì?

582
00:46:22,920 --> 00:46:31,610
Chúng tôi sẽ kiểm tra nếu (hiện -> giá trị == giá trị),

583
00:46:31,610 --> 00:46:35,160
sau đó chúng tôi biết rằng chúng tôi đã thực sự tìm thấy các nút mà chúng tôi đang tìm kiếm.

584
00:46:35,160 --> 00:46:40,450
Vì vậy, ở đây, chúng ta có thể trở lại đúng sự thật.

585
00:46:40,450 --> 00:46:49,830
Nếu không, chúng tôi muốn thấy có hoặc không có giá trị nhỏ hơn giá trị.

586
00:46:49,830 --> 00:46:53,850
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,

587
00:46:53,850 --> 00:46:57,280
chúng ta sẽ di chuyển sang phải.

588
00:46:57,280 --> 00:47:10,600
Vì vậy, hiện = hiện -> right_child; và nếu không, chúng ta sẽ di chuyển sang bên trái.

589
00:47:10,600 --> 00:47:17,480
hiện = hiện -> left_child; Khá đơn giản.

590
00:47:17,480 --> 00:47:22,830
>> Bạn có thể nhận ra những vòng lặp đó trông rất giống với điều này từ

591
00:47:22,830 --> 00:47:27,580
tìm kiếm nhị phân trước đó trong thời hạn, trừ trường hợp sau đó chúng tôi đã được giao dịch thấp, giữa, và cao.

592
00:47:27,580 --> 00:47:30,000
Ở đây, chúng tôi chỉ cần có để nhìn vào một giá trị hiện tại,

593
00:47:30,000 --> 00:47:31,930
vì vậy nó là tốt đẹp và đơn giản.

594
00:47:31,930 --> 00:47:34,960
Hãy chắc chắn rằng mã này đang làm việc.

595
00:47:34,960 --> 00:47:42,780
Trước tiên, hãy chắc chắn rằng nó biên dịch. Hình như nó.

596
00:47:42,780 --> 00:47:47,920
Chúng ta hãy thử chạy nó.

597
00:47:47,920 --> 00:47:50,160
Và quả thực, nó in ra tất cả mọi thứ mà chúng ta mong đợi.

598
00:47:50,160 --> 00:47:54,320
Nó tìm thấy 6 trong cây, không tìm thấy 10 bởi vì 10 không có trong cây,

599
00:47:54,320 --> 00:47:57,740
và không tìm thấy 1 hoặc vì 1 cũng không phải trong cây.

600
00:47:57,740 --> 00:48:01,420
Mát công cụ.

601
00:48:01,420 --> 00:48:04,470
>> Được rồi. Hãy quay trở lại đặc điểm kỹ thuật của chúng tôi và xem những gì tiếp theo.

602
00:48:04,470 --> 00:48:07,990
Bây giờ, nó muốn để thêm các nút thêm một số cây của chúng tôi.

603
00:48:07,990 --> 00:48:11,690
Nó muốn để thêm 5, 2, và 8, và làm cho chắc chắn rằng chúng tôi có chứa mã

604
00:48:11,690 --> 00:48:13,570
vẫn hoạt động như mong đợi.

605
00:48:13,570 --> 00:48:14,900
Hãy làm điều đó.

606
00:48:14,900 --> 00:48:19,430
Tại thời điểm này, thay vì làm điều đó bản sao gây phiền nhiễu và dán một lần nữa,

607
00:48:19,430 --> 00:48:23,770
chúng ta hãy viết một chức năng để thực sự tạo ra một nút.

608
00:48:23,770 --> 00:48:27,740
Nếu chúng ta di chuyển xuống tất cả các con đường chính, chúng tôi thấy rằng chúng tôi đã làm điều này

609
00:48:27,740 --> 00:48:31,210
mã rất giống nhau hơn và hơn nữa mỗi khi chúng tôi muốn tạo ra một nút.

610
00:48:31,210 --> 00:48:39,540
>> Hãy viết một chức năng đó sẽ thực sự xây dựng một nút cho chúng ta và trả lại nó.

611
00:48:39,540 --> 00:48:41,960
Tôi sẽ để gọi nó build_node.

612
00:48:41,960 --> 00:48:45,130
Tôi sẽ xây dựng một nút với một giá trị cụ thể.

613
00:48:45,130 --> 00:48:51,040
Phóng ở đây.

614
00:48:51,040 --> 00:48:56,600
Điều đầu tiên tôi sẽ làm là thực sự tạo ra không gian cho các nút trên heap.

615
00:48:56,600 --> 00:49:05,400
Vì vậy, node * n = malloc (sizeof (node)); n -> giá trị = giá trị;

616
00:49:05,400 --> 00:49:14,960
và sau đó ở đây, tôi chỉ cần đi để khởi tạo tất cả các trường là các giá trị thích hợp.

617
00:49:14,960 --> 00:49:22,500
Và cuối cùng, chúng tôi sẽ trả lại nút của chúng tôi.

618
00:49:22,500 --> 00:49:28,690
Được rồi. Một điều cần lưu ý rằng chức năng này ngay tại đây

619
00:49:28,690 --> 00:49:34,320
để trả về một con trỏ trỏ tới bộ nhớ đã được heap-phân bổ.

620
00:49:34,320 --> 00:49:38,880
Có gì đẹp về việc này là nút này -

621
00:49:38,880 --> 00:49:42,420
chúng ta phải khai báo nó trên heap bởi vì nếu chúng tôi tuyên bố nó trên stack

622
00:49:42,420 --> 00:49:45,050
chúng tôi sẽ không thể làm điều đó trong chức năng này như thế này.

623
00:49:45,050 --> 00:49:47,690
Rằng bộ nhớ sẽ đi ra khỏi phạm vi

624
00:49:47,690 --> 00:49:51,590
và không có giá trị nếu chúng ta đã cố gắng để truy cập nó sau này.

625
00:49:51,590 --> 00:49:53,500
Vì chúng ta đang tuyên bố đống phân bổ bộ nhớ,

626
00:49:53,500 --> 00:49:55,830
chúng ta sẽ phải chăm sóc giải phóng nó sau này

627
00:49:55,830 --> 00:49:58,530
chương trình của chúng tôi không bị rò rỉ bất kỳ bộ nhớ.

628
00:49:58,530 --> 00:50:01,270
Chúng tôi đã punting cho mọi thứ khác trong các mã

629
00:50:01,270 --> 00:50:02,880
để đơn giản vào thời điểm đó,

630
00:50:02,880 --> 00:50:05,610
nhưng nếu bạn đã bao giờ viết một chức năng mà trông như thế này

631
00:50:05,610 --> 00:50:10,370
nơi mà bạn đã có một số gọi nó là một malloc hoặc realloc bên trong -

632
00:50:10,370 --> 00:50:14,330
bạn muốn làm cho chắc chắn rằng bạn đặt một số loại bình luận ở đây nói rằng,

633
00:50:14,330 --> 00:50:29,970
hey, bạn biết đấy, trả về một nút đống phân bổ được khởi tạo với giá trị thông qua trong.

634
00:50:29,970 --> 00:50:33,600
Và sau đó bạn muốn đảm bảo rằng bạn đặt trong một số loại lưu ý nói rằng

635
00:50:33,600 --> 00:50:41,720
người gọi phải giải phóng bộ nhớ quay trở lại.

636
00:50:41,720 --> 00:50:45,450
Bằng cách đó, nếu ai đó bao giờ đi và sử dụng chức năng đó,

637
00:50:45,450 --> 00:50:48,150
họ biết rằng bất cứ điều gì họ nhận được từ chức năng đó

638
00:50:48,150 --> 00:50:50,870
tại một số điểm cần phải được giải phóng.

639
00:50:50,870 --> 00:50:53,940
>> Giả sử tất cả là tốt và tốt,

640
00:50:53,940 --> 00:51:02,300
chúng ta có thể đi xuống vào mã của chúng tôi và thay thế tất cả những dòng này ngay tại đây

641
00:51:02,300 --> 00:51:05,410
với các cuộc gọi chức năng nút xây dựng của chúng tôi.

642
00:51:05,410 --> 00:51:08,170
Hãy làm điều đó thực sự nhanh chóng.

643
00:51:08,170 --> 00:51:15,840
Một phần rằng chúng tôi không thể thay thế phần này xuống đây

644
00:51:15,840 --> 00:51:18,520
ở dưới cùng mà chúng tôi thực sự dây lên các nút để trỏ đến nhau,

645
00:51:18,520 --> 00:51:21,030
bởi vì chúng ta không thể làm chức năng của chúng tôi.

646
00:51:21,030 --> 00:51:37,400
Tuy nhiên, chúng ta hãy làm root = build_node (7); node * ba = build_node (3);

647
00:51:37,400 --> 00:51:47,980
node * 6 = build_node (6); node * 9 = build_node (9);

648
00:51:47,980 --> 00:51:52,590
Và bây giờ, chúng tôi cũng muốn để thêm các nút cho

649
00:51:52,590 --> 00:52:03,530
node * 5 = build_node (5); nút * 8 = build_node (8);

650
00:52:03,530 --> 00:52:09,760
và các nút khác là gì? Hãy xem ở đây. Chúng tôi cũng muốn thêm một 2 -

651
00:52:09,760 --> 00:52:20,280
nút * 2 = build_node (2);

652
00:52:20,280 --> 00:52:26,850
Được rồi. Tại thời điểm này, chúng tôi biết rằng chúng tôi đã có 7, 3, 9, và 6

653
00:52:26,850 --> 00:52:30,320
tất cả các dây lên một cách thích hợp, nhưng những gì về 5, 8, và 2?

654
00:52:30,320 --> 00:52:33,550
Để giữ cho tất cả mọi thứ theo thứ tự thích hợp,

655
00:52:33,550 --> 00:52:39,230
chúng ta biết rằng con phải của 3 là 6.

656
00:52:39,230 --> 00:52:40,890
Vì vậy, nếu chúng ta sẽ thêm 5,

657
00:52:40,890 --> 00:52:46,670
5 cũng thuộc về phía bên phải của cây trong đó có 3 là gốc rễ,

658
00:52:46,670 --> 00:52:50,440
như vậy 5 thuộc là con trái của 6.

659
00:52:50,440 --> 00:52:58,650
Chúng tôi có thể làm điều này bằng cách nói rằng, sáu -> left_child = 5;

660
00:52:58,650 --> 00:53:10,790
và sau đó là 8 thuộc là con trái của 9, vì vậy 9 -> left_child = 8;

661
00:53:10,790 --> 00:53:22,190
và sau đó 2 là con trái của 3, do đó, chúng ta có thể làm điều đó ở đây - ngươi -> left_child = 2;

662
00:53:22,190 --> 00:53:27,730
Nếu bạn không hoàn toàn theo cùng với điều đó, tôi đề nghị bạn vẽ nó ra cho mình.

663
00:53:27,730 --> 00:53:35,660
>> Được rồi. Hãy tiết kiệm này. Hãy đi ra ngoài và chắc chắn rằng nó biên dịch,

664
00:53:35,660 --> 00:53:40,760
và sau đó chúng ta có thể thêm vào Chứa các cuộc gọi của chúng tôi.

665
00:53:40,760 --> 00:53:44,120
Hình như tất cả mọi thứ vẫn còn biên dịch.

666
00:53:44,120 --> 00:53:51,790
Chúng ta hãy đi vào và thêm vào một số chứa các cuộc gọi.

667
00:53:51,790 --> 00:53:59,640
Một lần nữa, tôi sẽ làm một chút sao chép và dán.

668
00:53:59,640 --> 00:54:15,860
Bây giờ hãy tìm kiếm 5, 8, và 2. Được rồi.

669
00:54:15,860 --> 00:54:28,330
Hãy chắc chắn rằng điều này vẫn còn tất cả sẽ tốt. Great! Lưu và bỏ thuốc lá.

670
00:54:28,330 --> 00:54:33,220
Bây giờ chúng ta hãy làm biên dịch, và bây giờ hãy chạy.

671
00:54:33,220 --> 00:54:37,540
Từ những kết quả, có vẻ như tất cả mọi thứ đang làm việc chỉ tốt đẹp và tốt.

672
00:54:37,540 --> 00:54:41,780
Great! Vì vậy, bây giờ chúng tôi đã có Chứa của chúng tôi chức năng bằng văn bản.

673
00:54:41,780 --> 00:54:46,160
Hãy di chuyển và bắt đầu làm việc về việc làm thế nào để chèn nút vào cây

674
00:54:46,160 --> 00:54:50,000
vì, như chúng tôi đang làm nó ngay bây giờ, mọi thứ không phải là rất đẹp.

675
00:54:50,000 --> 00:54:52,280
>> Nếu chúng ta quay trở lại các đặc điểm kỹ thuật,

676
00:54:52,280 --> 00:55:00,540
nó yêu cầu chúng tôi viết một chức năng được gọi là chèn - một lần nữa, trả lại một bool

677
00:55:00,540 --> 00:55:04,400
hay không, chúng tôi thực sự có thể chèn các nút vào cây -

678
00:55:04,400 --> 00:55:07,710
và sau đó giá trị để chèn vào cây được quy định như

679
00:55:07,710 --> 00:55:11,060
Lý lẽ duy nhất chức năng chèn của chúng tôi.

680
00:55:11,060 --> 00:55:18,180
Chúng tôi sẽ trở lại đúng sự thật nếu chúng ta thực sự có thể chèn giá trị có chứa nút vào cây,

681
00:55:18,180 --> 00:55:20,930
điều đó có nghĩa rằng chúng ta, một, đã có đủ bộ nhớ,

682
00:55:20,930 --> 00:55:24,840
và sau đó hai, rằng nút không đã tồn tại trong cây từ -

683
00:55:24,840 --> 00:55:32,170
hãy nhớ rằng, chúng tôi sẽ không có giá trị nhân bản trong cây, chỉ để làm cho mọi thứ đơn giản.

684
00:55:32,170 --> 00:55:35,590
Được rồi. Sao để mã.

685
00:55:35,590 --> 00:55:44,240
Mở nó lên. Phóng to một chút, sau đó di chuyển xuống.

686
00:55:44,240 --> 00:55:47,220
Hãy đặt các chức năng chèn ngay bên trên có chứa.

687
00:55:47,220 --> 00:55:56,360
Một lần nữa, nó sẽ được gọi là bool chèn (int giá trị).

688
00:55:56,360 --> 00:56:01,840
Cung cấp cho nó không gian nhiều hơn một chút, và sau đó, như một mặc định,

689
00:56:01,840 --> 00:56:08,870
chúng ta hãy đặt return false vào cuối.

690
00:56:08,870 --> 00:56:22,620
Bây giờ xuống phía dưới, chúng ta hãy đi trước và thay vào đó tự xây dựng các nút

691
00:56:22,620 --> 00:56:27,900
trong chính bản thân mình và hệ thống dây điện để trỏ đến nhau như chúng tôi đang làm,

692
00:56:27,900 --> 00:56:30,600
chúng tôi sẽ dựa vào chức năng chèn của chúng tôi để làm điều đó.

693
00:56:30,600 --> 00:56:35,510
Chúng tôi sẽ không dựa vào chức năng chèn của chúng tôi để xây dựng toàn bộ cây từ đầu chỉ được nêu ra,

694
00:56:35,510 --> 00:56:39,970
mà đúng hơn là chúng tôi sẽ nhận được thoát khỏi những dòng này - we'll nhận xét ra những dòng này -

695
00:56:39,970 --> 00:56:43,430
xây dựng 5 nút, 8, và 2.

696
00:56:43,430 --> 00:56:55,740
Và thay vào đó, chúng ta sẽ chèn các cuộc gọi chức năng chèn của chúng tôi

697
00:56:55,740 --> 00:57:01,280
để chắc chắn rằng đó thực sự hoạt động.

698
00:57:01,280 --> 00:57:05,840
Ở đây chúng tôi đi.

699
00:57:05,840 --> 00:57:09,300
>> Bây giờ chúng ta đã nhận xét ra những dòng này.

700
00:57:09,300 --> 00:57:13,700
Chúng tôi chỉ có 7, 3, 9, và 6 trong cây của chúng tôi vào thời điểm này.

701
00:57:13,700 --> 00:57:18,870
Để chắc chắn rằng điều này là tất cả làm việc,

702
00:57:18,870 --> 00:57:25,050
chúng ta có thể thu nhỏ, làm cho cây nhị phân của chúng tôi,

703
00:57:25,050 --> 00:57:30,750
chạy nó, và chúng ta có thể thấy có nói với chúng tôi rằng chúng tôi hoàn toàn đúng -

704
00:57:30,750 --> 00:57:33,110
5, 8, và 2 là không còn trong cây.

705
00:57:33,110 --> 00:57:37,960
Trở lại vào mã này,

706
00:57:37,960 --> 00:57:41,070
và làm thế nào chúng ta sẽ để chèn?

707
00:57:41,070 --> 00:57:46,290
Hãy nhớ những gì chúng ta đã làm khi chúng ta đã thực sự chèn 5, 8, và 2 trước đây.

708
00:57:46,290 --> 00:57:50,100
Chúng tôi chơi trò chơi Plinko nơi chúng tôi bắt đầu ở gốc,

709
00:57:50,100 --> 00:57:52,780
đã đi xuống một cây một

710
00:57:52,780 --> 00:57:54,980
cho đến khi chúng tôi tìm thấy khoảng cách thích hợp,

711
00:57:54,980 --> 00:57:57,570
và sau đó chúng tôi có dây trong nút tại vị trí thích hợp.

712
00:57:57,570 --> 00:57:59,480
Chúng ta sẽ làm điều tương tự.

713
00:57:59,480 --> 00:58:04,070
Điều này về cơ bản là giống như viết mã mà chúng tôi sử dụng trong có chứa chức năng

714
00:58:04,070 --> 00:58:05,910
để tìm ra nơi mà các nút nên,

715
00:58:05,910 --> 00:58:10,560
và sau đó chúng tôi chỉ cần đi để chèn các nút phải có.

716
00:58:10,560 --> 00:58:17,000
Hãy bắt đầu làm điều đó.

717
00:58:17,000 --> 00:58:24,200
>> Vì vậy, chúng tôi có một nút * hiện = root, chúng tôi chỉ đi theo có chứa mã

718
00:58:24,200 --> 00:58:26,850
cho đến khi chúng ta thấy rằng nó không hoàn toàn làm việc cho chúng tôi.

719
00:58:26,850 --> 00:58:32,390
Chúng ta sẽ phải đi qua cây trong khi các yếu tố hiện không phải là null,

720
00:58:32,390 --> 00:58:45,280
và nếu chúng ta thấy đó là hiện giá trị bằng với giá trị mà chúng tôi đang cố gắng để chèn

721
00:58:45,280 --> 00:58:49,600
, điều này là một trong các trường hợp trong đó chúng ta có thể không thực sự chèn các nút

722
00:58:49,600 --> 00:58:52,730
vào các cây bởi vì điều này có nghĩa là chúng ta có một giá trị trùng lặp.

723
00:58:52,730 --> 00:58:59,010
Ở đây chúng ta đang thực sự sẽ trả về false.

724
00:58:59,010 --> 00:59:08,440
Bây giờ, nếu người nào khác hiện của giá trị thấp hơn giá trị,

725
00:59:08,440 --> 00:59:10,930
bây giờ chúng ta biết rằng chúng tôi di chuyển ở bên phải

726
00:59:10,930 --> 00:59:17,190
 bởi vì giá trị thuộc về nửa bên phải của cây hiện.

727
00:59:17,190 --> 00:59:30,110
Nếu không, chúng ta sẽ di chuyển sang bên trái.

728
00:59:30,110 --> 00:59:37,980
Đó là cơ bản Chứa của chúng tôi hoạt động phải có.

729
00:59:37,980 --> 00:59:41,820
>> Tại thời điểm này, khi chúng tôi đã hoàn thành trong vòng lặp trong khi,

730
00:59:41,820 --> 00:59:47,350
con trỏ hiện của chúng tôi sẽ được trỏ đến null

731
00:59:47,350 --> 00:59:51,540
nếu chức năng này đã không được trả lại.

732
00:59:51,540 --> 00:59:58,710
Do đó, chúng ta đang có hiện tại chỗ, nơi chúng tôi muốn chèn các nút mới.

733
00:59:58,710 --> 01:00:05,210
Những gì còn lại phải được thực hiện là để thực sự xây dựng các nút mới,

734
01:00:05,210 --> 01:00:08,480
mà chúng ta có thể làm khá dễ dàng.

735
01:00:08,480 --> 01:00:14,930
Chúng tôi có thể sử dụng chức năng nút siêu tiện dụng của chúng tôi xây dựng,

736
01:00:14,930 --> 01:00:17,210
và một cái gì đó mà chúng ta không làm trước đó -

737
01:00:17,210 --> 01:00:21,400
chúng ta chỉ cần loại cho các cấp, nhưng bây giờ chúng tôi sẽ làm chỉ để chắc chắn -

738
01:00:21,400 --> 01:00:27,130
chúng tôi sẽ kiểm tra để đảm bảo rằng giá trị trả về bởi nút mới đã thực sự

739
01:00:27,130 --> 01:00:33,410
không phải null, bởi vì chúng tôi không muốn để bắt đầu truy cập bộ nhớ rằng nếu nó là null.

740
01:00:33,410 --> 01:00:39,910
Chúng tôi có thể kiểm tra để chắc chắn rằng nút mới không bằng vô giá trị.

741
01:00:39,910 --> 01:00:42,910
Hoặc thay vào đó, chúng tôi chỉ có thể nhìn thấy nếu nó thực sự là vô giá trị,

742
01:00:42,910 --> 01:00:52,120
và nếu nó là null, sau đó chúng tôi chỉ có thể trả về false sớm.

743
01:00:52,120 --> 01:00:59,090
>> Tại thời điểm này, chúng tôi có dây nút mới vào vị trí thích hợp của nó trong cây.

744
01:00:59,090 --> 01:01:03,510
Nếu chúng ta nhìn lại chính nơi mà chúng tôi đã thực sự hệ thống dây điện trong giá trị trước đây,

745
01:01:03,510 --> 01:01:08,470
chúng ta thấy rằng cách chúng tôi đã làm việc đó khi chúng tôi muốn đặt 3 trong cây

746
01:01:08,470 --> 01:01:11,750
chúng tôi truy cập con trái của gốc.

747
01:01:11,750 --> 01:01:14,920
Khi chúng tôi đặt 9 trong cây, chúng tôi đã có để truy cập vào các con phải của gốc.

748
01:01:14,920 --> 01:01:21,030
Chúng tôi đã có một con trỏ đến phụ huynh để đưa một giá trị mới vào cây.

749
01:01:21,030 --> 01:01:24,430
Di chuyển trở lại để chèn, đó là sẽ không khá làm việc ở đây

750
01:01:24,430 --> 01:01:27,550
vì chúng ta không có một con trỏ cha mẹ.

751
01:01:27,550 --> 01:01:31,650
Những gì chúng tôi muốn có thể làm được là, vào thời điểm này,

752
01:01:31,650 --> 01:01:37,080
kiểm tra giá trị của cha mẹ và xem - tốt, chúa ơi,

753
01:01:37,080 --> 01:01:41,990
nếu giá trị của cha mẹ ít hơn giá trị hiện tại,

754
01:01:41,990 --> 01:01:54,440
sau đó con phải của cha mẹ nên là nút mới;

755
01:01:54,440 --> 01:02:07,280
nếu không, con trái của cha mẹ nên là các node mới.

756
01:02:07,280 --> 01:02:10,290
Tuy nhiên, chúng tôi không có con trỏ này mẹ khá chưa.

757
01:02:10,290 --> 01:02:15,010
>> Để có được nó, chúng tôi đang thực sự sẽ phải theo dõi nó như chúng tôi đi qua cây

758
01:02:15,010 --> 01:02:18,440
và tìm thấy những vị trí thích hợp trong vòng lặp của chúng tôi ở trên.

759
01:02:18,440 --> 01:02:26,840
Chúng ta có thể làm điều đó bằng cách di chuyển trở lại lên đến trên cùng của chức năng chèn của chúng tôi

760
01:02:26,840 --> 01:02:32,350
và theo dõi một biến con trỏ khác được gọi là cha mẹ.

761
01:02:32,350 --> 01:02:39,340
Chúng tôi sẽ thiết lập nó bằng vô giá trị ban đầu,

762
01:02:39,340 --> 01:02:43,640
và sau đó mỗi khi chúng tôi đi qua cây,

763
01:02:43,640 --> 01:02:51,540
chúng ta sẽ đặt con trỏ phụ huynh để phù hợp với con trỏ hiện tại.

764
01:02:51,540 --> 01:02:59,140
Đặt cha mẹ bằng hiện.

765
01:02:59,140 --> 01:03:02,260
Bằng cách này, mỗi lần chúng tôi đi qua,

766
01:03:02,260 --> 01:03:05,550
chúng ta sẽ đảm bảo rằng, cũng như con trỏ hiện tại được tăng lên

767
01:03:05,550 --> 01:03:12,640
con trỏ mẹ sau nó chỉ là một mức độ cao hơn so với con trỏ hiện tại trong cây.

768
01:03:12,640 --> 01:03:17,370
Đó là tất cả có vẻ khá tốt.

769
01:03:17,370 --> 01:03:22,380
>> Tôi nghĩ rằng một điều rằng chúng tôi sẽ muốn điều chỉnh này là xây dựng vô nút quay trở lại.

770
01:03:22,380 --> 01:03:25,380
Để có được xây dựng nút để thực sự thành công trở về null,

771
01:03:25,380 --> 01:03:31,060
chúng tôi sẽ phải sửa đổi mã đó,

772
01:03:31,060 --> 01:03:37,270
bởi vì ở đây, chúng ta không bao giờ được thử nghiệm để đảm bảo rằng malloc trả về một con trỏ hợp lệ.

773
01:03:37,270 --> 01:03:53,390
Vì vậy, nếu (n = NULL!), Sau đó -

774
01:03:53,390 --> 01:03:55,250
nếu malloc trả về một con trỏ hợp lệ, sau đó chúng tôi sẽ khởi tạo nó;

775
01:03:55,250 --> 01:04:02,540
nếu không, chúng tôi sẽ chỉ quay trở lại và sẽ kết thúc trở về null cho chúng tôi.

776
01:04:02,540 --> 01:04:13,050
Bây giờ tất cả trông khá tốt. Hãy làm cho chắc chắn rằng điều này thực sự biên dịch.

777
01:04:13,050 --> 01:04:22,240
Làm cho cây nhị phân, và oh, chúng tôi đã có một số công cụ xảy ra ở đây.

778
01:04:22,240 --> 01:04:29,230
>> Chúng tôi đã có một tuyên bố tiềm ẩn của chức năng xây dựng nút.

779
01:04:29,230 --> 01:04:31,950
Một lần nữa, với các trình biên dịch, chúng ta sẽ bắt đầu ở đầu trang.

780
01:04:31,950 --> 01:04:36,380
Những gì mà phải có nghĩa là tôi đang kêu gọi xây dựng nút trước khi tôi thực sự tuyên bố nó.

781
01:04:36,380 --> 01:04:37,730
Hãy quay trở lại các mã thực sự nhanh chóng.

782
01:04:37,730 --> 01:04:43,510
Di chuyển xuống, và chắc chắn đủ, chức năng chèn của tôi được khai báo

783
01:04:43,510 --> 01:04:47,400
phía trên xây dựng chức năng nút,

784
01:04:47,400 --> 01:04:50,070
nhưng tôi đang cố gắng để sử dụng xây dựng nút bên trong chèn.

785
01:04:50,070 --> 01:05:06,610
Tôi sẽ đi và sao chép và sau đó dán cách xây dựng chức năng nút lên đây ở đầu trang.

786
01:05:06,610 --> 01:05:11,750
Bằng cách đó, hy vọng rằng sẽ làm việc. Hãy cung cấp cho khác đi.

787
01:05:11,750 --> 01:05:18,920
Bây giờ tất cả biên dịch. Tất cả là tốt.

788
01:05:18,920 --> 01:05:21,640
>> Tuy nhiên, vào thời điểm này, chúng tôi đã không thực sự được gọi là chức năng chèn của chúng tôi.

789
01:05:21,640 --> 01:05:26,510
Chúng tôi chỉ biết rằng nó biên dịch, do đó, chúng ta hãy đi vào và đặt một số cuộc gọi.

790
01:05:26,510 --> 01:05:28,240
Hãy làm điều đó trong chức năng chính của chúng tôi.

791
01:05:28,240 --> 01:05:32,390
Ở đây, chúng tôi nhận xét ra 5, 8, và 2,

792
01:05:32,390 --> 01:05:36,680
và sau đó chúng ta không dây lên xuống đây.

793
01:05:36,680 --> 01:05:41,640
Hãy làm cho một số cuộc gọi để chèn,

794
01:05:41,640 --> 01:05:46,440
và chúng ta hãy cũng sử dụng cùng một loại công cụ mà chúng tôi sử dụng

795
01:05:46,440 --> 01:05:52,810
khi chúng ta thực hiện những cuộc gọi printf để đảm bảo rằng tất cả mọi thứ đã lăp.

796
01:05:52,810 --> 01:06:00,550
Tôi sẽ để sao chép và dán,

797
01:06:00,550 --> 01:06:12,450
và thay vì chứa chúng ta sẽ làm chèn.

798
01:06:12,450 --> 01:06:30,140
Và thay vì 6, 10, và 1, chúng tôi sẽ sử dụng 5, 8, và 2.

799
01:06:30,140 --> 01:06:37,320
Điều này hy vọng sẽ chèn 5, 8, và 2 vào cây.

800
01:06:37,320 --> 01:06:44,050
Biên dịch. Tất cả là tốt. Bây giờ chúng ta sẽ thực sự chạy chương trình của chúng tôi.

801
01:06:44,050 --> 01:06:47,330
>> Tất cả mọi thứ trở lại sai.

802
01:06:47,330 --> 01:06:53,830
Vì vậy, 5, 8, và 2 không đi, và nó trông giống như Chứa không tìm thấy chúng hoặc.

803
01:06:53,830 --> 01:06:58,890
Chuyện gì đang xảy ra? Hãy thu nhỏ.

804
01:06:58,890 --> 01:07:02,160
Vấn đề đầu tiên là chèn dường như quay trở lại sai,

805
01:07:02,160 --> 01:07:08,750
và có vẻ như đó là bởi vì chúng tôi còn lại trong cuộc gọi giả trở lại của chúng tôi,

806
01:07:08,750 --> 01:07:14,590
và chúng tôi không bao giờ thực sự trở lại đúng sự thật.

807
01:07:14,590 --> 01:07:17,880
Chúng ta có thể thiết lập mà lên.

808
01:07:17,880 --> 01:07:25,290
Vấn đề thứ hai là, bây giờ ngay cả nếu chúng ta làm - tiết kiệm này, bỏ điều này,

809
01:07:25,290 --> 01:07:34,530
chạy làm lại, có nó biên dịch, sau đó chạy nó -

810
01:07:34,530 --> 01:07:37,670
chúng ta thấy rằng cái gì khác xảy ra ở đây.

811
01:07:37,670 --> 01:07:42,980
5, 8, và 2 người vẫn không bao giờ được tìm thấy trong cây.

812
01:07:42,980 --> 01:07:44,350
Vì vậy, những gì đang xảy ra?

813
01:07:44,350 --> 01:07:45,700
>> Chúng ta hãy xem xét điều này trong các mã.

814
01:07:45,700 --> 01:07:49,790
Hãy xem nếu chúng ta có thể con số này ra.

815
01:07:49,790 --> 01:07:57,940
Chúng tôi bắt đầu với phụ huynh không phải là vô giá trị.

816
01:07:57,940 --> 01:07:59,510
Chúng tôi đặt con trỏ hiện tại bằng con trỏ gốc,

817
01:07:59,510 --> 01:08:04,280
và chúng tôi sẽ làm việc theo cách của chúng tôi thông qua cây.

818
01:08:04,280 --> 01:08:08,650
Nếu nút hiện tại không phải là null, sau đó chúng tôi biết rằng chúng tôi có thể di chuyển xuống một chút.

819
01:08:08,650 --> 01:08:12,330
Chúng tôi đặt con trỏ mẹ của chúng tôi để được bình đẳng với con trỏ hiện tại,

820
01:08:12,330 --> 01:08:15,420
kiểm tra giá trị nếu các giá trị đều giống nhau, chúng tôi quay trở lại sai.

821
01:08:15,420 --> 01:08:17,540
Nếu các giá trị ít, chúng tôi chuyển sang bên phải;

822
01:08:17,540 --> 01:08:20,399
nếu không, chúng tôi chuyển sang bên trái.

823
01:08:20,399 --> 01:08:24,220
Sau đó, chúng tôi xây dựng một nút. Tôi sẽ phóng to một chút.

824
01:08:24,220 --> 01:08:31,410
Và ở đây, chúng tôi sẽ cố gắng để dây lên các giá trị để được giống.

825
01:08:31,410 --> 01:08:37,250
Chuyện gì đang xảy ra? Hãy xem nếu có thể Valgrind có thể cung cấp cho chúng tôi một gợi ý.

826
01:08:37,250 --> 01:08:43,910
>> Tôi thích sử dụng Valgrind chỉ vì Valgrind thực sự nhanh chóng chạy

827
01:08:43,910 --> 01:08:46,729
và cho bạn biết nếu có bất kỳ lỗi bộ nhớ.

828
01:08:46,729 --> 01:08:48,300
Khi chúng tôi chạy Valgrind trên các mã,

829
01:08:48,300 --> 01:08:55,859
như bạn có thể nhìn thấy ngay here--Valgrind./binary_tree--and nhấn Enter.

830
01:08:55,859 --> 01:09:03,640
Bạn thấy rằng chúng tôi không có bất kỳ lỗi bộ nhớ, vì vậy nó trông giống như tất cả mọi thứ sao cho đến nay.

831
01:09:03,640 --> 01:09:07,529
Chúng tôi có một số rò rỉ bộ nhớ, mà chúng ta biết, bởi vì chúng tôi không

832
01:09:07,529 --> 01:09:08,910
xảy ra để giải phóng bất kỳ của các nút của chúng tôi.

833
01:09:08,910 --> 01:09:13,050
Chúng ta hãy thử chạy GDB để xem những gì đang thực sự xảy ra.

834
01:09:13,050 --> 01:09:20,010
Chúng tôi sẽ làm gdb / binary_tree. Nó khởi động tốt.

835
01:09:20,010 --> 01:09:23,670
Hãy thiết lập một điểm break trên chèn.

836
01:09:23,670 --> 01:09:28,600
Hãy chạy.

837
01:09:28,600 --> 01:09:31,200
Dường như chúng tôi không bao giờ thực sự được gọi là chèn.

838
01:09:31,200 --> 01:09:39,410
Có vẻ như vấn đề chỉ là khi tôi thay đổi trong chính

839
01:09:39,410 --> 01:09:44,279
tất cả các cuộc gọi printf từ chứa -

840
01:09:44,279 --> 01:09:56,430
Tôi không bao giờ thực sự thay đổi này gọi chèn.

841
01:09:56,430 --> 01:10:01,660
Bây giờ chúng ta hãy cho nó một thử. Hãy biên dịch.

842
01:10:01,660 --> 01:10:09,130
Tất cả sẽ tốt. Bây giờ chúng ta hãy thử chạy nó, xem những gì sẽ xảy ra.

843
01:10:09,130 --> 01:10:13,320
Ổn chứ! Tất cả mọi thứ trông khá tốt ở đó.

844
01:10:13,320 --> 01:10:18,130
>> Điều cuối cùng để suy nghĩ về, được có bất kỳ trường hợp cạnh để chèn này?

845
01:10:18,130 --> 01:10:23,170
Và nó quay ra rằng, tốt, một trong những trường hợp cạnh đó là luôn luôn thú vị để suy nghĩ về

846
01:10:23,170 --> 01:10:26,250
là, những gì sẽ xảy ra nếu cây của bạn là trống rỗng và bạn gọi chức năng này chèn?

847
01:10:26,250 --> 01:10:30,330
Nó sẽ làm việc? Vâng, chúng ta hãy cho nó một thử.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c.

849
01:10:32,110 --> 01:10:35,810
Cách chúng ta sẽ kiểm tra điều này, chúng ta sẽ đi xuống với chức năng chính của chúng tôi,

850
01:10:35,810 --> 01:10:41,690
và thay vì dây các nút lên như thế này,

851
01:10:41,690 --> 01:10:56,730
chúng tôi chỉ có nhận xét về toàn bộ điều,

852
01:10:56,730 --> 01:11:02,620
và thay vì dây lên các nút chính mình,

853
01:11:02,620 --> 01:11:09,400
chúng ta có thể thực sự đi trước và xóa tất cả những điều này.

854
01:11:09,400 --> 01:11:17,560
Chúng ta sẽ làm cho tất cả mọi thứ của một cuộc gọi để chèn.

855
01:11:17,560 --> 01:11:49,020
Vì vậy, chúng ta hãy làm - thay vì 5, 8, và 2, chúng ta sẽ để chèn 7, 3, và 9.

856
01:11:49,020 --> 01:11:58,440
Và sau đó chúng tôi cũng sẽ muốn chèn 6, cũng.

857
01:11:58,440 --> 01:12:05,190
Lưu. Bỏ thuốc lá. Cây nhị phân.

858
01:12:05,190 --> 01:12:08,540
Tất cả biên dịch.

859
01:12:08,540 --> 01:12:10,320
Chúng tôi chỉ có thể chạy nó như là và xem những gì sẽ xảy ra,

860
01:12:10,320 --> 01:12:12,770
nhưng nó cũng sẽ được thực sự quan trọng để đảm bảo rằng

861
01:12:12,770 --> 01:12:14,740
chúng tôi không có bất kỳ lỗi bộ nhớ,

862
01:12:14,740 --> 01:12:16,840
vì đây là một trong những trường hợp của chúng tôi mà chúng ta biết về.

863
01:12:16,840 --> 01:12:20,150
>> Hãy chắc chắn rằng nó hoạt động tốt dưới Valgrind,

864
01:12:20,150 --> 01:12:28,310
mà chúng tôi sẽ làm bằng cách chỉ chạy Valgrind / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Có vẻ như chúng tôi thực sự có một lỗi từ một bối cảnh -

866
01:12:31,110 --> 01:12:33,790
chúng tôi có lỗi phân khúc này.

867
01:12:33,790 --> 01:12:36,690
Điều gì đã xảy ra?

868
01:12:36,690 --> 01:12:41,650
Valgrind thực sự cho chúng ta biết nó ở đâu.

869
01:12:41,650 --> 01:12:43,050
Thu nhỏ một chút.

870
01:12:43,050 --> 01:12:46,040
Có vẻ như nó đang xảy ra trong chức năng chèn của chúng tôi,

871
01:12:46,040 --> 01:12:53,420
nơi chúng tôi có một chi tiết không hợp lệ của kích thước 4 tại chèn, đường 60.

872
01:12:53,420 --> 01:13:03,590
Chúng ta hãy quay trở lại và xem những gì đang xảy ra ở đây.

873
01:13:03,590 --> 01:13:05,350
Thu nhỏ thực sự nhanh chóng.

874
01:13:05,350 --> 01:13:14,230
Tôi muốn làm cho chắc chắn rằng nó không đi đến các cạnh của màn hình, do đó chúng ta có thể nhìn thấy tất cả mọi thứ.

875
01:13:14,230 --> 01:13:18,760
Kéo mà một chút. Được rồi.

876
01:13:18,760 --> 01:13:35,030
Di chuyển xuống, và vấn đề là ngay tại đây.

877
01:13:35,030 --> 01:13:40,120
Điều gì sẽ xảy ra nếu chúng ta có được xuống và nút hiện tại của chúng tôi là đã được vô giá trị,

878
01:13:40,120 --> 01:13:44,010
nút cha của chúng tôi là vô giá trị, vì vậy nếu chúng ta nhìn ở đầu, ngay tại đây -

879
01:13:44,010 --> 01:13:47,340
nếu điều này vòng lặp trong khi không bao giờ thực sự thực hiện

880
01:13:47,340 --> 01:13:52,330
bởi vì giá trị hiện tại của chúng tôi là vô giá trị gốc của chúng tôi là null để hiện là null -

881
01:13:52,330 --> 01:13:57,810
sau đó mẹ của chúng tôi không bao giờ được thiết lập hiện hoặc giá trị hợp lệ,

882
01:13:57,810 --> 01:14:00,580
như vậy, cha mẹ cũng sẽ là null.

883
01:14:00,580 --> 01:14:03,700
Chúng ta cần nhớ để kiểm tra cho rằng

884
01:14:03,700 --> 01:14:08,750
theo thời gian, chúng tôi nhận được xuống ở đây, và chúng tôi bắt đầu truy cập giá trị của cha mẹ.

885
01:14:08,750 --> 01:14:13,190
Vì vậy, những gì sẽ xảy ra? Vâng, nếu phụ huynh là null -

886
01:14:13,190 --> 01:14:17,990
(cha mẹ == NULL) - sau đó chúng ta biết rằng

887
01:14:17,990 --> 01:14:19,530
đó không phải là bất cứ điều gì trong cây.

888
01:14:19,530 --> 01:14:22,030
Chúng ta phải cố gắng để chèn nó ở gốc.

889
01:14:22,030 --> 01:14:32,570
Chúng ta có thể làm điều đó bằng cách chỉ cần cài đặt gốc bằng các nút mới.

890
01:14:32,570 --> 01:14:40,010
Sau đó, vào thời điểm này, chúng tôi không thực sự muốn đi qua những thứ khác.

891
01:14:40,010 --> 01:14:44,780
Thay vào đó, ngay tại đây, chúng ta có thể làm một trong hai khác-nếu-khác,

892
01:14:44,780 --> 01:14:47,610
hoặc chúng ta có thể kết hợp tất cả mọi thứ ở đây trong một khác,

893
01:14:47,610 --> 01:14:56,300
nhưng ở đây chúng tôi chỉ sẽ sử dụng khác và làm theo cách đó.

894
01:14:56,300 --> 01:14:59,030
Bây giờ, chúng ta sẽ kiểm tra để đảm bảo rằng mẹ của chúng tôi không phải là null

895
01:14:59,030 --> 01:15:02,160
sau đó trước khi thực sự cố gắng để truy cập vào các lĩnh vực của mình.

896
01:15:02,160 --> 01:15:05,330
Điều này sẽ giúp chúng ta tránh được lỗi phân khúc.

897
01:15:05,330 --> 01:15:14,740
Vì vậy, chúng tôi bỏ thuốc lá, thu nhỏ, biên dịch, chạy.

898
01:15:14,740 --> 01:15:18,130
>> Không có lỗi, nhưng chúng tôi vẫn có một bó của rò rỉ bộ nhớ

899
01:15:18,130 --> 01:15:20,650
vì chúng tôi không giải phóng bất kỳ của các nút của chúng tôi.

900
01:15:20,650 --> 01:15:24,350
Tuy nhiên, nếu chúng ta đi lên ở đây và chúng ta nhìn vào bản in của chúng tôi,

901
01:15:24,350 --> 01:15:30,880
chúng ta thấy rằng, tốt, trông giống như tất cả của chèn của chúng tôi đã trở về đúng, đó là tốt.

902
01:15:30,880 --> 01:15:33,050
Việc chèn là tất cả sự thật,

903
01:15:33,050 --> 01:15:36,670
và sau đó có chứa các cuộc gọi phù hợp cũng đúng.

904
01:15:36,670 --> 01:15:41,510
>> Good job! Có vẻ như chúng tôi đã thành công bằng văn bản chèn.

905
01:15:41,510 --> 01:15:47,430
Đó là tất cả chúng tôi đã cho Đặc điểm kỹ thuật Set vấn đề này trong tuần.

906
01:15:47,430 --> 01:15:51,720
Một thách thức thú vị để suy nghĩ về cách bạn thực sự sẽ đi vào

907
01:15:51,720 --> 01:15:55,340
và miễn phí tất cả các nút trong cây này.

908
01:15:55,340 --> 01:15:58,830
Chúng ta có thể làm như vậy là một số cách khác nhau,

909
01:15:58,830 --> 01:16:01,930
nhưng tôi sẽ để lại cho bạn để thử nghiệm,

910
01:16:01,930 --> 01:16:06,080
và là một thách thức thú vị, hãy thử và đảm bảo rằng bạn có thể chắc chắn rằng

911
01:16:06,080 --> 01:16:09,490
rằng báo cáo này Valgrind trả về không có lỗi và không có rò rỉ.

912
01:16:09,490 --> 01:16:12,880
>> Chúc may mắn vào bộ Huffman tuần này vấn đề mã hóa,

913
01:16:12,880 --> 01:16:14,380
và chúng tôi sẽ nhìn thấy bạn trong tuần tới!

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