haskell - 在 Haskell 中删除具有特定 Int 的树叶

Question

我有定义的类型:数据树=节点树树|叶国际|无。我想创建一个方法 delete::Tree -> Int -> Tree ，它删除具有第二个参数中给出的特定 Int 的所有 Leaf 。

Answer 1

如果你的树没有任何特定的结构，你可以这样做

delete NIL _ = NIL
delete (Leaf i) int | i == int = NIL
                    | otherwise = Leaf i
delete (Node left right) int = Node (delete left int) (delete right int)

为什么？

删除 NIL _ = NIL 因为我们必须处理所有情况，甚至是末端的空树。 _ 代表我们不关心的任何值。

delete (Leaf i) int | i == int = NIL
                    | otherwise = Leaf i

因为我们需要首先检查| i== int 来查看我们是否要删除该节点。如果这样做，我们将其替换为空的三个，NIL。否则，我们就不管它。

delete (Node left right) int = Node (delete left int) (delete right int) 因为如果我们在一个节点上，我们需要删除 int 来自 left 和 right 子树。

你最终不会得到一大堆 NIL 吗？

是的，我想这可能会发生。你可以用

来清除

prune (Node  NIL      NIL    ) = NIL
prune (Node (Leaf i)  NIL    ) = Leaf i 
prune (Node  NIL     (Leaf i)) = Leaf i 
prune (Node (Leaf i) (Leaf j)) = Node (Leaf i) (Leaf j)
prune (Node  left     right  ) = prune (Node (prune left) (prune right))
prune t = t

前三行删除了左侧、右侧或两者上的 NIL，第四行仅留下两片叶子。

仅当该节点的左子树或右子树之一本身就是一个节点时，第五行才会被调用。为什么修剪三次？也许当你向左修剪和向右修剪时，其中一个或多个最终会变成NIL。

prune t = t 在一个简洁的模式匹配中处理 NIL 和 Leaf i。