首页/数据结构/04-tree/完全二叉树的性质 🔗 在 Obsidian 中打开
数据结构 · 树与二叉树

完全二叉树的性质

难度 ★★重要度 ★★ 考查频率 低 二叉树完全二叉树
速查
编号从 1 开始：双亲 $\lfloor i/2\rfloor$、左孩子 $2i$、右孩子 $2i+1$、层次 $\lfloor\log_2 i\rfloor+1$。叶子数 $\lceil n/2\rceil$、最后一个非叶 $\lfloor n/2\rfloor$、高度 $\lfloor\log_2 n\rfloor+1$、度为 1 的结点 0 或 1。

核心概念 ▾

完全二叉树的定义

一棵深度为 $k$ 的二叉树，若满足：

  1. 前 $k-1$ 层都是满的；
  2. 第 $k$ 层的结点从左到右连续排列，中间没有空位；

则称为完全二叉树。

完全二叉树示例：          非完全二叉树示例：
       1                      1
      / \                    / \
     2   3                  2   3
    / \ /                  /   / \
   4  5 6                 4   6   7

右边不是完全二叉树：结点 2 缺右孩子（编号 5 空），却在编号 6、7 上又有结点 —— 层序编号不连续。

层序编号规则

按层序从 1 开始逐个编号，先上后下、先左后右：

       1
      / \
     2   3
    / \ / \
   4  5 6  7
本质完全二叉树 = 「按层序编号后，编号 $1\sim n$ 无空缺」。这条等价定义是所有编号公式成立的前提，也是顺序存储与堆能用数组实现的根本原因。

八条关键性质 ▾

#性质公式 / 结论成立条件
1结点 $i$ 的双亲$\lfloor i/2 \rfloor$$i>1$
2结点 $i$ 的左孩子$2i$$2i \le n$
3结点 $i$ 的右孩子$2i+1$$2i+1 \le n$
4结点 $i$ 的层次$\lfloor \log_2 i \rfloor + 1$—
5叶子结点数$\lceil n/2 \rceil$—
6最后一个非叶结点$\lfloor n/2 \rfloor$—
7树的高度$\lfloor \log_2 n \rfloor + 1$—
8度为 1 的结点数0 或 1$n$ 奇 → 0；$n$ 偶 → 1
性质 5、6 互补$\lfloor n/2\rfloor$ 个非叶 + $\lceil n/2\rceil$ 个叶子 $= n$，无论 $n$ 奇偶都成立。所以记住一个就能推出另一个。
性质 8 的直观理解度为 1 的结点只可能出现在「最后一个非叶结点」上，且只能是「只有左孩子」。$n$ 为偶数时最后一个结点是某个双亲的左孩子（右孩子缺失）→ 恰 1 个；$n$ 为奇数时所有非叶都是满的 → 0 个。

手算示例 ▾

示例一：求各种结点数（$n=2024$）

所求公式结果
叶子结点数$\lceil 2024/2 \rceil$1012
度为 1 的结点数$n$ 为偶数1
树的高度$\lfloor \log_2 2024 \rfloor + 1 = \lfloor 10.98 \rfloor + 1$11
最后一个非叶结点编号$\lfloor 2024/2 \rfloor$1012

校验：$n_0=1012$、$n_1=1$，则 $n_2=n_0-1=1011$，合计 $1012+1+1011=2024$ ✓

示例二：求双亲与孩子（$n=15$，问结点 8）

  • 双亲：$\lfloor 8/2 \rfloor = \textbf{4}$
  • 左孩子：$2\times 8 = 16 > 15$ → 无左孩子
  • 右孩子：$2\times 8+1 = 17 > 15$ → 无右孩子
  • 结论：结点 8 是叶子（$2i>n$）

示例三：层次编号应用（$n=20$）

  1. 第 4 层有多少个结点？第 4 层编号范围 $2^3=8$ 到 $2^4-1=15$；因 $15 \le 20$，该层已满，共 8 个。
  2. 结点 10 在第几层？$\lfloor \log_2 10 \rfloor + 1 = \lfloor 3.32 \rfloor + 1 = \textbf{第 4 层}$。

顺带：第 5 层编号从 16 到 20，共 5 个；总高度 $\lfloor\log_2 20\rfloor+1 = 4+1 = 5$ ✓

示例四：从编号判断结点类型（$n=30$，问结点 15）

  • 左孩子：$2\times 15 = 30 \le 30$ → 有左孩子（30 号）
  • 右孩子：$2\times 15+1 = 31 > 30$ → 无右孩子
  • 结论：结点 15 不是叶子，它是那个唯一的度为 1 的结点（$n=30$ 为偶数 ✓）

常见考法 ▾

题型一 · 计算各种结点数给定 $n$，求叶子数 $\lceil n/2\rceil$、度为 1 结点数（看奇偶）、高度 $\lfloor\log_2 n\rfloor+1$。
题型二 · 求双亲 / 孩子给定编号 $i$，代入 $\lfloor i/2\rfloor$、$2i$、$2i+1$，并检查是否 $\le n$。
题型三 · 判断结点类型判断叶子：$2i > n$。（用 $2i+1>n$ 会误判「只有左孩子」的结点为叶子。）
题型四 · 与满二叉树对比满二叉树是完全二叉树的特例（每层都满，$n=2^k-1$，此时 $n$ 必为奇数，$n_1=0$）。

易错点 ▾

必记
  1. 编号从 1 开始：不是 0，所有公式依赖这一点。
  2. 叶子数是 $\lceil n/2\rceil$（向上取整），不要记成 $\lfloor n/2\rfloor$。
  3. 高度是 $\lfloor\log_2 n\rfloor+1$，别漏 $+1$。
  4. 度为 1 的结点最多 1 个 —— 这是完全二叉树独有的性质，普通二叉树没有。
  5. 判断叶子用 $2i>n$，不是 $2i+1>n$。

核心结论 ▾

完全二叉树的核心编号性质（$n$ 个结点，编号从 1 开始）：

公式含义
$\lfloor i/2 \rfloor$双亲编号
$2i$左孩子编号
$2i+1$右孩子编号
$\lfloor n/2 \rfloor$最后一个非叶结点
$\lceil n/2 \rceil$叶子结点数
$\lfloor \log_2 n \rfloor + 1$树的高度

记忆卡片 ▾

结点 i 的左孩子编号？
$2i$（前提 $2i \le n$，否则无左孩子）。
n 个结点的完全二叉树叶子数？
$\lceil n/2 \rceil$（向上取整）。
度为 1 的结点最多几个？
最多 1 个：$n$ 奇为 0，$n$ 偶为 1。
如何判断结点 i 是叶子？
看 $2i > n$ 是否成立。
n 个结点的完全二叉树高度？
$\lfloor \log_2 n \rfloor + 1$。
最后一个非叶结点编号？
$\lfloor n/2 \rfloor$（堆的建堆循环就从这里往前扫）。

交互动画 · 编号公式验证器（n = 12） ▾

1 2 3 4 5 6 7 8 9 10 11 12
点击任意结点：橙色 = 该结点，绿色 = 它的孩子，米色 = 它的双亲
自测点结点 6：$2\times6=12 \le 12$ 有左孩子，$2\times6+1=13>12$ 无右孩子 —— 它就是那个唯一度为 1 的结点（因为 $n=12$ 为偶数）。再点「标出所有叶子」，数一数是不是 $\lceil 12/2\rceil = 6$ 个。

相关知识点

（暂无关联知识点）

↑ 源笔记 front-matter 中 related 为空；本页右上「在 Obsidian 中打开」可跳回源笔记。