Ir al contenido principal

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)