Recorrido de árboles en espiral
Los árboles se pueden representar mediante el siguiente tipo de datos
data Arbol a = N a [Arbol a] deriving Show
Por ejemplo, los árboles
1 1 1
/ \ / \ / \
/ \ 8 3 8 3
2 3 /|\ /|\ |
/ \ / \ 4 5 6 4 5 6 7
4 5 6 7
se representan por
ej1, ej2, ej3 :: Arbol Int ej1 = N 1 [N 2 [N 4 [], N 5 []], N 3 [N 6 [], N 7 []]] ej2 = N 1 [N 8 [], N 3 [N 4 [], N 5 [], N 6 []]] ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]
Definir la función
espiral :: Arbol a -> [a]
tal que (espiral x) es la lista de los nodos del árbol x recorridos en espiral; es decir, la raíz de x, los nodos del primer nivel de izquierda a derecha, los nodos del segundo nivel de derecha a izquierda y así sucesivamente. Por ejemplo,
espiral ej1 == [1,2,3,7,6,5,4] espiral ej2 == [1,8,3,6,5,4] espiral ej3 == [1,8,3,7,6,5,4]
Soluciones
data Arbol a = N a [Arbol a] deriving Show ej1, ej2, ej3 :: Arbol Int ej1 = N 1 [N 2 [N 4 [], N 5 []], N 3 [N 6 [], N 7 []]] ej2 = N 1 [N 8 [], N 3 [N 4 [], N 5 [], N 6 []]] ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]] espiral :: Arbol a -> [a] espiral x = concat [f xs | (f,xs) <- zip (cycle [reverse,id]) (niveles x)] -- (niveles x) es la lista de los niveles del árbol x. Por ejemplo, -- niveles ej1 == [[1],[8,3],[4]] -- niveles ej2 == [[1],[8,3],[4,5,6]] -- niveles ej3 == [[1],[8,3],[4,5,6,7]] niveles :: Arbol a -> [[a]] niveles x = takeWhile (not . null) [nivel n x | n <- [0..]] -- (nivel n x) es el nivel de nivel n del árbol x. Por ejemplo, -- nivel 0 ej1 == [1] -- nivel 1 ej1 == [8,3] -- nivel 2 ej1 == [4] -- nivel 4 ej1 == [] nivel :: Int -> Arbol a -> [a] nivel 0 (N x _) = [x] nivel n (N _ xs) = concatMap (nivel (n-1)) xs