3- Árboles3.2 Árboles generales

Implementación de árboles generales en ADA (.adb)
    with unchecked_deallocation;
    package body arboles is
     
      procedure disponer is new unchecked_deallocation(nodo,arbol);

      procedure creaVacio(b:out bosque) is
      -- Post: b=bVacío
      begin

        b.primArbol:=null;
        b.ultArbol:=null;
        b.long:=0;
        b.altura:=-1;
      end creaVacio;

      procedure anadeDch(b:in out bosque; a:in arbol) is
      -- Pre: b=b0
      -- Post: b=+dch(b0,a)
      -- NO HACE COPIA DE a
      begin

        if long(b)=0 then
          b.primArbol:=a;
        else
          b.ultArbol.sighermano:=a;
        end if;
        b.ultArbol:=a;
        b.long:=b.long+1;
        b.altura:=integer'max(b.altura,a.altura);
      end anadeDch;

      function long(b:in bosque) return integer is
      -- Post: long(b)=long(b)
      begin

        return(b.long);
      end long;

      procedure observa(b:in bosque; i:in integer; a:out arbol) is
      -- Pre: 1<=i<=long(b) 
      -- Post: a=b[i]
      -- HACE COPIA
      aux: arbol;
      begin

         aux:=b.primarbol;
         for n in 2..i loop
            aux:=aux.sighermano;
         end loop;
         asignaArbol(a,aux);
         a.sighermano:=null;
      end observa;

      function altBosque(b:bosque) return integer is
      -- Post: altBosque(b)=altBosque(b)
      begin

         return(b.altura);
      end altBosque;

      procedure enraizar(e:in elemento; b:in bosque; 
      a:out arbol) is
      -- Post: a=enraizar(e,b)
      -- NO HACE COPIA DE b
      begin

         a:=new nodo'(e,b.primArbol,null,b.altura+1,b.long);
      end enraizar;

      function raiz(a:arbol) return elemento is
      -- Post: raiz(a)=raíz(a)
      begin

         return(a.dato);
      end raiz;

      procedure subarbol(a:in arbol; i:in integer;
      sa:out arbol) is
      -- Pre: 1<=i<=numHijosRaiz(a)
      -- Post: sa=subárbol(a,i)
      -- HACE COPIA
      aux: arbol;
      begin

         aux:=a.primogenito;
         for n in 2..i loop
            aux:=aux.sighermano;
         end loop;
         asignaArbol(sa,aux);
         sa.sighermano:=null;
      end subarbol;

      function numHijos(a:arbol) return integer is
      -- Post: numHijos(a)=numHijosRaiz(a)
      begin

         return(a.numHijos);
      end numHijos;

      function esHoja(a:arbol) return boolean is
      -- Post: esHoja(a)=hoja?(a)
      begin

         return(a.numHijos=0);
      end esHoja;

      function altArbol(a:arbol) return integer is 
      -- Post: altArbol(a)=altÁrbol(a)
      begin

         return(a.altura);
      end altArbol;

      procedure elBosque(a:in arbol; b:out bosque) is
      -- Guarda en b la lista de subárboles de a.
      -- No actualiza b.ultimo
      -- No duplica
      begin

        b.primArbol:=a.primogenito;
        b.long:=a.numHijos;
        b.altura:=a.altura-1;
      end elBosque;

      procedure asignaBosque(nuevo:out bosque; 
      viejo:in bosque) is
      -- Duplica la representación del bosque viejo
      -- guardándolo en nuevo.
      -- No utiliza viejo.ultArbol
      auxV,auxN:arbol;
      begin

        if viejo.primArbol=null 
        then
           creaVacio(nuevo);
        else
          asignaArbol(auxN,viejo.primArbol);
          nuevo.primArbol:=auxN;
          nuevo.long:=viejo.long;
          nuevo.altura:=viejo.altura;
          auxV:=viejo.primArbol.sigHermano;
          while auxV/=null loop
             asignaArbol(auxN.sigHermano,auxV);
             auxV:=auxV.sigHermano;
             auxN:=auxN.sigHermano;
          end loop;
          nuevo.ultArbol:=auxN;
          auxN.sigHermano:=null;
        end if;
      end asignaBosque;

      procedure liberaBosque(b:in out bosque) is
      -- Libera la memoria dinámica accesible 
      -- desde b, quedando b vacío.
      -- No utiliza b.ultArbol
      aux,aux2:arbol;
      begin

        if b.primArbol/=null then
          aux:=b.primArbol;
          aux2:=b.primArbol.sigHermano;
          for i in 1..b.long loop 
            liberaArbol(aux);
            aux:=aux2;
            aux2:=aux2.sigHermano;
          end loop;
          creaVacio(b);
        end if;
      end liberaBosque;

      procedure asignaArbol(nuevo:out arbol;
      viejo:in arbol) is
      -- Duplica la representación del árbol viejo 
      -- guardándolo en nuevo.
      baux,baux2:bosque;
      begin

        baux.primArbol:=viejo.primogenito;
        baux.long:=viejo.numHijos;
        baux.altura:=viejo.altura-1;
        -- asignaBosque no necesita baux.ultArbol
        asignaBosque(baux2,baux);
        enraizar(raiz(viejo),baux2,nuevo);
      end asignaArbol;

      procedure liberaArbol(a:in out arbol) is
      -- Libera la memoria dinámica accesible 
      -- desde a.
      baux:bosque;
      begin

        baux.primArbol:=a.primogenito;
        baux.long:=a.numHijos;
        baux.altura:=a.altura-1;
        -- liberaBosque no necesita baux.ultArbol
        liberaBosque(baux);
        disponer(a);
      end liberaArbol;
    end arboles;
     


  E.Mayordomo y K. Urzelai 
elvira at posta.unizar.es
karmelo at posta.unizar.es
Fecha de actualización: 4-9-01