CSP-S 提高级 · CSP 2024 提高级第一轮 第 11 题

假设有一棵 $h$ 层的完全二叉树，该树最多包含多少个结点？

这题考树形结构里的完全二叉树和满二叉树概念。拿到题先想：h 层最多节点就是满二叉树，用等比数列求和公式 2^0+2^1+...+2^{h-1} 直接算，别被层数定义搞晕。

最容易错在层数起始定义上。很多同学看到 h 层就下意识想 2^{h+1}-1，那是根在第 0 层的情况。本题根明确在第 1 层，第 h 层只有 2^{h-1} 个节点，总和是 2^h-1。还有人选 2^h 或 2^{h+1}，是把节点数当成层数或者把满二叉树公式记错成 2^h，完全二叉树最多加一层也不会超过满二叉树的总数。

考察知识点

数据结构 — 树形结构 / 二叉树基础

概念定义

• 完全二叉树：除最后一层外，每一层都被填满；最后一层从左到右连续填充。
• 满二叉树：每一层都被完全填满的二叉树。完全二叉树的一种特例。
• 层数约定：根节点在第 1 层。

命题视角

命题人爱在“层数定义”上挖坑。完全二叉树求节点数，本质就是求满二叉树的节点数，因为“最多”意味着最后一层也填满了。但公式里的指数和层数 h 的关系，取决于根是从第几层开始算的。如果根在第 0 层，h 层满二叉树是 2^{h+1}-1；本题根在第 1 层，指数要减 1，变成 2^h-1。这是历年高频考点，也是区分度所在。

逐步推导

h 层的二叉树最多节点的情况就是满二叉树：

• 第 1 层：2^0 = 1 个节点
• 第 2 层：2^1 = 2 个节点
• 第 3 层：2^2 = 4 个节点
• ...
• 第 h 层：2^{h-1} 个节点

总节点数 = 2^0 + 2^1 + ... + 2^{h-1} = 2^h - 1。

验证：h=1 时，1 个节点，2^1-1=1 ✓；h=3 时，7 个节点，2^3-1=7 ✓。

避坑指南

注意层数的起始定义！如果题目说根在第 0 层，则 h 层满二叉树有 2^{h+1}-1 个节点。本题根在第 1 层，所以选 A。千万不要把 2^h 当成答案，那是层数，不是节点数。

考频与趋势

树形结构在题库共考过 26 题，覆盖 3 个考试级别（2018-2026）；逐年分布：2018 年 1 题、2021 年 2 题、2023 年 6 题、2024 年 3 题、2025 年 3 题、2026 年 8 题、null 年 3 题；分赛事：CSP 提高级 13 题、CSP 入门级 12 题、NOIP 提高组 初赛 1 题。二叉树基础共考过 220 题，覆盖 8 个考试级别（2008-2026）；逐年分布：2008 年 2 题、2009 年 2 题、2010 年 4 题、2011 年 3 题、2012 年 1 题、2013 年 3 题、2014 年 1 题、2015 年 4 题、2016 年 3 题、2019 年 3 题、2020 年 1 题、2021 年 4 题、2022 年 2 题、2023 年 20 题、2024 年 60 题、2025 年 67 题、2026 年 28 题、null 年 12 题；分赛事：GESP 六级 100 题、GESP 七级 56 题、GESP 八级 19 题、NOIP 普及组 初赛 14 题、NOIP 提高组 初赛 9 题、CSP 提高级 8 题、CSP 入门级 8 题、GESP 五级 6 题。

预测

暂无足够依据预测未来可能怎么考。