Actividad 1 U4y5

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,

...