如何在 SML 中找到树的最小值和最大值

Question

我有两种数据类型：

datatype 'a Tree = LEAF of 'a | NODE of ('a Tree) * ('a Tree)

和

datatype 'a myTree = myLEAF of 'a | myNODE of 'a * 'a * 'a myTree * 'a myTree

有了这两个，我需要能够找到树的最小值和最大值。

例如：

findMin (NODE(NODE(LEAF(5),NODE(LEAF(6),LEAF(8))),LEAF(4)))

将产生 4 个。

我已经研究了一段时间了，我很困惑。

任何指导都会有所帮助。谢谢。

Answer 1

你知道每个'一棵树中至少有一个元素，所以总有一个min/max.

在LEAF和NODE两个构造函数中的每一个上使用模式匹配，并在NODE情况下使用递归，因为两个分支可能有不同的min/max节点的值和 min/max 由其分支的 min/max 决定。如果您要查找树的 min/max 整数，请使用内置的辅助函数 Int.min 和 Int.max。（你的例子表明是这种情况。）

fun findMin (LEAF x) = (* ... *)
  | findMin (NODE (leftTree, rightTree)) =
    let (* ... use findMin recursively on each branch ... *)
    in (* ... find the minimal value of the two branches ... *)
    end

我不确定 'a myTree 类型有什么用：它是一棵二叉树，因为它有两个 'a myTree[=每个节点有 87=] 个分支，但每个节点也有两个 'a 元素？您是否有兴趣找到这些值中或的 min/max？或者在某些基于树的字典结构中，一个是键，另一个是值？如果是这样，那为什么是 'a -> 'a 而不是 'a -> 'b？当您不理解问题陈述时，很难解决问题，而数据类型是其中的很大一部分。

编辑：既然你自己提供了解决方案，我来反馈一下：

fun findMin (LEAF(v)) = v | findMin (NODE(left, right)) = if findMin(left) < findMin(right) then findMin(left) else findMin(right)

这个解决方案非常低效，因为它为每个节点的整个子树调用自身三次。这意味着函数调用的次数大致遵循 recurrence relation f(0) = 1 和 f(n) = 3 ⋅ f(n-1) 。这相当于 3ⁿ 或指数多次调用以在 n 列表中查找最小元素元素。

这里有一种方法，通过临时存储你使用两次的结果来占用线性时间：

fun findMin (LEAF v) = v | findMin (NODE (left, right)) = let val minLeft = findMin left val minRight = findMin right in if minLeft < minRight then minLeft else minRight end

没有理由在树的每个节点中多次执行计算 findMin left 和 findMin right 的艰巨任务。由于我们多次引用它，let-in-end 是一种简单的方法 bind 结果到词法范围的名称，minLeft 和 minRight.

表达式if minLeft < minRight then minLeft else minRight其实在标准库中有个名字：Int.min。所以我们可以这样做：

fun findMin (LEAF v) = v | findMin (NODE (left, right)) = let val minLeft = findMin left val minRight = findMin right in Int.min (minLeft, minRight) end

但是使用 let-in-end 的原因实际上已经消失了，因为在库函数的帮助下，我们现在只现在参考 findMin left（又名 minLeft）和 findMin right（又名 minRight）一次。（实际上，我们不止一次引用它们，但那是在 Int.min 中，其中结果也被绑定到一个临时的，词法范围的名称。）

所以我们放弃了 let-in-end 更短的时间：

fun findMin (LEAF v) = v | findMin (NODE (left, right)) = Int.min (findMin left, findMin right)

在任何情况下，这些都是同样最优的：它们只使用 n 递归函数调用树中的 n 元素，这是元素未排序时您可以做的最少的事情。现在，如果您知道较小的元素总是在左边，您就会有一个 binary search tree 并且可以更快地找到 min/max。 :-)

编辑（再次）： 只是为了好玩，您可以同时找到 min/max：

fun findMinMax (LEAF v) = (v, v) | findMinMax (NODE (left, right)) = let val (minLeft, maxLeft) = findMinMax left val (minRight, maxRight) = findMinMax right in (Int.min (minLeft, minRight), Int.max(maxLeft, maxRight)) end

Answer 2

我认为一个问题是您正在认真考虑如何遍历树并按某种顺序检查所有节点并跟踪事物，但递归会为您处理。

你的树有两种情况；它要么是一片叶子，要么是一个有两个子树的节点。
这表明该解决方案还将有两种情况：一种用于叶子，一种用于内部节点。

写下（用你自己的话，而不是代码）你如何找到

中的最小值

一片叶子；和
一个内部节点如果您已经知道它的子树各自的最小值——不要担心如何找到它们，但假装您知道它们是什么。

然后写下你是如何找到一个内部节点的子树的最小值的。
（这是一个递归，所以你在开始思考之前就已经解决了这个问题。）

然后你把它翻译成ML。

Answer 3

我 100% 只是想太多了。谢谢你们的帮助！我得到了答案。

fun findMin (LEAF(v)) = v
  | findMin (NODE(left, right)) =
      if findMin(left) < findMin(right)
      then findMin(left)
      else findMin(right)

fun findMax (LEAF(v)) = v
  | findMax (NODE(left, right)) =
      if findMax(left) > findMax(right)
      then findMax(left)
      else findMax(right)

如何在 SML 中找到树的最小值和最大值

How to find the min and max values of a tree in SML

sml

smlnj