maxhoja.pas

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

a) Escribir un procedure HOJAS (A: arbol; n: nodo);
   que lista las etiquetas de las hojas de un \'arbol
   ordenado orientado. Por ejemplo, en el
   \'arbol (142 (63 (33) 42 (23 7 35)) 48 125 (130 12))
   debe listar: 33 23 7 35 48 130 12.
b) Escribir una function MAXHOJA (A: arbol; n: nodo):integer;
   que retorna el m\'aximo de las etiquetas de las hojas
   de un \'arbol ordenado orientado. Por ejemplo, en el
   \'arbol (142 (63 (33) 42 (23 7 35)) 48 125 (130 12))
   debe retornar 130.
keywords: arbol orientado

FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ Ejemplo:  142
          /  |  \
       63   48  125
      /  \      /  \
    33   42   130  12
        / | \
      23  7 35 }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: maxhoja.pas v3 2003/04/14  7:02 mstorti Exp jdelia $}
program  phojas;
uses u_arbori;
type
   bosque = bosque_arbori;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure HOJAS (A: bosque; n: curs_nodo);
var
   c : curs_nodo;
begin
  if (n = lambda) then
  else if (A.HIJO_MAS_IZQ (n) = lambda) then {Es una hoja}
    writeln ('hoja = ', A.ETIQUETA (n) )
  else begin { Es un nodo interior }
    c := A.HIJO_MAS_IZQ (n);
    while (c <> lambda) do begin
      HOJAS (A, c);
      c := A.HERMANO_DER (c);
    end; {while}
  end; {if}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function MAXHOJA (A : bosque; n : curs_nodo) : integer;
var
   c   : curs_nodo;
   r, v: integer;
begin
   r := 0;
   if (n = lambda) then
    { No hace nada. r=0 esta OK }
   else if (A.HIJO_MAS_IZQ (n) = lambda) then
    {Es una hoja, retorna la etiqueta. }
    r := A.ETIQUETA (n)
   else begin
    {Es un nodo interior. Retorna el maximo de los MAXHOJAS}
    {de los hijos: Sin tener en cuenta la etiqueta de n!!}
    c := A.HIJO_MAS_IZQ (n);
    while (c <> lambda) do begin
       v := MAXHOJA (A,c);
       if (v > r) then r := v;
       c := A.HERMANO_DER (c);
    end; {while}
  end; {if}
  MAXHOJA := r;
end;

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

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

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_SIM (B: bosque; n: curs_nodo);
var
  c : curs_nodo;
begin
  if (n <> lambda) then begin
    c := B.HIJO_MAS_IZQ (n);
    ORD_SIM (B, c);
    write (B.ETIQUETA (n),' ');
    if (c <> lambda) then begin
      c := B.HERMANO_DER (c);
      while (c <> lambda) do begin
        ORD_SIM (B, c);
        c := B.HERMANO_DER (c);
      end; {while}
    end; {if}
  end; {if}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   A    : bosque ;
   carb : array [1..100] of curs_nodo;
   n    : curs_nodo;
begin
   A.INICIALIZA_NODOS;
   carb [1] := A.CREA0 (33);
   carb [2] := A.CREA0 (23);
   carb [3] := A.CREA0 (7);
   carb [4] := A.CREA0 (35);
   carb [5] := A.CREA0 (130);
   carb [6] := A.CREA0 (12);
   carb [7] := A.CREA3 (42, carb [2], carb [3], carb [4]);
   carb [8] := A.CREA2 (63, carb [1], carb [7]);
   carb [9] := A.CREA0 (48);
   carb [10]:= A.CREA2 (125, carb [5], carb [6]);
   n := A.CREA3 (142, carb [8], carb [9], carb [10]);
   writeln ;
   writeln ('listado en orden previo');
   ORD_PREV (A, n);
   writeln ;
   writeln ;
   HOJAS (A,n);
   writeln ;
   writeln ('MAXHOJA: ', MAXHOJA (A,n));
   writeln ;
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}