Cruce de árboles
En informática , el recorrido de árbol (también conocido como búsqueda de árbol y caminar por el árbol ) es una forma de recorrido de gráfico y se refiere al proceso de visitar (por ejemplo, recuperar, actualizar o eliminar) cada nodo en una estructura de datos de árbol , exactamente una vez. Dichos recorridos se clasifican por el orden en que se visitan los nodos. Los siguientes algoritmos se describen para un árbol binario , pero también pueden generalizarse a otros árboles.
A diferencia de las listas enlazadas , las matrices unidimensionales y otras estructuras de datos lineales , que se atraviesan canónicamente en orden lineal, los árboles se pueden atravesar de varias formas. Se pueden atravesar primero en profundidad o en amplitud . Hay tres formas comunes de atravesarlos en primer orden en profundidad: en orden, preorden y posorden. [1] Más allá de estos recorridos básicos, son posibles varios esquemas más complejos o híbridos, como búsquedas de profundidad limitada como búsqueda iterativa de profundización primero en profundidad . Esta última, así como la búsqueda en amplitud, también se puede utilizar para atravesar árboles infinitos, ver más abajo .
Atravesar un árbol implica iterar sobre todos los nodos de alguna manera. Debido a que de un nodo dado hay más de un posible siguiente nodo (no es una estructura de datos lineal), entonces, asumiendo el cálculo secuencial (no paralelo), algunos nodos deben ser diferidos, almacenados de alguna manera para una visita posterior. Esto se hace a menudo a través de una pila (LIFO) o una cola (FIFO). Como un árbol es una estructura de datos autorreferencial (definida recursivamente), el recorrido se puede definir por recursividad o, más sutilmente, correcursión , de una manera natural y clara; en estos casos, los nodos diferidos se almacenan implícitamente en la pila de llamadas .
La búsqueda en profundidad se implementa fácilmente a través de una pila, incluso de forma recursiva (a través de la pila de llamadas), mientras que la búsqueda en profundidad se implementa fácilmente a través de una cola, incluido el núcleo de forma cursiva. [2] : 45−61
En la búsqueda en profundidad primero (DFS), el árbol de búsqueda se profundiza tanto como sea posible antes de pasar al siguiente hermano.
Para atravesar árboles binarios con búsqueda en profundidad, realice las siguientes operaciones en cada nodo: [3] [4]
- Pedido anticipado (nodo visitado en la posición roja ● ) : F, B, A, D, C, E, G, I, H;
- En orden (nodo visitado en la posición verde ● ) : A, B, C, D, E, F, G, H, I;
- Pedido posterior (nodo visitado en la posición azul ● ) : A, C, E, D, B, H, I, G, F.
