NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 5 题

已知一棵二叉树有 $2013$ 个节点，则其中至多有（ ）个节点有 $2$ 个子节点。

这题核心就是二叉树那个经典性质：叶子数比度为2的节点数多1。拿到题先别慌，把总节点拆成三类（叶子、单孩子、双孩子），利用n=n₀+n₁+n₂和n₀=n₂+1这两个等式，消掉n₀和n₁，直接求n₂的最大值。

很多同学一看到“至多”就想到把n₁设成0，但往往忘了先确认n₀=n₂+1这个性质是否真的成立。还有人容易把“度为2”理解成“有两个孩子”，却忽略度为1的节点也能存在，导致列方程时漏掉n₁。最典型的错误是直接把2013除以2得到1006.5然后四舍五入，或者误以为n₂最大就是n/2，没考虑到n₀必须比n₂多1，所以实际方程是2n₂+n₁=2012，只有当n₁=0时n₂才取到整数最大值1006。

考察知识点

二叉树基础：节点度数与叶子数的关系。

概念定义

二叉树中每个节点的“度”指它拥有的子节点数。度为0的节点是叶子，度为1的节点只有一个孩子，度为2的节点有两个孩子。记n₀、n₁、n₂分别代表三类节点的数量。二叉树有一个极其重要的性质：n₀ = n₂ + 1。这个性质之所以成立，是因为整棵树总边数等于n-1，同时总边数也等于n₁+2n₂（度为1贡献1条边，度为2贡献2条边），联立n=n₀+n₁+n₂即可推出n₀=n₂+1。