Arboles Binarios
Enviado por loganliz • 20 de Mayo de 2012 • 418 Palabras (2 Páginas) • 1.199 Visitas
¿Qué son los arboles binarios?
Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Un árbol binario es un conjunto finito de elementos que está vacío o dividido en tres subconjuntos separados. El primer subconjunto contiene un único elemento llamado raíz del árbol. Los otros 2 subconjuntos son por si mismos árboles binarios y se les conoce como subárboles izquierdo y derecho del árbol original. Cada elemento de un árbol binario se denomina nodo. La ausencia de una ramificación indica un subárbol vacio.
¿Cómo se declara un árbol binario?
Para declarar un árbol en C de inmediato pensamos en 2 alternativas: se declara un arreglo de nodos de árbol o se asigna una variable dinámica para cada nodo creado. Sin embargo ¿Cuál será la estructura de cada nodo individual? En la representación de árbol binario, cada nodo contiene un campo de información y 2 apuntadores hacia sus 2 hijos. Pero ¿Cuántos apuntadores debe contener un nodo de árbol?. La cantidad de hijos de un nodo es variable y puede ser tan grande o pequeña como sea necesario.
¿Explica los tres recorridos que existen para arboles binarios?
Un árbol binario no vacio puede ser recorrido de 3 maneras distintas: Orden previo, orden y orden posterior.
El recorrido en orden previo (Orden de primero profundidad) sigue 3 operaciones:
• Visitar la raíz.
• Recorrer el subárbol izquierdo en orden previo.
• Recorrer el subárbol derecho en orden previo.
El recorrido en orden (Orden simétrico) es así:
• Recorrer el subárbol izquierdo en orden
• Visitar la raíz.
• Recorrer el subárbol derecho en orden.
El recorrido en orden posterior se presenta de la siguiente manera.
• Recorrer el subárbol izquierdo en orden posterior.
• Recorrer el subárbol derecho en orden posterior.
• Visitar la raíz.
Existe un árbol binario que presenta la propiedad de que todos los elementos
...