SML 中的二叉搜索树

Question

我正在尝试在 SML 中实现二叉搜索树。我有一个插入函数，我正在尝试实现另一个函数，它接受一个列表并在列表中的每个元素上调用插入函数。这是我目前所拥有的，

fun insertB (l) = insert (hd(l),  Node(insertB(tl (l)), Nil, Nil))

但我没有基本案例，所以这是一个问题。我的输入函数将一个 int 和一个 Node 作为参数。我目前得到的错误是 error right-hand-side of clause doesn't agree with function result type [tycon mismatch]

Answer 1

您的 insertB 函数的基本情况是空列表 []。什么二叉搜索树对应于那个？当然，一个空的，在你的例子中似乎被命名为 Nil:

fun insertB [] = Nil

这是递归的基本情况。您现在需要递归案例，这与您所做的非常相似，只是您不尝试构建 BST，而是让递归调用构建它：

  | insertB (head :: tail) = insert (head, insertB tail)

整个函数是这样的：

fun insertB []             = Nil
  | insertB (head :: tail) = insert (head, insertB tail)

或者，您可以使用 foldl:

fun insertB xs = foldl insert Nil xs

Binary Search Tree in SML