(课件)第2章非数据结构树和图

1、下一页上一页停止放映 西安交通大学计教中心西安交通大学计教中心下一页上一页停止放映第2页/91树形结构树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在，并应用于：人类社会的族谱、家谱、行政区域划分管理；各种社会组织机构；在计算机领域中，用树表示源程序的语法结构；在os中，文件系统、目录等组织结构也是用树来表示的。下一页上一页停止放映第3页/91树的逻辑结构树是一种数据结构，可用二元组表示为： tree=（d，r）其中：d 是具有相同特性的数据元素的集合；r 是数据元素间逻辑关系的集合，且满足：在d中存在唯一的称为根的数据元素，没有前趋；d中其余数据元素都有且只有一个前趋；d中

2、所有元素，或有若干个互不相同的后继（子树），或无后继（叶结点）； 则称tree为树。下一页上一页停止放映第4页/91树的递归定义: gacfdeb下一页上一页停止放映第5页/91树结构举例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.3c3书目录 目录树 树结构下一页上一页停止放映第6页/91与树相关的术语 结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。 结点的度：结点拥有的非空子树的个数。 树的度：树中所有结点的度的最大值。 叶子结点：度为0的结点。

3、分支结点：至少有一个非空子树的结点。 孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。下一页上一页停止放映第7页/91 兄弟结点：具有相同父结点的结点互为兄弟结点。 结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。 树的深度：树中结点所在的最大层次。 有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。 森林：由零棵或有限棵互不相交的树组成的集合。 下一页上一页停止放映第8页/91二叉树的定义二叉树是另一种树形结构： binary_tree =( d,r) 其中:

4、d 是具有相同性质的数据元素的集合; r 是在d上某个两元关系的集合,且满足:d中存在唯一称为根的数据元素,没有前趋;d中其余元素都有且仅有一个前趋;每个结点至多只有两个子树;d中元素,或有两个互不相交后继,或无后继;左、右子树分别又是一棵二叉树。下一页上一页停止放映第9页/91二叉树的五种基本形态二叉树的五种基本形态 （a）（b）（c）（d）（e）o 空结点空结点 o 单个结点单个结点oo右子树为空右子树为空的二叉树的二叉树oo左子树为空左子树为空的二叉树的二叉树左、右子左、右子树非空的树非空的二叉树二叉树ooo下一页上一页停止放映第10页/91二叉树与树的区别二叉树与树的区别 表达形式（对

5、3个结点） 普通树 二叉树 （a） （b） （c） （d） （e） oooooo有两种不同形式有两种不同形式（a）（b b）ooooooooooooooo有五种不同形式有五种不同形式下一页上一页停止放映第11页/91二叉树与树的区别（二）二叉树与树的区别（二） 观念二叉树的子树有顺序关系，分左子树和右子树，而树则无此区分；二叉树的分支度一定为0、1或2，而树的度可大于2。下一页上一页停止放映第12页/91特殊二叉树特殊二叉树满二叉树完全二叉树平衡二叉树二叉排序树下一页上一页停止放映第13页/91满二叉树满二叉树q当二叉树每个分支结点的度都是当二叉树每个分支结点的度都是2 2，且所有叶子，且所有

6、叶子结点都在同一层上，则称其为满二叉树。结点都在同一层上，则称其为满二叉树。q若若k k为二叉树为二叉树t t的深度，且的深度，且t t中共有中共有2 2k-1-1个结点个结点（k k 1 1），则称），则称t t为满二叉树。为满二叉树。（a） 满二叉树 （b）非满二叉树 oooo o oooooooo下一页上一页停止放映第14页/91完全二叉树完全二叉树q从满二叉树叶子所在的层次中，自右向从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被左连续删除若干叶子所得到的二叉树被称为完全二叉树。称为完全二叉树。（a）完全二叉树 （b） 非完全二叉树ooooooooooo叶结点只可能

7、出现在层次最大的两层上。下一页上一页停止放映第15页/91平衡二叉树平衡二叉树二叉树上任一结点的左子树深度减去右子树深度的差值，称为该结点的平衡因子。任意结点左、右子树的深度之差的绝对值1 ，这样的树称为平衡二叉树。ooooooo ooooooooo（a）平衡二叉树 （b）非平衡二叉树下一页上一页停止放映第16页/91二叉排序树定义二叉排序树定义二叉排序树或者是空二叉树；或者是：左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均大于等于根结点的值；左、右子树本身又是一棵二叉排序树。 10571114181515141851012137（a）二叉排序树 （b）非二叉排序树下一页上一页停

8、止放映第17页/91二叉树的性质一二叉树的性质一 二叉树的第i层上至多有2i-1个结点（ i 1）。利用归纳法证明：i=1时，只有一个结点，对的；假设对所有的j，1 j i，命题成立， 即在第j层上，至多有2j-1 个结点。由归纳假设，第i-1层上至多有2i-2 个结点。由于二叉树的每个结点的度至多为2，故第i层上的最大结点数为第i-1层上的最大结点数的2倍，即 22i-2 = 2i-1。下一页上一页停止放映第18页/91二叉树的性质二二叉树的性质二深度为深度为h的二叉树上至多含的二叉树上至多含2h-1个结点个结点(h1)。i=1h （第（第i i层上的最大结点数）层上的最大结点数） hi=1

9、= = 2 2i-1i-1 = 2 = 2h h-1-1证明：证明：由性质一可见，深度为h的二叉树的最大结点数为：下一页上一页停止放映第19页/91包含包含n(n0)个结点的二叉树总的分支数为个结点的二叉树总的分支数为n-1。二叉树的性质三二叉树的性质三证明：证明： 二叉树中除了根结点之外每个元素有且只有一二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子结点与父结点间有且只有个父结点。在所有子结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支，一个分支，即除根外每个结点对应一个分支，因此二叉树总的分支数为因此二叉树总的分支数为n-1。oooo o oooooooo下一页上一

10、页停止放映第20页/91 任意二叉树，若含有任意二叉树，若含有n0个叶结点、个叶结点、n2个度为个度为2的结点，则必存在关系式的结点，则必存在关系式n0=n2+1 。二叉树的性质四二叉树的性质四证明：设二叉树含有证明：设二叉树含有n1个度为个度为1的结点，则二叉的结点，则二叉树结点总数显然为：树结点总数显然为：n0 + n1 + n2（2-2）再看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为： 1 + n1 + 2n2（2-3）由（2-2）和（2-3）两式可

11、知：n0=n2+1下一页上一页停止放映第21页/91 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2(n)+1。二叉树的性质五二叉树的性质五证明：证明： 假设二叉树的深度为假设二叉树的深度为h， 则必有则必有2h-1-1n2h-1， 于是有于是有2h-1n+12h，也就是，也就是 2h-1n2h， 从而得到从而得到h-1log2(n)n，则该结点无左孩子。否则，编号，则该结点无左孩子。否则，编号为为2i的结点为其左孩子结点；的结点为其左孩子结点； 若若2i+1n，则该结点无右孩子。否则，编，则该结点无右孩子。否则，编号为号为2i+1的结点为其右孩子结点。的结点为其右孩

12、子结点。证明：通过对证明：通过对i进行归纳即可得证。进行归纳即可得证。二叉树的性质六二叉树的性质六下一页上一页停止放映第23页/91验证性质六验证性质六 143256 1 2 3 4 5 6 1 2 3 4 5 6 第第i i个结点就存放在第个结点就存放在第i i个位置上；个位置上；第第i i个结点（个结点（i1)i1)的父结点就存放在第的父结点就存放在第 i/2i/2个位置个位置; ;第第i i个结点的左子结点就存放在第个结点的左子结点就存放在第2 2* *i i的位置的位置; ;右子存放在第右子存放在第2 2* *i+1i+1的位置（的位置（若若2i+1n ）。）。下一页上一页停止放映第2

13、4页/91二叉树的链式存储二叉树的链式存储 结点定义：结点定义：struct bintreenode elemtype data;struct bintreenode *leftchild, *rightchild; ; struct bintreenode *root; / 定义根结点指针定义根结点指针 这里leftchild和rightchild分别为某一结点指向其左孩子和右孩子的指针。对于叶结点或一个新生成的结点而言，其左孩子和右孩子指针都为空值。下一页上一页停止放映第25页/91二叉树的链式存储abcde利用这种结点形式存储的树一般称为二叉链表。从根结点出发，可以访问二叉树的任何结点。

14、为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。 下一页上一页停止放映第26页/91二叉树的遍历二叉树的遍历 遍历（traversing）是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。 遍历的方法很多，常用的有： 前序法（preorder） 中序法（inorder） 后序法（postorder）下一页上一页停止放映第27页/91前序法（前序法（preorder）方法描述：从根结点a开始访问，接着访问左子结点b，最后访问右子结点c。即：根根左子左子右子右子abc遍历序列a b c下一页上一页停止放映第28页/91中序

15、法（中序法（inorder）方法描述：从左子结点b开始访问，接着访问根结点a，最后访问右子结点c。即：根根左子左子右子右子abc遍历序列b a c下一页上一页停止放映第29页/91后序法（后序法（postorder） 方法描述：从左子结点b开始访问，接着访问右子结点c，最后访问根结点a。 即：根根左子左子右子右子abc遍历序列b c a下一页上一页停止放映第30页/91二叉树的遍历举例二叉树的遍历举例 oooooooooabcdefghi前序遍历序列：前序遍历序列：中序遍历序列：中序遍历序列：后序遍历序列：后序遍历序列： dgebhifcadgebhifcadbgeachfidbgeachfi

16、abdegcfhiabdegcfhi下一页上一页停止放映第31页/91二叉树遍历算法（递归、前序法二叉树遍历算法（递归、前序法）void preorder(bintreenode *t) if (t) visit( t ); /访问根结点访问根结点 preorder( t-leftchild ); /遍历左子树遍历左子树 preorder( t-rightchild ); /遍历右子树遍历右子树 abcdef前序遍历二叉树的序列为： a b c d e f下一页上一页停止放映第32页/91二叉树遍历算法（递归、前序法验证）二叉树遍历算法（递归、前序法验证）打印a 取a.左子(b) 打印b取b.

17、左子(c)打印c取c.左子(空)取c.右子(空) 取b.右子(d)打印d取d.左子(e)打印e取e.左子(空)取e.右子(空)取d.右子(f)打印f取f.左子(空)取f.右子(空) 取a.右子(空)结束a ab bc cd de ef fatopatopbatopbatopbcatopdatopdeatopdatopfatop下一页上一页停止放映第33页/91（2 2）中序遍历）中序遍历 对一颗非空二叉树进行中序遍历时，首先按对一颗非空二叉树进行中序遍历时，首先按中序遍历方式访问左子树，然后访问根结点，中序遍历方式访问左子树，然后访问根结点，最后按中序遍历方式访问右子树。中序遍历最后按中序遍历

18、方式访问右子树。中序遍历算法如下：算法如下：void inorder(bintreenode *t) if(t) inorder( t-leftchild ); / 遍历左子树遍历左子树 visit( t ); / 访问根节点访问根节点 inorder( t-rightchild ); / 遍历右子树遍历右子树下一页上一页停止放映第34页/91（3 3）后序遍历）后序遍历对一颗非空二叉树进行中序遍历时，首先按对一颗非空二叉树进行中序遍历时，首先按后序遍后序遍历历方式访问左子树，然后方式访问左子树，然后按后序遍历按后序遍历方式访问右方式访问右子树，最后访问根结点。子树，最后访问根结点。后序遍历后

19、序遍历算法如下：算法如下： void postorder(bintreenode *t) if(t) postorder( t-leftchild ); / 遍历左子树遍历左子树postorder( t-rightchild ); / 遍历右子树遍历右子树visit( t ); / 访问根节点访问根节点下一页上一页停止放映第35页/91表达式树及应用表达式树及应用在计算机中对表达式进行分析和计算是一项重要的任务。举例，用二叉树表示表达式： a + b * （ c - d）前序遍历序列：中序遍历序列：后序遍历序列：分析： 每个叶结点为运算对象； 每个非叶结点为运算符； 每个子树对应一个子表达式。

20、表达式处理一般采用后序法，也称“逆波兰”法。表达式处理规则： 见运算数入栈； 见运算符，取两个栈顶元素运算后再压栈； 直到处理结束。efbcda a下一页上一页停止放映第36页/91表达式树应用举例表达式树应用举例（1） a b c d 入栈dcba（1）（2） c - d b a（3） b*（c-d） aa+b*（c-d）（4）（5）a+b*（c-d）fe（6）e/fa+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）遇/，

21、f e 出栈， 运算后再压栈；（7）遇-，a+b*（c-d）和e/f出栈，运算后再压栈。下一页上一页停止放映第37页/91图的基本概念图的基本概念 图的来源图的来源：通信网、交通网等，它表现了数据对：通信网、交通网等，它表现了数据对象间多对多的联系。在该结构中，数据元素一般象间多对多的联系。在该结构中，数据元素一般称为顶点称为顶点。图的定义：图的定义：图是对结点的前趋和后继个数不加限制的图是对结点的前趋和后继个数不加限制的数数据结构，它据结构，它v ve e下一页上一页停止放映第38页/91图例图例设图g1 = （v，e）v=v1，v2，v3，v4e=（v1，v2），（v1，v3）， （v2，

22、v1），（v2，v3）， （v2，v4），（v3，v1）， （v3，v2），（v4，v2） oooov1v2v3v4g1下一页上一页停止放映第39页/91有向图、无向图有向图、无向图有向图（digraph） 图g中顶点的偶对若是有向的，称为有向图。如图g2所示。为示区别， 其偶对用表示。 例 g2=（v，e） v= 1，2，3，4 e=1，2,1，3， 3，4,4，1无向图（undigraph） 图g中顶点的偶对若是无向的，称为无向图，其偶对用（vx，vy）表示，如图g1所示。 1324 g2oooov1v2v3v4g1下一页上一页停止放映第40页/91边、弧边、弧边（edge） 顶点间的关系

23、可描述为顶点的偶对，也称为顶点的边。记为：（vx，vy）。边是无序的，可看成是（vx，vy），也可看成是（vy，vx）。弧（arc） 若顶点间的边是有方向性（有序）的，则称该偶对为弧。记为：vx，vy。弧是有序的，vx，vy表示从vx到vy。弧头（head）弧的终点（terminal node）称为弧头（方向前方）。弧尾（tail）弧的起始点（initial node）称为弧尾（方向后方）。 弧 vx，vy表示为，弧尾弧尾 弧头弧头vx vyvx vy下一页上一页停止放映第41页/91顶点、邻接点顶点、邻接点顶点（顶点（vertexvertex）图中的数据元素（结点）称为顶点。如图g1、g2中

24、的1、2，1，2。邻接点（邻接点（adjacentadjacent）无向图中,若边（x,y） e，则x和y互为邻接点;有向图中，若弧x,y e，则y是x的邻接点，反之，不是。vxvyx、y互为邻接点互为邻接点vxvyy是是x的邻接点的邻接点下一页上一页停止放映第42页/91顶点的度（顶点的度（degree）无向图中，顶点的度是以该顶点为一个端点的边的条数。例如，g1中v2的度为3，v4的度为1。有向图中，以某顶点为弧头的弧的数目称为该顶点的入度（indegree）。例如g2中顶点1的入度为1。以某顶点为弧尾的弧的数目称为该顶点的出度（outdegree）。例如g2中顶点1的出度为2。该顶点的度

25、=入度+出度。例如，g2中顶点1的度=2+1=3。oooov1v2v3v4g11324 g2下一页上一页停止放映第43页/91路径、长度路径、长度路径（path） 在图中，从顶点vx到顶点vy的顶点序列（vx，v1，v2，,vn,vy)称为从vx到vy的路径。路径可能是不唯一的。例如，g1中，v1到v3的路径为：（v1v2v3）或（v1v3）；而g2中，1到4的路径为。长度（length） 路径的长度是该路径上边或弧的数目。例如，g1中v1到v3的长度为1或2；而g2中1到4的长度为2。1324 g2oooov1v2v3v4g1下一页上一页停止放映第44页/91连通图、强连通图、连通分量连通图

26、、强连通图、连通分量 连通图（连通图（connected graphconnected graph） 在无向图中，若每一对顶点间都有路径，称此图是连通图。如图g3所示。 连通分量（连通分量（connected componentconnected component） 无向图中的极大连通子图称为连通 分量。强连通图（强连通图（strongly connected graphstrongly connected graph） 在有向图中，若每对顶点vx到vy间都存在vx到vy，及从vy到vx的路径，则称此图是强连通图。如图g4所示。12345g321345g4下一页上一页停止放映第45页/91子

27、图、生成树子图、生成树子图 有两个图g和g1，若v1v，e1 e，即v1中的顶点都属于v中的顶点，e1中的关系都属于e中的关系，则称g1是g的子图。g =（v，e），g1=（v1，e1） （图的部分顶点和部分边组成的图） 生成子图、生成树 设g是一个连通图，g中任一包含g的所有顶点的子图称为生成子图。如果该子图是树，则称为g的生成树。g的生成树不是唯一的。一棵有n个顶点的生成树，有且仅有n-1条边（弧）。（子图包含所有顶点，但不一定包含所有边）下一页上一页停止放映第46页/91网、权网、权权（权（weightweight） 若图的边或弧带有与之相关的数，称此数为该边或弧的权。权通常用来表示从一

28、个顶点到另一个顶点的距离或费用。网（网（networknetwork） 带权的图称为网。如g5为带权的网。v1v2v3v4g52357下一页上一页停止放映第47页/91图的存储方式图的存储方式 1 1邻接矩阵邻接矩阵利用数组实现的。它利用一维数组存储顶点信息，利用二维数组存储顶点间边或弧的信息。此二维数组又称邻接矩阵邻接矩阵。 邻接矩阵存储方式可用于无向图或有向图。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。下一页上一页停止放映第48页/91 图的邻接矩阵存储可用下面结构体表示：图的邻接矩阵存储可用下面结构体表示：#define max_num 100 /最大顶点个数typede

29、f struct vertextype vexsmax_num; /顶点信息数组arctype matrixmax_nummax_num; /邻接矩阵int vexnum,arcnum; /图实际顶点数和弧(边)数int kind; /图种类标志,1有向图,2有向网 / 3无向图,4无向网 mgraph;其中:arctype是顶点关系的数据类型。 vertextype是顶点的数据类型。 max_num表示最多可存的顶点数。下一页上一页停止放映第49页/91假设无向图假设无向图g=(v,e)g=(v,e)是一个有是一个有n n个顶点的图，则图个顶点的图，则图的邻接矩阵的邻接矩阵a a是是n n阶

30、方阵，其内容如下：阶方阵，其内容如下：其中其中w(i,j)w(i,j)是与边或弧相关的权。是与边或弧相关的权。 其它或当 e)v,(v ev,vji,( if1, ji下一页上一页停止放映第50页/910132528130123410234 (a) (a)无向图无向图 (b)(b)有向图有向图 (c)(c)网络网络 0010100011100110110111110a013240010010010000000010101000a38125a01324012340123401230132(a)(a)无向图邻接矩阵无向图邻接矩阵 (b)(b)有向图邻接矩阵有向图邻接矩阵 (c)(c)网络邻接矩阵网

31、络邻接矩阵 邻接矩阵举例邻接矩阵举例 下一页上一页停止放映第51页/912 2邻接表邻接表邻接表存储形式是一种链表与数组结合的存储形式。在邻接表中有两种结点，一种是头结点，另一种是表结点。（1）头结点存储一个顶点的详细信息，为了便于管理，所有头结点都存放在一个数组中。（2）对于某个顶点而言，需要将所有与它邻接的顶点存储为表结点形式，并将它们链接成单链表，这个单链表就称为该顶点的邻接表。（3）还要在每个顶点的头结点中存储指向其邻接表首元结点的指针。 下一页上一页停止放映第52页/91邻接表的结点结构邻接表的结点结构(c)(c)网络的表结点：网络的表结点：infonextadjvexnextadj

32、vexfirstvexdata(a)(a)头结点头结点(b)(b)无权图的表结点：无权图的表结点：顶点顶点vi的邻接点的邻接点与边或弧有关的权值与边或弧有关的权值存放存放vi信息信息指向指向vi单链表的第一个结点单链表的第一个结点指向指向vi的下一个邻接点的指针的下一个邻接点的指针顶点顶点vi的邻接点的邻接点指向指向vi的下一个的下一个邻接点的指针邻接点的指针下一页上一页停止放映第53页/91邻接表的举例邻接表的举例无向图中无向图中v vi i的度是第的度是第i i个单链表的长度。个单链表的长度。下一页上一页停止放映第54页/91逆邻接表逆邻接表为求顶点为求顶点v vi i的入度，对每个顶点的

33、入度，对每个顶点v vi i，建立一个链，建立一个链接接 以以v vi i为弧头的邻接点链表，称该表为逆邻接表。为弧头的邻接点链表，称该表为逆邻接表。 显然逆邻接表的单链表中结点的个数就是顶点显然逆邻接表的单链表中结点的个数就是顶点v vi i的的 入度。入度。邻接表中第邻接表中第i i个单链表的长度是顶点个单链表的长度是顶点v vi i的出度。的出度。逆邻接表中第逆邻接表中第i i个单链表的长度是顶点个单链表的长度是顶点v vi i的入度的入度下一页上一页停止放映第55页/91图的邻接表描述图的邻接表描述 #define max_num 100 /顶点最大允许数量 struct adjnod

34、e /表结点类型定义 int adjvex; /该邻接点在数组中的位置 infotype info; /该弧相关信息 struct adjnode *next; /指向下一邻接点的指针; typedef struct vnode /头结点类型定义 vertextype data; /顶点信息 adjnode *first; /指向邻接表第一个结点 adjlistmax_num;下一页上一页停止放映第56页/91typedef struct adjlist headarray; /头结点数组int vexnum, arcnum; /图的当前顶点数和弧数int kind; /图的种类标志 algr

35、aph; 其中： adjnode为表结点； infotype为与边相关信息的数据类型（包括权等）； vnode为头结点； vertextype是顶点的数据类型； max_num表示最多可以存放的顶点个数。下一页上一页停止放映第57页/91图的遍历图的遍历图的遍历（traversing graph） 从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访问一次，该过程为图的遍历。图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点就不相同，路径也就不同。因为图中元素是“多对多”的关系，为避免发生重复，设立一个辅助数组visited，每访问一个顶点，便将其状态visitedi置为“真”。下一

36、页上一页停止放映第58页/91图的遍历方法图的遍历方法常用的图的遍历方法有两种：深度优先遍历法广度优先遍历法下一页上一页停止放映第59页/91深度优先遍历法深度优先遍历法算法思想：step1 从图中某个顶点v0出发，并访问此顶点；step2 从v0出发，访问与v0邻接的顶点v1后，再从v1出发，访问与v1邻接且未被访问过的顶点v2。重复上述过程，直到不存在未访问过的邻接点为止。step3 如果是连通图，从任一顶点v0出发，就可以遍历所有相邻接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作为出发点，重复step1、step2，直到全部被访问过的邻接点都被访问为止。下一页上一页停止放映第6

37、0页/91深度优先遍历法举例深度优先遍历法举例遍历过程遍历过程 访问顶点访问顶点 所过边所过边起始顶点起始顶点v1 vv1 v1 1 v1v1的第的第1 1个邻接点个邻接点v3 vv3 v3 3 （v v1 1，v v3 3）v3v3的第的第1 1个邻接点个邻接点v1v1已访问，已访问， 取下一个邻接点取下一个邻接点v5 vv5 v5 5 （v v3 3，v v5 5）v5v5的第的第1 1个邻接点个邻接点v3v3已访问，已访问， 取下一个邻接点取下一个邻接点v2 vv2 v2 2 （v v5 5，v v2 2）v2v2的两个邻接点均被访问，的两个邻接点均被访问， 回退到回退到v5v5，v5v

38、5的邻接点均被访问，的邻接点均被访问， 回退到回退到v3v3，v3v3的邻接点均被访问的邻接点均被访问 ， 回退到回退到v1v1，v1v1的另一个邻接点的另一个邻接点v4v4 未被访问未被访问 v v4 4 （v v1 1，v v4 4）v4v4的第一个邻接点的第一个邻接点v1v1已被访问，已被访问， 另一个邻接点另一个邻接点v6v6未被访问未被访问 v v6 6 （v v4 4，v v6 6）v6v6的邻接点被访问，回退到的邻接点被访问，回退到v4v4v4v4的邻接点均被访问的邻接点均被访问回退到回退到v1v1，返回到出发点，遍历结束。，返回到出发点，遍历结束。v1v3v5v4v6g6v2示

39、例示例下一页上一页停止放映第61页/91遍历产生的结果遍历产生的结果深度优先遍历g6所走过的序列： v1 v3 v5 v2 v4 v6v1v3v5v2v4v6所走过的边： （v1，v3）,（v3，v5）,（v5，v2）,（v1，v4）,（v4，v6）遍历生成树下一页上一页停止放映第62页/91下一页上一页停止放映第63页/91bool visitedmax; /顶点访问标志数组 void dfstraverse(algragh g) for(int i=0;ig.vexnum;i+) visitedi =false; for(int i=0;ig.vexnum;i+) if( ! visite

40、di ) dfs(g,i) ;void dfs(algraph g, int v) /从v顶点出发递归深度优先遍历图g adjnode *p; visitedv = true; coutvnext ) if(!visitedp-adjvex) dfs(g,p-adjvex); 下一页上一页停止放映第64页/91深度优先遍历算法程序深度优先遍历算法程序( (非递归非递归) )void traver_dfs(algragh g,int v) int stackn,visitedn, top=-1 ; adjnode *p; for (int i=0;in;i+) visitedi= false;

41、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; 下一页上一页停止放映第65页/91广度优先遍历算法广度优先遍历算法广度优先遍历法首先访问第1个顶点所有邻接点，再访问下一个顶点所有未被访问的邻接点。算法思想：step1 从图中某个顶点v0出发，并访问此顶点；step2 从v0出发，访问v0的各个未曾访问的邻接点w1，w2，,wk;然

42、后,依此从w1,w2,wk出发访问各自未被访问的邻接点。step3 重复step2，直到全部顶点都被访问为止。下一页上一页停止放映第66页/91广度优先遍历法举例广度优先遍历法举例遍历过程 访问顶点 所过边起始顶点v1 v1 访问v1的未被访问过的 所有邻接点 v3,v2,v4 （v1,v3） (v1,v2) (v1,v4)访问v3的未被访问过 的所有的邻接点 v5 （v3,v5）访问v2的未被访问过 的所有的邻接点 无访问v4的未被访问过 的所有的邻接点 v6 (v4,v6)所有顶点已被访问,结束。v1v3v5v4v6g6v2示例示例下一页上一页停止放映第67页/91遍历产生的结果遍历产生的

43、结果广度优先遍历g6所走过的序列： v1 v3 v2 v4 v5 v6v1v3v5v2v4v6所走过的边： （v1，v3），（v1，v2），（v1，v4）， （v3，v5），（v4，v6）遍历生成树下一页上一页停止放映第68页/91程序举例程序举例图的深度优先遍历和广度优先遍历。v1v3v5v4v6g6v2深度优先遍历序列：深度优先遍历序列：v1 v3 v5 v2 v4 v6广度优先遍历序列：广度优先遍历序列：v1 v3 v2 v4 v5 v61324 g2深度优先遍历序列：深度优先遍历序列： 1 3 4 2广度优先遍历序列：广度优先遍历序列： 1 3 2 4示例示例下一页上一页停止放映第69

44、页/91树和图的应用树和图的应用 哈夫曼树和哈夫曼编码 最小生成树下一页上一页停止放映第70页/91哈夫曼树和哈夫曼编码哈夫曼树和哈夫曼编码 设计二进制编码方案时要考虑不同字符的使用频率，使用频率高的字符编码应当尽量短一些。但是仅仅考虑使用频率也是不够的。例如：某个文件由a、b、c、d 4个字符组成，其中a用得最多，c次之。方案1: a1 c 0 b 10 d 11 那么象1100这样的二进制数据具有二义性，既代表aacc，又可代表abc，还可代表dcc。为了不使二进制编码具有二义性，每个字符编码都不能与其他字符编码的前面若干位重合。下一页上一页停止放映第71页/91bd ca 0011ab0

45、1d c0011 (a)有二义性的编码系统对应的二叉树 (b)无二义性的编码系统对应的二叉树任何一个无二义性的二进制字符编码系统必然与这样一颗二叉树对应：该二叉树的叶子结点对应着所有需要转换的字符，并且按照左分支代表0、右分支代表1的规则，从根到该叶子的分支对应的0、1序列就构成叶子对应字符的二进制编码。 可以利用二叉树分析字符编码问题。假设二叉树可以利用二叉树分析字符编码问题。假设二叉树中的左分支代表中的左分支代表0 0，右分支代表，右分支代表1 1，则不论字符是，则不论字符是采用何种采用何种0 0、1 1组合形式构成的编码，它必然对应组合形式构成的编码，它必然对应某个二叉树中一个结点某个二

46、叉树中一个结点。下一页上一页停止放映第72页/911 1）假设每个字符使用频率是相等的，那么不同字符）假设每个字符使用频率是相等的，那么不同字符的编码长度之和就可衡量编码系统的优劣。的编码长度之和就可衡量编码系统的优劣。2 2）如果每个字符使用频率不相等，那么将不同字符）如果每个字符使用频率不相等，那么将不同字符的编码长度乘上其使用权值再加起来，也可衡量编的编码长度乘上其使用权值再加起来，也可衡量编码系统的优劣。即用根到每个叶子的路径长度乘以码系统的优劣。即用根到每个叶子的路径长度乘以叶子对应字符的使用权值再加起来作为衡量标准，叶子对应字符的使用权值再加起来作为衡量标准，显然这种加权和除以字符

47、总数就是每个字符的加权显然这种加权和除以字符总数就是每个字符的加权平均编码长度。平均编码长度。 下一页上一页停止放映第73页/91 二叉树带权路径长度二叉树带权路径长度：设二叉树有：设二叉树有n n个带有权个带有权值的叶子结点，每个叶子到根的路径长度乘以值的叶子结点，每个叶子到根的路径长度乘以其权值之和称为二叉树带权路径长度。一般记其权值之和称为二叉树带权路径长度。一般记作：作：其中，其中，wi为第为第i个叶子的权重，个叶子的权重，li为第为第i个叶子到个叶子到根的路径长度。根的路径长度。 哈夫曼树：哈夫曼树：以一些带有固定权值的结点作为叶以一些带有固定权值的结点作为叶子所构造的，具有子所构造

48、的，具有最小最小带权路径长度的二叉树带权路径长度的二叉树称为哈夫曼树称为哈夫曼树。 huffman树也称为最优树，是一类带权路径最短的二叉树。niiilwwpl1下一页上一页停止放映第74页/91huffmanhuffman树举例树举例以下有三棵树：（a）（b）（c）abcdabcdacbd777555222444wpla =7x2+5x2+2x2+4x2 = 36wplb =7x3+5x3+2x1+4x2 = 46 wplc = 7x1+5x2+2x3+4x3 = 35 事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。下一页上一页停止放映第75页/91应用举例

49、应用举例由统计规律可知，考试成绩的分布符合正态分布：-1 1 0 分数 059 60 69 70 79 80 89 90 100比例数 0.05 0.15 0.40 0.3 0.10 根据正态分布规律，在根据正态分布规律，在60609090之间的分数占之间的分数占85%85%，而不及格和优秀是少数。而不及格和优秀是少数。下一页上一页停止放映第76页/91将百分制转换成五分制将百分制转换成五分制 判定树比较：a60?a70?a80?a90?不及格 及格 中等 良好 优秀yyyynnnna80?a70?a90?a60?不及格 优秀 良好 中等 中等 及格不及格yyynnnnyy(a)(b)若输入若

50、输入1 1万个数据，按万个数据，按a a的判定过程进行操作，约的判定过程进行操作，约需比较需比较3.23.2万次，而按万次，而按b b比较比较, ,则仅需则仅需2.22.2万次。万次。下一页上一页停止放映第77页/91构造构造huffmanhuffman树树构造huffman树算法步骤：step1 将n个带权值wi（in）的结点构成n棵二叉树的集合t=t1，t2，tn，每棵二叉树只有一个根结点。step2 在t中选取两个权值最小的结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和；step3 在t中删除这两棵树，将新构成的树加入到t中；step4 重复2）、3）步的操作，直

51、到t中只含一棵树为止，该树就是huffman树。下一页上一页停止放映第78页/91假定有一段报文由假定有一段报文由a a、b b、c c、d d四个字符构成，它们四个字符构成，它们的使用频率比为的使用频率比为6 64 42 21 1，则用，则用a a、b b、c c、d d作为作为叶子结点构造哈夫曼树的过程如图所示。叶子结点构造哈夫曼树的过程如图所示。 若二叉树中的左分支代表0，右分支代表1,则a、b、c、d的哈夫曼编码分别为0、10、110、111。 下一页上一页停止放映第79页/91构造构造huffmanhuffman树举例树举例以权值分别为7，5，2，4的结点a、b、c、d构造huffm

52、an树。t= a b c d cdt3246bt3t26511bt26511cd241118at27t1618a7t1bt3t251118a7t1b511cd264（d）t= t1 （c）t= a t2 （b）t= a b t3 （a）t= a b c d 代入代入t2代入代入t3代入代入t1示例示例下一页上一页停止放映第80页/91huffmanhuffman编码编码编码：用二进制数的不同组合来表示字符的方法。前缀编码：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。 a0b01cd011编码：编码：a a（0 0） b b（0101） c c（011011） d d（11

53、1111）方法约定：1）左分支为02）右分支为13）由叶到根路径上字符组成的二进制串就是该叶结点的编码。 huffman编码：一种非等长度的编码。以给定权值的结点构造huffman树，按二进制前缀编码的方式构成的编码为huffman编码。下一页上一页停止放映第81页/91huffmanhuffman编码举例编码举例在某系统的通信联络中可能出现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树为：000000011111115378142911234258100huf

54、fman编码为：编码为：a 5 0110b 29 01c 7 0111d 8 1111e 14 011f 23 00g 3 1110h 11 010下一页上一页停止放映第82页/91 【例2-5】假定编码系统中有五个字符假定编码系统中有五个字符x x、s s、d d、e e、a a，它们的使用频率比为，它们的使用频率比为2 29 95 57 78 8，以这些，以这些频率值作叶子的权构造哈夫曼树，并输出哈夫曼频率值作叶子的权构造哈夫曼树，并输出哈夫曼编码。编码。 257oooo89ooooo00111001下一页上一页停止放映第83页/91最小生成树最小生成树 该问题是构造连通图的最小代价生成树

55、问题。一棵生成树的代价就是树上各边（弧）的代价之和。考虑一个通信网的建设问题。考虑一个通信网的建设问题。若要在n个城市间建立通信联络网，则只需n-1条线路。但在n个城市间，最多可能架设n*（n-1）/2条线路，选择哪n-1条线路，使费用最少。普里姆（prim）算法克鲁斯卡尔（kruskal）算法下一页上一页停止放映第84页/91实例实例下一页上一页停止放映第85页/91（1 1）普里姆算法）普里姆算法 假定假定g= v, e g= v, e 为连通网络，其中为连通网络，其中v v为顶点集为顶点集合，合，e e为带权边集合。设置生成树顶点集合为带权边集合。设置生成树顶点集合u u，最初它只包含某

56、一个顶点。设置生成树边集合最初它只包含某一个顶点。设置生成树边集合t t，最初为空集。而后考察这样的边，它的一个顶最初为空集。而后考察这样的边，它的一个顶点点uuuu，另一个顶点，另一个顶点vv-uvv-u，每次从所有这样，每次从所有这样的边中选择权值最小的边的边中选择权值最小的边(u, v)(u, v)加入集合加入集合t t，并，并把顶点把顶点v v加入到集合加入到集合u u中。如此不断重复，直到中。如此不断重复，直到所有顶点都加入到集合所有顶点都加入到集合u u中为止。中为止。下一页上一页停止放映第86页/91下一页上一页停止放映第87页/91普里姆（普里姆（primprim）算法举例）算

57、法举例12345687214357681110912u=1，v-u=2，3，4，5，6，7，812212421473（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例子下一页上一页停止放映第88页/91普里姆（普里姆（primprim）算法举例）算法举例( (续续) ) 47535（4）76（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

58、,7,5,6,3,8), v-u= 43（7）83654722136589155（6）476363558下一页上一页停止放映第89页/91下一页上一页停止放映第90页/91（2 2）克鲁斯卡尔算法）克鲁斯卡尔算法 假定假定g= v, e 为连通网络，其中为连通网络，其中v为为顶点集合，顶点集合，e为带权边集合。先构造一个为带权边集合。先构造一个包含所有顶点，没有边的非连通图包含所有顶点，没有边的非连通图t= v, ，图中每个顶点自成一个连通分量。，图中每个顶点自成一个连通分量。当在当在e中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的两个顶点落在若该边的两个顶点落在t的不同的

59、连通分的不同的连通分量上，则将此边加入到量上，则将此边加入到t中；否则将此边中；否则将此边舍去，重新选择一条权值最小的边。如舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连此重复下去，直到所有顶点在同一个连通分量上为止。通分量上为止。 下一页上一页停止放映第91页/91克鲁斯卡尔（克鲁斯卡尔（kruskalkruskal）算法举例）算法举例 1234561524663556251346123(4)131 1462(3)123456 (1)13(2)1 1下一页上一页停止放映第92页/91克鲁斯卡尔（克鲁斯卡尔（kruskalkruskal）算法举例）算法举例( (续）续）

60、123456 (5)1234123456152466355613256412435（6）例子下一页上一页停止放映第93页/91结束语结束语欢迎参加到中心网站软件开发技术基础课程的学习讨论中来。中心网址： http:/课件下载地址: 60/moodle15我的e-mail地址: lzq答疑安排： 每星期五下午：3:006:00 地点： 计教中心505房间 下一页上一页停止放映d7d3ung5ibp+5!*uwnrs*in&mgep8ebz-m6v-jg$n*lto3yapqnwp*stjeaei+csg!%ea8!v*jw82lbg)4jrsz-e*ddwigvgrf(pn!4fatilbmzij5frd#z)qvu92tdg4%f!eojnziq8$k1yosw%ish-am+)8rpt)o6bnfd%c4jeyfqndy&rs&heyjk3jtbhjpk*gtgro