cuentaalt.pas

{ COMIENZO DE DESCRIPCION

Escribir una funci\'on function CUENTA_ALT(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 tales que la altura de su
subarbol es de altura menor o igual que m. [Tomado en el Examen
Final del 27 de febrero de 2003] Keywords: arbol orientado

FIN DE DESCRIPCION }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: cuentaprof.pas,v 1.2 2002/07/12 20:30:34 mstorti Exp mstorti $  }

program cuenta_alt_p;

uses u_arborip;
{ uses u_arbori;}

type
   arbol = arborip;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{    RUTINAS AUXILIARES                                     }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CUENTA_ALT(n : nodo; m:integer; var altura: integer; a:arbol):integer;
var
   c : nodo;
   s, max_altura_hijo, altura_hijo : integer;
begin
   { El nodo no existe }
   if (n=Lambda) then
   begin
      s:=0;
      altura := -1;
   end
   else
   begin
      { El numero de nodos que cumple la condicion es igual a}
      { la suma sobre los hijos  mas eventualmente 1 si el nodo}
      { esta a una altura menor o igual que la indicada }
      s:=0;
      max_altura_hijo :=-1; { maxima altura de los hijos }
      c := a.hijo_mas_izq(n);
      while c<>Lambda do
      begin
	 { Calcula la altura del hijo y la cantidad de nodos con}
	 { altura menor que la especificada }
	 s := s + CUENTA_ALT(c,m,altura_hijo,a);
	 { Eventualmente, actualiza la maxima altura de hijo }
	 if altura_hijo>max_altura_hijo then
	    max_altura_hijo := altura_hijo;
	 { Sigue la lista de hijos }
	 c := a.hermano_der(c);
      end;
      { Altura del nodo }
      altura := max_altura_hijo + 1;
      { Si el nodo cumple con la condicion especificada,}
      { entonces suma uno al valor calculado. }
      if  altura <= m then s := s + 1;
   end;
   CUENTA_ALT := s;
end; { CUENTA_PROF }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{    RUTINAS AUXILIARES                                     }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
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;
end; { CUENTA_HIJOS }

function CUENTA_HERM(n	: nodo; a:arbol):integer;
begin
   CUENTA_HERM := cuenta_hijos(a.padre(n),a);
end; { CUENTA_HERM }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ Genera un arbol aleatorio con nn nodos }
procedure RANDOM_ARB(a :arbol;  nn :integer );
var
   j,M,k,v,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;
      end;

      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
	    n := a.hijo_mas_izq(n);
	 v:=RANDOM(M);
	 a.agrega_hijo_mas_izq(v,n);
      end
      else
      begin
	 v:=RANDOM(M);
	 a.agrega_herm_der(v,n);
      end;
   end;
end; { RANDOM_ARB }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   a		     : arbol;
   n		     : nodo;
   alt, cant, cantt,altura  : integer;
begin

   a.inicializa;
   { Crea un arbol aleatorio con 10 nodos }
   randomize;
   random_arb(a,10);
   a.imprime_arb('abol: ');

   n:=a.raiz;
   cant:=0;
   { Va calculando la cantidad de nodos con altura menor o igual que 'alt' }
   { con 'alt' incrementando. Cuando da lo mismo en `alt' y `alt+1' }
   { es que ya todo el arbol tiene altura maxima 'alt'. }
   while true do
   begin
      cantt := cuenta_alt(n,alt,altura,a);
      if cantt=cant then break;
      cant := cantt;
      writeln(cantt,' nodos hasta el nivel ',alt);
      alt := alt+1;
   end;
   
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}