如何清理一个层级遍历函数？

Question

我正在处理定义如下的通用树设置：

data Tree a = Node a [Tree a] deriving (Eq, Read, Show)

通过这个设置，我创建了一个函数来打印树的特定级别的节点（根是级别 0，根的直接子级是级别 1，等等）。这是函数：

level :: Int -> Tree a -> [a]
level 0 (Node a _) = [a]
level n (Node _ subtrees) = concatMap (level (n - 1)) subtrees

以这个函数为基础，我创建了第二个函数，levelorder，它按层次顺序遍历打印树中所有节点的列表。该函数目前看起来像这样：

levelorder :: Tree a -> [a]
levelorder tree = level 0 tree ++ level 1 tree ++ level 2 tree ++ level 3 tree

虽然这对我目前正在处理的树非常有效，但我想将其清理到可以处理任何大小的树的位置。如您所见，它目前仅适用于具有 4 个级别（0 到 3）的树。我将如何实现这一点，直到我仍然可以利用关卡功能作为基础？

Answer 1

如果你有一个函数 depth :: Tree a -> Int 告诉你树有多深，它会像

一样简单

levelorder tree = concatMap (\lvl -> level lvl tree) [0..depth tree]

虽然这不是一个特别快的实现，但您最终会多次遍历树。

Answer 2

你首先需要一个深度函数，这样你就不需要固定你连接的层数。

depth :: Tree a -> Int
depth (Node _ [])       = 1
depth (Node _ r@(x:xs)) = 1 + maximum (map depth r)

然后，不要固定使用 (++) 的次数，您只需 concat map 在您从列表 [0..depth tree].

中绘制的每个级别上使用级别函数的结果

levelorder' tree = concatMap (flip level tree) [0..depth tree]

Answer 3

您可以依次遍历关卡，直到运行个节点：

levelorder :: Tree a -> [a]
levelorder t = concat $ takeWhile (not . null) $ map (`level` t) [0..]

How to clean up a level traversal function?