《教学课件第2章非线性数据结构树和图》由会员分享，可在线阅读，更多相关《教学课件第2章非线性数据结构树和图（93页珍藏版）》请在金锄头文库上搜索。
1、下一页上一页停止放映第第2 2章章 非线性数据结构非线性数据结构树和图树和图西安交通大学计教中心西安交通大学计教中心1下一页上一页停止放映树形结构树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在，并应用于：人类社会的族谱、家谱、行政区域划分管理；各种社会组织机构；在计算机领域中，用树表示源程序的语法结构；在OS中，文件系统、目录等组织结构也是用树来表示的。2下一页上一页停止放映树的逻辑结构树是一种数据结构，可用二元组表示为： Tree=（D，R）其中：D 是具有相同特性的数据元素的集合；R 是数据元素间逻辑关系的集合，且满足：在D中存在唯一的称为根的数据元素，没有前趋；D中其
2、余数据元素都有且只有一个前趋；D中所有元素，或有若干个互不相同的后继（子树），或无后继（叶结点）； 则称Tree为树。3下一页上一页停止放映树的递归定义: 树是由树是由n n个具有相同特性的数据元素组成的集合。个具有相同特性的数据元素组成的集合。若若n=0n=0，则称其为空树。一棵非空树，则称其为空树。一棵非空树T T必须满足：必须满足：1 1）其中有一个特定的元素称为）其中有一个特定的元素称为T T的根的根rootroot。2 2）除根以外的集合可被划分为）除根以外的集合可被划分为m m个不相交的子集个不相交的子集T T1 1，T T2 2，T Tm m，其中每个子集都是树。它们称，其中每个
3、子集都是树。它们称为根为根rootroot的子树。的子树。 GACFDEB树的一般形式树的一般形式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.3C3书目录 目录树 树结构5下一页上一页停止放映与树相关的术语 结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。 结点的度：结点拥有的非空子树的个数。 树的度：树中所有结点的度的最大值。 叶子结点：度为0的结点。 分支结点：至少有一个非空子树的结点。 孩子结点和父结点：某结点所有子
4、树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。6下一页上一页停止放映 兄弟结点：具有相同父结点的结点互为兄弟结点。 结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。 树的深度：树中结点所在的最大层次。 有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。 森林：由零棵或有限棵互不相交的树组成的集合。 7下一页上一页停止放映二叉树的定义二叉树是另一种树形结构： Binary_Tree =( D,R) 其中: D 是具有相同性质的数据元素的集合; R 是在D上某个两元关系的集合,且满足:D中存在唯
5、一称为根的数据元素,没有前趋;D中其余元素都有且仅有一个前趋;每个结点至多只有两个子树;D中元素,或有两个互不相交后继,或无后继;左、右子树分别又是一棵二叉树。8下一页上一页停止放映二叉树的五种基本形态二叉树的五种基本形态 （a）（b）（c）（d）（e）O空结点空结点 O单个结点单个结点OO右子树为空右子树为空的二叉树的二叉树OO左子树为空左子树为空的二叉树的二叉树左、右子左、右子树非空的树非空的二叉树二叉树OOO9下一页上一页停止放映二叉树与树的区别二叉树与树的区别表达形式（对3个结点） 普通树 二叉树 （a） （b） （c） （d） （e） OOOOOO有两种不同形式有两种不同形式（a）（
6、b b）OOOOOOOOOOOOOOO有五种不同形式有五种不同形式10下一页上一页停止放映二叉树与树的区别（二）二叉树与树的区别（二）观念二叉树的子树有顺序关系，分左子树和右子树，而树则无此区分；二叉树的分支度一定为0、1或2，而树的度可大于2。11下一页上一页停止放映特殊二叉树特殊二叉树满二叉树完全二叉树平衡二叉树二叉排序树12下一页上一页停止放映满二叉树满二叉树q当当二二叉叉树树每每个个分分支支结结点点的的度度都都是是2 2，且且所所有有叶叶子子结点都在同一层上，则称其为满二叉树。结点都在同一层上，则称其为满二叉树。q若若k k为为二二叉叉树树T T的的深深度度，且且T T中中共共有有2
7、2k-1-1个个结结点点（k k 1 1），），则称则称T T为满二叉树。为满二叉树。（a） 满二叉树 （b）非满二叉树 OOOO O OOOOOOOO13下一页上一页停止放映完全二叉树完全二叉树q从满二叉树叶子所在的层次中，自右向从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被左连续删除若干叶子所得到的二叉树被称为完全二叉树。称为完全二叉树。（a）完全二叉树 （b） 非完全二叉树OOOOOOOOOOO叶结点只可能出现在层次最大的两层上。14下一页上一页停止放映平衡二叉树平衡二叉树二叉树上任一结点的左子树深度减去右子树深度的差值，称为该结点的平衡因子。任意结点左、右子树的深
8、度之差的绝对值1 ，这样的树称为平衡二叉树。OOOOOOO OOOOOOOOO（a）平衡二叉树 （b）非平衡二叉树15下一页上一页停止放映二叉排序树定义二叉排序树定义二叉排序树或者是空二叉树；或者是：左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均大于等于根结点的值；左、右子树本身又是一棵二叉排序树。 10571114181515141851012137（a）二叉排序树 （b）非二叉排序树16下一页上一页停止放映二叉树的性质一二叉树的性质一二叉树的第i层上至多有2i-1个结点（ i 1）。利用归纳法证明：i=1时，只有一个结点，对的；假设对所有的j，1 j i，命题成立， 即在第j
9、层上，至多有2j-1 个结点。由归纳假设，第i-1层上至多有2i-2 个结点。由于二叉树的每个结点的度至多为2，故第i层上的最大结点数为第i-1层上的最大结点数的2倍，即 22i-2 = 2i-1。17下一页上一页停止放映二叉树的性质二二叉树的性质二深度为深度为h的二叉树上至多含的二叉树上至多含2h-1个结点个结点(h1)。i=1h （第（第i i层上的最大结点数）层上的最大结点数） hi=1= = 2 2i-1i-1 = 2 = 2h h-1-1证明：证明：由性质一可见，深度为h的二叉树的最大结点数为：18下一页上一页停止放映包含包含n(n0)个结点的二叉树总的分支数为个结点的二叉树总的分支
10、数为n-1。二叉树的性质三二叉树的性质三证明：证明：二二叉叉树树中中除除了了根根结结点点之之外外每每个个元元素素有有且且只只有有一一个个父父结结点点。在在所所有有子子结结点点与与父父结结点点间间有有且且只只有有一一个个分分支支，即即除除根根外外每每个个结结点点对对应应一一个个分分支支，因此二叉树总的分支数为因此二叉树总的分支数为n-1。OOOO O OOOOOOOO19下一页上一页停止放映任意二叉树，若含有任意二叉树，若含有n0个叶结点、个叶结点、n2个度为个度为2的结点，则必存在关系式的结点，则必存在关系式n0=n2+1。二叉树的性质四二叉树的性质四证明：设二叉树含有证明：设二叉树含有n1个
11、度为个度为1的结点，则二叉的结点，则二叉树结点总数显然为：树结点总数显然为：n0+n1+n2（2-2）再看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为： 1 + n1 + 2n2（2-3）由（2-2）和（2-3）两式可知：n0=n2+120下一页上一页停止放映具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2(n)+1。二叉树的性质五二叉树的性质五证明：证明：假设二叉树的深度为假设二叉树的深度为h，则必有则必有2h-1-1n2h-1，于是
12、有于是有2h-1n+12h，也就是，也就是2h-1n2h，从而得到从而得到h-1log2(n)n，则则该该结结点点无无左左孩孩子子。否否则则，编编号号为为2i的结点为其左孩子结点；的结点为其左孩子结点；若若2i+1n，则则该该结结点点无无右右孩孩子子。否否则则，编编号为号为2i+1的结点为其右孩子结点。的结点为其右孩子结点。证明：通过对证明：通过对i进行归纳即可得证。进行归纳即可得证。二叉树的性质六二叉树的性质六22下一页上一页停止放映验证性质六验证性质六 143256 123456123456第第i i个结点就存放在第个结点就存放在第i i个位置上；个位置上；第第i i个结点（个结点（i1)
13、i1)的父结点就存放在第的父结点就存放在第 i/2i/2个位置个位置; ;第第i i个结点的左子结点就存放在第个结点的左子结点就存放在第2*i2*i的位置的位置; ;右子存放在第右子存放在第2*i+12*i+1的位置（的位置（若若2i+1n ）。）。23下一页上一页停止放映二叉树的链式存储二叉树的链式存储结点定义：结点定义：structBinTreeNodeElemTypedata;structBinTreeNode*leftChild,*rightChild;structBinTreeNode*root;/定义根结点指针定义根结点指针这里leftChild和rightChild分别为某一结点
14、指向其左孩子和右孩子的指针。对于叶结点或一个新生成的结点而言，其左孩子和右孩子指针都为空值。24下一页上一页停止放映二叉树的链式存储ABCDE利用这种结点形式存储的树一般称为二叉链表。从根结点出发，可以访问二叉树的任何结点。为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。 25下一页上一页停止放映二叉树的遍历二叉树的遍历遍历（Traversing）是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。遍历的方法很多，常用的有：前序法（PreOrder）中序法（InOrder）后序法（PostOrder）26下一页上一页停止
15、放映前序法（前序法（PreOrder）方法描述：从根结点a开始访问，接着访问左子结点b，最后访问右子结点c。即：根根左子左子右子右子abc遍历序列a b c27下一页上一页停止放映中序法（中序法（InOrder）方法描述：从左子结点b开始访问，接着访问根结点a，最后访问右子结点c。即：根根左子左子右子右子abc遍历序列b a c28下一页上一页停止放映后序法（后序法（PostOrder）方法描述：从左子结点b开始访问，接着访问右子结点c，最后访问根结点a。即：根根左子左子右子右子abc遍历序列b c a29下一页上一页停止放映二叉树的遍历举例二叉树的遍历举例 oooooooooABCDEFGH
16、I前序遍历序列：前序遍历序列：中序遍历序列：中序遍历序列：后序遍历序列：后序遍历序列： DGEBHIFCADGEBHIFCADBGEACHFIDBGEACHFIABDEGCFHIABDEGCFHI30下一页上一页停止放映二叉树遍历算法（递归、前序法二叉树遍历算法（递归、前序法）voidPreOrder(BinTreeNode*t) if(t)Visit(t);/访问根结点访问根结点PreOrder(t-leftChild);/遍历左子树遍历左子树PreOrder(t-rightChild);/遍历右子树遍历右子树ABCDEF前序遍历二叉树的序列为： A B C D E F31下一页上一页停止放
17、映二叉树遍历算法（递归、前序法验证）二叉树遍历算法（递归、前序法验证）打印A取A.左子(B)打印B取B.左子(C)打印C取C.左子(空)取C.右子(空) 取B.右子(D)打印D取D.左子(E)打印E取E.左子(空)取E.右子(空)取D.右子(F)打印F取F.左子(空)取F.右子(空)取A.右子(空)结束A AB BC CD DE EF FATOPATOPBATOPBATOPBCATOPDATOPDEATOPDATOPFATOP32下一页上一页停止放映（2 2）中序遍历）中序遍历对对一一颗颗非非空空二二叉叉树树进进行行中中序序遍遍历历时时，首首先先按按中中序序遍遍历历方方式式访访问问左左子子树树
18、，然然后后访访问问根根结结点点，最最后后按按中中序序遍遍历历方方式式访访问问右右子子树树。中中序序遍遍历历算法如下：算法如下：voidInOrder(BinTreeNode*t)if(t) InOrder(t-leftChild);/遍历左子树遍历左子树Visit(t);/访问根节点访问根节点InOrder(t-rightChild);/遍历右子树遍历右子树33下一页上一页停止放映（3 3）后序遍历）后序遍历对对一一颗颗非非空空二二叉叉树树进进行行中中序序遍遍历历时时，首首先先按按后后序序遍遍历历方方式式访访问问左左子子树树，然然后后按按后后序序遍遍历历方方式式访访问问右右子树，最后访问根结点
19、。子树，最后访问根结点。后序遍历后序遍历算法如下：算法如下：voidPostOrder(BinTreeNode*t)if(t)PostOrder(t-leftChild);/遍历左子树遍历左子树PostOrder(t-rightChild);/遍历右子树遍历右子树Visit(t);/访问根节点访问根节点34下一页上一页停止放映表达式树及应用表达式树及应用在计算机中对表达式进行分析和计算是一项重要的任务。举例，用二叉树表示表达式： a + b * （ c - d）前序遍历序列：中序遍历序列：后序遍历序列：分析：每个叶结点为运算对象；每个非叶结点为运算符；每个子树对应一个子表达式。表达式处理一般采
20、用后序法，也称“逆波兰”法。表达式处理规则：见运算数入栈；见运算符，取两个栈顶元素运算后再压栈；直到处理结束。efbcda a35下一页上一页停止放映表达式树应用举例表达式树应用举例（1） a b c d 入栈dcba（1）（2）c-dba（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）遇/，f e 出栈， 运算后再压栈；（7）遇-，a+
21、b*（c-d）和e/f出栈，运算后再压栈。36下一页上一页停止放映图的基本概念图的基本概念图图的的来来源源：通通信信网网、交交通通网网等等，它它表表现现了了数数据据对对象象间间多多对对多多的的联联系系。在在该该结结构构中中，数数据据元元素素一一般般称为顶点称为顶点。图的定义：图的定义：图图是是对对结结点点的的前前趋趋和和后后继继个个数数不不加加限限制制的的一一一一种种种种数数据据结结构构，它它是是是是由由由由顶顶顶顶点点点点集集集集合合合合及及及及顶顶顶顶点点点点间间间间的的的的关关关关系系系系集集集集合合合合组组组组成。一般记作成。一般记作成。一般记作成。一般记作: : : : Graph
22、Graph Graph Graph( V, E )( V, E )( V, E )( V, E ) 其其其其中中中中: : : :V V是是是是顶顶顶顶点点点点的的的的有有有有限限限限非非非非空空空空集集集集合合合合；E E是是是是顶顶顶顶点点点点之之之之间间间间关关关关系的有限集合。系的有限集合。系的有限集合。系的有限集合。37下一页上一页停止放映图例图例设图G1 = （V，E）V=v1，v2，v3，v4E=（v1，v2），（v1，v3）， （v2，v1），（v2，v3）， （v2，v4），（v3，v1）， （v3，v2），（v4，v2） oooov1v2v3v4G138下一页上一页停止放映
23、有向图、无向图有向图、无向图有向图（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所示。 1324G2oooov1v2v3v4G139下一页上一页停止放映边、弧边、弧边（Edge） 顶点间的关系可描述为顶点的偶对，也称为顶点的边。记为：（Vx，Vy）。边是无序的，可看成是（Vx，Vy），也可看成是（Vy，Vx）。弧（Arc） 若顶点间的边是有方向性（有序）的
24、，则称该偶对为弧。记为：Vx，Vy。弧是有序的，Vx，Vy表示从Vx到Vy。弧头（Head）弧的终点（TerminaL Node）称为弧头（方向前方）。弧尾（Tail）弧的起始点（Initial Node）称为弧尾（方向后方）。 弧 Vx，Vy表示为，弧尾弧尾弧头弧头Vx VyVx Vy40下一页上一页停止放映顶点、邻接点顶点、邻接点顶顶点点（VertexVertex）图中的数据元素（结点）称为顶点。如图G1、G2中的1、2，1，2。邻邻接接点点（AdjacentAdjacent）无向图中,若边（x,y） E，则x和y互为邻接点;有向图中，若弧x,y E，则y是x的邻接点，反之，不是。VxVy
25、x、y互为邻接点互为邻接点VxVyy是是x的邻接点的邻接点41下一页上一页停止放映顶点的度（顶点的度（Degree）无向图中，顶点的度是以该顶点为一个端点的边的条数。例如，G1中V2的度为3，V4的度为1。有向图中，以某顶点为弧头的弧的数目称为该顶点的入度（Indegree）。例如G2中顶点1的入度为1。以某顶点为弧尾的弧的数目称为该顶点的出度（Outdegree）。例如G2中顶点1的出度为2。该顶点的度=入度+出度。例如，G2中顶点1的度=2+1=3。oooov1v2v3v4G11324G242下一页上一页停止放映路径、长度路径、长度路径（Path） 在图中，从顶点Vx到顶点Vy的顶点序列（
26、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。1324G2oooov1v2v3v4G143下一页上一页停止放映连通图、强连通图、连通分量连通图、强连通图、连通分量 连通图（连通图（Connected GraphConnected Graph） 在无向图中，若每一对顶点间都有路径，称此图是连通图。如图G3所示。 连通分量（连通分量（Connected Com
27、ponentConnected Component） 无向图中的极大连通子图称为连通 分量。强连通图（强连通图（Strongly Connected GraphStrongly Connected Graph） 在有向图中，若每对顶点Vx到Vy间都存在Vx到Vy，及从Vy到Vx的路径，则称此图是强连通图。如图G4所示。12345G321345G444下一页上一页停止放映子图、生成树子图、生成树子图 有两个图G和G1，若V1V，E1 E，即V1中的顶点都属于V中的顶点，E1中的关系都属于E中的关系，则称G1是G的子图。G =（V，E），G1=（V1，E1） （图的部分顶点和部分边组成的图） 生成
28、子图、生成树 设G是一个连通图，G中任一包含G的所有顶点的子图称为生成子图。如果该子图是树，则称为G的生成树。G的生成树不是唯一的。一棵有n个顶点的生成树，有且仅有n-1条边（弧）。（子图包含所有顶点，但不一定包含所有边）45下一页上一页停止放映网、权网、权权（权（WeightWeight） 若图的边或弧带有与之相关的数，称此数为该边或弧的权。权通常用来表示从一个顶点到另一个顶点的距离或费用。网（网（NetworkNetwork） 带权的图称为网。如G5为带权的网。V1V2V3V4G5235746下一页上一页停止放映图的存储方式图的存储方式1 1邻接矩阵邻接矩阵利用数组实现的。它利用一维数组存
29、储顶点信息，利用二维数组存储顶点间边或弧的信息。此二维数组又称邻接矩阵邻接矩阵。 邻接矩阵存储方式可用于无向图或有向图。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。47下一页上一页停止放映 图的邻接矩阵存储可用下面结构体表示：图的邻接矩阵存储可用下面结构体表示：#define MAX_NUM 100 /最大顶点个数typedef struct VertexType vexsMAX_NUM; /顶点信息数组ArcType MatrixMAX_NUMMAX_NUM; /邻接矩阵int vexnum,arcnum; /图实际顶点数和弧(边)数int kind; /图种类标志,1有向图,
30、2有向网 / 3无向图,4无向网 MGraph;其中:ArcType是顶点关系的数据类型。 VertexType是顶点的数据类型。 MAX_NUM表示最多可存的顶点数。48下一页上一页停止放映假设无向图假设无向图G=(V,E)G=(V,E)是一个有是一个有n n个顶点的图，则图个顶点的图，则图的邻接矩阵的邻接矩阵A A是是n n阶方阵，其内容如下：阶方阵，其内容如下：其中其中W(i,j)W(i,j)是与边或弧相关的权。是与边或弧相关的权。 对于含权的网络而言，其邻接矩阵可定义如下：对于含权的网络而言，其邻接矩阵可定义如下：49下一页上一页停止放映0132528130123410234 (a)
31、(a)无向图无向图 (b) (b)有向图有向图 (c) (c)网络网络0132401324012340123401230132(a)(a)无向图邻接矩阵无向图邻接矩阵 (b) (b)有向图邻接矩阵有向图邻接矩阵 (c) (c)网络邻接矩阵网络邻接矩阵邻接矩阵举例邻接矩阵举例50下一页上一页停止放映2 2邻接表邻接表邻接表存储形式是一种链表与数组结合的存储形式。在邻接表中有两种结点，一种是头结点，另一种是表结点。（1）头结点存储一个顶点的详细信息，为了便于管理，所有头结点都存放在一个数组中。（2）对于某个顶点而言，需要将所有与它邻接的顶点存储为表结点形式，并将它们链接成单链表，这个单链表就称为该
32、顶点的邻接表。（3）还要在每个顶点的头结点中存储指向其邻接表首元结点的指针。51下一页上一页停止放映邻接表的结点结构邻接表的结点结构(c)(c)网络的表结点：网络的表结点：infonextadjvexnextadjvexfirstVexdata(a)(a)头结点头结点(b)(b)无权图的表结点：无权图的表结点：顶点顶点Vi的邻接点的邻接点与边或弧有关的权值与边或弧有关的权值存放存放Vi信息信息指向指向Vi单链表的第一个结点单链表的第一个结点指向指向Vi的下一个邻接点的指针的下一个邻接点的指针顶点顶点Vi的邻接点的邻接点指向指向Vi的下一个的下一个邻接点的指针邻接点的指针52下一页上一页停止放映
33、邻接表的举例邻接表的举例无向图中无向图中V Vi i的度是第的度是第i i个单链表的长度。个单链表的长度。53下一页上一页停止放映逆邻接表逆邻接表为求顶点为求顶点V Vi i的入度，对每个顶点的入度，对每个顶点V Vi i，建立一个链接建立一个链接 以以V Vi i为弧头的邻接点链表，称该表为逆邻接表。为弧头的邻接点链表，称该表为逆邻接表。 显然逆邻接表的单链表中结点的个数就是顶点显然逆邻接表的单链表中结点的个数就是顶点V Vi i的的 入度。入度。邻接表中第邻接表中第i i个单链表的长度是顶点个单链表的长度是顶点V Vi i的出度。的出度。逆邻接表中第逆邻接表中第i i个单链表的长度是顶点个
34、单链表的长度是顶点V Vi i的入度的入度54下一页上一页停止放映图的邻接表描述图的邻接表描述#defineMAX_NUM100/顶点最大允许数量structAdjNode/表结点类型定义intadjvex;/该邻接点在数组中的位置InfoTypeinfo;/该弧相关信息structAdjNode*next;/指向下一邻接点的指针;typedefstructVNode/头结点类型定义VertexTypedata; /顶点信息AdjNode*first;/指向邻接表第一个结点AdjListMAX_NUM;55下一页上一页停止放映typedefstructAdjListheadArray;/头结点
35、数组intvexnum,arcnum;/图的当前顶点数和弧数intkind;/图的种类标志ALGraph;其中： AdjNode为表结点； InfoType为与边相关信息的数据类型（包括权等）； VNode为头结点； VertexType是顶点的数据类型； MAX_NUM表示最多可以存放的顶点个数。56下一页上一页停止放映图的遍历图的遍历图的遍历（Traversing Graph） 从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访问一次，该过程为图的遍历。图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点就不相同，路径也就不同。因为图中元素是“多对多”的关系，为避免发生重复，设立
36、一个辅助数组visited， 每 访 问 一 个 顶 点 ， 便 将 其 状 态visitedi置为“真”。57下一页上一页停止放映图的遍历方法图的遍历方法常用的图的遍历方法有两种：深度优先遍历法广度优先遍历法58下一页上一页停止放映深度优先遍历法深度优先遍历法算法思想：step1 从图中某个顶点V0出发，并访问此顶点；step2 从V0出发，访问与V0邻接的顶点V1后，再从V1出发，访问与V1邻接且未被访问过的顶点V2。重复上述过程，直到不存在未访问过的邻接点为止。step3 如果是连通图，从任一顶点V0出发，就可以遍历所有相邻接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作为出发点
37、，重复step1、step2，直到全部被访问过的邻接点都被访问为止。59下一页上一页停止放映深度优先遍历法举例深度优先遍历法举例遍历过程遍历过程 访问顶点访问顶点 所过边所过边起始顶点起始顶点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）
38、V2V2的两个邻接点均被访问，的两个邻接点均被访问， 回退到回退到V5V5，V5V5的邻接点均被访问，的邻接点均被访问， 回退到回退到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
39、，返回到出发点，遍历结束。返回到出发点，遍历结束。V1V3V5V4V6G6V2示例示例60下一页上一页停止放映遍历产生的结果遍历产生的结果深度优先遍历G6所走过的序列： V1 V3 V5 V2 V4 V6V1V3V5V2V4V6所走过的边： （ V1， V3） ,（ V3， V5） ,（ V5， V2）,（V1，V4）,（V4，V6）遍历生成树61下一页上一页停止放映62下一页上一页停止放映bool visitedMAX; /顶点访问标志数组 void DFSTraverse(ALGragh G) for(int i=0;iG.vexnum;i+) visitedi =FALSE; for(i
40、nt 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
41、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 从图中某个顶点V0出发，并访问此顶点；step2 从V0出发，访问V
42、0的各个未曾访问的邻接点W1，W2，,Wk;然后,依此从W1,W2,Wk出发访问各自未被访问的邻接点。step3 重复step2，直到全部顶点都被访问为止。65下一页上一页停止放映广度优先遍历法举例广度优先遍历法举例遍历过程 访问顶点 所过边起始顶点V1 V1 访问V1的未被访问过的 所有邻接点 V3,V2,V4 （V1,V3） (V1,V2) (V1,V4)访问V3的未被访问过 的所有的邻接点 V5 （V3,V5）访问V2的未被访问过 的所有的邻接点 无访问V4的未被访问过 的所有的邻接点 V6 (V4,V6)所有顶点已被访问,结束。V1V3V5V4V6G6V2示例示例66下一页上一页停止放
43、映遍历产生的结果遍历产生的结果广度优先遍历G6所走过的序列： V1 V3 V2 V4 V5 V6V1V3V5V2V4V6所走过的边： （V1，V3），（V1，V2），（V1，V4）， （V3，V5），（V4，V6）遍历生成树67下一页上一页停止放映程序举例程序举例图的深度优先遍历和广度优先遍历。V1V3V5V4V6G6V2深度优先遍历序列：深度优先遍历序列：V1V3V5V2V4V6广度优先遍历序列：广度优先遍历序列：V1V3V2V4V5V61324G2深度优先遍历序列：深度优先遍历序列：1342广度优先遍历序列：广度优先遍历序列：1324示例示例68下一页上一页停止放映树和图的应用树和图的应用
44、哈夫曼树和哈夫曼编码最小生成树69下一页上一页停止放映哈夫曼树和哈夫曼编码哈夫曼树和哈夫曼编码 设计二进制编码方案时要考虑不同字符的使用频率，使用频率高的字符编码应当尽量短一些。但是仅仅考虑使用频率也是不够的。例如：某个文件由A、B、C、D 4个字符组成，其中A用得最多，C次之。方案1: A1 C 0 B 10 D 11 那么象1100这样的二进制数据具有二义性，既代表AACC，又可代表ABC，还可代表DCC。为了不使二进制编码具有二义性，每个字符编码都不能与其他字符编码的前面若干位重合。70下一页上一页停止放映BD CA 0011AB01D C0011 (a)有二义性的编码系统对应的二叉树
45、(b)无二义性的编码系统对应的二叉树任何一个无二义性的二进制字符编码系统必然与这样一颗二叉树对应：该二叉树的叶子结点对应着所有需要转换的字符，并且按照左分支代表0、右分支代表1的规则，从根到该叶子的分支对应的0、1序列就构成叶子对应字符的二进制编码。 可以利用二叉树分析字符编码问题。假设二叉树可以利用二叉树分析字符编码问题。假设二叉树中的左分支代表中的左分支代表0 0，右分支代表，右分支代表1 1，则不论字符是，则不论字符是采用何种采用何种0 0、1 1组合形式构成的编码，它必然对应组合形式构成的编码，它必然对应某个二叉树中一个结点某个二叉树中一个结点。71下一页上一页停止放映1 1）假设每个
46、字符使用频率是相等的，那么不同字符）假设每个字符使用频率是相等的，那么不同字符的编码长度之和就可衡量编码系统的优劣。的编码长度之和就可衡量编码系统的优劣。2 2）如果每个字符使用频率不相等，那么将不同字符）如果每个字符使用频率不相等，那么将不同字符的编码长度乘上其使用权值再加起来，也可衡量编的编码长度乘上其使用权值再加起来，也可衡量编码系统的优劣。即用根到每个叶子的路径长度乘以码系统的优劣。即用根到每个叶子的路径长度乘以叶子对应字符的使用权值再加起来作为衡量标准，叶子对应字符的使用权值再加起来作为衡量标准，显然这种加权和除以字符总数就是每个字符的加权显然这种加权和除以字符总数就是每个字符的加权
47、平均编码长度。平均编码长度。 72下一页上一页停止放映二二叉叉树树带带权权路路径径长长度度：设设二二叉叉树树有有n n个个带带有有权权值值的的叶叶子子结结点点，每每个个叶叶子子到到根根的的路路径径长长度度乘乘以以其其权权值值之之和和称称为为二二叉叉树树带带权权路路径径长长度度。一一般般记记作：作：其其中中，wi为为第第i个个叶叶子子的的权权重重，li为为第第i个个叶叶子子到到根的路径长度。根的路径长度。哈哈夫夫曼曼树树：以以一一些些带带有有固固定定权权值值的的结结点点作作为为叶叶子子所所构构造造的的，具具有有最最小小带带权权路路径径长长度度的的二二叉叉树树称称为为哈哈夫夫曼曼树树。 Huffm
48、an树也称为最优树，是一类带权路径最短的二叉树。73下一页上一页停止放映HuffmanHuffman树举例树举例以下有三棵树：（a）（b）（c）abcdabcdacbd777555222444WPLa =7x2+5x2+2x2+4x2 = 36WPLb =7x3+5x3+2x1+4x2 = 46 WPLc = 7x1+5x2+2x3+4x3 = 35 事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。74下一页上一页停止放映应用举例应用举例由统计规律可知，考试成绩的分布符合正态分布：-1 1 0 分数 059 60 69 70 79 80 89 90 100比例数
49、 0.05 0.15 0.40 0.3 0.10 根据正态分布规律，在根据正态分布规律，在60609090之间的分数占之间的分数占85%85%，而不及格和优秀是少数。，而不及格和优秀是少数。75下一页上一页停止放映将百分制转换成五分制将百分制转换成五分制判定树比较：a60?a70?a80?a90?不及格 及格 中等 良好 优秀YYYYNNNNa80?a70?a90?a60?不及格 优秀 良好 中等 中等 及格不及格YYYNNNNYY(A)(B)若输入若输入1 1万个数据，按万个数据，按A A的判定过程进行操作，约的判定过程进行操作，约需比较需比较3.23.2万次，而按万次，而按B B比较比较,
50、 ,则仅需则仅需2.22.2万次。万次。76下一页上一页停止放映构造构造HuffmanHuffman树树构造Huffman树算法步骤：Step1 将n个带权值wi（in）的结点构成n棵二叉树的集合T=T1，T2，Tn，每棵二叉树只有一个根结点。Step2 在T中选取两个权值最小的结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和；Step3 在T中删除这两棵树，将新构成的树加入到T中；Step4 重复2）、3）步的操作，直到T中只含一棵树为止，该树就是Huffman树。77下一页上一页停止放映假定有一段报文由假定有一段报文由a a、b b、c c、d d四个字符构成，它们的
51、四个字符构成，它们的使用频率比为使用频率比为64216421，则用，则用a a、b b、c c、d d作为叶子作为叶子结点构造哈夫曼树的过程如图所示。结点构造哈夫曼树的过程如图所示。 若二叉树中的左分支代表0，右分支代表1,则a、b、c、d的哈夫曼编码分别为0、10、110、111。 78下一页上一页停止放映构造构造HuffmanHuffman树举例树举例以权值分别为7，5，2，4的结点a、b、c、d构造Huffman树。T= a b c d cdT3246bT3T26511bT26511cd241118aT27T1618a7T1bT3T251118a7T1b511cd264（d）T= T1
52、（c）T= a T2 （b）T= a b T3 （a）T= a b c d 代入代入T2代代入入T3代入代入T1示例示例79下一页上一页停止放映HuffmanHuffman编码编码编码：用二进制数的不同组合来表示字符的方法。前缀编码：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。 a0b01cd011编码：编码：a a（0 0） b b（0101） c c（011011） d d（111111）方法约定：1）左分支为02）右分支为13）由叶到根路径上字符组成的二进制串就是该叶结点的编码。 Huffman编码：一种非等长度的编码。以给定权值的结点构造Huffman树，按二进制
53、前缀编码的方式构成的编码为Huffman编码。80下一页上一页停止放映HuffmanHuffman编码举例编码举例在某系统的通信联络中可能出现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树为：000000011111115378142911234258100Huffman编码为：编码为：A50110B2901C70111D81111E14011F2300G31110H1101081下一页上一页停止放映 【例2-5】假定编码系统中有五个字符假定编码系统中有五个字符
54、X X、S S、D D、E E、A A，它们的使用频率比为，它们的使用频率比为2957829578，以这些，以这些频率值作叶子的权构造哈夫曼树，并输出哈夫曼频率值作叶子的权构造哈夫曼树，并输出哈夫曼编码。编码。 257oooo89ooooo0011100182下一页上一页停止放映最小生成树最小生成树 该问题是构造连通图的最小代价生成树问题。一棵生成树的代价就是树上各边（弧）的代价之和。考考虑虑一一个个通通信信网网的的建建设设问问题题。若要在n个城市间建立通信联络网，则只需n-1条线路。但在n个城市间，最多可能架设n*（n-1）/2条线路，选择哪n-1条线路，使费用最少。普里姆（Prim）算法克
55、鲁斯卡尔（Kruskal）算法83下一页上一页停止放映实例实例84下一页上一页停止放映（1 1）普里姆算法）普里姆算法 假假定定G= G= V, V, E E 为为连连通通网网络络，其其中中V V为为顶顶点点集集合合，E E为为带带权权边边集集合合。设设置置生生成成树树顶顶点点集集合合U U，最最初初它它只只包包含含某某一一个个顶顶点点。设设置置生生成成树树边边集集合合T T，最最初初为为空空集集。而而后后考考察察这这样样的的边边，它它的的一一个个顶顶点点uUuU，另另一一个个顶顶点点vV-UvV-U，每每次次从从所所有有这这样样的的边边中中选选择择权权值值最最小小的的边边(u, (u, v)
56、v)加加入入集集合合T T，并并把把顶顶点点v v加加入入到到集集合合U U中中。如如此此不不断断重重复复，直直到所有顶点都加入到集合到所有顶点都加入到集合U U中为止。中为止。85下一页上一页停止放映86下一页上一页停止放映普里姆（普里姆（PrimPrim）算法举例）算法举例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例子87下一页上一页停止放映普里姆（普里姆（Pri
57、mPrim）算法举例）算法举例( (续续) ) 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,7,5,6,3,8),V-U=43（7）83654722136589155（6）47636355888下一页上一页停止放映89下一页上一页停止放映（2 2）克鲁斯卡尔算法）克鲁斯卡尔算法假假定定G=V,E为为连连通通网网络络，其其中中V为为顶顶点点集集合合，E为为带带权权边边集集合合。先先构构造造一一个个包包含含所所有有顶顶点点，没没有有边边的的非非连连通
58、通图图T=V,，图图中中每每个个顶顶点点自自成成一一个个连连通通分分量量。当当在在E中中选选到到一一条条具具有有最最小小权权值值的的边边时时,若若该该边边的的两两个个顶顶点点落落在在T的的不不同同的的连连通通分分量量上上，则则将将此此边边加加入入到到T中中；否否则则将将此此边边舍舍去去，重重新新选选择择一一条条权权值值最最小小的的边边。如如此此重重复复下下去去，直直到到所所有有顶顶点点在在同同一一个个连连通分量上为止。通分量上为止。90下一页上一页停止放映克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）算法举例）算法举例 1234561524663556251346123(4)131 1462(3)123456 (1)13(2)1 191下一页上一页停止放映克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）算法举例）算法举例( (续）续） 123456 (5)1234123456152466355613256412435（6）例子92下一页上一页停止放映结束语结束语欢迎参加到中心网站软件开发技术基础课程的学习讨论中来。中心网址： http:/课件下载地址:我的E-mail地址: 答疑安排： 每星期五下午：3:006:00 地点： 计教中心505房间 93
