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 C 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 C, podemos mapear cada carpeta a un GeneralNode y utilizar funciones como obtenerHijos (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 motores embebidos o parsers escritos en C, podemos representar el DOM con estructuras similares a las utilizadas en este tutorial y ejecutar recorridos preorden para generar HTML, o postorden para liberar la memoria asociada a cada nodo.

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 C, 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 C 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 moverSubarbol (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:

• Utiliza malloc y free en bloques o arenas para reducir la fragmentación.
• Desactiva la recursión profunda y adopta pilas/colas iterativas (como en los temas 4 y 6) para evitar desbordes.
• 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.

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 C que recorre un directorio del disco en Windows utilizando las API de FindFirstFile/FindNextFile. El ejemplo parte de la carpeta C:\\prueba, construye un árbol general con las carpetas y archivos encontrados y luego lo imprime.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>

typedef struct GeneralNode {
  char *nombre;
  int esDirectorio;
  struct GeneralNode *primerHijo;
  struct GeneralNode *siguienteHermano;
  struct GeneralNode *padre;
} GeneralNode;

GeneralNode *crearNodo(const char *nombre, int esDirectorio) {
  GeneralNode *nodo = malloc(sizeof(GeneralNode));
  if (!nodo) return NULL;
  nodo->nombre = strdup(nombre);
  nodo->esDirectorio = esDirectorio;
  nodo->primerHijo = NULL;
  nodo->siguienteHermano = NULL;
  nodo->padre = NULL;
  return nodo;
}

void insertarHijo(GeneralNode *padre, GeneralNode *hijo) {
  if (!padre || !hijo) return;
  hijo->padre = padre;
  hijo->siguienteHermano = padre->primerHijo;
  padre->primerHijo = hijo;
}

void liberarArbol(GeneralNode *nodo) {
  if (!nodo) return;
  GeneralNode *hijo = nodo->primerHijo;
  while (hijo) {
    GeneralNode *sig = hijo->siguienteHermano;
    liberarArbol(hijo);
    hijo = sig;
  }
  free(nodo->nombre);
  free(nodo);
}

void imprimirArbol(const GeneralNode *nodo, unsigned int sangria) {
  if (!nodo) return;
  for (unsigned int i = 0; i < sangria; ++i) printf("  ");
  printf("%s%s\n", nodo->nombre, nodo->esDirectorio ? "/" : "");
  for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
    imprimirArbol(hijo, sangria + 1);
  }
}

int construirDesdeDirectorio(GeneralNode *padre, const char *ruta) {
  size_t lenBusqueda = strlen(ruta) + 3;
  char *patron = malloc(lenBusqueda);
  if (!patron) return 0;
  snprintf(patron, lenBusqueda, "%s\\*", ruta);

  WIN32_FIND_DATAA data;
  HANDLE hFind = FindFirstFileA(patron, &data);
  free(patron);
  if (hFind == INVALID_HANDLE_VALUE) {
    fprintf(stderr, "No se pudo abrir %s\n", ruta);
    return 0;
  }

  do {
    if (strcmp(data.cFileName, ".") == 0 || strcmp(data.cFileName, "..") == 0) {
      continue;
    }
    size_t lenRuta = strlen(ruta) + strlen(data.cFileName) + 2;
    char *rutaCompleta = malloc(lenRuta);
    if (!rutaCompleta) {
      FindClose(hFind);
      return 0;
    }
    snprintf(rutaCompleta, lenRuta, "%s\\%s", ruta, data.cFileName);
    int esDir = (data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) != 0;
    GeneralNode *nodo = crearNodo(data.cFileName, esDir);
    if (!nodo) {
      free(rutaCompleta);
      FindClose(hFind);
      return 0;
    }
    insertarHijo(padre, nodo);
    if (esDir) {
      construirDesdeDirectorio(nodo, rutaCompleta);
    }
    free(rutaCompleta);
  } while (FindNextFileA(hFind, &data));

  FindClose(hFind);
  return 1;
}

int main(void) {
  const char *rutaRaiz = "C:\\prueba";
  GeneralNode *raiz = crearNodo(rutaRaiz, 1);
  if (!raiz) {
    fprintf(stderr, "Sin memoria\n");
    return EXIT_FAILURE;
  }
  if (!construirDesdeDirectorio(raiz, rutaRaiz)) {
    liberarArbol(raiz);
    return EXIT_FAILURE;
  }
  puts("Contenido del directorio:");
  imprimirArbol(raiz, 0);
  liberarArbol(raiz);
  return EXIT_SUCCESS;
}

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.