Suma de las alturas de los nodos de un árbol
Las árboles binarios se pueden representar con el siguiente tipo
|
1 2 3 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving Show |
Por ejemplo, el árbol
|
1 2 3 4 5 |
1 / \ 2 3 / \ 4 5 |
se representa por
|
1 2 |
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
|
1 |
sumaAlturas :: Arbol t -> Int |
tal que (sumaAlturas a) es la suma de las alturas de los elementos de a. Por ejemplo,
|
1 2 3 4 5 6 |
λ> 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving Show -- 1ª definición -- ============= 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) -- 2ª definición -- ============= sumaAlturas2 :: Arbol t -> Int sumaAlturas2 = snd . alturaYsumaAlturas -- (alturaYsumaAlturas a) es el par formado por la altura del árbol a y -- la suma de las alturas de los nodos de a. Por ejemplo, -- alturaYsumaAlturas H == (0,0) -- alturaYsumaAlturas (N 7 H H) == (1,1) -- alturaYsumaAlturas (N 7 (N 5 H H) H) == (2,3) -- alturaYsumaAlturas (N 7 (N 5 H (N 6 H H)) H) == (3,6) alturaYsumaAlturas :: Arbol t -> (Int,Int) alturaYsumaAlturas H = (0,0) alturaYsumaAlturas (N _ i d) = (a,a + si + sd) where (ai,si) = alturaYsumaAlturas i (ad,sd) = alturaYsumaAlturas d a = 1 + max ai ad -- 3ª definición -- ============= sumaAlturas3 :: Arbol t -> Int sumaAlturas3 = sum . alturas -- (alturas a) es la lista de las alturas de los nodos del árbol a. Por -- ejemplo, -- alturas H == [0] -- alturas (N 7 H H) == [1,0,0] -- alturas (N 7 (N 5 H H) H) == [2,1,0,0,0] -- alturas (N 7 (N 5 H (N 6 H H)) H) == [3,2,0,1,0,0,0] alturas :: Arbol t -> [Int] alturas H = [0] alturas (N _ a b) = (1 + max x y) : xs ++ ys where xs@(x : _) = alturas a ys@(y : _) = alturas b |