*Las estructuras arborescentes pueden ser recorridas de
muchas maneras diferentes. Comenzando en la raíz de un árbol binario, hay tres
pasos principales que pueden ser realizados y el orden en la cual son
realizados define el tipo de recorrido. Estos pasos (en ningún orden
particular) son: ejecución de una acción en el nodo actual (referido como
“visitando” el nodo), recorriendo al nodo hijo de la izquierda, y recorriendo
al nodo hijo de la derecha. Así el proceso es más fácilmente descrito
a través de la recursión.
*Los
nombres dados para un estilo particular de recorrido vienen de la posición del
elemento de raíz con respecto a los nodos izquierdo y derecho. Los nodos
izquierdo y derecho son constantes en espacio, entonces el nodo raíz puede
colocarse a la izquierda del nodo izquierdo (pre-orden), entre el nodo
izquierdo y derecho (in-orden), o a la derecha del nodo derecho (post-orden).
>Recorrido en profundidad-primero:
El método de este recorrido es tratar de encontrar de la
cabecera a la raíz en nodo de unidad binaria.
*En arboles binarios:
*Pre-orden: En este tipo de recorrido se realiza
cierta acción sobre el nodo actual y posteriormente se trata el sub-árbol
izquierdo y cuando se haya concluido, el sub-árbol derecho. Otra forma para
entender el recorrido con este método seria seguir el orden: nodo raíz, nodo
izquierda, nodo derecha. Los pasos entonces serian:
1.
Visitar la raíz
2.
Atravesar el sub-árbol izquierdo
3.
Atravesar el sub-árbol derecho
*En el
árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.
*In-orden: En este caso se trata primero el sub-árbol izquierdo, después el nodo
actual y por último el sub-árbol derecho. Otra forma para entender el recorrido
con este método seria seguir el orden: nodo izquierda, nodo raíz, nodo derecha.
Los pasos entonces serian:
1.
Atravesar el sub-árbol izquierdo
2.
Visitar la raíz
3.
Atravesar el sub-árbol derecho
* En el
árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.
*Post-orden: En este caso se trata primero el sub-árbol izquierdo, después el
derecho y por último el nodo actual. Otra forma para entender el recorrido con
este método seria seguir el orden: nodo izquierda, nodo derecha, nodo raíz. Los
pasos entonces serian:
1.
Atravesar el sub-árbol izquierdo
2.
Atravesar el sub-árbol derecho
3.
Visitar la raíz
* En el árbol de la figura el recorrido en post-orden sería: 2, 5, 11, 6, 7,
4, 9, 5 y 2.
*Arboles
genéricos:
Para recorrer un árbol no vacío en
orden de profundidad-primero, hay que realizar las siguientes operaciones
recursivamente en cada nodo:
1. Realizar la operación pre-orden
2. Para i=1 a n-1 hacer
1. Visitar al hijo[i], si existe
2. Realizar la operación in-orden
3. Visitar al hijo[n], si existe
4. Realizar la operación post-orden
>Recorrido en amplitud (o por
niveles):
En este caso el recorrido se realiza en orden por los distintos niveles
del árbol. Así, se comenzaría tratando el nivel 1, que solo contiene el nodo
raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En el árbol de la
figura el recorrido en amplitud sería: 2, 7, 5, 2, 6, 9, 5, 11 y 4.
