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

#define TAM_MAX 100  /* Tamanho máximo de uma string */

typedef struct RegAux {  /* Registro que representa nó em árvore binária */
  int info;                    
  struct RegAux *esq, *dir;
} RegArv, *ArvBin;

#define testanull(ap,fun) if ( (ap) == NULL ) { return; } 
/*
#define testanull(ap,fun) if ( (ap) == NULL ) { comAviso(AVS1,fun); return; } 
*/

/* Esta função deve inserir o valor da variável "valor"
   na árvore binária de busca representada pela variável
   "ab". Note que valores iguais devem ser inseridos
   sempre à direita. */
void InsereValor(ArvBin *ab, int valor) {
  testanull(ab,"InsereValor");

  if ( (*ab) == NULL ) { /* Arvore Vazia, Insira Aqui */
    (*ab) = (ArvBin) calloc(1,sizeof(RegArv));
    (*ab)->esq = (*ab)->dir = NULL;
    (*ab)->info=valor;
  } else {
    if ( valor < (*ab)->info )  /* Deve Ser Inserido à esquerda */
      InsereValor(&((*ab)->esq),valor);
    else 
      InsereValor(&((*ab)->dir),valor);
  }  
}



/* Esta função deve remover o valor da variável "valor"
   da árvore binária de busca representada pela variável
   "ab". Note que no caso de remoção de nó de grau 2,
   seu valor deve ser substituído pelo valor do
   menor sucessor. */
void RemoveValor(ArvBin *ab, int valor) {
  ArvBin tmp,aux;
  testanull(ab,"RemoveValor");

  if ( (*ab) == NULL ) /* Arvore Vazia, nao faz nada */
    return;
  else {
    
    if ( valor < (*ab)->info ) /* Desce pela Esquerda */
      RemoveValor(&((*ab)->esq),valor);
    else if (valor > (*ab)->info ) /* Desce pela Direita */
      RemoveValor(&((*ab)->dir),valor);
    else { /* Achou! Remova */
      
      if ( ((*ab)->dir != NULL) && ((*ab)->esq == NULL) ) {
	tmp = (*ab);
	*ab = (*ab)->dir;
	free(tmp);
	tmp=NULL;
      } else if ( ((*ab)->esq != NULL) && ((*ab)->dir == NULL) ) {
	tmp = (*ab);
	*ab = (*ab)->esq;
	free(tmp);
	tmp=NULL;
      } else if ( ((*ab)->esq != NULL) && ((*ab)->dir != NULL) ) {
	/* Anda para a direita 1 vez e desce pela esquerda até o fim */
	tmp = (*ab)->dir;
	if (tmp->esq != NULL) { /* troca o mais à esq com a raiz */
	  while ( tmp->esq->esq != NULL)
	    tmp = tmp->esq;
	  (*ab)->info = tmp->esq->info;
	  aux = tmp->esq;
	  tmp->esq = tmp->esq->dir;
	} else { /* Faz o da Direita ser o pai */
	  aux = *ab;
	  tmp->esq = (*ab)->esq;
	  *ab = tmp;
	}
	free(aux);
	aux = NULL;
      } else if ( ((*ab)->esq == NULL) && ((*ab)->dir == NULL) ) { /* Nao Tem filhos */
	free(*ab);
	*ab = NULL;
      }
    }
  }
} 

/* Esta função deve percorrer a árvore ab em
   pré-ordem e gerar uma cadeia de caracteres s
   com os valores visitados em pré-ordem separados
   por um espaço em branco. */
void VisitaPreOrdem(ArvBin ab, char **s) {
  if (ab == NULL) return;
  sprintf(*s,"%s%i ",*s,ab->info);
  if(ab->esq!=NULL) VisitaPreOrdem(ab->esq,s);
  if(ab->dir!=NULL) VisitaPreOrdem(ab->dir,s);
  return;
}


/* Esta função deve percorrer a árvore ab em in-ordem e
   gerar uma cadeia de caracteres s com os
   valores visitados em in-ordem separados por um
   espaço em branco. */
void VisitaInOrdem(ArvBin ab, char **s) {
  if (ab == NULL) return;
  if(ab->esq!=NULL) VisitaInOrdem(ab->esq,s);
  sprintf(*s,"%s%i ",*s,ab->info);
  if(ab->dir!=NULL) VisitaInOrdem(ab->dir,s);
  return;
}

/* Esta função deve percorrer a árvore ab em
   pós-ordem e gerar uma cadeia de caracteres s
   com os valores visitados em pós-ordem separados
   por um espaço em branco. */
void VisitaPosOrdem(ArvBin ab, char **s) {
  if (ab == NULL) return;
  if(ab->esq!=NULL) VisitaPosOrdem(ab->esq,s);
  if(ab->dir!=NULL) VisitaPosOrdem(ab->dir,s);
  sprintf(*s,"%s%i ",*s,ab->info);
  return;
}

/* Esta função deve calcular e retornar o
   número de nós da árvore ab */
int  NumerodeNos(ArvBin ab) {
  int resultado=0;
  
  if (ab == NULL) return 0;
  resultado = NumerodeNos(ab->esq);
  resultado++; /* Conta o nó atual */
  resultado += NumerodeNos(ab->dir);
  return resultado;
}

/* Esta função deve calcular e retornar a
   altura da árvore ab */
int  Altura(ArvBin ab) {
  int esq=0 , dir=0;

  if (ab == NULL) return 0;

  esq = Altura(ab->esq);
  dir = Altura(ab->dir);
  
  return ( 1 + ((esq > dir) ? esq : dir));
}


/* Esta função deve calcular os k maiores valores
   armazenados na árvore ab e retorná-los em
   ordem decrescente e separados por um espaço em
   branco na cadeia de caracteres s */
void MaioresValores(ArvBin ab, char **s, int *k) {
  testanull(s,"MenoresValores");

  if (ab == NULL) return;

  if (*k < 1) return;

  /* Desce até o maior elemento da (sub)arvore */
  MaioresValores(ab->dir,s,k);
  if (*k < 1) return;
  sprintf(*s,"%s%d ",*s,ab->info);
  (*k)--;
  if (*k < 1) return;
  MaioresValores(ab->esq,s,k);
  
  return;
}


/* Esta função deve calcular os k
   menores valores armazenados na
   árvore ab e retorná-los em
   ordem crescente e separados por um
   espaço em branco na cadeia de
   caracteres s */
void MenoresValores(ArvBin ab, char **s, int *k) {
  testanull(s,"MenoresValores");

  if (ab == NULL) return;

  if (*k < 1) return;

  /* Desce até o menor elemento da (sub)arvore */
  MenoresValores(ab->esq,s,k);
  if (*k < 1) return;
  sprintf(*s,"%s%d ",*s,ab->info);
  (*k)--;
  if (*k < 1) return;
  MenoresValores(ab->dir,s,k);
  
  return;
}

/* Esta função supõe que a árvore ab armazena
   apenas valores não negativos. Ela deve
   calcular o maior valor n armazenado na árvore
   e criar um vetor de freqüência f de
   tamanho n+1. Depois ela deve calcular e
   armazenar em f[i] o número de ocorrências
   do valor i na árvore ab. Por fim, ela deve
   retornar o vetor f e seu tamanho n+1. */
void Frequencia(ArvBin ab, int **f, int *n) {
  char *s;
  char saida[TAM_MAX], tmp[20];
  int num;
  ArvBin aux;

  if (ab == NULL) return;

  aux = ab;
  s=saida;

  while ( aux->dir != NULL)
    aux=aux->dir;
  /* Acha o maior numero */
  *n = aux->info + 1;
  
  /* Aloca o vetor */
  if (*f != NULL)
    free(*f);
  *f = (int*) calloc(*n,sizeof(int));

  /* Serviu para alguma coisa esta porcaria */
  *s='\0';
  VisitaPreOrdem(ab,&s);

  while ( *s != '\0' ) { 
    strcpy(tmp,"");
    while (*s != ' ') {
      sprintf(tmp,"%s%c",tmp,*s);
      s++;
    }
    num = atoi(tmp);
    ((*f)[num])++;
    s++;
  }
  
  return;
}


/* Esta função deve remover da árvore ab todos os valores
   repetidos deixando apenas uma ocorrência de cada valor. */
void EliminaRepetidos(ArvBin *ab) {
  int *f=NULL, n, i,j;

  if (*ab == NULL) return;

  /* Serviu para alguma coisa esta porcaria */
  Frequencia(*ab,&f,&n);

  for (i=0; i < n; i++)
    for (j=1; j < f[i]; j++)
      RemoveValor(ab,i);

  free(f);
}


/* Esta função deve liberar todo espaço
   de memória alocado para a árvore */
void LiberaArvore(ArvBin *ab) {
  testanull(ab,"LiberaArvore");

  if ( (*ab) != NULL ) {
    if ( (*ab)->esq != NULL )
      LiberaArvore(&((*ab)->esq));
    if ( (*ab)->dir != NULL )
      LiberaArvore(&((*ab)->dir));
    free(*ab);
  }
}









/* author: Gustavo Sverzut Barbieri (http://www.gustavobarbieri.com.br) */