ARBOLES BINARIOS PRI

ARBOLES BINARIOS
Introducción
A los arboles ordenados de grado dos se les conoce como arboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. 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 en distintos puntos.
La representación gráficade un árbol binario es la siguiente:

Representación en Memoria
Hay dos formas tradicionales de representar un árbol binario en memoria:
Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
Por medio de arreglos.
Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.
Los nodos del árbol binario seránrepresentados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.
Cada nodo se representa gráficamente de la siguiente manera:

El algoritmo de creación de un árbol binario es el siguiente:
Procedimiento crear(q:nodo)
inicio
mensaje("Rama izquierda?")lee(respuesta)
si respuesta = "si" entonces
new(p)
q(li) <-- nil
crear(p)
en caso contrario
q(li) <-- nil
mensaje("Rama derecha?")
lee(respuesta)
si respuesta="si" entonces
new(p)
q(ld)<--p
crear(p)
en caso contrario
q(ld) <--nil
fin
INICIO
new(p)
raiz<--p
crear(p)
FIN
Clasificación de Árboles Binarios
Existen cuatro tipos de árbol binario:.
A. B. Distinto.
A. B. Similares.
A. B. Equivalentes.
A.B. Completos.
A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.
A. B. DISTINTO
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:

A. B. SIMILARES
Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.Ejemplo:

A. B. EQUIVALENTES
Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:

A. B. COMPLETOS
Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho
Recorrido de un Árbol Binario
Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada unade ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:
INORDEN
Recorrer el subarbol izquierdo en inorden.
Examinar la raíz.
Recorrer el subarbol derecho en inorden.
PREORDEN
Examinar la raíz.
Recorrer el subarbol izquierdo en preorden.
recorrer el subarbol derecho en preorden.
POSTORDEN
Recorrer el subarbol izquierdo en postorden.
Recorrer el subarbolderecho en postorden.
Examinar la raíz.
A continuación se muestra un ejemplo de los diferentes recorridos en un árbol binario.

Inorden: GDBHEIACJKF
Preorden: ABDGEHICFJK
Postorden: GDHIEBKJFCA
5.5 Arboles Enhebrados
Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol binario enhebrado a laderecha.

ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor.
ARBOL ENHEBRADO A LA IZQUIERDA. Estos arboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden
Control de Acceso a los Elementos de un Arreglo
En C++, el acceso a los elementos de un arreglo tiene que ser controlado por el programador, ya que ellenguaje no restringe la posibilidad de accesar a posiciones de memoria que están más abajo de la última posición reservada para el arreglo. Lo mismo sucede cuando se manejan cadenas, donde el programador tiene la responsabilidad de controlar el acceso a los caracteres de la cadena, tomando como límite el terminador nulo. En el listado 5.6 se presenta un ejemplo de acceso a los 5 bytes colocados abajo...