antecesor.pas
{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION
Suponga que se tienen los arreglos ORD_PRE [n],
ORD_SIM [n] y ORD_POS [n] que dan las posiciones en
los \'ordenes previo, sim\'etrico y posterior,
respectivamente, de cada nodo $n$ de un \'arbol ordenado
y orientado. Describa un algoritmo que diga si un nodo
$i$ es un antecesor o no de un nodo $j$, para cualquier
par de nodos $i$, $j$ e incluya los casos de antecesores
propios e impropios. Explique c\'omo trabaja
el algoritmo.
FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: antecesor.pas 2002/04/23 18:00 mstorti Exp jdelia $ }
{
La solucion es que, en orden previo, los nodos antecesores
estan antes, y en orden posterior, despues.
Por ejemplo, consideremos el siguiente arbol orientado
y ordenado:
142
/ | \
/ | \
/ | \
/ | \
63 48 125
/ \ / \
/ \ / \
/ \ / \
33 41 130 12
/| \
/ | \
/ | \
8 7 62
Para implementar la solucion necesitamos: (i) disponer
de los listados de las etiquetas en orden previo y en
orden posterior, los cuales los almacenaremos en los
vectores XPRE y XPOS, respectivamente ; (ii) introducir
algun indicador para detectar los cambios en el orden de
aparicion de las etiquetas en cada listado. Para esto:
a) Introducimos las colas CPRE y CPOS en los listados en
orden previo y posterior, respectivamente, para
"recordar" el orden de aparicion de los nodosen cada
recorrido.
b) Implementamos la funcion RECORRIDO para pasar
el contenido de ambas colas a los vectores
X_PRE = [ 142 63 33 41 8 7 62 48 125 130 12 ]
y
X_POS = [ 33 8 7 62 41 63 48 130 12 125 142 ]
respectivamente. Ademas, nos devuelve el numero "n" de
nodos en el arbol (n=11 en el ejemplo).
c) Implementamos un procedimiento IDENTIFICA en donde,
primero, numeramos los elementos listados en orden
previo:
O_PRE = [ 1 2 3 4 5 6 7 8 9 10 11 ]
y luego buscamos a donde van a parar estos indices en
el listado en orden posterior:
O_POS = [ 3 5 6 7 4 2 8 10 11 9 1 ].
Por ejemplo, la etiqueta "63" esta en la posicion i = 2
en X_PRE y esta en i'= 6 en X_POS, por lo que el indice
2 en O_PRE, asociado a este elemento, pasara a la
posicion i'= 6 en O_POS, que es el lugar en donde
vuelve a aparecer esa etiqueta en X_POS.
d) Luego, el nodo "i" es antecesor del nodo "j", solo
cuando el condicional:
ES_ANTECESOR := ( OPRE [i] <= OPRE [j] ) and
( OPOS [i] >= OPOS [j] )
resulte verdadero, en donde el "=" es para el caso
de antecesores "impropios".
e) Por ultimo, hemos agregado un par de lazos sobre todos
los nodos para explorar en forma exhaustiva.
}
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
program antecesor ;
uses u_arbori, u_colapi ;
const
n_max = 100;
z = ' ' ;
type
bosque = bosque_arbori ;
cola = colapi ;
vector = array [1..n_max] of curs_nodo ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_PREV (A: curs_nodo; B: bosque; var C: cola);
var
temp : curs_nodo;
x : tipo_elemento ;
begin
if (A <> lambda) then begin
x := B.ETIQUETA (A);
C.PONE (x);
writeln (x:3);
temp := B.HIJO_MAS_IZQ (A);
while (temp <> lambda) do begin
ORD_PREV (temp, B, C);
temp := B.HERMANO_DER (temp);
end; {while}
end; {if}
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_SIME (A: curs_nodo; B: bosque; var C: cola) ;
var
temp : curs_nodo;
x : tipo_elemento ;
begin
if (A <> lambda) then begin
temp := B.HIJO_MAS_IZQ (A);
ORD_SIME (temp, B, C);
x := B.ETIQUETA (A);
C.PONE (x);
writeln (x:3);
if (temp <> lambda) then begin
temp := B.HERMANO_DER (temp);
while (temp <> lambda) do begin
ORD_SIME (temp, B, C);
temp := B.HERMANO_DER (temp);
end; {while}
end; {if}
end; {if}
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ORD_POST (A: curs_nodo; B: bosque; var C: cola) ;
var
temp : curs_nodo;
x : tipo_elemento ;
begin
if (A <> lambda) then begin
temp := B.HIJO_MAS_IZQ (A);
while (temp <> lambda) do begin
ORD_POST (temp, B, C);
temp := B.HERMANO_DER (temp);
end; {while}
x := B.ETIQUETA (A);
C.PONE (x);
writeln (x:3);
end; {if}
end;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function RECORRIDO ( var C : cola ;
var E : vector;
s : string): curs_nodo ;
var
i : curs_nodo ;
n : curs_nodo ;
x : curs_nodo ;
begin
n := 0 ;
while not C.VACIA do begin
n := n + 1;
x := C.FRENTE ;
E [n] := x ;
C.QUITA ;
end ;
if length (s) > 0 then write (s, z);
for i := 1 to n do write ( E [i]:3 , z);
writeln ;
RECORRIDO := n ;
end ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure IDENTIFICA ( XPRE, XPOS: vector ;
var OPRE, OPOS: vector ;
n: curs_nodo);
var
i, j : curs_nodo ;
begin
for i := 1 to (n) do begin
OPRE [i] := i ;
for j := 1 to n do begin
if XPOS [j] = XPRE [i] then OPOS [i] := j ;
end ; {j}
end ; {i}
writeln ;
write ('i-orden previo :');
for i := 1 to n do write ( OPRE [i]:3, z);
writeln ;
write ('i-orden posterior:');
for i := 1 to n do write ( OPOS [i]:3, z);
writeln ;
readln ;
end ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
BB : bosque;
arbol, arb1, arb2, arb3, arb4, arb5 : curs_nodo;
arb6 , arb7, arb8, arb9, arb0 : curs_nodo;
i, j, n : curs_nodo ;
ES_ANTECESOR : boolean ;
CX , CY : cola ;
XPRE, XPOS : vector ;
OPRE, OPOS : vector ;
begin
BB.INICIALIZA_NODOS;
arb1 := BB.CREA0 ( 33);
arb2 := BB.CREA0 ( 8);
arb3 := BB.CREA0 ( 7);
arb4 := BB.CREA0 ( 62);
arb5 := BB.CREA0 (130);
arb6 := BB.CREA0 ( 12);
arb7 := BB.CREA3 ( 41, arb2, arb3, arb4);
arb8 := BB.CREA2 ( 63, arb1, arb7);
arb9 := BB.CREA0 ( 48);
arb0 := BB.CREA2 (125, arb5, arb6);
arbol := BB.CREA3 (142, arb8, arb9, arb0);
CX.ANULA; {anula cola para etiquetas en orden previo}
CY.ANULA; {anula cola para etiquetas en orden posterior}
writeln ('Listado en orden previo : ');
ORD_PREV (arbol, BB, CX); {ademas carga cola CX}
writeln ('Listado en orden posterior: ');
ORD_POST (arbol, BB, CY); {ademas carga cola CY}
writeln ;
n := RECORRIDO (CX, XPRE, 'x-orden previo :');
n := RECORRIDO (CY, XPOS, 'x-orden posterior:');
IDENTIFICA (XPRE, XPOS, OPRE, OPOS, n);
for i := 1 to n do begin {lazos exhaustivos}
for j := 1 to n do begin
ES_ANTECESOR := ( OPRE [i] <= OPRE [j] ) and
( OPOS [i] >= OPOS [j] ) ;
writeln ;
writeln (' ni = ', XPRE [i]:3);
writeln (' nj = ', XPRE [j]:3);
writeln (' ni .es_antecesor. nj = ', ES_ANTECESOR);
end ;
end ;
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
Generated by GNU enscript 1.6.1.