4 - Construcción de árboles binarios
Con el modelo de nodos definido en el tema anterior podemos concentrarnos en construir árboles binarios de distintas formas. Este capítulo cubre las inserciones iterativas, la carga desde arreglos, la generación balanceada y alguns rutas para recibir datos del usuario sin comprometer la integridad del árbol.
4.1 Planificar la construcción
Antes de escribir código conviene definir si los datos llegan ordenados, desordenados o en un flujo interactivo. De esto depende si necesitamos herramientas extra para balancear el árbol o si basta con aplicar la inserción secuencial.
- Listas desordenadas: se insertan una a una usando comparaciones. El árbol puede quedar sesgado si la entrada ya está casi ordenada.
- Arreglos ordenados: permiten construir un árbol balanceado tomando siempre el elemento central como raíz del subárbol.
- Entradas interactivas: requieren validar cada valor antes de insertarlo y ofrecer opciones para finalizar la carga.
4.2 Componentes base reutilizables
Usaremos el mismo struct de nodos del tema 3 junto con las utilidades de inicialización y limpieza para comenzar desde un estado conocido.
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;
}
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;
}Estas utilidades se reutilizan en cada variante de construcción, por lo que conviene mantenerlas en un archivo independiente del proyecto.
4.3 Inserción iterativa reutilizable
Partimos de la misma estructura del tema 3: el recorrido es iterativo, compara valores y enlaza el nuevo nodo al encontrar un puntero nulo.
typedef struct TreeNode {
int valor;
struct TreeNode *izquierdo;
struct TreeNode *derecho;
unsigned char nivel;
} TreeNode;
typedef struct {
TreeNode *raiz;
unsigned int cantidad;
} ArbolBinario;
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;
}
TreeNode *insertar(ArbolBinario *arbol, int valor) {
if (!arbol->raiz) {
TreeNode *raiz = crearNodo(valor);
if (!raiz) return NULL;
arbol->raiz = raiz;
arbol->cantidad = 1;
return raiz;
}
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;
}El nivel se calcula sumando uno al nivel del nodo padre, lo que simplifica recorridos posteriores.
4.4 Carga desde arreglo
La forma más rápida de poblar el árbol con datos desordenados es recorrer un arreglo y enviar cada valor a insertar. La función siguiente también reinicia el árbol cuando se indica.
void construirDesdeArreglo(ArbolBinario *arbol, int valores[], unsigned int cantidad, int reiniciar) {
if (reiniciar) {
limpiarArbol(arbol);
}
for (unsigned int i = 0; i < cantidad; i++) {
insertar(arbol, valores[i]);
}
}Esta rutina es ideal para pruebas: basta con definir un arreglo de enteros y llamarla con el flag reiniciar en 1 para descartar el contenido anterior.
4.5 Construcción balanceada desde datos ordenados
Si el arreglo ya viene ordenado podemos crear un árbol balanceado seleccionando el elemento central como raíz y repitiendo el proceso en cada mitad. El resultado mantiene alturas similares entre los subárboles.
TreeNode *construirBalanceadoRec(int valores[], int inicio, int fin, unsigned char nivel, unsigned int *contador) {
if (inicio > fin) return NULL;
int medio = (inicio + fin) / 2;
TreeNode *nodo = crearNodo(valores[medio]);
if (!nodo) return NULL;
nodo->nivel = nivel;
nodo->izquierdo = construirBalanceadoRec(valores, inicio, medio - 1, nivel + 1, contador);
nodo->derecho = construirBalanceadoRec(valores, medio + 1, fin, nivel + 1, contador);
(*contador)++;
return nodo;
}
int construirBalanceado(ArbolBinario *arbol, int valores[], unsigned int cantidad) {
limpiarArbol(arbol);
unsigned int contador = 0;
TreeNode *raiz = construirBalanceadoRec(valores, 0, (int)cantidad - 1, 0, &contador);
if (!raiz && cantidad > 0) {
return 0;
}
arbol->raiz = raiz;
arbol->cantidad = contador;
return 1;
}La función devuelve 1 si pudo crear la estructura completa; en caso de fallo deja el árbol vacío para evitar estados inconsistentes.
4.6 Construcción interactiva
Cuando los datos provienen de la entrada estándar debemos validar cada valor. El siguiente ejemplo solicita enteros hasta que el usuario ingresa 0:
void cargarInteractivo(ArbolBinario *arbol) {
int valor = 0;
do {
printf("Ingrese un entero (0 para terminar): ");
if (scanf("%d", &valor) != 1) {
puts("Entrada invalida, cancelando.");
break;
}
if (valor != 0) {
insertar(arbol, valor);
}
} while (valor != 0);
}Este patrón se adapta a cualquier fuente de datos mientras podamos convertir la entrada a entero.
4.7 Herramientas de depuración
Para comprobar que la construcción fue correcta conviene implementar al menos un recorrido en preorden y otro en inorden.
void imprimirPreorden(TreeNode *nodo) {
if (!nodo) return;
printf("%d (nivel %u)\n", nodo->valor, nodo->nivel);
imprimirPreorden(nodo->izquierdo);
imprimirPreorden(nodo->derecho);
}
void imprimirInorden(TreeNode *nodo) {
if (!nodo) return;
imprimirInorden(nodo->izquierdo);
printf("%d ", nodo->valor);
imprimirInorden(nodo->derecho);
}El recorrido inorden de un árbol de búsqueda binaria debería producir una secuencia ordenada ascendentemente; si no ocurre, la construcción contiene errores.
4.8 Escenario práctico
Juntando todo podemos construir un árbol con datos desordenados, revisarlo y luego reemplazarlo por una versión balanceada:
void demoConstruccion(void) {
ArbolBinario arbol;
inicializarArbol(&arbol);
int datos[] = {10, 5, 20, 3, 7, 15};
construirDesdeArreglo(&arbol, datos, 6, 0);
puts("Preorden original:");
imprimirPreorden(arbol.raiz);
int ordenados[] = {2, 4, 6, 8, 12, 16, 18};
construirBalanceado(&arbol, ordenados, 7);
puts("\\nPreorden balanceado:");
imprimirPreorden(arbol.raiz);
limpiarArbol(&arbol);
}El ejemplo anterior permite comparar la distribución de niveles antes y después de balancear.
4.9 Código completo listo para CLion
El siguiente archivo integra todas las funciones y crea dos árboles: uno con inserciones secuenciales y otro balanceado a partir de un arreglo ordenado.
#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 *insertar(ArbolBinario *arbol, int valor) {
if (!arbol->raiz) {
TreeNode *raiz = crearNodo(valor);
if (!raiz) return NULL;
arbol->raiz = raiz;
arbol->cantidad = 1;
return raiz;
}
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;
}
TreeNode *construirBalanceadoRec(int valores[], int inicio, int fin, unsigned char nivel, unsigned int *contador) {
if (inicio > fin) return NULL;
int medio = (inicio + fin) / 2;
TreeNode *nodo = crearNodo(valores[medio]);
if (!nodo) return NULL;
nodo->nivel = nivel;
nodo->izquierdo = construirBalanceadoRec(valores, inicio, medio - 1, nivel + 1, contador);
nodo->derecho = construirBalanceadoRec(valores, medio + 1, fin, nivel + 1, contador);
(*contador)++;
return nodo;
}
int construirBalanceado(ArbolBinario *arbol, int valores[], unsigned int cantidad) {
limpiarArbol(arbol);
if (cantidad == 0) {
return 1;
}
unsigned int contador = 0;
TreeNode *raiz = construirBalanceadoRec(valores, 0, (int)cantidad - 1, 0, &contador);
if (!raiz) {
liberarSubarbol(raiz);
arbol->raiz = NULL;
arbol->cantidad = 0;
return 0;
}
arbol->raiz = raiz;
arbol->cantidad = contador;
return 1;
}
void construirDesdeArreglo(ArbolBinario *arbol, int valores[], unsigned int cantidad) {
for (unsigned int i = 0; i < cantidad; i++) {
insertar(arbol, valores[i]);
}
}
int main(void) {
ArbolBinario arbol;
inicializarArbol(&arbol);
int datos[] = {10, 5, 20, 3, 7, 15};
unsigned int cantidadDatos = (unsigned int)(sizeof(datos) / sizeof(datos[0]));
construirDesdeArreglo(&arbol, datos, cantidadDatos);
puts("Arbol generado con inserciones secuenciales:");
imprimirPreorden(arbol.raiz);
limpiarArbol(&arbol);
int ordenados[] = {2, 4, 6, 8, 12, 16, 18};
unsigned int cantidadOrdenados = (unsigned int)(sizeof(ordenados) / sizeof(ordenados[0]));
if (construirBalanceado(&arbol, ordenados, cantidadOrdenados)) {
puts("\nArbol balanceado:");
imprimirPreorden(arbol.raiz);
} else {
puts("No se pudo construir el arbol balanceado.");
}
limpiarArbol(&arbol);
return 0;
}