Haskell level-order

Question

I have a structure for a tree, and I want to print the tree by levels.

data Tree a = Nd a [Tree a] deriving Show
type Nd = String
tree = Nd "a" [Nd "b" [Nd "c" [],
                       Nd "g" [Nd "h" [],
                               Nd "i" [],
                               Nd "j" [],
                               Nd "k" []]],
               Nd "d" [Nd "f" []],
               Nd "e" [Nd "l" [Nd "n" [Nd "o" []]],
                       Nd "m" []]]
preorder (Nd x ts) = x : concatMap preorder ts
postorder (Nd x ts) = (concatMap postorder ts) ++ [x]

But how to do it by levels? The "level tree" should print ["a", "bde", "cgflm", "hijkn", "o"]. I think that “iteration” would be a suitable function for this purpose, but I cannot figure out how to use it. Will you help me please?

Answer 1

You just need to calculate the levels for all subtrees and fix them all together after root:

levels :: Tree [a] -> [[a]]
levels (Nd a bs) = a : foldr (zipWith' (++)) [] (map levels bs)

Unfortunately, zipWithit does not do the right thing, so we can use instead:

zipWith' f xs [] = xs
zipWith' f [] xs = xs
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

: ( ), , , , , . , , , , , :

levels' (Nd a bs) = [a] : foldr (zipWith' (++)) [] (map levels' bs)

Answer 2

, . , , , , :

preorder , node . postorder . "", , node . levelorder? -, levelorder recurses, ? , "" , Tree?

( ..?) of levelorder , . !

, , :

element :: Tree a -> a
element (Nd x _) = x
subtrees :: Tree a -> [Tree a]
subtrees (Nd _ s) = s

, Haskell, , Tree :

data Tree a = Nd { element :: a, subtrees :: [Tree a] }
    deriving Show

---

:

, levelorder Tree. Tree, - :

levelorder :: Tree a -> [a]
levelorder t = step [t]
    where step [] = []
          step ts = map element ts ++ step (concatMap subtrees ts)

, , preorder postorder do, .

, , ++ : :

bylevel :: Tree a -> [[a]]
bylevel t = step [t]
    where step [] = []
          step ts = map element ts : step (concatMap subtrees ts)

. . , .

Answer 3

levels :: (Tree a) -> [[a]]
levels (Nd x ts) = [[x]] ++ levelshelper ts

level2 = (map concat).levels

levelshelper :: [Tree a] -> [[a]]
levelshelper [] = []
levelshelper xs = (map (\(Nd x ts) -> x) xs) : (levelshelper (extractl xs))

--get the next level Nd 
extractl :: [Tree a] -> [Tree a]
extractl [] = []
extractl ((Nd x ts):xs) = ts ++ (extractl xs)

, . , , , , , ? . *** , concat!!

Answer 4

, Tree a Tree [a].

levelorder :: Tree a -> [[a]]
levelorder (Nd x ts) = [x]:(ziplist (map levelorder ts))

ziplist :: [[[a]]] -> [[a]]
ziplist l = if null ls then [] else (concat heads):(ziplist tails)
    where
        ls = filter (not.null) l
        heads = map head ls
        tails = map tail ls

, :

levelorder2 :: Tree [a] -> [[a]]
levelorder2 = (map concat).levelorder