Árboles acotados
Los árboles binarios se pueden representar mediante el tipo Arbol definido por
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show |
Por ejemplo, el árbol
|
1 2 3 4 5 6 7 |
7 / \ / \ / \ 4 9 / \ / \ 1 3 5 6 |
se puede representar por
|
1 |
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
|
1 2 3 4 5 |
5 9 5 9 / \ / \ / \ / \ 5 5 9 9 5 6 9 7 / \ / \ 9 9 9 9 |
Definir las funciones
|
1 2 |
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,
|
1 2 |
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,
|
1 2 3 4 5 |
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
|
1 2 3 4 5 6 7 8 9 10 11 |
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] |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>