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.

Arboles:

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

También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Esto son definiciones simples. Pero las características que implican no lo son tanto.

Definiremos varios conceptos. 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 con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.

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: aunque esta definición apenas la usaremos, 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'.

Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.

Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.

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

En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un á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

...