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

《【教学课件】第2章非线性数据结构树和图.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第2章非线性数据结构树和图.ppt（93页珍藏版）》请在三一办公上搜索。

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

2、的后继（子树），或无后继（叶结点）；则称Tree为树。,第4页/91,树的递归定义:,树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足：1）其中有一个特定的元素称为T的根root。2）除根以外的集合可被划分为m个不相交的子集T1，T2，Tm，其中每个子集都是树。它们称为根root的子树。,第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,与树相关的术语,结点：在树结构

3、中一般把数据元素及其若干指向子树的分支称为结点。结点的度：结点拥有的非空子树的个数。树的度：树中所有结点的度的最大值。叶子结点：度为0的结点。分支结点：至少有一个非空子树的结点。孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。,第7页/91,兄弟结点：具有相同父结点的结点互为兄弟结点。结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。树的深度：树中结点所在的最大层次。有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。森林：由零棵或有限棵互不相交的树组成的集合。,第8

4、页/91,二叉树的定义,二叉树是另一种树形结构：Binary_Tree=(D,R)其中:D 是具有相同性质的数据元素的集合;R 是在D上某个两元关系的集合,且满足:D中存在唯一称为根的数据元素,没有前趋;D中其余元素都有且仅有一个前趋;每个结点至多只有两个子树;D中元素,或有两个互不相交后继,或无后继;左、右子树分别又是一棵二叉树。,第9页/91,二叉树的五种基本形态,（a）（b）（c）,（d）（e）,O 空结点,O 单个结点,右子树为空的二叉树,左子树为空的二叉树,左、右子树非空的二叉树,第10页/91,二叉树与树的区别,表达形式（对3个结点）普通树 二叉树（a）（b）（c）（d）（e）,O

5、,O,O,O,O,O,有两种不同形式,（a）,（b）,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,有五种不同形式,第11页/91,二叉树与树的区别（二）,观念二叉树的子树有顺序关系，分左子树和右子树，而树则无此区分；二叉树的分支度一定为0、1或2，而树的度可大于2。,第12页/91,特殊二叉树,满二叉树完全二叉树平衡二叉树二叉排序树,第13页/91,满二叉树,当二叉树每个分支结点的度都是2，且所有叶子结点都在同一层上，则称其为满二叉树。若k为二叉树T的深度，且T中共有2k-1个结点（k 1），则称T为满二叉树。（a）满二叉树（b）非满二叉树,第14页/91,完全二叉树,从满二叉

6、树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树。（a）完全二叉树（b）非完全二叉树,叶结点只可能出现在层次最大的两层上。,第15页/91,平衡二叉树,二叉树上任一结点的左子树深度减去右子树深度的差值，称为该结点的平衡因子。任意结点左、右子树的深度之差的绝对值1，这样的树称为平衡二叉树。,（a）平衡二叉树（b）非平衡二叉树,第16页/91,二叉排序树定义,二叉排序树或者是空二叉树；或者是：左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均大于等于根结点的值；左、右子树本身又是一棵二叉排序树。,10,5,7,11,14,18,15,15,14,18,5,10,

7、12,13,7,（a）二叉排序树（b）非二叉排序树,第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)。,证明：由性质一可见，深度为h的二叉树的最大结点数为：,第19页/91,包含n(n0)个结点的二叉

8、树总的分支数为n-1。,二叉树的性质三,证明：二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支，因此二叉树总的分支数为n-1。,第20页/91,任意二叉树，若含有n0个叶结点、n2个度为2的结点，则必存在关系式n0=n2+1。,二叉树的性质四,证明：设二叉树含有n1个度为1的结点，则二叉树结点总数显然为：n0+n1+n2（2-2）,再看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为：,1+n

9、1+2n2（2-3）由（2-2）和（2-3）两式可知：n0=n2+1,第21页/91,具有n个结点的完全二叉树的深度为 log2(n)+1。,二叉树的性质五,证明：假设二叉树的深度为h，则必有2h-1-1n2h-1，于是有2h-1n+12h，也就是 2h-1n2h，从而得到h-1log2(n)h，于是h=log2(n)+1。,第22页/91,若对含n个结点的完全二叉树从上到下、从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点：若i=1，则该结点是二叉树的根，无父结点。否则，编号为i/2的结点为其父结点；若2in，则该结点无左孩子。否则，编号为2i的结点为其左孩子结点；若2i+1n，

10、则该结点无右孩子。否则，编号为2i+1的结点为其右孩子结点。证明：通过对i进行归纳即可得证。,二叉树的性质六,第23页/91,验证性质六,第i个结点就存放在第i个位置上；第i个结点（i1)的父结点就存放在第 i/2个位置;第i个结点的左子结点就存放在第2*i的位置;右子存放在第2*i+1的位置（若2i+1n）。,第24页/91,二叉树的链式存储,结点定义：struct BinTreeNode ElemType data;struct BinTreeNode*leftChild,*rightChild;struct BinTreeNode*root;/定义根结点指针 这里leftChild和ri

11、ghtChild分别为某一结点指向其左孩子和右孩子的指针。对于叶结点或一个新生成的结点而言，其左孩子和右孩子指针都为空值。,第25页/91,利用这种结点形式存储的树一般称为二叉链表。从根结点出发，可以访问二叉树的任何结点。为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。,第26页/91,二叉树的遍历,遍历（Traversing）是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。,遍历的方法很多，常用的有：前序法（PreOrder）中序法（InOrder）后序法（PostOrder）,第27页/91,前序法（PreOrd

12、er）,方法描述：从根结点a开始访问，接着访问左子结点b，最后访问右子结点c。即：,根,左子,右子,a b c,第28页/91,中序法（InOrder）,方法描述：从左子结点b开始访问，接着访问根结点a，最后访问右子结点c。即：,根,左子,右子,b a c,第29页/91,后序法（PostOrder）,方法描述：从左子结点b开始访问，接着访问右子结点c，最后访问根结点a。即：,根,左子,右子,b c a,第30页/91,二叉树的遍历举例,前序遍历序列：中序遍历序列：后序遍历序列：,DGEBHIFCA,DBGEACHFI,ABDEGCFHI,第31页/91,二叉树遍历算法（递归、前序法）,voi

13、d PreOrder(BinTreeNode*t)if(t)Visit(t);/访问根结点 PreOrder(t-leftChild);/遍历左子树 PreOrder(t-rightChild);/遍历右子树,前序遍历二叉树的序列为：A B C D E F,第32页/91,二叉树遍历算法（递归、前序法验证）,打印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,第33页/91,（2）中序遍历

14、对一颗非空二叉树进行中序遍历时，首先按中序遍历方式访问左子树，然后访问根结点，最后按中序遍历方式访问右子树。中序遍历算法如下：void InOrder(BinTreeNode*t)if(t),InOrder(t-leftChild);/遍历左子树 Visit(t);/访问根节点 InOrder(t-rightChild);/遍历右子树,第34页/91,（3）后序遍历对一颗非空二叉树进行中序遍历时，首先按后序遍历方式访问左子树，然后按后序遍历方式访问右子树，最后访问根结点。后序遍历算法如下：void PostOrder(BinTreeNode*t)if(t),PostOrder(t-leftCh

15、ild);/遍历左子树PostOrder(t-rightChild);/遍历右子树Visit(t);/访问根节点,第35页/91,表达式树及应用,在计算机中对表达式进行分析和计算是一项重要的任务。举例，用二叉树表示表达式：a+b*（c-d）前序遍历序列：中序遍历序列：后序遍历序列：分析：每个叶结点为运算对象；每个非叶结点为运算符；每个子树对应一个子表达式。表达式处理一般采用后序法，也称“逆波兰”法。表达式处理规则：见运算数入栈；见运算符，取两个栈顶元素运算后再压栈；直到处理结束。,第36页/91,表达式树应用举例,（1）a b c d 入栈,（2）遇-，c d 出栈，运算后再压栈；,（3）遇*

16、，（c-d）和 b 出栈，运算后再压栈；,（4）遇+，b*（c-d）和a出栈，运算后再压栈；,（5）e f 入栈,（6）遇/，f e 出栈，运算后再压栈；,（7）遇-，a+b*（c-d）和e/f出栈，运算后再压栈。,第37页/91,图的基本概念,图的来源：通信网、交通网等，它表现了数据对象间多对多的联系。在该结构中，数据元素一般称为顶点。图的定义：图是对结点的前趋和后继个数不加限制的一种数据结构，它是由顶点集合及顶点间的关系集合组成。一般记作:Graph(V,E)其中:V是顶点的有限非空集合；E是顶点之间关系的有限集合。,第38页/91,图例,设图G1=（V，E）V=v1，v2，v3，v4E=

17、（v1，v2），（v1，v3），（v2，v1），（v2，v3），（v2，v4），（v3，v1），（v3，v2），（v4，v2）,第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所示。,第40页/91,边、弧,边（Edge）顶点间的关系可描述为顶点的偶对，也称为顶点的边。记为：（Vx，Vy）。边是无序的，可看成是（Vx，Vy），也可看成

18、是（Vy，Vx）。弧（Arc）若顶点间的边是有方向性（有序）的，则称该偶对为弧。记为：Vx，Vy。弧是有序的，Vx，Vy表示从Vx到Vy。弧头（Head）弧的终点（TerminaL Node）称为弧头（方向前方）。弧尾（Tail）弧的起始点（Initial Node）称为弧尾（方向后方）。弧 Vx，Vy表示为，,第41页/91,顶点、邻接点,顶点（Vertex）图中的数据元素（结点）称为顶点。如图G1、G2中的1、2，1，2。邻接点（Adjacent）无向图中,若边（x,y）E，则x和y互为邻接点;有向图中，若弧x,y E，则y是x的邻接点，反之，不是。,Vx,Vy,x、y互为邻接点,Vx,V

19、y,y是x的邻接点,第42页/91,顶点的度（Degree）,无向图中，顶点的度是以该顶点为一个端点的边的条数。例如，G1中V2的度为3，V4的度为1。有向图中，以某顶点为弧头的弧的数目称为该顶点的入度（Indegree）。例如G2中顶点1的入度为1。以某顶点为弧尾的弧的数目称为该顶点的出度（Outdegree）。例如G2中顶点1的出度为2。该顶点的度=入度+出度。例如，G2中顶点1的度=2+1=3。,第43页/91,路径、长度,路径（Path）在图中，从顶点Vx到顶点Vy的顶点序列（Vx，V1，V2，,Vn,Vy)称为从Vx到Vy的路径。路径可能是不唯一的。例如，G1中，V1到V3的路径为：

20、（V1V2V3）或（V1V3）；而G2中，1到4的路径为。长度（Length）路径的长度是该路径上边或弧的数目。例如，G1中V1到V3的长度为1或2；而G2中1到4的长度为2。,1,3,2,4,G2,o,o,o,o,v1,v2,v3,v4,G1,第44页/91,连通图、强连通图、连通分量,连通图（Connected Graph）在无向图中，若每一对顶点间都有路径，称此图是连通图。如图G3所示。连通分量（Connected Component）无向图中的极大连通子图称为连通 分量。强连通图（Strongly Connected Graph）在有向图中，若每对顶点Vx到Vy间都存在Vx到Vy，及从

21、Vy到Vx的路径，则称此图是强连通图。如图G4所示。,第45页/91,子图、生成树,子图 有两个图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,网、权,权（Weight）若图的边或弧带有与之相关的数，称此数为该边或弧的权。

22、权通常用来表示从一个顶点到另一个顶点的距离或费用。网（Network）带权的图称为网。如G5为带权的网。,第47页/91,图的存储方式,1邻接矩阵利用数组实现的。它利用一维数组存储顶点信息，利用二维数组存储顶点间边或弧的信息。此二维数组又称邻接矩阵。邻接矩阵存储方式可用于无向图或有向图。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。,第48页/91,图的邻接矩阵存储可用下面结构体表示：#define MAX_NUM 100/最大顶点个数typedef struct VertexType vexsMAX_NUM;/顶点信息数组ArcType MatrixMAX_NUMMAX_NUM;

23、/邻接矩阵int vexnum,arcnum;/图实际顶点数和弧(边)数int kind;/图种类标志,1有向图,2有向网/3无向图,4无向网 MGraph;其中:ArcType是顶点关系的数据类型。VertexType是顶点的数据类型。MAX_NUM表示最多可存的顶点数。,第49页/91,假设无向图G=(V,E)是一个有n个顶点的图，则图的邻接矩阵A是n阶方阵，其内容如下：,其中W(i,j)是与边或弧相关的权。,对于含权的网络而言，其邻接矩阵可定义如下：,第50页/91,(a)无向图邻接矩阵(b)有向图邻接矩阵(c)网络邻接矩阵,邻接矩阵举例,第51页/91,2邻接表邻接表存储形式是一种链表

24、与数组结合的存储形式。在邻接表中有两种结点，一种是头结点，另一种是表结点。（1）头结点存储一个顶点的详细信息，为了便于管理，所有头结点都存放在一个数组中。（2）对于某个顶点而言，需要将所有与它邻接的顶点存储为表结点形式，并将它们链接成单链表，这个单链表就称为该顶点的邻接表。（3）还要在每个顶点的头结点中存储指向其邻接表首元结点的指针。,第52页/91,邻接表的结点结构,(c)网络的表结点：,(a)头结点,(b)无权图的表结点：,顶点Vi的邻接点,与边或弧有关的权值,存放Vi信息,指向Vi单链表的第一个结点,指向Vi的下一个邻接点的指针,顶点Vi的邻接点,指向Vi的下一个邻接点的指针,第53页/

25、91,邻接表的举例,无向图中Vi的度是第i个单链表的长度。,第54页/91,逆邻接表,为求顶点Vi的入度，对每个顶点Vi，建立一个链接 以Vi为弧头的邻接点链表，称该表为逆邻接表。显然逆邻接表的单链表中结点的个数就是顶点Vi的 入度。,邻接表中第i个单链表的长度是顶点Vi的出度。逆邻接表中第i个单链表的长度是顶点Vi的入度,第55页/91,图的邻接表描述,#define MAX_NUM 100/顶点最大允许数量 struct AdjNode/表结点类型定义 int adjvex;/该邻接点在数组中的位置 InfoType info;/该弧相关信息 struct AdjNode*next;/指向

26、下一邻接点的指针;typedef struct VNode/头结点类型定义 VertexType data;/顶点信息 AdjNode*first;/指向邻接表第一个结点 AdjListMAX_NUM;,第56页/91,typedef struct AdjList headArray;/头结点数组int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志 ALGraph;其中：AdjNode为表结点；InfoType为与边相关信息的数据类型（包括权等）；VNode为头结点；VertexType是顶点的数据类型；MAX_NUM表示最多可以存放的顶点个数。,第57页

27、/91,图的遍历,图的遍历（Traversing Graph）从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访问一次，该过程为图的遍历。图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点就不相同，路径也就不同。因为图中元素是“多对多”的关系，为避免发生重复，设立一个辅助数组visited，每访问一个顶点，便将其状态visitedi置为“真”。,第58页/91,图的遍历方法,常用的图的遍历方法有两种：深度优先遍历法广度优先遍历法,第59页/91,深度优先遍历法,算法思想：step1 从图中某个顶点V0出发，并访问此顶点；step2 从V0出发，访问与V0邻接的顶点V1后，再从V1出

28、发，访问与V1邻接且未被访问过的顶点V2。重复上述过程，直到不存在未访问过的邻接点为止。step3 如果是连通图，从任一顶点V0出发，就可以遍历所有相邻接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作为出发点，重复step1、step2，直到全部被访问过的邻接点都被访问为止。,第60页/91,深度优先遍历法举例,遍历过程 访问顶点 所过边,起始顶点V1 V1 V1的第1个邻接点V3 V3（V1，V3）V3的第1个邻接点V1已访问，取下一个邻接点V5 V5（V3，V5）V5的第1个邻接点V3已访问，取下一个邻接点V2 V2（V5，V2）V2的两个邻接点均被访问，回退到V5，V5的邻接点均

29、被访问，回退到V3，V3的邻接点均被访问，回退到V1，V1的另一个邻接点V4 未被访问 V4（V1，V4）V4的第一个邻接点V1已被访问，另一个邻接点V6未被访问 V6（V4，V6）V6的邻接点被访问，回退到V4V4的邻接点均被访问回退到V1，返回到出发点，遍历结束。,V1,V3,V5,V4,V6,G6,V2,示例,第61页/91,遍历产生的结果,深度优先遍历G6所走过的序列：V1 V3 V5 V2 V4 V6,所走过的边：（V1，V3）,（V3，V5）,（V5，V2）,（V1，V4）,（V4，V6）,遍历生成树,第62页/91,第63页/91,bool visitedMAX;/顶点访问标志数

30、组 void DFSTraverse(ALGragh G)for(int i=0;inext)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;iadjvex)p=p-next;else coutadjvex.dataadjvex=TRUE;top+;stacktop=p-adjvex;p=Gp-adjvex.first;if(top!=-1)v=stacktop

31、;top-;p=Gv.first;p=p-next;,第65页/91,广度优先遍历算法,广度优先遍历法首先访问第1个顶点所有邻接点，再访问下一个顶点所有未被访问的邻接点。算法思想：step1 从图中某个顶点V0出发，并访问此顶点；step2 从V0出发，访问V0的各个未曾访问的邻接点W1，W2，,Wk;然后,依此从W1,W2,Wk出发访问各自未被访问的邻接点。step3 重复step2，直到全部顶点都被访问为止。,第66页/91,广度优先遍历法举例,遍历过程 访问顶点 所过边,起始顶点V1 V1 访问V1的未被访问过的 所有邻接点 V3,V2,V4（V1,V3）(V1,V2)(V1,V4)访问

32、V3的未被访问过 的所有的邻接点 V5（V3,V5）访问V2的未被访问过 的所有的邻接点 无访问V4的未被访问过 的所有的邻接点 V6(V4,V6)所有顶点已被访问,结束。,V1,V3,V5,V4,V6,G6,V2,示例,第67页/91,遍历产生的结果,广度优先遍历G6所走过的序列：V1 V3 V2 V4 V5 V6,所走过的边：（V1，V3），（V1，V2），（V1，V4），（V3，V5），（V4，V6）,遍历生成树,第68页/91,程序举例,图的深度优先遍历和广度优先遍历。,深度优先遍历序列：V1 V3 V5 V2 V4 V6广度优先遍历序列：V1 V3 V2 V4 V5 V6,深度优先遍

33、历序列：1 3 4 2广度优先遍历序列：1 3 2 4,示例,第69页/91,树和图的应用,哈夫曼树和哈夫曼编码最小生成树,第70页/91,哈夫曼树和哈夫曼编码,设计二进制编码方案时要考虑不同字符的使用频率，使用频率高的字符编码应当尽量短一些。但是仅仅考虑使用频率也是不够的。例如：某个文件由A、B、C、D 4个字符组成，其中A用得最多，C次之。方案1:A1 C 0 B 10 D 11 那么象1100这样的二进制数据具有二义性，既代表AACC，又可代表ABC，还可代表DCC。为了不使二进制编码具有二义性，每个字符编码都不能与其他字符编码的前面若干位重合。,第71页/91,(a)有二义性的编码系统

34、对应的二叉树(b)无二义性的编码系统对应的二叉树,任何一个无二义性的二进制字符编码系统必然与这样一颗二叉树对应：该二叉树的叶子结点对应着所有需要转换的字符，并且按照左分支代表0、右分支代表1的规则，从根到该叶子的分支对应的0、1序列就构成叶子对应字符的二进制编码。,可以利用二叉树分析字符编码问题。假设二叉树中的左分支代表0，右分支代表1，则不论字符是采用何种0、1组合形式构成的编码，它必然对应某个二叉树中一个结点。,第72页/91,1）假设每个字符使用频率是相等的，那么不同字符的编码长度之和就可衡量编码系统的优劣。2）如果每个字符使用频率不相等，那么将不同字符的编码长度乘上其使用权值再加起来，

35、也可衡量编码系统的优劣。即用根到每个叶子的路径长度乘以叶子对应字符的使用权值再加起来作为衡量标准，显然这种加权和除以字符总数就是每个字符的加权平均编码长度。,第73页/91,二叉树带权路径长度：设二叉树有n个带有权值的叶子结点，每个叶子到根的路径长度乘以其权值之和称为二叉树带权路径长度。一般记作：其中，wi为第i个叶子的权重，li为第i个叶子到根的路径长度。哈夫曼树：以一些带有固定权值的结点作为叶子所构造的，具有最小带权路径长度的二叉树称为哈夫曼树。Huffman树也称为最优树，是一类带权路径最短的二叉树。,第74页/91,Huffman树举例,以下有三棵树：,（a）,（b）,（c）,a,b,

36、c,d,a,b,c,d,a,c,b,d,7,7,7,5,5,5,2,2,2,4,4,4,WPLa=7x2+5x2+2x2+4x2=36,WPLb=7x3+5x3+2x1+4x2=46,WPLc=7x1+5x2+2x3+4x3=35,事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。,第75页/91,应用举例,由统计规律可知，考试成绩的分布符合正态分布：,-1,1,0,分数 059 60 69 70 79 80 89 90 100,比例数 0.05 0.15 0.40 0.3 0.10,根据正态分布规律，在6090之间的分数占85%，而不及格和优秀是少数。,第76页

37、/91,将百分制转换成五分制,判定树比较：,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万次。,第77页/91,构造Huffman树,构造Huffman树算法步骤：Step1 将n个带权值wi（in）的结点构成n棵二叉树的集合T=T1，T2，Tn，每棵二叉树只有一个根结点。Step2 在T中选取两个权值最小的结点作

38、为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和；Step3 在T中删除这两棵树，将新构成的树加入到T中；Step4 重复2）、3）步的操作，直到T中只含一棵树为止，该树就是Huffman树。,第78页/91,假定有一段报文由a、b、c、d四个字符构成，它们的使用频率比为6421，则用a、b、c、d作为叶子结点构造哈夫曼树的过程如图所示。,若二叉树中的左分支代表0，右分支代表1,则a、b、c、d的哈夫曼编码分别为0、10、110、111。,第79页/91,构造Huffman树举例,以权值分别为7，5，2，4的结点a、b、c、d构造Huffman树。T=a b c d,4,（d）

39、T=T1,（c）T=a T2,（b）T=a b T3,（a）T=a b c d,示例,第80页/91,Huffman编码,编码：用二进制数的不同组合来表示字符的方法。前缀编码：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。,编码：a（0）b（01）c（011）d（111）,方法约定：1）左分支为02）右分支为13）由叶到根路径上字符组成的二进制串就是该叶结点的编码。,Huffman编码：一种非等长度的编码。以给定权值的结点构造Huffman树，按二进制前缀编码的方式构成的编码为Huffman编码。,第81页/91,Huffman编码举例,在某系统的通信联络中可能出现8种字符

40、，其频率分别为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树为：,第82页/91,【例2-5】假定编码系统中有五个字符X、S、D、E、A，它们的使用频率比为29578，以这些频率值作叶子的权构造哈夫曼树，并输出哈夫曼编码。,第83页/91,最小生成树,该问题是构造连通图的最小代价生成树问题。一棵生成树的代价就是树上各边（弧）的代价之和。考虑一个通信网的建设问题。若要在n个城市间建立通信联络网，则只需n-1条线路。但在n个城市间，最多可能架设n*（n-1）/2条线路，选择哪n-1条线路

41、，使费用最少。普里姆（Prim）算法克鲁斯卡尔（Kruskal）算法,第84页/91,实例,第85页/91,（1）普里姆算法 假定G=V,E 为连通网络，其中V为顶点集合，E为带权边集合。设置生成树顶点集合U，最初它只包含某一个顶点。设置生成树边集合T，最初为空集。而后考察这样的边，它的一个顶点uU，另一个顶点vV-U，每次从所有这样的边中选择权值最小的边(u,v)加入集合T，并把顶点v加入到集合U中。如此不断重复，直到所有顶点都加入到集合U中为止。,第86页/91,第87页/91,普里姆（Prim）算法举例,1,2,3,4,5,6,8,7,2,1,4,3,5,7,6,8,11,10,9,12

42、,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,例子,第88页/91,普里姆（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,5,5,第89页/91,第90

43、页/91,（2）克鲁斯卡尔算法 假定G=V,E 为连通网络，其中V为顶点集合，E为带权边集合。先构造一个包含所有顶点，没有边的非连通图T=V,，图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在T的不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。,第91页/91,克鲁斯卡尔（Kruskal）算法举例,1,2,3,4,5,6,1,5,2,4,6,6,3,5,5,6,第92页/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,例子,第93页/91,结束语,欢迎参加到中心网站软件开发技术基础课程的学习讨论中来。中心网址：http:/课件下载地址:我的E-mail地址:答疑安排：每星期五下午：3:006:00 地点：计教中心505房间,