caminoord.pas

{ COMIENZO DE DESCRIPCION

Dado un arbol ordenado binario A y un nodo n escribir una funcion
CAMINO_ORD(n: nodo, A:arbol): boolean; que retorna verdadero si existe
algun camino ordenado desde n a una hoja en el subarbol del nodo
n. Por ejemplo en el caso del arbol de la izquierda en la figura de
abajo debe retornar true ya que el camino marcado con lineas de puntos
esta ordenado de menor a mayor yendo desde la raiz a la hoja, mientras
que para el de la derecha debe retornar false ya que no existe ningun
camino con esas caracteristicas. Se sugiere el siguiente algoritmo: Un
dado nodo n debe retornar true si, o bien es una hoja, o bien alguno
de sus hijos c contiene un camino ordenado y ETIQUETA(c)>ETIQUETA(n).
[Tomado 2do parcial de 2003, 3-Jun-2003]
keywords: arbol binario

FIN DE DESCRIPCION }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $Id: caminoord.pas,v 1.3 2003/06/04 11:19:48 mstorti Exp mstorti $  }

program camino_ord_p;

uses u_arbbii, arbbtools;

type
   bosque	= bosque_arbbii;

function camino_ord(n : curs_nodo; A: bosque) : boolean;
var
   ci,cd : curs_nodo;
   e : integer;
begin 
   camino_ord := true;

   { El nodo no existe }
   if n=Lambda then exit;

   e := A.etiqueta(n); ci := A.hijo_izq(n); cd := A.hijo_der(n);

   { El nodo es una hoja }
   if (ci=Lambda) and (cd=Lambda) then exit;

   { Existe un camino ordenado por el hijo izquierdo }
   if (ci<> Lambda) and camino_ord(ci,A) and (A.etiqueta(ci)>e) then exit;

   { Existe un camino ordenado por el hijo derecho }
   if (cd<> Lambda) and camino_ord(cd,A) and (A.etiqueta(cd)>e) then exit;
   
   { No existe camino ordenado  }
   camino_ord := false;
   
end; { camino_ord }

procedure test_tree(s : string; A:bosque);
var
   n : curs_nodo;
begin
   write('arbol: ',s,' Existe camino ord: ');
   n := crea_de_string(s,A);
   if camino_ord(n,A) then
      writeln('SI')
   else
      writeln('NO');
end;   

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
var
   A : bosque;
   n,m : curs_nodo;
   k : integer;
begin
   A.inicializa_nodos;
   test_tree('1{8{3,2},4{9,2}}',A);
   test_tree('1{8{3,2},4{2,2}}',A);
   test_tree('1{8{3,2},4{8{5,9},2}}',A);
   test_tree('1{8{3,2},4{8{5,7},2}}',A);
end.
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}