创建二叉树的实例（Robert Harper 的编程标准 ML）

Question

在 Robert Harper 的在线书籍（编程标准 ML，第 88 页）中，我们对二叉树有以下定义：

datatype 'a tree =
  Leaf
| Node of 'a branch * 'a branch
and 'a branch =
  Branch of 'a * 'a tree;

我想创建以下示例树：

           10
          /  \
         5   11
        / \
       2   6

我正在努力创建根节点。到目前为止我所得到的是：

val two = Branch (2, Leaf);
val six = Branch (6, Leaf);
val eleven = Branch (11, Leaf);
val five = Branch (5, Node (two, six));
val ten = Branch (10, Node (five, eleven));

但是

ten

并不是树的根。我是如何形成这棵树的根的？

Answer 1

你应该从根源开始，逐步深入。

树的每个条目应该是类似于这样的数据结构：

Node {
   value: int
   left_child: Node? = null // default value is null
   right_child: Node? = null // default value is null
}

// a Node with null left child and null right child is a Leaf.

要创建根，您需要执行以下操作：

root = Node(value: 10)

现在创建左左节点：

root.left_child = Node(value: 5)

右边：

root.right_child = Node(value: 11)

依此类推。

构建树的方法有很多，你可以像我刚才展示的那样广度优先，也可以深度优先等，但基本思想是从顶部开始并向下工作。

您的

Node(five, eleven)

符号在概念上会给您带来麻烦，因为您确实需要两个子节点，一个用于左分支，一个用于右分支。

Answer 2

如果我重新构建树，即创建一棵新树，如下所示

           root
           /  \
         10    12
        /  \
       5   11
      / \
     2   6

那么这当然是微不足道的

val two = Branch (2, Leaf);
val six = Branch (6, Leaf);
val eleven = Branch (11, Leaf);
val twelve = Branch(12, Leaf);
val five = Branch (5, Node (two, six));
val ten = Branch (10, Node (five, eleven));
val root = Node (ten, twelve);

从树定义的类型可以看出，每个节点必须有两个分支。