NOIP 普及组初赛 · NOIP 2008 普及组初赛试题 第 5 题

完全二叉树共有 $2N-1$ 个结点，则它的叶节点数是（ ）。

这题不用画图，直接套二叉树那个最经典的结论：叶子数总比度为1的节点数多1。把完全二叉树的总节点数拆成‘叶子+度1点’，列个简单方程就能秒杀。

很多同学习惯背‘完全二叉树叶子数等于总节点数的一半（向上取整）’，这招只适用于计算叶子数，但本题问的是用N表示的答案，直接套一半会算出N，却忘了验证是否符合二叉树性质。另一个坑是混淆度为1的节点数：完全二叉树里度为1的节点要么0个要么1个，但题目给的是2N−1这种奇数个节点，说明度为1的节点必然是1个（即最后一层只有一个节点），这一点如果不反应过来，就会误以为度为1的节点是0个，导致算出叶子数=N−1，选错A。还有的同学把N当成‘非叶子节点数’，其实N就是总节点数的一半，概念不清容易在列方程时把I写成N而不是N−1。

完全二叉树的叶子数

设叶子节点数为L，度为1的节点数为I。任意二叉树都满足$L = I + 1$。

完全二叉树总节点数为$2N-1$，即$L + I = 2N-1$。

将$L = I + 1$代入总节点式： $(I + 1) + I = 2N - 1$ $2I = 2N - 2$ $I = N - 1$

于是叶子数$L = I + 1 = N$。

因此答案是B（N）。

命题视角

这题在初赛里属于送分题，但命题人特意把总节点数写成$2N-1$而不是直接给数字，就是为了考察你是否真正理解‘度为1的节点’在完全二叉树里的特殊性。

完全二叉树里，度为1的节点要么0个要么1个。当总节点数是奇数时，最后一层只有一个节点，这个节点必然是度为1的节点，所以$I = 1$；当总节点数偶数时，最后一层要么全满要么空，此时$I = 0$。

题目给的是$2N-1$，显然是奇数，所以$I = 1$，代入$L = I + 1$就得$L = 2$，但这只是针对具体数字的情况。而本题用N表示，实际上是把$I$用$N$表达出来：$I = N - 1$，$L = N$。