Haskell树转换为列表 - 先序遍历

Question

在 Haskell 中，给定以下树形结构：

data Tree = Leaf Int | Node Int Tree Tree deriving Show

如何让Haskell返回一个先序遍历数据列表？

例如，给定一棵树：

Node 1 (Leaf 2) (Leaf 3)

返回类似以下内容：

preorder = [1,2,3]

- Gravy

---

不要忘记在满意后接受一个答案。 - Riccardo T.

Answer 1

你可以尝试采用更通用的解决方案，将你的数据类型实例化为Foldable。在hackage上有一个非常相似的示例，但它实现了后序访问。如果你想支持前序访问，你需要编写类似于以下内容的代码：

import qualified Data.Foldable as F

data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving Show

instance F.Foldable Tree where
    foldr f z (Leaf x) = f x z
    foldr f z (Node k l r) = f k (F.foldr f (F.foldr f z r) l)

通过这个方法，您可以使用所有适用于“可折叠”类型的函数，例如 elem, foldr, foldr, sum, minimum, maximum 等等（请参见此处）。

特别是，您可以使用 toList 来获得您正在查找的列表。以下是一些通过定义该实例而编写的示例：

*Main> let t = Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5)
*Main> F.toList t
[1,2,3,4,5]
*Main> F.foldl (\a x -> a ++ [x]) [] t
[1,2,3,4,5]
*Main> F.foldr (\x a -> a ++ [x]) [] t
[5,4,3,2,1]
*Main> F.sum t
15
*Main> F.elem 3 t
True
*Main> F.elem 12 t
False

- Riccardo T.

Answer 2

使用模式匹配

preorder (Leaf n) = [n]
preorder (Node n a b) = n:(preorder a) ++ (preorder b)

- Philip JF

---

我得到了以下错误信息： 无法匹配预期类型[t0]和实际类型Tree 在模式中：Node n a b 在preorder的等式中： preorder (Node n a b) = n : (preorder a) ++ (preorder b) - Gravy

@Gravy 这很奇怪。尝试添加一个明确的类型签名 preorder :: Tree -> [Int]。我觉得你会遇到错误并不合理。 - Philip JF

很奇怪，我刚刚测试了一下，似乎是可以工作的。你确定你复制了所有的内容吗？ - mck

@Gravy 还要确保你的 preorder (Leaf n) = [n] 而不是 preorder (Lead n) = n。那些 [ ] 很重要。 - Philip JF

preorder（Leaf n）= [n] preorder（Node n treeL treeR）= [n] ++ preorder treeL ++ preorder treeR - Gravy

Answer 3

好的，很抱歉回复晚了，但我按照以下方式使其工作：

preorder(Leaf n) = [n]
preorder(Node n treeL treeR) = [n] ++ preorder treeL ++ preorder treeR'code'

这对我仍然不起作用。

preorder (Leaf n) = [n]   
preorder (Node n a b) = n:(preorder a) ++ (preorder b) 

- Gravy