1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Bagian 7] [Kurang Nyaman]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Harvard University]

3
00:00:04,890 --> 00:00:07,000
[Ini adalah CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Selamat Datang di Bagian 7.

5
00:00:09,080 --> 00:00:11,330
Berkat badai Sandy,

6
00:00:11,330 --> 00:00:13,440
bukan memiliki bagian yang normal pekan ini,

7
00:00:13,440 --> 00:00:17,650
kami melakukan hal ini berjalan-melalui, melalui bagian dari pertanyaan.

8
00:00:17,650 --> 00:00:22,830
Saya akan mengikuti bersama dengan Masalah Set 6 Spesifikasi,

9
00:00:22,830 --> 00:00:25,650
dan akan melalui semua pertanyaan dalam

10
00:00:25,650 --> 00:00:27,770
Sebuah Bagian bagian Pertanyaan.

11
00:00:27,770 --> 00:00:30,940
Jika ada pertanyaan,

12
00:00:30,940 --> 00:00:32,960
silahkan posting ini pada CS50 Bahas.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Mari kita mulai.

14
00:00:35,480 --> 00:00:40,780
Saat ini aku sedang melihat halaman 3 dari Set Keterangan Soal.

15
00:00:40,780 --> 00:00:44,110
Kami akan pertama kali mulai berbicara tentang pohon biner

16
00:00:44,110 --> 00:00:47,850
karena mereka memiliki banyak relevansi untuk mengatur masalah ini minggu -

17
00:00:47,850 --> 00:00:49,950
pengkodean Pohon Huffman.

18
00:00:49,950 --> 00:00:55,000
Salah satu struktur data pertama kita bicarakan pada CS50 adalah array.

19
00:00:55,000 --> 00:01:00,170
Ingat bahwa array adalah urutan elemen -

20
00:01:00,170 --> 00:01:04,019
semua jenis yang sama - disimpan tepat di samping satu sama lain dalam memori.

21
00:01:04,019 --> 00:01:14,420
Jika saya memiliki sebuah array integer yang aku bisa menggambar menggunakan gaya kotak-nomor-bilangan bulat -

22
00:01:14,420 --> 00:01:20,290
Katakanlah saya memiliki 5 di kotak pertama, saya memiliki 7 di kedua,

23
00:01:20,290 --> 00:01:27,760
maka saya memiliki 8, 10, dan 20 di kotak akhir.

24
00:01:27,760 --> 00:01:33,000
Ingat, keduanya benar-benar baik hal tentang array ini

25
00:01:33,000 --> 00:01:38,800
adalah bahwa kita memiliki akses konstan-waktu untuk setiap elemen tertentu

26
00:01:38,800 --> 00:01:40,500
 dalam array jika kita tahu indeks.

27
00:01:40,500 --> 00:01:44,670
Sebagai contoh, jika saya ingin ambil elemen ketiga dalam array -

28
00:01:44,670 --> 00:01:47,870
pada indeks 2 menggunakan zero-based sistem pengindeksan kami -

29
00:01:47,870 --> 00:01:52,220
Aku benar-benar hanya perlu melakukan perhitungan matematika sederhana,

30
00:01:52,220 --> 00:01:56,170
hop ke posisi dalam array,

31
00:01:56,170 --> 00:01:57,840
mencabut 8 yang disimpan di sana,

32
00:01:57,840 --> 00:01:59,260
dan aku baik untuk pergi.

33
00:01:59,260 --> 00:02:03,350
>> Salah satu hal buruk tentang array ini - yang kita bicarakan

34
00:02:03,350 --> 00:02:05,010
ketika kita membahas daftar link -

35
00:02:05,010 --> 00:02:09,120
adalah bahwa jika saya ingin memasukkan elemen ke dalam array ini,

36
00:02:09,120 --> 00:02:11,090
Aku akan harus melakukan beberapa pergeseran sekitar.

37
00:02:11,090 --> 00:02:12,940
Misalnya, array ini di sini

38
00:02:12,940 --> 00:02:16,850
adalah dalam rangka diurutkan - diurutkan dalam urutan -

39
00:02:16,850 --> 00:02:19,440
5, maka 7, kemudian 8, kemudian 10, kemudian 20 -

40
00:02:19,440 --> 00:02:23,100
tetapi jika saya ingin memasukkan nomor 9 ke dalam array ini,

41
00:02:23,100 --> 00:02:27,460
Aku akan harus mengalihkan beberapa elemen untuk membuat ruang.

42
00:02:27,460 --> 00:02:30,440
Kita dapat menarik ini di sini.

43
00:02:30,440 --> 00:02:35,650
Aku akan harus memindahkan 5, 7, dan kemudian 8;

44
00:02:35,650 --> 00:02:38,720
menciptakan celah di mana saya dapat menempatkan 9,

45
00:02:38,720 --> 00:02:45,910
dan kemudian 10 dan 20 dapat pergi ke kanan 9.

46
00:02:45,910 --> 00:02:49,450
Ini adalah jenis rasa sakit karena dalam skenario terburuk -

47
00:02:49,450 --> 00:02:54,350
ketika kita harus memasukkan baik di awal atau di akhir

48
00:02:54,350 --> 00:02:56,040
dari array, tergantung pada bagaimana kita pergeseran -

49
00:02:56,040 --> 00:02:58,850
kita mungkin akhirnya harus menggeser semua elemen

50
00:02:58,850 --> 00:03:00,750
bahwa kita sedang menyimpan dalam array.

51
00:03:00,750 --> 00:03:03,810
>> Jadi, apa cara sekitar ini?

52
00:03:03,810 --> 00:03:09,260
Cara sekitar ini adalah untuk pergi ke linked-list metode kami di mana -

53
00:03:09,260 --> 00:03:19,820
bukannya menyimpan elemen 5, 7, 8, 10, dan 20 semua sebelah satu sama lain dalam memori -

54
00:03:19,820 --> 00:03:25,630
bukan apa yang kita lakukan adalah menyimpannya jenis mana pun kita ingin menyimpannya

55
00:03:25,630 --> 00:03:32,470
dalam linked-list node yang aku menggambar di sini, semacam ad hoc.

56
00:03:32,470 --> 00:03:42,060
Dan kemudian kita menghubungkan mereka bersama-sama menggunakan pointer berikutnya.

57
00:03:42,060 --> 00:03:44,370
Saya dapat memiliki pointer dari 5 ke 7,

58
00:03:44,370 --> 00:03:46,420
pointer dari 7 ke 8,

59
00:03:46,420 --> 00:03:47,770
pointer dari 8 ke 10,

60
00:03:47,770 --> 00:03:51,220
dan akhirnya, sebuah pointer dari 10 ke 20,

61
00:03:51,220 --> 00:03:54,880
dan kemudian pointer null pada 20 menunjukkan bahwa tidak ada yang kiri.

62
00:03:54,880 --> 00:03:59,690
Trade-off yang kita miliki di sini

63
00:03:59,690 --> 00:04:05,360
adalah bahwa sekarang jika kita ingin memasukkan nomor 9 dalam daftar kami diurutkan,

64
00:04:05,360 --> 00:04:08,270
yang harus kita lakukan adalah membuat simpul baru dengan 9,

65
00:04:08,270 --> 00:04:12,290
kawat itu untuk menunjuk ke tempat yang tepat,

66
00:04:12,290 --> 00:04:20,630
dan kemudian kembali-kawat 8 untuk menunjuk ke 9.

67
00:04:20,630 --> 00:04:25,660
Itu cukup cepat, dengan asumsi kita tahu persis di mana kita ingin memasukkan 9.

68
00:04:25,660 --> 00:04:32,610
Namun trade-off dalam pertukaran untuk ini adalah bahwa sekarang kami telah kehilangan akses konstan-waktu

69
00:04:32,610 --> 00:04:36,230
kepada elemen tertentu dalam struktur data kami.

70
00:04:36,230 --> 00:04:40,950
Sebagai contoh, jika saya ingin mencari elemen keempat dalam linked list,

71
00:04:40,950 --> 00:04:43,510
Aku akan harus mulai dari awal daftar

72
00:04:43,510 --> 00:04:48,930
dan bekerja dengan cara saya melalui menghitung simpul-simpul by-sampai aku menemukan yang keempat.

73
00:04:48,930 --> 00:04:55,870
>> Dalam rangka untuk mendapatkan kinerja akses lebih baik daripada linked list -

74
00:04:55,870 --> 00:04:59,360
tetapi juga mempertahankan beberapa manfaat yang kita miliki

75
00:04:59,360 --> 00:05:01,800
dalam hal penyisipan-waktu dari sebuah linked list -

76
00:05:01,800 --> 00:05:05,750
pohon biner akan perlu menggunakan memori lebih sedikit.

77
00:05:05,750 --> 00:05:11,460
Secara khusus, bukan hanya memiliki satu pointer dalam simpul pohon biner -

78
00:05:11,460 --> 00:05:13,350
seperti linked list-node tidak -

79
00:05:13,350 --> 00:05:16,950
kita akan menambahkan pointer kedua node pohon biner.

80
00:05:16,950 --> 00:05:19,950
Daripada hanya memiliki satu pointer ke elemen berikutnya,

81
00:05:19,950 --> 00:05:24,420
kita akan memiliki pointer ke anak kiri dan anak kanan.

82
00:05:24,420 --> 00:05:26,560
>> Mari kita menggambar untuk melihat apa yang benar-benar tampak seperti.

83
00:05:26,560 --> 00:05:31,350
Sekali lagi, aku akan menggunakan kotak dan panah.

84
00:05:31,350 --> 00:05:37,150
Sebuah simpul pohon biner akan mulai dengan hanya kotak sederhana.

85
00:05:37,150 --> 00:05:40,940
Ini akan memiliki ruang untuk nilai,

86
00:05:40,940 --> 00:05:47,280
dan kemudian itu juga akan memiliki ruang untuk anak kiri dan anak kanan.

87
00:05:47,280 --> 00:05:49,280
Aku akan label mereka di sini.

88
00:05:49,280 --> 00:05:57,560
Kita akan memiliki anak kiri, dan kemudian kita akan memiliki anak kanan.

89
00:05:57,560 --> 00:05:59,920
Ada banyak cara yang berbeda untuk melakukan hal ini.

90
00:05:59,920 --> 00:06:02,050
Kadang-kadang untuk ruang dan kenyamanan,

91
00:06:02,050 --> 00:06:06,460
Aku benar-benar akan menarik seperti saya lakukan di sini di bagian bawah

92
00:06:06,460 --> 00:06:10,910
di mana aku akan memiliki nilai di atas,

93
00:06:10,910 --> 00:06:14,060
dan kemudian anak kanan di kanan bawah,

94
00:06:14,060 --> 00:06:16,060
dan anak kiri di bagian bawah-kiri.

95
00:06:16,060 --> 00:06:20,250
Akan kembali ke diagram atas,

96
00:06:20,250 --> 00:06:22,560
kita memiliki nilai di bagian paling atas,

97
00:06:22,560 --> 00:06:25,560
maka kita memiliki pointer kiri-anak, dan kemudian kita memiliki pointer kanan anak.

98
00:06:25,560 --> 00:06:30,110
>> Dalam Spesifikasi Soal Set,

99
00:06:30,110 --> 00:06:33,110
kita berbicara tentang menggambar simpul yang memiliki nilai 7,

100
00:06:33,110 --> 00:06:39,750
dan kemudian pointer kiri-anak yang nol, dan pointer kanan anak yang null.

101
00:06:39,750 --> 00:06:46,040
Kita dapat menulis NULL modal dalam ruang untuk

102
00:06:46,040 --> 00:06:51,610
baik anak kiri dan anak kanan, atau kita dapat menarik garis miring diagonal ini

103
00:06:51,610 --> 00:06:53,750
melalui masing-masing kotak untuk menunjukkan bahwa itu nol.

104
00:06:53,750 --> 00:06:57,560
Aku akan melakukan itu hanya karena itu sederhana.

105
00:06:57,560 --> 00:07:03,700
Apa yang Anda lihat di sini adalah dua cara diagram simpul biner pohon yang sangat sederhana

106
00:07:03,700 --> 00:07:07,960
di mana kita memiliki nilai 7 dan pointer anak nol.

107
00:07:07,960 --> 00:07:15,220
>> Bagian kedua pembicaraan spesifikasi kami tentang bagaimana dengan daftar link -

108
00:07:15,220 --> 00:07:18,270
ingat, kita hanya harus berpegang pada elemen pertama dalam daftar

109
00:07:18,270 --> 00:07:20,270
mengingat seluruh daftar -

110
00:07:20,270 --> 00:07:26,140
dan juga, dengan pohon biner, kita hanya perlu berpegang pada satu pointer ke pohon

111
00:07:26,140 --> 00:07:31,120
dalam rangka untuk mempertahankan kontrol atas struktur seluruh data.

112
00:07:31,120 --> 00:07:36,150
Unsur khusus dari pohon disebut node akar pohon.

113
00:07:36,150 --> 00:07:43,360
Misalnya, jika satu simpul - simpul ini mengandung nilai 7

114
00:07:43,360 --> 00:07:45,500
dengan pointer kiri dan kanan-anak nol -

115
00:07:45,500 --> 00:07:47,360
adalah satu-satunya nilai di pohon kami,

116
00:07:47,360 --> 00:07:50,390
maka ini akan menjadi simpul akar kami.

117
00:07:50,390 --> 00:07:52,240
Ini adalah awal dari pohon kami.

118
00:07:52,240 --> 00:07:58,530
Kita bisa melihat ini sedikit lebih jelas sekali kita mulai menambahkan node lebih untuk pohon kami.

119
00:07:58,530 --> 00:08:01,510
Mari saya menarik sebuah halaman baru.

120
00:08:01,510 --> 00:08:05,000
>> Sekarang kita akan menggambar pohon yang memiliki 7 pada akar,

121
00:08:05,000 --> 00:08:10,920
dan 3 dalam dari anak kiri, dan 9 dalam anak kanan.

122
00:08:10,920 --> 00:08:13,500
Sekali lagi, ini cukup sederhana.

123
00:08:13,500 --> 00:08:26,510
Kami punya 7, menggambar node untuk 3, sebuah node untuk 9,

124
00:08:26,510 --> 00:08:32,150
dan aku akan mengatur pointer kiri-anak 7 untuk menunjuk ke simpul yang mengandung 3,

125
00:08:32,150 --> 00:08:37,850
dan pointer kanan anak dari simpul yang mengandung 7 ke node yang mengandung 9.

126
00:08:37,850 --> 00:08:42,419
Sekarang, sejak 3 dan 9 tidak memiliki anak,

127
00:08:42,419 --> 00:08:48,500
kita akan mengatur semua pointer anak mereka untuk menjadi nol.

128
00:08:48,500 --> 00:08:56,060
Di sini, akar pohon kita sesuai dengan simpul yang berisi nomor 7.

129
00:08:56,060 --> 00:09:02,440
Anda dapat melihat bahwa jika semua yang kita miliki adalah pointer ke simpul akar,

130
00:09:02,440 --> 00:09:07,330
kita kemudian dapat berjalan melalui pohon dan mengakses kedua node anak -

131
00:09:07,330 --> 00:09:10,630
baik 3 dan 9.

132
00:09:10,630 --> 00:09:14,820
Tidak perlu untuk mempertahankan pointer ke setiap node tunggal pada pohon.

133
00:09:14,820 --> 00:09:22,080
Alright. Sekarang kita akan menambahkan node lain untuk diagram ini.

134
00:09:22,080 --> 00:09:25,370
Kita akan menambahkan node yang mengandung 6,

135
00:09:25,370 --> 00:09:34,140
dan kita akan menambahkan ini sebagai anak kanan dari simpul yang mengandung 3.

136
00:09:34,140 --> 00:09:41,850
Untuk melakukan itu, aku akan menghapus bahwa pointer nol dalam 3-node

137
00:09:41,850 --> 00:09:47,750
dan kawat itu untuk menunjuk ke simpul yang mengandung 6. Alright.

138
00:09:47,750 --> 00:09:53,800
>> Pada titik ini, mari kita membahas sedikit terminologi.

139
00:09:53,800 --> 00:09:58,230
Untuk memulai, alasan bahwa ini disebut pohon biner khususnya

140
00:09:58,230 --> 00:10:00,460
adalah bahwa ia memiliki dua pointer anak.

141
00:10:00,460 --> 00:10:06,020
Ada jenis lain dari pohon yang memiliki pointer anak lagi.

142
00:10:06,020 --> 00:10:10,930
Secara khusus, Anda melakukan 'mencoba' di Set Soal 5.

143
00:10:10,930 --> 00:10:19,310
Anda akan melihat bahwa dalam mencoba itu, Anda memiliki 27 pointer yang berbeda untuk anak-anak yang berbeda -

144
00:10:19,310 --> 00:10:22,410
satu untuk masing-masing dari 26 huruf dalam abjad Inggris,

145
00:10:22,410 --> 00:10:25,410
dan kemudian 27 untuk tanda kutip -

146
00:10:25,410 --> 00:10:28,900
sehingga, yang mirip dengan jenis pohon.

147
00:10:28,900 --> 00:10:34,070
Tapi di sini, karena biner itu, kita hanya memiliki dua pointer anak.

148
00:10:34,070 --> 00:10:37,880
>> Selain ini simpul akar yang kita bicarakan,

149
00:10:37,880 --> 00:10:41,470
kami juga telah melemparkan sekitar istilah 'anak'.

150
00:10:41,470 --> 00:10:44,470
Apa artinya untuk satu node menjadi anak node lain?

151
00:10:44,470 --> 00:10:54,060
Secara harfiah berarti bahwa node anak adalah anak dari node lain

152
00:10:54,060 --> 00:10:58,760
jika node lain memiliki salah satu pointer anaknya diatur untuk menunjuk ke simpul tersebut.

153
00:10:58,760 --> 00:11:01,230
Untuk menempatkan ini ke dalam istilah yang lebih konkret,

154
00:11:01,230 --> 00:11:11,170
jika 3 ditunjukkan oleh salah satu pointer anak 7, maka 3 adalah anak 7.

155
00:11:11,170 --> 00:11:14,510
Jika kita mencari tahu apa anak-anak dari 7 adalah -

156
00:11:14,510 --> 00:11:18,510
baik, kita melihat bahwa 7 memiliki pointer ke 3 dan pointer ke 9,

157
00:11:18,510 --> 00:11:22,190
jadi 9 dan 3 adalah anak-anak 7.

158
00:11:22,190 --> 00:11:26,650
Sembilan tidak memiliki anak karena anaknya pointer adalah null,

159
00:11:26,650 --> 00:11:30,940
dan 3 hanya memiliki satu anak, 6.

160
00:11:30,940 --> 00:11:37,430
Enam juga tidak memiliki anak karena kedua pointer nya adalah null, yang kita akan menarik sekarang.

161
00:11:37,430 --> 00:11:45,010
>> Selain itu, kita juga berbicara tentang orang tua dari node tertentu,

162
00:11:45,010 --> 00:11:51,100
dan ini adalah, seperti yang Anda harapkan, kebalikan dari deskripsi anak.

163
00:11:51,100 --> 00:11:58,620
Setiap node hanya memiliki satu orang tua - bukan dua seperti yang Anda harapkan dengan manusia.

164
00:11:58,620 --> 00:12:03,390
Misalnya, orang tua dari 3 adalah 7.

165
00:12:03,390 --> 00:12:10,800
Orang tua dari 9 juga 7, dan orang tua dari 6 adalah 3. Tidak banyak untuk itu.

166
00:12:10,800 --> 00:12:15,720
Kami juga memiliki istilah untuk berbicara tentang kakek-nenek dan cucu,

167
00:12:15,720 --> 00:12:18,210
dan lebih umumnya kita berbicara tentang nenek moyang

168
00:12:18,210 --> 00:12:20,960
dan keturunan dari node tertentu.

169
00:12:20,960 --> 00:12:25,710
Nenek moyang node - atau nenek moyang, lebih tepatnya, dari node -

170
00:12:25,710 --> 00:12:32,730
adalah semua node yang terletak di jalan dari akar ke simpul tersebut.

171
00:12:32,730 --> 00:12:36,640
Sebagai contoh, jika saya melihat 6 node,

172
00:12:36,640 --> 00:12:46,430
maka leluhur akan menjadi baik 3 dan 7.

173
00:12:46,430 --> 00:12:55,310
Nenek moyang dari 9, misalnya, - jika saya melihat 9 simpul -

174
00:12:55,310 --> 00:12:59,990
maka nenek moyang 9 hanya 7.

175
00:12:59,990 --> 00:13:01,940
Dan keturunan yang persis sebaliknya.

176
00:13:01,940 --> 00:13:05,430
Jika saya ingin melihat semua keturunan 7,

177
00:13:05,430 --> 00:13:11,020
maka saya harus melihat semua node di bawahnya.

178
00:13:11,020 --> 00:13:16,950
Jadi, saya memiliki 3, 9, dan 6 semua sebagai keturunan dari 7.

179
00:13:16,950 --> 00:13:24,170
>> Istilah terakhir yang kita akan berbicara tentang gagasan menjadi saudara kandung.

180
00:13:24,170 --> 00:13:27,980
Saudara - jenis mengikuti dari awal pada istilah-istilah keluarga -

181
00:13:27,980 --> 00:13:33,150
adalah node yang berada pada tingkat yang sama di pohon.

182
00:13:33,150 --> 00:13:42,230
Jadi, 3 dan 9 adalah saudara kandung karena mereka berada pada tingkat yang sama di pohon.

183
00:13:42,230 --> 00:13:46,190
Mereka berdua memiliki induk yang sama, 7.

184
00:13:46,190 --> 00:13:51,400
6 tidak memiliki saudara kandung karena 9 tidak memiliki anak.

185
00:13:51,400 --> 00:13:55,540
Dan 7 tidak memiliki saudara kandung karena akar pohon kita,

186
00:13:55,540 --> 00:13:59,010
dan ada hanya pernah 1 root.

187
00:13:59,010 --> 00:14:02,260
Untuk 7 untuk memiliki saudara di sana harus menjadi simpul di atas 7.

188
00:14:02,260 --> 00:14:07,480
Ada akan menjadi orang tua dari 7, dalam hal ini 7 akan tidak lagi menjadi akar pohon.

189
00:14:07,480 --> 00:14:10,480
Kemudian orang tua baru 7 juga harus memiliki anak,

190
00:14:10,480 --> 00:14:16,480
dan anak yang kemudian akan menjadi saudara dari 7.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Pindah.

192
00:14:21,040 --> 00:14:24,930
Ketika kita mulai diskusi kita dari pohon biner,

193
00:14:24,930 --> 00:14:28,790
kita berbicara tentang bagaimana kami akan menggunakannya untuk

194
00:14:28,790 --> 00:14:32,800
memperoleh keuntungan lebih baik array dan linked list.

195
00:14:32,800 --> 00:14:37,220
Dan cara kita akan melakukannya adalah dengan memesan properti.

196
00:14:37,220 --> 00:14:41,080
Kami mengatakan bahwa sebuah pohon biner yang memerintahkan, sesuai dengan spesifikasi,

197
00:14:41,080 --> 00:14:45,740
jika untuk setiap node di pohon kita, semua keturunannya di sebelah kiri -

198
00:14:45,740 --> 00:14:48,670
anak kiri dan semua keturunan anak kiri -

199
00:14:48,670 --> 00:14:54,510
memiliki nilai yang lebih rendah, dan semua node di sebelah kanan -

200
00:14:54,510 --> 00:14:57,770
anak kanan dan semua keturunan anak kanan itu -

201
00:14:57,770 --> 00:15:02,800
memiliki node lebih besar dari nilai node saat ini bahwa kita sedang melihat.

202
00:15:02,800 --> 00:15:07,850
Hanya untuk kesederhanaan, kita akan berasumsi bahwa tidak ada duplikasi node di pohon kita.

203
00:15:07,850 --> 00:15:11,180
Misalnya, di pohon ini kita tidak akan berurusan dengan kasus

204
00:15:11,180 --> 00:15:13,680
di mana kita memiliki nilai 7 pada akar

205
00:15:13,680 --> 00:15:16,720
 dan kemudian kita juga memiliki nilai 7 tempat lain di pohon.

206
00:15:16,720 --> 00:15:24,390
Dalam hal ini, Anda akan melihat bahwa pohon ini memang diperintahkan.

207
00:15:24,390 --> 00:15:26,510
Kami memiliki nilai 7 pada akar.

208
00:15:26,510 --> 00:15:29,720
Semuanya di sebelah kiri 7 -

209
00:15:29,720 --> 00:15:35,310
jika saya membatalkan semua tanda kecil di sini -

210
00:15:35,310 --> 00:15:40,450
semuanya ke kiri 7 - 3 dan 6 -

211
00:15:40,450 --> 00:15:49,410
nilai-nilai keduanya kurang dari 7, dan semuanya ke kanan - yang hanya 9 ini -

212
00:15:49,410 --> 00:15:53,450
lebih besar dari 7.

213
00:15:53,450 --> 00:15:58,650
>> Ini bukan satu-satunya pohon memerintahkan mengandung nilai-nilai,

214
00:15:58,650 --> 00:16:03,120
tapi mari kita menarik beberapa lagi dari mereka.

215
00:16:03,120 --> 00:16:05,030
Sebenarnya ada sejumlah cara yang bisa kita lakukan ini.

216
00:16:05,030 --> 00:16:09,380
Aku akan menggunakan singkat hanya untuk menjaga hal-hal sederhana di mana -

217
00:16:09,380 --> 00:16:11,520
bukannya menarik keluar seluruh kotak-dan-panah -

218
00:16:11,520 --> 00:16:14,220
Aku hanya akan menarik angka dan menambahkan panah menghubungkan mereka.

219
00:16:14,220 --> 00:16:22,920
Untuk memulai, kita hanya akan menulis pohon asli kami lagi di mana kami memiliki 7, dan kemudian 3,

220
00:16:22,920 --> 00:16:25,590
dan kemudian menunjuk 3 kembali ke kanan ke 6,

221
00:16:25,590 --> 00:16:30,890
dan 7 memiliki anak kanan itu 9.

222
00:16:30,890 --> 00:16:33,860
Alright. Apa cara lain yang kita bisa menulis pohon ini?

223
00:16:33,860 --> 00:16:38,800
Alih-alih memiliki 3 menjadi anak kiri dari 7,

224
00:16:38,800 --> 00:16:41,360
kita juga bisa memiliki 6 menjadi anak kiri dari 7,

225
00:16:41,360 --> 00:16:44,470
dan kemudian 3 menjadi anak kiri dari 6.

226
00:16:44,470 --> 00:16:48,520
Itu akan terlihat seperti pohon ini di sini di mana saya punya 7,

227
00:16:48,520 --> 00:16:57,860
kemudian 6, kemudian 3, dan 9 di sebelah kanan.

228
00:16:57,860 --> 00:17:01,490
Kami juga tidak harus memiliki 7 sebagai simpul akar kami.

229
00:17:01,490 --> 00:17:03,860
Kita juga bisa memiliki 6 sebagai simpul akar kami.

230
00:17:03,860 --> 00:17:06,470
Apa yang akan terlihat seperti?

231
00:17:06,470 --> 00:17:09,230
Jika kita akan mempertahankan properti memerintahkan,

232
00:17:09,230 --> 00:17:12,970
semuanya ke kiri dari 6 harus kurang dari itu.

233
00:17:12,970 --> 00:17:16,540
Hanya ada satu kemungkinan, dan itu 3.

234
00:17:16,540 --> 00:17:19,869
Tapi kemudian sebagai anak kanan dari 6, kita memiliki dua kemungkinan.

235
00:17:19,869 --> 00:17:25,380
Pertama, kita bisa memiliki 7 dan kemudian 9,

236
00:17:25,380 --> 00:17:28,850
atau kita bisa menggambar - seperti aku akan lakukan di sini -

237
00:17:28,850 --> 00:17:34,790
di mana kita memiliki 9 sebagai anak kanan dari 6,

238
00:17:34,790 --> 00:17:39,050
dan kemudian 7 sebagai anak kiri 9.

239
00:17:39,050 --> 00:17:44,240
>> Sekarang, 7 dan 6 adalah bukan nilai-nilai hanya mungkin untuk root.

240
00:17:44,240 --> 00:17:50,200
Kita juga bisa memiliki 3 berada di akar.

241
00:17:50,200 --> 00:17:52,240
Apa yang terjadi jika 3 adalah pada akar?

242
00:17:52,240 --> 00:17:54,390
Di sini, hal mendapatkan sedikit menarik.

243
00:17:54,390 --> 00:17:58,440
Tiga tidak memiliki nilai-nilai yang kurang dari itu,

244
00:17:58,440 --> 00:18:02,070
sehingga sisi kiri seluruh pohon itu hanya akan menjadi nol.

245
00:18:02,070 --> 00:18:03,230
Ada tidak akan menjadi apa pun di sana.

246
00:18:03,230 --> 00:18:07,220
Ke kanan, kita bisa daftar hal-hal dalam urutan.

247
00:18:07,220 --> 00:18:15,530
Kita bisa memiliki 3, kemudian 6, kemudian 7, kemudian 9.

248
00:18:15,530 --> 00:18:26,710
Atau, kita bisa melakukan 3, kemudian 6, kemudian 9, kemudian 7.

249
00:18:26,710 --> 00:18:35,020
Atau, kita bisa melakukan 3, kemudian 7, kemudian 6, kemudian 9.

250
00:18:35,020 --> 00:18:40,950
Atau, 3, 7 - sebenarnya tidak ada, kita tidak bisa melakukan lagi 7.

251
00:18:40,950 --> 00:18:43,330
Itulah salah satu hal yang kami di sana.

252
00:18:43,330 --> 00:18:54,710
Kita bisa melakukan 9, dan kemudian dari 9 bisa kita lakukan dan kemudian 6 7.

253
00:18:54,710 --> 00:19:06,980
Atau, kita bisa melakukan 3, kemudian 9, kemudian 7, dan kemudian 6.

254
00:19:06,980 --> 00:19:12,490
>> Satu hal yang menarik perhatian Anda ke sini adalah

255
00:19:12,490 --> 00:19:14,510
bahwa pohon-pohon yang sedikit aneh yang tampak.

256
00:19:14,510 --> 00:19:17,840
Secara khusus, jika kita melihat pada 4 pohon di sisi kanan -

257
00:19:17,840 --> 00:19:20,930
Saya akan mengitarinya, di sini -

258
00:19:20,930 --> 00:19:28,410
pohon-pohon ini terlihat hampir persis seperti linked list.

259
00:19:28,410 --> 00:19:32,670
Setiap node hanya memiliki satu anak,

260
00:19:32,670 --> 00:19:38,950
dan jadi kita tidak memiliki salah satu dari ini struktur pohon seperti yang kita lihat, misalnya,

261
00:19:38,950 --> 00:19:44,720
 di pohon satu satunya di sini di sebelah kiri bawah.

262
00:19:44,720 --> 00:19:52,490
Pohon-pohon ini sebenarnya disebut merosot pohon biner,

263
00:19:52,490 --> 00:19:54,170
dan kita akan berbicara tentang ini lebih di masa depan -

264
00:19:54,170 --> 00:19:56,730
terutama jika Anda pergi untuk mengambil kursus ilmu komputer lainnya.

265
00:19:56,730 --> 00:19:59,670
Pohon-pohon ini merosot.

266
00:19:59,670 --> 00:20:03,780
Mereka tidak sangat berguna karena, memang, struktur ini cocok

267
00:20:03,780 --> 00:20:08,060
 untuk pencarian kali mirip dengan linked list.

268
00:20:08,060 --> 00:20:13,050
Kami tidak bisa mengambil keuntungan dari memori tambahan - ini pointer ekstra -

269
00:20:13,050 --> 00:20:18,840
karena struktur kami yang buruk dengan cara ini.

270
00:20:18,840 --> 00:20:24,700
Daripada pergi dan menarik keluar pohon biner yang memiliki 9 pada akar,

271
00:20:24,700 --> 00:20:27,220
yang merupakan kasus terakhir yang kita akan memiliki,

272
00:20:27,220 --> 00:20:32,380
kita sebaliknya, pada saat ini, akan berbicara sedikit tentang istilah lainnya

273
00:20:32,380 --> 00:20:36,150
yang kita gunakan ketika berbicara tentang pohon, yang disebut ketinggian.

274
00:20:36,150 --> 00:20:45,460
>> Ketinggian pohon adalah jarak dari akar ke simpul paling-jauh,

275
00:20:45,460 --> 00:20:48,370
atau lebih tepatnya jumlah hop yang akan Anda harus membuat dalam rangka

276
00:20:48,370 --> 00:20:53,750
mulai dari akar dan kemudian berakhir di node paling jauh di pohon.

277
00:20:53,750 --> 00:20:57,330
Jika kita melihat beberapa pohon yang kita telah ditarik di sini,

278
00:20:57,330 --> 00:21:07,870
kita dapat melihat bahwa jika kita mengambil pohon ini di sudut kiri atas dan kita mulai pada 3,

279
00:21:07,870 --> 00:21:14,510
maka kita harus membuat 1 hop untuk sampai ke 6, sebuah hop kedua untuk sampai ke 7,

280
00:21:14,510 --> 00:21:20,560
dan hop ketiga untuk sampai ke 9.

281
00:21:20,560 --> 00:21:26,120
Jadi, ketinggian pohon ini adalah 3.

282
00:21:26,120 --> 00:21:30,640
Kita bisa melakukan latihan yang sama untuk pohon lain diuraikan dengan hijau ini,

283
00:21:30,640 --> 00:21:40,100
dan kita melihat bahwa tinggi dari semua pohon juga memang 3.

284
00:21:40,100 --> 00:21:45,230
Itu bagian dari apa yang membuat mereka merosot -

285
00:21:45,230 --> 00:21:53,750
bahwa tinggi mereka hanya satu kurang dari jumlah node di seluruh pohon.

286
00:21:53,750 --> 00:21:58,400
Jika kita melihat pohon lain yang dikelilingi dengan merah, di sisi lain,

287
00:21:58,400 --> 00:22:03,920
kita melihat bahwa yang paling jauh-node daun adalah 6 dan 9 -

288
00:22:03,920 --> 00:22:06,940
daun menjadi orang node yang tidak memiliki anak.

289
00:22:06,940 --> 00:22:11,760
Jadi, dalam rangka untuk mendapatkan dari node root baik 6 atau 9,

290
00:22:11,760 --> 00:22:17,840
kita harus membuat satu hop untuk sampai ke 7 dan kemudian hop kedua untuk sampai ke 9,

291
00:22:17,840 --> 00:22:21,240
dan juga, hanya hop kedua dari 7 untuk sampai ke 6.

292
00:22:21,240 --> 00:22:29,080
Jadi, ketinggian pohon ini di sini hanya 2.

293
00:22:29,080 --> 00:22:35,330
Anda dapat kembali dan melakukan itu untuk semua pohon-pohon lain yang kita bahas sebelumnya

294
00:22:35,330 --> 00:22:37,380
dimulai dengan 7 dan 6,

295
00:22:37,480 --> 00:22:42,500
dan Anda akan menemukan bahwa tinggi dari semua pohon-pohon juga 2.

296
00:22:42,500 --> 00:22:46,320
>> Alasan kami telah berbicara tentang memerintahkan pohon biner

297
00:22:46,320 --> 00:22:50,250
dan mengapa mereka keren karena Anda dapat mencari melalui mereka dalam

298
00:22:50,250 --> 00:22:53,810
cara yang sangat mirip dengan mencari lebih dari array diurutkan.

299
00:22:53,810 --> 00:22:58,720
Di sinilah kita berbicara tentang mendapatkan bahwa waktu pencarian ditingkatkan

300
00:22:58,720 --> 00:23:02,730
atas linked list sederhana.

301
00:23:02,730 --> 00:23:05,010
Dengan linked list - jika Anda ingin mencari elemen tertentu -

302
00:23:05,010 --> 00:23:07,470
Anda terbaik akan melakukan semacam pencarian linear

303
00:23:07,470 --> 00:23:10,920
di mana Anda mulai pada awal daftar dan hop satu-per-satu -

304
00:23:10,920 --> 00:23:12,620
satu node oleh satu node -

305
00:23:12,620 --> 00:23:16,060
melalui seluruh daftar sampai Anda menemukan apa pun yang Anda cari.

306
00:23:16,060 --> 00:23:19,440
Sedangkan, jika Anda memiliki sebuah pohon biner yang disimpan dalam format yang bagus,

307
00:23:19,440 --> 00:23:23,300
Anda benar-benar bisa mendapatkan lebih dari pencarian biner terjadi

308
00:23:23,300 --> 00:23:25,160
di mana Anda membagi dan menaklukkan

309
00:23:25,160 --> 00:23:29,490
dan pencarian melalui paruh tepat pohon di setiap langkah.

310
00:23:29,490 --> 00:23:32,840
Mari kita lihat bagaimana yang bekerja.

311
00:23:32,840 --> 00:23:38,850
>> Jika kita memiliki - lagi, akan kembali ke pohon asli kami -

312
00:23:38,850 --> 00:23:46,710
kita mulai pada 7, kami memiliki 3 di sebelah kiri, 9 di sebelah kanan,

313
00:23:46,710 --> 00:23:51,740
dan di bawah 3 yang kita miliki 6 tersebut.

314
00:23:51,740 --> 00:24:01,880
Jika kita ingin mencari nomor 6 di pohon ini, kita akan mulai dari akar.

315
00:24:01,880 --> 00:24:08,910
Kami akan membandingkan nilai yang kita cari, katakanlah 6,

316
00:24:08,910 --> 00:24:12,320
dengan nilai yang tersimpan dalam simpul yang kita sedang melihat, 7,

317
00:24:12,320 --> 00:24:21,200
menemukan bahwa 6 memang kurang dari 7, jadi kita akan bergerak ke kiri.

318
00:24:21,200 --> 00:24:25,530
Jika nilai 6 sudah lebih besar dari 7, kita akan sebaliknya pindah ke kanan.

319
00:24:25,530 --> 00:24:29,770
Karena kita tahu bahwa - karena struktur pohon biner memerintahkan kita -

320
00:24:29,770 --> 00:24:33,910
semua nilai kurang dari 7 akan disimpan di sebelah kiri 7,

321
00:24:33,910 --> 00:24:40,520
ada tidak perlu repot-repot mencari melalui sisi kanan pohon.

322
00:24:40,520 --> 00:24:43,780
Setelah kita bergerak ke kiri dan kami sekarang di node mengandung 3,

323
00:24:43,780 --> 00:24:48,110
kita bisa melakukan itu perbandingan yang sama lagi di mana kita membandingkan 3 dan 6.

324
00:24:48,110 --> 00:24:52,430
Dan kita menemukan bahwa sementara 6 - nilai yang kita cari - lebih besar dari 3,

325
00:24:52,430 --> 00:24:58,580
kita bisa pergi ke sisi kanan dari node yang mengandung 3.

326
00:24:58,580 --> 00:25:02,670
Tidak ada sisi kiri di sini, jadi kita bisa mengabaikan itu.

327
00:25:02,670 --> 00:25:06,510
Tapi kita hanya tahu bahwa karena kita sedang melihat pohon itu sendiri,

328
00:25:06,510 --> 00:25:08,660
dan kita dapat melihat bahwa pohon itu tidak memiliki anak.

329
00:25:08,660 --> 00:25:13,640
>> Hal ini juga cukup mudah untuk mencari 6 di pohon ini jika kita melakukannya diri sebagai manusia,

330
00:25:13,640 --> 00:25:16,890
tapi mari kita ikuti proses ini mekanis seperti komputer akan melakukan

331
00:25:16,890 --> 00:25:18,620
untuk benar-benar memahami algoritma.

332
00:25:18,620 --> 00:25:26,200
Pada titik ini, kita sekarang melihat sebuah simpul yang berisi 6,

333
00:25:26,200 --> 00:25:29,180
dan kami sedang mencari nilai 6,

334
00:25:29,180 --> 00:25:31,740
jadi, memang, kami telah menemukan simpul yang tepat.

335
00:25:31,740 --> 00:25:35,070
Kami menemukan nilai 6 di pohon kita, dan kita dapat menghentikan pencarian kami.

336
00:25:35,070 --> 00:25:37,330
Pada titik ini, tergantung pada apa yang terjadi,

337
00:25:37,330 --> 00:25:41,870
kita dapat mengatakan, ya, kami telah menemukan nilai 6, itu ada di pohon kami.

338
00:25:41,870 --> 00:25:47,640
Atau, jika kita berencana untuk memasukkan node atau melakukan sesuatu, kita bisa melakukan itu pada saat ini.

339
00:25:47,640 --> 00:25:53,010
>> Mari kita melakukan pencarian beberapa lebih hanya untuk melihat bagaimana ini bekerja.

340
00:25:53,010 --> 00:25:59,390
Mari kita lihat apa yang terjadi jika kita mencoba dan mencari nilai 10.

341
00:25:59,390 --> 00:26:02,970
Jika kita melihat ke atas nilai 10, kita akan mulai dari akar.

342
00:26:02,970 --> 00:26:07,070
Kita akan melihat bahwa 10 lebih besar dari 7, jadi kita akan bergerak ke kanan.

343
00:26:07,070 --> 00:26:13,640
Kita akan sampai ke 9 dan membandingkan 9 ke 10 dan melihat bahwa 9 memang kurang dari 10.

344
00:26:13,640 --> 00:26:16,210
Jadi sekali lagi, kita akan mencoba untuk bergerak ke kanan.

345
00:26:16,210 --> 00:26:20,350
Tapi pada titik ini, kita akan melihat bahwa kita berada di node null.

346
00:26:20,350 --> 00:26:23,080
Ada apa di sana. Tidak ada di mana 10 seharusnya.

347
00:26:23,080 --> 00:26:29,360
Di sinilah kita dapat melaporkan kegagalan - bahwa memang tidak 10 di atas pohon.

348
00:26:29,360 --> 00:26:35,420
Dan akhirnya, mari kita pergi melalui kasus di mana kita berusaha untuk mencari 1 di pohon.

349
00:26:35,420 --> 00:26:38,790
Hal ini mirip dengan apa yang terjadi jika kita melihat ke atas 10, kecuali bukannya pergi ke kanan,

350
00:26:38,790 --> 00:26:41,260
kita akan pergi ke kiri.

351
00:26:41,260 --> 00:26:46,170
Kita mulai di 7 dan melihat bahwa 1 adalah kurang dari 7, jadi kita bergerak ke kiri.

352
00:26:46,170 --> 00:26:51,750
Kami sampai ke 3 dan melihat bahwa 1 adalah kurang dari 3, sehingga sekali lagi kita mencoba untuk bergerak ke kiri.

353
00:26:51,750 --> 00:26:59,080
Pada titik ini kita memiliki node nol, sehingga sekali lagi kita dapat melaporkan kegagalan.

354
00:26:59,080 --> 00:27:10,260
>> Jika Anda ingin mempelajari lebih lanjut tentang pohon biner,

355
00:27:10,260 --> 00:27:14,420
ada sejumlah besar masalah kecil menyenangkan yang dapat Anda lakukan dengan mereka.

356
00:27:14,420 --> 00:27:19,450
Saya sarankan berlatih gambar keluar dari diagram ini satu-per-satu

357
00:27:19,450 --> 00:27:21,910
dan mengikuti melalui semua langkah-langkah yang berbeda,

358
00:27:21,910 --> 00:27:25,060
karena ini akan datang di super-handy

359
00:27:25,060 --> 00:27:27,480
tidak hanya ketika Anda melakukan set Huffman encoding masalah

360
00:27:27,480 --> 00:27:29,390
tetapi juga dalam program masa depan -

361
00:27:29,390 --> 00:27:32,220
hanya belajar bagaimana untuk menarik keluar struktur data dan berpikir melalui masalah

362
00:27:32,220 --> 00:27:38,000
dengan pena dan kertas atau, dalam hal ini, iPad dan stylus.

363
00:27:38,000 --> 00:27:41,000
>> Pada titik ini meskipun, kita akan melanjutkan untuk melakukan beberapa latihan coding

364
00:27:41,000 --> 00:27:44,870
dan benar-benar bermain dengan pohon-pohon biner dan melihat.

365
00:27:44,870 --> 00:27:52,150
Aku akan beralih kembali ke komputer saya.

366
00:27:52,150 --> 00:27:58,480
Untuk ini bagian dari bagian, daripada menggunakan CS50 CS50 Run atau Spaces,

367
00:27:58,480 --> 00:28:01,500
Aku akan menggunakan alat.

368
00:28:01,500 --> 00:28:04,950
>> Setelah bersama dengan spesifikasi Set Soal,

369
00:28:04,950 --> 00:28:07,740
Saya melihat bahwa aku harus membuka alat,

370
00:28:07,740 --> 00:28:11,020
pergi ke folder Dropbox saya, membuat folder bernama Bagian 7,

371
00:28:11,020 --> 00:28:15,730
dan kemudian membuat sebuah file yang bernama binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Di sini kita pergi. Aku punya alat sudah terbuka.

373
00:28:22,050 --> 00:28:25,910
Aku akan menarik terminal.

374
00:28:25,910 --> 00:28:38,250
Aku akan pergi ke folder Dropbox, membuat direktori bernama section7,

375
00:28:38,250 --> 00:28:42,230
dan melihat itu benar-benar kosong.

376
00:28:42,230 --> 00:28:48,860
Sekarang aku akan membuka binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Di sini kita pergi - file kosong.

378
00:28:51,750 --> 00:28:54,330
>> Mari kita kembali ke spesifikasi.

379
00:28:54,330 --> 00:28:59,850
Spesifikasi meminta untuk membuat definisi tipe baru

380
00:28:59,850 --> 00:29:03,080
untuk simpul pohon biner yang mengandung nilai-nilai int -

381
00:29:03,080 --> 00:29:07,110
seperti nilai-nilai yang kita menarik dalam diagram kami sebelum.

382
00:29:07,110 --> 00:29:11,740
Kita akan menggunakan boilerplate ini typedef yang kita lakukan di sini

383
00:29:11,740 --> 00:29:14,420
bahwa Anda harus mengenali dari Set Soal 5 -

384
00:29:14,420 --> 00:29:19,190
jika Anda melakukan cara tabel hash dari menaklukkan program ejaan.

385
00:29:19,190 --> 00:29:22,540
Anda juga harus mengenalinya dari bagian minggu lalu

386
00:29:22,540 --> 00:29:23,890
di mana kita berbicara tentang daftar terhubung.

387
00:29:23,890 --> 00:29:27,870
Kami telah mendapat typedef dari node struct,

388
00:29:27,870 --> 00:29:34,430
dan kami telah memberikan node ini struct ini nama node struct sebelumnya

389
00:29:34,430 --> 00:29:39,350
sehingga kita kemudian dapat merujuk ke sana karena kita akan ingin memiliki pointer struct simpul

390
00:29:39,350 --> 00:29:45,740
sebagai bagian dari struct kami, tapi kami sudah dikelilingi kemudian ini -

391
00:29:45,740 --> 00:29:47,700
atau lebih tepatnya, terlampir ini - dalam typedef

392
00:29:47,700 --> 00:29:54,600
sehingga, kemudian dalam kode, kita bisa merujuk pada struct ini hanya sebagai simpul bukan node struct.

393
00:29:54,600 --> 00:30:03,120
>> Ini akan menjadi sangat mirip dengan daftar definisi sendiri-linked yang kita lihat minggu lalu.

394
00:30:03,120 --> 00:30:20,070
Untuk melakukan hal ini, mari kita mulai dengan menuliskan boilerplate tersebut.

395
00:30:20,070 --> 00:30:23,840
Kita tahu bahwa kita harus memiliki nilai integer,

396
00:30:23,840 --> 00:30:32,170
jadi kita akan dimasukkan ke dalam nilai int, dan kemudian bukan hanya memiliki satu pointer ke elemen berikutnya -

397
00:30:32,170 --> 00:30:33,970
seperti yang kita lakukan dengan sendiri-linked list -

398
00:30:33,970 --> 00:30:38,110
kita akan memiliki pointer anak kiri dan kanan.

399
00:30:38,110 --> 00:30:42,880
Itu juga cukup sederhana - struct node anak * kiri;

400
00:30:42,880 --> 00:30:51,190
dan struct node anak * benar;. Cool.

401
00:30:51,190 --> 00:30:54,740
Yang tampak seperti awal yang cukup bagus.

402
00:30:54,740 --> 00:30:58,530
Mari kita kembali ke spesifikasi.

403
00:30:58,530 --> 00:31:05,030
>> Sekarang kita perlu mendeklarasikan variabel simpul * global untuk akar pohon.

404
00:31:05,030 --> 00:31:10,590
Kita akan membuat ini global yang sama seperti kami membuat pointer pertama dalam daftar kami terkait juga global.

405
00:31:10,590 --> 00:31:12,690
Ini adalah sehingga dalam fungsi yang kita tulis

406
00:31:12,690 --> 00:31:16,180
kita tidak harus tetap lewat di sekitar akar ini -

407
00:31:16,180 --> 00:31:19,620
meskipun kita akan melihat bahwa jika Anda ingin menulis fungsi rekursif,

408
00:31:19,620 --> 00:31:22,830
mungkin lebih baik untuk tidak bahkan lulus sekitar sebagai global di tempat pertama

409
00:31:22,830 --> 00:31:28,090
dan bukannya menginisialisasi secara lokal dalam fungsi utama Anda.

410
00:31:28,090 --> 00:31:31,960
Tapi, kami akan melakukannya secara global untuk memulai.

411
00:31:31,960 --> 00:31:39,920
Sekali lagi, kami akan memberikan beberapa ruang, dan aku akan menyatakan akar * simpul.

412
00:31:39,920 --> 00:31:46,770
Hanya untuk memastikan bahwa saya tidak meninggalkan uninitialized, aku akan mengatur itu sama dengan nol.

413
00:31:46,770 --> 00:31:52,210
Sekarang, dalam fungsi utama - yang kita akan menulis sangat cepat di sini -

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

415
00:32:00,450 --> 00:32:10,640
dan aku akan mulai mendeklarasikan array argv saya sebagai const hanya agar saya tahu

416
00:32:10,640 --> 00:32:14,550
bahwa mereka argumen argumen bahwa aku mungkin tidak ingin mengubah.

417
00:32:14,550 --> 00:32:18,390
Jika saya ingin memodifikasi mereka aku mungkin harus membuat salinan dari mereka.

418
00:32:18,390 --> 00:32:21,740
Anda akan melihat ini banyak dalam kode.

419
00:32:21,740 --> 00:32:25,440
Tidak apa-apa baik cara. Tidak apa-apa untuk meninggalkan sebagai - menghilangkan const jika Anda ingin.

420
00:32:25,440 --> 00:32:28,630
Saya biasanya memasukkannya ke dalam hanya agar saya mengingatkan diri sendiri

421
00:32:28,630 --> 00:32:33,650
 bahwa saya mungkin tidak ingin memodifikasi argumen-argumen.

422
00:32:33,650 --> 00:32:39,240
>> Seperti biasa, aku akan kembali untuk memasukkan baris 0 pada akhir utama.

423
00:32:39,240 --> 00:32:45,730
Di sini, saya akan menginisialisasi simpul akar saya.

424
00:32:45,730 --> 00:32:48,900
Seperti berdiri sekarang, aku punya pointer yang diatur ke nol,

425
00:32:48,900 --> 00:32:52,970
sehingga itu menunjuk pada apa-apa.

426
00:32:52,970 --> 00:32:57,480
Dalam rangka untuk benar-benar mulai membangun node,

427
00:32:57,480 --> 00:32:59,250
Saya pertama kali perlu mengalokasikan memori untuk itu.

428
00:32:59,250 --> 00:33:05,910
Aku akan melakukannya dengan membuat memori di heap menggunakan malloc.

429
00:33:05,910 --> 00:33:10,660
Aku akan mengatur akar sama dengan hasil dari malloc,

430
00:33:10,660 --> 00:33:19,550
dan aku akan menggunakan operator sizeof untuk menghitung ukuran node.

431
00:33:19,550 --> 00:33:24,990
Alasan yang saya gunakan simpul sizeof sebagai lawan, mengatakan,

432
00:33:24,990 --> 00:33:37,020
melakukan sesuatu seperti ini - malloc (4 + 4 +4) atau malloc 12 -

433
00:33:37,020 --> 00:33:40,820
karena saya ingin kode saya untuk menjadi seperti yang kompatibel mungkin.

434
00:33:40,820 --> 00:33:44,540
Saya ingin bisa mengambil file ini. C, kompilasi pada alat,

435
00:33:44,540 --> 00:33:48,820
dan kemudian kompilasi pada 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
atau pada arsitektur yang sama sekali berbeda -

437
00:33:52,040 --> 00:33:54,640
dan saya ingin semua ini untuk bekerja sama.

438
00:33:54,640 --> 00:33:59,510
>> Jika saya membuat asumsi tentang ukuran variabel -

439
00:33:59,510 --> 00:34:02,070
ukuran int atau ukuran pointer -

440
00:34:02,070 --> 00:34:06,070
maka aku juga membuat asumsi tentang jenis arsitektur

441
00:34:06,070 --> 00:34:10,440
di mana kode saya berhasil dapat mengkompilasi ketika dijalankan.

442
00:34:10,440 --> 00:34:15,030
Selalu gunakan sizeof sebagai lawan manual menjumlahkan bidang struct.

443
00:34:15,030 --> 00:34:20,500
Alasan lain adalah bahwa ada juga mungkin bantalan bahwa kompilator menempatkan ke struct.

444
00:34:20,500 --> 00:34:26,570
Bahkan hanya menjumlahkan bidang individu bukanlah sesuatu yang Anda biasanya ingin lakukan,

445
00:34:26,570 --> 00:34:30,340
ya, hapus baris tersebut.

446
00:34:30,340 --> 00:34:33,090
Sekarang, untuk benar-benar menginisialisasi ini node root,

447
00:34:33,090 --> 00:34:36,489
Aku akan harus memasukkan nilai untuk masing-masing bidang yang berbeda.

448
00:34:36,489 --> 00:34:41,400
Misalnya, untuk nilai aku tahu aku ingin menginisialisasi ke 7,

449
00:34:41,400 --> 00:34:46,920
dan untuk saat ini aku akan mengatur anak kiri menjadi nol

450
00:34:46,920 --> 00:34:55,820
dan anak kanan juga menjadi nol. Great!

451
00:34:55,820 --> 00:35:02,670
Kami telah melakukan itu bagian dari spec.

452
00:35:02,670 --> 00:35:07,390
>> Spesifikasi turun di bagian bawah halaman 3 meminta saya untuk membuat tiga node -

453
00:35:07,390 --> 00:35:10,600
satu berisi 3, satu berisi 6, dan satu dengan 9 -

454
00:35:10,600 --> 00:35:14,210
dan kemudian kawat mereka sehingga terlihat persis seperti diagram pohon kita

455
00:35:14,210 --> 00:35:17,120
yang kita bicarakan sebelumnya.

456
00:35:17,120 --> 00:35:20,450
Mari kita lakukan itu cukup cepat di sini.

457
00:35:20,450 --> 00:35:26,270
Anda akan melihat benar-benar cepat bahwa aku akan mulai menulis sekelompok kode duplikat.

458
00:35:26,270 --> 00:35:32,100
Aku akan membuat * node dan aku akan menyebutnya tiga.

459
00:35:32,100 --> 00:35:36,000
Aku akan mengaturnya sama dengan malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Aku akan menetapkan tiga-> value = 3.

461
00:35:41,070 --> 00:35:54,780
Tiga -> left_child = NULL; tiga -> tepat _child = NULL; juga.

462
00:35:54,780 --> 00:36:01,150
Itu terlihat sangat mirip dengan menginisialisasi akar, dan itulah yang

463
00:36:01,150 --> 00:36:05,760
Aku akan lakukan jika saya mulai menginisialisasi 6 dan 9 juga.

464
00:36:05,760 --> 00:36:20,720
Saya akan melakukan yang benar-benar cepat di sini - sebenarnya, aku akan melakukan copy dan paste sedikit,

465
00:36:20,720 --> 00:36:46,140
dan memastikan bahwa saya - baik-baik saja.

466
00:36:46,470 --> 00:37:09,900
 Sekarang, saya sudah mendapatkannya disalin dan aku bisa pergi ke depan dan mengatur ini sama dengan 6.

467
00:37:09,900 --> 00:37:14,670
Anda dapat melihat bahwa ini mengambil beberapa waktu dan tidak super-efisien.

468
00:37:14,670 --> 00:37:22,610
Dalam hanya sedikit, kita akan menulis fungsi yang akan melakukan hal ini untuk kita.

469
00:37:22,610 --> 00:37:32,890
Saya ingin mengganti ini dengan 9, menggantikan dengan 6.

470
00:37:32,890 --> 00:37:37,360
>> Sekarang kita punya semua node kami dibuat dan diinisialisasi.

471
00:37:37,360 --> 00:37:41,200
Kami punya root ditetapkan sama dengan 7, atau mengandung nilai 7,

472
00:37:41,200 --> 00:37:46,510
kami simpul yang mengandung 3, simpul kami mengandung 6, dan simpul kami mengandung 9.

473
00:37:46,510 --> 00:37:50,390
Pada titik ini, yang harus kita lakukan adalah kawat semuanya.

474
00:37:50,390 --> 00:37:53,020
Alasan saya diinisialisasi semua pointer ke null hanya sehingga saya memastikan bahwa

475
00:37:53,020 --> 00:37:56,260
Saya tidak memiliki pointer uninitialized di sana oleh kecelakaan.

476
00:37:56,260 --> 00:38:02,290
Dan juga karena, pada saat ini, saya hanya harus benar-benar menghubungkan node satu sama lain -

477
00:38:02,290 --> 00:38:04,750
kepada orang-orang yang mereka benar-benar terhubung ke - Saya tidak harus melalui dan membuat

478
00:38:04,750 --> 00:38:08,240
Pastikan bahwa semua nulls berada di sana di tempat yang tepat.

479
00:38:08,240 --> 00:38:15,630
>> Mulai dari akar, saya tahu bahwa anak kiri akar adalah 3.

480
00:38:15,630 --> 00:38:21,250
Saya tahu bahwa anak kanan akar adalah 9.

481
00:38:21,250 --> 00:38:24,880
Setelah itu, satu-satunya anak lain yang saya telah meninggalkan khawatir tentang

482
00:38:24,880 --> 00:38:39,080
adalah anak kanan 3, yang adalah 6.

483
00:38:39,080 --> 00:38:44,670
Pada titik ini, semua terlihat cukup bagus.

484
00:38:44,670 --> 00:38:54,210
Kami akan menghapus beberapa baris.

485
00:38:54,210 --> 00:38:59,540
Sekarang semuanya terlihat cukup bagus.

486
00:38:59,540 --> 00:39:04,240
Mari kita kembali ke spesifikasi kami dan melihat apa yang harus kita lakukan selanjutnya.

487
00:39:04,240 --> 00:39:07,610
>> Pada titik ini, kita harus menulis sebuah fungsi yang disebut 'berisi'

488
00:39:07,610 --> 00:39:14,150
dengan prototipe dari 'dikandungnya bool (int value)'.

489
00:39:14,150 --> 00:39:17,060
Dan ini mengandung fungsi akan kembali benar

490
00:39:17,060 --> 00:39:21,200
 jika pohon yang ditunjuk oleh variabel akar global kami

491
00:39:21,200 --> 00:39:26,950
 mengandung nilai dilewatkan ke fungsi dan palsu sebaliknya.

492
00:39:26,950 --> 00:39:29,000
Mari kita pergi ke depan dan melakukan itu.

493
00:39:29,000 --> 00:39:35,380
Ini akan menjadi persis seperti pencarian yang kita lakukan dengan tangan pada iPad hanya sedikit lalu.

494
00:39:35,380 --> 00:39:40,130
Mari kita tampilannya kembali dalam sedikit dan gulir ke atas.

495
00:39:40,130 --> 00:39:43,130
Kita akan menempatkan fungsi ini tepat di atas fungsi utama kami

496
00:39:43,130 --> 00:39:48,990
sehingga kita tidak perlu melakukan apapun prototyping.

497
00:39:48,990 --> 00:39:55,960
Jadi, bool mengandung (int value).

498
00:39:55,960 --> 00:40:00,330
Di sana kami pergi. Ada deklarasi boilerplate kami.

499
00:40:00,330 --> 00:40:02,900
Hanya untuk memastikan bahwa ini akan mengkompilasi,

500
00:40:02,900 --> 00:40:06,820
Aku akan pergi ke depan dan hanya mengatur itu sama dengan return false.

501
00:40:06,820 --> 00:40:09,980
Saat fungsi ini tidak akan melakukan apa-apa dan selalu melaporkan bahwa

502
00:40:09,980 --> 00:40:14,010
nilai yang kita cari tidak ada di dalam pohon.

503
00:40:14,010 --> 00:40:16,280
>> Pada titik ini, itu mungkin ide yang baik -

504
00:40:16,280 --> 00:40:19,600
karena kita telah menulis sejumlah kode dan kami bahkan belum mencoba mengujinya belum -

505
00:40:19,600 --> 00:40:22,590
untuk memastikan bahwa semuanya mengkompilasi.

506
00:40:22,590 --> 00:40:27,460
Ada beberapa hal yang harus kita lakukan untuk memastikan bahwa ini benar-benar akan mengkompilasi.

507
00:40:27,460 --> 00:40:33,530
Pertama, melihat apakah kita telah menggunakan fungsi-fungsi dalam perpustakaan yang kita belum disertakan.

508
00:40:33,530 --> 00:40:37,940
Fungsi kami telah digunakan sejauh ini malloc,

509
00:40:37,940 --> 00:40:43,310
dan kemudian kita juga telah menggunakan jenis ini - jenis ini tidak standar yang disebut 'bool' -

510
00:40:43,310 --> 00:40:45,750
yang termasuk dalam file header standar bool.

511
00:40:45,750 --> 00:40:53,250
Kita pasti ingin memasukkan bool.h standar untuk tipe bool,

512
00:40:53,250 --> 00:40:59,230
dan kami juga ingin # include lib.h standar untuk perpustakaan standar

513
00:40:59,230 --> 00:41:03,530
yang mencakup malloc, dan bebas, dan semua itu.

514
00:41:03,530 --> 00:41:08,660
Jadi, zoom out, kita akan berhenti.

515
00:41:08,660 --> 00:41:14,190
Mari kita mencoba dan memastikan bahwa ini benar-benar melakukan kompilasi.

516
00:41:14,190 --> 00:41:18,150
Kita melihat bahwa hal itu, jadi kami berada di jalur yang benar.

517
00:41:18,150 --> 00:41:22,990
>> Mari kita membuka binary_tree.c lagi.

518
00:41:22,990 --> 00:41:34,530
Ini mengkompilasi. Mari kita turun dan memastikan bahwa kami memasukkan beberapa panggilan ke fungsi yang dikandungnya kami -

519
00:41:34,530 --> 00:41:40,130
hanya untuk memastikan bahwa itu semua baik dan bagus.

520
00:41:40,130 --> 00:41:43,170
Sebagai contoh, ketika kita melakukan beberapa pencarian di pohon kami sebelumnya,

521
00:41:43,170 --> 00:41:48,500
kami mencoba untuk mencari nilai-nilai 6, 10, dan 1, dan kita tahu bahwa 6 berada di pohon,

522
00:41:48,500 --> 00:41:52,220
10 tidak di pohon, dan 1 tidak di pohon baik.

523
00:41:52,220 --> 00:41:57,230
Mari kita menggunakan panggilan sampel tersebut sebagai cara untuk mengetahui apakah atau tidak

524
00:41:57,230 --> 00:41:59,880
dikandungnya fungsi kita bekerja.

525
00:41:59,880 --> 00:42:05,210
Untuk melakukan itu, saya akan menggunakan fungsi printf,

526
00:42:05,210 --> 00:42:10,280
dan kita akan mencetak hasil dari panggilan untuk mengandung.

527
00:42:10,280 --> 00:42:13,280
Aku akan dimasukkan ke dalam string "mengandung (% d) = karena

528
00:42:13,280 --> 00:42:20,470
 kita akan pasang di nilai bahwa kita akan mencari,

529
00:42:20,470 --> 00:42:27,130
dan =% s \ n "dan menggunakannya sebagai format string kami.

530
00:42:27,130 --> 00:42:30,720
Kami hanya akan melihat - secara harfiah mencetak di layar -

531
00:42:30,720 --> 00:42:32,060
apa yang tampak seperti pemanggilan fungsi.

532
00:42:32,060 --> 00:42:33,580
Hal ini tidak benar-benar fungsi panggil.

533
00:42:33,580 --> 00:42:36,760
 Ini hanyalah sebuah string yang dirancang untuk terlihat seperti pemanggilan fungsi.

534
00:42:36,760 --> 00:42:41,140
>> Sekarang, kita akan pasang di nilai.

535
00:42:41,140 --> 00:42:43,580
Kami akan mencoba mengandung pada 6,

536
00:42:43,580 --> 00:42:48,340
dan kemudian apa yang akan kita lakukan di sini adalah menggunakan operator ternary.

537
00:42:48,340 --> 00:42:56,340
Mari kita lihat - berisi 6 - jadi, sekarang aku sudah mengandung 6 dan jika mengandung 6 adalah benar,

538
00:42:56,340 --> 00:43:01,850
string yang akan kita kirim ke karakter format% s

539
00:43:01,850 --> 00:43:04,850
akan menjadi string "true".

540
00:43:04,850 --> 00:43:07,690
Mari kita gulir lebih sedikit.

541
00:43:07,690 --> 00:43:16,210
Jika tidak, kami ingin mengirim string "palsu" jika mengandung 6 returns false.

542
00:43:16,210 --> 00:43:19,730
Ini adalah sedikit konyol-tampak, tapi saya pikir saya mungkin juga menggambarkan

543
00:43:19,730 --> 00:43:23,780
apa operator terner tampak seperti karena kita belum melihat itu untuk sementara.

544
00:43:23,780 --> 00:43:27,670
Ini akan menjadi cara yang baik, berguna untuk mencari tahu apakah yang dikandungnya fungsi kita bekerja.

545
00:43:27,670 --> 00:43:30,040
Aku akan gulir kembali ke kiri,

546
00:43:30,040 --> 00:43:39,900
dan aku akan copy dan paste baris ini beberapa kali.

547
00:43:39,900 --> 00:43:44,910
Itu mengubah beberapa nilai sekitar,

548
00:43:44,910 --> 00:43:59,380
jadi ini akan menjadi 1, dan ini akan menjadi 10.

549
00:43:59,380 --> 00:44:02,480
>> Pada titik ini kita punya fungsi yang dikandungnya yang bagus.

550
00:44:02,480 --> 00:44:06,080
Kami punya beberapa tes, dan kita akan melihat apakah semua ini bekerja.

551
00:44:06,080 --> 00:44:08,120
Pada titik ini kita telah menulis beberapa kode lagi.

552
00:44:08,120 --> 00:44:13,160
Waktu untuk berhenti keluar dan memastikan bahwa semuanya masih mengkompilasi.

553
00:44:13,160 --> 00:44:20,360
Berhenti keluar, dan sekarang mari kita mencoba membuat pohon biner lagi.

554
00:44:20,360 --> 00:44:22,260
Yah, sepertinya kita punya kesalahan,

555
00:44:22,260 --> 00:44:26,930
dan kita sudah mendapat ini secara eksplisit menyatakan fungsi perpustakaan printf.

556
00:44:26,930 --> 00:44:39,350
Sepertinya kita perlu masuk dan # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Dan dengan itu, segala sesuatu harus mengkompilasi. Kita semua baik.

558
00:44:45,350 --> 00:44:50,420
Sekarang mari kita coba jalankan pohon biner dan melihat apa yang terjadi.

559
00:44:50,420 --> 00:44:53,520
Di sini kita, / binary_tree.,

560
00:44:53,520 --> 00:44:55,190
dan kita melihat bahwa, seperti yang kita harapkan -

561
00:44:55,190 --> 00:44:56,910
karena kita belum diimplementasikan mengandung belum,

562
00:44:56,910 --> 00:44:59,800
atau lebih tepatnya, kita baru saja dimasukkan ke dalam return false -

563
00:44:59,800 --> 00:45:03,300
kita melihat bahwa itu hanya kembali palsu untuk mereka semua,

564
00:45:03,300 --> 00:45:06,180
jadi itu semua bekerja untuk sebagian besar cukup baik.

565
00:45:06,180 --> 00:45:11,860
>> Mari kita kembali dan benar-benar menerapkan mengandung pada saat ini.

566
00:45:11,860 --> 00:45:17,490
Aku akan gulir ke bawah, memperbesar, dan -

567
00:45:17,490 --> 00:45:22,330
ingat, algoritma yang kita gunakan adalah bahwa kita mulai pada simpul akar

568
00:45:22,330 --> 00:45:28,010
dan kemudian pada setiap simpul yang kita hadapi, kita melakukan perbandingan,

569
00:45:28,010 --> 00:45:32,380
dan berdasarkan perbandingan yang kita pindahkan ke anak kiri atau ke anak kanan.

570
00:45:32,380 --> 00:45:39,670
Ini akan terlihat sangat mirip dengan kode pencarian biner yang kita tulis sebelumnya dalam istilah.

571
00:45:39,670 --> 00:45:47,810
Ketika kita memulai, kita tahu bahwa kita ingin berpegang pada node saat ini

572
00:45:47,810 --> 00:45:54,050
bahwa kita sedang melihat, dan simpul saat ini akan diinisialisasi ke simpul akar.

573
00:45:54,050 --> 00:45:56,260
Dan sekarang, kita akan terus melalui pohon,

574
00:45:56,260 --> 00:45:58,140
dan ingat bahwa kondisi kita menghentikan -

575
00:45:58,140 --> 00:46:01,870
 ketika kita benar-benar bekerja melalui contoh dengan tangan -

576
00:46:01,870 --> 00:46:03,960
adalah ketika kami mengalami simpul null,

577
00:46:03,960 --> 00:46:05,480
tidak ketika kita melihat seorang anak nol,

578
00:46:05,480 --> 00:46:09,620
tetapi ketika kita benar-benar pindah ke sebuah simpul di pohon

579
00:46:09,620 --> 00:46:12,640
dan menemukan bahwa kami berada di node null.

580
00:46:12,640 --> 00:46:20,720
Kita akan iterate sampai skr tidak sama dengan nol.

581
00:46:20,720 --> 00:46:22,920
Dan apa yang akan kita lakukan?

582
00:46:22,920 --> 00:46:31,610
Kita akan menguji apakah (skr -> value == value),

583
00:46:31,610 --> 00:46:35,160
maka kita tahu bahwa kita telah benar-benar menemukan node yang kita cari.

584
00:46:35,160 --> 00:46:40,450
Jadi di sini, kita bisa kembali benar.

585
00:46:40,450 --> 00:46:49,830
Jika tidak, kita ingin melihat apakah atau tidak nilai kurang dari nilai.

586
00:46:49,830 --> 00:46:53,850
Jika nilai node saat ini kurang dari nilai yang kita cari,

587
00:46:53,850 --> 00:46:57,280
kita akan bergerak ke kanan.

588
00:46:57,280 --> 00:47:10,600
Jadi, skr = skr -> right_child, dan sebaliknya, kita akan bergerak ke kiri.

589
00:47:10,600 --> 00:47:17,480
skr = skr -> left_child;. Cukup sederhana.

590
00:47:17,480 --> 00:47:22,830
>> Anda mungkin mengenali loop yang terlihat sangat mirip dengan ini dari

591
00:47:22,830 --> 00:47:27,580
biner pencarian awal istilah, kecuali kemudian kami berurusan dengan rendah, menengah, dan tinggi.

592
00:47:27,580 --> 00:47:30,000
Di sini, kita hanya harus melihat nilai saat ini,

593
00:47:30,000 --> 00:47:31,930
sehingga sangat bagus dan sederhana.

594
00:47:31,930 --> 00:47:34,960
Mari kita pastikan kode ini bekerja.

595
00:47:34,960 --> 00:47:42,780
Pertama, pastikan mengkompilasi. Sepertinya tidak.

596
00:47:42,780 --> 00:47:47,920
Mari kita coba menjalankannya.

597
00:47:47,920 --> 00:47:50,160
Dan memang, ia akan mencetak segala sesuatu yang kami harapkan.

598
00:47:50,160 --> 00:47:54,320
Ia menemukan 6 di pohon, tidak menemukan 10 karena 10 tidak di pohon,

599
00:47:54,320 --> 00:47:57,740
dan tidak menemukan 1 baik karena 1 juga tidak di pohon.

600
00:47:57,740 --> 00:48:01,420
Cool stuff.

601
00:48:01,420 --> 00:48:04,470
>> Alright. Mari kita kembali ke spesifikasi kami dan melihat apa yang berikutnya.

602
00:48:04,470 --> 00:48:07,990
Sekarang, ia ingin menambahkan node lagi ke pohon kami.

603
00:48:07,990 --> 00:48:11,690
Ia ingin menambah 5, 2, dan 8, dan pastikan bahwa kami berisi kode

604
00:48:11,690 --> 00:48:13,570
masih bekerja seperti yang diharapkan.

605
00:48:13,570 --> 00:48:14,900
Mari kita lakukan itu.

606
00:48:14,900 --> 00:48:19,430
Pada titik ini, daripada melakukan hal itu mengganggu copy dan paste lagi,

607
00:48:19,430 --> 00:48:23,770
mari kita menulis fungsi untuk benar-benar menciptakan sebuah node.

608
00:48:23,770 --> 00:48:27,740
Jika kita scroll ke bawah sampai ke utama, kita melihat bahwa kita sudah melakukan ini

609
00:48:27,740 --> 00:48:31,210
sangat mirip kode berulang-ulang setiap kali kita ingin membuat sebuah node.

610
00:48:31,210 --> 00:48:39,540
>> Mari kita menulis fungsi yang benar-benar akan membangun simpul bagi kita dan mengembalikannya.

611
00:48:39,540 --> 00:48:41,960
Aku akan menyebutnya build_node.

612
00:48:41,960 --> 00:48:45,130
Aku akan membangun sebuah node dengan nilai tertentu.

613
00:48:45,130 --> 00:48:51,040
Zoom di sini.

614
00:48:51,040 --> 00:48:56,600
Hal pertama yang saya akan lakukan adalah benar-benar membuat ruang untuk node di heap.

615
00:48:56,600 --> 00:49:05,400
Jadi, simpul * n = malloc (sizeof (node)), n -> value = value;

616
00:49:05,400 --> 00:49:14,960
dan kemudian di sini, aku hanya akan menginisialisasi semua bidang untuk menjadi nilai-nilai yang sesuai.

617
00:49:14,960 --> 00:49:22,500
Dan di akhir, kami akan kembali simpul kami.

618
00:49:22,500 --> 00:49:28,690
Alright. Satu hal yang perlu diperhatikan adalah bahwa fungsi ini di sini

619
00:49:28,690 --> 00:49:34,320
akan kembali pointer ke memori yang telah dialokasikan tumpukan-.

620
00:49:34,320 --> 00:49:38,880
Apa yang baik tentang ini adalah bahwa node ini sekarang -

621
00:49:38,880 --> 00:49:42,420
kita harus mendeklarasikan di heap karena jika kita menyatakan itu di stack

622
00:49:42,420 --> 00:49:45,050
kita tidak akan mampu melakukannya dalam fungsi ini seperti ini.

623
00:49:45,050 --> 00:49:47,690
Memori yang akan keluar dari ruang lingkup

624
00:49:47,690 --> 00:49:51,590
dan akan valid jika kita mencoba untuk mengaksesnya nanti.

625
00:49:51,590 --> 00:49:53,500
Karena kita menyatakan tumpukan-dialokasikan memori,

626
00:49:53,500 --> 00:49:55,830
kita akan harus mengurus membebaskan nanti

627
00:49:55,830 --> 00:49:58,530
untuk program kami untuk tidak bocor memori apapun.

628
00:49:58,530 --> 00:50:01,270
Kami sudah punting pada bahwa untuk segala sesuatu yang lain dalam kode

629
00:50:01,270 --> 00:50:02,880
hanya untuk mudahnya pada saat itu,

630
00:50:02,880 --> 00:50:05,610
tetapi jika Anda pernah menulis fungsi yang terlihat seperti ini

631
00:50:05,610 --> 00:50:10,370
di mana Anda punya - beberapa menyebutnya malloc atau realloc dalam -

632
00:50:10,370 --> 00:50:14,330
Anda ingin memastikan bahwa Anda menempatkan semacam komentar di sini yang mengatakan,

633
00:50:14,330 --> 00:50:29,970
hey, kau tahu, mengembalikan node tumpukan-dialokasikan diinisialisasi dengan nilai berlalu-in.

634
00:50:29,970 --> 00:50:33,600
Dan kemudian Anda ingin memastikan bahwa Anda masukkan ke dalam semacam catatan yang mengatakan

635
00:50:33,600 --> 00:50:41,720
pemanggil harus membebaskan memori dikembalikan.

636
00:50:41,720 --> 00:50:45,450
Dengan begitu, jika seseorang pernah berjalan dan menggunakan fungsi itu,

637
00:50:45,450 --> 00:50:48,150
mereka tahu bahwa apa pun yang mereka dapatkan kembali dari fungsi yang

638
00:50:48,150 --> 00:50:50,870
di beberapa titik perlu dibebaskan.

639
00:50:50,870 --> 00:50:53,940
>> Dengan asumsi bahwa semuanya baik-baik dan baik di sini,

640
00:50:53,940 --> 00:51:02,300
kita bisa turun ke dalam kode kita dan menggantikan semua baris di sini

641
00:51:02,300 --> 00:51:05,410
dengan panggilan ke fungsi simpul kami membangun.

642
00:51:05,410 --> 00:51:08,170
Mari kita lakukan yang benar-benar cepat.

643
00:51:08,170 --> 00:51:15,840
Bagian yang kita tidak akan menggantikan adalah bagian ini di sini

644
00:51:15,840 --> 00:51:18,520
di bagian bawah di mana kita benar-benar memasang sebuah node untuk menunjuk satu sama lain,

645
00:51:18,520 --> 00:51:21,030
karena kita tidak bisa dilakukan di fungsi kita.

646
00:51:21,030 --> 00:51:37,400
Tapi, mari kita lakukan root = build_node (7), simpul * = build_node tiga (3);

647
00:51:37,400 --> 00:51:47,980
simpul * = build_node enam (6), simpul * sembilan = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
Dan sekarang, kami juga ingin menambahkan node untuk -

649
00:51:52,590 --> 00:52:03,530
simpul * = build_node lima (5), simpul delapan * = build_node (8);

650
00:52:03,530 --> 00:52:09,760
dan apa node lainnya? Mari kita lihat di sini. Kami ingin juga menambahkan 2 -

651
00:52:09,760 --> 00:52:20,280
simpul * dua = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Alright. Pada titik ini, kita tahu bahwa kita punya 7, 3, 9, dan 6

653
00:52:26,850 --> 00:52:30,320
semua kabel dengan tepat, tapi bagaimana dengan 5, 8, dan 2?

654
00:52:30,320 --> 00:52:33,550
Untuk menjaga semuanya dalam urutan yang tepat,

655
00:52:33,550 --> 00:52:39,230
kita tahu bahwa anak kanan ketiga adalah 6.

656
00:52:39,230 --> 00:52:40,890
Jadi, jika kita akan menambahkan 5,

657
00:52:40,890 --> 00:52:46,670
5 juga termasuk dalam sisi kanan pohon yang 3 adalah akar,

658
00:52:46,670 --> 00:52:50,440
jadi 5 milik sebagai anak kiri 6.

659
00:52:50,440 --> 00:52:58,650
Kita bisa melakukan hal ini dengan mengatakan, enam -> left_child = lima;

660
00:52:58,650 --> 00:53:10,790
dan kemudian 8 milik sebagai anak kiri dari 9, maka sembilan -> left_child = delapan;

661
00:53:10,790 --> 00:53:22,190
dan kemudian 2 adalah anak kiri dari 3, sehingga kita bisa melakukan itu di sini - engkau -> left_child = dua;.

662
00:53:22,190 --> 00:53:27,730
Jika Anda tidak cukup mengikuti bersama dengan itu, saya sarankan Anda menariknya keluar sendiri.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Mari kita menyimpan. Mari kita pergi keluar dan pastikan mengkompilasi,

664
00:53:35,660 --> 00:53:40,760
dan kemudian kita dapat menambahkan panggilan kami yang dikandungnya.

665
00:53:40,760 --> 00:53:44,120
Sepertinya semuanya masih mengkompilasi.

666
00:53:44,120 --> 00:53:51,790
Mari kita masuk dan menambahkan beberapa berisi panggilan.

667
00:53:51,790 --> 00:53:59,640
Sekali lagi, aku akan melakukan sedikit copy dan paste.

668
00:53:59,640 --> 00:54:15,860
Sekarang mari kita mencari 5, 8, dan 2. Alright.

669
00:54:15,860 --> 00:54:28,330
Mari kita pastikan bahwa ini semua terlihat baik masih. Great! Simpan dan berhenti.

670
00:54:28,330 --> 00:54:33,220
Sekarang mari kita membuat, kompilasi, dan sekarang mari kita jalankan.

671
00:54:33,220 --> 00:54:37,540
Dari hasil, sepertinya semuanya bekerja hanya bagus dan baik.

672
00:54:37,540 --> 00:54:41,780
Great! Jadi sekarang kita punya dikandungnya kami fungsi ditulis.

673
00:54:41,780 --> 00:54:46,160
Mari kita lanjutkan dan mulai bekerja pada cara memasukkan node ke pohon

674
00:54:46,160 --> 00:54:50,000
karena, seperti yang kita lakukan sekarang juga, hal ini tidak sangat cantik.

675
00:54:50,000 --> 00:54:52,280
>> Jika kita kembali ke spesifikasi,

676
00:54:52,280 --> 00:55:00,540
itu meminta kita untuk menulis sebuah fungsi yang disebut masukkan - lagi, mengembalikan bool

677
00:55:00,540 --> 00:55:04,400
untuk apakah atau tidak kita benar-benar bisa memasukkan node ke pohon -

678
00:55:04,400 --> 00:55:07,710
dan kemudian nilai untuk memasukkan ke dalam pohon itu ditetapkan sebagai

679
00:55:07,710 --> 00:55:11,060
argumen hanya untuk fungsi insert kami.

680
00:55:11,060 --> 00:55:18,180
Kami akan mengembalikan true jika kita memang bisa memasukkan nilai yang mengandung simpul dalam pohon,

681
00:55:18,180 --> 00:55:20,930
yang berarti bahwa kita, satu, memiliki memori yang cukup,

682
00:55:20,930 --> 00:55:24,840
dan kemudian dua, simpul yang tidak sudah ada di pohon sejak -

683
00:55:24,840 --> 00:55:32,170
ingat, kita tidak akan memiliki nilai ganda di pohon, hanya untuk membuat hal-hal sederhana.

684
00:55:32,170 --> 00:55:35,590
Alright. Kembali ke kode.

685
00:55:35,590 --> 00:55:44,240
Membukanya. Memperbesar sedikit, kemudian gulir ke bawah.

686
00:55:44,240 --> 00:55:47,220
Mari kita menempatkan fungsi insert tepat di atas dikandungnya.

687
00:55:47,220 --> 00:55:56,360
Sekali lagi, itu akan disebut insert bool (int value).

688
00:55:56,360 --> 00:56:01,840
Berikan sedikit lebih banyak ruang, dan kemudian, sebagai default,

689
00:56:01,840 --> 00:56:08,870
mari kita dimasukkan ke dalam return false di akhir.

690
00:56:08,870 --> 00:56:22,620
Sekarang turun di bawah, mari kita pergi ke depan dan bukannya secara manual membangun node

691
00:56:22,620 --> 00:56:27,900
di utama diri kita sendiri dan kabel mereka untuk menunjuk satu sama lain seperti yang kita lakukan,

692
00:56:27,900 --> 00:56:30,600
kita akan bergantung pada fungsi insert kami untuk melakukan itu.

693
00:56:30,600 --> 00:56:35,510
Kami tidak akan bergantung pada fungsi insert kami untuk membangun seluruh pohon dari awal dulu,

694
00:56:35,510 --> 00:56:39,970
melainkan kita akan menyingkirkan garis - kami komentari baris berikut -

695
00:56:39,970 --> 00:56:43,430
yang membangun node 5, 8, dan 2.

696
00:56:43,430 --> 00:56:55,740
Dan sebagai gantinya, kami akan memasukkan panggilan ke fungsi insert kami

697
00:56:55,740 --> 00:57:01,280
untuk memastikan bahwa benar-benar bekerja.

698
00:57:01,280 --> 00:57:05,840
Di sini kita pergi.

699
00:57:05,840 --> 00:57:09,300
>> Sekarang kita sudah komentar baris ini.

700
00:57:09,300 --> 00:57:13,700
Kami hanya memiliki 7, 3, 9, dan 6 di pohon kami pada saat ini.

701
00:57:13,700 --> 00:57:18,870
Untuk memastikan bahwa ini semua bekerja,

702
00:57:18,870 --> 00:57:25,050
kita bisa memperkecil, membuat pohon biner kita,

703
00:57:25,050 --> 00:57:30,750
menjalankannya, dan kita dapat melihat bahwa mengandung sekarang mengatakan kepada kita bahwa kita benar-benar benar -

704
00:57:30,750 --> 00:57:33,110
5, 8, dan 2 tidak lagi di pohon.

705
00:57:33,110 --> 00:57:37,960
Kembali ke dalam kode,

706
00:57:37,960 --> 00:57:41,070
dan bagaimana kita akan memasukkan?

707
00:57:41,070 --> 00:57:46,290
Ingat apa yang kita lakukan ketika kita benar-benar memasukkan 5, 8, dan 2 sebelumnya.

708
00:57:46,290 --> 00:57:50,100
Kami bermain bahwa permainan Plinko mana kita mulai pada akar,

709
00:57:50,100 --> 00:57:52,780
turun satu pohon oleh satu per satu

710
00:57:52,780 --> 00:57:54,980
sampai kami menemukan kesenjangan yang tepat,

711
00:57:54,980 --> 00:57:57,570
dan kemudian kita kabel di node di tempat yang tepat.

712
00:57:57,570 --> 00:57:59,480
Kita akan melakukan hal yang sama.

713
00:57:59,480 --> 00:58:04,070
Hal ini pada dasarnya seperti menulis kode yang kita digunakan dalam mengandung fungsi

714
00:58:04,070 --> 00:58:05,910
untuk menemukan tempat di mana node seharusnya,

715
00:58:05,910 --> 00:58:10,560
dan kemudian kita hanya akan memasukkan node di sana.

716
00:58:10,560 --> 00:58:17,000
Mari kita mulai melakukan hal itu.

717
00:58:17,000 --> 00:58:24,200
>> Jadi kita memiliki simpul * skr = root, kita hanya akan mengikuti berisi kode

718
00:58:24,200 --> 00:58:26,850
sampai kita menemukan bahwa itu tidak cukup bekerja untuk kita.

719
00:58:26,850 --> 00:58:32,390
Kita akan pergi melalui pohon sementara elemen saat ini tidak null,

720
00:58:32,390 --> 00:58:45,280
dan jika kita menemukan nilai yang skr adalah sama dengan nilai yang kita mencoba untuk memasukkan -

721
00:58:45,280 --> 00:58:49,600
baik, ini adalah salah satu kasus di mana kita tidak bisa benar-benar memasukkan node

722
00:58:49,600 --> 00:58:52,730
ke pohon karena ini berarti kita memiliki nilai duplikat.

723
00:58:52,730 --> 00:58:59,010
Di sini kita benar-benar akan kembali palsu.

724
00:58:59,010 --> 00:59:08,440
Sekarang, lain jika nilai skr adalah kurang dari nilai,

725
00:59:08,440 --> 00:59:10,930
sekarang kita tahu bahwa kita bergerak ke kanan

726
00:59:10,930 --> 00:59:17,190
 karena nilai termasuk dalam bagian kanan dari pohon skr.

727
00:59:17,190 --> 00:59:30,110
Jika tidak, kita akan bergerak ke kiri.

728
00:59:30,110 --> 00:59:37,980
Itu pada dasarnya berfungsi dikandungnya kami di sana.

729
00:59:37,980 --> 00:59:41,820
>> Pada titik ini, setelah kami telah menyelesaikan ini loop sementara,

730
00:59:41,820 --> 00:59:47,350
pointer skr kita akan menunjuk ke null

731
00:59:47,350 --> 00:59:51,540
jika fungsi tersebut belum dikembalikan.

732
00:59:51,540 --> 00:59:58,710
Oleh karena itu kita memiliki skr di tempat di mana kita ingin menyisipkan simpul baru.

733
00:59:58,710 --> 01:00:05,210
Apa yang masih harus dilakukan adalah untuk benar-benar membangun node baru,

734
01:00:05,210 --> 01:00:08,480
yang bisa kita lakukan cukup mudah.

735
01:00:08,480 --> 01:00:14,930
Kita dapat menggunakan super-praktis kami fungsi simpul membangun,

736
01:00:14,930 --> 01:00:17,210
dan sesuatu yang kita tidak lakukan sebelumnya -

737
01:00:17,210 --> 01:00:21,400
kita hanya semacam mengambil untuk diberikan, tapi sekarang kita akan melakukan hanya untuk memastikan -

738
01:00:21,400 --> 01:00:27,130
kita akan menguji untuk memastikan bahwa nilai yang dikembalikan oleh node baru sebenarnya

739
01:00:27,130 --> 01:00:33,410
tidak nol, karena kita tidak ingin mulai mengakses memori yang jika nol.

740
01:00:33,410 --> 01:00:39,910
Kita dapat menguji untuk memastikan bahwa node baru tidak sama dengan nol.

741
01:00:39,910 --> 01:00:42,910
Atau sebaliknya, kita hanya bisa melihat apakah itu benar-benar nol,

742
01:00:42,910 --> 01:00:52,120
dan jika itu adalah nol, maka kita hanya dapat return false awal.

743
01:00:52,120 --> 01:00:59,090
>> Pada titik ini, kita harus kawat simpul baru ke dalam tempat yang sesuai dalam pohon.

744
01:00:59,090 --> 01:01:03,510
Jika kita melihat kembali utama dan di mana kami benar-benar kabel nilai sebelumnya,

745
01:01:03,510 --> 01:01:08,470
kita melihat bahwa cara kita melakukan hal itu ketika kita ingin menempatkan 3 di pohon

746
01:01:08,470 --> 01:01:11,750
yang kita diakses anak kiri akar.

747
01:01:11,750 --> 01:01:14,920
Ketika kita menempatkan 9 di pohon, kami harus mengakses anak kanan dari akar.

748
01:01:14,920 --> 01:01:21,030
Kami harus memiliki pointer ke orang tua dalam rangka untuk menempatkan nilai baru ke dalam pohon.

749
01:01:21,030 --> 01:01:24,430
Bergulir kembali untuk memasukkan, itu tidak akan cukup bekerja di sini

750
01:01:24,430 --> 01:01:27,550
karena kita tidak memiliki pointer orangtua.

751
01:01:27,550 --> 01:01:31,650
Apa yang kita ingin bisa lakukan adalah, pada saat ini,

752
01:01:31,650 --> 01:01:37,080
memeriksa nilai orang tua dan melihat - baik, gosh,

753
01:01:37,080 --> 01:01:41,990
jika nilai orangtua kurang dari nilai saat ini,

754
01:01:41,990 --> 01:01:54,440
maka anak kanan orangtua harus menjadi simpul baru;

755
01:01:54,440 --> 01:02:07,280
jika tidak, anak kiri induk harus menjadi simpul baru.

756
01:02:07,280 --> 01:02:10,290
Tapi, kita tidak memiliki pointer orangtua belum cukup.

757
01:02:10,290 --> 01:02:15,010
>> Untuk mendapatkannya, kita benar-benar akan harus melacak itu seperti yang kita pergi melalui pohon

758
01:02:15,010 --> 01:02:18,440
dan menemukan tempat yang sesuai dalam lingkaran di atas kami.

759
01:02:18,440 --> 01:02:26,840
Kita bisa melakukannya dengan menggulir kembali ke atas fungsi insert kami

760
01:02:26,840 --> 01:02:32,350
dan pelacakan variabel lain disebut pointer orangtua.

761
01:02:32,350 --> 01:02:39,340
Kita akan mengaturnya sama dengan null awalnya,

762
01:02:39,340 --> 01:02:43,640
dan kemudian setiap kali kita pergi melalui pohon,

763
01:02:43,640 --> 01:02:51,540
kita akan mengatur pointer orangtua untuk mencocokkan pointer saat ini.

764
01:02:51,540 --> 01:02:59,140
Set orangtua sama dengan skr.

765
01:02:59,140 --> 01:03:02,260
Dengan cara ini, setiap kali kita pergi melalui,

766
01:03:02,260 --> 01:03:05,550
kita akan memastikan bahwa sebagai pointer saat akan bertambah

767
01:03:05,550 --> 01:03:12,640
pointer orangtua mengikutinya - hanya satu tingkat lebih tinggi dari pointer saat ini di pohon.

768
01:03:12,640 --> 01:03:17,370
Itu semua terlihat cukup bagus.

769
01:03:17,370 --> 01:03:22,380
>> Saya pikir satu hal yang kita akan ingin menyesuaikan ini membangun simpul nol kembali.

770
01:03:22,380 --> 01:03:25,380
Dalam rangka untuk mendapatkan membangun simpul untuk benar-benar berhasil mengembalikan null,

771
01:03:25,380 --> 01:03:31,060
kita harus memodifikasi kode tersebut,

772
01:03:31,060 --> 01:03:37,270
karena di sini, kita tidak pernah diuji untuk memastikan bahwa malloc kembali pointer yang valid.

773
01:03:37,270 --> 01:03:53,390
Jadi, jika (n = NULL!), Kemudian -

774
01:03:53,390 --> 01:03:55,250
jika malloc kembali pointer yang valid, maka kita akan menginisialisasi itu;

775
01:03:55,250 --> 01:04:02,540
jika tidak, kita hanya akan kembali dan itu akan berakhir kembali nol bagi kita.

776
01:04:02,540 --> 01:04:13,050
Sekarang semua terlihat cukup bagus. Mari kita pastikan ini benar-benar mengkompilasi.

777
01:04:13,050 --> 01:04:22,240
Membuat pohon biner, dan oh, kami punya beberapa hal terjadi di sini.

778
01:04:22,240 --> 01:04:29,230
>> Kami punya sebuah deklarasi implisit dari fungsi membangun simpul.

779
01:04:29,230 --> 01:04:31,950
Sekali lagi, dengan kompiler, kita akan mulai dari atas.

780
01:04:31,950 --> 01:04:36,380
Apa yang harus maksud adalah bahwa aku menelepon membangun simpul sebelum aku benar-benar menyatakan itu.

781
01:04:36,380 --> 01:04:37,730
Mari kita kembali ke kode benar-benar cepat.

782
01:04:37,730 --> 01:04:43,510
Gulir ke bawah, dan tentu saja, fungsi insert saya dinyatakan

783
01:04:43,510 --> 01:04:47,400
atas fungsi simpul membangun,

784
01:04:47,400 --> 01:04:50,070
tapi aku mencoba untuk menggunakan membangun simpul dalam insert.

785
01:04:50,070 --> 01:05:06,610
Aku akan masuk dan copy - dan kemudian paste cara membangun simpul fungsi di sini di bagian atas.

786
01:05:06,610 --> 01:05:11,750
Dengan begitu, mudah-mudahan yang akan bekerja. Mari kita memberikan ini lain pergi.

787
01:05:11,750 --> 01:05:18,920
Sekarang semuanya mengkompilasi. Semua baik.

788
01:05:18,920 --> 01:05:21,640
>> Tapi pada saat ini, kita belum benar-benar disebut fungsi insert kami.

789
01:05:21,640 --> 01:05:26,510
Kita hanya tahu bahwa itu mengkompilasi, jadi mari kita masuk dan menaruh beberapa panggilan masuk

790
01:05:26,510 --> 01:05:28,240
Mari kita melakukan itu dalam fungsi utama kami.

791
01:05:28,240 --> 01:05:32,390
Di sini, kami komentar 5, 8, dan 2,

792
01:05:32,390 --> 01:05:36,680
dan kemudian kita tidak kawat mereka di sini.

793
01:05:36,680 --> 01:05:41,640
Mari kita membuat beberapa panggilan untuk memasukkan,

794
01:05:41,640 --> 01:05:46,440
dan mari kita juga menggunakan jenis yang sama hal-hal yang kita digunakan

795
01:05:46,440 --> 01:05:52,810
ketika kita membuat panggilan ini printf untuk memastikan bahwa segala sesuatu tidak bisa dimasukkan dengan benar.

796
01:05:52,810 --> 01:06:00,550
Aku akan copy dan paste,

797
01:06:00,550 --> 01:06:12,450
dan bukannya mengandung kita akan melakukan insert.

798
01:06:12,450 --> 01:06:30,140
Dan bukannya 6,, 10 dan 1, kita akan menggunakan 5, 8, dan 2.

799
01:06:30,140 --> 01:06:37,320
Ini diharapkan harus memasukkan 5, 8, dan 2 ke atas pohon.

800
01:06:37,320 --> 01:06:44,050
Kompilasi. Semua baik. Sekarang kita benar-benar akan menjalankan program kami.

801
01:06:44,050 --> 01:06:47,330
>> Semuanya kembali palsu.

802
01:06:47,330 --> 01:06:53,830
Jadi, 5, 8, dan 2 tidak pergi, dan sepertinya yang dikandungnya tidak menemukan mereka baik.

803
01:06:53,830 --> 01:06:58,890
Apa yang terjadi? Mari kita zoom out.

804
01:06:58,890 --> 01:07:02,160
Masalah pertama adalah bahwa insert tampaknya kembali palsu,

805
01:07:02,160 --> 01:07:08,750
dan tampaknya seperti itu karena kami meninggalkan panggilan return false kami,

806
01:07:08,750 --> 01:07:14,590
dan kita tidak pernah benar-benar kembali benar.

807
01:07:14,590 --> 01:07:17,880
Kita dapat mengatur bahwa sampai.

808
01:07:17,880 --> 01:07:25,290
Masalah kedua adalah, sekarang bahkan jika kita lakukan - menyimpan, keluar ini,

809
01:07:25,290 --> 01:07:34,530
menjalankan make lagi, memilikinya mengkompilasi, kemudian jalankan -

810
01:07:34,530 --> 01:07:37,670
kita melihat bahwa sesuatu yang lain terjadi di sini.

811
01:07:37,670 --> 01:07:42,980
The 5, 8, dan 2 masih tidak pernah ditemukan di pohon.

812
01:07:42,980 --> 01:07:44,350
Jadi, apa yang terjadi?

813
01:07:44,350 --> 01:07:45,700
>> Mari kita lihat ini dalam kode.

814
01:07:45,700 --> 01:07:49,790
Mari kita lihat apakah kita bisa mengetahui ini.

815
01:07:49,790 --> 01:07:57,940
Kita mulai dengan orangtua tidak menjadi nol.

816
01:07:57,940 --> 01:07:59,510
Kami mengatur pointer saat ini sama dengan pointer akar,

817
01:07:59,510 --> 01:08:04,280
dan kita akan bekerja dengan cara kami turun melalui pohon.

818
01:08:04,280 --> 01:08:08,650
Jika node saat ini tidak nol, maka kita tahu bahwa kita bisa bergerak ke bawah sedikit.

819
01:08:08,650 --> 01:08:12,330
Kami menetapkan pointer induk kami untuk menjadi sama dengan pointer saat ini,

820
01:08:12,330 --> 01:08:15,420
memeriksa nilai - jika nilai yang sama kami kembali palsu.

821
01:08:15,420 --> 01:08:17,540
Jika nilai kurang kami pindah ke kanan;

822
01:08:17,540 --> 01:08:20,399
jika tidak, kami pindah ke kiri.

823
01:08:20,399 --> 01:08:24,220
Kemudian kita membangun node. Saya akan memperbesar sedikit.

824
01:08:24,220 --> 01:08:31,410
Dan di sini, kita akan mencoba untuk kawat sampai nilai-nilai yang sama.

825
01:08:31,410 --> 01:08:37,250
Apa yang terjadi? Mari kita lihat apakah kemungkinan Valgrind dapat memberi kita petunjuk.

826
01:08:37,250 --> 01:08:43,910
>> Saya ingin menggunakan Valgrind Valgrind hanya karena benar-benar cepat berjalan

827
01:08:43,910 --> 01:08:46,729
dan memberitahu Anda jika ada kesalahan memori.

828
01:08:46,729 --> 01:08:48,300
Ketika kita menjalankan Valgrind pada kode,

829
01:08:48,300 --> 01:08:55,859
karena Anda dapat melihat hit here--Valgrind./binary_tree--and benar masuk.

830
01:08:55,859 --> 01:09:03,640
Anda lihat bahwa kita tidak memiliki kesalahan memori, sehingga terlihat seperti semuanya baik-baik saja sejauh ini.

831
01:09:03,640 --> 01:09:07,529
Kami memiliki kebocoran memori tertentu, yang kita tahu, karena kita tidak

832
01:09:07,529 --> 01:09:08,910
terjadi untuk membebaskan salah satu node kami.

833
01:09:08,910 --> 01:09:13,050
Mari kita coba jalankan GDB untuk melihat apa yang sebenarnya terjadi.

834
01:09:13,050 --> 01:09:20,010
Kami akan melakukan gdb / binary_tree.. Ini boot up baik-baik saja.

835
01:09:20,010 --> 01:09:23,670
Mari kita menetapkan titik istirahat di masukkan.

836
01:09:23,670 --> 01:09:28,600
Mari kita jalankan.

837
01:09:28,600 --> 01:09:31,200
Sepertinya kita tidak pernah benar-benar disebut insert.

838
01:09:31,200 --> 01:09:39,410
Sepertinya masalahnya hanya itu ketika saya berubah di sini di utama -

839
01:09:39,410 --> 01:09:44,279
semua panggilan printf dari mengandung -

840
01:09:44,279 --> 01:09:56,430
Aku tidak pernah benar-benar berubah ini untuk memanggil insert.

841
01:09:56,430 --> 01:10:01,660
Sekarang mari kita mencobanya. Mari kita kompilasi.

842
01:10:01,660 --> 01:10:09,130
Semua tampak baik di sana. Sekarang mari kita coba menjalankannya, melihat apa yang terjadi.

843
01:10:09,130 --> 01:10:13,320
Alright! Semuanya terlihat cukup baik di sana.

844
01:10:13,320 --> 01:10:18,130
>> Hal terakhir untuk berpikir tentang adalah, apakah ada kasus tepi apapun untuk menyisipkan ini?

845
01:10:18,130 --> 01:10:23,170
Dan ternyata, baik, salah satu ujung kasus yang selalu menarik untuk berpikir tentang

846
01:10:23,170 --> 01:10:26,250
adalah, apa yang terjadi jika pohon Anda kosong dan Anda memanggil fungsi ini insert?

847
01:10:26,250 --> 01:10:30,330
Apakah akan berhasil? Nah, mari kita mencobanya.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c -.

849
01:10:32,110 --> 01:10:35,810
Cara kita akan menguji ini, kita akan pergi ke fungsi utama kami,

850
01:10:35,810 --> 01:10:41,690
dan bukannya kabel node ini sampai seperti ini,

851
01:10:41,690 --> 01:10:56,730
kita hanya akan komentar pada seluruh hal,

852
01:10:56,730 --> 01:11:02,620
dan bukannya kabel sampai node diri kita sendiri,

853
01:11:02,620 --> 01:11:09,400
kita benar-benar bisa hanya pergi ke depan dan menghapus semua ini.

854
01:11:09,400 --> 01:11:17,560
Kita akan membuat segalanya panggilan untuk menyisipkan.

855
01:11:17,560 --> 01:11:49,020
Jadi, mari kita lakukan - bukan 5, 8, dan 2, kita akan memasukkan 7, 3, dan 9.

856
01:11:49,020 --> 01:11:58,440
Dan kemudian kita juga akan ingin memasukkan 6 juga.

857
01:11:58,440 --> 01:12:05,190
Simpan. Keluar. Membuat pohon biner.

858
01:12:05,190 --> 01:12:08,540
Semuanya mengkompilasi.

859
01:12:08,540 --> 01:12:10,320
Kami hanya bisa menjalankannya seperti dan melihat apa yang terjadi,

860
01:12:10,320 --> 01:12:12,770
tapi itu juga akan menjadi sangat penting untuk memastikan bahwa

861
01:12:12,770 --> 01:12:14,740
kita tidak memiliki kesalahan memori,

862
01:12:14,740 --> 01:12:16,840
karena ini adalah salah satu kasus tepi kita yang kita ketahui.

863
01:12:16,840 --> 01:12:20,150
>> Mari kita pastikan bahwa ia bekerja dengan baik di bawah Valgrind,

864
01:12:20,150 --> 01:12:28,310
yang akan kita lakukan dengan hanya menjalankan Valgrind / binary_tree..

865
01:12:28,310 --> 01:12:31,110
Sepertinya kita memang memiliki satu kesalahan dari satu konteks -

866
01:12:31,110 --> 01:12:33,790
kita memiliki kesalahan segmentasi.

867
01:12:33,790 --> 01:12:36,690
Apa yang terjadi?

868
01:12:36,690 --> 01:12:41,650
Valgrind sebenarnya memberitahu kita di mana itu.

869
01:12:41,650 --> 01:12:43,050
Perkecil sedikit.

870
01:12:43,050 --> 01:12:46,040
Sepertinya itu terjadi dalam fungsi insert kami,

871
01:12:46,040 --> 01:12:53,420
di mana kita memiliki membaca valid ukuran 4 di insert, baris 60.

872
01:12:53,420 --> 01:13:03,590
Mari kita kembali dan melihat apa yang terjadi di sini.

873
01:13:03,590 --> 01:13:05,350
Perkecil benar-benar cepat.

874
01:13:05,350 --> 01:13:14,230
Saya ingin memastikan bahwa ia tidak pergi ke tepi layar sehingga kita bisa melihat segala sesuatu.

875
01:13:14,230 --> 01:13:18,760
Menarik bahwa dalam sedikit. Alright.

876
01:13:18,760 --> 01:13:35,030
Gulir ke bawah, dan masalahnya adalah di sini.

877
01:13:35,030 --> 01:13:40,120
Apa yang terjadi jika kita turun dan node saat ini kami sudah nol,

878
01:13:40,120 --> 01:13:44,010
simpul induk kami adalah null, jadi jika kita melihat ke atas di bagian paling atas, di sini -

879
01:13:44,010 --> 01:13:47,340
jika ini while loop tidak pernah benar-benar melaksanakan

880
01:13:47,340 --> 01:13:52,330
karena nilai kami saat ini adalah null - root adalah null sehingga skr null -

881
01:13:52,330 --> 01:13:57,810
maka orang tua kami tidak pernah akan diatur ke skr atau nilai yang valid,

882
01:13:57,810 --> 01:14:00,580
jadi, orang tua juga akan nol.

883
01:14:00,580 --> 01:14:03,700
Kita harus ingat untuk memeriksa untuk itu

884
01:14:03,700 --> 01:14:08,750
pada saat kita sampai ke sini, dan kami mulai mengakses nilai orangtua.

885
01:14:08,750 --> 01:14:13,190
Jadi, apa yang terjadi? Nah, jika orang tua adalah null -

886
01:14:13,190 --> 01:14:17,990
if (parent == NULL) - maka kita tahu bahwa

887
01:14:17,990 --> 01:14:19,530
tidak boleh ada apa pun di pohon.

888
01:14:19,530 --> 01:14:22,030
Kita harus mencoba untuk memasukkannya pada akar.

889
01:14:22,030 --> 01:14:32,570
Kita dapat melakukannya dengan hanya menetapkan akar sama dengan node baru.

890
01:14:32,570 --> 01:14:40,010
Kemudian pada titik ini, kita tidak benar-benar ingin pergi melalui hal-hal lainnya.

891
01:14:40,010 --> 01:14:44,780
Sebaliknya, di sini, kita bisa melakukan keduanya dengan yang lain-jika-lain,

892
01:14:44,780 --> 01:14:47,610
atau kita bisa menggabungkan semuanya di sini di lain,

893
01:14:47,610 --> 01:14:56,300
tapi di sini kita hanya akan menggunakan lain dan melakukannya dengan cara itu.

894
01:14:56,300 --> 01:14:59,030
Sekarang, kita akan menguji untuk memastikan bahwa orang tua kami tidak null

895
01:14:59,030 --> 01:15:02,160
sebelum kemudian benar-benar mencoba untuk mengakses bidangnya.

896
01:15:02,160 --> 01:15:05,330
Hal ini akan membantu kita menghindari kesalahan segmentasi.

897
01:15:05,330 --> 01:15:14,740
Jadi, kita berhenti, zoom out, kompilasi, jalankan.

898
01:15:14,740 --> 01:15:18,130
>> Tidak ada kesalahan, tapi kami masih memiliki banyak kebocoran memori

899
01:15:18,130 --> 01:15:20,650
karena kita tidak membebaskan salah satu node kami.

900
01:15:20,650 --> 01:15:24,350
Tapi, jika kita pergi di sini dan kami melihat cetakan kami,

901
01:15:24,350 --> 01:15:30,880
kita melihat bahwa, baik, sepertinya semua sisipan kami kembali benar, yang baik.

902
01:15:30,880 --> 01:15:33,050
Menyisipkan semua benar,

903
01:15:33,050 --> 01:15:36,670
dan kemudian dikandungnya sesuai panggilan juga benar.

904
01:15:36,670 --> 01:15:41,510
>> Good job! Sepertinya kita telah berhasil ditulis insert.

905
01:15:41,510 --> 01:15:47,430
Itu semua yang kita miliki untuk Set Keterangan minggu ini Masalah.

906
01:15:47,430 --> 01:15:51,720
Salah satu tantangan yang menyenangkan untuk berpikir tentang adalah bagaimana Anda benar-benar akan masuk

907
01:15:51,720 --> 01:15:55,340
dan bebas dari semua node dalam pohon ini.

908
01:15:55,340 --> 01:15:58,830
Kita bisa melakukannya dengan sejumlah cara yang berbeda,

909
01:15:58,830 --> 01:16:01,930
tapi aku akan meninggalkan terserah kepada Anda untuk bereksperimen,

910
01:16:01,930 --> 01:16:06,080
dan sebagai tantangan yang menyenangkan, mencoba dan pastikan bahwa Anda dapat memastikan

911
01:16:06,080 --> 01:16:09,490
bahwa laporan Valgrind kembali tidak ada kesalahan dan tidak ada kebocoran.

912
01:16:09,490 --> 01:16:12,880
>> Good luck pada minggu ini set coding masalah Huffman,

913
01:16:12,880 --> 01:16:14,380
dan kita akan melihat Anda minggu depan!

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