什么是二叉树中的"NULL指针标记"？

Question

我所经历的这个和这个职位约二叉搜索树的实现.

我看到二进制搜索树表示为(例如):

1 5 7 10 40 50

我试图了解相同的序列化或反序列化在这里.博客文章让我疯狂的那些-1他们正在调用NULL指针的标记.他们将树代表为:

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

混乱

什么是-1秒？

我的最终目标是使用C#存储和读取某种文件的二进制搜索树,但这种混乱让我失望.

Answer 1

这些-1代表了没有更多孩子的地方.

以你为榜样

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

您可以想象添加额外的-1(您可以使用树本身不会发生的任何值)到节点没有子节点的位置:

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

现在如果你通过"root,然后左子树,然后右子树"顺序浏览你的树,你将获得以下字符串:

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

这正是你所拥有的.所以这是一种以数组形式表示树的方法.同时,很容易从该形式重建树.知道这些-1s在某种意义上是特殊的,因为它们没有更多的孩子,你可以从这样的数组中重建树而没有任何歧义.