六、树和二叉树的回顾复习课程知识讲稿.ppt

第六章回顾;树的三种存储结构 双亲表示法 孩子链表表示法 孩子兄弟表示法 森林和二叉树的转换 由森林转换为二叉树 由二叉树转换为森林 树和森林的遍历 树的先根遍历（= 二叉树的先序遍历） 树的后根遍历（= 二叉树的中序遍历） 森林的先序遍历（= 二叉树的先序遍历） 森林的中序遍历（= 二叉树的中序遍历） 赫夫曼树和赫夫曼编码;课前思考;;课前导学 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的应用 7.5 总结与提高;【学习目标】;【重点和难点】;【学习指南】; 有向图(Digraph)——;无向图(Undigraph)——;有向完备图——n个顶点的有向图最大边数是n(n-1) 无向完备图——n个顶点的无向图最大边数是n(n-1)/2;顶点的度 无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目 ;子图——如果图G(V,E)和图G’(V’,E’),满足：V’?V E’?E 则称G‘为G的子图;权(Weight)——与图的边或弧相关的数,可以表示两个顶点之间的距离或耗费 网——带权的图 上海→北京 怎么走最优?　;路径——路径是顶点的序列V={Vi，0,Vi，1,……Vi，n}，满足(Vi，j-1,Vi，j)?E 或 Vi，j-1,Vi，j?E,(1j?n) 路径长度——沿路径边的数目或沿路径各边权值之和 回路——第一个顶点和最后一个顶点相同的路径 简单路径——序列中顶点不重复出现的路径 简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路;例;连通——从顶点V到顶点W有路径，则说V和W是连通的； 连通图——无向图中任意两个顶点都是连通的 连通分量——无向图中的极大连通子图 强连通图——有向图中，对每一对Vi,Vj∈V, Vi≠Vj,从Vi到Vj 和从Vj到 Vi都存在路径 强连通分量——有向图中的极大强连通子图;2. 图的抽象数据类型ADT Graph {数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R＝{VR} VR＝{v,w| v,w∈V且P(v,w)，v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息 } 基本操作P：结构的建立和销毁: CreateGraph(G,V,VR); // 按V和VR的定义构造图G DestroyGraph(G); // 销毁图G; 对顶点的访问操作: LocateVex(G, u); // 若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。 GetVex(G, v); // 返回v的值 PutVex(G, v, value); // 对v赋值value 对邻接点的操作: FirstAdjVex(G, v); // 返回v的第一个邻接点。若该顶点在G中没有邻接点，则返回“空”  NextAdjVex(G, v, w); //返回v的（相对于w的）下一个邻接点若w是v的最后一个邻接点，则返回“空” 插入或删除顶点: InsertVex(G, v); // 在图G中增添新顶点v DeleteVex(G, v); // 删除G中顶点v及其相关的弧; 插入和删除弧: InsertArc(G, v, w); // 在G中增添弧v,w，若G是无向的，则还增添对称弧w,v DeleteArc(G, v, w); //在G中删除弧v,w，若G是无向的，则还删除对称弧w,v遍历: DFSTraverse(G, v, Visit()); // 从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次 BFSTraverse(G, v, Visit()); // 从顶点v起广度优先遍历图 G，并对每个顶点调用函数Visit一次且仅一次 ;7.2 图的存储结构　;特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 有向图中， 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和;网络的邻接矩阵可定义为：;?;图的邻接矩阵存储表示：#define INFINITY INT_MAX // 最大值∞#define MAX_VERTEX_NUM 20 // 最大顶点个数typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图,有向