如何在Haskell中找到保存二叉树中最小元素的节点？

Question

“我正在尝试解决类似的问题（在列表树中找到最短的列表），我认为解决这个问题会是一个不错的开始。”

“假设有一个数据类型，如下所示：”

data (Ord a, Eq a) => Tree a = Nil | Node (Tree a) a (Tree a) 

如何在上述二叉树中找到包含最小元素的节点？ 请注意，这不是一棵二叉搜索树。

我试图递归地思考：最小值是左、右子树和当前值之间的最小值。但是，我很难将其转换为Haskell代码。我面临的问题之一是我想返回树而不仅仅是值。

- user35477

---

创建一个 Foldable 实例并使用 min 进行 fold。 - Shanthakumar

Answer 1

注意：在Haskell 2010中，不再支持对数据类型声明的类约束，并且通常不建议使用。因此，请改用以下方法：

data Tree a =   Nil
              | Node (Tree a) a (Tree a)

递归思考：

getMinTree  :: Ord a => Tree a -> Maybe (Tree a)
getMinTree = snd <=< getMinTree'

getMinTree' :: Ord a => Tree a -> Maybe (a, Tree a)
getMinTree' Nil = ???
getMinTree' (Node Nil value Nil) = ???
getMinTree' (Node Nil value right) = ???
getMinTree' (Node left value Nil) = ???
getMin' (Node left value right) = ???

注意：不需要使用Eq约束。由于Eq是Ord的超类，因此Ord约束意味着Eq约束。我认为你甚至不太可能使用==来实现这一点。

- dfeuer

---

很抱歉，我还是有些困惑。实际上，在阅读您的答案之前，我已经得出结论，我需要处理这些基本情况，但我不知道如何编写代码。例如，“getMinTree'（Node Nil value right）”这种情况意味着我们只需将此节点与右侧进行比较；但我不确定如何实现它。 - user35477

@chi 谢谢。我想我已经修复了，但是等我回到电脑前再测试一下。 - dfeuer

@user35477，这个概念是将子树与其最小节点配对。 - dfeuer

s/it's/its/ @dfeuer - JDługosz

@jdlugosz，尽管这个错误很令人尴尬，但现在我无能为力去修复它。 - dfeuer

我以为注释可以被编辑，但是一个字符太小了，除了作者之外没有人能修复它？ - JDługosz

Answer 2

这里有一个提示：

您可以先定义一个辅助函数，用于计算两个树中的最小值。Node将按照其值进行比较，忽略子树，并将Nil与任何树t进行比较，使t成为最小值（在某种意义上，我们认为Nil是“最大”的树）。编写此代码可以通过以下方式完成：

binaryMin :: Ord a => Tree a -> Tree a -> Tree a
binaryMin Nil t = t
binaryMin t Nil = t
binaryMin (Node l1 v1 r1) (Node l2 v2 r2) = ???

然后通过递归利用 binaryMin，找到最小的子树。

treeMin :: Ord a => Tree a -> Tree a
treeMin Nil = Nil
treeMin (Node left value right) = ???
   where l = treeMin left
         r = treeMin right

- chi

Answer 3

你的理解是正确的。我认为当你能证明以下内容时，你应该没问题：

• 最小值树可能是Nil
• 最小值树可能在根节点上有最小值

所以，你需要对子树进行模式匹配来获取根节点的值，而不仅仅是比较值。

你没有提及函数的类型。所以让我们假设它看起来像这样：

findmin :: Tree a -> Tree a

现在，假设您已经有一个函数可以找到树的最小值。类似这样：

findmin Nil = Nil -- no tree - no min
findmin (Node l x r) = case (findmin ..., findmin ...) of
       -- like you said, find min of the left, and find min of the right
       -- there will be a few cases of what the min is like on the left and right
       -- so you can compare them to x
                         some case -> how to find the min in this case
                         some other case -> how to find min in that other case

也许，你需要知道前两个问题的答案。

很难给出一个不泄露实际代码的答案，因为你的思路已经是正确的。

- Sassa NF

---

“probably has the min value at the root”是什么意思？在这种情况下，这听起来不太可能是正确的，因为没有关于树中元素如何排列的信息。 - dfeuer

@dfeuer 我认为这就是 OP 所说的“返回树”的意思。 - John L