Recorrido por niveles de árboles binarios
Los árboles binarios con valores en las hojas y en los nodos se definen por
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Eq, Show) |
Por ejemplo, el árbol
|
1 2 3 4 5 6 7 |
1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 |
se pueden representar por
|
1 2 3 4 |
ejArbol :: Arbol Int ejArbol = N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)) |
Definir la función
|
1 |
recorrido :: Arbol t -> [t] |
tal que (recorrido a) es el recorrido del árbol a por niveles desde la raíz a las hojas y de izquierda a derecha. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> recorrido (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7))) [1,2,3,4,5,6,7,8,9] λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (N 5 (H 8) (H 9)))) [1,3,2,6,7,4,5,8,9] λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (H 5))) [1,3,2,6,7,4,5] λ> recorrido (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7))) [1,2,3,4,5,6,7] λ> recorrido (N 1 (N 2 (H 4) (H 5)) (H 3)) [1,2,3,4,5] λ> recorrido (N 1 (H 4) (H 3)) [1,4,3] λ> recorrido (H 3) [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 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 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Eq, Show) ejArbol :: Arbol Int ejArbol = N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)) -- 1ª definición -- ============= recorrido :: Arbol t -> [t] recorrido = concat . niveles -- (niveles a) es la lista de los niveles del árbol a. Por ejemplo, -- λ> niveles (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7))) -- [[1],[2,3],[4,5,6,7],[8,9]] niveles :: Arbol t -> [[t]] niveles (H x) = [[x]] niveles (N x i d) = [x] : mezcla (niveles i) (niveles d) -- (mezcla xss yss) es la lista obtenida concatenando los -- correspondientes elementos de xss e yss. Por ejemplo, -- λ> mezcla [[1,3],[2,5,7]] [[4],[1,9],[0,14]] -- [[1,3,4],[2,5,7,1,9],[0,14]] -- λ> mezcla [[1,3],[2,5,7]] [[4]] -- [[1,3,4],[2,5,7]] mezcla :: [[a]] -> [[a]] -> [[a]] mezcla [] yss = yss mezcla xss [] = xss mezcla (xs:xss) (ys:yss) = (xs ++ ys) : mezcla xss yss -- 2ª definición -- ============= recorrido2 :: Arbol t -> [t] recorrido2 = concat . niveles2 -- (niveles2 a) es la lista de los niveles del árbol a. Por ejemplo, -- λ> niveles2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7))) -- [[1],[2,3],[4,5,6,7],[8,9]] niveles2 :: Arbol t -> [[t]] niveles2 a = takeWhile (not . null) [nivel n a | n <- [0..]] -- (nivel n a) es el nivel iésimo del árbol a. Por ejemplo, -- λ> nivel 2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7))) -- [4,5,6,7] -- λ> nivel 5 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7))) -- [] nivel :: Int -> Arbol t -> [t] nivel 0 (H x) = [x] nivel n (H _) = [] nivel 0 (N x _ _) = [x] nivel n (N x i d) = nivel (n-1) i ++ nivel (n-1) d |