Day 11　二叉树基础：结点、层数与完全二叉树

建议用时：20～25 分钟
今日目标：掌握二叉树的结点关系和常用数量公式，会计算完全二叉树的高度、叶子数和数组编号，并理解二叉搜索树最基本的有序性质。

大纲定位：树与二叉树、二叉树表示与存储、完全二叉树、二叉搜索树；遍历和哈夫曼树放在 Day12。

一、先认清树上的“亲属关系”

树是一种有层次的结构。最上方的结点叫根结点；一个结点向下直接连接的结点是它的孩子，向上直接连接的是它的父结点；同一个父结点的孩子互为兄弟。没有孩子的结点叫叶子结点。

二叉树的“二叉”表示每个结点最多有两个孩子，并不是每个结点都必须有两个孩子。即使一个结点只有一个孩子，也必须分清它是左孩子还是右孩子，左右位置不能随意交换。

结点的度等于它拥有的孩子数：

• 没有孩子：度为 0，也是叶子；
• 只有一个孩子：度为 1；
• 左右孩子都有：度为 2。

二、为什么总有 n₀=n₂₊₁

设一棵非空二叉树中，度为 0、1、2 的结点数分别为 n₀,n₁,n₂，总结点数为

从“父结点有几个孩子”的角度数边：度为 1 的结点贡献 1 条向下的边，度为 2 的结点贡献 2 条，所以边数为

从整棵树的角度看，除根外每个结点都恰有一条连向父亲的边，所以边数又是

令两种数法相等并约去 n₁：

这也解释了为什么度为 1 的结点数不会影响结论。初赛中如果给出 n₀,n₁,n₂，除了套公式，还应先检查数据是否满足这个关系；不满足就不可能构成一棵二叉树。

三、层数、高度和最多结点数

本套材料统一采用：根在第 1 层，树的高度等于最大层数。某些书把根到最深叶子的“边数”叫高度，会比这里少 1；做题一定先看题目定义。

二叉树第 k 层最多有 2^k-1 个结点，因为每个结点最多再生出两个孩子。因此高度为 h 时，总结点数最多为

达到上限时，每一层都放满。反过来，如果给定总结点数 n，完全二叉树的高度 h 满足

例如 n=20，因为 16≤20≤31，所以高度为 5。不要把“第 5 层最多有 16 个”误当成“整棵树有 16 个”。

四、满二叉树与完全二叉树不是一回事

• 满二叉树：每一层都达到最大结点数，高度为 h 时共有 2^h-1 个结点，叶子全部在第 h 层；
• 完全二叉树：除最后一层外全部放满，最后一层从左向右连续排列，中间不能留空；
• 普通二叉树只要求每个结点最多有两个孩子，形状可以很不规则。

满二叉树一定是完全二叉树，完全二叉树不一定满。例如最后一层只有最左边三个结点，仍可以是完全二叉树；如果左边空着却在右边出现结点，就一定不是。

高度为 h 的完全二叉树：前 h-1 层必须放满，第 h 层至少有 1 个结点，所以总结点数范围是

完全二叉树的“不同形态”怎样数

高度恰为 h 的完全二叉树，前 h-1 层已经唯一确定；最后一层可以从左到右放 1～2^h-1 个结点。每一种结点数对应唯一形态，因此共有 2^h-1 种不同形态。

例如高度为 5 时，第 5 层可以放 1～16 个结点，所以共有 16 种形态。这正是 2021 年单选的考法。

公式可以推广到 k 叉树

若每个结点最多有 k 个孩子，第 i 层最多有 k^i-1 个结点，高度为 h 时最多有：

给定总结点数求最小高度时，从较小的 h 开始比较“最多能装多少个”，找到第一个容量不小于总结点数的高度。2023 年单选用 2023 个结点的三叉树考查了这一推广。

五、完全二叉树为什么适合放进数组

把根编号为 1，按层从左到右连续编号。编号为 i 的结点具有固定关系：

• 若 i>1，父结点编号为 ⌊ i/2⌋；
• 左孩子若存在，编号为 2i；
• 右孩子若存在，编号为 2i+1。

“公式算出的编号”不等于“孩子一定存在”，还要检查编号是否超过总结点数 n。例如一棵有 10 个结点的完全二叉树，结点 5 的左孩子编号为 10，确实存在；右孩子编号为 11，超过了 n，所以不存在。

最后一个可能有孩子的结点编号是 ⌊ n/2⌋，因此

都是叶子，叶子数为

如果数组从下标 0 开始存树，公式会变为父结点 ⌊(i-1)/2⌋、左孩子 2i+1、右孩子 2i+2。初赛最爱利用“从 0 还是从 1 开始”设置干扰项。

六、二叉搜索树：左边小，右边大

二叉搜索树（BST）把“比较大小”写进了树的结构。对于结点关键字互不相同的基本情况：

• 左子树中的关键字都小于当前结点；
• 右子树中的关键字都大于当前结点；
• 左、右子树本身也分别是二叉搜索树。

因此对二叉搜索树进行中序遍历，会得到严格递增的关键字序列。例如依次插入 5,3,7,2,4，中序遍历结果为 2,3,4,5,7。这条性质比死记树形更重要。

易错提醒：二叉搜索树不保证每个结点都有两个孩子，也不一定是完全二叉树；插入顺序不同，树形可能不同。

七、一页公式怎样真正用对

遇到数量题，按下面顺序判断：

1. 题目说的是一般二叉树、满二叉树，还是完全二叉树？
2. 高度按层数还是按边数计算？数组编号从 0 还是从 1 开始？
3. 先写适用条件，再代公式；公式得到孩子编号后，还要检查它是否存在。

近五年 CSP-J 中，树的删除与连通、完全二叉树编号、树高、遍历、哈夫曼、叶子数量等几乎年年出现。2022 年考过完全二叉树编号，2023 年考过树高，2025 年又考了完全二叉树叶子数量；这里属于必须拿稳的高频分。

今日练习

第 1～4 题选自 2021～2025 年 CSP-J 第一轮单选题，其中第 2 题仅统一了标点和数学格式；第 5～7 题巩固数量关系，第 8 题补齐大纲中的二叉搜索树。

1. 【CSP-J 2021·第 8 题】 如果只有根结点的二叉树高度为 1，那么高度为 5 的完全二叉树有（　）种不同形态。

   A. 16　 B. 15　 C. 17　 D. 32

2. 【CSP-J 2022·第 8 题】 一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（　）。

   A. 8，18　 B. 10，18　 C. 8，19　 D. 10，19

3. 【CSP-J 2023·第 5 题】 根结点高度为 1，一棵拥有 2023 个结点的三叉树高度至少为（　）。

   A. 6　 B. 7　 C. 8　 D. 9

4. 【CSP-J 2025·第 14 题】 一棵包含 1000 个结点的完全二叉树，其叶子结点数量是（　）。

   A. 499　 B. 512　 C. 500　 D. 501

5. 【巩固题】 一棵二叉树有 20 个度为 2 的结点，则叶子结点有（　）个。

   A. 19
   B. 20
   C. 21
   D. 22

6. 【巩固题】 一棵 5 层满二叉树共有（　）个结点，其中叶子结点有（　）个。

   A. 31，16
   B. 31，15
   C. 32，16
   D. 63，32

7. 【巩固题】 高度为 6 的二叉树最多有（　）个结点。

   A. 31
   B. 32
   C. 63
   D. 64

8. 一棵关键字互不相同的二叉搜索树，其中序遍历序列一定（　）。

   A. 按插入顺序排列
   B. 严格递增
   C. 严格递减
   D. 从根结点开始逐层排列