ocaml - OCaml - 按顺序设置对下一个节点的引用（二叉树）

Question

键入'一棵树= | 空| 'a * 'a tree* 'a tree* 'a tree ref;; 的节点

我们希望将每个节点树的引用按顺序设置为下一个节点；

例如

Node (1, Node(2, Empty, Empty, ref Empty), Node(3, Empty, Empty, ref Empty), ref Empty) )
The result is:

Node (1, Node(2, Empty, Empty, content = {Node (1....) }).....

Answer 1

这并不难：您进行中序遍历，同时传递（并返回）包含在前一个节点中的引用。当您到达给定节点时，您将前一个节点的引用设置为当前节点。如果每个节点都分配给前一个节点的引用，这意味着每个节点的引用都包含下一个节点。

在示例中，中序遍历按以下顺序遍历树：2 1 3

当您在节点 2 时，将其 ref 返回给调用者，即节点 1。当您到达节点 1 时，将节点 2 的 ref 设置为指向节点 1，并将节点 1 的 ref 传递给节点3. 当你在节点 3 时，你将节点 1 的 ref 设置为指向节点 3。

您需要决定对第一个节点（分配一个虚拟引用以启动进程）和最后一个节点（大概将其引用设置为 Empty，尽管有时将其设置为第一个节点可能有用）做什么。

我有工作代码（15 行）。我不会发布它，因为这会破坏假定的分配。