escompleto.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION
 Ejercicio tomado en el Ex\'amen Final del 28/2/2002:
 se dice que un \'arbol binario es completo si cada nodo del
 mismo o bien es una hoja o bien tiene sus dos hijos.
 Escribir una funci\'on recursiva ES_COMPLETO (a: arbol) :
 boolean, la cual retorna verdadero si el \'arbol binario 'a'
 es completo. Usar las funciones de \'arbol binario:
 HIJO_IZQUIERDO (n), HIJO_DERECHO (n), ETIQUETA (n).
 keywords: arbol binario

FIN DE DESCRIPCION }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: escompleto.pas 2002/04/05 12:10 mstroti Exp jdelia $}
program prueba;

uses u_arbbii ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function SIGUIENTE_FICHA (var pos: integer; s: string): char;
begin
   SIGUIENTE_FICHA := s [pos];
   pos := pos + 1;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure DEVUELVE_FICHA (var pos: integer; s:string);
begin
   pos := pos - 1;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CREA_DE_STRING_REC (s: string;
         var bosque: bosque_arbbii;
         var    pos: integer): curs_nodo ;
var
  eti    : integer;
  f, aux : char;
  n1, n2 : curs_nodo;
begin
  f := SIGUIENTE_FICHA (pos, s);
  if (f ='0') then
    CREA_DE_STRING_REC := lambda
  else if ( f in ['0'..'9'] ) then begin
    eti := ord (f) - ord ('0');
    aux := SIGUIENTE_FICHA (pos, s);
    if ( aux = '{' ) then
      begin
      n1  := CREA_DE_STRING_REC (s, bosque, pos);
      aux := SIGUIENTE_FICHA (pos, s);
      if ( aux <> ',' ) then begin
        writeln ('No puede encontrar ","');
        exit;
      end ; {if}
      n2  := CREA_DE_STRING_REC (s, bosque, pos);
      aux := SIGUIENTE_FICHA (pos,s);
      if ( aux <> '}' ) then begin
        writeln ('No puede encontrar ","');
        exit ;
      end ; {if}
      CREA_DE_STRING_REC := bosque.crea2 (eti,n1,n2);
      end
    else begin
      DEVUELVE_FICHA (pos, s);
      CREA_DE_STRING_REC := bosque.crea2 (eti,lambda,lambda);
    end ; {if}
  end ; {if}
end ;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CREA_DE_STRING (s: string;
         var bosque: bosque_arbbii): curs_nodo ;
var
  pos : integer;
begin
  pos := 1;
  CREA_DE_STRING := CREA_DE_STRING_REC (s, bosque, pos);
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_PREV (n: curs_nodo; b: bosque_arbbii);
begin
   if (n = lambda) then exit;
   writeln (chr (b.ETIQUETA (n)),' ');
   ORD_PREV (b.HIJO_IZQ (n),b);
   ORD_PREV (b.HIJO_DER (n),b);
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure IMPRIME_S (n: curs_nodo; b: bosque_arbbii);
var
   mi, md: curs_nodo;
begin
   if (n = lambda) then begin
      write ('0');
      exit ;
   end ;
   write ( chr (b.ETIQUETA(n)));
   mi := b.HIJO_IZQ (n);
   md := b.HIJO_DER (n);
   if (mi <> lambda) or (md <> lambda) then begin
     write ('{');
     IMPRIME_S (mi,b);
     write (',');
     IMPRIME_S(md,b);
     write('}');
   end ; {if}
   if (b.PADRE (n) = lambda) then writeln ('');
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function ES_COMPLETO (n: curs_nodo;
                      b: bosque_arbbii): boolean;
begin
 if (n = lambda) then
   ES_COMPLETO := false
 else if (b.HIJO_IZQ (n) = lambda) <>
         (b.HIJO_DER (n) = lambda) then
   ES_COMPLETO := false
 else begin
   ES_COMPLETO :=
   ( b.HIJO_IZQ (n) = lambda) or
   ( ES_COMPLETO (b.HIJO_IZQ (n),b) and
     ES_COMPLETO (b.HIJO_DER (n),b)     )
 end ; {if}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ES_COMPLETO_S (s: string; b: bosque_arbbii);
var
  n :  curs_nodo;
begin
  n := crea_de_string (s,b);
  writeln ('El arbol ',s,' es completo ? ',ES_COMPLETO (n,b));
  b.ANULA (n);
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
  bosque: bosque_arbbii; {El bosque donde estan los arboles }
begin
  bosque.INICIALIZA_NODOS;
  ES_COMPLETO_s ('1{3,5{6{0,7},9}}',bosque); {NO es completo}
  ES_COMPLETO_s ('1{3,5{6{3,7},9}}',bosque); {SI es completo}
  ES_COMPLETO_s ('1{0,5{6{3,7},9}}',bosque); {NO es completo}
  ES_COMPLETO_s ('1{8,5{6{3,7},9{4,2}}}',bosque); { SI lo es}
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}