2 - Componentes y propiedades de un árbol general
Profundizamos en cada elemento que describe a un árbol general: cómo se define el nodo, de qué manera se enlazan las aristas, cuál es el impacto de los subárboles y cómo medir propiedades como grado, altura y estado vacío. Mantendremos la convención de nombres introducida en el primer tema para que cualquier fragmento sea fácil de reusar en C.
2.1 Nodos
El nodo general debe tolerar cualquier cantidad de hijos. Una estrategia habitual consiste en almacenar punteros al primer hijo y al siguiente hermano, además de un enlace opcional al padre para simplificar recorridos ascendentes. Conservamos el campo valor y dejamos todos los punteros en NULL al crear la estructura.
#include <stdlib.h>
typedef struct GeneralNode {
int valor;
struct GeneralNode *primerHijo;
struct GeneralNode *siguienteHermano;
struct GeneralNode *padre;
} GeneralNode;
GeneralNode *crearNodoGeneral(int valor) {
GeneralNode *nodo = malloc(sizeof(GeneralNode));
if (!nodo) {
return NULL;
}
nodo->valor = valor;
nodo->primerHijo = NULL;
nodo->siguienteHermano = NULL;
nodo->padre = NULL;
return nodo;
}Este diseño replica la semántica de los punteros izquierdo y derecho del tutorial de árboles binarios, lo que facilita adaptar código existente.
2.2 Aristas
Las aristas definen las conexiones entre padres e hijos. En un árbol general, cada nueva arista se agrega sumando el hijo en la lista enlazada de descendientes y actualizando los punteros de hermano. Podemos reutilizar una función auxiliar que inserta al hijo al principio de la lista para mantener el costo constante.
void enlazarComoPrimerHijo(GeneralNode *padre, GeneralNode *nuevoHijo) {
if (!padre || !nuevoHijo) {
return;
}
nuevoHijo->padre = padre;
nuevoHijo->siguienteHermano = padre->primerHijo;
padre->primerHijo = nuevoHijo;
}
void enlazarComoHermano(GeneralNode *referencia, GeneralNode *nuevoHermano) {
if (!referencia || !nuevoHermano) {
return;
}
nuevoHermano->padre = referencia->padre;
nuevoHermano->siguienteHermano = referencia->siguienteHermano;
referencia->siguienteHermano = nuevoHermano;
}Llevar el control de estas aristas nos permite recorrer hijos linealmente, reordenar ramas y detectar inconsistencias antes de ejecutar algoritmos más costosos.
2.3 Raíz, hijos y hermanos
La raíz es el nodo superior y punto de entrada del árbol. Desde ella obtenemos cualquier hijo siguiendo el puntero primerHijo. Cada hijo a su vez posee un enlace a su hermano inmediato mediante siguienteHermano. Estas tres piezas bastan para reconstruir todo el arbolado y permiten operar tanto vertical como horizontalmente.
En los recorridos es común alternar una iteración mientras existan hermanos y, dentro de cada hermano, entrar de forma recursiva a sus respectivos hijos. Este patrón asegura que no dejamos ramas aisladas.
2.4 Subárboles
Un subárbol está formado por un nodo y todos sus descendientes. Trabajar con subárboles facilita tareas como clonar secciones, mover ramas completas o liberar memoria de forma localizada. La función siguiente recorre un subárbol y acumula sus nodos, devolviendo una cantidad útil para estadísticas o depuración.
unsigned int contarSubarbol(const GeneralNode *nodo) {
if (!nodo) {
return 0;
}
unsigned int total = 1;
for (GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
total += contarSubarbol(hijo);
}
return total;
}Este recorrido sigue la misma firma que utilizaremos para borrar subárboles, serializarlos o calcular alturas locales.
2.5 Número de hijos (grado del nodo)
El grado describe cuántos hijos directos posee un nodo. En árboles generales un grado alto indica fan-out elevado y, por ende, mayor costo de memoria para esa rama. Se obtiene contando la cantidad de nodos en la lista de hijos.
unsigned int gradoNodo(const GeneralNode *nodo) {
unsigned int grado = 0;
for (const GeneralNode *hijo = nodo ? nodo->primerHijo : NULL; hijo; hijo = hijo->siguienteHermano) {
grado++;
}
return grado;
}Guardar el grado nos ayuda a dimensionar arreglos auxiliares, validar que un nodo respete un límite de hijos o ajustar las heurísticas de balance.
2.6 Altura y profundidad
La profundidad de un nodo es la cantidad de aristas que lo separan de la raíz; la altura del árbol es la profundidad máxima encontrada. Estos valores influyen en la complejidad de las operaciones, especialmente cuando se recorre todo el árbol.
unsigned int profundidad(const GeneralNode *nodo) {
unsigned int nivel = 0;
while (nodo && nodo->padre) {
nodo = nodo->padre;
nivel++;
}
return nivel;
}
unsigned int altura(const GeneralNode *nodo) {
if (!nodo) {
return 0;
}
unsigned int maxHijos = 0;
for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
unsigned int alturaHijo = altura(hijo);
if (alturaHijo > maxHijos) {
maxHijos = alturaHijo;
}
}
return 1 + maxHijos;
}Calcular estas medidas periódicamente nos permite detectar ramas que crecen sin control y decidir si conviene normalizarlas.
2.7 Árbol vacío y árbol no vacío
Diferenciar entre un árbol vacío y uno con nodos activos evita accesos indebidos. Centralizamos esta información en un contenedor que registra la raíz y el total de nodos administrados.
typedef struct {
GeneralNode *raiz;
unsigned int cantidad;
} GeneralTree;
void inicializarGeneralTree(GeneralTree *arbol) {
arbol->raiz = NULL;
arbol->cantidad = 0;
}
int estaVacio(const GeneralTree *arbol) {
return !arbol || !arbol->raiz;
}Al encapsular la raíz podemos crear funciones de inserción que incrementan cantidad y detectar si las operaciones dejan el árbol en estado inconsistente.
2.8 Representación gráfica
Visualizar el árbol ayuda a depurar y documentar. Sin depender de librerías externas podemos imprimir una representación textual con indentaciones, simulando un diagrama jerárquico. Cada nivel se desplaza algunos espacios para reflejar la profundidad.
#include <stdio.h>
void imprimirArbol(const GeneralNode *nodo, unsigned int sangria) {
if (!nodo) {
return;
}
for (unsigned int i = 0; i < sangria; ++i) {
printf(" ");
}
printf("-%d\n", nodo->valor);
for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
imprimirArbol(hijo, sangria + 1);
}
}Este mismo patrón puede adaptarse para generar diagramas ASCII o exportar datos en formatos aptos para herramientas de visualización.
Para liberar toda la memoria reservada utilizamos un recorrido en postorden que visita primero a los hijos, luego a los hermanos y por último al nodo actual:
#include <stdlib.h>
void destruirArbol(GeneralNode *nodo) {
if (!nodo) {
return;
}
destruirArbol(nodo->primerHijo);
destruirArbol(nodo->siguienteHermano);
free(nodo);
}Para cerrar este tema incluimos un archivo completo listo para ejecutar en CLion, con la mayoría de las funciones anteriores y un ejemplo de uso:
#include <stdio.h>
#include <stdlib.h>
typedef struct GeneralNode {
int valor;
struct GeneralNode *primerHijo;
struct GeneralNode *siguienteHermano;
struct GeneralNode *padre;
} GeneralNode;
typedef struct {
GeneralNode *raiz;
unsigned int cantidad;
} GeneralTree;
GeneralNode *crearNodoGeneral(int valor) {
GeneralNode *nodo = malloc(sizeof(GeneralNode));
if (!nodo) {
return NULL;
}
nodo->valor = valor;
nodo->primerHijo = NULL;
nodo->siguienteHermano = NULL;
nodo->padre = NULL;
return nodo;
}
void inicializarGeneralTree(GeneralTree *arbol) {
arbol->raiz = NULL;
arbol->cantidad = 0;
}
int estaVacio(const GeneralTree *arbol) {
return !arbol || !arbol->raiz;
}
void enlazarComoPrimerHijo(GeneralNode *padre, GeneralNode *nuevoHijo) {
if (!padre || !nuevoHijo) {
return;
}
nuevoHijo->padre = padre;
nuevoHijo->siguienteHermano = padre->primerHijo;
padre->primerHijo = nuevoHijo;
}
void enlazarComoHermano(GeneralNode *referencia, GeneralNode *nuevoHermano) {
if (!referencia || !nuevoHermano) {
return;
}
nuevoHermano->padre = referencia->padre;
nuevoHermano->siguienteHermano = referencia->siguienteHermano;
referencia->siguienteHermano = nuevoHermano;
}
unsigned int contarSubarbol(const GeneralNode *nodo) {
if (!nodo) {
return 0;
}
unsigned int total = 1;
for (GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
total += contarSubarbol(hijo);
}
return total;
}
unsigned int gradoNodo(const GeneralNode *nodo) {
unsigned int grado = 0;
for (const GeneralNode *hijo = nodo ? nodo->primerHijo : NULL; hijo; hijo = hijo->siguienteHermano) {
grado++;
}
return grado;
}
unsigned int profundidad(const GeneralNode *nodo) {
unsigned int nivel = 0;
while (nodo && nodo->padre) {
nodo = nodo->padre;
nivel++;
}
return nivel;
}
unsigned int altura(const GeneralNode *nodo) {
if (!nodo) {
return 0;
}
unsigned int maxHijos = 0;
for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
unsigned int alturaHijo = altura(hijo);
if (alturaHijo > maxHijos) {
maxHijos = alturaHijo;
}
}
return 1 + maxHijos;
}
void imprimirArbol(const GeneralNode *nodo, unsigned int sangria) {
if (!nodo) {
return;
}
for (unsigned int i = 0; i < sangria; ++i) {
printf(" ");
}
printf("-%d\n", nodo->valor);
for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
imprimirArbol(hijo, sangria + 1);
}
}
void destruirArbol(GeneralNode *nodo) {
if (!nodo) {
return;
}
destruirArbol(nodo->primerHijo);
destruirArbol(nodo->siguienteHermano);
free(nodo);
}
int main(void) {
GeneralTree arbol;
inicializarGeneralTree(&arbol);
arbol.raiz = crearNodoGeneral(1);
if (!arbol.raiz) {
fprintf(stderr, "Sin memoria\n");
return EXIT_FAILURE;
}
arbol.cantidad = 1;
GeneralNode *nodoA = crearNodoGeneral(2);
GeneralNode *nodoB = crearNodoGeneral(3);
GeneralNode *nodoC = crearNodoGeneral(4);
enlazarComoPrimerHijo(arbol.raiz, nodoB);
enlazarComoPrimerHijo(arbol.raiz, nodoA);
enlazarComoHermano(nodoA, nodoC);
arbol.cantidad += 3;
GeneralNode *nodoD = crearNodoGeneral(5);
GeneralNode *nodoE = crearNodoGeneral(6);
enlazarComoPrimerHijo(nodoB, nodoD);
enlazarComoHermano(nodoD, nodoE);
arbol.cantidad += 2;
puts("Representacion del arbol:");
imprimirArbol(arbol.raiz, 0);
printf("Cantidad total de nodos: %u\n", contarSubarbol(arbol.raiz));
printf("Grado de la raiz: %u\n", gradoNodo(arbol.raiz));
printf("Altura del arbol: %u\n", altura(arbol.raiz));
printf("Profundidad de nodoE: %u\n", profundidad(nodoE));
destruirArbol(arbol.raiz);
return EXIT_SUCCESS;
}