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 |
10 / \ / \ 8 2 / \ / \ 3 5 2 0 |
se pueden representar por
|
1 2 3 |
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
|
1 |
propSuma :: Arbol Int -> Bool |
tal que (propSuma a) se verifica si el árbol a cumple la propiedad de la suma. Por ejemplo,
|
1 2 3 4 5 6 |
λ> 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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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 |