下载此文档

第六章 树与森林课程.ppt


文档分类:行业资料 | 页数:约33页 举报非法文档有奖
1/33
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/33 下载此文档
文档列表 文档介绍
第六章树与森林
学****要点:
树的递归定义和森林的基本概念。
树与森林的存储结构。
树与森林的遍历算法
树、森林与二叉树的相互转换。
2
§ 树及其相关概念
树的基本概念
1、树的基本概念
3
树(Tree)是一个由n(n≥0)个结点构成的有限集合T。
①当n=0时,称T为“空树”。
②当n≠0时,T中诸元素满足下述条件:
●有且仅有一个特定数据元素没有前驱,称其为T的根结点。
●除根结点外其余数据元素,又可分为m(0≤m<n)个互不相交的有限集合:T1,T2,…,Tm,每一个集合Ti(0≤i≤m)又是一棵树,称为根的子树。
树的基本概念
1、树的基本概念2
树的特性:
4
空树是树的一个特例;
一棵非空树,至少有一个根结点,只有根结点的树为最小树;
在有多个结点的树里,除根结点外,其余结点分属若干个子树,各子树间互不相交;
除根结点外,树中其他结点有且只有一个前驱结点,但可以有零个或多个后继结点。
树的基本概念
1、树的基本概念3
有序树与无序树如果树T中各子树从左至右按照一定此序排列,不得互换,则称T是有序树(order tree),否则为无序树(unorder tree)。由此可知,二叉树是一种特殊的有序树,但不是一般树的特例。
森林 n(n≥0)棵互不相交的树的集合,称为森林(forest)。
5
树的基本概念2
2、树的表示方法
①树形表示法
6
②文氏图表示法
③凹入表示法
④括弧表示法
(A(B(D)(E(I)(J))(F))(C(G)(H)))
结点及其基本概念
1、结点
结点的度:结点拥有的子树数目,即该结点的后继结点的个数
结点的深度(层次):结点位于树的层次数
树的度:一棵树中各结点度的最大值
树的深度:一棵树中各结点深度的最大值
结点间路径:从树中一个结点到另一个结点之间的分支
路径长度:一条路径上边即连接两个结点的线段的个数称为该路径的长度
7
结点及其基本概念2
8
2、结点分类
(1)根结点:树T中没有前驱的结点称为T的根结点
叶结点:树T中没有后继的点称为T的叶结点
内部结点:树T中既有前驱又有后继的结点称为T的内部结点

(2)分支结点:树T中度数不等于0的结点为T的分支结点
非分支结点:树T中度数等于0的结点称为T的非分支结点
结点及其基本概念3
9
3、结点间关系描述
子结点:树T中一个结点N的所有直接后继,都被称作是该结点N的子结点
父结点:树T中把一个结点称作是它所有后继结点的父结点
兄弟结点:在树T中,具有相同双亲的结点,互称为是兄弟结点
堂兄弟结点:在树T中,双亲在同一层的那些结点,互称为是堂兄弟结点
子孙结点:一个结点的子树中的所有结点,都被称作是该结点的子孙结点
祖先结点:从根结点到某个结点的路径上的所有分支结点,称为该结点的祖先结点
§ 树的存储结构
父结点表示法存储
将树中结点按照“由上到下”和“由左到右”的顺序做成一个结点序列,将该序列存放在一维数组Tr当中。Tr中每个元素(结点)都有一个Data域和一个Parent域,其中Data域存放结点数据,而Parent域存放结点的父结点在数组中下标。
10

第六章 树与森林课程 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数33
  • 收藏数0 收藏
  • 顶次数0
  • 上传人12345
  • 文件大小0 KB
  • 时间2015-11-14