Recorrido De Un Arbol

Recorridos en un Árbol

Tomado de http://www.mitecnologico.com/Main/RecorridosEnUnArbol

En este tema trataremos las diferentes formas de hacer recorridos en el árbol sintáctico de una expresión algebraica, con el fin de poder cambiar de manera algorítmica de una representación en sufijo a forma de prefijo o posfijo.

Se llama recorrido de un árbol al proceso que permite acceder una sola vez a cada uno de los nodos del árbol para examinar el conjunto completo de nodos.

Recorrido en Profundidad: El proceso exige alcanzar las profundidades de un camino desde la raíz hacia el descendiente más lejano del primer hijo, antes de proseguir con el segundo.

Recorrido en Anchura: el proceso se realiza horizontalmente desde la raíz a todos sus hijos antes de pasar con la descendencia de alguno de ellos.

Primeramente se ven los algoritmos para construir el árbol sintáctico, para la expresión dada en sufijo, prefijo o posfijo y también se presentan algoritmos para reconocer si una expresión está sintácticamente correcta cuando esta dada en prefijo o posfijo.

Recorridos

Al visitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol.

Los ordenamientos más importantes son llamados: preorden, post-orden y in-orden y se definen recursivamente como sigue:

Si un árbol T es nulo, entonces, la lista vacía es el listado preorden, post-orden y en-orden del árbol T.

Si T consiste de un sólo nodo n, entonces, n es el listado preorden, post-orden y en-orden del árbol T.

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 llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PRE-ORDEN:

• Visitar el nodo raíz

• Recorrer el subárbol izquierdo en pre-orden

• Recorrer el subárbol derecho en pre-orden

Recorrido IN-ORDEN

• Recorrer el subárbol izquierdo en en-orden

• Visitar el raíz

• Recorrer el subárbol derecho en en-orden

Recorrido en POST-ORDEN

• Recorrer el subárbol izquierdo en post-orden

• Recorrer el subárbol derecho en post-orden

• Visitar el nodo raíz

Recorreremos el Árbol Siguiente:

“

Recorrido Pre Orden (RID): 15, 6, 4, 10, 20, 17, 22

Recorrido En Orden (IRD): 4, 6, 10, 15, 17, 20, 22

Recorrido Post Orden (IDR): 4, 10, 6, 17, 22, 20, 15

Pre Orden (RID)

...