1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Odjeljak 7: ugodnije]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Sveučilište Harvard]

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

4
00:00:07,930 --> 00:00:10,110
U redu. Dakle, kao što sam rekao u mom e-pošte,

5
00:00:10,110 --> 00:00:14,060
ovo će biti binarno stablo intenzivni odjel.

6
00:00:14,060 --> 00:00:16,820
No, tu se ne da mnogo pitanja.

7
00:00:16,820 --> 00:00:18,920
Tako ćemo pokušati izvući na svako pitanje

8
00:00:18,920 --> 00:00:25,430
i ići u bolne detalje svih najboljih načina obavljanja stvari.

9
00:00:25,430 --> 00:00:31,200
Dakle, odmah na početku, idemo kroz uzorak crteža binarnih stabala i slično.

10
00:00:31,200 --> 00:00:35,970
Dakle, ovdje, "Sjetite se da binarno stablo ima čvorove slične onima povezane liste,

11
00:00:35,970 --> 00:00:38,150
osim umjesto jednog pokazivača postoje dva: jedan za lijevi 'dijete'

12
00:00:38,150 --> 00:00:41,950
i jedan za pravo 'dijete'. "

13
00:00:41,950 --> 00:00:45,630
Dakle binarno stablo je baš kao i povezanog popisa,

14
00:00:45,630 --> 00:00:47,910
osim struct će imati dva pokazivača.

15
00:00:47,910 --> 00:00:51,390
Tu je trinary stabala, koji će imati tri pokazivače,

16
00:00:51,390 --> 00:00:56,540
postoje N-arna stabla, koje samo imaju generički pokazivač

17
00:00:56,540 --> 00:01:00,320
da li onda moram malloc biti dovoljno velik da imaju

18
00:01:00,320 --> 00:01:04,840
dovoljno upućuje na svim mogućim djece.

19
00:01:04,840 --> 00:01:08,200
Dakle binarno stablo jednostavno dogodi da imaju stalan broj dva.

20
00:01:08,200 --> 00:01:11,260
Ako želite, možete dati povezanu popis kao predznak stabla,

21
00:01:11,260 --> 00:01:15,360
ali ja ne mislim da itko zove to da.

22
00:01:15,360 --> 00:01:18,060
"Nacrtaj kutije-i-strelice dijagram binarnog stabla čvor

23
00:01:18,060 --> 00:01:24,110
sadrži Nate je omiljeni broj 7, gdje će svako dijete pokazivač je null. "

24
00:01:24,110 --> 00:01:27,780
Dakle ipad način.

25
00:01:27,780 --> 00:01:30,280
>> To će biti prilično jednostavan.

26
00:01:30,280 --> 00:01:36,150
Mi samo ćeš imati čvor, ja ću ga izvući kao trga.

27
00:01:36,150 --> 00:01:38,730
I ja ću nacrtati vrijednosti ovdje.

28
00:01:38,730 --> 00:01:41,090
Tako je vrijednost će ići ovdje,

29
00:01:41,090 --> 00:01:44,770
i onda ovdje ćemo morati lijevu pokazivač na lijevo i desno pokazivač na desnoj strani.

30
00:01:44,770 --> 00:01:50,430
I to je jako puno tako konvenciji da ga zovu lijevo i desno, pokazivač imena.

31
00:01:50,430 --> 00:01:52,460
Oba će biti nula.

32
00:01:52,460 --> 00:01:57,870
To će samo biti nula, i da će samo biti nula.

33
00:01:57,870 --> 00:02:03,630
Ok. Dakle, natrag na ovdje.

34
00:02:03,630 --> 00:02:05,700
"S povezane popisu, samo mi morali pohraniti pokazivač

35
00:02:05,700 --> 00:02:09,639
na prvi čvor u popisu kako bi se sjetiti cijeli povezanog popisa, ili cijeli popis.

36
00:02:09,639 --> 00:02:11,650
Isto tako, s drvećem, imamo samo za pohranu pokazivač

37
00:02:11,650 --> 00:02:13,420
na jednom čvoru kako bi se sjetiti cijeli stablo.

38
00:02:13,420 --> 00:02:15,980
Ovaj čvor je calle je 'korijen' od stabla.

39
00:02:15,980 --> 00:02:18,320
Graditi na slici, od prije ili privući novu

40
00:02:18,320 --> 00:02:21,690
kao da imate kutije-i-strelice prikazom binarnog stabla

41
00:02:21,690 --> 00:02:25,730
s vrijednost 7, a zatim 3 u lijevo,

42
00:02:25,730 --> 00:02:32,760
zatim 9 na desnoj strani, a zatim 6 na desno od 3 ".

43
00:02:32,760 --> 00:02:34,810
Idemo vidjeti ako ja mogu sjetiti svega toga u mojoj glavi.

44
00:02:34,810 --> 00:02:37,670
Dakle, ovo će biti naš korijen ovdje.

45
00:02:37,670 --> 00:02:41,600
Mi ćemo imati neki pokazivač negdje, nešto što ćemo nazvati korijen,

46
00:02:41,600 --> 00:02:45,140
i to je pokazujući na ovim tipom.

47
00:02:45,140 --> 00:02:48,490
Sada bi novi čvor,

48
00:02:48,490 --> 00:02:52,870
što imamo, 3 na lijevoj strani?

49
00:02:52,870 --> 00:02:57,140
Dakle, novi čvor s tri, i to na početku ističe null.

50
00:02:57,140 --> 00:02:59,190
Ja ću samo staviti N.

51
00:02:59,190 --> 00:03:02,250
Sada želimo napraviti da ide s lijeve strane 7.

52
00:03:02,250 --> 00:03:06,840
Tako ćemo promijeniti ovu pokazivač do sada ukazuju na ovim tipom.

53
00:03:06,840 --> 00:03:12,420
I mi isto. Želimo 9 ovamo

54
00:03:12,420 --> 00:03:14,620
koji je u početku samo kaže null.

55
00:03:14,620 --> 00:03:19,600
Mi ćemo promijeniti ovu pokazivača, pokažite na devet,

56
00:03:19,600 --> 00:03:23,310
a sada želimo staviti šest na desnoj 3.

57
00:03:23,310 --> 00:03:32,170
Dakle, to će - napraviti šest.

58
00:03:32,170 --> 00:03:34,310
A taj čovjek će ukazati postoji.

59
00:03:34,310 --> 00:03:38,320
Ok. Dakle, to je sve što od nas traži da učiniti.

60
00:03:38,320 --> 00:03:42,770
>> Sada idemo preko neke terminologije.

61
00:03:42,770 --> 00:03:46,690
Već smo razgovarali o tome kako je korijen stabla je top-najviše čvor u stablu.

62
00:03:46,690 --> 00:03:54,720
Jedan sadrži sedam. Čvorovi na dnu stabla nazivaju se lišće.

63
00:03:54,720 --> 00:04:01,240
Svaki čvor koji ima samo null kao svoje djece je list.

64
00:04:01,240 --> 00:04:03,680
Dakle, to je moguće, ako je naš binarno stablo je samo jedan čvor,

65
00:04:03,680 --> 00:04:10,130
da je stablo list, i to je to.

66
00:04:10,130 --> 00:04:12,060
"The 'Visina' od stabla je broj hmelja morate napraviti

67
00:04:12,060 --> 00:04:16,620
dobiti od vrha do list ".

68
00:04:16,620 --> 00:04:18,640
Mi ćemo ući u, u drugi, razliku

69
00:04:18,640 --> 00:04:21,940
između uravnoteženih i neuravnotežena binarnih stabala,

70
00:04:21,940 --> 00:04:29,470
ali za sada, ukupna visina ovog stabla

71
00:04:29,470 --> 00:04:34,520
Rekao bih da je 3, iako ako računamo broj skokova

72
00:04:34,520 --> 00:04:39,710
morate napraviti kako bi se doći do 9, onda je to stvarno samo visina 2.

73
00:04:39,710 --> 00:04:43,340
Upravo sada je to neuravnotežena binarno stablo,

74
00:04:43,340 --> 00:04:49,840
ali ćemo razgovarali o uravnotežena kad se dobiva biti relevantan.

75
00:04:49,840 --> 00:04:52,040
Dakle, sada možemo govoriti o čvorova u stablu u smislu

76
00:04:52,040 --> 00:04:54,700
u odnosu na ostale čvorove u stablu.

77
00:04:54,700 --> 00:04:59,730
Tako sada imamo roditelje, djecu, braću i sestre, predaka, potomaka.

78
00:04:59,730 --> 00:05:05,650
Oni su prilično zdrav razum, što oni znače.

79
00:05:05,650 --> 00:05:09,610
Ako pitamo - to je roditelje.

80
00:05:09,610 --> 00:05:12,830
Dakle, ono što je roditelj 3?

81
00:05:12,830 --> 00:05:16,090
[Studenti] 7. >> Da. Roditelj samo će biti ono što ukazuje na vas.

82
00:05:16,090 --> 00:05:20,510
Onda ono što su djeca 7?

83
00:05:20,510 --> 00:05:23,860
[Studenti] 3 i 9. >> Da.

84
00:05:23,860 --> 00:05:26,460
Obavijest da "djeca" doslovno znači djecu,

85
00:05:26,460 --> 00:05:31,010
pa 6 neće primijeniti, jer to je kao unuka.

86
00:05:31,010 --> 00:05:35,540
Ali onda ako idemo potomke, tako što su potomci 7?

87
00:05:35,540 --> 00:05:37,500
[Studenti] 3, 6 i 9. >> Da.

88
00:05:37,500 --> 00:05:42,330
Potomci root čvor će biti sve u drvetu,

89
00:05:42,330 --> 00:05:47,950
osim možda korijen čvor sama, ako ne želite uzeti u obzir da je potomak.

90
00:05:47,950 --> 00:05:50,750
I konačno, preci, tako da je suprotnom smjeru.

91
00:05:50,750 --> 00:05:55,740
Dakle, ono što su preci 6?

92
00:05:55,740 --> 00:05:58,920
[Studenti] 3 i 7. >> Da. 9 nije uključena.

93
00:05:58,920 --> 00:06:02,520
To je samo izravna linija natrag do korijena

94
00:06:02,520 --> 00:06:13,230
će biti vaši preci.

95
00:06:13,230 --> 00:06:16,300
>> "Mi kažemo da je binarno stablo je" naredio "da za svaki čvor u stablu,

96
00:06:16,300 --> 00:06:19,530
sve svoje potomke na lijevoj strani imaju manje vrijednosti

97
00:06:19,530 --> 00:06:22,890
i sve one na desnoj strani imaju veće vrijednosti.

98
00:06:22,890 --> 00:06:27,060
Na primjer, stablo iznad naredio, ali to nije jedino moguće naručiti aranžman. "

99
00:06:27,060 --> 00:06:30,180
Prije nego što smo dobili na to,

100
00:06:30,180 --> 00:06:36,420
naredio binarno stablo je također poznat kao binarni pretraživanje stabla.

101
00:06:36,420 --> 00:06:38,660
Ovdje ćemo se dogoditi da se nazivajući ga je naredio binarnog stabla,

102
00:06:38,660 --> 00:06:41,850
ali nikada nisam čuo da se zove naredio binarno stablo prije,

103
00:06:41,850 --> 00:06:46,650
i na kvizu smo mnogo više vjerojatno da će staviti binarnog stabla pretraživanja.

104
00:06:46,650 --> 00:06:49,250
Oni su jedna te ista,

105
00:06:49,250 --> 00:06:54,580
i to je važno da prepoznaju razliku između binarnog stabla i binarnog stabla pretraživanja.

106
00:06:54,580 --> 00:06:58,830
Binarno stablo je samo stablo koje ukazuje na dvije stvari.

107
00:06:58,830 --> 00:07:02,120
Svaki čvor ukazuje na dvije stvari.

108
00:07:02,120 --> 00:07:06,310
Nema razmišljanje o vrijednostima koje to ukazuje na.

109
00:07:06,310 --> 00:07:11,370
Tako se sviđa ovdje, jer je binarno stablo pretraživanja,

110
00:07:11,370 --> 00:07:14,030
znamo da ako idemo lijevo od 7,

111
00:07:14,030 --> 00:07:16,670
onda sve vrijednosti koje smo eventualno mogu doći

112
00:07:16,670 --> 00:07:19,310
odlaskom lijevo od sedam moraju biti manje od sedam.

113
00:07:19,310 --> 00:07:24,070
Primijetit ćete da su sve vrijednosti manje od 7 su tri i šest.

114
00:07:24,070 --> 00:07:26,040
Oni su svi s lijeve strane 7.

115
00:07:26,040 --> 00:07:29,020
Ako idemo na desnoj 7, sve mora biti veći od sedam,

116
00:07:29,020 --> 00:07:33,220
pa 9 je na desnoj strani 7, tako da smo dobri.

117
00:07:33,220 --> 00:07:36,150
To nije slučaj za binarno stablo,

118
00:07:36,150 --> 00:07:40,020
za redovite binarnog stabla možemo samo imati tri na vrhu, sedam na lijevoj strani,

119
00:07:40,020 --> 00:07:47,630
9 na lijevoj 7; nema naručivanje vrijednosti bilo koje vrste.

120
00:07:47,630 --> 00:07:56,140
Sada, mi zapravo neće to učiniti, jer to je zamorno i nepotrebno,

121
00:07:56,140 --> 00:07:59,400
ali "pokušati izvući što više naručili stabala kao što možete zamisliti

122
00:07:59,400 --> 00:08:01,900
koristeći brojeve 7, 3, 9, i 6.

123
00:08:01,900 --> 00:08:06,800
Koliko različita rješenja postoje? Koja je visina svakog jedan? "

124
00:08:06,800 --> 00:08:10,480
>> Mi ćemo napraviti par, ali glavna ideja je,

125
00:08:10,480 --> 00:08:16,530
ovo je ni na koji način jedinstveni prikaz binarnog stabla sadrži ove vrijednosti.

126
00:08:16,530 --> 00:08:22,760
Sve što trebate je neki binarno stablo koje sadrži 7, 3, 6 i 9.

127
00:08:22,760 --> 00:08:25,960
Drugi mogući vrijedi jedan će biti korijen je 3,

128
00:08:25,960 --> 00:08:30,260
idite na lijevo, a to je 6, idite na lijevo, a to je 7,

129
00:08:30,260 --> 00:08:32,730
idite na lijevo, a to je 9.

130
00:08:32,730 --> 00:08:36,169
To je savršeno valjana binarno stablo pretraživanja.

131
00:08:36,169 --> 00:08:39,570
To nije vrlo korisno, jer to je isto kao povezane liste

132
00:08:39,570 --> 00:08:43,750
i sve ove naputke su samo null.

133
00:08:43,750 --> 00:08:48,900
Ali, to je valjan stablo. Da?

134
00:08:48,900 --> 00:08:51,310
[Studentski] Zar vrijednosti moraju biti veći na desnoj strani?

135
00:08:51,310 --> 00:08:56,700
Ili je to -? >> To sam trebao ići na drugi način.

136
00:08:56,700 --> 00:09:00,960
Tu je i - da, ajmo prebaciti da.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Dobar ulov.

138
00:09:07,770 --> 00:09:11,730
Ona još uvijek ima da slušaju ono što traži binarno stablo je trebalo učiniti.

139
00:09:11,730 --> 00:09:15,650
Dakle, sve na lijevoj strani mora biti manje od bilo kojeg čvora.

140
00:09:15,650 --> 00:09:23,180
Mi samo mogao pomaknuti, recimo, ovaj šest i staviti ga ovdje.

141
00:09:23,180 --> 00:09:26,880
Ne, ne možemo. Zašto sam zadržati taj događaj?

142
00:09:26,880 --> 00:09:35,350
Učinimo - ovdje je 6, ovdje je 7, 6 bodova u tri.

143
00:09:35,350 --> 00:09:39,290
To je još uvijek vrijedi binarno stablo pretraživanja.

144
00:09:39,290 --> 00:09:49,260
Što je krivo, ako sam - ajmo vidjeti ako ja mogu doći do dogovora.

145
00:09:49,260 --> 00:09:52,280
Da, u redu. Dakle, ono što je krivo s ovom stablu?

146
00:09:52,280 --> 00:10:08,920
Valjda sam već dao naslutiti da nešto nije u redu s njim.

147
00:10:08,920 --> 00:10:14,430
Zašto sam zadržati taj događaj?

148
00:10:14,430 --> 00:10:18,510
Ok. Ovo izgleda razumno.

149
00:10:18,510 --> 00:10:22,590
Ako gledamo na svakom čvoru, kao i sedam, a zatim s lijeve strane 7 je tri.

150
00:10:22,590 --> 00:10:24,960
Dakle, imamo tri, stvar s desne strane 3 je šest.

151
00:10:24,960 --> 00:10:27,750
A ako pogledate 6, stvar na pravo 6 je devet.

152
00:10:27,750 --> 00:10:30,910
Pa zašto je to ne vrijedi binarno pretraživanje stablo?

153
00:10:30,910 --> 00:10:36,330
[Studenti] 9 je još uvijek na lijevoj 7. >> Da.

154
00:10:36,330 --> 00:10:43,710
To mora biti istina da su sve vrijednosti koje eventualno mogu doći tako da odete na lijevoj sedam manje od sedam.

155
00:10:43,710 --> 00:10:49,120
Ako idemo lijevo od sedam, možemo doći do tri, a mi još uvijek može doći do 6,

156
00:10:49,120 --> 00:10:52,520
još uvijek možemo doći do 9, ali nakon što je otišao manje od 7,

157
00:10:52,520 --> 00:10:55,070
ne bismo trebali biti u mogućnosti doći do broja koji je veći od 7.

158
00:10:55,070 --> 00:10:59,830
Dakle, to nije valjan binarno stablo pretraživanja.

159
00:10:59,830 --> 00:11:02,330
>> Moj brat je zapravo imao intervju pitanje

160
00:11:02,330 --> 00:11:07,760
da je u osnovi to, samo kod se nešto kako bismo provjerili

161
00:11:07,760 --> 00:11:10,500
da li je stablo binarno pretraživanje stablo,

162
00:11:10,500 --> 00:11:13,580
i tako prva stvar koju je učinio bila samo provjeriti

163
00:11:13,580 --> 00:11:17,020
ako je lijevo i desno su točne, a zatim ponoviti tamo dolje.

164
00:11:17,020 --> 00:11:19,700
No, ne možete samo to učiniti, morate pratiti

165
00:11:19,700 --> 00:11:22,550
činjenice da je sada da sam otišao lijevo od 7,

166
00:11:22,550 --> 00:11:26,340
Sve u ovom podstablo mora biti manji od sedam.

167
00:11:26,340 --> 00:11:28,430
Ispravan algoritam treba pratiti

168
00:11:28,430 --> 00:11:35,970
od granica koje su vrijednosti eventualno može pasti u.

169
00:11:35,970 --> 00:11:38,360
Nećemo proći kroz sve njih.

170
00:11:38,360 --> 00:11:41,630
Tu je lijepo ponavljanje odnos,

171
00:11:41,630 --> 00:11:44,810
iako nismo došli do njih, ili nećemo doći do onih,

172
00:11:44,810 --> 00:11:47,030
definiranje koliko ima zapravo jesu.

173
00:11:47,030 --> 00:11:53,180
Dakle, tu su 14 od njih.

174
00:11:53,180 --> 00:11:56,020
Ideja o tome kako bi to matematički je kao,

175
00:11:56,020 --> 00:11:59,770
možete odabrati bilo ni jedan da se korijen čvor,

176
00:11:59,770 --> 00:12:03,160
i onda ako sam pokupiti 7 biti korijen čvor,

177
00:12:03,160 --> 00:12:08,150
zatim tu su, recimo, neki brojevi koji mogu ići biti moj lijevi čvor,

178
00:12:08,150 --> 00:12:10,440
a tu su i neki brojevi koji mogu biti moje pravo čvor,

179
00:12:10,440 --> 00:12:15,090
ali ako sam n ukupan broj, onda je iznos koji se može ići na lijevo

180
00:12:15,090 --> 00:12:18,820
uvećan za iznos koji se može ići na pravo je n - 1.

181
00:12:18,820 --> 00:12:26,130
Dakle, od preostalih brojeva, oni moraju biti u mogućnosti otići ni lijevo ili desno.

182
00:12:26,130 --> 00:12:31,580
Čini se da je teško, ako sam stavio 3 prvi onda sve mora ići na lijevoj strani,

183
00:12:31,580 --> 00:12:35,080
ali ako sam stavio 7, onda se neke stvari mogu ići na lijevo i neke stvari mogu ići desno.

184
00:12:35,080 --> 00:12:39,570
I '3 prvi 'Mislio sam sve što se može ići desno.

185
00:12:39,570 --> 00:12:42,350
To je stvarno, samo morate razmišljati o tome što,

186
00:12:42,350 --> 00:12:47,980
koliko stvari mogu ići na sljedeću razinu od stabla.

187
00:12:47,980 --> 00:12:50,420
I to dolazi od biti 14, ili možete izvući sve od njih,

188
00:12:50,420 --> 00:12:54,650
i onda ćete dobiti 14.

189
00:12:54,650 --> 00:13:01,120
>> Vraćajući se ovdje,

190
00:13:01,120 --> 00:13:03,510
"Naredio binarni stabla su kul jer možemo tražiti kroz njih

191
00:13:03,510 --> 00:13:06,910
na vrlo sličan način na potrazi preko sortirani niz.

192
00:13:06,910 --> 00:13:10,120
Da biste to učinili, možemo početi u korijenu i rade svoj put prema dolje stablo

193
00:13:10,120 --> 00:13:13,440
prema lišća, provjeru Svaki čvor je vrijednosti protiv vrijednosti smo u potrazi za.

194
00:13:13,440 --> 00:13:15,810
Ako je trenutni čvora vrijednost manja od vrijednosti tražimo,

195
00:13:15,810 --> 00:13:18,050
idete pokraj čvora pravo djeteta.

196
00:13:18,050 --> 00:13:20,030
Inače, idete na čvor lijevog djeteta.

197
00:13:20,030 --> 00:13:22,800
U nekom trenutku, ili će pronaći vrijednost koju tražite, ili ćete pokrenuti u null,

198
00:13:22,800 --> 00:13:28,520
pokazuje vrijednost nije u stablu. "

199
00:13:28,520 --> 00:13:32,450
Moram ponovno iscrtavanje stablo smo imali prije, da ću uzeti drugi.

200
00:13:32,450 --> 00:13:38,280
No, želimo li pogledati 6, 10, i 1 u stablo.

201
00:13:38,280 --> 00:13:49,180
Dakle, ono što je bilo, 7, 9, 3, 6. Ok.

202
00:13:49,180 --> 00:13:52,730
Brojevi koje žele izgledati gore, želimo gledati 6.

203
00:13:52,730 --> 00:13:55,440
Kako to algoritam rad?

204
00:13:55,440 --> 00:14:03,040
Pa, mi također imaju neke root pokazivač na našem stablu.

205
00:14:03,040 --> 00:14:12,460
I mi bi ići na korijen i reći, je ta vrijednost jednaka vrijednosti smo u potrazi za?

206
00:14:12,460 --> 00:14:15,000
Dakle, mi smo u potrazi za šest, tako da to nije jednaka.

207
00:14:15,000 --> 00:14:20,140
Tako smo zadržati ide, a sada možemo reći, u redu, tako da je manje od šest sedam.

208
00:14:20,140 --> 00:14:23,940
Znači li to da želimo ići lijevo, ili ne želimo ići na pravo?

209
00:14:23,940 --> 00:14:27,340
[Studentski] Left. >> Da.

210
00:14:27,340 --> 00:14:33,340
To je znatno lakše, sve što morate učiniti je izvući jedan mogući čvor stabla

211
00:14:33,340 --> 00:14:37,760
i onda nemojte - umjesto da pokušavate misliti u vašoj glavi,

212
00:14:37,760 --> 00:14:40,020
ok, ako je manje, moram ići lijevo ili ići pravo,

213
00:14:40,020 --> 00:14:43,030
samo gleda na ovoj slici, to je vrlo jasno da moram ići lijevo

214
00:14:43,030 --> 00:14:47,700
ako je to čvor je veća od vrijednosti da sam u potrazi za.

215
00:14:47,700 --> 00:14:52,600
Dakle, idete na lijevoj strani, a sada sam na tri.

216
00:14:52,600 --> 00:14:57,770
Želim - 3 je manje od vrijednosti tražim, što je šest.

217
00:14:57,770 --> 00:15:03,420
Tako smo ići na pravo, a sada sam završiti na šest,

218
00:15:03,420 --> 00:15:07,380
koja je vrijednost tražim, pa sam se vratiti istinito.

219
00:15:07,380 --> 00:15:15,760
Sljedeći vrijednost ću tražiti je 10.

220
00:15:15,760 --> 00:15:23,230
Ok. Dakle, 10, sada se ide - odsječen da - će slijediti korijen.

221
00:15:23,230 --> 00:15:27,670
Sada, 10 će biti veći od sedam, pa želim gledati na desnoj strani.

222
00:15:27,670 --> 00:15:31,660
Ja ću doći ovamo, 10 će biti veći od 9,

223
00:15:31,660 --> 00:15:34,520
pa ću žele izgledati desno.

224
00:15:34,520 --> 00:15:42,100
Ja dolazim ovamo, ali ovdje sada sam na null.

225
00:15:42,100 --> 00:15:44,170
Što trebam učiniti ako sam pogodio null?

226
00:15:44,170 --> 00:15:47,440
[Studentski] Povratak lažno? >> Da. Nisam našao 10.

227
00:15:47,440 --> 00:15:49,800
1 će biti gotovo identičan slučaj,

228
00:15:49,800 --> 00:15:51,950
osim to samo će biti zrcaljeno, umjesto u potrazi

229
00:15:51,950 --> 00:15:56,540
dolje na desnoj strani, ja ću pogledati dolje lijevu stranu.

230
00:15:56,540 --> 00:16:00,430
>> Sada mislim da smo zapravo doći do koda.

231
00:16:00,430 --> 00:16:04,070
Evo gdje - otvaranje CS50 aparat i navigaciju svoj put tamo,

232
00:16:04,070 --> 00:16:07,010
ali također možete samo to učiniti u prostoru.

233
00:16:07,010 --> 00:16:09,170
To je vjerojatno idealno to učiniti u prostoru,

234
00:16:09,170 --> 00:16:13,760
jer možemo raditi u prostoru.

235
00:16:13,760 --> 00:16:19,170
"Prvo ćemo trebati novi tip definiciju za binarnog stabla čvor koji sadrži int vrijednosti.

236
00:16:19,170 --> 00:16:21,400
Koristeći predloženi typedef nastavku,

237
00:16:21,400 --> 00:16:24,510
stvoriti novu definiciju tipa za čvor u binarno stablo.

238
00:16:24,510 --> 00:16:27,930
Ako zapnete. . . "Bla, bla, bla. Ok.

239
00:16:27,930 --> 00:16:30,380
Dakle, neka je stavi predloženi ovdje,

240
00:16:30,380 --> 00:16:41,630
typedef struct čvor, a čvor. Da, u redu.

241
00:16:41,630 --> 00:16:44,270
Dakle, ono što su polja idemo da želite u našoj čvoru?

242
00:16:44,270 --> 00:16:46,520
[Studentski] Int, a zatim dvije pokazivače?

243
00:16:46,520 --> 00:16:49,700
>> Int vrijednost, dva pokazivače? Kako pisati naputke?

244
00:16:49,700 --> 00:16:58,440
[Studentski] struct. >> Ja bi povećali u. Da, tako struct node * lijevo,

245
00:16:58,440 --> 00:17:01,320
i rekonstruirati čvor * desno.

246
00:17:01,320 --> 00:17:03,460
I zapamtite raspravu iz prošlog vremena,

247
00:17:03,460 --> 00:17:15,290
da to nema smisla, to nema smisla,

248
00:17:15,290 --> 00:17:18,270
ovo nema smisla.

249
00:17:18,270 --> 00:17:25,000
Morate sve tamo kako bi se definirati ovaj rekurzivni struct.

250
00:17:25,000 --> 00:17:27,970
Ok, tako da je ono što naša stablo će izgledati.

251
00:17:27,970 --> 00:17:37,670
Ako nismo trinary stablo, onda čvor može izgledati B1, B2, struct node * B3,

252
00:17:37,670 --> 00:17:43,470
gdje je b grana - zapravo, ja sam više čuo je lijevo, sredina, desno, ali bez obzira.

253
00:17:43,470 --> 00:17:55,610
Mi samo stalo binarnom, pa desno, lijevo.

254
00:17:55,610 --> 00:17:59,110
"Sada proglasiti globalnu varijablu * čvor za korijen stabla."

255
00:17:59,110 --> 00:18:01,510
Pa nećemo to učiniti.

256
00:18:01,510 --> 00:18:08,950
Da bi se stvari malo teže i više generalizirati,

257
00:18:08,950 --> 00:18:11,570
nećemo imati globalnu varijablu čvor.

258
00:18:11,570 --> 00:18:16,710
Umjesto toga, u glavnom ćemo proglasiti sve naše čvora stvari,

259
00:18:16,710 --> 00:18:20,500
a to znači da u nastavku, kada smo se početi prikazivati

260
00:18:20,500 --> 00:18:23,130
Sadrži naša funkcija i naša umetak funkcija,

261
00:18:23,130 --> 00:18:27,410
umjesto naših sadrži samo djeluju pomoću ovog globalnog čvora varijablu,

262
00:18:27,410 --> 00:18:34,280
idemo da se to uzeti kao argument stablo koje želimo da obraditi.

263
00:18:34,280 --> 00:18:36,650
Nakon što je globalnu varijablu je trebao kako bi što lakše.

264
00:18:36,650 --> 00:18:42,310
Mi ćemo napraviti stvari teže.

265
00:18:42,310 --> 00:18:51,210
Sada uzeti minutu ili tako da se samo napraviti ovu vrstu stvar,

266
00:18:51,210 --> 00:18:57,690
gdje unutar glavna želite stvoriti ovo drvo, i to je sve što želim učiniti.

267
00:18:57,690 --> 00:19:04,530
Pokušajte i izgraditi ovo drvo u svom glavnom funkciji.

268
00:19:42,760 --> 00:19:47,610
>> Ok. Dakle, ne morate čak ni da su izgrađene stablo, cijeli put još.

269
00:19:47,610 --> 00:19:49,840
No, svatko ima nešto što sam mogao podići

270
00:19:49,840 --> 00:20:03,130
pokazuju kako bi se moglo početi gradnju takvog stabla?

271
00:20:03,130 --> 00:20:08,080
[Studentski] Nečiji lupanje, pokušava izaći.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Svatko ugodno sa svojim stabla gradnje?

273
00:20:13,100 --> 00:20:15,520
[Studentski] Naravno. To nije učinjeno. >> To je u redu. Mi samo možemo završiti -

274
00:20:15,520 --> 00:20:26,860
oh, mogu li ga spasiti? Hura.

275
00:20:26,860 --> 00:20:32,020
Dakle, ovdje imamo - oh, ja sam malo odsječen.

276
00:20:32,020 --> 00:20:34,770
Jesam li ja zumirana u?

277
00:20:34,770 --> 00:20:37,730
Povećavanje, pomaknite se. >> Imam pitanje. >> Da?

278
00:20:37,730 --> 00:20:44,410
[Studentski] Kada definirate struct, su stvari poput inicijalizirane na ništa?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Ok. Dakle, ti bi da inicijalizirati -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Kada definirate, ili kada se proglasi struct,

281
00:20:50,450 --> 00:20:55,600
to nije inicijaliziran po defaultu, to je baš kao ako proglasi int.

282
00:20:55,600 --> 00:20:59,020
To je točno istu stvar. To je kao da svaki od njegovih pojedinačnih polja

283
00:20:59,020 --> 00:21:04,460
može imati smeća vrijednost u tome. >> I to je moguće definirati - ili proglasiti struct

284
00:21:04,460 --> 00:21:07,740
na način da se to čini ih inicijalizirati?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Da. Dakle, prečac inicijalizacije sintaksa

286
00:21:13,200 --> 00:21:18,660
će izgledati -

287
00:21:18,660 --> 00:21:22,200
Postoje dva načina možemo to učiniti. Mislim da bismo trebali prevesti ga

288
00:21:22,200 --> 00:21:25,840
kako bi bili sigurni zveka to čini.

289
00:21:25,840 --> 00:21:28,510
Redoslijed argumenata koji dolazi u struct,

290
00:21:28,510 --> 00:21:32,170
ste stavili kao bi argumenata unutar tih vitičastih zagrada.

291
00:21:32,170 --> 00:21:35,690
Dakle, ako želite da ga inicijalizirati do 9 i lijevo onda se ništavnim i pravo biti nula,

292
00:21:35,690 --> 00:21:41,570
to će biti 9, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternativa je, a urednik ne sviđa ovaj sintaksu,

294
00:21:47,890 --> 00:21:50,300
i da misli da ja želim novi blok,

295
00:21:50,300 --> 00:22:01,800
ali alternativa je nešto poput -

296
00:22:01,800 --> 00:22:04,190
ovdje, ja ću ga staviti u novi redak.

297
00:22:04,190 --> 00:22:09,140
Vi izričito ne može reći, zaboravila sam točno sintaksu.

298
00:22:09,140 --> 00:22:13,110
Tako možete i eksplicitno ih rješavati po imenu, i recimo,

299
00:22:13,110 --> 00:22:21,570
. C, ili. Vrijednost = 9,. Lijevo = NULL.

300
00:22:21,570 --> 00:22:24,540
Ja sam guessing ove potrebu da se zarezi.

301
00:22:24,540 --> 00:22:29,110
. Pravo = NULL, tako da je ovo način da se ne

302
00:22:29,110 --> 00:22:33,780
zapravo treba znati redoslijed struct,

303
00:22:33,780 --> 00:22:36,650
i kada ste čitajući ovo, to je puno precizniji

304
00:22:36,650 --> 00:22:41,920
o čemu je vrijednost je se inicijaliziraju.

305
00:22:41,920 --> 00:22:44,080
>> To se događa da se jedna od stvari koje -

306
00:22:44,080 --> 00:22:49,100
tako, za najveći dio, C + + je nadskup C.

307
00:22:49,100 --> 00:22:54,160
Možete uzeti C kod, premjestiti ga na C + +, i to bi trebalo sastaviti.

308
00:22:54,160 --> 00:22:59,570
To je jedna od stvari koje C + + ne podržavaju, tako da ljudi imaju tendenciju da ne to učiniti.

309
00:22:59,570 --> 00:23:01,850
Ja ne znam da li je to jedini razlog ljudi imaju tendenciju da ne to učiniti,

310
00:23:01,850 --> 00:23:10,540
ali slučaj gdje sam trebao koristiti ga potrebno za rad s C + + i tako nisam mogao koristiti ovu.

311
00:23:10,540 --> 00:23:14,000
Još jedan primjer nešto što ne raditi s C + + je

312
00:23:14,000 --> 00:23:16,940
kako malloc vraća void * "," tehnički,

313
00:23:16,940 --> 00:23:20,200
ali samo mogao reći char * x = malloc štogod,

314
00:23:20,200 --> 00:23:22,840
i ona će automatski biti bačeni na char *.

315
00:23:22,840 --> 00:23:25,450
To automatski baci se ne događa u C + +.

316
00:23:25,450 --> 00:23:28,150
To ne bi sastaviti, a vi bi eksplicitno treba reći

317
00:23:28,150 --> 00:23:34,510
char *, malloc, što god, da ga baci na char *.

318
00:23:34,510 --> 00:23:37,270
Ne postoje mnoge stvari koje C i C + + ne slažu o,

319
00:23:37,270 --> 00:23:40,620
ali one su dvije.

320
00:23:40,620 --> 00:23:43,120
Dakle, mi ćemo ići s tom sintaksom.

321
00:23:43,120 --> 00:23:46,150
Ali čak i ako mi ne ide s tom sintaksom,

322
00:23:46,150 --> 00:23:49,470
što je - može biti krivo s tim?

323
00:23:49,470 --> 00:23:52,170
[Studentski] Ne trebam ga dereference? >> Da.

324
00:23:52,170 --> 00:23:55,110
Sjetite se da strelica ima implicitnu dereference,

325
00:23:55,110 --> 00:23:58,230
pa kad smo tek bave struct,

326
00:23:58,230 --> 00:24:04,300
želimo koristiti. dobiti na polju unutrašnjosti struct.

327
00:24:04,300 --> 00:24:07,200
A jedini put kad smo koristiti strelicu kada želimo napraviti -

328
00:24:07,200 --> 00:24:13,450
dobro, strelica je ekvivalent -

329
00:24:13,450 --> 00:24:17,020
to je ono što bi značilo, ako sam koristiti strelicu.

330
00:24:17,020 --> 00:24:24,600
Sve strelica znači da je, dereference ovo, sad sam na struct, a ja mogu dobiti polje.

331
00:24:24,600 --> 00:24:28,040
Ili se polje izravno ili dereference i dobiti polje -

332
00:24:28,040 --> 00:24:30,380
Pretpostavljam da je ovo trebala biti vrijednost.

333
00:24:30,380 --> 00:24:33,910
No, ovdje imam posla sa samo struct, a ne pokazivač na struct,

334
00:24:33,910 --> 00:24:38,780
i tako ja ne mogu koristiti strelicu.

335
00:24:38,780 --> 00:24:47,510
No, ova vrsta stvar možemo učiniti za sve čvorove.

336
00:24:47,510 --> 00:24:55,790
Bože moj.

337
00:24:55,790 --> 00:25:09,540
Ovo je 6, 7, i 3.

338
00:25:09,540 --> 00:25:16,470
Tada možemo postaviti grane u našoj stabla, možemo imati 7 -

339
00:25:16,470 --> 00:25:21,650
možemo imati, njegova lijeva treba ukazati na tri.

340
00:25:21,650 --> 00:25:25,130
Pa kako ćemo to učiniti?

341
00:25:25,130 --> 00:25:29,320
[Studenti, nerazumljivo] >> Da. Adresu node3,

342
00:25:29,320 --> 00:25:34,170
a ako nisu imali adresu, onda to jednostavno ne bi sastaviti.

343
00:25:34,170 --> 00:25:38,190
No, sjetite se da su to upućuje na sljedeću čvorova.

344
00:25:38,190 --> 00:25:44,930
Pravo treba ukazati na devet,

345
00:25:44,930 --> 00:25:53,330
i 3 treba ukazati na pravo na šest.

346
00:25:53,330 --> 00:25:58,480
Mislim da je to sve skupa. Sve primjedbe ili pitanja?

347
00:25:58,480 --> 00:26:02,060
[Student, nerazumljivo] Korijen će biti sedam.

348
00:26:02,060 --> 00:26:08,210
Mi samo možemo reći čvor * ptr =

349
00:26:08,210 --> 00:26:14,160
ili korijena, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Za naše potrebe, mi ćemo se baviti umetkom,

351
00:26:20,730 --> 00:26:25,490
tako da ćemo želite napisati funkciju za umetanje u ovom binarnom stablu

352
00:26:25,490 --> 00:26:34,230
i umetanje neizbježno će se zvati malloc stvoriti novi čvor za ovog stabla.

353
00:26:34,230 --> 00:26:36,590
Dakle, stvari će se dobiti messy s činjenicom da su neki čvorovi

354
00:26:36,590 --> 00:26:38,590
su trenutno na stog

355
00:26:38,590 --> 00:26:43,680
i ostali čvorovi će završiti na hrpi kad smo ih umetnuti.

356
00:26:43,680 --> 00:26:47,640
To je savršeno valjana, ali jedini razlog

357
00:26:47,640 --> 00:26:49,600
mi smo u mogućnosti to učiniti na stog

358
00:26:49,600 --> 00:26:51,840
je zato što je tako neprirodan primjer da znamo

359
00:26:51,840 --> 00:26:56,360
stablo je trebao biti izgrađen kao 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Ako nismo, onda ne bi trebala malloc na prvom mjestu.

361
00:27:02,970 --> 00:27:06,160
Kao što ćemo vidjeti malo kasnije, trebali bismo se malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Upravo sada je savršeno razumna staviti na stog,

363
00:27:08,570 --> 00:27:14,750
ali ajmo to promijeniti na malloc provedbu.

364
00:27:14,750 --> 00:27:17,160
Dakle, svaki od njih sada će biti nešto poput

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

366
00:27:24,240 --> 00:27:28,040
A sad ćemo morati učiniti naš ček.

367
00:27:28,040 --> 00:27:34,010
ako (node9 == NULL) - Nisam želio da -

368
00:27:34,010 --> 00:27:40,950
povratak jednog, a onda možemo učiniti node9-> jer sada je pokazivač,

369
00:27:40,950 --> 00:27:45,300
vrijednost = 6, node9-> lijevo = NULL,

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

371
00:27:48,930 --> 00:27:51,410
a mi ćemo to morati učiniti da za svaki od tih čvorova.

372
00:27:51,410 --> 00:27:57,490
Dakle, umjesto, ajmo ga staviti unutar posebnog funkcije.

373
00:27:57,490 --> 00:28:00,620
Nazovimo to čvor * build_node,

374
00:28:00,620 --> 00:28:09,050
i to je nešto slično API pružamo za Huffman ovo kodiranje.

375
00:28:09,050 --> 00:28:12,730
Mi vam dati inicijalizatora funkcije za drvo

376
00:28:12,730 --> 00:28:20,520
i dekonstrukcionista "funkcije" Za one stabala i isti za šume.

377
00:28:20,520 --> 00:28:22,570
>> Dakle, ovdje ćemo imati inicijalizatora funkciju

378
00:28:22,570 --> 00:28:25,170
samo izgraditi čvor za nas.

379
00:28:25,170 --> 00:28:29,320
I to će izgledati prilično točno ovako.

380
00:28:29,320 --> 00:28:32,230
I čak ću biti lijeni i ne promijeniti ime varijable,

381
00:28:32,230 --> 00:28:34,380
iako node9 nema smisla više.

382
00:28:34,380 --> 00:28:38,610
Oh, pretpostavljam node9 je vrijednost ne bi trebala biti šest.

383
00:28:38,610 --> 00:28:42,800
Sada se možemo vratiti node9.

384
00:28:42,800 --> 00:28:49,550
I ovdje bi se trebali vratiti null.

385
00:28:49,550 --> 00:28:52,690
Svatko se slažu na toj graditi-čvor funkciji?

386
00:28:52,690 --> 00:28:59,780
Dakle, sada možemo samo pozvati da za izgradnju bilo čvor s određenom vrijednosti i null pokazivače.

387
00:28:59,780 --> 00:29:09,750
Sada možemo nazvati, možemo napraviti čvor * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
I nemojmo učiniti. . .

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

390
00:29:33,980 --> 00:29:39,330
A sada želimo postaviti iste upućuje,

391
00:29:39,330 --> 00:29:42,470
osim sada je sve već u smislu upućuje

392
00:29:42,470 --> 00:29:48,480
tako da više ne trebate adresu.

393
00:29:48,480 --> 00:29:56,300
Ok. Dakle, ono što je zadnja stvar koju želim učiniti?

394
00:29:56,300 --> 00:30:03,850
Tu je pogreška-provjera da ja ne radim.

395
00:30:03,850 --> 00:30:06,800
Što znači graditi čvor povratak?

396
00:30:06,800 --> 00:30:11,660
[Student, nerazumljivo] >> Da. Ako malloc nije uspio, to će se vratiti null.

397
00:30:11,660 --> 00:30:16,460
Tako ću lijeno staviti ga ovdje umjesto da radiš što je uvjet za svaki.

398
00:30:16,460 --> 00:30:22,320
Ako (node9 == NULL, ili - još jednostavnije,

399
00:30:22,320 --> 00:30:28,020
to je ekvivalent samo ako ne node9.

400
00:30:28,020 --> 00:30:38,310
Dakle, ako ne node9, ili ne node6, ili ne node3, ili ne node7, vratiti jedan.

401
00:30:38,310 --> 00:30:42,850
Možda bismo trebali ispisati malloc nije uspio, ili tako nešto.

402
00:30:42,850 --> 00:30:46,680
[Studentski] Je lažno jednaka null, kao i?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Bilo nula vrijednost je false.

404
00:30:51,290 --> 00:30:53,920
Dakle, null je nula vrijednost.

405
00:30:53,920 --> 00:30:56,780
Zero je nula vrijednost. Lažno je nula vrijednost.

406
00:30:56,780 --> 00:31:02,130
Bilo - prilično mnogo samo dva nula vrijednosti su nula i nula,

407
00:31:02,130 --> 00:31:07,900
lažno je samo mljeveno meso definira kao nula.

408
00:31:07,900 --> 00:31:13,030
To vrijedi i ako ne tvrdimo globalnu varijablu.

409
00:31:13,030 --> 00:31:17,890
Ako smo imali korijen čvor * ovdje,

410
00:31:17,890 --> 00:31:24,150
zatim - Lijepo je stvar o globalnim varijablama je da oni uvijek imaju početnu vrijednost.

411
00:31:24,150 --> 00:31:27,500
To nije točno funkcija, kako unutar ovdje,

412
00:31:27,500 --> 00:31:34,870
ako imamo, kao što je, čvor * ili čvor x.

413
00:31:34,870 --> 00:31:37,380
Mi nemamo pojma što x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
ili bismo ih mogli ispisati i oni mogli biti proizvoljna.

415
00:31:40,700 --> 00:31:44,980
To nije istina globalnih varijabli.

416
00:31:44,980 --> 00:31:47,450
Dakle, čvor korijen ili čvor x.

417
00:31:47,450 --> 00:31:53,410
Po defaultu, sve što je globalna, ako ne i eksplicitno inicijalizirana na neke vrijednosti,

418
00:31:53,410 --> 00:31:57,390
ima nultu vrijednost kao vrijednost.

419
00:31:57,390 --> 00:32:01,150
Dakle, ovdje, čvor korijen *, ne izričito inicijalizirati na ništa,

420
00:32:01,150 --> 00:32:06,350
tako da je njegova vrijednost zadana će biti nula, što je nula vrijednost upućuje.

421
00:32:06,350 --> 00:32:11,870
Zadana vrijednost x. će značiti da x.value je nula,

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

423
00:32:14,260 --> 00:32:21,070
Dakle, budući da je rekonstruirati sve poljima struct će biti nula vrijednosti.

424
00:32:21,070 --> 00:32:24,410
Mi ne trebamo koristiti da se ovdje, ipak.

425
00:32:24,410 --> 00:32:27,320
[Studentski] U tvorevina su drugačiji od ostalih varijabli, a ostale varijable

426
00:32:27,320 --> 00:32:31,400
smeće vrijednosti, to su nule?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Druge vrijednosti previše. Tako je u X, X će biti nula.

428
00:32:36,220 --> 00:32:40,070
Ako je na globalnom okviru, ona ima početnu vrijednost. >> Ok.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Ili je početna vrijednost koju je dao ga ili nula.

430
00:32:48,950 --> 00:32:53,260
Mislim da se brine o svemu tome.

431
00:32:53,260 --> 00:32:58,390
>> Ok. Dakle, sljedeći dio pitanja pita,

432
00:32:58,390 --> 00:33:01,260
"Sada želimo napisati funkciju pod nazivom sadrži

433
00:33:01,260 --> 00:33:04,930
s prototip bool sadrži int vrijednosti. "

434
00:33:04,930 --> 00:33:08,340
Nećemo učiniti bool sadrži int vrijednost.

435
00:33:08,340 --> 00:33:15,110
Naš prototip će izgledati

436
00:33:15,110 --> 00:33:22,380
bool sadrži (int vrijednost.

437
00:33:22,380 --> 00:33:24,490
I onda mi također idemo proći ga stablo

438
00:33:24,490 --> 00:33:28,870
da bi trebao biti ček vidjeti ako ima tu vrijednost.

439
00:33:28,870 --> 00:33:38,290
Dakle, čvor * stablo). Ok.

440
00:33:38,290 --> 00:33:44,440
A onda ga možemo nazvati s nešto poput,

441
00:33:44,440 --> 00:33:46,090
možda ćemo želite printf ili nešto.

442
00:33:46,090 --> 00:33:51,040
Sadrži 6, naš korijen.

443
00:33:51,040 --> 00:33:54,300
To bi trebalo vratiti jedan, ili istinske,

444
00:33:54,300 --> 00:33:59,390
a sadrži pet korijen trebao vratiti false.

445
00:33:59,390 --> 00:34:02,690
Tako se drugi provesti ovu.

446
00:34:02,690 --> 00:34:06,780
Možete to učiniti bilo iterativno ili rekurzivno.

447
00:34:06,780 --> 00:34:09,739
Lijepo je stvar o načinu smo postavili stvari je da

448
00:34:09,739 --> 00:34:12,300
ona sama posuđuje našem rekurzivni rješenje puno lakše

449
00:34:12,300 --> 00:34:14,719
od globalne varijable način učinio.

450
00:34:14,719 --> 00:34:19,750
Jer ako imamo samo sadrži int vrijednost, onda nemamo način recursing dolje subtrees.

451
00:34:19,750 --> 00:34:24,130
Mi bi imati odvojenu pomagač funkcije koje recurses dolje subtrees za nas.

452
00:34:24,130 --> 00:34:29,610
No, budući da smo promijenili da se stablo kao argument,

453
00:34:29,610 --> 00:34:32,760
kojima bi uvijek bili na prvom mjestu,

454
00:34:32,760 --> 00:34:35,710
Sada možemo recurse lakše.

455
00:34:35,710 --> 00:34:38,960
Dakle, iterativni ili rekurzivna, mi ćemo ići preko oba,

456
00:34:38,960 --> 00:34:46,139
ali vidjet ćemo da rekurzivnih završava gore bitak prilično jednostavan.

457
00:34:59,140 --> 00:35:02,480
Ok. Ima li netko nešto možemo raditi s?

458
00:35:02,480 --> 00:35:12,000
>> [Studentski] Imam rješenje iterativnog. >> Redu, iterativni.

459
00:35:12,000 --> 00:35:16,030
Ok, ovo izgleda dobro.

460
00:35:16,030 --> 00:35:18,920
Dakle, želite nas prošetati kroz nju?

461
00:35:18,920 --> 00:35:25,780
[Studentski] Naravno. Tako sam postaviti temp varijablu da biste dobili prvi čvor stabla.

462
00:35:25,780 --> 00:35:28,330
A onda sam provući kroz dok temperatura ne jednak null,

463
00:35:28,330 --> 00:35:31,700
pa dok je još na stablu, pretpostavljam.

464
00:35:31,700 --> 00:35:35,710
A ako je vrijednost jednaka vrijednosti koje temp pokazuje da,

465
00:35:35,710 --> 00:35:37,640
tada vraća tu vrijednost.

466
00:35:37,640 --> 00:35:40,210
Inače, on provjerava ako je na desnoj strani ili lijevoj strani.

467
00:35:40,210 --> 00:35:43,400
Ako ste ikada dobili situaciju u kojoj nema više stablo,

468
00:35:43,400 --> 00:35:47,330
zatim se vraća - to izlazi iz petlje i false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Ok. Tako da se čini dobro.

470
00:35:52,190 --> 00:35:58,470
Svatko ima bilo kakve komentare o svemu?

471
00:35:58,470 --> 00:36:02,400
Nemam ispravnosti komentare na sve.

472
00:36:02,400 --> 00:36:11,020
Jedna stvar koju možemo učiniti je taj tip.

473
00:36:11,020 --> 00:36:21,660
Oh, to će ići malo dužeg.

474
00:36:21,660 --> 00:36:33,460
Ja ću popraviti taj gore. Ok.

475
00:36:33,460 --> 00:36:37,150
>> Svatko treba imati na umu kako je trojni radi.

476
00:36:37,150 --> 00:36:38,610
Tu svakako su kvizove u prošlosti

477
00:36:38,610 --> 00:36:41,170
da vam dati funkciju s ternarni operatora,

478
00:36:41,170 --> 00:36:45,750
i reći, prevesti ovo, učiniti nešto da se ne koristi ternarni.

479
00:36:45,750 --> 00:36:49,140
Dakle, ovo je vrlo čest slučaj kada bih misliti da koristite ternarni,

480
00:36:49,140 --> 00:36:54,610
gdje ako neki uvjet postaviti varijablu na nešto,

481
00:36:54,610 --> 00:36:58,580
drugdje postaviti tu istu varijablu na nešto drugo.

482
00:36:58,580 --> 00:37:03,390
To je nešto što je vrlo često se može pretvoriti u takvim stvarima

483
00:37:03,390 --> 00:37:14,420
gdje postaviti tu varijablu na to - ili, dobro, je li to istina? Onda je ovo, drugi je ovo.

484
00:37:14,420 --> 00:37:18,550
[Studentski] Prvi je ako je istina, zar ne?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Aha. Način na koji sam ga uvijek pročitati je, temperatura je jednaka vrijednost veću od vrijednosti temp,

486
00:37:25,570 --> 00:37:30,680
onda je to, ostalo je ovo. To je molba pitanje.

487
00:37:30,680 --> 00:37:35,200
Je li to veća? Zatim napraviti prvu stvar. Inače to druga stvar.

488
00:37:35,200 --> 00:37:41,670
Ja gotovo uvijek - debelo crijevo, ja samo - u mojoj glavi, čitao sam kao drugi.

489
00:37:41,670 --> 00:37:47,180
>> Se bilo tko imati rekurzivni rješenje?

490
00:37:47,180 --> 00:37:49,670
Ok. Ovaj ćemo se - to je već mogao biti velik,

491
00:37:49,670 --> 00:37:53,990
ali ćemo to učiniti još boljim.

492
00:37:53,990 --> 00:37:58,720
To je ljepušan velik dio isti točan ideja.

493
00:37:58,720 --> 00:38:03,060
To je samo, dobro, ne želite da objasni?

494
00:38:03,060 --> 00:38:08,340
[Studentski] Naravno. Dakle, mi smo sigurni da stablo nije null prvi,

495
00:38:08,340 --> 00:38:13,380
jer ako je drvo null onda će to povratak false, jer nismo ga pronašli.

496
00:38:13,380 --> 00:38:19,200
I ako još uvijek postoji stablo, idemo u - prvo provjerite je li vrijednost je trenutni čvor.

497
00:38:19,200 --> 00:38:23,740
Povratak vrijedi ako je to, a ako ne možemo recurse na lijevo ili desno.

498
00:38:23,740 --> 00:38:25,970
Zvuči primjereno? >> Mm-hmm. (Ugovor)

499
00:38:25,970 --> 00:38:33,880
Dakle, primijetite da je to gotovo - strukturno vrlo sličan iterativnog rješenja.

500
00:38:33,880 --> 00:38:38,200
To je samo da umjesto recursing, imali smo while petlja.

501
00:38:38,200 --> 00:38:40,840
A osnovni slučaj ovdje, gdje stabla ne jednak null

502
00:38:40,840 --> 00:38:44,850
bio uvjet pod kojim smo izbio while petlje.

503
00:38:44,850 --> 00:38:50,200
Oni su vrlo slični. No, idemo uzeti ovaj jedan korak dalje.

504
00:38:50,200 --> 00:38:54,190
Sada, mi radimo istu stvar ovdje.

505
00:38:54,190 --> 00:38:57,680
Obavijest smo vraća istu stvar u oba ova linija,

506
00:38:57,680 --> 00:39:00,220
osim za jedan argument je drugačiji.

507
00:39:00,220 --> 00:39:07,950
Tako ćemo napraviti da u trodjelna.

508
00:39:07,950 --> 00:39:13,790
Udario sam opciju nešto, a to je simbol. Ok.

509
00:39:13,790 --> 00:39:21,720
Tako ćemo se vratiti sadrži toga.

510
00:39:21,720 --> 00:39:28,030
Ovaj je uzimajući biti više redaka, dobro, zumirani je.

511
00:39:28,030 --> 00:39:31,060
Obično, kao stilsku stvar, ne mislim da mnogo ljudi

512
00:39:31,060 --> 00:39:38,640
staviti razmak nakon strelice, ali mislim da, ako ste dosljedni, to je u redu.

513
00:39:38,640 --> 00:39:44,320
Ako je vrijednost manja od stabla vrijednosti, želimo recurse na stabla lijeve strane,

514
00:39:44,320 --> 00:39:53,890
drugo želimo recurse na stabla desno.

515
00:39:53,890 --> 00:39:58,610
Dakle, to je bio jedan korak izrade ovo izgleda manji.

516
00:39:58,610 --> 00:40:02,660
Korak dva izrade ovo izgleda manji -

517
00:40:02,660 --> 00:40:09,150
možemo odvojiti to više redaka.

518
00:40:09,150 --> 00:40:16,500
Ok. Korak dva, čineći ga izgledati manje je ovdje,

519
00:40:16,500 --> 00:40:25,860
tako da povratna vrijednost jednaka stablo vrijednost, ili sadrži bilo što.

520
00:40:25,860 --> 00:40:28,340
>> Ovo je važna stvar.

521
00:40:28,340 --> 00:40:30,860
Nisam siguran da li je on rekao da eksplicitno u razredu,

522
00:40:30,860 --> 00:40:34,740
ali to se zove kratki spoj procjena.

523
00:40:34,740 --> 00:40:41,060
Ideja je vrijednost == stablo vrijednost.

524
00:40:41,060 --> 00:40:49,960
Ako je to istina, onda je to istina, a mi želimo da 'ili' da sa što je više ovdje.

525
00:40:49,960 --> 00:40:52,520
Dakle, čak i bez razmišljanja o svemu što je ovdje,

526
00:40:52,520 --> 00:40:55,070
što je cijeli izraz će vratiti?

527
00:40:55,070 --> 00:40:59,430
[Studentski] Istina? >> Da, jer vrijedi ništa,

528
00:40:59,430 --> 00:41:04,990
or'd - ili istina or'd sa sve što je nužno istinito.

529
00:41:04,990 --> 00:41:08,150
Dakle, čim smo vidjeli povratnu vrijednost = stablo vrijednost,

530
00:41:08,150 --> 00:41:10,140
samo mi ide na povratak istina.

531
00:41:10,140 --> 00:41:15,710
Ni ide recurse dalje sadrži niz liniju.

532
00:41:15,710 --> 00:41:20,980
Možemo uzeti ovaj jedan korak dalje.

533
00:41:20,980 --> 00:41:29,490
Povratak stablo ne jednak null i sve to.

534
00:41:29,490 --> 00:41:32,650
To je to jedna linija funkcija.

535
00:41:32,650 --> 00:41:36,790
Ovo je također primjer kratkog spoja evaluacije.

536
00:41:36,790 --> 00:41:40,680
No, sada je ista ideja -

537
00:41:40,680 --> 00:41:47,320
umjesto - pa ako stablo nije jednak null - ili, dobro,

538
00:41:47,320 --> 00:41:49,580
ako stablo ne jednak null, koji je loš slučaj,

539
00:41:49,580 --> 00:41:54,790
ako stablo jednaka null, zatim prvi uvjet će biti lažni.

540
00:41:54,790 --> 00:42:00,550
Dakle, lažni anded s ničim će biti što?

541
00:42:00,550 --> 00:42:04,640
[Studentski] Netočno. >> Da. Ovo je druga polovica kratkog spoja evaluacije,

542
00:42:04,640 --> 00:42:10,710
gdje ako stablo ne jednaka null, onda mi se ne ide na čak ići -

543
00:42:10,710 --> 00:42:14,930
ili ako stablo ne jednak null, onda mi se ne ide raditi vrijednost == stablo vrijednosti.

544
00:42:14,930 --> 00:42:17,010
Mi samo ćeš odmah vratiti false.

545
00:42:17,010 --> 00:42:20,970
Koja je važno, jer ako to nije kratki spoj ocijeniti,

546
00:42:20,970 --> 00:42:25,860
onda ako stablo ne jednak null, ovaj drugi uvjet će SEG krivnjom,

547
00:42:25,860 --> 00:42:32,510
jer stablo-> vrijednost dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Dakle, to je to. Može li se to - pomak jedanput.

549
00:42:40,490 --> 00:42:44,840
To je vrlo uobičajena stvar, također, ne čineći ovu jednu liniju s tim,

550
00:42:44,840 --> 00:42:49,000
ali to je uobičajena stvar u uvjetima, možda ne baš ovdje,

551
00:42:49,000 --> 00:42:59,380
ali ako (stablo! = NULL, i drvo-> vrijednost == vrijednost), što god.

552
00:42:59,380 --> 00:43:01,560
To je vrlo česta pojava, gdje umjesto

553
00:43:01,560 --> 00:43:06,770
razbiti to u dvije oklijevanja, gdje se sviđa, je stablo null?

554
00:43:06,770 --> 00:43:11,780
Ok, to nije null, tako da sada je stablo vrijednost jednaka vrijednosti? Učinite to.

555
00:43:11,780 --> 00:43:17,300
Umjesto toga, ovaj uvjet, to se nikada neće SEG kvar

556
00:43:17,300 --> 00:43:21,220
jer će izbiti ako se to dogodi biti nula.

557
00:43:21,220 --> 00:43:24,000
Pa, mislim da ako je vaš stablo je potpuno nevažeći pokazivač, to još uvijek može SEG kvar,

558
00:43:24,000 --> 00:43:26,620
ali to se ne može pokvariti ako SEG stablo je null.

559
00:43:26,620 --> 00:43:32,900
Ako je to bila nula, to bi izbiti prije nego li ikada dereferenced pokazivač na prvom mjestu.

560
00:43:32,900 --> 00:43:35,000
[Studentski] Je li ovo zove lijeni procjena?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy procjena je zasebna stvar.

562
00:43:40,770 --> 00:43:49,880
Lazy procjena je više kao što tražiti vrijednosti,

563
00:43:49,880 --> 00:43:54,270
pitate se izračunati vrijednost, vrsta, ali ne treba odmah.

564
00:43:54,270 --> 00:43:59,040
Dakle, dok se zapravo treba, to nije ocijenjen.

565
00:43:59,040 --> 00:44:03,920
To nije točno istu stvar, ali u Huffman pset,

566
00:44:03,920 --> 00:44:06,520
on kaže da smo "lijeno" pisati.

567
00:44:06,520 --> 00:44:08,670
Razlog činimo to je zato što mi zapravo puferski WRITE -

568
00:44:08,670 --> 00:44:11,820
ne želimo pisati pojedinačne bitove na vrijeme,

569
00:44:11,820 --> 00:44:15,450
ili pojedini bajtova u isto vrijeme, mi umjesto žele dobiti komad bajtova.

570
00:44:15,450 --> 00:44:19,270
Onda kada imamo komad bajtova, onda ćemo ga napisati.

571
00:44:19,270 --> 00:44:22,640
Iako ga pitati za pisanje - i fwrite i fread učiniti istu vrstu stvari.

572
00:44:22,640 --> 00:44:26,260
Oni tampon vaš čita i piše.

573
00:44:26,260 --> 00:44:31,610
Iako ga pitati pisati odmah, vjerojatno neće.

574
00:44:31,610 --> 00:44:34,540
I ne možete biti sigurni da su stvari će biti napisano

575
00:44:34,540 --> 00:44:37,540
dok vi zovete hfclose ili što god to je,

576
00:44:37,540 --> 00:44:39,620
koji je tada, kaže, ok, ja sam zatvaranja moj dosje,

577
00:44:39,620 --> 00:44:43,450
to znači da sam bolje bih napisati sve nisam pisao još.

578
00:44:43,450 --> 00:44:45,770
To ne treba pisati sve iz

579
00:44:45,770 --> 00:44:49,010
dok se zatvara datoteku, a zatim ga treba.

580
00:44:49,010 --> 00:44:56,220
Dakle, to je upravo ono što lijeni - to čeka dok ne mora dogoditi.

581
00:44:56,220 --> 00:44:59,990
Ovo - uzeti 51, a vi ćete ići u nju u više detalja,

582
00:44:59,990 --> 00:45:05,470
jer OCaml i sve u 51, sve je rekurzije.

583
00:45:05,470 --> 00:45:08,890
Nema iterativnog rješenja, osnovi.

584
00:45:08,890 --> 00:45:11,550
Sve je rekurzije, a pasivno vrednovanje

585
00:45:11,550 --> 00:45:14,790
će biti važno za puno okolnostima

586
00:45:14,790 --> 00:45:19,920
gdje, ako nije lijeno ocijeniti, to bi značilo -

587
00:45:19,920 --> 00:45:24,760
Primjer je potoci, koji su beskrajno dugo.

588
00:45:24,760 --> 00:45:30,990
U teoriji, možete misliti prirodnih brojeva kao tok 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Dakle lijeno ocjenjivali stvari su u redu.

590
00:45:33,090 --> 00:45:37,210
Ako kažem hoću deseti broj, onda ja mogu procijeniti do desetog broja.

591
00:45:37,210 --> 00:45:40,300
Ako želim stoti broj, onda ja mogu procijeniti do stote broju.

592
00:45:40,300 --> 00:45:46,290
Bez lijen ocjenu, onda će to pokušati procijeniti sve brojeve odmah.

593
00:45:46,290 --> 00:45:50,000
Ti si ocjenu beskonačno mnogo brojeva, a to jednostavno nije moguće.

594
00:45:50,000 --> 00:45:52,080
Dakle, postoji mnogo okolnosti u kojima pasivno vrednovanje

595
00:45:52,080 --> 00:45:57,840
je samo bitno da dobivanje stvari raditi.

596
00:45:57,840 --> 00:46:05,260
>> Sada želimo pisati umetak gdje umetak će biti

597
00:46:05,260 --> 00:46:08,430
slično mijenjaju u svojoj definiciji.

598
00:46:08,430 --> 00:46:10,470
Dakle, sada je bool umetak (int vrijednost).

599
00:46:10,470 --> 00:46:23,850
Mi ćemo to promijeniti za bool umetkom (int vrijednost, čvor * stablo).

600
00:46:23,850 --> 00:46:29,120
Mi zapravo će se promijeniti da opet malo, pa ćemo vidjeti zašto.

601
00:46:29,120 --> 00:46:32,210
I krenimo build_node, samo za pakao od toga,

602
00:46:32,210 --> 00:46:36,730
iznad umetnite tako da ne moram napisati funkcije prototip.

603
00:46:36,730 --> 00:46:42,450
Koji je nagovještaja da ste idući u biti koristeći build_node u privitku.

604
00:46:42,450 --> 00:46:49,590
Ok. Uzmi trenutak za to.

605
00:46:49,590 --> 00:46:52,130
Mislim da sam spasio reviziju ako želite izvući iz toga,

606
00:46:52,130 --> 00:47:00,240
ili, barem, ja sam sada.

607
00:47:00,240 --> 00:47:04,190
Htio sam blagi pauzu za razmišljanje o logici umetkom,

608
00:47:04,190 --> 00:47:08,750
ako ne možete misliti o tome.

609
00:47:08,750 --> 00:47:12,860
Uglavnom, samo će ikada biti umetanja na lišću.

610
00:47:12,860 --> 00:47:18,640
Kao, ako sam umetnuti jedan, onda sam neizbježno ću se umetanjem 1 -

611
00:47:18,640 --> 00:47:21,820
Ja ću se promijeniti u crno - Ja ću biti umetanjem jednog ovamo.

612
00:47:21,820 --> 00:47:28,070
Ili, ako sam umetnuti 4, želim da se umetanjem 4 ovamo.

613
00:47:28,070 --> 00:47:32,180
Dakle, bez obzira na ono što radite, vi ćete biti ugurate list.

614
00:47:32,180 --> 00:47:36,130
Sve što morate učiniti je ponoviti niz drvo dok ne dođete do čvora

615
00:47:36,130 --> 00:47:40,890
koji bi trebao biti čvor roditelj, novog čvora roditelj,

616
00:47:40,890 --> 00:47:44,560
i onda promijeniti svoju lijevu ili desnu pokazivač, ovisno o tome

617
00:47:44,560 --> 00:47:47,060
to je veći ili manji od trenutnog čvora.

618
00:47:47,060 --> 00:47:51,180
Promjena taj pokazivač ukazati na novi čvor.

619
00:47:51,180 --> 00:48:05,490
Tako ponoviti niz drvo, napraviti list točku na novi čvor.

620
00:48:05,490 --> 00:48:09,810
Također razmišljati o tome zašto da zabranjuje vrstu situacije prije,

621
00:48:09,810 --> 00:48:17,990
gdje sam konstruirao binarnog stabla gdje je bio ispravan

622
00:48:17,990 --> 00:48:19,920
ako je samo gledao u jednom čvoru,

623
00:48:19,920 --> 00:48:24,830
ali 9 je bio na lijevoj 7 ako ponovljena dolje skroz.

624
00:48:24,830 --> 00:48:29,770
Tako da je nemoguće u ovom scenariju, jer -

625
00:48:29,770 --> 00:48:32,530
razmišljam o umetanju 9 ili tako nešto, na prvi čvor,

626
00:48:32,530 --> 00:48:35,350
Idem vidjeti 7, a ja samo idem na desno.

627
00:48:35,350 --> 00:48:38,490
Dakle, bez obzira što mi je činiti, ako sam umetanjem odlaskom na list,

628
00:48:38,490 --> 00:48:40,790
i na list pomoću odgovarajućeg algoritma,

629
00:48:40,790 --> 00:48:43,130
to će biti nemoguće za mene za umetanje 9 na lijevoj 7

630
00:48:43,130 --> 00:48:48,250
jer čim sam pogodio sedam ću ići na pravo.

631
00:48:59,740 --> 00:49:02,070
Ima li netko nešto za početak s?

632
00:49:02,070 --> 00:49:05,480
[Studentski] ja. >> Naravno.

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

634
00:49:09,200 --> 00:49:14,390
[Ostalo učenik, nerazumljivo]

635
00:49:14,390 --> 00:49:18,330
[Bowden] To je poštovati. Ok. Želite li objasniti?

636
00:49:18,330 --> 00:49:20,690
>> [Studentski] Budući da znamo da su umetanja

637
00:49:20,690 --> 00:49:24,060
novi čvorovi na kraju stabla,

638
00:49:24,060 --> 00:49:28,070
Ja provući kroz stabla iterativno

639
00:49:28,070 --> 00:49:31,360
dok sam na čvoru koji je naglasio na nulu.

640
00:49:31,360 --> 00:49:34,220
I onda sam odlučio staviti ga bilo na desnoj strani ili lijevoj strani

641
00:49:34,220 --> 00:49:37,420
Korištenjem ove pravu varijablu, ona mi je rekla gdje da ga stavi.

642
00:49:37,420 --> 00:49:41,850
A onda, u suštini, samo sam napravio da je zadnji -

643
00:49:41,850 --> 00:49:47,520
da točka temperatura čvor za novi čvor koji je stvara,

644
00:49:47,520 --> 00:49:50,770
ili na lijevoj strani ili na desnoj strani, ovisno o tome što je vrijednost upravo bio.

645
00:49:50,770 --> 00:49:56,530
Konačno, sam postaviti novi čvor vrijednost na vrijednost njegovog ispitivanja.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Ok, tako da vidim jedan problem ovdje.

647
00:49:59,550 --> 00:50:02,050
To je kao 95% na putu tamo.

648
00:50:02,050 --> 00:50:07,550
Onaj problem koji ja vidim, dobro, ne bilo tko drugi vidi problem?

649
00:50:07,550 --> 00:50:18,400
Što je okolnost pod kojima su break izvan petlje?

650
00:50:18,400 --> 00:50:22,100
[Studentski] Ako temperatura je nula? >> Da. Pa kako se probiti izvan petlje je ako temperatura je nula.

651
00:50:22,100 --> 00:50:30,220
Ali, što da radim ovdje?

652
00:50:30,220 --> 00:50:35,410
Ja dereference temp, što je neizbježno null.

653
00:50:35,410 --> 00:50:39,840
Dakle, druga stvar koju trebate učiniti je ne samo pratiti dok temperatura je nula,

654
00:50:39,840 --> 00:50:45,590
Želite li pratiti od roditelja u svim vremenima.

655
00:50:45,590 --> 00:50:52,190
Također želimo roditelj čvor *, mislim da možemo zadržati na null na prvom mjestu.

656
00:50:52,190 --> 00:50:55,480
To će imati čudan ponašanje za korijen stabla,

657
00:50:55,480 --> 00:50:59,210
ali mi ćemo doći do toga.

658
00:50:59,210 --> 00:51:03,950
Ako je vrijednost veća od god, onda temp = temperatura u pravu.

659
00:51:03,950 --> 00:51:07,910
No, prije nego što smo to učiniti, roditelj = temp.

660
00:51:07,910 --> 00:51:14,500
Ili su roditelji uvijek ide na jednakoj temp? Je li to tako?

661
00:51:14,500 --> 00:51:19,560
Ako temperatura nije null, onda ću za kretanje prema dolje, bez obzira na sve,

662
00:51:19,560 --> 00:51:24,030
na čvoru za koje temp je roditelj.

663
00:51:24,030 --> 00:51:27,500
Dakle, roditelj će biti temp, a onda sam se presele temp dolje.

664
00:51:27,500 --> 00:51:32,410
Sada temperatura je nula, ali roditelj ukazuje na roditelju stvar koja je nula.

665
00:51:32,410 --> 00:51:39,110
Dakle, ovdje dolje, ne želim postaviti pravo jednak jedan.

666
00:51:39,110 --> 00:51:41,300
Tako sam se preselio u pravu, pa ako desno = 1,

667
00:51:41,300 --> 00:51:45,130
i mislim da i vi želite učiniti -

668
00:51:45,130 --> 00:51:48,530
ako premjestiti na lijevoj strani, želite postaviti pravo jednaka 0.

669
00:51:48,530 --> 00:51:55,950
Inače, ako ste ikada premjestiti na desno.

670
00:51:55,950 --> 00:51:58,590
Dakle, pravo = 0. Ako desnoj = 1,

671
00:51:58,590 --> 00:52:04,260
Sada želimo napraviti roditelj pravo pokazivač newnode,

672
00:52:04,260 --> 00:52:08,520
drugo želimo napraviti roditelj lijevu pokazivača newnode.

673
00:52:08,520 --> 00:52:16,850
Pitanja o tome?

674
00:52:16,850 --> 00:52:24,880
Ok. Dakle, ovo je način na koji smo - Pa, zapravo, umjesto za to,

675
00:52:24,880 --> 00:52:29,630
mi polovina očekuje da koristite build_node.

676
00:52:29,630 --> 00:52:40,450
A onda, ako newnode jednaka null, povratak false.

677
00:52:40,450 --> 00:52:44,170
To je to. Sada, to je ono što smo i očekivali da to učinite.

678
00:52:44,170 --> 00:52:47,690
>> To je ono što djelatnici rješenja učiniti.

679
00:52:47,690 --> 00:52:52,360
Ne slažem se s tim što je "pravo" način će o tome

680
00:52:52,360 --> 00:52:57,820
ali to je savršeno u redu i da će raditi.

681
00:52:57,820 --> 00:53:02,840
Jedna stvar koja je malo čudno sada je pravo

682
00:53:02,840 --> 00:53:08,310
ako stablo započinje kao null, prolazimo u null stabla.

683
00:53:08,310 --> 00:53:12,650
Pretpostavljam da to ovisi o tome kako definirati ponašanje prolazi u null stabla.

684
00:53:12,650 --> 00:53:15,490
Ja mislim da bi, ako prođe u null stabla,

685
00:53:15,490 --> 00:53:17,520
zatim umetanje vrijednost u null stablo

686
00:53:17,520 --> 00:53:23,030
treba samo vratiti na stablo, gdje je jedina vrijednost je da jedan čvor.

687
00:53:23,030 --> 00:53:25,830
Nemojte ljudi se slažu s tim? Vi bi mogli, ako ste htjeli,

688
00:53:25,830 --> 00:53:28,050
ako prođe u null stablo

689
00:53:28,050 --> 00:53:31,320
i želite umetnuti vrijednost u tome, povratak false.

690
00:53:31,320 --> 00:53:33,830
To je do vas da definiraju da.

691
00:53:33,830 --> 00:53:38,320
Da biste to je prva stvar koju sam rekao i onda -

692
00:53:38,320 --> 00:53:40,720
dobro, ti si idući u imati problema radi toga, jer

693
00:53:40,720 --> 00:53:44,090
to će biti lakše ako smo imali globalni pokazivač na stvar,

694
00:53:44,090 --> 00:53:48,570
ali mi ne, pa ako je stablo null, ne postoji ništa što možemo učiniti o tome.

695
00:53:48,570 --> 00:53:50,960
Mi samo možemo vratiti false.

696
00:53:50,960 --> 00:53:52,840
Dakle, ja ću promijeniti umetak.

697
00:53:52,840 --> 00:53:56,540
Mi samo tehnički moglo promijeniti to pravo ovdje,

698
00:53:56,540 --> 00:53:58,400
kako se to Ponavljanje više stvari,

699
00:53:58,400 --> 00:54:04,530
ali ja ću promijeniti umetak da se čvor ** stablo.

700
00:54:04,530 --> 00:54:07,510
Dupli pokazivače.

701
00:54:07,510 --> 00:54:09,710
Što to znači?

702
00:54:09,710 --> 00:54:12,330
Umjesto da se bave pokazivače na čvorove,

703
00:54:12,330 --> 00:54:16,690
stvar ću se manipulira ovaj pokazivač.

704
00:54:16,690 --> 00:54:18,790
Ja ću se manipulira ovaj pokazivač.

705
00:54:18,790 --> 00:54:21,770
Ja ću se manipulira upućuje izravno.

706
00:54:21,770 --> 00:54:25,760
To ima smisla, jer, razmišljam o dolje -

707
00:54:25,760 --> 00:54:33,340
dobro, sad to ukazuje na nulu.

708
00:54:33,340 --> 00:54:38,130
Ono što želim učiniti je manipulirati ovaj pokazivač do točke da ne null.

709
00:54:38,130 --> 00:54:40,970
Želim ukazati na moj novi čvor.

710
00:54:40,970 --> 00:54:44,870
Ako sam samo pratiti naputke moje naputke,

711
00:54:44,870 --> 00:54:47,840
onda ja ne trebate pratiti roditelja pokazivača.

712
00:54:47,840 --> 00:54:52,640
Ja samo mogu pratiti da vidi je li pokazivač pokazuje na nulu,

713
00:54:52,640 --> 00:54:54,580
a ako pokazivač pokazuje na nulu,

714
00:54:54,580 --> 00:54:57,370
ga promijeniti ukazati na čvoru želim.

715
00:54:57,370 --> 00:55:00,070
I ja to mogu promijeniti jer imam pokazivač na pokazivač.

716
00:55:00,070 --> 00:55:02,040
Hajdemo vidjeti ovo pravo sada.

717
00:55:02,040 --> 00:55:05,470
Vi zapravo možete to učiniti rekurzivno prilično lako.

718
00:55:05,470 --> 00:55:08,080
Ne želimo to učiniti?

719
00:55:08,080 --> 00:55:10,980
Da, mi radimo.

720
00:55:10,980 --> 00:55:16,790
>> Idemo ga vidjeti rekurzivno.

721
00:55:16,790 --> 00:55:24,070
Prvo, što je naša baza slučaj će biti?

722
00:55:24,070 --> 00:55:29,140
Gotovo uvijek naša baza slučaj, ali zapravo, to je vrsta lukav.

723
00:55:29,140 --> 00:55:34,370
Prvo stvari prvi, ako (drvo == NULL)

724
00:55:34,370 --> 00:55:37,550
Pretpostavljam da smo tek će se vratiti false.

725
00:55:37,550 --> 00:55:40,460
To je različito od vašeg stabla bića null.

726
00:55:40,460 --> 00:55:44,510
Ovo je pokazivač na pokazivač korijena bića null

727
00:55:44,510 --> 00:55:48,360
što znači da je vaš korijen pokazivač ne postoji.

728
00:55:48,360 --> 00:55:52,390
Dakle, ovdje dolje, ako mi je činiti

729
00:55:52,390 --> 00:55:55,760
čvor * - neka je samo ponovno ovu.

730
00:55:55,760 --> 00:55:58,960
Čvor * korijen = NULL,

731
00:55:58,960 --> 00:56:00,730
i onda ću pozvati umetak radeći nešto slično,

732
00:56:00,730 --> 00:56:04,540
umetnite 4 u & korijena.

733
00:56:04,540 --> 00:56:06,560
Tako i korijen, ako je korijen čvor *

734
00:56:06,560 --> 00:56:11,170
onda i korijen će biti čvor **.

735
00:56:11,170 --> 00:56:15,120
Ovo vrijedi. U ovom slučaju, stablo, ovdje,

736
00:56:15,120 --> 00:56:20,120
stablo nije null - ili umetak.

737
00:56:20,120 --> 00:56:24,630
Ovdje. Stablo nije null; * stablo null, što je u redu

738
00:56:24,630 --> 00:56:26,680
jer ako * stablo null, onda ja to mogu manipulirati

739
00:56:26,680 --> 00:56:29,210
do sada ukazati na ono što sam htjela ukazati na.

740
00:56:29,210 --> 00:56:34,750
Ali, ako je stablo null, to znači da sam došao ovamo i rekao null.

741
00:56:34,750 --> 00:56:42,710
To nema smisla. Ja ne mogu ništa učiniti s tim.

742
00:56:42,710 --> 00:56:45,540
Ako stablo null, povratak false.

743
00:56:45,540 --> 00:56:48,220
Tako sam zapravo već rekao što je naš pravi baza slučaj.

744
00:56:48,220 --> 00:56:50,580
A što se da će to biti?

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

746
00:56:55,030 --> 00:57:00,000
[Bowden] Da. Dakle, ako (* stablo == NULL).

747
00:57:00,000 --> 00:57:04,520
Ovo se odnosi na slučaj ovamo

748
00:57:04,520 --> 00:57:09,640
gdje ako moja crvena kazaljka je Pokazivač sam usredotočen na,

749
00:57:09,640 --> 00:57:12,960
pa kao što sam usredotočen na ovom pokazivač, sada sam fokusiran na ovaj pokazivač.

750
00:57:12,960 --> 00:57:15,150
Sada sam fokusiran na ovaj pokazivač.

751
00:57:15,150 --> 00:57:18,160
Dakle, ako moja crvena kazaljka, koja je moja čvor **,

752
00:57:18,160 --> 00:57:22,880
je ikada - ako *, moj crveni pokazivač je uvijek nula,

753
00:57:22,880 --> 00:57:28,470
to znači da sam u slučaju kada sam s naglaskom na pokazivač koji pokazuje -

754
00:57:28,470 --> 00:57:32,530
ovo je pokazivač koji pripada list.

755
00:57:32,530 --> 00:57:41,090
Želim promijeniti ovaj pokazivač ukazati na mom novom čvoru.

756
00:57:41,090 --> 00:57:45,230
Vrati se ovamo.

757
00:57:45,230 --> 00:57:56,490
Moj newnode će biti samo čvor * n = build_node (vrijednost)

758
00:57:56,490 --> 00:58:07,300
zatim n, ako n = null, povratak false.

759
00:58:07,300 --> 00:58:12,600
Inače želimo promijeniti ono što pokazivač trenutno ukazuje na

760
00:58:12,600 --> 00:58:17,830
do sada ukazuju na našem novoizgrađenom čvoru.

761
00:58:17,830 --> 00:58:20,280
Mi zapravo može učiniti da je ovdje.

762
00:58:20,280 --> 00:58:30,660
Umjesto da se kaže n, možemo reći * stablo = ako * stabla.

763
00:58:30,660 --> 00:58:35,450
Svatko razumije da? To što se bave pokazivače na pokazivače,

764
00:58:35,450 --> 00:58:40,750
možemo promijeniti null upućuje da ukažu na stvari koje žele im ukazati na.

765
00:58:40,750 --> 00:58:42,820
To je naša baza slučaj.

766
00:58:42,820 --> 00:58:45,740
>> Sada naša ponavljanja, ili naš rekurzije,

767
00:58:45,740 --> 00:58:51,430
će biti vrlo sličan svim ostalim recursions smo radili.

768
00:58:51,430 --> 00:58:55,830
Mi ćemo želite umetnuti vrijednost,

769
00:58:55,830 --> 00:58:59,040
a sada ću koristiti ternarni opet, ali ono što je naše stanje će biti?

770
00:58:59,040 --> 00:59:05,180
Što je to što tražimo da odluči da li želimo ići lijevo ili desno?

771
00:59:05,180 --> 00:59:07,760
Ajmo to učiniti u odvojenim koracima.

772
00:59:07,760 --> 00:59:18,850
Ako (vrijednost <) što?

773
00:59:18,850 --> 00:59:23,200
[Studentski] stablu je vrijednost?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Pa sjetite se da sam trenutno -

775
00:59:27,490 --> 00:59:31,260
[Studenti, nerazumljivih]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Da, tako ovdje, recimo da je ovo zelena strelica

777
00:59:34,140 --> 00:59:39,050
je primjer onoga što stablo trenutno je, je pointer na ovaj pokazivač.

778
00:59:39,050 --> 00:59:46,610
Dakle, to znači da sam pokazivač na pokazivač na tri.

779
00:59:46,610 --> 00:59:48,800
The dereference dvaput dobro zvuči.

780
00:59:48,800 --> 00:59:51,010
Što ja - kako ću to učiniti?

781
00:59:51,010 --> 00:59:53,210
[Studentski] Dereference jednom, a zatim učinite strelica na taj način?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Pa (* stablo) je dereference jednom -> vrijednost

783
00:59:58,420 --> 01:00:05,960
će mi dati vrijednost čvora da sam neizravno sam pokazuje na.

784
01:00:05,960 --> 01:00:11,980
Dakle, ja mogu napisati ** tree.value ako vam je draže da.

785
01:00:11,980 --> 01:00:18,490
Ili radi.

786
01:00:18,490 --> 01:00:26,190
Ako je to slučaj, onda želim pozvati umetnuti s vrijednosti.

787
01:00:26,190 --> 01:00:32,590
I ono što je moj ažurirani čvor ** će biti?

788
01:00:32,590 --> 01:00:39,440
Želim ići na lijevo, tako ** tree.left će biti moj lijevo.

789
01:00:39,440 --> 01:00:41,900
I želim pokazivač na tu stvar

790
01:00:41,900 --> 01:00:44,930
tako da, ako je lijeva završi null pokazivač,

791
01:00:44,930 --> 01:00:48,360
Ja mogu mijenjati ukazati na moj novi čvor.

792
01:00:48,360 --> 01:00:51,460
>> I drugi slučaj može biti vrlo slična.

793
01:00:51,460 --> 01:00:55,600
Ajmo zapravo čine da je moj ternarni upravo sada.

794
01:00:55,600 --> 01:01:04,480
Umetni vrijednost ako vrijednost <(** stablo). Vrijednost.

795
01:01:04,480 --> 01:01:11,040
Tada želimo ažurirati naše ** s lijeve strane,

796
01:01:11,040 --> 01:01:17,030
drugo želimo ažurirati naše ** desno.

797
01:01:17,030 --> 01:01:22,540
[Studentski] da li se pokazivač na pokazivač?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Zapamtite da - ** tree.right je čvor zvijezda.

799
01:01:30,940 --> 01:01:35,040
[Student, nerazumljivo] >> Da.

800
01:01:35,040 --> 01:01:41,140
** Tree.right je kao što je ovaj pokazivač ili nešto.

801
01:01:41,140 --> 01:01:45,140
Dakle, uzimajući pokazivač da, da mi daje ono što želim

802
01:01:45,140 --> 01:01:50,090
od pokazivača do tog momka.

803
01:01:50,090 --> 01:01:54,260
[Studentski] Može li mi ići opet zašto smo koristeći dvije pokazivače?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Aha. Dakle - ne, možete, a da rješenje prije

805
01:01:58,220 --> 01:02:04,540
je način to radiš radi bez dva pokazivača.

806
01:02:04,540 --> 01:02:08,740
Morate biti u stanju razumjeti pomoću dva pokazivača,

807
01:02:08,740 --> 01:02:11,660
i to je čišći rješenje.

808
01:02:11,660 --> 01:02:16,090
Također, primijetite da je, što se događa ako je moj stablo -

809
01:02:16,090 --> 01:02:24,480
što se događa ako je moj korijen je bio nula? Što će se dogoditi ako ja napraviti ovaj slučaj ovdje?

810
01:02:24,480 --> 01:02:30,540
Dakle, čvor * korijen = NULL, umetnite 4 u & korijena.

811
01:02:30,540 --> 01:02:35,110
Što je korijen će biti nakon toga?

812
01:02:35,110 --> 01:02:37,470
[Student, nerazumljivo] >> Da.

813
01:02:37,470 --> 01:02:41,710
Korijen vrijednost će biti četiri.

814
01:02:41,710 --> 01:02:45,510
Korijen lijevo će biti nula, korijen pravo će biti nula.

815
01:02:45,510 --> 01:02:49,490
U slučaju da nismo proći korijen po adresi,

816
01:02:49,490 --> 01:02:52,490
nismo mogli mijenjati korijen.

817
01:02:52,490 --> 01:02:56,020
U slučaju stablo - gdje korijen je bio nula,

818
01:02:56,020 --> 01:02:58,410
samo smo morali vratiti false. Nema ništa što bi mogao učiniti.

819
01:02:58,410 --> 01:03:01,520
Mi ne možemo umetnuti čvor u praznu stabla.

820
01:03:01,520 --> 01:03:06,810
No, sada možemo, mi jednostavno napraviti prazno stablo u jedan čvor stabla.

821
01:03:06,810 --> 01:03:13,400
Koja je obično očekivani način na koji bi to trebalo raditi.

822
01:03:13,400 --> 01:03:21,610
>> Nadalje, to je znatno kraći od

823
01:03:21,610 --> 01:03:26,240
Također praćenje roditelja, i tako ćete ponoviti dolje skroz.

824
01:03:26,240 --> 01:03:30,140
Sada imam roditelja, a ja samo imam pokazivač roditelj pravo na bilo što.

825
01:03:30,140 --> 01:03:35,640
Umjesto toga, ako je to učinio iterativno, to bi se ista ideja s while petlje.

826
01:03:35,640 --> 01:03:38,100
No, umjesto da se bave mojim roditelja pokazivač,

827
01:03:38,100 --> 01:03:40,600
umjesto moj trenutni pokazivač bi biti stvar

828
01:03:40,600 --> 01:03:43,790
da sam izravno sam modificiranje ukazati na moj novi čvor.

829
01:03:43,790 --> 01:03:46,090
Ja ne moram nositi s bilo to ukazuje na lijevoj strani.

830
01:03:46,090 --> 01:03:48,810
Ja ne moram nositi s bilo to pokazuje na desno.

831
01:03:48,810 --> 01:04:00,860
To je samo ono što ovaj pokazivač, ja ću ga postaviti ukazati na moj novi čvor.

832
01:04:00,860 --> 01:04:05,740
Svatko shvatiti kako se to radi?

833
01:04:05,740 --> 01:04:09,460
Ako ne, zašto ne želimo to učiniti na ovaj način,

834
01:04:09,460 --> 01:04:14,920
ali barem da to funkcionira kao rješenje?

835
01:04:14,920 --> 01:04:17,110
[Studentski] Kamo ćemo povratak istina?

836
01:04:17,110 --> 01:04:21,550
[Bowden] To je vjerojatno upravo ovdje.

837
01:04:21,550 --> 01:04:26,690
Ako smo ispravno ga uložite, povratak istina.

838
01:04:26,690 --> 01:04:32,010
Inače, ovdje ćemo se žele vratiti što god umetanje vraća.

839
01:04:32,010 --> 01:04:35,950
>> I ono što je posebno o ovom rekurzivne funkcije?

840
01:04:35,950 --> 01:04:43,010
To je rep rekurzivna, tako dugo dok smo sastaviti s nekim optimizacije,

841
01:04:43,010 --> 01:04:48,060
da će priznati da je i nikada nećete dobiti stack overflow od toga,

842
01:04:48,060 --> 01:04:53,230
čak i ako naša stablo ima visinu od 10.000 ili 10 milijuna.

843
01:04:53,230 --> 01:04:55,630
[Student, nerazumljivo]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Mislim da to čini na Dash - ili ono što optimizacija razina

845
01:05:00,310 --> 01:05:03,820
je potrebno za rep rekurzije biti priznat.

846
01:05:03,820 --> 01:05:09,350
Mislim da je to prepoznaje - GCC i zveka

847
01:05:09,350 --> 01:05:12,610
Također imaju različita značenja za njihove optimizacije razinama.

848
01:05:12,610 --> 01:05:17,870
Želim reći da je DashO 2, sigurno da će prepoznati rep rekurzija.

849
01:05:17,870 --> 01:05:27,880
Ali mi - mogli graditi kao Fibonocci primjer ili nešto.

850
01:05:27,880 --> 01:05:30,030
To nije lako za testiranje s tim, jer je teško izgraditi

851
01:05:30,030 --> 01:05:32,600
binarno stablo koje je toliko velika.

852
01:05:32,600 --> 01:05:37,140
Ali da, mislim da je DashO 2, koji

853
01:05:37,140 --> 01:05:40,580
ako kompajlirati sa DashO dvije, to će izgledati za rep rekurzije

854
01:05:40,580 --> 01:05:54,030
i optimizirati da van.

855
01:05:54,030 --> 01:05:58,190
Vratimo se - umetnite je doslovno zadnja stvar treba.

856
01:05:58,190 --> 01:06:04,900
Vratimo se na umetka ovamo

857
01:06:04,900 --> 01:06:07,840
gdje idemo napraviti istu ideju.

858
01:06:07,840 --> 01:06:14,340
Još uvijek ćete imati nedostatak ne bude u mogućnosti da u potpunosti obrađuju

859
01:06:14,340 --> 01:06:17,940
kada je korijen sama je nula, ili prošlosti ulaz null,

860
01:06:17,940 --> 01:06:20,060
ali umjesto da se bave s roditeljem pokazivač,

861
01:06:20,060 --> 01:06:27,430
ajmo primijeniti istu logiku vođenja upućuje na pokazivače.

862
01:06:27,430 --> 01:06:35,580
Ako ovdje ćemo zadržati naš čvor ** sad,

863
01:06:35,580 --> 01:06:37,860
i ne trebamo pratiti desno više,

864
01:06:37,860 --> 01:06:47,190
ali čvor ** sad = & stablo.

865
01:06:47,190 --> 01:06:54,800
I sada naš while petlja će biti dok * sad ne jednak null.

866
01:06:54,800 --> 01:07:00,270
Ne trebate pratiti roditelja više.

867
01:07:00,270 --> 01:07:04,180
Ne trebate pratiti lijevo i desno.

868
01:07:04,180 --> 01:07:10,190
I ja ću ga nazvati temp, jer smo već koristite temp.

869
01:07:10,190 --> 01:07:17,200
Ok. Dakle, ako (vrijednost> * temperatura),

870
01:07:17,200 --> 01:07:24,010
tada & (* temp) -> desni

871
01:07:24,010 --> 01:07:29,250
drugi temp = & (* temp) -> lijevo.

872
01:07:29,250 --> 01:07:32,730
I sada, u ovom trenutku, nakon ovog while petlje,

873
01:07:32,730 --> 01:07:36,380
Samo sam to učiniti jer možda je lakše razmišljati o iterativno nego rekurzivno,

874
01:07:36,380 --> 01:07:39,010
ali nakon ovog while petlje,

875
01:07:39,010 --> 01:07:43,820
* Temp je pokazivač želimo promijeniti.

876
01:07:43,820 --> 01:07:48,960
>> Prije smo imali roditelja, i htjeli smo promijeniti bilo koji roditelj lijevo ili desno roditelja,

877
01:07:48,960 --> 01:07:51,310
ali ako želimo promijeniti roditelj pravo,

878
01:07:51,310 --> 01:07:54,550
onda * temp je roditelj u pravu, a možemo ga promijeniti izravno.

879
01:07:54,550 --> 01:08:05,860
Dakle, ovdje dolje, možemo učiniti * temp = newnode, i to je to.

880
01:08:05,860 --> 01:08:09,540
Dakle, obavijesti, sve što smo učinili u to uzmu linija koda.

881
01:08:09,540 --> 01:08:14,770
Kako bi se pratiti od roditelja u svemu što je dodatni napor.

882
01:08:14,770 --> 01:08:18,689
Evo, ako mi samo pratiti pokazivača na pokazivač,

883
01:08:18,689 --> 01:08:22,990
pa čak i ako smo htjeli da biste dobili osloboditi od svih tih vitičastih zagrada sada,

884
01:08:22,990 --> 01:08:27,170
čine ga gledati kraći.

885
01:08:27,170 --> 01:08:32,529
Ovo sada je isti rješenje,

886
01:08:32,529 --> 01:08:38,210
ali manje linija koda.

887
01:08:38,210 --> 01:08:41,229
Jednom kada počnete prepoznajući to kao valjani rješenje,

888
01:08:41,229 --> 01:08:43,529
to je također lakše razloga o nego kao, ok,

889
01:08:43,529 --> 01:08:45,779
zašto imam ovu zastavu na int desno?

890
01:08:45,779 --> 01:08:49,290
Što to znači? Oh, to je znači da

891
01:08:49,290 --> 01:08:51,370
svaki put sam ići desno, moram ga postaviti,

892
01:08:51,370 --> 01:08:53,819
drugo, ako sam ići lijevo moram ga postaviti na nulu.

893
01:08:53,819 --> 01:09:04,060
Evo, ja ne moram razlog za to, to je samo lakše razmišljati o tome.

894
01:09:04,060 --> 01:09:06,710
Pitanja?

895
01:09:06,710 --> 01:09:16,290
[Student, nerazumljivo] >> Da.

896
01:09:16,290 --> 01:09:23,359
Ok, tako da je u posljednjem malo -

897
01:09:23,359 --> 01:09:28,080
Valjda jedan brz i jednostavan funkcija možemo učiniti je,

898
01:09:28,080 --> 01:09:34,910
let's - zajedno, pretpostavljam, probati i napisati sadrži funkciju

899
01:09:34,910 --> 01:09:38,899
koji ne mari da li je binarno stablo pretraživanja.

900
01:09:38,899 --> 01:09:43,770
Sadrži funkcija treba vratiti istinito

901
01:09:43,770 --> 01:09:58,330
ako nigdje u toj općoj binarno stablo je vrijednost tražimo.

902
01:09:58,330 --> 01:10:02,520
Dakle, neka prvi to učiniti rekurzivno i onda ćemo to učiniti iterativno.

903
01:10:02,520 --> 01:10:07,300
Mi zapravo može samo to učiniti zajedno, jer će to biti jako kratko.

904
01:10:07,300 --> 01:10:11,510
>> Što je moja baza slučaj će biti?

905
01:10:11,510 --> 01:10:13,890
[Student, nerazumljivo]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Dakle, ako (drvo == NULL), što onda?

907
01:10:18,230 --> 01:10:22,740
[Studentski] Povratak lažna.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Inače, dobro, ja ne treba drugo.

909
01:10:26,160 --> 01:10:30,250
Ako je moja druga baza slučaj.

910
01:10:30,250 --> 01:10:32,450
[Student] stablo je vrijednost? >> Da.

911
01:10:32,450 --> 01:10:36,430
Dakle, ako (drvo-> vrijednost == vrijednost.

912
01:10:36,430 --> 01:10:39,920
Obavijest smo natrag do čvora *, a ne čvor ** e?

913
01:10:39,920 --> 01:10:42,990
Sadrži nikada nećete morati koristiti čvor **,

914
01:10:42,990 --> 01:10:45,480
jer mi se ne mijenja naputke.

915
01:10:45,480 --> 01:10:50,540
Samo smo ih poprijeko.

916
01:10:50,540 --> 01:10:53,830
Ako se to dogodi, onda želimo da se vrate istina.

917
01:10:53,830 --> 01:10:58,270
Inače želimo proći djecu.

918
01:10:58,270 --> 01:11:02,620
Dakle, ne možemo zaključivati ​​o tome da li je sve na lijevoj strani je manje

919
01:11:02,620 --> 01:11:05,390
i sve na desnoj strani je veći.

920
01:11:05,390 --> 01:11:09,590
Dakle, ono što je naše stanje će biti ovdje - ili, što ćemo učiniti?

921
01:11:09,590 --> 01:11:11,840
[Student, nerazumljivo] >> Da.

922
01:11:11,840 --> 01:11:17,400
Povratak sadrži (vrijednost, drvo-> lijevo)

923
01:11:17,400 --> 01:11:26,860
ili sadrži (vrijednost, stablo-> desni). I to je to.

924
01:11:26,860 --> 01:11:29,080
I primijetiti da je neki kratki spoj procjena,

925
01:11:29,080 --> 01:11:32,520
gdje ako mi se dogoditi da naći vrijednost u lijevom stablu,

926
01:11:32,520 --> 01:11:36,820
mi nikada ne treba gledati na desnoj stabla.

927
01:11:36,820 --> 01:11:40,430
To je cijela funkcija.

928
01:11:40,430 --> 01:11:43,690
Sada ćemo to učiniti iterativno,

929
01:11:43,690 --> 01:11:48,060
koja će biti manje lijepo.

930
01:11:48,060 --> 01:11:54,750
Mi ćemo poduzeti uobičajene početak čvor * valutama = stabla.

931
01:11:54,750 --> 01:12:03,250
Dok (sad! = NULL).

932
01:12:03,250 --> 01:12:08,600
Brzo će se vidjeti problem.

933
01:12:08,600 --> 01:12:12,250
Ako sad - ovdje, ako mi ikada break out to,

934
01:12:12,250 --> 01:12:16,020
onda smo ponestane stvari za pogledati, pa povratak false.

935
01:12:16,020 --> 01:12:24,810
Ako (sad-> vrijednost == vrijednost), povratak istina.

936
01:12:24,810 --> 01:12:32,910
Dakle, sada smo na jednom mjestu -

937
01:12:32,910 --> 01:12:36,250
Ne znamo da li želimo ići lijevo ili desno.

938
01:12:36,250 --> 01:12:44,590
Dakle, samovoljno, neka je samo ići lijevo.

939
01:12:44,590 --> 01:12:47,910
Ja očito nisam izvoditi u pitanju, gdje sam potpuno sam napustio sve -

940
01:12:47,910 --> 01:12:50,760
Ja samo da će ikada provjeriti lijevu stranu stabla.

941
01:12:50,760 --> 01:12:56,050
Ja nikada ne će provjeriti sve što je pravo dijete ništa.

942
01:12:56,050 --> 01:13:00,910
Kako mogu popraviti ovo?

943
01:13:00,910 --> 01:13:05,260
[Studentski] Morate pratiti lijevo i desno u stog.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Aha. Dakle, neka je to učiniti

945
01:13:13,710 --> 01:13:32,360
struct lista, čvor * n, a zatim čvor ** sljedeći?

946
01:13:32,360 --> 01:13:40,240
Mislim da radi dobro.

947
01:13:40,240 --> 01:13:45,940
Mi želimo ići preko lijeve, ili let's - ovdje.

948
01:13:45,940 --> 01:13:54,350
Struct Lista = Lista, to ću početi

949
01:13:54,350 --> 01:13:58,170
se na tom popisu struct.

950
01:13:58,170 --> 01:14:04,040
* Popis = NULL. Tako da će to biti naša povezana popis

951
01:14:04,040 --> 01:14:08,430
od subtrees da smo preskočili.

952
01:14:08,430 --> 01:14:13,800
Mi ćemo proći lijevo sada,

953
01:14:13,800 --> 01:14:17,870
ali budući da smo neminovno morati vratiti na desno,

954
01:14:17,870 --> 01:14:26,140
Mi ćemo zadržati desnu stranu unutar našeg struct popisu.

955
01:14:26,140 --> 01:14:32,620
Tada ćemo imati new_list ili struct,

956
01:14:32,620 --> 01:14:41,080
struct list *, new_list = malloc (sizeof (popis)).

957
01:14:41,080 --> 01:14:44,920
Ja ću ignorirati pogreške provjere, ali trebali biste provjeriti da vidi da li je null.

958
01:14:44,920 --> 01:14:50,540
New_list čvor kada će se ukazati -

959
01:14:50,540 --> 01:14:56,890
oh, to je razlog zašto sam ga htjela ovdje. To će ukazati na drugom struct popisu.

960
01:14:56,890 --> 01:15:02,380
To je samo koliko je vezan liste rad.

961
01:15:02,380 --> 01:15:04,810
To je isto kao int povezane liste

962
01:15:04,810 --> 01:15:06,960
osim samo smo zamjene int s čvora *.

963
01:15:06,960 --> 01:15:11,040
To je točno isti.

964
01:15:11,040 --> 01:15:15,100
Dakle new_list, vrijednost našeg new_list čvora,

965
01:15:15,100 --> 01:15:19,120
će biti sad-> desno.

966
01:15:19,120 --> 01:15:24,280
Vrijednost našeg new_list-> next će biti naš izvorni popis,

967
01:15:24,280 --> 01:15:30,760
i onda ćemo ažurirati naš popis ukazati na new_list.

968
01:15:30,760 --> 01:15:33,650
>> Sada trebamo nekakav način povlačenjem stvari,

969
01:15:33,650 --> 01:15:37,020
kao što smo prelazili cijela lijevo podstablo.

970
01:15:37,020 --> 01:15:40,480
Sada moramo izvući stvari iz nje,

971
01:15:40,480 --> 01:15:43,850
kao sad je null, mi ne želimo samo vratiti false.

972
01:15:43,850 --> 01:15:50,370
Želimo sada povući izvan u našem novom popisu.

973
01:15:50,370 --> 01:15:53,690
Zgodan način za to - dobro, zapravo, postoji više načina za to.

974
01:15:53,690 --> 01:15:56,680
Svatko ima prijedlog?

975
01:15:56,680 --> 01:15:58,790
Gdje bih trebao učiniti ovo ili kako bih trebao učiniti?

976
01:15:58,790 --> 01:16:08,010
Imamo samo nekoliko minuta, ali bilo kakve prijedloge?

977
01:16:08,010 --> 01:16:14,750
Umjesto - jedan način, umjesto našeg stanja bića, dok

978
01:16:14,750 --> 01:16:17,090
ono što mi trenutno gledamo nije null,

979
01:16:17,090 --> 01:16:22,340
umjesto da ćemo i dalje ići do našeg lista sama po sebi je ništavan.

980
01:16:22,340 --> 01:16:25,680
Dakle, ako naš popis završi null,

981
01:16:25,680 --> 01:16:30,680
tada smo ponestane stvari koje treba tražiti, pretraživati.

982
01:16:30,680 --> 01:16:39,860
No, to znači da je prva stvar u našem popisu samo će biti prvi čvor.

983
01:16:39,860 --> 01:16:49,730
Prva stvar će biti - mi više ne treba da se vidi da.

984
01:16:49,730 --> 01:16:58,710
Dakle, popis-> n će biti naša stablo.

985
01:16:58,710 --> 01:17:02,860
Lista-> next će biti nula.

986
01:17:02,860 --> 01:17:07,580
I sada, dok popis ne jednak null.

987
01:17:07,580 --> 01:17:11,610
Sad će se povući nešto s našeg popisa.

988
01:17:11,610 --> 01:17:13,500
Dakle, sad će se jednako Lista-> n.

989
01:17:13,500 --> 01:17:20,850
I onda popis ide na jednak Lista-> n, ili popis-> next.

990
01:17:20,850 --> 01:17:23,480
Dakle, ako sad vrijednost jednaka vrijednosti.

991
01:17:23,480 --> 01:17:28,790
Sada možemo dodati i naše pravo i naš pokazivač lijevo pokazivač

992
01:17:28,790 --> 01:17:32,900
dokle god oni ne null.

993
01:17:32,900 --> 01:17:36,390
Ovdje dolje, mislim da smo trebali učiniti da na prvom mjestu.

994
01:17:36,390 --> 01:17:44,080
Ako (sad-> desno! = NULL)

995
01:17:44,080 --> 01:17:56,380
onda ćemo umetnuti taj čvor u našem popisu.

996
01:17:56,380 --> 01:17:59,290
Ako (sad-> lijevo), ovo je malo dodatnog rada, ali to je u redu.

997
01:17:59,290 --> 01:18:02,690
Ako (sad-> lijevo! = NULL),

998
01:18:02,690 --> 01:18:14,310
i da ćemo umetnuti lijevo u našem povezane liste,

999
01:18:14,310 --> 01:18:19,700
i da bi trebao biti to.

1000
01:18:19,700 --> 01:18:22,670
Mi ponoviti - dokle god imamo nešto u našem listu,

1001
01:18:22,670 --> 01:18:26,640
imamo još jedan čvor da pogledate.

1002
01:18:26,640 --> 01:18:28,920
Dakle, mi gledamo na tom čvoru,

1003
01:18:28,920 --> 01:18:31,390
smo unaprijediti naše liste na sljedeću.

1004
01:18:31,390 --> 01:18:34,060
Ako je čvor je vrijednost tražimo, možemo se vratiti istina.

1005
01:18:34,060 --> 01:18:37,640
Inače umetnite obje naše lijeve i desne subtrees,

1006
01:18:37,640 --> 01:18:40,510
dokle god oni ne null, u našem popisu

1007
01:18:40,510 --> 01:18:43,120
tako da smo neminovno ide preko njih.

1008
01:18:43,120 --> 01:18:45,160
Dakle, ako oni nisu bili null,

1009
01:18:45,160 --> 01:18:47,950
ako je naš korijen pokazivač ukazao na dvije stvari,

1010
01:18:47,950 --> 01:18:51,670
onda na prvi smo izdvajali nešto tako naš popis završi null.

1011
01:18:51,670 --> 01:18:56,890
I onda smo stavili dvije stvari natrag, tako da sada naš popis je veličine dva.

1012
01:18:56,890 --> 01:19:00,030
Onda idemo petlje natrag gore i samo mi ćemo povući,

1013
01:19:00,030 --> 01:19:04,250
recimo, lijevi pokazivač našeg korijena čvora.

1014
01:19:04,250 --> 01:19:07,730
I da ću samo držati se događa, a mi ćemo završiti petlje nad svime.

1015
01:19:07,730 --> 01:19:11,280
>> Primijetit ćete da je to znatno složenija

1016
01:19:11,280 --> 01:19:14,160
u rekurzivne rješenje.

1017
01:19:14,160 --> 01:19:17,260
I ja sam rekao više puta

1018
01:19:17,260 --> 01:19:25,120
da rekurzivna rješenje obično ima mnogo toga zajedničkog s iterativno rješenje.

1019
01:19:25,120 --> 01:19:30,820
Evo to je upravo ono što rekurzivna rješenje radi.

1020
01:19:30,820 --> 01:19:36,740
Jedina promjena je da umjesto implicitno koristi snop, program stog,

1021
01:19:36,740 --> 01:19:40,840
kao način praćenja ono čvorovi još uvijek morate posjetiti,

1022
01:19:40,840 --> 01:19:45,430
Sada imate izričito koristiti povezanu listu.

1023
01:19:45,430 --> 01:19:49,070
U oba slučaja se praćenje onoga čvor uvijek treba posjetio.

1024
01:19:49,070 --> 01:19:51,790
U rekurzivni slučaju to je samo lakše jer stog

1025
01:19:51,790 --> 01:19:57,100
provodi se za vas kao programa stog.

1026
01:19:57,100 --> 01:19:59,550
Obavijest da je to povezano popis, to je stog.

1027
01:19:59,550 --> 01:20:01,580
Što god mi samo staviti na stog

1028
01:20:01,580 --> 01:20:09,960
je odmah što ćemo skinuti hrpu posjetiti sljedeći.

1029
01:20:09,960 --> 01:20:14,380
Mi smo izvan vremena, ali kakvih pitanja?

1030
01:20:14,380 --> 01:20:23,530
[Student, nerazumljivo]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Aha. Dakle, ako imamo povezanu listu,

1032
01:20:27,790 --> 01:20:30,150
struja će ukazati na ovog momka,

1033
01:20:30,150 --> 01:20:34,690
i sada smo samo napreduje naš povezanu listu da se usredotoče na ovim tipom.

1034
01:20:34,690 --> 01:20:44,200
Mi smo prešli preko povezanog popisa u toj liniji.

1035
01:20:44,200 --> 01:20:51,200
I onda mislim da bi trebao osloboditi naše povezanu listu i stvari

1036
01:20:51,200 --> 01:20:53,880
jednom prije povratka istinita ili lažna, trebamo

1037
01:20:53,880 --> 01:20:57,360
iteraciju preko našeg povezanog popisa i uvijek ovdje, pretpostavljam,

1038
01:20:57,360 --> 01:21:03,900
ako mi sad pravo nije jednaka, dodajte ga, tako da sada želimo osloboditi

1039
01:21:03,900 --> 01:21:09,600
sad, jer, dobro, nije mi potpuno zaboraviti na popisu? Aha.

1040
01:21:09,600 --> 01:21:12,880
Dakle, to je ono što želimo učiniti ovdje.

1041
01:21:12,880 --> 01:21:16,730
Gdje je pokazivač?

1042
01:21:16,730 --> 01:21:23,320
Sad je tada bio - mi želimo na struct popis * 10 iznosi popis sljedeći.

1043
01:21:23,320 --> 01:21:29,240
Besplatno popis, popis = temp.

1044
01:21:29,240 --> 01:21:32,820
I u slučaju kada smo se vratili istina, mi trebamo ponoviti

1045
01:21:32,820 --> 01:21:37,050
tijekom ostatka našeg povezanog popisa oslobađanja stvari.

1046
01:21:37,050 --> 01:21:39,700
Lijepo je stvar o rekurzivni rješenje je oslobađanje stvari

1047
01:21:39,700 --> 01:21:44,930
samo znači iskakanje factorings off stog što će se dogoditi za vas.

1048
01:21:44,930 --> 01:21:50,720
Tako smo otišli iz nešto što je kao tri linije teško razmišljati o-koda

1049
01:21:50,720 --> 01:21:57,520
na nešto što je znatno mnogo više teško razmišljati o-linija koda.

1050
01:21:57,520 --> 01:22:00,620
Svaki više pitanja?

1051
01:22:00,620 --> 01:22:08,760
U redu. Mi smo dobro. Bok!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]