二叉树的高效阵列存储

我喜欢的一种方法是存储预遍历遍历，但还可以在其中包含“空”节点。存储“空”节点消除了对也存储树的顺序的需求。

这种方法的一些优点

• 在大多数实际情况下，与前/后+顺序方法相比，您可以做得更好。
• 序列化只需要一个遍历
• 反序列化可以一次完成。
• 可以遍历顺序遍历而无需构造树，如果情况需要，则可能很有用。

例如，假设您有一个由64位整数组成的二进制树，则可以在每个节点之后存储一个额外的位，以表明下一个节点是否为空节点（第一个节点始终是根节点）。空节点，可以用一个位表示。

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

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

因此，您可以在此pre / post +顺序方法中节省62 * n位的空间。

考虑树

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

哪里是“。” 是空节点。

您将序列化为

100 10 . . 200 150 . . 300 . .

现在，每个（包括子树）“空前序遍历”具有以下属性：空节点数=节点数+ 1。

由于第一个节点是树的根，因此您可以一次性创建序列化版本的树。后面的节点是左边的子树，后面是右边的子树，可以这样看：

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

要创建有序遍历，请使用堆栈并在看到节点时推送，并在看到null时d出（跳至列表）。