什么是＆QUOT;标志为空指针＆QUOT;在二叉树？ [英] What are "marker for NULL pointers" in binary tree?

问题描述

我要通过这个和这个有关的二叉搜索树的实施。

I was going through this and this post about binary search tree implementation.

我看到一个二叉搜索树重新presented为（例如）的：

I saw that a binary search tree is represented as (for example):

1 5 7 10 40 50

1 5 7 10 40 50

我是想了解序列化和反序列相同这里。该博客文章让我疯了那些 1 ■哪些他们叫标记为空指针。他们正在重新presenting的树：

I was trying to learn about the serialization or de-serialization of the same here. The blog post is making me crazy with those -1s which they're calling markers for NULL pointers. And they're representing the tree as:

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

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

困惑

什么是那些 1 S'

我的最终目标是存储和使用C＃读二叉搜索树的一些类型的文件，但这种混乱是保持了我。

My final goal is to store and read a binary search tree to some kind of file using C# but this confusion is keeping me off.

推荐答案

这些 1 站立的地方，没有更多的孩子的。

These -1 stand for places where there is no more childs.

有关您的例子

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

您可以想象增加额外的 1 （您可以使用不能出现在树本身的任何值）的地方，节点有没有孩子：

You can imagine adding additional -1 (you can use any value that can not occur in the tree itself) to places where nodes have no children:

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

现在，如果你在根，则左子树，再右子树才能通过你的树，你会得到以下字符串：

And now if you go through your tree in "root, then left subtree, then right subtree" order, you will get the following string:

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

这正是你所拥有的。因此，这是一种方式重新present树以阵列形式。与此同时，它很容易从这种形式重建树。知道这些 1 是特殊的意义上，他们没有更多的孩子，你可以重建从这样的一个数组的树没有任何含糊之处。

Which is exactly what you have. So this is a way to represent the tree in an array form. At the same time, it is easy to reconstruct the tree from that form. Knowing that these -1s are special in a sense that they have no more children, you can reconstruct the tree from such an array without any ambiguity.

这篇关于什么是＆QUOT;标志为空指针＆QUOT;在二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！