5选讲树和二叉树解析.pptx
《5选讲树和二叉树解析.pptx》由会员分享,可在线阅读,更多相关《5选讲树和二叉树解析.pptx(41页珍藏版)》请在咨信网上搜索。
1、树和二叉树树和二叉树树和二叉树树和二叉树 预习检查预习检查v什么是二叉树v树的遍历有哪几种方式v树有那些应用2024/4/20 周六3 本章目标本章目标了解树的定义和基本术语了解树的定义和基本术语 了解二叉树的定义、性质、和存储结构了解二叉树的定义、性质、和存储结构掌握二叉树的遍历掌握二叉树的遍历本章结构本章结构树的逻辑结构和存储结构树的逻辑结构和存储结构树和二叉树树和二叉树二叉树遍历二叉树2024/4/20 周六5 5 5.1.1.1.1树型结构实例树型结构实例树型结构实例树型结构实例 1 1家族树家族树家族树家族树 5 5-1-1 树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和
2、存储结构树的逻辑结构和存储结构 图图图图5-15-1家族树家族树家族树家族树 2024/4/20 周六62 2书的目录结构书的目录结构书的目录结构书的目录结构 图图图图5-25-2书的目录书的目录书的目录书的目录 5 5-1-1 书的目录结构书的目录结构书的目录结构书的目录结构2024/4/20 周六7 5 5.1.1.2 2 树的定义树的定义树的定义树的定义 1 1树的定义树的定义 树树(Tree)Tree)是是n n(n(n0)0)个个结结点点的的有有限限集集(记记为为T)T),T T为为空空时时称称为为空空树树,否否则它满足以下两个条件:则它满足以下两个条件:(1)(1)有且仅有一个结点
3、没有前驱,称该结点为根结点有且仅有一个结点没有前驱,称该结点为根结点(Root)Root);(2)(2)除根结点以外,除根结点以外,其余结点可分为其余结点可分为m(mm(m0 0)个互不相交的有限集合个互不相交的有限集合T0T0,TlTl,Tm-1Tm-1。其中每个集合其中每个集合又构成一棵树,又构成一棵树,树树T0T0,Tl Tl,Tm-1Tm-1被被称为根结点的子树称为根结点的子树(Subree)Subree)。每棵子树的根结点有且仅有一个每棵子树的根结点有且仅有一个每棵子树的根结点有且仅有一个每棵子树的根结点有且仅有一个直接直接直接直接前驱,前驱,前驱,前驱,但可以有但可以有但可以有但可
4、以有0 0个或多个后继。个或多个后继。个或多个后继。个或多个后继。树的逻辑结构表示数据之间的关系是一对多,或者多对一的关系。树的逻辑结构表示数据之间的关系是一对多,或者多对一的关系。它的结构特点具有它的结构特点具有明显的层次关系,是一种十分重要的非线性的数据结明显的层次关系,是一种十分重要的非线性的数据结构。构。5 5-1-1 树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构 2024/4/20 周六8图图图图5-35-3树的示例树的示例树的示例树的示例 图图图图5-3(a)5-3(a)是一棵只有一个根结点的树;是一棵只有一个根结点的树;是一棵只有一个根
5、结点的树;是一棵只有一个根结点的树;图图图图5-35-3(b)(b)是是是是一一一一棵棵棵棵有有有有1212个个个个结结结结点点点点的的的的树树树树,即即即即T=AT=A,B B,C C,KK,LL。A A是是是是棵棵棵棵根根根根,除除除除根根根根结结结结点点点点A A之之之之外外外外,其其其其余余余余的的的的1111个个个个结结结结点点点点分分分分为为为为三三三三个个个个互互互互不不不不相相相相交交交交的的的的集集集集合合合合。T1T1T1T1,T2T2T2T2和和和和T3T3T3T3是是是是根根根根A A A A的的的的三三三三棵棵棵棵子子子子树树树树,且且且且本本本本身身身身又又又又都都
6、都都是是是是一一一一棵棵棵棵树。树。树。树。所以树的所以树的所以树的所以树的定义定义是递归的是递归的是递归的是递归的 。2024/4/20 周六92 2 2 2树的基本术语树的基本术语树的基本术语树的基本术语 树的结点包含一个数据元素及若干指向其子树的分支。树的结点包含一个数据元素及若干指向其子树的分支。树的结点包含一个数据元素及若干指向其子树的分支。树的结点包含一个数据元素及若干指向其子树的分支。1.1.树的结点树的结点:包含一个包含一个DEDE和指向其子树的所有分支和指向其子树的所有分支;2.2.结点的度结点的度:一个结点拥有的子树个数一个结点拥有的子树个数,度为零的结点称为度为零的结点称
7、为叶结点叶结点;3.3.树的度树的度:树中所有结点的度的最大值树中所有结点的度的最大值 Max(D(I)Max(D(I)含义含义:树中最大分支数为树的度树中最大分支数为树的度;4.4.结点的层次及树的深度结点的层次及树的深度:根为第一层根为第一层,根的孩子为第二层根的孩子为第二层,若某结若某结点为第点为第k k层层,则其孩子为则其孩子为k+1k+1层层.树中结点的最大层次称为树中结点的最大层次称为树的深度树的深度或高度或高度5.5.森林森林:是是m(m=0)m(m=0)棵互不相的树的集合棵互不相的树的集合 森林与树概念相近森林与树概念相近,相互很容易转换相互很容易转换.6.有序树、无序树有序树
8、、无序树 如果树中每棵子树从左向右的排列拥有一定的如果树中每棵子树从左向右的排列拥有一定的顺序,不得互换,则称为有序树,否则称为无序树。顺序,不得互换,则称为有序树,否则称为无序树。2024/4/20 周六107.7.森林森林:是是m m(m0m0)棵互不相交的树的集合。棵互不相交的树的集合。在树结构中,结点之间的关系又可以用家族关系描述,定义如下:在树结构中,结点之间的关系又可以用家族关系描述,定义如下:8.8.孩子、双亲孩子、双亲:结点子树的根称为这个结点的孩子,而这个结点又结点子树的根称为这个结点的孩子,而这个结点又被称为孩子的双亲。被称为孩子的双亲。9.9.子孙子孙:以某结点为根的子树
9、中的所有结点都被称为是该结点的子以某结点为根的子树中的所有结点都被称为是该结点的子孙。孙。10.10.祖先祖先:从根结点到该结点路径上的所有结点。从根结点到该结点路径上的所有结点。11.11.兄弟兄弟:同一个双亲的孩子之间互为兄弟。同一个双亲的孩子之间互为兄弟。12.12.堂兄弟堂兄弟:双亲在同一层的结点互为堂兄弟。双亲在同一层的结点互为堂兄弟。2024/4/20 周六113.3.树的基本运算树的基本运算树的基本运算树的基本运算树的基本运算主要有:树的基本运算主要有:初始化操作初始化操作INITIATE(T)INITIATE(T):创建一棵空树。创建一棵空树。求根函数求根函数ROOT(T)RO
10、OT(T):求树求树T T的根;的根;ROOT(X)ROOT(X):求结点求结点x x所在树的所在树的根。根。求双亲函数求双亲函数PARENT(T,x)PARENT(T,x):在树在树T T中求中求x x的双亲。的双亲。求第求第i i个孩子函数个孩子函数CHILD(T,x,i)CHILD(T,x,i):在树在树T T中求结点中求结点x x的第的第i i个孩个孩子。子。建树函数建树函数CRT-TREE(x,F)CRT-TREE(x,F):建立以结点建立以结点x x为根,森林为根,森林F F为子树为子树的树。的树。6.6.遍历树操作遍历树操作TRAVERSE(T)TRAVERSE(T):按顺序访问
11、树按顺序访问树T T中各个结点。中各个结点。2024/4/20 周六121 1树的遍历树的遍历树的遍历树的遍历 所所所所谓谓谓谓树树树树的的的的遍遍遍遍历历历历,就就就就是是是是按按按按照照照照某某某某种种种种顺顺顺顺序序序序依依依依次次次次访访访访问问问问树树树树中中中中各各各各个个个个结结结结点点点点,并并并并使使使使得得得得每每每每个个个个结结结结点点点点只只只只被被被被访访访访问问问问一一一一次次次次。也也也也就就就就是是是是把把把把非非非非线线线线性性性性结结结结构构构构的的的的树树树树结结结结点点点点变变变变成成成成线性序列的一种方式线性序列的一种方式线性序列的一种方式线性序列的一
12、种方式 。树树树树的的的的遍遍遍遍历历历历可可可可以以以以按按按按深深深深度度度度优优优优先先先先遍遍遍遍历历历历,也也也也可可可可以以以以按按按按照照照照广广广广度度度度优优优优先先先先(按按按按层层层层次)遍历。深度优先遍历通常有两种方式:次)遍历。深度优先遍历通常有两种方式:次)遍历。深度优先遍历通常有两种方式:次)遍历。深度优先遍历通常有两种方式:前序前序前序前序遍历和遍历和遍历和遍历和后序后序后序后序遍历。遍历。遍历。遍历。(1)(1)前序遍历的递归定义:前序遍历的递归定义:前序遍历的递归定义:前序遍历的递归定义:若树若树若树若树T T T T非空,则:非空,则:非空,则:非空,则:
13、访问根结点访问根结点访问根结点访问根结点R R;按按按按照照照照从从从从左左左左到到到到右右右右的的的的顺顺顺顺序序序序依依依依次次次次前前前前序序序序遍遍遍遍历历历历根根根根结结结结点点点点R R的的的的各各各各子子子子树树树树T T1 1,T T2 2,T Tk k。5 5-1-5-1-5 树的遍历树的遍历树的遍历树的遍历2024/4/20 周六13(2)(2)(2)(2)后序遍历的递归定义:后序遍历的递归定义:后序遍历的递归定义:后序遍历的递归定义:若树若树若树若树T T T T非空,则:非空,则:非空,则:非空,则:按照从左到右的顺序依次后序遍历根按照从左到右的顺序依次后序遍历根按照从
14、左到右的顺序依次后序遍历根按照从左到右的顺序依次后序遍历根T T T T的各子树的各子树的各子树的各子树T T T Tl l l l,T T T T2 2 2 2,T T T Tk k k k;访问根结点访问根结点访问根结点访问根结点R R。(3)(3)(3)(3)广度优先(按层)遍历广度优先(按层)遍历广度优先(按层)遍历广度优先(按层)遍历广广广广度度度度优优优优先先先先(按按按按层层层层次次次次)遍遍遍遍历历历历定定定定义义义义为为为为:先先先先访访访访问问问问第第第第一一一一层层层层结结结结点点点点(即即即即树树树树根根根根结结结结点点点点),再再再再从从从从左左左左至至至至右右右右访
15、访访访问问问问第第第第二二二二层层层层结结结结点点点点,依依依依次次次次按按按按层层层层访访访访问问问问,直直直直到到到到树树树树中中中中结结结结点点点点全全全全部部部部被被被被访访访访问问问问为为为为止止止止。对对对对图图图图6-66-6(a)a)中中中中的的的的树树树树进进进进行行行行按按按按层层层层次次次次遍遍遍遍历历历历得得得得到到到到树树树树的的的的广广广广度度度度优优优优先先先先遍遍遍遍历历历历序序序序列为:列为:列为:列为:ABCDEFGABCDEFG。说明:说明:说明:说明:前前前前序序序序遍遍遍遍历历历历一一一一棵棵棵棵树树树树恰恰恰恰好好好好等等等等价价价价于于于于前前前前
16、序序序序遍遍遍遍历历历历该该该该树树树树所所所所对对对对应应应应的的的的二二二二叉叉叉叉树树树树。(6.26.2节节节节将介绍二叉树)将介绍二叉树)将介绍二叉树)将介绍二叉树)后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。2024/4/20 周六14树的先序遍历算法描述如下:树的先序遍历算法描述如下:树的先序遍历算法描述如下:树的先序遍历算法描述如下:voidPreorder(Btree*root)/先根遍历先根遍历k叉树叉树if(root!=NUL
17、L)printf(“%cn”,root-data);/访问根结点访问根结点for(i=0;iti);/递归前序遍历每一个子结点递归前序遍历每一个子结点2024/4/20 周六15 5 5.2.1.2.1.2.1.2.1二叉树的定义与性质二叉树的定义与性质二叉树的定义与性质二叉树的定义与性质 二叉树二叉树(Binary Tree)Binary Tree)是另一种重要的树型结构。是度为是另一种重要的树型结构。是度为2 2的的有序树,它的特点是每个结点至多有两棵子树。和树结构的定义有序树,它的特点是每个结点至多有两棵子树。和树结构的定义类似,二叉树的定义也可以用递归形式给出。类似,二叉树的定义也可以
18、用递归形式给出。1 1 1 1二叉树的递归定义二叉树的递归定义二叉树的递归定义二叉树的递归定义 二二叉叉树树(BinaryTree)BinaryTree)是是n(nn(n0)0)个个结结点点的的有有限限集集。它它或或者者是是空空集集(n=0)n=0),或者同时满足以下两个条件:或者同时满足以下两个条件:(1)(1)有且仅有一个根结点;有且仅有一个根结点;(2)(2)其余的结点分成两棵互不相交的左子树和右子树。其余的结点分成两棵互不相交的左子树和右子树。5 5-2 2 二叉树二叉树二叉树二叉树2024/4/20 周六16 二二叉叉树树与与树树有有区区别别:树树至至少少应应有有一一个个结结点点,而
19、而二二叉叉树树可可以以为为空空;树树的的子子树树没没有有顺顺序序,但但如如果果二二叉叉树树的的根根结结点点只只有有一一棵棵子子树树,必必须须明明确确区区分分它它是是左左子子树树还还是是右右子子树树,因因为为两两者者将将构构成成不不同同形形态态的的二二叉叉树树。因因此此,二二叉树不是树的特例。它们是两种不同的数据结构。叉树不是树的特例。它们是两种不同的数据结构。二叉树有二叉树有5 5种基本形态:种基本形态:图图图图5-75-7二叉树的五种基本形态二叉树的五种基本形态二叉树的五种基本形态二叉树的五种基本形态(a)a)a)a)空二叉树空二叉树空二叉树空二叉树 (b)b)b)b)只有根结点的二叉树只有
20、根结点的二叉树只有根结点的二叉树只有根结点的二叉树(c)c)c)c)右子树为空的二叉树右子树为空的二叉树右子树为空的二叉树右子树为空的二叉树 (d)d)左子树为空的二叉树左子树为空的二叉树左子树为空的二叉树左子树为空的二叉树(e)e)左右子树均不为空的二叉树左右子树均不为空的二叉树左右子树均不为空的二叉树左右子树均不为空的二叉树 2024/4/20 周六17两种特殊形态的二叉树两种特殊形态的二叉树:满二叉树和完全二叉树。满二叉树和完全二叉树。满二叉树和完全二叉树。满二叉树和完全二叉树。(1)(1)满二叉树满二叉树(FullBinaryTree)FullBinaryTree)深度为深度为k k,
21、且有且有2 2k k-1-1个结点的个结点的二叉树二叉树。特点:(特点:(1 1)每一层上结点数都达到最大)每一层上结点数都达到最大 (2 2)度为)度为1 1的结点的结点n n1 1=0=0,树叶都在最下一层上。树叶都在最下一层上。结点层序编号方法:从根结点起从上到下逐层(层内从左到右)对二叉树的结点层序编号方法:从根结点起从上到下逐层(层内从左到右)对二叉树的结点进行连续编号。结点进行连续编号。1237654K=3n=23-1=7 满二叉树2024/4/20 周六18 (2)(2)完全二叉树完全二叉树(Complete BinaryTree)Complete BinaryTree)深度为深
22、度为k k,结点数为结点数为n n的二叉树,当且仅当每个结点的编号都与相同深的二叉树,当且仅当每个结点的编号都与相同深度的满二叉树中从度的满二叉树中从1 1到到n n的结点一一对应时,称为完全二叉树。的结点一一对应时,称为完全二叉树。图图5-8 5-8 完全二叉树完全二叉树完全二叉树的特点:完全二叉树的特点:(1 1)每个结点)每个结点i i的左子树的深度的左子树的深度LhLhi i-其结点其结点i i的右子树的深度的右子树的深度RhRhi i等等于于0 0或或1 1,即叶结点只可能出现在层次最大或次最大的两层上。,即叶结点只可能出现在层次最大或次最大的两层上。(2 2)完全二叉树结点数)完全
23、二叉树结点数n n满足满足2 2k-1k-1-1-1n2n2k k-1-1(3 3)满二叉树一定是完全二叉树,反之不成立。满二叉树一定是完全二叉树,反之不成立。452132024/4/20 周六191324653241LH1=3RH1=1LH1-RH1=2 非完全二叉树非完全二叉树非完全二叉树非完全二叉树LHLH2 2=0=0RHRH2 2=1=1LH2-RH2=0-1=-12024/4/20 周六202 2 2 2二叉树的性质二叉树的性质二叉树的性质二叉树的性质 性质性质1 1 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1 i-1 个结点个结点(i1)i1)。性质性质2 2
24、 深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点(k1)k1)。(深度一定,二叉树的最大结点数也确定)深度一定,二叉树的最大结点数也确定)性质性质3 3 二叉树中二叉树中,终端结点数终端结点数n n0 0与度为与度为2 2的结点数的结点数n n2 2有如下关系有如下关系:n n0=0=n n2 2+1+1 性质性质4 4 结点数为结点数为n n的完全二叉树,其深度为的完全二叉树,其深度为 loglog2 2n n +l+l 性质性质5 5 在按层序编号的在按层序编号的n n个结点的完全二叉树中,任意一结点个结点的完全二叉树中,任意一结点i(1in)i(1in)有
25、:有:i=1i=1时,结点时,结点i i是树的根;否则是树的根;否则,结点结点i i的双亲为结点的双亲为结点 i/2i/2 (i1)i1)。2i 2in n时,结点时,结点i i无左孩子,为叶结点;否则,结点无左孩子,为叶结点;否则,结点i i的左孩子为结的左孩子为结点点2 2i i。2i+1 2i+1n n时,结点时,结点i i无右孩子;否则,结点无右孩子;否则,结点i i的右孩子为结点的右孩子为结点2 2i+1i+1。2024/4/20 周六21链式存储结构链式存储结构链式存储结构链式存储结构 (二叉链表)二叉链表)设计不同的结点结构,可以构成不同的链式存储结构。常用的有:设计不同的结点结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 选讲树 二叉 解析
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。