文档介绍：第6章树和二叉树
本章主题:树、二叉树
教学目的:掌握树和二叉树的类型定义、运算及存储结构
教学重点:树的各种表示、各种存储方式和运算,
二叉树的概念及其运算和应用
教学难点:二叉树的非递归运算及应用
主要内容:树二叉树
树、森林与二叉树的转换
树的应用
2017/12/5
1
本章学习导读
本章主要介绍树的基本概念,树的存储结构,树和二叉树的遍历等一些常用算法。通过本章学习,读者应该:
1) 熟练掌握二叉树的各种遍历算法,并能灵活运用遍历算法实现二叉树的其它操作。
2) 理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。
3) 熟练掌握二叉树和树的各种存储结构及建立的算法。
4) 学会编写实现树的各种操作的算法。
5)了解最优二叉树的特性,掌握建立最优二叉树和哈夫曼编码的方法。
2017/12/5
2
数据结构:线性结构和非线性结构
线性结构(线性表, 栈,队列等)
非线性结构: 至少存在一个数据元素有不止一个直接前驱或后继(树,图等)
树型结构是一类重要的非线性结构。树型结构是结点之间有分支,并且具有层次关系的结构,它非常类似于自然界中的树。树结构在客观世界国是大量存在的,例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程。等等。
2017/12/5
3
.1 树型结构实例
树的逻辑结构和存储结构
图6-1 家族树
2017/12/5
4
图6-2 书的目录
2017/12/5
5
.2 树的定义
树(Tree)是n (n≥0)个结点的有限集(记为T),T为空时称为空树,否则它满足以下两个条件:
(1) 有且仅有一个结点没有前驱,称该结点为根结点(Root);
(2) 除根结点以外,其余结点可分为m(m≥0)个互不相交的有限集合T0,Tl,…,Tm-1。其中每个集合又构成一棵树,树T0,Tl ,…,Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个后继。
树的逻辑结构表示数据之间的关系是一对多,或者多对一的关系。它的结构特点具有明显的层次关系,是一种十分重要的非线性的数据结构。
树的逻辑结构和存储结构
2017/12/5
6
图6-3 树的示例
图6-3 (a)是一棵只有一个根结点的树;
图6-3 (b)是一棵有12个结点的树,即T={A,B,C,…,K,L }。A是棵根,除根结点A之外,其余的11个结点分为三个互不相交的集合。T1,T2和T3是根A的三棵子树,且本身又都是一棵树。所以树的定义是递归的。
返回
2017/12/5
7
树的结点包含一个数据元素及若干指向其子树的分支。
1. 树的结点:包含一个DE和指向其子树的所有分支;
2. 结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点;
3. 树的度:树中所有结点的度的最大值 Max(D(I))
含义:树中最大分支数为树的度;
4. 结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.
树中结点的最大层次称为树的深度或高度
:是m(m>=0)棵互不相的树的集合
森林与树概念相近,相互很容易转换.
6 .有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序,不得互换,则称为有序树,否则称为无序树。
2017/12/5
8
: 是m(m≥0)棵互不相交的树的集合。
在树结构中,结点之间的关系又可以用家族关系描述,定义如下:
、双亲: 结点子树的根称为这个结点的孩子,而这个结点又被称为孩子的双亲。
: 以某结点为根的子树中的所有结点都被称为是该结点的子孙。
: 从根结点到该结点路径上的所有结点。
: 同一个双亲的孩子之间互为兄弟。
: 双亲在同一层的结点互为堂兄弟。
2017/12/5
9
3. 树的基本运算
树的基本运算主要有:
⒈初始化操作INITIATE(T):创建一棵空树。
⒉求根函数ROOT(T):求树T的根;ROOT(X):求结点x所在树的根。
⒊求双亲函数PARENT(T,x):在树T中求x的双亲。
⒋求第i个孩子函数CHILD(T,x,i):在树T中求结点x的第i个孩子。
⒌建树函数CRT-TREE(x,F):建立以结点x为根,森林F为子树的树。
(T):按顺序访问树T中各个结点。