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

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

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

4
00:00:07,930 --> 00:00:10,110
Semua hak. Jadi seperti yang saya katakan dalam e-mel saya,

5
00:00:10,110 --> 00:00:14,060
ini akan menjadi bahagian binari pokok-intensif.

6
00:00:14,060 --> 00:00:16,820
Tetapi ada tidak begitu banyak soalan.

7
00:00:16,820 --> 00:00:18,920
Jadi kita pergi untuk mencuba dan menarik keluar setiap soalan

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 betul-betul pada permulaan, kita pergi melalui lukisan sampel pokok binari dan barangan.

10
00:00:31,200 --> 00:00:35,970
Jadi di sini, "Ingatlah bahawa pokok binari mempunyai nod yang sama kepada mereka senarai berkaitan,

11
00:00:35,970 --> 00:00:38,150
kecuali bukannya satu penunjuk terdapat dua: satu untuk 'anak' kiri

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

13
00:00:41,950 --> 00:00:45,630
Jadi pokok binari adalah sama seperti senarai berpaut,

14
00:00:45,630 --> 00:00:47,910
kecuali struct akan mempunyai dua petunjuk.

15
00:00:47,910 --> 00:00:51,390
Ada pokok trinary, yang akan mempunyai tiga petunjuk,

16
00:00:51,390 --> 00:00:56,540
terdapat N-ary pokok, yang hanya mempunyai penunjuk generik

17
00:00:56,540 --> 00:01:00,320
yang anda kemudian perlu malloc menjadi cukup besar untuk mempunyai

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

19
00:01:04,840 --> 00:01:08,200
Jadi pokok binari hanya berlaku untuk mempunyai beberapa berterusan dua.

20
00:01:08,200 --> 00:01:11,260
Jika anda mahu, anda boleh memberikan senarai berpaut sebagai pokok unari,

21
00:01:11,260 --> 00:01:15,360
tetapi saya tidak fikir sesiapa memanggilnya bahawa.

22
00:01:15,360 --> 00:01:18,060
"Lukiskan gambarajah kotak dan anak panah nod pokok binari

23
00:01:18,060 --> 00:01:24,110
mengandungi nombor kegemaran Nate, 7, di mana setiap penunjuk kanak-kanak adalah batal. "

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

25
00:01:27,780 --> 00:01:30,280
>> Ia akan menjadi agak mudah.

26
00:01:30,280 --> 00:01:36,150
Kami hanya akan mempunyai nod, saya akan menarik sebagai persegi.

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

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

29
00:01:41,090 --> 00:01:44,770
dan kemudian turun di sini kita akan mempunyai penunjuk kiri di sebelah kiri dan penunjuk yang betul di sebelah kanan.

30
00:01:44,770 --> 00:01:50,430
Dan ia adalah sangat banyak supaya konvensyen memanggilnya kiri dan kanan, penunjuk nama.

31
00:01:50,430 --> 00:01:52,460
Kedua-dua akan menjadi batal.

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

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

34
00:02:03,630 --> 00:02:05,700
"Dengan senarai dikaitkan, kita hanya terpaksa untuk menyimpan penunjuk

35
00:02:05,700 --> 00:02:09,639
kepada nod pertama dalam senarai untuk ingat senarai keseluruhan yang berkaitan, atau keseluruhan senarai.

36
00:02:09,639 --> 00:02:11,650
Begitu juga, dengan pokok-pokok, kita hanya perlu untuk menyimpan penunjuk

37
00:02:11,650 --> 00:02:13,420
kepada nod tunggal untuk ingat keseluruhan pokok.

38
00:02:13,420 --> 00:02:15,980
Nod Ini adalah calle 'akar pokok.

39
00:02:15,980 --> 00:02:18,320
Membina gambarajah anda dari sebelum atau menarik yang baru

40
00:02:18,320 --> 00:02:21,690
seperti yang anda mempunyai gambaran kotak dan anak panah pokok binari

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

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

43
00:02:32,760 --> 00:02:34,810
Mari kita lihat jika saya boleh ingat semua itu dalam kepala saya.

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 mempunyai penunjuk beberapa tempat, sesuatu yang kita akan panggil akar,

46
00:02:41,600 --> 00:02:45,140
dan ia menunjuk kepada lelaki ini.

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

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

49
00:02:52,870 --> 00:02:57,140
Jadi nod baru dengan 3, dan ia pada mulanya mata batal.

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

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

52
00:03:02,250 --> 00:03:06,840
Jadi kita mengubah penunjuk ini kini menunjukkan lelaki ini.

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

54
00:03:12,420 --> 00:03:14,620
yang pada mulanya hanya mengatakan batal.

55
00:03:14,620 --> 00:03:19,600
Kami akan menukar penunjuk ini, titik hingga 9,

56
00:03:19,600 --> 00:03:23,310
dan sekarang kita mahu untuk meletakkan 6 ke kanan 3.

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

58
00:03:32,170 --> 00:03:34,310
Dan lelaki itu akan menunjukkan di sana.

59
00:03:34,310 --> 00:03:38,320
Okay. Jadi itulah semua ia meminta kita lakukan.

60
00:03:38,320 --> 00:03:42,770
>> Sekarang mari kita pergi atas beberapa istilah.

61
00:03:42,770 --> 00:03:46,690
Kita sudah bercakap tentang bagaimana akar pokok itu adalah nod yang paling atas di pokok itu.

62
00:03:46,690 --> 00:03:54,720
Satu mengandungi 7. Nod di bawah pokok itu dipanggil daun.

63
00:03:54,720 --> 00:04:01,240
Sebarang nod yang hanya mempunyai batal sebagai kanak-kanak adalah daun.

64
00:04:01,240 --> 00:04:03,680
Jadi ia adalah mustahil, jika pokok binari kami adalah hanya nod tunggal,

65
00:04:03,680 --> 00:04:10,130
bahawa pokok adalah daun, dan itulah ia.

66
00:04:10,130 --> 00:04:12,060
"'Ketinggian' pokok itu adalah bilangan hop anda perlu 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 kedua, perbezaan

69
00:04:18,640 --> 00:04:21,940
antara pokok binari seimbang dan tidak seimbang,

70
00:04:21,940 --> 00:04:29,470
tapi sekarang, ketinggian keseluruhan pokok ini

71
00:04:29,470 --> 00:04:34,520
Saya akan katakan ialah 3, walaupun jika anda mengira bilangan hop

72
00:04:34,520 --> 00:04:39,710
anda perlu membuat untuk mendapatkan hingga 9, maka ia adalah benar-benar hanya ketinggian 2.

73
00:04:39,710 --> 00:04:43,340
Sekarang ini adalah pokok binari yang tidak seimbang,

74
00:04:43,340 --> 00:04:49,840
tetapi kita akan bercakap tentang seimbang apabila ia mendapat untuk menjadi relevan.

75
00:04:49,840 --> 00:04:52,040
Jadi sekarang kita boleh bercakap tentang nod dalam pokok dari segi

76
00:04:52,040 --> 00:04:54,700
relatif kepada nod lain di pokok itu.

77
00:04:54,700 --> 00:04:59,730
Jadi sekarang kita mempunyai ibu bapa, anak-anak, adik-beradik, nenek moyang, dan keturunan.

78
00:04:59,730 --> 00:05:05,650
Mereka rasa agak biasa, apa yang mereka maksudkan.

79
00:05:05,650 --> 00:05:09,610
Jika kita bertanya - ibu bapa itu.

80
00:05:09,610 --> 00:05:12,830
Jadi apakah ibu bapa 3?

81
00:05:12,830 --> 00:05:16,090
[Pelajar] 7. >> Yeah. Ibu bapa hanya akan menjadi apa yang menunjukkan kepada anda.

82
00:05:16,090 --> 00:05:20,510
Kemudian apakah kanak-kanak dari 7?

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

84
00:05:23,860 --> 00:05:26,460
Perhatikan bahawa "kanak-kanak" bermaksud kanak-kanak,

85
00:05:26,460 --> 00:05:31,010
jadi 6 tidak akan terpakai, kerana ia adalah seperti cucu.

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

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

88
00:05:37,500 --> 00:05:42,330
Keturunan nod akar akan menjadi segala-galanya di pokok itu,

89
00:05:42,330 --> 00:05:47,950
kecuali mungkin nod akar itu sendiri, jika anda tidak mahu menganggap bahawa keturunan.

90
00:05:47,950 --> 00:05:50,750
Dan akhirnya, nenek moyang, jadi ia adalah arah bertentangan.

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

92
00:05:55,740 --> 00:05:58,920
[Pelajar] 3 dan 7. >> Yeah. 9 tidak dimasukkan.

93
00:05:58,920 --> 00:06:02,520
Ia hanya belakang 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 bahawa pokok binari 'mengarahkan' jika untuk setiap nod dalam pokok itu,

96
00:06:16,300 --> 00:06:19,530
semua keturunan di sebelah kiri mempunyai nilai-nilai yang lebih rendah

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

98
00:06:22,890 --> 00:06:27,060
Sebagai contoh, pokok atas diperintahkan tetapi ia tidak hanya susunan mungkin diperintahkan. "

99
00:06:27,060 --> 00:06:30,180
Sebelum kita dapat itu,

100
00:06:30,180 --> 00:06:36,420
diperintahkan pokok binari juga dikenali sebagai pokok carian binari.

101
00:06:36,420 --> 00:06:38,660
Di sini kita berlaku untuk memanggil ia pokok binari diperintahkan,

102
00:06:38,660 --> 00:06:41,850
tetapi saya tidak pernah mendengar ia dipanggil pokok binari diperintahkan sebelum,

103
00:06:41,850 --> 00:06:46,650
dan pada kuiz kita lebih cenderung untuk meletakkan pokok carian binari.

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

105
00:06:49,250 --> 00:06:54,580
dan ia adalah penting anda mengenali perbezaan di antara pokok binari dan pokok carian binari.

106
00:06:54,580 --> 00:06:58,830
Satu pokok binari hanya pokok yang mata kepada dua perkara.

107
00:06:58,830 --> 00:07:02,120
Setiap nod mata kepada dua perkara.

108
00:07:02,120 --> 00:07:06,310
Tidak ada hujah tentang nilai-nilai yang ia menjurus kepada.

109
00:07:06,310 --> 00:07:11,370
Jadi seperti di sini, kerana ia adalah pokok carian binari,

110
00:07:11,370 --> 00:07:14,030
kita tahu bahawa jika kita pergi kiri 7,

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

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

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

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

115
00:07:26,040 --> 00:07:29,020
Jika kita pergi ke kanan 7, segala-galanya telah menjadi lebih daripada 7,

116
00:07:29,020 --> 00:07:33,220
begitu 9 adalah hak 7, jadi kami baik.

117
00:07:33,220 --> 00:07:36,150
Ini bukan kes untuk pokok binari,

118
00:07:36,150 --> 00:07:40,020
untuk pokok binari tetap kita hanya boleh mempunyai 3 di atas, 7 ke kiri,

119
00:07:40,020 --> 00:07:47,630
9 ke kiri 7; tiada pesanan nilai jua.

120
00:07:47,630 --> 00:07:56,140
Sekarang, kita akan sebenarnya tidak melakukan ini kerana ia adalah membosankan dan tidak perlu,

121
00:07:56,140 --> 00:07:59,400
tetapi "cuba untuk menarik seberapa ramai diperintahkan pokok seperti yang anda boleh berfikir

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

123
00:08:01,900 --> 00:08:06,800
Berapa banyak perkiraan yang berbeza berada di sana? Apakah ketinggian setiap satu? "

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

125
00:08:10,480 --> 00:08:16,530
ini adalah dengan cara tiada perwakilan unik pokok binari yang mengandungi nilai-nilai ini.

126
00:08:16,530 --> 00:08:22,760
Apa yang kami perlukan adalah beberapa pokok binari yang mengandungi 7, 3, 6, dan 9.

127
00:08:22,760 --> 00:08:25,960
Satu lagi salah yang sah yang mungkin akan menjadi akar ialah 3,

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

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

130
00:08:32,730 --> 00:08:36,169
Itulah pokok carian binari yang sah.

131
00:08:36,169 --> 00:08:39,570
Ia tidak sangat membantu, kerana ia adalah sama seperti senarai berkaitan

132
00:08:39,570 --> 00:08:43,750
dan semua ini petunjuk hanya batal.

133
00:08:43,750 --> 00:08:48,900
Tetapi ia adalah pokok yang sah. Yeah?

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

135
00:08:51,310 --> 00:08:56,700
Atau adakah ini? >> Ini Saya bermaksud untuk pergi dengan cara yang lain.

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

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Tangkapan yang baik.

138
00:09:07,770 --> 00:09:11,730
Ia masih mempunyai untuk mentaati apa carian binari pokok yang sepatutnya dilakukan.

139
00:09:11,730 --> 00:09:15,650
Jadi segala-galanya ke kiri mempunyai menjadi kurang daripada nod yang diberikan.

140
00:09:15,650 --> 00:09:23,180
Kita hanya boleh bergerak, berkata, ini 6 dan meletakkan ia di sini.

141
00:09:23,180 --> 00:09:26,880
Tidak, kita tidak boleh. Kenapa saya terus berbuat demikian?

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

143
00:09:35,350 --> 00:09:39,290
Ini adalah masih pokok carian binari yang sah.

144
00:09:39,290 --> 00:09:49,260
Apakah salah jika saya - mari kita lihat jika saya boleh tampil dengan perkiraan.

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

146
00:09:52,280 --> 00:10:08,920
Saya rasa saya telah diberi petunjuk bahawa ada sesuatu yang salah dengan itu.

147
00:10:08,920 --> 00:10:14,430
Kenapa saya terus berbuat demikian?

148
00:10:14,430 --> 00:10:18,510
Okay. Ini kelihatan munasabah.

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

150
00:10:22,590 --> 00:10:24,960
Jadi kita mempunyai 3, perkara ke kanan sebanyak 3 ialah 6.

151
00:10:24,960 --> 00:10:27,750
Dan jika anda melihat pada 6, perkara yang hak daripada 6 9.

152
00:10:27,750 --> 00:10:30,910
Jadi mengapa ini bukan pokok carian binari yang sah?

153
00:10:30,910 --> 00:10:36,330
[Pelajar] 9 adalah masih kiri 7. >> Yeah.

154
00:10:36,330 --> 00:10:43,710
Ia mesti benar bahawa semua nilai yang anda mungkin boleh mencapai dengan pergi ke kiri 7 adalah kurang daripada 7.

155
00:10:43,710 --> 00:10:49,120
Jika kita pergi kiri 7, kita dapat 3 dan kita masih boleh mendapatkan hingga 6,

156
00:10:49,120 --> 00:10:52,520
kita masih boleh mendapatkan hingga 9, tetapi dengan mempunyai pergi kurang daripada 7,

157
00:10:52,520 --> 00:10:55,070
kita tidak harus mampu untuk mendapatkan nombor yang lebih besar daripada 7.

158
00:10:55,070 --> 00:10:59,830
Jadi ini tidak adalah pokok carian binari yang sah.

159
00:10:59,830 --> 00:11:02,330
>> Abang saya sebenarnya mempunyai soalan temuduga

160
00:11:02,330 --> 00:11:07,760
yang pada asasnya ini, hanya kod sehingga sesuatu untuk mengesahkan

161
00:11:07,760 --> 00:11:10,500
sama ada pokok adalah pokok carian binari,

162
00:11:10,500 --> 00:11:13,580
dan sebagainya perkara pertama yang beliau lakukan adalah hanya menyemak untuk melihat

163
00:11:13,580 --> 00:11:17,020
jika kiri dan kanan adalah betul, dan kemudian melelar bawah sana.

164
00:11:17,020 --> 00:11:19,700
Tetapi anda tidak boleh hanya berbuat demikian, anda perlu menjejaki

165
00:11:19,700 --> 00:11:22,550
hakikat bahawa sekarang saya telah pergi kiri 7,

166
00:11:22,550 --> 00:11:26,340
segala-galanya di pohon mestilah kurang daripada 7.

167
00:11:26,340 --> 00:11:28,430
Algoritma yang betul perlu untuk menjejaki

168
00:11:28,430 --> 00:11:35,970
batas bahawa nilai mungkin boleh jatuh masuk

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

170
00:11:38,360 --> 00:11:41,630
Terdapat hubungan berulangnya bagus,

171
00:11:41,630 --> 00:11:44,810
walaupun kita tidak mendapat kepada mereka, atau kita tidak akan sampai kepada mereka,

172
00:11:44,810 --> 00:11:47,030
menentukan berapa ramai sebenarnya.

173
00:11:47,030 --> 00:11:53,180
Jadi, terdapat 14 daripada mereka.

174
00:11:53,180 --> 00:11:56,020
Idea bagaimana anda akan melakukan matematik adalah seperti,

175
00:11:56,020 --> 00:11:59,770
anda boleh memilih mana-mana satu untuk menjadi nod akar,

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

177
00:12:03,160 --> 00:12:08,150
maka terdapat, katakan, beberapa nombor yang boleh pergi menjadi nod kiri saya,

178
00:12:08,150 --> 00:12:10,440
dan terdapat beberapa nombor yang boleh menjadi nod kanan saya,

179
00:12:10,440 --> 00:12:15,090
tetapi jika saya telah n jumlah nombor, maka jumlah yang boleh pergi ke kiri

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

181
00:12:18,820 --> 00:12:26,130
Jadi nombor yang tinggal, mereka perlu mampu untuk pergi sama ada ke kiri atau kanan.

182
00:12:26,130 --> 00:12:31,580
Ia seolah-olah sukar bahawa, jika saya meletakkan 3 pertama maka segala-galanya telah pergi ke kiri,

183
00:12:31,580 --> 00:12:35,080
tetapi jika saya meletakkan 7, maka beberapa perkara yang boleh pergi kiri dan beberapa perkara yang boleh pergi ke kanan.

184
00:12:35,080 --> 00:12:39,570
Dan oleh '3 'pertama saya bermakna segala-galanya boleh pergi ke kanan.

185
00:12:39,570 --> 00:12:42,350
Ia benar-benar, anda hanya perlu untuk berfikir tentang hal seperti,

186
00:12:42,350 --> 00:12:47,980
berapa banyak perkara yang boleh pergi pada tahap seterusnya pokok itu.

187
00:12:47,980 --> 00:12:50,420
Dan ia datang untuk menjadi 14; atau anda boleh menarik mereka semua,

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

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

190
00:13:01,120 --> 00:13:03,510
"Tertib pokok binari adalah sejuk kerana kita boleh mencari melalui mereka

191
00:13:03,510 --> 00:13:06,910
dalam cara yang sangat serupa untuk mencari lebih pelbagai disusun.

192
00:13:06,910 --> 00:13:10,120
Untuk berbuat demikian, kita bermula di akar dan bekerja cara kami ke bawah pokok

193
00:13:10,120 --> 00:13:13,440
ke arah daun, memeriksa nilai setiap nod terhadap nilai-nilai kita sedang mencari.

194
00:13:13,440 --> 00:13:15,810
Jika nilai nod semasa adalah kurang daripada nilai kita sedang mencari,

195
00:13:15,810 --> 00:13:18,050
anda pergi bersebelahan untuk kanak-kanak kanan nod.

196
00:13:18,050 --> 00:13:20,030
Jika tidak, anda pergi kepada anak kiri nod.

197
00:13:20,030 --> 00:13:22,800
Pada satu ketika, anda akan mencari nilai yang anda sedang mencari, atau anda akan menghadapi satu null,

198
00:13:22,800 --> 00:13:28,520
menunjukkan nilai bukan di pokok itu. "

199
00:13:28,520 --> 00:13:32,450
Saya mempunyai untuk melukis pokok yang kita lalui sebelum ini, yang akan mengambil kedua.

200
00:13:32,450 --> 00:13:38,280
Tetapi kita mahu melihat sama ada 6, 10, dan 1 di pokok itu.

201
00:13:38,280 --> 00:13:49,180
Jadi apa yang ia adalah, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
Nombor yang anda mahu melihat, kita mahu mencari 6.

203
00:13:52,730 --> 00:13:55,440
Bagaimanakah ini berfungsi algoritma?

204
00:13:55,440 --> 00:14:03,040
Nah, kita juga mempunyai beberapa penunjuk akar ke pokok kita.

205
00:14:03,040 --> 00:14:12,460
Dan kita akan pergi ke akar dan berkata, adalah nilai ini bersamaan dengan nilai kita sedang mencari?

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

207
00:14:15,000 --> 00:14:20,140
Jadi kita terus pergi, dan kini kita katakan, okay, jadi 6 adalah kurang daripada 7.

208
00:14:20,140 --> 00:14:23,940
Adakah ini bermakna kita mahu pergi ke kiri, atau adakah kita mahu pergi ke kanan?

209
00:14:23,940 --> 00:14:27,340
[Pelajar] Kiri. >> Yeah.

210
00:14:27,340 --> 00:14:33,340
Ia adalah jauh lebih mudah, semua yang anda perlu lakukan adalah menarik salah satu nod mungkin pokok itu

211
00:14:33,340 --> 00:14:37,760
dan kemudian anda Don 't - dan bukannya cuba untuk berfikir dalam kepala anda,

212
00:14:37,760 --> 00:14:40,020
okay, jika ia kurang, saya pergi ke kiri atau pergi kanan,

213
00:14:40,020 --> 00:14:43,030
hanya melihat gambar ini, ia adalah sangat jelas bahawa saya perlu pergi ke kiri

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

215
00:14:47,700 --> 00:14:52,600
Jadi anda pergi ke kiri, sekarang saya pada 3.

216
00:14:52,600 --> 00:14:57,770
Saya mahu - 3 adalah kurang daripada nilai Saya mencari yang adalah 6.

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

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

219
00:15:07,380 --> 00:15:15,760
Nilai seterusnya saya akan mencari adalah 10.

220
00:15:15,760 --> 00:15:23,230
Okay. Jadi 10, kini, akan - memotong bahawa - akan mengikuti akar.

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

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

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

224
00:15:34,520 --> 00:15:42,100
Saya datang ke sini, tetapi di sini sekarang saya di batal.

225
00:15:42,100 --> 00:15:44,170
Apa yang perlu saya lakukan jika saya memukul batal?

226
00:15:44,170 --> 00:15:47,440
[Pelajar] Return palsu? >> Yeah. Saya tidak menjumpai 10.

227
00:15:47,440 --> 00:15:49,800
1 adalah akan menjadi satu kes yang hampir sama,

228
00:15:49,800 --> 00:15:51,950
kecuali ia hanya akan dijentik; bukan mencari

229
00:15:51,950 --> 00:15:56,540
ke sebelah kanan, saya akan melihat ke bawah sebelah kiri.

230
00:15:56,540 --> 00:16:00,430
>> Sekarang saya fikir kita sebenarnya mendapatkan kod.

231
00:16:00,430 --> 00:16:04,070
Berikut adalah di mana - membuka perkakas CS50 dan mengemudi jalan anda di sana,

232
00:16:04,070 --> 00:16:07,010
tetapi anda boleh juga hanya melakukannya dalam ruang.

233
00:16:07,010 --> 00:16:09,170
Ia mungkin sesuai untuk melakukannya di dalam ruang,

234
00:16:09,170 --> 00:16:13,760
kerana kita boleh bekerja di dalam ruang.

235
00:16:13,760 --> 00:16:19,170
"Mula-mula kita akan memerlukan jenis definisi baru bagi nod pokok binari yang mengandungi nilai int.

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

237
00:16:21,400 --> 00:16:24,510
mencipta definisi jenis baru bagi nod dalam pokok binari.

238
00:16:24,510 --> 00:16:27,930
Jika anda tersekat. . . "Blah, blah, blah. Okay.

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

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

241
00:16:41,630 --> 00:16:44,270
Jadi apakah bidang kita akan mahu dalam nod kami?

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

243
00:16:46,520 --> 00:16:49,700
>> Nilai Int, dua petunjuk? Bagaimana saya menulis petunjuk?

244
00:16:49,700 --> 00:16:58,440
[Pelajar] struct. >> Saya perlu mengezum masuk Yeah, jadi nod struct * meninggalkan,

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

246
00:17:01,320 --> 00:17:03,460
Dan ingat perbincangan dari masa lalu,

247
00:17:03,460 --> 00:17:15,290
bahawa 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-galanya ada dalam usaha untuk menentukan struct rekursi.

250
00:17:25,000 --> 00:17:27,970
Okay, supaya apa yang pokok kami akan kelihatan seperti.

251
00:17:27,970 --> 00:17:37,670
Jika kita lakukan pokok trinary, maka nod mungkin kelihatan seperti b1, b2, struct nod * b3,

252
00:17:37,670 --> 00:17:43,470
mana b adalah cawangan - sebenarnya, saya lebih mendengar ia kiri, tengah, kanan, tetapi apa sahaja.

253
00:17:43,470 --> 00:17:55,610
Kami hanya mengambil berat tentang binari, jadi kanan, kiri.

254
00:17:55,610 --> 00:17:59,110
"Sekarang mengisytiharkan * nod pembolehubah global untuk akar pokok itu."

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

256
00:18:01,510 --> 00:18:08,950
Dalam usaha untuk membuat perkara yang lebih sukar dan lebih umum,

257
00:18:08,950 --> 00:18:11,570
kita tidak akan mempunyai pembolehubah nod global.

258
00:18:11,570 --> 00:18:16,710
Sebaliknya, dalam utama yang kita akan mengisytiharkan semua perkara nod kami,

259
00:18:16,710 --> 00:18:20,500
dan itu bererti bahawa di bawah, apabila kita mula menjalankan

260
00:18:20,500 --> 00:18:23,130
fungsi Mengandungi dan fungsi kami memasukkan kami,

261
00:18:23,130 --> 00:18:27,410
bukannya Mengandungi kita berfungsi hanya menggunakan pembolehubah nod global,

262
00:18:27,410 --> 00:18:34,280
kita akan mempunyai ia mengambil sebagai hujah pokok yang kita mahu ia untuk memproses.

263
00:18:34,280 --> 00:18:36,650
Mempunyai pembolehubah global sepatutnya untuk membuat perkara yang mudah.

264
00:18:36,650 --> 00:18:42,310
Kami pergi untuk membuat perkara yang sukar.

265
00:18:42,310 --> 00:18:51,210
Sekarang mengambil minit atau lebih untuk hanya melakukan perkara seperti ini,

266
00:18:51,210 --> 00:18:57,690
di mana di dalam utama anda mahu untuk mewujudkan pokok ini, dan itulah semua yang anda mahu lakukan.

267
00:18:57,690 --> 00:19:04,530
Cuba dan membina pokok ini dalam fungsi utama anda.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Jadi anda tidak perlu telah dibina pokok keseluruhan cara lagi.

269
00:19:47,610 --> 00:19:49,840
Tetapi sesiapa yang mempunyai sesuatu yang saya boleh tarik sehingga

270
00:19:49,840 --> 00:20:03,130
untuk menunjukkan bagaimana seseorang mungkin mula membina pokok tersebut?

271
00:20:03,130 --> 00:20:08,080
[Pelajar] terhantuk Seseorang, cuba untuk keluar.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Sesiapa selesa dengan pembinaan pokok mereka?

273
00:20:13,100 --> 00:20:15,520
[Pelajar] Pasti. Ia tidak dilakukan. >> Ia adalah denda. Kita hanya boleh selesai -

274
00:20:15,520 --> 00:20:26,860
oh, anda boleh menyimpan? Hore.

275
00:20:26,860 --> 00:20:32,020
Jadi di sini kita mempunyai - oh, saya sedikit memotong.

276
00:20:32,020 --> 00:20:34,770
Saya dizum dalam?

277
00:20:34,770 --> 00:20:37,730
Mengezum masuk, tatal keluar. >> Saya mempunyai satu soalan. >> Yeah?

278
00:20:37,730 --> 00:20:44,410
[Pelajar] Apabila anda menentukan struct, adalah perkara-perkara seperti dimulakan untuk apa-apa?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Okay. Jadi, anda akan perlu untuk memulakan -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Apabila anda menentukan, atau apabila anda mengisytiharkan struct,

281
00:20:50,450 --> 00:20:55,600
ia tidak dimulakan secara lalai, ia hanya suka jika anda mengaku int.

282
00:20:55,600 --> 00:20:59,020
Ia adalah perkara yang sama. Ia seperti setiap bidang individu

283
00:20:59,020 --> 00:21:04,460
boleh mempunyai nilai sampah di dalamnya. >> Dan ia mungkin untuk menentukan atau untuk mengisytiharkan struct

284
00:21:04,460 --> 00:21:07,740
dalam cara yang ia tidak memulakan mereka?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ya. Jadi, jalan pintas pengawalan sintaks

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

287
00:21:18,660 --> 00:21:22,200
Ada dua cara yang boleh kita lakukan ini. Saya fikir kita perlu menyusun

288
00:21:22,200 --> 00:21:25,840
untuk membuat dilafaz pasti juga tidak ini.

289
00:21:25,840 --> 00:21:28,510
Perintah hujah yang datang dalam struct,

290
00:21:28,510 --> 00:21:32,170
anda meletakkan sebagai perintah hujah di dalam ini pendakap kerinting.

291
00:21:32,170 --> 00:21:35,690
Jadi jika anda mahu untuk memulakan hingga 9 dan meninggalkan batal dan kemudian kanan menjadi batal,

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

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

294
00:21:47,890 --> 00:21:50,300
dan ia difikirkan Saya mahu sebuah blok baru,

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

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

297
00:22:04,190 --> 00:22:09,140
Anda dengan jelas boleh mengatakan, saya lupa sintaks yang tepat.

298
00:22:09,140 --> 00:22:13,110
Jadi jelas anda boleh menangani mereka dengan nama, dan berkata,

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

300
00:22:21,570 --> 00:22:24,540
Saya meneka ini keperluan untuk menjadi koma.

301
00:22:24,540 --> 00:22:29,110
Kanan = NULL, jadi cara ini anda tidak

302
00:22:29,110 --> 00:22:33,780
sebenarnya perlu tahu perintah struct itu,

303
00:22:33,780 --> 00:22:36,650
dan apabila anda membaca ini, ia adalah lebih jelas

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

305
00:22:41,920 --> 00:22:44,080
>> Ini berlaku untuk menjadi salah satu perkara yang -

306
00:22:44,080 --> 00:22:49,100
begitu, bagi sebahagian besar, C + + adalah superset C.

307
00:22:49,100 --> 00:22:54,160
Anda boleh mengambil kod C, bergerak ia lebih kepada C + +, dan ia perlu menyusun.

308
00:22:54,160 --> 00:22:59,570
Ini adalah salah satu daripada perkara-perkara yang C + + tidak menyokong, jadi orang cenderung untuk tidak melakukannya.

309
00:22:59,570 --> 00:23:01,850
Saya tidak tahu jika itulah sebab hanya orang cenderung untuk tidak melakukannya,

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

311
00:23:10,540 --> 00:23:14,000
Satu lagi contoh sesuatu yang tidak berfungsi dengan C + + adalah

312
00:23:14,000 --> 00:23:16,940
bagaimana malloc mengembalikan "* tidak sah," teknikal,

313
00:23:16,940 --> 00:23:20,200
tetapi anda hanya boleh mengatakan char * x = malloc apa sahaja,

314
00:23:20,200 --> 00:23:22,840
dan ia secara automatik akan dibuang * char.

315
00:23:22,840 --> 00:23:25,450
Itu cast automatik tidak berlaku dalam C + +.

316
00:23:25,450 --> 00:23:28,150
Itu tidak akan menyusun, dan jelas anda akan perlu untuk mengatakan

317
00:23:28,150 --> 00:23:34,510
* char, malloc, apa sahaja, untuk membuang * char.

318
00:23:34,510 --> 00:23:37,270
Tidak ada banyak perkara bahawa C dan C + + tidak bersetuju,

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 walaupun kita tidak pergi dengan sintaks itu,

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

323
00:23:49,470 --> 00:23:52,170
[Pelajar] Saya tidak perlu dereference ia? >> Yeah.

324
00:23:52,170 --> 00:23:55,110
Ingatlah bahawa anak panah mempunyai dereference tersirat,

325
00:23:55,110 --> 00:23:58,230
dan sebagainya apabila kita hanya berurusan dengan struct,

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

327
00:24:04,300 --> 00:24:07,200
Dan masa sahaja kita menggunakan anak panah adalah apabila kita mahu lakukan -

328
00:24:07,200 --> 00:24:13,450
baik, arrow adalah bersamaan dengan -

329
00:24:13,450 --> 00:24:17,020
itulah apa yang ia akan bermakna jika saya menggunakan anak panah.

330
00:24:17,020 --> 00:24:24,600
Semua cara arrow, dereference ini, kini saya di struct, dan saya boleh mendapatkan bidang.

331
00:24:24,600 --> 00:24:28,040
Sama ada mendapatkan bidang secara langsung atau dereference dan mendapatkan bidang -

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

333
00:24:30,380 --> 00:24:33,910
Tetapi di sini saya berurusan dengan hanya struct, bukan penunjuk kepada struct satu,

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

335
00:24:38,780 --> 00:24:47,510
Tetapi ini jenis perkara yang boleh kita lakukan untuk semua nod.

336
00:24:47,510 --> 00:24:55,790
Oh Tuhan saya.

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 boleh menubuhkan cawangan di pokok kita, kita boleh mempunyai 7 -

339
00:25:16,470 --> 00:25:21,650
kita boleh, kiri harus menunjukkan kepada 3.

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

341
00:25:25,130 --> 00:25:29,320
[Pelajar, difahami] >> Yeah. Alamat node3,

342
00:25:29,320 --> 00:25:34,170
dan jika anda tidak mempunyai alamat, maka ia hanya tidak akan mengumpulkannya.

343
00:25:34,170 --> 00:25:38,190
Tetapi ingat bahawa ini adalah petunjuk untuk nod seterusnya.

344
00:25:38,190 --> 00:25:44,930
Hak hendaklah menuding ke 9,

345
00:25:44,930 --> 00:25:53,330
dan 3 perlu menunjukkan di sebelah kanan hingga 6.

346
00:25:53,330 --> 00:25:58,480
Saya rasa ini adalah menetapkan semua. Sebarang komen atau soalan?

347
00:25:58,480 --> 00:26:02,060
[Pelajar, difahami] Akar akan menjadi 7.

348
00:26:02,060 --> 00:26:08,210
Kita hanya boleh mengatakan nod * 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 memasukkan,

351
00:26:20,730 --> 00:26:25,490
jadi kita akan mahu untuk menulis fungsi untuk memasukkan ke dalam pokok ini binari

352
00:26:25,490 --> 00:26:34,230
dan masukkan tidak dapat dielakkan akan memanggil malloc untuk mewujudkan nod baru untuk pokok ini.

353
00:26:34,230 --> 00:26:36,590
Jadi perkara-perkara yang akan mendapat berantakan dengan hakikat bahawa sesetengah nod

354
00:26:36,590 --> 00:26:38,590
kini pada timbunan

355
00:26:38,590 --> 00:26:43,680
dan nodus lain akan berakhir pada timbunan apabila kita memasukkan mereka.

356
00:26:43,680 --> 00:26:47,640
Ini adalah betul-betul sah, tetapi sebab sahaja

357
00:26:47,640 --> 00:26:49,600
kami dapat melakukan ini pada timbunan

358
00:26:49,600 --> 00:26:51,840
adalah kerana ia adalah seperti contoh yang tersusun yang kita tahu

359
00:26:51,840 --> 00:26:56,360
pokok itu sepatutnya dibina sebagai 7, 3, 6, 9.

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

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

362
00:27:06,160 --> 00:27:08,570
Sekarang ia adalah sempurna yang munasabah untuk meletakkan pada timbunan,

363
00:27:08,570 --> 00:27:14,750
tetapi mari kita menukar ini kepada pelaksanaan malloc.

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

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

366
00:27:24,240 --> 00:27:28,040
Dan kini kami akan perlu untuk melakukan pemeriksaan kami.

367
00:27:28,040 --> 00:27:34,010
jika (node9 == NULL) - Saya tidak mahu bahawa -

368
00:27:34,010 --> 00:27:40,950
return 1, dan kemudian kita boleh lakukan node9-> kerana sekarang ia adalah penunjuk,

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

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

371
00:27:48,930 --> 00:27:51,410
dan kita akan perlu untuk berbuat demikian bagi setiap nod-nod.

372
00:27:51,410 --> 00:27:57,490
Jadi sebaliknya, mari kita meletakkan ia di dalam fungsi berasingan.

373
00:27:57,490 --> 00:28:00,620
Mari kita memanggilnya nod * build_node,

374
00:28:00,620 --> 00:28:09,050
dan ini adalah agak serupa dengan API kami sediakan untuk pengekodan Huffman.

375
00:28:09,050 --> 00:28:12,730
Kami memberi anda fungsi pengasal untuk pokok

376
00:28:12,730 --> 00:28:20,520
deconstructor "fungsi" bagi mereka pokok-pokok dan sama untuk hutan.

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

378
00:28:22,570 --> 00:28:25,170
hanya membina nod untuk kita.

379
00:28:25,170 --> 00:28:29,320
Dan ia akan kelihatan cukup banyak sama seperti ini.

380
00:28:29,320 --> 00:28:32,230
Dan saya juga akan menjadi malas dan tidak menukar nama pembolehubah,

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

382
00:28:34,380 --> 00:28:38,610
Oh, saya rasa nilai node9 tidak perlu telah 6.

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

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

385
00:28:49,550 --> 00:28:52,690
Semua orang bersetuju mengenai fungsi yang membina nod?

386
00:28:52,690 --> 00:28:59,780
Jadi sekarang kita hanya boleh memanggil bahawa untuk membina mana-mana nod dengan nilai yang diberikan dan penunjuk nol.

387
00:28:59,780 --> 00:29:09,750
Sekarang kita boleh memanggil bahawa, kita boleh melakukan nod * node9 = build_node (9).

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

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 mahu menubuhkan petunjuk yang sama,

391
00:29:39,330 --> 00:29:42,470
kecuali kini segala-galanya sudah di segi petunjuk

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

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

394
00:29:56,300 --> 00:30:03,850
Terdapat ralat semakan bahawa saya tidak melakukan.

395
00:30:03,850 --> 00:30:06,800
Apakah membina kembali nod?

396
00:30:06,800 --> 00:30:11,660
[Pelajar, difahami] >> Yeah. Jika malloc gagal, ia akan kembali batal.

397
00:30:11,660 --> 00:30:16,460
Jadi, saya akan malas meletakkan ia ke bawah di sini bukannya melakukan suatu keadaan bagi setiap.

398
00:30:16,460 --> 00:30:22,320
Jika (node9 == NULL, atau - walaupun mudah,

399
00:30:22,320 --> 00:30:28,020
ini adalah bersamaan 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
[Pelajar] Apakah palsu sama untuk menyeimbangkan serta?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Mana-mana nilai sifar adalah palsu.

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

405
00:30:53,920 --> 00:30:56,780
Sifar adalah nilai sifar. Palsu adalah nilai sifar.

406
00:30:56,780 --> 00:31:02,130
Mana-mana - cukup banyak hanya 2 nilai sifar adalah batal dan sifar,

407
00:31:02,130 --> 00:31:07,900
palsu adalah hanya hash ditakrifkan sebagai sifar.

408
00:31:07,900 --> 00:31:13,030
Itu juga terpakai jika kita mengisytiharkan pembolehubah global.

409
00:31:13,030 --> 00:31:17,890
Jika kita tidak mempunyai nod akar * di sini,

410
00:31:17,890 --> 00:31:24,150
kemudian - Perkara yang baik tentang pembolehubah global adalah bahawa mereka sentiasa mempunyai nilai awal.

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

412
00:31:27,500 --> 00:31:34,870
jika kita mempunyai, seperti, * nod atau x nod.

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

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

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

416
00:31:44,980 --> 00:31:47,450
Akar Jadi nod atau x nod.

417
00:31:47,450 --> 00:31:53,410
Secara lalai, segala-galanya yang global, jika tidak jelas dimulakan kepada nilai tertentu,

418
00:31:53,410 --> 00:31:57,390
mempunyai nilai sifar sebagai nilai.

419
00:31:57,390 --> 00:32:01,150
Jadi di sini, nod akar *, kita tidak jelas memulakan untuk apa-apa,

420
00:32:01,150 --> 00:32:06,350
jadi nilai lalai akan batal, yang merupakan nilai sifar petunjuk.

421
00:32:06,350 --> 00:32:11,870
Nilai lalai x akan bermakna bahawa x.value adalah sifar,

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

423
00:32:14,260 --> 00:32:21,070
Jadi kerana ia adalah struct, semua bidang struct yang akan menjadi nilai-nilai sifar.

424
00:32:21,070 --> 00:32:24,410
Kita tidak perlu untuk menggunakan bahawa sini, walaupun.

425
00:32:24,410 --> 00:32:27,320
[Pelajar] structs adalah berbeza daripada pembolehubah lain, dan pembolehubah lain

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

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

428
00:32:36,220 --> 00:32:40,070
Jika ia adalah pada skop global, ia mempunyai nilai awal. >> Okay.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Sama ada nilai awal anda memberikannya atau sifar.

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

431
00:32:53,260 --> 00:32:58,390
>> Okay. Jadi bahagian seterusnya soalan bertanya,

432
00:32:58,390 --> 00:33:01,260
"Sekarang kita mahu menulis fungsi yang dipanggil mengandungi

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

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

435
00:33:08,340 --> 00:33:15,110
Prototaip kami akan kelihatan seperti

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

437
00:33:22,380 --> 00:33:24,490
Dan kemudian kami juga akan lulus ia pokok

438
00:33:24,490 --> 00:33:28,870
bahawa ia harus memeriksa untuk melihat jika ia mempunyai nilai yang.

439
00:33:28,870 --> 00:33:38,290
Jadi nod * pokok). Okay.

440
00:33:38,290 --> 00:33:44,440
Dan kemudian kita boleh memanggil ia dengan sesuatu seperti,

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

442
00:33:46,090 --> 00:33:51,040
Mengandungi 6, akar kita.

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 mengandungi 5 akar harus kembali palsu.

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 boleh melakukannya sama ada iterative atau rekursif.

447
00:34:06,780 --> 00:34:09,739
Perkara yang baik tentang cara kita telah menetapkan perkara ini adalah bahawa

448
00:34:09,739 --> 00:34:12,300
ia meminjamkan dirinya kepada penyelesaian rekursi kami lebih mudah

449
00:34:12,300 --> 00:34:14,719
daripada cara pembolehubah global.

450
00:34:14,719 --> 00:34:19,750
Kerana jika kita hanya mempunyai mengandungi nilai int, maka kita mempunyai ada cara recursing turun subtrees.

451
00:34:19,750 --> 00:34:24,130
Kami akan perlu untuk mempunyai fungsi pembantu berasingan yang recurses menurunkan subtrees untuk kita.

452
00:34:24,130 --> 00:34:29,610
Tetapi oleh kerana kita telah mengubah ia untuk mengambil pokok itu sebagai hujah,

453
00:34:29,610 --> 00:34:32,760
yang ia sepatutnya sentiasa berada di tempat pertama,

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

455
00:34:35,710 --> 00:34:38,960
Jadi lelaran atau rekursi, kita akan pergi ke atas kedua-duanya,

456
00:34:38,960 --> 00:34:46,139
tetapi kita akan melihat bahawa hujung rekursi sehingga menjadi agak mudah.

457
00:34:59,140 --> 00:35:02,480
Okay. Adakah sesiapa yang mempunyai sesuatu yang kita boleh bekerja dengan?

458
00:35:02,480 --> 00:35:12,000
>> [Pelajar] Saya telah mendapat lelaran penyelesaian. >> Baiklah, lelaran.

459
00:35:12,000 --> 00:35:16,030
Okay, ini kelihatan baik.

460
00:35:16,030 --> 00:35:18,920
Jadi, mahu untuk berjalan kita melaluinya?

461
00:35:18,920 --> 00:35:25,780
[Pelajar] Pasti. Jadi saya menetapkan pembolehubah menggoda untuk mendapatkan nod pertama pokok itu.

462
00:35:25,780 --> 00:35:28,330
Dan kemudian saya hanya bergelung melalui manakala menggoda tidak batal sama,

463
00:35:28,330 --> 00:35:31,700
jadi sementara masih di pokok itu, saya rasa.

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

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

466
00:35:37,640 --> 00:35:40,210
Jika tidak, ia memeriksa jika ia adalah di sebelah kanan atau sebelah kiri.

467
00:35:40,210 --> 00:35:43,400
Jika anda pernah mendapatkan keadaan di mana terdapat ada pokok yang lebih,

468
00:35:43,400 --> 00:35:47,330
maka ia kembali - ia keluar gelung dan pulangan palsu.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. Jadi yang seolah-olah baik.

470
00:35:52,190 --> 00:35:58,470
Sesiapa yang mempunyai sebarang komen atas apa-apa?

471
00:35:58,470 --> 00:36:02,400
Saya tidak mempunyai komen ketepatan pada semua.

472
00:36:02,400 --> 00:36:11,020
Satu perkara yang boleh kita lakukan adalah lelaki ini.

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

474
00:36:21,660 --> 00:36:33,460
Saya akan menetapkan bahawa. Okay.

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

476
00:36:37,150 --> 00:36:38,610
Terdapat memang kuiz pada masa lalu

477
00:36:38,610 --> 00:36:41,170
yang memberi anda berfungsi dengan operator pertigaan,

478
00:36:41,170 --> 00:36:45,750
dan berkata, menterjemah ini, melakukan sesuatu yang tidak menggunakan pertigaan.

479
00:36:45,750 --> 00:36:49,140
Jadi ini adalah satu kes yang sangat biasa apabila saya akan berfikir untuk menggunakan pertigaan,

480
00:36:49,140 --> 00:36:54,610
di mana jika keadaan beberapa menetapkan pembolehubah kepada sesuatu,

481
00:36:54,610 --> 00:36:58,580
lain menetapkan bahawa pemboleh ubah yang sama kepada sesuatu yang lain.

482
00:36:58,580 --> 00:37:03,390
Itu adalah sesuatu yang sangat kerap boleh berubah menjadi jenis ini perkara

483
00:37:03,390 --> 00:37:14,420
mana menetapkan pembolehubah yang ini - atau, dengan baik, adakah ini benar? Kemudian ini, lain ini.

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

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. Cara saya selalu membacanya, temp sama dengan nilai yang lebih besar daripada nilai sementara,

486
00:37:25,570 --> 00:37:30,680
maka ini, lain ini. Ia bertanya soalan.

487
00:37:30,680 --> 00:37:35,200
Adakah ia lebih besar? Kemudian lakukan perkara pertama. Lain melakukan perkara kedua.

488
00:37:35,200 --> 00:37:41,670
Saya hampir selalu - kolon, saya hanya - dalam kepala saya, saya membaca lain.

489
00:37:41,670 --> 00:37:47,180
>> Adakah sesiapa yang mempunyai penyelesaian rekursi?

490
00:37:47,180 --> 00:37:49,670
Okay. Yang satu ini kita akan - ia sudah boleh menjadi besar,

491
00:37:49,670 --> 00:37:53,990
tetapi kita akan membuat ia lebih baik.

492
00:37:53,990 --> 00:37:58,720
Ini adalah cukup banyak idea yang tepat sama.

493
00:37:58,720 --> 00:38:03,060
Ia hanya, baik, adakah anda mahu jelaskan?

494
00:38:03,060 --> 00:38:08,340
[Pelajar] Pasti. Jadi kita memastikan bahawa pokok itu tidak menyeimbangkan 1,

495
00:38:08,340 --> 00:38:13,380
kerana jika pokok itu adalah batal, maka ia akan kembali palsu kerana kita tidak mendapati ia.

496
00:38:13,380 --> 00:38:19,200
Dan jika masih ada pokok, kita pergi ke - kita mula-mula memeriksa jika nilai nod semasa.

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

498
00:38:23,740 --> 00:38:25,970
Adakah bunyi yang sesuai? >> Mm-hmm. (Perjanjian)

499
00:38:25,970 --> 00:38:33,880
Jadi melihat bahawa ini adalah hampir - strukturnya sangat serupa kepada penyelesaian lelaran.

500
00:38:33,880 --> 00:38:38,200
Ia hanya bahawa bukannya recursing, kita mempunyai gelung sementara.

501
00:38:38,200 --> 00:38:40,840
Dan kes asas di sini mana pokok tidak batal sama

502
00:38:40,840 --> 00:38:44,850
adalah keadaan di mana kita tercetus gelung sementara.

503
00:38:44,850 --> 00:38:50,200
Mereka sangat serupa. Tetapi kita akan mengambil langkah ini satu lagi.

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

505
00:38:54,190 --> 00:38:57,680
Notis kita kembali perkara yang sama dalam kedua-dua ayat-ayat ini,

506
00:38:57,680 --> 00:39:00,220
kecuali satu hujah adalah berbeza.

507
00:39:00,220 --> 00:39:07,950
Jadi kita pergi untuk membuat yang ke pertigaan.

508
00:39:07,950 --> 00:39:13,790
Saya melanda sesuatu pilihan, dan ia dibuat simbol. Okay.

509
00:39:13,790 --> 00:39:21,720
Jadi kita pergi untuk kembali itu mengandungi.

510
00:39:21,720 --> 00:39:28,030
Ini semakin menjadi baris, baik, dizum dalam ia.

511
00:39:28,030 --> 00:39:31,060
Biasanya, sebagai perkara yang gaya, saya tidak fikir ramai orang

512
00:39:31,060 --> 00:39:38,640
meletakkan ruang selepas anak panah, tetapi saya rasa jika anda konsisten, ia adalah denda.

513
00:39:38,640 --> 00:39:44,320
Jika nilai adalah kurang daripada nilai pokok, kita mahu recurse di sebelah kiri pokok,

514
00:39:44,320 --> 00:39:53,890
lagi yang kita mahu recurse di sebelah kanan pokok.

515
00:39:53,890 --> 00:39:58,610
Jadi yang merupakan satu langkah membuat melihat ini lebih kecil.

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

517
00:40:02,660 --> 00:40:09,150
kita boleh memisahkan baris.

518
00:40:09,150 --> 00:40:16,500
Okay. Langkah kedua menjadikan ia kelihatan lebih kecil di sini,

519
00:40:16,500 --> 00:40:25,860
jadi nilai pulangan bersamaan nilai pokok, atau mengandungi apa jua.

520
00:40:25,860 --> 00:40:28,340
>> Ini adalah satu perkara yang penting.

521
00:40:28,340 --> 00:40:30,860
Saya tidak pasti jika dia berkata ia dengan jelas di dalam kelas,

522
00:40:30,860 --> 00:40:34,740
tetapi ia dipanggil litar pintas penilaian.

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

524
00:40:41,060 --> 00:40:49,960
Jika itu adalah benar, maka ini adalah benar, dan kita mahu 'atau' dengan apa yang ada di sini.

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

526
00:40:52,520 --> 00:40:55,070
apakah ungkapan keseluruhan akan kembali?

527
00:40:55,070 --> 00:40:59,430
[Pelajar] Benar? >> Ya, kerana benar apa-apa,

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

529
00:41:04,990 --> 00:41:08,150
Jadi seberapa segera seperti yang kita lihat return value = nilai pokok,

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

531
00:41:10,140 --> 00:41:15,710
Tidak juga akan recurse lagi mengandungi ke bawah baris.

532
00:41:15,710 --> 00:41:20,980
Kita boleh mengambil langkah ini satu lagi.

533
00:41:20,980 --> 00:41:29,490
Pulangan pokok tidak batal sama dan semua ini.

534
00:41:29,490 --> 00:41:32,650
Ia dibuat fungsi garis satu.

535
00:41:32,650 --> 00:41:36,790
Ini adalah juga satu contoh penilaian litar pintas.

536
00:41:36,790 --> 00:41:40,680
Tetapi sekarang ia adalah idea yang sama -

537
00:41:40,680 --> 00:41:47,320
bukan - jadi jika pokok tidak batal sama - atau, baik,

538
00:41:47,320 --> 00:41:49,580
jika pokok tidak batal sama, yang merupakan kes yang buruk,

539
00:41:49,580 --> 00:41:54,790
jika pokok sama batal, maka syarat pertama akan menjadi palsu.

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

541
00:42:00,550 --> 00:42:04,640
[Pelajar] Palsu. >> Yeah. Ini adalah separuh lagi penilaian litar pintas,

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

543
00:42:10,710 --> 00:42:14,930
atau jika pokok tidak batal sama, maka kita tidak akan untuk melakukan nilai nilai == pokok.

544
00:42:14,930 --> 00:42:17,010
Kami hanya akan dengan serta-merta mengembalikan palsu.

545
00:42:17,010 --> 00:42:20,970
Yang penting, kerana jika ia tidak melakukan litar pintas menilai,

546
00:42:20,970 --> 00:42:25,860
kemudian jika pokok tidak batal sama, keadaan ini kedua akan kesalahan seg,

547
00:42:25,860 --> 00:42:32,510
kerana pokok-> nilai dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Jadi itulah. Boleh membuat ini - beralih sekali lebih.

549
00:42:40,490 --> 00:42:44,840
Ini adalah satu perkara yang sangat biasa juga, tidak membuat ini selaras dengan ini,

550
00:42:44,840 --> 00:42:49,000
tetapi ia adalah perkara biasa dalam keadaan, mungkin tidak betul di sini,

551
00:42:49,000 --> 00:42:59,380
tetapi jika (pokok! = NULL, dan pokok-> nilai == nilai), melakukan apa sahaja.

552
00:42:59,380 --> 00:43:01,560
Ini adalah satu keadaan yang sangat biasa, di mana sebaliknya mempunyai

553
00:43:01,560 --> 00:43:06,770
untuk memecahkan ini kepada dua IFS, di mana suka, adalah batal pokok?

554
00:43:06,770 --> 00:43:11,780
Okay, ia tidak batal, jadi sekarang adalah nilai pokok yang bersamaan dengan nilai? Melakukan ini.

555
00:43:11,780 --> 00:43:17,300
Sebaliknya, keadaan ini, ini tidak akan seg bersalah

556
00:43:17,300 --> 00:43:21,220
kerana ia akan keluar jika ini berlaku kepada menjadi batal.

557
00:43:21,220 --> 00:43:24,000
Well, saya rasa jika pokok anda adalah penunjuk yang benar-benar tidak sah, ia masih boleh seg bersalah,

558
00:43:24,000 --> 00:43:26,620
tetapi ia tidak boleh seg kesalahan jika pokok adalah batal.

559
00:43:26,620 --> 00:43:32,900
Jika ia tidak batal, ia akan memecahkan sebelum anda pernah dereferenced penunjuk di tempat pertama.

560
00:43:32,900 --> 00:43:35,000
[Pelajar] Adakah ini dipanggil penilaian malas?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] penilaian Malas adalah satu perkara yang berasingan.

562
00:43:40,770 --> 00:43:49,880
Penilaian Malas adalah lebih seperti anda meminta untuk nilai,

563
00:43:49,880 --> 00:43:54,270
anda bertanya untuk mengira nilai, jenis, tetapi anda tidak perlu ia segera.

564
00:43:54,270 --> 00:43:59,040
Jadi sehingga anda benar-benar perlu, ia tidak dinilai.

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

566
00:44:03,920 --> 00:44:06,520
ia mengatakan bahawa kita "malas" menulis.

567
00:44:06,520 --> 00:44:08,670
Sebab kita berbuat demikian adalah kerana kita sebenarnya buffering menulis -

568
00:44:08,670 --> 00:44:11,820
kita tidak mahu untuk menulis bit individu pada satu-satu masa,

569
00:44:11,820 --> 00:44:15,450
atau bait individu pada satu-satu masa, kita bukannya mahu untuk mendapatkan sebahagian bait.

570
00:44:15,450 --> 00:44:19,270
Kemudian, apabila kita mempunyai sebahagian bait, maka kita akan menulis ia keluar.

571
00:44:19,270 --> 00:44:22,640
Walaupun anda meminta untuk menulis - dan fwrite dan fread melakukan perkara yang sama perkara.

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

573
00:44:26,260 --> 00:44:31,610
Walaupun anda meminta untuk menulis dengan segera, ia mungkin tidak akan.

574
00:44:31,610 --> 00:44:34,540
Dan anda tidak boleh yakin bahawa perkara-perkara yang akan ditulis

575
00:44:34,540 --> 00:44:37,540
sehingga anda memanggil hfclose atau apa sahaja ia adalah,

576
00:44:37,540 --> 00:44:39,620
yang kemudian berkata, okay, saya menutup fail saya,

577
00:44:39,620 --> 00:44:43,450
yang bermakna saya lebih baik akan menulis segala-galanya yang saya telah tidak ditulis lagi.

578
00:44:43,450 --> 00:44:45,770
Ia tidak perlu untuk menulis segala-galanya keluar

579
00:44:45,770 --> 00:44:49,010
sehingga anda menutup fail, dan kemudian ia perlu.

580
00:44:49,010 --> 00:44:56,220
Jadi itulah hanya apa yang malas - ia menunggu sehingga ia telah berlaku.

581
00:44:56,220 --> 00:44:59,990
Ini - mengambil 51 dan anda akan pergi ke dalam lebih terperinci,

582
00:44:59,990 --> 00:45:05,470
kerana OCaml dan segala-galanya di 51, segala-galanya adalah rekursi.

583
00:45:05,470 --> 00:45:08,890
Tiada lelaran penyelesaian, pada asasnya.

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

585
00:45:11,550 --> 00:45:14,790
akan menjadi penting untuk banyak keadaan

586
00:45:14,790 --> 00:45:19,920
di mana, jika anda tidak malas menilai, yang bermakna -

587
00:45:19,920 --> 00:45:24,760
Contoh sungai, yang panjang tak terhingga.

588
00:45:24,760 --> 00:45:30,990
Secara teori, anda boleh berfikir nombor tabii sebagai aliran 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Jadi malas dinilai perkara yang halus.

590
00:45:33,090 --> 00:45:37,210
Jika saya katakan saya mahu bilangan yang kesepuluh, maka saya boleh menilai sehingga bilangan kesepuluh.

591
00:45:37,210 --> 00:45:40,300
Jika saya mahu bilangan seratus, maka saya boleh menilai sehingga bilangan seratus.

592
00:45:40,300 --> 00:45:46,290
Tanpa penilaian malas, maka ia akan cuba untuk menilai semua nombor serta-merta.

593
00:45:46,290 --> 00:45:50,000
Anda menilai nombor tak terhingga banyaknya, dan bahawa hanya tidak mungkin.

594
00:45:50,000 --> 00:45:52,080
Jadi terdapat banyak keadaan di mana penilaian malas

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

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

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

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

599
00:46:10,470 --> 00:46:23,850
Kami pergi untuk menukar bahawa untuk memasukkan bool (int nilai nod * pokok).

600
00:46:23,850 --> 00:46:29,120
Kami sebenarnya pergi untuk menukar bahawa sekali lagi dalam sedikit, kita akan melihat mengapa.

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

602
00:46:32,210 --> 00:46:36,730
atas memasukkan jadi kita tidak perlu menulis prototaip fungsi.

603
00:46:36,730 --> 00:46:42,450
Yang merupakan petunjuk bahawa anda akan perlu menggunakan build_node pada sisip.

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

605
00:46:49,590 --> 00:46:52,130
Saya rasa saya disimpan semakan jika anda mahu tarik dari itu,

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

607
00:47:00,240 --> 00:47:04,190
Saya mahu berehat sedikit untuk berfikir tentang logik memasukkan,

608
00:47:04,190 --> 00:47:08,750
jika anda tidak boleh berfikir ia.

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

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

611
00:47:18,640 --> 00:47:21,820
Saya akan bertukar kepada hitam - I'll akan memasukkan 1 di sini.

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

613
00:47:28,070 --> 00:47:32,180
Jadi tidak kira apa yang anda lakukan, anda akan perlu memasukkan di daun.

614
00:47:32,180 --> 00:47:36,130
Semua yang anda perlu lakukan adalah melelar ke bawah pokok itu sehingga anda sampai ke nod

615
00:47:36,130 --> 00:47:40,890
yang perlu nod ibu bapa, ibu bapa nod baru,

616
00:47:40,890 --> 00:47:44,560
dan kemudian menukar penunjuk kiri atau kanan, bergantung kepada sama ada

617
00:47:44,560 --> 00:47:47,060
ia adalah lebih besar daripada atau kurang daripada nod semasa.

618
00:47:47,060 --> 00:47:51,180
Tukar penunjuk yang menuding kepada nod baru anda.

619
00:47:51,180 --> 00:48:05,490
Jadi melelar bawah pokok, membuat titik daun ke nod baru.

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

621
00:48:09,810 --> 00:48:17,990
di mana saya membina pokok perduaan di mana ia adalah betul

622
00:48:17,990 --> 00:48:19,920
jika anda hanya memandang pada nod tunggal,

623
00:48:19,920 --> 00:48:24,830
tetapi 9 adalah untuk sebelah kiri 7 jika anda terlelar turun sepanjang jalan.

624
00:48:24,830 --> 00:48:29,770
Jadi itulah mustahil dalam senario ini, kerana -

625
00:48:29,770 --> 00:48:32,530
berfikir tentang memasukkan 9 atau sesuatu; pada nod yang pertama,

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

627
00:48:35,350 --> 00:48:38,490
Jadi tidak kira 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
ia akan menjadi mustahil bagi saya untuk memasukkan 9 ke kiri 7

630
00:48:43,130 --> 00:48:48,250
kerana secepat saya mencecah 7 saya akan pergi ke kanan.

631
00:48:59,740 --> 00:49:02,070
Adakah sesiapa yang mempunyai sesuatu untuk memulakan dengan?

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

633
00:49:05,480 --> 00:49:09,200
[Pelajar, difahami]

634
00:49:09,200 --> 00:49:14,390
[Pelajar lain, difahami]

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

636
00:49:18,330 --> 00:49:20,690
>> [Pelajar] Sejak kita tahu bahawa kita telah memasukkan

637
00:49:20,690 --> 00:49:24,060
nod baru pada akhir pokok itu,

638
00:49:24,060 --> 00:49:28,070
Saya bergelung melalui pokok iterative

639
00:49:28,070 --> 00:49:31,360
sehingga saya mendapat kepada nod yang menunjukkan untuk menyeimbangkan.

640
00:49:31,360 --> 00:49:34,220
Dan kemudian saya memutuskan untuk meletakkan ia sama ada di sebelah kanan atau sebelah kiri

641
00:49:34,220 --> 00:49:37,420
menggunakan pembolehubah yang betul, ia memberitahu saya di mana untuk meletakkan ia.

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

643
00:49:41,850 --> 00:49:47,520
bahawa titik sementara nod ke nod baru bahawa ia telah mewujudkan,

644
00:49:47,520 --> 00:49:50,770
sama ada di sebelah kiri atau di sebelah kanan, bergantung pada apa nilai hak.

645
00:49:50,770 --> 00:49:56,530
Akhirnya, saya menetapkan nilai nod baru kepada nilai ujian.

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

647
00:49:59,550 --> 00:50:02,050
Ini adalah seperti 95% jalan sana.

648
00:50:02,050 --> 00:50:07,550
Satu isu yang saya lihat, baik, tidak sesiapa melihat isu?

649
00:50:07,550 --> 00:50:18,400
Apakah keadaan di mana mereka keluar daripada gelung?

650
00:50:18,400 --> 00:50:22,100
[Pelajar] Jika menggoda adalah batal? >> Yeah. Jadi bagaimana anda keluar gelung jika menggoda adalah batal.

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

652
00:50:30,220 --> 00:50:35,410
Saya dereference menggoda, yang tidak dapat dielakkan batal.

653
00:50:35,410 --> 00:50:39,840
Jadi perkara lain yang anda perlu lakukan bukan sahaja menjejaki sehingga menggoda adalah batal,

654
00:50:39,840 --> 00:50:45,590
anda mahu untuk menjejaki ibu bapa pada setiap masa.

655
00:50:45,590 --> 00:50:52,190
Kami juga mahu nod ibu bapa *, saya rasa kita boleh memastikan bahawa pada null pada mulanya.

656
00:50:52,190 --> 00:50:55,480
Ini akan mempunyai tingkah laku yang pelik untuk akar pokok itu,

657
00:50:55,480 --> 00:50:59,210
tetapi kita akan mendapat itu.

658
00:50:59,210 --> 00:51:03,950
Jika nilai adalah lebih besar daripada apa sahaja, maka temp = menggoda betul.

659
00:51:03,950 --> 00:51:07,910
Tetapi sebelum kita berbuat demikian, ibu bapa temp =.

660
00:51:07,910 --> 00:51:14,500
Atau adakah ibu bapa yang sentiasa akan menggoda sama? Adakah bahawa kes?

661
00:51:14,500 --> 00:51:19,560
Jika menggoda tidak batal, maka saya akan bergerak ke bawah, tidak kira apa,

662
00:51:19,560 --> 00:51:24,030
kepada nod yang menggoda adalah ibu bapa.

663
00:51:24,030 --> 00:51:27,500
Jadi ibu bapa yang akan menjadi temp, dan kemudian saya bergerak temp turun.

664
00:51:27,500 --> 00:51:32,410
Sekarang menggoda adalah batal, tetapi mata ibu bapa kepada ibu bapa perkara yang batal.

665
00:51:32,410 --> 00:51:39,110
Jadi turun di sini, saya tidak mahu untuk menetapkan hak sama dengan 1.

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

667
00:51:41,300 --> 00:51:45,130
dan saya rasa anda juga mahu lakukan -

668
00:51:45,130 --> 00:51:48,530
jika anda bergerak ke kiri, anda mahu untuk menetapkan hak sama rata kepada 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 kanan = 0. Jika kanan = 1,

671
00:51:58,590 --> 00:52:04,260
sekarang kita mahu untuk membuat ibu bapa newnode penunjuk yang betul,

672
00:52:04,260 --> 00:52:08,520
lain, kita mahu untuk membuat newnode ibu bapa penunjuk kiri.

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

674
00:52:16,850 --> 00:52:24,880
Okay. Jadi ini adalah cara kita - baik, sebenarnya, bukannya melakukan perkara ini,

675
00:52:24,880 --> 00:52:29,630
kita 1/2 dijangka anda untuk menggunakan build_node.

676
00:52:29,630 --> 00:52:40,450
Dan kemudian jika newnode sama batal, kembalikan palsu.

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

678
00:52:44,170 --> 00:52:47,690
>> Ini adalah apa penyelesaian kakitangan lakukan.

679
00:52:47,690 --> 00:52:52,360
Saya tidak bersetuju dengan ini sebagai cara yang "betul" pergi mengenainya

680
00:52:52,360 --> 00:52:57,820
tetapi ini adalah betul-betul halus dan ia akan berfungsi.

681
00:52:57,820 --> 00:53:02,840
Satu perkara yang hak pelik sedikit sekarang ialah

682
00:53:02,840 --> 00:53:08,310
jika pokok itu bermula sebagai batal, kita lulus dalam pokok nol.

683
00:53:08,310 --> 00:53:12,650
Saya rasa ia bergantung kepada bagaimana anda menentukan tingkah laku lulus dalam pokok nol.

684
00:53:12,650 --> 00:53:15,490
Saya akan berfikir bahawa jika anda lulus dalam pokok nol,

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

686
00:53:17,520 --> 00:53:23,030
hanya perlu kembali pokok di mana nilai hanya adalah bahawa nod tunggal.

687
00:53:23,030 --> 00:53:25,830
Adakah orang bersetuju dengan itu? Anda boleh, jika anda mahu,

688
00:53:25,830 --> 00:53:28,050
jika anda lulus dalam pokok 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
Ia terpulang kepada anda untuk menentukan bahawa.

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

692
00:53:38,320 --> 00:53:40,720
baik, anda akan mempunyai masalah berbuat demikian, kerana

693
00:53:40,720 --> 00:53:44,090
ia akan menjadi lebih mudah jika kita mempunyai penunjuk global kepada benda itu,

694
00:53:44,090 --> 00:53:48,570
tetapi kita tidak, jadi jika pokok adalah batal, ada apa-apa yang boleh kita lakukan tentang itu.

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

696
00:53:50,960 --> 00:53:52,840
Jadi saya akan menukar insert.

697
00:53:52,840 --> 00:53:56,540
Kita teknikal hanya boleh menukar hak ini di sini,

698
00:53:56,540 --> 00:53:58,400
bagaimana ia iterating atas perkara,

699
00:53:58,400 --> 00:54:04,530
tetapi saya akan untuk menukar insert untuk mengambil nod ** pokok.

700
00:54:04,530 --> 00:54:07,510
Petunjuk Double.

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

702
00:54:09,710 --> 00:54:12,330
Daripada berurusan dengan penunjuk ke nodus,

703
00:54:12,330 --> 00:54:16,690
perkara yang saya akan memanipulasi penunjuk ini.

704
00:54:16,690 --> 00:54:18,790
Saya akan memanipulasi penunjuk ini.

705
00:54:18,790 --> 00:54:21,770
Saya akan memanipulasi petunjuk langsung.

706
00:54:21,770 --> 00:54:25,760
Ini masuk akal kerana, berfikir tentang turun -

707
00:54:25,760 --> 00:54:33,340
baik, sekarang ini mata untuk menyeimbangkan.

708
00:54:33,340 --> 00:54:38,130
Apa yang saya mahu lakukan adalah memanipulasi penunjuk ini menunjukkan tidak menyeimbangkan.

709
00:54:38,130 --> 00:54:40,970
Saya mahu ia menunjukkan nod baru saya.

710
00:54:40,970 --> 00:54:44,870
Jika saya hanya menjejaki petunjuk petunjuk saya,

711
00:54:44,870 --> 00:54:47,840
maka saya tidak perlu untuk menjejaki penunjuk ibu bapa.

712
00:54:47,840 --> 00:54:52,640
Saya hanya boleh menjejaki untuk melihat jika penunjuk menunjuk untuk menyeimbangkan,

713
00:54:52,640 --> 00:54:54,580
dan jika penunjuk menunjuk untuk menyeimbangkan,

714
00:54:54,580 --> 00:54:57,370
mengubahnya menuding kepada nod yang saya mahu.

715
00:54:57,370 --> 00:55:00,070
Dan saya boleh menukar ia kerana saya mempunyai penunjuk kepada penunjuk.

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

717
00:55:02,040 --> 00:55:05,470
Anda sebenarnya boleh melakukannya rekursif cukup mudah.

718
00:55:05,470 --> 00:55:08,080
Adakah kita mahu berbuat demikian?

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

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

721
00:55:16,790 --> 00:55:24,070
Pertama, apa kes asas kami akan menjadi?

722
00:55:24,070 --> 00:55:29,140
Hampir selalu kes asas kami, tetapi sebenarnya, ini adalah jenis yang sukar.

723
00:55:29,140 --> 00:55:34,370
Perkara pertama yang pertama, jika (pokok == NULL)

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

725
00:55:37,550 --> 00:55:40,460
Ini adalah berbeza daripada null pokok anda.

726
00:55:40,460 --> 00:55:44,510
Ini adalah penunjuk penunjuk akar anda menjadi batal

727
00:55:44,510 --> 00:55:48,360
yang bermakna bahawa penunjuk akar anda tidak wujud.

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

729
00:55:52,390 --> 00:55:55,760
nod * - mari kita hanya menggunakan semula ini.

730
00:55:55,760 --> 00:55:58,960
Nod * akar = NULL,

731
00:55:58,960 --> 00:56:00,730
dan kemudian saya akan memanggil memasukkan dengan melakukan sesuatu seperti,

732
00:56:00,730 --> 00:56:04,540
memasukkan 4 ke akar &.

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

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

735
00:56:11,170 --> 00:56:15,120
Ini adalah sah. Dalam kes ini, pokok, di sini,

736
00:56:15,120 --> 00:56:20,120
pokok tidak adalah batal atau memasukkan.

737
00:56:20,120 --> 00:56:24,630
Di sini. Pokok adalah tidak batal, pokok * adalah batal, yang baik

738
00:56:24,630 --> 00:56:26,680
kerana jika pokok * adalah batal, maka saya boleh memanipulasi ia

739
00:56:26,680 --> 00:56:29,210
kini menunjukkan apa yang saya mahu ia menunjukkan.

740
00:56:29,210 --> 00:56:34,750
Tetapi jika pokok adalah batal, yang bermakna saya hanya datang ke sini dan kata batal.

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

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

743
00:56:45,540 --> 00:56:48,220
Jadi Saya pada dasarnya sudah berkata apa kes asas sebenar kami.

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

745
00:56:50,580 --> 00:56:55,030
[Pelajar, difahami]

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

747
00:57:00,000 --> 00:57:04,520
Ini berkaitan dengan kes itu di sini

748
00:57:04,520 --> 00:57:09,640
di mana jika penunjuk merah saya adalah penunjuk Saya memberi tumpuan kepada,

749
00:57:09,640 --> 00:57:12,960
jadi seperti saya memberi tumpuan kepada penunjuk ini, kini saya memberi tumpuan kepada penunjuk ini.

750
00:57:12,960 --> 00:57:15,150
Sekarang saya memberi tumpuan kepada penunjuk ini.

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

752
00:57:18,160 --> 00:57:22,880
pernah - jika *, penunjuk merah saya, pernah batal,

753
00:57:22,880 --> 00:57:28,470
yang bermakna bahawa saya di kes di mana saya memberi tumpuan kepada penunjuk bahawa mata -

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

755
00:57:32,530 --> 00:57:41,090
Saya ingin menukar penunjuk ini untuk menunjukkan kepada nod baru saya.

756
00:57:41,090 --> 00:57:45,230
Kembali di sini.

757
00:57:45,230 --> 00:57:56,490
Newnode saya hanya akan menjadi nod * n = build_node (nilai)

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
Yang lain kita mahu mengubah apa penunjuk sedang menunjuk ke

760
00:58:12,600 --> 00:58:17,830
kini menunjukkan kepada nod yang baru dibina kami.

761
00:58:17,830 --> 00:58:20,280
Kita sebenarnya boleh berbuat demikian di sini.

762
00:58:20,280 --> 00:58:30,660
Daripada mengatakan n, kita katakan * pokok = jika pokok *.

763
00:58:30,660 --> 00:58:35,450
Semua orang memahami bahawa? Bahawa dengan berurusan dengan petunjuk untuk petunjuk,

764
00:58:35,450 --> 00:58:40,750
kita boleh mengubah penunjuk nol untuk menunjukkan kepada perkara-perkara yang kita mahu mereka menunjukkan.

765
00:58:40,750 --> 00:58:42,820
Itulah kes asas kami.

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

767
00:58:45,740 --> 00:58:51,430
akan menjadi sangat serupa kepada semua recursions lain yang kami telah lakukan.

768
00:58:51,430 --> 00:58:55,830
Kami akan mahu untuk memasukkan nilai,

769
00:58:55,830 --> 00:58:59,040
dan kini saya akan menggunakan pertigaan lagi, tetapi apa yang keadaan kita akan menjadi?

770
00:58:59,040 --> 00:59:05,180
Apa yang kita sedang mencari untuk membuat keputusan sama ada kita mahu pergi kiri atau kanan?

771
00:59:05,180 --> 00:59:07,760
Mari kita melakukannya dalam langkah-langkah yang berasingan.

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

773
00:59:18,850 --> 00:59:23,200
[Pelajar] nilai Pokok?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Jadi ingat bahawa saya kini -

775
00:59:27,490 --> 00:59:31,260
[Pelajar, difahami]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, jadi di sini, katakan bahawa ini anak panah hijau

777
00:59:34,140 --> 00:59:39,050
adalah satu contoh apa pokok kini ialah, adalah penunjuk kepada penunjuk ini.

778
00:59:39,050 --> 00:59:46,610
Jadi itu bermakna saya penunjuk kepada penunjuk kepada 3.

779
00:59:46,610 --> 00:59:48,800
Dereference dua kali kedengaran seperti bagus.

780
00:59:48,800 --> 00:59:51,010
Apa yang saya - bagaimana saya berbuat demikian?

781
00:59:51,010 --> 00:59:53,210
[Pelajar] Dereference sekali, dan kemudian melakukan arrow bahawa cara?

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

783
00:59:58,420 --> 01:00:05,960
akan memberi saya nilai nod yang saya tidak langsung menunjuk ke.

784
01:00:05,960 --> 01:00:11,980
Jadi saya juga boleh menulis ia ** tree.value jika anda lebih suka bahawa.

785
01:00:11,980 --> 01:00:18,490
Sama ada berfungsi.

786
01:00:18,490 --> 01:00:26,190
Jika itu berlaku, maka saya mahu untuk memanggil memasukkan dengan nilai.

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

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

789
01:00:39,440 --> 01:00:41,900
Dan saya mahu penunjuk kepada perkara yang

790
01:00:41,900 --> 01:00:44,930
supaya jika kiri berakhir sehingga menjadi penunjuk nol,

791
01:00:44,930 --> 01:00:48,360
Saya boleh mengubah suai ia untuk menunjukkan kepada nod baru saya.

792
01:00:48,360 --> 01:00:51,460
>> Dan kes lain boleh menjadi sangat serupa.

793
01:00:51,460 --> 01:00:55,600
Mari kita sebenarnya membuat bahawa pertigaan saya sekarang.

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

795
01:01:04,480 --> 01:01:11,040
Kemudian kita mahu untuk mengemaskini ** kami ke kiri,

796
01:01:11,040 --> 01:01:17,030
lain kita mahu untuk mengemaskini ** kami ke kanan.

797
01:01:17,030 --> 01:01:22,540
[Pelajar] Adakah yang mendapat penunjuk penunjuk?

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

799
01:01:30,940 --> 01:01:35,040
[Pelajar, difahami] >> Yeah.

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

801
01:01:41,140 --> 01:01:45,140
Jadi dengan mengambil penunjuk itu, yang memberikan saya apa yang saya mahu

802
01:01:45,140 --> 01:01:50,090
penunjuk kepada lelaki itu.

803
01:01:50,090 --> 01:01:54,260
[Pelajar] Bolehkah kita pergi lebih lagi mengapa kita menggunakan dua petunjuk?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Jadi - tidak, anda boleh, dan penyelesaian yang sebelum

805
01:01:58,220 --> 01:02:04,540
adalah satu cara melakukannya tanpa melakukan dua petunjuk.

806
01:02:04,540 --> 01:02:08,740
Anda perlu dapat untuk memahami menggunakan dua petunjuk,

807
01:02:08,740 --> 01:02:11,660
dan ini adalah satu penyelesaian yang lebih bersih.

808
01:02:11,660 --> 01:02:16,090
Juga, notis bahawa, apa yang berlaku jika pokok saya -

809
01:02:16,090 --> 01:02:24,480
apa yang berlaku jika akar saya batal? Apa yang akan berlaku jika saya melakukan kes ini di sini?

810
01:02:24,480 --> 01:02:30,540
Jadi nod * akar = NULL, masukkan 4 ke akar &.

811
01:02:30,540 --> 01:02:35,110
Apa yang akar akan menjadi selepas ini?

812
01:02:35,110 --> 01:02:37,470
[Pelajar, difahami] >> Yeah.

813
01:02:37,470 --> 01:02:41,710
Akar nilai akan menjadi 4.

814
01:02:41,710 --> 01:02:45,510
Akar kiri akan menjadi batal, hak akar akan menjadi batal.

815
01:02:45,510 --> 01:02:49,490
Dalam kes di mana kita tidak lulus akar by Alamat,

816
01:02:49,490 --> 01:02:52,490
kita tidak boleh mengubah suai akar.

817
01:02:52,490 --> 01:02:56,020
Dalam kes di mana pokok - mana akar adalah batal,

818
01:02:56,020 --> 01:02:58,410
kita hanya terpaksa pulang palsu. Ada apa-apa yang kita boleh lakukan.

819
01:02:58,410 --> 01:03:01,520
Kita tidak boleh memasukkan nod ke pokok kosong.

820
01:03:01,520 --> 01:03:06,810
Tetapi sekarang kita boleh, kita hanya membuat pokok kosong ke pokok satu nod.

821
01:03:06,810 --> 01:03:13,400
Yang biasanya cara jangkaan bahawa ia sepatutnya untuk bekerja.

822
01:03:13,400 --> 01:03:21,610
>> Tambahan pula, ini adalah jauh lebih pendek berbanding

823
01:03:21,610 --> 01:03:26,240
juga mengesan ibu bapa, dan sebagainya anda melelar turun sepanjang jalan.

824
01:03:26,240 --> 01:03:30,140
Sekarang saya mempunyai ibu bapa saya, dan saya hanya mempunyai penunjuk hak ibu bapa saya untuk apa jua.

825
01:03:30,140 --> 01:03:35,640
Sebaliknya, jika kita lakukan ini iterative, ia akan menjadi idea yang sama dengan gelung sementara.

826
01:03:35,640 --> 01:03:38,100
Tetapi sebaliknya perlu berurusan dengan penunjuk ibu bapa saya,

827
01:03:38,100 --> 01:03:40,600
bukannya penunjuk semasa saya akan menjadi perkara yang

828
01:03:40,600 --> 01:03:43,790
bahawa saya terus mengubah suai untuk menunjukkan kepada nod baru saya.

829
01:03:43,790 --> 01:03:46,090
Saya tidak mempunyai untuk berurusan dengan sama ada ia menunjuk ke kiri.

830
01:03:46,090 --> 01:03:48,810
Saya tidak mempunyai untuk berurusan dengan sama ada ia menghala ke kanan.

831
01:03:48,810 --> 01:04:00,860
Ia hanya apa penunjuk ini, saya akan menetapkan ia untuk menunjukkan kepada nod baru saya.

832
01:04:00,860 --> 01:04:05,740
Semua orang memahami bagaimana ia berfungsi?

833
01:04:05,740 --> 01:04:09,460
Jika tidak mengapa kita mahu melakukannya dengan cara ini,

834
01:04:09,460 --> 01:04:14,920
tetapi sekurang-kurangnya bahawa kerja-kerja ini sebagai penyelesaian?

835
01:04:14,920 --> 01:04:17,110
[Pelajar] Di manakah kita kembali benar?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Itu mungkin betul di sini.

837
01:04:21,550 --> 01:04:26,690
Jika kita memasukkan, kembalikan benar.

838
01:04:26,690 --> 01:04:32,010
Lain, turun di sini kita akan mahu kembali pulangan memasukkan apa sahaja.

839
01:04:32,010 --> 01:04:35,950
>> Dan apa yang istimewa tentang fungsi ini rekursi?

840
01:04:35,950 --> 01:04:43,010
Ia rekursi ekor, jadi selagi kita menyusun dengan pengoptimuman beberapa,

841
01:04:43,010 --> 01:04:48,060
ia akan menyedari bahawa dan anda tidak akan mendapatkan limpahan timbunan daripada ini,

842
01:04:48,060 --> 01:04:53,230
walaupun pokok kita mempunyai ketinggian 10,000 atau 10 juta.

843
01:04:53,230 --> 01:04:55,630
[Pelajar, difahami]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Saya fikir ia tidak di Dash - atau apa yang pengoptimuman tahap

845
01:05:00,310 --> 01:05:03,820
diperlukan untuk rekursi ekor untuk diiktiraf.

846
01:05:03,820 --> 01:05:09,350
Saya fikir ia mengiktiraf - GCC dan dilafaz

847
01:05:09,350 --> 01:05:12,610
juga mempunyai makna yang berbeza bagi tahap pengoptimuman mereka.

848
01:05:12,610 --> 01:05:17,870
Saya mahu mengatakan ia DashO 2, untuk memastikan bahawa ia akan mengiktiraf rekursi ekor.

849
01:05:17,870 --> 01:05:27,880
Tetapi kita - anda boleh membina seperti contoh Fibonocci atau sesuatu.

850
01:05:27,880 --> 01:05:30,030
Ia tidak mudah untuk menguji dengan ini, kerana ia sukar untuk membina

851
01:05:30,030 --> 01:05:32,600
pokok binari yang begitu besar.

852
01:05:32,600 --> 01:05:37,140
Tetapi yeah, saya fikir ia adalah DashO 2,

853
01:05:37,140 --> 01:05:40,580
jika anda menyusun dengan DashO 2, ia akan mencari rekursi ekor

854
01:05:40,580 --> 01:05:54,030
dan mengoptimumkan yang keluar.

855
01:05:54,030 --> 01:05:58,190
Mari kita kembali kepada - memasukkan literal perkara terakhir yang diperlukan.

856
01:05:58,190 --> 01:06:04,900
Mari kita kembali kepada sisip di sini

857
01:06:04,900 --> 01:06:07,840
di mana kita pergi untuk melakukan idea yang sama.

858
01:06:07,840 --> 01:06:14,340
Ia masih akan mempunyai kecacatan tidak dapat untuk sepenuhnya mengendalikan

859
01:06:14,340 --> 01:06:17,940
apabila akar itu sendiri adalah batal, atau kemasukan lalu adalah batal,

860
01:06:17,940 --> 01:06:20,060
tetapi sebaliknya berurusan dengan penunjuk ibu bapa,

861
01:06:20,060 --> 01:06:27,430
mari kita menggunakan logik yang sama mengekalkan petunjuk kepada petunjuk.

862
01:06:27,430 --> 01:06:35,580
Jika di sini kita menyimpan nod kami ** kini,

863
01:06:35,580 --> 01:06:37,860
dan kita tidak perlu untuk menjejaki kanan lagi,

864
01:06:37,860 --> 01:06:47,190
tetapi nod ** kini = & pokok.

865
01:06:47,190 --> 01:06:54,800
Dan kini gelung sementara kita akan menjadi sementara kini * tidak batal sama.

866
01:06:54,800 --> 01:07:00,270
Tidak perlu menjejaki ibu bapa lagi.

867
01:07:00,270 --> 01:07:04,180
Tidak perlu untuk menjejaki kiri dan kanan.

868
01:07:04,180 --> 01:07:10,190
Dan saya akan memanggilnya sementara, kerana kita sudah menggunakan menggoda.

869
01:07:10,190 --> 01:07:17,200
Okay. Jadi, jika (nilai> * temp),

870
01:07:17,200 --> 01:07:24,010
kemudian & (* temp) -> right

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 ketika ini, selepas gelung selama ini,

873
01:07:32,730 --> 01:07:36,380
Saya hanya melakukan ini kerana mungkin ia adalah lebih mudah untuk berfikir tentang iterative daripada rekursif,

874
01:07:36,380 --> 01:07:39,010
tetapi selepas gelung selama ini,

875
01:07:39,010 --> 01:07:43,820
* Menggoda adalah penunjuk kita ingin menukar.

876
01:07:43,820 --> 01:07:48,960
>> Sebelum kita mempunyai ibu bapa, dan kita mahu untuk menukar sama ada kiri ibu bapa atau ibu bapa hak,

877
01:07:48,960 --> 01:07:51,310
tetapi jika kita mahu menukar hak ibu bapa,

878
01:07:51,310 --> 01:07:54,550
maka menggoda * adalah hak ibu bapa, dan kita boleh menukar ia secara langsung.

879
01:07:54,550 --> 01:08:05,860
Jadi turun di sini, kita boleh melakukan * temp = newnode, dan itulah ia.

880
01:08:05,860 --> 01:08:09,540
Jadi notis, semua yang kita lakukan dalam hal ini adalah mengambil baris kod.

881
01:08:09,540 --> 01:08:14,770
Dalam usaha untuk menjejaki induk dalam semua yang adalah usaha tambahan.

882
01:08:14,770 --> 01:08:18,689
Di sini, jika kita hanya menyimpan mengesan penunjuk penunjuk,

883
01:08:18,689 --> 01:08:22,990
dan walaupun kita mahu untuk mendapatkan menghapuskan semua ini pendakap kerinting kini,

884
01:08:22,990 --> 01:08:27,170
membuat ia kelihatan lebih pendek.

885
01:08:27,170 --> 01:08:32,529
Ini kini adalah penyelesaian yang sama yang tepat,

886
01:08:32,529 --> 01:08:38,210
tetapi kurang baris kod.

887
01:08:38,210 --> 01:08:41,229
Sebaik sahaja anda mula mengiktiraf ini sebagai penyelesaian yang sah,

888
01:08:41,229 --> 01:08:43,529
ia juga mudah sebab tentang daripada seperti, okay,

889
01:08:43,529 --> 01:08:45,779
mengapa saya mempunyai bendera ini di sebelah kanan int?

890
01:08:45,779 --> 01:08:49,290
Apa maksudnya? Oh, ia menandakan bahawa

891
01:08:49,290 --> 01:08:51,370
setiap kali saya pergi betul, saya perlu untuk menetapkan ia,

892
01:08:51,370 --> 01:08:53,819
lain jika saya pergi meninggalkan saya perlu untuk menetapkan ia kepada sifar.

893
01:08:53,819 --> 01:09:04,060
Di sini, saya tidak mempunyai sebab tentang itu, ia hanya lebih mudah untuk berfikir tentang.

894
01:09:04,060 --> 01:09:06,710
Soalan?

895
01:09:06,710 --> 01:09:16,290
[Pelajar, difahami] >> Yeah.

896
01:09:16,290 --> 01:09:23,359
Okay, jadi dalam bit terakhir -

897
01:09:23,359 --> 01:09:28,080
Saya rasa satu fungsi yang cepat dan mudah yang boleh kita lakukan adalah,

898
01:09:28,080 --> 01:09:34,910
let's - bersama-sama, saya rasa, cuba dan menulis mengandungi fungsi

899
01:09:34,910 --> 01:09:38,899
yang tidak peduli sama ada ia adalah pokok gelintaran perduaan.

900
01:09:38,899 --> 01:09:43,770
Ini mengandungi fungsi perlu kembali benar

901
01:09:43,770 --> 01:09:58,330
jika mana-mana sahaja di pokok binari umum ini adalah nilai yang kita cari.

902
01:09:58,330 --> 01:10:02,520
Jadi mari kita melakukannya rekursif dan kemudian kami akan melakukannya iterative.

903
01:10:02,520 --> 01:10:07,300
Kita boleh sebenarnya hanya melakukannya bersama-sama, kerana ini akan menjadi benar-benar pendek.

904
01:10:07,300 --> 01:10:11,510
>> Apa kes asas saya akan?

905
01:10:11,510 --> 01:10:13,890
[Pelajar, difahami]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Jadi jika (pokok == NULL), maka apa?

907
01:10:18,230 --> 01:10:22,740
[Pelajar] Return palsu.

908
01:10:22,740 --> 01:10:26,160
[Bowden] yang lain, baik, saya tidak perlu yang lain.

909
01:10:26,160 --> 01:10:30,250
Jika kes asas saya yang lain.

910
01:10:30,250 --> 01:10:32,450
[Pelajar] Pokok nilai? >> Yeah.

911
01:10:32,450 --> 01:10:36,430
Jadi, jika (pokok-> nilai == nilai.

912
01:10:36,430 --> 01:10:39,920
Perhatikan kami kembali ke nod *, tidak nod ** s?

913
01:10:39,920 --> 01:10:42,990
Contains tidak akan perlu untuk menggunakan ** nod,

914
01:10:42,990 --> 01:10:45,480
kerana kita tidak mengubah petunjuk.

915
01:10:45,480 --> 01:10:50,540
Kami hanya menyeberangi mereka.

916
01:10:50,540 --> 01:10:53,830
Jika itu berlaku, maka kita mahu kembali benar.

917
01:10:53,830 --> 01:10:58,270
Yang lain kita mahu untuk melintasi kanak-kanak.

918
01:10:58,270 --> 01:11:02,620
Jadi kita tidak boleh sebab tentang sama ada segala-galanya ke kiri adalah kurang

919
01:11:02,620 --> 01:11:05,390
dan segala-galanya ke kanan adalah lebih besar.

920
01:11:05,390 --> 01:11:09,590
Jadi apa yang keadaan kita akan berada di sini - atau, apa yang kita akan lakukan?

921
01:11:09,590 --> 01:11:11,840
[Pelajar, difahami] >> Yeah.

922
01:11:11,840 --> 01:11:17,400
Nyata ini mengandungi (nilai, pokok> kiri)

923
01:11:17,400 --> 01:11:26,860
atau mengandungi (nilai, pokok-> right). Dan itu sahaja.

924
01:11:26,860 --> 01:11:29,080
Dan notis terdapat beberapa penilaian litar pintas,

925
01:11:29,080 --> 01:11:32,520
di mana jika kita berlaku untuk mencari nilai dalam pokok kiri,

926
01:11:32,520 --> 01:11:36,820
kita tidak perlu melihat pokok yang betul.

927
01:11:36,820 --> 01:11:40,430
Itulah fungsi keseluruhan.

928
01:11:40,430 --> 01:11:43,690
Sekarang mari kita melakukannya iterative,

929
01:11:43,690 --> 01:11:48,060
yang akan menjadi kurang baik.

930
01:11:48,060 --> 01:11:54,750
Kami akan mengambil permulaan yang biasa kini nod * = pokok.

931
01:11:54,750 --> 01:12:03,250
Walaupun (kini! = NULL).

932
01:12:03,250 --> 01:12:08,600
Cepat akan melihat masalah.

933
01:12:08,600 --> 01:12:12,250
Jika kini - di sini, jika kita pernah keluar daripada ini,

934
01:12:12,250 --> 01:12:16,020
maka kita telah kehabisan perkara untuk melihat, jadi kembali palsu.

935
01:12:16,020 --> 01:12:24,810
Jika (kini> nilai == nilai), 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 sama ada kita mahu pergi kiri atau kanan.

938
01:12:36,250 --> 01:12:44,590
Jadi sewenang-wenangnya, mari kita hanya pergi ke kiri.

939
01:12:44,590 --> 01:12:47,910
Saya telah jelas menghadapi isu di mana saya telah benar-benar ditinggalkan segala-galanya -

940
01:12:47,910 --> 01:12:50,760
Saya akan hanya pernah memeriksa sebelah kiri pokok.

941
01:12:50,760 --> 01:12:56,050
Saya tidak akan memeriksa apa-apa yang kanak-kanak yang betul apa-apa.

942
01:12:56,050 --> 01:13:00,910
Bagaimana saya menetapkan ini?

943
01:13:00,910 --> 01:13:05,260
[Pelajar] Anda perlu menjejaki kiri dan kanan dalam timbunan.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Jadi mari kita membuat ia

945
01:13:13,710 --> 01:13:32,360
struct senarai, nod * n, dan kemudian nod ** seterusnya?

946
01:13:32,360 --> 01:13:40,240
Saya fikir yang berfungsi dengan baik.

947
01:13:40,240 --> 01:13:45,940
Kami mahu pergi ke kiri, atau let's - di sini.

948
01:13:45,940 --> 01:13:54,350
Struct = senarai senarai, ia akan mula

949
01:13:54,350 --> 01:13:58,170
daripada senarai struct ini.

950
01:13:58,170 --> 01:14:04,040
* Senarai = NULL. Jadi yang akan menjadi senarai berpaut kami

951
01:14:04,040 --> 01:14:08,430
subtrees bahawa kita telah melangkau lebih.

952
01:14:08,430 --> 01:14:13,800
Kami akan merentasi dibiarkan sekarang,

953
01:14:13,800 --> 01:14:17,870
tetapi kerana kita tidak dapat tidak perlu untuk kembali ke kanan,

954
01:14:17,870 --> 01:14:26,140
Kami akan menyimpan sebelah kanan di dalam senarai struct kami.

955
01:14:26,140 --> 01:14:32,620
Kemudian kita akan mempunyai new_list atau struct,

956
01:14:32,620 --> 01:14:41,080
struct list *, new_list = malloc (sizeof (senarai)).

957
01:14:41,080 --> 01:14:44,920
Saya akan mengabaikan kesilapan-memeriksa bahawa, tetapi anda perlu menyemak untuk melihat batal jika ia.

958
01:14:44,920 --> 01:14:50,540
New_list nod ia akan menunjukkan kepada -

959
01:14:50,540 --> 01:14:56,890
oh, itulah sebabnya saya mahu ia di sini. Ia akan untuk menunjukkan senarai struct kedua.

960
01:14:56,890 --> 01:15:02,380
Itulah betapa dikaitkan kerja senarai.

961
01:15:02,380 --> 01:15:04,810
Ini adalah sama seperti senarai int dikaitkan

962
01:15:04,810 --> 01:15:06,960
kecuali kita hanya menggantikan int * nod.

963
01:15:06,960 --> 01:15:11,040
Ia adalah betul-betul sama.

964
01:15:11,040 --> 01:15:15,100
Jadi new_list, nilai nod new_list kami,

965
01:15:15,100 --> 01:15:19,120
akan menjadi kini-> right.

966
01:15:19,120 --> 01:15:24,280
Nilai kami new_list-> seterusnya akan menjadi senarai asal kita,

967
01:15:24,280 --> 01:15:30,760
dan kemudian kita pergi untuk mengemaskini senarai kami untuk menunjukkan new_list.

968
01:15:30,760 --> 01:15:33,650
>> Sekarang kita perlu beberapa jenis cara perkara-perkara yang menarik,

969
01:15:33,650 --> 01:15:37,020
seperti yang kita telah dilalui anak pohon keseluruhan kiri.

970
01:15:37,020 --> 01:15:40,480
Sekarang kita perlu untuk menarik barangan daripada itu,

971
01:15:40,480 --> 01:15:43,850
seperti kini adalah batal, kita tidak mahu hanya kembali palsu.

972
01:15:43,850 --> 01:15:50,370
Kami mahu sekarang tarik luar di senarai baru kami.

973
01:15:50,370 --> 01:15:53,690
Satu cara yang mudah untuk melakukan ini - baik, sebenarnya, terdapat pelbagai cara untuk berbuat demikian.

974
01:15:53,690 --> 01:15:56,680
Sesiapa yang mempunyai cadangan?

975
01:15:56,680 --> 01:15:58,790
Jika perlu saya lakukan ini atau bagaimana yang perlu saya lakukan ini?

976
01:15:58,790 --> 01:16:08,010
Kita hanya mempunyai beberapa minit, tetapi apa-apa cadangan?

977
01:16:08,010 --> 01:16:14,750
Sebaliknya - satu cara, bukan keadaan kita yang sementara,

978
01:16:14,750 --> 01:16:17,090
apa yang kita sedang melihat tidak batal,

979
01:16:17,090 --> 01:16:22,340
sebaliknya kita akan terus pergi sehingga senarai kami sendiri adalah batal.

980
01:16:22,340 --> 01:16:25,680
Jadi, jika senarai kami akhirnya menjadi batal,

981
01:16:25,680 --> 01:16:30,680
maka kita telah kehabisan perkara untuk mencari, untuk mencari lebih.

982
01:16:30,680 --> 01:16:39,860
Tetapi itu bermakna bahawa perkara pertama dalam senarai kami hanya akan menjadi nod pertama.

983
01:16:39,860 --> 01:16:49,730
Perkara yang pertama akan - kita tidak lagi perlu melihat bahawa.

984
01:16:49,730 --> 01:16:58,710
Jadi senarai-> n akan menjadi pokok kami.

985
01:16:58,710 --> 01:17:02,860
senarai> seterusnya akan menjadi batal.

986
01:17:02,860 --> 01:17:07,580
Dan kini manakala senarai tidak batal sama.

987
01:17:07,580 --> 01:17:11,610
Cur akan tarik sesuatu dari senarai kami.

988
01:17:11,610 --> 01:17:13,500
Jadi kini akan sama senarai> n.

989
01:17:13,500 --> 01:17:20,850
Dan kemudian senarai akan sama senarai> n, atau senarai> seterusnya.

990
01:17:20,850 --> 01:17:23,480
Jadi, jika nilai kini sama nilai.

991
01:17:23,480 --> 01:17:28,790
Sekarang kita boleh menambah kedua-dua penunjuk kanan kita dan penunjuk kiri kita

992
01:17:28,790 --> 01:17:32,900
selagi mereka tidak batal.

993
01:17:32,900 --> 01:17:36,390
Down di sini, saya rasa kita sepatutnya dilakukan bahawa di tempat pertama.

994
01:17:36,390 --> 01:17:44,080
Jika (kini> right! = NULL)

995
01:17:44,080 --> 01:17:56,380
maka kita akan memasukkan nod tersebut ke dalam senarai kami.

996
01:17:56,380 --> 01:17:59,290
Jika (kini> kiri), ini adalah sedikit kerja tambahan, tetapi ia adalah denda.

997
01:17:59,290 --> 01:18:02,690
Jika (kini-> kiri! = NULL),

998
01:18:02,690 --> 01:18:14,310
dan kita akan memasukkan kiri ke dalam senarai dikaitkan kami,

999
01:18:14,310 --> 01:18:19,700
dan yang harus.

1000
01:18:19,700 --> 01:18:22,670
Kami melelar - selagi kita mempunyai sesuatu dalam senarai kami,

1001
01:18:22,670 --> 01:18:26,640
kita mempunyai satu lagi nod untuk melihat.

1002
01:18:26,640 --> 01:18:28,920
Jadi kita melihat nod tersebut,

1003
01:18:28,920 --> 01:18:31,390
kita memajukan senarai kami untuk satu depan.

1004
01:18:31,390 --> 01:18:34,060
Jika nod tersebut adalah nilai yang kita cari, kita boleh kembali benar.

1005
01:18:34,060 --> 01:18:37,640
Lagi memasukkan kedua-dua subtrees kiri dan kanan kita,

1006
01:18:37,640 --> 01:18:40,510
selagi mereka tidak batal, ke dalam senarai kami

1007
01:18:40,510 --> 01:18:43,120
supaya kita tidak dapat dielakkan pergi ke atas mereka.

1008
01:18:43,120 --> 01:18:45,160
Jadi, jika mereka tidak batal,

1009
01:18:45,160 --> 01:18:47,950
jika penunjuk akar kita menunjuk kepada dua perkara,

1010
01:18:47,950 --> 01:18:51,670
maka pada mulanya, kita ditarik sesuatu supaya senarai kami akhirnya menjadi batal.

1011
01:18:51,670 --> 01:18:56,890
Dan kemudian kita meletakkan dua perkara kembali, jadi kini senarai kami adalah saiz 2.

1012
01:18:56,890 --> 01:19:00,030
Kemudian kita pergi ke gelung kembali dan kami hanya akan tarik,

1013
01:19:00,030 --> 01:19:04,250
katakan, penunjuk kiri nod akar kita.

1014
01:19:04,250 --> 01:19:07,730
Dan yang hanya akan menyimpan berlaku, kita akan berakhir sehingga menggelung ke atas segala-galanya.

1015
01:19:07,730 --> 01:19:11,280
>> Perhatikan bahawa ini adalah jauh lebih rumit

1016
01:19:11,280 --> 01:19:14,160
dalam penyelesaian rekursi.

1017
01:19:14,160 --> 01:19:17,260
Dan saya telah berkata beberapa kali

1018
01:19:17,260 --> 01:19:25,120
bahawa penyelesaian rekursi biasanya mempunyai banyak persamaan dengan lelaran penyelesaian.

1019
01:19:25,120 --> 01:19:30,820
Berikut ini adalah apa penyelesaian rekursi melakukan.

1020
01:19:30,820 --> 01:19:36,740
Satu-satunya perubahan adalah bahawa bukannya tersirat menggunakan timbunan, timbunan program,

1021
01:19:36,740 --> 01:19:40,840
sebagai cara anda mengesan nodus apa yang anda masih perlu untuk melawat,

1022
01:19:40,840 --> 01:19:45,430
sekarang anda perlu jelas menggunakan senarai berpaut.

1023
01:19:45,430 --> 01:19:49,070
Dalam kedua-dua kes anda mengesan apa nod masih perlu dikunjungi.

1024
01:19:49,070 --> 01:19:51,790
Dalam kes rekursi ia hanya mudah kerana timbunan

1025
01:19:51,790 --> 01:19:57,100
dilaksanakan untuk anda sebagai timbunan program.

1026
01:19:57,100 --> 01:19:59,550
Perhatikan bahawa senarai ini yang berkaitan, ia adalah timbunan.

1027
01:19:59,550 --> 01:20:01,580
Apa sahaja yang kita hanya meletakkan pada timbunan

1028
01:20:01,580 --> 01:20:09,960
segera apa yang kita akan tarik luar tindanan untuk melawat seterusnya.

1029
01:20:09,960 --> 01:20:14,380
Kami kehabisan masa, tetapi apa-apa soalan?

1030
01:20:14,380 --> 01:20:23,530
[Pelajar, difahami]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Jadi, jika kita mempunyai senarai berpaut kami,

1032
01:20:27,790 --> 01:20:30,150
semasa akan untuk menunjukkan kepada lelaki ini,

1033
01:20:30,150 --> 01:20:34,690
dan kini kami hanya memajukan senarai berpaut kami untuk memberi tumpuan kepada lelaki ini.

1034
01:20:34,690 --> 01:20:44,200
Kami menyeberangi lebih senarai dikaitkan dalam barisan itu.

1035
01:20:44,200 --> 01:20:51,200
Dan kemudian saya rasa kita harus membebaskan senarai berpaut kami dan barangan

1036
01:20:51,200 --> 01:20:53,880
sekali sebelum kembali benar atau palsu, kita perlu

1037
01:20:53,880 --> 01:20:57,360
melelar lebih dikaitkan senarai kami dan sentiasa turun di sini, saya rasa,

1038
01:20:57,360 --> 01:21:03,900
jika hak kita kini tidak sama dengan, tambah, jadi sekarang kita mahu untuk membebaskan

1039
01:21:03,900 --> 01:21:09,600
kini kerana, dengan baik, adakah kita benar-benar lupa tentang senarai? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Jadi itulah apa yang kami mahu lakukan di sini.

1041
01:21:12,880 --> 01:21:16,730
Mana penunjuk?

1042
01:21:16,730 --> 01:21:23,320
Cur ketika itu - kita mahu ke senarai struct * 10 bersamaan senarai seterusnya.

1043
01:21:23,320 --> 01:21:29,240
Senarai percuma, senarai = temp.

1044
01:21:29,240 --> 01:21:32,820
Dan dalam kes di mana kita kembali benar, kita tidak perlu untuk melelar

1045
01:21:32,820 --> 01:21:37,050
atas baki senarai berpaut kami membebaskan perkara.

1046
01:21:37,050 --> 01:21:39,700
Perkara yang baik tentang penyelesaian rekursi membebaskan perkara

1047
01:21:39,700 --> 01:21:44,930
hanya bermakna pop factorings off tindanan yang akan berlaku untuk anda.

1048
01:21:44,930 --> 01:21:50,720
Jadi kami telah pergi dari sesuatu yang seperti 3 baris kod keras untuk berfikir tentang

1049
01:21:50,720 --> 01:21:57,520
kepada sesuatu yang jauh lebih banyak sukar untuk berfikir tentang baris kod.

1050
01:21:57,520 --> 01:22:00,620
Apa-apa lagi soalan?

1051
01:22:00,620 --> 01:22:08,760
Semua hak. Kami baik. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]