Caminhamento indutivo em Árvores Binárias

Neste post vamos construir indutivamente algoritmos que realizam os caminhamentos "pré-ordem", "em-ordem" e "pós-ordem" em árvores binárias. Tais algoritmos são similares, diferindo apenas na ordem em que as chamadas recursivas, que são representantes diretas da hipótese de indução, aparecem.

• Pré-Ordem: visita a raiz, em seguida a subárvore da esquerda e a subárvore da direita.
• Em-Ordem: visita a subárvore da esquerda, e em seguida a raiz e a subárvore da direita.
• Pós-Ordem: vista a subárvore da esquerda, e em seguida a subárvore da direita e a raiz.

O resultado dos caminhamentos aplicados a árvore acima são os seguintes:

• Pré-Ordem: A | B | D | E | C | F | G
• Em-Ordem: D | B | E | A | F | C | G
• Pós-Ordem: D | E | B | F | G | C | A

Agora vamos derivar o nosso algoritmo indutivamente.

Idéia indutiva

• Caso base: é trivial, pois não fazemos caminhamento em árvores binárias vazias.
• Hipótese de Indução: podemos assumir que já temos os caminhamentos das subárvores esquerda e direita.
• Caso Geral: Usando as respostas dadas pela hipótese de indução, basta definir quem será impresso/visitado primeiro. Seguindo o esquema dos três tipos de caminhamento apresentados acima.

As implementações são imediatas, pois já sabemos "o que fazer". A partir de agora nos preocuparemos com os detalhes de implementação.

Caminhamento pré-ordem

• Implementação em C++

void preOrdem(ARVORE *t)
{
  if(t != NULL)
  {
     cout << t->info << ' ';
     preOrdem(t->esq);
     preOrdem(t->dir);
  }
}

Caminhamento em-ordem

• Implementação em C++

void emOrdem(ARVORE *t)
{
  if(t != NULL)
  {
     emOrdem(t->esq);
     cout << t->info << ' ';
     emOrdem(t->dir);
  }
}

Caminhamento pós-ordem

• Implementação em C++

void posOrdem(ARVORE *t)
{
  if(t != NULL)
  {
     posOrdem(t->esq);
     posOrdem(t->dir);
     cout << t->info << ' ';
  }
}