Recorrido por niveles de árboles binarios
Los árboles binarios con valores en las hojas y en los nodos se definen por
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 / \ 8 9
se pueden representar por
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
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,
λ> 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
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