Contexto

A diferencia de los árboles binarios restringidos a dos ramas por nodo, los árboles N-arios (o generales) permiten modelar de forma natural cualquier estructura jerárquica del mundo real: sistemas de archivos, organigramas corporativos, menús de navegación y árboles de sintaxis abstracta (AST).

Un desafío clásico de ingeniería es cómo almacenar y procesar estas jerarquías:

  1. Mediante listas dinámicas de hijos en cada nodo (List<NodoNario<T>>).
  2. Mediante la transformación isomórfica a Primer Hijo / Siguiente Hermano (Left-Child / Right-Sibling), que permite representar cualquier árbol N-ario como un árbol binario estándar sin desperdiciar memoria.
  3. Mediante representación con vectores contiguos e índices numéricos para optimizar la localidad de caché.

Consigna

Vas a implementar un árbol N-ario genérico, su visualización indentada y su transformación a la estructura de primer hijo y siguiente hermano.

1. Modelo de Dominio N-ario

public class NodoNario<T> {
    private final T valor;
    private final List<NodoNario<T>> hijos = new ArrayList<>();
    private NodoNario<T> padre;

    public NodoNario(T valor) {
        if (valor == null) throw new IllegalArgumentException("El valor no puede ser null");
        this.valor = valor;
    }

    public void agregarHijo(NodoNario<T> hijo) {
        if (hijo == null) throw new IllegalArgumentException("Hijo no puede ser null");
        if (hijo.padre != null) throw new IllegalStateException("El nodo ya posee un padre asignado");
        hijo.padre = this;
        this.hijos.add(hijo);
    }
    // getters defensivos...
}

2. Algoritmos de Recorrido y Métricas

  • Recorrido Preorden: procesar el nodo actual y luego invocar recursivamente el preorden para cada uno de sus hijos en orden de aparición.
  • Altura: $0$ si el nodo es hoja; caso contrario $1 + \max(\text{altura de sus hijos})$.
  • Hojas: nodos cuya lista de hijos tiene tamaño 0.

3. Transformación Primer Hijo / Siguiente Hermano

En la estructura binaria equivalente:

  • El enlace primerHijo apunta al primer elemento de la lista de hijos.
  • El enlace siguienteHermano conecta en cadena horizontal a cada hermano con el posterior.
  • Invariante crítico: la raíz del árbol general no tiene hermanos; su puntero siguienteHermano debe ser estrictamente null.