二叉树中的 "marker for NULL pointers" 是什么？

Question

我正在执行 this and this post about binary search tree 实施。

我看到二叉搜索树表示为（例如）:

1 5 7 10 40 50

我试图了解相同 here 的序列化或反序列化。博客 post 让我对那些 -1 感到疯狂，他们称之为 空指针标记 。他们将树表示为：

20 8 4 -1 -1 12 10 -1 -1 14 -1 -1 -1

迷茫

那些 -1 是什么？

我的最终目标是使用 C# 将二叉搜索树存储和读取到某种文件，但这种混乱让我望而却步。

Answer 1

并非所有节点都有两个子节点。显然，因为否则树将是无限的。在 runtime/in 内存中，丢失的节点由 nullptr 表示，在磁盘上由 -1 表示。

Answer 2

这些-1代表没有孩子的地方。

以你为例

您可以想象在节点没有 children:

的地方添加额外的 -1（您可以使用树本身不会出现的任何值）

       20
      /   \
     8__   -1
    /   \
  4      12
 /\      /\
-1 -1   10  14
        /\   /\
      -1 -1 -1 -1

现在，如果您按 "root, then left subtree, then right subtree" 顺序遍历树，您将得到以下字符串：

20 8 4 -1 -1 12 10 -1 -1 14 -1 -1 -1

这正是您所拥有的。所以这是一种用数组形式表示树的方法。同时，很容易从该形式重建树。知道这些 -1 在某种意义上是特殊的，它们不再有 children，您可以从这样的数组中重建树，而不会产生任何歧义。

Answer 3

这些-1的含义在其他答案中都有解释，我来展示一下读写树的代码：

class Tree
{
public:
  int value;
  Tree* left;
  Tree* right;

  Tree(int i_value, Tree* i_left, Tree* i_right)
    : value(i_value), left(i_left), right(i_right)
  {}
  Tree(const Tree&) = delete;

  static const int NO_TREE = -1;

  template<typename Iterator>
  static Tree* Create(Iterator& i_iterator)
  {
    if (*i_iterator == NO_TREE)
    {
      i_iterator++;
      return nullptr;
    }
    int value = *(i_iterator++);
    Tree* left = Create(i_iterator);
    Tree* right = Create(i_iterator);
    return new Tree(value, left, right);
  }

  template<typename Iterator>
  static void Write(Tree* i_tree, Iterator& i_iterator)
  {
    if (i_tree == nullptr)
    {
      *(i_iterator++) = NO_TREE;
      return;
    }
    *(i_iterator++) = i_tree->value;
    Write(i_tree->left, i_iterator);
    Write(i_tree->right, i_iterator);
  }
};

用法：

vector<int> v = { 20, 8, 4, -1, -1, 12, 10, -1, -1, 14, -1, -1, -1 };
Tree* t = Tree::Create(v.begin());
vector<int> w;
Tree::Write(t, std::back_inserter(w));

二叉树中的 "marker for NULL pointers" 是什么？

What are "marker for NULL pointers" in binary tree?

c#

algorithm

implementation

nodes

binary-search-tree