二叉树的高效数组存储 [英] Efficient Array Storage for Binary Tree

问题描述

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

We have to write the nodes of a binary tree to a file. What is the most space efficient way of writing a binary tree . We can store it in array format with parent in position i and its children in 2i, 2i+1. But this will waste lot of space in case of sparse binary trees.

推荐答案

我喜欢的一种方法是存储前序遍历，但也包括空"节点.存储空"节点不需要同时存储树的中序.

One method which I like is to store the preorder traversal, but also include the 'null' nodes in there. Storing the 'null' nodes removes the need for also storing the inorder of the tree.

这种方法的一些优点

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

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

For example say you had a binary tree of 64 bit integers, you can store an extra bit after each node saying whether the next is a null node or not (the first node is always the root). Null nodes, you can represent by a single bit.

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

So if there are n nodes, the space usage would be 8n bytes + n-1 indicator bits + n+1 bits for null nodes = 66*n bits.

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

In the pre/post + inorder you will end up using 16n bytes= 128*n bits.

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

So you save a space of 62*n bits over this pre/post + inorder method.

考虑树

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

'.' 所在的位置是空节点.

where the '.' are the null nodes.

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

现在每个(包括子树)'preorder traversal with null'都具有空节点数=节点数+1的性质.

Now each (including subtrees) 'preorder traversal with null' has the property that number of null nodes = number of nodes + 1.

这允许您创建树，给定一次传递的序列化版本，因为第一个节点是树的根.后面的节点是左子树后跟右子树，可以这样看:

This allows you to create the tree, given the serialized version in one pass, as the first node is the root of the tree. Nodes that follow are the left subtree followed by right, which can be viewed to be like this:

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

要创建中序遍历，您使用堆栈并在看到节点时推送并在看到空值时弹出(到列表中).结果列表是中序遍历(对此的详细解释可以在这里找到:C++/C/Java:字谜 - 从原始字符串到目标；).

To create the inorder traversal, you use a stack and push when you see a node and pop (onto a list) when you see a null. The resulting list is the inorder traversal (a detailed explanation for this can be found here: C++/C/Java: Anagrams - from original string to target;).

这篇关于二叉树的高效数组存储的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！