arbol binario

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Superior
Instituto Universitario de Tecnología de Administración Industrial (IUTA)
Maracay-Aragua





















(Maracay, Julio de 2014)
Á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 doshijos (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. Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones endistintos puntos. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman. Los Árboles tienen 3 Recorridos Diferentes los cuales son: Pre-Orden, In-Orden y Post-Orden
PRE-ORDEN
El Recorrido “Pre-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en la Raíz, después viaje a travésdel Nodo Izquierdo y después a través del Nodo Derecho.

Pre-Ord (Árbol, Der, Izq., Pila, Raíz)
Temp → Raíz
Top →
Pila [Top] → Nulo
Si Raíz = Nulo
Imprimir “Árbol Vació…” y Salir
Repetir mientras Temp ≠ Nulo
Imprimir Árbol [Temp]
Si Der [Temp] ≠ Nulo
Top → Top + 1
Pila [Top] → Der [Temp]
Si Izq. [Temp] ≠ Nulo
Temp → Izq. [Temp]
Si no:
Temp → Pila [Top];
Top → Top - 1
Fin delciclo
Salir
IN-ORDEN
El Recorrido “In-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después la Raíz y finalmente viaja a través del Nodo Derecho. Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentrode él, lo recorrerá y viajara a través de los Arreglos Izq. y Der para determinar qué valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elemento correspondiente.

In-Ord (Árbol, Der, Izq., Pila, Raíz)
Temp → Raíz
Top →
Pila [Top] → Nulo
Si Raíz = Nulo
Imprimir “Árbol Vacío…” y Salir
Etiqueta:
Mientras Temp ≠ Nulo
Top → Top + 1
Pila [Top] → Temp
Temp → Izq.[Temp]
Fin del ciclo
Temp → Pila [Top]
Top → Top - 1
Mientras Temp ≠ Nulo
Imprimir Árbol [Temp]
Si Der [Temp] ≠ Nulo
Temp → Der [Temp]
Ir a Etiqueta
Temp → Pila [Top]
Top → Top - 1
Fin del ciclo
Salir


“POST-ORDEN”
El Recorrido “post-Orden” lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después el Nodo Derecho yfinalmente viaja a través de la Raíz. Temp toma el Valor de la Raíz y compara si el Árbol tiene algún Elemento, de otra manera Desplegara “Árbol Vació…” y terminara el método. Si el Árbol tiene elementos dentro de él, lo recorrerá y viajara a través de los Arreglos Izq. y Der para determinar qué valor meter en la Pila y en Temp para de esta manera imprimir el siguiente Elementocorrespondiente.

Post-Ord (Árbol, Der, Izq., Pila, Raíz)
Temp → Raíz
Top →
Pila [Top] → Nulo
Si Raíz = Nulo
Imprimir “Árbol Vacío…” y Salir
Etiqueta:
Mientras Temp ≠ Nulo
Top → Top + 1
Pila [Top] → Temp
Si Der [Temp] ≠ Nulo
Top → Top + 1
Pila [Top] → - (Der [Temp])
Temp → Izq. [Temp]
Temp → Pila [Top]
Top → Top - 1
Fin del ciclo
Mientras Temp ≥ 0
Imprimir Árbol [Temp]
Si Árbol [Temp] =Info [Raíz]
Salir
Temp → Pila [Top]
Top → Top - 1
Fin del ciclo
Si Temp < 0
Temp = -(Temp)
Ir a Etiqueta
Salir
Códigos fuentes de árbol binario

1) //programa que captura una cadena de caracteres de maximo 200 elementos y
//crea un arbol de busqueda con los caracteres de la cadena y realiza recorridos
// en preorden, entreorden y postorden.
#include
#include
#include
#include...