ARBOLES

Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.

Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas.

La definición de árbol es la siguiente: es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc... Formalmente se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de árboles disjuntos, llamados subárboles. Una forma particular de árbol puede ser la estructura vacía.

La figura siguiente representa a un árbol general.


Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos.

Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro.

Terminología

La terminología que por lo regular se utiliza para el manejo de árboles es la siguiente:

HIJO. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.

PADRE. X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.

HERMANO. Dos nodos serán hermanos si son descendientes directos de un mismo nodo.

HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).

NODO INTERIOR. Es un nodo que no es raíz ni terminal.

GRADO. Es el número de descendientes directos de un determinado nodo.

GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol.

NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

ALTURA. Es el máximo número de niveles de todos los nodos del árbol.

PESO. Es el número de nodos del árbol sin contar la raíz.

LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

Transformación de un Árbol Gral. en un Árbol Binario.

En esta sección estableceremos los mecanismos necesarios para convertir un árbol general en un árbol binario. Para esto, debemos seguir los pasos que se describen a continuación:

1. Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
2. Enlazar en forma vertical el nodo padre con el nodo hijo que se encuentra más a la izquierda. Además, debe eliminarse el vínculo de ese padre con el resto de sus hijos.
3. Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda, y así se obtendrá el árbol binario correspondiente.



ÁRBOLES BINARIOS

Introducción

A los árboles ordenados de grado dos se les conocen como árboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los árboles 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áfica de 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án representados 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 subárbol izquierdo y derecho del subárbol 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:.

· B. Distinto.
· B. Similares.
· B. Equivalentes.
· 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 árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.



Recorrido de un Arbol Binario

Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:

INORDEN
· Recorrer el subárbol izquierdo en inorden.
· Examinar la raíz.
· Recorrer el subárbol derecho en inorden.

PREORDEN
· Examinar la raíz.
· Recorrer el subárbol izquierdo en preorden.
· recorrer el subárbol derecho en preorden.

POSTORDEN
· Recorrer el subárbol izquierdo en postorden.
· Recorrer el subárbol derecho 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

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 la derecha.


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 árboles 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 el lenguaje 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.

#include // Para gets() y puts()
#include // Para clrscr() y gotoxy()
#include // Para strlen()

void main()
{
char nombre[31];
clrscr();
gotoxy(10,1);
puts("¿ Cuál es tu nombre ? ");
gotoxy(35,1);
gets(nombre);
clrscr();
gotoxy (10,1);
puts("ELEMENTO CARACTER DIRECCION");
for( int x=0 ; (x < x,nombre[x],nombre[x],&nombre[x]); u?, c="%4d" printf(?nombre[%2d] gotoxy(10,x+2); x++) x


Árboles en Montón

Esta sección consiste en transformar un bosque en un árbol binario. Entenderemos como bosque a un conjunto normalmente ordenado de dos o más árboles generales.

La serie de pasos que debemos seguir para lograr la conversión de un bosque en un árbol binario es la siguiente:

1. Enlazar horizontalmente las raíces de los distintos árboles generales.
2. Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
3. Enlazar verticalmente el nodo padre con el hijo que se encuentra más a la izquierda. Además debe eliminarse el vínculo de ese padre con el resto de sus hijos.
4. Debe rotarse el diagrama resultante aproximadamente 45 grados hacia la izquierda y así se obtendrá el árbol binario correspondiente.

Árboles binarios de búsqueda

Un árbol de búsqueda binaria es una estructura apropiada para muchas de las aplicaciones que se han discutido anteriormente con listas. La ventaja especial de utilizar un árbol es que se facilita la búsqueda.

Un árbol binario de búsqueda es aquel en el que el hijo de la izquierda (si existe) de cualquier nodo contiene un valor más pequeño que el nodo padre, y el hijo de la derecha (si existe) contiene un valor más grande que el nodo padre.
Un ejemplo de árbol binario de búsqueda es el siguiente:








EJERCICIOS PROPUESTOS

Escriba un algoritmo para determinar el número de hojas de un árbol binario representado como lista ligada.

Escriba un algoritmo para determinar el grado de un árbol binario representado como lista ligada.

Escriba el algoritmo para determinar la altura de un árbol binario representado como lista ligada.

Escriba el algoritmo para determinar el número de hojas de un árbol representado como lista.

Escriba un algoritmo para determinar el grado de un árbol representado como lista.

Escriba el algoritmo para determinar la altura de un árbol representado como lista.

Elabore un algoritmo para construir un árbol binario el cual le dieron los recorridos POSORDEN e INORDEN

Elabore un algoritmo para determinar el numero de hojas, el grado y la altura de un árbol teniéndolos representados como listas ligadas enhebradas.

Escribir un programa para ordenar una secuencia de números usando un árbol binario. Un árbol binario es una estructura tipo árbol con solamente 2 (posibles) ramas de cada nodo. Cada rama entonces representa una decisión de falso o verdadero. Para ordenar los números simplemente asignar a la rama izquierda los números menores respecto al número del nodo, y en la rama derecha el resto (es decir, los que son mayores o iguales a).

Por lo tanto, si la lista de entrada es: 14 15 4 9 7 18 3 5 16 4 20 17 0 14 5, se debe generar el árbol:



Árbol binario.


Para obtener una lista ordenada en forma ascendente, recorrer el árbol en preorden, es decir, visitar la raíz, recorrer el subárbol izquierdo en orden y recorrer el subárbol derecho en orden. Por lo que la salida deberá ser:

Los valores ordenados son: 0 3 4 4 5 5 7 9 14 14 15 16 17 18 20

Elabore un algoritmo que borre un registro de un árbol AVL.