{Terreno Antonio mat.9714216}
unit
   alberi;

interface

uses
   crt;
type
   tipo_elemento=integer;
   tipo_albero=^nodo;
   nodo= record
           el:tipo_elemento;
      sx,dx:tipo_albero
           end;

   procedure inserisci_elemento(var T:tipo_albero;x:tipo_elemento);
   procedure leggi_da_tastiera(var T:tipo_albero);
   procedure cancella_elemento(var T:tipo_albero;x:tipo_elemento);
   procedure dealloca_albero(var T:tipo_albero);
   function trova_elemento(x:tipo_elemento;T:tipo_albero):boolean;
   function altezza(T:tipo_albero):integer;
   procedure stampa_foglie(T:tipo_albero);
   function somma_valori_nodi(T:tipo_albero):integer;
   function numero_nodi(T:tipo_albero):integer;
   function num_nodi_fino(T:tipo_albero;sup:integer):integer;
   function num_nodi_dopo(T:tipo_albero;inf:integer):integer;
   function num_nodi_tra(T:tipo_albero;inf,sup:integer):integer;
   function num_nodi_a(T:tipo_albero;n:integer):integer;
   procedure stampa_albero(T:tipo_albero);
   procedure stampa_anticipato(T:tipo_albero);
   procedure stampa_posticipato(T:tipo_albero);
   procedure stampa_simmetrico(T:tipo_albero);

implementation

{funzioni,procedure che modificano l'albero}

procedure inserisci_elemento(var T:tipo_albero;x:tipo_elemento);
{ inserisce un elemento rispettando la proprieta' dell' albero binario di ricerca }
begin
   if (T=nil) then
      begin
         new(T);
         T^.el:=x;
         T^.sx:=nil;
         T^.dx:=nil
      end
   else if (T^.el<x) then
      inserisci_elemento(T^.dx,x)
   else if (T^.el>x) then
      inserisci_elemento(T^.sx,x)
end;

procedure leggi_da_tastiera(var T:tipo_albero);
{ legge da tasiera una sequenza di variabili tipo_elemento inserendo
 ogni elemento in un albero binario di ricerca }
var
   x:tipo_elemento;
begin
   T:=nil;
   while (not eoln) do
      begin
         read(x);
    inserisci_elemento(T,x);
      end
end;

function cancella_min(var T:tipo_albero):tipo_elemento;
{ cancella l'elemento piu' piccolo nell'abr T }
var
   tmp:tipo_albero;
begin
   if (T<>nil) then
      if (t^.sx<>nil) then
         cancella_min:=cancella_min(T^.sx)
      else
         begin
       cancella_min:=T^.el;
       tmp:=T;
       T:=T^.dx;
       dispose(tmp);
    end
end;

procedure cancella_elemento(var T:tipo_albero;x:tipo_elemento);
{cancella e dealloca il nodo di etichetta x}
var
   tmp:tipo_albero;
begin
   if (T<>nil) then
      if (T^.el<x) then
         cancella_elemento(T^.dx,x)
      else if (T^.el>x) then
         cancella_elemento(T^.sx,x)
      else if(T^.sx=nil)then
         begin
       tmp:=T;
       T:=t^.dx;
       dispose(tmp)
    end
      else if (T^.dx=nil) then
         begin
       tmp:=T;
       T:=T^.sx;
       dispose(tmp)
    end
      else
         T^.el:=cancella_min(T^.dx)
end;

procedure dealloca_albero(var T:tipo_albero);
{ dealloca un albero binario }
var
   tmp:tipo_albero;
begin
   if (T<>nil) then
      begin
         dealloca_albero(T^.dx);
    dealloca_albero(T^.sx);
    if (T^.sx=nil) then
       begin
          tmp:=T;
          T:=t^.dx;
          dispose(tmp)
       end
    else if (T^.dx=nil) then
       begin
          tmp:=T;
          T:=T^.sx;
          dispose(tmp)
       end
      end
end;

{predicati su alberi}

function trova_elemento(x:tipo_elemento;T:tipo_albero):boolean;
{ true se x e' nell' abr T false altrimenti }
begin
   if (T=nil) then
      trova_elemento:=false
   else if (T^.el=x) then
      trova_elemento:=true
   else if (T^.el>x) then
      trova_elemento:=trova_elemento(x,T^.sx)
   else
      trova_elemento:=trova_elemento(x,T^.dx)
end;

function max(x,y:integer):integer;
{ ritorna il massimo tra x e y (utilizzata in altezza) }
begin
     if (x>y) then
        max:=x
     else
        max:=y
end;

function altezza(T:tipo_albero):integer;
{ calcola l'altezza di un albero binario }
begin
   if(T=nil)then
      altezza:=-1
   else
      altezza:=1+max(altezza(T^.sx),altezza(T^.dx))
end;

{funzioni,procedure sulle foglie}

procedure stampa_foglie(T:tipo_albero);
{ stampa le foglie di un albero binario }
begin
   if (T<>nil) then
      if (T^.sx<>nil) and (T^.dx<>nil) then
         begin
       stampa_foglie(T^.sx);
       stampa_foglie(T^.dx)
    end
      else if (T^.sx<>nil) and (T^.dx=nil) then
         stampa_foglie(T^.sx)
      else if (T^.sx=nil) and (T^.dx<>nil) then
         stampa_foglie(T^.dx)
      else
         write(T^.el,' ')
end;

function is_leaf(T:tipo_albero):boolean;
{ true se T e' una foglia }
begin
   is_leaf:=(T<>nil)and(T^.sx=nil)and(T^.dx=nil)
end;

function num_foglie(T:tipo_albero):integer;
{ ritorna il numero di foglie }
begin
   if (T=nil) then
      num_foglie:=0
   else if (is_leaf(T)) then
      num_foglie:=1
   else
      num_foglie:=num_foglie(T^.sx)+num_foglie(T^.dx)
end;


{funzioni,procedure sui nodi}

function somma_valori_nodi(T:tipo_albero):integer;
{ ritorna la somma dei valori dei nodi }
begin
   if (T=nil) then
      somma_valori_nodi:=0
   else
      somma_valori_nodi:=somma_valori_nodi(T^.sx)+
                          somma_valori_nodi(T^.dx)+T^.el
end;

function numero_nodi(T:tipo_albero):integer;
{ ritorna il numero  dei nodi }
begin
   if (T=nil) then
      numero_nodi:=0
   else
      numero_nodi:=numero_nodi(T^.sx)+numero_nodi(T^.dx)+1
end;

function num_nodi_fino(T:tipo_albero;sup:integer):integer;
{ritorna il numero dei nodi fino al livello sup compreso}
begin
   if (T=nil) or (sup<0) then
      num_nodi_fino:=0
   else
      num_nodi_fino:=1+num_nodi_fino(T^.sx,sup-1)+
                      num_nodi_fino(T^.dx,sup-1)
end;

function num_nodi_dopo(T:tipo_albero;inf:integer):integer;
{ritorna il numero dei nodi dopo il livello inf compreso}
begin
   if (T=nil) then
      num_nodi_dopo:=0
   else if (inf>0) then
      num_nodi_dopo:=num_nodi_dopo(T^.sx,inf-1)+
                      num_nodi_dopo(T^.dx,inf-1)
   else
      num_nodi_dopo:=num_nodi_dopo(T^.sx,inf)+
                      num_nodi_dopo(T^.dx,inf)+1
end;

function num_nodi_tra(T:tipo_albero;inf,sup:integer):integer;
{ritorna il numero dei nodi tra inf e sup}
begin
   if (T=nil) or (sup<0) then
      num_nodi_tra:=0
   else if (inf>0) then
      num_nodi_tra:=num_nodi_tra(T^.sx,inf-1,sup-1)+
                     num_nodi_tra(T^.dx,inf-1,sup-1)
   else
      num_nodi_tra:=num_nodi_tra(T^.sx,inf-1,sup-1)+
                     num_nodi_tra(T^.dx,inf-1,sup-1)+1
end;

function num_nodi_a(T:tipo_albero;n:integer):integer;
{ritorna il numero dei nodi al livello n}
begin
   if (T=nil) or (n<0) then
      num_nodi_a:=0
   else if (n>0) then
      num_nodi_a:=num_nodi_a(T^.sx,n-1)+
                   num_nodi_a(T^.dx,n-1)
   else
      num_nodi_a:=num_nodi_a(T^.sx,n-1)+
                   num_nodi_a(T^.dx,n-1)+1
end;

{procedure di stampa}

procedure stampa_albero(T:tipo_albero);
{ stampa a video la reale collocazione degli elementi }
var
   Xmed:integer;

   procedure __stampa(T:tipo_albero;Xinf,Xsup,Y:integer);
      begin
         if (T<>nil) then
       begin
          Xmed:=(Xinf+Xsup) div 2;
          gotoxy(Xmed,Y);
          write(T^.el,' ');
          gotoxy(Xmed-1,Y+1);
          write('ÚÁ¿');
          __stampa(T^.sx,Xinf,Xmed,Y+2);
          __stampa(T^.dx,Xmed+1,Xsup,Y+2)
       end
      end;

begin
   __stampa(T,1,80,2);
end;{stampa_albero}

procedure stampa_anticipato(T:tipo_albero);
{stampa le etichette dell'albero in ordine anticipato}
begin
   if (T<>nil) then
      begin
         write(T^.el,' ');
    stampa_anticipato(T^.sx);
    stampa_anticipato(T^.dx);
      end
end;

procedure stampa_posticipato(T:tipo_albero);
{stampa le etichette dell'albero in ordine posticipato}
begin
   if (T<>nil) then
      begin
         stampa_posticipato(T^.sx);
    stampa_posticipato(T^.dx);
    write(T^.el,' ');
      end
end;

procedure stampa_simmetrico(T:tipo_albero);
{stampa le etichette dell'albero in ordine simmetrico}
begin
   if (T<>nil) then
      begin
         stampa_simmetrico(T^.sx);
    write(T^.el,' ');
    stampa_simmetrico(T^.dx);
      end
end;

end.