1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Sección 7: más cómodo]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvard University]

3
00:00:05,090 --> 00:00:07,930
[Esta es CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Está bien. Así que, como dije en mi e-mail,

5
00:00:10,110 --> 00:00:14,060
esto va a ser una sección del árbol binario de obra.

6
00:00:14,060 --> 00:00:16,820
Pero no hay que muchas preguntas.

7
00:00:16,820 --> 00:00:18,920
Así que vamos a tratar de sacar cada pregunta

8
00:00:18,920 --> 00:00:25,430
y entrar en detalles dolorosos de las mejores maneras de hacer las cosas.

9
00:00:25,430 --> 00:00:31,200
Así que desde el principio, vamos a través de los dibujos de la muestra de árboles binarios y esas cosas.

10
00:00:31,200 --> 00:00:35,970
Así que aquí, "Recuerda que un árbol binario tiene nodos similares a los de una lista enlazada,

11
00:00:35,970 --> 00:00:38,150
pero en lugar de un puntero hay dos: uno para "niño" a la izquierda

12
00:00:38,150 --> 00:00:41,950
y otro para la derecha "niño". "

13
00:00:41,950 --> 00:00:45,630
Así que un árbol binario es igual que una lista enlazada,

14
00:00:45,630 --> 00:00:47,910
excepto la estructura va a tener dos punteros.

15
00:00:47,910 --> 00:00:51,390
Hay árboles trinarios, que van a tener tres punteros,

16
00:00:51,390 --> 00:00:56,540
hay N-arias árboles, que sólo tienen un puntero genérico

17
00:00:56,540 --> 00:01:00,320
que usted entonces tiene que malloc ser lo suficientemente grande para tener

18
00:01:00,320 --> 00:01:04,840
indicadores suficientes para todos los niños posibles.

19
00:01:04,840 --> 00:01:08,200
Así árbol binario sólo pasa a tener un número constante de dos.

20
00:01:08,200 --> 00:01:11,260
Si lo desea, puede dar una lista enlazada como un árbol unario,

21
00:01:11,260 --> 00:01:15,360
pero yo no creo que nadie lo llama eso.

22
00:01:15,360 --> 00:01:18,060
"Dibujar un diagrama de cajas y flechas de un nodo del árbol binario

23
00:01:18,060 --> 00:01:24,110
que contiene el número preferido de Nate, 7, donde cada puntero niño es nulo. "

24
00:01:24,110 --> 00:01:27,780
Así que el modo de iPad.

25
00:01:27,780 --> 00:01:30,280
>> Va a ser bastante sencillo.

26
00:01:30,280 --> 00:01:36,150
Sólo vamos a tener un nodo, lo voy a dibujar un cuadrado.

27
00:01:36,150 --> 00:01:38,730
Y voy a sacar los valores de aquí.

28
00:01:38,730 --> 00:01:41,090
Así, el valor pasará de aquí,

29
00:01:41,090 --> 00:01:44,770
y entonces aquí vamos a tener el puntero a la izquierda de la izquierda y el puntero a la derecha en la derecha.

30
00:01:44,770 --> 00:01:50,430
Y es mucho lo que la convención de llamar a la izquierda y la derecha, los nombres de puntero.

31
00:01:50,430 --> 00:01:52,460
Ambos van a ser nulo.

32
00:01:52,460 --> 00:01:57,870
Eso sólo será nulo, y que sólo será nulo.

33
00:01:57,870 --> 00:02:03,630
Bien. Así que de vuelta a aquí.

34
00:02:03,630 --> 00:02:05,700
"Con una lista enlazada, sólo teníamos que almacenar un puntero

35
00:02:05,700 --> 00:02:09,639
al primer nodo de la lista para recordar toda la lista vinculada, o toda la lista.

36
00:02:09,639 --> 00:02:11,650
Del mismo modo, con los árboles, sólo tiene que almacenar un puntero

37
00:02:11,650 --> 00:02:13,420
a un único nodo con el fin de recordar a todo el árbol.

38
00:02:13,420 --> 00:02:15,980
Este nodo es la calle "raíz" del árbol.

39
00:02:15,980 --> 00:02:18,320
Basarse en el diagrama de antes o dibujar uno nuevo

40
00:02:18,320 --> 00:02:21,690
de tal manera que tiene una representación cajas y flechas de un árbol binario

41
00:02:21,690 --> 00:02:25,730
con el valor de 7, a continuación, 3 en la izquierda,

42
00:02:25,730 --> 00:02:32,760
a continuación, 9 a la derecha, y luego 6 a la derecha de la 3. "

43
00:02:32,760 --> 00:02:34,810
Vamos a ver si puedo recordar todo eso en mi cabeza.

44
00:02:34,810 --> 00:02:37,670
Así que esto va a ser nuestra raíz hasta aquí.

45
00:02:37,670 --> 00:02:41,600
Vamos a tener un poco de puntero en algún lugar, algo que llamaremos raíz,

46
00:02:41,600 --> 00:02:45,140
y que apunta a este tipo.

47
00:02:45,140 --> 00:02:48,490
Ahora para hacer un nuevo nodo,

48
00:02:48,490 --> 00:02:52,870
¿qué es lo que tenemos, 3 a la izquierda?

49
00:02:52,870 --> 00:02:57,140
Así que un nuevo nodo con 3, y que señala inicialmente nulo.

50
00:02:57,140 --> 00:02:59,190
Voy a poner N.

51
00:02:59,190 --> 00:03:02,250
Ahora queremos hacer que ir a la izquierda 7.

52
00:03:02,250 --> 00:03:06,840
Así que cambiamos este puntero para apuntar ahora a este tipo.

53
00:03:06,840 --> 00:03:12,420
Y hacemos lo mismo. Queremos un 9 por aquí

54
00:03:12,420 --> 00:03:14,620
que en un principio sólo dice nulo.

55
00:03:14,620 --> 00:03:19,600
Vamos a cambiar este puntero, señale a 9,

56
00:03:19,600 --> 00:03:23,310
y ahora queremos poner 6 a la derecha de 3.

57
00:03:23,310 --> 00:03:32,170
Así que va a - hacer un 6.

58
00:03:32,170 --> 00:03:34,310
Y ese chico va a apuntar allí.

59
00:03:34,310 --> 00:03:38,320
Bien. Así que eso es todo lo que se nos pide que hagamos.

60
00:03:38,320 --> 00:03:42,770
>> Ahora vamos a repasar algunos términos.

61
00:03:42,770 --> 00:03:46,690
Ya hemos hablado de cómo la raíz del árbol es el nodo de más arriba en el árbol.

62
00:03:46,690 --> 00:03:54,720
El uno que contiene 7. Los nodos en la parte inferior del árbol se llaman las hojas.

63
00:03:54,720 --> 00:04:01,240
Cualquier nodo que sólo tiene nulo como sus hijos es una hoja.

64
00:04:01,240 --> 00:04:03,680
Así es posible, si nuestro árbol binario es sólo un único nodo,

65
00:04:03,680 --> 00:04:10,130
que un árbol es una hoja, y eso es todo.

66
00:04:10,130 --> 00:04:12,060
"El 'height' del árbol es el número de saltos que tiene que hacer

67
00:04:12,060 --> 00:04:16,620
para llegar desde la parte superior a una hoja. "

68
00:04:16,620 --> 00:04:18,640
Vamos a entrar, en un segundo, la diferencia

69
00:04:18,640 --> 00:04:21,940
entre los árboles binarios balanceados y no balanceados,

70
00:04:21,940 --> 00:04:29,470
pero por ahora, la altura total de este árbol

71
00:04:29,470 --> 00:04:34,520
Yo diría que es 3, aunque si se cuenta el número de saltos

72
00:04:34,520 --> 00:04:39,710
lo que tienes que hacer para llegar a 9, entonces es realmente sólo una altura de 2.

73
00:04:39,710 --> 00:04:43,340
En este momento se trata de un árbol binario desequilibrado,

74
00:04:43,340 --> 00:04:49,840
pero vamos a hablar acerca de equilibrado cuando llega a ser relevante.

75
00:04:49,840 --> 00:04:52,040
Así que ahora podemos hablar de los nodos de un árbol en términos

76
00:04:52,040 --> 00:04:54,700
con respecto a los otros nodos en el árbol.

77
00:04:54,700 --> 00:04:59,730
Así que ahora tenemos padres, hijos, hermanos, ascendientes y descendientes.

78
00:04:59,730 --> 00:05:05,650
Son bastante sentido común, lo que significan.

79
00:05:05,650 --> 00:05:09,610
Si nos preguntamos - son los padres.

80
00:05:09,610 --> 00:05:12,830
Entonces, ¿qué es el padre de 3?

81
00:05:12,830 --> 00:05:16,090
[Los estudiantes] 7. Sí >>. El padre es sólo va a ser lo señala a usted.

82
00:05:16,090 --> 00:05:20,510
Entonces, ¿qué son los niños de 7?

83
00:05:20,510 --> 00:05:23,860
[Los estudiantes] 3 y 9. Sí >>.

84
00:05:23,860 --> 00:05:26,460
Tenga en cuenta que los "niños" significa literalmente hijos,

85
00:05:26,460 --> 00:05:31,010
así que 6 no se aplicaría, porque es como un nieto.

86
00:05:31,010 --> 00:05:35,540
Pero si vamos descendientes, así que lo que son los descendientes de 7?

87
00:05:35,540 --> 00:05:37,500
[Los estudiantes] 3, 6 y 9. Sí >>.

88
00:05:37,500 --> 00:05:42,330
Los descendientes del nodo raíz va a ser todo en el árbol,

89
00:05:42,330 --> 00:05:47,950
excepto tal vez el nodo raíz en sí, si no quieres tener en cuenta que un descendiente.

90
00:05:47,950 --> 00:05:50,750
Y finalmente, los ancestros, por lo que es la dirección opuesta.

91
00:05:50,750 --> 00:05:55,740
¿Cuáles son los antepasados ​​de 6?

92
00:05:55,740 --> 00:05:58,920
[Los estudiantes] 3 y 7. Sí >>. 9 no está incluido.

93
00:05:58,920 --> 00:06:02,520
Es sólo la parte de atrás linaje directo a la raíz

94
00:06:02,520 --> 00:06:13,230
Va a ser sus antepasados.

95
00:06:13,230 --> 00:06:16,300
>> "Decimos que un árbol binario es" ordenado "si para cada nodo en el árbol,

96
00:06:16,300 --> 00:06:19,530
todos sus descendientes de la izquierda tienen valores menores

97
00:06:19,530 --> 00:06:22,890
y todos los de la derecha tienen valores mayores.

98
00:06:22,890 --> 00:06:27,060
Por ejemplo, el árbol de arriba está ordenado, pero no es la única posible ordenado ".

99
00:06:27,060 --> 00:06:30,180
Antes de llegar a eso,

100
00:06:30,180 --> 00:06:36,420
un árbol binario ordenado también se conoce como un árbol binario de búsqueda.

101
00:06:36,420 --> 00:06:38,660
Aquí sucede que se le llama un árbol binario ordenado,

102
00:06:38,660 --> 00:06:41,850
pero nunca he oído llamar un árbol binario ordenado antes,

103
00:06:41,850 --> 00:06:46,650
y en una prueba que son mucho más propensos a poner árbol de búsqueda binaria.

104
00:06:46,650 --> 00:06:49,250
Son uno y el mismo,

105
00:06:49,250 --> 00:06:54,580
y es importante que usted reconozca la distinción entre árbol y árbol binario de búsqueda binaria.

106
00:06:54,580 --> 00:06:58,830
Un árbol binario es un árbol que apunta a dos cosas.

107
00:06:58,830 --> 00:07:02,120
Cada nodo apunta a dos cosas.

108
00:07:02,120 --> 00:07:06,310
No hay razonamiento sobre los valores que se apunta.

109
00:07:06,310 --> 00:07:11,370
Así como aquí, ya que es un árbol de búsqueda binaria,

110
00:07:11,370 --> 00:07:14,030
sabemos que si vamos a la izquierda de 7,

111
00:07:14,030 --> 00:07:16,670
entonces todos los valores que nos sea posible alcanzar

112
00:07:16,670 --> 00:07:19,310
yendo a la izquierda de 7 tiene que ser menor que 7.

113
00:07:19,310 --> 00:07:24,070
Tenga en cuenta que todos los valores menos que 7 son 3 y 6.

114
00:07:24,070 --> 00:07:26,040
Esos son todos a la izquierda de 7.

115
00:07:26,040 --> 00:07:29,020
Si nos vamos a la derecha de 7, todo tiene que ser superior a 7,

116
00:07:29,020 --> 00:07:33,220
9 es tan a la derecha de 7, así que estamos bien.

117
00:07:33,220 --> 00:07:36,150
Este no es el caso de un árbol binario,

118
00:07:36,150 --> 00:07:40,020
para un árbol binario regular que se puede tener en la parte superior 3, 7 a la izquierda,

119
00:07:40,020 --> 00:07:47,630
9 a la izquierda de 7, no hay orden de valores cualesquiera.

120
00:07:47,630 --> 00:07:56,140
Ahora, no vamos a hacer esto porque es tedioso e innecesario,

121
00:07:56,140 --> 00:07:59,400
sino "tratar de extraer árboles ordenados como muchos como usted puede pensar en

122
00:07:59,400 --> 00:08:01,900
usando los números 7, 3, 9, y 6.

123
00:08:01,900 --> 00:08:06,800
¿Cuántos arreglos diferentes hay? ¿Cuál es la altura de cada uno? "

124
00:08:06,800 --> 00:08:10,480
>> Haremos una pareja, pero es la idea principal,

125
00:08:10,480 --> 00:08:16,530
esto no es en manera alguna una representación única de un árbol binario que contiene estos valores.

126
00:08:16,530 --> 00:08:22,760
Todo lo que necesitamos es un árbol binario que contiene 7, 3, 6 y 9.

127
00:08:22,760 --> 00:08:25,960
Otra posibilidad sería válida la raíz es 3,

128
00:08:25,960 --> 00:08:30,260
ir a la izquierda y es 6, vaya a la izquierda y es 7,

129
00:08:30,260 --> 00:08:32,730
ir a la izquierda y es 9.

130
00:08:32,730 --> 00:08:36,169
Que es un árbol binario de búsqueda perfectamente válido.

131
00:08:36,169 --> 00:08:39,570
No es muy útil, ya que es como una lista enlazada

132
00:08:39,570 --> 00:08:43,750
y todos estos punteros son null.

133
00:08:43,750 --> 00:08:48,900
Pero es un árbol válida. ¿Sí?

134
00:08:48,900 --> 00:08:51,310
[Estudiante] ¿Acaso los valores tienen que ser mayores de la derecha?

135
00:08:51,310 --> 00:08:56,700
¿O es esto -? Estos >> quise ir a otro lado.

136
00:08:56,700 --> 00:09:00,960
Hay también - sí, vamos a cambiar eso.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Buena captura.

138
00:09:07,770 --> 00:09:11,730
Todavía tiene que obedecer lo que es un árbol de búsqueda binaria se supone que debe hacer.

139
00:09:11,730 --> 00:09:15,650
Así todo a la izquierda tiene que ser menor que cualquier nodo dado.

140
00:09:15,650 --> 00:09:23,180
Sólo podía mover, por ejemplo, el 6 y lo puso aquí.

141
00:09:23,180 --> 00:09:26,880
No, no podemos. ¿Por qué sigo haciendo esto?

142
00:09:26,880 --> 00:09:35,350
Vamos a hacerlo - aquí es 6, aquí es 7, 6 puntos a 3.

143
00:09:35,350 --> 00:09:39,290
Esto sigue siendo un árbol binario de búsqueda válida.

144
00:09:39,290 --> 00:09:49,260
¿Qué pasa si yo - vamos a ver si puedo llegar a un acuerdo.

145
00:09:49,260 --> 00:09:52,280
Sí, está bien. Entonces, ¿qué está mal con este árbol?

146
00:09:52,280 --> 00:10:08,920
Supongo que ya te he dado un indicio de que hay algo malo en ello.

147
00:10:08,920 --> 00:10:14,430
¿Por qué sigo haciendo esto?

148
00:10:14,430 --> 00:10:18,510
Bien. Esto parece razonable.

149
00:10:18,510 --> 00:10:22,590
Si nos fijamos en cada nodo, como 7, luego a la izquierda de 7 es un 3.

150
00:10:22,590 --> 00:10:24,960
Así que tenemos 3, la cosa a la derecha de 3 es un 6.

151
00:10:24,960 --> 00:10:27,750
Y si miras a los 6, la cosa a la derecha de 6 es un 9.

152
00:10:27,750 --> 00:10:30,910
¿Por qué no es este un árbol binario de búsqueda válido?

153
00:10:30,910 --> 00:10:36,330
[Los estudiantes] 9 es todavía a la izquierda de 7. Sí >>.

154
00:10:36,330 --> 00:10:43,710
Debe ser cierto que todos los valores que posiblemente puede llegar por ir a la izquierda de 7 son menos de 7.

155
00:10:43,710 --> 00:10:49,120
Si se va a la izquierda, de 7, se llega a 3 y todavía podemos llegar a 6,

156
00:10:49,120 --> 00:10:52,520
todavía podemos llegar a 9, pero por haber pasado menos de 7,

157
00:10:52,520 --> 00:10:55,070
no hay que ser capaz de llegar a un número que es mayor que 7.

158
00:10:55,070 --> 00:10:59,830
Así que esto no es un árbol binario de búsqueda válida.

159
00:10:59,830 --> 00:11:02,330
>> Mi hermano tenía realmente una pregunta de la entrevista

160
00:11:02,330 --> 00:11:07,760
que era básicamente esto, sólo algo de código para validar

161
00:11:07,760 --> 00:11:10,500
si un árbol es un árbol de búsqueda binaria,

162
00:11:10,500 --> 00:11:13,580
y así que lo primero que hizo fue simplemente compruebe

163
00:11:13,580 --> 00:11:17,020
si la izquierda y la derecha son correctos, y luego iterar por allí.

164
00:11:17,020 --> 00:11:19,700
Pero no se puede hacer eso, hay que seguir la pista

165
00:11:19,700 --> 00:11:22,550
el hecho de que ahora que me he ido a la izquierda de 7,

166
00:11:22,550 --> 00:11:26,340
todo en este subárbol debe ser menor que 7.

167
00:11:26,340 --> 00:11:28,430
El algoritmo correcto necesita seguir la pista

168
00:11:28,430 --> 00:11:35,970
de los límites de los valores que posiblemente pueden caer pulg

169
00:11:35,970 --> 00:11:38,360
No vamos a ir a través de todos ellos.

170
00:11:38,360 --> 00:11:41,630
Hay una relación de recurrencia agradable,

171
00:11:41,630 --> 00:11:44,810
aunque no hemos llegado a ellos, o no vamos a llegar a ellos,

172
00:11:44,810 --> 00:11:47,030
definir cuántos son en realidad.

173
00:11:47,030 --> 00:11:53,180
Así que hay 14 de ellos.

174
00:11:53,180 --> 00:11:56,020
La idea de la forma en que lo haría matemáticamente es como,

175
00:11:56,020 --> 00:11:59,770
usted puede escoger uno solo para ser el nodo raíz,

176
00:11:59,770 --> 00:12:03,160
y entonces si tomo 7 a ser el nodo raíz,

177
00:12:03,160 --> 00:12:08,150
luego están, por ejemplo, algunos números que pueden ir a ser mi nodo izquierdo,

178
00:12:08,150 --> 00:12:10,440
y hay algunos números que pueden ser mi nodo de la derecha,

179
00:12:10,440 --> 00:12:15,090
pero si tiene n cifras totales, la cantidad que puede ir a la izquierda

180
00:12:15,090 --> 00:12:18,820
más la cantidad que puede ir a la derecha es n - 1.

181
00:12:18,820 --> 00:12:26,130
Así de los números restantes, tienen que ser capaces de ir hacia la izquierda o la derecha.

182
00:12:26,130 --> 00:12:31,580
Parece difícil que, si pongo 3 primero y luego todo lo que tiene que ir a la izquierda,

183
00:12:31,580 --> 00:12:35,080
pero si pongo 7, a continuación, algunas cosas pueden ir a la izquierda y algunas cosas pueden ir a la derecha.

184
00:12:35,080 --> 00:12:39,570
Y por '3 'primero que quise decir todo puede ir a la derecha.

185
00:12:39,570 --> 00:12:42,350
En realidad, sólo hay que pensar en ello como,

186
00:12:42,350 --> 00:12:47,980
cuántas cosas pueden pasar en el siguiente nivel del árbol.

187
00:12:47,980 --> 00:12:50,420
Y viene a ser 14, o puede dibujar todos ellos,

188
00:12:50,420 --> 00:12:54,650
y entonces usted conseguirá 14.

189
00:12:54,650 --> 00:13:01,120
>> Volviendo aquí,

190
00:13:01,120 --> 00:13:03,510
"Ordenó árboles binarios son frescos ya que podemos buscar a través de ellos

191
00:13:03,510 --> 00:13:06,910
de una manera muy similar a la búsqueda a través de una matriz ordenada.

192
00:13:06,910 --> 00:13:10,120
Para ello, partimos de la raíz y vamos por el árbol

193
00:13:10,120 --> 00:13:13,440
hacia las hojas, comprobando los valores de cada nodo con los valores que estamos buscando.

194
00:13:13,440 --> 00:13:15,810
Si el valor del nodo actual es menor que el valor que estamos buscando,

195
00:13:15,810 --> 00:13:18,050
acercarte a hijo derecho del nodo.

196
00:13:18,050 --> 00:13:20,030
De lo contrario, vaya al hijo izquierdo del nodo.

197
00:13:20,030 --> 00:13:22,800
En algún momento, usted encontrará el valor que usted está buscando, o te encontrarás con un valor nulo,

198
00:13:22,800 --> 00:13:28,520
lo que indica que el valor no está en el árbol. "

199
00:13:28,520 --> 00:13:32,450
Tengo que volver a dibujar el árbol que teníamos antes, que tomará un segundo.

200
00:13:32,450 --> 00:13:38,280
Pero queremos mirar hacia arriba si 6, 10 y 1 están en el árbol.

201
00:13:38,280 --> 00:13:49,180
Así que lo que era, 7, 9, 3, 6. Bien.

202
00:13:49,180 --> 00:13:52,730
Los números que desea buscar, queremos mirar hacia arriba 6.

203
00:13:52,730 --> 00:13:55,440
¿Cómo funciona este algoritmo?

204
00:13:55,440 --> 00:14:03,040
Bueno, también tenemos algunos puntero raíz de nuestro árbol.

205
00:14:03,040 --> 00:14:12,460
Y nos volveríamos a ir a la raíz y decir, este valor es igual al valor que estamos buscando?

206
00:14:12,460 --> 00:14:15,000
Así que estamos buscando para 6, así que no es igual.

207
00:14:15,000 --> 00:14:20,140
Por lo tanto, seguir adelante, y ahora se dice, está bien, así que 6 es menor que 7.

208
00:14:20,140 --> 00:14:23,940
¿Significa eso que queremos ir hacia la izquierda, o queremos ir a la derecha?

209
00:14:23,940 --> 00:14:27,340
[Estudiante] Izquierda. Sí >>.

210
00:14:27,340 --> 00:14:33,340
Es mucho más fácil, lo único que tienes que hacer es sacar un nodo del árbol es posible

211
00:14:33,340 --> 00:14:37,760
y entonces no - en lugar de tratar de pensar en tu cabeza,

212
00:14:37,760 --> 00:14:40,020
bien, si es menos, ¿debo ir a la izquierda o ir a la derecha,

213
00:14:40,020 --> 00:14:43,030
sólo mirar a esta imagen, es muy claro que tengo que ir a la izquierda

214
00:14:43,030 --> 00:14:47,700
si este nodo es mayor que el valor que yo estoy buscando.

215
00:14:47,700 --> 00:14:52,600
Así que ir a la izquierda, ahora estoy en 3.

216
00:14:52,600 --> 00:14:57,770
Quiero - 3 es menor que el valor que estoy buscando, que es de 6.

217
00:14:57,770 --> 00:15:03,420
Así que nos vamos a la derecha, y ahora termino a las 6,

218
00:15:03,420 --> 00:15:07,380
que es el valor que estoy buscando, así que me devuelva true.

219
00:15:07,380 --> 00:15:15,760
El siguiente valor que voy a buscar es 10.

220
00:15:15,760 --> 00:15:23,230
Bien. Así que 10, ahora, va a - cortar eso - va a seguir la raíz.

221
00:15:23,230 --> 00:15:27,670
Ahora, el 10 va a ser superior a 7, así que quiero mirar a la derecha.

222
00:15:27,670 --> 00:15:31,660
Voy a venir por aquí, 10 va a ser mayor que 9,

223
00:15:31,660 --> 00:15:34,520
así que voy a querer mirar a la derecha.

224
00:15:34,520 --> 00:15:42,100
Yo vengo por aquí, pero aquí ahora estoy en null.

225
00:15:42,100 --> 00:15:44,170
¿Qué hago si me golpeó nulo?

226
00:15:44,170 --> 00:15:47,440
[Estudiante] Volver falso? Sí >>. No encontré 10.

227
00:15:47,440 --> 00:15:49,800
1 va a ser un caso casi idéntico,

228
00:15:49,800 --> 00:15:51,950
excepto que sólo va a dar la vuelta, en lugar de buscar

229
00:15:51,950 --> 00:15:56,540
por el lado derecho, voy a mirar hacia abajo a la izquierda.

230
00:15:56,540 --> 00:16:00,430
>> Ahora creo que en realidad obtener el código.

231
00:16:00,430 --> 00:16:04,070
Aquí es donde - abrir el aparato CS50 y navegar por su camino,

232
00:16:04,070 --> 00:16:07,010
pero usted puede también hacerlo en el espacio.

233
00:16:07,010 --> 00:16:09,170
Es probable que sea ideal para hacerlo en el espacio,

234
00:16:09,170 --> 00:16:13,760
porque podemos trabajar en el espacio.

235
00:16:13,760 --> 00:16:19,170
"Primero vamos a necesitar una definición de tipo nuevo para un nodo del árbol binario que contiene valores int.

236
00:16:19,170 --> 00:16:21,400
Usando el repetitivo typedef continuación,

237
00:16:21,400 --> 00:16:24,510
crear una definición de nuevo tipo para un nodo en un árbol binario.

238
00:16:24,510 --> 00:16:27,930
Si te quedas atascado. . . "Blah, blah, blah. Okay.

239
00:16:27,930 --> 00:16:30,380
Así que vamos a poner aquí el texto modelo,

240
00:16:30,380 --> 00:16:41,630
typedef struct nodo y nodo. Sí, está bien.

241
00:16:41,630 --> 00:16:44,270
Entonces, ¿qué son los campos que vamos a querer a nuestro nodo?

242
00:16:44,270 --> 00:16:46,520
[Estudiante] Int. y luego dos punteros?

243
00:16:46,520 --> 00:16:49,700
Int >> valor, dos punteros? ¿Cómo puedo escribir los punteros?

244
00:16:49,700 --> 00:16:58,440
[Estudiante] Struct. >> Me zoom in Sí, así struct nodo * a la izquierda,

245
00:16:58,440 --> 00:17:01,320
y struct nodo * derecha.

246
00:17:01,320 --> 00:17:03,460
Y recuerda que el debate de la última vez,

247
00:17:03,460 --> 00:17:15,290
que esto no tiene sentido, esto no tiene sentido,

248
00:17:15,290 --> 00:17:18,270
esto no tiene sentido.

249
00:17:18,270 --> 00:17:25,000
Necesitas todo lo que hay para definir esta estructura recursiva.

250
00:17:25,000 --> 00:17:27,970
Muy bien, así que eso es lo que nuestro árbol va a parecer.

251
00:17:27,970 --> 00:17:37,670
Si hiciéramos un árbol ternario, a continuación, un nodo puede ser como b1, b2, b3 struct nodo *,

252
00:17:37,670 --> 00:17:43,470
donde b es una rama - en realidad, he oído más a la izquierda, centro, derecha, pero lo que sea.

253
00:17:43,470 --> 00:17:55,610
Sólo nos importa binario, por lo derecha, izquierda.

254
00:17:55,610 --> 00:17:59,110
"Ahora declaramos una variable global para el nodo * la raíz del árbol."

255
00:17:59,110 --> 00:18:01,510
Así que no vamos a hacer eso.

256
00:18:01,510 --> 00:18:08,950
Para hacer las cosas un poco más difícil y más generalizada,

257
00:18:08,950 --> 00:18:11,570
no vamos a tener una variable de nodo global.

258
00:18:11,570 --> 00:18:16,710
En cambio, en principal por la que nos declarará todas nuestras cosas de nodos,

259
00:18:16,710 --> 00:18:20,500
y eso significa que más adelante, cuando empezamos a correr

260
00:18:20,500 --> 00:18:23,130
nuestra función CONTAINS y nuestra función de inserción,

261
00:18:23,130 --> 00:18:27,410
en lugar de nuestras contiene la función de sólo usar esta variable nodo global,

262
00:18:27,410 --> 00:18:34,280
vamos a tener que tomar como argumento el árbol que queremos que sean procesados.

263
00:18:34,280 --> 00:18:36,650
Tener la variable global se supone que hace las cosas más fáciles.

264
00:18:36,650 --> 00:18:42,310
Vamos a hacer las cosas más difíciles.

265
00:18:42,310 --> 00:18:51,210
Ahora tome un minuto para sólo hacer este tipo de cosas,

266
00:18:51,210 --> 00:18:57,690
donde dentro de la principal que desea crear este árbol, y eso es todo lo que quiero hacer.

267
00:18:57,690 --> 00:19:04,530
Trate de construir este árbol en su función principal.

268
00:19:42,760 --> 00:19:47,610
>> Bien. Así que no tienen ni siquiera haber construido el árbol durante todo el camino todavía.

269
00:19:47,610 --> 00:19:49,840
Pero alguien tiene algo que pudiera levantar

270
00:19:49,840 --> 00:20:03,130
para mostrar cómo se puede empezar a construir un árbol?

271
00:20:03,130 --> 00:20:08,080
[Estudiante] Alguien está golpeando, tratando de salir.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Cualquier persona cómodos con su construcción del árbol?

273
00:20:13,100 --> 00:20:15,520
[Estudiante] Claro. No se hace. >> Está bien. Sólo podemos terminar -

274
00:20:15,520 --> 00:20:26,860
oh, puede usted ahorrar? ¡Hurra.

275
00:20:26,860 --> 00:20:32,020
Así que aquí tenemos - oh, estoy un poco cortado.

276
00:20:32,020 --> 00:20:34,770
¿Estoy zoom?

277
00:20:34,770 --> 00:20:37,730
Zoom hacia dentro, desplácese hacia fuera. >> Tengo una pregunta. >> ¿Sí?

278
00:20:37,730 --> 00:20:44,410
[Estudiante] Cuando se define una estructura, son cosas como inicializado a algo?

279
00:20:44,410 --> 00:20:47,160
[Bowden] >> No. Está bien. Así que tendría que inicializar -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No. Cuando se define, o cuando se declara una struct,

281
00:20:50,450 --> 00:20:55,600
no se inicializa de forma predeterminada, es igual que si se declara un int.

282
00:20:55,600 --> 00:20:59,020
Es exactamente lo mismo. Es como si cada uno de sus campos individuales

283
00:20:59,020 --> 00:21:04,460
puede tener un valor basura en ella. >> Y es posible definir - o declarar a una estructura

284
00:21:04,460 --> 00:21:07,740
de una manera que lo hace inicializar ellos?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Sí. Por lo tanto, el acceso directo sintaxis de inicialización

286
00:21:13,200 --> 00:21:18,660
se va a ver como -

287
00:21:18,660 --> 00:21:22,200
Hay dos formas en que podemos hacer esto. Creo que debemos compilarlo

288
00:21:22,200 --> 00:21:25,840
para hacer Clang seguro también lo hace.

289
00:21:25,840 --> 00:21:28,510
El orden de los argumentos que viene en la estructura,

290
00:21:28,510 --> 00:21:32,170
usted pone el orden de los argumentos dentro de estas llaves.

291
00:21:32,170 --> 00:21:35,690
Así que si usted desea inicializar a 9 y se queda nulo y luego a la derecha ser nulo,

292
00:21:35,690 --> 00:21:41,570
sería 9, null, null.

293
00:21:41,570 --> 00:21:47,890
La alternativa es, y el editor no le gusta esta sintaxis,

294
00:21:47,890 --> 00:21:50,300
y se cree que quiero un nuevo bloque,

295
00:21:50,300 --> 00:22:01,800
pero la alternativa es algo así como -

296
00:22:01,800 --> 00:22:04,190
aquí, lo voy a poner en una nueva línea.

297
00:22:04,190 --> 00:22:09,140
Usted puede explicitamente decir, no recuerdo la sintaxis exacta.

298
00:22:09,140 --> 00:22:13,110
Así que usted puede abordar explícitamente por su nombre, y decir:

299
00:22:13,110 --> 00:22:21,570
. C o. = Valor 9,. Izquierda = NULL.

300
00:22:21,570 --> 00:22:24,540
Supongo que estos deben ser comas.

301
00:22:24,540 --> 00:22:29,110
. Derecha = NULL, por lo que este camino no lo hace

302
00:22:29,110 --> 00:22:33,780
realmente necesita saber el orden de la estructura,

303
00:22:33,780 --> 00:22:36,650
y cuando usted está leyendo esto, es mucho más explícita

304
00:22:36,650 --> 00:22:41,920
acerca de cuál es el valor que se está inicializado a.

305
00:22:41,920 --> 00:22:44,080
>> Esto pasa a ser una de las cosas que -

306
00:22:44,080 --> 00:22:49,100
así, en su mayor parte, C + + es un superconjunto de C.

307
00:22:49,100 --> 00:22:54,160
Usted puede tomar el código C, moverlo a C + +, y se debe compilar.

308
00:22:54,160 --> 00:22:59,570
Esta es una de las cosas que C + + no admite, por lo que la gente tiende a no hacerlo.

309
00:22:59,570 --> 00:23:01,850
No sé si esa es la única razón por la gente tiende a no hacerlo,

310
00:23:01,850 --> 00:23:10,540
pero el caso donde tenía que usarlo necesario para trabajar con C + + y lo que no podía usarlo.

311
00:23:10,540 --> 00:23:14,000
Otro ejemplo de algo que no funciona en C + + es

312
00:23:14,000 --> 00:23:16,940
como malloc devuelve un "void *," técnicamente,

313
00:23:16,940 --> 00:23:20,200
pero usted podría decir char * x = cualquier malloc,

314
00:23:20,200 --> 00:23:22,840
y automáticamente se convierte en un char *.

315
00:23:22,840 --> 00:23:25,450
Ese reparto automático no ocurre en C + +.

316
00:23:25,450 --> 00:23:28,150
Eso no va a compilar, y de forma explícita tendría que decir

317
00:23:28,150 --> 00:23:34,510
char *, malloc, lo que sea, para lanzarlo a un char *.

318
00:23:34,510 --> 00:23:37,270
No hay muchas cosas que C y C + + no están de acuerdo en,

319
00:23:37,270 --> 00:23:40,620
pero esos son dos.

320
00:23:40,620 --> 00:23:43,120
Así que vamos a ir con esta sintaxis.

321
00:23:43,120 --> 00:23:46,150
Pero incluso si no fue con esa sintaxis,

322
00:23:46,150 --> 00:23:49,470
lo que es - podría ser malo en esto?

323
00:23:49,470 --> 00:23:52,170
[Estudiante] No es necesario eliminar la referencia verdad? Sí >>.

324
00:23:52,170 --> 00:23:55,110
Recuerde que la flecha tiene un dereference implícita,

325
00:23:55,110 --> 00:23:58,230
y así, cuando sólo estamos tratando con una estructura,

326
00:23:58,230 --> 00:24:04,300
que desea utilizar. para llegar a un campo en el interior de la estructura.

327
00:24:04,300 --> 00:24:07,200
Y la única vez que utilice la flecha es cuando queremos hacer -

328
00:24:07,200 --> 00:24:13,450
así, la flecha es equivalente a -

329
00:24:13,450 --> 00:24:17,020
eso es lo que habría significado si he usado flecha.

330
00:24:17,020 --> 00:24:24,600
Todos los medios flecha es decir, eliminar la referencia esto, ahora estoy en una estructura, y puedo conseguir el terreno.

331
00:24:24,600 --> 00:24:28,040
Cualquiera de obtener el campo o directamente eliminar la referencia y obtener el campo -

332
00:24:28,040 --> 00:24:30,380
Supongo que esto debe ser el valor.

333
00:24:30,380 --> 00:24:33,910
Pero aquí estoy tratando con sólo una estructura, no es un puntero a una estructura,

334
00:24:33,910 --> 00:24:38,780
y por lo tanto no puedo usar la flecha.

335
00:24:38,780 --> 00:24:47,510
Pero este tipo de cosas que podemos hacer para todos los nodos.

336
00:24:47,510 --> 00:24:55,790
Oh mi Dios.

337
00:24:55,790 --> 00:25:09,540
Esto es 6, 7, y 3.

338
00:25:09,540 --> 00:25:16,470
Entonces podemos establecer las sucursales en nuestro árbol, podemos tener 7 -

339
00:25:16,470 --> 00:25:21,650
Podemos tener, a su izquierda debe apuntar a 3.

340
00:25:21,650 --> 00:25:25,130
Entonces, ¿cómo hacer eso?

341
00:25:25,130 --> 00:25:29,320
[Los estudiantes, ininteligible] >> Yeah. La dirección de node3,

342
00:25:29,320 --> 00:25:34,170
y si no tenía la dirección, entonces simplemente no se compilará.

343
00:25:34,170 --> 00:25:38,190
Pero recuerde que estos son punteros a los nodos próximos.

344
00:25:38,190 --> 00:25:44,930
El derecho debe apuntar a 9,

345
00:25:44,930 --> 00:25:53,330
y 3 deben apuntar a la derecha a 6.

346
00:25:53,330 --> 00:25:58,480
Creo que esto es todo listo. Cualquier comentario o pregunta?

347
00:25:58,480 --> 00:26:02,060
[Estudiante, ininteligible] La raíz va a ser 7.

348
00:26:02,060 --> 00:26:08,210
Sólo podemos decir nodo * ptr =

349
00:26:08,210 --> 00:26:14,160
o raíz, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Para nuestros propósitos, vamos a estar tratando con insert,

351
00:26:20,730 --> 00:26:25,490
así que vamos a querer escribir una función para insertar en este árbol binario

352
00:26:25,490 --> 00:26:34,230
y el inserto está inevitablemente va a llamar a malloc para crear un nuevo nodo de este árbol.

353
00:26:34,230 --> 00:26:36,590
Así que las cosas van a causar problemas con el hecho de que algunos nodos

354
00:26:36,590 --> 00:26:38,590
son actualmente en la pila

355
00:26:38,590 --> 00:26:43,680
y otros nodos van a terminar en el montón cuando las inserte.

356
00:26:43,680 --> 00:26:47,640
Esto es perfectamente válido, pero la única razón

357
00:26:47,640 --> 00:26:49,600
somos capaces de hacer esto en la pila

358
00:26:49,600 --> 00:26:51,840
es debido a que es un ejemplo artificial que sabemos

359
00:26:51,840 --> 00:26:56,360
el árbol se supone que se construye como 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Si no tiene esto, entonces no tendría que malloc en el primer lugar.

361
00:27:02,970 --> 00:27:06,160
Como veremos un poco más adelante, debemos estar malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Ahora mismo es perfectamente razonable para poner en la pila,

363
00:27:08,570 --> 00:27:14,750
pero vamos a cambiar esto a una implementación de malloc.

364
00:27:14,750 --> 00:27:17,160
Así que cada uno de ellos ahora va a ser algo así como

365
00:27:17,160 --> 00:27:24,240
nodo * node9 = malloc (sizeof (nodo)).

366
00:27:24,240 --> 00:27:28,040
Y ahora vamos a tener que hacer el proceso de registro.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - No quería que -

368
00:27:34,010 --> 00:27:40,950
devuelve 1, y luego podemos hacer node9-> porque ahora es un puntero,

369
00:27:40,950 --> 00:27:45,300
valor = 6, node9-> left = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> derecha = NULL,

371
00:27:48,930 --> 00:27:51,410
y vamos a tener que hacer esto para cada uno de los nodos.

372
00:27:51,410 --> 00:27:57,490
Así que en vez, vamos a poner dentro de una función separada.

373
00:27:57,490 --> 00:28:00,620
Digamos que es el nodo * build_node,

374
00:28:00,620 --> 00:28:09,050
y esto es algo similar a la API que proporcionar para la codificación de Huffman.

375
00:28:09,050 --> 00:28:12,730
Le damos las funciones inicializador para un árbol

376
00:28:12,730 --> 00:28:20,520
y deconstructor "funciones" de los árboles y lo mismo para los bosques.

377
00:28:20,520 --> 00:28:22,570
>> Así que aquí vamos a tener una función de inicialización

378
00:28:22,570 --> 00:28:25,170
a sólo construir un nodo para nosotros.

379
00:28:25,170 --> 00:28:29,320
Y va a ver casi exactamente así.

380
00:28:29,320 --> 00:28:32,230
Y estoy aún va a ser perezoso y no cambiar el nombre de la variable,

381
00:28:32,230 --> 00:28:34,380
aunque node9 no tiene sentido ya.

382
00:28:34,380 --> 00:28:38,610
Oh, supongo valor node9 no debería haber sido 6.

383
00:28:38,610 --> 00:28:42,800
Ahora podemos volver node9.

384
00:28:42,800 --> 00:28:49,550
Y aquí debemos volver nulo.

385
00:28:49,550 --> 00:28:52,690
Todo el mundo está de acuerdo en que la función build-a-nodo?

386
00:28:52,690 --> 00:28:59,780
Así que ahora sólo podemos llamar así a construir un nodo con un valor determinado y punteros nulos.

387
00:28:59,780 --> 00:29:09,750
Ahora podemos llamar así, que podemos hacer nodo * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Y vamos a hacer. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
Y ahora queremos establecer los punteros mismos,

391
00:29:39,330 --> 00:29:42,470
excepto que ahora todo está ya en términos de indicadores

392
00:29:42,470 --> 00:29:48,480
así que ya no necesita la dirección de.

393
00:29:48,480 --> 00:29:56,300
Bien. Entonces, ¿qué es lo último que quiero hacer?

394
00:29:56,300 --> 00:30:03,850
Hay un error de comprobación de que no estoy haciendo.

395
00:30:03,850 --> 00:30:06,800
¿Qué significa construir retorno nodo?

396
00:30:06,800 --> 00:30:11,660
[Estudiante, ininteligible] >> Si. Si malloc no, devolverá null.

397
00:30:11,660 --> 00:30:16,460
Así que voy a perezosamente dejar de leerlo aquí en vez de hacer una condición para cada uno.

398
00:30:16,460 --> 00:30:22,320
Si (node9 == NULL, - o aún más simple,

399
00:30:22,320 --> 00:30:28,020
esto es equivalente a poco si no node9.

400
00:30:28,020 --> 00:30:38,310
Así que si no node9, o no node6, o no node3, o no node7, devolverá 1.

401
00:30:38,310 --> 00:30:42,850
Tal vez deberíamos imprimir malloc fracasado, o algo así.

402
00:30:42,850 --> 00:30:46,680
[Estudiante] Es falso igual a null también?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Cualquier valor cero es falso.

404
00:30:51,290 --> 00:30:53,920
Así nulo es un valor cero.

405
00:30:53,920 --> 00:30:56,780
Cero es un valor de cero. False es un valor de cero.

406
00:30:56,780 --> 00:31:02,130
Cualquiera - prácticamente los únicos 2 valores cero son nulos y cero,

407
00:31:02,130 --> 00:31:07,900
falso es sólo hachís definido como cero.

408
00:31:07,900 --> 00:31:13,030
Esto también se aplica si se declaran variable global.

409
00:31:13,030 --> 00:31:17,890
Si tuviéramos nodo raíz * hasta aquí,

410
00:31:17,890 --> 00:31:24,150
entonces - lo bueno de variables globales es que siempre tienen un valor inicial.

411
00:31:24,150 --> 00:31:27,500
Eso no es cierto de funciones, como el interior de aquí,

412
00:31:27,500 --> 00:31:34,870
si tenemos, como *, nodo o nodo x.

413
00:31:34,870 --> 00:31:37,380
No tenemos idea de lo que x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
o podríamos imprimirlos y que podría resultar arbitrario.

415
00:31:40,700 --> 00:31:44,980
Eso no es cierto de las variables globales.

416
00:31:44,980 --> 00:31:47,450
Así nodo raíz o un nodo x.

417
00:31:47,450 --> 00:31:53,410
Por defecto, todo lo que es global, si no explícitamente inicializada a un valor,

418
00:31:53,410 --> 00:31:57,390
tiene un valor de cero como su valor.

419
00:31:57,390 --> 00:32:01,150
Así que aquí, la raíz nodo *, no explícitamente inicializar a cualquier cosa,

420
00:32:01,150 --> 00:32:06,350
por lo que su valor por defecto será nulo, que es el valor cero de punteros.

421
00:32:06,350 --> 00:32:11,870
El valor por omisión de x va a significar que x.value es cero,

422
00:32:11,870 --> 00:32:14,260
x.left es nulo, y x.right es nulo.

423
00:32:14,260 --> 00:32:21,070
Por lo tanto, ya que es una estructura, todos los campos de la estructura será el valor cero.

424
00:32:21,070 --> 00:32:24,410
No es necesario utilizar que aquí, sin embargo.

425
00:32:24,410 --> 00:32:27,320
[Estudiante] Las estructuras son diferentes de las otras variables, y son las otras variables

426
00:32:27,320 --> 00:32:31,400
valores de basura, que son ceros?

427
00:32:31,400 --> 00:32:36,220
Bowden [] Otros valores también. Así, en x, x será cero.

428
00:32:36,220 --> 00:32:40,070
Si es en el ámbito global, tiene un valor inicial. >> Okay.

429
00:32:40,070 --> 00:32:48,950
[Bowden] O el valor inicial que dio o cero.

430
00:32:48,950 --> 00:32:53,260
Creo que se encarga de todo esto.

431
00:32:53,260 --> 00:32:58,390
>> Bien. Así que la siguiente parte de la pregunta se refiere,

432
00:32:58,390 --> 00:33:01,260
"Ahora queremos escribir una función llamada contiene

433
00:33:01,260 --> 00:33:04,930
con un prototipo de bool contiene un valor int. "

434
00:33:04,930 --> 00:33:08,340
No vamos a hacer bool contiene un valor int.

435
00:33:08,340 --> 00:33:15,110
Nuestro prototipo se va a parecer

436
00:33:15,110 --> 00:33:22,380
bool contiene (valor int.

437
00:33:22,380 --> 00:33:24,490
Y también vamos a pasar el árbol

438
00:33:24,490 --> 00:33:28,870
que se debe comprobar para ver si tiene ese valor.

439
00:33:28,870 --> 00:33:38,290
Así nodo * árbol). Bien.

440
00:33:38,290 --> 00:33:44,440
Y entonces podemos llamarlo con algo así como:

441
00:33:44,440 --> 00:33:46,090
tal vez querrá printf o algo así.

442
00:33:46,090 --> 00:33:51,040
Contiene 6, nuestra raíz.

443
00:33:51,040 --> 00:33:54,300
Esto debería devolver uno o verdadero,

444
00:33:54,300 --> 00:33:59,390
mientras que la raíz contiene 5 debe devolver false.

445
00:33:59,390 --> 00:34:02,690
Así que toma un segundo para implementar esto.

446
00:34:02,690 --> 00:34:06,780
Puede hacerlo ya sea iterativamente o recursivamente.

447
00:34:06,780 --> 00:34:09,739
Lo bueno de la forma en que hemos establecido es que las cosas

448
00:34:09,739 --> 00:34:12,300
se presta a nuestra solución recursiva mucho más fácil

449
00:34:12,300 --> 00:34:14,719
de manera global la variable hecho.

450
00:34:14,719 --> 00:34:19,750
Porque si sólo tenemos contiene un valor int, entonces no tenemos forma de manera recursiva por subárboles.

451
00:34:19,750 --> 00:34:24,130
Tendríamos que tener una función auxiliar independiente que recursivamente por los subárboles para nosotros.

452
00:34:24,130 --> 00:34:29,610
Pero ya que hemos cambiado a tomar el árbol como un argumento,

453
00:34:29,610 --> 00:34:32,760
que debería haber sido siempre, en primer lugar,

454
00:34:32,760 --> 00:34:35,710
ahora podemos recurse con mayor facilidad.

455
00:34:35,710 --> 00:34:38,960
Así iterativo o recursivo, vamos a repasar los dos,

456
00:34:38,960 --> 00:34:46,139
pero vamos a ver que los extremos recursivas siendo bastante fácil.

457
00:34:59,140 --> 00:35:02,480
Bien. ¿Alguien tiene algo que podamos trabajar?

458
00:35:02,480 --> 00:35:12,000
>> [Estudiante] Tengo una solución iterativa. >> Muy bien, iterativo.

459
00:35:12,000 --> 00:35:16,030
Bueno, esto se ve bien.

460
00:35:16,030 --> 00:35:18,920
Por lo tanto, nos quieren caminar a través de él?

461
00:35:18,920 --> 00:35:25,780
[Estudiante] Claro. Así que me puse una variable temporal para obtener el primer nodo del árbol.

462
00:35:25,780 --> 00:35:28,330
Y entonces sólo en bucle mientras que la temperatura no nula de igualdad,

463
00:35:28,330 --> 00:35:31,700
así que mientras se encontraba todavía en el árbol, supongo.

464
00:35:31,700 --> 00:35:35,710
Y si el valor es igual al valor que está apuntando a temp,

465
00:35:35,710 --> 00:35:37,640
a continuación, se devuelve dicho valor.

466
00:35:37,640 --> 00:35:40,210
De lo contrario, se comprueba si está en el lado derecho o el lado izquierdo.

467
00:35:40,210 --> 00:35:43,400
Si alguna vez tienes una situación en la que no hay más árboles,

468
00:35:43,400 --> 00:35:47,330
luego vuelve - sale del bucle y devuelve false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Bueno. Así que parece bueno.

470
00:35:52,190 --> 00:35:58,470
Cualquier persona tiene algún comentario sobre cualquier cosa?

471
00:35:58,470 --> 00:36:02,400
No tengo comentarios corrección en absoluto.

472
00:36:02,400 --> 00:36:11,020
Lo único que podemos hacer es este tipo.

473
00:36:11,020 --> 00:36:21,660
Oh, va a ir un poco alargada.

474
00:36:21,660 --> 00:36:33,460
Voy a arreglar eso. Bien.

475
00:36:33,460 --> 00:36:37,150
>> Todo el mundo debería recordar cómo funciona ternario.

476
00:36:37,150 --> 00:36:38,610
No ha sido, sin duda pruebas en el pasado

477
00:36:38,610 --> 00:36:41,170
que le dan una función con un operador ternario,

478
00:36:41,170 --> 00:36:45,750
y decir, traducir esto, hacer algo que no utiliza ternario.

479
00:36:45,750 --> 00:36:49,140
Así que este es un caso muy común de cuando se le ocurriría utilizar ternario,

480
00:36:49,140 --> 00:36:54,610
donde si alguna condición establecer una variable a algo,

481
00:36:54,610 --> 00:36:58,580
otra indicación de que la misma variable a otra cosa.

482
00:36:58,580 --> 00:37:03,390
Eso es algo que con mucha frecuencia se puede transformar en este tipo de cosas

483
00:37:03,390 --> 00:37:14,420
donde asignar a esa variable esta - o, bien, ¿es esto cierto? Luego de esto, más esto.

484
00:37:14,420 --> 00:37:18,550
[Estudiante] La primera es si es cierto, ¿verdad?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. La forma en que siempre lo leído es, la temperatura es igual al valor mayor que el valor temporal,

486
00:37:25,570 --> 00:37:30,680
entonces esto, más de esto. Está haciendo una pregunta.

487
00:37:30,680 --> 00:37:35,200
¿Es grande? Luego hacer lo primero. Demás hacer lo segundo.

488
00:37:35,200 --> 00:37:41,670
Yo casi siempre - los dos puntos, yo sólo - en mi cabeza, he leído como otra cosa.

489
00:37:41,670 --> 00:37:47,180
>> ¿Alguien tiene una solución recursiva?

490
00:37:47,180 --> 00:37:49,670
Bien. Éste vamos a - que ya podía ser grande,

491
00:37:49,670 --> 00:37:53,990
pero vamos a hacerlo aún mejor.

492
00:37:53,990 --> 00:37:58,720
Esto es más o menos la idea exactamente el mismo.

493
00:37:58,720 --> 00:38:03,060
Es sólo que, bueno, es lo que quieres explicar?

494
00:38:03,060 --> 00:38:08,340
[Estudiante] Claro. Así nos aseguramos de que el árbol no es nulo en primer lugar,

495
00:38:08,340 --> 00:38:13,380
porque si el árbol es nulo entonces va a devolver falso, porque no lo hemos encontrado.

496
00:38:13,380 --> 00:38:19,200
Y si todavía hay un árbol, entramos en - en primer lugar comprobar si el valor es el nodo actual.

497
00:38:19,200 --> 00:38:23,740
Devuelve verdadero si lo es, y si no recurse a la izquierda oa la derecha.

498
00:38:23,740 --> 00:38:25,970
¿Le parece adecuado? >> Mm-hmm. (Acuerdo)

499
00:38:25,970 --> 00:38:33,880
Así cuenta de que esto es casi - estructuralmente muy similar a la solución iterativa.

500
00:38:33,880 --> 00:38:38,200
Es sólo que en lugar de recursividad, tuvimos un bucle while.

501
00:38:38,200 --> 00:38:40,840
Y el caso base aquí donde árbol no hace nulo igual

502
00:38:40,840 --> 00:38:44,850
era la condición bajo la cual rompió el bucle while.

503
00:38:44,850 --> 00:38:50,200
Son muy similares. Pero vamos a dar un paso más allá.

504
00:38:50,200 --> 00:38:54,190
Ahora, hacemos lo mismo aquí.

505
00:38:54,190 --> 00:38:57,680
Tenga en cuenta que estamos volviendo lo mismo en ambas líneas,

506
00:38:57,680 --> 00:39:00,220
a excepción de un argumento es diferente.

507
00:39:00,220 --> 00:39:07,950
Así que vamos a hacer eso en un ternario.

508
00:39:07,950 --> 00:39:13,790
Golpeé algo opción, e hizo un símbolo. Bien.

509
00:39:13,790 --> 00:39:21,720
Así que vamos a volver que contiene.

510
00:39:21,720 --> 00:39:28,030
Esto se está convirtiendo en varias líneas, bueno, el zoom es.

511
00:39:28,030 --> 00:39:31,060
Por lo general, como una cosa de estilo, no creo que mucha gente

512
00:39:31,060 --> 00:39:38,640
poner un espacio después de la flecha, pero supongo que si eres consistente, está bien.

513
00:39:38,640 --> 00:39:44,320
Si el valor es inferior al valor del árbol, queremos recurse a la izquierda del árbol,

514
00:39:44,320 --> 00:39:53,890
más queremos recurse a la derecha del árbol.

515
00:39:53,890 --> 00:39:58,610
Así que ese fue el primer paso de hacer esta mirada más pequeño.

516
00:39:58,610 --> 00:40:02,660
Paso dos de hacer esta mirada más pequeño -

517
00:40:02,660 --> 00:40:09,150
podemos separar esta a varias líneas.

518
00:40:09,150 --> 00:40:16,500
Bien. El segundo paso de hacer que se vea más pequeña está aquí,

519
00:40:16,500 --> 00:40:25,860
así valor de retorno es igual al valor del árbol, o contiene lo que sea.

520
00:40:25,860 --> 00:40:28,340
>> Esto es una cosa importante.

521
00:40:28,340 --> 00:40:30,860
No estoy seguro de si lo dijo explícitamente en la clase,

522
00:40:30,860 --> 00:40:34,740
pero se llama la evaluación de cortocircuito.

523
00:40:34,740 --> 00:40:41,060
La idea aquí es value == valor árbol.

524
00:40:41,060 --> 00:40:49,960
Si eso es verdad, entonces esto es cierto, y queremos »o« eso con lo que esté por aquí.

525
00:40:49,960 --> 00:40:52,520
Así, sin siquiera pensar en lo que está por aquí,

526
00:40:52,520 --> 00:40:55,070
¿cuál es la expresión entera va a regresar?

527
00:40:55,070 --> 00:40:59,430
[Estudiante] Cierto? >> Sí, porque cierto de nada,

528
00:40:59,430 --> 00:41:04,990
operación lógica OR - operación lógica OR o verdadero con todo es necesariamente cierto.

529
00:41:04,990 --> 00:41:08,150
Así que tan pronto como vemos valor de retorno = Valor de árbol,

530
00:41:08,150 --> 00:41:10,140
sólo vamos a volver realidad.

531
00:41:10,140 --> 00:41:15,710
Ni siquiera va a recurse contiene además de la línea.

532
00:41:15,710 --> 00:41:20,980
Podemos dar un paso más allá.

533
00:41:20,980 --> 00:41:29,490
Árbol retorno no nulo igual y todo eso.

534
00:41:29,490 --> 00:41:32,650
Lo hizo en función de una línea.

535
00:41:32,650 --> 00:41:36,790
Este es también un ejemplo de la evaluación de cortocircuito.

536
00:41:36,790 --> 00:41:40,680
Pero ahora es la misma idea -

537
00:41:40,680 --> 00:41:47,320
en lugar de - por lo que si el árbol no nulo igual - o, bien,

538
00:41:47,320 --> 00:41:49,580
si árbol hace nula de igualdad, que es el caso malo,

539
00:41:49,580 --> 00:41:54,790
si el árbol es igual a NULL, la primera condición será falsa.

540
00:41:54,790 --> 00:42:00,550
Así falso AND con cualquier cosa va a ser qué?

541
00:42:00,550 --> 00:42:04,640
[Estudiante] Falso. Sí >>. Esta es la otra mitad de la evaluación de cortocircuito,

542
00:42:04,640 --> 00:42:10,710
donde si el árbol es nulo no es igual, entonces no vamos a ir aún más -

543
00:42:10,710 --> 00:42:14,930
o si el árbol hace nulo iguales, entonces no vamos a hacer value == valor árbol.

544
00:42:14,930 --> 00:42:17,010
Sólo vamos a regresar de inmediato falsa.

545
00:42:17,010 --> 00:42:20,970
Lo cual es importante, ya que si no lo hiciera cortocircuito evaluate,

546
00:42:20,970 --> 00:42:25,860
entonces si el árbol hace nulo igual, esta segunda condición se va a culpa seg,

547
00:42:25,860 --> 00:42:32,510
porque árbol-> valor se desreferencia nula.

548
00:42:32,510 --> 00:42:40,490
Así que eso es todo. ¿Puede hacer esto - cambiar una vez más.

549
00:42:40,490 --> 00:42:44,840
Esto es una cosa muy común también, no hacer esta línea con esto,

550
00:42:44,840 --> 00:42:49,000
pero es una cosa común en condiciones, quizás no aquí,

551
00:42:49,000 --> 00:42:59,380
pero si (árbol! = NULL, y el árbol-> valor value ==), hacer lo que sea.

552
00:42:59,380 --> 00:43:01,560
Esta es una condición muy común, donde en lugar de tener

553
00:43:01,560 --> 00:43:06,770
a romper esto en dos ifs, donde quiera, es la nula árbol?

554
00:43:06,770 --> 00:43:11,780
Bueno, no es nulo, por lo que ahora es el valor equivalente al valor del árbol? Haga esto.

555
00:43:11,780 --> 00:43:17,300
En su lugar, esta condición, esto nunca falla seg

556
00:43:17,300 --> 00:43:21,220
porque va a salir si esto pasa a ser nulo.

557
00:43:21,220 --> 00:43:24,000
Bueno, supongo que si el árbol es un puntero nulo completamente, todavía puede seg culpa,

558
00:43:24,000 --> 00:43:26,620
pero no puede seg fallo si el árbol es nulo.

559
00:43:26,620 --> 00:43:32,900
Si fuera nulo, iba a estallar antes de que usted desreferencia el puntero en el primer lugar.

560
00:43:32,900 --> 00:43:35,000
[Estudiante] ¿Este evaluación perezosa llamada?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] La evaluación diferida es una cosa aparte.

562
00:43:40,770 --> 00:43:49,880
La evaluación diferida es más como usted pide un valor,

563
00:43:49,880 --> 00:43:54,270
pedirle que calcule un valor, tipo de, pero usted no lo necesita de inmediato.

564
00:43:54,270 --> 00:43:59,040
Así que hasta que realmente lo necesitan, no se evalúa.

565
00:43:59,040 --> 00:44:03,920
Esto no es exactamente lo mismo, pero, en el conjunto de procesadores Huffman

566
00:44:03,920 --> 00:44:06,520
que dice que "perezosa", escriben.

567
00:44:06,520 --> 00:44:08,670
La razón por la que hacemos esto es porque en realidad estamos amortiguación de la escritura -

568
00:44:08,670 --> 00:44:11,820
no quiero escribir bits individuales a la vez,

569
00:44:11,820 --> 00:44:15,450
o bytes individuales a la vez, en vez quiere conseguir un pedazo de bytes.

570
00:44:15,450 --> 00:44:19,270
Luego, una vez que tenemos un fragmento de bytes, entonces vamos a escribirlo.

571
00:44:19,270 --> 00:44:22,640
A pesar de que se pida a escribir - y fwrite y fread hacer el mismo tipo de cosas.

572
00:44:22,640 --> 00:44:26,260
Ellos amortiguar su lectura y escritura.

573
00:44:26,260 --> 00:44:31,610
A pesar de que se pida a escribir de inmediato, probablemente no lo hará.

574
00:44:31,610 --> 00:44:34,540
Y no se puede estar seguro de que las cosas van a ser escritos

575
00:44:34,540 --> 00:44:37,540
hasta que se llama hfclose o lo que sea,

576
00:44:37,540 --> 00:44:39,620
que luego se dice, está bien, voy a cerrar mi archivo,

577
00:44:39,620 --> 00:44:43,450
eso significa que será mejor que escribir todo lo que no he escrito todavía.

578
00:44:43,450 --> 00:44:45,770
No tiene que escribir todo lo que fuera

579
00:44:45,770 --> 00:44:49,010
hasta que se cierre el archivo y haga lo necesario.

580
00:44:49,010 --> 00:44:56,220
Así que eso es justo lo vago - que espera hasta que tiene que suceder.

581
00:44:56,220 --> 00:44:59,990
Esto - tomar 51 y podrás entrar en ella con más detalle,

582
00:44:59,990 --> 00:45:05,470
porque OCaml y todo lo que en el 51, todo es repetición.

583
00:45:05,470 --> 00:45:08,890
No existen soluciones iterativas, básicamente.

584
00:45:08,890 --> 00:45:11,550
Todo es repetición, y la evaluación perezosa

585
00:45:11,550 --> 00:45:14,790
va a ser importante para un montón de circunstancias

586
00:45:14,790 --> 00:45:19,920
donde, si no perezosamente evaluar, eso significaría -

587
00:45:19,920 --> 00:45:24,760
El ejemplo es corrientes, que son infinitamente largo.

588
00:45:24,760 --> 00:45:30,990
En teoría, se puede pensar en los números naturales como una corriente de 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Así que las cosas están bien evaluados perezosamente.

590
00:45:33,090 --> 00:45:37,210
Si digo que quiero que el décimo número, entonces puedo evaluar hasta el número diez.

591
00:45:37,210 --> 00:45:40,300
Si desea que el número cien, entonces puedo evaluar hasta el número cien.

592
00:45:40,300 --> 00:45:46,290
Sin la evaluación perezosa, entonces va a tratar de evaluar todos los números de inmediato.

593
00:45:46,290 --> 00:45:50,000
Se está evaluando un número infinito de números, y eso no es posible.

594
00:45:50,000 --> 00:45:52,080
Así que hay un montón de circunstancias en las que la evaluación perezosa

595
00:45:52,080 --> 00:45:57,840
es esencial para conseguir que las cosas funcionen.

596
00:45:57,840 --> 00:46:05,260
>> Ahora queremos escribir inserción insert donde va a ser

597
00:46:05,260 --> 00:46:08,430
de manera similar cambiando en su definición.

598
00:46:08,430 --> 00:46:10,470
Así que ahora mismo está inserto bool (int value).

599
00:46:10,470 --> 00:46:23,850
Vamos a cambiar eso para insertar bool (int value, nodo de árbol *).

600
00:46:23,850 --> 00:46:29,120
Estamos realmente va a cambiar de nuevo un poco, ya veremos por qué.

601
00:46:29,120 --> 00:46:32,210
Y vamos a pasar build_node, sólo por el gusto de hacerlo,

602
00:46:32,210 --> 00:46:36,730
por encima de insertar por lo que no tiene que escribir un prototipo de función.

603
00:46:36,730 --> 00:46:42,450
Lo cual es un indicio de que se va a utilizar en build_node inserción.

604
00:46:42,450 --> 00:46:49,590
Bien. Tome un minuto para eso.

605
00:46:49,590 --> 00:46:52,130
Creo que me salvó la revisión si quieres tirar de eso,

606
00:46:52,130 --> 00:47:00,240
o, al menos, lo hice ahora.

607
00:47:00,240 --> 00:47:04,190
Yo quería un ligero corte a pensar en la lógica de la inserción,

608
00:47:04,190 --> 00:47:08,750
si usted no puede pensar en él.

609
00:47:08,750 --> 00:47:12,860
Básicamente, sólo alguna vez se inserta en las hojas.

610
00:47:12,860 --> 00:47:18,640
Al igual que, si inserto 1, entonces estoy inevitablemente va a insertar 1 -

611
00:47:18,640 --> 00:47:21,820
Voy a cambiar a negro - Estaré insertar una por aquí.

612
00:47:21,820 --> 00:47:28,070
O si puedo insertar 4, quiero ser la inserción de 4 por aquí.

613
00:47:28,070 --> 00:47:32,180
Así que no importa lo que hagas, vas a insertar en una hoja.

614
00:47:32,180 --> 00:47:36,130
Todo lo que tienes que hacer es recorrer el árbol hasta llegar al nodo

615
00:47:36,130 --> 00:47:40,890
que debe ser el padre del nodo, el padre del nuevo nodo,

616
00:47:40,890 --> 00:47:44,560
y luego cambiar el puntero de izquierda o derecha, dependiendo de si

617
00:47:44,560 --> 00:47:47,060
es mayor o menor que el nodo actual.

618
00:47:47,060 --> 00:47:51,180
Cambiar ese puntero para apuntar a su nuevo nodo.

619
00:47:51,180 --> 00:48:05,490
Así iterar hacia abajo del árbol, hacen que el punto de la hoja al nuevo nodo.

620
00:48:05,490 --> 00:48:09,810
También piense por qué prohíbe el tipo de situación antes,

621
00:48:09,810 --> 00:48:17,990
donde construyó el árbol binario donde estaba correcta

622
00:48:17,990 --> 00:48:19,920
si sólo miró a un solo nodo,

623
00:48:19,920 --> 00:48:24,830
pero el 9 estaba a la izquierda de 7 si reiterado por todo el camino.

624
00:48:24,830 --> 00:48:29,770
Así que es imposible en esta situación, ya que -

625
00:48:29,770 --> 00:48:32,530
pensar en la inserción de 9 o algo, en el primer nodo,

626
00:48:32,530 --> 00:48:35,350
Voy a ver 7 y me voy a ir a la derecha.

627
00:48:35,350 --> 00:48:38,490
Así que no importa lo que haga, si estoy yendo a la inserción de una hoja,

628
00:48:38,490 --> 00:48:40,790
y a una hoja utilizando el algoritmo apropiado,

629
00:48:40,790 --> 00:48:43,130
que va a ser imposible para mí para insertar 9 a la izquierda, de 7 de

630
00:48:43,130 --> 00:48:48,250
porque tan pronto como me golpeó 7 Yo voy a ir a la derecha.

631
00:48:59,740 --> 00:49:02,070
¿Alguien tiene algo para empezar?

632
00:49:02,070 --> 00:49:05,480
[Estudiante] que hago. >> Claro.

633
00:49:05,480 --> 00:49:09,200
[Estudiante, ininteligible]

634
00:49:09,200 --> 00:49:14,390
[Otro estudiante, ininteligible]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Se aprecia. Bien. ¿Quieres explicarme?

636
00:49:18,330 --> 00:49:20,690
>> [Estudiante] Ya que sabemos que estábamos insertando

637
00:49:20,690 --> 00:49:24,060
nuevos nodos en el extremo del árbol,

638
00:49:24,060 --> 00:49:28,070
Me envían a través del árbol de forma iterativa

639
00:49:28,070 --> 00:49:31,360
hasta que llegué a un nodo que apuntaba a null.

640
00:49:31,360 --> 00:49:34,220
Y entonces me decidí a poner ya sea en el lado derecho o el lado izquierdo

641
00:49:34,220 --> 00:49:37,420
utilizando esta variable correcto, sino que me dijo dónde ponerlo.

642
00:49:37,420 --> 00:49:41,850
Y entonces, en esencia, que acabo de hacer que el pasado -

643
00:49:41,850 --> 00:49:47,520
ese punto temp nodo al nuevo nodo que se estaba creando,

644
00:49:47,520 --> 00:49:50,770
ya sea en el lado izquierdo o en el lado derecho, dependiendo de lo que el valor de la derecha era.

645
00:49:50,770 --> 00:49:56,530
Por último, establece el valor nuevo nodo con el valor de su prueba.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Está bien, así que no veo un problema aquí.

647
00:49:59,550 --> 00:50:02,050
Esto es como el 95% del camino.

648
00:50:02,050 --> 00:50:07,550
El único problema que veo, bueno, ¿alguien más ve un problema?

649
00:50:07,550 --> 00:50:18,400
¿Cuál es la circunstancia en las que romper el lazo?

650
00:50:18,400 --> 00:50:22,100
[Estudiante] Si la temperatura es nulo? Sí >>. Entonces, ¿cómo salir del bucle es si la temperatura es nulo.

651
00:50:22,100 --> 00:50:30,220
Pero, ¿qué hago aquí?

652
00:50:30,220 --> 00:50:35,410
Yo dereference temperatura, que es inevitablemente nulo.

653
00:50:35,410 --> 00:50:39,840
Así que lo que usted tiene que hacer no es sólo un seguimiento hasta que la temperatura es nulo,

654
00:50:39,840 --> 00:50:45,590
usted quiere estar al día de los padres en todo momento.

655
00:50:45,590 --> 00:50:52,190
También queremos que los padres nodo *, creo que podemos mantener en nulo al principio.

656
00:50:52,190 --> 00:50:55,480
Esto va a tener un comportamiento extraño en la raíz del árbol,

657
00:50:55,480 --> 00:50:59,210
pero ya llegaremos a eso.

658
00:50:59,210 --> 00:51:03,950
Si el valor es mayor de lo que sea, entonces temp = temp derecha.

659
00:51:03,950 --> 00:51:07,910
Pero antes de hacer eso, padre temp =.

660
00:51:07,910 --> 00:51:14,500
¿O los padres siempre van a temp iguales? ¿Es ese el caso?

661
00:51:14,500 --> 00:51:19,560
Si la temperatura no es nulo, entonces yo voy a bajar, no importa qué,

662
00:51:19,560 --> 00:51:24,030
a un nodo para el que la temperatura es el padre.

663
00:51:24,030 --> 00:51:27,500
Así que los padres va a ser temporal, y luego me muevo por temp.

664
00:51:27,500 --> 00:51:32,410
Ahora la temperatura es nulo, pero señala a los padres de los padres de lo que es nulo.

665
00:51:32,410 --> 00:51:39,110
Así que aquí, no quiero establecer derecha es igual a 1.

666
00:51:39,110 --> 00:51:41,300
Así que me mudé a la derecha, por lo que si la derecha = 1,

667
00:51:41,300 --> 00:51:45,130
y supongo que también quieren hacer -

668
00:51:45,130 --> 00:51:48,530
si se mueve hacia la izquierda, que desea establecer el derecho igual a 0.

669
00:51:48,530 --> 00:51:55,950
O bien, si alguna vez se mueven hacia la derecha.

670
00:51:55,950 --> 00:51:58,590
Así derecha = 0. Si la derecha = 1,

671
00:51:58,590 --> 00:52:04,260
ahora queremos que el padre nodo_nuevo puntero derecho,

672
00:52:04,260 --> 00:52:08,520
otra cosa que quiere hacer el padre nodo_nuevo puntero izquierdo.

673
00:52:08,520 --> 00:52:16,850
Las preguntas sobre eso?

674
00:52:16,850 --> 00:52:24,880
Bien. Así que esta es la forma en que - bueno, en realidad, en lugar de hacer esto,

675
00:52:24,880 --> 00:52:29,630
Casi esperaba que usted utilice build_node.

676
00:52:29,630 --> 00:52:40,450
Y luego, si es igual nodo_nuevo nulo, devuelve falso.

677
00:52:40,450 --> 00:52:44,170
Eso es todo. Ahora bien, esto es lo que esperábamos que hiciera.

678
00:52:44,170 --> 00:52:47,690
>> Esto es lo que las soluciones de personal hacer.

679
00:52:47,690 --> 00:52:52,360
No estoy de acuerdo con esto como la manera "correcta" de hacer las cosas

680
00:52:52,360 --> 00:52:57,820
pero esto está perfectamente bien y va a funcionar.

681
00:52:57,820 --> 00:53:02,840
Una cosa que es un derecho poco raro ahora es

682
00:53:02,840 --> 00:53:08,310
si el árbol comienza como nulo, se pasa en un árbol nulo.

683
00:53:08,310 --> 00:53:12,650
Supongo que depende de cómo se defina el comportamiento del pasajero en un árbol nulo.

684
00:53:12,650 --> 00:53:15,490
Me gustaría pensar que si se pasa un árbol nulo,

685
00:53:15,490 --> 00:53:17,520
a continuación, insertar el valor NULL en un árbol

686
00:53:17,520 --> 00:53:23,030
sólo debe devolver un árbol en el que el único valor es que solo nodo.

687
00:53:23,030 --> 00:53:25,830
¿Las personas están de acuerdo con eso? Usted puede, si quiere,

688
00:53:25,830 --> 00:53:28,050
si se pasa un árbol nulo

689
00:53:28,050 --> 00:53:31,320
y desea insertar un valor en él, devuelve falso.

690
00:53:31,320 --> 00:53:33,830
Depende de usted para definir eso.

691
00:53:33,830 --> 00:53:38,320
Para ello lo primero que me dijo y luego -

692
00:53:38,320 --> 00:53:40,720
así, vas a tener problemas para hacer eso, porque

693
00:53:40,720 --> 00:53:44,090
sería más fácil si tuviéramos un puntero global a la cosa,

694
00:53:44,090 --> 00:53:48,570
pero no, por lo que si el árbol es nulo, no hay nada que podamos hacer al respecto.

695
00:53:48,570 --> 00:53:50,960
Sólo puede devolver false.

696
00:53:50,960 --> 00:53:52,840
Así que me voy a cambiar de inserción.

697
00:53:52,840 --> 00:53:56,540
Nos técnicamente podría cambiar esto de aquí,

698
00:53:56,540 --> 00:53:58,400
cómo se itera sobre las cosas,

699
00:53:58,400 --> 00:54:04,530
pero yo voy a cambiar de inserción para tomar un nodo de árbol. **

700
00:54:04,530 --> 00:54:07,510
Punteros dobles.

701
00:54:07,510 --> 00:54:09,710
¿Qué quiere decir esto?

702
00:54:09,710 --> 00:54:12,330
En lugar de tratar con punteros a nodos,

703
00:54:12,330 --> 00:54:16,690
lo que voy a estar manipulando es este puntero.

704
00:54:16,690 --> 00:54:18,790
Voy a estar manipulando este puntero.

705
00:54:18,790 --> 00:54:21,770
Voy a estar manipulando directamente los punteros.

706
00:54:21,770 --> 00:54:25,760
Esto tiene sentido ya que, pensar hacia abajo -

707
00:54:25,760 --> 00:54:33,340
Bueno, ahora esto apunta a null.

708
00:54:33,340 --> 00:54:38,130
Lo que quiero hacer es manipular este puntero para apuntar a no nulo.

709
00:54:38,130 --> 00:54:40,970
Quiero que apunte a mi nuevo nodo.

710
00:54:40,970 --> 00:54:44,870
Si tan sólo realizar un seguimiento de los punteros a mis consejos,

711
00:54:44,870 --> 00:54:47,840
entonces no es necesario hacer un seguimiento de un puntero padres.

712
00:54:47,840 --> 00:54:52,640
Acabo de hacer un seguimiento para ver si el puntero apunta a null,

713
00:54:52,640 --> 00:54:54,580
y si el puntero apunta a null,

714
00:54:54,580 --> 00:54:57,370
cambiar para que apunte al nodo que quiero.

715
00:54:57,370 --> 00:55:00,070
Y puedo cambiar ya que tengo un puntero al puntero.

716
00:55:00,070 --> 00:55:02,040
Vamos a ver esto ahora mismo.

717
00:55:02,040 --> 00:55:05,470
En realidad se puede hacer de forma recursiva con bastante facilidad.

718
00:55:05,470 --> 00:55:08,080
¿Queremos hacerlo?

719
00:55:08,080 --> 00:55:10,980
Sí, lo hacemos.

720
00:55:10,980 --> 00:55:16,790
>> Vamos a ver de forma recursiva.

721
00:55:16,790 --> 00:55:24,070
En primer lugar, ¿cuál es nuestro caso base va a ser?

722
00:55:24,070 --> 00:55:29,140
Casi siempre nuestro caso base, pero en realidad, esto es un poco complicado.

723
00:55:29,140 --> 00:55:34,370
Lo primero es lo primero, si (árbol == NULL)

724
00:55:34,370 --> 00:55:37,550
Supongo que sólo va a devolver false.

725
00:55:37,550 --> 00:55:40,460
Esto es diferente de su nula árbol bienestar.

726
00:55:40,460 --> 00:55:44,510
Este es el puntero al puntero raíz siendo nula

727
00:55:44,510 --> 00:55:48,360
lo que significa que el puntero de su raíz no existe.

728
00:55:48,360 --> 00:55:52,390
Así que aquí, si lo hago

729
00:55:52,390 --> 00:55:55,760
* nodo - vamos a volver a usar esto.

730
00:55:55,760 --> 00:55:58,960
Nodo * root = NULL,

731
00:55:58,960 --> 00:56:00,730
y luego me voy a llamar a insertar haciendo algo como:

732
00:56:00,730 --> 00:56:04,540
insertar y 4 en la raíz.

733
00:56:04,540 --> 00:56:06,560
Así y raíz, si la raíz es un nodo *

734
00:56:06,560 --> 00:56:11,170
y entonces la raíz va a ser un ** nodo.

735
00:56:11,170 --> 00:56:15,120
Esto es válido. En este caso, el árbol, hasta aquí,

736
00:56:15,120 --> 00:56:20,120
árbol no es nulo - o inserción.

737
00:56:20,120 --> 00:56:24,630
Aquí. Tree no es nulo; árbol * es nulo, lo cual está bien

738
00:56:24,630 --> 00:56:26,680
porque si el árbol * es nulo, entonces puedo manipular

739
00:56:26,680 --> 00:56:29,210
apuntar ahora a lo que yo quiero que apuntar.

740
00:56:29,210 --> 00:56:34,750
Pero si el árbol es nulo, eso significa que sólo vine aquí y me dijo nulo.

741
00:56:34,750 --> 00:56:42,710
Eso no tiene sentido. No puedo hacer nada con eso.

742
00:56:42,710 --> 00:56:45,540
Si el árbol es nulo, devuelve falso.

743
00:56:45,540 --> 00:56:48,220
Así que, básicamente, lo que ya ha dicho nuestro caso base real.

744
00:56:48,220 --> 00:56:50,580
Y lo que es que va a ser?

745
00:56:50,580 --> 00:56:55,030
[Estudiante, ininteligible]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Sí. Así que si (* arbol == NULL).

747
00:57:00,000 --> 00:57:04,520
Esto se relaciona con el caso aquí

748
00:57:04,520 --> 00:57:09,640
donde si mi puntero rojo es el puntero que estoy enfocado,

749
00:57:09,640 --> 00:57:12,960
así que estoy centrado en este indicador, ahora estoy centrado en este indicador.

750
00:57:12,960 --> 00:57:15,150
Ahora estoy centrado en este indicador.

751
00:57:15,150 --> 00:57:18,160
Así que si mi puntero rojo, que es mi ** nodos,

752
00:57:18,160 --> 00:57:22,880
es cada vez - si *, mi puntero rojo, es siempre nulo,

753
00:57:22,880 --> 00:57:28,470
eso significa que estoy en el caso de que me voy a centrar en un puntero que apunta -

754
00:57:28,470 --> 00:57:32,530
este es un puntero que pertenece a una hoja.

755
00:57:32,530 --> 00:57:41,090
Quiero cambiar este puntero para apuntar a mi nuevo nodo.

756
00:57:41,090 --> 00:57:45,230
Vuelve por aquí.

757
00:57:45,230 --> 00:57:56,490
Mi nodo_nuevo sólo será nodo * n = build_node (valor)

758
00:57:56,490 --> 00:58:07,300
entonces n, si n = NULL, devuelve falso.

759
00:58:07,300 --> 00:58:12,600
Otras ventas que queremos cambiar lo que el puntero apunta actualmente

760
00:58:12,600 --> 00:58:17,830
apuntar ahora a nuestro nodo de nueva construcción.

761
00:58:17,830 --> 00:58:20,280
De hecho, podemos hacer eso aquí.

762
00:58:20,280 --> 00:58:30,660
En lugar de decir n, decimos árbol * = si el árbol *.

763
00:58:30,660 --> 00:58:35,450
Todo el mundo entiende eso? Eso negociando con punteros a punteros,

764
00:58:35,450 --> 00:58:40,750
podemos cambiar punteros nulos para apuntar a las cosas que queremos que apuntar.

765
00:58:40,750 --> 00:58:42,820
Ese es nuestro caso base.

766
00:58:42,820 --> 00:58:45,740
>> Ahora nuestro recurrencia, o nuestra recursividad,

767
00:58:45,740 --> 00:58:51,430
va a ser muy similar a todos los otros recurrencias que hemos estado haciendo.

768
00:58:51,430 --> 00:58:55,830
Vamos a querer insertar un valor,

769
00:58:55,830 --> 00:58:59,040
y ahora yo voy a usar de nuevo ternario, pero lo que es nuestra condición va a ser?

770
00:58:59,040 --> 00:59:05,180
¿Qué es lo que estamos buscando para decidir si queremos ir a la izquierda oa la derecha?

771
00:59:05,180 --> 00:59:07,760
Vamos a hacerlo en pasos separados.

772
00:59:07,760 --> 00:59:18,850
Si (valor <) qué?

773
00:59:18,850 --> 00:59:23,200
[Estudiante] El valor del árbol?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Así que recuerde que soy en la actualidad -

775
00:59:27,490 --> 00:59:31,260
[Los estudiantes], ininteligibles

776
00:59:31,260 --> 00:59:34,140
[Bowden] Sí, tan bien aquí, vamos a decir que esta flecha verde

777
00:59:34,140 --> 00:59:39,050
es un ejemplo de lo que actualmente es árbol, es un puntero al puntero.

778
00:59:39,050 --> 00:59:46,610
Así que eso significa que soy un puntero a un puntero a 3.

779
00:59:46,610 --> 00:59:48,800
El dereference dos veces sonaba bien.

780
00:59:48,800 --> 00:59:51,010
¿Qué - ¿cómo puedo hacer eso?

781
00:59:51,010 --> 00:59:53,210
[Estudiante] eliminar la referencia una vez, y luego hacer flecha de esa manera?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Entonces (árbol *) es la eliminación de referencias una vez, -> valor

783
00:59:58,420 --> 01:00:05,960
me va a dar el valor del nodo que estoy señalando indirectamente.

784
01:00:05,960 --> 01:00:11,980
Así que también se puede escribir ** tree.value si lo prefiere eso.

785
01:00:11,980 --> 01:00:18,490
Cualquiera de las obras.

786
01:00:18,490 --> 01:00:26,190
Si ese es el caso, entonces quiero llamar a insertar con valor.

787
01:00:26,190 --> 01:00:32,590
Y lo que es mi nodo actualizado ** va a ser?

788
01:00:32,590 --> 01:00:39,440
Yo quiero ir a la izquierda, por lo que arbol.izquierdo ** va a ser mi izquierda.

789
01:00:39,440 --> 01:00:41,900
Y quiero que el puntero a esa cosa

790
01:00:41,900 --> 01:00:44,930
de modo que si la izquierda termina siendo el puntero nulo,

791
01:00:44,930 --> 01:00:48,360
Puedo modificar para apuntar a mi nuevo nodo.

792
01:00:48,360 --> 01:00:51,460
>> Y el otro caso puede ser muy similar.

793
01:00:51,460 --> 01:00:55,600
Vamos a hacer que mi realidad ternario en estos momentos.

794
01:00:55,600 --> 01:01:04,480
Inserte valor si el valor <(árbol **). Valor.

795
01:01:04,480 --> 01:01:11,040
Entonces queremos actualizar nuestros ** a la izquierda,

796
01:01:11,040 --> 01:01:17,030
más queremos actualizar nuestros ** a la derecha.

797
01:01:17,030 --> 01:01:22,540
[Estudiante] ¿Eso obtener el puntero al puntero?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Recuerde que - ** arbol.derecho es una estrella nodo.

799
01:01:30,940 --> 01:01:35,040
[Estudiante, ininteligible] >> Si.

800
01:01:35,040 --> 01:01:41,140
** Arbol.derecho es como este puntero o algo así.

801
01:01:41,140 --> 01:01:45,140
Así, tomando un puntero a eso, que me da lo que quiero

802
01:01:45,140 --> 01:01:50,090
del puntero a ese tipo.

803
01:01:50,090 --> 01:01:54,260
[Estudiante] Podríamos ir otra vez por qué estamos utilizando los dos punteros?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Por lo tanto - no, usted puede, y la solución que antes

805
01:01:58,220 --> 01:02:04,540
Era una manera de hacerlo sin tener que hacer dos punteros.

806
01:02:04,540 --> 01:02:08,740
Tiene que ser capaz de entender el uso de dos punteros,

807
01:02:08,740 --> 01:02:11,660
y esta es una solución más limpia.

808
01:02:11,660 --> 01:02:16,090
Además, observe que, ¿qué pasa si mi árbol -

809
01:02:16,090 --> 01:02:24,480
¿qué pasa si mi raíz era nulo? ¿Qué pasa si no hago este caso aquí?

810
01:02:24,480 --> 01:02:30,540
Así nodo * root = NULL, insertar y 4 en la raíz.

811
01:02:30,540 --> 01:02:35,110
¿Qué es la raíz va a ser después de esto?

812
01:02:35,110 --> 01:02:37,470
[Estudiante, ininteligible] >> Si.

813
01:02:37,470 --> 01:02:41,710
Valor de la raíz va a ser 4.

814
01:02:41,710 --> 01:02:45,510
Raíz izquierda va a ser nulo, derecho fundamental va a ser nulo.

815
01:02:45,510 --> 01:02:49,490
En el caso en el que no pasó raíz de dirección,

816
01:02:49,490 --> 01:02:52,490
no podíamos modificar raíz.

817
01:02:52,490 --> 01:02:56,020
En el caso de que el árbol - donde la raíz era nulo,

818
01:02:56,020 --> 01:02:58,410
nos tuvimos que devolver false. No hay nada que pudiéramos hacer.

819
01:02:58,410 --> 01:03:01,520
No se puede insertar un nodo en un árbol vacío.

820
01:03:01,520 --> 01:03:06,810
Pero ahora sí, acabamos de hacer un árbol vacío en un árbol de un nodo.

821
01:03:06,810 --> 01:03:13,400
Lo cual es generalmente la manera esperada que se supone que debe funcionar.

822
01:03:13,400 --> 01:03:21,610
>> Además, éste es significativamente más corto que

823
01:03:21,610 --> 01:03:26,240
también hacer el seguimiento de los padres, y por lo que iterar hacia abajo todo el camino.

824
01:03:26,240 --> 01:03:30,140
Ahora tengo a mi padre, y yo sólo tengo mi puntero derecho del padre a lo que sea.

825
01:03:30,140 --> 01:03:35,640
En cambio, si hacemos esto iterativa, que sería la misma idea con un bucle while.

826
01:03:35,640 --> 01:03:38,100
Pero en lugar de tener que lidiar con mi padre puntero,

827
01:03:38,100 --> 01:03:40,600
mi lugar actual del puntero sería lo

828
01:03:40,600 --> 01:03:43,790
que estoy modificando directamente para apuntar a mi nuevo nodo.

829
01:03:43,790 --> 01:03:46,090
Yo no tengo que lidiar con el hecho de que apunta hacia la izquierda.

830
01:03:46,090 --> 01:03:48,810
Yo no tengo que lidiar con el hecho de que apunta hacia la derecha.

831
01:03:48,810 --> 01:04:00,860
Es sólo lo que este indicador es que me voy a fijar para que apunte a mi nuevo nodo.

832
01:04:00,860 --> 01:04:05,740
Todo el mundo entiende cómo funciona?

833
01:04:05,740 --> 01:04:09,460
Si no es así ¿por qué queremos hacerlo de esta manera,

834
01:04:09,460 --> 01:04:14,920
pero al menos que esto funciona como una solución?

835
01:04:14,920 --> 01:04:17,110
[Estudiante] ¿Dónde return true?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Eso es probablemente justo aquí.

837
01:04:21,550 --> 01:04:26,690
Si se inserta correctamente, devuelve true.

838
01:04:26,690 --> 01:04:32,010
Si no, aquí vamos a querer volver a lo que sea retornos de inserción.

839
01:04:32,010 --> 01:04:35,950
>> ¿Y qué tiene de especial esta función recursiva?

840
01:04:35,950 --> 01:04:43,010
Es la cola recursiva, por lo que mientras se compila con un poco de optimización,

841
01:04:43,010 --> 01:04:48,060
reconocerá y que nunca se tiene un desbordamiento de pila de esto,

842
01:04:48,060 --> 01:04:53,230
incluso si nuestro árbol tiene una altura de 10.000 millones o 10.

843
01:04:53,230 --> 01:04:55,630
[Estudiante, ininteligible]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Creo que lo hace a Dash - o qué nivel de optimización

845
01:05:00,310 --> 01:05:03,820
se requiere para una recursión de cola para ser reconocido.

846
01:05:03,820 --> 01:05:09,350
Creo que lo reconoce - GCC y Clang

847
01:05:09,350 --> 01:05:12,610
También tienen diferentes significados para sus niveles de optimización.

848
01:05:12,610 --> 01:05:17,870
Quiero decir que es DashO 2, para asegurarse de que se reconozca la recursión de cola.

849
01:05:17,870 --> 01:05:27,880
Pero - se puede construir como un ejemplo Fibonocci o algo así.

850
01:05:27,880 --> 01:05:30,030
No es fácil de probar con esto, porque es difícil construir

851
01:05:30,030 --> 01:05:32,600
un árbol binario que es tan grande.

852
01:05:32,600 --> 01:05:37,140
Pero sí, creo que es DashO 2, que

853
01:05:37,140 --> 01:05:40,580
si se compila con DashO 2, se buscará la recursión de cola

854
01:05:40,580 --> 01:05:54,030
y optimizar eso.

855
01:05:54,030 --> 01:05:58,190
Volvamos a - insertar, literalmente, la última cosa que necesita.

856
01:05:58,190 --> 01:06:04,900
Volvamos a la inserción de aquí

857
01:06:04,900 --> 01:06:07,840
donde vamos a hacer la misma idea.

858
01:06:07,840 --> 01:06:14,340
Todavía tendremos el defecto de no ser capaz de manejar todo

859
01:06:14,340 --> 01:06:17,940
cuando la misma raíz es nulo, o el pasado entrada es nulo,

860
01:06:17,940 --> 01:06:20,060
pero en lugar de tratar con un puntero padre,

861
01:06:20,060 --> 01:06:27,430
vamos a aplicar la misma lógica de los punteros a punteros de mantenimiento.

862
01:06:27,430 --> 01:06:35,580
Si aquí seguimos nuestro nodo ** cur,

863
01:06:35,580 --> 01:06:37,860
y no es necesario hacer un seguimiento de la derecha más,

864
01:06:37,860 --> 01:06:47,190
pero nodo ** act = & árbol.

865
01:06:47,190 --> 01:06:54,800
Y ahora nuestro bucle while va a ser mientras act * no nula de igualdad.

866
01:06:54,800 --> 01:07:00,270
No es necesario hacer un seguimiento de los padres más.

867
01:07:00,270 --> 01:07:04,180
No es necesario hacer un seguimiento de izquierda y derecha.

868
01:07:04,180 --> 01:07:10,190
Y lo voy a llamar a la temperatura, porque ya estamos usando temp.

869
01:07:10,190 --> 01:07:17,200
Bien. Así que si (valor> * temp),

870
01:07:17,200 --> 01:07:24,010
y entonces (* temp) -> derecha

871
01:07:24,010 --> 01:07:29,250
más temp = & (* temp) -> a la izquierda.

872
01:07:29,250 --> 01:07:32,730
Y ahora, en este punto, después de este bucle while,

873
01:07:32,730 --> 01:07:36,380
Yo sólo hago esto porque tal vez es más fácil pensar en forma iterativa de forma recursiva,

874
01:07:36,380 --> 01:07:39,010
pero después de este bucle while,

875
01:07:39,010 --> 01:07:43,820
* Temp es el puntero que desea cambiar.

876
01:07:43,820 --> 01:07:48,960
>> Antes de tener padres, y queríamos cambiar hacia la izquierda padre o padres derecha,

877
01:07:48,960 --> 01:07:51,310
pero si queremos cambiar derechos de los padres,

878
01:07:51,310 --> 01:07:54,550
entonces es correcto * temp padre, y podemos cambiarlo directamente.

879
01:07:54,550 --> 01:08:05,860
Así que aquí, podemos hacer * temp = nodo_nuevo, y eso es todo.

880
01:08:05,860 --> 01:08:09,540
Así que aviso, todo lo que hicimos en esta era sacar líneas de código.

881
01:08:09,540 --> 01:08:14,770
Con el fin de seguir la pista de la matriz en todo lo que es esfuerzo adicional.

882
01:08:14,770 --> 01:08:18,689
En este caso, si tan sólo no perder de vista el puntero al puntero,

883
01:08:18,689 --> 01:08:22,990
e incluso si quería deshacerse de todas estas llaves ahora,

884
01:08:22,990 --> 01:08:27,170
hacer que se vea más corto.

885
01:08:27,170 --> 01:08:32,529
Esta es la misma solución exacta,

886
01:08:32,529 --> 01:08:38,210
pero menos líneas de código.

887
01:08:38,210 --> 01:08:41,229
Una vez que empezar a reconocer esto como una solución válida,

888
01:08:41,229 --> 01:08:43,529
también es más fácil de razonar acerca de que como, bien,

889
01:08:43,529 --> 01:08:45,779
¿por qué tengo esta bandera a la derecha int?

890
01:08:45,779 --> 01:08:49,290
¿Qué significa eso? Oh, está significando que

891
01:08:49,290 --> 01:08:51,370
cada vez que vaya a la derecha, tengo que ponerlo,

892
01:08:51,370 --> 01:08:53,819
else if I a la izquierda tengo que ponerlo a cero.

893
01:08:53,819 --> 01:09:04,060
En este caso, no tengo la razón en eso, es más fácil que pensar.

894
01:09:04,060 --> 01:09:06,710
¿Preguntas?

895
01:09:06,710 --> 01:09:16,290
[Estudiante, ininteligible] >> Si.

896
01:09:16,290 --> 01:09:23,359
Está bien, así que en el último -

897
01:09:23,359 --> 01:09:28,080
Supongo que una función rápida y fácil que podemos hacer es,

898
01:09:28,080 --> 01:09:34,910
let's - junto, creo, tratar de escribir una función contains

899
01:09:34,910 --> 01:09:38,899
que no le importa si se trata de un árbol de búsqueda binaria.

900
01:09:38,899 --> 01:09:43,770
Contiene función debe devolver true

901
01:09:43,770 --> 01:09:58,330
si cualquier parte de este árbol binario general es el valor que está buscando.

902
01:09:58,330 --> 01:10:02,520
Así que primero vamos a hacerlo de forma recursiva y luego lo haremos iterativa.

903
01:10:02,520 --> 01:10:07,300
De hecho, podemos simplemente hacerlo juntos, porque esto va a ser muy corta.

904
01:10:07,300 --> 01:10:11,510
>> ¿Cuál es mi hipótesis de base va a ser?

905
01:10:11,510 --> 01:10:13,890
[Estudiante, ininteligible]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Así que si (árbol == NULL), ¿entonces qué?

907
01:10:18,230 --> 01:10:22,740
[Estudiante] Volver falso.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Si no, bueno, yo no necesito el otro.

909
01:10:26,160 --> 01:10:30,250
Si fue mi caso otra base.

910
01:10:30,250 --> 01:10:32,450
Valor [Estudiante] Tree? Sí >>.

911
01:10:32,450 --> 01:10:36,430
Así que si (árbol-> value value ==.

912
01:10:36,430 --> 01:10:39,920
Tenga en cuenta que estamos de vuelta a * nodo no, nodo ** s?

913
01:10:39,920 --> 01:10:42,990
Contiene nunca tendrá que usar un ** nodos,

914
01:10:42,990 --> 01:10:45,480
ya que no estamos modificando punteros.

915
01:10:45,480 --> 01:10:50,540
Estamos atravesando ellos.

916
01:10:50,540 --> 01:10:53,830
Si eso sucede, entonces queremos volver realidad.

917
01:10:53,830 --> 01:10:58,270
Otras ventas que queremos recorrer los niños.

918
01:10:58,270 --> 01:11:02,620
Así que no podemos razonar acerca de si todo a la izquierda es menor

919
01:11:02,620 --> 01:11:05,390
y todo a la derecha es mayor.

920
01:11:05,390 --> 01:11:09,590
Entonces, ¿cuál es nuestro estado va a estar aquí - o, ¿qué vamos a hacer?

921
01:11:09,590 --> 01:11:11,840
[Estudiante, ininteligible] >> Si.

922
01:11:11,840 --> 01:11:17,400
Volver contiene (valor, árbol-> izquierdo)

923
01:11:17,400 --> 01:11:26,860
o contiene (valor, árbol-> derecha). Y eso es todo.

924
01:11:26,860 --> 01:11:29,080
Y cuenta de que hay algún tipo de evaluación de corto circuito,

925
01:11:29,080 --> 01:11:32,520
donde si nos toca encontrar el valor en el árbol de la izquierda,

926
01:11:32,520 --> 01:11:36,820
que nunca necesitamos mirar el árbol de la derecha.

927
01:11:36,820 --> 01:11:40,430
Esa es la función entera.

928
01:11:40,430 --> 01:11:43,690
Ahora vamos a hacerlo iterativamente,

929
01:11:43,690 --> 01:11:48,060
que va a ser menos agradable.

930
01:11:48,060 --> 01:11:54,750
Vamos a tomar la salida habitual de nodo * act = árbol.

931
01:11:54,750 --> 01:12:03,250
Mientras (act! = NULL).

932
01:12:03,250 --> 01:12:08,600
Rápidamente vamos a ver un problema.

933
01:12:08,600 --> 01:12:12,250
Si act - aquí, si alguna vez salir de esto,

934
01:12:12,250 --> 01:12:16,020
entonces nos hemos quedado sin cosas que ver, por lo que devuelve falso.

935
01:12:16,020 --> 01:12:24,810
Si (act-> valor value ==), devuelve true.

936
01:12:24,810 --> 01:12:32,910
Así que ahora, estamos en un lugar -

937
01:12:32,910 --> 01:12:36,250
no sabemos si queremos ir a la izquierda oa la derecha.

938
01:12:36,250 --> 01:12:44,590
Por lo tanto arbitrariamente, vamos a ir a la izquierda.

939
01:12:44,590 --> 01:12:47,910
Obviamente he topado con un problema en el que me he abandonado por completo todo -

940
01:12:47,910 --> 01:12:50,760
Sólo voy a comprobar siempre el lado izquierdo de un árbol.

941
01:12:50,760 --> 01:12:56,050
Nunca se compruebe todo lo que es un hijo derecho a nada.

942
01:12:56,050 --> 01:13:00,910
¿Cómo puedo solucionar este problema?

943
01:13:00,910 --> 01:13:05,260
[Estudiante] Hay que seguir la pista de la izquierda y la derecha en una pila.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Así que vamos a hacerlo

945
01:13:13,710 --> 01:13:32,360
struct lista nodo * n, y luego nodo ** siguiente?

946
01:13:32,360 --> 01:13:40,240
Yo creo que funciona bien.

947
01:13:40,240 --> 01:13:45,940
Queremos ir por la izquierda o let's - hasta aquí.

948
01:13:45,940 --> 01:13:54,350
Struct = lista de la lista, que va a empezar

949
01:13:54,350 --> 01:13:58,170
a cabo en esta lista struct.

950
01:13:58,170 --> 01:14:04,040
* Lista = NULL. Así que va a ser nuestra lista enlazada

951
01:14:04,040 --> 01:14:08,430
de subárboles que hemos saltado.

952
01:14:08,430 --> 01:14:13,800
Vamos a atravesar la izquierda ahora,

953
01:14:13,800 --> 01:14:17,870
pero es inevitable que tenga que volver a la derecha,

954
01:14:17,870 --> 01:14:26,140
Vamos a mantener el lado derecho dentro de nuestra lista de estructura.

955
01:14:26,140 --> 01:14:32,620
Entonces tendremos new_list o estructura,

956
01:14:32,620 --> 01:14:41,080
struct lista *, new_list = malloc (sizeof (lista)).

957
01:14:41,080 --> 01:14:44,920
Voy a pasar por alto la comprobación de errores, pero usted debe comprobar para ver si es nulo.

958
01:14:44,920 --> 01:14:50,540
New_list el nodo que va a apuntar a -

959
01:14:50,540 --> 01:14:56,890
oh, es por eso que lo quería aquí. Se va a apuntar a una lista struct segundo.

960
01:14:56,890 --> 01:15:02,380
Así es como el trabajo vinculado listas.

961
01:15:02,380 --> 01:15:04,810
Este es el mismo como una lista vinculada int

962
01:15:04,810 --> 01:15:06,960
excepto sólo estamos reemplazando con int * nodo.

963
01:15:06,960 --> 01:15:11,040
Es exactamente lo mismo.

964
01:15:11,040 --> 01:15:15,100
Así new_list, el valor de nuestro nodo new_list,

965
01:15:15,100 --> 01:15:19,120
va a ser actual-> derecha.

966
01:15:19,120 --> 01:15:24,280
El valor de nuestra new_list-> siguiente va a ser nuestra lista original,

967
01:15:24,280 --> 01:15:30,760
y luego vamos a actualizar nuestra lista para apuntar a new_list.

968
01:15:30,760 --> 01:15:33,650
>> Ahora necesitamos algún tipo de forma de las cosas que tiran,

969
01:15:33,650 --> 01:15:37,020
como hemos atravesado el subárbol izquierdo entero.

970
01:15:37,020 --> 01:15:40,480
Ahora tenemos que tirar cosas fuera de él,

971
01:15:40,480 --> 01:15:43,850
como act es nulo; no queremos volver simplemente falso.

972
01:15:43,850 --> 01:15:50,370
Queremos tirar ahora fuera de nuestra nueva lista.

973
01:15:50,370 --> 01:15:53,690
Una manera conveniente de hacer esto - bueno, en realidad, hay varias maneras de hacer esto.

974
01:15:53,690 --> 01:15:56,680
¿Alguien tiene alguna sugerencia?

975
01:15:56,680 --> 01:15:58,790
¿Dónde debo hacer esto o cómo debo hacerlo?

976
01:15:58,790 --> 01:16:08,010
Sólo tenemos un par de minutos, pero cualquier sugerencia?

977
01:16:08,010 --> 01:16:14,750
En lugar de - de una manera, en vez de nuestra condición de ser tiempo,

978
01:16:14,750 --> 01:16:17,090
lo que estamos mirando no es nulo,

979
01:16:17,090 --> 01:16:22,340
en lugar de eso vamos a seguir para ir hasta nuestra lista en sí es nulo.

980
01:16:22,340 --> 01:16:25,680
Así que si nuestra lista termina siendo nulo,

981
01:16:25,680 --> 01:16:30,680
entonces nos hemos quedado sin cosas que debe buscar, a buscar otra vez.

982
01:16:30,680 --> 01:16:39,860
Pero eso significa que lo primero en nuestra lista es sólo va a ser el primer nodo.

983
01:16:39,860 --> 01:16:49,730
Lo primero será - ya no tenemos que ver eso.

984
01:16:49,730 --> 01:16:58,710
Así lista-> n será nuestro árbol.

985
01:16:58,710 --> 01:17:02,860
lista-> siguiente va a ser nulo.

986
01:17:02,860 --> 01:17:07,580
Y ahora, mientras que la lista no nula de igualdad.

987
01:17:07,580 --> 01:17:11,610
Cur va a sacar algo de nuestra lista.

988
01:17:11,610 --> 01:17:13,500
Así act va a igual list-> n.

989
01:17:13,500 --> 01:17:20,850
Y entonces lista va a igual list-> n, o lista-> siguiente.

990
01:17:20,850 --> 01:17:23,480
Así que si el valor es igual al valor act.

991
01:17:23,480 --> 01:17:28,790
Ahora podemos añadir tanto los nuestros como puntero derecho y nuestro puntero izquierdo

992
01:17:28,790 --> 01:17:32,900
siempre y cuando no es nulo.

993
01:17:32,900 --> 01:17:36,390
Aquí abajo, supongo que deberíamos haber hecho eso en primer lugar.

994
01:17:36,390 --> 01:17:44,080
Si (act-> bien! = NULL)

995
01:17:44,080 --> 01:17:56,380
entonces vamos a insertar el nodo en la lista.

996
01:17:56,380 --> 01:17:59,290
Si (act-> izquierda), se trata de un poco de trabajo extra, pero está bien.

997
01:17:59,290 --> 01:18:02,690
Si (act-> izquierda! = NULL),

998
01:18:02,690 --> 01:18:14,310
y vamos a insertar a la izquierda en nuestra lista enlazada,

999
01:18:14,310 --> 01:18:19,700
y que debería ser.

1000
01:18:19,700 --> 01:18:22,670
Nos iterar - siempre y cuando tenemos algo en nuestra lista,

1001
01:18:22,670 --> 01:18:26,640
tenemos otro nodo a la vista.

1002
01:18:26,640 --> 01:18:28,920
Así que nos fijamos en ese nodo,

1003
01:18:28,920 --> 01:18:31,390
avanzamos nuestra lista para la siguiente.

1004
01:18:31,390 --> 01:18:34,060
Si el nodo es el valor que buscamos, podemos volver realidad.

1005
01:18:34,060 --> 01:18:37,640
Otras ventas insertar ambos subárboles nuestra izquierda y la derecha,

1006
01:18:37,640 --> 01:18:40,510
siempre y cuando no sean nulos, en la lista

1007
01:18:40,510 --> 01:18:43,120
de modo que es inevitable ir sobre ellos.

1008
01:18:43,120 --> 01:18:45,160
Así que si no eran nulas,

1009
01:18:45,160 --> 01:18:47,950
si nuestro puntero raíz señaló dos cosas,

1010
01:18:47,950 --> 01:18:51,670
a continuación, al principio nos sacó algo por lo que nuestra lista termina siendo nulo.

1011
01:18:51,670 --> 01:18:56,890
Y luego ponemos dos cosas de nuevo, por lo que ahora nuestra lista es de tamaño 2.

1012
01:18:56,890 --> 01:19:00,030
A continuación, vamos a tejer por atrás y sólo vamos a tirar,

1013
01:19:00,030 --> 01:19:04,250
digamos, el puntero izquierdo de nuestro nodo raíz.

1014
01:19:04,250 --> 01:19:07,730
Y eso va a seguir ocurriendo, vamos a terminar recorrer todo.

1015
01:19:07,730 --> 01:19:11,280
>> Observe que esto era significativamente más complicado

1016
01:19:11,280 --> 01:19:14,160
en la solución recursiva.

1017
01:19:14,160 --> 01:19:17,260
Y ya he dicho varias veces

1018
01:19:17,260 --> 01:19:25,120
que la solución recursiva por lo general tiene mucho en común con la solución iterativa.

1019
01:19:25,120 --> 01:19:30,820
Aquí es exactamente lo que la solución recursiva está haciendo.

1020
01:19:30,820 --> 01:19:36,740
El único cambio es que en lugar de utilizar implícitamente la pila, la pila del programa,

1021
01:19:36,740 --> 01:19:40,840
como su forma de hacer el seguimiento de qué nodos usted todavía tiene que visitar,

1022
01:19:40,840 --> 01:19:45,430
Ahora usted tiene que utilizar explícitamente una lista enlazada.

1023
01:19:45,430 --> 01:19:49,070
En ambos casos, usted está guardando un registro de lo nodo todavía tiene que ser visitado.

1024
01:19:49,070 --> 01:19:51,790
En el caso recursivo es más fácil porque una pila

1025
01:19:51,790 --> 01:19:57,100
que se aplique a usted como la pila del programa.

1026
01:19:57,100 --> 01:19:59,550
Observe que esta lista enlazada, es una pila.

1027
01:19:59,550 --> 01:20:01,580
Independientemente de lo que acaba de poner en la pila

1028
01:20:01,580 --> 01:20:09,960
es inmediatamente lo que vamos a quitar la pila para la próxima visita.

1029
01:20:09,960 --> 01:20:14,380
Estamos fuera de tiempo, pero alguna pregunta?

1030
01:20:14,380 --> 01:20:23,530
[Estudiante, ininteligible]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Así que si tenemos nuestra lista enlazada,

1032
01:20:27,790 --> 01:20:30,150
actual se va a apuntar a este chico,

1033
01:20:30,150 --> 01:20:34,690
y ahora estamos avanzando a nuestra lista enlazada para centrarse en este tipo.

1034
01:20:34,690 --> 01:20:44,200
Estamos atravesando por la lista enlazada en esa línea.

1035
01:20:44,200 --> 01:20:51,200
Y entonces creo que debemos liberar nuestra lista enlazada y esas cosas

1036
01:20:51,200 --> 01:20:53,880
una vez antes de regresar verdadera o falsa, tenemos que

1037
01:20:53,880 --> 01:20:57,360
iterar a través de nuestra lista enlazada y siempre aquí abajo, supongo,

1038
01:20:57,360 --> 01:21:03,900
si act derecho no es igual que agregar, por lo que ahora queremos liberar

1039
01:21:03,900 --> 01:21:09,600
act porque, bueno, qué nos olvidamos por completo de la lista? Si.

1040
01:21:09,600 --> 01:21:12,880
Así que eso es lo que queremos hacer aquí.

1041
01:21:12,880 --> 01:21:16,730
¿Dónde está el puntero?

1042
01:21:16,730 --> 01:21:23,320
Cur era entonces - queremos una lista struct * 10 es igual a la lista siguiente.

1043
01:21:23,320 --> 01:21:29,240
Lista libre, list = temp.

1044
01:21:29,240 --> 01:21:32,820
Y en el caso de que nos devuelva true, necesitamos iterar

1045
01:21:32,820 --> 01:21:37,050
durante el resto de nuestra lista enlazada liberar cosas.

1046
01:21:37,050 --> 01:21:39,700
Lo bueno de la solución recursiva es liberar a las cosas

1047
01:21:39,700 --> 01:21:44,930
Sólo significa factorings apareciendo de la pila que va a suceder para usted.

1048
01:21:44,930 --> 01:21:50,720
Así que hemos pasado de algo que es como 3 líneas de duro-a-pensar-sobre el código

1049
01:21:50,720 --> 01:21:57,520
a algo que es significativamente muchos más difíciles de pensamiento acerca de las líneas de código.

1050
01:21:57,520 --> 01:22:00,620
Algo más preguntas?

1051
01:22:00,620 --> 01:22:08,760
Está bien. Estamos bien. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]