Haskell二叉树的前序遍历

Question

我正在尝试编写一个函数来遍历二叉树和 return 遇到的整数列表。我的数据树声明如下：

data Tree = Node Int Tree Tree | Leaf Int
   deriving (Eq,Show)

我的第一个想法是启动函数：

preorder :: Tree -> [a]  --take in tree, return list of ints

但是我在网上看到有人通过使用类似于以下的函数声明格式来解决这个问题：

preorder :: (a -> c) -> (b -> c) -> Tree -> [c]

而且我不太明白这条线是做什么的，它需要多个输入吗？

谢谢

Answer 1

这将取决于树的底层定义。他们可能正在使用另一种树定义，常见的是：

data Tree a b = Leaf b | Branch a (Tree a b) (Tree a b)

因此他们可能需要获取将类型 a 和 b 的值映射到类型 c 的函数。由于您的树定义仅包含 Int 类型的元素，因此 preorder 函数的类型为 Tree -> [Int].

就足够了

更新：

如果你想在树的元素类型中概括你的树，你可以声明这个数据类型：

data Tree a = Leaf a | Node a (Tree a) (Tree a)

通过这个定义，你可以定义preorder函数的类型如下：

preorder :: Tree a -> [a]

Haskell preorder traversal of binary tree