Exploración de Árboles en Java

public class NodoArbol<T> {
    T dato;
    NodoArbol<T> izquierdo;
    NodoArbol<T> derecho;

    public NodoArbol(T dato) {
        this.dato = dato;
        this.izquierdo = null;
        this.derecho = null;
    }

    public NodoArbol(T dato, NodoArbol<T> izquierdo, NodoArbol<T> derecho) {
        this.dato = dato;
        this.izquierdo = izquierdo;
        this.derecho = derecho;
    }

    @Override
    public String toString() {
        return dato.toString();
    }
}

/*
 * Árbol de ejemplo:
 *
 *        a
 *       / \
 *      b   c
 *     / \
 *    d   e
 */
NodoArbol<String> d = new NodoArbol<>("d");
NodoArbol<String> e = new NodoArbol<>("e");
NodoArbol<String> b = new NodoArbol<>("b", d, e);
NodoArbol<String> c = new NodoArbol<>("c");
NodoArbol<String> a = new NodoArbol<>("a", b, c);
// 'a' es la raíz del árbol

/**
 * Recorrido en preorden: Raíz → Izquierdo → Derecho
 * @param nodo raíz del subárbol a recorrer
 */
public static <T> void preorden(NodoArbol<T> nodo) {
    if (nodo == null) {
        return; // Caso base: subárbol vacío
    }
    System.out.print(nodo.dato + " ");  // 1. Procesar raíz
    preorden(nodo.izquierdo);            // 2. Recorrer subárbol izquierdo
    preorden(nodo.derecho);              // 3. Recorrer subárbol derecho
}

preorden(a)  →  imprime "a", luego preorden(b), luego preorden(c)
  preorden(b)  →  imprime "b", luego preorden(d), luego preorden(e)
    preorden(d)  →  imprime "d", luego preorden(null), preorden(null) → retorna
    preorden(e)  →  imprime "e", luego preorden(null), preorden(null) → retorna
  preorden(c)  →  imprime "c", luego preorden(null), preorden(null) → retorna

Resultado: a  b  d  e  c

/**
 * Recorrido en inorden: Izquierdo → Raíz → Derecho
 * En un BST, produce los valores en orden ascendente.
 * @param nodo raíz del subárbol a recorrer
 */
public static <T> void inorden(NodoArbol<T> nodo) {
    if (nodo == null) {
        return;
    }
    inorden(nodo.izquierdo);             // 1. Recorrer subárbol izquierdo
    System.out.print(nodo.dato + " ");   // 2. Procesar raíz
    inorden(nodo.derecho);               // 3. Recorrer subárbol derecho
}

inorden(a) → inorden(b), imprime "a", inorden(c)
  inorden(b) → inorden(d), imprime "b", inorden(e)
    inorden(d) → inorden(null), imprime "d", inorden(null)
    inorden(e) → inorden(null), imprime "e", inorden(null)
  inorden(c) → inorden(null), imprime "c", inorden(null)

Resultado: d  b  e  a  c

/*
 * BST numérico:
 *        8
 *       / \
 *      3   10
 *     / \    \
 *    1   6    14
 */
NodoArbol<Integer> n1  = new NodoArbol<>(1);
NodoArbol<Integer> n6  = new NodoArbol<>(6);
NodoArbol<Integer> n14 = new NodoArbol<>(14);
NodoArbol<Integer> n3  = new NodoArbol<>(3, n1, n6);
NodoArbol<Integer> n10 = new NodoArbol<>(10, null, n14);
NodoArbol<Integer> n8  = new NodoArbol<>(8, n3, n10);

inorden(n8);  // Salida: 1  3  6  8  10  14  (¡ordenados!)

/**
 * Recorrido en postorden: Izquierdo → Derecho → Raíz
 * Ideal para liberar memoria o calcular propiedades bottom-up.
 * @param nodo raíz del subárbol a recorrer
 */
public static <T> void postorden(NodoArbol<T> nodo) {
    if (nodo == null) {
        return;
    }
    postorden(nodo.izquierdo);           // 1. Recorrer subárbol izquierdo
    postorden(nodo.derecho);             // 2. Recorrer subárbol derecho
    System.out.print(nodo.dato + " ");   // 3. Procesar raíz
}

postorden(a) → postorden(b), postorden(c), imprime "a"
  postorden(b) → postorden(d), postorden(e), imprime "b"
    postorden(d) → postorden(null), postorden(null), imprime "d"
    postorden(e) → postorden(null), postorden(null), imprime "e"
  postorden(c) → postorden(null), postorden(null), imprime "c"

Resultado: d  e  b  c  a

/**
 * Calcula la altura de un árbol binario usando recorrido postorden.
 * La altura de un árbol vacío es -1 por convención.
 */
public static <T> int altura(NodoArbol<T> nodo) {
    if (nodo == null) {
        return -1;  // Caso base
    }
    int alturaIzq = altura(nodo.izquierdo);   // Postorden: primero hijos
    int alturaDer = altura(nodo.derecho);
    return 1 + Math.max(alturaIzq, alturaDer); // Después raíz
}

// Ejemplo:
System.out.println(altura(a)); // Salida: 2 (a→b→d tiene 2 aristas)

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

/**
 * Recorrido en anchura (BFS): nivel por nivel, de izquierda a derecha.
 * Usa una cola FIFO como estructura auxiliar.
 * @param raiz nodo raíz del árbol
 */
public static <T> void bfs(NodoArbol<T> raiz) {
    if (raiz == null) {
        return;
    }

    Queue<NodoArbol<T>> cola = new LinkedList<>();
    cola.add(raiz);  // 1. Insertar raíz

    while (!cola.isEmpty()) {
        NodoArbol<T> actual = cola.poll();          // 2. Extraer del frente
        System.out.print(actual.dato + " ");         // 3. Procesar

        if (actual.izquierdo != null) {
            cola.add(actual.izquierdo);              // 4a. Encolar hijo izquierdo
        }
        if (actual.derecho != null) {
            cola.add(actual.derecho);                // 4b. Encolar hijo derecho
        }
    }
}

Cola inicial: [a]

Paso 1: Extraer a → Procesar "a" → Encolar b, c  → Cola: [b, c]
Paso 2: Extraer b → Procesar "b" → Encolar d, e  → Cola: [c, d, e]
Paso 3: Extraer c → Procesar "c" → Sin hijos      → Cola: [d, e]
Paso 4: Extraer d → Procesar "d" → Sin hijos      → Cola: [e]
Paso 5: Extraer e → Procesar "e" → Sin hijos      → Cola: []

Resultado: a  b  c  d  e   (nivel 0, nivel 1, nivel 2)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Recorrido BFS por niveles. Devuelve una lista de listas,
 * donde cada sublista contiene los valores de un nivel del árbol.
 */
public static <T> List<List<T>> bfsPorNiveles(NodoArbol<T> raiz) {
    List<List<T>> niveles = new ArrayList<>();
    if (raiz == null) {
        return niveles;
    }

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

    while (!cola.isEmpty()) {
        int tamanoNivel = cola.size(); // Nodos en el nivel actual
        List<T> nivelActual = new ArrayList<>();

        for (int i = 0; i < tamanoNivel; i++) {
            NodoArbol<T> nodo = cola.poll();
            nivelActual.add(nodo.dato);

            if (nodo.izquierdo != null) cola.add(nodo.izquierdo);
            if (nodo.derecho != null)   cola.add(nodo.derecho);
        }
        niveles.add(nivelActual);
    }
    return niveles;
}

// Ejemplo de uso:
// bfsPorNiveles(a) → [[a], [b, c], [d, e]]

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Recorrido en preorden usando pila explícita (iterativo).
 * Evita StackOverflowError en árboles muy profundos.
 */
public static <T> void preordenIterativo(NodoArbol<T> raiz) {
    if (raiz == null) {
        return;
    }

    Deque<NodoArbol<T>> pila = new ArrayDeque<>();
    pila.push(raiz);

    while (!pila.isEmpty()) {
        NodoArbol<T> actual = pila.pop();
        System.out.print(actual.dato + " ");

        // Apilar derecho primero para que izquierdo salga antes (LIFO)
        if (actual.derecho != null) {
            pila.push(actual.derecho);
        }
        if (actual.izquierdo != null) {
            pila.push(actual.izquierdo);
        }
    }
}

// preordenIterativo(a) → a  b  d  e  c  (mismo resultado que recursivo)

/**
 * Recorrido en inorden usando pila explícita (iterativo).
 */
public static <T> void inordenIterativo(NodoArbol<T> raiz) {
    Deque<NodoArbol<T>> pila = new ArrayDeque<>();
    NodoArbol<T> actual = raiz;

    while (actual != null || !pila.isEmpty()) {
        // Descender por la izquierda hasta el fondo
        while (actual != null) {
            pila.push(actual);
            actual = actual.izquierdo;
        }
        // Procesar el nodo del tope de la pila
        actual = pila.pop();
        System.out.print(actual.dato + " ");
        // Moverse al subárbol derecho
        actual = actual.derecho;
    }
}

// inordenIterativo(a) → d  b  e  a  c  (mismo resultado que recursivo)

import java.util.*;

/**
 * Nodo del sistema de archivos. Puede ser archivo o directorio.
 * Los directorios pueden tener múltiples hijos (árbol n-ario).
 */
class NodoFS {
    String nombre;
    boolean esDirectorio;
    long tamanoBytes;          // Solo para archivos
    List<NodoFS> hijos;       // Solo para directorios

    // Constructor para archivo
    NodoFS(String nombre, long tamanoBytes) {
        this.nombre = nombre;
        this.esDirectorio = false;
        this.tamanoBytes = tamanoBytes;
        this.hijos = Collections.emptyList();
    }

    // Constructor para directorio
    NodoFS(String nombre, NodoFS... hijos) {
        this.nombre = nombre;
        this.esDirectorio = true;
        this.tamanoBytes = 0;
        this.hijos = Arrays.asList(hijos);
    }
}

public class ExploradorFS {

    /**
     * PREORDEN: Listar todos los elementos con indentación.
     * Procesa la raíz primero → muestra la estructura jerárquica.
     */
    public static void listarArbol(NodoFS nodo, int profundidad) {
        if (nodo == null) return;

        String indent = "  ".repeat(profundidad);
        String icono = nodo.esDirectorio ? "📁" : "📄";
        String info = nodo.esDirectorio ? "" : " (" + nodo.tamanoBytes + " bytes)";
        System.out.println(indent + icono + " " + nodo.nombre + info);

        for (NodoFS hijo : nodo.hijos) {
            listarArbol(hijo, profundidad + 1);
        }
    }

    /**
     * POSTORDEN: Calcular el tamaño total de un directorio.
     * Procesa los hijos primero → suma sus tamaños antes de reportar.
     */
    public static long calcularTamano(NodoFS nodo) {
        if (nodo == null) return 0;

        if (!nodo.esDirectorio) {
            return nodo.tamanoBytes;  // Archivo: retornar su tamaño
        }

        long total = 0;
        for (NodoFS hijo : nodo.hijos) {
            total += calcularTamano(hijo);  // Postorden: hijos primero
        }
        return total;  // Luego la raíz acumula
    }

    /**
     * BFS: Encontrar el archivo más grande en el primer nivel.
     * Explora nivel por nivel → ideal para búsquedas de proximidad.
     */
    public static String archivoMasGrandeNivel(NodoFS raiz, int nivelObjetivo) {
        if (raiz == null) return null;

        Queue<NodoFS> cola = new LinkedList<>();
        cola.add(raiz);
        int nivelActual = 0;
        String mayorArchivo = null;
        long mayorTamano = -1;

        while (!cola.isEmpty() && nivelActual <= nivelObjetivo) {
            int tamNivel = cola.size();
            for (int i = 0; i < tamNivel; i++) {
                NodoFS nodo = cola.poll();
                if (nivelActual == nivelObjetivo && !nodo.esDirectorio) {
                    if (nodo.tamanoBytes > mayorTamano) {
                        mayorTamano = nodo.tamanoBytes;
                        mayorArchivo = nodo.nombre;
                    }
                }
                for (NodoFS hijo : nodo.hijos) {
                    cola.add(hijo);
                }
            }
            nivelActual++;
        }
        return mayorArchivo;
    }

    public static void main(String[] args) {
        // Construir sistema de archivos de ejemplo
        NodoFS raiz = new NodoFS("proyecto",
            new NodoFS("src",
                new NodoFS("Main.java", 2048),
                new NodoFS("Utils.java", 1024),
                new NodoFS("modelos",
                    new NodoFS("Usuario.java", 512),
                    new NodoFS("Producto.java", 768)
                )
            ),
            new NodoFS("docs",
                new NodoFS("README.md", 4096),
                new NodoFS("API.md", 8192)
            ),
            new NodoFS("pom.xml", 256)
        );

        System.out.println("=== Listado del árbol (Preorden) ===");
        listarArbol(raiz, 0);

        System.out.println("\n=== Tamaño total (Postorden) ===");
        System.out.println("Total: " + calcularTamano(raiz) + " bytes");

        System.out.println("\n=== Archivo más grande en nivel 2 (BFS) ===");
        System.out.println("Archivo: " + archivoMasGrandeNivel(raiz, 2));
    }
}

=== Listado del árbol (Preorden) ===
📁 proyecto
  📁 src
    📄 Main.java (2048 bytes)
    📄 Utils.java (1024 bytes)
    📁 modelos
      📄 Usuario.java (512 bytes)
      📄 Producto.java (768 bytes)
  📁 docs
    📄 README.md (4096 bytes)
    📄 API.md (8192 bytes)
  📄 pom.xml (256 bytes)

=== Tamaño total (Postorden) ===
Total: 16896 bytes

=== Archivo más grande en nivel 2 (BFS) ===
Archivo: API.md

// ❌ MAL: sin caso base → StackOverflowError
public static void preorden(NodoArbol nodo) {
    System.out.print(nodo.dato + " ");
    preorden(nodo.izquierdo); // NullPointerException cuando hijo es null
    preorden(nodo.derecho);
}

// ✅ BIEN: siempre verificar si el nodo es null
public static void preorden(NodoArbol nodo) {
    if (nodo == null) return;  // CASO BASE OBLIGATORIO
    System.out.print(nodo.dato + " ");
    preorden(nodo.izquierdo);
    preorden(nodo.derecho);
}

// ❌ MAL: apilar izquierdo antes → recorre primero el derecho
pila.push(actual.izquierdo);  // Sale segundo (LIFO)
pila.push(actual.derecho);    // Sale primero

// ✅ BIEN: apilar derecho antes para que izquierdo salga primero
pila.push(actual.derecho);    // Sale segundo
pila.push(actual.izquierdo);  // Sale primero (LIFO)

// ❌ OBSOLETO: Stack hereda de Vector (sincronizado innecesariamente)
Stack<NodoArbol> pila = new Stack<>();

// ✅ RECOMENDADO: ArrayDeque es más rápido y moderno
Deque<NodoArbol> pila = new ArrayDeque<>();

// ❌ MAL: encolar sin verificar → NullPointerException al extraer
cola.add(actual.izquierdo); // Puede ser null
cola.add(actual.derecho);

// ✅ BIEN: verificar antes de encolar
if (actual.izquierdo != null) cola.add(actual.izquierdo);
if (actual.derecho != null)   cola.add(actual.derecho);