Recorridos de Árboles

Los tres recorridos fundamentales

En un árbol binario, cada nodo tiene a lo más dos hijos: izquierdo y derecho. Hay tres formas clásicas de visitarlos:

        1
       / \
      2   3
     / \   \
    4   5   6

Truco para recordar: El nombre indica cuándo visitas la raíz: pre (antes), in (en medio), post (después).

Implementación

Estructura del árbol binario

struct Nodo {
    int valor;
    int izq, der;  // -1 si no tiene hijo
};

Nodo arbol[100005];

Preorden (NID)

void preorden(int nodo) {
    if (nodo == -1) return;

    cout << arbol[nodo].valor << " ";  // Nodo
    preorden(arbol[nodo].izq);          // Izquierda
    preorden(arbol[nodo].der);          // Derecha
}

Inorden (IND)

void inorden(int nodo) {
    if (nodo == -1) return;

    inorden(arbol[nodo].izq);           // Izquierda
    cout << arbol[nodo].valor << " ";  // Nodo
    inorden(arbol[nodo].der);           // Derecha
}

Postorden (IDN)

void postorden(int nodo) {
    if (nodo == -1) return;

    postorden(arbol[nodo].izq);         // Izquierda
    postorden(arbol[nodo].der);         // Derecha
    cout << arbol[nodo].valor << " ";  // Nodo
}

Recorrido por niveles (BFS)

Visitar nivel por nivel, de izquierda a derecha:

void porNiveles(int raiz) {
    queue<int> q;
    q.push(raiz);

    while (!q.empty()) {
        int nodo = q.front();
        q.pop();

        cout << arbol[nodo].valor << " ";

        if (arbol[nodo].izq != -1) q.push(arbol[nodo].izq);
        if (arbol[nodo].der != -1) q.push(arbol[nodo].der);
    }
}
// Resultado para el ejemplo: 1 2 3 4 5 6

Recorridos en árboles generales (no binarios)

En competencias, los árboles generalmente no son binarios. Usamos DFS:

vector<int> adj[100005];

// Preorden (euler tour - tiempo de entrada)
int tin[100005], tout[100005], timer = 0;

void dfs(int nodo, int padre) {
    tin[nodo] = timer++;

    // Procesar nodo aquí (preorden)

    for (int hijo : adj[nodo]) {
        if (hijo != padre) {
            dfs(hijo, nodo);
        }
    }

    tout[nodo] = timer++;
    // Procesar nodo aquí (postorden)
}

Euler Tour

Técnica fundamental: asignar a cada nodo un tiempo de entrada y salida. Esto convierte el árbol en un arreglo lineal.

int tin[100005], tout[100005], timer = 0;
int eulerTour[200005];  // El recorrido completo

void euler(int nodo, int padre) {
    tin[nodo] = timer;
    eulerTour[timer++] = nodo;

    for (int hijo : adj[nodo]) {
        if (hijo != padre) {
            euler(hijo, nodo);
        }
    }

    tout[nodo] = timer;
    eulerTour[timer++] = nodo;
}

Propiedad clave: El nodo u es ancestro de v si y solo si tin[u] ≤ tin[v] y tout[u] ≥ tout[v].

Reconstruir árbol a partir de recorridos

Problema clásico: Dados el preorden y el inorden, reconstruir el árbol.

int preorden[] = {1, 2, 4, 5, 3, 6};
int inorden[]  = {4, 2, 5, 1, 3, 6};

int construir(int preL, int preR, int inL, int inR) {
    if (preL > preR) return -1;

    int raiz = preorden[preL];

    // Encontrar la raíz en inorden
    int pos = inL;
    while (inorden[pos] != raiz) pos++;

    int tamIzq = pos - inL;

    arbol[raiz].izq = construir(preL + 1, preL + tamIzq, inL, pos - 1);
    arbol[raiz].der = construir(preL + tamIzq + 1, preR, pos + 1, inR);

    return raiz;
}

Ejercicio de práctica

Dado un árbol binario representado con padre y dirección (I=izquierdo, D=derecho), imprime los recorridos preorden, inorden y postorden.

#include <iostream>
using namespace std;

struct Nodo {
    int izq = -1, der = -1;
};

Nodo arbol[105];

void pre(int n) {
    if (n == -1) return;
    cout << n << " ";
    pre(arbol[n].izq);
    pre(arbol[n].der);
}

void in(int n) {
    if (n == -1) return;
    in(arbol[n].izq);
    cout << n << " ";
    in(arbol[n].der);
}

void post(int n) {
    if (n == -1) return;
    post(arbol[n].izq);
    post(arbol[n].der);
    cout << n << " ";
}

int main() {
    int n;
    cin >> n;

    bool esHijo[105] = {};
    for (int i = 0; i < n - 1; i++) {
        int padre, hijo;
        char dir;
        cin >> padre >> hijo >> dir;
        if (dir == 'I') arbol[padre].izq = hijo;
        else arbol[padre].der = hijo;
        esHijo[hijo] = true;
    }

    // Encontrar la raíz (nodo que no es hijo de nadie)
    int raiz = 1;
    for (int i = 1; i <= n; i++) {
        if (!esHijo[i]) { raiz = i; break; }
    }

    cout << "Preorden: "; pre(raiz); cout << endl;
    cout << "Inorden: "; in(raiz); cout << endl;
    cout << "Postorden: "; post(raiz); cout << endl;

    return 0;
}