Recorrido postorden de árbol binario en C: ejercicio resuelto

Si buscas recorrido postorden de árbol binario en C ejercicio resuelto, aquí tienes la versión recursiva y la iterativa con dos pilas. El postorden visita los nodos en el orden hijo izquierdo → hijo derecho → raíz (LRN), lo que lo convierte en el recorrido natural para liberar la memoria de un árbol.

La versión iterativa del postorden es más compleja que la del preorden porque la raíz se procesa al final; el truco de las dos pilas invierte el preorden derecho para obtener el postorden.

Enunciado

Dado el árbol:

Imprime los nodos en orden postorden de forma recursiva e iterativa.

Solución en C

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <stdlib.h>

typedef struct Nodo {
    int dato;
    struct Nodo *izq, *der;
} Nodo;

Nodo *nuevo(int dato) {
    Nodo *n = malloc(sizeof(Nodo));
    n->dato = dato; n->izq = n->der = NULL;
    return n;
}

/* --- Versión recursiva --- */
void postorden_rec(const Nodo *n) {
    if (!n) return;
    postorden_rec(n->izq);
    postorden_rec(n->der);
    printf("%d ", n->dato);
}

/* --- Versión iterativa con dos pilas --- */
#define MAX 64
void postorden_iter(const Nodo *raiz) {
    if (!raiz) return;
    const Nodo *p1[MAX], *p2[MAX];
    int t1 = 0, t2 = 0;
    p1[t1++] = raiz;

    while (t1 > 0) {
        const Nodo *n = p1[--t1];
        p2[t2++] = n;                   /* resultado inverso */
        if (n->izq) p1[t1++] = n->izq;
        if (n->der) p1[t1++] = n->der;
    }
    /* Vaciar la segunda pila = postorden */
    while (t2 > 0) printf("%d ", p2[--t2]->dato);
}

void liberar(Nodo *n) {
    if (!n) return;
    liberar(n->izq);
    liberar(n->der);
    free(n);
}

int main(void) {
    Nodo *raiz = nuevo(1);
    raiz->izq  = nuevo(2);
    raiz->der  = nuevo(3);
    raiz->izq->izq = nuevo(4);
    raiz->izq->der = nuevo(5);
    raiz->der->der = nuevo(6);

    printf("Recursivo: "); postorden_rec(raiz);  printf("\n");
    printf("Iterativo: "); postorden_iter(raiz); printf("\n");

    liberar(raiz);
    return 0;
}

Resultado esperado

1
2
Recursivo: 4 5 2 6 3 1 
Iterativo: 4 5 2 6 3 1 

Errores frecuentes

Intentar usar una sola pila para el postorden iterativo sin un puntero de seguimiento: es posible pero requiere una variable adicional que rastreé el último nodo visitado, lo que complica la implementación. Las dos pilas son más claras.
No respetar el orden LRN: es común invertir los hijos y visitar RLN; el resultado es un recorrido en espejo.
Liberar la memoria en preorden en lugar de postorden: liberar un nodo antes de sus hijos deja punteros colgantes e impide llegar a los hijos.
Usar int como tipo del puntero de pila en lugar de Nodo *: la pila debe almacenar punteros a nodos.

Aplicación práctica

El postorden se usa para liberar la memoria de un árbol (los hijos deben liberarse antes que el padre), para evaluar expresiones en notación postfija (RPN), para calcular el tamaño de subdirectorios en un árbol de ficheros y para la compilación (generación de código donde los operandos se evalúan antes que el operador).

Siguiente ejercicio recomendado

Práctica guiada y libro completo

Si quieres una ruta completa con progresión real de dificultad:

FAQ

¿Por qué el postorden iterativo necesita dos pilas?

Porque el postorden procesa la raíz al final, lo cual es contrario al comportamiento natural de una pila LIFO. El truco consiste en hacer un recorrido similar al preorden pero visitando primero el hijo derecho (obteniendo raíz-derecho-izquierdo), guardar los nodos en una segunda pila, y al vaciarla se obtiene el orden inverso: izquierdo-derecho-raíz = postorden.

¿Cómo saber si un recorrido está en postorden sin ejecutar el código?

Para el árbol del ejercicio: los nodos hoja (4, 5, 6) siempre aparecen antes que sus padres (2, 3), y la raíz (1) siempre aparece al final. Si el último elemento es la raíz y los hijos siempre preceden a sus padres, el recorrido es postorden.

¿Se puede implementar el postorden con una sola pila?

Sí, manteniendo un puntero ultimo_visitado que indica el último nodo procesado. Cuando el hijo derecho ya fue visitado (o no existe), se procesa la raíz. La lógica es más compleja; las dos pilas son preferibles por claridad.