二叉树的高效数组存储

Question

我们需要将二叉树的节点写入文件。那么以最节省空间的方式，如何将二叉树写入文件呢？我们可以以数组格式存储它，父节点在位置i，其子节点在2i和2i+1中。但是对于稀疏的二叉树来说，这种方式会浪费很多空间。

- Sundararajan S

Answer 1

我喜欢的一种方法是存储先序遍历，但也包括其中的“null”节点。存储“null”节点可以省去存储树中序的需要。

这种方法的一些优点：

• 在大多数实际情况下，您可以比先序/后序+中序方法更好地进行存储。
• 序列化只需要一个遍历
• 反序列化可以一次完成。
• 可以在不构造树的情况下一次性获取中序遍历，如果情况需要，这可能很有用。

例如，假设您有一个64位整数的二叉树，您可以在每个节点后面存储一个额外的位，表示下一个节点是否为null节点（第一个节点始终为根节点）。Null节点可以用单个位表示。

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

在先序/后序+中序中，您最终将使用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 - from original string to target;）。

- Aryabhatta

---

@manyu 这里提到的中序遍历是树的深度优先遍历，可以通过迭代结果数组来找到，跳过任何为null的内容。 - Kevin Shea

问题的重点不是要你将树重建成与之前完全相同吗？我不明白你如何使用你的解决方案来实现这一点。你最后只有中序遍历结果。能否请你解释一下？ - devo

@user529734 最终你将得到中序遍历和前序遍历，这样你就可以重建与之前完全相同的树。在这里有详细解释：http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal。 - Max Shytikov

什么是n-1指示器位？另外，在代码中如何处理64位整数（用于值）和位（用于空指针）？ - pepero

你建议使用哪些数据结构来序列化和反序列化树？ - JavaDeveloper

Answer 2

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

- Ray

---

这也使用了2n的空间，这比preoder/inorder好在哪里呢？ - JavaDeveloper

Answer 3

如果你有一棵（几乎）完整的树，则2i、2i+1（二叉堆）方法确实是最好的方法。

否则，你将不得不为每个节点存储一个ParentId（父索引）。

- H H

Answer 4

你可以将二叉树的中序遍历和前/后序遍历保存在文件中，并从这些遍历中重建树。

- codaddict

---

在这种情况下，我将始终消耗2n的空间（n用于中序遍历，n用于后序遍历）。 - Sundararajan S

Answer 5

您可以存储层序遍历，也称为DFS输出，包括任何空子节点。在从值和null列表重建树时，使用节点队列，并知道列表中的下两个项始终是来自队列的当前节点的左侧和右侧。

这仍然需要存储总共n+1个“null标识符”，但与前序遍历递归地进行反序列化相比，这种方法是迭代完成的。

JS中的POC：

class Node {
  constructor(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function dfs(root) {
  const queue = [root];
  const output = [];

  while (queue.length > 0) {
    const curr = queue.pop();

    // if curr is null, push null, else curr.val
    output.push(curr && curr.val);

    if (curr !== null) {
      queue.unshift(curr.left);
      queue.unshift(curr.right);
    }
  }

  return output;
}

function undfs(list) {
  const root = new Node(list.shift());
  const queue = [root];

  while (queue.length > 0) {
    const curr = queue.shift();
    const [leftVal, rightVal] = list.splice(0,2);

    if (leftVal) {
      curr.left = new Node(leftVal);
      queue.push(curr.left);
    }

    if (rightVal) {
      curr.right = new Node(rightVal);
      queue.push(curr.right);
    }
  }

  return root;
}

const root =
  new Node(100,
    new Node(10),
    new Node(200,
      new Node(150),
      new Node(300)
    )
  );

const dfsOutput = dfs(root);

console.log("List output:");
console.log(dfsOutput.map(a => a || "null").join(", "));

console.log("\nTree output:");
console.log(undfs(dfsOutput));

- max

---

好的建议。有一个小问题：我认为层序遍历是广度优先搜索（BFS）的输出，而不是深度优先搜索（DFS）。 - Ben Jones

Answer 6

由于只有2ⁿ-1个项目可以存储而不浪费空间，因此您必须将N个元素分成子树，按顺序存储，并保持“主索引”在树之间的值以决定在哪棵树中搜索。 一个明显的方法是利用数字的二进制格式来决定子树，这里我说的是N，即树中项目的计数。

假设您有一个排序的20个不同项的序列：

['aeu', 'bfz', 'cdi', 'dfc', 'eap', 'ggk', 'gsb', 'guj', 'idm', 'ieg',
 'izr', 'pba', 'plp', 'rap', 'rhp', 'tat', 'uho', 'uwb', 'wdf', 'yhp']

20₁₀是10100₂，其中1位决定了拆分。

您的主表中的第一个条目将是item[15]，0（15₁₀≡01111₂比N小或等于2的最大幂次少1，0是到目前为止输出列表的长度，也就是子树的起始索引）。前面的15个（0-14）项将被附加到您的输出列表中，再次利用二进制算术：item[7₁₀≡0111₂]在0处，item[3₁₀≡0011₂]在1处，item[11₁₀≡1001₂]在2处，以此类推，从而保留规则item[i] < item[2*i] && item[i] > item[2*i+1]。

完成这一步之后：

master_table = [('tat', 0)]
output_list = ['guj', 'dfc', 'pba', 'bfz', 'ggk', 'ieg', 'rap', 'aeu', 'cdi', 'eap', 'gsb', 'idm', 'izr', 'plp', 'rhp']

如果 N == 2ⁿ，则此 Python 生成器会生成所需的顺序：

def heap_order(pow2):
    """Return the tree order of items
    pow2 MUST be a power of two"""

    bit= pow2>>1
    while bit:
        yield from range(bit - 1, pow2, bit*2)
        bit>>= 1

从列表中删除（或忽略）前16个项目，并重复使用列表长度中的下一个1位：

剩余的输入列表是['uho'，'uwb'，'wdf'，'yhp']，其长度为4₁₀==100₂。最大的2ⁿ-1是3，因此您将基于零的第3项与当前输出列表的长度一起添加到主表中，然后将前3个项目附加到输出列表中，结果如下：

master_table = [('tat', 0), ('yhp', 15)]
# master table items: (key, subtree_base_index)
output_list = [
    'guj', 'dfc', 'pba', 'bfz', 'ggk',
    'ieg', 'rap', 'aeu', 'cdi', 'eap',
    'gsb', 'idm', 'izr', 'plp', 'rhp',

    'uwb', 'uho', 'wdf'
]

整个结果相当于一个二叉树，其中所有左子树都有要么是叶节点要么是具有两个子节点的树节点。

要搜索一个值：扫描主表以找到大于您的搜索键的键，并在相应的子树中搜索您的键，始终使用index-subtree_base_index调整您的2*index、2*index-1计算。失败搜索所需的最大总比较次数（主表+子树）通常为⌈log₂N⌉，有时——当搜索键大于主表的第一个条目时——小于该值（对于N的0位不创建子树）。

您还应在主表中存储每个子树的级别计数（以便知道在多少次搜索后应停止搜索子树）。

- tzot