[Powered by Google Translate] [Sección 7: más cómodo]
[Rob Bowden] [Harvard University]
[Esta es CS50] [CS50.TV]
Está bien. Así que, como dije en mi e-mail,
esto va a ser una sección del árbol binario de obra.
Pero no hay que muchas preguntas.
Así que vamos a tratar de sacar cada pregunta
y entrar en detalles dolorosos de las mejores maneras de hacer las cosas.
Así que desde el principio, vamos a través de los dibujos de la muestra de árboles binarios y esas cosas.
Así que aquí, "Recuerda que un árbol binario tiene nodos similares a los de una lista enlazada,
pero en lugar de un puntero hay dos: uno para "niño" a la izquierda
y otro para la derecha "niño". "
Así que un árbol binario es igual que una lista enlazada,
excepto la estructura va a tener dos punteros.
Hay árboles trinarios, que van a tener tres punteros,
hay N-arias árboles, que sólo tienen un puntero genérico
que usted entonces tiene que malloc ser lo suficientemente grande para tener
indicadores suficientes para todos los niños posibles.
Así árbol binario sólo pasa a tener un número constante de dos.
Si lo desea, puede dar una lista enlazada como un árbol unario,
pero yo no creo que nadie lo llama eso.
"Dibujar un diagrama de cajas y flechas de un nodo del árbol binario
que contiene el número preferido de Nate, 7, donde cada puntero niño es nulo. "
Así que el modo de iPad.
>> Va a ser bastante sencillo.
Sólo vamos a tener un nodo, lo voy a dibujar un cuadrado.
Y voy a sacar los valores de aquí.
Así, el valor pasará de aquí,
y entonces aquí vamos a tener el puntero a la izquierda de la izquierda y el puntero a la derecha en la derecha.
Y es mucho lo que la convención de llamar a la izquierda y la derecha, los nombres de puntero.
Ambos van a ser nulo.
Eso sólo será nulo, y que sólo será nulo.
Bien. Así que de vuelta a aquí.
"Con una lista enlazada, sólo teníamos que almacenar un puntero
al primer nodo de la lista para recordar toda la lista vinculada, o toda la lista.
Del mismo modo, con los árboles, sólo tiene que almacenar un puntero
a un único nodo con el fin de recordar a todo el árbol.
Este nodo es la calle "raíz" del árbol.
Basarse en el diagrama de antes o dibujar uno nuevo
de tal manera que tiene una representación cajas y flechas de un árbol binario
con el valor de 7, a continuación, 3 en la izquierda,
a continuación, 9 a la derecha, y luego 6 a la derecha de la 3. "
Vamos a ver si puedo recordar todo eso en mi cabeza.
Así que esto va a ser nuestra raíz hasta aquí.
Vamos a tener un poco de puntero en algún lugar, algo que llamaremos raíz,
y que apunta a este tipo.
Ahora para hacer un nuevo nodo,
¿qué es lo que tenemos, 3 a la izquierda?
Así que un nuevo nodo con 3, y que señala inicialmente nulo.
Voy a poner N.
Ahora queremos hacer que ir a la izquierda 7.
Así que cambiamos este puntero para apuntar ahora a este tipo.
Y hacemos lo mismo. Queremos un 9 por aquí
que en un principio sólo dice nulo.
Vamos a cambiar este puntero, señale a 9,
y ahora queremos poner 6 a la derecha de 3.
Así que va a - hacer un 6.
Y ese chico va a apuntar allí.
Bien. Así que eso es todo lo que se nos pide que hagamos.
>> Ahora vamos a repasar algunos términos.
Ya hemos hablado de cómo la raíz del árbol es el nodo de más arriba en el árbol.
El uno que contiene 7. Los nodos en la parte inferior del árbol se llaman las hojas.
Cualquier nodo que sólo tiene nulo como sus hijos es una hoja.
Así es posible, si nuestro árbol binario es sólo un único nodo,
que un árbol es una hoja, y eso es todo.
"El 'height' del árbol es el número de saltos que tiene que hacer
para llegar desde la parte superior a una hoja. "
Vamos a entrar, en un segundo, la diferencia
entre los árboles binarios balanceados y no balanceados,
pero por ahora, la altura total de este árbol
Yo diría que es 3, aunque si se cuenta el número de saltos
lo que tienes que hacer para llegar a 9, entonces es realmente sólo una altura de 2.
En este momento se trata de un árbol binario desequilibrado,
pero vamos a hablar acerca de equilibrado cuando llega a ser relevante.
Así que ahora podemos hablar de los nodos de un árbol en términos
con respecto a los otros nodos en el árbol.
Así que ahora tenemos padres, hijos, hermanos, ascendientes y descendientes.
Son bastante sentido común, lo que significan.
Si nos preguntamos - son los padres.
Entonces, ¿qué es el padre de 3?
[Los estudiantes] 7. Sí >>. El padre es sólo va a ser lo señala a usted.
Entonces, ¿qué son los niños de 7?
[Los estudiantes] 3 y 9. Sí >>.
Tenga en cuenta que los "niños" significa literalmente hijos,
así que 6 no se aplicaría, porque es como un nieto.
Pero si vamos descendientes, así que lo que son los descendientes de 7?
[Los estudiantes] 3, 6 y 9. Sí >>.
Los descendientes del nodo raíz va a ser todo en el árbol,
excepto tal vez el nodo raíz en sí, si no quieres tener en cuenta que un descendiente.
Y finalmente, los ancestros, por lo que es la dirección opuesta.
¿Cuáles son los antepasados ​​de 6?
[Los estudiantes] 3 y 7. Sí >>. 9 no está incluido.
Es sólo la parte de atrás linaje directo a la raíz
Va a ser sus antepasados.
>> "Decimos que un árbol binario es" ordenado "si para cada nodo en el árbol,
todos sus descendientes de la izquierda tienen valores menores
y todos los de la derecha tienen valores mayores.
Por ejemplo, el árbol de arriba está ordenado, pero no es la única posible ordenado ".
Antes de llegar a eso,
un árbol binario ordenado también se conoce como un árbol binario de búsqueda.
Aquí sucede que se le llama un árbol binario ordenado,
pero nunca he oído llamar un árbol binario ordenado antes,
y en una prueba que son mucho más propensos a poner árbol de búsqueda binaria.
Son uno y el mismo,
y es importante que usted reconozca la distinción entre árbol y árbol binario de búsqueda binaria.
Un árbol binario es un árbol que apunta a dos cosas.
Cada nodo apunta a dos cosas.
No hay razonamiento sobre los valores que se apunta.
Así como aquí, ya que es un árbol de búsqueda binaria,
sabemos que si vamos a la izquierda de 7,
entonces todos los valores que nos sea posible alcanzar
yendo a la izquierda de 7 tiene que ser menor que 7.
Tenga en cuenta que todos los valores menos que 7 son 3 y 6.
Esos son todos a la izquierda de 7.
Si nos vamos a la derecha de 7, todo tiene que ser superior a 7,
9 es tan a la derecha de 7, así que estamos bien.
Este no es el caso de un árbol binario,
para un árbol binario regular que se puede tener en la parte superior 3, 7 a la izquierda,
9 a la izquierda de 7, no hay orden de valores cualesquiera.
Ahora, no vamos a hacer esto porque es tedioso e innecesario,
sino "tratar de extraer árboles ordenados como muchos como usted puede pensar en
usando los números 7, 3, 9, y 6.
¿Cuántos arreglos diferentes hay? ¿Cuál es la altura de cada uno? "
>> Haremos una pareja, pero es la idea principal,
esto no es en manera alguna una representación única de un árbol binario que contiene estos valores.
Todo lo que necesitamos es un árbol binario que contiene 7, 3, 6 y 9.
Otra posibilidad sería válida la raíz es 3,
ir a la izquierda y es 6, vaya a la izquierda y es 7,
ir a la izquierda y es 9.
Que es un árbol binario de búsqueda perfectamente válido.
No es muy útil, ya que es como una lista enlazada
y todos estos punteros son null.
Pero es un árbol válida. ¿Sí?
[Estudiante] ¿Acaso los valores tienen que ser mayores de la derecha?
¿O es esto -? Estos >> quise ir a otro lado.
Hay también - sí, vamos a cambiar eso.
9, 7, 6, 3. Buena captura.
Todavía tiene que obedecer lo que es un árbol de búsqueda binaria se supone que debe hacer.
Así todo a la izquierda tiene que ser menor que cualquier nodo dado.
Sólo podía mover, por ejemplo, el 6 y lo puso aquí.
No, no podemos. ¿Por qué sigo haciendo esto?
Vamos a hacerlo - aquí es 6, aquí es 7, 6 puntos a 3.
Esto sigue siendo un árbol binario de búsqueda válida.
¿Qué pasa si yo - vamos a ver si puedo llegar a un acuerdo.
Sí, está bien. Entonces, ¿qué está mal con este árbol?
Supongo que ya te he dado un indicio de que hay algo malo en ello.
¿Por qué sigo haciendo esto?
Bien. Esto parece razonable.
Si nos fijamos en cada nodo, como 7, luego a la izquierda de 7 es un 3.
Así que tenemos 3, la cosa a la derecha de 3 es un 6.
Y si miras a los 6, la cosa a la derecha de 6 es un 9.
¿Por qué no es este un árbol binario de búsqueda válido?
[Los estudiantes] 9 es todavía a la izquierda de 7. Sí >>.
Debe ser cierto que todos los valores que posiblemente puede llegar por ir a la izquierda de 7 son menos de 7.
Si se va a la izquierda, de 7, se llega a 3 y todavía podemos llegar a 6,
todavía podemos llegar a 9, pero por haber pasado menos de 7,
no hay que ser capaz de llegar a un número que es mayor que 7.
Así que esto no es un árbol binario de búsqueda válida.
>> Mi hermano tenía realmente una pregunta de la entrevista
que era básicamente esto, sólo algo de código para validar
si un árbol es un árbol de búsqueda binaria,
y así que lo primero que hizo fue simplemente compruebe
si la izquierda y la derecha son correctos, y luego iterar por allí.
Pero no se puede hacer eso, hay que seguir la pista
el hecho de que ahora que me he ido a la izquierda de 7,
todo en este subárbol debe ser menor que 7.
El algoritmo correcto necesita seguir la pista
de los límites de los valores que posiblemente pueden caer pulg
No vamos a ir a través de todos ellos.
Hay una relación de recurrencia agradable,
aunque no hemos llegado a ellos, o no vamos a llegar a ellos,
definir cuántos son en realidad.
Así que hay 14 de ellos.
La idea de la forma en que lo haría matemáticamente es como,
usted puede escoger uno solo para ser el nodo raíz,
y entonces si tomo 7 a ser el nodo raíz,
luego están, por ejemplo, algunos números que pueden ir a ser mi nodo izquierdo,
y hay algunos números que pueden ser mi nodo de la derecha,
pero si tiene n cifras totales, la cantidad que puede ir a la izquierda
más la cantidad que puede ir a la derecha es n - 1.
Así de los números restantes, tienen que ser capaces de ir hacia la izquierda o la derecha.
Parece difícil que, si pongo 3 primero y luego todo lo que tiene que ir a la izquierda,
pero si pongo 7, a continuación, algunas cosas pueden ir a la izquierda y algunas cosas pueden ir a la derecha.
Y por '3 'primero que quise decir todo puede ir a la derecha.
En realidad, sólo hay que pensar en ello como,
cuántas cosas pueden pasar en el siguiente nivel del árbol.
Y viene a ser 14, o puede dibujar todos ellos,
y entonces usted conseguirá 14.
>> Volviendo aquí,
"Ordenó árboles binarios son frescos ya que podemos buscar a través de ellos
de una manera muy similar a la búsqueda a través de una matriz ordenada.
Para ello, partimos de la raíz y vamos por el árbol
hacia las hojas, comprobando los valores de cada nodo con los valores que estamos buscando.
Si el valor del nodo actual es menor que el valor que estamos buscando,
acercarte a hijo derecho del nodo.
De lo contrario, vaya al hijo izquierdo del nodo.
En algún momento, usted encontrará el valor que usted está buscando, o te encontrarás con un valor nulo,
lo que indica que el valor no está en el árbol. "
Tengo que volver a dibujar el árbol que teníamos antes, que tomará un segundo.
Pero queremos mirar hacia arriba si 6, 10 y 1 están en el árbol.
Así que lo que era, 7, 9, 3, 6. Bien.
Los números que desea buscar, queremos mirar hacia arriba 6.
¿Cómo funciona este algoritmo?
Bueno, también tenemos algunos puntero raíz de nuestro árbol.
Y nos volveríamos a ir a la raíz y decir, este valor es igual al valor que estamos buscando?
Así que estamos buscando para 6, así que no es igual.
Por lo tanto, seguir adelante, y ahora se dice, está bien, así que 6 es menor que 7.
¿Significa eso que queremos ir hacia la izquierda, o queremos ir a la derecha?
[Estudiante] Izquierda. Sí >>.
Es mucho más fácil, lo único que tienes que hacer es sacar un nodo del árbol es posible
y entonces no - en lugar de tratar de pensar en tu cabeza,
bien, si es menos, ¿debo ir a la izquierda o ir a la derecha,
sólo mirar a esta imagen, es muy claro que tengo que ir a la izquierda
si este nodo es mayor que el valor que yo estoy buscando.
Así que ir a la izquierda, ahora estoy en 3.
Quiero - 3 es menor que el valor que estoy buscando, que es de 6.
Así que nos vamos a la derecha, y ahora termino a las 6,
que es el valor que estoy buscando, así que me devuelva true.
El siguiente valor que voy a buscar es 10.
Bien. Así que 10, ahora, va a - cortar eso - va a seguir la raíz.
Ahora, el 10 va a ser superior a 7, así que quiero mirar a la derecha.
Voy a venir por aquí, 10 va a ser mayor que 9,
así que voy a querer mirar a la derecha.
Yo vengo por aquí, pero aquí ahora estoy en null.
¿Qué hago si me golpeó nulo?
[Estudiante] Volver falso? Sí >>. No encontré 10.
1 va a ser un caso casi idéntico,
excepto que sólo va a dar la vuelta, en lugar de buscar
por el lado derecho, voy a mirar hacia abajo a la izquierda.
>> Ahora creo que en realidad obtener el código.
Aquí es donde - abrir el aparato CS50 y navegar por su camino,
pero usted puede también hacerlo en el espacio.
Es probable que sea ideal para hacerlo en el espacio,
porque podemos trabajar en el espacio.
"Primero vamos a necesitar una definición de tipo nuevo para un nodo del árbol binario que contiene valores int.
Usando el repetitivo typedef continuación,
crear una definición de nuevo tipo para un nodo en un árbol binario.
Si te quedas atascado. . . "Blah, blah, blah. Okay.
Así que vamos a poner aquí el texto modelo,
typedef struct nodo y nodo. Sí, está bien.
Entonces, ¿qué son los campos que vamos a querer a nuestro nodo?
[Estudiante] Int. y luego dos punteros?
Int >> valor, dos punteros? ¿Cómo puedo escribir los punteros?
[Estudiante] Struct. >> Me zoom in Sí, así struct nodo * a la izquierda,
y struct nodo * derecha.
Y recuerda que el debate de la última vez,
que esto no tiene sentido, esto no tiene sentido,
esto no tiene sentido.
Necesitas todo lo que hay para definir esta estructura recursiva.
Muy bien, así que eso es lo que nuestro árbol va a parecer.
Si hiciéramos un árbol ternario, a continuación, un nodo puede ser como b1, b2, b3 struct nodo *,
donde b es una rama - en realidad, he oído más a la izquierda, centro, derecha, pero lo que sea.
Sólo nos importa binario, por lo derecha, izquierda.
"Ahora declaramos una variable global para el nodo * la raíz del árbol."
Así que no vamos a hacer eso.
Para hacer las cosas un poco más difícil y más generalizada,
no vamos a tener una variable de nodo global.
En cambio, en principal por la que nos declarará todas nuestras cosas de nodos,
y eso significa que más adelante, cuando empezamos a correr
nuestra función CONTAINS y nuestra función de inserción,
en lugar de nuestras contiene la función de sólo usar esta variable nodo global,
vamos a tener que tomar como argumento el árbol que queremos que sean procesados.
Tener la variable global se supone que hace las cosas más fáciles.
Vamos a hacer las cosas más difíciles.
Ahora tome un minuto para sólo hacer este tipo de cosas,
donde dentro de la principal que desea crear este árbol, y eso es todo lo que quiero hacer.
Trate de construir este árbol en su función principal.
>> Bien. Así que no tienen ni siquiera haber construido el árbol durante todo el camino todavía.
Pero alguien tiene algo que pudiera levantar
para mostrar cómo se puede empezar a construir un árbol?
[Estudiante] Alguien está golpeando, tratando de salir.
[Bowden] Cualquier persona cómodos con su construcción del árbol?
[Estudiante] Claro. No se hace. >> Está bien. Sólo podemos terminar -
oh, puede usted ahorrar? ¡Hurra.
Así que aquí tenemos - oh, estoy un poco cortado.
¿Estoy zoom?
Zoom hacia dentro, desplácese hacia fuera. >> Tengo una pregunta. >> ¿Sí?
[Estudiante] Cuando se define una estructura, son cosas como inicializado a algo?
[Bowden] >> No. Está bien. Así que tendría que inicializar -
[Bowden] No. Cuando se define, o cuando se declara una struct,
no se inicializa de forma predeterminada, es igual que si se declara un int.
Es exactamente lo mismo. Es como si cada uno de sus campos individuales
puede tener un valor basura en ella. >> Y es posible definir - o declarar a una estructura
de una manera que lo hace inicializar ellos?
[Bowden] Sí. Por lo tanto, el acceso directo sintaxis de inicialización
se va a ver como -
Hay dos formas en que podemos hacer esto. Creo que debemos compilarlo
para hacer Clang seguro también lo hace.
El orden de los argumentos que viene en la estructura,
usted pone el orden de los argumentos dentro de estas llaves.
Así que si usted desea inicializar a 9 y se queda nulo y luego a la derecha ser nulo,
sería 9, null, null.
La alternativa es, y el editor no le gusta esta sintaxis,
y se cree que quiero un nuevo bloque,
pero la alternativa es algo así como -
aquí, lo voy a poner en una nueva línea.
Usted puede explicitamente decir, no recuerdo la sintaxis exacta.
Así que usted puede abordar explícitamente por su nombre, y decir:
. C o. = Valor 9,. Izquierda = NULL.
Supongo que estos deben ser comas.
. Derecha = NULL, por lo que este camino no lo hace
realmente necesita saber el orden de la estructura,
y cuando usted está leyendo esto, es mucho más explícita
acerca de cuál es el valor que se está inicializado a.
>> Esto pasa a ser una de las cosas que -
así, en su mayor parte, C + + es un superconjunto de C.
Usted puede tomar el código C, moverlo a C + +, y se debe compilar.
Esta es una de las cosas que C + + no admite, por lo que la gente tiende a no hacerlo.
No sé si esa es la única razón por la gente tiende a no hacerlo,
pero el caso donde tenía que usarlo necesario para trabajar con C + + y lo que no podía usarlo.
Otro ejemplo de algo que no funciona en C + + es
como malloc devuelve un "void *," técnicamente,
pero usted podría decir char * x = cualquier malloc,
y automáticamente se convierte en un char *.
Ese reparto automático no ocurre en C + +.
Eso no va a compilar, y de forma explícita tendría que decir
char *, malloc, lo que sea, para lanzarlo a un char *.
No hay muchas cosas que C y C + + no están de acuerdo en,
pero esos son dos.
Así que vamos a ir con esta sintaxis.
Pero incluso si no fue con esa sintaxis,
lo que es - podría ser malo en esto?
[Estudiante] No es necesario eliminar la referencia verdad? Sí >>.
Recuerde que la flecha tiene un dereference implícita,
y así, cuando sólo estamos tratando con una estructura,
que desea utilizar. para llegar a un campo en el interior de la estructura.
Y la única vez que utilice la flecha es cuando queremos hacer -
así, la flecha es equivalente a -
eso es lo que habría significado si he usado flecha.
Todos los medios flecha es decir, eliminar la referencia esto, ahora estoy en una estructura, y puedo conseguir el terreno.
Cualquiera de obtener el campo o directamente eliminar la referencia y obtener el campo -
Supongo que esto debe ser el valor.
Pero aquí estoy tratando con sólo una estructura, no es un puntero a una estructura,
y por lo tanto no puedo usar la flecha.
Pero este tipo de cosas que podemos hacer para todos los nodos.
Oh mi Dios.
Esto es 6, 7, y 3.
Entonces podemos establecer las sucursales en nuestro árbol, podemos tener 7 -
Podemos tener, a su izquierda debe apuntar a 3.
Entonces, ¿cómo hacer eso?
[Los estudiantes, ininteligible] >> Yeah. La dirección de node3,
y si no tenía la dirección, entonces simplemente no se compilará.
Pero recuerde que estos son punteros a los nodos próximos.
El derecho debe apuntar a 9,
y 3 deben apuntar a la derecha a 6.
Creo que esto es todo listo. Cualquier comentario o pregunta?
[Estudiante, ininteligible] La raíz va a ser 7.
Sólo podemos decir nodo * ptr =
o raíz, = & node7.
>> Para nuestros propósitos, vamos a estar tratando con insert,
así que vamos a querer escribir una función para insertar en este árbol binario
y el inserto está inevitablemente va a llamar a malloc para crear un nuevo nodo de este árbol.
Así que las cosas van a causar problemas con el hecho de que algunos nodos
son actualmente en la pila
y otros nodos van a terminar en el montón cuando las inserte.
Esto es perfectamente válido, pero la única razón
somos capaces de hacer esto en la pila
es debido a que es un ejemplo artificial que sabemos
el árbol se supone que se construye como 7, 3, 6, 9.
Si no tiene esto, entonces no tendría que malloc en el primer lugar.
Como veremos un poco más adelante, debemos estar malloc'ing.
Ahora mismo es perfectamente razonable para poner en la pila,
pero vamos a cambiar esto a una implementación de malloc.
Así que cada uno de ellos ahora va a ser algo así como
nodo * node9 = malloc (sizeof (nodo)).
Y ahora vamos a tener que hacer el proceso de registro.
if (node9 == NULL) - No quería que -
devuelve 1, y luego podemos hacer node9-> porque ahora es un puntero,
valor = 6, node9-> left = NULL,
node9-> derecha = NULL,
y vamos a tener que hacer esto para cada uno de los nodos.
Así que en vez, vamos a poner dentro de una función separada.
Digamos que es el nodo * build_node,
y esto es algo similar a la API que proporcionar para la codificación de Huffman.
Le damos las funciones inicializador para un árbol
y deconstructor "funciones" de los árboles y lo mismo para los bosques.
>> Así que aquí vamos a tener una función de inicialización
a sólo construir un nodo para nosotros.
Y va a ver casi exactamente así.
Y estoy aún va a ser perezoso y no cambiar el nombre de la variable,
aunque node9 no tiene sentido ya.
Oh, supongo valor node9 no debería haber sido 6.
Ahora podemos volver node9.
Y aquí debemos volver nulo.
Todo el mundo está de acuerdo en que la función build-a-nodo?
Así que ahora sólo podemos llamar así a construir un nodo con un valor determinado y punteros nulos.
Ahora podemos llamar así, que podemos hacer nodo * node9 = build_node (9).
Y vamos a hacer. . .
6, 3, 7, 6, 3, 7.
Y ahora queremos establecer los punteros mismos,
excepto que ahora todo está ya en términos de indicadores
así que ya no necesita la dirección de.
Bien. Entonces, ¿qué es lo último que quiero hacer?
Hay un error de comprobación de que no estoy haciendo.
¿Qué significa construir retorno nodo?
[Estudiante, ininteligible] >> Si. Si malloc no, devolverá null.
Así que voy a perezosamente dejar de leerlo aquí en vez de hacer una condición para cada uno.
Si (node9 == NULL, - o aún más simple,
esto es equivalente a poco si no node9.
Así que si no node9, o no node6, o no node3, o no node7, devolverá 1.
Tal vez deberíamos imprimir malloc fracasado, o algo así.
[Estudiante] Es falso igual a null también?
[Bowden] Cualquier valor cero es falso.
Así nulo es un valor cero.
Cero es un valor de cero. False es un valor de cero.
Cualquiera - prácticamente los únicos 2 valores cero son nulos y cero,
falso es sólo hachís definido como cero.
Esto también se aplica si se declaran variable global.
Si tuviéramos nodo raíz * hasta aquí,
entonces - lo bueno de variables globales es que siempre tienen un valor inicial.
Eso no es cierto de funciones, como el interior de aquí,
si tenemos, como *, nodo o nodo x.
No tenemos idea de lo que x.value, x.whatever,
o podríamos imprimirlos y que podría resultar arbitrario.
Eso no es cierto de las variables globales.
Así nodo raíz o un nodo x.
Por defecto, todo lo que es global, si no explícitamente inicializada a un valor,
tiene un valor de cero como su valor.
Así que aquí, la raíz nodo *, no explícitamente inicializar a cualquier cosa,
por lo que su valor por defecto será nulo, que es el valor cero de punteros.
El valor por omisión de x va a significar que x.value es cero,
x.left es nulo, y x.right es nulo.
Por lo tanto, ya que es una estructura, todos los campos de la estructura será el valor cero.
No es necesario utilizar que aquí, sin embargo.
[Estudiante] Las estructuras son diferentes de las otras variables, y son las otras variables
valores de basura, que son ceros?
Bowden [] Otros valores también. Así, en x, x será cero.
Si es en el ámbito global, tiene un valor inicial. >> Okay.
[Bowden] O el valor inicial que dio o cero.
Creo que se encarga de todo esto.
>> Bien. Así que la siguiente parte de la pregunta se refiere,
"Ahora queremos escribir una función llamada contiene
con un prototipo de bool contiene un valor int. "
No vamos a hacer bool contiene un valor int.
Nuestro prototipo se va a parecer
bool contiene (valor int.
Y también vamos a pasar el árbol
que se debe comprobar para ver si tiene ese valor.
Así nodo * árbol). Bien.
Y entonces podemos llamarlo con algo así como:
tal vez querrá printf o algo así.
Contiene 6, nuestra raíz.
Esto debería devolver uno o verdadero,
mientras que la raíz contiene 5 debe devolver false.
Así que toma un segundo para implementar esto.
Puede hacerlo ya sea iterativamente o recursivamente.
Lo bueno de la forma en que hemos establecido es que las cosas
se presta a nuestra solución recursiva mucho más fácil
de manera global la variable hecho.
Porque si sólo tenemos contiene un valor int, entonces no tenemos forma de manera recursiva por subárboles.
Tendríamos que tener una función auxiliar independiente que recursivamente por los subárboles para nosotros.
Pero ya que hemos cambiado a tomar el árbol como un argumento,
que debería haber sido siempre, en primer lugar,
ahora podemos recurse con mayor facilidad.
Así iterativo o recursivo, vamos a repasar los dos,
pero vamos a ver que los extremos recursivas siendo bastante fácil.
Bien. ¿Alguien tiene algo que podamos trabajar?
>> [Estudiante] Tengo una solución iterativa. >> Muy bien, iterativo.
Bueno, esto se ve bien.
Por lo tanto, nos quieren caminar a través de él?
[Estudiante] Claro. Así que me puse una variable temporal para obtener el primer nodo del árbol.
Y entonces sólo en bucle mientras que la temperatura no nula de igualdad,
así que mientras se encontraba todavía en el árbol, supongo.
Y si el valor es igual al valor que está apuntando a temp,
a continuación, se devuelve dicho valor.
De lo contrario, se comprueba si está en el lado derecho o el lado izquierdo.
Si alguna vez tienes una situación en la que no hay más árboles,
luego vuelve - sale del bucle y devuelve false.
[Bowden] Bueno. Así que parece bueno.
Cualquier persona tiene algún comentario sobre cualquier cosa?
No tengo comentarios corrección en absoluto.
Lo único que podemos hacer es este tipo.
Oh, va a ir un poco alargada.
Voy a arreglar eso. Bien.
>> Todo el mundo debería recordar cómo funciona ternario.
No ha sido, sin duda pruebas en el pasado
que le dan una función con un operador ternario,
y decir, traducir esto, hacer algo que no utiliza ternario.
Así que este es un caso muy común de cuando se le ocurriría utilizar ternario,
donde si alguna condición establecer una variable a algo,
otra indicación de que la misma variable a otra cosa.
Eso es algo que con mucha frecuencia se puede transformar en este tipo de cosas
donde asignar a esa variable esta - o, bien, ¿es esto cierto? Luego de esto, más esto.
[Estudiante] La primera es si es cierto, ¿verdad?
[Bowden] Yeah. La forma en que siempre lo leído es, la temperatura es igual al valor mayor que el valor temporal,
entonces esto, más de esto. Está haciendo una pregunta.
¿Es grande? Luego hacer lo primero. Demás hacer lo segundo.
Yo casi siempre - los dos puntos, yo sólo - en mi cabeza, he leído como otra cosa.
>> ¿Alguien tiene una solución recursiva?
Bien. Éste vamos a - que ya podía ser grande,
pero vamos a hacerlo aún mejor.
Esto es más o menos la idea exactamente el mismo.
Es sólo que, bueno, es lo que quieres explicar?
[Estudiante] Claro. Así nos aseguramos de que el árbol no es nulo en primer lugar,
porque si el árbol es nulo entonces va a devolver falso, porque no lo hemos encontrado.
Y si todavía hay un árbol, entramos en - en primer lugar comprobar si el valor es el nodo actual.
Devuelve verdadero si lo es, y si no recurse a la izquierda oa la derecha.
¿Le parece adecuado? >> Mm-hmm. (Acuerdo)
Así cuenta de que esto es casi - estructuralmente muy similar a la solución iterativa.
Es sólo que en lugar de recursividad, tuvimos un bucle while.
Y el caso base aquí donde árbol no hace nulo igual
era la condición bajo la cual rompió el bucle while.
Son muy similares. Pero vamos a dar un paso más allá.
Ahora, hacemos lo mismo aquí.
Tenga en cuenta que estamos volviendo lo mismo en ambas líneas,
a excepción de un argumento es diferente.
Así que vamos a hacer eso en un ternario.
Golpeé algo opción, e hizo un símbolo. Bien.
Así que vamos a volver que contiene.
Esto se está convirtiendo en varias líneas, bueno, el zoom es.
Por lo general, como una cosa de estilo, no creo que mucha gente
poner un espacio después de la flecha, pero supongo que si eres consistente, está bien.
Si el valor es inferior al valor del árbol, queremos recurse a la izquierda del árbol,
más queremos recurse a la derecha del árbol.
Así que ese fue el primer paso de hacer esta mirada más pequeño.
Paso dos de hacer esta mirada más pequeño -
podemos separar esta a varias líneas.
Bien. El segundo paso de hacer que se vea más pequeña está aquí,
así valor de retorno es igual al valor del árbol, o contiene lo que sea.
>> Esto es una cosa importante.
No estoy seguro de si lo dijo explícitamente en la clase,
pero se llama la evaluación de cortocircuito.
La idea aquí es value == valor árbol.
Si eso es verdad, entonces esto es cierto, y queremos »o« eso con lo que esté por aquí.
Así, sin siquiera pensar en lo que está por aquí,
¿cuál es la expresión entera va a regresar?
[Estudiante] Cierto? >> Sí, porque cierto de nada,
operación lógica OR - operación lógica OR o verdadero con todo es necesariamente cierto.
Así que tan pronto como vemos valor de retorno = Valor de árbol,
sólo vamos a volver realidad.
Ni siquiera va a recurse contiene además de la línea.
Podemos dar un paso más allá.
Árbol retorno no nulo igual y todo eso.
Lo hizo en función de una línea.
Este es también un ejemplo de la evaluación de cortocircuito.
Pero ahora es la misma idea -
en lugar de - por lo que si el árbol no nulo igual - o, bien,
si árbol hace nula de igualdad, que es el caso malo,
si el árbol es igual a NULL, la primera condición será falsa.
Así falso AND con cualquier cosa va a ser qué?
[Estudiante] Falso. Sí >>. Esta es la otra mitad de la evaluación de cortocircuito,
donde si el árbol es nulo no es igual, entonces no vamos a ir aún más -
o si el árbol hace nulo iguales, entonces no vamos a hacer value == valor árbol.
Sólo vamos a regresar de inmediato falsa.
Lo cual es importante, ya que si no lo hiciera cortocircuito evaluate,
entonces si el árbol hace nulo igual, esta segunda condición se va a culpa seg,
porque árbol-> valor se desreferencia nula.
Así que eso es todo. ¿Puede hacer esto - cambiar una vez más.
Esto es una cosa muy común también, no hacer esta línea con esto,
pero es una cosa común en condiciones, quizás no aquí,
pero si (árbol! = NULL, y el árbol-> valor value ==), hacer lo que sea.
Esta es una condición muy común, donde en lugar de tener
a romper esto en dos ifs, donde quiera, es la nula árbol?
Bueno, no es nulo, por lo que ahora es el valor equivalente al valor del árbol? Haga esto.
En su lugar, esta condición, esto nunca falla seg
porque va a salir si esto pasa a ser nulo.
Bueno, supongo que si el árbol es un puntero nulo completamente, todavía puede seg culpa,
pero no puede seg fallo si el árbol es nulo.
Si fuera nulo, iba a estallar antes de que usted desreferencia el puntero en el primer lugar.
[Estudiante] ¿Este evaluación perezosa llamada?
>> [Bowden] La evaluación diferida es una cosa aparte.
La evaluación diferida es más como usted pide un valor,
pedirle que calcule un valor, tipo de, pero usted no lo necesita de inmediato.
Así que hasta que realmente lo necesitan, no se evalúa.
Esto no es exactamente lo mismo, pero, en el conjunto de procesadores Huffman
que dice que "perezosa", escriben.
La razón por la que hacemos esto es porque en realidad estamos amortiguación de la escritura -
no quiero escribir bits individuales a la vez,
o bytes individuales a la vez, en vez quiere conseguir un pedazo de bytes.
Luego, una vez que tenemos un fragmento de bytes, entonces vamos a escribirlo.
A pesar de que se pida a escribir - y fwrite y fread hacer el mismo tipo de cosas.
Ellos amortiguar su lectura y escritura.
A pesar de que se pida a escribir de inmediato, probablemente no lo hará.
Y no se puede estar seguro de que las cosas van a ser escritos
hasta que se llama hfclose o lo que sea,
que luego se dice, está bien, voy a cerrar mi archivo,
eso significa que será mejor que escribir todo lo que no he escrito todavía.
No tiene que escribir todo lo que fuera
hasta que se cierre el archivo y haga lo necesario.
Así que eso es justo lo vago - que espera hasta que tiene que suceder.
Esto - tomar 51 y podrás entrar en ella con más detalle,
porque OCaml y todo lo que en el 51, todo es repetición.
No existen soluciones iterativas, básicamente.
Todo es repetición, y la evaluación perezosa
va a ser importante para un montón de circunstancias
donde, si no perezosamente evaluar, eso significaría -
El ejemplo es corrientes, que son infinitamente largo.
En teoría, se puede pensar en los números naturales como una corriente de 1-2-3-4-5-6-7,
Así que las cosas están bien evaluados perezosamente.
Si digo que quiero que el décimo número, entonces puedo evaluar hasta el número diez.
Si desea que el número cien, entonces puedo evaluar hasta el número cien.
Sin la evaluación perezosa, entonces va a tratar de evaluar todos los números de inmediato.
Se está evaluando un número infinito de números, y eso no es posible.
Así que hay un montón de circunstancias en las que la evaluación perezosa
es esencial para conseguir que las cosas funcionen.
>> Ahora queremos escribir inserción insert donde va a ser
de manera similar cambiando en su definición.
Así que ahora mismo está inserto bool (int value).
Vamos a cambiar eso para insertar bool (int value, nodo de árbol *).
Estamos realmente va a cambiar de nuevo un poco, ya veremos por qué.
Y vamos a pasar build_node, sólo por el gusto de hacerlo,
por encima de insertar por lo que no tiene que escribir un prototipo de función.
Lo cual es un indicio de que se va a utilizar en build_node inserción.
Bien. Tome un minuto para eso.
Creo que me salvó la revisión si quieres tirar de eso,
o, al menos, lo hice ahora.
Yo quería un ligero corte a pensar en la lógica de la inserción,
si usted no puede pensar en él.
Básicamente, sólo alguna vez se inserta en las hojas.
Al igual que, si inserto 1, entonces estoy inevitablemente va a insertar 1 -
Voy a cambiar a negro - Estaré insertar una por aquí.
O si puedo insertar 4, quiero ser la inserción de 4 por aquí.
Así que no importa lo que hagas, vas a insertar en una hoja.
Todo lo que tienes que hacer es recorrer el árbol hasta llegar al nodo
que debe ser el padre del nodo, el padre del nuevo nodo,
y luego cambiar el puntero de izquierda o derecha, dependiendo de si
es mayor o menor que el nodo actual.
Cambiar ese puntero para apuntar a su nuevo nodo.
Así iterar hacia abajo del árbol, hacen que el punto de la hoja al nuevo nodo.
También piense por qué prohíbe el tipo de situación antes,
donde construyó el árbol binario donde estaba correcta
si sólo miró a un solo nodo,
pero el 9 estaba a la izquierda de 7 si reiterado por todo el camino.
Así que es imposible en esta situación, ya que -
pensar en la inserción de 9 o algo, en el primer nodo,
Voy a ver 7 y me voy a ir a la derecha.
Así que no importa lo que haga, si estoy yendo a la inserción de una hoja,
y a una hoja utilizando el algoritmo apropiado,
que va a ser imposible para mí para insertar 9 a la izquierda, de 7 de
porque tan pronto como me golpeó 7 Yo voy a ir a la derecha.
¿Alguien tiene algo para empezar?
[Estudiante] que hago. >> Claro.
[Estudiante, ininteligible]
[Otro estudiante, ininteligible]
[Bowden] Se aprecia. Bien. ¿Quieres explicarme?
>> [Estudiante] Ya que sabemos que estábamos insertando
nuevos nodos en el extremo del árbol,
Me envían a través del árbol de forma iterativa
hasta que llegué a un nodo que apuntaba a null.
Y entonces me decidí a poner ya sea en el lado derecho o el lado izquierdo
utilizando esta variable correcto, sino que me dijo dónde ponerlo.
Y entonces, en esencia, que acabo de hacer que el pasado -
ese punto temp nodo al nuevo nodo que se estaba creando,
ya sea en el lado izquierdo o en el lado derecho, dependiendo de lo que el valor de la derecha era.
Por último, establece el valor nuevo nodo con el valor de su prueba.
[Bowden] Está bien, así que no veo un problema aquí.
Esto es como el 95% del camino.
El único problema que veo, bueno, ¿alguien más ve un problema?
¿Cuál es la circunstancia en las que romper el lazo?
[Estudiante] Si la temperatura es nulo? Sí >>. Entonces, ¿cómo salir del bucle es si la temperatura es nulo.
Pero, ¿qué hago aquí?
Yo dereference temperatura, que es inevitablemente nulo.
Así que lo que usted tiene que hacer no es sólo un seguimiento hasta que la temperatura es nulo,
usted quiere estar al día de los padres en todo momento.
También queremos que los padres nodo *, creo que podemos mantener en nulo al principio.
Esto va a tener un comportamiento extraño en la raíz del árbol,
pero ya llegaremos a eso.
Si el valor es mayor de lo que sea, entonces temp = temp derecha.
Pero antes de hacer eso, padre temp =.
¿O los padres siempre van a temp iguales? ¿Es ese el caso?
Si la temperatura no es nulo, entonces yo voy a bajar, no importa qué,
a un nodo para el que la temperatura es el padre.
Así que los padres va a ser temporal, y luego me muevo por temp.
Ahora la temperatura es nulo, pero señala a los padres de los padres de lo que es nulo.
Así que aquí, no quiero establecer derecha es igual a 1.
Así que me mudé a la derecha, por lo que si la derecha = 1,
y supongo que también quieren hacer -
si se mueve hacia la izquierda, que desea establecer el derecho igual a 0.
O bien, si alguna vez se mueven hacia la derecha.
Así derecha = 0. Si la derecha = 1,
ahora queremos que el padre nodo_nuevo puntero derecho,
otra cosa que quiere hacer el padre nodo_nuevo puntero izquierdo.
Las preguntas sobre eso?
Bien. Así que esta es la forma en que - bueno, en realidad, en lugar de hacer esto,
Casi esperaba que usted utilice build_node.
Y luego, si es igual nodo_nuevo nulo, devuelve falso.
Eso es todo. Ahora bien, esto es lo que esperábamos que hiciera.
>> Esto es lo que las soluciones de personal hacer.
No estoy de acuerdo con esto como la manera "correcta" de hacer las cosas
pero esto está perfectamente bien y va a funcionar.
Una cosa que es un derecho poco raro ahora es
si el árbol comienza como nulo, se pasa en un árbol nulo.
Supongo que depende de cómo se defina el comportamiento del pasajero en un árbol nulo.
Me gustaría pensar que si se pasa un árbol nulo,
a continuación, insertar el valor NULL en un árbol
sólo debe devolver un árbol en el que el único valor es que solo nodo.
¿Las personas están de acuerdo con eso? Usted puede, si quiere,
si se pasa un árbol nulo
y desea insertar un valor en él, devuelve falso.
Depende de usted para definir eso.
Para ello lo primero que me dijo y luego -
así, vas a tener problemas para hacer eso, porque
sería más fácil si tuviéramos un puntero global a la cosa,
pero no, por lo que si el árbol es nulo, no hay nada que podamos hacer al respecto.
Sólo puede devolver false.
Así que me voy a cambiar de inserción.
Nos técnicamente podría cambiar esto de aquí,
cómo se itera sobre las cosas,
pero yo voy a cambiar de inserción para tomar un nodo de árbol. **
Punteros dobles.
¿Qué quiere decir esto?
En lugar de tratar con punteros a nodos,
lo que voy a estar manipulando es este puntero.
Voy a estar manipulando este puntero.
Voy a estar manipulando directamente los punteros.
Esto tiene sentido ya que, pensar hacia abajo -
Bueno, ahora esto apunta a null.
Lo que quiero hacer es manipular este puntero para apuntar a no nulo.
Quiero que apunte a mi nuevo nodo.
Si tan sólo realizar un seguimiento de los punteros a mis consejos,
entonces no es necesario hacer un seguimiento de un puntero padres.
Acabo de hacer un seguimiento para ver si el puntero apunta a null,
y si el puntero apunta a null,
cambiar para que apunte al nodo que quiero.
Y puedo cambiar ya que tengo un puntero al puntero.
Vamos a ver esto ahora mismo.
En realidad se puede hacer de forma recursiva con bastante facilidad.
¿Queremos hacerlo?
Sí, lo hacemos.
>> Vamos a ver de forma recursiva.
En primer lugar, ¿cuál es nuestro caso base va a ser?
Casi siempre nuestro caso base, pero en realidad, esto es un poco complicado.
Lo primero es lo primero, si (árbol == NULL)
Supongo que sólo va a devolver false.
Esto es diferente de su nula árbol bienestar.
Este es el puntero al puntero raíz siendo nula
lo que significa que el puntero de su raíz no existe.
Así que aquí, si lo hago
* nodo - vamos a volver a usar esto.
Nodo * root = NULL,
y luego me voy a llamar a insertar haciendo algo como:
insertar y 4 en la raíz.
Así y raíz, si la raíz es un nodo *
y entonces la raíz va a ser un ** nodo.
Esto es válido. En este caso, el árbol, hasta aquí,
árbol no es nulo - o inserción.
Aquí. Tree no es nulo; árbol * es nulo, lo cual está bien
porque si el árbol * es nulo, entonces puedo manipular
apuntar ahora a lo que yo quiero que apuntar.
Pero si el árbol es nulo, eso significa que sólo vine aquí y me dijo nulo.
Eso no tiene sentido. No puedo hacer nada con eso.
Si el árbol es nulo, devuelve falso.
Así que, básicamente, lo que ya ha dicho nuestro caso base real.
Y lo que es que va a ser?
[Estudiante, ininteligible]
[Bowden] Sí. Así que si (* arbol == NULL).
Esto se relaciona con el caso aquí
donde si mi puntero rojo es el puntero que estoy enfocado,
así que estoy centrado en este indicador, ahora estoy centrado en este indicador.
Ahora estoy centrado en este indicador.
Así que si mi puntero rojo, que es mi ** nodos,
es cada vez - si *, mi puntero rojo, es siempre nulo,
eso significa que estoy en el caso de que me voy a centrar en un puntero que apunta -
este es un puntero que pertenece a una hoja.
Quiero cambiar este puntero para apuntar a mi nuevo nodo.
Vuelve por aquí.
Mi nodo_nuevo sólo será nodo * n = build_node (valor)
entonces n, si n = NULL, devuelve falso.
Otras ventas que queremos cambiar lo que el puntero apunta actualmente
apuntar ahora a nuestro nodo de nueva construcción.
De hecho, podemos hacer eso aquí.
En lugar de decir n, decimos árbol * = si el árbol *.
Todo el mundo entiende eso? Eso negociando con punteros a punteros,
podemos cambiar punteros nulos para apuntar a las cosas que queremos que apuntar.
Ese es nuestro caso base.
>> Ahora nuestro recurrencia, o nuestra recursividad,
va a ser muy similar a todos los otros recurrencias que hemos estado haciendo.
Vamos a querer insertar un valor,
y ahora yo voy a usar de nuevo ternario, pero lo que es nuestra condición va a ser?
¿Qué es lo que estamos buscando para decidir si queremos ir a la izquierda oa la derecha?
Vamos a hacerlo en pasos separados.
Si (valor <) qué?
[Estudiante] El valor del árbol?
[Bowden] Así que recuerde que soy en la actualidad -
[Los estudiantes], ininteligibles
[Bowden] Sí, tan bien aquí, vamos a decir que esta flecha verde
es un ejemplo de lo que actualmente es árbol, es un puntero al puntero.
Así que eso significa que soy un puntero a un puntero a 3.
El dereference dos veces sonaba bien.
¿Qué - ¿cómo puedo hacer eso?
[Estudiante] eliminar la referencia una vez, y luego hacer flecha de esa manera?
[Bowden] Entonces (árbol *) es la eliminación de referencias una vez, -> valor
me va a dar el valor del nodo que estoy señalando indirectamente.
Así que también se puede escribir ** tree.value si lo prefiere eso.
Cualquiera de las obras.
Si ese es el caso, entonces quiero llamar a insertar con valor.
Y lo que es mi nodo actualizado ** va a ser?
Yo quiero ir a la izquierda, por lo que arbol.izquierdo ** va a ser mi izquierda.
Y quiero que el puntero a esa cosa
de modo que si la izquierda termina siendo el puntero nulo,
Puedo modificar para apuntar a mi nuevo nodo.
>> Y el otro caso puede ser muy similar.
Vamos a hacer que mi realidad ternario en estos momentos.
Inserte valor si el valor <(árbol **). Valor.
Entonces queremos actualizar nuestros ** a la izquierda,
más queremos actualizar nuestros ** a la derecha.
[Estudiante] ¿Eso obtener el puntero al puntero?
[Bowden] Recuerde que - ** arbol.derecho es una estrella nodo.
[Estudiante, ininteligible] >> Si.
** Arbol.derecho es como este puntero o algo así.
Así, tomando un puntero a eso, que me da lo que quiero
del puntero a ese tipo.
[Estudiante] Podríamos ir otra vez por qué estamos utilizando los dos punteros?
[Bowden] Yeah. Por lo tanto - no, usted puede, y la solución que antes
Era una manera de hacerlo sin tener que hacer dos punteros.
Tiene que ser capaz de entender el uso de dos punteros,
y esta es una solución más limpia.
Además, observe que, ¿qué pasa si mi árbol -
¿qué pasa si mi raíz era nulo? ¿Qué pasa si no hago este caso aquí?
Así nodo * root = NULL, insertar y 4 en la raíz.
¿Qué es la raíz va a ser después de esto?
[Estudiante, ininteligible] >> Si.
Valor de la raíz va a ser 4.
Raíz izquierda va a ser nulo, derecho fundamental va a ser nulo.
En el caso en el que no pasó raíz de dirección,
no podíamos modificar raíz.
En el caso de que el árbol - donde la raíz era nulo,
nos tuvimos que devolver false. No hay nada que pudiéramos hacer.
No se puede insertar un nodo en un árbol vacío.
Pero ahora sí, acabamos de hacer un árbol vacío en un árbol de un nodo.
Lo cual es generalmente la manera esperada que se supone que debe funcionar.
>> Además, éste es significativamente más corto que
también hacer el seguimiento de los padres, y por lo que iterar hacia abajo todo el camino.
Ahora tengo a mi padre, y yo sólo tengo mi puntero derecho del padre a lo que sea.
En cambio, si hacemos esto iterativa, que sería la misma idea con un bucle while.
Pero en lugar de tener que lidiar con mi padre puntero,
mi lugar actual del puntero sería lo
que estoy modificando directamente para apuntar a mi nuevo nodo.
Yo no tengo que lidiar con el hecho de que apunta hacia la izquierda.
Yo no tengo que lidiar con el hecho de que apunta hacia la derecha.
Es sólo lo que este indicador es que me voy a fijar para que apunte a mi nuevo nodo.
Todo el mundo entiende cómo funciona?
Si no es así ¿por qué queremos hacerlo de esta manera,
pero al menos que esto funciona como una solución?
[Estudiante] ¿Dónde return true?
[Bowden] Eso es probablemente justo aquí.
Si se inserta correctamente, devuelve true.
Si no, aquí vamos a querer volver a lo que sea retornos de inserción.
>> ¿Y qué tiene de especial esta función recursiva?
Es la cola recursiva, por lo que mientras se compila con un poco de optimización,
reconocerá y que nunca se tiene un desbordamiento de pila de esto,
incluso si nuestro árbol tiene una altura de 10.000 millones o 10.
[Estudiante, ininteligible]
[Bowden] Creo que lo hace a Dash - o qué nivel de optimización
se requiere para una recursión de cola para ser reconocido.
Creo que lo reconoce - GCC y Clang
También tienen diferentes significados para sus niveles de optimización.
Quiero decir que es DashO 2, para asegurarse de que se reconozca la recursión de cola.
Pero - se puede construir como un ejemplo Fibonocci o algo así.
No es fácil de probar con esto, porque es difícil construir
un árbol binario que es tan grande.
Pero sí, creo que es DashO 2, que
si se compila con DashO 2, se buscará la recursión de cola
y optimizar eso.
Volvamos a - insertar, literalmente, la última cosa que necesita.
Volvamos a la inserción de aquí
donde vamos a hacer la misma idea.
Todavía tendremos el defecto de no ser capaz de manejar todo
cuando la misma raíz es nulo, o el pasado entrada es nulo,
pero en lugar de tratar con un puntero padre,
vamos a aplicar la misma lógica de los punteros a punteros de mantenimiento.
Si aquí seguimos nuestro nodo ** cur,
y no es necesario hacer un seguimiento de la derecha más,
pero nodo ** act = & árbol.
Y ahora nuestro bucle while va a ser mientras act * no nula de igualdad.
No es necesario hacer un seguimiento de los padres más.
No es necesario hacer un seguimiento de izquierda y derecha.
Y lo voy a llamar a la temperatura, porque ya estamos usando temp.
Bien. Así que si (valor> * temp),
y entonces (* temp) -> derecha
más temp = & (* temp) -> a la izquierda.
Y ahora, en este punto, después de este bucle while,
Yo sólo hago esto porque tal vez es más fácil pensar en forma iterativa de forma recursiva,
pero después de este bucle while,
* Temp es el puntero que desea cambiar.
>> Antes de tener padres, y queríamos cambiar hacia la izquierda padre o padres derecha,
pero si queremos cambiar derechos de los padres,
entonces es correcto * temp padre, y podemos cambiarlo directamente.
Así que aquí, podemos hacer * temp = nodo_nuevo, y eso es todo.
Así que aviso, todo lo que hicimos en esta era sacar líneas de código.
Con el fin de seguir la pista de la matriz en todo lo que es esfuerzo adicional.
En este caso, si tan sólo no perder de vista el puntero al puntero,
e incluso si quería deshacerse de todas estas llaves ahora,
hacer que se vea más corto.
Esta es la misma solución exacta,
pero menos líneas de código.
Una vez que empezar a reconocer esto como una solución válida,
también es más fácil de razonar acerca de que como, bien,
¿por qué tengo esta bandera a la derecha int?
¿Qué significa eso? Oh, está significando que
cada vez que vaya a la derecha, tengo que ponerlo,
else if I a la izquierda tengo que ponerlo a cero.
En este caso, no tengo la razón en eso, es más fácil que pensar.
¿Preguntas?
[Estudiante, ininteligible] >> Si.
Está bien, así que en el último -
Supongo que una función rápida y fácil que podemos hacer es,
let's - junto, creo, tratar de escribir una función contains
que no le importa si se trata de un árbol de búsqueda binaria.
Contiene función debe devolver true
si cualquier parte de este árbol binario general es el valor que está buscando.
Así que primero vamos a hacerlo de forma recursiva y luego lo haremos iterativa.
De hecho, podemos simplemente hacerlo juntos, porque esto va a ser muy corta.
>> ¿Cuál es mi hipótesis de base va a ser?
[Estudiante, ininteligible]
[Bowden] Así que si (árbol == NULL), ¿entonces qué?
[Estudiante] Volver falso.
[Bowden] Si no, bueno, yo no necesito el otro.
Si fue mi caso otra base.
Valor [Estudiante] Tree? Sí >>.
Así que si (árbol-> value value ==.
Tenga en cuenta que estamos de vuelta a * nodo no, nodo ** s?
Contiene nunca tendrá que usar un ** nodos,
ya que no estamos modificando punteros.
Estamos atravesando ellos.
Si eso sucede, entonces queremos volver realidad.
Otras ventas que queremos recorrer los niños.
Así que no podemos razonar acerca de si todo a la izquierda es menor
y todo a la derecha es mayor.
Entonces, ¿cuál es nuestro estado va a estar aquí - o, ¿qué vamos a hacer?
[Estudiante, ininteligible] >> Si.
Volver contiene (valor, árbol-> izquierdo)
o contiene (valor, árbol-> derecha). Y eso es todo.
Y cuenta de que hay algún tipo de evaluación de corto circuito,
donde si nos toca encontrar el valor en el árbol de la izquierda,
que nunca necesitamos mirar el árbol de la derecha.
Esa es la función entera.
Ahora vamos a hacerlo iterativamente,
que va a ser menos agradable.
Vamos a tomar la salida habitual de nodo * act = árbol.
Mientras (act! = NULL).
Rápidamente vamos a ver un problema.
Si act - aquí, si alguna vez salir de esto,
entonces nos hemos quedado sin cosas que ver, por lo que devuelve falso.
Si (act-> valor value ==), devuelve true.
Así que ahora, estamos en un lugar -
no sabemos si queremos ir a la izquierda oa la derecha.
Por lo tanto arbitrariamente, vamos a ir a la izquierda.
Obviamente he topado con un problema en el que me he abandonado por completo todo -
Sólo voy a comprobar siempre el lado izquierdo de un árbol.
Nunca se compruebe todo lo que es un hijo derecho a nada.
¿Cómo puedo solucionar este problema?
[Estudiante] Hay que seguir la pista de la izquierda y la derecha en una pila.
[Bowden] Yeah. Así que vamos a hacerlo
struct lista nodo * n, y luego nodo ** siguiente?
Yo creo que funciona bien.
Queremos ir por la izquierda o let's - hasta aquí.
Struct = lista de la lista, que va a empezar
a cabo en esta lista struct.
* Lista = NULL. Así que va a ser nuestra lista enlazada
de subárboles que hemos saltado.
Vamos a atravesar la izquierda ahora,
pero es inevitable que tenga que volver a la derecha,
Vamos a mantener el lado derecho dentro de nuestra lista de estructura.
Entonces tendremos new_list o estructura,
struct lista *, new_list = malloc (sizeof (lista)).
Voy a pasar por alto la comprobación de errores, pero usted debe comprobar para ver si es nulo.
New_list el nodo que va a apuntar a -
oh, es por eso que lo quería aquí. Se va a apuntar a una lista struct segundo.
Así es como el trabajo vinculado listas.
Este es el mismo como una lista vinculada int
excepto sólo estamos reemplazando con int * nodo.
Es exactamente lo mismo.
Así new_list, el valor de nuestro nodo new_list,
va a ser actual-> derecha.
El valor de nuestra new_list-> siguiente va a ser nuestra lista original,
y luego vamos a actualizar nuestra lista para apuntar a new_list.
>> Ahora necesitamos algún tipo de forma de las cosas que tiran,
como hemos atravesado el subárbol izquierdo entero.
Ahora tenemos que tirar cosas fuera de él,
como act es nulo; no queremos volver simplemente falso.
Queremos tirar ahora fuera de nuestra nueva lista.
Una manera conveniente de hacer esto - bueno, en realidad, hay varias maneras de hacer esto.
¿Alguien tiene alguna sugerencia?
¿Dónde debo hacer esto o cómo debo hacerlo?
Sólo tenemos un par de minutos, pero cualquier sugerencia?
En lugar de - de una manera, en vez de nuestra condición de ser tiempo,
lo que estamos mirando no es nulo,
en lugar de eso vamos a seguir para ir hasta nuestra lista en sí es nulo.
Así que si nuestra lista termina siendo nulo,
entonces nos hemos quedado sin cosas que debe buscar, a buscar otra vez.
Pero eso significa que lo primero en nuestra lista es sólo va a ser el primer nodo.
Lo primero será - ya no tenemos que ver eso.
Así lista-> n será nuestro árbol.
lista-> siguiente va a ser nulo.
Y ahora, mientras que la lista no nula de igualdad.
Cur va a sacar algo de nuestra lista.
Así act va a igual list-> n.
Y entonces lista va a igual list-> n, o lista-> siguiente.
Así que si el valor es igual al valor act.
Ahora podemos añadir tanto los nuestros como puntero derecho y nuestro puntero izquierdo
siempre y cuando no es nulo.
Aquí abajo, supongo que deberíamos haber hecho eso en primer lugar.
Si (act-> bien! = NULL)
entonces vamos a insertar el nodo en la lista.
Si (act-> izquierda), se trata de un poco de trabajo extra, pero está bien.
Si (act-> izquierda! = NULL),
y vamos a insertar a la izquierda en nuestra lista enlazada,
y que debería ser.
Nos iterar - siempre y cuando tenemos algo en nuestra lista,
tenemos otro nodo a la vista.
Así que nos fijamos en ese nodo,
avanzamos nuestra lista para la siguiente.
Si el nodo es el valor que buscamos, podemos volver realidad.
Otras ventas insertar ambos subárboles nuestra izquierda y la derecha,
siempre y cuando no sean nulos, en la lista
de modo que es inevitable ir sobre ellos.
Así que si no eran nulas,
si nuestro puntero raíz señaló dos cosas,
a continuación, al principio nos sacó algo por lo que nuestra lista termina siendo nulo.
Y luego ponemos dos cosas de nuevo, por lo que ahora nuestra lista es de tamaño 2.
A continuación, vamos a tejer por atrás y sólo vamos a tirar,
digamos, el puntero izquierdo de nuestro nodo raíz.
Y eso va a seguir ocurriendo, vamos a terminar recorrer todo.
>> Observe que esto era significativamente más complicado
en la solución recursiva.
Y ya he dicho varias veces
que la solución recursiva por lo general tiene mucho en común con la solución iterativa.
Aquí es exactamente lo que la solución recursiva está haciendo.
El único cambio es que en lugar de utilizar implícitamente la pila, la pila del programa,
como su forma de hacer el seguimiento de qué nodos usted todavía tiene que visitar,
Ahora usted tiene que utilizar explícitamente una lista enlazada.
En ambos casos, usted está guardando un registro de lo nodo todavía tiene que ser visitado.
En el caso recursivo es más fácil porque una pila
que se aplique a usted como la pila del programa.
Observe que esta lista enlazada, es una pila.
Independientemente de lo que acaba de poner en la pila
es inmediatamente lo que vamos a quitar la pila para la próxima visita.
Estamos fuera de tiempo, pero alguna pregunta?
[Estudiante, ininteligible]
[Bowden] Yeah. Así que si tenemos nuestra lista enlazada,
actual se va a apuntar a este chico,
y ahora estamos avanzando a nuestra lista enlazada para centrarse en este tipo.
Estamos atravesando por la lista enlazada en esa línea.
Y entonces creo que debemos liberar nuestra lista enlazada y esas cosas
una vez antes de regresar verdadera o falsa, tenemos que
iterar a través de nuestra lista enlazada y siempre aquí abajo, supongo,
si act derecho no es igual que agregar, por lo que ahora queremos liberar
act porque, bueno, qué nos olvidamos por completo de la lista? Si.
Así que eso es lo que queremos hacer aquí.
¿Dónde está el puntero?
Cur era entonces - queremos una lista struct * 10 es igual a la lista siguiente.
Lista libre, list = temp.
Y en el caso de que nos devuelva true, necesitamos iterar
durante el resto de nuestra lista enlazada liberar cosas.
Lo bueno de la solución recursiva es liberar a las cosas
Sólo significa factorings apareciendo de la pila que va a suceder para usted.
Así que hemos pasado de algo que es como 3 líneas de duro-a-pensar-sobre el código
a algo que es significativamente muchos más difíciles de pensamiento acerca de las líneas de código.
Algo más preguntas?
Está bien. Estamos bien. Bye!
[CS50.TV]