通过折叠找到二叉搜索树的所有叶子

Question

我得到了从该数据类型的二叉树中获取所有叶子的任务：

data Bintree el = Empty |
                  Tree {left :: Bintree el, node :: el, right :: Bintree el} deriving Show

现在我有了这个 Treefold 函数，它在测试中完美运行：

binTreeFold :: (a -> b -> a -> a) -> a -> Bintree b -> a
binTreeFold f el Empty = el 
binTreeFold f el tree@(Tree leftTree node rightTree) = f (binTreeFold f el leftTree) node (binTreeFold f el rightTree)

我尝试获取所有叶子，但不知何故它根本不起作用（下面提到的编译问题）：

leavesWithFold :: Bintree a -> [a]
leavesWithFold Empty = []
leavesWithFold tree =  binTreeFold (\left -> \node -> \right -> if (checkIfTreeIsLeaf node) then left ++ [node] ++ right else left ++ [] ++ right) [] tree

使用以下函数：

checkIfTreeIsLeaf :: Bintree a -> Bool
checkIfTreeIsLeaf Empty = False
checkIfTreeIsLeaf (Tree Empty node Empty) = True
checkIfTreeIsLeaf _ = False

编译器告诉我

Couldn't match type `a' with `Bintree a0'

但在以前的函数中使用

left ++ [node] ++ right

工作得很好。你知道我做错了什么吗？我可能会改变什么？

祝福

Answer 1

通常情况下，使用 fold 函数的想法是它会为您完成所有工作。所以通过编写一个分支到 Empty case 和 tree case 的函数，这已经有点奇怪了。

一种递归方法

但是让我们简单地从递归方法开始。暂时忘记折叠等。我们一般如何生成叶子列表？

这里基本上有三种情况：

如果我们遇到 Empty，那么我们 return 空列表，因为 Empty 不是 而不是 一片叶子，我们应该 return 所有叶子，所以：
```
leaves Empty = []
```
万一遇到Tree左右子树都是Empty，我们就知道Tree是叶子，所以我们return 它携带的元素，作为一个列表：
```
leaves (Tree Empty x Empty) = [x]
```
如果两个子树之一（或两者）不是Empty，我们将递归调用leaves函数，并将两者连接在一起：
```
leaves (Tree l _ r) = leaves l ++ leaves r
```

所以现在我们得到了完整的：

leaves :: Bintree a -> [a]
leaves Empty = []
leaves (Tree Empty x Empty) = [x]
leaves (Tree l x r) = leaves l ++ leaves r

如何通过递归检测这个是一片叶子

我们当然不能用 binTreeFold 方法做到这一点。但是我们不能检测一棵树是否真的是一片叶子吗？如果两次递归调用 both 导致一个空列表，我们知道当前 Bintree 实际上是一个叶子。事实上：如果左（和右）子树是 Empty，它们会导致空列表。如果这些不为空，那么这些要么是叶子，将递归地产生一个单例列表，要么那些不是 Tree 具有后代的，最终将导致叶子，从而导致非空列表。

在 fold 函数中对此进行编码

所以我们首先看一下递归调用，然后根据这些是两个空列表，还是return一个单例列表叶元素，或将两个列表连接在一起，如：

f [] x [] = [x]
f l _ r = l ++ r

或者在 binTreeFold 函数中使用：

leavesWithFold :: Bintree a -> [a]
leavesWithFold = binTreeFold f []
    where f [] x [] = [x]
          f l _ r = l ++ r

通过折叠找到二叉搜索树的所有叶子

Find all leafes of a binary searchtree by folding

binary-tree

haskell

fold

一种递归方法

如何通过递归检测这个是一片叶子

在 fold 函数中对此进行编码