Nós e estrutura de árvores
Modele um nó com ponteiros.
Nós e estrutura de árvores é uma aula grátis de C Academy no CoddyKit. Esta é a aula 1 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 árvore binária
Uma árvore binária é uma estrutura hierárquica na qual cada nó armazena um valor e possui links para até dois filhos: um filho esquerdo e um filho direito.
O nó no topo é a raiz. Nós sem filhos são folhas. Esse formato torna as árvores binárias excelentes para pesquisa rápida, ordenação e processamento recursivo.
A struct Node
Em C, modelamos um nó com uma struct que armazena os dados e dois ponteiros autorreferentes.
Cada ponteiro aponta para outro Node ou para NULL quando não há filho daquele lado.
struct Node {
int value;
struct Node *left;
struct Node *right;
};Por que usar ponteiros autorreferentes
Um nó não pode conter outro nó completo por valor, pois isso exigiria armazenamento infinito. Em vez disso, ele mantém ponteiros para seus filhos.
Os ponteiros têm tamanho fixo, portanto a struct mantém um tamanho conhecido e ainda pode se encadear a outros nós na heap.
struct Node {
int value;
struct Node *left; /* 8 bytes on 64-bit */
struct Node *right; /* 8 bytes on 64-bit */
};Um typedef por conveniência
Digitar struct Node em todos os lugares é trabalhoso. Um typedef permite escrever apenas Node.
A tag ainda é necessária dentro da struct, pois o tipo ainda não está totalmente definido nesse ponto.
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;Alocando um Node
Os nós ficam na heap e são criados com malloc. Definimos o valor e inicializamos ambos os ponteiros para filhos como NULL.
Verifique sempre se malloc não retornou NULL antes de usar a memória.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (n == NULL) return NULL;
n->value = value;
n->left = NULL;
n->right = NULL;
return n;
}Construindo manualmente uma árvore pequena
Para entender os links, vamos conectar manualmente três nós: uma raiz com dois filhos.
Este programa constrói a árvore e imprime os valores; depois, normalmente a liberaríamos (isso será abordado mais adiante).
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;
Node *create_node(int v) {
Node *n = malloc(sizeof(Node));
n->value = v; n->left = NULL; n->right = NULL;
return n;
}
int main(void) {
Node *root = create_node(10);
root->left = create_node(5);
root->right = create_node(15);
printf("%d %d %d\n", root->left->value, root->value, root->right->value);
return 0;
}Alcançando os netos
O senhor percorre a árvore encadeando o operador seta. root->left->right desce até o filho esquerdo e depois até o filho direito dele.
Antes de seguir um ponteiro, certifique-se de que ele não é NULL, ou o programa falhará.
/* root
* \
* right (15)
* \
* right->right (20)
*/
if (root->right != NULL && root->right->right != NULL)
printf("%d\n", root->right->right->value);Contando nós recursivamente
A recursão se adapta naturalmente às árvores. Para contar os nós, uma subárvore vazia tem zero nós; caso contrário, contamos este nó mais as duas subárvores.
A verificação de NULL é o caso-base que interrompe a recursão.
int count_nodes(Node *root) {
if (root == NULL) return 0;
return 1 + count_nodes(root->left)
+ count_nodes(root->right);
}Medindo a altura
A altura de uma árvore é o caminho mais longo da raiz até uma folha, medido em arestas.
Escolhemos a maior das alturas das duas subárvores e adicionamos um. A uma árvore vazia atribuímos altura -1, para que um único nó tenha altura 0.
int height(Node *root) {
if (root == NULL) return -1;
int l = height(root->left);
int r = height(root->right);
return 1 + (l > r ? l : r);
}Identificando folhas
Uma folha é um nó sem filhos: tanto left quanto right são NULL.
Esse pequeno auxiliar é útil em muitas rotinas de percurso e contagem.
int is_leaf(Node *n) {
return n != NULL && n->left == NULL && n->right == NULL;
}Colocando a estrutura em uso
Aqui, uma árvore pequena é construída, e relatamos sua quantidade de nós e sua altura usando os auxiliares recursivos.
Observe que os auxiliares nunca presumem um formato fixo; eles funcionam para qualquer árvore porque a recursão segue os ponteiros reais.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }
int main(void){
Node *root = nn(10);
root->left = nn(5); root->right = nn(15);
root->left->left = nn(2);
printf("nodes=%d height=%d\n", count(root), height(root));
return 0;
}Verificação rápida
Teste sua compreensão da estrutura de nós.
Recapitulação
Um nó de árvore binária armazena um valor e dois ponteiros autorreferentes (left, right), definidos como NULL quando estão ausentes.
Alocamos nós com malloc, conectamo-los manualmente e processamo-los recursivamente. A verificação de NULL é sempre o caso-base para contagem, altura e testes de folhas.
Perguntas Frequentes
A aula “Nós e estrutura de árvores” é grátis?
Sim — o texto completo de “Nós e estrutura de árvores” é 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 “Nós e estrutura de árvores”?
Modele um nó com ponteiros. 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 1 de 4.
Quanto tempo leva a aula “Nós e estrutura de árvores”?
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