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

/*
                ESTRUTURA DA ARVORE
                                                            */
typedef struct no {
    int conteudo;
    struct no *esq,
              *dir;
}Arvore;
//                      FIM





/*
                CASE '1' -> INSERÇÃO NA ARVORE
                                                            */

Arvore *insereNaArvore(Arvore *raiz, Arvore *r, int conteudo){
    if (!r) {//VERIFICA SE r É NULL, SE FOR ALOCA, ESQ E DIR = NULL, RECEBE
        r = (Arvore *)malloc(sizeof(Arvore));                          // CONTEUDO
        if (!r) {//TESTA SE ALOCOU O r
            printf("\n\n\nSEM MEMORIA!!");
            exit(0);
        }
        r->esq = NULL;
        r->dir = NULL;
        r->conteudo = conteudo;

        if (!raiz) {
            return r; //PRIMEIRA ENTRADA, ARVORE ASSUME O VALOR DE r
        }

        if (conteudo == raiz->conteudo) {//VERICA SE JA É CADASTRADO
            printf("\n\n\n\n\nNUMERO %d JA CADASTRADO.",raiz->conteudo);
            return ;
        }
        if(conteudo < raiz->conteudo){//SE O CONTEUDO FOR MENOR, ASSUME VALOR DA
            raiz->esq = r;             //ESQUERDA       */
            printf("\n\n\n\n\nNUMERO CADASTRADO: %d",r->conteudo);//INFORMA NUMERO
        }
        else{
            raiz->dir = r;//SE MAIOR, ASSUME DA DIREITA
            printf("\n\n\n\n\nNUMERO CADASTRADO: %d",r->conteudo);//INFORMA NUMERO
        }

        getch();
        return r;   //APENAS VOLTA PARA A FUNCAO
    }
    if (conteudo == r->conteudo){//VERIFICA SE JA FOI CADASTRADO
        printf("\n\n\nNUMERO %d JA CADASTRADO.",raiz->conteudo);
        getch();
        return ;
    }
    else if (conteudo < r->conteudo){//NUMERO MENOR, VAI PRA ESQUERDA
        printf("\n\n<-- FOI PRA ESQUERDA");
        insereNaArvore(r, r->esq, conteudo);
    }
    else{ //NUMERO MAIOR, VAI PRA DIREITA
        printf("\n\nFOI PRA DIREITA -->"); //NUMERO MAIOR, VAI PRA DIREITA
        insereNaArvore(r, r->dir, conteudo);
    }
}
//                      FIM





/*
                CASE '2' -> MOSTRAR A ARVORE
                                                            */
Arvore *imprimiArvore(Arvore *raiz, int l){
    int i;
    if(!raiz)//SE RAIZ = NULA, RETORNA
        return;

    imprimiArvore(raiz->dir,l+1);//IMPRIMI À DIREITA

    for(i=0 ; i<l ;i++)//FUNCAO PARA FAZER A IMPRESSAO CORRETA EM ARVORE
        printf("  ");

    printf("%d\n",raiz->conteudo);

    imprimiArvore(raiz->esq,l+1);//IMPRIMI À ESQUERDA
}





/*
                CASE '3' -> REMOVER ARQUIVOS
                                                            */
Arvore *deletaArvore(Arvore *raiz, int conteudo) {
    Arvore *p, *p2;

    if (!raiz)  //RAIZ = NULA, QUER DIZER QUE TA VAZIA
        return raiz;

    if ( raiz->conteudo%conteudo == 0) { //SE O RESTO DA DIVISAO DO NÓ PELO
                                     //CONTEUDO FOR 0, É MULTIPLO ENTAO DELETA
        printf("\n\n\nNUMERO %d DELETADO.",raiz->conteudo);
        getch();
        if (raiz->esq == raiz->dir){  //RAIZ NULA
            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;
        }
    }
                                            //VERIFICA SE É MAIOR OU MENOR
    if (raiz->conteudo < conteudo)          //VAI PRA DIREITA OU ESQUERDA
        raiz->dir = deletaArvore(raiz->dir, conteudo);
    else raiz->esq = deletaArvore(raiz->esq, conteudo);

    return raiz;
}





/*
                FUNCAO PRINCIPAL
                                                            */
main(){
    int quantidade, conteudo,i;
    char op;

    srand(time(NULL));

    Arvore *arvore,*arvoreB; //CRIA UMA VARIAVEL ARVORE
    arvore = NULL;  //DEIXA INICIALMENTE NULA

    do{                                   //MENU
        system("cls");
	    printf("\t\t\t ______________________");
		printf("\n\t\t\t|    MENU DE ARVORES:  |");
		printf("\n\t\t\t ______________________");
		printf("\n\t\t\t|1|    GERAR ARVORE    |");
		printf("\n\t\t\t|2|      MOSTRAR       |");
		printf("\n\t\t\t|3|      REMOVER       |");
		printf("\n\t\t\t|0|       SAIR         |");
		printf("\n\t\t\t ----------------------");
		printf("\n\n\t\t\tOpcao: ");
		op = getchar();                  //RECEBE OPCAO
		fflush(stdin);
		switch(op){

            case '1':
                system("cls");
                printf("\n\t\t\tGERANDO ARVORE RANDOMICAMENTE:");
                printf("\n\n\n\nDIGITE A QUANTIA DE NOS(1 a 100): ");
                scanf("%d",&quantidade);
                fflush(stdin);

                if(quantidade > 100 || quantidade < 1){ //TESTA SE TA NOS
                    printf("\n\n\n\n\n\nNUMERO INVALIDO.");    //LIMITES
                    getch();
                    break;
                }

                for (i = 1; i <= quantidade; i++){ //GERANDO NUMEROS RANDOM
                    system("cls");
                    conteudo = rand() % 100;
                    if (!arvore)  //SE FOR A PRIMEIRA INSERÇÃO
                        arvore = insereNaArvore(arvore, arvore, conteudo);
                    else insereNaArvore(arvore, arvore, conteudo);
                }

                printf("\n\n\n\n\n\nARVORE GERADA COM SUCESSO!!\n");

                getchar();
                break;


            case '2':
                printf("\n\nIMPRIMINDO A ARVORE\n\n");

                if(arvore)//SE EXISTIR, MOSTRA
                    imprimiArvore(arvore,0);
                else printf("\n\nARVORE NULA");//SE NAO, INFORMA QUE TA NULA

                getch();
                break;


            case '3':
                printf("\n\nREMOVENDO ITENS DA ARVORE\n\n");

                if (!arvore)
                    printf("\n\nARVORE NULA");//INFORMA QUE TA NULA
                else {
                    printf("DIGITE UM NUMERO: ");//RECEBE O NUMERO A SER
                    scanf("%d", &conteudo);  //VERIFICADO PARA DELETAR
                    fflush(stdin);
                    while(arvore != arvoreB){
                        arvoreB = arvore;
                        arvore = deletaArvore(arvore,conteudo);
                    }
                 }

                 getchar();
                 break;


            case '0': // SAIR DO PROGRAMA
                break;
        }
        }while(op!='0');
 }