mirror of
https://github.com/happyflyer/wangdao-data-structure.git
synced 2026-02-02 18:20:02 +08:00
树与二叉树
1. 树的基本概念
树是 n（n \geq 0） 个结点的有限集合，n=0 时，称为空树。
而任意非空树应满足：
- 有且仅有一个特定的称为根的结点。
- 当
n>0时，其余结点可分为m（m \geq 0）个互不相交的有限集合，其中每一个集合本身又是一棵树，称为根结点的子树。
n 个结点的树中只有 n-1 条边。
2. 基本术语
- 祖先结点和子孙结点
- 双亲结点和孩子结点
- 兄弟结点
- （结点的）度：树中一个结点的子结点的个数称为该结点的度。
- （树的）度：树中最大度数。
- 分支结点：度大于
0的结点。 - 叶子结点：度为
0的结点。 - 结点的层次：根结点为第一层（或第零层）。
- 结点的高度：从叶子结点（第一层）开始逐层累加。
- 结点的深度：从根结点（第一层）开始逐层累加。
- 树的高度（深度）是树中结点的最大层数。
- 有序树和无序树
- 路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。（树的分支是有向的，即从双亲结点指向孩子结点，所以路径一定是自上而下的。）
- 路径长度：路径上所经过边的个数。
- 森林：
m（m \geq 0）棵互不相交的树的集合。
3. 树的性质
- 树中结点树等于所有结点的度加 $1$。
- 度为
m的树中第i层上至少有m^{i-1}个结点（$i \geq 1$）。 - 高度为
h的m叉树至多有(m^h-1)/(m-1)个结点。 - 具有
n个结点的m叉树的最小高度为：$\left \lceil log_m(n(m-1)+1) \right \rceil$。
性质二说明：
- 第一层：
1=m^0 - 第二层：
1=m^1 - 第三层：
1=m^2 - ...
- 第
i层：1=m^{i-1}
4. 二叉树
4.1. 五种基本形态
4.2. 二叉树 VS 度为 2 的有序树
4.3. 特殊二叉树
4.4. 二叉树的性质
4.5. 二叉树的存储结构
4.6. 二叉树的遍历
4.7. 线索二叉树
4.7.1. 线索二叉树的概念
- 先序线索二叉树
- 中序线索二叉树
- 后序线索二叉树
4.7.2. 线索二叉树的构造
5. 树的存储结构
| 优点 | 缺点 | |
|---|---|---|
| 双亲表示法 | 寻找结点的双亲结点效率高 | 寻找结点的孩子结点效率低 |
| 孩子表示法 | 寻找结点的孩子结点效率高 | 寻找结点的双亲结点效率低 |
| 孩子兄弟表示法 | 寻找结点的孩子结点效率高，方便实现树转换为二叉树 | 寻找结点的双亲结点效率低 |
6. 树与森林
| 树 | 森林 | 二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |