Definição indutiva de Árvores Binárias

Saber manipular uma estrutura de dados corretamente é imprescindível para qualquer programador. E com árvores binárias não pode ser diferente, principalmente quando nos deparamos com problemas cuja natureza exige uma  estrutura de dados não linear e que permita uma hierarquização dos dados que serão manipulados.

Indutivamente, podemos definir uma árvore binária T como sendo:

• Uma árvore vazia, ou
• Um nó especial r, chamado raiz de T, com duas subárvores Te e Td. Onde Te e Td são as subárvores esquerda e direita respectivamente.

Podemos tirar proveito da definição acima na hora de construir algoritmos que manipulam árvores. Para isso, basta assumir que o problema que desejamos resolver, já está resolvido para as subárvores esquerda e direita. Por exemplo, vamos supor que desejamos somar os valores armazenados em todos os vértices de uma árvore binária. Usando indução, a solução é a seguinte:

• Caso Base: a soma dos nós de uma árvore vazia é zero.
• Hipótese de Indução: assumimos que já temos a soma de todos os valores armazenados nas subárvores esquerda e direita.
• Caso Geral: é quase trivial, pois simplesmente somamos o valor armazenado na raiz com os valores que por hipótese de indução são as somas das subárvores esquerda e direita.

A implementação decorre "diretamente" do esquema apresentado acima:

• Implementação em C++

int somaNos(ARVORE t)
{
  if(t == NULL)
    return 0;
  else
    return t->info + somaNos(t->esq) + somaNos(t->dir); 
}