树的性质

结点数=总度数+1

度为m 的树与 m叉树 的区别

度为m 的树：

• 任意结点的度 <=m （最多m个孩子）
• 至少有一个结点度 =m （有m个孩子）
• 一定是非空树，至少有 m+1 个结点

m叉树 ：

• 任意结点的度 <=m （最多m个孩子）
• 允许所有结点的度都 <m
• 可以是空树

度为m 的树 / m叉树 第 i 层 至多 有 $m^i-1$ 个结点 (i>=1)

高度为 h 的 m叉树 至多有 $\frac{m^h-1}{m-1}$ 个结点

高度为 h 的 m叉树 至少有 h 个结点

高度为 h 的 度为m 的树 至少有 h+m-1 个结点

具有 n 个结点的 m叉树 的最小高度为 $\lceil log_m(n(m-1)+1) \rceil$