arrays - 二叉树的高效数组存储

Question

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

Answer 1

我喜欢的一种方法是存储前序遍历，但也包括其中的“空”节点。存储“空”节点不再需要存储树的顺序。

这种方法的一些优点

• 在大多数实际情况下，您可以比 pre/post + inorder 方法做更好的存储。
• 序列化只需要一次遍历
• 反序列化可以一次性完成。
• 中序遍历可以在不构建树的情况下一次完成，如果情况需要，这可能很有用。

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

因此，如果有 n 个节点，则空间使用量为 8n 字节 + n-1 指示位 + n+1 空节点位 = 66*n 位。

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

所以你比这个 pre/post + inorder 方法节省了 62*n 位的空间。

考虑树

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

'.' 在哪里是空节点。

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

现在每个(包括子树)'带空值的前序遍历'都具有空节点数 = 节点数 + 1 的属性。

这允许您在给定序列化版本的情况下创建树，因为第一个节点是树的根。后面的节点是左子树和右子树，可以这样看:

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

要创建中序遍历，您可以使用堆栈并在看到节点时压入，在看到空值时弹出(到列表中)。结果列表是中序遍历(可以在此处找到对此的详细解释:C++/C/Java: Anagrams - from original string to target;)。