完全二叉树768个结点无右孩子结点数怎么算？公式与编号法详解

这次我们来看一道 408 统考数据结构里非常经典的完全二叉树题一棵完全二叉树有 768 个结点其中无右孩子结点有几个这道题经常以各种变体出现在王道、天勤的习题里也是 2011 年统考真题的直接衍生问法。很多同学背熟了“叶子结点数 度为 2 的结点数 1”但一看到“无右孩子结点”这种表述还是会犹豫无右孩子到底包括哪些结点是只算叶子还是把“只有左孩子”的结点也算进去先直接给结论一棵完全二叉树如果有 768 个结点那么无右孩子的结点一共有385 个。这个数字不是靠画图数出来的而是靠完全二叉树的编号性质直接算出来的。下面我会先回顾 2011 年真题原题再从编号法、分类法、Python 验证三个角度拆解这道题最后给出一套通用公式和避坑指南。如果你正在准备 408 考研或者还在复习数据结构二叉树这一章这篇文章可以直接收藏。1. 核心考点速览项目内容考点名称完全二叉树的基本性质所属科目数据结构——树与二叉树常见问法 1完全二叉树第 6 层有 8 个叶结点结点个数最多是多少常见问法 2完全二叉树有 n 个结点无右孩子结点有几个核心结论无右孩子结点数 ⌊n/2⌋ 1常用方法层序编号 孩子编号判断真题背景2011 年 408 统考数据结构第 6 题及同类变式难度评级中等偏易但极易在“无右孩子”概念上出错这道题考察的不是复杂算法而是完全二叉树顺序存储时父子下标关系的理解。只要把编号法吃透考试时 30 秒内可以出答案。2. 题目再现2011 年 408 数据结构第 6 题先回顾当年真题的经典表述已知一棵完全二叉树的第 6 层设根为第 1 层有 8 个叶结点则该完全二叉树的结点个数最多是 。这道题在很多复习资料中的标准答案是111。为什么是 111因为结点总数要最多树的高度就要尽量大。设树高为 7前 6 层是满的前 6 层结点数为2^6 - 1 63第 6 层本身有 2^5 32 个结点其中 8 个是叶结点说明这 8 个结点没有第 7 层孩子。为了让结点总数最多剩下的 32 - 8 24 个结点都应该有第 7 层孩子第 7 层最多有24 × 2 48所以最大结点数为63 48 111这道原题的关键在于理解完全二叉树中第 6 层的 8 个叶结点只能出现在该层靠右的位置这样才能保证第 7 层结点从左侧连续排列。而“无右孩子结点有几个”正是同一考点的更深一层问法它要求我们把完全二叉树里所有没有右孩子的结点一次性数清楚。下面用编号法来拆。3. 用编号法直接推导“无右孩子结点”完全二叉树最常用的性质是层序编号。对一棵有 n 个结点的完全二叉树从 1 到 n 编号根结点编号为 1那么对任意结点 i有左孩子编号为 2i右孩子编号为 2i 1父结点编号为 ⌊i/2⌋这个性质来自完全二叉树顺序存储的逻辑结构也是解决很多二叉树选择题的钥匙。3.1 结点 i 有右孩子的条件结点 i 有右孩子当且仅当右孩子编号 2i 1 不超过总结点数 n也就是2i 1 ≤ n不等式化简i ≤ (n - 1) / 2因为 i 是整数所以有右孩子的结点编号 i 必须满足i ≤ ⌊(n - 1) / 2⌋换句话说编号从 1 到 ⌊(n - 1)/2⌋ 的结点都有右孩子。3.2 结点 i 无右孩子的条件无右孩子就是 2i 1 n即i (n - 1) / 2也就是i ≥ ⌊(n - 1) / 2⌋ 1 ⌊(n 1) / 2⌋这个推导看起来有点绕实际做题时可以直接理解为在一棵完全二叉树中大约后一半结点是没有右孩子的。更精确的结论是无右孩子结点数 n - ⌊(n - 1) / 2⌋ ⌊n / 2⌋ 1这个公式非常重要建议直接记住。3.3 小数据验证先不急着算 768用几个小数据验证一下。n无右孩子结点编号无右孩子个数⌊n/2⌋ 1111121, 22232, 32242, 3, 43353, 4, 53363, 4, 5, 644可见公式完全成立。这也说明一个问题无右孩子结点并不仅仅是叶子结点。比如 n 2 时根结点 1 只有左孩子没有右孩子它是无右孩子结点但并不是叶子结点。4. 768 个结点实例的完整推导现在回到标题的核心问题完全二叉树有 768 个结点无右孩子结点有几个按照第 3 节的编号法n 768。有右孩子的结点需要满足2i 1 ≤ 768即i ≤ 383.5所以有右孩子的结点编号为 1 到 383共 383 个。那么无右孩子结点数就是768 - 383 385用公式验证⌊768 / 2⌋ 1 384 1 3854.1 三类结点的分布明细为了彻底搞懂我们把 768 个结点的完全二叉树拆成三类结点类型判断条件编号范围个数有右孩子结点2i 1 ≤ 7681 ~ 383383只有左孩子结点有左孩子且无右孩子3841叶子结点无左孩子385 ~ 768384所以叶子结点384 个只有左孩子结点1 个无右孩子结点384 1 385 个这里最容易出错的点是很多人算完叶子结点后直接写 384忽略了编号为 384 的结点。这个结点有左孩子 768但没有右孩子它也是“无右孩子结点”。4.2 为什么 n 为偶数时一定会多出 1 个768 是偶数完全二叉树最后一个结点是编号 768。结点 768 的父结点是 ⌊768/2⌋ 384。由于 768 是偶数编号它是父结点的左孩子。父结点 384 既然有左孩子按照完全二叉树的连续编号规则它不一定有右孩子。当 n 768 时右孩子编号应该是 2 × 384 1 769已经超过总结点数所以结点 384 没有右孩子。这就是 n 为偶数时“无右孩子结点数”比“叶子结点数”多 1 的根本原因。当 n 为奇数时最后一个结点是奇数编号它是父结点的右孩子所以不会有“只有左孩子”的结点。此时无右孩子结点数刚好等于叶子结点数。这个规律可以直观记为n 为偶数多一个“单左子”结点无右孩子数 叶子数 1n 为奇数没有“单左子”结点无右孩子数 叶子数5. 通用公式与快速记忆方法把上面的推导整理成一组公式。假设完全二叉树共有 n 个结点指标公式叶子结点数n - ⌊n/2⌋只有左孩子结点数n 为偶数时取 1n 为奇数时取 0无右孩子结点数⌊n/2⌋ 1有右孩子结点数⌊(n - 1)/2⌋其中“无右孩子结点数 ⌊n/2⌋ 1”是最好记的。记忆技巧完全二叉树的结点序号约一半是“左半部分”这些结点从左到右连续拥有左右孩子。无右孩子结点基本集中在后一半但比后一半多一个。例如 n 768后一半是 384 个再多 1 个就是 385。也可以从编号连续性理解最后一个无右孩子结点编号是 768第一个无右孩子结点编号是 ⌊(n-1)/2⌋ 1 384。用等差数列个数公式768 - 384 1 385这个“尾编号 - 首编号 1”的思路在考场上比套公式更快。6. 完全二叉树性质串讲把这道题放到整个知识体系中看它考察的是完全二叉树的一组基础性质。先把相关性质完整过一遍后面遇到类似题就不会慌。6.1 叶子结点只出现在最后两层完全二叉树的特点是除最后一层外每一层都是满的最后一层结点从左到右连续排列。所以叶子结点只会出现在倒数第一层和倒数第二层。6.2 度为 1 的结点最多只有 1 个完全二叉树中只有一个孩子的结点只可能是“只有左孩子”且这样的结点最多 1 个。当结点总数为偶数时存在 1 个当结点总数为奇数时不存在。原因很简单如果某个结点只有右孩子而没有左孩子那编号序列就会出现断档破坏完全二叉树的连续编号结构。6.3 n0 n2 1对于任意非空二叉树叶子结点数 n0 与度为 2 的结点数 n2 满足n0 n2 1这个公式所有二叉树都满足408 选择题经常结合它来出题。回到 n 768 的例子度为 2 的结点有右孩子的结点共 383 个n2 383叶子结点数 n0 n2 1 384和前面的分类结果一致。6.4 高度范围有 n 个结点的完全二叉树高度 h 满足2^(h-1) ≤ n ≤ 2^h - 1反过来已知高度 h可以判断结点数量范围。2011 年真题问“第 6 层有 8 个叶结点结点数最多”本质就是利用高度和分层结点数来求解。7. 相似变式题训练下面给几道变式题可以拿来自测。每道题都标注了解题思路。变式 1完全二叉树有 767 个结点无右孩子结点有几个n 767 是奇数代入公式⌊767 / 2⌋ 1 383 1 384也可以这样理解767 是奇数不存在“只有左孩子”的结点所以无右孩子结点数等于叶子结点数。叶子结点数 767 - ⌊767/2⌋ 767 - 383 384。结果一致。变式 2完全二叉树有 100 个结点无右孩子结点有几个⌊100 / 2⌋ 1 50 1 51因为 100 是偶数编号 50 的结点有左孩子 100但没有右孩子所以多出 1 个。变式 3完全二叉树有 100 个结点有右孩子结点有几个用总数减无右孩子数100 - 51 49也可以直接算⌊(100 - 1) / 2⌋ ⌊99 / 2⌋ 49变式 42011 真题反向提问如果一棵完全二叉树无右孩子结点有 111 个那么总结点数可能是多少由公式反推⌊n / 2⌋ 1 111意味着⌊n / 2⌋ 110所以 n 可以是 220 或 221。这类反向题在模拟卷中偶尔出现用公式可以快速锁定答案范围。变式 5完全二叉树第 6 层有 8 个叶结点结点数最少是多少2011 真题问最多这里再往前一步第 6 层有 8 个叶结点结点数最少时说明第 6 层就是最后一层。第 6 层总共有 32 个结点其中有 8 个叶结点其他 24 个结点位于第 6 层但并不是“叶结点”。这句话要仔细想如果第 6 层是最后一层那么第 6 层的所有结点都应该是叶结点才对。所以“第 6 层有 8 个叶结点”并一定要求第 6 层是最后一层。实际上这个条件隐含的意思是第 6 层的结点中只有 8 个是叶结点其余 24 个有第 7 层孩子。那么结点数最少的情况是第 6 层就是最后一层吗不是。如果第 6 层就是最后一层那么第 6 层所有 32 个结点都是叶子和“只有 8 个叶结点”矛盾。所以树高至少为 7。最少时第 7 层只有 1 个结点此时总数为前 6 层满 63 第 7 层 1 个 64这种情况对应的第 6 层结点中只有 1 个结点有孩子那其他 31 个都是叶子和“8 个叶结点”仍然不符。所以这道题的最小值计算要更细致要让总数最少第 7 层只能有很少的结点但第 6 层又必须恰好有 8 个叶结点。由于完全二叉树的连续性第 6 层靠右的结点如果已经是叶子那么它右侧的结点都不能有第 7 层孩子。实际上最小情况是第 7 层只有 16 个结点对应第 6 层有 8 个结点有孩子其余 24 个是叶子也不符合“8 个叶结点”。这里需要特别注意“叶结点”的定义如果一个第 6 层结点有第 7 层孩子它就不是叶结点。所以第 6 层的 8 个叶结点意味着第 6 层只有 8 个结点没有第 7 层孩子剩下 24 个结点都有第 7 层孩子。因此第 7 层结点数最少是 24 × 1 24 吗不是完全二叉树第 7 层结点必须从左到右连续且这些结点的父结点也必须是连续的。最少情况是第 6 层有 24 个结点有孩子为了总数最少这 24 个结点应该尽量靠左第 7 层每个有孩子的第 6 层结点至少贡献 1 个孩子。但完全二叉树的第 7 层要连续所以不能是每个结点只生一个孩子然后空着。实际上最少时第 7 层只有 16 个结点对应第 6 层前 8 个结点有孩子。但这样第 6 层只有 8 个结点不是叶结点其他 24 个是叶结点仍然不符合“8 个叶结点”。问题出在表述上。更严谨的说法是完全二叉树第 6 层有 8 个叶结点意思是这 8 个叶结点位于第 6 层并且它们没有孩子而第 6 层其他结点是否有孩子不确定。要让总数最少应该是第 6 层这 8 个叶结点靠左其余 24 个结点靠右且都没有孩子不对如果靠右的 24 个结点没有孩子那它们也是叶结点这样叶结点就是 24 个而不是 8 个。所以正确的理解是第 6 层有 8 个叶结点意味着第 6 层恰好有 8 个结点没有孩子其余 24 个结点都有孩子。要让总数最少第 7 层的结点数应该尽可能少。完全二叉树中第 7 层如果有结点一定从第 7 层最左侧开始连续排列。对应的父结点在第 6 层也是从左到右连续。设第 6 层有 k 个结点有孩子则第 7 层至少有 k 个不完全对。因为每个有孩子的第 6 层结点都可以有 1 或 2 个孩子但第 7 层必须连续编号所以如果前 m 个第 6 层结点有孩子第 7 层结点数必须在某个范围内。最少的第 7 层结点数是第 6 层前 24 个结点都有孩子时第 7 层至少有 24 个结点每个都有左孩子。此时第 7 层只有 1 个不对24 个父结点每个至少有一个左孩子第 7 层从左到右先排 24 个左孩子所以至少有 24 个结点。这样总结点数就是63 24 87所以第 6 层有 8 个叶结点时结点数最少为 87最多为 111。这个结论在一些教材习题中出现过。不过这道变式题不是 2011 年原题只是用于加深理解。这里我不展开太多以免偏离主线。核心是记住第 6 层有 8 个叶结点相当于第 6 层有 32 - 8 24 个非叶结点这些结点是第 7 层结点的父结点。8. 常见错误与避坑指南这类题虽然简单但错误率一直不低。下面把最常见的几个坑单独列出来。8.1 混淆“无右孩子”和“叶子结点”无右孩子结点包含两类叶子结点无左孩子也无右孩子只有左孩子没有右孩子的结点很多人算出叶子结点数后直接当作答案忽略单分支结点。n 768 的例子里叶子结点是 384 个无右孩子结点是 385 个恰好差 1 个。8.2 忘记 n 为偶数时多一个单分支结点完全二叉树只有在总结点数为偶数时才会出现“只有左孩子”的结点。这个结点的编号是 n/2。奇数时没有这个结点。很多同学公式记了一半只记得“无右孩子约等于一半”结果在偶数情况上被扣分。8.3 不等式方向搞反有右孩子条件是 2i 1 ≤ n无右孩子条件是 2i 1 n。考试时如果时间紧张容易把编号范围算成“前一半”和“后一半”反了。建议做题时先写不等式再代入具体数字不要凭感觉。8.4 完全二叉树画成满二叉树有些同学一看到完全二叉树就直接脑补成满二叉树。满二叉树所有非叶结点都有左右孩子而无右孩子结点个数是固定的 ≈ n/2。这个差距非常大。满二叉树只是完全二叉树的特殊情况。8.5 忽略根结点的情况当 n 比较小时容易忽略特殊结点。例如 n 2 时根结点没有右孩子但它不是叶子。用公式 ⌊n/2⌋ 1 2 可以覆盖这种情况。9. 用 Python 做一次自动化验证这类选择题最适合写一个简单脚本验证加深对完全二叉树编号规则的理解。下面这个脚本遍历 1 到 n 的所有结点统计无右孩子结点数量。def count_nodes_without_right_child(n: int) - int: cnt 0 for i in range(1, n 1): right_child 2 * i 1 if right_child n: cnt 1 return cnt for n in [1, 2, 3, 4, 5, 6, 7, 8, 100, 767, 768]: result count_nodes_without_right_child(n) formula n // 2 1 print(fn {n}, 无右孩子结点 {result}, 公式结果 {formula}, 是否一致 {result formula})运行输出n 1, 无右孩子结点 1, 公式结果 1, 是否一致 True n 2, 无右孩子结点 2, 公式结果 2, 是否一致 True n 3, 无右孩子结点 2, 公式结果 2, 是否一致 True n 4, 无右孩子结点 3, 公式结果 3, 是否一致 True n 5, 无右孩子结点 3, 公式结果 3, 是否一致 True n 6, 无右孩子结点 4, 公式结果 4, 是否一致 True n 7, 无右孩子结点 4, 公式结果 4, 是否一致 True n 8, 无右孩子结点 5, 公式结果 5, 是否一致 True n 100, 无右孩子结点 51, 公式结果 51, 是否一致 True n 767, 无右孩子结点 384, 公式结果 384, 是否一致 True n 768, 无右孩子结点 385, 公式结果 385, 是否一致 True脚本逻辑很简单一个结点没有右孩子当且仅当它的右孩子编号 2i 1 大于总结点数 n。这个逻辑和考试时的编号法完全一致建议复习时自己写一遍。如果需要生成一棵具体树来核对可以再加一个递归建树和层序打印的函数。不过对刷题来说上面的统计脚本已经够用。10. 备考建议与自我检验方法10.1 先画图再记公式第一次接触完全二叉树性质时不要直接背公式。建议画出 n 1 到 n 7 的完整树形逐个标注结点编号再用红笔圈出无右孩子结点。画一遍后编号法的直觉就建立了。10.2 把公式推导过程写在错题本上错题本上不要只写结论要把如下推导写一遍结点 i 无右孩子 ⟺ 2i 1 n ⟺ i ≥ ⌊(n 1) / 2⌋ ⟺ 无右孩子结点数 n - ⌊(n - 1) / 2⌋ ⌊n / 2⌋ 1考试时即使忘记公式也能在 1 分钟内重新推出来。10.3 同类知识点对比记忆完全二叉树题目经常把“叶子结点数”“分支结点数”“无右孩子数”“树高”放在一起考。复习时可以做一张横向对比表考察点核心公式易错点叶子结点数n - ⌊n/2⌋忘记 n0 n2 1无右孩子结点数⌊n/2⌋ 1忘记单分支结点有右孩子结点数⌊(n-1)/2⌋不等式方向树高范围2^(h-1) ≤ n ≤ 2^h - 1忘记等号10.4 做题时先判断 n 的奇偶性看到“完全二叉树 结点个数”类题目第一步先判断 n 是奇数还是偶数。奇偶性直接决定有没有“只有左孩子”的结点。如果 n 是偶数无右孩子数 叶子数 1如果 n 是奇数无右孩子数 叶子数。11. 总结回到最初的问题完全二叉树有 768 个结点无右孩子结点有几个答案是385 个。记忆路径有两条公式法⌊768/2⌋ 1 384 1 385编号法无右孩子结点编号为 384 到 768共 385 个这道题真正要掌握的不是背一个具体答案而是理解完全二叉树层序编号与孩子编号的关系。只要掌握了“结点 i 的右孩子编号是 2i 1”这一条性质无论题目换成“有右孩子结点有几个”“第 6 层有 8 个叶结点最多多少个结点”都能在 30 秒内解出来。建议收藏这篇文章刷到二叉树选择题时拿出来对照复习。