第13章非线性结构.ppt
《第13章非线性结构.ppt》由会员分享,可在线阅读,更多相关《第13章非线性结构.ppt(35页珍藏版)》请在三一文库上搜索。
1、第13 章 非线性结构,本章课件制作:靳展,第三部分 数据结构基础,本章内容(树形结构), 树的基本概念 二叉树的基本概念和性质 二叉树的存储结构 二叉树的遍历 C+中的二叉树类 树、森林与二叉树的转换 哈夫曼树,本章内容(图形结构), 图的概念 图的存储结构 图的遍历 图的生成树和最小生成树 最短路径 拓扑排序 关键路径,树的基本概念,1. 树的特点,2. 树的定义,树是n(n0)个数据元素的有限集合。它满足以下两个条件: 有且仅有一个特定的称为根的元素; 其余元素分为()个互不相交的有限集合1、2、,其中每个集合又都是一棵树并称其为根的子树。,树形结构是一类非常重要的非线性结构,适合于描述
2、数据元素之间的层次关系,树的常用术语, 双亲、子女、边:若结点是结点的一棵子树的根,则称做的“双亲” 称做的“子女”;有序对,称做从到的“边” 。 兄弟:具有同一双亲的结点 。 路径、路径长度:若树中存在着一个结点的序列12j,使ki是ki+1( )的双亲,则称该结点序列为从k1到kj的一条路径;路径长度 等于-,它是该路径所经过的边的数目 。 结点的层数:根结点层数为,其余结点层数等于其双亲结点层数加 。 树的深度(高度):即树中层数最大的结点的层数 。 结点的度数、树的度数:一个结点子女的个数称为该结点的“度数”。 树中度数最大的结点的度数叫做“树的度数” 。 树叶、分支结点:度数为的结点
3、叫做“树叶” ;度数大于的结点叫做“分 支结点”或“内结点” 。 有序树、无序树:若将树中每个结点的各个子树看成从左到右有序的, 则称该树为有序树;否则为无序树 。 森林:()棵互不相交的树的集合称为森林 。,树的常用术语举例, 是的双亲,是的子女,是从到的边。 、互为兄弟,而和不是兄弟 。 ADIN是从结点到结点的一条路径,其长度为 。 层数为的结点有,层数为的结点有、 。 树的深度为 。 、的度数分别为、;树的度数为 。 、都是树叶,其余结点都是分支结点 。,森 林,二叉树的基本概念,二叉树是()个结点的有限集合。它或者是空集(),或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和
4、右子树的二叉树组成。,1.二叉树的定义,2. 二叉树五种基本形态, 二叉树的子树有左、右之分,树的子树是相同的。 二叉树可以是空,而树不能为空。,3.树和二叉树的差别,二叉树的性质,性质 二叉树第层上的结点数目最多为2i()。 性质 深度为的二叉树至多有2k+1-1个结点()。 性质 在任意一棵二叉树中,若终端结点的个数为n0、度数为的结点的个数为n2,则n0=n2+1。,1. 二叉树的性质,2. 两种特殊的二叉树,满二叉树 完全二叉树,完全二叉树性质,性质4 具有个结点的完全二叉树的深度为 log2n 性质5 若对一棵有个结点的完全二叉树,按自顶向下、同层由左到右顺序依次为其每个结点从0开始
5、编号,则对编号为的结点ki(n-1)则有: 若0,则ki双亲结点的编号为 (i-1)/2 若=,则ki是根结点。 若2i+1n,则ki左子女结点的编号是2i+1,否则ki无左子女。 若2i+2n,则ki右子女结点的编号为2i+2,否则ki无右子女。,二叉树的存储结构,对完全二叉树,利用性质5,将其所有结点按编号顺序依次存储在一维数组里。 对一般二叉树,需要加上一些并不存在的“虚结点”,转换为完全二叉树的形式。,1. 顺序存储结构,二叉树的存储结构,2. 链式存储结构,链接存储时结点的结构,二叉树的遍历,先序遍历 访问根结点,先序遍历左子树,先序遍历右子树。 中序遍历 中序遍历左子树,访问根结点
6、,中序遍历右子树。 后序遍历 后序遍历左子树,后序遍历右子树,访问根结点。 层次遍历 按层数由小到大、同一层从左到右顺序依次访问二叉树的各个结点,先序访问序列 :ABDGECF 中序访问序列 :DGBEAFC 后序访问序列 :GDBEAFC 层次访问序列 :ABCDEFG,二叉排序树类,二叉排序树:一种特殊的二叉树,其特点是:左子树上所有结点的值均小于其双亲结点的值,右子树上所有结点的值均大于或等于其双亲结点的值。,二叉排序树类的成员函数,树、森林与二叉树的转换,将树转换成二叉树: 在所有的兄弟之间加一条连线; 对每个结点,除了保留与最左边子女的连线外,去掉与其他子女连线; 将保留下来的边作为
7、左子树的边,兄弟间的连线作为右子树的边。 将一个森林转换成二叉树: 先将森林中的每一棵树变为二叉树,然后将各二叉树的根结点看成兄弟, 用线把它们连到一起,经整理后可得到相应的二叉树。,树、森林到二叉树的转换,树、森林与二叉树的转换 (续),若结点是其双亲的左子女,则把的右子女、右子女的右子女都与连线,最后去掉所有双亲到右子女的连线。,2二叉树到树、森林的转换,哈夫曼树基本概念,扩充二叉树和带权路径长度: 假设W0,W1,Wn-1是个实数的集合,其中Wi(-)。若是一棵有个叶结点的二叉树,而且将W0,W1,Wn-1分别赋给的个叶结点作为它们的权,则称是权值为W0,W1,Wn-1的扩充二叉树。带有
8、权值的叶结点叫做扩充二叉树的外结点,其余的分支结点叫做内结点。 一个有个外结点的扩充二叉树的带权路径长度()为: WPL= 其中,Wi为外结点所带的权值;li为从根结点到外结点的路径长度。,(a) WPL=40 (b) WPL=50 (c) WPL=38,哈夫曼树基本概念 (续),2最优二叉树 通常,把权值取为W0,W1,Wn-1的所有扩充二叉树中为最小的扩充二叉树称为最优二叉树。 3哈夫曼树 利用哈夫曼提出的方法构造出的最优二叉树称为哈夫曼树。,4哈夫曼树构造方法 由给定的个权值W0,W1,Wn-1构造含有棵扩充二叉树的森林,森林中的每棵二叉树都只有一个根结点,且每个根结点都取一个各不相同的
9、Wi作为权值; 用森林中根结点的权值为最小和次小的两棵二叉树作为左、右子树构造出一棵新的二叉树,并将新二叉树的根结点的权值取为左、右子树根结点权值之和; 从森林中删去作为新二叉树左、右子树的两棵二叉树,将新构造的二叉树加入到森林中; 重复步骤和,直到中仅剩下一棵二叉树为止。,哈夫曼树的构造,哈夫曼树的应用,例 设电文字符集为a,b,c,d,e,f,各字符发送频率是6,2,3,3,4,9,利用哈夫曼树构造个字符的编码。 以字符发送频率为权值构造哈夫曼树,哈夫曼编码,各字符的哈夫曼编码是 a:01 b:001 c:001 d:100 e:101 f:100,图的概念,图的定义,图用二重组(,)表示
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 13 非线性 结构
链接地址:https://www.31doc.com/p-3420515.html