El manejo de estructursa de datos jerárquicas es una habilidad fundamental en la ingeniería de software. A continuación, se presanta una guía técnica detallada sobre la resolución de problemas comunes relacionados con árboles binarios, utilizando C++ como lenguaje de implementación.

1. Recorrido por Niveles (Breadth-First Search)

El recorrido por niveles organiza los nodos de un árbol procesándolos horizontalmente, de arriba hacia abajo. Una implementación eficiente utiliza una cola para gestionar la visita de los nodos.

#include <vector>
#include <queue>

struct NodoArbol {
    int valor;
    NodoArbol *izq, *der;
    NodoArbol(int x) : valor(x), izq(nullptr), der(nullptr) {}
};

class ProcesadorArbol {
public:
    std::vector<std::vector<int>> obtenerNiveles(NodoArbol* raiz) {
        if (!raiz) return {};
        std::vector<std::vector<int>> resultado;
        std::queue<NodoArbol*> cola;
        cola.push(raiz);

        while (!cola.empty()) {
            int nodosEnNivel = cola.size();
            std::vector<int> nivelActual;
            
            for (int i = 0; i < nodosEnNivel; ++i) {
                NodoArbol* actual = cola.front();
                cola.pop();
                nivelActual.push_back(actual->valor);
                
                if (actual->izq) cola.push(actual->izq);
                if (actual->der) cola.push(actual->der);
            }
            resultado.push_back(nivelActual);
        }
        return resultado;
    }
};

2. Recorrido en Zigzag

Esta variante del recorrido por niveles alterna la dirección de procesamiento (izquierda a derecha y viceversa) en cada nivel sucesivo.

#include <algorithm>

std::vector<std::vector<int>> recorridoZigZag(NodoArbol* raiz) {
    if (!raiz) return {};
    std::vector<std::vector<int>> final;
    std::queue<NodoArbol*> q;
    q.push(raiz);
    bool invertir = false;

    while (!q.empty()) {
        int tam = q.size();
        std::vector<int> fila(tam);
        for (int i = 0; i < tam; ++i) {
            NodoArbol* n = q.front();
            q.pop();
            
            int pos = invertir ? (tam - 1 - i) : i;
            fila[pos] = n->valor;
            
            if (n->izq) q.push(n->izq);
            if (n->der) q.push(n->der);
        }
        final.push_back(fila);
        invertir = !invertir;
    }
    return final;
}

3. Ancho Máximo del Árbol Binario

El ancho máximo se define como la mayor distancia entre el nodo más a la izquierda y el más a la derecha en cualquier nivel, considerando nodos nulos intermedios. Se utiliza indexación de tipo 2*i y 2*i + 1.

#include <utility>

typedef unsigned long long ull;

int calcularAnchoMaximo(NodoArbol* raiz) {
    if (!raiz) return 0;
    ull maxAncho = 0;
    std::queue<std::pair<NodoArbol*, ull>> q;
    q.push({raiz, 1});

    while (!q.empty()) {
        int cuenta = q.size();
        ull inicio = q.front().second;
        ull fin = inicio;
        
        for (int i = 0; i < cuenta; ++i) {
            auto [nodo, id] = q.front();
            q.pop();
            fin = id;
            if (nodo->izq) q.push({nodo->izq, id * 2});
            if (nodo->der) q.push({nodo->der, id * 2 + 1});
        }
        maxAncho = std::max(maxAncho, fin - inicio + 1);
    }
    return (int)maxAncho;
}

4. Profundidad del Árbol

La profundidad máxima es la dsitancia a la hoja más lejana, mientras que la mínima es la distancia a la hoja más cercana.

int profundidadMaxima(NodoArbol* n) {
    if (!n) return 0;
    return 1 + std::max(profundidadMaxima(n->izq), profundidadMaxima(n->der));
}

int profundidadMinima(NodoArbol* n) {
    if (!n) return 0;
    if (!n->izq) return 1 + profundidadMinima(n->der);
    if (!n->der) return 1 + profundidadMinima(n->izq);
    return 1 + std::min(profundidadMinima(n->izq), profundidadMinima(n->der));
}

5. Reconstrucción desde Preorden e Inorden

Utilizando las propiedades de los recorridos, podemos reconstruir la estructura original del árbol de forma recursiva.

#include <unordered_map>

class ConstructorArbol {
    std::unordered_map<int, int> mapaInorden;
    
    NodoArbol* helper(std::vector<int>& pre, int p_ini, int p_fin, int i_ini, int i_fin) {
        if (p_ini > p_fin) return nullptr;
        
        NodoArbol* raiz = new NodoArbol(pre[p_ini]);
        int idxRaiz = mapaInorden[pre[p_ini]];
        int numIzquierda = idxRaiz - i_ini;
        
        raiz->izq = helper(pre, p_ini + 1, p_ini + numIzquierda, i_ini, idxRaiz - 1);
        raiz->der = helper(pre, p_ini + numIzquierda + 1, p_fin, idxRaiz + 1, i_fin);
        return raiz;
    }

public:
    NodoArbol* construir(std::vector<int>& preorden, std::vector<int>& inorden) {
        for (int i = 0; i < inorden.size(); ++i) mapaInorden[inorden[i]] = i;
        return helper(preorden, 0, preorden.size() - 1, 0, inorden.size() - 1);
    }
};

6. Validación de Árbol Binario Completo

Un árbol es completo si todos sus niveles están llenos, excepto posiblemente el último, que debe estar lleno de izquierda a derecha.

bool esCompleto(NodoArbol* raiz) {
    if (!raiz) return true;
    std::queue<NodoArbol*> q;
    q.push(raiz);
    bool encontroIncompleto = false;

    while (!q.empty()) {
        NodoArbol* actual = q.front();
        q.pop();

        if (actual) {
            if (encontroIncompleto) return false;
            q.push(actual->izq);
            q.push(actual->der);
        } else {
            encontroIncompleto = true;
        }
    }
    return true;
}

7. Ancestro Común más Cercano (LCA)

El LCA de dos nodos p y q es el nodo más profundo que tiene a ambos como descendientes.

En Árbol Binario General:

NodoArbol* buscarLCA(NodoArbol* raiz, NodoArbol* p, NodoArbol* q) {
    if (!raiz || raiz == p || raiz == q) return raiz;
    
    NodoArbol* izq = buscarLCA(raiz->izq, p, q);
    NodoArbol* der = buscarLCA(raiz->der, p, q);
    
    if (izq && der) return raiz;
    return izq ? izq : der;
}

En Árbol Binario de Búsqueda (BST):

NodoArbol* lcaBST(NodoArbol* raiz, NodoArbol* p, NodoArbol* q) {
    while (raiz) {
        if (p->valor < raiz->valor && q->valor < raiz->valor)
            raiz = raiz->izq;
        else if (p->valor > raiz->valor && q->valor > raiz->valor)
            raiz = raiz->der;
        else
            return raiz;
    }
    return nullptr;
}