{
  ***********************************************

  Rotinas Genericas: Arvore Binaria Ordenada

  ***********************************************

  Descricao dos tipos de dados
}


Type
  TArvBin_Dado    = Integer;
  Ptr_ArvBin_Nodo = ^ArvBin_Nodo;
  ArvBin_Nodo     = Record
                      Dado: TArvBin_Dado;
                      Pai: Ptr_ArvBin_Nodo;
                      ArvEsq, ArvDir : Ptr_ArvBin_Nodo;
                    End;


{
  Descricao das Rotinas
}
Procedure ArvBin_Inicializa (Var ABO: Ptr_ArvBin_Nodo);
{ ABO = Ponteiro para a raiz da arvore binaria ordenada,
        inicializado com NIL  }
Begin
  ABO := NIL;
End;

Procedure ArvBin_Insere_Ordenado (Var ABO: Ptr_ArvBin_Nodo; Dado: TArvBin_Dado);
{ Insere um dado de modo ordenado na arvore binaria }
Var
  novo, ptr, ant : Ptr_ArvBin_Nodo;
Begin
  New(novo);
  novo^.dado := Dado;
  novo^.ArvEsq := NIL;
  novo^.ArvDir := NIL;
  ptr := ABO;

  While ptr <> NIL
  Do  Begin
        ant := ptr;
        If dado > ptr^.dado
        Then ptr := ptr^.ArvDir
        Else ptr := ptr^.ArvEsq;
      End;
  If ptr = ABO
  Then Begin
         novo^.Pai := NIL;
         ABO := novo;
       End
  Else Begin
         novo^.Pai := ant;
         If dado > ant^.dado
         Then ant^.ArvDir := novo
         Else ant^.ArvEsq := novo;
       End;
End;

Procedure ArvBin_Exibe_Infixado (ABO: Ptr_ArvBin_Nodo);
{ Exibe o conteudo (dados) da arvore em ordem infixada...
  seja ela ordenada ou nao }
Begin
  If ABO <> NIL
  Then Begin
         ArvBin_Exibe_Infixado(ABO^.ArvEsq);
         Writeln (ABO^.dado);
         ArvBin_Exibe_Infixado(ABO^.ArvDir);
       End;
End;

Procedure ArvBin_Exibe_Prefixado (ABO: Ptr_ArvBin_Nodo);
{ Exibe o conteudo (dados) da arvore em ordem prefixada...
  seja ela ordenada ou nao  }
Begin
  If ABO <> NIL
  Then Begin
         Writeln (ABO^.dado);
         ArvBin_Exibe_Prefixado(ABO^.ArvEsq);
         ArvBin_Exibe_Prefixado(ABO^.ArvDir);
       End;
End;

Procedure ArvBin_Exibe_Posfixado (ABO: Ptr_ArvBin_Nodo);
{ Exibe o conteudo (dados) da arvore em ordem posfixada...
  seja ela ordenada ou nao  }
Begin
     If ABO <> NIL
     Then Begin
            ArvBin_Exibe_Posfixado(ABO^.ArvEsq);
            ArvBin_Exibe_Posfixado(ABO^.ArvDir);
            Writeln (ABO^.dado);
          End;
End;