Recorrido de árboles

A diferencia de las listas enlazadas, las matrices unidimensionales y otras estructuras de datos lineales, que se recorren canónicamente en orden lineal, los árboles pueden recorrerse de múltiples maneras. Pueden ser recorridos en orden de profundidad o de amplitud. Hay tres formas habituales de recorrerlos en orden de profundidad: dentro del orden, antes del orden y después del orden. Más allá de estos recorridos básicos, son posibles varios esquemas más complejos o híbridos, como las búsquedas limitadas en profundidad, como la búsqueda iterativa en profundidad. Este último, así como la búsqueda de amplitud primero, también se puede utilizar para atravesar árboles infinitos, ver más abajo.

Estructuras de datos para atravesar árbolesEditar

Atravesar un árbol implica iterar sobre todos los nodos de alguna manera. Debido a que desde un nodo dado hay más de un posible nodo siguiente (no es una estructura de datos lineal), entonces, asumiendo un cálculo secuencial (no paralelo), algunos nodos deben ser diferidos-almacenados de alguna manera para ser visitados posteriormente. Esto suele hacerse mediante una pila (LIFO) o una cola (FIFO). Como un árbol es una estructura de datos autorreferencial (definida recursivamente), el recorrido puede definirse por recursión o, más sutilmente, por corecursión, de una manera muy natural y clara; en estos casos los nodos diferidos se almacenan implícitamente en la pila de llamadas.

La búsqueda de profundidad primero se implementa fácilmente a través de una pila, incluso recursivamente (a través de la pila de llamadas), mientras que la búsqueda de amplitud primero se implementa fácilmente a través de una cola, incluso corecursivamente.:45-61

Búsqueda en profundidad de árbol binarioEditar

Recorrido en profundidad (camino punteado) de un árbol binario:

• Preorden (acceso al nodo en posición roja ●):

  F, B, A, D, C, E, G, I, H;

• In-order (acceso a nodo en posición verde ●):

  A, B, C, D, E, F, G, H, I;

• Post-order (acceso a nodo en posición azul ●):

  A, C, E, D, B, H, I, G, F.

Estas búsquedas se denominan búsqueda en profundidad (DFS), ya que el árbol de búsqueda se profundiza al máximo en cada hijo antes de pasar al siguiente hermano. Para un árbol binario, se definen como operaciones de acceso en cada nodo, empezando por el nodo actual, cuyo algoritmo es el siguiente:

El patrón recursivo general para recorrer un árbol binario es el siguiente:

1. Desciende un nivel hasta el argumento recursivo N. Si N existe (no está vacío) ejecuta las tres operaciones siguientes en un orden determinado: L: Recorrer recursivamente el subárbol izquierdo de N. R: Recorrer recursivamente el subárbol derecho de N. N: Acceder (visitar) el propio nodo actual N.
2. Regresa subiendo un nivel y llegando al nodo padre de N.

Hay tres métodos (patrones) en qué posición del parcours (travesía) relativa al nodo (en la figura: rojo, verde o azul) se realizará la visita (acceso) del nodo. La elección de exactamente un color determina exactamente una visita a un nodo, como se describe a continuación. El acceso en los tres colores da lugar a una triple visita del mismo nodo produciendo la secuencialización «todo orden»:

F-B-A-A-B-D-C-C-D-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F

Pre-orden, NLREdit

1. Accede a la parte de datos del nodo actual (en la figura: posición roja).
2. Recorrer el subárbol izquierdo llamando recursivamente a la función de preorden.
3. Recorrer el subárbol derecho llamando recursivamente a la función de preorden.

El recorrido de preorden es un recorrido topológicamente ordenado, porque un nodo padre se procesa antes que cualquiera de sus nodos hijos.

In-order, LNREdit

1. Recorre el subárbol izquierdo llamando recursivamente a la función in-order.
2. Accede a la parte de datos del nodo actual (en la figura: posición verde).
3. Recorre el subárbol derecho llamando recursivamente a la función in-order.

En un árbol de búsqueda binario ordenado de tal manera que en cada nodo la clave es mayor que todas las claves de su subárbol izquierdo y menor que todas las claves de su subárbol derecho, el recorrido en orden recupera las claves en orden ascendente.

Invertir el orden, RNLEdit

1. Recorrer el subárbol derecho llamando recursivamente a la función de inversión del orden.
2. Acceder a la parte de datos del nodo actual.
3. Recorrer el subárbol izquierdo llamando recursivamente a la función de inversión del orden.

En un árbol de búsqueda binario, el recorrido de orden inverso recupera las claves en orden descendente.

Post-orden, LRNEdit

1. Recorre el subárbol izquierdo llamando recursivamente a la función de post-orden.
2. Recorrer el subárbol derecho llamando recursivamente a la función de post-orden.
3. Acceder a la parte de datos del nodo actual (en la figura: posición azul).

La traza de un recorrido se llama secuencialización del árbol. La traza de la travesía es una lista de cada nodo visitado. Ninguna secuenciación según el orden previo, previo o posterior describe el árbol subyacente de forma única. Dado un árbol con elementos distintos, el pre-orden o el post-orden emparejados con el in-orden son suficientes para describir el árbol de forma única. Sin embargo, el pre-orden con post-orden deja cierta ambigüedad en la estructura del árbol.

Generic treeEdit

Para recorrer cualquier árbol con búsqueda en profundidad, realizar las siguientes operaciones en cada nodo:

1. Si el nodo no está presente volver.
2. Acceder (= visitar) el nodo (posición de preorden).
3. Por cada i de 1 a número_de_hijos – 1 hacer:
   1. Recorrer recursivamente el i-ésimo hijo.
   2. Accede al nodo (posición en el orden).
4. Recursivamente recorre el último hijo.
5. Accede al nodo (posición posterior al orden).

Dependiendo del problema en cuestión, las operaciones de pre-orden, post-orden, y especialmente una de las operaciones de (número_de_hijos – 1) dentro del orden pueden ser nulas, o se quiere acceder sólo a un hijo específico, por lo que estas operaciones son opcionales. Además, en la práctica puede ser necesaria más de una de las operaciones de preorden, inorden y posorden. Por ejemplo, al insertar en un árbol ternario, se realiza una operación de preorden al comparar elementos. Después puede ser necesaria una operación de post-orden para reequilibrar el árbol.

Búsqueda en primer lugar, u orden de nivelEditar

Orden de nivel: F, B, G, A, D, I, C, E, H.

Los árboles también se pueden recorrer en orden de niveles, donde visitamos cada nodo de un nivel antes de ir a un nivel inferior. Esta búsqueda se denomina búsqueda por amplitud (BFS), ya que el árbol de búsqueda se amplía tanto como sea posible en cada profundidad antes de pasar a la siguiente.

Otros tiposEditar

También hay algoritmos de recorrido de árboles que no se clasifican como búsqueda por profundidad ni por amplitud. Uno de estos algoritmos es la búsqueda en árbol de Monte Carlo, que se concentra en el análisis de los movimientos más prometedores, basando la expansión del árbol de búsqueda en un muestreo aleatorio del espacio de búsqueda.