从给定数据构建二叉树

Question

我无法理解如何根据给定的一组数字构建 binary tree...

30
15
4
NULL
NULL
20
18
NULL
19
NULL
NULL
NULL
35
32
NULL
NULL
38
NULL
NULL

我翻阅了我的书和笔记，但似乎无法弄清楚。 NULL 是什么意思？如果你能给我看一棵正确建造的树，那将是最有帮助的，我是一个非常有视觉的人。我已经更改了作业中的值和 NULL 顺序，所以不要担心我不会从中学习！

Answer 1

如果你只考虑数字，这里的二叉树应该是这样的：

                +--+
                |30|
          +------------------+
          |                  |
       +--+                 ++-+
       |15|                 |35|
  +------------+         +----------+
  |            |       +--+       +--+
+-+          +-++      |32|       |38|
|4|          |20|      +--+       +--+
+-+          +--+
       +-----+
       |18|
       +---+
           |
           +----+
             |19|
             +--+

现在，如果您再次查看列表，您会看到 NULL 表示何时停止。 30有一个child，15，15有一个child，4，4没有一个child（后面跟着两个NULLs），往上一个，15有第二个child，20，20有一个children： 18。 18没有左children（后面用NULL表示），但有右children19。它没有任何 children（两个 NULLs）。 20也没有了children:NULL导致15的其他child:35等

Answer 2

我假设第一个节点表示树的根节点。

列表中的以下两个节点是直接叶子。

我假设 NULL 值表示列表中的前一个节点只有一个叶节点或没有叶节点。

关于树结构中的节点顺序，如果是二叉搜索树，每对叶子节点应该大于或小于父节点，通常较小的值应该在左边叶节点。这意味着您可以通过从根开始并选择较高或较低的叶节点，向下遍历树直到找到所需的节点来搜索树。

Answer 3

您的问题很可能与 Łukasiewicz 代码有关。

给定一棵二叉树，Łukasiewicz 代码是由完整的前序遍历生成的序列，其中内部节点标记为 a，外部节点（NULL 指针）标记为 b. 'a/b` 的使用是约定俗成的。您可以使用任何其他符号；例如，位。

比如这棵树

这应该是与您的问题相对应的树，具有如下序列的 Łukasiewicz 代码：

aaabbaababbbaabbabb

考虑绘制同一棵树，但使用外部节点。一些如

在这个图中，每个外部节点都用水平条绘制。每个外部节点都是一个 NULL 指针。

现在执行前序遍历。当您找到外部节点（即 NULL 指针）时，您打印 NULL 和 eol。当您找到一个内部节点（与 NULL 不同）时，您打印键值加上 eol.

您将获得您所提供的序列。

因此，任务是根据这种 Łukasiewicz 遍历重建原始树。这样的任务可以通过这样的例程来完成：

Node * to_tree(istream & input)
{
  string val;
  input >> val;
  if (val == "NULL")
    return nullptr;

  Node * p = new Node;
  p->get_key() = atoi(val.c_str());
  p->left  = to_tree(input);
  p->right = to_tree(input);

  return p;
}

如果序列生成正确，那么你可以安全地调用这个函数，没有任何风险；它会完成。如果您有兴趣验证输入，则可以进行预处理。您将计数器初始化为零。每次找到一个键时加 1，找到 NULL 时减 1。正确的序列必须在末尾产生 -1。这是因为 n 个节点的所有二叉树都有 n + 1 个外部节点（或 NULL 个指针）。最后访问的节点是外部节点，这是计数器达到-1 的唯一也是最后一次。

您可以根据您的树实现调整他的例程并编写程序：

int main(int, char **)
{
  Node * root = to_tree(cin);
  return 0;
}

编译然后执行：

./my-program < my-input

瞧瞧！

从给定数据构建二叉树

Building a Binary Tree from Given Data

tree

binary-tree

integer

binary-search-tree