一. 树的定义和基本术语

1. 树是n（n≥0）个结点的有限集合，n = 0时，称为 空树 。

   

2. 非空树中应满足：
   有且仅有一个特定的称为根的结点。
   当n > 1时，其余结点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

   

3. 度：树中一个结点的孩子个数称为该结点的度。所有结点的度的最大值是树的度。
   度大于0的结点称为分支结点，度为0的结点称为叶子结点。

4. 结点的层次（深度）：从上往下数。
   结点的高度：从下往上数。
   树的高度（深度）：树中结点的层数。

5. 祖先结点：从一个结点出发，一直向上走，一直走到根结点为止，所经过的所有结点都是祖先结点。
   子孙结点：从一个结点出发所有的分支都属于子孙结点。
   双亲结点（父结点）：一个结点的直接前驱结点。
   孩子结点：一个结点的直接后继结点。
   兄弟结点：前驱结点为同一个结点的结点。

6. 若树中结点的各子树从左至右是有次序的，不能互换，则该树称为有序树，否则称为无序树。

7. 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。

8. 森林：森林是m（m≥0）棵互不相交的树的集合。

   

---

二. 树的常考性质

1. 结点数 = 总度数 + 1

由于树的特殊结构以及度数的定义，我们可以发现第n-1层的结点度数之和就是第n层的所有结点数量，如此循环往复，我们就能知道从第1层到第n层的结点度数和实际上就是除了根节点之外的所有结点的数量。

---

2. 度为 m 的树、m 叉树的区别

---

3. 度为 m 的树第 i 层至多有 m^i-1个结点（i≥1）

同理：m 叉树第 i 层至多有 m^i-1 个结点（i≥1）。

---

4. 高度为 h、度为 m 的树至多有 $\frac{m^h-1}{m-1}$ 个结点。（等比数列求和）

等比数列求和公式：      直接带入公式得到结果。

---

5. 高度为 h、度为 m 的树至少有（h+m-1）个结点。

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

---

6. 具有 n 个结点的 m 叉树的最小高度为 ⌈log_m ( n ( m − 1 ) + 1 )⌉