RESOLUÇÃO DA QUESTÃO EXTRA MAC 122 — B.C.C.

Para calcular o valor a ser armazenado no campo bal precisamos saber o valor da altura dos filhos esquerdo e direito do nó sendo analisado. Reparemos que a altura não é esse valor no campo bal.

A idéia para resolver esta questão é fazer a função retornar a altura de cada nó. Aqui usamos a convenção de que a altura da árvore vazia é igual a −1. Mas se fosse

utilizada altura igual a zero, a função também funcionaria, pois o que nos interessa é a diferença entre as alturas das sub-árvores filhas.

int calcula_balanco (No * raiz)
{
  int ae,       /* altura da sub-arvore esquerda  */
      ad,       /* altura da sub-arvore direita   */
      altura;   /* altura do nó apontado por raiz */
  if (raiz == NULL)
    altura = -1;
  else {
    ae = calcula_balanco (raiz->f_esq);
    ad = calcula_balanco (raiz->f_dir);
    raiz->bal = ae - ad;
    altura = 1 + (ae > ad ? ae : ad);
  }
  return altura;
}