OpcionesLos árboles son estructuras de datos usadas cuando se quieren manejar rápidamente gran cantidad de datos. A menudo querremos realizar operaciones sobre los nodos del árbol para lo que necesitaremos explorarlo. A pesar de la variedad
de algoritmos, en todos ellos deberemos visitar todos los nodos o lo que es lo mismo recorrer el árbol.
Existen dos formas principales para recorrer un árbol:
- Profundidad, que engloba recorridos que se realizarán de forma recursiva.
- Anchura que seguirá la estructura de niveles del árbol.
Existen tres formas de recorrer un árbol en profundidad:
- Preorden. El tratamiento de la raíz se realiza primero y luego el de los hijos, siendo el orden de recorrido raiz, hijoIzquierdo, hijoDerecho.
- Inorden. El tratamiento de la raíz se realiza entre el de los subárboles. El orden del recorrido será hijoIzquierdo, raíz, hijoDerecho.
- Postorden. Se realiza el tratamiento de los hijos y se deja para el final el de la raíz quedando un orden de recorrido hijoIzquierdo, hijoDerecho, raíz.
Los recorridos en profundidad son muy sencillos de implementar ya que siguen la estructura recursiva del árbol. Veremos la implementación de los distintos recorridos en Java:
Veremos un método que imprime el contenido de un árbol en preorden. El algoritmo consta de tres pasos:
- Imprimir nodo raíz
- Llamada recursiva al método con el hijo izquierdo
- Llamada recursiva al método con el hijo derecho
quedando la implementación como sigue:
En el siguiente árbol ejemplo:
la impresión resultado sería:
a
b
d
e
c
El algoritmo de recorrido inorden es similar salvo que la raíz se imprimirá después de haber impreso todo el subárbol correspondiente al hijo izquierdo. Por tanto la primera llamada recursiva será a ImprimirEnInorden con el hijo
izquierdo. Después se imprimirá la raiz y por último la llamada a ImprimirEnInorden con el hijo derecho.
En el árbol ejemplo:
la impresión resultado sería:
d
b
e
a
c
La implementación del algoritmo de recorrido en postorden es muy parecida:
En el árbol ejemplo:
la impresión resultado sería:
d
e
b
c
a
Aunque existen distintas formas de recorrer un árbol en anchura, nosotros estudiaremos la manera más usual, de izquierda a derecha y descendente.
Para la implementación se utilizará una cola donde se almacenarán los nodos que deben ser visitados. El primer elemento que se insertará en la cola será el árbol.
El algoritmo irá extrayendo de la cabeza de la cola el árbol correspondiente. Cuando se extrae la cabeza obtendremos un subárbol. Realizaremos el tratamiento correspondiente con el nodo raíz y
los hijos los insertaremos en la cola de la cola.
Este proceso se realizará de forma iterativa hasta que la cola se quede vacía. Lo último que nos quedaría por concretar es qué sucede cuando llegamos a un árbol que está compuesto por un único nodo hoja. En este caso no insertaremos
ningún subárbol en la cola puesto que no éste no tiene.
La implementación en Java de un procedimiento que imprime el contenido de los nodos recorriendo el árbol en anchura quedaría:
