Métodos de Recorrido

• Recorrido Preorden: El nodo raíz está al principio, es decir, raíz-izquierda-derecha. El resultado del ejemplo anterior es ABC.
• Recorrido Inorden: El nodo raíz está en el medio, es decir, izqiuerda-raíz-derecha. El resultado del ejemplo anterior es BAC.
• Recorrido Postorden: El nodo raíz está al final, es decir, izquierda-derecha-raíz. El resultado del ejemplo anterior es BCA.
• Recorrido por Niveles: Recorrido nivel por nivel. El resultado del ejemplo anterior es ABC.

Recorridos Preorden, Inorden y Postorden

Este tipo de problemas proporciona el recorrido inorden junto con uno de los recorridos preorden o postorden para obtener el otro.

Por ejemplo, si se proporcionan los recorridos preorden e inorden, se utiliza recursivamente para encontrar la raíz actual y generar el resultado.

void explorarArbol(string preorden, string inorden) {
    if(preorden.empty()) return;
    char nodoActual = preorden[0];
    int posicion = inorden.find(nodoActual);
    
    explorarArbol(preorden.substr(1, posicion), inorden.substr(0, posicion));
    explorarArbol(preorden.substr(posicion + 1), inorden.substr(posicion + 1));
    
    cout << nodoActual;
}

Es importante tener en cuenta la posición de salida, ya que es diferente para los recorridos preorden y postorden.

Recorrido por Niveles

Proporcionando el resultado del recorrido por niveles, se debe imprimir el contenido del nivel k.

long long i, n, nivel, limiteInferior, limiteSuperior;
    cin >> n;
    
    // Almacenar los nodos
    vector<long long=""> nodos(n + 1);
    for(i = 1; i <= n; i++) {
        cin >> nodos[i];
    }
    
    cin >> nivel;
    
    // Calcular los límites del nivel solicitado
    limiteInferior = pow(2, nivel - 1);
    limiteSuperior = pow(2, nivel) - 1;
    
    // Imprimir los nodos del nivel solicitado
    bool hayNodos = false;
    for(i = limiteInferior; i <= min(n, limiteSuperior); i++) {
        cout << nodos[i] << " ";
        hayNodos = true;
    }
    
    if(!hayNodos) {
        cout << "VACIO" << endl;
    }
    
    return 0;
</long>

La función de potencia puede optimizarse con exponentiación rápida.

Tipos Especiales de Árboles Binarios

Árbol Binario Completo

Un árbol de k niveles tiene \(2^{k-1}\) nodos.

Árbol Binario Lleno

Los nodos del 1 al n son los primeros n nodos de un árbol binario completo.

Árbol de Búsqueda Binaria

El nodo raíz siempre es mayor que los valores del subárbol izquierdo y menor que los valores del subárbol derecho.

Recorrido de Árboles

Primero, se almacenan todas las aristas del árbol en un vector (almacenando cada arista una sola vez).

int n;
vector<int> adyacencia[MAX_NODOS];
bool visitado[MAX_NODOS];
int profundidad[MAX_NODOS];

void almacenarAristas() {
    for(int i = 1; i <= n - 1; i++) {
        int nodo1, nodo2;
        cin >> nodo1 >> nodo2;
        adyacencia[nodo1].push_back(nodo2);
        adyacencia[nodo2].push_back(nodo1);
    }
}
</int>

Luego, se utiliza DFS para explorar cada arista.

void dfs(int nodoActual) {
    visitado[nodoActual] = true;
    
    for(int vecino : adyacencia[nodoActual]) {
        if(!visitado[vecino]) {
            profundidad[vecino] = profundidad[nodoActual] + 1;
            dfs(vecino);
        }
    }
}

Árboles y Grafos Bipartitos

Todos los árboles pueden transformarse en grafos bipartitos.

Concepto de Grafo Bipartito

El conjunto de vértices V puede dividirce en dos subconjuntos disjuntos, y cada arista del grafo conecta vértices de diferentes subconjuntos. Los vértices dentro del mismo subconjunto no están conectados.

Transformación de Árboles a Grafos Bipartitos

Como se muestra en la imagen, transformar un árbol en un grafo bipartito implica separar los niveles impares y pares del árbol. Por lo tanto, es necesario almacenar la profundidad de cada nodo (mediante el recorrido del árbol).