满二叉树的数据结构

Question

我收到了这个问题，但我似乎无法理解如何回答和解释它：

使用数组表示的完整二叉树与其可接受的表示形式相比，最多可能需要一个常量（可能非常大）的乘积差。对还是错？解释一下。

Answer 1

我会解释我对这个问题的理解。假设我们有一棵树 T，大小为 n（其中 n = 2ˣ - 1 对于一些 x > 0，因为它是一棵完整的树），在数组中表示 T 所需的 space 应该正好是 n.

假设T是下面的树：

数组表示为 [1, 2, 3, 4, 5, 6, 7]，正好占用 n 个槽（在本例中为 7 个）。

如果您要以二叉树的正常格式表示 T，每个节点应该是一个包含数据和 2 个子节点引用的结构：

         ______________
        |   data (1)   |
        |--------------|
        | left | right |
         ‾/‾‾‾‾‾‾‾‾‾‾\‾
 ________/_____      _\____________
|   data (2)   |    |   data (3)   |
|--------------|    |--------------|
| left | right |    | left | right |
 ‾/‾‾‾‾‾‾‾‾‾‾\‾      ‾/‾‾‾‾‾‾‾‾‾‾\‾
...          ...    ...          ...

理论上这应该占用 3n 个槽（因为每个 n 节点都有 3 个槽）。

简而言之，两者都是 O(n)，但第一个占用 n 个插槽，第二个占用 3n.

满二叉树的数据结构

Data structure for a full binary tree

arrays

algorithm

computer-science

binary-tree

data-structures