5 - Operaciones fundamentales sobre árboles generales

Este tema recopila las funciones indispensables para trabajar con un árbol general en C. Utilizaremos la representación hijo-izquierdo/hermano-derecho para mantener cada operación concisa y consistente con los temas anteriores.

typedef struct GeneralNode {
  int valor;
  struct GeneralNode *primerHijo;
  struct GeneralNode *siguienteHermano;
} GeneralNode;

5.1 Contar nodos del árbol

Contar los nodos permite validar inserciones, dimensionar estructuras auxiliares y estimar el costo de futuros algoritmos. El conteo se implementa con un recorrido recursivo que suma los nodos de cada subárbol.

unsigned int contarNodos(const GeneralNode *nodo) {
  if (!nodo) {
    return 0;
  }
  unsigned int total = 1;
  for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
    total += contarNodos(hijo);
  }
  return total;
}

5.2 Contar hojas

Las hojas representan estados finales o elementos terminales. Identificarlas permite evaluar la profundidad del árbol y detectar condiciones de borde.

unsigned int contarHojas(const GeneralNode *nodo) {
  if (!nodo) {
    return 0;
  }
  if (!nodo->primerHijo) {
    return 1;
  }
  unsigned int hojas = 0;
  for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
    hojas += contarHojas(hijo);
  }
  return hojas;
}

5.3 Contar hijos de un nodo

Determinar el número de hijos directos es útil para validar restricciones de grado y adaptar representaciones alternas.

unsigned int contarHijos(const GeneralNode *nodo) {
  unsigned int grado = 0;
  for (const GeneralNode *hijo = nodo ? nodo->primerHijo : NULL; hijo; hijo = hijo->siguienteHermano) {
    grado++;
  }
  return grado;
}

5.4 Altura del árbol

La altura refleja el nivel máximo alcanzado por cualquier rama. Es clave para analizar la complejidad de los recorridos y el balance del árbol.

unsigned int alturaGeneral(const GeneralNode *nodo) {
  if (!nodo) {
    return 0;
  }
  unsigned int maxAltura = 0;
  for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
    unsigned int alturaHijo = alturaGeneral(hijo);
    if (alturaHijo > maxAltura) {
      maxAltura = alturaHijo;
    }
  }
  return 1 + maxAltura;
}

5.5 Búsqueda de un valor

Buscar un valor permite implementar consultas genéricas y validar si un dato ya existe antes de insertarlo. El siguiente ejemplo realiza una búsqueda en profundidad regresando el primer nodo coincidente.

const GeneralNode *buscarValor(const GeneralNode *nodo, int objetivo) {
  if (!nodo) {
    return NULL;
  }
  if (nodo->valor == objetivo) {
    return nodo;
  }
  for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
    const GeneralNode *resultado = buscarValor(hijo, objetivo);
    if (resultado) {
      return resultado;
    }
  }
  return NULL;
}

5.6 Cálculo de profundidades

La profundidad de cada nodo describe cuántas aristas lo separan de la raíz. Para almacenarla podemos propagar un contador durante el recorrido y ejecutar un callback sobre cada nodo visitado.

typedef void (*VisitFn)(const GeneralNode *nodo, unsigned int profundidad, void *ctx);

void calcularProfundidades(const GeneralNode *nodo, unsigned int profundidad, VisitFn fn, void *ctx) {
  if (!nodo || !fn) {
    return;
  }
  fn(nodo, profundidad, ctx);
  for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
    calcularProfundidades(hijo, profundidad + 1, fn, ctx);
  }
}

Esta estrategia evita guardar la profundidad dentro del nodo y permite reutilizar el cálculo en visualizaciones o algoritmos específicos.

5.7 Obtener la lista de hijos de un nodo

En muchas aplicaciones necesitamos un arreglo temporal con los hijos directos para ordenarlos, filtrarlos o mostrarlos en la interfaz. El siguiente ejemplo extrae los punteros en un arreglo provisto por el llamador y devuelve el total de elementos almacenados.

unsigned int obtenerHijos(const GeneralNode *nodo, const GeneralNode **buffer, unsigned int maxBuffer) {
  if (!nodo || !buffer || !maxBuffer) {
    return 0;
  }
  unsigned int count = 0;
  for (const GeneralNode *hijo = nodo->primerHijo; hijo && count < maxBuffer; hijo = hijo->siguienteHermano) {
    buffer[count++] = hijo;
  }
  return count;
}

Cuando el número de hijos supera el tamaño del buffer, podemos llamar nuevamente con un arreglo más grande o procesar los datos por bloques.

5.8 Comparar dos árboles

Comparar árboles generalizados es clave para detectar cambios, sincronizar versiones o verificar resultados de algoritmos. Definimos equivalencia cuando ambos nodos comparten el mismo valor y sus listas de hijos son comparables posicionalmente.

int sonIguales(const GeneralNode *a, const GeneralNode *b) {
  if (!a && !b) {
    return 1;
  }
  if (!a || !b || a->valor != b->valor) {
    return 0;
  }
  const GeneralNode *hijoA = a->primerHijo;
  const GeneralNode *hijoB = b->primerHijo;
  while (hijoA && hijoB) {
    if (!sonIguales(hijoA, hijoB)) {
      return 0;
    }
    hijoA = hijoA->siguienteHermano;
    hijoB = hijoB->siguienteHermano;
  }
  return hijoA == NULL && hijoB == NULL;
}

Para comparar sin importar el orden de los hijos podríamos recopilar los valores en arreglos temporales y ordenarlos antes de evaluar cada nivel. La decisión depende de los requisitos del proyecto.

Retornar