RECORRIDO DE UN ARBOL

Se denomina recorrido de un árbol el proceso que permite acceder una sola vez a cada uno de los nodos del árbol. Cuando un árbol se recorre , el conjunto completo de nodos se examina.

Existen muchos modos para recorrer un árbol binario. Por ejemplo, existen seis diferentes recorridos generales en un árbol binario, simétricos dos a dos.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

Visitar el nodo raíz,

recorrer el subárbol izquierdo,

recorrer el subárbol derecho.

Estas tres acciones repartidas en diferentes órdenes proporcionan los diferentes recorridos del árbol. Los más frecuentes tienen siempre en común recorrer primero el subárbol izquierdo y luego el subárbol derecho. Los algoritmos anteriores se llaman pre-orden, post-orden, in-orden y su nombre refleja el momento en que se visita el nodo raíz. En el in-orden el raíz está en el medio del recorrido, en el pre-orden, el raíz está primero y en el post-orden el raíz está el último.

Recorrido pre-orden:

1.- Visitar el raíz.

2.- Recorrer el subárbol izquierdo en pre-orden.

3.- Recorrer el subárbol derecho en pre-orden.

Recorrido en-orden:

1.- Recorrer el subárbol izquierdo en in-orden.

2.- Visitar el raíz.

3.- Recorrer el subárbol derecho en in-orden.

Recorrido en post-orden:

1.- Recorrer el subárbol izquierdo en post-orden.

2.- Recorrer el subárbol derecho en post-orden.

3.- Visitar raíz.