Suma de las alturas de los nodos de un árbol
Las árboles binarios se pueden representar con el siguiente tipo
data Arbol a = H | N a (Arbol a) (Arbol a) deriving Show
Por ejemplo, el árbol
1 / \ 2 3 / \ 4 5
se representa por
ej1 :: Arbol Int ej1 = N 1 (N 2 (N 4 H H) (N 5 H H)) (N 3 H H)
La altura de cada elemento del árbol es la máxima distancia a las hojas en su rama. Por ejemplo, en el árbol anterior, la altura de 1 es 3, la de 2 es 2, la de 3 es 1, la de 4 es 1 y la de 5 es 1.
Definir la función
sumaAlturas :: Arbol t -> Int
tal que (sumaAlturas a) es la suma de las alturas de los elementos de a. Por ejemplo,
λ> sumaAlturas (N 1 (N 2 (N 4 H H) (N 5 H H)) (N 3 H H)) 8 λ> sumaAlturas (N 1 (N 2 (N 4 H H) H) (N 3 H H)) 7 λ> sumaAlturas (N 1 (N 2 (N 4 H H) H) (N 2 (N 4 H H) (N 5 H H))) 10
Soluciones
data Arbol a = H | N a (Arbol a) (Arbol a) deriving Show sumaAlturas :: Arbol t -> Int sumaAlturas H = 0 sumaAlturas a@(N _ i d) = altura a + sumaAlturas i + sumaAlturas d -- (altura a) es la altura del árbol a. Por ejemplo, -- altura H == 0 -- altura (N 7 H H) == 1 -- altura (N 7 (N 5 H H) H) == 2 -- altura (N 7 (N 5 H (N 6 H H)) H) == 3 altura :: Arbol t -> Int altura H = 0 altura (N _ i d) = 1 + max (altura i) (altura d)