Suma de las hojas de mínimo nivel
Los árboles binarios con valores en las hojas y en los nodos se definen por
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Eq, Show) |
Por ejemplo, el árbol
1 2 3 4 5 6 7 |
1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 |
se pueden representar por
1 2 3 4 |
ejArbol :: Arbol Int ejArbol = N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)) |
En el árbol anterior, los valores de las hojas de menor nivel son 4, 6 y 7 cuya suma es 17.
Definir la función
1 |
suma :: Num t => Arbol t -> t |
tal que (suma a) es la suma de los valores de las hojas de menor nivel del árbol a. Por ejemplo,
1 2 3 4 5 |
suma ejArbol == 17 suma (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7))) == 22 suma (N 1 (H 2) (N 3 (H 6) (H 7))) == 2 suma (N 1 (H 2) (H 3)) == 5 suma (H 2) == 2 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Eq, Show) ejArbol :: Arbol Int ejArbol = N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)) suma :: Num t => Arbol t -> t suma a = aux [a] where aux as | null xs = aux (concat [[i,d] | (N _ i d) <- as]) | otherwise = sum xs where xs = [x | (H x) <- as] |
Buenas, la definición no es correcta. Por ejemplo
Donde suma2 es tu función.
Es cierto, no se cumple para todos los árboles. Por recursión se me ocurre también esta: