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

您知道每个'a Tree中至少有一个元素，因此总有一个最小值/最大值。

在两个构造函数LEAFand 中的每一个上使用模式匹配NODE，并在这种NODE情况下使用递归，因为两个分支可能具有不同的最小值/最大值，并且节点的最小值/最大值由其分支的最小值/最大值决定。并使用内置的辅助函数Int.minand 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分支，但每个节点也有两个'a元素？您是否有兴趣找到这些值中的任何一个的最小值/最大值？或者在某些基于树的字典结构中，一个是键，另一个是值？如果是这样，那么为什么是'a -> 'a而不是'a -> 'b？当您不理解问题陈述时，很难解决问题，而数据类型是其中的很大一部分。

编辑：由于您自己提供了解决方案，让我对此提供一些反馈：

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

该解决方案非常低效，因为它为每个节点的整个子树调用了 3 次。这意味着函数调用的数量大致遵循递推关系 f(0) = 1和f(n) = 3 ⋅ f(n-1)。这相当于3 ^ñ或指数多次呼吁找到列表的最小元素ñ元素。

• 这是一种通过临时存储两次使用的结果来花费线性时间的方法：

  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是一种将结果绑定到词法范围名称的简单方法，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(aka minLeft) 和findMin right(aka minRight)一次。（实际上，我们不止一次提到它们，但Int.min在里面，结果也被绑定到一个临时的、词法范围的名称。）

  所以我们放弃了让终端更短的时间：

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

  在任何情况下，这些都是同样优化的：它们只对树中的n 个元素使用n 个递归函数调用，这是元素未排序时最少可以执行的操作。现在，如果你知道较小的元素总是在左边，你就会有一个二叉搜索树，你可以更快地找到最小值/最大值。:-)

编辑（再次）：只是为了好玩，您可以同时找到最小值/最大值：

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