Haskell遍历树的中序、前序和后序

Question

I have the following Haskell data definition:

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

我编写了以下程序来遍历树的先序、中序和后序：

preorder(Leaf n) = n
preorder(Node n t0 t1) = [n] ++ preorder t0 ++ preorder t1

inorder(Leaf n) = n
inorder(Node n t0 t1) = inorder t0 ++ [n] ++ inorder t1

postorder(Leaf n) = n
postorder(Node n t0 t1) = postorder t0 ++ postorder t1 ++ [n]

我得到的错误是：

- Type error in application  
*** Expression     : preorder t0 ++ preorder t1  
*** Term           : preorder t1  
*** Type           : Int  
*** Does not match : [a]  

我需要返回一个包含所有三个整数的适当顺序列表。由于我是Haskell的新手，所以非常感谢任何帮助。

- Adriana

Answer 1

你从基础情况返回了Int，但从构造情况返回了[Int]。 叶子节点也应该是列表。

- geekosaur

---

我编辑了问题以使其更清晰。我需要返回一份包含树中所有整数的列表。你能详细说明吗？ - Adriana

我正在努力弄清楚这是否是作业。但是：在递归情况下您使用了 [n]。那么在基本情况下，您认为应该使用什么？ - geekosaur

Answer 2

错误信息如下：

preorder(Leaf n) = n

Should be:

preorder(Leaf n) = [n] 

同样适用于中序遍历和后序遍历。

- Adriana

Answer 3

更改函数可以修复错误，但您只能将元素成对插入到您的树中。

最好改为：

data Tree = Leaf | Branch Int Tree Tree deriving Show

inorder Leaf = []
inorder (Branch n left right) = inorder left ++ [n] ++ inorder right
-- etc.

一个检查不同语言下算法实现的好网页是Rosetta Code，其中包括了关于树遍历的页面，其中也有Haskell的实现。

- Ondřej Šebek