第六章树与森林.ppt
《第六章树与森林.ppt》由会员分享,可在线阅读,更多相关《第六章树与森林.ppt(33页珍藏版)》请在三一文库上搜索。
1、第六章 树与森林,学习要点:,树的递归定义和森林的基本概念。 树与森林的存储结构。 树与森林的遍历算法 树、森林与二叉树的相互转换。,2,6.1 树及其相关概念,6.1.1 树的基本概念 1、树的基本概念,3,树(Tree)是一个由n(n0)个结点构成的有限集合T。 当n=0时,称T为“空树”。 当n0时,T中诸元素满足下述条件: 有且仅有一个特定数据元素没有前驱,称其为T的根结点。 除根结点外其余数据元素,又可分为m(0mn)个互不相交的有限集合:T1,T2,Tm,每一个集合Ti(0im)又是一棵树,称为根的子树。,6.1.1 树的基本概念,1、树的基本概念2 树的特性:,4,空树是树的一个
2、特例; 一棵非空树,至少有一个根结点,只有根结点的树为最小树; 在有多个结点的树里,除根结点外,其余结点分属若干个子树,各子树间互不相交; 除根结点外,树中其他结点有且只有一个前驱结点,但可以有零个或多个后继结点。,6.1.1 树的基本概念,1、树的基本概念3 有序树与无序树 如果树T中各子树从左至右按照一定此序排列,不得互换,则称T是有序树(order tree),否则为无序树(unorder tree)。由此可知,二叉树是一种特殊的有序树,但不是一般树的特例。 森林 n(n0)棵互不相交的树的集合,称为森林(forest)。,5,6.1.1 树的基本概念2,2、树的表示方法 树形表示法,6
3、, 文氏图表示法, 凹入表示法, 括弧表示法 (A(B(D)(E(I)(J)(F)(C(G)(H),6.1.2 结点及其基本概念,1、结点 结点的度:结点拥有的子树数目,即该结点的后继结点的个数 结点的深度(层次):结点位于树的层次数 树的度:一棵树中各结点度的最大值 树的深度:一棵树中各结点深度的最大值 结点间路径:从树中一个结点到另一个结点之间的分支 路径长度:一条路径上边即连接两个结点的线段的个数称为该路径的长度,7,6.1.2 结点及其基本概念2,8,2、结点分类 (1)根结点:树T中没有前驱的结点称为T的根结点 叶结点:树T中没有后继的点称为T的叶结点 内部结点:树T中既有前驱又有后
4、继的结点称为T的内部结点 (2)分支结点:树T中度数不等于0的结点为T的分支结点 非分支结点:树T中度数等于0的结点称为T的非分支结点,6.1.2 结点及其基本概念3,9,3、结点间关系描述 子结点:树T中一个结点N的所有直接后继,都被称作是该结点N的子结点 父结点:树T中把一个结点称作是它所有后继结点的父结点 兄弟结点:在树T中,具有相同双亲的结点,互称为是兄弟结点 堂兄弟结点:在树T中,双亲在同一层的那些结点,互称为是堂兄弟结点 子孙结点:一个结点的子树中的所有结点,都被称作是该结点的子孙结点 祖先结点:从根结点到某个结点的路径上的所有分支结点,称为该结点的祖先结点,6.2 树的存储结构,
5、6.2.1 父结点表示法存储 将树中结点按照“由上到下”和“由左到右”的顺序做成一个结点序列,将该序列存放在一维数组Tr当中。Tr中每个元素(结点)都有一个Data域和一个Parent域,其中Data域存放结点数据,而Parent域存放结点的父结点在数组中下标。,10,6.2.2 子结点表示法存储,考虑通过设立结点的Children域来存储树结构信息。当使用链式结构来实现树存储时,就需要将每个结点的孩子信息都存放在存储结点中。此时存储结点除建立Data域外,还需按照树的度m对每个结点构建m个指针域。,11,6.2.2 子结点表示法存储2,1、子结点链表存储法,12, 将树T中结点按照层序进行排
6、序。 为树T中每个结点都设置一个单链表,该链表由该结点的所有子结点按照层序进行链接。这样的链表也称为子结点链表。 将每个结点子结点链表的表头指针按照树T结点的层序集中起来组成数组Tr。,6.2.2 子结点表示法存储3,2、子结点顺序表存储法,13, 将树T的结点按照层序进行排序,组成数组Tr。 对Tr中每个数组元素开辟Data域和m个子结点域:Child1,Child2,Childm,这些子结点域分别记录每个结点的子结点信息。 将数组Tr进行存储。,6.2.3 左子/右兄弟结点表示法存储,结点由Data域(存放数据信息)、Lch域(存放该结点第一个子结点即左子结点信息)和RS域(存放该结点第一
7、个兄弟结点即右兄弟结点信息)组成。,14,6.2.3 左子/右兄弟结点表示法存储2,可以分别按照顺序或链表方式进行进行存储。,15,6.3 树的遍历,6.3.1 层次遍历 1、层次遍历概念,16,两个步骤: 按照树的“层”的顺序进行访问,即“从上到下”。 访问到达每一层后,再依次访问该层的每个结点,即“从左到右”。 两个基本点: 采用子结点表示法的存储结构记录树中结点。 基于队列的结点存储 当进入一个结点后,需要将该结点所有子结点信息记录下来以便必要时能够使用。由于先达到结点的子结点,将来会得到首先访问,所以需要采用队列方式记录结点的子结点信息以保证它们能够依照进入队列的先后顺序得到访问。,例
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六 森林
链接地址:https://www.31doc.com/p-2566249.html