Caminos maximales en árboles binarios
Consideremos los árboles binarios con etiquetas en las hojas y en los nodos. Por ejemplo,
1 2 3 4 5 6 7 |
5 / \ 2 4 / \ 7 1 / \ 2 3 |
Un camino es una sucesión de nodos desde la raiz hasta una hoja. Por ejemplo, [5,2] y [5,4,1,2] son caminos que llevan a 2, mientras que [5,4,1] no es un camino, pues no lleva a una hoja.
Definimos el tipo de dato Arbol y el ejemplo por
1 2 3 4 5 |
data Arbol = H Int | N Arbol Int Arbol deriving Show arb1:: Arbol arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3))) |
Definir la función
1 |
maxLong :: Int -> Arbol -> Int |
tal que (maxLong x a) es la longitud máxima de los caminos que terminan en x. Por ejemplo,
1 2 3 |
maxLong 3 arb1 == 4 maxLong 2 arb1 == 4 maxLong 7 arb1 == 3 |
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 |
data Arbol = H Int | N Arbol Int Arbol deriving Show arb1:: Arbol arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3))) -- 1ª solución (calculando los caminos) -- ------------------------------------ -- (caminos x a) es la lista de los caminos en el árbol a desde la raíz -- hasta las hojas x. Por ejemplo, -- caminos 2 arb1 == [[5,2],[5,4,1,2]] -- caminos 3 arb1 == [[5,4,1,3]] -- caminos 1 arb1 == [] caminos :: Int -> Arbol -> [[Int]] caminos x (H y) | x == y = [[x]] | otherwise = [] caminos x (N i r d) = map (r:) (caminos x i ++ caminos x d) maxLong1 :: Int -> Arbol -> Int maxLong1 x a = maximum (0: map length (caminos x a)) -- 2ª solución -- ----------- maxLong2 :: Int -> Arbol -> Int maxLong2 x a = maximum (0 : aux x a) where aux x (H y) | x == y = [1] | otherwise = [] aux x (N i r d) = map (+1) (aux x i ++ aux x d) |