Número de folhas em uma Árvore Binária

Neste post, vamos descrever indutivamente um algoritmo que calcula o número de folhas em uma árvore binária. Vamos novamente utilizar indução.

Descrição indutiva:

• Caso base: uma árvore binária vazia não possui folhas, uma árvore com apenas um nó, possui uma folha.
• Hipótese de indução: caso a árvore não seja vazia, podemos assumir que já temos a quantidade de folhas nas subárvores esquerda e direita. (isso mesmo, o número de folhas nas subárvores caíram do céu =) ).
• Caso Geral: é trivial, pois basta somar os valores encontrados pela hipótese de indução.

O algoritmo segue EXATAMENTE a ideia apresentada acima.

• Implementação em C++

int numFolhas(ARVORE *raiz){
  if(raiz == null)
    return 0;
  else
    if(raiz->esq == raiz->dir)
      return 1;
   else
      return numFolhas(raiz->esq) + numFolhas(raiz->dir);
}