数据结构(非线性结构)讲解

《数据结构(非线性结构)讲解》由会员分享，可在线阅读，更多相关《数据结构(非线性结构)讲解（228页珍藏版）》请在金锄头文库上搜索。

1、2019/11/7,1,2.5 树和二叉树 树型结构是一类很重要的非线性数据结构，在这类结构中，元素之间存在分支和层次关系。 如：家谱、章节划分、多级目录结构、单位组织结构。(1:m),内容:树和二叉树的定义、术语、存储结构、基本性质。 重点:二叉树。 二叉树的算法特点:递归调用。 遍历算法是所有算法的基础。,2019/11/7,2,2.5.1 树的定义及其存储结构,1、树的定义和术语(看图说明),倒长树； 前件、后件。,2019/11/7,3,树是由n个结点（n0）组成的有限集合T。其中有且仅有一个结点称为根结点（root）。其余结点可以分为m（ m0 ）个互不相交的有限集合T1，T2，Tm

2、，其中每一个集合Ti本身又是一棵树，称为root的子树。当n=0时称为空树。 递归描述 在描述树时又用到子树(与树具有相同定义)本身这个术语。,2019/11/7,4,用二元组关系定义树：-(本教材的优点,难点)严密、难懂 Tree=(T,R) 树由数据元素集合T及关系R组成，其中T是具有相同类型的数据元素集合T=x1,x2, ,xn。若T=,则R= ,称为空树。否则R是T上某个二元关系H的集合，即R=H。H的描述为： （1）在T中存在唯一的称为根的元素root，它在H关系下无前趋。 （2）若T-root ，则存在m个子集T1，T2，Tm(m0)，对任意的jk(1j,km),有TjTk= 。且

3、存在唯一的数据元素xiTi (1im)，满足 H。 （3）对应于T1，T2，Tm ，H-, ,划分为m个子集H1,H2, Hm(m0)，对任意的jk(1j,km)，有HjHk= ，Hi满足在Ti上的二元关系。因此(Ti,Hi)也是一棵符合本定义的树，称为根root的子树。,2019/11/7,5,术语(充分了解树的术语)： 结点(node): 树中的元素。 结点的度(degree): 结点拥有的子树数。一棵树中最大的结点度数为这棵树的度。 叶子(leaf): 度为零的结点，又称端结点,叶结点。 孩子(child): 除根结点外，每个结点都是其前趋结点的孩子。 双亲(parents): 孩子结点

4、的上层结点称为这些结点的双亲。-1:m 兄弟(sibling): 同一双亲的孩子。 结点的层次(level): 从根结点开始算起，根为第一层，根的直接后继结点为第二层，其余各层依此类推。 深度(depth): 树中结点的最大层次数。 森林(forest): 是m(m0)棵互不相交的树的集合。 有序树：树中结点在同层中按从左至右有序排列，不能互换的称为有序树-二叉排序树，反之称为无序树。,2019/11/7,6,深度层数 度数子树数,2019/11/7,7,补充内容(自己拓展)表达式树：在计算机中可用树结构来表示算术表达式。 算术表达式组成： 运算符 单目() 双目(、 、)二叉分支 多目函数运

5、算符, 如 f(x,y,z)K叉分支 运算对象 单变量 子表达式 规则： 运算符对应结点，称为运算符结点； 运算符的每个运算对象为该运算符结点的子树，从左到右； 运算对象中的单变量均为叶子结点。 方法：自底向上 不唯一 例：a(b+c/d)+e h-g f(s,t,x+y),2019/11/7,8,-,+,*,*,*,a,+,b,/,c,d,e,h,g,f,s,t,+,x,y,2019/11/7,9,2、树的存储结构,由于树为非线性结构,除特形树之外,一般都采用链式存储结构. 链式存储结构：因树是多分支非线性表，所以需采用多重链表结构，即每个结点设多个指针域，其中每一个指针指向一棵子树的根结点

6、。 种类 结点异构型：根据每个结点的子树数设置相应的指针域。度数不同，结点的结构不同。 同构型：每个结点的指针域个数均为树的度数。 优缺点 n个结点,k叉树，则有nk个指针域，有用的指针域有n-1个，空链域个数为nk-(n-1) =n(k-1)+1个。,2019/11/7,10,对不同的k值进行比较：,结论：k越大空链域所占比例越大，k=2时最小。着重讨论二叉树。,书中错误,K不可能取无穷大值,2019/11/7,11,2.5.2 二叉树及其性质,1、二叉树定义及其存储结构 定义：二叉树是n(n 0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的

7、二叉树(子树亦为二叉树)构成。 用二元组关系定义二叉树B_T: B_T=(D,R) 其中D是相同类型元素的集合D=x1,x2, ,xn。若D=,则R= ,称为空二叉树。否则R是D上某个二元关系H的集合，即R=H。H的描述为： （1）在D中存在唯一的称为根的元素r，它在H关系下无前趋。 （2）若D-r ，则D-r=DL,DR，且DLDR = 。 （3）若DL ,则DL中存在唯一元素xL，满足 H，且存在DL上关系HLH；若DR ,则DR中存在唯一元素xR，满足H，且存在DR上关系HRH；因此，H=,HL,HR。,2019/11/7,12,(4)(DL,HL)是一棵符合本定义的二叉树，称为根r的左

8、子树；(DR , HR)是一棵符合本定义的二叉树，称为根r的右子树； 存储结构(同构型)：,具有两个指针域的链表：左、右指针域和数据域。,2019/11/7,13,注意：二叉树的结点的子树有左右之分,两者不能互换。,2、二叉树的基本性质 （1）二叉树的第i层上至多有2i-1(i 1)个结点。 (归纳法) （2）深度为h的二叉树中至多含有2h-1个结点。 (证明：利用（1）),2019/11/7,14,（3）在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则n0=n2+1。,证明： 设n1为度为1的结点数，则总结点数为n: n=n0+n1+n2 除根结点外，每个结点都由一条分支与其双亲相

9、连，则指针数b(树中的弧的数量)满足：b=n-1 b又可以看作由度为1和2的结点与它们孩子之间的联系： b=n1+2n2 则：n0=n2+1 指针数: 结点与其双亲(); 双亲与其孩子().,2019/11/7,15,(4)具有n个结点的二叉树，其深度至少为log2n+1。 注意:不是log2(n+1) 由性质(2)反推. 结点数最多深度最小,2019/11/7,16,3、几种特殊形式的二叉树,（1）满二叉树 深度为h且含有2h-1个结点的二叉树。 结点编号从上到下，从左到右。,2019/11/7,17,（2）完全二叉树,如果一棵有n个结点的二叉树，按从上到下，从左到右方式对结点编号，若树中n

10、个结点和满二叉树1n编号完全一致，则该树称为完全二叉树。,2019/11/7,18,完全二叉树的性质(补充)：,（1）具有n个结点的完全二叉树，其深度为log2n+1。 （2）设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，n给结点编号，则对于编号为k的结点有以下结论： 若k=1,则该结点为根结点；若k1，则该结点的父结点编号为k/2。 若2kn，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点。 若2k+1n，则编号为k的结点的右子结点编号为2k，否则该结点无右子结点。 树和线性表 的关系,2019/11/7,19,2019/11/7,20,（3

11、）平衡二叉树,它或者是一棵空树，或者是具有下列性质的二叉树： 它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。 结点的平衡因子：结点的左子树和右子树的深度之差。-1、0、1（所有结点）,2019/11/7,21,4、一般树转换为二叉树,引出：为了使一般树也能像二叉树一样用二叉链表表示，必须找出树与二叉树的对应关系，且一一对应。 对于一般树，树中结点的次序没有要求，但为了得到对应该树的二叉树表示，则需要对树中每个孩子结点进行从左到右的排序。 转换方法： （1）在兄弟结点之间加一连线； （2）对每个结点，除了与它的第一个孩子保持联系外，去除与其它孩子的联系。 （3）以

12、树根为轴心，将整棵树顺时针旋转45度。 特性：任何一棵树转换成的二叉树，其右子树必空。,2019/11/7,22,作平行线法:撇,捺和平行。右子树为空的二叉树,2019/11/7,23,练习：2.28,2019/11/7,24,2.5.3 二叉树的遍历,遍历(traversing)：指循某条搜索路线，依次访问某数据结构中的全部结点，且每个结点只被访问一次。 线性表结构：顺序扫描每个结点元素即可。 非线性表结构：需人为设定搜索路径。 1、遍历二叉树的定义 一棵非空二叉树由根结点、左子树和右子树组成。 以D,L,R分别表示访问根结点、遍历左子树和遍历右子树。 规定先左后右。 则搜索路径种类： DL

13、R：先序遍历 LDR：中序遍历 LRD：后序遍历 因二叉树是递归定义的，所以也用递归方式描述二叉树的遍历。 先序遍历：先访问根结点，然后先序遍历左子树，再先序遍历右子树。,2019/11/7,25,说明：用不同的遍历方式对同一棵二叉树进行遍历，可以得到不同的结点序列。 例,反之:已知遍历序列,画出树?中序+先(后)序,2019/11/7,26,2、遍历算法,P是指向当前遍历二叉树的根结点指针，语句write表示访问当前遍历的结点。 PREORDER(p) 1.if(pnil) then 2.write(data(p); 3. PREORDER(L child(p);/先序遍历左子树 4. PR

14、EORDER(R child(p); 5.return 中序遍历、后序遍历类同。 二叉树的各种操作： 遍历是二叉树的各种操作的基础，如： （1）求二叉树中叶子数； （2）求结点的双亲； （3）求结点的孩子； （4）判断结点所在的层次； （5）计算二叉树的深度。,递归调用,2019/11/7,27,例：计算二叉树中叶子数,COUNTLEAF(p,count)/p指向根结点，count为计数器/ 1.if(p nil) then 2.if(L child(p)=nil)and(R child(p)=nil) 3. then countcount+1 4. COUNTLEAF(L child(p),

15、count); 5 COUNTLEAF(R child(p),count) 6.return(count) 遍历算法分析： 在遍历二叉树的算法中，基本操作是访问结点，因此不论按哪一种次序进行遍历，对含有n个结点的二叉树来说，其时间复杂度均为O(n)。,2019/11/7,28,DEPTH(p,d) If(p=nil) then d0 Elsedepth(L child(p),d); d1 d depth(R child(p),d) d max(d1,d)+1 return,2019/11/7,29,练习：,2.30 试说明为什么由二叉树的中序和前序（后序）遍历序列可以唯一确定一棵二叉树，而由前

16、序和后序遍历则不能。,2019/11/7,30,2.5.4 二叉树的应用,二叉树是树型结构的一种基本形态,应用广泛. 内容：二叉排序树、哈夫曼树。 1、二叉排序树(树表)结点的数据值的大小关系 一种表的组织手段，查找,排序法之一 （1）定义：二叉排序树或是空树，或是具有下列性质的二叉树：其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值。左子树和右子树又各是一棵二叉排序树。 递归定义、中序搜索，从小到大。在排序中应用很广。,2019/11/7,31,例,举例一棵深度不小于4的二叉排序树； 用1-15这16个自然数编号的结点形成一棵深度为4的二叉排序树. 树的退化. 方法:从下向上,依左、根、右顺序,从小到大编号.,2019/11/7,32,（2）二叉