《第13章非线性结构.ppt》由会员分享，可在线阅读，更多相关《第13章非线性结构.ppt（35页珍藏版）》请在三一办公上搜索。
1、第13 章 非线性结构,本章课件制作：靳展,第三部分 数据结构基础,本章内容（树形结构）,树的基本概念 二叉树的基本概念和性质 二叉树的存储结构 二叉树的遍历 C+中的二叉树类 树、森林与二叉树的转换 哈夫曼树,本章内容（图形结构）,图的概念 图的存储结构 图的遍历 图的生成树和最小生成树 最短路径 拓扑排序 关键路径,树的基本概念,1.树的特点,2.树的定义,树是n(n0)个数据元素的有限集合。它满足以下两个条件：有且仅有一个特定的称为根的元素；其余元素分为（）个互不相交的有限集合1、2、，其中每个集合又都是一棵树并称其为根的子树。,树形结构是一类非常重要的非线性结构，适合于描述数据元素之间
2、的层次关系,树的常用术语,双亲、子女、边:若结点是结点的一棵子树的根，则称做的“双亲”称做的“子女”；有序对，称做从到的“边”。兄弟：具有同一双亲的结点。路径、路径长度：若树中存在着一个结点的序列12j，使ki是ki+1（）的双亲，则称该结点序列为从k1到kj的一条路径；路径长度 等于-，它是该路径所经过的边的数目。结点的层数：根结点层数为，其余结点层数等于其双亲结点层数加。树的深度（高度）：即树中层数最大的结点的层数。结点的度数、树的度数：一个结点子女的个数称为该结点的“度数”。树中度数最大的结点的度数叫做“树的度数”。树叶、分支结点：度数为的结点叫做“树叶”；度数大于的结点叫做“分 支结点
3、”或“内结点”。有序树、无序树：若将树中每个结点的各个子树看成从左到右有序的，则称该树为有序树；否则为无序树。森林：（）棵互不相交的树的集合称为森林。,树的常用术语举例,是的双亲，是的子女，是从到的边。、互为兄弟，而和不是兄弟。ADIN是从结点到结点的一条路径，其长度为。层数为的结点有，层数为的结点有、。树的深度为。、的度数分别为、；树的度数为。、都是树叶，其余结点都是分支结点。,森 林,二叉树的基本概念,二叉树是（）个结点的有限集合。它或者是空集（），或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。,1.二叉树的定义,2.二叉树五种基本形态,二叉树的子树有左、右
4、之分，树的子树是相同的。二叉树可以是空，而树不能为空。,3.树和二叉树的差别,二叉树的性质,性质 二叉树第层上的结点数目最多为2i（）。性质 深度为的二叉树至多有2k+1-1个结点（）。性质 在任意一棵二叉树中，若终端结点的个数为n0、度数为的结点的个数为n2，则n0=n2+1。,1.二叉树的性质,2.两种特殊的二叉树,满二叉树 完全二叉树,完全二叉树性质,性质4 具有个结点的完全二叉树的深度为 log2n 性质5 若对一棵有个结点的完全二叉树，按自顶向下、同层由左到右顺序依次为其每个结点从0开始编号，则对编号为的结点ki（n-1）则有：若0，则ki双亲结点的编号为(i-1)/2 若=，则ki
5、是根结点。若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的扩充二叉树。带有权值的叶结点叫做扩充二叉树的外结点，其余的分支结点叫做内结点。一个有个外结点的扩充二叉树的带权路径长度（）为：WPL=其中，Wi为外结点所带的权值；
8、li为从根结点到外结点的路径长度。,(a)WPL=40(b)WPL=50(c)WPL=38,哈夫曼树基本概念（续）,2最优二叉树通常，把权值取为W0，W1，Wn-1的所有扩充二叉树中为最小的扩充二叉树称为最优二叉树。3哈夫曼树利用哈夫曼提出的方法构造出的最优二叉树称为哈夫曼树。,4哈夫曼树构造方法由给定的个权值W0，W1，Wn-1构造含有棵扩充二叉树的森林，森林中的每棵二叉树都只有一个根结点，且每个根结点都取一个各不相同的Wi作为权值；用森林中根结点的权值为最小和次小的两棵二叉树作为左、右子树构造出一棵新的二叉树，并将新二叉树的根结点的权值取为左、右子树根结点权值之和；从森林中删去作为新二叉树
9、左、右子树的两棵二叉树，将新构造的二叉树加入到森林中；重复步骤和，直到中仅剩下一棵二叉树为止。,哈夫曼树的构造,哈夫曼树的应用,例 设电文字符集为a，b，c，d，e，f，各字符发送频率是6，2，3，3，4，9，利用哈夫曼树构造个字符的编码。以字符发送频率为权值构造哈夫曼树,哈夫曼编码,各字符的哈夫曼编码是 a：01 b：001 c：001 d：100 e：101 f：100,图的概念,图的定义,图用二重组（，）表示。其中，是顶点的有穷非空集合；是中顶点偶对（称为边）的有穷集合。对一个给定的图，用（）表示顶点集，用（）表示边集。,有向图,如果一个图中的每条边都有方向，称它为有向图。在有向图中，一
10、条有向边是由两个顶点组成的有序对。有序对常用尖括号表示，例如，表示一条有向边，Vi是边的始点，Vj是边的终点。和表示的是两条不同的边。,无向图,如果一个图中每条边都是没有方向的，则称此图为无向图。无向图中组成边的两个顶点是无序的，通常用圆括号表示。例如，(Vi,Vj)表示一条无向边。(Vi,Vj)和(Vj,Vi)表示的是同一条边。,图的常用术语,邻接顶点 在无向图中，若（，）是图中的一条边，则称顶点和互为邻接顶点。在有向图中，若，是图中的一条边，则称顶点邻接到顶点，顶点邻接自顶点。顶点的度 与顶点相关联的边的数目叫做度。有向图顶点的度还有入度与出度之分：顶点的入度即以该顶点为终点的边的数目；顶
11、点的出度即以该顶点为始点的边的数目。子图 设有两个图（，）、（，）。若VV、EE，并且中的边所关联的顶点都在中，则称图是图的子图。,图的常用术语（续）,权 有些图的边附带有数据信息，称这些数据信息为权。常把带权的图称为网络。路径 在图G=(V,E)中，若存在顶点序列VP,Vi1,Vi2,Vin,Vq使得(VP,Vi1),(Vi1,Vi2),(Vin,Vq)都在中，则称从顶点VP到Vq存在一条路径。路径长度 对于不带权的图，路径长度是指路径上边的数目；对带权的图，路径长度是指路径上各条边的权值之和。简单路径 如果一条路径上除第一个顶点和最后一个顶点可以相同外，其他顶点都不相同，则称此路径为简单路
12、径。连通图 对无向图（，）而言，如果从顶点Vi到顶点Vj有一条路径，则称Vi和Vj是连通的。若（）中任意两个不同的顶点Vi和Vj都连通，则称此图为连通图。,图的存储结构,称A为邻接矩阵。,1邻接矩阵法,设图（，）有（）个顶点 V0，V1，Vn-1，可以用一个nn阶的矩阵A描述图中边的情况。对于A中的每个元素aij满足,（0in-1,0jn-1）,图的存储结构,性质：对无向图而言，顶点Vi的度数di是矩阵第i行元素值之和，即；对有向图而言，顶点Vi的出度为第行元素值之和，顶点Vi的入度为第列元素值之和。顶点Vi的度为,1邻接矩阵法（续）,对于带权的图，邻接矩阵A中的元素可以定义为：,（0in-1
13、,0jn-1）,图的存储结构,2邻接表法,用邻接表表示有个顶点的无向图时，需要一个以顺序方式或链接方式存储的顶点表和个单链表。顶点表的每个表目包括两个域：一个域用来存放顶点Vi的信息，另一个域用来存放一个指针，它指向与该顶点对应的单链表。与顶点Vi对应的单链表中的每个结点代表了一个与Vi相邻接的顶点，它包括三个域：dest、weight和link。dest域中保存了一个与Vi相邻接的顶点的下标；weight域存放相应边的权值（对不带权的图，weight域可以省略）；link域保存指向链表中下一个结点的指针。,图的存储结构,2邻接表法（续）,有向图的邻接表在构造与顶点Vi相关的链表时只链入以Vi
14、为起点的所有有向边，称这种邻接表为出边表。在顶点Vi的边链表中链接所有以Vi为终点的边，称这种链表为入边表。,性质：从有向图的出边表中统计Vi的边链表中结点个数即可得顶点Vi的出度。从有向图的入边表中统计Vi的边链表中结点个数即可得顶点Vi的入度。,比较：在邻接矩阵表示法中占用的存储单元个数与图中边的数目无关，只与图中顶点的个数有关。在邻接表表示法中，需要使用的存储单元不仅与图中顶点的个数有关，而且与边数也有关。,图的遍历,深度优先遍历序列：、广度优先遍历序列：、,深度优先搜索遍历从图中的一个顶点V为起点并访问之，然后访问与相邻接但至今未被访问过的顶点，再访问与邻接但未被访问过的任意一个顶点，
15、依此类推。当到达一个所有邻接顶点都被访问过的顶点时，从已经被访问过的顶点序列中最后一个还有未被访问过的邻接顶点的顶点开始，重复上述遍历过程。广度优先搜索遍历任意指定图中的一个顶点，访问此顶点，然后访问与顶点邻接的全部顶点W1、2、b，再依次访问与W1、2、b相邻的但未被访问过的顶点，如此下去。,图的生成树和最小生成树,图的生成树对连通的无向图、强连通的有向图或有根的有向图，从其中任何一个顶点或根出发都可以不间断地访问到图中的全部顶点。由图的所有顶点加上遍历过程中所经过的边构成的子图称为图的生成树。有n个顶点的生成树必有n-1条边。图的生成树不是惟一的。最小生成树图的各个生成树中各边权值之和为最
16、小的生成树称为图的最小生成树。,图的最小生成树,普里姆算法:从任意一个顶点开始，首先把这个顶点包括在生成树里，然后在一个顶点已在生成树里而另一个顶点还未在生成树里的边中找出权值最小的一条边，并把这条边和其不在生成树里的那个顶点包括进生成树，如此进行下去直到把所有的顶点都包括进生成树。最小生成树不是惟一的。,图的最短路径,最短路径:在带权的有向图中求两个顶点间长度最短的路径问题。两种情况：一是求从一个顶点到其他各顶点的最短路径；二是求每对顶点之间的最短路径。,AOV网和拓扑排序,AOV网:在有向图中，用顶点表示活动，用有向边表示活动之间的先后关系。称这样有向图为用顶点表示活动的网络，简称AOV网
17、(Activity On Vertices)。,拓扑序列和拓扑排序：将一个AOV网所有顶点排成一个线性序列，并使该序列满足以下条件：若在网中有一条从顶点i到j的路径，则在序列中顶点i必在顶点j的前面。满足此条件的AOV网的顶称点序列称为拓扑序列，称构造拓扑序列的过程为拓扑排序。,拓扑排序,拓扑排序算法：从网中选择一个入度为的顶点并输出之；如果找不到入度为的顶点，则说明此AOV网存在回路，不能得到拓扑序列。从网中删除该顶点和所有以它为始点的边。重复步骤、，直到AOV网中的全部顶点均已输出。,存在回路的AOV网不能得到拓扑序列。一个AOV网的拓扑序列不是惟一的。,序列之一：c0 c1 c2 c4
18、c3 c7 c8 c6 c5序列之二：c0 c7 c8 c1 c4 c2 c3 c5 c6,关键路径,AOE网：在带权的有向图中，用顶点表示事件，边表示活动，权表示活动的持续时间，称此图为AOE网。AOE网应该是无环的，且存在惟一的入度为的顶点（称为源点）和惟一的出度为的顶点（称为汇点）。,在AOE网中，有些活动可以并行执行，完成整个工程所需要的最少时间由从源点到汇点的最长路径的长度决定，称具有最大长度的路径为关键路径。关键路径上的活动称为关键活动。,拓扑排序,关键路径的相关量：活动ai的最早开始时间用ei表示。活动ai的最迟开始时间用li表示。li与ei之差为完成活动ai的时间余量。若某个活动ai有li=ei，则称活动ai是一个关键活动。,最早发生时间和最迟发生时间的计算：从ee0=0开始向汇点递推，即(k=1,2,.,n-1)从len-1=een-1开始向源点递推，即(j=n-2,.,0),
