Con la estructura de nodos lista, necesitamos recorrer el árbol para visitar, procesar y verificar cada dato. En este tema aplicamos los patrones de recorrido más comunes usando la representación hijo-izquierdo/hermano-derecho y listas de hijos, todos implementados en C.
En el recorrido preorden visitamos el nodo actual antes que sus hijos. Este orden resulta ideal para serializar el árbol, copiarlo u obtener una vista jerárquica.
#include <stdio.h>
typedef struct GeneralNode {
int valor;
struct GeneralNode *primerHijo;
struct GeneralNode *siguienteHermano;
} GeneralNode;
void recorridoPreorden(const GeneralNode *nodo) {
if (!nodo) {
return;
}
printf("%d ", nodo->valor);
for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
recorridoPreorden(hijo);
}
}El ciclo for itera sobre los hermanos y cada llamada recursiva procesa el subárbol completo del hijo.
El recorrido postorden procesa primero a los hijos y luego al nodo. Este orden es el preferido para liberar memoria, calcular alturas o evaluar expresiones.
void recorridoPostorden(const GeneralNode *nodo) {
if (!nodo) {
return;
}
for (const GeneralNode *hijo = nodo->primerHijo; hijo; hijo = hijo->siguienteHermano) {
recorridoPostorden(hijo);
}
printf("%d ", nodo->valor);
}Recuerda que cada llamada delimita un subárbol completo; al terminar, disponemos del orden necesario para tareas como la liberación de nodos.
El breadth-first search (BFS) recorre los nodos nivel por nivel utilizando una cola. En C implementamos una cola simple con estructura circular o lista enlazada. El ejemplo siguiente usa una cola enlazada ligera.
#include <stdlib.h>
typedef struct QueueNode {
const GeneralNode *nodo;
struct QueueNode *sig;
} QueueNode;
typedef struct {
QueueNode *frente;
QueueNode *fondo;
} Queue;
void queueInit(Queue *q) {
q->frente = NULL;
q->fondo = NULL;
}
int queueEmpty(const Queue *q) {
return !q->frente;
}
void queuePush(Queue *q, const GeneralNode *nodo) {
QueueNode *nuevo = malloc(sizeof(QueueNode));
if (!nuevo) {
return;
}
nuevo->nodo = nodo;
nuevo->sig = NULL;
if (q->fondo) {
q->fondo->sig = nuevo;
} else {
q->frente = nuevo;
}
q->fondo = nuevo;
}
const GeneralNode *queuePop(Queue *q) {
if (!q->frente) {
return NULL;
}
QueueNode *tmp = q->frente;
const GeneralNode *nodo = tmp->nodo;
q->frente = tmp->sig;
if (!q->frente) {
q->fondo = NULL;
}
free(tmp);
return nodo;
}
void recorridoPorNiveles(const GeneralNode *raiz) {
Queue q;
queueInit(&q);
queuePush(&q, raiz);
while (!queueEmpty(&q)) {
const GeneralNode *actual = queuePop(&q);
if (!actual) {
continue;
}
printf("%d ", actual->valor);
for (const GeneralNode *hijo = actual->primerHijo; hijo; hijo = hijo->siguienteHermano) {
queuePush(&q, hijo);
}
}
}Este recorrido es ideal para analizar la estructura por niveles, calcular anchuras y exportar el árbol a formatos que dependen de orden topológico.
Las funciones anteriores se apoyan en recursión natural. Sin embargo, cuando la altura del árbol es grande podría convenir una versión iterativa con pilas manuales.
#include <stdlib.h>
typedef struct StackNode {
const GeneralNode *nodo;
struct StackNode *sig;
} StackNode;
void push(StackNode **pila, const GeneralNode *nodo) {
StackNode *nuevo = malloc(sizeof(StackNode));
if (!nuevo) return;
nuevo->nodo = nodo;
nuevo->sig = *pila;
*pila = nuevo;
}
const GeneralNode *pop(StackNode **pila) {
if (!*pila) return NULL;
StackNode *tmp = *pila;
const GeneralNode *nodo = tmp->nodo;
*pila = tmp->sig;
free(tmp);
return nodo;
}
void preordenIterativo(const GeneralNode *raiz) {
StackNode *pila = NULL;
push(&pila, raiz);
while (pila) {
const GeneralNode *actual = pop(&pila);
if (!actual) continue;
printf("%d ", actual->valor);
const GeneralNode *hijos[128];
unsigned int count = 0;
for (const GeneralNode *h = actual->primerHijo; h && count < 128; h = h->siguienteHermano) {
hijos[count++] = h;
}
while (count) {
push(&pila, hijos[--count]);
}
}
}La versión iterativa evita desbordar la pila del sistema a costa de administrar estructuras auxiliares.
Los recorridos por niveles utilizan colas, mientras que las variantes iterativas de preorden y postorden emplean pilas. También es posible apoyar los recorridos en listas y arreglos temporales para preservar el orden original de los hijos. Elegir la estructura correcta depende de si necesitamos FIFO (cola), LIFO (pila) o un almacenamiento temporal ordenado.
En C debemos liberar todas las estructuras auxiliares después de usarlas; por ello conviene encapsular las operaciones de cola o pila en funciones propias que administren malloc/free.
Todos los recorridos visitan cada nodo una sola vez, por lo que su complejidad temporal es O(n), siendo n la cantidad de nodos del árbol. La complejidad espacial depende de la estructura auxiliar:
Monitorear estas cotas ayuda a evitar sorpresas cuando el árbol crece con datos reales.