7 - Árboles generalizados de múltiples niveles

Las estructuras n-arias son ideales para representar dominios donde cada entidad tiene una cantidad arbitraria de elementos subordinados. A continuación revisamos los casos de uso más habituales y cómo las estructuras implementadas en Python nos ayudan a modelarlos.

7.1 Árboles para sistemas de archivos

Los sistemas de archivos jerárquicos, como los descritos en File System, utilizan árboles generales para organizar carpetas y archivos. Cada carpeta puede contener un número variable de entradas, lo que hace que la representación LCRS o la lista de hijos sean opciones naturales.

En Python, podemos mapear cada carpeta a un Nodo y utilizar funciones como obtener_hijos (del tema 5) para listar entradas, ordenarlas alfabéticamente o filtrar según permisos.

7.2 Árboles para documentos (HTML, XML, JSON)

El DOM describe una página HTML como un árbol general donde cada nodo representa una etiqueta y sus hijos son elementos anidados. La misma idea se aplica a formatos como XML y JSON.

En parsers o utilidades escritas en Python, podemos representar el DOM con estructuras similares a las utilizadas en este tutorial y ejecutar recorridos preorden para generar HTML, o postorden para limpiar la estructura cuando ya no sea necesaria.

7.3 Árboles como estructuras de IA

Los árboles de decisión, de comportamiento o de juego son pilares de la inteligencia artificial. Cada nodo representa una decisión o estado, y los hijos indican las opciones posibles. Los recorridos preorden o por niveles ayudan a evaluar heurísticas, mientras que la inserción y eliminación de subárboles permiten ajustar estrategias en tiempo de ejecución.

Para IA basada en Python, la representación LCRS facilita ejecutar algoritmos como minimax y podas alfa-beta sin cambiar la estructura de datos base.

7.4 Árboles en videojuegos (misiones, decisiones, diálogos)

Los videojuegos modernos contienen estructuras narrativas complejas: misiones con submisiones, árboles de diálogos y rutas de progreso. Cada nodo del árbol modela un evento, y cada hijo, una consecuencia o una misión dependiente.

En Python podemos construir editores de contenido que serialicen este árbol a JSON, lo envíen al motor principal y lo recorran en tiempo real para habilitar o bloquear misiones. La función mover_subarbol (tema 6) se vuelve esencial para reordenar partes de la historia sin recrear todo el árbol.

7.5 Representación de árboles extensos

Al manejar árboles con millones de nodos, debemos controlar cuidadosamente el uso de memoria y los recorridos. Algunas recomendaciones:

• Evita recursión profunda y adopta pilas/colas iterativas (como en los temas 4 y 6) para reducir el uso de la pila.
• Guarda metadatos ligeros (por ejemplo, el grado o la profundidad) en estructuras auxiliares si los necesitas frecuentemente.
• Serializa el árbol a formatos streaming (JSON, binario personalizado) para cargar solo las ramas necesarias en memoria.
• Usa generadores y recorridos parciales cuando solo necesitas un subconjunto del árbol.

Aplicando estas estrategias, los árboles generales escalan adecuadamente en proyectos reales que exigen estructuras multiescalares, como navegadores, motores de juego y sistemas expertos.

7.6 Explorador de disco usando árboles generales

Como aplicación completa, implementaremos un programa en Python que recorre un directorio del disco usando os.walk. El ejemplo parte de la carpeta C:\\prueba, construye un árbol general con las carpetas y archivos encontrados y luego lo imprime.

import os


class Nodo:
  def __init__(self, nombre, es_directorio):
    self.nombre = nombre
    self.es_directorio = es_directorio
    self.primer_hijo = None
    self.siguiente_hermano = None
    self.padre = None


class ArbolGeneral:
  def __init__(self):
    self.raiz = None

  def agregar_hijo(self, padre, nombre, es_directorio):
    nuevo = Nodo(nombre, es_directorio)
    nuevo.padre = padre
    nuevo.siguiente_hermano = padre.primer_hijo
    padre.primer_hijo = nuevo
    return nuevo

  def imprimir(self, nodo=None, sangria=0):
    nodo = nodo or self.raiz
    if nodo is None:
      return
    sufijo = "/" if nodo.es_directorio else ""
    print("  " * sangria + f"{nodo.nombre}{sufijo}")
    hijo = nodo.primer_hijo
    while hijo:
      self.imprimir(hijo, sangria + 1)
      hijo = hijo.siguiente_hermano


def construir_desde_directorio(arbol, ruta_raiz):
  arbol.raiz = Nodo(ruta_raiz, True)
  mapa = {ruta_raiz: arbol.raiz}

  for ruta_actual, carpetas, archivos in os.walk(ruta_raiz):
    padre = mapa.get(ruta_actual)
    if padre is None:
      continue
    for carpeta in carpetas:
      ruta = os.path.join(ruta_actual, carpeta)
      nodo = arbol.agregar_hijo(padre, carpeta, True)
      mapa[ruta] = nodo
    for archivo in archivos:
      arbol.agregar_hijo(padre, archivo, False)


if __name__ == "__main__":
  ruta = r"C:\prueba"
  arbol = ArbolGeneral()
  construir_desde_directorio(arbol, ruta)
  print("Contenido del directorio:")
  arbol.imprimir()

Este explorador recorre recursivamente todas las carpetas, guarda los nombres en el árbol general y luego lo imprime con sangrías, replicando la estructura real del disco.