TAD Árbol: Recorridos y Árbol Binario de Búsqueda

Todo lo que viste hasta acá era lineal: cada elemento tiene un anterior y un siguiente, y buscar algo implica, en el peor caso, recorrer todo.

Un árbol rompe esa linealidad. Cada nodo puede tener varios hijos, y eso habilita algo muy poderoso: descartar la mitad de los datos en cada paso. Buscar entre un millón de elementos deja de costar un millón de comparaciones y pasa a costar veinte.

Y además, muchísimas cosas del mundo real son árboles: el sistema de archivos, el DOM de una página, el organigrama de una empresa, la jerarquía de clases de Java, las decisiones de un juego.

1. Vocabulario

La clase que lo modela es la hermana de la Nodo de la lección TAD Lista: Estáticas, Dinámicas y Enlazadas, con una referencia más:

public class NodoArbol {
    int valor;
    NodoArbol izquierdo;
    NodoArbol derecho;

    public NodoArbol(int valor) {
        this.valor = valor;
    }
}

public class ArbolBinario {
    private NodoArbol raiz;   // igual que 'cabeza', pero acá se llama raíz
}

Y como cada nodo tiene dos hijos que a su vez son árboles completos, todo en los árboles se resuelve con recursión. Es la estructura de datos donde la recursión deja de ser un ejercicio académico y se vuelve la herramienta natural.

2. Los tres recorridos en profundidad

Recorrer una lista tiene un solo orden posible. Un árbol tiene varios, y cada uno sirve para algo distinto.

Los tres se diferencian únicamente en dónde se procesa la raíz respecto de sus subárboles:

El código es casi idéntico en los tres casos. Lo único que se mueve es una línea:

public void preOrden(NodoArbol nodo) {
    if (nodo == null) return;               // caso base: siempre primero
    System.out.print(nodo.valor + " ");     // ← la raíz, ANTES
    preOrden(nodo.izquierdo);
    preOrden(nodo.derecho);
}

public void inOrden(NodoArbol nodo) {
    if (nodo == null) return;
    inOrden(nodo.izquierdo);
    System.out.print(nodo.valor + " ");     // ← la raíz, EN EL MEDIO
    inOrden(nodo.derecho);
}

public void postOrden(NodoArbol nodo) {
    if (nodo == null) return;
    postOrden(nodo.izquierdo);
    postOrden(nodo.derecho);
    System.out.print(nodo.valor + " ");     // ← la raíz, DESPUÉS
}

El if (nodo == null) return; es el caso base, y no es un detalle: sin él la recursión no termina nunca y obtenés un StackOverflowError. Que, como viste en la lección TAD Pila y TAD Cola: Estructuras Lineales, es literalmente la pila de llamadas de la JVM desbordándose.

In-orden sobre un ABB devuelve los datos ordenados. Esa propiedad, que parece un truco de magia, es la razón por la que un TreeMap puede recorrerse en orden de clave sin ordenar nada: el orden ya está en la forma del árbol.

3. Recorrido por niveles (BFS), con una cola

Los tres recorridos anteriores bajan hasta el fondo antes de moverse al lado. A veces querés lo contrario: visitar el árbol nivel por nivel.

La recursión no sirve acá. Lo que sirve es una cola, exactamente la de la lección TAD Pila y TAD Cola: Estructuras Lineales:

public void porNiveles() {
    if (raiz == null) return;

    Queue<NodoArbol> cola = new ArrayDeque<>();
    cola.offer(raiz);

    while (!cola.isEmpty()) {
        NodoArbol actual = cola.poll();
        System.out.print(actual.valor + " ");

        if (actual.izquierdo != null) cola.offer(actual.izquierdo);
        if (actual.derecho  != null) cola.offer(actual.derecho);
    }
}
// Salida: 50 30 70 20 40 60 80

Fijate el mecanismo: encolo los hijos y los proceso recién cuando terminé con todos los del nivel actual. Ese “primero en entrar, primero en salir” de la cola es exactamente lo que produce el orden por niveles.

Si cambiás la cola por una pila, obtenés un recorrido en profundidad sin recursión. Cambiar la estructura cambia el algoritmo, sin tocar el resto del código. Es la misma idea que vas a usar en grafos, en la lección siguiente.

4. El Árbol Binario de Búsqueda

Hasta acá los árboles solo guardaban datos. Un ABB agrega una regla que lo cambia todo:

Para todo nodo: cada valor del subárbol izquierdo es menor, y cada valor del subárbol derecho es mayor.

Con esa regla, buscar deja de recorrer y pasa a decidir:

public boolean buscar(int valor) {
    return buscar(raiz, valor);
}

private boolean buscar(NodoArbol nodo, int valor) {
    if (nodo == null) return false;               // llegué al vacío: no está
    if (valor == nodo.valor) return true;         // lo encontré
    return valor < nodo.valor
        ? buscar(nodo.izquierdo, valor)           // más chico: a la izquierda
        : buscar(nodo.derecho, valor);            // más grande: a la derecha
}

La inserción usa exactamente la misma lógica: baja hasta encontrar un lugar vacío y ahí cuelga el nodo nuevo.

public void insertar(int valor) {
    raiz = insertar(raiz, valor);
}

private NodoArbol insertar(NodoArbol nodo, int valor) {
    if (nodo == null) return new NodoArbol(valor);   // acá va

    if (valor < nodo.valor) {
        nodo.izquierdo = insertar(nodo.izquierdo, valor);
    } else if (valor > nodo.valor) {
        nodo.derecho = insertar(nodo.derecho, valor);
    }
    // si es igual, no hacemos nada: un ABB no admite duplicados
    return nodo;
}

El patrón nodo.izquierdo = insertar(nodo.izquierdo, valor) —reasignar el resultado de la recursión— es la forma idiomática de modificar árboles en Java. Evita tener que llevar una referencia al padre.

5. El talón de Aquiles: el desbalanceo

Todo lo anterior asume que el árbol tiene forma de árbol. Pero eso no está garantizado:

Este es el motivo por el que no vas a implementar un ABB en producción. TreeMap y TreeSet son árboles rojo-negro: se reacomodan solos con rotaciones en cada inserción y garantizan O(log n) sin importar en qué orden llegan los datos.

Lo que sí te llevás es entender por qué son O(log n) y qué pasaría si no se balancearan.

6. Errores frecuentes

7. Ejercicio práctico guiado

Desafío: completar el ABB

Implementá sobre ArbolBinarioBusqueda:

1. insertar(int valor), sin duplicados.
2. buscar(int valor) que devuelva boolean.
3. altura() del árbol.
4. contarNodos() y contarHojas().
5. esABBValido() que verifique que la propiedad se cumple en todo el árbol.
6. Los tres recorridos en profundidad y el recorrido por niveles.

El punto 5 es más difícil de lo que parece. Pensalo antes de mirar la solución.

import java.util.ArrayDeque;
import java.util.Queue;

public class ArbolBinarioBusqueda {

    private static class NodoArbol {
        int valor;
        NodoArbol izquierdo, derecho;
        NodoArbol(int valor) { this.valor = valor; }
    }

    private NodoArbol raiz;

    // ── 1. Inserción ────────────────────────────────────────────
    public void insertar(int valor) {
        raiz = insertar(raiz, valor);
    }

    private NodoArbol insertar(NodoArbol nodo, int valor) {
        if (nodo == null) return new NodoArbol(valor);
        if (valor < nodo.valor)      nodo.izquierdo = insertar(nodo.izquierdo, valor);
        else if (valor > nodo.valor) nodo.derecho   = insertar(nodo.derecho, valor);
        // igual → se ignora, no admitimos duplicados
        return nodo;   // devolver el nodo es lo que hace funcionar la reasignación
    }

    // ── 2. Búsqueda ─────────────────────────────────────────────
    public boolean buscar(int valor) {
        return buscar(raiz, valor);
    }

    private boolean buscar(NodoArbol nodo, int valor) {
        if (nodo == null) return false;
        if (valor == nodo.valor) return true;
        return valor < nodo.valor ? buscar(nodo.izquierdo, valor)
                                  : buscar(nodo.derecho, valor);
    }

    // ── 3. Altura ───────────────────────────────────────────────
    public int altura() {
        return altura(raiz);
    }

    private int altura(NodoArbol nodo) {
        if (nodo == null) return -1;   // -1 para que una hoja dé altura 0
        return 1 + Math.max(altura(nodo.izquierdo), altura(nodo.derecho));
    }

    // ── 4. Conteos ──────────────────────────────────────────────
    public int contarNodos() { return contarNodos(raiz); }

    private int contarNodos(NodoArbol nodo) {
        if (nodo == null) return 0;
        return 1 + contarNodos(nodo.izquierdo) + contarNodos(nodo.derecho);
    }

    public int contarHojas() { return contarHojas(raiz); }

    private int contarHojas(NodoArbol nodo) {
        if (nodo == null) return 0;
        if (nodo.izquierdo == null && nodo.derecho == null) return 1;
        return contarHojas(nodo.izquierdo) + contarHojas(nodo.derecho);
    }

    // ── 5. Validación del ABB ───────────────────────────────────
    public boolean esABBValido() {
        return esValido(raiz, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // La clave: cada nodo hereda un RANGO permitido, no solo la comparación
    // con su padre inmediato. Al bajar a la izquierda, el máximo permitido
    // pasa a ser el valor del padre; al bajar a la derecha, el mínimo.
    private boolean esValido(NodoArbol nodo, long min, long max) {
        if (nodo == null) return true;
        if (nodo.valor <= min || nodo.valor >= max) return false;
        return esValido(nodo.izquierdo, min, nodo.valor)
            && esValido(nodo.derecho,   nodo.valor, max);
    }

    // ── 6. Recorridos ───────────────────────────────────────────
    public void preOrden()  { preOrden(raiz);  System.out.println(); }
    public void inOrden()   { inOrden(raiz);   System.out.println(); }
    public void postOrden() { postOrden(raiz); System.out.println(); }

    private void preOrden(NodoArbol n) {
        if (n == null) return;
        System.out.print(n.valor + " ");
        preOrden(n.izquierdo);
        preOrden(n.derecho);
    }

    private void inOrden(NodoArbol n) {
        if (n == null) return;
        inOrden(n.izquierdo);
        System.out.print(n.valor + " ");
        inOrden(n.derecho);
    }

    private void postOrden(NodoArbol n) {
        if (n == null) return;
        postOrden(n.izquierdo);
        postOrden(n.derecho);
        System.out.print(n.valor + " ");
    }

    public void porNiveles() {
        if (raiz == null) { System.out.println("(vacío)"); return; }
        Queue<NodoArbol> cola = new ArrayDeque<>();
        cola.offer(raiz);
        while (!cola.isEmpty()) {
            NodoArbol actual = cola.poll();
            System.out.print(actual.valor + " ");
            if (actual.izquierdo != null) cola.offer(actual.izquierdo);
            if (actual.derecho  != null) cola.offer(actual.derecho);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ArbolBinarioBusqueda arbol = new ArbolBinarioBusqueda();
        for (int v : new int[]{50, 30, 70, 20, 40, 60, 80}) {
            arbol.insertar(v);
        }

        System.out.print("Pre-orden : "); arbol.preOrden();    // 50 30 20 40 70 60 80
        System.out.print("In-orden  : "); arbol.inOrden();     // 20 30 40 50 60 70 80
        System.out.print("Post-orden: "); arbol.postOrden();   // 20 40 30 60 80 70 50
        System.out.print("Niveles   : "); arbol.porNiveles();  // 50 30 70 20 40 60 80

        System.out.println("\nAltura        : " + arbol.altura());        // 2
        System.out.println("Nodos         : " + arbol.contarNodos());     // 7
        System.out.println("Hojas         : " + arbol.contarHojas());     // 4
        System.out.println("buscar(40)    : " + arbol.buscar(40));        // true
        System.out.println("buscar(45)    : " + arbol.buscar(45));        // false
        System.out.println("esABBValido() : " + arbol.esABBValido());     // true

        // Demostración del desbalanceo
        ArbolBinarioBusqueda degenerado = new ArbolBinarioBusqueda();
        for (int v : new int[]{10, 20, 30, 40, 50, 60, 70}) {
            degenerado.insertar(v);
        }
        System.out.println("\nMismos 7 valores, insertados ordenados:");
        System.out.println("Altura: " + degenerado.altura() + "  ← era 2, ahora es 6");
    }
}

// MAL: solo mira al padre inmediato
if (nodo.izquierdo != null && nodo.izquierdo.valor >= nodo.valor) return false;

      50
     /  \
   30    70
  /  \
20    60      ← el 60 es mayor que 50 y está en el subárbol IZQUIERDO de 50

Para llevarte

• Un árbol rompe la linealidad y permite descartar la mitad de los datos en cada paso.
• Todo en árboles se resuelve con recursión, y todo método recursivo arranca con su caso base.
• Los tres recorridos DFS se diferencian en una sola línea: dónde se procesa la raíz.
• In-orden sobre un ABB devuelve los datos ordenados. Por eso TreeMap se recorre en orden sin ordenar nada.
• El recorrido por niveles (BFS) necesita una cola, no recursión.
• La propiedad del ABB —izquierda menor, derecha mayor, en todo el árbol— es lo que convierte una búsqueda en una decisión.
• Insertar datos ya ordenados degenera el ABB en una lista y lo lleva de O(log n) a O(n).
• En producción usá TreeMap/TreeSet: son árboles rojo-negro que se reequilibran solos.