Haskell列表树-预订单遍历

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

您可以以更通用的解决方案为目标，使您的数据类型成为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等（请参阅此处以获取参考）。

特别是，您正在搜索的列表可以通过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 2

使用模式匹配

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

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)