第四章-树(数据结构word版课件).doc
《第四章-树(数据结构word版课件).doc》由会员分享,可在线阅读,更多相关《第四章-树(数据结构word版课件).doc(96页珍藏版)》请在咨信网上搜索。
1、第四章 树4.1 树的基本概念直观地说,树是按分支关系将数据连接起来的数据结构,就像自然界中的具有树杈分支的树一样。4.1.1 树的定义为方便计,有时常将“树”称之为“树形”,或“树形结构”。定义4.11 一个树(或树形)就是一个有限非空的结点集合T,其中:1 有一个特别标出的被称为该树(或树形)之根root(T)的结点;2 其余结点被分成m 0 个不相交的集合T1, T2, , Tm,且T1, T2, , Tm又都是树(或树形)。树(或树形)T1, T2, , Tm被称作root(T)的子树(或子树形)。上面给出的定义是递归的,就是说用树来定义树。树形的递归定义似乎是更合适的,因为递归是树形
2、结构的固有特征。在自然界中可观察到,树上的幼芽可长成为具有自己的幼芽的子树,树长出子树,子树又长出它的子树(子树的子树)。图4.1(a)是一棵根结点为A的树,由定义4.1可知,该树中除结点A之外的每个结点,又都是该树中某个子树的根。图4.1 (a) 树AECDBIHGF为了从另外一个角度来理解树结构的概念,我们给出了树的非递归定义。定义4.2 树是包含n ( n 1 )个结点且满足如下条件的有限集合:1) 存在一个唯一的结点v0,它没有前驱结点,称为树的根(或根结点);2) 任何非根结点都有且仅有一个前驱结点,称为该结点的父结点;3) 任何结点都可能有多个( n-1)后继结点,称之为该结点的子
3、结点;若某结点没有后继结点,则称之为叶结点。4) 任一非根结点vk都有且仅有一条从根节点v0到该结点的结点序列(或曰路径)v0 v1 vk,其中vi是vi-1的子结点(1 i k)。如对于图4.1(a)中的结点F来说,存在唯一一条从根结点A到它的结点序列ABEF;对于结点H,存在唯一一条从根结点A到它的结点序列ACH .图4.1 (a) 树AECDBIHGF4.1.2 树的相关术语1度一个结点的子结点的数目,称为该结点的度或者次数。一棵树的度为maxi=1, n D (i),其中n为树中结点总数,i指树中的第i个结点,D(i)表结点i的度。2叶结点、分支结点度为0的结点被称为叶结点;度 0的结
4、点被称为分支结点。在图4.1(a)中: B有一个子结点E,度为1;A有三个子结点B、C和D(换言之,A是B、C和D的父结点),度为3,故这棵树的度也为3 .图4.1 (a) 树AECDBIHGF3结点的层数树形T中结点的层数递归定义如下: root(T)层数为零; 其余结点的层数为其前驱结点的层数加1 .4路径树形中结点间的连线被称为边。若树形T中存在结点序列vm vm+1 vm+k,1 k T的最大层数,满足vi+1是vi(m i m+k-1)的子结点,则称此结点序列为vm到vm+k的路径,该路径所经历的边数k被称为路径长度。5. 子孙结点、祖先结点一棵树中若存在结点vm到vn的路径,则称v
5、n为vm的子孙结点,vm为vn的祖先结点。图4.1 (a) 树AECDBIHGF不难看出,一个结点到它的某个子孙结点有且仅有一条路径。树形T的任一结点p都是T的一棵子树的根结点,该子树由结点p和其所有子孙结点构成。图4.1(a)中的结点B是由结点B、E、F组成的子树的根,而结点C是由结点C、G、H组成的子树的根。6树的高度树的高度为maxi=1, n NL (i),其中n为树中结点总数,i指树中第i个结点,NL(i)之值为结点i的层数。例如,图4.1(b)中,结点A的层数为0 ,B、C、D的层数为1 ,E、G、H、I的层数为2 ,F的层数为3,故图4.1(b)中之树的高度为3 .AECDBIH
6、GF第0层第1层第2层第3层图4.1 (b) 结点的层数 图4.2给出了一个高度为5的世系树。图4.2 世系树4.2 二叉树二叉树是一种常用的树结构,它是树结构的另一种重要类型,其特征是:树中每个结点最多有两个子树形。4.2.1 二叉树定义和主要性质定义4.3 二叉树(形)是结点的有限集合,它或者是空集,或者由一个根及两个不相交的称为这个根的左、右子树形的二叉树组成。-abc/+/def图4.3 公式a-b(c/d+e/f)的二叉树表示二叉树有如下重要性质:引理4.1 二叉树中层数为的结点至多有2i个,i 0 .证明:用数学归纳法。当i = 0时,仅有一个根结点,其层数为0,因此i = 0时引
7、理成立。假定当i = j ( j 0)时,引理成立,即第j层上至多有2j个结点。对于二叉树的任意结点,其子结点个数最多为2,故第j +1层上至多有22j = 2j+1个结点,故i = j + 1时,引理亦成立。证毕容易看出高度为k (k 1)的二叉树中至少有k+1个结点。含有k (k 1)个结点的二叉树高度至多为k-1 . 如图4.5是高度为3结点最少的二叉树之一。图4.6(a)是高度为3结点最多的二叉树。图4.5 有4个结点、高度为3的二叉树CABD(a) 15个结点的满二叉树832145671314151011129引理4.2 高度为k的二叉树中至多有2k+1-1( k 0)个结点。证明:
8、从第0层到第k层,对每层的最大结点数求和,由引理4.1知,证毕引理4.3 设T是由n个结点构成的二叉树,其中叶结点个数为n0,次数为2的结点个数为n2,则有n0 = n2 +1 .证明:设n1是T中次数为1的结点个数,则 n = n0 + n1 + n2 (1)(4.1)设二叉树T的边个数为E. 我们知道,除根结点外,每个结点和父结点之间都有且仅有一条边,即一个结点对应一条边,因此,n比边的个数多1(根结点不对应边),即n =E+1 (2)从另一个角度看,次数为1的结点对应一条边,次数为2的结点对应两条边,因此 E = n1+2n2 (3)由(1)、(2)和(3)可以得到 n0= n2+1.
9、证毕定义4.4 一棵非空高度为k( k 0)的满二叉树,是有2k+1-1个结点的二叉树。(a) 15个结点的满二叉树832145671314151011129我们可按层次顺序(即按从第0层到第k层,每层由左向右的次序)将一棵满二叉树的所有结点用自然数从1开始编号。例如,图4.6(a) 给出了高度为3的满二叉树的24-1个结点的编号。定义4.5 一棵包含n个结点高为k的二叉树T,当按层次顺序编号T的所有结点,对应于一棵高为k的满二叉树中编号由1至n的那些结点时,T被称为完全二叉树。满二叉树和完全二叉树是二叉树的两种特殊情形。(a) 15个结点的满二叉树832145671314151011129图
10、4.6 满二叉树与完全二叉树(b) 10个结点的完全二叉树83214567109引理4.4 若将一棵有n个结点的完全二叉树按层次顺序用自然数从1开始编号,则编号为i (1 i n)的结点满足如下性质: 若i 1,则编号为i的结点之父结点的编号为 i /2; 若2i n,则编号为的结点的左孩子编号为2i,否则i无左孩子; 若2i + 1 n,则i结点的右孩子编号为2i + 1,否则i无右孩子。证明:用归纳法可证明.若i =1,如果n 2,则左孩子编号显然为2 .假定对所有j(1 j i,2i n),j的左孩子编号为2j,则往证结点j=i+1之左孩子的编号为2(i+1)的情况。如果2(i +1)
11、n,则由层次顺序知,i +1的左孩子之前的两个结点就是i的左孩子和右孩子,因为i的左孩子编号为2i(由归纳假设),故i的右孩子编号为2i+1,从而i+1的左孩子编号为2i+2=2(i+1) . 因为由可直接推出,由和又可得到,证毕例如:图4.6 (b)中编号为4的结点的父结点编号为2,其左孩子编号为8,右孩子编号为9,而编号为5的结点的父结点编号为2,其左孩子编号为10,无右孩子。图4.6 满二叉树与完全二叉树(b) 10个结点的完全二叉树83214567109引理4.5 具有n个结点的完全二叉树的高度是log2 n .证明:设二叉树高度为k,由定义4.5知,完全二叉树的结点个数介于高度为k和
12、高度为k - 1的满二叉树的结点数之间,即有:2k-1 n 2k+1-1,从而有2k n 2k+1-1,即k log2 n k +1,有log2 n -1 k log2 n,因为k为整数,故有k = log2 n,证毕4.2.2 二叉树顺序存储要存储一棵二叉树,必须存储其所有结点的数据信息、左孩子和右孩子地址,既可用顺序结构存储,也可用链接结构存储。二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中,同时反映出二叉树中结点间的逻辑关系。对于完全二叉树,结点的层次顺序反映了其结构,可按层次顺序给出一棵完全二叉树之结点的编号,事实上,这就是完全二叉树的顺序存储方法,结点
13、编号恰好反映了结点间的逻辑关系。只要对二叉树之结点按照层次顺序进行编号,就可利用一维数组A来存储一棵含有n个结点的完全二叉树,其中A1存储二叉树的根结点,Ai存储二叉树中编号为i的结点,并且结点Ai的左孩子(若存在)存放在A2i处,而Ai的右孩子(若存在)存放在A2i+1处。图4.7 (b) 描述了图4.7 (a) 所示的完全二叉树的顺序存储结构。 图4.7 完全二叉树与顺序存储结构AECDB(b) 图(a)的顺序存储结构A1A3A21(a) 5个结点的完全二叉树EBACD2345A4A5这种顺序存储方式是完全二叉树最简单、最节省空间的存储方式,多数完全二叉树应用算法都采用了这种顺序存储方式。
14、它实际上只存储了结点信息域之值,而未存储其左孩子和右孩子地址,通过计算可找到它的左孩子、右孩子和父结点,寻找子孙结点和祖先结点也非常方便。但是,这种方法应用到非完全二叉树时,却有很多缺点。如果采用上述的顺序存储方式,按照层次顺序,对非完全二叉树之结点进行编号,则这时的编号不能与结点一一对应。为此,先加入若干虚结点将其转换成一棵“完全二叉树”,然后再对原来的结点和虚结点统一编号,最后完成顺序存储。但这增加了用于存储虚结点的空间。如图4.8(a) 所示,二叉树中只有4个结点,转换为“完全二叉树”后如图4.8 (b) 所示,图中的方形结点为增加的虚结点,其顺序存储结构如图4.8(c)所示,需要15个
15、数组元素,但ABCDABCD(a) 非完全二叉树(b) 完全二叉树ABCD A1 A3 A7 A15图4.8 非完全二叉树与顺序存储结构(c) 非完全二叉树的顺序存储结构实际上只有A1、A3、A7和A15 等4个数组元素的存储空间能被充分利用,而其它11个数组元素所占用的空间却被浪费。显然,对非完全二叉树,顺序存储结构可能会浪费大量存储空间。此外,同线性表的顺序存储一样,二叉树顺序存储方式对插入或删除结点等操作不够方便。4.2.3 二叉树链接存储二叉树的链接存储系指二叉树诸结点被随机存放在内存空间中,结点之间的关系用指针说明。在二叉树的链接存储中,二叉树结点应包含三个域:数据域Data、左指针
16、域Left和右指针域Right,结点结构如下: LeftDataRight其中数据域Data存放结点自身的信息,域Left和Right分别存放指向该结点之左孩子和右孩子的指针。在二叉树的链接存储中,有一个指向根结点的指针,称为根指针,二叉树由根指针唯一确定。若二叉树为空,则根指针为NULL(即L);若结点的某个孩子不存在,则相应的指针域存放NULL.显然,叶结点的左、右指针域皆存放NULL. 在包含n个结点之二叉树的链接存储中,需要2n个指针域,但其中只有n-1个用来指示结点的左、右孩子,其余n+1个指针域为空(见引理4.3,E = n -1)。图4.9 (a) 为一棵二叉树,其链接存储结构如
17、图4.9 (b),结点A的Left指针指向其左子结点B,Right指针指向其右子结点C,结点B的Left指针为空, Right指针指向其子结点D .BDrootECAACBDE(a) 二叉树(b) 二叉树的链接表示图4.9二叉树的链接存储结构下面用三个算法来说明,二叉树的链接存储可方便地进行二叉树的一些操作。 在二叉树中搜索给定结点的父结点算法Father ( t, p . q )/* 指针t指向二叉树T之根,在T中搜索给定结点p之父结点; q指向p之父结点;本算法使用了递归 */Father1. t =L? IF t = L THEN ( q L . RETURN. ) Father2. t
18、为所求? IF Left ( t ) = p OR Right ( t ) = p THEN ( q t. RETURN. )Father3. 递归Father ( Left ( t ) , p . qL).IF qL L THEN (q qL . RETURN. ) ELSE (Father (Right ( t ), p . qR). q qR . RETURN. ) 搜索二叉树中符合数据域条件的结点算法Find( t, item . q )/* 在二叉树T中搜索Data域之值为item的结点,指针t指向T之根,指针q指向欲搜索的结点 */Find1. t =L? IF t = L THE
19、N (q L . RETURN. ).IF Data( t ) = item THEN (q t . RETURN. ).Find2 .递归Find ( Left(t), item . p ).IF p L THEN (q p . RETURN. ).Find (Right(t), item . q ).RETURN. 从二叉树中删除给定结点及其左右子树算法DST ( t )/* root指向一棵二叉树T之根,本算法从T中删除给定结点t (是简称,其含义是:t是指向该结点的指针)及其左右子树;DST是DelSubTree之缩写*/DST1. t =L? IF t = L THEN RETURN
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击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。