list - 从标准 ML 的列表中将元素插入树中

Question

我刚刚开始自己​​学习 SML，但遇到了教程中的一个问题。假设我有：

树数据类型

datatype node of (tree*int*tree) | null

插入函数

fun insert (newItem, null) = node (null, newItem, null)
|   insert (newItem, node (left, oldItem, right)) =                               
    if (newItem <= oldItem) then node (insert(newItem,left),oldItem, right)
                            else
                                 node (left, oldItem, insert(newItem, right)

一个整数列表

val intList  = [19,23,21,100,2];

我的问题是如何添加编写一个函数来遍历列表中的每个元素并添加到树中？

非常感谢您的回答。

Answer 1

使用 foldl 和 insert 作为折叠函数，并使用空树作为起始值。

对于列表中的每个项目， foldl 将使用该项目和迄今为止创建的树作为参数调用 insert。然后，insert 调用的结果将在下一次 insert 调用中用于列表中的下一个项目，依此类推。

另请注意，问题中树类型和插入函数的定义被破坏：首先，您没有给类型命名（语法是datatype name = Foo | Bar，不是datatype Foo | Bar）。其次，构造函数名称必须以大写字母开头。所以类型定义需要datatype tree = Node of (tree*int*tree) | Null在插入函数中，你必须用“Node”和“Null”替换每次出现的“node”和“null”。