文档介绍：第二部分树和二叉树
一、树的定义和基本概念
1 树的存储结构
二、二叉树
1 二叉树的定义和基本术语
2 二叉树的性质
3 二叉树的存储结构
三、遍历二叉树
1 遍历二叉树
2 线索二叉树
四、二叉排序树和平衡二叉排序树
1 二叉排序树
2 平衡二叉排序树
五、树和森林
1 森林与二叉树的转换
六、树和二叉树的应用
1 Huffman 树
2 树的应用
§1 树结构
树型结构是一类重要的非线性结构。树型结构是结点之间有分支,并且具有层次关系的结构,它非常类似于自然界中的树。树结构在客观世界中是大量存在的。例如家谱、行政组织机构都可用树形象地表示。
树结构在计算机领域中也有着广泛的应用,例如在编译程序中,用树结构来表示源程序的语法结构;在数据库系统中,可用树结构来组织信息;在分析算法的行为时,可用树结构来描述其执行过程等等。
现实中,许多分层次的关系都可以看成树结构。
例如:1、行政隶属关系。
2、家族关系。
3、计算机中的文件管理器,资源管理器
等。
一、树的定义和基本术语
定义:树(Tree)是n(n≥0)个结点的有限集T。
当n = 0时,称T为空树。否则,它满足如下两个条件:
(1)、有且仅有一个特定的被称为根(Root)的结点;
(2)、其余的结点可分为m(m≥0)个互不相交的子集T1,T2,T3…Tm,其中每个子集Ti(1≤i≤m)又是一棵树,并称其为子树(Subtree)。
例如:
A
B
C
D
E
G
H
I
J
F
K
(b) 一般的树
树的示例
A
(a) 只有根结点的树
二、树的描述方法
1、形式化表示法
树是一种数据结构 T=(D, R)
其中:D是树中结点的集合,R是树中结点关系的集合。
当D={}时,即树中结点为空,则称T为空树;否则,设树T中有m棵子树:D={root}∪Df;
其中:root为树的树根结点;
Df = D1∪D2∪…∪ Dm∧Di∩Dj=∮∧(i≠j,1≤i,j≤m)
当树中结点个数n≤1时,则R={},否则有:
R={<root,Ri>,i =1,2,… m,Ri是根结点root的子树Ti的根结点}
2、树形表示法
该方法是借助于自然界中树的形态,用一棵倒置的树来表示,非常直观、
形象,人们易于接受和采用。
3、凹入表示法
如图(a)所示,该方法类似于书的编目,常用于树结构的打印和显示。
4、文氏表示法
利用集合和集合的包含关系来描述树结构。如图(b)所示。
5、广义表表示法
利用广义表来描述树结构。如图(c)所示。
A
B
F
G
C
D
H
J
I
K
E
(a)凹入表示法
C
A
B
E
D
K
F
G
H
J
I
(b)文氏表示法
A(B(F,G),C,D(H,I,J),E(K))
(c)广义表表示法
树的表示法示意
三、树的基本操作
1、建立一棵空树:InitialTree(T)
初始条件:无;
操作结果:构造一棵空树T。
2、  求树T的树根结点:RootTree(T)
初始条件:树T已经存在;
操作结果:返回树T的根。
3、  求树T中结点p的双亲:ParentTree(T,p)
初始条件:树T已经存在,且p是树T中的一个结点;
操作结果:若p不是树T的根结点,则返回结点p的双亲结点;否则,返回NULL、
4、求树T中结点p的最左边的孩子结点:LeftChildTree(T,p)
初始条件:树T已经存在,且p是树T中的一个结点;
操作结果:若p不是树T的叶子结点,则返回结点p的最左边孩子结点;否则,返回NULL。
5、  求树T中结点p的最右边的孩子结点:RightChildTree(T,p)
初始条件:树T已经存在,且p是树T中的一个结点;
操作结果:若p不是树T的叶子结点,则返回结点p的最右边孩子结点;否则,返回 NULL。
6、  判断树T是否为空:EmptyTree(T)
初始条件:树T已经存在;
操作结果:若树T为空,则返回True;否则,返回False。
7、求树T的深度:DepthTree(T)
初始条件:树T已经存在;
操作结果:返回树T的深度。
8、将结点p作为树T中结点q的第i棵子树插入:InsertTree(T,p,q,i)
初始条件:树T已经存在,q是树T中的结点,且1≤i≤q所指结点的度+1;
操作结果:将结点p作为树T中结点q的第i棵子树插入。
9、在树T中删除结点p的第i棵子树:DeleteTree(T,p,i)
初始条件:树T已经存在,p是树T中的结点,且1≤i≤p所指结点的度;
操作结果:在树T中删除结点p的第i棵子树。
10、按某种