16.1. 完全二叉树的数组实现¶

从 满二叉树定理 可知， 在典型的二叉树结点实现中，很大一部分空间用于结构性的 空间开销 ，而不是存储数据。 本模块介绍一种简单、紧凑的 完全二叉树 实现。 回想一下，完全二叉树除最底层外所有层都填满， 而最底层的所有结点都从左到右依次填充。 因此，含 \(n\) 个结点的完全二叉树只有一种可能的形状。 你可能会觉得完全二叉树是一种如此罕见的情形， 没有必要为它专门开发一种实现。 然而，完全二叉树有实际用途， 其中最重要的就是 堆 数据结构。 堆常用来实现 优先队列 ，也用于 外部排序算法 。

我们首先为完全二叉树中的结点位置编号， 逐层、从左到右，如图 12.16.1 所示。 数组可以高效地存储树的数据值， 把每个数据值放在与该结点在树中的位置相对应的数组位置上。 表中列出了图 12.16.1 中每个结点的 子结点、父结点和兄弟结点的数组下标。

下面这张表列出了每个结点位置对应的父结点、兄弟结点和子结点的位置。

观察该表，您应该能看到关于节点亲属在数组中位置的规律。可以从 \(R\) 的索引推导出用于计算节点 \(R\) 每个亲属数组索引的简单公式。无需显式指针即可访问节点的左子节点或右子节点。这意味着，如果为具有 \(n\) 个节点的树选择大小为 \(n\) 的数组，则数组实现没有额外开销。

计算结点各个亲属数组下标的公式如下。 树中结点的总数为 \(n\) 。 所讨论结点的下标为 \(r\) ， 它必须落在 0 到 \(n-1\) 的范围内。

• 父结点( \(r\) ) \(= \lfloor(r - 1)/2\rfloor\) （当 \(r \neq 0\) ）。

• 左子结点( \(r\) ) \(= 2r + 1\) （当 \(2r + 1 < n\) ）。

• 右子结点( \(r\) ) \(= 2r + 2\) （当 \(2r + 2 < n\) ）。

• 左兄弟结点( \(r\) ) \(= r - 1\) （当 \(r\) 为偶数且 \(r \neq 0\) ）。

• 右兄弟结点( \(r\) ) \(= r + 1\) （当 \(r\) 为奇数且 \(r + 1 < n\) ）。