Árbol desde preorden e inorden

Reconstruir un árbol binario a partir de sus recorridos en preorden e inorden es una técnica fundamental que nos permite entender la estructura completa del árbol a partir de dos representaciones lineales. Para ello, necesitamos comprender cómo identificar la raíz y cómo separar los subárboles izquierdo y derecho usando ambas representaciones.

Primero, partimos de la observación clave de que en el recorrido en preorden el primer elemento siempre es la raíz del árbol. Por ejemplo, si tenemos un preorden como 5, 3, 1, 7, 6, 9, el número 5 será la raíz. Esto nos da un punto de partida para reconstruir el árbol.

A continuación, buscamos esta raíz en la representación en inorden. En el inorden, la raíz aparece en medio, con todos los elementos a su izquierda formando el subárbol izquierdo y todos los elementos a su derecha formando el subárbol derecho. Por ejemplo, si el inorden es 1, 3, 5, 6, 7, 9, el 5 divide la lista en 1, 3 a la izquierda y 6, 7, 9 a la derecha. Esto nos indica que los nodos 1 y 3 pertenecen al subárbol izquierdo, mientras que 6, 7 y 9 pertenecen al subárbol derecho.

El siguiente paso es identificar en el preorden cuáles nodos corresponden a cada subárbol. Sabemos cuántos nodos hay en el subárbol izquierdo porque los contamos en el inorden (en este caso, dos nodos: 1 y 3). Entonces, en el preorden, después de la raíz, tomamos ese mismo número de nodos para el subárbol izquierdo. En nuestro ejemplo, después del 5 en preorden, los dos siguientes nodos 3 y 1 forman el subárbol izquierdo, y el resto 7, 6, 9 el subárbol derecho.

Con esta división clara, aplicamos el mismo proceso de forma recursiva para cada subárbol. Para el subárbol izquierdo con preorden 3, 1 e inorden 1, 3, tomamos el primer elemento del preorden, 3, como raíz. En el inorden, 3 está en medio, con 1 a la izquierda y nada a la derecha, lo que indica que 1 es el hijo izquierdo de 3 y que 3 no tiene hijo derecho. Repetimos la recursión para el nodo 1, que al no tener elementos a su izquierda ni a su derecha en inorden, es una hoja.

Para el subárbol derecho con preorden 7, 6, 9 e inorden 6, 7, 9, la raíz es 7. En el inorden, 6 está a la izquierda y 9 a la derecha de 7, por lo que 6 es el hijo izquierdo y 9 el hijo derecho. Como ambos son nodos individuales sin más descendientes, terminamos la recursión.

Este método nos permite reconstruir el árbol completo, asegurándonos de que si volvemos a obtener sus recorridos en preorden e inorden, coincidirán con las representaciones iniciales. La clave está en usar el preorden para identificar la raíz y el inorden para dividir los subárboles, y luego aplicar esta lógica recursivamente hasta procesar todos los nodos.

Para ilustrar este proceso, el código en Java que implementa esta reconstrucción podría ser algo así:

class Nodo {
    int valor;
    Nodo izquierdo, derecho;

    Nodo(int valor) {
        this.valor = valor;
    }
}

public class ReconstruirArbol {
    private int indicePreorden = 0;

    public Nodo construirArbol(int[] preorden, int[] inorden) {
        return construir(preorden, inorden, 0, inorden.length - 1);
    }

    private Nodo construir(int[] preorden, int[] inorden, int inicio, int fin) {
        if (inicio > fin) {
            return null;
        }

        int raizValor = preorden[indicePreorden++];
        Nodo raiz = new Nodo(raizValor);

        int indiceInorden = buscarIndice(inorden, inicio, fin, raizValor);

        raiz.izquierdo = construir(preorden, inorden, inicio, indiceInorden - 1);
        raiz.derecho = construir(preorden, inorden, indiceInorden + 1, fin);

        return raiz;
    }

    private int buscarIndice(int[] arr, int inicio, int fin, int valor) {
        for (int i = inicio; i <= fin; i++) {
            if (arr[i] == valor) {
                return i;
            }
        }
        return -1; // No debería ocurrir si los datos son correctos
    }
}

Este código refleja el proceso explicado: tomamos la raíz del preorden, buscamos su posición en el inorden para dividir los subárboles, y aplicamos la función recursivamente para construir los hijos izquierdo y derecho.

Así, con esta técnica podemos reconstruir cualquier árbol binario siempre que tengamos sus recorridos en preorden e inorden, lo que resulta muy útil para ejercicios, exámenes o para entender mejor la estructura interna de los árboles.