Menu Close

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 []]]
 
-- 1ª solución
-- ===========
 
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
 
-- 2ª solución
-- ===========
 
espiral2 :: Arbol a -> [a]
espiral2 = 
  concat . zipWith ($) (cycle [reverse,id]) . niveles
 
-- 3ª solución
-- ===========
 
espiral3 :: Arbol a -> [a]
espiral3 = concat . zipWith ($) (cycle [reverse,id]) . niveles3
 
niveles3 :: Arbol a -> [[a]]
niveles3 t = map (map raiz)
           . takeWhile (not . null)
           . iterate (concatMap subBosque) $ [t]
 
raiz :: Arbol a -> a
raiz (N x _) = x
 
subBosque :: Arbol a -> [Arbol a]
subBosque (N _ ts) = ts
 
-- 4ª solución
-- ===========
 
espiral4 :: Arbol a -> [a]
espiral4 = concat . zipWith ($) (cycle [reverse,id]) . niveles4
 
niveles4 :: Arbol a -> [[a]]
niveles4 = map (map raiz)
         . takeWhile (not . null)
         . iterate (concatMap subBosque)
         . return  
 
-- 5ª definición
-- =============
 
espiral5 :: Arbol a -> [a]
espiral5 x = concat $ zipWith ($) (cycle [reverse,id]) $ niveles5 [x]
 
niveles5 :: [Arbol a] -> [[a]]
niveles5 [] = []
niveles5 xs = a : niveles5 (concat b)
  where (a,b) = unzip $ map (\(N x y) -> (x,y)) xs
 
-- 6ª definición
-- =============
 
espiral6 :: Arbol a -> [a]
espiral6 = concat . zipWith ($) (cycle [reverse,id]) . niveles5 . return

5 soluciones de “Recorrido de árboles en espiral

  1. angruicam1
    data Arbol a = N {rootLabel :: a,
                      subForest :: [Arbol a]}
      deriving Show
     
    espiral :: Arbol a -> [a]
    espiral =
      concat . zipWith ($) (cycle [reverse,id]) . levels
     
    -- (levels t) es la lista de niveles del árbol t. Por ejemplo,
    --    levels ej1  ==  [[1],[2,3],[4,5,6,7]]
    --    levels ej2  ==  [[1],[8,3],[4,5,6]]
    --    levels ej3  ==  [[1],[8,3],[4,5,6,7]]
    levels :: Arbol a -> [[a]]
    levels t =
      map (map rootLabel)
      . takeWhile (not . null)
      . iterate (concatMap subForest) $ [t]
  2. alerodrod5
     
    data Arbol a = N a [Arbol a]
         deriving Show
     
    espiral :: Arbol a -> [a]
    espiral a = concat [nivel x  a | x <- [1..b]]
      where b = profundidad  a
     
    profundidad :: Arbol a -> Int
    profundidad (N _ []) = 1
    profundidad (N _ xs) = 1 + maximum [profundidad a | a <- xs]
     
    nivel :: Int -> Arbol a -> [a]
    nivel 1 (N x _) = [x]
    nivel x (N _ xs)
      | odd x     = reverse $ concat [nivel (x-1) a| a <- xs]
      | otherwise = concat [nivel (x-1) a| a <- xs]
  3. antnavoro
    data Arbol a = N a [Arbol a]
      deriving Show
     
    espiral :: Arbol a -> [a]
    espiral x = concat $ zipWith ($) (cycle [reverse,id]) $ listas [x]
    listas :: [Arbol a] -> [[a]]
    listas [] = []
    listas xs = a : listas (concat b)
      where (a,b) = unzip $ map ((N x y) -> (x,y)) xs
  4. jorcatote
    espiral :: Arbol a -> [a]
    espiral = map fst
            . concat
            . espiralizar
            . groupBy ((_,b) (_,d)-> b == d)
            . sortBy ((a,b) (c,d) -> compare b d)
            . aux 0
     
    espiralizar :: [[a]] -> [[a]]
    espiralizar []       = []
    espiralizar [x]      = [reverse x]
    espiralizar (x:y:xs) = reverse x : y: espiralizar xs
     
    aux :: Int -> Arbol a -> [(a,Int)]
    aux b (N a []) = [(a,b)]
    aux b (N a xs) = (a,b) : concatMap (aux (b+1)) xs
  5. jaibengue
    data Arbol a = N a [Arbol a]
                 deriving Show
     
    espiral :: Arbol a -> [a]
    espiral = aux . niveles
      where aux (xs:ys:zss) = reverse xs ++ ys ++ aux zss
            aux [xs]        = reverse xs
            aux []          = []
     
    niveles :: Arbol a -> [[a]]
    niveles (N r h) = [r] : aux (map niveles h)
      where aux (xs:xss)       = aux2 xs (aux xss)
            aux []             = []
            aux2 (y:ys) (z:zs) = (y ++ z) : aux2 ys zs
            aux2 ys []         = ys
            aux2 [] zs         = zs

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.