6.3 Algoritmos de recorrido y búsqueda

6.3 Algoritmos de recorrido y búsqueda

Existen algunas maneras útiles en las cuales se pueden ordenar sistemáticamente los nodos de un árbol. Los más importantes son: preorden, post-orden y en-orden.

Estos tienen tres tipos de actividades comunes:

Visitar el nodo raíz

Recorrer el subárbol izquierdo

Recorrer el subárbol derecho

Estas tres actividades llevadas a cabo en distinto orden, crean los distintos recorridos del árbol.

Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

Visite la raíz

Atraviese el sub-árbol izquierdo

Atraviese el sub-árbol derecho

Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

Atraviese el sub-árbol izquierdo

Visite la raíz

Atraviese el sub-árbol derecho

Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

Atraviese el sub-árbol izquierdo

Atraviese el sub-árbol derecho

Visite la raíz

Se llama recorrido de un árbol al proceso que permite accede una vez a cada uno de los elementos de un árbol para examinar el conjunto completo. Primero se ven los algoritmo 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.

Los ordenamientos más importantes son llamados: prefijo, sufijo y posfijo.

Los algoritmos de recorrido de un árbol presentan tres tipos 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