1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Sehemu ya 7: Zaidi Starehe]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Chuo Kikuu cha Harvard]

3
00:00:05,090 --> 00:00:07,930
[Hii ni CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Wote haki. Hivyo kama nilivyosema katika barua pepe yangu,

5
00:00:10,110 --> 00:00:14,060
hii itakuwa ni sehemu ya binary-mti-intensive.

6
00:00:14,060 --> 00:00:16,820
Lakini kuna si kwamba maswali mengi.

7
00:00:16,820 --> 00:00:18,920
Hivyo sisi ni kwenda kujaribu na kusogea nje ya kila swali

8
00:00:18,920 --> 00:00:25,430
na kuingia kwa undani chungu ya njia zote bora ya kufanya mambo.

9
00:00:25,430 --> 00:00:31,200
Hivyo haki ya mwanzo, sisi kupitia michoro ya sampuli ya miti binary na mambo ya ajabu.

10
00:00:31,200 --> 00:00:35,970
Hivyo hapa, "Kumbuka kwamba mti binary ina nodes sawa na wale wa orodha wanaohusishwa,

11
00:00:35,970 --> 00:00:38,150
isipokuwa badala ya pointer moja kuna mawili: moja kwa ajili ya 'mtoto' kushoto

12
00:00:38,150 --> 00:00:41,950
na moja kwa ajili ya 'mtoto' haki. "

13
00:00:41,950 --> 00:00:45,630
Hivyo mti binary ni kama orodha zilizounganishwa,

14
00:00:45,630 --> 00:00:47,910
ila struct ataenda kuwa na kuyatumia mbili.

15
00:00:47,910 --> 00:00:51,390
Kuna trinary miti, ambayo ni kwenda na kuyatumia tatu,

16
00:00:51,390 --> 00:00:56,540
kuna N-ary miti, ambayo tu pointer generic

17
00:00:56,540 --> 00:01:00,320
kwamba wewe kisha kuwa na malloc kuwa kubwa ya kutosha na

18
00:01:00,320 --> 00:01:04,840
kutosha kuyatumia kwa watoto wote iwezekanavyo.

19
00:01:04,840 --> 00:01:08,200
Hivyo binary mti hutokea tu kuwa na idadi ya mara kwa mara ya mbili.

20
00:01:08,200 --> 00:01:11,260
Kama unataka, unaweza kutoa orodha zilizounganishwa kama mti unary,

21
00:01:11,260 --> 00:01:15,360
lakini sidhani mtu yeyote anaiita hiyo.

22
00:01:15,360 --> 00:01:18,060
"Chora mchoro masanduku-na-mishale ya nodi binary mti

23
00:01:18,060 --> 00:01:24,110
zenye Nate favorite idadi, 7, ambapo kila mtoto ni pointer null. "

24
00:01:24,110 --> 00:01:27,780
Hivyo iPad mode.

25
00:01:27,780 --> 00:01:30,280
>> Ni kwenda kuwa pretty moja kwa moja.

26
00:01:30,280 --> 00:01:36,150
Sisi ni kwenda tu kuwa na node, mimi itabidi kuteka ni kama mraba.

27
00:01:36,150 --> 00:01:38,730
Na mimi itabidi kuteka maadili katika hapa.

28
00:01:38,730 --> 00:01:41,090
Hivyo thamani kwenda katika hapa,

29
00:01:41,090 --> 00:01:44,770
na kisha chini hapa tutaweza kuwa pointer wa kushoto juu ya kushoto na kulia pointer juu ya haki.

30
00:01:44,770 --> 00:01:50,430
Na ni mengi sana na hivyo mkataba kuiita kushoto na kulia, majina pointer.

31
00:01:50,430 --> 00:01:52,460
Yote haya ni kwenda kuwa null.

32
00:01:52,460 --> 00:01:57,870
Hiyo tu kuwa null, na kwamba itakuwa tu kuwa null.

33
00:01:57,870 --> 00:02:03,630
Sawa. Hivyo nyuma kwa hapa.

34
00:02:03,630 --> 00:02:05,700
"Pamoja na orodha wanaohusishwa, sisi tu alikuwa na kuhifadhi pointer

35
00:02:05,700 --> 00:02:09,639
na nodi ya kwanza katika orodha ili kukumbuka nzima wanaohusishwa orodha, au orodha nzima.

36
00:02:09,639 --> 00:02:11,650
Aidha, pamoja na miti, sisi tu kuhifadhi pointer

37
00:02:11,650 --> 00:02:13,420
na nodi ya moja ili kukumbuka mti mzima.

38
00:02:13,420 --> 00:02:15,980
Nodi Hii ni calle 'mzizi' ya mti.

39
00:02:15,980 --> 00:02:18,320
Kujenga juu ya mchoro wako kutoka kabla au kuteka moja mpya

40
00:02:18,320 --> 00:02:21,690
vile kwamba una maelezo ya masanduku-na-mishale ya mti binary

41
00:02:21,690 --> 00:02:25,730
na thamani ya 7, kisha 3 katika kushoto,

42
00:02:25,730 --> 00:02:32,760
kisha 9 juu ya haki, na kisha 6 juu ya haki ya 3. "

43
00:02:32,760 --> 00:02:34,810
Hebu angalia kama naweza kukumbuka yote ya kwamba katika kichwa changu.

44
00:02:34,810 --> 00:02:37,670
Hivyo hii ni kwenda kuwa mizizi yetu hapa.

45
00:02:37,670 --> 00:02:41,600
Tutaweza kuwa na baadhi ya pointer mahali fulani, kitu ambacho Tutamwita mizizi,

46
00:02:41,600 --> 00:02:45,140
na ni akizungumzia guy.

47
00:02:45,140 --> 00:02:48,490
Sasa kufanya nodi mpya,

48
00:02:48,490 --> 00:02:52,870
nini tuna, 3 upande wa kushoto?

49
00:02:52,870 --> 00:02:57,140
Hivyo nodi mpya na 3, na ni awali pointi null.

50
00:02:57,140 --> 00:02:59,190
Mimi itabidi kuweka N.

51
00:02:59,190 --> 00:03:02,250
Sasa tunataka kufanya kwamba kwenda upande wa kushoto wa 7.

52
00:03:02,250 --> 00:03:06,840
Hivyo sisi kubadili hili pointer sasa kumweka kwa guy.

53
00:03:06,840 --> 00:03:12,420
Na sisi kufanya hivyo. Tunataka 9 ya juu hapa

54
00:03:12,420 --> 00:03:14,620
ambayo awali tu anasema null.

55
00:03:14,620 --> 00:03:19,600
Sisi ni kwenda kubadilisha hii pointer, hatua kwa 9,

56
00:03:19,600 --> 00:03:23,310
na sasa tunataka kuweka 6 na haki ya 3.

57
00:03:23,310 --> 00:03:32,170
Hivyo ni kwenda - kufanya 6.

58
00:03:32,170 --> 00:03:34,310
Na kwamba guy nitawaelekezeni huko.

59
00:03:34,310 --> 00:03:38,320
Sawa. Basi hiyo ni wote inauliza tufanye.

60
00:03:38,320 --> 00:03:42,770
>> Sasa hebu kwenda juu ya baadhi ya istilahi.

61
00:03:42,770 --> 00:03:46,690
Sisi tayari kuongelea kuhusu jinsi mizizi ya mti ni nodi ya juu-wengi katika mti.

62
00:03:46,690 --> 00:03:54,720
moja zenye 7. nodes chini ya mti wanaitwa majani.

63
00:03:54,720 --> 00:04:01,240
Yoyote ambayo nodi tu ana null kama watoto wake ni jani.

64
00:04:01,240 --> 00:04:03,680
Hivyo inawezekana, kama binary yetu ni mti tu nodi moja,

65
00:04:03,680 --> 00:04:10,130
kwamba mti ni jani, na hiyo ni yake.

66
00:04:10,130 --> 00:04:12,060
"'Urefu' wa mti ni idadi ya humle una kufanya

67
00:04:12,060 --> 00:04:16,620
kupata kutoka juu na majani. "

68
00:04:16,620 --> 00:04:18,640
Tutaweza kupata ndani, katika pili, tofauti

69
00:04:18,640 --> 00:04:21,940
kati ya uwiano na unbalanced binary miti,

70
00:04:21,940 --> 00:04:29,470
lakini kwa sasa, urefu wa jumla ya mti huu

71
00:04:29,470 --> 00:04:34,520
Naweza kusema ni 3, ingawa kama wewe kuhesabu idadi ya humle

72
00:04:34,520 --> 00:04:39,710
una kufanya ili kupata 9, basi ni kweli tu urefu wa 2.

73
00:04:39,710 --> 00:04:43,340
Sasa hivi ni unbalanced binary mti,

74
00:04:43,340 --> 00:04:49,840
lakini tutaweza aliyesema kuhusu uwiano wakati anapata kuwa muhimu.

75
00:04:49,840 --> 00:04:52,040
Hivyo sasa tunaweza kuongea kuhusu nodes katika mti katika suala

76
00:04:52,040 --> 00:04:54,700
jamaa na nodes nyingine katika mti.

77
00:04:54,700 --> 00:04:59,730
Hivyo basi, tuna wazazi, watoto, ndugu, mababu, na wazao.

78
00:04:59,730 --> 00:05:05,650
Wao ni pretty akili ya kawaida, maana yake.

79
00:05:05,650 --> 00:05:09,610
Kama sisi kuuliza - wazazi wake.

80
00:05:09,610 --> 00:05:12,830
Hivyo kile ni mzazi wa 3?

81
00:05:12,830 --> 00:05:16,090
[Wanafunzi] 7. >> Yeah. mzazi ni kwenda tu kuwa kile pointi na wewe.

82
00:05:16,090 --> 00:05:20,510
Kisha nini ni watoto wa 7?

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

84
00:05:23,860 --> 00:05:26,460
Ona kwamba "watoto" likiwa na maana ya watoto,

85
00:05:26,460 --> 00:05:31,010
hivyo 6 bila kuomba, kwa sababu ni kama mjukuu.

86
00:05:31,010 --> 00:05:35,540
Lakini basi kama sisi kwenda wazao, ili kile ni wazao wa 7?

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

88
00:05:37,500 --> 00:05:42,330
wazao wa nodi mzizi ni kwenda kuwa kila kitu katika mti,

89
00:05:42,330 --> 00:05:47,950
isipokuwa labda nodi mizizi yenyewe, kama huna kufikiria kwamba mtoto.

90
00:05:47,950 --> 00:05:50,750
Na hatimaye, mababu, hivyo ni kinyume mwelekeo.

91
00:05:50,750 --> 00:05:55,740
Kwa hiyo kile ni mababu wa 6?

92
00:05:55,740 --> 00:05:58,920
[Wanafunzi] 3 na 7. >> Yeah. 9 si pamoja.

93
00:05:58,920 --> 00:06:02,520
Ni tu moja kwa moja ukoo nyuma mizizi

94
00:06:02,520 --> 00:06:13,230
ni kwenda kuwa baba zenu.

95
00:06:13,230 --> 00:06:16,300
>> "Sisi tunasema kwamba mti binary 'kuamuru' kama kwa kila nodi katika mti,

96
00:06:16,300 --> 00:06:19,530
yote ya wazao wake kwa upande wa kushoto na maadili mdogo

97
00:06:19,530 --> 00:06:22,890
na wote wa wadogo juu ya haki na maadili zaidi.

98
00:06:22,890 --> 00:06:27,060
Kwa mfano, mti hapo juu ni amri lakini siyo tu inawezekana kuamuru utaratibu. "

99
00:06:27,060 --> 00:06:30,180
Kabla ya sisi kupata kwamba,

100
00:06:30,180 --> 00:06:36,420
kuamuru mti binary pia anajulikana kama mti binary tafuta.

101
00:06:36,420 --> 00:06:38,660
Hapa sisi kutokea kwa kuwa kuiita kuamuru binary mti,

102
00:06:38,660 --> 00:06:41,850
lakini sijawahi kusikia ni kuitwa kuamuru binary mti kabla,

103
00:06:41,850 --> 00:06:46,650
na juu ya chemsha bongo sisi ni zaidi ya uwezekano wa kuweka binary tafuta mti.

104
00:06:46,650 --> 00:06:49,250
Wao ni moja na sawa,

105
00:06:49,250 --> 00:06:54,580
na ni muhimu wewe kutambua tofauti kati ya mti na kisha binary mti tafuta.

106
00:06:54,580 --> 00:06:58,830
mti binary ni mti pointi kwa mambo mawili.

107
00:06:58,830 --> 00:07:02,120
Nodi ya kila pointi kwa mambo mawili.

108
00:07:02,120 --> 00:07:06,310
Hakuna hoja kuhusu maadili ambayo inaelekeza katika.

109
00:07:06,310 --> 00:07:11,370
Hivyo kama zaidi hapa, tangu ni binary tafuta mti,

110
00:07:11,370 --> 00:07:14,030
tunajua kwamba kama sisi kwenda kushoto ya 7,

111
00:07:14,030 --> 00:07:16,670
basi wote wa maadili ambayo tunaweza pengine kufikia

112
00:07:16,670 --> 00:07:19,310
kwa kwenda kushoto ya 7 na kuwa chini ya 7.

113
00:07:19,310 --> 00:07:24,070
Ona kwamba maadili yote chini ya 7 ni 3 na 6.

114
00:07:24,070 --> 00:07:26,040
Wale wote ni wa kushoto wa 7.

115
00:07:26,040 --> 00:07:29,020
Kama sisi kwenda kulia wa 7, kila kitu kina kuwa kubwa kuliko 7,

116
00:07:29,020 --> 00:07:33,220
hivyo 9 ni haki ya 7, hivyo sisi ni nzuri.

117
00:07:33,220 --> 00:07:36,150
Hii si kesi kwa mti binary,

118
00:07:36,150 --> 00:07:40,020
kwa mti wa kawaida kisha tunaweza tu 3 saa ya juu, 7 wa kushoto,

119
00:07:40,020 --> 00:07:47,630
9 ya kushoto ya 7; hakuna kuagiza maadili wowote.

120
00:07:47,630 --> 00:07:56,140
Sasa, sisi si kweli kufanya hivyo kwa sababu ni tedious na unnecessary,

121
00:07:56,140 --> 00:07:59,400
lakini "kujaribu kuteka kama miti mingi kuamuru kama unaweza kufikiri ya

122
00:07:59,400 --> 00:08:01,900
kutumia namba 7, 3, 9, na 6.

123
00:08:01,900 --> 00:08:06,800
Ngapi mipangilio tofauti ni huko? Je, ni urefu wa kila mmoja? "

124
00:08:06,800 --> 00:08:10,480
>> Tutaweza kufanya wanandoa, lakini wazo kuu ni,

125
00:08:10,480 --> 00:08:16,530
hii ni katika hakuna njia ya uwakilishi wa kipekee wa mti binary zenye maadili haya.

126
00:08:16,530 --> 00:08:22,760
Wote tunahitaji ni baadhi mti binary kwamba ina 7, 3, 6, na 9.

127
00:08:22,760 --> 00:08:25,960
Mwingine iwezekanavyo moja halali itakuwa ni mzizi 3,

128
00:08:25,960 --> 00:08:30,260
kwenda kushoto na ni 6, kwenda kushoto na ni 7,

129
00:08:30,260 --> 00:08:32,730
kwenda kushoto na ni 9.

130
00:08:32,730 --> 00:08:36,169
Hiyo ni kikamilifu halali binary tafuta mti.

131
00:08:36,169 --> 00:08:39,570
Ni hayasaidii sana, kwa sababu ni kama tu orodha wanaohusishwa

132
00:08:39,570 --> 00:08:43,750
na wote wa kuyatumia haya ni null.

133
00:08:43,750 --> 00:08:48,900
Lakini ni mti halali. Yeah?

134
00:08:48,900 --> 00:08:51,310
[Mwanafunzi] Je, si maadili kuwa mkuu juu ya haki?

135
00:08:51,310 --> 00:08:56,700
Au ni hii -? >> Haya mimi maana ya kwenda njia nyingine.

136
00:08:56,700 --> 00:09:00,960
Kuna pia - yeah, hebu kubadili hilo.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Nzuri samaki.

138
00:09:07,770 --> 00:09:11,730
Bado ina kutii kile tafuta binary mti zinatakiwa kufanya.

139
00:09:11,730 --> 00:09:15,650
Kwa hiyo kila kitu kwa upande wa kushoto ina kuwa chini ya nodi wowote.

140
00:09:15,650 --> 00:09:23,180
Tunaweza tu hoja, kusema, hii 6 na kuiweka hapa.

141
00:09:23,180 --> 00:09:26,880
Hapana, hatuwezi. Kwa nini mimi kuendelea kufanya hivyo?

142
00:09:26,880 --> 00:09:35,350
Hebu kufanya - hapa ni 6, hapa ni 7, 6 pointi 3.

143
00:09:35,350 --> 00:09:39,290
Hii bado ni halali binary tafuta mti.

144
00:09:39,290 --> 00:09:49,260
Je, ni makosa kama mimi - hebu angalia kama naweza kuja na mpangilio.

145
00:09:49,260 --> 00:09:52,280
Yeah, okay. Hiyo ni nini kibaya na mti?

146
00:09:52,280 --> 00:10:08,920
Mimi nadhani nimekuwa tayari kupeni dokezo kwamba kuna kitu kibaya.

147
00:10:08,920 --> 00:10:14,430
Kwa nini mimi kuendelea kufanya hivyo?

148
00:10:14,430 --> 00:10:18,510
Sawa. Hii inaonekana busara.

149
00:10:18,510 --> 00:10:22,590
Kama sisi kuangalia kila node, kama 7, kisha ya kushoto ya 7 ni 3.

150
00:10:22,590 --> 00:10:24,960
Hivyo tuna 3, jambo haki ya 3 ni 6.

151
00:10:24,960 --> 00:10:27,750
Na kama ukiangalia 6, jambo haki ya 6 ni 9.

152
00:10:27,750 --> 00:10:30,910
Hivyo kwa nini hii si halali binary tafuta mti?

153
00:10:30,910 --> 00:10:36,330
[Wanafunzi] 9 bado ni ya kushoto ya 7. >> Yeah.

154
00:10:36,330 --> 00:10:43,710
Ni lazima kuwa kweli kwamba wote maadili unaweza uwezekano wa kufikia kwa kwenda kushoto wa 7 ni chini ya 7.

155
00:10:43,710 --> 00:10:49,120
Kama sisi kwenda kushoto ya 7, tunapata 3 na bado tunaweza kupata 6,

156
00:10:49,120 --> 00:10:52,520
bado tunaweza kupata 9, lakini kwa kuwa wamekwenda chini ya 7,

157
00:10:52,520 --> 00:10:55,070
hatupaswi kuwa na uwezo wa kupata idadi hiyo ni kubwa kuliko 7.

158
00:10:55,070 --> 00:10:59,830
Hivyo hii si halali binary tafuta mti.

159
00:10:59,830 --> 00:11:02,330
>> Ndugu yangu kweli alikuwa swali mahojiano

160
00:11:02,330 --> 00:11:07,760
kwamba alikuwa kimsingi hii, tu code up kitu kuhalalisha

161
00:11:07,760 --> 00:11:10,500
kama mti ni binary tafuta mti,

162
00:11:10,500 --> 00:11:13,580
na hivyo jambo la kwanza alivyofanya mara tu kuangalia kuona

163
00:11:13,580 --> 00:11:17,020
ikiwa kushoto na kulia ni sahihi, na kisha iterate chini huko.

164
00:11:17,020 --> 00:11:19,700
Lakini huwezi kufanya hivyo; una kuweka wimbo

165
00:11:19,700 --> 00:11:22,550
ukweli kwamba sasa kwamba mimi tumeenda kushoto ya 7,

166
00:11:22,550 --> 00:11:26,340
kila kitu katika hii subtree lazima kiwe chini ya 7.

167
00:11:26,340 --> 00:11:28,430
algorithm sahihi inahitaji kuweka wimbo

168
00:11:28,430 --> 00:11:35,970
ya mipaka ya maadili inaweza uwezekano kuanguka in

169
00:11:35,970 --> 00:11:38,360
Sisi si kwenda kwa njia ya wote.

170
00:11:38,360 --> 00:11:41,630
Kuna ni nzuri upprepning uhusiano,

171
00:11:41,630 --> 00:11:44,810
ingawa sisi si wamezipata kwa wale, au sisi si kupata wale,

172
00:11:44,810 --> 00:11:47,030
kufafanua jinsi kuna kweli ni.

173
00:11:47,030 --> 00:11:53,180
Hivyo kuna 14 ya yao.

174
00:11:53,180 --> 00:11:56,020
wazo la jinsi gani kufanya hivyo mathematically ni kama,

175
00:11:56,020 --> 00:11:59,770
unaweza kuchukua yoyote moja kuwa nodi mizizi,

176
00:11:59,770 --> 00:12:03,160
na kisha kama mimi pick 7 kuwa mizizi nodi,

177
00:12:03,160 --> 00:12:08,150
basi kuna, kusema, baadhi idadi ambayo yanaweza kwenda kuwa nodi wangu wa kushoto,

178
00:12:08,150 --> 00:12:10,440
na kuna baadhi ya idadi ambayo inaweza kuwa nodi wangu wa kulia,

179
00:12:10,440 --> 00:12:15,090
lakini kama mimi n idadi jumla, basi kiasi kwamba anaweza kwenda kushoto

180
00:12:15,090 --> 00:12:18,820
pamoja na kiasi cha kwamba anaweza kwenda kulia ni n - 1.

181
00:12:18,820 --> 00:12:26,130
Hivyo idadi iliyobaki, wanatakiwa kuwa na uwezo wa kwenda aidha kwa upande wa kushoto au kulia.

182
00:12:26,130 --> 00:12:31,580
Inaonekana vigumu kuwa, kama mimi kuweka 3 kwanza kisha kila kitu ina kwenda kushoto,

183
00:12:31,580 --> 00:12:35,080
lakini kama mimi kuweka 7, basi baadhi ya mambo yanaweza kwenda kushoto na baadhi ya mambo yanaweza kwenda kulia.

184
00:12:35,080 --> 00:12:39,570
Na kwa ''3 kwanza mimi maana kila kitu wanaweza kwenda kulia.

185
00:12:39,570 --> 00:12:42,350
Ni kweli, wewe tu na kufikiri juu yake kama,

186
00:12:42,350 --> 00:12:47,980
mambo mangapi unaweza kwenda kwenye ngazi ya pili ya mti.

187
00:12:47,980 --> 00:12:50,420
Na inakuja nje kuwa 14; au unaweza kuteka wote,

188
00:12:50,420 --> 00:12:54,650
na kisha utapata 14.

189
00:12:54,650 --> 00:13:01,120
>> Tukirudi hapa,

190
00:13:01,120 --> 00:13:03,510
"Aliamrisha miti binary ni baridi kwa sababu tunaweza kutafuta njia yao

191
00:13:03,510 --> 00:13:06,910
katika njia sawa sana kutafuta juu ya safu Iliyopangwa.

192
00:13:06,910 --> 00:13:10,120
Kwa kufanya hivyo, sisi kuanza katika mizizi na kazi njia yetu chini ya mti

193
00:13:10,120 --> 00:13:13,440
kuelekea majani, kuangalia maadili ya kila nodi dhidi ya maadili sisi ni kwa ajili ya kutafuta.

194
00:13:13,440 --> 00:13:15,810
Kama thamani ya nodi ya sasa ni chini ya thamani sisi ni kuangalia kwa,

195
00:13:15,810 --> 00:13:18,050
kwenda karibu na mtoto nodi wa kulia.

196
00:13:18,050 --> 00:13:20,030
Vinginevyo, unaweza kwenda kwa mtoto nodi la kushoto.

197
00:13:20,030 --> 00:13:22,800
Katika hatua nyingine, wewe utakuwa aidha kupata thamani wewe ni kuangalia kwa, au utasikia kukimbia katika null,

198
00:13:22,800 --> 00:13:28,520
kuonyesha thamani si katika mti. "

199
00:13:28,520 --> 00:13:32,450
Nina redraw mti tulikuwa kabla; kwamba itabidi kuchukua pili.

200
00:13:32,450 --> 00:13:38,280
Lakini tunataka kuangalia juu kama 6, 10, na 1 ni katika mti.

201
00:13:38,280 --> 00:13:49,180
Hivyo ilikuwa ni nini, 7, 9, 3, 6. Sawa.

202
00:13:49,180 --> 00:13:52,730
idadi unataka kuangalia juu, tunataka kuangalia up 6.

203
00:13:52,730 --> 00:13:55,440
Jinsi gani hii algorithm kazi?

204
00:13:55,440 --> 00:14:03,040
Naam, sisi pia kuwa baadhi ya pointer mizizi ya mti wetu.

205
00:14:03,040 --> 00:14:12,460
Na tunataka kwenda kwa mizizi na kusema, hii ni sawa na thamani thamani sisi ni kwa ajili ya kutafuta?

206
00:14:12,460 --> 00:14:15,000
Hivyo sisi ni kuangalia kwa 6, hivyo si sawa.

207
00:14:15,000 --> 00:14:20,140
Hivyo sisi kuendelea, na sasa tunasema, sawa, hivyo ni chini ya 6 7.

208
00:14:20,140 --> 00:14:23,940
Je inamaanisha tunataka kwenda upande wa kushoto, au kufanya sisi unataka kwenda upande wa kulia?

209
00:14:23,940 --> 00:14:27,340
[Mwanafunzi] kushoto. >> Yeah.

210
00:14:27,340 --> 00:14:33,340
Ni kwa kiasi kikubwa rahisi, wote una kufanya ni kuteka moja iwezekanavyo nodi ya mti

211
00:14:33,340 --> 00:14:37,760
na kisha wewe don't - badala ya kujaribu kufikiri katika kichwa yako,

212
00:14:37,760 --> 00:14:40,020
sawa, kama ni kidogo, je, mimi kwenda kushoto au kwenda kulia,

213
00:14:40,020 --> 00:14:43,030
kuangalia tu picha hii, ni wazi kwamba mimi kwenda kushoto

214
00:14:43,030 --> 00:14:47,700
ikiwa nodi hii ni mkubwa kuliko thamani ya kuwa mimi nina kuangalia kwa.

215
00:14:47,700 --> 00:14:52,600
Hivyo wewe kwenda kushoto, sasa mimi nina saa 3.

216
00:14:52,600 --> 00:14:57,770
Nataka - 3 ni chini ya thamani nina kuangalia kwa, ambayo ni 6.

217
00:14:57,770 --> 00:15:03,420
Hivyo sisi kwenda kulia, na sasa mimi kuishia katika 6,

218
00:15:03,420 --> 00:15:07,380
ambayo ni thamani nina kuangalia kwa, hivyo mimi kurudi kweli.

219
00:15:07,380 --> 00:15:15,760
thamani ijayo mimi naenda kwa kuangalia ni 10.

220
00:15:15,760 --> 00:15:23,230
Sawa. Hivyo 10, sasa, ni kwenda - kukatwa kwamba - kwenda kufuata mizizi.

221
00:15:23,230 --> 00:15:27,670
Sasa, 10 ni kwenda kuwa mkuu zaidi kuliko 7, hivyo nataka kuangalia kwa haki.

222
00:15:27,670 --> 00:15:31,660
Mimi naenda kuja hapa, 10 ni kwenda kuwa mkuu zaidi kuliko 9,

223
00:15:31,660 --> 00:15:34,520
hivyo mimi nina kwenda unataka kuangalia kwa haki.

224
00:15:34,520 --> 00:15:42,100
Mimi kuja hapa, lakini zaidi ya hapa sasa mimi nina katika null.

225
00:15:42,100 --> 00:15:44,170
Nifanye nini kama mimi hit null?

226
00:15:44,170 --> 00:15:47,440
[Mwanafunzi] Kurudi uongo? >> Yeah. Sikuweza kupata 10.

227
00:15:47,440 --> 00:15:49,800
1 ni kwenda kuwa kesi karibu kufanana,

228
00:15:49,800 --> 00:15:51,950
isipokuwa tu kwenda kuwa flipped; badala ya kuangalia

229
00:15:51,950 --> 00:15:56,540
chini upande wa kulia, mimi nina kwenda kuangalia chini upande wa kushoto.

230
00:15:56,540 --> 00:16:00,430
>> Sasa nadhani sisi kweli kupata code.

231
00:16:00,430 --> 00:16:04,070
Hapa ni wapi - kufungua appliance CS50 na navigate njia yako huko,

232
00:16:04,070 --> 00:16:07,010
lakini pia unaweza tu kufanya hivyo katika nafasi.

233
00:16:07,010 --> 00:16:09,170
Ni pengine bora ya kufanya hivyo katika nafasi,

234
00:16:09,170 --> 00:16:13,760
kwa sababu tunaweza kufanya kazi katika nafasi.

235
00:16:13,760 --> 00:16:19,170
"Kwanza tutaweza haja aina mpya ufafanuzi kwa nodi binary mti zenye maadili int.

236
00:16:19,170 --> 00:16:21,400
Kutumia boilerplate typedef chini,

237
00:16:21,400 --> 00:16:24,510
kuunda aina mpya ya ufafanuzi kwa nodi katika mti binary.

238
00:16:24,510 --> 00:16:27,930
Kama wewe kukwama. . . "Blah, blah, blah Sawa..

239
00:16:27,930 --> 00:16:30,380
Hivyo basi, tulenge boilerplate hapa,

240
00:16:30,380 --> 00:16:41,630
typedef struct nodi, na nodi. Yeah, okay.

241
00:16:41,630 --> 00:16:44,270
Kwa hiyo kile ni mashamba tunakwenda unataka katika nodi zetu?

242
00:16:44,270 --> 00:16:46,520
[Mwanafunzi] Int na kisha kuyatumia mbili?

243
00:16:46,520 --> 00:16:49,700
>> Int thamani, kuyatumia mbili? Je, mimi kuandika kuyatumia?

244
00:16:49,700 --> 00:16:58,440
[Mwanafunzi] Struct. >> Mimi lazima zoom in Yeah, hivyo struct nodi * kushoto,

245
00:16:58,440 --> 00:17:01,320
na struct nodi * haki.

246
00:17:01,320 --> 00:17:03,460
Na kumbuka mjadala toka mara ya mwisho,

247
00:17:03,460 --> 00:17:15,290
kwamba hii haina mantiki, hii haina mantiki,

248
00:17:15,290 --> 00:17:18,270
hii haina mantiki.

249
00:17:18,270 --> 00:17:25,000
Unahitaji kila kitu huko ili kufafanua hili struct ya kujirudia.

250
00:17:25,000 --> 00:17:27,970
Sawa, hivyo kwamba ni nini mti wetu ni kwenda kuangalia kama.

251
00:17:27,970 --> 00:17:37,670
Kama sisi alifanya mti trinary, basi nodi ili kuangalia kama B2 B1, struct nodi * B3,

252
00:17:37,670 --> 00:17:43,470
ambapo b ni tawi - kweli, nimekuwa zaidi waliposikia kushoto, katikati, kulia, lakini chochote.

253
00:17:43,470 --> 00:17:55,610
Sisi tu huduma kuhusu binary, hivyo haki, kushoto.

254
00:17:55,610 --> 00:17:59,110
"Sasa kutangaza kimataifa nodi * variable kwa mizizi ya mti."

255
00:17:59,110 --> 00:18:01,510
Hivyo sisi hamtaweza kufanya hivyo.

256
00:18:01,510 --> 00:18:08,950
Ili kufanya mambo kidogo vigumu zaidi na zaidi ya jumla,

257
00:18:08,950 --> 00:18:11,570
hatutakuwa na kimataifa nodi kutofautiana.

258
00:18:11,570 --> 00:18:16,710
Badala yake, katika kuu sisi kutangaza mambo yetu yote ya nodi,

259
00:18:16,710 --> 00:18:20,500
na hiyo ina maana kwamba chini, wakati sisi kuanza mbio

260
00:18:20,500 --> 00:18:23,130
yetu ina kazi na Insert yetu kazi,

261
00:18:23,130 --> 00:18:27,410
badala ya ina yetu inafanya kazi tu kwa kutumia hii ya kimataifa nodi variable,

262
00:18:27,410 --> 00:18:34,280
sisi itawabidi kuchukua kama hoja mti kwamba tunataka ni mchakato.

263
00:18:34,280 --> 00:18:36,650
Baada ya variable kimataifa ilitakiwa kufanya mambo rahisi.

264
00:18:36,650 --> 00:18:42,310
Sisi ni kwenda kufanya mambo magumu.

265
00:18:42,310 --> 00:18:51,210
Sasa kuchukua dakika au hivyo tu kufanya jambo la aina hii,

266
00:18:51,210 --> 00:18:57,690
ambapo ndani ya kuu unataka kujenga mti huu, na kwamba wote unataka kufanya.

267
00:18:57,690 --> 00:19:04,530
Jaribu na kujenga mti huu katika kazi yako kuu.

268
00:19:42,760 --> 00:19:47,610
>> Sawa. Hivyo hawana hata kuwa yalijengwa mti njia nzima bado.

269
00:19:47,610 --> 00:19:49,840
Lakini mtu yeyote kuwa kitu ningeweza kuvuta up

270
00:19:49,840 --> 00:20:03,130
kuonyesha jinsi mtu anaweza kuanza kujenga mti vile?

271
00:20:03,130 --> 00:20:08,080
[Mwanafunzi] Mtu wa banging, kujaribu kupata nje.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Yeyote starehe na mti ujenzi yao?

273
00:20:13,100 --> 00:20:15,520
[Mwanafunzi] Uhakika. Ni si kufanyika. >> Ni faini. Tunaweza tu kumaliza -

274
00:20:15,520 --> 00:20:26,860
oh, unaweza kuokoa yake? Hooray.

275
00:20:26,860 --> 00:20:32,020
Hivyo hapa tuna - oh, mimi nina kidogo kukatwa.

276
00:20:32,020 --> 00:20:34,770
Am I zoomed katika?

277
00:20:34,770 --> 00:20:37,730
Zoom katika, tembeza nje. >> Nina swali. >> Yeah?

278
00:20:37,730 --> 00:20:44,410
[Mwanafunzi] Wakati unaweza kufafanua struct, ni mambo kama initialized kwa kitu chochote?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Sawa. Hivyo ingekuwa initialize -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Wakati unaweza kufafanua, au wakati kutangaza struct,

281
00:20:50,450 --> 00:20:55,600
si initialized na default; ni kama tu kama wewe kutangaza int.

282
00:20:55,600 --> 00:20:59,020
Ni hasa kitu kimoja. Ni kama kila moja ya mashamba yake binafsi

283
00:20:59,020 --> 00:21:04,460
unaweza kuwa na thamani ya takataka ndani yake. >> Na inawezekana define - au kutangaza struct

284
00:21:04,460 --> 00:21:07,740
katika njia ambayo haina initialize yao?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ndiyo. Hivyo, njia ya mkato initialization syntax

286
00:21:13,200 --> 00:21:18,660
ni kwenda kuangalia kama -

287
00:21:18,660 --> 00:21:22,200
Kuna njia mbili za tunaweza kufanya hivyo. Nadhani tunapaswa kukusanya ni

288
00:21:22,200 --> 00:21:25,840
kufanya Clang uhakika pia gani hii.

289
00:21:25,840 --> 00:21:28,510
utaratibu wa hoja kwamba anakuja katika struct,

290
00:21:28,510 --> 00:21:32,170
kuweka kama utaratibu wa hoja ndani ya hizi braces curly.

291
00:21:32,170 --> 00:21:35,690
Hivyo kama unataka initialize kwa 9 na kushoto kuwa batili na kisha haki itakuwa batili,

292
00:21:35,690 --> 00:21:41,570
itakuwa 9, null, null.

293
00:21:41,570 --> 00:21:47,890
mbadala ni, na mhariri hapendi hii syntax,

294
00:21:47,890 --> 00:21:50,300
na hivyo anadhani nataka block mpya,

295
00:21:50,300 --> 00:22:01,800
lakini mbadala ni kitu kama -

296
00:22:01,800 --> 00:22:04,190
hapa, mimi itabidi kuweka kwenye mstari mpya.

297
00:22:04,190 --> 00:22:09,140
Unaweza kupanga kusema, mimi kusahau syntax halisi.

298
00:22:09,140 --> 00:22:13,110
Hivyo unaweza kupanga kuyashughulikia kwa jina, na kusema,

299
00:22:13,110 --> 00:22:21,570
. C, au. Thamani = 9, kushoto. = Null.

300
00:22:21,570 --> 00:22:24,540
Mimi guessing haya haja ya kuwa na koma.

301
00:22:24,540 --> 00:22:29,110
. Haki = null, hivyo njia hii huna

302
00:22:29,110 --> 00:22:33,780
kweli wanahitaji kujua utaratibu wa struct,

303
00:22:33,780 --> 00:22:36,650
na wakati wewe ni kusoma, ni zaidi ya wazi

304
00:22:36,650 --> 00:22:41,920
kuhusu nini thamani ni kuwa initialized kwa.

305
00:22:41,920 --> 00:22:44,080
>> Hii hutokea kwa kuwa moja ya mambo ambayo -

306
00:22:44,080 --> 00:22:49,100
hivyo, kwa sehemu kubwa, C + + ni superset ya C.

307
00:22:49,100 --> 00:22:54,160
Unaweza kuchukua C code, hoja ni juu ya C + +, na ni lazima kukusanya.

308
00:22:54,160 --> 00:22:59,570
Hii ni moja ya mambo ambayo C + + hakiingiliani, hivyo watu huwa si ya kufanya hivyo.

309
00:22:59,570 --> 00:23:01,850
Mimi sijui kama hiyo ni sababu tu watu huwa si ya kufanya hivyo,

310
00:23:01,850 --> 00:23:10,540
lakini kesi ambapo mimi zinahitajika kutumia ni zinahitajika kufanya kazi na C + + na hivyo sikuweza kutumia hii.

311
00:23:10,540 --> 00:23:14,000
Mfano mwingine wa kitu ambacho hana kazi na C + + ni

312
00:23:14,000 --> 00:23:16,940
jinsi malloc anarudi "Kosa *," kitaalam,

313
00:23:16,940 --> 00:23:20,200
lakini unaweza tu kusema Char * x = malloc chochote,

314
00:23:20,200 --> 00:23:22,840
na itakuwa moja kwa moja kutupwa katika * Char.

315
00:23:22,840 --> 00:23:25,450
Kwamba kutupwa moja kwa moja haina kutokea katika C + +.

316
00:23:25,450 --> 00:23:28,150
Hiyo si kukusanya, na ungependa waziwazi haja ya kusema

317
00:23:28,150 --> 00:23:34,510
Char *, malloc, chochote, kuwatupia * Char.

318
00:23:34,510 --> 00:23:37,270
Kuna mambo mengi ambayo C na C + + hawakubaliani juu,

319
00:23:37,270 --> 00:23:40,620
lakini wale ni mbili.

320
00:23:40,620 --> 00:23:43,120
Hivyo tutaweza kwenda kwa syntax hii.

321
00:23:43,120 --> 00:23:46,150
Lakini hata kama sisi hawakuwa kwenda kwa syntax kwamba,

322
00:23:46,150 --> 00:23:49,470
nini ni - inaweza kuwa na makosa na hili?

323
00:23:49,470 --> 00:23:52,170
[Mwanafunzi] mimi hawana haja ya dereference yake? >> Yeah.

324
00:23:52,170 --> 00:23:55,110
Kumbuka kwamba mshale ana dereference thabiti,

325
00:23:55,110 --> 00:23:58,230
na hivyo wakati tuko tu kushughulika na struct,

326
00:23:58,230 --> 00:24:04,300
tunataka kutumia. kupata saa ndani ya uwanja wa struct.

327
00:24:04,300 --> 00:24:07,200
Na wakati tu sisi kutumia mshale ni wakati tunataka kufanya -

328
00:24:07,200 --> 00:24:13,450
vizuri, mshale ni sawa na -

329
00:24:13,450 --> 00:24:17,020
hiyo ndiyo ingekuwa na maana kama mimi kutumika mshale.

330
00:24:17,020 --> 00:24:24,600
Njia zote mshale ni, dereference hii, sasa mimi nina katika struct, na mimi tunaweza kupata shamba.

331
00:24:24,600 --> 00:24:28,040
Aidha kupata shamba moja kwa moja au dereference na kupata shamba -

332
00:24:28,040 --> 00:24:30,380
Nadhani hii inapaswa kuwa thamani.

333
00:24:30,380 --> 00:24:33,910
Lakini hapa mimi nina kushughulika na struct tu, si pointer struct,

334
00:24:33,910 --> 00:24:38,780
na hivyo siwezi kutumia mshale.

335
00:24:38,780 --> 00:24:47,510
Lakini jambo la aina hii tunaweza kufanya kwa ajili nodes wote.

336
00:24:47,510 --> 00:24:55,790
Oh, Mungu wangu.

337
00:24:55,790 --> 00:25:09,540
Hii ni 6, 7, na 3.

338
00:25:09,540 --> 00:25:16,470
Kisha tunaweza kuanzisha matawi katika mti yetu, tunaweza kuwa 7 -

339
00:25:16,470 --> 00:25:21,650
tunaweza kuwa, kushoto wake wanapaswa kumweka kwa 3.

340
00:25:21,650 --> 00:25:25,130
Hivyo ni jinsi gani sisi kufanya hivyo?

341
00:25:25,130 --> 00:25:29,320
[Wanafunzi, unintelligible] >> Yeah. anuani ya node3,

342
00:25:29,320 --> 00:25:34,170
na kama hakuwa na anuani, basi tu bila kukusanya.

343
00:25:34,170 --> 00:25:38,190
Lakini kumbuka kwamba hawa ni kuyatumia na nodi ijayo.

344
00:25:38,190 --> 00:25:44,930
haki lazima kumweka kwa 9,

345
00:25:44,930 --> 00:25:53,330
na 3 wanapaswa kumweka juu ya haki ya 6.

346
00:25:53,330 --> 00:25:58,480
Nadhani hii ni kuweka wote. Maoni yoyote au maswali?

347
00:25:58,480 --> 00:26:02,060
[Mwanafunzi, unintelligible] mzizi ni kwenda kuwa 7.

348
00:26:02,060 --> 00:26:08,210
Tunaweza tu kusema nodi * PTR =

349
00:26:08,210 --> 00:26:14,160
au mizizi, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Kwa madhumuni yetu, sisi ni kwenda kuwa kushughulika na Insert,

351
00:26:20,730 --> 00:26:25,490
hivyo sisi ni kwenda unataka kuandika kazi na kuingiza ndani ya mti huu binary

352
00:26:25,490 --> 00:26:34,230
na Insert ni inevitably kwenda kuwaita malloc kujenga nodi mpya kwa ajili ya mti huu.

353
00:26:34,230 --> 00:26:36,590
Basi mambo ni kwenda kupata messy na ukweli kwamba baadhi nodes

354
00:26:36,590 --> 00:26:38,590
sasa ni juu ya stack

355
00:26:38,590 --> 00:26:43,680
na nodes nyingine ni kwenda kuishia juu ya lundo wakati sisi Insert yao.

356
00:26:43,680 --> 00:26:47,640
Hii ni kikamilifu halali, lakini kwa sababu tu

357
00:26:47,640 --> 00:26:49,600
sisi ni uwezo wa kufanya hivyo kwenye stack

358
00:26:49,600 --> 00:26:51,840
ni kwa sababu ni mfano vile contrived kwamba sisi kujua

359
00:26:51,840 --> 00:26:56,360
mti zinatakiwa kuwa yalijengwa kama 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Kama hatukuwa na hii, basi tusingekuwa na malloc katika nafasi ya kwanza.

361
00:27:02,970 --> 00:27:06,160
Kama tutaweza kuona kidogo baadaye, sisi lazima malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Hivi sasa ni kikamilifu busara ya kuweka kwenye stack,

363
00:27:08,570 --> 00:27:14,750
lakini hebu kubadili hili kwa utekelezaji malloc.

364
00:27:14,750 --> 00:27:17,160
Hivyo kila moja ya haya ni sasa kwenda kuwa kitu kama

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

366
00:27:24,240 --> 00:27:28,040
Na sasa sisi itawabidi kufanya hundi yetu.

367
00:27:28,040 --> 00:27:34,010
kama (node9 == null) - sikutaka kwamba -

368
00:27:34,010 --> 00:27:40,950
kurudi 1, na kisha tunaweza kufanya node9-> kwa sababu sasa ni pointer,

369
00:27:40,950 --> 00:27:45,300
thamani = 6, node9-> kushoto = null,

370
00:27:45,300 --> 00:27:48,930
node9-> kulia = null,

371
00:27:48,930 --> 00:27:51,410
na sisi itawabidi kufanya hivyo kwa kila nodes hizo.

372
00:27:51,410 --> 00:27:57,490
Hivyo badala yake, hebu kuiweka ndani ya kazi tofauti.

373
00:27:57,490 --> 00:28:00,620
Hebu kuiita nodi * build_node,

374
00:28:00,620 --> 00:28:09,050
na hii ni sawa na kiasi fulani APIs sisi kutoa kwa Huffman coding.

375
00:28:09,050 --> 00:28:12,730
Sisi kukupa kazi initializer kwa mti

376
00:28:12,730 --> 00:28:20,520
na deconstructor "kazi" kwa ajili ya miti na wale sawa kwa misitu.

377
00:28:20,520 --> 00:28:22,570
>> Hivyo hapa tunakwenda kuwa na kazi initializer

378
00:28:22,570 --> 00:28:25,170
tu kujenga nodi kwa ajili yetu.

379
00:28:25,170 --> 00:28:29,320
Na ni kwenda kuangalia kiasi pretty hasa kama hii.

380
00:28:29,320 --> 00:28:32,230
Na mimi hata kwenda kuwa wavivu na si kubadili jina la kutofautiana,

381
00:28:32,230 --> 00:28:34,380
ingawa node9 haina mantiki tena.

382
00:28:34,380 --> 00:28:38,610
Oh, mimi nadhani thamani node9 wa haifai kuwa 6.

383
00:28:38,610 --> 00:28:42,800
Sasa tunaweza kurudi node9.

384
00:28:42,800 --> 00:28:49,550
Na hapa sisi lazima kurudi null.

385
00:28:49,550 --> 00:28:52,690
Kila mtu kukubaliana kwamba kazi kujenga-a-nodi?

386
00:28:52,690 --> 00:28:59,780
Hivyo sasa tunaweza kuwaita tu kwamba kujenga yoyote ya nodi thamani aliyopewa na kuyatumia null.

387
00:28:59,780 --> 00:29:09,750
Sasa tunaweza kuwaita kuwa, tunaweza kufanya nodi * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Na hebu kufanya. . .

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

390
00:29:33,980 --> 00:29:39,330
Na sasa tunataka kuanzisha kuyatumia huo,

391
00:29:39,330 --> 00:29:42,470
ila sasa kila kitu tayari katika suala la kuyatumia

392
00:29:42,470 --> 00:29:48,480
hivyo hakuna haja tena ya anuani.

393
00:29:48,480 --> 00:29:56,300
Sawa. Basi nini jambo la mwisho nataka kufanya?

394
00:29:56,300 --> 00:30:03,850
Kuna kosa-kuangalia kwamba mimi si kufanya.

395
00:30:03,850 --> 00:30:06,800
Gani kujenga nodi kurudi?

396
00:30:06,800 --> 00:30:11,660
[Mwanafunzi, unintelligible] >> Yeah. Kama malloc alishindwa, hivyo itabidi kurudi null.

397
00:30:11,660 --> 00:30:16,460
Hivyo nina kwenda kwa lazily kuiweka chini hapa badala ya kufanya kwa kila hali.

398
00:30:16,460 --> 00:30:22,320
Kama (node9 == null, au - hata rahisi,

399
00:30:22,320 --> 00:30:28,020
hii ni sawa tu kama si node9.

400
00:30:28,020 --> 00:30:38,310
Hivyo kama si node9, au si node6, au si node3, au si node7, kurudi 1.

401
00:30:38,310 --> 00:30:42,850
Labda sisi lazima magazeti malloc wameshindwa, au kitu.

402
00:30:42,850 --> 00:30:46,680
[Mwanafunzi] Je uongo sawa null vile vile?

403
00:30:46,680 --> 00:30:51,290
[Bowden] yoyote thamani sifuri ni uongo.

404
00:30:51,290 --> 00:30:53,920
Hivyo ni thamani null sifuri.

405
00:30:53,920 --> 00:30:56,780
Zero ni thamani sifuri. Uongo ni thamani sifuri.

406
00:30:56,780 --> 00:31:02,130
Yoyote - pretty much tu 2 maadili sifuri ni batili na sifuri,

407
00:31:02,130 --> 00:31:07,900
uongo ni hash hufafanuliwa kama sifuri.

408
00:31:07,900 --> 00:31:13,030
Hiyo pia inatumika kama hatuwezi kutangaza variable kimataifa.

409
00:31:13,030 --> 00:31:17,890
Kama sisi tulikuwa na nodi * mizizi hapa juu,

410
00:31:17,890 --> 00:31:24,150
basi - kitu kizuri kuhusu vigezo kimataifa ni kwamba wao daima kuwa na thamani ya awali.

411
00:31:24,150 --> 00:31:27,500
Hiyo si kweli wa kazi, jinsi ya ndani ya hapa,

412
00:31:27,500 --> 00:31:34,870
kama tuna, kama, nodi * au x nodi.

413
00:31:34,870 --> 00:31:37,380
Sisi hatuna wazo nini x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
au tunaweza magazeti yao na wanaweza kuwa holela.

415
00:31:40,700 --> 00:31:44,980
Hiyo si kweli ya vigezo kimataifa.

416
00:31:44,980 --> 00:31:47,450
Hivyo nodi mizizi au x nodi.

417
00:31:47,450 --> 00:31:53,410
By default, kila kitu kilicho duniani, kama si wazi initialized kwa thamani baadhi,

418
00:31:53,410 --> 00:31:57,390
ina thamani ya sifuri kama thamani yake.

419
00:31:57,390 --> 00:32:01,150
Hivyo hapa, nodi * mizizi, sisi si wazi initialize kwa kitu chochote,

420
00:32:01,150 --> 00:32:06,350
hivyo default thamani yake itakuwa null, ambayo ni thamani ya sifuri ya kuyatumia.

421
00:32:06,350 --> 00:32:11,870
thamani default ya x ni kwenda maana kwamba x.value ni sifuri,

422
00:32:11,870 --> 00:32:14,260
x.left ni null, na x.right ni null.

423
00:32:14,260 --> 00:32:21,070
Hivyo kwa vile ni struct, wote wa mashamba ya struct itakuwa sifuri maadili.

424
00:32:21,070 --> 00:32:24,410
Hatuna haja ya kutumia kwamba hapa, ingawa.

425
00:32:24,410 --> 00:32:27,320
[Mwanafunzi] structs ni tofauti kuliko vigezo vingine, na vigezo vingine ni

426
00:32:27,320 --> 00:32:31,400
takataka maadili, haya ni ya zeros?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Nyengine maadili pia. Hivyo katika x, x itakuwa sifuri.

428
00:32:36,220 --> 00:32:40,070
Kama ni katika upeo wa kimataifa, ina thamani ya awali. >> Sawa.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Ama thamani ya awali wewe akampa au sifuri.

430
00:32:48,950 --> 00:32:53,260
Nadhani kwamba inachukua huduma ya yote haya.

431
00:32:53,260 --> 00:32:58,390
>> Sawa. Hivyo sehemu ya pili ya swali anauliza,

432
00:32:58,390 --> 00:33:01,260
"Sasa tunataka kuandika kazi kuitwa ina

433
00:33:01,260 --> 00:33:04,930
kwa mfano wa bool ina thamani int. "

434
00:33:04,930 --> 00:33:08,340
Sisi si kwenda kufanya bool ina thamani int.

435
00:33:08,340 --> 00:33:15,110
Mfano wetu ni kwenda kuangalia kama

436
00:33:15,110 --> 00:33:22,380
bool ina (thamani int.

437
00:33:22,380 --> 00:33:24,490
Na kisha sisi ni pia kwenda kupita mti

438
00:33:24,490 --> 00:33:28,870
kwamba ni lazima kuangalia kuona kama ana kwamba thamani.

439
00:33:28,870 --> 00:33:38,290
Hivyo nodi * mti). Sawa.

440
00:33:38,290 --> 00:33:44,440
Na kisha tunaweza kuiita na kitu kama,

441
00:33:44,440 --> 00:33:46,090
labda tutaweza wanataka printf au kitu.

442
00:33:46,090 --> 00:33:51,040
Ina 6, mizizi yetu.

443
00:33:51,040 --> 00:33:54,300
Kwamba lazima kurudi moja, au kweli,

444
00:33:54,300 --> 00:33:59,390
ambapo ina 5 mzizi lazima kurudi uongo.

445
00:33:59,390 --> 00:34:02,690
Hivyo kuchukua pili kutekeleza hili.

446
00:34:02,690 --> 00:34:06,780
Unaweza kufanya hivyo aidha iteratively au recursively.

447
00:34:06,780 --> 00:34:09,739
Jambo zuri kuhusu njia tumekuwa kuweka mambo juu ni kwamba

448
00:34:09,739 --> 00:34:12,300
ni kunafaa kwa ufumbuzi yetu ya kujirudia rahisi

449
00:34:12,300 --> 00:34:14,719
kuliko njia ya kimataifa-variable alivyofanya.

450
00:34:14,719 --> 00:34:19,750
Kwa sababu kama sisi tu ina thamani int, basi hatuna njia ya recursing chini subtrees.

451
00:34:19,750 --> 00:34:24,130
Tunataka kuwa na tofauti msaidizi kazi kwamba recurses chini subtrees kwa ajili yetu.

452
00:34:24,130 --> 00:34:29,610
Lakini tangu tumekuwa iliyopita ni kuchukua mti kama hoja,

453
00:34:29,610 --> 00:34:32,760
ambayo ni lazima daima wamekuwa katika nafasi ya kwanza,

454
00:34:32,760 --> 00:34:35,710
sasa tunaweza recurse kwa urahisi zaidi.

455
00:34:35,710 --> 00:34:38,960
Hivyo iterative au kujirudia, tutaweza kwenda juu ya wote,

456
00:34:38,960 --> 00:34:46,139
lakini tutaweza kuona kwamba ncha ya kujirudia up kuwa rahisi kabisa.

457
00:34:59,140 --> 00:35:02,480
Sawa. Je, mtu yeyote kuwa na kitu tunaweza kufanya kazi na?

458
00:35:02,480 --> 00:35:12,000
>> [Mwanafunzi] Mimi nimepata iterative ufumbuzi. >> Sawa, iterative.

459
00:35:12,000 --> 00:35:16,030
Okay, hii inaonekana ni nzuri.

460
00:35:16,030 --> 00:35:18,920
Hivyo, wanataka kutembea kwetu kwa njia hiyo?

461
00:35:18,920 --> 00:35:25,780
[Mwanafunzi] Uhakika. Basi, mimi kuweka variable temp kupata nodi ya kwanza ya mti.

462
00:35:25,780 --> 00:35:28,330
Na kisha mimi tu looped kupitia wakati temp haina null sawa,

463
00:35:28,330 --> 00:35:31,700
hivyo wakati bado alikuwa katika mti, mimi nadhani.

464
00:35:31,700 --> 00:35:35,710
Na kama thamani ni sawa na thamani ya kwamba ni temp akizungumzia,

465
00:35:35,710 --> 00:35:37,640
kisha kuirudisha kwamba thamani.

466
00:35:37,640 --> 00:35:40,210
Vinginevyo, ni hundi kama ni upande wa kulia au kushoto.

467
00:35:40,210 --> 00:35:43,400
Kama umewahi kupata hali ambapo hakuna mti zaidi,

468
00:35:43,400 --> 00:35:47,330
kisha kuirudisha - ni exits kitanzi na anarudi uongo.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Sawa. Hivyo kwamba inaonekana nzuri.

470
00:35:52,190 --> 00:35:58,470
Mtu yeyote kuwa maoni yoyote juu ya kitu chochote?

471
00:35:58,470 --> 00:36:02,400
Sina usahihi maoni wakati wote.

472
00:36:02,400 --> 00:36:11,020
Jambo moja tunaweza kufanya ni hii guy.

473
00:36:11,020 --> 00:36:21,660
Oh, ni kwenda longish kidogo.

474
00:36:21,660 --> 00:36:33,460
Mimi itabidi kurekebisha up. Sawa.

475
00:36:33,460 --> 00:36:37,150
>> Kila mmoja anapaswa kukumbuka jinsi ternary kazi.

476
00:36:37,150 --> 00:36:38,610
Kuna dhahiri imekuwa Quizzes katika kipindi cha

477
00:36:38,610 --> 00:36:41,170
kwamba kukupa kazi pamoja na operator ternary,

478
00:36:41,170 --> 00:36:45,750
na kusema, kutafsiri hii, kufanya kitu ambacho si kutumia ternary.

479
00:36:45,750 --> 00:36:49,140
Hivyo hii ni kesi ya kawaida sana ya wakati mimi kudhani kutumia ternary,

480
00:36:49,140 --> 00:36:54,610
ambapo kama hali baadhi kuweka variable na kitu,

481
00:36:54,610 --> 00:36:58,580
mwingine kuweka kwamba variable sawa na kitu kingine.

482
00:36:58,580 --> 00:37:03,390
Hiyo ni kitu ambacho mara nyingi sana inaweza kubadilishwa katika aina hii ya jambo

483
00:37:03,390 --> 00:37:14,420
ambapo kuweka kwamba kutofautiana kwa hii - au, vizuri, hii ni kweli? Kisha hii, pengine hii.

484
00:37:14,420 --> 00:37:18,550
[Mwanafunzi] moja ya kwanza ni kama kweli, haki?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. njia ya mimi daima kusoma ni, temp sawa thamani kubwa zaidi kuliko thamani temp,

486
00:37:25,570 --> 00:37:30,680
basi hii, pengine hii. Ni kuuliza swali.

487
00:37:30,680 --> 00:37:35,200
Je, ni kubwa? Kisha kufanya jambo la kwanza. Mwingine kufanya kitu cha pili.

488
00:37:35,200 --> 00:37:41,670
Mimi daima karibu - koloni, mimi tu - katika kichwa changu, mimi kusoma kama mwingine.

489
00:37:41,670 --> 00:37:47,180
>> Je, mtu yeyote kuwa na ufumbuzi kujirudia?

490
00:37:47,180 --> 00:37:49,670
Sawa. Hii moja tunakwenda - inaweza tayari kuwa kubwa,

491
00:37:49,670 --> 00:37:53,990
lakini sisi ni kwenda kufanya ni bora zaidi.

492
00:37:53,990 --> 00:37:58,720
Hii ni pretty kiasi sawa exact wazo.

493
00:37:58,720 --> 00:38:03,060
Ni tu, vizuri, unataka kueleza?

494
00:38:03,060 --> 00:38:08,340
[Mwanafunzi] Uhakika. Hivyo sisi ni kuhakikisha kwamba mti si null kwanza,

495
00:38:08,340 --> 00:38:13,380
kwa sababu kama mti ni null basi ni kwenda na kurudi uongo kwa sababu sisi si kupatikana.

496
00:38:13,380 --> 00:38:19,200
Na kama bado kuna mti, tunaingia katika - sisi kwanza kuangalia kama thamani ni nodi sasa.

497
00:38:19,200 --> 00:38:23,740
Kurudi kweli kama ilivyo, na kama si sisi recurse upande wa kushoto au kulia.

498
00:38:23,740 --> 00:38:25,970
Je, kwamba sauti sahihi? >> MM-hmm. (Mkataba)

499
00:38:25,970 --> 00:38:33,880
Hivyo taarifa kwamba hii ni karibu - kimuundo ni sawa na ufumbuzi iterative.

500
00:38:33,880 --> 00:38:38,200
Ni tu kwamba badala ya recursing, tulikuwa na kitanzi wakati.

501
00:38:38,200 --> 00:38:40,840
Na kesi ya msingi hapa ambapo mti haina null sawa

502
00:38:40,840 --> 00:38:44,850
ilikuwa hali ya chini ambayo sisi kuvunja nje ya kitanzi wakati.

503
00:38:44,850 --> 00:38:50,200
Wao ni sawa sana. Lakini sisi ni kwenda kuchukua hatua hii moja zaidi.

504
00:38:50,200 --> 00:38:54,190
Sasa, sisi kufanya kitu kimoja hapa.

505
00:38:54,190 --> 00:38:57,680
Angalia tuko kurudi kitu kimoja katika wote wa mistari haya,

506
00:38:57,680 --> 00:39:00,220
isipokuwa kwa moja hoja ni tofauti.

507
00:39:00,220 --> 00:39:07,950
Hivyo sisi ni kwenda kufanya kwamba katika ternary.

508
00:39:07,950 --> 00:39:13,790
I hit chaguo kitu, na alifanya ishara. Sawa.

509
00:39:13,790 --> 00:39:21,720
Hivyo sisi ni kwenda na kurudi ina kuwa.

510
00:39:21,720 --> 00:39:28,030
Hii ni kupata kuwa nyingi mistari, vizuri, zoomed katika ni.

511
00:39:28,030 --> 00:39:31,060
Kawaida, kama kitu Stylistic, sidhani watu wengi

512
00:39:31,060 --> 00:39:38,640
kuweka nafasi baada ya mshale, lakini mimi nadhani kama wewe ni thabiti, ni faini.

513
00:39:38,640 --> 00:39:44,320
Kama thamani ni chini ya thamani ya mti, tunataka recurse kushoto mti,

514
00:39:44,320 --> 00:39:53,890
mwingine tunataka recurse juu ya haki ya mti.

515
00:39:53,890 --> 00:39:58,610
Hivyo kwamba ilikuwa hatua moja ya kufanya kuangalia hii ndogo.

516
00:39:58,610 --> 00:40:02,660
Hatua mbili za kufanya kuangalia hii ndogo ndogo -

517
00:40:02,660 --> 00:40:09,150
tunaweza kutenganisha hii kwa mistari mingi.

518
00:40:09,150 --> 00:40:16,500
Sawa. Hatua mbili za kufanya ni kuangalia ni ndogo hapa,

519
00:40:16,500 --> 00:40:25,860
hivyo kurudi thamani sawa na mti thamani, au ina chochote.

520
00:40:25,860 --> 00:40:28,340
>> Hili ni jambo muhimu.

521
00:40:28,340 --> 00:40:30,860
Mimi nina uhakika kama yeye alisema ni wazi katika darasa,

522
00:40:30,860 --> 00:40:34,740
lakini ni wito mfupi-mzunguko tathmini.

523
00:40:34,740 --> 00:40:41,060
Wazo hapa ni thamani == mti thamani.

524
00:40:41,060 --> 00:40:49,960
Kama hiyo ni kweli, basi hii ni kweli, na tunataka 'au' kuwa na chochote ni zaidi ya hapa.

525
00:40:49,960 --> 00:40:52,520
Hivyo bila hata kufikiria juu ya chochote ni zaidi ya hapa,

526
00:40:52,520 --> 00:40:55,070
kile ni usemi mzima kwenda na kurudi?

527
00:40:55,070 --> 00:40:59,430
[Mwanafunzi] Kweli? >> Yeah, kwa sababu ya kweli ya kitu chochote,

528
00:40:59,430 --> 00:41:04,990
or'd - au kweli or'd na kitu chochote ni lazima kweli.

529
00:41:04,990 --> 00:41:08,150
Hivyo kwa haraka kama sisi kuona kurudi thamani = mti thamani,

530
00:41:08,150 --> 00:41:10,140
sisi ni kwenda tu kurudi kweli.

531
00:41:10,140 --> 00:41:15,710
Si hata kwenda recurse zaidi ina chini ya mstari.

532
00:41:15,710 --> 00:41:20,980
Tunaweza kuchukua hatua hii moja zaidi.

533
00:41:20,980 --> 00:41:29,490
Kurudi mti haina null sawa na hii yote.

534
00:41:29,490 --> 00:41:32,650
Ni alifanya hivyo kazi moja-line.

535
00:41:32,650 --> 00:41:36,790
Hii pia ni mfano wa tathmini mfupi mzunguko.

536
00:41:36,790 --> 00:41:40,680
Lakini sasa ni wazo sawa -

537
00:41:40,680 --> 00:41:47,320
badala ya - hivyo kama mti haina sawa null - au, vizuri,

538
00:41:47,320 --> 00:41:49,580
kama mti gani null sawa, ambayo ni kesi mbaya,

539
00:41:49,580 --> 00:41:54,790
kama mti sawa null, basi hali ya kwanza ni kwenda kuwa uongo.

540
00:41:54,790 --> 00:42:00,550
Hivyo uongo anded na kitu chochote ni kwenda kuwa nini?

541
00:42:00,550 --> 00:42:04,640
[Mwanafunzi] Uongo. >> Yeah. Hii ni nusu nyingine ya tathmini short-mzunguko,

542
00:42:04,640 --> 00:42:10,710
ambapo kama mti haina sawa null, basi sisi si kwenda hata kwenda -

543
00:42:10,710 --> 00:42:14,930
au kama mti gani null sawa, basi sisi si kwenda kufanya thamani == mti thamani.

544
00:42:14,930 --> 00:42:17,010
Sisi ni kwenda tu mara moja kurudi uongo.

545
00:42:17,010 --> 00:42:20,970
Ambayo ni muhimu, kwani kama ilivyokuwa si mfupi-mzunguko kutathmini,

546
00:42:20,970 --> 00:42:25,860
basi kama mti gani null sawa, hii hali ya pili ni kwenda kosa seg,

547
00:42:25,860 --> 00:42:32,510
kwa sababu mti-> thamani dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Basi hiyo ni kwamba. Wanaweza kufanya hili - kuhama mara moja zaidi.

549
00:42:40,490 --> 00:42:44,840
Hili ni jambo la kawaida sana pia, si kufanya hii line moja na hili,

550
00:42:44,840 --> 00:42:49,000
lakini ni jambo la kawaida katika hali, labda si haki hapa,

551
00:42:49,000 --> 00:42:59,380
lakini kama (mti = null!, na mti-> thamani == thamani), kufanya chochote.

552
00:42:59,380 --> 00:43:01,560
Hii ni hali ya kawaida sana, ambapo badala ya kuwa

553
00:43:01,560 --> 00:43:06,770
kuvunja hii katika ikiwa mbili, ambapo kama, ni null mti?

554
00:43:06,770 --> 00:43:11,780
Okay, siyo null, hivyo sasa ni thamani mti sawa na thamani? Je hii.

555
00:43:11,780 --> 00:43:17,300
Badala yake, hali hii, hii kamwe seg kosa

556
00:43:17,300 --> 00:43:21,220
sababu itakuwa kuvunja nje kama hii hutokea kwa kuwa null.

557
00:43:21,220 --> 00:43:24,000
Naam, mimi nadhani kama mti yako ni pointer kabisa batili, bado inaweza seg kosa,

558
00:43:24,000 --> 00:43:26,620
lakini haiwezi seg kosa kama mti ni null.

559
00:43:26,620 --> 00:43:32,900
Kama walikuwa null, ingekuwa kuvunja nje kabla ya milele dereferenced pointer katika nafasi ya kwanza.

560
00:43:32,900 --> 00:43:35,000
[Mwanafunzi] Je hii inayoitwa wavivu tathmini?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] tathmini Lazy ni jambo tofauti.

562
00:43:40,770 --> 00:43:49,880
Tathmini wavivu ni zaidi kama wewe kuuliza kwa thamani,

563
00:43:49,880 --> 00:43:54,270
kuuliza kwa mahesabu ya thamani, aina, lakini huna haja ya mara moja.

564
00:43:54,270 --> 00:43:59,040
Hivyo mpaka wewe kweli haja yake, si tathmini.

565
00:43:59,040 --> 00:44:03,920
Hii si hasa kitu kimoja, lakini katika pset Huffman,

566
00:44:03,920 --> 00:44:06,520
inasema kwamba sisi "lazily" kuandika.

567
00:44:06,520 --> 00:44:08,670
sababu sisi kufanya hivyo ni kwa sababu sisi ni kweli buffering kuandika -

568
00:44:08,670 --> 00:44:11,820
hatutaki kuandika bits mmoja kwa wakati,

569
00:44:11,820 --> 00:44:15,450
au ka mmoja kwa wakati, sisi badala wanataka kupata chunk ya ka.

570
00:44:15,450 --> 00:44:19,270
Kisha mara moja tuna chunk ya ka, basi tutaweza kuandika ni nje.

571
00:44:19,270 --> 00:44:22,640
Hata kama wewe ni kuuliza kuandika - na fwrite na fread kufanya aina moja ya kitu.

572
00:44:22,640 --> 00:44:26,260
Wao buffer wasomaji wako na anaandika.

573
00:44:26,260 --> 00:44:31,610
Hata kama wewe ni kuuliza kuandika mara moja, labda si.

574
00:44:31,610 --> 00:44:34,540
Na huwezi kuwa na uhakika kwamba mambo yanaenda kuwa imeandikwa

575
00:44:34,540 --> 00:44:37,540
mpaka wewe piga hfclose au chochote ni,

576
00:44:37,540 --> 00:44:39,620
ambayo kisha anasema, sawa, mimi nina kufunga faili yangu,

577
00:44:39,620 --> 00:44:43,450
kwamba maana ningependa bora uandike kila kitu Sikuwaandikia bado.

578
00:44:43,450 --> 00:44:45,770
Ni hakuna haja ya kuandika kila kitu nje

579
00:44:45,770 --> 00:44:49,010
mpaka wewe ni kufunga faili, na kisha inahitaji.

580
00:44:49,010 --> 00:44:56,220
Basi hiyo ni kile tu wavivu - waits mpaka ina kutokea.

581
00:44:56,220 --> 00:44:59,990
Hii - kuchukua 51 na utasikia uende ndani yake kwa undani zaidi,

582
00:44:59,990 --> 00:45:05,470
kwa sababu OCaml na kila kitu katika 51, kila kitu ni recursion.

583
00:45:05,470 --> 00:45:08,890
Hakuna ufumbuzi iterative, kimsingi.

584
00:45:08,890 --> 00:45:11,550
Kila kitu ni recursion, na tathmini wavivu

585
00:45:11,550 --> 00:45:14,790
ni kwenda kuwa muhimu kwa ajili ya kura ya mazingira

586
00:45:14,790 --> 00:45:19,920
ambapo, kama hakuwa na lazily kutathmini, kwamba ingekuwa na maana -

587
00:45:19,920 --> 00:45:24,760
Mfano ni mito, ambayo ni kubwa kwa muda mrefu.

588
00:45:24,760 --> 00:45:30,990
Katika nadharia, unaweza kufikiria idadi ya asili kama mkondo wa 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Hivyo lazily tathmini mambo ni faini.

590
00:45:33,090 --> 00:45:37,210
Nikisema mimi nataka namba kumi, kisha naweza kutathmini hadi idadi ya kumi.

591
00:45:37,210 --> 00:45:40,300
Kama mimi nataka namba mia, naweza kutathmini hadi idadi mia.

592
00:45:40,300 --> 00:45:46,290
Bila tathmini wavivu, basi ni kwenda kujaribu kutathmini idadi yote mara moja.

593
00:45:46,290 --> 00:45:50,000
Wewe ni kutathmini idadi kubwa wengi, na kwamba si tu iwezekanavyo.

594
00:45:50,000 --> 00:45:52,080
Hivyo kuna mengi ya mazingira ambapo wavivu tathmini

595
00:45:52,080 --> 00:45:57,840
ni tu muhimu kwa kupata mambo ya kufanya kazi.

596
00:45:57,840 --> 00:46:05,260
>> Sasa tunataka kuandika Insert ambapo Insert ni kwenda kuwa

597
00:46:05,260 --> 00:46:08,430
vile vile kubadilisha katika ufafanuzi wake.

598
00:46:08,430 --> 00:46:10,470
Hivyo sasa hivi ni bool Insert (int thamani).

599
00:46:10,470 --> 00:46:23,850
Sisi ni kwenda na mabadiliko ya kwamba ili Insert bool (int thamani, nodi * mti).

600
00:46:23,850 --> 00:46:29,120
Sisi ni kweli kwenda na mabadiliko ya kwamba tena katika kidogo, tutaweza kuona nini.

601
00:46:29,120 --> 00:46:32,210
Na hebu hoja build_node, tu kwa ajili ya heck yake,

602
00:46:32,210 --> 00:46:36,730
juu Insert hivyo hatuna kuandika mfano kazi.

603
00:46:36,730 --> 00:46:42,450
Ambayo ni dokezo kwamba utaenda kuwa na kutumia build_node katika Insert.

604
00:46:42,450 --> 00:46:49,590
Sawa. Chukua dakika kwa ajili hiyo.

605
00:46:49,590 --> 00:46:52,130
Nadhani mimi kuokolewa marekebisho kama unataka kuvuta kutoka kwamba,

606
00:46:52,130 --> 00:47:00,240
au, angalau, mimi sasa.

607
00:47:00,240 --> 00:47:04,190
Nilitaka mapumziko kidogo kufikiria juu ya mantiki ya Insert,

608
00:47:04,190 --> 00:47:08,750
kama huwezi kufikiria hivyo.

609
00:47:08,750 --> 00:47:12,860
Kimsingi, utakuwa tu milele kuwa inserting katika majani.

610
00:47:12,860 --> 00:47:18,640
Kama, kama mimi Insert 1, basi mimi nina inevitably kwenda kuwa inserting 1 -

611
00:47:18,640 --> 00:47:21,820
Mimi umebadirisha hadi nyeusi - I'll kuwa inserting 1 zaidi ya hapa.

612
00:47:21,820 --> 00:47:28,070
Au kama mimi Insert 4, nataka kuwa inserting 4 zaidi ya hapa.

613
00:47:28,070 --> 00:47:32,180
Hivyo hakuna jambo gani wewe, wewe utaenda inserting katika jani.

614
00:47:32,180 --> 00:47:36,130
Wote una kufanya ni iterate chini ya mti mpaka kupata na nodi

615
00:47:36,130 --> 00:47:40,890
kwamba wanapaswa kuwa mzazi wa nodi, mzazi nodi mpya,

616
00:47:40,890 --> 00:47:44,560
na kisha kubadili pointer wake wa kushoto au kulia, kutegemea kama

617
00:47:44,560 --> 00:47:47,060
ni zaidi au chini ya nodi ya sasa.

618
00:47:47,060 --> 00:47:51,180
Mabadiliko ya kwamba pointer kwa uhakika na nodi ya mwezi mpya.

619
00:47:51,180 --> 00:48:05,490
Hivyo iterate chini ya mti, kufanya uhakika jani na nodi ya mwezi.

620
00:48:05,490 --> 00:48:09,810
Pia kufikiria kuhusu nini kuwa inakataza hali ya aina kabla,

621
00:48:09,810 --> 00:48:17,990
ambapo mimi yalijengwa mti binary ambapo ilikuwa sahihi

622
00:48:17,990 --> 00:48:19,920
kama wewe tu inaonekana kwenye nodi moja,

623
00:48:19,920 --> 00:48:24,830
lakini 9 ilikuwa upande wa kushoto wa 7 kama wewe iterated chini njia yote.

624
00:48:24,830 --> 00:48:29,770
Basi hiyo ni vigumu katika hali hii, tangu -

625
00:48:29,770 --> 00:48:32,530
Msidhani kuhusu inserting 9 au kitu; kwenye nodi sana kwanza,

626
00:48:32,530 --> 00:48:35,350
Mimi nina kwenda kuona 7 na Mimi tu anaenda kwenda kulia.

627
00:48:35,350 --> 00:48:38,490
Hivyo hakuna jambo nini mimi, kama mimi nina kuingiza kwa kwenda jani,

628
00:48:38,490 --> 00:48:40,790
na kwa kutumia majani ya algorithm inafaa,

629
00:48:40,790 --> 00:48:43,130
itakavyo kuwa vigumu kwa mimi Insert 9 ya kushoto ya 7

630
00:48:43,130 --> 00:48:48,250
kwa sababu kwa haraka kama mimi hit 7 mimi nina kwenda kwa haki.

631
00:48:59,740 --> 00:49:02,070
Je, mtu yeyote kuwa na kitu kuanza na?

632
00:49:02,070 --> 00:49:05,480
[Mwanafunzi] Mimi kufanya. >> Uhakika.

633
00:49:05,480 --> 00:49:09,200
[Mwanafunzi, unintelligible]

634
00:49:09,200 --> 00:49:14,390
[Nyengine mwanafunzi, unintelligible]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Ni appreciated. Sawa. Wanataka kueleza?

636
00:49:18,330 --> 00:49:20,690
>> [Mwanafunzi] Tangu Tunajua kwamba sisi walikuwa inserting

637
00:49:20,690 --> 00:49:24,060
mpya nodes katika mwisho wa mti,

638
00:49:24,060 --> 00:49:28,070
Mimi looped kupitia mti iteratively

639
00:49:28,070 --> 00:49:31,360
mpaka mimi got nodi kwamba alisema kwa null.

640
00:49:31,360 --> 00:49:34,220
Na kisha niliamua kuweka ama upande wa kulia au wa kushoto

641
00:49:34,220 --> 00:49:37,420
kutumia hii variable kulia, ni aliniambia ambapo kuiweka.

642
00:49:37,420 --> 00:49:41,850
Na kisha, kimsingi, mimi tu alifanya kwamba mwisho -

643
00:49:41,850 --> 00:49:47,520
kwamba nodi temp uhakika na nodi ya mwezi kuwa ni kujenga,

644
00:49:47,520 --> 00:49:50,770
ama upande wa kushoto au upande wa kulia, kutegemea na nini thamani kuume ulikuwa.

645
00:49:50,770 --> 00:49:56,530
Mwisho, mimi kuweka mpya wa nodi unafanya thamani kwa thamani ya kupima yake.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Sawa, hivyo mimi kuona suala moja hapa.

647
00:49:59,550 --> 00:50:02,050
Hii ni kama 95% ya njia pale.

648
00:50:02,050 --> 00:50:07,550
suala moja kwamba mimi kuona, vizuri, haina mtu yeyote mwingine kuona suala hilo?

649
00:50:07,550 --> 00:50:18,400
Je, ni hali ya chini ambayo wao kuvunja nje ya kitanzi?

650
00:50:18,400 --> 00:50:22,100
[Mwanafunzi] Kama ni temp null? >> Yeah. Hivyo ni jinsi wewe kuvunja nje ya kitanzi ni kama temp ni null.

651
00:50:22,100 --> 00:50:30,220
Lakini nini mimi hapa hapa?

652
00:50:30,220 --> 00:50:35,410
Mimi dereference temp, ambayo ni inevitably null.

653
00:50:35,410 --> 00:50:39,840
Hivyo kitu kingine unahitaji kufanya ni si tu kuweka wimbo mpaka temp ni null,

654
00:50:39,840 --> 00:50:45,590
unataka kuweka wimbo wa mzazi wakati wote.

655
00:50:45,590 --> 00:50:52,190
Sisi pia wanataka nodi * mzazi, mimi nadhani sisi inaweza kuendelea kuwa katika null mara ya kwanza.

656
00:50:52,190 --> 00:50:55,480
Hii ni kwenda kuwa na tabia weird kwa mizizi ya mti,

657
00:50:55,480 --> 00:50:59,210
lakini tutaweza kupata kwamba.

658
00:50:59,210 --> 00:51:03,950
Kama thamani ni kubwa zaidi kuliko chochote, kisha temp = temp haki.

659
00:51:03,950 --> 00:51:07,910
Lakini kabla ya sisi kufanya hivyo, mzazi = temp.

660
00:51:07,910 --> 00:51:14,500
Au ni wazazi daima kwenda temp sawa? Ni kwamba kesi?

661
00:51:14,500 --> 00:51:19,560
Kama temp si null, basi mimi naenda kwa hoja chini, hakuna jambo gani,

662
00:51:19,560 --> 00:51:24,030
na nodi ambayo ni temp mzazi.

663
00:51:24,030 --> 00:51:27,500
Hivyo mzazi kwenda kuwa temp, na kisha mimi hoja temp chini.

664
00:51:27,500 --> 00:51:32,410
Sasa temp ni null, lakini pointi mzazi na mzazi wa kitu ambacho ni null.

665
00:51:32,410 --> 00:51:39,110
Hivyo hapa chini, mimi sitaki kuweka haki sawa na 1.

666
00:51:39,110 --> 00:51:41,300
Hivyo mimi wakiongozwa na haki, hivyo kama haki = 1,

667
00:51:41,300 --> 00:51:45,130
na mimi nadhani wewe pia wanataka kufanya -

668
00:51:45,130 --> 00:51:48,530
kama hoja kwa upande wa kushoto, unataka kuweka haki sawa ya 0.

669
00:51:48,530 --> 00:51:55,950
Au mwingine kama wewe milele hoja ya haki.

670
00:51:55,950 --> 00:51:58,590
Hivyo haki = 0. Kama haki = 1,

671
00:51:58,590 --> 00:52:04,260
sasa tunataka kufanya mzazi haki pointer newnode,

672
00:52:04,260 --> 00:52:08,520
mwingine tunataka kufanya mzazi kushoto pointer newnode.

673
00:52:08,520 --> 00:52:16,850
Maswali juu ya hilo?

674
00:52:16,850 --> 00:52:24,880
Sawa. Hivyo hii ni njia ya sisi - vizuri, kwa kweli, badala ya kufanya hivyo,

675
00:52:24,880 --> 00:52:29,630
sisi nusu inatarajiwa wewe kutumia build_node.

676
00:52:29,630 --> 00:52:40,450
Na kisha kama newnode sawa null, kurudi uongo.

677
00:52:40,450 --> 00:52:44,170
Hiyo ni kwamba. Sasa, hii ni kile sisi inatarajiwa kufanya.

678
00:52:44,170 --> 00:52:47,690
>> Hii ni nini ufumbuzi wafanyakazi kufanya.

679
00:52:47,690 --> 00:52:52,360
Sikubaliani na hii kama njia ya "haki" ya kwenda kuhusu hilo

680
00:52:52,360 --> 00:52:57,820
lakini hii ni kikamilifu faini na itakuwa kazi.

681
00:52:57,820 --> 00:53:02,840
Jambo moja kwamba ni kidogo weird hivi sasa ni

682
00:53:02,840 --> 00:53:08,310
kama mti huanza mbali kama null, sisi kupita katika mti null.

683
00:53:08,310 --> 00:53:12,650
Nadhani inategemea jinsi unaweza kufafanua tabia ya kupita katika mti null.

684
00:53:12,650 --> 00:53:15,490
Mimi kudhani kwamba kama wewe kupita katika mti null,

685
00:53:15,490 --> 00:53:17,520
kisha kuingiza thamani katika mti null

686
00:53:17,520 --> 00:53:23,030
lazima tu kurudi mti ambapo thamani tu ni kwamba nodi moja.

687
00:53:23,030 --> 00:53:25,830
Je, watu kukubaliana na kwamba? Unaweza, kama alitaka,

688
00:53:25,830 --> 00:53:28,050
ikiwa wewe kupita katika mti null

689
00:53:28,050 --> 00:53:31,320
na unataka Insert thamani ndani yake, kurudi uongo.

690
00:53:31,320 --> 00:53:33,830
Ni juu yako na kufafanua kwamba.

691
00:53:33,830 --> 00:53:38,320
Kwa kufanya jambo la kwanza mimi alisema na kisha -

692
00:53:38,320 --> 00:53:40,720
vizuri, utaenda kuwa na matatizo ya kufanya hivyo, kwa sababu

693
00:53:40,720 --> 00:53:44,090
itakuwa rahisi kama tungekuwa na pointer kimataifa kwa kitu,

694
00:53:44,090 --> 00:53:48,570
lakini hatuna, hivyo kama mti ni null, kuna kitu tunaweza kufanya juu ya hilo.

695
00:53:48,570 --> 00:53:50,960
Tunaweza tu kurudi uongo.

696
00:53:50,960 --> 00:53:52,840
Hivyo nina kwenda kubadili Insert.

697
00:53:52,840 --> 00:53:56,540
Sisi kitaalam inaweza kubadili tu haki hii hapa,

698
00:53:56,540 --> 00:53:58,400
jinsi gani iterating juu ya mambo,

699
00:53:58,400 --> 00:54:04,530
lakini nina kwenda na mabadiliko Insert kuchukua nodi ** mti.

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

701
00:54:07,510 --> 00:54:09,710
Hii ina maana gani?

702
00:54:09,710 --> 00:54:12,330
Badala ya kushughulika na kuyatumia kwa nodes,

703
00:54:12,330 --> 00:54:16,690
kitu nitakacho kuwa manipulating ni hii pointer.

704
00:54:16,690 --> 00:54:18,790
Mimi naenda kuwa manipulating hii pointer.

705
00:54:18,790 --> 00:54:21,770
Mimi naenda kuwa manipulating kuyatumia moja kwa moja.

706
00:54:21,770 --> 00:54:25,760
Hii hufanya akili tangu, kufikiri juu ya chini -

707
00:54:25,760 --> 00:54:33,340
vizuri sasa hivi pointi null.

708
00:54:33,340 --> 00:54:38,130
Nini nataka kufanya ni kuendesha hii pointer kwa uhakika na si null.

709
00:54:38,130 --> 00:54:40,970
Mimi nataka kwa uhakika na nodi yangu mpya.

710
00:54:40,970 --> 00:54:44,870
Kama mimi tu kuweka wimbo wa kuyatumia na kuyatumia yangu,

711
00:54:44,870 --> 00:54:47,840
basi mimi si haja ya kuweka wimbo wa pointer mzazi.

712
00:54:47,840 --> 00:54:52,640
Naweza tu kuweka wimbo kuona kama pointer ni akizungumzia null,

713
00:54:52,640 --> 00:54:54,580
na kama pointer ni akizungumzia null,

714
00:54:54,580 --> 00:54:57,370
mabadiliko hayo kwa uhakika na nodi nataka.

715
00:54:57,370 --> 00:55:00,070
Na ninaweza mabadiliko hayo kwa kuwa nina pointer pointer.

716
00:55:00,070 --> 00:55:02,040
Hebu angalia hii hivi sasa.

717
00:55:02,040 --> 00:55:05,470
Unaweza kweli kufanya hivyo recursively pretty urahisi.

718
00:55:05,470 --> 00:55:08,080
Je, tunataka kufanya hivyo?

719
00:55:08,080 --> 00:55:10,980
Ndiyo, sisi kufanya.

720
00:55:10,980 --> 00:55:16,790
>> Hebu kuona recursively.

721
00:55:16,790 --> 00:55:24,070
Kwanza, ni nini msingi wetu kesi kwenda kuwa?

722
00:55:24,070 --> 00:55:29,140
Karibu daima msingi wetu kesi; lakini kwa kweli, hii ni aina ya gumu.

723
00:55:29,140 --> 00:55:34,370
Kwanza mambo ya kwanza, kama (mti == null)

724
00:55:34,370 --> 00:55:37,550
Nadhani sisi ni kwenda tu kurudi uongo.

725
00:55:37,550 --> 00:55:40,460
Hii ni tofauti na null mti yako kuwa.

726
00:55:40,460 --> 00:55:44,510
Hii ni pointer pointer mizizi yako kuwa null

727
00:55:44,510 --> 00:55:48,360
ambayo ina maana kwamba mizizi yako pointer haipo.

728
00:55:48,360 --> 00:55:52,390
Hivyo hapa chini, kama mimi kufanya

729
00:55:52,390 --> 00:55:55,760
nodi * - wacha tu kutumia tena hii.

730
00:55:55,760 --> 00:55:58,960
Node * mzizi = null,

731
00:55:58,960 --> 00:56:00,730
na kisha mimi naenda kuwaita Insert kwa kufanya kitu kama,

732
00:56:00,730 --> 00:56:04,540
Insert 4 ndani ya mizizi &.

733
00:56:04,540 --> 00:56:06,560
Hivyo & mizizi, mizizi ya mti ikiwa ni * nodi

734
00:56:06,560 --> 00:56:11,170
kisha & mzizi ni kwenda kuwa ** nodi.

735
00:56:11,170 --> 00:56:15,120
Hii ni halali. Katika kesi hiyo, mti, hapa juu,

736
00:56:15,120 --> 00:56:20,120
mti si null - au Insert.

737
00:56:20,120 --> 00:56:24,630
Hapa. Mti si null; * mti ni null, ambayo ni nzuri

738
00:56:24,630 --> 00:56:26,680
kwa sababu kama * mti ni null, naweza kuendesha ni

739
00:56:26,680 --> 00:56:29,210
kwa sasa uhakika na kile Mimi nataka kumweka kwa.

740
00:56:29,210 --> 00:56:34,750
Lakini kama mti ni null, kwamba maana mimi tu alifika hapa na alisema null.

741
00:56:34,750 --> 00:56:42,710
Hiyo haina mantiki. Mimi siwezi kufanya kitu na kwamba.

742
00:56:42,710 --> 00:56:45,540
Kama mti ni null, kurudi uongo.

743
00:56:45,540 --> 00:56:48,220
Hivyo mimi kimsingi tayari alisema nini msingi wetu kesi halisi ni.

744
00:56:48,220 --> 00:56:50,580
Na kile kwamba kwenda kuwa?

745
00:56:50,580 --> 00:56:55,030
[Mwanafunzi, unintelligible]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ndiyo. Hivyo kama (* mti == null).

747
00:57:00,000 --> 00:57:04,520
Hii inahusiana na kesi zaidi ya hapa

748
00:57:04,520 --> 00:57:09,640
ambapo kama pointer yangu nyekundu ni pointer mimi nina ililenga,

749
00:57:09,640 --> 00:57:12,960
hivyo kama mimi nina ililenga pointer hii, sasa mimi nina ililenga pointer hii.

750
00:57:12,960 --> 00:57:15,150
Sasa mimi nina ililenga pointer hii.

751
00:57:15,150 --> 00:57:18,160
Hivyo kama pointer yangu nyekundu, ambayo ni nodi wangu **,

752
00:57:18,160 --> 00:57:22,880
ni milele - kama *, pointer yangu nyekundu, ni milele null,

753
00:57:22,880 --> 00:57:28,470
hiyo ina maana kwamba mimi niko kwenye kesi ambapo mimi nina kulenga pointer kwamba pointi -

754
00:57:28,470 --> 00:57:32,530
hii ni pointer kwamba ni mali ya jani.

755
00:57:32,530 --> 00:57:41,090
Mimi nataka kubadili hili pointer kwa uhakika na nodi yangu mpya.

756
00:57:41,090 --> 00:57:45,230
Njoo nyuma zaidi ya hapa.

757
00:57:45,230 --> 00:57:56,490
Newnode yangu tu kuwa nodi * n = build_node (thamani)

758
00:57:56,490 --> 00:58:07,300
kisha n, ikiwa n = null, kurudi uongo.

759
00:58:07,300 --> 00:58:12,600
Mwingine tunataka kubadili kile pointer sasa akizungumzia

760
00:58:12,600 --> 00:58:17,830
kwa sasa uhakika na nodi wetu wapya kujengwa.

761
00:58:17,830 --> 00:58:20,280
Tunaweza kweli kufanya hivyo hapa.

762
00:58:20,280 --> 00:58:30,660
Badala ya kusema n, tunasema * mti = ikiwa mti *.

763
00:58:30,660 --> 00:58:35,450
Kila mtu kuelewa kwamba? Kwamba kwa kushughulika na kuyatumia kwa kuyatumia,

764
00:58:35,450 --> 00:58:40,750
tunaweza kubadili kuyatumia null kwa uhakika na mambo tunataka yao kwa uhakika na.

765
00:58:40,750 --> 00:58:42,820
Hiyo ni msingi wetu kesi.

766
00:58:42,820 --> 00:58:45,740
>> Sasa upprepning yetu, au recursion yetu,

767
00:58:45,740 --> 00:58:51,430
ni kwenda kuwa ni sawa na recursions mengine yote tumekuwa kufanya.

768
00:58:51,430 --> 00:58:55,830
Sisi ni kwenda unataka Insert thamani,

769
00:58:55,830 --> 00:58:59,040
na sasa mimi naenda kutumia ternary tena, lakini nini ni hali yetu ya kwenda kuwa?

770
00:58:59,040 --> 00:59:05,180
Nini ni sisi ni kuangalia kwa kuamua kama tunataka kwenda kushoto au kulia?

771
00:59:05,180 --> 00:59:07,760
Hebu kufanya hivyo katika hatua tofauti.

772
00:59:07,760 --> 00:59:18,850
Kama (thamani <) nini?

773
00:59:18,850 --> 00:59:23,200
[Mwanafunzi] thamani ya mti?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Basi kumbuka kwamba mimi nina sasa -

775
00:59:27,490 --> 00:59:31,260
[Wanafunzi, unintelligible]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, hivyo hapa hapa, hebu kusema kwamba hii arrow kijani

777
00:59:34,140 --> 00:59:39,050
ni mfano wa nini sasa ni mti, ni pointer pointer hii.

778
00:59:39,050 --> 00:59:46,610
Hivyo kwamba maana mimi ni pointer pointer 3.

779
00:59:46,610 --> 00:59:48,800
dereference mara mbili akapiga nzuri.

780
00:59:48,800 --> 00:59:51,010
Nifanye - jinsi gani mimi kufanya hivyo?

781
00:59:51,010 --> 00:59:53,210
[Mwanafunzi] Dereference mara moja, na kisha kufanya mshale njia?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Basi (* mti) ni dereference mara moja, -> thamani

783
00:59:58,420 --> 01:00:05,960
anaenda kunipa thamani ya nodi kwamba mimi nina moja akizungumzia.

784
01:00:05,960 --> 01:00:11,980
Hivyo siwezi pia kuandika ** tree.value kama unapendelea kwamba.

785
01:00:11,980 --> 01:00:18,490
Aidha kazi.

786
01:00:18,490 --> 01:00:26,190
Kama kwamba ni kesi, kisha Mimi nataka kuwaita Insert na thamani.

787
01:00:26,190 --> 01:00:32,590
Na kile nodi yangu updated ** kwenda kuwa?

788
01:00:32,590 --> 01:00:39,440
Nataka kwenda kwa upande wa kushoto, hivyo ** tree.left ni kwenda kuwa wangu wa kushoto.

789
01:00:39,440 --> 01:00:41,900
Na mimi nataka pointer kitu

790
01:00:41,900 --> 01:00:44,930
hivyo kwamba kama kushoto kuishia kuwa pointer null,

791
01:00:44,930 --> 01:00:48,360
Naweza kurekebisha kwa uhakika na nodi yangu mpya.

792
01:00:48,360 --> 01:00:51,460
>> Na kesi nyingine inaweza kuwa sawa sana.

793
01:00:51,460 --> 01:00:55,600
Hebu kweli kufanya kwamba ternary yangu hivi sasa.

794
01:00:55,600 --> 01:01:04,480
Ingiza thamani kama thamani <(** mti). Thamani.

795
01:01:04,480 --> 01:01:11,040
Kisha tunataka update ** wetu wa kushoto,

796
01:01:11,040 --> 01:01:17,030
mwingine tunataka update ** yetu kwa haki.

797
01:01:17,030 --> 01:01:22,540
[Mwanafunzi] Je, hiyo kupata pointer pointer?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Kumbuka kwamba - ** tree.right ni nyota wa nodi.

799
01:01:30,940 --> 01:01:35,040
[Mwanafunzi, unintelligible] >> Yeah.

800
01:01:35,040 --> 01:01:41,140
** Tree.right ni kama hii pointer au kitu.

801
01:01:41,140 --> 01:01:45,140
Hivyo kwa kuchukua pointer kwamba, anipaye nini nataka

802
01:01:45,140 --> 01:01:50,090
ya pointer guy kwamba.

803
01:01:50,090 --> 01:01:54,260
[Mwanafunzi] Inawezekana sisi kwenda juu tena kwa nini sisi ni kutumia kuyatumia mbili?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Hivyo - hapana, unaweza, na kwamba ufumbuzi kabla ya

805
01:01:58,220 --> 01:02:04,540
ilikuwa ni njia ya kufanya hivyo bila ya kufanya kuyatumia mbili.

806
01:02:04,540 --> 01:02:08,740
Unahitaji kuwa na uwezo wa kuelewa kutumia kuyatumia mbili,

807
01:02:08,740 --> 01:02:11,660
na hii ni ufumbuzi safi.

808
01:02:11,660 --> 01:02:16,090
Pia, ona kwamba, kile kinachotokea kama mti wangu -

809
01:02:16,090 --> 01:02:24,480
kile kinachotokea kama mzizi yangu ilikuwa null? Nini kinatokea kama mimi kufanya kesi hii hapa hapa?

810
01:02:24,480 --> 01:02:30,540
Hivyo nodi * mzizi = null, ingiza 4 ndani ya mizizi &.

811
01:02:30,540 --> 01:02:35,110
Nini mizizi kwenda kuwa baada ya hili?

812
01:02:35,110 --> 01:02:37,470
[Mwanafunzi, unintelligible] >> Yeah.

813
01:02:37,470 --> 01:02:41,710
Mizizi thamani ni kwenda kuwa 4.

814
01:02:41,710 --> 01:02:45,510
Mizizi kushoto ni kwenda kuwa null, mzizi haki ni kwenda kuwa null.

815
01:02:45,510 --> 01:02:49,490
Katika kesi ambapo hatukuwa kupita mizizi na anuani,

816
01:02:49,490 --> 01:02:52,490
hatukuweza kurekebisha mizizi.

817
01:02:52,490 --> 01:02:56,020
Katika kesi ambapo mti - mizizi ambapo alikuwa null,

818
01:02:56,020 --> 01:02:58,410
sisi tu alikuwa na kurudi uongo. Kuna kitu tunaweza kufanya.

819
01:02:58,410 --> 01:03:01,520
Hatuwezi kuingiza nodi katika mti tupu.

820
01:03:01,520 --> 01:03:06,810
Lakini sasa tunaweza; sisi tu kufanya mti tupu ndani ya mti mmoja wa nodi.

821
01:03:06,810 --> 01:03:13,400
Ambayo ni kawaida njia inatarajiwa kwamba ni walidhani kazi.

822
01:03:13,400 --> 01:03:21,610
>> Aidha, hii ni kwa kiasi kikubwa mfupi kuliko

823
01:03:21,610 --> 01:03:26,240
pia kuweka wimbo wa mzazi, na hivyo iterate chini njia yote.

824
01:03:26,240 --> 01:03:30,140
Sasa nina mzazi wangu, na mimi tu na mzazi wangu wa kulia pointer chochote.

825
01:03:30,140 --> 01:03:35,640
Badala yake, kama sisi alifanya hivyo iteratively, ni d kuwa wazo moja na kitanzi wakati.

826
01:03:35,640 --> 01:03:38,100
Lakini badala ya kuwa ili kukabiliana na mzazi pointer yangu,

827
01:03:38,100 --> 01:03:40,600
badala pointer yangu sasa itakuwa jambo

828
01:03:40,600 --> 01:03:43,790
kwamba mimi nina moja kwa moja kubadilisha kwa uhakika na nodi yangu mpya.

829
01:03:43,790 --> 01:03:46,090
Mimi wala kuwa na kushughulika na kama ni akizungumzia kushoto.

830
01:03:46,090 --> 01:03:48,810
Mimi wala kuwa na kushughulika na kama ni akizungumzia haki.

831
01:03:48,810 --> 01:04:00,860
Ni tu chochote pointer hii, mimi nina kwenda kuweka kwa uhakika na nodi yangu mpya.

832
01:04:00,860 --> 01:04:05,740
Kila mtu kuelewa jinsi kazi?

833
01:04:05,740 --> 01:04:09,460
Kama siyo kwa nini tunataka kufanya ni njia hii,

834
01:04:09,460 --> 01:04:14,920
lakini angalau kwamba kazi hii kama suluhisho?

835
01:04:14,920 --> 01:04:17,110
[Mwanafunzi] wapi sisi kurudi kweli?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Hiyo pengine hapa hapa.

837
01:04:21,550 --> 01:04:26,690
Kama sisi usahihi kuingiza, kurudi kweli.

838
01:04:26,690 --> 01:04:32,010
Mwingine, chini hapa tunakwenda unataka kurudi anarudi Insert chochote.

839
01:04:32,010 --> 01:04:35,950
>> Na nini maalum kuhusu kazi hii ya kujirudia?

840
01:04:35,950 --> 01:04:43,010
Ni mkia kujirudia, hivyo muda mrefu kama sisi kukusanya na optimization baadhi,

841
01:04:43,010 --> 01:04:48,060
itakuwa kutambua kuwa na wewe kamwe kupata kufurika stack kutoka hii,

842
01:04:48,060 --> 01:04:53,230
hata kama mti yetu ina urefu wa 10,000 au milioni 10.

843
01:04:53,230 --> 01:04:55,630
[Mwanafunzi, unintelligible]

844
01:04:55,630 --> 01:05:00,310
[Bowden] nadhani ni gani katika Dash - au nini optimization ngazi

845
01:05:00,310 --> 01:05:03,820
inahitajika kwa ajili ya recursion mkia na kutambuliwa.

846
01:05:03,820 --> 01:05:09,350
Nadhani inatambua - GCC na Clang

847
01:05:09,350 --> 01:05:12,610
pia kuwa na maana tofauti kwa viwango vyao optimization.

848
01:05:12,610 --> 01:05:17,870
Mimi nataka kusema ni DashO 2, kwa uhakika kwamba ni mapenzi kutambua recursion mkia.

849
01:05:17,870 --> 01:05:27,880
Lakini sisi - unaweza kujenga kama mfano Fibonocci au kitu.

850
01:05:27,880 --> 01:05:30,030
Siyo rahisi kwa mtihani na hii, kwa sababu ni vigumu kujenga

851
01:05:30,030 --> 01:05:32,600
mti binary kwamba hivyo kubwa.

852
01:05:32,600 --> 01:05:37,140
Lakini yeah, nadhani ni DashO 2, kwamba

853
01:05:37,140 --> 01:05:40,580
kama wewe kukusanya na DashO 2, itakuwa kuangalia kwa recursion mkia

854
01:05:40,580 --> 01:05:54,030
na optimize kwamba nje.

855
01:05:54,030 --> 01:05:58,190
Turudi kwa - Insert ni literally jambo la mwisho ni mahitaji.

856
01:05:58,190 --> 01:06:04,900
Turudi kwa Insert juu hapa

857
01:06:04,900 --> 01:06:07,840
ambapo sisi ni kwenda kufanya wazo moja.

858
01:06:07,840 --> 01:06:14,340
Ni utakuwa bado kuwa na flaw ya kutokuwa na uwezo wa kushughulikia kabisa

859
01:06:14,340 --> 01:06:17,940
wakati mizizi yenyewe ni null, au kuingia zamani ni null,

860
01:06:17,940 --> 01:06:20,060
lakini badala ya kushughulika na pointer mzazi,

861
01:06:20,060 --> 01:06:27,430
hebu kuomba mantiki hiyo hiyo ya kuyatumia kutunza na kuyatumia.

862
01:06:27,430 --> 01:06:35,580
Kama hapa sisi kushika nodi zetu ** cur,

863
01:06:35,580 --> 01:06:37,860
na hatuna haja ya kuweka wimbo wa kulia tena,

864
01:06:37,860 --> 01:06:47,190
lakini nodi ** cur = & mti.

865
01:06:47,190 --> 01:06:54,800
Na sasa wakati wetu kitanzi ni kwenda kuwa wakati * cur haina null sawa.

866
01:06:54,800 --> 01:07:00,270
Hawana haja ya kuweka wimbo wa wazazi tena.

867
01:07:00,270 --> 01:07:04,180
Hawana haja ya kuweka wimbo wa kushoto na kulia.

868
01:07:04,180 --> 01:07:10,190
Na mimi itabidi kuiita temp, kwa sababu tuko tayari kutumia temp.

869
01:07:10,190 --> 01:07:17,200
Sawa. Hivyo kama (thamani> * temp),

870
01:07:17,200 --> 01:07:24,010
kisha & (* temp) -> kulia

871
01:07:24,010 --> 01:07:29,250
mwingine temp = & (* temp) -> kushoto.

872
01:07:29,250 --> 01:07:32,730
Na sasa, katika hatua hii, baada ya hii kitanzi wakati,

873
01:07:32,730 --> 01:07:36,380
Mimi tu kufanya hivyo kwa sababu labda ni rahisi kufikiri juu iteratively kuliko recursively,

874
01:07:36,380 --> 01:07:39,010
lakini baada ya hii kitanzi wakati,

875
01:07:39,010 --> 01:07:43,820
* Temp ni pointer tunataka kubadili.

876
01:07:43,820 --> 01:07:48,960
>> Kabla ya hapo tulikuwa mzazi, na sisi alitaka mabadiliko aidha kushoto mzazi au mzazi wa kulia,

877
01:07:48,960 --> 01:07:51,310
lakini kama tunataka kubadili mzazi wa kulia,

878
01:07:51,310 --> 01:07:54,550
kisha * temp ni mzazi wa kulia, na tunaweza kubadilisha hiyo moja kwa moja.

879
01:07:54,550 --> 01:08:05,860
Hivyo hapa chini, tunaweza kufanya * temp = newnode, na hiyo ni yake.

880
01:08:05,860 --> 01:08:09,540
Hivyo taarifa, wote sisi gani katika hii ilikuwa kuchukua mstari wa kanuni.

881
01:08:09,540 --> 01:08:14,770
Ili kuweka wimbo wa mzazi katika yote ni nyongeza ya jitihada.

882
01:08:14,770 --> 01:08:18,689
Hapa, kama sisi tu kuweka wimbo wa pointer pointer,

883
01:08:18,689 --> 01:08:22,990
na hata kama sisi alitaka kujikwamua hizi braces wote curly sasa,

884
01:08:22,990 --> 01:08:27,170
kufanya ni kuangalia mfupi.

885
01:08:27,170 --> 01:08:32,529
Hii sasa ni exact ufumbuzi,

886
01:08:32,529 --> 01:08:38,210
lakini wachache mstari wa kanuni.

887
01:08:38,210 --> 01:08:41,229
Mara baada ya kuanza hii kutambua kama ufumbuzi halali,

888
01:08:41,229 --> 01:08:43,529
pia ni rahisi sababu ya juu kuliko kama, sawa,

889
01:08:43,529 --> 01:08:45,779
kwa nini nina hii bendera kulia int?

890
01:08:45,779 --> 01:08:49,290
Hiyo ina maana gani? Oh, ni akionyesha kwamba

891
01:08:49,290 --> 01:08:51,370
kila wakati mimi kwenda kulia, nahitaji kuweka,

892
01:08:51,370 --> 01:08:53,819
mwingine kama mimi kwenda kushoto nahitaji kuweka kwa sifuri.

893
01:08:53,819 --> 01:09:04,060
Hapa, mimi hawana sababu juu ya kwamba, ni rahisi tu kufikiria.

894
01:09:04,060 --> 01:09:06,710
Maswali?

895
01:09:06,710 --> 01:09:16,290
[Mwanafunzi, unintelligible] >> Yeah.

896
01:09:16,290 --> 01:09:23,359
Okay, kwa hivyo katika kidogo mwisho -

897
01:09:23,359 --> 01:09:28,080
Nadhani moja ya haraka na rahisi kazi tunaweza kufanya ni,

898
01:09:28,080 --> 01:09:34,910
let's - pamoja, mimi nadhani, kujaribu na kuandika ina kazi

899
01:09:34,910 --> 01:09:38,899
ambayo haina huduma kama ni binary tafuta mti.

900
01:09:38,899 --> 01:09:43,770
Hii ina kazi lazima kurudi kweli

901
01:09:43,770 --> 01:09:58,330
kama mahali popote katika mti huu jumla binary ni thamani sisi ni kuangalia kwa.

902
01:09:58,330 --> 01:10:02,520
Basi hebu kwanza kufanya hivyo recursively na kisha tutaweza kufanya hivyo iteratively.

903
01:10:02,520 --> 01:10:07,300
Tunaweza kweli tu kufanya hivyo pamoja, kwa sababu hii ni ya kwenda kuwa kweli mfupi.

904
01:10:07,300 --> 01:10:11,510
>> Nini msingi wangu kesi kwenda kuwa?

905
01:10:11,510 --> 01:10:13,890
[Mwanafunzi, unintelligible]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Hivyo kama (mti == null), basi nini?

907
01:10:18,230 --> 01:10:22,740
[Mwanafunzi] Kurudi uongo.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, vizuri, sihitaji mwingine.

909
01:10:26,160 --> 01:10:30,250
Kama ilikuwa msingi yangu nyingine kesi.

910
01:10:30,250 --> 01:10:32,450
[Mwanafunzi] Tree wa thamani? >> Yeah.

911
01:10:32,450 --> 01:10:36,430
Hivyo kama (mti-> thamani == thamani.

912
01:10:36,430 --> 01:10:39,920
Kumbuka hatuna nyuma * nodi, si nodi ** s?

913
01:10:39,920 --> 01:10:42,990
Ina kamwe haja ya kutumia ** nodi,

914
01:10:42,990 --> 01:10:45,480
tangu sisi si kubadilisha kuyatumia.

915
01:10:45,480 --> 01:10:50,540
Sisi ni tu traversing yao.

916
01:10:50,540 --> 01:10:53,830
Kama kwamba hutokea, basi tunataka kurudi kweli.

917
01:10:53,830 --> 01:10:58,270
Mwingine tunataka traverse watoto.

918
01:10:58,270 --> 01:11:02,620
Hivyo hatuwezi kufikiri kuhusu kama kila kitu kwa upande wa kushoto ni chini

919
01:11:02,620 --> 01:11:05,390
na kila kitu kwa kulia, ni mkubwa.

920
01:11:05,390 --> 01:11:09,590
Hivyo kile ni hali yetu ya kwenda kuwa hapa - au, nini sisi kwenda kufanya?

921
01:11:09,590 --> 01:11:11,840
[Mwanafunzi, unintelligible] >> Yeah.

922
01:11:11,840 --> 01:11:17,400
Kurudi ina (thamani, mti-> kushoto)

923
01:11:17,400 --> 01:11:26,860
au ina (thamani, mti-> kulia). Na kwamba ni.

924
01:11:26,860 --> 01:11:29,080
Na taarifa kuna baadhi ya tathmini short-mzunguko,

925
01:11:29,080 --> 01:11:32,520
ambapo kama sisi kutokea kwa kupata thamani katika mti wa kushoto,

926
01:11:32,520 --> 01:11:36,820
sisi kamwe haja ya kuangalia mti wa kulia.

927
01:11:36,820 --> 01:11:40,430
Hiyo ni kazi nzima.

928
01:11:40,430 --> 01:11:43,690
Sasa hebu kufanya hivyo iteratively,

929
01:11:43,690 --> 01:11:48,060
ambayo ni kwenda kuwa chini nice.

930
01:11:48,060 --> 01:11:54,750
Tutaweza kuchukua kuanza kawaida ya cur nodi * = mti.

931
01:11:54,750 --> 01:12:03,250
Wakati (cur = null!).

932
01:12:03,250 --> 01:12:08,600
Haraka kwenda kuona tatizo.

933
01:12:08,600 --> 01:12:12,250
Kama cur - nje hapa, kama sisi milele kuvunja nje ya hili,

934
01:12:12,250 --> 01:12:16,020
kisha tumekuwa kukimbia nje ya mambo ya kuangalia, hivyo kurudi uongo.

935
01:12:16,020 --> 01:12:24,810
Kama (cur-> thamani == thamani), kurudi kweli.

936
01:12:24,810 --> 01:12:32,910
Hivyo sasa, sisi ni katika nafasi -

937
01:12:32,910 --> 01:12:36,250
sisi hatujui kama tunataka kwenda kushoto au kulia.

938
01:12:36,250 --> 01:12:44,590
Hivyo kiholela, hebu tu kwenda kushoto.

939
01:12:44,590 --> 01:12:47,910
Nimekuwa wazi kukimbia katika suala ambapo nimekuwa kabisa kutelekezwa kila kitu -

940
01:12:47,910 --> 01:12:50,760
Nami milele tu kuangalia upande wa kushoto wa mti.

941
01:12:50,760 --> 01:12:56,050
Mimi kamwe chochote ambacho ni kuangalia mtoto haki ya kitu chochote.

942
01:12:56,050 --> 01:13:00,910
Je, mimi kurekebisha hili?

943
01:13:00,910 --> 01:13:05,260
[Mwanafunzi] Una kuweka wimbo wa kushoto na kulia katika stack.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Basi hebu kufanya hivyo

945
01:13:13,710 --> 01:13:32,360
struct orodha, nodi * n, na kisha nodi ** ijayo?

946
01:13:32,360 --> 01:13:40,240
Nadhani kwamba kazi nzuri.

947
01:13:40,240 --> 01:13:45,940
Tunataka kwenda juu ya kushoto, au let's - hapa juu.

948
01:13:45,940 --> 01:13:54,350
Struct orodha orodha =, hivyo itabidi kuanza

949
01:13:54,350 --> 01:13:58,170
nje katika orodha hii struct.

950
01:13:58,170 --> 01:14:04,040
* = Orodha null. Ili kwenda kuwa orodha yetu zilizounganishwa

951
01:14:04,040 --> 01:14:08,430
ya subtrees kwamba tuna skipped juu.

952
01:14:08,430 --> 01:14:13,800
Sisi ni kwenda Traverse kushoto sasa,

953
01:14:13,800 --> 01:14:17,870
lakini tangu sisi inevitably haja ya kurudi kwa haki,

954
01:14:17,870 --> 01:14:26,140
Sisi ni kwenda kuweka upande wa kulia ndani ya struct orodha yetu.

955
01:14:26,140 --> 01:14:32,620
Kisha sisi itabidi new_list au struct,

956
01:14:32,620 --> 01:14:41,080
struct orodha *, new_list = malloc (sizeof (orodha)).

957
01:14:41,080 --> 01:14:44,920
Mimi naenda kupuuza kosa-kuangalia kwamba, lakini unapaswa kuangalia kuona kama ni null.

958
01:14:44,920 --> 01:14:50,540
New_list nodi ni kwenda kwa uhakika na -

959
01:14:50,540 --> 01:14:56,890
oh, hiyo ndiyo sababu nilitaka it up hapa. Ni kwenda na kumweka kwa orodha ya pili struct.

960
01:14:56,890 --> 01:15:02,380
Hiyo tu jinsi wanaohusishwa orodha ya kazi.

961
01:15:02,380 --> 01:15:04,810
Hii ni sawa kama orodha int wanaohusishwa

962
01:15:04,810 --> 01:15:06,960
ila tuko tu kuondoa int na * nodi.

963
01:15:06,960 --> 01:15:11,040
Ni sawa.

964
01:15:11,040 --> 01:15:15,100
Hivyo new_list, thamani ya new_list nodi zetu,

965
01:15:15,100 --> 01:15:19,120
ni kwenda kuwa cur-> kulia.

966
01:15:19,120 --> 01:15:24,280
thamani ya yetu new_list-> ijayo itakuwa ni orodha yetu ya awali,

967
01:15:24,280 --> 01:15:30,760
na kisha tunakwenda update orodha yetu kwa uhakika na new_list.

968
01:15:30,760 --> 01:15:33,650
>> Sasa tunahitaji baadhi ya aina ya njia ya mambo kuunganisha,

969
01:15:33,650 --> 01:15:37,020
kama tuna traversed nzima kushoto subtree.

970
01:15:37,020 --> 01:15:40,480
Sasa tunahitaji vuta stuff nje ya hayo,

971
01:15:40,480 --> 01:15:43,850
kama cur ni null; hatutaki tu kurudi uongo.

972
01:15:43,850 --> 01:15:50,370
Tunataka sasa vuta nje katika orodha yetu mpya.

973
01:15:50,370 --> 01:15:53,690
njia rahisi ya kufanya hivyo - vizuri, kwa kweli, kuna nyingi njia ya kufanya hili.

974
01:15:53,690 --> 01:15:56,680
Mtu yeyote kuwa pendekezo?

975
01:15:56,680 --> 01:15:58,790
Ambapo mimi lazima kufanya hivyo au jinsi mimi lazima kufanya hivyo?

976
01:15:58,790 --> 01:16:08,010
Sisi tu dakika kadhaa, lakini mapendekezo yoyote?

977
01:16:08,010 --> 01:16:14,750
Badala ya - njia moja, badala ya hali yetu ya kuwa wakati,

978
01:16:14,750 --> 01:16:17,090
nini sasa tuko kuangalia si null,

979
01:16:17,090 --> 01:16:22,340
badala ya sisi ni kwenda kuendelea kwenda mpaka orodha yetu yenyewe ni null.

980
01:16:22,340 --> 01:16:25,680
Hivyo kama orodha yetu kuishia kuwa null,

981
01:16:25,680 --> 01:16:30,680
kisha sisi kukimbia nje ya mambo kwa kuangalia, kutafuta zaidi.

982
01:16:30,680 --> 01:16:39,860
Lakini hiyo ina maana kwamba jambo la kwanza katika orodha yetu ni kwenda tu kuwa nodi kwanza.

983
01:16:39,860 --> 01:16:49,730
kitu ya kwanza kabisa itakuwa - sisi tena haja ya kuona kwamba.

984
01:16:49,730 --> 01:16:58,710
Hivyo orodha-> n itakuwa mti wetu.

985
01:16:58,710 --> 01:17:02,860
orodha-> ijayo itakuwa ni null.

986
01:17:02,860 --> 01:17:07,580
Na sasa wakati orodha haina null sawa.

987
01:17:07,580 --> 01:17:11,610
Cur ni kwenda kuvuta kitu kutoka orodha yetu.

988
01:17:11,610 --> 01:17:13,500
Hivyo cur inaenda sawa orodha-> n.

989
01:17:13,500 --> 01:17:20,850
Na kisha orodha ni kwenda sawa orodha-> n, au orodha-> ijayo.

990
01:17:20,850 --> 01:17:23,480
Hivyo kama cur thamani sawa na thamani.

991
01:17:23,480 --> 01:17:28,790
Sasa tunaweza kuongeza wote haki yetu pointer na pointer wetu wa kushoto

992
01:17:28,790 --> 01:17:32,900
muda mrefu kama wao siyo null.

993
01:17:32,900 --> 01:17:36,390
Hapa chini, mimi nadhani tunapaswa wamefanya hivyo katika nafasi ya kwanza.

994
01:17:36,390 --> 01:17:44,080
Kama (cur-> kulia =! Null)

995
01:17:44,080 --> 01:17:56,380
basi sisi ni kwenda Insert kwamba nodi katika orodha yetu.

996
01:17:56,380 --> 01:17:59,290
Kama (cur-> kushoto), hii ni kidogo kidogo ya kazi ya ziada, lakini ni nzuri.

997
01:17:59,290 --> 01:18:02,690
Kama (cur-> kushoto =! Null),

998
01:18:02,690 --> 01:18:14,310
na sisi ni kwenda Insert kushoto katika orodha yetu wanaohusishwa,

999
01:18:14,310 --> 01:18:19,700
na kwamba lazima iwe hivyo.

1000
01:18:19,700 --> 01:18:22,670
Sisi iterate - kwa muda mrefu kama tuna kitu katika orodha yetu,

1001
01:18:22,670 --> 01:18:26,640
tuna mwingine nodi kuangalia.

1002
01:18:26,640 --> 01:18:28,920
Hivyo sisi kuangalia nodi kwamba,

1003
01:18:28,920 --> 01:18:31,390
sisi kuendeleza orodha yetu ya moja ijayo.

1004
01:18:31,390 --> 01:18:34,060
Kama nodi kwamba ni thamani sisi ni kuangalia kwa, tunaweza kurudi kweli.

1005
01:18:34,060 --> 01:18:37,640
Mwingine Insert wote wetu subtrees kushoto na kulia,

1006
01:18:37,640 --> 01:18:40,510
muda mrefu kama wao siyo null, katika orodha yetu

1007
01:18:40,510 --> 01:18:43,120
ili sisi inevitably kwenda juu yao.

1008
01:18:43,120 --> 01:18:45,160
Hivyo kama walikuwa si null,

1009
01:18:45,160 --> 01:18:47,950
mizizi ya mti ikiwa wetu pointer zimeelekezwa kwa mambo mawili,

1010
01:18:47,950 --> 01:18:51,670
kisha saa ya kwanza sisi vunjwa kitu nje hivyo orodha yetu kuishia kuwa null.

1011
01:18:51,670 --> 01:18:56,890
Na kisha sisi kuweka mambo mawili nyuma katika, hivyo sasa orodha yetu ni ya kawaida 2.

1012
01:18:56,890 --> 01:19:00,030
Kisha tunakwenda kitanzi nyuma juu na sisi ni tu kwenda kuvuta,

1013
01:19:00,030 --> 01:19:04,250
hebu sema, pointer kushoto wa mizizi nodi zetu.

1014
01:19:04,250 --> 01:19:07,730
Na kwamba nitaendelea yanafanyika, sisi kuishia looping juu ya kila kitu.

1015
01:19:07,730 --> 01:19:11,280
>> Ona kwamba hii ilikuwa ngumu zaidi kwa kiasi kikubwa

1016
01:19:11,280 --> 01:19:14,160
katika ufumbuzi kujirudia.

1017
01:19:14,160 --> 01:19:17,260
Na nimekuwa alisema mara nyingi

1018
01:19:17,260 --> 01:19:25,120
kwamba ufumbuzi kujirudia kawaida ana mengi kwa pamoja na iterative ufumbuzi.

1019
01:19:25,120 --> 01:19:30,820
Hapa hii ni nini hasa ufumbuzi kujirudia ni kufanya.

1020
01:19:30,820 --> 01:19:36,740
mabadiliko tu ni kwamba badala ya kutumia implicitly stack, stack mpango,

1021
01:19:36,740 --> 01:19:40,840
kama njia yako ya kuweka wimbo wa nini nodes wewe bado haja ya kutembelea,

1022
01:19:40,840 --> 01:19:45,430
sasa una kupanga kutumia orodha zilizounganishwa.

1023
01:19:45,430 --> 01:19:49,070
Katika kesi zote wewe ni kuweka wimbo wa nini nodi bado inahitaji alitembelea.

1024
01:19:49,070 --> 01:19:51,790
Katika kesi ya kujirudia ni rahisi tu kwa sababu stack

1025
01:19:51,790 --> 01:19:57,100
unatekelezwa kwa wewe kama stack mpango.

1026
01:19:57,100 --> 01:19:59,550
Ona kwamba orodha hii wanaohusishwa, ni stack.

1027
01:19:59,550 --> 01:20:01,580
Chochote sisi tu ya kuweka juu ya stack

1028
01:20:01,580 --> 01:20:09,960
ni mara moja nini tuko kwenda kuvuta mbali stack kutembelea ijayo.

1029
01:20:09,960 --> 01:20:14,380
Sisi ni nje ya muda, lakini maswali yoyote?

1030
01:20:14,380 --> 01:20:23,530
[Mwanafunzi, unintelligible]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Hivyo kama tuna orodha yetu zilizounganishwa,

1032
01:20:27,790 --> 01:20:30,150
sasa inaenda kwa guy hii,

1033
01:20:30,150 --> 01:20:34,690
na sasa tuko tu kuendeleza orodha yetu zilizounganishwa kuzingatia guy.

1034
01:20:34,690 --> 01:20:44,200
Sisi ni traversing zaidi ya orodha wanaohusishwa katika mstari huo.

1035
01:20:44,200 --> 01:20:51,200
Na kisha mimi nadhani sisi wamkomboe orodha yetu zilizounganishwa na stuff

1036
01:20:51,200 --> 01:20:53,880
mara moja kabla ya kurejea kweli au uongo, tunahitaji

1037
01:20:53,880 --> 01:20:57,360
iterate juu ya orodha yetu wanaohusishwa na daima chini hapa, mimi nadhani,

1038
01:20:57,360 --> 01:21:03,900
kama sisi cur haki si sawa, kuongeza kuwa, hivyo sasa tunataka huru

1039
01:21:03,900 --> 01:21:09,600
cur kwa sababu, vizuri, hatukuwa kusahau kabisa kuhusu orodha? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Hivyo kwamba ni nini tunataka kufanya hapa.

1041
01:21:12,880 --> 01:21:16,730
Wapi pointer?

1042
01:21:16,730 --> 01:21:23,320
Cur alikuwa kisha - tunataka orodha struct * 10 sawa na orodha inayofuata.

1043
01:21:23,320 --> 01:21:29,240
Bure orodha, orodha = temp.

1044
01:21:29,240 --> 01:21:32,820
Na katika kesi ambapo sisi kurudi kweli, hatuna haja ya iterate

1045
01:21:32,820 --> 01:21:37,050
juu ya salio ya orodha yetu zilizounganishwa kumkomboa mambo.

1046
01:21:37,050 --> 01:21:39,700
Jambo zuri kuhusu ufumbuzi kujirudia ni kumkomboa mambo

1047
01:21:39,700 --> 01:21:44,930
njia tu factorings popping mbali stack ambayo kitatokea kwa ajili yenu.

1048
01:21:44,930 --> 01:21:50,720
Hivyo tumeenda kutoka kitu ambacho ni kama mistari 3 ya maadili ngumu-kwa-kufikiri kuhusu-

1049
01:21:50,720 --> 01:21:57,520
kitu ambacho ni kikubwa zaidi wengi ngumu-kwa-kufikiri-kuhusu mstari wa kanuni.

1050
01:21:57,520 --> 01:22:00,620
Tena maswali?

1051
01:22:00,620 --> 01:22:08,760
Wote haki. Sisi ni nzuri. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]