1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Artículo 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 es CS50.] [CS50.TV]

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

5
00:00:09,080 --> 00:00:11,330
Gracias a huracán de arena,

6
00:00:11,330 --> 00:00:13,440
en lugar de tener una sección normal de esta semana,

7
00:00:13,440 --> 00:00:17,650
estamos haciendo este recorrido, a través de la sección de preguntas.

8
00:00:17,650 --> 00:00:22,830
Voy a estar siguiendo junto con el boletín de problemas 6 Especificación,

9
00:00:22,830 --> 00:00:25,650
y pasando por todas las preguntas de la

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

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

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

13
00:00:32,960 --> 00:00:35,480
>> Muy bien. Vamos a empezar.

14
00:00:35,480 --> 00:00:40,780
En este momento estoy buscando en la página 3 de la Especificación de problemas.

15
00:00:40,780 --> 00:00:44,110
Vamos a empezar a hablar primero sobre árboles binarios

16
00:00:44,110 --> 00:00:47,850
ya que éstos tienen una gran relevancia para conjunto de problemas de esta semana -

17
00:00:47,850 --> 00:00:49,950
la codificación del árbol de Huffman.

18
00:00:49,950 --> 00:00:55,000
Una de las estructuras de datos muy primero hablamos sobre CS50 fue el arreglo.

19
00:00:55,000 --> 00:01:00,170
Recuerde que una matriz es una secuencia de elementos -

20
00:01:00,170 --> 00:01:04,019
todas del mismo tipo - almacena uno al lado del otro en la memoria.

21
00:01:04,019 --> 00:01:14,420
Si tengo una matriz de enteros que puedo dibujar con este estilo de cajas-numbers-números enteros -

22
00:01:14,420 --> 00:01:20,290
Digamos que tengo 5 en la primera casilla, tengo 7 en el segundo,

23
00:01:20,290 --> 00:01:27,760
entonces tienen 8, 10, y 20 en el cuadro final.

24
00:01:27,760 --> 00:01:33,000
Recuerde las cosas, los dos realmente buenas de esta matriz

25
00:01:33,000 --> 00:01:38,800
es que tenemos este acceso constante a tiempo a cualquier elemento particular

26
00:01:38,800 --> 00:01:40,500
 en la matriz si se sabe que su índice.

27
00:01:40,500 --> 00:01:44,670
Por ejemplo, si quiero agarrar el tercer elemento de la matriz -

28
00:01:44,670 --> 00:01:47,870
en el índice 2 usando nuestra base cero sistema de indexación -

29
00:01:47,870 --> 00:01:52,220
Yo, literalmente, sólo hay que hacer un cálculo matemático simple,

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

31
00:01:56,170 --> 00:01:57,840
saque el 8 que esté almacenado,

32
00:01:57,840 --> 00:01:59,260
y estoy listo para salir.

33
00:01:59,260 --> 00:02:03,350
>> Una de las cosas malas de este conjunto - que hablamos

34
00:02:03,350 --> 00:02:05,010
cuando hablamos de listas enlazadas -

35
00:02:05,010 --> 00:02:09,120
es que si desea insertar un elemento en el array,

36
00:02:09,120 --> 00:02:11,090
Voy a tener que hacer algún cambio a su alrededor.

37
00:02:11,090 --> 00:02:12,940
Por ejemplo, esta matriz aquí

38
00:02:12,940 --> 00:02:16,850
está en el orden establecido - en orden ascendente -

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

40
00:02:19,440 --> 00:02:23,100
pero si lo desea insertar el número 9 en esta matriz,

41
00:02:23,100 --> 00:02:27,460
Voy a tener que cambiar algunos de los elementos con el fin de hacer espacio.

42
00:02:27,460 --> 00:02:30,440
Podemos extraer esta aquí.

43
00:02:30,440 --> 00:02:35,650
Voy a tener que mover el 5, el 7 y luego la 8;

44
00:02:35,650 --> 00:02:38,720
crear un espacio donde puedo poner el 9,

45
00:02:38,720 --> 00:02:45,910
y luego el 10 y el 20 puede ir a la derecha de la 9.

46
00:02:45,910 --> 00:02:49,450
Este es un tipo de dolor porque en el peor de los casos -

47
00:02:49,450 --> 00:02:54,350
cuando estamos tener que insertar ya sea al principio o al final

48
00:02:54,350 --> 00:02:56,040
de la matriz, en función de cómo estamos cambiando -

49
00:02:56,040 --> 00:02:58,850
podríamos llegar a tener que cambiar todos los elementos

50
00:02:58,850 --> 00:03:00,750
que actualmente estamos almacenando en la matriz.

51
00:03:00,750 --> 00:03:03,810
>> Entonces, ¿cuál era la forma de evitar esto?

52
00:03:03,810 --> 00:03:09,260
La forma de evitar esto era ir a nuestro método de lista enlazada, donde -

53
00:03:09,260 --> 00:03:19,820
en lugar de almacenar los elementos 5, 7, 8, 10 y 20 todos uno al lado del otro en la memoria -

54
00:03:19,820 --> 00:03:25,630
lo que en su lugar se les estaba almacenar especie de donde queríamos para almacenarlos

55
00:03:25,630 --> 00:03:32,470
en estos nodos de la lista enlazada que estoy dibujando aquí, un poco ad hoc.

56
00:03:32,470 --> 00:03:42,060
Y entonces ellos conectados entre sí mediante estos indicadores siguientes.

57
00:03:42,060 --> 00:03:44,370
Puedo tener un puntero del 5 al 7 de

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

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

60
00:03:47,770 --> 00:03:51,220
y por último, un triple desde la 10 a la 20,

61
00:03:51,220 --> 00:03:54,880
y luego un puntero nulo en los años 20 lo que indica que no hay nada a la izquierda.

62
00:03:54,880 --> 00:03:59,690
La disyuntiva que tenemos aquí

63
00:03:59,690 --> 00:04:05,360
es que ahora si queremos insertar el número 9 en la lista ordenada,

64
00:04:05,360 --> 00:04:08,270
todo lo que tenemos que hacer es crear un nuevo nodo con 9,

65
00:04:08,270 --> 00:04:12,290
cablear hacia arriba para que apunte al lugar adecuado,

66
00:04:12,290 --> 00:04:20,630
y luego re-cableado del 8 al apuntar hacia abajo a la 9.

67
00:04:20,630 --> 00:04:25,660
Eso es bastante rápido, en el supuesto que sabemos exactamente donde queremos insertar el 9.

68
00:04:25,660 --> 00:04:32,610
Pero la compensación a cambio de esto es que hemos perdido el acceso constante de tiempo

69
00:04:32,610 --> 00:04:36,230
a cualquier elemento particular en nuestra estructura de datos.

70
00:04:36,230 --> 00:04:40,950
Por ejemplo, si quiero encontrar el cuarto elemento en esta lista enlazada,

71
00:04:40,950 --> 00:04:43,510
Voy a tener que empezar desde el principio de la lista

72
00:04:43,510 --> 00:04:48,930
y trabajar a mi manera a través de contar nodo por nodo hasta que encuentre el cuarto.

73
00:04:48,930 --> 00:04:55,870
>> Con el fin de obtener un mejor rendimiento de acceso de una lista enlazada -

74
00:04:55,870 --> 00:04:59,360
pero también retienen algunas de las ventajas que teníamos

75
00:04:59,360 --> 00:05:01,800
en términos de inserción a tiempo de una lista enlazada -

76
00:05:01,800 --> 00:05:05,750
un árbol binario se va a tener que utilizar la memoria un poco más.

77
00:05:05,750 --> 00:05:11,460
En particular, en lugar de sólo tener un puntero a un nodo de árbol binario -

78
00:05:11,460 --> 00:05:13,350
al igual que la lista enlazada de nodos hace -

79
00:05:13,350 --> 00:05:16,950
vamos a añadir un segundo puntero para el nodo del árbol binario.

80
00:05:16,950 --> 00:05:19,950
En lugar de tener un puntero al siguiente elemento,

81
00:05:19,950 --> 00:05:24,420
vamos a tener un puntero a un hijo izquierdo y un hijo derecho.

82
00:05:24,420 --> 00:05:26,560
>> Vamos a hacer un dibujo para ver lo que realmente parece.

83
00:05:26,560 --> 00:05:31,350
Una vez más, voy a utilizar estas cajas y flechas.

84
00:05:31,350 --> 00:05:37,150
Un nodo del árbol binario a empezar con sólo una caja simple.

85
00:05:37,150 --> 00:05:40,940
Va a tener un espacio para el valor,

86
00:05:40,940 --> 00:05:47,280
y entonces también va a tener un espacio para que el hijo izquierdo y el hijo derecho.

87
00:05:47,280 --> 00:05:49,280
Voy a etiquetarlos aquí.

88
00:05:49,280 --> 00:05:57,560
Vamos a tener el hijo izquierdo, y luego nos vamos a tener el hijo derecho.

89
00:05:57,560 --> 00:05:59,920
Hay muchas maneras diferentes de hacer esto.

90
00:05:59,920 --> 00:06:02,050
A veces por espacio y comodidad,

91
00:06:02,050 --> 00:06:06,460
De hecho, me voy a dibujar como que estoy haciendo aquí en la parte inferior

92
00:06:06,460 --> 00:06:10,910
donde yo voy a tener el valor en la parte superior,

93
00:06:10,910 --> 00:06:14,060
y entonces el niño a la derecha en la parte inferior derecha,

94
00:06:14,060 --> 00:06:16,060
y el hijo izquierdo en la parte inferior izquierda.

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

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

97
00:06:22,560 --> 00:06:25,560
entonces tenemos el puntero izquierdo-hijo, y entonces tenemos el puntero derecho del niño.

98
00:06:25,560 --> 00:06:30,110
>> En la especificación del conjunto de problemas,

99
00:06:30,110 --> 00:06:33,110
se habla de la elaboración de un nodo que tiene un valor de 7,

100
00:06:33,110 --> 00:06:39,750
y luego un puntero izquierdo niño que es nulo, y un puntero derecho del niño que es nulo.

101
00:06:39,750 --> 00:06:46,040
Podemos escribir NULL capital en el espacio para

102
00:06:46,040 --> 00:06:51,610
tanto el hijo izquierdo y el hijo derecho, o podemos sacar esta barra diagonal

103
00:06:51,610 --> 00:06:53,750
a través de cada una de las casillas para indicar que es nulo.

104
00:06:53,750 --> 00:06:57,560
Voy a hacer eso sólo porque es más simple.

105
00:06:57,560 --> 00:07:03,700
Lo que se ve aquí son dos formas de diagramación de un nodo de árbol binario muy sencillo

106
00:07:03,700 --> 00:07:07,960
donde tenemos el valor 7 y punteros nulos infantil.

107
00:07:07,960 --> 00:07:15,220
>> La segunda parte de nuestras conversaciones con las especificaciones acerca de cómo las listas enlazadas -

108
00:07:15,220 --> 00:07:18,270
recuerde, sólo tuvimos que esperar al primer elemento de una lista

109
00:07:18,270 --> 00:07:20,270
para recordar toda la lista -

110
00:07:20,270 --> 00:07:26,140
y del mismo modo, con un árbol binario, sólo tenemos que aguantar a un puntero al árbol

111
00:07:26,140 --> 00:07:31,120
con el fin de mantener el control sobre la estructura de datos completa.

112
00:07:31,120 --> 00:07:36,150
Este elemento especial del árbol se denomina nodo raíz del árbol.

113
00:07:36,150 --> 00:07:43,360
Por ejemplo, si este nodo de uno - este nodo que contiene el valor 7

114
00:07:43,360 --> 00:07:45,500
con punteros nulos izquierda y derecha para niños -

115
00:07:45,500 --> 00:07:47,360
eran el único valor en nuestro árbol,

116
00:07:47,360 --> 00:07:50,390
entonces este sería nuestro nodo raíz.

117
00:07:50,390 --> 00:07:52,240
Es el comienzo mismo de nuestro árbol.

118
00:07:52,240 --> 00:07:58,530
Podemos ver esto un poco más clara una vez que comience a añadir más nodos a nuestro árbol.

119
00:07:58,530 --> 00:08:01,510
Déjame sacar una nueva página.

120
00:08:01,510 --> 00:08:05,000
>> Ahora vamos a dibujar un árbol que tiene 7 en la raíz,

121
00:08:05,000 --> 00:08:10,920
y 3 dentro de la hijo izquierdo, y 9 en el interior de el hijo derecho.

122
00:08:10,920 --> 00:08:13,500
Una vez más, esto es bastante simple.

123
00:08:13,500 --> 00:08:26,510
Tenemos 7, dibuje un nodo para el 3, un nodo 9,

124
00:08:26,510 --> 00:08:32,150
y yo voy a poner el puntero izquierdo niño de 7 a apuntar al nodo que contiene 3,

125
00:08:32,150 --> 00:08:37,850
y el puntero derecho del hijo del nodo que contiene 7 al nodo que contiene 9.

126
00:08:37,850 --> 00:08:42,419
Ahora, desde el 3 y 9 no tienen hijos,

127
00:08:42,419 --> 00:08:48,500
vamos a hacer que todos los punteros a sus hijos a ser nulo.

128
00:08:48,500 --> 00:08:56,060
Aquí, la raíz de nuestro árbol corresponde al nodo que contiene el número 7.

129
00:08:56,060 --> 00:09:02,440
Se puede ver que si todo lo que tenemos es un puntero a ese nodo raíz,

130
00:09:02,440 --> 00:09:07,330
entonces podemos caminar a través de nuestro árbol y acceder a ambos nodos secundarios -

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

132
00:09:10,630 --> 00:09:14,820
No es necesario mantener los punteros a cada nodo en el árbol.

133
00:09:14,820 --> 00:09:22,080
Muy bien. Ahora vamos a agregar un nodo a este diagrama.

134
00:09:22,080 --> 00:09:25,370
Vamos a añadir un nodo que contiene 6,

135
00:09:25,370 --> 00:09:34,140
y vamos a añadir esto como el hijo derecho del nodo que contiene 3.

136
00:09:34,140 --> 00:09:41,850
Para hacer eso, voy a borrar ese puntero nulo en el 3-nodo

137
00:09:41,850 --> 00:09:47,750
y cablear para que apunte al nodo que contiene 6. Muy bien.

138
00:09:47,750 --> 00:09:53,800
>> En este punto, vamos a repasar un poco de la terminología.

139
00:09:53,800 --> 00:09:58,230
Para empezar, la razón por la que esto se llama un árbol binario en particular

140
00:09:58,230 --> 00:10:00,460
es que tiene dos punteros niño.

141
00:10:00,460 --> 00:10:06,020
Hay otros tipos de árboles que tienen más punteros del niño.

142
00:10:06,020 --> 00:10:10,930
En particular, se hizo un 'try' en Boletín de problemas 5.

143
00:10:10,930 --> 00:10:19,310
Se dará cuenta de que en ese intento, que tuvo 27 punteros diferentes para diferentes niños -

144
00:10:19,310 --> 00:10:22,410
uno para cada una de las 26 letras en el alfabeto Inglés,

145
00:10:22,410 --> 00:10:25,410
y luego el día 27 para el apóstrofe -

146
00:10:25,410 --> 00:10:28,900
es así, que es similar a un tipo de árbol.

147
00:10:28,900 --> 00:10:34,070
Pero aquí, ya que es binario, sólo tenemos dos punteros del niño.

148
00:10:34,070 --> 00:10:37,880
>> Además de este nodo raíz que hemos hablado,

149
00:10:37,880 --> 00:10:41,470
también hemos estado lanzando en torno a este término "niño".

150
00:10:41,470 --> 00:10:44,470
¿Qué significa para un nodo a ser un hijo de otro nodo?

151
00:10:44,470 --> 00:10:54,060
Es, literalmente, significa que un nodo hijo es un hijo de otro nodo

152
00:10:54,060 --> 00:10:58,760
si otro nodo que tiene una de sus punteros de niños fijan para apuntar a ese nodo.

153
00:10:58,760 --> 00:11:01,230
Para ponerlo en términos más concretos,

154
00:11:01,230 --> 00:11:11,170
si 3 es apuntado por uno de los punteros de niño de 7, entonces 3 es un niño de 7.

155
00:11:11,170 --> 00:11:14,510
Si tuviéramos que entender lo que los niños de 7 son -

156
00:11:14,510 --> 00:11:18,510
así, vemos que 7 tiene un puntero a 3 y un puntero a 9,

157
00:11:18,510 --> 00:11:22,190
lo 9 y 3 son hijos de 7.

158
00:11:22,190 --> 00:11:26,650
Nueve no tiene hijos, porque sus hijos son punteros nulos,

159
00:11:26,650 --> 00:11:30,940
y 3 sólo tiene un hijo de 6.

160
00:11:30,940 --> 00:11:37,430
Seis tampoco tiene hijos, porque sus dos punteros son nulos, lo que vamos a llamar ahora mismo.

161
00:11:37,430 --> 00:11:45,010
>> Además, también hablamos de los padres de un nodo en particular,

162
00:11:45,010 --> 00:11:51,100
y esto es, como era de esperar, el reverso de esta descripción niño.

163
00:11:51,100 --> 00:11:58,620
Cada nodo tiene un solo padre - en lugar de dos como se podría esperar de los seres humanos.

164
00:11:58,620 --> 00:12:03,390
Por ejemplo, la matriz de 3 es 7.

165
00:12:03,390 --> 00:12:10,800
El padre de 9 es también 7, y el padre de 6 es 3. No hay mucho a ella.

166
00:12:10,800 --> 00:12:15,720
También tenemos términos para hablar de los abuelos y los nietos,

167
00:12:15,720 --> 00:12:18,210
y en general se habla de los antepasados

168
00:12:18,210 --> 00:12:20,960
y descendientes de un nodo en particular.

169
00:12:20,960 --> 00:12:25,710
El ancestro de un nodo - o antepasados, más bien, de un nodo -

170
00:12:25,710 --> 00:12:32,730
son todos los nodos que se encuentran en el camino desde la raíz a ese nodo.

171
00:12:32,730 --> 00:12:36,640
Por ejemplo, si estoy buscando en el nodo 6,

172
00:12:36,640 --> 00:12:46,430
entonces los antepasados ​​va a ser a la vez 3 y 7.

173
00:12:46,430 --> 00:12:55,310
Los antepasados ​​de 9, por ejemplo, son - si estoy buscando en el nodo 9 -

174
00:12:55,310 --> 00:12:59,990
entonces el antepasado de 9 es sólo 7.

175
00:12:59,990 --> 00:13:01,940
Y descendientes son exactamente lo contrario.

176
00:13:01,940 --> 00:13:05,430
Si desea ver todos los descendientes de 7,

177
00:13:05,430 --> 00:13:11,020
entonces tengo que mirar a todos los nodos que dependen de ella.

178
00:13:11,020 --> 00:13:16,950
Por lo tanto, tengo 3, 9, y 6 todos como hijos de 7.

179
00:13:16,950 --> 00:13:24,170
>> El plazo final que vamos a hablar es de esta noción de ser un hermano.

180
00:13:24,170 --> 00:13:27,980
Hermanos - algo siguiendo a lo largo de estos términos familias -

181
00:13:27,980 --> 00:13:33,150
son nodos que están en el mismo nivel en el árbol.

182
00:13:33,150 --> 00:13:42,230
Así, 3 y 9 son hermanos porque están en el mismo nivel en el árbol.

183
00:13:42,230 --> 00:13:46,190
Ambos tienen el mismo padre, 7.

184
00:13:46,190 --> 00:13:51,400
El 6 no tiene hermanos porque 9 no tengo hijos.

185
00:13:51,400 --> 00:13:55,540
Y 7 no tiene hermanos, porque es la raíz de nuestro árbol,

186
00:13:55,540 --> 00:13:59,010
y sólo hay siempre una raíz.

187
00:13:59,010 --> 00:14:02,260
Para tener 7 hermanos no tendría que ser un nodo por encima de 7.

188
00:14:02,260 --> 00:14:07,480
No tendría que ser una matriz de 7, en cuyo caso 7 ya no sería la raíz del árbol.

189
00:14:07,480 --> 00:14:10,480
Luego de que los padres nuevos de 7 también tendría que tener un hijo,

190
00:14:10,480 --> 00:14:16,480
y que niño sería entonces el hermano de 7.

191
00:14:16,480 --> 00:14:21,040
>> Muy bien. Cambiando de tema.

192
00:14:21,040 --> 00:14:24,930
Cuando comenzamos nuestra discusión de los árboles binarios,

193
00:14:24,930 --> 00:14:28,790
hablamos de lo que íbamos a utilizar para

194
00:14:28,790 --> 00:14:32,800
obtener una ventaja sobre ambas matrices y listas enlazadas.

195
00:14:32,800 --> 00:14:37,220
Y la forma en que vamos a hacerlo es con esta propiedad pedido.

196
00:14:37,220 --> 00:14:41,080
Se dice que un árbol binario es ordenado, de acuerdo con la especificación,

197
00:14:41,080 --> 00:14:45,740
si para cada nodo en nuestro árbol, todos sus descendientes de la izquierda -

198
00:14:45,740 --> 00:14:48,670
el hijo de la izquierda y todos los descendientes del hijo izquierdo -

199
00:14:48,670 --> 00:14:54,510
tienen valores menores, y todos los nodos de la derecha -

200
00:14:54,510 --> 00:14:57,770
el hijo derecho y todos los descendientes de los hijos de derecho -

201
00:14:57,770 --> 00:15:02,800
tienen nodos mayores que el valor del nodo actual que estamos viendo.

202
00:15:02,800 --> 00:15:07,850
Sólo para simplificar, vamos a suponer que no hay nodos duplicados en nuestro árbol.

203
00:15:07,850 --> 00:15:11,180
Por ejemplo, en este árbol no vamos a tratar el caso

204
00:15:11,180 --> 00:15:13,680
donde tenemos el valor 7 en la raíz

205
00:15:13,680 --> 00:15:16,720
 y luego también tenemos el valor 7 en otro lugar en el árbol.

206
00:15:16,720 --> 00:15:24,390
En este caso, se dará cuenta de que este árbol es de hecho ordenado.

207
00:15:24,390 --> 00:15:26,510
Tenemos el valor 7 en la raíz.

208
00:15:26,510 --> 00:15:29,720
Todo a la izquierda de 7 -

209
00:15:29,720 --> 00:15:35,310
si puedo deshacer todas estas pequeñas marcas aquí -

210
00:15:35,310 --> 00:15:40,450
todo a la izquierda de 7 - el 3 y el 6 -

211
00:15:40,450 --> 00:15:49,410
esos valores se encuentran a menos de 7, y todo a la derecha - - que es precisamente este 9

212
00:15:49,410 --> 00:15:53,450
es mayor que 7.

213
00:15:53,450 --> 00:15:58,650
>> Este no es el único árbol ordenado que contiene estos valores,

214
00:15:58,650 --> 00:16:03,120
pero vamos a hacer un poco más de ellos.

215
00:16:03,120 --> 00:16:05,030
En realidad, hay un montón de maneras en que podemos hacer esto.

216
00:16:05,030 --> 00:16:09,380
Voy a usar un atajo sólo para mantener las cosas simples donde -

217
00:16:09,380 --> 00:16:11,520
en vez de extraer la totalidad cajas y flechas -

218
00:16:11,520 --> 00:16:14,220
Yo sólo voy a dibujar los números y agregar flechas conectan.

219
00:16:14,220 --> 00:16:22,920
Para empezar, sólo tendremos que escribir nuestro árbol original de nuevo donde teníamos 7, y luego un 3,

220
00:16:22,920 --> 00:16:25,590
y luego 3 señaló de nuevo a la derecha a la 6,

221
00:16:25,590 --> 00:16:30,890
y 7 tuvieron un hijo derecho que tenía 9 años.

222
00:16:30,890 --> 00:16:33,860
Muy bien. ¿De qué otra manera que no podamos escribir este árbol?

223
00:16:33,860 --> 00:16:38,800
En vez de tener 3 será el hijo izquierdo de 7,

224
00:16:38,800 --> 00:16:41,360
También podría tener el 6 ser el hijo izquierdo de 7,

225
00:16:41,360 --> 00:16:44,470
y luego 3 será el hijo izquierdo de la 6.

226
00:16:44,470 --> 00:16:48,520
Eso se parecería a este árbol aquí donde tengo 7,

227
00:16:48,520 --> 00:16:57,860
luego 6, luego 3, y un 9 a la derecha.

228
00:16:57,860 --> 00:17:01,490
Tampoco tiene que tener 7 como nuestro nodo raíz.

229
00:17:01,490 --> 00:17:03,860
También podría tener 6 como nuestro nodo raíz.

230
00:17:03,860 --> 00:17:06,470
¿Qué se ve?

231
00:17:06,470 --> 00:17:09,230
Si vamos a mantener este inmueble ordenado,

232
00:17:09,230 --> 00:17:12,970
todo a la izquierda de la 6 tiene que ser menor que ella.

233
00:17:12,970 --> 00:17:16,540
Sólo hay una posibilidad, y eso es 3.

234
00:17:16,540 --> 00:17:19,869
Pero entonces, como el hijo derecho de 6, tenemos dos posibilidades.

235
00:17:19,869 --> 00:17:25,380
En primer lugar, podríamos tener el 7 y luego el 9,

236
00:17:25,380 --> 00:17:28,850
o podríamos llamar - que estoy a punto de hacer aquí -

237
00:17:28,850 --> 00:17:34,790
donde tenemos el 9 como el hijo derecho de la 6,

238
00:17:34,790 --> 00:17:39,050
y luego el 7 como el hijo izquierdo de la 9.

239
00:17:39,050 --> 00:17:44,240
>> Ahora, 7 y 6 no son los únicos valores posibles de la raíz.

240
00:17:44,240 --> 00:17:50,200
También podríamos tener 3 en la raíz.

241
00:17:50,200 --> 00:17:52,240
¿Qué sucede si 3 es la raíz?

242
00:17:52,240 --> 00:17:54,390
Aquí, las cosas se ponen un poco más interesante.

243
00:17:54,390 --> 00:17:58,440
Tres no tiene valores que son menores de lo que,

244
00:17:58,440 --> 00:18:02,070
de modo que todo el lado izquierdo del árbol es sólo va a ser nulo.

245
00:18:02,070 --> 00:18:03,230
No va a ser nada allí.

246
00:18:03,230 --> 00:18:07,220
A la derecha, podríamos enumerar las cosas en orden ascendente.

247
00:18:07,220 --> 00:18:15,530
Podríamos tener 3, luego 6, luego 7, luego 9.

248
00:18:15,530 --> 00:18:26,710
O bien, podemos hacer 3, luego 6, luego 9, luego 7.

249
00:18:26,710 --> 00:18:35,020
O bien, podemos hacer 3, luego 7, luego 6, luego 9.

250
00:18:35,020 --> 00:18:40,950
O, 3, 7 - en realidad no, no podemos hacer un 7 más.

251
00:18:40,950 --> 00:18:43,330
Esa es nuestra única cosa allí.

252
00:18:43,330 --> 00:18:54,710
Podemos hacer 9, y luego desde el 9 podemos hacer 6 y 7.

253
00:18:54,710 --> 00:19:06,980
O bien, podemos hacer 3, luego 9, luego 7 y luego 6.

254
00:19:06,980 --> 00:19:12,490
>> Una cosa para llamar su atención aquí es

255
00:19:12,490 --> 00:19:14,510
que estos árboles son un poco de aspecto extraño.

256
00:19:14,510 --> 00:19:17,840
En particular, si nos fijamos en los cuatro árboles en el lado derecho -

257
00:19:17,840 --> 00:19:20,930
Voy a rodearlos, aquí -

258
00:19:20,930 --> 00:19:28,410
estos árboles se ven casi exactamente igual que una lista enlazada.

259
00:19:28,410 --> 00:19:32,670
Cada nodo tiene un solo hijo,

260
00:19:32,670 --> 00:19:38,950
por lo que no tiene ninguno de esta estructura en forma de árbol que vemos, por ejemplo,

261
00:19:38,950 --> 00:19:44,720
 en este árbol un solitario aquí en la parte inferior izquierda.

262
00:19:44,720 --> 00:19:52,490
Estos árboles se llama en realidad degenerada árboles binarios,

263
00:19:52,490 --> 00:19:54,170
y vamos a hablar de estos más en el futuro -

264
00:19:54,170 --> 00:19:56,730
especialmente si usted va a tomar otros cursos de ciencias de la computación.

265
00:19:56,730 --> 00:19:59,670
Estos árboles son degenerados.

266
00:19:59,670 --> 00:20:03,780
No son muy útiles porque, en efecto, esta estructura se presta

267
00:20:03,780 --> 00:20:08,060
 para buscar tiempos similares a la de una lista enlazada.

268
00:20:08,060 --> 00:20:13,050
No conseguimos aprovechar la memoria adicional - este puntero extra -

269
00:20:13,050 --> 00:20:18,840
porque de nuestra estructura de ser malo de esta manera.

270
00:20:18,840 --> 00:20:24,700
En vez de seguir adelante y sacar los árboles binarios que tienen 9 en la raíz,

271
00:20:24,700 --> 00:20:27,220
que es el caso final que tendría,

272
00:20:27,220 --> 00:20:32,380
estamos en cambio, en este punto, vamos a hablar un poco acerca de este otro término

273
00:20:32,380 --> 00:20:36,150
que utilizamos cuando hablamos de árboles, que se llama la altura.

274
00:20:36,150 --> 00:20:45,460
>> La altura de un árbol es la distancia desde la raíz hasta el nodo más distante,

275
00:20:45,460 --> 00:20:48,370
o más bien el número de saltos que se tendría que hacer a fin de

276
00:20:48,370 --> 00:20:53,750
comenzar desde la raíz y luego terminan en el nodo más lejano en el árbol.

277
00:20:53,750 --> 00:20:57,330
Si nos fijamos en algunos de estos árboles que hemos dibujado aquí,

278
00:20:57,330 --> 00:21:07,870
podemos ver que si tomamos este árbol en la esquina superior izquierda y empezamos a 3,

279
00:21:07,870 --> 00:21:14,510
entonces tenemos que hacer un salto para llegar a la 6, un segundo salto para llegar a los 7,

280
00:21:14,510 --> 00:21:20,560
y una tercera hop para llegar a la 9.

281
00:21:20,560 --> 00:21:26,120
Así, la altura de este árbol es 3.

282
00:21:26,120 --> 00:21:30,640
Podemos hacer el mismo ejercicio para los otros árboles señalados con este color verde,

283
00:21:30,640 --> 00:21:40,100
y se ve que la altura de todos estos árboles es también de hecho 3.

284
00:21:40,100 --> 00:21:45,230
Eso es parte de lo que los hace degenerar -

285
00:21:45,230 --> 00:21:53,750
que su altura es sólo uno menos que el número de nodos en el árbol completo.

286
00:21:53,750 --> 00:21:58,400
Si nos fijamos en este otro árbol que está rodeado de rojo, por otro lado,

287
00:21:58,400 --> 00:22:03,920
vemos que los nodos de hoja más distantes son el 6 y el 9 -

288
00:22:03,920 --> 00:22:06,940
la deja ser aquellos nodos que no tienen hijos.

289
00:22:06,940 --> 00:22:11,760
Así, con el fin de obtener desde el nodo raíz a ya sea el 6 o el 9,

290
00:22:11,760 --> 00:22:17,840
tenemos que hacer un salto para llegar a la 7 y luego un segundo salto para llegar a la 9,

291
00:22:17,840 --> 00:22:21,240
y del mismo modo, sólo un salto de la segunda 7 para llegar a la 6.

292
00:22:21,240 --> 00:22:29,080
Así, la altura de este árbol de aquí es sólo 2.

293
00:22:29,080 --> 00:22:35,330
Usted puede volver atrás y hacer que para todos los demás árboles que previamente discutido

294
00:22:35,330 --> 00:22:37,380
comenzando con el 7 y el 6,

295
00:22:37,480 --> 00:22:42,500
y te darás cuenta de que la altura de todos esos árboles es también 2.

296
00:22:42,500 --> 00:22:46,320
>> La razón por la que hemos estado hablando ordenó árboles binarios

297
00:22:46,320 --> 00:22:50,250
y por qué estamos bien es porque usted puede buscar a través de ellos en

298
00:22:50,250 --> 00:22:53,810
de una manera muy similar a la búsqueda a través de una matriz ordenada.

299
00:22:53,810 --> 00:22:58,720
Aquí es donde hablamos de conseguir que el tiempo de búsqueda mejorada

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

301
00:23:02,730 --> 00:23:05,010
Con una lista enlazada - si usted desea encontrar un elemento en particular -

302
00:23:05,010 --> 00:23:07,470
eres lo mejor va a hacer algún tipo de búsqueda lineal

303
00:23:07,470 --> 00:23:10,920
donde se inicia al comienzo de la lista y saltar de uno en uno -

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

305
00:23:12,620 --> 00:23:16,060
a través de toda la lista hasta que encuentre lo que usted está buscando.

306
00:23:16,060 --> 00:23:19,440
Mientras que si usted tiene un árbol binario que se almacena en este formato agradable,

307
00:23:19,440 --> 00:23:23,300
usted puede obtener más de una búsqueda binaria pasando

308
00:23:23,300 --> 00:23:25,160
donde se divide y vencerás

309
00:23:25,160 --> 00:23:29,490
y buscar en la media correspondiente del árbol en cada paso.

310
00:23:29,490 --> 00:23:32,840
Vamos a ver cómo funciona.

311
00:23:32,840 --> 00:23:38,850
>> Si tenemos - de nuevo, volviendo a nuestro árbol original -

312
00:23:38,850 --> 00:23:46,710
comenzamos a 7, que tienen 3 a la izquierda, 9 a la derecha,

313
00:23:46,710 --> 00:23:51,740
y debajo de la 3 tenemos la 6.

314
00:23:51,740 --> 00:24:01,880
Si queremos buscar el número 6 de este árbol, nos gustaría empezar en la raíz.

315
00:24:01,880 --> 00:24:08,910
Queremos comparar el valor que buscamos, por ejemplo 6,

316
00:24:08,910 --> 00:24:12,320
con el valor almacenado en el nodo que estamos mirando, 7,

317
00:24:12,320 --> 00:24:21,200
encontrar que 6 es de hecho menor que 7, por lo que nos mueve a la izquierda.

318
00:24:21,200 --> 00:24:25,530
Si el valor de 6 había sido mayor que 7, habríamos se mueven a la derecha.

319
00:24:25,530 --> 00:24:29,770
Ya que sabemos que - debido a la estructura de nuestro árbol binario ordenado -

320
00:24:29,770 --> 00:24:33,910
todos los valores de menos de 7 van a ser almacenados a la izquierda de 7,

321
00:24:33,910 --> 00:24:40,520
no hay necesidad de molestarse siquiera mirar por el lado derecho del árbol.

322
00:24:40,520 --> 00:24:43,780
Una vez que nos movemos hacia la izquierda y ahora estamos en el nodo que contiene 3,

323
00:24:43,780 --> 00:24:48,110
podemos hacer esa comparación misma de nuevo donde se compara el 3 y el 6.

324
00:24:48,110 --> 00:24:52,430
Y encontramos que mientras que el 6 - el valor que estamos buscando - es mayor que 3,

325
00:24:52,430 --> 00:24:58,580
que puede ir hacia el lado derecho del nodo que contiene 3.

326
00:24:58,580 --> 00:25:02,670
No hay lado izquierdo aquí, así que podría haber ignorado eso.

327
00:25:02,670 --> 00:25:06,510
Sin embargo, sólo se sabe que debido a que estamos viendo en el propio árbol,

328
00:25:06,510 --> 00:25:08,660
y podemos ver que el árbol no tiene hijos.

329
00:25:08,660 --> 00:25:13,640
>> También es muy fácil buscar 6 de este árbol si lo estamos haciendo a nosotros mismos como seres humanos,

330
00:25:13,640 --> 00:25:16,890
pero vamos a seguir este proceso mecánicamente como un ordenador haría

331
00:25:16,890 --> 00:25:18,620
para comprender realmente el algoritmo.

332
00:25:18,620 --> 00:25:26,200
En este punto, ahora estamos viendo un nodo que contiene 6,

333
00:25:26,200 --> 00:25:29,180
y estamos buscando el valor 6,

334
00:25:29,180 --> 00:25:31,740
así que, de hecho, hemos encontrado el nodo apropiado.

335
00:25:31,740 --> 00:25:35,070
Encontramos el valor 6 en nuestro árbol, y podemos detener nuestra búsqueda.

336
00:25:35,070 --> 00:25:37,330
En este punto, dependiendo de lo que está pasando,

337
00:25:37,330 --> 00:25:41,870
podemos decir, sí, hemos encontrado el valor 6, existe en nuestro árbol.

338
00:25:41,870 --> 00:25:47,640
O bien, si estamos planeando para insertar un nodo o hacer algo, podemos hacer eso en este momento.

339
00:25:47,640 --> 00:25:53,010
>> Vamos a hacer un par de búsquedas sólo para ver cómo funciona esto.

340
00:25:53,010 --> 00:25:59,390
Echemos un vistazo a lo que sucede si fuéramos a tratar de buscar el valor 10.

341
00:25:59,390 --> 00:26:02,970
Si tuviéramos que buscar el valor 10, que comenzaría en la raíz.

342
00:26:02,970 --> 00:26:07,070
Nos gustaría ver que 10 es mayor que 7, por lo que nos mueve a la derecha.

343
00:26:07,070 --> 00:26:13,640
Llegábamos a las 9 y comparar 9 a las 10 y ver que el 9 es de hecho inferior a 10.

344
00:26:13,640 --> 00:26:16,210
Así que de nuevo, nos gustaría tratar de mover a la derecha.

345
00:26:16,210 --> 00:26:20,350
Pero en este punto, se daría cuenta de que estamos en un nodo nulo.

346
00:26:20,350 --> 00:26:23,080
No hay nada allí. No hay nada que el 10 debe ser.

347
00:26:23,080 --> 00:26:29,360
Aquí es donde podemos informar fracaso - que hay de hecho no 10 en el árbol.

348
00:26:29,360 --> 00:26:35,420
Y, por último, vamos a pasar por el caso en el que estamos tratando de buscar una en el árbol.

349
00:26:35,420 --> 00:26:38,790
Esto es similar a lo que ocurre si miramos hacia arriba 10, excepto que en lugar de ir a la derecha,

350
00:26:38,790 --> 00:26:41,260
vamos a ir a la izquierda.

351
00:26:41,260 --> 00:26:46,170
Empezamos en el 7 y ver que 1 es menor que 7, por lo que se mueven a la izquierda.

352
00:26:46,170 --> 00:26:51,750
Llegamos a la 3 y ver que 1 es menor que 3, por lo que de nuevo se trata de mover a la izquierda.

353
00:26:51,750 --> 00:26:59,080
En este momento tenemos un nodo nulo, así que de nuevo podemos informar fracaso.

354
00:26:59,080 --> 00:27:10,260
>> Si usted quiere aprender más sobre los árboles binarios,

355
00:27:10,260 --> 00:27:14,420
hay un montón de divertidos pequeños problemas que se pueden hacer con ellos.

356
00:27:14,420 --> 00:27:19,450
Sugiero practicar el dibujo de estos diagramas de una por uno

357
00:27:19,450 --> 00:27:21,910
y siguiendo a través de todos los diferentes pasos,

358
00:27:21,910 --> 00:27:25,060
porque esto vendrá en super manejable

359
00:27:25,060 --> 00:27:27,480
no sólo cuando estás haciendo la codificación Huffman conjunto de problemas

360
00:27:27,480 --> 00:27:29,390
sino también en los futuros cursos -

361
00:27:29,390 --> 00:27:32,220
aprendiendo a dibujar estas estructuras de datos y reflexionar sobre los problemas

362
00:27:32,220 --> 00:27:38,000
con lápiz y papel o, en este caso, el iPhone y el lápiz.

363
00:27:38,000 --> 00:27:41,000
>> En este punto, sin embargo, vamos a pasar a hacer algunas prácticas de codificación

364
00:27:41,000 --> 00:27:44,870
y realmente jugar con estos árboles binarios y ver.

365
00:27:44,870 --> 00:27:52,150
Voy a volver a mi equipo.

366
00:27:52,150 --> 00:27:58,480
Para esta parte de la sección, en lugar de utilizar CS50 CS50 Run o Spaces,

367
00:27:58,480 --> 00:28:01,500
Voy a utilizar el aparato.

368
00:28:01,500 --> 00:28:04,950
>> Siguiendo con la especificación conjunto de problemas,

369
00:28:04,950 --> 00:28:07,740
Veo que tengo que abrir el aparato,

370
00:28:07,740 --> 00:28:11,020
ir a mi carpeta de Dropbox, cree una carpeta llamada Sección 7,

371
00:28:11,020 --> 00:28:15,730
a continuación, cree un archivo llamado binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Aquí vamos. Tengo el aparato ya está abierto.

373
00:28:22,050 --> 00:28:25,910
Voy a levantar una terminal.

374
00:28:25,910 --> 00:28:38,250
Voy a ir a la carpeta de Dropbox, cree un directorio llamado Sección 7,

375
00:28:38,250 --> 00:28:42,230
y ver que es totalmente vacío.

376
00:28:42,230 --> 00:28:48,860
Ahora voy a abrir binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Muy bien. Aquí vamos - archivo vacío.

378
00:28:51,750 --> 00:28:54,330
>> Volvamos a la especificación.

379
00:28:54,330 --> 00:28:59,850
La especificación pide que cree una definición de tipo nuevo

380
00:28:59,850 --> 00:29:03,080
para un nodo de árbol binario que contiene valores int -

381
00:29:03,080 --> 00:29:07,110
al igual que los valores que nos sacó de nuestra diagramación antes.

382
00:29:07,110 --> 00:29:11,740
Vamos a utilizar este texto modelo typedef que hemos hecho aquí

383
00:29:11,740 --> 00:29:14,420
que se debe reconocer de Serie de problemas 5 -

384
00:29:14,420 --> 00:29:19,190
si lo hizo de la manera tabla hash de conquistar el programa corrector ortográfico.

385
00:29:19,190 --> 00:29:22,540
También debe reconocer a partir de la sección de la semana pasada

386
00:29:22,540 --> 00:29:23,890
donde hablamos acerca de las listas enlazadas.

387
00:29:23,890 --> 00:29:27,870
Tenemos esta typedef de un nodo de estructura,

388
00:29:27,870 --> 00:29:34,430
y le hemos dado a este nodo struct este nombre de nodo de estructura de antemano

389
00:29:34,430 --> 00:29:39,350
para que luego pueda referirse a ella ya que querrá tener punteros struct nodo

390
00:29:39,350 --> 00:29:45,740
como parte de nuestra estructura, pero luego nos hemos rodeado este -

391
00:29:45,740 --> 00:29:47,700
o más bien, encerrado esto - en un typedef

392
00:29:47,700 --> 00:29:54,600
de modo que, más adelante en el código, se puede hacer referencia a esta estructura como un nodo en lugar de un nodo de estructura.

393
00:29:54,600 --> 00:30:03,120
>> Esto va a ser muy similar a la definición de la lista simplemente enlazada que vimos la semana pasada.

394
00:30:03,120 --> 00:30:20,070
Para ello, vamos a empezar por escribir el texto modelo.

395
00:30:20,070 --> 00:30:23,840
Sabemos que tenemos que tener un valor entero,

396
00:30:23,840 --> 00:30:32,170
así que vamos a poner en valor int, y entonces, en lugar de tener sólo un puntero al siguiente elemento -

397
00:30:32,170 --> 00:30:33,970
como lo hicimos con simplemente enlazada listas -

398
00:30:33,970 --> 00:30:38,110
vamos a tener punteros hijo izquierdo y derecho.

399
00:30:38,110 --> 00:30:42,880
Eso es bastante simple también - niño struct nodo * left;

400
00:30:42,880 --> 00:30:51,190
struct nodo y niño * derecha;. Cool.

401
00:30:51,190 --> 00:30:54,740
Eso parece un buen comienzo.

402
00:30:54,740 --> 00:30:58,530
Volvamos a la especificación.

403
00:30:58,530 --> 00:31:05,030
>> Ahora tenemos que declarar una variable de nodo * global para la raíz de un árbol.

404
00:31:05,030 --> 00:31:10,590
Vamos a hacer de este mundial al igual que hicimos en nuestro primer puntero lista enlazada también global.

405
00:31:10,590 --> 00:31:12,690
Esto era para que en las funciones que escribimos

406
00:31:12,690 --> 00:31:16,180
nosotros no tenemos que seguir pasando alrededor de esta raíz -

407
00:31:16,180 --> 00:31:19,620
aunque ya veremos que si quiero escribir estas funciones de forma recursiva,

408
00:31:19,620 --> 00:31:22,830
puede ser que sea mejor ni siquiera lo pasan a su alrededor como un mundial en el primer lugar

409
00:31:22,830 --> 00:31:28,090
y en lugar de iniciar a nivel local en su función principal.

410
00:31:28,090 --> 00:31:31,960
Pero, lo haremos a nivel mundial para comenzar.

411
00:31:31,960 --> 00:31:39,920
Una vez más, vamos a dar un par de espacios, y yo voy a declarar una raíz * nodo.

412
00:31:39,920 --> 00:31:46,770
Sólo para asegurarse de que no me deja esta sin inicializar, me voy a fijar igual a null.

413
00:31:46,770 --> 00:31:52,210
Ahora, en la función principal - lo que vamos a escribir muy rápido 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
y yo voy a empezar a declarar mi matriz argv como const sólo para que yo sepa

416
00:32:10,640 --> 00:32:14,550
que esos argumentos son los argumentos que probablemente no quieren modificar.

417
00:32:14,550 --> 00:32:18,390
Si desea modificarlos Probablemente debería estar haciendo copias de ellos.

418
00:32:18,390 --> 00:32:21,740
Usted verá esto mucho en el código.

419
00:32:21,740 --> 00:32:25,440
Está bien de cualquier manera. Está bien dejarlo como - omitir la const si lo desea.

420
00:32:25,440 --> 00:32:28,630
Me suelen ponerlo en sólo para que me recuerdo

421
00:32:28,630 --> 00:32:33,650
 que probablemente no desea modificar esos argumentos.

422
00:32:33,650 --> 00:32:39,240
>> Como siempre, voy a incluir esta línea return 0 al final del principal.

423
00:32:39,240 --> 00:32:45,730
Aquí, voy a iniciar mi nodo raíz.

424
00:32:45,730 --> 00:32:48,900
Tal como está ahora mismo, tengo un puntero que se establece en null,

425
00:32:48,900 --> 00:32:52,970
lo que apunta a la nada.

426
00:32:52,970 --> 00:32:57,480
Con el fin de iniciar realmente la construcción del nodo,

427
00:32:57,480 --> 00:32:59,250
La primera vez que asignar memoria para él.

428
00:32:59,250 --> 00:33:05,910
Voy a hacer que al hacer memoria en el heap usando malloc.

429
00:33:05,910 --> 00:33:10,660
Voy a establecer root igual al resultado de malloc,

430
00:33:10,660 --> 00:33:19,550
y voy a utilizar el operador sizeof para calcular el tamaño de un nodo.

431
00:33:19,550 --> 00:33:24,990
La razón por la que uso nodo sizeof a diferencia de, digamos,

432
00:33:24,990 --> 00:33:37,020
hacer algo como esto - malloc (4 + 4 + 4) o malloc 12 -

433
00:33:37,020 --> 00:33:40,820
es porque quiero que mi código sea lo más compatible posible.

434
00:33:40,820 --> 00:33:44,540
Quiero ser capaz de tomar este archivo. C, compilarlo en el aparato,

435
00:33:44,540 --> 00:33:48,820
y luego compilarlo en mi 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
o en una arquitectura completamente diferente -

437
00:33:52,040 --> 00:33:54,640
y quiero que todo esto funcione de la misma.

438
00:33:54,640 --> 00:33:59,510
>> Si estoy haciendo suposiciones sobre el tamaño de las variables -

439
00:33:59,510 --> 00:34:02,070
el tamaño de un int o el tamaño de un puntero -

440
00:34:02,070 --> 00:34:06,070
entonces yo también estoy haciendo suposiciones acerca de los tipos de arquitecturas

441
00:34:06,070 --> 00:34:10,440
en el que mi código se puede compilar con éxito cuando se ejecuta.

442
00:34:10,440 --> 00:34:15,030
Siempre utilice sizeof en lugar de manualmente sumando los campos struct.

443
00:34:15,030 --> 00:34:20,500
La otra razón es que también puede haber acolchado que el compilador pone en la estructura.

444
00:34:20,500 --> 00:34:26,570
Aunque sólo sea sumando los campos individuales no es algo que normalmente se quiere hacer,

445
00:34:26,570 --> 00:34:30,340
así, eliminar esa línea.

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

447
00:34:33,090 --> 00:34:36,489
Voy a tener que enchufar los valores para cada uno de sus campos.

448
00:34:36,489 --> 00:34:41,400
Por ejemplo, para el valor sé que quiero para inicializar a 7,

449
00:34:41,400 --> 00:34:46,920
y por ahora me voy a poner al niño izquierda a ser nulo

450
00:34:46,920 --> 00:34:55,820
y el hijo derecho a ser también nulo. Great!

451
00:34:55,820 --> 00:35:02,670
Lo hemos hecho parte de la especificación.

452
00:35:02,670 --> 00:35:07,390
>> La especificación abajo en la parte inferior de la página 3 me pide que cree más tres nodos -

453
00:35:07,390 --> 00:35:10,600
una que contiene 3, una que contiene 6, y uno con 9 -

454
00:35:10,600 --> 00:35:14,210
y luego cablear para que se vea exactamente igual que nuestro diagrama de árbol

455
00:35:14,210 --> 00:35:17,120
que hablábamos anteriormente.

456
00:35:17,120 --> 00:35:20,450
Vamos a hacer esto muy rápidamente aquí.

457
00:35:20,450 --> 00:35:26,270
Usted verá realmente rápido que voy a empezar a escribir un montón de código duplicado.

458
00:35:26,270 --> 00:35:32,100
Voy a crear un nodo * y voy a llamar tres.

459
00:35:32,100 --> 00:35:36,000
Voy a ponerlo igual a malloc (sizeof (nodo)).

460
00:35:36,000 --> 00:35:41,070
Me voy a poner tres-> valor = 3.

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

462
00:35:54,780 --> 00:36:01,150
Eso se ve muy similar a la inicialización de la raíz, y eso es exactamente lo que

463
00:36:01,150 --> 00:36:05,760
Voy a tener que hacer si comienzo la inicialización de 6 y 9 también.

464
00:36:05,760 --> 00:36:20,720
Lo haré muy rápido aquí - en realidad, yo voy a hacer un poco de copia y pega,

465
00:36:20,720 --> 00:36:46,140
y asegurarse de que yo - bien.

466
00:36:46,470 --> 00:37:09,900
 Ahora, tengo que copiar y puedo seguir adelante y crear esta igual a 6.

467
00:37:09,900 --> 00:37:14,670
Se puede ver que esto toma tiempo y no es super-eficiente.

468
00:37:14,670 --> 00:37:22,610
En tan sólo un poco, vamos a escribir una función que lo hará por nosotros.

469
00:37:22,610 --> 00:37:32,890
Quiero sustituir esto con un 9, reemplazarlo con un 6.

470
00:37:32,890 --> 00:37:37,360
>> Ahora tenemos todos nuestros nodos creado e inicializado.

471
00:37:37,360 --> 00:37:41,200
Tenemos nuestra raíz igual a 7, o que contiene el valor 7,

472
00:37:41,200 --> 00:37:46,510
nuestro nodo que contiene 3, nuestro nodo que contiene 6, y nuestro nodo contiene 9.

473
00:37:46,510 --> 00:37:50,390
En este punto, todo lo que tenemos que hacer es cablear todo.

474
00:37:50,390 --> 00:37:53,020
La razón por la que inicializa todos los punteros a null es sólo para que me aseguro de que

475
00:37:53,020 --> 00:37:56,260
Yo no tengo ningún puntero sin inicializar en allí por accidente.

476
00:37:56,260 --> 00:38:02,290
Y también porque, en este momento, sólo tiene que conectar realmente los nodos entre sí -

477
00:38:02,290 --> 00:38:04,750
a los que en realidad están conectados a - Yo no tengo que ir a través y hacer

478
00:38:04,750 --> 00:38:08,240
Asegúrese de que todos los nulos están ahí en los lugares apropiados.

479
00:38:08,240 --> 00:38:15,630
>> A partir de la raíz, lo sé hijo izquierdo de la raíz es 3.

480
00:38:15,630 --> 00:38:21,250
Sé que hijo derecho de la raíz es 9.

481
00:38:21,250 --> 00:38:24,880
Después de eso, el hijo único que me queda para preocuparse

482
00:38:24,880 --> 00:38:39,080
es hijo derecho 3, que es 6.

483
00:38:39,080 --> 00:38:44,670
En este punto, todo se ve muy bien.

484
00:38:44,670 --> 00:38:54,210
Vamos a eliminar algunas de estas líneas.

485
00:38:54,210 --> 00:38:59,540
Ahora todo se ve muy bien.

486
00:38:59,540 --> 00:39:04,240
Volvamos a nuestras especificaciones y ver lo que tenemos que hacer a continuación.

487
00:39:04,240 --> 00:39:07,610
>> En este punto, tenemos que escribir una función llamada "contiene"

488
00:39:07,610 --> 00:39:14,150
con un prototipo del 'contiene bool (int value).

489
00:39:14,150 --> 00:39:17,060
Y esto incluye la función va a devolver true

490
00:39:17,060 --> 00:39:21,200
 si el árbol apuntado por la variable raíz global

491
00:39:21,200 --> 00:39:26,950
 contiene el valor que se pasa a la función y false en caso contrario.

492
00:39:26,950 --> 00:39:29,000
Vamos a seguir adelante y hacer eso.

493
00:39:29,000 --> 00:39:35,380
Esto va a ser exactamente igual que la búsqueda que hemos hecho a mano en el iPad un poco atrás.

494
00:39:35,380 --> 00:39:40,130
Vamos a volver a aumentar un poco y desplácese hacia arriba.

495
00:39:40,130 --> 00:39:43,130
Vamos a poner esta función justo encima de nuestra función principal

496
00:39:43,130 --> 00:39:48,990
de modo que no tenemos que hacer ningún tipo de prototipos.

497
00:39:48,990 --> 00:39:55,960
Por lo tanto, contiene bool (int value).

498
00:39:55,960 --> 00:40:00,330
Ahí vamos. Ahí está nuestra declaración repetitivo.

499
00:40:00,330 --> 00:40:02,900
Sólo para asegurarse de que esta se compilará,

500
00:40:02,900 --> 00:40:06,820
Voy a seguir adelante y sólo lo hace igual a devolver false.

501
00:40:06,820 --> 00:40:09,980
En este momento esta función simplemente no hacer nada y siempre informan de que

502
00:40:09,980 --> 00:40:14,010
el valor que está buscando no está en el árbol.

503
00:40:14,010 --> 00:40:16,280
>> En este punto, es probablemente una buena idea -

504
00:40:16,280 --> 00:40:19,600
ya que he escrito un montón de código y ni siquiera hemos intentado probarlo todavía -

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

506
00:40:22,590 --> 00:40:27,460
Hay un par de cosas que tenemos que hacer para asegurarse de que esto va a compilar.

507
00:40:27,460 --> 00:40:33,530
En primer lugar, ver si hemos estado utilizando cualquiera de las funciones de las bibliotecas que aún no hemos incluidos.

508
00:40:33,530 --> 00:40:37,940
Las funciones que hemos utilizado hasta ahora son malloc,

509
00:40:37,940 --> 00:40:43,310
y también hemos estado utilizando este tipo - este tipo no estándar llamada "bool' -

510
00:40:43,310 --> 00:40:45,750
que se incluye en el archivo de cabecera bool estándar.

511
00:40:45,750 --> 00:40:53,250
Definitivamente, queremos incluir bool.h estándar para el tipo bool,

512
00:40:53,250 --> 00:40:59,230
y también queremos incluir # lib.h estándar para las bibliotecas estándar

513
00:40:59,230 --> 00:41:03,530
que incluyen malloc y libre, y todo eso.

514
00:41:03,530 --> 00:41:08,660
Por lo tanto, alejar la imagen, vamos a dejar de fumar.

515
00:41:08,660 --> 00:41:14,190
Vamos a tratar de asegurarse de que esto realmente hizo compilación.

516
00:41:14,190 --> 00:41:18,150
Vemos que lo hace, así que estamos en el camino correcto.

517
00:41:18,150 --> 00:41:22,990
>> Vamos a abrir binary_tree.c nuevo.

518
00:41:22,990 --> 00:41:34,530
Compila. Vamos hacia abajo y asegúrese de que insertamos algunas llamadas a nuestra función contiene -

519
00:41:34,530 --> 00:41:40,130
sólo para asegurarse de que eso es todo bien y bueno.

520
00:41:40,130 --> 00:41:43,170
Por ejemplo, cuando hicimos algunas búsquedas en nuestro árbol antes,

521
00:41:43,170 --> 00:41:48,500
hemos tratado de buscar los 6 valores, 10 y 1, y sabíamos que el 6 estaba en el árbol,

522
00:41:48,500 --> 00:41:52,220
10 no estaba en el árbol, y 1 no estaba en el árbol tampoco.

523
00:41:52,220 --> 00:41:57,230
Vamos a usar esas llamadas muestra como una forma de averiguar si es o no

524
00:41:57,230 --> 00:41:59,880
nuestra función contiene está funcionando.

525
00:41:59,880 --> 00:42:05,210
Con el fin de hacer eso, voy a utilizar la función printf,

526
00:42:05,210 --> 00:42:10,280
y vamos a imprimir el resultado de la llamada a la contenga.

527
00:42:10,280 --> 00:42:13,280
Me voy a poner en una cadena "contiene (% d) = porque

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

529
00:42:20,470 --> 00:42:27,130
y =% s \ n ", y usar eso como nuestra cadena de formato.

530
00:42:27,130 --> 00:42:30,720
Sólo vamos a ver - literalmente imprimir en la pantalla -

531
00:42:30,720 --> 00:42:32,060
lo que parece una llamada de función.

532
00:42:32,060 --> 00:42:33,580
Esto no es realmente la llamada a la función.

533
00:42:33,580 --> 00:42:36,760
 Esto es sólo una cadena diseñado para parecerse a una llamada de función.

534
00:42:36,760 --> 00:42:41,140
>> Ahora, vamos a conectar los valores.

535
00:42:41,140 --> 00:42:43,580
Vamos a intentar contiene los días 6,

536
00:42:43,580 --> 00:42:48,340
y entonces, ¿qué vamos a hacer aquí es utilizar ese operador ternario.

537
00:42:48,340 --> 00:42:56,340
Vamos a ver - incluye 6 - así que, ahora que he contenía 6 y si contiene 6 es cierto,

538
00:42:56,340 --> 00:43:01,850
la cadena que vamos a enviar al carácter de formato% s

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

540
00:43:04,850 --> 00:43:07,690
Vamos a desplazarse durante un rato.

541
00:43:07,690 --> 00:43:16,210
De lo contrario, queremos enviar la cadena "false" si contiene 6 devuelve false.

542
00:43:16,210 --> 00:43:19,730
Esto es un poco torpe aspecto, pero me imagino que bien podría ilustrar

543
00:43:19,730 --> 00:43:23,780
lo que el operador ternario parece, ya que no lo he visto por un tiempo.

544
00:43:23,780 --> 00:43:27,670
Esta será una manera agradable, muy práctico para saber si nuestra función contiene está funcionando.

545
00:43:27,670 --> 00:43:30,040
Voy a desplazarse de nuevo hacia la izquierda,

546
00:43:30,040 --> 00:43:39,900
y voy a copiar y pegar esta línea un par de veces.

547
00:43:39,900 --> 00:43:44,910
Cambió algunos de estos valores alrededor,

548
00:43:44,910 --> 00:43:59,380
así que esto va a ser 1, y esto va a ser de 10.

549
00:43:59,380 --> 00:44:02,480
>> En este punto tenemos una función contiene agradable.

550
00:44:02,480 --> 00:44:06,080
Tenemos algunas pruebas, y vamos a ver si funciona todo esto.

551
00:44:06,080 --> 00:44:08,120
En este punto hemos escrito código un poco más.

552
00:44:08,120 --> 00:44:13,160
Es hora de dejar de fumar y asegurarse de que todo lo que todavía compila.

553
00:44:13,160 --> 00:44:20,360
Salir fuera, y ahora vamos a intentar hacer árbol binario de nuevo.

554
00:44:20,360 --> 00:44:22,260
Bueno, parece que tenemos un error,

555
00:44:22,260 --> 00:44:26,930
Y tenemos esta declarar explícitamente la función de biblioteca printf.

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

557
00:44:39,350 --> 00:44:45,350
Y con eso, todo debe compilar. Estamos todos bien.

558
00:44:45,350 --> 00:44:50,420
Ahora vamos a intentar ejecutar árbol binario y ver qué pasa.

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

560
00:44:53,520 --> 00:44:55,190
y vemos que, como esperábamos -

561
00:44:55,190 --> 00:44:56,910
porque no han puesto en práctica contiene, sin embargo,

562
00:44:56,910 --> 00:44:59,800
o más bien, acabamos de poner en return false -

563
00:44:59,800 --> 00:45:03,300
vemos que se acaba de devolver false para todos ellos,

564
00:45:03,300 --> 00:45:06,180
de modo que todo está funcionando en su mayor parte bastante bien.

565
00:45:06,180 --> 00:45:11,860
>> Vamos a ir de nuevo y poner en práctica en realidad contiene en este punto.

566
00:45:11,860 --> 00:45:17,490
Voy a desplazarse hacia abajo, acercar, y -

567
00:45:17,490 --> 00:45:22,330
recuerde, el algoritmo que se utilizó fue que empezamos en el nodo raíz

568
00:45:22,330 --> 00:45:28,010
y luego en cada nodo que encontramos, hacemos una comparación,

569
00:45:28,010 --> 00:45:32,380
y en base a esa comparación que o mover al niño a la izquierda oa la derecha niño.

570
00:45:32,380 --> 00:45:39,670
Esto va a parecer muy similar al código binario de búsqueda que hemos escrito anteriormente en el término.

571
00:45:39,670 --> 00:45:47,810
Cuando nos pusimos en marcha, sabemos que queremos mantener en el nodo actual

572
00:45:47,810 --> 00:45:54,050
que estamos viendo, y el nodo actual va a ser inicializado al nodo raíz.

573
00:45:54,050 --> 00:45:56,260
Y ahora, vamos a seguir adelante a través del árbol,

574
00:45:56,260 --> 00:45:58,140
y recordar que nuestra condición de parada -

575
00:45:58,140 --> 00:46:01,870
 cuando realmente terminado con el ejemplo a mano -

576
00:46:01,870 --> 00:46:03,960
Fue entonces cuando nos encontramos con un nodo nulo,

577
00:46:03,960 --> 00:46:05,480
no cuando miramos a un niño nulo,

578
00:46:05,480 --> 00:46:09,620
sino más bien cuando realmente mueve a un nodo en el árbol

579
00:46:09,620 --> 00:46:12,640
y encontraron que estamos en un nodo nulo.

580
00:46:12,640 --> 00:46:20,720
Vamos a iterar hasta act no es igual a null.

581
00:46:20,720 --> 00:46:22,920
¿Y qué vamos a hacer?

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

583
00:46:31,610 --> 00:46:35,160
entonces sabemos que en realidad hemos encontrado el nodo que estamos buscando.

584
00:46:35,160 --> 00:46:40,450
Así que aquí, podemos volver realidad.

585
00:46:40,450 --> 00:46:49,830
De lo contrario, queremos ver si el valor es menor que el valor.

586
00:46:49,830 --> 00:46:53,850
Si el valor del nodo actual es menor que el valor que estamos buscando,

587
00:46:53,850 --> 00:46:57,280
vamos a mover a la derecha.

588
00:46:57,280 --> 00:47:10,600
Por lo tanto, act act = -> right_child, y de lo contrario, vamos a mover hacia la izquierda.

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

590
00:47:17,480 --> 00:47:22,830
>> Es probable que reconocer el lazo que se ve muy similar a la de este

591
00:47:22,830 --> 00:47:27,580
búsqueda binaria anteriormente en el término, excepto entonces se trataba de mediados baja y alta.

592
00:47:27,580 --> 00:47:30,000
En este caso, sólo tenemos que mirar a un valor actual,

593
00:47:30,000 --> 00:47:31,930
así que es agradable y simple.

594
00:47:31,930 --> 00:47:34,960
Vamos a asegurarnos de que el código esté funcionando.

595
00:47:34,960 --> 00:47:42,780
Primero, asegúrese de que compila. Parece que lo hace.

596
00:47:42,780 --> 00:47:47,920
Vamos a tratar de ejecutarlo.

597
00:47:47,920 --> 00:47:50,160
Y, en efecto, imprime todo lo que esperábamos.

598
00:47:50,160 --> 00:47:54,320
Se encuentra a 6 en el árbol, no encuentra 10 porque 10 no está en el árbol,

599
00:47:54,320 --> 00:47:57,740
y no encuentra ya sea porque 1 1 No es también en el árbol.

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

601
00:48:01,420 --> 00:48:04,470
>> Muy bien. Volvamos a nuestra especificación y ver lo que se viene.

602
00:48:04,470 --> 00:48:07,990
Ahora, quiere agregar nodos algunos más para nuestro árbol.

603
00:48:07,990 --> 00:48:11,690
Quiere añadir 5, 2 y 8, y asegúrese de que contiene nuestro código

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

605
00:48:13,570 --> 00:48:14,900
Vamos a hacer eso.

606
00:48:14,900 --> 00:48:19,430
En este punto, en lugar de hacer que copia molesto y pegar de nuevo,

607
00:48:19,430 --> 00:48:23,770
vamos a escribir una función para crear realmente un nodo.

608
00:48:23,770 --> 00:48:27,740
Si nos desplazamos hacia abajo hasta llegar a principal, vemos que hemos estado haciendo esto

609
00:48:27,740 --> 00:48:31,210
código muy similar una y otra vez cada vez que queremos crear un nodo.

610
00:48:31,210 --> 00:48:39,540
>> Vamos a escribir una función que en realidad va a construir un nodo para nosotros y lo devuelve.

611
00:48:39,540 --> 00:48:41,960
Voy a llamarlo build_node.

612
00:48:41,960 --> 00:48:45,130
Voy a construir un nodo con un valor determinado.

613
00:48:45,130 --> 00:48:51,040
Acércate aquí.

614
00:48:51,040 --> 00:48:56,600
Lo primero que voy a hacer es crear un espacio para el nodo en el montón.

615
00:48:56,600 --> 00:49:05,400
Por lo tanto, el nodo * n = malloc (sizeof (nodo)); n -> valor = valor;

616
00:49:05,400 --> 00:49:14,960
y luego aquí, yo sólo voy a inicializar todos los campos para los valores adecuados.

617
00:49:14,960 --> 00:49:22,500
Y al final, vamos a volver a nuestra nodo.

618
00:49:22,500 --> 00:49:28,690
Muy bien. Una cosa a tener en cuenta es que esta función aquí

619
00:49:28,690 --> 00:49:34,320
va a devolver un puntero a la memoria que ha sido asignada por montón.

620
00:49:34,320 --> 00:49:38,880
Lo bueno de esto es que este nodo ahora -

621
00:49:38,880 --> 00:49:42,420
tenemos que declarar en el montón porque si lo declarado en la pila

622
00:49:42,420 --> 00:49:45,050
no seríamos capaces de hacer en esta función como esta.

623
00:49:45,050 --> 00:49:47,690
Esa memoria se salga del ámbito

624
00:49:47,690 --> 00:49:51,590
y no sería válida si intentamos acceder a él más adelante.

625
00:49:51,590 --> 00:49:53,500
Ya que estamos declarando montón asignado por la memoria,

626
00:49:53,500 --> 00:49:55,830
vamos a tener que cuidar de liberarlo más tarde

627
00:49:55,830 --> 00:49:58,530
para nuestro programa no se escape ningún recuerdo.

628
00:49:58,530 --> 00:50:01,270
Hemos estado en el que batea para todo lo demás en el código

629
00:50:01,270 --> 00:50:02,880
sólo por razones de simplicidad en el momento,

630
00:50:02,880 --> 00:50:05,610
pero si alguna vez escribir una función que tiene este aspecto

631
00:50:05,610 --> 00:50:10,370
donde tienes - algunos lo llaman un malloc o realloc interior -

632
00:50:10,370 --> 00:50:14,330
usted querrá asegurarse de que usted pone algún tipo de comentario por aquí que dice:

633
00:50:14,330 --> 00:50:29,970
bueno, ya sabes, devuelve un nodo de heap asignado se inicializa con el valor pasado como.

634
00:50:29,970 --> 00:50:33,600
Y entonces usted quiere asegurarse de que usted pone en una especie de nota que dice:

635
00:50:33,600 --> 00:50:41,720
el llamador debe liberar la memoria devuelta.

636
00:50:41,720 --> 00:50:45,450
De esa manera, si alguien alguna vez va y usa esa función,

637
00:50:45,450 --> 00:50:48,150
ellos saben que cualquier cosa que regrese de esa función

638
00:50:48,150 --> 00:50:50,870
en algún momento tendrá que ser liberado.

639
00:50:50,870 --> 00:50:53,940
>> Suponiendo que todo está bien y bueno aquí,

640
00:50:53,940 --> 00:51:02,300
podemos bajar a nuestro código y reemplazar todas estas líneas aquí

641
00:51:02,300 --> 00:51:05,410
con llamadas a nuestra función de nodo de generación.

642
00:51:05,410 --> 00:51:08,170
Vamos a hacer esto muy rápidamente.

643
00:51:08,170 --> 00:51:15,840
La única parte que no vamos a sustituir es esta parte aquí abajo

644
00:51:15,840 --> 00:51:18,520
en la parte inferior donde realmente cablear los nodos para que apunte a la otra,

645
00:51:18,520 --> 00:51:21,030
ya que no podemos hacer en nuestra función.

646
00:51:21,030 --> 00:51:37,400
Pero, vamos a hacer root = build_node (7); nodo * = build_node tres (3);

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

648
00:51:47,980 --> 00:51:52,590
Y ahora, también queríamos agregar nodos para -

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

650
00:52:03,530 --> 00:52:09,760
y lo que era el otro nodo? Vamos a ver aquí. Hemos querido añadir también un 2 -

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

652
00:52:20,280 --> 00:52:26,850
Muy bien. En este punto, sabemos que tenemos el 7, el 3, el 9 y el 6

653
00:52:26,850 --> 00:52:30,320
todos conectados de forma apropiada, pero ¿qué pasa con el 5, el 8, y el 2?

654
00:52:30,320 --> 00:52:33,550
Para mantener todo en el orden apropiado,

655
00:52:33,550 --> 00:52:39,230
sabemos que el hijo derecho es tres 6.

656
00:52:39,230 --> 00:52:40,890
Por lo tanto, si vamos a añadir los 5,

657
00:52:40,890 --> 00:52:46,670
el 5 pertenece también en el lado derecho del árbol de los cuales 3 es la raíz,

658
00:52:46,670 --> 00:52:50,440
así como 5 pertenece el hijo izquierdo de 6.

659
00:52:50,440 --> 00:52:58,650
Podemos hacer esto diciendo, seis -> left_child = cinco;

660
00:52:58,650 --> 00:53:10,790
y luego el 8 pertenece como hijo izquierdo de 9, por lo que nueve -> left_child = ocho;

661
00:53:10,790 --> 00:53:22,190
y luego 2 es el hijo izquierdo de 3, por lo que podemos hacer eso aquí - te -> left_child = dos;.

662
00:53:22,190 --> 00:53:27,730
Si usted no acababa de seguir junto con eso, le sugiero que lo alcanzará a ti mismo.

663
00:53:27,730 --> 00:53:35,660
>> Muy bien. Vamos a guardar este. Vamos a salir y asegurarse de que recopila,

664
00:53:35,660 --> 00:53:40,760
y luego podemos añadir en nuestras llamadas contiene.

665
00:53:40,760 --> 00:53:44,120
Parece que todo aún se compila.

666
00:53:44,120 --> 00:53:51,790
Vamos a entrar y añadir en algunos contiene llamadas.

667
00:53:51,790 --> 00:53:59,640
Una vez más, voy a hacer un poco de copiar y pegar.

668
00:53:59,640 --> 00:54:15,860
Ahora vamos a buscar a 5, 8 y 2. Muy bien.

669
00:54:15,860 --> 00:54:28,330
Vamos a asegurarnos de que todo esto se ve bien quieto. Great! Guardar y salir.

670
00:54:28,330 --> 00:54:33,220
Ahora vamos a hacer, compilar, y ahora vamos a correr.

671
00:54:33,220 --> 00:54:37,540
A partir de los resultados, parece que todo está funcionando muy bien y bien.

672
00:54:37,540 --> 00:54:41,780
Great! Así que ahora tenemos a nuestra función CONTAINS escrito.

673
00:54:41,780 --> 00:54:46,160
Vamos a seguir adelante y empezar a trabajar en la forma de insertar nodos en el árbol

674
00:54:46,160 --> 00:54:50,000
ya que, como lo estamos haciendo en este momento, las cosas no son muy bonitos.

675
00:54:50,000 --> 00:54:52,280
>> Si nos remontamos a la especificación,

676
00:54:52,280 --> 00:55:00,540
nos pide que escriba una función llamada insertar - de nuevo, volviendo a bool

677
00:55:00,540 --> 00:55:04,400
para saber si estamos o no en realidad podría insertar el nodo en el árbol -

678
00:55:04,400 --> 00:55:07,710
y luego el valor para insertar en el árbol se especifica como

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

680
00:55:11,060 --> 00:55:18,180
Nos devolverá true si realmente puede insertar el valor del nodo que contiene al árbol,

681
00:55:18,180 --> 00:55:20,930
lo que significa que, uno, tenía suficiente memoria,

682
00:55:20,930 --> 00:55:24,840
y luego dos, ese nodo no existe en el árbol ya que -

683
00:55:24,840 --> 00:55:32,170
Recuerde, nosotros no vamos a tener valores duplicados en el árbol, sólo para hacer las cosas simples.

684
00:55:32,170 --> 00:55:35,590
Muy bien. Volver al principio Código.

685
00:55:35,590 --> 00:55:44,240
Ábrelo. Acercar un poco, a continuación, desplácese hacia abajo.

686
00:55:44,240 --> 00:55:47,220
Vamos a poner la función de inserción justo encima de las CONTAINS.

687
00:55:47,220 --> 00:55:56,360
Una vez más, va a ser llamado insert bool (int value).

688
00:55:56,360 --> 00:56:01,840
Dale un poco más espacio y, a continuación, de forma predeterminada,

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

690
00:56:08,870 --> 00:56:22,620
Ahora, en el fondo, vamos a seguir adelante y en vez de construir manualmente los nodos

691
00:56:22,620 --> 00:56:27,900
principal en nosotros mismos y el cableado hasta el punto que el uno al otro como lo estamos haciendo,

692
00:56:27,900 --> 00:56:30,600
vamos a confiar en nuestra función de inserción de hacer eso.

693
00:56:30,600 --> 00:56:35,510
No vamos a confiar en nuestra función de inserción para construir el árbol entero desde cero todavía,

694
00:56:35,510 --> 00:56:39,970
sino que más bien nos desharemos de estas líneas - nos volveremos comentar estas líneas -

695
00:56:39,970 --> 00:56:43,430
que construir los nodos 5, 8 y 2.

696
00:56:43,430 --> 00:56:55,740
Y en su lugar, vamos a insertar llamadas a nuestra función de inserción

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

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

699
00:57:05,840 --> 00:57:09,300
>> Ahora hemos comentado estas líneas.

700
00:57:09,300 --> 00:57:13,700
Sólo tenemos 7, 3, 9, y 6 en nuestro árbol en este punto.

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

702
00:57:18,870 --> 00:57:25,050
podemos alejar, hacer nuestro árbol binario,

703
00:57:25,050 --> 00:57:30,750
ejecutarlo, y podemos ver que contiene ahora nos dicen que estamos totalmente a la derecha -

704
00:57:30,750 --> 00:57:33,110
5, 8, y 2 ya no están en el árbol.

705
00:57:33,110 --> 00:57:37,960
Volver atrás en el código,

706
00:57:37,960 --> 00:57:41,070
y ¿cómo vamos a insertar?

707
00:57:41,070 --> 00:57:46,290
Recuerda lo que hicimos cuando estábamos en realidad la inserción de 5, 8, y 2 previamente.

708
00:57:46,290 --> 00:57:50,100
Hemos jugado a ese juego Plinko donde empezamos en la raíz,

709
00:57:50,100 --> 00:57:52,780
bajó el árbol por uno por uno

710
00:57:52,780 --> 00:57:54,980
hasta encontrar el hueco apropiado,

711
00:57:54,980 --> 00:57:57,570
y luego por cable en el nodo en el lugar apropiado.

712
00:57:57,570 --> 00:57:59,480
Vamos a hacer lo mismo.

713
00:57:59,480 --> 00:58:04,070
Esto es básicamente como escribir el código que usamos en la función CONTAINS

714
00:58:04,070 --> 00:58:05,910
para encontrar el punto donde el nodo debe ser,

715
00:58:05,910 --> 00:58:10,560
y entonces sólo vamos a insertar el nodo allí.

716
00:58:10,560 --> 00:58:17,000
Vamos a empezar a hacer eso.

717
00:58:17,000 --> 00:58:24,200
>> Así que tenemos un nodo * act = root, sólo vamos a seguir el código contiene

718
00:58:24,200 --> 00:58:26,850
hasta que nos encontramos con que no acaba de funcionar para nosotros.

719
00:58:26,850 --> 00:58:32,390
Vamos a ir a través del árbol, mientras que el elemento actual no es nulo,

720
00:58:32,390 --> 00:58:45,280
y si encontramos que act valor es igual al valor que estamos tratando de insertar -

721
00:58:45,280 --> 00:58:49,600
bueno, este es uno de los casos en los que no pudimos insertar el nodo

722
00:58:49,600 --> 00:58:52,730
en el árbol porque esto significa que tenemos un valor duplicado.

723
00:58:52,730 --> 00:58:59,010
Aquí estamos en realidad va a devolver false.

724
00:58:59,010 --> 00:59:08,440
Ahora bien, si el valor act es menor que el valor,

725
00:59:08,440 --> 00:59:10,930
ahora sabemos que nos movemos hacia la derecha

726
00:59:10,930 --> 00:59:17,190
 porque el valor pertenece en la mitad derecha del árbol act.

727
00:59:17,190 --> 00:59:30,110
De lo contrario, vamos a mover hacia la izquierda.

728
00:59:30,110 --> 00:59:37,980
Eso es básicamente nuestra función CONTAINS ahí.

729
00:59:37,980 --> 00:59:41,820
>> En este punto, una vez que hayamos completado este bucle while,

730
00:59:41,820 --> 00:59:47,350
nuestro puntero act va a estar apuntando a null

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

732
00:59:51,540 --> 00:59:58,710
Estamos por lo tanto tener act en el lugar donde queremos insertar el nuevo nodo.

733
00:59:58,710 --> 01:00:05,210
Lo que queda por hacer es construir realmente el nuevo nodo,

734
01:00:05,210 --> 01:00:08,480
que podemos hacer con bastante facilidad.

735
01:00:08,480 --> 01:00:14,930
Podemos utilizar nuestra super manejable y función de nodo de generación,

736
01:00:14,930 --> 01:00:17,210
y es algo que no hemos hecho antes -

737
01:00:17,210 --> 01:00:21,400
nosotros sólo tipo de daba por hecho, pero ahora lo haremos sólo para asegurarse de -

738
01:00:21,400 --> 01:00:27,130
vamos a probar para asegurarse de que el valor devuelto por el nuevo nodo en realidad era

739
01:00:27,130 --> 01:00:33,410
no es nulo, porque no quiero empezar a acceder a esa memoria si es nulo.

740
01:00:33,410 --> 01:00:39,910
Podemos probar para asegurarse de que el nuevo nodo no es igual a null.

741
01:00:39,910 --> 01:00:42,910
O por el contrario, sólo podemos ver si realmente es nulo,

742
01:00:42,910 --> 01:00:52,120
y si es nulo, entonces solo puede devolver false temprano.

743
01:00:52,120 --> 01:00:59,090
>> En este punto, tenemos que cablear nuevo nodo en su lugar correspondiente en el árbol.

744
01:00:59,090 --> 01:01:03,510
Si miramos hacia atrás en la principal y en el que en realidad eran el cableado en los valores de antes,

745
01:01:03,510 --> 01:01:08,470
vemos que la forma en que lo hacían cuando querían poner 3 en el árbol

746
01:01:08,470 --> 01:01:11,750
Se accede a que el hijo izquierdo de la raíz.

747
01:01:11,750 --> 01:01:14,920
Cuando ponemos 9 en el árbol, tuvimos que acceder al hijo derecho de la raíz.

748
01:01:14,920 --> 01:01:21,030
Teníamos que tener un puntero a la matriz con el fin de poner un nuevo valor en el árbol.

749
01:01:21,030 --> 01:01:24,430
Desplazamiento de una copia de seguridad para insertar, eso no va a funcionar bastante aquí

750
01:01:24,430 --> 01:01:27,550
porque no tenemos un puntero padres.

751
01:01:27,550 --> 01:01:31,650
Lo que quiero ser capaz de hacer es, en este punto,

752
01:01:31,650 --> 01:01:37,080
comprobar el valor de los padres y ver - bueno, caramba,

753
01:01:37,080 --> 01:01:41,990
si el valor de los padres es menor que el valor de la corriente,

754
01:01:41,990 --> 01:01:54,440
entonces hijo derecho de los padres debe ser el nuevo nodo;

755
01:01:54,440 --> 01:02:07,280
de lo contrario, hijo izquierdo del padre debería ser el nodo nuevo.

756
01:02:07,280 --> 01:02:10,290
Pero, no tenemos este puntero padre todavía.

757
01:02:10,290 --> 01:02:15,010
>> Para conseguirlo, estamos en realidad va a tener que seguir a medida que avanzamos a través del árbol

758
01:02:15,010 --> 01:02:18,440
y encontrar el lugar adecuado en nuestro bucle anterior.

759
01:02:18,440 --> 01:02:26,840
Podemos hacerlo de nuevo, desplazándose hasta la parte superior de nuestra función de inserción

760
01:02:26,840 --> 01:02:32,350
y el seguimiento de otra variable puntero llamado el padre.

761
01:02:32,350 --> 01:02:39,340
Vamos a ponerlo igual a null inicialmente,

762
01:02:39,340 --> 01:02:43,640
y entonces cada vez que pasamos por el árbol,

763
01:02:43,640 --> 01:02:51,540
vamos a establecer el puntero padre para que coincida con el puntero actual.

764
01:02:51,540 --> 01:02:59,140
Establecer padre igual act.

765
01:02:59,140 --> 01:03:02,260
De esta manera, cada vez que vamos a través,

766
01:03:02,260 --> 01:03:05,550
vamos a garantizar que, como el actual puntero se incrementa

767
01:03:05,550 --> 01:03:12,640
el puntero del padre que sigue - sólo un nivel más alto que el actual puntero en el árbol.

768
01:03:12,640 --> 01:03:17,370
Que todo se ve muy bien.

769
01:03:17,370 --> 01:03:22,380
>> Creo que la única cosa que vamos a querer ajustar es construir este nodo nulo retorno.

770
01:03:22,380 --> 01:03:25,380
Con el fin de conseguir construir nodo para volver realidad con éxito nulo,

771
01:03:25,380 --> 01:03:31,060
vamos a tener que modificar el código,

772
01:03:31,060 --> 01:03:37,270
porque aquí, nunca hemos probado para asegurarse de que malloc devuelve un puntero válido.

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

774
01:03:53,390 --> 01:03:55,250
si malloc devuelve un puntero válido, entonces vamos a inicializar;

775
01:03:55,250 --> 01:04:02,540
de lo contrario, sólo tendremos que regresar y que va a terminar devolviendo un valor nulo para nosotros.

776
01:04:02,540 --> 01:04:13,050
Ahora todo se ve muy bien. Vamos a asegurarnos de que esto realmente compila.

777
01:04:13,050 --> 01:04:22,240
Haga árbol binario, y oh, tenemos algunas cosas que están pasando aquí.

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

779
01:04:29,230 --> 01:04:31,950
Una vez más, con estos compiladores, vamos a empezar en la parte superior.

780
01:04:31,950 --> 01:04:36,380
Lo que eso quiere decir es que estoy llamando a construir nodo antes de que yo he hecho lo declaró.

781
01:04:36,380 --> 01:04:37,730
Volvamos al código muy rápido.

782
01:04:37,730 --> 01:04:43,510
Desplácese hacia abajo y, por supuesto, mi función de inserción se declara

783
01:04:43,510 --> 01:04:47,400
por encima de la función de nodo de generación,

784
01:04:47,400 --> 01:04:50,070
pero estoy tratando de usar construir nodo dentro del inserto.

785
01:04:50,070 --> 01:05:06,610
Voy a entrar y copiar - pegar y luego el nodo de generación manera función aquí en la parte superior.

786
01:05:06,610 --> 01:05:11,750
De esta manera, es de esperar que funcione. Vamos a dar esta otra oportunidad.

787
01:05:11,750 --> 01:05:18,920
Ahora todo se compila. Todo está bien.

788
01:05:18,920 --> 01:05:21,640
>> Pero en este punto, no se han llamado nuestra función de inserción.

789
01:05:21,640 --> 01:05:26,510
Sólo sabemos que compila, así que vamos a ir y poner algunas llamadas pulg

790
01:05:26,510 --> 01:05:28,240
Vamos a hacer que en nuestra función principal.

791
01:05:28,240 --> 01:05:32,390
En este sentido, comentada 5, 8, y 2,

792
01:05:32,390 --> 01:05:36,680
y luego no los cable hasta aquí.

793
01:05:36,680 --> 01:05:41,640
Vamos a hacer algunas llamadas para insertar,

794
01:05:41,640 --> 01:05:46,440
y también vamos a utilizar el mismo tipo de cosas que hemos utilizado

795
01:05:46,440 --> 01:05:52,810
cuando hicimos estas llamadas printf para asegurarse de que todo lo que se te ha insertado correctamente.

796
01:05:52,810 --> 01:06:00,550
Voy a copiar y pegar,

797
01:06:00,550 --> 01:06:12,450
y contiene en lugar de que vamos a hacer de inserción.

798
01:06:12,450 --> 01:06:30,140
Y en vez de 6, 10 y 1, que vamos a utilizar 5, 8 y 2.

799
01:06:30,140 --> 01:06:37,320
Esto debería insertar 5, 8, y 2 en el árbol.

800
01:06:37,320 --> 01:06:44,050
Compilar. Todo está bien. Ahora estamos realmente va a ejecutar nuestro programa.

801
01:06:44,050 --> 01:06:47,330
>> Todo lo devuelve false.

802
01:06:47,330 --> 01:06:53,830
Así, 5, 8 y 2 no ir, y parece que contiene no los encontró tampoco.

803
01:06:53,830 --> 01:06:58,890
¿Qué está pasando? Vamos a reducir.

804
01:06:58,890 --> 01:07:02,160
El primer problema fue que se insertan parecía volver falsa,

805
01:07:02,160 --> 01:07:08,750
y parece que eso es porque nos fuimos en nuestro call return false,

806
01:07:08,750 --> 01:07:14,590
y que en realidad nunca volvió realidad.

807
01:07:14,590 --> 01:07:17,880
Podemos poner esto en marcha.

808
01:07:17,880 --> 01:07:25,290
El segundo problema es que ahora incluso si lo hacemos - guardar esto, salga de esto,

809
01:07:25,290 --> 01:07:34,530
hacer funcionar de nuevo, han compilarlo, a continuación, ejecútelo -

810
01:07:34,530 --> 01:07:37,670
vemos que algo más pasó aquí.

811
01:07:37,670 --> 01:07:42,980
El 5, 8, y 2 nunca se encuentran todavía en el árbol.

812
01:07:42,980 --> 01:07:44,350
Entonces, ¿qué está pasando?

813
01:07:44,350 --> 01:07:45,700
>> Vamos a echar un vistazo a esto en el código.

814
01:07:45,700 --> 01:07:49,790
Vamos a ver si podemos resolver esto.

815
01:07:49,790 --> 01:07:57,940
Empezamos con el padre no es nulo.

816
01:07:57,940 --> 01:07:59,510
Hemos establecido el puntero actual es igual al puntero raíz,

817
01:07:59,510 --> 01:08:04,280
y vamos a trabajar nuestro camino hacia abajo a través del árbol.

818
01:08:04,280 --> 01:08:08,650
Si el nodo actual no es nulo, entonces sabemos que podemos bajar un poco.

819
01:08:08,650 --> 01:08:12,330
Hemos creado nuestro puntero padre para ser igual al puntero actual,

820
01:08:12,330 --> 01:08:15,420
comprobado el valor - si los valores son los mismos que volvimos falsa.

821
01:08:15,420 --> 01:08:17,540
Si los valores son menores que nos mudamos a la derecha;

822
01:08:17,540 --> 01:08:20,399
de lo contrario, nos trasladamos a la izquierda.

823
01:08:20,399 --> 01:08:24,220
A continuación, se construye un nodo. Voy a ampliar un poco.

824
01:08:24,220 --> 01:08:31,410
Y aquí, vamos a tratar de cablear los valores a ser el mismo.

825
01:08:31,410 --> 01:08:37,250
¿Qué está pasando? Vamos a ver si posiblemente Valgrind puede darnos una pista.

826
01:08:37,250 --> 01:08:43,910
>> Me gusta usar Valgrind Valgrind sólo porque corre muy rápido

827
01:08:43,910 --> 01:08:46,729
y te dice si hay errores de memoria.

828
01:08:46,729 --> 01:08:48,300
Cuando corremos Valgrind en el código,

829
01:08:48,300 --> 01:08:55,859
como pueden ver afectados here--Valgrind./binary_tree--and derecho entrar.

830
01:08:55,859 --> 01:09:03,640
Ya ves que no tenía ningún error de memoria, así que parece que todo está bien hasta ahora.

831
01:09:03,640 --> 01:09:07,529
Tenemos algunas pérdidas de memoria, lo que conocemos, porque no somos

832
01:09:07,529 --> 01:09:08,910
pasando a liberar a cualquiera de nuestros nodos.

833
01:09:08,910 --> 01:09:13,050
Vamos a intentar ejecutar GDB para ver lo que realmente está pasando.

834
01:09:13,050 --> 01:09:20,010
Haremos gdb. / Binary_tree. Se arrancado bien.

835
01:09:20,010 --> 01:09:23,670
Vamos a poner un punto de interrupción de la plaquita.

836
01:09:23,670 --> 01:09:28,600
Vamos a correr.

837
01:09:28,600 --> 01:09:31,200
Parece que nunca nos llama en realidad inserción.

838
01:09:31,200 --> 01:09:39,410
Parece que el problema era que cuando me cambié aquí en principal -

839
01:09:39,410 --> 01:09:44,279
todas estas llamadas de printf contiene -

840
01:09:44,279 --> 01:09:56,430
En realidad, nunca cambió de inmediato a llamar inserción.

841
01:09:56,430 --> 01:10:01,660
Ahora vamos a darle una oportunidad. Vamos a compilar.

842
01:10:01,660 --> 01:10:09,130
Todo se ve bien allí. Ahora vamos a tratar de ejecutarlo, a ver qué pasa.

843
01:10:09,130 --> 01:10:13,320
¡Muy bien! Todo se ve muy bien allí.

844
01:10:13,320 --> 01:10:18,130
>> La última cosa a considerar es, ¿hay casos límite a esta inserción?

845
01:10:18,130 --> 01:10:23,170
Y resulta que, bueno, el caso extremo que es siempre interesante pensar

846
01:10:23,170 --> 01:10:26,250
Es decir, ¿qué pasa si el árbol está vacío y se llama a esta función de inserción?

847
01:10:26,250 --> 01:10:30,330
¿Funcionará? Bueno, vamos a darle una oportunidad.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
La forma en que vamos a probar esto, vamos a ir a nuestra función principal,

850
01:10:35,810 --> 01:10:41,690
y en lugar de cableado de estos nodos de esta manera,

851
01:10:41,690 --> 01:10:56,730
sólo vamos a comentar toda la cosa,

852
01:10:56,730 --> 01:11:02,620
y en vez de nosotros mismos cableando los nodos,

853
01:11:02,620 --> 01:11:09,400
en realidad podemos simplemente seguir adelante y borrar todo esto.

854
01:11:09,400 --> 01:11:17,560
Vamos a hacer todo lo que una llamada a insertar.

855
01:11:17,560 --> 01:11:49,020
Por lo tanto, vamos a hacer - en vez de 5, 8 y 2, vamos a insertar 7, 3, y 9.

856
01:11:49,020 --> 01:11:58,440
Y luego también querrá insertar 6 también.

857
01:11:58,440 --> 01:12:05,190
Guardar. Salir. Hacer árbol binario.

858
01:12:05,190 --> 01:12:08,540
Todo compila.

859
01:12:08,540 --> 01:12:10,320
Sólo se puede ejecutar como está y ver qué pasa,

860
01:12:10,320 --> 01:12:12,770
pero también va a ser muy importante para asegurarse de que

861
01:12:12,770 --> 01:12:14,740
no tenemos ningún error de memoria,

862
01:12:14,740 --> 01:12:16,840
ya que este es uno de nuestros casos extremos que conocemos.

863
01:12:16,840 --> 01:12:20,150
>> Vamos a asegurarnos de que funciona bien bajo Valgrind,

864
01:12:20,150 --> 01:12:28,310
que vamos a hacer simplemente ejecutando Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Parece que sí tienen un error de un contexto -

866
01:12:31,110 --> 01:12:33,790
tenemos este fallo de segmentación.

867
01:12:33,790 --> 01:12:36,690
¿Qué ha pasado?

868
01:12:36,690 --> 01:12:41,650
Valgrind en realidad nos dice dónde está.

869
01:12:41,650 --> 01:12:43,050
Reducir un poco.

870
01:12:43,050 --> 01:12:46,040
Parece que lo que está sucediendo en nuestra función de inserción,

871
01:12:46,040 --> 01:12:53,420
donde tenemos una lectura no válida del 4 al tamaño de inserción, la línea 60.

872
01:12:53,420 --> 01:13:03,590
Vamos a volver atrás y ver lo que está pasando aquí.

873
01:13:03,590 --> 01:13:05,350
Alejar muy rápido.

874
01:13:05,350 --> 01:13:14,230
Quiero para asegurarse de que no va hasta el borde de la pantalla para que podamos ver todo.

875
01:13:14,230 --> 01:13:18,760
Tire de que en un poco. Muy bien.

876
01:13:18,760 --> 01:13:35,030
Desplácese hacia abajo, y el problema está aquí.

877
01:13:35,030 --> 01:13:40,120
¿Qué sucede si nos ponemos manos y nuestro nodo actual ya es nulo,

878
01:13:40,120 --> 01:13:44,010
nuestro nodo padre es nulo, por lo que si miramos hacia arriba en la parte superior, a la derecha aquí -

879
01:13:44,010 --> 01:13:47,340
si nunca este bucle while ejecuta realmente

880
01:13:47,340 --> 01:13:52,330
porque nuestro valor actual es nulo - nuestra raíz es nulo así act es nulo -

881
01:13:52,330 --> 01:13:57,810
entonces nunca nuestro padre se establece en act oa un valor válido,

882
01:13:57,810 --> 01:14:00,580
así, los padres también será nulo.

883
01:14:00,580 --> 01:14:03,700
Tenemos que recordar para comprobar que

884
01:14:03,700 --> 01:14:08,750
en el momento en que nos pongamos aquí, y empezar a acceder valor de los padres.

885
01:14:08,750 --> 01:14:13,190
Entonces, ¿qué sucede? Bueno, si el padre es nulo -

886
01:14:13,190 --> 01:14:17,990
if (padre == NULL) - entonces sabemos que

887
01:14:17,990 --> 01:14:19,530
no debe haber nada en el árbol.

888
01:14:19,530 --> 01:14:22,030
Debemos estar intentando insertarlo en la raíz.

889
01:14:22,030 --> 01:14:32,570
Podemos hacer eso con sólo ajustar la raíz igual al nuevo nodo.

890
01:14:32,570 --> 01:14:40,010
Entonces en este punto, que en realidad no quieren pasar por estas otras cosas.

891
01:14:40,010 --> 01:14:44,780
En cambio, aquí, podemos hacer bien una cosa-if-else,

892
01:14:44,780 --> 01:14:47,610
o podemos combinar todo aquí en una cosa,

893
01:14:47,610 --> 01:14:56,300
pero aquí sólo tendremos que usar más y hacerlo de esa manera.

894
01:14:56,300 --> 01:14:59,030
Ahora, vamos a probarlo para asegurarse de que nuestro padre no es nulo

895
01:14:59,030 --> 01:15:02,160
antes de esa realidad tratando de acceder a sus campos.

896
01:15:02,160 --> 01:15:05,330
Esto nos ayudará a evitar el fallo de segmentación.

897
01:15:05,330 --> 01:15:14,740
Así pues, dejar de fumar, reducir, compilar, ejecutar.

898
01:15:14,740 --> 01:15:18,130
>> No hay errores, pero todavía tenemos un montón de pérdidas de memoria

899
01:15:18,130 --> 01:15:20,650
porque no liberar a cualquiera de nuestros nodos.

900
01:15:20,650 --> 01:15:24,350
Pero, si vamos por aquí y nos fijamos en nuestro listado,

901
01:15:24,350 --> 01:15:30,880
vemos que, bueno, parece que todos nuestros insertos se devuelve true, lo cual es bueno.

902
01:15:30,880 --> 01:15:33,050
Los insertos son todas verdaderas,

903
01:15:33,050 --> 01:15:36,670
y luego las llamadas contiene apropiados, son ciertas.

904
01:15:36,670 --> 01:15:41,510
>> ¡Buen trabajo! Parece que has escrito correctamente inserto.

905
01:15:41,510 --> 01:15:47,430
Eso es todo lo que tenemos para la especificación de esta semana Problema.

906
01:15:47,430 --> 01:15:51,720
Un divertido desafío es pensar en cómo usted iría en

907
01:15:51,720 --> 01:15:55,340
y libre de todos los nodos de este árbol.

908
01:15:55,340 --> 01:15:58,830
Podemos hacer un número de maneras diferentes,

909
01:15:58,830 --> 01:16:01,930
pero lo dejo a usted para experimentar,

910
01:16:01,930 --> 01:16:06,080
y como un reto divertido, tratar de asegurarse de que usted puede asegurarse de que

911
01:16:06,080 --> 01:16:09,490
que este informe Valgrind devuelve ningún error y sin fugas.

912
01:16:09,490 --> 01:16:12,880
>> Buena suerte en el set de esta semana Huffman problema de codificación,

913
01:16:12,880 --> 01:16:14,380
y nos vemos la próxima semana!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]