Caminos en un árbol binario con suma dada
Los árboles binarios se pueden representar con el de tipo de dato algebraico
|
1 2 3 |
data Arbol = H | N Int Arbol Arbol deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 7 8 9 |
3 7 1 / \ / \ / \ 2 4 5 8 / \ / \ \ / / \ / \ 1 7 5 6 4 9 3 -1 / \ / \ 2 1 4 5 / / \ \ 1 1 2 6 |
se representan por
|
1 2 3 4 5 |
ej1, ej2, ej3 :: Arbol ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H)) ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H)) ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H)) (N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H))) |
Definir las funciones
|
1 2 |
caminos :: Arbol -> [[Int]] caminosSuma :: Arbol -> Int -> [[Int]] |
tales que
- (caminos a) es la lista de los caminos entre dos nodos cualesquiera del árbol a. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> caminos ej1 [[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5], [2],[2,1],[2,7],[1],[7],[4],[4,5],[5]] λ> caminos ej2 [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9], [5],[5,6],[6],[8],[8,4],[8,9],[4],[9]] λ> length (caminos ej3) 33 |
- (caminosSuma a k) es la lista de los caminos entre dos nodos cualesquiera del árbol a cuya suma es k. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 |
λ> caminosSuma ej1 3 [[3],[2,1]] λ> caminosSuma ej3 3 [[3],[-1,4]] λ> caminosSuma ej3 4 [[1,3],[1,-1,4],[3,1],[-1,4,1],[-1,5],[4]] λ> caminosSuma ej3 5 [[1,3,1],[1,-1,4,1],[1,-1,5],[3,2],[3,1,1],[-1,4,2],[4,1],[5]] λ> caminosSuma ej3 6 [[1,3,2],[1,3,1,1],[1,-1,4,2],[4,2],[6]] λ> caminosSuma ej3 7 [] |
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 |
data Arbol = H | N Int Arbol Arbol deriving Show ej1, ej2, ej3 :: Arbol ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H)) ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H)) ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H)) (N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H))) caminos :: Arbol -> [[Int]] caminos H = [] caminos a@(N r i d) = caminosDesdeRaiz a ++ caminos i ++ caminos d -- (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la -- raíz de a hasta cualquiera de sus nodos. Por ejemplo. -- λ> caminosDesdeRaiz ej1 -- [[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5]] -- λ> caminosDesdeRaiz ej2 -- [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]] caminosDesdeRaiz :: Arbol -> [[Int]] caminosDesdeRaiz H = [] caminosDesdeRaiz (N x i d) = [x] : [x:ys | ys <- caminosDesdeRaiz i ++ caminosDesdeRaiz d] caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a k = [ys | ys <- caminos a , sum ys == k] |
Referencia
Basado en Print all k-sum paths in a binary tree de GeeksforGeeks.