Ⅴ. 树

1. 树的基本术语

1. 结点
2. 结点的度 ： 拥有的分支个数（该结点子结点的个数）
3. 树的度 ： Max(结点的度)
4. 叶子结点，非叶子结点
5. 孩子，双亲，兄弟，祖先，子孙
6. 层次 ： 从根开始，根为第一层，根的孩子为第二层，依此类推
7. 树的高度 ＝ 树的深度 ： 树中结点最大层次
8. 结点的高度 ： 从该结点的最底层叶子结点算起，记最底层的高度为1，到该结点所经过的结点个数（包括此结点）为结点的高度
9. 结点的深度 ：计算一个结点的深度， 从 根结点算起，记根的结点深度为1，可以这样理解，从1开始计数，而不是0（统一规定一下），到该结点所经过的结点个数（包括此结点）为结点的深度
   [注] 有些参考书记最底层高度为0，根的结点深度为0，在此，统一记为1
10. 堂兄弟
11. 森林
12. 树的性质：
    • (1) 树中的结点数 = 所有结点的度数 + 1
    • (2) 度为 m 的树中第 i 层上至多有 m^(i-1) 个结点
    • (3) 高为 h ， 度为 m 的树，至多有( (m^h)-1)/(m-1)
    • (4) 具有 n 个结点的 m 叉树的最小高度为logm(n*(m-1)+1)取上整
      [注] (2) -> (3) -> (4) （可推导）

---

树的深度和高度的图解

[注]
树的深度是从根结点开始，自上而下逐层累加
树的高度是从叶结点开始，自底向上逐层累加
结点的高度从该结点对应的最底层叶子结点算起，记最底层的高度为1

规定：
空树的高度记为 0
单结点的(子)树(即只有根节点)的高度记为 1

任意一个结点 ： Depth(V) + Height(V) <= Height(T)

---

2. 树的表示结构

1. 父结点＋孩子结点 的树结构
   父结点 + 孩子结点

• 采用结构体数组表示 !

2. 长子兄弟表示法 的树结构
   对一个树：其中任一个结点的第一个孩子结点（若存在）作为其"左孩子"，第一个兄弟结点（若存在）作为其"右孩子"，从根开始整理
   [注] 长子兄弟 的树结构表示法可以将"任意多叉树表示成二叉树"

长子-兄弟表示法

3. 如何利用二叉树来描述多叉树
在实际应用中，二叉树的使用情况是最多的，相关的算法也是很完善的，若能将一棵树(多叉树)表示成二叉树结构，就能很好的对一棵树进行操作（上面的长子兄弟表示法能够将任意多叉树表示成二叉树）

• 二叉树是多叉树的特例，在有根并且有序的情况下，其描述能力足以覆盖后者。（即满足这两个）
• 多叉树都可以表示为二叉树 （长子兄弟表示树结构来构造，见上图）