5.3 Algoritmo de recorrido y busqueda

 5.3 Algoritmo de recorrida y busqueda

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.

Recorreremos el Árbol Siguiente:

Recorrido Pre Orden (RID)

El recorrido en Pre Orden del árbol es el siguiente: 15, 6, 4, 10, 20, 17, 22

Recorrido En Orden(IRD)

El recorrido en En Orden del árbol es el siguiente: 4, 6, 10, 15, 17, 20, 22

Recorrido Post Orden(IDR)

El recorrido en Post Orden del árbol es el siguiente: 4, 10, 6, 17, 22, 20, 15

En este tema trataremos las diferentes formas de hacer recorridos de un árbol de una expresión algebraica, con el fin de poder cambiar de manera algorítmica una expresió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 elementos del árbol para examinar el conjunto completo. Primeramente se ven los algoritmos para construir el árbol, para la expresión dada en sufijo, prefijo o posfijo y también se presentan algoritmos para reconocer si una expresión está correcta cuando esta dada en prefijo o posfijo.

Recorridos

Al visitar los elementos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente. Los ordenamientos más importantes son llamados: prefijo, sufijo y posfijo.

Los algoritmos de recorrido de un árbol presentan tres tipos de actividades

• 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 PREFIJO:

• Visitar la raíz
• Recorrer el subárbol izquierdo en prefijo
• Recorrer el subárbol derecho en prefijo

Recorrido SUFIJO:

• Recorrer el subárbol izquierdo en sufijo
• Visitar la raíz
• Recorrer el subárbol derecho en sufijo

Recorrido en POSFIJO:

• Recorrer el subárbol izquierdo en postfijo
• Recorrer el subárbol derecho en postfijo
• Visitar la raíz
• 
  

Flores, I. (22 de 11 de 2014). Relaciones y teoría de grafos. Obtenido de Relaciones y teoría de grafos.: http://equipo1mditq.blogspot.mx/2014/11/63-algoritmos-de-recorrido-y-busqueda.html