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

问题描述

我们必须写一个二叉树的节点到一个文件中。什么是一个写二进制树的空间利用率最高的方式。我们可以在阵列格式，其存储与父位置'我'和它的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 childs in 2i,2i+1. But this will waste lot of space in case of sparse binary trees.

推荐答案

这是我喜欢的是存储在preorder穿越，而且还包括了零的节点在那里的一种方法。存放空节点不再需要外还存储树的序。

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 /后+序在大多数实际情况的方法更好的存储。
• 在序列化，只需要一个遍历
• 在反序列化可以在一次通过完成。
• 的序遍历可以在一传没有得到构造树，如果它的形势需要，这可能是有用的。

例如说你有64位整数的二进制树，你可以在每次节点说法是否接下来就是一个空节点或不存储一个额外的位（第一个节点是永远的根目录）。空节点，您可以通过单个位重新present。

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 /后+序，你会最终使用16N字节= 128 * n位。

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

所以，你救了62 * N位的空间，在这个pre /后+序的方法。

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遍历与空'具有这样的性质：空节点数目=节点数量+ 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 . .))

要创建序遍历，您使用堆栈，当你看到一个节点和pop（上表）推当你看到一个空。结果列表是序遍历（这一个详细的解释可以在这里找到：<一href="http://stackoverflow.com/questions/2377286/c-c-java-anagrams-from-original-string-to-target/2377819#2377819">http://stackoverflow.com/questions/2377286/c-c-java-anagrams-from-original-string-to-target/2377819#2377819).

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: http://stackoverflow.com/questions/2377286/c-c-java-anagrams-from-original-string-to-target/2377819#2377819).

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