以下是我目前擁有的代碼。不確定它是否正確，但資料型別行必須保持不變。我正在嘗試創建一個 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
對此的任何幫助將不勝感激。謝謝！
uj5u.com熱心網友回復：
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;
uj5u.com熱心網友回復：
想清楚這一點。Atree是 aleaf或 a node。Anode包含一個值和另外兩個trees。
a 的最大值是leaf多少？它沒有值，所以它是NONE.
a 的最大值是node多少？嗯，這是兩者中的最大值：
- 它的價值。
- 其左分支的最大值。
- 或者，它的右分支的最大值。
你如何找到三個int option值的最大值？一種方法可能是：
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
uj5u.com熱心網友回復：
更慣用的是，使用更精確的模式匹配，并遵循int option規范而不是使例外復雜化：
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/461522.html
上一篇：Terraform資源已更改