Haskell中的树遍历

Question

这里有一段遍历树的代码，但是它并没有起作用：

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]

我被要求执行以下任务：

Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

当我执行以上语句时，它会原样返回，但实际上应该返回：

preorder t = [8,3,5,2,1,9,6]

inorder t = [5,3,2,8,9,1,6]

postorder t =[5,2,3,9,6,1,8]

我该如何解决这个问题？

- Mnahi Aldossary

---

我不太明白你的问题；postorder (Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))) 给出了预期的结果，同时将 inorder 和 postorder 应用于同一棵树也是如此。 - valderman

由谁提出的问题？这是一道作业题吗？ - n. m.

如果t = Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))，那么它的运行结果符合预期。 - amindfv

哦！您真正评估的是 节点8（节点3（叶子5）（叶子2））（节点1（叶子9）（叶子6）），并且得到了相同的结果。这是数据，您需要将其传递给一个函数，以返回一个新值。 - amindfv

是的，正如@amindfv所写的那样，启动ghci并键入preorder（Node 8（Node 3（Leaf 5）（Leaf 2））（Node 1（Leaf 9）（Leaf 6）））（然后按回车键）。这将对此树评估函数preorder。 - danr

Answer 1

您提供的内容：

Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

一个Tree类型的值。你可以通过创建绑定或定义来为这个值命名。如果你正在源文件中工作，你可以直接进行如下操作：

myTree = Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

或者给它一个类型签名：

myTree :: Tree  -- this is the type signature
myTree = Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

如果您正在使用解释器ghci工作，您可以使用let创建一个新的定义：

Prelude> let myTree = Node 8 (Node 3 (Leaf 5) (Leaf 2)) (Node 1 (Leaf 9) (Leaf 6))

你的任务似乎是在给定这棵树的情况下评估postorder、inorder和preorder这些函数。 如果你在源文件中，请将结果保存在定义中：

inOrderResult :: [Int]
inOrderResult = inorder myTree

（请注意，我们将myTree作为参数传递给inorder函数。）如果您正在使用ghci，只需键入

Prelude> inorder myTree

将结果打印到终端。

- Matt Fenwick