二叉树的高效阵列存储

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

回答(4)

3 years ago

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

这种方法的一些优点

  • 在大多数实际情况下,您可以比前/后顺序方法做更好的存储 .

  • 序列化只需要一次遍历

  • 反序列化可以一次完成 .

  • inorder遍历可以在一次传递中获得,而不构造树,如果情况需要它可能是有用的 .

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

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

在前/后顺序中,您将最终使用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 - from original string to target;) .

3 years ago

想想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/// .

3 years ago

如果你有一个(几乎)完整的树,2i,2i 1(二进制堆)方法确实是最好的方法 .

否则,您将无法转义为每个节点存储ParentId(父索引) .

3 years ago

您可以在文件中保存二叉树的 in-orderpre/post-order 遍历,并从这些遍历中重建树 .