Recirrido de arbol prefija

RECORRIDO DE ARBOLPREFIJA

En el orden preorden se recorre de la siguiente manera: raíz, subárbol izquierdo, subárbol derecho. En el orden inorden se recorre de la siguiente manera: subárbol izquierdo, raíz, subárbol derecho. En el orden postorden se recorre de la siguiente manera: subárbol izquierdo, subárbol derecho, raíz.

En ciencias de la computación, el recorrido de árboles se refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un árbol binario, pero también pueden ser generalizados a otros árboles.

Recorrido en profundidad-primero

Artículo principal: Búsqueda en profundidad

Árbol binario

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

1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho

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

1. Atraviese el sub-árbol izquierdo
2. Visite la raíz
3. Atraviese el sub-árbol derecho

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

1. Atraviese el sub-árbol izquierdo
2. Atraviese el sub-árbol derecho
3. Visite la raíz

En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.

• En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho
• En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y
• En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho

Preorden (antes), inorden (en medio), postorden (después).

Árbol genérico

Para recorrer un árbol no vacío en orden de profundidad-primero, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Realice la operación pre-orden
2. Para i=1 a n-1 haga
   1. Visite al hijo[i], si existe
   2. Realice la operación in-orden
3. Visite al hijo[n], si existe
4. Realice la operación post-orden

donde n es el número de nodos hijos. Dependiendo del problema actual, las operaciones de pre-orden, in-orden o post-orden pueden ser vacías (void), o usted puede querer visitar solamente un nodo de hijo específico, así que estas operaciones pueden ser consideradas opcionales. También, en la práctica, más de una de las operaciones de pre-orden, in-orden y post-orden pueden ser requeridas. Por ejemplo, al insertar en un árbol ternario, una operación de pre-orden es realizada comparando elementos. Una operación de post-orden puede luego ser necesitada para rebalancear el árbol.

Recorrido en anchura-primero

Artículo principal: Búsqueda en anchura

Los árboles también pueden ser recorridos en orden por nivel (de nivel en nivel), donde visitamos cada nodo en un nivel antes de ir a un nivel inferior. Esto también es llamado recorrido en anchura-primero o recorrido en anchura.