{############################################################################
                     TAD ARBOLES BINARIOS DE BUSQUEDA
                                11-10-2000
                            Coded by mOrGoLoCk
                      gulfas_morgolock@hotmail.com
 ############################################################################}
UNIT ARBOLES;

Interface

         type tArbol=^Reg;
              Reg= Record
                   N: integer;
                   IZQ,DER:tArbol;
              end;

   Procedure CrearArbol(Var A:tArbol);
   Procedure CrearNodo(N:Integer; VAR Nodo:tArbol);
   Procedure Imprimir(A:tArbol;Orden:byte);
   Procedure Insertar(VAR A:tArbol; N:Integer);
   Procedure Borrar(VAR A:tArbol; N:Integer);
   Function Max(A:tArbol):Integer;
   Function Min(A:tArbol):Integer;
   Function NroNodos(A:tArbol):Integer;
   Function Altura(A:tArbol):Integer;
   Function Pertenece(A:tArbol; N:Integer):Boolean;

Implementation

Procedure Borrar(VAR A:tArbol; N:Integer);
Var NodoViejo:tArbol;
    Procedure CambiarRaiz(Nodo:tArbol);
    {Cambia la Ra¡z del arbol A por el elemento m s grade del subarbol apuntado por Nodo}
    Var MaxNodo:tArbol;
    Begin
    if (Nodo^.DER=NIL) then begin {¨Es el elemento mas grade del subarbol?}
       MaxNodo:=Nodo;
       Nodo:=Nodo^.IZQ;
       MaxNodo^.IZQ:=A^.IZQ;
       MaxNodo^.DER:=A^.DER;
       A:=MaxNodo;
    end
    else CambiarRaiz(A^.DER) {Buscamos el elemento m s grade}
    end;
begin
if (A<>NIL) then
   if (A^.N=N)then begin
      NodoViejo:=A;
      if A^.IZQ=NIL then {No tiene hijo izq}
         A:=A^.DER
      else if A^.DER=NIL then {No tiene hijo der}
           A:=A^.IZQ
           else CambiarRaiz(A^.IZQ); {Tiene dos hijos}
      dispose(NodoViejo);
      Borrar(A,N);
   end
   else if N>A^.N then Borrar(A^.DER,N)
        else Borrar(A^.IZQ,N)
end;

Function Pertenece(A:tArbol; N:Integer):Boolean;
Begin
if (A=nil) then Pertenece:=FALSE
else if (A^.N=N) then Pertenece:=TRUE
     else if (N>A^.N) then Pertenece:=Pertenece(A^.DER,N)
          else Pertenece:=Pertenece(A^.IZQ,N)
end;

Procedure CrearArbol(Var A:tArbol);
begin
A:=nil
end;

Procedure CrearNodo(N:Integer; Var Nodo:tArbol);
begin
     new(Nodo);
     Nodo^.N:=N;
     Nodo^.IZQ:=nil;
     Nodo^.DER:=nil;
end;

Procedure Imprimir(A:tArbol;Orden:byte);
{Orden=0 Pre Orden}
{Orden=1 En Orden}
{Orden=2 Post Orden}
Begin
 if (a<>nil) then begin
    if Orden=0 then WRITELN(A^.N);
    Imprimir(A^.IZQ,Orden);
    if Orden=1 then WRITELN(A^.N);
    Imprimir(A^.DER,Orden);
    if Orden=2 then WRITELN(A^.N);
 end;
end;

Procedure Insertar(VAR A:tArbol;N:Integer);
Var aux:tArbol;
Begin
     if (A=NIL) then begin
           CrearNodo(N,AUX);
           A:=aux
      end
      else begin
           if(N>A^.N) then Insertar(A^.DER,N)
           else Insertar(A^.IZQ,N);
      end;
end;


Function Max(A:tArbol):Integer;
begin
if (A<>nil)then
   if (A^.DER=nil) then Max:=A^.N
   else Max:=Max(A^.DER);
end;

Function Min(A:tArbol):Integer;
begin
if (A<>nil)then
   if (A^.IZQ=nil) then Min:=A^.N
   else Min:=Min(A^.IZQ);
end;

Function NroNodos(A:tArbol):Integer;
begin
if (a=nil)then NroNodos:=0
else NroNodos:=( NroNodos(A^.IZQ) + NroNodos(A^.DER) )+1
end;

Function Altura(A:tArbol):Integer;
 Function Mayor(N1,N2:Integer):Integer;
 begin
      if N1>N2 then Mayor:=N1
      else Mayor:=N2
 end;
begin
if (a=nil) then Altura:=0
else Altura:= Mayor( Altura(A^.IZQ) ,Altura(A^.DER) ) + 1
end;

begin

end.
