1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [7 skirsnis: patogesnė]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvardo universiteto]

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

4
00:00:07,930 --> 00:00:10,110
Gerai. Taigi, kaip sakiau mano elektroninio pašto adresą,

5
00:00:10,110 --> 00:00:14,060
tai bus dvejetainis medis intensyviai dalis.

6
00:00:14,060 --> 00:00:16,820
Bet ten nėra, kad daug klausimų.

7
00:00:16,820 --> 00:00:18,920
Taigi, mes ketiname išbandyti ir atkreipti dėmesį į kiekvieną klausimą

8
00:00:18,920 --> 00:00:25,430
ir eiti į skausminga išsamiai visų geriausių būdų, kaip daryti dalykus.

9
00:00:25,430 --> 00:00:31,200
Taigi pačioje pradžioje, mes einame, per imčių brėžinius dvejetainiai medžiai ir kita.

10
00:00:31,200 --> 00:00:35,970
Taigi čia, "Atminkite, kad dvejetainis medis mazgus, panašias į susietą sąrašą,

11
00:00:35,970 --> 00:00:38,150
išskyrus vietoj vieno rodyklė yra du: vienas kairėje "vaiko"

12
00:00:38,150 --> 00:00:41,950
ir vienas dešinėje "vaiko". "

13
00:00:41,950 --> 00:00:45,630
Taigi dvejetainis medis yra kaip susietą sąrašą,

14
00:00:45,630 --> 00:00:47,910
išskyrus struct turi dvi rodykles.

15
00:00:47,910 --> 00:00:51,390
Yra Trójkowy medžiai, kurie ketina turėti tris patarimų,

16
00:00:51,390 --> 00:00:56,540
yra N-Arnhem medžiai, kuri tiesiog bendrinis žymeklį

17
00:00:56,540 --> 00:01:00,320
kad tada jūs turite malloc būti pakankamai didelis, kad

18
00:01:00,320 --> 00:01:04,840
pakankamai pabrėžiamas visų galimų vaikų.

19
00:01:04,840 --> 00:01:08,200
Taigi, dvejetainis medis, tiesiog taip atsitinka, turėti pastovų skaičių dviejų.

20
00:01:08,200 --> 00:01:11,260
Jei norite, galite duoti kaip Smūginės medžio susietą sąrašą,

21
00:01:11,260 --> 00:01:15,360
bet aš nemanau, kad kas vadina tai, kad.

22
00:01:15,360 --> 00:01:18,060
"Nupiešk dėžės ir rodykles dvejetainis medis mazgas schema

23
00:01:18,060 --> 00:01:24,110
su Nate mėgstamą skaičių, 7, kur kiekvienas vaikas žymeklis yra niekinis. "

24
00:01:24,110 --> 00:01:27,780
Taigi, iPad režimas.

25
00:01:27,780 --> 00:01:30,280
>> Tai bus gana paprasta.

26
00:01:30,280 --> 00:01:36,150
Mes tiesiog teks mazgas, aš padaryti tai kaip kvadratas.

27
00:01:36,150 --> 00:01:38,730
Ir aš padaryti vertybes čia.

28
00:01:38,730 --> 00:01:41,090
Taigi ši vertė bus eiti čia,

29
00:01:41,090 --> 00:01:44,770
ir tada žemyn čia mes į kairę rodyklę kairėje ir teisę rodyklę dešinėje.

30
00:01:44,770 --> 00:01:50,430
Ir tai yra labai daug, todėl konvencija skambinti į kairę ir į dešinę, žymeklis pavadinimai.

31
00:01:50,430 --> 00:01:52,460
Abi šios priemonės yra bus niekinis.

32
00:01:52,460 --> 00:01:57,870
, Kad bus tiesiog nulis, ir kad bus tiesiog yra niekinis.

33
00:01:57,870 --> 00:02:03,630
Gerai. Taigi atgal čia.

34
00:02:03,630 --> 00:02:05,700
"Su susietą sąrašą, mes tik turėjo laikyti žymeklį

35
00:02:05,700 --> 00:02:09,639
į pirmąjį sąrašą, kad būtų prisiminti visą susietą sąrašą, arba visą sąrašą mazgas.

36
00:02:09,639 --> 00:02:11,650
Be to, su medžiais, mes tik laikyti žymeklį

37
00:02:11,650 --> 00:02:13,420
į vieną mazgą, siekiant prisiminti visą medį.

38
00:02:13,420 --> 00:02:15,980
Šis mazgas yra Calle "root" iš medžio.

39
00:02:15,980 --> 00:02:18,320
Remtis diagramos prieš arba parengti naują

40
00:02:18,320 --> 00:02:21,690
toks, kad turite dėžės ir rodykles vaizdavimas dvejetainis medis

41
00:02:21,690 --> 00:02:25,730
vertė 7, tada kairėje 3

42
00:02:25,730 --> 00:02:32,760
9 Tada dešinėje, o tada 6 nuo 3 teise. "

43
00:02:32,760 --> 00:02:34,810
Leiskite pamatyti, jei aš galiu prisiminti visa tai, mano galva.

44
00:02:34,810 --> 00:02:37,670
Taigi, tai bus mūsų šaknis čia.

45
00:02:37,670 --> 00:02:41,600
Mes turime šiek tiek žymeklį kažkur, kažkas, kad mes vadiname šaknį,

46
00:02:41,600 --> 00:02:45,140
ir ji nukreipta šis vaikinas.

47
00:02:45,140 --> 00:02:48,490
Dabar, kad naują mazgas,

48
00:02:48,490 --> 00:02:52,870
Ką turime 3 kairėje?

49
00:02:52,870 --> 00:02:57,140
Taigi, naujas mazgas su 3, ir ji iš pradžių nurodo null.

50
00:02:57,140 --> 00:02:59,190
Aš tiesiog įdėti N.

51
00:02:59,190 --> 00:03:02,250
Dabar mes norime padaryti, kad eiti į kairę nuo 7.

52
00:03:02,250 --> 00:03:06,840
Taigi, mes pakeisti šį žymiklį į dabar šis vaikinas.

53
00:03:06,840 --> 00:03:12,420
Ir mes darome tą patį. Mes norime, kad 9 Over Here

54
00:03:12,420 --> 00:03:14,620
, kuri iš pradžių tiesiog sako null.

55
00:03:14,620 --> 00:03:19,600
Mes ketiname pakeisti šią rodyklę, nurodykite 9,

56
00:03:19,600 --> 00:03:23,310
ir dabar mes norime įdėti 6 į dešinę iš 3.

57
00:03:23,310 --> 00:03:32,170
Taigi jis ketina padaryti 6.

58
00:03:32,170 --> 00:03:34,310
Ir kad vaikinas bus nurodyti kryptį.

59
00:03:34,310 --> 00:03:38,320
Gerai. Taip, kad visa tai prašo mūsų padaryti.

60
00:03:38,320 --> 00:03:42,770
>> Dabar eikime per kai terminologija.

61
00:03:42,770 --> 00:03:46,690
Mes jau kalbėjome apie tai, kaip iš medžio šaknys yra iš viršaus labiausiai medžio mazgas.

62
00:03:46,690 --> 00:03:54,720
Vienas yra 7. "Iš medžio apačioje centrai yra vadinami lapai.

63
00:03:54,720 --> 00:04:01,240
Kiekvienas mazgas, kuris tiesiog yra niekinis, kaip savo vaikų lapų.

64
00:04:01,240 --> 00:04:03,680
Taigi tai yra įmanoma, jei mūsų dvejetainis medis yra tik vienas mazgas,

65
00:04:03,680 --> 00:04:10,130
kad medis yra lapas, ir viskas.

66
00:04:10,130 --> 00:04:12,060
"Iš medžio" aukštis "yra apynių, jūs turite padaryti

67
00:04:12,060 --> 00:04:16,620
gauti iš viršaus į lapo pusėje. "

68
00:04:16,620 --> 00:04:18,640
Mes susisieksime per sekundę, skirtumą

69
00:04:18,640 --> 00:04:21,940
tarp subalansuotas ir nesubalansuoto dvejetainiai medžiai,

70
00:04:21,940 --> 00:04:29,470
bet dabar, bendras aukštis šio medžio

71
00:04:29,470 --> 00:04:34,520
Sakyčiau, yra 3, nors jei skaičiuoti apynių

72
00:04:34,520 --> 00:04:39,710
jūs turite padaryti, siekiant gauti iki 9, tada tai tikrai tik aukštis 2.

73
00:04:39,710 --> 00:04:43,340
Dabar tai yra nesubalansuotas dvejetainis medis,

74
00:04:43,340 --> 00:04:49,840
bet mes kalbėjome apie subalansuota, kai ji gali būti aktuali.

75
00:04:49,840 --> 00:04:52,040
Taigi dabar mes galime kalbėti apie medžio mazgų požiūriu

76
00:04:52,040 --> 00:04:54,700
, palyginti su kitų mazgų medyje.

77
00:04:54,700 --> 00:04:59,730
Taigi dabar mes turime tėvai, vaikai, broliai, seserys, protėviai, ir palikuonių.

78
00:04:59,730 --> 00:05:05,650
Jie yra gana sveiku protu, ką jie reiškia.

79
00:05:05,650 --> 00:05:09,610
Jei mes klausiame - tai tėvus.

80
00:05:09,610 --> 00:05:12,830
Taigi, kas yra 3 tėvų?

81
00:05:12,830 --> 00:05:16,090
[Studentai] 7. >> Taip. Patronuojanti įmonė yra tiesiog bus, kas rodo jums.

82
00:05:16,090 --> 00:05:20,510
Tai kas yra 7 vaikai?

83
00:05:20,510 --> 00:05:23,860
[Studentai] 3 ir 9. >> Taip.

84
00:05:23,860 --> 00:05:26,460
Atkreipkite dėmesį, kad "vaikai" tiesiog reiškia, kad vaikai,

85
00:05:26,460 --> 00:05:31,010
taip 6 negalėjo būti taikoma, nes jis kaip anūkas.

86
00:05:31,010 --> 00:05:35,540
Bet tada, jei mes einame palikuonis, todėl tai, ką yra 7 palikuonys?

87
00:05:35,540 --> 00:05:37,500
[Studentai] 3, 6 ir 9. >> Taip.

88
00:05:37,500 --> 00:05:42,330
Šakninis mazgas palikuonys bus viskas į medį,

89
00:05:42,330 --> 00:05:47,950
išskyrus gal pati šakninis mazgas, jei nenorite manyti, kad palikuonis.

90
00:05:47,950 --> 00:05:50,750
Ir, pagaliau, protėviai, todėl priešinga kryptimi.

91
00:05:50,750 --> 00:05:55,740
Taigi, kas yra 6 protėviai?

92
00:05:55,740 --> 00:05:58,920
[Studentai] 3 ir 7. >> Taip. 9 neįskaičiuoti.

93
00:05:58,920 --> 00:06:02,520
Tai tiesiog tiesioginė sąsaja atgal į šaknis

94
00:06:02,520 --> 00:06:13,230
bus jūsų protėviai.

95
00:06:13,230 --> 00:06:16,300
>> "Mes sakome, kad dvejetainis medis" užsakė ", jei už kiekvieno medžio mazgas,

96
00:06:16,300 --> 00:06:19,530
visų savo palikuonių kairėje turi mažiau vertybes

97
00:06:19,530 --> 00:06:22,890
ir teise, turi didesnės reikšmės.

98
00:06:22,890 --> 00:06:27,060
Pavyzdžiui, aukščiau medis užsisakyti bet tai nėra vienintelis galimas tvarkingas.

99
00:06:27,060 --> 00:06:30,180
Prieš mes į, kad,

100
00:06:30,180 --> 00:06:36,420
užsisakyti dvejetainis medis, taip pat žinomas kaip dvejetainis paieškos medis.

101
00:06:36,420 --> 00:06:38,660
Čia mes atsitiktų būti vadiname tai tvarkingas dvejetainis medis,

102
00:06:38,660 --> 00:06:41,850
bet aš niekada girdėjote jis vadinamas užsisakyti dvejetainis medis, prieš,

103
00:06:41,850 --> 00:06:46,650
ir viktorinos yra daug labiau tikėtina, įdėti dvejetainis paieškos medis.

104
00:06:46,650 --> 00:06:49,250
Jie vienas ir tas pats,

105
00:06:49,250 --> 00:06:54,580
ir labai svarbu, jums atpažinti skirtumą tarp dvejetainis medis ir dvejetainis paieškos medis.

106
00:06:54,580 --> 00:06:58,830
Dvejetainis medis yra tik medis, kad atkreipia dėmesį į du dalykus.

107
00:06:58,830 --> 00:07:02,120
Kiekvienas mazgas atkreipia dėmesį į du dalykus.

108
00:07:02,120 --> 00:07:06,310
Yra ne apie vertybes, ji pažymi, kad motyvai.

109
00:07:06,310 --> 00:07:11,370
Taigi, kaip čia, nes tai dvejetainis paieškos medis,

110
00:07:11,370 --> 00:07:14,030
mes žinome, kad, jei mes einame į kairę nuo 7,

111
00:07:14,030 --> 00:07:16,670
tada visi vertybių, kurį galime pasiekti

112
00:07:16,670 --> 00:07:19,310
eidami liko iš 7 turi būti mažiau nei 7.

113
00:07:19,310 --> 00:07:24,070
Atkreipkite dėmesį, kad visos vertybės yra mažiau kaip 7 3 ir 6.

114
00:07:24,070 --> 00:07:26,040
Visi tie, kurie į kairę nuo 7.

115
00:07:26,040 --> 00:07:29,020
Jei mes einame į dešinę nuo 7, viskas turi būti didesnis kaip 7,

116
00:07:29,020 --> 00:07:33,220
taip 9 yra į dešinę nuo 7, todėl mes geri.

117
00:07:33,220 --> 00:07:36,150
Tai ne dvejetainis medis,

118
00:07:36,150 --> 00:07:40,020
reguliariai dvejetainis medis, mes galime tik 3 viršuje, 7 į kairę,

119
00:07:40,020 --> 00:07:47,630
Nuo 9 iki 7 kairėje; nėra užsisakyti vertybių bebūtų.

120
00:07:47,630 --> 00:07:56,140
Dabar, mes ne iš tikrųjų, nes tai varginantis ir nereikalingas,

121
00:07:56,140 --> 00:07:59,400
bet "stengiasi padaryti su daug užsakytas medžių, kaip jūs galite galvoti

122
00:07:59,400 --> 00:08:01,900
skaičius 7, 3, 9 ir 6.

123
00:08:01,900 --> 00:08:06,800
Kiek skirtingų tvarka yra? Kas yra kiekvienam iš jų aukštis? "

124
00:08:06,800 --> 00:08:10,480
>> Mes padarysime pora, bet pagrindinė idėja yra,

125
00:08:10,480 --> 00:08:16,530
tai jokiu būdu unikalus atstovavimas dvejetainis medis, kurio sudėtyje yra šių vertybių.

126
00:08:16,530 --> 00:08:22,760
Visi mes turime, yra kai dvejetainis medis, kuris yra 7, 3, 6, ir 9.

127
00:08:22,760 --> 00:08:25,960
Kitas galimas galioja vienerius būtų šaknis yra 3,

128
00:08:25,960 --> 00:08:30,260
eiti į kairę ir tai 6, eikite į kairę ir tai 7,

129
00:08:30,260 --> 00:08:32,730
eiti į kairę ir tai 9.

130
00:08:32,730 --> 00:08:36,169
, Kuri yra puikiai tinka dvejetainis paieškos medis.

131
00:08:36,169 --> 00:08:39,570
Tai nėra labai naudingi, nes tai tiesiog kaip susietą sąrašą

132
00:08:39,570 --> 00:08:43,750
ir visi šių rodykles yra tiesiog niekinis.

133
00:08:43,750 --> 00:08:48,900
Bet tai galioja medis. Taip?

134
00:08:48,900 --> 00:08:51,310
[Studentų] Ar vertybės turi būti didesnis dešinėje?

135
00:08:51,310 --> 00:08:56,700
Ar tai? >> Tai reiškė eiti į kitą pusę.

136
00:08:56,700 --> 00:09:00,960
Yra taip pat - Taip, galime pereiti, kad.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Geras laimikis.

138
00:09:07,770 --> 00:09:11,730
Jis vis dar turi klausyti, ką dvejetainis medis paiešką turėtų daryti.

139
00:09:11,730 --> 00:09:15,650
Taigi viskas į kairę turi būti mažesnis, nei bet kuriuo mazgo.

140
00:09:15,650 --> 00:09:23,180
Mes galime tiesiog perkelti, tarkim, šį 6 ir įdėti jį čia.

141
00:09:23,180 --> 00:09:26,880
Ne, mes negalime. Kodėl aš nuolat tai daro?

142
00:09:26,880 --> 00:09:35,350
Darom - čia yra 6, čia yra 7, 6 taškai 3.

143
00:09:35,350 --> 00:09:39,290
Tai vis dar galioja dvejetainis paieškos medis.

144
00:09:39,290 --> 00:09:49,260
Kas yra negerai, jei aš - galime pamatyti, jei aš gali sugalvoti susitarimą.

145
00:09:49,260 --> 00:09:52,280
Taip, gerai. Taigi, kas yra negerai su šio medžio?

146
00:09:52,280 --> 00:10:08,920
Manau, aš jau davė jums užuominą, kad yra kažkas negerai su juo.

147
00:10:08,920 --> 00:10:14,430
Kodėl aš nuolat tai daro?

148
00:10:14,430 --> 00:10:18,510
Gerai. Tai atrodo pagrįstas.

149
00:10:18,510 --> 00:10:22,590
Jei pažvelgsime kiekvieną mazgą, kaip 7, tada 7 kairėje yra 3.

150
00:10:22,590 --> 00:10:24,960
Taigi, mes turime 3, dalykas, į dešinę nuo 3 6.

151
00:10:24,960 --> 00:10:27,750
Ir jei jums atrodo 6-ąją, dalykas, į dešinę nuo 6 yra 9.

152
00:10:27,750 --> 00:10:30,910
Tad kodėl tai nėra galioja dvejetainis paieškos medis?

153
00:10:30,910 --> 00:10:36,330
[Studentai] 9 vis dar yra į kairę nuo 7. >> Taip.

154
00:10:36,330 --> 00:10:43,710
Ji turi būti teisinga, kad visos reikšmės jums galbūt gali pasiekti, eikite į kairę nuo 7 yra mažiau nei 7.

155
00:10:43,710 --> 00:10:49,120
Jei mes einame į kairę iš 7, mes turime 3, ir mes vis dar galite gauti iki 6,

156
00:10:49,120 --> 00:10:52,520
mes vis dar galite gauti iki 9, bet powędrowały mažiau nei 7,

157
00:10:52,520 --> 00:10:55,070
mes neturėtų būti suteikta galimybė gauti skaičius, kad didesnis nei 7.

158
00:10:55,070 --> 00:10:59,830
Taigi, tai nėra galiojantis dvejetainis paieškos medis.

159
00:10:59,830 --> 00:11:02,330
>> Mano brolis iš tikrųjų turėjo interviu klausimą

160
00:11:02,330 --> 00:11:07,760
, kad iš esmės tai buvo, tiesiog kodas kažką, kad būtų patvirtinta

161
00:11:07,760 --> 00:11:10,500
ar medis yra dvejetainis paieškos medis,

162
00:11:10,500 --> 00:11:13,580
, todėl pirmas dalykas, kurį jis darė, buvo tik patikrinti,

163
00:11:13,580 --> 00:11:17,020
jeigu iš kairės ir dešinės yra teisingos, ir tada pakartoti ten.

164
00:11:17,020 --> 00:11:19,700
, Bet jūs galite ne tik padaryti, kad, todėl jūs turite sekti

165
00:11:19,700 --> 00:11:22,550
į tai, kad dabar, kai aš atvyko liko iš 7,

166
00:11:22,550 --> 00:11:26,340
viskas šiame šaka turi būti mažiau nei 7.

167
00:11:26,340 --> 00:11:28,430
Teisingas algoritmas turi sekti

168
00:11:28,430 --> 00:11:35,970
lemia, kad vertybės galbūt gali sumažėti.

169
00:11:35,970 --> 00:11:38,360
Mes negalime eiti per visus juos.

170
00:11:38,360 --> 00:11:41,630
Yra gražus pasikartojimo santykis,

171
00:11:41,630 --> 00:11:44,810
nors mes ne Dotarłeś tiems, arba mes ne gauti tiems,

172
00:11:44,810 --> 00:11:47,030
nustatyti, kiek ten iš tikrųjų yra.

173
00:11:47,030 --> 00:11:53,180
Taigi yra 14 iš jų.

174
00:11:53,180 --> 00:11:56,020
Idėja, kaip jūs daryti matematiškai yra panašus,

175
00:11:56,020 --> 00:11:59,770
galite pasirinkti bet kurią vieną šakninis mazgas,

176
00:11:59,770 --> 00:12:03,160
ir tada, jei aš pasiimti 7 šakninis mazgas,

177
00:12:03,160 --> 00:12:08,150
tada yra, tarkim, kai kuriuos skaičius, kad galite eiti mano kairę mazgas,

178
00:12:08,150 --> 00:12:10,440
ir yra keletas numeriai, kurie gali būti mano dešinėje mazgas,

179
00:12:10,440 --> 00:12:15,090
bet jei aš n skaičiai, tada suma, kad gali eiti į kairę

180
00:12:15,090 --> 00:12:18,820
plius sumą, kad gali eiti į dešinę, yra n - 1.

181
00:12:18,820 --> 00:12:26,130
Taigi likusių numerių, jie turi, kad būtų galima eiti arba į kairę, arba teise.

182
00:12:26,130 --> 00:12:31,580
Atrodo, kad sunku, kad, jei aš per pirmuosius 3, tada viskas turi eiti į kairę,

183
00:12:31,580 --> 00:12:35,080
bet jei aš įdėti 7, tada kai kurie dalykai gali eiti į kairę ir kai kurių dalykų gali eiti į dešinę.

184
00:12:35,080 --> 00:12:39,570
Ir "3 pirmasis", aš reiškė, viskas gali eiti į dešinę.

185
00:12:39,570 --> 00:12:42,350
Tai tikrai, jūs tiesiog turite galvoti apie tai, kaip,

186
00:12:42,350 --> 00:12:47,980
kiek daug dalykų gali eiti į kitą lygį medžio.

187
00:12:47,980 --> 00:12:50,420
Ir jis išeina būti 14 arba jūs galite padaryti juos visus,

188
00:12:50,420 --> 00:12:54,650
ir tada jūs gausite 14.

189
00:12:54,650 --> 00:13:01,120
>> Grįžtant čia,

190
00:13:01,120 --> 00:13:03,510
"Užsakytas dvejetainiai medžiai yra kietas, nes mes galime ieškoti per juos

191
00:13:03,510 --> 00:13:06,910
labai panašiai kaip ieškoti per rūšiuotų masyvo.

192
00:13:06,910 --> 00:13:10,120
Norėdami tai padaryti, mes pradedame ties pagrindu ir dirbti savo kelią žemyn medžio

193
00:13:10,120 --> 00:13:13,440
prieš lapų, nuo vertybių, mes ieško patikrinti kiekvienas mazgas vertybes.

194
00:13:13,440 --> 00:13:15,810
Jei dabartinės mazgo vertė yra mažesnė už vertę, mes ieškome,

195
00:13:15,810 --> 00:13:18,050
jūs einate šalia mazgas teisių kūdikiui.

196
00:13:18,050 --> 00:13:20,030
Priešingu atveju, jūs einate mazgas kairėje vaiko.

197
00:13:20,030 --> 00:13:22,800
Tam tikru momentu, jums rasti vertę, jūs ieškote, arba jums paleisti į nulį,

198
00:13:22,800 --> 00:13:28,520
vertę ne į medį ".

199
00:13:28,520 --> 00:13:32,450
Turiu perbraižyti medį, mes turėjome anksčiau, kad paims antrą.

200
00:13:32,450 --> 00:13:38,280
Bet mes norime ieškoti, ar 6, 10 ir 1 į medį.

201
00:13:38,280 --> 00:13:49,180
Taigi, kas tai buvo, 7, 9, 3, 6. Gerai.

202
00:13:49,180 --> 00:13:52,730
Numerius, kuriuos norite ieškoti, mes norime ieškoti 6.

203
00:13:52,730 --> 00:13:55,440
Kaip veikia šis algoritmas darbą?

204
00:13:55,440 --> 00:14:03,040
Na, mes taip pat turi keletą šaknų žymiklį prie mūsų medžio.

205
00:14:03,040 --> 00:14:12,460
Ir mes norėtume eiti į šaknis ir pasakyti, tai yra vertė lygi vertės Mes ieškote?

206
00:14:12,460 --> 00:14:15,000
Taigi, mes ieškome už 6, todėl tai nėra lygus.

207
00:14:15,000 --> 00:14:20,140
Todėl mes nuolat vyksta, ir dabar mes galime pasakyti, gerai, kad 6 yra mažiau nei 7.

208
00:14:20,140 --> 00:14:23,940
Ar tai reiškia, mes norime eiti į kairę, ar mes norime eiti į dešinę?

209
00:14:23,940 --> 00:14:27,340
[Studentų] kairės. >> Taip.

210
00:14:27,340 --> 00:14:33,340
Tai žymiai lengviau, visi jūs turite padaryti, tai atkreipti vieną galimą mazgas medžio

211
00:14:33,340 --> 00:14:37,760
ir tada jums NeraŠykiTe - vietoj bando galvoti savo galva,

212
00:14:37,760 --> 00:14:40,020
gerai, jei tai mažiau, man eiti į kairę arba eiti teisę,

213
00:14:40,020 --> 00:14:43,030
tiesiog žiūri šioje nuotraukoje, tai labai aišku, kad aš turiu eiti į kairę

214
00:14:43,030 --> 00:14:47,700
jei šis mazgas yra didesnė už vertę, kad Aš ieškau.

215
00:14:47,700 --> 00:14:52,600
Taigi jūs einate į kairę, dabar aš ne 3.

216
00:14:52,600 --> 00:14:57,770
Noriu - 3 yra mažiau Aš ieškau už vertę, kuri yra 6.

217
00:14:57,770 --> 00:15:03,420
Taigi, mes einame į dešinę, ir dabar aš galų gale 6,

218
00:15:03,420 --> 00:15:07,380
o tai yra vertė, aš ieškau, todėl aš return true.

219
00:15:07,380 --> 00:15:15,760
Kitą vertė aš ruošiuosi ieškoti 10.

220
00:15:15,760 --> 00:15:23,230
Gerai. Taigi, 10, dabar vyksta - nupjautų, kad ketina laikytis pagrindines.

221
00:15:23,230 --> 00:15:27,670
Dabar 10 yra bus didesnė už 7, todėl aš noriu žiūrėti į dešinę.

222
00:15:27,670 --> 00:15:31,660
Aš ruošiuosi atvažiuoti čia, 10 bus didesnė už 9,

223
00:15:31,660 --> 00:15:34,520
todėl aš ruošiuosi norėsite pažvelgti į dešinę.

224
00:15:34,520 --> 00:15:42,100
Aš atėjau čia, bet kaip čia dabar aš ne null.

225
00:15:42,100 --> 00:15:44,170
Ką daryti, jei aš paspauskite null?

226
00:15:44,170 --> 00:15:47,440
[Studentų] Grįžti klaidingas? >> Taip. Neradau 10.

227
00:15:47,440 --> 00:15:49,800
1 bus beveik identiškas atvejis,

228
00:15:49,800 --> 00:15:51,950
, išskyrus atvejus, ji tiesiog bus apversta, užuot ieškojus

229
00:15:51,950 --> 00:15:56,540
žemyn dešinėje pusėje, aš ruošiuosi žiūrėti žemyn į kairę pusę.

230
00:15:56,540 --> 00:16:00,430
>> Dabar manau, kad mes iš tikrųjų gauti kodą.

231
00:16:00,430 --> 00:16:04,070
Štai kur - atverti CS50 prietaisą ir naršyti savo kelią ten,

232
00:16:04,070 --> 00:16:07,010
bet taip pat galite tiesiog padaryti jį erdvėje.

233
00:16:07,010 --> 00:16:09,170
Tai tikriausiai idealus daryti erdvėje,

234
00:16:09,170 --> 00:16:13,760
nes mes galime dirbti erdvėje.

235
00:16:13,760 --> 00:16:19,170
"Pirmiausia mums reikės dvejetainis medis mazgas, kuriame yra int vertybes naujo tipo apibrėžimą.

236
00:16:19,170 --> 00:16:21,400
Naudojant Šablonas Typedef žemiau,

237
00:16:21,400 --> 00:16:24,510
dvejetainis medis mazgas sukurti naujo tipo apibrėžimą.

238
00:16:24,510 --> 00:16:27,930
, Jei turite problemų. . . "Blah, blah, blah. Gerai.

239
00:16:27,930 --> 00:16:30,380
Taigi tegul Standartiniai čia,

240
00:16:30,380 --> 00:16:41,630
Typedef struct mazgas, ir mazgas. Taip, gerai.

241
00:16:41,630 --> 00:16:44,270
Taigi, ką mes ketiname nori mūsų mazgo laukai?

242
00:16:44,270 --> 00:16:46,520
[Studentų] Žiniasklaida ir tada du patarimų?

243
00:16:46,520 --> 00:16:49,700
>> Žiniasklaida vertė, dvi rodykles? Kaip aš rašau patarimų?

244
00:16:49,700 --> 00:16:58,440
[Studentų] struct. >> Turėčiau padidinti. Taip, kad Struct mazgas * paliko,

245
00:16:58,440 --> 00:17:01,320
ir Struct mazgas * teisus.

246
00:17:01,320 --> 00:17:03,460
Ir atminkite diskusiją nuo paskutinio karto,

247
00:17:03,460 --> 00:17:15,290
, kad tai neturi jokios prasmės, tai neturi jokios prasmės,

248
00:17:15,290 --> 00:17:18,270
tai neturi prasmės.

249
00:17:18,270 --> 00:17:25,000
Jums reikia viską, ką siekiant apibrėžti šį rekursinis struct.

250
00:17:25,000 --> 00:17:27,970
Gerai, kad ką mūsų medis atrodys.

251
00:17:27,970 --> 00:17:37,670
Jei mes padarėme Trójkowy medį, tada mazgas gali atrodyti B1, B2, struct mazgas * B3,

252
00:17:37,670 --> 00:17:43,470
kur b yra filialas - Tiesą sakant, aš daugiau girdėjau, tai Kairėn, Vidurys, teisę, bet whatever.

253
00:17:43,470 --> 00:17:55,610
Mes rūpi tik dvejetainis, todėl kairę, į dešinę.

254
00:17:55,610 --> 00:17:59,110
"Dabar paskelbti pasaulinį mazgas * kintamąjį iš medžio šaknų".

255
00:17:59,110 --> 00:18:01,510
Taigi mes neketiname to daryti.

256
00:18:01,510 --> 00:18:08,950
Tam, kad, kad viskas šiek tiek sunkesnis ir apibendrintas,

257
00:18:08,950 --> 00:18:11,570
mes ne pasaulio mazgas kintamąjį.

258
00:18:11,570 --> 00:18:16,710
Vietoj to, pagrindinis bus paskelbti visus mūsų mazgas dalykų,

259
00:18:16,710 --> 00:18:20,500
, o tai reiškia, kad žemiau, kai mes pradedame veikia

260
00:18:20,500 --> 00:18:23,130
mūsų Contains funkcija ir mūsų įterpti funkciją,

261
00:18:23,130 --> 00:18:27,410
vietoj mūsų sudėtį įeina veikia tik naudojant šį pasaulinį mazgas kintamasis,

262
00:18:27,410 --> 00:18:34,280
mes ketiname kaip argumentas medį, kad mes norime jį apdoroti.

263
00:18:34,280 --> 00:18:36,650
Atsižvelgdama pasaulinį kintamąjį buvo manoma, kad būtų lengviau.

264
00:18:36,650 --> 00:18:42,310
Mes ketiname padaryti ką sunkiau.

265
00:18:42,310 --> 00:18:51,210
Dabar užtrukti minutę ar dvi, tiesiog daryti tai dalykas rūšiuoti,

266
00:18:51,210 --> 00:18:57,690
kai viduje pagrindinis norite sukurti šį medį, ir kad visi jūs norite daryti.

267
00:18:57,690 --> 00:19:04,530
Išbandykite šį medį ir pastatyti savo pagrindinės funkcijos.

268
00:19:42,760 --> 00:19:47,610
>> Gerai. Taigi jums nereikia net buvo pastatyta The Tree visą kelią dar.

269
00:19:47,610 --> 00:19:49,840
Tačiau bet kas, ką aš galėtų atsigriebti

270
00:19:49,840 --> 00:20:03,130
parodyti, kaip galima būtų pradėti statyti tokį medį?

271
00:20:03,130 --> 00:20:08,080
[Studentų] Kažkieno trankosi, bando išeiti.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Kiekvienas patogiai su savo medžio statybos?

273
00:20:13,100 --> 00:20:15,520
[Studentų] Žinoma. Tai nebuvo padaryta. >> Tai gerai. Mes galime tiesiog pabaigti

274
00:20:15,520 --> 00:20:26,860
oh, galite jį išsaugoti? Valio.

275
00:20:26,860 --> 00:20:32,020
Taigi čia mes turime - O, aš šiek tiek nukirto.

276
00:20:32,020 --> 00:20:34,770
Aš Mastelis?

277
00:20:34,770 --> 00:20:37,730
Padidinti vaizdą, spauskite slinkties klavišą. >> Turiu klausimą. >> Taip?

278
00:20:37,730 --> 00:20:44,410
[Studentų] Kai apibrėžti struct, yra dalykų, pavyzdžiui, inicijuoti, kad nieko?

279
00:20:44,410 --> 00:20:47,160
[Bowden] L. >> Gerai. Todėl jūs turite inicijuoti

280
00:20:47,160 --> 00:20:50,450
[Bowden] L. Kai jūs nustatote, arba kai paskelbti struct

281
00:20:50,450 --> 00:20:55,600
ji nėra inicializuoti pagal nutylėjimą, tai tiesiog patinka, jei pareiškiate, int.

282
00:20:55,600 --> 00:20:59,020
Tai lygiai tas pats. Tai kaip kiekvieną iš savo atskirų laukų

283
00:20:59,020 --> 00:21:04,460
gali turėti šiukšlių vertę. >> Ir tai galima nustatyti ar paskelbti struct

284
00:21:04,460 --> 00:21:07,740
tokiu būdu, kad ji nenori inicijuoti juos?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Taip. Taigi, nuoroda iniciacijos sintaksė

286
00:21:13,200 --> 00:21:18,660
atrodys -

287
00:21:18,660 --> 00:21:22,200
Yra du būdai, kaip mes galime tai padaryti. Manau, kad turėtume sudaryti

288
00:21:22,200 --> 00:21:25,840
įsitikinti, kad Apsukite metalinis garsas, taip pat tai daro.

289
00:21:25,840 --> 00:21:28,510
Argumentų tam, kad ateina į struct,

290
00:21:28,510 --> 00:21:32,170
jūs įtraukėte kaip argumentų viduje šių klamrami tvarka.

291
00:21:32,170 --> 00:21:35,690
Taigi, jei norite inicijuoti iki 9, o į kairę, yra niekinis ir tada dešiniuoju yra niekinis,

292
00:21:35,690 --> 00:21:41,570
jis turėtų būti 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternatyva yra, ir redaktorius nemėgsta šią sintaksę,

294
00:21:47,890 --> 00:21:50,300
ir jis mano, kad aš noriu naują bloką,

295
00:21:50,300 --> 00:22:01,800
tačiau alternatyva yra kažkas panašaus -

296
00:22:01,800 --> 00:22:04,190
čia, aš įdėti jį į naują eilutę.

297
00:22:04,190 --> 00:22:09,140
Galite tiksliai pasakyti, nepamenu tikslaus sintaksę.

298
00:22:09,140 --> 00:22:13,110
Todėl jūs galite aiškiai nurodo jų pavadinimą, ir pasakyti,

299
00:22:13,110 --> 00:22:21,570
C arba. Vertė = 9, kairėje = ​​NULL.

300
00:22:21,570 --> 00:22:24,540
Spėju, kad šie veiksmai turi būti kableliais.

301
00:22:24,540 --> 00:22:29,110
Dešinę = NULL, todėl tokiu būdu jūs neturite

302
00:22:29,110 --> 00:22:33,780
tikrųjų reikia žinoti struct tvarka,

303
00:22:33,780 --> 00:22:36,650
ir kai jūs skaitote šį, tai daug aiškus

304
00:22:36,650 --> 00:22:41,920
apie tai, kas vertė yra inicializuoti.

305
00:22:41,920 --> 00:22:44,080
>> Tai atsitinka, kad vienas iš dalykų, kad -

306
00:22:44,080 --> 00:22:49,100
taip, kad didžioji dalis, C + + yra C supersets

307
00:22:49,100 --> 00:22:54,160
Galite imtis C kodą, perkelti jį į C + +, ir tai turėtų sudaryti.

308
00:22:54,160 --> 00:22:59,570
Tai yra vienas iš dalykų, kad C + + nepalaiko, todėl žmonės linkę to nedaryti.

309
00:22:59,570 --> 00:23:01,850
Aš nežinau, jei tai yra vienintelė priežastis, kodėl žmonės linkę to nedaryti,

310
00:23:01,850 --> 00:23:10,540
tačiau tuo atveju, kai man reikia jį naudoti, reikia dirbti su C + + ir todėl aš negalėjo naudoti šią.

311
00:23:10,540 --> 00:23:14,000
Kitas kažką, kad pavyzdys neveikia su C + +

312
00:23:14,000 --> 00:23:16,940
malloc grįžta "void *," techniškai

313
00:23:16,940 --> 00:23:20,200
, bet jūs galite tiesiog pasakyti, char * x = malloc whatever,

314
00:23:20,200 --> 00:23:22,840
ir jis bus automatiškai būti įmestam į char *.

315
00:23:22,840 --> 00:23:25,450
Kad automatinis dauguma neatsitinka C + +.

316
00:23:25,450 --> 00:23:28,150
Kad nebūtų sudaryti, ir jūs aiškiai reikia pasakyti,

317
00:23:28,150 --> 00:23:34,510
char *, malloc, nesvarbu, mesti jį į char *.

318
00:23:34,510 --> 00:23:37,270
Nėra daug dalykų, kad C ir C + + gali nesutarti dėl

319
00:23:37,270 --> 00:23:40,620
tačiau jie yra du.

320
00:23:40,620 --> 00:23:43,120
Taigi mes eiti su šia sintakse.

321
00:23:43,120 --> 00:23:46,150
Bet net jei mes ne eiti su ta sintaksė

322
00:23:46,150 --> 00:23:49,470
tai, kas gali būti negerai?

323
00:23:49,470 --> 00:23:52,170
[Studentų] Man nereikia dereference jį? >> Taip.

324
00:23:52,170 --> 00:23:55,110
Atminkite, kad rodyklė turi implicitini dereference,

325
00:23:55,110 --> 00:23:58,230
ir todėl, kai mes tik susijusius su struct

326
00:23:58,230 --> 00:24:04,300
mes norite naudoti. gauti lauko vidaus struct.

327
00:24:04,300 --> 00:24:07,200
Ir tik laiko mes naudojame rodyklę yra, kai mes norime daryti -

328
00:24:07,200 --> 00:24:13,450
gerai, rodyklė yra lygiavertis

329
00:24:13,450 --> 00:24:17,020
tai, ką ji reikštų, jei aš rodyklę.

330
00:24:17,020 --> 00:24:24,600
Visi rodyklė reiškia, dereference tai dabar aš esu ne struct, ir aš galiu gauti lauką.

331
00:24:24,600 --> 00:24:28,040
Arba gauti lauką tiesiogiai ar dereference ir gauti lauką -

332
00:24:28,040 --> 00:24:30,380
Manau, tai turėtų būti vertė.

333
00:24:30,380 --> 00:24:33,910
Bet čia aš susiduriame tik su, o ne rodyklių į struct struct,

334
00:24:33,910 --> 00:24:38,780
ir todėl aš negaliu naudoti rodyklę.

335
00:24:38,780 --> 00:24:47,510
Bet šis dalykas rūšiuoti, mes galime padaryti visų mazgų.

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

337
00:24:55,790 --> 00:25:09,540
Tai 6, 7 ir 3.

338
00:25:09,540 --> 00:25:16,470
Tada mes galime sukurti mūsų medžio šakas, mes galime turėti 7 -

339
00:25:16,470 --> 00:25:21,650
mes galime, ar tai kairysis turėtų atkreipti dėmesį į 3.

340
00:25:21,650 --> 00:25:25,130
Taigi, kaip tai padaryti?

341
00:25:25,130 --> 00:25:29,320
[Studentai, nesuprantamas] >> Yeah. Adresą iš node3,

342
00:25:29,320 --> 00:25:34,170
ir jei jūs neturite adreso, tada jis tiesiog nebūtų surinkti.

343
00:25:34,170 --> 00:25:38,190
Bet atsiminkite, kad tai yra rodykles į kitą mazgų.

344
00:25:38,190 --> 00:25:44,930
Teisė turėtų atkreipti iki 9,

345
00:25:44,930 --> 00:25:53,330
ir 3 turėtų atkreipti dešinėje iki 6.

346
00:25:53,330 --> 00:25:58,480
Manau, kad tai yra visas rinkinys. Visos pastabos ar klausimai?

347
00:25:58,480 --> 00:26:02,060
[Studentas, nesuprantamas] šaknis bus 7.

348
00:26:02,060 --> 00:26:08,210
Mes galime tik pasakyti mazgas * ptr =

349
00:26:08,210 --> 00:26:14,160
arba šaknis, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Mūsų tikslais, mes ketiname būti susijusios su įdėklu,

351
00:26:20,730 --> 00:26:25,490
todėl mes ketiname norite parašyti funkciją įterpti į šį dvejetainis medis

352
00:26:25,490 --> 00:26:34,230
ir įterpti neišvengiamai ketinate skambinti malloc sukurti naują šio medžio mazgą.

353
00:26:34,230 --> 00:26:36,590
Taigi viskas vyksta gauti purvinas su tuo, kad kai kurie mazgai

354
00:26:36,590 --> 00:26:38,590
Šiuo metu kamino

355
00:26:38,590 --> 00:26:43,680
ir kiti mazgai yra ketina baigti krūvos, kai mes įdėkite juos.

356
00:26:43,680 --> 00:26:47,640
Tai yra visiškai teisingas, bet tik todėl,

357
00:26:47,640 --> 00:26:49,600
mes galime tai padaryti kamino

358
00:26:49,600 --> 00:26:51,840
yra todėl, kad tai nenatūralu pavyzdys, kad mes žinome,

359
00:26:51,840 --> 00:26:56,360
medis turėtų būti sukonstruoti taip, 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Jei mes neturėjome, tada mes būtume neturi malloc į pirmąją vietą.

361
00:27:02,970 --> 00:27:06,160
Kaip matysime šiek tiek vėliau, mes turėtume malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Dabar tai visiškai pagrįsta įdėti į steką,

363
00:27:08,570 --> 00:27:14,750
bet galime tai pakeisti į malloc įgyvendinimo.

364
00:27:14,750 --> 00:27:17,160
Taigi, kiekvienas iš jų yra dabar ketina būti kažkas panašaus

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

366
00:27:24,240 --> 00:27:28,040
Ir dabar mes ketiname turi padaryti mūsų atvykimo.

367
00:27:28,040 --> 00:27:34,010
jei (== NULL node9) - Aš nenorėjau, kad

368
00:27:34,010 --> 00:27:40,950
Atgal 1, tada mes galime padaryti node9-> nes dabar rodyklė,

369
00:27:40,950 --> 00:27:45,300
vertė = 6, node9> left = NULL,

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

371
00:27:48,930 --> 00:27:51,410
ir mes ketiname daryti, kad kiekvieno iš šių mazgų.

372
00:27:51,410 --> 00:27:57,490
Taigi vietoj to, tegul jį viduje atskirame funkcijos.

373
00:27:57,490 --> 00:28:00,620
Tegul jį vadiname mazgas * build_node

374
00:28:00,620 --> 00:28:09,050
ir tai yra šiek tiek panašus į API, mes pateikiame Hafmano kodavimas.

375
00:28:09,050 --> 00:28:12,730
Mes suteikiame Jums inicijavimo priemonės funkcijas medžio

376
00:28:12,730 --> 00:28:20,520
deconstructor "funkcijos" tų medžių ir miškų.

377
00:28:20,520 --> 00:28:22,570
>> Taigi čia mes ketiname turėti inicijavimo priemonės funkciją

378
00:28:22,570 --> 00:28:25,170
tiesiog statyti už mus mazgas.

379
00:28:25,170 --> 00:28:29,320
Ir tai vyksta atrodo beveik lygiai taip pat kaip tai.

380
00:28:29,320 --> 00:28:32,230
Ir aš net būti tingus, o ne pakeisti kintamojo pavadinimą,

381
00:28:32,230 --> 00:28:34,380
nors node9 jokios prasmės nebėra.

382
00:28:34,380 --> 00:28:38,610
O, aš manau, node9 vertė neturėjo būti 6.

383
00:28:38,610 --> 00:28:42,800
Dabar galime grįžti node9.

384
00:28:42,800 --> 00:28:49,550
Ir čia mes grąžina NULL.

385
00:28:49,550 --> 00:28:52,690
Kiekvienas susitarti dėl to Build-A-mazgo funkciją?

386
00:28:52,690 --> 00:28:59,780
Taigi dabar mes galime tiesiog paskambinkite, kad sukurti bet su tam tikros ribos, null Pointeriai mazgas.

387
00:28:59,780 --> 00:29:09,750
Dabar mes galime skambinti, kad mes galime padaryti mazgas * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Ir darykime. . .

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

390
00:29:33,980 --> 00:29:39,330
Ir dabar mes norime sukurti tuos pačius nurodymus,

391
00:29:39,330 --> 00:29:42,470
išskyrus dabar viskas jau patarimų

392
00:29:42,470 --> 00:29:48,480
todėl nebereikia adresą.

393
00:29:48,480 --> 00:29:56,300
Gerai. Taigi, kas yra paskutinis dalykas, kurį noriu padaryti,?

394
00:29:56,300 --> 00:30:03,850
Yra klaidų nebus, kad aš ne daryti.

395
00:30:03,850 --> 00:30:06,800
Ką statyti mazgas grįžti?

396
00:30:06,800 --> 00:30:11,660
[Studentas, nesuprantamas] >> Taip. Jei malloc nepavyko, jis bus grąžina NULL.

397
00:30:11,660 --> 00:30:16,460
Taigi, aš ruošiuosi tingiai tai nuleisk ją čia, o ne padaryti už kiekvieną sąlygą.

398
00:30:16,460 --> 00:30:22,320
Jei (node9 == NULL, arba - dar paprasčiau,

399
00:30:22,320 --> 00:30:28,020
tai atitinka tik jei ne node9.

400
00:30:28,020 --> 00:30:38,310
Taigi jei ne node9, ar ne node6, ar ne node3, ar ne node7, grįžkite 1.

401
00:30:38,310 --> 00:30:42,850
Gal reikėtų spausdinti malloc nepavyko, ar kažkas.

402
00:30:42,850 --> 00:30:46,680
[Studentų] Ar klaidinga lygus nulis taip pat?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Bet nulinė vertė yra klaidinga.

404
00:30:51,290 --> 00:30:53,920
Taigi null yra nulinė vertė.

405
00:30:53,920 --> 00:30:56,780
Nulis yra nulinė vertė. False yra nulinė vertė.

406
00:30:56,780 --> 00:31:02,130
Bet koks - gana daug tik 2 nulines vertes yra niekinis ir lygus nuliui,

407
00:31:02,130 --> 00:31:07,900
klaidinga yra tik maišos apibrėžiamas kaip lygus nuliui.

408
00:31:07,900 --> 00:31:13,030
Tai taip pat taikoma, jei mes paskelbti pasaulinį kintamąjį.

409
00:31:13,030 --> 00:31:17,890
Jei mes turėjo mazgas * šaknis čia,

410
00:31:17,890 --> 00:31:24,150
tada - malonus dalykas, apie globalių kintamųjų, kad jie visada turi pradinę vertę.

411
00:31:24,150 --> 00:31:27,500
Tai nėra tiesa funkcijų, kaip viduje iš čia,

412
00:31:27,500 --> 00:31:34,870
jei mes turime, pavyzdžiui, mazgas * arba mazgas x.

413
00:31:34,870 --> 00:31:37,380
Mes neturime jokio supratimo ką x.value, x.whatever

414
00:31:37,380 --> 00:31:40,700
ar mes galime juos atsispausdinti ir jie gali būti savavališkai.

415
00:31:40,700 --> 00:31:44,980
Tai nėra tiesa globalių kintamųjų.

416
00:31:44,980 --> 00:31:47,450
Taigi mazgas šaknų mazgas x.

417
00:31:47,450 --> 00:31:53,410
Pagal nutylėjimą, viskas, kas pasaulio, jei ne aiškiai inicijuoti tam tikrą vertę,

418
00:31:53,410 --> 00:31:57,390
turi nulinę vertę kaip jo vertės.

419
00:31:57,390 --> 00:32:01,150
Taigi čia, mazgas * šaknis, mes ne tiesiogiai inicijuoti jį nieko,

420
00:32:01,150 --> 00:32:06,350
todėl jos numatytoji reikšmė bus niekinis, kuri yra nulinė vertė patarimų.

421
00:32:06,350 --> 00:32:11,870
Numatytoji vertė x reiškia, kad x.value yra lygi nuliui,

422
00:32:11,870 --> 00:32:14,260
, x.left yra niekinis, ir yra niekinis x.right.

423
00:32:14,260 --> 00:32:21,070
Taigi, kadangi tai yra struct, visi struct srityse bus nulines vertes.

424
00:32:21,070 --> 00:32:24,410
Mums nereikia naudoti, kad čia, nors.

425
00:32:24,410 --> 00:32:27,320
[Studentų] structs yra kitoks nei kitų kintamųjų, ir kiti kintamieji

426
00:32:27,320 --> 00:32:31,400
šiukšlių vertės; tai yra nuliai?

427
00:32:31,400 --> 00:32:36,220
[Bowden] ir kitas vertes, taip pat. Taigi, X, X bus lygi nuliui.

428
00:32:36,220 --> 00:32:40,070
Jei ji yra pasaulinio pobūdžio, ji pradinę vertę. >> Gerai.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Bet pradinė vertė jums davė, arba nulis.

430
00:32:48,950 --> 00:32:53,260
Manau, kad rūpinasi visa tai.

431
00:32:53,260 --> 00:32:58,390
>> Gerai. Taigi kai kitą klausimo dalis iš esmės klausia,

432
00:32:58,390 --> 00:33:01,260
"Dabar mes norime parašyti funkciją, vadinamą yra

433
00:33:01,260 --> 00:33:04,930
su bool prototipas yra int vertę. "

434
00:33:04,930 --> 00:33:08,340
Mes neketiname daryti, bool yra int vertę.

435
00:33:08,340 --> 00:33:15,110
Mūsų prototipas atrodys

436
00:33:15,110 --> 00:33:22,380
bool yra (int vertę.

437
00:33:22,380 --> 00:33:24,490
Ir tada mes taip pat ketiname perduoti jį į medį

438
00:33:24,490 --> 00:33:28,870
kad ji turėtų būti patikrinti, pamatyti, jei ji turi tą vertę.

439
00:33:28,870 --> 00:33:38,290
Taigi mazgas * medis). Gerai.

440
00:33:38,290 --> 00:33:44,440
Ir tada mes galime skambinti kažką panašaus,

441
00:33:44,440 --> 00:33:46,090
ir galbūt mes norite printf ar kažką.

442
00:33:46,090 --> 00:33:51,040
Sudėtyje yra 6, mūsų šaknų.

443
00:33:51,040 --> 00:33:54,300
Tai turėtų grąžinti vieną ar tikrosios,

444
00:33:54,300 --> 00:33:59,390
o yra 5 šaknis turėtų grįžti klaidinga.

445
00:33:59,390 --> 00:34:02,690
Taigi imtis antra tai įgyvendinti.

446
00:34:02,690 --> 00:34:06,780
Jūs galite tai padaryti arba keletą kartų arba rekursyviai.

447
00:34:06,780 --> 00:34:09,739
Gražus dalykas, apie tai, kaip mes Nustatykite, yra tai, kad

448
00:34:09,739 --> 00:34:12,300
jis skolina pati į mūsų rekursinis tirpalu daug lengviau

449
00:34:12,300 --> 00:34:14,719
kaip pasaulio kintamųjų būdas.

450
00:34:14,719 --> 00:34:19,750
Nes jei mes tiesiog yra int vertę, tada mes turime jokių recursing žemyn subtrees būdu.

451
00:34:19,750 --> 00:34:24,130
Mes turėtume turėti atskirą pagalbininkas funkciją, kad recurses mus subtrees.

452
00:34:24,130 --> 00:34:29,610
Bet kadangi mes pakeitėme ji galėtų imtis medį kaip argumentą,

453
00:34:29,610 --> 00:34:32,760
kurią jis turėtų visada buvo pirmoje vietoje,

454
00:34:32,760 --> 00:34:35,710
dabar mes galime šabl lengviau.

455
00:34:35,710 --> 00:34:38,960
Taigi pasikartojantis arba rekursinis mes pereiti tiek,

456
00:34:38,960 --> 00:34:46,139
bet mes pamatysime, kad rekursinių galų gale buvo gana lengva.

457
00:34:59,140 --> 00:35:02,480
Gerai. Ar kas nors turi ką mes galime dirbti su?

458
00:35:02,480 --> 00:35:12,000
>> [Studentų] Turiu kartotinis sprendimas. >> Viskas gerai, kartojamas.

459
00:35:12,000 --> 00:35:16,030
Gerai, tai gerai atrodo.

460
00:35:16,030 --> 00:35:18,920
Taigi, nori vaikščioti mus per tai?

461
00:35:18,920 --> 00:35:25,780
[Studentų] Žinoma. Taigi, aš temp kintamąjį gauti pirmąjį mazgą medžio.

462
00:35:25,780 --> 00:35:28,330
Ir tada aš tiesiog Kilpinės per, o temperatūra nėra lygi null

463
00:35:28,330 --> 00:35:31,700
taip, o dar į medį, I guess.

464
00:35:31,700 --> 00:35:35,710
Ir jei reikšmė yra lygi vertės, kad temperatūra yra nukreipta į

465
00:35:35,710 --> 00:35:37,640
tada ji grąžina šią vertę.

466
00:35:37,640 --> 00:35:40,210
Priešingu atveju, jis pasitikrina, jei tai dešinėje arba kairėje pusėje.

467
00:35:40,210 --> 00:35:43,400
Jei jūs kada nors gauti situaciją, kai ne daugiau medžių,

468
00:35:43,400 --> 00:35:47,330
tada ji grąžina - išeinant kilpą ir False.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Gerai. Taip, kad atrodo gerai.

470
00:35:52,190 --> 00:35:58,470
Kiekvienas turi jokių pastabų dėl nieko?

471
00:35:58,470 --> 00:36:02,400
Aš neturiu korektiškumo komentarus.

472
00:36:02,400 --> 00:36:11,020
Vienas dalykas, mes galime padaryti, tai vaikinas.

473
00:36:11,020 --> 00:36:21,660
O, jis ketina eiti šiek tiek ilgais,.

474
00:36:21,660 --> 00:36:33,460
Aš nustatyti, kad iki. Gerai.

475
00:36:33,460 --> 00:36:37,150
>> Kiekvienas turi prisiminti, kaip trijų komponentų veikia.

476
00:36:37,150 --> 00:36:38,610
Ten tikrai buvo viktorinos praeityje

477
00:36:38,610 --> 00:36:41,170
, kad suteikti Jums su trijų komponentų pluoštų operatoriaus funkciją,

478
00:36:41,170 --> 00:36:45,750
ir pasakyti, išversti, kažką daryti, kad nenaudoja trinariu.

479
00:36:45,750 --> 00:36:49,140
Taigi tai yra labai dažnas atvejis, kai aš norėčiau galvoti naudoti trijų komponentų,

480
00:36:49,140 --> 00:36:54,610
kur, jei kai sąlyga nustatyti kintamąjį į kažką

481
00:36:54,610 --> 00:36:58,580
dar tą patį kintamąjį į ką nors kita.

482
00:36:58,580 --> 00:37:03,390
, Kad kažkas, kad labai dažnai šis dalykas rūšiuoti gali būti transformuota į

483
00:37:03,390 --> 00:37:14,420
kur nustatyti, kad kintamąjį - arba gerai, ar tai tiesa? Tada tai kitas.

484
00:37:14,420 --> 00:37:18,550
[Studentų] Pirmasis yra, jei tiesa, tiesa?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Taip. Būdas, aš visada skaityti, temperatūra lygi reikšmę didesnę nei temp vertės,

486
00:37:25,570 --> 00:37:30,680
tada tai kitas. Užduoti klausimą.

487
00:37:30,680 --> 00:37:35,200
Ar jis didesnis? Tada atlikite pirmas dalykas. Kita padaryti Antras dalykas.

488
00:37:35,200 --> 00:37:41,670
Aš beveik visada - dvitaškis, aš tiesiog, mano galva, aš perskaičiau, kaip kitur.

489
00:37:41,670 --> 00:37:47,180
>> Ar kas nors turite rekursinį sprendimą?

490
00:37:47,180 --> 00:37:49,670
Gerai. Tai vienas, mes ketiname - tai jau gali būti didelis,

491
00:37:49,670 --> 00:37:53,990
bet mes ketiname padaryti dar geriau.

492
00:37:53,990 --> 00:37:58,720
Tai yra gana daug pats tiksliai idėja.

493
00:37:58,720 --> 00:38:03,060
Tai tiesiog, gerai, jūs norite paaiškinti?

494
00:38:03,060 --> 00:38:08,340
[Studentų] Žinoma. Taigi mes įsitikinkite, kad medis IS NOT NULL 1.

495
00:38:08,340 --> 00:38:13,380
nes jei medis yra niekinis, jis ketina grįžti klaidinga, nes mums nepavyko rasti jį.

496
00:38:13,380 --> 00:38:19,200
Ir jei dar yra medis, mes einame į - mes pirmą kartą patikrinti, ar vertė yra dabartinė mazgas.

497
00:38:19,200 --> 00:38:23,740
Grąžina true jei jis yra, ir jei ne mes šabl kairę arba į dešinę.

498
00:38:23,740 --> 00:38:25,970
Ar tai garso tinkamas? >> Mm-hmm. (Susitarimas)

499
00:38:25,970 --> 00:38:33,880
Taigi, pastebėsite, kad tai beveik struktūriškai labai panaši į Pakartotinai tirpalu.

500
00:38:33,880 --> 00:38:38,200
Tai tiesiog, kad vietoj recursing, mes turėjome while cikle.

501
00:38:38,200 --> 00:38:40,840
Ir bazė atveju, kai medis nėra lygi null

502
00:38:40,840 --> 00:38:44,850
buvo sąlyga, pagal kurią mes įsiplieskė while cikle.

503
00:38:44,850 --> 00:38:50,200
Jie labai panašūs. Bet mes ketiname imtis dar vieną žingsnį.

504
00:38:50,200 --> 00:38:54,190
Dabar, mes čia tą patį.

505
00:38:54,190 --> 00:38:57,680
Pranešimas mes grįžti tą patį šių eilučių,

506
00:38:57,680 --> 00:39:00,220
išskyrus vienas argumentas yra skirtingos.

507
00:39:00,220 --> 00:39:07,950
Taigi, mes ketiname padaryti, kad į trinariu.

508
00:39:07,950 --> 00:39:13,790
Aš paspauskite parinktį kažką, ir ji padarė simbolį. Gerai.

509
00:39:13,790 --> 00:39:21,720
Taigi mes ketiname grįžti yra ta.

510
00:39:21,720 --> 00:39:28,030
Tai vis į kelias eilutes, gerai, Mastelis tai.

511
00:39:28,030 --> 00:39:31,060
Paprastai, kaip stiliaus dalykas, aš ne manau, daug žmonių

512
00:39:31,060 --> 00:39:38,640
įdėti po rodyklės erdvę, bet aš manau, jei esate nuosekli, tai gerai.

513
00:39:38,640 --> 00:39:44,320
Jei vertė yra mažesnė nei medžio vertę, mes norime šabl ant medžio kairėje,

514
00:39:44,320 --> 00:39:53,890
dar norime recurse nuo medžio teise.

515
00:39:53,890 --> 00:39:58,610
Kad buvo padaryti tai atrodo mažesnis vienas žingsnis.

516
00:39:58,610 --> 00:40:02,660
Antras žingsnis tai atrodo mažesnis -

517
00:40:02,660 --> 00:40:09,150
mes galime atskirti keletą eilučių.

518
00:40:09,150 --> 00:40:16,500
Gerai. Todėl atrodo mažesni dviejų etapų yra čia,

519
00:40:16,500 --> 00:40:25,860
grąžinimo vertė yra lygi medžio vertę, ar yra whatever.

520
00:40:25,860 --> 00:40:28,340
>> Tai yra svarbus dalykas.

521
00:40:28,340 --> 00:40:30,860
Aš nesu įsitikinęs, jei jis sakė, kad tai aiškiai klasėje,

522
00:40:30,860 --> 00:40:34,740
bet tai vadinama trumpojo jungimo vertinimas.

523
00:40:34,740 --> 00:40:41,060
Čia yra idėja vertė == medis vertė.

524
00:40:41,060 --> 00:40:49,960
Jei tai tiesa, tada tai yra tiesa, ir mes norime, kad "arba" kad visa, kas čia.

525
00:40:49,960 --> 00:40:52,520
Taigi, net galvoti apie ką čia,

526
00:40:52,520 --> 00:40:55,070
kas yra visa išraiška nesiruošia grįžti?

527
00:40:55,070 --> 00:40:59,430
[Studentų] Tikroji? >> Taip, nes tiesa nieko,

528
00:40:59,430 --> 00:41:04,990
su niekuo or'd - ar tiesa or'd yra nebūtinai tiesa.

529
00:41:04,990 --> 00:41:08,150
Taigi, kuo greičiau, kaip matome sugrįžimo vertę = medis vertės,

530
00:41:08,150 --> 00:41:10,140
mes tiesiog ketina grįžti tiesa.

531
00:41:10,140 --> 00:41:15,710
Net ketina recurse toliau yra žemyn linija.

532
00:41:15,710 --> 00:41:20,980
Mes galime imtis vieną žingsnį toliau.

533
00:41:20,980 --> 00:41:29,490
Grįžti medis nėra lygi null Ir visa tai.

534
00:41:29,490 --> 00:41:32,650
Jis padarė tai vienos eilutės funkcija.

535
00:41:32,650 --> 00:41:36,790
Tai yra trumpojo jungimo vertinimo pavyzdys.

536
00:41:36,790 --> 00:41:40,680
Bet dabar tai pati idėja -

537
00:41:40,680 --> 00:41:47,320
vietoj - taigi, jei medis, nėra lygi null - arba gerai,

538
00:41:47,320 --> 00:41:49,580
jei medis nėra vienodas null, kuris atvejis yra blogas,

539
00:41:49,580 --> 00:41:54,790
jei medis yra lygus nuliui, tada pirmoji sąlyga bus klaidingas.

540
00:41:54,790 --> 00:42:00,550
Taigi klaidinga anded, su nieko bus, ką?

541
00:42:00,550 --> 00:42:04,640
[Studentų] klaidinga. >> Taip. Tai kita pusė trumpojo jungimo vertinimo,

542
00:42:04,640 --> 00:42:10,710
kur jei medis nėra lygus NULL, tada mes nesiruošia net eiti

543
00:42:10,710 --> 00:42:14,930
arba jei medis nėra vienodas null, tada mes ne ketinate daryti vertę == medis vertės.

544
00:42:14,930 --> 00:42:17,010
Mes tik ketina nedelsiant gražins false.

545
00:42:17,010 --> 00:42:20,970
, Kuris yra svarbus, nes jei jis to nepadarė trumpojo jungimo ir įvertinimas,

546
00:42:20,970 --> 00:42:25,860
tada, jei medis ar vienodą null ši antroji sąlyga ketina seg kaltės,

547
00:42:25,860 --> 00:42:32,510
nes medis-> vertė dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Taigi tai, kad. Tai gali padaryti - pereiti vieną kartą per.

549
00:42:40,490 --> 00:42:44,840
Tai yra labai dažnas dalykas, taip pat, ne šį vieną eilutę su šiuo,

550
00:42:44,840 --> 00:42:49,000
bet tai sąlygomis dažnas dalykas, o gal ir ne čia,

551
00:42:49,000 --> 00:42:59,380
bet jei (medis! = NULL, ir medis-> value == vertė), daryti ką.

552
00:42:59,380 --> 00:43:01,560
Tai labai dažna būklė, kai užuot

553
00:43:01,560 --> 00:43:06,770
padalyti į dvi IF, kur, pavyzdžiui, yra medis null?

554
00:43:06,770 --> 00:43:11,780
Gerai, tai nėra lygus nuliui, taigi dabar yra medis vertė yra lygi vertės? Tai padaryti.

555
00:43:11,780 --> 00:43:17,300
Vietoj to, ši sąlyga, tai niekada seg kaltės

556
00:43:17,300 --> 00:43:21,220
, nes tai bus pertrauka, jei tai atsitiks, yra niekinis.

557
00:43:21,220 --> 00:43:24,000
Na, manau, jei jūsų medis yra visiškai neteisingas rodyklė, ji gali dar seg kaltės,

558
00:43:24,000 --> 00:43:26,620
tačiau jis negali seg kaltės, jei medis yra niekinis.

559
00:43:26,620 --> 00:43:32,900
Jei ji buvo nulis, tai būtų galima nutraukti, prieš jūs kada nors dereferenced žymiklį į pirmąją vietą.

560
00:43:32,900 --> 00:43:35,000
[Studentų] Ar Tai vadinama tingus vertinimas?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy vertinimas yra atskiras dalykas.

562
00:43:40,770 --> 00:43:49,880
Tingus vertinimas yra daugiau, kaip jūs paklausti, kurių vertė,

563
00:43:49,880 --> 00:43:54,270
Jūs klausiate, apskaičiuoti vertę, rūšis, tačiau jums nereikia iš karto.

564
00:43:54,270 --> 00:43:59,040
Taigi, kol jūs iš tikrųjų reikia, tai nėra vertinamas.

565
00:43:59,040 --> 00:44:03,920
Tai ne visai tas pats, bet Hafmano pset

566
00:44:03,920 --> 00:44:06,520
ji sako, kad mes "tingiai" rašyti.

567
00:44:06,520 --> 00:44:08,670
Priežastis mes tai padarysime, nes mes iš tikrųjų buferinė Rašyti

568
00:44:08,670 --> 00:44:11,820
mes nenorime rašyti atskirus bitai vienu metu,

569
00:44:11,820 --> 00:44:15,450
arba atskirų baitų vienu metu, mes, o ne norite gauti baitų riekė.

570
00:44:15,450 --> 00:44:19,270
Tada, kai mes turime baitų riekė, tada mes rašyti jį.

571
00:44:19,270 --> 00:44:22,640
Nors jūs paprašykite rašyti ir fwrite ir fread padaryti tos pačios rūšies dalykas.

572
00:44:22,640 --> 00:44:26,260
Jie buferio jūsų skaito ir rašo.

573
00:44:26,260 --> 00:44:31,610
Net jei jūs paprašykite jį rašyti iš karto, tai tikriausiai nebus.

574
00:44:31,610 --> 00:44:34,540
Ir jūs negalite būti tikri, kad viskas bus parašyta

575
00:44:34,540 --> 00:44:37,540
kol skambinate hfclose ar kokia ji yra,

576
00:44:37,540 --> 00:44:39,620
tada sako, gerai, aš uždaryti savo failą,

577
00:44:39,620 --> 00:44:43,450
tai reiškia, kad aš geriau rašyti viską, ką esu dar nėra parašyta.

578
00:44:43,450 --> 00:44:45,770
Ji nereikia rašyti viską iš

579
00:44:45,770 --> 00:44:49,010
tol, kol yra uždaryti failą, ir tada jis turi.

580
00:44:49,010 --> 00:44:56,220
Taigi, tai tik ką tingus - jis laukia, kol jis turi įvykti.

581
00:44:56,220 --> 00:44:59,990
Tai - imtis 51 ir jums eiti į jį išsamiau,

582
00:44:59,990 --> 00:45:05,470
nes OCaml ir viskas 51, viskas yra rekursija.

583
00:45:05,470 --> 00:45:08,890
Yra ne kartotinis sprendimus, iš esmės.

584
00:45:08,890 --> 00:45:11,550
Viskas yra rekursija ir tingus vertinimas

585
00:45:11,550 --> 00:45:14,790
bus svarbu daug aplinkybių

586
00:45:14,790 --> 00:45:19,920
kur, jei tu ne tingiai įvertinti, tai reikštų -

587
00:45:19,920 --> 00:45:24,760
Pavyzdys yra srautai, kurie yra be galo ilgas.

588
00:45:24,760 --> 00:45:30,990
Teoriškai jūs galite galvoti kaip 1-2-3-4-5-6-7 srauto iš natūralių skaičių

589
00:45:30,990 --> 00:45:33,090
Taip tingiai įvertino viskas yra gerai.

590
00:45:33,090 --> 00:45:37,210
Jei aš sakau, kad aš noriu dešimties skaičių, tada aš gali įvertinti iki dešimtosios skaičiaus.

591
00:45:37,210 --> 00:45:40,300
Jei aš noriu šimtąjį skaičių, tada aš gali įvertinti šimtąjį skaičių.

592
00:45:40,300 --> 00:45:46,290
Be tingus vertinimo, tada jis vyksta pabandyti įvertinti visus numerius iš karto.

593
00:45:46,290 --> 00:45:50,000
Jūs vertinti be galo daug skaičių, ir tai yra tiesiog neįmanoma.

594
00:45:50,000 --> 00:45:52,080
Taigi yra daug aplinkybių, kai tingus vertinimas

595
00:45:52,080 --> 00:45:57,840
yra tiesiog būtina gauti dalykų dirbti.

596
00:45:57,840 --> 00:46:05,260
>> Dabar mes norime parašyti informacinį lapelį, kur įterpti bus

597
00:46:05,260 --> 00:46:08,430
taip pat keičiasi jos apibrėžime.

598
00:46:08,430 --> 00:46:10,470
Taigi dabar tai bool įterpti (int vertė).

599
00:46:10,470 --> 00:46:23,850
Mes ketiname pakeisti, kad bool įdėklu (int vertė, mazgas * medis).

600
00:46:23,850 --> 00:46:29,120
Mes iš tikrųjų ketiname pakeisti, kad dar kartą šiek tiek, mes suprasti, kodėl.

601
00:46:29,120 --> 00:46:32,210
Ir tegul perkelti build_node, tik jo gi,

602
00:46:32,210 --> 00:46:36,730
, įdėkite, kad mes neturime rašyti funkcijos prototipas.

603
00:46:36,730 --> 00:46:42,450
Kuris yra užuomina, kad jūs ketinate naudoti build_node įdėkle.

604
00:46:42,450 --> 00:46:49,590
Gerai. Imtis, kad minutę.

605
00:46:49,590 --> 00:46:52,130
Manau, kad išgelbėjo peržiūrėti, jei norite ištraukti,

606
00:46:52,130 --> 00:47:00,240
ar bent jau, aš dabar.

607
00:47:00,240 --> 00:47:04,190
Norėjau šiek tiek pertraukos galvoti apie įdėklu logika,

608
00:47:04,190 --> 00:47:08,750
jei tu negali galvoti apie tai.

609
00:47:08,750 --> 00:47:12,860
Iš esmės, jūs tik kada nors bus įstatykite lapų.

610
00:47:12,860 --> 00:47:18,640
, Pavyzdžiui, jei aš įterpti 1, tada aš neišvengiamai bus įterpiant 1 -

611
00:47:18,640 --> 00:47:21,820
Aš pakeisti juoda - I'll įterpiant 1 čia.

612
00:47:21,820 --> 00:47:28,070
Arba, jeigu aš įterpti 4, aš noriu būti čia įterpiant 4.

613
00:47:28,070 --> 00:47:32,180
Todėl nesvarbu, ką jūs darote, jūs ketinate būti lapo įterpti.

614
00:47:32,180 --> 00:47:36,130
Viskas, ką jums reikia padaryti, yra pakartoti medį, kol gausite į mazgą

615
00:47:36,130 --> 00:47:40,890
kad turėtų būti tėvų mazgas, naujas mazgas tėvų,

616
00:47:40,890 --> 00:47:44,560
ir tada pakeisti savo kairę arba į dešinę žymeklį, priklausomai nuo to, ar

617
00:47:44,560 --> 00:47:47,060
tai didesnis arba mažesnis nei dabartinis mazgas.

618
00:47:47,060 --> 00:47:51,180
Pakeisti, kad žymiklį, kad atkreipti dėmesį į savo naujas mazgas.

619
00:47:51,180 --> 00:48:05,490
Taigi pakartoti medį, kad lapų tašką į naują mazgas.

620
00:48:05,490 --> 00:48:09,810
Taip pat pagalvokite apie tai, kodėl draudžia situacijos tipą prieš,

621
00:48:09,810 --> 00:48:17,990
kur aš pastatė dvejetainis medis, kur ji buvo teisinga,

622
00:48:17,990 --> 00:48:19,920
jei jūs tik pažvelgė į vieno mazgo,

623
00:48:19,920 --> 00:48:24,830
bet 9 buvo jei pakartota visą kelią į kairę nuo 7.

624
00:48:24,830 --> 00:48:29,770
Taip, kad neįmanoma šiame scenarijuje, nes -

625
00:48:29,770 --> 00:48:32,530
galvoti apie įstatykite 9 arba kažką labai iš pirmo mazgo,

626
00:48:32,530 --> 00:48:35,350
Aš ruošiuosi žr. 7 ir aš dabar einu į dešinę.

627
00:48:35,350 --> 00:48:38,490
Todėl nesvarbu, ką man daryti, jei aš ketina lapo įterpti,

628
00:48:38,490 --> 00:48:40,790
ir lapų, naudojant atitinkamą algoritmą,

629
00:48:40,790 --> 00:48:43,130
tai bus neįmanoma, man 9 įterpti į kairę nuo 7

630
00:48:43,130 --> 00:48:48,250
nes kuo greičiau aš paspauskite 7 Aš ruošiuosi eiti į dešinę.

631
00:48:59,740 --> 00:49:02,070
Ar kas nors turi kažką pradėti?

632
00:49:02,070 --> 00:49:05,480
[Studentų] darau. >> Žinoma.

633
00:49:05,480 --> 00:49:09,200
[Studentų, nesuprantamas]

634
00:49:09,200 --> 00:49:14,390
[Other studentas, neįskaitomai]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Tai vertinama. Gerai. Noriu paaiškinti?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Kadangi mes žinome, kad buvo įterpiant

637
00:49:20,690 --> 00:49:24,060
naujus mazgus iš medžio,

638
00:49:24,060 --> 00:49:28,070
Aš Kilpinės keletą kartų per medžio

639
00:49:28,070 --> 00:49:31,360
kol aš mazgas, kad atkreipė dėmesį į nulis.

640
00:49:31,360 --> 00:49:34,220
Ir tada aš nusprendžiau įdėti jį arba dešinėje arba kairėje pusėje

641
00:49:34,220 --> 00:49:37,420
naudojasi šia teise, kintamuosius; jis man pasakė, kur įdėti.

642
00:49:37,420 --> 00:49:41,850
Ir tada, iš esmės, aš tiesiog padarė, kad paskutinis -

643
00:49:41,850 --> 00:49:47,520
kad temp mazgas naujas mazgas, kad ji buvo sukurti,

644
00:49:47,520 --> 00:49:50,770
kairėje pusėje ar dešinėje pusėje, priklausomai nuo to, kas vertė teisė.

645
00:49:50,770 --> 00:49:56,530
Galiausiai, aš nustačiau naują mazgas vertę savo bandymų vertės.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Gerai, kad aš matau čia vieną problemą.

647
00:49:59,550 --> 00:50:02,050
Tai, pavyzdžiui, 95%, kaip ten.

648
00:50:02,050 --> 00:50:07,550
Vienas klausimas, kad aš matau, gerai, ar kas nors kitas pamatyti problemą?

649
00:50:07,550 --> 00:50:18,400
Kas yra aplinkybė, pagal kurią jie išeiti iš kilpos?

650
00:50:18,400 --> 00:50:22,100
[Studentų] Jei temperatūra yra niekinis? >> Taip. Taigi, kaip jums išeiti iš kilpos, jei temperatūra yra niekinis.

651
00:50:22,100 --> 00:50:30,220
Bet ką aš čia?

652
00:50:30,220 --> 00:50:35,410
Aš dereference temperatūra, kuri yra neišvengiamai null.

653
00:50:35,410 --> 00:50:39,840
Taigi, kitas dalykas, ką jums reikia padaryti yra ne tik stebėti, kol temperatūra yra niekinis,

654
00:50:39,840 --> 00:50:45,590
norite sekti iš tėvų visą laiką.

655
00:50:45,590 --> 00:50:52,190
Mes taip pat norime mazgas * tėvų, aš manau, mes galime laikyti, kad netekusiais iš pradžių.

656
00:50:52,190 --> 00:50:55,480
Teks keistą elgesį iš medžio šaknų,

657
00:50:55,480 --> 00:50:59,210
bet mes gauti, kad.

658
00:50:59,210 --> 00:51:03,950
Jei vertė yra didesnė nei whatever, tada temp = temp teisus.

659
00:51:03,950 --> 00:51:07,910
Tačiau prieš tai, kad, tėvų = temp.

660
00:51:07,910 --> 00:51:14,500
Ar tėvai visada vyksta į vienodą temp? Yra tai, kad šiuo atveju?

661
00:51:14,500 --> 00:51:19,560
Jei temperatūra nėra lygus nuliui, tada aš ruošiuosi judėti žemyn, nesvarbu, ką,

662
00:51:19,560 --> 00:51:24,030
mazgas, kurių temperatūra yra patronuojanti.

663
00:51:24,030 --> 00:51:27,500
Taigi patronuojančios įmonės bus temp, ir tada aš perkelti temp žemyn.

664
00:51:27,500 --> 00:51:32,410
Dabar temperatūra yra nulis, bet iš tėvų yra niekinis dalykas, kad tėvų.

665
00:51:32,410 --> 00:51:39,110
Taip žemai čia, aš nenoriu nustatyti lygi 1.

666
00:51:39,110 --> 00:51:41,300
Taigi, aš persikėlė į dešinę, todėl, jei dešinę = 1,

667
00:51:41,300 --> 00:51:45,130
ir aš manau, jūs taip pat norite padaryti, -

668
00:51:45,130 --> 00:51:48,530
jei jums judėti į kairę, norite nustatyti lygi 0.

669
00:51:48,530 --> 00:51:55,950
Ar kitur, jei jūs kada nors perkelti į dešinę.

670
00:51:55,950 --> 00:51:58,590
Kad teisė = 0. Jei dešinėje = ​​1,

671
00:51:58,590 --> 00:52:04,260
dabar mes norime, kad patronuojančiai tinkamą rodyklė newnode

672
00:52:04,260 --> 00:52:08,520
dar norime, kad patronuojančiai kairę rodyklę newnode.

673
00:52:08,520 --> 00:52:16,850
Turite klausimų apie tai?

674
00:52:16,850 --> 00:52:24,880
Gerai. Taigi tai yra būdas, kuriuo mes - gerai, iš tikrųjų, o ne tai padaryti,

675
00:52:24,880 --> 00:52:29,630
mes 1/2, tikimasi jums naudoti build_node.

676
00:52:29,630 --> 00:52:40,450
Ir tada, jei newnode lygus nuliui, gražins false.

677
00:52:40,450 --> 00:52:44,170
Tai, kad. Dabar, tai yra tai, ką mes tikėjomės jums reikia padaryti.

678
00:52:44,170 --> 00:52:47,690
>> Tai yra, ką darbuotojai sprendimai padaryti.

679
00:52:47,690 --> 00:52:52,360
Nesutinku su "teisingu" būdu vyksta apie tai

680
00:52:52,360 --> 00:52:57,820
bet tai yra visiškai gerai, ir ji veiks.

681
00:52:57,820 --> 00:53:02,840
Vienas dalykas, kad šiek tiek keista dabar

682
00:53:02,840 --> 00:53:08,310
jei medis prasideda netekusiais, mes pereiname neapibrėžta medžio.

683
00:53:08,310 --> 00:53:12,650
Manau, tai priklauso nuo to, kaip jūs nustatote perduoti neapibrėžta medžio elgesį.

684
00:53:12,650 --> 00:53:15,490
Manyčiau, kad jei pereisite neapibrėžta medžio,

685
00:53:15,490 --> 00:53:17,520
įterpiant vertę į neapibrėžta medis

686
00:53:17,520 --> 00:53:23,030
tiesiog reikia grįžti į medį, kur tik vertė yra tai, kad vienas mazgas.

687
00:53:23,030 --> 00:53:25,830
Žmonės sutinka su tuo? Tu gali, jei norite,

688
00:53:25,830 --> 00:53:28,050
, jei pereisite neapibrėžta medžio

689
00:53:28,050 --> 00:53:31,320
ir norite įterpti reikšmės į, gražins false.

690
00:53:31,320 --> 00:53:33,830
Tai iki jums nustatyti, kad.

691
00:53:33,830 --> 00:53:38,320
Norėdami tai padaryti pirmas dalykas, kurį pasakiau ir tada -

692
00:53:38,320 --> 00:53:40,720
Na, jūs ketinate turėti sunku daryti, kad, nes

693
00:53:40,720 --> 00:53:44,090
būtų lengviau, jei mes turėjome pasaulio žymeklį į dalykas,

694
00:53:44,090 --> 00:53:48,570
bet mes neturime, todėl jei medis yra niekinis, ten nieko mes galime padaryti apie tai.

695
00:53:48,570 --> 00:53:50,960
Mes galime tik grįžti klaidinga.

696
00:53:50,960 --> 00:53:52,840
Taigi, aš ruošiuosi pakeisti įdėklą.

697
00:53:52,840 --> 00:53:56,540
Techniškai galima tiesiog pakeisti šią teisę,

698
00:53:56,540 --> 00:53:58,400
kaip tai iteravimu užkliuvę,

699
00:53:58,400 --> 00:54:04,530
bet aš ruošiuosi pakeisti įdėklą mazgas ** medį.

700
00:54:04,530 --> 00:54:07,510
Dvigulės patarimų.

701
00:54:07,510 --> 00:54:09,710
Ką tai reiškia?

702
00:54:09,710 --> 00:54:12,330
Užuot užsiėmusi nuorodomis mazgams,

703
00:54:12,330 --> 00:54:16,690
ką aš ruošiuosi būti manipuliuoti tai rodyklė.

704
00:54:16,690 --> 00:54:18,790
Aš ruošiuosi manipuliuoti šį žymeklį.

705
00:54:18,790 --> 00:54:21,770
Aš ruošiuosi būti tiesiogiai manipuliuoti patarimų.

706
00:54:21,770 --> 00:54:25,760
Tai logiška, nes, pagalvokite, žemyn -

707
00:54:25,760 --> 00:54:33,340
Na, dabar tai rodo null.

708
00:54:33,340 --> 00:54:38,130
Ką aš noriu padaryti, tai manipuliuoti šį žymiklį į tašką NOT NULL.

709
00:54:38,130 --> 00:54:40,970
Aš noriu, kad mano naujas mazgas.

710
00:54:40,970 --> 00:54:44,870
Jei aš tiesiog sekti mano rodykles patarimų,

711
00:54:44,870 --> 00:54:47,840
tada man nereikia sekti patronuojančios rodyklė.

712
00:54:47,840 --> 00:54:52,640
Aš galiu tik stebėti, norėdami pamatyti, jei yra rodyklė, nukreipta į null,

713
00:54:52,640 --> 00:54:54,580
ir jei rodyklė yra nukreipta į nulis,

714
00:54:54,580 --> 00:54:57,370
jį pakeisti, kad rodytų į mazgą, aš noriu.

715
00:54:57,370 --> 00:55:00,070
Ir aš galiu jį pakeisti,, nes turiu žymeklį į žymeklis.

716
00:55:00,070 --> 00:55:02,040
Pažiūrėkime, tai dabar.

717
00:55:02,040 --> 00:55:05,470
Jūs iš tikrųjų galite tai padaryti rekursyviai gana lengvai.

718
00:55:05,470 --> 00:55:08,080
Ar mes norime tai padaryti?

719
00:55:08,080 --> 00:55:10,980
Taip, mes darome.

720
00:55:10,980 --> 00:55:16,790
>> Pažiūrėkime, jį rekursyviai.

721
00:55:16,790 --> 00:55:24,070
Pirma, kas yra mūsų bazė atveju bus?

722
00:55:24,070 --> 00:55:29,140
Beveik visada mūsų bazinį scenarijų, bet iš tikrųjų, tai yra rūšies sudėtinga.

723
00:55:29,140 --> 00:55:34,370
Pirmasis ko pirma, jei (medis == NULL)

724
00:55:34,370 --> 00:55:37,550
Manau, mes tiesiog ketina grįžti klaidinga.

725
00:55:37,550 --> 00:55:40,460
Tai skiriasi nuo savo medį null.

726
00:55:40,460 --> 00:55:44,510
Tai yra rodyklė į savo šaknų rodyklė null

727
00:55:44,510 --> 00:55:48,360
, o tai reiškia, kad jūsų šakninis rodyklė neegzistuoja.

728
00:55:48,360 --> 00:55:52,390
Tiek žemyn čia, jei aš

729
00:55:52,390 --> 00:55:55,760
mazgas * - tegul tiesiog pakartotinai tai.

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

731
00:55:58,960 --> 00:56:00,730
ir tada aš ruošiuosi skambinti intarpą, daro kažką panašaus,

732
00:56:00,730 --> 00:56:04,540
įterpti į & Root 4.

733
00:56:04,540 --> 00:56:06,560
Taigi, ir šaknis, jei šaknis yra mazgas *

734
00:56:06,560 --> 00:56:11,170
& Root bus mazgas **.

735
00:56:11,170 --> 00:56:15,120
Tai galioja. Šiuo atveju, medis, čia,

736
00:56:15,120 --> 00:56:20,120
medis nėra lygus nuliui, arba įrašyti.

737
00:56:20,120 --> 00:56:24,630
Čia. Medis yra ne null; * medis yra niekinis, kuris yra gerai

738
00:56:24,630 --> 00:56:26,680
nes jei * medis yra niekinis, tada galiu manipuliuoti

739
00:56:26,680 --> 00:56:29,210
atkreipti dėmesį į ką aš noriu atkreipti.

740
00:56:29,210 --> 00:56:34,750
Bet jei medis yra nulis, tai reiškia, kad aš tiesiog atėjo čia ir sakė null.

741
00:56:34,750 --> 00:56:42,710
Tai neturi prasmės. Aš negaliu nieko daryti su tuo.

742
00:56:42,710 --> 00:56:45,540
Jei medis yra niekinis, gražins false.

743
00:56:45,540 --> 00:56:48,220
Taigi, aš iš esmės jau pasakė tai, ką mūsų nekilnojamojo bazinį scenarijų.

744
00:56:48,220 --> 00:56:50,580
Ir kas yra tai, kad bus?

745
00:56:50,580 --> 00:56:55,030
[Studentų, nesuprantamas]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Taip. Taigi, jei (* medis == NULL).

747
00:57:00,000 --> 00:57:04,520
Tai susiję su tuo atveju, čia

748
00:57:04,520 --> 00:57:09,640
kur, jei mano raudona rodyklė rodyklė aš sutelktas į

749
00:57:09,640 --> 00:57:12,960
taip, kaip aš sutelktas į šio rodyklė, dabar aš orientuota į šio rodyklė.

750
00:57:12,960 --> 00:57:15,150
Dabar aš orientuota į šio rodyklė.

751
00:57:15,150 --> 00:57:18,160
Taigi, jei mano raudona rodyklė, kuri yra mano mazgas **

752
00:57:18,160 --> 00:57:22,880
kada nors - jei *, mano raudona rodyklė, kada null,

753
00:57:22,880 --> 00:57:28,470
tai reiškia, kad aš esu tuo atveju, jei aš dėmesio žymeklis, kuris nurodo

754
00:57:28,470 --> 00:57:32,530
tai rodyklę, kad priklauso lapo.

755
00:57:32,530 --> 00:57:41,090
Noriu pakeisti šį žymiklį į mano naujas mazgas.

756
00:57:41,090 --> 00:57:45,230
Grįžti čia.

757
00:57:45,230 --> 00:57:56,490
Mano newnode bus tik mazgas * n = build_node (vertė)

758
00:57:56,490 --> 00:58:07,300
tada n jei n = NULL, gražins false.

759
00:58:07,300 --> 00:58:12,600
Kita mes norime pakeisti tai, kas yra rodyklė, nukreipta į

760
00:58:12,600 --> 00:58:17,830
dabar atkreipti dėmesį į mūsų naujai pastatytas mazgas.

761
00:58:17,830 --> 00:58:20,280
Mes iš tikrųjų galite tai padaryti čia.

762
00:58:20,280 --> 00:58:30,660
Užuot pasakęs n, mes sakome, * = jei * medžio medis.

763
00:58:30,660 --> 00:58:35,450
Visi supranta, kad? , Kad sprendžiant rodykles į rodykles,

764
00:58:35,450 --> 00:58:40,750
mes galime pakeisti tuščių patarimų, atkreipti ką norime nukreipkite jas į.

765
00:58:40,750 --> 00:58:42,820
Štai mūsų bazinį scenarijų.

766
00:58:42,820 --> 00:58:45,740
>> Dabar mūsų pasikartojimo, arba mūsų rekursija,

767
00:58:45,740 --> 00:58:51,430
bus labai panašus į visų kitų recursions, mes buvo padaryti.

768
00:58:51,430 --> 00:58:55,830
Mes ketiname norite įterpti vertę,

769
00:58:55,830 --> 00:58:59,040
ir dabar aš ruošiuosi naudoti trinariu vėl, bet kas yra mūsų sąlyga bus?

770
00:58:59,040 --> 00:59:05,180
Kas tai mes ieškome nuspręsti, ar mes norime eiti į kairę arba į dešinę?

771
00:59:05,180 --> 00:59:07,760
Darykime jį į atskirus žingsnius.

772
00:59:07,760 --> 00:59:18,850
If (vertė <), ką?

773
00:59:18,850 --> 00:59:23,200
[Studentų] The Tree vertė?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Taigi, nepamirškite, kad aš šiuo metu -

775
00:59:27,490 --> 00:59:31,260
[Studentai, nesuprantami]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Taip, kad čia, tarkim, kad tai žalia rodyklė

777
00:59:34,140 --> 00:59:39,050
tai kokiu medžiu šiuo metu yra pavyzdys, yra rodyklė į šio rodyklė.

778
00:59:39,050 --> 00:59:46,610
Taigi, tai reiškia, kad aš esu rodyklė rodyklė į 3.

779
00:59:46,610 --> 00:59:48,800
Dereference du kartus skambėjo gerai.

780
00:59:48,800 --> 00:59:51,010
Tai, ką aš - kaip aš galiu padaryti, kad?

781
00:59:51,010 --> 00:59:53,210
[Studentų] Dereference vieną kartą, ir tada atlikite arrow, kad taip?

782
00:59:53,210 --> 00:59:58,420
[Bowden] (* medis) yra dereference vieną kartą, -> vertė

783
00:59:58,420 --> 01:00:05,960
ketina duoti man mazgo, kad aš netiesiogiai nukreipta į vertę.

784
01:00:05,960 --> 01:00:11,980
, Kad aš taip pat galite rašyti ** tree.value, jei norite, kad.

785
01:00:11,980 --> 01:00:18,490
Bet veikia.

786
01:00:18,490 --> 01:00:26,190
Jei taip yra šiuo atveju, tada aš noriu skambinti įdėkite vertę.

787
01:00:26,190 --> 01:00:32,590
Ir kas mano atnaujinama mazgas ** bus?

788
01:00:32,590 --> 01:00:39,440
Aš noriu eiti į kairę, todėl ** tree.left bus mano kairę.

789
01:00:39,440 --> 01:00:41,900
Ir aš noriu žymiklį į tą daiktą

790
01:00:41,900 --> 01:00:44,930
taip, kad jei kairę baigiasi NULL pointeris,

791
01:00:44,930 --> 01:00:48,360
Galiu keisti, kad rodytų į mano naujas mazgas.

792
01:00:48,360 --> 01:00:51,460
>> Ir kitu atveju gali būti labai panašūs.

793
01:00:51,460 --> 01:00:55,600
Tegul realiai padaryti, kad mano trinariu dabar.

794
01:00:55,600 --> 01:01:04,480
Įterpti vertę jei vertė <(** medis). Vertė.

795
01:01:04,480 --> 01:01:11,040
Tai mes norime atnaujinti savo ** į kairę,

796
01:01:11,040 --> 01:01:17,030
dar norime atnaujinti savo ** į dešinę.

797
01:01:17,030 --> 01:01:22,540
[Studentų] Ar tai gauti žymiklį į žymeklis?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Atminkite, kad - ** tree.right mazgas žvaigždė.

799
01:01:30,940 --> 01:01:35,040
[Studentas, nesuprantamas] >> Taip.

800
01:01:35,040 --> 01:01:41,140
** Tree.right kaip šio rodyklė ar kažką.

801
01:01:41,140 --> 01:01:45,140
Taigi, atsižvelgiant rodyklę į, kuris suteikia man, ką aš noriu

802
01:01:45,140 --> 01:01:50,090
žymeklis, kad vaikinas.

803
01:01:50,090 --> 01:01:54,260
[Studentų] Nepavyko mes einame vėl, kodėl mes naudojame dvi rodykles?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Taip. Taigi - ne, jūs galite, ir kad sprendimas prieš

805
01:01:58,220 --> 01:02:04,540
buvo būdas tai daryti be padaryti du nurodymus.

806
01:02:04,540 --> 01:02:08,740
Jums reikia, kad būtų galima suprasti naudojant dvi rodykles,

807
01:02:08,740 --> 01:02:11,660
ir tai yra švaresnis sprendimas.

808
01:02:11,660 --> 01:02:16,090
Taip pat pastebėsite, kad kas atsitiks, jei mano medis -

809
01:02:16,090 --> 01:02:24,480
kas atsitiks, jei mano šaknys buvo niekinis? Kas atsitiks, jei aš šiuo atveju čia?

810
01:02:24,480 --> 01:02:30,540
Taigi mazgas * šaknis = NULL, įdėkite į & Root 4.

811
01:02:30,540 --> 01:02:35,110
Kas yra Root bus po to?

812
01:02:35,110 --> 01:02:37,470
[Studentas, nesuprantamas] >> Taip.

813
01:02:37,470 --> 01:02:41,710
Šaknis vertė bus 4.

814
01:02:41,710 --> 01:02:45,510
Šaknis į kairę bus niekinis, šaknis teisė bus niekinis.

815
01:02:45,510 --> 01:02:49,490
Tais atvejais, kai mes ne išlaikyti šaknis adresą,

816
01:02:49,490 --> 01:02:52,490
mes negalime pakeisti šaknis.

817
01:02:52,490 --> 01:02:56,020
Tais atvejais, kai medis - šaknys buvo niekinis,

818
01:02:56,020 --> 01:02:58,410
mes tiesiog turėjo grįžti klaidinga. Nėra nieko mes galime padaryti.

819
01:02:58,410 --> 01:03:01,520
Mes negalime įterpti į tuščią medžio mazgas.

820
01:03:01,520 --> 01:03:06,810
Bet dabar mes galime, mes tiesiog padaryti tuščią medį į vieną mazgas medžio.

821
01:03:06,810 --> 01:03:13,400
Kuris paprastai yra numatomas būdas, kad jis turėjo dirbti.

822
01:03:13,400 --> 01:03:21,610
>> Be to, tai yra žymiai trumpesnis nei

823
01:03:21,610 --> 01:03:26,240
taip pat sekti iš tėvų, ir todėl jūs pakartoti visą kelią.

824
01:03:26,240 --> 01:03:30,140
Dabar aš turiu savo tėvų, ir aš tiesiog savo patronuojančiai tinkamą žymeklį į whatever.

825
01:03:30,140 --> 01:03:35,640
Vietoj to, jei mes padarėme tai keletą kartų, tai būčiau tą pačią idėją su while cikle.

826
01:03:35,640 --> 01:03:38,100
Bet vietoj to, kad spręsti su mano tėvų rodyklė,

827
01:03:38,100 --> 01:03:40,600
o mano dabartinis rodyklė būtų dalykas

828
01:03:40,600 --> 01:03:43,790
kad aš tiesiogiai modifikavimo, kad rodytų į mano naujas mazgas.

829
01:03:43,790 --> 01:03:46,090
Aš neturiu spręsti, nesvarbu ar tai būtų nukreipta į kairę.

830
01:03:46,090 --> 01:03:48,810
Aš neturiu spręsti, nesvarbu ar tai būtų nukreipta į dešinę.

831
01:03:48,810 --> 01:04:00,860
Tai tiesiog viskas, ką šis žymeklis, aš ruošiuosi nustatyti, kad jis mano naujas mazgas.

832
01:04:00,860 --> 01:04:05,740
Visi supranta, kaip tai veikia?

833
01:04:05,740 --> 01:04:09,460
Jei ne, kodėl mes norime tai padaryti tokiu būdu,

834
01:04:09,460 --> 01:04:14,920
bet bent jau, kad tai, kaip išspręsti veikia?

835
01:04:14,920 --> 01:04:17,110
[Studentų] Kur mes grįžti tiesa?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Tai turbūt čia.

837
01:04:21,550 --> 01:04:26,690
Jei mes teisingai įdėkite jį, grąžinti tiesa.

838
01:04:26,690 --> 01:04:32,010
Kitur, žemyn čia mes einame, kad nori grįžti, nepriklausomai nuo įterpti grąžą.

839
01:04:32,010 --> 01:04:35,950
>> Ir kas ypatingo apie šį rekursinis funkcija?

840
01:04:35,950 --> 01:04:43,010
Uodega rekursinis, taip ilgai, kaip mes sudaryti su kai kuriais optimizavimo,

841
01:04:43,010 --> 01:04:48,060
bus pripažinti, kad ir jūs niekada gauti nepakeliama,

842
01:04:48,060 --> 01:04:53,230
net jei mūsų medis aukštis 10.000 arba 10 mln.

843
01:04:53,230 --> 01:04:55,630
[Studentų, nesuprantamas]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Manau, kad ji tai daro ne Dash - arba optimizavimas lygis

845
01:05:00,310 --> 01:05:03,820
reikalingas uodegos rekursijos būti pripažintos.

846
01:05:03,820 --> 01:05:09,350
Manau, kad ji pripažįsta - Persijos įlankos bendradarbiavimo tarybos ir Apsukite metalinis garsas

847
01:05:09,350 --> 01:05:12,610
taip pat turi skirtingas reikšmes už jų optimizavimo lygį.

848
01:05:12,610 --> 01:05:17,870
Noriu pasakyti, tai DashO 2, įsitikinkite, kad jis bus pripažinti uodegos rekursija.

849
01:05:17,870 --> 01:05:27,880
Bet mes - galite statyti kaip Fibonocci pavyzdžiui, ar kažką.

850
01:05:27,880 --> 01:05:30,030
Tai nėra lengva išbandyti su tai, nes sunku statyti

851
01:05:30,030 --> 01:05:32,600
dvejetainis medis, tai toks didelis.

852
01:05:32,600 --> 01:05:37,140
Bet taip, manau, kad tai DashO 2, kad

853
01:05:37,140 --> 01:05:40,580
jei sudaryti DashO 2, tai atrodys uodegos rekursijos

854
01:05:40,580 --> 01:05:54,030
ir optimizuoti, kad iš

855
01:05:54,030 --> 01:05:58,190
Grįžkime - įdėkite pažodžiui paskutinis dalykas, kurį jis turi.

856
01:05:58,190 --> 01:06:04,900
Grįžkime įdėklu per čia

857
01:06:04,900 --> 01:06:07,840
kur mes ketiname padaryti tą pačią idėją.

858
01:06:07,840 --> 01:06:14,340
Jis vis dar turite negalės visiškai rankena trūkumus

859
01:06:14,340 --> 01:06:17,940
kai šaknys yra niekinis, ar praeities įrašas yra niekinis,

860
01:06:17,940 --> 01:06:20,060
bet vietoj susijusius su patronuojančios žymeklį,

861
01:06:20,060 --> 01:06:27,430
leisti taikyti tą pačią logiką palaikymo rodykles rodykles.

862
01:06:27,430 --> 01:06:35,580
Jei čia mes išlaikyti mūsų mazgas ** dab,

863
01:06:35,580 --> 01:06:37,860
ir mums nereikia sekti šiuo nebėra

864
01:06:37,860 --> 01:06:47,190
bet mazgas ** dab = & medžiu.

865
01:06:47,190 --> 01:06:54,800
Ir dabar mūsų while cikle bus o * dab nėra lygi null.

866
01:06:54,800 --> 01:07:00,270
Nereikia sekti tėvų nebėra.

867
01:07:00,270 --> 01:07:04,180
Nereikia sekti į kairę ir į dešinę.

868
01:07:04,180 --> 01:07:10,190
Ir aš jums jį vadiname temp, nes mes jau naudojate temp.

869
01:07:10,190 --> 01:07:17,200
Gerai. Taigi, jei (vertė> * temp),

870
01:07:17,200 --> 01:07:24,010
tada & (* temp) -> į dešinę

871
01:07:24,010 --> 01:07:29,250
dar temp = & (* temp) -> paliko.

872
01:07:29,250 --> 01:07:32,730
Ir dabar, šiuo metu, po šio while cikle,

873
01:07:32,730 --> 01:07:36,380
Aš tik tai padaryti, nes gal tai lengviau galvoti apie keletą kartų nei rekursyviai,

874
01:07:36,380 --> 01:07:39,010
bet po šio while cikle,

875
01:07:39,010 --> 01:07:43,820
* Temp tai rodyklė, mes norime pakeisti.

876
01:07:43,820 --> 01:07:48,960
>> Kol mes turėjo tėvų, ir mes norėjome pakeisti į kairę iš tėvų arba vieno iš tėvų teisę,

877
01:07:48,960 --> 01:07:51,310
tačiau, jei norime pakeisti patronuojančiai teisę,

878
01:07:51,310 --> 01:07:54,550
* temperatūra yra tėvų teisė, ir mes galime jį pakeisti tiesiogiai.

879
01:07:54,550 --> 01:08:05,860
Tiek žemyn čia, mes galime padaryti * temp = newnode, ir viskas.

880
01:08:05,860 --> 01:08:09,540
Taigi pranešimo, mes padarėme tai buvo imti eilutes kodo.

881
01:08:09,540 --> 01:08:14,770
Tam, kad sekti visose tėvų, kad yra papildomų pastangų.

882
01:08:14,770 --> 01:08:18,689
Čia, jei mes tiesiog sekti, kad rodyklė prie rodyklė

883
01:08:18,689 --> 01:08:22,990
ir net jei mes norėjome atsikratyti visų šių klamrami dabar,

884
01:08:22,990 --> 01:08:27,170
kad ji atrodo trumpesnis.

885
01:08:27,170 --> 01:08:32,529
Tai dabar yra lygiai toks pats sprendimas,

886
01:08:32,529 --> 01:08:38,210
bet mažiau eilučių kodo.

887
01:08:38,210 --> 01:08:41,229
Kai pradėsite Pripažindama, kad tai tinkamas sprendimas,

888
01:08:41,229 --> 01:08:43,529
jis taip pat lengviau samprotauti apie nei kaip, gerai,

889
01:08:43,529 --> 01:08:45,779
kodėl aš turiu šią vėliavą int teise?

890
01:08:45,779 --> 01:08:49,290
Ką tai reiškia? Oh, tai, reiškiantis, kad

891
01:08:49,290 --> 01:08:51,370
kiekvieną kartą, kai aš einu į dešinę, reikia nustatyti,

892
01:08:51,370 --> 01:08:53,819
dar, jei aš einu į kairę, aš jį nustatyti į nulinę padėtį.

893
01:08:53,819 --> 01:09:04,060
Čia, aš ne apie tai, kad priežastis, tai tiesiog lengviau galvoti apie.

894
01:09:04,060 --> 01:09:06,710
Turite klausimų?

895
01:09:06,710 --> 01:09:16,290
[Studentas, nesuprantamas] >> Taip.

896
01:09:16,290 --> 01:09:23,359
Gerai, kad per pastaruosius tiek

897
01:09:23,359 --> 01:09:28,080
Manau, greitai ir lengvai funkcija, mes galime padaryti,

898
01:09:28,080 --> 01:09:34,910
let's - kartu, manau, išbandyti ir rašyti yra funkcija

899
01:09:34,910 --> 01:09:38,899
nerūpi, ar tai yra dvejetainis paieškos medis.

900
01:09:38,899 --> 01:09:43,770
Tai yra funkcija turėtų grįžti tiesa

901
01:09:43,770 --> 01:09:58,330
jei bet kurios šios bendrosios dvejetainis medis yra vertė, mes ieškome.

902
01:09:58,330 --> 01:10:02,520
Taigi, tegul pirmas tai padaryti rekursyviai ir tada mes tai padaryti keletą kartų.

903
01:10:02,520 --> 01:10:07,300
Mes iš tikrųjų galite tiesiog padaryti jį kartu, nes tai bus tikrai trumpas.

904
01:10:07,300 --> 01:10:11,510
>> Kas yra "Mano bazinį scenarijų bus?

905
01:10:11,510 --> 01:10:13,890
[Studentų, nesuprantamas]

906
01:10:13,890 --> 01:10:18,230
[] Taigi, jei (Bowden medis == NULL), kas tada?

907
01:10:18,230 --> 01:10:22,740
[Studentų] Grįžti klaidinga.

908
01:10:22,740 --> 01:10:26,160
[Bowden] kita, gerai, aš ne reikia kitame.

909
01:10:26,160 --> 01:10:30,250
Jei buvo mano kiti bazinį scenarijų.

910
01:10:30,250 --> 01:10:32,450
[Studentų] Tree vertė? >> Taip.

911
01:10:32,450 --> 01:10:36,430
Taigi, jei (medis-> value == vertė.

912
01:10:36,430 --> 01:10:39,920
Atkreipkite dėmesį, mes grįžome į mazgas *, o ne mazgas ** s?

913
01:10:39,920 --> 01:10:42,990
Yra niekada nereikės naudoti mazgas **

914
01:10:42,990 --> 01:10:45,480
nes mes nesame iš dalies keičiantis patarimų.

915
01:10:45,480 --> 01:10:50,540
Mes tiesiog einant.

916
01:10:50,540 --> 01:10:53,830
Jei tai atsitiks, tada mes norime return true.

917
01:10:53,830 --> 01:10:58,270
Kita, ką norite feed vaikus.

918
01:10:58,270 --> 01:11:02,620
Taigi, mes galime samprotauti apie tai, ar viskas į kairę yra mažiau

919
01:11:02,620 --> 01:11:05,390
ir viskas į dešinę yra didesnis.

920
01:11:05,390 --> 01:11:09,590
Taigi, kas yra mūsų sąlyga bus čia - arba, ką mes ketiname daryti?

921
01:11:09,590 --> 01:11:11,840
[Studentas, nesuprantamas] >> Taip.

922
01:11:11,840 --> 01:11:17,400
Grąža yra (vertė, medis-> kairėje)

923
01:11:17,400 --> 01:11:26,860
arba jame yra (vertė, medis-> dešinėje). Ir viskas.

924
01:11:26,860 --> 01:11:29,080
Ir pastebėsite, kad yra kai trumpojo jungimo vertinimą,

925
01:11:29,080 --> 01:11:32,520
kur, jei atsitiktų rasti kairiajame medžio vertę,

926
01:11:32,520 --> 01:11:36,820
mes niekada nereikės pažvelgti į dešinėje medžio.

927
01:11:36,820 --> 01:11:40,430
Štai visos funkcijos.

928
01:11:40,430 --> 01:11:43,690
Dabar padarykime tai keletą kartų,

929
01:11:43,690 --> 01:11:48,060
bus mažiau gražus.

930
01:11:48,060 --> 01:11:54,750
Mes priimsime įprastą pradžią mazgas * dab = medžio.

931
01:11:54,750 --> 01:12:03,250
Nors (dab! = NULL).

932
01:12:03,250 --> 01:12:08,600
Greitai ketiname pamatyti problemą.

933
01:12:08,600 --> 01:12:12,250
Jei dab - čia, jei mes kada nors išeiti iš šio,

934
01:12:12,250 --> 01:12:16,020
tada mes paleisti iš ką pažvelgti, todėl grįžti klaidinga.

935
01:12:16,020 --> 01:12:24,810
If (dab-> == vertė) return true.

936
01:12:24,810 --> 01:12:32,910
Taigi dabar, mes esame toje pačioje vietoje -

937
01:12:32,910 --> 01:12:36,250
mes nežinome, ar mes norime eiti į kairę arba į dešinę.

938
01:12:36,250 --> 01:12:44,590
Taip savavališkai, galime tiesiog eiti į kairę.

939
01:12:44,590 --> 01:12:47,910
Aš akivaizdžiai paleisti į problemą, kai aš visiškai apleistame viską, -

940
01:12:47,910 --> 01:12:50,760
Aš tik kada nors patikrinti medį kairėje pusėje.

941
01:12:50,760 --> 01:12:56,050
Aš niekada patikrinti nieko, kad yra teisė, vaikas nieko.

942
01:12:56,050 --> 01:13:00,910
Kaip man išspręsti šią problemą?

943
01:13:00,910 --> 01:13:05,260
[Studentų] Jūs turite sekti kairę ir į dešinę kamino.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Taip. Taigi padarykime

945
01:13:13,710 --> 01:13:32,360
struct sąrašas, mazgas * n, tada mazgas ** toliau?

946
01:13:32,360 --> 01:13:40,240
Manau, kad puikiai veikia.

947
01:13:40,240 --> 01:13:45,940
Mes norime eiti per kairėje arba let's - čia.

948
01:13:45,940 --> 01:13:54,350
Struct sąrašas yra =, jis bus pradėti

949
01:13:54,350 --> 01:13:58,170
iš šiuo struct sąrašą.

950
01:13:58,170 --> 01:14:04,040
* Sąrašas = NULL. Taip, kad bus mūsų susieta sąrašas

951
01:14:04,040 --> 01:14:08,430
subtrees, kad mes praleista daugiau.

952
01:14:08,430 --> 01:14:13,800
Mes ketiname feed paliko dabar,

953
01:14:13,800 --> 01:14:17,870
bet kadangi mes neišvengiamai reikia grįžti į dešinę,

954
01:14:17,870 --> 01:14:26,140
Mes ketiname išlaikyti tinkamą pusę, viduje mūsų struct sąrašą.

955
01:14:26,140 --> 01:14:32,620
Tada mes turime new_list arba struct

956
01:14:32,620 --> 01:14:41,080
struct sąrašas * new_list = malloc (sizeof (sąrašas)).

957
01:14:41,080 --> 01:14:44,920
Aš ruošiuosi ignoruoti klaida tikrinant, ar, bet turėtumėte patikrinti, pamatyti, jei ji null.

958
01:14:44,920 --> 01:14:50,540
New_list mazgas, jis ketina atkreipti dėmesį į

959
01:14:50,540 --> 01:14:56,890
oh, tai kodėl aš norėjau jį čia. Jis ketina atkreipti dėmesį į antrą struct sąrašą.

960
01:14:56,890 --> 01:15:02,380
Štai tik tai, kaip jis susijęs sąrašai veiktų.

961
01:15:02,380 --> 01:15:04,810
Tai yra tas pats kaip int susiję sąrašas

962
01:15:04,810 --> 01:15:06,960
, išskyrus tuos atvejus, mes tiesiog pakeisti int mazgas *.

963
01:15:06,960 --> 01:15:11,040
Tai lygiai tas pats.

964
01:15:11,040 --> 01:15:15,100
Taigi new_list, vertė mūsų new_list mazgo,

965
01:15:15,100 --> 01:15:19,120
bus dab-> į dešinę.

966
01:15:19,120 --> 01:15:24,280
Mūsų new_list vertė-> Kitas bus mūsų pradinis sąrašas

967
01:15:24,280 --> 01:15:30,760
ir tada mes ketiname atnaujinti savo sąrašą, kad rodytų į new_list.

968
01:15:30,760 --> 01:15:33,650
>> Dabar mes turime kažkokią būdu pašalintas dalykus,

969
01:15:33,650 --> 01:15:37,020
, kaip mes kertamos visą kairę šaka.

970
01:15:37,020 --> 01:15:40,480
Dabar mes turime traukti dalykų iš jo,

971
01:15:40,480 --> 01:15:43,850
kaip dab yra niekinis, mes nenorime tiesiog gražins false.

972
01:15:43,850 --> 01:15:50,370
Mes norime, kad dabar traukti už mūsų naują sąrašą.

973
01:15:50,370 --> 01:15:53,690
Patogus būdas tai padaryti - gerai, iš tikrųjų, yra daug būdų, kaip tai daryti.

974
01:15:53,690 --> 01:15:56,680
Kas nors turite pasiūlymą?

975
01:15:56,680 --> 01:15:58,790
Kur aš tai padaryti, arba kaip aš turėčiau tai padaryti?

976
01:15:58,790 --> 01:16:08,010
Turime tik keletą minučių, tačiau kokių nors pasiūlymų?

977
01:16:08,010 --> 01:16:14,750
Vietoj to, kad vienas iš būdų, o ne mūsų būklę, o

978
01:16:14,750 --> 01:16:17,090
tai, ką mes šiuo metu ieško NOT NULL,

979
01:16:17,090 --> 01:16:22,340
vietoj to, mes ketiname ir toliau eiti, kol mūsų sąrašas pati yra niekinis.

980
01:16:22,340 --> 01:16:25,680
Taigi, jei mūsų sąrašą galų gale buvo niekinis,

981
01:16:25,680 --> 01:16:30,680
tada mes paleisti iš dalykų, ieškoti, ieškoti per.

982
01:16:30,680 --> 01:16:39,860
Bet tai reiškia, kad mūsų sąraše yra tik pirmas dalykas, bus pirmą mazgas.

983
01:16:39,860 --> 01:16:49,730
Pats pirmas dalykas bus - mes nebereikia matyti, kad.

984
01:16:49,730 --> 01:16:58,710
Taigi sąrašas-> n bus mūsų medžio.

985
01:16:58,710 --> 01:17:02,860
sąrašas-> Kitas bus niekinis.

986
01:17:02,860 --> 01:17:07,580
Ir dabar, o sąrašas nėra lygi null.

987
01:17:07,580 --> 01:17:11,610
Dab ketina traukti ką nors iš mūsų sąraše.

988
01:17:11,610 --> 01:17:13,500
Taigi dab ketina vienodo sąrašo> N.

989
01:17:13,500 --> 01:17:20,850
Ir tada sąrašas vienodo sąrašo> N arba sąrašo> Toliau.

990
01:17:20,850 --> 01:17:23,480
Taigi, jei dab vertė lygi vertę.

991
01:17:23,480 --> 01:17:28,790
Dabar mes galime įdėti mūsų teisę žymeklį ir mūsų kairę rodyklę

992
01:17:28,790 --> 01:17:32,900
tol, kol jie nėra lygus nuliui.

993
01:17:32,900 --> 01:17:36,390
Žemyn čia, aš manau, mes turėtume padaryti, kad į pirmąją vietą.

994
01:17:36,390 --> 01:17:44,080
If (dab-> teisus! = NULL)

995
01:17:44,080 --> 01:17:56,380
tada mes ketiname įterpti tą mazgą į mūsų sąrašą.

996
01:17:56,380 --> 01:17:59,290
If (dab-> į kairę), tai yra šiek tiek papildomo darbo, bet tai gerai.

997
01:17:59,290 --> 01:18:02,690
If (dab-> kairę! = NULL),

998
01:18:02,690 --> 01:18:14,310
ir mes ketiname įterpti į kairę į mūsų susijusi sąrašą,

999
01:18:14,310 --> 01:18:19,700
ir kad turėtų būti ji.

1000
01:18:19,700 --> 01:18:22,670
Mes pakartoti - tol, kol mes turime ką nors į mūsų sąrašą,

1001
01:18:22,670 --> 01:18:26,640
mes turime kitą mazgą pažvelgti.

1002
01:18:26,640 --> 01:18:28,920
Taigi, mes ieškome tuo mazgas,

1003
01:18:28,920 --> 01:18:31,390
mes iš anksto mūsų sąrašą į kitą.

1004
01:18:31,390 --> 01:18:34,060
Jei tai mazgas yra vertė, mes ieškome, mes galime grįžti tiesa.

1005
01:18:34,060 --> 01:18:37,640
Kita įterpti tiek savo kairę ir į dešinę subtrees

1006
01:18:37,640 --> 01:18:40,510
tol, kol jie nėra lygus nuliui, į mūsų sąrašą

1007
01:18:40,510 --> 01:18:43,120
kad mes neišvengiamai pereiti per juos.

1008
01:18:43,120 --> 01:18:45,160
Taigi, jei jie nebuvo niekiniai,

1009
01:18:45,160 --> 01:18:47,950
jei mūsų šaknis rodyklė atkreipė dėmesį į du dalykus.

1010
01:18:47,950 --> 01:18:51,670
tada pirma, ką mes iškedentas, todėl mūsų sąraše baigiasi yra niekinis.

1011
01:18:51,670 --> 01:18:56,890
Ir tada mes įdėti du dalykus atgal, todėl dabar mūsų sąraše yra 2 dydžio.

1012
01:18:56,890 --> 01:19:00,030
Tada mes kilpa atgal į viršų ir mes tiesiog ketina traukti,

1013
01:19:00,030 --> 01:19:04,250
tarkim, kairįjį pelės žymeklį mūsų šakninis mazgas.

1014
01:19:04,250 --> 01:19:07,730
Ir kad bus tiesiog laikyti vyksta, mes galų gale kilpų virš visko.

1015
01:19:07,730 --> 01:19:11,280
>> Atkreipkite dėmesį, kad tai buvo gerokai sudėtingesnis

1016
01:19:11,280 --> 01:19:14,160
rekursinis tirpale.

1017
01:19:14,160 --> 01:19:17,260
Ir aš sakė kelis kartus

1018
01:19:17,260 --> 01:19:25,120
kad rekursinis sprendimas paprastai turi daug bendro su pasikartojantis sprendimą.

1019
01:19:25,120 --> 01:19:30,820
Čia būtent tai rekursinis sprendimas daro.

1020
01:19:30,820 --> 01:19:36,740
Vienintelis pakeitimas yra tai, kad, užuot netiesiogiai naudojant krūvą, programa kamino,

1021
01:19:36,740 --> 01:19:40,840
jūsų būdas sekti ką mazgai, jūs vis dar reikia aplankyti

1022
01:19:40,840 --> 01:19:45,430
dabar jūs turite aiškiai susietą sąrašą.

1023
01:19:45,430 --> 01:19:49,070
Abiem atvejais jūs sekti ką mazgas dar reikia lankėsi.

1024
01:19:49,070 --> 01:19:51,790
Rekursinis atveju tai tik lengviau, nes kamino

1025
01:19:51,790 --> 01:19:57,100
įgyvendinamos programos kamino.

1026
01:19:57,100 --> 01:19:59,550
Atkreipkite dėmesį, kad tai susijęs sąrašas, tai kamino.

1027
01:19:59,550 --> 01:20:01,580
Ką mes tiesiog įdėti į steką

1028
01:20:01,580 --> 01:20:09,960
iš karto, ką mes ketiname nutempti pluoštą ir aplankyti kitas.

1029
01:20:09,960 --> 01:20:14,380
Mes laiko, bet kokių nors klausimų?

1030
01:20:14,380 --> 01:20:23,530
[Studentų, nesuprantamas]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Taip. Taigi, jei mes turime susietą sąrašą,

1032
01:20:27,790 --> 01:20:30,150
dabartinis vyksta šis vaikinas,

1033
01:20:30,150 --> 01:20:34,690
ir dabar mes tiesiog plečiant mūsų susietą sąrašą sutelkti dėmesį į šį vaikiną.

1034
01:20:34,690 --> 01:20:44,200
Mes kirsti tos linijos per susietą sąrašą.

1035
01:20:44,200 --> 01:20:51,200
Ir tada aš manau, kad mes turėtų išlaisvinti mūsų susietą sąrašą ir kita

1036
01:20:51,200 --> 01:20:53,880
kartą prieš grįžtant true arba false, turime

1037
01:20:53,880 --> 01:20:57,360
pakartoti per Susietos sąrašą ir visada žemyn čia, manau,

1038
01:20:57,360 --> 01:21:03,900
jei mes dab teisė nėra lygus, įtraukite ją, todėl dabar mes norime išlaisvinti

1039
01:21:03,900 --> 01:21:09,600
dab nes, gerai, tai mes visiškai pamiršti apie šį sąrašą? Taip.

1040
01:21:09,600 --> 01:21:12,880
Todėl tai, ką mes norime padaryti čia.

1041
01:21:12,880 --> 01:21:16,730
Kur yra žymeklis?

1042
01:21:16,730 --> 01:21:23,320
Dab buvo tada - mes norime, struct sąrašą * 10 lygu sąrašą šalia.

1043
01:21:23,320 --> 01:21:29,240
Nemokama sąrašą, sąrašas = temp.

1044
01:21:29,240 --> 01:21:32,820
Ir tuo atveju, kai mes grįžtame tiesa, mes reikia pakartoti

1045
01:21:32,820 --> 01:21:37,050
per likusį mūsų susietą sąrašą nutekamosios dalykų.

1046
01:21:37,050 --> 01:21:39,700
Gražus dalykas, apie grįžtamojo sprendimas atlaisvinti dalykus

1047
01:21:39,700 --> 01:21:44,930
tiesiog reiškia, Popping factorings off kamino, kuris įvyks jums.

1048
01:21:44,930 --> 01:21:50,720
Taigi, mes perėjome nuo ko nors, kad kaip 3 eilutes sunkiai manote apie kodą

1049
01:21:50,720 --> 01:21:57,520
kažką, kad yra žymiai daug daugiau sunku-manote-apie eilučių kodo.

1050
01:21:57,520 --> 01:22:00,620
Ar turite klausimų?

1051
01:22:00,620 --> 01:22:08,760
Gerai. Mes geri. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]