NOIP 普及组初赛 · NOIP 2015 普及组初赛试题 第 22 题

一棵结点数为 $2015$ 的二叉树最多有___个叶子结点。

这题考二叉树叶子结点最大值。拿到题先想：叶子最多意味着非叶子结点都得‘生’两个孩子，也就是要尽量凑成满二叉树。用公式 n 个结点满二叉树叶子=⌈n/2⌉，直接套 2015 算即可。

很多同学会误以为叶子最多是链状结构，或者死记硬背成 n/2 直接除，遇到奇数就懵了。其实叶子最多的情况恰恰是‘每个有孩子的结点都有两个孩子’，也就是满二叉树。2015 是奇数，非叶子结点最多只有 1007 个，剩下的 1008 个必然是叶子。别被‘几乎一半’的直觉带偏，奇数时叶子反而比非叶子多一个。

二叉树叶子最多的情况

这题考查二叉树中叶子结点数量的极值问题。核心思路是：要让叶子结点最多，就得让非叶子结点尽可能多地‘生’两个孩子，也就是要把树往‘满’的方向凑。

概念：满二叉树与叶子数公式

所谓满二叉树，是指除了最后一层外，所有层都是满的，且最后一层的结点都靠左排列。在这种树里，每个有孩子的结点都有两个孩子，没有‘单孩子’的情况。

对于 n 个结点的二叉树，叶子结点数的最大值就是满二叉树时的叶子数，公式为：

叶子数最大值 = ⌈n / 2⌉

（⌈x⌉ 表示向上取整）

为什么是 n/2 向上取整？因为每增加一个非叶子结点，就会同时增加两个新结点（两个叶子），所以非叶子结点最多有 ⌊n/2⌋ 个，而叶子结点就是剩下的 n - ⌊n/2⌋ = ⌈n/2⌉ 个。