树与二叉树.pdf

第七章第七章
树与二叉树
一个数据元素: 一个结点结点
A
数据元素(结点)之间的关系: 分支分支
A
B
本本章章主主要要内内容容
重点
重点
树
(Huffman)
树的基本概念
二叉树
树的存储结构
平衡二叉树
哈夫曼
二叉树的存储结构二叉树的遍历线索二叉树二叉排序树





*
树的基本概念树的基本概念

树树是由n≥0个结点组成的有穷集合(不妨用
符号D表示)以及结点之间关系组成的集合构成
的结构,记为T。当n=0时,称T为空树。
在任何一棵非空的树中,有一个特殊的结
点t∈D,称之为该树的根结点;其余结点D–{t}被
分割成m>0个不相交的子集D1, D2, …,Dm,其中,
每一个子集Di分别构成一棵树,称之为t的。子树子树
递归定义递归定义
A
T1 T2 T3
B C X
E F G H I J
A的第1棵子树 A的第3棵子树
A的第2棵子树
不不
相相 A A
交交 B
的的 B C C
子子 X E F X F
集集
A
T1 T2 T3
B C X
E F G H I J
A的第1棵子树 A的第3棵子树
A的第2棵子树
(逻辑上)的特点
,该结点为树的根结点;
,每个结点有且仅有一个直接前驱结点;
,每个结点可以有多个后继结点。

1. 文氏图表示法
教材P161页
2. 凹入表示法
3. 嵌套括号表示法(广义表表示法)
A( B( E, F, G ), C( H ), X( I, J ) )
A
B C X
E F G H I J
4. 树形表示法
借助自然界中一棵倒置的树的形状
来表示数据元素之间层次关系的方法。
A
B C X
E F G H I J

1. 结点的度:该结点拥有的子树的数目。
2. 树的度:树中结点度的最大值。
3. 叶结点:度为0 的结点。(终结点)
4. 分支结点: 度非0 的结点。(非终结点)
5. 树的层次: 根结点为第一层,若某结点在第i 层,
则其孩子结点(若存在)为第i+1层。
6. 树的深度: 树中结点所处的最大层次数。
A 第1层第1层
深
度
为 B C X 第2层第2层
3
E F G H I J 第3层第3层
7. 路径:若在树中存在一个结点序列d1,d2, …, dj,使
得di是di+1的双亲(1≤i<j),则称该结点序列
是从di到dj的一条路径。路径的长度为j-1。
8. 祖先与子孙:若树中结点d到ds存在一条路径,则
称d是ds的祖先,ds是d的子孙。
一个结点的祖先是从根
从根结点到树中结点到该结点路径上所
其余结点均分别存在经过的所有结点;而一
一条唯一路径个结点的子孙则是以该
结点为根的子树上的所
A 有其他结点。
B C X
E F G H I J