Menu Close

Recorrido de árboles en espiral

José A. Alonso,

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
Posted in Ejercicio
Tagged , , , , , , , , , , ,

5 Comments

  1. angruicam1
    Responder 
    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
    Responder 
     
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
    Responder 
    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
    Responder 
    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
    Responder 
    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.