5.1.3 树的计数性质

设度为 $i$ 的结点数为 $n_i$。总结点数 $n=\sum n_i$，总分支数既等于 $n-1$，又等于各结点孩子数之和 $\sum i{n}_i$，故 $\sum i{n}_i=n-1$。这条“双重计数”比死背叶结点公式更通用。度为 $m$ 的树第 $k$ 层最多 $m^{k-1}$ 个结点，高度 $h$ 最多 $(m^h-1)/(m-1)$ 个。

手工推演

若一棵树有 $n_0$ 个叶、$n_1$ 个一度结点、$n_2$ 个二度结点、$n_3$ 个三度结点，则 $n_1+2n_2+3n_3=n-1=n_0+n_1+n_2+n_3-1$，消去得 $n_0=1+n_2+2n_3$。一度结点数被消去并非遗漏，而是贡献正好抵消。

结构与代码

最少高度问题等价于尽量填满前几层；给定高度求最少结点则必须看题目是否要求每层至少一个结点、树的度是否“恰为”某值。仅知最大度不代表每个内部结点都达到最大度。

错解反馈

把“树的度为 3”理解成所有非叶度都为 3；把最大结点公式拿来算最少值；忘记空树或根层约定；只列结点数不列边数等式，都是常见失分点。

迁移练习

已知 $n_2=4,n_3=2$，求叶数。答案 $1+4+2\times 2=9$，与 $n_1$ 无关。独立验收：能从边的两种计数现场推导，而非背结果。