Percorrer uma árvore: em-ordem, pré-ordem e pós-ordem

Mais de uma ordem faz sentido

Percorrer uma lista não tem mistério: você anda do primeiro ao último e pronto. A árvore complica de um jeito interessante. Ao chegar num nó, você tem que decidir a ordem entre três coisas: visitar o próprio nó, mergulhar no ramo esquerdo e mergulhar no ramo direito. Não existe uma única ordem certa; existem escolhas, e cada escolha tem um nome e um uso. Os três percursos clássicos por profundidade combinam sempre esquerda antes de direita, mas mudam a posição do nó atual (a raiz do momento): ele pode ser visitado no meio, antes ou depois dos filhos. Só isso muda de um percurso para o outro, e essa pequena diferença gera resultados bem distintos.

Os nomes dizem tudo, se você prestar atenção à palavra ordem em cada um. Em-ordem: visita o esquerdo, depois a raiz (no meio), depois o direito. Pré-ordem: a raiz vem antes (pré) de tudo, depois esquerdo e direito. Pós-ordem: a raiz vem depois (pós) de tudo, primeiro esquerdo e direito, a raiz por último. O jeitinho de decorar é olhar onde a raiz aparece: no meio (em-ordem), no começo (pré) ou no fim (pós). Os filhos são sempre visitados esquerda antes de direita, então o que dança é apenas a raiz.

O percurso que devolve tudo ordenado

Um resultado bonito une esta aula à anterior. Se você fizer o percurso em-ordem numa árvore de busca binária, os valores saem em ordem crescente, do menor ao maior, de graça. O motivo é a regra da BST: como o lado esquerdo guarda os menores, visitá-lo antes da raiz garante que os menores venham primeiro; e como a direita guarda os maiores, deixá-la por último garante que os maiores venham no fim. Pegue a BST da aula passada (raiz 8, com 3 à esquerda tendo filhos 1 e 6, e 10 à direita). O em-ordem visita nesta sequência: 1, 3, 6, 8, 10. Ordenada, sem nenhum esforço extra de ordenação. É um dos motivos de a BST ser tão valorizada: ela mantém os dados prontos para sair em ordem a qualquer momento.

funcao emOrdem(no)
  se no e nulo então
    retorne
  fim
  emOrdem(no.esquerdo)   // 1º: mergulha à esquerda
  escreva(no.valor)       // 2º: visita a raiz (no meio)
  emOrdem(no.direito)    // 3º: mergulha à direita
fim
// numa BST, isto imprime os valores em ordem crescente

Em-ordem: esquerdo, raiz, direito. A recursão desce cada ramo; a raiz é impressa no meio. Numa BST, sai ordenado.

Cada percurso tem seu uso

Os três percursos não são só curiosidade acadêmica; cada um resolve um problema. O em-ordem, como vimos, lista os valores de uma BST em ordem, perfeito para imprimir dados ordenados ou gerar um relatório crescente. O pré-ordem visita a raiz antes dos filhos, o que é ideal para copiar ou salvar uma árvore: você grava o pai antes dos filhos, então na hora de reconstruir já tem onde pendurá-los. O pós-ordem visita a raiz por último, útil quando você precisa cuidar dos filhos antes do pai, como ao apagar uma árvore (libera os galhos antes de cortar o tronco) ou ao calcular o tamanho de pastas somando o conteúdo antes de fechar a pasta que as contém. Escolher o percurso é escolher a ordem que o seu problema pede.