Pesquisando e liberando
Encontre nós e libere memória.
Pesquisando e liberando é uma aula grátis de C Academy no CoddyKit. Esta é a aula 4 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.
Pesquisando em uma BST
A busca aproveita a regra de ordenação. Em cada nó, comparamos o alvo com o valor do nó e seguimos para apenas uma subárvore.
Como descartamos metade dos nós restantes a cada etapa, o custo da busca cresce com a altura da árvore, não com o seu tamanho.
Busca recursiva
A busca recursiva tem dois casos-base: uma subárvore vazia significa que o valor não foi encontrado, e um valor correspondente significa que ele foi encontrado.
Caso contrário, fazemos uma chamada recursiva para a esquerda ou para a direita, dependendo da comparação.
Node *search(Node *root, int target) {
if (root == NULL || root->value == target)
return root;
if (target < root->value)
return search(root->left, target);
return search(root->right, target);
}Busca iterativa
A busca também pode ser implementada como um simples laço, evitando o custo adicional da recursão.
Seguimos os ponteiros pela árvore até encontrar o alvo ou ultrapassar o fim em NULL.
Node *search_iter(Node *root, int target) {
while (root != NULL) {
if (target == root->value) return root;
root = (target < root->value)
? root->left : root->right;
}
return NULL; /* not found */
}A busca em ação
Este programa constrói uma BST e procura um valor presente e um valor ausente, imprimindo se cada um foi encontrado.
Um retorno diferente de NULL significa que o valor foi encontrado; NULL significa que ele não está na árvore.
#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;
}
Node *search(Node *r,int t){
if(!r||r->value==t) return r;
return t<r->value ? search(r->left,t) : search(r->right,t);
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("7:%s 99:%s\n",
search(root,7)?"found":"no",
search(root,99)?"found":"no");
return 0;
}Encontrando o mínimo
Em uma BST, o menor valor está no nó mais à esquerda: continue seguindo left até que ele seja NULL.
De forma simétrica, o maior valor está no nó mais à direita. Essas funções auxiliares são importantes para remoção e consultas por intervalo.
Node *find_min(Node *root) {
if (root == NULL) return NULL;
while (root->left != NULL)
root = root->left;
return root;
}Por que liberar é importante
Cada nó veio de malloc, portanto cada nó deve ser devolvido com free. Esquecer de liberar causa vazamento de memória.
Porém, você não pode liberar um nó e depois ler os ponteiros de seus filhos, portanto a ordem de liberação é fundamental.
Liberando em pós-ordem
A forma segura de liberar uma árvore é usar a pós-ordem: libere primeiro os dois filhos e depois o próprio nó.
Isso garante que leiamos os ponteiros left e right de um nó antes que a memória dele seja liberada.
void free_tree(Node *root) {
if (root == NULL) return;
free_tree(root->left);
free_tree(root->right);
free(root);
}Uma ordem incorreta perigosa
Se você liberar o nó antes de fazer a chamada recursiva para os filhos, criará um comportamento indefinido: tentará desreferenciar memória liberada para alcançar as subárvores.
Esse é um erro clássico de uso após liberação. Sempre libere os filhos primeiro.
/* WRONG: use-after-free */
void bad_free(Node *root) {
if (!root) return;
free(root); /* freed here */
bad_free(root->left); /* reads freed memory! */
bad_free(root->right);
}Evite ponteiros pendentes
Depois que free_tree retorna, o ponteiro original da raiz ainda contém o endereço antigo, mas a memória desapareceu.
Defini-lo novamente como NULL no chamador evita o uso acidental de um ponteiro pendente.
free_tree(root);
root = NULL; /* avoid a dangling pointer */Contando nós liberados
Podemos confirmar que a liberação funciona contando os nós durante a travessia em pós-ordem e liberando cada um deles em seguida.
Este programa constrói uma árvore, libera-a e informa quantos nós foram liberados.
#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;
}
int free_count(Node *r){
if(!r) return 0;
int c = free_count(r->left) + free_count(r->right);
free(r);
return c + 1;
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("freed=%d\n", free_count(root));
root = NULL;
return 0;
}Busca e liberação juntas
Um ciclo de vida completo: construir a árvore, pesquisá-la e depois liberá-la. Fazer as três coisas mantém os programas corretos e sem vazamentos.
Ferramentas como Valgrind podem confirmar que cada chamada a malloc corresponde a uma chamada a free.
/* lifecycle
* 1. insert values (allocate)
* 2. search as needed (read-only)
* 3. free_tree(root) (deallocate)
* 4. root = NULL (avoid dangling)
*/Verificação rápida
Raciocine sobre a desalocação segura.
Recapitulação
A busca em uma BST compara e desce para uma subárvore a cada etapa, com custo de tempo proporcional à altura. O mínimo é o nó mais à esquerda; o máximo, o nó mais à direita.
Libere uma árvore em pós-ordem para que os filhos sejam liberados antes do pai e, em seguida, defina a raiz como NULL para evitar um ponteiro pendente.
Aprenda C com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 39
- Aulas
- 144
Perguntas Frequentes
A aula “Pesquisando e liberando” é grátis?
Sim — o texto completo de “Pesquisando e liberando” é 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 “Pesquisando e liberando”?
Encontre nós e libere memória. 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 4 de 4.
Quanto tempo leva a aula “Pesquisando e liberando”?
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.
Todas as aulas deste curso
- Nós e estrutura de árvores
- Inserindo em uma BST
- Percursos
- Pesquisando e liberando