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

typedef struct no {
  int conteudo;
  struct no *esq,
            *dir;
} Arvore;



/*################################################################################
	Função que remove da árvore binária os múltiplos do valor informado pelo usuário
	################################################################################*/

Arvore *deletaArvore(Arvore *raiz, int conteudo) {
  Arvore *p, *p2;

  if (!raiz) return raiz; //arvore vazia, logo conteudo nao encontrado

  if (raiz->conteudo == conteudo) { //apagar a raiz
    //isso significa uma arvore vazia
    if (raiz->esq == raiz->dir) {
      free(raiz);
      return NULL;
    } else if (raiz->esq == NULL) { //ou se uma subarvore é nula
      p = raiz->dir;
      free(raiz);
      return p;
    } else if (raiz->dir == NULL) {
      p = raiz->esq;
      free(raiz);
      return p;
    }
		else {  //ou as duas subarvores estao presentes
      p2 = raiz->dir;
      p = raiz->dir;
      while (p->esq)
        p = p->esq;
      p->esq = raiz->esq;
      free(raiz);
      return p2;
    }
  }
  if (raiz->conteudo < conteudo)
			raiz->dir = deletaArvore(raiz->dir, conteudo);
  else
  		raiz->esq = deletaArvore(raiz->esq, conteudo);


  return raiz;
}

/*###############################################################################
	#######Função que percorre a árvore e verifica se o valor é múltiplo###########
	##############################################################################*/

Arvore *deletaMultiplo(Arvore *raiz, Arvore *r, int conteudo, int nivel) {

  if (!raiz)
		return r;

	deletaMultiplo(raiz->dir, r, conteudo, nivel + 1);
  if(raiz->conteudo%conteudo==0);
   	r = deletaArvore(r, nivel);
	  deletaMultiplo(raiz->esq, r, conteudo, nivel + 1);

}

/*###############################################################################
	#########################Função que exibe a árvore binária#####################
	##############################################################################*/

void imprimeArvore(Arvore *raiz, int nivel) {
  int i;

  if (!raiz) return; //como eh procedimento, soh retorna o controle para o main()
  imprimeArvore(raiz->dir, nivel + 1);
  for (i = 0; i < nivel; ++i)
    printf("  ");
  printf("%d\n", raiz->conteudo);
  imprimeArvore(raiz->esq, nivel + 1);
}

/*###############################################################################
	#######################Função de inserção na árvore binária####################
	##############################################################################*/

Arvore *insereNaArvoreBinaria(Arvore *raiz, Arvore *r, int conteudo) {
  if (!r) { //se r for NULO
    r = (Arvore *)malloc(sizeof(Arvore)); //alocação de memoria
    if (!r) { // se ao alocar não existir memoria, o programa é finalizado
      printf("\n\nSEM MEMORIA!! Programa finalizado!\n");
      exit(0);
    }
    r->esq = NULL;
    r->dir = NULL;
    r->conteudo = conteudo;

    if (!raiz) {
      printf("\nPrimeira inserção...Raiz principal!!\n");
      return r; //retorna a primeira inserção
    }
    if (conteudo == raiz->conteudo) {//verificando se o valor já existe na árvore
      printf("\nValor já existente na árvore\n");
      return ;//retorna para o menu
    }
    else if (conteudo < raiz->conteudo)
						raiz->esq = r;
    else raiz->dir = r;

    return r;
  }
  if (conteudo == r->conteudo){//verificando se o valor já existe na árvore
      printf("\nValor já existente na árvore\n");
      return ;
    }
    //se valor a ser inserido for menor que a raiz, valor é inserido à esquerda
  else if (conteudo < r->conteudo) {
    printf("\nDescendo para esquerda\n");
    insereNaArvoreBinaria(r, r->esq, conteudo);//chama a recurção lado esquerdo
  }
  	 //se valor a ser inserido for maior que a raiz, valor é inserido à direita
  else {
    printf("\nDescendo para direita\n");
    insereNaArvoreBinaria(r, r->dir, conteudo);//chama a recurção lado direito
  }
}

int main() {
  Arvore *arvore;
  char op;
  int conteudo, i, qtdNos;

  srand(time(NULL));

  //recebe do usuario a quantidade de elementos a serem inserido na arvore
  arvore = NULL;

  do {
    system("cls");
    printf("Menu de opcoes para arvore binaria de pesquisa BALANCEADA (AVL)\n\n\n");
    printf("1  - Gera arvore aleatoriamente\n");
    printf("2  - Exibir arvore\n");
    printf("3  - Remove elemento da arvore\n");
    printf("4  - Sair\n\n\n");
    printf("Opcao: ");
    op = getchar();
    fflush(stdin);

    switch (op) {
      case '1' : printf("Gerando arvore aleatoriamente ...\n");
                 printf("Digite a quantidade de nos para a arvore: ");
                 scanf("%d", &qtdNos);
                 fflush(stdin);
                 //laço que gera números randomicamente à serem inseridos na árvore
                 for (i = 1; i <= qtdNos; i++) {
                   conteudo = rand() % 100;
                   if (!arvore)//se arvore for igual a NULL
									 	arvore = insereNaArvoreBinaria(arvore, arvore, conteudo);
                   else insereNaArvoreBinaria(arvore, arvore, conteudo);
                 }
                 printf("\nARVORE GERADA COM SUCESSO!!\n");
								 getchar();
    		         break;
      case '2' : printf("Mostrando a arvore ...\n");
                 if (arvore)//se arvore for diferente de NULL
								 	imprimeArvore(arvore, 0);
                 else
								 	printf("Arvore vazia!!\n");// senão árvore está vazia
                 getchar();
                 break;
      case '3' : printf("Removendo elemento da arvore ...\n");
                 if (!arvore)
								 	printf("Arvore vazia!!\n");
                 else
                   printf("Digite um numero: ");//valora ser removido, informado pelo usuário
                   scanf("%d", &conteudo);
                   fflush(stdin);
   								 arvore = deletaMultiplo(arvore, arvore, conteudo, 0);
                 getchar();
                 break;
      case '4' : break;
      default  : printf("\nOpcao invalida!\n\n");
								getchar();
    }
  } while (op != '4');

return 1;
}