[Powered by Google Translate] [Artículo 7] [Menos Cómodo] [Nate Hardison] [Harvard University] [Esta es CS50.] [CS50.TV] 

Bienvenido a la Sección 7. Gracias a huracán de arena, en lugar de tener una sección normal de esta semana, estamos haciendo este recorrido, a través de la sección de preguntas. Voy a estar siguiendo junto con el boletín de problemas 6 Especificación, y pasando por todas las preguntas de la Una sección de la sección de Preguntas. Si hay alguna pregunta, por favor, publicarlo en estos CS50 discutir. 

Muy bien. Vamos a empezar. En este momento estoy buscando en la página 3 de la Especificación de problemas. Vamos a empezar a hablar primero sobre árboles binarios ya que éstos tienen una gran relevancia para conjunto de problemas de esta semana - la codificación del árbol de Huffman. Una de las estructuras de datos muy primero hablamos sobre CS50 fue el arreglo. Recuerde que una matriz es una secuencia de elementos - todas del mismo tipo - almacena uno al lado del otro en la memoria. Si tengo una matriz de enteros que puedo dibujar con este estilo de cajas-numbers-números enteros - Digamos que tengo 5 en la primera casilla, tengo 7 en el segundo, entonces tienen 8, 10, y 20 en el cuadro final. Recuerde las cosas, los dos realmente buenas de esta matriz es que tenemos este acceso constante a tiempo a cualquier elemento particular  en la matriz si se sabe que su índice. Por ejemplo, si quiero agarrar el tercer elemento de la matriz - en el índice 2 usando nuestra base cero sistema de indexación - Yo, literalmente, sólo hay que hacer un cálculo matemático simple, saltar a la posición en la matriz, saque el 8 que esté almacenado, y estoy listo para salir. 

Una de las cosas malas de este conjunto - que hablamos cuando hablamos de listas enlazadas - es que si desea insertar un elemento en el array, Voy a tener que hacer algún cambio a su alrededor. Por ejemplo, esta matriz aquí está en el orden establecido - en orden ascendente - 5, a continuación, 7, 8 y luego, a continuación, 10, y luego 20 - pero si lo desea insertar el número 9 en esta matriz, Voy a tener que cambiar algunos de los elementos con el fin de hacer espacio. Podemos extraer esta aquí. Voy a tener que mover el 5, el 7 y luego la 8; crear un espacio donde puedo poner el 9, y luego el 10 y el 20 puede ir a la derecha de la 9. Este es un tipo de dolor porque en el peor de los casos - cuando estamos tener que insertar ya sea al principio o al final de la matriz, en función de cómo estamos cambiando - podríamos llegar a tener que cambiar todos los elementos que actualmente estamos almacenando en la matriz. 

Entonces, ¿cuál era la forma de evitar esto? La forma de evitar esto era ir a nuestro método de lista enlazada, donde - en lugar de almacenar los elementos 5, 7, 8, 10 y 20 todos uno al lado del otro en la memoria - lo que en su lugar se les estaba almacenar especie de donde queríamos para almacenarlos en estos nodos de la lista enlazada que estoy dibujando aquí, un poco ad hoc. Y entonces ellos conectados entre sí mediante estos indicadores siguientes. Puedo tener un puntero del 5 al 7 de un triple desde la 7 a la 8, un triple desde la 8 a la 10, y por último, un triple desde la 10 a la 20, y luego un puntero nulo en los años 20 lo que indica que no hay nada a la izquierda. La disyuntiva que tenemos aquí es que ahora si queremos insertar el número 9 en la lista ordenada, todo lo que tenemos que hacer es crear un nuevo nodo con 9, cablear hacia arriba para que apunte al lugar adecuado, y luego re-cableado del 8 al apuntar hacia abajo a la 9. Eso es bastante rápido, en el supuesto que sabemos exactamente donde queremos insertar el 9. Pero la compensación a cambio de esto es que hemos perdido el acceso constante de tiempo a cualquier elemento particular en nuestra estructura de datos. Por ejemplo, si quiero encontrar el cuarto elemento en esta lista enlazada, Voy a tener que empezar desde el principio de la lista y trabajar a mi manera a través de contar nodo por nodo hasta que encuentre el cuarto. 

Con el fin de obtener un mejor rendimiento de acceso de una lista enlazada - pero también retienen algunas de las ventajas que teníamos en términos de inserción a tiempo de una lista enlazada - un árbol binario se va a tener que utilizar la memoria un poco más. En particular, en lugar de sólo tener un puntero a un nodo de árbol binario - al igual que la lista enlazada de nodos hace - vamos a añadir un segundo puntero para el nodo del árbol binario. En lugar de tener un puntero al siguiente elemento, vamos a tener un puntero a un hijo izquierdo y un hijo derecho. 

Vamos a hacer un dibujo para ver lo que realmente parece. Una vez más, voy a utilizar estas cajas y flechas. Un nodo del árbol binario a empezar con sólo una caja simple. Va a tener un espacio para el valor, y entonces también va a tener un espacio para que el hijo izquierdo y el hijo derecho. Voy a etiquetarlos aquí. Vamos a tener el hijo izquierdo, y luego nos vamos a tener el hijo derecho. Hay muchas maneras diferentes de hacer esto. A veces por espacio y comodidad, De hecho, me voy a dibujar como que estoy haciendo aquí en la parte inferior donde yo voy a tener el valor en la parte superior, y entonces el niño a la derecha en la parte inferior derecha, y el hijo izquierdo en la parte inferior izquierda. Volviendo a este diagrama superior, tenemos el valor en la parte superior, entonces tenemos el puntero izquierdo-hijo, y entonces tenemos el puntero derecho del niño. 

En la especificación del conjunto de problemas, se habla de la elaboración de un nodo que tiene un valor de 7, y luego un puntero izquierdo niño que es nulo, y un puntero derecho del niño que es nulo. Podemos escribir NULL capital en el espacio para tanto el hijo izquierdo y el hijo derecho, o podemos sacar esta barra diagonal a través de cada una de las casillas para indicar que es nulo. Voy a hacer eso sólo porque es más simple. Lo que se ve aquí son dos formas de diagramación de un nodo de árbol binario muy sencillo donde tenemos el valor 7 y punteros nulos infantil. 

La segunda parte de nuestras conversaciones con las especificaciones acerca de cómo las listas enlazadas - recuerde, sólo tuvimos que esperar al primer elemento de una lista para recordar toda la lista - y del mismo modo, con un árbol binario, sólo tenemos que aguantar a un puntero al árbol con el fin de mantener el control sobre la estructura de datos completa. Este elemento especial del árbol se denomina nodo raíz del árbol. Por ejemplo, si este nodo de uno - este nodo que contiene el valor 7 con punteros nulos izquierda y derecha para niños - eran el único valor en nuestro árbol, entonces este sería nuestro nodo raíz. Es el comienzo mismo de nuestro árbol. Podemos ver esto un poco más clara una vez que comience a añadir más nodos a nuestro árbol. Déjame sacar una nueva página. 

Ahora vamos a dibujar un árbol que tiene 7 en la raíz, y 3 dentro de la hijo izquierdo, y 9 en el interior de el hijo derecho. Una vez más, esto es bastante simple. Tenemos 7, dibuje un nodo para el 3, un nodo 9, y yo voy a poner el puntero izquierdo niño de 7 a apuntar al nodo que contiene 3, y el puntero derecho del hijo del nodo que contiene 7 al nodo que contiene 9. Ahora, desde el 3 y 9 no tienen hijos, vamos a hacer que todos los punteros a sus hijos a ser nulo. Aquí, la raíz de nuestro árbol corresponde al nodo que contiene el número 7. Se puede ver que si todo lo que tenemos es un puntero a ese nodo raíz, entonces podemos caminar a través de nuestro árbol y acceder a ambos nodos secundarios - ambos 3 y 9. No es necesario mantener los punteros a cada nodo en el árbol. Muy bien. Ahora vamos a agregar un nodo a este diagrama. Vamos a añadir un nodo que contiene 6, y vamos a añadir esto como el hijo derecho del nodo que contiene 3. Para hacer eso, voy a borrar ese puntero nulo en el 3-nodo y cablear para que apunte al nodo que contiene 6. Muy bien. 

En este punto, vamos a repasar un poco de la terminología. Para empezar, la razón por la que esto se llama un árbol binario en particular es que tiene dos punteros niño. Hay otros tipos de árboles que tienen más punteros del niño. En particular, se hizo un 'try' en Boletín de problemas 5. Se dará cuenta de que en ese intento, que tuvo 27 punteros diferentes para diferentes niños - uno para cada una de las 26 letras en el alfabeto Inglés, y luego el día 27 para el apóstrofe - es así, que es similar a un tipo de árbol. Pero aquí, ya que es binario, sólo tenemos dos punteros del niño. 

Además de este nodo raíz que hemos hablado, también hemos estado lanzando en torno a este término "niño". ¿Qué significa para un nodo a ser un hijo de otro nodo? Es, literalmente, significa que un nodo hijo es un hijo de otro nodo si otro nodo que tiene una de sus punteros de niños fijan para apuntar a ese nodo. Para ponerlo en términos más concretos, si 3 es apuntado por uno de los punteros de niño de 7, entonces 3 es un niño de 7. Si tuviéramos que entender lo que los niños de 7 son - así, vemos que 7 tiene un puntero a 3 y un puntero a 9, lo 9 y 3 son hijos de 7. Nueve no tiene hijos, porque sus hijos son punteros nulos, y 3 sólo tiene un hijo de 6. Seis tampoco tiene hijos, porque sus dos punteros son nulos, lo que vamos a llamar ahora mismo. 

Además, también hablamos de los padres de un nodo en particular, y esto es, como era de esperar, el reverso de esta descripción niño. Cada nodo tiene un solo padre - en lugar de dos como se podría esperar de los seres humanos. Por ejemplo, la matriz de 3 es 7. El padre de 9 es también 7, y el padre de 6 es 3. No hay mucho a ella. También tenemos términos para hablar de los abuelos y los nietos, y en general se habla de los antepasados y descendientes de un nodo en particular. El ancestro de un nodo - o antepasados, más bien, de un nodo - son todos los nodos que se encuentran en el camino desde la raíz a ese nodo. Por ejemplo, si estoy buscando en el nodo 6, entonces los antepasados ​​va a ser a la vez 3 y 7. Los antepasados ​​de 9, por ejemplo, son - si estoy buscando en el nodo 9 - entonces el antepasado de 9 es sólo 7. Y descendientes son exactamente lo contrario. Si desea ver todos los descendientes de 7, entonces tengo que mirar a todos los nodos que dependen de ella. Por lo tanto, tengo 3, 9, y 6 todos como hijos de 7. 

El plazo final que vamos a hablar es de esta noción de ser un hermano. Hermanos - algo siguiendo a lo largo de estos términos familias - son nodos que están en el mismo nivel en el árbol. Así, 3 y 9 son hermanos porque están en el mismo nivel en el árbol. Ambos tienen el mismo padre, 7. El 6 no tiene hermanos porque 9 no tengo hijos. Y 7 no tiene hermanos, porque es la raíz de nuestro árbol, y sólo hay siempre una raíz. Para tener 7 hermanos no tendría que ser un nodo por encima de 7. No tendría que ser una matriz de 7, en cuyo caso 7 ya no sería la raíz del árbol. Luego de que los padres nuevos de 7 también tendría que tener un hijo, y que niño sería entonces el hermano de 7. 

Muy bien. Cambiando de tema. Cuando comenzamos nuestra discusión de los árboles binarios, hablamos de lo que íbamos a utilizar para obtener una ventaja sobre ambas matrices y listas enlazadas. Y la forma en que vamos a hacerlo es con esta propiedad pedido. Se dice que un árbol binario es ordenado, de acuerdo con la especificación, si para cada nodo en nuestro árbol, todos sus descendientes de la izquierda - el hijo de la izquierda y todos los descendientes del hijo izquierdo - tienen valores menores, y todos los nodos de la derecha - el hijo derecho y todos los descendientes de los hijos de derecho - tienen nodos mayores que el valor del nodo actual que estamos viendo. Sólo para simplificar, vamos a suponer que no hay nodos duplicados en nuestro árbol. Por ejemplo, en este árbol no vamos a tratar el caso donde tenemos el valor 7 en la raíz  y luego también tenemos el valor 7 en otro lugar en el árbol. En este caso, se dará cuenta de que este árbol es de hecho ordenado. Tenemos el valor 7 en la raíz. Todo a la izquierda de 7 - si puedo deshacer todas estas pequeñas marcas aquí - todo a la izquierda de 7 - el 3 y el 6 - esos valores se encuentran a menos de 7, y todo a la derecha - - que es precisamente este 9 es mayor que 7. 

Este no es el único árbol ordenado que contiene estos valores, pero vamos a hacer un poco más de ellos. En realidad, hay un montón de maneras en que podemos hacer esto. Voy a usar un atajo sólo para mantener las cosas simples donde - en vez de extraer la totalidad cajas y flechas - Yo sólo voy a dibujar los números y agregar flechas conectan. Para empezar, sólo tendremos que escribir nuestro árbol original de nuevo donde teníamos 7, y luego un 3, y luego 3 señaló de nuevo a la derecha a la 6, y 7 tuvieron un hijo derecho que tenía 9 años. Muy bien. ¿De qué otra manera que no podamos escribir este árbol? En vez de tener 3 será el hijo izquierdo de 7, También podría tener el 6 ser el hijo izquierdo de 7, y luego 3 será el hijo izquierdo de la 6. Eso se parecería a este árbol aquí donde tengo 7, luego 6, luego 3, y un 9 a la derecha. Tampoco tiene que tener 7 como nuestro nodo raíz. También podría tener 6 como nuestro nodo raíz. ¿Qué se ve? Si vamos a mantener este inmueble ordenado, todo a la izquierda de la 6 tiene que ser menor que ella. Sólo hay una posibilidad, y eso es 3. Pero entonces, como el hijo derecho de 6, tenemos dos posibilidades. En primer lugar, podríamos tener el 7 y luego el 9, o podríamos llamar - que estoy a punto de hacer aquí - donde tenemos el 9 como el hijo derecho de la 6, y luego el 7 como el hijo izquierdo de la 9. 

Ahora, 7 y 6 no son los únicos valores posibles de la raíz. También podríamos tener 3 en la raíz. ¿Qué sucede si 3 es la raíz? Aquí, las cosas se ponen un poco más interesante. Tres no tiene valores que son menores de lo que, de modo que todo el lado izquierdo del árbol es sólo va a ser nulo. No va a ser nada allí. A la derecha, podríamos enumerar las cosas en orden ascendente. Podríamos tener 3, luego 6, luego 7, luego 9. O bien, podemos hacer 3, luego 6, luego 9, luego 7. O bien, podemos hacer 3, luego 7, luego 6, luego 9. O, 3, 7 - en realidad no, no podemos hacer un 7 más. Esa es nuestra única cosa allí. Podemos hacer 9, y luego desde el 9 podemos hacer 6 y 7. O bien, podemos hacer 3, luego 9, luego 7 y luego 6. 

Una cosa para llamar su atención aquí es que estos árboles son un poco de aspecto extraño. En particular, si nos fijamos en los cuatro árboles en el lado derecho - Voy a rodearlos, aquí - estos árboles se ven casi exactamente igual que una lista enlazada. Cada nodo tiene un solo hijo, por lo que no tiene ninguno de esta estructura en forma de árbol que vemos, por ejemplo,  en este árbol un solitario aquí en la parte inferior izquierda. Estos árboles se llama en realidad degenerada árboles binarios, y vamos a hablar de estos más en el futuro - especialmente si usted va a tomar otros cursos de ciencias de la computación. Estos árboles son degenerados. No son muy útiles porque, en efecto, esta estructura se presta  para buscar tiempos similares a la de una lista enlazada. No conseguimos aprovechar la memoria adicional - este puntero extra - porque de nuestra estructura de ser malo de esta manera. En vez de seguir adelante y sacar los árboles binarios que tienen 9 en la raíz, que es el caso final que tendría, estamos en cambio, en este punto, vamos a hablar un poco acerca de este otro término que utilizamos cuando hablamos de árboles, que se llama la altura. 

La altura de un árbol es la distancia desde la raíz hasta el nodo más distante, o más bien el número de saltos que se tendría que hacer a fin de comenzar desde la raíz y luego terminan en el nodo más lejano en el árbol. Si nos fijamos en algunos de estos árboles que hemos dibujado aquí, podemos ver que si tomamos este árbol en la esquina superior izquierda y empezamos a 3, entonces tenemos que hacer un salto para llegar a la 6, un segundo salto para llegar a los 7, y una tercera hop para llegar a la 9. Así, la altura de este árbol es 3. Podemos hacer el mismo ejercicio para los otros árboles señalados con este color verde, y se ve que la altura de todos estos árboles es también de hecho 3. Eso es parte de lo que los hace degenerar - que su altura es sólo uno menos que el número de nodos en el árbol completo. Si nos fijamos en este otro árbol que está rodeado de rojo, por otro lado, vemos que los nodos de hoja más distantes son el 6 y el 9 - la deja ser aquellos nodos que no tienen hijos. Así, con el fin de obtener desde el nodo raíz a ya sea el 6 o el 9, tenemos que hacer un salto para llegar a la 7 y luego un segundo salto para llegar a la 9, y del mismo modo, sólo un salto de la segunda 7 para llegar a la 6. Así, la altura de este árbol de aquí es sólo 2. Usted puede volver atrás y hacer que para todos los demás árboles que previamente discutido comenzando con el 7 y el 6, y te darás cuenta de que la altura de todos esos árboles es también 2. 

La razón por la que hemos estado hablando ordenó árboles binarios y por qué estamos bien es porque usted puede buscar a través de ellos en de una manera muy similar a la búsqueda a través de una matriz ordenada. Aquí es donde hablamos de conseguir que el tiempo de búsqueda mejorada sobre la lista enlazada simple. Con una lista enlazada - si usted desea encontrar un elemento en particular - eres lo mejor va a hacer algún tipo de búsqueda lineal donde se inicia al comienzo de la lista y saltar de uno en uno - un nodo a un nodo - a través de toda la lista hasta que encuentre lo que usted está buscando. Mientras que si usted tiene un árbol binario que se almacena en este formato agradable, usted puede obtener más de una búsqueda binaria pasando donde se divide y vencerás y buscar en la media correspondiente del árbol en cada paso. Vamos a ver cómo funciona. 

Si tenemos - de nuevo, volviendo a nuestro árbol original - comenzamos a 7, que tienen 3 a la izquierda, 9 a la derecha, y debajo de la 3 tenemos la 6. Si queremos buscar el número 6 de este árbol, nos gustaría empezar en la raíz. Queremos comparar el valor que buscamos, por ejemplo 6, con el valor almacenado en el nodo que estamos mirando, 7, encontrar que 6 es de hecho menor que 7, por lo que nos mueve a la izquierda. Si el valor de 6 había sido mayor que 7, habríamos se mueven a la derecha. Ya que sabemos que - debido a la estructura de nuestro árbol binario ordenado - todos los valores de menos de 7 van a ser almacenados a la izquierda de 7, no hay necesidad de molestarse siquiera mirar por el lado derecho del árbol. Una vez que nos movemos hacia la izquierda y ahora estamos en el nodo que contiene 3, podemos hacer esa comparación misma de nuevo donde se compara el 3 y el 6. Y encontramos que mientras que el 6 - el valor que estamos buscando - es mayor que 3, que puede ir hacia el lado derecho del nodo que contiene 3. No hay lado izquierdo aquí, así que podría haber ignorado eso. Sin embargo, sólo se sabe que debido a que estamos viendo en el propio árbol, y podemos ver que el árbol no tiene hijos. 

También es muy fácil buscar 6 de este árbol si lo estamos haciendo a nosotros mismos como seres humanos, pero vamos a seguir este proceso mecánicamente como un ordenador haría para comprender realmente el algoritmo. En este punto, ahora estamos viendo un nodo que contiene 6, y estamos buscando el valor 6, así que, de hecho, hemos encontrado el nodo apropiado. Encontramos el valor 6 en nuestro árbol, y podemos detener nuestra búsqueda. En este punto, dependiendo de lo que está pasando, podemos decir, sí, hemos encontrado el valor 6, existe en nuestro árbol. O bien, si estamos planeando para insertar un nodo o hacer algo, podemos hacer eso en este momento. 

Vamos a hacer un par de búsquedas sólo para ver cómo funciona esto. Echemos un vistazo a lo que sucede si fuéramos a tratar de buscar el valor 10. Si tuviéramos que buscar el valor 10, que comenzaría en la raíz. Nos gustaría ver que 10 es mayor que 7, por lo que nos mueve a la derecha. Llegábamos a las 9 y comparar 9 a las 10 y ver que el 9 es de hecho inferior a 10. Así que de nuevo, nos gustaría tratar de mover a la derecha. Pero en este punto, se daría cuenta de que estamos en un nodo nulo. No hay nada allí. No hay nada que el 10 debe ser. Aquí es donde podemos informar fracaso - que hay de hecho no 10 en el árbol. Y, por último, vamos a pasar por el caso en el que estamos tratando de buscar una en el árbol. Esto es similar a lo que ocurre si miramos hacia arriba 10, excepto que en lugar de ir a la derecha, vamos a ir a la izquierda. Empezamos en el 7 y ver que 1 es menor que 7, por lo que se mueven a la izquierda. Llegamos a la 3 y ver que 1 es menor que 3, por lo que de nuevo se trata de mover a la izquierda. En este momento tenemos un nodo nulo, así que de nuevo podemos informar fracaso. 

Si usted quiere aprender más sobre los árboles binarios, hay un montón de divertidos pequeños problemas que se pueden hacer con ellos. Sugiero practicar el dibujo de estos diagramas de una por uno y siguiendo a través de todos los diferentes pasos, porque esto vendrá en super manejable no sólo cuando estás haciendo la codificación Huffman conjunto de problemas sino también en los futuros cursos - aprendiendo a dibujar estas estructuras de datos y reflexionar sobre los problemas con lápiz y papel o, en este caso, el iPhone y el lápiz. 

En este punto, sin embargo, vamos a pasar a hacer algunas prácticas de codificación y realmente jugar con estos árboles binarios y ver. Voy a volver a mi equipo. Para esta parte de la sección, en lugar de utilizar CS50 CS50 Run o Spaces, Voy a utilizar el aparato. 

Siguiendo con la especificación conjunto de problemas, Veo que tengo que abrir el aparato, ir a mi carpeta de Dropbox, cree una carpeta llamada Sección 7, a continuación, cree un archivo llamado binary_tree.c. Aquí vamos. Tengo el aparato ya está abierto. Voy a levantar una terminal. Voy a ir a la carpeta de Dropbox, cree un directorio llamado Sección 7, y ver que es totalmente vacío. Ahora voy a abrir binary_tree.c. Muy bien. Aquí vamos - archivo vacío. 

Volvamos a la especificación. La especificación pide que cree una definición de tipo nuevo para un nodo de árbol binario que contiene valores int - al igual que los valores que nos sacó de nuestra diagramación antes. Vamos a utilizar este texto modelo typedef que hemos hecho aquí que se debe reconocer de Serie de problemas 5 - si lo hizo de la manera tabla hash de conquistar el programa corrector ortográfico. También debe reconocer a partir de la sección de la semana pasada donde hablamos acerca de las listas enlazadas. Tenemos esta typedef de un nodo de estructura, y le hemos dado a este nodo struct este nombre de nodo de estructura de antemano para que luego pueda referirse a ella ya que querrá tener punteros struct nodo como parte de nuestra estructura, pero luego nos hemos rodeado este - o más bien, encerrado esto - en un typedef de modo que, más adelante en el código, se puede hacer referencia a esta estructura como un nodo en lugar de un nodo de estructura. 

Esto va a ser muy similar a la definición de la lista simplemente enlazada que vimos la semana pasada. Para ello, vamos a empezar por escribir el texto modelo. Sabemos que tenemos que tener un valor entero, así que vamos a poner en valor int, y entonces, en lugar de tener sólo un puntero al siguiente elemento - como lo hicimos con simplemente enlazada listas - vamos a tener punteros hijo izquierdo y derecho. Eso es bastante simple también - niño struct nodo * left; struct nodo y niño * derecha;. Cool. Eso parece un buen comienzo. Volvamos a la especificación. 

Ahora tenemos que declarar una variable de nodo * global para la raíz de un árbol. Vamos a hacer de este mundial al igual que hicimos en nuestro primer puntero lista enlazada también global. Esto era para que en las funciones que escribimos nosotros no tenemos que seguir pasando alrededor de esta raíz - aunque ya veremos que si quiero escribir estas funciones de forma recursiva, puede ser que sea mejor ni siquiera lo pasan a su alrededor como un mundial en el primer lugar y en lugar de iniciar a nivel local en su función principal. Pero, lo haremos a nivel mundial para comenzar. Una vez más, vamos a dar un par de espacios, y yo voy a declarar una raíz * nodo. Sólo para asegurarse de que no me deja esta sin inicializar, me voy a fijar igual a null. Ahora, en la función principal - lo que vamos a escribir muy rápido aquí - int main (int argc, const char * argv []) - y yo voy a empezar a declarar mi matriz argv como const sólo para que yo sepa que esos argumentos son los argumentos que probablemente no quieren modificar. Si desea modificarlos Probablemente debería estar haciendo copias de ellos. Usted verá esto mucho en el código. Está bien de cualquier manera. Está bien dejarlo como - omitir la const si lo desea. Me suelen ponerlo en sólo para que me recuerdo  que probablemente no desea modificar esos argumentos. 

Como siempre, voy a incluir esta línea return 0 al final del principal. Aquí, voy a iniciar mi nodo raíz. Tal como está ahora mismo, tengo un puntero que se establece en null, lo que apunta a la nada. Con el fin de iniciar realmente la construcción del nodo, La primera vez que asignar memoria para él. Voy a hacer que al hacer memoria en el heap usando malloc. Voy a establecer root igual al resultado de malloc, y voy a utilizar el operador sizeof para calcular el tamaño de un nodo. La razón por la que uso nodo sizeof a diferencia de, digamos, hacer algo como esto - malloc (4 + 4 + 4) o malloc 12 - es porque quiero que mi código sea lo más compatible posible. Quiero ser capaz de tomar este archivo. C, compilarlo en el aparato, y luego compilarlo en mi 64-bit Mac - o en una arquitectura completamente diferente - y quiero que todo esto funcione de la misma. 

Si estoy haciendo suposiciones sobre el tamaño de las variables - el tamaño de un int o el tamaño de un puntero - entonces yo también estoy haciendo suposiciones acerca de los tipos de arquitecturas en el que mi código se puede compilar con éxito cuando se ejecuta. Siempre utilice sizeof en lugar de manualmente sumando los campos struct. La otra razón es que también puede haber acolchado que el compilador pone en la estructura. Aunque sólo sea sumando los campos individuales no es algo que normalmente se quiere hacer, así, eliminar esa línea. Ahora, para inicializar realmente este nodo raíz, Voy a tener que enchufar los valores para cada uno de sus campos. Por ejemplo, para el valor sé que quiero para inicializar a 7, y por ahora me voy a poner al niño izquierda a ser nulo y el hijo derecho a ser también nulo. Great! Lo hemos hecho parte de la especificación. 

La especificación abajo en la parte inferior de la página 3 me pide que cree más tres nodos - una que contiene 3, una que contiene 6, y uno con 9 - y luego cablear para que se vea exactamente igual que nuestro diagrama de árbol que hablábamos anteriormente. Vamos a hacer esto muy rápidamente aquí. Usted verá realmente rápido que voy a empezar a escribir un montón de código duplicado. Voy a crear un nodo * y voy a llamar tres. Voy a ponerlo igual a malloc (sizeof (nodo)). Me voy a poner tres-> valor = 3. Tres -> left_child = NULL; tres -> derecha _child = NULL; también. Eso se ve muy similar a la inicialización de la raíz, y eso es exactamente lo que Voy a tener que hacer si comienzo la inicialización de 6 y 9 también. Lo haré muy rápido aquí - en realidad, yo voy a hacer un poco de copia y pega, y asegurarse de que yo - bien.  Ahora, tengo que copiar y puedo seguir adelante y crear esta igual a 6. Se puede ver que esto toma tiempo y no es super-eficiente. En tan sólo un poco, vamos a escribir una función que lo hará por nosotros. Quiero sustituir esto con un 9, reemplazarlo con un 6. 

Ahora tenemos todos nuestros nodos creado e inicializado. Tenemos nuestra raíz igual a 7, o que contiene el valor 7, nuestro nodo que contiene 3, nuestro nodo que contiene 6, y nuestro nodo contiene 9. En este punto, todo lo que tenemos que hacer es cablear todo. La razón por la que inicializa todos los punteros a null es sólo para que me aseguro de que Yo no tengo ningún puntero sin inicializar en allí por accidente. Y también porque, en este momento, sólo tiene que conectar realmente los nodos entre sí - a los que en realidad están conectados a - Yo no tengo que ir a través y hacer Asegúrese de que todos los nulos están ahí en los lugares apropiados. 

A partir de la raíz, lo sé hijo izquierdo de la raíz es 3. Sé que hijo derecho de la raíz es 9. Después de eso, el hijo único que me queda para preocuparse es hijo derecho 3, que es 6. En este punto, todo se ve muy bien. Vamos a eliminar algunas de estas líneas. Ahora todo se ve muy bien. Volvamos a nuestras especificaciones y ver lo que tenemos que hacer a continuación. 

En este punto, tenemos que escribir una función llamada "contiene" con un prototipo del 'contiene bool (int value). Y esto incluye la función va a devolver true  si el árbol apuntado por la variable raíz global  contiene el valor que se pasa a la función y false en caso contrario. Vamos a seguir adelante y hacer eso. Esto va a ser exactamente igual que la búsqueda que hemos hecho a mano en el iPad un poco atrás. Vamos a volver a aumentar un poco y desplácese hacia arriba. Vamos a poner esta función justo encima de nuestra función principal de modo que no tenemos que hacer ningún tipo de prototipos. Por lo tanto, contiene bool (int value). Ahí vamos. Ahí está nuestra declaración repetitivo. Sólo para asegurarse de que esta se compilará, Voy a seguir adelante y sólo lo hace igual a devolver false. En este momento esta función simplemente no hacer nada y siempre informan de que el valor que está buscando no está en el árbol. 

En este punto, es probablemente una buena idea - ya que he escrito un montón de código y ni siquiera hemos intentado probarlo todavía - para asegurarse de que todo se compila. Hay un par de cosas que tenemos que hacer para asegurarse de que esto va a compilar. En primer lugar, ver si hemos estado utilizando cualquiera de las funciones de las bibliotecas que aún no hemos incluidos. Las funciones que hemos utilizado hasta ahora son malloc, y también hemos estado utilizando este tipo - este tipo no estándar llamada "bool' - que se incluye en el archivo de cabecera bool estándar. Definitivamente, queremos incluir bool.h estándar para el tipo bool, y también queremos incluir # lib.h estándar para las bibliotecas estándar que incluyen malloc y libre, y todo eso. Por lo tanto, alejar la imagen, vamos a dejar de fumar. Vamos a tratar de asegurarse de que esto realmente hizo compilación. Vemos que lo hace, así que estamos en el camino correcto. 

Vamos a abrir binary_tree.c nuevo. Compila. Vamos hacia abajo y asegúrese de que insertamos algunas llamadas a nuestra función contiene - sólo para asegurarse de que eso es todo bien y bueno. Por ejemplo, cuando hicimos algunas búsquedas en nuestro árbol antes, hemos tratado de buscar los 6 valores, 10 y 1, y sabíamos que el 6 estaba en el árbol, 10 no estaba en el árbol, y 1 no estaba en el árbol tampoco. Vamos a usar esas llamadas muestra como una forma de averiguar si es o no nuestra función contiene está funcionando. Con el fin de hacer eso, voy a utilizar la función printf, y vamos a imprimir el resultado de la llamada a la contenga. Me voy a poner en una cadena "contiene (% d) = porque  vamos a enchufar el valor que vamos a buscar, y =% s \ n ", y usar eso como nuestra cadena de formato. Sólo vamos a ver - literalmente imprimir en la pantalla - lo que parece una llamada de función. Esto no es realmente la llamada a la función.  Esto es sólo una cadena diseñado para parecerse a una llamada de función. 

Ahora, vamos a conectar los valores. Vamos a intentar contiene los días 6, y entonces, ¿qué vamos a hacer aquí es utilizar ese operador ternario. Vamos a ver - incluye 6 - así que, ahora que he contenía 6 y si contiene 6 es cierto, la cadena que vamos a enviar al carácter de formato% s va a ser la cadena "true". Vamos a desplazarse durante un rato. De lo contrario, queremos enviar la cadena "false" si contiene 6 devuelve false. Esto es un poco torpe aspecto, pero me imagino que bien podría ilustrar lo que el operador ternario parece, ya que no lo he visto por un tiempo. Esta será una manera agradable, muy práctico para saber si nuestra función contiene está funcionando. Voy a desplazarse de nuevo hacia la izquierda, y voy a copiar y pegar esta línea un par de veces. Cambió algunos de estos valores alrededor, así que esto va a ser 1, y esto va a ser de 10. 

En este punto tenemos una función contiene agradable. Tenemos algunas pruebas, y vamos a ver si funciona todo esto. En este punto hemos escrito código un poco más. Es hora de dejar de fumar y asegurarse de que todo lo que todavía compila. Salir fuera, y ahora vamos a intentar hacer árbol binario de nuevo. Bueno, parece que tenemos un error, Y tenemos esta declarar explícitamente la función de biblioteca printf. Parece que tenemos que ir y # include standardio.h. Y con eso, todo debe compilar. Estamos todos bien. Ahora vamos a intentar ejecutar árbol binario y ver qué pasa. Aquí estamos. / Binary_tree, y vemos que, como esperábamos - porque no han puesto en práctica contiene, sin embargo, o más bien, acabamos de poner en return false - vemos que se acaba de devolver false para todos ellos, de modo que todo está funcionando en su mayor parte bastante bien. 

Vamos a ir de nuevo y poner en práctica en realidad contiene en este punto. Voy a desplazarse hacia abajo, acercar, y - recuerde, el algoritmo que se utilizó fue que empezamos en el nodo raíz y luego en cada nodo que encontramos, hacemos una comparación, y en base a esa comparación que o mover al niño a la izquierda oa la derecha niño. Esto va a parecer muy similar al código binario de búsqueda que hemos escrito anteriormente en el término. Cuando nos pusimos en marcha, sabemos que queremos mantener en el nodo actual que estamos viendo, y el nodo actual va a ser inicializado al nodo raíz. Y ahora, vamos a seguir adelante a través del árbol, y recordar que nuestra condición de parada -  cuando realmente terminado con el ejemplo a mano - Fue entonces cuando nos encontramos con un nodo nulo, no cuando miramos a un niño nulo, sino más bien cuando realmente mueve a un nodo en el árbol y encontraron que estamos en un nodo nulo. Vamos a iterar hasta act no es igual a null. ¿Y qué vamos a hacer? Vamos a probar si (act -> valor value ==), entonces sabemos que en realidad hemos encontrado el nodo que estamos buscando. Así que aquí, podemos volver realidad. De lo contrario, queremos ver si el valor es menor que el valor. Si el valor del nodo actual es menor que el valor que estamos buscando, vamos a mover a la derecha. Por lo tanto, act act = -> right_child, y de lo contrario, vamos a mover hacia la izquierda. act = act -> left_child;. Bastante simple. 

Es probable que reconocer el lazo que se ve muy similar a la de este búsqueda binaria anteriormente en el término, excepto entonces se trataba de mediados baja y alta. En este caso, sólo tenemos que mirar a un valor actual, así que es agradable y simple. Vamos a asegurarnos de que el código esté funcionando. Primero, asegúrese de que compila. Parece que lo hace. Vamos a tratar de ejecutarlo. Y, en efecto, imprime todo lo que esperábamos. Se encuentra a 6 en el árbol, no encuentra 10 porque 10 no está en el árbol, y no encuentra ya sea porque 1 1 No es también en el árbol. Cool stuff. 

Muy bien. Volvamos a nuestra especificación y ver lo que se viene. Ahora, quiere agregar nodos algunos más para nuestro árbol. Quiere añadir 5, 2 y 8, y asegúrese de que contiene nuestro código aún funciona como se esperaba. Vamos a hacer eso. En este punto, en lugar de hacer que copia molesto y pegar de nuevo, vamos a escribir una función para crear realmente un nodo. Si nos desplazamos hacia abajo hasta llegar a principal, vemos que hemos estado haciendo esto código muy similar una y otra vez cada vez que queremos crear un nodo. 

Vamos a escribir una función que en realidad va a construir un nodo para nosotros y lo devuelve. Voy a llamarlo build_node. Voy a construir un nodo con un valor determinado. Acércate aquí. Lo primero que voy a hacer es crear un espacio para el nodo en el montón. Por lo tanto, el nodo * n = malloc (sizeof (nodo)); n -> valor = valor; y luego aquí, yo sólo voy a inicializar todos los campos para los valores adecuados. Y al final, vamos a volver a nuestra nodo. Muy bien. Una cosa a tener en cuenta es que esta función aquí va a devolver un puntero a la memoria que ha sido asignada por montón. Lo bueno de esto es que este nodo ahora - tenemos que declarar en el montón porque si lo declarado en la pila no seríamos capaces de hacer en esta función como esta. Esa memoria se salga del ámbito y no sería válida si intentamos acceder a él más adelante. Ya que estamos declarando montón asignado por la memoria, vamos a tener que cuidar de liberarlo más tarde para nuestro programa no se escape ningún recuerdo. Hemos estado en el que batea para todo lo demás en el código sólo por razones de simplicidad en el momento, pero si alguna vez escribir una función que tiene este aspecto donde tienes - algunos lo llaman un malloc o realloc interior - usted querrá asegurarse de que usted pone algún tipo de comentario por aquí que dice: bueno, ya sabes, devuelve un nodo de heap asignado se inicializa con el valor pasado como. Y entonces usted quiere asegurarse de que usted pone en una especie de nota que dice: el llamador debe liberar la memoria devuelta. De esa manera, si alguien alguna vez va y usa esa función, ellos saben que cualquier cosa que regrese de esa función en algún momento tendrá que ser liberado. 

Suponiendo que todo está bien y bueno aquí, podemos bajar a nuestro código y reemplazar todas estas líneas aquí con llamadas a nuestra función de nodo de generación. Vamos a hacer esto muy rápidamente. La única parte que no vamos a sustituir es esta parte aquí abajo en la parte inferior donde realmente cablear los nodos para que apunte a la otra, ya que no podemos hacer en nuestra función. Pero, vamos a hacer root = build_node (7); nodo * = build_node tres (3); nodo * seis = build_node (6); nodo * nueve = build_node (9);. Y ahora, también queríamos agregar nodos para - nodo * cinco = build_node (5); nodo * = build_node ocho (8); y lo que era el otro nodo? Vamos a ver aquí. Hemos querido añadir también un 2 - nodo * = build_node dos (2);. Muy bien. En este punto, sabemos que tenemos el 7, el 3, el 9 y el 6 todos conectados de forma apropiada, pero ¿qué pasa con el 5, el 8, y el 2? Para mantener todo en el orden apropiado, sabemos que el hijo derecho es tres 6. Por lo tanto, si vamos a añadir los 5, el 5 pertenece también en el lado derecho del árbol de los cuales 3 es la raíz, así como 5 pertenece el hijo izquierdo de 6. Podemos hacer esto diciendo, seis -> left_child = cinco; y luego el 8 pertenece como hijo izquierdo de 9, por lo que nueve -> left_child = ocho; y luego 2 es el hijo izquierdo de 3, por lo que podemos hacer eso aquí - te -> left_child = dos;. Si usted no acababa de seguir junto con eso, le sugiero que lo alcanzará a ti mismo. 

Muy bien. Vamos a guardar este. Vamos a salir y asegurarse de que recopila, y luego podemos añadir en nuestras llamadas contiene. Parece que todo aún se compila. Vamos a entrar y añadir en algunos contiene llamadas. Una vez más, voy a hacer un poco de copiar y pegar. Ahora vamos a buscar a 5, 8 y 2. Muy bien. Vamos a asegurarnos de que todo esto se ve bien quieto. Great! Guardar y salir. Ahora vamos a hacer, compilar, y ahora vamos a correr. A partir de los resultados, parece que todo está funcionando muy bien y bien. Great! Así que ahora tenemos a nuestra función CONTAINS escrito. Vamos a seguir adelante y empezar a trabajar en la forma de insertar nodos en el árbol ya que, como lo estamos haciendo en este momento, las cosas no son muy bonitos. 

Si nos remontamos a la especificación, nos pide que escriba una función llamada insertar - de nuevo, volviendo a bool para saber si estamos o no en realidad podría insertar el nodo en el árbol - y luego el valor para insertar en el árbol se especifica como el único argumento a nuestra función de inserción. Nos devolverá true si realmente puede insertar el valor del nodo que contiene al árbol, lo que significa que, uno, tenía suficiente memoria, y luego dos, ese nodo no existe en el árbol ya que - Recuerde, nosotros no vamos a tener valores duplicados en el árbol, sólo para hacer las cosas simples. Muy bien. Volver al principio Código. Ábrelo. Acercar un poco, a continuación, desplácese hacia abajo. Vamos a poner la función de inserción justo encima de las CONTAINS. Una vez más, va a ser llamado insert bool (int value). Dale un poco más espacio y, a continuación, de forma predeterminada, vamos a poner en return false al final. Ahora, en el fondo, vamos a seguir adelante y en vez de construir manualmente los nodos principal en nosotros mismos y el cableado hasta el punto que el uno al otro como lo estamos haciendo, vamos a confiar en nuestra función de inserción de hacer eso. No vamos a confiar en nuestra función de inserción para construir el árbol entero desde cero todavía, sino que más bien nos desharemos de estas líneas - nos volveremos comentar estas líneas - que construir los nodos 5, 8 y 2. Y en su lugar, vamos a insertar llamadas a nuestra función de inserción para asegurarse de que que realmente funciona. Aquí vamos. 

Ahora hemos comentado estas líneas. Sólo tenemos 7, 3, 9, y 6 en nuestro árbol en este punto. Para asegurarse de que todo esto está funcionando, podemos alejar, hacer nuestro árbol binario, ejecutarlo, y podemos ver que contiene ahora nos dicen que estamos totalmente a la derecha - 5, 8, y 2 ya no están en el árbol. Volver atrás en el código, y ¿cómo vamos a insertar? Recuerda lo que hicimos cuando estábamos en realidad la inserción de 5, 8, y 2 previamente. Hemos jugado a ese juego Plinko donde empezamos en la raíz, bajó el árbol por uno por uno hasta encontrar el hueco apropiado, y luego por cable en el nodo en el lugar apropiado. Vamos a hacer lo mismo. Esto es básicamente como escribir el código que usamos en la función CONTAINS para encontrar el punto donde el nodo debe ser, y entonces sólo vamos a insertar el nodo allí. Vamos a empezar a hacer eso. 

Así que tenemos un nodo * act = root, sólo vamos a seguir el código contiene hasta que nos encontramos con que no acaba de funcionar para nosotros. Vamos a ir a través del árbol, mientras que el elemento actual no es nulo, y si encontramos que act valor es igual al valor que estamos tratando de insertar - bueno, este es uno de los casos en los que no pudimos insertar el nodo en el árbol porque esto significa que tenemos un valor duplicado. Aquí estamos en realidad va a devolver false. Ahora bien, si el valor act es menor que el valor, ahora sabemos que nos movemos hacia la derecha  porque el valor pertenece en la mitad derecha del árbol act. De lo contrario, vamos a mover hacia la izquierda. Eso es básicamente nuestra función CONTAINS ahí. 

En este punto, una vez que hayamos completado este bucle while, nuestro puntero act va a estar apuntando a null si la función no ha regresado. Estamos por lo tanto tener act en el lugar donde queremos insertar el nuevo nodo. Lo que queda por hacer es construir realmente el nuevo nodo, que podemos hacer con bastante facilidad. Podemos utilizar nuestra super manejable y función de nodo de generación, y es algo que no hemos hecho antes - nosotros sólo tipo de daba por hecho, pero ahora lo haremos sólo para asegurarse de - vamos a probar para asegurarse de que el valor devuelto por el nuevo nodo en realidad era no es nulo, porque no quiero empezar a acceder a esa memoria si es nulo. Podemos probar para asegurarse de que el nuevo nodo no es igual a null. O por el contrario, sólo podemos ver si realmente es nulo, y si es nulo, entonces solo puede devolver false temprano. 

En este punto, tenemos que cablear nuevo nodo en su lugar correspondiente en el árbol. Si miramos hacia atrás en la principal y en el que en realidad eran el cableado en los valores de antes, vemos que la forma en que lo hacían cuando querían poner 3 en el árbol Se accede a que el hijo izquierdo de la raíz. Cuando ponemos 9 en el árbol, tuvimos que acceder al hijo derecho de la raíz. Teníamos que tener un puntero a la matriz con el fin de poner un nuevo valor en el árbol. Desplazamiento de una copia de seguridad para insertar, eso no va a funcionar bastante aquí porque no tenemos un puntero padres. Lo que quiero ser capaz de hacer es, en este punto, comprobar el valor de los padres y ver - bueno, caramba, si el valor de los padres es menor que el valor de la corriente, entonces hijo derecho de los padres debe ser el nuevo nodo; de lo contrario, hijo izquierdo del padre debería ser el nodo nuevo. Pero, no tenemos este puntero padre todavía. 

Para conseguirlo, estamos en realidad va a tener que seguir a medida que avanzamos a través del árbol y encontrar el lugar adecuado en nuestro bucle anterior. Podemos hacerlo de nuevo, desplazándose hasta la parte superior de nuestra función de inserción y el seguimiento de otra variable puntero llamado el padre. Vamos a ponerlo igual a null inicialmente, y entonces cada vez que pasamos por el árbol, vamos a establecer el puntero padre para que coincida con el puntero actual. Establecer padre igual act. De esta manera, cada vez que vamos a través, vamos a garantizar que, como el actual puntero se incrementa el puntero del padre que sigue - sólo un nivel más alto que el actual puntero en el árbol. Que todo se ve muy bien. 

Creo que la única cosa que vamos a querer ajustar es construir este nodo nulo retorno. Con el fin de conseguir construir nodo para volver realidad con éxito nulo, vamos a tener que modificar el código, porque aquí, nunca hemos probado para asegurarse de que malloc devuelve un puntero válido. Así, si (n = NULL), entonces - si malloc devuelve un puntero válido, entonces vamos a inicializar; de lo contrario, sólo tendremos que regresar y que va a terminar devolviendo un valor nulo para nosotros. Ahora todo se ve muy bien. Vamos a asegurarnos de que esto realmente compila. Haga árbol binario, y oh, tenemos algunas cosas que están pasando aquí. 

Tenemos una declaración implícita de la función de construir nodo. Una vez más, con estos compiladores, vamos a empezar en la parte superior. Lo que eso quiere decir es que estoy llamando a construir nodo antes de que yo he hecho lo declaró. Volvamos al código muy rápido. Desplácese hacia abajo y, por supuesto, mi función de inserción se declara por encima de la función de nodo de generación, pero estoy tratando de usar construir nodo dentro del inserto. Voy a entrar y copiar - pegar y luego el nodo de generación manera función aquí en la parte superior. De esta manera, es de esperar que funcione. Vamos a dar esta otra oportunidad. Ahora todo se compila. Todo está bien. 

Pero en este punto, no se han llamado nuestra función de inserción. Sólo sabemos que compila, así que vamos a ir y poner algunas llamadas pulg Vamos a hacer que en nuestra función principal. En este sentido, comentada 5, 8, y 2, y luego no los cable hasta aquí. Vamos a hacer algunas llamadas para insertar, y también vamos a utilizar el mismo tipo de cosas que hemos utilizado cuando hicimos estas llamadas printf para asegurarse de que todo lo que se te ha insertado correctamente. Voy a copiar y pegar, y contiene en lugar de que vamos a hacer de inserción. Y en vez de 6, 10 y 1, que vamos a utilizar 5, 8 y 2. Esto debería insertar 5, 8, y 2 en el árbol. Compilar. Todo está bien. Ahora estamos realmente va a ejecutar nuestro programa. 

Todo lo devuelve false. Así, 5, 8 y 2 no ir, y parece que contiene no los encontró tampoco. ¿Qué está pasando? Vamos a reducir. El primer problema fue que se insertan parecía volver falsa, y parece que eso es porque nos fuimos en nuestro call return false, y que en realidad nunca volvió realidad. Podemos poner esto en marcha. El segundo problema es que ahora incluso si lo hacemos - guardar esto, salga de esto, hacer funcionar de nuevo, han compilarlo, a continuación, ejecútelo - vemos que algo más pasó aquí. El 5, 8, y 2 nunca se encuentran todavía en el árbol. Entonces, ¿qué está pasando? 

Vamos a echar un vistazo a esto en el código. Vamos a ver si podemos resolver esto. Empezamos con el padre no es nulo. Hemos establecido el puntero actual es igual al puntero raíz, y vamos a trabajar nuestro camino hacia abajo a través del árbol. Si el nodo actual no es nulo, entonces sabemos que podemos bajar un poco. Hemos creado nuestro puntero padre para ser igual al puntero actual, comprobado el valor - si los valores son los mismos que volvimos falsa. Si los valores son menores que nos mudamos a la derecha; de lo contrario, nos trasladamos a la izquierda. A continuación, se construye un nodo. Voy a ampliar un poco. Y aquí, vamos a tratar de cablear los valores a ser el mismo. ¿Qué está pasando? Vamos a ver si posiblemente Valgrind puede darnos una pista. 

Me gusta usar Valgrind Valgrind sólo porque corre muy rápido y te dice si hay errores de memoria. Cuando corremos Valgrind en el código, como pueden ver afectados here--Valgrind./binary_tree--and derecho entrar. Ya ves que no tenía ningún error de memoria, así que parece que todo está bien hasta ahora. Tenemos algunas pérdidas de memoria, lo que conocemos, porque no somos pasando a liberar a cualquiera de nuestros nodos. Vamos a intentar ejecutar GDB para ver lo que realmente está pasando. Haremos gdb. / Binary_tree. Se arrancado bien. Vamos a poner un punto de interrupción de la plaquita. Vamos a correr. Parece que nunca nos llama en realidad inserción. Parece que el problema era que cuando me cambié aquí en principal - todas estas llamadas de printf contiene - En realidad, nunca cambió de inmediato a llamar inserción. Ahora vamos a darle una oportunidad. Vamos a compilar. Todo se ve bien allí. Ahora vamos a tratar de ejecutarlo, a ver qué pasa. ¡Muy bien! Todo se ve muy bien allí. 

La última cosa a considerar es, ¿hay casos límite a esta inserción? Y resulta que, bueno, el caso extremo que es siempre interesante pensar Es decir, ¿qué pasa si el árbol está vacío y se llama a esta función de inserción? ¿Funcionará? Bueno, vamos a darle una oportunidad. - Binary_tree c. - La forma en que vamos a probar esto, vamos a ir a nuestra función principal, y en lugar de cableado de estos nodos de esta manera, sólo vamos a comentar toda la cosa, y en vez de nosotros mismos cableando los nodos, en realidad podemos simplemente seguir adelante y borrar todo esto. Vamos a hacer todo lo que una llamada a insertar. Por lo tanto, vamos a hacer - en vez de 5, 8 y 2, vamos a insertar 7, 3, y 9. Y luego también querrá insertar 6 también. Guardar. Salir. Hacer árbol binario. Todo compila. Sólo se puede ejecutar como está y ver qué pasa, pero también va a ser muy importante para asegurarse de que no tenemos ningún error de memoria, ya que este es uno de nuestros casos extremos que conocemos. 

Vamos a asegurarnos de que funciona bien bajo Valgrind, que vamos a hacer simplemente ejecutando Valgrind. / binary_tree. Parece que sí tienen un error de un contexto - tenemos este fallo de segmentación. ¿Qué ha pasado? Valgrind en realidad nos dice dónde está. Reducir un poco. Parece que lo que está sucediendo en nuestra función de inserción, donde tenemos una lectura no válida del 4 al tamaño de inserción, la línea 60. Vamos a volver atrás y ver lo que está pasando aquí. Alejar muy rápido. Quiero para asegurarse de que no va hasta el borde de la pantalla para que podamos ver todo. Tire de que en un poco. Muy bien. Desplácese hacia abajo, y el problema está aquí. ¿Qué sucede si nos ponemos manos y nuestro nodo actual ya es nulo, nuestro nodo padre es nulo, por lo que si miramos hacia arriba en la parte superior, a la derecha aquí - si nunca este bucle while ejecuta realmente porque nuestro valor actual es nulo - nuestra raíz es nulo así act es nulo - entonces nunca nuestro padre se establece en act oa un valor válido, así, los padres también será nulo. Tenemos que recordar para comprobar que en el momento en que nos pongamos aquí, y empezar a acceder valor de los padres. Entonces, ¿qué sucede? Bueno, si el padre es nulo - if (padre == NULL) - entonces sabemos que no debe haber nada en el árbol. Debemos estar intentando insertarlo en la raíz. Podemos hacer eso con sólo ajustar la raíz igual al nuevo nodo. Entonces en este punto, que en realidad no quieren pasar por estas otras cosas. En cambio, aquí, podemos hacer bien una cosa-if-else, o podemos combinar todo aquí en una cosa, pero aquí sólo tendremos que usar más y hacerlo de esa manera. Ahora, vamos a probarlo para asegurarse de que nuestro padre no es nulo antes de esa realidad tratando de acceder a sus campos. Esto nos ayudará a evitar el fallo de segmentación. Así pues, dejar de fumar, reducir, compilar, ejecutar. 

No hay errores, pero todavía tenemos un montón de pérdidas de memoria porque no liberar a cualquiera de nuestros nodos. Pero, si vamos por aquí y nos fijamos en nuestro listado, vemos que, bueno, parece que todos nuestros insertos se devuelve true, lo cual es bueno. Los insertos son todas verdaderas, y luego las llamadas contiene apropiados, son ciertas. 

¡Buen trabajo! Parece que has escrito correctamente inserto. Eso es todo lo que tenemos para la especificación de esta semana Problema. Un divertido desafío es pensar en cómo usted iría en y libre de todos los nodos de este árbol. Podemos hacer un número de maneras diferentes, pero lo dejo a usted para experimentar, y como un reto divertido, tratar de asegurarse de que usted puede asegurarse de que que este informe Valgrind devuelve ningún error y sin fugas. 

Buena suerte en el set de esta semana Huffman problema de codificación, y nos vemos la próxima semana! [CS50.TV]