codigo da aula de 08.11.2016

/******************************************************************************/
/*              Este programa gerencia arvores AVL                            */
/*  Arvores AVL sao arvores balanceadas na altura.                            */
/*  O nome AVL vem de seus criadores Adelson Velsky e Landis, cuja primeira   */
/*    referência encontra-se no documento "Algoritmos para organização da     */
/*    informação" de 1962.                                                    */
/******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define true 1
#define false 0

//typedef int int;
typedef int TIPOCHAVE;
typedef struct aux {
 TIPOCHAVE chave;
 struct aux *esq;
 struct aux *dir;
 int bal; // fator de balanceamento (0, -1 ou +1) => altura direita - altura esquerda
} NO, *PONT;

/* cria um novo (aloca memoria e preenche valores) no com chave=ch e retorna 
       seu endereco */

PONT criarNovoNo(TIPOCHAVE ch){
 PONT novoNo = (PONT)malloc(sizeof(NO));
 novoNo->esq = NULL;
 novoNo->dir = NULL;
 novoNo->chave = ch;
 novoNo->bal = 0;
 return novoNo;
}

// Retorna o maior valor entre dois inteiros
int max(int a, int b){
 if (a>b) return a;
 return b;
}

// Retorna a altura de uma (sub-)arvore
int altura(PONT p){
 if (!p) return 0;
 else return 1 + max(altura(p->esq),altura(p->dir));
}

/* Exibe arvore Em Ordem         */
void exibirArvoreEmOrdem(PONT raiz){
 if (raiz == NULL) return;
 exibirArvoreEmOrdem(raiz->esq);
 printf("%d ",raiz->chave);
 exibirArvoreEmOrdem(raiz->dir);
}


/* Exibe arvore Pre Ordem         */
void exibirArvorePreOrdem(PONT raiz){
 if (raiz == NULL) return;
 printf("%d ",raiz->chave);
 exibirArvorePreOrdem(raiz->esq);
 exibirArvorePreOrdem(raiz->dir);
}

/* Exibe arvore Pos Ordem         */
void exibirArvorePosOrdem(PONT raiz){
 if (raiz == NULL) return;
 exibirArvorePreOrdem(raiz->esq);
 exibirArvorePreOrdem(raiz->dir);
 printf("%d ",raiz->chave);
}

/* Exibe arvore Em Ordem (com parenteses para os filhos)    */
void exibirArvore(PONT raiz){
 if (raiz == NULL) return;
 printf("%d[%d]",raiz->chave,raiz->bal);
 printf("(");     
 exibirArvore(raiz->esq);
 exibirArvore(raiz->dir);
 printf(")");     
}

/* Exibe arvore Pre-Ordem indicando pai de cada no    */
void exibirArvore2(PONT raiz, TIPOCHAVE chavePai){
 if (raiz == NULL) return;
 printf("(%d,%d) ",chavePai,raiz->chave);
 exibirArvore2(raiz->esq,raiz->chave);
 exibirArvore2(raiz->dir,raiz->chave);
}

// Verifica se árvore é AVL
int ehAVL(PONT p){
 int e,d;
 int ok = true;
 if(p){
  ok = ehAVL(p->esq);
  if(ok) ok = ehAVL(p->dir);
  if(ok){
   e = altura(p->esq);
   d = altura(p->dir);
   if(abs(e-d) <= 1) ok = true;  
   else ok = false;
  }
 }
 return(ok);
}

// Verifica se árvore é AVL
int ehAVL2(PONT p, int* alt){
    if (!p){
       *alt=0;
       return true;
    }
    int res;
    int d, e;
 res = ehAVL2(p->dir,&d);
 if (!res) return false;
 res = ehAVL2(p->esq,&e);
    if (!res) return false;
    if ((d-e<-1) || (d-e>1)) return false;
 *alt = max(d,e)+1; 
 return true; 
}

int atualizarBalanceamentoTotal(PONT raiz){
 if (!raiz) return 0;
 int d = atualizarBalanceamentoTotal(raiz->dir);
 int e = atualizarBalanceamentoTotal(raiz->esq);
 raiz->bal = d-e;
 return max(d,e)+1;
}

// Rotações à direita (LL e LR)
void rotacaoL(PONT *p){
 printf("Rotacao a esquerda, problema no no: %d\n",(*p)->chave);
 PONT u, v;
 u = (*p)->esq;
 if(u->bal == -1) {   // LL
  (*p)->esq = u->dir;
  u->dir = *p;
  (*p)->bal = 0;
  *p = u;
 } else {  // LR
  v = u->dir;
  u->dir = v->esq;
  v->esq = u;
  (*p)->esq = v->dir;
  v->dir = *p;
  if(v->bal == -1)(*p)->bal = 1;
  else (*p)->bal = 0;
  if(v->bal == 1) u->bal = -1;
  else u->bal = 0;
  *p = v;
 }
 (*p)->bal = 0; // balanço final da raiz (p) da subarvore
}

// Rotações à esquerda (RR e RL)
void rotacaoR(PONT *p){
 printf("Rotacao a direita, problema no no: %d\n",(*p)->chave);
 PONT u, v;
 u = (*p)->dir;
 if(u->bal == 1) {   // RR
  (*p)->dir = u->esq;
  u->esq = *p;
  (*p)->bal = 0;
  *p = u;
 } else {  // RL
  v = u->esq;
  u->esq = v->dir;
  v->dir = u;
  (*p)->dir = v->esq;
  v->esq = *p;
  if(v->bal == -1)(*p)->bal = 1;
  else (*p)->bal = 0;
  if(v->bal == 1) u->bal = -1;
  else u->bal = 0;
  *p = v;
 }
 (*p)->bal = 0; // balanço final da raiz (p) da subarvore
}

// Inserção AVL: p é inicializado com raiz e *alterou com false
// O retorno da função é o nó inserido, mas não precisa ser usado em main()

void inserirAVL(PONT *pp, TIPOCHAVE ch, int *alterou){
 PONT p = *pp;
 if(!p){
  *pp = criarNovoNo(ch);
  *alterou = true;
  //else printf("Criando no %d, filho de %d", ch, (*raiz)->chave);
 } else {
  if(ch < p->chave) {
            inserirAVL(&(p->esq), ch, alterou);
   if(*alterou)
    switch (p->bal) {
    case 1 : p->bal = 0;
    *alterou = false;
    break;
    case 0 : p->bal = -1;
    break;
    case -1: rotacaoL(pp);
    *alterou = false;
    break;
    }
  } else {
   inserirAVL(&(p->dir), ch, alterou);
   if(*alterou)
    switch (p->bal) {
    case -1: p->bal = 0;
    *alterou = false;
    break;
    case 0 : p->bal = 1;
    break;
    case 1 : rotacaoR(pp);
    *alterou = false;
    break;
    }
  }
 }
}

/* retorna o endereco do NO que contem chave=ch ou NULL caso a chave nao seja
       encontrada. Utiliza busca binaria recursiva                                */
PONT buscaBinaria(TIPOCHAVE ch, PONT raiz){
 if (raiz == NULL) return NULL;
 if (raiz->chave == ch) return raiz;
 if (raiz->chave<ch) 
  return buscaBinaria(ch,raiz->dir);
 return buscaBinaria(ch,raiz->esq);
}  

// Busca binária não recursiva devolvendo o nó pai
PONT buscaNo(PONT raiz, TIPOCHAVE ch, PONT *pai){
 PONT atual = raiz;
 *pai = NULL;
 while (atual) {
  if(atual->chave == ch)
   return(atual);
  *pai = atual;
  if(ch < atual->chave) atual = atual->esq;
  else atual = atual->dir;
 }
 return(NULL);
}

/* funcao auxiliar na destruicao (liberacao da memoria) de uma arvore */
void destruirAux(PONT subRaiz){
 if (subRaiz){
  destruirAux(subRaiz->esq);
  destruirAux(subRaiz->dir);
  free(subRaiz);
 }
}

/* libera toda memoria de uma arvore e coloca NULL no valor da raiz    */
void destruirArvore(PONT * raiz){
 destruirAux(*raiz);
 *raiz = NULL;
}

/* inicializa arvore: raiz=NULL */
void inicializar(PONT * raiz){
 *raiz = NULL;
}

void travessiaAux(PONT p, int *niv, TIPOCHAVE ch, int *achou) {
 if(p) {
  (*niv)++;// *niv = *niv + 1;
  if(p->chave == ch) *achou = true;
  else {
   travessiaAux(p->esq, niv, ch, achou);
   if(!(*achou)) travessiaAux(p->dir, niv, ch, achou);
   if(!(*achou)) *niv = *niv - 1;
  }
 }
}

/* Retorna true e o nivel de uma chave (caso seja encontrada) e false caso 
contrario.                                                                */
int travessia(PONT p, int *niv, TIPOCHAVE ch) {
 *niv = 0;
 PONT temp = buscaBinaria(ch,p);
 if (temp){
  int achou = false;
  travessiaAux(p, niv, ch, &achou);
  return true;
 }
 else return false;
}

void verificaEhAVL(PONT l){
     if (ehAVL(l)) printf("Arvore eh AVL.\n");
     else printf("PROBLEMA: a arvore nao eh mais AVL.\n");
}

void inserir(PONT *l, int x){
  TIPOCHAVE ch = x;
  //scanf("%d",&ch);
  int alterou;
  inserirAVL(l,ch,&alterou);
  printf("Elemento %d inserido corretamente.\n",ch);
}

void buscar(NO *l){
  TIPOCHAVE ch;
  scanf("%d",&ch);
  PONT posicao = buscaBinaria(ch,l);
  if (posicao != NULL) printf("Elemento %d encontrado no endereco %d.\n",ch,posicao);
  else printf("Nao foi possivel encontrar elemento %d.\n",ch);
}

void usaTravessia(NO *l){
  TIPOCHAVE ch;
  scanf("%d",&ch);
  int niv;
  if (travessia(l, &niv, ch)) printf("Elemento %d encontrado no nivel %d.\n",ch,niv);
  else printf("Nao foi possivel encontrar elemento %d.\n",ch);
}

void exibirEmOrdem(NO *l){
   printf("Em ordem: ");
   exibirArvoreEmOrdem(l); printf("\n");
}

void exibirArvoreP(NO *l){
   exibirArvore(l); printf("\n");
}

void exibirArvoreX(NO *l){
   printf("Arvore AVL: ");
   exibirArvore2(l,-1); printf("\n");
}

void exibirPreOrdem(NO *l){
   printf("Pre ordem: ");
   exibirArvorePreOrdem(l); printf("\n");
}

void exibirPosOrdem(NO *l){
   printf("Pos ordem: ");
   exibirArvorePosOrdem(l); printf("\n");
}

void help(){
  printf("Comandos validos: \n");
  printf("   i <chave1>: inserir elemento com chave=chave1\n");
  printf("   d : destruir (zerar) NO\n");
  printf("   h : exibir esta mensagem de ajuda\n");
  printf("   b <chave1>: exibir endereco do elemento com chave=chave1\n");
  printf("   0 : exibir arvore EM ordem.\n");
  printf("   1 : exibir arvore PRE-ordem.\n");
  printf("   2 : exibir arvore POS-ordem.\n");
  printf("   3 : exibir arvore parenteses.\n");
  printf("   9: verifica se arvore eh AVL.\n");
}

void destruir(PONT *l){
     destruirArvore(l);
     printf("Arvore zerada (toda memoria liberada).\n");
}

void removerf (PONT* pp, int ch/*, int *alterou*/){
    PONT l=*pp;
   // inserirAVL(&(p->esq), ch, alterou);
if(ch  < l->chave){
    removerf(&(l->esq), ch);
}
if(ch  > l->chave){
    removerf(&(l->dir), ch);
}
    if(ch  ==l->chave){
   free(l);
}else {
   printf("nao encontrou");
}
}

void imprimeArvorePorNo (PONT n, int altura) {
    int i;
    if (n) {
     imprimeArvorePorNo (n->dir, altura+1);
      for (i=0;i<altura;i++) {
       printf ("      ");
      }
       printf ("%04d ", n->chave);
      puts ("");
    imprimeArvorePorNo (n -> esq, altura+1);
    }
}

void imprimeArvore (PONT raiz) {
  if  (raiz==NULL){
    printf ("arvore inexistente ou vazia.\n");
  } else {
    imprimeArvorePorNo( raiz, 0);
  }
}

/*
int main()`
  PONT raiz;
  inicializar(&raiz);
  help();
  char comando = ' ';
  scanf("%c",&comando);
  while (comando != 'q'){
    switch (comando) {
      case 'i' : inserir(&raiz); break;
      case 'd' : destruir(&raiz); break;
      case 'h' : help(); break;
      case 'b' : buscar(raiz); break;
      case '0' : exibirEmOrdem(raiz); break;
      case '1' : exibirPreOrdem(raiz); break;
      case '2' : exibirPosOrdem(raiz); break;
      case '3' : exibirArvoreP(raiz); break;
      case '5' : exibirArvoreX(raiz); break;
      case '9' : verificaEhAVL(raiz); break;
      default: {while (comando != '\n') scanf("%c",&comando);};
    } 
    scanf("%c",&comando);
  }
  return 0;
}
 */

 int main () {
     printf ("hello\n"); //void inserirAVL(PONT *pp, TIPOCHAVE ch, int *alterou)
     PONT raiz;
     inicializar(&raiz);
     inserir(&raiz, 679);
  inserir(&raiz, 279);
     inserir(&raiz, 879);
     inserir(&raiz, 600);
     inserir(&raiz, 9);
     inserir(&raiz, 79);
     inserir(&raiz, 3679);
     inserir(&raiz, 6279);
      //removerf(&raiz,9);
     exibirEmOrdem(raiz);
     removerf(&raiz,6279);
   imprimeArvore (raiz);
     exibirArvoreX(raiz);
     printf ("hello\n");
}