1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Sectie 7] [minder comfortabel]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Harvard University]

3
00:00:04,890 --> 00:00:07,000
[Dit is CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Welkom bij hoofdstuk 7.

5
00:00:09,080 --> 00:00:11,330
Dankzij orkaan Sandy,

6
00:00:11,330 --> 00:00:13,440
plaats van een normale sectie deze week

7
00:00:13,440 --> 00:00:17,650
we doen dit walk-through, via de rubriek van vragen.

8
00:00:17,650 --> 00:00:22,830
Ik ga te volgen, samen met het probleem Set 6-specificatie,

9
00:00:22,830 --> 00:00:25,650
en gaan door alle van de vragen in de

10
00:00:25,650 --> 00:00:27,770
Een deel van de vragen sectie.

11
00:00:27,770 --> 00:00:30,940
Als er vragen zijn,

12
00:00:30,940 --> 00:00:32,960
plaats dan graag deze op CS50 te bespreken.

13
00:00:32,960 --> 00:00:35,480
>> Alright. Laten we beginnen.

14
00:00:35,480 --> 00:00:40,780
Op dit moment ben ik op zoek op pagina 3 van het probleem Set-specificatie.

15
00:00:40,780 --> 00:00:44,110
We gaan eerst beginnen te praten over binaire bomen

16
00:00:44,110 --> 00:00:47,850
aangezien die hebben veel van belang zijn voor problemen van deze week set -

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

18
00:00:49,950 --> 00:00:55,000
Een van de eerste data structuren die we over hadden op CS50 was de array.

19
00:00:55,000 --> 00:01:00,170
Bedenk dat een array een reeks elementen -

20
00:01:00,170 --> 00:01:04,019
alle van hetzelfde type - naast elkaar in het geheugen opgeslagen.

21
00:01:04,019 --> 00:01:14,420
Als ik een integer array die ik kan trekken met behulp van deze boxen-nummers-integers stijl -

22
00:01:14,420 --> 00:01:20,290
Laten we zeggen dat ik 5 in het eerste vak, ik heb 7 in de tweede,

23
00:01:20,290 --> 00:01:27,760
dan heb ik 8, 10 en 20 in de uiteindelijke doos.

24
00:01:27,760 --> 00:01:33,000
Vergeet niet dat de twee echt goede dingen over deze array

25
00:01:33,000 --> 00:01:38,800
zijn dat we deze constante-time toegang tot een bepaald element hebben

26
00:01:38,800 --> 00:01:40,500
 in de array als we weten zijn index.

27
00:01:40,500 --> 00:01:44,670
Bijvoorbeeld, als ik wil het derde element in de array te grijpen -

28
00:01:44,670 --> 00:01:47,870
bij index 2 met behulp van onze zero-based indexeringssysteem -

29
00:01:47,870 --> 00:01:52,220
Ik letterlijk alleen maar een eenvoudige wiskundige berekening uit te voeren,

30
00:01:52,220 --> 00:01:56,170
hop die positie in het array,

31
00:01:56,170 --> 00:01:57,840
trek de 8 dat er wordt opgeslagen,

32
00:01:57,840 --> 00:01:59,260
en ik ben klaar om te gaan.

33
00:01:59,260 --> 00:02:03,350
>> Een van de slechte dingen over deze array - dat hebben we gesproken over

34
00:02:03,350 --> 00:02:05,010
toen bespraken we gelinkte lijsten -

35
00:02:05,010 --> 00:02:09,120
is dat als ik wil een element in te voegen in deze array,

36
00:02:09,120 --> 00:02:11,090
Ik ga te hebben om wat verschuiven rond te doen.

37
00:02:11,090 --> 00:02:12,940
Bijvoorbeeld, deze array hier

38
00:02:12,940 --> 00:02:16,850
is in de gesorteerde volgorde - in oplopende volgorde gesorteerd -

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

40
00:02:19,440 --> 00:02:23,100
maar als ik wil de nummer 9 in te voegen in deze array,

41
00:02:23,100 --> 00:02:27,460
Ik zal moeten bepaalde elementen verschuiven om ruimte te maken.

42
00:02:27,460 --> 00:02:30,440
We kunnen putten dit uit hier.

43
00:02:30,440 --> 00:02:35,650
Ik zal moeten de 5, de 7 verplaatsen en de 8;

44
00:02:35,650 --> 00:02:38,720
maak een gat waar ik zet de 9,

45
00:02:38,720 --> 00:02:45,910
en de 10 en de 20 kan naar rechts van de 9.

46
00:02:45,910 --> 00:02:49,450
Dit is een soort van een pijn omdat in het worst-case scenario -

47
00:02:49,450 --> 00:02:54,350
als we hoeven voegen ofwel aan het begin of aan het einde

48
00:02:54,350 --> 00:02:56,040
van de array, afhankelijk van hoe we het verschuiven -

49
00:02:56,040 --> 00:02:58,850
we kunnen eindigen met alle elementen verschuiven

50
00:02:58,850 --> 00:03:00,750
dat we op dit moment te slaan in de array.

51
00:03:00,750 --> 00:03:03,810
>> Dus, wat was de manier om dit?

52
00:03:03,810 --> 00:03:09,260
De manier om dit was om naar onze linked-lists methode waar -

53
00:03:09,260 --> 00:03:19,820
in plaats van het opslaan van de elementen 5, 7, 8, 10 en 20 alle naast elkaar in het geheugen -

54
00:03:19,820 --> 00:03:25,630
wat we in plaats daarvan deed was ze opslaan soort waar we wilden op te slaan

55
00:03:25,630 --> 00:03:32,470
in deze linked-lists knooppunten die ik tekenen hier, een soort van ad hoc.

56
00:03:32,470 --> 00:03:42,060
En dan gaan we verbonden aan elkaar met behulp van deze volgende tips.

57
00:03:42,060 --> 00:03:44,370
Ik kan een pointer van 5 tot de 7,

58
00:03:44,370 --> 00:03:46,420
een pointer van de 7 de 8,

59
00:03:46,420 --> 00:03:47,770
een pointer van de 8 aan de 10,

60
00:03:47,770 --> 00:03:51,220
en tenslotte een pointer van de 10 tot de 20,

61
00:03:51,220 --> 00:03:54,880
en dan een null pointer op de 20 geeft aan dat er niets meer over.

62
00:03:54,880 --> 00:03:59,690
De trade-off die we hier hebben

63
00:03:59,690 --> 00:04:05,360
is dat nu als we willen de nummer 9 in te voegen in onze gesorteerde lijst,

64
00:04:05,360 --> 00:04:08,270
alles wat we moeten doen is het creëren van een nieuw knooppunt met 9,

65
00:04:08,270 --> 00:04:12,290
draad het op te wijzen naar de juiste plaats,

66
00:04:12,290 --> 00:04:20,630
en dan her-bedrading de 8 naar beneden wijzen op de 9.

67
00:04:20,630 --> 00:04:25,660
Dat is behoorlijk snel, in de veronderstelling weten we precies waar we willen de 9 in te voegen.

68
00:04:25,660 --> 00:04:32,610
Maar de trade-off in ruil voor dit is dat we nu hebben de constante-time toegang verloren

69
00:04:32,610 --> 00:04:36,230
tot een bepaald element in onze datastructuur.

70
00:04:36,230 --> 00:04:40,950
Bijvoorbeeld, als ik wil het vierde element vinden in deze gelinkte lijst,

71
00:04:40,950 --> 00:04:43,510
Ik ga moeten beginnen bij het begin van de lijst

72
00:04:43,510 --> 00:04:48,930
en werk mijn weg door het tellen van knooppunt-voor-knooppunt tot ik de vierde.

73
00:04:48,930 --> 00:04:55,870
>> Met het oog op een betere toegang prestaties dan een gekoppelde lijst te krijgen -

74
00:04:55,870 --> 00:04:59,360
maar behouden ook enkele van de voordelen die we hadden

75
00:04:59,360 --> 00:05:01,800
in termen van het inbrengen-tijd van een gekoppelde lijst -

76
00:05:01,800 --> 00:05:05,750
een binaire boom is gaat nodig hebben om een ​​beetje meer geheugen te gebruiken.

77
00:05:05,750 --> 00:05:11,460
In het bijzonder, in plaats van alleen het hebben van een aanwijzer in een binaire boom node -

78
00:05:11,460 --> 00:05:13,350
zoals de linked-lists knoop doet -

79
00:05:13,350 --> 00:05:16,950
we gaan een tweede pointer toe te voegen aan de binaire boom knooppunt.

80
00:05:16,950 --> 00:05:19,950
In plaats van alleen het hebben van een pointer naar het volgende element,

81
00:05:19,950 --> 00:05:24,420
we gaan een pointer naar een linker kind en een recht kind te hebben.

82
00:05:24,420 --> 00:05:26,560
>> Laten we een tekening maken om te zien hoe dat er daadwerkelijk uitziet.

83
00:05:26,560 --> 00:05:31,350
Nogmaals, ik ga deze dozen en pijlen te gebruiken.

84
00:05:31,350 --> 00:05:37,150
Een binaire boom knooppunt zal beginnen met slechts een simpele doos.

85
00:05:37,150 --> 00:05:40,940
Het gaat om een ​​ruimte voor de waarde hebben,

86
00:05:40,940 --> 00:05:47,280
en dan is het ook gaan om een ​​ruimte voor het linker kind en het recht kind te hebben.

87
00:05:47,280 --> 00:05:49,280
Ik ga hier benoem ze.

88
00:05:49,280 --> 00:05:57,560
We gaan naar links kind hebben, en dan gaan we naar de juiste kind.

89
00:05:57,560 --> 00:05:59,920
Er zijn veel verschillende manieren om dit te doen.

90
00:05:59,920 --> 00:06:02,050
Soms voor ruimte en gemak,

91
00:06:02,050 --> 00:06:06,460
Ik zal echt trek het zoals ik hier doe op de bodem

92
00:06:06,460 --> 00:06:10,910
waar ik ga om de waarde hebben aan de top,

93
00:06:10,910 --> 00:06:14,060
en dan de juiste kind op de bottom-rechts,

94
00:06:14,060 --> 00:06:16,060
en de linker kind op de linksonder.

95
00:06:16,060 --> 00:06:20,250
Terug te gaan naar deze top diagram,

96
00:06:20,250 --> 00:06:22,560
hebben we de waarde aan de top,

97
00:06:22,560 --> 00:06:25,560
dan hebben we de linker-kind pointer, en dan hebben wij het recht-kind pointer.

98
00:06:25,560 --> 00:06:30,110
>> In het Probleem Set specificatie,

99
00:06:30,110 --> 00:06:33,110
we praten over het tekenen van een knooppunt dat een waarde 7 heeft,

100
00:06:33,110 --> 00:06:39,750
en dan van links-kind pointer die nul is, en een rechter-kind pointer die is null.

101
00:06:39,750 --> 00:06:46,040
We kunnen het kapitaal NULL ofwel schrijven in de ruimte voor

102
00:06:46,040 --> 00:06:51,610
zowel de linker kind en het recht kind, of we kunnen trekken deze schuine streep

103
00:06:51,610 --> 00:06:53,750
door elk van de dozen te geven dat null is.

104
00:06:53,750 --> 00:06:57,560
Ik ga doen dat alleen maar omdat dat is eenvoudiger.

105
00:06:57,560 --> 00:07:03,700
Wat u hier ziet zijn twee manieren om diagrammen een zeer eenvoudige binaire boom knooppunt

106
00:07:03,700 --> 00:07:07,960
waar we de waarde 7 en null kind pointers.

107
00:07:07,960 --> 00:07:15,220
>> Het tweede deel van onze specificatie vertelt over hoe met gelinkte lijsten -

108
00:07:15,220 --> 00:07:18,270
vergeet niet, we hadden alleen vast te houden aan het eerste element in een lijst

109
00:07:18,270 --> 00:07:20,270
om de hele lijst herinneren -

110
00:07:20,270 --> 00:07:26,140
en eveneens, met een binaire boom, we hebben alleen vast te houden aan een pointer naar de boom

111
00:07:26,140 --> 00:07:31,120
om de controle over het gehele data structuur te handhaven.

112
00:07:31,120 --> 00:07:36,150
Deze speciale element van de boom heet de root node van de boom.

113
00:07:36,150 --> 00:07:43,360
Bijvoorbeeld, indien een knooppunt - dit knooppunt met de waarde 7

114
00:07:43,360 --> 00:07:45,500
met null links-en rechts-kind pointers -

115
00:07:45,500 --> 00:07:47,360
waren de enige waarde in onze boom,

116
00:07:47,360 --> 00:07:50,390
dan zou dit onze root node zijn.

117
00:07:50,390 --> 00:07:52,240
Het is het begin van onze boom.

118
00:07:52,240 --> 00:07:58,530
We kunnen dit een beetje duidelijker als we eenmaal beginnen met het toevoegen van meer knooppunten aan onze boom.

119
00:07:58,530 --> 00:08:01,510
Laat me trek een nieuwe pagina.

120
00:08:01,510 --> 00:08:05,000
>> Nu gaan we een boom die 7 heeft aan de wortel te trekken,

121
00:08:05,000 --> 00:08:10,920
en 3 binnenzijde van de linker kind, en 9 binnenkant van de rechter kind.

122
00:08:10,920 --> 00:08:13,500
Nogmaals, dit is vrij eenvoudig.

123
00:08:13,500 --> 00:08:26,510
We hebben 7 hebt, trek een knooppunt voor de 3, een knooppunt voor 9,

124
00:08:26,510 --> 00:08:32,150
en ik ga naar links-kind wijzer van 7 om te wijzen op het knooppunt met 3 in te stellen,

125
00:08:32,150 --> 00:08:37,850
en het rechter kind pointer van het knooppunt met 7 tot het knooppunt met 9.

126
00:08:37,850 --> 00:08:42,419
Nu, sinds 3 en 9 geen kinderen,

127
00:08:42,419 --> 00:08:48,500
we gaan al hun kind pointers ingesteld op null zijn.

128
00:08:48,500 --> 00:08:56,060
Hier, de wortel van de boom komt overeen met het knooppunt met het getal 7.

129
00:08:56,060 --> 00:09:02,440
U kunt zien dat als alles wat we hebben is een pointer naar die root node,

130
00:09:02,440 --> 00:09:07,330
kunnen we dan wandelen door onze boom en toegang tot zowel onderliggende knooppunten -

131
00:09:07,330 --> 00:09:10,630
zowel 3 en 9.

132
00:09:10,630 --> 00:09:14,820
Geen behoefte om pointers te behouden om elk knooppunt op de boom.

133
00:09:14,820 --> 00:09:22,080
Alright. Nu gaan we naar een ander knooppunt toe te voegen aan dit schema.

134
00:09:22,080 --> 00:09:25,370
We gaan een knooppunt met 6 toe te voegen,

135
00:09:25,370 --> 00:09:34,140
en we gaan dit toe te voegen als het recht kind van de node met 3.

136
00:09:34,140 --> 00:09:41,850
Om dat te doen, ga ik dat null-pointer te wissen in de 3-knooppunt

137
00:09:41,850 --> 00:09:47,750
en bedrading van het op te wijzen op het knooppunt met 6. Alright.

138
00:09:47,750 --> 00:09:53,800
>> Op dit punt, laten we gaan over een beetje van terminologie.

139
00:09:53,800 --> 00:09:58,230
Om te beginnen, de reden dat dit wordt een binaire boom name

140
00:09:58,230 --> 00:10:00,460
is dat het twee kind pointers heeft.

141
00:10:00,460 --> 00:10:06,020
Er zijn andere soorten van bomen die meer kind pointers hebben.

142
00:10:06,020 --> 00:10:10,930
In het bijzonder, je hebt een 'proberen' in Probleem Set 5.

143
00:10:10,930 --> 00:10:19,310
U zult dat merken in dat proberen, je had 27 verschillende verwijzingen naar verschillende kinderen -

144
00:10:19,310 --> 00:10:22,410
een voor elk van de 26 letters in het alfabet Engels,

145
00:10:22,410 --> 00:10:25,410
en dan de 27e voor de apostrof -

146
00:10:25,410 --> 00:10:28,900
dus, dat is vergelijkbaar met een type boom.

147
00:10:28,900 --> 00:10:34,070
Maar hier, omdat het de binaire, we hebben maar twee kinderen pointers.

148
00:10:34,070 --> 00:10:37,880
>> In aanvulling op deze root node waar we over spraken,

149
00:10:37,880 --> 00:10:41,470
we hebben ook al uitput in deze term 'kind'.

150
00:10:41,470 --> 00:10:44,470
Wat betekent het voor het ene knooppunt naar een kind van een ander knooppunt te zijn?

151
00:10:44,470 --> 00:10:54,060
Het betekent letterlijk dat een kind knooppunt is een kind van een ander knooppunt

152
00:10:54,060 --> 00:10:58,760
indien die andere node heeft een van de onderliggende pointers ingesteld om te wijzen op dat knooppunt.

153
00:10:58,760 --> 00:11:01,230
Om dit in meer concrete termen,

154
00:11:01,230 --> 00:11:11,170
Als 3 aangeduid wordt door een van de onderliggende wijzers van 7 dan 3 is een kind van 7.

155
00:11:11,170 --> 00:11:14,510
Als we te achterhalen wat de kinderen van 7 zijn -

156
00:11:14,510 --> 00:11:18,510
goed, zien we dat 7 een pointer naar 3 en een pointer naar 9 heeft,

157
00:11:18,510 --> 00:11:22,190
zo 9 en 3 zijn de kinderen van 7.

158
00:11:22,190 --> 00:11:26,650
Negen heeft geen kinderen, omdat de kinderen pointers zijn null,

159
00:11:26,650 --> 00:11:30,940
en 3 slechts een kind 6.

160
00:11:30,940 --> 00:11:37,430
Zes heeft ook geen kinderen, omdat haar beide pointers zijn null, waar we op dit moment te trekken.

161
00:11:37,430 --> 00:11:45,010
>> Daarnaast hebben we ook praten over de ouders van een bepaald knooppunt,

162
00:11:45,010 --> 00:11:51,100
en dit is, zoals je zou verwachten, de keerzijde van dit kind beschrijving.

163
00:11:51,100 --> 00:11:58,620
Elk knooppunt heeft slechts een ouder - in plaats van twee zoals je zou verwachten met mensen.

164
00:11:58,620 --> 00:12:03,390
Bijvoorbeeld de ouder van 3 7.

165
00:12:03,390 --> 00:12:10,800
De ouder van 9 is 7 en de ouder van 6 3. Niet veel aan.

166
00:12:10,800 --> 00:12:15,720
We hebben ook wat te praten over grootouders en kleinkinderen,

167
00:12:15,720 --> 00:12:18,210
en meer in het algemeen praten we over de voorouders

168
00:12:18,210 --> 00:12:20,960
en afstammelingen van een bepaald knooppunt.

169
00:12:20,960 --> 00:12:25,710
De stamvader van een knoop - of voorouders, beter gezegd, van een knooppunt -

170
00:12:25,710 --> 00:12:32,730
zijn alle knooppunten die liggen op het pad van de wortel naar dat knooppunt.

171
00:12:32,730 --> 00:12:36,640
Bijvoorbeeld, als ik kijk naar het knooppunt 6,

172
00:12:36,640 --> 00:12:46,430
dan de voorouders zullen zowel 3 en 7.

173
00:12:46,430 --> 00:12:55,310
De voorouders van 9, bijvoorbeeld, zijn - als ik kijk naar het knooppunt 9 -

174
00:12:55,310 --> 00:12:59,990
dan is de voorouder van 9 ligt op slechts 7.

175
00:12:59,990 --> 00:13:01,940
En afstammelingen zijn precies het omgekeerde.

176
00:13:01,940 --> 00:13:05,430
Als ik wil kijken naar alle van de nakomelingen van 7,

177
00:13:05,430 --> 00:13:11,020
dan moet ik om te kijken naar alle knooppunten eronder.

178
00:13:11,020 --> 00:13:16,950
Dus, ik heb 3, 9 en 6 al als nakomelingen van 7.

179
00:13:16,950 --> 00:13:24,170
>> De laatste term die we praten over is deze notie van het zijn een broer of zus.

180
00:13:24,170 --> 00:13:27,980
Broers en zussen - soort van volgende mee op deze familie-termen -

181
00:13:27,980 --> 00:13:33,150
zijn knopen die op hetzelfde niveau in de boom.

182
00:13:33,150 --> 00:13:42,230
Dus, 3 en 9 siblings omdat zij op hetzelfde niveau in de boom.

183
00:13:42,230 --> 00:13:46,190
Ze hebben allebei dezelfde ouder, 7.

184
00:13:46,190 --> 00:13:51,400
De 6 heeft geen broers en zussen omdat 9 heeft geen kinderen.

185
00:13:51,400 --> 00:13:55,540
En 7 heeft geen broers en zussen, want het is de wortel van onze boom,

186
00:13:55,540 --> 00:13:59,010
en er is alleen maar 1 root.

187
00:13:59,010 --> 00:14:02,260
7 tot siblings hebben zou er een knooppunt boven 7 zijn.

188
00:14:02,260 --> 00:14:07,480
Er zou een ouder van 7, waarbij 7 niet langer de wortel van de boom.

189
00:14:07,480 --> 00:14:10,480
Dan is dat nieuwe moedermaatschappij van 7 zou ook een kind te krijgen,

190
00:14:10,480 --> 00:14:16,480
en dat kind zou dan het broertje van 7.

191
00:14:16,480 --> 00:14:21,040
>> Alright. Verder.

192
00:14:21,040 --> 00:14:24,930
Wanneer we onze bespreking van binaire bomen begonnen,

193
00:14:24,930 --> 00:14:28,790
hebben we gesproken over hoe we zouden gaan om ze te gebruiken om

194
00:14:28,790 --> 00:14:32,800
krijgen een voordeel ten opzichte van beide arrays en gelinkte lijsten.

195
00:14:32,800 --> 00:14:37,220
En de manier waarop we dat doen is met deze bestelling eigenschap.

196
00:14:37,220 --> 00:14:41,080
We zeggen dat een binaire boom wordt verwezen, volgens de specificatie,

197
00:14:41,080 --> 00:14:45,740
indien voor iedere knoop in de boom, al zijn nakomelingen links -

198
00:14:45,740 --> 00:14:48,670
de linker kind en alle afstammelingen van de linker kind -

199
00:14:48,670 --> 00:14:54,510
hebben minder waarden en alle knooppunten rechts -

200
00:14:54,510 --> 00:14:57,770
het recht kind en alle nakomelingen het recht kind -

201
00:14:57,770 --> 00:15:02,800
hebben nodes groter is dan de waarde van het huidige knooppunt dat we kijken.

202
00:15:02,800 --> 00:15:07,850
Gewoon voor de eenvoud, gaan we ervan uit dat er helemaal geen dubbele knopen in onze boom.

203
00:15:07,850 --> 00:15:11,180
Bijvoorbeeld, in deze boom we niet van plan om de zaak te behandelen

204
00:15:11,180 --> 00:15:13,680
waar we de waarde 7 aan de wortel

205
00:15:13,680 --> 00:15:16,720
 en dan hebben we ook de waarde 7 elders in de boom.

206
00:15:16,720 --> 00:15:24,390
In dit geval, zult u merken dat deze boom inderdaad besteld.

207
00:15:24,390 --> 00:15:26,510
Wij hebben de waarde 7 bij de wortel.

208
00:15:26,510 --> 00:15:29,720
Alles links van 7 -

209
00:15:29,720 --> 00:15:35,310
als ik hier ongedaan maken van deze kleine merken -

210
00:15:35,310 --> 00:15:40,450
alles links van 7 - de 3 en de 6 -

211
00:15:40,450 --> 00:15:49,410
deze waarden liggen beide op minder dan 7, en alles naar rechts - die net is dit 9 -

212
00:15:49,410 --> 00:15:53,450
groter is dan 7.

213
00:15:53,450 --> 00:15:58,650
>> Dit is niet het enige geordende boom die deze waarden

214
00:15:58,650 --> 00:16:03,120
maar laten we trekken nog een paar van hen.

215
00:16:03,120 --> 00:16:05,030
Er is eigenlijk een hele hoop manieren waarop we dit kunnen doen.

216
00:16:05,030 --> 00:16:09,380
Ik ga een vlugschrift te gebruiken alleen maar om het simpel te houden, waar -

217
00:16:09,380 --> 00:16:11,520
in plaats van het tekenen uit het hele dozen-en-pijlen -

218
00:16:11,520 --> 00:16:14,220
Ik ga gewoon naar de getallen tekenen en pijlen verbinden ze toe te voegen.

219
00:16:14,220 --> 00:16:22,920
Om te beginnen, we zullen gewoon weer schrijven onze oorspronkelijke boom waar we 7, en dan een 3,

220
00:16:22,920 --> 00:16:25,590
en vervolgens 3 similisteen naar rechts om de 6,

221
00:16:25,590 --> 00:16:30,890
en 7 had het recht kind dat was 9.

222
00:16:30,890 --> 00:16:33,860
Alright. Wat is een andere manier dat we deze boom achterlaten?

223
00:16:33,860 --> 00:16:38,800
In plaats van 3 de linker kind van 7,

224
00:16:38,800 --> 00:16:41,360
we ook de 6 als linker kind van 7,

225
00:16:41,360 --> 00:16:44,470
en 3 de linker kind van de 6.

226
00:16:44,470 --> 00:16:48,520
Dat zou er als volgt uitzien boom hier, waar ik heb 7,

227
00:16:48,520 --> 00:16:57,860
dan 6 dan 3 en een 9 rechts.

228
00:16:57,860 --> 00:17:01,490
We hebben evenmin tot 7 als het root node.

229
00:17:01,490 --> 00:17:03,860
We kunnen ook hebben 6 als onze root node.

230
00:17:03,860 --> 00:17:06,470
Hoe zou dat er uit zien?

231
00:17:06,470 --> 00:17:09,230
Als we dit besteld pand te behouden,

232
00:17:09,230 --> 00:17:12,970
alles links van de 6 moet minder dan.

233
00:17:12,970 --> 00:17:16,540
Er is maar een mogelijkheid, en dat is 3.

234
00:17:16,540 --> 00:17:19,869
Maar dan als het recht kind van 6 hebben we twee mogelijkheden.

235
00:17:19,869 --> 00:17:25,380
Ten eerste kunnen we de 7 en de 9,

236
00:17:25,380 --> 00:17:28,850
of we kunnen tekenen - alsof ik op het punt om hier te doen -

237
00:17:28,850 --> 00:17:34,790
waar we de 9 hebben de rechter kind van de 6,

238
00:17:34,790 --> 00:17:39,050
en de 7 als het linker kind van de 9.

239
00:17:39,050 --> 00:17:44,240
>> Nu, 7 en 6 zijn niet de enige mogelijke waarden voor de root.

240
00:17:44,240 --> 00:17:50,200
We konden ook 3 worden aan de wortel.

241
00:17:50,200 --> 00:17:52,240
Wat gebeurt er als 3 is aan de wortel?

242
00:17:52,240 --> 00:17:54,390
Hier liggen de zaken een beetje interessant.

243
00:17:54,390 --> 00:17:58,440
Drie heeft geen waarden die minder dan,

244
00:17:58,440 --> 00:18:02,070
zodat dat hele linkerkant van de boom wordt gewoon naar null zijn.

245
00:18:02,070 --> 00:18:03,230
Er zal niet er iets.

246
00:18:03,230 --> 00:18:07,220
Aan de rechterkant, konden we een lijst dingen in oplopende volgorde.

247
00:18:07,220 --> 00:18:15,530
We zouden 3, dan 6, dan 7, dan 9.

248
00:18:15,530 --> 00:18:26,710
Of kunnen we doen 3, dan 6, dan 9, vervolgens op 7.

249
00:18:26,710 --> 00:18:35,020
Of kunnen we doen op 3 en 7, dan 6, dan 9.

250
00:18:35,020 --> 00:18:40,950
Of, 3, 7 - eigenlijk geen, we kunnen niet meer doen een 7.

251
00:18:40,950 --> 00:18:43,330
Dat is onze een ding daar.

252
00:18:43,330 --> 00:18:54,710
Dat kunnen we doen 9, en vervolgens van de 9 die we kunnen doen 6 en dan op 7.

253
00:18:54,710 --> 00:19:06,980
Of kunnen we doen 3, dan 9, dan 7, en vervolgens 6.

254
00:19:06,980 --> 00:19:12,490
>> Een ding om uw aandacht te vestigen op hier is

255
00:19:12,490 --> 00:19:14,510
dat deze bomen zijn een beetje raar uitzien.

256
00:19:14,510 --> 00:19:17,840
In het bijzonder, als we kijken naar de 4 bomen aan de rechterkant -

257
00:19:17,840 --> 00:19:20,930
Ik zal omcirkelen ze, hier -

258
00:19:20,930 --> 00:19:28,410
deze bomen lijken bijna net zoals een gekoppelde lijst.

259
00:19:28,410 --> 00:19:32,670
Elk knooppunt heeft slechts een kind,

260
00:19:32,670 --> 00:19:38,950
en we hebben geen van deze boomstructuur die we bijvoorbeeld

261
00:19:38,950 --> 00:19:44,720
 in dit ene eenzame boom hier in de linkerbenedenhoek.

262
00:19:44,720 --> 00:19:52,490
Deze bomen zijn eigenlijk genoemd ontaarden binaire bomen,

263
00:19:52,490 --> 00:19:54,170
en we praten over deze meer in de toekomst -

264
00:19:54,170 --> 00:19:56,730
vooral als je gaat naar andere informatica cursussen te volgen.

265
00:19:56,730 --> 00:19:59,670
Deze bomen zijn gedegenereerd.

266
00:19:59,670 --> 00:20:03,780
Ze zijn niet erg nuttig, want, inderdaad, deze structuur leent zich

267
00:20:03,780 --> 00:20:08,060
 de tijden vergelijkbaar met die van een gekoppelde lijst opzoeken.

268
00:20:08,060 --> 00:20:13,050
We krijgen niet om te profiteren van de extra geheugen - deze extra pointer -

269
00:20:13,050 --> 00:20:18,840
omdat onze structuur slecht zijn op deze manier.

270
00:20:18,840 --> 00:20:24,700
In plaats van te gaan en trekken uit de binaire bomen die 9 hebben aan de wortel,

271
00:20:24,700 --> 00:20:27,220
dat is de laatste geval is dat we zouden hebben,

272
00:20:27,220 --> 00:20:32,380
We zijn in plaats daarvan, op dit punt, gaat een beetje over praten andere term

273
00:20:32,380 --> 00:20:36,150
die we gebruiken als we het over bomen, die wordt genoemd de hoogte.

274
00:20:36,150 --> 00:20:45,460
>> De hoogte van een boom is de afstand van de basis naar de meest nabije knooppunt,

275
00:20:45,460 --> 00:20:48,370
of beter gezegd het aantal hops dat je zou moeten maken om

276
00:20:48,370 --> 00:20:53,750
starten vanaf de wortel en dan eindigen op de meest verre node in de boom.

277
00:20:53,750 --> 00:20:57,330
Als we kijken naar een aantal van deze bomen die we hier getekend,

278
00:20:57,330 --> 00:21:07,870
kunnen we dat als we deze boom in de linker hoek en we beginnen op de 3,

279
00:21:07,870 --> 00:21:14,510
dan moeten we een hop om de 6 een tweede stap om de 7 te maken,

280
00:21:14,510 --> 00:21:20,560
en een derde hop om naar de 9.

281
00:21:20,560 --> 00:21:26,120
Dus de hoogte van de boom is 3.

282
00:21:26,120 --> 00:21:30,640
Dat kunnen we doen dezelfde oefening voor de andere bomen geschetst met deze groene,

283
00:21:30,640 --> 00:21:40,100
en we zien dat de hoogte van al deze bomen ook inderdaad 3.

284
00:21:40,100 --> 00:21:45,230
Dat is een deel van wat maakt ontaarde hen -

285
00:21:45,230 --> 00:21:53,750
dat de hoogte slechts een minder dan het aantal knooppunten in de gehele boom.

286
00:21:53,750 --> 00:21:58,400
Als we kijken naar deze andere boom is omringd met rode, anderzijds,

287
00:21:58,400 --> 00:22:03,920
zien we dat de meest afgelegen leaf nodes zijn de 6 en de 9 -

288
00:22:03,920 --> 00:22:06,940
de bladeren zijn die knopen die geen kinderen hebben.

289
00:22:06,940 --> 00:22:11,760
Dus, om om van het hoofdknooppunt hetzij de 6 of 9,

290
00:22:11,760 --> 00:22:17,840
moeten we een hop te maken om naar de 7 en vervolgens een tweede hop om naar de 9,

291
00:22:17,840 --> 00:22:21,240
en ook, om slechts een tweede hop uit de 7 naar de 6.

292
00:22:21,240 --> 00:22:29,080
Dus de hoogte van de boom hier slechts 2.

293
00:22:29,080 --> 00:22:35,330
U kunt terug gaan en doen dat voor alle andere bomen die we eerder besproken

294
00:22:35,330 --> 00:22:37,380
beginnen met de 7 en 6,

295
00:22:37,480 --> 00:22:42,500
en je zult zien dat de hoogte van al die bomen ook 2 is.

296
00:22:42,500 --> 00:22:46,320
>> De reden dat we hebben het over besteld binaire bomen

297
00:22:46,320 --> 00:22:50,250
en waarom ze is cool, want je kunt er doorheen zoeken in

298
00:22:50,250 --> 00:22:53,810
een zeer gelijkaardige manier aan het zoeken over een gesorteerde array.

299
00:22:53,810 --> 00:22:58,720
Dit is waar we praten over het krijgen van die verbeterde lookup tijd

300
00:22:58,720 --> 00:23:02,730
opzichte van de eenvoudige gekoppelde lijst.

301
00:23:02,730 --> 00:23:05,010
Met een gekoppelde lijst - als u een bepaald element te vinden -

302
00:23:05,010 --> 00:23:07,470
je bent in het beste geval gaan om een ​​soort van lineaire zoekopdracht

303
00:23:07,470 --> 00:23:10,920
waar je start aan het begin van een lijst en hop een-voor-een -

304
00:23:10,920 --> 00:23:12,620
een knooppunt van een knooppunt -

305
00:23:12,620 --> 00:23:16,060
door de hele lijst totdat u vinden wat u zoekt.

306
00:23:16,060 --> 00:23:19,440
Overwegende dat, als u een binaire boom die is opgeslagen in deze mooie vorm,

307
00:23:19,440 --> 00:23:23,300
kan je eigenlijk meer van een binair zoeken aan de hand

308
00:23:23,300 --> 00:23:25,160
waar u verdeel en heers

309
00:23:25,160 --> 00:23:29,490
doorzoeken en de passende helft van de boom bij elke stap.

310
00:23:29,490 --> 00:23:32,840
Laten we eens kijken hoe dat werkt.

311
00:23:32,840 --> 00:23:38,850
>> Als we - weer terug te gaan naar onze oorspronkelijke boom -

312
00:23:38,850 --> 00:23:46,710
we beginnen op 7 hebben we 3 links, 9 rechts

313
00:23:46,710 --> 00:23:51,740
en onder de 3 hebben we de 6.

314
00:23:51,740 --> 00:24:01,880
Als we willen zoeken naar de nummer 6 in deze boom, zouden we beginnen bij de wortel.

315
00:24:01,880 --> 00:24:08,910
We zouden vergelijken de waarde die we zoeken, laten we zeggen 6,

316
00:24:08,910 --> 00:24:12,320
om de waarde opgeslagen in het knooppunt dat we op dit moment op zoek bent naar, 7,

317
00:24:12,320 --> 00:24:21,200
6 vinden dat inderdaad minder dan 7, dus we naar links.

318
00:24:21,200 --> 00:24:25,530
Als de waarde van 6 hoger was dan 7, zou plaats hebben we naar rechts.

319
00:24:25,530 --> 00:24:29,770
Omdat we weten dat - als gevolg van de structuur van onze bestelde binaire boom -

320
00:24:29,770 --> 00:24:33,910
alle waarden minder dan 7 zullen worden opgeslagen links van 7,

321
00:24:33,910 --> 00:24:40,520
er is geen noodzaak om zelfs moeite om te kijken door de rechterkant van de boom.

322
00:24:40,520 --> 00:24:43,780
Zodra we naar links en we zijn nu op het knooppunt met 3,

323
00:24:43,780 --> 00:24:48,110
we dat kunnen doen dezelfde vergelijking weer waar we de 3 en de 6.

324
00:24:48,110 --> 00:24:52,430
En vinden we dat, terwijl 6 - de waarde die we zoeken - groter is dan 3,

325
00:24:52,430 --> 00:24:58,580
kunnen we naar de rechterzijde van het knooppunt met 3.

326
00:24:58,580 --> 00:25:02,670
Er is geen links hier, dus we konden hebben genegeerd dat.

327
00:25:02,670 --> 00:25:06,510
Maar we weten alleen dat, want we kijken naar de boom zelf,

328
00:25:06,510 --> 00:25:08,660
en we zien dat de boom geen kinderen heeft.

329
00:25:08,660 --> 00:25:13,640
>> Het is ook vrij eenvoudig op te zoeken 6 in deze boom als we doen het onszelf als mens,

330
00:25:13,640 --> 00:25:16,890
maar laten we mechanisch volgen dit proces als een computer zou doen

331
00:25:16,890 --> 00:25:18,620
om echt te begrijpen het algoritme.

332
00:25:18,620 --> 00:25:26,200
Op dit punt zijn we nu op zoek naar een knooppunt dat 6 bevat,

333
00:25:26,200 --> 00:25:29,180
en we zijn op zoek naar de waarde 6,

334
00:25:29,180 --> 00:25:31,740
ja, inderdaad, we hebben gevonden de juiste node.

335
00:25:31,740 --> 00:25:35,070
We vonden dat de waarde 6 in onze boom, en we kunnen onze zoektocht stoppen.

336
00:25:35,070 --> 00:25:37,330
Op dit punt, afhankelijk van wat er gaande is,

337
00:25:37,330 --> 00:25:41,870
kunnen we zeggen, ja, we hebben de waarde 6 gevonden, bestaat het in onze boom.

338
00:25:41,870 --> 00:25:47,640
Of, als we zijn van plan om een ​​knooppunt te voegen of iets doen, kunnen we dat doen op dit punt.

339
00:25:47,640 --> 00:25:53,010
>> Laten we een paar lookups alleen maar om zien hoe dit werkt.

340
00:25:53,010 --> 00:25:59,390
Laten we eens kijken wat er gebeurt als we zouden proberen en kijken de waarde 10.

341
00:25:59,390 --> 00:26:02,970
Als we kijken op de waarde 10, dan zouden we beginnen bij de wortel.

342
00:26:02,970 --> 00:26:07,070
We willen zien dat 10 groter is dan 7, dus we zouden naar rechts te verplaatsen.

343
00:26:07,070 --> 00:26:13,640
We zouden naar de 9 en 9 vergelijkt de 10 en 9 zien dat inderdaad minder dan 10.

344
00:26:13,640 --> 00:26:16,210
Dus nogmaals, we zouden proberen om naar rechts te verplaatsen.

345
00:26:16,210 --> 00:26:20,350
Maar op dit punt, zouden we merken dat we op een null-knooppunt.

346
00:26:20,350 --> 00:26:23,080
Er is niets daar. Er is niets waar de 10 zou moeten zijn.

347
00:26:23,080 --> 00:26:29,360
Dit is waar we kunnen mislukking rapporteren - dat er inderdaad geen 10 in de boom.

348
00:26:29,360 --> 00:26:35,420
En tot slot, laten we gaan door de zaak waar we proberen op te zoeken 1 in de boom.

349
00:26:35,420 --> 00:26:38,790
Dit is vergelijkbaar met wat er gebeurt als we kijken met 10, behalve in plaats van naar rechts,

350
00:26:38,790 --> 00:26:41,260
we gaan naar links.

351
00:26:41,260 --> 00:26:46,170
We beginnen bij de 7 en zie dat 1 minder dan 7, dus we gaan naar links.

352
00:26:46,170 --> 00:26:51,750
We de 3 en ziet dat 1 minder dan 3, dus opnieuw proberen we naar links.

353
00:26:51,750 --> 00:26:59,080
Op dit punt hebben we een null knooppunt, zodat we weer kunnen melden falen.

354
00:26:59,080 --> 00:27:10,260
>> Als u meer wilt leren over binaire bomen,

355
00:27:10,260 --> 00:27:14,420
Er zijn een hele hoop leuke problemen die je kunt doen met hen.

356
00:27:14,420 --> 00:27:19,450
Ik stel voor het beoefenen van de tekening uit deze diagrammen een-voor-een

357
00:27:19,450 --> 00:27:21,910
en na door alle verschillende stappen,

358
00:27:21,910 --> 00:27:25,060
omdat dit zal komen in superhandige

359
00:27:25,060 --> 00:27:27,480
niet alleen wanneer je doet de Huffman codering probleem set

360
00:27:27,480 --> 00:27:29,390
maar ook in de toekomst cursussen -

361
00:27:29,390 --> 00:27:32,220
gewoon leren hoe te trekken uit deze gegevens structuren en nadenken over de problemen

362
00:27:32,220 --> 00:27:38,000
met pen en papier of, in dit geval, iPad en stylus.

363
00:27:38,000 --> 00:27:41,000
>> Op dit punt echter, gaan we verder met een aantal codering praktijk doen

364
00:27:41,000 --> 00:27:44,870
en eigenlijk spelen met deze binaire bomen en zien.

365
00:27:44,870 --> 00:27:52,150
Ik ga om terug te schakelen naar mijn computer.

366
00:27:52,150 --> 00:27:58,480
Voor dit deel van het hoofdstuk, in plaats van het gebruik van CS50 Run of CS50 Spaces,

367
00:27:58,480 --> 00:28:01,500
Ik ga het apparaat te gebruiken.

368
00:28:01,500 --> 00:28:04,950
>> Na samen met het probleem Set specificatie

369
00:28:04,950 --> 00:28:07,740
Ik zie dat ik moet openen van het apparaat,

370
00:28:07,740 --> 00:28:11,020
ga naar mijn Dropbox-map, maak een map met de naam hoofdstuk 7,

371
00:28:11,020 --> 00:28:15,730
en maak vervolgens een bestand met de naam binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Daar gaan we. Ik heb het apparaat al open.

373
00:28:22,050 --> 00:28:25,910
Ik ga trekken van een terminal.

374
00:28:25,910 --> 00:28:38,250
Ik ga naar de Dropbox-map, maak een map met de naam section7,

375
00:28:38,250 --> 00:28:42,230
en zie het is helemaal leeg.

376
00:28:42,230 --> 00:28:48,860
Nu ga ik het openstellen van binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Alright. Hier gaan we - leeg bestand.

378
00:28:51,750 --> 00:28:54,330
>> Laten we terug gaan naar de specificatie.

379
00:28:54,330 --> 00:28:59,850
De specificatie vraagt ​​om een ​​nieuw type definitie

380
00:28:59,850 --> 00:29:03,080
voor een binaire boom knooppunt met int-waarden -

381
00:29:03,080 --> 00:29:07,110
net als de waarden die we haalde in onze diagrammen voor.

382
00:29:07,110 --> 00:29:11,740
We gaan gebruik maken van deze boilerplate typedef dat we hier gedaan

383
00:29:11,740 --> 00:29:14,420
dat je moet herkennen uit Probleem Set 5 -

384
00:29:14,420 --> 00:29:19,190
als je dat deed de hash table weg van het veroveren van de speller programma.

385
00:29:19,190 --> 00:29:22,540
Je moet ook herkennen van sectie van vorige week

386
00:29:22,540 --> 00:29:23,890
waar hadden we het over gelinkte lijsten.

387
00:29:23,890 --> 00:29:27,870
We hebben dit typedef van een struct knoop,

388
00:29:27,870 --> 00:29:34,430
en we hebben gezien deze struct knoop deze naam van struct knoop vooraf

389
00:29:34,430 --> 00:29:39,350
zodat wij kunnen dan verwijzen naar het sinds we willen struct knoop pointers hebben

390
00:29:39,350 --> 00:29:45,740
als onderdeel van onze struct, maar we hebben dan omringd dit -

391
00:29:45,740 --> 00:29:47,700
of liever ingesloten dit - in een typedef

392
00:29:47,700 --> 00:29:54,600
zodat later in de code kunnen we verwijzen naar deze struct als slechts een knooppunt in plaats van een struct knoop.

393
00:29:54,600 --> 00:30:03,120
>> Dit gaat erg vergelijkbaar met die van de enkelvoudig-gelinkte lijst definitie die we zagen vorige week.

394
00:30:03,120 --> 00:30:20,070
Om dit te doen, laten we beginnen met het schrijven van de standaardtekst.

395
00:30:20,070 --> 00:30:23,840
We weten dat we naar een geheel getal zijn,

396
00:30:23,840 --> 00:30:32,170
dus zetten we in int waarde, en dan in plaats van het hebben van slechts een pointer naar het volgende element -

397
00:30:32,170 --> 00:30:33,970
zoals we deden met enkelvoudig gelinkte lijsten -

398
00:30:33,970 --> 00:30:38,110
we gaan links en rechts kind pointers hebben.

399
00:30:38,110 --> 00:30:42,880
Dat is vrij eenvoudig ook - struct knoop * linker kind;

400
00:30:42,880 --> 00:30:51,190
en struct knoop * rechts kind;. Cool.

401
00:30:51,190 --> 00:30:54,740
Dat ziet eruit als een redelijk goede start.

402
00:30:54,740 --> 00:30:58,530
Laten we terug gaan naar de specificatie.

403
00:30:58,530 --> 00:31:05,030
>> Nu moeten we een globale knooppunt * variabele te declareren voor de wortel van een boom.

404
00:31:05,030 --> 00:31:10,590
We gaan om dit mondiale net zoals we voor het eerst wijzer gemaakt in onze gelinkte lijst ook mondiaal.

405
00:31:10,590 --> 00:31:12,690
Dit was zodat de functies die we schrijven

406
00:31:12,690 --> 00:31:16,180
we niet moeten blijven passeren rond deze wortel -

407
00:31:16,180 --> 00:31:19,620
hoewel we zullen zien dat als je wilt recursief schrijven van deze functies,

408
00:31:19,620 --> 00:31:22,830
het zou beter zijn om zelfs het uitdelen als globale in de eerste plaats

409
00:31:22,830 --> 00:31:28,090
en in plaats daarvan lokaal initialiseren in uw belangrijkste functie.

410
00:31:28,090 --> 00:31:31,960
Maar, we wereldwijd doen het om te beginnen.

411
00:31:31,960 --> 00:31:39,920
Nogmaals, we geven een paar ruimtes, en ik ga naar een knooppunt * wortel te verklaren.

412
00:31:39,920 --> 00:31:46,770
Gewoon om ervoor te zorgen dat ik niet laat dit niet-geïnitialiseerd, ik ga het gelijk aan null.

413
00:31:46,770 --> 00:31:52,210
Nu, in de belangrijkste functie - die we zullen heel snel schrijven hier -

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
en ik ga beginnen aangeven mijn argv array als const gewoon zo dat ik weet

416
00:32:10,640 --> 00:32:14,550
dat deze argumenten zijn argumenten die ik waarschijnlijk niet wilt wijzigen.

417
00:32:14,550 --> 00:32:18,390
Als ik wil ze te wijzigen moet ik waarschijnlijk het maken van kopieën van hen.

418
00:32:18,390 --> 00:32:21,740
Je ziet dit veel in de code.

419
00:32:21,740 --> 00:32:25,440
Het is fijn een van beide manier. Het is fijn om het te laten zoals - de const weglaten als je wilt.

420
00:32:25,440 --> 00:32:28,630
Ik meestal zet het in gewoon zo dat ik me te herinneren

421
00:32:28,630 --> 00:32:33,650
 dat ik waarschijnlijk niet willen deze argumenten aan te passen.

422
00:32:33,650 --> 00:32:39,240
>> Zoals altijd, ik ga deze return 0 lijn aan het eind van de belangrijkste op te nemen.

423
00:32:39,240 --> 00:32:45,730
Hier zal ik initialiseren mijn root node.

424
00:32:45,730 --> 00:32:48,900
Zoals het er nu op dit moment, ik heb een pointer die is ingesteld op null,

425
00:32:48,900 --> 00:32:52,970
dus het is te wijzen op niets.

426
00:32:52,970 --> 00:32:57,480
Om daadwerkelijk beginnen met de bouw van het knooppunt,

427
00:32:57,480 --> 00:32:59,250
Ik moet eerst naar het geheugen voor het toewijzen.

428
00:32:59,250 --> 00:33:05,910
Ik ga dat doen door het maken van het geheugen op de heap malloc gebruikt.

429
00:33:05,910 --> 00:33:10,660
Ik ga wortel gelijk is aan het resultaat van malloc in te stellen,

430
00:33:10,660 --> 00:33:19,550
en ik ga de sizeof operator om de grootte van een knoop berekenen.

431
00:33:19,550 --> 00:33:24,990
De reden dat ik sizeof knooppunt gebruiken in plaats van, laten we zeggen,

432
00:33:24,990 --> 00:33:37,020
het doen van zoiets als dit - malloc (4 + 4 +4) of malloc 12 -

433
00:33:37,020 --> 00:33:40,820
is omdat ik wil dat mijn code om zo compatibel mogelijk.

434
00:33:40,820 --> 00:33:44,540
Ik wil in staat zijn om dit. C bestand te nemen, compileren op het apparaat,

435
00:33:44,540 --> 00:33:48,820
en vervolgens compileren het op mijn 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
of op een heel andere architectuur -

437
00:33:52,040 --> 00:33:54,640
en ik wil dit allemaal op hetzelfde werken.

438
00:33:54,640 --> 00:33:59,510
>> Als ik het maken van veronderstellingen over de omvang van de variabelen -

439
00:33:59,510 --> 00:34:02,070
de grootte van een int of de grootte van een pointer -

440
00:34:02,070 --> 00:34:06,070
dan ben ik ook het maken van veronderstellingen over de soorten architecturen

441
00:34:06,070 --> 00:34:10,440
waarop mijn code met succes kan compileren wanneer deze wordt uitgevoerd.

442
00:34:10,440 --> 00:34:15,030
Altijd sizeof tegenover handmatig optellen van de struct velden.

443
00:34:15,030 --> 00:34:20,500
De andere reden is dat er mogelijk ook padding dat de compiler zet in de struct.

444
00:34:20,500 --> 00:34:26,570
Zelfs alleen het optellen van de afzonderlijke velden is niet iets dat je normaal gesproken wilt doen,

445
00:34:26,570 --> 00:34:30,340
zo, verwijdert u die lijn.

446
00:34:30,340 --> 00:34:33,090
Nu, om echt te initialiseren deze root node,

447
00:34:33,090 --> 00:34:36,489
Ik ga te hebben om aan te sluiten in de waarden voor elk van de verschillende gebieden.

448
00:34:36,489 --> 00:34:41,400
Bijvoorbeeld, voor waarde ik weet dat ik wilt initialiseren tot en met 7,

449
00:34:41,400 --> 00:34:46,920
en voor nu ga ik stel de linker-kind te zijn null

450
00:34:46,920 --> 00:34:55,820
en het recht kind om ook null zijn. Geweldig!

451
00:34:55,820 --> 00:35:02,670
Dat hebben we gedaan een deel van de spec.

452
00:35:02,670 --> 00:35:07,390
>> De specificatie op de bodem van pagina 3 vraagt ​​me om drie meer knooppunten -

453
00:35:07,390 --> 00:35:10,600
een met 3, een met 6 en een met 9 -

454
00:35:10,600 --> 00:35:14,210
en dan bedraden zodat het lijkt precies op onze boomdiagram

455
00:35:14,210 --> 00:35:17,120
dat we aan het praten waren over eerder.

456
00:35:17,120 --> 00:35:20,450
Laten we dat doen vrij snel hier.

457
00:35:20,450 --> 00:35:26,270
Je zult heel snel zien dat ik ga om te beginnen met het schrijven van een heleboel dubbele code.

458
00:35:26,270 --> 00:35:32,100
Ik ga een knooppunt * maken en ik ga noemen drie.

459
00:35:32,100 --> 00:35:36,000
Ik ga je die kunt gelijk aan malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Ik ga drie-> waarde in te stellen = 3.

461
00:35:41,070 --> 00:35:54,780
Drie -> left_child = NULL; drie -> rechts _child = NULL; ook.

462
00:35:54,780 --> 00:36:01,150
Dat ziet er redelijk vergelijkbaar met het initialiseren van de wortel, en dat is precies wat

463
00:36:01,150 --> 00:36:05,760
Ik ga doen als ik begin het initialiseren van 6 en 9 ook.

464
00:36:05,760 --> 00:36:20,720
Ik doe dat heel snel hier - in feite, ik ga een beetje kopiëren en plakken te doen,

465
00:36:20,720 --> 00:36:46,140
en zorg ervoor dat ik - goed.

466
00:36:46,470 --> 00:37:09,900
 Nu, ik heb gekopieerd en ik kan doorgaan en stel deze gelijk aan 6.

467
00:37:09,900 --> 00:37:14,670
Je kunt zien dat dit een tijdje duurt en is niet super-efficiënt.

468
00:37:14,670 --> 00:37:22,610
In slechts een klein beetje, dan schrijven we een functie die dit voor ons zal doen.

469
00:37:22,610 --> 00:37:32,890
Ik wil dit vervangen door een 9, vervang dat met een 6.

470
00:37:32,890 --> 00:37:37,360
>> Nu hebben we al onze nodes aangemaakt en geïnitialiseerd.

471
00:37:37,360 --> 00:37:41,200
We hebben onze wortels te stellen gelijk aan 7, of met de waarde 7,

472
00:37:41,200 --> 00:37:46,510
onze node met 3, onze knooppunt met 6, en onze node met 9.

473
00:37:46,510 --> 00:37:50,390
Op dit punt, alles wat we hoeven te doen is draad alles op.

474
00:37:50,390 --> 00:37:53,020
De reden dat ik geïnitialiseerd alle pointers op null is gewoon zo dat ik er zeker van dat

475
00:37:53,020 --> 00:37:56,260
Ik heb geen geïnitialiseerde pointers daar per ongeluk.

476
00:37:56,260 --> 00:38:02,290
En ook omdat op dit moment heb ik alleen daadwerkelijk de knooppunten met elkaar te verbinden -

477
00:38:02,290 --> 00:38:04,750
aan degenen die ze eigenlijk hebt met - Ik heb geen te gaan door en maken

478
00:38:04,750 --> 00:38:08,240
ervoor dat alle nullen zijn daar op de juiste plaats.

479
00:38:08,240 --> 00:38:15,630
>> Beginnend bij de wortel, weet ik dat de wortel van de linker kind 3.

480
00:38:15,630 --> 00:38:21,250
Ik weet dat de wortel van het recht kind is 9.

481
00:38:21,250 --> 00:38:24,880
Daarna is de enige andere kind dat ik nog heb te maken over

482
00:38:24,880 --> 00:38:39,080
gelijk kind 3, die is 6.

483
00:38:39,080 --> 00:38:44,670
Op dit punt, het ziet er allemaal erg goed.

484
00:38:44,670 --> 00:38:54,210
We verwijderen een aantal van deze lijnen.

485
00:38:54,210 --> 00:38:59,540
Nu is alles ziet er goed uit.

486
00:38:59,540 --> 00:39:04,240
Laten we terug gaan naar onze specificatie en zien wat we moeten gaan doen.

487
00:39:04,240 --> 00:39:07,610
>> Op dit punt moeten we schrijven de naam van een functie 'bevat'

488
00:39:07,610 --> 00:39:14,150
met een prototype van 'bool bevat (int waarde)'.

489
00:39:14,150 --> 00:39:17,060
En deze bevat functie gaat return true

490
00:39:17,060 --> 00:39:21,200
 als de boom door onze wereldwijde wortel variabele wees

491
00:39:21,200 --> 00:39:26,950
 bevat de waarde die in de functie en anders false.

492
00:39:26,950 --> 00:39:29,000
Laten we verder gaan en dat doen.

493
00:39:29,000 --> 00:39:35,380
Dit gaat precies zoals de lookup die we deden met de hand op de iPad gewoon een beetje geleden.

494
00:39:35,380 --> 00:39:40,130
Laten we weer terug in te zoomen een beetje en omhoog.

495
00:39:40,130 --> 00:39:43,130
We gaan deze functie te zetten recht boven onze belangrijkste functie

496
00:39:43,130 --> 00:39:48,990
zodat we niet om elke vorm van prototyping doen.

497
00:39:48,990 --> 00:39:55,960
Dus, bool bevat (int waarde).

498
00:39:55,960 --> 00:40:00,330
Daar gaan we dan. Daar is onze standaardtekst verklaring.

499
00:40:00,330 --> 00:40:02,900
Gewoon om ervoor te zorgen dat dit zal compileren,

500
00:40:02,900 --> 00:40:06,820
Ik ga om verder te gaan en stel het gewoon gelijk aan return false.

501
00:40:06,820 --> 00:40:09,980
Op dit moment deze functie gewoon niet alles doen en altijd melden dat

502
00:40:09,980 --> 00:40:14,010
de waarde die we zoeken is niet in de boom.

503
00:40:14,010 --> 00:40:16,280
>> Op dit punt, is het waarschijnlijk een goed idee -

504
00:40:16,280 --> 00:40:19,600
want we hebben geschreven een hele hoop code en we hebben het niet eens geprobeerd te testen nog -

505
00:40:19,600 --> 00:40:22,590
om ervoor te zorgen dat het allemaal compileert.

506
00:40:22,590 --> 00:40:27,460
Er zijn een paar dingen die we moeten doen om ervoor te zorgen dat dit ook daadwerkelijk zal compileren.

507
00:40:27,460 --> 00:40:33,530
Ten eerste, kijken of we al gebruik van alle functies in een bibliotheken die we nog niet hebben opgenomen.

508
00:40:33,530 --> 00:40:37,940
De functies die we tot nu toe gebruikt zijn malloc,

509
00:40:37,940 --> 00:40:43,310
en dan hebben we ook gebruik gemaakt van dit type - deze niet-standaard type genaamd 'bool' -

510
00:40:43,310 --> 00:40:45,750
die is opgenomen in de standaard bool header-bestand.

511
00:40:45,750 --> 00:40:53,250
We zijn zeker willen standaard bool.h voor de bool type zijn,

512
00:40:53,250 --> 00:40:59,230
en we willen ook # include standaard lib.h voor de standaard bibliotheken

513
00:40:59,230 --> 00:41:03,530
dat onder meer malloc, en vrij, en dat allemaal.

514
00:41:03,530 --> 00:41:08,660
Dus, uitzoomen, we gaan om te stoppen.

515
00:41:08,660 --> 00:41:14,190
Laten we proberen ervoor te zorgen dat dit ook daadwerkelijk het compileren deed.

516
00:41:14,190 --> 00:41:18,150
We zien dat het geval is, dus we zijn op de goede weg.

517
00:41:18,150 --> 00:41:22,990
>> Laten we weer open binary_tree.c.

518
00:41:22,990 --> 00:41:34,530
Het compileert. Laten we naar beneden gaan en ervoor te zorgen dat we een aantal gesprekken te voegen aan onze Bevat functie -

519
00:41:34,530 --> 00:41:40,130
alleen maar om ervoor te zorgen dat dat is allemaal goed en wel.

520
00:41:40,130 --> 00:41:43,170
Bijvoorbeeld, wanneer we een aantal lookups deden in onze boom eerder,

521
00:41:43,170 --> 00:41:48,500
hebben we geprobeerd op te zoeken van de waarden 6, 10, en 1, en we wisten dat 6 was in de boom,

522
00:41:48,500 --> 00:41:52,220
10 was niet in de boom, en 1 was niet in de boom niet.

523
00:41:52,220 --> 00:41:57,230
Laten we gebruik maken van deze monster oproepen als een manier om erachter te komen of

524
00:41:57,230 --> 00:41:59,880
onze Bevat functie werkt.

525
00:41:59,880 --> 00:42:05,210
Om dat te doen, ik ga naar de printf functie te gebruiken,

526
00:42:05,210 --> 00:42:10,280
en we gaan voor het afdrukken van het resultaat van de oproep tot bevat.

527
00:42:10,280 --> 00:42:13,280
Ik ga in een string "bevat (% d) = omdat

528
00:42:13,280 --> 00:42:20,470
 we gaan om aan te sluiten in de waarde die we gaan op zoek naar,

529
00:42:20,470 --> 00:42:27,130
en =% s \ n ", en gebruik dat als onze format string.

530
00:42:27,130 --> 00:42:30,720
We gaan gewoon om te zien - letterlijk uit te printen op het scherm -

531
00:42:30,720 --> 00:42:32,060
wat lijkt op een functie-aanroep.

532
00:42:32,060 --> 00:42:33,580
Dit is niet echt de functie-aanroep.

533
00:42:33,580 --> 00:42:36,760
 Dit is slechts een string ontworpen om eruit als een functie aanroep.

534
00:42:36,760 --> 00:42:41,140
>> Nu gaan we aan te sluiten op de waarden.

535
00:42:41,140 --> 00:42:43,580
We gaan bevat proberen op 6,

536
00:42:43,580 --> 00:42:48,340
en wat gaan we hier doen is gebruik dat ternaire operator.

537
00:42:48,340 --> 00:42:56,340
Laten we eens kijken - bevat 6 - ja, nu ben ik die 6, en indien bevat 6 waar is,

538
00:42:56,340 --> 00:43:01,850
de string die we gaan naar de% s karakter

539
00:43:01,850 --> 00:43:04,850
gaat naar de string "echte" te zijn.

540
00:43:04,850 --> 00:43:07,690
Laten we schuiven dan een beetje.

541
00:43:07,690 --> 00:43:16,210
Buiten dat, we willen versturen van de string "false" als bevat 6 false retourneert.

542
00:43:16,210 --> 00:43:19,730
Dit is een beetje goofy uitziende, maar ik denk dat ik net zo goed illustreren

543
00:43:19,730 --> 00:43:23,780
wat de ternaire operator lijkt omdat we nog niet hebt gezien voor een tijdje.

544
00:43:23,780 --> 00:43:27,670
Dit zal een leuke, handige manier om erachter te komen of onze Bevat functie werkt wel.

545
00:43:27,670 --> 00:43:30,040
Ik ga terug te bladeren naar links,

546
00:43:30,040 --> 00:43:39,900
en ik ga om te kopiëren en deze lijn plak een paar keer.

547
00:43:39,900 --> 00:43:44,910
Veranderde sommige van deze waarden rond,

548
00:43:44,910 --> 00:43:59,380
dus dit zal worden 1, en dit zal worden 10.

549
00:43:59,380 --> 00:44:02,480
>> Op dit punt hebben we een mooi Bevat functie.

550
00:44:02,480 --> 00:44:06,080
We hebben een aantal tests, en we zullen zien of dit allemaal werkt.

551
00:44:06,080 --> 00:44:08,120
Op dit punt hebben we geschreven wat meer code.

552
00:44:08,120 --> 00:44:13,160
Tijd om te stoppen uit en zorg ervoor dat alles nog compileert.

553
00:44:13,160 --> 00:44:20,360
Ga uit, en nu laten we proberen het maken van binaire boom weer.

554
00:44:20,360 --> 00:44:22,260
Nou, het lijkt erop dat we hebben een fout,

555
00:44:22,260 --> 00:44:26,930
En we hebben dit expliciet te verklaren de bibliotheek functie printf.

556
00:44:26,930 --> 00:44:39,350
Het lijkt erop dat we moeten gaan en # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
En met dat, indien alles samen te stellen. We zijn allemaal goed.

558
00:44:45,350 --> 00:44:50,420
Laten we nu eens proberen het uitvoeren van binaire boom en zien wat er gebeurt.

559
00:44:50,420 --> 00:44:53,520
Hier zijn we dan,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
en we zien dat, als we verwacht hadden -

561
00:44:55,190 --> 00:44:56,910
omdat we nog niet geïmplementeerd bevat nog,

562
00:44:56,910 --> 00:44:59,800
of beter gezegd, hebben we gewoon in return false -

563
00:44:59,800 --> 00:45:03,300
zien we dat het gewoon valse terugkeer voor hen allen,

564
00:45:03,300 --> 00:45:06,180
dus dat is alle werkende voor het grootste deel vrij goed.

565
00:45:06,180 --> 00:45:11,860
>> Laten we terug gaan in een daadwerkelijke uitvoering bevat op dit punt.

566
00:45:11,860 --> 00:45:17,490
Ik ga naar beneden scrollen, in te zoomen, en -

567
00:45:17,490 --> 00:45:22,330
vergeet niet dat het algoritme dat we gebruikten was dat we begonnen op de root node

568
00:45:22,330 --> 00:45:28,010
en dan bij elk knooppunt dat we tegenkomen, we doen een vergelijking,

569
00:45:28,010 --> 00:45:32,380
en op basis van die vergelijking we ofwel naar links kind of rechts kind.

570
00:45:32,380 --> 00:45:39,670
Dit gaat erg lijken op de binaire zoekcode die we al eerder schreef in de term.

571
00:45:39,670 --> 00:45:47,810
Als we beginnen, we weten dat we willen vasthouden aan de huidige node

572
00:45:47,810 --> 00:45:54,050
dat we kijken naar, en het huidige knooppunt zal worden geïnitialiseerd naar de root node.

573
00:45:54,050 --> 00:45:56,260
En nu gaan we om door te gaan door middel van de boom,

574
00:45:56,260 --> 00:45:58,140
en vergeet niet dat onze stoppen voorwaarde -

575
00:45:58,140 --> 00:46:01,870
 als we daadwerkelijk gewerkt door het voorbeeld met de hand -

576
00:46:01,870 --> 00:46:03,960
was toen kwamen we een null knooppunt,

577
00:46:03,960 --> 00:46:05,480
niet toen we keken naar een null-kind,

578
00:46:05,480 --> 00:46:09,620
maar wanneer we daadwerkelijk verplaatst naar een knoop in de boom

579
00:46:09,620 --> 00:46:12,640
en vond dat we op een null-knooppunt.

580
00:46:12,640 --> 00:46:20,720
We gaan herhalen totdat huidig ​​is niet gelijk aan null.

581
00:46:20,720 --> 00:46:22,920
En wat gaan we doen?

582
00:46:22,920 --> 00:46:31,610
We gaan om te testen of (huidig ​​-> waarde == waarde),

583
00:46:31,610 --> 00:46:35,160
dan weten we dat we eigenlijk hebben het knooppunt dat we zoeken gevonden.

584
00:46:35,160 --> 00:46:40,450
Dus hier kunnen we return true.

585
00:46:40,450 --> 00:46:49,830
Anders willen we zien of de waarde kleiner is dan de waarde.

586
00:46:49,830 --> 00:46:53,850
Als de huidige knooppunt lager is dan de waarde die we zoeken,

587
00:46:53,850 --> 00:46:57,280
we gaan naar rechts te verplaatsen.

588
00:46:57,280 --> 00:47:10,600
Dus, huidig ​​= huidig ​​-> right_child, en anders gaan we naar links te verplaatsen.

589
00:47:10,600 --> 00:47:17,480
huidig ​​= huidig ​​-> left_child;. Vrij eenvoudig.

590
00:47:17,480 --> 00:47:22,830
>> Misschien herken je de lus die ziet er zeer vergelijkbaar met deze van

591
00:47:22,830 --> 00:47:27,580
binair zoeken eerder in de term, behalve dan hebben we te maken hadden met een laag, midden en hoog.

592
00:47:27,580 --> 00:47:30,000
Hier, we hoeven alleen maar te kijken naar een actuele waarde,

593
00:47:30,000 --> 00:47:31,930
dus het is leuk en eenvoudig.

594
00:47:31,930 --> 00:47:34,960
Laten we ervoor zorgen dat deze code werkt.

595
00:47:34,960 --> 00:47:42,780
Ten eerste, zorg ervoor dat het compileert. Het lijkt erop dat het doet.

596
00:47:42,780 --> 00:47:47,920
Laten we proberen het runnen van het.

597
00:47:47,920 --> 00:47:50,160
En inderdaad, het drukt alles wat we verwacht hadden.

598
00:47:50,160 --> 00:47:54,320
Het vindt 6 in de boom, niet vinden 10, omdat 10 niet in de boom,

599
00:47:54,320 --> 00:47:57,740
en ook niet vinden 1 omdat 1 is ook niet in de boom.

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

601
00:48:01,420 --> 00:48:04,470
>> Alright. Laten we terug gaan naar onze specificatie en te zien wat de toekomst biedt.

602
00:48:04,470 --> 00:48:07,990
Nu wil het wat meer nodes toe te voegen aan onze boom.

603
00:48:07,990 --> 00:48:11,690
Het wil 5, 2, en 8 toe te voegen en te zorgen dat onze code bevat te maken

604
00:48:11,690 --> 00:48:13,570
nog steeds werkt zoals verwacht.

605
00:48:13,570 --> 00:48:14,900
Laten we dat doen.

606
00:48:14,900 --> 00:48:19,430
Op dit punt, dan doet dat irritante kopiëren en plakken weer,

607
00:48:19,430 --> 00:48:23,770
laten we een functie schrijven om daadwerkelijk een knooppunt.

608
00:48:23,770 --> 00:48:27,740
Als we naar beneden scrollen helemaal naar hoofd, zien we dat we al dit doen

609
00:48:27,740 --> 00:48:31,210
zeer vergelijkbaar code over en weer iedere keer dat we willen een knooppunt te creëren.

610
00:48:31,210 --> 00:48:39,540
>> We beginnen met een functie die een node ook daadwerkelijk te bouwen voor ons en terug te sturen.

611
00:48:39,540 --> 00:48:41,960
Ik ga noemen build_node.

612
00:48:41,960 --> 00:48:45,130
Ik ga een knooppunt te bouwen met een bepaalde waarde.

613
00:48:45,130 --> 00:48:51,040
Zoom in hier.

614
00:48:51,040 --> 00:48:56,600
Het eerste wat ik ga doen is eigenlijk ruimte scheppen voor het knooppunt op de heap.

615
00:48:56,600 --> 00:49:05,400
Dus, knoop * n = malloc (sizeof (node)); n -> waarde = waarde;

616
00:49:05,400 --> 00:49:14,960
en dan hier, ik ben gewoon gaan alle van de velden te initialiseren te zijn de juiste waarden.

617
00:49:14,960 --> 00:49:22,500
En helemaal aan het eind, zullen we terug onze node.

618
00:49:22,500 --> 00:49:28,690
Alright. Een ding om op te merken is dat deze functie hier

619
00:49:28,690 --> 00:49:34,320
gaat een pointer terug te keren naar het geheugen dat is heap-toegewezen.

620
00:49:34,320 --> 00:49:38,880
Wat is er leuk aan is, is dat deze knoop nu -

621
00:49:38,880 --> 00:49:42,420
we moeten het verklaren op de heap, want als we verklaard dat op de stapel

622
00:49:42,420 --> 00:49:45,050
zouden we niet in staat zijn om het te doen in deze functie als deze.

623
00:49:45,050 --> 00:49:47,690
Dat geheugen zou gaan van ruimte

624
00:49:47,690 --> 00:49:51,590
en zou zijn ongeldig indien we geprobeerd om toegang te krijgen later.

625
00:49:51,590 --> 00:49:53,500
Aangezien we verklaren heap-toegewezen geheugen,

626
00:49:53,500 --> 00:49:55,830
we zullen moeten zorgen voor het vrijmaken van het later

627
00:49:55,830 --> 00:49:58,530
voor ons programma om niet lekken geen geheugen.

628
00:49:58,530 --> 00:50:01,270
We hebben punteren op die voor al het andere in de code

629
00:50:01,270 --> 00:50:02,880
alleen gemakshalve tegelijkertijd,

630
00:50:02,880 --> 00:50:05,610
maar als je ooit een functie schrijven die er zo uitziet

631
00:50:05,610 --> 00:50:10,370
waar heb je - sommigen noemen het een malloc of realloc binnen -

632
00:50:10,370 --> 00:50:14,330
wilt u ervoor zorgen dat u een soort van reactie zetten hier up die zegt:

633
00:50:14,330 --> 00:50:29,970
hey, je weet wel, geeft een heap-toegewezen knooppunt geïnitialiseerd met de doorrekeningen in waarde.

634
00:50:29,970 --> 00:50:33,600
En dan wilt u ervoor zorgen dat u in een soort briefje dat zegt:

635
00:50:33,600 --> 00:50:41,720
de beller moet bevrijden van de terug-geheugen.

636
00:50:41,720 --> 00:50:45,450
Op die manier, als iemand ooit gaat en maakt gebruik van die functie,

637
00:50:45,450 --> 00:50:48,150
ze weten dat wat ze terug van die functie

638
00:50:48,150 --> 00:50:50,870
op een gegeven moment moeten worden bevrijd.

639
00:50:50,870 --> 00:50:53,940
>> Ervan uitgaande dat alles hier goed en wel,

640
00:50:53,940 --> 00:51:02,300
kunnen we naar beneden gaan in onze code en vervang alle van deze lijnen hier

641
00:51:02,300 --> 00:51:05,410
met oproepen naar onze build knooppunt functie.

642
00:51:05,410 --> 00:51:08,170
Laten we dat doen echt snel.

643
00:51:08,170 --> 00:51:15,840
Het ene deel dat we niet gaan vervangen is dit deel hier beneden

644
00:51:15,840 --> 00:51:18,520
onderaan waar we eigenlijk kabellengte de knooppunten naar elkaar,

645
00:51:18,520 --> 00:51:21,030
want dat kunnen we niet doen in onze functie.

646
00:51:21,030 --> 00:51:37,400
Maar, laten we het doen root = build_node (7); knoop * drie = build_node (3);

647
00:51:37,400 --> 00:51:47,980
knooppunt * zes = build_node (6); knoop * negen = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
En nu, wilden we ook nodes toe te voegen voor -

649
00:51:52,590 --> 00:52:03,530
knooppunt * vijf = build_node (5); knoop * acht = build_node (8);

650
00:52:03,530 --> 00:52:09,760
en wat was het andere knooppunt? Laten we hier zien. We wilden ook nog een 2 -

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

652
00:52:20,280 --> 00:52:26,850
Alright. Op dit punt, weten we dat we de 7, de 3, de 9, en de 6 kreeg

653
00:52:26,850 --> 00:52:30,320
alle bedraad op de juiste wijze, maar hoe zit het met 5, de 8, en de 2?

654
00:52:30,320 --> 00:52:33,550
Om alles te houden in de juiste volgorde,

655
00:52:33,550 --> 00:52:39,230
we weten dat juist kind drie is 6.

656
00:52:39,230 --> 00:52:40,890
Dus, als we gaan naar de 5 toe te voegen,

657
00:52:40,890 --> 00:52:46,670
de 5 behoort ook in de rechterkant van de boom waarvan 3 de wortel,

658
00:52:46,670 --> 00:52:50,440
dus 5 behoort als de linker kind van 6.

659
00:52:50,440 --> 00:52:58,650
We kunnen dit doen door te zeggen, zes -> left_child = vijf;

660
00:52:58,650 --> 00:53:10,790
en dan de 8 behoort als de linker kind van 9, dus negen -> left_child = acht;

661
00:53:10,790 --> 00:53:22,190
en dan 2 is de linker kind van 3, dus we kunnen dat doen hier - thee -> left_child = twee;.

662
00:53:22,190 --> 00:53:27,730
Als je niet helemaal volgen samen met dat, ik stel voor dat je trek het uit jezelf.

663
00:53:27,730 --> 00:53:35,660
>> Alright. Laten we bewaar deze. Laten we naar buiten gaan en ervoor te zorgen dat de samenstelling en het

664
00:53:35,660 --> 00:53:40,760
en dan kunnen we toevoegen aan onze Bevat gesprekken.

665
00:53:40,760 --> 00:53:44,120
Het lijkt erop dat alles nog compileert.

666
00:53:44,120 --> 00:53:51,790
Laten we in en voeg in een aantal bevat gesprekken.

667
00:53:51,790 --> 00:53:59,640
Nogmaals, ik ga een beetje kopiëren en plakken doen.

668
00:53:59,640 --> 00:54:15,860
Nu laten we zoeken naar 5, 8, en 2. Alright.

669
00:54:15,860 --> 00:54:28,330
Laten we ervoor zorgen dat dit alles ziet er nog steeds goed uit. Geweldig! Opslaan en stoppen.

670
00:54:28,330 --> 00:54:33,220
Laten we nu te maken, samen te stellen, en laten we nu lopen.

671
00:54:33,220 --> 00:54:37,540
Uit de resultaten, het lijkt erop dat alles werkt gewoon mooi en goed.

672
00:54:37,540 --> 00:54:41,780
Geweldig! Dus nu hebben we onze bevat functiebouwstenen geschreven.

673
00:54:41,780 --> 00:54:46,160
Laten we verder gaan en beginnen te werken over hoe je nodes in te voegen in de boom

674
00:54:46,160 --> 00:54:50,000
omdat, zoals we doen het nu, dingen zijn niet erg mooi.

675
00:54:50,000 --> 00:54:52,280
>> Als we terug gaan naar de specificatie,

676
00:54:52,280 --> 00:55:00,540
Het vraagt ​​ons om te schrijven een functie genaamd invoegen - nogmaals, het teruggeven van een bool

677
00:55:00,540 --> 00:55:04,400
voor het al dan niet konden we het knooppunt daadwerkelijk in te voegen in de boom -

678
00:55:04,400 --> 00:55:07,710
waarna de waarde in te voegen in de boom is gespecificeerd als

679
00:55:07,710 --> 00:55:11,060
het enige argument om onze insert functie.

680
00:55:11,060 --> 00:55:18,180
We zullen terugkeren waar als we de knoop met waarde inderdaad te voegen in de boom,

681
00:55:18,180 --> 00:55:20,930
wat betekent dat we, een, genoeg geheugen had,

682
00:55:20,930 --> 00:55:24,840
en dan twee, heeft dat knooppunt niet al bestaan ​​in de boom, omdat -

683
00:55:24,840 --> 00:55:32,170
vergeet niet, we niet van plan om dubbele waarden hebben in de boom, alleen maar om dingen eenvoudig.

684
00:55:32,170 --> 00:55:35,590
Alright. Terug naar de code.

685
00:55:35,590 --> 00:55:44,240
Open het. Zoom in een beetje, dan scroll naar beneden.

686
00:55:44,240 --> 00:55:47,220
Laten we de insert-functie rechts boven de bevat.

687
00:55:47,220 --> 00:55:56,360
Nogmaals, het is gaan heten bool insert (int waarde).

688
00:55:56,360 --> 00:56:01,840
Geef het een beetje meer ruimte, en dan, als standaard,

689
00:56:01,840 --> 00:56:08,870
laten we in return false helemaal aan het eind.

690
00:56:08,870 --> 00:56:22,620
Nu op de bodem, we gaan je gang en in plaats van handmatig de bouw van de knooppunten

691
00:56:22,620 --> 00:56:27,900
in de belangrijkste onszelf en bedrading ze te wijzen op elkaar als we aan het doen,

692
00:56:27,900 --> 00:56:30,600
we vertrouwen op onze insert functie om dat te doen.

693
00:56:30,600 --> 00:56:35,510
We zullen niet vertrouwen op onze insert-functie om de hele boom van de grond af op te bouwen gewoon nog niet,

694
00:56:35,510 --> 00:56:39,970
maar we zullen ontdoen van deze lijnen - we zullen de volgende regels toe -

695
00:56:39,970 --> 00:56:43,430
die voortbouwen de knooppunten 5, 8, en 2.

696
00:56:43,430 --> 00:56:55,740
En in plaats daarvan zullen we voegen bellen naar onze insert-functie

697
00:56:55,740 --> 00:57:01,280
om ervoor te zorgen dat dat echt werkt.

698
00:57:01,280 --> 00:57:05,840
Daar gaan we.

699
00:57:05,840 --> 00:57:09,300
>> Nu hebben we commentaar van deze lijnen.

700
00:57:09,300 --> 00:57:13,700
We slechts 7, 3, 9 en 6 in de boom op dit punt.

701
00:57:13,700 --> 00:57:18,870
Om ervoor te zorgen dat dit alles werkt,

702
00:57:18,870 --> 00:57:25,050
kunnen we uit te zoomen, onze binaire boom,

703
00:57:25,050 --> 00:57:30,750
draaien, en we kunnen zien dat bevat nu ons te vertellen dat we helemaal rechts -

704
00:57:30,750 --> 00:57:33,110
5, 8 en 2 niet langer in de boom.

705
00:57:33,110 --> 00:57:37,960
Ga terug in de code,

706
00:57:37,960 --> 00:57:41,070
en hoe gaan we om in te voegen?

707
00:57:41,070 --> 00:57:46,290
Weet je nog wat we deden toen we waren eigenlijk het plaatsen van 5, 8, en 2 eerder.

708
00:57:46,290 --> 00:57:50,100
We speelden dat Plinko spel waar we begonnen aan de wortel,

709
00:57:50,100 --> 00:57:52,780
ging de boom voor een door een

710
00:57:52,780 --> 00:57:54,980
totdat we vonden de gepaste opening,

711
00:57:54,980 --> 00:57:57,570
en dan hebben we vast in de knoop op de juiste plek.

712
00:57:57,570 --> 00:57:59,480
We gaan hetzelfde doen.

713
00:57:59,480 --> 00:58:04,070
Dit is in principe net als het schrijven van de code die we gebruikt in de functie bevat

714
00:58:04,070 --> 00:58:05,910
de plaats waar de knoop moet vinden,

715
00:58:05,910 --> 00:58:10,560
en dan gaan we gewoon naar het knooppunt voegen daar.

716
00:58:10,560 --> 00:58:17,000
Laten we beginnen om dat te doen.

717
00:58:17,000 --> 00:58:24,200
>> Dus hebben we een knoop * huidig ​​= root, we gaan gewoon te houden aan de code bevat

718
00:58:24,200 --> 00:58:26,850
totdat we vinden dat het niet helemaal werkt voor ons.

719
00:58:26,850 --> 00:58:32,390
We gaan om te gaan door de boom, terwijl het huidige element is niet nul,

720
00:58:32,390 --> 00:58:45,280
en als we vinden dat huidig ​​waarde is gelijk aan de waarde die we proberen in te voegen -

721
00:58:45,280 --> 00:58:49,600
goed, dit is een van de gevallen die we konden niet echt steek het knooppunt

722
00:58:49,600 --> 00:58:52,730
in de boom, omdat dit betekent dat we een dubbele waarde.

723
00:58:52,730 --> 00:58:59,010
Hier zijn we echt gaan om terug te keren vals.

724
00:58:59,010 --> 00:59:08,440
Nu else if huidig ​​waarde kleiner is dan de waarde,

725
00:59:08,440 --> 00:59:10,930
Nu weten we dat we naar rechts te verplaatsen

726
00:59:10,930 --> 00:59:17,190
 omdat de waarde hoort in de rechter helft van de huidige boom.

727
00:59:17,190 --> 00:59:30,110
Anders gaan we naar links te verplaatsen.

728
00:59:30,110 --> 00:59:37,980
Dat is eigenlijk onze Bevat functioneren daar.

729
00:59:37,980 --> 00:59:41,820
>> Op dit punt, als we eenmaal hebt voltooid deze while-lus,

730
00:59:41,820 --> 00:59:47,350
onze huidig ​​wijzer zal worden gericht op null

731
00:59:47,350 --> 00:59:51,540
als de functie nog niet teruggekeerd.

732
00:59:51,540 --> 00:59:58,710
We hebben dan ook huidig ​​op de plek waar we willen het nieuwe knooppunt plaatst.

733
00:59:58,710 --> 01:00:05,210
Wat nog gedaan moet worden is om daadwerkelijk bouwen van de nieuwe node,

734
01:00:05,210 --> 01:00:08,480
die we kunnen vrij gemakkelijk te doen.

735
01:00:08,480 --> 01:00:14,930
We kunnen gebruik maken van onze superhandige build knooppunt functie,

736
01:00:14,930 --> 01:00:17,210
en iets dat we niet doen eerder -

737
01:00:17,210 --> 01:00:21,400
we gewoon een soort van vanzelfsprekend vonden, maar nu zullen we doen alleen maar om ervoor te zorgen -

738
01:00:21,400 --> 01:00:27,130
we testen om ervoor te zorgen dat de waarde die wordt geretourneerd door nieuwe knooppunt eigenlijk was

739
01:00:27,130 --> 01:00:33,410
niet null is, omdat we niet willen beginnen met het openen dat het geheugen als het null.

740
01:00:33,410 --> 01:00:39,910
We kunnen testen om ervoor te zorgen dat nieuwe knooppunt niet gelijk is aan nul.

741
01:00:39,910 --> 01:00:42,910
Of in plaats daarvan, kunnen we gewoon zien of het daadwerkelijk nul is,

742
01:00:42,910 --> 01:00:52,120
en als het nul is, dan kunnen we gewoon vroeg return false.

743
01:00:52,120 --> 01:00:59,090
>> Op dit punt moeten we nieuwe knoop draad in de juiste plek in de boom.

744
01:00:59,090 --> 01:01:03,510
Als we terugkijken op de belangrijkste en waar we waren eigenlijk bedrading in waarden voor,

745
01:01:03,510 --> 01:01:08,470
zien we dat de manier waarop we dat deden toen we wilden naar 3 in de boom

746
01:01:08,470 --> 01:01:11,750
was dat we benaderd de linker kind van de wortel.

747
01:01:11,750 --> 01:01:14,920
Wanneer we 9 in de boom, moesten we de juiste kind van de root-toegang.

748
01:01:14,920 --> 01:01:21,030
We moesten een pointer naar de moederverbinding om een ​​nieuwe waarde genomen de boom.

749
01:01:21,030 --> 01:01:24,430
Scrollen een back-up in te voegen, dat is niet van plan om helemaal hier werken

750
01:01:24,430 --> 01:01:27,550
omdat we niet over een parent-pointer.

751
01:01:27,550 --> 01:01:31,650
Wij willen kunnen doen is, op dit punt,

752
01:01:31,650 --> 01:01:37,080
Controleer de ouders waarde en zie - nou ja, goh,

753
01:01:37,080 --> 01:01:41,990
Als de ouder lager is dan de huidige waarde,

754
01:01:41,990 --> 01:01:54,440
dan is de ouder het recht kind moet de nieuwe node te zijn;

755
01:01:54,440 --> 01:02:07,280
anders, moet de ouder de linker kind van de nieuwe node.

756
01:02:07,280 --> 01:02:10,290
Maar, we hebben niet de parent-pointer helemaal nog niet.

757
01:02:10,290 --> 01:02:15,010
>> Om het te krijgen, we echt gaan hebben om het te volgen als we door de boom

758
01:02:15,010 --> 01:02:18,440
en vind de juiste plek in ons lus boven.

759
01:02:18,440 --> 01:02:26,840
We kunnen dat doen door naar een back-up naar de top van onze insert-functie

760
01:02:26,840 --> 01:02:32,350
en het bijhouden van een andere pointer variabele genaamd de ouder.

761
01:02:32,350 --> 01:02:39,340
We gaan in te stellen die gelijk is aan het begin null,

762
01:02:39,340 --> 01:02:43,640
en dan elke keer als we gaan door de boom,

763
01:02:43,640 --> 01:02:51,540
we gaan naar de parent-pointer ingesteld op de huidige cursorpositie te passen.

764
01:02:51,540 --> 01:02:59,140
Stel ouder van huidig.

765
01:02:59,140 --> 01:03:02,260
Op deze manier, elke keer dat we gaan door,

766
01:03:02,260 --> 01:03:05,550
we gaan om ervoor te zorgen dat als de huidige cursorpositie wordt opgehoogd

767
01:03:05,550 --> 01:03:12,640
de ouder wijzer volgt het - net een niveau hoger dan de huidige cursorpositie in de boom.

768
01:03:12,640 --> 01:03:17,370
Dat ziet er allemaal best goed.

769
01:03:17,370 --> 01:03:22,380
>> Ik denk dat het een ding dat we willen stellen is dit te bouwen knooppunt terug null.

770
01:03:22,380 --> 01:03:25,380
Om te krijgen op te bouwen knooppunt om daadwerkelijk met succes terug te keren null,

771
01:03:25,380 --> 01:03:31,060
we moeten die code te wijzigen,

772
01:03:31,060 --> 01:03:37,270
want hier hebben we nooit getest om ervoor te zorgen dat malloc een geldige pointer terug.

773
01:03:37,270 --> 01:03:53,390
Dus als (n = NULL's), dan -

774
01:03:53,390 --> 01:03:55,250
als malloc terug een geldige pointer, dan zullen wij deze initialiseren;

775
01:03:55,250 --> 01:04:02,540
anders, zullen we gewoon terug en dat zal uiteindelijk terugkeren null voor ons.

776
01:04:02,540 --> 01:04:13,050
Nu zijn alle ziet er goed uit. Laten we ervoor zorgen dat dit eigenlijk compileert.

777
01:04:13,050 --> 01:04:22,240
Maak binaire boom, en oh, we hebben een aantal dingen aan de hand.

778
01:04:22,240 --> 01:04:29,230
>> We hebben een impliciete verklaring van de functie op te bouwen knooppunt.

779
01:04:29,230 --> 01:04:31,950
Nogmaals, met deze compilers, gaan we beginnen aan de top.

780
01:04:31,950 --> 01:04:36,380
Wat dat moet betekenen dat ik bel bouwen knooppunt voor ik heb eigenlijk verklaard.

781
01:04:36,380 --> 01:04:37,730
Laten we terug gaan naar de code heel snel.

782
01:04:37,730 --> 01:04:43,510
Scroll naar beneden, en ja hoor, mijn insert-functie wordt verklaard

783
01:04:43,510 --> 01:04:47,400
boven de build knooppunt functie,

784
01:04:47,400 --> 01:04:50,070
maar ik probeer te gebruiken node binnenkant van insert.

785
01:04:50,070 --> 01:05:06,610
Ik ga naar binnen en kopiëren - en plak de build knooppunt functie weg hier aan de top.

786
01:05:06,610 --> 01:05:11,750
Op die manier, hopelijk dat zal werken. Laten we dit nog eens gaan.

787
01:05:11,750 --> 01:05:18,920
Nu stelt zij alles. Alles is goed.

788
01:05:18,920 --> 01:05:21,640
>> Maar op dit punt hebben we niet echt geroepen onze insert-functie.

789
01:05:21,640 --> 01:05:26,510
We weten dat het compileert, dus laten we naar binnen gaan en er wat gesprekken binnen

790
01:05:26,510 --> 01:05:28,240
Laten we dat in onze belangrijkste functie.

791
01:05:28,240 --> 01:05:32,390
Hier hebben we uitgecommentarieerd 5, 8, en 2,

792
01:05:32,390 --> 01:05:36,680
en dan hebben we niet bedraden hier beneden.

793
01:05:36,680 --> 01:05:41,640
Laten we wat telefoontjes plegen om in te voegen,

794
01:05:41,640 --> 01:05:46,440
en laten we ook dezelfde soort dingen die we gebruikten gebruiken

795
01:05:46,440 --> 01:05:52,810
als we deze printf oproepen om ervoor te zorgen dat alles was goed te krijgen geplaatst.

796
01:05:52,810 --> 01:06:00,550
Ik ga om te kopiëren en plakken,

797
01:06:00,550 --> 01:06:12,450
en bevat in plaats van we gaan insert doen.

798
01:06:12,450 --> 01:06:30,140
En in plaats van 6, 10, en 1, we gaan naar 5, 8, en 2 te gebruiken.

799
01:06:30,140 --> 01:06:37,320
Deze hopelijk invoegen 5, 8 en 2 in de boom.

800
01:06:37,320 --> 01:06:44,050
Samen te stellen. Alles is goed. Nu gaan we echt rennen ons programma.

801
01:06:44,050 --> 01:06:47,330
>> Alles terug vals.

802
01:06:47,330 --> 01:06:53,830
Dus, 5, 8, en 2 niet gaan, en het lijkt erop Bevat ook niet vinden.

803
01:06:53,830 --> 01:06:58,890
Wat is er aan de hand? Laten we uit te zoomen.

804
01:06:58,890 --> 01:07:02,160
Het eerste probleem was dat insert leek om terug te keren vals,

805
01:07:02,160 --> 01:07:08,750
en het lijkt erop dat dat is omdat we nog in onze return false oproep,

806
01:07:08,750 --> 01:07:14,590
en we nooit echt terug waar.

807
01:07:14,590 --> 01:07:17,880
Wij kunnen dat op.

808
01:07:17,880 --> 01:07:25,290
Het tweede probleem is nu, zelfs als we dat doen - Bewaar deze, sluit deze,

809
01:07:25,290 --> 01:07:34,530
draai make nogmaals, laat het dan vervolgens compileren, voer het uit -

810
01:07:34,530 --> 01:07:37,670
zien we dat hier nog iets anders gebeurd.

811
01:07:37,670 --> 01:07:42,980
De 5, 8 en 2 waren nog nooit gevonden in de boom.

812
01:07:42,980 --> 01:07:44,350
Dus, wat is er aan de hand?

813
01:07:44,350 --> 01:07:45,700
>> Laten we eens een kijkje nemen op deze in de code.

814
01:07:45,700 --> 01:07:49,790
Laten we eens kijken of we dit uitzoeken.

815
01:07:49,790 --> 01:07:57,940
We beginnen met de ouder het niet null.

816
01:07:57,940 --> 01:07:59,510
We zetten de huidige cursorpositie gelijk aan de wortel wijzer,

817
01:07:59,510 --> 01:08:04,280
en we gaan onze af te werken door middel van de boom.

818
01:08:04,280 --> 01:08:08,650
Als het huidige knooppunt niet null is, dan weten we dat we naar beneden een beetje.

819
01:08:08,650 --> 01:08:12,330
We zetten onze parent-pointer gelijk te zijn aan de huidige cursorpositie,

820
01:08:12,330 --> 01:08:15,420
controleerde de waarde - als de waarden gelijk zijn we terug vals.

821
01:08:15,420 --> 01:08:17,540
Als de waarden minder zijn we verhuisd naar de rechterkant;

822
01:08:17,540 --> 01:08:20,399
anders, zijn we verhuisd naar de linkerkant.

823
01:08:20,399 --> 01:08:24,220
Dan bouwen we een knooppunt. Ik zal in te zoomen een beetje.

824
01:08:24,220 --> 01:08:31,410
En hier, we gaan proberen om bedraden de waarden hetzelfde te zijn.

825
01:08:31,410 --> 01:08:37,250
Wat is er aan de hand? Laten we eens kijken of eventueel Valgrind kan ons een hint.

826
01:08:37,250 --> 01:08:43,910
>> Ik wil Valgrind gebruiken, alleen maar omdat Valgrind echt snel loopt

827
01:08:43,910 --> 01:08:46,729
en vertelt u of er geheugenfouten.

828
01:08:46,729 --> 01:08:48,300
Wanneer we lopen Valgrind op de code,

829
01:08:48,300 --> 01:08:55,859
zoals je kunt zien rechts here--Valgrind./binary_tree--and druk op enter.

830
01:08:55,859 --> 01:09:03,640
Je ziet dat we geen geheugen fout, dus het lijkt erop dat alles is in orde nu toe.

831
01:09:03,640 --> 01:09:07,529
We hebben wel wat geheugenlekken, waarvan we weten, omdat we niet

832
01:09:07,529 --> 01:09:08,910
gebeurt met een van onze knooppunten te bevrijden.

833
01:09:08,910 --> 01:09:13,050
Laten we proberen het uitvoeren van GDB om te zien wat er eigenlijk aan de hand.

834
01:09:13,050 --> 01:09:20,010
We doen gdb. / Binary_tree. Het opgestart prima.

835
01:09:20,010 --> 01:09:23,670
Laten we stellen een breekpunt op insert.

836
01:09:23,670 --> 01:09:28,600
Laten we lopen.

837
01:09:28,600 --> 01:09:31,200
Het lijkt erop dat we nooit echt geroepen insert.

838
01:09:31,200 --> 01:09:39,410
Het lijkt erop dat het probleem was alleen dat toen ik veranderde hier beneden in de belangrijkste -

839
01:09:39,410 --> 01:09:44,279
al deze printf oproepen bevat -

840
01:09:44,279 --> 01:09:56,430
Ik heb nooit echt veranderd deze naar insert bellen.

841
01:09:56,430 --> 01:10:01,660
Laten we nu eens te proberen. Laten we samen te stellen.

842
01:10:01,660 --> 01:10:09,130
Alle ziet er goed uit daar. Nu gaan we proberen het runnen van het, zie wat er gebeurt.

843
01:10:09,130 --> 01:10:13,320
Alright! Alles ziet er goed uit daar.

844
01:10:13,320 --> 01:10:18,130
>> Het laatste ding om te denken is, zijn er randgevallen aan deze inzet?

845
01:10:18,130 --> 01:10:23,170
En het blijkt dat, nou ja, de ene rand geval dat altijd interessant om na te denken over

846
01:10:23,170 --> 01:10:26,250
is, wat gebeurt er als uw boom leeg is en u noemen insert functie?

847
01:10:26,250 --> 01:10:30,330
Zal het werken? Nou, laten we het eens proberen.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
De manier waarop we dit gaan testen is, gaan we naar beneden te gaan naar onze belangrijkste functie,

850
01:10:35,810 --> 01:10:41,690
en in plaats van bedraden deze knooppunten op als dit,

851
01:10:41,690 --> 01:10:56,730
we gaan gewoon commentaar uit de hele zaak,

852
01:10:56,730 --> 01:11:02,620
en in plaats van de bedrading van de knooppunten zelf,

853
01:11:02,620 --> 01:11:09,400
kunnen we eigenlijk gewoon doorgaan en verwijderen van dit alles.

854
01:11:09,400 --> 01:11:17,560
We gaan alles een oproep om in te voegen te maken.

855
01:11:17,560 --> 01:11:49,020
Dus, laten we het doen - in plaats van 5, 8, en 2, we gaan tot en met 7 plaatsen, 3 en 9.

856
01:11:49,020 --> 01:11:58,440
En dan gaan we ook willen tot 6 invoegen ook.

857
01:11:58,440 --> 01:12:05,190
Opslaan. Quit. Maak binaire boom.

858
01:12:05,190 --> 01:12:08,540
Het compileert alles.

859
01:12:08,540 --> 01:12:10,320
We kunnen gewoon draaien zoals het is en zien wat er gebeurt,

860
01:12:10,320 --> 01:12:12,770
maar het is ook gaat echt belangrijk om ervoor te zorgen dat

861
01:12:12,770 --> 01:12:14,740
we hebben geen geheugenfouten,

862
01:12:14,740 --> 01:12:16,840
want dit is een van onze kant gevallen die we kennen.

863
01:12:16,840 --> 01:12:20,150
>> Laten we ervoor zorgen dat het goed werkt onder Valgrind,

864
01:12:20,150 --> 01:12:28,310
die we zullen doen door alleen rennen Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Het lijkt erop dat we inderdaad een fout van de ene context -

866
01:12:31,110 --> 01:12:33,790
we hebben dit segmentation fault.

867
01:12:33,790 --> 01:12:36,690
Wat is er gebeurd?

868
01:12:36,690 --> 01:12:41,650
Valgrind vertelt ons eigenlijk waar het is.

869
01:12:41,650 --> 01:12:43,050
Uitzoomen een beetje.

870
01:12:43,050 --> 01:12:46,040
Het lijkt erop dat het gebeurt in onze insert-functie,

871
01:12:46,040 --> 01:12:53,420
waar we een ongeldige lezen van grootte 4 hebben op insert, lijn 60.

872
01:12:53,420 --> 01:13:03,590
Laten we terug gaan en zien wat er hier aan de hand.

873
01:13:03,590 --> 01:13:05,350
Zoom uit echt snel.

874
01:13:05,350 --> 01:13:14,230
Ik wil ervoor zorgen dat het niet naar de rand van het scherm, zodat we alles kunnen zien.

875
01:13:14,230 --> 01:13:18,760
Trek dat in een klein beetje. Alright.

876
01:13:18,760 --> 01:13:35,030
Scroll naar beneden, en het probleem is hier.

877
01:13:35,030 --> 01:13:40,120
Wat gebeurt er als we naar beneden en onze huidige knooppunt is reeds null,

878
01:13:40,120 --> 01:13:44,010
onze parent node is null, dus als we kijken omhoog naar de top, exact hier -

879
01:13:44,010 --> 01:13:47,340
als dit while loop nooit daadwerkelijk wordt uitgevoerd

880
01:13:47,340 --> 01:13:52,330
omdat onze huidige waarde is null - onze wortel is null dus huidig ​​null -

881
01:13:52,330 --> 01:13:57,810
dan is onze ouder wordt nooit op huidig ​​of naar een geldige waarde,

882
01:13:57,810 --> 01:14:00,580
zo is, zal ouder ook null zijn.

883
01:14:00,580 --> 01:14:03,700
We moeten niet vergeten om te controleren op dat

884
01:14:03,700 --> 01:14:08,750
tegen de tijd dat we hier beneden, en we beginnen met het openen van de ouder-waarde.

885
01:14:08,750 --> 01:14:13,190
Dus, wat gebeurt er dan? Nou, als de ouder is null -

886
01:14:13,190 --> 01:14:17,990
if (ouder == NULL) - dan weten we dat

887
01:14:17,990 --> 01:14:19,530
er moet niet iets in de boom.

888
01:14:19,530 --> 01:14:22,030
We moeten proberen om deze in te voegen bij de wortel.

889
01:14:22,030 --> 01:14:32,570
We kunnen dat doen door gewoon het instellen van de wortel gelijk is aan de nieuwe node.

890
01:14:32,570 --> 01:14:40,010
Dan op dit punt hebben we niet echt willen gaan door die andere dingen.

891
01:14:40,010 --> 01:14:44,780
In plaats daarvan, exact hier, kunnen we dit doen een else-if-else,

892
01:14:44,780 --> 01:14:47,610
of we kunnen combineren alles hier in een ander,

893
01:14:47,610 --> 01:14:56,300
maar hier zullen we gewoon anders te gebruiken en het op die manier.

894
01:14:56,300 --> 01:14:59,030
Nu, we gaan testen om ervoor te zorgen dat onze ouders niet null is

895
01:14:59,030 --> 01:15:02,160
voor die tijd eigenlijk proberen om de velden te gebruiken.

896
01:15:02,160 --> 01:15:05,330
Dit zal ons helpen voorkomen dat de segmentation fault.

897
01:15:05,330 --> 01:15:14,740
Dus, we stoppen, zoomen, compileren, uit te voeren.

898
01:15:14,740 --> 01:15:18,130
>> Geen fouten, maar we hebben nog een heleboel geheugenlekken

899
01:15:18,130 --> 01:15:20,650
omdat we niet bevrijden van een van onze knooppunten.

900
01:15:20,650 --> 01:15:24,350
Maar, als we hier en we kijken naar onze afdruk,

901
01:15:24,350 --> 01:15:30,880
zien we dat, nou, ziet eruit als al onze inzetstukken terugkeerden waar is, wat goed is.

902
01:15:30,880 --> 01:15:33,050
De inserts zijn allemaal waar,

903
01:15:33,050 --> 01:15:36,670
en vervolgens de juiste Bevat gesprekken zijn ook waar.

904
01:15:36,670 --> 01:15:41,510
>> Good job! Het lijkt erop dat we met succes geschreven insert.

905
01:15:41,510 --> 01:15:47,430
Dat is alles wat we hebben voor Problem deze week Set specificatie.

906
01:15:47,430 --> 01:15:51,720
Een leuke uitdaging om na te denken over hoe je eigenlijk zou gaan in

907
01:15:51,720 --> 01:15:55,340
en vrij alle knooppunten in deze boom.

908
01:15:55,340 --> 01:15:58,830
We kunnen dit doen op verschillende manieren

909
01:15:58,830 --> 01:16:01,930
maar ik laat dat aan jou om te experimenteren,

910
01:16:01,930 --> 01:16:06,080
en als een leuke uitdaging, proberen en zorg ervoor dat u er zeker van kunt maken

911
01:16:06,080 --> 01:16:09,490
dat dit Valgrind rapport had geen fouten en geen lekken.

912
01:16:09,490 --> 01:16:12,880
>> Veel succes op deze week Huffman-codering probleem set,

913
01:16:12,880 --> 01:16:14,380
en we zien jullie volgende week!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]