基本网络使用---浙江广播电视大学玉环学院

1、,数据结构 玉环电大计算机教研室 2002年,第4章树,学习重点,了解二叉树的结构特性线 熟悉二叉树的各种存储结构的特点 熟练掌握二叉树的三种遍历算法 线索二叉树 了解最优树的特性,掌握建立最优树及哈夫曼编码的方法,树的定义和基本术语,一、什么是树？,树(Tree)是n(n0)个结点的有限集T，且满足以下条件：(1) 有且仅有一个特定的称为根(Root)的结点;(2) 除根结点外的其余结点可分为m(m0)个互不相交的有限集T1,T2.Tm,其中,每一个集合本身 又是一棵树, 并且称为根的子树(subtree,例如,在图中,(a)是只有一个根 结点的树; (b)是有 13个结点的树,其中A是根,

2、其余结点分成三个互不相交的子树：,树的定义和基本术语,二、树的基本术语,树的结点：包含一个数据元素及若干个指向其子树的分支 结点的度：结点拥有的子树数 树的度：树内各结点的度的最大值 叶子（终端结点）：度为零的结点 非终端结点（分支结点）：度不为零的结点 孩子、双亲及兄弟结点： 结点的层次和树的深度：,二叉树,一、什么是二叉树？,二叉树(binary tree)是另一种树型结构，它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒.,二叉树的五种基本形态见P50图421,二、二叉树的重要性质,二叉树,性质1：二叉树第i(i1)层

3、上至多有2i-1个结点,性质2：深度为K(K1)的二叉树至多有2k-1个结点,性质3：在任意二叉树中，若叶子结点（即度为0）个数为N0，度为 1的结点数为N1 ，度为2的结点个数为N2 ，那么： N0 N2 1,性质4：具有n个结点的完全二叉树，其深度为log2n+1,二叉树,性质5：若对n个结点的完全二叉树进行顺序编号(1In)，那么， 对于编号为i(i 1)的结点，有： (1)当i=1时，该结点为根，它无双亲结点； (2)当i1时，该结点的双亲结点编号为i/2； (3)当2in，则有编号为2i 的左孩子，否则没有左孩子； (4)若2i+1n，则有编号为2i+1的右孩子，否则没有右孩子。,二

4、、二叉树的重要性质,二叉树,三、二叉树的存储结构,二叉树,三、二叉树的存储结构,2、 链式存储结构 由二叉树的定义得知二叉树 的结点由一个数据元素和分别 指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点 至少包含三个域:数据域和左右 指针域,如图(b)所示。有时,为了 便于找 到结点的双亲,则还可在 结点结构中增加一个指向其双 亲受的指针域，如图6.7(c)所示。,二叉树,四、遍历二叉树,遍历二叉树(traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先(根)序遍历

5、，中(根)序遍历和后(根)序遍历。,1、先根(前序)遍历 访问根节点 前序遍历左子树 前序遍历右子树,2、中根(中序)遍历 中序遍历左子树 访问根节点 中序遍历右子树,二叉树,四、遍历二叉树,2、后根(后序)遍历 后序遍历左子树 后序遍历右子树 访问根节点,二叉树,四、遍历二叉树,二叉树,五、线索二叉树（简介） （p58),六、二叉树、树和森林,1、树的存储结构（双亲数组、结点定长、孩子兄弟二叉链表p61),2、树与二叉树之间的转换,一般树转化为二叉树 将一般树转化为二叉树的思路，主要根据树的孩子一兄弟存储方式而来，具体步骤为： (1)加线：在各兄弟结点之间用虚线相连。可理解为每个结点的兄弟指

6、针指向它的一个兄弟。 (2)抹线：对每个结点仅保留它与其最左一个孩子的连线，抹去该结点与其它孩子之间的连线。可理解为每个结点仅有一个孩子指针，让它指向自己的第一个孩子。 (3)旋转：把虚线改为实线从水平方向向下旋转45，成右斜下方向。原树中实线成左斜下方向。这样就形成一棵二叉树。,(1)加线： (2)抹线： (3)旋转：,一般树转化为二叉树,七、哈夫曼树及其应用,哈夫曼树，又称最优二叉树，是一类带权路径最短的树，有着广泛的应用。一、基本概念： 1、路径长度：从树中一个节点到另一个节点之间的分支构成这两个节点的路径,路径上的分支数目称为路径长度。 2、树的路径长度：是从树根到每一节点的路径之和.

7、 这种路径长度最短的二叉树是本节中定义的完全二叉树. 3、节点的带权路径长度：从树根到该结点之间的路径长度与结点上权的乘积。 4、树的带权路径长度：树中所有叶子结点的带权路径长度之和,通常记作 WPL=WkLk(k=1.n). 5、最优二叉树或哈夫曼树： 假设有n个权值w1,w1,.,wn,试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为W1, 则其中带权路径长度WPL最少的二叉树称作最优二叉树或哈夫曼树.,例如,图例6.24中的三棵二叉树,都有备无4个叶子结点a、b、c、d,分别带权力下放7、5、2、4,它们的带权路径长度分别为:(a)WPL=72+52+24+42=36 (b)WPL=

8、73+53+21+42=46 (c)WPL=71+52+23+43=35 其中以(c)树的为最少.可以验证,它恰为哈夫曼树,既取带权路径在所有带权为7、5、2、4,的四个叶子结点二叉树居最少,七、哈夫曼树及其应用,1）构造哈夫曼树的方法 (1)根据给定的n个权值 W1，W2，W n构成n棵二叉树的集合F=T1，T2，T n ，其中每一棵二叉树T i中只有一个带权为Wi的根结点，其左右子树均空； (2)在F中选出两棵根结点权值最小的树作为一棵新的二叉树的左右子树，且置新二叉树根结点的权值为两棵子树根结点的权值之和； (3)从F中删去这两棵树，同时把新二叉树加入F中； (4)重复(2)和（3），直

9、到F中只有一棵树为止，此树便是哈夫曼树。 现根据上述的方法，对于一组具体的权值2，4，5，8构造哈夫曼树。图4-6-2为具体构造过程,二、构造哈夫曼树,数据结构 玉环电大计算机教研室 2002年,第5章图,学习重点,熟悉图的各种存储结构 熟练掌握遍历图的递归算法和非递归算法 应用图的遍历算法求解各种简单路径问题,一、图的定义和术语,图G（Graph）是一种数据结构，它的形式化定义为 Graph=（V，E） 其中：V是顶点（vertex）的非空有穷集合 E是用顶点对表示的边（Edge）的有穷集合,（一）图的定义,1、无向图：若图G中表示边的顶点是无序的，则称G为无向图，通常用(Vi,Vj)表示顶

10、点Vi和Vj间相连的边。在无向图中， (Vi,Vj)和(Vj,Vi)表示同一条边。 G2为无向图。G2=(V，E) 其中V=V1,V2,V3,V4,V5 E=(V1,V2),(V1,V4)(V2,V3),(V2,V5)(V3,V4),(V3,V5) 2、有向图：若图G中表示边的顶点对是有序的，则称G为有向图。 有向边通常称为弧(arc),用表示从顶点Vi到Vj的一条弧，称Vi为弧尾(tail)或初始点，称Vj为弧头（head）或终端点。在有向图中， 和表示两条不同弧。 G1=(V,E)其中: V=V1,V2,V3,V4 E=(,),（二）图的基本术语,1、邻接点、相关边（p73),2、完全图（

11、图示：p73） 有n(n-1) /2条边的无向图称为无向完全图； 有n(n-1)条边的有向图称为有向完全图；,用n 表示图中顶点数目,用e表示边或弧的数目.在下面的讨论中 我们不考虑顶点到其自身的弧或边,4、顶点的度 顶点的度（TD） 入度（ID） 出度（OD）,3、子图 对于图G（V，E）， G（V，E） 若有V V ，EE则G为G的子图,（二）图的基本术语,5、路径、回路 路径（顶点序列，在有向图中，路径也是有向的。 路径长度（路径上边或弧的数目） 回路或环（路径的起终点相同） 简单路径（顶点不重复出现的路径）,6、连通、强连通 连通（若从顶点Vi到Vj（ij)有路径，则称Vi和Vj是连通

12、的） 连通图（在无向图中任意两顶点Vi和Vj（ij)都是连通的，则称此无向图为连通图） 连通分量（无向图中极大连通子图称为连通分量） 强连通图（在有向图中任意两顶点Vi和Vj都是连通的，则称此有向图为强连通图） 强连通分量（有向图中极大强连通子图称为强连通分量）,7、权、网,二、图的存储结构,(一)邻接矩阵表示法 用两个数组分别存储数据元素(顶点)的信息和数据元素之间的 关系(边或弧)的信息,0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0,特点： 1、无向图的邻接表一定对称； 2、无向图的邻接表的第

13、i行(列)非零元素的个数正好是第i个顶点的度 有向图的邻接表的第i行非零元素的个数正好是第i个顶点的出度 有向图的邻接表的第I列非零元素的个数正好是第i个顶点的入度 3、从邻接矩阵很容易确定图中任意两顶点是否有边或弧相连,邻接矩阵表示的存储形式： # define VEX_NUM 10 /* 图的顶点数 */ Typedef char vextype ; /* 顶点类型 */ Typedef struct vextype vexsVEX_NUM; /* 顶点向量 */ int arcsVEX_NUMVEX_NUM;/* 邻接矩阵 */ Mgraph; 创建邻接矩阵的算法（参见P75),邻接矩阵

14、表示法,二、图的存储结构,(二)邻接表（adjacecy List） 图的邻接表是一种顺序分配和链式分配相结合的一种存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。,特点： 1、若无向图中有n个顶点，e条边，则它的邻接表需n个头结点和2e个表结点。2、在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数；而在有向图中，第i个链表中的结点个数只是顶点vi的出度。 比较邻接矩阵与邻接表(P76) 创建邻接表算法(P77),三、图的遍历,从图中某一顶点出发访遍图中其余顶点，且使每一顶点仅被访问一次,1、深度优先搜索遍

15、历 连通图深度优先遍历类似于树的先序遍历，其基本思想如下：假定以图中某个顶点vi为出发点，首先访问出发点，然后选择一个vi的未访问过的邻接点vj，以vj为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。显然，这是一个递归的搜索过程。,现以图5-3-1中G为例说明深度优先搜索过程。假定v0是出发点，首先访问v0。因v0有两个邻接点v1、v2均末被访问过，可以选择v1作为新的出发点，访问v1之后，再找v1的末访问过的邻接点。同v1邻接的有v0、v3和v4，其中v0已被访问过，而v3、v4尚未被访问过，可以选择v3作为新的出发点。重复上述搜索过程，继续依次访问v7、v4 。访问v4之后，

16、由于与v4相邻的顶点均已被访问过，搜索退回到v7。由于v7、v3和v1都是没有末被访问的邻接点，所以搜索过程连续地从v7退回到v3，再退回v1，最后退回到v0。这时再选择v0的末被访问过的邻接点v2，继续往下搜索，依次访问v2、v5和v6，止此图中全部顶点均被访问过。遍历过程见图5-3-1（b），得到的顶点的访问序列为：v0 v1 v3 v7 v4 v2 v5 v6。,因为深度优先搜索遍历是递归定义的，故容易写出其递归算法。下面的算法5.3是以邻接矩阵作为图的存储结构下的深度优先搜索遍历算法；算法5.4是以邻接表作为图的存储结构下的深度优先搜索遍历算法。 算法5.3 int visitedVA

17、X_VEX=0; void Dfs_m( Mgraph *G,int i) /* 从第i个顶点出发深度优先遍历图G，G以邻接矩阵表示*/ printf(%3c,G-vexsi); visitedi=1; for (j=0;jarcsij=1) /*Dfs_m */,算法5.4 int visitedVEX_NUM=0; void Dfs_L(ALgraph G,int i) /* 从第i个顶点出发深度优先遍历图G，G以邻接表表示 */ printf(%3c,Gi.data); visitedi=1; p=Gi.firstarc; while (p!=NULL) if(visitedp-adjv

18、ex=0) Dfs_L(G,p-adjvex); p=p-nextarc; /*dfs_L*/,2、广度优先搜索遍历 连通图广度优先遍历类似于树的按层次遍历，其基本思想如下：从图中某个顶点vi为出发点，在访问了vi 之后，依次访问vi的各个未曾访问过的邻接点；然后分别从这些邻接点出发，依次访问它们未曾访问过的邻接点，直至图中所有顶点都被访问过。,得到的顶点的访问序列为：v0 v1 v2 v3 v4 v5 v6 v7 。,int visitedVAX_VEX=0; void Bfs_m( Mgraph *G,int k) /* 从第k个顶点出发广度优先遍历图G，G以邻接矩阵表示*/ Int qu

19、20，f=0，r=0； printf(%3c,G-vexsk); visitedk=1; While (r！f) f+ ；I=quf； for (j=0;jarcsij=1) /*Bfs_m */,四、图的最小生成树,(一)生成树的概念 (二)网络的最小生成树 如果连通图是一个网络，称该网络中所有生成树中权值总和最小 的生成树为最小生成树（也称最小代价生成树）。（P81图示） MST性质（P81）,1、普里姆算法 普里姆算法的基本思想如下：假设G=(V，E)是连通网，T=(U，TE)为欲构造的最小生成树。初始时，U=u0，TE=。重复下述操作：在所有uU，vV-U的边中，选择一条权值最小的边(u，v)并入TE，同时将v并入U，直到U=V为止。这时产生的TE中具有n-1条边。上述过程中求得的T=(U，TE)便是G的一棵最小生成树。,普里姆算法演示,2、克 鲁斯卡尔算法,五、最短路径,1、从某源点到其余顶点之间的最短路径 设有向网G=（V，E），以某指定顶点为源点v0，求从v0出发到图中所有其余各项点的最短路径。以图5-5-1所示的有向网络为例，若指定v0为源点，通过分析可以得到从v0出发到其余各顶点的最短路径和路径长度为：,v0 v1 ：无路径 v