#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;


typedef struct{
  int conta;
}contador;

void iniciacontador(contador *p){
  p->conta=0;
}

/* Cada nó armazena três informações:
   nesse caso um número (num),
   ponteiro para subárvore à direita (sad)
   e ponteiro para subárvore à esquerda (sae).*/
typedef struct tree
{
  int num;
  struct tree* sad;
  struct tree* sae;
} Tree;

/* A estrutura da árvore é representada por um ponteiro
   para o nó raiz. Com esse ponteiro, temos acesso aos
   demais nós. */

/* Função que cria uma árvore */
Tree* createTree()
{

  /* Uma árvore é representada pelo endereço do nó raiz,
     essa função cria uma árvore com nenhum elemento,
     ou seja, cria uma árvore vazia, por isso retorna NULL. */
  return NULL;
}

/* Função que verifica se uma árvore é vazia */
int treeIsEmpty(Tree* t)
{
  /* Retorna 1 se a árvore for vazia e 0 caso contrário */
  return t == NULL;

}

/* Função que mostra a informação da árvore */
void preordem(Tree* t)
{
  /* Essa função imprime os elementos de forma recursiva */

  printf("<"); /* notação para organizar na hora de mostrar os elementos */
  if(!treeIsEmpty(t)) /* se a árvore não for vazia... */
  {
    /* Mostra os elementos em pré-ordem */
    printf("%d", t->num); /* mostra a raiz */
    preordem(t->sae); /* mostra a sae (subárvore à esquerda) */
    preordem(t->sad); /* mostra a sad (subárvore à direita) */
  }
  printf(">"); /* notação para organizar na hora de mostrar os elementos */
}

void posordem(Tree* t){
  printf("<"); /* notação para organizar na hora de mostrar os elementos */
  if(!treeIsEmpty(t)) /* se a árvore não for vazia... */
  {
    /* Mostra os elementos em pré-ordem */
    posordem(t->sae); /* mostra a sae (subárvore à esquerda) */
    posordem(t->sad); /* mostra a sad (subárvore à direita) */
    printf("%d", t->num); /* mostra a raiz */
  }
  printf(">"); /* notação para organizar na hora de mostrar os elementos */
}

void inordem (Tree* t){
  /* Essa função imprime os elementos de forma recursiva */

  printf("<"); /* notação para organizar na hora de mostrar os elementos */
  if(!treeIsEmpty(t)) /* se a árvore não for vazia... */
  {
    /* Mostra os elementos em pré-ordem */
    inordem(t->sae); /* mostra a sae (subárvore à esquerda) */
    printf("%d", t->num); /* mostra a raiz */
    inordem(t->sad); /* mostra a sad (subárvore à direita) */
  }
  printf(">"); /* notação para organizar na hora de mostrar os elementos */
}

/* Função que insere um dado na árvore */
void insertTree(Tree** t, int num)
{
  /* Essa função insere os elementos de forma recursiva */
  if(*t == NULL)
  {
    *t = (Tree*)malloc(sizeof(Tree)); /* Aloca memória para a estrutura */
    (*t)->sae = NULL; /* Subárvore à esquerda é NULL */
    (*t)->sad = NULL; /* Subárvore à direita é NULL */
    (*t)->num = num; /* Armazena a informação */
  } else {
    if(num < (*t)->num) /* Se o número for menor então vai pra esquerda */
    {
      /* Percorre pela subárvore à esquerda */
      insertTree(&(*t)->sae, num);
    }
    if(num > (*t)->num) /* Se o número for maior então vai pra direita */
    {
      /* Percorre pela subárvore à direita */
      insertTree(&(*t)->sad, num);
    }
  }
}

/* Função que verifica se um elemento pertence ou não à árvore */
int isInTree(Tree* t, int num) {

  if(treeIsEmpty(t)) { /* Se a árvore estiver vazia, então retorna 0 */
    return 0;
  }

  /* O operador lógico || interrompe a busca quando o elemento for encontrado */
  return t->num==num || isInTree(t->sae, num) || isInTree(t->sad, num);
}

void noIntTree(Tree* t, int cont, contador *p) {

  if(!treeIsEmpty(t)) /* se a árvore não for vazia... */
  {
    /* Mostra os elementos em pré-ordem */
    if(t->sad!=NULL||t->sae!=NULL){
    printf("%d ", t->num); /* mostra a raiz */
    p->conta++;
    cont++;
  }
    noIntTree(t->sae,cont, p); /* mostra a sae (subárvore à esquerda) */
    noIntTree(t->sad,cont , p); /* mostra a sad (subárvore à direita) */
  }


}



int main()
{
  Tree* t = createTree(); /* cria uma árvore */
  contador c;
  iniciacontador(&c);

  int op,n,cont=0;

  while (1){
    printf ("\n Menu");
    printf ("\n 1. Insere");
    printf ("\n 2. Exibe PRE-FIXADO ");
    printf ("\n 3. Exibe INFIXADO ");
    printf ("\n 4. Exibe POS-FIXADO ");
    printf ("\n 5. Verifica se numero esta na arvore ");
    printf ("\n 6. Verifica arvore vazia ");
    printf("\n 7. Sair");
    printf ("\n\n Entre a sua opcao: ");
    scanf ("%d",&op);
    fflush(stdin);
    if(op==1){
    scanf("%d", &n);
    insertTree(&t, n);
  }
  else if(op==2){
    preordem(t);
  }
  else if(op==3){
    inordem(t);
  }
  else if(op==4){
    posordem(t);
  }
  else if(op==5){
    scanf("%d", &n);
    if(isInTree(t, n)) { /* Verifica se o número 22 pertence a árvore */
        printf("\nO numero %d pertence a arvore!\n\n", n);
    }

    else {
       printf("\nO numero %d NAO pertence a arvore!\n\n", n);
    }
  }
  else if(op==6){
    if(treeIsEmpty(t)) /* Verifica se a árvore está vazia */
    {
      printf("\n\nArvore vazia!!\n");
    } else {
      printf("\n\nArvore NAO vazia!!\n");
    }
  }
  else if(op==7){
    noIntTree(t,cont, &c);
    cout<<endl;
    cout<<"Numero de nós internos: "<<c.conta<<endl;
  }
  else if(op==8){
    break;
  }
  }

  free(t); /* Libera a memória alocada pela estrutura árvore */

  return 0;
}