1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Sección 7] [menos cómodo]

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

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

4
00:00:07,000 --> 00:00:09,080
>> Benvido á sección 7.

5
00:00:09,080 --> 00:00:11,330
Grazas ao furacán Sandy,

6
00:00:11,330 --> 00:00:13,440
en vez de ter unha sección normal esta semana

7
00:00:13,440 --> 00:00:17,650
estamos facendo este paso a paso, a través da sección de preguntas.

8
00:00:17,650 --> 00:00:22,830
Eu vou estar a seguir, xunto co conxunto de problemas 6 especificación,

9
00:00:22,830 --> 00:00:25,650
e pasando por todas as preguntas do

10
00:00:25,650 --> 00:00:27,770
A Sección de sección de Preguntas.

11
00:00:27,770 --> 00:00:30,940
Se hai algunha dúbida,

12
00:00:30,940 --> 00:00:32,960
por favor publicar estes en CS50 discutir.

13
00:00:32,960 --> 00:00:35,480
>> Todo ben. Imos comezar.

14
00:00:35,480 --> 00:00:40,780
Agora eu estou ollando para a páxina 3 da especificación conxunto de problemas.

15
00:00:40,780 --> 00:00:44,110
Nós imos primeiro comezar a falar sobre árbores binarias

16
00:00:44,110 --> 00:00:47,850
unha vez que estes teñen moita relevancia para o conxunto desta semana - problema

17
00:00:47,850 --> 00:00:49,950
a codificación árbore Huffman.

18
00:00:49,950 --> 00:00:55,000
Unha das estruturas de datos primeiras falamos sobre CS50 foi a matriz.

19
00:00:55,000 --> 00:01:00,170
Lembre que unha matriz é unha secuencia de elementos -

20
00:01:00,170 --> 00:01:04,019
todos do mesmo tipo, - almacenados xunto uns dos outros na memoria.

21
00:01:04,019 --> 00:01:14,420
Se eu tivera unha matriz de enteiros que eu poida deseñar usando este estilo de caixas números-enteiros -

22
00:01:14,420 --> 00:01:20,290
Imos dicir que eu teño 5 na primeira caixa, eu teño sete no segundo,

23
00:01:20,290 --> 00:01:27,760
entón teño 8, 10, e 20 na caixa final.

24
00:01:27,760 --> 00:01:33,000
Cousas Lembre, os dous realmente boas sobre esta matriz

25
00:01:33,000 --> 00:01:38,800
son de que temos ese acceso e de tempo constante para calquera elemento específico

26
00:01:38,800 --> 00:01:40,500
 na matriz, se sabemos seu índice.

27
00:01:40,500 --> 00:01:44,670
Por exemplo, se eu queira incorporarse o terceiro elemento na matriz -

28
00:01:44,670 --> 00:01:47,870
no índice 2, usando o noso sistema de indexación baseada en cero -

29
00:01:47,870 --> 00:01:52,220
Eu literalmente só tes que facer un simple cálculo matemático,

30
00:01:52,220 --> 00:01:56,170
hop para esa posición na matriz,

31
00:01:56,170 --> 00:01:57,840
puxe o 8 que está almacenado alí,

32
00:01:57,840 --> 00:01:59,260
e eu son bo para ir.

33
00:01:59,260 --> 00:02:03,350
>> Unha das cousas malas sobre esta matriz - que falou sobre

34
00:02:03,350 --> 00:02:05,010
cando discutimos listas ligadas -

35
00:02:05,010 --> 00:02:09,120
é que se eu queira inserir un elemento para esa matriz,

36
00:02:09,120 --> 00:02:11,090
Vou ter que facer algunha mudanza por aí.

37
00:02:11,090 --> 00:02:12,940
Por exemplo, a matriz iso aquí

38
00:02:12,940 --> 00:02:16,850
é na orde de clasificación - clasificados en orde crecente -

39
00:02:16,850 --> 00:02:19,440
5, a continuación, 7, 8, a continuación, a continuación, 10, e despois 20 -

40
00:02:19,440 --> 00:02:23,100
pero se eu queira inserir o seu número 9 desta matriz,

41
00:02:23,100 --> 00:02:27,460
Vou ter que cambiar algúns dos elementos a fin de facer o espazo.

42
00:02:27,460 --> 00:02:30,440
Podemos chamar iso aquí.

43
00:02:30,440 --> 00:02:35,650
Vou ter que mover a 5, o 7 e, a continuación, a 8;

44
00:02:35,650 --> 00:02:38,720
crear un espazo onde podo poñer o 9,

45
00:02:38,720 --> 00:02:45,910
e, a continuación, a 10 ea 20 pode ir á dereita do 9.

46
00:02:45,910 --> 00:02:49,450
Este é un tipo de dor, porque no peor escenario -

47
00:02:49,450 --> 00:02:54,350
cando estamos tendo que introducir ou no inicio ou no final

48
00:02:54,350 --> 00:02:56,040
da matriz, dependendo de como estamos cambiando -

49
00:02:56,040 --> 00:02:58,850
podemos acabar tendo que cambiar todos os elementos

50
00:02:58,850 --> 00:03:00,750
que estamos actualmente a almacenar na matriz.

51
00:03:00,750 --> 00:03:03,810
>> Entón, o que era a maneira de evitar isto?

52
00:03:03,810 --> 00:03:09,260
O xeito de evitar isto era para ir ao noso método de lista encadeada, onde -

53
00:03:09,260 --> 00:03:19,820
en vez de almacenar os elementos 5, 7, 8, 10, e 20 todas próximas unhas das outras na memoria -

54
00:03:19,820 --> 00:03:25,630
o que, en vez fixo foi almacena-los tipo de onde nos queria para almacena-los

55
00:03:25,630 --> 00:03:32,470
nestes nós Linked-lista que eu estou deseñando aquí, tipo de ad hoc.

56
00:03:32,470 --> 00:03:42,060
E, entón, conectado-los en conxunto, utilizando estes punteiros próximos.

57
00:03:42,060 --> 00:03:44,370
I pode ter un punteiro a partir de 5 a 7,

58
00:03:44,370 --> 00:03:46,420
un punteiro a partir do 7 ao 8,

59
00:03:46,420 --> 00:03:47,770
un punteiro a partir do 8 ao 10,

60
00:03:47,770 --> 00:03:51,220
e, finalmente, un punteiro de 10 a 20,

61
00:03:51,220 --> 00:03:54,880
e, a continuación, un punteiro nulo no 20, indicando que non hai nada de esquerda.

62
00:03:54,880 --> 00:03:59,690
O trade-off que temos aquí

63
00:03:59,690 --> 00:04:05,360
é que agora se pretende introducir o número 9 na nosa lista ordenada,

64
00:04:05,360 --> 00:04:08,270
todo o que temos que facer é crear un novo nodo con 9,

65
00:04:08,270 --> 00:04:12,290
fío-lo para apuntar para o lugar apropiado,

66
00:04:12,290 --> 00:04:20,630
e, a continuación, re-conexión do 8 ao apuntar para abaixo para o 9.

67
00:04:20,630 --> 00:04:25,660
Isto é moi rápido, asumir que sabemos exactamente onde queremos inserir o 9.

68
00:04:25,660 --> 00:04:32,610
Pero o trade-off a cambio para iso é que temos agora perdeu o acceso de tempo constante

69
00:04:32,610 --> 00:04:36,230
para calquera elemento particular na nosa estrutura de datos.

70
00:04:36,230 --> 00:04:40,950
Por exemplo, se quero atopar o cuarto elemento nesta lista ligada,

71
00:04:40,950 --> 00:04:43,510
Vou ter que comezar ben no inicio da lista

72
00:04:43,510 --> 00:04:48,930
e traballar o meu camiño a través da conta no a nó ata atopar o cuarto.

73
00:04:48,930 --> 00:04:55,870
>> Co fin de obter un rendemento mellor acceso do que unha lista ligada -

74
00:04:55,870 --> 00:04:59,360
pero tamén manter algúns dos beneficios que tivemos

75
00:04:59,360 --> 00:05:01,800
en termos de tempo de inserción a partir dunha lista ligada -

76
00:05:01,800 --> 00:05:05,750
unha árbore binaria está indo a necesidade de usar a memoria un pouco máis.

77
00:05:05,750 --> 00:05:11,460
En particular, en vez de ter só un punteiro en un nó de árbore binaria -

78
00:05:11,460 --> 00:05:13,350
como a lista ligada nodo fai -

79
00:05:13,350 --> 00:05:16,950
imos engadir un segundo punteiro para o nó de árbore binaria.

80
00:05:16,950 --> 00:05:19,950
En vez de ter só un punteiro para o próximo elemento,

81
00:05:19,950 --> 00:05:24,420
imos ter un punteiro para un neno esquerdo e un dereito do neno.

82
00:05:24,420 --> 00:05:26,560
>> Imos tomar unha foto para ver o que realmente parece.

83
00:05:26,560 --> 00:05:31,350
Unha vez máis, eu vou usar esas caixas e frechas.

84
00:05:31,350 --> 00:05:37,150
Un nodo da árbore binaria vai comezar con só unha caixa simple.

85
00:05:37,150 --> 00:05:40,940
Vai ter un espazo para o valor,

86
00:05:40,940 --> 00:05:47,280
e despois tamén vai ter un espazo para o neno esquerda e dereita do neno.

87
00:05:47,280 --> 00:05:49,280
Eu estou indo a clasificalos los aquí.

88
00:05:49,280 --> 00:05:57,560
Nós imos ter o fillo esquerdo, e entón nós imos ter o fillo dereito.

89
00:05:57,560 --> 00:05:59,920
Hai moitas formas diferentes de facer iso.

90
00:05:59,920 --> 00:06:02,050
Ás veces para o espazo e conveniencia,

91
00:06:02,050 --> 00:06:06,460
Eu, en realidade, deseña-lo como eu estou facendo aquí abaixo

92
00:06:06,460 --> 00:06:10,910
onde eu vou ter o valor superior,

93
00:06:10,910 --> 00:06:14,060
e despois o fillo da dereita no ángulo inferior dereito,

94
00:06:14,060 --> 00:06:16,060
e neno á esquerda na parte inferior esquerda.

95
00:06:16,060 --> 00:06:20,250
Volvendo a este diagrama superior,

96
00:06:20,250 --> 00:06:22,560
temos o valor superior,

97
00:06:22,560 --> 00:06:25,560
entón temos o punteiro esquerdo neno, e despois temos o punteiro neno dereito.

98
00:06:25,560 --> 00:06:30,110
>> Na especificación conxunto de problemas,

99
00:06:30,110 --> 00:06:33,110
falamos de deseñar un nodo que ten un valor de 7,

100
00:06:33,110 --> 00:06:39,750
e un punteiro-esquerda neno que é nulo, e un punteiro dereito do neno, que é nulo.

101
00:06:39,750 --> 00:06:46,040
Nós pode escribir NULL capital no espazo de

102
00:06:46,040 --> 00:06:51,610
tanto o neno como a esquerda e dereita do neno, ou podemos chamar esta barra diagonal

103
00:06:51,610 --> 00:06:53,750
en cada unha das caixas, para indicar que é nula.

104
00:06:53,750 --> 00:06:57,560
Eu vou facer iso só porque é máis sinxelo.

105
00:06:57,560 --> 00:07:03,700
O que ve aquí son dúas formas de diagramação dun nodo árbore moi simple binario

106
00:07:03,700 --> 00:07:07,960
onde temos o valor 7 e punteiros neno nulos.

107
00:07:07,960 --> 00:07:15,220
>> A segunda parte fala sobre como os nosos especificación con listas ligadas -

108
00:07:15,220 --> 00:07:18,270
Lembre, temos só a soster o primeiro elemento dunha lista

109
00:07:18,270 --> 00:07:20,270
para lembrar a listaxe -

110
00:07:20,270 --> 00:07:26,140
e do mesmo xeito, con unha árbore binaria, só temos que soster un punteiro para a árbore

111
00:07:26,140 --> 00:07:31,120
, A fin de manter o control sobre a estrutura de datos enteira.

112
00:07:31,120 --> 00:07:36,150
Este elemento especial da árbore chámase nó raíz da árbore.

113
00:07:36,150 --> 00:07:43,360
Por exemplo, se ese nodo un - este nodo que contén o valor 7

114
00:07:43,360 --> 00:07:45,500
con punteiros nulos lados esquerdo e dereito do neno -

115
00:07:45,500 --> 00:07:47,360
eran o único valor na nosa árbore,

116
00:07:47,360 --> 00:07:50,390
entón este sería o noso nodo raíz.

117
00:07:50,390 --> 00:07:52,240
É o inicio da nosa árbore.

118
00:07:52,240 --> 00:07:58,530
Podemos ver isto un pouco máis claramente, unha vez que comece a engadir máis nós a nosa árbore.

119
00:07:58,530 --> 00:08:01,510
Déixame sacar a unha nova páxina.

120
00:08:01,510 --> 00:08:05,000
>> Agora imos debuxar unha árbore que ten 7 na raíz,

121
00:08:05,000 --> 00:08:10,920
e 3 dentro do neno á esquerda, e 9 no interior do neno dereita.

122
00:08:10,920 --> 00:08:13,500
De novo, iso é moi sinxelo.

123
00:08:13,500 --> 00:08:26,510
Temos 7, debuxe un nó para o 3, un nó para 9,

124
00:08:26,510 --> 00:08:32,150
e eu estou indo a definir o punteiro esquerdo neno de 7 a apuntar para o nodo que contén 3,

125
00:08:32,150 --> 00:08:37,850
E o punteiro dereito do fillo do nodo que contén 7 para o nodo que contén 9.

126
00:08:37,850 --> 00:08:42,419
Agora, desde 3 e 9 non ten fillos,

127
00:08:42,419 --> 00:08:48,500
imos definir os seus punteiros fillo para ser nulo.

128
00:08:48,500 --> 00:08:56,060
Aquí, a raíz da nosa árbore corresponde ao nodo que contén o número 7.

129
00:08:56,060 --> 00:09:02,440
Podes ver que, se todo o que temos é un punteiro para o nodo raíz,

130
00:09:02,440 --> 00:09:07,330
entón podemos camiñar a través da nosa árbore e acceder nós tanto o neno -

131
00:09:07,330 --> 00:09:10,630
ambos os 3 e 9.

132
00:09:10,630 --> 00:09:14,820
Non hai necesidade de manter punteiro a cada nó na árbore.

133
00:09:14,820 --> 00:09:22,080
Todo ben. Agora imos engadir outro nodo a este diagrama.

134
00:09:22,080 --> 00:09:25,370
Estamos indo para engadir un nodo que contén 6,

135
00:09:25,370 --> 00:09:34,140
e nós estamos indo para engadir este como o fillo dereito do nodo contén 3.

136
00:09:34,140 --> 00:09:41,850
Para facer isto, eu vou borrar este punteiro nulo no 3-no

137
00:09:41,850 --> 00:09:47,750
e conecta-lo para apuntar para o nodo que contén 6. Todo ben.

138
00:09:47,750 --> 00:09:53,800
>> Neste punto, imos falar sobre un pouco de terminoloxía.

139
00:09:53,800 --> 00:09:58,230
Para comezar, a razón pola que iso é chamado dunha árbore binaria en particular

140
00:09:58,230 --> 00:10:00,460
é que ten dous punteiros de nenos.

141
00:10:00,460 --> 00:10:06,020
Existen outros tipos de árbores que teñen máis enlaces neno.

142
00:10:06,020 --> 00:10:10,930
En particular, fixo un 'try' no Conxunto Problema 5.

143
00:10:10,930 --> 00:10:19,310
Vostede vai entender que aquel intento, tivo 27 indicacións distintas para os diferentes nenos -

144
00:10:19,310 --> 00:10:22,410
un para cada unha das 26 letras do alfabeto inglés,

145
00:10:22,410 --> 00:10:25,410
e despois a 27 para o apóstrofo -

146
00:10:25,410 --> 00:10:28,900
así, que é semellante a un tipo de árbore.

147
00:10:28,900 --> 00:10:34,070
Pero aquí, xa que é binario, só temos dous punteiros do neno.

148
00:10:34,070 --> 00:10:37,880
>> Ademais deste nodo raíz que falamos,

149
00:10:37,880 --> 00:10:41,470
Nós tamén estamos xogando en torno a este termo "neno".

150
00:10:41,470 --> 00:10:44,470
O que significa para un nodo a un fillo de outro no?

151
00:10:44,470 --> 00:10:54,060
É, literalmente, significa que un nodo fillo é un fillo de outro no

152
00:10:54,060 --> 00:10:58,760
que outro nó ten unha das súas nenos punteiros definidas para apuntar a este nodo.

153
00:10:58,760 --> 00:11:01,230
Para poñer isto en termos máis concretos,

154
00:11:01,230 --> 00:11:11,170
3 é apuntada por un dos punteiros neno de 7, a continuación, 3 é un neno de 7.

155
00:11:11,170 --> 00:11:14,510
Se tivésemos de descubrir o que os fillos de 7 son -

156
00:11:14,510 --> 00:11:18,510
ben, vemos que 7 ten un punteiro para 3 e un punteiro a 9,

157
00:11:18,510 --> 00:11:22,190
para 9 e 3 son os nenos de 7.

158
00:11:22,190 --> 00:11:26,650
Nove non ten fillos porque punteiros seus fillos son nulos,

159
00:11:26,650 --> 00:11:30,940
e 3 ten só un fillo, 6.

160
00:11:30,940 --> 00:11:37,430
Seis tampouco ten fillos, porque ambos os punteiros son nulos, o que nós imos chamar agora.

161
00:11:37,430 --> 00:11:45,010
>> Ademais, tamén falamos sobre os pais dun nodo,

162
00:11:45,010 --> 00:11:51,100
e este é, como sería de esperar, o reverso desta descrición neno.

163
00:11:51,100 --> 00:11:58,620
Cada nodo ten só un pai - en vez de dous, como podería esperar cos humanos.

164
00:11:58,620 --> 00:12:03,390
Por exemplo, a matriz de 3 a 7.

165
00:12:03,390 --> 00:12:10,800
O pai de 9 tamén é 7, o pai e de 6 a 3. Non hai moito a el.

166
00:12:10,800 --> 00:12:15,720
Tamén temos condicións de falar avós e netos,

167
00:12:15,720 --> 00:12:18,210
e, máis xeralmente falamos sobre os antepasados

168
00:12:18,210 --> 00:12:20,960
e descendentes dun nodo específico.

169
00:12:20,960 --> 00:12:25,710
O ancestral dun nodo - ou antepasados, si, un nó -

170
00:12:25,710 --> 00:12:32,730
son todos os nós que están no camiño da raíz para este nodo.

171
00:12:32,730 --> 00:12:36,640
Por exemplo, se eu estou ollando para o 6,

172
00:12:36,640 --> 00:12:46,430
a continuación, os antepasados ​​van ser o 3 eo 7.

173
00:12:46,430 --> 00:12:55,310
Os devanceiros de 9, por exemplo, son - se eu estou ollando para o nodo 9 -

174
00:12:55,310 --> 00:12:59,990
a continuación, o antepasado de 9 é só 7.

175
00:12:59,990 --> 00:13:01,940
E descendentes son exactamente o contrario.

176
00:13:01,940 --> 00:13:05,430
Se quero ollar para todos os descendentes de 7,

177
00:13:05,430 --> 00:13:11,020
entón eu teño que mirar para todos os nós, abaixo dela.

178
00:13:11,020 --> 00:13:16,950
Entón, eu teño 3, 9 e 6 todos como descendentes de 7.

179
00:13:16,950 --> 00:13:24,170
>> O prazo final que imos falar é esta noción de ser un irmán.

180
00:13:24,170 --> 00:13:27,980
Irmáns - tipo de seguir xunto con estes termos familiares -

181
00:13:27,980 --> 00:13:33,150
son nos que están ao mesmo nivel da árbore.

182
00:13:33,150 --> 00:13:42,230
Entón, 3 e 9 son irmáns porque son ao mesmo nivel na árbore.

183
00:13:42,230 --> 00:13:46,190
Ambos teñen o mesmo pai, 7.

184
00:13:46,190 --> 00:13:51,400
O 6 non ten irmáns, porque 9 non teñen fillos.

185
00:13:51,400 --> 00:13:55,540
E 7 non ten irmáns, porque é a raíz da nosa árbore,

186
00:13:55,540 --> 00:13:59,010
e sempre hai só unha raíz.

187
00:13:59,010 --> 00:14:02,260
Para 7 ter irmáns non tería que ser un nodo por riba de 7.

188
00:14:02,260 --> 00:14:07,480
Tería que ser un pai de 7, caso en que 7 xa non sería a raíz da árbore.

189
00:14:07,480 --> 00:14:10,480
Entón que o pai novo, de 7 tamén tería que ter un fillo,

190
00:14:10,480 --> 00:14:16,480
e que o neno sería, entón, o irmán de 7.

191
00:14:16,480 --> 00:14:21,040
>> Todo ben. Seguindo adiante.

192
00:14:21,040 --> 00:14:24,930
Cando comezamos a nosa discusión sobre árbores binarias,

193
00:14:24,930 --> 00:14:28,790
falamos de como nós iamos usalos para

194
00:14:28,790 --> 00:14:32,800
gañar unha vantaxe sobre os dous matrices e listas ligadas.

195
00:14:32,800 --> 00:14:37,220
E a forma como imos facelo é con esta propiedade pedido.

196
00:14:37,220 --> 00:14:41,080
Dicimos que unha árbore binaria é ordenada, de acordo coa especificación,

197
00:14:41,080 --> 00:14:45,740
se, para cada nodo na nosa árbore, todos os seus descendentes á esquerda -

198
00:14:45,740 --> 00:14:48,670
o neno esquerda e todos os descendentes do fillo esquerdo de -

199
00:14:48,670 --> 00:14:54,510
teñen valores menores, e todos os nós da dereita -

200
00:14:54,510 --> 00:14:57,770
o dereito do neno e todos os descendentes de dereito do neno a -

201
00:14:57,770 --> 00:15:02,800
ter nós máis que o valor do nodo actual que estamos mirando.

202
00:15:02,800 --> 00:15:07,850
Só para simplificar, imos asumir que non hai nos duplicados na nosa árbore.

203
00:15:07,850 --> 00:15:11,180
Por exemplo, nesta árbore que non estamos indo para xestionar o caso

204
00:15:11,180 --> 00:15:13,680
onde temos o valor 7 na raíz

205
00:15:13,680 --> 00:15:16,720
 e despois tamén temos o valor 7 noutras partes da árbore.

206
00:15:16,720 --> 00:15:24,390
Neste caso, vai entender que esta árbore é de feito ordenado.

207
00:15:24,390 --> 00:15:26,510
Temos o valor 7 na raíz.

208
00:15:26,510 --> 00:15:29,720
Todo para a esquerda, de 7 -

209
00:15:29,720 --> 00:15:35,310
se eu desfacer todas esas pequenas marcas aquí -

210
00:15:35,310 --> 00:15:40,450
todo á esquerda, de 7 - 3 ea 6 -

211
00:15:40,450 --> 00:15:49,410
eses valores están a menos de 7, e todo para a dereita - o que é exactamente iso 9 -

212
00:15:49,410 --> 00:15:53,450
é maior que 7.

213
00:15:53,450 --> 00:15:58,650
>> Esta non é a única árbore ordenados conteñen estes valores,

214
00:15:58,650 --> 00:16:03,120
pero imos deseñar un pouco máis deles.

215
00:16:03,120 --> 00:16:05,030
Hai realmente unha morea de formas que podemos facer iso.

216
00:16:05,030 --> 00:16:09,380
Vou usar un atallo só para manter as cousas simples, onde -

217
00:16:09,380 --> 00:16:11,520
en vez de deseñar a todo caixas-e-flechas -

218
00:16:11,520 --> 00:16:14,220
Eu só vou para deseñar os números e engadir frechas conectando-los.

219
00:16:14,220 --> 00:16:22,920
Para comezar, imos escribir a nosa árbore orixinal de novo, onde tivemos 7, e despois un 3,

220
00:16:22,920 --> 00:16:25,590
e despois 3 apuntou para o dereito á 6,

221
00:16:25,590 --> 00:16:30,890
e 7 tivo un fillo dereito que tiña 9 anos.

222
00:16:30,890 --> 00:16:33,860
Todo ben. O que é outra forma que podemos escribir esta árbore?

223
00:16:33,860 --> 00:16:38,800
En vez de ter 3 ser o fillo esquerdo de 7,

224
00:16:38,800 --> 00:16:41,360
Tamén poderiamos ter a 6 ser o fillo esquerdo de 7,

225
00:16:41,360 --> 00:16:44,470
e despois 3 ser o fillo esquerdo do 6.

226
00:16:44,470 --> 00:16:48,520
Que sería coma esta árbore aquí onde eu teño 7,

227
00:16:48,520 --> 00:16:57,860
despois 6, despois 3, e un 9 do lado dereito.

228
00:16:57,860 --> 00:17:01,490
Tamén non hai que ter 7 como o noso nodo raíz.

229
00:17:01,490 --> 00:17:03,860
Tamén poderiamos ter 6 como o noso nodo raíz.

230
00:17:03,860 --> 00:17:06,470
O que isto parece?

231
00:17:06,470 --> 00:17:09,230
Se imos manter esta propiedade ordenada,

232
00:17:09,230 --> 00:17:12,970
todo á esquerda do 6 ten que ser menos do que iso.

233
00:17:12,970 --> 00:17:16,540
Hai só unha posibilidade, e iso é 3.

234
00:17:16,540 --> 00:17:19,869
Pero, entón, como o dereito do neno de 6, temos dúas posibilidades.

235
00:17:19,869 --> 00:17:25,380
En primeiro lugar, pódese ter a 7 e, a continuación, o 9,

236
00:17:25,380 --> 00:17:28,850
ou poderiamos chamar iso - como eu estou a piques de facer aquí -

237
00:17:28,850 --> 00:17:34,790
onde temos o 9 como o dereito do neno o 6,

238
00:17:34,790 --> 00:17:39,050
e logo a 7 como o fillo esquerdo do 9.

239
00:17:39,050 --> 00:17:44,240
>> Agora, 7 e 6 non son os únicos valores posibles para a raíz.

240
00:17:44,240 --> 00:17:50,200
Tamén poderiamos ter 3 estar na raíz.

241
00:17:50,200 --> 00:17:52,240
Qué acontece se 3 é a raíz?

242
00:17:52,240 --> 00:17:54,390
Aquí, as cousas están un pouco máis interesante.

243
00:17:54,390 --> 00:17:58,440
Tres non ten valores que son menos que isto,

244
00:17:58,440 --> 00:18:02,070
Así que o lado esquerdo enteiro da árbore é só vai ser nulo.

245
00:18:02,070 --> 00:18:03,230
Non vai ser nada alí.

246
00:18:03,230 --> 00:18:07,220
Á dereita, podemos enumerar as cousas en orde crecente.

247
00:18:07,220 --> 00:18:15,530
Poderiamos ter 3, e logo 6, despois 7, a continuación, 9.

248
00:18:15,530 --> 00:18:26,710
Ou, poderiamos facer 3, despois 6, despois 9, despois 7.

249
00:18:26,710 --> 00:18:35,020
Ou, poderiamos facer 3, despois 7, despois 6, despois 9.

250
00:18:35,020 --> 00:18:40,950
Ou, 3, 7 - na verdade, non, non podemos facer un 7 máis.

251
00:18:40,950 --> 00:18:43,330
Esa é a nosa única cousa alí.

252
00:18:43,330 --> 00:18:54,710
Podemos facer 9, e despois dende o 9 podemos facer 6 e 7.

253
00:18:54,710 --> 00:19:06,980
Ou, pode-se facer-3, e logo 9, a continuación, 7, e, a continuación, 6.

254
00:19:06,980 --> 00:19:12,490
>> Unha cousa de chamar a atención aquí é

255
00:19:12,490 --> 00:19:14,510
que estas árbores son un pouco esquisito.

256
00:19:14,510 --> 00:19:17,840
En particular, se olharmos para as catro árbores no lado dereito -

257
00:19:17,840 --> 00:19:20,930
Vou circular-los, aquí -

258
00:19:20,930 --> 00:19:28,410
estas árbores parecen case exactamente como unha lista ligada.

259
00:19:28,410 --> 00:19:32,670
Cada nodo ten só un fillo,

260
00:19:32,670 --> 00:19:38,950
e así non temos nada diso estrutura de árbore que vemos, por exemplo,

261
00:19:38,950 --> 00:19:44,720
 nesta árbore un solitario aquí na parte inferior esquerda.

262
00:19:44,720 --> 00:19:52,490
Estas árbores son chamadas realmente dexenerada árbores binarias,

263
00:19:52,490 --> 00:19:54,170
e nós imos falar sobre estes máis futuro -

264
00:19:54,170 --> 00:19:56,730
especialmente se seguir a facer cursos de ciencias outros computadores.

265
00:19:56,730 --> 00:19:59,670
Estas árbores son dexenerados.

266
00:19:59,670 --> 00:20:03,780
Eles non son moi útiles, pois, de feito, esa estrutura se presta

267
00:20:03,780 --> 00:20:08,060
 a procura de veces semellantes aos dunha lista ligada.

268
00:20:08,060 --> 00:20:13,050
Nós non temos aproveitar a memoria extra - este punteiro extra -

269
00:20:13,050 --> 00:20:18,840
por mor da nosa estrutura ser malo así.

270
00:20:18,840 --> 00:20:24,700
En vez de ir e tirar as árbores binarias que nove na raíz,

271
00:20:24,700 --> 00:20:27,220
Que é o caso final que tería,

272
00:20:27,220 --> 00:20:32,380
estamos en vez diso, neste momento, vou falar un pouco sobre ese outro termo

273
00:20:32,380 --> 00:20:36,150
que usan ao falar sobre as árbores, que se chama a altura.

274
00:20:36,150 --> 00:20:45,460
>> A altura dunha árbore é a distancia a partir da raíz para o nó de máis distante,

275
00:20:45,460 --> 00:20:48,370
ou mellor, o número de saltos que tería que facer a fin de

276
00:20:48,370 --> 00:20:53,750
comezar a partir da raíz e despois acaban no nodo máis distante na árbore.

277
00:20:53,750 --> 00:20:57,330
Se miramos para algunhas destas árbores que temos deseñado aquí,

278
00:20:57,330 --> 00:21:07,870
podemos ver que, se tomamos esta árbore na esquina superior esquerda e comezamos a 3,

279
00:21:07,870 --> 00:21:14,510
entón temos que facer un salto para chegar ao 6, un segundo salto para chegar ao 7,

280
00:21:14,510 --> 00:21:20,560
e un terceiro hop para chegar ao 9.

281
00:21:20,560 --> 00:21:26,120
Entón, a altura da árbore é de 3.

282
00:21:26,120 --> 00:21:30,640
Podemos facer o mesmo exercicio para as outras árbores descritas con este verde,

283
00:21:30,640 --> 00:21:40,100
e podemos ver que a altura de todas estas árbores é tamén certo 3.

284
00:21:40,100 --> 00:21:45,230
Isto é parte do que os fai dexenerada -

285
00:21:45,230 --> 00:21:53,750
que a súa altura é só un a menos que o número de nós en toda a árbore.

286
00:21:53,750 --> 00:21:58,400
Se olharmos para esta outra árbore que está rodeada con vermello, por outra banda,

287
00:21:58,400 --> 00:22:03,920
vemos que os nós máis distantes da folla son o 6 eo 9 -

288
00:22:03,920 --> 00:22:06,940
o deixa de ser os nós que non teñen fillos.

289
00:22:06,940 --> 00:22:11,760
Así, a fin de obter a partir do nó de raíz, tanto a 6 ou 9,

290
00:22:11,760 --> 00:22:17,840
temos que facer un salto para chegar ao 7 e, a continuación, un segundo salto para chegar ao 9,

291
00:22:17,840 --> 00:22:21,240
e do mesmo xeito, só o salto de un segundo a partir do 7 para obter a 6.

292
00:22:21,240 --> 00:22:29,080
Así, a altura desta árbore aquí é só 2.

293
00:22:29,080 --> 00:22:35,330
Vostede pode volver e facelo para todas as outras árbores que previamente discutido

294
00:22:35,330 --> 00:22:37,380
comezando co 7 e a 6,

295
00:22:37,480 --> 00:22:42,500
e podes ver que a altura de todas as árbores tamén é 2.

296
00:22:42,500 --> 00:22:46,320
>> A razón pola que temos falado sobre ordenou árbores binarias

297
00:22:46,320 --> 00:22:50,250
e por que son legais porque pode buscar por eles en

298
00:22:50,250 --> 00:22:53,810
unha forma moi semellante á procura dun array ordenado.

299
00:22:53,810 --> 00:22:58,720
Este é o lugar onde se fala de conseguir que o tempo de busca mellorada

300
00:22:58,720 --> 00:23:02,730
sobre a lista ligada simple.

301
00:23:02,730 --> 00:23:05,010
Cunha lista ligada - se quere atopar un elemento particular -

302
00:23:05,010 --> 00:23:07,470
está no mellor vai facer algún tipo de busca lineal

303
00:23:07,470 --> 00:23:10,920
onde comeza o inicio dunha lista de correo-hop un-por-un -

304
00:23:10,920 --> 00:23:12,620
un nó, un nó -

305
00:23:12,620 --> 00:23:16,060
toda a lista ata atopar o que está a procurar.

306
00:23:16,060 --> 00:23:19,440
Considerando que, se ten unha árbore binaria que está almacenado neste formato agradable,

307
00:23:19,440 --> 00:23:23,300
realmente pode ser máis de unha busca binaria suceder

308
00:23:23,300 --> 00:23:25,160
onde dividir e conquistar

309
00:23:25,160 --> 00:23:29,490
e investigación a través da metade apropiada da árbore de cada etapa.

310
00:23:29,490 --> 00:23:32,840
Imos ver como funciona isto.

311
00:23:32,840 --> 00:23:38,850
>> Se temos - de novo, volvendo a nosa árbore orixinal -

312
00:23:38,850 --> 00:23:46,710
comezamos a 7, que teñen 3, á esquerda, á dereita 9,

313
00:23:46,710 --> 00:23:51,740
e baixo a 3 temos a 6.

314
00:23:51,740 --> 00:24:01,880
Se queremos buscar o número 6 na árbore, nós iniciar na raíz.

315
00:24:01,880 --> 00:24:08,910
Nós comparar o valor que estamos a buscar, digamos 6,

316
00:24:08,910 --> 00:24:12,320
ao valor almacenado no nodo que nós estamos a buscar, aos 7,

317
00:24:12,320 --> 00:24:21,200
descubrir que 6 é de feito menor que 7, entón mover á esquerda.

318
00:24:21,200 --> 00:24:25,530
Se o valor de 6 fora superior a 7, que tería lugar movido cara á dereita.

319
00:24:25,530 --> 00:24:29,770
Como sabemos que - debido á estrutura da nosa árbore binaria ordenada -

320
00:24:29,770 --> 00:24:33,910
todos os valores menos que 7 serán almacenadas á esquerda, de 7,

321
00:24:33,910 --> 00:24:40,520
non hai necesidade de incomodar mesmo mirando polo lado dereito da árbore.

322
00:24:40,520 --> 00:24:43,780
Unha vez que se mover á esquerda e agora estamos no nodo que contén 3,

323
00:24:43,780 --> 00:24:48,110
podemos facelo de novo mesmo comparación, onde se compara o 3 eo 6.

324
00:24:48,110 --> 00:24:52,430
E descubrimos que, mentres 6 - o valor que estamos a buscar - é maior que 3,

325
00:24:52,430 --> 00:24:58,580
que pode ir para o lado dereito do nodo contén 3.

326
00:24:58,580 --> 00:25:02,670
Non hai á esquerda aquí, polo tanto, podería ter ignorado iso.

327
00:25:02,670 --> 00:25:06,510
Pero só sabemos que xa nós estamos mirando para a propia árbore,

328
00:25:06,510 --> 00:25:08,660
e podemos ver que a árbore non ten fillos.

329
00:25:08,660 --> 00:25:13,640
>> Tamén é moi fácil mirar para arriba 6 nesta árbore estamos facendo a nós mesmos como seres humanos,

330
00:25:13,640 --> 00:25:16,890
pero imos seguir ese proceso mecánicamente como un ordenador faría

331
00:25:16,890 --> 00:25:18,620
para realmente entender o algoritmo.

332
00:25:18,620 --> 00:25:26,200
Neste punto, estamos agora mirando para un nodo que contén 6,

333
00:25:26,200 --> 00:25:29,180
e nós estamos mirando para o valor 6,

334
00:25:29,180 --> 00:25:31,740
así, en verdade, atopamos o no apropiado.

335
00:25:31,740 --> 00:25:35,070
Atopamos o valor 6 na nosa árbore, e podemos deixar a nosa procura.

336
00:25:35,070 --> 00:25:37,330
Neste punto, dependendo do que está a suceder,

337
00:25:37,330 --> 00:25:41,870
podemos dicir, si, atopamos o valor 6, que existe na nosa árbore.

338
00:25:41,870 --> 00:25:47,640
Ou, se estamos a planear para inserir un nodo ou facer algo, podemos facelo neste momento.

339
00:25:47,640 --> 00:25:53,010
>> Imos facer buscas algunhas só para ver como funciona isto.

340
00:25:53,010 --> 00:25:59,390
Vexamos o que pasa se fósemos probar e mirar para arriba o valor 10.

341
00:25:59,390 --> 00:26:02,970
Se estivésemos a mirar para arriba o valor 10, que ía comezar na raíz.

342
00:26:02,970 --> 00:26:07,070
Vemos que 10 é maior que 7, así que mover á dereita.

343
00:26:07,070 --> 00:26:13,640
Teriamos a 9 e comparar 9 ao 10 e mira que 9 é realmente inferior a 10.

344
00:26:13,640 --> 00:26:16,210
Entón, de novo, que ía tentar mover á dereita.

345
00:26:16,210 --> 00:26:20,350
Pero, neste punto, a xente entende que estamos nun nodo nulo.

346
00:26:20,350 --> 00:26:23,080
Non hai nada alí. Non hai nada que o 10 debe ser.

347
00:26:23,080 --> 00:26:29,360
Este é o lugar onde podemos informar fallo - que en realidade non hai 10 na árbore.

348
00:26:29,360 --> 00:26:35,420
E, finalmente, imos percorrer o caso en que estamos a tentar buscar unha na árbore.

349
00:26:35,420 --> 00:26:38,790
Isto é semellante ao que acontece cando miramos cara arriba 10, excepto en vez de ir para a dereita,

350
00:26:38,790 --> 00:26:41,260
Estamos indo para ir á esquerda.

351
00:26:41,260 --> 00:26:46,170
Nós comezamos no 7, e ver que unha é inferior a 7, de xeito que se mover cara á esquerda.

352
00:26:46,170 --> 00:26:51,750
Chegamos ao 3 e ver que 1 é menor que 3, polo tanto, unha vez máis, tentar mover á esquerda.

353
00:26:51,750 --> 00:26:59,080
Neste punto temos un nodo nulo, entón, de novo, podemos denunciar o fracaso.

354
00:26:59,080 --> 00:27:10,260
>> Se queres saber máis sobre árbores binarias,

355
00:27:10,260 --> 00:27:14,420
hai unha morea de diversión pequenos problemas que pode facer con eles.

356
00:27:14,420 --> 00:27:19,450
Eu suxiro facer o deseño destes diagramas un-por-un

357
00:27:19,450 --> 00:27:21,910
e despois a través de todos os pasos diferentes,

358
00:27:21,910 --> 00:27:25,060
porque iso virá a super-accesible

359
00:27:25,060 --> 00:27:27,480
non só cando está facendo a Huffman conxunto de problemas de codificación

360
00:27:27,480 --> 00:27:29,390
pero tamén en cursos futuros -

361
00:27:29,390 --> 00:27:32,220
só aprender a sacar esas estruturas de datos e reflexionar sobre os problemas

362
00:27:32,220 --> 00:27:38,000
con pluma e papel, ou, neste caso do iPad, e pluma.

363
00:27:38,000 --> 00:27:41,000
>> Neste punto, porén, imos pasar a facer algunha práctica de codificación

364
00:27:41,000 --> 00:27:44,870
e realmente xogar con esas árbores binarias e ver.

365
00:27:44,870 --> 00:27:52,150
Vou volver para o meu ordenador.

366
00:27:52,150 --> 00:27:58,480
Para esta parte da sección, en vez de usar CS50 CS50 Executar ou espazos,

367
00:27:58,480 --> 00:28:01,500
Vou usar o aparello.

368
00:28:01,500 --> 00:28:04,950
>> Tras xunto coa especificación do conxunto de problemas,

369
00:28:04,950 --> 00:28:07,740
Eu vexo que eu teño que abrir o dispositivo,

370
00:28:07,740 --> 00:28:11,020
ir á miña carpeta Dropbox, cree unha carpeta chamada Sección 7,

371
00:28:11,020 --> 00:28:15,730
e, entón, crear un arquivo chamado binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Aquí imos nós. Eu teño o aparello xa está aberta.

373
00:28:22,050 --> 00:28:25,910
Vou tirar un terminal.

374
00:28:25,910 --> 00:28:38,250
Eu estou indo a ir á carpeta Dropbox, cree un directorio chamado Sección 7,

375
00:28:38,250 --> 00:28:42,230
e ver que é totalmente baleiro.

376
00:28:42,230 --> 00:28:48,860
Agora vou abrir binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Todo ben. Aquí imos nós - Arquivo baleiro.

378
00:28:51,750 --> 00:28:54,330
>> Imos volver con especificación.

379
00:28:54,330 --> 00:28:59,850
A especificación pide para crear unha nova definición de tipo

380
00:28:59,850 --> 00:29:03,080
para un nodo árbore binaria conteñen valores int -

381
00:29:03,080 --> 00:29:07,110
así como os valores que sacou na nosa diagramação antes.

382
00:29:07,110 --> 00:29:11,740
Nós imos usar ese cliché typedef que fixemos aquí

383
00:29:11,740 --> 00:29:14,420
que ten que recoñecer de conxunto de problemas 5 -

384
00:29:14,420 --> 00:29:19,190
se fixo o camiño táboa hash do programa conquistando o Speller.

385
00:29:19,190 --> 00:29:22,540
Tamén debe recoñece-lo da sección da semana pasada

386
00:29:22,540 --> 00:29:23,890
onde falamos sobre listas ligadas.

387
00:29:23,890 --> 00:29:27,870
Temos este typedef dun nodo de estrutura,

388
00:29:27,870 --> 00:29:34,430
e demos a este nodo struct este nome de nodo struct previamente

389
00:29:34,430 --> 00:29:39,350
para que poidamos, a continuación refírense a el, xa que vai querer ter punteiros nodo struct

390
00:29:39,350 --> 00:29:45,740
como parte da nosa estrutura, pero entón cercaron iso -

391
00:29:45,740 --> 00:29:47,700
ou antes, esta pechada - nun typedef

392
00:29:47,700 --> 00:29:54,600
de xeito que, ao final do código, que pode referirse a esa estrutura como só un nó no canto dun nodo de estrutura.

393
00:29:54,600 --> 00:30:03,120
>> Isto vai ser moi semellante á definición de lista individualmente-vinculado que vimos a semana pasada.

394
00:30:03,120 --> 00:30:20,070
Para iso, imos comezar por escribir o cliché.

395
00:30:20,070 --> 00:30:23,840
Sabemos que temos que ter un valor enteiro,

396
00:30:23,840 --> 00:30:32,170
entón imos poñer en valor int, e despois, no canto de ter só un punteiro para o próximo elemento -

397
00:30:32,170 --> 00:30:33,970
como fixemos co illadamente conectados listas -

398
00:30:33,970 --> 00:30:38,110
imos ter punteiros neno esquerdo e dereito.

399
00:30:38,110 --> 00:30:42,880
Isto é moi sinxelo tamén - struct fillo do nodo * esquerda;

400
00:30:42,880 --> 00:30:51,190
e struct nodo fillo dereito *;. Cool.

401
00:30:51,190 --> 00:30:54,740
Isto parece un bo comezo.

402
00:30:54,740 --> 00:30:58,530
Imos volver con especificación.

403
00:30:58,530 --> 00:31:05,030
>> Agora necesitamos declarar unha variable * mundial no a raíz dunha árbore.

404
00:31:05,030 --> 00:31:10,590
Nós imos facer este global como fixemos punteiro primeiro na nosa lista ligada tamén global.

405
00:31:10,590 --> 00:31:12,690
Este foi, de xeito que nas funcións que escriben

406
00:31:12,690 --> 00:31:16,180
non temos que manter esta pasando en torno a raíz -

407
00:31:16,180 --> 00:31:19,620
pero imos ver que se quere escribir estas funcións de forma recursiva,

408
00:31:19,620 --> 00:31:22,830
quizais sexa mellor non mesmo pasalo en torno a como unha empresa global, en primeiro lugar

409
00:31:22,830 --> 00:31:28,090
e, en vez arrincar-lo localmente na súa función principal.

410
00:31:28,090 --> 00:31:31,960
Pero, imos facelo globalmente para comezar.

411
00:31:31,960 --> 00:31:39,920
Unha vez máis, imos dar un par de espazos, e eu vou declarar unha raíz * nodo.

412
00:31:39,920 --> 00:31:46,770
Só para estar seguro que non deixe este non inicializar, eu estou indo a define-la igual a null.

413
00:31:46,770 --> 00:31:52,210
Agora, na función principal - o que imos escribir moi rapidamente 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
e eu vou comezar declarando miña matriz argv como const só así que eu sei

416
00:32:10,640 --> 00:32:14,550
que estes argumentos son argumentos que eu probablemente non queren modificar.

417
00:32:14,550 --> 00:32:18,390
Se eu queira modificalo los eu probablemente debería estar facendo copias deles.

418
00:32:18,390 --> 00:32:21,740
Vai ver moito iso no código.

419
00:32:21,740 --> 00:32:25,440
É bo de calquera maneira. É bo deixalo como - omitir a const se desexa.

420
00:32:25,440 --> 00:32:28,630
Eu normalmente poñelas só para que eu me lembrar

421
00:32:28,630 --> 00:32:33,650
 que probablemente non queren modificar eses argumentos.

422
00:32:33,650 --> 00:32:39,240
>> Como sempre, eu estou indo a incluír este retorno 0 ao final do principal.

423
00:32:39,240 --> 00:32:45,730
Aquí, vou comezar o meu nó de raíz.

424
00:32:45,730 --> 00:32:48,900
Tal e como está agora, eu teño un punteiro que está definido como nulo,

425
00:32:48,900 --> 00:32:52,970
por iso está a apuntar cara a nada.

426
00:32:52,970 --> 00:32:57,480
A fin de que realmente comezar a construír o nó,

427
00:32:57,480 --> 00:32:59,250
Eu primeiro teño reservar memoria para el.

428
00:32:59,250 --> 00:33:05,910
Eu vou facer iso, facendo memoria na pila empregando malloc.

429
00:33:05,910 --> 00:33:10,660
Eu estou indo para definir raíz igual ao resultado de malloc,

430
00:33:10,660 --> 00:33:19,550
e eu vou usar o operador sizeof para calcular o tamaño dun nodo.

431
00:33:19,550 --> 00:33:24,990
A razón que eu uso no sizeof ao contrario, digamos,

432
00:33:24,990 --> 00:33:37,020
facer algo así - malloc (4 + 4 +4) ou malloc 12 -

433
00:33:37,020 --> 00:33:40,820
é porque quero o meu código para ser o máis compatible posible.

434
00:33:40,820 --> 00:33:44,540
Eu quero ser capaz de tomar isto. Arquivo c, recompila-lo no seu dispositivo,

435
00:33:44,540 --> 00:33:48,820
e despois recompila-lo no meu 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
ou sobre unha arquitectura completamente diferente -

437
00:33:52,040 --> 00:33:54,640
e quero que todo para o mesmo traballo.

438
00:33:54,640 --> 00:33:59,510
>> Se eu estou facendo suposicións sobre o tamaño de variables -

439
00:33:59,510 --> 00:34:02,070
o tamaño dun int ou o tamaño dun punteiro -

440
00:34:02,070 --> 00:34:06,070
entón eu tamén estou facendo suposicións sobre os tipos de arquitecturas

441
00:34:06,070 --> 00:34:10,440
en que o meu código pode compilar con éxito cando sexa executado.

442
00:34:10,440 --> 00:34:15,030
Sempre use sizeof ao contrario manualmente suma dos campos de estruturas.

443
00:34:15,030 --> 00:34:20,500
A outra razón é que tamén pode haber recheo que o compilador pon na estrutura.

444
00:34:20,500 --> 00:34:26,570
Mesmo só sumar os campos individuais non é algo que normalmente quere facer,

445
00:34:26,570 --> 00:34:30,340
así, eliminar a liña.

446
00:34:30,340 --> 00:34:33,090
Agora, para realmente iniciar este nodo raíz,

447
00:34:33,090 --> 00:34:36,489
Vou ter que conectar os valores de cada un dos seus diferentes campos.

448
00:34:36,489 --> 00:34:41,400
Por exemplo, para o valor que sei que quero para arrincar 7,

449
00:34:41,400 --> 00:34:46,920
e agora eu estou indo a definir o fillo esquerdo de ser nulo

450
00:34:46,920 --> 00:34:55,820
e do dereito do neno a ser tamén nulo. Gran!

451
00:34:55,820 --> 00:35:02,670
Nós fixemos iso parte da especificación.

452
00:35:02,670 --> 00:35:07,390
>> A especificación para abaixo na parte inferior da páxina 3 me pide para crear tres máis nós -

453
00:35:07,390 --> 00:35:10,600
un contendo 3, un contendo 6, e un 9 -

454
00:35:10,600 --> 00:35:14,210
e, a continuación, conecta-los de xeito que parece exactamente como o noso diagrama de árbore

455
00:35:14,210 --> 00:35:17,120
que estabamos falando anteriormente.

456
00:35:17,120 --> 00:35:20,450
Imos facelo ben rápido aquí.

457
00:35:20,450 --> 00:35:26,270
Vai ver moi rapidamente que eu vou comezar a escribir unha morea de código duplicado.

458
00:35:26,270 --> 00:35:32,100
Eu estou indo para crear un nó * e eu vou chamalo de tres.

459
00:35:32,100 --> 00:35:36,000
Eu estou indo a define-la igual a malloc (sizeof (nó)).

460
00:35:36,000 --> 00:35:41,070
Eu estou indo para definir tres-> valor = 3.

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

462
00:35:54,780 --> 00:36:01,150
Isto parece moi semellante ao inicializar a raíz, e iso é o que

463
00:36:01,150 --> 00:36:05,760
Vou ter que facer se eu comezar a arrincar 6 e 9 tamén.

464
00:36:05,760 --> 00:36:20,720
Vou facelo moi rapidamente aquí - na verdade, eu vou facer unha copia pouco e pegar,

465
00:36:20,720 --> 00:36:46,140
e asegúrese de que - todo ben.

466
00:36:46,470 --> 00:37:09,900
 Agora, eu teño que copiar e podo ir adiante e establecer esta igual a 6.

467
00:37:09,900 --> 00:37:14,670
Podes ver que iso leva tempo e non é super-eficiente.

468
00:37:14,670 --> 00:37:22,610
En só un pouco, imos escribir unha función que vai facelo por nós.

469
00:37:22,610 --> 00:37:32,890
Quero substituír iso cun 9, substitúa que, cun 6.

470
00:37:32,890 --> 00:37:37,360
>> Agora temos todos os nosos nós creado e inicializar.

471
00:37:37,360 --> 00:37:41,200
Temos a nosa raíz definido igual a 7, ou que contén o valor 7,

472
00:37:41,200 --> 00:37:46,510
nosa nodo contén 3, o noso nodo que contén 6, e contén o nodo 9.

473
00:37:46,510 --> 00:37:50,390
Neste punto, todo o que temos que facer é todo o fío cara arriba.

474
00:37:50,390 --> 00:37:53,020
A razón de eu inicializar os punteiros como nulo é só para que eu estar seguro de que

475
00:37:53,020 --> 00:37:56,260
Eu non teño os punteiros non inicializados alí por accidente.

476
00:37:56,260 --> 00:38:02,290
E tamén porque, neste momento, eu só teño que realmente conectar os nós para o outro -

477
00:38:02,290 --> 00:38:04,750
para os que están realmente ligadas a - Eu non teño que pasar e facer

478
00:38:04,750 --> 00:38:08,240
seguro de que todos os nulos están alí nos lugares apropiados.

479
00:38:08,240 --> 00:38:15,630
>> A partir da raíz, sei que fillo esquerda da raíz é 3.

480
00:38:15,630 --> 00:38:21,250
Sei que fillo dereito da raíz é 9.

481
00:38:21,250 --> 00:38:24,880
Despois diso, o fillo único outro que me queda para se preocupar

482
00:38:24,880 --> 00:38:39,080
É dereito do neno 3, que é 6.

483
00:38:39,080 --> 00:38:44,670
Neste punto, todo parece moi bo.

484
00:38:44,670 --> 00:38:54,210
Nós imos eliminar algunhas destas liñas.

485
00:38:54,210 --> 00:38:59,540
Agora todo parece moi bo.

486
00:38:59,540 --> 00:39:04,240
Imos volver para a nosa especificación e ver o que temos que facer a continuación.

487
00:39:04,240 --> 00:39:07,610
>> Neste punto, debemos escribir unha función chamada "contén"

488
00:39:07,610 --> 00:39:14,150
con un prototipo de 'contén bool (valor enteiro).

489
00:39:14,150 --> 00:39:17,060
E este contén función devolverá true

490
00:39:17,060 --> 00:39:21,200
 a árbore apuntada pola nosa variable raíz global

491
00:39:21,200 --> 00:39:26,950
 contén o valor pasado para a función e falso en caso contrario.

492
00:39:26,950 --> 00:39:29,000
Imos adiante e facelo.

493
00:39:29,000 --> 00:39:35,380
Este vai ser exactamente como a investigación que fixemos coa man no iPad un pouco atrás.

494
00:39:35,380 --> 00:39:40,130
Imos zoom un pouco e vai cara arriba.

495
00:39:40,130 --> 00:39:43,130
Nós imos poñer esta función logo enriba a nosa función principal

496
00:39:43,130 --> 00:39:48,990
de modo que non hai que facer calquera tipo de prototipado.

497
00:39:48,990 --> 00:39:55,960
Entón, bool contén (valor enteiro).

498
00:39:55,960 --> 00:40:00,330
Alí imos nós. Non é a nosa declaración cliché.

499
00:40:00,330 --> 00:40:02,900
Só para ter seguro que isto vai compilar,

500
00:40:02,900 --> 00:40:06,820
Eu estou indo a ir adiante e configure-lo igual a voltar falso.

501
00:40:06,820 --> 00:40:09,980
Neste momento esta función só non vai facer nada e sempre relatan que

502
00:40:09,980 --> 00:40:14,010
o valor que estamos a buscar non está na árbore.

503
00:40:14,010 --> 00:40:16,280
>> Neste punto, pode ser unha boa idea -

504
00:40:16,280 --> 00:40:19,600
desde que escribín unha morea de código e non temos sequera intentou proba-lo aínda -

505
00:40:19,600 --> 00:40:22,590
para asegurarse de que todo compila.

506
00:40:22,590 --> 00:40:27,460
Hai un par de cousas que temos que facer para estar seguro de que iso realmente vai compilar.

507
00:40:27,460 --> 00:40:33,530
Primeiro, vexa se estamos usando todas as funcións en calquera biblioteca que aínda non foron incluídas.

508
00:40:33,530 --> 00:40:37,940
As funcións que usan ata agora son malloc,

509
00:40:37,940 --> 00:40:43,310
e entón nós tamén está a usar este tipo - este tipo fóra do estándar chamado 'bool' -

510
00:40:43,310 --> 00:40:45,750
que está incluído no ficheiro de cabeceira estándar bool.

511
00:40:45,750 --> 00:40:53,250
Nós sempre queremos incluír bool.h estándar para o tipo bool,

512
00:40:53,250 --> 00:40:59,230
e nós tamén queremos # include lib.h estándar para as bibliotecas estándar

513
00:40:59,230 --> 00:41:03,530
que inclúen malloc, e libre, e todo iso.

514
00:41:03,530 --> 00:41:08,660
Entón, zoom out, imos deixar de fumar.

515
00:41:08,660 --> 00:41:14,190
Imos tentar e ter seguro de que iso realmente fixo a compilación.

516
00:41:14,190 --> 00:41:18,150
Vemos que fai, entón estamos no camiño correcto.

517
00:41:18,150 --> 00:41:22,990
>> Imos abrir binary_tree.c novo.

518
00:41:22,990 --> 00:41:34,530
El compila. Imos descender e estar seguro de que imos introducir algunhas chamadas nosa función contén -

519
00:41:34,530 --> 00:41:40,130
só para que seguro que iso é todo moi ben.

520
00:41:40,130 --> 00:41:43,170
Por exemplo, cando fixemos algunhas investigacións na nosa árbore máis cedo,

521
00:41:43,170 --> 00:41:48,500
intentamos buscar os 6 valores en 10, e 1, e nós sabiamos que era 6 na árbore,

522
00:41:48,500 --> 00:41:52,220
10 non estaba na árbore, e 1 non estaba na árbore ou.

523
00:41:52,220 --> 00:41:57,230
Imos usar as chamadas de mostras, como forma de descubrir se ou non

524
00:41:57,230 --> 00:41:59,880
nosa función contén funciona.

525
00:41:59,880 --> 00:42:05,210
Co fin de facer iso, eu vou usar a función printf,

526
00:42:05,210 --> 00:42:10,280
e nós estamos indo para imprimir o resultado da chamada contén.

527
00:42:10,280 --> 00:42:13,280
Vou poñer unha cadea "contén (% d) = porque

528
00:42:13,280 --> 00:42:20,470
 imos activar o valor que imos buscar,

529
00:42:20,470 --> 00:42:27,130
e =% s \ n "e usar isto como a nosa secuencia de formato.

530
00:42:27,130 --> 00:42:30,720
Nós só imos ver - literalmente imprimir na pantalla -

531
00:42:30,720 --> 00:42:32,060
o que parece ser unha chamada de función.

532
00:42:32,060 --> 00:42:33,580
Isto non é realmente a chamada de función.

533
00:42:33,580 --> 00:42:36,760
 Esta é só unha secuencia deseñado para parecerse a unha chamada de función.

534
00:42:36,760 --> 00:42:41,140
>> Agora, imos chamar os valores.

535
00:42:41,140 --> 00:42:43,580
Nós imos tratar contén o 6,

536
00:42:43,580 --> 00:42:48,340
e entón o que imos facer aquí é usar o operador ternário.

537
00:42:48,340 --> 00:42:56,340
Imos ver - contén 6 - así, agora contiña 6 e contén 6 é certa,

538
00:42:56,340 --> 00:43:01,850
a cadea que imos enviar o carácter de formato% s

539
00:43:01,850 --> 00:43:04,850
vai ser a cadea "true".

540
00:43:04,850 --> 00:43:07,690
Imos rolar un pouco máis.

541
00:43:07,690 --> 00:43:16,210
En caso contrario, queremos enviar a string "false" se contén seis retorno falsos.

542
00:43:16,210 --> 00:43:19,730
Isto é un pouco tolo bonito, pero eu creo que eu podería moi ben ilustrar

543
00:43:19,730 --> 00:43:23,780
o que o operador ternário parece, xa que non vin el por algún tempo.

544
00:43:23,780 --> 00:43:27,670
Esta será unha forma agradable, útil para descubrir a nosa función contén funciona.

545
00:43:27,670 --> 00:43:30,040
Eu estou indo a rolar de volta cara á esquerda,

546
00:43:30,040 --> 00:43:39,900
e eu vou copiar e pegar esta liña algunhas veces.

547
00:43:39,900 --> 00:43:44,910
El cambiou algúns deses valores ao redor,

548
00:43:44,910 --> 00:43:59,380
polo que este vai ser un, e iso vai ser 10.

549
00:43:59,380 --> 00:44:02,480
>> Neste punto, temos unha función contén agradable.

550
00:44:02,480 --> 00:44:06,080
Temos algunhas probas, e imos ver se esta todo funciona.

551
00:44:06,080 --> 00:44:08,120
Neste punto, teño escrito algúns códigos máis.

552
00:44:08,120 --> 00:44:13,160
Tempo para saír fóra e asegúrese de que todo aínda compila.

553
00:44:13,160 --> 00:44:20,360
Sae fóra, e agora imos tratar de facer árbore binaria de novo.

554
00:44:20,360 --> 00:44:22,260
Ben, parece que temos un erro,

555
00:44:22,260 --> 00:44:26,930
E nós temos esta declarar explicitamente a función de biblioteca printf.

556
00:44:26,930 --> 00:44:39,350
Parece que temos que ir e # include standardio.h.

557
00:44:39,350 --> 00:44:45,350
E, con iso, todo debe compilar. Estamos todos ben.

558
00:44:45,350 --> 00:44:50,420
Agora imos tratar de correr árbore binaria e ver o que acontece.

559
00:44:50,420 --> 00:44:53,520
Aquí estamos nós,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
e vemos que, como se esperaba -

561
00:44:55,190 --> 00:44:56,910
porque non teñen implementado contén aínda,

562
00:44:56,910 --> 00:44:59,800
ou mellor, acabamos de poñer no return false -

563
00:44:59,800 --> 00:45:03,300
vemos que está só retornando teito para todos eles,

564
00:45:03,300 --> 00:45:06,180
Entón iso é todo traballo para a maior parte bastante ben.

565
00:45:06,180 --> 00:45:11,860
>> Imos volver e realmente aplicar contén neste momento.

566
00:45:11,860 --> 00:45:17,490
Eu estou indo a rolar para abaixo, aumentar o zoom, e -

567
00:45:17,490 --> 00:45:22,330
Lembre, o algoritmo que usan foi que comezou no nodo raíz

568
00:45:22,330 --> 00:45:28,010
e en cada nodo que atopamos, facemos unha comparación,

569
00:45:28,010 --> 00:45:32,380
e en base a que a comparación que quere pasar ao fillo esquerdo ou dereito para o neno.

570
00:45:32,380 --> 00:45:39,670
Isto vai parecer moi semellante ao código de búsqueda binaria que escribimos no inicio do prazo.

571
00:45:39,670 --> 00:45:47,810
Cando comezamos, nós sabemos que queremos soster o nodo actual

572
00:45:47,810 --> 00:45:54,050
que estamos mirando, eo nodo actual vai ser inicializar a nó raíz.

573
00:45:54,050 --> 00:45:56,260
E agora, imos continuar a árbore,

574
00:45:56,260 --> 00:45:58,140
e lembre que a nosa condición de deixar -

575
00:45:58,140 --> 00:46:01,870
 cando efectivamente traballadas a través do exemplo a man -

576
00:46:01,870 --> 00:46:03,960
foi cando atopou un nodo nulo,

577
00:46:03,960 --> 00:46:05,480
non cando miramos para un neno nulo,

578
00:46:05,480 --> 00:46:09,620
pero cando realmente mudou-se para un nó na árbore

579
00:46:09,620 --> 00:46:12,640
e descubriu que estamos nun nodo nulo.

580
00:46:12,640 --> 00:46:20,720
Estamos indo para iterar ata actual non é igual a nulo.

581
00:46:20,720 --> 00:46:22,920
E que é o que imos facer?

582
00:46:22,920 --> 00:46:31,610
Nós imos comprobar se (cur -> valor valor ==)

583
00:46:31,610 --> 00:46:35,160
entón sabemos que temos en realidade, o nodo que estamos a buscar.

584
00:46:35,160 --> 00:46:40,450
Entón, aquí, podemos volver true.

585
00:46:40,450 --> 00:46:49,830
En caso contrario, queremos a ver se ou non o valor é menor que o valor.

586
00:46:49,830 --> 00:46:53,850
Se o valor do nodo actual é menor que o valor que está a buscar,

587
00:46:53,850 --> 00:46:57,280
imos pasar para a dereita.

588
00:46:57,280 --> 00:47:10,600
Entón, cur = actual -> right_child, e se non, nós estamos indo para mover á esquerda.

589
00:47:10,600 --> 00:47:17,480
actual actual = -> left_child;. Moi sinxelo.

590
00:47:17,480 --> 00:47:22,830
>> Probablemente recoñece o lazo que se parece moi semellante a este de

591
00:47:22,830 --> 00:47:27,580
busca binaria no inicio do prazo, agás a continuación estabamos lidando con baixa, media e alta.

592
00:47:27,580 --> 00:47:30,000
Aquí, só temos que ollar para un valor actual,

593
00:47:30,000 --> 00:47:31,930
por iso é bo e sinxelo.

594
00:47:31,930 --> 00:47:34,960
Imos ter a certeza de que este código está funcionando.

595
00:47:34,960 --> 00:47:42,780
En primeiro lugar, asegúrese de que compila. Parece que fai.

596
00:47:42,780 --> 00:47:47,920
Imos tentar executa-lo.

597
00:47:47,920 --> 00:47:50,160
E, de feito, ela mostra todo o que esperabamos.

598
00:47:50,160 --> 00:47:54,320
Atopa 6 na árbore, non atopa 10, porque 10 non está na árbore,

599
00:47:54,320 --> 00:47:57,740
e non se atope unha ou porque non é unha tamén na árbore.

600
00:47:57,740 --> 00:48:01,420
Cousas legais.

601
00:48:01,420 --> 00:48:04,470
>> Todo ben. Imos volver para a nosa especificación e ver o que está próximo.

602
00:48:04,470 --> 00:48:07,990
Agora, quere engadir nós algúns para a nosa árbore.

603
00:48:07,990 --> 00:48:11,690
El quere engadir 5, 2 e 8, e asegúrese de que a nosa contén código

604
00:48:11,690 --> 00:48:13,570
aínda funciona como se esperaba.

605
00:48:13,570 --> 00:48:14,900
Imos facelo.

606
00:48:14,900 --> 00:48:19,430
Neste punto, en vez de facer a copia irritante e pegar de novo,

607
00:48:19,430 --> 00:48:23,770
imos escribir unha función para realmente crear un nó.

608
00:48:23,770 --> 00:48:27,740
Se rolar todo o camiño para o inicio, vemos que temos está a facer esta

609
00:48:27,740 --> 00:48:31,210
código moi semellante e outra vez cada vez que queremos crear un nó.

610
00:48:31,210 --> 00:48:39,540
>> Imos escribir unha función que realmente construír un nó para nós e para devolve-lo.

611
00:48:39,540 --> 00:48:41,960
Vou chamalo build_node.

612
00:48:41,960 --> 00:48:45,130
Vou construír un nó cun valor específico.

613
00:48:45,130 --> 00:48:51,040
Zoom aquí.

614
00:48:51,040 --> 00:48:56,600
O primeiro que vou facer é, en realidade, crear espazo para o nodo na pila.

615
00:48:56,600 --> 00:49:05,400
Así, o nó * n = malloc (sizeof (nó)); n - valor> = valor;

616
00:49:05,400 --> 00:49:14,960
e despois aquí, eu estou indo só para arrincar todos os campos para valores apropiados.

617
00:49:14,960 --> 00:49:22,500
E ao final, imos voltar a nosa nodo.

618
00:49:22,500 --> 00:49:28,690
Todo ben. Unha cousa a notar é que esta función aquí

619
00:49:28,690 --> 00:49:34,320
vai voltar un punteiro para a memoria que foi alocada chea.

620
00:49:34,320 --> 00:49:38,880
O que é legal sobre iso é que este nodo agora -

621
00:49:38,880 --> 00:49:42,420
temos que declaralo lo na pila porque se declarou na pila

622
00:49:42,420 --> 00:49:45,050
non sería capaz de facelo nesta función como esta.

623
00:49:45,050 --> 00:49:47,690
Que a memoria vai fóra do alcance

624
00:49:47,690 --> 00:49:51,590
e sería válido se intentamos acceder a ela máis tarde.

625
00:49:51,590 --> 00:49:53,500
Unha vez que estamos declarando pila alocada de memoria,

626
00:49:53,500 --> 00:49:55,830
imos ter que coidar de liberar-lo máis tarde

627
00:49:55,830 --> 00:49:58,530
para o noso programa para non baleirar calquera memoria.

628
00:49:58,530 --> 00:50:01,270
Fomos punting en que a calquera outra cousa no código

629
00:50:01,270 --> 00:50:02,880
só por mor da simplicidade na época,

630
00:50:02,880 --> 00:50:05,610
pero se xa escribir unha función parecida con esta

631
00:50:05,610 --> 00:50:10,370
onde ten - algúns chaman un malloc ou realloc dentro -

632
00:50:10,370 --> 00:50:14,330
quere estar seguro de que poñer algún tipo de comentario por aquí que di:

633
00:50:14,330 --> 00:50:29,970
ei, vostede sabe, retorna un nó pila alocada inicializar o valor pasado-in.

634
00:50:29,970 --> 00:50:33,600
E entón quere estar seguro de que poñer en algún tipo de nota que di

635
00:50:33,600 --> 00:50:41,720
o chamador debe liberar a memoria volveu.

636
00:50:41,720 --> 00:50:45,450
Desta forma, se alguén non vai e utiliza esa función,

637
00:50:45,450 --> 00:50:48,150
eles saben que o que reciben de volta que a función

638
00:50:48,150 --> 00:50:50,870
nalgún momento terá que ser liberado.

639
00:50:50,870 --> 00:50:53,940
>> Asumindo que todo está ben e bo aquí,

640
00:50:53,940 --> 00:51:02,300
podemos ir para abaixo no noso código e substituír todas estas liñas aquí

641
00:51:02,300 --> 00:51:05,410
con chamadas a nosa función de construción.

642
00:51:05,410 --> 00:51:08,170
Imos facelo moi rapidamente.

643
00:51:08,170 --> 00:51:15,840
A única parte que non estamos indo para substituír é esa parte aquí

644
00:51:15,840 --> 00:51:18,520
na parte inferior onde realmente conectar os nós para apuntar para o outro,

645
00:51:18,520 --> 00:51:21,030
porque non podemos facer na nosa función.

646
00:51:21,030 --> 00:51:37,400
Pero, imos facer raíz = build_node (7); nodo * tres = build_node (3);

647
00:51:37,400 --> 00:51:47,980
nó * seis = build_node (6); nodo * nove = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
E agora, nós tamén quería engadir nós para -

649
00:51:52,590 --> 00:52:03,530
nó * cinco = build_node (5); nodo * oito = build_node (8);

650
00:52:03,530 --> 00:52:09,760
e cal foi o outro no? Imos ver aquí. Queriamos tamén engadir un 2 -

651
00:52:09,760 --> 00:52:20,280
nó * dous = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Todo ben. Neste punto, sabemos que temos o 7, o 3, o 9, e os 6

653
00:52:26,850 --> 00:52:30,320
todo ligado de forma adecuada, pero que sobre o 5, o 8, eo 2?

654
00:52:30,320 --> 00:52:33,550
Para manter todo en orde apropiada,

655
00:52:33,550 --> 00:52:39,230
sabemos que neno dereita tres é 6.

656
00:52:39,230 --> 00:52:40,890
Entón, se nós imos engadir a 5,

657
00:52:40,890 --> 00:52:46,670
a 5 tamén pertence ao lado dereito da árbore dos cales 3 é a raíz,

658
00:52:46,670 --> 00:52:50,440
así como 5 pertenza o neno esquerda de 6.

659
00:52:50,440 --> 00:52:58,650
Podemos facer isto por dicir, seis -> left_child = cinco;

660
00:52:58,650 --> 00:53:10,790
e, a continuación, a 8 pertenza como o fillo esquerdo de 9, para nove -> left_child = oito;

661
00:53:10,790 --> 00:53:22,190
e 2 é o fillo esquerdo de tres, para que poidamos facelo aquí - te -> left_child = dous;.

662
00:53:22,190 --> 00:53:27,730
Se non chegou a seguir, xunto con iso, eu sugiro que retirala la só.

663
00:53:27,730 --> 00:53:35,660
>> Todo ben. Imos salvar este. Imos saír e asegurarse de que compila,

664
00:53:35,660 --> 00:53:40,760
e entón podemos engadir ás nosas chamadas contén.

665
00:53:40,760 --> 00:53:44,120
Parece que todo aínda compila.

666
00:53:44,120 --> 00:53:51,790
Imos entrar e engadir en algunhas contén chamadas.

667
00:53:51,790 --> 00:53:59,640
Unha vez máis, eu vou facer un pouco de copiar e pegar.

668
00:53:59,640 --> 00:54:15,860
Agora imos buscar 5, 8 e 2. Todo ben.

669
00:54:15,860 --> 00:54:28,330
Imos estar seguro de que todo isto parece ser bo aínda. Gran! Gardar e saír.

670
00:54:28,330 --> 00:54:33,220
Agora imos facer, compilar, e agora imos realizar.

671
00:54:33,220 --> 00:54:37,540
A partir dos resultados, parece que todo está funcionando moi agradable e ben.

672
00:54:37,540 --> 00:54:41,780
Gran! Entón, agora temos os nosos contén función escrito.

673
00:54:41,780 --> 00:54:46,160
Imos seguir adiante e comezar a traballar en como inserir nós na árbore

674
00:54:46,160 --> 00:54:50,000
unha vez que, como estamos facendo agora, as cousas non son moi bonitas.

675
00:54:50,000 --> 00:54:52,280
>> Se volvemos para a especificación,

676
00:54:52,280 --> 00:55:00,540
que nos pide para escribir unha función chamada introducir - de novo, retornando un bool

677
00:55:00,540 --> 00:55:04,400
para se ou non poderiamos engadir o nodo na árbore -

678
00:55:04,400 --> 00:55:07,710
e, a continuación, o valor para introducir na árbore é especificado como

679
00:55:07,710 --> 00:55:11,060
o único argumento para a nosa función de inserción.

680
00:55:11,060 --> 00:55:18,180
Volveremos realidade se podería de feito introducir o valor do nodo que contén na árbore,

681
00:55:18,180 --> 00:55:20,930
o que significa que un tiña suficiente memoria,

682
00:55:20,930 --> 00:55:24,840
e dous, que o nodo xa non existe na árbore desde entón -

683
00:55:24,840 --> 00:55:32,170
Lembre, non imos ter valores duplicados na árbore, só para facer as cousas simples.

684
00:55:32,170 --> 00:55:35,590
Todo ben. De volta para o código.

685
00:55:35,590 --> 00:55:44,240
Abre-se. Zoom un pouco, a continuación, vai para abaixo.

686
00:55:44,240 --> 00:55:47,220
Imos poñer a función de inserción logo enriba os contén.

687
00:55:47,220 --> 00:55:56,360
Unha vez máis, que vai ser chamado de inserción bool (valor enteiro).

688
00:55:56,360 --> 00:56:01,840
Dele un pouco máis espazo, e entón, como un estándar,

689
00:56:01,840 --> 00:56:08,870
imos poñer en return false ao final.

690
00:56:08,870 --> 00:56:22,620
Agora, na parte inferior, imos adiante e en vez de construír manualmente os nós

691
00:56:22,620 --> 00:56:27,900
na principal nós mesmos e fiación-los para apuntar para o outro como nós estamos facendo,

692
00:56:27,900 --> 00:56:30,600
imos confiar na nosa función de inserción para facelo.

693
00:56:30,600 --> 00:56:35,510
Non imos contar coa nosa función de inserción para construír a árbore enteira a partir de cero aínda,

694
00:56:35,510 --> 00:56:39,970
pero nós imos nos librar destas liñas - imos comentar as liñas -

695
00:56:39,970 --> 00:56:43,430
que construír os 5 nós, 8 e 2.

696
00:56:43,430 --> 00:56:55,740
E en vez diso, imos introducir chamadas nosa función de inserción

697
00:56:55,740 --> 00:57:01,280
para estar seguro de que isto realmente funciona.

698
00:57:01,280 --> 00:57:05,840
Aquí imos nós.

699
00:57:05,840 --> 00:57:09,300
>> Agora que xa comentou estas liñas.

700
00:57:09,300 --> 00:57:13,700
Nós só temos 7, 3, 9 e 6 na nosa árbore neste momento.

701
00:57:13,700 --> 00:57:18,870
Para asegurarse de que todo está funcionando,

702
00:57:18,870 --> 00:57:25,050
podemos reducir, facer a nosa árbore binaria,

703
00:57:25,050 --> 00:57:30,750
executa-lo, e podemos ver que contén agora está nos dicindo que está totalmente seguro -

704
00:57:30,750 --> 00:57:33,110
5, 8, e 2 non na árbore.

705
00:57:33,110 --> 00:57:37,960
Voltar para o código,

706
00:57:37,960 --> 00:57:41,070
e como é que imos inserir?

707
00:57:41,070 --> 00:57:46,290
Teña en conta que o que fixemos cando estabamos realmente a inserción de 5, 8 e 2 anteriormente.

708
00:57:46,290 --> 00:57:50,100
Nós xogamos este xogo Plinko onde comezamos na raíz,

709
00:57:50,100 --> 00:57:52,780
descendeu a unha árbore por un por un

710
00:57:52,780 --> 00:57:54,980
ata atopamos a fenda adecuado,

711
00:57:54,980 --> 00:57:57,570
e, entón, con fío no nó no lugar apropiado.

712
00:57:57,570 --> 00:57:59,480
Nós imos facer o mesmo.

713
00:57:59,480 --> 00:58:04,070
Isto é basicamente como escribir o código que usan no contén función

714
00:58:04,070 --> 00:58:05,910
para atopar o lugar onde o nodo debe ser,

715
00:58:05,910 --> 00:58:10,560
e entón nós só estamos indo a introducir o nó alí mesmo.

716
00:58:10,560 --> 00:58:17,000
Imos comezar a facelo.

717
00:58:17,000 --> 00:58:24,200
>> Polo tanto, temos un nó * cur = raíz; nós só estamos indo a seguir o contén código

718
00:58:24,200 --> 00:58:26,850
ata descubrir que non funciona moi ben para nós.

719
00:58:26,850 --> 00:58:32,390
Nós imos pasar por árbore, mentres que o elemento actual non é nulo,

720
00:58:32,390 --> 00:58:45,280
e atopar o valor que actual é igual ao valor que estamos intentando introducir -

721
00:58:45,280 --> 00:58:49,600
ben, este é un dos casos en que non podería realmente introducir o no

722
00:58:49,600 --> 00:58:52,730
para a árbore, porque iso significa que temos un valor duplicado.

723
00:58:52,730 --> 00:58:59,010
Aquí estamos indo realmente para voltar falso.

724
00:58:59,010 --> 00:59:08,440
Agora outra cousa, o valor actual é menor que o valor,

725
00:59:08,440 --> 00:59:10,930
agora sabemos que imos pasar para a dereita

726
00:59:10,930 --> 00:59:17,190
 porque o valor pertence a metade dereita da árbore cur.

727
00:59:17,190 --> 00:59:30,110
Se non, nós estamos indo para mover á esquerda.

728
00:59:30,110 --> 00:59:37,980
Iso é basicamente nosos contén función alí.

729
00:59:37,980 --> 00:59:41,820
>> Neste punto, unha vez que teñamos completado esta loop while,

730
00:59:41,820 --> 00:59:47,350
noso punteiro actual vai estar apuntando para null

731
00:59:47,350 --> 00:59:51,540
a función non retorno.

732
00:59:51,540 --> 00:59:58,710
Estamos, polo tanto, ter cur no lugar onde desexa inserir o novo nodo.

733
00:59:58,710 --> 01:00:05,210
O que queda por facer é realmente construír o novo nodo,

734
01:00:05,210 --> 01:00:08,480
o que podemos facer moi facilmente.

735
01:00:08,480 --> 01:00:14,930
Podemos usar o noso super-accesíbel función do nó de construción,

736
01:00:14,930 --> 01:00:17,210
é algo que non fixemos antes -

737
01:00:17,210 --> 01:00:21,400
que só un tipo de levou para concedida, pero agora imos facer só para ter seguro -

738
01:00:21,400 --> 01:00:27,130
imos probar para estar seguro de que o valor de retorno polo novo nodo foi realmente

739
01:00:27,130 --> 01:00:33,410
non nulo, porque nós non queremos comezar a acceder á memoria é nulo.

740
01:00:33,410 --> 01:00:39,910
Podemos probar para estar seguro de que novo no non é igual a nulo.

741
01:00:39,910 --> 01:00:42,910
Ou en vez diso, podemos só ver se realmente é nulo,

742
01:00:42,910 --> 01:00:52,120
e é nulo, entón podemos simplemente voltar falso cedo.

743
01:00:52,120 --> 01:00:59,090
>> Neste punto, é preciso conectarse novo no no seu lugar axeitado na árbore.

744
01:00:59,090 --> 01:01:03,510
Se miramos cara atrás, principal e onde estabamos realmente fiación en valores antes,

745
01:01:03,510 --> 01:01:08,470
vemos que o xeito no que nós estabamos facendo iso cando quería poñer 3 na árbore

746
01:01:08,470 --> 01:01:11,750
foi acessamos o fillo esquerdo de raíz.

747
01:01:11,750 --> 01:01:14,920
Cando poñemos nove na árbore, tivemos que acceder ao fillo dereito da raíz.

748
01:01:14,920 --> 01:01:21,030
Tiñamos que ter un punteiro para o pai, a fin de poñer un novo valor para a árbore.

749
01:01:21,030 --> 01:01:24,430
Rolando de volta para introducir, que non vai moito traballar aquí

750
01:01:24,430 --> 01:01:27,550
porque non temos un punteiro pai.

751
01:01:27,550 --> 01:01:31,650
O que se quere ser capaz de facer é, neste punto,

752
01:01:31,650 --> 01:01:37,080
comprobar o valor do pai e ver - ben, caramba,

753
01:01:37,080 --> 01:01:41,990
o valor do pai é menor que o valor actual,

754
01:01:41,990 --> 01:01:54,440
entón o neno o dereito dos pais debe ser o novo nodo;

755
01:01:54,440 --> 01:02:07,280
en caso contrario, fillo esquerdo do pai debe ser o novo nodo.

756
01:02:07,280 --> 01:02:10,290
Pero, non temos este punteiro pai aínda.

757
01:02:10,290 --> 01:02:15,010
>> A fin de obtê-lo, nós imos mesmo ter que segui-lo como nós atravesamos a árbore

758
01:02:15,010 --> 01:02:18,440
e atopar o lugar axeitado no noso loop anterior.

759
01:02:18,440 --> 01:02:26,840
Podemos facelo por desprazamento de volta ata o cumio da nosa función de inserción

760
01:02:26,840 --> 01:02:32,350
e seguimento doutra variable punteiro chamado pai.

761
01:02:32,350 --> 01:02:39,340
Nós imos define-lo igual a nulo, inicialmente,

762
01:02:39,340 --> 01:02:43,640
e entón cada vez que pasar pola árbore,

763
01:02:43,640 --> 01:02:51,540
imos definir o punteiro pai para coincidir co punteiro actual.

764
01:02:51,540 --> 01:02:59,140
Establecer pai igual a cur.

765
01:02:59,140 --> 01:03:02,260
Deste xeito, cada vez que pasar,

766
01:03:02,260 --> 01:03:05,550
imos garantir que, como o punteiro actual é incrementado

767
01:03:05,550 --> 01:03:12,640
o punteiro pai segue - só un nivel máis elevado do que o punteiro actual na árbore.

768
01:03:12,640 --> 01:03:17,370
Iso todo parece moi bo.

769
01:03:17,370 --> 01:03:22,380
>> Eu creo que o único que imos querer axustar é esta compilación nulo nó de retorno.

770
01:03:22,380 --> 01:03:25,380
A fin de obter construír no realmente con éxito voltar nulo,

771
01:03:25,380 --> 01:03:31,060
Nós imos ter que modificar este código,

772
01:03:31,060 --> 01:03:37,270
porque aquí, nunca probado para garantir que malloc retornou un punteiro válido.

773
01:03:37,270 --> 01:03:53,390
Así, (n = NULL!), A continuación, -

774
01:03:53,390 --> 01:03:55,250
se malloc retornou un punteiro válido, entón imos arrincar-lo;

775
01:03:55,250 --> 01:04:02,540
en caso contrario, imos voltar e que vai acabar volvendo nulo para nós.

776
01:04:02,540 --> 01:04:13,050
Agora todo parece moi bo. Imos ter a certeza de que isto realmente compila.

777
01:04:13,050 --> 01:04:22,240
Facer árbore binaria, e Oh, nós temos algunhas cousas a ocorrer aquí.

778
01:04:22,240 --> 01:04:29,230
>> Temos unha declaración implícita da función construír no.

779
01:04:29,230 --> 01:04:31,950
De novo, con estes compiladores, imos comezar na parte superior.

780
01:04:31,950 --> 01:04:36,380
O que ten que dicir é que eu estou chamando construír no antes de realmente declarado.

781
01:04:36,380 --> 01:04:37,730
Imos volver ao código moi rapidamente.

782
01:04:37,730 --> 01:04:43,510
Rolar para abaixo, e con certeza, a miña función de inserción é declarado

783
01:04:43,510 --> 01:04:47,400
enriba da función do nó de construción,

784
01:04:47,400 --> 01:04:50,070
pero eu estou tentando usar construír no interior de inserción.

785
01:04:50,070 --> 01:05:06,610
Eu vou entrar e copia - e despois pega o camiño de construción función do nó aquí arriba.

786
01:05:06,610 --> 01:05:11,750
Desta forma, espero que funcione. Imos dar estoutro ir.

787
01:05:11,750 --> 01:05:18,920
Agora todo compila. Todo é bo.

788
01:05:18,920 --> 01:05:21,640
>> Pero neste momento, non temos realmente chamou a función de inserción.

789
01:05:21,640 --> 01:05:26,510
Nós só sabemos que compila, entón imos entrar e poñer algunhas chamadas dentro

790
01:05:26,510 --> 01:05:28,240
Imos facelo na nosa función principal.

791
01:05:28,240 --> 01:05:32,390
Aquí, nós comentada 5, 8 e 2,

792
01:05:32,390 --> 01:05:36,680
e, despois, non conecta-los aquí.

793
01:05:36,680 --> 01:05:41,640
Imos facer algunhas chamadas para introducir,

794
01:05:41,640 --> 01:05:46,440
e imos usar o mesmo tipo de material que usamos

795
01:05:46,440 --> 01:05:52,810
cando fixemos estas chamadas printf para estar seguro de que todo o que se introducir correctamente.

796
01:05:52,810 --> 01:06:00,550
Vou copiar e pegar,

797
01:06:00,550 --> 01:06:12,450
e en vez de conter imos facer de inserción.

798
01:06:12,450 --> 01:06:30,140
E, en vez de 6, 10 e 1, imos usar 5, 8 e 2.

799
01:06:30,140 --> 01:06:37,320
Isto débese Esperanza introducir 5, 8, e dous para a árbore.

800
01:06:37,320 --> 01:06:44,050
Compilar. Todo é bo. Agora imos executar o noso programa.

801
01:06:44,050 --> 01:06:47,330
>> Todo volveu falso.

802
01:06:47,330 --> 01:06:53,830
Entón, 5, 8 e 2 non foi, e parece que contén non pensou ningunha delas.

803
01:06:53,830 --> 01:06:58,890
O que está a suceder? Imos diminuír o zoom.

804
01:06:58,890 --> 01:07:02,160
O primeiro problema foi que introducir parecía retornar falso,

805
01:07:02,160 --> 01:07:08,750
e parece que iso é porque saímos na nosa chamada de retorno falso,

806
01:07:08,750 --> 01:07:14,590
e nós nunca realmente retornou certo.

807
01:07:14,590 --> 01:07:17,880
Podemos configurar isto.

808
01:07:17,880 --> 01:07:25,290
O segundo problema é que, agora mesmo que facer - gardar este, deixar isto,

809
01:07:25,290 --> 01:07:34,530
executar o make novo, telo compilar, a continuación, executa-lo -

810
01:07:34,530 --> 01:07:37,670
vemos que algo máis pasou aquí.

811
01:07:37,670 --> 01:07:42,980
O 5, 8, e 2 foron aínda non atopou na árbore.

812
01:07:42,980 --> 01:07:44,350
Entón, o que está a suceder?

813
01:07:44,350 --> 01:07:45,700
>> Imos dar un ollo niso no código.

814
01:07:45,700 --> 01:07:49,790
Imos ver se podemos descubrir iso.

815
01:07:49,790 --> 01:07:57,940
Comezamos co pai non ser nulo.

816
01:07:57,940 --> 01:07:59,510
Nós ajustamos o punteiro actual coincide co punteiro raíz,

817
01:07:59,510 --> 01:08:04,280
e nós imos traballar o noso camiño a través da árbore.

818
01:08:04,280 --> 01:08:08,650
Se o nodo actual non é nulo, entón sabemos que podemos mover un pouco para abaixo.

819
01:08:08,650 --> 01:08:12,330
Montar noso punteiro pai para ser igual ao actual do punteiro,

820
01:08:12,330 --> 01:08:15,420
comprobar o valor - se os valores son os mesmos que retornou falso.

821
01:08:15,420 --> 01:08:17,540
Se os valores son menos nos cambiamos para a dereita;

822
01:08:17,540 --> 01:08:20,399
en caso contrario, mudouse para a esquerda.

823
01:08:20,399 --> 01:08:24,220
Entón, imos construír un nó. Vou ampliar un pouco.

824
01:08:24,220 --> 01:08:31,410
E aquí, nós imos tratar conectar os valores a ser o mesmo.

825
01:08:31,410 --> 01:08:37,250
O que está a suceder? Imos ver se posiblemente Valgrind pode dar unha información.

826
01:08:37,250 --> 01:08:43,910
>> Eu gusto de usar Valgrind só porque Valgrind moi rapidamente executado

827
01:08:43,910 --> 01:08:46,729
e dille se hai erros de memoria.

828
01:08:46,729 --> 01:08:48,300
Cando corremos Valgrind no código,

829
01:08:48,300 --> 01:08:55,859
como podes ver hit here--Valgrind./binary_tree--and dereito entrar.

830
01:08:55,859 --> 01:09:03,640
Vostede ve que non ten ningún erro de memoria, polo que parece que está todo ben ata agora.

831
01:09:03,640 --> 01:09:07,529
Temos algúns derrames de memoria, que sabemos, porque non somos

832
01:09:07,529 --> 01:09:08,910
pasando para liberar calquera dos nosos nós.

833
01:09:08,910 --> 01:09:13,050
Imos tentar executar GDB para ver o que está realmente a suceder.

834
01:09:13,050 --> 01:09:20,010
Nós imos facer gdb. / Binary_tree. El iniciou-se moi ben.

835
01:09:20,010 --> 01:09:23,670
Imos definir un punto de ruptura na inserción.

836
01:09:23,670 --> 01:09:28,600
Imos correr.

837
01:09:28,600 --> 01:09:31,200
Parece que nunca realmente chamado de inserción.

838
01:09:31,200 --> 01:09:39,410
Parece que o problema era só que cando eu mudei para aquí en principal -

839
01:09:39,410 --> 01:09:44,279
todas esas chamadas de printf contén -

840
01:09:44,279 --> 01:09:56,430
Eu nunca realmente cambiou destes para chamar de inserción.

841
01:09:56,430 --> 01:10:01,660
Agora imos dar unha oportunidade. Imos compilar.

842
01:10:01,660 --> 01:10:09,130
Todo parece bo alí. Agora imos tratar de executa-lo, ver o que acontece.

843
01:10:09,130 --> 01:10:13,320
Todo ben! Todo parece moi bo alí.

844
01:10:13,320 --> 01:10:18,130
>> A última cousa a pensar é, existen casos de punta a esta entrada?

845
01:10:18,130 --> 01:10:23,170
E ocorre que, así, o caso de borde que sempre é interesante para pensar

846
01:10:23,170 --> 01:10:26,250
, o que pasa se a súa árbore está baleira e chamar esa función de inserción?

847
01:10:26,250 --> 01:10:30,330
Será que vai funcionar? Ben, imos dar unha oportunidade.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
A maneira que nós imos probar que é, estamos indo a ir ata a nosa función principal,

850
01:10:35,810 --> 01:10:41,690
e ao contrario de fiación eses nós así,

851
01:10:41,690 --> 01:10:56,730
Nós só estamos indo a comentar a cousa toda,

852
01:10:56,730 --> 01:11:02,620
e en vez de fiación ata os nós de nós mesmos,

853
01:11:02,620 --> 01:11:09,400
podemos realmente ir adiante e eliminar todo isto.

854
01:11:09,400 --> 01:11:17,560
Nós imos facer todo o que unha chamada para introducir.

855
01:11:17,560 --> 01:11:49,020
Entón, imos facer - en vez de 5, 8 e 2, imos introducir 7, 3 e 9.

856
01:11:49,020 --> 01:11:58,440
E entón nós tamén quere inserir 6 tamén.

857
01:11:58,440 --> 01:12:05,190
Gardar. Saír. Facer árbore binaria.

858
01:12:05,190 --> 01:12:08,540
Todo compila.

859
01:12:08,540 --> 01:12:10,320
Podemos só executa-lo como está e ver o que acontece,

860
01:12:10,320 --> 01:12:12,770
pero tamén vai ser moi importante para asegurarse de que

861
01:12:12,770 --> 01:12:14,740
non temos ningún erros de memoria,

862
01:12:14,740 --> 01:12:16,840
unha vez que este é un dos nosos casos de punta que nós coñecemos.

863
01:12:16,840 --> 01:12:20,150
>> Imos estar seguro de que funciona ben baixo Valgrind,

864
01:12:20,150 --> 01:12:28,310
o que faremos simplemente executando Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Parece que, de feito, un erro dun contexto -

866
01:12:31,110 --> 01:12:33,790
temos esa fallo de segmento.

867
01:12:33,790 --> 01:12:36,690
¿Qué pasou?

868
01:12:36,690 --> 01:12:41,650
Valgrind realmente nos di onde está.

869
01:12:41,650 --> 01:12:43,050
Zoom para fóra un pouco.

870
01:12:43,050 --> 01:12:46,040
Parece que está a suceder na nosa función de inserción,

871
01:12:46,040 --> 01:12:53,420
onde temos unha lectura incorrecta de tamaño 4 a inserción, liña 60.

872
01:12:53,420 --> 01:13:03,590
Imos volver e ver o que está a suceder aquí.

873
01:13:03,590 --> 01:13:05,350
Diminuír o zoom moi rápido.

874
01:13:05,350 --> 01:13:14,230
Eu quero estar seguro de que non vai para o bordo da pantalla, para que poidamos ver todo.

875
01:13:14,230 --> 01:13:18,760
Puxe que un pouco. Todo ben.

876
01:13:18,760 --> 01:13:35,030
Rolar para abaixo, e que o problema está aquí.

877
01:13:35,030 --> 01:13:40,120
Qué acontece se nós descermos eo noso nodo actual xa é nulo,

878
01:13:40,120 --> 01:13:44,010
noso nodo pai é nulo, polo que se miramos cara o cumio, aquí -

879
01:13:44,010 --> 01:13:47,340
se isto non loop while realmente executa

880
01:13:47,340 --> 01:13:52,330
porque o seu valor actual é nulo - a nosa raíz é nula a actual é nulo -

881
01:13:52,330 --> 01:13:57,810
entón nunca o noso pai está configurado para actual ou para un valor válido,

882
01:13:57,810 --> 01:14:00,580
así, o pai tamén será nulo.

883
01:14:00,580 --> 01:14:03,700
Necesitamos recordar para comprobar que

884
01:14:03,700 --> 01:14:08,750
no momento en que chegar aquí, e comezar a acceder valor do pai.

885
01:14:08,750 --> 01:14:13,190
Entón, o que ocorre? Ben, o pai é nulo -

886
01:14:13,190 --> 01:14:17,990
if (pai == NULL) -, entón sabemos que

887
01:14:17,990 --> 01:14:19,530
non debe haber nada na árbore.

888
01:14:19,530 --> 01:14:22,030
Debemos estar intentando inserir-lo na raíz.

889
01:14:22,030 --> 01:14:32,570
Podemos facelo definindo só a raíz igual ao novo nodo.

890
01:14:32,570 --> 01:14:40,010
Entón, neste momento, nós realmente non quero pasar por esas outras cousas.

891
01:14:40,010 --> 01:14:44,780
En vez diso, aquí, podemos facer unha ou outra cousa se else,

892
01:14:44,780 --> 01:14:47,610
ou podemos combinar todo aquí en outra persoa,

893
01:14:47,610 --> 01:14:56,300
pero aquí imos usar máis e facelo desa maneira.

894
01:14:56,300 --> 01:14:59,030
Agora, imos probar para estar seguro de que o noso pai non é nulo

895
01:14:59,030 --> 01:15:02,160
antes, entón realmente intentando acceder os seus campos.

896
01:15:02,160 --> 01:15:05,330
Isto vai axudar a evitar a fallo de segmento.

897
01:15:05,330 --> 01:15:14,740
Entón, nós paramos, zoom out, compilar, executar.

898
01:15:14,740 --> 01:15:18,130
>> Sen erros, pero aínda temos unha morea de derrames de memoria

899
01:15:18,130 --> 01:15:20,650
porque non liberar calquera dos nosos nós.

900
01:15:20,650 --> 01:15:24,350
Pero se somos aquí e vai para a impresión,

901
01:15:24,350 --> 01:15:30,880
vemos que, así, parece que todos os nosos insercións foron retornando certo, o que é bo.

902
01:15:30,880 --> 01:15:33,050
As pastillas son todas verdadeiras,

903
01:15:33,050 --> 01:15:36,670
e despois as chamadas pertinentes contén tamén son certas.

904
01:15:36,670 --> 01:15:41,510
>> Bo traballo! Parece que temos escrito con éxito inserción.

905
01:15:41,510 --> 01:15:47,430
Isto é todo o que temos para esta semana Especificación conxunto de problemas.

906
01:15:47,430 --> 01:15:51,720
Un reto divertido pensar é como realmente ir

907
01:15:51,720 --> 01:15:55,340
e libre de todos os nós desta árbore.

908
01:15:55,340 --> 01:15:58,830
Podemos facer un número de xeitos diferentes,

909
01:15:58,830 --> 01:16:01,930
pero vou deixar isto para vostede experimentar,

910
01:16:01,930 --> 01:16:06,080
e como un reto divertido, probar e asegurarse de que pode que seguro

911
01:16:06,080 --> 01:16:09,490
que este informe Valgrind amosa erros e sen vazamentos.

912
01:16:09,490 --> 01:16:12,880
>> Boa sorte no partido desta semana problema Huffman,

913
01:16:12,880 --> 01:16:14,380
e imos ver semana que vén!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]