Tipos de recorrido de un árbol

Tipos de recorrido

*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.

-Vídeos con respecto al tipo de recorrido:

*Post-orden: https://www.youtube.com/watch?v=sHyqUUTIvzQ
*In-orden: https://www.youtube.com/watch?v=LjeI9Py_z4E

*Pre-orden: https://www.youtube.com/watch?v=gSsG5fFme3w

-Bibliografia utilizada:

*Wikipedia/ Recorrido en Arboles.(Junio de 2018). Obtenido de https://es.wikipedia.org/wiki/Recorrido_de_%C3%A1rboles

*Wikipedians. (2015). Algoritmos y estructuras de datos. Brandenburg, Germany: Fachbereich Informatik und Medien. Obtenido de https://www.researchgate.net/profile/Reiner_Creutzburg/publication/277814853_Algoritmos_y_Estructura_de_Datos_Parte_7_Arboles_y_Graficas/links/558fdefd08ae1e1f9badf8e6/Algoritmos-y-Estructura-de-Datos-Parte-7-Arboles-y-Graficas.pdf