1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [7 §] [vähemmän mukavaksi]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Harvardin yliopisto]

3
00:00:04,890 --> 00:00:07,000
[Tämä on CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Tervetuloa 7 §.

5
00:00:09,080 --> 00:00:11,330
Kiitos hurrikaani Sandy,

6
00:00:11,330 --> 00:00:13,440
sen sijaan, jolla on normaali osa tällä viikolla,

7
00:00:13,440 --> 00:00:17,650
teemme tämän selattava läpi osa kysymyksistä.

8
00:00:17,650 --> 00:00:22,830
Aion Seuraamme yhdessä Harjoitus 6 Specification,

9
00:00:22,830 --> 00:00:25,650
ja menee läpi kaikki kysymykset

10
00:00:25,650 --> 00:00:27,770
§ Kysymysten osan.

11
00:00:27,770 --> 00:00:30,940
Jos on kysyttävää,

12
00:00:30,940 --> 00:00:32,960
lähetä nämä on CS50 keskustella.

13
00:00:32,960 --> 00:00:35,480
>> Selvä. Aloitetaan.

14
00:00:35,480 --> 00:00:40,780
Juuri nyt olen etsimässä sivulla 3 Harjoitus Specification.

15
00:00:40,780 --> 00:00:44,110
Menemme ensin alkaa puhua binääripuita

16
00:00:44,110 --> 00:00:47,850
koska ne on paljon merkitystä tällä viikolla ongelma set -

17
00:00:47,850 --> 00:00:49,950
Huffman Tree koodausta.

18
00:00:49,950 --> 00:00:55,000
Yksi ensimmäisistä tietorakenteiden puhuimme siitä CS50 oli jono.

19
00:00:55,000 --> 00:01:00,170
Muista, että matriisi on sekvenssi elementtejä -

20
00:01:00,170 --> 00:01:04,019
kaikki samaa tyyppiä - tallennetaan aivan toistensa muistiin.

21
00:01:04,019 --> 00:01:14,420
Jos minulla on kokonaisluku array, että voin tehdä tällä laatikot-numerot-kokonaislukuja style -

22
00:01:14,420 --> 00:01:20,290
Sanotaan Minulla on 5 ensimmäiseen ruutuun, minulla 7 toiseen,

23
00:01:20,290 --> 00:01:27,760
Sitten minulla on 8, 10, ja 20 lopullisessa ruutuun.

24
00:01:27,760 --> 00:01:33,000
Muista, kaksi todella hyvää tästä array

25
00:01:33,000 --> 00:01:38,800
on, että meillä on tämä jatkuva-aikaisen pääsyn jokin erityinen tekijä

26
00:01:38,800 --> 00:01:40,500
 pakassa, jos tiedämme sen indeksi.

27
00:01:40,500 --> 00:01:44,670
Esimerkiksi, jos haluan napata kolmannen elementin array -

28
00:01:44,670 --> 00:01:47,870
klo indeksi 2 käyttämällä nolla-pohjainen indeksointijärjestelmä -

29
00:01:47,870 --> 00:01:52,220
Olen kirjaimellisesti vain täytyy tehdä yksinkertaisen laskutoimituksen,

30
00:01:52,220 --> 00:01:56,170
hop tuossa asemassa array,

31
00:01:56,170 --> 00:01:57,840
vedä 8, joka on tallennettu siellä,

32
00:01:57,840 --> 00:01:59,260
ja olen hyvä mennä.

33
00:01:59,260 --> 00:02:03,350
>> Yksi pahaa tästä array - että puhuimme

34
00:02:03,350 --> 00:02:05,010
kun keskustelimme linkitettyjä listoja -

35
00:02:05,010 --> 00:02:09,120
että jos haluan lisätä elementin tähän array,

36
00:02:09,120 --> 00:02:11,090
Aion täytyy tehdä joitakin siirtymässä ympärille.

37
00:02:11,090 --> 00:02:12,940
Esimerkiksi tämä joukko täällä

38
00:02:12,940 --> 00:02:16,850
on lajiteltu järjestyksessä - lajiteltu nousevaan järjestykseen -

39
00:02:16,850 --> 00:02:19,440
5, sitten 7, sitten 8, sitten 10, sitten 20 -

40
00:02:19,440 --> 00:02:23,100
mutta jos haluan lisätä numero 9 tähän array,

41
00:02:23,100 --> 00:02:27,460
Aion pitää siirtää joitakin elementtejä, jotta tilaa.

42
00:02:27,460 --> 00:02:30,440
Voimme tehdä tämän täällä.

43
00:02:30,440 --> 00:02:35,650
Aion pitää siirtää 5, 7, ja sitten 8;

44
00:02:35,650 --> 00:02:38,720
luoda kuilu, jossa voin laittaa 9,

45
00:02:38,720 --> 00:02:45,910
ja sitten 10 ja 20 voi mennä oikealle 9.

46
00:02:45,910 --> 00:02:49,450
Tämä on eräänlainen kipu koska pahimmassa tapauksessa -

47
00:02:49,450 --> 00:02:54,350
kun meillä ollut lisätä joko alussa tai lopussa

48
00:02:54,350 --> 00:02:56,040
ja array, riippuen siitä, miten me Tuulen -

49
00:02:56,040 --> 00:02:58,850
saatamme päätyä siirtää kaikki elementit

50
00:02:58,850 --> 00:03:00,750
että olemme nyt tallentaminen array.

51
00:03:00,750 --> 00:03:03,810
>> Joten, mikä oli tapa kiertää tämä?

52
00:03:03,810 --> 00:03:09,260
Tapa kiertää tämä oli mennä meidän linkitetyn-lista menetelmää, jossa -

53
00:03:09,260 --> 00:03:19,820
sen sijaan, että tallennetaan elementtien 5, 7, 8, 10, ja 20 kaikki vierekkäin muistiin -

54
00:03:19,820 --> 00:03:25,630
Mitä me sen sijaan ei ollut tallentaa ne tavallaan missä halusimme tallentaa ne

55
00:03:25,630 --> 00:03:32,470
Näiden linkitetyn listan solmuista, jotka olen piirustus täällä, tavallaan ad hoc.

56
00:03:32,470 --> 00:03:42,060
Ja sitten me liittää ne yhteen näitä ensi osoittimia.

57
00:03:42,060 --> 00:03:44,370
Voin olla osoitin 5.-7,

58
00:03:44,370 --> 00:03:46,420
osoitinta 7 ja 8,

59
00:03:46,420 --> 00:03:47,770
osoitinta 8 10,

60
00:03:47,770 --> 00:03:51,220
ja lopuksi, osoitinta 10 ja 20,

61
00:03:51,220 --> 00:03:54,880
ja sitten nollaosoittimen klo 20 osoittaa, että ei ole mitään jäljellä.

62
00:03:54,880 --> 00:03:59,690
Kauppa-off, että meillä on täällä

63
00:03:59,690 --> 00:04:05,360
että nyt, jos haluamme lisätä numero 9 meidän järjestetty luettelo,

64
00:04:05,360 --> 00:04:08,270
kaikki mitä on tehtävä on luoda uusi solmu 9,

65
00:04:08,270 --> 00:04:12,290
lanka sen osoittamaan sopivaan paikkaan,

66
00:04:12,290 --> 00:04:20,630
ja sitten uudelleen johdin 8 osoittamaan alas 9.

67
00:04:20,630 --> 00:04:25,660
Se on aika nopea, olettaen tiedämme tarkalleen missä haluamme lisätä 9.

68
00:04:25,660 --> 00:04:32,610
Mutta kauppa-off vaihdossa on se, että olemme nyt menettäneet vakio-aika pääsy

69
00:04:32,610 --> 00:04:36,230
mihinkään tiettyyn osa meidän tietorakenne.

70
00:04:36,230 --> 00:04:40,950
Esimerkiksi, jos haluan löytää neljäs osa tätä linkitetty lista,

71
00:04:40,950 --> 00:04:43,510
Aion on aloitettava alusta luettelon

72
00:04:43,510 --> 00:04:48,930
ja työskennellä minun läpi laskemalla solmun-by-solmu kunnes löydän neljäs.

73
00:04:48,930 --> 00:04:55,870
>> Saadakseen paremman pääsyn suorituskykyä kuin linkitetty lista -

74
00:04:55,870 --> 00:04:59,360
mutta myös säilyttää joitakin etuja, että meillä oli

75
00:04:59,360 --> 00:05:01,800
suhteen lisäys-aika linkitetty lista -

76
00:05:01,800 --> 00:05:05,750
binääripuu on menossa tarvitse käyttää hieman enemmän muistia.

77
00:05:05,750 --> 00:05:11,460
Erityisesti sen sijaan, että vain ottaa yksi osoitin on binääripuun solmu -

78
00:05:11,460 --> 00:05:13,350
kuten linkitetyn listan solmu ei -

79
00:05:13,350 --> 00:05:16,950
aiomme lisätä toinen osoitin binääripuu solmu.

80
00:05:16,950 --> 00:05:19,950
Pikemminkin kuin vain ottaa yksi osoitin seuraavaan elementtiin,

81
00:05:19,950 --> 00:05:24,420
aiomme olla osoittimen vasen lapsi ja oikea lapsi.

82
00:05:24,420 --> 00:05:26,560
>> Katsotaanpa piirtää kuvaa nähdäksesi, mitä se todella näyttää.

83
00:05:26,560 --> 00:05:31,350
Jälleen aion käyttää näitä laatikoita ja nuolia.

84
00:05:31,350 --> 00:05:37,150
Binääripuu solmu aluksi vain yksinkertainen laatikko.

85
00:05:37,150 --> 00:05:40,940
Se tulee olemaan tilaa arvoa,

86
00:05:40,940 --> 00:05:47,280
ja sitten se myös tulee olemaan tilaa vasen lapsi ja oikea lapsi.

87
00:05:47,280 --> 00:05:49,280
Aion merkitä ne tänne.

88
00:05:49,280 --> 00:05:57,560
Aiomme olla vasen lapsi, ja sitten me aiomme olla oikea lapsi.

89
00:05:57,560 --> 00:05:59,920
On olemassa monia erilaisia ​​tapoja tehdä tätä.

90
00:05:59,920 --> 00:06:02,050
Joskus tilaa ja mukavuutta,

91
00:06:02,050 --> 00:06:06,460
Minä itse piirtää niin kuin olen täällä alhaalla

92
00:06:06,460 --> 00:06:10,910
minne olen menossa arvoa yläreunassa,

93
00:06:10,910 --> 00:06:14,060
ja sitten oikealle lapsen alaoikealla,

94
00:06:14,060 --> 00:06:16,060
ja vasen lapsi alhaalla vasemmalla.

95
00:06:16,060 --> 00:06:20,250
Palataan tähän alkuun kaavio,

96
00:06:20,250 --> 00:06:22,560
meillä arvoa huipulla,

97
00:06:22,560 --> 00:06:25,560
Sitten meillä on vasemman lapsen osoitin, ja sitten meillä on oikeus lapsen osoitin.

98
00:06:25,560 --> 00:06:30,110
>> Vuonna Harjoitus Specification,

99
00:06:30,110 --> 00:06:33,110
puhumme piirtämällä solmu, jonka arvo on 7,

100
00:06:33,110 --> 00:06:39,750
ja sitten vasen lapsi osoitin, joka on nolla, ja oikea lapsi-osoitin, joka on nolla.

101
00:06:39,750 --> 00:06:46,040
Voimme joko kirjoittaa pääomaa NULL tilaa

102
00:06:46,040 --> 00:06:51,610
Sekä vasen lapsi ja oikea lapsi, tai voimme tehdä tämän lävistäjä slash

103
00:06:51,610 --> 00:06:53,750
läpi jokaisen laatikot osoittavat että se on null.

104
00:06:53,750 --> 00:06:57,560
Aion tehdä sitä vain koska se on yksinkertaisempi.

105
00:06:57,560 --> 00:07:03,700
Mitä näet tässä on kaksi tapaa kaavio hyvin yksinkertainen binääripuu solmu

106
00:07:03,700 --> 00:07:07,960
jossa meillä on arvo 7 ja null lapsi viitteitä.

107
00:07:07,960 --> 00:07:15,220
>> Toinen osa eritelmän puhutaan kuinka linkitettyjä luetteloita -

108
00:07:15,220 --> 00:07:18,270
Muista, meillä oli vain pitää kiinni aivan ensimmäinen elementti luettelossa

109
00:07:18,270 --> 00:07:20,270
muistaa koko lista -

110
00:07:20,270 --> 00:07:26,140
ja samoin, jossa on binääripuu, meillä on vain pitää kiinni yksi osoitin puun

111
00:07:26,140 --> 00:07:31,120
säilyttämiseksi valvonnan koko tietorakenne.

112
00:07:31,120 --> 00:07:36,150
Tämä erityinen osa puun kutsutaan juurisolmu puun.

113
00:07:36,150 --> 00:07:43,360
Esimerkiksi, jos tämä solmu - tämä solmu sisältää arvon 7

114
00:07:43,360 --> 00:07:45,500
null-vasen-ja oikea-lapsi osoittimia -

115
00:07:45,500 --> 00:07:47,360
olivat ainoa arvo meidän puu,

116
00:07:47,360 --> 00:07:50,390
niin tämä olisi meidän juurisolmun.

117
00:07:50,390 --> 00:07:52,240
Se on alusta meidän puu.

118
00:07:52,240 --> 00:07:58,530
Voimme nähdä tämän hieman selkeämmin kun alamme lisäämällä solmut meidän puuhun.

119
00:07:58,530 --> 00:08:01,510
Saanen vetää uuden sivun.

120
00:08:01,510 --> 00:08:05,000
>> Nyt aiomme tehdä puu, joka on 7 juuresta,

121
00:08:05,000 --> 00:08:10,920
ja 3 sisällä vasen lapsi, ja 9 sisällä oikea lapsi.

122
00:08:10,920 --> 00:08:13,500
Tämäkin on melko yksinkertainen.

123
00:08:13,500 --> 00:08:26,510
Meillä 7, piirtää solmu 3, solmu 9,

124
00:08:26,510 --> 00:08:32,150
ja aion asettaa vasemman lapsen osoitin 7 osoittamaan solmuun sisältävät 3,

125
00:08:32,150 --> 00:08:37,850
ja oikea lapsi-osoitin solmun sisältää 7 solmu, joka sisältää 9.

126
00:08:37,850 --> 00:08:42,419
Nyt, koska 3 ja 9 ei ole lapsia,

127
00:08:42,419 --> 00:08:48,500
aiomme asettaa kaikki lapsensa osoittimia olla null.

128
00:08:48,500 --> 00:08:56,060
Tässä juuri meidän puu vastaa solmun sisältävä numero 7.

129
00:08:56,060 --> 00:09:02,440
Voit nähdä, että jos kaikki meillä on osoitin, joka juurisolmu

130
00:09:02,440 --> 00:09:07,330
Voimme sitten kävellä läpi puiden ja käyttää sekä lapsen solmut -

131
00:09:07,330 --> 00:09:10,630
sekä 3 ja 9.

132
00:09:10,630 --> 00:09:14,820
Ei tarvitse säilyttää viitteitä jokaiseen solmuun puussa.

133
00:09:14,820 --> 00:09:22,080
Selvä. Nyt aiomme lisätä toisen solmun tähän kaavio.

134
00:09:22,080 --> 00:09:25,370
Aiomme lisätä solmun sisältää 6,

135
00:09:25,370 --> 00:09:34,140
ja aiomme lisätä tätä oikeutta lapsi solmu sisältää 3.

136
00:09:34,140 --> 00:09:41,850
Voit tehdä sen, aion poistaa että null osoitin 3-solmu

137
00:09:41,850 --> 00:09:47,750
ja lanka sen osoittamaan solmuun sisältää 6. Selvä.

138
00:09:47,750 --> 00:09:53,800
>> Tässä vaiheessa mennään yli hieman terminologiaa.

139
00:09:53,800 --> 00:09:58,230
Voit aloittaa, syystä, että tätä kutsutaan binääripuu erityisesti

140
00:09:58,230 --> 00:10:00,460
on, että se on kaksi lasta osoittimia.

141
00:10:00,460 --> 00:10:06,020
On olemassa muitakin puita, jotka ovat enemmän lapsi osoittimia.

142
00:10:06,020 --> 00:10:10,930
Erityisesti teit 'yritä' in Harjoitus 5.

143
00:10:10,930 --> 00:10:19,310
Huomaat, että se yrittää, teillä oli 27 eri osoittimia eri lapsille -

144
00:10:19,310 --> 00:10:22,410
yksi kullekin 26 kirjainten Englanti aakkoset,

145
00:10:22,410 --> 00:10:25,410
ja sitten 27. ja heittomerkki -

146
00:10:25,410 --> 00:10:28,900
niin, että se vastaa puun tyyppi.

147
00:10:28,900 --> 00:10:34,070
Mutta täällä, koska se on binääri, meillä on vain kaksi lasta viitteitä.

148
00:10:34,070 --> 00:10:37,880
>> Tämän lisäksi juurisolmu että puhuimme,

149
00:10:37,880 --> 00:10:41,470
olemme myös heittää noin termiä "lapsi".

150
00:10:41,470 --> 00:10:44,470
Mitä se tarkoittaa yhden solmun olla lapselle toisen solmun?

151
00:10:44,470 --> 00:10:54,060
Se tarkoittaa kirjaimellisesti että lapsi solmu on lapsi toisen solmun

152
00:10:54,060 --> 00:10:58,760
ja jos tämä toinen solmulla on yksi sen lapsen osoittimia asetettu osoittamaan, että solmu.

153
00:10:58,760 --> 00:11:01,230
Tämän toteuttamiseksi enemmän Konkreettisesti

154
00:11:01,230 --> 00:11:11,170
jos 3, joka on suunnattu yhden lapsen osoittimien 7, sitten 3 on lapsi 7.

155
00:11:11,170 --> 00:11:14,510
Jos me selvittää, mitä lapset 7 ovat -

156
00:11:14,510 --> 00:11:18,510
hyvin, näemme, että 7 on osoittimen 3 ja osoittimen 9,

157
00:11:18,510 --> 00:11:22,190
joten 9 ja 3 ovat lapsia 7.

158
00:11:22,190 --> 00:11:26,650
Yhdeksän ole lapsia, koska sen lapsen osoittimet ovat null,

159
00:11:26,650 --> 00:11:30,940
ja 3 on vain yksi lapsi, 6.

160
00:11:30,940 --> 00:11:37,430
Kuusi ei myöskään ole lapsia, koska sen molemmat osoittimet ovat null, jossa me tehdä juuri nyt.

161
00:11:37,430 --> 00:11:45,010
>> Lisäksi me myös puhumme vanhemmille tietyn solmun,

162
00:11:45,010 --> 00:11:51,100
ja tämä on, kuten odottaa saattaa, käänteinen tämän lapsen kuvauksen.

163
00:11:51,100 --> 00:11:58,620
Jokaisella solmulla on vain yksi vanhempi - kahden sijasta kuten arvata saattaa ihmisten kanssa.

164
00:11:58,620 --> 00:12:03,390
Esimerkiksi vanhemman 3 on 7.

165
00:12:03,390 --> 00:12:10,800
Vanhempi 9 on 7, ja vanhempi 6 on 3. Ei paljon se.

166
00:12:10,800 --> 00:12:15,720
Meillä on myös ehdot puhua isovanhemmat ja lapsenlapset,

167
00:12:15,720 --> 00:12:18,210
ja yleisemmin puhumme esivanhemmat

168
00:12:18,210 --> 00:12:20,960
ja jälkeläiset tiettyyn solmuun.

169
00:12:20,960 --> 00:12:25,710
Esi solmun - tai esivanhemmat, pikemminkin on solmu -

170
00:12:25,710 --> 00:12:32,730
ovat kaikki solmut, jotka sijaitsevat polkua juuresta, että solmu.

171
00:12:32,730 --> 00:12:36,640
Jos esimerkiksi Etsin solmuun 6,

172
00:12:36,640 --> 00:12:46,430
sitten esi-isät tulevat olemaan sekä 3 ja 7.

173
00:12:46,430 --> 00:12:55,310
Esi 9, esimerkiksi, ovat - jos Etsin navassa 9 -

174
00:12:55,310 --> 00:12:59,990
Sitten kantaisä 9 on vain 7.

175
00:12:59,990 --> 00:13:01,940
Ja jälkeläiset ovat täsmälleen päinvastainen.

176
00:13:01,940 --> 00:13:05,430
Jos haluan tarkastella kaikkia jälkeläisiä 7,

177
00:13:05,430 --> 00:13:11,020
Sitten minun täytyy katsoa kaikki solmut sen alapuolella.

178
00:13:11,020 --> 00:13:16,950
Joten, minulla on 3, 9 ja 6 kaikki jälkeläisinä 7.

179
00:13:16,950 --> 00:13:24,170
>> Lopullisen termi puhumme tämä käsite on sisarus.

180
00:13:24,170 --> 00:13:27,980
Sisarukset - eräänlainen seuraavat pitkin näiden perheiden ehdoin -

181
00:13:27,980 --> 00:13:33,150
ovat solmuja, jotka ovat samalla tasolla puussa.

182
00:13:33,150 --> 00:13:42,230
Niin, 3 ja 9 ovat sisaruksia, koska ne ovat samalla tasolla puussa.

183
00:13:42,230 --> 00:13:46,190
Niillä molemmilla on sama emo, 7.

184
00:13:46,190 --> 00:13:51,400
6 ei ole sisaruksia, koska 9 ei ole lapsia.

185
00:13:51,400 --> 00:13:55,540
Ja 7 ei ole sisaruksia, koska se on juuri meidän puu,

186
00:13:55,540 --> 00:13:59,010
ja siellä on aina vain 1 root.

187
00:13:59,010 --> 00:14:02,260
7 on sisaruksia ei pitäisi olla solmun yläpuolella 7.

188
00:14:02,260 --> 00:14:07,480
Siellä pitäisi olla vanhempi 7, jolloin 7 olisi enää puun juuresta.

189
00:14:07,480 --> 00:14:10,480
Sitten että uusi emoyhtiö 7 olisi myös oltava lapsen,

190
00:14:10,480 --> 00:14:16,480
ja että lapsi olisi silloin sisarus 7.

191
00:14:16,480 --> 00:14:21,040
>> Selvä. Liikettä.

192
00:14:21,040 --> 00:14:24,930
Kun aloitimme keskustelun binääripuita,

193
00:14:24,930 --> 00:14:28,790
puhuimme siitä, miten aiomme käyttää niitä

194
00:14:28,790 --> 00:14:32,800
saavat etulyöntiaseman sekä taulukot ja linkitettyjen listojen.

195
00:14:32,800 --> 00:14:37,220
Ja miten aiomme tehdä se on tämän tilauksen omaisuutta.

196
00:14:37,220 --> 00:14:41,080
Sanomme, että binääripuu on tilattu, erittelyn mukainen,

197
00:14:41,080 --> 00:14:45,740
jos kunkin solmun meidän puu, kaikki sen jälkeläiset vasemmalla -

198
00:14:45,740 --> 00:14:48,670
vasen lapsi ja kaikki vasemman lapsen jälkeläiset -

199
00:14:48,670 --> 00:14:54,510
on vähemmän arvot, ja kaikki solmut oikealla -

200
00:14:54,510 --> 00:14:57,770
oikea lapsi ja kaikki oikean lapsen jälkeläiset -

201
00:14:57,770 --> 00:15:02,800
on solmuja suurempi kuin arvo nykyisen solmun että me tarkastelemme.

202
00:15:02,800 --> 00:15:07,850
Vain yksinkertaisuuden, aiomme olettaa, että ei ole mitään päällekkäisiä solmuja meidän puu.

203
00:15:07,850 --> 00:15:11,180
Esimerkiksi tämä puu emme aio käsitellä asian

204
00:15:11,180 --> 00:15:13,680
jossa meillä on arvo 7 juuresta

205
00:15:13,680 --> 00:15:16,720
 ja sitten meillä on myös arvo 7 muualla puussa.

206
00:15:16,720 --> 00:15:24,390
Tässä tapauksessa, huomaat, että tämä puu on todellakin tilattu.

207
00:15:24,390 --> 00:15:26,510
Meillä on arvo 7 juuresta.

208
00:15:26,510 --> 00:15:29,720
Kaiken vasemmalla 7 -

209
00:15:29,720 --> 00:15:35,310
jos minä perua kaikki nämä pikku merkkien täällä -

210
00:15:35,310 --> 00:15:40,450
kaiken vasemmalla 7 - 3 ja 6 -

211
00:15:40,450 --> 00:15:49,410
nämä arvot ovat molemmat alle 7, ja kaiken oikealle - mikä on juuri tämä 9 -

212
00:15:49,410 --> 00:15:53,450
on suurempi kuin 7.

213
00:15:53,450 --> 00:15:58,650
>> Tämä ei ole ainoa tilattu puu, joka sisältää näitä arvoja,

214
00:15:58,650 --> 00:16:03,120
mutta katsotaanpa piirtää muutamia niistä.

215
00:16:03,120 --> 00:16:05,030
On todella koko joukko tapoja, joilla voimme tehdä tämän.

216
00:16:05,030 --> 00:16:09,380
Aion käyttää pika vain pitää asiat yksinkertaisina, jossa -

217
00:16:09,380 --> 00:16:11,520
sijaan piirustus ulos koko laatikot-ja-nuolet -

218
00:16:11,520 --> 00:16:14,220
Aion tehdä numeroita ja lisätä nuolia yhdistämällä ne.

219
00:16:14,220 --> 00:16:22,920
Voit aloittaa, me vain kirjoittaa meidän alkuperäinen Tree jälleen missä meillä oli 7, ja sitten 3,

220
00:16:22,920 --> 00:16:25,590
ja sitten 3 huomautti takaisin oikealle 6,

221
00:16:25,590 --> 00:16:30,890
ja 7 oli oikea lapsi, joka oli 9.

222
00:16:30,890 --> 00:16:33,860
Selvä. Mikä on toinen tapa, että voisimme kirjoittaa tämä puu?

223
00:16:33,860 --> 00:16:38,800
Sen sijaan, että 3 on vasen lapsi 7,

224
00:16:38,800 --> 00:16:41,360
Voisimme myös 6 olla vasen lapsi 7,

225
00:16:41,360 --> 00:16:44,470
ja sitten 3 on vasemmalla puolella lapsi 6.

226
00:16:44,470 --> 00:16:48,520
Se näyttää tältä puu täällä missä minulla 7,

227
00:16:48,520 --> 00:16:57,860
Sitten 6, sitten 3 ja 9 oikealla puolella.

228
00:16:57,860 --> 00:17:01,490
Emme myöskään tarvitse olla 7 meidän juurisolmun.

229
00:17:01,490 --> 00:17:03,860
Voisimme myös 6 meidän juurisolmun.

230
00:17:03,860 --> 00:17:06,470
Mikä se näyttää?

231
00:17:06,470 --> 00:17:09,230
Jos aiomme säilyttää tämän tilattu omaisuutta,

232
00:17:09,230 --> 00:17:12,970
kaiken vasemmalla puolella 6 täytyy olla pienempi kuin se.

233
00:17:12,970 --> 00:17:16,540
On vain yksi mahdollisuus, ja se on 3.

234
00:17:16,540 --> 00:17:19,869
Mutta sitten kun oikea lapsi 6, meillä on kaksi vaihtoehtoa.

235
00:17:19,869 --> 00:17:25,380
Ensinnäkin, meillä voisi olla 7 ja sitten 9,

236
00:17:25,380 --> 00:17:28,850
tai voimme tehdä sen - kuten aion tehdä täällä -

237
00:17:28,850 --> 00:17:34,790
jossa meillä on 9 kuin oikea lapsi 6,

238
00:17:34,790 --> 00:17:39,050
ja sitten 7 kuten vasen lapsi 9.

239
00:17:39,050 --> 00:17:44,240
>> Nyt, 7 ja 6 eivät ole ainoat mahdolliset arvot root.

240
00:17:44,240 --> 00:17:50,200
Voisimme myös 3 syihin.

241
00:17:50,200 --> 00:17:52,240
Mitä tapahtuu, jos 3 on root?

242
00:17:52,240 --> 00:17:54,390
Täällä asiat saavat hieman mielenkiintoinen.

243
00:17:54,390 --> 00:17:58,440
Kolme ei ole mitään arvoja, jotka ovat vähemmän kuin se,

244
00:17:58,440 --> 00:18:02,070
siten, että koko vasen puoli puu on vain olemaan nolla.

245
00:18:02,070 --> 00:18:03,230
Ei ei tule olemaan mitään.

246
00:18:03,230 --> 00:18:07,220
Oikealle, voisimme luetella asioita nousevassa järjestyksessä.

247
00:18:07,220 --> 00:18:15,530
Meillä voisi olla 3, sitten 6, sitten 7, sitten 9.

248
00:18:15,530 --> 00:18:26,710
Tai voisimme tehdä 3, sitten 6, sitten 9 ja sitten 7.

249
00:18:26,710 --> 00:18:35,020
Tai voisimme tehdä 3, sitten 7, sitten 6, sitten 9.

250
00:18:35,020 --> 00:18:40,950
Tai, 3, 7 - oikeastaan ​​mitään, emme voi tehdä 7 enää.

251
00:18:40,950 --> 00:18:43,330
Se on meidän yksi asia siellä.

252
00:18:43,330 --> 00:18:54,710
Voimme tehdä 9, ja sitten 9 voimme tehdä 6 ja sitten 7.

253
00:18:54,710 --> 00:19:06,980
Tai voimme tehdä 3, sitten 9, sitten 7 ja sitten 6.

254
00:19:06,980 --> 00:19:12,490
>> Yksi asia kiinnittää huomiota tässä

255
00:19:12,490 --> 00:19:14,510
että nämä puut ovat hieman oudon näköisiä.

256
00:19:14,510 --> 00:19:17,840
Erityisesti jos katsomme 4 puut oikealla puolella -

257
00:19:17,840 --> 00:19:20,930
Minä ympyrä heitä täällä -

258
00:19:20,930 --> 00:19:28,410
nämä puut näyttävät melkein täsmälleen kuten linkitetty lista.

259
00:19:28,410 --> 00:19:32,670
Kukin solmu on vain yksi lapsi,

260
00:19:32,670 --> 00:19:38,950
ja joten meillä ei ole mitään tämän puumainen rakenne, että me katso esimerkiksi,

261
00:19:38,950 --> 00:19:44,720
 tässä yksi yksinäinen puu tänne alhaalla vasemmalla.

262
00:19:44,720 --> 00:19:52,490
Nämä puut ovat todella kutsutaan degeneroitunut binääripuita,

263
00:19:52,490 --> 00:19:54,170
ja me puhumme näistä enemmän tulevaisuudessa -

264
00:19:54,170 --> 00:19:56,730
varsinkin jos menet ottamaan muihin tietojenkäsittelytieteen kursseja.

265
00:19:56,730 --> 00:19:59,670
Nämä puut ovat rappeutua.

266
00:19:59,670 --> 00:20:03,780
He eivät ole kovin hyödyllisiä, koska, todellakin, tämä rakenne soveltuu

267
00:20:03,780 --> 00:20:08,060
 lookup kertaa samanlainen kuin linkitetty lista.

268
00:20:08,060 --> 00:20:13,050
Emme saa hyödyntää lisämuistia - tämä extra osoitin -

269
00:20:13,050 --> 00:20:18,840
koska meidän rakenne on huono tällä tavalla.

270
00:20:18,840 --> 00:20:24,700
Sen sijaan mene ja vedä binääripuita että on 9 juuresta,

271
00:20:24,700 --> 00:20:27,220
mikä on viimeinen asia, että meillä olisi,

272
00:20:27,220 --> 00:20:32,380
olemme sen sijaan, tässä vaiheessa aio puhua hieman tästä muiden aikavälillä

273
00:20:32,380 --> 00:20:36,150
että käytämme puhuttaessa puita, jota kutsutaan korkeus.

274
00:20:36,150 --> 00:20:45,460
>> Korkeus puu on etäisyys juuresta eniten kaukana solmu,

275
00:20:45,460 --> 00:20:48,370
tai pikemminkin hyppyjen määrä, että sinun täytyisi tehdä, jotta

276
00:20:48,370 --> 00:20:53,750
alkaa juuresta ja sitten päätyvät eniten kaukana solmu puussa.

277
00:20:53,750 --> 00:20:57,330
Jos tarkastelemme joitakin näistä puita että olemme piirretty täällä,

278
00:20:57,330 --> 00:21:07,870
Voimme nähdä, että jos otamme tämän puun vasemmassa yläkulmassa ja aloitamme klo 3,

279
00:21:07,870 --> 00:21:14,510
Sitten meidän on tehtävä 1 hypyn päästä 6, toinen hop päästä 7,

280
00:21:14,510 --> 00:21:20,560
ja kolmasosa hop päästä 9.

281
00:21:20,560 --> 00:21:26,120
Joten, korkeus tämä puu on 3.

282
00:21:26,120 --> 00:21:30,640
Voimme tehdä sama harjoitus muut puut hahmotellut tätä vihreä,

283
00:21:30,640 --> 00:21:40,100
ja näemme, että korkeus kaikki nämä puut on todellakin 3.

284
00:21:40,100 --> 00:21:45,230
Se osa, mikä tekee niistä rappeutua -

285
00:21:45,230 --> 00:21:53,750
että niiden korkeus on vain yksi vähemmän kuin solmujen lukumäärä koko puun.

286
00:21:53,750 --> 00:21:58,400
Jos tarkastelemme tässä muut puu, joka on ympäröity punaisella, toisaalta,

287
00:21:58,400 --> 00:22:03,920
näemme, että kaikkein-kaukaisessa lehtisolmuja ovat 6 ja 9 -

288
00:22:03,920 --> 00:22:06,940
lehdet ovat ne solmut, joilla ei ole lapsia.

289
00:22:06,940 --> 00:22:11,760
Joten, jotta saada siitä juurisolmu joko 6 tai 9,

290
00:22:11,760 --> 00:22:17,840
Meidän täytyy tehdä yhden hypyn päästä 7 ja sitten toisen hypyn päästä 9,

291
00:22:17,840 --> 00:22:21,240
ja samoin, vain toisen hypyn päässä 7 päästä 6.

292
00:22:21,240 --> 00:22:29,080
Niin, korkeus tämän puun yli tässä vain 2.

293
00:22:29,080 --> 00:22:35,330
Voit mennä takaisin ja tehdä kaikkien muiden puiden että aiemmin keskusteltu

294
00:22:35,330 --> 00:22:37,380
aloittaen 7 ja 6,

295
00:22:37,480 --> 00:22:42,500
ja huomaat, että korkeuden kaikkien näiden puiden on myös 2.

296
00:22:42,500 --> 00:22:46,320
>> Syy olemme puhuneet tilattu binääripuita

297
00:22:46,320 --> 00:22:50,250
ja miksi he siistiä, koska voit etsiä niitä

298
00:22:50,250 --> 00:22:53,810
hyvin samalla tavalla kuin hakemisen yli lajitellaan matriisina.

299
00:22:53,810 --> 00:22:58,720
Tästä me puhumme saada että parempi hakuaika

300
00:22:58,720 --> 00:23:02,730
yli yksinkertainen linkitetty lista.

301
00:23:02,730 --> 00:23:05,010
Kanssa linkitetty lista - jos haluat löytää tietyn elementin -

302
00:23:05,010 --> 00:23:07,470
olet paras aikoo tehdä jonkinlainen lineaarinen haku

303
00:23:07,470 --> 00:23:10,920
missä aloitat alussa luettelon ja hop yhden by-one -

304
00:23:10,920 --> 00:23:12,620
yksi solmu yksi solmu -

305
00:23:12,620 --> 00:23:16,060
läpi koko luetteloa kunnes löydät mitä etsit.

306
00:23:16,060 --> 00:23:19,440
Katsoo, että jos sinulla on binääripuu, joka on tallennettu tähän kivaan,

307
00:23:19,440 --> 00:23:23,300
voit itse saada enemmän binäärihakupuu käynnissä

308
00:23:23,300 --> 00:23:25,160
missä hajoita ja hallitse

309
00:23:25,160 --> 00:23:29,490
ja etsiä sopiva puoli puun kussakin vaiheessa.

310
00:23:29,490 --> 00:23:32,840
Katsotaan miten se toimii.

311
00:23:32,840 --> 00:23:38,850
>> Jos meillä on - jälleen menossa takaisin meidän alkuperäiseen puuhun -

312
00:23:38,850 --> 00:23:46,710
aloitamme klo 7, meillä on 3 vasemmalla puolella, 9 oikealla puolella,

313
00:23:46,710 --> 00:23:51,740
ja alle 3 meillä 6.

314
00:23:51,740 --> 00:24:01,880
Jos haluamme etsiä numero 6 tässä puussa, olimme alkaa juuresta.

315
00:24:01,880 --> 00:24:08,910
Haluamme verrata arvo etsimme, sanovat 6,

316
00:24:08,910 --> 00:24:12,320
arvoon tallennetaan solmun, joka tällä hetkellä vielä katselee, 7,

317
00:24:12,320 --> 00:24:21,200
toteavat, että 6 on todellakin alle 7, joten olimme liikkumaan vasemmalle.

318
00:24:21,200 --> 00:24:25,530
Jos arvo on 6 oli ollut suurempi kuin 7, olisimme sen sijaan siirretty oikealle.

319
00:24:25,530 --> 00:24:29,770
Koska tiedämme, että - rakenteen vuoksi meidän määräsi binaaripuun -

320
00:24:29,770 --> 00:24:33,910
kaikki arvot alle 7 aiotaan varastoida vasemmalla 7,

321
00:24:33,910 --> 00:24:40,520
ei tarvitse edes vaivaudu etsii läpi oikealle puolelle puun.

322
00:24:40,520 --> 00:24:43,780
Kun olemme siirtyä vasemmalle ja olemme nyt solmu, joka sisältää 3,

323
00:24:43,780 --> 00:24:48,110
voimme tehdä saman vertailun jälleen missä me vertailla 3 ja 6.

324
00:24:48,110 --> 00:24:52,430
Ja huomaamme, että vaikka 6 - arvo etsimme - on suurempi kuin 3,

325
00:24:52,430 --> 00:24:58,580
voimme mennä oikealle puolelle solmu, joka sisältää 3.

326
00:24:58,580 --> 00:25:02,670
Ei ole vasemmalla puolella täällä, joten olisimme voineet sivuuttaa sitä.

327
00:25:02,670 --> 00:25:06,510
Mutta tiedämme vain, että koska me tarkastelemme puu itse,

328
00:25:06,510 --> 00:25:08,660
ja voimme nähdä, että puu ei ole lapsia.

329
00:25:08,660 --> 00:25:13,640
>> Se on myös melko helppo etsiä 6 tässä puussa, jos teemme sen itsemme ihmisille,

330
00:25:13,640 --> 00:25:16,890
mutta seuraamme tätä prosessia mekaanisesti kuin tietokone tekisi

331
00:25:16,890 --> 00:25:18,620
todella ymmärtää algoritmin.

332
00:25:18,620 --> 00:25:26,200
Tässä vaiheessa me nyt katsot solmu, joka sisältää 6,

333
00:25:26,200 --> 00:25:29,180
ja etsimme arvon 6,

334
00:25:29,180 --> 00:25:31,740
niin, todellakin, olemme löytäneet sopivan solmun.

335
00:25:31,740 --> 00:25:35,070
Löysimme arvo 6 meidän puu, ja voimme lopettaa meidän etsiä.

336
00:25:35,070 --> 00:25:37,330
Tässä vaiheessa mukaan, mitä on tekeillä,

337
00:25:37,330 --> 00:25:41,870
Voimme sanoa, kyllä, olemme löytäneet arvon 6, se on olemassa meidän puu.

338
00:25:41,870 --> 00:25:47,640
Tai, jos me aiot lisätä solmun tai tehdä jotain, voimme tehdä sen tässä vaiheessa.

339
00:25:47,640 --> 00:25:53,010
>> Tehdään pari enemmän hakuja vain nähdä, miten tämä toimii.

340
00:25:53,010 --> 00:25:59,390
Katsotaan mitä tapahtuu, jos olisimme yrittää etsiä arvon 10.

341
00:25:59,390 --> 00:26:02,970
Jos me etsiä arvo 10, alkaisimme juureen.

342
00:26:02,970 --> 00:26:07,070
Olimme nähdä, että 10 on suurempi kuin 7, joten olimme liikkua oikealle.

343
00:26:07,070 --> 00:26:13,640
Olimme päästä 9 ja vertailla 9 10 ja nähdä, että 9 on todellakin alle 10.

344
00:26:13,640 --> 00:26:16,210
Joten jälleen, olimme yrittää siirtyä oikealle.

345
00:26:16,210 --> 00:26:20,350
Mutta tässä vaiheessa, olisimme huomata, että me olemme null solmussa.

346
00:26:20,350 --> 00:26:23,080
Siellä ei ole mitään. Mikään jossa 10 pitäisi olla.

347
00:26:23,080 --> 00:26:29,360
Tämä on, jos voimme ilmoittaa vika - että on todellakin Ei 10 puussa.

348
00:26:29,360 --> 00:26:35,420
Ja lopuksi, mennään läpi jos yritämme etsiä 1 puussa.

349
00:26:35,420 --> 00:26:38,790
Tämä on samanlainen kuin mitä tapahtuu, jos etsiä 10, paitsi sen sijaan menee oikealle,

350
00:26:38,790 --> 00:26:41,260
aiomme mennä vasemmalle.

351
00:26:41,260 --> 00:26:46,170
Aloitetaan 7 ja nähdä, että 1 on pienempi kuin 7, joten liikkumaan vasemmalle.

352
00:26:46,170 --> 00:26:51,750
Saamme 3 ja nähdä, että 1 on pienempi kuin 3, joten jälleen yritämme siirtyä vasemmalle.

353
00:26:51,750 --> 00:26:59,080
Tässä vaiheessa meillä null solmun, joten jälleen voimme raportoida vika.

354
00:26:59,080 --> 00:27:10,260
>> Jos et halua oppia lisää binääripuita,

355
00:27:10,260 --> 00:27:14,420
olemassa koko joukko hauskoja pikku ongelmia, voit tehdä heidän kanssaan.

356
00:27:14,420 --> 00:27:19,450
Ehdotan harjoitellaan piirustuksen pois näistä kaavioiden yksi kerrallaan

357
00:27:19,450 --> 00:27:21,910
ja sen jälkeen läpi kaikki eri vaiheet,

358
00:27:21,910 --> 00:27:25,060
koska tämä tulee super-kätevää

359
00:27:25,060 --> 00:27:27,480
ei vain teet Huffman koodaus ongelma setti

360
00:27:27,480 --> 00:27:29,390
mutta myös tulevaisuudessa kursseja -

361
00:27:29,390 --> 00:27:32,220
vain oppia miten tehdä näitä tietorakenteita ja ajatella läpi ongelmia

362
00:27:32,220 --> 00:27:38,000
kynällä ja paperilla tai, tässä tapauksessa, iPad ja stylus.

363
00:27:38,000 --> 00:27:41,000
>> Tässä vaiheessa kuitenkin aiomme siirtyä tekemään joitakin koodaus käytännössä

364
00:27:41,000 --> 00:27:44,870
ja todella pelata näitä binääripuita ja nähdä.

365
00:27:44,870 --> 00:27:52,150
Aion siirtyä takaisin yli tietokoneeseen.

366
00:27:52,150 --> 00:27:58,480
Tämän osan osa, sen sijaan, että käytetään CS50 Run tai CS50 tilat,

367
00:27:58,480 --> 00:28:01,500
Aion käyttää laitetta.

368
00:28:01,500 --> 00:28:04,950
>> Jälkeen yhdessä Ongelma Set erittely,

369
00:28:04,950 --> 00:28:07,740
Näen, että minun pitäisi avata laitteen

370
00:28:07,740 --> 00:28:11,020
menen Dropbox kansioon, luo kansio nimeltä 7 §,

371
00:28:11,020 --> 00:28:15,730
ja sitten luoda tiedoston nimeltä binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Täällä mennään. Minulla laite jo auki.

373
00:28:22,050 --> 00:28:25,910
Aion vetää ylös terminaali.

374
00:28:25,910 --> 00:28:38,250
Aion mennä Dropbox kansioon, tee hakemistoon section7,

375
00:28:38,250 --> 00:28:42,230
ja nähdä se on täysin tyhjä.

376
00:28:42,230 --> 00:28:48,860
Nyt aion avata binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Selvä. Täällä mennään - tyhjän tiedoston.

378
00:28:51,750 --> 00:28:54,330
>> Mennään takaisin spesifikaation.

379
00:28:54,330 --> 00:28:59,850
Eritelmä pyytää luomaan uudenlaisen määritelmän

380
00:28:59,850 --> 00:29:03,080
varten binääripuu solmu sisältää int arvot -

381
00:29:03,080 --> 00:29:07,110
kuten arvot, joita me veti pois meidän kaavio ennen.

382
00:29:07,110 --> 00:29:11,740
Me aiomme käyttää tätä boilerplate typedef että olemme tehneet täällä

383
00:29:11,740 --> 00:29:14,420
että sinun pitäisi tunnistat Harjoitus 5 -

384
00:29:14,420 --> 00:29:19,190
jos teit hash table tapa valloittaa speller ohjelman.

385
00:29:19,190 --> 00:29:22,540
Sinun tulisi myös tunnistaa sen viime viikon jaksossa

386
00:29:22,540 --> 00:29:23,890
jossa puhuimme linkitettyjä listoja.

387
00:29:23,890 --> 00:29:27,870
Meillä tämä typedef of struct solmu,

388
00:29:27,870 --> 00:29:34,430
ja olemme antaneet tämän struct solmu tämä nimi struct solmu etukäteen

389
00:29:34,430 --> 00:29:39,350
jotta voimme viitata siihen, koska me haluamme olla struct solmu osoittimet

390
00:29:39,350 --> 00:29:45,740
osana struct, mutta olemme silloin ympäröi tätä -

391
00:29:45,740 --> 00:29:47,700
tai pikemminkin, suljettu tätä - typedef

392
00:29:47,700 --> 00:29:54,600
niin, että myöhemmin koodia, voimme viitata tähän struct kuin vain solmun sijasta struct solmu.

393
00:29:54,600 --> 00:30:03,120
>> Tämä tulee olemaan hyvin samanlainen yksittäin-linkitetty lista määritelmä että näimme viime viikolla.

394
00:30:03,120 --> 00:30:20,070
Voit tehdä tämän, haluan vain aloittaa kirjoittamisen boilerplate.

395
00:30:20,070 --> 00:30:23,840
Tiedämme, että meillä on oltava kokonaisluku,

396
00:30:23,840 --> 00:30:32,170
niin me laittaa int arvon, ja sitten sen sijaan, että vain yksi osoitin seuraavaan elementtiin -

397
00:30:32,170 --> 00:30:33,970
kuten teimme yksin-linkitettyjen listojen -

398
00:30:33,970 --> 00:30:38,110
aiomme olla vasemmalle ja oikealle lapselle viitteitä.

399
00:30:38,110 --> 00:30:42,880
Se on melko yksinkertainen liikaa - struct solmu * vasen lapsi;

400
00:30:42,880 --> 00:30:51,190
ja struct solmu * oikea lapsi;. Cool.

401
00:30:51,190 --> 00:30:54,740
Tuo näyttää melko hyvä alku.

402
00:30:54,740 --> 00:30:58,530
Mennään takaisin spesifikaation.

403
00:30:58,530 --> 00:31:05,030
>> Nyt meidän täytyy julistaa maailmanlaajuinen solmu * muuttuja juuri puu.

404
00:31:05,030 --> 00:31:10,590
Me aiomme tehdä tämän maailmanlaajuisen aivan kuten teimme ensimmäinen osoitin meidän linkitetty lista myös maailmanlaajuisesti.

405
00:31:10,590 --> 00:31:12,690
Tämä oli niin, että toiminnot, jotka me kirjoittaa

406
00:31:12,690 --> 00:31:16,180
meillä ei ole pidettävä kulkee ympärillä root -

407
00:31:16,180 --> 00:31:19,620
Vaikka näemme, että jos et halua kirjoittaa näitä toimintoja rekursiivisesti,

408
00:31:19,620 --> 00:31:22,830
se voisi olla parempi olla edes sitä tule noin globaalina ensiksi

409
00:31:22,830 --> 00:31:28,090
vaan alustaa sen paikallisesti omassa päätehtävä.

410
00:31:28,090 --> 00:31:31,960
Mutta teemme sen maailmanlaajuisesti aloittaa.

411
00:31:31,960 --> 00:31:39,920
Jälleen annamme pari tiloja, ja aion julistaa solmuun * root.

412
00:31:39,920 --> 00:31:46,770
Vain varmista, että en jätä tätä alustamattoman, aion asettaa sen yhtä null.

413
00:31:46,770 --> 00:31:52,210
Nyt, päätehtävä - jonka me kirjoittaa todella nopeasti täällä -

414
00:31:52,210 --> 00:32:00,450
int main (int argc, const char * argv []) -

415
00:32:00,450 --> 00:32:10,640
ja aion aloittaa julistamaan minun argv levyjärjestelmän const juuri niin että tiedän

416
00:32:10,640 --> 00:32:14,550
että nämä väitteet ovat väitteitä, että en luultavasti halua muokata.

417
00:32:14,550 --> 00:32:18,390
Jos haluan muuttaa niitä minun pitäisi luultavasti kopioita niistä.

418
00:32:18,390 --> 00:32:21,740
Näet paljon koodia.

419
00:32:21,740 --> 00:32:25,440
Se on hieno kumpaankaan suuntaan. On hienoa jättää se - jätä const jos haluat.

420
00:32:25,440 --> 00:32:28,630
En yleensä laita se vain niin, että muistutan itseäni

421
00:32:28,630 --> 00:32:33,650
 että en luultavasti halua muuttaa näitä väitteitä.

422
00:32:33,650 --> 00:32:39,240
>> Kuten aina, aion sisällyttää tähän return 0 linjan lopussa tärkein.

423
00:32:39,240 --> 00:32:45,730
Täällä, aion alustaa minun juurisolmun.

424
00:32:45,730 --> 00:32:48,900
Koska se on nyt, minulla osoitin, joka on asetettu nollaksi,

425
00:32:48,900 --> 00:32:52,970
joten se on suunnattu mitään.

426
00:32:52,970 --> 00:32:57,480
Jotta todella alkaa rakentaa solmu,

427
00:32:57,480 --> 00:32:59,250
Minun täytyy ensin varata muistia se.

428
00:32:59,250 --> 00:33:05,910
Aion tehdä tekemällä muisti kasaan käyttäen malloc.

429
00:33:05,910 --> 00:33:10,660
Aion asettaa root yhtä tulosta malloc,

430
00:33:10,660 --> 00:33:19,550
ja aion käyttää sizeof operaattori laskea koko solmun.

431
00:33:19,550 --> 00:33:24,990
Syystä, että käytän sizeof solmu toisin kuin vaikkapa

432
00:33:24,990 --> 00:33:37,020
tehdä jotain tällaista - malloc (4 + 4 +4) tai malloc 12 -

433
00:33:37,020 --> 00:33:40,820
on koska haluan koodin olla mahdollisimman yhteensopivia.

434
00:33:40,820 --> 00:33:44,540
Haluan pystyä ottamaan tämän. C tiedostoa, kääntää sen laitteen

435
00:33:44,540 --> 00:33:48,820
ja sitten koota se minun 64-bittinen Mac -

436
00:33:48,820 --> 00:33:52,040
tai täysin eri arkkitehtuuria -

437
00:33:52,040 --> 00:33:54,640
ja haluan tämän kaiken toimimaan samoin.

438
00:33:54,640 --> 00:33:59,510
>> Jos teen oletuksia koko muuttujien -

439
00:33:59,510 --> 00:34:02,070
koko int tai koko osoittimen -

440
00:34:02,070 --> 00:34:06,070
Sitten olen myös tehdä oletuksia erilaisia ​​arkkitehtuureja

441
00:34:06,070 --> 00:34:10,440
johon minun koodi voi menestyksekkäästi kääntää ajettaessa.

442
00:34:10,440 --> 00:34:15,030
Aina käyttää sizeof toisin kuin manuaalisesti summaamalla struct kentät.

443
00:34:15,030 --> 00:34:20,500
Toinen syy on se, että voi olla täyte, että kääntäjä pannaan struct.

444
00:34:20,500 --> 00:34:26,570
Vaikka vain yhteen yksittäiset kentät ei ole jotain, että te yleensä halua tehdä,

445
00:34:26,570 --> 00:34:30,340
niin, poista se rivi.

446
00:34:30,340 --> 00:34:33,090
Nyt todella alustamaan tätä juurisolmu

447
00:34:33,090 --> 00:34:36,489
Aion pitää kytkeä arvot kullekin sen eri aloilla.

448
00:34:36,489 --> 00:34:41,400
Esimerkiksi arvo Tiedän haluan alustaa 7,

449
00:34:41,400 --> 00:34:46,920
ja nyt aion asettaa vasen lapsi on null

450
00:34:46,920 --> 00:34:55,820
ja oikea lapsi myös null. Hienoa!

451
00:34:55,820 --> 00:35:02,670
Olemme tehneet että osa spec.

452
00:35:02,670 --> 00:35:07,390
>> Eritelmä alas alareunassa sivun 3 Joudun luoda kolme solmua -

453
00:35:07,390 --> 00:35:10,600
toinen sisältää 3, joista yksi sisälsi 6, ja yksi, jossa on 9 -

454
00:35:10,600 --> 00:35:14,210
ja sitten lanka niitä niin se näyttää täsmälleen samalta kuin meidän puukaavion

455
00:35:14,210 --> 00:35:17,120
että puhuimme aiemmin.

456
00:35:17,120 --> 00:35:20,450
Tehdään se melko nopeasti täällä.

457
00:35:20,450 --> 00:35:26,270
Näet todella nopeasti, että aion alkaa kirjoittaa joukko päällekkäisiä koodi.

458
00:35:26,270 --> 00:35:32,100
Aion luoda solmuun *, ja aion kutsua sitä kolme.

459
00:35:32,100 --> 00:35:36,000
Aion asettaa se yhtä malloc (sizeof (solmu)).

460
00:35:36,000 --> 00:35:41,070
Aion asettaa kolme> value = 3.

461
00:35:41,070 --> 00:35:54,780
Kolme -> left_child = NULL; kolme -> oikea _child = NULL; samoin.

462
00:35:54,780 --> 00:36:01,150
Se näyttää melko samanlainen alustettaessa root, ja se on juuri

463
00:36:01,150 --> 00:36:05,760
Aion pitää tehdä, jos aloitan alustuksen 6 ja 9 sekä.

464
00:36:05,760 --> 00:36:20,720
Teen sen todella nopeasti täällä - itse asiassa, aion tehdä vähän kopioi ja liitä,

465
00:36:20,720 --> 00:36:46,140
ja varmista, että minä - okei.

466
00:36:46,470 --> 00:37:09,900
 Nyt minulla on kopioitu ja voin mennä eteenpäin ja asettaa tämä vastaa 6.

467
00:37:09,900 --> 00:37:14,670
Voit nähdä, että tämä vie aikaa, ja ei ole super-tehokasta.

468
00:37:14,670 --> 00:37:22,610
Vain vähän, me kirjoittaa funktio, joka tekee tämän meille.

469
00:37:22,610 --> 00:37:32,890
Haluan korvata tätä 9, vaihda, että 6.

470
00:37:32,890 --> 00:37:37,360
>> Nyt meillä on kaikki meidän solmujen luotu ja alustettu.

471
00:37:37,360 --> 00:37:41,200
Meillä myös root asettaa yhtä 7 tai sisältää arvon 7,

472
00:37:41,200 --> 00:37:46,510
meidän solmu, joka sisältää 3, meidän solmu, joka sisältää 6, ja meidän solmu, joka sisältää 9.

473
00:37:46,510 --> 00:37:50,390
Tässä vaiheessa meidän täytyy tehdä, on lanka kaiken ylös.

474
00:37:50,390 --> 00:37:53,020
Syystä alustetaan kaikki viitteitä null on vain niin, että olen varmista, että

475
00:37:53,020 --> 00:37:56,260
Minulla ei ole mitään alustamattoman viitteitä sinne vahingossa.

476
00:37:56,260 --> 00:38:02,290
Ja myös koska tässä vaiheessa, minulla on vain todella yhdistää solmut toisiinsa -

477
00:38:02,290 --> 00:38:04,750
kuin ne, jotka he todella kytketty - Minun ei tarvitse käydä läpi ja tehdä

478
00:38:04,750 --> 00:38:08,240
Varmista, että kaikki nollat ​​ovat siellä oikeissa paikoissa.

479
00:38:08,240 --> 00:38:15,630
>> Alkaen juureen, tiedän että juuren vasemman lapsen on 3.

480
00:38:15,630 --> 00:38:21,250
Tiedän, että root oikeus lapsi on 9.

481
00:38:21,250 --> 00:38:24,880
Sen jälkeen, ainoa lapsi, joka minulla on jäljellä murehtia

482
00:38:24,880 --> 00:38:39,080
on 3: n oikea lapsi, joka on 6.

483
00:38:39,080 --> 00:38:44,670
Tässä vaiheessa kaikki näyttää aika hyvältä.

484
00:38:44,670 --> 00:38:54,210
Me poistaa joitakin näistä linjat.

485
00:38:54,210 --> 00:38:59,540
Nyt kaikki näyttää aika hyvältä.

486
00:38:59,540 --> 00:39:04,240
Mennään takaisin meidän toiveiden ja mitä meidän täytyy tehdä seuraavaksi.

487
00:39:04,240 --> 00:39:07,610
>> Tässä vaiheessa meidän on kirjoittaa toiminto nimeltään "sisältää"

488
00:39:07,610 --> 00:39:14,150
jossa prototyyppi "bool sisältää (int arvo)".

489
00:39:14,150 --> 00:39:17,060
Ja tämä on toiminto tulee palauttaa true

490
00:39:17,060 --> 00:39:21,200
 jos puu huomautti meidän globaali root muuttuja

491
00:39:21,200 --> 00:39:26,950
 sisältää arvon johdetaan funktio ja vääriä toisin.

492
00:39:26,950 --> 00:39:29,000
Mennään eteenpäin ja tehdä sitä.

493
00:39:29,000 --> 00:39:35,380
Tämä tulee olemaan aivan kuten haku, että teimme käsin iPad vain vähän sitten.

494
00:39:35,380 --> 00:39:40,130
Katsotaanpa zoomata takaisin hieman ja selaamalla ylös.

495
00:39:40,130 --> 00:39:43,130
Me aiomme laittaa tämä toiminto oikeutta edellä meidän päätehtävä

496
00:39:43,130 --> 00:39:48,990
niin että meidän ei tarvitse tehdä minkäänlaista prototyyppien.

497
00:39:48,990 --> 00:39:55,960
Joten, bool sisältää (int arvo).

498
00:39:55,960 --> 00:40:00,330
Siellä mennään. On meidän boilerplate ilmoituksen.

499
00:40:00,330 --> 00:40:02,900
Vain varmista, että se kokoaa,

500
00:40:02,900 --> 00:40:06,820
Aion mennä eteenpäin ja vain asettaa se yhtä palauttaa false.

501
00:40:06,820 --> 00:40:09,980
Juuri nyt tämä toiminto vain ei tehdä mitään ja aina kertoa, että

502
00:40:09,980 --> 00:40:14,010
arvo että etsimme ole puussa.

503
00:40:14,010 --> 00:40:16,280
>> Tässä vaiheessa se on luultavasti hyvä ajatus -

504
00:40:16,280 --> 00:40:19,600
koska olemme kirjoittanut koko joukko koodin emmekä ole edes kokeillut testata sitä vielä -

505
00:40:19,600 --> 00:40:22,590
varmista, että se kaikki kokoaa.

506
00:40:22,590 --> 00:40:27,460
On pari asiaa, jotka meidän on tehtävä varmistaa, että tämä todella kääntää.

507
00:40:27,460 --> 00:40:33,530
Ensinnäkin, onko olemme käyttäneet mitään toimintoja kaikissa kirjastoissa, jotka emme ole vielä mukana.

508
00:40:33,530 --> 00:40:37,940
Toimintoja olemme käyttäneet tähän asti ovat malloc,

509
00:40:37,940 --> 00:40:43,310
ja sitten olemme myös tämäntyyppisten - tämä kirjakieleen tyyppinen kutsutaan bool' -

510
00:40:43,310 --> 00:40:45,750
joka sisältyy standardi bool otsikkotiedosto.

511
00:40:45,750 --> 00:40:53,250
Haluamme ehdottomasti sisällyttää standardin bool.h varten bool tyyppi,

512
00:40:53,250 --> 00:40:59,230
ja haluamme myös # include standardin lib.h varten standardin kirjastot

513
00:40:59,230 --> 00:41:03,530
jotka sisältävät malloc, ja ilmainen, ja kaikki tämä.

514
00:41:03,530 --> 00:41:08,660
Joten, loitontaa, aiomme lopettaa.

515
00:41:08,660 --> 00:41:14,190
Kokeillaan ja varmista, että tämä oli tehnyt käännöksen.

516
00:41:14,190 --> 00:41:18,150
Näemme, että se tekee, niin olemme oikealla tiellä.

517
00:41:18,150 --> 00:41:22,990
>> Katsotaanpa avata binary_tree.c uudelleen.

518
00:41:22,990 --> 00:41:34,530
Se kokoaa. Mennään alas ja varmista, että lisäämme muutamia puheluita meidän on toimintomoduuleja -

519
00:41:34,530 --> 00:41:40,130
vain varmista, että se on ihan hyvä.

520
00:41:40,130 --> 00:41:43,170
Esimerkiksi kun teimme hakuja meidän puu aiemmin,

521
00:41:43,170 --> 00:41:48,500
Yritimme etsiä arvot 6, 10 ja 1, ja tiesimme, että 6 oli puu,

522
00:41:48,500 --> 00:41:52,220
10 ei ollut puussa, ja 1 ei ollut puussa joko.

523
00:41:52,220 --> 00:41:57,230
Katsotaanpa käyttää näitä näyte puheluihin tapa selvittää, onko

524
00:41:57,230 --> 00:41:59,880
meidän Sisältää toiminto toimii.

525
00:41:59,880 --> 00:42:05,210
Jotta niin, että aion käyttää printf toimintoa,

526
00:42:05,210 --> 00:42:10,280
ja aiomme tulostaa tuloksen puhelun sisältää.

527
00:42:10,280 --> 00:42:13,280
Aion laittaa merkkijono "sisältää (% d) = koska

528
00:42:13,280 --> 00:42:20,470
 aiomme pistoke arvon että aiomme etsiä,

529
00:42:20,470 --> 00:42:27,130
ja =% s \ n ", ja käyttää sitä meidän muotomerkkijonoa.

530
00:42:27,130 --> 00:42:30,720
Olemme juuri menossa nähdä - kirjaimellisesti tulostaa ruudulla -

531
00:42:30,720 --> 00:42:32,060
mitä näyttää funktiokutsuna.

532
00:42:32,060 --> 00:42:33,580
Tämä ei ole oikeastaan ​​toimintoa puhelun.

533
00:42:33,580 --> 00:42:36,760
 Tämä on vain merkkijono suunniteltu näyttämään funktiokutsuna.

534
00:42:36,760 --> 00:42:41,140
>> Nyt aiomme kytkeä arvot.

535
00:42:41,140 --> 00:42:43,580
Aiomme kokeilla sisältää 6,

536
00:42:43,580 --> 00:42:48,340
ja sitten mitä aiomme tehdä tässä käyttää sitä ternäärisen operaattori.

537
00:42:48,340 --> 00:42:56,340
Katsotaanpa - sisältää 6 - niin, nyt olen sisälsi 6 ja jos sisältää 6 on totta,

538
00:42:56,340 --> 00:43:01,850
merkkijono aiomme lähettää% s paluukutsumäärä

539
00:43:01,850 --> 00:43:04,850
tulee olemaan merkkijonon "tosi".

540
00:43:04,850 --> 00:43:07,690
Katsotaanpa vieritä hieman.

541
00:43:07,690 --> 00:43:16,210
Muuten, haluamme lähettää merkkijonon "vääriä" jos sisältää 6 palaa vääriä.

542
00:43:16,210 --> 00:43:19,730
Tämä on hieman typerä näköinen, mutta ajattelin voisin yhtä hyvin kuvaavat

543
00:43:19,730 --> 00:43:23,780
mitä ternäärinen operaattori näyttää, koska emme ole nähneet sitä jonkin aikaa.

544
00:43:23,780 --> 00:43:27,670
Tämä on mukava, kätevä tapa selvittää, jos meidän Contains toiminto toimii.

545
00:43:27,670 --> 00:43:30,040
Aion siirtyä takaisin yli vasemmalle,

546
00:43:30,040 --> 00:43:39,900
ja aion kopioida ja liittää tämän linjan muutaman kerran.

547
00:43:39,900 --> 00:43:44,910
Se muutti joitakin näistä arvoista ympärillä,

548
00:43:44,910 --> 00:43:59,380
joten tämä tulee olemaan 1, ja tämä tulee olemaan 10.

549
00:43:59,380 --> 00:44:02,480
>> Tässä vaiheessa meillä kiva Contains toimintoa.

550
00:44:02,480 --> 00:44:06,080
Meillä on joitakin testejä, ja näemme, jos tämä kaikki toimii.

551
00:44:06,080 --> 00:44:08,120
Tässä vaiheessa olemme kirjoittaneet hieman koodia.

552
00:44:08,120 --> 00:44:13,160
Aika lopettaa pois ja varmista, että kaikki vielä kokoaa.

553
00:44:13,160 --> 00:44:20,360
Lopeta ulos, ja nyt yritetään tehdä binääripuu uudelleen.

554
00:44:20,360 --> 00:44:22,260
No, näyttää siltä meillä virhe,

555
00:44:22,260 --> 00:44:26,930
ja meillä tämä nimenomaisesti todetaan kirjaston funktion printf.

556
00:44:26,930 --> 00:44:39,350
Se näyttää meidän mennä ja # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
Ja siitä, että kaiken pitäisi laatia. Olemme kaikki hyviä.

558
00:44:45,350 --> 00:44:50,420
Nyt voit kokeilla binääripuu ja katso mitä tapahtuu.

559
00:44:50,420 --> 00:44:53,520
Täällä me olemme,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
ja näemme, että odotimme -

561
00:44:55,190 --> 00:44:56,910
koska emme ole toteutettu sisältää vielä

562
00:44:56,910 --> 00:44:59,800
tai pikemminkin olemme vain laittaa vastineeksi väärä -

563
00:44:59,800 --> 00:45:03,300
näemme, että se on juuri palaamassa vääriä niistä kaikista,

564
00:45:03,300 --> 00:45:06,180
Niin, että kaikki työskentelevät pääosin melko hyvin.

565
00:45:06,180 --> 00:45:11,860
>> Mennään takaisin ja todella toteuttaa sisältää tässä vaiheessa.

566
00:45:11,860 --> 00:45:17,490
Aion vierittää alaspäin, zoomata ja -

567
00:45:17,490 --> 00:45:22,330
Muista, algoritmi jota käytimme oli Aloitimme juurisolmua

568
00:45:22,330 --> 00:45:28,010
ja sitten jokaisessa solmussa että kohtaamme, teemme vertailua,

569
00:45:28,010 --> 00:45:32,380
ja perustuu siihen, että vertailun me joko siirtyä vasemmalle lapsen tai oikealle lapselle.

570
00:45:32,380 --> 00:45:39,670
Tämä on menossa muistuttavat hyvin binäärihakupuu koodi, joka me kirjoitti aikaisemmin aikavälillä.

571
00:45:39,670 --> 00:45:47,810
Kun lähdetään, me tiedämme, että me haluamme pitää kiinni nykyisestä solmuun

572
00:45:47,810 --> 00:45:54,050
että me tarkastelemme, ja nykyinen solmu tulee olemaan alustetaan juurisolmuun.

573
00:45:54,050 --> 00:45:56,260
Ja nyt, me aiomme jatkaa läpi puu,

574
00:45:56,260 --> 00:45:58,140
ja muista, että meidän pysäyttää kunnossa -

575
00:45:58,140 --> 00:46:01,870
 kun me itse työskennellyt läpi esimerkiksi käsin -

576
00:46:01,870 --> 00:46:03,960
oli kun törmäsimme null solmu,

577
00:46:03,960 --> 00:46:05,480
ei kun me katsoimme null lapsi,

578
00:46:05,480 --> 00:46:09,620
vaan kun me todella siirretään solmu puussa

579
00:46:09,620 --> 00:46:12,640
ja totesi, että me olemme null solmussa.

580
00:46:12,640 --> 00:46:20,720
Aiomme toistaa kunnes nyk. ei vastaa null.

581
00:46:20,720 --> 00:46:22,920
Ja mitä me teemme?

582
00:46:22,920 --> 00:46:31,610
Aiomme testata (nyk. -> arvo == arvo),

583
00:46:31,610 --> 00:46:35,160
tiedämme, että olemme todella löytäneet solmu, että etsimme.

584
00:46:35,160 --> 00:46:40,450
Joten tässä, voimme palata totta.

585
00:46:40,450 --> 00:46:49,830
Muussa tapauksessa, haluamme onko arvo on pienempi kuin arvo.

586
00:46:49,830 --> 00:46:53,850
Jos nykyinen solmun arvo on pienempi kuin arvo etsimme,

587
00:46:53,850 --> 00:46:57,280
aiomme siirtyä oikealle.

588
00:46:57,280 --> 00:47:10,600
Joten nyk. = nyk. -> right_child, ja muuten, aiomme siirtyä vasemmalle.

589
00:47:10,600 --> 00:47:17,480
nyk. = nyk. -> left_child;. Melko yksinkertainen.

590
00:47:17,480 --> 00:47:22,830
>> Olet luultavasti tunnistaa silmukka, joka näyttää hyvin samankaltainen tätä alkaen

591
00:47:22,830 --> 00:47:27,580
binäärihakupuu aiemmin aikavälillä, paitsi silloin olimme tekemisissä alhainen, keski ja korkea.

592
00:47:27,580 --> 00:47:30,000
Täällä meillä on vain katsoa käyvän arvon

593
00:47:30,000 --> 00:47:31,930
joten se on mukava ja yksinkertainen.

594
00:47:31,930 --> 00:47:34,960
Tehdään varmista tämä koodi toimii.

595
00:47:34,960 --> 00:47:42,780
Ensinnäkin, varmista, että se kokoaa. Näyttää se.

596
00:47:42,780 --> 00:47:47,920
Yritetään käynnissä se.

597
00:47:47,920 --> 00:47:50,160
Ja todellakin, se tulostaa kaiken odotimme.

598
00:47:50,160 --> 00:47:54,320
Se löytää 6 puussa, ei löydä 10, koska 10 ei puussa,

599
00:47:54,320 --> 00:47:57,740
ja ei löydä 1 joko koska 1 ei myöskään ole puussa.

600
00:47:57,740 --> 00:48:01,420
Cool stuff.

601
00:48:01,420 --> 00:48:04,470
>> Selvä. Mennään takaisin meidän toiveiden ja nähdä mitä seuraavaksi.

602
00:48:04,470 --> 00:48:07,990
Nyt se haluaa lisätä hieman solmut meidän puuhun.

603
00:48:07,990 --> 00:48:11,690
Se haluaa lisätä 5, 2 ja 8, ja varmista, että sisältää koodia

604
00:48:11,690 --> 00:48:13,570
toimii edelleen odotetusti.

605
00:48:13,570 --> 00:48:14,900
Mennään tekemään se.

606
00:48:14,900 --> 00:48:19,430
Tässä vaiheessa, eikä tee se harmittaa kopioi ja liitä uudelleen,

607
00:48:19,430 --> 00:48:23,770
Kirjoitetaan funktio itse luoda solmu.

608
00:48:23,770 --> 00:48:27,740
Jos me selaa aina tärkein, huomaamme, että olemme tehneet tätä

609
00:48:27,740 --> 00:48:31,210
hyvin samankaltaisia ​​koodi uudestaan ​​ja uudestaan ​​aina, että haluamme luoda solmuun.

610
00:48:31,210 --> 00:48:39,540
>> Kirjoitetaan funktio, joka todella rakentaa solmu meille ja palauta se.

611
00:48:39,540 --> 00:48:41,960
Aion kutsua sitä build_node.

612
00:48:41,960 --> 00:48:45,130
Aion rakentaa solmu erityinen arvo.

613
00:48:45,130 --> 00:48:51,040
Zoom täällä.

614
00:48:51,040 --> 00:48:56,600
Ensimmäinen asia aion tehdä todella luovat tilaa solmulle kasaan.

615
00:48:56,600 --> 00:49:05,400
Joten, solmu * n = malloc (sizeof (solmu)), n -> arvo = arvo;

616
00:49:05,400 --> 00:49:14,960
ja sitten täällä, olen juuri menossa alustaa kaikki kentät sopivina arvoihin.

617
00:49:14,960 --> 00:49:22,500
Ja aivan lopussa, palaamme meidän solmu.

618
00:49:22,500 --> 00:49:28,690
Selvä. Yksi asia huomata, että tämä toiminto täällä

619
00:49:28,690 --> 00:49:34,320
aikoo palata osoittimen muistin että on kasa kohdennettu.

620
00:49:34,320 --> 00:49:38,880
Mitä mukavaa tästä on se, että tämä solmu nyt -

621
00:49:38,880 --> 00:49:42,420
Meidän täytyy julistaa sen kasaan, sillä jos me julisti sen pinoon

622
00:49:42,420 --> 00:49:45,050
emme voi tehdä sitä tässä toimivat näin.

623
00:49:45,050 --> 00:49:47,690
Että muisti menisi pois soveltamisalasta

624
00:49:47,690 --> 00:49:51,590
ja olisi pätemätön, jos yritimme käyttää sitä myöhemmin.

625
00:49:51,590 --> 00:49:53,500
Koska olemme julistaa keko-jaettu muisti,

626
00:49:53,500 --> 00:49:55,830
aiomme pitää huolehtia vapauttaa myöhemmin

627
00:49:55,830 --> 00:49:58,530
meidän ohjelma ei vuoda mitään muistia.

628
00:49:58,530 --> 00:50:01,270
Olemme punting että kaikki muu koodi

629
00:50:01,270 --> 00:50:02,880
vain yksinkertaisuuden vuoksi tuolloin,

630
00:50:02,880 --> 00:50:05,610
mutta jos joskus kirjoittaa toiminto, joka näyttää tältä

631
00:50:05,610 --> 00:50:10,370
jossa sinulla - jotkut kutsuvat sitä malloc tai realloc sisällä -

632
00:50:10,370 --> 00:50:14,330
haluat varmistaa, että voit laittaa jonkinlainen kommentti täällä sanotaan,

633
00:50:14,330 --> 00:50:29,970
Hei, te tiedätte, palauttaa keon Kohdistamattomat solmu alustettu läpikulkevien-arvo.

634
00:50:29,970 --> 00:50:33,600
Ja sitten haluat varmistaa, että voit laittaa jonkinlainen huomaa, että sanoo

635
00:50:33,600 --> 00:50:41,720
soittaja on vapautettava takaisin muistiin.

636
00:50:41,720 --> 00:50:45,450
Näin, jos joku joskus menee ja käyttää tätä toimintoa,

637
00:50:45,450 --> 00:50:48,150
he tietävät, että mitä he saavat takaisin tämän tehtävän

638
00:50:48,150 --> 00:50:50,870
jossain vaiheessa täytyy vapauttaa.

639
00:50:50,870 --> 00:50:53,940
>> Olettaen, että kaikki on hyvin ja hyvä täällä,

640
00:50:53,940 --> 00:51:02,300
Voimme mennä alas meidän koodi ja korvaa kaikki nämä rivit täällä

641
00:51:02,300 --> 00:51:05,410
joissa vaaditaan meidän rakentaa solmuun toimintoa.

642
00:51:05,410 --> 00:51:08,170
Tehdään se todella nopeasti.

643
00:51:08,170 --> 00:51:15,840
Yksi osa, että emme aio korvata tämä osa täällä

644
00:51:15,840 --> 00:51:18,520
alaosassa, jossa me itse johdottaa solmut osoittavat toisiinsa,

645
00:51:18,520 --> 00:51:21,030
koska emme voi tehdä meidän tehtävämme.

646
00:51:21,030 --> 00:51:37,400
Mutta tehkäämme root = build_node (7), solmu * Kolme = build_node (3);

647
00:51:37,400 --> 00:51:47,980
solmu * Kuusi = build_node (6), solmu * Yhdeksän = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
Ja nyt, halusimme myös lisätä solmuja -

649
00:51:52,590 --> 00:52:03,530
solmu * Viisi = build_node (5); solmu * Kahdeksan = build_node (8);

650
00:52:03,530 --> 00:52:09,760
ja mikä oli toinen solmu? Katsotaanpa täällä. Halusimme myös lisätä 2 -

651
00:52:09,760 --> 00:52:20,280
solmu * kaksi = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Selvä. Tässä vaiheessa tiedämme, että meillä 7, 3, 9, ja 6

653
00:52:26,850 --> 00:52:30,320
kaikki johdotettu oikein, mutta entä 5, 8, ja 2?

654
00:52:30,320 --> 00:52:33,550
Pitää kaikki oikeassa järjestyksessä,

655
00:52:33,550 --> 00:52:39,230
Tiedämme, että kolme oikeus lapsen 6.

656
00:52:39,230 --> 00:52:40,890
Joten, jos aiomme lisätä 5,

657
00:52:40,890 --> 00:52:46,670
5 kuuluu myös oikeassa reunassa puun joista 3 on juuri,

658
00:52:46,670 --> 00:52:50,440
niin 5 kuuluu kuin vasen lapsi 6.

659
00:52:50,440 --> 00:52:58,650
Voimme tehdä tämän sanomalla, kuusi -> left_child = viisi;

660
00:52:58,650 --> 00:53:10,790
ja sitten 8 kuuluu kuten vasen lapsi 9, joten yhdeksän -> left_child = kahdeksan;

661
00:53:10,790 --> 00:53:22,190
ja sitten 2 on vasen lapsi on 3, joten voimme tehdä sen täällä - sinulle -> left_child = kaksi;.

662
00:53:22,190 --> 00:53:27,730
Jos et ole aivan seuraa yhdessä, että sinun kannattaa piirtää sitä itse.

663
00:53:27,730 --> 00:53:35,660
>> Selvä. Säästetään tätä. Mennään ulos ja varmista, että se kokoaa,

664
00:53:35,660 --> 00:53:40,760
ja sitten voimme lisätä meidän Sisältää puhelut.

665
00:53:40,760 --> 00:53:44,120
Näyttää siltä, ​​että kaikki vielä kokoaa.

666
00:53:44,120 --> 00:53:51,790
Mennään sisään ja lisää joidenkin sisältää puhelut.

667
00:53:51,790 --> 00:53:59,640
Jälleen aion tehdä hieman kopioi ja liitä.

668
00:53:59,640 --> 00:54:15,860
Nyt etsitään 5, 8, ja 2. Selvä.

669
00:54:15,860 --> 00:54:28,330
Tehdään varma, että tämä kaikki näyttää hyvältä vielä. Hienoa! Tallenna ja lopeta.

670
00:54:28,330 --> 00:54:33,220
Nyt merkki, kääntää, ja nyt mennään juosta.

671
00:54:33,220 --> 00:54:37,540
Tuloksista näyttää siltä, ​​että kaikki toimii vain mukava ja hyvin.

672
00:54:37,540 --> 00:54:41,780
Hienoa! Joten nyt meillä meidän on toimintomoduuleja kirjoitettu.

673
00:54:41,780 --> 00:54:46,160
Siirrytään ja alkaa työstää miten lisätä solmut puuhun

674
00:54:46,160 --> 00:54:50,000
sillä, kuten teemme juuri nyt, asiat eivät ole kovin kaunis.

675
00:54:50,000 --> 00:54:52,280
>> Jos menemme takaisin eritelmää,

676
00:54:52,280 --> 00:55:00,540
Se pyytää meitä kirjoittamaan toiminto nimeltään lisätä - jälleen palaamassa bool

677
00:55:00,540 --> 00:55:04,400
varten vai emme voisi todella lisätä solmun puuhun -

678
00:55:04,400 --> 00:55:07,710
ja sitten arvo lisätä puuhun on määritetty

679
00:55:07,710 --> 00:55:11,060
ainoa argumentti meidän insert toimintoa.

680
00:55:11,060 --> 00:55:18,180
Palaamme true jos voisimme todellakin lisätä solmun sisältää arvon puuhun,

681
00:55:18,180 --> 00:55:20,930
mikä tarkoittaa sitä, että yksi oli riittävästi muistia,

682
00:55:20,930 --> 00:55:24,840
ja sitten kaksi, että solmu ei jo puussa, koska -

683
00:55:24,840 --> 00:55:32,170
Muista, emme aio olla päällekkäisiä arvoja puu, vain tehdä asiat yksinkertaisina.

684
00:55:32,170 --> 00:55:35,590
Selvä. Takaisin koodia.

685
00:55:35,590 --> 00:55:44,240
Avaa se. Lähennä vähän, rullaa sitten alaspäin.

686
00:55:44,240 --> 00:55:47,220
Laitetaan insertin toiminnon oikealla yläpuolella sisältää.

687
00:55:47,220 --> 00:55:56,360
Jälleen se tulee olemaan nimeltään bool insert (int arvo).

688
00:55:56,360 --> 00:56:01,840
Anna sille vähän enemmän tilaa, ja sitten, kuten oletus,

689
00:56:01,840 --> 00:56:08,870
Laitetaan vastineeksi false aivan lopussa.

690
00:56:08,870 --> 00:56:22,620
Nyt alas alareunassa, mennään eteenpäin ja sen sijaan käsin rakentaa solmut

691
00:56:22,620 --> 00:56:27,900
Tärkeimpien itseämme ja johdotus heidät osoittamaan toisiaan kuin me teemme,

692
00:56:27,900 --> 00:56:30,600
me luottaa meidän insert toiminto tehdä.

693
00:56:30,600 --> 00:56:35,510
Emme ole riippuvaisia ​​meidän insert toiminto rakentaa koko puun tyhjästä aivan vielä,

694
00:56:35,510 --> 00:56:39,970
vaan saamme eroon näistä linjat - we'll kommentoida näitä rivejä -

695
00:56:39,970 --> 00:56:43,430
että rakentaa solmut 5, 8, ja 2.

696
00:56:43,430 --> 00:56:55,740
Ja sen sijaan, me aseta puhelut meidän insertin toiminta

697
00:56:55,740 --> 00:57:01,280
varmistaa, että joka todella toimii.

698
00:57:01,280 --> 00:57:05,840
Täällä mennään.

699
00:57:05,840 --> 00:57:09,300
>> Nyt olemme kommentoineet näitä rivejä.

700
00:57:09,300 --> 00:57:13,700
Meillä on vain 7, 3, 9, ja 6 meidän puu tässä vaiheessa.

701
00:57:13,700 --> 00:57:18,870
Varmista, että tämä on kaikki työ,

702
00:57:18,870 --> 00:57:25,050
Voimme loitontaa, tekevät binääripuu,

703
00:57:25,050 --> 00:57:30,750
käyttää sitä, ja voimme nähdä, että on nyt kertoo meille, että olemme täysin oikeassa -

704
00:57:30,750 --> 00:57:33,110
5, 8, ja 2 eivät ole enää puussa.

705
00:57:33,110 --> 00:57:37,960
Mene takaisin koodia,

706
00:57:37,960 --> 00:57:41,070
ja miten aiomme lisätä?

707
00:57:41,070 --> 00:57:46,290
Muistakaa mitä teimme, kun olimme todella lisäämällä 5, 8, ja 2 aiemmin.

708
00:57:46,290 --> 00:57:50,100
Soitimme että Plinko peli jossa aloitimme juuresta,

709
00:57:50,100 --> 00:57:52,780
meni alas puun yksi yksitellen

710
00:57:52,780 --> 00:57:54,980
kunnes löysimme sopivan raon,

711
00:57:54,980 --> 00:57:57,570
ja sitten me johdotettu solmussa sopivalla paikalla.

712
00:57:57,570 --> 00:57:59,480
Aiomme tehdä saman.

713
00:57:59,480 --> 00:58:04,070
Tämä on pohjimmiltaan kuin kirjallisesti koodin että käytimme sisältää funktion

714
00:58:04,070 --> 00:58:05,910
löytää paikan, jossa solmun pitäisi olla,

715
00:58:05,910 --> 00:58:10,560
ja sitten me vain lisätä solmuun tuolla.

716
00:58:10,560 --> 00:58:17,000
Aloitetaan näin.

717
00:58:17,000 --> 00:58:24,200
>> Joten meillä on solmu * nyk. = root; olemme juuri menossa seuraamaan sisältää koodia

718
00:58:24,200 --> 00:58:26,850
kunnes huomaamme, että se ei aivan toimi meille.

719
00:58:26,850 --> 00:58:32,390
Aiomme käydä läpi puun, kun nykyinen elementti ei ole nolla,

720
00:58:32,390 --> 00:58:45,280
ja jos huomaamme, että nyk. n arvo on sama arvo, yritämme lisätä -

721
00:58:45,280 --> 00:58:49,600
No, tämä on yksi niistä tapauksista, joissa emme voi oikeastaan ​​lisätä solmun

722
00:58:49,600 --> 00:58:52,730
puuhun, koska tämä tarkoittaa, että meillä on päällekkäisiä arvoa.

723
00:58:52,730 --> 00:58:59,010
Täällä olemme todella palaamassa vääriä.

724
00:58:59,010 --> 00:59:08,440
Nyt, if nyk.: n arvo on pienempi kuin arvo,

725
00:59:08,440 --> 00:59:10,930
Nyt tiedämme, että meidän siirtyä oikealle

726
00:59:10,930 --> 00:59:17,190
 koska arvo kuuluu oikeassa puolessa nyk. puu.

727
00:59:17,190 --> 00:59:30,110
Muuten aiomme siirtyä vasemmalle.

728
00:59:30,110 --> 00:59:37,980
Se on pohjimmiltaan meidän on toimintomoduuleja oikeassa.

729
00:59:37,980 --> 00:59:41,820
>> Tässä vaiheessa, kun olemme valmistuu tänä aikana silmukka,

730
00:59:41,820 --> 00:59:47,350
meidän nyk. osoitin aiotaan osoittaa null

731
00:59:47,350 --> 00:59:51,540
Jos toiminto ei ole jo palannut.

732
00:59:51,540 --> 00:59:58,710
Olemme siis ottaa nyk. paikassa, missä haluamme lisätä uusi solmu.

733
00:59:58,710 --> 01:00:05,210
Mitä on vielä tehtävä on todella rakentaa uuden solmun,

734
01:00:05,210 --> 01:00:08,480
jonka voimme tehdä melko helposti.

735
01:00:08,480 --> 01:00:14,930
Voimme käyttää super kätevä rakentaa solmu funktio,

736
01:00:14,930 --> 01:00:17,210
ja jotain, että emme tee aikaisemmin -

737
01:00:17,210 --> 01:00:21,400
me vain eräänlainen otti itsestäänselvyytenä, mutta nyt teemme vain varmistaa -

738
01:00:21,400 --> 01:00:27,130
me testata varmistaa, että arvo palauttama uusi solmu oli todella

739
01:00:27,130 --> 01:00:33,410
ei null, koska emme halua aloittaa päästä, että muisti jos se on tyhjä.

740
01:00:33,410 --> 01:00:39,910
Voimme testata varmistaa, että uusi solmu ei ole yhtä kuin nolla.

741
01:00:39,910 --> 01:00:42,910
Tai sen sijaan, voimme vain nähdä, jos se todella on nolla,

742
01:00:42,910 --> 01:00:52,120
ja jos se on tyhjä, niin voimme vain palata vääriä aikaisin.

743
01:00:52,120 --> 01:00:59,090
>> Tässä vaiheessa meidän on lanka uuteen solmun asianmukaisen paikalla puussa.

744
01:00:59,090 --> 01:01:03,510
Jos katsomme taaksepäin tärkeimmät ja missä olimme todella johdot arvot ennen,

745
01:01:03,510 --> 01:01:08,470
näemme, että niin teimme sen, kun halusimme laittaa 3 puussa

746
01:01:08,470 --> 01:01:11,750
oli meillä näytetty vasen lapsi juuren.

747
01:01:11,750 --> 01:01:14,920
Kun laitamme 9 puussa, meillä oli saada oikea lapsi juuren.

748
01:01:14,920 --> 01:01:21,030
Meidän täytyi olla osoitin vanhemman pannakseen uuden arvon puuhun.

749
01:01:21,030 --> 01:01:24,430
Rullaat jopa lisätä, että ei aio aivan toimi täällä

750
01:01:24,430 --> 01:01:27,550
koska meillä ei ole vanhemman osoitin.

751
01:01:27,550 --> 01:01:31,650
Mitä halutaan pystyä tekemään on, tässä vaiheessa,

752
01:01:31,650 --> 01:01:37,080
Tarkista vanhemman arvosta ja nähdä - hyvin, Gosh,

753
01:01:37,080 --> 01:01:41,990
jos vanhempi: n arvo on pienempi kuin nykyinen arvo,

754
01:01:41,990 --> 01:01:54,440
sitten vanhemman oikeus lapsen pitäisi olla uuden solmun;

755
01:01:54,440 --> 01:02:07,280
muuten vanhemman vasen lapsi olisi uusi solmu.

756
01:02:07,280 --> 01:02:10,290
Mutta meillä ei ole tätä vanhemman osoitin ihan vielä.

757
01:02:10,290 --> 01:02:15,010
>> Saadakseen sen, olemme todella täytyy seurata sitä kun käymme läpi puun

758
01:02:15,010 --> 01:02:18,440
ja löytää sopiva paikalla meidän silmukan yli.

759
01:02:18,440 --> 01:02:26,840
Voimme tehdä sen siirtymällä takaisin ylös meidän insertin toiminta

760
01:02:26,840 --> 01:02:32,350
ja seuranta toinen osoitin muuttuja nimeltä vanhempi.

761
01:02:32,350 --> 01:02:39,340
Me aiomme asettaa sen yhtä null aluksi,

762
01:02:39,340 --> 01:02:43,640
ja sen jälkeen joka kerta käymme läpi puu,

763
01:02:43,640 --> 01:02:51,540
aiomme asettaa vanhemman osoitin vastaamaan nykyistä osoitin.

764
01:02:51,540 --> 01:02:59,140
Aseta vanhempi vastaa nyk..

765
01:02:59,140 --> 01:03:02,260
Näin joka kerta käymme läpi,

766
01:03:02,260 --> 01:03:05,550
aiomme varmistaa, että nykyinen osoitin muuttuu kasvatetaan

767
01:03:05,550 --> 01:03:12,640
Emoyhtiön osoitin seuraa sitä - vain yksi korkeampi kuin nykyiset osoitin puussa.

768
01:03:12,640 --> 01:03:17,370
Että kaikki näyttää aika hyvältä.

769
01:03:17,370 --> 01:03:22,380
>> Mielestäni yksi asia, että me haluamme muuttaa tämä rakentaa solmu palaa null.

770
01:03:22,380 --> 01:03:25,380
Saadakseen rakentaa solmuun todella onnistuneesti palata null,

771
01:03:25,380 --> 01:03:31,060
meidän täytyy muuttaa, että koodia,

772
01:03:31,060 --> 01:03:37,270
koska täällä, emme koskaan testattu varmistaa, että malloc palasi kelvollinen osoitin.

773
01:03:37,270 --> 01:03:53,390
Joten, jos (n! = NULL), sitten -

774
01:03:53,390 --> 01:03:55,250
jos malloc palautetaan kelvollinen osoitin, niin me alustaa sen;

775
01:03:55,250 --> 01:04:02,540
muuten me vain palata ja jotka päätyvät takaisin null meille.

776
01:04:02,540 --> 01:04:13,050
Nyt kaikki näyttää aika hyvältä. Tehkäämme että tämä todella kokoaa.

777
01:04:13,050 --> 01:04:22,240
Tee binääripuu, ja oi, meillä on joitakin juttuja täällä.

778
01:04:22,240 --> 01:04:29,230
>> Meillä implisiittinen ilmoitus toiminnon rakentaa solmun.

779
01:04:29,230 --> 01:04:31,950
Jälleen nämä kääntäjät, aiomme aloittaa huipulla.

780
01:04:31,950 --> 01:04:36,380
Mitä se täytyy tarkoittaa, että soitan rakentaa solmuun ennen kuin olen itse julisti sen.

781
01:04:36,380 --> 01:04:37,730
Mennään takaisin koodia todella nopeasti.

782
01:04:37,730 --> 01:04:43,510
Selaa alaspäin, ja totta tosiaan, minun insertti toiminto on julistettu

783
01:04:43,510 --> 01:04:47,400
yläpuolella rakentaa solmu funktio,

784
01:04:47,400 --> 01:04:50,070
mutta yritän käyttää rakentaa solmuun sisällä insertin.

785
01:04:50,070 --> 01:05:06,610
Aion mennä ja kopioi - ja liitä rakentaa solmu funktio asti täällä ylhäällä.

786
01:05:06,610 --> 01:05:11,750
Näin toivottavasti se toimii. Annetaan tämän toisen mennä.

787
01:05:11,750 --> 01:05:18,920
Nyt se kaikki kokoaa. Kaikki on hyvin.

788
01:05:18,920 --> 01:05:21,640
>> Mutta tässä vaiheessa, emme ole kutsuttu meidän insert toimintoa.

789
01:05:21,640 --> 01:05:26,510
Tiedämme vain, että se kokoaa, joten mennään sisään ja laittaa puhelut tuumaa

790
01:05:26,510 --> 01:05:28,240
Tehdään se meidän pääasiallinen tehtävä.

791
01:05:28,240 --> 01:05:32,390
Täällä, kommentoi out 5, 8, ja 2,

792
01:05:32,390 --> 01:05:36,680
ja sitten emme johdottaa niitä tänne.

793
01:05:36,680 --> 01:05:41,640
Tehdään muutamia puheluita lisätä,

794
01:05:41,640 --> 01:05:46,440
ja mennään myös käyttää samanlaisia ​​juttuja, että käytimme

795
01:05:46,440 --> 01:05:52,810
kun teimme nämä printf puhelut varmistaa, että kaikki eivät saa asennettu oikein.

796
01:05:52,810 --> 01:06:00,550
Aion kopioida ja liittää,

797
01:06:00,550 --> 01:06:12,450
ja sen sijaan sisältää aiomme tehdä insertin.

798
01:06:12,450 --> 01:06:30,140
Ja sen sijaan 6, 10, ja 1, aiomme käyttää 5, 8, ja 2.

799
01:06:30,140 --> 01:06:37,320
Tämä olisi toivottavasti lisätä 5, 8, ja 2 puuhun.

800
01:06:37,320 --> 01:06:44,050
Kokoa. Kaikki on hyvin. Nyt me todella ajaa ohjelmaamme.

801
01:06:44,050 --> 01:06:47,330
>> Kaikkea palasi vääriä.

802
01:06:47,330 --> 01:06:53,830
Joten, 5, 8, ja 2 ei mene, ja se näyttää Contains eivät löytäneet niitä.

803
01:06:53,830 --> 01:06:58,890
Mitä on tekeillä? Mennään loitontaa.

804
01:06:58,890 --> 01:07:02,160
Ensimmäinen ongelma oli, että insertti tuntui palata vääriä,

805
01:07:02,160 --> 01:07:08,750
ja se näyttää että koska lähdimme paluumatkalle vääriä puhelun

806
01:07:08,750 --> 01:07:14,590
emmekä oikeastaan ​​koskaan palannut totta.

807
01:07:14,590 --> 01:07:17,880
Voimme asettaa, että ylös.

808
01:07:17,880 --> 01:07:25,290
Toinen ongelma on, nyt vaikka teemme - pelastaa tämä, lopeta tätä,

809
01:07:25,290 --> 01:07:34,530
ajaa tekemään uudelleen, on se kääntää, niin suorita se -

810
01:07:34,530 --> 01:07:37,670
näemme, että jotain muuta täällä on tapahtunut.

811
01:07:37,670 --> 01:07:42,980
5, 8, ja 2 olivat vielä koskaan löydetty puussa.

812
01:07:42,980 --> 01:07:44,350
Joten, mitä on tekeillä?

813
01:07:44,350 --> 01:07:45,700
>> Katsotaanpa katsomaan tätä koodia.

814
01:07:45,700 --> 01:07:49,790
Katsotaan jos voimme selvittää tämän.

815
01:07:49,790 --> 01:07:57,940
Aloitamme vanhemman ei ole null.

816
01:07:57,940 --> 01:07:59,510
Asetamme kulloisenkin sama root osoitin,

817
01:07:59,510 --> 01:08:04,280
ja aiomme työskennellä tiemme alas puusta.

818
01:08:04,280 --> 01:08:08,650
Jos nykyinen solmu ei ole nolla, niin tiedämme, että voimme liikkua alas hieman.

819
01:08:08,650 --> 01:08:12,330
Asetimme vanhemman osoitin vastattava nykyistä osoitin,

820
01:08:12,330 --> 01:08:15,420
tarkastetaan arvo - jos arvot ovat samat palasimme vääriä.

821
01:08:15,420 --> 01:08:17,540
Jos arvot ovat vähemmän muutimme oikealle;

822
01:08:17,540 --> 01:08:20,399
muuten, muutimme vasemmalle.

823
01:08:20,399 --> 01:08:24,220
Sitten me rakennamme solmu. Minä suurentaa hieman.

824
01:08:24,220 --> 01:08:31,410
Ja tässä me aiomme yrittää johdottaa arvot olla samat.

825
01:08:31,410 --> 01:08:37,250
Mitä on tekeillä? Katsotaan jos mahdollisesti Valgrind voi antaa meille vihjeen.

826
01:08:37,250 --> 01:08:43,910
>> Haluan käyttää Valgrind vain siksi Valgrind todella tyhjenee nopeasti

827
01:08:43,910 --> 01:08:46,729
ja kertoo onko muisti virheitä.

828
01:08:46,729 --> 01:08:48,300
Kun otamme Valgrind on koodi,

829
01:08:48,300 --> 01:08:55,859
kuten näette oikealla here--Valgrind./binary_tree--and paina enter.

830
01:08:55,859 --> 01:09:03,640
Huomaatte, että meillä ei ole mitään muistikuvaa virhettä, joten se näyttää kaikki on kunnossa toistaiseksi.

831
01:09:03,640 --> 01:09:07,529
Meillä on joitakin muistivuotoja, jonka tiedämme, koska me emme ole

832
01:09:07,529 --> 01:09:08,910
tapahtumassa vapauttaa kaikki meidän solmuja.

833
01:09:08,910 --> 01:09:13,050
Yritetään käynnissä GDB nähdä, mitä todella tapahtuu.

834
01:09:13,050 --> 01:09:20,010
Teemme GDB. / Binary_tree. Se käynnistetty hienosti.

835
01:09:20,010 --> 01:09:23,670
Katsotaanpa asettaa kulmapisteen insertti.

836
01:09:23,670 --> 01:09:28,600
Katsotaanpa juosta.

837
01:09:28,600 --> 01:09:31,200
Näyttää siltä, ​​emme koskaan oikeastaan ​​nimeltään insert.

838
01:09:31,200 --> 01:09:39,410
Näyttää siltä ongelma oli vain, että kun muutin tänne vuonna pääasiassa -

839
01:09:39,410 --> 01:09:44,279
kaikki nämä printf puhelut sisältää -

840
01:09:44,279 --> 01:09:56,430
En ole koskaan oikeastaan ​​muuttunut näiden soittaa insertin.

841
01:09:56,430 --> 01:10:01,660
Nyt antaa sille yrittää. Katsotaanpa koota.

842
01:10:01,660 --> 01:10:09,130
Kaikki näyttää hyvältä siellä. Nyt voit kokeilla sitä, mitä tapahtuu.

843
01:10:09,130 --> 01:10:13,320
Alright! Kaikki näyttää melko hyvä siellä.

844
01:10:13,320 --> 01:10:18,130
>> Viimeinen asia ajatella on, onko mitään reuna tapauksissa tähän lisätään?

845
01:10:18,130 --> 01:10:23,170
Ja näyttää siltä, ​​että hyvin, yksi reuna tapaus, joka on aina mielenkiintoista ajatella

846
01:10:23,170 --> 01:10:26,250
on, mitä tapahtuu, jos puu on tyhjä ja soitat tähän lisätään toiminto?

847
01:10:26,250 --> 01:10:30,330
Toimiiko se? No, katsotaanpa kokeilla sitä.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree. C -

849
01:10:32,110 --> 01:10:35,810
Miten aiomme testata tätä, aiomme mennä alas meidän päätehtävä,

850
01:10:35,810 --> 01:10:41,690
ja kaapeloinnin sijaan nämä solmut näin,

851
01:10:41,690 --> 01:10:56,730
olemme juuri menossa kommentoida ulos koko juttu,

852
01:10:56,730 --> 01:11:02,620
ja johdotuksen sijasta jopa solmut itseämme,

853
01:11:02,620 --> 01:11:09,400
Voimme oikeastaan ​​vain mennä eteenpäin ja poistaa kaikki tämän.

854
01:11:09,400 --> 01:11:17,560
Aiomme tehdä kaiken puhelun lisätä.

855
01:11:17,560 --> 01:11:49,020
Joten, tehkäämme - sijasta 5, 8, ja 2, aiomme lisätä 7, 3, ja 9.

856
01:11:49,020 --> 01:11:58,440
Ja sitten me myös haluamme lisätä 6 samoin.

857
01:11:58,440 --> 01:12:05,190
Tallenna. Lopeta. Tee binääripuu.

858
01:12:05,190 --> 01:12:08,540
Kaikki kokoaa.

859
01:12:08,540 --> 01:12:10,320
Voimme vain ajaa se on ja mitä tapahtuu,

860
01:12:10,320 --> 01:12:12,770
mutta se myös tulee olemaan todella tärkeää varmistaa, että

861
01:12:12,770 --> 01:12:14,740
meillä ei ole mitään muisti virheitä,

862
01:12:14,740 --> 01:12:16,840
sillä tämä on yksi reuna tapauksissa tiedämme.

863
01:12:16,840 --> 01:12:20,150
>> Tehdään varmista, että se toimii hyvin Valgrind,

864
01:12:20,150 --> 01:12:28,310
jonka teemme vain hieman käynnissä Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Se näyttää meillä todellakin on yksi virhe yhdeltä yhteydessä -

866
01:12:31,110 --> 01:12:33,790
meillä on tämä segmentointi vika.

867
01:12:33,790 --> 01:12:36,690
Mitä tapahtui?

868
01:12:36,690 --> 01:12:41,650
Valgrind oikeastaan ​​kertoo meille, missä se on.

869
01:12:41,650 --> 01:12:43,050
Pienennä hieman.

870
01:12:43,050 --> 01:12:46,040
Se näyttää siltä kuin se tapahtuu meidän insert-toiminto,

871
01:12:46,040 --> 01:12:53,420
jossa meillä on virheellinen luku on kooltaan 4: insert, rivi 60.

872
01:12:53,420 --> 01:13:03,590
Mennään takaisin ja nähdä, mitä on tekeillä.

873
01:13:03,590 --> 01:13:05,350
Pienennä todella nopeasti.

874
01:13:05,350 --> 01:13:14,230
Haluan varmistaa, että se ei mene näytön reunaan, jotta voimme nähdä kaiken.

875
01:13:14,230 --> 01:13:18,760
Vedä että hieman. Selvä.

876
01:13:18,760 --> 01:13:35,030
Selaa alaspäin, ja ongelma on juuri tässä.

877
01:13:35,030 --> 01:13:40,120
Mitä tapahtuu, jos saamme alas ja nykyinen solmu on jo tyhjä,

878
01:13:40,120 --> 01:13:44,010
meidän vanhempi solmu on null, niin jos katsomme ylös hyvin alkuun, täällä -

879
01:13:44,010 --> 01:13:47,340
Jos tämä taas silmukka koskaan suorittaa

880
01:13:47,340 --> 01:13:52,330
koska nykyinen arvo on nolla - meidän root on nolla niin nyk. on null -

881
01:13:52,330 --> 01:13:57,810
Sitten meidän vanhempi ei koskaan saa asettaa nyk. tai kelvollisen arvon,

882
01:13:57,810 --> 01:14:00,580
niin, vanhempi myös null.

883
01:14:00,580 --> 01:14:03,700
Meidän täytyy muistaa tarkistaa, että

884
01:14:03,700 --> 01:14:08,750
mennessä saamme tänne, ja alamme päästä vanhemman arvosta.

885
01:14:08,750 --> 01:14:13,190
Joten, mitä tapahtuu? No, jos vanhempi on null -

886
01:14:13,190 --> 01:14:17,990
jos (vanhempi == NULL) - tiedämme, että

887
01:14:17,990 --> 01:14:19,530
ei saa olla mitään puussa.

888
01:14:19,530 --> 01:14:22,030
Meidän täytyy yrittää lisätä sen juureen.

889
01:14:22,030 --> 01:14:32,570
Voimme tehdä sen vain asettamalla root sama uusi solmu.

890
01:14:32,570 --> 01:14:40,010
Sitten tässä vaiheessa, emme oikeastaan ​​halua käydä läpi näitä muita asioita.

891
01:14:40,010 --> 01:14:44,780
Sen sijaan täällä, voimme tehdä joko else-if-else,

892
01:14:44,780 --> 01:14:47,610
tai voisimme yhdistää kaiken tänne muuta,

893
01:14:47,610 --> 01:14:56,300
mutta täällä me vain käyttää muuta ja tehdä niin.

894
01:14:56,300 --> 01:14:59,030
Nyt aiomme testata varmistaa, että vanhempi ei ole nolla

895
01:14:59,030 --> 01:15:02,160
sitä ennen todella yrittää päästä omilla.

896
01:15:02,160 --> 01:15:05,330
Tämä auttaa meitä välttämään segmentointi vika.

897
01:15:05,330 --> 01:15:14,740
Joten me lopettaa, loitontaa, kääntää, juosta.

898
01:15:14,740 --> 01:15:18,130
>> Ei virheitä, mutta meillä on vielä joukko muistivuotoja

899
01:15:18,130 --> 01:15:20,650
koska emme vapauttamaan kaikki meidän solmuja.

900
01:15:20,650 --> 01:15:24,350
Mutta, jos me menemme ylös tänne ja katsomme meidän tuloste,

901
01:15:24,350 --> 01:15:30,880
näemme, että hyvin, näyttää kaikki meidän insertit olivat palaamassa totta, mikä on hyvä.

902
01:15:30,880 --> 01:15:33,050
Insertit ovat kaikki totta,

903
01:15:33,050 --> 01:15:36,670
ja sitten sopiva Sisältää puhelut ovat myös totta.

904
01:15:36,670 --> 01:15:41,510
>> Hyvää työtä! Näyttää olemme onnistuneesti kirjoitettu insertti.

905
01:15:41,510 --> 01:15:47,430
Siinä kaikki olemme tämän viikon Problem Set Specification.

906
01:15:47,430 --> 01:15:51,720
Yksi hauska haaste miettiä, miten te todella mennä

907
01:15:51,720 --> 01:15:55,340
ja vapaa kaikki solmut tämän puu.

908
01:15:55,340 --> 01:15:58,830
Voimme tehdä niin monella eri tavalla,

909
01:15:58,830 --> 01:16:01,930
mutta Jätän että jopa voit kokeilla,

910
01:16:01,930 --> 01:16:06,080
ja hauska haaste, kokeile ja varmista, että voit varmistaa

911
01:16:06,080 --> 01:16:09,490
että tämä Valgrind raportti palauttaa mitään virheitä eikä vuotoja.

912
01:16:09,490 --> 01:16:12,880
>> Onnea tämän viikon Huffman koodaus ongelma set,

913
01:16:12,880 --> 01:16:14,380
ja näemme ensi viikolla!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]