Árboles con valores acotados
Los árboles binarios se pueden representar mediante el tipo Arbol definido por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show
Por ejemplo, el árbol
7
/ \
/ \
/ \
4 9
/ \ / \
1 3 5 6
se puede representar por
N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))
Un árbol está acotado por un conjunto ys si todos los valores de sus hojas y sus nodos pertenecen a ys. Por ejemplo, el árbol anterior está acotado por [1..10] pero no lo está por [1..7].
Un árbol es monovalorado si todos sus elementos son iguales. Por ejemplo, de los siguientes árboles sólo son monovalorados los dos primeros
5 9 5 9
/ \ / \ / \ / \
5 5 9 9 5 6 9 7
/ \ / \
9 9 9 9
Definir las funciones
acotado :: Eq a => Arbol a -> [a] -> Bool monovalorados :: Arbol -> [Arbol]
tales que
- (acotado a ys) se verifica si a está acotado por ys. Por ejemplo,
acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..10] == True acotado (N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))) [1..7] == False
- (monovalorado a) se verifica si a es monovalorado. Por ejemplo,
monovalorado (N 5 (H 5) (H 5)) == True monovalorado (N 5 (H 5) (H 6)) == False monovalorado (N 9 (H 9) (N 9 (H 9) (H 9))) == True monovalorado (N 9 (H 9) (N 7 (H 9) (H 9))) == False monovalorado (N 9 (H 9) (N 9 (H 7) (H 9))) == False
Soluciones
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show acotado :: Eq a => Arbol a -> [a] -> Bool acotado (H x) ys = x `elem` ys acotado (N x i d) ys = x `elem` ys && acotado i ys && acotado d ys monovalorado :: Eq a => Arbol a -> Bool monovalorado (H _) = True monovalorado (N x i d) = acotado i [x] && acotado d [x]