遍历Haskell中的二叉树并返回满足条件的树

Question

我试图遍历Haskell中的一个树，其中的想法是返回一个满足预定义条件的新树。如果节点的值x>=a和x<b、 则该节点应当被包括在新的树中。我必须能够遍历整个树和所有分支，以确保包括所有有效节点。

然而，现在我正在努力想出一个解决方案，当节点中不满足先决条件时，如何遍历左分支和右分支。

例如，对于a＝-5和b＝0，使得-5<＝x<0:

3
/ 
-12   8
/ 
1  -5 

应返回-5。因此，解决方案应该丢弃任何不满足前提条件的节点，如果满足了前提条件，就应该将该节点添加到新的树中。

这个代码就是我到目前为止得到的。

data Tree = Void | Node Tree Integer Tree 
deriving (Eq, Show) 
nextTree :: Integer -> Integer -> Tree -> Tree
nextTree _ _ Void = Void
nextTree a b (Node Void x Void) = if x >= a && x < b then Node Void x Void else Void
nextTree a b (Node l x Void) = if x >= a && x < b then Node (nextTree a b l) x Void else nextTree a b l
nextTree a b (Node Void x r) = if x >= a && x < b then Node Void x (nextTree a b r) else nextTree a b r
nextTree a b (Node l x r)  
|  x >= a && x < b = Node (nextTree a b l) x (nextTree a b r) 
| not (x >= a && x < b) = undefined
| otherwise = undefined

正是在写undefined的地方，我需要一些方法来遍历左分支和右分支，然后将下一个子树返回到nextTree。我只是做

| not (x >= a && x < b) = nextTree (a b r)

它将只遍历右分支。我想要这样的东西

| not (x >= a && x < b) = nextTree (a b r) && nextTree (a b r)

但我不知道如何在哈斯克尔做到这一点。或者如果可能的话？

Answer 1

首先，我将简化您的分支逻辑。与其多次重复keep条件和递归情况，不如只写一次并对其结果进行模式匹配。此外，如果我们在闭包中捕获lo和hi，我们可以避免在链上下重复传递它们：

nextTree :: Integer -> Integer -> Tree -> Tree
nextTree lo hi = go
where go Void = Void
go (Node l x r) = case (x >= lo && x < hi, go l, go r) of
(True, l', r') -> Node l' x r'
(False, Void, r') -> r'
(False, l', Void) -> l'
(False, l', r') -> undefined

这和你的问题是一样的逻辑，但随着重复的消失，我们可以看到森林，而不是陷入树木和嘘声中。我还删除了Node Void x Void案例，因为它已经包含在您的其他案例中。

现在，我们可以清楚地看到还有什么需要处理：您有两个子树(已经递归修剪(，但曾经是它们的父节点的节点正在消失。所以，你需要的是一些函数，把两棵树变成一棵树。当然，你不可能总是在完美地保留结构的同时做到这一点：在某个时刻，你必须做出一些任意的决定，决定将原始节点的值放在其中一个子树的哪里。

让我们把这个函数称为graft:

nextTree :: Integer -> Integer -> Tree -> Tree
nextTree lo hi = go
where go Void = Void
go (Node l x r) = case (x >= lo && x < hi, go l, go r) of
(True, l', r') -> Node l' x r'
(False, Void, r') -> r'
(False, l', Void) -> l'
(False, l', r') -> graft l' r'
graft a Void = a
graft Void b = b
graft (Node l x r) n = Node (graft l r) x n

如果我们找到一个虚空，我们就会放下那棵树，然后归还另一棵。否则，我们有两个非虚空树。我们任意选择不使用右树，提升左节点的值作为新的父节点，然后将左节点的两个子节点移植到一起。

在编写这个函数时，我没有任何特别的计划。在nextTree中，我只是删除了重复，直到剩下一些简单的东西，而未实现的情况有一个清晰的"；"洞"；其中，我们有两个Tree值，因此需要一个Tree。所以，试着写一个这种类型的函数。同样，应用模式匹配：前两种情况很简单，最后一种情况也不错：一旦你意识到剩下的都是了，你唯一能做的就是创建一个Node，提升x，并递归调用graft。这种方法通常被称为面向孔的编程，值得一试。