3 - Modelado de nodos en C
Para programar un árbol binario necesitamos una representación de los nodos que sea consistente, fácil de inicializar y sencilla de liberar. En este tema diseñamos el struct base y construimos utilidades que conectan hijos, actualizan niveles y mantienen el estado del árbol sin fugas de memoria.
3.1 Estructura del nodo
El nodo almacena el dato y los punteros a cada hijo junto con el nivel actual. Con esa información podemos reconstruir la jerarquía sin depender de punteros adicionales y mantener la estructura ligera.
typedef struct TreeNode {
int valor;
struct TreeNode *izquierdo;
struct TreeNode *derecho;
unsigned char nivel;
} TreeNode;Mantener la estructura compacta y sin puntero al padre simplifica la reserva de memoria y reduce el tamaño total del árbol.
3.2 Contenedor del árbol e inicialización
Centralizamos la raíz y la cantidad de nodos en una estructura contenedora. Esta práctica simplifica la detección de árboles vacíos y el seguimiento del tamaño.
typedef struct {
TreeNode *raiz;
unsigned int cantidad;
} ArbolBinario;
void inicializarArbol(ArbolBinario *arbol) {
arbol->raiz = NULL;
arbol->cantidad = 0;
}Siempre que el puntero a la raíz valga NULL consideramos al árbol vacío; cualquier inserción crea la nueva raíz.
3.3 Funciones de creación
Las funciones encargadas de reservar memoria deben devolver NULL cuando malloc falla y dejar los enlaces en estado consistente. Las siguientes utilidades cubren tanto la creación genérica como la inserción de la raíz.
#include <stdlib.h>
TreeNode *crearNodo(int valor) {
TreeNode *nodo = malloc(sizeof(TreeNode));
if (!nodo) {
return NULL;
}
nodo->valor = valor;
nodo->izquierdo = NULL;
nodo->derecho = NULL;
nodo->nivel = 0;
return nodo;
}
TreeNode *crearRaiz(ArbolBinario *arbol, int valor) {
if (arbol->raiz) {
return arbol->raiz;
}
TreeNode *nodo = crearNodo(valor);
if (!nodo) {
return NULL;
}
arbol->raiz = nodo;
arbol->cantidad = 1;
return nodo;
}Separar la creación de la raíz evita errores cuando el árbol ya posee nodos.
3.4 Inserción genérica no recursiva
La inserción sin recursión se apoya en comparaciones: avanzamos por la rama izquierda si el valor es menor al nodo actual, o por la derecha en caso contrario. Una vez que encontramos un puntero nulo, enlazamos el nuevo nodo y actualizamos su nivel.
TreeNode *insertar(ArbolBinario *arbol, int valor) {
if (!arbol->raiz) {
return crearRaiz(arbol, valor);
}
TreeNode *actual = arbol->raiz;
TreeNode *anterior = NULL;
while (actual) {
anterior = actual;
if (valor < actual->valor) {
actual = actual->izquierdo;
} else {
actual = actual->derecho;
}
}
TreeNode *nuevo = crearNodo(valor);
if (!nuevo) {
return NULL;
}
nuevo->nivel = (unsigned char)(anterior->nivel + 1);
if (valor < anterior->valor) {
anterior->izquierdo = nuevo;
} else {
anterior->derecho = nuevo;
}
arbol->cantidad++;
return nuevo;
}Asignar duplicados a la rama derecha mantiene la rutina simple y evita reacomodar nodos; más adelante podremos ajustar esta regla según las necesidades del algoritmo.
3.5 Ejemplo de inserción manual
Para validar el modelado conviene crear un pequeño escenario donde agregamos valores y verificamos el resultado con un recorrido en preorden. Observa cómo los nodos se distribuyen hacia la izquierda cuando el valor insertado es menor.
void poblarArbol(ArbolBinario *arbol) {
insertar(arbol, 10);
insertar(arbol, 5);
insertar(arbol, 20);
insertar(arbol, 3);
insertar(arbol, 7);
}
void imprimirPreorden(TreeNode *nodo) {
if (!nodo) return;
printf("%d (nivel %u)\n", nodo->valor, nodo->nivel);
imprimirPreorden(nodo->izquierdo);
imprimirPreorden(nodo->derecho);
}El recorrido confirma que los niveles y punteros quedaron correctamente sincronizados.
3.6 Liberación segura de memoria
Una vez que terminamos de utilizar el árbol debemos liberar cada nodo. El siguiente helper lo hace en postorden para garantizar que no queden referencias pendientes.
void liberarSubarbol(TreeNode *nodo) {
if (!nodo) return;
liberarSubarbol(nodo->izquierdo);
liberarSubarbol(nodo->derecho);
free(nodo);
}
void limpiarArbol(ArbolBinario *arbol) {
liberarSubarbol(arbol->raiz);
arbol->raiz = NULL;
arbol->cantidad = 0;
}Antes de salir del programa o al reconstruir la estructura, llamamos a limpiarArbol para evitar fugas de memoria.
Contar con estas piezas nos permite abordar el siguiente tema: construir árboles binarios completos a partir de entradas reales sin perder consistencia en los nodos.
3.7 Código completo listo para CLion
El siguiente archivo compila directamente en CLion o en cualquier entorno compatible con C17. Reúne las funciones vistas en el tema, crea un árbol de ejemplo y muestra su recorrido en preorden.
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int valor;
struct TreeNode *izquierdo;
struct TreeNode *derecho;
unsigned char nivel;
} TreeNode;
typedef struct {
TreeNode *raiz;
unsigned int cantidad;
} ArbolBinario;
void inicializarArbol(ArbolBinario *arbol) {
arbol->raiz = NULL;
arbol->cantidad = 0;
}
TreeNode *crearNodo(int valor) {
TreeNode *nodo = malloc(sizeof(TreeNode));
if (!nodo) return NULL;
nodo->valor = valor;
nodo->izquierdo = NULL;
nodo->derecho = NULL;
nodo->nivel = 0;
return nodo;
}
TreeNode *crearRaiz(ArbolBinario *arbol, int valor) {
if (arbol->raiz) {
return arbol->raiz;
}
TreeNode *nodo = crearNodo(valor);
if (!nodo) return NULL;
arbol->raiz = nodo;
arbol->cantidad = 1;
return nodo;
}
TreeNode *insertar(ArbolBinario *arbol, int valor) {
if (!arbol->raiz) {
return crearRaiz(arbol, valor);
}
TreeNode *actual = arbol->raiz;
TreeNode *anterior = NULL;
while (actual) {
anterior = actual;
if (valor < actual->valor) {
actual = actual->izquierdo;
} else {
actual = actual->derecho;
}
}
TreeNode *nuevo = crearNodo(valor);
if (!nuevo) return NULL;
nuevo->nivel = (unsigned char)(anterior->nivel + 1);
if (valor < anterior->valor) {
anterior->izquierdo = nuevo;
} else {
anterior->derecho = nuevo;
}
arbol->cantidad++;
return nuevo;
}
void imprimirPreorden(TreeNode *nodo) {
if (!nodo) return;
printf("%d (nivel %u)\n", nodo->valor, nodo->nivel);
imprimirPreorden(nodo->izquierdo);
imprimirPreorden(nodo->derecho);
}
void liberarSubarbol(TreeNode *nodo) {
if (!nodo) return;
liberarSubarbol(nodo->izquierdo);
liberarSubarbol(nodo->derecho);
free(nodo);
}
void limpiarArbol(ArbolBinario *arbol) {
liberarSubarbol(arbol->raiz);
arbol->raiz = NULL;
arbol->cantidad = 0;
}
int main(void) {
ArbolBinario arbol;
inicializarArbol(&arbol);
insertar(&arbol, 10);
insertar(&arbol, 5);
insertar(&arbol, 20);
insertar(&arbol, 3);
insertar(&arbol, 7);
puts("Recorrido preorden:");
imprimirPreorden(arbol.raiz);
limpiarArbol(&arbol);
return 0;
}