Árvore binária de busca: percursos pré, em e pós-ordem

Árvores são a estrutura de dados preferida das bancas para exercícios de simulação: dá-se uma sequência de inserção e pede-se o resultado de um percurso. O raciocínio é mecânico, e quem o domina acerta quase todas. Este guia monta uma árvore passo a passo e confere os percursos; as saídas foram obtidas executando o código em um teste.

Vocabulário essencial

Nó: elemento da árvore, com um valor.
Raiz: o nó do topo, sem pai.
Folha: nó sem filhos.
Filho esquerdo e direito: numa árvore binária, cada nó tem no máximo dois filhos.
Subárvore: um nó com todos os seus descendentes.
Altura: contada em arestas, é o maior caminho da raiz a uma folha; contada em níveis (ou nós), é uma unidade maior. Há divergência entre autores, por isso o enunciado precisa dizer a convenção usada. Quando não diz, confira a bibliografia da banca.

A regra da árvore binária de busca

Numa árvore binária de busca (ABB), para todo nó, os valores da subárvore esquerda são menores que o valor do nó, e os da direita são maiores (a questão deve dizer o que fazer com iguais; aqui não há repetidos). Para inserir um valor: parta da raiz, vá à esquerda se for menor e à direita se for maior, até achar uma posição vazia.

Montando a árvore

Sequência de inserção: 50, 30, 70, 20, 40, 60, 80, 35.

50 vira a raiz.
30 < 50: filho esquerdo de 50.
70 > 50: filho direito de 50.
20 < 50, < 30: filho esquerdo de 30.
40 < 50, > 30: filho direito de 30.
60 > 50, < 70: filho esquerdo de 70.
80 > 50, > 70: filho direito de 70.
35 < 50, > 30, < 40: filho esquerdo de 40.

Resultado:

Nó	Filho esquerdo	Filho direito
50	30	70
30	20	40
70	60	80
40	35	nenhum
20, 60, 80, 35	nenhum	nenhum

As folhas são 20, 35, 60 e 80.

Os percursos

Nos percursos em profundidade, a diferença é o momento de visitar a raiz de cada subárvore:

Percurso	Ordem	Resultado neste exemplo
Pré-ordem	raiz, esquerda, direita	50, 30, 20, 40, 35, 70, 60, 80
Em ordem	esquerda, raiz, direita	20, 30, 35, 40, 50, 60, 70, 80
Pós-ordem	esquerda, direita, raiz	20, 35, 40, 30, 60, 80, 70, 50
Por nível (largura)	nível a nível, da esquerda para a direita	50, 30, 70, 20, 40, 60, 80, 35

Observações importantes:

O percurso em ordem de uma ABB produz os valores em ordem crescente. É a propriedade mais cobrada: se o percurso em ordem não saiu ordenado, a árvore não é uma ABB.
A pré-ordem começa pela raiz; a pós-ordem termina nela. Isso permite conferir rápido: o primeiro da pré-ordem e o último da pós-ordem são sempre a raiz (50).
O percurso por nível usa uma fila, enquanto os percursos em profundidade usam recursão (ou uma pilha). Veja as duas estruturas em pilha, fila e lista.

Uma dica para escrever os percursos sem se perder: percorra o contorno da árvore com o dedo. Na pré-ordem, anote o nó na primeira vez em que passa por ele (pela esquerda); na em ordem, quando passa por baixo; na pós-ordem, pela última vez (pela direita).

Altura e o caso degenerado

A árvore do exemplo tem 4 níveis (50; 30 e 70; 20, 40, 60 e 80; e 35), ou seja, altura 3 se contada em arestas. Com 8 nós, essa forma é bem equilibrada.

Mas a ordem de inserção importa. Inserindo 10, 20, 30, 40, 50 (já ordenados), cada valor é maior que todos os anteriores e vai sempre para a direita: a árvore vira uma lista encadeada, com 5 níveis para 5 nós. O percurso em ordem continua correto (10, 20, 30, 40, 50), mas a busca perde a vantagem. Em árvore equilibrada, a busca custa O(log n); no caso degenerado, O(n). Para evitar o problema existem árvores auto-balanceadas, como a AVL e a rubro-negra, que reorganizam os nós a cada inserção.

Remoção em ABB, em linhas gerais

Remover uma folha: basta cortá-la.
Remover nó com um filho: o filho ocupa o lugar do nó.
Remover nó com dois filhos: substitui-se o valor pelo seu sucessor em ordem (o menor da subárvore direita) ou pelo antecessor (o maior da esquerda), e remove-se esse nó, que cai num dos casos anteriores.

Como resolver na prova

Desenhe a árvore inserindo um valor por vez, sempre da raiz.
Confira se a regra esquerda menor, direita maior vale em todo nó.
Escreva o percurso pedido usando a ordem do quadro acima.
Confira o resultado: em ordem deve sair crescente; a raiz deve ser o primeiro da pré-ordem e o último da pós-ordem.

Erros comuns

Inserir no primeiro lugar vazio da esquerda para a direita (isso é árvore completa por nível, não ABB).
Confundir pré-ordem com pós-ordem.
Esquecer que a árvore depende da ordem de inserção.
Calcular altura sem checar se o enunciado conta arestas ou níveis.
Dizer que toda árvore binária é de busca.

Fontes e atualização

Não há norma oficial brasileira sobre estruturas de dados; o conteúdo segue a literatura clássica. Os percursos foram conferidos executando o código com a sequência indicada. Convenções de altura e de tratamento de valores repetidos variam: confira o enunciado e o edital.

Próximos passos

Compare com a busca em busca sequencial e binária e Big O.
Revise ordenação: bubble, selection e insertion.
Veja o uso de índices em bancos de dados: chaves, normalização, SQL e transações.