maxarbo.pas
{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION
Operaciones varias con \'arboles orientados:
(ver ``maxarbb.pas'' para las mismas
operaciones con \'arboles binarios):
1) CANT_NOD: cantidad de nodos;
2) PROF_NOD: profundidad de un nodo (cuando el nodo es el
nodo raiz, entonces su profundidad es la profundidad
del \'arbol y coincide con su altura);
3) SUMA_ETIQ: suma de las etiquetas;
4) CTOS_PARES: cantidad de nodos con etiqueta par;
5) PROF_PAR: profundidad del \'arbol teniendo en cuenta
solamente los nodos con etiqueta par;
6) MAX_ETIQ: m\'aximo de las etiquetas, asumiendo que
todas son positivas;
7) MAXIMO_PAR: m\'axima etiqueta par.
keywords: arbol orientado
FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: maxarbo.pas 2002/08/02 7:00 mstorti Exp jdelia $ }
program maxarbo ;
uses u_arbori;
type
bosque = bosque_arbori;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CANT_NOD (n : curs_nodo; B : bosque) : integer;
var
c : curs_nodo;
p : integer ;
begin
if (n = lambda) then
p := 0
else begin
c := B.HIJO_MAS_IZQ (n);
p := 1 ;
while (c <> lambda) do begin
p := p + CANT_NOD (c,B);
c := B.HERMANO_DER (c);
end; {while}
end ; {if}
CANT_NOD := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function PROF_NOD (n : curs_nodo; B : bosque) : integer;
var
c : curs_nodo;
p : integer ;
begin
if (n = lambda) then
p := -1
else begin
c := B.HIJO_MAS_IZQ (n);
p := -1 ;
while (c <> lambda) do begin
if ( PROF_NOD (c,B) > p ) then p := PROF_NOD (c,B);
c := B.HERMANO_DER (c);
end; {while}
if ( p >= 0 ) then
p := p + 1
else begin
p := 0 ;
end ; {if}
end ; {if}
PROF_NOD := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function SUMA_ETIQ (n: curs_nodo; B: bosque) : integer;
var
c : curs_nodo;
p : integer ;
begin
if (n = lambda) then
p := 0
else begin
p := B.ETIQUETA (n);
c := B.HIJO_MAS_IZQ (n);
while (c <> lambda) do begin
p := p + SUMA_ETIQ (c,B);
c := B.HERMANO_DER (c);
end; {while}
end ; {if}
SUMA_ETIQ := p;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CTOS_PARES (n: curs_nodo ; B: bosque) : integer;
var
c : curs_nodo;
p : integer ;
begin
if (n = lambda) then
p := 0
else begin
p := 0 ;
if not odd ( B.ETIQUETA (n) ) then p := 1 ;
c := B.HIJO_MAS_IZQ (n);
while (c <> lambda) do begin
p := p + CTOS_PARES (c,B);
c := B.HERMANO_DER (c);
end; {while}
end ; {if}
CTOS_PARES := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function PROF_PAR (n: curs_nodo ; B: bosque) : integer;
var
c : curs_nodo;
h, p : integer ;
begin
if (n = lambda) then
p := -1
else begin
c := B.HIJO_MAS_IZQ (n);
p := -1 ;
while (c <> lambda) do begin
h := PROF_PAR (c,B) ;
if ( h > p ) then p := h ;
c := B.HERMANO_DER (c);
end; {while}
if ( p >= 0 ) then
p := p + 1
else begin
if not odd ( B.ETIQUETA (n) ) then p := 0;
end ; {if}
end ; {if}
PROF_PAR := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function MAX_ETIQ (n: curs_nodo ; B: bosque) : integer;
var
c : curs_nodo ;
h, p : integer ;
begin
if (n = lambda) then
p := 0
else begin
p := B.ETIQUETA (n);
c := B.HIJO_MAS_IZQ (n);
while ( c <> lambda ) do begin
h := MAX_ETIQ (c,B) ;
if ( h > p ) then p := h ;
c := B.HERMANO_DER (c);
end; {while}
end ; {if}
MAX_ETIQ := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function MAXIMO_PAR (n: curs_nodo; B: bosque): integer;
var
c1 : curs_nodo;
p1, p2 : integer ;
p : integer ;
begin
if (n = lambda) then
p := 0
else begin
p := 0 ;
if not odd (B.ETIQUETA (n)) then p := B.ETIQUETA (n);
c1 := B.HIJO_MAS_IZQ (n);
while ( c1 <> lambda ) do begin
p1 := MAXIMO_PAR (c1,B) ;
if ( p1 > p ) then p := p1 ;
c1 := B.HERMANO_DER (c1);
end ; {while}
end ; {if}
MAXIMO_PAR := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_PREV (n: curs_nodo; B: bosque);
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 (c,B);
c := B.HERMANO_DER (c);
end; {while}
end; {if}
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_POST (n: curs_nodo; B: bosque);
var
c : curs_nodo;
begin
if (n <> lambda) then begin
c := B.HIJO_MAS_IZQ (n);
while (c <> lambda) do begin
ORD_POST (c,B);
c := B.HERMANO_DER (c);
end; {while}
write (B.ETIQUETA (n),' ');
end; {if}
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_SIM (n: curs_nodo; B: bosque);
var
c : curs_nodo;
begin
if (n <> lambda) then begin
c := B.HIJO_MAS_IZQ (n);
ORD_SIM (c, B);
write (B.ETIQUETA (n),' ');
if (c <> lambda) then begin
c := B.HERMANO_DER (c);
while (c <> lambda) do begin
ORD_SIM (c, B);
c := B.HERMANO_DER (c);
end; {while}
end; {if}
end; {if}
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
bos : array [1..100] of curs_nodo;
B : bosque ; {El bosque donde estan los arboles }
T1, T2 : curs_nodo;
T3, T4 : curs_nodo;
begin
B.INICIALIZA_NODOS;
bos [1] := B.CREA0 ( 33);
bos [2] := B.CREA0 ( 23);
bos [3] := B.CREA0 ( 7);
bos [4] := B.CREA0 ( 35);
bos [5] := B.CREA0 (130);
bos [6] := B.CREA0 ( 12);
bos [7] := B.CREA3 ( 42, bos [2], bos [3], bos [4]);
bos [8] := B.CREA2 ( 63, bos [1], bos [7]);
bos [9] := B.CREA0 ( 48);
bos [10] := B.CREA2 (125, bos [5], bos [6]);
bos [11] := B.CREA3 (142, bos [8], bos [9], bos [10]);
T1 := bos [11];
T2 := bos [10]; {subarbol de T1}
T2 := bos [7]; {subarbol de T1}
T3 := bos [2]; {subarbol de T1}
T4 := bos [6]; {subarbol de T1}
writeln ;
writeln ('orden previo T1 ');
ORD_PREV (T1, B);
writeln ;
writeln ('orden posterior T1 ');
ORD_POST (T1, B);
writeln ;
writeln ('Cantidad de nodos : ', CANT_NOD (T1,B));
writeln ('Profundidad : ', PROF_NOD (T1,B));
writeln ('Suma de etiquetas : ', SUMA_ETIQ (T1,B));
writeln ('Cant. de nodos pares : ', CTOS_PARES (T1,B));
writeln ('Profun. nodos pares : ', PROF_PAR (T1,B));
writeln ('Max. etiqueta : ', MAX_ETIQ (T1,B));
writeln ('Max. etiqueta par : ', MAXIMO_PAR (T1,B));
writeln ;
write ('orden previo T2: ');
ORD_PREV (T2, B);
writeln ;
write ('orden posterior T2: ');
ORD_POST (T2, B);
writeln ;
writeln ('Cantidad de nodos : ', CANT_NOD (T2,B));
writeln ('Profundidad : ', PROF_NOD (T2,B));
writeln ('Suma de etiquetas : ', SUMA_ETIQ (T2,B));
writeln ('Cant. de nodos pares : ', CTOS_PARES (T2,B));
writeln ('Profun. nodos pares : ', PROF_PAR (T2,B));
writeln ('Max. etiqueta : ', MAX_ETIQ (T2,B));
writeln ('Max. etiqueta par : ', MAXIMO_PAR (T2,B));
writeln ;
write ('orden previo T3: ');
ORD_PREV (T3, B);
writeln ;
write ('orden posterior T3: ');
ORD_POST (T3, B);
writeln ;
writeln ('Cantidad de nodos : ', CANT_NOD (T3,B));
writeln ('Profundidad : ', PROF_NOD (T3,B));
writeln ('Suma de etiquetas : ', SUMA_ETIQ (T3,B));
writeln ('Cant. de nodos pares : ', CTOS_PARES (T3,B));
writeln ('Profun. nodos pares : ', PROF_PAR (T3,B));
writeln ('Max. etiqueta : ', MAX_ETIQ (T3,B));
writeln ('Max. etiqueta par : ', MAXIMO_PAR (T3,B));
writeln ;
write ('orden previo T4: ');
ORD_PREV (T4, B);
writeln ;
write ('orden posterior T4: ');
ORD_POST (T4, B);
writeln ;
writeln ('Cantidad de nodos : ', CANT_NOD (T4,B));
writeln ('Profundidad : ', PROF_NOD (T4,B));
writeln ('Suma de etiquetas : ', SUMA_ETIQ (T4,B));
writeln ('Cant. de nodos pares : ', CTOS_PARES (T4,B));
writeln ('Profun. nodos pares : ', PROF_PAR (T4,B));
writeln ('Max. etiqueta : ', MAX_ETIQ (T4,B));
writeln ('Max. etiqueta par : ', MAXIMO_PAR (T4,B));
writeln ;
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
Generated by GNU enscript 1.6.1.