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
Vídeo explicativo: https://www.youtube.com/watch?v=AnsWNI2TfuA
No hay comentarios.:
Publicar un comentario