左指针域 右指针域
三、树与二叉树的转换 1．树转换为二叉树
孩子域 兄弟域 ① 将树转换为二叉树，只要将树中各结点的第一个孩子看作左孩子，第一个兄弟看作右孩子即可。
② 任一棵树对应的二叉树的右子树必空。 2．森林转换为二叉树
① 将每棵树先转换为二叉树B1，B2，?，Bn
② 以B1为基准，将B2作为B1根结点的右子树，将B3作为B2根结点的右子树，? 3．二叉树转换为森林
① 将二叉树根结点的右子树撤去，得到多棵二叉树B1，B2，?，Bn ② 将二叉树分别转换为树T1，T2，?，Tn。 四、树的遍历
先根遍历：根结点、各棵子树 后根遍历：各棵子树、根结点 层次遍历
6．4哈夫曼树和判定树
一、基本术语
1．叶子结点的路径长度：从根结点到某个叶子结点所经过的分支数。 2．树的路径长度：树中各叶子结点的路径长度之和。 3．叶子结点的权：各叶子结点出现的概率。 4．带权路径长度（WPL）
各个叶子结点的权wi与相应的路径长度li乘积之和，称为树的带权路径长度。
WPL??wili
i?1n二、哈夫曼树 1．什么叫哈夫曼树？
带权路径长度WPL最小的二叉树，称为哈夫曼树。 特点：
① 一般地说，权值越大的叶子结点离根越近。 ② 哈夫曼树的时间性能最好，是最优的二叉树。 ③ 哈夫曼树中各结点的度只能是0或2。
16
④ 具有n个结点的哈夫曼树共有2n-1个结点。 2．如何构造一棵哈夫曼树？（参考P88） 3．哈夫曼编码
对一棵哈夫曼树约定：指向左孩子的分支表示为0，指向右孩子的分支表示为1。取从根到叶子结点一路上的“0”或“1”组成的序列，称为叶子结点的前缀编码。 三、分类和判定树
1．用于描述分类问题的二叉树称为判定树。
判定树的每个分支结点对应一种判断，每个叶子结点对应一种分类结果。
2．一个分类问题对应着若干棵判定树，其中必有一棵判定树的WPL最小，WPL又称平均比较次数。
3．一棵判定树对应着一种算法，哈夫曼树对应的算法的时间性能最好。 4．如何对一个分类问题写最优的算法？ ① 对分类结果画哈夫曼树； ② 根据哈夫曼树写算法；
第7章 图 7．1 图的定义和术语
一、图的定义
图G由顶点集V和边集E组成，记为G=（V，E）。 ① 最简单的图只有一个顶点； ② 每条边由其连接的两个顶点表示：
例：无向边（v1 ，v2）；有向边< v1 ，v2>，< v2 ，v1> 二、术语 1．邻接点
若顶点vi，vj存在一条边，则vi，vj互为邻接点。
在有向边
若存在一条有向边
① 顶点的度：与顶点v相关联的边数，记为D（v）； ② 顶点的入度，出度：
在有向图中，顶点v的入边的数目，称为入度，记为ID（v）； 顶点v的出边的数目，称为出度，记为OD（v）； D（v）= ID（v）+ OD（v）
17
4．无向完全图，有向完全图
无向完全图：任意两个顶点之间都存在一条边的无向图；
有向完全图：任意两个顶点之间都存在方向相反的两条边的有向图； 5． 子图
设有两个图G=（V，E）和G′=（V′，E′），若V′是V的子集，E′是E的子集，则G′是G的子图。 6． 连通图和连通分量
连通：在无向图中，若两个顶点有路径，则称两顶点是连通的； 连通图：任意两个顶点都连通的无向图； 连通分量：无向图中的极大连通子图。 7． 强连通图和强连通分量
强连通：在有向图中，若vi到
vj，vj到vi都有路径，则称vi，vj是强连通的；
强连通图：任意两个顶点都强连通的有向图； 强连通分量：有向图中的极大连通子图。 8．带权图：又称网
带权有向图（有向网） 带权无向图（无向网）
7．2 图的存储结构
一、邻接矩阵 1．邻接矩阵的构建
① 将各个顶点排成一行和一列，形成矩阵。
② 若行、列顶点之间存在一条边，则对应元素记1，否则，对应元素记0。 2．邻接矩阵的特点
无向图的邻接矩阵是对称的，有向图的邻接矩阵一般不对称。 3．用邻接矩阵表示加权图
只要把1元素换成相应边的权值，0元素换成∞即可。 4． 邻接矩阵的用途
便于查找每个顶点的度、入度、出度。
无向图：每个顶点的度等于该顶点相应的行或列中1元素的个数。
有向图：每个顶点的出度等于该顶点相应行中1元素的个数，入度等于相应列中1元素的个数。 二、邻接链表
树的孩子链表、图的邻接链表组织结构相同。 1．邻接链表的构建
18
① 为每个顶点建立一个邻接链表，一个图有几个顶点，就有几个邻接链表。 ② 顶点x的邻接链表是一个带头结点的单链表，用于存储与x相邻接的顶点序号。 ③ 将所有头结点组织成一维数组。 2．邻接链表的用途
便于求顶点的度、出度。
无向图：每个顶点的度等于它的邻接链表中表结点的个数。 有向图：每个顶点的出度等于它的邻接链表中表结点的个数。 3．如何求顶点的入度？
构造一个逆邻接链表，即顶点x的逆邻接链表存储的是与x的入边相关联的顶点序号。 注：一个图的邻接矩阵是唯一的，但邻接表一般不唯一。
7．3 图的遍历
1．树的遍历
先根遍历：根结点、各棵子树 后根遍历：各棵子树、根结点 层次遍历
2．图的遍历：适应于无向图，也适应于有向图。 深度优先搜索遍历：类似树的先根遍历。 广度优先搜索遍历：类似树的层次遍历 3．深度优先搜索遍历：
首先访问出发点Vi，然后任选一个Vi的未访问过的邻接点Vj，以Vj为新的出发点继续进行深度优先搜索。
深度优先搜索遍历、广度优先搜索遍历得到的顶点序列不唯一。
7．4 图的应用
一、最小生成树 1．什么叫生成树？
从n个顶点的连通图G中，取它的全部顶点和n-1条边构成子图G′，如果这些边刚好将G′的全部顶点连通但又不形成回路，则称子图G′是G的一棵生成树。
注意：① 一个连通图可以有多棵生成树。 ② 生成树是边数极少的连通子图。 ③ 连通分量：指极大连通子图。
④ 根据图的宽度优先遍历或深度优先遍历可构造生成树。 2．最小生成树
① 生成树的权：各条边权值之和 权值最小的生成树，称为最小生成树。
19
② 带权无向图才可构造最小生成树。
求造价最低的通讯网问题，实际是求最小生成树问题。 3．构造最小生成树的算法：Prim（普里姆）算法 二、拓扑排序 1．拓扑序列
在有向图中，若不存在回路，则所有顶点可排成一个线性序列，以便列出各顶点的前后关系，称此序列为拓扑序列。
2．拓扑排序：实现有向图的一个拓扑序列的过程。
任何一个有向无环图，其全部顶点可以排成一个拓扑序列，且其拓扑序列不唯一。 若图中入度为0的顶点和出度为0的顶点都是唯一的，则其拓扑序列是唯一的。 3．构成有向图拓扑序列的过程
① 从图中选择一个入度为0的顶点，输出该顶点。 ② 从图中删除该顶点及其相关联的所有边。 ③ 重复执行1，2，直到找不到入度为0的顶点。 三、最短路径 1．最短路径问题
① 带权有向图才存在最短路径问题。
② 图的路径长度：一条路径上各条边的权值之和。
2．求一个源点到其余各个顶点的最短路径：Dijkstra 迪杰斯特拉）算法
从源点到其余各个顶点的最短路径中，先求最短的一条，再求次短的一条，以此顺序，最后求最长的一条。 3．Dijkstra算法描述
① 假设S为顶点集合，初值为源点v0。
② 首先从v0出发的所有边中找出权值最小的边的终点加入到S中。
③ 下一条最短路径是终点不在S中，中间只经过S中的顶点且路径长度最短，找到后将终点加入到S中。
④ 反复执行（3），直到所有顶点都加入到S中。 例：根据P115图7.17，求顶点V1到其余各顶点的最短路径。
终点 V2 V3 V4 V5 集合S 20