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

问题描述

我们必须将二叉树的节点写入文件。编写二叉树最有效的方式是什么？我们可以将它存储在数组格式中，父母位于 i ，其子节点位于 2i ， 2i + 1 。但是这样做会浪费大量的空间，因为二叉树是稀疏的。

解决方案

我喜欢的一种方法是存储预订遍历，而且还包括'null'节点。存储空节点消除了也存储树的顺序的需要。

此方法的一些优点

• 在大多数实际情况下，您可以比pre / post + inorder方法更好的存储。


• 序列化只需要一次遍历


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


• 可以在一次通过中获得无序遍历，而不构造树，如果情况需要，可能会有用。例如，你有一个64位整数的二叉树，每个节点之后可以存储一个额外的位，说明下一个是否是一个空节点（第一个节点始终是根）。空节点，您可以通过一个位来表示。
  
  
  

  所以如果有n个节点，空间使用将是8n个字节+ n-1个指示符位+ n + 1空节点的位= 66 * n位。

  
  
  

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

  
  
  

  因此，您可以在此前/后+无序方法中保存62 * n位的空间。

  
  
  

  树

    100 
   / \ 
   / \ 
   / \ 
   10 200 
   / \ / \ 
  。 。 150 300 
   / \ / \ 
  。 。 。 。 
    

  其中'。'是空节点。

  
  
  

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

  
  
  

  现在每个（包括子树）'预订遍历为空'具有空节点数=节点数+1的属性。

  
  
  

  这允许您在一次通过时给出序列化版本，因为第一个节点是树的根。下面的节点是右子树，右边的子树可以被看作是这样的：

    100（10。 （200（150。）（300。））
    

  要创建无序遍历，请使用当您看到一个空值时，当您看到一个节点并弹出（在列表中）时，会发生堆栈和推送。得到的列表是顺序遍历（详细的解释可以在这里找到： C ++ / C / Java：Anagrams - 从原始字符串到目标; ）。

  
  

  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.

  Some advantages of this method

  • You can do better storage than pre/post + inorder method in most practical cases.
  • Serialization just takes one traversal
  • Deserialization can be done in one pass.
  • The inorder traversal can be gotten in one pass without constructing the tree, which might be useful if the situation calls for it.

  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.

  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.

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

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

  Consider the tree

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

  where the '.' are the null nodes.

  You will serialize it as 100 10 . . 200 150 . . 300 . .

  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 . .))
  

  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屋！