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
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.
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
Comparemos Otros Recorridos
Pre Orden (RID) 18, 12, 5, 9, 28, 20, 35
En Orden (IRD) 5, 9, 12, 18, 20, 28, 35
Post Orden (IDR) 9, 5, 12, 20, 35, 28, 18
A+B SUFIJO
+AB PREFIJO
AB+ POSFIJO
El arbol normal
(a+b) * c
*
A+b c
+
A b
I pre orden
d entre orden
r pos orden
idr posfijo
rid Prefijo
ird sufijo
3.7.4 Recorridos en un Árbol
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
Autor : Cuevas Flores Ricardo
Recorridos de un Arbol
Un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados).
Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a).
Sólo puede haber un único nodo sin padres, que llamaremos raíz.
Un nodo que no tiene hijos se conoce como hoja.
Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.
Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:
1. INORDEN(Sufijo)
Recorrer el subarbol izquierdo en inorden. Examinar la raíz. Recorrer el subarbol derecho en inorden.
2. PREORDEN(Prefijo)
Examinar la raíz. Recorrer el subárbol izquierdo en preorden. recorrer el subárbol derecho en preorden.
3. POSTORDEN(Posfijo)
Recorrer el subárbol izquierdo en postorden. Recorrer el subárbol derecho en postorden. Examinar la raíz.
un ejemplo para expresar en notacion POSFIJO.
consideremos la expresión:
A / B ** C + D * E – A * C
1. Parentizar completamente de acuerdo al orden de ejecución de los operadores. A cada operador le corresponderá
un paréntesis izquierdo y un paréntesis derecho.
(((A / (B ** C)) + (D * E)) – (A * C))
Los operadores se moverán a reemplazar su correspondiente paréntesis derecho.
Las flechas apuntan desde el operador hacia su correspondiente paréntesis derecho.
2. Al hacer los movimientos la expresión queda:
(((A (B C ** / (D E * + (AC * -
3. Rescribir la expresión suprimiendo los paréntesis izquierdos. La expresión quedará:
ABC ** / DE * + AC * -
Por: Cesar Lopez Gonzalez
BIBLIOGRAFIA:
www.cema.edu.ar/~rst/Teoria/7._Arboles_binarios.ppt
BIBLIOGRAFIA:
http://www.lcc.uma.es/~pepeg/mates/tema9.pdf
PAGINA MODIFICADA POR:
Valenzuela Arce Fernando de Montserrat
Olivas Ramirez Jesús Alberto
Guirado Flores Jesús G.
“Solis Covarrubias Alejandro.”(AQUI ESTAN UNAS IMAGENES PARA QUE SE DEN COLOR DEL TEMA)
http://soliscovarrbiasalejandro.blogspot.com/
Cesar Lopez Gonzalez!!!
| ⇐ | Tema Anterior: 3.7.3 Arboles Generadores Minimales |
| ⇒ | Siguiente Tema: 3.7.5 Ordenamientos Arboles |
| Regresar al TEMARIO: Matematicas Computacion |