Árvores binárias: estrutura, percursos e métricas
Árvore é uma estrutura de dados hierárquica formada por nós e ligações entre eles. Em uma árvore enraizada, um nó é a raiz; cada outro nó tem exatamente um pai, e não há ciclos. Essa organização serve, por exemplo, para representar expressões, diretórios e decisões. Neste artigo, o foco é a árvore binária, na qual cada nó possui, no máximo, um filho à esquerda e um à direita. A posição dos filhos importa: trocar esquerda e direita pode mudar o resultado de um percurso.
Fundamentos e estrutura
Um nó sem filhos é uma folha. Nós com pelo menos um filho são internos. O conjunto formado por um nó e seus descendentes é uma subárvore. A profundidade de um nó é o número de arestas da raiz até ele; a raiz tem profundidade zero. Uma árvore vazia não tem raiz. Essas definições permitem descrever a estrutura sem depender dos valores armazenados (OpenDSA Project Contributors, 2024a).
Considere uma pequena árvore de identificadores de tarefas. O diagrama mostra as posições dos sete nós; as setas representam vínculos entre pai e filho.
Figura 1. Árvore binária de tarefas usada em todos os exemplos.
flowchart TD
A["8"] --> B["4"]
A --> C["12"]
B --> D["2"]
B --> E["6"]
C --> F["10"]
C --> G["14"]
A raiz é 8; 4 e 12 estão na profundidade 1; 2, 6, 10 e 14 são folhas na profundidade 2. Cada nó tem até dois filhos, mas uma árvore binária não precisa ser completa nem conter valores ordenados. Árvore binária de busca (ABB) é uma categoria adicional: em cada nó, valores da subárvore esquerda são menores e valores da direita são maiores, supondo chaves distintas. A árvore da figura satisfaz essa regra, mas os percursos e métricas a seguir também se aplicam a árvores binárias que não a satisfazem.
Em C++17, podemos representar cada nó por seu valor e dois ponteiros para filhos. A ausência de filho é representada por nullptr. A implementação completa aparece adiante; o importante aqui é que as duas ligações preservam a distinção entre esquerda e direita.
Propriedades que decorrem da estrutura
Se uma árvore não vazia tem n nós, ela tem exatamente n − 1 arestas: cada nó, exceto a raiz, contribui com uma única ligação ao pai. Em uma árvore binária com n nós, há 2n posições possíveis de filho; como n − 1 posições estão ocupadas, restam n + 1 ligações nulas. Essas contas são úteis para detectar erros em representações encadeadas.
Na profundidade d podem existir, no máximo, 2^d nós: cada nó do nível anterior cria até dois filhos. Portanto, uma árvore de altura h (em arestas) tem, no máximo, 1 + 2 + ··· + 2^h = 2^(h+1) − 1 nós. Invertendo a desigualdade, h ≥ ⌈log₂(n + 1)⌉ − 1. Esse é um limite inferior, não uma garantia de que qualquer árvore com n nós seja rasa: uma cadeia de n nós tem altura n − 1. Para a Figura 1, n = 7 e h = 2, atingindo o máximo de nós possível nessa altura.
Uma árvore estrita tem nós com zero ou dois filhos; nesse caso, se i é o número de nós internos e f o de folhas, f = i + 1. A figura tem três nós internos e quatro folhas. Já uma árvore perfeita ocupa todas as posições até sua altura, como a figura; uma árvore completa ocupa todos os níveis anteriores ao último e preenche o último da esquerda para a direita. “Balanceada” depende de um critério formal específico: uma ABB pode satisfazer a regra de ordenação sem ser balanceada. Weiss (2014) trata a distinção entre árvores binárias de busca e mecanismos de balanceamento, como árvores AVL.
Percursos em árvores binárias
Percorrer uma árvore é visitar todos os seus nós segundo uma regra. Nos percursos em profundidade, a posição da visita ao nó atual define a ordem: pré-ordem visita nó, esquerda e direita; em ordem visita esquerda, nó e direita; pós-ordem visita esquerda, direita e nó. O percurso por níveis visita os nós de cada profundidade da esquerda para a direita, usando uma fila (OpenDSA Project Contributors, 2024b).
| Percurso | Sequência na Figura 1 | Uso típico |
|---|---|---|
| Pré-ordem | 8, 4, 2, 6, 12, 10, 14 | Processar um nó antes de seus descendentes |
| Em ordem | 2, 4, 6, 8, 10, 12, 14 | Obter chaves ordenadas se a árvore for uma ABB |
| Pós-ordem | 2, 6, 4, 10, 14, 12, 8 | Processar filhos antes do pai |
| Por níveis | 8, 4, 12, 2, 6, 10, 14 | Examinar a árvore por profundidade |
Por exemplo, na pré-ordem visitamos 8 antes de entrar na subárvore de 4. Na pós-ordem, 4 só aparece depois de 2 e 6. A ordem crescente do percurso em ordem decorre da propriedade de ABB desta árvore específica; ela não é garantida para uma árvore binária arbitrária.
Por que cada ordem funciona
Os três percursos em profundidade seguem a mesma decomposição recursiva: resolvem um problema para a raiz e duas subárvores. A diferença é quando emitem a raiz. A pré-ordem é útil quando o pai precisa aparecer antes de seus descendentes, por exemplo, ao registrar uma estrutura hierárquica. A pós-ordem é adequada quando um resultado depende de ambos os filhos, como no cálculo da altura. Em uma árvore de expressão, a posição do operador em relação aos operandos também explica as formas prefixa, infixa e pós-fixa.
Para entender a execução de emOrdem na figura, siga as chamadas: de 8 para 4, de 4 para 2; emita 2; volte e emita 4; visite 6; volte e emita 8; repita na subárvore de 12. O retorno da recursão preserva o ponto em que a subárvore foi interrompida. Por indução na estrutura da ABB, todo valor emitido pela esquerda é menor que a raiz e todo valor emitido pela direita é maior; logo a concatenação esquerda–raiz–direita fica crescente. Essa prova exige que a propriedade valha em todas as subárvores, e não apenas entre a raiz e seus filhos (Cormen et al., 2022).
O percurso por níveis tem outra disciplina: a fila contém nós descobertos e ainda não processados. Ao remover o primeiro nó e acrescentar seu filho esquerdo antes do direito, preservamos a ordem da esquerda para a direita em cada nível. Essa é uma aplicação de busca em largura. A fila pode atingir tamanho proporcional a n em uma árvore larga; na Figura 1, chega a conter as quatro folhas.
| Nó removido | Fila após acrescentar os filhos |
|---|---|
| 8 | 4, 12 |
| 4 | 12, 2, 6 |
| 12 | 2, 6, 10, 14 |
| 2 | 6, 10, 14 |
O início do traço mostra por que 12 é visitado antes de 2: ele já estava na fila quando os filhos de 4 foram acrescentados. Depois de 2, removem-se 6, 10 e 14, sem novas inserções.
Cada percurso visita cada nó uma vez, com tempo Θ(n) para n nós. Os percursos recursivos mantêm até h + 1 chamadas ativas, em que h é a altura medida em arestas; a fila do percurso por níveis pode guardar até a largura máxima da árvore (OpenDSA Project Contributors, 2023).
Métricas e operações auxiliares
Adotaremos a convenção altura em arestas: a altura da árvore vazia é −1 e a de uma folha é 0. Assim, altura(nó) = 1 + max(altura(esquerda), altura(direita)). A árvore da Figura 1 tem sete nós, quatro folhas e altura 2. A profundidade de 10 é 2; a altura da subárvore enraizada em 12 é 1. Há outras convenções que contam nós em vez de arestas, por isso é necessário declarar a unidade antes de comparar resultados (OpenDSA Project Contributors, 2024a).
| Nó | Profundidade | Altura da subárvore | Tamanho da subárvore |
|---|---|---|---|
| 8 | 0 | 2 | 7 |
| 4 e 12 | 1 | 1 | 3 cada |
| 2, 6, 10 e 14 | 2 | 0 | 1 cada |
A tabela evidencia que profundidade e altura medem direções opostas: ao descer até uma folha, a profundidade aumenta e a altura da subárvore diminui. Uma folha pode ter profundidade diferente de 2 em outra árvore, mas sua altura continua 0 nessa convenção.
O tamanho é 0 para árvore vazia e 1 + tamanho(esquerda) + tamanho(direita) para nó existente. A contagem de folhas vale 1 quando ambos os filhos são ausentes; nos demais casos, soma as folhas das subárvores. Uma operação de busca pode examinar esquerda e direita recursivamente em uma árvore binária comum, custando O(n) no pior caso. Em uma ABB, a comparação com a chave permite escolher apenas um lado; o custo passa a O(h + 1), que ainda pode ser O(n) se a árvore degenerar em uma cadeia (OpenDSA Project Contributors, 2023).
Recorrências, casos de borda e invariantes
As fórmulas recursivas têm dois componentes: um caso base para árvore vazia e uma combinação dos resultados dos filhos. A altura usa máximo porque procura o caminho mais longo; o tamanho usa soma porque todas as duas subárvores contribuem. A profundidade, ao contrário da altura, é medida a partir da raiz da árvore considerada até um nó específico. Para a árvore vazia, tamanho = 0, folhas = 0 e altura = −1; para um nó isolado, os valores são 1, 1 e 0. Fixar esses casos evita erros de uma unidade.
O teste de presença de uma chave é diferente de um percurso completo: ele pode parar quando encontra a primeira ocorrência. Em árvore binária geral, o pior caso ainda examina todos os nós. Em ABB de chaves distintas, chave < valor manda buscar à esquerda e chave > valor manda buscar à direita. A inserção segue as mesmas comparações até encontrar uma posição vazia; para preservar a propriedade de busca, não basta anexar um nó em qualquer posição. Remoção exige tratar separadamente folha, nó com um filho e nó com dois filhos, neste último caso substituindo a chave por predecessor ou sucessor e ajustando a ligação correspondente (Cormen et al., 2022). O código abaixo demonstra consulta estrutural geral; ele não implementa inserção nem remoção de ABB.
O programa C++17 abaixo constrói exatamente a árvore da figura, executa os quatro percursos, calcula as métricas e consulta a profundidade de uma chave. Os identificadores são distintos; profundidadeDe retorna −1 quando a chave não existe. std::unique_ptr cuida da liberação da memória ao final do programa.
#include <algorithm>
#include <iostream>
#include <memory>
#include <queue>
struct No {
int valor;
std::unique_ptr<No> esquerda;
std::unique_ptr<No> direita;
explicit No(int valor) : valor(valor) {}
};
void preOrdem(const No* no) {
if (no == nullptr) return;
std::cout << ' ' << no->valor;
preOrdem(no->esquerda.get());
preOrdem(no->direita.get());
}
void emOrdem(const No* no) {
if (no == nullptr) return;
emOrdem(no->esquerda.get());
std::cout << ' ' << no->valor;
emOrdem(no->direita.get());
}
void posOrdem(const No* no) {
if (no == nullptr) return;
posOrdem(no->esquerda.get());
posOrdem(no->direita.get());
std::cout << ' ' << no->valor;
}
void porNiveis(const No* raiz) {
if (raiz == nullptr) return;
std::queue<const No*> pendentes;
pendentes.push(raiz);
while (!pendentes.empty()) {
const No* atual = pendentes.front();
pendentes.pop();
std::cout << ' ' << atual->valor;
if (atual->esquerda) pendentes.push(atual->esquerda.get());
if (atual->direita) pendentes.push(atual->direita.get());
}
}
int tamanho(const No* no) {
if (no == nullptr) return 0;
return 1 + tamanho(no->esquerda.get()) + tamanho(no->direita.get());
}
int altura(const No* no) {
if (no == nullptr) return -1;
return 1 + std::max(altura(no->esquerda.get()), altura(no->direita.get()));
}
int folhas(const No* no) {
if (no == nullptr) return 0;
if (!no->esquerda && !no->direita) return 1;
return folhas(no->esquerda.get()) + folhas(no->direita.get());
}
int profundidadeDe(const No* no, int chave, int profundidade = 0) {
if (no == nullptr) return -1;
if (no->valor == chave) return profundidade;
int encontrada = profundidadeDe(no->esquerda.get(), chave, profundidade + 1);
if (encontrada != -1) return encontrada;
return profundidadeDe(no->direita.get(), chave, profundidade + 1);
}
int main() {
auto raiz = std::make_unique<No>(8);
raiz->esquerda = std::make_unique<No>(4);
raiz->direita = std::make_unique<No>(12);
raiz->esquerda->esquerda = std::make_unique<No>(2);
raiz->esquerda->direita = std::make_unique<No>(6);
raiz->direita->esquerda = std::make_unique<No>(10);
raiz->direita->direita = std::make_unique<No>(14);
std::cout << "Pré-ordem:"; preOrdem(raiz.get()); std::cout << '\n';
std::cout << "Em ordem:"; emOrdem(raiz.get()); std::cout << '\n';
std::cout << "Pós-ordem:"; posOrdem(raiz.get()); std::cout << '\n';
std::cout << "Por níveis:"; porNiveis(raiz.get()); std::cout << '\n';
std::cout << "Nós: " << tamanho(raiz.get()) << '\n';
std::cout << "Folhas: " << folhas(raiz.get()) << '\n';
std::cout << "Altura (arestas): " << altura(raiz.get()) << '\n';
std::cout << "Profundidade de 10: " << profundidadeDe(raiz.get(), 10) << '\n';
}A entrada está fixada na construção da árvore em main; não há leitura do teclado. A saída esperada é:
Pré-ordem: 8 4 2 6 12 10 14
Em ordem: 2 4 6 8 10 12 14
Pós-ordem: 2 6 4 10 14 12 8
Por níveis: 8 4 12 2 6 10 14
Nós: 7
Folhas: 4
Altura (arestas): 2
Profundidade de 10: 2Custos e limitações
Tamanho, altura e folhas calculados dessa forma percorrem toda a árvore: cada chamada custa Θ(n). Se muitas consultas forem feitas após cada alteração, pode valer a pena armazenar métricas nos nós, desde que inserções e remoções as atualizem corretamente. A busca geral também pode percorrer n nós. Uma ABB equilibrada reduz a altura a uma ordem logarítmica; a propriedade de busca, sozinha, não impede uma cadeia. Além disso, recursão profunda pode esgotar a pilha de chamadas; versões iterativas são apropriadas quando a altura pode ser muito grande.
Mais precisamente, para qualquer percurso completo, o trabalho obedece a T(n) = T(n_e) + T(n_d) + Θ(1), em que n_e + n_d = n − 1; daí T(n) = Θ(n), seja a árvore equilibrada ou não. O espaço adicional da recursão é Θ(h + 1), pois só uma cadeia de chamadas fica ativa por vez. Na árvore perfeita de altura h, a fila do percurso por níveis pode armazenar Θ(2^h) nós, isto é, Θ(n). Em uma cadeia, a fila armazena no máximo um nó. Essas cotas distinguem tempo de visita de memória de controle.
Não confunda “árvore completa” com “ABB”: a primeira descreve formato; a segunda, relação de ordem entre chaves. Tampouco conclua que uma ABB comum oferece busca O(log n) no pior caso. Essa garantia exige uma restrição de balanceamento ou outra organização que limite a altura. Segundo Cormen et al. (2022), a altura é decisiva para o custo das operações em estruturas de busca baseadas em árvores.
Síntese
Árvores binárias organizam nós por relações de pai, filho esquerdo e filho direito. As restrições estruturais explicam limites de altura e quantidade de nós, mas não impõem balanceamento. Pré-ordem, em ordem e pós-ordem diferem pelo momento de visitar o nó; o percurso por níveis usa uma fila. Tamanho, folhas, profundidade e altura descrevem aspectos diferentes da estrutura, e a convenção de altura precisa estar explícita. Uma ABB acrescenta uma regra de ordenação que permite buscar em apenas uma subárvore por etapa, com custo dependente da altura.
Referências
CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Introduction to algorithms. 4. ed. Cambridge, MA: MIT Press, 2022.
OPENDSA PROJECT CONTRIBUTORS. Binary trees. CNUCPSC270FA24 OpenDSA Data Structures and Algorithms, 2024a. Disponível em: https://opendsa-server.cs.vt.edu/ODSA/Books/cnu/cpsc270/fall-2024/TR_130/html/BinaryTree.html. Acesso em: 30 out. 2026.
OPENDSA PROJECT CONTRIBUTORS. Binary tree traversals. CNUCPSC270FA24 OpenDSA Data Structures and Algorithms, 2024b. Disponível em: https://opendsa-server.cs.vt.edu/ODSA/Books/cnu/cpsc270/fall-2024/TR_130/html/BinaryTreeTraversal.html. Acesso em: 30 out. 2026.
OPENDSA PROJECT CONTRIBUTORS. Binary search trees. OpenDSA Stand-alone Modules, 2023. Disponível em: https://opendsa-server.cs.vt.edu/ODSA/StandaloneModules/20231208151338/html/BST.html. Acesso em: 30 out. 2026.
WEISS, Mark Allen. Data structures and algorithm analysis in C++. 4. ed. [S. l.]: Pearson, 2014.
Atividade de fixação
Acrescente o nó 5 como filho esquerdo de 6 na árvore da Figura 1. Sem executar o programa, escreva as quatro novas sequências de percurso, o novo tamanho, a quantidade de folhas, a altura e a profundidade de 5. Explique por que a árvore continua sendo uma ABB e qual seria a resposta de profundidadeDe para uma chave ausente.