Ejercicio 6 (Funciones sobre rosetrees) F
A continuación se presenta el tipo Rosetree:
TAD Rosetree(α)
géneros rosetree(α)
igualdad observacional
(∀r1, r2 : rosetree) (r1 =obs r2 ⇐⇒ (raíz(r1) =obs raíz(r2) ∧ hijos(r1) =obs hijos(r2)))
observadores básicos
raíz : rosetree(α) −→ α
hijos : rosetree(α) −→ secu(rosetree(α)))
generadores
rose : α × secu(rosetree(α)) −→ rosetree(α)
axiomas ∀s: secu(rosetree(α)) ∀a: α
raíz(rose(a, s)) ≡ a
hijos(rose(a, s)) ≡ s
Fin TAD
Ejemplos de instancias:
rose(1, <>)
rose(true, rose(false, <>) • <>)
rose(true, rose(false, <>) • rose(true, rose(true, <>) • <>) • rose(false, <>) • <>)
Defina operaciones auxiliares para:
a) Conocer la altura de un rosetree.
b) Calcular la cantidad de hojas de un rosetree.
c) Podar un rosetree, es decir, eliminar todas las hojas del rosetree.
d) Dado un número natural n, devolver una secuencia con los elementos del nivel n enumerados de izquierda a
derecha. Los elementos de nivel n son aquellos nodos que se encuentran a distancia n de la raíz del rosetree.
e) Calcular el conjunto de las ramas más largas de un rosetree que contienen al menos un elemento repetido.