Recorridos
En orden, preorden y postorden
Recorridos es una lección gratuita de C Academy en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de C Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de C Academy incluye 4 lecciones en total.
¿Qué es un recorrido?
Un recorrido es una forma sistemática de visitar cada nodo de un árbol exactamente una vez.
Los tres órdenes clásicos en profundidad son inorden, preorden y postorden. Solo se diferencian en cuándo se procesa el nodo actual con respecto a sus subárboles.
Recorrido inorden
El recorrido inorden visita el subárbol izquierdo, después el nodo y, por último, el subárbol derecho.
En un BST, muestra los valores en orden ascendente, por lo que es el recorrido más útil para los árboles de búsqueda.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Recorrido en preorden
El recorrido en preorden visita primero el nodo, después el subárbol izquierdo y, por último, el subárbol derecho.
Resulta útil para copiar un árbol o generar una expresión prefija, porque la raíz se emite antes que sus hijos.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Recorrido en postorden
El recorrido en postorden visita primero ambos subárboles y deja el nodo para el final.
Como los hijos se procesan antes que su padre, este orden es exactamente el que necesita para liberar un árbol, de modo que nunca se use un nodo después de que sus hijos hayan desaparecido.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}El patrón común
Los tres recorridos en profundidad comparten la misma estructura: un caso base NULL, una llamada recursiva para el hijo izquierdo, otra para el hijo derecho y un paso de visita.
Lo único que cambia el nombre del orden es la posición del paso de visita.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/El recorrido inorden imprime en orden
Este programa construye un BST pequeño y ejecuta un recorrido inorden para demostrar la propiedad de mostrar los valores ordenados.
Los valores aparecen del menor al mayor independientemente del orden de inserción.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}Comparación de los tres órdenes
Para el árbol cuya raíz es 10, con 5 a la izquierda y 15 a la derecha, las salidas son diferentes:
El preorden produce 10 5 15. El inorden produce 5 10 15. El postorden produce 5 15 10. Los valores de los nodos son los mismos; solo cambia el momento de la visita.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Recorrido por niveles
El recorrido en anchura, o por niveles, visita los nodos nivel por nivel, de arriba abajo. No es naturalmente recursivo; utiliza una cola.
Se encola la raíz y, después, se desencola repetidamente un nodo, se imprime y se encolan sus hijos.
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}El recorrido permite realizar trabajo real
Los recorridos son plantillas para cualquier operación que deba acceder a todos los nodos, no solo para imprimirlos.
Sustituya el paso de visita por una suma de valores, la búsqueda del máximo o la copia de nodos, y la misma estructura realizará el trabajo.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Coste de un recorrido
Cada recorrido visita cada nodo una vez, por lo que se ejecuta en un tiempo proporcional a n, el número de nodos.
La recursión utiliza un espacio de pila proporcional a la altura del árbol, que es log(n) cuando está equilibrado y n en el peor caso.
Los tres a la vez
Este programa imprime el preorden, el inorden y el postorden del mismo árbol para que pueda compararlos uno junto a otro.
Observe cómo solo la posición de la llamada de impresión cambia la secuencia resultante.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}Comprobación rápida
Elija el recorrido adecuado para cada tarea.
Resumen
Los recorridos en profundidad comparten una misma estructura recursiva; la posición del paso de visita determina si son preorden, inorden o postorden. El inorden de un BST produce una salida ordenada y el postorden es el orden seguro para liberar memoria.
El recorrido por niveles es en anchura y utiliza una cola. Todos visitan cada nodo una vez, en un tiempo O(n).
Preguntas frecuentes
¿La lección «Recorridos» es gratis?
Sí — el texto completo de «Recorridos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de C Academy, actualiza a CoddyKit PRO. El curso de C Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Recorridos»?
En orden, preorden y postorden Practicas C Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar C Academy?
No se requiere experiencia previa. C Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Recorridos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de C Academy?
Sí. Cada lección de C Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.