如何找到下面给出的BST的最小值和最大值？

Question

以下是我当前拥有的代码。不确定它是否正确，但是数据类型行必须保持不变。我正在尝试创建一个getmin和getmax功能。以下是对此的要求。

datatype tree = leaf | node of int * tree * tree;

fun isEmpty leaf = if leaf=nil then true else false;

fun inorder leaf = nil
  | inorder (node(key,left,right)) = inorder left @ [key] @ inorder right;

fun preorder leaf = nil
  | preorder (node(key,left,right)) = preorder left @ preorder right @ [key];

fun postorder leaf = nil
  | postorder (node(key,left,right)) = [key] @ preorder right @ preorder left;

(* Inputs a BST. Returns the smallest value in the tree. If the tree is empty, the function should return NONE. *)
    getMin : tree -> int option

(* Inputs a BST. Returns the largest value in the tree. If the tree is empty, the function should return NONE. *)
    getMax : tree -> int option

对此的任何帮助将不胜感激。谢谢！

Answer 1

fun isLeaf (node(_, _, _)) = false
  | isLeaf leaf = true;

fun getMin(node(x, left, _)) =
    if isLeaf left then x
    else getMin left
  | getMin leaf = raise Empty;

fun getMax(node(x,_,right)) =
    if isLeaf right then x
    else getMax right
  | getMax leaf = raise Empty;

Answer 2

通过这个思考。 树是leaf或node。 A 节点包含一个值和两个其他tree s。

叶的最大值是多少？它没有值，因此是无。

节点的最大值是多少？好吧，这是两个的最大值：

• 它的价值。
• 其左分支的最大值。
• 或者，其右分支的最大值。

您如何找到三个int选项值的最大值？一种方法可能是：

fun max(NONE,   NONE,   NONE)   = NONE
  | max(SOME a, NONE,   NONE)   = SOME a
  | max(NONE,   SOME b, NONE)   = SOME b
  | max(NONE,   NONE,   SOME c) = SOME c
  | max(SOME a, SOME b, NONE)   = if a > b then SOME a else SOME b
  | max(SOME a, NONE,   SOME c) = if a > c then SOME a else SOME c
  | max(NONE,   SOME b, SOME c) = if b > c then SOME b else SOME c
  | max(SOME a, SOME b, SOME c) = 
    if a > b andalso a > c then SOME a
    else if b > a andalso b > c then SOME b
    else SOME c

Answer 3

更加惯用地，使用更精确的模式匹配，并遵循int选项规范，而不是使事物复杂化，而异常：

fun getMin (node (x, leaf, _)) = SOME x
  | getMin (node (_, left, _)) = getMin left
  | getMin leaf = NONE

fun getMax (node (x, _, leaf)) = SOME x
  | getMax (node (_, _, right)) = getMax right
  | getMax leaf = NONE