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 |
Dedicado a Lucia < 3
Perdón, lo del max no funciona bien, habría que pensar otra forma para calcularlo en un sólo recorrido
¿Qué te parece hacerlo así? Creo que lo haría en un solo recorrido, la idea es definir otro tipo de dato con sintaxis de registro que acumule los resultados.
Muy buena idea, también se puede hacer sin tener que definir otro tipo de dato usando los pares, aunque la idea es completamente la misma