Subárboles monovalorados
Los árboles binarios con valores enteros se pueden representar mediante el tipo Arbol definido por
|
1 2 3 |
data Arbol = H Int | N Int Arbol Arbol 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 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 la función
|
1 |
monovalorados :: Arbol -> [Arbol] |
tal que (monovalorados a) es la lista de los subárboles monovalorados de a. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
λ> monovalorados (N 5 (H 5) (H 5)) [N 5 (H 5) (H 5),H 5,H 5] λ> monovalorados (N 5 (H 5) (H 6)) [H 5,H 6] λ> monovalorados (N 9 (H 9) (N 9 (H 9) (H 9))) [N 9 (H 9) (N 9 (H 9) (H 9)),H 9,N 9 (H 9) (H 9),H 9,H 9] λ> monovalorados (N 9 (H 9) (N 7 (H 9) (H 9))) [H 9,H 9,H 9] λ> monovalorados (N 9 (H 9) (N 9 (H 7) (H 9))) [H 9,H 7,H 9] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
data Arbol = H Int | N Int Arbol Arbol deriving (Show, Eq) monovalorados :: Arbol -> [Arbol] monovalorados (H x) = [H x] monovalorados (N x i d) | todosIguales i x && todosIguales d x = (N x i d) : (subarboles i ++ subarboles d) | otherwise = monovalorados i ++ monovalorados d -- (todosIguales a x) se verifica si todos los valores de los nodos y -- las hojas del árbol a son iguales a x. todosIguales :: Arbol -> Int -> Bool todosIguales (H y) x = y == x todosIguales (N y i d) x = y == x && todosIguales i x && todosIguales d x -- (subarboles a) es la lista de los subárboles de a. subarboles :: Arbol -> [Arbol] subarboles (H x) = [H x] subarboles (N x i d) = (N x i d) : (subarboles i ++ subarboles d) |
Pensamiento
Y nadie pregunta
ni nadie contesta,
todos hablan solos.Antonio Machado