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

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard University]

3
00:00:05,090 --> 00:00:07,930
[Ini adalah CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Baiklah. Jadi seperti saya katakan di email saya,

5
00:00:10,110 --> 00:00:14,060
ini akan menjadi bagian biner-pohon-intensif.

6
00:00:14,060 --> 00:00:16,820
Tapi ada tidak banyak pertanyaan.

7
00:00:16,820 --> 00:00:18,920
Jadi kita akan mencoba dan menarik keluar setiap pertanyaan

8
00:00:18,920 --> 00:00:25,430
dan pergi ke detail menyakitkan semua cara terbaik untuk melakukan sesuatu.

9
00:00:25,430 --> 00:00:31,200
Jadi tepat di awal, kita pergi melalui gambar sampel pohon biner dan barang-barang.

10
00:00:31,200 --> 00:00:35,970
Jadi di sini, "Ingatlah bahwa pohon biner memiliki node sama dengan linked list,

11
00:00:35,970 --> 00:00:38,150
kecuali bukan satu pointer ada dua: satu untuk 'anak' kiri

12
00:00:38,150 --> 00:00:41,950
dan satu untuk 'anak' yang tepat. "

13
00:00:41,950 --> 00:00:45,630
Jadi pohon biner adalah seperti sebuah linked list,

14
00:00:45,630 --> 00:00:47,910
kecuali struct akan memiliki dua pointer.

15
00:00:47,910 --> 00:00:51,390
Ada pohon trinary, yang akan memiliki tiga pointer,

16
00:00:51,390 --> 00:00:56,540
ada N-ary pohon, yang hanya memiliki pointer generik

17
00:00:56,540 --> 00:01:00,320
yang kemudian harus malloc cukup besar untuk memiliki

18
00:01:00,320 --> 00:01:04,840
cukup pointer untuk semua anak-anak yang mungkin.

19
00:01:04,840 --> 00:01:08,200
Jadi pohon biner kebetulan memiliki sejumlah konstan dua.

20
00:01:08,200 --> 00:01:11,260
Jika Anda ingin, Anda dapat memberikan daftar link sebagai pohon unary,

21
00:01:11,260 --> 00:01:15,360
tapi saya tidak berpikir siapa pun menyebutnya itu.

22
00:01:15,360 --> 00:01:18,060
"Gambarkan diagram kotak-dan-panah dari simpul pohon biner

23
00:01:18,060 --> 00:01:24,110
mengandung nomor favorit Nate, 7, di mana setiap anak adalah null pointer. "

24
00:01:24,110 --> 00:01:27,780
Jadi iPad modus.

25
00:01:27,780 --> 00:01:30,280
>> Ini akan menjadi cukup sederhana.

26
00:01:30,280 --> 00:01:36,150
Kami hanya akan memiliki sebuah node, saya akan menggambar sebagai persegi.

27
00:01:36,150 --> 00:01:38,730
Dan aku akan menarik nilai-nilai di sini.

28
00:01:38,730 --> 00:01:41,090
Jadi nilai akan masuk di sini,

29
00:01:41,090 --> 00:01:44,770
dan kemudian turun di sini kita akan memiliki pointer kiri di sebelah kiri dan pointer tepat di sebelah kanan.

30
00:01:44,770 --> 00:01:50,430
Dan itu sangat banyak sehingga konvensi untuk menyebutnya kiri dan kanan, nama pointer.

31
00:01:50,430 --> 00:01:52,460
Kedua hal ini akan menjadi nol.

32
00:01:52,460 --> 00:01:57,870
Itu hanya akan menjadi nol, dan itu hanya akan menjadi nol.

33
00:01:57,870 --> 00:02:03,630
Oke. Jadi kembali ke sini.

34
00:02:03,630 --> 00:02:05,700
"Dengan linked list, kita hanya harus menyimpan pointer

35
00:02:05,700 --> 00:02:09,639
ke node pertama dalam daftar untuk mengingat linked list keseluruhan, atau seluruh daftar.

36
00:02:09,639 --> 00:02:11,650
Demikian juga, dengan pohon-pohon, kita hanya perlu menyimpan pointer

37
00:02:11,650 --> 00:02:13,420
ke node tunggal untuk mengingat seluruh pohon.

38
00:02:13,420 --> 00:02:15,980
Simpul ini calle 'root' dari pohon.

39
00:02:15,980 --> 00:02:18,320
Membangun diagram Anda dari sebelumnya atau menggambar yang baru

40
00:02:18,320 --> 00:02:21,690
sedemikian rupa sehingga Anda memiliki gambaran kotak-dan-panah dari pohon biner

41
00:02:21,690 --> 00:02:25,730
dengan nilai 7, kemudian 3 di sebelah kiri,

42
00:02:25,730 --> 00:02:32,760
kemudian 9 di sebelah kanan, dan kemudian 6 di sebelah kanan dari 3. "

43
00:02:32,760 --> 00:02:34,810
Mari kita lihat apakah saya bisa mengingat semua itu dalam kepalaku.

44
00:02:34,810 --> 00:02:37,670
Jadi ini akan menjadi akar kami di sini.

45
00:02:37,670 --> 00:02:41,600
Kami akan memiliki beberapa pointer di suatu tempat, sesuatu yang kita akan menelepon akar,

46
00:02:41,600 --> 00:02:45,140
dan itu menunjuk ke orang ini.

47
00:02:45,140 --> 00:02:48,490
Sekarang untuk membuat node baru,

48
00:02:48,490 --> 00:02:52,870
apa yang kita miliki, 3 di sebelah kiri?

49
00:02:52,870 --> 00:02:57,140
Jadi node baru dengan 3, dan awalnya poin nol.

50
00:02:57,140 --> 00:02:59,190
Saya hanya akan menempatkan N.

51
00:02:59,190 --> 00:03:02,250
Sekarang kita ingin membuat yang pergi ke kiri 7.

52
00:03:02,250 --> 00:03:06,840
Jadi kita mengubah pointer ini untuk sekarang menunjukkan orang ini.

53
00:03:06,840 --> 00:03:12,420
Dan kami melakukan hal yang sama. Kami ingin 9 di sini

54
00:03:12,420 --> 00:03:14,620
yang awalnya hanya mengatakan nol.

55
00:03:14,620 --> 00:03:19,600
Kita akan mengubah pointer, arahkan ke 9,

56
00:03:19,600 --> 00:03:23,310
dan sekarang kami ingin menempatkan 6 di sebelah kanan 3.

57
00:03:23,310 --> 00:03:32,170
Jadi itu akan - membuat 6.

58
00:03:32,170 --> 00:03:34,310
Dan pria yang akan mengarahkan sana.

59
00:03:34,310 --> 00:03:38,320
Oke. Jadi itu semua itu meminta kita untuk melakukan.

60
00:03:38,320 --> 00:03:42,770
>> Sekarang mari kita membahas beberapa terminologi.

61
00:03:42,770 --> 00:03:46,690
Kami sudah berbicara tentang bagaimana akar pohon adalah simpul paling atas di pohon.

62
00:03:46,690 --> 00:03:54,720
Yang satu berisi 7. Simpul di bagian bawah pohon yang disebut daun.

63
00:03:54,720 --> 00:04:01,240
Setiap simpul yang hanya memiliki null sebagai anak adalah daun.

64
00:04:01,240 --> 00:04:03,680
Jadi, mungkin, jika pohon biner kita hanya node tunggal,

65
00:04:03,680 --> 00:04:10,130
bahwa pohon adalah daun, dan hanya itu.

66
00:04:10,130 --> 00:04:12,060
"The 'tinggi' dari pohon adalah jumlah hop Anda harus membuat

67
00:04:12,060 --> 00:04:16,620
untuk mendapatkan dari atas ke daun. "

68
00:04:16,620 --> 00:04:18,640
Kami akan masuk ke dalam, dalam satu detik, perbedaan

69
00:04:18,640 --> 00:04:21,940
antara pohon-pohon biner seimbang dan tak seimbang,

70
00:04:21,940 --> 00:04:29,470
tapi untuk saat ini, ketinggian keseluruhan pohon ini

71
00:04:29,470 --> 00:04:34,520
Saya akan katakan adalah 3, meskipun jika Anda menghitung jumlah hop

72
00:04:34,520 --> 00:04:39,710
Anda harus membuat untuk mendapatkan sampai 9, maka itu benar-benar hanya ketinggian 2.

73
00:04:39,710 --> 00:04:43,340
Sekarang ini adalah sebuah pohon biner seimbang,

74
00:04:43,340 --> 00:04:49,840
tapi kami akan berbicara tentang seimbang ketika sampai relevan.

75
00:04:49,840 --> 00:04:52,040
Jadi sekarang kita bisa bicara tentang node di pohon dalam hal

76
00:04:52,040 --> 00:04:54,700
relatif terhadap node lain dalam pohon.

77
00:04:54,700 --> 00:04:59,730
Jadi sekarang kita memiliki orang tua, anak, saudara, nenek moyang, dan keturunan.

78
00:04:59,730 --> 00:05:05,650
Mereka adalah akal yang cukup umum, apa yang mereka maksudkan.

79
00:05:05,650 --> 00:05:09,610
Jika kita bertanya - orang tua itu.

80
00:05:09,610 --> 00:05:12,830
Jadi apa adalah orang tua dari 3?

81
00:05:12,830 --> 00:05:16,090
[Siswa] 7. >> Ya. Orangtua hanya akan menjadi apa yang menunjuk ke Anda.

82
00:05:16,090 --> 00:05:20,510
Lalu apa yang anak-anak dari 7?

83
00:05:20,510 --> 00:05:23,860
[Siswa] 3 dan 9. >> Ya.

84
00:05:23,860 --> 00:05:26,460
Perhatikan bahwa "anak-anak" secara harfiah berarti anak-anak,

85
00:05:26,460 --> 00:05:31,010
jadi 6 tidak akan berlaku, karena itu seperti seorang cucu.

86
00:05:31,010 --> 00:05:35,540
Tapi kemudian jika kita pergi keturunan, jadi apa adalah keturunan dari 7?

87
00:05:35,540 --> 00:05:37,500
[Siswa] 3, 6 dan 9. >> Ya.

88
00:05:37,500 --> 00:05:42,330
Keturunan dari simpul akar akan menjadi segala sesuatu di pohon,

89
00:05:42,330 --> 00:05:47,950
kecuali mungkin simpul akar itu sendiri, jika Anda tidak ingin mempertimbangkan bahwa keturunan.

90
00:05:47,950 --> 00:05:50,750
Dan akhirnya, nenek moyang, jadi arah yang berlawanan.

91
00:05:50,750 --> 00:05:55,740
Jadi apa nenek moyang dari 6?

92
00:05:55,740 --> 00:05:58,920
[Siswa] 3 dan 7. >> Ya. 9 tidak termasuk.

93
00:05:58,920 --> 00:06:02,520
Hanya saja kembali keturunan langsung ke akar

94
00:06:02,520 --> 00:06:13,230
akan menjadi nenek moyang Anda.

95
00:06:13,230 --> 00:06:16,300
>> "Kami mengatakan bahwa pohon biner 'memerintahkan' jika untuk setiap node di pohon,

96
00:06:16,300 --> 00:06:19,530
semua keturunannya di sebelah kiri memiliki nilai lebih rendah

97
00:06:19,530 --> 00:06:22,890
dan semua orang-orang di sebelah kanan memiliki nilai yang lebih besar.

98
00:06:22,890 --> 00:06:27,060
Misalnya, pohon di atas memerintahkan tapi itu bukan pengaturan memerintahkan hanya mungkin. "

99
00:06:27,060 --> 00:06:30,180
Sebelum kita menuju ke sana,

100
00:06:30,180 --> 00:06:36,420
sebuah pohon biner memerintahkan juga dikenal sebagai pohon pencarian biner.

101
00:06:36,420 --> 00:06:38,660
Di sini kita kebetulan menyebutnya sebuah pohon biner memerintahkan,

102
00:06:38,660 --> 00:06:41,850
tapi saya belum pernah mendengarnya disebut pohon biner memesan sebelum,

103
00:06:41,850 --> 00:06:46,650
dan pada kuis kita jauh lebih mungkin untuk menempatkan pohon pencarian biner.

104
00:06:46,650 --> 00:06:49,250
Mereka satu dan sama,

105
00:06:49,250 --> 00:06:54,580
dan itu penting Anda mengenali perbedaan antara pohon biner dan pohon pencarian biner.

106
00:06:54,580 --> 00:06:58,830
Sebuah pohon biner hanya pohon yang menunjuk ke dua hal.

107
00:06:58,830 --> 00:07:02,120
Setiap node menunjuk ke dua hal.

108
00:07:02,120 --> 00:07:06,310
Tidak ada alasan tentang nilai-nilai yang menunjuk ke.

109
00:07:06,310 --> 00:07:11,370
Jadi seperti di sini, karena itu adalah pohon pencarian biner,

110
00:07:11,370 --> 00:07:14,030
kita tahu bahwa jika kita pergi meninggalkan dari 7,

111
00:07:14,030 --> 00:07:16,670
maka semua nilai-nilai yang kita mungkin dapat mencapai

112
00:07:16,670 --> 00:07:19,310
dengan pergi kiri 7 harus kurang dari 7.

113
00:07:19,310 --> 00:07:24,070
Perhatikan bahwa semua nilai kurang dari 7 adalah 3 dan 6.

114
00:07:24,070 --> 00:07:26,040
Mereka semua di sebelah kiri 7.

115
00:07:26,040 --> 00:07:29,020
Jika kita pergi ke kanan 7, semuanya harus lebih besar dari 7,

116
00:07:29,020 --> 00:07:33,220
jadi 9 adalah di sebelah kanan 7, jadi kita baik.

117
00:07:33,220 --> 00:07:36,150
Ini tidak terjadi untuk sebuah pohon biner,

118
00:07:36,150 --> 00:07:40,020
untuk pohon biner biasa kita hanya bisa memiliki 3 di bagian atas, 7 ke kiri,

119
00:07:40,020 --> 00:07:47,630
9 di sebelah kiri 7, tidak ada pemesanan nilai apapun.

120
00:07:47,630 --> 00:07:56,140
Sekarang, kita tidak akan benar-benar melakukan ini karena itu membosankan dan tidak perlu,

121
00:07:56,140 --> 00:07:59,400
tapi "mencoba untuk menarik pohon memerintahkan sebanyak yang Anda bisa memikirkan

122
00:07:59,400 --> 00:08:01,900
menggunakan angka 7, 3, 9, dan 6.

123
00:08:01,900 --> 00:08:06,800
Berapa banyak pengaturan yang berbeda yang ada? Apa ketinggian masing-masing? "

124
00:08:06,800 --> 00:08:10,480
>> Kami akan melakukan beberapa, tapi gagasan utama adalah,

125
00:08:10,480 --> 00:08:16,530
ini sama sekali tidak representasi yang unik dari pohon biner yang mengandung nilai-nilai ini.

126
00:08:16,530 --> 00:08:22,760
Yang kita butuhkan adalah beberapa pohon biner yang berisi 7, 3, 6, dan 9.

127
00:08:22,760 --> 00:08:25,960
Satu lagi berlaku mungkin akan akar adalah 3,

128
00:08:25,960 --> 00:08:30,260
pergi ke kiri dan itu 6, pergi ke kiri dan itu 7,

129
00:08:30,260 --> 00:08:32,730
pergi ke kiri dan itu 9.

130
00:08:32,730 --> 00:08:36,169
Itu adalah pohon pencarian biner yang valid sempurna.

131
00:08:36,169 --> 00:08:39,570
Hal ini tidak sangat membantu, karena itu hanya seperti sebuah linked list

132
00:08:39,570 --> 00:08:43,750
dan semua pointer hanya nol.

133
00:08:43,750 --> 00:08:48,900
Tapi itu adalah pohon valid. Ya?

134
00:08:48,900 --> 00:08:51,310
[Mahasiswa] Jangan nilai-nilai harus lebih besar di sebelah kanan?

135
00:08:51,310 --> 00:08:56,700
Atau ini -? >> Ini saya dimaksudkan untuk pergi ke arah lain.

136
00:08:56,700 --> 00:09:00,960
Ada juga - yeah, mari kita beralih itu.

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

138
00:09:07,770 --> 00:09:11,730
Ini masih harus menuruti apa pencarian pohon biner yang seharusnya dilakukan.

139
00:09:11,730 --> 00:09:15,650
Jadi semuanya ke kiri harus kurang dari setiap node yang diberikan.

140
00:09:15,650 --> 00:09:23,180
Kami hanya bisa bergerak, mengatakan, ini 6 dan taruh di sini.

141
00:09:23,180 --> 00:09:26,880
Tidak, kita tidak bisa. Mengapa saya terus melakukan itu?

142
00:09:26,880 --> 00:09:35,350
Mari kita lakukan - di sini adalah 6, di sini adalah 7, 6 poin ke 3.

143
00:09:35,350 --> 00:09:39,290
Ini masih sebuah pohon biner yang valid pencarian.

144
00:09:39,290 --> 00:09:49,260
Apa yang salah jika saya - mari kita lihat apakah saya bisa datang dengan pengaturan.

145
00:09:49,260 --> 00:09:52,280
Ya, oke. Jadi apa yang salah dengan pohon ini?

146
00:09:52,280 --> 00:10:08,920
Saya kira saya sudah memberi Anda petunjuk bahwa ada sesuatu yang salah dengan itu.

147
00:10:08,920 --> 00:10:14,430
Mengapa saya terus melakukan itu?

148
00:10:14,430 --> 00:10:18,510
Oke. Hal ini terlihat wajar.

149
00:10:18,510 --> 00:10:22,590
Jika kita melihat pada setiap node, seperti 7, kemudian ke kiri 7 adalah 3.

150
00:10:22,590 --> 00:10:24,960
Jadi kita memiliki 3, hal di sebelah kanan adalah 3 6 a.

151
00:10:24,960 --> 00:10:27,750
Dan jika Anda melihat 6, hal di sebelah kanan 6 adalah 9.

152
00:10:27,750 --> 00:10:30,910
Lalu mengapa ini bukan sebuah pohon biner yang valid pencarian?

153
00:10:30,910 --> 00:10:36,330
[Siswa] 9 masih di sebelah kiri 7. >> Ya.

154
00:10:36,330 --> 00:10:43,710
Ini harus benar bahwa semua nilai yang Anda mungkin dapat mencapai dengan pergi ke sebelah kiri 7 kurang dari 7.

155
00:10:43,710 --> 00:10:49,120
Jika kita pergi kiri 7, kita sampai 3 dan kita masih bisa sampai ke 6,

156
00:10:49,120 --> 00:10:52,520
kita masih bisa mendapatkan sampai 9, tetapi dengan telah pergi kurang dari 7,

157
00:10:52,520 --> 00:10:55,070
kita tidak harus bisa mendapatkan nomor yang lebih besar dari 7.

158
00:10:55,070 --> 00:10:59,830
Jadi ini bukan sebuah pohon biner yang valid pencarian.

159
00:10:59,830 --> 00:11:02,330
>> Adikku benar-benar memiliki pertanyaan wawancara

160
00:11:02,330 --> 00:11:07,760
yang pada dasarnya hal ini, hanya kode sesuatu untuk memvalidasi

161
00:11:07,760 --> 00:11:10,500
apakah pohon adalah pohon pencarian biner,

162
00:11:10,500 --> 00:11:13,580
sehingga hal pertama yang ia lakukan adalah hanya memeriksa untuk melihat

163
00:11:13,580 --> 00:11:17,020
jika kiri dan kanan sudah benar, dan kemudian iterate di sana.

164
00:11:17,020 --> 00:11:19,700
Tapi Anda tidak bisa melakukan itu, Anda harus melacak

165
00:11:19,700 --> 00:11:22,550
dari fakta bahwa sekarang aku sudah kiri 7,

166
00:11:22,550 --> 00:11:26,340
segala sesuatu di subtree harus kurang dari 7.

167
00:11:26,340 --> 00:11:28,430
Algoritma yang benar perlu untuk melacak

168
00:11:28,430 --> 00:11:35,970
dari batasan bahwa nilai mungkin bisa jatuh masuk

169
00:11:35,970 --> 00:11:38,360
Kami tidak akan pergi melalui semua dari mereka.

170
00:11:38,360 --> 00:11:41,630
Ada hubungan kekambuhan yang bagus,

171
00:11:41,630 --> 00:11:44,810
meskipun kami belum mendapatkan mereka, atau kita tidak akan sampai ke mereka,

172
00:11:44,810 --> 00:11:47,030
mendefinisikan berapa banyak sebenarnya ada.

173
00:11:47,030 --> 00:11:53,180
Jadi ada 14 dari mereka.

174
00:11:53,180 --> 00:11:56,020
Ide tentang bagaimana Anda akan melakukannya matematis seperti,

175
00:11:56,020 --> 00:11:59,770
Anda dapat memilih salah satu tunggal untuk menjadi node root,

176
00:11:59,770 --> 00:12:03,160
dan kemudian jika saya memilih 7 menjadi simpul akar,

177
00:12:03,160 --> 00:12:08,150
maka ada, katakanlah, beberapa nomor yang bisa menjadi simpul kiri saya,

178
00:12:08,150 --> 00:12:10,440
dan ada beberapa nomor yang bisa menjadi simpul kanan saya,

179
00:12:10,440 --> 00:12:15,090
tetapi jika saya memiliki n jumlah total, maka jumlah yang bisa pergi ke kiri

180
00:12:15,090 --> 00:12:18,820
ditambah jumlah yang dapat pergi ke kanan adalah n - 1.

181
00:12:18,820 --> 00:12:26,130
Jadi dari nomor yang tersisa, mereka harus mampu untuk pergi baik ke kiri atau ke kanan.

182
00:12:26,130 --> 00:12:31,580
Tampaknya sulit yang, jika saya menempatkan 3 pertama maka semuanya harus pergi ke kiri,

183
00:12:31,580 --> 00:12:35,080
tetapi jika aku menaruh 7, maka beberapa hal dapat pergi kiri dan beberapa hal dapat pergi ke kanan.

184
00:12:35,080 --> 00:12:39,570
Dan dengan '3 'pertama saya berarti segalanya bisa pergi ke kanan.

185
00:12:39,570 --> 00:12:42,350
Ini benar-benar, Anda hanya perlu berpikir tentang hal ini sebagai,

186
00:12:42,350 --> 00:12:47,980
berapa banyak hal yang bisa pergi pada tingkat berikutnya dari pohon.

187
00:12:47,980 --> 00:12:50,420
Dan itu keluar menjadi 14, atau Anda dapat menarik mereka semua,

188
00:12:50,420 --> 00:12:54,650
dan kemudian Anda akan mendapatkan 14.

189
00:12:54,650 --> 00:13:01,120
>> Akan kembali ke sini,

190
00:13:01,120 --> 00:13:03,510
"Pohon biner Memerintahkan keren karena kita bisa mencari melalui mereka

191
00:13:03,510 --> 00:13:06,910
dalam cara yang sangat mirip dengan mencari lebih dari array diurutkan.

192
00:13:06,910 --> 00:13:10,120
Untuk melakukannya, kita mulai dari akar dan bekerja dengan cara kami menuruni pohon

193
00:13:10,120 --> 00:13:13,440
terhadap daun, memeriksa nilai-nilai setiap node terhadap nilai-nilai yang kita cari.

194
00:13:13,440 --> 00:13:15,810
Jika nilai node saat ini kurang dari nilai yang kita cari,

195
00:13:15,810 --> 00:13:18,050
Anda pergi di samping anak kanan node.

196
00:13:18,050 --> 00:13:20,030
Jika tidak, Anda pergi ke anak kiri node.

197
00:13:20,030 --> 00:13:22,800
Pada titik tertentu, Anda akan menemukan nilai yang Anda cari, atau Anda akan lari ke null,

198
00:13:22,800 --> 00:13:28,520
menunjukkan nilai tidak di pohon. "

199
00:13:28,520 --> 00:13:32,450
Saya harus redraw pohon kita sebelumnya, yang akan mengambil kedua.

200
00:13:32,450 --> 00:13:38,280
Tapi kami ingin mencari apakah 6, 10, dan 1 berada di pohon.

201
00:13:38,280 --> 00:13:49,180
Jadi apa itu, 7, 9, 3, 6. Oke.

202
00:13:49,180 --> 00:13:52,730
Angka yang Anda ingin mencari, kami ingin mencari 6.

203
00:13:52,730 --> 00:13:55,440
Bagaimana ini bekerja algoritma?

204
00:13:55,440 --> 00:14:03,040
Nah, kami juga memiliki beberapa pointer akar ke pohon kami.

205
00:14:03,040 --> 00:14:12,460
Dan kami akan pergi ke akar dan mengatakan, ini nilai yang sama dengan nilai yang kita cari?

206
00:14:12,460 --> 00:14:15,000
Jadi kita mencari 6, jadi tidak sama.

207
00:14:15,000 --> 00:14:20,140
Jadi kita terus, dan sekarang kita katakan, oke, jadi 6 kurang dari 7.

208
00:14:20,140 --> 00:14:23,940
Apakah itu berarti kita ingin pergi ke kiri, atau kita ingin pergi ke kanan?

209
00:14:23,940 --> 00:14:27,340
[Mahasiswa] Kiri. >> Ya.

210
00:14:27,340 --> 00:14:33,340
Ini secara signifikan lebih mudah, yang harus Anda lakukan adalah menggambar satu node mungkin pohon

211
00:14:33,340 --> 00:14:37,760
dan kemudian Anda jangan - alih-alih mencoba untuk berpikir di kepala Anda,

212
00:14:37,760 --> 00:14:40,020
oke, jika kurang, aku pergi ke kiri atau ke kanan tersebut,

213
00:14:40,020 --> 00:14:43,030
hanya melihat gambar ini, sangat jelas bahwa saya harus pergi ke kiri

214
00:14:43,030 --> 00:14:47,700
jika node ini lebih besar dari nilai yang saya cari.

215
00:14:47,700 --> 00:14:52,600
Jadi Anda pergi ke kiri, sekarang aku di 3.

216
00:14:52,600 --> 00:14:57,770
Saya ingin - 3 adalah kurang dari nilai yang saya cari, yaitu 6.

217
00:14:57,770 --> 00:15:03,420
Jadi kita pergi ke kanan, dan sekarang saya berakhir di 6,

218
00:15:03,420 --> 00:15:07,380
yang merupakan nilai yang saya cari, jadi saya kembali benar.

219
00:15:07,380 --> 00:15:15,760
Nilai berikutnya aku akan dicari adalah 10.

220
00:15:15,760 --> 00:15:23,230
Oke. Jadi 10, sekarang, akan - dipotong bahwa - akan mengikuti akar.

221
00:15:23,230 --> 00:15:27,670
Sekarang, 10 akan menjadi lebih besar dari 7, jadi saya ingin melihat ke kanan.

222
00:15:27,670 --> 00:15:31,660
Aku akan datang ke sini, 10 akan menjadi lebih besar dari 9,

223
00:15:31,660 --> 00:15:34,520
jadi aku akan ingin melihat ke kanan.

224
00:15:34,520 --> 00:15:42,100
Aku datang ke sini, tapi di sini sekarang aku di nol.

225
00:15:42,100 --> 00:15:44,170
Apa yang harus saya lakukan jika aku memukul nol?

226
00:15:44,170 --> 00:15:47,440
[Mahasiswa] Kembali palsu? >> Ya. Saya tidak menemukan 10.

227
00:15:47,440 --> 00:15:49,800
1 akan menjadi kasus hampir sama,

228
00:15:49,800 --> 00:15:51,950
kecuali itu hanya akan membalik, bukannya mencari

229
00:15:51,950 --> 00:15:56,540
di sisi kanan, aku akan melihat ke bawah sisi kiri.

230
00:15:56,540 --> 00:16:00,430
>> Sekarang saya pikir kita benar-benar bisa kode.

231
00:16:00,430 --> 00:16:04,070
Di sinilah - membuka alat CS50 dan menavigasi jalan Anda di sana,

232
00:16:04,070 --> 00:16:07,010
tetapi Anda juga dapat hanya melakukannya di ruang.

233
00:16:07,010 --> 00:16:09,170
Itu mungkin ideal untuk melakukannya dalam ruang,

234
00:16:09,170 --> 00:16:13,760
karena kita dapat bekerja dalam ruang.

235
00:16:13,760 --> 00:16:19,170
"Pertama kita akan membutuhkan definisi tipe baru untuk simpul pohon biner yang mengandung nilai-nilai int.

236
00:16:19,170 --> 00:16:21,400
Menggunakan boilerplate typedef bawah,

237
00:16:21,400 --> 00:16:24,510
membuat definisi tipe baru untuk node dalam pohon biner.

238
00:16:24,510 --> 00:16:27,930
Jika Anda terjebak. . . "Bla, bla, bla. Oke.

239
00:16:27,930 --> 00:16:30,380
Jadi mari kita boilerplate di sini,

240
00:16:30,380 --> 00:16:41,630
struct typedef node, dan node. Ya, oke.

241
00:16:41,630 --> 00:16:44,270
Jadi apa bidang kita akan inginkan dalam simpul kita?

242
00:16:44,270 --> 00:16:46,520
[Mahasiswa] Int dan kemudian dua pointer?

243
00:16:46,520 --> 00:16:49,700
>> Int nilai, dua pointer? Bagaimana cara menulis pointer?

244
00:16:49,700 --> 00:16:58,440
[Mahasiswa] Struct. >> Saya harus tampilannya masuk Yeah, jadi struct simpul * kiri,

245
00:16:58,440 --> 00:17:01,320
dan struct simpul * tepat.

246
00:17:01,320 --> 00:17:03,460
Dan ingat diskusi dari waktu lalu,

247
00:17:03,460 --> 00:17:15,290
bahwa ini tidak masuk akal, ini tidak masuk akal,

248
00:17:15,290 --> 00:17:18,270
ini tidak masuk akal.

249
00:17:18,270 --> 00:17:25,000
Anda perlu segala sesuatu dalam rangka untuk menentukan ini struct rekursif.

250
00:17:25,000 --> 00:17:27,970
Oke, jadi itulah yang kami pohon akan terlihat seperti.

251
00:17:27,970 --> 00:17:37,670
Jika kita melakukan sebuah pohon trinary, maka simpul mungkin terlihat seperti b1, b2, struct simpul * b3,

252
00:17:37,670 --> 00:17:43,470
di mana b adalah cabang - sebenarnya, saya lebih mendengar itu meninggalkan, tengah, kanan, tapi apa pun.

253
00:17:43,470 --> 00:17:55,610
Kami hanya peduli biner, sehingga kanan, kiri.

254
00:17:55,610 --> 00:17:59,110
"Sekarang mendeklarasikan variabel simpul * global untuk akar pohon."

255
00:17:59,110 --> 00:18:01,510
Jadi kita tidak akan melakukan itu.

256
00:18:01,510 --> 00:18:08,950
Dalam rangka untuk membuat hal-hal yang sedikit lebih sulit dan lebih umum,

257
00:18:08,950 --> 00:18:11,570
kita tidak akan memiliki variabel simpul global.

258
00:18:11,570 --> 00:18:16,710
Sebaliknya, di utama kami akan menyatakan semua hal simpul kami,

259
00:18:16,710 --> 00:18:20,500
dan itu berarti bahwa di bawah ini, ketika kita mulai berjalan

260
00:18:20,500 --> 00:18:23,130
kami dikandungnya fungsi dan fungsi insert kami,

261
00:18:23,130 --> 00:18:27,410
bukannya dikandungnya kami hanya menggunakan fungsi ini variabel simpul global,

262
00:18:27,410 --> 00:18:34,280
kita akan memilikinya mengambil sebagai argumen pohon yang kita inginkan untuk memproses.

263
00:18:34,280 --> 00:18:36,650
Memiliki variabel global seharusnya membuat segalanya lebih mudah.

264
00:18:36,650 --> 00:18:42,310
Kita akan membuat hal-hal sulit.

265
00:18:42,310 --> 00:18:51,210
Sekarang mengambil satu menit atau lebih untuk hanya melakukan hal semacam ini,

266
00:18:51,210 --> 00:18:57,690
di mana dalam utama Anda ingin membuat pohon ini, dan itu semua yang ingin Anda lakukan.

267
00:18:57,690 --> 00:19:04,530
Coba dan membangun pohon ini dalam fungsi utama Anda.

268
00:19:42,760 --> 00:19:47,610
>> Oke. Jadi Anda tidak bahkan harus telah dibangun pohon seluruh jalan belum.

269
00:19:47,610 --> 00:19:49,840
Tapi ada yang punya sesuatu yang saya bisa menarik

270
00:19:49,840 --> 00:20:03,130
untuk menunjukkan bagaimana seseorang bisa mulai membangun semacam pohon?

271
00:20:03,130 --> 00:20:08,080
[Mahasiswa] membenturkan Seseorang, mencoba untuk keluar.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Siapapun nyaman dengan konstruksi pohon mereka?

273
00:20:13,100 --> 00:20:15,520
[Mahasiswa] Tentu. Ini tidak dilakukan. >> Tidak apa-apa. Kami hanya bisa menyelesaikan -

274
00:20:15,520 --> 00:20:26,860
oh, bisa Anda menyimpannya? Hore.

275
00:20:26,860 --> 00:20:32,020
Jadi di sini kita memiliki - oh, aku sedikit terpotong.

276
00:20:32,020 --> 00:20:34,770
Apakah saya diperbesar?

277
00:20:34,770 --> 00:20:37,730
Zoom in, gulir keluar. >> Saya punya pertanyaan. >> Ya?

278
00:20:37,730 --> 00:20:44,410
[Siswa] Ketika Anda mendefinisikan struct, hal-hal seperti diinisialisasi apa pun?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Oke. Jadi, Anda harus menginisialisasi -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Ketika Anda mendefinisikan, atau ketika Anda mendeklarasikan sebuah struct,

281
00:20:50,450 --> 00:20:55,600
tidak diinisialisasi secara default, itu hanya seperti jika Anda mendeklarasikan int.

282
00:20:55,600 --> 00:20:59,020
Ini hal yang persis sama. Ini seperti setiap bidang individu

283
00:20:59,020 --> 00:21:04,460
dapat memiliki nilai sampah di dalamnya. >> Dan apakah mungkin untuk menentukan - atau untuk mendeklarasikan struct

284
00:21:04,460 --> 00:21:07,740
dengan cara yang itu tidak menginisialisasi mereka?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ya. Jadi, shortcut inisialisasi sintaks

286
00:21:13,200 --> 00:21:18,660
akan terlihat seperti -

287
00:21:18,660 --> 00:21:22,200
Ada dua cara yang dapat kita lakukan ini. Saya pikir kita harus compile

288
00:21:22,200 --> 00:21:25,840
untuk membuat dentang yakin juga melakukan hal ini.

289
00:21:25,840 --> 00:21:28,510
Urutan argumen yang datang dalam struct,

290
00:21:28,510 --> 00:21:32,170
Anda menempatkan sebagai urutan argumen dalam kurung kurawal tersebut.

291
00:21:32,170 --> 00:21:35,690
Jadi jika Anda ingin menginisialisasi ke 9 dan meninggalkan menjadi batal dan kemudian ke kanan menjadi nol,

292
00:21:35,690 --> 00:21:41,570
itu akan menjadi 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternatif lain adalah, dan editor tidak menyukai sintaks ini,

294
00:21:47,890 --> 00:21:50,300
dan berpikir saya ingin blok baru,

295
00:21:50,300 --> 00:22:01,800
namun alternatif adalah sesuatu seperti -

296
00:22:01,800 --> 00:22:04,190
di sini, saya akan meletakkannya pada baris baru.

297
00:22:04,190 --> 00:22:09,140
Anda secara eksplisit bisa mengatakan, saya lupa sintaks yang tepat.

298
00:22:09,140 --> 00:22:13,110
Jadi Anda secara eksplisit dapat mengatasinya dengan nama, dan berkata,

299
00:22:13,110 --> 00:22:21,570
C, atau. Nilai. = 9, kiri =. NULL.

300
00:22:21,570 --> 00:22:24,540
Saya menduga ini perlu menjadi koma.

301
00:22:24,540 --> 00:22:29,110
. Kanan = NULL, sehingga cara ini Anda tidak

302
00:22:29,110 --> 00:22:33,780
benar-benar perlu untuk mengetahui urutan struct,

303
00:22:33,780 --> 00:22:36,650
dan ketika Anda membaca ini, itu jauh lebih eksplisit

304
00:22:36,650 --> 00:22:41,920
tentang apa nilai yang sedang diinisialisasi ke.

305
00:22:41,920 --> 00:22:44,080
>> Hal ini terjadi untuk menjadi salah satu hal yang -

306
00:22:44,080 --> 00:22:49,100
jadi, untuk sebagian besar, C + + adalah superset dari C.

307
00:22:49,100 --> 00:22:54,160
Anda dapat mengambil kode C, memindahkannya ke C + +, dan harus mengkompilasi.

308
00:22:54,160 --> 00:22:59,570
Ini adalah salah satu hal yang C + + tidak mendukung, sehingga orang-orang cenderung untuk tidak melakukannya.

309
00:22:59,570 --> 00:23:01,850
Saya tidak tahu apakah itu satu-satunya alasan orang cenderung untuk tidak melakukannya,

310
00:23:01,850 --> 00:23:10,540
namun kasus di mana saya perlu untuk menggunakannya diperlukan untuk bekerja dengan C + + dan jadi saya tidak bisa menggunakan ini.

311
00:23:10,540 --> 00:23:14,000
Contoh lain dari sesuatu yang tidak bekerja dengan C + + adalah

312
00:23:14,000 --> 00:23:16,940
bagaimana malloc mengembalikan "void *," secara teknis,

313
00:23:16,940 --> 00:23:20,200
tetapi Anda hanya bisa mengatakan char * x = malloc apapun,

314
00:23:20,200 --> 00:23:22,840
dan secara otomatis akan dilemparkan ke char *.

315
00:23:22,840 --> 00:23:25,450
Itu cor otomatis tidak terjadi di C + +.

316
00:23:25,450 --> 00:23:28,150
Itu tidak akan mengkompilasi, dan Anda secara eksplisit akan perlu untuk mengatakan

317
00:23:28,150 --> 00:23:34,510
char *, malloc, apa pun, untuk melemparkan ke char *.

318
00:23:34,510 --> 00:23:37,270
Ada tidak banyak hal yang C dan C + + tidak setuju pada,

319
00:23:37,270 --> 00:23:40,620
tetapi mereka adalah dua.

320
00:23:40,620 --> 00:23:43,120
Jadi kita akan pergi dengan sintaks ini.

321
00:23:43,120 --> 00:23:46,150
Tetapi bahkan jika kita tidak pergi dengan sintaks yang,

322
00:23:46,150 --> 00:23:49,470
apa - mungkin salah dengan ini?

323
00:23:49,470 --> 00:23:52,170
[Siswa] saya tidak perlu dereference itu? >> Ya.

324
00:23:52,170 --> 00:23:55,110
Ingat bahwa panah memiliki dereference implisit,

325
00:23:55,110 --> 00:23:58,230
dan jadi ketika kami hanya berurusan dengan struct,

326
00:23:58,230 --> 00:24:04,300
kita ingin menggunakan. untuk mendapatkan di dalam bidang struct.

327
00:24:04,300 --> 00:24:07,200
Dan satu-satunya waktu yang kita gunakan panah adalah ketika kita ingin melakukan -

328
00:24:07,200 --> 00:24:13,450
baik, panah adalah setara dengan -

329
00:24:13,450 --> 00:24:17,020
itulah yang akan berarti jika saya menggunakan panah.

330
00:24:17,020 --> 00:24:24,600
Semua sarana panah, dereference ini, sekarang aku di struct, dan saya bisa mendapatkan lapangan.

331
00:24:24,600 --> 00:24:28,040
Entah mendapatkan lapangan langsung atau dereference dan mendapatkan lapangan -

332
00:24:28,040 --> 00:24:30,380
Saya kira ini harus menjadi nilai.

333
00:24:30,380 --> 00:24:33,910
Tapi di sini aku berurusan hanya dengan struct, bukan pointer ke struct,

334
00:24:33,910 --> 00:24:38,780
dan jadi saya tidak dapat menggunakan panah.

335
00:24:38,780 --> 00:24:47,510
Tapi hal semacam ini bisa kita lakukan untuk semua node.

336
00:24:47,510 --> 00:24:55,790
Oh my God.

337
00:24:55,790 --> 00:25:09,540
Ini adalah 6, 7, dan 3.

338
00:25:09,540 --> 00:25:16,470
Kemudian kita dapat mengatur cabang di pohon kita, kita dapat memiliki 7 -

339
00:25:16,470 --> 00:25:21,650
kita dapat memiliki, kiri harus menunjuk ke 3.

340
00:25:21,650 --> 00:25:25,130
Jadi bagaimana kita melakukannya?

341
00:25:25,130 --> 00:25:29,320
[Mahasiswa, dipahami] >> Ya. Alamat node3,

342
00:25:29,320 --> 00:25:34,170
dan jika Anda tidak memiliki alamat, maka tidak akan mengkompilasi.

343
00:25:34,170 --> 00:25:38,190
Tapi ingat bahwa ini adalah pointer ke node berikutnya.

344
00:25:38,190 --> 00:25:44,930
Hak harus menunjuk ke 9,

345
00:25:44,930 --> 00:25:53,330
dan 3 harus menunjuk pada hak untuk 6.

346
00:25:53,330 --> 00:25:58,480
Saya pikir ini adalah mengatur semua. Ada komentar atau pertanyaan?

347
00:25:58,480 --> 00:26:02,060
[Mahasiswa, dipahami] akar akan menjadi 7.

348
00:26:02,060 --> 00:26:08,210
Kami hanya bisa mengatakan simpul * ptr =

349
00:26:08,210 --> 00:26:14,160
atau akar, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Untuk tujuan kita, kita akan berurusan dengan insert,

351
00:26:20,730 --> 00:26:25,490
jadi kita akan ingin menulis fungsi untuk memasukkan ke dalam pohon biner

352
00:26:25,490 --> 00:26:34,230
dan insert pasti akan menelepon malloc untuk membuat node baru untuk pohon ini.

353
00:26:34,230 --> 00:26:36,590
Jadi hal-hal yang akan mendapatkan berantakan dengan fakta bahwa beberapa node

354
00:26:36,590 --> 00:26:38,590
saat ini di stack

355
00:26:38,590 --> 00:26:43,680
dan node lain akan berakhir di heap ketika kita memasukkan mereka.

356
00:26:43,680 --> 00:26:47,640
Ini adalah hal yang sah, tapi satu-satunya alasan

357
00:26:47,640 --> 00:26:49,600
kita dapat melakukan hal ini di stack

358
00:26:49,600 --> 00:26:51,840
karena itu seperti contoh buat yang kita tahu

359
00:26:51,840 --> 00:26:56,360
pohon seharusnya dibangun sebagai 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Jika kita tidak memiliki ini, maka kita tidak perlu malloc di tempat pertama.

361
00:27:02,970 --> 00:27:06,160
Seperti yang akan kita lihat sedikit kemudian, kita harus malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Sekarang ini sangat masuk akal untuk menempatkan di stack,

363
00:27:08,570 --> 00:27:14,750
tapi mari kita mengubah ini untuk implementasi malloc.

364
00:27:14,750 --> 00:27:17,160
Jadi masing-masing kini akan menjadi sesuatu seperti

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

366
00:27:24,240 --> 00:27:28,040
Dan sekarang kita akan harus melakukan cek kami.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Aku tidak ingin itu -

368
00:27:34,010 --> 00:27:40,950
kembali 1, dan kemudian kita bisa melakukan node9-> karena sekarang ini pointer,

369
00:27:40,950 --> 00:27:45,300
value = 6, node9-> kiri = NULL,

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

371
00:27:48,930 --> 00:27:51,410
dan kita akan harus melakukan itu untuk masing-masing node.

372
00:27:51,410 --> 00:27:57,490
Jadi, bukannya, mari kita memasukkannya dalam fungsi yang terpisah.

373
00:27:57,490 --> 00:28:00,620
Mari kita menyebutnya simpul * build_node,

374
00:28:00,620 --> 00:28:09,050
dan ini agak mirip dengan API yang kami sediakan untuk Huffman coding.

375
00:28:09,050 --> 00:28:12,730
Kami memberikan fungsi initializer untuk pohon

376
00:28:12,730 --> 00:28:20,520
dan Deconstructor "fungsi" bagi pohon-pohon dan sama untuk hutan.

377
00:28:20,520 --> 00:28:22,570
>> Jadi di sini kita akan memiliki fungsi initializer

378
00:28:22,570 --> 00:28:25,170
hanya membangun simpul bagi kita.

379
00:28:25,170 --> 00:28:29,320
Dan itu akan terlihat cukup banyak persis seperti ini.

380
00:28:29,320 --> 00:28:32,230
Dan aku bahkan akan menjadi malas dan tidak mengubah nama variabel,

381
00:28:32,230 --> 00:28:34,380
meskipun node9 tidak masuk akal lagi.

382
00:28:34,380 --> 00:28:38,610
Oh, saya kira nilai node9 tak seharusnya 6.

383
00:28:38,610 --> 00:28:42,800
Sekarang kita dapat kembali node9.

384
00:28:42,800 --> 00:28:49,550
Dan di sini kita harus kembali nol.

385
00:28:49,550 --> 00:28:52,690
Semua orang setuju bahwa fungsi build-a-node?

386
00:28:52,690 --> 00:28:59,780
Jadi sekarang kita hanya bisa menelepon bahwa untuk membangun setiap node dengan nilai yang diberikan dan pointer null.

387
00:28:59,780 --> 00:29:09,750
Sekarang kita bisa menyebutnya, yang bisa kita lakukan simpul * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Dan mari kita lakukan. . .

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

390
00:29:33,980 --> 00:29:39,330
Dan sekarang kita ingin mengatur pointer yang sama,

391
00:29:39,330 --> 00:29:42,470
kecuali sekarang semuanya sudah dalam hal pointer

392
00:29:42,470 --> 00:29:48,480
sehingga tidak perlu lagi alamat.

393
00:29:48,480 --> 00:29:56,300
Oke. Jadi apa hal terakhir yang ingin saya lakukan?

394
00:29:56,300 --> 00:30:03,850
Ada kesalahan pengecekan bahwa aku tidak melakukan.

395
00:30:03,850 --> 00:30:06,800
Apa membangun kembali simpul?

396
00:30:06,800 --> 00:30:11,660
[Mahasiswa, dipahami] >> Ya. Jika malloc gagal, itu akan mengembalikan null.

397
00:30:11,660 --> 00:30:16,460
Jadi aku akan malas meletakkannya di sini bukannya melakukan suatu kondisi untuk masing-masing.

398
00:30:16,460 --> 00:30:22,320
Jika (node9 == NULL, atau - bahkan lebih sederhana,

399
00:30:22,320 --> 00:30:28,020
ini setara dengan hanya jika tidak node9.

400
00:30:28,020 --> 00:30:38,310
Jadi jika tidak node9, atau tidak node6, atau tidak node3, atau tidak node7, kembali 1.

401
00:30:38,310 --> 00:30:42,850
Mungkin kita harus mencetak malloc gagal, atau sesuatu.

402
00:30:42,850 --> 00:30:46,680
[Mahasiswa] Apakah palsu sama dengan null juga?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Setiap nilai nol adalah palsu.

404
00:30:51,290 --> 00:30:53,920
Jadi nol adalah nilai nol.

405
00:30:53,920 --> 00:30:56,780
Nol adalah nilai nol. False adalah nilai nol.

406
00:30:56,780 --> 00:31:02,130
Setiap - cukup banyak hanya 2 nilai nol adalah nol dan nol,

407
00:31:02,130 --> 00:31:07,900
palsu hanya hash didefinisikan sebagai nol.

408
00:31:07,900 --> 00:31:13,030
Itu juga berlaku jika kita mendeklarasikan variabel global.

409
00:31:13,030 --> 00:31:17,890
Jika kita memiliki akar simpul * di sini,

410
00:31:17,890 --> 00:31:24,150
kemudian - hal yang baik tentang variabel global adalah bahwa mereka selalu memiliki nilai awal.

411
00:31:24,150 --> 00:31:27,500
Itu tidak benar fungsi, seberapa dalam sini,

412
00:31:27,500 --> 00:31:34,870
jika kita memiliki, seperti *, node atau simpul x.

413
00:31:34,870 --> 00:31:37,380
Kami tidak tahu apa x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
atau kita bisa mencetak mereka dan mereka bisa sewenang-wenang.

415
00:31:40,700 --> 00:31:44,980
Itu tidak benar dari variabel global.

416
00:31:44,980 --> 00:31:47,450
Jadi simpul akar atau x simpul.

417
00:31:47,450 --> 00:31:53,410
Secara default, segala sesuatu yang global, jika tidak secara eksplisit diinisialisasi untuk beberapa nilai,

418
00:31:53,410 --> 00:31:57,390
memiliki nilai nol sebagai nilainya.

419
00:31:57,390 --> 00:32:01,150
Jadi di sini, akar * simpul, kita tidak secara eksplisit menginisialisasi dengan apapun,

420
00:32:01,150 --> 00:32:06,350
sehingga nilai default akan nol, yang merupakan nilai nol dari pointer.

421
00:32:06,350 --> 00:32:11,870
Nilai default dari x akan berarti bahwa x.value adalah nol,

422
00:32:11,870 --> 00:32:14,260
x.left adalah nol, dan x.right adalah null.

423
00:32:14,260 --> 00:32:21,070
Jadi karena itu adalah sebuah struct, semua bidang struct akan nilai nol.

424
00:32:21,070 --> 00:32:24,410
Kita tidak perlu menggunakan itu di sini, meskipun.

425
00:32:24,410 --> 00:32:27,320
[Mahasiswa] The structs berbeda dibandingkan variabel lainnya, dan variabel lainnya

426
00:32:27,320 --> 00:32:31,400
nilai sampah, ini adalah nol?

427
00:32:31,400 --> 00:32:36,220
[Bowden] lain nilai-nilai juga. Jadi dalam x, x akan menjadi nol.

428
00:32:36,220 --> 00:32:40,070
Jika itu di lingkup global, memiliki nilai awal. Oke >>.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Entah nilai awal yang Anda berikan atau nol.

430
00:32:48,950 --> 00:32:53,260
Saya pikir yang menangani semua ini.

431
00:32:53,260 --> 00:32:58,390
>> Oke. Jadi bagian selanjutnya dari pertanyaan bertanya,

432
00:32:58,390 --> 00:33:01,260
"Sekarang kita ingin menulis sebuah fungsi yang disebut mengandung

433
00:33:01,260 --> 00:33:04,930
dengan prototipe bool mengandung nilai int. "

434
00:33:04,930 --> 00:33:08,340
Kami tidak akan melakukan bool mengandung nilai int.

435
00:33:08,340 --> 00:33:15,110
Prototipe kami akan terlihat seperti

436
00:33:15,110 --> 00:33:22,380
bool mengandung (nilai int.

437
00:33:22,380 --> 00:33:24,490
Dan kemudian kita juga akan lulus pohon

438
00:33:24,490 --> 00:33:28,870
bahwa itu harus memeriksa untuk melihat apakah memiliki nilai itu.

439
00:33:28,870 --> 00:33:38,290
Jadi simpul * pohon). Oke.

440
00:33:38,290 --> 00:33:44,440
Dan kemudian kita bisa menyebutnya dengan sesuatu seperti,

441
00:33:44,440 --> 00:33:46,090
mungkin kita akan ingin printf atau sesuatu.

442
00:33:46,090 --> 00:33:51,040
Berisi 6, akar kami.

443
00:33:51,040 --> 00:33:54,300
Itu harus kembali satu, atau benar,

444
00:33:54,300 --> 00:33:59,390
sedangkan berisi 5 root harus return false.

445
00:33:59,390 --> 00:34:02,690
Jadi mengambil kedua untuk melaksanakan ini.

446
00:34:02,690 --> 00:34:06,780
Anda dapat melakukannya baik iteratif atau rekursif.

447
00:34:06,780 --> 00:34:09,739
Yang menyenangkan tentang cara kita telah mengatur segalanya adalah bahwa

448
00:34:09,739 --> 00:34:12,300
itu cocok untuk solusi rekursif kami jauh lebih mudah

449
00:34:12,300 --> 00:34:14,719
daripada cara-variabel global yang melakukannya.

450
00:34:14,719 --> 00:34:19,750
Karena jika kita hanya memiliki mengandung nilai int, maka kita tidak memiliki cara untuk recursing bawah subpohon.

451
00:34:19,750 --> 00:34:24,130
Kami harus memiliki fungsi pembantu terpisah yang recurses turun subpohon bagi kita.

452
00:34:24,130 --> 00:34:29,610
Tapi karena kita telah berubah itu untuk mengambil pohon sebagai argumen,

453
00:34:29,610 --> 00:34:32,760
yang harus selalu berada di tempat pertama,

454
00:34:32,760 --> 00:34:35,710
sekarang kita bisa recurse lebih mudah.

455
00:34:35,710 --> 00:34:38,960
Jadi iteratif atau rekursif, kita akan pergi ke baik,

456
00:34:38,960 --> 00:34:46,139
tetapi kita akan melihat bahwa ujung rekursif sampai menjadi cukup mudah.

457
00:34:59,140 --> 00:35:02,480
Oke. Apakah ada yang memiliki sesuatu yang kita dapat bekerja dengan?

458
00:35:02,480 --> 00:35:12,000
>> [Mahasiswa] Aku punya solusi iteratif. >> Baiklah, iteratif.

459
00:35:12,000 --> 00:35:16,030
Oke, ini tampak bagus.

460
00:35:16,030 --> 00:35:18,920
Jadi, ingin berjalan kita melalui itu?

461
00:35:18,920 --> 00:35:25,780
[Mahasiswa] Tentu. Jadi saya menetapkan variabel temp untuk mendapatkan simpul pertama dari pohon.

462
00:35:25,780 --> 00:35:28,330
Dan kemudian aku hanya dilingkarkan melalui sementara suhu tidak nol sama,

463
00:35:28,330 --> 00:35:31,700
jadi sementara masih di pohon, saya kira.

464
00:35:31,700 --> 00:35:35,710
Dan jika nilai sama dengan nilai yang suhu menunjuk ke,

465
00:35:35,710 --> 00:35:37,640
maka mengembalikan nilai itu.

466
00:35:37,640 --> 00:35:40,210
Jika tidak, itu akan memeriksa apakah itu di sisi kanan atau sisi kiri.

467
00:35:40,210 --> 00:35:43,400
Jika Anda pernah mendapatkan situasi di mana tidak ada pohon lagi,

468
00:35:43,400 --> 00:35:47,330
maka kembali - itu keluar loop dan kembali palsu.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Oke. Sehingga tampaknya baik.

470
00:35:52,190 --> 00:35:58,470
Ada yang punya komentar pada apa pun?

471
00:35:58,470 --> 00:36:02,400
Saya tidak punya komentar benar sama sekali.

472
00:36:02,400 --> 00:36:11,020
Satu hal yang dapat kita lakukan adalah orang ini.

473
00:36:11,020 --> 00:36:21,660
Oh, itu akan pergi gondrong sedikit.

474
00:36:21,660 --> 00:36:33,460
Saya akan memperbaiki itu. Oke.

475
00:36:33,460 --> 00:36:37,150
>> Setiap orang harus ingat bagaimana terner bekerja.

476
00:36:37,150 --> 00:36:38,610
Ada pasti telah kuis di masa lalu

477
00:36:38,610 --> 00:36:41,170
yang memberikan fungsi dengan operator terner,

478
00:36:41,170 --> 00:36:45,750
dan berkata, menerjemahkan, melakukan sesuatu yang tidak menggunakan terner.

479
00:36:45,750 --> 00:36:49,140
Jadi ini adalah kasus yang sangat umum ketika saya akan berpikir untuk menggunakan terner,

480
00:36:49,140 --> 00:36:54,610
di mana jika beberapa kondisi mengatur variabel untuk sesuatu,

481
00:36:54,610 --> 00:36:58,580
lain mengatur bahwa variabel yang sama untuk sesuatu yang lain.

482
00:36:58,580 --> 00:37:03,390
Itu adalah sesuatu yang sangat sering dapat diubah menjadi hal semacam ini

483
00:37:03,390 --> 00:37:14,420
di mana mengatur variabel yang ini - atau, juga, apakah ini benar? Maka ini, yang lain ini.

484
00:37:14,420 --> 00:37:18,550
[Mahasiswa] Yang pertama adalah jika benar, kan?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Ya. Cara saya selalu membaca itu, suhu sama dengan nilai yang lebih besar dari nilai temp,

486
00:37:25,570 --> 00:37:30,680
maka ini, yang lain ini. Ini mengajukan pertanyaan.

487
00:37:30,680 --> 00:37:35,200
Apakah yang lebih besar? Kemudian lakukan hal pertama. Lain melakukan hal yang kedua.

488
00:37:35,200 --> 00:37:41,670
Saya hampir selalu - usus besar, saya hanya - di kepala saya, saya baca sebagai yang lain.

489
00:37:41,670 --> 00:37:47,180
>> Apakah ada yang punya solusi rekursif?

490
00:37:47,180 --> 00:37:49,670
Oke. Ini yang kita akan - sudah bisa menjadi besar,

491
00:37:49,670 --> 00:37:53,990
tapi kami akan membuatnya lebih baik.

492
00:37:53,990 --> 00:37:58,720
Hal ini cukup banyak ide yang sama persis.

493
00:37:58,720 --> 00:38:03,060
Hanya saja, baik, apakah Anda ingin menjelaskan?

494
00:38:03,060 --> 00:38:08,340
[Mahasiswa] Tentu. Jadi kita memastikan bahwa pohon tersebut tidak nol pertama,

495
00:38:08,340 --> 00:38:13,380
karena jika pohon adalah null maka akan return false karena kita belum menemukannya.

496
00:38:13,380 --> 00:38:19,200
Dan jika masih ada pohon, kita pergi ke - pertama-tama kita memeriksa apakah nilai adalah node saat ini.

497
00:38:19,200 --> 00:38:23,740
Kembali benar jika, dan jika tidak kita recurse di sebelah kiri atau kanan.

498
00:38:23,740 --> 00:38:25,970
Apakah itu terdengar tepat? >> Mm-hmm. (Perjanjian)

499
00:38:25,970 --> 00:38:33,880
Jadi melihat bahwa ini hampir - struktural sangat mirip dengan solusi iteratif.

500
00:38:33,880 --> 00:38:38,200
Hanya saja bahwa alih-alih recursing, kami memiliki loop sementara.

501
00:38:38,200 --> 00:38:40,840
Dan kasus dasar di sini di mana pohon tidak nol sama

502
00:38:40,840 --> 00:38:44,850
adalah kondisi di mana kita pecah keluar dari while loop.

503
00:38:44,850 --> 00:38:50,200
Mereka sangat mirip. Tapi kami akan mengambil satu langkah lebih jauh.

504
00:38:50,200 --> 00:38:54,190
Sekarang, kami melakukan hal yang sama di sini.

505
00:38:54,190 --> 00:38:57,680
Perhatikan kita kembali hal yang sama di kedua jalur,

506
00:38:57,680 --> 00:39:00,220
kecuali untuk satu argumen berbeda.

507
00:39:00,220 --> 00:39:07,950
Jadi kita akan membuat itu menjadi terner.

508
00:39:07,950 --> 00:39:13,790
Aku memukul sesuatu pilihan, dan itu membuat simbol. Oke.

509
00:39:13,790 --> 00:39:21,720
Jadi kita akan kembali mengandung itu.

510
00:39:21,720 --> 00:39:28,030
Hal ini semakin menjadi beberapa baris, dengan baik, diperbesar itu.

511
00:39:28,030 --> 00:39:31,060
Biasanya, sebagai hal gaya, saya tidak berpikir banyak orang

512
00:39:31,060 --> 00:39:38,640
menempatkan spasi setelah panah, tapi saya kira jika Anda konsisten, tidak apa-apa.

513
00:39:38,640 --> 00:39:44,320
Jika nilai kurang dari nilai pohon, kami ingin recurse di sebelah kiri pohon,

514
00:39:44,320 --> 00:39:53,890
lain kita ingin recurse di sebelah kanan pohon.

515
00:39:53,890 --> 00:39:58,610
Jadi itu salah satu langkah untuk membuat tampilan ini lebih kecil.

516
00:39:58,610 --> 00:40:02,660
Langkah dua membuat tampilan ini lebih kecil -

517
00:40:02,660 --> 00:40:09,150
kita dapat memisahkan ini untuk beberapa baris.

518
00:40:09,150 --> 00:40:16,500
Oke. Langkah dua sehingga terlihat lebih kecil di sini,

519
00:40:16,500 --> 00:40:25,860
sehingga nilai kembali sama dengan nilai pohon, atau berisi apapun.

520
00:40:25,860 --> 00:40:28,340
>> Ini merupakan hal yang penting.

521
00:40:28,340 --> 00:40:30,860
Saya tidak yakin jika ia mengatakan itu tandasnya di kelas,

522
00:40:30,860 --> 00:40:34,740
tapi itu disebut hubungan arus pendek evaluasi.

523
00:40:34,740 --> 00:40:41,060
Idenya di sini adalah nilai == nilai pohon.

524
00:40:41,060 --> 00:40:49,960
Jika itu benar, maka ini adalah benar, dan kami ingin 'atau' bahwa dengan apa pun di sini.

525
00:40:49,960 --> 00:40:52,520
Jadi tanpa berpikir tentang apa pun ada di sini,

526
00:40:52,520 --> 00:40:55,070
apa seluruh ekspresi akan kembali?

527
00:40:55,070 --> 00:40:59,430
[Mahasiswa] Benar? >> Ya, karena sesungguhnya apa-apa,

528
00:40:59,430 --> 00:41:04,990
or'd - or'd atau benar dengan apa pun tentu benar.

529
00:41:04,990 --> 00:41:08,150
Jadi segera setelah kami melihat nilai kembali = nilai pohon,

530
00:41:08,150 --> 00:41:10,140
kita hanya akan kembali benar.

531
00:41:10,140 --> 00:41:15,710
Bahkan tidak akan recurse lebih berisi di telepon.

532
00:41:15,710 --> 00:41:20,980
Kita dapat mengambil satu langkah lebih jauh.

533
00:41:20,980 --> 00:41:29,490
Pohon kembali tidak nol sama dan semua ini.

534
00:41:29,490 --> 00:41:32,650
Hal itu membuat fungsi satu-line.

535
00:41:32,650 --> 00:41:36,790
Ini juga merupakan contoh dari hubungan arus pendek evaluasi.

536
00:41:36,790 --> 00:41:40,680
Tapi sekarang itu adalah ide yang sama -

537
00:41:40,680 --> 00:41:47,320
bukannya - jadi jika pohon tidak nol sama - atau, baik,

538
00:41:47,320 --> 00:41:49,580
jika pohon tidak nol sama, yang merupakan kasus yang buruk,

539
00:41:49,580 --> 00:41:54,790
jika pohon sama dengan nol, maka kondisi pertama akan menjadi palsu.

540
00:41:54,790 --> 00:42:00,550
Jadi palsu anded dengan apa pun akan menjadi apa?

541
00:42:00,550 --> 00:42:04,640
[Mahasiswa] False. >> Ya. Ini adalah bagian lain dari sirkuit pendek evaluasi,

542
00:42:04,640 --> 00:42:10,710
di mana jika pohon tidak nol tidak sama, maka kita tidak akan bahkan pergi -

543
00:42:10,710 --> 00:42:14,930
atau jika pohon tidak nol sama, maka kita tidak akan melakukan value == nilai pohon.

544
00:42:14,930 --> 00:42:17,010
Kita hanya akan segera kembali palsu.

545
00:42:17,010 --> 00:42:20,970
Yang penting, karena jika tidak sirkuit pendek mengevaluasi,

546
00:42:20,970 --> 00:42:25,860
maka jika pohon tidak nol sama, ini kondisi kedua akan kesalahan seg,

547
00:42:25,860 --> 00:42:32,510
karena pohon-> nilai dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Jadi itulah yang. Bisa membuat ini - pergeseran sekali atas.

549
00:42:40,490 --> 00:42:44,840
Ini adalah hal yang sangat umum juga, tidak membuat satu baris dengan ini,

550
00:42:44,840 --> 00:42:49,000
tapi itu hal yang umum dalam kondisi, mungkin tidak di sini,

551
00:42:49,000 --> 00:42:59,380
tetapi jika (pohon = NULL,! dan pohon-> value == value), melakukan apapun.

552
00:42:59,380 --> 00:43:01,560
Ini adalah kondisi yang sangat umum, di mana daripada harus

553
00:43:01,560 --> 00:43:06,770
untuk istirahat ini menjadi dua ifs, di mana suka, adalah nol pohon?

554
00:43:06,770 --> 00:43:11,780
Oke, itu tidak nol, jadi sekarang adalah nilai pohon sama dengan nilai? Lakukan ini.

555
00:43:11,780 --> 00:43:17,300
Sebaliknya, kondisi ini, ini tidak akan pernah seg kesalahan

556
00:43:17,300 --> 00:43:21,220
karena akan keluar jika hal ini terjadi menjadi nol.

557
00:43:21,220 --> 00:43:24,000
Nah, saya kira jika pohon Anda adalah pointer sepenuhnya valid, masih bisa seg kesalahan,

558
00:43:24,000 --> 00:43:26,620
tetapi tidak bisa seg kesalahan jika pohon adalah null.

559
00:43:26,620 --> 00:43:32,900
Jika itu adalah nol, itu akan pecah sebelum Anda pernah dereferenced pointer di tempat pertama.

560
00:43:32,900 --> 00:43:35,000
[Mahasiswa] Apakah ini disebut evaluasi malas?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] evaluasi malas adalah hal yang terpisah.

562
00:43:40,770 --> 00:43:49,880
Evaluasi malas lebih seperti Anda meminta nilai,

563
00:43:49,880 --> 00:43:54,270
Anda meminta untuk menghitung nilai, jenis, tetapi Anda tidak membutuhkannya segera.

564
00:43:54,270 --> 00:43:59,040
Jadi sampai Anda benar-benar membutuhkannya, tidak dievaluasi.

565
00:43:59,040 --> 00:44:03,920
Ini bukan hal yang persis sama, tetapi dalam pset Huffman,

566
00:44:03,920 --> 00:44:06,520
dikatakan bahwa kita "malas" menulis.

567
00:44:06,520 --> 00:44:08,670
Alasan kami melakukan itu adalah karena kita benar-benar penyangga menulis -

568
00:44:08,670 --> 00:44:11,820
kita tidak ingin menulis bit individu pada suatu waktu,

569
00:44:11,820 --> 00:44:15,450
atau byte individu pada suatu waktu, kita malah ingin mendapatkan potongan byte.

570
00:44:15,450 --> 00:44:19,270
Kemudian setelah kita memiliki sepotong byte, maka kita akan menulis itu.

571
00:44:19,270 --> 00:44:22,640
Meskipun Anda meminta untuk menulis - dan fwrite dan fread melakukan hal yang sama.

572
00:44:22,640 --> 00:44:26,260
Mereka penyangga membaca dan menulis.

573
00:44:26,260 --> 00:44:31,610
Meskipun Anda meminta untuk menulis segera, mungkin tidak akan.

574
00:44:31,610 --> 00:44:34,540
Dan Anda tidak bisa yakin bahwa hal-hal yang akan ditulis

575
00:44:34,540 --> 00:44:37,540
sampai Anda menelepon hfclose atau apapun itu,

576
00:44:37,540 --> 00:44:39,620
yang kemudian berkata, oke, aku menutup file saya,

577
00:44:39,620 --> 00:44:43,450
itu berarti lebih baik aku menulis segala sesuatu yang saya belum ditulis belum.

578
00:44:43,450 --> 00:44:45,770
Hal ini tidak perlu menulis semuanya

579
00:44:45,770 --> 00:44:49,010
sampai Anda menutup file, dan kemudian perlu.

580
00:44:49,010 --> 00:44:56,220
Jadi itulah yang malas - itu menunggu sampai harus terjadi.

581
00:44:56,220 --> 00:44:59,990
Ini - mengambil 51 dan Anda akan masuk ke dalamnya secara lebih rinci,

582
00:44:59,990 --> 00:45:05,470
karena OCaml dan segala sesuatu di 51, semuanya rekursi.

583
00:45:05,470 --> 00:45:08,890
Tidak ada solusi iteratif, pada dasarnya.

584
00:45:08,890 --> 00:45:11,550
Semuanya rekursi, dan evaluasi malas

585
00:45:11,550 --> 00:45:14,790
akan menjadi penting bagi banyak situasi

586
00:45:14,790 --> 00:45:19,920
di mana, jika Anda tidak malas mengevaluasi, itu berarti -

587
00:45:19,920 --> 00:45:24,760
Contoh adalah aliran, yang jauh lebih lama.

588
00:45:24,760 --> 00:45:30,990
Secara teori, Anda bisa memikirkan alam nomor sebagai aliran 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Jadi hal-hal yang malas dievaluasi baik-baik saja.

590
00:45:33,090 --> 00:45:37,210
Jika saya mengatakan saya ingin nomor sepuluh, maka saya dapat mengevaluasi sampai ke nomor sepuluh.

591
00:45:37,210 --> 00:45:40,300
Jika saya ingin nomor keseratus, maka saya dapat mengevaluasi sampai jumlah keseratus.

592
00:45:40,300 --> 00:45:46,290
Tanpa evaluasi malas, maka itu akan mencoba untuk mengevaluasi semua nomor segera.

593
00:45:46,290 --> 00:45:50,000
Anda mengevaluasi angka tak terhingga banyaknya, dan itu hanya tidak mungkin.

594
00:45:50,000 --> 00:45:52,080
Jadi ada banyak situasi di mana malas evaluasi

595
00:45:52,080 --> 00:45:57,840
hanya penting untuk mendapatkan sesuatu untuk bekerja.

596
00:45:57,840 --> 00:46:05,260
>> Sekarang kita ingin menulis insert mana insert akan menjadi

597
00:46:05,260 --> 00:46:08,430
sama berubah dalam definisi.

598
00:46:08,430 --> 00:46:10,470
Jadi sekarang ini memasukkan bool (nilai int).

599
00:46:10,470 --> 00:46:23,850
Kita akan mengubah itu untuk memasukkan bool (int nilai, simpul * pohon).

600
00:46:23,850 --> 00:46:29,120
Kami benar-benar akan mengubah itu lagi dalam sedikit, kita akan melihat mengapa.

601
00:46:29,120 --> 00:46:32,210
Dan mari kita bergerak build_node, hanya untuk heck itu,

602
00:46:32,210 --> 00:46:36,730
atas masukkan sehingga kita tidak perlu menulis prototipe fungsi.

603
00:46:36,730 --> 00:46:42,450
Yang adalah petunjuk bahwa Anda akan menggunakan build_node di insert.

604
00:46:42,450 --> 00:46:49,590
Oke. Ambil satu menit untuk itu.

605
00:46:49,590 --> 00:46:52,130
Saya pikir saya menyelamatkan revisi jika Anda ingin menarik dari itu,

606
00:46:52,130 --> 00:47:00,240
atau, setidaknya, saya lakukan sekarang.

607
00:47:00,240 --> 00:47:04,190
Saya ingin istirahat sedikit untuk berpikir tentang logika insert,

608
00:47:04,190 --> 00:47:08,750
jika Anda tidak bisa memikirkan itu.

609
00:47:08,750 --> 00:47:12,860
Pada dasarnya, Anda hanya akan pernah memasukkan di daun.

610
00:47:12,860 --> 00:47:18,640
Seperti, jika saya memasukkan 1, maka aku pasti akan memasukkan 1 -

611
00:47:18,640 --> 00:47:21,820
Aku akan berubah menjadi hitam - aku akan bisa memasukkan 1 di sini.

612
00:47:21,820 --> 00:47:28,070
Atau jika saya memasukkan 4, saya ingin memasukkan 4 di sini.

613
00:47:28,070 --> 00:47:32,180
Jadi tidak peduli apa yang Anda lakukan, Anda akan memasukkan pada daun.

614
00:47:32,180 --> 00:47:36,130
Semua harus Anda lakukan adalah iterate bawah pohon sampai Anda mendapatkan ke node

615
00:47:36,130 --> 00:47:40,890
yang harus orangtua node, orangtua node baru,

616
00:47:40,890 --> 00:47:44,560
dan kemudian mengubah pointer yang kiri atau kanan, tergantung pada apakah

617
00:47:44,560 --> 00:47:47,060
itu lebih besar dari atau kurang dari node saat ini.

618
00:47:47,060 --> 00:47:51,180
Mengubah pointer yang untuk menunjuk ke simpul baru.

619
00:47:51,180 --> 00:48:05,490
Jadi iterate bawah pohon, membuat titik daun ke node baru.

620
00:48:05,490 --> 00:48:09,810
Juga berpikir tentang mengapa yang melarang jenis situasi sebelumnya,

621
00:48:09,810 --> 00:48:17,990
di mana saya membangun pohon biner di mana itu benar

622
00:48:17,990 --> 00:48:19,920
jika Anda hanya melihat satu node,

623
00:48:19,920 --> 00:48:24,830
tapi 9 adalah di sebelah kiri 7 jika Anda mengulangi turun sepanjang jalan.

624
00:48:24,830 --> 00:48:29,770
Sehingga tidak mungkin dalam skenario ini, karena -

625
00:48:29,770 --> 00:48:32,530
berpikir tentang memasukkan 9 atau sesuatu, pada simpul pertama,

626
00:48:32,530 --> 00:48:35,350
Aku akan melihat 7 dan aku hanya akan pergi ke kanan.

627
00:48:35,350 --> 00:48:38,490
Jadi tidak peduli apa yang saya lakukan, jika saya memasukkan dengan pergi ke daun,

628
00:48:38,490 --> 00:48:40,790
dan daun menggunakan algoritma yang sesuai,

629
00:48:40,790 --> 00:48:43,130
itu akan menjadi mustahil bagi saya untuk memasukkan 9 di sebelah kiri 7

630
00:48:43,130 --> 00:48:48,250
karena begitu aku memukul 7 Aku akan pergi ke kanan.

631
00:48:59,740 --> 00:49:02,070
Apakah ada yang memiliki sesuatu untuk memulai dengan?

632
00:49:02,070 --> 00:49:05,480
[Siswa] saya lakukan. Tentu >>.

633
00:49:05,480 --> 00:49:09,200
[Mahasiswa, dipahami]

634
00:49:09,200 --> 00:49:14,390
[Mahasiswa lainnya, tidak dapat dipahami]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Ini dihargai. Oke. Ingin menjelaskan?

636
00:49:18,330 --> 00:49:20,690
>> [Mahasiswa] Karena kita tahu bahwa kita sedang memasukkan

637
00:49:20,690 --> 00:49:24,060
baru node pada akhir pohon,

638
00:49:24,060 --> 00:49:28,070
Saya dilingkarkan melalui pohon iteratif

639
00:49:28,070 --> 00:49:31,360
sampai aku ke node yang menunjuk ke null.

640
00:49:31,360 --> 00:49:34,220
Dan kemudian saya memutuskan untuk meletakkannya baik di sisi kanan atau sisi kiri

641
00:49:34,220 --> 00:49:37,420
menggunakan variabel yang tepat, itu mengatakan kepada saya di mana untuk meletakkannya.

642
00:49:37,420 --> 00:49:41,850
Dan kemudian, pada dasarnya, saya hanya membuat yang terakhir -

643
00:49:41,850 --> 00:49:47,520
bahwa node suhu menunjuk ke simpul baru yang menciptakan itu,

644
00:49:47,520 --> 00:49:50,770
baik di sisi kiri maupun di sisi kanan, tergantung pada apa nilai tepat adalah.

645
00:49:50,770 --> 00:49:56,530
Akhirnya, saya menetapkan nilai node baru dengan nilai pengujian.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Oke, jadi saya melihat satu masalah di sini.

647
00:49:59,550 --> 00:50:02,050
Ini seperti 95% dari perjalanan ke sana.

648
00:50:02,050 --> 00:50:07,550
Salah satu masalah yang saya lihat, baik, tidak ada orang lain melihat masalah?

649
00:50:07,550 --> 00:50:18,400
Apa keadaan di mana mereka keluar dari loop?

650
00:50:18,400 --> 00:50:22,100
[Mahasiswa] Jika suhu adalah null? >> Ya. Jadi bagaimana Anda keluar dari loop adalah jika suhu adalah null.

651
00:50:22,100 --> 00:50:30,220
Tapi apa yang saya lakukan di sini?

652
00:50:30,220 --> 00:50:35,410
Saya dereference temp, yang pasti nol.

653
00:50:35,410 --> 00:50:39,840
Jadi hal lain yang perlu Anda lakukan adalah tidak hanya melacak sampai temp adalah nol,

654
00:50:39,840 --> 00:50:45,590
Anda ingin melacak orang tua setiap saat.

655
00:50:45,590 --> 00:50:52,190
Kami juga ingin orangtua simpul *, saya kira kita bisa menjaga bahwa pada nol pada awalnya.

656
00:50:52,190 --> 00:50:55,480
Ini akan memiliki perilaku aneh untuk akar pohon,

657
00:50:55,480 --> 00:50:59,210
tapi kita akan mendapatkan itu.

658
00:50:59,210 --> 00:51:03,950
Jika nilai lebih besar dari apa pun, maka temp = temp benar.

659
00:51:03,950 --> 00:51:07,910
Tapi sebelum kita melakukan itu, orangtua temp =.

660
00:51:07,910 --> 00:51:14,500
Atau orang tua selalu akan suhu yang sama? Apakah itu kasus ini?

661
00:51:14,500 --> 00:51:19,560
Jika suhu tidak null, maka aku akan bergerak ke bawah, tidak peduli apa,

662
00:51:19,560 --> 00:51:24,030
ke node yang temp adalah orangtua.

663
00:51:24,030 --> 00:51:27,500
Jadi orang tua akan menjadi temp, dan kemudian aku pindah suhu turun.

664
00:51:27,500 --> 00:51:32,410
Sekarang temp adalah nol, tapi poin orangtua kepada orang tua hal yang null.

665
00:51:32,410 --> 00:51:39,110
Jadi di sini, saya tidak ingin diatur tepat sama dengan 1.

666
00:51:39,110 --> 00:51:41,300
Jadi saya pindah ke kanan, jadi jika benar = 1,

667
00:51:41,300 --> 00:51:45,130
dan saya kira Anda juga ingin melakukan -

668
00:51:45,130 --> 00:51:48,530
jika Anda pindah ke kiri, Anda ingin mengatur hak yang sama untuk 0.

669
00:51:48,530 --> 00:51:55,950
Atau yang lain jika Anda pernah bergerak ke kanan.

670
00:51:55,950 --> 00:51:58,590
Jadi benar = 0. Jika benar = 1,

671
00:51:58,590 --> 00:52:04,260
sekarang kita ingin membuat newNode pointer orangtua yang tepat,

672
00:52:04,260 --> 00:52:08,520
lain kita ingin membuat newNode pointer orangtua kiri.

673
00:52:08,520 --> 00:52:16,850
Pertanyaan itu?

674
00:52:16,850 --> 00:52:24,880
Oke. Jadi ini adalah cara kita - baik, sebenarnya, bukan untuk melakukan hal ini,

675
00:52:24,880 --> 00:52:29,630
Kami setengah berharap Anda untuk menggunakan build_node.

676
00:52:29,630 --> 00:52:40,450
Dan kemudian jika newNode sama dengan nol, kembali palsu.

677
00:52:40,450 --> 00:52:44,170
Itulah itu. Sekarang, ini adalah apa yang kami harapkan Anda lakukan.

678
00:52:44,170 --> 00:52:47,690
>> Inilah solusi staf lakukan.

679
00:52:47,690 --> 00:52:52,360
Saya tidak setuju dengan hal ini sebagai cara yang "benar" akan hal itu

680
00:52:52,360 --> 00:52:57,820
tapi ini baik-baik saja dan itu akan bekerja.

681
00:52:57,820 --> 00:53:02,840
Satu hal itu adalah hak sedikit aneh sekarang adalah

682
00:53:02,840 --> 00:53:08,310
jika pohon dimulai sebagai null, kita lulus dalam pohon nol.

683
00:53:08,310 --> 00:53:12,650
Saya kira itu tergantung pada bagaimana Anda mendefinisikan perilaku lewat di pohon nol.

684
00:53:12,650 --> 00:53:15,490
Saya akan berpikir bahwa jika Anda lulus dalam pohon nol,

685
00:53:15,490 --> 00:53:17,520
kemudian memasukkan nilai ke sebuah pohon nol

686
00:53:17,520 --> 00:53:23,030
hanya harus kembali pohon di mana satu-satunya nilai adalah bahwa node tunggal.

687
00:53:23,030 --> 00:53:25,830
Apakah orang setuju dengan itu? Anda bisa, jika Anda ingin,

688
00:53:25,830 --> 00:53:28,050
jika Anda lulus di pohon nol

689
00:53:28,050 --> 00:53:31,320
dan Anda ingin memasukkan nilai ke dalamnya, kembali palsu.

690
00:53:31,320 --> 00:53:33,830
Terserah Anda untuk menentukan hal itu.

691
00:53:33,830 --> 00:53:38,320
Untuk melakukan hal pertama yang saya katakan dan kemudian -

692
00:53:38,320 --> 00:53:40,720
baik, Anda akan mengalami kesulitan melakukan hal itu, karena

693
00:53:40,720 --> 00:53:44,090
akan lebih mudah jika kita memiliki pointer global untuk hal tersebut,

694
00:53:44,090 --> 00:53:48,570
tapi kami tidak, jadi jika pohon adalah null, tidak ada yang bisa kita lakukan tentang hal itu.

695
00:53:48,570 --> 00:53:50,960
Kami hanya bisa kembali palsu.

696
00:53:50,960 --> 00:53:52,840
Jadi aku akan mengubah insert.

697
00:53:52,840 --> 00:53:56,540
Kami secara teknis hanya bisa mengubah ini di sini,

698
00:53:56,540 --> 00:53:58,400
bagaimana itu iterasi atas hal-hal,

699
00:53:58,400 --> 00:54:04,530
tapi aku akan mengubah insert untuk mengambil simpul pohon **.

700
00:54:04,530 --> 00:54:07,510
Ganda pointer.

701
00:54:07,510 --> 00:54:09,710
Apa artinya ini?

702
00:54:09,710 --> 00:54:12,330
Alih-alih berurusan dengan pointer ke node,

703
00:54:12,330 --> 00:54:16,690
hal yang saya akan memanipulasi adalah pointer ini.

704
00:54:16,690 --> 00:54:18,790
Aku akan memanipulasi pointer ini.

705
00:54:18,790 --> 00:54:21,770
Aku akan memanipulasi pointer secara langsung.

706
00:54:21,770 --> 00:54:25,760
Ini masuk akal karena, pikirkan bawah -

707
00:54:25,760 --> 00:54:33,340
baik, sekarang ini menunjuk ke null.

708
00:54:33,340 --> 00:54:38,130
Apa yang saya ingin lakukan adalah memanipulasi pointer ini untuk menunjuk ke tidak nol.

709
00:54:38,130 --> 00:54:40,970
Saya ingin untuk menunjuk ke simpul baru.

710
00:54:40,970 --> 00:54:44,870
Jika saya hanya melacak pointer ke pointer saya,

711
00:54:44,870 --> 00:54:47,840
maka saya tidak perlu melacak pointer orangtua.

712
00:54:47,840 --> 00:54:52,640
Aku hanya bisa melacak untuk melihat apakah pointer menunjuk ke null,

713
00:54:52,640 --> 00:54:54,580
dan jika pointer menunjuk ke null,

714
00:54:54,580 --> 00:54:57,370
mengubahnya untuk menunjuk ke simpul saya inginkan.

715
00:54:57,370 --> 00:55:00,070
Dan saya bisa mengubahnya karena saya memiliki pointer ke pointer.

716
00:55:00,070 --> 00:55:02,040
Mari kita lihat sekarang ini.

717
00:55:02,040 --> 00:55:05,470
Anda benar-benar dapat melakukannya secara rekursif cukup mudah.

718
00:55:05,470 --> 00:55:08,080
Apakah kita ingin melakukan itu?

719
00:55:08,080 --> 00:55:10,980
Ya, kita lakukan.

720
00:55:10,980 --> 00:55:16,790
>> Mari kita lihat secara rekursif.

721
00:55:16,790 --> 00:55:24,070
Pertama, apa yang kasus dasar kita akan menjadi?

722
00:55:24,070 --> 00:55:29,140
Hampir selalu terjadi basis kami, tetapi sebenarnya, ini agak sulit.

723
00:55:29,140 --> 00:55:34,370
Pertama-tama, jika (pohon == NULL)

724
00:55:34,370 --> 00:55:37,550
Saya kira kita hanya akan kembali palsu.

725
00:55:37,550 --> 00:55:40,460
Hal ini berbeda dari nol pohon Anda menjadi.

726
00:55:40,460 --> 00:55:44,510
Ini adalah pointer ke pointer root anda yang null

727
00:55:44,510 --> 00:55:48,360
yang berarti bahwa pointer root anda tidak ada.

728
00:55:48,360 --> 00:55:52,390
Jadi di sini, jika saya lakukan

729
00:55:52,390 --> 00:55:55,760
* node - mari kita menggunakan kembali hal ini.

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

731
00:55:58,960 --> 00:56:00,730
dan kemudian aku akan menelepon insert dengan melakukan sesuatu seperti,

732
00:56:00,730 --> 00:56:04,540
masukkan ke dalam 4 & root.

733
00:56:04,540 --> 00:56:06,560
Jadi & akar, jika akar adalah simpul *

734
00:56:06,560 --> 00:56:11,170
kemudian & root akan menjadi ** simpul.

735
00:56:11,170 --> 00:56:15,120
Ini berlaku. Dalam kasus ini, pohon, di sini,

736
00:56:15,120 --> 00:56:20,120
Pohon tidak null - atau insert.

737
00:56:20,120 --> 00:56:24,630
Disini. Pohon tidak null; * pohon adalah null, yang baik-baik saja

738
00:56:24,630 --> 00:56:26,680
karena jika pohon * adalah null, maka saya bisa memanipulasi

739
00:56:26,680 --> 00:56:29,210
untuk sekarang menunjukkan apa yang saya inginkan untuk menunjuk ke.

740
00:56:29,210 --> 00:56:34,750
Namun jika pohon adalah null, yang berarti saya hanya datang ke sini dan berkata nol.

741
00:56:34,750 --> 00:56:42,710
Itu tidak masuk akal. Saya tidak bisa berbuat apa-apa dengan itu.

742
00:56:42,710 --> 00:56:45,540
Jika pohon adalah null, kembali palsu.

743
00:56:45,540 --> 00:56:48,220
Jadi saya pada dasarnya sudah mengatakan apa kasus dasar nyata kita adalah.

744
00:56:48,220 --> 00:56:50,580
Dan apa yang yang akan menjadi?

745
00:56:50,580 --> 00:56:55,030
[Mahasiswa, dipahami]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ya. Jadi, jika (* pohon == NULL).

747
00:57:00,000 --> 00:57:04,520
Hal ini berkaitan dengan kasus di sini

748
00:57:04,520 --> 00:57:09,640
di mana jika pointer merah saya adalah pointer saya berfokus pada,

749
00:57:09,640 --> 00:57:12,960
jadi seperti aku fokus pada pointer ini, sekarang aku fokus pada pointer ini.

750
00:57:12,960 --> 00:57:15,150
Sekarang aku fokus pada pointer ini.

751
00:57:15,150 --> 00:57:18,160
Jadi jika pointer merah saya, yang ** simpul saya,

752
00:57:18,160 --> 00:57:22,880
yang pernah - jika *, pointer merah saya, yang pernah nol,

753
00:57:22,880 --> 00:57:28,470
itu berarti bahwa saya di kasus di mana saya sedang berfokus pada pointer yang menunjuk -

754
00:57:28,470 --> 00:57:32,530
ini adalah pointer yang dimiliki daun.

755
00:57:32,530 --> 00:57:41,090
Saya ingin mengubah pointer ini untuk menunjuk ke simpul baru.

756
00:57:41,090 --> 00:57:45,230
Kembalilah ke sini.

757
00:57:45,230 --> 00:57:56,490
NewNode saya hanya akan menjadi simpul * n = build_node (value)

758
00:57:56,490 --> 00:58:07,300
maka n, jika n = NULL, kembali palsu.

759
00:58:07,300 --> 00:58:12,600
Lain kita ingin mengubah apa pointer saat ini sedang menunjuk ke

760
00:58:12,600 --> 00:58:17,830
sekarang menunjuk ke simpul kami baru dibangun.

761
00:58:17,830 --> 00:58:20,280
Kami benar-benar bisa melakukannya di sini.

762
00:58:20,280 --> 00:58:30,660
Alih-alih mengatakan n, kita katakan * tree = jika pohon *.

763
00:58:30,660 --> 00:58:35,450
Semua orang memahami bahwa? Bahwa oleh berurusan dengan pointer ke pointer,

764
00:58:35,450 --> 00:58:40,750
kita dapat mengubah pointer nol untuk menunjuk ke hal yang kita ingin mereka untuk menunjuk ke.

765
00:58:40,750 --> 00:58:42,820
Itulah kasus dasar kami.

766
00:58:42,820 --> 00:58:45,740
>> Sekarang kami kambuh, atau rekursi kami,

767
00:58:45,740 --> 00:58:51,430
akan menjadi sangat mirip dengan semua recursions lain kita sudah melakukan.

768
00:58:51,430 --> 00:58:55,830
Kita akan ingin menyisipkan nilai,

769
00:58:55,830 --> 00:58:59,040
dan sekarang aku akan menggunakan terner lagi, tapi apa yang kondisi kita akan menjadi?

770
00:58:59,040 --> 00:59:05,180
Apa itu yang kita cari untuk memutuskan apakah kita ingin pergi kiri atau kanan?

771
00:59:05,180 --> 00:59:07,760
Mari kita lakukan dalam langkah-langkah terpisah.

772
00:59:07,760 --> 00:59:18,850
If (nilai <) apa?

773
00:59:18,850 --> 00:59:23,200
[Mahasiswa] Nilai Pohon itu?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Jadi ingat bahwa aku saat ini -

775
00:59:27,490 --> 00:59:31,260
[Mahasiswa, dipahami]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Ya, jadi di sini, mari kita mengatakan bahwa ini panah hijau

777
00:59:34,140 --> 00:59:39,050
adalah contoh dari apa pohon saat ini, adalah pointer ke pointer ini.

778
00:59:39,050 --> 00:59:46,610
Jadi itu berarti saya pointer ke pointer ke 3.

779
00:59:46,610 --> 00:59:48,800
Dereference dua kali terdengar baik.

780
00:59:48,800 --> 00:59:51,010
Apa yang harus saya - bagaimana saya melakukan itu?

781
00:59:51,010 --> 00:59:53,210
[Mahasiswa] dereference sekali, dan kemudian melakukan panah itu?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Jadi (* pohon) adalah dereference sekali, -> value

783
00:59:58,420 --> 01:00:05,960
akan memberikan nilai node bahwa aku tidak langsung menunjuk ke.

784
01:00:05,960 --> 01:00:11,980
Jadi saya juga bisa menulis ** tree.value jika Anda lebih suka itu.

785
01:00:11,980 --> 01:00:18,490
Entah bekerja.

786
01:00:18,490 --> 01:00:26,190
Jika itu terjadi, maka saya ingin menelepon masukkan dengan nilai.

787
01:00:26,190 --> 01:00:32,590
Dan apa yang saya simpul diperbarui ** akan menjadi?

788
01:00:32,590 --> 01:00:39,440
Saya ingin pergi ke kiri, sehingga ** tree.left akan menjadi kiri saya.

789
01:00:39,440 --> 01:00:41,900
Dan saya ingin pointer ke hal yang

790
01:00:41,900 --> 01:00:44,930
sehingga jika kiri berakhir menjadi null pointer,

791
01:00:44,930 --> 01:00:48,360
Saya dapat memodifikasi untuk menunjuk ke simpul baru.

792
01:00:48,360 --> 01:00:51,460
>> Dan kasus lain bisa sangat mirip.

793
01:00:51,460 --> 01:00:55,600
Mari kita benar-benar membuat bahwa terner saya sekarang.

794
01:00:55,600 --> 01:01:04,480
Masukkan nilai jika nilai <(** pohon). Nilai.

795
01:01:04,480 --> 01:01:11,040
Kemudian kita ingin memperbarui ** kami ke kiri,

796
01:01:11,040 --> 01:01:17,030
lain kita ingin memperbarui ** kami ke kanan.

797
01:01:17,030 --> 01:01:22,540
[Mahasiswa] Apakah yang mendapatkan pointer ke pointer?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Ingatlah bahwa - ** tree.right adalah bintang simpul.

799
01:01:30,940 --> 01:01:35,040
[Mahasiswa, dipahami] >> Ya.

800
01:01:35,040 --> 01:01:41,140
** Tree.right seperti ini pointer atau sesuatu.

801
01:01:41,140 --> 01:01:45,140
Jadi dengan mengambil pointer untuk itu, yang memberikan apa yang saya inginkan

802
01:01:45,140 --> 01:01:50,090
dari pointer ke orang itu.

803
01:01:50,090 --> 01:01:54,260
[Mahasiswa] Bisakah kita pergi lagi mengapa kita menggunakan dua pointer?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Ya. Jadi - tidak, Anda bisa, dan solusi yang sebelumnya

805
01:01:58,220 --> 01:02:04,540
adalah cara untuk melakukannya tanpa melakukan dua pointer.

806
01:02:04,540 --> 01:02:08,740
Anda harus mampu memahami menggunakan dua pointer,

807
01:02:08,740 --> 01:02:11,660
dan ini adalah solusi yang bersih.

808
01:02:11,660 --> 01:02:16,090
Juga, perhatikan bahwa, apa yang terjadi jika pohon saya -

809
01:02:16,090 --> 01:02:24,480
apa yang terjadi jika akar saya nol? Apa yang terjadi jika saya melakukan hal ini di sini?

810
01:02:24,480 --> 01:02:30,540
Jadi simpul * root = NULL, masukkan ke dalam 4 & root.

811
01:02:30,540 --> 01:02:35,110
Apa yang akan menjadi akar setelah ini?

812
01:02:35,110 --> 01:02:37,470
[Mahasiswa, dipahami] >> Ya.

813
01:02:37,470 --> 01:02:41,710
Nilai akar akan menjadi 4.

814
01:02:41,710 --> 01:02:45,510
Kiri akar akan menjadi nol, benar akar akan menjadi nol.

815
01:02:45,510 --> 01:02:49,490
Dalam kasus di mana kita tidak lulus akar berdasarkan alamat,

816
01:02:49,490 --> 01:02:52,490
kita tidak bisa memodifikasi akar.

817
01:02:52,490 --> 01:02:56,020
Dalam kasus di mana pohon - di mana akar adalah nol,

818
01:02:56,020 --> 01:02:58,410
kami hanya harus kembali palsu. Tidak ada yang bisa kami lakukan.

819
01:02:58,410 --> 01:03:01,520
Kita tidak dapat menyisipkan sebuah node menjadi pohon yang kosong.

820
01:03:01,520 --> 01:03:06,810
Tapi sekarang kita bisa, kita hanya membuat sebuah pohon kosong ke pohon satu simpul.

821
01:03:06,810 --> 01:03:13,400
Yang biasanya cara yang diharapkan bahwa itu seharusnya bekerja.

822
01:03:13,400 --> 01:03:21,610
>> Selain itu, hal ini secara signifikan lebih pendek dibandingkan

823
01:03:21,610 --> 01:03:26,240
juga melacak orangtua, sehingga Anda iterate turun sepanjang jalan.

824
01:03:26,240 --> 01:03:30,140
Sekarang saya memiliki orang tua saya, dan saya hanya memiliki orangtua kanan saya pointer untuk apa pun.

825
01:03:30,140 --> 01:03:35,640
Sebaliknya, jika kita melakukan ini iteratif, itu akan menjadi ide yang sama dengan while loop.

826
01:03:35,640 --> 01:03:38,100
Tapi bukannya harus berurusan dengan pointer orangtua saya,

827
01:03:38,100 --> 01:03:40,600
bukan pointer saya saat ini akan menjadi hal yang

828
01:03:40,600 --> 01:03:43,790
bahwa aku langsung memodifikasi untuk menunjuk ke simpul baru.

829
01:03:43,790 --> 01:03:46,090
Saya tidak harus berurusan dengan apakah itu menunjuk ke kiri.

830
01:03:46,090 --> 01:03:48,810
Saya tidak harus berurusan dengan apakah itu menunjuk ke kanan.

831
01:03:48,810 --> 01:04:00,860
Hanya saja apa pointer ini, aku akan mengaturnya untuk menunjuk ke simpul baru.

832
01:04:00,860 --> 01:04:05,740
Semua orang mengerti cara kerjanya?

833
01:04:05,740 --> 01:04:09,460
Jika tidak mengapa kita ingin melakukannya dengan cara ini,

834
01:04:09,460 --> 01:04:14,920
tapi setidaknya bahwa ini bekerja sebagai solusi?

835
01:04:14,920 --> 01:04:17,110
[Siswa] mana kita kembali benar?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Itu mungkin di sini.

837
01:04:21,550 --> 01:04:26,690
Jika kita benar masukkan, kembali benar.

838
01:04:26,690 --> 01:04:32,010
Lain, di sini kita akan ingin kembali apapun kembali insert.

839
01:04:32,010 --> 01:04:35,950
>> Dan apa yang khusus tentang fungsi rekursif?

840
01:04:35,950 --> 01:04:43,010
Ini ekor rekursif, sehingga selama kita mengkompilasi dengan beberapa optimasi,

841
01:04:43,010 --> 01:04:48,060
akan menyadari bahwa Anda dan tidak akan pernah mendapatkan stack overflow dari ini,

842
01:04:48,060 --> 01:04:53,230
bahkan jika pohon kami memiliki ketinggian 10.000 atau 10 juta.

843
01:04:53,230 --> 01:04:55,630
[Mahasiswa, dipahami]

844
01:04:55,630 --> 01:05:00,310
[Bowden] saya pikir itu melakukannya di Dash - atau apa tingkat optimasi

845
01:05:00,310 --> 01:05:03,820
diperlukan untuk rekursi ekor untuk diakui.

846
01:05:03,820 --> 01:05:09,350
Saya pikir itu mengakui - GCC dan dentang

847
01:05:09,350 --> 01:05:12,610
juga memiliki arti yang berbeda untuk tingkat optimasi mereka.

848
01:05:12,610 --> 01:05:17,870
Saya ingin mengatakan itu DashO 2, untuk memastikan bahwa hal itu akan mengenali rekursi ekor.

849
01:05:17,870 --> 01:05:27,880
Tapi kami - Anda bisa membangun seperti contoh Fibonocci atau sesuatu.

850
01:05:27,880 --> 01:05:30,030
Ini tidak mudah untuk menguji dengan ini, karena sulit untuk membangun

851
01:05:30,030 --> 01:05:32,600
pohon biner yang begitu besar.

852
01:05:32,600 --> 01:05:37,140
Tapi ya, saya pikir itu DashO 2, yang

853
01:05:37,140 --> 01:05:40,580
jika Anda mengkompilasi dengan DashO 2, maka akan mencari rekursi ekor

854
01:05:40,580 --> 01:05:54,030
dan mengoptimalkan yang keluar.

855
01:05:54,030 --> 01:05:58,190
Mari kita kembali ke - masukkan secara harfiah hal terakhir yang dibutuhkan.

856
01:05:58,190 --> 01:06:04,900
Mari kita kembali ke insert di sini

857
01:06:04,900 --> 01:06:07,840
di mana kita akan melakukan ide yang sama.

858
01:06:07,840 --> 01:06:14,340
Ini masih akan memiliki cacat yang tidak mampu untuk sepenuhnya menangani

859
01:06:14,340 --> 01:06:17,940
ketika akar itu sendiri adalah null, atau masuknya masa lalu adalah null,

860
01:06:17,940 --> 01:06:20,060
tapi bukannya berurusan dengan pointer tua,

861
01:06:20,060 --> 01:06:27,430
mari kita menerapkan logika yang sama dari pointer ke pointer menjaga.

862
01:06:27,430 --> 01:06:35,580
Jika di sini kita tetap simpul kami ** skr,

863
01:06:35,580 --> 01:06:37,860
dan kita tidak perlu untuk melacak yang benar lagi,

864
01:06:37,860 --> 01:06:47,190
tapi simpul ** skr = & pohon.

865
01:06:47,190 --> 01:06:54,800
Dan sekarang loop sementara kita akan menjadi saat skr * tidak nol sama.

866
01:06:54,800 --> 01:07:00,270
Tidak perlu untuk melacak orang tua lagi.

867
01:07:00,270 --> 01:07:04,180
Tidak perlu melacak kiri dan kanan.

868
01:07:04,180 --> 01:07:10,190
Dan aku akan menyebutnya temp, karena kita sudah menggunakan temp.

869
01:07:10,190 --> 01:07:17,200
Oke. Jadi, jika (nilai> * temp),

870
01:07:17,200 --> 01:07:24,010
kemudian & (* temp) -> benar

871
01:07:24,010 --> 01:07:29,250
lain temp = & (* temp) -> kiri.

872
01:07:29,250 --> 01:07:32,730
Dan sekarang, pada saat ini, setelah loop sementara,

873
01:07:32,730 --> 01:07:36,380
Saya hanya melakukan ini karena mungkin akan lebih mudah untuk berpikir tentang iteratively daripada rekursif,

874
01:07:36,380 --> 01:07:39,010
tapi setelah ini loop sementara,

875
01:07:39,010 --> 01:07:43,820
* Suhu adalah pointer kita ingin berubah.

876
01:07:43,820 --> 01:07:48,960
>> Sebelum kita memiliki orang tua, dan kami ingin mengubah baik kiri orang tua atau orang tua yang tepat,

877
01:07:48,960 --> 01:07:51,310
tetapi jika kita ingin mengubah hak orang tua,

878
01:07:51,310 --> 01:07:54,550
maka * suhu yang tepat orangtua, dan kita bisa mengubahnya secara langsung.

879
01:07:54,550 --> 01:08:05,860
Jadi di sini, kita bisa lakukan * temp = newNode, dan hanya itu.

880
01:08:05,860 --> 01:08:09,540
Jadi pemberitahuan, semua yang kita lakukan dalam hal ini adalah mengambil baris kode.

881
01:08:09,540 --> 01:08:14,770
Dalam rangka untuk melacak orang tua dalam semua itu adalah upaya tambahan.

882
01:08:14,770 --> 01:08:18,689
Di sini, jika kita hanya melacak pointer ke pointer,

883
01:08:18,689 --> 01:08:22,990
dan bahkan jika kita ingin menyingkirkan semua kurung kurawal sekarang,

884
01:08:22,990 --> 01:08:27,170
membuatnya terlihat lebih pendek.

885
01:08:27,170 --> 01:08:32,529
Ini sekarang adalah solusi yang persis sama,

886
01:08:32,529 --> 01:08:38,210
namun sedikit baris kode.

887
01:08:38,210 --> 01:08:41,229
Setelah Anda mulai mengakui ini sebagai solusi yang valid,

888
01:08:41,229 --> 01:08:43,529
itu juga lebih mudah untuk alasan tentang daripada seperti, oke,

889
01:08:43,529 --> 01:08:45,779
mengapa saya memiliki bendera ini di kanan int?

890
01:08:45,779 --> 01:08:49,290
Apa artinya? Oh, itu menandakan bahwa

891
01:08:49,290 --> 01:08:51,370
setiap kali aku pergi tepat, saya harus mengaturnya,

892
01:08:51,370 --> 01:08:53,819
lain jika saya pergi meninggalkan saya perlu untuk mengatur ke nol.

893
01:08:53,819 --> 01:09:04,060
Di sini, saya tidak punya alasan tentang itu, hanya saja lebih mudah untuk berpikir tentang.

894
01:09:04,060 --> 01:09:06,710
Pertanyaan?

895
01:09:06,710 --> 01:09:16,290
[Mahasiswa, dipahami] >> Ya.

896
01:09:16,290 --> 01:09:23,359
Oke, jadi dalam bit terakhir -

897
01:09:23,359 --> 01:09:28,080
Saya kira satu fungsi cepat dan mudah dapat kita lakukan adalah,

898
01:09:28,080 --> 01:09:34,910
ayo - bersama-sama, saya kira, mencoba dan menulis mengandung fungsi

899
01:09:34,910 --> 01:09:38,899
yang tidak peduli apakah itu adalah pohon pencarian biner.

900
01:09:38,899 --> 01:09:43,770
Ini berisi fungsi harus kembali benar

901
01:09:43,770 --> 01:09:58,330
jika di mana saja di pohon biner secara umum adalah nilai yang kita cari.

902
01:09:58,330 --> 01:10:02,520
Jadi mari kita pertama melakukannya secara rekursif dan kemudian kita akan melakukannya iteratif.

903
01:10:02,520 --> 01:10:07,300
Kami benar-benar bisa hanya melakukannya bersama-sama, karena ini akan menjadi benar-benar pendek.

904
01:10:07,300 --> 01:10:11,510
>> Apa yang kasus dasar saya akan?

905
01:10:11,510 --> 01:10:13,890
[Mahasiswa, dipahami]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Jadi, jika (pohon == NULL), lalu apa?

907
01:10:18,230 --> 01:10:22,740
[Mahasiswa] Kembali palsu.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Lain, baik, saya tidak perlu lagi tersebut.

909
01:10:26,160 --> 01:10:30,250
Jika itu kasus dasar saya yang lain.

910
01:10:30,250 --> 01:10:32,450
[Mahasiswa] Tree nilai? >> Ya.

911
01:10:32,450 --> 01:10:36,430
Jadi, jika (pohon-> value == nilai.

912
01:10:36,430 --> 01:10:39,920
Perhatikan kita kembali ke * node, bukan simpul ** s?

913
01:10:39,920 --> 01:10:42,990
Berisi tidak akan pernah perlu menggunakan simpul **,

914
01:10:42,990 --> 01:10:45,480
karena kita tidak memodifikasi pointer.

915
01:10:45,480 --> 01:10:50,540
Kami hanya melintasi mereka.

916
01:10:50,540 --> 01:10:53,830
Jika itu terjadi, maka kita ingin kembali benar.

917
01:10:53,830 --> 01:10:58,270
Lain kita ingin melintasi anak-anak.

918
01:10:58,270 --> 01:11:02,620
Jadi kita tidak bisa berpikir tentang apakah semuanya ke kiri kurang

919
01:11:02,620 --> 01:11:05,390
dan segala sesuatu ke kanan lebih besar.

920
01:11:05,390 --> 01:11:09,590
Jadi apa yang kondisi kita akan berada di sini - atau, apa yang akan kita lakukan?

921
01:11:09,590 --> 01:11:11,840
[Mahasiswa, dipahami] >> Ya.

922
01:11:11,840 --> 01:11:17,400
Kembali mengandung (nilai, pohon-> kiri)

923
01:11:17,400 --> 01:11:26,860
atau mengandung (nilai, pohon-> kanan). Dan itu saja.

924
01:11:26,860 --> 01:11:29,080
Dan perhatikan ada beberapa evaluasi sirkuit pendek,

925
01:11:29,080 --> 01:11:32,520
di mana jika kita kebetulan menemukan nilai di pohon kiri,

926
01:11:32,520 --> 01:11:36,820
kita tidak pernah perlu melihat pohon yang tepat.

927
01:11:36,820 --> 01:11:40,430
Itulah seluruh fungsi.

928
01:11:40,430 --> 01:11:43,690
Sekarang mari kita lakukan iteratively,

929
01:11:43,690 --> 01:11:48,060
yang akan menjadi kurang bagus.

930
01:11:48,060 --> 01:11:54,750
Kami akan mengambil start biasa simpul * skr = pohon.

931
01:11:54,750 --> 01:12:03,250
Sementara (skr = NULL!).

932
01:12:03,250 --> 01:12:08,600
Cepat akan melihat masalah.

933
01:12:08,600 --> 01:12:12,250
Jika skr - di sini, jika kita pernah keluar dari ini,

934
01:12:12,250 --> 01:12:16,020
maka kita sudah kehabisan hal untuk melihat, jadi kembali palsu.

935
01:12:16,020 --> 01:12:24,810
Jika (skr-> value == value), kembali benar.

936
01:12:24,810 --> 01:12:32,910
Jadi sekarang, kita berada di tempat -

937
01:12:32,910 --> 01:12:36,250
kita tidak tahu apakah kita ingin pergi kiri atau kanan.

938
01:12:36,250 --> 01:12:44,590
Jadi sewenang-wenang, mari kita pergi ke kiri.

939
01:12:44,590 --> 01:12:47,910
Aku sudah jelas mengalami masalah di mana saya benar-benar meninggalkan segalanya -

940
01:12:47,910 --> 01:12:50,760
Saya hanya akan memeriksa sisi kiri pohon.

941
01:12:50,760 --> 01:12:56,050
Aku tidak pernah akan memeriksa apa-apa yang merupakan anak kanan dari apa pun.

942
01:12:56,050 --> 01:13:00,910
Bagaimana cara mengatasinya?

943
01:13:00,910 --> 01:13:05,260
[Siswa] Anda harus melacak kiri dan kanan dalam tumpukan.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Ya. Jadi mari kita membuatnya

945
01:13:13,710 --> 01:13:32,360
struct daftar, simpul * n, dan kemudian simpul ** selanjutnya?

946
01:13:32,360 --> 01:13:40,240
Saya berpikir bahwa bekerja dengan baik.

947
01:13:40,240 --> 01:13:45,940
Kami ingin pergi ke kiri, atau ayo - di sini.

948
01:13:45,940 --> 01:13:54,350
= Daftar struct daftar, itu akan mulai

949
01:13:54,350 --> 01:13:58,170
keluar di daftar ini struct.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Sehingga akan menjadi linked list kami

951
01:14:04,040 --> 01:14:08,430
dari subpohon yang kita telah terlampaui.

952
01:14:08,430 --> 01:14:13,800
Kami akan melintasi tersisa sekarang,

953
01:14:13,800 --> 01:14:17,870
tapi karena mau tak mau kita harus datang kembali ke kanan,

954
01:14:17,870 --> 01:14:26,140
Kita akan menjaga sisi kanan dalam daftar struct kami.

955
01:14:26,140 --> 01:14:32,620
Kemudian kita akan memiliki new_list atau struct,

956
01:14:32,620 --> 01:14:41,080
struct daftar *, new_list = malloc (sizeof (daftar)).

957
01:14:41,080 --> 01:14:44,920
Aku akan mengabaikan kesalahan-memeriksa bahwa, tetapi Anda harus memeriksa untuk melihat null jika itu.

958
01:14:44,920 --> 01:14:50,540
New_list node itu akan menunjuk ke -

959
01:14:50,540 --> 01:14:56,890
oh, itu sebabnya aku ingin di sini. Ini akan menunjukkan daftar struct kedua.

960
01:14:56,890 --> 01:15:02,380
Itu hanya cara kerja terkait daftar.

961
01:15:02,380 --> 01:15:04,810
Ini adalah sama dengan linked list int

962
01:15:04,810 --> 01:15:06,960
kecuali kami hanya mengganti int dengan * simpul.

963
01:15:06,960 --> 01:15:11,040
Ini persis sama.

964
01:15:11,040 --> 01:15:15,100
Jadi new_list, nilai simpul new_list kami,

965
01:15:15,100 --> 01:15:19,120
akan menjadi skr-> benar.

966
01:15:19,120 --> 01:15:24,280
Nilai kami new_list-> berikutnya akan menjadi daftar asli kami,

967
01:15:24,280 --> 01:15:30,760
dan kemudian kita akan memperbarui daftar kami untuk menunjuk ke new_list.

968
01:15:30,760 --> 01:15:33,650
>> Sekarang kita perlu beberapa macam cara hal-hal menarik,

969
01:15:33,650 --> 01:15:37,020
seperti kita telah melintasi seluruh subtree kiri.

970
01:15:37,020 --> 01:15:40,480
Sekarang kita perlu untuk menarik barang-barang keluar dari itu,

971
01:15:40,480 --> 01:15:43,850
seperti skr adalah null, kami tidak ingin hanya kembali palsu.

972
01:15:43,850 --> 01:15:50,370
Kami ingin sekarang tarik luar di daftar baru kami.

973
01:15:50,370 --> 01:15:53,690
Sebuah cara mudah untuk melakukan hal ini - baik, sebenarnya, ada beberapa cara untuk melakukan hal ini.

974
01:15:53,690 --> 01:15:56,680
Ada yang punya saran?

975
01:15:56,680 --> 01:15:58,790
Dimana saya harus melakukan ini atau bagaimana saya harus melakukan ini?

976
01:15:58,790 --> 01:16:08,010
Kami hanya memiliki beberapa menit, tetapi ada saran?

977
01:16:08,010 --> 01:16:14,750
Alih-alih - salah satu cara, bukan kondisi kita yang sementara,

978
01:16:14,750 --> 01:16:17,090
apa yang kita sedang melihat tidak null,

979
01:16:17,090 --> 01:16:22,340
sebaliknya kita akan terus pergi sampai daftar kami sendiri adalah null.

980
01:16:22,340 --> 01:16:25,680
Jadi jika daftar kami akhirnya menjadi nol,

981
01:16:25,680 --> 01:16:30,680
maka kita telah kehabisan hal untuk mencari, untuk mencari lebih.

982
01:16:30,680 --> 01:16:39,860
Tapi itu berarti bahwa hal pertama dalam daftar kami hanya akan menjadi simpul pertama.

983
01:16:39,860 --> 01:16:49,730
Hal pertama akan - kita tidak perlu lagi untuk melihat bahwa.

984
01:16:49,730 --> 01:16:58,710
Jadi list-> n akan menjadi pohon kami.

985
01:16:58,710 --> 01:17:02,860
Daftar-> selanjutnya akan menjadi nol.

986
01:17:02,860 --> 01:17:07,580
Dan sekarang sementara daftar tidak nol sama.

987
01:17:07,580 --> 01:17:11,610
Cur akan menarik sesuatu dari daftar kami.

988
01:17:11,610 --> 01:17:13,500
Jadi skr akan daftar-> sama n.

989
01:17:13,500 --> 01:17:20,850
Dan kemudian daftar akan daftar-> sama n, atau daftar-> berikutnya.

990
01:17:20,850 --> 01:17:23,480
Jadi jika nilai sama dengan nilai skr.

991
01:17:23,480 --> 01:17:28,790
Sekarang kita dapat menambahkan kedua pointer yang tepat dan pointer kiri kami

992
01:17:28,790 --> 01:17:32,900
asalkan mereka tidak nol.

993
01:17:32,900 --> 01:17:36,390
Di sini, saya kira kita harus melakukan itu di tempat pertama.

994
01:17:36,390 --> 01:17:44,080
Jika (skr-> kanan = NULL!)

995
01:17:44,080 --> 01:17:56,380
maka kita akan menyisipkan simpul yang menjadi daftar kami.

996
01:17:56,380 --> 01:17:59,290
Jika (skr-> kiri), ini adalah sedikit kerja ekstra, tapi tidak apa-apa.

997
01:17:59,290 --> 01:18:02,690
Jika (skr-> kiri = NULL!),

998
01:18:02,690 --> 01:18:14,310
dan kita akan memasukkan kiri ke daftar kami terkait,

999
01:18:14,310 --> 01:18:19,700
dan yang harus itu.

1000
01:18:19,700 --> 01:18:22,670
Kami iterate - selama kita memiliki sesuatu dalam daftar kami,

1001
01:18:22,670 --> 01:18:26,640
kita memiliki node lain untuk melihat.

1002
01:18:26,640 --> 01:18:28,920
Jadi kita melihat simpul tersebut,

1003
01:18:28,920 --> 01:18:31,390
kita memajukan daftar kami ke yang berikutnya.

1004
01:18:31,390 --> 01:18:34,060
Jika node adalah nilai yang kita cari, kita dapat kembali benar.

1005
01:18:34,060 --> 01:18:37,640
Lain memasukkan kedua sub pohon kiri dan kanan kami,

1006
01:18:37,640 --> 01:18:40,510
asalkan mereka tidak null, ke dalam daftar

1007
01:18:40,510 --> 01:18:43,120
sehingga kita pasti pergi atas mereka.

1008
01:18:43,120 --> 01:18:45,160
Jadi, jika mereka tidak null,

1009
01:18:45,160 --> 01:18:47,950
jika pointer root menunjuk dua hal,

1010
01:18:47,950 --> 01:18:51,670
maka pada awalnya kami mengeluarkan sesuatu sehingga daftar kami berakhir menjadi nol.

1011
01:18:51,670 --> 01:18:56,890
Dan kemudian kami menempatkan dua hal kembali, jadi sekarang daftar kami adalah ukuran 2.

1012
01:18:56,890 --> 01:19:00,030
Kemudian kita akan loop kembali ke atas dan kami hanya akan menarik,

1013
01:19:00,030 --> 01:19:04,250
katakanlah, pointer kiri simpul akar kami.

1014
01:19:04,250 --> 01:19:07,730
Dan itu hanya akan terus terjadi, kita akan berakhir perulangan atas segala sesuatu.

1015
01:19:07,730 --> 01:19:11,280
>> Perhatikan bahwa ini secara signifikan lebih rumit

1016
01:19:11,280 --> 01:19:14,160
dalam solusi rekursif.

1017
01:19:14,160 --> 01:19:17,260
Dan saya sudah mengatakan beberapa kali

1018
01:19:17,260 --> 01:19:25,120
bahwa solusi rekursif biasanya memiliki banyak kesamaan dengan berulang solusi.

1019
01:19:25,120 --> 01:19:30,820
Berikut ini adalah apa solusi rekursif lakukan.

1020
01:19:30,820 --> 01:19:36,740
Satu-satunya perubahan adalah bahwa alih-alih implisit menggunakan stack, stack program,

1021
01:19:36,740 --> 01:19:40,840
sebagai cara Anda melacak apa yang node Anda masih perlu untuk mengunjungi,

1022
01:19:40,840 --> 01:19:45,430
sekarang Anda harus secara eksplisit menggunakan linked list.

1023
01:19:45,430 --> 01:19:49,070
Dalam kedua kasus Anda melacak apa yang simpul masih perlu untuk dikunjungi.

1024
01:19:49,070 --> 01:19:51,790
Dalam kasus rekursif itu hanya lebih mudah karena stack

1025
01:19:51,790 --> 01:19:57,100
diimplementasikan untuk Anda sebagai tumpukan program.

1026
01:19:57,100 --> 01:19:59,550
Perhatikan bahwa linked list, itu adalah stack.

1027
01:19:59,550 --> 01:20:01,580
Apapun yang kita hanya menempatkan di stack

1028
01:20:01,580 --> 01:20:09,960
segera apa yang kita akan menarik dari tumpukan untuk mengunjungi selanjutnya.

1029
01:20:09,960 --> 01:20:14,380
Kami kehabisan waktu, tetapi setiap pertanyaan?

1030
01:20:14,380 --> 01:20:23,530
[Mahasiswa, dipahami]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Ya. Jadi jika kita memiliki linked list kami,

1032
01:20:27,790 --> 01:20:30,150
saat akan menunjuk ke orang ini,

1033
01:20:30,150 --> 01:20:34,690
dan sekarang kami hanya memajukan linked list kami untuk fokus pada orang ini.

1034
01:20:34,690 --> 01:20:44,200
Kami sedang melintasi atas daftar link di baris itu.

1035
01:20:44,200 --> 01:20:51,200
Dan kemudian saya kira kita harus membebaskan linked list kami dan barang-barang

1036
01:20:51,200 --> 01:20:53,880
sekali sebelum kembali benar atau salah, kita perlu

1037
01:20:53,880 --> 01:20:57,360
iterate atas daftar kami terkait dan selalu di sini, saya kira,

1038
01:20:57,360 --> 01:21:03,900
jika kita skr benar tidak sama dengan, menambahkannya, jadi sekarang kita ingin membebaskan

1039
01:21:03,900 --> 01:21:09,600
skr karena, well, apakah kita benar-benar melupakan daftar? Ya.

1040
01:21:09,600 --> 01:21:12,880
Jadi itulah yang kami ingin lakukan di sini.

1041
01:21:12,880 --> 01:21:16,730
Dimana pointer?

1042
01:21:16,730 --> 01:21:23,320
Cur kemudian - kami ingin daftar struct * 10 sama dengan daftar berikutnya.

1043
01:21:23,320 --> 01:21:29,240
Daftar gratis, daftar = temp.

1044
01:21:29,240 --> 01:21:32,820
Dan dalam kasus di mana kita kembali benar, kita perlu iterate

1045
01:21:32,820 --> 01:21:37,050
selama sisa linked list kami membebaskan hal.

1046
01:21:37,050 --> 01:21:39,700
Yang menyenangkan tentang solusi rekursif membebaskan hal-hal

1047
01:21:39,700 --> 01:21:44,930
hanya berarti factorings muncul dari tumpukan yang akan terjadi untuk Anda.

1048
01:21:44,930 --> 01:21:50,720
Jadi kita sudah pergi dari sesuatu yang seperti 3 baris sulit berpikir tentang kode-

1049
01:21:50,720 --> 01:21:57,520
sesuatu yang secara signifikan lebih banyak sulit berpikir-tentang baris kode.

1050
01:21:57,520 --> 01:22:00,620
Ada pertanyaan lain?

1051
01:22:00,620 --> 01:22:08,760
Baiklah. Kita baik. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]