1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Adran 7: Mwy cyfforddus]

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

3
00:00:05,090 --> 00:00:07,930
[Mae hyn yn CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Mae pob hawl. Felly, fel y dywedais yn fy e-bost,

5
00:00:10,110 --> 00:00:14,060
mae hyn yn mynd i fod yn rhan deuaidd-tree-ddwys.

6
00:00:14,060 --> 00:00:16,820
Ond nid oes yw bod llawer o gwestiynau.

7
00:00:16,820 --> 00:00:18,920
Felly, rydym yn mynd i geisio tynnu allan bob cwestiwn

8
00:00:18,920 --> 00:00:25,430
ac yn mynd i fanylder poenus o'r holl ffyrdd gorau o wneud pethau.

9
00:00:25,430 --> 00:00:31,200
Felly, i'r dde ar y dechrau, rydym yn mynd trwy luniadau sampl o goed deuaidd a stwff.

10
00:00:31,200 --> 00:00:35,970
Felly yma, "Cofiwch fod coeden ddeuaidd wedi nodau tebyg i'r rhai o restr cysylltiedig,

11
00:00:35,970 --> 00:00:38,150
ac eithrio yn lle un pwyntydd mae dau: un ar gyfer 'plentyn' y chwith

12
00:00:38,150 --> 00:00:41,950
ac un ar gyfer yr hawl 'plentyn'. "

13
00:00:41,950 --> 00:00:45,630
Felly goeden ddeuaidd yn union fel rhestr cysylltiedig,

14
00:00:45,630 --> 00:00:47,910
heblaw am y strwythur yn mynd i gael dau awgrymiadau.

15
00:00:47,910 --> 00:00:51,390
Mae coed trinary, sydd yn mynd i gael tri awgrymiadau,

16
00:00:51,390 --> 00:00:56,540
mae yna N-ary coed, a dim ond yn cael pwyntydd generig

17
00:00:56,540 --> 00:01:00,320
eich bod yn rhaid i malloc i fod yn ddigon mawr i gael

18
00:01:00,320 --> 00:01:04,840
awgrymiadau ddigon i holl blant y bo modd.

19
00:01:04,840 --> 00:01:08,200
Felly goeden ddeuaidd unig fydd yn digwydd i gael nifer cyson o ddau.

20
00:01:08,200 --> 00:01:11,260
Os hoffech, gallwch roi rhestr cysylltiedig fel coeden unary,

21
00:01:11,260 --> 00:01:15,360
ond nid wyf yn meddwl fod neb yn ei alw hynny.

22
00:01:15,360 --> 00:01:18,060
"Tynnwch ddiagram flychau-a-saethau o nod goeden ddeuol

23
00:01:18,060 --> 00:01:24,110
cynnwys Nate rhif hoff, 7, lle mae pob plentyn yn pwyntydd nwl. "

24
00:01:24,110 --> 00:01:27,780
Modd Felly iPad.

25
00:01:27,780 --> 00:01:30,280
>> Mae'n mynd i fod yn eithaf syml.

26
00:01:30,280 --> 00:01:36,150
Rydym yn unig yn mynd i gael nod, 'n annhymerus' tynnu fel sgwâr.

27
00:01:36,150 --> 00:01:38,730
A byddaf yn tynnu y gwerthoedd yma.

28
00:01:38,730 --> 00:01:41,090
Felly, bydd y gwerth yn mynd i mewn yma,

29
00:01:41,090 --> 00:01:44,770
ac yna i lawr yma byddwn yn cael y pwyntydd chwith ar y chwith a'r dde pwyntydd ar y dde.

30
00:01:44,770 --> 00:01:50,430
Ac mae'n iawn felly confensiwn i alw yn chwith a dde, enwau'r pwyntydd.

31
00:01:50,430 --> 00:01:52,460
Mae'r ddau o'r rhain yn mynd i fod yn null.

32
00:01:52,460 --> 00:01:57,870
Yn unig fydd honno null, ac y bydd dim ond yn null.

33
00:01:57,870 --> 00:02:03,630
Iawn. Felly cefn i yma.

34
00:02:03,630 --> 00:02:05,700
"Gyda rhestr cysylltiedig, dim ond bu'n rhaid i storio pwyntydd

35
00:02:05,700 --> 00:02:09,639
at y nod cyntaf yn y rhestr er mwyn cofio y rhestr gyfan sy'n gysylltiedig, neu restr gyfan.

36
00:02:09,639 --> 00:02:11,650
Yn yr un modd, gyda choed, dim ond rhaid i chi storio pwyntydd

37
00:02:11,650 --> 00:02:13,420
i un nod er mwyn cofio y goeden gyfan.

38
00:02:13,420 --> 00:02:15,980
Mae'r nod yn Calle y 'wraidd' y goeden.

39
00:02:15,980 --> 00:02:18,320
Adeiladu ar eich diagram o'r cyfnod cyn neu lunio un newydd

40
00:02:18,320 --> 00:02:21,690
fel bod gennych ddarlun flychau-a-saethau ar goeden ddeuaidd

41
00:02:21,690 --> 00:02:25,730
gyda gwerth 7, yna 3 yn y chwith,

42
00:02:25,730 --> 00:02:32,760
yna 9 ar y dde, ac yna 6 ar y dde o'r 3. "

43
00:02:32,760 --> 00:02:34,810
Gawn ni weld os gallaf gofio hynny i gyd yn fy mhen.

44
00:02:34,810 --> 00:02:37,670
Felly, mae hyn yn mynd i fod yn ein gwreiddiau i fyny yma.

45
00:02:37,670 --> 00:02:41,600
Byddwn yn cael rhywfaint o pwyntydd yn rhywle, rhywbeth y byddwn yn galw gwraidd,

46
00:02:41,600 --> 00:02:45,140
ac mae'n pwyntio at y boi.

47
00:02:45,140 --> 00:02:48,490
Nawr i wneud nod newydd,

48
00:02:48,490 --> 00:02:52,870
yr hyn sydd gennym, y 3 ar y chwith?

49
00:02:52,870 --> 00:02:57,140
Felly, nod newydd gyda 3, ac mae'n dechrau pwyntiau null.

50
00:02:57,140 --> 00:02:59,190
'N annhymerus' jyst yn rhoi N.

51
00:02:59,190 --> 00:03:02,250
Nawr rydym am i wneud i hynny fynd i'r chwith o 7.

52
00:03:02,250 --> 00:03:06,840
Felly, rydym yn newid y pwyntydd yn hyn bwyntio at y boi.

53
00:03:06,840 --> 00:03:12,420
Ac rydym yn gwneud yr un peth. Rydym eisiau 9 dros yma

54
00:03:12,420 --> 00:03:14,620
sy'n dechrau yn unig yn dweud null.

55
00:03:14,620 --> 00:03:19,600
Rydym yn mynd i newid y pwyntydd, pwynt i 9,

56
00:03:19,600 --> 00:03:23,310
ac yn awr yr ydym am roi 6 i dde o 3.

57
00:03:23,310 --> 00:03:32,170
Felly, mae'n mynd i - wneud 6.

58
00:03:32,170 --> 00:03:34,310
A bydd y dyn pwyntio yno.

59
00:03:34,310 --> 00:03:38,320
Iawn. Felly dyna i gyd mae'n gofyn i ni ei wneud.

60
00:03:38,320 --> 00:03:42,770
>> Nawr gadewch i ni fynd dros rai termau.

61
00:03:42,770 --> 00:03:46,690
Rydym eisoes yn siarad am sut y mae gwraidd y goeden yn y nod uchaf y rhan fwyaf yn y goeden.

62
00:03:46,690 --> 00:03:54,720
Mae'r un yn cynnwys 7. Mae'r nodau ar waelod y goeden yn cael eu galw y dail.

63
00:03:54,720 --> 00:04:01,240
Unrhyw nod a dim ond wedi null fel ei phlant yn deilen.

64
00:04:01,240 --> 00:04:03,680
Felly mae'n bosibl, os bydd ein coeden ddeuaidd yn unig yw nod sengl,

65
00:04:03,680 --> 00:04:10,130
bod coeden yn deilen, a dyna ni.

66
00:04:10,130 --> 00:04:12,060
"Mae'r 'uchder' y goeden yn y nifer o hopys rhaid i chi wneud

67
00:04:12,060 --> 00:04:16,620
ei gael o'r brig i'r deilen. "

68
00:04:16,620 --> 00:04:18,640
Byddwn yn mynd i mewn, mewn eiliad, y gwahaniaeth

69
00:04:18,640 --> 00:04:21,940
rhwng y coed deuaidd cytbwys ac anghytbwys,

70
00:04:21,940 --> 00:04:29,470
ond ar hyn o bryd, mae'r uchder cyffredinol y goeden

71
00:04:29,470 --> 00:04:34,520
Byddwn yn ei ddweud yw 3, er os ydych yn cyfrif y nifer o hopys

72
00:04:34,520 --> 00:04:39,710
rhaid i chi wneud er mwyn cael i 9, yna mae'n mewn gwirionedd dim ond uchder o 2.

73
00:04:39,710 --> 00:04:43,340
Ar hyn o bryd mae hyn yn goeden ddeuaidd anghytbwys,

74
00:04:43,340 --> 00:04:49,840
ond byddwn yn siarad am cytbwys pan mae'n mynd i fod yn berthnasol.

75
00:04:49,840 --> 00:04:52,040
Felly nawr gallwn ni siarad am nodau mewn coeden o ran

76
00:04:52,040 --> 00:04:54,700
perthynas i'r nodau eraill yn y goeden.

77
00:04:54,700 --> 00:04:59,730
Felly, nawr rydym wedi rhieni, plant, brodyr a chwiorydd, hynafiaid, a disgynyddion.

78
00:04:59,730 --> 00:05:05,650
Maent yn synnwyr cyffredin 'n bert, yr hyn y maent yn ei olygu.

79
00:05:05,650 --> 00:05:09,610
Os byddwn yn gofyn - mae'n rhieni.

80
00:05:09,610 --> 00:05:12,830
Felly beth yw rhiant o 3?

81
00:05:12,830 --> 00:05:16,090
[Myfyrwyr] 7. >> Yeah. Mae'r rhiant yn unig yn mynd i fod pa bwyntiau i chi.

82
00:05:16,090 --> 00:05:20,510
Yna, beth yw'r plant o 7?

83
00:05:20,510 --> 00:05:23,860
[Mae myfyrwyr yn] 3 a 9. >> Yeah.

84
00:05:23,860 --> 00:05:26,460
Noder bod "plant" yn llythrennol yn golygu plant,

85
00:05:26,460 --> 00:05:31,010
felly ni fyddent 6 yn gymwys, am ei fod yn debyg i ŵyr neu wyres.

86
00:05:31,010 --> 00:05:35,540
Ond yna, os ydym yn mynd ddisgynyddion, felly beth yn ddisgynyddion o 7?

87
00:05:35,540 --> 00:05:37,500
[Mae myfyrwyr yn] 3, 6 a 9. >> Yeah.

88
00:05:37,500 --> 00:05:42,330
Mae disgynyddion y nod gwraidd yn mynd i fod popeth yn y goeden,

89
00:05:42,330 --> 00:05:47,950
ac eithrio efallai y nod gwraidd ei hun, os nad ydych am i ystyried y ddisgynnydd.

90
00:05:47,950 --> 00:05:50,750
Ac yn olaf, hynafiaid, felly ei fod yn y cyfeiriad arall.

91
00:05:50,750 --> 00:05:55,740
Felly beth yw'r hynafiaid o 6?

92
00:05:55,740 --> 00:05:58,920
[Mae myfyrwyr yn] 3 a 7. >> Yeah. 9 Nid yn cael ei gynnwys.

93
00:05:58,920 --> 00:06:02,520
Dim ond y cefn llinach uniongyrchol at wraidd

94
00:06:02,520 --> 00:06:13,230
yn mynd i fod eich hynafiaid.

95
00:06:13,230 --> 00:06:16,300
>> "Rydym yn dweud bod coeden ddeuaidd ei 'archebu' os ar gyfer pob nod yn y goeden,

96
00:06:16,300 --> 00:06:19,530
ei holl ddisgynyddion ar y chwith werthoedd llai

97
00:06:19,530 --> 00:06:22,890
a phob un o'r rhai ar y dde yn cael gwerthoedd uwch.

98
00:06:22,890 --> 00:06:27,060
Er enghraifft, y goeden uchod yn cael ei archebu, ond nid yw'r trefniant ond yn bosibl archebu. "

99
00:06:27,060 --> 00:06:30,180
Cyn i ni gyrraedd y sefyllfa honno,

100
00:06:30,180 --> 00:06:36,420
goeden ddeuaidd gorchymyn ei adnabod hefyd fel coeden chwiliad deuaidd.

101
00:06:36,420 --> 00:06:38,660
Yma rydym yn digwydd bod yn galw ei goeden ddeuaidd archebu,

102
00:06:38,660 --> 00:06:41,850
ond dydw i erioed wedi clywed ei alw goeden ddeuaidd archebwyd cyn,

103
00:06:41,850 --> 00:06:46,650
ac ar gwis ydym yn llawer mwy tebygol o roi coeden chwiliad deuaidd.

104
00:06:46,650 --> 00:06:49,250
Maent yn un ac yr un fath,

105
00:06:49,250 --> 00:06:54,580
ac mae'n bwysig eich bod yn cydnabod y gwahaniaeth rhwng y goeden ddeuaidd coed a chwiliad deuaidd.

106
00:06:54,580 --> 00:06:58,830
Mae coeden ddeuaidd yn unig yw coeden sy'n pwyntio at ddau beth.

107
00:06:58,830 --> 00:07:02,120
Mae pob nod yn cyfeirio at ddau beth.

108
00:07:02,120 --> 00:07:06,310
Nid oes rhesymeg am y gwerthoedd y mae'n cyfeirio at.

109
00:07:06,310 --> 00:07:11,370
Felly hoffi dros yma, gan ei fod yn goeden chwiliad deuaidd,

110
00:07:11,370 --> 00:07:14,030
rydym yn gwybod os ydym yn mynd i'r chwith o 7,

111
00:07:14,030 --> 00:07:16,670
yna mae'r holl werthoedd y gallwn o bosibl cyrraedd

112
00:07:16,670 --> 00:07:19,310
drwy fynd i'r chwith o 7 fod yn llai na 7.

113
00:07:19,310 --> 00:07:24,070
Sylwch fod yr holl werth sy'n llai na 7 yn 3 a 6.

114
00:07:24,070 --> 00:07:26,040
Mae'r rheini i gyd i'r chwith o 7.

115
00:07:26,040 --> 00:07:29,020
Os ydym yn mynd i'r dde o'r 7, rhaid i bopeth fod yn fwy na 7,

116
00:07:29,020 --> 00:07:33,220
hynny 9 ar y dde o 7, felly rydym yn dda.

117
00:07:33,220 --> 00:07:36,150
Nid yw hyn yn wir am goeden ddeuaidd,

118
00:07:36,150 --> 00:07:40,020
am goeden ddeuaidd rheolaidd y gallwn dim ond wedi 3 ar y brig, 7 ar y chwith,

119
00:07:40,020 --> 00:07:47,630
9 i'r chwith o 7; does dim archebu o werthoedd o gwbl.

120
00:07:47,630 --> 00:07:56,140
Yn awr, ni fyddwn mewn gwirionedd yn gwneud hyn oherwydd ei fod yn ddiflas ac yn ddiangen,

121
00:07:56,140 --> 00:07:59,400
ond "ceisio tynnu coed archebu cymaint ag y gallwch chi feddwl am

122
00:07:59,400 --> 00:08:01,900
ddefnyddio y 7 rhifau, 3, 9, a 6.

123
00:08:01,900 --> 00:08:06,800
Faint o drefniadau gwahanol sydd ar gael? Beth yw uchder pob un? "

124
00:08:06,800 --> 00:08:10,480
>> Byddwn yn gwneud cwpl, ond y prif syniad yw,

125
00:08:10,480 --> 00:08:16,530
hyn mewn unrhyw ffordd yn ddarlun unigryw o goeden ddeuaidd sy'n cynnwys y gwerthoedd hyn.

126
00:08:16,530 --> 00:08:22,760
Y cyfan sydd ei angen yw rhywfaint o goeden ddeuaidd sy'n cynnwys 7, 3, 6, a 9.

127
00:08:22,760 --> 00:08:25,960
Byddai un arall dilys posibl fyddai y gwraidd yw 3,

128
00:08:25,960 --> 00:08:30,260
ewch i'r chwith ac mae'n 6, ewch i'r chwith ac mae'n 7,

129
00:08:30,260 --> 00:08:32,730
ewch i'r chwith ac mae'n 9.

130
00:08:32,730 --> 00:08:36,169
Mae hynny'n goeden ddeuol berffaith ddilys chwilio.

131
00:08:36,169 --> 00:08:39,570
Dyw hi ddim yn ddefnyddiol iawn, am ei fod yn union fel rhestr cysylltiedig

132
00:08:39,570 --> 00:08:43,750
a phob un o'r pwyntiau yn unig null.

133
00:08:43,750 --> 00:08:48,900
Ond mae'n goeden dilys. Yeah?

134
00:08:48,900 --> 00:08:51,310
[Myfyrwyr] Peidiwch â gwerthoedd rhaid i fod yn fwy ar y dde?

135
00:08:51,310 --> 00:08:56,700
Neu a yw hyn -? Mae'r rhain yn >> wyf i fod i fynd y ffordd arall.

136
00:08:56,700 --> 00:09:00,960
Mae hefyd - ie, gadewch i ni newid hynny.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Helfa dda.

138
00:09:07,770 --> 00:09:11,730
Mae dal i ufuddhau beth yw deuaidd chwilio coeden i fod i'w wneud.

139
00:09:11,730 --> 00:09:15,650
Felly popeth ar y chwith wedi i fod yn llai nag unrhyw nod penodol.

140
00:09:15,650 --> 00:09:23,180
Gallai Rydym yn unig yn symud, dyweder, hyn 6 a'i roi yma.

141
00:09:23,180 --> 00:09:26,880
Na, ni allwn. Pam ydw i'n barhau i wneud hynny?

142
00:09:26,880 --> 00:09:35,350
Gadewch i ni wneud - dyma yw 6, dyma yw 7, 6 pwynt i 3.

143
00:09:35,350 --> 00:09:39,290
Mae hyn yn dal i fod yn goeden ddeuaidd chwilio dilys.

144
00:09:39,290 --> 00:09:49,260
Beth sydd o'i le os byddaf yn - gadewch i ni weld os gallaf ddod o hyd i drefniant.

145
00:09:49,260 --> 00:09:52,280
Yeah, iawn. Felly beth sydd o'i le ar y goeden?

146
00:09:52,280 --> 00:10:08,920
Amcana i wedi roi ichi yn barod awgrym bod rhywbeth o'i le ag ef.

147
00:10:08,920 --> 00:10:14,430
Pam ydw i'n barhau i wneud hynny?

148
00:10:14,430 --> 00:10:18,510
Iawn. Mae hyn yn edrych yn rhesymol.

149
00:10:18,510 --> 00:10:22,590
Os ydym yn edrych ar bob nod, fel 7, yna i'r chwith o 7 yn 3.

150
00:10:22,590 --> 00:10:24,960
Felly mae gennym 3, y peth i'r dde o 3 o 6.

151
00:10:24,960 --> 00:10:27,750
Ac os ydych yn edrych yn 6, y peth i'r dde o 6 yn 9.

152
00:10:27,750 --> 00:10:30,910
Felly pam nad yw hyn yn goeden ddeuaidd chwilio ddilys?

153
00:10:30,910 --> 00:10:36,330
[Mae myfyrwyr yn] 9 yn dal ar y chwith o 7. >> Yeah.

154
00:10:36,330 --> 00:10:43,710
Rhaid iddo fod yn wir bod yr holl werthoedd y gallwch o bosibl cyrraedd trwy fynd i'r chwith o 7 yn llai na 7.

155
00:10:43,710 --> 00:10:49,120
Os ydym yn mynd i'r chwith o 7, rydym yn cael i 3 a gallwn yn dal i gael i 6,

156
00:10:49,120 --> 00:10:52,520
gallwn dal i gael i 9, ond drwy gael mynd yn llai na 7,

157
00:10:52,520 --> 00:10:55,070
Ni ddylem fod yn gallu cyrraedd nifer sy'n fwy na 7.

158
00:10:55,070 --> 00:10:59,830
Felly, nid yw hyn yn goeden ddeuaidd chwilio dilys.

159
00:10:59,830 --> 00:11:02,330
>> Mae fy mrawd mewn gwirionedd yn cael cwestiwn cyfweliad

160
00:11:02,330 --> 00:11:07,760
a oedd yn y bôn hyn, dim ond cod o hyd i rywbeth i ddilysu

161
00:11:07,760 --> 00:11:10,500
a yw coeden yn goeden chwiliad deuaidd,

162
00:11:10,500 --> 00:11:13,580
ac felly y peth cyntaf a wnaeth oedd dim ond edrych i weld

163
00:11:13,580 --> 00:11:17,020
os y chwith a dde yn gywir, ac yna ailadrodd lawr yno.

164
00:11:17,020 --> 00:11:19,700
Ond nid ydych yn gallu gwneud hynny; rhaid i chi gadw golwg

165
00:11:19,700 --> 00:11:22,550
y ffaith bod yn awr fy mod i wedi mynd i'r chwith o'r 7,

166
00:11:22,550 --> 00:11:26,340
mae'n rhaid i bopeth yn y Terfynau Chwilio yn llai na 7.

167
00:11:26,340 --> 00:11:28,430
Mae algorithm cywir angen i gadw golwg

168
00:11:28,430 --> 00:11:35,970
o'r terfynau y gall y gwerthoedd o bosibl syrthio i mewn

169
00:11:35,970 --> 00:11:38,360
Ni fyddwn yn mynd drwy bob un ohonynt.

170
00:11:38,360 --> 00:11:41,630
Mae yna berthynas gylchol braf,

171
00:11:41,630 --> 00:11:44,810
er nad ydym wedi gotten i rheini, neu ni fyddwn yn mynd i'r rheini,

172
00:11:44,810 --> 00:11:47,030
diffinio faint ohonynt mewn gwirionedd.

173
00:11:47,030 --> 00:11:53,180
Felly mae 14 ohonynt.

174
00:11:53,180 --> 00:11:56,020
Mae'r syniad o sut y byddech yn ei wneud fathemategol yn debyg,

175
00:11:56,020 --> 00:11:59,770
gallwch ddewis unrhyw un sengl i fod yn nod gwraidd,

176
00:11:59,770 --> 00:12:03,160
ac yna, os wyf yn dewis 7 i fod yn nod gwraidd,

177
00:12:03,160 --> 00:12:08,150
yna mae, dyweder, rhai rhifau a all fynd yn fy nod chwith,

178
00:12:08,150 --> 00:12:10,440
ac mae rhai rhifau a all fod yn fy nod iawn,

179
00:12:10,440 --> 00:12:15,090
ond os wyf wedi n cyfanswm, yna bydd y swm y gellir mynd i'r chwith

180
00:12:15,090 --> 00:12:18,820
yn ogystal â'r swm y gellir mynd i'r dde yn n - 1.

181
00:12:18,820 --> 00:12:26,130
Felly, y niferoedd sy'n weddill, rhaid iddynt fod yn gallu mynd naill ai i'r chwith neu'r dde.

182
00:12:26,130 --> 00:12:31,580
Mae'n ymddangos yn anodd, os wyf yn rhoi 3 gyntaf, yna rhaid i bopeth fynd i'r chwith,

183
00:12:31,580 --> 00:12:35,080
ond os wyf yn rhoi 7, yna gall rhai pethau fynd i'r chwith a gall y rhai pethau yn mynd i'r dde.

184
00:12:35,080 --> 00:12:39,570
A thrwy '3 'cyntaf i mi yn golygu y gall popeth yn mynd i'r dde.

185
00:12:39,570 --> 00:12:42,350
Mae'n wir, os oes gen ti i feddwl am y peth fel,

186
00:12:42,350 --> 00:12:47,980
sut y gall llawer o bethau yn mynd ar y lefel nesaf y goeden.

187
00:12:47,980 --> 00:12:50,420
Ac mae'n dod allan i fod yn 14 oed; neu gallwch dynnu pob un ohonynt,

188
00:12:50,420 --> 00:12:54,650
ac yna byddwch yn cael 14.

189
00:12:54,650 --> 00:13:01,120
>> Mynd yn ôl yma,

190
00:13:01,120 --> 00:13:03,510
"Gorchmynnwyd coed deuaidd yn oer oherwydd gallwn chwilio drwyddynt

191
00:13:03,510 --> 00:13:06,910
mewn ffordd debyg iawn i chwilio dros amrywiaeth datrys.

192
00:13:06,910 --> 00:13:10,120
I wneud hynny, rydym yn dechrau wrth wraidd ac yn gweithio ein ffordd i lawr y goeden

193
00:13:10,120 --> 00:13:13,440
tuag at ddail, gwirio gwerthoedd pob nod yn erbyn y gwerthoedd rydym yn chwilio am.

194
00:13:13,440 --> 00:13:15,810
Os werth y nod ar hyn o bryd yn llai na gwerth yr ydym yn chwilio amdano,

195
00:13:15,810 --> 00:13:18,050
byddwch yn mynd nesaf at blentyn y nod yn iawn.

196
00:13:18,050 --> 00:13:20,030
Fel arall, byddwch yn mynd i blentyn y nod o chwith.

197
00:13:20,030 --> 00:13:22,800
Ar ryw bwynt, byddwch naill ai yn dod o hyd i'r gwerth rydych chi'n chwilio amdano, neu byddwch yn rhedeg i mewn null,

198
00:13:22,800 --> 00:13:28,520
Nid yw dangos y gwerth sydd yn y goeden. "

199
00:13:28,520 --> 00:13:32,450
Rhaid i mi ail-lunio'r goeden oedd gennym o'r blaen; bydd yn cymryd eiliad.

200
00:13:32,450 --> 00:13:38,280
Ond rydym am edrych i fyny a 6, 10, ac 1 yn y goeden.

201
00:13:38,280 --> 00:13:49,180
Felly, beth oedd yno, 7, 9, 3, 6. Iawn.

202
00:13:49,180 --> 00:13:52,730
Mae'r niferoedd ydych am edrych i fyny, rydym yn awyddus i edrych i fyny 6.

203
00:13:52,730 --> 00:13:55,440
Sut mae hyn yn gweithio algorithm?

204
00:13:55,440 --> 00:14:03,040
Wel, mae gennym hefyd rai pwyntydd wraidd i'n goeden.

205
00:14:03,040 --> 00:14:12,460
Ac byddem yn mynd at wraidd a dweud, mae hyn yn gyfwerth â gwerth rydym yn chwilio amdano?

206
00:14:12,460 --> 00:14:15,000
Felly, rydym yn chwilio am 6, felly nid yw'n gyfartal.

207
00:14:15,000 --> 00:14:20,140
Felly, rydym yn dal i fynd, ac yn awr rydym yn dweud, iawn, felly 6 yn llai na 7.

208
00:14:20,140 --> 00:14:23,940
Ydy hynny'n golygu ein bod am fynd i'r chwith, neu a ydym am fynd i'r dde?

209
00:14:23,940 --> 00:14:27,340
[Myfyrwyr] Chwith. >> Yeah.

210
00:14:27,340 --> 00:14:33,340
Mae'n llawer haws, y cyfan mae'n rhaid i chi ei wneud yw tynnu un nod bosibl y goeden

211
00:14:33,340 --> 00:14:37,760
ac yna i chi peidiwch - yn hytrach na cheisio meddwl yn eich pen,

212
00:14:37,760 --> 00:14:40,020
iawn, os yw'n llai, ydw i'n mynd ar y chwith neu ewch i'r dde,

213
00:14:40,020 --> 00:14:43,030
dim ond yn edrych ar y darlun hwn, mae'n glir iawn bod rhaid i mi fynd i'r chwith

214
00:14:43,030 --> 00:14:47,700
os yw hyn nod yn fwy na'r gwerth a Im 'yn chwilio amdano.

215
00:14:47,700 --> 00:14:52,600
Felly, byddwch yn mynd i'r chwith, nawr rwy'n yn 3.

216
00:14:52,600 --> 00:14:57,770
Rwyf am - 3 yn llai na'r gwerth rwy'n chwilio amdano, sef 6.

217
00:14:57,770 --> 00:15:03,420
Felly, rydym yn mynd i'r dde, ac yn awr yr wyf yn y pen draw yn 6,

218
00:15:03,420 --> 00:15:07,380
sef y gwerth rwy'n chwilio amdano, felly yr wyf yn dychwelyd yn wir.

219
00:15:07,380 --> 00:15:15,760
Mae gwerth nesaf rwy'n mynd i chwilio amdano yw 10.

220
00:15:15,760 --> 00:15:23,230
Iawn. Felly 10, yn awr, yn mynd i - torri i ffwrdd hynny - yn mynd i ddilyn y gwraidd.

221
00:15:23,230 --> 00:15:27,670
Yn awr, 10 yn mynd i fod yn fwy na 7, felly yr wyf am edrych ar y dde.

222
00:15:27,670 --> 00:15:31,660
Rydw i'n mynd i ddod draw yma, mae 10 yn mynd i fod yn fwy na 9,

223
00:15:31,660 --> 00:15:34,520
felly dwi'n mynd i eisiau edrych ar y dde.

224
00:15:34,520 --> 00:15:42,100
Rwy'n dod draw yma, ond dros yma nawr rwy'n yn null.

225
00:15:42,100 --> 00:15:44,170
Beth ddylwn i ei wneud os byddaf yn taro null?

226
00:15:44,170 --> 00:15:47,440
[Myfyrwyr] Dychwelyd ffug? >> Yeah. Doeddwn i ddim yn dod o hyd i 10.

227
00:15:47,440 --> 00:15:49,800
1 yn mynd i fod yn achos bron yn union yr un fath,

228
00:15:49,800 --> 00:15:51,950
ac eithrio mai dim ond yn mynd i gael eu flipped; yn hytrach nag edrych

229
00:15:51,950 --> 00:15:56,540
i lawr yr ochr dde, dw i'n mynd i edrych i lawr yr ochr chwith.

230
00:15:56,540 --> 00:16:00,430
>> Nawr Rwy'n credu ein bod mewn gwirionedd yn cael i cod.

231
00:16:00,430 --> 00:16:04,070
Dyma lle - agor i fyny 'r offer CS50 a llywio eich ffordd yno,

232
00:16:04,070 --> 00:16:07,010
ond gall dim ond i chi hefyd wneud yn y gofod.

233
00:16:07,010 --> 00:16:09,170
Mae'n debyg ddelfrydol i wneud hynny yn y gofod,

234
00:16:09,170 --> 00:16:13,760
oherwydd fe allwn ni weithio yn y gofod.

235
00:16:13,760 --> 00:16:19,170
"Yn gyntaf byddwn angen diffiniad math newydd ar gyfer nod goeden ddeuol sy'n cynnwys gwerthoedd int.

236
00:16:19,170 --> 00:16:21,400
Gan ddefnyddio'r boilerplate typedef isod,

237
00:16:21,400 --> 00:16:24,510
creu diffiniad math newydd ar gyfer nod mewn coeden deuaidd.

238
00:16:24,510 --> 00:16:27,930
Os ewch i drafferthion. . . "Blah, blah, blah. Iawn.

239
00:16:27,930 --> 00:16:30,380
Felly, gadewch i ni roi'r boilerplate yma,

240
00:16:30,380 --> 00:16:41,630
nod strwythur typedef, a nod. Yeah, iawn.

241
00:16:41,630 --> 00:16:44,270
Felly beth yw'r meysydd rydym yn mynd i eisiau yn ein nod?

242
00:16:44,270 --> 00:16:46,520
[Myfyrwyr] Int ac yna dau awgrymiadau?

243
00:16:46,520 --> 00:16:49,700
>> Int werth, dau awgrymiadau? Sut ydw i'n ysgrifennu'r awgrymiadau?

244
00:16:49,700 --> 00:16:58,440
[Myfyrwyr] strwythur. >> Dylwn chwyddo i mewn Yeah, felly strwythur nod * chwith,

245
00:16:58,440 --> 00:17:01,320
a strwythur nod * dde.

246
00:17:01,320 --> 00:17:03,460
A chofiwch y drafodaeth o'r tro diwethaf,

247
00:17:03,460 --> 00:17:15,290
bod hyn yn gwneud unrhyw synnwyr, mae hyn yn gwneud unrhyw synnwyr,

248
00:17:15,290 --> 00:17:18,270
mae hyn yn gwneud unrhyw synnwyr.

249
00:17:18,270 --> 00:17:25,000
Mae angen popeth yno er mwyn diffinio y strwythur ailadroddus.

250
00:17:25,000 --> 00:17:27,970
Iawn, felly dyna beth mae ein coeden yn mynd i edrych fel.

251
00:17:27,970 --> 00:17:37,670
Pe baem yn gwneud coeden trinary, yna gallai nod yn edrych fel, b2 b1, strwythur nod * b3,

252
00:17:37,670 --> 00:17:43,470
lle b yn gangen - mewn gwirionedd, yr wyf wedi clywed mwy gadael iddo, canol, i'r dde, ond beth bynnag.

253
00:17:43,470 --> 00:17:55,610
Byddwn ond yn gofalu am deuaidd, felly dde, i'r chwith.

254
00:17:55,610 --> 00:17:59,110
"Nawr datgan newidyn nod * byd-eang am wraidd y goeden."

255
00:17:59,110 --> 00:18:01,510
Felly nid ydym yn mynd i wneud hynny.

256
00:18:01,510 --> 00:18:08,950
Er mwyn gwneud pethau ychydig yn fwy anodd ac yn fwy cyffredinol,

257
00:18:08,950 --> 00:18:11,570
ni fydd gennym newidyn nod byd-eang.

258
00:18:11,570 --> 00:18:16,710
Yn lle hynny, yn y brif byddwn yn datgan ein holl bethau nod,

259
00:18:16,710 --> 00:18:20,500
ac mae hynny'n golygu bod isod, pan fyddwn yn dechrau rhedeg

260
00:18:20,500 --> 00:18:23,130
Yn cynnwys ein swyddogaeth a'n swyddogaeth rhowch yn ei le,

261
00:18:23,130 --> 00:18:27,410
yn hytrach na o'n Yn cynnwys swyddogaeth ddefnyddio dim ond y newidyn nod byd-eang,

262
00:18:27,410 --> 00:18:34,280
rydym yn mynd i gael ei gymryd fel dadl y goeden yr ydym am i brosesu.

263
00:18:34,280 --> 00:18:36,650
Mae cael y newidyn byd-eang oedd i fod i wneud pethau'n haws.

264
00:18:36,650 --> 00:18:42,310
Rydym yn mynd i wneud pethau'n anoddach.

265
00:18:42,310 --> 00:18:51,210
Nawr gymryd munud neu ddau i ddim ond gwneud y math hwn o beth,

266
00:18:51,210 --> 00:18:57,690
lle y tu mewn o brif ydych am greu y goeden hon, a dyna i gyd rydych am ei wneud.

267
00:18:57,690 --> 00:19:04,530
Ceisiwch ac adeiladu y goeden hon yn eich prif swyddogaeth.

268
00:19:42,760 --> 00:19:47,610
>> Iawn. Felly, nid oes hyd yn oed yn rhaid i wedi adeiladu y goeden y ffordd gyfan eto.

269
00:19:47,610 --> 00:19:49,840
Ond mae unrhyw un gael rhywbeth y gallwn dynnu i fyny

270
00:19:49,840 --> 00:20:03,130
i ddangos sut y gallai un ddechrau adeiladu o'r fath goeden?

271
00:20:03,130 --> 00:20:08,080
[Myfyrwyr] guro rhywun, yn ceisio mynd allan.

272
00:20:08,080 --> 00:20:13,100
[Bowden] unrhyw un gyfforddus gyda'u adeiladu coeden?

273
00:20:13,100 --> 00:20:15,520
[Myfyrwyr] Cadarn. Dyw hi ddim yn ei wneud. >> Mae'n iawn. Gallwn orffen -

274
00:20:15,520 --> 00:20:26,860
oh, allwch chi ei gadw? Hwre.

275
00:20:26,860 --> 00:20:32,020
Felly dyma gennym - oh, rwy'n ychydig yn torri i ffwrdd.

276
00:20:32,020 --> 00:20:34,770
Ydw i'n chwyddo i mewn?

277
00:20:34,770 --> 00:20:37,730
Chwyddo i mewn, sgrolio allan. >> Mae gen i gwestiwn. >> Yeah?

278
00:20:37,730 --> 00:20:44,410
[Myfyrwyr] Pan fyddwch yn diffinio strwythur, yw pethau fel ymgychwyn i unrhyw beth?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Rhif >> Iawn. Felly, byddai'n rhaid i chi ymgychwyn -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Rhif Pan fyddwch yn diffinio, neu pan fyddwch yn datgan strwythur,

281
00:20:50,450 --> 00:20:55,600
nad yw'n cael ei ymgychwyn yn rhagosodedig; mae'n union fel os ydych yn datgan int.

282
00:20:55,600 --> 00:20:59,020
Mae'n union yr un peth. Mae fel pob un o'i meysydd unigol

283
00:20:59,020 --> 00:21:04,460
yn gallu cael gwerth garbage ynddo. >> A yw'n bosibl diffinio - neu i ddatgan strwythur

284
00:21:04,460 --> 00:21:07,740
mewn ffordd a wna ymgychwyn nhw?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Ydw. Felly, cystrawen shortcut initialization

286
00:21:13,200 --> 00:21:18,660
yn mynd i edrych fel -

287
00:21:18,660 --> 00:21:22,200
Mae dwy ffordd y gallwn wneud hyn. Rwy'n meddwl y dylem lunio ei

288
00:21:22,200 --> 00:21:25,840
i wneud yn siwr Clang hefyd yn gwneud hyn.

289
00:21:25,840 --> 00:21:28,510
Mae'r gorchymyn o ddadleuon sy'n dod i mewn i'r strwythur,

290
00:21:28,510 --> 00:21:32,170
i chi roi fel trefn y dadleuon y tu mewn o'r rhain braces cyrliog.

291
00:21:32,170 --> 00:21:35,690
Felly, os ydych am i ymgychwyn i 9 a gadawodd ei null ac yna i'r dde yn null,

292
00:21:35,690 --> 00:21:41,570
byddai'n 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Y dewis arall yw, ac nid y golygydd ddim yn hoffi y gystrawen,

294
00:21:47,890 --> 00:21:50,300
ac mae'n credu yr wyf am gael bloc newydd,

295
00:21:50,300 --> 00:22:01,800
ond y dewis arall yw rhywbeth fel -

296
00:22:01,800 --> 00:22:04,190
yma, byddaf yn ei roi ar linell newydd.

297
00:22:04,190 --> 00:22:09,140
Gallwch ddweud yn benodol, yr wyf yn anghofio y gystrawen union.

298
00:22:09,140 --> 00:22:13,110
Felly, gallwch chi fynd i'r afael yn benodol drwy eu henwi, a dweud,

299
00:22:13,110 --> 00:22:21,570
. C, neu. Werth = 9,. NULL = chwith.

300
00:22:21,570 --> 00:22:24,540
Rwy'n dyfalu angen i'r rhain fod atalnodau.

301
00:22:24,540 --> 00:22:29,110
. I'r dde = NULL, felly mae hyn yn ffordd nad ydych yn ei wneud

302
00:22:29,110 --> 00:22:33,780
mewn gwirionedd mae angen i chi wybod y drefn y strwythur,

303
00:22:33,780 --> 00:22:36,650
a phan fyddwch chi'n darllen hwn, mae'n llawer mwy penodol

304
00:22:36,650 --> 00:22:41,920
am yr hyn y gwerth sy'n cael ei ymgychwyn i.

305
00:22:41,920 --> 00:22:44,080
>> Mae hyn yn digwydd i fod yn un o'r pethau hynny -

306
00:22:44,080 --> 00:22:49,100
felly, ar gyfer y rhan fwyaf, C + + yn uwchset o C.

307
00:22:49,100 --> 00:22:54,160
Gallwch gymryd C cod, symud drosodd i C + +, a dylai lunio.

308
00:22:54,160 --> 00:22:59,570
Mae hwn yn un o'r pethau y C + + Nid yw'n cefnogi, felly mae pobl yn tueddu i beidio â gwneud hynny.

309
00:22:59,570 --> 00:23:01,850
Nid wyf yn gwybod os dyna'r unig reswm mae pobl yn tueddu i beidio â gwneud hynny,

310
00:23:01,850 --> 00:23:10,540
ond yr achos lle roedd angen i mi ei ddefnyddio hangen i weithio gyda C + +, ac felly ni allwn ddefnyddio hyn.

311
00:23:10,540 --> 00:23:14,000
Nid yw enghraifft arall o rywbeth yw hynny'n gweithio gyda C + + yn

312
00:23:14,000 --> 00:23:16,940
sut malloc yn dychwelyd "* ddi-rym," dechnegol,

313
00:23:16,940 --> 00:23:20,200
ond gallech ddweud torgoch * x beth bynnag malloc =,

314
00:23:20,200 --> 00:23:22,840
a bydd yn awtomatig yn cael ei bwrw i * torgoch.

315
00:23:22,840 --> 00:23:25,450
Nid yw cast awtomatig yn digwydd mewn C + +.

316
00:23:25,450 --> 00:23:28,150
Ni fyddai hynny'n lunio, a byddech yn benodol rhaid i chi ddweud

317
00:23:28,150 --> 00:23:34,510
* torgoch, malloc, beth bynnag, i fwrw ef i * torgoch.

318
00:23:34,510 --> 00:23:37,270
Nid oes llawer o bethau y C a C + + yn anghytuno ar,

319
00:23:37,270 --> 00:23:40,620
ond y rhai yn ddau.

320
00:23:40,620 --> 00:23:43,120
Felly, byddwn yn mynd â'r chystrawen.

321
00:23:43,120 --> 00:23:46,150
Ond hyd yn oed os nad ydym yn mynd â'r cystrawen,

322
00:23:46,150 --> 00:23:49,470
beth yw - a allai fod o'i le ar hyn?

323
00:23:49,470 --> 00:23:52,170
[Myfyrwyr] Nid oes angen i mi ei dereference? >> Yeah.

324
00:23:52,170 --> 00:23:55,110
Cofiwch bod y saeth yn cael dereference ymhlyg,

325
00:23:55,110 --> 00:23:58,230
ac felly pan fyddwn yn unig yn delio â strwythur,

326
00:23:58,230 --> 00:24:04,300
ydym am eu defnyddio. i gyrraedd y tu mewn maes y strwythur.

327
00:24:04,300 --> 00:24:07,200
Ac mae'r amser yn unig yr ydym yn defnyddio saeth yw pan fyddwn am ei wneud -

328
00:24:07,200 --> 00:24:13,450
yn dda, saeth yn cyfateb i -

329
00:24:13,450 --> 00:24:17,020
dyna beth y byddai wedi golygu os byddaf yn defnyddio saeth.

330
00:24:17,020 --> 00:24:24,600
Pob dull saeth yn, dereference hyn, nawr rwy'n mewn strwythur, a gallaf gael y maes.

331
00:24:24,600 --> 00:24:28,040
Naill ai cael y cae yn uniongyrchol neu dereference a chael y maes -

332
00:24:28,040 --> 00:24:30,380
Amcana dylai hyn fod yn werth.

333
00:24:30,380 --> 00:24:33,910
Ond dyma rwy'n delio gyda dim ond nid strwythur, pwyntydd i strwythur,

334
00:24:33,910 --> 00:24:38,780
ac felly ni allaf ddefnyddio'r saeth.

335
00:24:38,780 --> 00:24:47,510
Ond y math hwn o beth y gallwn ei wneud ar gyfer yr holl nodau.

336
00:24:47,510 --> 00:24:55,790
O fy Nuw.

337
00:24:55,790 --> 00:25:09,540
Mae hyn yn 6, 7, a 3.

338
00:25:09,540 --> 00:25:16,470
Yna, gallwn sefydlu canghennau yn ein coeden, gallwn gael 7 -

339
00:25:16,470 --> 00:25:21,650
gallwn gael, ei chwith dylai pwynt i 3.

340
00:25:21,650 --> 00:25:25,130
Felly, sut ydyn ni'n gwneud hynny?

341
00:25:25,130 --> 00:25:29,320
[Myfyrwyr, annealladwy] >> Yeah. Mae'r cyfeiriad node3,

342
00:25:29,320 --> 00:25:34,170
ac os nad oedd gennych gyfeiriad, yna ni fyddai dim ond llunio.

343
00:25:34,170 --> 00:25:38,190
Ond cofiwch bod y rhain yn awgrymiadau ar gyfer nodau nesaf.

344
00:25:38,190 --> 00:25:44,930
Dylai'r hawl gyfeirio at 9,

345
00:25:44,930 --> 00:25:53,330
a 3 Dylai bwyntio ar yr hawl i 6.

346
00:25:53,330 --> 00:25:58,480
Rwy'n credu bod hyn i gyd yn set. Unrhyw sylwadau neu gwestiynau?

347
00:25:58,480 --> 00:26:02,060
[Myfyrwyr, annealladwy] Mae'r gwreiddyn yn mynd i fod yn 7.

348
00:26:02,060 --> 00:26:08,210
Gallwn ddweud nod * ptr =

349
00:26:08,210 --> 00:26:14,160
neu wreiddyn, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> At ein dibenion ni, rydym yn mynd i fod yn delio gyda mewnosodiad,

351
00:26:20,730 --> 00:26:25,490
felly rydym yn mynd i eisiau i ysgrifennu swyddogaeth i fewnosod i mewn i'r goeden ddeuaidd

352
00:26:25,490 --> 00:26:34,230
a rhowch yn ei le yn anochel yn mynd i alw malloc i greu nod newydd ar gyfer y goeden.

353
00:26:34,230 --> 00:26:36,590
Felly mae pethau yn mynd i gael anniben â'r ffaith bod rhai nodau

354
00:26:36,590 --> 00:26:38,590
Ar hyn o bryd ar y simnai

355
00:26:38,590 --> 00:26:43,680
a nodau eraill yn mynd i roi diwedd ar i fyny ar y domen pan fyddwn yn mewnosod nhw.

356
00:26:43,680 --> 00:26:47,640
Mae hyn yn berffaith ddilys, ond yr unig reswm

357
00:26:47,640 --> 00:26:49,600
rydym yn gallu gwneud hyn ar y simnai

358
00:26:49,600 --> 00:26:51,840
oherwydd ei fod yn enghraifft mor ddyfeisgar ein bod yn gwybod

359
00:26:51,840 --> 00:26:56,360
y goeden i fod i gael ei hadeiladu fel 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Os nad oedd gennym hyn, yna ni fyddai rhaid i ni malloc yn y lle cyntaf.

361
00:27:02,970 --> 00:27:06,160
Fel byddwn yn gweld ychydig yn ddiweddarach, dylem fod yn malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Ar hyn o bryd mae'n hollol resymol i'w roi ar y corn,

363
00:27:08,570 --> 00:27:14,750
ond gadewch i ni newid hyn i weithredu malloc.

364
00:27:14,750 --> 00:27:17,160
Felly mae gan bob un o'r rhain yn awr yn mynd i fod yn rhywbeth fel

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

366
00:27:24,240 --> 00:27:28,040
Ac yn awr rydym yn mynd i gael i wneud ein siec.

367
00:27:28,040 --> 00:27:34,010
os (node9 == NULL) - doeddwn i ddim eisiau hynny -

368
00:27:34,010 --> 00:27:40,950
dychwelyd 1, ac yna gallwn wneud node9-> oherwydd erbyn hyn mae'n pwyntydd,

369
00:27:40,950 --> 00:27:45,300
gwerth = 6, node9-> adael = NULL,

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

371
00:27:48,930 --> 00:27:51,410
ac rydym yn mynd i gael i wneud hynny ar gyfer pob un o'r nodau.

372
00:27:51,410 --> 00:27:57,490
Felly, yn lle hynny, gadewch i ni roi y tu mewn swyddogaeth ar wahân.

373
00:27:57,490 --> 00:28:00,620
Gadewch i ni ei alw nod * build_node,

374
00:28:00,620 --> 00:28:09,050
ac mae hyn yn weddol debyg i APIs rydym yn darparu ar gyfer codio Huffman.

375
00:28:09,050 --> 00:28:12,730
Rydym yn rhoi i chi swyddogaethau initializer i goeden

376
00:28:12,730 --> 00:28:20,520
a deconstructor "swyddogaethau" ar gyfer y coed a'r un fath ar gyfer coedwigoedd.

377
00:28:20,520 --> 00:28:22,570
>> Felly dyma ni yn mynd i gael swyddogaeth initializer

378
00:28:22,570 --> 00:28:25,170
i ddim ond adeiladu nod i ni.

379
00:28:25,170 --> 00:28:29,320
Ac mae'n mynd i edrych yn bert lawer yn union fel hyn.

380
00:28:29,320 --> 00:28:32,230
Ac yr wyf ddim hyd yn oed yn mynd i fod yn ddiog ac nid newid enw'r newidyn,

381
00:28:32,230 --> 00:28:34,380
er node9 yn gwneud unrhyw synnwyr anymore.

382
00:28:34,380 --> 00:28:38,610
O, rwy'n dyfalu node9 yn werth ddylai fod wedi bod yn 6.

383
00:28:38,610 --> 00:28:42,800
Nawr gallwn ddychwelyd node9.

384
00:28:42,800 --> 00:28:49,550
Ac yma y dylem ddychwelyd null.

385
00:28:49,550 --> 00:28:52,690
Mae pawb yn cytuno ar y swyddogaeth adeiladu-a-nod?

386
00:28:52,690 --> 00:28:59,780
Felly, yn awr yn gallu rydym yn unig alw hynny i adeiladu unrhyw nod gyda gwerth a roddir ac awgrymiadau null.

387
00:28:59,780 --> 00:29:09,750
Nawr gallwn alw hynny, gallwn wneud nod * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
A gadewch i ni ei wneud. . .

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

390
00:29:33,980 --> 00:29:39,330
Ac yn awr rydym am i sefydlu'r awgrymiadau un,

391
00:29:39,330 --> 00:29:42,470
ac eithrio nawr mae popeth sydd eisoes o ran arwyddion

392
00:29:42,470 --> 00:29:48,480
felly nid oes angen y cyfeiriad.

393
00:29:48,480 --> 00:29:56,300
Iawn. Felly beth yw'r peth olaf yr wyf am ei wneud?

394
00:29:56,300 --> 00:30:03,850
Mae gwall-gwirio nad wyf i'n gwneud.

395
00:30:03,850 --> 00:30:06,800
Beth yw adeiladu dychwelyd nod?

396
00:30:06,800 --> 00:30:11,660
[Myfyrwyr, annealladwy] >> Yeah. Os malloc methu, bydd yn dychwelyd null.

397
00:30:11,660 --> 00:30:16,460
Felly, yr wyf i'n mynd i lazily roi i lawr yma yn hytrach na gwneud yn amod ar gyfer pob un.

398
00:30:16,460 --> 00:30:22,320
Os (node9 == NULL, neu - hyd yn oed yn symlach,

399
00:30:22,320 --> 00:30:28,020
mae hyn yn gyfwerth â dim ond os nad node9.

400
00:30:28,020 --> 00:30:38,310
Felly, os nad node9, neu beidio node6, neu beidio node3, neu beidio node7, yn dychwelyd 1.

401
00:30:38,310 --> 00:30:42,850
Efallai y dylem argraffu methu malloc, neu rywbeth.

402
00:30:42,850 --> 00:30:46,680
[Myfyrwyr] A yw ffug cyfartal i null hefyd?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Unrhyw gwerth sero yn ffug.

404
00:30:51,290 --> 00:30:53,920
Felly null yn werth sero.

405
00:30:53,920 --> 00:30:56,780
Zero yn werth sero. Ffug yn werth sero.

406
00:30:56,780 --> 00:31:02,130
Bydd unrhyw - 'n bert lawer yr 2 yn unig gwerthoedd sero yn null a sero,

407
00:31:02,130 --> 00:31:07,900
ffug yn unig hash a ddiffinnir fel sero.

408
00:31:07,900 --> 00:31:13,030
Mae hynny hefyd yn berthnasol os ydym yn datgan amrywiol byd-eang.

409
00:31:13,030 --> 00:31:17,890
Os oedd gennym wraidd * nod yma,

410
00:31:17,890 --> 00:31:24,150
yna - y peth braf am newidynnau byd-eang yw eu bod bob amser yn cael gwerth cychwynnol.

411
00:31:24,150 --> 00:31:27,500
Nid yw hynny'n wir am swyddogaethau, sut tu mewn yma,

412
00:31:27,500 --> 00:31:34,870
os ydym yn cael, fel, * node neu'n x nod.

413
00:31:34,870 --> 00:31:37,380
Nid oes gennym unrhyw syniad beth x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
neu gallem eu hargraffu a gallent fod yn fympwyol.

415
00:31:40,700 --> 00:31:44,980
Nid yw hynny'n wir o newidynnau byd-eang.

416
00:31:44,980 --> 00:31:47,450
Felly nod gwraidd neu x nod.

417
00:31:47,450 --> 00:31:53,410
Yn ddiofyn, mae popeth sy'n fyd-eang, os nad ymgychwyn benodol i ryw werth,

418
00:31:53,410 --> 00:31:57,390
mae iddo werth sero fel ei werth.

419
00:31:57,390 --> 00:32:01,150
Felly yma, gwraidd * nod, nid ydym yn benodol ymgychwyn i unrhyw beth,

420
00:32:01,150 --> 00:32:06,350
felly bydd ei gwerth diofyn yn null, sef gwerth sero o awgrymiadau.

421
00:32:06,350 --> 00:32:11,870
Mae gwerth rhagosodedig x yn mynd i olygu bod x.value yn sero,

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

423
00:32:14,260 --> 00:32:21,070
Felly, gan ei fod yn strwythur, bydd yr holl feysydd y strwythur fod yn sero gwerthoedd.

424
00:32:21,070 --> 00:32:24,410
Nid oes angen i ddefnyddio hynny yma, er.

425
00:32:24,410 --> 00:32:27,320
[Myfyrwyr] Mae'r structs yn wahanol na newidynnau eraill, ac mae'r newidynnau eraill yn

426
00:32:27,320 --> 00:32:31,400
gwerthoedd garbage; mae'r rhain yn zeros?

427
00:32:31,400 --> 00:32:36,220
[Bowden] gwerthoedd eraill hefyd. Felly, yn x, bydd x fod yn sero.

428
00:32:36,220 --> 00:32:40,070
Os yw'n ar gwmpas byd-eang, mae ganddo werth cychwynnol. >> Iawn.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Naill ai y gwerth cychwynnol a roesoch iddo neu sero.

430
00:32:48,950 --> 00:32:53,260
Rwy'n credu bod yn gofalu am hyn i gyd.

431
00:32:53,260 --> 00:32:58,390
>> Iawn. Felly, y rhan nesaf y cwestiwn yn gofyn,

432
00:32:58,390 --> 00:33:01,260
"Nawr rydym yn awyddus i ysgrifennu swyddogaeth a elwir yn cynnwys

433
00:33:01,260 --> 00:33:04,930
gyda prototeip o bool yn cynnwys gwerth int. "

434
00:33:04,930 --> 00:33:08,340
Nid ydym yn mynd i wneud bool yn cynnwys gwerth int.

435
00:33:08,340 --> 00:33:15,110
Mae ein prototeip yn mynd i edrych fel

436
00:33:15,110 --> 00:33:22,380
bool yn cynnwys (gwerth int.

437
00:33:22,380 --> 00:33:24,490
Ac yna rydym hefyd yn mynd i basio y goeden

438
00:33:24,490 --> 00:33:28,870
y dylai fod yn gwirio i weld a yw'n ei werth.

439
00:33:28,870 --> 00:33:38,290
Felly, nod * goeden). Iawn.

440
00:33:38,290 --> 00:33:44,440
Ac yna gallwn ei alw gyda rhywbeth fel,

441
00:33:44,440 --> 00:33:46,090
efallai y byddwn eisiau printf neu rywbeth.

442
00:33:46,090 --> 00:33:51,040
Yn cynnwys 6, ein gwreiddiau.

443
00:33:51,040 --> 00:33:54,300
Y dylai ddychwelyd un, neu yn wir,

444
00:33:54,300 --> 00:33:59,390
tra yn cynnwys 5 Dylai gwraidd ddychwelyd ffug.

445
00:33:59,390 --> 00:34:02,690
Felly, am eiliad, i weithredu hyn.

446
00:34:02,690 --> 00:34:06,780
Gallwch ei wneud naill ai yn iteraidd neu'n ailadroddus.

447
00:34:06,780 --> 00:34:09,739
Y peth braf am y ffordd yr ydym wedi gosod pethau i fyny yw bod

448
00:34:09,739 --> 00:34:12,300
mae'n cynnig ei hun i ein ateb recursive yn llawer haws

449
00:34:12,300 --> 00:34:14,719
na'r ffordd fyd-eang-amrywiol wnaeth.

450
00:34:14,719 --> 00:34:19,750
Oherwydd os ydym yn unig yn cael cynnwys gwerth int, yna nid oes gennym unrhyw ffordd o recursing i lawr subtrees.

451
00:34:19,750 --> 00:34:24,130
Byddai'n rhaid i ni gael swyddogaeth gynorthwyydd ar wahân sy'n recurses i lawr y subtrees i ni.

452
00:34:24,130 --> 00:34:29,610
Ond ers i ni wedi newid i gymryd y goeden fel dadl,

453
00:34:29,610 --> 00:34:32,760
y dylai fod bob amser wedi bod yn y lle cyntaf,

454
00:34:32,760 --> 00:34:35,710
yn awr rydym yn gallu recurse yn haws.

455
00:34:35,710 --> 00:34:38,960
Felly ailadroddol neu ailadroddus, byddwn yn mynd dros y ddau,

456
00:34:38,960 --> 00:34:46,139
ond byddwn yn gweld bod yn dod i ben i fyny recursive fod yn eithaf hawdd.

457
00:34:59,140 --> 00:35:02,480
Iawn. Oes gan unrhyw un rhywbeth y gallwn weithio gyda?

458
00:35:02,480 --> 00:35:12,000
>> [Myfyrwyr] Mae gen i ailadroddol ateb. >> Mae pob hawl, ailadroddol.

459
00:35:12,000 --> 00:35:16,030
Iawn, mae hyn yn edrych yn dda.

460
00:35:16,030 --> 00:35:18,920
Felly, yn awyddus i gerdded i ni drwyddo?

461
00:35:18,920 --> 00:35:25,780
[Myfyrwyr] Cadarn. Felly, yr wyf yn gosod newidyn dros dro i gael y nod cyntaf y goeden.

462
00:35:25,780 --> 00:35:28,330
Ac yna Fi jyst dolennog drwy er nad dros dro yn null cyfartal,

463
00:35:28,330 --> 00:35:31,700
felly er yn dal yn y coed, yr wyf yn dyfalu.

464
00:35:31,700 --> 00:35:35,710
Ac os bydd y gwerth yn cyfateb i werth y temp yn pwyntio at,

465
00:35:35,710 --> 00:35:37,640
yna mae'n dychwelyd y gwerth.

466
00:35:37,640 --> 00:35:40,210
Fel arall, mae'n gwirio os yw'n ar yr ochr dde neu'r ochr chwith.

467
00:35:40,210 --> 00:35:43,400
Os ydych chi erioed wedi cael sefyllfa lle nad oes coed mwy,

468
00:35:43,400 --> 00:35:47,330
yna mae'n dychwelyd - mae'n gadael y ddolen ac yn dychwelyd ffug.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Iawn. Felly dyna ymddangos yn dda.

470
00:35:52,190 --> 00:35:58,470
Dylai unrhyw un gennych unrhyw sylwadau ar unrhyw beth?

471
00:35:58,470 --> 00:36:02,400
Nid oes gennyf unrhyw sylwadau cywirdeb o gwbl.

472
00:36:02,400 --> 00:36:11,020
Yr un peth y gallwn ei wneud yn y boi.

473
00:36:11,020 --> 00:36:21,660
O, mae'n mynd i fynd gyd gyda'i gilydd ychydig.

474
00:36:21,660 --> 00:36:33,460
'N annhymerus' atgyweiria hynny. Iawn.

475
00:36:33,460 --> 00:36:37,150
>> Dylai pawb yn cofio sut deiran yn gweithio.

476
00:36:37,150 --> 00:36:38,610
Mae wedi bendant wedi cwisiau yn y gorffennol

477
00:36:38,610 --> 00:36:41,170
sy'n rhoi i chi swyddogaeth gyda gweithredydd teiran,

478
00:36:41,170 --> 00:36:45,750
a dweud, cyfieithu hyn, wneud rhywbeth nad yw'n defnyddio teiran.

479
00:36:45,750 --> 00:36:49,140
Felly, mae hyn yn achos cyffredin iawn pan fyddwn yn meddwl i ddefnyddio teiran,

480
00:36:49,140 --> 00:36:54,610
lle os yw rhai amod a osodir newidyn i rywbeth,

481
00:36:54,610 --> 00:36:58,580
gosod y newidyn arall yr un i rywbeth arall.

482
00:36:58,580 --> 00:37:03,390
Mae hynny'n rhywbeth y gall yn aml iawn yn cael ei drawsnewid i mewn i math hwn o beth

483
00:37:03,390 --> 00:37:14,420
os ydynt wedi'u y newidyn i hyn - neu, yn dda, mae hyn yn wir? Yna hyn, arall y.

484
00:37:14,420 --> 00:37:18,550
[Myfyrwyr] Mae'r un cyntaf yw os yw'n wir, dde?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. Y ffordd yr wyf bob amser yn darllen y mae, dros dro yn dychwelyd gwerth yn fwy na gwerth dros dro,

486
00:37:25,570 --> 00:37:30,680
yna mae hyn, arall y. Mae'n gofyn cwestiwn.

487
00:37:30,680 --> 00:37:35,200
A yw'n fwy? Yna gwneud y peth cyntaf. Arall gwneud y peth ail.

488
00:37:35,200 --> 00:37:41,670
Yr wyf yn bron bob amser - y colon, Fi jyst - yn fy mhen, yr wyf yn darllen fel arall.

489
00:37:41,670 --> 00:37:47,180
>> Oes gan unrhyw un ateb recursive?

490
00:37:47,180 --> 00:37:49,670
Iawn. Mae hyn yn un rydym ni'n mynd i - gallai fod eisoes yn wych,

491
00:37:49,670 --> 00:37:53,990
ond rydym ni'n mynd i'w wneud yn hyd yn oed yn well.

492
00:37:53,990 --> 00:37:58,720
Dyma 'n bert lawer y syniad union yr un.

493
00:37:58,720 --> 00:38:03,060
Mae'n jyst, wel, ydych chi eisiau i esbonio?

494
00:38:03,060 --> 00:38:08,340
[Myfyrwyr] Cadarn. Felly, rydym yn gwneud yn siŵr nad yw'r goeden yn null gyntaf,

495
00:38:08,340 --> 00:38:13,380
oherwydd os bydd y goeden yn null, yna mae'n mynd i ddychwelyd ffug oherwydd nad ydym wedi dod o hyd iddo.

496
00:38:13,380 --> 00:38:19,200
Ac os oes dal i fod yn goeden, byddwn yn mynd - yn gyntaf wirio a yw'r gwerth yn y nod ar hyn o bryd.

497
00:38:19,200 --> 00:38:23,740
Dychwelyd wir os ydyw, ac os nad ydym yn recurse ar y chwith neu i'r dde.

498
00:38:23,740 --> 00:38:25,970
A yw hynny'n gadarn yn briodol? >> Mm-hmm. (Cytundeb)

499
00:38:25,970 --> 00:38:33,880
Felly sylwi bod hyn bron - strwythurol yn debyg iawn i'r ateb ailadroddol.

500
00:38:33,880 --> 00:38:38,200
Mae'n dim ond bod yn lle recursing, cawsom dolen gyfnod.

501
00:38:38,200 --> 00:38:40,840
Ac mae'r achos sylfaenol yma lle nad yw coed yn null cyfartal

502
00:38:40,840 --> 00:38:44,850
oedd cyflwr o dan yr ydym dorrodd allan o'r ddolen tra.

503
00:38:44,850 --> 00:38:50,200
Maen nhw'n debyg iawn. Ond rydym yn mynd i gymryd hyn un cam ymhellach.

504
00:38:50,200 --> 00:38:54,190
Nawr, rydym yn gwneud yr un peth yma.

505
00:38:54,190 --> 00:38:57,680
Hysbysiad rydym yn dychwelyd yr un peth yn y ddau llinellau hyn,

506
00:38:57,680 --> 00:39:00,220
heblaw am un ddadl yn wahanol.

507
00:39:00,220 --> 00:39:07,950
Felly, rydym yn mynd i wneud hynny i mewn i teiran.

508
00:39:07,950 --> 00:39:13,790
Yr wyf yn taro rhywbeth opsiwn, a gwnaeth symbol. Iawn.

509
00:39:13,790 --> 00:39:21,720
Felly, rydym yn mynd i ddychwelyd yn cynnwys hynny.

510
00:39:21,720 --> 00:39:28,030
Mae hyn yn mynd i fod yn llinellau lluosog, yn dda, chwyddo i mewn ag y mae.

511
00:39:28,030 --> 00:39:31,060
Fel arfer, fel peth arddull, nid wyf yn meddwl llawer o bobl

512
00:39:31,060 --> 00:39:38,640
rhoi bwlch ar ôl y saeth, ond mae'n debyg os ydych yn gyson, mae'n iawn.

513
00:39:38,640 --> 00:39:44,320
Os gwerth yn llai na gwerth coed, rydym am i recurse ar y chwith coed,

514
00:39:44,320 --> 00:39:53,890
arall yr ydym yn awyddus i recurse goeden ar y dde.

515
00:39:53,890 --> 00:39:58,610
Felly dyna oedd y cam cyntaf o wneud hyn yn edrych yn llai.

516
00:39:58,610 --> 00:40:02,660
Cam dau o wneud hyn yn edrych yn llai -

517
00:40:02,660 --> 00:40:09,150
gallwn wahanu'r hyn i linellau lluosog.

518
00:40:09,150 --> 00:40:16,500
Iawn. Cam dau o wneud iddo edrych yn llai yma,

519
00:40:16,500 --> 00:40:25,860
felly gwerth dychwelyd hafal werth coed, neu sy'n cynnwys beth bynnag.

520
00:40:25,860 --> 00:40:28,340
>> Mae hwn yn beth pwysig.

521
00:40:28,340 --> 00:40:30,860
Dwi ddim yn siŵr os dywedodd ei fod yn eglur yn y dosbarth,

522
00:40:30,860 --> 00:40:34,740
ond fe'i gelwir byr-cylched werthuso.

523
00:40:34,740 --> 00:40:41,060
Y syniad yma yw gwerth == gwerth coed.

524
00:40:41,060 --> 00:40:49,960
Os yw hynny'n wir, yna mae hyn yn wir, ac rydym am i 'neu' bod gyda beth bynnag sydd dros yma.

525
00:40:49,960 --> 00:40:52,520
Felly, heb hyd yn oed feddwl am beth bynnag sydd dros yma,

526
00:40:52,520 --> 00:40:55,070
beth yw'r ymadrodd cyfan yn mynd i ddychwelyd?

527
00:40:55,070 --> 00:40:59,430
[Myfyrwyr] Gwir? >> Yeah, oherwydd yn wir am unrhyw beth,

528
00:40:59,430 --> 00:41:04,990
or'd - or'd neu yn wir gydag unrhyw beth o reidrwydd yn wir.

529
00:41:04,990 --> 00:41:08,150
Felly, cyn gynted ag y gwelwn werth dychwelyd gwerth coed =,

530
00:41:08,150 --> 00:41:10,140
rydym yn jyst yn mynd i ddychwelyd yn wir.

531
00:41:10,140 --> 00:41:15,710
Nid hyd yn oed yn mynd i recurse bellach yn cynnwys i lawr y llinell.

532
00:41:15,710 --> 00:41:20,980
Gallwn gymryd hyn un cam ymhellach.

533
00:41:20,980 --> 00:41:29,490
Nid yw'r goeden Dychwelyd yn null cyfartal a hyn i gyd.

534
00:41:29,490 --> 00:41:32,650
Mae'n ei gwneud yn swyddogaeth un llinell.

535
00:41:32,650 --> 00:41:36,790
Mae hyn hefyd yn enghraifft o gylched byr-werthuso.

536
00:41:36,790 --> 00:41:40,680
Ond yn awr mae'n un syniad -

537
00:41:40,680 --> 00:41:47,320
yn hytrach na - felly os coeden nad yw'n null cyfartal - neu, yn dda,

538
00:41:47,320 --> 00:41:49,580
os goeden yn null cyfartal, sydd yn wir ddrwg,

539
00:41:49,580 --> 00:41:54,790
os goeden hafal null, yna mae'r amod cyntaf yn mynd i fod yn ffug.

540
00:41:54,790 --> 00:42:00,550
Felly, ffug anded ag unrhyw beth yn mynd i fod yn beth?

541
00:42:00,550 --> 00:42:04,640
[Myfyrwyr] Anghywir. >> Yeah. Mae hyn yn yr hanner arall byr-cylched gwerthuso,

542
00:42:04,640 --> 00:42:10,710
lle os goeden yn null nid gyfartal, yna nid ydym yn mynd i hyd yn oed fynd -

543
00:42:10,710 --> 00:42:14,930
neu os goeden yn null cyfartal, yna nid ydym yn mynd i wneud gwerth == gwerth coed.

544
00:42:14,930 --> 00:42:17,010
Rydym yn unig yn mynd i ddychwelyd ar unwaith ffug.

545
00:42:17,010 --> 00:42:20,970
Pa yn bwysig, oherwydd os nad oedd byr-cylched werthuso,

546
00:42:20,970 --> 00:42:25,860
yna os goeden yn null cyfartal, mae hyn yn ail amod yn mynd i seg fai,

547
00:42:25,860 --> 00:42:32,510
oherwydd bod coed> werth yn dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Felly dyna hynny. A all wneud hyn - newid unwaith dros.

549
00:42:40,490 --> 00:42:44,840
Mae hyn yn beth cyffredin iawn hefyd, beidio â gwneud y llinell hon un â hyn,

550
00:42:44,840 --> 00:42:49,000
ond mae'n beth cyffredin mewn amgylchiadau, efallai na dde yma,

551
00:42:49,000 --> 00:42:59,380
ond os (goeden! = NULL, a gwerth == coed> werth), gwneud beth bynnag.

552
00:42:59,380 --> 00:43:01,560
Mae hwn yn gyflwr cyffredin iawn, lle yn hytrach na chael

553
00:43:01,560 --> 00:43:06,770
i dorri hyn i ddau IFS, lle hoffi, yw'r null goeden?

554
00:43:06,770 --> 00:43:11,780
Iawn, nid yw'n null, felly nawr yw'r gwerth coed cyfartal i werth? Gwnewch hyn.

555
00:43:11,780 --> 00:43:17,300
Yn hytrach, y cyflwr hwn, ni fydd hyn yn SEG bai

556
00:43:17,300 --> 00:43:21,220
oherwydd bydd yn torri allan os bydd hyn yn digwydd i fod yn null.

557
00:43:21,220 --> 00:43:24,000
Wel, yr wyf yn dyfalu os yw eich coeden yn hollol annilys pwyntydd, gall fod yn dal SEG fai,

558
00:43:24,000 --> 00:43:26,620
ond ni all SEG bai os coeden yn null.

559
00:43:26,620 --> 00:43:32,900
Pe bai'n null, byddai'n torri allan cyn i chi dereferenced erioed y pwyntydd yn y lle cyntaf.

560
00:43:32,900 --> 00:43:35,000
[Myfyrwyr] A yw hyn yn werthusiad ddiog elwir?

561
00:43:35,000 --> 00:43:40,770
>> Gwerthuso [Bowden] Lazy yn beth ar wahân.

562
00:43:40,770 --> 00:43:49,880
Gwerthuso Lazy yn fwy fel chi ofyn am werth,

563
00:43:49,880 --> 00:43:54,270
byddwch yn gofyn i gyfrifo gwerth, math o, ond nid oes angen ar unwaith.

564
00:43:54,270 --> 00:43:59,040
Felly, hyd nes y byddwch ei angen mewn gwirionedd, nid yw'n cael ei werthuso.

565
00:43:59,040 --> 00:44:03,920
Nid yw hyn yn union yr un peth, ond yn y pset Huffman,

566
00:44:03,920 --> 00:44:06,520
ei fod yn dweud ein bod yn "ddiog" ysgrifennu.

567
00:44:06,520 --> 00:44:08,670
Y rheswm rydym yn ei wneud hynny oherwydd ein bod mewn gwirionedd yn clustogi y ysgrifennu -

568
00:44:08,670 --> 00:44:11,820
nid ydym am i ysgrifennu darnau unigol ar y tro,

569
00:44:11,820 --> 00:44:15,450
neu bytes unigol ar y tro, rydym yn lle hynny am gael darn o bytes.

570
00:44:15,450 --> 00:44:19,270
Yna, unwaith y bydd gennym darn o bytes, yna byddwn yn ysgrifennu arni.

571
00:44:19,270 --> 00:44:22,640
Hyd yn oed er byddwch yn gofyn iddo ysgrifennu - a fwrite a fread gwneud yr un math o beth.

572
00:44:22,640 --> 00:44:26,260
Maent yn clustogi eich darllen ac ysgrifennu.

573
00:44:26,260 --> 00:44:31,610
Hyd yn oed er byddwch yn gofyn i ysgrifennu ar unwaith, mae'n debyg nad fydd.

574
00:44:31,610 --> 00:44:34,540
Ac ni allwch fod yn siwr bod pethau'n mynd i gael ei ysgrifennu

575
00:44:34,540 --> 00:44:37,540
hyd nes y byddwch yn ffonio hfclose neu beth bynnag ydyw,

576
00:44:37,540 --> 00:44:39,620
sydd wedyn yn dweud, iawn, dwi'n cau fy ffeil,

577
00:44:39,620 --> 00:44:43,450
sy'n golygu y byddai'n well i mi ysgrifennu popeth Nid wyf wedi ysgrifennu eto.

578
00:44:43,450 --> 00:44:45,770
Mae wedi oes angen i chi ysgrifennu popeth allan

579
00:44:45,770 --> 00:44:49,010
nes eich bod yn cau y ffeil, ac yna mae angen iddo.

580
00:44:49,010 --> 00:44:56,220
Felly dyna'n union yr hyn ddiog - mae'n aros hyd nes y mae'n rhaid iddo ddigwydd.

581
00:44:56,220 --> 00:44:59,990
Mae hyn yn - cymryd 51 a byddwch yn mynd i mewn iddo yn fwy manwl,

582
00:44:59,990 --> 00:45:05,470
oherwydd OCaml a phopeth mewn 51, mae popeth yn dychweliad.

583
00:45:05,470 --> 00:45:08,890
Nid oes unrhyw atebion ailadroddol, yn y bôn.

584
00:45:08,890 --> 00:45:11,550
Mae popeth yn dychweliad, a gwerthuso diog

585
00:45:11,550 --> 00:45:14,790
yn mynd i fod yn bwysig ar gyfer llawer o amgylchiadau

586
00:45:14,790 --> 00:45:19,920
lle, os nad oeddech yn ddiog gwerthuso, a fyddai'n golygu -

587
00:45:19,920 --> 00:45:24,760
Mae'r enghraifft yn nentydd, sydd yn eithriadol hir.

588
00:45:24,760 --> 00:45:30,990
Mewn theori, gallwch feddwl am y rhifau naturiol fel ffrwd o 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Pethau Felly lazily gwerthuso yn iawn.

590
00:45:33,090 --> 00:45:37,210
Os wyf yn dweud fy mod am i'r rhif degfed, yna gallaf werthuso hyd at y nifer degfed.

591
00:45:37,210 --> 00:45:40,300
Os ydw i am i'r rhif ganfed, yna gallaf werthuso hyd at y nifer canfed.

592
00:45:40,300 --> 00:45:46,290
Heb werthusiad ddiog, yna mae'n mynd i geisio i werthuso'r holl rifau ar unwaith.

593
00:45:46,290 --> 00:45:50,000
Rydych yn gwerthuso nifer anfeidrol lawer, ac nad dim ond y bo modd.

594
00:45:50,000 --> 00:45:52,080
Felly, mae yna lawer o amgylchiadau lle gwerthuso ddiog

595
00:45:52,080 --> 00:45:57,840
yn unig yn hanfodol i gael pethau i weithio.

596
00:45:57,840 --> 00:46:05,260
>> Nawr rydym am i ysgrifennu nodwch lle rhowch yn ei le yn mynd i fod

597
00:46:05,260 --> 00:46:08,430
ran newid yn ei ddiffiniad.

598
00:46:08,430 --> 00:46:10,470
Felly, ar hyn o bryd mae'n mewnosod bool (gwerth int).

599
00:46:10,470 --> 00:46:23,850
Rydym yn mynd i newid hynny i mewnosodwch bool (int gwerth, nod * coeden).

600
00:46:23,850 --> 00:46:29,120
Rydym yn wir yn mynd i newid hynny eto mewn ychydig, byddwn yn gweld pam.

601
00:46:29,120 --> 00:46:32,210
A gadewch i ni symud build_node, dim ond ar gyfer y Heck ohono,

602
00:46:32,210 --> 00:46:36,730
uchod yn mewnosod felly nid ydym yn rhaid i chi ysgrifennu prototeip swyddogaeth.

603
00:46:36,730 --> 00:46:42,450
Pa yn awgrym eich bod yn mynd i gael ei defnyddio build_node yn mewnosod.

604
00:46:42,450 --> 00:46:49,590
Iawn. Cymerwch funud ar gyfer hynny.

605
00:46:49,590 --> 00:46:52,130
Rwy'n credu fy mod arbed yr adolygiad os ydych am dynnu hynny,

606
00:46:52,130 --> 00:47:00,240
neu, o leiaf, yr wyf yn gwneud yn awr.

607
00:47:00,240 --> 00:47:04,190
Roeddwn i eisiau cael seibiant bach i feddwl am y rhesymeg mewnosoder,

608
00:47:04,190 --> 00:47:08,750
os nad ydych yn gallu meddwl amdano.

609
00:47:08,750 --> 00:47:12,860
Yn y bôn, byddwch ond byth yn cael ei fewnosod yn y dail.

610
00:47:12,860 --> 00:47:18,640
Fel, os wyf yn mewnosod 1, yna rwy'n anochel yn mynd i gael ei gosod 1 -

611
00:47:18,640 --> 00:47:21,820
'N annhymerus' newid i ddu - I'll yn gosod 1 dros yma.

612
00:47:21,820 --> 00:47:28,070
Neu os byddaf yn ychwanegu 4, hoffwn gael eu gosod 4 dros yma.

613
00:47:28,070 --> 00:47:32,180
Felly, dim ots beth ydych yn ei wneud, rydych yn mynd i gael eu gosod ar y ddeilen.

614
00:47:32,180 --> 00:47:36,130
Y cyfan sydd raid i chi ei wneud yw ailadrodd i lawr y goeden nes i chi gyrraedd y nod

615
00:47:36,130 --> 00:47:40,890
a ddylai fod yn rhiant y nod, rhiant y nod newydd,

616
00:47:40,890 --> 00:47:44,560
ac yna newid ei pwyntydd ar y chwith neu i'r dde, yn dibynnu ar p'un a

617
00:47:44,560 --> 00:47:47,060
mae'n fwy na neu'n llai na'r nod ar hyn o bryd.

618
00:47:47,060 --> 00:47:51,180
Newid y pwyntydd i bwyntio at eich nod newydd.

619
00:47:51,180 --> 00:48:05,490
Felly, ailadrodd i lawr y goeden, yn gwneud y pwynt ddeilen at y nod newydd.

620
00:48:05,490 --> 00:48:09,810
Hefyd yn meddwl am pam sy'n gwahardd y math o sefyllfa o'r blaen,

621
00:48:09,810 --> 00:48:17,990
lle yr wyf yn adeiladu y goeden ddeuaidd lle'r oedd yn gywir

622
00:48:17,990 --> 00:48:19,920
os mai dim ond edrych ar nod unigol,

623
00:48:19,920 --> 00:48:24,830
ond 9 oedd i'r chwith o 7 os ydych Ailadroddodd i lawr yr holl ffordd.

624
00:48:24,830 --> 00:48:29,770
Felly, mae hyn yn amhosibl yn y sefyllfa hon, ers hynny -

625
00:48:29,770 --> 00:48:32,530
meddwl am osod 9 neu rhywbeth; yn y nod cyntaf,

626
00:48:32,530 --> 00:48:35,350
Dw i'n mynd i weld 7 a Im 'jyst yn mynd i fynd ar y dde.

627
00:48:35,350 --> 00:48:38,490
Felly, dim ots beth ddylwn i ei wneud, os ydw i'n gosod trwy fynd i deilen,

628
00:48:38,490 --> 00:48:40,790
ac i deilen gan ddefnyddio algorithm priodol,

629
00:48:40,790 --> 00:48:43,130
mae'n mynd i fod yn amhosibl i mi i fewnosod 9 i'r chwith o 7

630
00:48:43,130 --> 00:48:48,250
oherwydd cyn gynted ag y taro 7 Rwyf i'n mynd i fynd ar y dde.

631
00:48:59,740 --> 00:49:02,070
Oes gan unrhyw un rywbeth i ddechrau?

632
00:49:02,070 --> 00:49:05,480
[Myfyrwyr] ddylwn i ei wneud. >> Cadarn.

633
00:49:05,480 --> 00:49:09,200
[Myfyrwyr, annealladwy]

634
00:49:09,200 --> 00:49:14,390
[Fyfyrwyr eraill, annealladwy]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Mae'n cael ei werthfawrogi. Iawn. Eisiau esbonio?

636
00:49:18,330 --> 00:49:20,690
>> [Myfyrwyr] Ers i ni wybod ein bod yn mewnosod

637
00:49:20,690 --> 00:49:24,060
nodau newydd ar ddiwedd y goeden,

638
00:49:24,060 --> 00:49:28,070
I dolennog drwy'r goeden iteraidd

639
00:49:28,070 --> 00:49:31,360
hyd nes i mi gyrraedd sefyllfa o nod a dynnodd sylw at null.

640
00:49:31,360 --> 00:49:34,220
Ac yna penderfynais ei roi naill ai ar yr ochr dde neu'r ochr chwith

641
00:49:34,220 --> 00:49:37,420
defnyddio'r newidyn hwn iawn, mae'n dweud wrthyf ble i roi.

642
00:49:37,420 --> 00:49:41,850
Ac yna, yn y bôn, Fi jyst gwneud y diwedd -

643
00:49:41,850 --> 00:49:47,520
bod dros dro pwynt nod at y nod newydd ei bod yn creu,

644
00:49:47,520 --> 00:49:50,770
naill ai ar yr ochr chwith neu ar yr ochr dde, yn dibynnu ar beth yw gwerth iawn oedd.

645
00:49:50,770 --> 00:49:56,530
Yn olaf, yr wyf yn gosod y gwerth nod newydd i'r gwerth ei brofi.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Iawn, felly yr wyf yn gweld un mater yma.

647
00:49:59,550 --> 00:50:02,050
Mae hyn yn debyg 95% o'r ffordd yno.

648
00:50:02,050 --> 00:50:07,550
Y mater un yr wyf yn gweld, yn dda, oes unrhyw un arall ei weld yn broblem?

649
00:50:07,550 --> 00:50:18,400
Beth yw'r amgylchiadau o dan ba maent yn torri allan o'r cylch?

650
00:50:18,400 --> 00:50:22,100
[Myfyrwyr] Os yw'r tymheredd yn null? >> Yeah. Felly, sut byddwch yn torri allan o'r cylch yw os dros dro yn null.

651
00:50:22,100 --> 00:50:30,220
Ond beth ddylwn i ei wneud iawn yma?

652
00:50:30,220 --> 00:50:35,410
Dros dro dereference I, sydd yn anochel yn null.

653
00:50:35,410 --> 00:50:39,840
Felly nid yw'r peth arall sydd angen i chi ei wneud yw jyst cadw trac nes dros dro yn null,

654
00:50:39,840 --> 00:50:45,590
ydych chi am gadw golwg ar y rhiant bob amser.

655
00:50:45,590 --> 00:50:52,190
Rydym hefyd am riant * nod, mae'n debyg y gallwn gadw hynny yn null ar y dechrau.

656
00:50:52,190 --> 00:50:55,480
Mae hyn yn mynd i gael ymddygiad rhyfedd i wraidd y goeden,

657
00:50:55,480 --> 00:50:59,210
ond byddwn yn mynd i hynny.

658
00:50:59,210 --> 00:51:03,950
Os werth yn fwy na'r beth bynnag, ac yna i'r dde dros dro temp =.

659
00:51:03,950 --> 00:51:07,910
Ond cyn i ni wneud hynny, rhiant = temp.

660
00:51:07,910 --> 00:51:14,500
Neu a rhieni bob amser yn mynd i dros dro cyfartal? A yw hynny'n wir?

661
00:51:14,500 --> 00:51:19,560
Os nad yw dros dro yn null, yna dwi'n mynd i symud i lawr, ni waeth beth,

662
00:51:19,560 --> 00:51:24,030
i nod y tymheredd yn rhiant.

663
00:51:24,030 --> 00:51:27,500
Felly rhiant yn mynd i fod dros dro, ac yna byddaf yn symud dros dro i lawr.

664
00:51:27,500 --> 00:51:32,410
Nawr dros dro yn null, ond mae'n tynnu sylw rhieni at y rhiant y peth sydd yn null.

665
00:51:32,410 --> 00:51:39,110
Felly i lawr yma, nid wyf am osod i'r dde yn hafal i 1.

666
00:51:39,110 --> 00:51:41,300
Felly symudais i'r dde, felly os gywir = 1,

667
00:51:41,300 --> 00:51:45,130
ac yr wyf yn dyfalu y byddwch hefyd am ei wneud -

668
00:51:45,130 --> 00:51:48,530
os byddwch yn symud i'r chwith, ydych chi eisiau i osod hawl gyfartal i 0.

669
00:51:48,530 --> 00:51:55,950
Neu arall, os ydych chi erioed wedi symud i'r dde.

670
00:51:55,950 --> 00:51:58,590
Felly, i'r dde = 0. Os cywir = 1,

671
00:51:58,590 --> 00:52:04,260
yn awr rydym eisiau gwneud y pwyntydd rhiant newnode iawn,

672
00:52:04,260 --> 00:52:08,520
arall rydym eisiau gwneud y pwyntydd rhiant newnode chwith.

673
00:52:08,520 --> 00:52:16,850
Cwestiynau ar hynny?

674
00:52:16,850 --> 00:52:24,880
Iawn. Felly, mae hyn yn y ffordd yr ydym yn - wel, mewn gwirionedd, yn hytrach na gwneud hyn,

675
00:52:24,880 --> 00:52:29,630
rydym yn disgwyl i chi 1/2 i ddefnyddio build_node.

676
00:52:29,630 --> 00:52:40,450
Ac yna os newnode hafal null, yn dychwelyd ffug.

677
00:52:40,450 --> 00:52:44,170
Dyna hynny. Yn awr, dyma beth yr ydym yn disgwyl i chi ei wneud.

678
00:52:44,170 --> 00:52:47,690
>> Dyma beth yw'r atebion staff yn ei wneud.

679
00:52:47,690 --> 00:52:52,360
Yr wyf yn anghytuno â hyn fel y "cywir" ffordd o fynd am y peth

680
00:52:52,360 --> 00:52:57,820
ond mae hyn yn berffaith iawn a bydd yn gweithio.

681
00:52:57,820 --> 00:53:02,840
Un peth sy'n hawl rhyfedd ychydig yn awr yw

682
00:53:02,840 --> 00:53:08,310
os yw'r goeden yn dechrau i ffwrdd fel null, rydym yn pasio mewn coeden null.

683
00:53:08,310 --> 00:53:12,650
Amcana mae'n dibynnu ar sut yr ydych yn diffinio ymddygiad basio mewn coeden null.

684
00:53:12,650 --> 00:53:15,490
Byddwn yn meddwl, os byddwch yn mynd heibio mewn coeden null,

685
00:53:15,490 --> 00:53:17,520
Yna gosod y gwerth i mewn i goeden null

686
00:53:17,520 --> 00:53:23,030
dylai fynd yn ôl coeden lle mae'r gwerth yn unig yw bod nod sengl.

687
00:53:23,030 --> 00:53:25,830
Ydy pobl yn cytuno â hynny? Gallech, os ydych yn dymuno,

688
00:53:25,830 --> 00:53:28,050
os byddwch yn mynd heibio mewn coeden null

689
00:53:28,050 --> 00:53:31,320
a'ch bod eisiau mewnosod gwerth i mewn iddo, yn dychwelyd ffug.

690
00:53:31,320 --> 00:53:33,830
Mae i fyny i chi i ddiffinio hynny.

691
00:53:33,830 --> 00:53:38,320
Er mwyn gwneud y peth cyntaf i mi ddweud, ac yna -

692
00:53:38,320 --> 00:53:40,720
yn dda, rydych chi'n mynd i gael trafferth gwneud hynny, oherwydd

693
00:53:40,720 --> 00:53:44,090
byddai'n haws pe bai gennym bwyntydd byd-eang at y peth,

694
00:53:44,090 --> 00:53:48,570
ond nid ydym yn ei wneud, felly os goeden yn null, does dim byd y gallwn ei wneud am hynny.

695
00:53:48,570 --> 00:53:50,960
Gallwn fynd yn ôl ffug.

696
00:53:50,960 --> 00:53:52,840
Felly dw i'n mynd i newid mewnosodiad.

697
00:53:52,840 --> 00:53:56,540
Rydym gallai dechnegol dim ond newid y dde yma,

698
00:53:56,540 --> 00:53:58,400
sut mae'n ailadrodd dros bethau,

699
00:53:58,400 --> 00:54:04,530
ond rwy'n mynd i newid rhowch yn ei le i gymryd nod ** coeden.

700
00:54:04,530 --> 00:54:07,510
Awgrymiadau dwbl.

701
00:54:07,510 --> 00:54:09,710
Beth yw ystyr hyn?

702
00:54:09,710 --> 00:54:12,330
Yn hytrach na delio â awgrymiadau i nodau,

703
00:54:12,330 --> 00:54:16,690
y peth yr wyf i'n mynd i gael eu trin yn y pwyntydd.

704
00:54:16,690 --> 00:54:18,790
Rydw i'n mynd i gael eu trin y pwyntydd.

705
00:54:18,790 --> 00:54:21,770
Rydw i'n mynd i gael eu trin awgrymiadau yn uniongyrchol.

706
00:54:21,770 --> 00:54:25,760
Mae hyn yn gwneud synnwyr ers hynny, meddyliwch am i lawr -

707
00:54:25,760 --> 00:54:33,340
yn dda, ar hyn o bryd mae hyn pwyntiau i'w null.

708
00:54:33,340 --> 00:54:38,130
Hyn yr wyf am ei wneud yw trin y pwyntydd i bwyntio at beidio null.

709
00:54:38,130 --> 00:54:40,970
Yr wyf am iddo bwyntio at fy nod newydd.

710
00:54:40,970 --> 00:54:44,870
Os Fi jyst cadw cofnod o awgrymiadau i fy awgrymiadau,

711
00:54:44,870 --> 00:54:47,840
yna nid oes angen i mi gadw golwg ar pwyntydd rhiant.

712
00:54:47,840 --> 00:54:52,640
Gall Fi jyst cadw golwg i weld os yw'r pwyntydd yn pwyntio at null,

713
00:54:52,640 --> 00:54:54,580
ac os bydd y pwyntydd yn pwyntio at null,

714
00:54:54,580 --> 00:54:57,370
newid i gyfeirio at y nod rwyf eisiau.

715
00:54:57,370 --> 00:55:00,070
A allaf newid ers i mi gael pwyntydd i'r pwyntydd.

716
00:55:00,070 --> 00:55:02,040
Gadewch i ni weld hyn yn awr.

717
00:55:02,040 --> 00:55:05,470
Gallwch wneud hynny mewn gwirionedd yn eithaf ailadroddus yn hawdd.

718
00:55:05,470 --> 00:55:08,080
A ydym eisiau gwneud hynny?

719
00:55:08,080 --> 00:55:10,980
Oes, rydym yn ei wneud.

720
00:55:10,980 --> 00:55:16,790
>> Gadewch i ni weld ei ailadroddus.

721
00:55:16,790 --> 00:55:24,070
Yn gyntaf, beth yw ein achos sylfaenol yn mynd i fod?

722
00:55:24,070 --> 00:55:29,140
Mae bron bob amser yn ein achos sylfaenol, ond mewn gwirionedd, mae hyn yn fath o anodd.

723
00:55:29,140 --> 00:55:34,370
Pethau cyntaf yn gyntaf, os (coeden == NULL)

724
00:55:34,370 --> 00:55:37,550
Amcana rydym yn jyst yn mynd i ddychwelyd ffug.

725
00:55:37,550 --> 00:55:40,460
Mae hyn yn wahanol i'ch null coed lles.

726
00:55:40,460 --> 00:55:44,510
Mae hyn yn y pwyntydd i'r pwyntydd eich gwreiddiau yn null

727
00:55:44,510 --> 00:55:48,360
sy'n golygu nad yw eich pwyntydd gwraidd yn bodoli.

728
00:55:48,360 --> 00:55:52,390
Felly i lawr yma, os wyf yn gwneud

729
00:55:52,390 --> 00:55:55,760
* nod - gadewch i ni dim ond ailddefnyddio'r hyn.

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

731
00:55:58,960 --> 00:56:00,730
ac yna yr wyf i'n mynd i alw rhowch yn ei le drwy wneud rhywbeth fel,

732
00:56:00,730 --> 00:56:04,540
rhowch 4 i & gwraidd.

733
00:56:04,540 --> 00:56:06,560
So & gwraidd, os gwraidd yn * nod

734
00:56:06,560 --> 00:56:11,170
yna & gwraidd yn mynd i fod yn ** nod.

735
00:56:11,170 --> 00:56:15,120
Mae hyn yn ddilys. Yn yr achos hwn, coed, hyd yma,

736
00:56:15,120 --> 00:56:20,120
Nid yw'r goeden yn null - neu rhowch.

737
00:56:20,120 --> 00:56:24,630
Yma. Nid yw'r goeden yn null; * goeden yn null, sy'n iawn

738
00:56:24,630 --> 00:56:26,680
oherwydd os goeden * yn null, yna gallaf drin ei

739
00:56:26,680 --> 00:56:29,210
yn hyn gyfeirio at yr hyn yr wyf am iddo bwyntio at.

740
00:56:29,210 --> 00:56:34,750
Ond os goeden yn null, sy'n golygu fy mod yn unig yn dod i lawr yma a dweud null.

741
00:56:34,750 --> 00:56:42,710
Nid yw hynny'n gwneud synnwyr. Nid wyf yn gallu gwneud unrhyw beth â hynny.

742
00:56:42,710 --> 00:56:45,540
Os goeden yn null, yn dychwelyd ffug.

743
00:56:45,540 --> 00:56:48,220
Felly, yr wyf eisoes wedi dweud y bôn yr hyn y mae ein achos sylfaenol go iawn.

744
00:56:48,220 --> 00:56:50,580
A beth yw bod yn mynd i fod?

745
00:56:50,580 --> 00:56:55,030
[Myfyrwyr, annealladwy]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Ydw. Felly, os (* coeden == NULL).

747
00:57:00,000 --> 00:57:04,520
Mae hyn yn ymwneud ag achos dros yma

748
00:57:04,520 --> 00:57:09,640
lle os bydd fy pwyntydd coch yn y pwyntydd rwy'n canolbwyntio ar,

749
00:57:09,640 --> 00:57:12,960
felly fel fy mod yn canolbwyntio ar y pwyntydd, nawr rwy'n canolbwyntio ar y pwyntydd.

750
00:57:12,960 --> 00:57:15,150
Nawr rwy'n canolbwyntio ar y pwyntydd.

751
00:57:15,150 --> 00:57:18,160
Felly, os yw fy pwyntydd coch, sef fy ** nod,

752
00:57:18,160 --> 00:57:22,880
byth - os *, fy pwyntydd coch, byth yn null,

753
00:57:22,880 --> 00:57:28,470
hynny'n golygu fy mod yn yr achos lle dwi'n canolbwyntio ar pwyntydd y pwyntiau -

754
00:57:28,470 --> 00:57:32,530
mae hwn yn pwyntydd sy'n perthyn i ddeilen.

755
00:57:32,530 --> 00:57:41,090
Rwyf am newid y pwyntydd i bwyntio at fy nod newydd.

756
00:57:41,090 --> 00:57:45,230
Dewch yn ôl dros yma.

757
00:57:45,230 --> 00:57:56,490
Bydd fy newnode yn unig fod nod * n = build_node (gwerth)

758
00:57:56,490 --> 00:58:07,300
Yna, n, os yw n = NULL, yn dychwelyd ffug.

759
00:58:07,300 --> 00:58:12,600
Arall ydym am newid yr hyn y pwyntydd ar hyn o bryd pwyntio at

760
00:58:12,600 --> 00:58:17,830
yn hyn bwyntio at ein nod newydd gael eu hadeiladu.

761
00:58:17,830 --> 00:58:20,280
Gallwn yn gwneud hynny yma.

762
00:58:20,280 --> 00:58:30,660
Yn hytrach na dweud n, yr ydym yn dweud * coeden = os * goeden.

763
00:58:30,660 --> 00:58:35,450
Mae pawb yn deall hynny? Drwy ymdrin ag awgrymiadau i awgrymiadau,

764
00:58:35,450 --> 00:58:40,750
gallwn ni newid awgrymiadau null cyfeirio at bethau yr ydym am iddynt gyfeirio atynt.

765
00:58:40,750 --> 00:58:42,820
Dyna ein achos sylfaenol.

766
00:58:42,820 --> 00:58:45,740
>> Nawr ein eto, neu ein dychweliad,

767
00:58:45,740 --> 00:58:51,430
yn mynd i fod yn debyg iawn i'r holl recursions eraill rydym wedi bod yn ei wneud.

768
00:58:51,430 --> 00:58:55,830
Rydym yn mynd i eisiau i fewnosod gwerth,

769
00:58:55,830 --> 00:58:59,040
ac yn awr yr wyf i'n mynd i ddefnyddio deiran eto, ond beth yw ein cyflwr yn mynd i fod?

770
00:58:59,040 --> 00:59:05,180
Beth ydyw rydym yn chwilio amdano i benderfynu a ydym am fynd i'r chwith neu i'r dde?

771
00:59:05,180 --> 00:59:07,760
Gadewch i ni ei wneud mewn camau ar wahân.

772
00:59:07,760 --> 00:59:18,850
Os (gwerth <) beth?

773
00:59:18,850 --> 00:59:23,200
[Myfyrwyr] werth y goeden?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Felly cofiwch fy mod ar hyn o bryd -

775
00:59:27,490 --> 00:59:31,260
[Myfyrwyr, annealladwy]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, felly dde yma, gadewch i ni ddweud bod y saeth werdd

777
00:59:34,140 --> 00:59:39,050
yn enghraifft o'r hyn y goeden ar hyn o bryd yw, yn pwyntydd at y pwyntydd.

778
00:59:39,050 --> 00:59:46,610
Felly mae hynny'n golygu fy mod yn pwyntydd i pwyntydd i 3.

779
00:59:46,610 --> 00:59:48,800
Mae'r dereference ddwywaith yn swnio'n dda.

780
00:59:48,800 --> 00:59:51,010
Beth ydw i'n - sut ydw i'n gwneud hynny?

781
00:59:51,010 --> 00:59:53,210
[Myfyrwyr] dereference unwaith, ac yna gwneud saeth y ffordd honno?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Felly (* coeden) yw'r dereference unwaith, -> werth

783
00:59:58,420 --> 01:00:05,960
yn mynd i roi i mi gwerth y nod fy mod i'n anuniongyrchol gan bwyntio at.

784
01:00:05,960 --> 01:00:11,980
Felly gallaf hefyd ysgrifennu ei ** tree.value os yw'n well gennych hynny.

785
01:00:11,980 --> 01:00:18,490
Naill ai yn gweithio.

786
01:00:18,490 --> 01:00:26,190
Os mai dyna'r achos, yna yr wyf am alw mewnosod â gwerth.

787
01:00:26,190 --> 01:00:32,590
A beth yw fy nod ddiweddaru ** mynd i fod?

788
01:00:32,590 --> 01:00:39,440
Dw i eisiau mynd i'r chwith, felly ** tree.left yn mynd i fod yn fy chwith.

789
01:00:39,440 --> 01:00:41,900
Ac yr wyf am i'r pwyntydd i'r peth

790
01:00:41,900 --> 01:00:44,930
felly os bydd y chwith yn dod i ben i fyny yn y pwyntydd null,

791
01:00:44,930 --> 01:00:48,360
Gallaf addasu i gyfeirio at fy nod newydd.

792
01:00:48,360 --> 01:00:51,460
>> A gall yr achos arall yn debyg iawn.

793
01:00:51,460 --> 01:00:55,600
Gadewch i ni mewn gwirionedd yn gwneud bod fy teiran ar hyn o bryd.

794
01:00:55,600 --> 01:01:04,480
Rhowch werth os werth <(** coeden). Werth.

795
01:01:04,480 --> 01:01:11,040
Yna, rydym yn awyddus i ddiweddaru ein ** ar y chwith,

796
01:01:11,040 --> 01:01:17,030
arall yr ydym yn awyddus i ddiweddaru ein ** ar y dde.

797
01:01:17,030 --> 01:01:22,540
[Myfyrwyr] yw hynny'n cael y pwyntydd i'r pwyntydd?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Cofiwch fod - ** tree.right yn seren nod.

799
01:01:30,940 --> 01:01:35,040
[Myfyrwyr, annealladwy] >> Yeah.

800
01:01:35,040 --> 01:01:41,140
** Tree.right fel hyn pwyntydd neu rywbeth.

801
01:01:41,140 --> 01:01:45,140
Felly, drwy gymryd pwyntydd hynny, y mae yn rhoi i mi yr hyn yr wyf eisiau

802
01:01:45,140 --> 01:01:50,090
y pwyntydd i'r dyn.

803
01:01:50,090 --> 01:01:54,260
[Myfyrwyr] A gawn ni fynd dros eto pam ein bod yn defnyddio y ddau awgrymiadau?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Felly - na, allwch, a bod ateb cyn

805
01:01:58,220 --> 01:02:04,540
yn ffordd o wneud hyn heb wneud dau awgrymiadau.

806
01:02:04,540 --> 01:02:08,740
Mae angen i chi allu deall gan ddefnyddio dau awgrymiadau,

807
01:02:08,740 --> 01:02:11,660
ac mae hyn yn ateb glanach.

808
01:02:11,660 --> 01:02:16,090
Hefyd, yn sylwi bod, beth fydd yn digwydd os bydd fy coeden -

809
01:02:16,090 --> 01:02:24,480
beth sy'n digwydd os yw fy gwraidd yn null? Beth fydd yn digwydd os wyf yn gwneud yr achos hwn iawn yma?

810
01:02:24,480 --> 01:02:30,540
Felly, nod * gwraidd = NULL, rhowch 4 i & gwraidd.

811
01:02:30,540 --> 01:02:35,110
Beth yw gwraidd mynd i fod ar ôl hyn?

812
01:02:35,110 --> 01:02:37,470
[Myfyrwyr, annealladwy] >> Yeah.

813
01:02:37,470 --> 01:02:41,710
Gwerth Root yn mynd i fod yn 4.

814
01:02:41,710 --> 01:02:45,510
Chwith Root yn mynd i fod yn null, hawl gwraidd yn mynd i fod yn null.

815
01:02:45,510 --> 01:02:49,490
Yn yr achos lle nad oeddem yn pasio wraidd ôl cyfeiriad,

816
01:02:49,490 --> 01:02:52,490
nid oeddem yn gallu addasu gwraidd.

817
01:02:52,490 --> 01:02:56,020
Yn yr achos lle y goeden - lle gwraidd yn null,

818
01:02:56,020 --> 01:02:58,410
rydym yn unig wedi dychwelyd ffug. Does dim byd y gallem ei wneud.

819
01:02:58,410 --> 01:03:01,520
Ni allwn gosod nod i mewn i goeden wag.

820
01:03:01,520 --> 01:03:06,810
Ond yn awr rydym yn gallu; byddwn yn gwneud coeden wag i mewn i goeden un nod.

821
01:03:06,810 --> 01:03:13,400
Pa un yw fel arfer yn y ffordd y disgwylir ei fod yn fod i weithio.

822
01:03:13,400 --> 01:03:21,610
>> Ar ben hynny, mae hyn yn sylweddol fyrrach na'r

823
01:03:21,610 --> 01:03:26,240
hefyd yn cadw golwg ar y rhiant, ac felly i chi ailadrodd i lawr yr holl ffordd.

824
01:03:26,240 --> 01:03:30,140
Nawr rwyf wedi fy rhieni, a Fi jyst wedi fy rhieni pwyntydd hawl i beth bynnag.

825
01:03:30,140 --> 01:03:35,640
Yn lle hynny, os ydym yn gwneud hyn iteraidd, byddwn yn cael yr un syniad gyda dolen gyfnod.

826
01:03:35,640 --> 01:03:38,100
Ond yn hytrach na gorfod delio gyda fy pwyntydd rhiant,

827
01:03:38,100 --> 01:03:40,600
yn hytrach na byddai fy pwyntydd ar hyn o bryd fod y peth

828
01:03:40,600 --> 01:03:43,790
fy mod yn uniongyrchol addasu i bwyntio at fy nod newydd.

829
01:03:43,790 --> 01:03:46,090
Nid oes gennyf i ddelio ag a yw'n pwyntio i'r chwith.

830
01:03:46,090 --> 01:03:48,810
Nid oes gennyf i ddelio ag a yw'n pwyntio i'r dde.

831
01:03:48,810 --> 01:04:00,860
Dim ond beth bynnag y pwyntydd yw, dwi'n mynd i osod i bwyntio at fy nod newydd.

832
01:04:00,860 --> 01:04:05,740
Mae pawb yn deall sut mae'n gweithio?

833
01:04:05,740 --> 01:04:09,460
Os na, pam ydym ni eisiau ei wneud fel hyn,

834
01:04:09,460 --> 01:04:14,920
ond o leiaf bod hyn yn gweithio fel ateb?

835
01:04:14,920 --> 01:04:17,110
[Myfyrwyr] Ble rydyn ni'n dychwelyd yn wir?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Mae hynny'n debyg iawn yma.

837
01:04:21,550 --> 01:04:26,690
Os ydym yn gywir rhowch ef, yn dychwelyd yn wir.

838
01:04:26,690 --> 01:04:32,010
Else, i lawr yma rydym yn mynd i eisiau dychwelyd ffurflenni rhowch beth bynnag.

839
01:04:32,010 --> 01:04:35,950
>> A beth sy'n arbennig am y swyddogaeth recursive?

840
01:04:35,950 --> 01:04:43,010
Mae'n gynffon recursive, felly cyn belled ag y llunio gyda rhywfaint o optimization,

841
01:04:43,010 --> 01:04:48,060
bydd yn cydnabod hynny ac na fyddwch byth yn cael gorlif pentwr o hyn,

842
01:04:48,060 --> 01:04:53,230
hyd yn oed os yw ein coed yn cael uchder o 10,000 neu 10 miliwn.

843
01:04:53,230 --> 01:04:55,630
[Myfyrwyr, annealladwy]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Rwy'n credu y mae'n ei wneud yn Dash - neu ba lefel optimeiddio

845
01:05:00,310 --> 01:05:03,820
ei angen ar gyfer dychweliad gynffon i gael ei gydnabod.

846
01:05:03,820 --> 01:05:09,350
Rwy'n credu ei fod yn cydnabod - Cyngor Gwynedd a Clang

847
01:05:09,350 --> 01:05:12,610
hefyd yn cael ystyron gwahanol ar gyfer eu lefelau Optimization.

848
01:05:12,610 --> 01:05:17,870
Hoffwn i ddweud ei fod DashO 2, yn sicr y bydd yn cydnabod dychweliad gynffon.

849
01:05:17,870 --> 01:05:27,880
Ond ni - gallech adeiladu fel enghraifft rywbeth Fibonocci neu.

850
01:05:27,880 --> 01:05:30,030
Nid yw'n hawdd i brofi â hyn, oherwydd ei fod yn anodd i adeiladu

851
01:05:30,030 --> 01:05:32,600
goeden ddeuaidd sydd mor fawr.

852
01:05:32,600 --> 01:05:37,140
Ond yeah, yr wyf yn meddwl ei fod yn DashO 2, sy'n

853
01:05:37,140 --> 01:05:40,580
os ydych yn llunio gyda DashO 2, bydd yn edrych am dychweliad gynffon

854
01:05:40,580 --> 01:05:54,030
a gwneud y gorau hynny.

855
01:05:54,030 --> 01:05:58,190
Gadewch i ni fynd yn ôl i - rhowch llythrennol y peth olaf sydd ei angen.

856
01:05:58,190 --> 01:06:04,900
Gadewch i ni fynd yn ôl i'r mewnosodiad dros yma

857
01:06:04,900 --> 01:06:07,840
lle'r ydym yn mynd i wneud yr un syniad.

858
01:06:07,840 --> 01:06:14,340
Bydd yn dal i gael y flaw o beidio â bod yn gallu ymdrin yn gyfan gwbl

859
01:06:14,340 --> 01:06:17,940
pan fydd y gwreiddiau ei hun yn null, neu y cofnod diwethaf yn null,

860
01:06:17,940 --> 01:06:20,060
ond yn hytrach na delio gyda pwyntydd rhiant,

861
01:06:20,060 --> 01:06:27,430
gadewch i ni wneud cais yr un rhesymeg o awgrymiadau gan gadw at awgrymiadau.

862
01:06:27,430 --> 01:06:35,580
Os dyma rydym yn cadw ein nod ** cyf,

863
01:06:35,580 --> 01:06:37,860
ac nid oes angen i ni gadw golwg ar hawl i anymore,

864
01:06:37,860 --> 01:06:47,190
ond nod ** cyf = & goeden.

865
01:06:47,190 --> 01:06:54,800
Ac yn awr mae ein dolen tra yn mynd i fod er nad cyf * yn null cyfartal.

866
01:06:54,800 --> 01:07:00,270
Nid oes angen i gadw golwg ar rieni anymore.

867
01:07:00,270 --> 01:07:04,180
Nid oes angen i gadw golwg ar y chwith ac i'r dde.

868
01:07:04,180 --> 01:07:10,190
A byddaf yn ei alw dros dro, oherwydd ein bod eisoes yn defnyddio dros dro.

869
01:07:10,190 --> 01:07:17,200
Iawn. Felly os (gwerth> * dros dro),

870
01:07:17,200 --> 01:07:24,010
Yna, & (* dros dro) -> dde

871
01:07:24,010 --> 01:07:29,250
arall dros dro = & (* dros dro) -> chwith.

872
01:07:29,250 --> 01:07:32,730
Ac yn awr, yn y fan hon, ar ôl y ddolen tra,

873
01:07:32,730 --> 01:07:36,380
Dim ond gwneud hyn oherwydd efallai ei fod yn haws i feddwl am iteraidd na recursively,

874
01:07:36,380 --> 01:07:39,010
ond ar ôl hyn dolen tra,

875
01:07:39,010 --> 01:07:43,820
* Dros dro yn y pwyntydd yr ydym am ei newid.

876
01:07:43,820 --> 01:07:48,960
>> Cyn i ni gael rhiant, ac rydym yn awyddus i newid chwith rhiant naill neu'r rhiant hawl,

877
01:07:48,960 --> 01:07:51,310
ond os ydym am newid i'r dde rhiant,

878
01:07:51,310 --> 01:07:54,550
yna * dros dro yn iawn rhiant, a gallwn ei newid yn uniongyrchol.

879
01:07:54,550 --> 01:08:05,860
Felly i lawr yma, y ​​gallwn ei wneud dros dro * = newnode, a dyna ni.

880
01:08:05,860 --> 01:08:09,540
Felly rhybudd, y cyfan a wnaethom yn hyn yn cymryd allan linellau o god.

881
01:08:09,540 --> 01:08:14,770
Er mwyn cadw golwg ar y rhiant ym mhopeth sydd yn ymdrech ychwanegol.

882
01:08:14,770 --> 01:08:18,689
Yma, os ydym yn unig yn cadw golwg ar y pwyntydd i'r pwyntydd,

883
01:08:18,689 --> 01:08:22,990
a hyd yn oed os ydym am gael gwared o'r holl braces cyrliog yn awr,

884
01:08:22,990 --> 01:08:27,170
gwneud iddo edrych yn fyrrach.

885
01:08:27,170 --> 01:08:32,529
Mae hyn yn awr yw un ateb yn union,

886
01:08:32,529 --> 01:08:38,210
ond llinellau llai o god.

887
01:08:38,210 --> 01:08:41,229
Pan fyddwch yn dechrau cydnabod hyn fel ateb dilys,

888
01:08:41,229 --> 01:08:43,529
mae hefyd yn haws i resymu am na tebyg, iawn,

889
01:08:43,529 --> 01:08:45,779
pam ydw i'n cael y faner ar y dde int?

890
01:08:45,779 --> 01:08:49,290
Beth mae hynny'n ei olygu? O, mae'n dynodi ei

891
01:08:49,290 --> 01:08:51,370
bob tro rwy'n mynd yn iawn, mae angen i mi ei osod,

892
01:08:51,370 --> 01:08:53,819
arall os byddaf yn mynd ar ôl rhaid i mi osod i sero.

893
01:08:53,819 --> 01:09:04,060
Yma, nid oes gennyf reswm i am hynny; mae'n haws i feddwl amdano.

894
01:09:04,060 --> 01:09:06,710
Cwestiynau?

895
01:09:06,710 --> 01:09:16,290
[Myfyrwyr, annealladwy] >> Yeah.

896
01:09:16,290 --> 01:09:23,359
Iawn, felly yn y rhan olaf -

897
01:09:23,359 --> 01:09:28,080
Amcana un swyddogaeth cyflym a hawdd y gallwn ni ei wneud yw,

898
01:09:28,080 --> 01:09:34,910
let's - gyda'n gilydd, mae'n debyg, ceisiwch ysgrifennu yn cynnwys swyddogaeth

899
01:09:34,910 --> 01:09:38,899
nad yw'n gofalu a yw'n goeden chwiliad deuaidd.

900
01:09:38,899 --> 01:09:43,770
Mae hyn yn cynnwys y dylai swyddogaeth ddychwelyd wir

901
01:09:43,770 --> 01:09:58,330
os unrhyw le yn y goeden ddeuaidd cyffredinol yw gwerth rydym yn chwilio am.

902
01:09:58,330 --> 01:10:02,520
Felly, gadewch i ni cyntaf sydd ei recursively ac yna byddwn yn gwneud hynny iteraidd.

903
01:10:02,520 --> 01:10:07,300
Gallwn mewn gwirionedd dim ond ei wneud gyda'n gilydd, gan fod hyn yn mynd i fod yn brin iawn.

904
01:10:07,300 --> 01:10:11,510
>> Beth yw fy achos sylfaenol yn mynd i fod?

905
01:10:11,510 --> 01:10:13,890
[Myfyrwyr, annealladwy]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Felly os (coeden == NULL), yna beth?

907
01:10:18,230 --> 01:10:22,740
[Myfyrwyr] Dychwelyd ffug.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, wel, dwi ddim yn angen y arall.

909
01:10:26,160 --> 01:10:30,250
Os oedd fy achos sylfaenol eraill.

910
01:10:30,250 --> 01:10:32,450
[Myfyrwyr] Coed yn werth? >> Yeah.

911
01:10:32,450 --> 01:10:36,430
Felly os (gwerth == coed> werth.

912
01:10:36,430 --> 01:10:39,920
Hysbysiad rydym yn ôl i beidio â * nod, nod ** s?

913
01:10:39,920 --> 01:10:42,990
Ni fydd Yn cynnwys angen i chi ddefnyddio ** nod,

914
01:10:42,990 --> 01:10:45,480
gan nad ydym yn addasu awgrymiadau.

915
01:10:45,480 --> 01:10:50,540
Rydym yn unig yn croesi nhw.

916
01:10:50,540 --> 01:10:53,830
Os bydd hynny'n digwydd, yna rydym eisiau dychwelyd yn wir.

917
01:10:53,830 --> 01:10:58,270
Arall rydym am i groesi'r plant.

918
01:10:58,270 --> 01:11:02,620
Felly, ni allwn resymu ynghylch a phopeth ar y chwith yn llai

919
01:11:02,620 --> 01:11:05,390
a phopeth ar y dde yn fwy.

920
01:11:05,390 --> 01:11:09,590
Felly beth yw ein cyflwr yn mynd i fod yma - neu, beth ydyn ni'n mynd i'w wneud?

921
01:11:09,590 --> 01:11:11,840
[Myfyrwyr, annealladwy] >> Yeah.

922
01:11:11,840 --> 01:11:17,400
Dychwelyd yn cynnwys (gwerth, coed-> chwith)

923
01:11:17,400 --> 01:11:26,860
neu'n cynnwys (gwerth, coed-> dde). A dyna ni.

924
01:11:26,860 --> 01:11:29,080
Ac yn sylwi bod peth gwerthuso byr-cylched,

925
01:11:29,080 --> 01:11:32,520
lle os ydym yn digwydd i ddod o hyd i'r gwerth yn y goeden ar y chwith,

926
01:11:32,520 --> 01:11:36,820
ni byth angen i edrych ar y goeden gywir.

927
01:11:36,820 --> 01:11:40,430
Dyna y swyddogaeth gyfan.

928
01:11:40,430 --> 01:11:43,690
Nawr, gadewch i ni ei wneud iteraidd,

929
01:11:43,690 --> 01:11:48,060
sydd yn mynd i fod yn llai 'n glws.

930
01:11:48,060 --> 01:11:54,750
Byddwn yn cymryd y cychwyn arferol o cyf nod * = goeden.

931
01:11:54,750 --> 01:12:03,250
Er (cyf! = NULL).

932
01:12:03,250 --> 01:12:08,600
Yn gyflym yn mynd i weld problem.

933
01:12:08,600 --> 01:12:12,250
Os cyf - allan yma, os ydym byth yn dorri allan o hyn,

934
01:12:12,250 --> 01:12:16,020
yna rydym ni wedi rhedeg allan o bethau i edrych arnynt, felly dychwelyd ffug.

935
01:12:16,020 --> 01:12:24,810
Os (cyf-> == gwerth gwerth), yn dychwelyd yn wir.

936
01:12:24,810 --> 01:12:32,910
Felly nawr, rydym wedi cyrraedd lle -

937
01:12:32,910 --> 01:12:36,250
nid ydym yn gwybod a ydym am fynd i'r chwith neu i'r dde.

938
01:12:36,250 --> 01:12:44,590
Felly fympwyol, gadewch i ni dim ond yn mynd i'r chwith.

939
01:12:44,590 --> 01:12:47,910
Rydw i wedi rhedeg yn amlwg i fater lle dwi 'di gadael yn llwyr bopeth -

940
01:12:47,910 --> 01:12:50,760
Byddaf ond yn edrych ar yr ochr chwith y goeden.

941
01:12:50,760 --> 01:12:56,050
Ni fyddaf byth yn gwirio unrhyw beth sydd yn blentyn hawl i unrhyw beth.

942
01:12:56,050 --> 01:13:00,910
Sut ydw i'n atgyweiria hon?

943
01:13:00,910 --> 01:13:05,260
[Myfyrwyr] Mae'n rhaid i chi gadw golwg ar y chwith a'r dde mewn pentwr.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Felly, gadewch i ni ei gwneud yn

945
01:13:13,710 --> 01:13:32,360
strwythur rhestr, nod * n, ac yna nod ** nesaf?

946
01:13:32,360 --> 01:13:40,240
Credaf fod yn gweithio iawn.

947
01:13:40,240 --> 01:13:45,940
Rydym yn awyddus i fynd dros y chwith, neu let's - hyd yma.

948
01:13:45,940 --> 01:13:54,350
Strwythur = rhestr rhestr, bydd yn dechrau

949
01:13:54,350 --> 01:13:58,170
allan ar y rhestr hon strwythur.

950
01:13:58,170 --> 01:14:04,040
* Rhestr = null. Felly, mae hynny'n mynd i fod yn rhestr cysylltiedig

951
01:14:04,040 --> 01:14:08,430
o subtrees yr ydym wedi hepgor drosodd.

952
01:14:08,430 --> 01:14:13,800
Rydym yn mynd i deithio ar draws i'r chwith yn awr,

953
01:14:13,800 --> 01:14:17,870
ond gan ein bod yn anochel angen i ni ddod yn ôl i'r dde,

954
01:14:17,870 --> 01:14:26,140
Rydym yn mynd i gadw'r ochr dde y tu mewn i strwythur ein rhestr.

955
01:14:26,140 --> 01:14:32,620
Yna, bydd gennym new_list neu strwythur,

956
01:14:32,620 --> 01:14:41,080
strwythur rhestr *, new_list = malloc (sizeof (rhestr)).

957
01:14:41,080 --> 01:14:44,920
Rydw i'n mynd i anwybyddu gwall-wirio hynny, ond dylech edrych i weld os yw'n null.

958
01:14:44,920 --> 01:14:50,540
New_list y nod, mae'n mynd i gyfeirio at -

959
01:14:50,540 --> 01:14:56,890
oh, dyna pam yr wyf am i fyny yma. Mae'n mynd i gyfeirio at restr strwythur arall.

960
01:14:56,890 --> 01:15:02,380
Dyna pa mor cysylltiedig rhestrau gwaith.

961
01:15:02,380 --> 01:15:04,810
Mae hyn yr un fath fel rhestr int cysylltiedig

962
01:15:04,810 --> 01:15:06,960
ac eithrio ni jyst yn disodli int gyda * nod.

963
01:15:06,960 --> 01:15:11,040
Mae'n union yr un fath.

964
01:15:11,040 --> 01:15:15,100
Felly new_list, gwerth ein nod new_list,

965
01:15:15,100 --> 01:15:19,120
yn mynd i fod yn cyf-> dde.

966
01:15:19,120 --> 01:15:24,280
Mae gwerth ein new_list-> nesaf yn mynd i fod yn ein rhestr wreiddiol,

967
01:15:24,280 --> 01:15:30,760
ac yna rydym yn mynd i ddiweddaru ein rhestr i gyfeirio at new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nawr rydym angen rhyw fath o ffordd o bethau tynnu,

969
01:15:33,650 --> 01:15:37,020
fel yr ydym wedi croesi'r Terfynau Chwilio cyfan chwith.

970
01:15:37,020 --> 01:15:40,480
Nawr mae angen i ni dynnu pethau allan ohono,

971
01:15:40,480 --> 01:15:43,850
fel cyf yn null, nid ydym am i ddim ond dychwelyd ffug.

972
01:15:43,850 --> 01:15:50,370
Rydym yn awyddus i dynnu y tu allan yn awr ar ein rhestr newydd.

973
01:15:50,370 --> 01:15:53,690
Ffordd gyfleus o wneud hyn - wel, mewn gwirionedd, mae nifer o ffyrdd o wneud hyn.

974
01:15:53,690 --> 01:15:56,680
Dylai unrhyw un gennych awgrym?

975
01:15:56,680 --> 01:15:58,790
Ble ddylwn i ei wneud hyn neu sut y dylwn wneud hyn?

976
01:15:58,790 --> 01:16:08,010
Dim ond cwpl o funudau, ond bydd unrhyw awgrymiadau?

977
01:16:08,010 --> 01:16:14,750
Yn hytrach na - un ffordd, yn hytrach na bod yn ein cyflwr tra,

978
01:16:14,750 --> 01:16:17,090
nid yr hyn rydym yn hyn o bryd yn edrych arno yw null,

979
01:16:17,090 --> 01:16:22,340
yn lle hynny rydym ni'n mynd i barhau i fynd hyd nes ein rhestr ei hun yn null.

980
01:16:22,340 --> 01:16:25,680
Felly, os yw ein rhestr yn dod i ben i fyny fod yn null,

981
01:16:25,680 --> 01:16:30,680
hynny rydym wedi rhedeg allan o bethau i chwilio am, i chwilio drosodd.

982
01:16:30,680 --> 01:16:39,860
Ond mae hynny'n golygu mai'r peth cyntaf yn ein rhestr yn unig yn mynd i fod y nod cyntaf.

983
01:16:39,860 --> 01:16:49,730
Bydd Y peth cyntaf fod - ni nid oes angen i weld hynny.

984
01:16:49,730 --> 01:16:58,710
Felly rhestr-> Bydd n fydd ein coeden.

985
01:16:58,710 --> 01:17:02,860
rhestr-> nesaf yn mynd i fod yn null.

986
01:17:02,860 --> 01:17:07,580
Ac yn awr er nad rhestr yn null cyfartal.

987
01:17:07,580 --> 01:17:11,610
Cyf yn mynd i dynnu rhywbeth oddi ar ein rhestr.

988
01:17:11,610 --> 01:17:13,500
Felly cyf yn mynd i'r rhestr-> gyfartal n.

989
01:17:13,500 --> 01:17:20,850
Ac yna rhestr yn mynd i'r rhestr-> gyfartal n, neu restr-> nesaf.

990
01:17:20,850 --> 01:17:23,480
Felly gwerth cyf os yn dychwelyd gwerth.

991
01:17:23,480 --> 01:17:28,790
Nawr gallwn ychwanegu y ddau ein pwyntydd iawn ac mae ein pwyntydd ar y chwith

992
01:17:28,790 --> 01:17:32,900
cyn belled nad ydynt yn null.

993
01:17:32,900 --> 01:17:36,390
Down yma, mae'n debyg y dylem fod wedi gwneud hynny yn y lle cyntaf.

994
01:17:36,390 --> 01:17:44,080
Os (cyf-> iawn! = NULL)

995
01:17:44,080 --> 01:17:56,380
yna rydym yn mynd i osod y nod yn ein rhestr.

996
01:17:56,380 --> 01:17:59,290
Os (cyf-> chwith), mae hyn yn ychydig o waith ychwanegol, ond mae'n iawn.

997
01:17:59,290 --> 01:18:02,690
Os (cyf-> chwith! = NULL),

998
01:18:02,690 --> 01:18:14,310
ac rydym yn mynd i fewnosod y chwith i mewn i'n rhestr cysylltiedig,

999
01:18:14,310 --> 01:18:19,700
a dylai hynny fod yn.

1000
01:18:19,700 --> 01:18:22,670
Rydym yn ailadrodd - cyn belled ag y byddwn wedi rhywbeth yn ein rhestr,

1001
01:18:22,670 --> 01:18:26,640
mae gennym nod arall i edrych ar.

1002
01:18:26,640 --> 01:18:28,920
Felly, rydym yn edrych ar y nod,

1003
01:18:28,920 --> 01:18:31,390
rydym yn datblygu ein rhestr i'r un nesaf.

1004
01:18:31,390 --> 01:18:34,060
Os yw'r nod yn y gwerth yr ydym yn chwilio amdano, gallwn ddychwelyd yn wir.

1005
01:18:34,060 --> 01:18:37,640
Arall rhowch ddau subtrees y chwith a dde,

1006
01:18:37,640 --> 01:18:40,510
cyn belled nad ydynt yn null, yn ein rhestr

1007
01:18:40,510 --> 01:18:43,120
fel ein bod yn anochel yn mynd drostynt.

1008
01:18:43,120 --> 01:18:45,160
Felly, os nad oeddent yn null,

1009
01:18:45,160 --> 01:18:47,950
os yw ein pwyntydd gwreiddiau tynnu sylw at ddau beth,

1010
01:18:47,950 --> 01:18:51,670
yna ar y dechrau rydym yn tynnu rhywbeth allan felly mae ein rhestr yn dod i ben i fyny fod yn null.

1011
01:18:51,670 --> 01:18:56,890
Ac yna rydym yn rhoi dau beth yn ôl, felly, yn awr ein rhestr o faint 2.

1012
01:18:56,890 --> 01:19:00,030
Yna rydym yn mynd i dolen yn ôl i fyny ac rydym yn jyst yn mynd i dynnu,

1013
01:19:00,030 --> 01:19:04,250
gadewch i ni ddweud, y pwyntydd chwith ein nod gwraidd.

1014
01:19:04,250 --> 01:19:07,730
A bydd mai dim ond cadw digwydd; byddwn yn y pen draw dolennu dros bopeth.

1015
01:19:07,730 --> 01:19:11,280
>> Sylwch fod hyn yn llawer mwy cymhleth

1016
01:19:11,280 --> 01:19:14,160
yn yr ateb ailadroddus.

1017
01:19:14,160 --> 01:19:17,260
Ac yr wyf wedi dweud sawl gwaith

1018
01:19:17,260 --> 01:19:25,120
fod yr ateb recursive fel arfer yn lawer yn gyffredin â'r ailadroddol ateb.

1019
01:19:25,120 --> 01:19:30,820
Yma, mae hyn yn union beth yw'r ateb ailadroddus yn ei wneud.

1020
01:19:30,820 --> 01:19:36,740
Yr unig newid yw, yn lle ymhlyg defnyddio'r corn, y pentwr rhaglen,

1021
01:19:36,740 --> 01:19:40,840
fel eich ffordd o gadw golwg ar yr hyn nodau angen i chi ymweld â nhw,

1022
01:19:40,840 --> 01:19:45,430
nawr mae'n rhaid i chi yn benodol defnyddio rhestr cysylltiedig.

1023
01:19:45,430 --> 01:19:49,070
Yn y ddau achos eich bod yn cadw golwg ar yr hyn nod dal i fod angen ymweld â hwy.

1024
01:19:49,070 --> 01:19:51,790
Yn yr achos recursive mae'n haws oherwydd bod pentwr

1025
01:19:51,790 --> 01:19:57,100
yn cael ei weithredu i chi fel y pentwr rhaglen.

1026
01:19:57,100 --> 01:19:59,550
Sylwch fod y rhestr hon yn gysylltiedig, mae'n pentwr.

1027
01:19:59,550 --> 01:20:01,580
Beth bynnag rydym yn unig ei roi ar y corn

1028
01:20:01,580 --> 01:20:09,960
yn union beth yr ydym yn mynd i dynnu oddi ar y pentwr i ymweld nesaf.

1029
01:20:09,960 --> 01:20:14,380
Rydym yn allan o amser, ond bydd unrhyw gwestiynau?

1030
01:20:14,380 --> 01:20:23,530
[Myfyrwyr, annealladwy]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Felly, os ydym wedi ein rhestr cysylltiedig,

1032
01:20:27,790 --> 01:20:30,150
ar hyn o bryd yn mynd i gyfeirio at y boi,

1033
01:20:30,150 --> 01:20:34,690
ac yn awr rydym yn unig yn hyrwyddo ein rhestr cysylltiedig i ganolbwyntio ar y dyn.

1034
01:20:34,690 --> 01:20:44,200
Rydym yn croesi dros y rhestr cysylltiedig yn y llinell honno.

1035
01:20:44,200 --> 01:20:51,200
Ac yna mae'n debyg y dylem ryddhau ein rhestr cysylltiedig a phethau

1036
01:20:51,200 --> 01:20:53,880
unwaith cyn dychwelyd yn wir neu'n anwir, mae angen i ni

1037
01:20:53,880 --> 01:20:57,360
ailadrodd dros ein rhestr gysylltiedig a bob amser i lawr yma, mi dybiaf,

1038
01:20:57,360 --> 01:21:03,900
os ydym yn cyf ddim yn iawn yn hafal i, ychwanegu, felly nawr rydym am i ryddhau

1039
01:21:03,900 --> 01:21:09,600
cyf oherwydd, wel, wnaethon ni llwyr anghofio am y rhestr? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Felly dyna beth rydym eisiau ei wneud yma.

1041
01:21:12,880 --> 01:21:16,730
Ble mae'r pwyntydd?

1042
01:21:16,730 --> 01:21:23,320
Cyf oedd ar y pryd - rydym am i restr strwythur * 10 yn dychwelyd rhestr nesaf.

1043
01:21:23,320 --> 01:21:29,240
Rhestr am ddim, rhestr = temp.

1044
01:21:29,240 --> 01:21:32,820
Ac yn yr achos lle byddwn yn dychwelyd wir, mae angen i ailadrodd

1045
01:21:32,820 --> 01:21:37,050
dros y gweddill ein rhestr cysylltiedig rhyddhau pethau.

1046
01:21:37,050 --> 01:21:39,700
Y peth braf am yr ateb recursive yn rhyddhau pethau

1047
01:21:39,700 --> 01:21:44,930
yn unig yn golygu factorings popping oddi ar y pentwr a fydd yn digwydd i chi.

1048
01:21:44,930 --> 01:21:50,720
Felly, rydym wedi mynd o rywbeth sy'n debyg 3 llinellau o anodd-i-feddwl-am god

1049
01:21:50,720 --> 01:21:57,520
i rywbeth sydd dipyn llawer mwy anodd-i-feddwl-am linellau o god.

1050
01:21:57,520 --> 01:22:00,620
Unrhyw mwy o gwestiynau?

1051
01:22:00,620 --> 01:22:08,760
Mae pob hawl. Rydym yn dda. Hwyl!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]