Haskell 中的级别顺序

Question

我有一棵树的结构，我想按级别打印树。

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]

但如何按级别进行呢？ “levels tree”应该打印[“a”，“bde”，“cgflm”，“hijkn”，“o”]。 我认为“迭代”是适合此目的的函数，但我无法想出如何使用它的解决方案。请你帮我一下好吗？

Answer 1

您只需要计算所有子树的级别，然后将它们全部压缩到根之后：

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

遗憾的是， zipWith 没有做正确的事情，所以我们可以改为使用：

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 中，首先“报告”当前项目，然后递归所有这些节点的尾部。在postorder中，这两个步骤是相反的。在这两种情况下，递归都是“本地”的，即它一次只需要处理一个节点。 levelorder 是这样吗？或者换个角度问，levelorder递归时，递归的结果是否交互？如果是这样，那么，如果不是单个树，那么递归的“单位”是什么？

了解 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 都是如此，并且是广度优先遍历的通常定义。

相反，如果您确实希望按级别对元素进行分组，只需将 ++ 运算符更改为 : 将产生该版本：

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

注意：我已经为所有顶级元素提供了类型签名级函数。这是一个非常值得养成的好习惯，并且会节省您大量的调试时间。

Answer 3

这是另一个版本，可以应用于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

Answer 4

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)

结果我的做法比我想要的更加笨拙。如果我错了，请纠正我，因为字符串是字符列表，但是您使用的是多态类型，那么像问题中指定的那样打印结果真的那么简单吗？此代码生成字符串列表的列表。 ***克里斯在他更优雅的回答中提醒我有关 concat 的使用！

Answer 5

您可以对空列表重复 [] ，这样就不会出现 zipWith 的问题

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