🥇 Árboles en Java: estructura de datos con implementación

Los árboles en Java son una de las estructuras de datos más importantes y versátiles en la programación. A diferencia de las estructuras lineales como listas, pilas o colas, los árboles organizan los datos de forma jerárquica, lo que permite modelar relaciones naturales como sistemas de archivos, organigramas empresariales, árboles genealógicos o la estructura del DOM en una página web.

En este artículo aprenderás desde los conceptos fundamentales de la estructura de datos árbol hasta su implementación completa en Java, incluyendo árboles binarios, árboles binarios de búsqueda (BST), los diferentes tipos de recorridos y las operaciones esenciales de inserción, búsqueda y eliminación. Todo ello con código ejecutable y ejercicios prácticos progresivos.

Dominar los árboles es imprescindible para cualquier programador Java, ya que son la base de estructuras como TreeMap y TreeSet de la API estándar, y aparecen constantemente en entrevistas técnicas, algoritmos de compiladores, bases de datos indexadas y sistemas de toma de decisiones.

🌳 ¿Qué es un árbol en programación?

Un árbol es una estructura de datos no lineal compuesta por un conjunto de nodos (o vértices) conectados mediante aristas (o arcos) que satisface estas propiedades fundamentales:

Existe un nodo especial denominado raíz que no tiene padre. Cada nodo distinto de la raíz está conectado exactamente a un nodo padre mediante una arista. Existe un camino único desde la raíz hasta cualquier otro nodo del árbol. Esta última propiedad es la que distingue un árbol de un grafo general: en un árbol no hay ciclos.

A diferencia de una lista enlazada, donde cada elemento tiene como máximo un sucesor, un nodo de un árbol puede tener múltiples sucesores (hijos). Esta capacidad de ramificación es lo que convierte al árbol en una estructura tan potente para representar relaciones jerárquicas.

💡 Analogía práctica: Piensa en el sistema de archivos de tu ordenador. El directorio raíz (/ en Linux o C:\ en Windows) es el nodo raíz. Cada carpeta es un nodo interno que puede contener más carpetas (hijos) y archivos (hojas). No puedes llegar a un archivo por dos rutas diferentes dentro de la misma estructura, exactamente como en un árbol.

En Java, los árboles se implementan mediante clases donde cada objeto (nodo) contiene una referencia a sus nodos hijos. La naturaleza recursiva de los árboles hace que tanto su definición como la mayoría de sus algoritmos se expresen de forma natural mediante recursividad.

📖 Terminología fundamental de los árboles

Antes de implementar un árbol en Java, es esencial conocer la terminología que se utiliza universalmente en la literatura de estructuras de datos. Estos conceptos aparecerán continuamente en la documentación, en entrevistas técnicas y en el análisis de algoritmos.

Tipos de nodos

Concepto	Definición	Ejemplo
Nodo raíz	Nodo sin padre que inicia la jerarquía del árbol	El directorio `/` en un sistema de archivos
Nodo hoja (externo)	Nodo sin hijos, situado en los extremos del árbol	Un archivo dentro de una carpeta
Nodo interno	Nodo que tiene al menos un hijo	Una carpeta que contiene otras carpetas
Nodo padre	Nodo del que desciende directamente otro nodo	La carpeta que contiene un archivo
Nodo hijo	Nodo que desciende directamente de otro nodo	Un archivo o carpeta dentro de otra carpeta
Hermanos	Nodos que comparten el mismo padre	Dos archivos en la misma carpeta
Descendiente	Nodo alcanzable siguiendo aristas hacia abajo desde otro nodo	Cualquier archivo dentro de `/home`
Ancestro	Nodo en el camino desde un nodo dado hasta la raíz	`/home` es ancestro de `/home/user/doc.txt`

Propiedades topológicas

Propiedad	Definición	Fórmula / Nota
Camino	Secuencia de aristas que conecta dos nodos	Siempre único en un árbol
Longitud del camino	Número de aristas en un camino	Camino raíz → hoja de profundidad 3 tiene longitud 3
Profundidad de un nodo	Longitud del camino desde la raíz hasta ese nodo	La raíz tiene profundidad 0
Altura del árbol	Profundidad máxima entre todos los nodos hoja	Un árbol con solo la raíz tiene altura 0
Nivel	Conjunto de nodos a la misma profundidad	Nivel 0 = {raíz}, Nivel 1 = {hijos de raíz}, etc.
Grado de un nodo	Número de hijos de ese nodo	En un árbol binario, grado máximo = 2
Subárbol	Árbol formado por un nodo y todos sus descendientes	Cada nodo define un subárbol con raíz en él

✅ Relación clave: Un árbol con n nodos siempre tiene exactamente n − 1 aristas. Esta propiedad es consecuencia directa de que cada nodo (excepto la raíz) tiene exactamente un padre.

🔀 Árboles binarios: definición y propiedades

Un árbol binario es un caso particular de árbol en el que cada nodo tiene como máximo dos hijos, denominados hijo izquierdo e hijo derecho. Esta restricción simplifica enormemente la implementación y el análisis de algoritmos, y es la base de muchas estructuras de datos avanzadas como montículos, árboles AVL, árboles rojo-negro y árboles de expresión.

Definición recursiva

Un árbol binario se define de forma recursiva como: un árbol vacío (sin nodos), o un nodo raíz con un subárbol izquierdo y un subárbol derecho, donde ambos subárboles son a su vez árboles binarios. Esta definición recursiva es la que guía la implementación en Java y justifica que la mayoría de algoritmos sobre árboles binarios sean también recursivos.

Tipos de árboles binarios

Tipo	Definición	Propiedad destacada
Árbol binario completo	Todos los niveles están llenos excepto posiblemente el último, que se llena de izquierda a derecha	Se puede almacenar eficientemente en un array
Árbol binario lleno (full)	Cada nodo tiene 0 o exactamente 2 hijos	Si tiene h hojas, tiene h − 1 nodos internos
Árbol binario perfecto	Todos los nodos internos tienen 2 hijos y todas las hojas están al mismo nivel	Tiene exactamente 2^h+1 − 1 nodos (donde h es la altura)
Árbol binario degenerado	Cada nodo interno tiene exactamente 1 hijo	Se comporta como una lista enlazada: O(n) en búsqueda
Árbol binario de búsqueda (BST)	Para cada nodo, todos los valores del subárbol izquierdo son menores y los del derecho mayores	Búsqueda, inserción y eliminación en O(log n) promedio

⚠️ Cuidado con la degeneración: Si insertas elementos ya ordenados (1, 2, 3, 4, 5...) en un BST sin balanceo, el árbol degenera en una lista enlazada y todas las operaciones pasan de O(log n) a O(n). Para evitarlo, se usan árboles autobalanceados como AVL o rojo-negro.

⚙️ Implementación de un árbol binario en Java

La implementación de un árbol binario en Java requiere dos componentes fundamentales: una clase Nodo que represente cada elemento del árbol con referencias a sus hijos, y una clase ArbolBinario que gestione la raíz y las operaciones sobre la estructura completa.

Clase Nodo

Cada nodo almacena un dato (en este caso un entero, aunque puede generalizarse con genéricos) y dos referencias: una al hijo izquierdo y otra al hijo derecho. Si un hijo no existe, la referencia es null.

public class Nodo {
    int dato;
    Nodo izquierdo;
    Nodo derecho;

    // Constructor para nodo hoja (sin hijos)
    public Nodo(int dato) {
        this.dato = dato;
        this.izquierdo = null;
        this.derecho = null;
    }

    // Constructor para nodo con hijos
    public Nodo(int dato, Nodo izquierdo, Nodo derecho) {
        this.dato = dato;
        this.izquierdo = izquierdo;
        this.derecho = derecho;
    }

    public boolean esHoja() {
        return izquierdo == null && derecho == null;
    }
}

Clase ArbolBinario

La clase ArbolBinario encapsula la referencia a la raíz y ofrece métodos para calcular propiedades fundamentales del árbol como su tamaño, altura y número de hojas.

public class ArbolBinario {
    Nodo raiz;

    public ArbolBinario() {
        this.raiz = null;
    }

    public ArbolBinario(Nodo raiz) {
        this.raiz = raiz;
    }

    public boolean estaVacio() {
        return raiz == null;
    }

    // --- Tamaño del árbol (número de nodos) ---
    public int tamaño() {
        return tamañoRec(raiz);
    }

    private int tamañoRec(Nodo nodo) {
        if (nodo == null) return 0;
        return 1 + tamañoRec(nodo.izquierdo) + tamañoRec(nodo.derecho);
    }

    // --- Altura del árbol ---
    public int altura() {
        return alturaRec(raiz);
    }

    private int alturaRec(Nodo nodo) {
        if (nodo == null) return -1; // Árbol vacío: altura -1
        return 1 + Math.max(alturaRec(nodo.izquierdo),
                            alturaRec(nodo.derecho));
    }

    // --- Contar hojas ---
    public int contarHojas() {
        return contarHojasRec(raiz);
    }

    private int contarHojasRec(Nodo nodo) {
        if (nodo == null) return 0;
        if (nodo.esHoja()) return 1;
        return contarHojasRec(nodo.izquierdo)
             + contarHojasRec(nodo.derecho);
    }
}

Salida de ejemplo para un árbol construido manualmente:

// Árbol:       10
//            /    \
//          5       15
//         / \       \
//        3   7      20

Nodo n3 = new Nodo(3);
Nodo n7 = new Nodo(7);
Nodo n20 = new Nodo(20);
Nodo n5 = new Nodo(5, n3, n7);
Nodo n15 = new Nodo(15, null, n20);
Nodo n10 = new Nodo(10, n5, n15);

ArbolBinario arbol = new ArbolBinario(n10);
System.out.println("Tamaño: " + arbol.tamaño());       // Tamaño: 6
System.out.println("Altura: " + arbol.altura());        // Altura: 2
System.out.println("Hojas: " + arbol.contarHojas());    // Hojas: 3

💡 Observa el patrón recursivo: Cada método sigue la misma estructura: caso base (nodo null → retornar valor por defecto) y caso recursivo (operar con el nodo actual y llamar recursivamente a izquierdo y derecho). Este patrón es universal en los algoritmos sobre árboles.

🔍 Árbol binario de búsqueda (BST)

Un árbol binario de búsqueda (Binary Search Tree, BST) es un árbol binario con una propiedad de orden que lo convierte en una estructura extremadamente eficiente para buscar, insertar y eliminar datos. La regla es sencilla pero poderosa:

✅ Propiedad BST: Para todo nodo del árbol, todos los valores en su subárbol izquierdo son estrictamente menores, y todos los valores en su subárbol derecho son estrictamente mayores.

Esta propiedad permite descartar la mitad del árbol en cada comparación, logrando una complejidad de O(log n) en el caso promedio para búsqueda, inserción y eliminación, similar a una búsqueda binaria sobre un array ordenado pero con la flexibilidad de las inserciones dinámicas.

public class ArbolBST {
    private Nodo raiz;

    public ArbolBST() {
        this.raiz = null;
    }

    // --- Inserción ---
    public void insertar(int valor) {
        raiz = insertarRec(raiz, valor);
    }

    private Nodo insertarRec(Nodo nodo, int valor) {
        if (nodo == null) {
            return new Nodo(valor);
        }
        if (valor < nodo.dato) {
            nodo.izquierdo = insertarRec(nodo.izquierdo, valor);
        } else if (valor > nodo.dato) {
            nodo.derecho = insertarRec(nodo.derecho, valor);
        }
        // Si valor == nodo.dato, no se inserta (sin duplicados)
        return nodo;
    }

    // --- Búsqueda ---
    public boolean buscar(int valor) {
        return buscarRec(raiz, valor);
    }

    private boolean buscarRec(Nodo nodo, int valor) {
        if (nodo == null) return false;
        if (valor == nodo.dato) return true;
        if (valor < nodo.dato) return buscarRec(nodo.izquierdo, valor);
        return buscarRec(nodo.derecho, valor);
    }

    // --- Valor mínimo (nodo más a la izquierda) ---
    public int minimo() {
        if (raiz == null) throw new IllegalStateException("Árbol vacío");
        Nodo actual = raiz;
        while (actual.izquierdo != null) {
            actual = actual.izquierdo;
        }
        return actual.dato;
    }

    // --- Valor máximo (nodo más a la derecha) ---
    public int maximo() {
        if (raiz == null) throw new IllegalStateException("Árbol vacío");
        Nodo actual = raiz;
        while (actual.derecho != null) {
            actual = actual.derecho;
        }
        return actual.dato;
    }

    // Getter para la raíz (usado en recorridos)
    public Nodo getRaiz() {
        return raiz;
    }
}

Ejemplo de uso:

ArbolBST bst = new ArbolBST();
bst.insertar(50);
bst.insertar(30);
bst.insertar(70);
bst.insertar(20);
bst.insertar(40);
bst.insertar(60);
bst.insertar(80);

// Árbol resultante:
//         50
//       /    \
//     30      70
//    /  \    /  \
//  20   40  60   80

System.out.println(bst.buscar(40));  // true
System.out.println(bst.buscar(55));  // false
System.out.println(bst.minimo());    // 20
System.out.println(bst.maximo());    // 80

Complejidad temporal del BST

Operación	Caso promedio	Peor caso (degenerado)
Búsqueda	O(log n)	O(n)
Inserción	O(log n)	O(n)
Eliminación	O(log n)	O(n)
Mínimo / Máximo	O(log n)	O(n)
Recorrido inorden	O(n)	O(n)

🔄 Recorridos de un árbol: inorden, preorden, postorden

Recorrer un árbol significa visitar cada uno de sus nodos exactamente una vez. En los recorridos en profundidad (Depth-First Search, DFS), se explora cada rama hasta llegar a las hojas antes de retroceder. Existen tres variantes según el momento en que se procesa el nodo raíz de cada subárbol:

Recorrido	Orden de visita	Uso principal
Preorden	Raíz → Izquierdo → Derecho	Copiar la estructura del árbol, serialización
Inorden	Izquierdo → Raíz → Derecho	En un BST, produce los valores ordenados
Postorden	Izquierdo → Derecho → Raíz	Liberar memoria, evaluar expresiones aritméticas

public class Recorridos {

    // ▶️ Recorrido PREORDEN: raíz → izquierdo → derecho
    public static void preorden(Nodo nodo) {
        if (nodo == null) return;
        System.out.print(nodo.dato + " ");
        preorden(nodo.izquierdo);
        preorden(nodo.derecho);
    }

    // ▶️ Recorrido INORDEN: izquierdo → raíz → derecho
    public static void inorden(Nodo nodo) {
        if (nodo == null) return;
        inorden(nodo.izquierdo);
        System.out.print(nodo.dato + " ");
        inorden(nodo.derecho);
    }

    // ▶️ Recorrido POSTORDEN: izquierdo → derecho → raíz
    public static void postorden(Nodo nodo) {
        if (nodo == null) return;
        postorden(nodo.izquierdo);
        postorden(nodo.derecho);
        System.out.print(nodo.dato + " ");
    }
}

// --- Ejemplo de uso con el BST anterior ---
//         50
//       /    \
//     30      70
//    /  \    /  \
//  20   40  60   80

// Preorden:  50 30 20 40 70 60 80
// Inorden:   20 30 40 50 60 70 80   ← ¡Ordenados!
// Postorden: 20 40 30 60 80 70 50

✅ Dato clave: El recorrido inorden de un BST siempre produce los elementos en orden ascendente. Si no lo hace, el árbol no cumple la propiedad BST. Esta es una excelente forma de verificar la validez de un BST.

📊 Recorrido en anchura (BFS)

El recorrido en anchura (Breadth-First Search, BFS) visita los nodos nivel por nivel, de izquierda a derecha, empezando por la raíz. A diferencia de los recorridos en profundidad, que utilizan recursividad (o una pila), el BFS utiliza una cola como estructura auxiliar.

import java.util.LinkedList;
import java.util.Queue;

public class RecorridoBFS {

    public static void bfs(Nodo raiz) {
        if (raiz == null) return;

        Queue<Nodo> cola = new LinkedList<>();
        cola.add(raiz);

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

            if (actual.izquierdo != null) {
                cola.add(actual.izquierdo);
            }
            if (actual.derecho != null) {
                cola.add(actual.derecho);
            }
        }
    }
}

// Con el árbol:    50
//                /    \
//              30      70
//             /  \    /  \
//           20   40  60   80

// BFS: 50 30 70 20 40 60 80  ← nivel por nivel

El algoritmo funciona así: se encola la raíz. En cada iteración, se desencola un nodo, se procesa y se encolan sus hijos (si existen). El proceso continúa hasta que la cola queda vacía. La complejidad es O(n) en tiempo y O(w) en espacio, donde w es la anchura máxima del árbol.

🛠️ Operaciones principales: inserción, búsqueda y eliminación

Las tres operaciones fundamentales de un BST son inserción, búsqueda y eliminación. Ya hemos visto la inserción y búsqueda. La eliminación es la más compleja porque debe mantener la propiedad BST intacta. Se distinguen tres casos:

Los tres casos de eliminación en un BST

Caso 1 — Nodo hoja: simplemente se elimina, estableciendo la referencia del padre a null.

Caso 2 — Nodo con un solo hijo: se reemplaza el nodo por su único hijo, conectando al padre directamente con el nieto.

Caso 3 — Nodo con dos hijos: se busca el sucesor inorden (el menor valor del subárbol derecho), se copia su valor al nodo a eliminar y se elimina recursivamente el sucesor inorden del subárbol derecho.

// Añadir a la clase ArbolBST:

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

private Nodo eliminarRec(Nodo nodo, int valor) {
    if (nodo == null) return null;

    if (valor < nodo.dato) {
        nodo.izquierdo = eliminarRec(nodo.izquierdo, valor);
    } else if (valor > nodo.dato) {
        nodo.derecho = eliminarRec(nodo.derecho, valor);
    } else {
        // Nodo encontrado: aplicar el caso correspondiente

        // Caso 1: nodo hoja (sin hijos)
        if (nodo.izquierdo == null && nodo.derecho == null) {
            return null;
        }
        // Caso 2a: solo tiene hijo derecho
        if (nodo.izquierdo == null) {
            return nodo.derecho;
        }
        // Caso 2b: solo tiene hijo izquierdo
        if (nodo.derecho == null) {
            return nodo.izquierdo;
        }
        // Caso 3: tiene dos hijos
        // Buscar el sucesor inorden (mínimo del subárbol derecho)
        int sucesor = encontrarMinimo(nodo.derecho);
        nodo.dato = sucesor;
        nodo.derecho = eliminarRec(nodo.derecho, sucesor);
    }
    return nodo;
}

private int encontrarMinimo(Nodo nodo) {
    while (nodo.izquierdo != null) {
        nodo = nodo.izquierdo;
    }
    return nodo.dato;
}

Ejemplo de eliminación:

ArbolBST bst = new ArbolBST();
int[] valores = {50, 30, 70, 20, 40, 60, 80};
for (int v : valores) bst.insertar(v);

// Estado inicial:      50
//                    /    \
//                  30      70
//                 /  \    /  \
//               20   40  60   80

bst.eliminar(20);  // Caso 1: hoja → se elimina directamente
// Resultado:           50
//                    /    \
//                  30      70
//                    \    /  \
//                    40  60   80

bst.eliminar(30);  // Caso 2: un hijo → 40 sube
// Resultado:           50
//                    /    \
//                  40      70
//                         /  \
//                        60   80

bst.eliminar(50);  // Caso 3: dos hijos → sucesor inorden (60) reemplaza
// Resultado:           60
//                    /    \
//                  40      70
//                            \
//                            80

📋 Ejemplo integrador: sistema de agenda telefónica

Vamos a aplicar todo lo aprendido en un ejemplo práctico: una agenda telefónica que almacena contactos ordenados alfabéticamente usando un BST. Este ejemplo muestra cómo adaptar el árbol para trabajar con objetos complejos en lugar de simples enteros.

public class AgendaTelefonica {

    // --- Nodo especializado para contactos ---
    private static class NodoContacto {
        String nombre;
        String telefono;
        NodoContacto izquierdo, derecho;

        NodoContacto(String nombre, String telefono) {
            this.nombre = nombre;
            this.telefono = telefono;
        }
    }

    private NodoContacto raiz;

    // --- Insertar contacto (ordenado por nombre) ---
    public void agregarContacto(String nombre, String telefono) {
        raiz = insertarRec(raiz, nombre, telefono);
    }

    private NodoContacto insertarRec(NodoContacto nodo,
                                      String nombre, String telefono) {
        if (nodo == null) return new NodoContacto(nombre, telefono);

        int cmp = nombre.compareToIgnoreCase(nodo.nombre);
        if (cmp < 0) {
            nodo.izquierdo = insertarRec(nodo.izquierdo, nombre, telefono);
        } else if (cmp > 0) {
            nodo.derecho = insertarRec(nodo.derecho, nombre, telefono);
        } else {
            nodo.telefono = telefono; // Actualizar si ya existe
        }
        return nodo;
    }

    // --- Buscar teléfono por nombre ---
    public String buscarTelefono(String nombre) {
        NodoContacto resultado = buscarRec(raiz, nombre);
        return resultado != null ? resultado.telefono : "No encontrado";
    }

    private NodoContacto buscarRec(NodoContacto nodo, String nombre) {
        if (nodo == null) return null;
        int cmp = nombre.compareToIgnoreCase(nodo.nombre);
        if (cmp == 0) return nodo;
        if (cmp < 0) return buscarRec(nodo.izquierdo, nombre);
        return buscarRec(nodo.derecho, nombre);
    }

    // --- Listar contactos en orden alfabético (inorden) ---
    public void listarContactos() {
        System.out.println("--- Agenda telefónica ---");
        inorden(raiz);
    }

    private void inorden(NodoContacto nodo) {
        if (nodo == null) return;
        inorden(nodo.izquierdo);
        System.out.printf("  %-15s → %s%n", nodo.nombre, nodo.telefono);
        inorden(nodo.derecho);
    }

    // --- Programa principal ---
    public static void main(String[] args) {
        AgendaTelefonica agenda = new AgendaTelefonica();

        agenda.agregarContacto("María",   "612-345-678");
        agenda.agregarContacto("Alberto", "698-111-222");
        agenda.agregarContacto("Zara",    "655-999-888");
        agenda.agregarContacto("Carlos",  "611-333-444");
        agenda.agregarContacto("Elena",   "677-555-666");

        agenda.listarContactos();

        System.out.println();
        System.out.println("Teléfono de Carlos: "
            + agenda.buscarTelefono("Carlos"));
        System.out.println("Teléfono de Pedro: "
            + agenda.buscarTelefono("Pedro"));
    }
}

--- Agenda telefónica ---
  Alberto         → 698-111-222
  Carlos          → 611-333-444
  Elena           → 677-555-666
  María           → 612-345-678
  Zara            → 655-999-888

Teléfono de Carlos: 611-333-444
Teléfono de Pedro: No encontrado

💡 Observa: Los contactos se listan en orden alfabético gracias al recorrido inorden del BST, sin necesidad de ordenar explícitamente. El método compareToIgnoreCase permite comparar cadenas respetando el orden lexicográfico sin distinguir mayúsculas y minúsculas.

❌ Errores frecuentes al trabajar con árboles

Los árboles son una estructura donde los errores de implementación pueden ser sutiles y difíciles de depurar. A continuación se documentan los errores más comunes entre estudiantes y programadores que se inician con esta estructura de datos.

Error 1: No asignar el resultado de la inserción recursiva

// ❌ INCORRECTO: no se asigna el resultado
private void insertarRec(Nodo nodo, int valor) {
    if (nodo == null) {
        nodo = new Nodo(valor); // ¡Solo cambia la referencia local!
    }
    // El nuevo nodo NUNCA se conecta al árbol
}

// ✅ CORRECTO: retornar el nodo para que el padre lo asigne
private Nodo insertarRec(Nodo nodo, int valor) {
    if (nodo == null) {
        return new Nodo(valor); // Se retorna al padre
    }
    if (valor < nodo.dato) {
        nodo.izquierdo = insertarRec(nodo.izquierdo, valor);
    } else if (valor > nodo.dato) {
        nodo.derecho = insertarRec(nodo.derecho, valor);
    }
    return nodo;
}

Error 2: NullPointerException al acceder a hijos sin verificar null

// ❌ INCORRECTO: no verifica null antes de acceder
private int alturaRec(Nodo nodo) {
    return 1 + Math.max(alturaRec(nodo.izquierdo),  // NPE si nodo es null
                        alturaRec(nodo.derecho));
}

// ✅ CORRECTO: caso base antes de cualquier acceso
private int alturaRec(Nodo nodo) {
    if (nodo == null) return -1;  // Caso base primero
    return 1 + Math.max(alturaRec(nodo.izquierdo),
                        alturaRec(nodo.derecho));
}

Error 3: Confundir la propiedad BST

// Este árbol parece correcto localmente pero NO es un BST válido:
//        50
//       /  \
//     30    70
//       \
//       60   ← ¡ERROR! 60 > 50, pero está en el subárbol IZQUIERDO de 50
//
// La propiedad BST exige que TODOS los valores del subárbol izquierdo
// de 50 sean menores que 50, incluidos los nietos, bisnietos, etc.

Error 4: Olvidar mantener la propiedad BST al eliminar

Al eliminar un nodo con dos hijos, algunos programadores intentan reemplazarlo por uno de sus hijos directamente, lo que rompe la propiedad BST. La solución correcta es reemplazar por el sucesor inorden (mínimo del subárbol derecho) o el predecesor inorden (máximo del subárbol izquierdo).

✏️ Ejercicios prácticos resueltos

Ejercicio 1: Verificar si un árbol binario es un BST válido

Implementa un método esBST() que verifique si un árbol binario cumple la propiedad de árbol binario de búsqueda. Pista: utiliza un recorrido inorden y comprueba que los valores están en orden ascendente.

Ver solución

public class VerificadorBST {

    private static Integer valorAnterior = null;

    public static boolean esBST(Nodo nodo) {
        valorAnterior = null; // Reiniciar antes de cada verificación
        return esBSTRec(nodo);
    }

    private static boolean esBSTRec(Nodo nodo) {
        if (nodo == null) return true;

        // Verificar subárbol izquierdo
        if (!esBSTRec(nodo.izquierdo)) return false;

        // Verificar nodo actual contra el anterior (inorden)
        if (valorAnterior != null && nodo.dato <= valorAnterior) {
            return false;
        }
        valorAnterior = nodo.dato;

        // Verificar subárbol derecho
        return esBSTRec(nodo.derecho);
    }

    // Ejemplo de uso:
    // ArbolBST bst = new ArbolBST();
    // bst.insertar(50); bst.insertar(30); bst.insertar(70);
    // System.out.println(esBST(bst.getRaiz())); // true
}

Ejercicio 2: Calcular la suma de todos los nodos del árbol

Implementa un método recursivo sumaTotal() que devuelva la suma de todos los valores almacenados en los nodos del árbol.

Ver solución

// Añadir a la clase ArbolBinario o ArbolBST:

public int sumaTotal() {
    return sumaTotalRec(raiz);
}

private int sumaTotalRec(Nodo nodo) {
    if (nodo == null) return 0;
    return nodo.dato
         + sumaTotalRec(nodo.izquierdo)
         + sumaTotalRec(nodo.derecho);
}

// Ejemplo:
//         50
//       /    \
//     30      70
//    /  \    /  \
//  20   40  60   80
//
// Suma: 20 + 30 + 40 + 50 + 60 + 70 + 80 = 350
// System.out.println(bst.sumaTotal()); // 350

Ejercicio 3: Obtener los nodos en un nivel específico

Implementa un método nodosEnNivel(int nivel) que imprima todos los nodos que se encuentran a una profundidad determinada. El nivel 0 es la raíz, el nivel 1 son los hijos de la raíz, etc.

Ver solución

// Añadir a ArbolBinario o ArbolBST:

public void nodosEnNivel(int nivel) {
    System.out.print("Nodos en nivel " + nivel + ": ");
    nodosEnNivelRec(raiz, nivel, 0);
    System.out.println();
}

private void nodosEnNivelRec(Nodo nodo, int nivelObjetivo,
                              int nivelActual) {
    if (nodo == null) return;
    if (nivelActual == nivelObjetivo) {
        System.out.print(nodo.dato + " ");
        return; // No es necesario bajar más
    }
    nodosEnNivelRec(nodo.izquierdo, nivelObjetivo, nivelActual + 1);
    nodosEnNivelRec(nodo.derecho, nivelObjetivo, nivelActual + 1);
}

// Ejemplo con el BST:
//         50           ← nivel 0
//       /    \
//     30      70       ← nivel 1
//    /  \    /  \
//  20   40  60   80    ← nivel 2
//
// bst.nodosEnNivel(0);  → Nodos en nivel 0: 50
// bst.nodosEnNivel(1);  → Nodos en nivel 1: 30 70
// bst.nodosEnNivel(2);  → Nodos en nivel 2: 20 40 60 80

📚 Artículos relacionados

❓ Preguntas frecuentes sobre Árboles en Java: estructura de datos con implementación completa

Las dudas más comunes respondidas de forma clara y directa.

Un árbol binario es una estructura de datos jerárquica en la que cada nodo tiene como máximo dos hijos, denominados hijo izquierdo e hijo derecho. En Java se implementa mediante clases con referencias a los nodos hijos, permitiendo organizar datos de forma eficiente para operaciones de búsqueda, inserción y eliminación.

Un árbol binario es cualquier árbol donde cada nodo tiene 0, 1 o 2 hijos sin restricciones de orden. Un árbol binario de búsqueda (BST) añade la restricción de que, para cada nodo, todos los valores del subárbol izquierdo son menores y todos los del subárbol derecho son mayores, lo que permite búsquedas eficientes en O(log n).

Los tres recorridos en profundidad son: inorden (izquierdo → raíz → derecho), que en un BST produce los elementos ordenados; preorden (raíz → izquierdo → derecho), útil para copiar la estructura del árbol; y postorden (izquierdo → derecho → raíz), usado para liberar memoria o evaluar expresiones.

Un BST es preferible cuando necesitas realizar búsquedas, inserciones y eliminaciones frecuentes con complejidad O(log n) en el caso promedio. Un ArrayList es mejor cuando necesitas acceso por índice O(1) o cuando los datos se insertan una vez y luego solo se leen secuencialmente.

Java ofrece TreeMap y TreeSet en el paquete java.util, que internamente utilizan un árbol rojo-negro (un tipo de árbol binario de búsqueda autobalanceado). TreeMap implementa Map con claves ordenadas, y TreeSet implementa Set con elementos ordenados, ambos garantizando operaciones en O(log n).

💬 Foro de discusión

¿Tienes dudas sobre Árboles en Java: estructura de datos con implementación completa? Comparte tu pregunta con la comunidad.

¿Tienes cuenta? o comenta como invitado ↓

Todavía no hay mensajes. ¡Sé el primero en participar!

Árboles en Java: estructura de datos con implementación completa

🌳 ¿Qué es un árbol en programación?

📖 Terminología fundamental de los árboles

Tipos de nodos

Propiedades topológicas

🔀 Árboles binarios: definición y propiedades

Definición recursiva

Tipos de árboles binarios

⚙️ Implementación de un árbol binario en Java

Clase Nodo

Clase ArbolBinario

🔍 Árbol binario de búsqueda (BST)

Complejidad temporal del BST

🔄 Recorridos de un árbol: inorden, preorden, postorden

📊 Recorrido en anchura (BFS)

🛠️ Operaciones principales: inserción, búsqueda y eliminación

Los tres casos de eliminación en un BST

📋 Ejemplo integrador: sistema de agenda telefónica

❌ Errores frecuentes al trabajar con árboles

Error 1: No asignar el resultado de la inserción recursiva

Error 2: NullPointerException al acceder a hijos sin verificar null

Error 3: Confundir la propiedad BST

Error 4: Olvidar mantener la propiedad BST al eliminar

✏️ Ejercicios prácticos resueltos

📚 Artículos relacionados

❓ Preguntas frecuentes sobre Árboles en Java: estructura de datos con implementación completa

💬 Foro de discusión

🔑 Recuperar contraseña

Crear cuenta

¿Cómo valorarías tu experiencia aprendiendo en esta sección?

¡Gracias por tu valoración!

🌳 ¿Qué es un árbol en programación?

📖 Terminología fundamental de los árboles

Tipos de nodos

Propiedades topológicas

🔀 Árboles binarios: definición y propiedades

Definición recursiva

Tipos de árboles binarios

⚙️ Implementación de un árbol binario en Java

Clase Nodo

Clase ArbolBinario

🔍 Árbol binario de búsqueda (BST)

Complejidad temporal del BST

🔄 Recorridos de un árbol: inorden, preorden, postorden

📊 Recorrido en anchura (BFS)

🛠️ Operaciones principales: inserción, búsqueda y eliminación

Los tres casos de eliminación en un BST

📋 Ejemplo integrador: sistema de agenda telefónica

❌ Errores frecuentes al trabajar con árboles

Error 1: No asignar el resultado de la inserción recursiva

Error 2: NullPointerException al acceder a hijos sin verificar null

Error 3: Confundir la propiedad BST

Error 4: Olvidar mantener la propiedad BST al eliminar

✏️ Ejercicios prácticos resueltos

📚 Artículos relacionados

❓ Preguntas frecuentes sobre Árboles en Java: estructura de datos con implementación completa

💬 Foro de discusión

Iniciar sesión

🔑 Recuperar contraseña

Crear cuenta