下一页
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学
计算机教学实验中心
第 5单元
非线性数据结构
图
下一页
上一页
停止放映
第 2 页
上节内容提要
1.树的定义
2.树的基本概念
结点, 结点度, 根, 支, 叶结点
子结点, 父结点, 兄弟结点
树的度, 路径, 长度, 深度
森林, 有序, 无序
下一页
上一页
停止放映
第 3 页
上节内容提要
3.二叉树
二叉树的定义
二叉树的性质 （ 每层结点个数, 总结点数 ）
二叉树的存储结构,顺序存储, 记录数组结构 (结点, 左
子, 右子 ),链式存储结构 （ 二叉链表三叉链表 ）
4.特殊二叉树
满二叉树 （ 性质 ）, 完全二叉树 （ 性质 ）, 平衡二叉树,
二叉排序树 ）
5.二叉树的遍历操作 （ 前序, 中序, 后序 ）
6.树的存储结构,
数组实现方法 （ 双亲表示法 ）, 链表实现方式 （ 孩子表
示法 ）, 二叉链表实现方式 （ 孩子兄弟表示法 ）
7.树, 森林与二叉树的转换
下一页
第 5单元
非线性数据结构
图
下一页
上一页
停止放映
第 5 页
一,图及其基本概念
? 图是一种较之线性表和树形结构更为复杂
的非线性数据结构 。 图中各数据元素之间
的关系可以是任意的, 描述的是, 多对多,
的关系 。
? 图 是对结点的 前趋和后继个数不加限制 的
数据结构 。
下一页
上一页
停止放映
第 6 页
图（ Graph）的定义
? 图 G = （ V,E ）
其中,V={ v1,v2,……,vn}是非空 有穷的
结点集合 ;E 是顶点偶对的集合 。
? 例, 图 G1 = （ V,E）
V={v1,v2,v3,v4}
E={（ v1,v2）, （ v1,v3）,
（ v2,v1）, （ v2,v3）,
（ v2,v4）, （ v3,v1）,
（ v3,v2）, （ v4,v2）
}
o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 7 页
有向图、无向图
? 有向图（ Digraph）
图 G中 顶点的偶对若是有向的,形成的图称有向图。
如图 G2所示。
为示区别，其偶对用 <vx,vy>表示。
? 无向图（ Undigraph）
图 G中 顶点的偶对若是无向的,形成的图称为无向
图，其偶对用 （ vx,vy） 表示 (区别在括号 )，如图 G1
所示。
? G2=（ V,E）
V={ 1,2,3,4}
E={〈 1,2〉, 〈 1,3〉
,〈 3,4〉, 〈 4,1〉 }
1
3
2
4
G2
下一页
上一页
停止放映
第 8 页
边、弧
? 边 （ Edge）
顶点间的关系可描述为顶点的偶对, 也称为顶点的边 。
记为,（ Vx,Vy） 。 边是无序的, 可以看成是 （ Vx，
Vy）, 也可以看成是 （ Vy,Vx） 。
? 弧 （ Arc）
若顶点间的边是有方向性 （ 有序 ） 的, 则称该偶对为弧 。
记为,〈 Vx,Vy〉 。 弧是有序的, 〈 Vx,Vy〉 表示从
Vx到 Vy。
? 弧头 （ Head）
弧的终点 （ TerminaL Node） 称为弧头 （ 方向前方 ） 。
? 弧尾 （ Tail）
弧的起始点 （ Initial Node） 称为弧尾 （ 方向后方 ） 。
弧 〈 Vx,Vy〉 表示为, Vx Vy
弧尾 弧头
下一页
上一页
停止放映
第 9 页
顶点、邻接点
? 顶点 （ Vertex）, 图中的数据元素 （ 结点 ） 称为顶点 。
如图 G1,G2中的Ｖ 1,Ｖ 2,1,2。
? 邻接点 （ Adjacent）
– 无向图中, 若边 （ Ｖ x,Ｖ y） ? E，
则Ｖ x,Ｖ y互为 邻接点 。
– 有向图中, 若弧 〈 Ｖ x,Ｖ y〉 ? E，
则 Ｖ y是Ｖ x的邻接点, 反之, 不是 。 (弧头是弧尾的邻接点 )
Vx Vy
Ｖ x、Ｖ y互为邻接点
Vx Vy
Ｖ y是Ｖ x的邻接点
1
3
2
4
G2
o o
oo
v1 v2
v3 v4G1
下一页
上一页
停止放映
第 10 页
顶点的度（ Degree）
? 无向图 中, 顶点的 度 是以该顶点为一个端点的边
的条数 。 例如, G1中 V2的度为 3,V4的度为 1。
? 有向图 中, 以某顶点为弧头的弧的数目称为该顶
点的 入度 （ Indegree） 。 例如 G2中顶点 1的入度
为 1。 以某顶点为弧尾的弧的数目称为该顶点的
出度 （ Outdegree） 。 例如 G2中顶点 1的出度为 2。
该 顶点的度 =入度 +出度 。 例如, G2中顶点 1的度
=2+1=3。
o o
oo
v1 v2
v3 v4
G1
1
3
2
4
G2
下一页
上一页
停止放映
第 11 页
路径、长度
? 路径 （ Path）
在图中, 从顶点 Vx到顶点 Vy的顶点序列 （ Vx,V1，
V2,…,Vn,Vy)称为从 Vx到 Vy的路径 。 路径可能是
不唯一的 。 例如, G1中, V1到 V3的路径为：
（ V1V2V3） 或 （ V1V3） ；而 G2中, 1到 4的路径为
<134>。
? 长度 （ Length）
路径的长度是该路径 上边或弧的数目 。 例如, G1
中 V1到 V3的长度为 1或 2；而 G2中 1到 4的长度为 2。
1
3
2
4
G2
o o
oo
v1 v2
v3 v4
G1
相应的边必
须在图中
下一页
上一页
停止放映
第 12 页
连通图、强连通图、连通分 量
1 2
? 连通图（ Connected Graph）
在无向图中,若每一对顶点间都有路径，
称此图是连通图。如图 G3所示。
? 连通分量（ Connected Component）
无向图中的 极大连通子图称为连通
分量 。 （ 连通图有一个分量, 非连通图
有多个连通分量 ）
? 强连通图 （ Strongly Connected
Graph）
在有向图中, 若 每对顶点 Vx到 Vy
间都存在 Vx到 Vy,及从 Vy到 Vx的路径,
则称此图是强连通图 。 如图 G4所示 。
（ 有去有回 ）
3
4 5
G3
21
3
4 5
G4
下一页
上一页
停止放映
第 13 页
子图、生成树
? 子图
有两个图 G和 G1,若 V1?V,E1 ? E,即 V1中的顶点
G = （ V,E） 都属于 V中的顶点, E1中的关系都
G1 =（ V1,E1） 属于 E中的关系, 则称 G1是 G的子图 。
（图的部分顶点和部分边组成的图）
? 生成子图, 生成树
设 G是一个连通图, G中任一包含 G的所有顶点的子图
称为 生成子图 。 如果该子图是树, 则称为 G的 生成树 。
G的生成树不是唯一的 。 一棵有 n个顶点的生成树,
有且仅有 n-1条边 （ 弧 ） 。
（ 子图包含所有顶点, 但不一定包含所有边 ）
下一页
上一页
停止放映
第 14 页
网、权
? 权 （ Weight）
若图的边或弧带有与之相关的数, 称此数为该
边或弧的权 。 权通常用来表示从一个顶点到另
一个顶点的距离或费用 。
? 网 （ Network） (赋权图 )
带权的图 称为网 。 如 G5为带权的网 。
V1 V2
V3V4
G523
5
7
下一页
上一页
停止放映
第 15 页
图的应用实例
? [路径问题 ] 城市中有许多街道，每一个十字路口都可以
看作图中一个顶点，邻接两个十字路口之间的每一段街
道既可以看作一条，也可以看作两条有向边。如果街道
是双向的，就用两条有向边。如果街道是单向的，就用
一条有向边 。 (路线咨询 )
下一页
上一页
停止放映
第 16 页
图的应用实例
? [生成树 ] 设 G= (V,E)是一个无向图，当且
仅当 G中每一对顶点之间有一条路径时，可
认为 G是连通的（ c o n n e c t e d）
? 一个 n节点的连通图必须至少有 n- 1条边。
因此当通信网络的每条链路具有相同的建
造费用时，在任意一棵生成树上建设所有
的链路可以将网络建设费用减至最小，并
且能保证每两个城市之间存在一条通信路
径。如果链路具有不同的耗费，那么需要
在一棵最小耗费生成树上建立链路。
下一页
上一页
停止放映
第 17 页
图的应用实例
下一页
上一页
停止放映
第 18 页
二、图的存储结构
? 1、邻接矩阵表示法
? 根据图的定义可知，图的逻辑结构分为两部分,V（顶
点）和 E（边或弧）的集合。因此，
– 用一个一维数组存放图中所有顶点数据；
– 用一个二维数组存放顶点间关系（边或弧）的数据，
称这个二维数组为 邻接矩阵 。
– 邻接矩阵又分为 有向图邻接矩阵 和 无向图邻接矩阵 。
1 2 3 4
1 0 1 0 1
2 1 0 1 0
3 0 1 0 1
4 1 0 1 0
下一页
上一页
停止放映
第 19 页
有向图的邻接矩阵
? 定义
设图 G=（ V,E） 是有 n（ n ? 1） 个顶点的图, 则 G的邻
接矩阵是具有下述性质的 nxn的方阵, 元素为：
1 当 〈 Vi,Vj>? E 时 （ 存在弧 ）
A[ i,j] =
0 当 〈 Vi,Vj>? E 时 （ 不存在弧 ）
例如, G2的邻接矩阵为：
G.nodes=
1
2
3
4
A= G.Arc=
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0 4x4
1
3
2
4
G2
注意：不一定对称，对角线全为 0
下一页
上一页
停止放映
第 20 页
无向的图邻接矩阵
? 定义
设图 G=（ V,E）是有 n（ n ? 1）个顶点的图，则 G的邻
接矩阵是具有下述性质的对称阵，元素为：
1 当 (Vi,Vj） ? E 时 (有边 )
A[ i,j] =A[j,i] =
0 当 (Vi,Vj） ? E 时（无边）
无向图的邻接矩阵是一个对称矩阵
例如,G1的邻接矩阵为：
G.nodes =
1
2
3
4
A=G.edge =
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0 4x4
o o
oo
v1 v2
v3 v4
G1
注意：一定对称，对角线全为 0
下一页
上一页
停止放映
第 21 页
求图中顶点的度
? 借助邻接矩阵,可以很容易地求出图中顶点
的度 。
– 无向图 邻接矩阵的第 i行 （ 或第 i列 ）
的元素之和是顶点 Vi的度 。 例, G1中 V2
的度是 3。 （ 上页图 ）
– 有向图 邻接矩阵第 i行的元素之和为顶
点 Vi的出度；第 j列的元素之和为顶点 Vj
的入度 。 例, G2中, V2的出度为 0（ 第 2
行的元素之和为 0）, V1的入度为 1（ 第 1
列的元素之和为 1） 。
o o
oo
v1 v2
v3 v4
G1
A= G.Arc=
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
1
3
2
4
G2
下一页
上一页
停止放映
第 22 页
网的邻接矩阵
? 定义：
Wij 若 （ Vi,Vj） 或 〈 Vi,Vj〉 ? E(有边 )
A[i,j] =
? 若 （ Vi,Vj） 或 〈 Vi,Vj〉 ? E（ 无边 ）
G.nodes=
V1
V2
V3
V4
A=G.Arc=
? 5 ? 3
? ? 2 ?
? ? ? ?
? ? 7 ? 4x4
G5的邻接矩阵。
V1 V2
V3V4
G523
5
7
？为什么不用 0表示无边或弧？
对称？
下一页
上一页
停止放映
第 23 页
A
1 2
B 3 C
2、邻接表表示法
? 邻接表是图的一种链式存储结构 。 对图的 每个顶点建立
一个单链表 （ n个顶点建立 n个单链表 ）, 第 i个单链表
中的结点包含顶点 Vi的所有邻接顶点 。
? 在邻接表中, 每个顶点由三个域组成：
? 每个单链表附设一个头结点, 结构为：
adjvex data nextarc
顶点 Vi的邻接点
（名称 or编号） 与边或弧有关的权值
指向 Vi的下一个
邻接点的指针
Vexdata firstarc
指向 Vi单链表的第一个结点存放 Vi信息
A
B 1
C 2 null
下一页
上一页
停止放映
第 24 页
邻接表存储结构描述
C语言描述
#define VTXNUM n
struct arcnode { //定义弧结点
int adjvex；
float data；
struct arcnode *nextarc； //下一个邻接点
}；
typedef struct arcnode ARCNODE ；
struct headnode { //定义头结点
int data ；
ARCNODE * firstarc ； //第 1个邻接点
} adjlist[VTXNUM]； //头结点数组
下一页
上一页
停止放映
第 25 页
无向图 G1的邻接表
V1
V2
V3
V4
^V3V2
V1 V4 ^V3
^V1 V2
^V2
顶点 Vi的度恰好就是
第 i个单链表中的结点数。o o
oo
v1 v2
v3 v4
G1 注：边无权，节点只需两个
域
下一页
上一页
停止放映
第 26 页
有向图 G2的邻接表
1
2
3
4
^23
^4
^1
^
?描述,在有向图中，第 i个单链表中结点的个
数是顶点 Vi的出度；
?特点,求出度方便，求入度，必须遍历整个邻
接表。
1
3
2
4
G2
头结点 链 表
下一页
上一页
停止放映
第 27 页
逆邻接表
? 描述,为求顶点 Vi的入度, 对每个顶点 Vi,建
立一个链接以 Vi为弧头的邻接点链表, 称该表
为逆邻接表 。 例如 G2的逆邻接表为：
1
2
3
4
4
1
1
3
^
^
^
^
特点,方便求入度。
显然逆邻接表的单链表 i中结点的个数
就是顶点 Vi的入度。
1
3
2
4
G2
下一页
上一页
停止放映
第 28 页
建立邻接表的算法
? 操作步骤：
– step1 初始化邻接表的 n个头结点,
– Step2 读入一条弧或边的偶对 〈 i,j〉 或
（ i,j） 。
– step3 申请一个结点 S的空间, 将 S插入到
第 i个单链表中；
– step4 读下一条弧或边的偶对, 若存在此
弧或边, 则继续执行 step2；否则, 结束 。
下一页
上一页
停止放映
第 29 页
建立邻接表算法的程序
createadjlist(struct headnode G[],int n)
{ int i,j,k; float w; ARCNODE *s;
for (k=1; k<= n ; k++ )
{ scanf(,%d”,&G[k].data); //初始化 n个头结点
G[k].firstarc = NULL ;
}
scanf(“%d,%d,%f”,&i,&j,&w ); //输入边和权
while (( i >=0 && i <n)&&(j>=0 && j<n)) //合法性校验
{ s= (ARCNODDE *)malloc(sizeof(ARCNODE)); //申请结点空间
s->adjvex = j; //总是将结点插在第 I个头结点和其第一个邻结点之间
s->info = w;
s->nextarc = G[i].firstarc;
G[i].firstarc = s;
scanf(“%d,%d,%f”,&i,&j,&w);
}
} i null k wk null
j wj null
s1
s2
下一页
上一页
停止放映
第 30 页
三、图的遍历
? 图的遍历 （ Traversing Graph）
从图中指定顶点出发访问图中每一个顶点, 且使每个
顶点只被访问一次, 该过程为图的遍历 。
? 图的遍历要比树结构复杂的多 。 出发点不同, 任一
顶点的邻接点就不相同, 路径也就不同 。
? 因为图中元素是, 多对多, 的关系, 为避免发生重
复, 设立一个辅助数组 visited[],每访问一个顶点,
便将其状态 visited[i]置为, 真, 。
? 常用的图的遍历方法有两种：
– 深度优先遍历法
– 广度优先遍历法 图的遍历序列
不是唯一的
下一页
上一页
停止放映
第 31 页
深度优先遍历法
? 深度优先遍历法类似于树的先根遍历法 。
? 算法思想：
– step1 从图中某个顶点 V0出发, 并访问此顶点；
– step2 从 V0出发, 访问与 V0邻接的顶点 V1后, 再从
V1出发, 访问与 V1邻接 且未被访问过的 顶点 V2。 重
复上述过程, 直到不存在未访问过的邻接点为止 。
– step3 如果是连通图, 从任一顶点 V0出发, 就可以
遍历所有相邻接的顶点；如果是非连通图, 则再选
择一个未被访问过的顶点作为出发点, 重复 step1、
step2,直到全部被访问过的邻接点都被访问为止 。
下一页
上一页
停止放映
第 32 页
深度优先遍历法举例
遍历过程 访问顶点 所过边
?起始顶点 V1 V1
?V1的第 1个邻接点 V3 V3 （ V1,V3）
?V3的第 1个邻接点 V1已访问，取下
一个邻接点 V5 V5 （ V3,V5）
?V5的第 1个邻接点 V3已访问，取下
一个邻接点 V2 V2 （ V5,V2）
?V2的两个邻接点均被访问，
回退 到 V5,V5的邻接点均被访问，
回退到 V3,V3的邻接点均被访问,
回退到 V1,V1的另一个邻接点 V4
未被访问 V4 （ V1,V4）
?V4的第一个邻接点 V1已被访问，
另一个邻接点 V6未被访问 V6 （ V4,V6）
?V6的邻接点被访问，回退到 V4
?V4的邻接点均被访问
?回退到 V1，返回到出发点，遍历结束。
V1
V3
V5
V4
V6
G6
V2
示例
下一页
上一页
停止放映
第 33 页
遍历产生的结果
? 深度优先遍历 G6所走过的序列：
V1? V3 ? V5 ? V2 ? V4 ? V6
? 所走过的边：
（ V1,V3）, （ V3,V5）, （ V5,V2）, （ V1,V4）, （ V4，
V6）
? 由此生成一棵树, 称为 遍历生成树
V1
V3
V5
V2
V4
V6 求遍历序列时
不需写出生成树
下一页
上一页
停止放映
第 34 页
深度优先遍历算法程序 (非递归 )
Traver_dfs(struct headnode G[],int v)
{ int i,stack[N],visited[N],top=-1 ; ARCNODE *p;
for (i=0;i<N;i++) visited[I]=0; //所有结点未被访问
printf(“%d ->”,G[v].data); //访问初始结点
visited[v]=1; top ++; stack[top]=v; p=G[v].firstarc;
while((top!=-1)||(p!=NULL)) //栈非空, p非空循环
{ while(p!=NULL)
{ if (visited[p->adjvex]) p=p->nextarc;//所指节点已访问
else { printf(“%d ->”,G[p->adjvex].data);
visited[p->adjvex]=1; top++; stack[top]=p->adjvex;
p=G[p->adjvex].firstarc; } //访问未被访问的节点
if( top !=-1) //回退
{ v=stack[top]; top- -; p=G[v].firstarc;
p=p->nextarc; }
}
}
}？ if(top!=1)所处位置对不对
下一页
上一页
停止放映
第 35 页
广度优先遍历算法
? 广度优先遍历法类似于树的按层次遍历的过程。
即先访问第 1个顶点所有邻接点后，再访问下一
个顶点所有未被访问的邻接点。
? 算法思想：
– step1 从图中某个顶点 V0出发，并访问此顶点；
– step2 从 V0出发，访问 V0的各个未曾访问的邻
接点 W1,W2,…,Wk;然后,依此从 W1,W2,…,Wk
出发访问各自未被访问的邻接点。
– step3 重复 step2，直到全部顶点都被访问为
止。
下一页
上一页
停止放映
第 36 页
广度优先遍历法举例
遍历过程 访问顶点 所过边
?起始顶点 V1 V1
?访问 V1的未被访问过
的所有邻接点 V3,V2,V4 （ V1,V3）
(V1,V2)
(V1,V4)
?访问 V3的未被访问过
的所有的邻接点 V5 （ V3,V5）
?访问 V2的未被访问过
的所有的邻接点 无
?访问 V4的未被访问过
的所有的邻接点 V6 (V4,V6)
?所有顶点已被访问,结束。
V1
V3
V5
V4
V6
G6
V2
示例
？ 思考题：广度优先遍历算法的辅助数据结构？
下一页
上一页
停止放映
第 37 页
遍历产生的结果
? 广度优先遍历 G6所走过的序列：
V1? V3 ? V2 ? V4 ? V5 ? V6
? 所走过的边：
（ V1,V3）, （ V1,V2）, （ V1,V4）, （ V3,V5）, （ V4,V6）
? 遍历生成树
V1
V3
V5
V2 V4
V6
下一页
上一页
停止放映
第 38 页
四、图的常用基本操作
? LOC_VERTEX（ G,Vi） 确定顶点 Vi在 G中的位置 。
? GET_VERTEX（ G,i） 求图 G中第 i个顶点 。
? FIRST_VERTEX（ G,i） 求图 G中 Vi的第 1个邻接点 。
? NEXT_ADJ(G,v,w) 已知 w为 G中顶点 v的第 1个邻接点,
求顶点 w的下一个邻接点 。
? INS_VERTEX(G,u) 在图 G中插入一个顶点 u,为图 G的
第 n+1个顶点 。
? INS_ARC(G,v,w) 在图 G中插入一条从顶点 v到顶点 w
的弧 。
? DEL_VERTEX(G,Vi) 删除图 G中顶点 Vi,以及与 Vi相
关联的边或弧 。
? DEL_ARC(G,v,w) 删除图 G中从顶点 v到顶点 w的弧 。
下一页
上一页
停止放映
第 39 页
五、图的应用
? 最小生成树
? 拓扑排序
? 关键路径
? 最短路径
下一页
上一页
停止放映
第 40 页
最小生成树
? 即连通图的最小代价生成树 。 生成树上各边
（ 弧 ） 的代价之和最小 。
? 例如, 若要在 n个城市间建立通信联络网, 则只
需 n-1条线路 。 但在 n个城市间, 最多可能架设 n
（ n-1） /2条线路, 选择哪 n-1条线路, 使费用
最少 。
– 普里姆 （ Prim） 算法
– 克鲁斯卡尔 （ Kruskal） 算法
下一页
上一页
停止放映
第 41 页
普里姆（ Prim） 算法
? 设 N=（ V,E） 是连通图,
? U是最小生成树的 顶点集
? TE是最小生成树中 边的集合 。
– 从 U={u0} （ u0 ? V）, TE= 空开始；
– 重复执行,在所有 u?U,v ?V-U的边 （ u,v）
?E中找一条代价最小的边 （ u0,v0） 并入 TE,同
时 v0并入 U,直到 U=V为止；
– 此时 TE中必有 n-1条边, 则 T=（ V,TE） 为 N的最
小生成树 。
下一页
上一页
停止放映
第 42 页
普里姆（ Prim） 算法举例
1
2
3 4
5
6
8 7
2
1
4
35
7 6
8
11
10
9
12
U={1},V-U={2,3,4,5,6,7,8}
1
2
2
1
2
4
2
1
4 7
3
（ 1）
（ 2） （ 3）
(1) U={1,2},V-U={3,4,5,6,7,8}
(2) U={1,2,4},V-U={3,5,6,7,8}
(3) U={1,2,4,7},V-U={3,5,6,8}
1,2,4,7、
5,6,3,8
下一页
上一页
停止放映
第 43 页
普里姆（ Prim） 算法举例 (续 )
4 7
5
3
5
（ 4）
7
6
（ 5）
6
（ 6）
4 7
6
3 8
（ 7）
8 3
6
5
4 7
2
2 1
3
6
589
(4) U={1,2,4,7,5},V-U={3,6,8}
(5) U={1,2,4,7,5,6},V-U={3,8}
(6) U={1,2,4,7,5,6,3},V-U={8}
(7) U={1,2,4,7,5,6,3,8),V-U={ }
4 3
6
3
1
下一页
上一页
停止放映
第 44 页
克鲁斯卡尔（ Kruskal）算法
? 操作步骤,
– 假设 N=（ V,E） 是连通图, T为生成树
– 取图中每个顶点自成一个连通分量 (先看成 n个顶点, 无边 )
– 在 { E }中选择代价最小的边, 若该边所依附的顶
点落在 T中不同的连通分量上 （ 能把不连的点或树连起来 ）,
则将此边加入生成树 T中；否则, 舍去此边, 再选
择下一条代价最小的边 。
– 重复上述步, 直到 T中所有顶点都在同一连通分量
上为止 。
下一页
上一页
停止放映
第 45 页
克鲁斯卡尔（ Kruskal）算法举例
1
2 3 4
5 6
1 5
24
6
63
55
6
2
5
1
3
4
6
1
2
3
(4)
1
3
1 4
6
2
(3)
1
2 3 4
5 6
(1)
1
3
(2)
1
1-3,4-6
2-5,3-6
2-3
下一页
上一页
停止放映
第 46 页
克鲁斯卡尔（ Kruskal）算法举例 (续）
1
2 3 4
5 6
(5)
1
23 4
1
2 3 4
5 6
1 5
24
6
63
55
6
1
32
5 6
4
1
243
5
（ 6）
下一页
上一页
停止放映
第 47 页
拓扑排序
? 研究一个有机整体中不同个体间的次序问题 。
例如：课程间优先关系有向图问题 。
? 软件专业的课程优先关系：
课程编号 课程名称 先决条件
C1 程序设计基础 无
C2 离散数学 C1
C3 汇编语言 C1,C2
……
C9 高等数学 无
？ 选择一种选课顺序
下一页
上一页
停止放映
第 48 页
拓扑排序举例
? 方法步骤
– 在有向图中选一个没有前驱的顶点并输出 ;
– 从图中删除该顶点和所有以它为尾的弧 ;
– 重复前 2步,直到全部顶点均输出为止 。
– 输出序列即为拓扑排序序列 。
? 拓扑排序序列不唯一 。
?？ 二叉树的遍历序列唯一吗？
?？ 图的遍历序列唯一吗？
下一页
上一页
停止放映
第 49 页
拓扑排序举例
C1
C9
C4
C2
C3
C5
C7
C12
C10
C11
C6
C8
?C1 C2 C3 C4 C5 C7 C9 C10 C11 C6 C12 C8
?C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C8
下一页
上一页
停止放映
第 50 页
最短路径
? 研究的是类似于交通调度一类的带权有向图问题 。
求路径最短或费用最省 。
? 从源到其余各顶点的最短路径
? 原理,引进一个辅助向量 dist,它的每个分量
disk[i]表示当前所找到的从始点 v到每个终点 vi
的最短路径的长度 。 它的初始状态为：若从 v到
vi有弧, 则 disk[i]为弧上的权值；否则置
disk[i]为无穷,
? disk[j]=Min{disk[i]|vi∈V}
? 就是从 v出发的长度最短的一条最短路 （ v,vj）,
? 即 v到 vj的最短路 。
下一页
上一页
停止放映
第 51 页
最短路径
? 设 下一条最短路 的终点为 vk,则 这条路径
或者是 (v,vk)，或者是（ v,vj,vk），它的长
度或者是从 v到 vk的弧的权值，或者是
diak[j]和从 vj到 vk的弧上的权值之和,
? 算法,
? （ 1）假设用带权的邻接矩阵 cost来表示带
权有向图,cost[i,j]表示弧（ i,j）上的权值。
若（ vi,vj）不存在，则置 cost[i,j]为 ∞。
? S为已找到的从 v出发的最短路径的终点的
集合，它的初始状态为空集
? Disk[i]=cost[v,i],vi∈ V
下一页
上一页
停止放映
第 52 页
? （ 2）选择 vj，使得
? Disk[j]=min{disk[i]| vi∈ V-S}
? Vj就是当前求得的一条从 v出发的最短路径
的终点。
? S=S∪ {j}
? （ 3）修改从 v出发到集合 V-S上的任一顶点
vk可达的最短路径长度。如果
? disk[j]+cost[j,k]<disk[k]
? 则 disk[k]= disk[j]+cost[j,k]
? （ 4）重复（ 2）、（ 3）共 n-1次。 (p87例 )
下一页
上一页
停止放映
第 53 页
作业、思考题
第 2章
1、思考题,3,4,18
2、第 2章作业, 8,13,20
3,作业命名方式为,学号 _ch02_2
第 3章
思考题, p112 第 2,3,5~7,11题
作 业, p113 第 13题
命 名,学号 _ch03_1
下一页
上一页
停止放映
第 54 页
结束语
? 欢迎参加网上讨论，网站的地址：
http,//ctec.xjtu.edu.cn
? 下载课件的 FTP地址：
ftp,//ctec.xjtu.edu.cn
? 数字化课件的路径,
jec254\user2\tools\lzq\软件基础
? 答疑安排：
星期五晚 7,00～ 9,00
谢谢，再见！
下一页
上一页
停止放映
第 55 页
六、二叉排序树的生成 （树的应用）
对给定数列 {a1,a2,…,an},根据二叉排序树特性,逐个将
结点插入到二叉排序中 。
具体操作步骤：
step1 a1是根结点；对结点 ai：
step2 若 ai<aj,且 aj的左子为空,则将 ai插入到 aj的左子 ;
若 aj的左子非空,则继续寻找合适的插入位置 。
若 ai?aj,且 aj的右子为空, 则将 ai插入到 aj的右子；
否则继续沿右子树寻找合适的插入位置；
插入 ai 插入到 aj的左子 ai〈 aj
插入到 aj的右子 ai ? aj
step3 重复 step2，直到所有结点插入完为止。
(Flash)相关算法在后面，自己看 <goto 平衡二叉排序树
>
下一页
上一页
停止放映
第 56 页
二叉排序树算法
二叉排序树结点结构：
struct tree {
char info；
struct tree *left, * right ；
}
算法描述,
? 输入结点非空循环,若是第 1个结点,令指针
ROOT指向该结点。
? 打印输出该二叉排序树；
? 输入一个值，在该树中查找，若找到输出该
结点值；否则，显示查找失败。
下一页
上一页
停止放映
第 57 页
二叉排序树生成算法
建立二叉树
Create_btree()
查询结点
Search_btree()
打印二叉树
Print_btree()
主程序
Btree.C
下一页
上一页
停止放映
第 58 页
主程序框图
开始
初始化
输入结点数据
！ ROOT
root=create_btee（） create_btree()
结束?
N
Y
打印该树
查找指定结点
Print_btree()
Search_btree()
下一页
上一页
停止放映
第 59 页
生成二叉排序树程序框图
Create_btree() 开始
r = 0？
Y
申请结点空间
r = 0？显示“溢出”
结束
根结点的处理 N
Y
N
r->left = 0;
r->right = 0;
r->info = info ;
非根结点
info<r->info?Y
t=r->left t=r->right
N
调用本函数
root?
返回
Y N
r->left=0
r->right=0
root->left=r
或
root->right=r
下一页
上一页
停止放映
第 60 页
查询二叉排序树算法框图
开始 Search_btree()
!root
Y
显示“空树”
返回
N
root->info!=key循环
key<root->info?
root=root->left root=root->right
root=0?
NY
查找成功,显示 返回
显示“失败”
root!=0?
循环结束?
N
Y
下一页
上一页
停止放映
第 61 页
打印算法框图
开始 Print_btree()
r=0?
Y
N
调用自身打印左子
打印当前结点值
调用自身打印右子
返回
下一页
上一页
停止放映
第 62 页
主程序 Btree.C
#include,stdio.h”
struct tree {
char info;
struct tree *left,*right;
}
main ( )
{ char *s,*c,key=??;
struct tree *create_btree(),*search_btree(),*root=0;
do {
printf(“Enter a letter:”);
gets(s);
if (!root)
root=create_btree(root,root,*s);
else
create_btrr(root,root,*s);
} while (*s) ;
下一页
上一页
停止放映
第 63 页
主程序 Btree.C(续）
print_btree(root,0);
key=?1?;
while ( key)
{
printf(“Enter a key to find:”);
scanf(“%s”,&c);
key=search_btree(root,c);
printf(“press to continue\n”);
}
} /* Btree.C 结束 */
下一页
上一页
停止放映
第 64 页
生成二叉排序树程序
struct tree create_btree(root,r,info)
struct tree *root,*r;
char info;
{ if (r = =0 )
{ r=malloc(sizeof(struct tree));
if ( r = = 0)
{ printf(“Out of memory\n”); exit(0); }
r->left= 0; r->right=0; r->info=info;
if (root)
{ if(info<root->info) root -> left=r;
else root->right=r;
}
else
{ r->right=0; r->left = 0; }
return r;
} /* if = = 0 接下页 */
下一页
上一页
停止放映
第 65 页
生成二叉排序树程序 （续）
if (info < r->info)
create_btree(r,r->left,info);
if(info>=r->info)
create_btree(r,r->right,info);
} /* create_btree(root,r,info) */
下一页
上一页
停止放映
第 66 页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Emptu btree\n”); return root; }
while(root->info!=key)
{ if(key<root->info)
root=root->left;
else
root=root->right;
if(root==0)
{ printf(“Search Failure\n”);
break ;
}
} /* while(root->info!=key) */
查询二叉排序树程序
下一页
上一页
停止放映
第 67 页
if (root !=0)
printf(“Successful search\n key=%c\n”,root->info);
return root ;
} /* *search_btree(root,key) */
查询二叉排序树程序（续）
下一页
上一页
停止放映
第 68 页
打印二叉排序树程序
print_btree(r,l)
struct tree *r;
int l;
{ int i;
if (r = = 0) return ;
print_tree(r->left,l+1);
for(i=0;i<l;i++)
printf(“,);
printf(“%c\n”,r->info);
print_btree(r->right,l+1);
}
下一页
上一页
停止放映
第 69 页
程序输入
输入,输出：
h ? b
d ? d
p ? e
r ? h
b ? p
e ? r
?
下一页
上一页
停止放映
第 70 页
举例
对数列 {10,18,3,4,9,13,25},生成二叉排序树 。
10
（ 1）
10
18
（ 2）
10
3 18
（ 3）
10
3 18
4 （ 4）
10
3
4
18
9（ 5）
（ 7）
10
3
9
4
18
13 25
10
3
4
9
18
13
（ 6）
示例
下一页
上一页
停止放映
第 71 页
平衡二叉排序树
在二叉排序树的动态生成过
程中, 由于数据本身的特性, 将
影响二叉排序树的性质, 例如 {3，
5,7,9,20}这样的数列, 生成
的二叉排序树就是一棵单枝树 。
因此, 在动态生成二叉排序树的
过程中, 要进行平衡化处理 。
平衡化处理就是在
不影响 二 叉 排序树特性的前题
下, 通过, 旋转, 处理, 使该结
点
的平衡因子不大于 2。
旋转分,LL,RR,LR和 RL
四种 。
3
5
7
9
20
下一页
上一页
停止放映
第 72 页
LL平衡化处理
由于在 A的左子树的左
子树上插入结点, 使 A
点失去平衡, 需进行
一次 LL旋转 （ 顺时针
旋转 ） 操作 。
程序实现为：
b = a?.lc
a?.lc = b?.rc
b?.rc = a
a?.bf = 0
b?.bf = 0
b为子树的新根
A
B
C
LL B
C A
示例
示意为：
下一页
上一页
停止放映
第 73 页
RR平衡化处理
由于在 A的右子树的右子
树上插入结点, 使 A点
失去平衡, 需进行一次
RR旋转 （ 逆时针旋转 ）
操作 。
程序实现为：
b = a?.rc
a?.rc = b?.lc
b?.lc = a
a?.bf = 0
b?.bf = 0
b为子树新根
A
B
C
RR B
A C
示例
示意为：
下一页
上一页
停止放映
第 74 页
LR平衡化处理
程序实现为：
b = a?.lc,c = b?.rc,a?.lc = c?.rc
b?.rc = c?.lc,c?.lc = b,c?.rc = a
A
B
C
C
B A
A
C
B
示例
由于在 A的左子树的右子树上插入结点, 使 A点失去平
衡, 需进行一次 LR旋转 （ 两次旋转 ;先逆时针,再顺
时针旋转 ） 操作 。
示意为：
下一页
上一页
停止放映
第 75 页
RL平衡化处理
由于在 A的右子树的左子树上插入结点, 使 A点失去平衡,
需进行一次 RL旋转 （ 两次旋转 ;先顺时针,再逆时针旋转 ）
操作 。
A
B
C
C
A B
A
C
B
程序实现为：
b = a?.rc,c = b?.lc,a?.rc = c?.lc
b?.lc = c?.rc,c?.lc = a,c?.rc = b
示意为：
示例
下一页
上一页
停止放映
第 76 页
平衡化处理举例
有数据序列 {13,24,37,90,53}
? 插入 13,树是平衡的 ;
? 插入 24,树仍为平衡 ;
? 插入 37,树不再平衡,
执行 RR旋转 ;
? 插入 90,树仍平衡 ;
? 插入 53,失去平衡,
执行 RL旋转,
13
(1)
13
24
(2)
13
24
37 3713
24
(3)
24
13 37
90
(4)
24
13 37
90
53
24
13 37
53
90
24
13 53
37 90
(5)
示例
下一页
上一页
停止放映
第 77 页
Huffman(哈夫曼）树及应用
? Huffman树的定义
? 构造 Huffman树
? Huffman编码
? Huffman编码的译码
下一页
上一页
停止放映
第 78 页
Huffman树的定义
? Huffman树也称为最优树，是一类带权路径最短
的二叉树。
? 树的带权路径长度定义为：
WPL = ∑ wklk
k = 1
n
其中：
n 是树 中叶结点的个数
wi 是第 i个 结点的权值
li 是第 i个结点的路径长度
下一页
上一页
停止放映
第 79 页
Huffman树举例
? 以下有三棵树：
（ a） （ b） （ c）
a
b
c d
a b c d
a
c
b
d7
7
7
5
5
52
2
2
4 4
4WPLa =7x2+5x2+2x2+4x2
= 36 WPL
b =7x3+5x3+2x1+4x2
= 46
WPLc =
7x1+5x2+2x3+4x3
= 35 √
? 事实证明按哈夫曼树构造二叉树，可得到很好的特
性，应用于实际问题，可提高处理效率。
结点个数及权相同，
不同组合得到不同的带权路径长度
下一页
上一页
停止放映
第 80 页
应用举例
? 由统计规律可知，考试成绩的分布符合正态分布：
-1 10
分数 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100
比例数 0.05 0.15 0.40 0.3 0.10
? 根据正态分布规律，在 60 ～ 90之间的分数占 85%，
而不及格和优秀是少数。
下一页
上一页
停止放映
第 81 页
将百分制转换成五分制
? 判定树比较,a<60?
a<70?
a<80?
a<90?
不及格
及格
中等
良好 优秀
Y
Y
Y
Y
N N
N
N
a<80?
a<70? a<90?
a<60?
不及格
优秀良好中等及格不及格
Y
Y
Y N
N
N NY
(A)
(B)
? 若输入 1万个数据，按 A的判定过程进行操作，约需比较 3.2
万次，而按 B比较,则仅需 2.2万次。
下一页
上一页
停止放映
第 82 页
构造 Huffman树
? 构造 Huffman树算法步骤：
– 1）将 n个带权值 wi（ i≤n）的结点构成 n棵二叉树
的集合 T={T1,T2,……, Tn}，每棵二叉树只有一
个根结点。
– 2）在 T中选取两个权值最小的结点作为左右子树，
构成一个新的二叉树，其根结点的权值取左右子树
权值之和；
– 3）在 T中删除这两棵树，将新构成的树加入到 T中；
– 4）重复 2）,3）步的操作，直到 T中只含一棵树
为止，该树就是 Huffman树。
下一页
上一页
停止放映
第 83 页
构造 Huffman树举例
? 以权值分别为 7,5,2,4的结点 a,b,c,d构造 Huffman树。
T= { a b c d }
c d
T
32 4
6
b T3
T
2 65
11
b
T
2 65
11
c d2 4
18
a T27
11
T
1
6
18
a7
T
1
b T3
T
25
11
18
a7
T
1
b5
11
c d2
6
4（ d） T={ T1 }
（ c） T= { a T2 }
（ b） T= { a b T3 }
（ a） T= { a b c d }
代入 T2
代
入T
3
示例
下一页
上一页
停止放映
第 84 页
Huffman树的应用,Huffman编码
? 编码：用二进制数的不同组合来表示字符的方法。
? 前缀编码：一种非等长度的编码 (任一个字符的编码
都不是另一个字符编码的前缀 )。
a
0
b
0
1
c d
0
1
1
编码,A（ 0）
B（ 10）
C（ 110）
D（ 111）
方法约定：
1）左分支为‘ 0’
2）右分支为‘ 1’
3）由叶到根路径上字符组
成的二进制串就是该叶结点
的编码。
? Huffman编码：一种非等长度的编码。以给定权
值的结点构造 Huffman树，按二进制前缀编码的
方式构成的编码为 Huffman编码。
下一页
上一页
停止放映
第 85 页
Huffman编码举例
? 在某系统的通信联络中可能出现 8种字符，其频率
分别为 0.05,0.29,0.07,0.08,0.14,0.23、
0.03,0.11，设权值分别为 {5,29,7,8,14，
23,3,11},n=8，其 Huffman树为：
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 86 页
Huffman编码存储结构
? 由于 Huffman树中 没有度为 1的结点,则 n个叶结点
的 Huffman树共有 2n-1个结点。例如,4个结点的
Huffman树，共有 7个结点。因此可以用长度为 2n-1
的一维数组存放。
? 求 Huffman编码,从叶到根的编码。因此要知道每
个结点的父结点。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 87 页
Huffman编码的译码
? 从 Huffman编码树上不难看出，代码全部在叶结
点上，根据 Huffman编码，就能求出相应的字符。
该过程称为“译码”。
? 译码是根据从根到叶的 Huffman编码求相应的字
符。因此要知道每个结点的左右子结点。
? 例如，根据,1111”，就能求出对应的字符是,8”。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Typedef strudt{
Unsigned int weight;
Unsigned int pa,lc,rc;
}Htnode *HT;
计算机软件基础
The software basic
of computer
主讲：赵英良
西安交通大学
计算机教学实验中心
第 5单元
非线性数据结构
图
下一页
上一页
停止放映
第 2 页
上节内容提要
1.树的定义
2.树的基本概念
结点, 结点度, 根, 支, 叶结点
子结点, 父结点, 兄弟结点
树的度, 路径, 长度, 深度
森林, 有序, 无序
下一页
上一页
停止放映
第 3 页
上节内容提要
3.二叉树
二叉树的定义
二叉树的性质 （ 每层结点个数, 总结点数 ）
二叉树的存储结构,顺序存储, 记录数组结构 (结点, 左
子, 右子 ),链式存储结构 （ 二叉链表三叉链表 ）
4.特殊二叉树
满二叉树 （ 性质 ）, 完全二叉树 （ 性质 ）, 平衡二叉树,
二叉排序树 ）
5.二叉树的遍历操作 （ 前序, 中序, 后序 ）
6.树的存储结构,
数组实现方法 （ 双亲表示法 ）, 链表实现方式 （ 孩子表
示法 ）, 二叉链表实现方式 （ 孩子兄弟表示法 ）
7.树, 森林与二叉树的转换
下一页
第 5单元
非线性数据结构
图
下一页
上一页
停止放映
第 5 页
一,图及其基本概念
? 图是一种较之线性表和树形结构更为复杂
的非线性数据结构 。 图中各数据元素之间
的关系可以是任意的, 描述的是, 多对多,
的关系 。
? 图 是对结点的 前趋和后继个数不加限制 的
数据结构 。
下一页
上一页
停止放映
第 6 页
图（ Graph）的定义
? 图 G = （ V,E ）
其中,V={ v1,v2,……,vn}是非空 有穷的
结点集合 ;E 是顶点偶对的集合 。
? 例, 图 G1 = （ V,E）
V={v1,v2,v3,v4}
E={（ v1,v2）, （ v1,v3）,
（ v2,v1）, （ v2,v3）,
（ v2,v4）, （ v3,v1）,
（ v3,v2）, （ v4,v2）
}
o o
oo
v1 v2
v3 v4
G1
下一页
上一页
停止放映
第 7 页
有向图、无向图
? 有向图（ Digraph）
图 G中 顶点的偶对若是有向的,形成的图称有向图。
如图 G2所示。
为示区别，其偶对用 <vx,vy>表示。
? 无向图（ Undigraph）
图 G中 顶点的偶对若是无向的,形成的图称为无向
图，其偶对用 （ vx,vy） 表示 (区别在括号 )，如图 G1
所示。
? G2=（ V,E）
V={ 1,2,3,4}
E={〈 1,2〉, 〈 1,3〉
,〈 3,4〉, 〈 4,1〉 }
1
3
2
4
G2
下一页
上一页
停止放映
第 8 页
边、弧
? 边 （ Edge）
顶点间的关系可描述为顶点的偶对, 也称为顶点的边 。
记为,（ Vx,Vy） 。 边是无序的, 可以看成是 （ Vx，
Vy）, 也可以看成是 （ Vy,Vx） 。
? 弧 （ Arc）
若顶点间的边是有方向性 （ 有序 ） 的, 则称该偶对为弧 。
记为,〈 Vx,Vy〉 。 弧是有序的, 〈 Vx,Vy〉 表示从
Vx到 Vy。
? 弧头 （ Head）
弧的终点 （ TerminaL Node） 称为弧头 （ 方向前方 ） 。
? 弧尾 （ Tail）
弧的起始点 （ Initial Node） 称为弧尾 （ 方向后方 ） 。
弧 〈 Vx,Vy〉 表示为, Vx Vy
弧尾 弧头
下一页
上一页
停止放映
第 9 页
顶点、邻接点
? 顶点 （ Vertex）, 图中的数据元素 （ 结点 ） 称为顶点 。
如图 G1,G2中的Ｖ 1,Ｖ 2,1,2。
? 邻接点 （ Adjacent）
– 无向图中, 若边 （ Ｖ x,Ｖ y） ? E，
则Ｖ x,Ｖ y互为 邻接点 。
– 有向图中, 若弧 〈 Ｖ x,Ｖ y〉 ? E，
则 Ｖ y是Ｖ x的邻接点, 反之, 不是 。 (弧头是弧尾的邻接点 )
Vx Vy
Ｖ x、Ｖ y互为邻接点
Vx Vy
Ｖ y是Ｖ x的邻接点
1
3
2
4
G2
o o
oo
v1 v2
v3 v4G1
下一页
上一页
停止放映
第 10 页
顶点的度（ Degree）
? 无向图 中, 顶点的 度 是以该顶点为一个端点的边
的条数 。 例如, G1中 V2的度为 3,V4的度为 1。
? 有向图 中, 以某顶点为弧头的弧的数目称为该顶
点的 入度 （ Indegree） 。 例如 G2中顶点 1的入度
为 1。 以某顶点为弧尾的弧的数目称为该顶点的
出度 （ Outdegree） 。 例如 G2中顶点 1的出度为 2。
该 顶点的度 =入度 +出度 。 例如, G2中顶点 1的度
=2+1=3。
o o
oo
v1 v2
v3 v4
G1
1
3
2
4
G2
下一页
上一页
停止放映
第 11 页
路径、长度
? 路径 （ Path）
在图中, 从顶点 Vx到顶点 Vy的顶点序列 （ Vx,V1，
V2,…,Vn,Vy)称为从 Vx到 Vy的路径 。 路径可能是
不唯一的 。 例如, G1中, V1到 V3的路径为：
（ V1V2V3） 或 （ V1V3） ；而 G2中, 1到 4的路径为
<134>。
? 长度 （ Length）
路径的长度是该路径 上边或弧的数目 。 例如, G1
中 V1到 V3的长度为 1或 2；而 G2中 1到 4的长度为 2。
1
3
2
4
G2
o o
oo
v1 v2
v3 v4
G1
相应的边必
须在图中
下一页
上一页
停止放映
第 12 页
连通图、强连通图、连通分 量
1 2
? 连通图（ Connected Graph）
在无向图中,若每一对顶点间都有路径，
称此图是连通图。如图 G3所示。
? 连通分量（ Connected Component）
无向图中的 极大连通子图称为连通
分量 。 （ 连通图有一个分量, 非连通图
有多个连通分量 ）
? 强连通图 （ Strongly Connected
Graph）
在有向图中, 若 每对顶点 Vx到 Vy
间都存在 Vx到 Vy,及从 Vy到 Vx的路径,
则称此图是强连通图 。 如图 G4所示 。
（ 有去有回 ）
3
4 5
G3
21
3
4 5
G4
下一页
上一页
停止放映
第 13 页
子图、生成树
? 子图
有两个图 G和 G1,若 V1?V,E1 ? E,即 V1中的顶点
G = （ V,E） 都属于 V中的顶点, E1中的关系都
G1 =（ V1,E1） 属于 E中的关系, 则称 G1是 G的子图 。
（图的部分顶点和部分边组成的图）
? 生成子图, 生成树
设 G是一个连通图, G中任一包含 G的所有顶点的子图
称为 生成子图 。 如果该子图是树, 则称为 G的 生成树 。
G的生成树不是唯一的 。 一棵有 n个顶点的生成树,
有且仅有 n-1条边 （ 弧 ） 。
（ 子图包含所有顶点, 但不一定包含所有边 ）
下一页
上一页
停止放映
第 14 页
网、权
? 权 （ Weight）
若图的边或弧带有与之相关的数, 称此数为该
边或弧的权 。 权通常用来表示从一个顶点到另
一个顶点的距离或费用 。
? 网 （ Network） (赋权图 )
带权的图 称为网 。 如 G5为带权的网 。
V1 V2
V3V4
G523
5
7
下一页
上一页
停止放映
第 15 页
图的应用实例
? [路径问题 ] 城市中有许多街道，每一个十字路口都可以
看作图中一个顶点，邻接两个十字路口之间的每一段街
道既可以看作一条，也可以看作两条有向边。如果街道
是双向的，就用两条有向边。如果街道是单向的，就用
一条有向边 。 (路线咨询 )
下一页
上一页
停止放映
第 16 页
图的应用实例
? [生成树 ] 设 G= (V,E)是一个无向图，当且
仅当 G中每一对顶点之间有一条路径时，可
认为 G是连通的（ c o n n e c t e d）
? 一个 n节点的连通图必须至少有 n- 1条边。
因此当通信网络的每条链路具有相同的建
造费用时，在任意一棵生成树上建设所有
的链路可以将网络建设费用减至最小，并
且能保证每两个城市之间存在一条通信路
径。如果链路具有不同的耗费，那么需要
在一棵最小耗费生成树上建立链路。
下一页
上一页
停止放映
第 17 页
图的应用实例
下一页
上一页
停止放映
第 18 页
二、图的存储结构
? 1、邻接矩阵表示法
? 根据图的定义可知，图的逻辑结构分为两部分,V（顶
点）和 E（边或弧）的集合。因此，
– 用一个一维数组存放图中所有顶点数据；
– 用一个二维数组存放顶点间关系（边或弧）的数据，
称这个二维数组为 邻接矩阵 。
– 邻接矩阵又分为 有向图邻接矩阵 和 无向图邻接矩阵 。
1 2 3 4
1 0 1 0 1
2 1 0 1 0
3 0 1 0 1
4 1 0 1 0
下一页
上一页
停止放映
第 19 页
有向图的邻接矩阵
? 定义
设图 G=（ V,E） 是有 n（ n ? 1） 个顶点的图, 则 G的邻
接矩阵是具有下述性质的 nxn的方阵, 元素为：
1 当 〈 Vi,Vj>? E 时 （ 存在弧 ）
A[ i,j] =
0 当 〈 Vi,Vj>? E 时 （ 不存在弧 ）
例如, G2的邻接矩阵为：
G.nodes=
1
2
3
4
A= G.Arc=
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0 4x4
1
3
2
4
G2
注意：不一定对称，对角线全为 0
下一页
上一页
停止放映
第 20 页
无向的图邻接矩阵
? 定义
设图 G=（ V,E）是有 n（ n ? 1）个顶点的图，则 G的邻
接矩阵是具有下述性质的对称阵，元素为：
1 当 (Vi,Vj） ? E 时 (有边 )
A[ i,j] =A[j,i] =
0 当 (Vi,Vj） ? E 时（无边）
无向图的邻接矩阵是一个对称矩阵
例如,G1的邻接矩阵为：
G.nodes =
1
2
3
4
A=G.edge =
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0 4x4
o o
oo
v1 v2
v3 v4
G1
注意：一定对称，对角线全为 0
下一页
上一页
停止放映
第 21 页
求图中顶点的度
? 借助邻接矩阵,可以很容易地求出图中顶点
的度 。
– 无向图 邻接矩阵的第 i行 （ 或第 i列 ）
的元素之和是顶点 Vi的度 。 例, G1中 V2
的度是 3。 （ 上页图 ）
– 有向图 邻接矩阵第 i行的元素之和为顶
点 Vi的出度；第 j列的元素之和为顶点 Vj
的入度 。 例, G2中, V2的出度为 0（ 第 2
行的元素之和为 0）, V1的入度为 1（ 第 1
列的元素之和为 1） 。
o o
oo
v1 v2
v3 v4
G1
A= G.Arc=
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
1
3
2
4
G2
下一页
上一页
停止放映
第 22 页
网的邻接矩阵
? 定义：
Wij 若 （ Vi,Vj） 或 〈 Vi,Vj〉 ? E(有边 )
A[i,j] =
? 若 （ Vi,Vj） 或 〈 Vi,Vj〉 ? E（ 无边 ）
G.nodes=
V1
V2
V3
V4
A=G.Arc=
? 5 ? 3
? ? 2 ?
? ? ? ?
? ? 7 ? 4x4
G5的邻接矩阵。
V1 V2
V3V4
G523
5
7
？为什么不用 0表示无边或弧？
对称？
下一页
上一页
停止放映
第 23 页
A
1 2
B 3 C
2、邻接表表示法
? 邻接表是图的一种链式存储结构 。 对图的 每个顶点建立
一个单链表 （ n个顶点建立 n个单链表 ）, 第 i个单链表
中的结点包含顶点 Vi的所有邻接顶点 。
? 在邻接表中, 每个顶点由三个域组成：
? 每个单链表附设一个头结点, 结构为：
adjvex data nextarc
顶点 Vi的邻接点
（名称 or编号） 与边或弧有关的权值
指向 Vi的下一个
邻接点的指针
Vexdata firstarc
指向 Vi单链表的第一个结点存放 Vi信息
A
B 1
C 2 null
下一页
上一页
停止放映
第 24 页
邻接表存储结构描述
C语言描述
#define VTXNUM n
struct arcnode { //定义弧结点
int adjvex；
float data；
struct arcnode *nextarc； //下一个邻接点
}；
typedef struct arcnode ARCNODE ；
struct headnode { //定义头结点
int data ；
ARCNODE * firstarc ； //第 1个邻接点
} adjlist[VTXNUM]； //头结点数组
下一页
上一页
停止放映
第 25 页
无向图 G1的邻接表
V1
V2
V3
V4
^V3V2
V1 V4 ^V3
^V1 V2
^V2
顶点 Vi的度恰好就是
第 i个单链表中的结点数。o o
oo
v1 v2
v3 v4
G1 注：边无权，节点只需两个
域
下一页
上一页
停止放映
第 26 页
有向图 G2的邻接表
1
2
3
4
^23
^4
^1
^
?描述,在有向图中，第 i个单链表中结点的个
数是顶点 Vi的出度；
?特点,求出度方便，求入度，必须遍历整个邻
接表。
1
3
2
4
G2
头结点 链 表
下一页
上一页
停止放映
第 27 页
逆邻接表
? 描述,为求顶点 Vi的入度, 对每个顶点 Vi,建
立一个链接以 Vi为弧头的邻接点链表, 称该表
为逆邻接表 。 例如 G2的逆邻接表为：
1
2
3
4
4
1
1
3
^
^
^
^
特点,方便求入度。
显然逆邻接表的单链表 i中结点的个数
就是顶点 Vi的入度。
1
3
2
4
G2
下一页
上一页
停止放映
第 28 页
建立邻接表的算法
? 操作步骤：
– step1 初始化邻接表的 n个头结点,
– Step2 读入一条弧或边的偶对 〈 i,j〉 或
（ i,j） 。
– step3 申请一个结点 S的空间, 将 S插入到
第 i个单链表中；
– step4 读下一条弧或边的偶对, 若存在此
弧或边, 则继续执行 step2；否则, 结束 。
下一页
上一页
停止放映
第 29 页
建立邻接表算法的程序
createadjlist(struct headnode G[],int n)
{ int i,j,k; float w; ARCNODE *s;
for (k=1; k<= n ; k++ )
{ scanf(,%d”,&G[k].data); //初始化 n个头结点
G[k].firstarc = NULL ;
}
scanf(“%d,%d,%f”,&i,&j,&w ); //输入边和权
while (( i >=0 && i <n)&&(j>=0 && j<n)) //合法性校验
{ s= (ARCNODDE *)malloc(sizeof(ARCNODE)); //申请结点空间
s->adjvex = j; //总是将结点插在第 I个头结点和其第一个邻结点之间
s->info = w;
s->nextarc = G[i].firstarc;
G[i].firstarc = s;
scanf(“%d,%d,%f”,&i,&j,&w);
}
} i null k wk null
j wj null
s1
s2
下一页
上一页
停止放映
第 30 页
三、图的遍历
? 图的遍历 （ Traversing Graph）
从图中指定顶点出发访问图中每一个顶点, 且使每个
顶点只被访问一次, 该过程为图的遍历 。
? 图的遍历要比树结构复杂的多 。 出发点不同, 任一
顶点的邻接点就不相同, 路径也就不同 。
? 因为图中元素是, 多对多, 的关系, 为避免发生重
复, 设立一个辅助数组 visited[],每访问一个顶点,
便将其状态 visited[i]置为, 真, 。
? 常用的图的遍历方法有两种：
– 深度优先遍历法
– 广度优先遍历法 图的遍历序列
不是唯一的
下一页
上一页
停止放映
第 31 页
深度优先遍历法
? 深度优先遍历法类似于树的先根遍历法 。
? 算法思想：
– step1 从图中某个顶点 V0出发, 并访问此顶点；
– step2 从 V0出发, 访问与 V0邻接的顶点 V1后, 再从
V1出发, 访问与 V1邻接 且未被访问过的 顶点 V2。 重
复上述过程, 直到不存在未访问过的邻接点为止 。
– step3 如果是连通图, 从任一顶点 V0出发, 就可以
遍历所有相邻接的顶点；如果是非连通图, 则再选
择一个未被访问过的顶点作为出发点, 重复 step1、
step2,直到全部被访问过的邻接点都被访问为止 。
下一页
上一页
停止放映
第 32 页
深度优先遍历法举例
遍历过程 访问顶点 所过边
?起始顶点 V1 V1
?V1的第 1个邻接点 V3 V3 （ V1,V3）
?V3的第 1个邻接点 V1已访问，取下
一个邻接点 V5 V5 （ V3,V5）
?V5的第 1个邻接点 V3已访问，取下
一个邻接点 V2 V2 （ V5,V2）
?V2的两个邻接点均被访问，
回退 到 V5,V5的邻接点均被访问，
回退到 V3,V3的邻接点均被访问,
回退到 V1,V1的另一个邻接点 V4
未被访问 V4 （ V1,V4）
?V4的第一个邻接点 V1已被访问，
另一个邻接点 V6未被访问 V6 （ V4,V6）
?V6的邻接点被访问，回退到 V4
?V4的邻接点均被访问
?回退到 V1，返回到出发点，遍历结束。
V1
V3
V5
V4
V6
G6
V2
示例
下一页
上一页
停止放映
第 33 页
遍历产生的结果
? 深度优先遍历 G6所走过的序列：
V1? V3 ? V5 ? V2 ? V4 ? V6
? 所走过的边：
（ V1,V3）, （ V3,V5）, （ V5,V2）, （ V1,V4）, （ V4，
V6）
? 由此生成一棵树, 称为 遍历生成树
V1
V3
V5
V2
V4
V6 求遍历序列时
不需写出生成树
下一页
上一页
停止放映
第 34 页
深度优先遍历算法程序 (非递归 )
Traver_dfs(struct headnode G[],int v)
{ int i,stack[N],visited[N],top=-1 ; ARCNODE *p;
for (i=0;i<N;i++) visited[I]=0; //所有结点未被访问
printf(“%d ->”,G[v].data); //访问初始结点
visited[v]=1; top ++; stack[top]=v; p=G[v].firstarc;
while((top!=-1)||(p!=NULL)) //栈非空, p非空循环
{ while(p!=NULL)
{ if (visited[p->adjvex]) p=p->nextarc;//所指节点已访问
else { printf(“%d ->”,G[p->adjvex].data);
visited[p->adjvex]=1; top++; stack[top]=p->adjvex;
p=G[p->adjvex].firstarc; } //访问未被访问的节点
if( top !=-1) //回退
{ v=stack[top]; top- -; p=G[v].firstarc;
p=p->nextarc; }
}
}
}？ if(top!=1)所处位置对不对
下一页
上一页
停止放映
第 35 页
广度优先遍历算法
? 广度优先遍历法类似于树的按层次遍历的过程。
即先访问第 1个顶点所有邻接点后，再访问下一
个顶点所有未被访问的邻接点。
? 算法思想：
– step1 从图中某个顶点 V0出发，并访问此顶点；
– step2 从 V0出发，访问 V0的各个未曾访问的邻
接点 W1,W2,…,Wk;然后,依此从 W1,W2,…,Wk
出发访问各自未被访问的邻接点。
– step3 重复 step2，直到全部顶点都被访问为
止。
下一页
上一页
停止放映
第 36 页
广度优先遍历法举例
遍历过程 访问顶点 所过边
?起始顶点 V1 V1
?访问 V1的未被访问过
的所有邻接点 V3,V2,V4 （ V1,V3）
(V1,V2)
(V1,V4)
?访问 V3的未被访问过
的所有的邻接点 V5 （ V3,V5）
?访问 V2的未被访问过
的所有的邻接点 无
?访问 V4的未被访问过
的所有的邻接点 V6 (V4,V6)
?所有顶点已被访问,结束。
V1
V3
V5
V4
V6
G6
V2
示例
？ 思考题：广度优先遍历算法的辅助数据结构？
下一页
上一页
停止放映
第 37 页
遍历产生的结果
? 广度优先遍历 G6所走过的序列：
V1? V3 ? V2 ? V4 ? V5 ? V6
? 所走过的边：
（ V1,V3）, （ V1,V2）, （ V1,V4）, （ V3,V5）, （ V4,V6）
? 遍历生成树
V1
V3
V5
V2 V4
V6
下一页
上一页
停止放映
第 38 页
四、图的常用基本操作
? LOC_VERTEX（ G,Vi） 确定顶点 Vi在 G中的位置 。
? GET_VERTEX（ G,i） 求图 G中第 i个顶点 。
? FIRST_VERTEX（ G,i） 求图 G中 Vi的第 1个邻接点 。
? NEXT_ADJ(G,v,w) 已知 w为 G中顶点 v的第 1个邻接点,
求顶点 w的下一个邻接点 。
? INS_VERTEX(G,u) 在图 G中插入一个顶点 u,为图 G的
第 n+1个顶点 。
? INS_ARC(G,v,w) 在图 G中插入一条从顶点 v到顶点 w
的弧 。
? DEL_VERTEX(G,Vi) 删除图 G中顶点 Vi,以及与 Vi相
关联的边或弧 。
? DEL_ARC(G,v,w) 删除图 G中从顶点 v到顶点 w的弧 。
下一页
上一页
停止放映
第 39 页
五、图的应用
? 最小生成树
? 拓扑排序
? 关键路径
? 最短路径
下一页
上一页
停止放映
第 40 页
最小生成树
? 即连通图的最小代价生成树 。 生成树上各边
（ 弧 ） 的代价之和最小 。
? 例如, 若要在 n个城市间建立通信联络网, 则只
需 n-1条线路 。 但在 n个城市间, 最多可能架设 n
（ n-1） /2条线路, 选择哪 n-1条线路, 使费用
最少 。
– 普里姆 （ Prim） 算法
– 克鲁斯卡尔 （ Kruskal） 算法
下一页
上一页
停止放映
第 41 页
普里姆（ Prim） 算法
? 设 N=（ V,E） 是连通图,
? U是最小生成树的 顶点集
? TE是最小生成树中 边的集合 。
– 从 U={u0} （ u0 ? V）, TE= 空开始；
– 重复执行,在所有 u?U,v ?V-U的边 （ u,v）
?E中找一条代价最小的边 （ u0,v0） 并入 TE,同
时 v0并入 U,直到 U=V为止；
– 此时 TE中必有 n-1条边, 则 T=（ V,TE） 为 N的最
小生成树 。
下一页
上一页
停止放映
第 42 页
普里姆（ Prim） 算法举例
1
2
3 4
5
6
8 7
2
1
4
35
7 6
8
11
10
9
12
U={1},V-U={2,3,4,5,6,7,8}
1
2
2
1
2
4
2
1
4 7
3
（ 1）
（ 2） （ 3）
(1) U={1,2},V-U={3,4,5,6,7,8}
(2) U={1,2,4},V-U={3,5,6,7,8}
(3) U={1,2,4,7},V-U={3,5,6,8}
1,2,4,7、
5,6,3,8
下一页
上一页
停止放映
第 43 页
普里姆（ Prim） 算法举例 (续 )
4 7
5
3
5
（ 4）
7
6
（ 5）
6
（ 6）
4 7
6
3 8
（ 7）
8 3
6
5
4 7
2
2 1
3
6
589
(4) U={1,2,4,7,5},V-U={3,6,8}
(5) U={1,2,4,7,5,6},V-U={3,8}
(6) U={1,2,4,7,5,6,3},V-U={8}
(7) U={1,2,4,7,5,6,3,8),V-U={ }
4 3
6
3
1
下一页
上一页
停止放映
第 44 页
克鲁斯卡尔（ Kruskal）算法
? 操作步骤,
– 假设 N=（ V,E） 是连通图, T为生成树
– 取图中每个顶点自成一个连通分量 (先看成 n个顶点, 无边 )
– 在 { E }中选择代价最小的边, 若该边所依附的顶
点落在 T中不同的连通分量上 （ 能把不连的点或树连起来 ）,
则将此边加入生成树 T中；否则, 舍去此边, 再选
择下一条代价最小的边 。
– 重复上述步, 直到 T中所有顶点都在同一连通分量
上为止 。
下一页
上一页
停止放映
第 45 页
克鲁斯卡尔（ Kruskal）算法举例
1
2 3 4
5 6
1 5
24
6
63
55
6
2
5
1
3
4
6
1
2
3
(4)
1
3
1 4
6
2
(3)
1
2 3 4
5 6
(1)
1
3
(2)
1
1-3,4-6
2-5,3-6
2-3
下一页
上一页
停止放映
第 46 页
克鲁斯卡尔（ Kruskal）算法举例 (续）
1
2 3 4
5 6
(5)
1
23 4
1
2 3 4
5 6
1 5
24
6
63
55
6
1
32
5 6
4
1
243
5
（ 6）
下一页
上一页
停止放映
第 47 页
拓扑排序
? 研究一个有机整体中不同个体间的次序问题 。
例如：课程间优先关系有向图问题 。
? 软件专业的课程优先关系：
课程编号 课程名称 先决条件
C1 程序设计基础 无
C2 离散数学 C1
C3 汇编语言 C1,C2
……
C9 高等数学 无
？ 选择一种选课顺序
下一页
上一页
停止放映
第 48 页
拓扑排序举例
? 方法步骤
– 在有向图中选一个没有前驱的顶点并输出 ;
– 从图中删除该顶点和所有以它为尾的弧 ;
– 重复前 2步,直到全部顶点均输出为止 。
– 输出序列即为拓扑排序序列 。
? 拓扑排序序列不唯一 。
?？ 二叉树的遍历序列唯一吗？
?？ 图的遍历序列唯一吗？
下一页
上一页
停止放映
第 49 页
拓扑排序举例
C1
C9
C4
C2
C3
C5
C7
C12
C10
C11
C6
C8
?C1 C2 C3 C4 C5 C7 C9 C10 C11 C6 C12 C8
?C9 C10 C11 C6 C1 C12 C4 C2 C3 C5 C7 C8
下一页
上一页
停止放映
第 50 页
最短路径
? 研究的是类似于交通调度一类的带权有向图问题 。
求路径最短或费用最省 。
? 从源到其余各顶点的最短路径
? 原理,引进一个辅助向量 dist,它的每个分量
disk[i]表示当前所找到的从始点 v到每个终点 vi
的最短路径的长度 。 它的初始状态为：若从 v到
vi有弧, 则 disk[i]为弧上的权值；否则置
disk[i]为无穷,
? disk[j]=Min{disk[i]|vi∈V}
? 就是从 v出发的长度最短的一条最短路 （ v,vj）,
? 即 v到 vj的最短路 。
下一页
上一页
停止放映
第 51 页
最短路径
? 设 下一条最短路 的终点为 vk,则 这条路径
或者是 (v,vk)，或者是（ v,vj,vk），它的长
度或者是从 v到 vk的弧的权值，或者是
diak[j]和从 vj到 vk的弧上的权值之和,
? 算法,
? （ 1）假设用带权的邻接矩阵 cost来表示带
权有向图,cost[i,j]表示弧（ i,j）上的权值。
若（ vi,vj）不存在，则置 cost[i,j]为 ∞。
? S为已找到的从 v出发的最短路径的终点的
集合，它的初始状态为空集
? Disk[i]=cost[v,i],vi∈ V
下一页
上一页
停止放映
第 52 页
? （ 2）选择 vj，使得
? Disk[j]=min{disk[i]| vi∈ V-S}
? Vj就是当前求得的一条从 v出发的最短路径
的终点。
? S=S∪ {j}
? （ 3）修改从 v出发到集合 V-S上的任一顶点
vk可达的最短路径长度。如果
? disk[j]+cost[j,k]<disk[k]
? 则 disk[k]= disk[j]+cost[j,k]
? （ 4）重复（ 2）、（ 3）共 n-1次。 (p87例 )
下一页
上一页
停止放映
第 53 页
作业、思考题
第 2章
1、思考题,3,4,18
2、第 2章作业, 8,13,20
3,作业命名方式为,学号 _ch02_2
第 3章
思考题, p112 第 2,3,5~7,11题
作 业, p113 第 13题
命 名,学号 _ch03_1
下一页
上一页
停止放映
第 54 页
结束语
? 欢迎参加网上讨论，网站的地址：
http,//ctec.xjtu.edu.cn
? 下载课件的 FTP地址：
ftp,//ctec.xjtu.edu.cn
? 数字化课件的路径,
jec254\user2\tools\lzq\软件基础
? 答疑安排：
星期五晚 7,00～ 9,00
谢谢，再见！
下一页
上一页
停止放映
第 55 页
六、二叉排序树的生成 （树的应用）
对给定数列 {a1,a2,…,an},根据二叉排序树特性,逐个将
结点插入到二叉排序中 。
具体操作步骤：
step1 a1是根结点；对结点 ai：
step2 若 ai<aj,且 aj的左子为空,则将 ai插入到 aj的左子 ;
若 aj的左子非空,则继续寻找合适的插入位置 。
若 ai?aj,且 aj的右子为空, 则将 ai插入到 aj的右子；
否则继续沿右子树寻找合适的插入位置；
插入 ai 插入到 aj的左子 ai〈 aj
插入到 aj的右子 ai ? aj
step3 重复 step2，直到所有结点插入完为止。
(Flash)相关算法在后面，自己看 <goto 平衡二叉排序树
>
下一页
上一页
停止放映
第 56 页
二叉排序树算法
二叉排序树结点结构：
struct tree {
char info；
struct tree *left, * right ；
}
算法描述,
? 输入结点非空循环,若是第 1个结点,令指针
ROOT指向该结点。
? 打印输出该二叉排序树；
? 输入一个值，在该树中查找，若找到输出该
结点值；否则，显示查找失败。
下一页
上一页
停止放映
第 57 页
二叉排序树生成算法
建立二叉树
Create_btree()
查询结点
Search_btree()
打印二叉树
Print_btree()
主程序
Btree.C
下一页
上一页
停止放映
第 58 页
主程序框图
开始
初始化
输入结点数据
！ ROOT
root=create_btee（） create_btree()
结束?
N
Y
打印该树
查找指定结点
Print_btree()
Search_btree()
下一页
上一页
停止放映
第 59 页
生成二叉排序树程序框图
Create_btree() 开始
r = 0？
Y
申请结点空间
r = 0？显示“溢出”
结束
根结点的处理 N
Y
N
r->left = 0;
r->right = 0;
r->info = info ;
非根结点
info<r->info?Y
t=r->left t=r->right
N
调用本函数
root?
返回
Y N
r->left=0
r->right=0
root->left=r
或
root->right=r
下一页
上一页
停止放映
第 60 页
查询二叉排序树算法框图
开始 Search_btree()
!root
Y
显示“空树”
返回
N
root->info!=key循环
key<root->info?
root=root->left root=root->right
root=0?
NY
查找成功,显示 返回
显示“失败”
root!=0?
循环结束?
N
Y
下一页
上一页
停止放映
第 61 页
打印算法框图
开始 Print_btree()
r=0?
Y
N
调用自身打印左子
打印当前结点值
调用自身打印右子
返回
下一页
上一页
停止放映
第 62 页
主程序 Btree.C
#include,stdio.h”
struct tree {
char info;
struct tree *left,*right;
}
main ( )
{ char *s,*c,key=??;
struct tree *create_btree(),*search_btree(),*root=0;
do {
printf(“Enter a letter:”);
gets(s);
if (!root)
root=create_btree(root,root,*s);
else
create_btrr(root,root,*s);
} while (*s) ;
下一页
上一页
停止放映
第 63 页
主程序 Btree.C(续）
print_btree(root,0);
key=?1?;
while ( key)
{
printf(“Enter a key to find:”);
scanf(“%s”,&c);
key=search_btree(root,c);
printf(“press to continue\n”);
}
} /* Btree.C 结束 */
下一页
上一页
停止放映
第 64 页
生成二叉排序树程序
struct tree create_btree(root,r,info)
struct tree *root,*r;
char info;
{ if (r = =0 )
{ r=malloc(sizeof(struct tree));
if ( r = = 0)
{ printf(“Out of memory\n”); exit(0); }
r->left= 0; r->right=0; r->info=info;
if (root)
{ if(info<root->info) root -> left=r;
else root->right=r;
}
else
{ r->right=0; r->left = 0; }
return r;
} /* if = = 0 接下页 */
下一页
上一页
停止放映
第 65 页
生成二叉排序树程序 （续）
if (info < r->info)
create_btree(r,r->left,info);
if(info>=r->info)
create_btree(r,r->right,info);
} /* create_btree(root,r,info) */
下一页
上一页
停止放映
第 66 页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Emptu btree\n”); return root; }
while(root->info!=key)
{ if(key<root->info)
root=root->left;
else
root=root->right;
if(root==0)
{ printf(“Search Failure\n”);
break ;
}
} /* while(root->info!=key) */
查询二叉排序树程序
下一页
上一页
停止放映
第 67 页
if (root !=0)
printf(“Successful search\n key=%c\n”,root->info);
return root ;
} /* *search_btree(root,key) */
查询二叉排序树程序（续）
下一页
上一页
停止放映
第 68 页
打印二叉排序树程序
print_btree(r,l)
struct tree *r;
int l;
{ int i;
if (r = = 0) return ;
print_tree(r->left,l+1);
for(i=0;i<l;i++)
printf(“,);
printf(“%c\n”,r->info);
print_btree(r->right,l+1);
}
下一页
上一页
停止放映
第 69 页
程序输入
输入,输出：
h ? b
d ? d
p ? e
r ? h
b ? p
e ? r
?
下一页
上一页
停止放映
第 70 页
举例
对数列 {10,18,3,4,9,13,25},生成二叉排序树 。
10
（ 1）
10
18
（ 2）
10
3 18
（ 3）
10
3 18
4 （ 4）
10
3
4
18
9（ 5）
（ 7）
10
3
9
4
18
13 25
10
3
4
9
18
13
（ 6）
示例
下一页
上一页
停止放映
第 71 页
平衡二叉排序树
在二叉排序树的动态生成过
程中, 由于数据本身的特性, 将
影响二叉排序树的性质, 例如 {3，
5,7,9,20}这样的数列, 生成
的二叉排序树就是一棵单枝树 。
因此, 在动态生成二叉排序树的
过程中, 要进行平衡化处理 。
平衡化处理就是在
不影响 二 叉 排序树特性的前题
下, 通过, 旋转, 处理, 使该结
点
的平衡因子不大于 2。
旋转分,LL,RR,LR和 RL
四种 。
3
5
7
9
20
下一页
上一页
停止放映
第 72 页
LL平衡化处理
由于在 A的左子树的左
子树上插入结点, 使 A
点失去平衡, 需进行
一次 LL旋转 （ 顺时针
旋转 ） 操作 。
程序实现为：
b = a?.lc
a?.lc = b?.rc
b?.rc = a
a?.bf = 0
b?.bf = 0
b为子树的新根
A
B
C
LL B
C A
示例
示意为：
下一页
上一页
停止放映
第 73 页
RR平衡化处理
由于在 A的右子树的右子
树上插入结点, 使 A点
失去平衡, 需进行一次
RR旋转 （ 逆时针旋转 ）
操作 。
程序实现为：
b = a?.rc
a?.rc = b?.lc
b?.lc = a
a?.bf = 0
b?.bf = 0
b为子树新根
A
B
C
RR B
A C
示例
示意为：
下一页
上一页
停止放映
第 74 页
LR平衡化处理
程序实现为：
b = a?.lc,c = b?.rc,a?.lc = c?.rc
b?.rc = c?.lc,c?.lc = b,c?.rc = a
A
B
C
C
B A
A
C
B
示例
由于在 A的左子树的右子树上插入结点, 使 A点失去平
衡, 需进行一次 LR旋转 （ 两次旋转 ;先逆时针,再顺
时针旋转 ） 操作 。
示意为：
下一页
上一页
停止放映
第 75 页
RL平衡化处理
由于在 A的右子树的左子树上插入结点, 使 A点失去平衡,
需进行一次 RL旋转 （ 两次旋转 ;先顺时针,再逆时针旋转 ）
操作 。
A
B
C
C
A B
A
C
B
程序实现为：
b = a?.rc,c = b?.lc,a?.rc = c?.lc
b?.lc = c?.rc,c?.lc = a,c?.rc = b
示意为：
示例
下一页
上一页
停止放映
第 76 页
平衡化处理举例
有数据序列 {13,24,37,90,53}
? 插入 13,树是平衡的 ;
? 插入 24,树仍为平衡 ;
? 插入 37,树不再平衡,
执行 RR旋转 ;
? 插入 90,树仍平衡 ;
? 插入 53,失去平衡,
执行 RL旋转,
13
(1)
13
24
(2)
13
24
37 3713
24
(3)
24
13 37
90
(4)
24
13 37
90
53
24
13 37
53
90
24
13 53
37 90
(5)
示例
下一页
上一页
停止放映
第 77 页
Huffman(哈夫曼）树及应用
? Huffman树的定义
? 构造 Huffman树
? Huffman编码
? Huffman编码的译码
下一页
上一页
停止放映
第 78 页
Huffman树的定义
? Huffman树也称为最优树，是一类带权路径最短
的二叉树。
? 树的带权路径长度定义为：
WPL = ∑ wklk
k = 1
n
其中：
n 是树 中叶结点的个数
wi 是第 i个 结点的权值
li 是第 i个结点的路径长度
下一页
上一页
停止放映
第 79 页
Huffman树举例
? 以下有三棵树：
（ a） （ b） （ c）
a
b
c d
a b c d
a
c
b
d7
7
7
5
5
52
2
2
4 4
4WPLa =7x2+5x2+2x2+4x2
= 36 WPL
b =7x3+5x3+2x1+4x2
= 46
WPLc =
7x1+5x2+2x3+4x3
= 35 √
? 事实证明按哈夫曼树构造二叉树，可得到很好的特
性，应用于实际问题，可提高处理效率。
结点个数及权相同，
不同组合得到不同的带权路径长度
下一页
上一页
停止放映
第 80 页
应用举例
? 由统计规律可知，考试成绩的分布符合正态分布：
-1 10
分数 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100
比例数 0.05 0.15 0.40 0.3 0.10
? 根据正态分布规律，在 60 ～ 90之间的分数占 85%，
而不及格和优秀是少数。
下一页
上一页
停止放映
第 81 页
将百分制转换成五分制
? 判定树比较,a<60?
a<70?
a<80?
a<90?
不及格
及格
中等
良好 优秀
Y
Y
Y
Y
N N
N
N
a<80?
a<70? a<90?
a<60?
不及格
优秀良好中等及格不及格
Y
Y
Y N
N
N NY
(A)
(B)
? 若输入 1万个数据，按 A的判定过程进行操作，约需比较 3.2
万次，而按 B比较,则仅需 2.2万次。
下一页
上一页
停止放映
第 82 页
构造 Huffman树
? 构造 Huffman树算法步骤：
– 1）将 n个带权值 wi（ i≤n）的结点构成 n棵二叉树
的集合 T={T1,T2,……, Tn}，每棵二叉树只有一
个根结点。
– 2）在 T中选取两个权值最小的结点作为左右子树，
构成一个新的二叉树，其根结点的权值取左右子树
权值之和；
– 3）在 T中删除这两棵树，将新构成的树加入到 T中；
– 4）重复 2）,3）步的操作，直到 T中只含一棵树
为止，该树就是 Huffman树。
下一页
上一页
停止放映
第 83 页
构造 Huffman树举例
? 以权值分别为 7,5,2,4的结点 a,b,c,d构造 Huffman树。
T= { a b c d }
c d
T
32 4
6
b T3
T
2 65
11
b
T
2 65
11
c d2 4
18
a T27
11
T
1
6
18
a7
T
1
b T3
T
25
11
18
a7
T
1
b5
11
c d2
6
4（ d） T={ T1 }
（ c） T= { a T2 }
（ b） T= { a b T3 }
（ a） T= { a b c d }
代入 T2
代
入T
3
示例
下一页
上一页
停止放映
第 84 页
Huffman树的应用,Huffman编码
? 编码：用二进制数的不同组合来表示字符的方法。
? 前缀编码：一种非等长度的编码 (任一个字符的编码
都不是另一个字符编码的前缀 )。
a
0
b
0
1
c d
0
1
1
编码,A（ 0）
B（ 10）
C（ 110）
D（ 111）
方法约定：
1）左分支为‘ 0’
2）右分支为‘ 1’
3）由叶到根路径上字符组
成的二进制串就是该叶结点
的编码。
? Huffman编码：一种非等长度的编码。以给定权
值的结点构造 Huffman树，按二进制前缀编码的
方式构成的编码为 Huffman编码。
下一页
上一页
停止放映
第 85 页
Huffman编码举例
? 在某系统的通信联络中可能出现 8种字符，其频率
分别为 0.05,0.29,0.07,0.08,0.14,0.23、
0.03,0.11，设权值分别为 {5,29,7,8,14，
23,3,11},n=8，其 Huffman树为：
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 86 页
Huffman编码存储结构
? 由于 Huffman树中 没有度为 1的结点,则 n个叶结点
的 Huffman树共有 2n-1个结点。例如,4个结点的
Huffman树，共有 7个结点。因此可以用长度为 2n-1
的一维数组存放。
? 求 Huffman编码,从叶到根的编码。因此要知道每
个结点的父结点。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Huffman编码为：
A 5 0110
B 29 01
C 7 0111
D 8 1111
E 14 011
F 23 00
G 3 1110
H 11 010
下一页
上一页
停止放映
第 87 页
Huffman编码的译码
? 从 Huffman编码树上不难看出，代码全部在叶结
点上，根据 Huffman编码，就能求出相应的字符。
该过程称为“译码”。
? 译码是根据从根到叶的 Huffman编码求相应的字
符。因此要知道每个结点的左右子结点。
? 例如，根据,1111”，就能求出对应的字符是,8”。
0
0
0
0
0
0
0
1
1
1
11
1
1
5 3 7 8
14
29
11
23
42 58
100
Typedef strudt{
Unsigned int weight;
Unsigned int pa,lc,rc;
}Htnode *HT;
