从树和树本身检索最小值 - haskell

Question

有了这个函数，我可以删除二叉搜索树中的最小值：

data BTree a = Empty
             | Node a (BTree a) (BTree a)

semmin :: BTree a -> BTree a
semmin (Node x Empty Empty) = Empty
semmin (Node x l r) = Node x (semmin l) r

我想检索最小值和没有这个最小值的树，技巧是，我只能遍历一次。

The type is mimSmim :: BTree a -> (a,BTree a)

我应该怎么做？

编辑：这算作一次遍历吗？

semmin :: BTree a -> (a,BTree a)
semmin (Node x Empty Empty) = (x,Empty)
semmin (Node x l r) = let i= (semmin l)
                       in (fst(i),(Node x (snd(i)) r))

Answer 1

提示：如果您在 Node x l r 并且您已经知道左边树的 mimSmim l 是 (a, l')，那么 Node 的 mimSmim (Node x l r) 将是 (a, Node x l' r).

Answer 2

您正在寻找 zipper。 [zipper][1] 是另一种数据结构的表示，它使您可以关注整个结构的一个部分而不会丢失其余部分。请参阅 Learn You A Haskell 的最后一章，了解开发 zipper 数据类型和在其上使用的函数的直观方法。

Answer 3

发布的代码在正确的轨道上，即使不完全正确：

semmin :: BTree a -> (a,BTree a)
semmin (Node x Empty Empty) = (x,Empty)
semmin (Node x l r) = let i= (semmin l)
                       in (fst(i),(Node x (snd(i)) r))

作为改进代码的提示，不是以下崩溃：

semmin (Node 1 Empty (Node 2 Empty Empty))

此外，为了提高可读性，我建议：

semmin :: BTree a -> (a,BTree a)
semmin (Node x Empty Empty) = (x,Empty)
semmin (Node x l r) = let (minValue, minTree) = semmin l
                       in (minValue, Node x minTree r)

最后，这看起来像是在返回整棵树，而不是找到最小值的那棵树。检查是否是这种情况，是否是您想要的。

从树和树本身检索最小值 - haskell

Retrieve minimum from tree and the tree itself - haskell

haskell