Suma de árboles por niveles
Los árboles binarios con valores enteros se pueden representar con el de tipo de dato algebraico
data Arbol = H | N a Arbol Arbol
Por ejemplo, los árboles
3 7
/ \ / \
2 4 5 8
/ \ \ / \ \
1 3 5 6 4 10
/ /
9 1
se representan por
ej1, ej2 :: Arbol ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H)) ej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H))
Definir la función
suma :: Arbol -> Int
tal que (suma a) es la suma de todos los nodos a una distancia par de la raíz del árbol a menos la suma de todos los nodos a una distancia impar de la raíz. Por ejemplo,
suma ej1 == 6 suma ej2 == 4
ya que
(3 + 1+3+5) - (2+4) = 6 (7 + 6+4+10) - (5+8 + 9+1) = 4
Soluciones
data Arbol = H | N Int Arbol Arbol ej1, ej2 :: Arbol ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H)) ej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H)) suma :: Arbol -> Int suma H = 0 suma (N x i d) = x - suma i - suma d