Haskell Tree to List - preorder遍历

Question

给定Haskell中的以下树结构：

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

如何让Haskell返回预排序的数据列表？

例如，给定一棵树：

Node 1 (Leaf 2) (Leaf 3)

返回类似如下的内容：

preorder = [1,2,3]

Answer 1

好吧，很抱歉回复得太晚了，但我按如下方式解决了这个问题：

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) 

Answer 2

您可以着眼于更通用的解决方案，使您的数据类型成为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)

这样，您就可以使用所有处理Foldable类型的函数，如elem、foldr、foldr、sum、minimum、maximum等(请参阅here的参考资料)。

特别是，您要搜索的列表可以使用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

Answer 3

使用模式匹配

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