Recorridos de árboles

Se puede hacer un recorrido de un árbol en profundidad o en anchura. Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno de los hijos. El coste de recorrer el ABB es O(n), ya que se necesitan visitar todos los vértices (Academy, 2018). 

El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inorden, preorden y postorden. Una propiedad de los ABB es que al hacer un recorrido en profundidad inorden obtenemos los elementos ordenados de forma ascendente  (Academy, 2018). 

El recorrido de un árbol es el proceso para recorrer (desplazarse a lo largo) un árbol de manera sistemática a fin de que cada vértice se visite y procese exactamente una vez .Hay tres métodos para recorrer un árbol binario a saber recorridos de pre orden de in orden y de pos orden (Weebly, 2016). 

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.

Entreorden:

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 (Weebly, 2016).

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. La Figura 5 muestra una versión limitada de un libro con sólo dos capítulos. Tenga en cuenta que el algoritmo de recorrido funciona para árboles con cualquier número de hijos, pero nos limitaremos a los árboles binarios por ahora (Academy, 2018).

En los siguientes videos encontraras información que te retroalimentara más acerca del tema: 

Referencias

Academy (2018) 6.8. Recorridos de árboles — Solución de problemas con algoritmos y estructuras de datos, Runestone.academy. Disponible en: https://runestone.academy/ns/books/published/pythoned/Trees/RecorridosDeArboles.html (Consultado: el 18 de noviembre de 2023).

Weebly (2016) Recorrido, Matemáticas Discretas. Disponible en: https://arboles12.weebly.com/recorrido.html (Consultado: el 18 de noviembre de 2023).

Matemática, A. (2020) RECORRIDO EN ARBOLES (Matemática discreta). Youtube. Disponible en: https://www.youtube.com/watch?v=1OaWFB2XjDo (Consultado: el 18 de noviembre de 2023).

Code, A. [@AsimovCode]. (2021, noviembre 8). Árboles Binarios y cómo recorrerlos | Matemática Discreta. Youtube. https://www.youtube.com/watch?v=rmvxvipV8O4