Esercizi svolti a lezione il 16 Marzo 2001 & Esercizi proposti

(ATTENZIONE: chi trova un errore in questa pagina ricevera' un premio!!!)

Alberi binari (continua)

Lo scopo di questa lezione e' lo stesso delle due lezioni precedenti.

Gli esercizi presentati faranno riferimento alla UNIT "alberi" presentata nel corso di di Programmazione II.

Esercizi svolti a lezione

Consideriamo aberi binari a etichette intere tutte di identico valore (ad esempio il valore 0). Consideriamo le seguenti operazioni su tali alberi:

Unione di forme

Sviluppiamo l'algoritmo procedendo come illustrato la scorsa lezione.

  1. Intestazione 
    {AI: t1, t2 sono inizializzati e "contengono" gli alberi T1 e T2}
{AF: t contiene l'albero unione di T1 e T2,
     T1 e T2 non sono stati modificati, 
     non c'e condivisione di nodi tra albero unione e T1,T2}
procedure u (t1,t2:tree; var t:tree);
  2. Algoritmo "ad alto livello" 

    u([],T) = u(T,[]) = T
u([0,L1,R1],[0,L2,R2]) = [0,u(L1,L2),u(R1,R2)]
  3. Algoritmo in "pseudo-codice" Pascal 

    procedure u (t1,t2:tree; var t:tree);
  begin
    if t1=nil then --copia t2 in t
    else if t2=nil then --copia t1 in t
    else begin
           new t;
           t^.elem:=0;
           u(t1^.left,t2^.left,t^.left);
           u(t1^.right,t2^.right,t^.right);
         end
  end;
  4. Algoritmo in Pascal (CON I COMMENTI) 

    {AI: ti e' inizializzato e "contiene" l'albero T}
{AF: to "contiene" una copia dell'albero T} 
function copia (ti:tree; var to:tree);
begin
  if ti=nil then to:=nil
  else begin
         new to;
         to^.elem:=0;
         copia(ti^.left,to^.left);
         copia(ti^.right,to^.right);
       end
end;

{AI: t1, t2 sono inizializzati e "contengono" gli alberi T1 e T2}
{AF: t contiene l'albero unione di T1 e T2,
     T1 e T2 non sono stati modificati,
     non c'e condivisione di nodi tra albero unione e T1,T2}
procedure u (t1,t2:tree; var t:tree);
{SPECIFICA DELL'ALGORITMO:
u([],T) = u(T,[]) = T
u([0,L1,R1],[0,L2,R2]) = [0,u(L1,L2),u(R1,R2)]
}
  begin
    if t1=nil then copia(t2,t)
    else if t2=nil then copia(t1,t)
    else begin
           new t;
           t^.elem:=0;
           u(t1^.left,t2^.left,t^.left);
           u(t1^.right,t2^.right,t^.right);
         end
  end;

Esercizi proposti

Definire le operazioni rimaste (in un modo che vi sembri ragionevole) e sviluppare i rispettivi programmi.