maxarbb.pas
{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION
Operaciones varias con \'arboles binarios
(ver ``maxarbo.pas'' para las mismas
operaciones con \'arboles orientados):
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 binario
FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: maxarbb.pas 2002/08/02 7:00 jdelia Exp jdelia $ }
program maxarbb ;
uses u_arbbii ;
const
nmax = 100 ;
type
bosque = bosque_arbbii ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CANT_NOD (n: curs_nodo ; B: bosque) : integer;
var
c1, c2 : curs_nodo;
p : integer ;
begin
if (n = lambda) then
p := 0
else begin
c1 := B.HIJO_IZQ (n);
c2 := B.HIJO_DER (n);
p := CANT_NOD (c1,B) + CANT_NOD (c2,B) + 1;
end ; {if}
CANT_NOD := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function PROF_NOD (n: curs_nodo; B : bosque) : integer;
var
c1, c2 : curs_nodo;
h1, h2 : integer ;
p : integer ;
begin
if (n = lambda) then
p := -1
else begin
c1 := B.HIJO_IZQ (n);
c2 := B.HIJO_DER (n);
h1 := PROF_NOD (c1, B) ;
h2 := PROF_NOD (c2, B) ;
p := -1 ;
if ( h1 > p ) then p := h1 ;
if ( h2 > p ) then p := h2 ;
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
c1, c2 : curs_nodo;
p : integer ;
begin
if (n = lambda) then
p := 0
else begin
c1 := B.HIJO_IZQ (n);
c2 := B.HIJO_DER (n);
p := B.ETIQUETA (n);
p := p + SUMA_ETIQ (c1,B) + SUMA_ETIQ (c2,B);
end ; {if}
SUMA_ETIQ := p;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function CTOS_PARES (n: curs_nodo; B: bosque): integer;
var
c1, c2 : curs_nodo;
p : integer ;
begin
if (n = lambda) then
p := 0
else begin
p := 0 ;
if not odd ( B.ETIQUETA (n) ) then p := 1 ;
c1 := B.HIJO_IZQ (n);
c2 := B.HIJO_DER (n);
p := p + CTOS_PARES (c1,B) + CTOS_PARES (c2,B);
end ; {if}
CTOS_PARES := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function PROF_PAR (n: curs_nodo; B : bosque) : integer;
var
c1, c2 : curs_nodo;
h1, h2 : integer ;
p : integer ;
begin
if (n = lambda) then
p := -1
else begin
c1 := B.HIJO_IZQ (n);
c2 := B.HIJO_DER (n);
h1 := PROF_PAR (c1,B) ;
h2 := PROF_PAR (c2,B) ;
p := -1 ;
if ( h1 > p ) then p := h1 ;
if ( h2 > p ) then p := h2 ;
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
c1, c2 : curs_nodo;
h1, h2 : integer ;
p : integer ;
begin
if (n = lambda) then
p := 0
else begin
p := B.ETIQUETA (n);
c1 := B.HIJO_IZQ (n);
c2 := B.HIJO_DER (n);
h1 := MAX_ETIQ (c1,B);
h2 := MAX_ETIQ (c2,B);
if ( h1 > p ) then p := h1 ;
if ( h2 > p ) then p := h2 ;
end ; {if}
MAX_ETIQ := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function MAXIMO_PAR (n: curs_nodo; B: bosque): integer;
var
c1, c2 : curs_nodo;
p1, p2 : integer ;
p : integer ;
begin
if (n = lambda) then
p := 0
else begin
c1 := B.HIJO_IZQ (n);
c2 := B.HIJO_DER (n);
p1 := MAXIMO_PAR (c1,B) ;
p2 := MAXIMO_PAR (c2,B) ;
p := 0 ;
if not odd (B.ETIQUETA (n)) then p := B.ETIQUETA (n);
if ( p1 > p ) then p := p1 ;
if ( p2 > p ) then p := p2 ;
end ; {if}
MAXIMO_PAR := p ;
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_PREV (n: curs_nodo; B: bosque);
begin
if (n <> lambda) then begin
write (B.ETIQUETA (n),' ');
ORD_PREV (B.HIJO_IZQ (n), B);
ORD_PREV (B.HIJO_DER (n), B);
end ; {if}
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_POST (n: curs_nodo; B: bosque);
begin
if (n <> lambda) then begin
ORD_POST (B.HIJO_IZQ (n), B);
ORD_POST (B.HIJO_DER (n), B);
write (B.ETIQUETA (n),' ');
end ; {if}
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_SIM (n: curs_nodo; B: bosque);
begin
if (n <> lambda) then begin
ORD_SIM (B.HIJO_IZQ (n), B);
write (B.ETIQUETA (n),' ');
ORD_SIM (B.HIJO_DER (n), B);
end ; {if}
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
bos : array [1..nmax] 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.CREA2 ( 33, lambda, lambda);
bos [2] := B.CREA2 ( 23, lambda, lambda);
bos [3] := B.CREA2 ( 7, lambda, lambda);
bos [4] := B.CREA2 ( 35, lambda, lambda);
bos [5] := B.CREA2 ( 12, lambda, lambda);
bos [6] := B.CREA2 ( 48, lambda, bos [4]);
bos [7] := B.CREA2 ( 42, bos [2], bos [3]);
bos [8] := B.CREA2 (130, bos [6], lambda);
bos [9] := B.CREA2 ( 63, bos [1], bos [7]);
bos [10] := B.CREA2 (125, bos [8], bos [5]);
bos [11] := B.CREA2 (142, bos [9], bos [10]);
T1 := bos [11] ;
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));
T2 := bos [10] ;
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));
T3 := bos [2] ;
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));
T4 := bos [5] ;
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));
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
Generated by GNU enscript 1.6.1.