Articulos de interes



Curso online gratuito - POO y Java - Click Aquí

Exploración de Árboles

Los á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:

Exploracion

En el siguiente árbol ejemplo,

Arbol

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.

Exploracion

En el árbol ejemplo,

Arbol

la impresión resultado sería:

d

b

e

a

c

La implementación del algoritmo de recorrido en postorden es muy parecida:

Exploracion

En el árbol ejemplo,

Arbol

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:

Exploracion



Nombre:

Email:

Comentario: