Haskell中的等级序

xvw2m8pv  于 2022-11-14  发布在  其他
关注(0)|答案(5)|浏览(204)

我有一个树的结构,我想按级别打印该树。

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]

但是如何通过层次来实现呢?“层次树”应该打印[“a”,“bde”,“cgflm”,“hijkn”,“o”]。我认为“iterate”是适合这个目的的函数,但是我不能想出一个如何使用它的解决方案。你能帮助我吗?

qvsjd97n

qvsjd97n1#

You just need to compute the levels for all of the subtrees and zip them all together after the root:

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

Sadly, zipWith doesn't do the right thing, so we can instead use:

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

Update: there is some concern (which I agree with) that what you originally asked is a little weird as it's not a generic breadth-first tree to list convertor. What you probably really want is to concat the result of:

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

izj3ouym2#

I'm guessing this is homework. On the assumption that it is, then here's some ideas for how to think about the problem that might lead you to an answer:
In preorder , first the current item is "reported", then recurse for all this node's tails. In postorder these two steps are done in reverse. In both cases, the recursion is "local", in the sense that it only need deal with one node at a time. Is this true for levelorder ? Or to ask it another way, when levelorder recurses, do the results of the recursions interact or no? If so, then, what is the "unit" of recursion, if not a single Tree ?
Understanding the nature of the recursion (or iteration..?) of levelorder will lead you to a solution that very simple and elegant. My version is only three lines long!
By the way, it might be nice to have these utility functions to make the code even clearer in some places:

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

Or, if you are familiar with record syntax in Haskell, you can achieve exactly this by changing your original Tree definition to:

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

A full solution:

The key is realizing that levelorder requires recursion on a list of Tree . At each step the elements from each Tree is extracted, and the next step is upon the concatenation of the subtrees:

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

This produces the elements in a single, flattened list, much like preorder and postorder do, and is the usual definition of a breadth-first traversal.
If instead you really want the elements grouped by level, a single change of the ++ operator to : will yield that version:

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

Note: I have given type signatures for all top-level functions. This is a really good habit to get into, and will save you considerable time debugging.

ht4b089n

ht4b089n3#

Here is another version which can be applied to Tree a instead of 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

If you want to concatenate the strings at the end you may use:

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

zbwhf8kr4#

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's Nd's 
extractl :: [Tree a] -> [Tree a]
extractl [] = []
extractl ((Nd x ts):xs) = ts ++ (extractl xs)

我的方法比我想的要笨拙一些。如果我错了,请纠正我,因为字符串是字符列表,但是您使用的是多态类型,打印出问题中指定的结果真的这么简单吗?这段代码生成了字符串列表。***Chris在他更优雅的回答中提醒我使用concat!!

zazmityj

zazmityj5#

您可以对空列表重复[],这样就不会遇到zipWith的问题

levels :: Tree a -> [[a]]
levels Empty          = repeat []
levels (Branch x l r) = [x] : zipWith (++) (levels l) (levels r)

相关问题