cuentaprof.pas

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

  Escribir una function CUENTA_PROF (n: nodo; m: integer;
  A: arbol): integer; que dado un nodo n en un \'arbol A
  cuenta el n\'umero de nodos del sub\'arbol de A cuya
  raiz es n y que est\'an a profundidad m o menor (con
  respecto a n). [Tomado en el Examen Final del 11 de
  julio de 2002] keywords: arbol

FIN DE DESCRIPCION }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: cuentaprof.pas 2002/07/12 20:30 mstorti Exp mstorti$ }
program cuentaprof_p;
uses u_arborip;
type
  arbol = arborip;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CUENTA_PROF (n: nodo;m: integer;a: arbol): integer;
var
  c : nodo;
  s : integer;
begin
  { El nodo no existe o la profundidad es negativa }
  if (n = lambda) or (m < 0) then
    s := 0
  else begin
    { El nro de nodos es igual a 1 mas el nro de nodos de }
    { los hijos con una profundidad tope menor en uno     }
    s := 1;
    c := a.HIJO_MAS_IZQ (n);
    while (c <> lambda) do begin
      s := s + CUENTA_PROF (c,m-1,a);
      c := a.HERMANO_DER (c);
    end;
   end;
   CUENTA_PROF := s;
end; { CUENTA_PROF }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CUENTA_HIJOS (n: nodo; a: arbol): integer;
var
   c : nodo;
begin
   c := a.HIJO_MAS_IZQ (n);
   cuenta_hijos := 0;
   while (c <> lambda) do begin
      cuenta_hijos := cuenta_hijos + 1;
      c := a.hermano_der(c);
   end; {while}
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CUENTA_HERM (n: nodo; a: arbol): integer;
begin
   CUENTA_HERM := CUENTA_HIJOS (a.PADRE (n), a);
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ Genera un arbol aleatorio con nn nodos }
procedure RANDOM_ARB (a :arbol;  nn :integer );
var
  j, m, k, v: integer ;
  max_herm  : integer;
  n, q	    : nodo;
begin
  a.ANULA (a.RAIZ);
  m := 100;
  max_herm := 4;
  n := a.AGREGA_HIJO_MAS_IZQ (random (m), lambda);
  for j := 1 to nn do begin
    for k :=1 to 20 do begin
      if    (random (2) = 0)
        and (a.HIJO_MAS_IZQ (n) <> lambda) then
        n := a.HIJO_MAS_IZQ (n)
      else begin
        q := a.HERMANO_DER (n);
        if (q =lambda)  then q := a.PADRE (n);
        if (q <>lambda) then n := q;
      end; {if}
    end; {k}
    if   (random (3) = 0)
      or (a.PADRE (n) = lambda)
      or (CUENTA_HERM (n,a) >= max_herm) then begin
      while (CUENTA_HIJOS (n,a) >= max_herm) do begin
        n := a.HIJO_MAS_IZQ (n);
      end ; {while}
      v := random (m);
      a.AGREGA_HIJO_MAS_IZQ (v,n); end {then}
    else begin
      v := random (m);
      a.AGREGA_HERM_DER (v,n);
    end; {if}
  end; {j}
end; { RANDOM_ARB }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
  a                 : arbol;
  n                 : nodo;
  prof, cant, cantt : integer;
begin
  a.INICIALIZA;
  { Crea un arbol aleatorio con 10 nodos }
  RANDOM_ARB (a,10);
  a.IMPRIME_ARB ('arbol: ');
  n := a.RAIZ;
  cant := 0;
  prof := 0 ;
 {Va calculando la cantidad de nodos hasta profundidad prof}
 {con prof variable. Cuando da lo mismo en prof y prof+1 }
 {es que se acabaron los nodos. }
  while true do begin
    cantt := CUENTA_PROF (n, prof, a);
    if (cantt = cant) then break;
    cant := cantt;
    writeln (cantt,' nodos hasta el nivel ', prof);
    prof := prof + 1;
  end; {while}
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}