◆ 二叉树的应用：哈夫曼树和哈夫曼编码。
Huffman树：最优二叉树（带权路径长度最短的树） Huffman编码：不等长编码。 树的带权路径长度：
（树中所有叶子结点的带权路径长度之和）
构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。 构造Huffman树的步骤（即Huffman算法）：
(1) 由给定的 n 个权值{ w1, w2, ?, wn }构成n棵二叉树的集合F = { T1, T2, ?, Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。
(2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。
(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。
(4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。 具体操作步骤：
学习重点：（本章内容是本课程的重点）
◆ 二叉树性质及证明方法，并能把这种方法推广到K叉树。
◆ 二叉树遍历，遍历是基础，由此导出许多实用的算法，如求二叉树的高度、各结点的层次数、度为0、1、2的结点数。
◆ 由二叉树遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树。由前序和后序序列不能唯一确定一棵二叉树。
◆ 完全二叉树的性质。
◆ 树、森林和二叉树间的相互转换。
◆ 哈夫曼树的定义、构造及求哈夫曼编码。
补充：
1.满二叉树和完全二叉树有什么区别？
答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。
2.Huffman树有什么用？
最小冗余编码、信息高效传输
第七章 图 内容提要：
◆ 图的定义，概念、术语及基本操作。 图：记为 G＝( V, E )
其中：V 是G 的顶点集合，是有穷非空集； E 是G 的边集合，是有穷集。 术语：见课件
◆ 图的存储结构。 1.邻接矩阵(数组)表示法
① 建立一个顶点表和一个邻接矩阵
② 设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edge[n][n]。 注：在有向图的邻接矩阵中，
第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。
邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。
邻接矩阵法缺点：n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 2.邻接表(链式)表示法
① 对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域:
② 每个单链表还应当附设一个头结点（设为2个域），存vi信息； ③ 每个单链表的头结点另外用顺序存储结构存储。 邻接表的优点：空间效率高；容易寻找顶点的邻接点；
邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。
◆ 图的遍历。
遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。 图常用的遍历：一、深度优先搜索；二、广度优先搜索 深度优先搜索（遍历）步骤： ① 访问起始点 v;
② 若v的第1个邻接点没访问过，深度遍历此邻接点；
③ 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。 基本思想：——仿树的先序遍历过程。
广度优先搜索（遍历）步骤：
① 在访问了起始点v之后，依次访问 v的邻接点；
② 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点； ③ 直到所有顶点都被访问过为止。
◆ 图的应用（最小生成树，最短路经）
最小生成树（MST）的性质如下：若U集是V的一个非空子集，若(u0, v0)是一条最小权值的边，其中u0?U，v0?V-U；则：(u0, v0)必在最小生成树上。
求MST最常用的是以下两种：Kruskal（克鲁斯卡尔）算法、Prim（普里姆）算法 Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。 Prime算法特点: 将顶点归并，与边数无关，适于稠密网。
在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。 两种常见的最短路径问题：
一、 单源最短路径—用Dijkstra（迪杰斯特拉）算法 二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法
一、单源最短路径 (Dijkstra算法)一顶点到其余各顶点（v0→j）
目的： 设一有向图G=（V, E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。 二、所有顶点之间的最短路径
可以通过调用n次Dijkstra算法来完成，还有更简单的一个算法：Floyd算法（自学）。
学习重点： 图是应用最广泛的一种数据结构，本章也是这门课程的重点。 ◆ 基本概念中，连通分量，生成树，邻接点是重点。
① 连通图：在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。 如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 ② 生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。 ③ 邻接点：若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。
◆ 图是复杂的数据结构，也有顺序和链式两种存储结构：数组表示法（重点是邻接距阵）和邻接表。这两种存储结构对有向图和无向图均适用
◆ 图的遍历是图的各种算法的基础，应熟练掌握图的深度、广度优先遍历。
◆ 连通图的最小生成树不是唯一的，但最小生成树边上的权值之和是唯一的。 应熟练掌握prim和kruscal算法，特别是手工分步模拟生成树的生成过程。
◆ 从单源点到其他顶点，以及各个顶点间的最短路径问题，掌握熟练手工模拟。
补充：
1.问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？ 答：是树！而且是一棵有向树！
2.讨论：邻接表与邻接矩阵有什么异同之处？
1. 联系：邻接表中每个链表对应于邻接矩阵中的一行， 链表中结点个数等于一行中非零元素的个数。 2. 区别：
对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致）， 但邻接表不唯一（链接次序与顶点编号无关）。 3. 用途：
邻接矩阵多用于稠密图的存储 而邻接表多用于稀疏图的存储
3.若对连通图进行遍历，得到的是生成树
若对非连通图进行遍历，得到的是生成森林。