Recorrer sin ciclos

Cuando hay dos caminos, la función se llama a sí misma.

1Por qué

Recorrer una lista es fácil porque solo hay un camino: avanzas hasta el NULL. Un árbol no tiene «el siguiente»: tiene dos, y en cada uno vuelve a haber dos.

Con un ciclo esto se pone feo enseguida, porque habría que ir anotando a mano los caminos pendientes. Pero hay una forma que cabe en tres líneas, y funciona porque un árbol está hecho de árboles: el hijo izquierdo de la raíz es, él solo, un árbol completo.

Si ya tienes una función que recorre un árbol, para recorrer el de la izquierda basta con llamarla otra vez. Eso es la recursión: una función que se llama a sí misma sobre un trozo más pequeño del problema.

Dos partes, siempre. Dónde parar —aquí, cuando el nodo es NULL— y la llamada sobre algo más chico. Si falta la primera, la función sigue bajando más allá del último nodo y termina preguntándole algo a un puntero que vale NULL. El taller te lo va a señalar, con su línea.

El orden de las tres líneas decide en qué orden salen los datos. Poniendo el izquierdo primero, después el valor y al final el derecho, salen ordenados de menor a mayor. Eso no es casualidad: es la regla de colocar menores a la izquierda, leída al derecho.

2Míralo andar

Este programa funciona. Léelo, y después ejecútalo sin cambiar nada.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Nodo {
    int valor;
    struct Nodo *izq;
    struct Nodo *der;
} Nodo;
 
Nodo *crear(int v)
{
    Nodo *n = malloc(sizeof(Nodo));
    n->valor = v;
    n->izq = NULL;
    n->der = NULL;
    return n;
}
 
void enOrden(Nodo *n)
{
    if (n == NULL) return;
 
    enOrden(n->izq);
    printf("%d ", n->valor);
    enOrden(n->der);
}
 
int main(void)
{
    Nodo *raiz = crear(5);
    raiz->izq = crear(3);
    raiz->der = crear(8);
 
    enOrden(raiz);
    printf("\n");
 
    free(raiz->izq);
    free(raiz->der);
    free(raiz);
    return 0;
}

línea 21
Dónde parar. Sin esta línea la función se llamaría para siempre: es la mitad más importante de las dos.
línea 23
Se llama a sí misma sobre el hijo izquierdo, que es un árbol completo más chico.
línea 24
El valor sale ENTRE las dos llamadas. Ese orden es lo que hace que salgan de menor a mayor.
línea 34
Una sola llamada recorre el árbol entero, sin ciclos por ninguna parte.

3Ahora tú

A esta función le falta dónde parar, así que no termina. Escribe esa línea

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Nodo {
    int valor;
    struct Nodo *izq;
    struct Nodo *der;
} Nodo;
 
Nodo *crear(int v)
{
    Nodo *n = malloc(sizeof(Nodo));
    n->valor = v;
    n->izq = NULL;
    n->der = NULL;
    return n;
}
 
void enOrden(Nodo *n)
{
    
 
    enOrden(n->izq);
    printf("%d ", n->valor);
    enOrden(n->der);
}
 
int main(void)
{
    Nodo *raiz = crear(6);
    raiz->izq = crear(2);
    raiz->der = crear(9);
 
    enOrden(raiz);
    printf("\n");
 
    free(raiz->izq);
    free(raiz->der);
    free(raiz);
    return 0;
}

↖︎ Tu línea va aquí, antes de las llamadas: es la pregunta que corta el descenso.

Recorrer sin ciclos

1Por qué

2Míralo andar

3Ahora tú

Ejecutar

Lo que dice tu programa

Qué pasó

4Qué guarda tu programa

Memoria