数据结构 第2版 宗大华 陈吉人 数据结构 课件-6

数据结构 第2版 宗大华 陈吉人 数据结构 课件-6

ID:40247057

大小:6.49 MB

页数:22页

时间:2019-07-29

数据结构 第2版 宗大华 陈吉人 数据结构 课件-6_第1页
数据结构 第2版 宗大华 陈吉人 数据结构 课件-6_第2页
数据结构 第2版 宗大华 陈吉人 数据结构 课件-6_第3页
数据结构 第2版 宗大华 陈吉人 数据结构 课件-6_第4页
数据结构 第2版 宗大华 陈吉人 数据结构 课件-6_第5页
资源描述:

《数据结构 第2版 宗大华 陈吉人 数据结构 课件-6》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第6章树与森林1.2.3.本章讲述内容:树的定义及基本概念;树、森林与二叉树之间的相互转换;树的各种存储结构;树、森林的遍历。4.6.1树的概述6.1.1树的定义与特性树的定义1.2..所谓“树”是指由n(n≥0)个结点构成的有限数据元素的集合T。当n=0时,称其为“空树”。.当n≠0时,树中诸结点应该满足下面的两个条件:树的几个特性(2)根结点外的其余结点,可分为m(m≥0)个互不相交的有限集合:T1、T2、…、Tm,每一个集合Ti(0≤i≤m)又是一棵树,被称为是根的子树。(1)有且仅有一个特定

2、的结点,它没有前驱,是该树的根,称为树的根结点;空树是树的一个特例;..一棵非空树,至少有一个根结点,只有根结点的树为最小树;.在拥有多个结点的树里,除根结点外,其余各结点分属若干个子树,各子树间互不相交;.除根结点外,树中所有其他结点有且只有一个前驱结点,但可以有零个或多个后继结点。3.其他表示分支、层次关系的方法例:AФ(空树)BCDIKLMGACDHFBEJA(最小树)(单分支树)(一般的树).文氏图表示法.凹入表示法.括号表示法BDEFGCIHAGCABDFEIH在这种表示法中,任意两个集合

3、或是不相交,或是一个包含另外一个。用不同长度的矩形表示树中的各个结点。ABDEHIFCGA(B(D,E(H,I),F),C(G))树的几种图形表示以右图给出的树为例:6.1.2有关树的常用术语1.有关结点的术语.结点:指一个数据元素以及指向其子树根结点的分支。在树型结构中,常用一个圆圈及一条条短线表示。.结点的度:指树中一个结点拥有的子树数目。因此,结点的度也就是该结点的后继结点的个数。.结点的深度:树是一种层次结构。通常,把一棵树的根作为第0层,其余结点的层次值,为其前驱结点所在层值加1。所谓结点

4、的“深度”,即是该结点位于树的层次数。.叶结点:树中度为0的结点被称为叶结点。叶结点也就是终端结点。.分支结点:树中度大于0的结点称为分支结点,或非终端结点。.结点的路径:从树中一个结点到另一个结点之间的分支,称为这两个结点间的路径。.路径长度:一条路径上的分支数,称为该路径的长度。2.有关结点间关系的术语.所谓“根”结点,是指树中没有直接前驱的那个结点,一棵树只能有一个根结点。.双亲结点:在树中,把一个结点称作是它所有后继结点的双亲结点。双亲结点有时也被称作父结点。.子孙结点:一个结点的子树中的所

5、有结点,都被称作是该结点的子孙结点,简称子孙。.祖先结点:从根结点到某个结点的路径上的所有分支结点,是该结点的祖先结点。.兄弟结点:在树中,具有相同双亲的结点,互称为是兄弟结点。.堂兄弟结点:在树中,双亲在同一层的那些结点,互称为是堂兄弟结点。3.有关树的整体术语.树的度:一棵树中各结点的度的最大值,称为这棵树的度。.树的深度:一棵树中各结点的深度的最大值,称为该树的深度。树的深度有时也称为树的高度。.有序树与无序树:如果限定树中各结点的子树从左至右的排列具有一定顺序,不得互换,那么就称该树是有序的

6、,否则称为是无序树。.森林:n(n≥0)棵互不相交的树的集合,称为森林。孩子结点:树中一个结点的所有直接后继,都被称作是该结点的孩子结点。实际上,一个结点的孩子结点就是该结点子树的根结点。.6.2树、森林和二叉树间的转换6.2.1树、森林转换到二叉树1.树转换到二叉树将如图所示的一棵树转换到所对应的二叉树。在树的所有兄弟结点之间添加一条连线;对树中的所有结点,除保留其与第一个孩子结点间的连线(即分支)外,删除到其他孩子之间的连线;.FHJACDGBEIKFHJACDGBEIK第1步:第2步:FHJA

7、CDGBEIK将森林中的每棵树转换成相应的二叉树;.以原树的根结点为轴心,将经过上述处理的树顺时针方向转动一个角度,即可得到该树所对应的二叉树。第3步:CABEFDGIJHK旋转方向结论:在把树转换成二叉树时,这棵二叉树的根结点只有左子树,没有右子树。对于这棵二叉树上的任何一个结点,其左孩子必定是它在树中的第一个孩子结点,右孩子是它在树中的兄弟结点。2.森林转换到二叉树.转换方法:先把森林中的每棵树都转换成只有左子树的二叉树。然后,把森林中后一棵树的根结点视为是前一棵树根结点的兄弟,这样就可把森林转

8、换成一棵二叉树。.将如图所示的森林转换成所对应的二叉树。HABGDFCEJLIK第1步:BADCEJFHGIKL依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右子树;第2步:JHGIKLBADCEFBADCEF第3步:在完成对所有二叉树的连接后,所得到的二叉树即为所求。6.2.2二叉树转换到树、森林1.二叉树转换到树.一棵树通过转换,可以得到与其相对应的、根结点只有左孩子的一棵二叉树。因此,只有根结点无右孩子的二叉树,才能够通过转换还原成一棵树。.将如图所示的二叉

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

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

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