-- AUTOR: Elvira Mayordomo Cámara
-- PROYECTO: módulo de declaración del TAD arboles 
-- FICHERO: arboles.ads
-- FECHA: 22-10-02, basado en el libro de Javier Campos (ver bibliografía)
-- Especificación en fichero aparte

generic
type elemento is private;

package arboles is

type arbol is limited private;
type bosque is limited private;
-- coste en memoria: un árbol de n nodos ocupa O(n)

procedure creaVacio(b:out bosque);
-- Post: b=bVacío
-- coste en tiempo O(1)

procedure anadeDch(b:in out bosque; a:in arbol);
-- Pre: b=b0
-- Post: b=+dcha(b0,a)
-- NO HACE COPIA DE a
-- coste en tiempo O(1)


function long(b:in bosque) return integer;
-- Post: long(b)=longitud(b)
-- coste en tiempo O(1)

procedure observa(b:in bosque; i:in integer; a:out arbol);
-- Pre: 1<=i<=longitud(b)  
-- Post: a=b[i]
-- HACE COPIA
-- coste en tiempo: para un árbol de n nodos tarda O(n)

function altBosque(b:bosque) return integer; 
-- Post: altBosque(b)=alturaB(b)
-- coste en tiempo O(1)

procedure enraizar(e:in elemento; b:in bosque; a:out arbol);
-- Post: a=enraizar(e,b)
-- NO HACE COPIA DE b
-- coste en tiempo O(1)

function raiz(a:arbol) return elemento;
-- Post: raiz(a)=raíz(a)
-- coste en tiempo O(1)

procedure subarbol(a:in arbol; i:in integer; sa:out arbol);
-- Pre: 1<=i<=numHijosRaiz(a)  
-- Post: sa=subárbol(a,i)
-- HACE COPIA
-- coste en tiempo: para un árbol de n nodos tarda O(n)

procedure subarbolsc(a:in arbol; i:in integer; sa:out arbol);
-- Pre: 1<=i<=numHijosRaiz(a)  
-- Post: sa=subárbol(a,i)
-- NO HACE COPIA
-- coste en tiempo O(i)

function numHijos(a:arbol) return integer;
-- Post: numHijos(a)=numHijosRaiz(a)
-- coste en tiempo O(1)

function esHoja(a:arbol) return boolean;
-- Post: esHoja(a)=eshoja(a)
-- coste en tiempo O(1)

function altArbol(a:arbol) return integer; 
-- Post: altArbol(a)=alturaA(a)
-- coste en tiempo O(1)

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

procedure asignaBosque(nuevo:out bosque; viejo:in bosque);
-- Duplica la representación del bosque 
-- viejo guardándolo en nuevo.
-- coste en tiempo: para un bosque de n nodos tarda O(n)

procedure liberaBosque(b:in out bosque);
-- Libera la memoria dinámica accesible 
-- desde b, quedando b vacío.
-- coste en tiempo: para un bosque de n nodos tarda O(n)

procedure asignaArbol(nuevo:out arbol; viejo:in arbol);
-- Duplica la representación del árbol 
-- viejo guardándolo en nuevo.
-- coste en tiempo: para un árbol de n nodos tarda O(n)

procedure liberaArbol(a:in out arbol);
-- Libera la memoria dinámica accesible desde a.
-- coste en tiempo: para un árbol de n nodos tarda O(n)

private

type nodo;
type arbol is access nodo;

type nodo is record
dato:elemento;
primogenito,sigHermano:arbol;
altura,numHijos:integer;
end record;
type bosque is record
primArbol,ultArbol:arbol;
long,altura:integer;
end record;

end arboles;