/*-Comentários na árvore do Omega-*/

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

typedef struct A
{
    int elemento;
    struct A *esq,*dir;

}arvore;

void adicionar_Elemento(arvore*, int);
void Imprimir(arvore*);
int  Pesquisar(arvore*, int);

int main(void)
{
    char opc;
    int elem_raiz, n, buf, pes;
    arvore *raiz;
    printf("Digite um numero para a raiz: "); // Este trecho poderia ter sido removido, para aproveitar mais uma célula na árvore.
    scanf(" %d", &elem_raiz);
    raiz = (arvore*)malloc(sizeof(arvore));
    raiz->elemento = elem_raiz;
    raiz->esq = NULL;
    raiz->dir = NULL;

        do{
           printf("\n\nO que deseja fazer?\n\
           A - Adicionar\n\
           L - Listar\n\
           P - Pesquisar\n\
           S - Sair\n");
           printf("\nOpcao escolhida: ");
               while ((buf = getchar()) != '\n' && buf != EOF); // isso aqui é mais uma das viadagens do Omega.
           scanf("%c", &opc);

           switch(opc)
           {
              case 'a': printf("\nDigite um inteiro: ");
                            scanf(" %d",&n);
                                adicionar_Elemento(raiz, n);
                    break;

              case 'l': printf("\n\n");
                    Imprimir(raiz);
                        break;

              case 'p': printf("\nQual elemento a procurar? ");
                        scanf(" %d",&n);
                pes = Pesquisar(raiz, n);
                if(pes) printf("\nElemento encontrado.\n");
                else printf("\nElemento nao encontrado.\n");
                break;
           }
        }while(opc != 's');

    return 0;
}

/* Função de adição, acionada para criar um novo valor
 * do tipo árvore para ser colocado no ponteiro *esquerda ou no *direita.
 */

void adicionar_Elemento(arvore *root, int n)
{
         arvore *no;
    // Opa, vamos noque interessa, essa porcaria é muito fácil.
     if(n < root->elemento)
     {
            if(root->esq == NULL)
        {
               no = (arvore*)malloc(sizeof(arvore));
                   no->elemento = n;
                   no->esq = NULL;
                   no->dir = NULL;
               root->esq = no;
        }
        else
               adicionar_Elemento(root->esq, n);
     }
    /* O trecho acima verifica se *esq é nulo, caso contrário o trecho passa o próximo
     * valor *esq para a função, mas isso só acontece se o valor for menor que o contido em "raiz"
     * caso contrário o else indicando para *dir é acionado.
     *
     */


     else
     {
        if(root->dir == NULL)
        {
               no = (arvore*)malloc(sizeof(arvore));
                       no->elemento = n;
                   no->esq = NULL;
                       no->dir = NULL;
               root->dir = no;
        }
        else
               adicionar_Elemento(root->dir, n);
     }

    /* Só para exercitar.

    se o novo numero for menor que o contido em raiz
        e se raiz.esquerda for nulo
        {
            eu crio um novo valor árvore
            adiciono o novo numero em novo_valor.elemento
            adiciono novo_valor em raiz.esquerda
            e finalizo a função.
        }

        caso raiz.esquerda esteja ocupado
            passo o valor raiz.esquerda para a função até que algum esquerda esteja vazio.


    agora se o novo valor for maior que o contido em raiz
        e se raiz.direita for nulo
        {
            eu crio um novo valor árvore
            adiciono o novo número em novo_valor.elemento
            adiciono novo_valoro em raiz.direita
            e finalizo a função.
        }

        caso raiz.direita esteja ocupado
            eu passo raiz.direita para a função até que algum direita esteja vazio.


    */
}

/*
 *Apesar de ser  pequena, está é a função do capeta!. Dá loop infinito na mente.
 */

void Imprimir(arvore *root)
{
    if(root) //se o valor recebido não for nulo a função executa este trecho.
    {
           Imprimir(root->esq); // Entrega o ponteiro da esquerda até que seja nulo
           printf("%d\n", root->elemento); // agora, como chega aqui e
           Imprimir(root->dir); // como chega aqui, sempre será um mistério :P .
    }
}

int Pesquisar(arvore *root, int n)
{
    if(root) // Primeiro verifica se o ponteiro é válido, se for, executa o trecho abaixo.
    {
           if(root->elemento == n) // fudeu.
              return 1;
           else
           {
              if(n < root->elemento)
                     return (Pesquisar(root->esq, n));
                  else
                     return (Pesquisar(root->dir, n));
           }
    }
    else
           return 0;
}