1.树的基本概念

基本术语

1. 度大于0的结点称为分支结点（又称非终端结点)；度为0（没有子女结点）的结点称为叶结点（又称终端结点）。在分支结点中，每个结点的分支数就是该结点的度。
2. 森林。森林是m(m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

性质

1. 树中的结点数等于所有结点的度数之和加 1
2. 度为m的树中第i层上至多有$m^{i-1}$个结点
3. 高度为h的m叉树至多有$\displaystyle\frac{m^h-1}{m-1}$个结点
4. 具有n个结点的m 叉树的最小高度为$\left \lceil \log_{m}(n(m-1)+1) \right \rceil$

性质4的证明

假设最小高度为$h$，则根据性质 3 我们可以得到

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

即结点$n$个数应当大于前一层最大的结点数，并且小于等于当前层的最大数
将不等式移项整理可得

$$n(m-1)+1\leq m^h$$

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

image.png