Los recorridos definen el orden en el que visitamos los nodos de un árbol binario. Dominar las variantes principales permite imprimir, buscar y serializar la estructura sin perder información. En este tema implementamos las versiones recursivas e iterativas de preorden, inorden y postorden, sumamos un recorrido por niveles y finalizamos con un ejemplo ejecutable.
Trabajaremos con el mismo modelo de nodo de los temas anteriores. Mantener una definición consistente asegura que cada helper funcione sin ajustes.
typedef struct TreeNode {
int valor;
struct TreeNode *izquierdo;
struct TreeNode *derecho;
unsigned char nivel;
} TreeNode;
void imprimirNodo(TreeNode *nodo) {
if (!nodo) return;
printf("%d (nivel %u)\n", nodo->valor, nodo->nivel);
}La función imprimirNodo nos servirá para mantener un formato homogéneo durante los ejemplos.
Preorden visita primero el nodo actual, luego el subárbol izquierdo y finalmente el derecho. Es ideal para clonar el árbol o guardarlo en disco.
void recorrerPreorden(TreeNode *nodo) {
if (!nodo) return;
imprimirNodo(nodo);
recorrerPreorden(nodo->izquierdo);
recorrerPreorden(nodo->derecho);
}Esta versión recursiva es directa y funciona siempre que la profundidad no exceda el límite de la pila del programa.
Inorden recorre el subárbol izquierdo, luego el nodo actual y al final el derecho. En un árbol de búsqueda binaria produce la lista de valores en orden ascendente.
void recorrerInorden(TreeNode *nodo) {
if (!nodo) return;
recorrerInorden(nodo->izquierdo);
imprimirNodo(nodo);
recorrerInorden(nodo->derecho);
}Postorden procesa ambos subárboles antes del nodo actual. Se usa para liberar memoria o evaluar expresiones aritméticas donde cada operador necesita los resultados de sus hijos.
void recorrerPostorden(TreeNode *nodo) {
if (!nodo) return;
recorrerPostorden(nodo->izquierdo);
recorrerPostorden(nodo->derecho);
imprimirNodo(nodo);
}Cuando la profundidad es grande podemos optar por pilas explícitas para evitar desbordes. A continuación una implementación simple de preorden iterativo.
typedef struct {
TreeNode **items;
int tope;
int capacidad;
} PilaNodos;
int crearPila(PilaNodos *pila, int capacidad) {
pila->items = malloc(sizeof(TreeNode *) * capacidad);
if (!pila->items) return 0;
pila->tope = -1;
pila->capacidad = capacidad;
return 1;
}
void destruirPila(PilaNodos *pila) {
free(pila->items);
}
void apilar(PilaNodos *pila, TreeNode *nodo) {
pila->items[++pila->tope] = nodo;
}
TreeNode *desapilar(PilaNodos *pila) {
if (pila->tope < 0) return NULL;
return pila->items[pila->tope--];
}
void recorrerPreordenIterativo(TreeNode *raiz) {
if (!raiz) return;
PilaNodos pila;
if (!crearPila(&pila, 128)) return;
apilar(&pila, raiz);
while (pila.tope >= 0) {
TreeNode *actual = desapilar(&pila);
imprimirNodo(actual);
if (actual->derecho) apilar(&pila, actual->derecho);
if (actual->izquierdo) apilar(&pila, actual->izquierdo);
}
destruirPila(&pila);
}La pila reserva un tamaño fijo para simplificar el ejemplo. En un proyecto real podrías redimensionarla dinámicamente.
Recorrer por niveles implica visitar los nodos en el orden en que se descubren al avanzar de izquierda a derecha. Utilizamos una cola circular.
typedef struct {
TreeNode **datos;
unsigned int frente;
unsigned int fondo;
unsigned int capacidad;
} ColaNiveles;
int crearCola(ColaNiveles *cola, unsigned int capacidad) {
cola->datos = malloc(sizeof(TreeNode *) * capacidad);
if (!cola->datos) return 0;
cola->frente = 0;
cola->fondo = 0;
cola->capacidad = capacidad;
return 1;
}
int colaVacia(ColaNiveles *cola) {
return cola->frente == cola->fondo;
}
void encolar(ColaNiveles *cola, TreeNode *nodo) {
cola->datos[cola->fondo++ % cola->capacidad] = nodo;
}
TreeNode *desencolar(ColaNiveles *cola) {
if (colaVacia(cola)) return NULL;
return cola->datos[cola->frente++ % cola->capacidad];
}
void destruirCola(ColaNiveles *cola) {
free(cola->datos);
}
void recorrerPorNiveles(TreeNode *raiz) {
if (!raiz) return;
ColaNiveles cola;
if (!crearCola(&cola, 128)) return;
encolar(&cola, raiz);
while (!colaVacia(&cola)) {
TreeNode *actual = desencolar(&cola);
imprimirNodo(actual);
if (actual->izquierdo) encolar(&cola, actual->izquierdo);
if (actual->derecho) encolar(&cola, actual->derecho);
}
destruirCola(&cola);
}El siguiente archivo crea un árbol, ejecuta los recorridos principales y muestra los resultados en consola.
#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;
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 imprimirNodo(TreeNode *nodo) {
if (!nodo) return;
printf("%d (nivel %u)\n", nodo->valor, nodo->nivel);
}
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 recorrerPreorden(TreeNode *nodo) {
if (!nodo) return;
imprimirNodo(nodo);
recorrerPreorden(nodo->izquierdo);
recorrerPreorden(nodo->derecho);
}
void recorrerInorden(TreeNode *nodo) {
if (!nodo) return;
recorrerInorden(nodo->izquierdo);
imprimirNodo(nodo);
recorrerInorden(nodo->derecho);
}
void recorrerPostorden(TreeNode *nodo) {
if (!nodo) return;
recorrerPostorden(nodo->izquierdo);
recorrerPostorden(nodo->derecho);
imprimirNodo(nodo);
}
void imprimirPreordenIterativo(TreeNode *raiz) {
if (!raiz) return;
TreeNode *pila[64];
int tope = -1;
pila[++tope] = raiz;
while (tope >= 0) {
TreeNode *actual = pila[tope--];
imprimirNodo(actual);
if (actual->derecho) pila[++tope] = actual->derecho;
if (actual->izquierdo) pila[++tope] = actual->izquierdo;
}
}
void imprimirPorNiveles(TreeNode *raiz) {
if (!raiz) return;
TreeNode *cola[64];
unsigned int frente = 0, fondo = 0;
cola[fondo++] = raiz;
while (frente < fondo) {
TreeNode *actual = cola[frente++];
imprimirNodo(actual);
if (actual->izquierdo) cola[fondo++] = actual->izquierdo;
if (actual->derecho) cola[fondo++] = actual->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 = {0};
int valores[] = {10, 5, 15, 3, 7, 12, 18};
unsigned int total = (unsigned int)(sizeof(valores) / sizeof(valores[0]));
for (unsigned int i = 0; i < total; i++) {
insertar(&arbol, valores[i]);
}
puts("Preorden:");
recorrerPreorden(arbol.raiz);
puts("\nInorden:");
recorrerInorden(arbol.raiz);
puts("\nPostorden:");
recorrerPostorden(arbol.raiz);
puts("\nPreorden iterativo:");
imprimirPreordenIterativo(arbol.raiz);
puts("\nRecorrido por niveles:");
imprimirPorNiveles(arbol.raiz);
limpiarArbol(&arbol);
return 0;
}