1 定义
树是一种数据结构，它是由n(n≥0)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。
2 术语
结点：
- 根结点：树最上面的结点，其不存在父结点
- 父结点：结点的前驱结点
- 子结点：结点的后继结点
- 兄弟结点：同个父结点下的子结点
- 叶子结点：度为0的结点
结点属性：
- 度：拥有的子树的数量被称为结点的度
- 层次：从根结点开始，根结点的层次为1，根结点的子结点为第二层，往下以此类推
- 高度：结点距最底层的叶子结点的距离称为结点的高度
- 深度：结点距根结点的距离称为结点的深度
树属性：
- 度：树中结点的度的最大值
- 高度/深度：树中结点的最大层次
3 表示方法
3.1 树状表示法
image.png
3.2 括号表示法
用括号先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。
(1(2(4(8,9),5(10)),3(6,7)))、
3.3 凹入表示法
1------------------
2--------------
4----------
8------
9------
5----------
10-----
3--------------
6----------
7----------
3.4 文氏图表示法
image.png
4 遍历方法
4.1 前序遍历
又叫先根遍历
- 结点1及子结点：1,2,3
- 结点2及子结点：1,2,4,5,3
- 结点3及子结点：1,2,4,5,3,6,7
- 结点4及子结点：1,2,4,8,9,5,3,6,7
- 结点5及子结点：1,2,4,8,9,5,10,3,6,7
4.2 中序遍历
仅二叉树有，又叫中根遍历
- 结点1及子结点：2,1,3
- 结点2及子结点：4,2,5,1,3
- 结点3及子结点：4,2,5,1,6,3,7
- 结点4及子结点：8,4,9,2,5,1,6,3,7
- 结点5及子结点：8,4,9,2,10,5,1,6,3,7
4.3 后序遍历
又叫后根遍历
- 结点1及子结点：2,3,1
- 结点2及子结点：4,5,2,3,1
- 结点3及子结点：4,5,2,6,7,3,1
- 结点4及子结点：8,9,4,5,2,6,7,3,1
- 结点5及子结点：8,9,4,10,5,2,6,7,3,1
4.4 层序遍历
- 第1层：1
- 第2层：1,2,3
- 第3层：1,2,3,4,5,6,7
- 第4层：1,2,3,4,5,6,7,8,9,10
| 遍历方式 | 结果 |
|---|---|
| 前序遍历 | 1,2,4,8,9,5,10,3,6,7 |
| 中序遍历 | 8,4,9,2,10,5,1,6,3,7 |
| 后序遍历 | 8,9,4,10,5,2,6,7,3,1 |
| 层序遍历 | 1,2,3,4,5,6,7,8,9,10 |
tips:
树的深度搜索与树的前序遍历同理
树的广度搜索与树的层次遍历同理
5 种类
5.1 是否有序
- 无序树：树中任意结点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树；
- 有序树：树中任意结点的子结点之间有顺序关系，这种树称为有序树；
5.2 分支数量
- 二叉树：一个结点最多只有两个子树，例如：红黑树
- 多叉树：多叉树一个结点可以有多于两个的子树，例如：B树
