/********************************************************

   ARVBIN
   ======

   Rotinas de manipulacao de ARVORES BINARIAS:
   - Estruturas de dados com alocacao dinamica
   - Insere ordenado
   - Insere a esquerda ou a direita
   - Exibe arvore em modo pre-fixado, infixado e pos-fixado
   - Remocao (nao implementada): sugere-se remocao logica

   Aplicacao tipica:
   - Busca binaria em arvores ordenadas

   Por: Fernando Osorio
   Data da ultima atualizacao: Nov. 2013

*********************************************************/

/* Incluir: stdio.h */
#include <string.h>

#define OK   1
#define ERRO 0

#define ACHOU 1
#define NAO_ACHOU 0

typedef struct 
        {
           char nome[5];
           char op;
           int  tipo;      /* 0 p/ operador, 1 p/folha */
           float num;
        } 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_raiz_arvbin (Nodo_AB **AB, Tipo_Dado Dado);
int  insere_ord_arvbin  (Nodo_AB **AB, Tipo_Dado Dado);
int  insere_esq_arvbin  (Nodo_AB **AB, Tipo_Dado Dado);             
int  insere_dir_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);

int  pesquisa_arvbin    (Nodo_AB *AB, Nodo_AB **AB, Tipo_Dado Dado);

void apaga_arvbin       (Nodo_AB **AB);
int  remove_dado_arvbin (Nodo_AB **AB, Tipo_Dado Dado);
int  conta_nodos_arvbin (Nodo_AB **AB);
int  maior_arvbin       (Nodo_AB **AB, Tipo_Dado *Dado);
int  menor_arvbin       (Nodo_AB **AB, Tipo_Dado *Dado);
int  sucessor_arvbin    (Nodo_AB **AB, Tipo_Dado *Dado);
int  predecessor_arvbin (Nodo_AB **AB, Tipo_Dado *Dado);

***/


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

int insere_raiz_arvbin (AB, Dado)
Nodo_AB **AB;
Tipo_Dado Dado;
{
   /* Insere o dado na raiz da arvore (topo) */
   Nodo_AB *novo;

   /* Erro se a arvore nao esta vazia... */
   if ((*AB) != NULL) 
      return(ERRO);
   
   /* Erro se nao conseguiu alocar o nodo... */
   novo = (Nodo_AB *) calloc ( 1, sizeof (Nodo_AB) );
   if ( novo == NULL ) return (ERRO);

   novo -> Dado = Dado;
   novo -> FilhoEsq = NULL;
   novo -> FilhoDir = NULL;
   novo -> Pai = (*AB);
   (*AB) = novo;

   return(OK);
}

int insere_esq_arvbin (AB, Dado)
Nodo_AB **AB;
Tipo_Dado Dado;
{
   /* Insere o dado no filho a esquerda do nodo */

   Nodo_AB *novo;

   /* Erro se ja existe um filho a esquerda... */
   if ((*AB)->FilhoEsq != NULL) 
      return(ERRO);
   
   /* Erro se nao conseguiu alocar o nodo... */
   novo = (Nodo_AB *) calloc ( 1, sizeof (Nodo_AB) );
   if ( novo == NULL ) return (ERRO);

   novo -> Dado = Dado;
   novo -> FilhoEsq = NULL;
   novo -> FilhoDir = NULL;
   novo -> Pai = (*AB);
   (*AB)->FilhoEsq = novo;

   return(OK);
}

int insere_dir_arvbin (AB, Dado)
Nodo_AB **AB;
Tipo_Dado Dado;
{
   /* Insere o dado no filho a esquerda do nodo */

   Nodo_AB *novo;

   /* Erro se ja existe um filho a esquerda... */
   if ((*AB)->FilhoDir != NULL) 
      return(ERRO);
   
   /* Erro se nao conseguiu alocar o nodo... */
   novo = (Nodo_AB *) calloc ( 1, sizeof (Nodo_AB) );
   if ( novo == NULL ) return (ERRO);

   novo -> Dado = Dado;
   novo -> FilhoEsq = NULL;
   novo -> FilhoDir = NULL;
   novo -> Pai = (*AB);
   (*AB)->FilhoDir = novo;

   return(OK);
}

void exibe_ab_infixado (AB)
Nodo_AB *AB;
{
   if ( AB != NULL )
   {
      exibe_ab_infixado ( AB -> FilhoEsq );
      if (AB->Dado.tipo)
         printf ("Num   : %d\n", AB -> Dado.num);
      else
         printf ("Op(%c): %s\n", AB->Dado.op, AB->Dado.nome);
      exibe_ab_infixado ( AB -> FilhoDir);
   }
}


void exibe_ab_prefixado (AB)
Nodo_AB *AB;
{
   if ( AB != NULL )
   {
      if (AB->Dado.tipo)
         printf ("Num   : %d\n", AB -> Dado.num);
      else
         printf ("Op(%c): %s\n", AB->Dado.op, AB->Dado.nome);
      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);
      if (AB->Dado.tipo)
         printf ("Num   : %f\n", AB -> Dado.num);
      else
         printf ("Op(%c): %s\n", AB->Dado.op, AB->Dado.nome);
   }
}

int pesquisa_arvbin (AB, Nodo, Dado)
Nodo_AB *AB;
Nodo_AB **Nodo;
Tipo_Dado Dado;
{
   int achou1, achou2;
   
   if ( (AB) != NULL )
   {
      if ( strcmp(AB -> Dado.nome,Dado.nome) == 0 ) 
	  { 
	     *Nodo = AB;
	     return(ACHOU);
	  }
      achou1 = pesquisa_arvbin( AB -> FilhoEsq, Nodo, Dado );
      achou2 = pesquisa_arvbin( AB -> FilhoDir, Nodo, Dado );
	  if (achou1 || achou2) 
	     return(ACHOU);
	  else
	     return(NAO_ACHOU);
   }
   else
      return(NAO_ACHOU);
}


/*=== FIM ====*/