Estructura de Datos: Árboles y Árboles Binarios de Búsqueda (ABB)

*Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

* En relación con otros nodos:

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.

Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

Los árboles tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre.

*En cuanto a la posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.

Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.

Nodo rama: Estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.

*Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.

Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.

Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.

Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

Los árboles de orden dos son bastante especiales. Estos árboles se conocen también como árboles binarios.

Recorridos por árboles:

El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo modo en que nos movíamos a través de las listas.

Lo que diferencia los distintos métodos de recorrer el árbol no es el sistema de hacerlo, sino el momento que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas, así existen tres tipos que son:

- Pre-orden: (Raíz - Izquierda – Derecha)

- In-orden: (Izquierda – Raíz - Derecha)

- Post-orden: (Izquierda - Derecha - Raíz)

Ejercicio: Responde a las siguientes preguntas:

a) ¿Cuántas aristas tiene un árbol con N nodos?

b) ¿Longitud de A a D?

c) ¿Longitud de C a K?

d) ¿Longitud de B a N?

e) ¿Longitud de B a B?

f) ¿Profundidad de A, B, C y F?

g) ¿Altura de B, C, I, F y del árbol?

Solución:

a) A = N - 1

b) 2

c) 2

d) 3

e) 0

f) 0, 1, 1 y 2

g) 3, 2, 1, 0 y 4

5. Muestra el resultado de recorrer en pre-orden, in-orden, post-orden y por

niveles el siguiente árbol:

Solución:

Pre-orden: + 5 * – / 8 4 1 2

In-orden: 5 + 8 / 4 – 1 * 2

Post-orden: 5 8 4 / 1 – 2 * +

Por niveles: + 5 * – 2 / 1 8 4

Árboles binarios:

Se trata de árboles de orden 2 en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo.

Declaración de tipos:

Como estamos trabajando con un árbol binario, sólo necesitamos una estructura para referirnos tanto a cualquiera de los nodos como al árbol completo. Recuerda que cualquier nodo puede ser considerado como la raíz de un árbol.

Insertar un elemento en un árbol ABB:

Diseñaremos una función que se ajuste al algoritmo:

1. Padre = NULL
2. nodo = Raíz
3. Bucle: mientras actual no sea un árbol vacío o hasta que se encuentre el elemento.
4. 1. Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo: Padre=nodo, nodo=nodo->izquierdo.
   2. Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho: Padre=nodo, nodo=nodo->derecho.
5. Si nodo no es NULL, el elemento está en el árbol, por lo tanto salimos.
6. Si Padre es NULL, el árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el nuevo elemento, que será la raíz del árbol.
7. Si el elemento es menor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol izquierdo de Padre.
8. Si el elemento es mayor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol derecho de Padre.