Altura de Árvores Binárias: uma abordagem indutiva

Agora vamos criar um algoritmo que nos diz a altura de uma árvore binária. A altura de uma árvore binária pode ser definida como:

• Comprimento do maior caminho que vai da raiz até um nó folha. Onde o comprimento de um caminho é determinado pelo número de arestas que ele possui.

A árvore abaixo possui altura 3.

Para construir nosso algoritmo vamos mais uma vez recorrer a abordagem indutiva.

Idéia indutiva

• Caso Base: a altura de uma árvore vazia, ou com apenas um nó, é igual a zero.
• Hipótese de Indução: podemos assumir que já temos as alturas das subárvores esquerda e direita.
• Caso Geral: a altura da árvore será a maior dentre as alturas encontradas pela hipótese de indução mais 1.

A implementação a seguir decorre da idéia indutiva apresentada acima.

• Implementação em Python

def height(tree):
  if tree.left == tree.right: return 0   # arvore vazia
  if height(tree.left) > height(tree.right): return height(tree.left) + 1
  return height(tree.right) + 1

• Implementação em C++

int height(ARVORE *t){
  if(t == NULL || t->esq == t->dir)
    return 0;
  else
    return max(height(t->esq), height(t->dir)) + 1;
}