Tipos de recorrido de un árbol

Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden específico, los recorridos nos pueden ayudar a encontrar un nodo en el árbol, o buscar una posición determinada para insertar o eliminar un nodo.

Básicamente podemos catalogar las búsqueda en dos tipos, las búsqueda en profundidad y las búsquedas en amplitud.

Búsquedas no informadas

Las búsquedas no informadas son aquellas en que se realiza el viaje por todo el árbol sin tener una pista de donde pueda estar el dato deseado. Este tipo de búsquedas también se conocen como búsquedas a ciegas.

Las siguientes métodos de búsqueda que veremos a continuación (Búsqueda en profundad y Búsqueda en amplitud) pertenecen a  las búsquedas no informadas.

Búsqueda en profundidad

Recorrido Pre-orden: El recorrido inicia en la Raíz y luego se recorre en pre-orden cada unos de los sub-árboles de izquierda a derecha. En pre-orden, la raíz se recorre antes que los recorridos de los sub-árboles izquierdo y derecho.

1. Ir a la raíz
2. Atravesar el sub-árbol izquierdo.
3. Atravesar el sub-árbol derecho.

Recorrido el árbol iniciando desde la Raíz.

Recorrido Pos-orden: Se recorre el pos-orden cada uno de los sub-árboles y al final se recorre la raíz.

1. Atravesar el sub-árbol izquierdo.
2. Atravesar el sub-árbol derecho.
3. Ir a la raíz.

El primer nodo que se imprime no es la Raíz pues en este recorrido la Raíz de cada Sub-Árbol es procesado al final, ya que toda su descendencia ha sido procesada.

Recorrido in-orden: Se recorre en in-orden el primer sub-árbol, luego se recorre la raíz y al final se recorre en in-orden los demás sub-árboles.

1. Atravesar el sub-árbol izquierdo.
2. Ir a la raíz.
3. Atravesar el sub-árbol derecho.

La Raíz no es el primero elemento en ser impreso, pues este recorrido recorre su rama izquierda, luego la raíz del sub-árbol y luego la rama derecha.

Búsqueda en amplitud.

Se recorre primero la raíz, luego se recorren los demás nodos ordenados por el nivel al que pertenecen en orden de Izquierda a derecha.

Este tipo de búsqueda se caracteriza por que la búsqueda se hace nivel por nivel y de izquierda a derecha.

El nodo es buscado mediante la búsqueda en profundidad.

El algoritmo se detiene cuando el elemento buscado es encontrado.

Índice:

1. ¿Qué es un árbol?
• Estructura
• Árboles libres y orientados
2. Propiedades
3. Tipos de recorridos de un árbol
4. Bibliografía