1

我试图用从零开始并递增的数字来标记二叉树的叶子。这是我对二叉树的定义

  type btree = I of int | Node of string * btree * btree

我的函数在应用时应该用从最左边的叶子开始的数字标记树叶，用零标记。例如。Node("a", Node("b", I 25, I 54), Node("c", I 12, I 47)) 应该返回树 Node("a", Node("b", I 0 , 我 1), 节点("c", 我 2, 我 3))。我怎样才能做到这一点？我尝试编写代码，但没有给出合适的结果。这是我的代码：

 let mark bst =
  let number x = function
  |Node(a, I b, I c) -> Node(a, I x, I (x + 1))
  |Node(a, b, I c) -> Node(a, (number x b), I(x + 1))
  |Node(a, I b, c) -> Node(a, x, (number (x + 1) c)
  |Node(a, b, c) -> Node(a, (number x b), (number x c))
 in number 0 bst

这段代码编译得很好，但是从一开始就分别对左右子树进行编号，即 0。请帮忙！

4

1 回答 1

3

以下应该工作。它一一处理子树。

let mark bst = 
  let rec number = function
    | (x, I a) -> (x+1, I x)
    | (x, Node(a, b, c)) -> 
    let p1 = number (x,b) in
    let p2 = number ((fst p1),c) in
    ((fst p2),Node(a,(snd p1), (snd p2)))
  in snd (number (0,bst))

这是我在您的示例上运行它时得到的结果。老实说，这是我尝试过的唯一例子。

# let tr =  Node("a", Node("b", I 25, I 54), Node("c", I 12, I 47));;
val tr : btree = Node ("a", Node ("b", I 25, I 54), Node ("c", I 12, I 47))
# markit tr;;
- : btree = Node ("a", Node ("b", I 0, I 1), Node ("c", I 2, I 3))

代码说明： 要按升序从左到右唯一地标记每个叶子，您必须查看每个子树，一次一个。查看左子树后，您需要知道您在标签过程中走了多远，即下一个标签是什么。为了获得这种能力，我的函数number返回一对 type int * btree，而你的返回 a btree。对int中的 是下一个未使用的标签。返回一对，允许我们有两个返回值。聪明的！

我想您理解前两行，因为它们与您的相同（几乎 - 记住let rec在定义递归函数时使用）。在函数mark中，number函数在最后一行启动 - 就像在您的代码中一样。不同之处在于，我没有像您那样给函数两个输入值，而是给它一个；一对值。但最后，我们只需要对中的第二个条目，我们使用snd. 在第 3-4 行，我们检查查看的是整数还是节点（即叶或子树）。请注意，根据您的类型定义，这两种情况是唯一的可能性。如果我们正在查看一个节点，我们需要首先遍历左子树，这发生在第 5 行。在遍历右子树之后，我们仍然需要将下一个未使用的标签向下传递给父节点，这就是为什么我们需要第 6 行。在第 7 行，组装返回对。

哇。那变得相当冗长。但我希望它在某种程度上澄清了一些事情。如果没有，请再问！

于 2013-08-12T13:14:51.817 回答