uses
   crt;
const
   Lmax=15;
type
   tipo_elemento=integer;
   tipo_vettore=array[1..Lmax] of tipo_elemento;
   tipo_albero=^nodo;
   nodo=record
            el:tipo_elemento;
            sx,dx:tipo_albero
         end;

{funzioni,procedure che modificano l'albero}

procedure inserisci_elemento(var T:tipo_albero;x:tipo_elemento);

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);

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;

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);

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;

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;

begin
   if(x>y)then
      max:=x
   else
      max:=y
end;

function altezza(T:tipo_albero):integer;

begin
   if(T=nil)then
      altezza:=-1
   else
      altezza:=1+max(altezza(T^.sx),altezza(T^.dx))
end;

function is_completo(T:tipo_albero):boolean;

begin
   if(T=nil)or((T^.sx=nil)and(T^.dx=nil))then
      is_completo:=true
   else
      if(T^.sx<>nil)and(T^.dx<>nil)then
         is_completo := is_completo(T^.sx) and is_completo(T^.dx)
      else
         is_completo:=false

end;

{funzioni,procedure sulle foglie}

procedure stampa_foglie(T:tipo_albero);

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;

begin
   is_leaf:=(T<>nil)and(T^.sx=nil)and(T^.dx=nil)
end;

function num_foglie(T:tipo_albero):integer;

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 di confronto alberi}

function alberi_uguali(T1,T2:tipo_albero):boolean;

begin
   if(T1=nil)and(T2=nil)then
      alberi_uguali:=true
   else if(T1=nil)and(T2<>nil)then
      alberi_uguali:=false
   else if(T1<>nil)and(T2=nil)then
      alberi_uguali:=false
   else if(T1^.el<>T2^.el)then
      alberi_uguali:=false
   else
      alberi_uguali:=alberi_uguali(T1^.sx,T2^.sx)and
                        alberi_uguali(T1^.dx,T2^.dx)
end;

{funzioni,procedure sui nodi}

function somma_valori_nodi(T:tipo_albero):integer;

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;

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);

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;

procedure stampa_cammino(T:tipo_albero;x:tipo_elemento);

begin
   if(T<>nil)then
      begin
         write(T^.el,' ');
         if(T^.el<x)then
            stampa_cammino(T^.dx,x)
         else
            stampa_cammino(T^.sx,x)
      end
end;

{procedure sui vettori}

procedure crea_vettore_ordinato(var a:tipo_vettore);

var
   i:integer;
begin
   for i:=1 to Lmax do
      a[i]:=i
end;

procedure stampa_vettore(var V:tipo_vettore);

var
   i:integer;
begin
   for i:=1 to Lmax do
      write(V[i],' ');
end;

{temi d'esame}

procedure maggiori(T:tipo_albero;x:tipo_elemento);
{es.2 12.4.96}
begin
   if(T<>nil)then
      if(T^.el>x)then
         begin
            write(T^.el);
            maggiori(T^.sx,x);
            maggiori(T^.dx,x)
         end
      else if(T^.el<x)then
         maggiori(T^.dx,x)
end;

function cons(x:tipo_elemento;T1,T2:tipo_albero):tipo_albero;

var
   tmp:tipo_albero;
begin
   new(tmp);
   tmp^.el:=x;
   tmp^.sx:=T1;
   tmp^.dx:=T2;
   cons:=tmp
end;

function copia_prefisso(T:tipo_albero;n:integer):tipo_albero;
{es.2 26.6.96}
begin
   if(T=nil)or(n<0)then
      copia_prefisso:=nil
   else  copia_prefisso:=cons(T^.el,copia_prefisso(T^.sx,n-1),
                                       copia_prefisso(T^.dx,n-1))
end;

procedure P(T:tipo_albero);
{es1 20.9.96}
begin
   if(T=nil)then
      write('()')
   else
      begin
         write('(');
         P(T^.sx);
         write(T^.el);
         P(T^.dx);
         write(')');
      end
end;


function costruisci(var a:tipo_vettore):tipo_albero;
{ da vettore in albero }
{es.3 20.10.96}
   function costr(inf,sup:integer):tipo_albero;
   var
      med:integer;
   begin
   if(inf>sup)then
      costr:=nil
   else
      begin
         med:=(inf+sup) div 2;
         costr:=cons(a[med],costr(inf,med-1),costr(med+1,sup))
      end
end;

begin
   costruisci:=costr(1,Lmax);
end;

function incluso(T1,T2:tipo_albero):boolean;
{es.3 8.1.97}
{true se T1 incluso in T2}
begin
   if(T1=nil)then
      incluso:=true
   else if(T2=nil)then
      incluso:=false
   else if(T1^.el<T2^.el)then
      incluso:=incluso(T1,T2^.sx)
   else if(T1^.el<T2^.el)then
      incluso:=incluso(T1,T2^.dx)
   else
      incluso:=(T1^.el=T2^.el)and
                  incluso(T1^.sx,T2^.sx)and
                  incluso(T1^.dx,T2^.dx)
end;

procedure conta(T:tipo_albero;var pari,disp:integer);
{es.1 16.9.97}
   procedure c(T:tipo_albero);

   begin
      if(T<>nil)then
         begin
            if((T^.el mod 2)=0)then
               inc(pari)
            else
               inc(disp);
            c(T^.sx);
            c(T^.dx)
         end
   end;

begin
   pari:=0;
   disp:=0;
   if(T<>nil)then
      c(T);
   writeln(pari);
   writeln(disp);
end;{conta}

function conta_mag_x(T:tipo_albero;x:tipo_elemento):integer;
{ritornailnumerodielementi>=x)
{es.2 3.12.97}
begin
   if(T=nil)then
      conta_mag_x:=0
   else if(T^.el>x)then
      conta_mag_x:=1+conta_mag_x(T^.sx,x)+conta_mag_x(T^.dx,x)
   else if(T^.el=x)then
      conta_mag_x:=1+conta_mag_x(T^.dx,x)
   else
      conta_mag_x:=conta_mag_x(T^.dx,x)
end;

procedure inservett(T:tipo_albero;inf,sup:integer;var V:tipo_vettore;var j:integer);
{inserisce in V in ordine simmetrico i nodi tra inf e sup}
{e ritorna in j il numero di elementi inseriti}
{es.3 3.12.97}
   procedure ins(T:tipo_albero;inf,sup:integer);

   begin
      if(T<>nil)and(sup>=0)then
         begin
            ins(T^.sx,inf-1,sup-1);
            if(inf<=0)then
               begin
                  inc(j);
                  V[j]:=T^.el;
               end;
            ins(T^.dx,inf-1,sup-1)
         end
   end;

begin
   j:=0;
   ins(T,inf,sup);
   writeln('elementi inseriti= ',j);
   write('vettore= ');
   stampa_vettore(V);
end;{inservett}

procedure scrivinv(T:tipo_albero;inf:integer);
{scrive in ordine "anti"simmetrico i nodi dopo inf}
{es.2 31.3.98}
begin
   if(T<>nil)then
      begin
         scrivinv(T^.dx,inf-1);
         if(inf<=0)then
            write(T^.el,' ');
         scrivinv(T^.sx,inf-1);
      end
end;

procedure array_in_albero(var A : tipo_vettore;n:integer; var T: tipo_albero);

var
   i:integer;
begin
   for i:=1 to Lmax do
       inserisci_elemento(T,a[i]);
end;



var
   A,B:tipo_albero;
   V:tipo_vettore;
   m:integer;

begin {main}
   clrscr;
   leggi_da_tastiera(A);
   stampa_albero(A);
   writeln;
   inservett(A,1,2,V,m);
   repeat until keypressed
end.