树的常考性质

结点数与总度数

树中边数等于结点数减 1。每条边都对应某个结点的一个孩子分支，所以：

$$
结点数 = 总度数 + 1
$$

这是普通树计数题的基础公式。

度为 m 的树与 m 叉树

项目 度为 m 的树 m 叉树
每个结点孩子数 至多 m 个 至多 m 个
是否必须有度为 m 的结点 必须至少有一个 不要求
是否可为空树 不可为空 可以为空
最少结点数 至少 $m+1$ 可以为 0

不要把“度为 m 的树”和“m 叉树”混用。前者强调整棵树的最大度恰好为 m；后者只是限制每个结点最多有 m 个孩子。

第 i 层最多结点数

度为 m 的树或 m 叉树，第 i 层至多有：

$$
m^{i-1}\quad(i\ge 1)
$$

根在第 1 层，所以第 1 层最多 $m^0=1$ 个结点。

高度为 h 的 m 叉树最多结点数

高度为 h 的 m 叉树至多有：

$$
1+m+m^2+\cdots+m^{h-1}=\frac{m^h-1}{m-1}
$$

达到上界时，每一层都满。

最少结点数

  • 高度为 h 的 m 叉树至少有 h 个结点：每层只有一个结点即可。
  • 高度为 h、度为 m 的树至少有 h + m - 1 个结点：既要保证高度为 h，又要至少有一个结点拥有 m 个孩子。

n 个结点的 m 叉树最小高度

要让高度最小，应尽量填满每一层。设高度为 h：

$$
\frac{m^{h-1}-1}{m-1}<n\le \frac{m^h-1}{m-1}
$$

推出：

$$
h_{\min}=\lceil \log_m(n(m-1)+1)\rceil
$$

该公式适用于 m > 1。