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

《数据结构 第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.二叉树转换到树.一棵树通过转换，可以得到与其相对应的、根结点只有左孩子的一棵二叉树。因此，只有根结点无右孩子的二叉树，才能够通过转换还原成一棵树。.将如图所示的二叉