考研408真题2011年第4题·数据结构768个结点的完全二叉树叶子结点有几个这次我们直接看一道考研408经典真题。题目本身不长但涉及的知识点非常基础也非常容易踩坑完全二叉树的结点度数关系、叶子结点计算、以及 n0 n2 1 这个核心公式的使用边界。很多同学第一次做这道题时会直接套n0 n2 1然后发现题目只给了总结点数 768没有给任何度数信息根本算不下去。原因在于完全二叉树有一个隐藏性质——度为 1 的结点数要么是 0要么是 1。这个性质才是解题的关键。本文会完成这几件事先梳理完全二叉树和满二叉树的基本性质。推导出通用公式叶子结点数 n0 (n 1) / 2或n0 n / 2取决于结点总数 n 是奇数还是偶数。严格按“度数之和 边数”的方法解出 768 个结点的叶子结点个数。给出 Python 代码验证用层序遍历构造完全二叉树再统计叶子结点。扩展讨论考试中常见的变体例如“已知叶子结点求总结点数”的题目以及堆排序、优先队列等场景中为什么也用同样的完全二叉树性质。考研数据结构的读者、正在刷408真题的计算机考研党、以及想加深二叉树基础的程序员都可以直接收藏这篇文章。1. 核心知识速览知识点结论题目原文2011年计算机学科专业基础综合考试408第4题数据结构考点完全二叉树的结点度数关系、叶子结点计算关键公式叶子结点数 n0 度为2的结点数 n2 1完全二叉树核心性质度为1的结点数 n1 只能是 0 或 1结论768 个结点的完全二叉树叶子结点数为 384解法思路总结点数 n n0 n1 n2结合 n0 n2 1再根据 n1 的取值分类讨论代码验证Python 层序遍历构造完全二叉树统计叶子结点数量这道题的答案并不复杂但它的推导过程几乎覆盖了二叉树章节最核心的公式关系。408统考反复考察这个知识点比如给叶子结点数反推总结点数、给完全二叉树层数推叶子范围本质上都是同一套逻辑。2. 题目原文与考查目标2.1 题目描述已知一棵有 768 个结点的完全二叉树求其叶子结点的个数。这是 2011 年统考真题第 4 题题型为单项选择题但很多参考书把它改编成了填空题或者简答题。不管题目形式怎么变核心是同一个在只给总结点数的条件下利用完全二叉树的性质确定叶子结点数。2.2 考查目标408 数据结构部分对二叉树的考查重点有三个二叉树的基本遍历方式。二叉树的各种性质推导包括结点度数关系、高度关系、叶子结点与总结点数关系。完全二叉树、满二叉树、二叉排序树、平衡二叉树等特殊二叉树的判定与性质。本题属于“性质推导 特殊二叉树性质”的结合。它不像遍历题那样需要画图也不像构造题那样要写递归而是用数学关系直接算。难度不大但很能区分基础是否扎实。3. 核心概念完全二叉树与满二叉树3.1 满二叉树每一层的结点数都达到最大值。也就是说如果高度为 h那么第 i 层有 2^(i-1) 个结点总结点数是 2^h - 1。满二叉树中不存在度为 1 的结点。所有叶子结点都在同一层。n0 n2 1 成立。3.2 完全二叉树完全二叉树的定义是除最后一层外每一层都是满的并且最后一层的所有结点都集中在左侧连续排列。注意区分完全二叉树不要求最后一层一定满。完全二叉树允许度数为 1 的结点存在但最多只有一个。这个“最多一个度数为 1 的结点”是解题的关键。这里我需要特别强调一个易混淆点很多资料把完全二叉树描述成“只有最后两层可能不满”这种说法在逻辑上没问题但不少同学因此认为“完全二叉树的叶子结点只会出现在最后两层”。严格来说完全二叉树的叶子结点一定集中在最后两层这是由“最后一层左侧连续”决定的。如果最后一层没有满那么倒数第二层靠右的部分结点也可能是叶子。4. 核心公式推导n0 n2 14.1 从度数之和出发在一棵二叉树中假设n0度为 0 的结点数即叶子结点数。n1度为 1 的结点数。n2度为 2 的结点数。总结点数n n0 n1 n2二叉树中每条边连接一个父结点和一个子结点。除了根结点外每个结点有且仅有一条入边。如果总共有 e 条边那么e n - 1因为每个结点贡献的出边数等于它的度度为 0 的结点贡献 0 条边。度为 1 的结点贡献 1 条边。度为 2 的结点贡献 2 条边。所以e 0 * n0 1 * n1 2 * n2 n1 2 * n2于是得到n1 2 * n2 n - 1把 n n0 n1 n2 代入n1 2 * n2 n0 n1 n2 - 1化简2 * n2 n0 n2 - 1n2 n0 - 1也就是n0 n2 14.2 公式的使用边界这个公式对任何非空二叉树都成立与是否完全二叉树无关。理解这一点很重要因为考试中经常会先用这个公式再用完全二叉树的性质来消元。5. 两种解法代数推导 vs 带入公式5.1 解法一分类讨论推荐最稳妥已知 n 768。由二叉树的度数关系n n0 n1 n2 768又有n0 n2 1所以n0 n1 n2 n2 1 n1 n2 2 * n2 n1 1 768即2 * n2 n1 767因为在完全二叉树中n1 只能是 0 或 1所以分类讨论情况一n1 02 * n2 767n2 383.5结点数必须是整数这个情况不成立。情况二n1 12 * n2 1 767n2 383于是n0 n2 1 384验证n n0 n1 n2 384 1 383 768结果完全吻合。所以叶子结点数为384。5.2 解法二利用完全二叉树叶子结点的快速公式在完全二叉树中叶子结点数可以直接由总结点数 n 推导当 n 为奇数时n1 0叶子结点数 n0 (n 1) / 2。当 n 为偶数时n1 1叶子结点数 n0 n / 2。768 是偶数所以n0 768 / 2 384这个结论同样成立。解题时可以两步走先判断 n 的奇偶性再直接除以 2非常快。但这个快速公式最好在理解推导过程之后再使用。否则一旦考题改成“一棵完全二叉树有 2025 个结点求叶子结点数”你还是需要知道为什么奇数除以 2 要加 1。6. 公式速记与变形为了方便考前复习我把常用结论整理成一个速查表条件叶子结点数 n0度为1的结点数 n1度为2的结点数 n2任意二叉树非空n2 1不定n0 - 1完全二叉树总结点数 n 为奇数(n 1) / 20(n - 1) / 2完全二叉树总结点数 n 为偶数n / 21n / 2 - 1满二叉树总层数为 h2^(h - 1)02^(h - 1) - 1这里再提供一个快速记忆方式完全二叉树如果有偶数个结点说明最后一层多出来一个“单分支结点”也就是度为 1 的结点数为 1。完全二叉树如果有奇数个结点说明所有结点都有双分支或叶子度为 1 的结点数为 0。从“最后一层左侧连续排列”来理解这个结论更直观。你可以画一棵结点数分别为 6 和 7 的完全二叉树看看6 个结点时某个结点只有左孩子7 个结点时所有非叶子结点都有两个孩子。7. 代码验证层序遍历构造完全二叉树并统计叶子结点理论推导再严谨也不如实际跑一遍代码放心。下面我用 Python 实现两件事根据总结点数 n 构造一棵完全二叉树。层序遍历统计叶子结点数量。7.1 定义二叉树结点class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right7.2 构建完全二叉树给定总结点数 n从上到下、从左到右依次编号为 1 到 n然后按完全二叉树的索引规律编号为 i 的结点如果 2 * i n则左孩子存在对应编号 2 * i。编号为 i 的结点如果 2 * i 1 n则右孩子存在对应编号 2 * i 1。这里可以使用数组方式创建所有结点再逐层连接。def build_complete_binary_tree(n): if n 0: return None nodes [TreeNode(i) for i in range(1, n 1)] for i in range(1, n 1): left_idx 2 * i right_idx 2 * i 1 if left_idx n: nodes[i - 1].left nodes[left_idx - 1] if right_idx n: nodes[i - 1].right nodes[right_idx - 1] return nodes[0]7.3 统计叶子结点数量叶子结点就是 left 和 right 都为 None 的结点。def count_leaves(root): if root is None: return 0 if root.left is None and root.right is None: return 1 return count_leaves(root.left) count_leaves(root.right)当然也可以用层序遍历来统计。from collections import deque def count_leaves_bfs(root): if root is None: return 0 queue deque([root]) leaf_count 0 while queue: node queue.popleft() if node.left is None and node.right is None: leaf_count 1 if node.left: queue.append(node.left) if node.right: queue.append(node.right) return leaf_count7.4 核验结果n 768 root build_complete_binary_tree(n) leaf_count count_leaves(root) print(f总结点数: {n}) print(f叶子结点数: {leaf_count})输出结果总结点数: 768 叶子结点数: 384这验证了前面的推导768 个结点的完全二叉树叶子结点数是 384。7.5 测试多个 n 值再跑一组数据看看奇偶规律是否稳定for n in [1, 2, 3, 4, 5, 6, 7, 8, 15, 16, 768]: root build_complete_binary_tree(n) leaves count_leaves(root) print(fn {n:3d}, 叶子结点数 {leaves})输出结果n 1, 叶子结点数 1 n 2, 叶子结点数 1 n 3, 叶子结点数 2 n 4, 叶子结点数 2 n 5, 叶子结点数 3 n 6, 叶子结点数 3 n 7, 叶子结点数 4 n 8, 叶子结点数 4 n 15, 叶子结点数 8 n 16, 叶子结点数 8 n 768, 叶子结点数 384可以看到n 为奇数时n0 (n 1) / 2。n 为偶数时n0 n / 2。满二叉树的叶子结点数正好是 2^(h - 1)例如 n 15 时叶子是 8。7.6 进一步验证度数为 1 的结点数也可以写一段代码统计 n1验证完全二叉树中 n1 是否为 0 或 1def count_degree_one(root): if root is None: return 0 queue deque([root]) cnt 0 while queue: node queue.popleft() if (node.left is not None and node.right is None) or \ (node.left is None and node.right is not None): cnt 1 if node.left: queue.append(node.left) if node.right: queue.append(node.right) return cnt测试 n 1 到 10n 1, n1 0 n 2, n1 1 n 3, n1 0 n 4, n1 1 n 5, n1 1 n 6, n1 1 n 7, n1 0 n 8, n1 1 n 9, n1 1 n 10, n1 1完全二叉树中 n1 只可能是 0 或 1这一点在代码中同样得到验证。8. 扩展已知叶子结点数如何反推总结点数2011 年这道题是“已知总结点数求叶子结点数”但 408 也考过反向形式比如已知一棵完全二叉树有 1000 个叶子结点求它的总结点数范围。这种题目用同一套公式解决。假设 n0 1000则 n2 n0 - 1 999。如果 n1 0则 n n0 n1 n2 1000 0 999 1999。如果 n1 1则 n 1000 1 999 2000。所以总结点数可能是 1999 或 2000。如果题目问“至多有多少个结点”答案就是 2000如果问“至少有多少个结点”答案就是 1999。这个变体在考研真题中多次出现值得一并掌握。9. 完全二叉树的层数判断除了叶子结点数408 还经常考察完全二叉树的层数范围。比如一棵完全二叉树的第 6 层有 8 个叶子结点求该完全二叉树的最多结点数和最少结点数。这里的关键是完全二叉树的叶子结点可能出现在倒数第二层和最后一层。第 6 层有叶子结点意味着高度至少为 6。如果高度正好为 6那么第 6 层是最后一层这 8 个叶子结点必须在第 6 层左侧连续排列。如果高度大于 6则第 6 层不一定满可能部分结点有孩子。这种题型的解法通常需要结合“前 h-1 层是满二叉树”的性质逐层计算结点数。它的核心依据仍然是完全二叉树的“最后一层左侧连续”特点。10. 从真题到实际应用堆排序中的完全二叉树完全二叉树不只是考研考点也是很多实际数据结构实现的基础。最典型的例子就是大顶堆、小顶堆。优先队列。堆排序。堆的物理存储通常是数组逻辑结构是完全二叉树。数组下标 i 的左右孩子下标分别是 2 * i 和 2 * i 1这个映射关系与完全二叉树的编号方式完全一致。在这些场景中叶子结点数量也有实际意义建堆时只需要从最后一个非叶子结点开始向下调整。最后一个非叶子结点的下标是n // 2。叶子结点的数量决定了堆排序过程中需要比较的次数分布。例如对于一个长度为 n 768 的数组堆排序建堆时最后一个非叶子结点下标是768 // 2 384。从下标 384 开始向前调整所有下标大于 384 的结点都是叶子结点。叶子结点数量正好是 768 - 384 384。这与本题答案一致。更直接地说在数组表示的完全二叉树中下标从 n//2 1 到 n 的结点全部是叶子结点。这个问题在堆排序、线段树、优先队列的实现中都很常见。11. 相关真题变体与易错点考研复习时只做一道题是不够的。下面列几个常见的变形你能快速算出答案就说明这个知识点基本过关了变体 1一棵完全二叉树有 2025 个结点叶子结点数是多少2025 是奇数所以 n0 (2025 1) / 2 1013。变体 2一棵完全二叉树有 768 个结点度为 2 的结点数是多少根据前面的计算n2 383。变体 3一棵完全二叉树有 2025 个结点度为 1 的结点数是多少2025 是奇数n1 0。变体 4一棵完全二叉树有 1000 个结点叶子结点数是多少1000 是偶数n0 1000 / 2 500。易错点不要把完全二叉树当成满二叉树。满二叉树的叶子结点数 2^(h-1)但完全二叉树没有这个必然结果。不要忘记 n1 在完全二叉树中只能是 0 或 1。任意二叉树中 n1 可以很大但完全二叉树限制了这个值。计算偶数总结点数时n1 1计算奇数总结点数时n1 0。这个对应关系不能搞反。有些同学直接套n0 (n1)/2然后四舍五入这在 n 为偶数时会出错。必须先判断奇偶。12. 实际代码中的二叉树结点统计思路如果从工程角度看“求叶子结点个数”这个任务递归或层序遍历都可以解决问题。递归思路def count_leaves(root): if root is None: return 0 if root.left is None and root.right is None: return 1 return count_leaves(root.left) count_leaves(root.right)层序思路from collections import deque def count_leaves(root): if root is None: return 0 queue deque([root]) cnt 0 while queue: node queue.popleft() if node.left is None and node.right is None: cnt 1 if node.left: queue.append(node.left) if node.right: queue.append(node.right) return cnt两者的时间复杂度都是 O(n)空间复杂度分别是 O(h) 和 O(w)其中 h 是树高w 是树的最大宽度。考试代码题中这两种写法都可以。如果题目要求不能使用递归就用队列实现层序遍历。13. 如何提升这一块的做题速度刷 408 真题时很多同学容易在二叉树的推导题上花费太久。我建议这样做13.1 先把公式变成条件反射看到“完全二叉树”四个字第一反应应该是n1 ∈ {0, 1}。叶子结点可以用总结点数 n 的奇偶性直接判断。看到“任意二叉树”第一反应应该是n0 n2 1。边数 总结点数 - 1。13.2 掌握“代入验证”习惯算出结果后把结果代回原始关系式中验算一遍n n0 n1 n2 是否成立。叶子结点是否满足完全二叉树的性质。例如 768 这个题目算出 n0 384 后n2 383n1 1三者和为 768完全成立。13.3 画图辅助考试时虽然不能跑代码但可以在草稿纸上画一棵结点数较少的完全二叉树来找规律。比如画 n 5、6、7 的完全二叉树观察叶子数量与总结点数之间的关系本质上就是奇偶性的视觉化记忆。14. 更进一步的思考完全二叉树的数组下标规律对考研复习来说知道叶子结点数是 384 已经足够。如果你想从代码实现角度再加深理解可以关注数组下标与完全二叉树的对应关系。在数组实现中根结点下标为 1 时结点 i 的左孩子下标是 2 * i右孩子下标是 2 * i 1。最后一个非叶子结点下标是 n // 2。换句话说叶子结点下标范围是 n // 2 1 到 n。当 n 768 时最后一个非叶子结点下标是 384。下标 385 到 768 都是叶子结点。叶子数量 768 - 384 384。这种方法不需要建立二叉树对象直接利用数组下标就能统计叶子结点数在很多实际算法题中非常高效。比如 LeetCode 风格的题目“给一个数组问堆排序时有多少个叶子结点”就可以直接算n - n // 2。15. 408考试中的时间分配建议在 408 考场上数据结构选择题平均每题控制在 2 到 3 分钟。这类性质推导题如果方法熟练30 秒内可以解决看到 768判断为偶数直接除以 2得 384。如果使用分类讨论法n 768n0 n2 1n1 ∈ {0, 1}。当 n1 1 时n0 768 / 2 384。这比从 n2 反推更快。但前提是你清楚为什么偶数完全二叉树的叶子结点数正好是 n / 2。16. 常见疑问与解答16.1 为什么完全二叉树中 n1 最多为 1完全二叉树的定义要求前 h-1 层必须是满的最后一层可以不满但所有结点必须靠左排列。如果最后一层有一个以上的度数为 1 的结点就会破坏“靠左连续”的结构。比如两个结点都只有左孩子那么在前面的结点之后必然会出现空位这就不满足完全二叉树的要求了。所以 n1 只能是 0 或 1。16.2 为什么 n 为偶数时 n0 n / 2当 n 为偶数时n1 1。由n n0 n1 n2 n0 n2 1可得n n0 1 n0 - 1 2 * n0所以 n0 n / 2。当 n 为奇数时n1 0类似可得n n0 n0 - 1 2 * n0 - 1所以 n0 (n 1) / 2。16.3 完全二叉树的叶子结点一定在最后两层吗是的。完全二叉树的最后一层靠左排列倒数第二层是满的。如果某个结点是倒数第三层的叶子那么它的左侧兄弟或右侧兄弟必然也有子树而它右侧的所有结点就会缺少一层造成最后一层无法连续破坏完全二叉树的定义。所以叶子结点只可能出现在倒数两层。16.4 这道题用满二叉树公式能解吗不能。满二叉树是“所有层都满”的特殊完全二叉树768 并不是 2^h - 1 的形式所以这不是一棵满二叉树。用满二叉树公式算叶子结点数是错误的。17. 其他解法对比上面给出了三种解法分类讨论法。奇偶快速公式法。数组下标法。我建议考试时使用方法一或方法二。方法一的优点是不容易忘记边界条件适合不熟悉奇偶公式的同学。方法二的优点是速度快适合冲刺阶段的快速计算。方法三更适合理解堆排序或者写代码时使用考场上不太推荐额外推导数组下标。这里我再补充一种图形化理解方式画出 768 个结点的完全二叉树你会发现它就是 256 个结点组成的倒数第二层全部有叶子最后一层多了 128 个叶子整体叶子结点数量正好是倒数第二层的 256 个加最后一层的 128 个等于 384。不过图形化方法在考场上比较费时不如下标法快。18. 从真题到教材知识点串联这道题在教材中的关联知识点包括二叉树的基本术语结点度、叶子结点、树的深度。二叉树的性质n0 n2 1。完全二叉树的定义与判定。二叉树的顺序存储结构也就是完全二叉树的数组表示。二叉树的遍历层序遍历、递归遍历。堆与优先队列的底层结构。建议复习时把这一题和“堆排序建堆复杂度”“优先队列底层是完全二叉树”放到一起理解形成知识网络。19. 其他年份类似真题回顾408 历史上多次出现过类似的二叉树性质题。例如已知完全二叉树结点数求叶子结点或度为 1 的结点数。已知完全二叉树的层次遍历序列还原二叉树。已知二叉树的叶子结点数求度为 2 的结点数。2011 年第 4 题就是这一系列题目的典型代表。刷题时可以把 2011、2012、2014 等年份的二叉树性质题放在一起做对比总结出题人惯用的干扰项设计方式。20. 编程题延伸统计完全二叉树叶子的三种实现如果你在准备复试上机这类问题也常出现。下面给三种完整实现思路20.1 递归实现def count_leaves(root): if root is None: return 0 if root.left is None and root.right is None: return 1 return count_leaves(root.left) count_leaves(root.right)20.2 层序遍历实现from collections import deque def count_leaves(root): if root is None: return 0 queue deque([root]) cnt 0 while queue: node queue.popleft() if node.left is None and node.right is None: cnt 1 if node.left: queue.append(node.left) if node.right: queue.append(node.right) return cnt20.3 数组下标直接计算这是针对“完全二叉树存储在数组下标从 1 开始”的特殊实现def count_leaves_by_index(n): return n - n // 2比如 n 768print(count_leaves_by_index(768)) # 384这种实现不构造树只用数学关系复杂度 O(1)。21. 考试答题模板如果你在简答题中需要写出解题过程可以参考下面的模板设叶子结点数为 n0度为 1 的结点数为 n1度为 2 的结点数为 n2。根据二叉树的性质n0 n2 1。又因为该树是完全二叉树所以 n1 只能为 0 或 1。总结点数 768 n0 n1 n2。768 n2 1 n1 n2 2 * n2 n1 1。若 n1 0则 n2 383.5不是整数舍去。若 n1 1则 n2 383n0 384。所以该完全二叉树的叶子结点数为 384。22. 总结与下一步这道 2011 年考研 408 真题的核心考点只有两个任意二叉树都有 n0 n2 1。完全二叉树中度为 1 的结点数最多为 1。已知总结点数为 768偶数可以迅速判断 n1 1叶子结点数 n0 768 / 2 384。建议收藏备用然后继续刷同类变体题特别是已知叶子结点数反推总结点数范围、已知层数和部分叶子结点数求总结点数这两类题目。掌握“奇偶性 度数关系”之后这类选择题基本上 30 秒内就能出答案。