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

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

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 ke Seksyen 7.

5
00:00:09,080 --> 00:00:11,330
Terima kasih kepada taufan Sandy,

6
00:00:11,330 --> 00:00:13,440
bukannya mempunyai seksyen biasa minggu ini,

7
00:00:13,440 --> 00:00:17,650
kita lakukan ini berjalan-melalui, melalui seksyen soalan.

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

9
00:00:22,830 --> 00:00:25,650
dan pergi melalui semua soalan dalam

10
00:00:25,650 --> 00:00:27,770
Seksyen seksyen Soalan.

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

12
00:00:30,940 --> 00:00:32,960
sila pos ini pada CS50 Bincangkan.

13
00:00:32,960 --> 00:00:35,480
>> Baiklah. Mari kita mulakan.

14
00:00:35,480 --> 00:00:40,780
Sekarang saya melihat 3 halaman Spesifikasi Set Masalah.

15
00:00:40,780 --> 00:00:44,110
Kami akan mula bercakap tentang pokok binari

16
00:00:44,110 --> 00:00:47,850
kerana mereka mempunyai banyak kaitan dengan set masalah minggu ini -

17
00:00:47,850 --> 00:00:49,950
Pokok pengekodan Huffman.

18
00:00:49,950 --> 00:00:55,000
Salah satu struktur data yang sangat pertama kita bercakap tentang di CS50 adalah array.

19
00:00:55,000 --> 00:01:00,170
Ingatlah bahawa array adalah urutan elemen -

20
00:01:00,170 --> 00:01:04,019
semua jenis yang sama - yang disimpan di sebelah antara satu sama lain dalam ingatan.

21
00:01:04,019 --> 00:01:14,420
Jika saya mempunyai pelbagai integer yang saya boleh menarik menggunakan gaya ini kotak-nombor integer -

22
00:01:14,420 --> 00:01:20,290
Katakan saya mempunyai 5 dalam kotak pertama, saya mempunyai 7 di kedua,

23
00:01:20,290 --> 00:01:27,760
maka saya mempunyai 8, 10, dan 20 dalam kotak yang terakhir.

24
00:01:27,760 --> 00:01:33,000
Ingat, kedua-dua benar-benar baik perkara tentang array ini

25
00:01:33,000 --> 00:01:38,800
adalah bahawa kita mempunyai akses ini berterusan masa kepada mana-mana elemen tertentu

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

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

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

29
00:01:47,870 --> 00:01:52,220
Saya benar-benar hanya perlu untuk melakukan pengiraan matematik mudah,

30
00:01:52,220 --> 00:01:56,170
melompat ke kedudukan itu dalam array,

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

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

33
00:01:59,260 --> 00:02:03,350
>> Salah satu daripada perkara-perkara buruk tentang array ini - bahawa kita bercakap tentang

34
00:02:03,350 --> 00:02:05,010
apabila kita membincangkan dikaitkan senarai -

35
00:02:05,010 --> 00:02:09,120
adalah bahawa jika saya mahu memasukkan unsur ke dalam array ini,

36
00:02:09,120 --> 00:02:11,090
Saya akan perlu untuk melakukan beberapa beralih sekitar.

37
00:02:11,090 --> 00:02:12,940
Sebagai contoh, ini pelbagai di sini

38
00:02:12,940 --> 00:02:16,850
dalam perintah disusun - disusun dalam tertib menaik -

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

40
00:02:19,440 --> 00:02:23,100
tetapi jika saya mahu memasukkan nombor 9 ke array ini,

41
00:02:23,100 --> 00:02:27,460
Saya akan perlu untuk beralih beberapa elemen untuk membuat ruang.

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

43
00:02:30,440 --> 00:02:35,650
Saya akan mempunyai untuk bergerak 5, 7, dan maka 8;

44
00:02:35,650 --> 00:02:38,720
mewujudkan jurang di mana saya boleh meletakkan 9,

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

46
00:02:45,910 --> 00:02:49,450
Ini adalah jenis sakit kerana dalam senario kes terburuk -

47
00:02:49,450 --> 00:02:54,350
apabila kita perlu untuk memasukkan sama ada di awal atau di akhir

48
00:02:54,350 --> 00:02:56,040
array, bergantung kepada bagaimana kita beralih -

49
00:02:56,040 --> 00:02:58,850
kita mungkin akhirnya perlu untuk mengalihkan semua unsur-unsur

50
00:02:58,850 --> 00:03:00,750
bahawa 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 kaedah berkaitan senarai kami di mana -

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

54
00:03:19,820 --> 00:03:25,630
apa yang kita bukannya tidak telah menyimpan mereka jenis mana-mana kita mahu untuk menyimpan mereka

55
00:03:25,630 --> 00:03:32,470
dalam nod senarai berpaut yang saya menarik di sini, jenis ad-hoc.

56
00:03:32,470 --> 00:03:42,060
Dan kemudian kita disambungkan mereka bersama-sama menggunakan petunjuk seterusnya.

57
00:03:42,060 --> 00:03:44,370
Saya boleh mempunyai penunjuk dari 5 kepada 7,

58
00:03:44,370 --> 00:03:46,420
penunjuk daripada 7 kepada 8,

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

60
00:03:47,770 --> 00:03:51,220
dan akhirnya, penunjuk dari 10 kepada 20,

61
00:03:51,220 --> 00:03:54,880
dan kemudian penunjuk nol pada 20 menunjukkan bahawa tiada apa-apa kiri.

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

63
00:03:59,690 --> 00:04:05,360
adalah bahawa sekarang jika kita mahu memasukkan nombor 9 ke dalam senarai diisih kami,

64
00:04:05,360 --> 00:04:08,270
semua yang perlu kita lakukan adalah mewujudkan nod baru dengan 9,

65
00:04:08,270 --> 00:04:12,290
wayar sehingga ke titik ke tempat yang sesuai,

66
00:04:12,290 --> 00:04:20,630
dan kemudian semula wayar 8 yang menunjukkan turun kepada 9.

67
00:04:20,630 --> 00:04:25,660
Itu cukup pantas, dengan anggapan kita tahu di mana kita mahu memasukkan 9.

68
00:04:25,660 --> 00:04:32,610
Tetapi trade-off dalam pertukaran untuk ini adalah bahawa sekarang kami telah kehilangan akses malar masa

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

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

71
00:04:40,950 --> 00:04:43,510
Saya akan mempunyai untuk memulakan pada awal-awal senarai

72
00:04:43,510 --> 00:04:48,930
dan bekerja cara saya melalui mengira nod oleh nod sehingga saya mendapati yang keempat.

73
00:04:48,930 --> 00:04:55,870
>> Dalam usaha untuk mendapatkan akses prestasi yang lebih baik daripada senarai berkaitan -

74
00:04:55,870 --> 00:04:59,360
tetapi juga mengekalkan beberapa faedah yang kita terpaksa

75
00:04:59,360 --> 00:05:01,800
dari segi masa kemasukan dari senarai berkaitan -

76
00:05:01,800 --> 00:05:05,750
pokok binari akan perlu untuk menggunakan memori yang lebih sedikit.

77
00:05:05,750 --> 00:05:11,460
Secara khususnya, bukan hanya mempunyai satu penunjuk dalam nod pokok binari -

78
00:05:11,460 --> 00:05:13,350
seperti senarai berpaut-nod tidak -

79
00:05:13,350 --> 00:05:16,950
kita akan menambah penunjuk kedua kepada nod pokok binari.

80
00:05:16,950 --> 00:05:19,950
Bukannya hanya mempunyai satu penunjuk kepada elemen seterusnya,

81
00:05:19,950 --> 00:05:24,420
kita akan mempunyai penunjuk kepada kanak-kanak kiri dan kanak-kanak yang betul.

82
00:05:24,420 --> 00:05:26,560
>> Mari melukis gambar untuk melihat apa yang sebenarnya kelihatan seperti.

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

84
00:05:31,350 --> 00:05:37,150
Satu nod pokok binari akan bermula dengan hanya kotak yang mudah.

85
00:05:37,150 --> 00:05:40,940
Ia akan mempunyai ruang untuk nilai,

86
00:05:40,940 --> 00:05:47,280
dan kemudian ia juga akan mempunyai ruang untuk kanak-kanak kiri dan kanak-kanak yang betul.

87
00:05:47,280 --> 00:05:49,280
Saya akan melabelkan mereka di sini.

88
00:05:49,280 --> 00:05:57,560
Kami akan mempunyai anak kiri, dan kemudian kita akan mempunyai kanak-kanak yang betul.

89
00:05:57,560 --> 00:05:59,920
Terdapat banyak cara yang berbeza untuk melakukan ini.

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

91
00:06:02,050 --> 00:06:06,460
Saya sebenarnya akan menarik ia seperti yang saya lakukan di sini di bahagian bawah

92
00:06:06,460 --> 00:06:10,910
di mana saya akan mempunyai nilai di atas,

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

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

95
00:06:16,060 --> 00:06:20,250
Akan kembali kepada gambarajah ini atas,

96
00:06:20,250 --> 00:06:22,560
kita mempunyai nilai di atas,

97
00:06:22,560 --> 00:06:25,560
maka kita mempunyai penunjuk kiri-anak, dan kemudian kita mempunyai penunjuk hak kanak-kanak.

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

99
00:06:30,110 --> 00:06:33,110
kita bercakap mengenai lukisan nod yang mempunyai nilai 7,

100
00:06:33,110 --> 00:06:39,750
dan kemudian penunjuk kiri kanak-kanak itu adalah batal, dan penunjuk hak-anak itu adalah batal.

101
00:06:39,750 --> 00:06:46,040
Kita boleh menulis NULL modal di dalam ruang bagi

102
00:06:46,040 --> 00:06:51,610
kedua-dua kanak-kanak kiri dan kanak-kanak yang betul, atau kita boleh menarik ini slash pepenjuru

103
00:06:51,610 --> 00:06:53,750
melalui setiap kotak untuk menunjukkan bahawa ia adalah batal.

104
00:06:53,750 --> 00:06:57,560
Saya akan berbuat demikian hanya kerana itulah mudah.

105
00:06:57,560 --> 00:07:03,700
Apa yang anda lihat di sini adalah dua cara diagramming nod pokok binari yang sangat mudah

106
00:07:03,700 --> 00:07:07,960
di mana kita mempunyai nilai 7 dan tunjuk ajar anak batal.

107
00:07:07,960 --> 00:07:15,220
>> Bahagian kedua ceramah spesifikasi kami tentang bagaimana dengan dikaitkan senarai -

108
00:07:15,220 --> 00:07:18,270
ingat, kita hanya terpaksa untuk berpegang kepada unsur yang pertama dalam senarai

109
00:07:18,270 --> 00:07:20,270
ingat seluruh senarai -

110
00:07:20,270 --> 00:07:26,140
dan begitu juga, dengan pokok binari, kita hanya perlu untuk berpegang kepada satu penunjuk kepada pokok

111
00:07:26,140 --> 00:07:31,120
dalam usaha untuk mengekalkan kawalan ke atas keseluruhan struktur data.

112
00:07:31,120 --> 00:07:36,150
Ini elemen khas pokok dipanggil nod akar pokok itu.

113
00:07:36,150 --> 00:07:43,360
Sebagai contoh, jika nod satu - nod ini mengandungi nilai 7

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

115
00:07:45,500 --> 00:07:47,360
nilai hanya di pokok kami,

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

117
00:07:50,390 --> 00:07:52,240
Ia adalah permulaan yang sangat pokok kami.

118
00:07:52,240 --> 00:07:58,530
Kita boleh melihat ini sedikit lebih jelas apabila kita mula menambah lebih nod ke pokok kita.

119
00:07:58,530 --> 00:08:01,510
Biar saya tarik sehingga halaman baru.

120
00:08:01,510 --> 00:08:05,000
>> Sekarang kita pergi untuk menarik pokok yang mempunyai 7 pada akar,

121
00:08:05,000 --> 00:08:10,920
dan 3 dalam anak kiri, dan 9 dalam kanak-kanak yang betul.

122
00:08:10,920 --> 00:08:13,500
Sekali lagi, ini adalah agak mudah.

123
00:08:13,500 --> 00:08:26,510
Kami telah mendapat 7, lukiskan nod bagi 3, nod for 9,

124
00:08:26,510 --> 00:08:32,150
dan saya akan menetapkan penunjuk kiri-anak 7 menuding kepada nod mengandungi 3,

125
00:08:32,150 --> 00:08:37,850
dan penunjuk-anak kanan nod yang mengandungi 7 nod mengandungi 9.

126
00:08:37,850 --> 00:08:42,419
Sekarang, sejak 3 dan 9 tidak mempunyai mana-mana kanak-kanak,

127
00:08:42,419 --> 00:08:48,500
kita pergi untuk menetapkan semua petunjuk anak mereka menjadi batal.

128
00:08:48,500 --> 00:08:56,060
Sini, akar pokok kita sepadan dengan nod mengandungi nombor 7.

129
00:08:56,060 --> 00:09:02,440
Anda boleh melihat bahawa jika semua yang kita ada adalah penunjuk kepada nod akar itu,

130
00:09:02,440 --> 00:09:07,330
maka kita boleh berjalan melalui pokok kami dan mengakses nod kedua-dua kanak-kanak -

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

132
00:09:10,630 --> 00:09:14,820
Tidak perlu untuk mengekalkan petunjuk untuk setiap nod tunggal pada pokok itu.

133
00:09:14,820 --> 00:09:22,080
Baiklah. Sekarang kita pergi untuk menambah nod lain kepada gambarajah ini.

134
00:09:22,080 --> 00:09:25,370
Kami akan menambah nod mengandungi 6,

135
00:09:25,370 --> 00:09:34,140
dan kita akan menambah ini sebagai kanak-kanak yang betul nod mengandungi 3.

136
00:09:34,140 --> 00:09:41,850
Untuk berbuat demikian, saya akan memadam bahawa penunjuk nol dalam 3 nod

137
00:09:41,850 --> 00:09:47,750
dan wayar sehingga ia menuding kepada nod mengandungi 6. Baiklah.

138
00:09:47,750 --> 00:09:53,800
>> Pada ketika ini, marilah kita pergi lebih sedikit istilah.

139
00:09:53,800 --> 00:09:58,230
Untuk memulakan, sebab bahawa ini dipanggil pokok binari khususnya

140
00:09:58,230 --> 00:10:00,460
adalah bahawa ia mempunyai dua penunjuk kanak-kanak.

141
00:10:00,460 --> 00:10:06,020
Terdapat lain-lain jenis pokok yang mempunyai lebih banyak petunjuk kanak-kanak.

142
00:10:06,020 --> 00:10:10,930
Khususnya, anda melakukan 'cuba' dalam Set Masalah 5.

143
00:10:10,930 --> 00:10:19,310
Anda akan melihat bahawa dalam mencuba bahawa, anda mempunyai 27 penunjuk berbeza kepada kanak-kanak yang berbeza -

144
00:10:19,310 --> 00:10:22,410
salah satu bagi setiap 26 huruf dalam abjad Inggeris,

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

146
00:10:25,410 --> 00:10:28,900
demikian, itu serupa kepada sejenis pokok.

147
00:10:28,900 --> 00:10:34,070
Tetapi di sini, sejak binari itu, kita hanya mempunyai dua penunjuk kanak-kanak.

148
00:10:34,070 --> 00:10:37,880
>> Di samping itu kepada nod akar ini bahawa kita bercakap tentang,

149
00:10:37,880 --> 00:10:41,470
kita juga telah telah membuang seluruh istilah ini 'kanak-kanak.'

150
00:10:41,470 --> 00:10:44,470
Apakah maknanya untuk satu nod untuk menjadi kanak-kanak nod lain?

151
00:10:44,470 --> 00:10:54,060
Ia bermaksud bahawa nod kanak-kanak adalah seorang kanak-kanak nod lain

152
00:10:54,060 --> 00:10:58,760
jika itu nod lain mempunyai salah satu petunjuk kanak-kanak bersedia untuk menunjukkan kepada nod tersebut.

153
00:10:58,760 --> 00:11:01,230
Untuk meletakkan ini ke dalam terma yang lebih konkrit,

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

155
00:11:11,170 --> 00:11:14,510
Jika kita memikirkan apa yang anak-anak 7 -

156
00:11:14,510 --> 00:11:18,510
baik, kita melihat bahawa 7 mempunyai penunjuk kepada 3 dan penunjuk hingga 9,

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

158
00:11:22,190 --> 00:11:26,650
Sembilan tidak mempunyai anak kerana petunjuk kanak-kanak adalah batal,

159
00:11:26,650 --> 00:11:30,940
dan 3 hanya mempunyai seorang kanak-kanak, 6.

160
00:11:30,940 --> 00:11:37,430
Enam juga tidak mempunyai anak kerana kedua-dua petunjuk yang adalah batal, yang kita akan menarik sekarang.

161
00:11:37,430 --> 00:11:45,010
>> Selain itu, kita juga bercakap mengenai ibu bapa nod tertentu,

162
00:11:45,010 --> 00:11:51,100
dan ini adalah, seperti yang anda harapkan, sebaliknya perihal kanak-kanak ini.

163
00:11:51,100 --> 00:11:58,620
Setiap nod mempunyai hanya satu ibu bapa bukan dua seperti yang anda jangkakan dengan manusia.

164
00:11:58,620 --> 00:12:03,390
Sebagai contoh, ibu bapa 3 ialah 7.

165
00:12:03,390 --> 00:12:10,800
Ibu bapa 9 adalah juga 7, dan ibu bapa 6 3. Tidak banyak kepadanya.

166
00:12:10,800 --> 00:12:15,720
Kami juga mempunyai terma untuk bercakap tentang datuk nenek dan cucu,

167
00:12:15,720 --> 00:12:18,210
dan lebih amnya kita bercakap mengenai nenek moyang

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

169
00:12:20,960 --> 00:12:25,710
Moyang nod atau nenek moyang, sebaliknya, nod -

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

171
00:12:32,730 --> 00:12:36,640
Sebagai contoh, jika saya mencari di 6 nod,

172
00:12:36,640 --> 00:12:46,430
maka nenek moyang akan menjadi kedua-dua 3 dan 7.

173
00:12:46,430 --> 00:12:55,310
Nenek moyang 9, sebagai contoh, adalah - jika saya mencari di 9 nod -

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

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

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

177
00:13:05,430 --> 00:13:11,020
maka saya perlu melihat semua nod bawahnya.

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

179
00:13:16,950 --> 00:13:24,170
>> Istilah terakhir yang kita akan bercakap tentang adalah idea ini menjadi adik-beradik.

180
00:13:24,170 --> 00:13:27,980
Adik-beradik - jenis berikut bersama-sama atas terma keluarga -

181
00:13:27,980 --> 00:13:33,150
adalah nod yang berada di tahap yang sama di pokok itu.

182
00:13:33,150 --> 00:13:42,230
Jadi, 3 dan 9 adik-beradik kerana mereka berada di tahap yang sama dalam pokok itu.

183
00:13:42,230 --> 00:13:46,190
Mereka kedua-duanya mempunyai ibu bapa yang sama, 7.

184
00:13:46,190 --> 00:13:51,400
6 tidak mempunyai adik-beradik kerana 9 tidak mempunyai apa-apa kanak-kanak.

185
00:13:51,400 --> 00:13:55,540
Dan 7 tidak mempunyai apa-apa adik-beradik kerana ia adalah akar pokok kami,

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

187
00:13:59,010 --> 00:14:02,260
Selama 7 hingga mempunyai adik-beradik di sana akan menjadi nod di atas 7.

188
00:14:02,260 --> 00:14:07,480
Terdapat akan menjadi ibu bapa 7, di mana 7 tidak lagi akan menjadi akar pokok.

189
00:14:07,480 --> 00:14:10,480
Kemudian bahawa ibu bapa baru 7 juga akan perlu untuk mempunyai anak,

190
00:14:10,480 --> 00:14:16,480
dan kanak-kanak itu kemudian akan menjadi adik-beradik daripada 7.

191
00:14:16,480 --> 00:14:21,040
>> Baiklah. Bergerak ke atas.

192
00:14:21,040 --> 00:14:24,930
Apabila kita memulakan perbincangan kami pokok binari,

193
00:14:24,930 --> 00:14:28,790
kita bercakap tentang bagaimana kita akan menggunakan mereka untuk

194
00:14:28,790 --> 00:14:32,800
mendapat kelebihan berbanding kedua-dua tatasusunan dan senarai yang berkaitan.

195
00:14:32,800 --> 00:14:37,220
Dan cara kita pergi untuk berbuat demikian adalah dengan harta ini pesanan.

196
00:14:37,220 --> 00:14:41,080
Kami mengatakan bahawa pokok binari diperintahkan, mengikut spesifikasi,

197
00:14:41,080 --> 00:14:45,740
jika untuk setiap nod dalam pokok kami, semua keturunan di sebelah kiri -

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

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

200
00:14:54,510 --> 00:14:57,770
kanak-kanak yang betul dan semua keturunan kanak-kanak yang betul -

201
00:14:57,770 --> 00:15:02,800
mempunyai nod yang lebih besar daripada nilai nod semasa yang kita sedang melihat.

202
00:15:02,800 --> 00:15:07,850
Hanya untuk kesederhanaan, kita akan menganggap bahawa tidak ada mana-mana nod pendua di pokok kita.

203
00:15:07,850 --> 00:15:11,180
Sebagai contoh, dalam pokok ini kita tidak akan berurusan dengan kes

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

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

206
00:15:16,720 --> 00:15:24,390
Dalam kes ini, anda akan melihat bahawa pokok ini memang diperintahkan.

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

208
00:15:26,510 --> 00:15:29,720
Semua kiri 7 -

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

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

211
00:15:40,450 --> 00:15:49,410
nilai-nilai kedua-duanya adalah kurang daripada 7, dan segala-galanya yang betul - yang hanya 9 ini -

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

213
00:15:53,450 --> 00:15:58,650
>> Ini bukan pokok hanya diperintahkan yang mengandungi nilai-nilai,

214
00:15:58,650 --> 00:16:03,120
tetapi mari kita lukiskan lebih sedikit daripada mereka.

215
00:16:03,120 --> 00:16:05,030
Terdapat sebenarnya adalah sekumpulan keseluruhan cara-cara yang boleh kita lakukan ini.

216
00:16:05,030 --> 00:16:09,380
Saya akan menggunakan trengkas hanya untuk menjaga perkara-perkara yang mudah di mana -

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

218
00:16:11,520 --> 00:16:14,220
Saya hanya akan menarik nombor dan tambah anak panah yang menghubungkan mereka.

219
00:16:14,220 --> 00:16:22,920
Untuk memulakan, kita hanya akan menulis pokok asal kita sekali lagi di mana kita mempunyai 7, dan kemudian 3,

220
00:16:22,920 --> 00:16:25,590
dan kemudian 3 menunjukkan kembali kepada hak kepada 6,

221
00:16:25,590 --> 00:16:30,890
dan 7 mempunyai seorang kanak-kanak yang betul adalah 9.

222
00:16:30,890 --> 00:16:33,860
Baiklah. Apa cara lain yang kita boleh menulis pokok ini?

223
00:16:33,860 --> 00:16:38,800
Sebaliknya mempunyai 3 menjadi anak kiri 7,

224
00:16:38,800 --> 00:16:41,360
kita juga boleh mempunyai 6 menjadi anak kiri 7,

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

226
00:16:44,470 --> 00:16:48,520
Yang akan kelihatan seperti pokok ini di sini di mana saya telah mendapat 7,

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

228
00:16:57,860 --> 00:17:01,490
Kita juga tidak perlu mempunyai 7 sebagai nod akar kami.

229
00:17:01,490 --> 00:17:03,860
Kita juga boleh mempunyai 6 sebagai nod akar kita.

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

231
00:17:06,470 --> 00:17:09,230
Jika kita pergi untuk mengekalkan harta yang diperintahkan,

232
00:17:09,230 --> 00:17:12,970
segala-galanya ke kiri sebanyak 6 telah menjadi kurang daripada ia.

233
00:17:12,970 --> 00:17:16,540
Terdapat hanya satu kemungkinan, dan itulah 3.

234
00:17:16,540 --> 00:17:19,869
Tetapi kemudian sebagai kanak-kanak yang betul 6, kita mempunyai dua kemungkinan.

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

236
00:17:25,380 --> 00:17:28,850
atau kita boleh menarik - seperti saya kira-kira untuk melakukan di sini -

237
00:17:28,850 --> 00:17:34,790
di mana kita mempunyai 9 sebagai kanak-kanak yang betul daripada 6,

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

239
00:17:39,050 --> 00:17:44,240
>> Sekarang, 7 dan 6 tidak nilai hanya boleh dilakukan untuk akar.

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

241
00:17:50,200 --> 00:17:52,240
Apakah yang akan berlaku jika 3 adalah pada akar?

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

243
00:17:54,390 --> 00:17:58,440
Tiga tidak mempunyai sebarang nilai yang kurang daripada itu,

244
00:17:58,440 --> 00:18:02,070
supaya seluruh sebelah kiri pokok itu hanya akan menjadi batal.

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

246
00:18:03,230 --> 00:18:07,220
Ke kanan, kita boleh menyenaraikan perkara-perkara dalam tertib menaik.

247
00:18:07,220 --> 00:18:15,530
Kita boleh mempunyai 3, maka 6, maka 7, kemudian 9.

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

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

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

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

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

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

254
00:19:06,980 --> 00:19:12,490
>> Satu perkara yang menarik perhatian anda di sini adalah

255
00:19:12,490 --> 00:19:14,510
bahawa pokok-pokok adalah sedikit pelik-cari.

256
00:19:14,510 --> 00:19:17,840
Khususnya, jika kita melihat 4 pokok di sebelah kanan -

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

258
00:19:20,930 --> 00:19:28,410
pokok-pokok kelihatan hampir tepat seperti senarai berkaitan.

259
00:19:28,410 --> 00:19:32,670
Setiap nod mempunyai hanya seorang kanak-kanak,

260
00:19:32,670 --> 00:19:38,950
dan sebagainya kita tidak mempunyai apa-apa struktur ini seperti pokok yang kita lihat, sebagai contoh,

261
00:19:38,950 --> 00:19:44,720
 dalam pokok ini satu tunggal di sini di sebelah kiri bahagian bawah.

262
00:19:44,720 --> 00:19:52,490
Pokok-pokok sebenarnya dipanggil merosot pokok binari,

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

264
00:19:54,170 --> 00:19:56,730
terutamanya jika anda pergi untuk mengambil kursus sains komputer lain.

265
00:19:56,730 --> 00:19:59,670
Ini pokok merosot.

266
00:19:59,670 --> 00:20:03,780
Mereka tidak sangat berguna kerana, sesungguhnya, struktur ini meminjamkan sendiri

267
00:20:03,780 --> 00:20:08,060
 untuk lookup serupa dengan senarai dikaitkan kali.

268
00:20:08,060 --> 00:20:13,050
Kita tidak dapat untuk mengambil kesempatan daripada memori tambahan - ini penunjuk tambahan -

269
00:20:13,050 --> 00:20:18,840
kerana struktur kita menjadi buruk dalam cara ini.

270
00:20:18,840 --> 00:20:24,700
Bukannya pergi dan menarik keluar pokok binari yang mempunyai 9 pada akar,

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

272
00:20:27,220 --> 00:20:32,380
kami sebaliknya, pada ketika ini, akan bercakap sedikit tentang istilah ini lain

273
00:20:32,380 --> 00:20:36,150
yang kita gunakan apabila bercakap tentang pokok-pokok, yang dipanggil ketinggian.

274
00:20:36,150 --> 00:20:45,460
>> Ketinggian pokok adalah jarak dari akar kepada nod yang paling-jauh,

275
00:20:45,460 --> 00:20:48,370
atau sebaliknya bilangan hop yang anda akan perlu membuat untuk

276
00:20:48,370 --> 00:20:53,750
bermula dari akar dan kemudian berakhir pada nod yang paling jauh di pokok itu.

277
00:20:53,750 --> 00:20:57,330
Jika kita lihat di beberapa pokok-pokok yang kami telah disediakan di sini,

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

279
00:21:07,870 --> 00:21:14,510
maka kita perlu membuat 1 hop untuk sampai kepada 6, hop kedua untuk mendapatkan kepada 7,

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

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

282
00:21:26,120 --> 00:21:30,640
Kita boleh melakukan senaman sama untuk pokok-pokok lain yang digariskan dengan hijau ini,

283
00:21:30,640 --> 00:21:40,100
dan kita lihat bahawa ketinggian semua pokok-pokok juga memang 3.

284
00:21:40,100 --> 00:21:45,230
Itu sebahagian daripada apa yang membuatkan mereka merosot -

285
00:21:45,230 --> 00:21:53,750
bahawa ketinggian mereka adalah hanya satu kurang daripada bilangan nod di seluruh pokok.

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

287
00:21:58,400 --> 00:22:03,920
kita lihat bahawa nod daun paling jauh adalah 6 dan 9 -

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

289
00:22:06,940 --> 00:22:11,760
Jadi, untuk mendapatkan dari nod akar sama ada 6 atau 9,

290
00:22:11,760 --> 00:22:17,840
kita perlu membuat satu hop untuk mendapatkan kepada 7 dan kemudian hop kedua untuk mendapatkan kepada 9,

291
00:22:17,840 --> 00:22:21,240
dan begitu juga, hanya hop kedua daripada 7 untuk mendapatkan kepada 6.

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

293
00:22:29,080 --> 00:22:35,330
Anda boleh kembali dan berbuat demikian untuk semua pokok-pokok yang lain yang kita telah dibincangkan sebelum ini

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

295
00:22:37,480 --> 00:22:42,500
dan anda akan mendapati bahawa ketinggian semua pokok-pokok juga 2.

296
00:22:42,500 --> 00:22:46,320
>> Sebab kita telah bercakap tentang mengarahkan pokok binari

297
00:22:46,320 --> 00:22:50,250
dan mengapa mereka sejuk kerana anda boleh mencari melalui mereka dalam

298
00:22:50,250 --> 00:22:53,810
cara yang sangat serupa dengan mencari lebih pelbagai disusun.

299
00:22:53,810 --> 00:22:58,720
Ini adalah di mana kita bercakap tentang mendapatkan masa pencarian yang lebih baik

300
00:22:58,720 --> 00:23:02,730
senarai lebih mudah dikaitkan.

301
00:23:02,730 --> 00:23:05,010
Dengan senarai berkaitan - jika anda mahu untuk mencari elemen tertentu -

302
00:23:05,010 --> 00:23:07,470
anda berada pada terbaik akan melakukan beberapa jenis carian linear

303
00:23:07,470 --> 00:23:10,920
di mana anda bermula pada awal senarai dan hop satu demi satu -

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

305
00:23:12,620 --> 00:23:16,060
melalui senarai keseluruhan sehingga anda mencari apa sahaja yang anda sedang mencari.

306
00:23:16,060 --> 00:23:19,440
Manakala, jika anda mempunyai pokok binari yang disimpan dalam format ini bagus,

307
00:23:19,440 --> 00:23:23,300
anda sebenarnya boleh mendapatkan lebih banyak carian binari berlaku

308
00:23:23,300 --> 00:23:25,160
di mana anda membahagi dan menakluk

309
00:23:25,160 --> 00:23:29,490
dan carian melalui separuh pokok pada setiap langkah yang sesuai.

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

311
00:23:32,840 --> 00:23:38,850
>> Jika kita mempunyai - sekali lagi, akan kembali kepada pokok asal kita -

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

313
00:23:46,710 --> 00:23:51,740
dan di bawah 3, kami mempunyai 6.

314
00:23:51,740 --> 00:24:01,880
Jika kita mahu mencari nombor 6 dalam pokok ini, kita akan bermula di akar.

315
00:24:01,880 --> 00:24:08,910
Kami akan membandingkan nilai kita sedang mencari untuk, katakan 6,

316
00:24:08,910 --> 00:24:12,320
kepada nilai yang disimpan di dalam nod bahawa kita sedang melihat, 7,

317
00:24:12,320 --> 00:24:21,200
mendapati bahawa 6 memang kurang daripada 7, jadi kita akan bergerak ke kiri.

318
00:24:21,200 --> 00:24:25,530
Jika nilai 6 telah lebih daripada 7, kita akan telah sebaliknya berpindah ke kanan.

319
00:24:25,530 --> 00:24:29,770
Sejak kita tahu bahawa kerana struktur pokok binari kita diperintahkan -

320
00:24:29,770 --> 00:24:33,910
semua nilai kurang daripada 7 akan disimpan ke kiri 7,

321
00:24:33,910 --> 00:24:40,520
tidak perlu bersusah payah mencari melalui sebelah kanan pokok.

322
00:24:40,520 --> 00:24:43,780
Apabila kita bergerak ke kiri dan kami kini pada nod mengandungi 3,

323
00:24:43,780 --> 00:24:48,110
yang boleh kita lakukan bahawa perbandingan yang sama sekali lagi di mana kita bandingkan 3 dan 6.

324
00:24:48,110 --> 00:24:52,430
Dan kita dapati bahawa manakala 6 - nilai yang kita cari - adalah lebih besar daripada 3,

325
00:24:52,430 --> 00:24:58,580
kita boleh pergi ke sebelah kanan nod mengandungi 3.

326
00:24:58,580 --> 00:25:02,670
Tiada sebelah kiri di sini, jadi kita boleh diabaikan bahawa.

327
00:25:02,670 --> 00:25:06,510
Tetapi kita hanya tahu bahawa kerana kita sedang melihat pokok itu sendiri,

328
00:25:06,510 --> 00:25:08,660
dan kita dapat melihat bahawa pokok itu tidak mempunyai anak.

329
00:25:08,660 --> 00:25:13,640
>> Ia juga agak mudah untuk mencari 6 dalam pokok ini jika kita melakukannya diri kita sebagai manusia,

330
00:25:13,640 --> 00:25:16,890
tetapi mari kita mengikuti proses ini mekanikal seperti komputer akan lakukan

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

332
00:25:18,620 --> 00:25:26,200
Pada ketika ini, kami sedang mencari di nod yang mengandungi 6,

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

334
00:25:29,180 --> 00:25:31,740
demikian, sesungguhnya, kami telah menemui nod yang sesuai.

335
00:25:31,740 --> 00:25:35,070
Kami mendapati nilai 6 di pokok kita, dan kita boleh menghentikan carian kami.

336
00:25:35,070 --> 00:25:37,330
Pada ketika ini, bergantung kepada apa yang berlaku,

337
00:25:37,330 --> 00:25:41,870
kita boleh katakan, ya, kami telah menemui nilai 6, ia wujud di pokok kita.

338
00:25:41,870 --> 00:25:47,640
Atau, jika kita sedang merancang untuk memasukkan nod atau melakukan sesuatu, kita boleh berbuat demikian pada ketika ini.

339
00:25:47,640 --> 00:25:53,010
>> Mari kita buat pasangan lebih lookup hanya untuk melihat bagaimana kerja-kerja ini.

340
00:25:53,010 --> 00:25:59,390
Mari kita melihat apa yang berlaku jika kita adalah untuk mencuba dan mencari nilai 10.

341
00:25:59,390 --> 00:26:02,970
Jika kita melihat nilai 10, kita akan bermula di akar.

342
00:26:02,970 --> 00:26:07,070
Kami ingin melihat bahawa 10 adalah lebih besar daripada 7, jadi kita akan bergerak ke kanan.

343
00:26:07,070 --> 00:26:13,640
Kami ingin sampai kepada 9 dan bandingkan 9 kepada 10 dan melihat bahawa 9 memang kurang daripada 10.

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

345
00:26:16,210 --> 00:26:20,350
Tetapi pada masa ini, kita akan melihat bahawa kita berada di nod nol.

346
00:26:20,350 --> 00:26:23,080
Tiada apa-apa di sana. Tiada apa-apa di mana 10 harus.

347
00:26:23,080 --> 00:26:29,360
Ini adalah di mana kita boleh melaporkan kegagalan - bahawa terdapat sesungguhnya tidak 10 di pokok itu.

348
00:26:29,360 --> 00:26:35,420
Dan akhirnya, mari kita pergi melalui kes di mana kita sedang cuba untuk mencari 1 dalam pokok itu.

349
00:26:35,420 --> 00:26:38,790
Ini adalah serupa dengan apa yang berlaku jika kita melihat sehingga 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
Kami bermula pada 7 dan melihat bahawa 1 adalah kurang daripada 7, jadi kami bergerak ke kiri.

352
00:26:46,170 --> 00:26:51,750
Kami mendapat kepada 3 dan melihat bahawa 1 adalah kurang daripada 3, jadi sekali lagi kita cuba untuk bergerak ke kiri.

353
00:26:51,750 --> 00:26:59,080
Pada ketika ini kita mempunyai nod batal, jadi sekali lagi kita boleh melaporkan kegagalan.

354
00:26:59,080 --> 00:27:10,260
>> Jika anda ingin mengetahui lebih lanjut mengenai pokok binari,

355
00:27:10,260 --> 00:27:14,420
terdapat sekumpulan keseluruhan masalah menyeronokkan sedikit yang boleh anda lakukan dengan mereka.

356
00:27:14,420 --> 00:27:19,450
Saya cadangkan mengamalkan lukisan daripada gambar rajah ini satu demi satu

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

358
00:27:21,910 --> 00:27:25,060
kerana ini akan datang dalam berguna super

359
00:27:25,060 --> 00:27:27,480
bukan sahaja apabila anda melakukan pengekodan Huffman masalah set

360
00:27:27,480 --> 00:27:29,390
tetapi juga dalam kursus-kursus yang akan datang -

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

362
00:27:32,220 --> 00:27:38,000
dengan pen dan kertas atau, dalam kes ini, iPad dan stilus.

363
00:27:38,000 --> 00:27:41,000
>> Pada ketika ini walaupun, kita akan bergerak ke atas untuk melakukan beberapa amalan kod

364
00:27:41,000 --> 00:27:44,870
dan sebenarnya bermain dengan pokok-pokok binari dan lihat.

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

366
00:27:52,150 --> 00:27:58,480
Untuk bahagian ini seksyen itu, dan bukannya menggunakan CS50 Run atau CS50 Ruang,

367
00:27:58,480 --> 00:28:01,500
Saya akan menggunakan perkakas.

368
00:28:01,500 --> 00:28:04,950
>> Berikutan bersama-sama dengan spesifikasi Set Masalah,

369
00:28:04,950 --> 00:28:07,740
Saya melihat bahawa saya sepatutnya untuk membuka perkakas,

370
00:28:07,740 --> 00:28:11,020
pergi ke folder Dropbox saya, membuat folder yang dipanggil Seksyen 7,

371
00:28:11,020 --> 00:28:15,730
dan kemudian mewujudkan fail yang dipanggil binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Di sini kita pergi. Saya telah mendapat perkakas sudah terbuka.

373
00:28:22,050 --> 00:28:25,910
Saya akan tarik sehingga terminal.

374
00:28:25,910 --> 00:28:38,250
Saya akan pergi ke folder Dropbox, membuat direktori yang dipanggil Seksyen 7,

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

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

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

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

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

380
00:28:59,850 --> 00:29:03,080
bagi nod pokok binari yang mengandungi nilai int -

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

382
00:29:07,110 --> 00:29:11,740
Kami akan menggunakan ini boilerplate typedef bahawa kita telah dilakukan di sini

383
00:29:11,740 --> 00:29:14,420
bahawa anda harus mengiktiraf daripada Set Masalah 5 -

384
00:29:14,420 --> 00:29:19,190
jika anda melakukannya cara jadual hash program pengeja menakluk.

385
00:29:19,190 --> 00:29:22,540
Anda juga perlu mengiktiraf ia dari seksyen minggu lepas

386
00:29:22,540 --> 00:29:23,890
di mana kita bercakap mengenai senarai yang dipautkan.

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

388
00:29:27,870 --> 00:29:34,430
dan kami telah diberikan ini nod struct ini nama nod struct terlebih dahulu

389
00:29:34,430 --> 00:29:39,350
supaya kita boleh merujuk kepada ia kerana kita akan mahu mempunyai petunjuk nod struct

390
00:29:39,350 --> 00:29:45,740
sebagai sebahagian daripada struct kami, tetapi kami telah kemudian dikelilingi ini -

391
00:29:45,740 --> 00:29:47,700
atau sebaliknya, disertakan ini - dalam typedef

392
00:29:47,700 --> 00:29:54,600
supaya, kemudian dalam kod, kita boleh merujuk kepada struct ini hanya sebagai nod bukannya nod struct.

393
00:29:54,600 --> 00:30:03,120
>> Ini akan menjadi sangat serupa dengan definisi berseorangan berkaitan senarai yang kita lihat minggu lepas.

394
00:30:03,120 --> 00:30:20,070
Untuk melakukan ini, mari kita mulakan dengan menulis boilerplate.

395
00:30:20,070 --> 00:30:23,840
Kita tahu bahawa kita perlu mempunyai nilai integer,

396
00:30:23,840 --> 00:30:32,170
jadi kita akan dimasukkan ke dalam nilai int, dan kemudian bukannya mempunyai hanya satu penunjuk kepada elemen seterusnya -

397
00:30:32,170 --> 00:30:33,970
seperti yang kita lakukan dengan senarai secara tunggal berkaitan -

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

399
00:30:38,110 --> 00:30:42,880
Itu agak mudah juga - struct nod kanak-kanak * kiri;

400
00:30:42,880 --> 00:30:51,190
dan struct nod * kanak-kanak yang betul;. Sejuk.

401
00:30:51,190 --> 00:30:54,740
Yang kelihatan seperti satu permulaan yang cukup baik.

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

403
00:30:58,530 --> 00:31:05,030
>> Sekarang kita perlu mengisytiharkan * nod pembolehubah global untuk akar pokok.

404
00:31:05,030 --> 00:31:10,590
Kami akan membuat global ini sama seperti kita membuat penunjuk pertama dalam senarai dikaitkan juga global kami.

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

406
00:31:12,690 --> 00:31:16,180
kita tidak perlu untuk memastikan lulus sekitar akar ini -

407
00:31:16,180 --> 00:31:19,620
walaupun kita akan melihat bahawa jika anda mahu untuk menulis fungsi-fungsi rekursif,

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

409
00:31:22,830 --> 00:31:28,090
dan bukannya memulakan tempatan dalam fungsi utama anda.

410
00:31:28,090 --> 00:31:31,960
Tetapi, kami akan melakukannya global untuk memulakan.

411
00:31:31,960 --> 00:31:39,920
Sekali lagi, kita akan memberikan beberapa ruang, dan saya akan mengisytiharkan akar * nod.

412
00:31:39,920 --> 00:31:46,770
Hanya untuk memastikan bahawa saya tidak meninggalkan ini tidak diisytiharkan, saya akan menetapkan ia sama untuk menyeimbangkan.

413
00:31:46,770 --> 00:31:52,210
Kini, fungsi utama - yang kami akan menulis benar-benar cepat di sini -

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

415
00:32:00,450 --> 00:32:10,640
dan saya akan mula mengisytiharkan pelbagai argv saya sebagai malar hanya supaya saya tahu

416
00:32:10,640 --> 00:32:14,550
bahawa hujah mereka adalah hujah bahawa saya mungkin tidak mahu untuk mengubah suai.

417
00:32:14,550 --> 00:32:18,390
Jika saya mahu mengubah mereka saya mungkin perlu membuat salinan mereka.

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

419
00:32:21,740 --> 00:32:25,440
Ia adalah denda sama ada cara. Ia adalah baik untuk meninggalkan ia sebagai - tinggalkan malar jika anda ingin.

420
00:32:25,440 --> 00:32:28,630
Saya biasanya meletakkan ia dalam hanya supaya saya mengingatkan diri

421
00:32:28,630 --> 00:32:33,650
 bahawa saya mungkin tidak mahu mengubah hujah-hujah mereka.

422
00:32:33,650 --> 00:32:39,240
>> Seperti biasa, saya akan menyertakan pulangan 0 selaras pada akhir utama.

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

424
00:32:45,730 --> 00:32:48,900
Sebagaimana keadaannya sekarang, saya telah mendapat pointer yang ditetapkan untuk menyeimbangkan,

425
00:32:48,900 --> 00:32:52,970
jadi ia menunjuk pada apa-apa.

426
00:32:52,970 --> 00:32:57,480
Dalam usaha untuk benar-benar mula membina nod,

427
00:32:57,480 --> 00:32:59,250
Saya mula-mula perlu untuk memperuntukkan memori untuk itu.

428
00:32:59,250 --> 00:33:05,910
Saya akan berbuat demikian dengan membuat ingatan pada timbunan menggunakan malloc.

429
00:33:05,910 --> 00:33:10,660
Saya akan menetapkan akar yang sama dengan hasil malloc,

430
00:33:10,660 --> 00:33:19,550
dan saya akan menggunakan pengendali sizeof untuk mengira saiz nod.

431
00:33:19,550 --> 00:33:24,990
Sebab itu saya menggunakan nod sizeof berbanding, katakan,

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
adalah kerana saya ingin kod saya untuk menjadi seperti yang serasi sebagai mungkin.

434
00:33:40,820 --> 00:33:44,540
Saya mahu menjadi mampu untuk mengambil fail ini c, menyusun perkakas,

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

436
00:33:48,820 --> 00:33:52,040
atau pada seni bina yang sama sekali berbeza -

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

438
00:33:54,640 --> 00:33:59,510
>> Jika saya membuat andaian mengenai saiz pembolehubah -

439
00:33:59,510 --> 00:34:02,070
saiz int atau saiz penunjuk -

440
00:34:02,070 --> 00:34:06,070
maka saya juga membuat andaian mengenai jenis seni bina

441
00:34:06,070 --> 00:34:10,440
di mana kod saya berjaya boleh mengumpul apabila berjalan.

442
00:34:10,440 --> 00:34:15,030
Sentiasa gunakan sizeof berbanding manual menjumlahkan bidang struct.

443
00:34:15,030 --> 00:34:20,500
Sebab lain adalah bahawa terdapat juga mungkin padding bahawa pengkompil meletakkan ke dalam struct.

444
00:34:20,500 --> 00:34:26,570
Walaupun hanya menjumlahkan bidang individu bukan sesuatu yang anda biasanya mahu lakukan,

445
00:34:26,570 --> 00:34:30,340
jadi, memadam garisan itu.

446
00:34:30,340 --> 00:34:33,090
Kini, untuk benar-benar memulakan ini nod akar,

447
00:34:33,090 --> 00:34:36,489
Saya akan mempunyai untuk palam dalam nilai-nilai bagi setiap bidang yang berbeza.

448
00:34:36,489 --> 00:34:41,400
Sebagai contoh, untuk nilai yang saya tahu saya mahu memulakan hingga 7,

449
00:34:41,400 --> 00:34:46,920
dan buat masa sekarang saya akan menetapkan kanak-kanak kiri menjadi batal

450
00:34:46,920 --> 00:34:55,820
dan kanak-kanak yang betul juga menjadi batal. Hebat!

451
00:34:55,820 --> 00:35:02,670
Kami telah dilakukan bahawa sebahagian daripada spesifikasi.

452
00:35:02,670 --> 00:35:07,390
>> Spesifikasi turun di bahagian bawah halaman 3 meminta saya untuk mewujudkan tiga nod lagi -

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

454
00:35:10,600 --> 00:35:14,210
dan kemudian wayar mereka supaya ia kelihatan sama seperti gambar rajah pokok kami

455
00:35:14,210 --> 00:35:17,120
bahawa kita telah bercakap tentang sebelumnya.

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

457
00:35:20,450 --> 00:35:26,270
Anda akan melihat benar-benar cepat bahawa saya akan mula menulis sekumpulan kod pendua.

458
00:35:26,270 --> 00:35:32,100
Saya akan mewujudkan * nod dan saya akan memanggilnya 3.

459
00:35:32,100 --> 00:35:36,000
Saya akan menetapkan ia sama dengan malloc (sizeof (nod)).

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

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

462
00:35:54,780 --> 00:36:01,150
Itu kelihatan agak serupa untuk Memulakan akar, dan itulah apa

463
00:36:01,150 --> 00:36:05,760
Saya akan perlu lakukan jika saya mula Memulakan 6 dan 9 serta.

464
00:36:05,760 --> 00:36:20,720
Saya akan melakukan yang benar-benar cepat di sini - sebenarnya, saya akan melakukan satu salinan dan tampal sedikit,

465
00:36:20,720 --> 00:36:46,140
dan memastikan bahawa saya - mengapa.

466
00:36:46,470 --> 00:37:09,900
 Kini, saya telah mendapat ia disalin dan saya boleh pergi ke hadapan dan menetapkan ini sama dengan 6.

467
00:37:09,900 --> 00:37:14,670
Anda boleh melihat bahawa ini mengambil seketika dan tidak super cekap.

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

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

470
00:37:32,890 --> 00:37:37,360
>> Sekarang kita telah mendapat semua nod kami diwujudkan dan dimulakan.

471
00:37:37,360 --> 00:37:41,200
Kami telah mendapat akar kita menetapkan sama hingga 7, atau mengandungi nilai 7,

472
00:37:41,200 --> 00:37:46,510
kami mengandungi nod 3, nod kita mengandungi 6, dan nod kami yang mengandungi 9.

473
00:37:46,510 --> 00:37:50,390
Pada ketika ini, semua yang perlu kita lakukan adalah segala-galanya wayar sehingga.

474
00:37:50,390 --> 00:37:53,020
Sebab saya dimulakan semua petunjuk untuk menyeimbangkan hanya supaya saya memastikan bahawa

475
00:37:53,020 --> 00:37:56,260
Saya tidak mempunyai apa-apa petunjuk yang tidak diisytiharkan di sana oleh kemalangan.

476
00:37:56,260 --> 00:38:02,290
Dan juga kerana, pada ketika ini, saya hanya perlu untuk benar-benar menyambung nod antara satu sama lain -

477
00:38:02,290 --> 00:38:04,750
kepada orang-orang yang mereka sebenarnya disambungkan kepada - saya tidak perlu untuk pergi melalui dan membuat

478
00:38:04,750 --> 00:38:08,240
pasti bahawa semua nulls berada di sana di tempat-tempat yang sesuai.

479
00:38:08,240 --> 00:38:15,630
>> Bermula pada akar, saya tahu bahawa anak kiri akar ialah 3.

480
00:38:15,630 --> 00:38:21,250
Saya tahu bahawa kanak-kanak yang betul akar ialah 9.

481
00:38:21,250 --> 00:38:24,880
Selepas itu, satu-satunya kanak-kanak lain yang saya telah meninggalkan bimbang tentang

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

483
00:38:39,080 --> 00:38:44,670
Pada ketika ini, ia semua kelihatan agak baik.

484
00:38:44,670 --> 00:38:54,210
Kami akan memadam beberapa ayat-ayat ini.

485
00:38:54,210 --> 00:38:59,540
Sekarang segala-galanya kelihatan agak baik.

486
00:38:59,540 --> 00:39:04,240
Mari kita kembali spesifikasi kami dan lihat apa yang kita perlu lakukan seterusnya.

487
00:39:04,240 --> 00:39:07,610
>> Pada ketika ini, kita perlu menulis satu fungsi yang dipanggil 'mengandungi'

488
00:39:07,610 --> 00:39:14,150
dengan prototaip 'Mengandungi bool (int nilai)'.

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

490
00:39:17,060 --> 00:39:21,200
 jika pokok yang ditunjukkan oleh akar pembolehubah global kami

491
00:39:21,200 --> 00:39:26,950
 mengandungi nilai yang diluluskan ke dalam fungsi dan palsu sebaliknya.

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

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

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

495
00:39:40,130 --> 00:39:43,130
Kami akan meletakkan fungsi ini betul-betul di atas fungsi utama kita

496
00:39:43,130 --> 00:39:48,990
supaya kita tidak perlu melakukan apa-apa jenis prototaip.

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

498
00:39:55,960 --> 00:40:00,330
Terdapat kita pergi. Ada pengisytiharan boilerplate kami.

499
00:40:00,330 --> 00:40:02,900
Hanya untuk memastikan bahawa ini akan menyusun,

500
00:40:02,900 --> 00:40:06,820
Saya akan pergi ke hadapan dan hanya menetapkan ia sama untuk kembali palsu.

501
00:40:06,820 --> 00:40:09,980
Sekarang fungsi ini hanya tidak akan berbuat apa-apa dan sentiasa melaporkan bahawa

502
00:40:09,980 --> 00:40:14,010
nilai yang kita cari tidak di pokok itu.

503
00:40:14,010 --> 00:40:16,280
>> Pada ketika ini, ia mungkin idea yang baik -

504
00:40:16,280 --> 00:40:19,600
kerana kita telah menulis sejumlah besar kod dan kita tidak cuba menguji lagi -

505
00:40:19,600 --> 00:40:22,590
untuk memastikan bahawa ia semua menyusun.

506
00:40:22,590 --> 00:40:27,460
Terdapat beberapa perkara yang perlu kita lakukan untuk memastikan bahawa ini sebenarnya akan menyusun.

507
00:40:27,460 --> 00:40:33,530
Pertama, lihat jika kita telah menggunakan mana-mana fungsi dalam mana-mana perpustakaan yang telah kita belum dimasukkan.

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

509
00:40:37,940 --> 00:40:43,310
dan kemudian kami telah juga telah menggunakan jenis ini - jenis ini tidak standard yang dipanggil 'bool' -

510
00:40:43,310 --> 00:40:45,750
yang dimasukkan ke dalam fail pengepala bool standard.

511
00:40:45,750 --> 00:40:53,250
Kita pasti mahu termasuk bool.h standard bagi jenis bool,

512
00:40:53,250 --> 00:40:59,230
dan kita juga mahu # termasuk lib.h standard untuk perpustakaan standard

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

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

515
00:41:08,660 --> 00:41:14,190
Mari kita cuba dan pastikan bahawa ini sebenarnya tidak menyusun.

516
00:41:14,190 --> 00:41:18,150
Kita lihat bahawa ia, maka kita berada di landasan yang betul.

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
Ia menyusun. Mari kita pergi ke bawah dan pastikan bahawa kita memasukkan beberapa panggilan kepada fungsi Mengandungi kami -

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

520
00:41:40,130 --> 00:41:43,170
Sebagai contoh, apabila kita melakukan lookup di pokok kami awal,

521
00:41:43,170 --> 00:41:48,500
kita cuba untuk melihat sehingga 6 nilai, 10, dan 1, dan kita tahu bahawa 6 berada di pokok itu,

522
00:41:48,500 --> 00:41:52,220
10 tidak di pokok itu, dan 1 bukan di pokok itu sama ada.

523
00:41:52,220 --> 00:41:57,230
Mari kita gunakan mereka panggilan sampel sebagai satu cara untuk mengetahui sama ada atau tidak

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

525
00:41:59,880 --> 00:42:05,210
Dalam usaha untuk berbuat demikian, saya akan menggunakan fungsi printf,

526
00:42:05,210 --> 00:42:10,280
dan kita pergi untuk mencetak hasil panggilan untuk mengandungi.

527
00:42:10,280 --> 00:42:13,280
Saya akan dimasukkan ke dalam rentetan "mengandungi (% d) = kerana

528
00:42:13,280 --> 00:42:20,470
 kita akan palam dalam nilai yang kita pergi untuk mencari,

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

530
00:42:27,130 --> 00:42:30,720
Kami hanya akan melihat - literal mencetak pada skrin -

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

532
00:42:32,060 --> 00:42:33,580
Ini sebenarnya bukanlah panggilan fungsi.

533
00:42:33,580 --> 00:42:36,760
 Ini adalah hanya rentetan yang direka untuk kelihatan seperti panggilan fungsi.

534
00:42:36,760 --> 00:42:41,140
>> Sekarang, kita pergi untuk palam dalam nilai.

535
00:42:41,140 --> 00:42:43,580
Kami akan cuba mengandungi pada 6,

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

537
00:42:48,340 --> 00:42:56,340
Mari kita lihat - mengandungi 6 - jadi, sekarang saya telah terkandung 6 dan jika mengandungi 6 adalah benar,

538
00:42:56,340 --> 00:43:01,850
rentetan bahawa kita akan menghantar kepada watak format% s

539
00:43:01,850 --> 00:43:04,850
akan menjadi rentetan "benar".

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

541
00:43:07,690 --> 00:43:16,210
Jika tidak, kita mahu menghantar rentetan "palsu" jika mengandungi 6 pulangan palsu.

542
00:43:16,210 --> 00:43:19,730
Ini adalah sedikit bodoh-cari, tetapi saya memikirkan saya juga mungkin menggambarkan

543
00:43:19,730 --> 00:43:23,780
apa pengendali pertigaan kelihatan seperti kerana kita tidak pernah melihat ia untuk seketika.

544
00:43:23,780 --> 00:43:27,670
Ini akan menjadi yang bagus, cara yang berguna untuk mengetahui jika fungsi Mengandungi kami bekerja.

545
00:43:27,670 --> 00:43:30,040
Saya akan skrol kembali ke kiri,

546
00:43:30,040 --> 00:43:39,900
dan saya akan salin dan tampal baris ini beberapa kali.

547
00:43:39,900 --> 00:43:44,910
Ia berubah beberapa nilai-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 ketika ini kita telah mendapat fungsi Mengandungi bagus.

550
00:44:02,480 --> 00:44:06,080
Kami telah mendapat beberapa ujian, dan kita akan melihat jika ini semua kerja.

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

552
00:44:08,120 --> 00:44:13,160
Masa untuk berhenti keluar dan memastikan bahawa segala-galanya masih menyusun.

553
00:44:13,160 --> 00:44:20,360
Berhenti keluar, dan sekarang mari kita cuba membuat pokok binari lagi.

554
00:44:20,360 --> 00:44:22,260
Nah, ia kelihatan seperti kita telah mendapat ralat,

555
00:44:22,260 --> 00:44:26,930
dan kita telah mendapat ini jelas mengisytiharkan fungsi perpustakaan printf.

556
00:44:26,930 --> 00:44:39,350
Nampaknya kita perlu pergi dalam dan # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Dan dengan itu, segala-galanya harus mengumpul. Kami semua yang baik.

558
00:44:45,350 --> 00:44:50,420
Sekarang mari kita cuba berlari pokok binari dan lihat apa yang berlaku.

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 lihat bahawa, seperti yang kita harapkan -

561
00:44:55,190 --> 00:44:56,910
kerana kita telah tidak dilaksanakan mengandungi lagi,

562
00:44:56,910 --> 00:44:59,800
atau sebaliknya, kami baru sahaja dimasukkan ke dalam penyata palsu -

563
00:44:59,800 --> 00:45:03,300
kita lihat bahawa ia hanya kembali palsu untuk mereka semua,

564
00:45:03,300 --> 00:45:06,180
supaya semua bekerja untuk sebahagian besar yang agak baik.

565
00:45:06,180 --> 00:45:11,860
>> Mari kita kembali dalam dan benar-benar melaksanakan mengandungi pada ketika ini.

566
00:45:11,860 --> 00:45:17,490
Saya akan tatal ke bawah, mengezum masuk, dan -

567
00:45:17,490 --> 00:45:22,330
ingat, algoritma yang kita digunakan adalah bahawa kita bermula pada nod akar

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

569
00:45:28,010 --> 00:45:32,380
dan berdasarkan perbandingan yang sama ada kita bergerak kepada anak kiri atau kanak-kanak yang betul.

570
00:45:32,380 --> 00:45:39,670
Ini akan kelihatan sangat serupa dengan kod carian binari bahawa kita menulis awal dalam jangka.

571
00:45:39,670 --> 00:45:47,810
Apabila kita bermula, kita tahu bahawa kita mahu berpegang kepada nod semasa

572
00:45:47,810 --> 00:45:54,050
bahawa kita melihat, dan nod semasa akan dimulakan ke nod akar.

573
00:45:54,050 --> 00:45:56,260
Dan sekarang, kita akan menyimpan melalui pokok itu,

574
00:45:56,260 --> 00:45:58,140
dan ingat bahawa keadaan kita berhenti -

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

576
00:46:01,870 --> 00:46:03,960
ialah apabila kita menghadapi nod nol,

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

578
00:46:05,480 --> 00:46:09,620
tetapi apabila kita sebenarnya berpindah ke nod dalam pokok

579
00:46:09,620 --> 00:46:12,640
dan mendapati bahawa kita berada di nod nol.

580
00:46:12,640 --> 00:46:20,720
Kami akan melelar sehingga kini tidak sama untuk menyeimbangkan.

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

582
00:46:22,920 --> 00:46:31,610
Kami akan menguji jika (kini -> nilai == nilai),

583
00:46:31,610 --> 00:46:35,160
maka kita tahu bahawa kita telah benar-benar menemui nod yang kita sedang mencari.

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

585
00:46:40,450 --> 00:46:49,830
Jika tidak, kita mahu melihat sama ada atau tidak nilai adalah kurang daripada nilai.

586
00:46:49,830 --> 00:46:53,850
Jika nilai nod semasa adalah kurang daripada nilai kita sedang mencari,

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

588
00:46:57,280 --> 00:47:10,600
Jadi, kini = kini -> right_child; dan selainnya, kita pergi untuk bergerak ke kiri.

589
00:47:10,600 --> 00:47:17,480
kini kini = -> left_child;. Agak mudah.

590
00:47:17,480 --> 00:47:22,830
>> Anda mungkin mengenali gelung yang kelihatan sangat serupa ini dari

591
00:47:22,830 --> 00:47:27,580
gelintaran perduaan awal dalam jangka, kecuali maka kita telah berurusan dengan rendah, pertengahan, dan tinggi.

592
00:47:27,580 --> 00:47:30,000
Di sini, kita hanya perlu melihat pada nilai semasa,

593
00:47:30,000 --> 00:47:31,930
jadi ia adalah baik dan mudah.

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

595
00:47:34,960 --> 00:47:42,780
Pertama, pastikan ia menyusun. Kelihatan seperti ia.

596
00:47:42,780 --> 00:47:47,920
Mari kita cuba berjalan ia.

597
00:47:47,920 --> 00:47:50,160
Dan demi sesungguhnya, ia mencetak keluar segala-galanya yang kita harapkan.

598
00:47:50,160 --> 00:47:54,320
Ia mendapati 6 di pokok itu, tidak mendapati 10 kerana 10 bukan di pokok itu,

599
00:47:54,320 --> 00:47:57,740
dan tidak mencari 1 sama ada kerana 1 juga tidak di pokok itu.

600
00:47:57,740 --> 00:48:01,420
Barangan sejuk.

601
00:48:01,420 --> 00:48:04,470
>> Baiklah. Mari kita kembali spesifikasi kami dan lihat apa yang seterusnya.

602
00:48:04,470 --> 00:48:07,990
Kini, ia mahu menambah beberapa lebih nod ke pokok kita.

603
00:48:07,990 --> 00:48:11,690
Ia mahu menambah 5, 2, dan 8, dan memastikan bahawa kita mengandungi kod

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

605
00:48:13,570 --> 00:48:14,900
Mari kita pergi berbuat demikian.

606
00:48:14,900 --> 00:48:19,430
Pada ketika ini, bukannya melakukan menjengkelkan bahawa salinan dan tampal sekali lagi,

607
00:48:19,430 --> 00:48:23,770
mari menulis fungsi sebenarnya mewujudkan nod.

608
00:48:23,770 --> 00:48:27,740
Jika kita tatal ke bawah sepanjang jalan utama, kita melihat bahawa kita telah melakukan ini

609
00:48:27,740 --> 00:48:31,210
kod yang sangat serupa berulang-ulang kali setiap kali kita mahu mencipta nod.

610
00:48:31,210 --> 00:48:39,540
>> Mari kita menulis fungsi yang sebenarnya akan membina nod untuk kita dan kembalikan.

611
00:48:39,540 --> 00:48:41,960
Saya akan memanggilnya build_node.

612
00:48:41,960 --> 00:48:45,130
Saya akan membina nod dengan nilai tertentu.

613
00:48:45,130 --> 00:48:51,040
Zum masuk sini.

614
00:48:51,040 --> 00:48:56,600
Perkara pertama yang saya akan lakukan sebenarnya mewujudkan ruang untuk nod pada timbunan.

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

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

617
00:49:14,960 --> 00:49:22,500
Dan pada akhir sangat, kami akan kembali nod kami.

618
00:49:22,500 --> 00:49:28,690
Baiklah. Satu perkara yang perlu diambil perhatian adalah bahawa fungsi ini di sini

619
00:49:28,690 --> 00:49:34,320
akan kembali penunjuk kepada memori yang telah timbunan-diperuntukkan.

620
00:49:34,320 --> 00:49:38,880
Apa yang baik tentang perkara ini ialah bahawa nod ini sekarang -

621
00:49:38,880 --> 00:49:42,420
kita perlu mengisytiharkan pada timbunan itu kerana jika kita mengisytiharkan ia pada timbunan

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

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

624
00:49:47,690 --> 00:49:51,590
dan akan menjadi tidak sah jika kita cuba untuk mengakses ia kemudian.

625
00:49:51,590 --> 00:49:53,500
Sejak kita mengisytiharkan timbunan-ingatan diperuntukkan,

626
00:49:53,500 --> 00:49:55,830
kita akan perlu menjaga membebaskan kemudian

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

628
00:49:58,530 --> 00:50:01,270
Kami telah punting bahawa untuk segala-galanya dalam kod

629
00:50:01,270 --> 00:50:02,880
hanya demi kesederhanaan pada masa itu,

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

631
00:50:05,610 --> 00:50:10,370
di mana anda telah mendapat - beberapa memanggilnya malloc atau realloc di dalam -

632
00:50:10,370 --> 00:50:14,330
anda ingin memastikan bahawa anda meletakkan beberapa jenis komen di sini yang mengatakan,

633
00:50:14,330 --> 00:50:29,970
hey, anda tahu, mengembalikan nod timbunan diperuntukkan yang dimulakan dengan nilai yang diluluskan dalam.

634
00:50:29,970 --> 00:50:33,600
Dan kemudian anda mahu pastikan yang anda dimasukkan ke dalam sejenis nota yang mengatakan

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

636
00:50:41,720 --> 00:50:45,450
Cara itu, jika seseorang yang pernah pergi dan menggunakan fungsi itu,

637
00:50:45,450 --> 00:50:48,150
mereka tahu bahawa apa sahaja yang mereka mendapat kembali daripada fungsi yang

638
00:50:48,150 --> 00:50:50,870
pada satu ketika akan perlu dibebaskan.

639
00:50:50,870 --> 00:50:53,940
>> Mengandaikan bahawa semua adalah baik dan baik di sini,

640
00:50:53,940 --> 00:51:02,300
kita boleh pergi ke dalam kod kami dan menggantikan semua ayat-ayat ini di sini

641
00:51:02,300 --> 00:51:05,410
dengan panggilan untuk membina fungsi nod kami.

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

643
00:51:08,170 --> 00:51:15,840
Bahagian satu bahawa kita tidak akan untuk menggantikan bahagian ini turun di sini

644
00:51:15,840 --> 00:51:18,520
di bawah mana kita sebenarnya wayar nod ke titik antara satu sama lain,

645
00:51:18,520 --> 00:51:21,030
kerana itu kita tidak boleh lakukan dalam fungsi kami.

646
00:51:21,030 --> 00:51:37,400
Tetapi, mari kita buat root = build_node (7); nod * tiga = build_node (3);

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

648
00:51:47,980 --> 00:51:52,590
Dan sekarang, kita juga mahu untuk menambah nod bagi -

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

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

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

652
00:52:20,280 --> 00:52:26,850
Baiklah. Pada ketika ini, kita tahu bahawa kita telah mendapat 7, 3, 9, dan 6

653
00:52:26,850 --> 00:52:30,320
semua berwayar sehingga sewajarnya, tetapi apa yang kira-kira 5, 8, dan 2?

654
00:52:30,320 --> 00:52:33,550
Untuk memastikan segala-galanya dalam perintah yang sesuai,

655
00:52:33,550 --> 00:52:39,230
kita tahu bahawa kanak-kanak yang betul 3 ialah 6.

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

657
00:52:40,890 --> 00:52:46,670
5 dengan juga tergolong dalam sebelah kanan pokok yang 3 adalah akar,

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

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

660
00:52:58,650 --> 00:53:10,790
dan kemudian 8 tergolong sebagai kanak-kanak kiri 9, jadi sembilan> left_child = 8;

661
00:53:10,790 --> 00:53:22,190
dan kemudian 2 adalah anak kiri 3, jadi kita boleh berbuat demikian di sini - wahai Muhammad -> left_child = dua;.

662
00:53:22,190 --> 00:53:27,730
Jika anda tidak cukup mengikuti bersama-sama dengan itu, saya cadangkan anda menarik ia keluar sendiri.

663
00:53:27,730 --> 00:53:35,660
>> Baiklah. Mari kita menyimpan ini. Mari kita pergi keluar dan pastikan ia menyusun,

664
00:53:35,660 --> 00:53:40,760
dan kemudian kita boleh menambah dalam panggilan Mengandungi kami.

665
00:53:40,760 --> 00:53:44,120
Kelihatan seperti segala-galanya masih menyusun.

666
00:53:44,120 --> 00:53:51,790
Mari kita pergi dan menambah dalam beberapa mengandungi panggilan.

667
00:53:51,790 --> 00:53:59,640
Sekali lagi, saya akan melakukan sedikit salin dan tampal.

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

669
00:54:15,860 --> 00:54:28,330
Mari kita pastikan bahawa ini semua kelihatan baik masih. Hebat! Simpan dan berhenti.

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

671
00:54:33,220 --> 00:54:37,540
Daripada keputusan, ia kelihatan seperti semua yang bekerja hanya bagus dan baik.

672
00:54:37,540 --> 00:54:41,780
Hebat! Jadi sekarang kita telah mendapat Mengandungi kami berfungsi ditulis.

673
00:54:41,780 --> 00:54:46,160
Mari kita bergerak ke atas dan mula bekerja pada bagaimana untuk memasukkan nod ke pokok

674
00:54:46,160 --> 00:54:50,000
kerana, seperti yang kita lakukan sekarang, perkara-perkara yang tidak sangat cantik.

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

676
00:54:52,280 --> 00:55:00,540
ia meminta kita untuk menulis fungsi yang dipanggil memasukkan - sekali lagi, kembali bool

677
00:55:00,540 --> 00:55:04,400
sama ada atau tidak kita sebenarnya boleh memasukkan nod ke pokok -

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

679
00:55:07,710 --> 00:55:11,060
hujah hanya kepada fungsi memasukkan kami.

680
00:55:11,060 --> 00:55:18,180
Kami akan kembali benar jika kita memang boleh memasukkan nilai nod mengandungi ke pokok itu,

681
00:55:18,180 --> 00:55:20,930
yang bermaksud bahawa kita, satu, mempunyai memori yang cukup,

682
00:55:20,930 --> 00:55:24,840
dan kemudian dua, nod yang tidak sudah wujud di pokok sejak

683
00:55:24,840 --> 00:55:32,170
ingat, kita tidak akan mempunyai nilai-nilai yang sama dalam pokok, hanya untuk membuat perkara yang mudah.

684
00:55:32,170 --> 00:55:35,590
Baiklah. Kembali kepada kod.

685
00:55:35,590 --> 00:55:44,240
Buka. Zum dalam sedikit, kemudian tatal ke bawah.

686
00:55:44,240 --> 00:55:47,220
Mari kita meletakkan fungsi memasukkan betul-betul di atas Mengandungi.

687
00:55:47,220 --> 00:55:56,360
Sekali lagi, ia akan dipanggil masukkan bool (int nilai).

688
00:55:56,360 --> 00:56:01,840
Memberikan ruang yang lebih sedikit, dan kemudian, sebagai lalai,

689
00:56:01,840 --> 00:56:08,870
mari kita dimasukkan ke dalam penyata palsu pada akhir sangat.

690
00:56:08,870 --> 00:56:22,620
Sekarang turun di bawah, mari kita pergi ke hadapan dan bukannya manual membina nod

691
00:56:22,620 --> 00:56:27,900
utama diri kita dan pendawaian mereka sehingga ke titik antara satu sama lain seperti yang kita sedang lakukan,

692
00:56:27,900 --> 00:56:30,600
kita akan bergantung pada fungsi memasukkan kami untuk berbuat demikian.

693
00:56:30,600 --> 00:56:35,510
Kami tidak akan bergantung pada fungsi memasukkan kami untuk membina pokok keseluruhan dari awal lagi,

694
00:56:35,510 --> 00:56:39,970
tetapi kita akan menghilangkan garisan ini - we'll mengulas keluar ayat-ayat ini -

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

696
00:56:43,430 --> 00:56:55,740
Dan sebaliknya, kita akan memasukkan panggilan kepada fungsi memasukkan kami

697
00:56:55,740 --> 00:57:01,280
memastikan bahawa sebenarnya berfungsi.

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

699
00:57:05,840 --> 00:57:09,300
>> Sekarang kita telah mengulas ayat-ayat ini.

700
00:57:09,300 --> 00:57:13,700
Kami hanya mempunyai 7, 3, 9, dan 6 di pokok kita pada ketika ini.

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

702
00:57:18,870 --> 00:57:25,050
kita boleh mengezum keluar, membuat pokok binari kami,

703
00:57:25,050 --> 00:57:30,750
menjalankannya, dan kita dapat melihat bahawa mengandungi kini memberitahu kita bahawa kita benar-benar betul -

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

705
00:57:33,110 --> 00:57:37,960
Kembali kepada kod,

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 apabila kita sebenarnya memasukkan 5, 8, dan 2 sebelumnya.

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

709
00:57:50,100 --> 00:57:52,780
pergi ke satu pokok dengan satu demi satu

710
00:57:52,780 --> 00:57:54,980
sehingga kita mendapati jurang yang sesuai,

711
00:57:54,980 --> 00:57:57,570
dan kemudian kita berwayar dalam nod di tempat yang sesuai.

712
00:57:57,570 --> 00:57:59,480
Kami akan melakukan perkara yang sama.

713
00:57:59,480 --> 00:58:04,070
Ini adalah pada dasarnya seperti menulis kod yang kita digunakan dalam mengandungi fungsi

714
00:58:04,070 --> 00:58:05,910
untuk mencari tempat di mana nod harus,

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

716
00:58:10,560 --> 00:58:17,000
Mari kita mulakan berbuat demikian.

717
00:58:17,000 --> 00:58:24,200
>> Jadi kita mempunyai nod * kini = akar; kami hanya akan mengikuti mengandungi kod

718
00:58:24,200 --> 00:58:26,850
sehingga kita mendapati bahawa ia tidak cukup bekerja untuk kita.

719
00:58:26,850 --> 00:58:32,390
Kami akan pergi melalui pokok manakala elemen semasa tidak adalah batal,

720
00:58:32,390 --> 00:58:45,280
dan jika kita dapati nilai yang kini adalah sama dengan nilai yang kita sedang cuba untuk memasukkan -

721
00:58:45,280 --> 00:58:49,600
baik, ini adalah salah satu kes di mana kita sebenarnya tidak boleh memasukkan nod

722
00:58:49,600 --> 00:58:52,730
ke pokok itu kerana ini bermakna kita mempunyai nilai pendua.

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

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

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

726
00:59:10,930 --> 00:59:17,190
 kerana nilai tergolong dalam separuh kanan pokok kini.

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
Itulah pada asasnya Mengandungi kami berfungsi di sana.

729
00:59:37,980 --> 00:59:41,820
>> Pada ketika ini, apabila kita telah selesai ini gelung sementara,

730
00:59:41,820 --> 00:59:47,350
penunjuk kini kita akan menunjuk untuk menyeimbangkan

731
00:59:47,350 --> 00:59:51,540
jika fungsi telah tidak sudah dikembalikan.

732
00:59:51,540 --> 00:59:58,710
Oleh itu, Kami mempunyai kini di tempat di mana kita mahu untuk memasukkan nod baru.

733
00:59:58,710 --> 01:00:05,210
Apa lagi yang perlu dilakukan adalah untuk benar-benar membina nod baru,

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

735
01:00:08,480 --> 01:00:14,930
Kita boleh menggunakan membina super berguna kami nod fungsi,

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

737
01:00:17,210 --> 01:00:21,400
kita hanya jenis mengambil untuk diberikan tetapi sekarang kita akan lakukan hanya untuk memastikan -

738
01:00:21,400 --> 01:00:27,130
kami akan menguji untuk memastikan bahawa nilai yang dikembalikan oleh nod baru sebenarnya

739
01:00:27,130 --> 01:00:33,410
tidak batal, kerana kita tidak mahu untuk memulakan mengakses memori yang jika ia adalah batal.

740
01:00:33,410 --> 01:00:39,910
Kita boleh menguji untuk memastikan bahawa nod baru tidak sama dengan null.

741
01:00:39,910 --> 01:00:42,910
Atau sebaliknya, kita hanya boleh melihat jika ia benar-benar adalah batal,

742
01:00:42,910 --> 01:00:52,120
dan jika ia adalah batal, maka kita hanya boleh kembali palsu awal.

743
01:00:52,120 --> 01:00:59,090
>> Pada ketika ini, kita perlu wayar nod baru ke tempat yang sesuai di pokok itu.

744
01:00:59,090 --> 01:01:03,510
Jika kita melihat kembali di utama dan di mana kita sebenarnya pendawaian di nilai sebelum ini,

745
01:01:03,510 --> 01:01:08,470
kita lihat bahawa cara kita melakukannya apabila kita mahu meletakkan 3 di pokok itu

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

747
01:01:11,750 --> 01:01:14,920
Apabila kita meletakkan 9 di pokok itu, kita terpaksa untuk mengakses kanak-kanak yang betul akar.

748
01:01:14,920 --> 01:01:21,030
Kami terpaksa mempunyai penunjuk kepada ibu bapa untuk meletakkan nilai baru ke dalam pokok itu.

749
01:01:21,030 --> 01:01:24,430
Menatal sandaran untuk memasukkan, itu tidak akan agak bekerja di sini

750
01:01:24,430 --> 01:01:27,550
kerana kita tidak mempunyai penunjuk ibu bapa.

751
01:01:27,550 --> 01:01:31,650
Apa yang kita mahu menjadi mampu lakukan adalah, pada ketika ini,

752
01:01:31,650 --> 01:01:37,080
memeriksa nilai ibu bapa dan lihat - baik, Astaga,

753
01:01:37,080 --> 01:01:41,990
jika nilai ibu bapa adalah kurang daripada nilai semasa,

754
01:01:41,990 --> 01:01:54,440
maka anak hak ibu bapa harus menjadi nod baru;

755
01:01:54,440 --> 01:02:07,280
sebaliknya, anak kiri ibu bapa harus menjadi nod baru.

756
01:02:07,280 --> 01:02:10,290
Tetapi, kita tidak mempunyai penunjuk induk agak lagi.

757
01:02:10,290 --> 01:02:15,010
>> Dalam usaha untuk mendapatkan ia, kita sebenarnya akan mempunyai untuk mengesan kerana kita pergi melalui pokok

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

759
01:02:18,440 --> 01:02:26,840
Kita boleh berbuat demikian dengan menatal kembali ke atas fungsi memasukkan kami

760
01:02:26,840 --> 01:02:32,350
dan pengesanan lain penuding dipanggil ibu bapa.

761
01:02:32,350 --> 01:02:39,340
Kami akan menetapkan ia sama untuk menyeimbangkan mulanya,

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

763
01:02:43,640 --> 01:02:51,540
kita akan menetapkan penunjuk ibu bapa untuk dipadankan penunjuk semasa.

764
01:02:51,540 --> 01:02:59,140
Tetapkan ibu bapa sama untuk kini.

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 bahawa sebagai penunjuk semasa mendapat incremented

767
01:03:05,550 --> 01:03:12,640
penunjuk induk berikut - hanya satu tahap lebih tinggi daripada penunjuk semasa dalam pokok itu.

768
01:03:12,640 --> 01:03:17,370
Itu semua kelihatan agak baik.

769
01:03:17,370 --> 01:03:22,380
>> Saya fikir satu perkara yang kita akan mahu untuk menyesuaikan diri ini membina kembali null nod.

770
01:03:22,380 --> 01:03:25,380
Dalam usaha untuk mendapatkan membina nod untuk benar-benar berjaya kembali batal,

771
01:03:25,380 --> 01:03:31,060
kita akan mempunyai untuk mengubah suai kod yang,

772
01:03:31,060 --> 01:03:37,270
kerana di sini, kita tidak pernah diuji untuk memastikan bahawa malloc kembali penunjuk yang sah.

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

774
01:03:53,390 --> 01:03:55,250
jika malloc kembali penunjuk yang sah, maka kita akan memulakan ia;

775
01:03:55,250 --> 01:04:02,540
sebaliknya, kita hanya akan kembali dan yang akan akhirnya kembali batal untuk kita.

776
01:04:02,540 --> 01:04:13,050
Sekarang semua kelihatan agak baik. Mari kita pastikan ini sebenarnya menyusun.

777
01:04:13,050 --> 01:04:22,240
Membuat pokok binari, dan oh, kami telah mendapat beberapa perkara yang berlaku di sini.

778
01:04:22,240 --> 01:04:29,230
>> Kami telah mendapat pengisytiharan tersirat fungsi membina nod.

779
01:04:29,230 --> 01:04:31,950
Sekali lagi, dengan penyusun, kami akan bermula di atas.

780
01:04:31,950 --> 01:04:36,380
Apa yang mesti bermakna adalah bahawa saya memanggil membina nod sebelum saya sebenarnya diisytiharkan.

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

782
01:04:37,730 --> 01:04:43,510
Tatal ke bawah, dan cukup yakin, fungsi memasukkan saya diisytiharkan

783
01:04:43,510 --> 01:04:47,400
atas fungsi nod membina,

784
01:04:47,400 --> 01:04:50,070
tetapi saya cuba untuk menggunakan membina nod di dalam sisipan.

785
01:04:50,070 --> 01:05:06,610
Saya akan pergi dalam salinan dan - dan kemudian paste cara fungsi nod membina sehingga di sini di atas.

786
01:05:06,610 --> 01:05:11,750
Cara itu, diharapkan yang akan bekerja. Mari kita memberi ini satu lagi pergi.

787
01:05:11,750 --> 01:05:18,920
Kini ia semua menyusun. Semua adalah baik.

788
01:05:18,920 --> 01:05:21,640
>> Tetapi pada masa ini, kita tidak sebenarnya dipanggil fungsi memasukkan kami.

789
01:05:21,640 --> 01:05:26,510
Kita hanya tahu bahawa ia menyusun, jadi mari kita pergi dalam dan meletakkan beberapa panggilan masuk

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

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

792
01:05:32,390 --> 01:05:36,680
dan kemudian kita tidak wayar 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 barangan yang kita digunakan

795
01:05:46,440 --> 01:05:52,810
apabila kita membuat panggilan printf untuk memastikan bahawa segala-galanya tidak dimasukkan dengan betul.

796
01:05:52,810 --> 01:06:00,550
Saya akan salin dan tampal,

797
01:06:00,550 --> 01:06:12,450
dan bukannya mengandungi kita pergi untuk melakukan memasukkan.

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 perlu memasukkan 5, 8, dan 2 ke pokok.

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

801
01:06:44,050 --> 01:06:47,330
>> Segalanya kembali palsu.

802
01:06:47,330 --> 01:06:53,830
Jadi, 5, 8, dan 2 tidak pergi, dan ia kelihatan seperti Mengandungi tidak mencari mereka sama ada.

803
01:06:53,830 --> 01:06:58,890
Apa yang berlaku? Mari kita mengezum keluar.

804
01:06:58,890 --> 01:07:02,160
Masalah pertama ialah memasukkan seolah-olah kembali palsu,

805
01:07:02,160 --> 01:07:08,750
dan ia kelihatan seperti itu kerana kita meninggalkan dalam panggilan penyata palsu 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 boleh menetapkan bahawa sehingga.

808
01:07:17,880 --> 01:07:25,290
Masalah kedua adalah, kini walaupun kita lakukan - menyelamatkan ini, cukai ini,

809
01:07:25,290 --> 01:07:34,530
menjalankan membuat lagi, ia telah menyusun, kemudian berjalan -

810
01:07:34,530 --> 01:07:37,670
kita melihat bahawa sesuatu yang lain berlaku di sini.

811
01:07:37,670 --> 01:07:42,980
5, 8, dan 2 masih tidak pernah ditemui di pokok itu.

812
01:07:42,980 --> 01:07:44,350
Jadi, apa yang berlaku?

813
01:07:44,350 --> 01:07:45,700
>> Mari kita lihat ini dalam kod.

814
01:07:45,700 --> 01:07:49,790
Mari kita lihat jika kita boleh memikirkan ini.

815
01:07:49,790 --> 01:07:57,940
Kita mulakan dengan ibu bapa tidak menjadi batal.

816
01:07:57,940 --> 01:07:59,510
Kami menetapkan penunjuk semasa sama dengan penunjuk akar,

817
01:07:59,510 --> 01:08:04,280
dan kita pergi untuk bekerja dengan cara kami ke bawah melalui pokok.

818
01:08:04,280 --> 01:08:08,650
Jika nod semasa tidak batal, maka kita tahu bahawa kita boleh bergerak ke bawah sedikit.

819
01:08:08,650 --> 01:08:12,330
Kami menetapkan penunjuk induk kami untuk menjadi sama dengan penunjuk semasa,

820
01:08:12,330 --> 01:08:15,420
diperiksa nilai - jika nilai adalah sama kita kembali palsu.

821
01:08:15,420 --> 01:08:17,540
Jika nilai adalah kurang kita berpindah ke kanan;

822
01:08:17,540 --> 01:08:20,399
sebaliknya, kita berpindah ke kiri.

823
01:08:20,399 --> 01:08:24,220
Kemudian kita membina nod. Saya akan mengezum masuk sedikit.

824
01:08:24,220 --> 01:08:31,410
Dan di sini, kita akan cuba wayar nilai untuk menjadi sama.

825
01:08:31,410 --> 01:08:37,250
Apa yang berlaku? Mari kita lihat jika mungkin Valgrind boleh memberi kita petunjuk.

826
01:08:37,250 --> 01:08:43,910
>> Saya suka menggunakan Valgrind hanya kerana Valgrind benar-benar cepat berjalan

827
01:08:43,910 --> 01:08:46,729
dan memberitahu anda jika terdapat sebarang kesilapan memori.

828
01:08:46,729 --> 01:08:48,300
Apabila kita menjalankan Valgrind pada kod,

829
01:08:48,300 --> 01:08:55,859
seperti yang anda boleh lihat hit here--Valgrind./binary_tree--and kanan masukkan.

830
01:08:55,859 --> 01:09:03,640
Anda melihat bahawa kami tidak mempunyai apa-apa kesilapan memori, jadi ia kelihatan seperti semua okay setakat ini.

831
01:09:03,640 --> 01:09:07,529
Kami mempunyai beberapa kebocoran memori, yang kita tahu, kerana kita tidak berada

832
01:09:07,529 --> 01:09:08,910
berlaku untuk membebaskan mana-mana nod kami.

833
01:09:08,910 --> 01:09:13,050
Mari kita cuba berjalan GDB untuk melihat apa yang sebenarnya berlaku.

834
01:09:13,050 --> 01:09:20,010
Kami akan melakukan Pra-Pemasangan / binary_tree. Ia boot sehingga hanya denda.

835
01:09:20,010 --> 01:09:23,670
Mari kita menetapkan titik rehat pada insert.

836
01:09:23,670 --> 01:09:28,600
Mari kita berjalan.

837
01:09:28,600 --> 01:09:31,200
Ia kelihatan seperti kita tidak pernah benar-benar dipanggil insert.

838
01:09:31,200 --> 01:09:39,410
Ia kelihatan seperti masalah itu hanya bahawa apabila saya berubah ke sini dalam utama -

839
01:09:39,410 --> 01:09:44,279
semua ini panggilan printf dari mengandungi -

840
01:09:44,279 --> 01:09:56,430
Saya tidak pernah benar-benar berubah ini untuk memanggil memasukkan.

841
01:09:56,430 --> 01:10:01,660
Sekarang mari kita mencubanya. Mari menyusun.

842
01:10:01,660 --> 01:10:09,130
Semua kelihatan baik di sana. Sekarang mari kita cuba berjalan ia, lihat apa yang berlaku.

843
01:10:09,130 --> 01:10:13,320
Baiklah! Semuanya kelihatan cukup baik di sana.

844
01:10:13,320 --> 01:10:18,130
>> Perkara yang terakhir untuk berfikir tentang adalah, adakah terdapat mana-mana kes kelebihan untuk memasukkan ini?

845
01:10:18,130 --> 01:10:23,170
Dan ternyata bahawa, baik, kes satu kelebihan yang sentiasa menarik untuk berfikir tentang

846
01:10:23,170 --> 01:10:26,250
, apa yang berlaku jika pokok anda adalah kosong dan anda memanggil fungsi ini memasukkan?

847
01:10:26,250 --> 01:10:30,330
Ia akan berfungsi? Nah, mari kita mencuba.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c -

849
01:10:32,110 --> 01:10:35,810
Cara kita pergi untuk menguji ini, kita akan pergi ke fungsi utama kami,

850
01:10:35,810 --> 01:10:41,690
dan bukannya pendawaian nod ini sehingga seperti ini,

851
01:10:41,690 --> 01:10:56,730
kita hanya akan mengulas perkara keseluruhan,

852
01:10:56,730 --> 01:11:02,620
dan bukannya pendawaian sehingga nodus diri,

853
01:11:02,620 --> 01:11:09,400
kita boleh sebenarnya hanya pergi ke hadapan dan memadam semua ini.

854
01:11:09,400 --> 01:11:17,560
Kami akan membuat segala-galanya panggilan untuk memasukkan.

855
01:11:17,560 --> 01:11:49,020
Jadi, mari kita lakukan - bukannya 5, 8, dan 2, kita akan untuk memasukkan 7, 3, dan 9.

856
01:11:49,020 --> 01:11:58,440
Dan kemudian kita juga akan mahu untuk memasukkan 6 serta.

857
01:11:58,440 --> 01:12:05,190
Simpan. Berhenti. Buat pokok binari.

858
01:12:05,190 --> 01:12:08,540
Ia semua menyusun.

859
01:12:08,540 --> 01:12:10,320
Kita hanya boleh jalankan ia sebagai dan lihat apa yang berlaku,

860
01:12:10,320 --> 01:12:12,770
tetapi ia juga akan menjadi benar-benar penting untuk memastikan bahawa

861
01:12:12,770 --> 01:12:14,740
kita tidak mempunyai apa-apa kesilapan memori,

862
01:12:14,740 --> 01:12:16,840
kerana ini adalah salah satu daripada kes kelebihan kita yang kita tahu tentang.

863
01:12:16,840 --> 01:12:20,150
>> Mari kita pastikan bahawa ia berfungsi dengan baik di bawah Valgrind,

864
01:12:20,150 --> 01:12:28,310
yang kita akan lakukan dengan hanya berjalan Valgrind / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Ia kelihatan seperti kita memang mempunyai satu kesilapan dari satu konteks -

866
01:12:31,110 --> 01:12:33,790
kita mempunyai kesalahan segmentasi.

867
01:12:33,790 --> 01:12:36,690
Apa yang berlaku?

868
01:12:36,690 --> 01:12:41,650
Valgrind sebenarnya memberitahu kita di mana ia.

869
01:12:41,650 --> 01:12:43,050
Zum keluar sedikit.

870
01:12:43,050 --> 01:12:46,040
Ia kelihatan seperti ia berlaku dalam fungsi memasukkan kami,

871
01:12:46,040 --> 01:12:53,420
di mana kita mempunyai membaca yang tidak sah daripada 4 saiz pada insert, line 60.

872
01:12:53,420 --> 01:13:03,590
Mari kita kembali dan lihat apa yang berlaku di sini.

873
01:13:03,590 --> 01:13:05,350
Zum keluar benar-benar cepat.

874
01:13:05,350 --> 01:13:14,230
Saya ingin memastikan bahawa ia tidak pergi ke pinggir skrin supaya kita boleh melihat segala-galanya.

875
01:13:14,230 --> 01:13:18,760
Tarik bahawa dalam sedikit. Baiklah.

876
01:13:18,760 --> 01:13:35,030
Tatal ke bawah, dan masalah yang tepat di sini.

877
01:13:35,030 --> 01:13:40,120
Apakah yang akan berlaku jika kita mendapatkan turun dan nod semasa kami sudah batal,

878
01:13:40,120 --> 01:13:44,010
nod induk kami adalah batal, jadi jika kita melihat di bahagian paling atas, di sini -

879
01:13:44,010 --> 01:13:47,340
jika ini gelung sementara tidak pernah benar-benar melaksanakan

880
01:13:47,340 --> 01:13:52,330
kerana nilai semasa kami adalah batal - akar kita adalah batal jadi kini adalah batal -

881
01:13:52,330 --> 01:13:57,810
maka ibu bapa kami tidak pernah mendapat bersedia untuk kini atau nilai yang sah,

882
01:13:57,810 --> 01:14:00,580
demikian, ibu bapa juga akan menjadi batal.

883
01:14:00,580 --> 01:14:03,700
Kita perlu ingat untuk memeriksa

884
01:14:03,700 --> 01:14:08,750
masa kita turun di sini, dan kami mula mengakses nilai ibu bapa.

885
01:14:08,750 --> 01:14:13,190
Jadi, apa yang berlaku? Nah, jika ibu bapa adalah batal -

886
01:14:13,190 --> 01:14:17,990
jika (ibu bapa == NULL) - maka kita tahu bahawa

887
01:14:17,990 --> 01:14:19,530
mestilah tidak ada apa-apa di pokok itu.

888
01:14:19,530 --> 01:14:22,030
Kita mesti cuba untuk memasukkan ia pada akar.

889
01:14:22,030 --> 01:14:32,570
Kita boleh berbuat demikian dengan hanya menetapkan akar yang sama dengan nod baru.

890
01:14:32,570 --> 01:14:40,010
Kemudian pada ketika ini, kita tidak benar-benar mahu pergi melalui perkara-perkara lain.

891
01:14:40,010 --> 01:14:44,780
Sebaliknya, di sini, kita boleh lakukan sama ada lain-jika-lain,

892
01:14:44,780 --> 01:14:47,610
atau kita boleh menggabungkan segala-galanya di sini dalam-galanya,

893
01:14:47,610 --> 01:14:56,300
tetapi 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 bahawa ibu bapa kita tidak batal

895
01:14:59,030 --> 01:15:02,160
sebelum itu sebenarnya cuba untuk mengakses bidang.

896
01:15:02,160 --> 01:15:05,330
Ini akan membantu kita mengelakkan kesalahan segmentasi.

897
01:15:05,330 --> 01:15:14,740
Jadi, kita berhenti, zum keluar, menyusun, jalankan.

898
01:15:14,740 --> 01:15:18,130
>> Tiada kesilapan, tetapi kita masih mempunyai sekumpulan kebocoran memori

899
01:15:18,130 --> 01:15:20,650
kerana kita tidak membebaskan sebarang nod kami.

900
01:15:20,650 --> 01:15:24,350
Tetapi, jika kita pergi di sini dan kita melihat cetakan kami,

901
01:15:24,350 --> 01:15:30,880
kita lihat bahawa, baik, kelihatan seperti memasukkan kami semua kembali benar, yang baik.

902
01:15:30,880 --> 01:15:33,050
Memasukkan semua adalah benar,

903
01:15:33,050 --> 01:15:36,670
dan kemudian Mengandungi sesuai panggilan adalah juga benar.

904
01:15:36,670 --> 01:15:41,510
>> Baik kerja! Ia kelihatan seperti kami telah berjaya ditulis memasukkan.

905
01:15:41,510 --> 01:15:47,430
Itu semua yang kita ada untuk Spesifikasi Set Masalah minggu ini.

906
01:15:47,430 --> 01:15:51,720
Salah satu cabaran yang menyeronokkan untuk berfikir tentang bagaimana anda sebenarnya akan pergi

907
01:15:51,720 --> 01:15:55,340
dan bebas semua nod dalam pokok ini.

908
01:15:55,340 --> 01:15:58,830
Kita boleh berbuat demikian beberapa cara yang berbeza,

909
01:15:58,830 --> 01:16:01,930
tetapi saya akan meninggalkan bahawa terpulang kepada anda untuk mencuba,

910
01:16:01,930 --> 01:16:06,080
dan sebagai cabaran yang menyeronokkan, cuba dan pastikan bahawa anda boleh memastikan

911
01:16:06,080 --> 01:16:09,490
bahawa laporan ini Valgrind mengembalikan tiada kesilapan dan tiada kebocoran.

912
01:16:09,490 --> 01:16:12,880
>> Nasib baik pada set masalah Huffman minggu ini pengekodan,

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]