#include <stdio.h>

#define OK   1
#define ERRO 0

typedef int Tipo_Dado;

typedef struct bloco_ab
        {
           Tipo_Dado          Dado;
           struct bloco_ab    *FilhoEsq, *FilhoDir;
           struct bloco_ab    *Pai;
        }  Nodo_AB;


/***  Rotinas...

void inicializa_arvbin (Nodo_AB **AB);
int insere_ord_arvbin            (Nodo_AB **AB, Tipo_Dado Dado);
int  remove_dado_arvbin    (Nodo_AB **AB, Tipo_Dado Dado);
void exibe_ab_infixado              (Nodo_AB   *AB);
void exibe_ab_prefixado        (Nodo_AB   *AB);
void exibe_ab_posfixado  (Nodo_AB  *AB);
void apaga_arvbin             (Nodo_AB **AB);
int conta_nodos_arvbin            (Nodo_AB   *AB);
Nodo_AB *pesquisa_arvbin    (Nodo_AB   *AB, Tipo_Dado Dado);
Nodo_AB *maior_arvbin          (Nodo_AB   *AB, Tipo_Dado *Dado);
Nodo_AB *menor_arvbin  (Nodo_AB   *AB, Tipo_Dado *Dado);
Nodo_AB *sucessor_arvbin  (Nodo_AB   *AB, Tipo_Dado *Dado);
Nodo_AB *predecessor_arvbin(Nodo_AB    *AB, Tipo_Dado *Dado);


***/


void inicializa_arvbin (AB)
Nodo_AB **AB;
{
  *AB = NULL;
}


int insere_ord_arvbin (AB, Dado)
Nodo_AB **AB;
Tipo_Dado Dado;
{
   /* Arvore bin ria onde os nodos sao inseridos de maneira ordenada:   */
   /* - Os nodos a esquerda de um nodo pai sao sempre menores que ele   */
   /* - Os nodos a direita de um nodo pai sao sempre maiores que ele    */

   Nodo_AB *novo,  *aux, *temp;

   novo = (Nodo_AB *) calloc ( 1, sizeof (Nodo_AB) );
   if ( novo == NULL ) return (ERRO);

   novo -> Dado = Dado;
   novo -> FilhoEsq = NULL;
   novo -> FilhoDir = NULL;
   aux = *AB;

   while ( aux != NULL )     /* Acha o ponto onde vai inserir */
   {

      temp = aux;
      if ( Dado > (aux -> Dado) )
         aux = aux -> FilhoDir;
      else
         aux = aux -> FilhoEsq;
   }

   if ( aux == *AB)
   {
      novo -> Pai = NULL;
      *AB = novo;
   }
   else
   {
      novo -> Pai = temp;
      if (Dado > temp->Dado)
          temp -> FilhoDir = novo;
      else
          temp -> FilhoEsq = novo;
   }
   return(OK);
}


void exibe_ab_infixado (AB)
Nodo_AB *AB;
{
   if ( AB != NULL )
   {
      exibe_ab_infixado ( AB -> FilhoEsq );
      printf ("%d\n", AB -> Dado);
      exibe_ab_infixado ( AB -> FilhoDir);
   }
}


void exibe_ab_prefixado (AB)
Nodo_AB *AB;
{
   if ( AB != NULL )
   {
      printf ("%d\n", AB -> Dado);
      exibe_ab_prefixado ( AB -> FilhoEsq );
      exibe_ab_prefixado ( AB -> FilhoDir);
   }
}

void exibe_ab_posfixado (AB)
Nodo_AB *AB;
{
   if ( AB != NULL )
   {
      exibe_ab_posfixado ( AB -> FilhoEsq );
      exibe_ab_posfixado ( AB -> FilhoDir);
      printf ("%d\n", AB -> Dado);
   }
}


main ( )
{

  Nodo_AB *Arvore;

  inicializa_arvbin (&Arvore);

  if ( insere_ord_arvbin(&Arvore, 10) )
     printf("Insercao do valor: 10\n");
  else
     printf(">> Erro na insercao!\n");

  if ( insere_ord_arvbin(&Arvore, 5) )
     printf("Insercao do valor: 5\n");
  else
     printf(">> Erro na insercao!\n");

  if ( insere_ord_arvbin(&Arvore, 15) )
     printf("Insercao do valor: 15\n");
  else
     printf(">> Erro na insercao!\n");


  printf("\nArvore: modo infixado\n");
  exibe_ab_infixado(Arvore);

  printf("\nArvore: modo prefixado\n");
  exibe_ab_prefixado(Arvore);

  printf("\nArvore: modo posfixado\n");
  exibe_ab_posfixado(Arvore);

  printf("\nFim\n");
  getch();
}