Arboles Binarios

Arboles Binarios de Búsqueda en C++ Recorrido por niveles (Amplitud)

¿Qué es un árbol?

Un árbol es una estructura de datos no lineal puesto que cada elemento apunta a uno o varios elementos del mismo tipo; esto es dado un elemento, no hay un único camino a seguir. El elemento que apunta a otro es llamado padre, mientras que el elemento apuntado se conoce como hijo. Todos los elementos tienen un padre a excepción de la raíz. Puede decirse que un árbol está formado por subárboles resaltando así su naturaleza recursiva.

¿Qué es un árbol binario?

Un ARBOL BINARIO es aquel que cada elemento apunta como máximo a otros 2 elementos, comúnmente llamados hijo izquierdo e hijo derecho.

¿Qué es un árbol binario de búsqueda?

Un árbol binario de buque da o ABB, es un árbol binario en el cual para todo elemento, los elementos mayores a él, se ubican en su rama derecha, mientras que los elementos menores van en su rama izquierda. Cada elemento se almacena una sola vez por lo que no existen elementos repetidos.

Ya con estas definiciones claras sobre arboles; ahora estos son conceptos generales de lo que es un árbol, para poder implementarlos en lenguaje C++ tenemos que tener conocimientos previos sobre listas enlazadas y su implementación.

Cada elemento (nodo) de un árbol ABB cuenta con tres campos:

- Dato (número, letra, palabra, etc.), en este caso usaremos un número (entero).

- Puntero al nodo derecho

- Puntero al nodo izquierdo

Los punteros tienen que ser del tipo árbol, ya que apuntaran a un nodo del mismo tipo, este sería un ejemplo de cómo sería el tipo árbol ABB.

Primero creamos el nodo:

struct nodo{

int dato;

struct nodo *der;

struct nodo *izq;

};

"Los punteros son variables que guardaran en la memoria la dirección de otra variable" en este caso la de una estructura llamado nodo.

Recorridos de una árbol

Es la manera recursiva como pasaremos por cada nodo del árbol, existes tres formas.

Enorden: Si visitamos primero hijo izquierdo, luego el padre y finalmente el hijo derecho

Preorden: Primero el padre, luego el hijo izquierdo y finalmente el hijo derecho.

Postorden: Primero hijo izquierdo, luego el hijo derecho y finalmente el padre

Existe muchos más conceptos sobre arboles ABB por ejemplo, recorridos por nivel, profundidad de una árbol, etc.; por ahora solo dejare esos conceptos. Ahora pasaremos a la implementación en lenguaje C++ como le había comentado al inicio del post.

Para borrar un elemento también nos basamos en el algoritmo de búsqueda. Si el elemento no está en el árbol no lo podremos borrar. Si está, hay dos casos posibles:

1. Se trata de un nodo hoja: en ese caso lo borraremos directamente.

2. Se trata de un nodo rama: en ese caso no podemos eliminarlo, puesto que perderíamos todos los elementos del árbol de que el nodo actual es padre. En su lugar buscamos el nodo más a la izquierda del subárbol derecho, o el más a la derecha del subárbol izquierdo e intercambiamos sus valores. A continuación eliminamos el nodo hoja.

Necesitamos un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL.

• Padre = NULL

• Si el árbol está vacío: el elemento no está en el árbol, por lo tanto salimos sin eliminar ningún elemento.

• (1) Si el valor del nodo raíz es igual que el del elemento que buscamos, estamos ante uno de los siguientes casos:

o El nodo raíz es un nodo hoja:

 Si 'Padre' es NULL, el nodo raíz es el único del árbol, por lo tanto el puntero al árbol debe ser NULL.

 Si raíz es la rama derecha de 'Padre', hacemos que esa rama apunte a NULL.

 Si raíz es la rama izquierda de 'Padre', hacemos que esa rama apunte a NULL.

 Eliminamos el nodo, y salimos.

o El nodo no es un nodo hoja:

 Buscamos el 'nodo' más a la izquierda del árbol derecho de raíz o el más a la derecha del árbol izquierdo. Hay que tener en cuenta que puede que sólo exista uno de esos árboles. Al mismo tiempo, actualizamos 'Padre' para que apunte al padre de 'nodo'.

 Intercambiamos los elementos de los nodos raíz y 'nodo'.

 Borramos el nodo 'nodo'. Esto significa volver a (1), ya que puede suceder que 'nodo' no sea un nodo hoja. (Ver ejemplo 3)

• Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.

• Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

Calcular la altura de un nodo.

No hay un modo directo de hacer esto, ya que no nos es posible recorrer el árbol en la dirección de la raíz. De modo que tendremos que recurrir a otra técnica para calcular la altura.

Lo que haremos es buscar el elemento del nodo de que queremos averiguar la altura. Cada vez que avancemos un nodo incrementamos la variable que contendrá la altura del nodo.

• Empezamos con el nodo raíz apuntando a Raiz, y la 'Altura' igual a cero.

• Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda y el valor de la altura es 'Altura'.

• Incrementamos 'Altura'.

• Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.

• Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

Calcular la altura de un árbol.

La altura del árbol es la altura del nodo de mayor altura. Para buscar este valor tendremos que recorrer todo el árbol, de nuevo es indiferente el tipo de recorrido que hagamos, cada vez que cambiemos de nivel incrementamos la variable que contiene la altura del nodo actual, cuando lleguemos a un nodo hoja compararemos su altura con la variable que contiene la altura del árbol si es mayor, actualizamos la altura del árbol.

• Iniciamos un recorrido del árbol en postorden, con la variable de altura igual a cero.

• Cada vez que empecemos a recorrer una nueva rama, incrementamos la altura para ese nodo.

• Después de procesar las dos ramas, verificamos si la altura del nodo es mayor que la variable que almacena la altura actual del árbol, si es así, actualizamos esa variable.

...