【教学课件】第2章非线性数据结构树和图

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,*,页/91,下一页,上一页,停止放映,第2章 非线性数据结构树和图,西安交通大学计教中心,1,树形结构,树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在，并应用于：,人类社会的族谱、家谱、行政区域划分管理；,各种社会组织机构；,在计算机领域中，用树表示源程序的语法结构；,在,OS,中，文件系统、目录等组织结构也是用树来表示的。,2,树的逻辑结构,树是一种数据结构，可用二元组表示为：,Tree=,（,D,，,R,）,其中：,D,是具有相同特性的数据元素的集合；,R,是数据元素间逻辑关系的集合，且满足：,在,D,中存在唯一的称为根的数据元素，没有前趋；,D,中其余数据元素都有且只有一个前趋；,D,中所有元素，或有若干个互不相同的后继（子树），或无后继（叶结点）；,则称,Tree,为树。,3,树的递归定义:,树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足：,1）其中有一个特定的元素称为T的根root。,2）除根以外的集合可被划分为m个不相交的子集T,1,，T,2,，T,m,，其中每个子集都是树。它们称为根root的子树。,G,A,C,F,D,E,B,树的一般形式,4,树结构举例,C1（章） BOOK,1.1(节),1.2 C1 C2 C3, ,C2,2.1 1.1 1.2 2.1 2.2 2.3, ,2.11,2.12,2.2 2.1.1 2.1.2, ,2.3,C3,书目录 目录树 树结构,5,与树相关的术语,结点,：,在树结构中一般把,数据元素及其若干指向子树的分支称为结点。,结点的度,：结点拥有的非空子树的个数。,树的度,：树中所有结点的度的最大值。,叶子结点,：度为0的结点。,分支结点,：至少有一个非空子树的结点。,孩子结点和父结点,：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。,6,兄弟结点,：具有相同父结点的结点互为兄弟结点。,结点的层次,：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。,树的深度,：树中结点所在的最大层次。,有序树和无序树,：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。,森林,：由零棵或有限棵互不相交的树组成的集合。,7,二叉树的定义,二叉树是另一种树形结构：,Binary_Tree =( D,R),其中:,D 是具有相同性质的数据元素的集合;,R 是在D上某个两元关系的集合,且满足:,D中存在唯一称为根的数据元素,没有前趋;,D中其余元素都有且仅有一个前趋;,每个结点至多只有两个子树;,D中元素,或有两个互不相交后继,或无后继;,左、右子树分别又是一棵二叉树。,8,二叉树的五种基本形态,（a）,（b）,（c）,（d）,（e）,O,空结点,O,单个结点,O,O,右子树为空的二叉树,O,O,左子树为空的二叉树,左、右子树非空的二叉树,O,O,O,9,二叉树与树的区别,表达形式（对3个结点）,普通树,二叉树,（a） （b） （c） （d） （e）,O,O,O,O,O,O,有两种不同形式,（a）,（b）,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,有五种不同形式,10,二叉树与树的区别（二）,观念,二叉树的子树有顺序关系，分左子树和右子树，而树则无此区分,；,二叉树的分支度一定为0、1或2，而树的度可大于2。,11,特殊二叉树,满二叉树,完全二叉树,平衡二叉树,二叉排序树,12,满二叉树,当二叉树每个分支结点的度都是,2,，且所有叶子结点都在同一层上，则称其为满二叉树。,若,k,为二叉树,T,的深度，且,T,中共有,2,k,-1,个结点（,k,1,），,则称,T,为满二叉树。,（,a,）,满二叉树 （,b,）,非满二叉树,O,O,O,O,O,O,O,O,O,O,O,O,O,13,完全二叉树,从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树。,（,a,）,完全二叉树 （,b,）,非完全二叉树,O,O,O,O,O,O,O,O,O,O,O,叶结点只可能出现在层次最大的两层上。,14,平衡二叉树,二叉树上任一结点的左子树深度减去右子树深度的差值，称为该结点的平衡因子。,任意结点左、右子树的深度之差的绝对值,1,，,这样的树称为平衡二叉树。,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,（a）平衡二叉树 （b）非平衡二叉树,15,二叉排序树定义,二叉排序树,或者是空二叉树；,或者是：,左子树上所有结点的值均小于根结点的值；,右子树上所有结点的值均大于等于根结点的值；,左、右子树本身又是一棵二叉排序树。,10,5,7,11,14,18,15,15,14,18,5,10,12,13,7,（a）二叉排序树 （b）非二叉排序树,16,二叉树的性质一,二叉树的第i层上至多有2,i-1,个结点（ i,1）。,利用归纳法证明：,i=1时，只有一个结点，对的；,假设对所有的j，1,j,i，命题成立，,即在第j层上，至多有2,j-1,个结点。,由归纳假设，第i-1层上至多有2,i-2,个结点。由于二叉树的每个结点的度至多为2，故第i层上的最大结点数为第i-1层上的最大结点数的2倍，即 22,i-2,= 2,i-1,。,17,二叉树的性质二,深度为h的二叉树上至多含2,h,-1个结点(h1)。,i=1,h,（第i层上的最大结点数）,h,i=1,=, 2,i-1,= 2,h,-1,证明：,由性质一可见，深度为,h,的二叉树的最大结点数为：,18,包含n(n0)个结点的二叉树总的分支数为n-1。,二叉树的性质三,证明：,二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支，因此二叉树总的分支数为n-1。,O,O,O,O,O,O,O,O,O,O,O,O,O,19,任意二叉树，若含有n,0,个叶结点、n,2,个度为2的结点，则必存在关系式n,0,=n,2,+1 。,二叉树的性质四,证明：设二叉树含有n,1,个度为1的结点，则二叉树结点总数显然为：,n,0,+ n,1,+ n,2,（2-2）,再看树的分支数，n,2,个度为2的结点必然有2n,2,个分支，n,1,个度为1的结点必然有n,1,个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为：,1 + n,1,+ 2n,2,（2-3）,由（2-2）和（2-3）两式可知：n,0,=n,2,+1,20,具有n个结点的完全二叉树的深度为 log,2,(n)+1。,二叉树的性质五,证明：,假设二叉树的深度为h，,则必有2,h-1,-1n2,h,-1，,于是有2,h-1,n+12,h,，也就是 2,h-1,n2,h,，,从而得到h-1log,2,(n)n，则该结点无左孩子。否则，编号为2i的结点为其左孩子结点；, 若2i+1n，则该结点无右孩子。否则，编号为2i+1的结点为其右孩子结点。,证明：通过对i进行归纳即可得证。,二叉树的性质六,22,验证性质六,1,4,3,2,5,6,1 2 3 4 5 6,1 2 3 4 5 6,第,i,个结点就存放在第,i,个位置上；,第,i,个结点（,i1),的父结点就存放在第,i/2,个位置,;,第,i,个结点的左子结点就存放在第,2*i,的位置,;,右子存放在第,2*i+1,的位置（,若,2i+1,n,）。,23,二叉树的链式存储,结点定义：,struct BinTreeNode ,ElemType data;,struct BinTreeNode *leftChild, *rightChild;,;,struct BinTreeNode *root; / 定义根结点指针,这里leftChild和rightChild分别为某一结点指向其左孩子和右孩子的指针。对于叶结点或一个新生成的结点而言，其左孩子和右孩子指针都为空值。,24,二叉树的链式存储,A,B,C,D,E,利用这种结点形式存储的树一般称为二叉链表。从根结点出发，可以访问二叉树的任何结点。,为了能够访问二叉树，必须保留指向根结点的指针,。这和单链表必须保留头指针的道理一样。,25,二叉树的遍历,遍历（Traversing）是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。,遍历的方法很多，常用的有：,前序法（PreOrder）,中序法（InOrder）,后序法（PostOrder）,26,前序法（PreOrder）,方法描述：,从根结点,a,开始访问，,接着访问左子结点,b,，,最后访问右子结点,c,。,即：,根,左子,右子,a,b,c,遍历,序列,a b c,27,中序法（InOrder）,方法描述：,从左子结点,b,开始访问，,接着访问根结点,a,，,最后访问右子结点,c,。,即：,根,左子,右子,a,b,c,遍历,序列,b a c,28,后序法（PostOrder）,方法描述：,从左子结点b开始访问，,接着访问右子结点c，,最后访问根结点a。,即：,根,左子,右子,a,b,c,遍历,序列,b c a,29,二叉树的遍历举例,o,o,o,o,o,o,o,o,o,A,B,C,D,E,F,G,H,I,前序遍历序列：,中序遍历序列：,后序遍历序列：,DGEBHIFCA,DBGEACHFI,ABDEGCFHI,30,二叉树遍历算法（递归、前序法,）,void PreOrder(BinTreeNode *t),if (t),Visit( t );,/访问根结点,PreOrder( t-leftChild );,/遍历左子树,PreOrder( t-rightChild );,/遍历右子树,A,B,C,D,E,F,前序遍历二叉树的序列为：,A B C D E F,31,二叉树遍历算法（递归、前序法验证）,打印A,取A,.左子(B),打印B,取B,.左子(C),打印C,取C,.左子(空),取C,.右子(空),取B,.右子(D),打印D,取D,.左子(E),打印E,取E,.左子(空),取E,.右子(空),取D,.右子(F),打印F,取F,.左子(空),取F,.右子(空),取A,.右子(空),结束,A,B,C,D,E,F,A,TOP,A,TOP,B,A,TOP,B,A,TOP,B,C,A,TOP,D,A,TOP,D,E,A,TOP,D,A,TOP,F,A,TOP,32,（2）中序遍历,对一颗非空二叉树进行中序遍历时，首先按中序遍历方式访问左子树，然后访问根结点，最后按中序遍历方式访问右子树。中序遍历算法如下：,void InOrder(BinTreeNode *t),if(t),InOrder( t-leftChild ); /,遍历左子树,Visit( t ); /,访问根节点,InOrder( t-rightChild ); /,遍历右子树,33,（3）后序遍历,对一颗非空二叉树进行中序遍历时，首先按,后序遍历,方式访问左子树，然后,按后序遍历,方式访问右子树，最后访问根结点。,后序遍历,算法如下：,void PostOrder(BinTreeNode *t),if(t),PostOrder( t-leftChild ); /,遍历左子树,PostOrder( t-rightChild ); /,遍历右子树,Visit( t ); /,访问根节点,34,表达式树及应用,在计算机中对表达式进行分析和计算是一项重要的任务。,举例，用二叉树表示表达式：,a + b *,（,c - d,）,前序遍历序列：,中序遍历序列：,后序遍历序列：,分析：,每个叶结点为运算对象；,每个非叶结点为运算符；,每个子树对应一个子表达式。,表达式处理一般采用后序法，也称“逆波兰”法。,表达式处理规则：,见运算数入栈；,见运算符，取两个栈顶元素运算后再压栈；,直到处理结束。,e,f,b,c,d,a,35,表达式树应用举例,（1） a b c d 入栈,d,c,b,a,（1）,（2）,c - d,b,a,（3）,b*（c-d）,a,a+b*（c-d）,（4）,（5）,a+b*（c-d）,f,e,（6）,e/f,a+b*（c-d）,（7）,a+b*（c-d）- e/f,（2）遇-，c d 出栈， 运算后再压栈；,（3）遇*，（c - d）和 b 出栈，运算后再压栈；,（4）遇+，b*（c-d）和a出栈，运算后再压栈；,（5）e f 入栈,（6）遇/，f e 出栈，,运算后再压栈；,（7）遇-，a+b*（c-d）,和e/f出栈，运算后再压栈。,36,图的基本概念,图的来源,：通信网、交通网等，它表现了数据对象间多对多的联系。在该结构中，数据元素一般称为顶点,。,图的定义：,图是对结点的前趋和后继个数不加限制的,一种,数据结构，它,是由顶点集合及顶点间的关系集合组成。一般记作:,Graph( V, E ),其中:,V,是顶点的有限非空集合；,E,是顶点之间关系的有限集合。,37,图例,设图G1 = （V，E）,V=v,1,，v,2,，v,3,，v,4,E=（v,1,，v,2,），（v,1,，v,3,），,（v,2,，v,1,），（v,2,，v,3,），,（v,2,，v,4,），（v,3,，v,1,），,（v,3,，v,2,），（v,4,，v,2,）,o,o,o,o,v,1,v,2,v,3,v,4,G1,38,有向图、无向图,有向图（Digraph）,图G中顶点的偶对若是有向的，称为有向图。如图G2所示。为示区别，,其偶对用表示。,例 G2=（V，E）,V= 1，2，3，4,E=1，2,1，3，,3，4,4，1,无向图（Undigraph）,图G中顶点的偶对若是无向的，称为无向图，其偶对用（v,x,，v,y,）表示，如图G1所示。,1,3,2,4,G2,o,o,o,o,v,1,v,2,v,3,v,4,G1,39,边、弧,边（Edge）,顶点间的关系可描述为顶点的偶对，也称为顶点的边。记为：（Vx，Vy）。边是无序的，可看成是（Vx，Vy），也可看成是（Vy，Vx）。,弧（Arc）,若顶点间的边是有方向性（有序）的，则称该偶对为弧。记为：Vx，Vy。弧是有序的，Vx，Vy表示从Vx到Vy。,弧头（Head）,弧的终点（,TerminaL Node,）称为弧头（方向前方）。,弧尾（Tail）,弧的起始点（,Initial Node,）称为弧尾（方向后方）。,弧,Vx，Vy,表示为，,弧尾 弧头,Vx Vy,40,顶点、邻接点,顶点（Vertex）,图中的数据元素（结点）称为顶点。如图G1、G2中的,1,、,2,，1，2。,邻接点（Adjacent）,无向图中,若边（,x,y,）, E，则,x,和,y,互为邻接点;有向图中，若弧,x,y, E，则,y,是,x,的邻接点，反之，不是。,Vx,Vy,x、y互为邻接点,Vx,Vy,y是x的邻接点,41,顶点的度（Degree）,无向图中，顶点的,度,是以该顶点为一个端点的边的条数。例如，,G1,中,V,2,的度为,3,，,V,4,的度为,1,。,有向图中，以某顶点为弧头的弧的数目称为该顶点的,入度（,Indegree,）,。,例如,G2,中顶点,1,的入度为,1,。以某顶点为弧尾的弧的数目称为该顶点的,出度（,Outdegree,）,。,例如,G2,中顶点,1,的出度为,2,。该顶点的度,=,入度,+,出度。例如，,G2,中顶点,1,的度,=2+1=3,。,o,o,o,o,v,1,v,2,v,3,v,4,G1,1,3,2,4,G2,42,路径、长度,路径（Path）,在图中，从顶点Vx到顶点Vy的顶点序列（Vx，V,1,，V,2,，,V,n,Vy)称为从Vx到Vy的路径。路径可能是不唯一的。例如，G1中，V,1,到V,3,的路径为：（V,1,V,2,V,3,）或（V,1,V,3,）；而G2中，1到4的路径为。,长度（Length）,路径的长度是该路径上边或弧的数目。例如，G1中V,1,到V,3,的长度为1或2；而G2中1到4的长度为2。,1,3,2,4,G2,o,o,o,o,v,1,v,2,v,3,v,4,G1,43,连通图、强连通图、连通分量,连通图（Connected Graph）,在无向图中，若每一对顶点间都有路径，称此图是连通图。如图G3所示。,连通分量（Connected Component）,无向图中的极大连通子图称为连通,分量。,强连通图（Strongly Connected Graph）,在有向图中，若每对顶点Vx到Vy间都存在Vx到Vy，及从Vy到Vx的路径，则称此图是强连通图。如图G4所示。,1,2,3,4,5,G3,2,1,3,4,5,G4,44,子图、生成树,子图,有两个图G和G1，若V1,V，E1 E，即V1中的顶点,都属于V中的顶点，E1中的关系都属于E中的关系，则称G1是G的子图。G =（V，E），G1=（V1，E1）,（图的部分顶点和部分边组成的图）,生成子图、生成树,设G是一个连通图，G中任一包含G的所有顶点的子图称为生成子图。如果该子图是树，则称为G的生成树。G的生成树不是唯一的。一棵有n个顶点的生成树，有且仅有n-1条边（弧）。,（子图包含所有顶点，但不一定包含所有边）,45,网、权,权（Weight）,若图的边或弧带有与之相关的数，称此数为该边或弧的权。权通常用来表示从一个顶点到另一个顶点的距离或费用。,网（Network）,带权的图称为网。如G5为带权的网。,V,1,V,2,V,3,V,4,G5,2,3,5,7,46,图的存储方式,1邻接矩阵,利用数组实现的。它利用一维数组存储顶点信息，利用二维数组存储顶点间边或弧的信息。此二维数组又称,邻接矩阵,。,邻接矩阵存储方式可用于无向图或有向图。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。,47,图的邻接矩阵存储可用下面结构体表示：,#define MAX_NUM 100,/最大顶点个数,typedef struct ,VertexType vexsMAX_NUM;,/顶点信息数组,ArcType MatrixMAX_NUMMAX_NUM;,/邻接矩阵,int vexnum,arcnum;,/图实际顶点数和弧(边)数,int kind;,/图种类标志,1有向图,2有向网 / 3无向图,4无向网, MGraph;,其中:ArcType是顶点关系的数据类型。,VertexType是顶点的数据类型。,MAX_NUM表示最多可存的顶点数。,48,假设无向图G=(V,E)是一个有n个顶点的图，则图的邻接矩阵A是n阶方阵，其内容如下：,其中W(i,j)是与边或弧相关的权。,对于含权的网络而言，其邻接矩阵可定义如下：,49,0,1,3,2,5,2,8,1,3,0,1,2,3,4,1,0,2,3,4,(a)无向图 (b)有向图 (c)网络,0,1,3,2,4,0,1,3,2,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,0,1,3,2,(a)无向图邻接矩阵 (b)有向图邻接矩阵 (c)网络邻接矩阵,邻接矩阵举例,50,2邻接表,邻接表存储形式是一种链表与数组结合的存储形式。在邻接表中有两种结点，一种是头结点，另一种是表结点。,（1）头结点存储一个顶点的详细信息，为了便于管理，所有头结点都存放在一个数组中。,（2）对于某个顶点而言，需要将所有与它邻接的顶点存储为表结点形式，并将它们链接成单链表，这个单链表就称为该顶点的邻接表。,（3）还要在每个顶点的头结点中存储指向其邻接表首元结点的指针。,51,邻接表的结点结构,(c)网络的表结点：,info,next,adjvex,next,adjvex,first,Vexdata,(a)头结点,(b)无权图的表结点：,顶点V,i,的邻接点,与边或弧有关的权值,存放V,i,信息,指向V,i,单链表的第一个结点,指向V,i,的下一个邻接点的指针,顶点V,i,的邻接点,指向V,i,的下一个,邻接点的指针,52,邻接表的举例,无向图中V,i,的度是第i个单链表的长度。,53,逆邻接表,为求顶点,V,i,的入度，对每个顶点,V,i,，,建立一个链接,以,V,i,为弧头的邻接点链表，称该表为逆邻接表。,显然逆邻接表的单链表中结点的个数就是顶点,V,i,的,入度。,邻接表中第i个单链表的长度是顶点V,i,的出度。,逆邻接表中第i个单链表的长度是顶点V,i,的入度,54,图的邻接表描述,#define MAX_NUM 100 /,顶点最大允许数量,struct AdjNode /,表结点类型定义,int adjvex; /,该邻接点在数组中的位置,InfoType info; /,该弧相关信息,struct AdjNode *next; /,指向下一邻接点的指针,;,typedef struct VNode /,头结点类型定义,VertexType data;,/,顶点信息,AdjNode *first; /,指向邻接表第一个结点, AdjListMAX_NUM;,55,typedef struct ,AdjList headArray; /,头结点数组,int vexnum, arcnum; /,图的当前顶点数和弧数,int kind; /,图的种类标志, ALGraph;,其中：,AdjNode,为表结点；,InfoType,为与边相关信息的数据类型（包括权等）；,VNode,为头结点；,VertexType,是顶点的数据类型；,MAX_NUM,表示最多可以存放的顶点个数。,56,图的遍历,图的遍历（,Traversing Graph,）,从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访问一次，该过程为图的遍历。,图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点就不相同，路径也就不同。,因为图中元素是“多对多”的关系，为避免发生重复，设立一个辅助数组,visited,，,每访问一个顶点，便将其状态,visitedi,置为“真”。,57,图的遍历方法,常用的图的遍历方法有两种：,深度优先遍历法,广度优先遍历法,58,深度优先遍历法,算法思想：,step1,从图中某个顶点V,0,出发，并访问此顶点；,step2,从V,0,出发，访问与V,0,邻接的顶点V,1,后，再从V,1,出发，访问与V,1,邻接且未被访问过的顶点V,2,。重复上述过程，直到不存在未访问过的邻接点为止。,step3,如果是连通图，从任一顶点V,0,出发，就可以遍历所有相邻接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作为出发点，重复step1、step2，直到全部被访问过的邻接点都被访问为止。,59,深度优先遍历法举例,遍历过程 访问顶点 所过边,起始顶点,V1 V,1,V1,的第,1,个邻接点,V3 V,3,（,V,1,，,V,3,）,V3,的第,1,个邻接点,V1,已访问，,取下一个邻接点,V5 V,5,（,V,3,，,V,5,）,V5,的第,1,个邻接点,V3,已访问，,取下一个邻接点,V2 V,2,（,V,5,，,V,2,）,V2,的两个邻接点均被访问，,回退到,V5,，,V5,的邻接点均被访问，,回退到,V3,，,V3,的邻接点均被访问,，,回退到,V1,，,V1,的另一个邻接点,V4,未被访问,V,4,（,V,1,，,V,4,）,V4,的第一个邻接点,V1,已被访问，,另一个邻接点,V6,未被访问,V,6,（,V,4,，,V,6,）,V6,的邻接点被访问，回退到,V4,V4,的邻接点均被访问,回退到,V1,，,返回到出发点，遍历结束。,V,1,V,3,V,5,V,4,V,6,G6,V,2,示例,60,遍历产生的结果,深度优先遍历,G6,所走过的序列：,V,1,V,3,V,5,V,2,V,4,V,6,V,1,V,3,V,5,V,2,V,4,V,6,所走过的边：,（,V,1,，,V,3,）,（,V,3,，,V,5,）,（,V,5,，,V,2,）,（,V,1,，,V,4,）,（,V,4,，,V,6,）,遍历生成树,61,62,bool visitedMAX; /顶点访问标志数组,void DFSTraverse(ALGragh G),for(int i=0;iG.vexnum;i+) visitedi =FALSE;,for(int i=0;iG.vexnum;i+) if( ! visitedi ) DFS(G,i) ;,void DFS(ALGraph G, int v) /从v顶点出发,递归深度优先遍历,图G,AdjNode *p;,visitedv = TRUE;,coutvnext ),if(!visitedp-adjvex),DFS(G,p-adjvex);,63,深度优先遍历算法程序(非递归),Void Traver_dfs(ALGragh G,int v),int stackN,visitedN, top=-1 ; AdjNode *p;,for (int i=0;iN;i+) visitedi= FALSE;,coutvadjvex) p=p-next;,else,coutadjvex.dataadjvex= TRUE ; top+;,stacktop=p-adjvex;,p=Gp-adjvex.first;,if( top !=-1),v=stacktop; top- -; p=Gv.first;,p=p-next;,64,广度优先遍历算法,广度优先遍历法首先访问第,1,个顶点所有邻接点，再访问下一个顶点所有未被访问的邻接点。,算法思想：,step1,从图中某个顶点,V,0,出发，并访问此顶点；,step2,从,V,0,出发，访问,V,0,的各个未曾访问的邻接点,W,1,，,W,2,，,W,k,;,然后,依此从,W,1,W,2,W,k,出发访问各自未被访问的邻接点。,step3,重复,step2,，,直到全部顶点都被访问为止。,65,广度优先遍历法举例,遍历过程 访问顶点 所过边,起始顶点,V,1,V,1,访问,V,1,的未被访问过的,所有邻接点,V,3,V,2,V,4,（,V,1,V,3,）,(V,1,V,2,),(V,1,V,4,),访问,V,3,的未被访问过,的所有的邻接点,V,5,（,V,3,V,5,）,访问,V,2,的未被访问过,的所有的邻接点,无,访问,V,4,的未被访问过,的所有的邻接点,V,6,(V,4,V,6,),所有顶点已被访问,结束。,V,1,V,3,V,5,V,4,V,6,G6,V,2,示例,66,遍历产生的结果,广度优先遍,历,G6,所走过的序列：,V,1,V,3,V,2,V,4,V,5,V,6,V,1,V,3,V,5,V,2,V,4,V,6,所走过的边：,（,V1,，,V3,），（,V1,，,V2,），（,V1,，,V4,），,（,V3,，,V5,），（,V4,，,V6,）,遍历生成树,67,程序举例,图的深度优先遍历和广度优先遍历。,V,1,V,3,V,5,V,4,V,6,G6,V,2,深度优先遍历序列：,V,1,V,3,V,5,V,2,V,4,V,6,广度优先遍历序列：,V,1,V,3,V,2,V,4,V,5,V,6,1,3,2,4,G2,深度优先遍历序列：,1 3 4 2,广度优先遍历序列：,1 3 2 4,示例,68,树和图的应用,哈夫曼树和哈夫曼编码,最小生成树,69,哈夫曼树和哈夫曼编码,设计二进制编码方案时要考虑不同字符的使用频率，使用频率高的字符编码应当尽量短一些。但是仅仅考虑使用频率也是不够的。,例如：某个文件由A、B、C、D 4个字符组成，其中A用得最多，C次之。,方案1: A1 C 0 B 10 D 11,那么象1100这样的二进制数据具有二义性，既代表AACC，又可代表ABC，还可代表DCC。,为了不使二进制编码具有二义性，每个字符编码都不能与其他字符编码的前面若干位重合。,70,B,D,C,A,0,0,1,1,A,B,0,1,D,C,0,0,1,1,(a)有二义性的编码系统对应的二叉树 (b)无二义性的编码系统对应的二叉树,任何一个无二义性的二进制字符编码系统必然与这样一颗二叉树对应：该二叉树的叶子结点对应着所有需要转换的字符，并且按照左分支代表0、右分支代表1的规则，从根到该叶子的分支对应的0、1序列就构成叶子对应字符的二进制编码。,可以利用二叉树分析字符编码问题。假设二叉树中的左分支代表0，右分支代表1，则不论字符是采用何种0、1组合形式构成的编码，它必然对应某个二叉树中一个结点,。,71,1）假设每个字符使用频率是相等的，那么不同字符的编码长度之和就可衡量编码系统的优劣。,2）如果每个字符使用频率不相等，那么将不同字符的编码长度乘上其使用权值再加起来，也可衡量编码系统的优劣。即用根到每个叶子的路径长度乘以叶子对应字符的使用权值再加起来作为衡量标准，,显然这种加权和除以字符总数就是每个字符的加权平均编码长度。,72,二叉树带权路径长度,：设二叉树有n个带有权值的叶子结点，每个叶子到根的路径长度乘以其权值之和称为二叉树带权路径长度。一般记作：,其中，,w,i,为第,i,个叶子的权重，,l,i,为第,i,个叶子到根的路径长度。,哈夫曼树：,以一些带有固定权值的结点作为叶子所构造的，具有,最小,带权路径长度的二叉树称为哈夫曼树,。,Huffman树也称为最优树，是一类带权路径最短的二叉树。,73,Huffman树举例,以下有三棵树：,（a）,（b）,（c）,a,b,c,d,a,b,c,d,a,c,b,d,7,7,7,5,5,5,2,2,2,4,4,4,WPL,a,=7x2+5x2+2x2+4x2,= 36,WPL,b,=7x3+5x3+2x1+4x2,= 46,WPL,c,=,7x1+5x2+2x3+4x3,= 35,事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。,74,应用举例,由统计规律可知，考试成绩的分布符合正态分布：,-1,1,0,分数 059 60 69 70 79 80 89 90 100,比例数 0.05 0.15 0.40 0.3 0.10,根据正态分布规律，在60,90之间的分数占85%，而不及格和优秀是少数。,75,将百分制转换成五分制,判定树比较：,a60?,a70?,a80?,a90?,不及格,及格,中等,良好,优秀,Y,Y,Y,Y,N,N,N,N,a80?,a70?,a90?,a60?,不及格,优秀,良好,中等,中等,及格,不及格,Y,Y,Y,N,N,N,N,Y,Y,(A),(B),若输入,1,万个数据，按,A,的判定过程进行操作，约需比较,3.2,万次，而按,B,比较,则仅需,2.2,万次。,76,构造Huffman树,构造Huffman树算法步骤：,Step1,将n个带权值w,i,（in）的结点构成n棵二叉树的集合T=T,1,，T,2,，T,n,，每棵二叉树只有一个根结点。,Step2,在T中选取两个权值最小的结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和；,Step3,在T中删除这两棵树，将新构成的树加入到T中；,Step4,重复2）、3）步的操作，直到T中只含一棵树为止，该树就是Huffman树。,77,假定有一段报文由a、b、c、d四个字符构成，它们的使用频率比为6421，则用a、b、c、d作为叶子结点构造哈夫曼树的过程如图所示。,若二叉树中的左分支代表0，右分支代表1,则a、b、c、d的哈夫曼编码分别为0、10、110、111。,78,构造Huffman树举例,以权值分别为,7,，,5,，,2,，,4,的结点,a,、,b,、,c,、,d,构造,Huffman,树。,T= a b c d ,c,d,T,3,2,4,6,b,T,3,T,2,6,5,11,b,T,2,6,5,11,c,d,2,4,11,18,a,T,2,7,T,1,6,18,a,7,T,1,b,T,3,T,2,5,11,18,a,7,T,1,b,5,11,c,d,2,6,4,（d）T= T,1,（c）T= a T,2,（b）T= a b T,3,（a）T= a b c d ,代入T,2,代入T,3,代入T,1,示例,79,Huffman编码,编码,：,用二进制数的不同组合来表示字符的方法。,前缀编码,：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。,a,0,b,0,1,c,d,0,1,1,编码：a（0）,b（01）,c（011）,d（111）,方法约定：,1）左分支为0,2）右分支为1,3）,由叶到根,路径上字符组成的二进制串就是该叶结点的编码。,Huffman编码,：一种非等长度的编码。以给定权值的结点构造Huffman树，按二进制前缀编码的方式构成的编码为Huffman编码。,80,Huffman编码举例,在某系统的通信联络中可能出现,8,种字符，其频率分别为,0.05,、,0.29,、,0.07,、,0.08,、,0.14,、,0.23,、,0.03,、,0.11,，设权值分别为,5,，,29,，,7,，,8,，,14,，,23,，,3,，,11,，,n=8,，其,Huffman,树为：,0,0,0,0,0,0,0,1,1,1,1,1,1,1,5,3,7,8,14,29,11,23,42,58,100,Huffman编码为：,A 5 0110,B 29 01,C 7 0111,D 8 1111,E 14 011,F 23 00,G 3 1110,H 11 010,81,【,例2-5,】,假定编码系统中有五个字符X、S、D、E、A，它们的使用频率比为29578，以这些频率值作叶子的权构造哈夫曼树，并输出哈夫曼编码。,2,5,7,o,o,o,o,8,9,o,o,o,o,o,0,0,1,1,1,0,0,1,82,最小生成树,该问题是构造连通图的最小代价生成树问题。一棵生成树的代价就是树上各边（弧）的代价之和。,考虑一个通信网的建设问题。,若要在,n,个城市间建立通信联络网，则只需,n-1,条线路。但在,n,个城市间，最多可能架设,n*,（,n-1,）,/2,条线路，选择哪,n-1,条线路，使费用最少。,普里姆（,Prim,）,算法,克鲁斯卡尔（,Kruskal,）,算法,83,实例,84,（1）普里姆算法,假定G= V, E 为连通网络，其中V为顶点集合，E为带权边集合。设置生成树顶点集合U，最初它只包含某一个顶点。设置生成树边集合T，最初为空集。而后考察这样的边，它的一个顶点uU，另一个顶点vV-U，每次从所有这样的边中选择权值最小的边(u, v)加入集合T，并把顶点v加入到集合U中。如此不断重复，直到所有顶点都加入到集合U中为止。,85,86,普里姆（Prim）算法举例,1,2,3,4,5,6,8,7,2,1,4,3,5,7,6,8,11,10,9,12,U=1，V-U=2，3，4，5，6，7，8,1,2,2,1,2,4,2,1,4,7,3,（1）,（2）,（3）,(1) U=1,2,V-U=3,4,5,6,7,8,(2) U=1,2,4,V-U=3,5,6,7,8,(3) U=1,2,4,7,V-U=3,5,6,8,例子,87,普里姆（Prim）算法举例(续),4,7,5,3,5,（4）,7,6,（5）,6,(4) U=1,2,4,7,5 , V-U=3,6,8,(5) U=1,2,4,7,5,6, V-U=3,8,(6) U=1,2,4,7,5,6,3, V-U=8,(7) U=1,2,4,7,5,6,3,8), V-U= ,4,3,（7）,8,3,6,5,4,7,2,2,1,3,6,5,8,9,1,5,5,（6）,4,7,6,3,6,3,5,5,8,88,89,（2）克鲁斯卡尔算法,假定G= V, E 为连通网络，其中V为顶点集合，E为带权边集合。先构造一个包含所有顶点，没有边的非连通图T= V, ，图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在T的不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。,90,克鲁斯卡尔（Kruskal）算法举例,1,2,3,4,5,6,1,5,2,4,6,6,3,5,5,6,2,5,1,3,4,6,1,2,3,(4),1,3,1,1,4,6,2,(3),1,2,3,4,5,6,(1),1,3,(2),1,1,91,克鲁斯卡尔（Kruskal）算法举例(续）,1,2,3,4,5,6,(5),1,2,3,4,1,2,3,4,5,6,1,5,2,4,6,6,3,5,5,6,1,3,2,5,6,4,1,2,4,3,5,（6）,例子,92,结束语,欢迎参加到中心网站,软件开发技术基础,课程的学习讨论中来。,中心网址：,http:/,课件下载地址,:,我的,E-mail,地址,:,答疑安排：,每星期五下午,：,3:00,6:00,地点： 计教中心,505,房间,93,