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

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

int contaNosNivel(int niv, Arvore *raiz){
    int numero;
		if(!raiz) return 0;
    if(raiz == 0) return 1;
    //este clobo que segue é dispensavel só faz uma chamada recursiva a menos
    if(niv==1){
        int numero=0;// inicia em 0, pois pode nao entrar no 1 if
        if(raiz->esq) numero=1;
        	if(raiz->dir)numero - numero + 1;
             return numero;
          }
    return contaNosNivel(niv -1, raiz->esq)+ contaNosNivel (niv -1, raiz->dir);
}

Arvore *achaMenor(Arvore *raiz){
	Arvore *menor, *menorSubArv;

	if(raiz){ // if(raiz!=NULL)
		menor=raiz;
		if(raiz->esq){
			menorSubArv = achaMenor(raiz->esq);
			if(menorSubArv && menorSubArv->conteudo < menor->conteudo)
				menor=menorSubArv;
			}
	  if(raiz->dir){
		  menorSubArv = achaMenor(raiz->dir);
		  if(menorSubArv && menorSubArv->conteudo < menor->conteudo)
			  menor = menorSubArv;
		}
	  return menor;
  }
  return NULL;
}



int contaNos(Arvore *raiz){
//return (!raiz)? 0 : 1 + contaNos (raiz->esq) + contaNos (raiz->dir);
		if(!raiz)
			return 0;
    else return 1 + contaNos (raiz->esq) + contaNos (raiz->dir);
	}

void emOrdem(Arvore *raiz) {
  if (!raiz) return; //como eh procedimento, soh retorna o controle para o main()

  emOrdem(raiz->esq);
  printf("%d ", raiz->conteudo);
  emOrdem(raiz->dir);
}

Arvore *pesquisaArvore(Arvore *raiz, int conteudoPesquisa) {
  if (!raiz) return raiz; //arvore vazia

  while (raiz->conteudo != conteudoPesquisa) {
    if (conteudoPesquisa < raiz->conteudo) raiz = raiz->esq;
    else raiz = raiz->dir;

    if (!raiz) break;
  }
  return raiz;
}

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

  if (!raiz) return; //como eh procedimento, soh retorna o controle para o main()

  imprimeArvore(raiz->dir, l + 1);

  for (i = 0; i < l; ++i) printf("  ");

  printf("%d\n", raiz->conteudo);
  imprimeArvore(raiz->esq, l + 1);
}

Arvore *insereNaArvoreBinaria(Arvore *raiz, Arvore *r, int conteudo) {
  if (!r) {
    r = (Arvore *)malloc(sizeof(Arvore));
    if (!r) {
      printf("\n\nSEM MEMORIA!! Programa finalizado!\n");
      exit(0);
    }
    r->esq = NULL;
    r->dir = NULL;
    r->conteudo = conteudo;

    if (!raiz) {
      printf("\nna primeira insercao\n");
      return r; //primeira entrada
    }
		if (conteudo == raiz->conteudo)
			printf("\nnumero jah cadastrado\n");
    else if (conteudo < raiz->conteudo) raiz->esq = r;
    else raiz->dir = r;

    return r;
  }
  if (conteudo < r->conteudo) {
    printf("\nfui pra esquerda\n");
    insereNaArvoreBinaria(r, r->esq, conteudo);
  }
  else {
    printf("\nfui pra direita\n");
    insereNaArvoreBinaria(r, r->dir, conteudo);
  }
}

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 eh 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;
}

int main() {
  Arvore *arvore, *menor;
  char op;
  int conteudo, cont, nivel, num;

  //recebe do usuario a quantidade de elementos a serem inserido na arvore
  arvore = NULL;
  do {
    system("cls");
    printf("Menu de opcoes para arvore binaria sobre vetores\n");
    printf(" \n1 - Inserir \n2 - Pesquisar \n3 - Mostrar \n4 - Remover \n5 - Conta Nos \n6 - Acha menor \n7 - Conta Niveis da arvore \n\n8 - Sair \n\nEscolha uma opcao:");
    op = getchar();
    fflush(stdin);//fflush(stdin);

    switch (op) {
      case '1' : printf("\nInserindo na arvore ...\n");
                 printf("\nDigite um numero: ");
                 scanf("%d", &conteudo);
                 fflush(stdin);//fflush(stdin);
                 if (!arvore)
								 	arvore = insereNaArvoreBinaria(arvore, arvore, conteudo);
                 else insereNaArvoreBinaria(arvore, arvore, conteudo);
                 getchar();
      		       break;
      case '2' : printf("\nPesquisando na arvore ...\n");
                 if (!arvore) printf("Arvore vazia!!\n");
                 else {
                   printf("\nDigite um numero: ");
                   scanf("%d", &conteudo);
                   fflush(stdin);//fflush(stdin);
                   if (pesquisaArvore(arvore, conteudo)) printf("Valor localizado na arvore\n");
                   else printf("\nValor NAO localizado na arvore!!\n");
                 }
                 getchar();
      case '3' : printf("\nMostrando a arvore ...\n");
                 if (arvore) imprimeArvore(arvore, 0);
                 else printf("Arvore vazia!!\n");
                 getchar();
                 break;
      case '4' : printf("\nRemovendo elemento da arvore ...\n");
                 if (!arvore) printf("Arvore vazia!!\n");
                 else {
                   printf("Digite um numero: ");
                   scanf("%d", &conteudo);
                   fflush(stdin);//fflush(stdin);
                   if (deletaArvore(arvore, conteudo)) printf("Valor localizado na arvore\n");
                   else printf("Valor NAO localizado na arvore!!\n");
                 }
                 getchar();
                 break;
      case '5' : printf("\nContando os nos...\n");
      					 cont = contaNos(arvore);
      					 if(cont==0)
								 printf("\nArvore vazia!!!");
								 else printf("Numero de nos: %d", cont);
								 getchar();
								 break;
			case '6' : printf("\nProcurando Menor NO...\n");
								 menor = achaMenor(arvore);
								 if(menor)
								 printf("\nMenor NO = %d", menor->conteudo);
								 else printf("\nArvore vazia!!!");
								 getchar();
								 break;
      case '7' : printf("\nContando os Niveis da arvore...");
      					 printf("\nInforme a árvore:");
      					 scanf("%d", &nivel);
								 num = contaNosNivel(nivel, arvore);
								 if(num)
								 printf("\nNumero de niveis da arvore %d = %d", nivel, num);
								 else printf("\nArvore %d vazia!!!", nivel);
								 getchar();
								 break;
			case '8' : break;
      default  : printf("\nOpcao invalida!\n\n");
								 getchar();
    }

  } while(op != '8');

  return 1;
}