时间戳

首页 > 解决方案 > 序列化完全二叉树的大小

serialization - 序列化完全二叉树的大小

问题描述

我正在尝试计算具有节点的序列化二叉树的大小（在LeetcodeN中也提到过）。这就是我计算大小的方式：

如果我们假设存储值所需的存储空间是V每个节点的位，那么存储N节点所需的存储空间将是N.V. 我们还需要储存NULL叶子；因为在一棵完整的树中确实有Ceiling(N/2)叶子，并且假设只有一个位足以表示NULL，那么将需要额外的2 x Ceiling(N/2)位。2 x Ceiling(N/2)转换N+1为在完整的树N中总是一个奇数。

因此，N.V + (N+1)总共需要位。

但是，我可以看到在 Leetcode 和其他一些地方（例如this），它的计算方式是N.V + 2N.

我错过了什么？

标签： serializationdata-structuresbinary-tree

解决方案

我错过了什么？

您提供的两个参考资料（LeetCode 和博客文章）处理任意二叉树，不一定是完整的 . 所以让我首先处理任意二叉树：

尽管 NULL 引用可以用一位表示（例如，值为 0），但您还需要存储引用不是NULL（值 1）这一事实。您不能只省略该位，因为下一位（属于节点值）可能会被误解为指示 NULL 引用。因此，您不仅应该为每个 NULL 引用计算该位，还应该为所有分支计算该位。

每个节点的序列化格式将表示：

  • 节点的值（位）
  • 其左孩子是否为 NULL（1 位）的事实
  • 其右孩子是否为 NULL（1 位）的事实

例子：

让 4

要序列化的树：

            10
           /  \
          7    13
                \
                 14

序列化过程（级别顺序）：

节点值 已经离开了 有权利 连载的 无间距
10 是的 是的 1010 1 1 101011
7 不 不 0111 0 0 011100
13 不 是的 1101 0 1 110101
14 不 不 1110 0 0 111000

完全的：

101011011100110101111000

如果我们只在有 NULL 时存储 0，那么我们会得到：

101001110011010111000
    ^

但是现在指示位置的位是不明确的，因为该位可以解释为表示 NULL 引用，但实际上它是表示值 7 的位 0111 中的第一个。

然而，可以用 2 位减少序列化字符串：在保证以叶子结尾的树遍历中，最后 2 位将始终为 0。例如，级别顺序和预顺序遍历就是这种情况。因此，您可以省略这 2 位。

完全二叉树的情况

首先是关于完全二叉树的定义。你写：

在一棵完整的树中，N总是一个奇数。

我想您对完整树的定义在 Wikipedia 上被称为完美树。然而，我们也可以查看（几乎）完整的二叉树（然后不一定是奇数）。

对于完全二叉树，情况更简单，因为完全二叉树的级别顺序遍历永远不会包含 NULL，即在这样的遍历中没有“间隙”。

因此，您可以按该顺序序列化节点的值，给出每个位。这实际上是用于二进制堆的数组表示：

父/子关系由数组中元素的索引隐式定义。

如果序列化发生在隐式具有长度属性的字符串数据类型中，那么就是这样。如果没有这样的元数据，那么您需要在序列化中为值添加前缀，为其保留预定义的位数。或者，如果存在永远不会作为实际节点值出现的特殊位值，则可以将其附加为终止符（很像\0在 C 字符串中）。

推荐阅读