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

  Rotinas Genericas: Arvore Binaria Ordenada

  Parte II - Exibe Estrutura
             Remocao de Nodos
             Pesquisa Binaria

  ***********************************************
}

{
  Descricao das Rotinas
}

Procedure ArvBin_Exibe_Arvore (ABO: Ptr_ArvBin_Nodo;
          Col,Lin,Ant:Integer);
{ Exibe a estrutura da arvore... }
Begin
  If ABO <> NIL
  Then Begin
         ArvBin_Exibe_Arvore(ABO^.ArvEsq,Col-abs(ant-col) DIV 2,lin+1,col);
         GotoXY(col,lin);
         Writeln (ABO^.dado);
         ArvBin_Exibe_Arvore(ABO^.ArvDir,col+abs(ant-col) DIV 2,lin+1,col);
       End;
End;


Function ArvBin_Pesquisa_Dado (ABO: Ptr_ArvBin_Nodo; Dado: TArvBin_Dado):
         Ptr_ArvBin_Nodo;
{ Procura um dado na arvore e retorna um ponteiro para o nodo se achou
  ou NIL se nao achou => Realiza uma Pesquisa Binaria! }
Var
  ptr:Ptr_ArvBin_Nodo;
Begin
  ptr:=ABO;
  While (ptr <> NIL) AND (ptr^.Dado <> Dado)
  Do If Dado > ptr^.Dado
     Then ptr:=ptr^.ArvDir
     Else ptr:=ptr^.ArvEsq;
  ArvBin_Pesquisa_Dado:=ptr;
End;


Function ArvBin_Menor (ABO: Ptr_ArvBin_Nodo; Var Dado: TArvBin_Dado):
         Ptr_ArvBin_Nodo;
{ Retorna o menor dado a partir do nodo corrente }
Var
  ptr:Ptr_ArvBin_Nodo;
Begin
  ptr:=ABO;
  If ptr=NIL
  Then ArvBin_Menor:=NIL
  Else Begin
         While (ptr^.ArvEsq <> NIL)
         Do ptr:=ptr^.ArvEsq;
         ArvBin_Menor:=ptr;
         Dado:=ptr^.Dado;
       End;  
End;

Function ArvBin_Maior (ABO: Ptr_ArvBin_Nodo; Var Dado: TArvBin_Dado):
         Ptr_ArvBin_Nodo;
{ Retorna o maior dado a partir do nodo corrente }
Var
  ptr:Ptr_ArvBin_Nodo;
Begin
  ptr:=ABO;
  If ptr=NIL
  Then ArvBin_Maior:=NIL
  Else Begin
         While (ptr^.ArvDir <> NIL)
         Do ptr:=ptr^.ArvDir;
         ArvBin_Maior:=ptr;
         Dado:=ptr^.Dado;
       End;
End;

Procedure ArvBin_Remove_Nodo (Var ABO: Ptr_ArvBin_Nodo; Var Dado: TArvBin_Dado);
{ Remove da arvore o nodo correntemente apontado }
Var
  aux, pai, filho:Ptr_ArvBin_Nodo;
  daux: TArvBin_Dado;
Begin
  If ABO <> NIL
  Then Begin
         Dado:=ABO^.Dado;
         If (ABO^.ArvEsq = NIL) AND (ABO^.ArvDir = NIL)
         Then Begin
                pai:=ABO^.pai;
                If pai <> NIL
                Then If ABO=pai^.ArvEsq
                     Then pai^.ArvEsq:=NIL
                     Else pai^.ArvDir:=NIL;
              End
         Else Begin
                aux:=ArvBin_Maior(ABO^.ArvEsq,daux);
                If aux <> NIL
                Then Begin
                       pai:=aux^.pai;
                       filho:=aux^.ArvEsq;
                       If pai = ABO
                       Then ABO^.ArvEsq:=filho
                       Else pai^.ArvDir:=filho;
                     End
                Else Begin
                       aux:=ArvBin_Menor(ABO^.ArvDir,daux);
                       pai:=aux^.pai;
                       filho:=aux^.ArvDir;
                       If pai = ABO
                       Then ABO^.ArvDir:=filho
                       Else pai^.ArvEsq:=filho;
                     End;
                If filho <> NIL
                Then filho^.pai:=pai;
                ABO^.dado:=aux^.dado;
                ABO:=aux;
              End;
         dispose(ABO);
         ABO:=NIL;
       End;
End;