0

我创造了一棵树

type 'a tree = {
      mutable cont: 'a;
      mutable left: 'a bin_tree;
      mutable right: 'a bin_tree
}
and 'a bin_tree =
     Empty
     | Node of 'a tree;;

我正在努力处理一些简单的功能，比如

  • 插入元素（到propper子树，没有重复）
  • 合并两棵二叉树

我用谷歌搜索了我的问题，但我经常遇到错误。例如：

let rec insert x tree =
match tree with
 Empty -> Node(x, Empty, Empty)
| Node(y, left, right) ->
   if x <= y then Node(y, insert x left, right)
             else Node(y, left, insert x right)

或者如果我尝试：

let rec insert x = function
Empty -> Node(Empty, x, Empty)
| Node(lb, r, rb) -> if x < r then Node(insert x lb, r, rb)
else Node{lb; r; insert x rb} ;;

我不断收到语法错误。

4

2 回答 2

4

为什么你的树使用可变记录？OCaml 程序员更喜欢使用不可变的数据结构。在这里，树的可变性不会提高复杂性，但会引入错误。

以下是如何以持久的方式实现树：

type 'a tree =
| Empty
| Node of 'a * 'a tree * 'a tree

实际上，您在代码中使用的就是这种类型member和insert。

于 2013-05-12T13:06:08.437 回答
0

您的匹配模式应包含{并}匹配记录，因此代码

match tree with
   Empty -> false
  | Node { cont=x; left=l; right=r } -> (*something here .... *)

实际上，记录符号的语言扩展允许在模式变量与字段具有相同名称时避免字段标签，因此Node { cont=cont; left=left; right=right }您可以编码而不是编写模式Node{cont;left;right}

您还可以查看 Ocaml 的stdlib/set.ml源文件。

请注意，您的'a bin_tree类型几乎等同于'a tree option.

于 2013-05-12T12:25:04.350 回答