iguales.pas

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

 Ejercicio tomado en el 2do parcial/01: verificar si dos
 \'arboles ordenados y orientados son iguales, es decir,
 si tienen la misma estructura y contenido.
 keywords: arbol orientado

FIN DE DESCRIPCION }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: iguales.pas  2002/04/05 13:30 mstorti Exp jdelia $  }
program iguales_ord;
uses u_arbori;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function IGUALES (n1, n2: curs_nodo;
                  B: Bosque_ArbOri): boolean;
var
  c1, c2 : curs_nodo;
begin
  { O los dos son lambda o los dos son diferentes de lambda }
  { Aqui el <> funciona como un xor }
  if (n1 = lambda) <> (n2 = lambda) then begin
    IGUALES := false;
    exit;
  end; {if}

  { Dos arboles vacios son iguales }
  if (n1 = lambda) and (n2 = lambda) then begin
    IGUALES := true ;
    exit;
  end; {if}

  { Si las etiquetas del nodo son diferentes son distintos }
  if B.ETIQUETA (n1) <> B.ETIQUETA (n2) then begin
    IGUALES := false;
    exit;
  end; {if}

  { Recorre las listas de hijos y compara recursivamente }
  c1 := B.HIJO_MAS_IZQ (n1);
  c2 := B.HIJO_MAS_IZQ (n2);
  while (c1 <> lambda) and (c2 <> lambda) do begin
    if not IGUALES (c1,c2,B) then begin
      IGUALES := false;
      exit;
    end; {if}
    c1 := B.HERMANO_DER (c1);
    c2 := B.HERMANO_DER (c2);
  end ; {while}

  { Las dos listas de hijos deben tener la misma longitud }
  IGUALES := (c1 = lambda) and (c2 = lambda);
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   BB : Bosque_ArbOrI;
   arbol, arb1, arb2, arb3, arb4, arb5      : curs_nodo;
   arb6, arb7, arb8, arb9, arb0             : curs_nodo;
   arbolb, arbb1, arbb2, arbb3, arbb4, arbb5: curs_nodo;
   arbolc, arbb6, arbb7, arbb8, arbb9, arbb0: curs_nodo;
begin

   BB.INICIALIZA_NODOS;

   arb1   := BB.CREA0 (33);
   arb2   := BB.CREA0 (8);
   arb3   := BB.CREA0 (7);
   arb4   := BB.CREA0 (62);
   arb5   := BB.CREA0 (130);
   arb6   := BB.CREA0 (12);
   arb7   := BB.CREA3 (41,arb2,arb3,arb4);
   arb8   := BB.CREA2 (63,arb1,arb7);
   arb9   := BB.CREA0 (48);
   arb0   := BB.CREA2 (125,arb5,arb6);

   arbol  := BB.CREA3 (142,arb8,arb9,arb0);

   arbb1  := BB.CREA0 (33);
   arbb2  := BB.CREA0 (8);
   arbb3  := BB.CREA0 (7);
   arbb4  := BB.CREA0 (62);
   arbb5  := BB.CREA0 (130);
   arbb6  := BB.CREA0 (12);
   arbb7  := BB.CREA3 (41,arbb2,arbb3,arbb4);
   arbb8  := BB.CREA2 (63,arbb1,arbb7);
   arbb9  := BB.CREA0 (48);
   arbb0  := BB.CREA2 (125,arbb5,arbb6);

   arbolb := BB.CREA3 (142,arbb8,arbb9,arbb0);

   arbb1  := BB.CREA0 (33);
   arbb2  := BB.CREA0 (8);
   arbb3  := BB.CREA0 (7);
   arbb4  := BB.CREA0 (62);
   arbb5  := BB.CREA0 (130);
   arbb6  := BB.CREA0 (16);
   arbb7  := BB.CREA3 (41,arbb2,arbb3,arbb4);
   arbb8  := BB.CREA2 (63,arbb1,arbb7);
   arbb9  := BB.CREA0 (48);
   arbb0  := BB.CREA2 (125,arbb5,arbb6);

   arbolc := BB.CREA3 (142,arbb8,arbb9,arbb0);

   writeln('iguales ? ',IGUALES (arbol,arbb1,BB));
   writeln('iguales ? ',IGUALES (arbol,arbolb,BB));
   writeln('iguales ? ',IGUALES (arbol,arbolc,BB));
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}