在列表中每层打印二叉树

Question

函数应该在层中打印参数树的标记，作为层列表。每个层中的节点和叶标记是从左到右列出的，即层中最左边的节点，列表的第一个元素，最右边的节点是列表的最后一个元素。Ord类型的参数指示从最小层到最大层(TopDown)的升序层还是从最大层到最小层(BottomUp)的降序层。

data Tree = Leaf Integer | Node Integer Tree Tree

type Layer = [Integer]

data Ord = BottomUp | TopDown

wLayer :: Tree -> Ord -> [Layer] 

示例1:我们使用参数调用函数wLayer

wLayer (节点1(节点2(叶21) (叶22)) (节点3(叶31) (叶32)) TopDown结果：[1,2,3,21,22,31,32]

例2: wLayer (节点1(节点2(叶21) (叶22)) (节点3(叶31) (叶32)) BottomUp结果：[21,22,31,32,2,3,1]

我怎样才能实现这一目标？

编辑

data Tree = Leaf Integer
          | Node Integer Tree Tree
type Layer = [Integer]
data Ord   = BottomUp | TopDown

writeLayer :: Tree -> Ord -> [Layer]
writeLayer Leaf x = [x]
writeLayer (Node x lt rt) BottomUp = (writeLayer rt BottomUp) ++ [x] ++ (writeLayer lt BottomUp)
writeLayer (Node x lt rt) TopDown  = [x] ++ (writeLayer lt TopDown) ++ (writeLayer rt TopDown)

这是我的程序，但它不工作，我怎么能修复它呢？

Answer 1

这里有一个简单的方法来实现这一点。它接受一个级别上的所有节点，并从它们中提取整数值，然后对这些相同节点的所有子节点进行递归。之后，您将在Ord上进行匹配，以确定是否需要反转列表。

writeLayer t o =
    case o of
        BottomUp -> reverse $ makeLayer [t]
        TopDown -> makeLayer [t]
    where
        extract (Node i _ _) = i
        extract (Leaf i) = i
        children (Node _ a b) = [a, b]
        children _ = []
        makeLayer [] = []
        makeLayer ts = map extract ts : (makeLayer $ concat $ map children ts)

Answer 2

一些提示：

• Tree是一个Leaf的情况很简单。
• BottomUp和TopDown的区别似乎在于您是否反转了Layer的列表
• 当Tree是一个Node时，您将不得不在子树上递归并以某种方式组合结果

编辑： OK，让我们集中讨论其中的第一个。

你对于这个案子的方程式是

writeLayer Leaf x = [x]

首先，Leaf x需要放在括号中，因为它是一个Tree值。

writeLayer (Leaf x) = [x]

第二，方程需要反映writeLayer有两个参数(正如上面所写的，它只需要一个参数)。对于Leaf值，我们不关心返回结果的顺序--我们给出的答案是相同的--但是我们仍然必须接受参数。我们使用_来表示我们不关心参数之上的问题，也不打算使用它。

writeLayer (Leaf x) _ = [x]

第三，[x]是Integers的(单元素)列表--但是我们应该返回一个Layers的列表，我相信您可以找到解决这个问题的方法。

最后，注意电脑给你的错误信息。理解他们。

Answer 3

Paul的回答给出了水平顺序遍历的共同递归定义--对列表的展开。(练习:使用makeLayer编写Data.List.unfoldr。)这也是我最喜欢的方式，参见被低估的人。

但它也可以递归地进行--就像树上的折叠一样。这些定义与清单上的foldr相似，定义如下：

foldt :: (Integer->a) -> (Integer->a->a->a) -> Tree -> a
foldt f g (Leaf n)     = f n
foldt f g (Node n t u) = g n (foldt f g t) (foldt f g u)

然后，通过一个简单的树折叠给出水平级遍历，并使用一个可能的reverse。

wLayer :: Tree -> Order -> [Layer] 
wLayer t o = (if o==BottomUp then reverse else id) (foldt single glue t)

我冒昧地将您的标志类型Order重命名为无效名称冲突，并使其成为Eq的实例。

data Order = BottomUp | TopDown deriving Eq

函数single对叶子进行水平顺序遍历：

single :: Integer -> [Layer]
single n = [[n]]

而glue将一个标签和两个子节点的遍历组合到一个节点的遍历中：

glue :: Integer -> [Layer] -> [Layer] -> [Layer]
glue n x y = [n] : longzipwith (++) x y

关键成分是函数longzipwith，它类似于zipWith，只不过(i)结果的长度是较长的参数的长度，而不是较短的参数，因此(ii)二进制运算符必须是a->a->a。

longzipwith :: (a->a->a) -> [a] -> [a] -> [a]
longzipwith f (a:x) (b:y) = f a b : longzipwith f x y
longzipwith f x     []    = x
longzipwith f []    y     = y