二叉树的高效阵列存储

Question

我们必须将二叉树的节点写入文件.什么是编写二叉树最节省空间的方法.我们可以将它存储在数组格式中,父级位于i其中,子级位于2i,2i+1.但是在稀疏二叉树的情况下,这将浪费大量空间.

Answer 1

我喜欢的一种方法是存储preorder遍历,但也包括'null'节点.存储'null'节点不需要也存储树的顺序.

这种方法的一些优点

• 在大多数实际情况下,您可以比pre/post + inorder方法做更好的存储.
• 序列化只需要一次遍历
• 反序列化可以一次完成.
• 可以在一次传递中获得inorder遍历而不构造树,如果情况需要它可能是有用的.

例如,假设您有一个64位整数的二叉树,您可以在每个节点之后存储一个额外的位,说明下一个节点是否为空节点(第一个节点始终是根节点).空节点,您可以用一个位表示.

因此,如果有n个节点,则空间使用将是8n字节+ n-1个指示符比特+ n + 1比特用于空节点= 66*n比特.

在pre/post + inorder中,您将最终使用16n个字节= 128*n位.

因此,您可以在此前/后+顺序方法上节省62*n位的空间.

考虑树

       100
      /   \
     /     \
    /       \
   10       200
  / \       /  \
 .   .     150  300
          / \    / \
         .   .   .  .

在哪里'.' 是空节点.

您将序列化为 100 10 . . 200 150 . . 300 . .

现在每个(包括子树)'preorder遍历为null'具有空节点数=节点数+ 1的属性.

这允许您在一次传递中给定序列化版本来创建树,因为第一个节点是树的根.接下来的节点是左子树,后面是右边,可以看作是这样的:

100 (10 . .) (200 (150 . .) (300 . .))

要创建inorder遍历,可以在看到节点时使用堆栈并按下,并在看到null时弹出(在列表中).结果列表是inorder遍历(可以在此处找到详细解释:C++/C/Java:Anagrams - 从原始字符串到目标;).

Answer 2

如果您有一个（几乎）完整的树，2i、2i+1（二叉堆）方法确实是最好的方法。

否则，您将无法避免为每个节点存储 ParentId（父索引）。

Answer 3

考虑一下XML。这是一种树序列化。例如：

<node id="1">
    <node id="2">                                   1
    </node>                                       /   \
    <node id="3">                                2     3
        <node id="4">                                 / \
        </node>                                      4   5
        <node id="5">
        </node>
    </node>
</node>

然后，为什么要使用空格和标签？我们可以逐步删除它们：

<1>
   <2></>
   <3>
     <4></>
     <5></>
   </>
</>

删除空格：<1><2></2><3><4></><5></></></>。

卸下尖括号： 12/34/5///

现在的问题是：如果节点具有一个空的左子树和一个非空的右子树怎么办？然后，我们可以使用另一个特殊字符“＃”表示一个空的左子树。

例如：

    1
  /   \
      2
     /  \
    3

该树可以序列化为：1#23///。