Percursos
Em ordem, pré-ordem e pós-ordem.
Percursos é uma aula grátis de C Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.
O que é uma travessia?
Uma travessia é uma forma sistemática de visitar cada nó de uma árvore exatamente uma vez.
As três ordens clássicas em profundidade são em-ordem, pré-ordem e pós-ordem. Elas diferem apenas em quando o nó atual é processado em relação às suas subárvores.
Travessia em ordem
A travessia em ordem visita a subárvore esquerda, depois o nó e, por fim, a subárvore direita.
Em uma BST, ela imprime os valores em ordem crescente, o que a torna a travessia mais útil para árvores de busca.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Travessia em pré-ordem
A travessia em pré-ordem visita primeiro o nó, depois a subárvore esquerda e, por fim, a subárvore direita.
Ela é útil para copiar uma árvore ou produzir uma expressão em notação prefixa, pois a raiz é emitida antes de seus filhos.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Travessia em pós-ordem
A travessia em pós-ordem visita primeiro as duas subárvores e deixa o nó para o final.
Como os filhos são processados antes do pai, essa é exatamente a ordem necessária para liberar uma árvore, garantindo que um nó nunca seja usado depois que seus filhos forem removidos.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}O padrão comum
As três travessias em profundidade compartilham a mesma estrutura: um caso-base NULL, uma chamada recursiva para o filho esquerdo, uma chamada recursiva para o filho direito e uma etapa de visita.
Apenas a posição da etapa de visita define o nome da ordem.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/A travessia em ordem imprime valores ordenados
Este programa constrói uma BST pequena e executa uma travessia em ordem, demonstrando a propriedade de saída ordenada.
Os valores aparecem do menor para o maior, independentemente da ordem de inserção.
#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;
}Comparando as três ordens
Para a árvore com raiz 10, filho esquerdo 5 e filho direito 15, as saídas diferem:
A pré-ordem produz 10 5 15. A ordem produz 5 10 15. A pós-ordem produz 5 15 10. Os valores dos nós são os mesmos; apenas o momento da visita muda.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Travessia por níveis
A travessia em largura, ou por níveis, visita os nós nível por nível, de cima para baixo. Ela não é naturalmente recursiva; usa uma fila.
Inserimos a raiz na fila e, em seguida, repetidamente retiramos um nó, imprimimos esse nó e inserimos seus filhos na fila.
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;
}
}A travessia permite realizar tarefas reais
As travessias são modelos para qualquer operação que precise acessar todos os nós, não apenas imprimi-los.
Substitua a etapa de visita por uma soma de valores, pela busca do maior valor ou pela cópia dos nós, e a mesma estrutura realizará a tarefa.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Custo de uma travessia
Cada travessia visita cada nó uma vez, portanto é executada em tempo proporcional a n, o número de nós.
A recursão usa espaço de pilha proporcional à altura da árvore: log(n) quando ela está balanceada e n no pior caso.
As três de uma vez
Este programa imprime a pré-ordem, a ordem e a pós-ordem da mesma árvore para que você possa compará-las lado a lado.
Observe como apenas a posição da chamada de impressão altera a sequência 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;
}Verificação rápida
Escolha a travessia adequada para cada tarefa.
Recapitulação
As travessias em profundidade compartilham uma estrutura recursiva; a posição da etapa de visita determina se são pré-ordem, em-ordem ou pós-ordem. A travessia em ordem de uma BST produz uma saída ordenada, e a pós-ordem é a ordem segura para liberar a árvore.
A travessia por níveis é uma travessia em largura e usa uma fila. Todas visitam cada nó uma vez, em tempo O(n).
Perguntas Frequentes
A aula “Percursos” é grátis?
Sim — o texto completo de “Percursos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.
O que vou aprender em “Percursos”?
Em ordem, pré-ordem e pós-ordem. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar C Academy?
Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Percursos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de C Academy?
Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.