1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Article 7] [Menys Còmode]

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

3
00:00:04,890 --> 00:00:07,000
[Aquesta és CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Benvingut a la Secció 7.

5
00:00:09,080 --> 00:00:11,330
Gràcies a huracà de sorra,

6
00:00:11,330 --> 00:00:13,440
en lloc de tenir una secció normal d'aquesta setmana,

7
00:00:13,440 --> 00:00:17,650
estem fent aquest recorregut, a través de la secció de preguntes.

8
00:00:17,650 --> 00:00:22,830
Vaig a estar seguint juntament amb el butlletí de problemes 6 Especificació,

9
00:00:22,830 --> 00:00:25,650
i passant per totes les preguntes de la

10
00:00:25,650 --> 00:00:27,770
Una secció de la secció de Preguntes.

11
00:00:27,770 --> 00:00:30,940
Si hi ha alguna pregunta,

12
00:00:30,940 --> 00:00:32,960
si us plau, publicar-lo en aquests CS50 discutir.

13
00:00:32,960 --> 00:00:35,480
>> Molt bé. Anem a començar.

14
00:00:35,480 --> 00:00:40,780
En aquest moment estic buscant a la pàgina 3 de l'Especificació de problemes.

15
00:00:40,780 --> 00:00:44,110
Anem a començar a parlar primer sobre arbres binaris

16
00:00:44,110 --> 00:00:47,850
ja que aquests tenen una gran rellevància per a conjunt de problemes d'aquesta setmana -

17
00:00:47,850 --> 00:00:49,950
la codificació de l'arbre de Huffman.

18
00:00:49,950 --> 00:00:55,000
Una de les estructures de dades molt 1 parlem sobre CS50 va ser l'arranjament.

19
00:00:55,000 --> 00:01:00,170
Recordeu que una matriu és una seqüència d'elements -

20
00:01:00,170 --> 00:01:04,019
totes del mateix tipus - emmagatzema un al costat de l'altre en la memòria.

21
00:01:04,019 --> 00:01:14,420
Si tinc una matriu d'enters que puc dibuixar amb aquest estil de caixes-numbers-nombres enters -

22
00:01:14,420 --> 00:01:20,290
Diguem que tinc 5 a la primera casella, tinc 7 al segon,

23
00:01:20,290 --> 00:01:27,760
llavors tenen 8, 10, i 20 en el quadre final.

24
00:01:27,760 --> 00:01:33,000
Recordeu les coses, els dos realment bones d'aquesta matriu

25
00:01:33,000 --> 00:01:38,800
és que tenim aquest accés constant a temps a qualsevol element particular

26
00:01:38,800 --> 00:01:40,500
 en la matriu si se sap que el seu índex.

27
00:01:40,500 --> 00:01:44,670
Per exemple, si vull agafar el tercer element de la matriu -

28
00:01:44,670 --> 00:01:47,870
al índex 2 usant la nostra base zero sistema d'indexació -

29
00:01:47,870 --> 00:01:52,220
Jo, literalment, només cal fer un càlcul matemàtic simple,

30
00:01:52,220 --> 00:01:56,170
saltar a la posició en la matriu,

31
00:01:56,170 --> 00:01:57,840
tregui el 8 que estigui emmagatzemat,

32
00:01:57,840 --> 00:01:59,260
i estic llest per sortir.

33
00:01:59,260 --> 00:02:03,350
>> Una de les coses dolentes d'aquest conjunt - que parlem

34
00:02:03,350 --> 00:02:05,010
quan parlem de llistes enllaçades -

35
00:02:05,010 --> 00:02:09,120
és que si voleu inserir un element en l'array,

36
00:02:09,120 --> 00:02:11,090
Vaig a haver de fer algun canvi al seu voltant.

37
00:02:11,090 --> 00:02:12,940
Per exemple, aquesta matriu aquí

38
00:02:12,940 --> 00:02:16,850
està en l'ordre establert - en ordre ascendent -

39
00:02:16,850 --> 00:02:19,440
5, a continuació, 7, 8 i després, a continuació, 10, i després 20 -

40
00:02:19,440 --> 00:02:23,100
però si ho desitja inserir el número 9 en aquesta matriu,

41
00:02:23,100 --> 00:02:27,460
Vaig a haver de canviar alguns dels elements per tal de fer espai.

42
00:02:27,460 --> 00:02:30,440
Podem extreure aquesta aquí.

43
00:02:30,440 --> 00:02:35,650
Vaig a haver de moure el 5, el 7 i després la 8;

44
00:02:35,650 --> 00:02:38,720
crear un espai on puc posar el 9,

45
00:02:38,720 --> 00:02:45,910
i després el 10 i el 20 pot anar a la dreta de la 9.

46
00:02:45,910 --> 00:02:49,450
Aquest és un tipus de dolor perquè en el pitjor dels casos -

47
00:02:49,450 --> 00:02:54,350
quan estem haver de inserir ja sigui al principi o al final

48
00:02:54,350 --> 00:02:56,040
de la matriu, en funció de com estem canviant -

49
00:02:56,040 --> 00:02:58,850
podríem arribar a haver de canviar tots els elements

50
00:02:58,850 --> 00:03:00,750
que actualment estem emmagatzemant en la matriu.

51
00:03:00,750 --> 00:03:03,810
>> Llavors, ¿quina era la forma d'evitar això?

52
00:03:03,810 --> 00:03:09,260
La forma d'evitar això era anar al nostre mètode de llista enllaçada, on -

53
00:03:09,260 --> 00:03:19,820
en lloc d'emmagatzemar els elements 5, 7, 8, 10 i 20 tots un al costat de l'altre en la memòria -

54
00:03:19,820 --> 00:03:25,630
el que en el seu lloc se'ls estava emmagatzemar espècie d'on volíem per emmagatzemar

55
00:03:25,630 --> 00:03:32,470
en aquests nodes de la llista enllaçada que estic dibuixant aquí, una mica ad hoc.

56
00:03:32,470 --> 00:03:42,060
I llavors ells connectats entre si mitjançant aquests indicadors següents.

57
00:03:42,060 --> 00:03:44,370
Puc tenir un punter del 5 al 7 de

58
00:03:44,370 --> 00:03:46,420
un triple des de la 7 a la 8,

59
00:03:46,420 --> 00:03:47,770
un triple des de la 8 a la 10,

60
00:03:47,770 --> 00:03:51,220
i finalment, un triple des de la 10 a la 20,

61
00:03:51,220 --> 00:03:54,880
i després un punter nul en els anys 20 el que indica que no hi ha res a l'esquerra.

62
00:03:54,880 --> 00:03:59,690
La disjuntiva que tenim aquí

63
00:03:59,690 --> 00:04:05,360
és que ara si volem inserir el número 9 a la llista ordenada,

64
00:04:05,360 --> 00:04:08,270
tot el que hem de fer és crear un nou node amb 9,

65
00:04:08,270 --> 00:04:12,290
cablejar cap amunt perquè apunti al lloc adequat,

66
00:04:12,290 --> 00:04:20,630
i després re-cablejat del 8 a l'apuntar cap avall a la 9.

67
00:04:20,630 --> 00:04:25,660
Això és bastant ràpid, en el supòsit que sabem exactament on volem inserir el 9.

68
00:04:25,660 --> 00:04:32,610
Però la compensació a canvi d'això és que hem perdut l'accés constant de temps

69
00:04:32,610 --> 00:04:36,230
a qualsevol element particular en la nostra estructura de dades.

70
00:04:36,230 --> 00:04:40,950
Per exemple, si vull trobar el quart element en aquesta llista enllaçada,

71
00:04:40,950 --> 00:04:43,510
Vaig a haver de començar des del principi de la llista

72
00:04:43,510 --> 00:04:48,930
i treballar a la meva manera a través de comptar node per node fins que trobi el quart.

73
00:04:48,930 --> 00:04:55,870
>> Per tal d'obtenir un millor rendiment d'accés d'una llista enllaçada -

74
00:04:55,870 --> 00:04:59,360
però també retenen alguns dels avantatges que teníem

75
00:04:59,360 --> 00:05:01,800
en termes d'inserció a temps d'una llista enllaçada -

76
00:05:01,800 --> 00:05:05,750
un arbre binari es va a haver d'utilitzar la memòria una mica més.

77
00:05:05,750 --> 00:05:11,460
En particular, en lloc de només tenir un punter a un node d'arbre binari -

78
00:05:11,460 --> 00:05:13,350
igual que la llista enllaçada de nodes fa -

79
00:05:13,350 --> 00:05:16,950
anem a afegir un segon punter per al node de l'arbre binari.

80
00:05:16,950 --> 00:05:19,950
En lloc de tenir un punter al següent element,

81
00:05:19,950 --> 00:05:24,420
tindrem un punter a un fill esquerre i un fill dret.

82
00:05:24,420 --> 00:05:26,560
>> Anem a fer un dibuix per veure el que realment sembla.

83
00:05:26,560 --> 00:05:31,350
Un cop més, vaig a utilitzar aquestes caixes i fletxes.

84
00:05:31,350 --> 00:05:37,150
Un node de l'arbre binari a començar amb només una caixa simple.

85
00:05:37,150 --> 00:05:40,940
Tindrà un espai per al valor,

86
00:05:40,940 --> 00:05:47,280
i llavors també tindrà un espai perquè el fill esquerre i el fill dret.

87
00:05:47,280 --> 00:05:49,280
Vaig a etiquetar aquí.

88
00:05:49,280 --> 00:05:57,560
Anem a tenir el fill esquerre, i després ens anem a tenir el fill dret.

89
00:05:57,560 --> 00:05:59,920
Hi ha moltes maneres diferents de fer això.

90
00:05:59,920 --> 00:06:02,050
De vegades per espai i comoditat,

91
00:06:02,050 --> 00:06:06,460
De fet, em vaig a dibuixar com que estic fent aquí a la part inferior

92
00:06:06,460 --> 00:06:10,910
on jo vaig a tenir el valor en la part superior,

93
00:06:10,910 --> 00:06:14,060
i llavors el nen a la dreta a la part inferior dreta,

94
00:06:14,060 --> 00:06:16,060
i el fill esquerre a la part inferior esquerra.

95
00:06:16,060 --> 00:06:20,250
Tornant a aquest diagrama superior,

96
00:06:20,250 --> 00:06:22,560
tenim el valor en la part superior,

97
00:06:22,560 --> 00:06:25,560
llavors tenim el punter esquerre-fill, i llavors tenim el punter dret de l'infant.

98
00:06:25,560 --> 00:06:30,110
>> En l'especificació del conjunt de problemes,

99
00:06:30,110 --> 00:06:33,110
es parla de l'elaboració d'un node que té un valor de 7,

100
00:06:33,110 --> 00:06:39,750
i després un punter esquerre nen que és nul, i un punter dret de l'infant que és nul.

101
00:06:39,750 --> 00:06:46,040
Podem escriure NULL capital en l'espai per

102
00:06:46,040 --> 00:06:51,610
tant el fill esquerre i el fill dret, o podem treure aquesta barra diagonal

103
00:06:51,610 --> 00:06:53,750
a través de cadascuna de les caselles per indicar que és nul.

104
00:06:53,750 --> 00:06:57,560
Vaig a fer això només perquè és més simple.

105
00:06:57,560 --> 00:07:03,700
El que es veu aquí són dues formes de diagramació d'un node d'arbre binari molt senzill

106
00:07:03,700 --> 00:07:07,960
on tenim el valor 7 i punters nuls infantil.

107
00:07:07,960 --> 00:07:15,220
>> La segona part de les nostres converses amb les especificacions sobre com les llistes enllaçades -

108
00:07:15,220 --> 00:07:18,270
recordi, només vam haver d'esperar al primer element d'una llista

109
00:07:18,270 --> 00:07:20,270
per recordar tota la llista -

110
00:07:20,270 --> 00:07:26,140
i de la mateixa manera, amb un arbre binari, només hem d'aguantar a un punter a l'arbre

111
00:07:26,140 --> 00:07:31,120
amb la finalitat de mantenir el control sobre l'estructura de dades completa.

112
00:07:31,120 --> 00:07:36,150
Aquest element especial de l'arbre s'anomena node arrel de l'arbre.

113
00:07:36,150 --> 00:07:43,360
Per exemple, si aquest node d'un - aquest node que conté el valor 7

114
00:07:43,360 --> 00:07:45,500
amb punters nuls esquerra i dreta per a nens -

115
00:07:45,500 --> 00:07:47,360
eren l'únic valor al nostre arbre,

116
00:07:47,360 --> 00:07:50,390
llavors aquest seria el nostre node arrel.

117
00:07:50,390 --> 00:07:52,240
És el començament mateix del nostre arbre.

118
00:07:52,240 --> 00:07:58,530
Podem veure això una mica més clara un cop que comenci a afegir més nodes al nostre arbre.

119
00:07:58,530 --> 00:08:01,510
Deixa treure una nova pàgina.

120
00:08:01,510 --> 00:08:05,000
>> Ara anem a dibuixar un arbre que té 7 a l'arrel,

121
00:08:05,000 --> 00:08:10,920
i 3 dins de la fill esquerre, i 9 a l'interior de el fill dret.

122
00:08:10,920 --> 00:08:13,500
Un cop més, això és bastant simple.

123
00:08:13,500 --> 00:08:26,510
Tenim 7, dibuixi un node per al 3, un node 9,

124
00:08:26,510 --> 00:08:32,150
i jo vaig a posar el punter esquerre nen de 7 a apuntar al node amb 3,

125
00:08:32,150 --> 00:08:37,850
i el punter dret del fill del node que conté 7 al node que conté 9.

126
00:08:37,850 --> 00:08:42,419
Ara, des del 3 i 9 no tenen fills,

127
00:08:42,419 --> 00:08:48,500
farem que tots els punters als seus fills a ser nul.

128
00:08:48,500 --> 00:08:56,060
Aquí, l'arrel del nostre arbre correspon al node que conté el número 7.

129
00:08:56,060 --> 00:09:02,440
Es pot veure que si tot el que tenim és un punter a aquest node arrel,

130
00:09:02,440 --> 00:09:07,330
llavors podem caminar a través del nostre arbre i accedir a tots dos nodes secundaris -

131
00:09:07,330 --> 00:09:10,630
ambdós 3 i 9.

132
00:09:10,630 --> 00:09:14,820
No cal mantenir els punters a cada node en l'arbre.

133
00:09:14,820 --> 00:09:22,080
Molt bé. Ara anem a afegir un node a aquest diagrama.

134
00:09:22,080 --> 00:09:25,370
Anem a afegir un node que conté 6,

135
00:09:25,370 --> 00:09:34,140
i anem a afegir això com el fill dret del node amb 3.

136
00:09:34,140 --> 00:09:41,850
Per fer això, vaig a esborrar aquest punter nul al 3-node

137
00:09:41,850 --> 00:09:47,750
i cablejar perquè apunti al node que conté 6. Molt bé.

138
00:09:47,750 --> 00:09:53,800
>> En aquest punt, anem a repassar una mica de la terminologia.

139
00:09:53,800 --> 00:09:58,230
Per començar, la raó per la qual això es diu un arbre binari en particular

140
00:09:58,230 --> 00:10:00,460
és que té dos punters nen.

141
00:10:00,460 --> 00:10:06,020
Hi ha altres tipus d'arbres que tenen més punters del nen.

142
00:10:06,020 --> 00:10:10,930
En particular, es va fer un 'try' en Butlletí de problemes 5.

143
00:10:10,930 --> 00:10:19,310
Es donarà compte de que en aquest intent, que va tenir 27 punters diferents per diferents nens -

144
00:10:19,310 --> 00:10:22,410
un per a cadascuna de les 26 lletres en l'alfabet anglès,

145
00:10:22,410 --> 00:10:25,410
i després el dia 27 per l'apòstrof -

146
00:10:25,410 --> 00:10:28,900
és així, que és similar a un tipus d'arbre.

147
00:10:28,900 --> 00:10:34,070
Però aquí, ja que és binari, només tenim dos punters del nen.

148
00:10:34,070 --> 00:10:37,880
>> A més d'aquest node arrel que hem parlat,

149
00:10:37,880 --> 00:10:41,470
també hem estat llançant al voltant d'aquest terme "nen".

150
00:10:41,470 --> 00:10:44,470
Què significa per a un node a ser un fill d'un altre node?

151
00:10:44,470 --> 00:10:54,060
És, literalment, significa que un node fill és un fill d'un altre node

152
00:10:54,060 --> 00:10:58,760
si un altre node que té una de les seves punters de nens fixen per apuntar a aquest node.

153
00:10:58,760 --> 00:11:01,230
Per posar-ho en termes més concrets,

154
00:11:01,230 --> 00:11:11,170
si 3 és apuntat per un dels punters de nen de 7, llavors 3 és un nen de 7.

155
00:11:11,170 --> 00:11:14,510
Si haguéssim de entendre el que els nens de 7 són -

156
00:11:14,510 --> 00:11:18,510
així, veiem que 7 té un punter a 3 i un punter a 9,

157
00:11:18,510 --> 00:11:22,190
el 9 i 3 són fills de 7.

158
00:11:22,190 --> 00:11:26,650
Nou no té fills, perquè els seus fills són punters nuls,

159
00:11:26,650 --> 00:11:30,940
i 3 només té un fill de 6.

160
00:11:30,940 --> 00:11:37,430
Sis tampoc té fills, perquè els seus dos punters són nuls, el que anomenarem ara mateix.

161
00:11:37,430 --> 00:11:45,010
>> A més, també parlem dels pares d'un node en particular,

162
00:11:45,010 --> 00:11:51,100
i això és, com era d'esperar, el revers d'aquesta descripció nen.

163
00:11:51,100 --> 00:11:58,620
Cada node té un sol pare - en lloc de dos com es podria esperar dels éssers humans.

164
00:11:58,620 --> 00:12:03,390
Per exemple, la matriu de 3 és 7.

165
00:12:03,390 --> 00:12:10,800
El pare de 9 és també 7, i el pare de 6 és 3. No hi ha molt a ella.

166
00:12:10,800 --> 00:12:15,720
També tenim termes per parlar dels avis i els néts,

167
00:12:15,720 --> 00:12:18,210
i en general es parla dels avantpassats

168
00:12:18,210 --> 00:12:20,960
i descendents d'un node en particular.

169
00:12:20,960 --> 00:12:25,710
L'ancestre d'un node - o avantpassats, més aviat, d'un node -

170
00:12:25,710 --> 00:12:32,730
són tots els nodes que es troben en el camí des de l'arrel a aquest node.

171
00:12:32,730 --> 00:12:36,640
Per exemple, si estic buscant en el node 6,

172
00:12:36,640 --> 00:12:46,430
llavors els avantpassats serà alhora 3 i 7.

173
00:12:46,430 --> 00:12:55,310
Els avantpassats de 9, per exemple, són - si estic buscant en el node 9 -

174
00:12:55,310 --> 00:12:59,990
llavors l'avantpassat de 9 és només 7.

175
00:12:59,990 --> 00:13:01,940
I descendents són exactament el contrari.

176
00:13:01,940 --> 00:13:05,430
Per veure tots els descendents de 7,

177
00:13:05,430 --> 00:13:11,020
llavors he de mirar tots els nodes que en depenen.

178
00:13:11,020 --> 00:13:16,950
Per tant, tinc 3, 9, i 6 tots com a fills de 7.

179
00:13:16,950 --> 00:13:24,170
>> El termini final que parlarem és d'aquesta noció de ser un germà.

180
00:13:24,170 --> 00:13:27,980
Germans - alguna cosa seguint al llarg d'aquests termes famílies -

181
00:13:27,980 --> 00:13:33,150
són nodes que estan en el mateix nivell en l'arbre.

182
00:13:33,150 --> 00:13:42,230
Així, 3 i 9 són germans perquè estan en el mateix nivell en l'arbre.

183
00:13:42,230 --> 00:13:46,190
Tots dos tenen el mateix pare, 7.

184
00:13:46,190 --> 00:13:51,400
El 6 no té germans perquè 9 no tinc fills.

185
00:13:51,400 --> 00:13:55,540
I 7 no té germans, perquè és l'arrel del nostre arbre,

186
00:13:55,540 --> 00:13:59,010
i només hi ha sempre una arrel.

187
00:13:59,010 --> 00:14:02,260
Per tenir 7 germans no hauria de ser un node per sobre de 7.

188
00:14:02,260 --> 00:14:07,480
No hauria de ser una matriu de 7, en aquest cas 7 ja no seria l'arrel de l'arbre.

189
00:14:07,480 --> 00:14:10,480
Després que els pares nous de 7 també hauria de tenir un fill,

190
00:14:10,480 --> 00:14:16,480
i que nen seria llavors el germà de 7.

191
00:14:16,480 --> 00:14:21,040
>> Molt bé. Canviant de tema.

192
00:14:21,040 --> 00:14:24,930
Quan vam començar la nostra discussió dels arbres binaris,

193
00:14:24,930 --> 00:14:28,790
parlem del que anàvem a utilitzar per

194
00:14:28,790 --> 00:14:32,800
obtenir un avantatge sobre ambdues matrius i llistes enllaçades.

195
00:14:32,800 --> 00:14:37,220
I la manera com ho farem és amb aquesta propietat comanda.

196
00:14:37,220 --> 00:14:41,080
Es diu que un arbre binari és ordenat, d'acord amb l'especificació,

197
00:14:41,080 --> 00:14:45,740
si per a cada node en el nostre arbre, tots els seus descendents de l'esquerra -

198
00:14:45,740 --> 00:14:48,670
el fill de l'esquerra i tots els descendents del fill esquerre -

199
00:14:48,670 --> 00:14:54,510
tenen valors menors, i tots els nodes de la dreta -

200
00:14:54,510 --> 00:14:57,770
el fill dret i tots els descendents dels fills de dret -

201
00:14:57,770 --> 00:15:02,800
tenen nodes més grans que el valor del node actual que estem veient.

202
00:15:02,800 --> 00:15:07,850
Només per simplificar, suposarem que no hi ha nodes duplicats al nostre arbre.

203
00:15:07,850 --> 00:15:11,180
Per exemple, en aquest arbre no tractarem el cas

204
00:15:11,180 --> 00:15:13,680
on tenim el valor 7 a l'arrel

205
00:15:13,680 --> 00:15:16,720
 i després també tenim el valor 7 en un altre lloc en l'arbre.

206
00:15:16,720 --> 00:15:24,390
En aquest cas, es donarà compte que aquest arbre és de fet ordenat.

207
00:15:24,390 --> 00:15:26,510
Tenim el valor 7 a l'arrel.

208
00:15:26,510 --> 00:15:29,720
Tot a l'esquerra de 7 -

209
00:15:29,720 --> 00:15:35,310
si puc desfer totes aquestes petites marques aquí -

210
00:15:35,310 --> 00:15:40,450
tot a l'esquerra de 7 - el 3 i el 6 -

211
00:15:40,450 --> 00:15:49,410
aquests valors es troben a menys de 7, i tot a la dreta - que és precisament aquest 9

212
00:15:49,410 --> 00:15:53,450
és més gran que 7.

213
00:15:53,450 --> 00:15:58,650
>> Aquest no és l'únic arbre ordenat que conté aquests valors,

214
00:15:58,650 --> 00:16:03,120
però farem una mica més d'ells.

215
00:16:03,120 --> 00:16:05,030
En realitat, hi ha un munt de maneres en què podem fer això.

216
00:16:05,030 --> 00:16:09,380
Vaig a utilitzar una drecera només per mantenir les coses simples on -

217
00:16:09,380 --> 00:16:11,520
en comptes d'extreure la totalitat caixes i fletxes -

218
00:16:11,520 --> 00:16:14,220
Jo només vaig a dibuixar els números i afegir fletxes connecten.

219
00:16:14,220 --> 00:16:22,920
Per començar, només haurem d'escriure el nostre arbre original de nou on teníem 7, i després un 3,

220
00:16:22,920 --> 00:16:25,590
i després 3 va assenyalar de nou a la dreta a la 6,

221
00:16:25,590 --> 00:16:30,890
i 7 van tenir un fill dret que tenia 9 anys.

222
00:16:30,890 --> 00:16:33,860
Molt bé. De quina altra manera que no puguem escriure aquest arbre?

223
00:16:33,860 --> 00:16:38,800
En comptes de tenir 3 serà el fill esquerre de 7,

224
00:16:38,800 --> 00:16:41,360
També podria tenir el 6 ser el fill esquerre de 7,

225
00:16:41,360 --> 00:16:44,470
i després 3 serà el fill esquerre de la 6.

226
00:16:44,470 --> 00:16:48,520
Això s'assemblaria a aquest arbre aquí on tinc 7,

227
00:16:48,520 --> 00:16:57,860
després 6, després 3, i un 9 a la dreta.

228
00:16:57,860 --> 00:17:01,490
Tampoc ha de tenir 7 com el nostre node arrel.

229
00:17:01,490 --> 00:17:03,860
També podria tenir 6 com el nostre node arrel.

230
00:17:03,860 --> 00:17:06,470
Què es veu?

231
00:17:06,470 --> 00:17:09,230
Si anem a mantenir aquest immoble ordenat,

232
00:17:09,230 --> 00:17:12,970
tot a l'esquerra de la 6 ha de ser menor que ella.

233
00:17:12,970 --> 00:17:16,540
Només hi ha una possibilitat, i això és 3.

234
00:17:16,540 --> 00:17:19,869
Però llavors, com el fill dret de 6, tenim dues possibilitats.

235
00:17:19,869 --> 00:17:25,380
En primer lloc, podríem tenir el 7 i després el 9,

236
00:17:25,380 --> 00:17:28,850
o podríem dir - que estic a punt de fer aquí -

237
00:17:28,850 --> 00:17:34,790
on tenim el 9 com el fill dret de la 6,

238
00:17:34,790 --> 00:17:39,050
i després el 7 com el fill esquerre de la 9.

239
00:17:39,050 --> 00:17:44,240
>> Ara, 7 i 6 no són els únics valors possibles de l'arrel.

240
00:17:44,240 --> 00:17:50,200
També podríem tenir 3 a l'arrel.

241
00:17:50,200 --> 00:17:52,240
Què passa si 3 és l'arrel?

242
00:17:52,240 --> 00:17:54,390
Aquí, les coses es posen una mica més interessant.

243
00:17:54,390 --> 00:17:58,440
Tres no té valors que són menors del que,

244
00:17:58,440 --> 00:18:02,070
de manera que tot el costat esquerre de l'arbre és només serà nul.

245
00:18:02,070 --> 00:18:03,230
No serà gens allà.

246
00:18:03,230 --> 00:18:07,220
A la dreta, podríem enumerar les coses en ordre ascendent.

247
00:18:07,220 --> 00:18:15,530
Podríem tenir 3, després 6, després 7, després 9.

248
00:18:15,530 --> 00:18:26,710
O bé, podem fer 3, després 6, després 9, després 7.

249
00:18:26,710 --> 00:18:35,020
O bé, podem fer 3, després 7, després 6, després 9.

250
00:18:35,020 --> 00:18:40,950
O, 3, 7 - en realitat no, no podem fer un 7 més.

251
00:18:40,950 --> 00:18:43,330
Aquesta és la nostra única cosa allà.

252
00:18:43,330 --> 00:18:54,710
Podem fer 9, i després des del 9 podem fer 6 i 7.

253
00:18:54,710 --> 00:19:06,980
O bé, podem fer 3, després 9, després 7 i després 6.

254
00:19:06,980 --> 00:19:12,490
>> Una cosa per cridar la seva atenció aquí és

255
00:19:12,490 --> 00:19:14,510
que aquests arbres són una mica d'aspecte estrany.

256
00:19:14,510 --> 00:19:17,840
En particular, si ens fixem en els quatre arbres al costat dret -

257
00:19:17,840 --> 00:19:20,930
Vaig a envoltar, aquí -

258
00:19:20,930 --> 00:19:28,410
aquests arbres es veuen gairebé exactament igual que una llista enllaçada.

259
00:19:28,410 --> 00:19:32,670
Cada node té un sol fill,

260
00:19:32,670 --> 00:19:38,950
pel que no té cap d'aquesta estructura en forma d'arbre que veiem, per exemple,

261
00:19:38,950 --> 00:19:44,720
 en aquest arbre un solitari aquí a la part inferior esquerra.

262
00:19:44,720 --> 00:19:52,490
Aquests arbres es diu en realitat degenerada arbres binaris,

263
00:19:52,490 --> 00:19:54,170
i anem a parlar d'aquests més en el futur -

264
00:19:54,170 --> 00:19:56,730
especialment si vostè va a prendre altres cursos de ciències de la computació.

265
00:19:56,730 --> 00:19:59,670
Aquests arbres són degenerats.

266
00:19:59,670 --> 00:20:03,780
No són molt útils perquè, en efecte, aquesta estructura es presta

267
00:20:03,780 --> 00:20:08,060
 per buscar temps similars a la d'una llista enllaçada.

268
00:20:08,060 --> 00:20:13,050
No aconseguim aprofitar la memòria addicional - aquest punter extra -

269
00:20:13,050 --> 00:20:18,840
perquè de la nostra estructura de ser dolent d'aquesta manera.

270
00:20:18,840 --> 00:20:24,700
En comptes de seguir endavant i treure els arbres binaris que tenen 9 a l'arrel,

271
00:20:24,700 --> 00:20:27,220
que és el cas final que tindria,

272
00:20:27,220 --> 00:20:32,380
estem en canvi, en aquest punt, parlarem una mica sobre aquest altre terme

273
00:20:32,380 --> 00:20:36,150
que utilitzem quan parlem d'arbres, que es diu l'alçada.

274
00:20:36,150 --> 00:20:45,460
>> L'altura d'un arbre és la distància des de l'arrel fins al node més distant,

275
00:20:45,460 --> 00:20:48,370
o més bé el nombre de salts que s'hauria de fer per tal de

276
00:20:48,370 --> 00:20:53,750
començar des de l'arrel i després acaben en el node més llunyà en l'arbre.

277
00:20:53,750 --> 00:20:57,330
Si ens fixem en alguns d'aquests arbres que hem dibuixat aquí,

278
00:20:57,330 --> 00:21:07,870
podem veure que si prenem aquest arbre a la cantonada superior esquerra i comencem a 3,

279
00:21:07,870 --> 00:21:14,510
llavors hem de fer un salt per arribar a la 6, un segon salt per arribar als 7,

280
00:21:14,510 --> 00:21:20,560
i una tercera hop per arribar a la 9.

281
00:21:20,560 --> 00:21:26,120
Així, l'alçada d'aquest arbre és 3.

282
00:21:26,120 --> 00:21:30,640
Podem fer el mateix exercici per als altres arbres assenyalats amb aquest color verd,

283
00:21:30,640 --> 00:21:40,100
i es veu que l'altura de tots aquests arbres és també de fet 3.

284
00:21:40,100 --> 00:21:45,230
Això és part del que els fa degenerar -

285
00:21:45,230 --> 00:21:53,750
que la seva altura és només un menys que el nombre de nodes al arbre.

286
00:21:53,750 --> 00:21:58,400
Si ens fixem en aquest altre arbre que està envoltat de vermell, d'altra banda,

287
00:21:58,400 --> 00:22:03,920
veiem que els nodes de fulla més distants són el 6 i el 9 -

288
00:22:03,920 --> 00:22:06,940
la deixa ser aquells nodes que no tenen fills.

289
00:22:06,940 --> 00:22:11,760
Així, amb la finalitat d'obtenir des del node arrel a ja sigui el 6 o el 9,

290
00:22:11,760 --> 00:22:17,840
hem de fer un salt per arribar a la 7 i després un segon salt per arribar a la 9,

291
00:22:17,840 --> 00:22:21,240
i de la mateixa manera, només un salt de la segona 7 per arribar a la 6.

292
00:22:21,240 --> 00:22:29,080
Així, l'alçada d'aquest arbre d'aquí és només 2.

293
00:22:29,080 --> 00:22:35,330
Vostè pot tornar enrere i fer que per a tots els altres arbres que prèviament discutit

294
00:22:35,330 --> 00:22:37,380
començant amb el 7 i el 6,

295
00:22:37,480 --> 00:22:42,500
i et donaràs compte de que l'altura de tots aquests arbres és també 2.

296
00:22:42,500 --> 00:22:46,320
>> La raó per la qual hem estat parlant ordenar arbres binaris

297
00:22:46,320 --> 00:22:50,250
i per què estem bé és perquè vostè pot cercar a través d'ells en

298
00:22:50,250 --> 00:22:53,810
d'una manera molt similar a la recerca a través d'una matriu ordenada.

299
00:22:53,810 --> 00:22:58,720
Aquí és on parlem d'aconseguir que el temps de recerca millorada

300
00:22:58,720 --> 00:23:02,730
sobre la llista enllaçada simple.

301
00:23:02,730 --> 00:23:05,010
Amb una llista enllaçada - si vol trobar un element en particular -

302
00:23:05,010 --> 00:23:07,470
ets el millor farà algun tipus de recerca lineal

303
00:23:07,470 --> 00:23:10,920
on s'inicia al començament de la llista i saltar d'un en un -

304
00:23:10,920 --> 00:23:12,620
un node a un node -

305
00:23:12,620 --> 00:23:16,060
a través de tota la llista fins que trobi el que vostè està buscant.

306
00:23:16,060 --> 00:23:19,440
Mentre que si vostè té un arbre binari que s'emmagatzema en aquest format agradable,

307
00:23:19,440 --> 00:23:23,300
preguntes més d'una recerca binària passant

308
00:23:23,300 --> 00:23:25,160
on es divideix i venceràs

309
00:23:25,160 --> 00:23:29,490
i buscar a la mitjana corresponent de l'arbre en cada pas.

310
00:23:29,490 --> 00:23:32,840
Anem a veure com funciona.

311
00:23:32,840 --> 00:23:38,850
>> Si tenim - de nou, tornant al nostre arbre original -

312
00:23:38,850 --> 00:23:46,710
comencem a 7, que tenen 3 a l'esquerra, 9 a la dreta,

313
00:23:46,710 --> 00:23:51,740
i sota la 3 tenim la 6.

314
00:23:51,740 --> 00:24:01,880
Si volem buscar el número 6 d'aquest arbre, ens agradaria començar en l'arrel.

315
00:24:01,880 --> 00:24:08,910
Volem comparar el valor que busquem, per exemple 6,

316
00:24:08,910 --> 00:24:12,320
amb el valor emmagatzemat en el node que estem mirant, 7,

317
00:24:12,320 --> 00:24:21,200
trobar que 6 és de fet menor que 7, de manera que ens mou a l'esquerra.

318
00:24:21,200 --> 00:24:25,530
Si el valor de 6 havia estat major que 7, hauríem es mouen a la dreta.

319
00:24:25,530 --> 00:24:29,770
Ja que sabem que - a causa de l'estructura del nostre arbre binari ordenat -

320
00:24:29,770 --> 00:24:33,910
tots els valors de menys de 7 seran emmagatzemats a l'esquerra de 7,

321
00:24:33,910 --> 00:24:40,520
no hi ha necessitat de molestar tan sols mirar pel costat dret de l'arbre.

322
00:24:40,520 --> 00:24:43,780
Quan ens movem cap a l'esquerra i ara estem en el node amb 3,

323
00:24:43,780 --> 00:24:48,110
podem fer aquesta comparació mateixa de nou on es compara el 3 i el 6.

324
00:24:48,110 --> 00:24:52,430
I trobem que mentre que el 6 - el valor que estem buscant - és més gran que 3,

325
00:24:52,430 --> 00:24:58,580
que pot anar cap al costat dret del node amb 3.

326
00:24:58,580 --> 00:25:02,670
No hi ha costat esquerre aquí, així que podria haver ignorat això.

327
00:25:02,670 --> 00:25:06,510
No obstant això, només se sap que pel fet que estem veient en el propi arbre,

328
00:25:06,510 --> 00:25:08,660
i podem veure que l'arbre no té fills.

329
00:25:08,660 --> 00:25:13,640
>> També és molt fàcil buscar 6 d'aquest arbre si ho fem a nosaltres mateixos com a éssers humans,

330
00:25:13,640 --> 00:25:16,890
però seguirem aquest procés mecànicament com un ordinador faria

331
00:25:16,890 --> 00:25:18,620
per comprendre realment l'algorisme.

332
00:25:18,620 --> 00:25:26,200
En aquest punt, ara estem veient un node que conté 6,

333
00:25:26,200 --> 00:25:29,180
i estem buscant el valor 6,

334
00:25:29,180 --> 00:25:31,740
així que, de fet, hem trobat el node apropiat.

335
00:25:31,740 --> 00:25:35,070
Trobem el valor 6 en el nostre arbre, i podem aturar la nostra recerca.

336
00:25:35,070 --> 00:25:37,330
En aquest punt, depenent del que està passant,

337
00:25:37,330 --> 00:25:41,870
podem dir, sí, hem trobat el valor 6, existeix al nostre arbre.

338
00:25:41,870 --> 00:25:47,640
O bé, si estem planejant per inserir un node o fer alguna cosa, podem fer això en aquest moment.

339
00:25:47,640 --> 00:25:53,010
>> Anem a fer un parell de recerques només per veure com funciona això.

340
00:25:53,010 --> 00:25:59,390
Fem una ullada al que succeeix si anéssim a tractar de buscar el valor 10.

341
00:25:59,390 --> 00:26:02,970
Si haguéssim de buscar el valor 10, que començaria a l'arrel.

342
00:26:02,970 --> 00:26:07,070
Ens agradaria veure que 10 és més gran que 7, pel que ens mou a la dreta.

343
00:26:07,070 --> 00:26:13,640
Arribàvem a les 9 i comparar 9 a les 10 i veure que el 9 és de fet inferior a 10.

344
00:26:13,640 --> 00:26:16,210
Així que de nou, ens agradaria tractar de moure a la dreta.

345
00:26:16,210 --> 00:26:20,350
Però en aquest punt, es donaria compte de que estem en un node nul.

346
00:26:20,350 --> 00:26:23,080
No hi ha res allà. No hi ha res que el 10 ha de ser.

347
00:26:23,080 --> 00:26:29,360
Aquí és on podem informar fracàs - que hi ha de fet no 10 en l'arbre.

348
00:26:29,360 --> 00:26:35,420
I, finalment, passarem pel cas en què estem tractant de buscar una al arbre.

349
00:26:35,420 --> 00:26:38,790
Això és similar al que passa si mirem cap amunt 10, excepte que en lloc d'anar a la dreta,

350
00:26:38,790 --> 00:26:41,260
anirem a l'esquerra.

351
00:26:41,260 --> 00:26:46,170
Comencem al 7 i veure que 1 és menor que 7, de manera que es mouen a l'esquerra.

352
00:26:46,170 --> 00:26:51,750
Arribem a la 3 i veure que 1 és menor que 3, pel que de nou es tracta de moure a l'esquerra.

353
00:26:51,750 --> 00:26:59,080
En aquest moment tenim un node nul, així que de nou podem informar fracàs.

354
00:26:59,080 --> 00:27:10,260
>> Si vostè vol aprendre més sobre els arbres binaris,

355
00:27:10,260 --> 00:27:14,420
hi ha un munt de divertits petits problemes que es poden fer amb ells.

356
00:27:14,420 --> 00:27:19,450
Suggereixo practicar el dibuix d'aquests diagrames d'una per un

357
00:27:19,450 --> 00:27:21,910
i seguint a través de tots els diferents passos,

358
00:27:21,910 --> 00:27:25,060
perquè això vindrà en super manejable

359
00:27:25,060 --> 00:27:27,480
no només quan estàs fent la codificació Huffman conjunt de problemes

360
00:27:27,480 --> 00:27:29,390
sinó també en els futurs cursos -

361
00:27:29,390 --> 00:27:32,220
aprenent a dibuixar aquestes estructures de dades i reflexionar sobre els problemes

362
00:27:32,220 --> 00:27:38,000
amb llapis i paper o, en aquest cas, l'iPhone i el llapis.

363
00:27:38,000 --> 00:27:41,000
>> En aquest punt, però, passarem a fer algunes pràctiques de codificació

364
00:27:41,000 --> 00:27:44,870
i realment jugar amb aquests arbres binaris i veure.

365
00:27:44,870 --> 00:27:52,150
Vaig a tornar al meu equip.

366
00:27:52,150 --> 00:27:58,480
Per aquesta part de la secció, en lloc d'utilitzar CS50 CS50 Run o Spaces,

367
00:27:58,480 --> 00:28:01,500
Vaig a utilitzar l'aparell.

368
00:28:01,500 --> 00:28:04,950
>> Seguint amb l'especificació conjunt de problemes,

369
00:28:04,950 --> 00:28:07,740
Veig que he d'obrir l'aparell,

370
00:28:07,740 --> 00:28:11,020
anar a la carpeta de Dropbox, creï una carpeta anomenada Secció 7,

371
00:28:11,020 --> 00:28:15,730
a continuació, creeu un fitxer anomenat binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Aquí anem. Tinc l'aparell ja està obert.

373
00:28:22,050 --> 00:28:25,910
Vaig a aixecar una terminal.

374
00:28:25,910 --> 00:28:38,250
Vaig a anar a la carpeta de Dropbox, creeu un directori anomenat Secció 7,

375
00:28:38,250 --> 00:28:42,230
i veure que és totalment buit.

376
00:28:42,230 --> 00:28:48,860
Ara vaig a obrir binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Molt bé. Aquí anem - arxiu buit.

378
00:28:51,750 --> 00:28:54,330
>> Tornem a l'especificació.

379
00:28:54,330 --> 00:28:59,850
L'especificació demana que creï una definició de tipus nou

380
00:28:59,850 --> 00:29:03,080
per a un node d'arbre binari que conté valors int -

381
00:29:03,080 --> 00:29:07,110
igual que els valors que ens va treure de la nostra diagramació abans.

382
00:29:07,110 --> 00:29:11,740
Utilitzarem aquest text model typedef que hem fet aquí

383
00:29:11,740 --> 00:29:14,420
que s'ha de reconèixer de Sèrie de problemes 5 -

384
00:29:14,420 --> 00:29:19,190
si ho va fer de la manera taula hash de conquerir el programa corrector ortogràfic.

385
00:29:19,190 --> 00:29:22,540
També ha de reconèixer a partir de la secció de la setmana passada

386
00:29:22,540 --> 00:29:23,890
on parlem sobre les llistes enllaçades.

387
00:29:23,890 --> 00:29:27,870
Tenim aquesta typedef d'un node d'estructura,

388
00:29:27,870 --> 00:29:34,430
i li hem donat a aquest node struct aquest nom de node d'estructura per endavant

389
00:29:34,430 --> 00:29:39,350
perquè després pugui referir-s'hi ja que voldrà tenir punters struct node

390
00:29:39,350 --> 00:29:45,740
com a part de la nostra estructura, però després ens hem envoltat aquest -

391
00:29:45,740 --> 00:29:47,700
o més aviat, tancat això - en un typedef

392
00:29:47,700 --> 00:29:54,600
de manera que, més endavant en el codi, es pot fer referència a aquesta estructura com un node en lloc d'un node d'estructura.

393
00:29:54,600 --> 00:30:03,120
>> Això serà molt similar a la definició de la llista simplement enllaçada que vam veure la setmana passada.

394
00:30:03,120 --> 00:30:20,070
Per això, anem a començar per escriure el text model.

395
00:30:20,070 --> 00:30:23,840
Sabem que hem de tenir un valor sencer,

396
00:30:23,840 --> 00:30:32,170
així que posarem en valor int, i llavors, en lloc de tenir només un punter al següent element -

397
00:30:32,170 --> 00:30:33,970
com ho vam fer amb simplement enllaçada llistes -

398
00:30:33,970 --> 00:30:38,110
tindrem punters fill esquerre i dret.

399
00:30:38,110 --> 00:30:42,880
Això és bastant simple també - nen struct node * left;

400
00:30:42,880 --> 00:30:51,190
struct node i nen * dreta;. Cool.

401
00:30:51,190 --> 00:30:54,740
Això sembla un bon començament.

402
00:30:54,740 --> 00:30:58,530
Tornem a l'especificació.

403
00:30:58,530 --> 00:31:05,030
>> Ara hem de declarar una variable de node * global per l'arrel d'un arbre.

404
00:31:05,030 --> 00:31:10,590
Anem a fer d'aquest mundial igual que vam fer en el nostre primer punter llista enllaçada també global.

405
00:31:10,590 --> 00:31:12,690
Això era perquè en les funcions que escrivim

406
00:31:12,690 --> 00:31:16,180
nosaltres no hem de seguir passant al voltant d'aquesta arrel -

407
00:31:16,180 --> 00:31:19,620
encara que ja veurem que si vull escriure aquestes funcions de manera recursiva,

408
00:31:19,620 --> 00:31:22,830
pot ser que sigui millor ni tan sols ho passen al seu voltant com un mundial al primer lloc

409
00:31:22,830 --> 00:31:28,090
i en lloc d'iniciar a nivell local en la seva funció principal.

410
00:31:28,090 --> 00:31:31,960
Però, ho farem a nivell mundial per començar.

411
00:31:31,960 --> 00:31:39,920
Un cop més, donarem un parell d'espais, i jo vaig a declarar una arrel * node.

412
00:31:39,920 --> 00:31:46,770
Només per assegurar-se que no em deixa aquesta sense inicialitzar, em fixaré igual a null.

413
00:31:46,770 --> 00:31:52,210
Ara, en la funció principal - el que anem a escriure molt ràpid aquí -

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
i jo vaig a començar a declarar la meva matriu argv com construïts només perquè jo sàpiga

416
00:32:10,640 --> 00:32:14,550
que aquests arguments són els arguments que probablement no volen modificar.

417
00:32:14,550 --> 00:32:18,390
Per modificar Probablement hauria d'estar fent còpies d'ells.

418
00:32:18,390 --> 00:32:21,740
Vostè veurà això molt en el codi.

419
00:32:21,740 --> 00:32:25,440
Està bé de qualsevol manera. Està bé deixar-lo com - ometre la construïts si ho desitja.

420
00:32:25,440 --> 00:32:28,630
Em solen posar-lo en només perquè em recordo

421
00:32:28,630 --> 00:32:33,650
 que probablement no voleu canviar aquests arguments.

422
00:32:33,650 --> 00:32:39,240
>> Com sempre, vaig a incloure aquesta línia return 0 al final del principal.

423
00:32:39,240 --> 00:32:45,730
Aquí, vaig a iniciar el meu node arrel.

424
00:32:45,730 --> 00:32:48,900
Tal com està ara mateix, tinc un punter que s'estableix en null,

425
00:32:48,900 --> 00:32:52,970
el que apunta al no-res.

426
00:32:52,970 --> 00:32:57,480
Per tal d'iniciar realment la construcció del node,

427
00:32:57,480 --> 00:32:59,250
La primera vegada que assignar memòria per a ell.

428
00:32:59,250 --> 00:33:05,910
Vaig a fer que en fer memòria al heap usant malloc.

429
00:33:05,910 --> 00:33:10,660
Vaig a establir root igual al resultat de malloc,

430
00:33:10,660 --> 00:33:19,550
i vaig a utilitzar l'operador sizeof per calcular la mida d'un node.

431
00:33:19,550 --> 00:33:24,990
La raó per la qual ús node sizeof a diferència de, diguem,

432
00:33:24,990 --> 00:33:37,020
fer alguna cosa com això - malloc (4 + 4 + 4) o malloc 12 -

433
00:33:37,020 --> 00:33:40,820
és perquè vull que el meu codi sigui el més compatible possible.

434
00:33:40,820 --> 00:33:44,540
Vull ser capaç de prendre aquest arxiu. C, compilar en l'aparell,

435
00:33:44,540 --> 00:33:48,820
i després compilar en el meu 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
o en una arquitectura completament diferent -

437
00:33:52,040 --> 00:33:54,640
i vull que tot això funcioni de la mateixa.

438
00:33:54,640 --> 00:33:59,510
>> Si estic fent suposicions sobre la mida de les variables -

439
00:33:59,510 --> 00:34:02,070
la mida d'un int o la mida d'un punter -

440
00:34:02,070 --> 00:34:06,070
llavors jo també estic fent suposicions sobre els tipus d'arquitectures

441
00:34:06,070 --> 00:34:10,440
en què el meu codi es pot compilar amb èxit quan s'executa.

442
00:34:10,440 --> 00:34:15,030
Sempre utilitzi sizeof en lloc de manualment sumant els camps struct.

443
00:34:15,030 --> 00:34:20,500
L'altra raó és que també pot haver encoixinat que el compilador posa en l'estructura.

444
00:34:20,500 --> 00:34:26,570
Encara que només sigui sumant els camps individuals no és una cosa que normalment es vol fer,

445
00:34:26,570 --> 00:34:30,340
així, eliminar aquesta línia.

446
00:34:30,340 --> 00:34:33,090
Ara, per inicialitzar realment aquest node arrel,

447
00:34:33,090 --> 00:34:36,489
Vaig a haver de connectar els valors per a cada un dels seus camps.

448
00:34:36,489 --> 00:34:41,400
Per exemple, per al valor sé que vull per inicialitzar a 7,

449
00:34:41,400 --> 00:34:46,920
i per ara em vaig a posar el nen esquerra a ser nul

450
00:34:46,920 --> 00:34:55,820
i el fill dret a ser també nul. Great!

451
00:34:55,820 --> 00:35:02,670
Ho hem fet part de l'especificació.

452
00:35:02,670 --> 00:35:07,390
>> L'especificació baix a la part inferior de la pàgina 3 em demana que creu més tres nodes -

453
00:35:07,390 --> 00:35:10,600
una que conté 3, una que conté 6, i un amb 9 -

454
00:35:10,600 --> 00:35:14,210
i després cablejar perquè es vegi exactament igual que el nostre diagrama d'arbre

455
00:35:14,210 --> 00:35:17,120
que parlàvem anteriorment.

456
00:35:17,120 --> 00:35:20,450
Farem això molt ràpidament aquí.

457
00:35:20,450 --> 00:35:26,270
Vostè veurà realment ràpid que vaig a començar a escriure un munt de codi duplicat.

458
00:35:26,270 --> 00:35:32,100
Vaig a crear un node * i vaig a trucar tres.

459
00:35:32,100 --> 00:35:36,000
Vaig a posar igual a malloc (sizeof (node)).

460
00:35:36,000 --> 00:35:41,070
Em posaré tres-> valor = 3.

461
00:35:41,070 --> 00:35:54,780
Tres -> left_child = NULL; tres -> dreta _child = NULL; també.

462
00:35:54,780 --> 00:36:01,150
Això es veu molt semblant a la inicialització de l'arrel, i això és exactament el que

463
00:36:01,150 --> 00:36:05,760
Vaig a haver de fer si començar la inicialització de 6 i 9 també.

464
00:36:05,760 --> 00:36:20,720
Ho faré molt ràpid aquí - en realitat, jo vaig a fer una mica de còpia i pega,

465
00:36:20,720 --> 00:36:46,140
i assegurar-se que jo - bé.

466
00:36:46,470 --> 00:37:09,900
 Ara, he de copiar i puc seguir endavant i crear aquesta igual a 6.

467
00:37:09,900 --> 00:37:14,670
Es pot veure que això pren temps i no és super-eficient.

468
00:37:14,670 --> 00:37:22,610
En tan sols una mica, anem a escriure una funció que ho farà per nosaltres.

469
00:37:22,610 --> 00:37:32,890
Vull substituir això amb un 9, reemplaçar amb un 6.

470
00:37:32,890 --> 00:37:37,360
>> Ara tenim tots els nostres nodes creat i inicialitzat.

471
00:37:37,360 --> 00:37:41,200
Tenim la nostra arrel igual a 7, o que conté el valor 7,

472
00:37:41,200 --> 00:37:46,510
nostre node amb 3, el nostre node que conté 6, i el nostre node conté 9.

473
00:37:46,510 --> 00:37:50,390
En aquest punt, tot el que hem de fer és cablejar tot.

474
00:37:50,390 --> 00:37:53,020
La raó per la qual inicialitza tots els punters a null és només perquè m'asseguro que

475
00:37:53,020 --> 00:37:56,260
Jo no tinc cap punter sense inicialitzar en allà per accident.

476
00:37:56,260 --> 00:38:02,290
I també perquè, en aquest moment, només ha de connectar realment els nodes entre si -

477
00:38:02,290 --> 00:38:04,750
als que en realitat estan connectats a - Jo no he d'anar a través i fer

478
00:38:04,750 --> 00:38:08,240
Assegureu-vos que tots els nuls hi són en els llocs apropiats.

479
00:38:08,240 --> 00:38:15,630
>> A partir de l'arrel, ho sé fill esquerre de l'arrel és 3.

480
00:38:15,630 --> 00:38:21,250
Sé que fill dret de l'arrel és 9.

481
00:38:21,250 --> 00:38:24,880
Després d'això, el fill únic que em queda per preocupar

482
00:38:24,880 --> 00:38:39,080
és fill dret 3, que és 6.

483
00:38:39,080 --> 00:38:44,670
En aquest punt, tot es veu molt bé.

484
00:38:44,670 --> 00:38:54,210
Anem a eliminar algunes d'aquestes línies.

485
00:38:54,210 --> 00:38:59,540
Ara tot es veu molt bé.

486
00:38:59,540 --> 00:39:04,240
Tornem a les nostres especificacions i veure el que hem de fer a continuació.

487
00:39:04,240 --> 00:39:07,610
>> En aquest punt, hem d'escriure una funció anomenada "conté"

488
00:39:07,610 --> 00:39:14,150
amb un prototip del 'conté bool (int value).

489
00:39:14,150 --> 00:39:17,060
I això inclou la funció tornarà true

490
00:39:17,060 --> 00:39:21,200
 si l'arbre apuntat per la variable arrel global

491
00:39:21,200 --> 00:39:26,950
 conté el valor que es passa a la funció i false en cas contrari.

492
00:39:26,950 --> 00:39:29,000
Seguirem endavant i fer això.

493
00:39:29,000 --> 00:39:35,380
Això serà exactament igual que la recerca que hem fet a mà en l'iPad una mica enrere.

494
00:39:35,380 --> 00:39:40,130
Anem a tornar a augmentar una mica i desplaceu-vos cap amunt.

495
00:39:40,130 --> 00:39:43,130
Posarem aquesta funció just a sobre de la nostra funció principal

496
00:39:43,130 --> 00:39:48,990
de manera que no hem de fer cap tipus de prototips.

497
00:39:48,990 --> 00:39:55,960
Per tant, conté bool (int value).

498
00:39:55,960 --> 00:40:00,330
Aquí anem. Aquí està la nostra declaració repetitiu.

499
00:40:00,330 --> 00:40:02,900
Només per assegurar-se que aquesta es compilarà,

500
00:40:02,900 --> 00:40:06,820
Vaig a seguir endavant i només ho fa igual a tornar false.

501
00:40:06,820 --> 00:40:09,980
En aquest moment aquesta funció simplement no fer res i sempre informen que

502
00:40:09,980 --> 00:40:14,010
el valor que està buscant no està en l'arbre.

503
00:40:14,010 --> 00:40:16,280
>> En aquest punt, és probablement una bona idea -

504
00:40:16,280 --> 00:40:19,600
ja que he escrit un munt de codi i ni tan sols hem intentat provar encara -

505
00:40:19,600 --> 00:40:22,590
per assegurar-se que tot es compila.

506
00:40:22,590 --> 00:40:27,460
Hi ha un parell de coses que hem de fer per assegurar-se que això va a compilar.

507
00:40:27,460 --> 00:40:33,530
En primer lloc, veure si hem estat utilitzant qualsevol de les funcions de les biblioteques que encara no hem inclosos.

508
00:40:33,530 --> 00:40:37,940
Les funcions que hem utilitzat fins ara són malloc,

509
00:40:37,940 --> 00:40:43,310
i també hem estat utilitzant aquest tipus - aquest tipus no estàndard anomenada "bool '-

510
00:40:43,310 --> 00:40:45,750
que s'inclou en l'arxiu de capçalera bool estàndard.

511
00:40:45,750 --> 00:40:53,250
Definitivament, volem incloure bool.h estàndard per al tipus bool,

512
00:40:53,250 --> 00:40:59,230
i també volem incloure # lib.h estàndard per les biblioteques estàndard

513
00:40:59,230 --> 00:41:03,530
que inclouen malloc i lliure, i tot això.

514
00:41:03,530 --> 00:41:08,660
Per tant, allunyar la imatge, anem a deixar de fumar.

515
00:41:08,660 --> 00:41:14,190
Tractarem d'assegurar-se que això realment va fer compilació.

516
00:41:14,190 --> 00:41:18,150
Veiem que el fa, així que estem en el camí correcte.

517
00:41:18,150 --> 00:41:22,990
>> Anem a obrir binary_tree.c nou.

518
00:41:22,990 --> 00:41:34,530
Compila. Anem cap avall i assegureu-vos que inserim algunes trucades a la nostra funció conté -

519
00:41:34,530 --> 00:41:40,130
només per assegurar-se que això és tot bé i bo.

520
00:41:40,130 --> 00:41:43,170
Per exemple, quan vam fer algunes recerques en el nostre arbre abans,

521
00:41:43,170 --> 00:41:48,500
hem tractat de buscar els 6 valors, 10 i 1, i sabíem que el 6 era al arbre,

522
00:41:48,500 --> 00:41:52,220
10 no estava en l'arbre, i 1 no estava en l'arbre tampoc.

523
00:41:52,220 --> 00:41:57,230
Anem a utilitzar aquestes trucades és una manera d'esbrinar si és o no

524
00:41:57,230 --> 00:41:59,880
nostra funció conté està funcionant.

525
00:41:59,880 --> 00:42:05,210
Per tal de fer això, vaig a utilitzar la funció printf,

526
00:42:05,210 --> 00:42:10,280
i anem a imprimir el resultat de la crida a la contingui.

527
00:42:10,280 --> 00:42:13,280
Em vaig a posar en una cadena "conté (% d) = perquè

528
00:42:13,280 --> 00:42:20,470
 anem a endollar el valor que anem a buscar,

529
00:42:20,470 --> 00:42:27,130
i =% s \ n ", i usar això com la nostra cadena de format.

530
00:42:27,130 --> 00:42:30,720
Només veurem - literalment imprimir a la pantalla -

531
00:42:30,720 --> 00:42:32,060
el que sembla una trucada de funció.

532
00:42:32,060 --> 00:42:33,580
Això no és realment la crida a la funció.

533
00:42:33,580 --> 00:42:36,760
 Això és només una cadena dissenyat per assemblar-se a una trucada de funció.

534
00:42:36,760 --> 00:42:41,140
>> Ara, anem a connectar els valors.

535
00:42:41,140 --> 00:42:43,580
Intentarem conté els dies 6,

536
00:42:43,580 --> 00:42:48,340
i llavors, què farem aquí és utilitzar aquest operador ternari.

537
00:42:48,340 --> 00:42:56,340
Anem a veure - inclou 6 - així que, ara que he contenia 6 i si conté 6 és cert,

538
00:42:56,340 --> 00:43:01,850
la cadena que enviarem al caràcter de format% s

539
00:43:01,850 --> 00:43:04,850
serà la cadena "true".

540
00:43:04,850 --> 00:43:07,690
Anem a desplaçar-se durant una estona.

541
00:43:07,690 --> 00:43:16,210
En cas contrari, volem enviar la cadena "false" si conté 6 retorna false.

542
00:43:16,210 --> 00:43:19,730
Això és una mica maldestre aspecte, però m'imagino que bé podria il · lustrar

543
00:43:19,730 --> 00:43:23,780
el que l'operador ternari sembla, ja que no l'he vist per un temps.

544
00:43:23,780 --> 00:43:27,670
Aquesta serà una manera agradable, molt pràctic per saber si la nostra funció conté està funcionant.

545
00:43:27,670 --> 00:43:30,040
Vaig a desplaçar-se de nou cap a l'esquerra,

546
00:43:30,040 --> 00:43:39,900
i vaig a copiar i enganxar aquesta línia un parell de vegades.

547
00:43:39,900 --> 00:43:44,910
Va canviar alguns d'aquests valors al voltant,

548
00:43:44,910 --> 00:43:59,380
així que això serà 1, i això serà de 10.

549
00:43:59,380 --> 00:44:02,480
>> En aquest punt tenim una funció conté agradable.

550
00:44:02,480 --> 00:44:06,080
Tenim algunes proves, i anem a veure si funciona tot això.

551
00:44:06,080 --> 00:44:08,120
En aquest punt hem escrit codi una mica més.

552
00:44:08,120 --> 00:44:13,160
És hora de deixar de fumar i assegurar-se que tot el que encara compila.

553
00:44:13,160 --> 00:44:20,360
Sortir fora, i ara intentarem fer arbre binari de nou.

554
00:44:20,360 --> 00:44:22,260
Bé, sembla que tenim un error,

555
00:44:22,260 --> 00:44:26,930
I tenim aquesta declarar explícitament la funció de biblioteca printf.

556
00:44:26,930 --> 00:44:39,350
Sembla que hem d'anar i # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
I amb això, tot ha compilar. Estem tots bé.

558
00:44:45,350 --> 00:44:50,420
Ara intentarem executar arbre binari i veure què passa.

559
00:44:50,420 --> 00:44:53,520
Aquí estem. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
i veiem que, com esperàvem -

561
00:44:55,190 --> 00:44:56,910
perquè no han posat en pràctica conté, però,

562
00:44:56,910 --> 00:44:59,800
o més aviat, acabem de posar en return false -

563
00:44:59,800 --> 00:45:03,300
veiem que s'acaba de tornar false per a tots ells,

564
00:45:03,300 --> 00:45:06,180
de manera que tot està funcionant en la seva major part bastant bé.

565
00:45:06,180 --> 00:45:11,860
>> Anem a anar de nou i posar en pràctica en realitat conté en aquest punt.

566
00:45:11,860 --> 00:45:17,490
Vaig a desplaçar-se cap avall, apropar, i -

567
00:45:17,490 --> 00:45:22,330
recordi, l'algorisme que es va utilitzar va ser que vam començar en el node arrel

568
00:45:22,330 --> 00:45:28,010
i després en cada node que trobem, fem una comparació,

569
00:45:28,010 --> 00:45:32,380
i d'acord amb aquesta comparació que o moure el nen a l'esquerra oa la dreta nen.

570
00:45:32,380 --> 00:45:39,670
Això semblarà molt similar al codi binari de recerca que hem escrit anteriorment en el terme.

571
00:45:39,670 --> 00:45:47,810
Quan ens vam posar en marxa, sabem que volem mantenir en el node actual

572
00:45:47,810 --> 00:45:54,050
que estem veient, i el node actual serà inicialitzat al node arrel.

573
00:45:54,050 --> 00:45:56,260
I ara, seguirem endavant a través de l'arbre,

574
00:45:56,260 --> 00:45:58,140
i recordar que la nostra condició de parada -

575
00:45:58,140 --> 00:46:01,870
 quan realment acabat amb l'exemple a mà -

576
00:46:01,870 --> 00:46:03,960
Va ser llavors quan ens trobem amb un node nul,

577
00:46:03,960 --> 00:46:05,480
no quan mirem a un nen nul,

578
00:46:05,480 --> 00:46:09,620
sinó més bé quan realment mou a un node a l'arbre

579
00:46:09,620 --> 00:46:12,640
i van trobar que estem en un node nul.

580
00:46:12,640 --> 00:46:20,720
Anem a iterar fins act no és igual a null.

581
00:46:20,720 --> 00:46:22,920
I què farem?

582
00:46:22,920 --> 00:46:31,610
Anem a provar si (act -> valor value ==),

583
00:46:31,610 --> 00:46:35,160
llavors sabem que en realitat hem trobat el node que estem buscant.

584
00:46:35,160 --> 00:46:40,450
Així que aquí, podem tornar realitat.

585
00:46:40,450 --> 00:46:49,830
En cas contrari, volem veure si el valor és menor que el valor.

586
00:46:49,830 --> 00:46:53,850
Si el valor del node actual és menor que el valor que busquem,

587
00:46:53,850 --> 00:46:57,280
mourem a la dreta.

588
00:46:57,280 --> 00:47:10,600
Per tant, act act = -> right_child, i si no, anem a moure cap a l'esquerra.

589
00:47:10,600 --> 00:47:17,480
act = act -> left_child;. Bastant simple.

590
00:47:17,480 --> 00:47:22,830
>> És probable que reconèixer el llaç que es veu molt similar a la d'aquest

591
00:47:22,830 --> 00:47:27,580
cerca binària anteriorment al terme, excepte llavors es tractava de mitjans baixa i alta.

592
00:47:27,580 --> 00:47:30,000
En aquest cas, només hem de mirar a un valor actual,

593
00:47:30,000 --> 00:47:31,930
així que és agradable i simple.

594
00:47:31,930 --> 00:47:34,960
Ens assegurarem que el codi estigui funcionant.

595
00:47:34,960 --> 00:47:42,780
Primer, assegureu-vos que compila. Sembla que ho fa.

596
00:47:42,780 --> 00:47:47,920
Tractarem d'executar.

597
00:47:47,920 --> 00:47:50,160
I, en efecte, imprimeix tot el que esperàvem.

598
00:47:50,160 --> 00:47:54,320
Es troba a 6 al arbre, no troba 10 perquè 10 no està en l'arbre,

599
00:47:54,320 --> 00:47:57,740
i no troba ja sigui perquè 1 1 No és també a l'arbre.

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

601
00:48:01,420 --> 00:48:04,470
>> Molt bé. Tornem a la nostra especificació i veure el que es ve.

602
00:48:04,470 --> 00:48:07,990
Ara, vol afegir nodes alguns més per al nostre arbre.

603
00:48:07,990 --> 00:48:11,690
Vol afegir 5, 2 i 8, i assegureu-vos que conté el nostre codi

604
00:48:11,690 --> 00:48:13,570
encara funciona com s'esperava.

605
00:48:13,570 --> 00:48:14,900
Farem això.

606
00:48:14,900 --> 00:48:19,430
En aquest punt, en lloc de fer que còpia molest i enganxar de nou,

607
00:48:19,430 --> 00:48:23,770
escriurem una funció per crear realment un node.

608
00:48:23,770 --> 00:48:27,740
Si ens desplacem cap avall fins arribar a principal, veiem que hem estat fent això

609
00:48:27,740 --> 00:48:31,210
codi molt semblant una i altra vegada cada vegada que volem crear un node.

610
00:48:31,210 --> 00:48:39,540
>> Anem a escriure una funció que en realitat va a construir un node per a nosaltres i el torna.

611
00:48:39,540 --> 00:48:41,960
Vaig a dir-build_node.

612
00:48:41,960 --> 00:48:45,130
Vaig a construir un node amb un valor determinat.

613
00:48:45,130 --> 00:48:51,040
Acosta't aquí.

614
00:48:51,040 --> 00:48:56,600
El primer que vaig a fer és crear un espai per al node en el munt.

615
00:48:56,600 --> 00:49:05,400
Per tant, el node * n = malloc (sizeof (node)); n -> valor = valor;

616
00:49:05,400 --> 00:49:14,960
i després aquí, jo només vaig a inicialitzar tots els camps per als valors adequats.

617
00:49:14,960 --> 00:49:22,500
I al final, tornarem a la nostra node.

618
00:49:22,500 --> 00:49:28,690
Molt bé. Una cosa a tenir en compte és que aquesta funció aquí

619
00:49:28,690 --> 00:49:34,320
tornarà un punter a la memòria que ha estat assignada per munt.

620
00:49:34,320 --> 00:49:38,880
El millor d'això és que aquest node ara -

621
00:49:38,880 --> 00:49:42,420
hem de declarar en el munt perquè si ho declarat a la pila

622
00:49:42,420 --> 00:49:45,050
no seríem capaços de fer en aquesta funció com aquesta.

623
00:49:45,050 --> 00:49:47,690
Aquesta memòria es surtin de l'àmbit

624
00:49:47,690 --> 00:49:51,590
i no seria vàlida si intentem accedir-hi més endavant.

625
00:49:51,590 --> 00:49:53,500
Ja que estem declarant munt assignat per la memòria,

626
00:49:53,500 --> 00:49:55,830
haurem de cuidar d'alliberar més tard

627
00:49:55,830 --> 00:49:58,530
per al nostre programa no s'escapi cap record.

628
00:49:58,530 --> 00:50:01,270
Hem estat en el qual safata per tota la resta en el codi

629
00:50:01,270 --> 00:50:02,880
només per raons de simplicitat en el moment,

630
00:50:02,880 --> 00:50:05,610
però si mai escriure una funció que té aquest aspecte

631
00:50:05,610 --> 00:50:10,370
on tens - alguns en diuen un malloc o realloc interior -

632
00:50:10,370 --> 00:50:14,330
vostè voldrà assegurar-se que vostè posa algun tipus de comentari per aquí que diu:

633
00:50:14,330 --> 00:50:29,970
bé, ja saps, torna un node de heap assignat s'inicialitza amb el valor passat com.

634
00:50:29,970 --> 00:50:33,600
I llavors vostè vol assegurar-se que vostè posa en una mena de nota que diu:

635
00:50:33,600 --> 00:50:41,720
el picador d'alliberar la memòria retornada.

636
00:50:41,720 --> 00:50:45,450
D'aquesta manera, si algú alguna vegada va i fa servir aquesta funció,

637
00:50:45,450 --> 00:50:48,150
ells saben que qualsevol cosa que torni d'aquesta funció

638
00:50:48,150 --> 00:50:50,870
en algun moment haurà de ser alliberat.

639
00:50:50,870 --> 00:50:53,940
>> Suposant que tot està bé i bo aquí,

640
00:50:53,940 --> 00:51:02,300
podem baixar al nostre codi i reemplaçar totes aquestes línies aquí

641
00:51:02,300 --> 00:51:05,410
amb trucades a la nostra funció de node de generació.

642
00:51:05,410 --> 00:51:08,170
Farem això molt ràpidament.

643
00:51:08,170 --> 00:51:15,840
L'única part que no anem a substituir és aquesta part aquí baix

644
00:51:15,840 --> 00:51:18,520
a la part inferior on realment cablejar els nodes perquè apunti a l'altra,

645
00:51:18,520 --> 00:51:21,030
ja que no podem fer en la nostra funció.

646
00:51:21,030 --> 00:51:37,400
Però, farem root = build_node (7); node * = build_node tres (3);

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

648
00:51:47,980 --> 00:51:52,590
I ara, també volíem afegir nodes per -

649
00:51:52,590 --> 00:52:03,530
node * 5 = build_node (5); node * = build_node vuit (8);

650
00:52:03,530 --> 00:52:09,760
i el que era l'altre node? Anem a veure aquí. Hem volgut afegir també un 2 -

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

652
00:52:20,280 --> 00:52:26,850
Molt bé. En aquest punt, sabem que tenim el 7, el 3, el 9 i el 6

653
00:52:26,850 --> 00:52:30,320
tots connectats de manera apropiada, però què passa amb el 5, el 8, i el 2?

654
00:52:30,320 --> 00:52:33,550
Per mantenir tot en l'ordre apropiat,

655
00:52:33,550 --> 00:52:39,230
sabem que el fill dret és tres 6.

656
00:52:39,230 --> 00:52:40,890
Per tant, si anem a afegir als 5,

657
00:52:40,890 --> 00:52:46,670
el 5 pertany també al costat dret de l'arbre dels quals 3 és l'arrel,

658
00:52:46,670 --> 00:52:50,440
així com 5 pertany el fill esquerre de 6.

659
00:52:50,440 --> 00:52:58,650
Podem fer això dient, sis -> left_child = cinc;

660
00:52:58,650 --> 00:53:10,790
i després el 8 pertany com fill esquerre de 9, de manera que nou -> left_child = vuit;

661
00:53:10,790 --> 00:53:22,190
i després 2 és el fill esquerre de 3, pel que podem fer això aquí - et -> left_child = dues;.

662
00:53:22,190 --> 00:53:27,730
Si no acabava d'assistir a juntament amb això, li suggereixo que ho arribarà a tu mateix.

663
00:53:27,730 --> 00:53:35,660
>> Molt bé. Anem a guardar aquest. Anem a sortir i assegurar-se que recopila,

664
00:53:35,660 --> 00:53:40,760
i després podem afegir a les nostres trucades conté.

665
00:53:40,760 --> 00:53:44,120
Sembla que tot segueix compila.

666
00:53:44,120 --> 00:53:51,790
Anem a entrar i afegir en alguns conté trucades.

667
00:53:51,790 --> 00:53:59,640
Un cop més, vaig a fer una mica de copiar i enganxar.

668
00:53:59,640 --> 00:54:15,860
Ara anem a buscar a 5, 8 i 2. Molt bé.

669
00:54:15,860 --> 00:54:28,330
Anem a fer de tot això es veu bé encara. Great! Guardar i sortir.

670
00:54:28,330 --> 00:54:33,220
Ara farem, compilar, i ara anem a córrer.

671
00:54:33,220 --> 00:54:37,540
A partir dels resultats, sembla que tot està funcionant molt bé i bé.

672
00:54:37,540 --> 00:54:41,780
Great! Així que ara tenim a la nostra funció contains escrit.

673
00:54:41,780 --> 00:54:46,160
Seguirem endavant i començar a treballar en la forma d'inserir nodes en l'arbre

674
00:54:46,160 --> 00:54:50,000
ja que, com ho estem fent en aquest moment, les coses no són molt bonics.

675
00:54:50,000 --> 00:54:52,280
>> Si ens remuntem a l'especificació,

676
00:54:52,280 --> 00:55:00,540
ens demana que escrigui una funció anomenada inserir - de nou, tornant a bool

677
00:55:00,540 --> 00:55:04,400
per saber si estem o no en realitat podria inserir el node a l'arbre -

678
00:55:04,400 --> 00:55:07,710
i després el valor per inserir en l'arbre s'especifica com

679
00:55:07,710 --> 00:55:11,060
l'únic argument a la nostra funció d'inserció.

680
00:55:11,060 --> 00:55:18,180
Ens retornarà true si realment pot inserir el valor del node que conté l'arbre,

681
00:55:18,180 --> 00:55:20,930
el que significa que, un, tenia suficient memòria,

682
00:55:20,930 --> 00:55:24,840
i després dos, aquest node no existeix en l'arbre ja que -

683
00:55:24,840 --> 00:55:32,170
Recordeu, nosaltres no tindrem valors duplicats a l'arbre, només per fer les coses simples.

684
00:55:32,170 --> 00:55:35,590
Molt bé. Tornar al principi Codi.

685
00:55:35,590 --> 00:55:44,240
Obre'l. Apropar una mica, a continuació, desplaceu-vos cap avall.

686
00:55:44,240 --> 00:55:47,220
Anem a posar la funció d'inserció just a sobre de les contains.

687
00:55:47,220 --> 00:55:56,360
Un cop més, serà anomenat insert bool (int value).

688
00:55:56,360 --> 00:56:01,840
Dóna-li una mica més espai i, a continuació, per defecte,

689
00:56:01,840 --> 00:56:08,870
posarem en return false al final.

690
00:56:08,870 --> 00:56:22,620
Ara, en el fons, seguirem endavant i en comptes de construir manualment els nodes

691
00:56:22,620 --> 00:56:27,900
principal en nosaltres mateixos i el cablejat fins al punt que l'un a l'altre com ho estem fent,

692
00:56:27,900 --> 00:56:30,600
anem a confiar en la nostra funció d'inserció de fer això.

693
00:56:30,600 --> 00:56:35,510
No anem a confiar en la nostra funció d'inserció per construir l'arbre sencer des de zero encara,

694
00:56:35,510 --> 00:56:39,970
sinó que més aviat ens desfarem d'aquestes línies - ens tornarem comentar aquestes línies -

695
00:56:39,970 --> 00:56:43,430
de construir els nodes 5, 8 i 2.

696
00:56:43,430 --> 00:56:55,740
I en el seu lloc, anem a inserir trucades a la nostra funció d'inserció

697
00:56:55,740 --> 00:57:01,280
per assegurar-se que que realment funciona.

698
00:57:01,280 --> 00:57:05,840
Aquí anem.

699
00:57:05,840 --> 00:57:09,300
>> Ara hem comentat aquestes línies.

700
00:57:09,300 --> 00:57:13,700
Només tenim 7, 3, 9, i 6 en el nostre arbre en aquest punt.

701
00:57:13,700 --> 00:57:18,870
Per assegurar-se que tot això està funcionant,

702
00:57:18,870 --> 00:57:25,050
podem allunyar, fer el nostre arbre binari,

703
00:57:25,050 --> 00:57:30,750
executar, i podem veure que conté ara ens està dient que tenim tota la raó -

704
00:57:30,750 --> 00:57:33,110
5, 8, i 2 ja no estan en l'arbre.

705
00:57:33,110 --> 00:57:37,960
Tornar enrere en el codi,

706
00:57:37,960 --> 00:57:41,070
i com podem inserir?

707
00:57:41,070 --> 00:57:46,290
Recordeu el que vam fer quan estàvem en realitat la inserció de 5, 8, i 2 prèviament.

708
00:57:46,290 --> 00:57:50,100
Hem jugat a aquest joc Plinko on vam començar a l'arrel,

709
00:57:50,100 --> 00:57:52,780
va baixar l'arbre per un per un

710
00:57:52,780 --> 00:57:54,980
fins a trobar el buit apropiat,

711
00:57:54,980 --> 00:57:57,570
i després per cable al node al punt apropiat.

712
00:57:57,570 --> 00:57:59,480
Anem a fer el mateix.

713
00:57:59,480 --> 00:58:04,070
Això és bàsicament com escriure el codi que fem servir en la funció contains

714
00:58:04,070 --> 00:58:05,910
per trobar el punt on el node ha de ser,

715
00:58:05,910 --> 00:58:10,560
i llavors només anem a inserir el node allà.

716
00:58:10,560 --> 00:58:17,000
Anem a començar a fer això.

717
00:58:17,000 --> 00:58:24,200
>> Així que tenim un node * act = root, només seguirem el codi conté

718
00:58:24,200 --> 00:58:26,850
fins que ens trobem que no acaba de funcionar per a nosaltres.

719
00:58:26,850 --> 00:58:32,390
Anirem a través de l'arbre, mentre que aquest element no és nul,

720
00:58:32,390 --> 00:58:45,280
i si trobem que act valor és igual al valor que estem tractant d'inserir -

721
00:58:45,280 --> 00:58:49,600
bo, aquest és un dels casos en què no vam poder inserir el node

722
00:58:49,600 --> 00:58:52,730
en l'arbre perquè això vol dir que tenim un valor duplicat.

723
00:58:52,730 --> 00:58:59,010
Aquí estem en realitat tornarà false.

724
00:58:59,010 --> 00:59:08,440
Ara bé, si el valor actual és menor que el valor,

725
00:59:08,440 --> 00:59:10,930
ara sabem que ens movem cap a la dreta

726
00:59:10,930 --> 00:59:17,190
 perquè el valor pertany a la meitat dreta de l'arbre act.

727
00:59:17,190 --> 00:59:30,110
En cas contrari, mourem cap a l'esquerra.

728
00:59:30,110 --> 00:59:37,980
Això és bàsicament la nostra funció contains aquí.

729
00:59:37,980 --> 00:59:41,820
>> En aquest punt, un cop hàgim completat aquest bucle while,

730
00:59:41,820 --> 00:59:47,350
nostre punter act estarà apuntant a null

731
00:59:47,350 --> 00:59:51,540
si la funció no ha tornat.

732
00:59:51,540 --> 00:59:58,710
Estem per tant tenir act al lloc on volem inserir el nou node.

733
00:59:58,710 --> 01:00:05,210
El que queda per fer és construir realment el nou node,

734
01:00:05,210 --> 01:00:08,480
que podem fer amb força facilitat.

735
01:00:08,480 --> 01:00:14,930
Podem utilitzar la nostra super manejable i funció de node de generació,

736
01:00:14,930 --> 01:00:17,210
i és una cosa que no hem fet abans -

737
01:00:17,210 --> 01:00:21,400
nosaltres només tipus de donava per fet, però ara ho farem només per assegurar-se -

738
01:00:21,400 --> 01:00:27,130
anem a provar per assegurar-se que el valor retornat pel nou node en realitat era

739
01:00:27,130 --> 01:00:33,410
no és nul, perquè no vull començar a accedir a aquesta memòria si és nul.

740
01:00:33,410 --> 01:00:39,910
Podem provar per assegurar-se que el nou node no és igual a null.

741
01:00:39,910 --> 01:00:42,910
O per contra, només podem veure si realment és nul,

742
01:00:42,910 --> 01:00:52,120
i si és nul, llavors només pot tornar false hora.

743
01:00:52,120 --> 01:00:59,090
>> En aquest punt, hem de cablejar nou node en el seu lloc corresponent en l'arbre.

744
01:00:59,090 --> 01:01:03,510
Si mirem cap enrere en la principal i en el qual en realitat eren el cablejat en els valors d'abans,

745
01:01:03,510 --> 01:01:08,470
veiem que la manera com ho feien quan volien posar 3 al arbre

746
01:01:08,470 --> 01:01:11,750
S'accedeix a que el fill esquerre de l'arrel.

747
01:01:11,750 --> 01:01:14,920
Quan posem 9 al arbre, vam haver accedir al fill dret de l'arrel.

748
01:01:14,920 --> 01:01:21,030
Havíem de tenir un punter a la matriu per tal de posar un nou valor en l'arbre.

749
01:01:21,030 --> 01:01:24,430
Desplaçament d'una còpia de seguretat per inserir, això no funcionarà bastant aquí

750
01:01:24,430 --> 01:01:27,550
perquè no tenim un punter pares.

751
01:01:27,550 --> 01:01:31,650
El que vull ser capaç de fer és, en aquest punt,

752
01:01:31,650 --> 01:01:37,080
comprovar el valor dels pares i veure - bé, caram,

753
01:01:37,080 --> 01:01:41,990
si el valor dels pares és menor que el valor del corrent,

754
01:01:41,990 --> 01:01:54,440
llavors fill dret dels pares ha de ser el nou node;

755
01:01:54,440 --> 01:02:07,280
en cas contrari, fill esquerre del pare hauria de ser el node nou.

756
01:02:07,280 --> 01:02:10,290
Però, no tenim aquest punter pare encara.

757
01:02:10,290 --> 01:02:15,010
>> Per aconseguir-ho, estem en realitat haurà de seguir a mesura que avancem a través de l'arbre

758
01:02:15,010 --> 01:02:18,440
i trobar el lloc adequat en el nostre bucle anterior.

759
01:02:18,440 --> 01:02:26,840
Podem fer-ho de nou, desplaçant-se fins la part superior de la nostra funció d'inserció

760
01:02:26,840 --> 01:02:32,350
i el seguiment d'una altra variable punter anomenat el pare.

761
01:02:32,350 --> 01:02:39,340
Anem a posar igual a null inicialment,

762
01:02:39,340 --> 01:02:43,640
i llavors cada vegada que passem per l'arbre,

763
01:02:43,640 --> 01:02:51,540
anem a establir el punter pare perquè coincideixi amb el punter actual.

764
01:02:51,540 --> 01:02:59,140
Establir pare igual act.

765
01:02:59,140 --> 01:03:02,260
D'aquesta manera, cada vegada que anem a través,

766
01:03:02,260 --> 01:03:05,550
anem a garantir que, com l'actual punter s'incrementa

767
01:03:05,550 --> 01:03:12,640
el punter del pare que segueix - només un nivell més alt que l'actual punter en l'arbre.

768
01:03:12,640 --> 01:03:17,370
Que tot es veu molt bé.

769
01:03:17,370 --> 01:03:22,380
>> Crec que l'única cosa que anem a voler ajustar és construir aquest node nul retorn.

770
01:03:22,380 --> 01:03:25,380
Per tal d'aconseguir construir node per tornar realitat amb èxit nul,

771
01:03:25,380 --> 01:03:31,060
haurem de modificar el codi,

772
01:03:31,060 --> 01:03:37,270
perquè aquí, mai hem provat per assegurar-se que malloc retorna un punter vàlid.

773
01:03:37,270 --> 01:03:53,390
Així, si (n = NULL), llavors -

774
01:03:53,390 --> 01:03:55,250
si malloc retorna un punter vàlid, llavors anem a inicialitzar;

775
01:03:55,250 --> 01:04:02,540
en cas contrari, només haurem de tornar i que acabarà retornant un valor nul per a nosaltres.

776
01:04:02,540 --> 01:04:13,050
Ara tot es veu molt bé. Ens assegurarem que això realment compila.

777
01:04:13,050 --> 01:04:22,240
Feu arbre binari, i oh, tenim algunes coses que estan passant aquí.

778
01:04:22,240 --> 01:04:29,230
>> Tenim una declaració implícita de la funció de construir node.

779
01:04:29,230 --> 01:04:31,950
Un cop més, amb aquests compiladors, anem a començar a la part superior.

780
01:04:31,950 --> 01:04:36,380
El que això vol dir és que estic trucant a construir node abans que jo he fet el va declarar.

781
01:04:36,380 --> 01:04:37,730
Tornem al codi molt ràpid.

782
01:04:37,730 --> 01:04:43,510
Desplaceu-vos cap avall i, per descomptat, la meva funció d'inserció es declara

783
01:04:43,510 --> 01:04:47,400
per sobre de la funció de node de generació,

784
01:04:47,400 --> 01:04:50,070
però estic tractant d'usar construir node dins del inserit.

785
01:04:50,070 --> 01:05:06,610
Vaig a entrar i copiar - enganxar i després el node de generació manera funció aquí a la part superior.

786
01:05:06,610 --> 01:05:11,750
D'aquesta manera, és d'esperar que funcioni. Anem a donar aquesta altra oportunitat.

787
01:05:11,750 --> 01:05:18,920
Ara tot es compila. Tot està bé.

788
01:05:18,920 --> 01:05:21,640
>> Però en aquest punt, no han cridat la nostra funció d'inserció.

789
01:05:21,640 --> 01:05:26,510
Només sabem que compila, així que anirem i posar algunes trucades polz

790
01:05:26,510 --> 01:05:28,240
Farem que en la funció principal.

791
01:05:28,240 --> 01:05:32,390
En aquest sentit, comentada 5, 8, i 2,

792
01:05:32,390 --> 01:05:36,680
i després no els cable fins aquí.

793
01:05:36,680 --> 01:05:41,640
Farem algunes trucades per inserir,

794
01:05:41,640 --> 01:05:46,440
i també utilitzarem el mateix tipus de coses que hem utilitzat

795
01:05:46,440 --> 01:05:52,810
quan vam fer aquestes trucades printf per assegurar-se que tot el que t'ha inserit correctament.

796
01:05:52,810 --> 01:06:00,550
Vaig a copiar i enganxar,

797
01:06:00,550 --> 01:06:12,450
i conté en lloc que farem d'inserció.

798
01:06:12,450 --> 01:06:30,140
I en comptes de 6, 10 i 1, que utilitzarem 5, 8 i 2.

799
01:06:30,140 --> 01:06:37,320
Això hauria inserir 5, 8, i 2 en l'arbre.

800
01:06:37,320 --> 01:06:44,050
Compilació. Tot està bé. Ara estem realment s'executarà el nostre programa.

801
01:06:44,050 --> 01:06:47,330
>> Tot el torna false.

802
01:06:47,330 --> 01:06:53,830
Així, 5, 8 i 2 no anar, i sembla que conté no els va trobar tampoc.

803
01:06:53,830 --> 01:06:58,890
Què està passant? Anem a reduir.

804
01:06:58,890 --> 01:07:02,160
El primer problema va ser que s'insereixen semblava tornar falsa,

805
01:07:02,160 --> 01:07:08,750
i sembla que això és perquè ens vam anar al nostre call return false,

806
01:07:08,750 --> 01:07:14,590
i que en realitat mai va tornar realitat.

807
01:07:14,590 --> 01:07:17,880
Podem posar això en marxa.

808
01:07:17,880 --> 01:07:25,290
El segon problema és que ara fins i tot si ho fem - guardar això, surti d'això,

809
01:07:25,290 --> 01:07:34,530
fer funcionar de nou, han compilar, a continuació, executeu-lo -

810
01:07:34,530 --> 01:07:37,670
veiem que alguna cosa més va passar aquí.

811
01:07:37,670 --> 01:07:42,980
El 5, 8, i 2 mai es troben encara a l'arbre.

812
01:07:42,980 --> 01:07:44,350
Llavors, què està passant?

813
01:07:44,350 --> 01:07:45,700
>> Anem a fer una ullada a això en el codi.

814
01:07:45,700 --> 01:07:49,790
A veure si podem resoldre això.

815
01:07:49,790 --> 01:07:57,940
Comencem amb el pare no és nul.

816
01:07:57,940 --> 01:07:59,510
Hem establert el punter actual és igual al punter arrel,

817
01:07:59,510 --> 01:08:04,280
i treballarem nostre camí cap avall a través de l'arbre.

818
01:08:04,280 --> 01:08:08,650
Si el node actual no és nul, llavors sabem que podem baixar una mica.

819
01:08:08,650 --> 01:08:12,330
Hem creat el nostre punter pare per ser igual al punter actual,

820
01:08:12,330 --> 01:08:15,420
comprovat el valor - que els valors són els mateixos que vam tornar falsa.

821
01:08:15,420 --> 01:08:17,540
Si els valors són menors que ens mudem a la dreta;

822
01:08:17,540 --> 01:08:20,399
en cas contrari, ens traslladem a l'esquerra.

823
01:08:20,399 --> 01:08:24,220
A continuació, es construeix un node. Vaig a ampliar una mica.

824
01:08:24,220 --> 01:08:31,410
I aquí, anem a tractar de cablejar els valors a ser el mateix.

825
01:08:31,410 --> 01:08:37,250
Què està passant? A veure si possiblement Valgrind pot donar-nos una pista.

826
01:08:37,250 --> 01:08:43,910
>> M'agrada utilitzar Valgrind Valgrind només perquè corre molt ràpid

827
01:08:43,910 --> 01:08:46,729
i et diu si hi ha errors de memòria.

828
01:08:46,729 --> 01:08:48,300
Quan correm Valgrind en el codi,

829
01:08:48,300 --> 01:08:55,859
com poden veure afectats here--Valgrind./binary_tree--and dret entrar.

830
01:08:55,859 --> 01:09:03,640
Ja veus que no tenia cap error de memòria, així que sembla que tot està bé fins ara.

831
01:09:03,640 --> 01:09:07,529
Tenim algunes pèrdues de memòria, el que coneixem, perquè no som

832
01:09:07,529 --> 01:09:08,910
passant a alliberar a qualsevol dels nostres nodes.

833
01:09:08,910 --> 01:09:13,050
Intentarem executar GDB per veure el que realment està passant.

834
01:09:13,050 --> 01:09:20,010
Farem gdb. / Binary_tree. Es arrencat bé.

835
01:09:20,010 --> 01:09:23,670
Anem a posar un punt d'interrupció de la plaqueta.

836
01:09:23,670 --> 01:09:28,600
Anem a córrer.

837
01:09:28,600 --> 01:09:31,200
Sembla que mai ens diu en realitat inserció.

838
01:09:31,200 --> 01:09:39,410
Sembla que el problema era que quan em vaig canviar aquí a principal -

839
01:09:39,410 --> 01:09:44,279
totes aquestes trucades de printf conté -

840
01:09:44,279 --> 01:09:56,430
En realitat, mai va canviar immediatament a trucar inserció.

841
01:09:56,430 --> 01:10:01,660
Ara anem a donar-li una oportunitat. Anem a compilar.

842
01:10:01,660 --> 01:10:09,130
Tot es veu bé. Ara anem a tractar d'executar, a veure què passa.

843
01:10:09,130 --> 01:10:13,320
Molt bé! Tot es veu molt bé.

844
01:10:13,320 --> 01:10:18,130
>> L'última cosa a considerar és, hi ha casos límit a aquesta inserció?

845
01:10:18,130 --> 01:10:23,170
I resulta que, bé, el cas extrem que és sempre interessant pensar

846
01:10:23,170 --> 01:10:26,250
És a dir, què passa si l'arbre està buit i es crida a aquesta funció d'inserció?

847
01:10:26,250 --> 01:10:30,330
Funcionarà? Bé, anem a donar-li una oportunitat.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
La manera com anem a provar això, anirem a la nostra funció principal,

850
01:10:35,810 --> 01:10:41,690
i en lloc de cablejat d'aquests nodes d'aquesta manera,

851
01:10:41,690 --> 01:10:56,730
només comentarem tota la cosa,

852
01:10:56,730 --> 01:11:02,620
i en comptes de nosaltres mateixos cablejant els nodes,

853
01:11:02,620 --> 01:11:09,400
en realitat podem simplement seguir endavant i esborrar tot això.

854
01:11:09,400 --> 01:11:17,560
Anem a fer tot el que una crida a inserir.

855
01:11:17,560 --> 01:11:49,020
Per tant, farem - en comptes de 5, 8 i 2, anem a inserir 7, 3, i 9.

856
01:11:49,020 --> 01:11:58,440
I després també voldrà inserir 6 també.

857
01:11:58,440 --> 01:12:05,190
Guardar. Sortir. Fer arbre binari.

858
01:12:05,190 --> 01:12:08,540
Tot compila.

859
01:12:08,540 --> 01:12:10,320
Només es pot executar com està i veure què passa,

860
01:12:10,320 --> 01:12:12,770
però també serà molt important per assegurar-se que

861
01:12:12,770 --> 01:12:14,740
no tenim cap error de memòria,

862
01:12:14,740 --> 01:12:16,840
ja que aquest és un dels nostres casos extrems que coneixem.

863
01:12:16,840 --> 01:12:20,150
>> Anem a fer de funciona bé sota Valgrind,

864
01:12:20,150 --> 01:12:28,310
que farem simplement executant Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Sembla que sí que tenen un error d'un context -

866
01:12:31,110 --> 01:12:33,790
tenim aquesta fallada de segmentació.

867
01:12:33,790 --> 01:12:36,690
¿Què ha passat?

868
01:12:36,690 --> 01:12:41,650
Valgrind en realitat ens diu on és.

869
01:12:41,650 --> 01:12:43,050
Reduir una mica.

870
01:12:43,050 --> 01:12:46,040
Sembla que el que està succeint en la nostra funció d'inserció,

871
01:12:46,040 --> 01:12:53,420
on tenim una lectura no vàlida del 4 a la mida d'inserció, la línia 60.

872
01:12:53,420 --> 01:13:03,590
Anem a tornar enrere i veure el que està passant aquí.

873
01:13:03,590 --> 01:13:05,350
Allunyar molt ràpid.

874
01:13:05,350 --> 01:13:14,230
Vull per assegurar-se que no va fins la vora de la pantalla perquè puguem veure tot.

875
01:13:14,230 --> 01:13:18,760
Tire que en una mica. Molt bé.

876
01:13:18,760 --> 01:13:35,030
Desplaceu-vos cap avall, i el problema està aquí.

877
01:13:35,030 --> 01:13:40,120
Què passa si ens posem mans i el nostre node actual ja és nul,

878
01:13:40,120 --> 01:13:44,010
nostre node pare és nul, de manera que si mirem cap amunt a la part superior, a la dreta aquí -

879
01:13:44,010 --> 01:13:47,340
si mai aquest bucle while executa realment

880
01:13:47,340 --> 01:13:52,330
perquè el nostre valor actual és nul - nostra arrel és nul així act és nul -

881
01:13:52,330 --> 01:13:57,810
llavors mai el nostre pare s'estableix en act oa un valor vàlid,

882
01:13:57,810 --> 01:14:00,580
així, els pares també serà nul.

883
01:14:00,580 --> 01:14:03,700
Hem de recordar per comprovar que

884
01:14:03,700 --> 01:14:08,750
en el moment en què ens posem aquí, i començar a accedir valor dels pares.

885
01:14:08,750 --> 01:14:13,190
Llavors, què passa? Bé, si el pare és nul -

886
01:14:13,190 --> 01:14:17,990
if (pare == NULL) - llavors sabem que

887
01:14:17,990 --> 01:14:19,530
no ha d'haver res en l'arbre.

888
01:14:19,530 --> 01:14:22,030
Hem d'estar intentant inserir en l'arrel.

889
01:14:22,030 --> 01:14:32,570
Podem fer això amb només ajustar l'arrel igual al nou node.

890
01:14:32,570 --> 01:14:40,010
Llavors en aquest punt, que en realitat no volen passar per aquestes altres coses.

891
01:14:40,010 --> 01:14:44,780
En canvi, aquí, podem fer bé una cosa-if-else,

892
01:14:44,780 --> 01:14:47,610
o podem combinar tot aquí en una cosa,

893
01:14:47,610 --> 01:14:56,300
però aquí només haurem de fer servir més i fer-ho d'aquesta manera.

894
01:14:56,300 --> 01:14:59,030
Ara, anem a provar per assegurar-se que el nostre pare no és nul

895
01:14:59,030 --> 01:15:02,160
abans d'aquesta realitat tractant d'accedir als seus camps.

896
01:15:02,160 --> 01:15:05,330
Això ens ajudarà a evitar la fallada de segmentació.

897
01:15:05,330 --> 01:15:14,740
Així doncs, deixar de fumar, reduir, compilar, executar.

898
01:15:14,740 --> 01:15:18,130
>> No hi ha errors, però encara tenim un munt de pèrdues de memòria

899
01:15:18,130 --> 01:15:20,650
perquè no alliberar a qualsevol dels nostres nodes.

900
01:15:20,650 --> 01:15:24,350
Però, si anem per aquí i ens fixem en el nostre llistat,

901
01:15:24,350 --> 01:15:30,880
veiem que, bé, sembla que tots els nostres inserits es torna true, la qual cosa és bo.

902
01:15:30,880 --> 01:15:33,050
Els inserits són totes vertaderes,

903
01:15:33,050 --> 01:15:36,670
i després les trucades conté apropiats, són certes.

904
01:15:36,670 --> 01:15:41,510
>> Bona feina! Sembla que has escrit correctament inserit.

905
01:15:41,510 --> 01:15:47,430
Això és tot el que tenim per a la especificació d'aquesta setmana Problema.

906
01:15:47,430 --> 01:15:51,720
Un divertit desafiament és pensar en com vostè aniria a

907
01:15:51,720 --> 01:15:55,340
i lliure de tots els nodes d'aquest arbre.

908
01:15:55,340 --> 01:15:58,830
Podem fer un nombre de maneres diferents,

909
01:15:58,830 --> 01:16:01,930
però ho deixo a vostè per experimentar,

910
01:16:01,930 --> 01:16:06,080
i com un repte divertit, intentar assegurar-se que vostè pot assegurar-se que

911
01:16:06,080 --> 01:16:09,490
que aquest informe Valgrind troba cap error i sense fuites.

912
01:16:09,490 --> 01:16:12,880
>> Bona sort en el set d'aquesta setmana Huffman problema de codificació,

913
01:16:12,880 --> 01:16:14,380
i ens veiem la propera setmana!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]