Nomenclatura sobre árboles. Declaración de árbol binario

Definición de árbol

Un árbol es una estructura de datos, que puede definirse de forma recursiva como:

- Una estructura vacía o

- Un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol binario.

Es, por tanto, una estructura no secuencial.

Otra definición nos da el árbol como un tipo de grafo (ver grafos): un árbol es un grafo acíclico, conexo y no dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par de nodos. Esta definición permite implementar un árbol y sus operaciones empleando las representaciones que se utilizan para los grafos. Sin embargo, en esta sección no se tratará esta implementación.

Formas de representación

- Mediante un grafo:

Figura 1

- Mediante un diagrama encolumnado:

a

b

d

c

e

f

En la computación se utiliza mucho una estructura de datos, que son los árboles binarios. Estos árboles tienen 0, 1 ó 2 descendientes como máximo. El árbol de la figura anterior es un ejemplo válido de árbol binario.

Nomenclatura sobre árboles

- Raíz: es aquel elemento que no tiene antecesor; ejemplo: a.

- Rama: arista entre dos nodos.

- Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.

- Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.

- Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2.

- Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d

- Nodo interno: aquel que tiene al menos un descendiente.

- Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3.

- Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3.

- Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.

Aclaraciones: se ha denominado a a la raíz, pero se puede observar según la figura que cualquier nodo podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que b fuera la raíz, y a y d los sucesores inmediatos de la raíz b. Sin embargo, en las implementaciones sobre un computador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz.

Declaración de árbol binario

Se definirá el árbol con una clave de tipo entero (puede ser cualquier otra tipo de datos) y dos hijos: izquierdo (izq) y derecho (der). Para representar los enlaces con los hijos se utilizan punteros. El árbol vacío se representará con un puntero nulo.

Un árbol binario puede declararse de la siguiente manera:

typedef struct tarbol

{

int clave;

struct tarbol *izq,*der;

} tarbol;

Otras declaraciones también añaden un enlace al nodo padre, pero no se estudiarán aquí.

Recorridos sobre árboles binarios

Se consideran dos tipos de recorrido: recorrido en profundidad y recorrido en anchura o a nivel. Puesto que los árboles no son secuenciales como las listas, hay que buscar estrategias alternativas para visitar todos los nodos.

- Recorridos en profundidad:

* Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser simplemente mostrar la clave del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por naturaleza.

Si se hace el recorrido en preorden del árbol de la figura 1 las visitas serían en el orden siguiente: a,b,d,c,e,f.

void preorden(tarbol *a)

{

if (a != NULL) {

visitar(a);

preorden(a->izq);

preorden(a->der);

}

}

* Recorrido en inorden u orden central: se visita el subárbol izquierdo, el nodo actual, y después se visita el subárbol derecho. En el ejemplo de la figura 1 las visitas serían en este orden: b,d,a,e,c,f.

void inorden(tarbol *a)

{

if (a != NULL) {

inorden(a->izq);

visitar(a);

inorden(a->der);

}

}

* Recorrido en postorden: se visitan primero el subárbol izquierdo, después el subárbol derecho, y por último el nodo actual. En el ejemplo de la figura 1 el recorrido quedaría así: d,b,e,f,c,a.

void postorden(arbol *a)

{

if (a != NULL) {

postorden(a->izq);

postorden(a->der);

visitar(a);

}

}

La ventaja del recorrido en postorden es que permite borrar el árbol de forma consistente. Es decir, si visitar se traduce por borrar el nodo actual, al ejecutar este recorrido se borrará el árbol o subárbol que se pasa como parámetro. La razón para hacer esto es que no se debe borrar un nodo y después sus subárboles, porque al borrarlo se pueden perder los enlaces, y aunque no se perdieran se rompe con la regla de manipular una estructura de datos inexistente. Una alternativa es utilizar una variable auxiliar, pero es innecesario aplicando este recorrido.

- Recorrido en amplitud:

Consiste en ir visitando el árbol por niveles. Primero se visitan los nodos de nivel 1 (como mucho hay uno, la raíz), después los nodos de nivel 2, así hasta que ya no queden más.

Si se hace el recorrido en amplitud del árbol de la figura una visitaría los nodos en este orden: a,b,c,d,e,f

En este caso el recorrido no se realizará de forma recursiva sino iterativa, utilizando una cola (ver Colas) como estructura de datos auxiliar. El procedimiento consiste en encolar (si no están vacíos) los subárboles izquierdo y derecho del nodo extraido de la cola, y seguir desencolando y encolando hasta que la cola esté vacía.

En la codificación que viene a continuación no se implementan las operaciones sobre colas.

void amplitud(tarbol *a)

{

tCola cola; /* las claves de la cola serán de tipo árbol binario */

arbol *aux;

if (a != NULL) {

CrearCola(cola);

encolar(cola, a);

while (!colavacia(cola)) {

desencolar(cola, aux);

visitar(aux);

if (aux->izq != NULL) encolar(cola, aux->izq);

if (aux->der != NULL) encolar(cola, aux->der);

}

}

}

Por último, considérese la sustitución de la cola por una pila en el recorrido en amplitud. ¿Qué tipo de recorrido se obtiene?

Construcción de un árbol binario

Hasta el momento se ha visto la declaración y recorrido de un árbol binario. Sin embargo no se ha estudiado ningún método para crearlos. A continuación se estudia un método para crear un árbol binario que no tenga claves repetidas partiendo de su recorrido en preorden e inorden, almacenados en sendos arrays.

Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es sencillo cuando uno es capaz de construir el árbol viendo sus recorridos pero sin haber visto el árbol terminado.

Partiendo de los recorridos preorden e inorden del árbol de la figura 1 puede determinarse que la raíz es el primer elemento del recorrido en preorden. Ese elemento se busca en el array inorden. Los elementos en el array inorden entre izq y la raíz forman el subárbol izquierdo. Asimismo los elementos entre der y la raíz forman el subárbol derecho. Por tanto se tiene este árbol:

A continuación comienza un proceso recursivo. Se procede a crear el subárbol izquierdo, cuyo tamaño está limitado por los índices izq y der. La siguiente posición en el recorrido en preorden es la raíz de este subárbol. Queda esto:

El subárbol b tiene un subárbol derecho, que no tiene ningún descendiente, tal y como indican los índices izq y der. Se ha obtenido el subárbol izquierdo completo de la raíz a, puesto que b no tiene subárbol izquierdo:

Después seguirá construyéndose el subárbol derecho a partir de la raíz a.

La implementación de la construcción de un árbol partiendo de los recorridos en preorden y en inorden puede consultarse aquí (en C).

Árbol binario de búsqueda

Un árbol binario de búsqueda es aquel que es:

- Una estructura vacía o

- Un elemento o clave de información (nodo) más un número finito -a lo sumo dos- de estructuras tipo árbol, disjuntos, llamados subárboles y además cumplen lo siguiente:

* Todas las claves del subárbol izquierdo al nodo son menores que la clave del nodo.

* Todas las claves del subárbol derecho al nodo son mayores que la clave del nodo.

* Ambos subárboles son árboles binarios de búsqueda.

Un ejemplo de árbol binario de búsqueda:

Figura 5

Al definir el tipo de datos que representa la clave de un nodo dentro de un árbol binario de búsqueda es necesario que en dicho tipo se pueda establecer una relación de orden. Por ejemplo, suponer que el tipo de datos de la clave es un puntero (da igual a lo que apunte). Si se codifica el árbol en Pascal no se puede establecer una relación de orden para las claves, puesto que Pascal no admite determinar si un puntero

...