incluido.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION

Ejercicio tomado en el Ex\'amen final del 14/12/01:
escribir una funci\'on INCLUIDO (B, A: nodo) : boolean, la
cual retorna verdadero si la estructura del \'arbol $B$
est\'a incluida dentro de la del \'arbol $A$. Definiendolo
en forma recursiva, un \'arbol $B$ est\'a incluido en otro
$A$ si: (B=Lambda) or (A<>Lambda). La estructura de los
hijos de $B$ est\'a incluida en la estructura de los
correspondientes hijos de $A$. Se pide:
(a) Explicar el significado de la condici\'on
    (B=Lambda) or (A<>Lambda);
(b) Escribir el procedimiento function INCLUIDO (B,A: nodo):
    boolean, utilizando las funciones PADRE (n,A),
    HIJO_MAS_IZQUIERDO (n,A), HERMANO_DERECHO (n,A),
    ETIQUETA (n,A), CREA0 (v), CREA1 (v,A1), CREA2 (v,A1,A2).

FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{$ Id: incluido.pas  2002/04/05 13:30 mstorti Exp jdelia $  }

program p_incluido ;

uses u_arbori;

type
   bosque = bosque_arbori ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_PREV (A: curs_nodo; B: bosque);
var
  temp : curs_nodo;
begin
  if (A <> lambda) then begin
     writeln  (B.ETIQUETA (A));
     temp := B.HIJO_MAS_IZQ (A);
     while (temp <> lambda) do begin
       ORD_PREV (temp,B);
       temp := B.HERMANO_DER (temp);
     end; {while}
  end; {if}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_POST (A: curs_nodo; B: bosque);
var
  temp : curs_nodo;
begin
  if (A <> lambda) then begin
    temp := B.HIJO_MAS_IZQ (A);
    while (temp <> lambda) do begin
      ORD_POST (temp,B);
      temp := B.HERMANO_DER (temp);
    end; {while}
    writeln (B.ETIQUETA (A));
  end; {if}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function INCLUIDO (B, A: curs_nodo;
                     BB: bosque) : boolean;
var
  mA, mB: curs_nodo;
begin
   if not ( (B = lambda) or (A <> lambda) ) then begin
     INCLUIDO := false;
     exit;
   end; {if}
   mA := BB.HIJO_MAS_IZQ (A);
   mB := BB.HIJO_MAS_IZQ (B);
   while ( mB <> lambda) do begin { B tiene nas hijos que A }
     if not INCLUIDO (mB, mA, BB) then
        begin  {uno de los hijos no es semejante }
        INCLUIDO:=false;
        exit;
     end; {if}
     mA := BB.HERMANO_DER (mA);
     mB := BB.HERMANO_DER (mB);
   end; {while}
   INCLUIDO := true;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   BB                      : bosque;
   n33, n12, n13, n14, n21 : curs_nodo;
begin

   BB.INICIALIZA_NODOS;

   n33 := BB.CREA0 (33);
   n12 := BB.AGREGA_HIJO_MAS_IZQ (n33, 12);
   n14 := BB.AGREGA_HERM_DER     (n12, 14);
   n13 := BB.AGREGA_HIJO_MAS_IZQ (n12, 13);
   n21 := BB.AGREGA_HERM_DER     (n13, 21);

   writeln ('Listado en orden previo: ');
   ORD_PREV (n33, BB);

   writeln ('Listado en orden posterior: ');
   ORD_POST (n33, BB);

   writeln ('Incluido 33 en 33: (deberia ser true ) ',
            INCLUIDO (n33, n33, BB));
   writeln ('Incluido 12 en 33: (deberia ser true ) ',
            INCLUIDO (n12, n33, BB));
   writeln ('Incluido 33 en 12: (deberia ser false) ',
            INCLUIDO (n33, n12, BB));

end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}