1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Pjesa 7: më të rehatshme]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Universiteti i Harvardit]

3
00:00:05,090 --> 00:00:07,930
[Kjo është CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Dakord. Pra, si unë, tha në email tim

5
00:00:10,110 --> 00:00:14,060
kjo do të jetë një binar-pemë-intensive seksion.

6
00:00:14,060 --> 00:00:16,820
Por nuk ka shumë pyetje që.

7
00:00:16,820 --> 00:00:18,920
Pra, ne jemi duke shkuar për të përpiqen dhe të tërheqë nga çdo pyetjeje

8
00:00:18,920 --> 00:00:25,430
dhe të shkojnë në detaje të dhimbshme të gjitha mënyrat më të mira për të bërë gjërat.

9
00:00:25,430 --> 00:00:31,200
Në mënyrë të drejtë në fillim, ne do të shkojmë përmes vizatimeve mostër e pemëve dhe sende binar.

10
00:00:31,200 --> 00:00:35,970
Kështu që këtu, "Mos harroni se një pemë binare ka nyje të ngjashme me ato të një liste të lidhura,

11
00:00:35,970 --> 00:00:38,150
përveç në vend të një akrep nuk janë dy: një për 'fëmijë' së majtës

12
00:00:38,150 --> 00:00:41,950
dhe një për "fëmijën" e djathtë ".

13
00:00:41,950 --> 00:00:45,630
Kështu që një pemë binare është vetëm si një listë e lidhur,

14
00:00:45,630 --> 00:00:47,910
përveç struct do të ketë dy pointers.

15
00:00:47,910 --> 00:00:51,390
Ka pemë trinary, të cilat do të ketë tre pointers,

16
00:00:51,390 --> 00:00:56,540
ka N-ARY pemë, të cilat vetëm kanë një tregues gjenerike

17
00:00:56,540 --> 00:01:00,320
që atëherë ju duhet të malloc të jetë mjaft e madhe që të ketë

18
00:01:00,320 --> 00:01:04,840
pointers të mjaftueshme për të gjithë fëmijët e mundshme.

19
00:01:04,840 --> 00:01:08,200
Pra, pemë binare vetëm ndodh që të ketë një numër të vazhdueshëm të dy.

20
00:01:08,200 --> 00:01:11,260
Në qoftë se ju dëshironi, ju mund të jepni një listë të lidhur si një pemë unary,

21
00:01:11,260 --> 00:01:15,360
por unë nuk mendoj se dikush e quan atë se.

22
00:01:15,360 --> 00:01:18,060
"Vizatoni një diagram kuti-dhe-shigjeta e një nyje pemë binare

23
00:01:18,060 --> 00:01:24,110
përmbajnë numrin e preferuar Nate-së, 7, ku çdo fëmijë është tregues null. "

24
00:01:24,110 --> 00:01:27,780
Mënyra kështu iPad.

25
00:01:27,780 --> 00:01:30,280
>> Ajo do të jetë shumë i thjeshtë.

26
00:01:30,280 --> 00:01:36,150
Ne jemi vetëm do të ketë një nyje, unë do të tërheqë atë si një shesh.

27
00:01:36,150 --> 00:01:38,730
Dhe unë do të të nxjerrë vlerat në këtu.

28
00:01:38,730 --> 00:01:41,090
Pra, vlera do të shkojnë në këtu,

29
00:01:41,090 --> 00:01:44,770
dhe pastaj këtu poshtë ne do të kemi në treguesin e majtë në të majtë dhe të djathtë kursorin në të djathtë.

30
00:01:44,770 --> 00:01:50,430
Dhe kjo është shumë e shumë në mënyrë konventë për të thirrur atë majtas dhe djathtas, emrat tregues.

31
00:01:50,430 --> 00:01:52,460
Të dyja këto do të jenë null.

32
00:01:52,460 --> 00:01:57,870
Kjo do të jetë vetëm null, dhe se do të jetë vetëm null.

33
00:01:57,870 --> 00:02:03,630
Rregull. Pra, përsëri në këtu.

34
00:02:03,630 --> 00:02:05,700
"Me një listë e lidhur, ne vetëm kishte për të ruajtur një akrep

35
00:02:05,700 --> 00:02:09,639
në nyjen e parë në listën në mënyrë që të mos harroni krejt Listen lidhur, ose listë e tërë.

36
00:02:09,639 --> 00:02:11,650
Gjithashtu, me pemë, ne kemi vetëm për të ruajtur një akrep

37
00:02:11,650 --> 00:02:13,420
në një nyje të vetme, në mënyrë për të kujtuar pemë të tërë.

38
00:02:13,420 --> 00:02:15,980
Kjo nyjë është calle 'root' nga pema.

39
00:02:15,980 --> 00:02:18,320
Të ndërtuar mbi diagramin tuaj para ose vizatoni një të re

40
00:02:18,320 --> 00:02:21,690
të tilla që ju keni një përshkrim kuti-dhe-shigjeta e një pemë binare

41
00:02:21,690 --> 00:02:25,730
me vlerën 7, pastaj 3 në të majtë,

42
00:02:25,730 --> 00:02:32,760
atëherë 9 në të drejtë, dhe pastaj 6 në të djathtë të 3. "

43
00:02:32,760 --> 00:02:34,810
Le të shohim nëse unë mund të kujtoj të gjithë se në kokën time.

44
00:02:34,810 --> 00:02:37,670
Pra, kjo do të jetë root tonë deri këtu.

45
00:02:37,670 --> 00:02:41,600
Ne do të kemi disa tregues diku, diçka që ne do të quajmë rrënjë,

46
00:02:41,600 --> 00:02:45,140
dhe kjo është treguar këtë djalë.

47
00:02:45,140 --> 00:02:48,490
Tani për të bërë një nyje të re,

48
00:02:48,490 --> 00:02:52,870
çfarë kemi, 3 në të majtë?

49
00:02:52,870 --> 00:02:57,140
Pra, një nyje e re me 3, dhe kjo fillimisht vë null.

50
00:02:57,140 --> 00:02:59,190
Unë vetëm do të vënë N.

51
00:02:59,190 --> 00:03:02,250
Tani ne duam të bëjë që të shkojnë në të majtë të 7.

52
00:03:02,250 --> 00:03:06,840
Pra, ne ndryshojmë këtë tregues më tani tregojnë për këtë djalë.

53
00:03:06,840 --> 00:03:12,420
Dhe ne bëjmë të njëjtën gjë. Ne duam një 9 mbi këtu

54
00:03:12,420 --> 00:03:14,620
e cila fillimisht vetëm thotë null.

55
00:03:14,620 --> 00:03:19,600
Ne jemi duke shkuar për të ndryshuar këtë pikë, akrep në 9,

56
00:03:19,600 --> 00:03:23,310
dhe tani ne duam të vënë 6 të drejtën e 3.

57
00:03:23,310 --> 00:03:32,170
Kështu ajo do të - të bëjë një 6.

58
00:03:32,170 --> 00:03:34,310
Dhe kjo do të tregojë djalë atje.

59
00:03:34,310 --> 00:03:38,320
Rregull. Pra, kjo është e gjitha që na kërkon të bëjmë.

60
00:03:38,320 --> 00:03:42,770
>> Tani le të shkojë mbi disa terminologji.

61
00:03:42,770 --> 00:03:46,690
Ne tashmë folur rreth asaj se si rrënja e pemës është top-më Nyja në pemë.

62
00:03:46,690 --> 00:03:54,720
Ai përmban 7. Nyjet në fund të pemës quhen gjethet.

63
00:03:54,720 --> 00:04:01,240
Çdo nyje e cila sapo ka null si fëmijët e tij është një fletë.

64
00:04:01,240 --> 00:04:03,680
Kështu që është e mundur, nëse pemë binare ynë është vetëm një nyjë të vetme,

65
00:04:03,680 --> 00:04:10,130
se një pemë është një fletë, dhe që është ajo.

66
00:04:10,130 --> 00:04:12,060
"The 'Lartësia' e pemës është numri i HOPS ju duhet të bëni

67
00:04:12,060 --> 00:04:16,620
të marrë nga lart në një fletë. "

68
00:04:16,620 --> 00:04:18,640
Ne do të merrni në, në një të dytë, dallimin

69
00:04:18,640 --> 00:04:21,940
mes pemëve të ekuilibruar dhe të paekuilibruar binare,

70
00:04:21,940 --> 00:04:29,470
por tani për tani, lartësia e përgjithshme e kësaj peme

71
00:04:29,470 --> 00:04:34,520
Unë do të thoja është 3, edhe pse në qoftë se ju të numëruar numrin e HOPS

72
00:04:34,520 --> 00:04:39,710
ju duhet të bëni në mënyrë që të merrni në 9, atëherë kjo është me të vërtetë vetëm një lartësi prej 2.

73
00:04:39,710 --> 00:04:43,340
Tani për tani kjo është një pemë binare paekuilibruar,

74
00:04:43,340 --> 00:04:49,840
por ne do të biseduar rreth ekuilibruar, kur ajo merr të jetë relevant.

75
00:04:49,840 --> 00:04:52,040
Deri tani ne mund të flasim për nyje në një pemë në aspektin

76
00:04:52,040 --> 00:04:54,700
në lidhje me nyjet e tjera në pemë.

77
00:04:54,700 --> 00:04:59,730
Deri tani ne kemi prindërit, fëmijët, vëllezërit e motrat, paraardhësit dhe pasardhësit.

78
00:04:59,730 --> 00:05:05,650
Ata janë goxha sens të përbashkët, atë që thotë.

79
00:05:05,650 --> 00:05:09,610
Nëse pyesim - prindërit është.

80
00:05:09,610 --> 00:05:12,830
Pra, çfarë është prind i 3?

81
00:05:12,830 --> 00:05:16,090
[Studentët] 7. Po >>. Prindi është vetëm do të jetë ajo që tregon ju.

82
00:05:16,090 --> 00:05:20,510
Atëherë çfarë janë bijtë e 7?

83
00:05:20,510 --> 00:05:23,860
[Studentët] 3 dhe 9. Po >>.

84
00:05:23,860 --> 00:05:26,460
Vini re se "fëmijët" fjalë për fjalë do të thotë fëmijë,

85
00:05:26,460 --> 00:05:31,010
kështu që nuk do të zbatohet 6, sepse ajo është si një mbesë.

86
00:05:31,010 --> 00:05:35,540
Por pastaj, nëse ne do të shkojmë pasardhës, kështu që çfarë janë pasardhësit e 7?

87
00:05:35,540 --> 00:05:37,500
[Studentët] 3, 6 dhe 9. Po >>.

88
00:05:37,500 --> 00:05:42,330
Pasardhësit e nyjeve rrënjë do të jetë gjithçka në pemë,

89
00:05:42,330 --> 00:05:47,950
me përjashtim të ndoshta nyja rrënjë në vetvete, në qoftë se ju nuk doni të marrin në konsideratë se një pasardhës.

90
00:05:47,950 --> 00:05:50,750
Dhe së fundi, paraardhësit, kështu që është drejtimi i kundërt.

91
00:05:50,750 --> 00:05:55,740
Pra, çfarë janë paraardhësit e 6?

92
00:05:55,740 --> 00:05:58,920
[Studentët] 3 dhe 7. Po >>. 9 A nuk është përfshirë.

93
00:05:58,920 --> 00:06:02,520
Kjo është vetëm pjesa e prapme e drejtpërdrejtë prejardhjen në rrënjë

94
00:06:02,520 --> 00:06:13,230
do të jetë etërit tuaj.

95
00:06:13,230 --> 00:06:16,300
>> "Ne themi se një pemë binare është" urdhëruar "në qoftë se për çdo nyje në pemë,

96
00:06:16,300 --> 00:06:19,530
të gjithë pasardhësit e saj në të majtë kanë vlera më të vogël

97
00:06:19,530 --> 00:06:22,890
dhe të gjitha ato në të djathtë kanë vlera të mëdha.

98
00:06:22,890 --> 00:06:27,060
Për shembull, pema më sipër është urdhëruar, por kjo nuk është e mundur vetëm marrëveshja urdhëruar. "

99
00:06:27,060 --> 00:06:30,180
Para se të marrim për këtë,

100
00:06:30,180 --> 00:06:36,420
një pemë e urdhëroi binar është i njohur edhe si një pemë binare e kërkimit.

101
00:06:36,420 --> 00:06:38,660
Këtu ne të ndodhë të jetë duke e quajtur atë një pemë binare urdhëruar,

102
00:06:38,660 --> 00:06:41,850
por unë kurrë nuk kam dëgjuar që ai e quajti një pemë binare urdhëruar më parë,

103
00:06:41,850 --> 00:06:46,650
dhe në një quiz ne jemi shumë më shumë gjasa për të vënë drurin binar të kërkimit.

104
00:06:46,650 --> 00:06:49,250
Ata janë një dhe të njëjtë,

105
00:06:49,250 --> 00:06:54,580
dhe kjo është e rëndësishme që ju njohin dallimin në mes të pemë binare dhe kërko binar pemë.

106
00:06:54,580 --> 00:06:58,830
Një pemë binare është vetëm një pemë që tregon dy gjëra.

107
00:06:58,830 --> 00:07:02,120
Çdo nyje tregon për dy gjëra.

108
00:07:02,120 --> 00:07:06,310
Nuk ka asnjë arsyetim për vlerat që ajo pikë për të.

109
00:07:06,310 --> 00:07:11,370
Pra, si gjatë këtu, pasi ajo është një pemë binare e kërkimit,

110
00:07:11,370 --> 00:07:14,030
ne e dimë se në qoftë se ne do të shkojmë majtë të 7,

111
00:07:14,030 --> 00:07:16,670
pastaj të gjitha vlerat që ne ndoshta mund të arrijnë

112
00:07:16,670 --> 00:07:19,310
duke shkuar la i 7 duhet të jetë më pak se 7.

113
00:07:19,310 --> 00:07:24,070
Vini re se të gjitha vlerat janë më pak se 7 3 dhe 6.

114
00:07:24,070 --> 00:07:26,040
Ata janë të gjithë të majtë të 7.

115
00:07:26,040 --> 00:07:29,020
Nëse ne do të shkojmë për të drejtën e 7, çdo gjë duhet të jetë më i madh se 7,

116
00:07:29,020 --> 00:07:33,220
kështu 9 është në të djathtë të 7, kështu që ne jemi të mirë.

117
00:07:33,220 --> 00:07:36,150
Ky nuk është rasti për një pemë binare,

118
00:07:36,150 --> 00:07:40,020
për një pemë binare të rregullt mund të ketë vetëm 3 në krye, 7 të majtë,

119
00:07:40,020 --> 00:07:47,630
9 të majtë e 7, nuk ka urdhëruar të vlerave whatsoever.

120
00:07:47,630 --> 00:07:56,140
Tani, ne fakt nuk do ta bëjë këtë, sepse kjo është e lodhshme dhe të panevojshme,

121
00:07:56,140 --> 00:07:59,400
por "përpiqet të tërheqë sa më shumë pemë urdhëruar si ju mund të mendoni

122
00:07:59,400 --> 00:08:01,900
duke përdorur numrat 7, 3, 9, dhe 6.

123
00:08:01,900 --> 00:08:06,800
Sa shumë rregullime të dallueshme janë atje? Çfarë është lartësia e secilit? "

124
00:08:06,800 --> 00:08:10,480
>> Ne do të bëjmë një çift, por ideja kryesore është,

125
00:08:10,480 --> 00:08:16,530
kjo është në asnjë mënyrë një përfaqësim unik i një pemë binare që përmbajnë këto vlera.

126
00:08:16,530 --> 00:08:22,760
Gjithë ne kemi nevojë është një pemë binare që përmban 7, 3, 6, dhe 9.

127
00:08:22,760 --> 00:08:25,960
Një tjetër është e mundur të vlefshme do të jetë rrënja është 3,

128
00:08:25,960 --> 00:08:30,260
shkoni në të majtë dhe kjo është 6, shkoni në të majtë dhe kjo është 7,

129
00:08:30,260 --> 00:08:32,730
shkoni në të majtë dhe kjo është 9.

130
00:08:32,730 --> 00:08:36,169
Kjo është një mënyrë të përkryer e vlefshme kërkimit binar pemë.

131
00:08:36,169 --> 00:08:39,570
Kjo nuk është shumë e dobishme, sepse ajo është vetëm si një listë e lidhur

132
00:08:39,570 --> 00:08:43,750
dhe të gjitha këto pointers janë vetëm null.

133
00:08:43,750 --> 00:08:48,900
Por kjo është një pemë të vlefshme. Po?

134
00:08:48,900 --> 00:08:51,310
[Student] A nuk e vlerave duhet të jetë më e madhe në të djathtë?

135
00:08:51,310 --> 00:08:56,700
Apo është kjo -? Këto >> Unë do të thotë për të shkuar në mënyrë tjetër.

136
00:08:56,700 --> 00:09:00,960
Ka gjithashtu - po, le të kaloni këtë.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Kapur mirë.

138
00:09:07,770 --> 00:09:11,730
Ajo ende duhet të binden se çfarë është një pemë binare kërkimi është menduar për të bërë.

139
00:09:11,730 --> 00:09:15,650
Pra, gjithçka në të majtë duhet të jetë më pak se çdo nyje të caktuar.

140
00:09:15,650 --> 00:09:23,180
Ne vetëm mund të lëvizin, të themi, këtë 6 dhe e vënë atë këtu.

141
00:09:23,180 --> 00:09:26,880
Jo, ne nuk mundemi. Pse unë mbaj duke bërë se?

142
00:09:26,880 --> 00:09:35,350
Le të bëjmë - këtu është 6, këtu është 7, 6 pikë në 3.

143
00:09:35,350 --> 00:09:39,290
Kjo është ende e vlefshme kërkimit binar pemë.

144
00:09:39,290 --> 00:09:49,260
Çfarë është e gabuar në qoftë se unë - le të shohim nëse unë mund të dalë me një marrëveshje.

145
00:09:49,260 --> 00:09:52,280
Po, në rregull. Pra, çfarë është e gabuar me këtë pemë?

146
00:09:52,280 --> 00:10:08,920
I guess Unë kam dhënë tashmë ju një aluzion se nuk është diçka e gabuar me të.

147
00:10:08,920 --> 00:10:14,430
Pse unë mbaj duke bërë se?

148
00:10:14,430 --> 00:10:18,510
Rregull. Kjo duket e arsyeshme.

149
00:10:18,510 --> 00:10:22,590
Nëse ne shikojmë në çdo nyje, si 7, pastaj në të majtë të 7 është një 3.

150
00:10:22,590 --> 00:10:24,960
Pra, ne kemi 3, gjë për të drejtën e 3 është një 6.

151
00:10:24,960 --> 00:10:27,750
Dhe në qoftë se ju shikoni në 6, gjë për të drejtën e 6 është një 9.

152
00:10:27,750 --> 00:10:30,910
Pra, pse nuk është kjo një kërkim të vlefshme binar pemë?

153
00:10:30,910 --> 00:10:36,330
[Studentët] 9 është ende në të majtë të 7. Po >>.

154
00:10:36,330 --> 00:10:43,710
Ajo duhet të jetë e vërtetë që të gjitha vlerat që ju ndoshta mund të arrijnë duke shkuar në të majtë të 7 janë më pak se 7.

155
00:10:43,710 --> 00:10:49,120
Nëse ne do të shkojmë majtë të 7, ne kemi marrë për 3 dhe ne ende mund të merrni në 6,

156
00:10:49,120 --> 00:10:52,520
ne ende mund të merrni në 9, por duke shkuar më pak se 7,

157
00:10:52,520 --> 00:10:55,070
ne nuk duhet të jetë në gjendje për të marrë një numër që është më i madh se 7.

158
00:10:55,070 --> 00:10:59,830
Pra, kjo nuk është e vlefshme kërkimit binar pemë.

159
00:10:59,830 --> 00:11:02,330
>> Vëllai im kishte në fakt një pyetje intervistë

160
00:11:02,330 --> 00:11:07,760
që ishte në thelb kjo, vetëm kodi deri diçka për të vërtetuar

161
00:11:07,760 --> 00:11:10,500
nëse një pemë është një pemë binare e kërkimit,

162
00:11:10,500 --> 00:11:13,580
dhe kështu gjëja e parë që ai bëri ishte vetëm kontrolloni për të parë

163
00:11:13,580 --> 00:11:17,020
qoftë të majtë dhe të djathtë janë të sakta, dhe pastaj iterate atje.

164
00:11:17,020 --> 00:11:19,700
Por ju nuk mund ta bëni vetëm se, ju duhet të mbajnë gjurmët

165
00:11:19,700 --> 00:11:22,550
për faktin se tani që unë kam shkuar lënë nga 7,

166
00:11:22,550 --> 00:11:26,340
gjithçka në këtë subtree duhet të jetë më pak se 7.

167
00:11:26,340 --> 00:11:28,430
Algorithm correct ka nevojë për të mbajtur nën

168
00:11:28,430 --> 00:11:35,970
prej caqeve që vlerat ndoshta mund të bien in

169
00:11:35,970 --> 00:11:38,360
Ne nuk do të kalojnë nëpër të gjitha prej tyre.

170
00:11:38,360 --> 00:11:41,630
Ekziston një lidhje e bukur përsëritje,

171
00:11:41,630 --> 00:11:44,810
edhe pse ne nuk kemi marrë për ata, ose ne nuk do të marrë për ata,

172
00:11:44,810 --> 00:11:47,030
përcaktimin se sa ka në të vërtetë janë.

173
00:11:47,030 --> 00:11:53,180
Kështu që nuk janë 14 prej tyre.

174
00:11:53,180 --> 00:11:56,020
Ideja se si ju do të bëni atë matematikisht është si,

175
00:11:56,020 --> 00:11:59,770
ju mund të vini çdo një të vetme që të jetë nyja rrënjë,

176
00:11:59,770 --> 00:12:03,160
dhe pastaj në qoftë se unë marr 7 të jetë nyja rrënjë,

177
00:12:03,160 --> 00:12:08,150
atëherë ka, të themi, disa numra që mund të shkojnë të jetë nyje ime e majtë,

178
00:12:08,150 --> 00:12:10,440
dhe ka disa numra që mund të jetë nyje ime e djathtë,

179
00:12:10,440 --> 00:12:15,090
por në qoftë se unë kam n numra gjithsej, atëherë shuma që mund të shkojnë në të majtë

180
00:12:15,090 --> 00:12:18,820
plus shuma që mund të shkojnë në të djathtë është n - 1.

181
00:12:18,820 --> 00:12:26,130
Pra, nga numrat e mbetura, ata duhet të jenë në gjendje të shkojnë as në të majtë apo të djathtë.

182
00:12:26,130 --> 00:12:31,580
Duket e vështirë që, në qoftë se kam vënë 3 pari atëherë gjithçka ka për të shkuar në të majtë,

183
00:12:31,580 --> 00:12:35,080
por në qoftë se kam vënë 7, atëherë disa gjëra mund të shkoni majtas dhe disa gjëra mund të shkojnë në të djathtë.

184
00:12:35,080 --> 00:12:39,570
Dhe nga '3 'e parë që unë do të thotë çdo gjë mund të shkoni në të djathtë.

185
00:12:39,570 --> 00:12:42,350
Është me të vërtetë, ju vetëm duhet të mendojnë për atë si,

186
00:12:42,350 --> 00:12:47,980
sa gjërat mund të shkojnë në nivelin e ardhshëm të pemës.

187
00:12:47,980 --> 00:12:50,420
Dhe kjo vjen nga që të jetë 14 ose ju mund të tërheqë të gjithë ata,

188
00:12:50,420 --> 00:12:54,650
dhe pastaj ju do të merrni 14.

189
00:12:54,650 --> 00:13:01,120
>> Going back këtu,

190
00:13:01,120 --> 00:13:03,510
"Urdhërohet pemë binare janë të ftohtë, sepse ne mund të kërkoni nëpër to

191
00:13:03,510 --> 00:13:06,910
në një mënyrë shumë të ngjashme me kërkim për një grup të renditura.

192
00:13:06,910 --> 00:13:10,120
Për ta bërë këtë, ne të fillojë në rrënjë dhe të punojnë rrugën tonë poshtë pemës

193
00:13:10,120 --> 00:13:13,440
drejt gjetheve, duke kontrolluar çdo nyje vlerat e kundër vlerave ne jemi në kërkim për të.

194
00:13:13,440 --> 00:13:15,810
Nëse vlera nyjen aktual është më pak se vlera ne jemi duke kërkuar për të,

195
00:13:15,810 --> 00:13:18,050
ju shkoni pranë fëmijës së djathtë nyjen së.

196
00:13:18,050 --> 00:13:20,030
Përndryshe, ju shkoni me fëmijën e majtë nyjen së.

197
00:13:20,030 --> 00:13:22,800
Në disa pika, ju do të gjeni vlerën ose ju jeni duke kërkuar për të, ose ju do të kandidojë në një null,

198
00:13:22,800 --> 00:13:28,520
treguar vlerën nuk është në pemë. "

199
00:13:28,520 --> 00:13:32,450
Unë kam për rishikimin pemë që kishim para, që do të marrë një të dytë.

200
00:13:32,450 --> 00:13:38,280
Por ne duam të shohim nëse deri 6, 10, dhe 1 janë në pemë.

201
00:13:38,280 --> 00:13:49,180
Pra, çfarë ishte, 7, 9, 3, 6. Rregull.

202
00:13:49,180 --> 00:13:52,730
Numrat që ju doni të kërkoni, ne duam të shohim deri 6.

203
00:13:52,730 --> 00:13:55,440
Si e bën këtë punë algorithm?

204
00:13:55,440 --> 00:14:03,040
E pra, ne gjithashtu kemi disa tregues rrënjë në pemë tonë.

205
00:14:03,040 --> 00:14:12,460
Dhe ne do të shkojë në rrënjë dhe të thonë, është kjo vlerë e barabartë me vlerën e ne jemi në kërkim për?

206
00:14:12,460 --> 00:14:15,000
Pra, ne jemi duke kërkuar për 6, kështu që nuk është e barabartë.

207
00:14:15,000 --> 00:14:20,140
Pra, ne do të mbajë, dhe tani të themi, në rregull, kështu që është më pak se 6 7.

208
00:14:20,140 --> 00:14:23,940
A do të thotë që ne duam të shkojnë në të majtë, ose nuk duam për të shkuar në të djathtë?

209
00:14:23,940 --> 00:14:27,340
[Student] Left. Po >>.

210
00:14:27,340 --> 00:14:33,340
Kjo është në mënyrë të konsiderueshme më e lehtë, të gjithë ju duhet të bëni është të nxjerrë një nyje e mundshme të pemës

211
00:14:33,340 --> 00:14:37,760
dhe pastaj ju don 't - në vend që të përpiqen për të menduar në kokën tuaj,

212
00:14:37,760 --> 00:14:40,020
rregull, në qoftë se është pak, nuk kam vajtur majtas ose shkoni të drejtë,

213
00:14:40,020 --> 00:14:43,030
vetëm duke kërkuar në këtë foto, ajo është shumë e qartë që unë kam për të shkuar në të majtë

214
00:14:43,030 --> 00:14:47,700
nëse kjo nyje është më e madhe se vlera që unë jam duke kërkuar për të.

215
00:14:47,700 --> 00:14:52,600
Pra, ju shkoni në të majtë, tani unë jam në 3.

216
00:14:52,600 --> 00:14:57,770
Unë dua të - 3 është më pak se vlera që unë jam duke kërkuar për të, e cila është 6.

217
00:14:57,770 --> 00:15:03,420
Pra, ne do të shkojmë në të djathtë, dhe tani unë përfundojë deri në 6,

218
00:15:03,420 --> 00:15:07,380
cila është vlera që unë jam duke kërkuar për të, kështu që unë të kthehen vërtetë.

219
00:15:07,380 --> 00:15:15,760
Vlera tjetër unë jam duke shkuar për të kërkuar është 10.

220
00:15:15,760 --> 00:15:23,230
Rregull. Pra 10, tani, do të - të prerë që - do të ndjekë rrënjë.

221
00:15:23,230 --> 00:15:27,670
Tani, 10 do të jetë më i madh se 7, kështu që unë dua të shikojnë në të djathtë.

222
00:15:27,670 --> 00:15:31,660
Unë jam duke shkuar për të ardhur këtu, 10 do të jetë më i madh se 9,

223
00:15:31,660 --> 00:15:34,520
kështu që unë jam duke shkuar për të dëshironi të shikoni në të djathtë.

224
00:15:34,520 --> 00:15:42,100
Kam ardhur gjatë këtu, por mbi këtu tani unë jam në null.

225
00:15:42,100 --> 00:15:44,170
Çfarë të bëj në qoftë se unë goditi null?

226
00:15:44,170 --> 00:15:47,440
[Student] Kthehu rreme? Po >>. Unë nuk e kam gjetur 10.

227
00:15:47,440 --> 00:15:49,800
1 do të jetë një rast pothuajse identike,

228
00:15:49,800 --> 00:15:51,950
përveç se është vetëm do të jetë kthyer, në vend që të kërkoni

229
00:15:51,950 --> 00:15:56,540
poshtë në anën e djathtë, unë jam duke shkuar për të kërkuar poshtë në anën e majtë.

230
00:15:56,540 --> 00:16:00,430
>> Tani unë mendoj se ne në të vërtetë të merrni për kodin.

231
00:16:00,430 --> 00:16:04,070
Ja ku - hapur pajisjen CS50 dhe të lundruar në rrugën tuaj atje,

232
00:16:04,070 --> 00:16:07,010
por ju mund vetëm të bëjë atë në hapësirë.

233
00:16:07,010 --> 00:16:09,170
Kjo është ndoshta ideal për të bërë atë në hapësirë,

234
00:16:09,170 --> 00:16:13,760
sepse ne mund të punojnë në hapësirë.

235
00:16:13,760 --> 00:16:19,170
"Së pari ne do të duhet një përkufizim të ri për një lloj nyje pemë binare që përmbajnë vlera Int.

236
00:16:19,170 --> 00:16:21,400
Përdorimi i Boilerplate typedef më poshtë,

237
00:16:21,400 --> 00:16:24,510
të krijojë një përkufizim të ri për një lloj nyje në një pemë binare.

238
00:16:24,510 --> 00:16:27,930
Në qoftë se ju merrni mbërthyer. . . "Blah, blah, blah. Mirë.

239
00:16:27,930 --> 00:16:30,380
Pra, le të vënë Boilerplate këtu,

240
00:16:30,380 --> 00:16:41,630
nyje typedef struct, dhe nyja. Po, në rregull.

241
00:16:41,630 --> 00:16:44,270
Pra, cilat janë fushat që ne jemi duke shkuar për të duan në nyje tonë?

242
00:16:44,270 --> 00:16:46,520
[Student] Int dhe pastaj dy pointers?

243
00:16:46,520 --> 00:16:49,700
Int >> vlerë, dy pointers? Si mund të shkruaj pointers?

244
00:16:49,700 --> 00:16:58,440
[Student] struct. Unë duhet të zoom >> in Yeah, kështu që struct nyje * la,

245
00:16:58,440 --> 00:17:01,320
dhe struct * nyja e drejtë.

246
00:17:01,320 --> 00:17:03,460
Dhe mbani mend diskutimin nga koha e kaluar,

247
00:17:03,460 --> 00:17:15,290
se kjo nuk ka kuptim, kjo nuk ka kuptim,

248
00:17:15,290 --> 00:17:18,270
kjo nuk ka kuptim.

249
00:17:18,270 --> 00:17:25,000
Ju duhet çdo gjë atje në mënyrë që të përcaktojë këtë struct rekursive.

250
00:17:25,000 --> 00:17:27,970
Mirë, kështu që kjo është ajo që pema jonë do të duken si.

251
00:17:27,970 --> 00:17:37,670
Nëse ne e bëmë një pemë trinary, atëherë një nyje mund të duket si, B2 B1, struct * nyja B3,

252
00:17:37,670 --> 00:17:43,470
ku b është një degë - në fakt, unë kam dëgjuar shumë majtas, mesme, të drejtë, çfarëdo, por.

253
00:17:43,470 --> 00:17:55,610
Ne vetëm kujdesen për binar, në mënyrë të drejtë, të majtë.

254
00:17:55,610 --> 00:17:59,110
"Tani deklarojë një ndryshore globale * nyje për rrënjët e pemës."

255
00:17:59,110 --> 00:18:01,510
Pra, ne nuk jemi duke shkuar për të bërë këtë.

256
00:18:01,510 --> 00:18:08,950
Në mënyrë për t'i bërë gjërat pak më e vështirë dhe më të përgjithësuar,

257
00:18:08,950 --> 00:18:11,570
ne nuk do të kemi një ndryshore globale nyje.

258
00:18:11,570 --> 00:18:16,710
Në vend të kësaj, në kryesore ne do të deklarojë të gjitha gjërat tona nyjen,

259
00:18:16,710 --> 00:18:20,500
dhe kjo do të thotë se më poshtë, kur ne të fillojnë running

260
00:18:20,500 --> 00:18:23,130
Funksioni përmban tonë dhe funksioni ynë insert,

261
00:18:23,130 --> 00:18:27,410
vend i përmban tona funksionojnë vetëm duke përdorur këtë ndryshore globale nyje,

262
00:18:27,410 --> 00:18:34,280
ne do të duhet të marrë si argument pemë që ne duam që ajo të procesit.

263
00:18:34,280 --> 00:18:36,650
Duke ndryshore globale ishte menduar për të bërë gjërat më të lehtë.

264
00:18:36,650 --> 00:18:42,310
Ne jemi duke shkuar për të bërë gjëra të vështirë.

265
00:18:42,310 --> 00:18:51,210
Tani të marrë një minutë apo më shumë vetëm për të bërë këtë gjë e tillë,

266
00:18:51,210 --> 00:18:57,690
ku brenda kryesore që ju doni të krijuar këtë pemë, dhe kjo është e gjitha që ju doni të bëni.

267
00:18:57,690 --> 00:19:04,530
Provo dhe të ndërtuar këtë pemë në funksion tuaj kryesor.

268
00:19:42,760 --> 00:19:47,610
>> Rregull. Pra, ju nuk keni për të kanë ndërtuar rrugën e pemës gjithë ende.

269
00:19:47,610 --> 00:19:49,840
Por dikush ka diçka që unë mund të tërheqë deri

270
00:19:49,840 --> 00:20:03,130
për të treguar se si dikush mund të fillojë ndërtimin e një pemë të tillë?

271
00:20:03,130 --> 00:20:08,080
[Student] banging dikujt, duke u përpjekur për të marrë jashtë.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Çdokush rehat me ndërtimin e tyre pemë?

273
00:20:13,100 --> 00:20:15,520
[Student] Sure. Kjo nuk është bërë. Kjo >> është në rregull. Ne vetëm mund të përfundojë -

274
00:20:15,520 --> 00:20:26,860
oh, ju mund ta ruani atë? Hooray.

275
00:20:26,860 --> 00:20:32,020
Pra, këtu kemi - oh, unë jam pak të prerë.

276
00:20:32,020 --> 00:20:34,770
Jam unë zoomed në?

277
00:20:34,770 --> 00:20:37,730
Zoom në, shkoni jashtë. >> Unë kam një pyetje. Po >>?

278
00:20:37,730 --> 00:20:44,410
[Student] Kur ju të përcaktojë strukturën, janë gjëra të tilla si initialized për asgjë?

279
00:20:44,410 --> 00:20:47,160
[Bowden] nr >> Okay. Pra, ju do të duhet të nisja -

280
00:20:47,160 --> 00:20:50,450
[Bowden] nr Kur ju të përcaktuar, ose kur ju të deklarojë një struct,

281
00:20:50,450 --> 00:20:55,600
ajo nuk është initialized nga default, ajo është vetëm si në qoftë se ju të deklarojë një int.

282
00:20:55,600 --> 00:20:59,020
Kjo është saktësisht e njëjta gjë. Është si çdo fushat e saj individuale

283
00:20:59,020 --> 00:21:04,460
mund të ketë një vlerë plehrash në të. Dhe >> është e mundur për të përcaktuar - ose të shpallë një struct

284
00:21:04,460 --> 00:21:07,740
në një mënyrë që ajo bën nisja e tyre?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Po. Pra, initialization shkurtore sintaksa

286
00:21:13,200 --> 00:21:18,660
do të duken si -

287
00:21:18,660 --> 00:21:22,200
Ka dy mënyra që ne mund të bëjmë këtë. Unë mendoj se ne duhet të hartojnë atë

288
00:21:22,200 --> 00:21:25,840
të bëjë tingëllimë siguruar gjithashtu e bën këtë.

289
00:21:25,840 --> 00:21:28,510
Urdhri i argumenteve që vjen në struct,

290
00:21:28,510 --> 00:21:32,170
ju vënë si qëllim të argumenteve brenda këtyre formatimin e teksteve kaçurrel.

291
00:21:32,170 --> 00:21:35,690
Pra, nëse ju doni të nisja atë të 9 dhe e la të pavlefshme dhe pastaj të drejtë të jetë i pavlefshëm,

292
00:21:35,690 --> 00:21:41,570
ajo do të jetë 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternativë është, dhe redaktor nuk ka si këtë sintaksë,

294
00:21:47,890 --> 00:21:50,300
dhe ajo mendon se unë dua një bllok të ri,

295
00:21:50,300 --> 00:22:01,800
por tjetër është diçka si -

296
00:22:01,800 --> 00:22:04,190
këtu, unë do të vënë atë në një linjë të re.

297
00:22:04,190 --> 00:22:09,140
Ju mund të thoni në mënyrë eksplicite, unë harroj sintaksë të saktë.

298
00:22:09,140 --> 00:22:13,110
Kështu që ju mund të në mënyrë eksplicite adresuar ato me emër, dhe thonë,

299
00:22:13,110 --> 00:22:21,570
. C, ose. Vlera = 9,. Majtas NULL =.

300
00:22:21,570 --> 00:22:24,540
Unë jam guessing këto duhet të presje.

301
00:22:24,540 --> 00:22:29,110
. Drejtë = NULL, kështu që në këtë mënyrë ju nuk e bëni

302
00:22:29,110 --> 00:22:33,780
në të vërtetë duhet të dini rendin e struct,

303
00:22:33,780 --> 00:22:36,650
dhe kur ju jeni duke e lexuar këtë, kjo është shumë më e qartë

304
00:22:36,650 --> 00:22:41,920
se çfarë vlera duke u nisur për të.

305
00:22:41,920 --> 00:22:44,080
>> Kjo ndodh të jetë një nga gjërat që -

306
00:22:44,080 --> 00:22:49,100
kështu, për pjesën më të madhe, C + + është një superset e C.

307
00:22:49,100 --> 00:22:54,160
Ju mund të merrni kodin C, lëvizin atë mbi të C + +, dhe ajo duhet të hartojnë.

308
00:22:54,160 --> 00:22:59,570
Kjo është një nga gjërat që C + + nuk e mbështesin, kështu që njerëzit nuk kanë tendencë për të bërë atë.

309
00:22:59,570 --> 00:23:01,850
Unë nuk e di nëse kjo është e vetmja arsye pse njerëzit nuk priren për të bërë atë,

310
00:23:01,850 --> 00:23:10,540
por rasti kur unë e nevojshme për të përdorur atë nevojshme për të punuar me C + + dhe kështu që unë nuk mund të përdorë këtë.

311
00:23:10,540 --> 00:23:14,000
Një tjetër shembull i diçkaje që nuk punojnë me C + + është

312
00:23:14,000 --> 00:23:16,940
si malloc kthen "* void," teknikisht,

313
00:23:16,940 --> 00:23:20,200
por ju mund vetëm të them char * = x çfarëdo malloc,

314
00:23:20,200 --> 00:23:22,840
dhe kjo automatikisht do të hidhet në një char *.

315
00:23:22,840 --> 00:23:25,450
Kjo cast automatike nuk ndodh në C + +.

316
00:23:25,450 --> 00:23:28,150
Kjo nuk do të përpilojnë, dhe ju do të duhet të them në mënyrë eksplicite

317
00:23:28,150 --> 00:23:34,510
* char, malloc, çfarëdo, për të hedhur atë në një char *.

318
00:23:34,510 --> 00:23:37,270
Nuk ka shumë gjëra që C dhe C + + nuk bien dakord mbi,

319
00:23:37,270 --> 00:23:40,620
por ato janë dy.

320
00:23:40,620 --> 00:23:43,120
Pra, ne do të shkojmë me këtë sintaksë.

321
00:23:43,120 --> 00:23:46,150
Por edhe në qoftë se ne nuk shkoni me atë sintaksës,

322
00:23:46,150 --> 00:23:49,470
çfarë është - mund të jetë i gabuar me këtë?

323
00:23:49,470 --> 00:23:52,170
[Student] Unë nuk duhet të dereference atë? Po >>.

324
00:23:52,170 --> 00:23:55,110
Mos harroni se ka një shigjetë dereference nënkuptuar,

325
00:23:55,110 --> 00:23:58,230
dhe kështu kur ne jemi vetëm që kanë të bëjnë me një struct,

326
00:23:58,230 --> 00:24:04,300
ne duam t'u përdorur. për të marrë në një fushë brenda të struct.

327
00:24:04,300 --> 00:24:07,200
Dhe e vetmja kohë që ne përdorim shigjetë është kur ne duam të bëjmë -

328
00:24:07,200 --> 00:24:13,450
mirë, është e barabartë me shigjetë -

329
00:24:13,450 --> 00:24:17,020
kjo është ajo që do të thotë në qoftë se kam përdorur arrow.

330
00:24:17,020 --> 00:24:24,600
Të gjitha mjetet shigjetë është, dereference këtë, tani unë jam në një struct, dhe unë mund të merrni këtë fushë.

331
00:24:24,600 --> 00:24:28,040
Ose të merrni në fushën e drejtpërdrejtë ose dereference dhe për të marrë fushë -

332
00:24:28,040 --> 00:24:30,380
Unë mendoj se kjo duhet të jetë vlerë.

333
00:24:30,380 --> 00:24:33,910
Por këtu unë jam që kanë të bëjnë me vetëm një struct jo, një tregues për një struct,

334
00:24:33,910 --> 00:24:38,780
dhe kështu që unë nuk mund të përdorin arrow.

335
00:24:38,780 --> 00:24:47,510
Por ky lloj i gjë që mund të bëjmë për të gjitha nyjet.

336
00:24:47,510 --> 00:24:55,790
Oh Perëndia im.

337
00:24:55,790 --> 00:25:09,540
Kjo është 6, 7, dhe 3.

338
00:25:09,540 --> 00:25:16,470
Atëherë ne mund të ngritur degë në pemë tonë, ne mund të kemi 7 -

339
00:25:16,470 --> 00:25:21,650
ne mund të kemi, majtas e tij duhet të theksojnë 3.

340
00:25:21,650 --> 00:25:25,130
Pra, si mund ta bëjmë këtë?

341
00:25:25,130 --> 00:25:29,320
[Studentët, pakuptueshëm] >> yeah. Adresa e node3,

342
00:25:29,320 --> 00:25:34,170
dhe në qoftë se ju nuk keni adresë, atëherë ai thjesht nuk do të përpilojnë.

343
00:25:34,170 --> 00:25:38,190
Por mos harroni se këto janë pointers në nyjet e ardhshme.

344
00:25:38,190 --> 00:25:44,930
E drejta duhet pikë në 9,

345
00:25:44,930 --> 00:25:53,330
dhe 3 duhet pikë për të drejtën e 6.

346
00:25:53,330 --> 00:25:58,480
Unë mendoj se kjo është e gjitha vendosur. Çdo komente ose pyetje?

347
00:25:58,480 --> 00:26:02,060
[Student, pakuptueshëm] Rrënja do të jetë 7.

348
00:26:02,060 --> 00:26:08,210
Ne mund të them vetëm nyjen * ptr =

349
00:26:08,210 --> 00:26:14,160
ose, rrënjë = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Për qëllimet tona, ne jemi duke shkuar për të merret me insert,

351
00:26:20,730 --> 00:26:25,490
kështu që ne jemi duke shkuar për të duan të shkruajnë një funksion për të futur në këtë pemë binare

352
00:26:25,490 --> 00:26:34,230
dhe është futur në mënyrë të pashmangshme do të thërrasë malloc për të krijuar një nyje të re për këtë pemë.

353
00:26:34,230 --> 00:26:36,590
Pra, gjërat janë duke shkuar për të marrë çrregullt me ​​faktin se disa nyje

354
00:26:36,590 --> 00:26:38,590
janë aktualisht në rafte

355
00:26:38,590 --> 00:26:43,680
dhe nyjet e tjera do të përfundojnë deri në tog kur ne futur ato.

356
00:26:43,680 --> 00:26:47,640
Kjo është krejtësisht e vlefshme, por arsyeja e vetme

357
00:26:47,640 --> 00:26:49,600
ne jemi në gjendje për ta bërë këtë në rafte

358
00:26:49,600 --> 00:26:51,840
është për shkak se ajo është e tillë një shembull i ndërtuar që ne e dimë

359
00:26:51,840 --> 00:26:56,360
pema është menduar për të ndërtuar si 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Nëse ne nuk e kemi këtë, atëherë ne nuk do të duhet të malloc në vendin e parë.

361
00:27:02,970 --> 00:27:06,160
Siç do të shohim pak më vonë, ne duhet të malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Tani për tani kjo është krejtësisht e arsyeshme për të vënë në rafte,

363
00:27:08,570 --> 00:27:14,750
por le të ndryshojë këtë në një zbatim malloc.

364
00:27:14,750 --> 00:27:17,160
Pra, secili prej tyre është tani do të jetë diçka si

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

366
00:27:24,240 --> 00:27:28,040
Dhe tani ne do të duhet të bëjë kontroll tonë.

367
00:27:28,040 --> 00:27:34,010
në qoftë se (== NULL node9) - Unë nuk dua se -

368
00:27:34,010 --> 00:27:40,950
1 kthehen, dhe pastaj ne mund të bëjmë node9-> sepse tani kjo është një akrep,

369
00:27:40,950 --> 00:27:45,300
vlera = 6, node9-> la = NULL,

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

371
00:27:48,930 --> 00:27:51,410
dhe ne do të duhet të bëjë se për secilin nga këto nyje.

372
00:27:51,410 --> 00:27:57,490
Pra, në vend, le të vënë atë në brendësi të një funksion të veçantë.

373
00:27:57,490 --> 00:28:00,620
Le të thërrasë atë nyje * build_node,

374
00:28:00,620 --> 00:28:09,050
dhe kjo është disi e ngjashme me TV ne ofrojmë për Huffman coding.

375
00:28:09,050 --> 00:28:12,730
Ne ju japim funksionet initializer për një pemë

376
00:28:12,730 --> 00:28:20,520
dhe deconstructor "funksione" për ato pemë dhe të njëjtat për pyjet.

377
00:28:20,520 --> 00:28:22,570
>> Pra, këtu ne do të ketë një funksion initializer

378
00:28:22,570 --> 00:28:25,170
të vetëm të ndërtuar një nyje për ne.

379
00:28:25,170 --> 00:28:29,320
Dhe kjo do të duket shumë e shumë tamam si kjo.

380
00:28:29,320 --> 00:28:32,230
Dhe unë jam edhe do të jetë dembel dhe jo të ndryshojë emrin e ndryshueshme,

381
00:28:32,230 --> 00:28:34,380
edhe pse node9 nuk ka kuptim më.

382
00:28:34,380 --> 00:28:38,610
Oh, unë mendoj se vlera node9 duhet të nuk kanë qenë 6.

383
00:28:38,610 --> 00:28:42,800
Tani ne mund të kthehen node9.

384
00:28:42,800 --> 00:28:49,550
Dhe këtu ne duhet të kthehen null.

385
00:28:49,550 --> 00:28:52,690
Gjithkush bien dakord mbi atë funksion ndërtuar-a-nyjeve?

386
00:28:52,690 --> 00:28:59,780
Deri tani ne vetëm mund të telefononi që të ndërtojë çdo nyje me një vlerë të caktuar dhe pointers null.

387
00:28:59,780 --> 00:29:09,750
Tani ne mund të quajmë këtë, ne mund të bëjmë nyje * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Dhe le ta bëjmë. . .

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

390
00:29:33,980 --> 00:29:39,330
Dhe tani ne duam të ngritur pointers të njëjta,

391
00:29:39,330 --> 00:29:42,470
përveç tani gjithçka është tashmë në drejtim të pointers

392
00:29:42,470 --> 00:29:48,480
kështu që nuk ka më nevojë për adresën e.

393
00:29:48,480 --> 00:29:56,300
Rregull. Pra, çfarë është gjëja e fundit që unë dua të bëj?

394
00:29:56,300 --> 00:30:03,850
Ka një gabim-checking se unë nuk jam duke bërë.

395
00:30:03,850 --> 00:30:06,800
Çfarë ka të ndërtuar kthimin nyje?

396
00:30:06,800 --> 00:30:11,660
[Student, pakuptueshëm] >> Yeah. Nëse malloc dështuar, ajo do të kthehet null.

397
00:30:11,660 --> 00:30:16,460
Kështu që unë jam duke shkuar për ta vënë atë poshtë lazily këtu në vend për të bërë një kusht për secilin.

398
00:30:16,460 --> 00:30:22,320
Në qoftë se (== NULL node9, ose - edhe më të thjeshta,

399
00:30:22,320 --> 00:30:28,020
kjo është e barabartë me vetëm nëse nuk node9.

400
00:30:28,020 --> 00:30:38,310
Pra, nëse nuk node9, apo jo node6, apo jo node3, apo jo node7, kthehen 1.

401
00:30:38,310 --> 00:30:42,850
Ndoshta ne duhet të shtypura malloc dështuar, apo diçka.

402
00:30:42,850 --> 00:30:46,680
[Student] A është i barabartë me të rreme null si?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Çdo vlerë zero është e rreme.

404
00:30:51,290 --> 00:30:53,920
Pra, null është një vlerë zero.

405
00:30:53,920 --> 00:30:56,780
Zero është një vlerë zero. False është një vlerë zero.

406
00:30:56,780 --> 00:31:02,130
Çdo - pretty much të vetmet 2 Vlerat janë zero dhe zero null,

407
00:31:02,130 --> 00:31:07,900
rreme hash është vetëm definohet si zero.

408
00:31:07,900 --> 00:31:13,030
Kjo vlen edhe në qoftë se ne nuk deklarojnë ndryshore globale.

409
00:31:13,030 --> 00:31:17,890
Nëse ne nuk kemi rrënjë * nyje deri këtu,

410
00:31:17,890 --> 00:31:24,150
pastaj - Gjë e bukur për variabla globale është se ata gjithmonë kanë një vlerë fillestare.

411
00:31:24,150 --> 00:31:27,500
Kjo nuk është e vërtetë e funksioneve, si brenda këtu,

412
00:31:27,500 --> 00:31:34,870
nëse kemi, si, * nyja ose x nyjë.

413
00:31:34,870 --> 00:31:37,380
Ne nuk kemi asnjë ide se çfarë x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
ose ne mund të shtypura dhe ato mund të jetë arbitrare.

415
00:31:40,700 --> 00:31:44,980
Kjo nuk është e vërtetë e variablave globale.

416
00:31:44,980 --> 00:31:47,450
Pra, rrënja nyje apo x nyjë.

417
00:31:47,450 --> 00:31:53,410
By default, çdo gjë që është globale, nëse nuk initialized në mënyrë eksplicite për disa vlera,

418
00:31:53,410 --> 00:31:57,390
ka një vlerë zero si vlerën e tij.

419
00:31:57,390 --> 00:32:01,150
Kështu që këtu, rrënjë nyje *, ne nuk eksplicite nisja atë për asgjë,

420
00:32:01,150 --> 00:32:06,350
kështu që vlera e saj do të jetë i paracaktuar null, që është vlera zero e pointers.

421
00:32:06,350 --> 00:32:11,870
Vlera e paracaktuar e x do të thotë se x.value është zero,

422
00:32:11,870 --> 00:32:14,260
x.left është i pavlefshëm, dhe x.right është i pavlefshëm.

423
00:32:14,260 --> 00:32:21,070
Kështu që kjo është një struct, të gjitha fushat e struct do të jetë zero vlera.

424
00:32:21,070 --> 00:32:24,410
Ne nuk duhet të përdorin atë këtu, pse.

425
00:32:24,410 --> 00:32:27,320
[Student] Të structs janë të ndryshme se sa variablave të tjerë, dhe variablave të tjera janë

426
00:32:27,320 --> 00:32:31,400
Vlerat e plehrave, këto janë zero?

427
00:32:31,400 --> 00:32:36,220
[Bowden] vlerat tjera. Pra, në x, x do të jetë zero.

428
00:32:36,220 --> 00:32:40,070
Nëse kjo është në qëllimin global, ajo ka një vlerë fillestare. Mirë >>.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Ose vlera fillestare që ju dha atë ose zero.

430
00:32:48,950 --> 00:32:53,260
Unë mendoj se kujdeset për të gjithë këtë.

431
00:32:53,260 --> 00:32:58,390
>> Rregull. Kështu pjesa tjetër e pyetjes pyet,

432
00:32:58,390 --> 00:33:01,260
"Tani ne duam të shkruani një funksion të quajtur përmban

433
00:33:01,260 --> 00:33:04,930
me një prototip të bool përmban vlerën int. "

434
00:33:04,930 --> 00:33:08,340
Ne nuk do të bëjë bool përmban vlerën int.

435
00:33:08,340 --> 00:33:15,110
Prototip ynë do të duken si

436
00:33:15,110 --> 00:33:22,380
bool përmban (vlera int.

437
00:33:22,380 --> 00:33:24,490
Dhe pastaj ne jemi gjithashtu do të kalojë atë pemë

438
00:33:24,490 --> 00:33:28,870
se duhet të kontrolluar për të parë nëse ajo ka atë vlerë.

439
00:33:28,870 --> 00:33:38,290
Pra nyje * pemë). Rregull.

440
00:33:38,290 --> 00:33:44,440
Dhe atëherë ne mund ta quajmë atë me diçka si,

441
00:33:44,440 --> 00:33:46,090
ndoshta ne do të duan të printf apo diçka.

442
00:33:46,090 --> 00:33:51,040
Përmban 6, rrënjë tonë.

443
00:33:51,040 --> 00:33:54,300
Kjo duhet të kthehet, ose një e vërtetë,

444
00:33:54,300 --> 00:33:59,390
ndërsa përmban 5 rrënja duhet të kthehen rreme.

445
00:33:59,390 --> 00:34:02,690
Pra, të marrë një të dytë për të zbatuar këtë.

446
00:34:02,690 --> 00:34:06,780
Ju mund ta bëni atë ose iteratively ose Recursively.

447
00:34:06,780 --> 00:34:09,739
Gjë e bukur për mënyrën se si ne kemi vendosur gjërat është se

448
00:34:09,739 --> 00:34:12,300
ajo jep veten për zgjidhjen tonë shumë më të lehtë rekursive

449
00:34:12,300 --> 00:34:14,719
se globale ndryshueshme rruga e bëri.

450
00:34:14,719 --> 00:34:19,750
Sepse në qoftë se ne vetëm kemi përmban vlera int, atëherë ne kemi asnjë mënyrë për të recursing poshtë tregoje.

451
00:34:19,750 --> 00:34:24,130
Ne do të duhet të ketë një funksion të veçantë ndihmëtar që recurses poshtë tregoje për ne.

452
00:34:24,130 --> 00:34:29,610
Por, pasi që ne kemi ndryshuar atë për të marrë pemë si argument,

453
00:34:29,610 --> 00:34:32,760
të cilat ajo duhet të ketë qenë gjithmonë në vendin e parë,

454
00:34:32,760 --> 00:34:35,710
tani ne mund të recurse më lehtë.

455
00:34:35,710 --> 00:34:38,960
Pra, përsëritës apo gjithkund rekursive, ne do të shkojnë mbi të dyja,

456
00:34:38,960 --> 00:34:46,139
por ne do të shohim që përfundon gjithkund rekursive duke qenë mjaft e lehtë.

457
00:34:59,140 --> 00:35:02,480
Rregull. Ka njeri të ketë diçka që ne mund të punojnë me të?

458
00:35:02,480 --> 00:35:12,000
>> [Student] Unë kam marrë një përsëritës zgjidhje. >> All right, përsëritës.

459
00:35:12,000 --> 00:35:16,030
Mirë, kjo duket e mirë.

460
00:35:16,030 --> 00:35:18,920
Pra, duan të ecin nëpër atë na?

461
00:35:18,920 --> 00:35:25,780
[Student] Sure. Kështu që unë vendosur një ndryshore temp të marrë nyja e parë e pemës.

462
00:35:25,780 --> 00:35:28,330
Dhe pastaj unë vetëm looped nëpërmjet temp, ndërsa nuk ka null barabartë,

463
00:35:28,330 --> 00:35:31,700
kështu ndërsa ishte ende në pemë, I guess.

464
00:35:31,700 --> 00:35:35,710
Dhe në qoftë se vlera është e barabartë me vlerën që temp është treguar,

465
00:35:35,710 --> 00:35:37,640
atëherë ajo kthehet atë vlerë.

466
00:35:37,640 --> 00:35:40,210
Përndryshe, ai kontrollon nëse është në anën e djathtë apo të majtë.

467
00:35:40,210 --> 00:35:43,400
Nëse ndonjëherë ju merrni një situatë ku nuk ka pemë më shumë,

468
00:35:43,400 --> 00:35:47,330
atëherë ajo kthehet - ajo daljet lak dhe kthen rreme.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. Kështu që duket e mirë.

470
00:35:52,190 --> 00:35:58,470
Çdokush keni ndonjë koment për asgjë?

471
00:35:58,470 --> 00:36:02,400
Unë nuk kam asnjë komentet e saktësisë në të gjitha.

472
00:36:02,400 --> 00:36:11,020
Një gjë që mund të bëjmë është ky djalë.

473
00:36:11,020 --> 00:36:21,660
Oh, ajo do të shkojë një longish pak.

474
00:36:21,660 --> 00:36:33,460
Unë do të rregullojmë se deri. Rregull.

475
00:36:33,460 --> 00:36:37,150
>> Gjithkush duhet të mbani mend se si punon tresh.

476
00:36:37,150 --> 00:36:38,610
Ka qenë definitivisht kuize në të kaluarën

477
00:36:38,610 --> 00:36:41,170
që të ju jap një funksion me një operator tresh,

478
00:36:41,170 --> 00:36:45,750
dhe thonë, kjo përkthehet, të bëjë diçka që nuk e përdor tresh.

479
00:36:45,750 --> 00:36:49,140
Pra, ky është një rast shumë të zakonshme të kur unë do të mendoj për të përdorur tresh,

480
00:36:49,140 --> 00:36:54,610
ku nëse disa kusht të vendosur një ndryshore për diçka,

481
00:36:54,610 --> 00:36:58,580
përcaktuar tjetër që ndryshore të njëjtë për diçka tjetër.

482
00:36:58,580 --> 00:37:03,390
Kjo është diçka që shumë shpesh mund të shndërrohet në këtë lloj gjë

483
00:37:03,390 --> 00:37:14,420
ku të vendosur se ndryshore për këtë - ose, edhe, është kjo e vërtetë? Atëherë kjo, tjetër këtë.

484
00:37:14,420 --> 00:37:18,550
[Student] E para është nëse vërtetë, apo jo?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. Mënyrën se si unë gjithmonë lexuar atë është, temp e barabartë me vlerë më të madhe se vlera e temp,

486
00:37:25,570 --> 00:37:30,680
atëherë kjo, tjetër këtë. Është pyetur një pyetje.

487
00:37:30,680 --> 00:37:35,200
Është ajo e madhe? Pastaj të bëjë gjënë e parë. Tjetër të bërë gjënë e dytë.

488
00:37:35,200 --> 00:37:41,670
Unë pothuajse gjithmonë - dy pika, unë vetëm - në kokën time, kam lexuar si tjetër.

489
00:37:41,670 --> 00:37:47,180
>> A ka dikush të ketë një zgjidhje rekursive?

490
00:37:47,180 --> 00:37:49,670
Rregull. Ky i fundit ne jemi duke shkuar për të - ajo tashmë mund të jetë i madh,

491
00:37:49,670 --> 00:37:53,990
por ne jemi duke shkuar për ta bërë atë edhe më të mirë.

492
00:37:53,990 --> 00:37:58,720
Kjo është shumë e shumë të njëjtën ide e saktë.

493
00:37:58,720 --> 00:38:03,060
Është vetëm, mirë, nuk ju duan të shpjegojë?

494
00:38:03,060 --> 00:38:08,340
[Student] Sure. Pra, ne jemi duke e bërë të sigurtë që pema nuk është i pavlefshëm parë,

495
00:38:08,340 --> 00:38:13,380
sepse nëse pema është i pavlefshëm, atëherë ajo do të kthehet të rreme, sepse ne nuk kemi gjetur atë.

496
00:38:13,380 --> 00:38:19,200
Dhe në qoftë se nuk ka ende një pemë, ne do të shkojmë në - së pari kontrolloni nëse vlera është nyja aktuale.

497
00:38:19,200 --> 00:38:23,740
Kthehu në qoftë se është e vërtetë, dhe në qoftë se ne nuk recurse në të majtë apo të djathtë.

498
00:38:23,740 --> 00:38:25,970
Bën që të shëndosha të përshtatshme? >> Mm-hmm. (Marrëveshja)

499
00:38:25,970 --> 00:38:33,880
Pra, vini re se kjo është gati - strukturalisht shumë të ngjashme me zgjidhjen përsëritës.

500
00:38:33,880 --> 00:38:38,200
Është vetëm se në vend të recursing, kemi pasur një lak kohë.

501
00:38:38,200 --> 00:38:40,840
Dhe rasti baza këtu, ku pema nuk null barabartë

502
00:38:40,840 --> 00:38:44,850
ishte kushti nën të cilin u ndamë nga lak, ndërsa.

503
00:38:44,850 --> 00:38:50,200
Ata janë shumë të ngjashme. Por ne jemi duke shkuar për të marrë këtë hap më tej.

504
00:38:50,200 --> 00:38:54,190
Tani, ne bëjmë të njëjtën gjë këtu.

505
00:38:54,190 --> 00:38:57,680
Njoftim ne jemi kthyer të njëjtën gjë në të dyja këto linja,

506
00:38:57,680 --> 00:39:00,220
me përjashtim të një argumenti është i ndryshëm.

507
00:39:00,220 --> 00:39:07,950
Pra, ne jemi duke shkuar për të bërë që në një tresh.

508
00:39:07,950 --> 00:39:13,790
I goditi diçka opsion, dhe ajo bëri një simbol. Rregull.

509
00:39:13,790 --> 00:39:21,720
Pra, ne jemi duke shkuar për t'u kthyer që përmban.

510
00:39:21,720 --> 00:39:28,030
Kjo po bëhet që të jetë linja të shumta, mirë, kjo është zoomed në.

511
00:39:28,030 --> 00:39:31,060
Zakonisht, si një gjë e stilistike, unë nuk mendoj se shumë njerëz

512
00:39:31,060 --> 00:39:38,640
vënë një hapësirë ​​pas shigjetë, por unë mendoj nëse jeni të qëndrueshëm, kjo është në rregull.

513
00:39:38,640 --> 00:39:44,320
Nëse vlera është më e vogël se vlera e pemës, ne duam të recurse pemë në të majtë,

514
00:39:44,320 --> 00:39:53,890
tjetër ne duam të recurse në të drejtën e pemë.

515
00:39:53,890 --> 00:39:58,610
Kështu që ishte një hap për të bërë këtë vështrim të vogla.

516
00:39:58,610 --> 00:40:02,660
Hapi dy për të bërë këtë vështrim të vogla -

517
00:40:02,660 --> 00:40:09,150
Ne mund t'i ndajmë këtë për linja të shumta.

518
00:40:09,150 --> 00:40:16,500
Rregull. Hapi dy për të bërë atë të duket e vogël është këtu,

519
00:40:16,500 --> 00:40:25,860
Pra, vlera e kthimit barabartë vlerën pemë, ose përmban çfarëdo.

520
00:40:25,860 --> 00:40:28,340
>> Kjo është një gjë e rëndësishme.

521
00:40:28,340 --> 00:40:30,860
Unë nuk jam i sigurt nëse ai tha se në mënyrë eksplicite në klasë,

522
00:40:30,860 --> 00:40:34,740
por ai që quhet qark i shkurtër vlerësimit.

523
00:40:34,740 --> 00:40:41,060
Ideja këtu është vlera == vlera pemë.

524
00:40:41,060 --> 00:40:49,960
Nëse kjo është e vërtetë, atëherë kjo është e vërtetë, dhe ne duam të 'ose' se me çdo gjë që është e gjatë këtu.

525
00:40:49,960 --> 00:40:52,520
Pra edhe pa menduar për çdo gjë që është e gjatë këtu,

526
00:40:52,520 --> 00:40:55,070
çfarë është shprehja gjithë do të ktheheni?

527
00:40:55,070 --> 00:40:59,430
[Student] Vërtetë? Po >>, sepse vërtetë e çdo gjë,

528
00:40:59,430 --> 00:41:04,990
or'd - or'd apo e vërtetë me çdo gjë është domosdoshmërisht e vërtetë.

529
00:41:04,990 --> 00:41:08,150
Pra, sa më shpejt që ne e shohim vlerën e kthimit = vlerës pemë,

530
00:41:08,150 --> 00:41:10,140
ne jemi vetëm do të kthehen vërtetë.

531
00:41:10,140 --> 00:41:15,710
Jo edhe më tej do të recurse përmban poshtë vijës.

532
00:41:15,710 --> 00:41:20,980
Ne mund të marrë këtë hap më tej.

533
00:41:20,980 --> 00:41:29,490
Pema kthimi nuk pavlefshëm të barabartë dhe të gjithë këtë.

534
00:41:29,490 --> 00:41:32,650
Kjo e bëri atë një funksion-line.

535
00:41:32,650 --> 00:41:36,790
Kjo është gjithashtu një shembull i shkurtër qark vlerësimit.

536
00:41:36,790 --> 00:41:40,680
Por tani kjo është ide e njëjtë -

537
00:41:40,680 --> 00:41:47,320
në vend të - kështu që nëse pema nuk null barabartë - ose, edhe,

538
00:41:47,320 --> 00:41:49,580
në qoftë se pema e bën null barabartë, që është rasti e keqe,

539
00:41:49,580 --> 00:41:54,790
nëse pema është e barabartë null, atëherë kushti i parë do të jetë e rreme.

540
00:41:54,790 --> 00:42:00,550
Pra rreme anded me ndonjë gjë do të jetë ajo?

541
00:42:00,550 --> 00:42:04,640
[Student] False. Po >>. Kjo është gjysma tjetër e qark i shkurtër vlerësimit,

542
00:42:04,640 --> 00:42:10,710
ku në qoftë se pema nuk null jo të barabartë, atëherë ne nuk do të shkojnë edhe -

543
00:42:10,710 --> 00:42:14,930
ose në qoftë se pema e bën null barabartë, atëherë ne nuk do të bëjmë vlerën == vlerë pemë.

544
00:42:14,930 --> 00:42:17,010
Ne jemi vetëm do të kthehen menjëherë rreme.

545
00:42:17,010 --> 00:42:20,970
E cila është e rëndësishme, pasi në qoftë se ajo nuk shkurtër qark të vlerësuar,

546
00:42:20,970 --> 00:42:25,860
atëherë në qoftë se pema e bën null barabartë, ky kusht i dytë do të defektit Seg,

547
00:42:25,860 --> 00:42:32,510
sepse pema-> vlera null dereferencing.

548
00:42:32,510 --> 00:42:40,490
Pra, kjo është se. Mund të bëjë këtë - zhvendoset herë gjatë.

549
00:42:40,490 --> 00:42:44,840
Kjo është një gjë shumë e zakonshme gjithashtu, nuk e bërë këtë një linjë me këtë,

550
00:42:44,840 --> 00:42:49,000
por kjo është një gjë e zakonshme në kushtet e, ndoshta jo të drejtë këtu,

551
00:42:49,000 --> 00:42:59,380
por në qoftë se (! pemë = NULL, dhe pemë-> vlera == vlera), të bëjë çdo gjë.

552
00:42:59,380 --> 00:43:01,560
Ky është një kusht shumë i zakonshëm, ku në vend të

553
00:43:01,560 --> 00:43:06,770
për të thyer këtë në dy VJ, ku si, është null pema?

554
00:43:06,770 --> 00:43:11,780
Mirë, nuk është i pavlefshëm, kështu që tani është vlera pema e barabartë me vlerën e? Bëni këtë.

555
00:43:11,780 --> 00:43:17,300
Në vend të kësaj, ky kusht, kjo kurrë nuk do të seg faj

556
00:43:17,300 --> 00:43:21,220
sepse ajo do të shpërthejë nëse kjo ndodh të jetë null.

557
00:43:21,220 --> 00:43:24,000
Well, I guess nëse pema juaj është një tregues tërësisht i pavlefshëm, ajo ende mund të seg faj,

558
00:43:24,000 --> 00:43:26,620
por ajo nuk mund seg faj nëse pema është i pavlefshëm.

559
00:43:26,620 --> 00:43:32,900
Nëse do të ishte null, ajo do të shpërthejë para se dereferenced ndonjëherë treguesin në vendin e parë.

560
00:43:32,900 --> 00:43:35,000
[Student] A është ky vlerësim i quajtur dembel?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] vlerësimi Lazy është një gjë e veçantë.

562
00:43:40,770 --> 00:43:49,880
Vlerësimi Lazy është më shumë si ju kërkoni për një vlerë,

563
00:43:49,880 --> 00:43:54,270
ju kërkoni për të llogaritur një vlerë, lloj, por ju nuk keni nevojë atë menjëherë.

564
00:43:54,270 --> 00:43:59,040
Pra, deri sa ju të vërtetë nevojë për të, ajo nuk është vlerësuar.

565
00:43:59,040 --> 00:44:03,920
Kjo nuk është saktësisht e njëjta gjë, por në pset Huffman,

566
00:44:03,920 --> 00:44:06,520
ai thotë se ne "lazily" shkruajnë.

567
00:44:06,520 --> 00:44:08,670
Arsyeja që ne të bërë këtë është për shkak se ne jemi në fakt buffering e shkrimit -

568
00:44:08,670 --> 00:44:11,820
ne nuk duam të shkruani bit individuale në një kohë,

569
00:44:11,820 --> 00:44:15,450
ose bytes individuale në një kohë, ne vend të dëshironi të merrni një copë e bytes.

570
00:44:15,450 --> 00:44:19,270
Pastaj një herë ne kemi një copë të bytes, atëherë ne do të shkruajnë atë.

571
00:44:19,270 --> 00:44:22,640
Edhe pse ju kërkoni atë për të shkruar - dhe fwrite dhe fread të bëjë të njëjtin lloj gjë.

572
00:44:22,640 --> 00:44:26,260
Ata tampon lexon dhe shkruan tuaj.

573
00:44:26,260 --> 00:44:31,610
Edhe pse ju kërkoni atë për të shkruar menjëherë, ajo ndoshta nuk do të.

574
00:44:31,610 --> 00:44:34,540
Dhe ju nuk mund të jetë i sigurt se gjërat do të jetë e shkruar

575
00:44:34,540 --> 00:44:37,540
derisa ju telefononi hfclose apo çfarëdo qoftë ajo është,

576
00:44:37,540 --> 00:44:39,620
e cila më pas thotë, në rregull, unë jam i mbyllur dosjen time,

577
00:44:39,620 --> 00:44:43,450
që do të thotë unë do të shkruaj më mirë gjithçka që unë nuk kam shkruar ende.

578
00:44:43,450 --> 00:44:45,770
Ajo nuk ka nevojë për të shkruar çdo gjë jashtë

579
00:44:45,770 --> 00:44:49,010
derisa ju jeni mbyllur dosjen, dhe pastaj ajo ka nevojë për të.

580
00:44:49,010 --> 00:44:56,220
Pra, kjo është vetëm ajo dembel - ajo pret derisa ajo ka për të ndodhë.

581
00:44:56,220 --> 00:44:59,990
Kjo - të marrë 51 dhe ju do të shkoni në atë më në detaje,

582
00:44:59,990 --> 00:45:05,470
sepse OCaml dhe gjithçka në 51, çdo gjë është recursion.

583
00:45:05,470 --> 00:45:08,890
Nuk ka zgjidhje përsëritës, në thelb.

584
00:45:08,890 --> 00:45:11,550
Çdo gjë është recursion, dembel dhe vlerësimi

585
00:45:11,550 --> 00:45:14,790
do të jetë e rëndësishme për një shumë të rrethanave

586
00:45:14,790 --> 00:45:19,920
ku, në qoftë se ju nuk e keni vlerësuar lazily, që do të thotë -

587
00:45:19,920 --> 00:45:24,760
Shembulli është streams, të cilat janë pafundësisht të gjatë.

588
00:45:24,760 --> 00:45:30,990
Në teori, ju mund të mendoni e numrave natyrore si një lumë i 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Pra, gjërat lazily vlerësuara janë të mirë.

590
00:45:33,090 --> 00:45:37,210
Nëse unë them unë dua numrin dhjetë, atëherë unë mund të vlerësojnë deri në numrin dhjetë.

591
00:45:37,210 --> 00:45:40,300
Nëse unë dua numrin njëqindtë, atëherë unë mund të vlerësojnë deri në numrin e qindta.

592
00:45:40,300 --> 00:45:46,290
Pa vlerësimit dembel, atëherë ajo do të përpiqet për të vlerësuar të gjithë numrat menjëherë.

593
00:45:46,290 --> 00:45:50,000
Ju jeni vlerësimin numrat pafundësisht shumë, dhe kjo është jo vetëm e mundur.

594
00:45:50,000 --> 00:45:52,080
Pra, ka shumë rrethana ku vlerësimi dembel

595
00:45:52,080 --> 00:45:57,840
është vetëm e domosdoshme për marrjen e gjëra për të punuar.

596
00:45:57,840 --> 00:46:05,260
>> Tani ne duam të shkruani insert ku insert do të jetë

597
00:46:05,260 --> 00:46:08,430
në mënyrë të ngjashme duke ndryshuar në përcaktimin e saj.

598
00:46:08,430 --> 00:46:10,470
Deri tani ajo është futur bool (vlera int).

599
00:46:10,470 --> 00:46:23,850
Ne jemi duke shkuar për të ndryshuar që të insert bool (int, vlera nyjen * pemë).

600
00:46:23,850 --> 00:46:29,120
Ne jemi të vërtetë do të ndryshojë se përsëri në një grimë, ne do të shohim se pse.

601
00:46:29,120 --> 00:46:32,210
Dhe le të shkojë build_node, vetëm për dreq e tij,

602
00:46:32,210 --> 00:46:36,730
sipër të futur kështu që ne nuk kemi për të shkruar një prototip funksion.

603
00:46:36,730 --> 00:46:42,450
E cila është një aluzion se ju jeni do të jetë duke përdorur build_node në insert.

604
00:46:42,450 --> 00:46:49,590
Rregull. Merrni një minutë për këtë.

605
00:46:49,590 --> 00:46:52,130
Unë mendoj se kam ruajtur rishikimin në qoftë se ju doni të tërheqë nga ajo,

606
00:46:52,130 --> 00:47:00,240
ose, të paktën, kam bërë tani.

607
00:47:00,240 --> 00:47:04,190
Doja një pushim të vogël për të menduar për logjikën e futur,

608
00:47:04,190 --> 00:47:08,750
në qoftë se ju nuk mund të mendoj për atë.

609
00:47:08,750 --> 00:47:12,860
Në thelb, ju vetëm do të jetë ndonjëherë futur në gjethe.

610
00:47:12,860 --> 00:47:18,640
Si, në qoftë se unë insert 1, atëherë unë jam në mënyrë të pashmangshme do të jetë futur 1 -

611
00:47:18,640 --> 00:47:21,820
Unë do të ndryshojë në të zezë - I'll të futur 1 mbi këtu.

612
00:47:21,820 --> 00:47:28,070
Ose në qoftë se unë insert 4, unë dua të futur 4 mbi këtu.

613
00:47:28,070 --> 00:47:32,180
Pra, pa marrë parasysh atë që ju bëni, ju do të jeni të futur në një fletë.

614
00:47:32,180 --> 00:47:36,130
Të gjithë ju duhet të bëni është të iterate drurin derisa ju të merrni në nyje

615
00:47:36,130 --> 00:47:40,890
që duhet të jetë prindi nyjen së, prindi nyja të ri,

616
00:47:40,890 --> 00:47:44,560
dhe pastaj të ndryshojë treguesin e majtë apo të djathtë, në varësi të faktit nëse

617
00:47:44,560 --> 00:47:47,060
kjo është më e madhe se ose më pak se nyjen e tanishme.

618
00:47:47,060 --> 00:47:51,180
Ndryshimi që treguesin për pikë në nyje tuaj të re.

619
00:47:51,180 --> 00:48:05,490
Pra iterate drurin, të bëjë pikë fletë në nyje të ri.

620
00:48:05,490 --> 00:48:09,810
Gjithashtu mendoj se pse që ndalon llojin e situatës para,

621
00:48:09,810 --> 00:48:17,990
ku kam ndërtuar pemë binare ku ajo ishte e saktë

622
00:48:17,990 --> 00:48:19,920
në qoftë se ju vetëm dukej në një nyje të vetme,

623
00:48:19,920 --> 00:48:24,830
9 por ishte në të majtë të përsëritur 7 në qoftë se ju të gjithë rrugën poshtë.

624
00:48:24,830 --> 00:48:29,770
Pra, kjo është e pamundur në këtë skenar, pasi -

625
00:48:29,770 --> 00:48:32,530
mendoni rreth 9 futur apo diçka; në nyjen e parë,

626
00:48:32,530 --> 00:48:35,350
Unë jam duke shkuar për të parë 7 dhe unë jam vetëm duke shkuar për të shkuar në të djathtë.

627
00:48:35,350 --> 00:48:38,490
Kështu që nuk ka rëndësi se çfarë të bëj, në qoftë se unë jam duke shkuar për të futur një fletë,

628
00:48:38,490 --> 00:48:40,790
dhe në një fletë duke përdorur algoritmin e duhur,

629
00:48:40,790 --> 00:48:43,130
ajo do të jetë e pamundur për mua për të futur 9 të majtë e 7

630
00:48:43,130 --> 00:48:48,250
sepse sa më shpejt që unë goditi 7 Unë jam duke shkuar për të shkuar në të djathtë.

631
00:48:59,740 --> 00:49:02,070
Ka njeri të ketë diçka për të filluar me?

632
00:49:02,070 --> 00:49:05,480
[Student] bëj unë. Sigurisht >>.

633
00:49:05,480 --> 00:49:09,200
[Student, pakuptueshëm]

634
00:49:09,200 --> 00:49:14,390
[Student tjera, pakuptueshëm]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Është vlerësuar. Rregull. Dëshironi të shpjegoni?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Që ne e dimë se ne ishim futur

637
00:49:20,690 --> 00:49:24,060
nyjet e reja në fund të pemës,

638
00:49:24,060 --> 00:49:28,070
Unë looped nëpër pemë iteratively

639
00:49:28,070 --> 00:49:31,360
derisa unë kam një nyje që vinte në dukje null.

640
00:49:31,360 --> 00:49:34,220
Dhe pastaj kam vendosur për të vënë atë ose në anën e djathtë ose e majtë

641
00:49:34,220 --> 00:49:37,420
duke përdorur këtë variabël të drejtë, ai më tha se ku për të vënë atë.

642
00:49:37,420 --> 00:49:41,850
Dhe pastaj, në thelb, unë vetëm e bëri që zgjasin -

643
00:49:41,850 --> 00:49:47,520
se nyja temp pikë në nyje të ri që është krijuar,

644
00:49:47,520 --> 00:49:50,770
ose në anën e majtë ose në të djathtë, në varësi të asaj vlera e drejtë ishte.

645
00:49:50,770 --> 00:49:56,530
Së fundi, kam vendosur vlera të reja nyje me vlerën e testimit saj.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Mirë, kështu që unë shoh një çështje këtu.

647
00:49:59,550 --> 00:50:02,050
Kjo është si 95% të rrugës atje.

648
00:50:02,050 --> 00:50:07,550
Një çështje që unë shoh, mirë, dikush tjetër do të shihni një çështje?

649
00:50:07,550 --> 00:50:18,400
Çfarë është rrethanë, sipas të cilës ata thyejnë nga lak?

650
00:50:18,400 --> 00:50:22,100
[Student] Nëse temp është i pavlefshëm? Po >>. Pra, si ju thyer nga lak është nëse temp është i pavlefshëm.

651
00:50:22,100 --> 00:50:30,220
Por çfarë të bëj këtu?

652
00:50:30,220 --> 00:50:35,410
Unë temp dereference, e cila është në mënyrë të pashmangshme null.

653
00:50:35,410 --> 00:50:39,840
Pra, gjëja tjetër që ju duhet të bëni nuk është vetëm të mbajnë gjurmët deri në temp është i pavlefshëm,

654
00:50:39,840 --> 00:50:45,590
ju doni të mbani gjurmët e prindit në të gjitha kohët.

655
00:50:45,590 --> 00:50:52,190
Ne gjithashtu duam * prind nyje, unë mendoj ne mund të vazhdojmë që në në fillim null.

656
00:50:52,190 --> 00:50:55,480
Kjo do të ketë sjellje të pazakontë për rrënjët e pemës,

657
00:50:55,480 --> 00:50:59,210
por ne do të merrni për këtë.

658
00:50:59,210 --> 00:51:03,950
Nëse vlera është më e madhe se çfarëdo, atëherë temp temp = drejtë.

659
00:51:03,950 --> 00:51:07,910
Por, para se të bëjmë këtë, prindi = temp.

660
00:51:07,910 --> 00:51:14,500
Ose janë prindërit gjithmonë do të temp të barabartë? Është se çështja?

661
00:51:14,500 --> 00:51:19,560
Nëse temp nuk është i pavlefshëm, atëherë unë jam duke shkuar për të lëvizur poshtë, pa marrë parasysh se çfarë,

662
00:51:19,560 --> 00:51:24,030
te nje nyje për të cilën temp është prind.

663
00:51:24,030 --> 00:51:27,500
Pra, prindi do të jetë temp, dhe pastaj kam lëvizur temp poshtë.

664
00:51:27,500 --> 00:51:32,410
Tani temp është null, por thekson prind të prindit të gjë që është null.

665
00:51:32,410 --> 00:51:39,110
Pra këtu poshtë, unë nuk dua për të vendosur të drejtën e barabartë me 1.

666
00:51:39,110 --> 00:51:41,300
Kështu që unë u zhvendos në të djathtë, kështu që nëse e drejta = 1,

667
00:51:41,300 --> 00:51:45,130
dhe unë mendoj se edhe ju doni të bëni -

668
00:51:45,130 --> 00:51:48,530
nëse ju hyni në të majtë, ju doni për të vendosur të drejtën e barabartë me 0.

669
00:51:48,530 --> 00:51:55,950
Ose tjetër, nëse ndonjëherë ju të lëvizin në të djathtë.

670
00:51:55,950 --> 00:51:58,590
Në mënyrë të drejtë = 0. Nëse = 1 djathtë,

671
00:51:58,590 --> 00:52:04,260
tani ne duam të bërë të drejtën prind newnode akrep,

672
00:52:04,260 --> 00:52:08,520
tjetër ne duam të bërë majtë prind newnode akrep.

673
00:52:08,520 --> 00:52:16,850
Pyetjet për këtë?

674
00:52:16,850 --> 00:52:24,880
Rregull. Pra, kjo është mënyra se si ne - mirë, në të vërtetë, në vend të bërë këtë,

675
00:52:24,880 --> 00:52:29,630
Ne gjysma pritet që të përdorni build_node.

676
00:52:29,630 --> 00:52:40,450
Dhe pastaj, nëse është e barabartë newnode null, kthehen rreme.

677
00:52:40,450 --> 00:52:44,170
Kjo është se. Tani, kjo është ajo që kemi pritur që ju të bëni.

678
00:52:44,170 --> 00:52:47,690
>> Kjo është ajo që zgjidhjet e stafit të bëjë.

679
00:52:47,690 --> 00:52:52,360
Unë nuk pajtohem me këtë si mënyrën e "drejtë" për të shkuar në lidhje me të

680
00:52:52,360 --> 00:52:57,820
por kjo është krejtësisht e mirë dhe ajo do të punojë.

681
00:52:57,820 --> 00:53:02,840
Një gjë që është një e drejtë pak i çuditshëm tani është

682
00:53:02,840 --> 00:53:08,310
në qoftë se pema fillon si null, ne të kalojë në një pemë null.

683
00:53:08,310 --> 00:53:12,650
Unë mendoj se varet se si ju define sjelljen e kalimit në një pemë null.

684
00:53:12,650 --> 00:53:15,490
Unë do të mendoj se në qoftë se ju të kalojë në një pemë null,

685
00:53:15,490 --> 00:53:17,520
pastaj futur vlera në një pemë null

686
00:53:17,520 --> 00:53:23,030
duhet vetëm të kthehet në një pemë, ku vlera e vetme është se nyja e vetme.

687
00:53:23,030 --> 00:53:25,830
Njerëzit dakord me këtë? Ju mund të, nëse do të donit,

688
00:53:25,830 --> 00:53:28,050
në qoftë se ju të kalojë në një pemë null

689
00:53:28,050 --> 00:53:31,320
dhe ju doni të futur një vlerë në të, kthimit të rreme.

690
00:53:31,320 --> 00:53:33,830
Është e deri tek ju për të përcaktuar se.

691
00:53:33,830 --> 00:53:38,320
Për të bërë gjënë e parë dhe pastaj thashë -

692
00:53:38,320 --> 00:53:40,720
mirë, ju jeni do të ketë probleme duke bërë këtë, sepse

693
00:53:40,720 --> 00:53:44,090
ajo do të jetë më e lehtë në qoftë se kemi pasur një tregues globale për gjë,

694
00:53:44,090 --> 00:53:48,570
por ne nuk e bëjnë, kështu që nëse pema është i pavlefshëm, nuk ka asgjë që mund të bëjmë për këtë.

695
00:53:48,570 --> 00:53:50,960
Ne vetëm mund të kthehen rreme.

696
00:53:50,960 --> 00:53:52,840
Kështu që unë jam duke shkuar për të ndryshuar futur.

697
00:53:52,840 --> 00:53:56,540
Ne teknikisht mund vetëm të ndryshojë këtë të drejtë këtu,

698
00:53:56,540 --> 00:53:58,400
se si është iterating mbi gjërat,

699
00:53:58,400 --> 00:54:04,530
por unë jam duke shkuar për të ndryshuar futur për të marrë një nyje ** pemë.

700
00:54:04,530 --> 00:54:07,510
Pointers dyfishtë.

701
00:54:07,510 --> 00:54:09,710
Çfarë do të thotë kjo?

702
00:54:09,710 --> 00:54:12,330
Në vend që të merret me pointers në nyje,

703
00:54:12,330 --> 00:54:16,690
gjë që unë jam duke shkuar për të manipuluar është ky pointer.

704
00:54:16,690 --> 00:54:18,790
Unë jam duke shkuar për të manipuluar këtë tregues.

705
00:54:18,790 --> 00:54:21,770
Unë jam duke shkuar për të manipuluar pointers direkt.

706
00:54:21,770 --> 00:54:25,760
Kjo ka kuptim që, mendoj për poshtë -

707
00:54:25,760 --> 00:54:33,340
mirë, tani kjo pikë për null.

708
00:54:33,340 --> 00:54:38,130
Ajo që unë dua të bëj është të manipuluar këtë tregues për pikë për të mos null.

709
00:54:38,130 --> 00:54:40,970
Unë dua që ajo të tregojë nyje tim të ri.

710
00:54:40,970 --> 00:54:44,870
Në qoftë se unë vetëm i mbajnë gjurmët e pointers për pointers mia,

711
00:54:44,870 --> 00:54:47,840
atëherë unë nuk kam nevojë për të mbajtur gjurmët e një tregues mëmë.

712
00:54:47,840 --> 00:54:52,640
Unë vetëm mund të mbajnë gjurmët për të parë nëse kursori është duke treguar null,

713
00:54:52,640 --> 00:54:54,580
dhe nëse treguesi është duke treguar null,

714
00:54:54,580 --> 00:54:57,370
ndryshojë atë për pikë në nyje dua.

715
00:54:57,370 --> 00:55:00,070
Dhe unë mund të ndryshojë atë që unë kam një tregues për treguesin.

716
00:55:00,070 --> 00:55:02,040
Le të shohim këtë të drejtë tani.

717
00:55:02,040 --> 00:55:05,470
Ju në fakt mund të bëjë atë Recursively mjaft lehtë.

718
00:55:05,470 --> 00:55:08,080
A duam të bëjmë këtë?

719
00:55:08,080 --> 00:55:10,980
Po, ne bëjmë.

720
00:55:10,980 --> 00:55:16,790
>> Le të shohim atë Recursively.

721
00:55:16,790 --> 00:55:24,070
Së pari, çfarë është rasti ynë bazë do të jetë?

722
00:55:24,070 --> 00:55:29,140
Pothuajse gjithmonë rasti ynë bazë, por në fakt, kjo është lloj i ndërlikuar.

723
00:55:29,140 --> 00:55:34,370
Gjërat e parë e parë, në qoftë se (== NULL pemë)

724
00:55:34,370 --> 00:55:37,550
I guess ne jemi vetëm do të kthehen rreme.

725
00:55:37,550 --> 00:55:40,460
Kjo është e ndryshme nga pemë null tuaj tani.

726
00:55:40,460 --> 00:55:44,510
Ky është tregues për treguesin tuaj rrënjë qenë null

727
00:55:44,510 --> 00:55:48,360
që do të thotë se treguesin tuaj rrënjë nuk ekziston.

728
00:55:48,360 --> 00:55:52,390
Pra këtu poshtë, në qoftë se unë bëj

729
00:55:52,390 --> 00:55:55,760
* nyje - le të vetëm të ripërdorimin këtë.

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

731
00:55:58,960 --> 00:56:00,730
dhe atëherë unë jam duke shkuar për të thirrur futur duke bërë diçka të tillë,

732
00:56:00,730 --> 00:56:04,540
futur në 4 & rrënjë.

733
00:56:04,540 --> 00:56:06,560
Pra dhe rrënjë, nëse rrënja është një nyje *

734
00:56:06,560 --> 00:56:11,170
atëherë dhe rrënjë është do të jetë një nyjë **.

735
00:56:11,170 --> 00:56:15,120
Kjo është e vlefshme. Në këtë rast, pemë, deri këtu,

736
00:56:15,120 --> 00:56:20,120
pema nuk është null - ose insert.

737
00:56:20,120 --> 00:56:24,630
Këtu. Pema nuk është i pavlefshëm; * pema është i pavlefshëm, e cila është e mirë

738
00:56:24,630 --> 00:56:26,680
sepse në qoftë se pema * është null, atëherë unë mund të manipulojnë atë

739
00:56:26,680 --> 00:56:29,210
tani tregojnë për atë që unë dua që ajo të tregojë.

740
00:56:29,210 --> 00:56:34,750
Por në qoftë se pema është i pavlefshëm, që do të thotë unë vetëm erdhi këtu dhe tha null.

741
00:56:34,750 --> 00:56:42,710
Kjo nuk ka kuptim. Unë nuk mund të bëjë asgjë me këtë.

742
00:56:42,710 --> 00:56:45,540
Nëse pema është null, kthimit të rreme.

743
00:56:45,540 --> 00:56:48,220
Kështu që unë në thelb thënë tashmë se çfarë ndodh vërtetë ynë bazë është.

744
00:56:48,220 --> 00:56:50,580
Dhe ajo që është se do të jetë?

745
00:56:50,580 --> 00:56:55,030
[Student, pakuptueshëm]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Po. Pra, në qoftë se (== NULL * pemë).

747
00:57:00,000 --> 00:57:04,520
Kjo ka të bëjë me rastin gjatë këtu

748
00:57:04,520 --> 00:57:09,640
ku nëse akrep ime e kuqe është tregues që unë jam përqëndruar në,

749
00:57:09,640 --> 00:57:12,960
kështu si unë jam i fokusuar në këtë tregues, tani unë jam i fokusuar në këtë tregues.

750
00:57:12,960 --> 00:57:15,150
Tani unë jam i fokusuar në këtë tregues.

751
00:57:15,150 --> 00:57:18,160
Pra, nëse pointer ime e kuqe, e cila është ** mi nyjë,

752
00:57:18,160 --> 00:57:22,880
është gjithnjë - nëse *, akrep ime e kuqe, është gjithnjë null,

753
00:57:22,880 --> 00:57:28,470
që do të thotë se unë jam në rastin kur unë jam përqëndruar në një tregues se pikat -

754
00:57:28,470 --> 00:57:32,530
ky është një tregues që i përket një gjethe.

755
00:57:32,530 --> 00:57:41,090
Unë dua të ndryshojë këtë tregues për pikë në nyje tim të ri.

756
00:57:41,090 --> 00:57:45,230
Vijnë përsëri mbi këtu.

757
00:57:45,230 --> 00:57:56,490
Newnode im do të jetë vetëm nyje * n = build_node (vlera)

758
00:57:56,490 --> 00:58:07,300
pastaj n, nëse n = null, kthehen rreme.

759
00:58:07,300 --> 00:58:12,600
Tjetër ne duam të ndryshojmë atë që kursori është duke treguar

760
00:58:12,600 --> 00:58:17,830
tani tregojnë për nyje tonë të ndërtuar rishtazi.

761
00:58:17,830 --> 00:58:20,280
Ne mund të bëjë në fakt që këtu.

762
00:58:20,280 --> 00:58:30,660
Në vend të thënë n, ne themi pema * = * nëse pemë.

763
00:58:30,660 --> 00:58:35,450
Gjithkush kuptojnë se? Që duke u marrë me pointers për pointers,

764
00:58:35,450 --> 00:58:40,750
ne mund të ndryshojmë pointers null që të tregojnë për gjërat që ne duam që ata të tregojnë për të.

765
00:58:40,750 --> 00:58:42,820
Kjo është rasti ynë bazë.

766
00:58:42,820 --> 00:58:45,740
>> Tani përsëritje tonë, ose recursion tonë,

767
00:58:45,740 --> 00:58:51,430
do të jetë shumë e ngjashme me të gjitha recursions tjera, ne kemi qenë duke bërë.

768
00:58:51,430 --> 00:58:55,830
Ne do të duan për të futur vlera,

769
00:58:55,830 --> 00:58:59,040
dhe tani unë jam duke shkuar për të përdorur tresh përsëri, por ajo që është gjendja jonë do të jetë?

770
00:58:59,040 --> 00:59:05,180
Çfarë është ajo që ne jemi duke kërkuar për të vendosur nëse duam të shkojmë majtas apo djathtas?

771
00:59:05,180 --> 00:59:07,760
Le të bëjmë atë në hapa të veçantë.

772
00:59:07,760 --> 00:59:18,850
Në qoftë se (vlera <) çfarë?

773
00:59:18,850 --> 00:59:23,200
[Student] vlerën e pemës së?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Pra, mos harroni se unë jam aktualisht -

775
00:59:27,490 --> 00:59:31,260
[Studentët, pakuptueshëm]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, në mënyrë të drejtë këtu, le të themi se kjo shigjetë e gjelbër

777
00:59:34,140 --> 00:59:39,050
është një shembull i asaj që pema është aktualisht, është një tregues për këtë tregues.

778
00:59:39,050 --> 00:59:46,610
Kështu që do të thotë që unë jam një tregues për një tregues për 3.

779
00:59:46,610 --> 00:59:48,800
The dereference dy herë dukej mirë.

780
00:59:48,800 --> 00:59:51,010
Çfarë - si mund ta bëni këtë?

781
00:59:51,010 --> 00:59:53,210
[Student] Dereference herë, dhe pastaj të bëjë shigjeta në këtë mënyrë?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Pra, (* pemë) është dereference herë, -> vlera

783
00:59:58,420 --> 01:00:05,960
do të më jepni vlerën e nyjeve që unë jam në mënyrë të tërthortë duke treguar për të.

784
01:00:05,960 --> 01:00:11,980
Kështu që unë mund të shkruaj atë ** tree.value nëse ju preferoni atë.

785
01:00:11,980 --> 01:00:18,490
Ose punon.

786
01:00:18,490 --> 01:00:26,190
Në qoftë se është rasti, atëherë unë dua të thërrasë futur me vlerë.

787
01:00:26,190 --> 01:00:32,590
Dhe çfarë është nyja e mia ** përditësuar do të jetë?

788
01:00:32,590 --> 01:00:39,440
Unë dua të shkoj në të majtë, kështu ** tree.left do të jetë majtë im.

789
01:00:39,440 --> 01:00:41,900
Dhe unë dua tregues për atë gjë

790
01:00:41,900 --> 01:00:44,930
kështu që nëse e majta përfundon duke qenë tregues null,

791
01:00:44,930 --> 01:00:48,360
Unë mund të modifikojë atë për pikë në nyje tim të ri.

792
01:00:48,360 --> 01:00:51,460
>> Dhe rasti tjetër mund të jetë shumë e ngjashme.

793
01:00:51,460 --> 01:00:55,600
Le të bëjë në fakt që tresh time tani.

794
01:00:55,600 --> 01:01:04,480
Vendos vlerën në qoftë se vlera <(** pemë). Vlera.

795
01:01:04,480 --> 01:01:11,040
Atëherë ne duam të rinovuar ** tona në të majtë,

796
01:01:11,040 --> 01:01:17,030
tjetër ne duam të rinovuar ** tona në të djathtë.

797
01:01:17,030 --> 01:01:22,540
[Student] A do të merrni treguesin në treguesin?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Mos harroni se - ** tree.right është një yll nyje.

799
01:01:30,940 --> 01:01:35,040
[Student, pakuptueshëm] >> Yeah.

800
01:01:35,040 --> 01:01:41,140
** Tree.right është si ky shkop ose diçka.

801
01:01:41,140 --> 01:01:45,140
Pra, duke marrë një tregues për atë, që i jep mua atë që unë dua

802
01:01:45,140 --> 01:01:50,090
i treguesin në atë djalë.

803
01:01:50,090 --> 01:01:54,260
[Student] A mund të shkojmë përsëri arsyeja pse ne jemi duke përdorur dy pointers?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Pra, - jo, ju mund të, dhe se zgjidhja më parë

805
01:01:58,220 --> 01:02:04,540
ishte një mënyrë për të bërë atë pa bërë dy pointers.

806
01:02:04,540 --> 01:02:08,740
Ju duhet të jetë në gjendje për të kuptuar përdorimin e dy pointers,

807
01:02:08,740 --> 01:02:11,660
dhe kjo është një zgjidhje e pastër.

808
01:02:11,660 --> 01:02:16,090
Gjithashtu, vini re se, çfarë ndodh në qoftë se pema ime -

809
01:02:16,090 --> 01:02:24,480
çfarë ndodh nëse rrënja ime ishte null? Çfarë ndodh në qoftë se unë bëj këtë rast të drejtë këtu?

810
01:02:24,480 --> 01:02:30,540
Pra nyje * root = NULL, futur 4 në & rrënjë.

811
01:02:30,540 --> 01:02:35,110
Çfarë është rrënja do të jetë pas kësaj?

812
01:02:35,110 --> 01:02:37,470
[Student, pakuptueshëm] >> Yeah.

813
01:02:37,470 --> 01:02:41,710
Vlera rrënjë do të jetë 4.

814
01:02:41,710 --> 01:02:45,510
Root majtë do të jetë null, rrënja e drejtë do të jetë i pavlefshëm.

815
01:02:45,510 --> 01:02:49,490
Në rastet kur nuk kemi rrënjë të kalojë nga adresa,

816
01:02:49,490 --> 01:02:52,490
ne nuk mund të modifikoni rrënjë.

817
01:02:52,490 --> 01:02:56,020
Në rastin kur pema - ku rrënja ishte null,

818
01:02:56,020 --> 01:02:58,410
ne vetëm kishte për të kthyer rreme. Nuk ka asgjë që mund të bëni.

819
01:02:58,410 --> 01:03:01,520
Ne nuk mund të futur një nyje në një pemë bosh.

820
01:03:01,520 --> 01:03:06,810
Por tani ne mund, ne vetëm të bëjë një pemë bosh në një pemë një nyje.

821
01:03:06,810 --> 01:03:13,400
E cila është zakonisht mënyra pritur që ajo është menduar për të punuar.

822
01:03:13,400 --> 01:03:21,610
>> Për më tepër, kjo është dukshëm më e shkurtër se

823
01:03:21,610 --> 01:03:26,240
edhe mbajtja e prindit, dhe kështu ju iterate poshtë gjithë rrugën.

824
01:03:26,240 --> 01:03:30,140
Tani unë kam prind tim, dhe unë vetëm kam të drejtë treguesin time prind për çdo gjë.

825
01:03:30,140 --> 01:03:35,640
Në vend të kësaj, në qoftë se ne e bëmë këtë iteratively, ajo do të jetë ideja njëjtë me një lak, ndërsa.

826
01:03:35,640 --> 01:03:38,100
Por në vend që të merren me treguesin tim mëmë,

827
01:03:38,100 --> 01:03:40,600
vend akrep tim aktual do të jetë gjëja më

828
01:03:40,600 --> 01:03:43,790
që unë jam direkt modifikuar për pikë në nyje tim të ri.

829
01:03:43,790 --> 01:03:46,090
Unë nuk duhet të merren me faktin nëse është e treguar në të majtë.

830
01:03:46,090 --> 01:03:48,810
Unë nuk duhet të merren me faktin nëse është e treguar në të djathtë.

831
01:03:48,810 --> 01:04:00,860
Është vetëm çdo gjë që ky tregues është, unë jam duke shkuar për të vendosur atë në pikë në nyje tim të ri.

832
01:04:00,860 --> 01:04:05,740
Gjithkush kuptuar se si funksionon?

833
01:04:05,740 --> 01:04:09,460
Nëse pse nuk duam të bëjmë atë në këtë mënyrë,

834
01:04:09,460 --> 01:04:14,920
por të paktën se kjo punon si një zgjidhje?

835
01:04:14,920 --> 01:04:17,110
[Student] Ku nuk kemi kthim i vërtetë?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Kjo është ndoshta e drejtë këtu.

837
01:04:21,550 --> 01:04:26,690
Nëse ne duhet futur atë, kthim i vërtetë.

838
01:04:26,690 --> 01:04:32,010
Tjetër, këtu poshtë ne do të duan të kthehen në çfarëdo kthimit futur.

839
01:04:32,010 --> 01:04:35,950
>> Dhe ajo që është e veçantë në lidhje me këtë funksion rekursive?

840
01:04:35,950 --> 01:04:43,010
Është bisht rekursive, aq sa kohë që ne të hartojë me disa optimization,

841
01:04:43,010 --> 01:04:48,060
ajo do të njohin atë dhe ju kurrë nuk do të merrni një overflow stack nga kjo,

842
01:04:48,060 --> 01:04:53,230
edhe në qoftë se pema jonë ka një lartësi prej 10,000 apo 10 milion.

843
01:04:53,230 --> 01:04:55,630
[Student, pakuptueshëm]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Unë mendoj se kjo e bën atë në dash - apo çfarë niveli optimization

845
01:05:00,310 --> 01:05:03,820
është e nevojshme për një recursion bisht të njohur.

846
01:05:03,820 --> 01:05:09,350
Unë mendoj se ai njeh - GCC dhe tingëllimë

847
01:05:09,350 --> 01:05:12,610
gjithashtu kanë kuptime të ndryshme për nivelin e tyre optimization.

848
01:05:12,610 --> 01:05:17,870
Unë dua të them se është Dasho 2, me siguri se do të njohë recursion bisht.

849
01:05:17,870 --> 01:05:27,880
Por ne - ju mund të ndërtojë si një shembull Fibonocci apo diçka.

850
01:05:27,880 --> 01:05:30,030
Kjo nuk është e lehtë për të provuar me këtë, sepse kjo është e vështirë për të ndërtuar

851
01:05:30,030 --> 01:05:32,600
një pemë binare që është aq i madh.

852
01:05:32,600 --> 01:05:37,140
Por, vërtet, unë mendoj se është Dasho 2, që

853
01:05:37,140 --> 01:05:40,580
në qoftë se ju hartojnë me Dasho 2, ajo do të shikoni për recursion bisht

854
01:05:40,580 --> 01:05:54,030
dhe jam optimist se nga.

855
01:05:54,030 --> 01:05:58,190
Le të kthehemi në - futur fjalë për fjalë gjëja e fundit që ajo ka nevojë.

856
01:05:58,190 --> 01:06:04,900
Le të kthehemi në insert mbi këtu

857
01:06:04,900 --> 01:06:07,840
ku ne jemi duke shkuar për të bërë të njëjtën ide.

858
01:06:07,840 --> 01:06:14,340
Ajo ende do të ketë krisje të mos qenë në gjendje për të krejtësisht të handle

859
01:06:14,340 --> 01:06:17,940
kur rrënja vetë është i pavlefshëm, ose nga hyrja kaluara është null,

860
01:06:17,940 --> 01:06:20,060
por në vend që të merret me një tregues mëmë,

861
01:06:20,060 --> 01:06:27,430
le të aplikojnë të njëjtën logjikë e pointers mbajtur për pointers.

862
01:06:27,430 --> 01:06:35,580
Nëse këtu kemi mbajtur nyje tonë ** cur,

863
01:06:35,580 --> 01:06:37,860
dhe ne nuk kemi nevojë për të mbajtur gjurmët e drejtë më,

864
01:06:37,860 --> 01:06:47,190
por nyje ** cur = & pemë.

865
01:06:47,190 --> 01:06:54,800
Dhe tani loop tonë, ndërsa do të jetë duke cur * nuk null barabartë.

866
01:06:54,800 --> 01:07:00,270
A nuk duhet të mbajnë gjurmët e prindërve më.

867
01:07:00,270 --> 01:07:04,180
A nuk duhet të mbajnë gjurmët e majtë dhe të djathtë.

868
01:07:04,180 --> 01:07:10,190
Dhe unë do të thërrasë atë temp, sepse ne jemi tashmë duke përdorur Temp.

869
01:07:10,190 --> 01:07:17,200
Rregull. Pra, nëse (vlera> * temp),

870
01:07:17,200 --> 01:07:24,010
pastaj & (* temp) -> të drejtë

871
01:07:24,010 --> 01:07:29,250
tjetër temp = & (* temp) -> majtë.

872
01:07:29,250 --> 01:07:32,730
Dhe tani, në këtë pikë, pasi këtë lak, ndërsa,

873
01:07:32,730 --> 01:07:36,380
Unë vetëm të bëjë këtë, sepse ndoshta është më e lehtë për të menduar për iteratively se Recursively,

874
01:07:36,380 --> 01:07:39,010
por pas kësaj lak, ndërsa,

875
01:07:39,010 --> 01:07:43,820
* Temp është tregues që ne duam të ndryshojmë.

876
01:07:43,820 --> 01:07:48,960
>> Para se të kemi pasur prind, dhe ne të kërkuar për të ndryshuar ose majtas prindit ose prindit të drejtë,

877
01:07:48,960 --> 01:07:51,310
por në qoftë se ne duam të ndryshojmë drejtën prind,

878
01:07:51,310 --> 01:07:54,550
* temp atëherë është e drejtë prindi, dhe ne mund të ndryshojë atë direkt.

879
01:07:54,550 --> 01:08:05,860
Pra këtu poshtë, ne mund të bëjmë * temp = newnode, dhe kjo është ajo.

880
01:08:05,860 --> 01:08:09,540
Pra njoftimit, të gjithë ne e bëmë në këtë ishte marrë nga rreshta të kodit.

881
01:08:09,540 --> 01:08:14,770
Në mënyrë për të mbajtur gjurmët e prindit në të gjitha që është përpjekje shtesë.

882
01:08:14,770 --> 01:08:18,689
Këtu, në qoftë se ne vetëm i mbajnë gjurmët e treguesin në treguesin,

883
01:08:18,689 --> 01:08:22,990
dhe madje edhe në qoftë se ne të kërkuar për të hequr qafe të gjitha këto formatimin e teksteve kaçurrel tani,

884
01:08:22,990 --> 01:08:27,170
bërë atë të duket e shkurtër.

885
01:08:27,170 --> 01:08:32,529
Kjo tani është zgjidhja e saktë të njëjtën,

886
01:08:32,529 --> 01:08:38,210
por linjat pak të kodit.

887
01:08:38,210 --> 01:08:41,229
Pasi ju filloni duke njohur këtë si një zgjidhje të vlefshme,

888
01:08:41,229 --> 01:08:43,529
kjo është edhe më e lehtë për arsye se rreth si, rregull,

889
01:08:43,529 --> 01:08:45,779
pse nuk kam këtë flamur në të djathtë int?

890
01:08:45,779 --> 01:08:49,290
Çfarë do të thotë kjo? Oh, kjo është nënkuptuar se

891
01:08:49,290 --> 01:08:51,370
çdo herë që unë shkoj drejtë, kam nevojë për të vendosur atë,

892
01:08:51,370 --> 01:08:53,819
tjetër në qoftë se unë shkoj lënë kam nevojë për të vendosur atë në zero.

893
01:08:53,819 --> 01:09:04,060
Këtu, unë nuk kam lidhje me atë për arsye, por vetëm më të lehtë për të menduar rreth.

894
01:09:04,060 --> 01:09:06,710
Pyetje?

895
01:09:06,710 --> 01:09:16,290
[Student, pakuptueshëm] >> Yeah.

896
01:09:16,290 --> 01:09:23,359
Mirë, kështu që në pak fundit -

897
01:09:23,359 --> 01:09:28,080
I guess një funksion të shpejtë dhe të lehtë ne mund të bëjmë është,

898
01:09:28,080 --> 01:09:34,910
let's - së bashku, unë mendoj, të përpiqet dhe të shkruajnë një funksion përmban

899
01:09:34,910 --> 01:09:38,899
që nuk i intereson nëse ajo është një pemë binare kërkim.

900
01:09:38,899 --> 01:09:43,770
Kjo përmban funksion duhet të kthehen vërtetë

901
01:09:43,770 --> 01:09:58,330
në qoftë se kudo në këtë pemë binare e përgjithshme është vlera ne jemi duke kërkuar për të.

902
01:09:58,330 --> 01:10:02,520
Pra, le të bëjë atë të parë Recursively dhe pastaj ne do të bëjmë atë iteratively.

903
01:10:02,520 --> 01:10:07,300
Ne në fakt mund të bëni vetëm atë së bashku, sepse kjo do të jetë me të vërtetë të shkurtër.

904
01:10:07,300 --> 01:10:11,510
>> Çfarë është rasti im bazë do të jetë?

905
01:10:11,510 --> 01:10:13,890
[Student, pakuptueshëm]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Pra, në qoftë se (== NULL pemë), pastaj çfarë?

907
01:10:18,230 --> 01:10:22,740
[Student] Kthehu rreme.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, mirë, unë nuk nevojë tjetër.

909
01:10:26,160 --> 01:10:30,250
Nëse ishte rast tjetër mia bazë.

910
01:10:30,250 --> 01:10:32,450
Vlera [Student] TREE-së? Po >>.

911
01:10:32,450 --> 01:10:36,430
Pra, nëse (pemë-> vlera == vlerë.

912
01:10:36,430 --> 01:10:39,920
Njoftim ne jemi kthyer në nyjen * jo, nyja ** s?

913
01:10:39,920 --> 01:10:42,990
Përmban kurrë nuk do të duhet të përdorni një ** nyjen,

914
01:10:42,990 --> 01:10:45,480
pasi ne nuk jemi modifikuar pointers.

915
01:10:45,480 --> 01:10:50,540
Ne jemi vetëm duke traversing ato.

916
01:10:50,540 --> 01:10:53,830
Nëse kjo ndodh, atëherë ne duam të kthehen vërtetë.

917
01:10:53,830 --> 01:10:58,270
Tjetër ne duam të kaloj fëmijët.

918
01:10:58,270 --> 01:11:02,620
Pra, ne nuk mund të arsyetojë se nëse gjithçka në të majtë është më pak

919
01:11:02,620 --> 01:11:05,390
dhe çdo gjë në të djathtë është më e madhe.

920
01:11:05,390 --> 01:11:09,590
Pra, çfarë është gjendja jonë do të jetë këtu - apo, çka do të shkojmë për të bërë?

921
01:11:09,590 --> 01:11:11,840
[Student, pakuptueshëm] >> Yeah.

922
01:11:11,840 --> 01:11:17,400
Kthimi përmban (vlera pemë-> majtas)

923
01:11:17,400 --> 01:11:26,860
ose përmban (vlera pemë-> djathtas). Dhe kjo është ajo.

924
01:11:26,860 --> 01:11:29,080
Dhe vini re ka disa qark të shkurtër të vlerësimit,

925
01:11:29,080 --> 01:11:32,520
ku në qoftë se ne të ndodhë për të gjetur vlerën në pemë majtë,

926
01:11:32,520 --> 01:11:36,820
ne kurrë nuk duhet të shikojmë në pemë e duhur.

927
01:11:36,820 --> 01:11:40,430
Kjo është funksioni i tërë.

928
01:11:40,430 --> 01:11:43,690
Tani le të bëjmë atë iteratively,

929
01:11:43,690 --> 01:11:48,060
e cila do të jetë më pak e bukur.

930
01:11:48,060 --> 01:11:54,750
Ne do të marrë fillimin e zakonshme të nyjeve monedhes * = pemë.

931
01:11:54,750 --> 01:12:03,250
Ndërsa (tani! = NULL).

932
01:12:03,250 --> 01:12:08,600
Shpejt do të shohim një problem.

933
01:12:08,600 --> 01:12:12,250
Nëse momen - këtu, në qoftë se ne ndonjëherë të thyer nga kjo,

934
01:12:12,250 --> 01:12:16,020
atëherë ne kemi të drejtuar nga gjërat për të shikoni në, kështu që rezultati false.

935
01:12:16,020 --> 01:12:24,810
Në qoftë se (cur-> vlera == vlera), kthehen vërtetë.

936
01:12:24,810 --> 01:12:32,910
Deri tani, ne jemi në një vend -

937
01:12:32,910 --> 01:12:36,250
ne nuk e dimë nëse ne duam të shkojnë majtas ose djathtas.

938
01:12:36,250 --> 01:12:44,590
Pra arbitrarisht, le të shkojnë vetëm të majtë.

939
01:12:44,590 --> 01:12:47,910
Unë kam drejtuar padyshim në një çështje ku unë kam braktisur plotësisht gjithçka -

940
01:12:47,910 --> 01:12:50,760
Unë vetëm do të ndonjëherë të shikoni në anën e majtë të një pemë.

941
01:12:50,760 --> 01:12:56,050
Unë kurrë nuk do të kontrollojë çdo gjë që është një fëmijë të drejtën e çdo gjë.

942
01:12:56,050 --> 01:13:00,910
Si mund ta fix this?

943
01:13:00,910 --> 01:13:05,260
[Student] Ju duhet të mbajnë gjurmët e të majtë dhe të djathtë në një pirg.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Pra, le të bëjë atë

945
01:13:13,710 --> 01:13:32,360
struct lista, nyje * n, dhe pastaj nyjen ** ardhshme?

946
01:13:32,360 --> 01:13:40,240
Unë mendoj se works fine.

947
01:13:40,240 --> 01:13:45,940
Ne duam për të shkuar mbi të majtë, ose let's - deri këtu.

948
01:13:45,940 --> 01:13:54,350
Struct = listë listë, ajo do të fillojë

949
01:13:54,350 --> 01:13:58,170
jashtë në këtë listë struct.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Kështu që do të jetë e lidhur me listën tonë

951
01:14:04,040 --> 01:14:08,430
të tregoje se kemi anashkaluar.

952
01:14:08,430 --> 01:14:13,800
Ne do të kaloj mbetur tani,

953
01:14:13,800 --> 01:14:17,870
por që ne në mënyrë të pashmangshme duhet të kthehen në të djathtë,

954
01:14:17,870 --> 01:14:26,140
Ne jemi duke shkuar për të mbajtur anën e djathtë brenda listës sonë struct.

955
01:14:26,140 --> 01:14:32,620
Atëherë ne do të kemi new_list ose struct,

956
01:14:32,620 --> 01:14:41,080
struct * listë, new_list = malloc (sizeof (lista)).

957
01:14:41,080 --> 01:14:44,920
Unë jam duke shkuar për të injoruar error checking-se, por ju duhet të kontrolloni për të parë nëse është e pavlefshme.

958
01:14:44,920 --> 01:14:50,540
New_list nyjen ajo do të tregojnë për -

959
01:14:50,540 --> 01:14:56,890
oh, kjo është arsyeja pse kam kërkuar atë deri këtu. Ajo do të tregojnë për një listë të dytë struct.

960
01:14:56,890 --> 01:15:02,380
Kjo është vetëm se si të lidhura listat punë.

961
01:15:02,380 --> 01:15:04,810
Kjo është e njëjtë si një listë int lidhur

962
01:15:04,810 --> 01:15:06,960
përveç ne jemi vetëm duke zëvendësuar int me * nyjeve.

963
01:15:06,960 --> 01:15:11,040
Kjo është saktësisht e njëjtë.

964
01:15:11,040 --> 01:15:15,100
Pra new_list, vlera e nyjeve tonë new_list,

965
01:15:15,100 --> 01:15:19,120
do të jetë cur-> drejtë.

966
01:15:19,120 --> 01:15:24,280
Vlera e tonë new_list-> ardhshme do të jetë lista jonë origjinale,

967
01:15:24,280 --> 01:15:30,760
dhe pastaj ne jemi duke shkuar për të rinovuar listën tonë për pikë në new_list.

968
01:15:30,760 --> 01:15:33,650
>> Tani ne kemi nevojë për disa lloj mënyrë për të tërhequr gjërave,

969
01:15:33,650 --> 01:15:37,020
si kemi përshkuar tërë subtree majtë.

970
01:15:37,020 --> 01:15:40,480
Tani ne kemi nevojë për të tërhequr gjëra nga ajo,

971
01:15:40,480 --> 01:15:43,850
si cur është i pavlefshëm, ne nuk duam të kthehen vetëm false.

972
01:15:43,850 --> 01:15:50,370
Ne duam që tani të tërhequr jashtë në listën tonë të ri.

973
01:15:50,370 --> 01:15:53,690
Një mënyrë e përshtatshme për ta bërë këtë - mirë, në fakt, ka mënyra të shumta për ta bërë këtë.

974
01:15:53,690 --> 01:15:56,680
Çdokush kanë një sugjerim?

975
01:15:56,680 --> 01:15:58,790
Ku unë duhet të bëjë këtë apo se si unë duhet ta bëjë këtë?

976
01:15:58,790 --> 01:16:08,010
Ne kemi vetëm disa minuta, por çdo sugjerime?

977
01:16:08,010 --> 01:16:14,750
Në vend të - një mënyrë, në vend të të qenit, ndërsa gjendjen tonë,

978
01:16:14,750 --> 01:16:17,090
ajo që ne jemi aktualisht në kërkim të nuk është i pavlefshëm,

979
01:16:17,090 --> 01:16:22,340
në vend të kësaj ne do të vazhdojë të shkojë deri në listën tonë është vetë null.

980
01:16:22,340 --> 01:16:25,680
Pra, nëse lista jonë e përfundon duke u null,

981
01:16:25,680 --> 01:16:30,680
atëherë ne kemi drejtuar nga gjërat për të kërkuar, për të kërkuar gjatë.

982
01:16:30,680 --> 01:16:39,860
Por kjo do të thotë se gjëja e parë në listën tonë është vetëm do të jetë nyja e parë.

983
01:16:39,860 --> 01:16:49,730
Gjëja e parë do të jetë - ne nuk duhet të shohin se.

984
01:16:49,730 --> 01:16:58,710
Kështu lista-> n do të jetë pema tonë.

985
01:16:58,710 --> 01:17:02,860
lista-> ardhshme do të jetë e pavlefshme.

986
01:17:02,860 --> 01:17:07,580
Dhe tani, ndërsa lista nuk ka null barabartë.

987
01:17:07,580 --> 01:17:11,610
Cur do të tërheqë diçka nga lista tonë.

988
01:17:11,610 --> 01:17:13,500
Pra, cur do të barabartë lista-> n.

989
01:17:13,500 --> 01:17:20,850
Dhe pastaj lista do të barabartë lista-> n, ose lista-> ardhshëm.

990
01:17:20,850 --> 01:17:23,480
Pra, nëse vlera e monedhes barabartë vlerë.

991
01:17:23,480 --> 01:17:28,790
Tani ne mund të shtoni edhe treguesin tonë të drejtë dhe treguesin e majtë tonë

992
01:17:28,790 --> 01:17:32,900
për aq kohë sa ata nuk janë null.

993
01:17:32,900 --> 01:17:36,390
Poshtë këtu, unë mendoj se ne duhet të kemi bërë që në vendin e parë.

994
01:17:36,390 --> 01:17:44,080
Në qoftë se (cur-> drejtë! = NULL)

995
01:17:44,080 --> 01:17:56,380
atëherë ne jemi duke shkuar për të futur atë nyje në listën tonë.

996
01:17:56,380 --> 01:17:59,290
Në qoftë se (cur-> majtas), kjo është pak e punë shtesë, por kjo është në rregull.

997
01:17:59,290 --> 01:18:02,690
Në qoftë se (cur-> majtas! = NULL),

998
01:18:02,690 --> 01:18:14,310
dhe ne jemi duke shkuar për të futur të majtën në listën tonë të lidhura,

999
01:18:14,310 --> 01:18:19,700
dhe që duhet të jetë ajo.

1000
01:18:19,700 --> 01:18:22,670
Ne iterate - sa kohë që ne kemi diçka në listën tonë,

1001
01:18:22,670 --> 01:18:26,640
ne kemi një tjetër nyje për të parë në.

1002
01:18:26,640 --> 01:18:28,920
Kështu që ne shikojmë në atë nyje,

1003
01:18:28,920 --> 01:18:31,390
Ne përpara listën tonë me një tjetër.

1004
01:18:31,390 --> 01:18:34,060
Në qoftë se nyja është vlera ne jemi duke kërkuar për të, ne mund të kthehen vërtetë.

1005
01:18:34,060 --> 01:18:37,640
Tjetër futur dy tregoje tona majtë dhe të djathtë,

1006
01:18:37,640 --> 01:18:40,510
për aq kohë sa ata nuk janë null, në listën tonë

1007
01:18:40,510 --> 01:18:43,120
kështu që ne në mënyrë të pashmangshme të shkojë mbi ta.

1008
01:18:43,120 --> 01:18:45,160
Pra, në qoftë se ata nuk ishin null,

1009
01:18:45,160 --> 01:18:47,950
nëse treguesin tonë root vuri në dukje dy gjëra,

1010
01:18:47,950 --> 01:18:51,670
atëherë në fillim kemi tërhequr diçka kështu lista jonë përfundon duke u null.

1011
01:18:51,670 --> 01:18:56,890
Dhe pastaj ne kemi vënë përsëri në dy gjëra, kështu që tani është lista jonë e madhësisë 2.

1012
01:18:56,890 --> 01:19:00,030
Atëherë ne jemi duke shkuar për lak back up dhe ne jemi vetëm duke shkuar për të tërhequr,

1013
01:19:00,030 --> 01:19:04,250
le të themi, në treguesin e majtë të nyjes root tonë.

1014
01:19:04,250 --> 01:19:07,730
Dhe kjo do të ndodh vetëm i mbajnë, ne do të përfundojë deri në looping mbi çdo gjë.

1015
01:19:07,730 --> 01:19:11,280
>> Vini re se kjo ishte dukshëm më e komplikuar

1016
01:19:11,280 --> 01:19:14,160
në tretësirë ​​rekursive.

1017
01:19:14,160 --> 01:19:17,260
Dhe unë kam thënë shumë herë

1018
01:19:17,260 --> 01:19:25,120
se zgjidhja rekursive zakonisht ka shumë të përbashkëta me përsëritës zgjidhje.

1019
01:19:25,120 --> 01:19:30,820
Ja kjo është pikërisht ajo që zgjidhja rekursive është duke bërë.

1020
01:19:30,820 --> 01:19:36,740
Ndryshimi i vetëm është se në vend të implicite përdorur rafte, rafte programi,

1021
01:19:36,740 --> 01:19:40,840
si mënyrën tuaj të mbajtur gjurmët e asaj që nyjet ju ende nevojë për të vizituar,

1022
01:19:40,840 --> 01:19:45,430
tani ju duhet të përdorni në mënyrë eksplicite një listë të lidhura.

1023
01:19:45,430 --> 01:19:49,070
Në të dy rastet ju jeni mbajtja e asaj nyje ka ende nevojë për t'u vizituar.

1024
01:19:49,070 --> 01:19:51,790
Në rastin gjithkund rekursive është vetëm më e lehtë për shkak se një pirg

1025
01:19:51,790 --> 01:19:57,100
zbatohet për ju si rafte programit.

1026
01:19:57,100 --> 01:19:59,550
Vini re se kjo listë e lidhur, kjo është një pirg.

1027
01:19:59,550 --> 01:20:01,580
Çdo gjë që ne vetëm vënë në rafte

1028
01:20:01,580 --> 01:20:09,960
është menjëherë ajo që ne jemi duke shkuar për të tërhequr off rafte për të vizituar ardhshëm.

1029
01:20:09,960 --> 01:20:14,380
Ne jemi jashtë kohës, por ndonjë pyetje?

1030
01:20:14,380 --> 01:20:23,530
[Student, pakuptueshëm]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Pra, nëse kemi listën tonë të lidhur,

1032
01:20:27,790 --> 01:20:30,150
aktuale do të tregojnë për këtë djalë,

1033
01:20:30,150 --> 01:20:34,690
dhe tani ne jemi vetëm avancimin listën tonë lidhur me përqëndrohet në këtë djalë.

1034
01:20:34,690 --> 01:20:44,200
Ne jemi duke traversing më shumë se lista e lidhur në atë linjë.

1035
01:20:44,200 --> 01:20:51,200
Dhe atëherë unë mendoj se ne duhet të lirojë listën tonë dhe sende të lidhur

1036
01:20:51,200 --> 01:20:53,880
herë para se të kthehej vërtetë apo e rreme, ne duhet të

1037
01:20:53,880 --> 01:20:57,360
iterate mbi listën tonë dhe gjithmonë i lidhur këtu poshtë, unë mendoj,

1038
01:20:57,360 --> 01:21:03,900
në qoftë se ne cur e drejtë nuk është e barabartë me, shtoni atë, kështu që tani që ne duam të çlirojmë

1039
01:21:03,900 --> 01:21:09,600
cur, sepse, mirë, nuk e kemi plotësisht të harrojmë për listën e? Po.

1040
01:21:09,600 --> 01:21:12,880
Pra, kjo është ajo që ne duam të bëjmë këtu.

1041
01:21:12,880 --> 01:21:16,730
Ku është akrep?

1042
01:21:16,730 --> 01:21:23,320
Cur ishte atëherë - duam një listë struct * 10 është e barabartë me listë tjetër.

1043
01:21:23,320 --> 01:21:29,240
Lista e lirë, list = temp.

1044
01:21:29,240 --> 01:21:32,820
Dhe në rastin kur kemi të kthehen vërtetë, ne nuk duhet të iterate

1045
01:21:32,820 --> 01:21:37,050
mbi pjesën e mbetur të listës sonë i lidhur çlirimin gjëra.

1046
01:21:37,050 --> 01:21:39,700
Gjë e bukur për zgjidhjen e gjithkund rekursive është liruar gjëra

1047
01:21:39,700 --> 01:21:44,930
thjesht do të thotë factorings popping jashtë rafte e cila do të ndodhë për ju.

1048
01:21:44,930 --> 01:21:50,720
Pra, ne kemi shkuar nga diçka që është si 3 linjat e vështirë të mendoj-rreth kodit

1049
01:21:50,720 --> 01:21:57,520
për diçka që është dukshëm më shumë të vështirë të mendoj-rreth rreshta të kodit.

1050
01:21:57,520 --> 01:22:00,620
Më pyetje?

1051
01:22:00,620 --> 01:22:08,760
Dakord. Ne jemi të mirë. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]