Recorridos de árboles

El recorrido preorden es un tipo de recorrido en un árbol binario. En un recorrido preorden, primero se visita el nodo raíz, luego se recorren recursivamente el subárbol izquierdo y el subárbol derecho.

La secuencia de visitas en un recorrido preorden sigue este orden:

1. *Visita el nodo raíz.
2. *Recorre el subárbol izquierdo en preorden.
3. *Recorre el subárbol derecho en preorden.

Este tipo de recorrido es útil para realizar ciertas operaciones en los nodos del árbol, como imprimir todos los nodos en un orden específico, realizar cálculos o búsqueda, entre otros.

Ahora que hemos examinado la funcionalidad básica de nuestra estructura de datos árbol, es hora de mirar algunos patrones de uso adicionales para los árboles. Estos patrones de uso se pueden dividir en las tres maneras en que tenemos acceso a los nodos del árbol. Hay tres patrones de uso común para visitar todos los nodos de un árbol. La diferencia entre estos patrones es el orden en que es visitado cada nodo. Llamamos a estas visitas de los nodos un “recorrido”. Los tres recorridos que vamos a ver se llaman preorden, inorden y postorden. Comencemos definiendo estos tres recorridos con más cuidado, para luego mirar algunos ejemplos donde estos patrones son útiles.

Preorden

En un recorrido en preorden, visitamos primero el nodo raíz, luego recursivamente realizamos un recorrido en preorden del subárbol izquierdo, seguido de un recorrido recursivo en preorden del subárbol derecho.

Inorden

En un recorrido en inorden, realizamos recursivamente un recorrido en inorden en el subárbol izquierdo, visitamos el nodo raíz, y finalmente hacemos un recorrido recursivo en inorden del subárbol derecho.

Postorden

En un recorrido en postorden, realizamos recursivamente recorridos en postorden del subárbol izquierdo y del subárbol derecho seguidos de una visita al nodo raíz.

Veamos algunos ejemplos que ilustran cada uno de estos tres tipos de recorridos. Primero veamos el recorrido en preorden. Como ejemplo de un árbol a recorrer, representaremos este libro como un árbol. El libro es la raíz del árbol, y cada capítulo es un hijo de la raíz. Cada sección dentro de un capítulo es un hijo del capítulo, y cada subsección es un hijo de su sección, y así sucesivamente.