verifsum.pas

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

En un programa de dise\~no asistido por computadora
(tipo AutoCAD) se desea mantener las piezas de un sistema
(por ejemplo un auto) clasificando sus partes en la forma
de un \'arbol, donde sus nodos interiores representan
sistemas del auto (planta motriz, direccion, carroceria),
sus hijos subs-sistemas y asi siguiendo hasta las hojas
que son los componentes indivisibles del automovil (por
ej. el tornillo de fijaci\'on del espejo retrovisor
izquierdo).

Se quiere mantener en cada hoja el peso (en Kilogramos)
del componente, y en los nodos interiores el peso total
de todos los componentes del sub\'arbol que cuelga de ese
nodo. Peri\'odicamente se quiere verificar que efectivamente
las etiquetas del \'arbol verifican esta propiedad, es
decir que la etiqueta de los nodos interiores es la
suma de las hojas del sub\'arbol que cuelga de \'el.

Escribir una function VERIFICA_SUMA (n: nodo; A: Arbol):
boolean; que retorna true si el subarbol que cuelga del nodo
verifica la condicion dada y false en caso contrario. Usar
las primitivas del `TAD ARBOL ORDENADO ORIENTADO':
`HIJO_MAS_IZQ (n,A)', `HERMANO_DER (n,A)',`ETIQUETA (n,A)'.
[Tomado en el segundo parcial del cursado 2002, 28/5/2002.]
keywords: arbol orientado

FIN DE DESCRIPCION }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: verifsum.pas 2002/05/22 19:59 mstorti Exp mstorti $  }
program verif_sum;
uses u_arborip;
type
   arbol = arborip;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function VERIFICA_SUMA (n: nodo; a: arbol) : boolean;
var
  c : nodo;
  s : integer;
begin
  c := a.HIJO_MAS_IZQ (n);
  if (c = lambda) then { Si el nodo es hoja entonces OK }
    VERIFICA_SUMA := true
  else begin
    s := 0;
    while (c <> lambda) do begin
      { Verifica que cada hijo satisface la condici\'on }
      if not VERIFICA_SUMA (c,a) then begin
         VERIFICA_SUMA := false;
         exit;
      end; {if}
      { Suma las etiquetas de los hijos }
      s := s + a.ETIQUETA (c);
      c := a.HERMANO_DER (c);
    end; {while}
    { Verifica que la suma sea igual a la etiqueta del nodo }
    VERIFICA_SUMA := (s = a.ETIQUETA (n));
   end; {if}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   a, b         : arbol;
   n, n100, n80 : nodo;
begin
   { inicializa arbol A } 
   a.INICIALIZA;
   n100 := a.AGREGA_HIJO_MAS_IZQ (100,lambda);
   n80  := a.AGREGA_HIJO_MAS_IZQ ( 80,n100);
   n    := a.AGREGA_HIJO_MAS_IZQ ( 70,n80);
   n    := a.AGREGA_HERM_DER     ( 10,n);
   n    := a.AGREGA_HERM_DER     ( 20,n80);
   n    := a.AGREGA_HIJO_MAS_IZQ (  5,n);
   n    := a.AGREGA_HERM_DER     ( 15,n);
   a.IMPRIME_ARB ('arbol A: ');
   writeln ('Satisface condicion de suma: ',
	     VERIFICA_SUMA (a.RAIZ, a));

   { inicializa arbol B }
   b.inicializa;
   n100 := b.AGREGA_HIJO_MAS_IZQ (100,lambda);
   n80  := b.AGREGA_HIJO_MAS_IZQ ( 80,n100);
   n    := b.AGREGA_HIJO_MAS_IZQ ( 71,n80);
   n    := b.AGREGA_HERM_DER     ( 10,n);
   n    := b.AGREGA_HERM_DER     ( 20,n80);
   n    := b.AGREGA_HIJO_MAS_IZQ (  5,n);
   n    := b.AGREGA_HERM_DER     ( 16,n);
   b.IMPRIME_ARB ('arbol B: ');
   writeln ('Satisface condicion de suma: ',
	     VERIFICA_SUMA (b.RAIZ, b));

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