Recorridos En Un Arbol

3.7.4 Recorridos en un Árbol

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 mas lejano del primer hijo, antes de proseguir con el segundo. Recorrido en Anchura: el proceso se realiza horizontalmente desde la raíz a todos su hijos antes de pasar con la descendencia de alguno de ellos.

Primeramente se ven los algorítmos 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 en-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 raíz • Recorrer el subárbol izquierdo en pre-orden • Recorrer el subárbol derecho en pre-orden

Recorrido EN-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 raíz

Recorridos

Si T es un árbol con raíz n y subárboles T1, T2, . . . , Tk, entonces, El listado pre-orden de los nodos de T es la raíz n, seguida por los nodos de T1 en pre-orden, después los nodos de T2 en preorden, y así, hasta los nodos de Tk en pre-orden. El listado post-orden de los nodos de T es los nodos de T1 en postorden, seguidos de los nodos de T2 en post-orden, y así hasta los nodos de Tk en post-orden, todos ellos seguidos de n. El listado en-orden de los nodos de T es los nodos de T1 en-orden, seguidos por n, seguidos por los nodos de T2, . . . , Tk, cada grupo.