Solução proposta para tarefa de 22.11

#include <stdio.h>
#include <stdlib.h>
#include "abb.h"

No *novoNo (int valor) {
// retorna null caso nao consiga alocar
 No *n;
 n= (No *) calloc (1, sizeof(No));
 if (n) n->valor=valor;
 return n;
}

Arvore * criaArvore() {
 Arvore * r;
 r = (Arvore * ) malloc(sizeof(Arvore));
 return r;
}

void imprimeNo(No * n) {
 printf("{%d, %d, %d} ", n->valor, n->altura, n->f);
}

void imprimeArvorePorNo(No * n, int nivel) {
 int i;
 if (n) {
  imprimeArvorePorNo(n->dir, nivel+1);
  for (i = 0; i < nivel; i++) {
   printf("           ");
  }
  imprimeNo(n);
  puts("");
  imprimeArvorePorNo(n->esq, nivel+1);
 }
}

void imprimeArvore(Arvore * A) {
 if ((A == NULL) || (A -> raiz == NULL)) {
  printf("arvore inexistente ou vazia.\n");
 } else {
  imprimeArvorePorNo(A->raiz, 0);
 }
}

void removeArvore(Arvore *A) { /* incompleto */
 free(A->raiz);
 free(A);
}
/*
No *buscaPorNo(Arvore *A, No *n, int valor) {
 int i;
 if ((n) && ( *n != 0)) { // ainda há onde buscar
    //printf ("%d ", *n);
  if ( *n == valor) return n; // achou
  else if ( *n < valor) return buscaPorNo(A, direita(A, n), valor);
  return buscaPorNo(A, esquerda(A, n), valor);
 }
 return NULL;
}


No *buscaNaArvore(Arvore *A, int valor) {
 if ((A == NULL) || (A->raiz == NULL)) {
  printf("arvore inexistente ou vazia.\n");
 } else {
  return buscaPorNo(&A->raiz, valor);
 }
}
*/

void calculaAlturaEF (No *n) {
 // dado que a altura dos filhos de n está correta, calcula a altura de n.
 int hd=-1;
 if (n->dir) hd=(n->dir)->altura;
 int he=-1;
 if (n->esq) he=(n->esq)->altura;

 n->altura=1+((hd>he)?hd:he);
 n->f=hd-he;
}


void inserePorNo(No **n, int valor) {
// como em insereNaArvore o caso da arvore vazia é tratado
// nao preciso me ocupar com ele aqui, mas preciso me ocupar se a posicao da folha nao
// existir
 if (*n==NULL) {
  *n= novoNo (valor);  // eh uma folha - altura zero e f==0 - foi criado com os valores certos.
  return;
 }
 if ((*n)->valor<valor) {
  inserePorNo(&((*n)->dir), valor);
 } else {
  inserePorNo(&((*n)->esq), valor);
 }

 // acerta campos altura e balanceamento do nó
 /*
 int hd=-1;
 if ((*n)->dir) hd=((*n)->dir)->altura;
 int he=-1;
 if ((*n)->esq) he=((*n)->esq)->altura;

 (*n)->altura=1+((hd>he)?hd:he);
 (*n)->f=hd-he;
 */
 calculaAlturaEF (*n);
}

void insereNaArvore(Arvore * A, int valor) {
 if (A == NULL) {
  printf("arvore inexistente.\n");
 } else {
  inserePorNo(&(A->raiz), valor);
 }
}

void rotacaoD (No **eixo) {
 No *e, *d;
 e=(*eixo)->esq;
 d=(*eixo)->dir;
 (*eixo)->esq=e->dir;
 e->dir=*eixo;
 calculaAlturaEF(*eixo);
 *eixo=e;
 calculaAlturaEF(*eixo);
}

void rotacaoE (No **eixo) {
 No *e, *d;
 e=(*eixo)->esq;
 d=(*eixo)->dir;
 if (!d) {
  puts ("Não há subarvore direita: não é possível rotacionar à esquerda.");
  return;
 }
 (*eixo)->dir=d->esq;
 d->esq=*eixo;
 calculaAlturaEF(*eixo);
 *eixo=d;
 calculaAlturaEF(*eixo);
}

void tentaBalancearPorNo(No **n) {
 if (*n==NULL) {
  // o pai tem um ou zero filhos. e este ramo é vazio.
  return;
 }
 tentaBalancearPorNo(&((*n)->dir));
 tentaBalancearPorNo(&((*n)->esq));

/*
 // acerta campos altura e balanceamento deste nó
 int hd=-1;
 if ((*n)->dir) hd=((*n)->dir)->altura;
 int he=-1;
 if ((*n)->esq) he=((*n)->esq)->altura;

 (*n)->altura=1+((hd>he)?hd:he);
 (*n)->f=hd-he;
 */
 calculaAlturaEF(*n);  // talvez seja desnecessario pois não houve nenhuma rotação na descida
 if ((*n)->f >1) {// subarvore da direita eh mais alta
  if (((*n)->dir) && ((*n)->dir->f<-1)) {// subarvore da esquerda do filho da direita eh mais alta
   puts ("rotação a direita em torno do filho da direita");
   rotacaoD(&((*n)->dir));
  }
  puts ("rotação a esquerda em torno do no");
  rotacaoE(n);
 }
 if ((*n)->f <-1) {// subarvore da esquerda eh mais alta
  if (((*n)->esq) && ((*n)->esq->f>1)) {// subarvore da direita do filho da esquerda eh mais alta
   puts ("rotação a esquerda em torno do filho da esquerda");
   rotacaoE(&((*n)->esq));
  }
  puts ("rotação a direita em torno do no");
  rotacaoD(n);
 }
}

void tentaBalancear(Arvore *A) {
 if (A == NULL) {
  printf("arvore inexistente.\n");
 } else {
  tentaBalancearPorNo(&(A->raiz));
 }
}