发布时间 : 星期五 文章数据结构-朱二周更新完毕开始阅读
重点：
(1)二叉树的性质及证明方法；
(2)二叉树的遍历及其基础上实现的其它操作； (3)线索二叉树的实质；
(4)树、森林与二叉树的转换；
(5)哈夫曼树(或最优二叉树)的特点及其构造。 难点：
(1)二叉树性质的证明过程； (2)二叉树的遍历及其算法； (3)树、森林与二叉树的转换； (4)线索二叉树；
(5)哈夫曼树及哈夫曼编码。 （四）作业及课外学习要求：
(1) 已知二叉树的前序序列和中序序列能否唯一确定一棵二叉树？已知二叉树
的后序序列和中序序列能否唯一确定一棵二叉树？已知二叉树的前序序列和后序序列能否唯一确定一棵二叉树？
(2) 一棵前序序列为1，2，3，4，的二叉树，其中序序列可能是4，1，2，3吗？
设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。 (3) 编写算法判断一棵二叉树是否是完全二叉树。
(4) 编写计算二叉树的最大宽度的算法（二叉树的最大宽度是指二叉树所有层中
结点个数的最大值）。
(5) 试将下列三棵树组成的森林转换成对应的二叉树。
(6) 编写复制一棵二叉树的非递归算法。
(7) 对以孩子-兄弟表示法，编写树的层次遍历算法。 (8) 对以孩子-兄弟表示法，编写计算树的深度的算法。
(9) 证明：在结点数多于1的哈夫曼树中不存在度为1的结点。
本知识点的讲授和学习，可以支撑“毕业要求1工程知识”中的“指标点1.1，能够运用数学与自然科学基础知识，理解软件工程中涉及的相关科学原理”；可以支撑“毕业要求2问题分析”中的“指标点2_3， 能够对于模型的正确性进行严谨的推理，并能够给出解”，使学生掌握将工程基础知识和本专业的基本理论知识向结合，锻炼学生的工程实践能力，并为后续课程的学习奠定理论基础。 第7章 图 ( 12学时)
（一）基本内容： 1图的定义和术语
定义：图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构
加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
术语：数据对象、数据关系、基本操作、有向图、无向图、完全图、连通分
量、连通图、路径、度、生成森林等等。 2图的存储结构
2.1 邻接矩阵
(1)有向图的邻接矩阵
具有n 个顶点的有向图可以用一个n?n 的方形矩阵表示。假设该矩阵的名称为M ， 则当
具有n 个顶点的无向图也可以用一个n?n 的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj ）是该无向图中的一条边时，M[i,j]=M[j,i]=1；否则，M[i,j]=M[j,j]=0 。第i 个顶点的度为矩阵中第i行中“1”的个数或第i列中“1”的个数。图中边的数目等于矩阵中“1”的个数的一半，这是因为每条边在矩阵中描述了两次。 2.2 邻接表
（1）边结点的结构：
adjvex next
其中，adjvex是该边或弧依附的顶点在数组中的下标，next是指向下一条边或弧结点的指针。 （2）项点结构
item firstedge
其中，item是顶点内容，firstedge是指向第一条边或弧结点的指针。 在C语言中，实现邻接表表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 30 //最大顶点个数 type struct EdgeNode{ //边结点
int adjvex;
struct EdgeNode *next; }EdgeNode;
typedef struct VexNode{ //顶点结点 EntryType item;
EdgeNode *firstedge;
}VexNode,AdjList[MAX_VERTEX_NUM];
本节讨论：邻接表与邻接矩阵有什么异同之处？
联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一
行中非零元素的个数。
区别：① 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号
一致），但邻接表不唯一（链接次序与顶点编号无关）。
② 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。 用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于
稀疏图的存储（e< 图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程称为图的遍历。图的遍历是求解图的连通性问题、拓扑排序和求关键路径等问题的基础。常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。 3.1深度优先遍历(depth-first search) 深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索遍历可定义如下： (1)首先访问顶点i，并将其访问标记置为访问过，即visited[i]=1； (2)然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visited[j]=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点； (3)若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完为止。 3.2广度优先遍历(width-first search) 广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是： (1) 首先访问顶点i，并将其访问标志置为已被访问，即visited[i]=1； (2) 接着依次访问与顶点i有边相连的所有顶点W1，W2，?，Wt； (3) 然后再按顺序访问与W1，W2，?，Wt有边相连又未曾访问过的顶点； 依此类推，直到图中所有顶点都被访问完为止 。 4无向图的连通分量与生成树 若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点； 若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。 生成树是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。 深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构成连通图的极小连通子图。它是连通图的一颗生成树。 由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。 5 最小生成树 n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(Minimum cost Spanning Tree) 构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先 选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中， 求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法 普里姆算法： 算法思想：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。 克鲁斯卡尔算法： 算法思想：将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。 6 拓扑排序 6.1.定义 给出有向图G=(V,E)，对于V中的顶点的线性序列(vi1,vi2,...,vin)，如果满足如下条件：若在G中从顶点 vi 到vj有一条路经，则在序列中顶点vi必在顶点 vj之前；则称该序列为 G的一个拓扑序列（Topological order） 构造有向图的一个拓扑序列的过程称为拓扑排序（Topological sort） 6.2.说明 (1)在AOV网中,若不存在回路,则所有活动可排成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,那么该序列为拓扑序列. (2)拓扑序列不是唯一的. (3) 对AOV网不一定都有拓扑序列. 在AOV网中， 因此，对给定的AOV网，应先判断它是否存在有向环。判断AOV网是否有有向环的方法是对该AOV网进行拓扑排序，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环，否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。 6.3拓扑排序算法。