1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [7 §: More Comfortable]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvardin yliopisto]

3
00:00:05,090 --> 00:00:07,930
[Tämä on CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Selvä. Niin kuin sanoin email,

5
00:00:10,110 --> 00:00:14,060
Tämä tulee olemaan binary-puu-intensiivinen jakso.

6
00:00:14,060 --> 00:00:16,820
Mutta ei ole kovin monia kysymyksiä.

7
00:00:16,820 --> 00:00:18,920
Joten aiomme yrittää vetää ulos jokaiseen kysymykseen

8
00:00:18,920 --> 00:00:25,430
ja mennä kivulias yksityiskohtaisesti kaikista parhaita tapoja tehdä asioita.

9
00:00:25,430 --> 00:00:31,200
Joten heti alussa, käymme läpi näytteen piirustukset binääripuita ja tavaraa.

10
00:00:31,200 --> 00:00:35,970
Joten tässä, "Muista, että binääripuu on solmuja kaltaisia ​​linkitetty lista,

11
00:00:35,970 --> 00:00:38,150
paitsi yhden sijasta osoittimen on kaksi: yksi vasemmalla "lapsi"

12
00:00:38,150 --> 00:00:41,950
ja yksi oikea "lapsi". "

13
00:00:41,950 --> 00:00:45,630
Joten binääripuu on aivan linkitetyn listan,

14
00:00:45,630 --> 00:00:47,910
lukuun ottamatta struct tulee olemaan kaksi osoitinta.

15
00:00:47,910 --> 00:00:51,390
On trinary puita, jotka ovat menossa on kolme osoitinta,

16
00:00:51,390 --> 00:00:56,540
on N-ary puita, joka on vain yleinen osoittimen

17
00:00:56,540 --> 00:01:00,320
että sinulla on sitten malloc olla niin suuria

18
00:01:00,320 --> 00:01:04,840
riittävästi osoittimia kaikki mahdolliset lapsille.

19
00:01:04,840 --> 00:01:08,200
Joten binääripuu sattuu olemaan vakio määrä on kaksi.

20
00:01:08,200 --> 00:01:11,260
Jos haluat, voit antaa linkitetyn listan unaarinen puu,

21
00:01:11,260 --> 00:01:15,360
mutta en usko, että kukaan kutsuu sitä että.

22
00:01:15,360 --> 00:01:18,060
"Piirrä laatikot-ja-nuolet kaavio binääripuun solmu

23
00:01:18,060 --> 00:01:24,110
sisältävät Nate suosikki numero 7, jossa jokainen lapsi osoitin on nolla. "

24
00:01:24,110 --> 00:01:27,780
Niin iPad tilassa.

25
00:01:27,780 --> 00:01:30,280
>> Se tulee olemaan melko yksinkertainen.

26
00:01:30,280 --> 00:01:36,150
Olemme juuri menossa on solmu, minä piirtää sen neliö.

27
00:01:36,150 --> 00:01:38,730
Ja minä piirtää arvojen täällä.

28
00:01:38,730 --> 00:01:41,090
Joten arvo menee tänne,

29
00:01:41,090 --> 00:01:44,770
ja sitten täällä meillä on vasemman osoittimen vasemmalla ja oikealla osoitin oikealla.

30
00:01:44,770 --> 00:01:50,430
Ja se on erittäin paljon, joten yleissopimuksen kutsua sitä vasemmalle ja oikealle, osoitin nimiä.

31
00:01:50,430 --> 00:01:52,460
Molemmat tulevat olemaan null.

32
00:01:52,460 --> 00:01:57,870
Se vain on nolla, ja se on vasta null.

33
00:01:57,870 --> 00:02:03,630
Okei. Joten takaisin tänne.

34
00:02:03,630 --> 00:02:05,700
"Kun linkitetty lista, meillä oli vain tallentaa osoittimen

35
00:02:05,700 --> 00:02:09,639
ensimmäisen solmun luettelosta, jotta muistaa koko linkitetty lista, tai koko lista.

36
00:02:09,639 --> 00:02:11,650
Samoin puita, meillä on vain tallentaa osoittimen

37
00:02:11,650 --> 00:02:13,420
yhteen solmuun, jotta muistaa koko puun.

38
00:02:13,420 --> 00:02:15,980
Tämä solmu on calle "root" puun.

39
00:02:15,980 --> 00:02:18,320
Kehitä kaaviota ennen tai piirrä uusi

40
00:02:18,320 --> 00:02:21,690
niin että sinulla on laatikoita ja-nuolet kuvaus binääripuun

41
00:02:21,690 --> 00:02:25,730
kanssa arvo 7, sitten 3 vasemmalle,

42
00:02:25,730 --> 00:02:32,760
sitten 9 oikealla puolella, ja sitten 6 oikealla puolella on 3 ".

43
00:02:32,760 --> 00:02:34,810
Katsotaan jos muistan kaiken tuon päähäni.

44
00:02:34,810 --> 00:02:37,670
Joten tämä tulee olemaan meidän root täällä.

45
00:02:37,670 --> 00:02:41,600
Saamme joitakin osoitin jossain, jota me soitamme root,

46
00:02:41,600 --> 00:02:45,140
ja se osoittaa tämän kaveri.

47
00:02:45,140 --> 00:02:48,490
Nyt tehdä uusi solmu,

48
00:02:48,490 --> 00:02:52,870
mitä olemme, 3 vasemmalla?

49
00:02:52,870 --> 00:02:57,140
Joten uusi solmu, jossa on 3, ja se aluksi osoittaa null.

50
00:02:57,140 --> 00:02:59,190
Laitan N.

51
00:02:59,190 --> 00:03:02,250
Nyt haluamme, että mennä vasemmalle 7.

52
00:03:02,250 --> 00:03:06,840
Joten me muuttaa osoittimen nyt kohta tämän kaveri.

53
00:03:06,840 --> 00:03:12,420
Ja me teemme samoin. Haluamme 9 tänne

54
00:03:12,420 --> 00:03:14,620
joka alun perin vain sanoo null.

55
00:03:14,620 --> 00:03:19,600
Me aiomme muuttaa tätä osoitin, kohta 9,

56
00:03:19,600 --> 00:03:23,310
ja nyt haluamme laittaa 6 oikealle 3.

57
00:03:23,310 --> 00:03:32,170
Joten se tulee - tehdä 6.

58
00:03:32,170 --> 00:03:34,310
Ja kaveri osoittaa sinne.

59
00:03:34,310 --> 00:03:38,320
Okei. Niin, että kaikki se pyytää meitä tekemään.

60
00:03:38,320 --> 00:03:42,770
>> Nyt mennään yli joitakin terminologiaa.

61
00:03:42,770 --> 00:03:46,690
Olemme jo puhuneet siitä, miten puun juurta on Ylimmässä solmu puussa.

62
00:03:46,690 --> 00:03:54,720
, Joka sisältää 7. Solmujen alareunassa puun kutsutaan lehtiä.

63
00:03:54,720 --> 00:04:01,240
Jokainen solmu joka juuri on nolla sen lapset on lehtiä.

64
00:04:01,240 --> 00:04:03,680
Niin se on mahdollista, jos meidän binääripuu on vain yksi solmu,

65
00:04:03,680 --> 00:04:10,130
että puu on lehtiä, ja se on siinä.

66
00:04:10,130 --> 00:04:12,060
"Korkeus" puun on hyppyjen määrä sinun täytyy tehdä

67
00:04:12,060 --> 00:04:16,620
saada ylhäältä lehtiä. "

68
00:04:16,620 --> 00:04:18,640
Pääsemme, toisessa, erotus

69
00:04:18,640 --> 00:04:21,940
välillä symmetrinen ja epäsymmetrinen binääripuita,

70
00:04:21,940 --> 00:04:29,470
mutta nyt kokonaiskorkeus tämän puun

71
00:04:29,470 --> 00:04:34,520
Sanoisin on 3, mutta jos lasketaan hyppyjen määrä

72
00:04:34,520 --> 00:04:39,710
sinun täytyy tehdä saadakseen 9, niin se on oikeastaan ​​vain korkeus 2.

73
00:04:39,710 --> 00:04:43,340
Juuri nyt tämä on epätasapainoinen binääripuu,

74
00:04:43,340 --> 00:04:49,840
mutta me puhuimme tasapainossa, kun se saa olla merkitystä.

75
00:04:49,840 --> 00:04:52,040
Joten nyt voimme puhua solmuja puu kannalta

76
00:04:52,040 --> 00:04:54,700
suhteessa muihin solmuihin puussa.

77
00:04:54,700 --> 00:04:59,730
Joten nyt meillä on vanhemmat, lapset, sisarukset, esivanhemmat ja jälkeläiset.

78
00:04:59,730 --> 00:05:05,650
Ne ovat melko tervettä järkeä, mitä ne tarkoittavat.

79
00:05:05,650 --> 00:05:09,610
Jos kysymme - sen vanhemmat.

80
00:05:09,610 --> 00:05:12,830
Joten mikä on vanhempi 3?

81
00:05:12,830 --> 00:05:16,090
[Opiskelijat] 7. >> Joo. Vanhempi vain olemaan mitä osoittaa sinulle.

82
00:05:16,090 --> 00:05:20,510
Sitten mitä lapset 7?

83
00:05:20,510 --> 00:05:23,860
[Opiskelijat] 3 ja 9. >> Joo.

84
00:05:23,860 --> 00:05:26,460
Huomaa, että "lapset" tarkoittaa kirjaimellisesti lapsia,

85
00:05:26,460 --> 00:05:31,010
joten 6 ei sovelleta, koska se on kuin lapsenlapsi.

86
00:05:31,010 --> 00:05:35,540
Mutta jos menemme jälkeläisiä, niin mitkä ovat jälkeläisiä 7?

87
00:05:35,540 --> 00:05:37,500
[Opiskelijat] 3, 6 ja 9. >> Joo.

88
00:05:37,500 --> 00:05:42,330
Jälkeläisiä juurisolmun tulee olemaan kaiken puun,

89
00:05:42,330 --> 00:05:47,950
paitsi ehkä juurisolmu itse, jos et halua katsoa, ​​että jälkeläinen.

90
00:05:47,950 --> 00:05:50,750
Ja lopuksi, esivanhemmat, joten se on vastakkaiseen suuntaan.

91
00:05:50,750 --> 00:05:55,740
Mitkä ovat esi 6?

92
00:05:55,740 --> 00:05:58,920
[Opiskelijat] 3 ja 7. >> Joo. 9 ei sisälly.

93
00:05:58,920 --> 00:06:02,520
Se on vain suoraa linjaa takaisin root

94
00:06:02,520 --> 00:06:13,230
tulee olemaan teidän esivanhempien.

95
00:06:13,230 --> 00:06:16,300
>> "Sanotaan, että binääripuu on" tilattu ", jos kunkin solmun puu,

96
00:06:16,300 --> 00:06:19,530
kaikki sen jälkeläiset vasemmalla on pienempi arvoista

97
00:06:19,530 --> 00:06:22,890
ja kaikki ne oikealla puolella on suuremmat arvot.

98
00:06:22,890 --> 00:06:27,060
Esimerkiksi puu edellä on tilattu, mutta se ei ole ainoa mahdollinen määräsi järjestely. "

99
00:06:27,060 --> 00:06:30,180
Ennen kuin pääsemme siihen,

100
00:06:30,180 --> 00:06:36,420
määräsi binääripuu tunnetaan myös binäärihakupuu.

101
00:06:36,420 --> 00:06:38,660
Täällä sattuvat olemaan kutsuen sitä määräsi binääripuu,

102
00:06:38,660 --> 00:06:41,850
mutta en ole koskaan kuullut sitä kutsutaan tilattu binääripuu ennen,

103
00:06:41,850 --> 00:06:46,650
ja tietovisa olemme paljon todennäköisemmin laittaa binäärihakupuu.

104
00:06:46,650 --> 00:06:49,250
Ne ovat yksi ja sama,

105
00:06:49,250 --> 00:06:54,580
ja se on tärkeää sinulle tunnistaa eron binääripuu ja binäärihakupuu.

106
00:06:54,580 --> 00:06:58,830
Binääripuu on vain puu, joka osoittaa kaksi asiaa.

107
00:06:58,830 --> 00:07:02,120
Jokainen solmu osoittaa kaksi asiaa.

108
00:07:02,120 --> 00:07:06,310
Ei ole perusteluja siitä arvoista että se osoittaa.

109
00:07:06,310 --> 00:07:11,370
Niin kuin tänne, koska se binäärihakupuu,

110
00:07:11,370 --> 00:07:14,030
me tiedämme, että jos menemme jäljellä 7,

111
00:07:14,030 --> 00:07:16,670
Sitten kaikki arvot että voimme mahdollisesti päästä

112
00:07:16,670 --> 00:07:19,310
menemällä jäljellä 7 on oltava pienempi kuin 7.

113
00:07:19,310 --> 00:07:24,070
Huomaa, että kaikki arvot alle 7 ovat 3 ja 6.

114
00:07:24,070 --> 00:07:26,040
Nämä kaikki ovat vasemmalla 7.

115
00:07:26,040 --> 00:07:29,020
Jos menemme oikeaan 7, kaiken pitää olla suurempi kuin 7,

116
00:07:29,020 --> 00:07:33,220
joten 9 on oikeus 7, joten olemme hyviä.

117
00:07:33,220 --> 00:07:36,150
Tämä ei päde binääripuu,

118
00:07:36,150 --> 00:07:40,020
säännöllistä binääripuun voimme vain 3 yläosassa, 7 vasemmalle,

119
00:07:40,020 --> 00:07:47,630
9 vasemmalla 7; ei ole mitään tilaaminen arvojen lainkaan.

120
00:07:47,630 --> 00:07:56,140
Nyt, emme todella tehdä tämän, koska se on työläs ja tarpeeton,

121
00:07:56,140 --> 00:07:59,400
mutta "yrittää tehdä niin monta tilata puita voit ajatella

122
00:07:59,400 --> 00:08:01,900
käyttäen numeroita 7, 3, 9, ja 6.

123
00:08:01,900 --> 00:08:06,800
Kuinka monta erillistä järjestelyt ovat siellä? Mikä on korkeus jokainen? "

124
00:08:06,800 --> 00:08:10,480
>> Teemme pari, mutta tärkein ajatus on,

125
00:08:10,480 --> 00:08:16,530
Tämä ei ole millään tavalla ainutlaatuinen esitys binääripuu, jotka sisältävät näitä arvoja.

126
00:08:16,530 --> 00:08:22,760
Tarvitsemme vain joitakin binääripuu joka sisältää 7, 3, 6 ja 9.

127
00:08:22,760 --> 00:08:25,960
Toinen mahdollinen voimassa yksi olisi juuri on 3,

128
00:08:25,960 --> 00:08:30,260
mene vasemmalle ja se on 6, mene vasemmalle ja se on 7,

129
00:08:30,260 --> 00:08:32,730
mene vasemmalle ja se on 9.

130
00:08:32,730 --> 00:08:36,169
Se on täysin pätevä binäärihakupuu.

131
00:08:36,169 --> 00:08:39,570
Se ei ole kovin hyödyllistä, koska se on aivan kuin linkitetty lista

132
00:08:39,570 --> 00:08:43,750
ja kaikki nämä viitteet ovat vain null.

133
00:08:43,750 --> 00:08:48,900
Mutta se on pätevä puu. Niin?

134
00:08:48,900 --> 00:08:51,310
[Student] Älä arvot on enemmän oikealla?

135
00:08:51,310 --> 00:08:56,700
Vai onko tämä -? >> Nämä Aioin mennä toisinpäin.

136
00:08:56,700 --> 00:09:00,960
Mukana on myös - joo, katsotaanpa vaihtaa se.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Hyvä saalis.

138
00:09:07,770 --> 00:09:11,730
Se on vielä totella mitä binääripuu haku on tarkoitus tehdä.

139
00:09:11,730 --> 00:09:15,650
Joten kaikki vasemmalle on oltava pienempi kuin minkä tahansa solmu.

140
00:09:15,650 --> 00:09:23,180
Voisimme vain liikkua, eli tämä 6 ja laittaa sen tänne.

141
00:09:23,180 --> 00:09:26,880
Ei, emme voi. Miksi pitää tehdä, että?

142
00:09:26,880 --> 00:09:35,350
Tehdäänpä - tässä on 6, täällä on 7, 6 pistettä 3.

143
00:09:35,350 --> 00:09:39,290
Tämä on edelleen voimassa binäärihakupuu.

144
00:09:39,290 --> 00:09:49,260
Mikä on vialla, jos I - Katsotaan jos voin keksiä järjestely.

145
00:09:49,260 --> 00:09:52,280
Joo, okei. Joten mikä on vikana puu?

146
00:09:52,280 --> 00:10:08,920
Olen kai jo antanut sinulle vihjeen, että on jotain vikaa.

147
00:10:08,920 --> 00:10:14,430
Miksi pitää tehdä, että?

148
00:10:14,430 --> 00:10:18,510
Okei. Tämä näyttää kohtuulliselta.

149
00:10:18,510 --> 00:10:22,590
Jos tarkastelemme jokaisessa solmussa, kuten 7, sitten vasemmalle 7 on 3.

150
00:10:22,590 --> 00:10:24,960
Joten meillä on 3, asia oikealla 3 on 6.

151
00:10:24,960 --> 00:10:27,750
Ja jos tarkastellaan 6, asia oikealla 6 on 9.

152
00:10:27,750 --> 00:10:30,910
Miksi tämä ei ole kelvollinen binäärihakupuu?

153
00:10:30,910 --> 00:10:36,330
[Opiskelijat] 9 on edelleen vasemmalla 7. >> Joo.

154
00:10:36,330 --> 00:10:43,710
Sen täytyy olla totta, että kaikki arvot voi mahdollisesti päästä menemällä vasemmalla 7 ovat alle 7.

155
00:10:43,710 --> 00:10:49,120
Jos menemme jäljellä 7, saamme 3 ja voimme vielä päästä 6,

156
00:10:49,120 --> 00:10:52,520
voimme silti saada 9, mutta mentyään alle 7,

157
00:10:52,520 --> 00:10:55,070
Meidän ei pitäisi voida saada numero, joka on suurempi kuin 7.

158
00:10:55,070 --> 00:10:59,830
Joten tämä ei ole kelvollinen binäärihakupuu.

159
00:10:59,830 --> 00:11:02,330
>> Veljeni oli todellakin haastattelu kysymys

160
00:11:02,330 --> 00:11:07,760
se oli pohjimmiltaan tämä, vain koodin jopa jotain validoida

161
00:11:07,760 --> 00:11:10,500
onko puu on binäärihakupuu,

162
00:11:10,500 --> 00:11:13,580
ja niin ensimmäinen asia, jonka hän teki, oli vain tarkistaa

163
00:11:13,580 --> 00:11:17,020
jos vasen ja oikea ovat oikein, ja sitten toistaa sinne.

164
00:11:17,020 --> 00:11:19,700
Mutta et voi vain tehdä niin, sinun täytyy seurata

165
00:11:19,700 --> 00:11:22,550
siitä, että nyt kun olen mennyt jäljellä 7,

166
00:11:22,550 --> 00:11:26,340
kaikki tämä alipuu on oltava alle 7.

167
00:11:26,340 --> 00:11:28,430
Oikea algoritmi tarvitsee seurata

168
00:11:28,430 --> 00:11:35,970
ja rajojen että arvot voivat mahdollisesti kuulua sisään

169
00:11:35,970 --> 00:11:38,360
Emme mene läpi niitä kaikkia.

170
00:11:38,360 --> 00:11:41,630
On kiva toistumisen suhteen,

171
00:11:41,630 --> 00:11:44,810
vaikka emme ole saaneet niitä, tai emme pääse niihin,

172
00:11:44,810 --> 00:11:47,030
määritellään kuinka monta todellisuudessa ovat.

173
00:11:47,030 --> 00:11:53,180
Joten on 14 niistä.

174
00:11:53,180 --> 00:11:56,020
Ajatus siitä, miten tekisit sen matemaattisesti on kuin,

175
00:11:56,020 --> 00:11:59,770
Voit valita minkä tahansa ikinen olla juurisolmu

176
00:11:59,770 --> 00:12:03,160
ja sitten jos otan 7 olla juurisolmu

177
00:12:03,160 --> 00:12:08,150
sitten on, sanovat, jotkut numerot voivat mennä minun vasen solmu,

178
00:12:08,150 --> 00:12:10,440
ja joitakin numeroita, jotka voivat olla minun oikea solmu,

179
00:12:10,440 --> 00:12:15,090
mutta jos olen N Yhteensä numeroita, niin summa voi mennä vasemmalle

180
00:12:15,090 --> 00:12:18,820
korotettuna joka voi mennä oikealle on n - 1.

181
00:12:18,820 --> 00:12:26,130
Niin, että jäljelle jäävät numerot, niiden on kyettävä menemään joko vasemmalle tai oikealle.

182
00:12:26,130 --> 00:12:31,580
On vaikeaa, että jos laitan 3 ensimmäinen sitten kaiken on mentävä vasemmalle,

183
00:12:31,580 --> 00:12:35,080
mutta jos laitan 7, niin jotkut asiat voivat mennä vasemmalle ja jotkut asiat voivat mennä oikealle.

184
00:12:35,080 --> 00:12:39,570
Ja '3 ensimmäinen "Tarkoitin kaikkea voi mennä oikealle.

185
00:12:39,570 --> 00:12:42,350
Se on todella, sinun täytyy vain ajatella sitä,

186
00:12:42,350 --> 00:12:47,980
kuinka paljon voi mennä seuraavalle tasolle puun.

187
00:12:47,980 --> 00:12:50,420
Ja se tulee ulos on 14, tai voit piirtää ne kaikki,

188
00:12:50,420 --> 00:12:54,650
ja sitten saat 14.

189
00:12:54,650 --> 00:13:01,120
>> Going takaisin tänne,

190
00:13:01,120 --> 00:13:03,510
"Tilattu binääripuita ovat viileitä, koska voimme etsiä niitä

191
00:13:03,510 --> 00:13:06,910
hyvin samalla tavalla hakemisen yli lajitellaan matriisina.

192
00:13:06,910 --> 00:13:10,120
Voit tehdä niin, aloitamme juuresta ja työskentelemme alas puusta

193
00:13:10,120 --> 00:13:13,440
kohti lehtiä, tarkistaa kunkin solmun arvot arvojen vastaisia ​​olemme etsimässä.

194
00:13:13,440 --> 00:13:15,810
Jos nykyinen solmun arvo on pienempi kuin arvo etsimme,

195
00:13:15,810 --> 00:13:18,050
menet vieressä solmun oikea lapsi.

196
00:13:18,050 --> 00:13:20,030
Muuten menet solmun vasen lapsi.

197
00:13:20,030 --> 00:13:22,800
Jossain vaiheessa, voit joko löytää arvo etsit, tai voit törmätä null,

198
00:13:22,800 --> 00:13:28,520
arvoa osoittava ei puussa. "

199
00:13:28,520 --> 00:13:32,450
Minun täytyy piirtää puun meillä oli ennen, että otan toisen.

200
00:13:32,450 --> 00:13:38,280
Mutta me haluamme etsiä onko 6, 10, ja 1 ovat puussa.

201
00:13:38,280 --> 00:13:49,180
Joten mitä se oli, 7, 9, 3, 6. Okei.

202
00:13:49,180 --> 00:13:52,730
Numerot haluat etsiä, haluamme etsiä 6.

203
00:13:52,730 --> 00:13:55,440
Miten tämä algoritmi toimii?

204
00:13:55,440 --> 00:14:03,040
No, meillä on myös joitakin root osoitin meidän puu.

205
00:14:03,040 --> 00:14:12,460
Ja me menisi juuri ja sanoa, on tämä arvo vastaa arvoa olemme etsimässä?

206
00:14:12,460 --> 00:14:15,000
Joten etsimme 6, joten se ei ole sama.

207
00:14:15,000 --> 00:14:20,140
Joten pidämme menossa, ja nyt sanomme, okei, joten 6 on alle 7.

208
00:14:20,140 --> 00:14:23,940
Tarkoittaako se, että haluamme mennä vasemmalle, vai haluammeko mennä oikealle?

209
00:14:23,940 --> 00:14:27,340
[Student] Vasen. >> Joo.

210
00:14:27,340 --> 00:14:33,340
Se on huomattavasti helpompaa, kaikki sinun tarvitsee vain vetää yhden mahdollisen solmu puun

211
00:14:33,340 --> 00:14:37,760
ja sitten älä - sen sijaan, että yrittää ajatella oman pään,

212
00:14:37,760 --> 00:14:40,020
okei, jos se on vähemmän, menen vasemmalle tai mennä oikealle,

213
00:14:40,020 --> 00:14:43,030
vain katsomalla tätä kuvaa, se on hyvin selvää, että minun täytyy mennä vasemmalle

214
00:14:43,030 --> 00:14:47,700
jos tämä solmu on suurempi kuin arvo, joka etsin.

215
00:14:47,700 --> 00:14:52,600
Joten te mennä vasemmalle, nyt olen 3.

216
00:14:52,600 --> 00:14:57,770
Haluan - 3 on pienempi kuin arvo etsin, joka on 6.

217
00:14:57,770 --> 00:15:03,420
Joten menemme oikealle, ja nyt minä päädy 6,

218
00:15:03,420 --> 00:15:07,380
mikä on arvo etsin, joten palaan totta.

219
00:15:07,380 --> 00:15:15,760
Seuraava arvo aion etsiä on 10.

220
00:15:15,760 --> 00:15:23,230
Okei. Joten 10, nyt on menossa - katkaista joka - aikoo seurata juuri.

221
00:15:23,230 --> 00:15:27,670
Nyt, 10 tulee olemaan suurempi kuin 7, joten haluan katsoa oikealle.

222
00:15:27,670 --> 00:15:31,660
Aion tulla tänne, 10 tulee olemaan suurempi kuin 9,

223
00:15:31,660 --> 00:15:34,520
joten aion haluta katsoa oikealle.

224
00:15:34,520 --> 00:15:42,100
Tulen tänne, mutta täällä nyt olen null.

225
00:15:42,100 --> 00:15:44,170
Mitä teen, jos osuin null?

226
00:15:44,170 --> 00:15:47,440
[Student] Return väärä? >> Joo. En löytänyt 10.

227
00:15:47,440 --> 00:15:49,800
1 tulee olemaan lähes identtinen tapauksessa,

228
00:15:49,800 --> 00:15:51,950
paitsi se vain menee kääntää, vaan tarkastella

229
00:15:51,950 --> 00:15:56,540
alas oikealle puolelle, aion katsoa alas vasemmalle puolelle.

230
00:15:56,540 --> 00:16:00,430
>> Nyt mielestäni itse saada koodin.

231
00:16:00,430 --> 00:16:04,070
Tässä jos - avata CS50 laite ja navigoi perille,

232
00:16:04,070 --> 00:16:07,010
mutta voit myös vain tehdä sen avaruudessa.

233
00:16:07,010 --> 00:16:09,170
Se on luultavasti ihanteellinen tehdä se tilaan,

234
00:16:09,170 --> 00:16:13,760
koska voimme työskennellä avaruudessa.

235
00:16:13,760 --> 00:16:19,170
"Ensin me tarvitsemme uuden tyyppinen määritelmä binääripuu solmu sisältää int-arvoja.

236
00:16:19,170 --> 00:16:21,400
Käyttämällä boilerplate typedef alla,

237
00:16:21,400 --> 00:16:24,510
luoda uuden tyyppinen määritelmä solmun binääripuu.

238
00:16:24,510 --> 00:16:27,930
Jos jäät jumiin. . . "Blaa, blaa, blaa. Okei.

239
00:16:27,930 --> 00:16:30,380
Joten laita boilerplate täällä,

240
00:16:30,380 --> 00:16:41,630
typedef struct solmu, ja solmu. Joo, okei.

241
00:16:41,630 --> 00:16:44,270
Joten mitä kenttiä aiomme haluavat meidän solmussa?

242
00:16:44,270 --> 00:16:46,520
[Opiskelija] Int ja sitten kaksi osoitinta?

243
00:16:46,520 --> 00:16:49,700
>> Int-arvo, kaksi osoitinta? Miten kirjoittaa viitteitä?

244
00:16:49,700 --> 00:16:58,440
[Student] Struct. >> Minun pitäisi Lähennä Joo, niin struct solmu * vasemmalle,

245
00:16:58,440 --> 00:17:01,320
ja struct solmu * oikealle.

246
00:17:01,320 --> 00:17:03,460
Ja muistakaa keskustelua viime kerran,

247
00:17:03,460 --> 00:17:15,290
että tämä ei ole mitään järkeä, tämä ei ole mitään järkeä,

248
00:17:15,290 --> 00:17:18,270
Tässä ei ole mitään järkeä.

249
00:17:18,270 --> 00:17:25,000
Tarvitset kaiken siellä voidakseen määritellä tämän rekursiivinen struct.

250
00:17:25,000 --> 00:17:27,970
Okei, niin se mitä meidän puu tulee näyttämään.

251
00:17:27,970 --> 00:17:37,670
Jos emme trinary puu, sitten solmu voisi näyttää B1, B2, struct solmu * b3,

252
00:17:37,670 --> 00:17:43,470
missä b on sivuliike - itse olen enemmän kuullut vasemmalle, keskelle, oikealle, mutta mitä.

253
00:17:43,470 --> 00:17:55,610
Me vain välitä binary, joten oikea, vasen.

254
00:17:55,610 --> 00:17:59,110
"Nyt julistaa maailmanlaajuinen solmu * muuttuja puun juurelle."

255
00:17:59,110 --> 00:18:01,510
Eli emme aio tehdä sitä.

256
00:18:01,510 --> 00:18:08,950
Jotta asiat hieman vaikeampaa ja enemmän yleistynyt,

257
00:18:08,950 --> 00:18:11,570
meillä ei ole maailmanlaajuinen solmu muuttuja.

258
00:18:11,570 --> 00:18:16,710
Sen sijaan pääasiassa me julistaa kaikki solmun asioita,

259
00:18:16,710 --> 00:18:20,500
ja se tarkoittaa, että alla, kun aloitamme käynnissä

260
00:18:20,500 --> 00:18:23,130
meidän on toimintomoduuleja ja meidän insert toiminto,

261
00:18:23,130 --> 00:18:27,410
sijaan meidän on toimintomoduuleja vain käyttämällä tätä maailmanlaajuista solmuun muuttuja,

262
00:18:27,410 --> 00:18:34,280
aiomme olla se ottaa niin väitteen puu että haluamme käsitellä.

263
00:18:34,280 --> 00:18:36,650
Ottavat globaalin muuttujan piti helpottaa asioita.

264
00:18:36,650 --> 00:18:42,310
Aiomme tehdä asioita vaikeampaa.

265
00:18:42,310 --> 00:18:51,210
Nyt kestää minuutin tai niin vain tehdä tällaista asiaa,

266
00:18:51,210 --> 00:18:57,690
jossa sisällä tärkeimmistä haluat luoda tätä puuta, ja se on kaikki mitä haluat tehdä.

267
00:18:57,690 --> 00:19:04,530
Kokeile ja rakentaa tämän puun teidän päätehtävä.

268
00:19:42,760 --> 00:19:47,610
>> Okei. Joten sinun ei edes tarvitse olla rakennettu puusta koko tie vielä.

269
00:19:47,610 --> 00:19:49,840
Mutta kellään jotain voisin vetää ylös

270
00:19:49,840 --> 00:20:03,130
osoittaa, miten joku voisi alkaa rakentaa sellainen puu?

271
00:20:03,130 --> 00:20:08,080
[Opiskelijan] Joku paukutti, yrittää saada pois.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Jokainen mukava niiden puukonstruktion?

273
00:20:13,100 --> 00:20:15,520
[Student] Toki. Se ei ole tehnyt. >> Se on hieno. Voimme vain lopettaa -

274
00:20:15,520 --> 00:20:26,860
oh, voit tallentaa sen? Hurraa.

275
00:20:26,860 --> 00:20:32,020
Joten tässä olemme - Voi, olen hieman leikattu.

276
00:20:32,020 --> 00:20:34,770
Olenko zoomataan?

277
00:20:34,770 --> 00:20:37,730
Lähennä selaamalla ulos. >> Minulla on kysymys. >> Niin?

278
00:20:37,730 --> 00:20:44,410
[Opiskelija] Kun määrität struct, ovat asioita, kuten alustettu mitään?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Okei. Joten sinun olisi alustamaan -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Kun määritellä, tai kun julistaa struct,

281
00:20:50,450 --> 00:20:55,600
se ei ole alustettu oletuksena, se on aivan kuin jos julistaa int.

282
00:20:55,600 --> 00:20:59,020
Se on aivan sama asia. Se on kuin jokainen sen yksittäisten kenttien

283
00:20:59,020 --> 00:21:04,460
voi olla roska arvo sitä. >> Ja on mahdollista määritellä - tai julistaa struct

284
00:21:04,460 --> 00:21:07,740
siten, että se tekee ne alustaa?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Kyllä. Joten pikakuvake alustus syntaksi

286
00:21:13,200 --> 00:21:18,660
tulee näyttämään -

287
00:21:18,660 --> 00:21:22,200
On kaksi tapaa voimme tehdä tämän. Mielestäni meidän pitäisi laatia sen

288
00:21:22,200 --> 00:21:25,840
varmista clang tekee myös tämän.

289
00:21:25,840 --> 00:21:28,510
Argumenttien järjestystä, joka tulee struct,

290
00:21:28,510 --> 00:21:32,170
laitat sillä argumenttien järjestystä sisällä näitä aaltosulkeita.

291
00:21:32,170 --> 00:21:35,690
Joten jos haluat alustaa sen 9 ja vasemmalle on nolla, ja sitten oikealle olla null,

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

293
00:21:41,570 --> 00:21:47,890
Vaihtoehtona on, ja toimittaja ei pidä tätä syntaksia,

294
00:21:47,890 --> 00:21:50,300
ja se luulee haluan uuden lohkon,

295
00:21:50,300 --> 00:22:01,800
mutta vaihtoehtona on jotain -

296
00:22:01,800 --> 00:22:04,190
täällä, laitan sen uuden linjan.

297
00:22:04,190 --> 00:22:09,140
Voit erikseen sanoa, unohdan tarkka syntaksi.

298
00:22:09,140 --> 00:22:13,110
Joten voit nimenomaan käsitellä heitä nimeltä, ja sanoa,

299
00:22:13,110 --> 00:22:21,570
. C tai. Arvo = 9,. Vasen = NULL.

300
00:22:21,570 --> 00:22:24,540
Olen arvaamaan näitä on pilkkuja.

301
00:22:24,540 --> 00:22:29,110
. Oikea = NULL, joten tällä tavalla ei

302
00:22:29,110 --> 00:22:33,780
todella tarvitsee tietää järjestystä struct,

303
00:22:33,780 --> 00:22:36,650
ja kun luet tätä, se on paljon selkeämpi

304
00:22:36,650 --> 00:22:41,920
mitä arvoa on parhaillaan alustetaan.

305
00:22:41,920 --> 00:22:44,080
>> Tämä sattuu olemaan yksi niistä asioista, jotka -

306
00:22:44,080 --> 00:22:49,100
niin, että suurin osa, C + + on pääjoukko C.

307
00:22:49,100 --> 00:22:54,160
Voit ottaa C-koodia, siirrä se yli C + +, ja se pitäisi laatia.

308
00:22:54,160 --> 00:22:59,570
Tämä on yksi niistä asioista, että C + + ei tue, joten ihmiset eivät yleensä tee sitä.

309
00:22:59,570 --> 00:23:01,850
En tiedä, jos se on ainoa syy, ihmiset eivät yleensä tee sitä,

310
00:23:01,850 --> 00:23:10,540
mutta jos minun piti käyttää sitä tarpeen työskennellä C + +, joten en voinut käyttää tätä.

311
00:23:10,540 --> 00:23:14,000
Toinen esimerkki jotain, joka ei toimi C + + on

312
00:23:14,000 --> 00:23:16,940
miten malloc palauttaa "void *," teknisesti,

313
00:23:16,940 --> 00:23:20,200
mutta voisitte sanoa char * x = malloc tahansa,

314
00:23:20,200 --> 00:23:22,840
ja se automaattisesti valetaan char *.

315
00:23:22,840 --> 00:23:25,450
Tämä automaattinen valettu ei tapahdu C + +.

316
00:23:25,450 --> 00:23:28,150
Se ei kerätä, ja sinulla olisi nimenomaisesti täytyy sanoa

317
00:23:28,150 --> 00:23:34,510
char *, malloc, mitä, heittää se char *.

318
00:23:34,510 --> 00:23:37,270
Ei ole monia asioita, jotka C ja C + + eri mieltä,

319
00:23:37,270 --> 00:23:40,620
mutta nämä ovat kaksi.

320
00:23:40,620 --> 00:23:43,120
Joten me menemme tällä syntaksilla.

321
00:23:43,120 --> 00:23:46,150
Mutta vaikka emme mene että syntaksi,

322
00:23:46,150 --> 00:23:49,470
mikä on - voi olla vikana?

323
00:23:49,470 --> 00:23:52,170
[Opiskelija] En tarvitse dereference sitä? >> Joo.

324
00:23:52,170 --> 00:23:55,110
Muista, että nuoli on implisiittinen dereference,

325
00:23:55,110 --> 00:23:58,230
ja niin kun me vain tekemisissä struct,

326
00:23:58,230 --> 00:24:04,300
haluamme käyttää. saada aikaa kentän sisällä struct.

327
00:24:04,300 --> 00:24:07,200
Ja ainoa kerta käytämme nuoli on, kun me haluamme tehdä -

328
00:24:07,200 --> 00:24:13,450
hyvin, nuoli vastaa -

329
00:24:13,450 --> 00:24:17,020
niinhän se olisi tarkoittanut, jos käytin nuolta.

330
00:24:17,020 --> 00:24:24,600
Kaikki nuoli tarkoittaa on, dereference tätä, nyt olen struct, ja saan kenttään.

331
00:24:24,600 --> 00:24:28,040
Joko saat kentän suoraan tai dereference ja saada kenttä -

332
00:24:28,040 --> 00:24:30,380
Kai tämä olisi arvoa.

333
00:24:30,380 --> 00:24:33,910
Mutta tässä olen tekemisissä vain struct, ei osoitin struct,

334
00:24:33,910 --> 00:24:38,780
joten en voi käyttää nuoli.

335
00:24:38,780 --> 00:24:47,510
Mutta tällaista asiaa voimme tehdä kaikki solmut.

336
00:24:47,510 --> 00:24:55,790
Voi luoja.

337
00:24:55,790 --> 00:25:09,540
Tämä on 6, 7, ja 3.

338
00:25:09,540 --> 00:25:16,470
Sitten voimme perustaa sivuliikkeitä meidän puu, meillä voi olla 7 -

339
00:25:16,470 --> 00:25:21,650
Meillä voi olla, sen vasemmalle pitäisi kohta 3.

340
00:25:21,650 --> 00:25:25,130
Joten miten me sen teemme?

341
00:25:25,130 --> 00:25:29,320
[Opiskelijat, käsittämätön] >> Joo. Osoite node3,

342
00:25:29,320 --> 00:25:34,170
ja jos sinulla ei ole osoitetta, se vain ei kerätä.

343
00:25:34,170 --> 00:25:38,190
Mutta muistakaa, että nämä ovat osoittimia seuraavaan solmut.

344
00:25:38,190 --> 00:25:44,930
Oikeus tulisi osoittaa 9,

345
00:25:44,930 --> 00:25:53,330
ja 3 olisi piste oikeus 6.

346
00:25:53,330 --> 00:25:58,480
Mielestäni tämä on kaikki asetettu. Kommentteja tai kysymyksiä?

347
00:25:58,480 --> 00:26:02,060
[Student, käsittämätön] root tulee olemaan 7.

348
00:26:02,060 --> 00:26:08,210
Voimme vain sanoa solmu * ptr =

349
00:26:08,210 --> 00:26:14,160
tai root, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Meidän kannalta, aiomme olla tekemisissä insert,

351
00:26:20,730 --> 00:26:25,490
joten olemme menossa halua kirjoittaa funktion lisätä tähän binaaripuun

352
00:26:25,490 --> 00:26:34,230
ja insertti on väistämättä menossa soittaa malloc luoda uusi solmu tämän puun.

353
00:26:34,230 --> 00:26:36,590
Joten asiat menevät sotkuinen, että jotkut solmut

354
00:26:36,590 --> 00:26:38,590
Tällä hetkellä pinoon

355
00:26:38,590 --> 00:26:43,680
ja muut solmut ovat menossa päätyä kasaan kun lisäämme niitä.

356
00:26:43,680 --> 00:26:47,640
Tämä on täysin pätevä, mutta ainoa syy

357
00:26:47,640 --> 00:26:49,600
pystymme tekemään tämän pinoon

358
00:26:49,600 --> 00:26:51,840
koska se on niin keinotekoinen esimerkki siitä, että tiedämme

359
00:26:51,840 --> 00:26:56,360
puu on tarkoitus olla rakennettu 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Jos meillä ei ole tätä, niin meillä ei tarvitsisi malloc ensimmäinen paikka.

361
00:27:02,970 --> 00:27:06,160
Kuten näemme hieman myöhemmin, meidän pitäisi malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Juuri nyt se on täysin järkevää laittaa pinon

363
00:27:08,570 --> 00:27:14,750
mutta katsotaanpa muuttaa tämän malloc toteuttamiseen.

364
00:27:14,750 --> 00:27:17,160
Joten jokainen nyt olemaan jotain

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

366
00:27:24,240 --> 00:27:28,040
Ja nyt me aiomme pitää teemme tarkastus.

367
00:27:28,040 --> 00:27:34,010
jos (node9 == NULL) - En halua, että -

368
00:27:34,010 --> 00:27:40,950
palaa 1, ja sitten voimme tehdä node9-> koska nyt on osoitin,

369
00:27:40,950 --> 00:27:45,300
value = 6, node9-> vasen = NULL,

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

371
00:27:48,930 --> 00:27:51,410
ja aiomme pitää tehdä, että jokaiselle näistä solmuista.

372
00:27:51,410 --> 00:27:57,490
Joten sen sijaan, katsotaanpa laita se sisällä erillisenä toimintona.

373
00:27:57,490 --> 00:28:00,620
Sanotaan se solmu * build_node,

374
00:28:00,620 --> 00:28:09,050
ja tämä on jossain määrin samanlainen kuin API me säätää Huffman-koodausta.

375
00:28:09,050 --> 00:28:12,730
Annamme sinulle alustajan toiminnot puu

376
00:28:12,730 --> 00:28:20,520
ja Deconstructor "toiminnot" niille puita ja sama metsiä.

377
00:28:20,520 --> 00:28:22,570
>> Joten tässä me aiomme olla alustajan toiminto

378
00:28:22,570 --> 00:28:25,170
vain rakentaa solmu meille.

379
00:28:25,170 --> 00:28:29,320
Ja se tulee näyttämään melko paljon juuri näin.

380
00:28:29,320 --> 00:28:32,230
Ja minä vielä olemaan laiska eikä muuttaa muuttujan nimi,

381
00:28:32,230 --> 00:28:34,380
vaikka tosin node9 ole mitään järkeä enää.

382
00:28:34,380 --> 00:28:38,610
Voi kai node9 arvo ei olisi ollut 6.

383
00:28:38,610 --> 00:28:42,800
Nyt voimme palata node9.

384
00:28:42,800 --> 00:28:49,550
Ja täällä pitäisi palata null.

385
00:28:49,550 --> 00:28:52,690
Jokainen samaa mieltä build-solmun funktio?

386
00:28:52,690 --> 00:28:59,780
Joten nyt voimme vain soittaa, että rakentaa mitään solmu tiettyyn arvoon ja null viitteitä.

387
00:28:59,780 --> 00:29:09,750
Nyt voimme kutsua, että voimme tehdä solmu * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Ja tehkäämme. . .

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

390
00:29:33,980 --> 00:29:39,330
Ja nyt me haluamme perustaa saman osoittimia,

391
00:29:39,330 --> 00:29:42,470
paitsi nyt kaikki on jo suhteen osoittimia

392
00:29:42,470 --> 00:29:48,480
joten ei enää tarvitse osoite.

393
00:29:48,480 --> 00:29:56,300
Okei. Joten mikä on viimeinen asia, jonka haluan tehdä?

394
00:29:56,300 --> 00:30:03,850
On virhe tarkkailun että en ole tekemässä.

395
00:30:03,850 --> 00:30:06,800
Mitä rakentaa solmu paluuta?

396
00:30:06,800 --> 00:30:11,660
[Student, käsittämätön] >> Joo. Jos malloc epäonnistui, se tulee palauttaa null.

397
00:30:11,660 --> 00:30:16,460
Joten aion laiskasti laittaa sen tänne sen sijaan tehdä edellytys jokaiselle.

398
00:30:16,460 --> 00:30:22,320
Jos (node9 == NULL tai - vielä yksinkertaisempi,

399
00:30:22,320 --> 00:30:28,020
tämä vastaa vain, jos ei ole node9.

400
00:30:28,020 --> 00:30:38,310
Joten jos ei node9, tai ei node6, tai ei node3, tai ei node7, palaa 1.

401
00:30:38,310 --> 00:30:42,850
Ehkä meidän pitäisi tulostaa malloc epäonnistui, tai jotain.

402
00:30:42,850 --> 00:30:46,680
[Student] Onko vääriä yhtä null samoin?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Kaikki nolla on epätosi.

404
00:30:51,290 --> 00:30:53,920
Joten null on nolla.

405
00:30:53,920 --> 00:30:56,780
Nolla on nolla. False on nolla.

406
00:30:56,780 --> 00:31:02,130
Jokainen - melko paljon vain 2 nolla-arvot ovat nolla ja nolla,

407
00:31:02,130 --> 00:31:07,900
väärä on aivan hash määritelty nollaksi.

408
00:31:07,900 --> 00:31:13,030
Tämä pätee myös, jos emme julistaa globaali muuttuja.

409
00:31:13,030 --> 00:31:17,890
Jos meillä oli solmu * root täällä,

410
00:31:17,890 --> 00:31:24,150
Sitten - Kiva juttu globaaleja muuttujia on, että ne ovat aina alkuarvo.

411
00:31:24,150 --> 00:31:27,500
Se ei ole totta toimintoja, kuinka sisällä täällä,

412
00:31:27,500 --> 00:31:34,870
jos meillä on, kuten, solmu * tai solmu x.

413
00:31:34,870 --> 00:31:37,380
Meillä ei ole aavistustakaan, mitä x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
tai voisimme tulostaa ne ja ne voivat olla mielivaltaisia.

415
00:31:40,700 --> 00:31:44,980
Se ei ole totta globaaleja muuttujia.

416
00:31:44,980 --> 00:31:47,450
Joten solmu root tai solmu x.

417
00:31:47,450 --> 00:31:53,410
Oletusarvoisesti kaikki, globaali, ellei nimenomaisesti alustetaan jotain arvoa,

418
00:31:53,410 --> 00:31:57,390
arvo on nolla, koska sen arvo.

419
00:31:57,390 --> 00:32:01,150
Joten tässä, solmu * root, emme erikseen alustaa sitä mihinkään,

420
00:32:01,150 --> 00:32:06,350
joten sen oletusarvo on nolla, joka on nolla-arvo osoittimia.

421
00:32:06,350 --> 00:32:11,870
Oletusarvo x on menossa tarkoita, että x.value on nolla,

422
00:32:11,870 --> 00:32:14,260
x.left on nolla, ja x.right on nolla.

423
00:32:14,260 --> 00:32:21,070
Niin koska se on struct, kaikki kentät struct on nolla-arvot.

424
00:32:21,070 --> 00:32:24,410
Meidän ei tarvitse käyttää sitä tässä, vaikka.

425
00:32:24,410 --> 00:32:27,320
[Student] tietueet ovat erilaisia ​​kuin muut muuttujat, ja muut muuttujat ovat

426
00:32:27,320 --> 00:32:31,400
roska-arvot; nämä ovat nollia?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Muut arvot myös. Joten x, x on nolla.

428
00:32:36,220 --> 00:32:40,070
Jos se on maailmanlaajuisesti soveltamisalaa, sillä on alkuarvo. >> Okei.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Joko alkuarvo annoit sen tai nolla.

430
00:32:48,950 --> 00:32:53,260
Mielestäni huolehtii kaiken tämän.

431
00:32:53,260 --> 00:32:58,390
>> Okei. Joten seuraava osa kysymyksessä tiedustellaan,

432
00:32:58,390 --> 00:33:01,260
"Nyt haluamme kirjoittaa toiminto nimeltään sisältää

433
00:33:01,260 --> 00:33:04,930
jossa prototyyppi bool sisältää int arvo. "

434
00:33:04,930 --> 00:33:08,340
Emme aio tehdä bool sisältää int arvo.

435
00:33:08,340 --> 00:33:15,110
Meidän prototyyppi tulee näyttämään

436
00:33:15,110 --> 00:33:22,380
bool sisältää (int arvo.

437
00:33:22,380 --> 00:33:24,490
Ja sitten me myös menossa ohi se puu

438
00:33:24,490 --> 00:33:28,870
että se olisi tarkistaa, jos se on, että arvo.

439
00:33:28,870 --> 00:33:38,290
Joten solmu * puu). Okei.

440
00:33:38,290 --> 00:33:44,440
Ja sitten voimme kutsua sitä jotain,

441
00:33:44,440 --> 00:33:46,090
Ehkä me haluamme printf tai jotain.

442
00:33:46,090 --> 00:33:51,040
Sisältää 6, meidän root.

443
00:33:51,040 --> 00:33:54,300
Tämän pitäisi palauttaa yhden tai totta,

444
00:33:54,300 --> 00:33:59,390
taas sisältää 5 root pitäisi palauttaa false.

445
00:33:59,390 --> 00:34:02,690
Joten ota toinen toteuttaa tämän.

446
00:34:02,690 --> 00:34:06,780
Voit tehdä sen joko iteratiivisesti tai rekursiivisesti.

447
00:34:06,780 --> 00:34:09,739
Kiva juttu miten olemme asettaa asioita on, että

448
00:34:09,739 --> 00:34:12,300
se on omiaan meidän rekursiivinen ratkaisu paljon helpompaa

449
00:34:12,300 --> 00:34:14,719
kuin globaali muuttujan tavalla teki.

450
00:34:14,719 --> 00:34:19,750
Koska jos meillä vain on sisältää int arvo, niin meillä ei ole mitään mahdollisuuksia recursing alas alipuut.

451
00:34:19,750 --> 00:34:24,130
Meidän täytyisi olla erillinen auttaja toiminnon recurses alas alipuut meille.

452
00:34:24,130 --> 00:34:29,610
Mutta koska olemme muuttaneet sen ottaa puuta argumentti,

453
00:34:29,610 --> 00:34:32,760
jotka sen olisi pitänyt aina ollut ensimmäinen paikka,

454
00:34:32,760 --> 00:34:35,710
Nyt voimme recurse helpommin.

455
00:34:35,710 --> 00:34:38,960
Joten iteratiivinen tai rekursiivinen, menemme yli niin,

456
00:34:38,960 --> 00:34:46,139
mutta näemme, että rekursiivinen päätyy melko helppoa.

457
00:34:59,140 --> 00:35:02,480
Okei. Onko kellään jotain voimme työskennellä?

458
00:35:02,480 --> 00:35:12,000
>> [Opiskelija] Minulla iteratiivinen ratkaisu. >> Selvä, iteratiivinen.

459
00:35:12,000 --> 00:35:16,030
Okei, tämä näyttää hyvältä.

460
00:35:16,030 --> 00:35:18,920
Joten, haluatko kävellä meidän läpi?

461
00:35:18,920 --> 00:35:25,780
[Student] Toki. Niin otan temp muuttuja saada ensimmäinen solmu puun.

462
00:35:25,780 --> 00:35:28,330
Ja sitten minä vain viedä läpi vaikka lämpötila ei ole sama null,

463
00:35:28,330 --> 00:35:31,700
joten kun oli vielä puussa, luulisin.

464
00:35:31,700 --> 00:35:35,710
Ja jos arvo on yhtä suuri kuin arvo, joka lämpötila on osoittaa,

465
00:35:35,710 --> 00:35:37,640
niin se palauttaa tämän arvon.

466
00:35:37,640 --> 00:35:40,210
Muuten se tarkistaa, jos se on oikealla puolella tai vasemmalla puolella.

467
00:35:40,210 --> 00:35:43,400
Jos joskus saat tilanteeseen, jossa ei ole enää puu,

468
00:35:43,400 --> 00:35:47,330
Sitten se palaa - se poistuu silmukasta ja palauttaa false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okei. Niin että tuntuu hyvältä.

470
00:35:52,190 --> 00:35:58,470
Kellään mitään kommentteja mistään?

471
00:35:58,470 --> 00:36:02,400
Minulla ei ole oikeellisuudesta kommentteja ollenkaan.

472
00:36:02,400 --> 00:36:11,020
Ainoa mitä voimme tehdä, on tämä kaveri.

473
00:36:11,020 --> 00:36:21,660
Voi, se on menossa hieman pitkähkö.

474
00:36:21,660 --> 00:36:33,460
Minä korjata se ylös. Okei.

475
00:36:33,460 --> 00:36:37,150
>> Jokaisen pitäisi muistaa kuinka ternäärisen toimii.

476
00:36:37,150 --> 00:36:38,610
On varmasti ollut tietokilpailuja aikaisemmin

477
00:36:38,610 --> 00:36:41,170
jotka antavat sinulle funktio ternäärinen toimija,

478
00:36:41,170 --> 00:36:45,750
ja sanoa, kääntää tätä, tehdä jotain, joka ei käytä ternäärisen.

479
00:36:45,750 --> 00:36:49,140
Joten tämä on hyvin yleinen tapaus, luulisin käyttää tertiaarisia

480
00:36:49,140 --> 00:36:54,610
jos jos ehdosta asettaa muuttujan johonkin,

481
00:36:54,610 --> 00:36:58,580
muuten asettaa saman muuttujan jotain muuta.

482
00:36:58,580 --> 00:37:03,390
Se on jotain, että hyvin usein voidaan muuntaa tällainen asia

483
00:37:03,390 --> 00:37:14,420
jos asetettu, että muuttuja tähän - tai no, on tämä totta? Sitten tämä, muuten tämä.

484
00:37:14,420 --> 00:37:18,550
[Opiskelija] Ensimmäinen on, jos totta, eikö?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Joo. Tapa Luen aina se, temp vastaa arvo on suurempi kuin lämpötila-arvo,

486
00:37:25,570 --> 00:37:30,680
Sitten tämä, muuten tämä. Se kysyy kysymyksen.

487
00:37:30,680 --> 00:37:35,200
Onko se suurempi? Tee sitten ensimmäinen asia. Else tehdä toinen asia.

488
00:37:35,200 --> 00:37:41,670
Olen melkein aina - paksusuolen, juuri - päähäni, luin kuin muualla.

489
00:37:41,670 --> 00:37:47,180
>> Onko kellään rekursiivinen ratkaisu?

490
00:37:47,180 --> 00:37:49,670
Okei. Tämän me aiomme - se voisi olla jo hyvä,

491
00:37:49,670 --> 00:37:53,990
mutta me aiomme tehdä sen vielä paremmin.

492
00:37:53,990 --> 00:37:58,720
Tämä on melko täsmälleen sama ajatus.

493
00:37:58,720 --> 00:38:03,060
Se on vain, no, haluatko selittää?

494
00:38:03,060 --> 00:38:08,340
[Student] Toki. Joten me varmista, että puu ei ole null ensin,

495
00:38:08,340 --> 00:38:13,380
sillä jos puu on nolla niin se tulee palauttaa false, koska emme ole löytäneet sitä.

496
00:38:13,380 --> 00:38:19,200
Ja jos siellä on vielä puussa, menemme - ensin tarkistaa, jos arvo on nykyinen solmu.

497
00:38:19,200 --> 00:38:23,740
Return true jos on, ja jos ei me recurse vasemmalle tai oikealle.

498
00:38:23,740 --> 00:38:25,970
Kuulostaako sopiva? >> Mm-hmm. (Sopimus)

499
00:38:25,970 --> 00:38:33,880
Niin huomata, että tämä on lähes - rakenteellisesti hyvin samanlainen kuin iteratiivinen ratkaisu.

500
00:38:33,880 --> 00:38:38,200
Se on vain, että sen sijaan recursing, meillä oli taas silmukka.

501
00:38:38,200 --> 00:38:40,840
Ja pohja tässä tapauksessa, jossa puu ei ole yhtä null

502
00:38:40,840 --> 00:38:44,850
oli ehto, jonka me puhkesi kun silmukka.

503
00:38:44,850 --> 00:38:50,200
Ne ovat hyvin samankaltaisia. Mutta aiomme ottaa tämän askeleen pidemmälle.

504
00:38:50,200 --> 00:38:54,190
Nyt teemme saman täällä.

505
00:38:54,190 --> 00:38:57,680
Ilmoitus olemme palaamassa samaa molemmissa linjat,

506
00:38:57,680 --> 00:39:00,220
paitsi yksi argumentti on erilainen.

507
00:39:00,220 --> 00:39:07,950
Joten me aiomme tehdä, että tulee kolmen komponentin.

508
00:39:07,950 --> 00:39:13,790
Löin vaihtoehto jotain, ja se teki symboli. Okei.

509
00:39:13,790 --> 00:39:21,720
Joten aiomme palata sisältää se.

510
00:39:21,720 --> 00:39:28,030
Tämä alkaa olla useita rivejä, hyvin, zoomataan se on.

511
00:39:28,030 --> 00:39:31,060
Yleensä, kuten tyylillinen juttu, en usko moni

512
00:39:31,060 --> 00:39:38,640
laittaa välilyönti jälkeen nuoli, mutta luulen jos olet johdonmukainen, se on hienoa.

513
00:39:38,640 --> 00:39:44,320
Jos arvo on pienempi kuin puu arvo, haluamme recurse puiden vasemmalle,

514
00:39:44,320 --> 00:39:53,890
muuta haluamme recurse puiden oikeassa.

515
00:39:53,890 --> 00:39:58,610
Niin että oli vaihe yksi tehdä tämän näyttämään pienemmältä.

516
00:39:58,610 --> 00:40:02,660
Vaihe kaksi tehdä tämän näyttämään pienemmältä -

517
00:40:02,660 --> 00:40:09,150
voimme erottaa tämän useita rivejä.

518
00:40:09,150 --> 00:40:16,500
Okei. Vaihe kaksi tehdä se näyttää pienempi on täällä,

519
00:40:16,500 --> 00:40:25,860
joten paluu arvo vastaa puun arvo tai sisältää mitä tahansa.

520
00:40:25,860 --> 00:40:28,340
>> Tämä on tärkeä asia.

521
00:40:28,340 --> 00:40:30,860
En ole varma, onko hän sanoi nimenomaan luokassa,

522
00:40:30,860 --> 00:40:34,740
mutta sitä kutsutaan oikosulku arviointi.

523
00:40:34,740 --> 00:40:41,060
Ideana on arvo == puu arvoa.

524
00:40:41,060 --> 00:40:49,960
Jos tämä on totta, niin tämä on totta, ja me haluamme "tai" että mitä on täällä.

525
00:40:49,960 --> 00:40:52,520
Joten edes ajatellut mitä on täällä,

526
00:40:52,520 --> 00:40:55,070
Mikä on koko lauseke aio palata?

527
00:40:55,070 --> 00:40:59,430
[Student] True? >> Joo, koska totta mitään,

528
00:40:59,430 --> 00:41:04,990
or'd - tai totta or'd mitään on välttämättä totta.

529
00:41:04,990 --> 00:41:08,150
Niin pian näemme paluuarvo = puu-arvo,

530
00:41:08,150 --> 00:41:10,140
olemme juuri menossa return true.

531
00:41:10,140 --> 00:41:15,710
Ei edes aio recurse sisältää lisäksi ruodussa.

532
00:41:15,710 --> 00:41:20,980
Voimme ottaa tämän askeleen pidemmälle.

533
00:41:20,980 --> 00:41:29,490
Return puu ei vastaa nolla ja kaikki tämä.

534
00:41:29,490 --> 00:41:32,650
Se teki yhden rivin funktio.

535
00:41:32,650 --> 00:41:36,790
Tämä on myös esimerkki oikosulun arviointi.

536
00:41:36,790 --> 00:41:40,680
Mutta nyt se on sama ajatus -

537
00:41:40,680 --> 00:41:47,320
sijasta - joten jos puu ei ole yhtä null - tai no,

538
00:41:47,320 --> 00:41:49,580
Jos puu ei yhtä suuri kuin nolla, joka on huono asia,

539
00:41:49,580 --> 00:41:54,790
jos puu vastaa null, niin ensimmäinen edellytys tulee olemaan väärä.

540
00:41:54,790 --> 00:42:00,550
Niin vääriä anded mitään tulee olemaan mitä?

541
00:42:00,550 --> 00:42:04,640
[Student] False. >> Joo. Tämä on toinen puoli oikosulun arviointi,

542
00:42:04,640 --> 00:42:10,710
jos jos puu ei yhtä null, niin emme aio edes mennä -

543
00:42:10,710 --> 00:42:14,930
tai jos puu ei yhtä null, niin emme aio tehdä arvo == puun arvoa.

544
00:42:14,930 --> 00:42:17,010
Olemme juuri menossa heti palauttaa false.

545
00:42:17,010 --> 00:42:20,970
Mikä on tärkeää, koska jos se ei oikosulun arvioi,

546
00:42:20,970 --> 00:42:25,860
Sitten jos puu ei yhtä null, tämä toinen edellytys on menossa segmenteille vika,

547
00:42:25,860 --> 00:42:32,510
koska puu-> arvo dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Joten se siitä. Voi tehdä tätä - siirtää kerran yli.

549
00:42:40,490 --> 00:42:44,840
Tämä on hyvin yleistä myös, ei tee tätä linjaa tässä,

550
00:42:44,840 --> 00:42:49,000
mutta se on yhteinen asia olosuhteissa, ehkä ei täällä,

551
00:42:49,000 --> 00:42:59,380
mutta jos (puu! = NULL, ja puu-> arvo == arvo), tehdä mitä tahansa.

552
00:42:59,380 --> 00:43:01,560
Tämä on hyvin yleinen sairaus, jossa sen sijaan,

553
00:43:01,560 --> 00:43:06,770
murtaa kahteen jossittelua, missä haluan, on puu null?

554
00:43:06,770 --> 00:43:11,780
Okei, se ei ole nolla, joten nyt on puu-arvo arvoon? Tee tämä.

555
00:43:11,780 --> 00:43:17,300
Sen sijaan, tämä ehto, tämä ei koskaan segmentti vian

556
00:43:17,300 --> 00:43:21,220
koska se puhkeaa, jos tämä sattuu olemaan null.

557
00:43:21,220 --> 00:43:24,000
No, kai jos puu on täysin virheellinen osoittimen, se voi silti segmentti vika,

558
00:43:24,000 --> 00:43:26,620
mutta se ei voi seg vika jos puu on tyhjä.

559
00:43:26,620 --> 00:43:32,900
Jos se olisi null, se puhkeaa ennen kuin koskaan dereferenced osoitin ensimmäinen paikka.

560
00:43:32,900 --> 00:43:35,000
[Student] Onko tämä sanottu laiska arviointi?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy arviointi on erillinen asia.

562
00:43:40,770 --> 00:43:49,880
Laiska arviointi on enemmän kuin pyydät arvon,

563
00:43:49,880 --> 00:43:54,270
pyydät laskea arvoa, eräänlainen, mutta et tarvitse sitä heti.

564
00:43:54,270 --> 00:43:59,040
Joten kunnes todella tarvitset sitä, se ei ole arvioitu.

565
00:43:59,040 --> 00:44:03,920
Tämä ei ole aivan sama asia, mutta Huffman PSET,

566
00:44:03,920 --> 00:44:06,520
se sanoo, että me "laiskasti" kirjoittavat.

567
00:44:06,520 --> 00:44:08,670
Syy teemme joka johtuu olemme todella puskurointia kirjoitus -

568
00:44:08,670 --> 00:44:11,820
emme halua kirjoittaa yksittäisiä bittiä kerrallaan,

569
00:44:11,820 --> 00:44:15,450
tai yksittäisiä tavuja kerralla, me vaan haluamme saada palan tavua.

570
00:44:15,450 --> 00:44:19,270
Sitten kun meillä on kimpale tavua, niin me kirjoittaa sitä.

571
00:44:19,270 --> 00:44:22,640
Vaikka et pyydä sitä kirjoittaa - ja fwrite ja fread tehdä sama sellainen asia.

572
00:44:22,640 --> 00:44:26,260
He puskuri teidän lukee ja kirjoittaa.

573
00:44:26,260 --> 00:44:31,610
Vaikka et pyydä sitä kirjoittaa heti, se luultavasti ei.

574
00:44:31,610 --> 00:44:34,540
Ja voit olla varma, että asiat ovat menossa kirjoitetaan

575
00:44:34,540 --> 00:44:37,540
kunnes soitat hfclose tai mikä se on,

576
00:44:37,540 --> 00:44:39,620
joka sitten kertoo, okei, olen päätän tiedosto,

577
00:44:39,620 --> 00:44:43,450
se tarkoittaa, että olisin parempi kirjoittaa kaikkea en ole kirjoittanut vielä.

578
00:44:43,450 --> 00:44:45,770
Se ei tarvitse kirjoittaa kaiken pois

579
00:44:45,770 --> 00:44:49,010
kunnes olet lopettamista, ja sitten se tarvitsee.

580
00:44:49,010 --> 00:44:56,220
Joten tuon juuri laiska - se odottaa, kunnes se on tapahtua.

581
00:44:56,220 --> 00:44:59,990
Tämä - ottaa 51 ja voit mennä sen tarkemmin,

582
00:44:59,990 --> 00:45:05,470
koska OCaml ja kaiken 51, kaikki on rekursio.

583
00:45:05,470 --> 00:45:08,890
Ei ole iteratiivinen ratkaisuja, periaatteessa.

584
00:45:08,890 --> 00:45:11,550
Kaikki on rekursio, ja laiska arviointi

585
00:45:11,550 --> 00:45:14,790
tulee olemaan tärkeä paljon olosuhteiden

586
00:45:14,790 --> 00:45:19,920
missä, jos et laiskasti arvioi, että merkitsisi -

587
00:45:19,920 --> 00:45:24,760
Esimerkki on virtoja, jotka ovat äärettömän pitkä.

588
00:45:24,760 --> 00:45:30,990
Teoriassa voit ajatella luonnon numerot virta 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Joten laiskasti arvioitava asiat ovat kunnossa.

590
00:45:33,090 --> 00:45:37,210
Jos sanon haluan kymmenes numero, niin voin arvioida jopa kymmenes numero.

591
00:45:37,210 --> 00:45:40,300
Jos haluan sadas numero, niin voin arvioida jopa sadasosaan numero.

592
00:45:40,300 --> 00:45:46,290
Ilman laiska arviointi, niin se tulee yrittää arvioida kaikki numerot heti.

593
00:45:46,290 --> 00:45:50,000
Olet arvioidaan äärettömän monta lukua, ja se ei vain ole mahdollista.

594
00:45:50,000 --> 00:45:52,080
Joten on olemassa paljon tilanteita, joissa laiska arviointi

595
00:45:52,080 --> 00:45:57,840
On vain tärkeää saada asiat toimimaan.

596
00:45:57,840 --> 00:46:05,260
>> Nyt haluamme kirjoittaa insertti jossa insertti tulee olemaan

597
00:46:05,260 --> 00:46:08,430
Samoin muuttaa sen määritelmä.

598
00:46:08,430 --> 00:46:10,470
Joten nyt on bool insert (int arvo).

599
00:46:10,470 --> 00:46:23,850
Aiomme vaihtaa sen BOOL insert (int arvo, solmu * puu).

600
00:46:23,850 --> 00:46:29,120
Olemme itse asiassa menossa muuttaa sitä jälleen hieman, näemme miksi.

601
00:46:29,120 --> 00:46:32,210
Ja lähdetään build_node, vain pahus se,

602
00:46:32,210 --> 00:46:36,730
Edellä aseta joten meidän ei tarvitse kirjoittaa funktion prototyyppi.

603
00:46:36,730 --> 00:46:42,450
Joka on vihje, että aiot käyttää build_node vuonna insert.

604
00:46:42,450 --> 00:46:49,590
Okei. Ota minuutti siitä.

605
00:46:49,590 --> 00:46:52,130
Uskon tallentanut tarkistamista, jos haluat vetää siitä, että

606
00:46:52,130 --> 00:47:00,240
tai ainakin tein nyt.

607
00:47:00,240 --> 00:47:04,190
Halusin hieman taukoa ajatella logiikkaa insertin,

608
00:47:04,190 --> 00:47:08,750
jos et voi ajatella sitä.

609
00:47:08,750 --> 00:47:12,860
Periaatteessa, et vain koskaan lisäämällä klo lehtiä.

610
00:47:12,860 --> 00:47:18,640
Kuten, jos asetan 1, niin olen väistämättä olemaan laittamalla 1 -

611
00:47:18,640 --> 00:47:21,820
Muutan mustaksi - Minä oltava lisäämällä 1 täällä.

612
00:47:21,820 --> 00:47:28,070
Tai jos asetan 4, haluan olla työntämällä 4 tänne.

613
00:47:28,070 --> 00:47:32,180
Joten ei ole väliä mitä teet, olet menossa on työntämällä klo lehtiä.

614
00:47:32,180 --> 00:47:36,130
Kaikki mitä sinun tarvitsee tehdä on toistaa alas puusta kunnes saat solmuun

615
00:47:36,130 --> 00:47:40,890
että pitäisi olla solmun vanhemman uuden solmun vanhempi,

616
00:47:40,890 --> 00:47:44,560
ja sitten muuttaa sen vasemmalle tai oikealle osoitin, riippuen siitä, onko

617
00:47:44,560 --> 00:47:47,060
se on suurempi tai pienempi kuin nykyinen solmu.

618
00:47:47,060 --> 00:47:51,180
Vaihda että osoitin osoittamaan uuteen solmuun.

619
00:47:51,180 --> 00:48:05,490
Joten toistaa alas puusta, tee lehtiä pisteen uuteen solmuun.

620
00:48:05,490 --> 00:48:09,810
Myös miettiä, miksi se kieltää tällaiseen tilanteeseen ennen,

621
00:48:09,810 --> 00:48:17,990
jossa rakensin binääripuu, jossa se oli oikein

622
00:48:17,990 --> 00:48:19,920
jos vain katseli yksi solmu,

623
00:48:19,920 --> 00:48:24,830
mutta 9 oli vasemmalla 7 jos iteroida alas koko matkan.

624
00:48:24,830 --> 00:48:29,770
Niin, että on mahdotonta tässä tilanteessa, koska -

625
00:48:29,770 --> 00:48:32,530
ajattelevat asetat 9 tai jotain, aivan ensimmäinen solmu,

626
00:48:32,530 --> 00:48:35,350
Aion nähdä 7 ja olen juuri menossa oikealle.

627
00:48:35,350 --> 00:48:38,490
Joten ei ole väliä mitä teen, jos olen työntämällä menemällä lehti,

628
00:48:38,490 --> 00:48:40,790
ja lehtien käyttäen sopivaa algoritmia,

629
00:48:40,790 --> 00:48:43,130
se tulee olemaan minulle mahdotonta lisätä 9 vasemmalle 7

630
00:48:43,130 --> 00:48:48,250
sillä heti kun osuin 7 aion mennä oikealle.

631
00:48:59,740 --> 00:49:02,070
Onko kellään jotain aloittaa?

632
00:49:02,070 --> 00:49:05,480
[Opiskelija] teen. >> Toki.

633
00:49:05,480 --> 00:49:09,200
[Student, käsittämättömällä]

634
00:49:09,200 --> 00:49:14,390
[Other opiskelija, käsittämättömällä]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Se arvostaa. Okei. Haluatko selittää?

636
00:49:18,330 --> 00:49:20,690
>> [Student] Koska me tiedämme, että me asetat

637
00:49:20,690 --> 00:49:24,060
uusien solmujen lopussa puun

638
00:49:24,060 --> 00:49:28,070
Olen viedä läpi puun iteratiivisesti

639
00:49:28,070 --> 00:49:31,360
kunnes sain solmun, joka osoitti null.

640
00:49:31,360 --> 00:49:34,220
Ja sitten päätin laittaa sen joko oikealla tai vasemmalla puolella

641
00:49:34,220 --> 00:49:37,420
Käyttämällä tätä oikeutta muuttuja, se kertoi minulle, mihin sitä.

642
00:49:37,420 --> 00:49:41,850
Ja sitten, lähinnä olen juuri tehnyt, että viimeinen -

643
00:49:41,850 --> 00:49:47,520
että temp solmupiste uuteen solmu, että se oli luoda,

644
00:49:47,520 --> 00:49:50,770
joko vasemmalla puolella tai oikealle puolelle, riippuen siitä, mitä arvoa oikean oli.

645
00:49:50,770 --> 00:49:56,530
Lopuksi otan uuden solmun arvon arvoa sen testaus.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Okei, joten näen yksi kysymys.

647
00:49:59,550 --> 00:50:02,050
Tämä on kuin 95% matkalla sinne.

648
00:50:02,050 --> 00:50:07,550
Yksi asia, että näen hyvin, ei kukaan muu näe asiaa?

649
00:50:07,550 --> 00:50:18,400
Mikä on seikka, jonka mukaan ne murtautumaan ulos silmukan?

650
00:50:18,400 --> 00:50:22,100
[Student] Jos lämpötila on nolla? >> Joo. Joten miten eroon silmukka jos lämpötila on nolla.

651
00:50:22,100 --> 00:50:30,220
Mutta mitä teen täällä?

652
00:50:30,220 --> 00:50:35,410
Minä dereference lämpötila, joka on väistämättä null.

653
00:50:35,410 --> 00:50:39,840
Joten toinen asia mitä sinun tarvitsee tehdä ei ole vain seurata, kunnes lämpötila on nolla,

654
00:50:39,840 --> 00:50:45,590
haluat seurata vanhemman aina.

655
00:50:45,590 --> 00:50:52,190
Haluamme myös solmu * vanhempi, kai voimme pitää, että null aluksi.

656
00:50:52,190 --> 00:50:55,480
Tämä tulee olemaan outo käyttäytyminen puun juurelle,

657
00:50:55,480 --> 00:50:59,210
mutta saamme siihen.

658
00:50:59,210 --> 00:51:03,950
Jos arvo on suurempi kuin mitä, niin temp = temp oikeassa.

659
00:51:03,950 --> 00:51:07,910
Mutta ennen kuin teemme, että vanhempi = lämpötila.

660
00:51:07,910 --> 00:51:14,500
Vai vanhemmat aina menossa yhtä temp? Onko näin?

661
00:51:14,500 --> 00:51:19,560
Jos lämpötila ei ole nolla, niin aion liikkua alaspäin, ei väliä mitä,

662
00:51:19,560 --> 00:51:24,030
solmuun, jonka lämpötila on vanhempi.

663
00:51:24,030 --> 00:51:27,500
Joten vanhemman tulee olemaan temp, ja sitten siirtyä lämpötila alas.

664
00:51:27,500 --> 00:51:32,410
Nyt lämpötila on nolla, mutta vanhemman viittaa vanhemman asia on null.

665
00:51:32,410 --> 00:51:39,110
Joten täällä, en halua asettaa oikealle vastaa 1.

666
00:51:39,110 --> 00:51:41,300
Joten muutin oikealle, joten jos oikea = 1,

667
00:51:41,300 --> 00:51:45,130
ja kai myös haluavat tehdä -

668
00:51:45,130 --> 00:51:48,530
Jos liikut vasemmalle, jonka haluat asettaa oikealle 0..

669
00:51:48,530 --> 00:51:55,950
Tai muuten jos joskus siirtyä oikealle.

670
00:51:55,950 --> 00:51:58,590
Joten oikea = 0. Jos oikea = 1,

671
00:51:58,590 --> 00:52:04,260
Nyt haluamme tehdä vanhemman oikeus osoitin newnode,

672
00:52:04,260 --> 00:52:08,520
muuta haluamme tehdä vanhemman vasemmalle osoittimen newnode.

673
00:52:08,520 --> 00:52:16,850
Kysymyksiä tästä?

674
00:52:16,850 --> 00:52:24,880
Okei. Joten tämä on tapamme - no, oikeastaan, eikä näin,

675
00:52:24,880 --> 00:52:29,630
me puoli odotetaan voit käyttää build_node.

676
00:52:29,630 --> 00:52:40,450
Ja sitten jos newnode vastaa null, palauttaa false.

677
00:52:40,450 --> 00:52:44,170
Se siitä. Nyt, tämä on mitä odotimme sinua tekemään.

678
00:52:44,170 --> 00:52:47,690
>> Tämä on mitä henkilökunta ratkaisut tekevät.

679
00:52:47,690 --> 00:52:52,360
Olen eri mieltä kuin "oikea" tapa edetä siitä

680
00:52:52,360 --> 00:52:57,820
mutta tämä on täysin hieno, ja se toimii.

681
00:52:57,820 --> 00:53:02,840
Yksi asia, joka on hieman outoa nyt on

682
00:53:02,840 --> 00:53:08,310
jos puu alkaa kuin null, me kulkea null puuhun.

683
00:53:08,310 --> 00:53:12,650
Kai se riippuu siitä miten määrittelet käyttäytymistä ohimennen null puuhun.

684
00:53:12,650 --> 00:53:15,490
Luulisin, että jos pyörryt in null puu,

685
00:53:15,490 --> 00:53:17,520
sitten asettamalla arvon osaksi null puuhun

686
00:53:17,520 --> 00:53:23,030
pitäisi vain palauttaa puu, jossa ainoa arvo on se yksi solmu.

687
00:53:23,030 --> 00:53:25,830
Ihmiset samaa mieltä? Voisit, jos halusi,

688
00:53:25,830 --> 00:53:28,050
Jos ohitat in null puu

689
00:53:28,050 --> 00:53:31,320
ja haluat lisätä arvoa siihen, palauttaa false.

690
00:53:31,320 --> 00:53:33,830
Se on jopa voit määrittää, että.

691
00:53:33,830 --> 00:53:38,320
Voit tehdä ensimmäinen asia sanoin ja sitten -

692
00:53:38,320 --> 00:53:40,720
hyvin, olet menossa on vaikeuksia tehdä niin, koska

693
00:53:40,720 --> 00:53:44,090
Olisi helpompaa, jos meillä olisi maailmanlaajuinen osoitin asia,

694
00:53:44,090 --> 00:53:48,570
mutta emme, joten jos puu on tyhjä, ei ole mitään emme voi tehdä asialle.

695
00:53:48,570 --> 00:53:50,960
Voimme vain palauttaa false.

696
00:53:50,960 --> 00:53:52,840
Joten aion vaihtaa insertin.

697
00:53:52,840 --> 00:53:56,540
Olemme teknisesti voisi juuri muuttaa tätä täällä,

698
00:53:56,540 --> 00:53:58,400
miten se iteroimalla läpi asioita,

699
00:53:58,400 --> 00:54:04,530
mutta aion vaihtaa insertin ottaa solmuun ** puu.

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

701
00:54:07,510 --> 00:54:09,710
Mitä tämä tarkoittaa?

702
00:54:09,710 --> 00:54:12,330
Sen sijaan käsitellä osoittimia solmuja,

703
00:54:12,330 --> 00:54:16,690
asia aion olla manipuloimalla tämä osoitin.

704
00:54:16,690 --> 00:54:18,790
Aion olla manipuloida tätä osoitinta.

705
00:54:18,790 --> 00:54:21,770
Aion olla manipuloimalla osoittimia suoraan.

706
00:54:21,770 --> 00:54:25,760
Tämä on järkevää, koska ajattelevat alas -

707
00:54:25,760 --> 00:54:33,340
No, nyt tämä viittaa null.

708
00:54:33,340 --> 00:54:38,130
Mitä haluan tehdä on manipuloida tämä osoitin osoittamaan ole null.

709
00:54:38,130 --> 00:54:40,970
Haluan sen osoittamaan minun uusi solmu.

710
00:54:40,970 --> 00:54:44,870
Jos minä vain seurata osoittimia minun osoittimia,

711
00:54:44,870 --> 00:54:47,840
niin minun ei tarvitse seurata vanhemman osoittimen.

712
00:54:47,840 --> 00:54:52,640
Voin vain seurata, onko osoitin osoittaa null,

713
00:54:52,640 --> 00:54:54,580
ja jos osoitin osoittaa null,

714
00:54:54,580 --> 00:54:57,370
vaihda se osoittamaan solmuun haluan.

715
00:54:57,370 --> 00:55:00,070
Ja voin vaihtaa sen koska minulla on osoittimen osoitin.

716
00:55:00,070 --> 00:55:02,040
Katsotaanpa tätä nyt.

717
00:55:02,040 --> 00:55:05,470
Voit itse tehdä sen rekursiivisesti melko helposti.

718
00:55:05,470 --> 00:55:08,080
Haluammeko tehdä niin?

719
00:55:08,080 --> 00:55:10,980
Kyllä, me teemme.

720
00:55:10,980 --> 00:55:16,790
>> Katsotaanpa sitä rekursiivisesti.

721
00:55:16,790 --> 00:55:24,070
Ensinnäkin, mitä meidän tukikohta tapauksessa olemaan?

722
00:55:24,070 --> 00:55:29,140
Lähes aina meidän tukikohta tapauksessa, mutta todellisuudessa tämä on tavallaan hankala.

723
00:55:29,140 --> 00:55:34,370
First things first, jos (puu == NULL)

724
00:55:34,370 --> 00:55:37,550
Taidamme juuri menossa palauttaa false.

725
00:55:37,550 --> 00:55:40,460
Tämä poikkeaa teidän puu on null.

726
00:55:40,460 --> 00:55:44,510
Tämä on osoitin pääkäyttäjän osoittimen ollessa null

727
00:55:44,510 --> 00:55:48,360
mikä tarkoittaa, että root osoitin ei ole olemassa.

728
00:55:48,360 --> 00:55:52,390
Joten täällä, jos en

729
00:55:52,390 --> 00:55:55,760
solmu * - Haluan vain käyttämään tätä.

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

731
00:55:58,960 --> 00:56:00,730
ja sitten aion soittaa insertin tekemällä jotain,

732
00:56:00,730 --> 00:56:04,540
aseta 4 osaksi & root.

733
00:56:04,540 --> 00:56:06,560
Niin & root, jos root on solmu *

734
00:56:06,560 --> 00:56:11,170
Sitten & root tulee olemaan solmu **.

735
00:56:11,170 --> 00:56:15,120
Tämä on voimassa. Tällöin puun, täällä,

736
00:56:15,120 --> 00:56:20,120
puu ei ole tyhjä - tai insert.

737
00:56:20,120 --> 00:56:24,630
Täällä. Puu ei ole nolla, * puu on nolla, mikä on hieno

738
00:56:24,630 --> 00:56:26,680
koska jos * puu on tyhjä, niin voin manipuloida sitä

739
00:56:26,680 --> 00:56:29,210
nyt osoittamaan, mitä haluan sen osoittamaan.

740
00:56:29,210 --> 00:56:34,750
Mutta jos puu on tyhjä, se tarkoittaa, että olen vain tuli tänne ja sanoi null.

741
00:56:34,750 --> 00:56:42,710
Tämä ei ole mitään järkeä. En voi tehdä mitään sen kanssa.

742
00:56:42,710 --> 00:56:45,540
Jos puu on tyhjä, palauttaa false.

743
00:56:45,540 --> 00:56:48,220
Joten olen periaatteessa jo sanonut, mitä todellinen pohja tapaus.

744
00:56:48,220 --> 00:56:50,580
Ja mitä on se tulee?

745
00:56:50,580 --> 00:56:55,030
[Student, käsittämättömällä]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Kyllä. Joten jos (* puu == NULL).

747
00:57:00,000 --> 00:57:04,520
Tämä koskee tapausta tänne

748
00:57:04,520 --> 00:57:09,640
jos jos minun punainen osoitin on osoitin olen keskittynyt,

749
00:57:09,640 --> 00:57:12,960
niin kuin olen keskittynyt tähän osoitin, nyt olen keskittynyt tähän osoitin.

750
00:57:12,960 --> 00:57:15,150
Nyt olen keskittynyt tähän osoitin.

751
00:57:15,150 --> 00:57:18,160
Joten jos minun punainen osoitin, joka on minun solmu **

752
00:57:18,160 --> 00:57:22,880
on aina - jos *, minun punainen osoitin, on aina nolla,

753
00:57:22,880 --> 00:57:28,470
se tarkoittaa, että olen silloin olen keskittynyt osoitin, joka osoittaa -

754
00:57:28,470 --> 00:57:32,530
tämä on osoitin, joka kuuluu lehtiä.

755
00:57:32,530 --> 00:57:41,090
Haluan muuttaa tätä osoitin osoittamaan minun uusi solmu.

756
00:57:41,090 --> 00:57:45,230
Tule takaisin tänne.

757
00:57:45,230 --> 00:57:56,490
Minun newnode vain on solmu * n = build_node (arvo)

758
00:57:56,490 --> 00:58:07,300
sitten n, jos n = NULL, palaa vääriä.

759
00:58:07,300 --> 00:58:12,600
Else haluamme muuttaa mitä osoitin on tällä hetkellä osoittaa

760
00:58:12,600 --> 00:58:17,830
nyt osoittamaan hiljattain rakennettu solmu.

761
00:58:17,830 --> 00:58:20,280
Voimme todella tehdä sen täällä.

762
00:58:20,280 --> 00:58:30,660
Sijaan sanoa n, sanomme * puu = jos * puu.

763
00:58:30,660 --> 00:58:35,450
Jokainen ymmärtää, että? Että käsittelemällä viitteitä osoittimia,

764
00:58:35,450 --> 00:58:40,750
voimme muuttaa null osoittimet osoittamaan asioita haluamme ne osoittamaan.

765
00:58:40,750 --> 00:58:42,820
Se on meidän perustapaus.

766
00:58:42,820 --> 00:58:45,740
>> Nyt meidän toistumisen tai meidän rekursio,

767
00:58:45,740 --> 00:58:51,430
tulee olemaan hyvin samanlainen kaikille muille rekursioiden olemme tehneet.

768
00:58:51,430 --> 00:58:55,830
Aiomme haluat lisätä arvoa,

769
00:58:55,830 --> 00:58:59,040
ja nyt aion käyttää ternäärinen uudestaan, mutta mitä tilaamme olemaan?

770
00:58:59,040 --> 00:59:05,180
Mitä me etsimme päättää haluamme mennä vasemmalle tai oikealle?

771
00:59:05,180 --> 00:59:07,760
Tehdään se erillisissä vaiheissa.

772
00:59:07,760 --> 00:59:18,850
Jos (arvo <) mitä?

773
00:59:18,850 --> 00:59:23,200
[Opiskelija] puun arvo?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Muista siis, että olen tällä hetkellä -

775
00:59:27,490 --> 00:59:31,260
[Opiskelijat, käsittämättömällä]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Joo, niin täällä sanotaan, että tämä vihreä nuoli

777
00:59:34,140 --> 00:59:39,050
on esimerkki siitä, mitä puu tällä hetkellä on, on osoitin tämän osoitin.

778
00:59:39,050 --> 00:59:46,610
Niin se tarkoittaa, että olen osoittimen osoittimen 3.

779
00:59:46,610 --> 00:59:48,800
Dereference kahdesti kuulosti hyvältä.

780
00:59:48,800 --> 00:59:51,010
Mitä teen - miten voin tehdä sen?

781
00:59:51,010 --> 00:59:53,210
[Student] dereference kerran, ja tee sitten nuolta niin?

782
00:59:53,210 --> 00:59:58,420
[Bowden] So (* puu) on dereference kerran -> arvo

783
00:59:58,420 --> 01:00:05,960
aikoo antaa minulle arvoa solmun että olen epäsuorasti osoittaa.

784
01:00:05,960 --> 01:00:11,980
Joten voin myös kirjoittaa sen ** tree.value jos haluat, että.

785
01:00:11,980 --> 01:00:18,490
Joko toimii.

786
01:00:18,490 --> 01:00:26,190
Jos näin on, niin haluan soittaa lisätä arvolla.

787
01:00:26,190 --> 01:00:32,590
Ja mitä minun päivitetään solmu ** olemaan?

788
01:00:32,590 --> 01:00:39,440
Haluan mennä vasemmalle, joten ** tree.left tulee olemaan minun vasemmalle.

789
01:00:39,440 --> 01:00:41,900
Ja haluan osoitinta että asia

790
01:00:41,900 --> 01:00:44,930
niin että jos vasemmalla päätyy on nollaosoittimen,

791
01:00:44,930 --> 01:00:48,360
Voin muuttaa sen osoittamaan minun uusi solmu.

792
01:00:48,360 --> 01:00:51,460
>> Ja toisessa tapauksessa voi olla hyvin samanlainen.

793
01:00:51,460 --> 01:00:55,600
Tehdään itse tehdä, että minun ternäärisen nyt.

794
01:00:55,600 --> 01:01:04,480
Aseta arvo, jos arvo <(** puu). Arvo.

795
01:01:04,480 --> 01:01:11,040
Sitten haluamme päivittää ** vasemmalle,

796
01:01:11,040 --> 01:01:17,030
muuta haluamme päivittää ** oikealle.

797
01:01:17,030 --> 01:01:22,540
[Opiskelija] Onko jotka saavat osoitin osoitin?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Muista, että - ** tree.right on solmu tähti.

799
01:01:30,940 --> 01:01:35,040
[Student, käsittämätön] >> Joo.

800
01:01:35,040 --> 01:01:41,140
** Tree.right on näin osoitin tai jotain.

801
01:01:41,140 --> 01:01:45,140
Joten ottamalla osoitin, että se antaa minulle mitä haluan

802
01:01:45,140 --> 01:01:50,090
ja osoitin että kaveri.

803
01:01:50,090 --> 01:01:54,260
[Student] Voisimmeko mennä uudestaan ​​miksi käytämme kaksi osoitinta?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Joo. Joten - no, voit, ja että ratkaisu ennen

805
01:01:58,220 --> 01:02:04,540
oli tapa tehdä se tekemättä kaksi osoitinta.

806
01:02:04,540 --> 01:02:08,740
Sinun täytyy pystyä ymmärtämään kahdella osoittimia,

807
01:02:08,740 --> 01:02:11,660
ja tämä on puhtaampaa ratkaisu.

808
01:02:11,660 --> 01:02:16,090
Huomaa myös, että mitä tapahtuu jos puu -

809
01:02:16,090 --> 01:02:24,480
Mitä tapahtuu, jos root oli null? Mitä tapahtuu, jos en tee tässä tapauksessa täällä?

810
01:02:24,480 --> 01:02:30,540
Joten solmu * root = NULL, aseta 4 osaksi & root.

811
01:02:30,540 --> 01:02:35,110
Mikä on root olemaan tämän jälkeen?

812
01:02:35,110 --> 01:02:37,470
[Student, käsittämätön] >> Joo.

813
01:02:37,470 --> 01:02:41,710
Root-arvo tulee olemaan 4.

814
01:02:41,710 --> 01:02:45,510
Root vasemmalle tulee olemaan null, root oikeus tulee olemaan null.

815
01:02:45,510 --> 01:02:49,490
Siinä tapauksessa emme ohittaa root osoitteen,

816
01:02:49,490 --> 01:02:52,490
emme voi muuttaa root.

817
01:02:52,490 --> 01:02:56,020
Tapauksessa, jossa puun - missä root oli null,

818
01:02:56,020 --> 01:02:58,410
meillä oli vain palauttaa false. Ei ole mitään mitä voisimme tehdä.

819
01:02:58,410 --> 01:03:01,520
Emme voi lisätä solmun tyhjään puuhun.

820
01:03:01,520 --> 01:03:06,810
Mutta nyt voimme, voimme vain tehdä tyhjä puu tulee yhden solmun Tree.

821
01:03:06,810 --> 01:03:13,400
Joka on yleensä odotetulla tavalla, että sen pitäisi toimia.

822
01:03:13,400 --> 01:03:21,610
>> Lisäksi tämä on huomattavasti lyhyempi kuin

823
01:03:21,610 --> 01:03:26,240
myös pitää kirjaa vanhemman, ja niin te iteroida alas koko matkan.

824
01:03:26,240 --> 01:03:30,140
Nyt minulla on vanhempieni, ja minulla on vain minun vanhemman oikeus osoitin tahansa.

825
01:03:30,140 --> 01:03:35,640
Sen sijaan, jos teimme tämän iteratiivisesti, se olisi sama idea kun silmukka.

826
01:03:35,640 --> 01:03:38,100
Mutta sen sijaan, käsitellä vanhempieni osoitin,

827
01:03:38,100 --> 01:03:40,600
vaan minun nykyinen osoitin olisi asia

828
01:03:40,600 --> 01:03:43,790
että olen suoraan muuttaa osoittamaan minun uusi solmu.

829
01:03:43,790 --> 01:03:46,090
Minulla ei ole käsitellä onko se osoittaa vasemmalle.

830
01:03:46,090 --> 01:03:48,810
Minulla ei ole käsitellä onko se osoittaa oikealle.

831
01:03:48,810 --> 01:04:00,860
Se on vain mitä tämä osoitin on, aion asettaa sen osoittamaan minun uusi solmu.

832
01:04:00,860 --> 01:04:05,740
Jokainen ymmärtää, miten se toimii?

833
01:04:05,740 --> 01:04:09,460
Jos ei, miksi haluamme tehdä näin,

834
01:04:09,460 --> 01:04:14,920
mutta ainakin tämä toimii ratkaisu?

835
01:04:14,920 --> 01:04:17,110
[Student] Mistä me palata totta?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Se on luultavasti täällä.

837
01:04:21,550 --> 01:04:26,690
Jos me oikein aseta se, return true.

838
01:04:26,690 --> 01:04:32,010
Else, tänne menemme halua palata mitä insertin tuottoa.

839
01:04:32,010 --> 01:04:35,950
>> Ja mitä erikoista tässä rekursiivinen funktio?

840
01:04:35,950 --> 01:04:43,010
Se hännän rekursiivinen, niin kauan kuin me koota joidenkin optimointi,

841
01:04:43,010 --> 01:04:48,060
se tunnistaa, että ja et koskaan saa pinon ylivuoto tästä,

842
01:04:48,060 --> 01:04:53,230
vaikka meidän puu korkeus on 10000 tai 10000000.

843
01:04:53,230 --> 01:04:55,630
[Student, käsittämättömällä]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Minusta se sitä Dash - tai mitä optimointi tasolla

845
01:05:00,310 --> 01:05:03,820
tarvitaan hännän rekursion on tunnustettava.

846
01:05:03,820 --> 01:05:09,350
Mielestäni tunnustetaan - GCC ja clang

847
01:05:09,350 --> 01:05:12,610
myös erilaisia ​​merkityksiä niiden optimointi tasoille.

848
01:05:12,610 --> 01:05:17,870
Haluan sanoa se DashO 2, että se tunnistaa häntä rekursio.

849
01:05:17,870 --> 01:05:27,880
Mutta me - voit rakentaa kuin Fibonocci esimerkiksi tai jotain.

850
01:05:27,880 --> 01:05:30,030
Se ei ole helppo testata tätä, koska se on vaikea rakentaa

851
01:05:30,030 --> 01:05:32,600
binääripuu, joka on niin suuri.

852
01:05:32,600 --> 01:05:37,140
Mutta joo, mielestäni se on DashO 2, että

853
01:05:37,140 --> 01:05:40,580
Jos käännät kanssa DashO 2, se etsii häntä rekursio

854
01:05:40,580 --> 01:05:54,030
ja optimoida se ulos.

855
01:05:54,030 --> 01:05:58,190
Mennään takaisin - lisätä kirjaimellisesti viimeinen asia se tarvitsee.

856
01:05:58,190 --> 01:06:04,900
Mennään takaisin insertin tänne

857
01:06:04,900 --> 01:06:07,840
minne olemme menossa tekemään saman ajatuksen.

858
01:06:07,840 --> 01:06:14,340
Se tulee vielä puute, ettei se pysty täysin käsittelemään

859
01:06:14,340 --> 01:06:17,940
kun juuri itse on nolla, tai viimeisen merkinnän on nolla,

860
01:06:17,940 --> 01:06:20,060
mutta sen sijaan käsitellä vanhemman osoitin,

861
01:06:20,060 --> 01:06:27,430
Katsotaanpa soveltaa samaa logiikkaa pitää osoittimia osoittimia.

862
01:06:27,430 --> 01:06:35,580
Jos täällä pidämme solmu ** nyk.,

863
01:06:35,580 --> 01:06:37,860
ja meidän ei tarvitse seurata oikean enää,

864
01:06:37,860 --> 01:06:47,190
mutta solmu ** nyk. = & puu.

865
01:06:47,190 --> 01:06:54,800
Ja nyt meidän while-silmukka tulee olemaan taas * nyk. ei ole sama null.

866
01:06:54,800 --> 01:07:00,270
Ei tarvitse seurata vanhempien enää.

867
01:07:00,270 --> 01:07:04,180
Ei tarvitse seurata vasemmalle ja oikealle.

868
01:07:04,180 --> 01:07:10,190
Ja minä kutsun sitä temp, koska olemme jo käytössä temp.

869
01:07:10,190 --> 01:07:17,200
Okei. Joten jos (arvo> * temp),

870
01:07:17,200 --> 01:07:24,010
Sitten & (* temp) -> oikea

871
01:07:24,010 --> 01:07:29,250
muu temp = & (* temp) -> vasemmalle.

872
01:07:29,250 --> 01:07:32,730
Ja nyt, tässä vaiheessa, tämän jälkeen, kun silmukka,

873
01:07:32,730 --> 01:07:36,380
Olen vain tehdä tämän, koska ehkä se on helpompi ajatella iteratiivisesti kuin rekursiivisesti,

874
01:07:36,380 --> 01:07:39,010
mutta tämän jälkeen kun silmukka,

875
01:07:39,010 --> 01:07:43,820
* Temp on osoitin haluamme muuttaa.

876
01:07:43,820 --> 01:07:48,960
>> Ennen meillä oli vanhempi, ja halusimme muuttaa joko vanhemman vasemmalle tai vanhempi oikealle,

877
01:07:48,960 --> 01:07:51,310
mutta jos haluamme muuttaa vanhemman oikealle,

878
01:07:51,310 --> 01:07:54,550
sitten * temp on vanhempi oikeassa, ja voimme muuttaa sen suoraan.

879
01:07:54,550 --> 01:08:05,860
Joten täällä, voimme tehdä * temp = newnode, ja se on siinä.

880
01:08:05,860 --> 01:08:09,540
Joten ilmoitus, kaikki teimme tällä oli ottaa pois riviä koodia.

881
01:08:09,540 --> 01:08:14,770
Jotta seurata vanhemman kaikessa on ylimääräistä vaivaa.

882
01:08:14,770 --> 01:08:18,689
Täällä, jos me vain seurata osoitin osoitin,

883
01:08:18,689 --> 01:08:22,990
ja vaikka halusimme päästä eroon kaikista näistä aaltosulkeita nyt,

884
01:08:22,990 --> 01:08:27,170
jotta se näyttää lyhyempi.

885
01:08:27,170 --> 01:08:32,529
Tämä on nyt täsmälleen sama ratkaisu,

886
01:08:32,529 --> 01:08:38,210
mutta vähemmän riviä koodia.

887
01:08:38,210 --> 01:08:41,229
Kun aloitat tunnustaa tätä pätevä ratkaisu,

888
01:08:41,229 --> 01:08:43,529
se on myös helpompi syynä noin kuin esimerkiksi, okei,

889
01:08:43,529 --> 01:08:45,779
miksi minulla on tämä lippu int oikeassa?

890
01:08:45,779 --> 01:08:49,290
Mitä se tarkoittaa? Voi, se on osoituksena, että

891
01:08:49,290 --> 01:08:51,370
aina kun menen oikealle, minun täytyy asettaa se,

892
01:08:51,370 --> 01:08:53,819
if menen vasemmalle minun täytyy asettaa sen nollaan.

893
01:08:53,819 --> 01:09:04,060
Täällä minun ei tarvitse syytä siitä, se on vain helpompi ajatella.

894
01:09:04,060 --> 01:09:06,710
Kysymyksiä?

895
01:09:06,710 --> 01:09:16,290
[Student, käsittämätön] >> Joo.

896
01:09:16,290 --> 01:09:23,359
Okei, joten viimeinen bitti -

897
01:09:23,359 --> 01:09:28,080
Luulen yksi nopea ja helppo toiminto voimme tehdä on,

898
01:09:28,080 --> 01:09:34,910
let's - yhdessä, luulisin, yrittää kirjoittaa sisältää funktion

899
01:09:34,910 --> 01:09:38,899
joka ei välitä onko se binäärihakupuu.

900
01:09:38,899 --> 01:09:43,770
Tämä sisältää funktion pitäisi palauttaa true

901
01:09:43,770 --> 01:09:58,330
Jos missä tahansa tämän yleisen binääripuussa on arvo etsimme.

902
01:09:58,330 --> 01:10:02,520
Joten ensin tehdä se rekursiivisesti ja sitten teemme sen iteratiivisesti.

903
01:10:02,520 --> 01:10:07,300
Voimme oikeastaan ​​vain tehdä se yhdessä, sillä tämä tulee olemaan todella lyhyt.

904
01:10:07,300 --> 01:10:11,510
>> Mitä minun perustapaus aiotaan?

905
01:10:11,510 --> 01:10:13,890
[Student, käsittämättömällä]

906
01:10:13,890 --> 01:10:18,230
[Bowden] So if (puu == NULL), mitä sitten?

907
01:10:18,230 --> 01:10:22,740
[Student] palauttaa false.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, hyvin, en tarvitse muuta.

909
01:10:26,160 --> 01:10:30,250
Jos oli minun toinen perustapaus.

910
01:10:30,250 --> 01:10:32,450
[Opiskelijan] Tree arvoa? >> Joo.

911
01:10:32,450 --> 01:10:36,430
Joten jos (puu-> arvo == arvo.

912
01:10:36,430 --> 01:10:39,920
Ilmoitus olemme takaisin solmuun *, ei solmu ** t?

913
01:10:39,920 --> 01:10:42,990
Sisältää koskaan tarvitse käyttää solmuun **

914
01:10:42,990 --> 01:10:45,480
koska emme muuttaa osoittimia.

915
01:10:45,480 --> 01:10:50,540
Olemme vain liikkumisesta niitä.

916
01:10:50,540 --> 01:10:53,830
Jos näin tapahtuu, niin me haluamme palata totta.

917
01:10:53,830 --> 01:10:58,270
Else haluamme kulkea lapsille.

918
01:10:58,270 --> 01:11:02,620
Joten emme voi järkeillä siitä kaiken vasemmalla on vähemmän

919
01:11:02,620 --> 01:11:05,390
ja kaiken oikealla on suurempi.

920
01:11:05,390 --> 01:11:09,590
Joten mitä tilaamme olemaan täällä - tai, mitä aiomme tehdä?

921
01:11:09,590 --> 01:11:11,840
[Student, käsittämätön] >> Joo.

922
01:11:11,840 --> 01:11:17,400
Return sisältää (arvo, puu-> vasen)

923
01:11:17,400 --> 01:11:26,860
tai sisältää (arvo, puu-> oikea). Ja siinä se.

924
01:11:26,860 --> 01:11:29,080
Ja huomaa jonkin verran oikosulku arviointi,

925
01:11:29,080 --> 01:11:32,520
jos jos huomaamme arvo vasen puu,

926
01:11:32,520 --> 01:11:36,820
Meidän ei tarvitse katsoa oikean puun.

927
01:11:36,820 --> 01:11:40,430
Tuo koko funktio.

928
01:11:40,430 --> 01:11:43,690
Nyt tehdään se iteratiivisesti,

929
01:11:43,690 --> 01:11:48,060
joka tulee olemaan vähemmän mukavaa.

930
01:11:48,060 --> 01:11:54,750
Otamme tavallista alkua solmun * nyk. = puu.

931
01:11:54,750 --> 01:12:03,250
Vaikka (nyk.! = NULL).

932
01:12:03,250 --> 01:12:08,600
Nopeasti näkemään ongelman.

933
01:12:08,600 --> 01:12:12,250
Jos nyk. - täällä, jos me koskaan eroon tästä,

934
01:12:12,250 --> 01:12:16,020
Sitten olemme lopu asioita katsomaan, niin palauta väärä.

935
01:12:16,020 --> 01:12:24,810
Jos (nyk.-> arvo == arvo), return true.

936
01:12:24,810 --> 01:12:32,910
Joten nyt olemme paikassa -

937
01:12:32,910 --> 01:12:36,250
emme tiedä onko meillä halua mennä vasemmalle tai oikealle.

938
01:12:36,250 --> 01:12:44,590
Joten mielivaltaisesti, mennään vain vasemmalle.

939
01:12:44,590 --> 01:12:47,910
Olen ilmeisesti joutunut ongelman, jossa olen täysin luopunut kaikesta -

940
01:12:47,910 --> 01:12:50,760
Olen aina vain tarkistaa vasemmalle puolelle puun.

941
01:12:50,760 --> 01:12:56,050
En koskaan tarkista mitään, että on oikea lapsi mitään.

942
01:12:56,050 --> 01:13:00,910
Miten korjaan tämän?

943
01:13:00,910 --> 01:13:05,260
[Student] Sinun pitää kirjaa vasemmalle ja oikealle pinoon.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Joo. Joten tehkäämme se

945
01:13:13,710 --> 01:13:32,360
struct lista, solmu * n, ja sitten solmu ** seuraavaksi?

946
01:13:32,360 --> 01:13:40,240
Mielestäni toimii hyvin.

947
01:13:40,240 --> 01:13:45,940
Haluamme mennä yli vasemmalle tai let's - täällä.

948
01:13:45,940 --> 01:13:54,350
Struct lista lista =, se tulee aloittaa

949
01:13:54,350 --> 01:13:58,170
pois tässä struct lista.

950
01:13:58,170 --> 01:14:04,040
* Lista = NULL. Niin, että tulee olemaan meidän linkitetty lista

951
01:14:04,040 --> 01:14:08,430
ja alipuut että olemme ohitetaan.

952
01:14:08,430 --> 01:14:13,800
Aiomme Traverse vasemmalle nyt,

953
01:14:13,800 --> 01:14:17,870
mutta koska me väistämättä täytyy palata oikealle,

954
01:14:17,870 --> 01:14:26,140
Aiomme pitää oikealla puolella sisällä meidän struct lista.

955
01:14:26,140 --> 01:14:32,620
Sitten meillä on new_list tai struct,

956
01:14:32,620 --> 01:14:41,080
struct lista *, new_list = malloc (sizeof (lista)).

957
01:14:41,080 --> 01:14:44,920
Aion jättää virheiden tarkkailun, mutta sinun pitäisi tarkistaa, onko se null.

958
01:14:44,920 --> 01:14:50,540
New_list solmu se tulee osoittamaan -

959
01:14:50,540 --> 01:14:56,890
oh, siksi halusin sen tänne. Se tulee osoittamaan toiseen struct lista.

960
01:14:56,890 --> 01:15:02,380
Se, miten linkitettyjä listoja työtä.

961
01:15:02,380 --> 01:15:04,810
Tämä on sama kuin int linkitetty lista

962
01:15:04,810 --> 01:15:06,960
paitsi me vain korvaa int solmuun *.

963
01:15:06,960 --> 01:15:11,040
Se on täsmälleen sama.

964
01:15:11,040 --> 01:15:15,100
Niin new_list, arvoa meidän new_list solmun,

965
01:15:15,100 --> 01:15:19,120
tulee olemaan nyk.-> oikeassa.

966
01:15:19,120 --> 01:15:24,280
Arvo meidän new_list-> seuraava tulee olemaan meidän alkuperäisessä luettelossa,

967
01:15:24,280 --> 01:15:30,760
ja sitten me aiomme päivittää luetteloa osoittamaan new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nyt tarvitaan jonkinlainen tapa vetää asioita,

969
01:15:33,650 --> 01:15:37,020
kuten olemme kulkeneet koko vasemman alipuun.

970
01:15:37,020 --> 01:15:40,480
Nyt meidän täytyy vetää tavaraa pois,

971
01:15:40,480 --> 01:15:43,850
kuten nyk. on nolla, emme halua vain palauttaa false.

972
01:15:43,850 --> 01:15:50,370
Haluamme nyt vetää ulkopuolella meidän uusi luettelo.

973
01:15:50,370 --> 01:15:53,690
Kätevä tapa tehdä tämä - hyvin, oikeastaan, siellä on useita tapoja tehdä tämä.

974
01:15:53,690 --> 01:15:56,680
Kellään ehdotuksia?

975
01:15:56,680 --> 01:15:58,790
Minne minun pitäisi tehdä tämän tai miten minun pitäisi tehdä tämän?

976
01:15:58,790 --> 01:16:08,010
Meillä on vain pari minuuttia, mutta mitään ehdotuksia?

977
01:16:08,010 --> 01:16:14,750
Sen sijaan - yksi tapa, eikä meidän edellytys on samalla,

978
01:16:14,750 --> 01:16:17,090
mitä me nyt katsot ei ole nolla,

979
01:16:17,090 --> 01:16:22,340
sijaan aiomme edelleen mennä kunnes meidän luetteloa on null.

980
01:16:22,340 --> 01:16:25,680
Joten jos lista päätyy null,

981
01:16:25,680 --> 01:16:30,680
Sitten olemme lopu asioita etsiä, etsiä yli.

982
01:16:30,680 --> 01:16:39,860
Mutta se tarkoittaa sitä, että ensimmäinen asia listallamme on juuri menossa olla ensimmäinen solmu.

983
01:16:39,860 --> 01:16:49,730
Aivan ensimmäinen asia on - meidän ei enää tarvitse nähdä sitä.

984
01:16:49,730 --> 01:16:58,710
Joten lista-> n tulee meidän puu.

985
01:16:58,710 --> 01:17:02,860
lista-> seuraava tulee olemaan null.

986
01:17:02,860 --> 01:17:07,580
Ja nyt, kun lista ei ole yhtä null.

987
01:17:07,580 --> 01:17:11,610
Nyk. aikoo vetää jotain listalta.

988
01:17:11,610 --> 01:17:13,500
Joten nyk. tulee yhtä lista-> n.

989
01:17:13,500 --> 01:17:20,850
Ja sitten lista on menossa yhtä lista-> n, tai luettelo-> Seuraava.

990
01:17:20,850 --> 01:17:23,480
Joten jos nyk. arvo on arvo.

991
01:17:23,480 --> 01:17:28,790
Nyt voimme lisätä sekä meidän oikeutemme osoitin ja meidän vasemmalle osoittimen

992
01:17:28,790 --> 01:17:32,900
niin kauan kuin he eivät null.

993
01:17:32,900 --> 01:17:36,390
Täällä, kai meidän olisi pitänyt tehdä, että ensimmäinen paikka.

994
01:17:36,390 --> 01:17:44,080
Jos (nyk.-> oikeassa! = NULL)

995
01:17:44,080 --> 01:17:56,380
Sitten aiomme lisätä, että solmun listalta.

996
01:17:56,380 --> 01:17:59,290
Jos (nyk.-> vasen), tämä on hieman ylimääräistä työtä, mutta se on hieno.

997
01:17:59,290 --> 01:18:02,690
Jos (nyk.-> vasen! = NULL),

998
01:18:02,690 --> 01:18:14,310
ja aiomme lisätä vasemmalle meidän linkitetty lista,

999
01:18:14,310 --> 01:18:19,700
ja että olisi se.

1000
01:18:19,700 --> 01:18:22,670
Me toistaa - niin kauan kuin meillä on jotain listalta,

1001
01:18:22,670 --> 01:18:26,640
meillä on toinen solmu katsoa.

1002
01:18:26,640 --> 01:18:28,920
Joten katsomme, että solmu,

1003
01:18:28,920 --> 01:18:31,390
me etukäteen lista on seuraava.

1004
01:18:31,390 --> 01:18:34,060
Jos tämä solmu on arvo etsimme, voimme palata totta.

1005
01:18:34,060 --> 01:18:37,640
Else laitat molemmat meidän vasemmalle ja oikealle alipuut,

1006
01:18:37,640 --> 01:18:40,510
niin kauan kuin he eivät null, meidän lista

1007
01:18:40,510 --> 01:18:43,120
niin että me väistämättä mennä niiden yli.

1008
01:18:43,120 --> 01:18:45,160
Joten jos ne eivät null,

1009
01:18:45,160 --> 01:18:47,950
jos meidän root osoitin osoitti kaksi asiaa,

1010
01:18:47,950 --> 01:18:51,670
Sitten aluksi me vedetään jotain niin lista päätyy null.

1011
01:18:51,670 --> 01:18:56,890
Ja sitten laitoimme kaksi asiaa takaisin, joten nyt meidän lista on kooltaan 2.

1012
01:18:56,890 --> 01:19:00,030
Sitten menemme silmukka takaisin ylös ja olemme juuri menossa vetämään,

1013
01:19:00,030 --> 01:19:04,250
Sanotaan, vasen osoitin meidän juurisolmun.

1014
01:19:04,250 --> 01:19:07,730
Ja että vain pitää tapahtumassa, me lopulta silmukoiden yli kaiken.

1015
01:19:07,730 --> 01:19:11,280
>> Huomaa, että tämä on huomattavasti monimutkaisempi

1016
01:19:11,280 --> 01:19:14,160
on rekursiivinen liuokseen.

1017
01:19:14,160 --> 01:19:17,260
Ja olen sanonut useita kertoja

1018
01:19:17,260 --> 01:19:25,120
että rekursiivinen ratkaisu on yleensä paljon yhteistä iteratiivinen ratkaisu.

1019
01:19:25,120 --> 01:19:30,820
Täällä tämä on juuri rekursiivinen ratkaisu tekee.

1020
01:19:30,820 --> 01:19:36,740
Ainoa muutos on se, että sen sijaan, että epäsuorasti käyttäen pinon, ohjelma pino,

1021
01:19:36,740 --> 01:19:40,840
kuin tapa pitää kirjaa mitä solmujen tarvitset silti käydä,

1022
01:19:40,840 --> 01:19:45,430
Nyt sinun on eksplisiittisesti käytettävä linkitetty lista.

1023
01:19:45,430 --> 01:19:49,070
Molemmissa tapauksissa olet tarkkailemalla mitä solmun on vielä käynyt.

1024
01:19:49,070 --> 01:19:51,790
Vuonna rekursiivinen tapauksessa se on vain helpompaa, koska pino

1025
01:19:51,790 --> 01:19:57,100
toteutetaan sinulle kuin ohjelma pino.

1026
01:19:57,100 --> 01:19:59,550
Huomaa, että tämä linkitetty lista, se on pino.

1027
01:19:59,550 --> 01:20:01,580
Mitä me vain laittaa pinoon

1028
01:20:01,580 --> 01:20:09,960
välittömästi, mitä aiomme vetää pois pinosta vierailla seuraavaksi.

1029
01:20:09,960 --> 01:20:14,380
Olemme myöhässä, mutta kysyttävää?

1030
01:20:14,380 --> 01:20:23,530
[Student, käsittämättömällä]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Joo. Eli jos meillä on linkitetty lista,

1032
01:20:27,790 --> 01:20:30,150
nykyinen tulee osoittamaan tämä kaveri,

1033
01:20:30,150 --> 01:20:34,690
ja nyt me vain edistämme linkitetyn listan keskittyä tämän kaveri.

1034
01:20:34,690 --> 01:20:44,200
Olemme liikkumisesta yli linkitetyn listan kyseisen rivin.

1035
01:20:44,200 --> 01:20:51,200
Ja sitten kai meidän pitäisi vapauttaa myös linkitetty lista ja juttuja

1036
01:20:51,200 --> 01:20:53,880
kerran ennen paluuta totta vai tarua, meidän

1037
01:20:53,880 --> 01:20:57,360
toistaa yli meidän linkitetty lista ja aina täällä, luulisin,

1038
01:20:57,360 --> 01:21:03,900
jos me nyk. oikeus ei ole sama, lisää se, joten nyt haluamme vapauttaa

1039
01:21:03,900 --> 01:21:09,600
nyk. koska hyvin, teimme täysin unohtaa luettelossa? Joo.

1040
01:21:09,600 --> 01:21:12,880
Niin, että mitä me haluamme tehdä täällä.

1041
01:21:12,880 --> 01:21:16,730
Missä osoitin?

1042
01:21:16,730 --> 01:21:23,320
Cur oli silloin - haluamme struct lista * 10 vastaa luettelon vieressä.

1043
01:21:23,320 --> 01:21:29,240
Ilmainen luettelo, lista = lämpötila.

1044
01:21:29,240 --> 01:21:32,820
Ja siinä tapauksessa, että palaamme totta, tarvitsemme iteroida

1045
01:21:32,820 --> 01:21:37,050
jäljellä olevan linkitetyn listan vapauttaa asioita.

1046
01:21:37,050 --> 01:21:39,700
Kiva juttu rekursiivinen ratkaisu on vapauttaa asioita

1047
01:21:39,700 --> 01:21:44,930
tarkoittaa vain popping factorings pinosta joka tapahtuu sinulle.

1048
01:21:44,930 --> 01:21:50,720
Joten olemme menneet jotain on kuin 3 riviä vaikeasti think noin code

1049
01:21:50,720 --> 01:21:57,520
jotain, joka on huomattavasti paljon enemmän vaikeasti think noin koodiriviä.

1050
01:21:57,520 --> 01:22:00,620
Vielä kysymyksiä?

1051
01:22:00,620 --> 01:22:08,760
Selvä. Olemme hyviä. Hei!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]