haskell - 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]

我该如何解决这个问题？

Answer 1

你所给予的:

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

是Tree类型的值。您可以通过为其创建绑定(bind)或定义来为该值命名。如果您正在处理源文件，则可以这样做

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

将结果打印到终端。