1

我设法完成了这项任务。答案如下。也许有人会需要这个解决方案。

你在 OCaml 中有一个二叉树。每个节点都有一个 int、左孩子、右孩子和对节点的引用。

type tree = Node of tree * int * tree * tree ref | Leaf;;

编写程序left_leaves : tree -> unit 该程序必须在每个节点中设置对其最深左子节点的引用。

         25
      /      \
     5        30
   /  \
  4    10
 /    /
2    6

对于每个节点，此过程必须在此节点中设置引用，如下所示：

25 -> Node(Leaf, 2, Leaf, Leaf)
5 -> Node(Leaf, 2, Leaf, Leaf)
4 -> Node(Leaf, 2, Leaf, Leaf)
2 -> Leaf
10 -> Node(Leaf, 6, Leaf, Leaf)
6 -> Leaf
30 -> Leaf

如何在 Ocaml 中编写此程序？我在考虑递归。我们应该从树的底部开始。首先，我们应该更改对 Leaf 的引用。然后在下一步中，我们应该更改对左节点的引用，然后递归地将节点中的每个引用更改为其左子节点的引用。我为测试目的添加了构建 BST 树的过程：

let rec add x tree =
match tree with
|Node (l, k, r, wsk) -> 
if x <= k then
Node (add x l, k, r, wsk)
else
Node(l, k, add x r, wsk)
|Leaf -> Node (Leaf, x, Leaf, ref Leaf)

let a = Node (Leaf, 25, Leaf, ref Leaf);;

let a = add 5 a;;

let a = add 10 a;;

let a = add 4 a;;

let a = add 2 a;;

let a = add 10 a;;

let a = add 30 a;;

let a = add 26 a;;

这是我的解决方案，但它不起作用。我不知道为什么。

编辑：在这篇文章的编辑期间，我想出了如何去做。我的代码：

let rec left_leaves tree =
match tree with
|Node (l, k, r, wsk) ->
(match l with
|Node (ll, lk, lr, lwsk) ->
left_leaves l; if ll = Leaf then wsk := l else wsk := !lwsk; left_leaves r;
|Leaf -> wsk := Leaf
)
|Leaf -> ();;
4

1 回答 1

1

我的解决方案起来了。在这篇文章的编辑期间，我设法做到了。;D

于 2015-12-26T05:11:28.410 回答