如何在Haskell的列表中返回树的叶子

Question

到目前为止我有这个代码:

data BinaryTree a  = Null | Node a (BinaryTree a) (BinaryTree a)

treeLeaves :: BinaryTree a -> [a]
treeLeaves tree = case tree of
    Null         -> []
    Node v t1 t2 -> [] ++ treeLeaves t1 ++ treeLeaves t2

我不确定我做错了什么.它输出一个空列表.

Answer 1

现在你错过了重要的一步,即将叶子添加到列表中,这就是为什么你总是得到一个空列表.这[] ++ treeLeaves t1 ++ treeLeaves t2将最终落入Null分支,并成为[] ++ [] ++ ... ++ []Zeta评论.

你知道你已经达到了叶时BinaryTree是Node v Null Null.所以你需要为这个案例写一个分支:

treeLeaves :: BinaryTree a -> [a]
treeLeaves tree = case tree of
    Null             -> []
    Node v Null Null -> v:[]
    Node _ t1 t2     -> treeLeaves t1 ++ treeLeaves t2

正如Igor所评论的那样,您可以使用_而不是v在最后一行,因为您没有在该节点中使用该元素(因为它不是叶子).