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:
- Mediante listas dinámicas de hijos en cada nodo (
List<NodoNario<T>>). - 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.
- 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
primerHijoapunta al primer elemento de la lista de hijos. - El enlace
siguienteHermanoconecta en cadena horizontal a cada hermano con el posterior. - Invariante crítico: la raíz del árbol general no tiene hermanos; su puntero
siguienteHermanodebe ser estrictamentenull.