tpu/ordnodo.pas

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

Escribir una function ORDNODO (n: nodo, A:arbol): boolean; 
que verifica si cada secuencia de hermanos del subarbol 
del nodo "n" (perteneciente al arbol ordenado orientado A) 
estan ordenadas entre si, de  izquierda a derecha. Por 
ejemplo, ver figura, para el arbol de la izquierda deberia 
retornar "true", mientras que para el de la derecha deberia 
retornar "false", ya que las secuencias de hermanos 
indicados en las rayadas NO estan ordenados. Se sugiere el 
siguiente algoritmo: para un dado nodo retornar false si: 
1) sus hijos no estan  ordenados o 2) algunos de sus hijos 
contiene  en su subarbol una  secuencia de  hermanos no 
ordenada (recursividad).
[Tomado 2do parcial de 2003, 3-Jun-2003]
keywords: arbol orientado

  FIN DE DESCRIPCION }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: ordnodo.pas 2003/06/04 11:26 mstorti Exp jdelia   $ }
program  ord_nodo_p;
uses u_arborip;
type
   arbol = arborip;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
function ORD_NODO (n: nodo; a: arbol) : boolean;
var
  c      : nodo;
  e1, e2 : integer;
begin
{ Si el arbol esta vacio entonces asumimos que esta }
{ ordenado (no tiene ninguna secuencia desordenada) }
  ORD_NODO := true;
  if (n = lambda) then exit;
{ Si es una hoja, esta claro que esta ordenado. Esto es     }
{ muy importante ya que es donde se corta la recursividad !!}
  c := a.HIJO_MAS_IZQ (n);
  if (c = lambda) then exit;
{ Revisa las etiquetas de los hijos. e1, e2 van siendo     }
{ dos etiquetas en dos hijos consecutivos. Si se encuentra }
{ algun par desordenado entonces se retorna `false'        }
{ Nota: Este lazo y el de abajo se podrian realizar en un solo}
{ lazo, pero de esta forma si las etiquetas de los hijos de}
{ un nodo estan desordenadas, entonces ya no hace falta revisar}
{ sus hijos. Esto puede llegar a ser MUCHO mas eficiente en}
{ ciertos casos }
  ORD_NODO := false;
  e1 := a.ETIQUETA (c);
  c := a.HERMANO_DER (c);
  while (c <> lambda) do begin
    e2 := a.ETIQUETA (c);
    if (e2 < e1) then exit;
    e1 := e2;
    c  := a.HERMANO_DER (c);
  end; {while}
{ Ahora aplica la funcion recursivamente a todos los hijos.}
{ Donde encuentra alguno que no viola la condicion ya }
{ puede salir y retornar `false'. }
   c := a.HIJO_MAS_IZQ (n);
   while (c <> lambda) do begin
     if not ORD_NODO (c,a) then exit ;
     c := a.HERMANO_DER (c);
   end;
{ Si paso todas las condiciones entonces retorna `true'. }
   ORD_NODO := true;
end;

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
  a : arbol;
  n : nodo;
  r : boolean;
begin
  a.INICIALIZA;
  n   := a.AGREGA_HIJO_MAS_IZQ (10,lambda);
  n   := a.AGREGA_HIJO_MAS_IZQ (21,n);
  n   := a.AGREGA_HERM_DER     (30,n);
  n   := a.AGREGA_HIJO_MAS_IZQ (40,n);
  n   := a.AGREGA_HERM_DER     (51,n);
  n   := a.AGREGA_HERM_DER     (80,n);
  n   := a.AGREGA_HIJO_MAS_IZQ (60,n);
  n   := a.AGREGA_HERM_DER     (70,n);
  a.IMPRIME_ARB ('arbol a: ');
  r := ORD_NODO (a.RAIZ, a);
  writeln ('Estan ordenadas las secuencias de hijos ? :',r);
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}