第6章(树和二叉树).ppt

第6章(树和二叉树).ppt

ID:61905867

大小:1.62 MB

页数:106页

时间:2021-03-26

第6章(树和二叉树).ppt_第1页
第6章(树和二叉树).ppt_第2页
第6章(树和二叉树).ppt_第3页
第6章(树和二叉树).ppt_第4页
第6章(树和二叉树).ppt_第5页
资源描述:

《第6章(树和二叉树).ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用树型结构是一类重要的非线性结构。树结构在客观世界里是大量存在的,树在计算机领域中也有着广泛的应用。6.1树的定义和基本术语1、定义树是n(n>=0)个结点的有限集T,T为空时称为空树, 否则它满足如下两个条件:(1)有且仅有一个特定的称为根的结点;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,T3,…,Tm,其中每个子集又是一棵树,并称其为根的子树。A只有根结点的树ABCDEFGHIJKLM有子树的树根子树结点——表示树中的

2、元素,包括数据项及若干指向其子树的分支2、基本术语结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点的子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的双亲兄弟(sibling)——同一双亲的孩子树的度——一棵树中各结点的度的最大值结点的层次(level)——从根结点算起,根为第一层,它的孩子为第二层……深度(depth)——树中结点的最大层次数森林(forest)——m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度:3结点B的度:2结点M的度:0叶子:K,L,F,G

3、,M,I,J结点A的孩子:B,C,D结点B的孩子:E,F结点I的双亲:D结点L的双亲:E结点B,C,D为兄弟结点K,L为兄弟树的度:3结点A的层次:1结点M的层次:4树的深度:4结点F,G为堂兄弟结点A是结点F、G的祖先2、基本术语6.2二叉树二叉树在树结构的应用中起着非常重要的作用,因为针对二叉树的许多操作算法简单,而任何树都可以与二叉树相互转换,这样就解决了树的存储结构及其运算中存在的复杂性。二叉树是由n(n>=0)个结点的有限集合构成,此集合或者为空集,或者由一个根结点及两棵互不相交的左右子树组成,并且左右子树也都是二叉树。这也是一个递归定义。二叉树可以是空集

4、合,根也可以有空的左子树或空的右子树。(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树二叉树的5种基本形态二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也要进行区分,说明它是左子树,还是右子树。这是二叉树与树的最主要的差别。6.2.1二叉树的定义6.2.2二叉树的性质二叉树具有下列重要性质:性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)。采用归纳法证明此性质。当i=1时,只有一个根结点,2i-1=21-1=20=1,命题成立。现在假定对所有的j,1≤j<i,命题成立,即第j层上至多有2j-1个结

5、点,那么需要证明当j=i时命题也成立。由归纳假设可知,第i-1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2,故在第i层上最大结点数为第i-1层上最大结点数的2倍,即2×2i-2=2i-1。命题得到证明。性质2:深度为k的二叉树至多有2k-1个结点(k≥1)。深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和,由性质1得到每层上的最大结点数,性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的 结点数为n2,则n0=n2+1。设二叉树中度为1的结点数为n1,二叉树中总结点数为N,因为二叉树中所有结点的度均小于或等于2,所以有:N=n0+

6、n1+n2(6-1)再看二叉树中的分支数,除根结点外,其余结点都有一个进入分支,设B为二叉树中的分支总数,则有:N=B+1由于这些分支都是由度为1和2的结点射出的,所以有:B=n1+2n2因此,N=B+1=n1+2n2+1(6-2)由式(6-1)和(6-2)得到:n0+n1+n2=n1+2n2+1可得n0=n2+1性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的 结点数为n2,则n0=n2+1。满二叉树2453671一棵深度为k且有2k-1个结点的二叉树称为满二叉树。下面就是一棵满二叉树,并对结点进行了顺序编号。下面介绍两种特殊形态的二叉树:满二叉树和完

7、全二叉树。123456(a)完全二叉树123457(b)非完全二叉树12367(c)非完全二叉树如果深度为k、有n个结点的二叉树中的每个结点能够与深度为k的顺序编号的满二叉树从1到n编号的结点相对应,则称这样的二叉树为完全二叉树。满二叉树是完全二叉树的特例。完全二叉树的特点(1)所有的叶结点都出现在第k层或第k-1层。(2)对任一结点,若其右分支下的子孙的最大层次为l,则其左分支下的子孙的最大层次必为l或l+1。性质4:具有n个结点的完全二叉树的深度为log2n+1。符号x表示不大于x的最大整数。假设此二叉树的深度为k,则根据性质2及完全二叉树的定义得:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。