文档介绍：第六章树和二叉树
树的定义和基本术语
二叉树
二叉树的定义
二叉树的性质
二叉树的存储结构
遍历二叉树和线索二叉树
遍历二叉树
线索二叉树
树和森林
树的存储结构
森林与二叉树的转换
赫夫曼树及其应用
最优二叉树(赫夫曼树)
第六章树和二叉树树的定义和基本术语
非线性数据结构。
树的递归定义:
树(tree)是n(n>=0)个结点的有限集。
当n>0时,
(1)有且仅有一个特定的称为根(root)的结点;
(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tm,其中每个集合本身又是一棵树。称为子树(subtree)。
树的示例
空树
n=0
层次
1
2
3
4
一般的树
A
B
C
D
E
F
G
H
I
J
K
L
只有根结点
的树 n=1
A
树的抽象数据类型定义:
ADT Tree{
数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:若D为空集,则称为空树;
若D仅含一个数据元素,则R为空集,否则R={H},H是如下二元关系:
(1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;
(2)若D-{root}≠φ,则存在D-{root}的一个划分D1, D2, ..., Dm (m>0),对任意j≠k(1≤j,k≤m)有Dj∩Dk=φ,且对任意的i(1≤i≤m),唯一存在数据元素xiξDi,有<root,xi>ξH;
(3)对应于D-{root}的划分,H-{<root,x1>,....,<root,xm>}有唯一的一个划分H1 , H2 ,..., Hm (m>0),对任意j≠k(1≤j,k≤m)有Hj∩Hk=φ,且对任意的i(1≤i≤m),Hi 是Di上的二元关系,(Di ,{Hi})是一棵符合本定义的树,称为根root的子树。
树的抽象数据类型定义:基本操作(之一)
INITTREE(&T);
操作结果:构造空树T。
DESTROYTREE(&T);
初始条件:树T存在。
操作结果:销毁树T。
CREATETREE(&T,DEFINITION);
初始条件:DEFINITION给出树T的定义。
操作结果:按DEFINITION构造树T。
CLEARTREE(&T);
初始条件:树T存在。
操作结果:将树T清为空树。
树的抽象数据类型定义:基本操作(之二)
TREEEMPTY(T)
初始条件:树T存在。
操作结果:若T为空树,则返回TURE,否则FALSE。
TREEDEPTH(T)
初始条件:树T存在。
操作结果:返回T的深度。
ROOT(T)
初始条件:树T存在。
操作结果:返回T的根。
VALUE(T, CUR_E);
初始条件:树T存在,CUR_E是T中某个结点。
操作结果:返回CUR_E的值。
树的抽象数据类型定义:基本操作(之三)
ASSIGN(T,CUR_E,VALUE)
初始条件:树T存在,CUR_E是T中某个结点。
操作结果:结点CUR_E赋值为VALUE。
PARENT(T,CUR_E)
初始条件:树T存在,CUR_E是T中某个结点。
操作结果:若CUR_E是T的非根结点,则返回它的双亲,否则函数值为“空”。
LEFTCHILD(T,CUR_E)
初始条件:树T存在,CUR_E是T中某个结点。
操作结果:若CUR_E是T的非叶子结点,则返回它的最左孩子,否则返回“空”。
RIGHTSIBLING(T,CUR_E)
初始条件:树T存在,CUR_E是T中某个结点。
操作结果:若CUR_E有右兄弟,则返回它的右兄弟,否则函数值为“空”。
树的抽象数据类型定义:基本操作(之四)
INSERTCHILD(&T,&P,I,C);
初始条件:树T存在,P指向T中某个结点,1≤I≤P所指结点的度+1,非空树C与T不相交。
操作结果:插入C为T中P指结点的第I棵子树。
DELETECHILD(&T,&P,I);
初始条件:树T存在,P指向T中某个结点,1≤I≤P指结点的度。
操作结果:删除T中P所指结点的第I棵子树。
TRAVERSETREE(T,VISIT());
初始条件:树t存在,VISIT是对结点操作的应用函数。
操作结果:按某种次序对T的每个结点调用函数VISIT()一次且至多一次。一旦VISIT()失败,则操作失败。
}ADT TREE
树的基本术语(之一)
子树(subtree)
结点
结点的度(degree)