基本概念
- 定义
树是n个节点的有限集,有且仅有一个特定的称为根的节点
-
图示
-
特点
- 根节点是唯一的
- 子树的个数没有限制,但他们一定是互不相交的
- 树中的概念
- 结点的度(Degree)
- 结点拥有的子树数
- 叶结点
- 度为0的结点
- 分支结点
- 度不为0的节点
- 内部结点
- 除了根节点以外的分支节点
- 树的度
- 树内各结点的度的最大值
- 结点的关系
- Child
- 结点的子树
- Parent
- 该结点
- Sibing
- 同一个Parent的Child
- 其他概念
-
树的深度(Depth)
- 结点的最大层次
-
有序树
- 树中结点的各子树从左至右是有序的,则称其为有序树
-
森林
- m棵互不相交的树的集合
树的ADT
树的存储结构
Parent表示法
|
|
Child表示法
- 多重链表表示法
每个结点有多个指针域,每个指针域指向一棵子树的根节点
- Child表示法
把每个结点的孩子结点排列起来,以单链表作为存储结构将他们存储起来
- 图示
- 代码
|
|
Sibling表示法
- 方法
设置两个指针,指向该结点的
fristchild
和rightsib
- 结构定义
|
|
- 图示
二叉树
定义
n个结点的有限集合,由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树构成
特点
-
每个结点最多两棵子树
-
左子树和右子树是有顺序的,一定要区分开
-
五种形态
-
空二叉树
-
只有一个根结点
-
根结点只有左子树
-
根结点只有右子树
-
根结点既有左子树又有右子树
特殊二叉树
- 斜树
- 左斜树和右斜树并称斜树
- 满二叉树
- 分支节点均有两个子树的二叉树
- 图示
- 完全二叉树
-
定义
- 编号为$i(1\le i\le n)$的结点与满二叉树中相应位置编号相同的二叉树
-
特点
- 叶子结点只出现在最下两层
- 最下层的子叶一定集中在左部连续位置
- 同样结点数的二叉树,完全二叉树的深度最小
-
图示
二叉树的性质
-
在二叉树的第$i$层上,最多只有$2^{i-1}$个结点
-
深度为$k$的二叉树,至多有$2^k -1$个结点
-
叶结点为$n_0$,度为2的结点数为$n_2$,则$n_0 = n_2 + 1$
-
具有$n$个结点的完全二叉树的深度为$\lfloor log_2 n\rfloor + 1$
-
对于完全二叉树的任意结点$i(1\le i \le n)$
- $i=1$,则为根结点
- $i \gt 1$,则parent结点为$\lfloor i/2 \rfloor$
- $2i \gt n$,则其无左孩子,否则其左孩子是结点$2i$
- $2i+1 \gt n$,则其无右孩子,否则其右孩子是结点$2i+1$
二叉树的存储结构
顺序存储结构
- 一般只用于完全二叉树
二叉链表
- 结点结构
lchild | data | rchild |
---|
- 代码表示
|
|
遍历二叉树
定义
从根结点出发,依照某找次序,依次遍历结点,使得每个结点仅被访问一次
方法
前序遍历
- 定义
若二叉树为空,则空操作返回;否则先访问根结点,再前序遍历左子树,最后前序遍历右子树
- 代码实现
|
|
中序遍历
- 定义
若二叉树为空,则空操作返回;否则从根结点开始,先中序遍历左子树,再访问根结点,最后中序遍历右子树
- 代码实现
|
|
后序遍历
-
定义可根据上述自行推导
-
代码实现
|
|
二叉树遍历的性质
-
已知前序和中序遍历(后序和中序遍历)可以确定唯一的二叉树.
-
已知前序和后序遍历,无法确定唯一的二叉树.
二叉树的建立
|
|
线索二叉树
线索
指向前驱和后继的指针被称为线索,加上线索的二叉链表就被称为二叉链表,相应的二叉树被称为线索二叉树(Threaded Binary Tree)
线索化
- 定义
对于二叉树使用某种方式遍历使其成为线索二叉树
- 结点结构
lchild | ltag | data | rtag | rchild |
---|
-
ltag
为0时,指向lchild
;为1时,指向前驱 -
rtag
为0时,指向rchild
;为1时,指向后继
- 代码实现
|
|