Padres como sumas de hijos
Los árboles binarios con valores en las hojas y en los nodos se definen por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Eq, Show)
Por ejemplo, el árbol
10
/ \
/ \
8 2
/ \ / \
3 5 2 0
se pueden representar por
ejArbol :: Arbol Int ejArbol = N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 0))
Un árbol cumple la propiedad de la suma si el valor de cada nodo es igual a la suma de los valores de sus hijos. Por ejemplo, el árbol anterior cumple la propiedad de la suma.
Definir la función
propSuma :: Arbol Int -> Bool
tal que (propSuma a) se verifica si el árbol a cumple la propiedad de la suma. Por ejemplo,
λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 0))) True λ> propSuma (N 10 (N 8 (H 4) (H 5)) (N 2 (H 2) (H 0))) False λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 1))) False
Soluciones
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show ejArbol :: Arbol Int ejArbol = N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 0)) propSuma :: Arbol Int -> Bool propSuma (H _) = True propSuma (N x i d) = x == raiz i + raiz d && propSuma i && propSuma d raiz :: Arbol Int -> Int raiz (H x) = x raiz (N x _ _) = x