第二章 生成树

第二章 树

教学安排的说明

章节题目：§2.1树的特性 ；§2.2割边与割点，§2.3生成树

学时分配：共2课时

本章教学目的与要求：会正确表述关于树的一些基本概念（如树、生成树、割边与

割点），会用避圈法和破圈法找生成树，会用树的方法描述一些简单的

实际问题．

课 堂 教 学 方 案

课程名称：§2.1树的特性；§2.2割边与割点；§2.3 生成树

授课时数：2学时

授课类型：理论课

教学方法与手段：讲授法

教学目的与要求：会正确表述关于树的一些基本概念（如树、生成树、割边与割点），

会用避圈法和破圈法找生成树，会用树的方法描述一些简单的实际问题．

教学重点、难点：

（1） 理解树的概念以及树的等价命题；

（2） 掌握割边与割点的概念；

（3） 理解生成树的定义；

（4） 掌握找生成树的两种方法——避圈法和破圈法。

教学内容：

树是图论中的一个重要概念。树是一种极为简单而又非常重要的特殊图，它在

计算机科学以及其它许多领域都有广泛的应用。在1847年克希霍夫就用树的理论

来研究电网络，1857年凯莱在计算有机化学中

C

2

H

2n2

的同分异构物数目时也用到

了树的理论。各类网络的主干网通常都是树的结构。本节介绍树的基本知识，其中

谈到的图都假定是简单图。

2.1 树的特性

定义2.1.1 连通无圈的无向图称为无向树，简称为树（Undirected tree）。记作

T

，树中的悬挂点（或称

T

中度数为1的顶点）又称为树叶（leave）（或叶顶点），

其它顶点称为树枝（Branch Point或内点(Inner Point)）。诸连通分支均为树的

图称为森林（forest），树是森林。

例1 图1中（a），（b）为树，（c）为森林。

图1

由于树无环也无重边（否则它有圈）,因此树必定是简单图。树还有等价命题：

设

T

是一个无向

(n,m)

图，则以下关于

T

的命题是等价的。

(1)

T

是树；

（2）

T

无圈且

mn1

；

(3)

T

连通且

mn1

；

（4）

T

无圈，但增加任一新边，得到且仅得到一个圈。

（5）

T

连通，但删去任一边便不连通(

n2

)。

（6）

T

的每一对顶点间有唯一的一条通路(

n2

)。

证明 (1)



（2）

由树的定义可知

T

无圈。下证

mn1

。对

n

进行归纳证明。

当

n1

时，

m0

，显然

mn1

。

假设

nk

时结论成立，现证明

nk1

时结论也成立。

由于树是连通而无圈的，所以至少有一个度数为1的顶点

v

，在

T

中删去

v

及

其关联边，便得到

k

个顶点的连通无圈图。由归纳假设它有

k1

条边。再将顶点

v

及其关联边加回得到原图

T

，所以

T

中含有

k1

个顶点和

k

条边，故结论

mn1

成立。所以树是无圈且

mn1

的图。

(2)



（3）

T

T

用反证法。若

T

不连通，设

T

有

k

个连通分支(

k2

)

1

，

2

，，

T

k

，其顶

点数分别是

k

n

1

,n

2

,

k

,n

k

，边数分别为

m

1

,m

2

,,m

k

，于是



n

i1

k

i

n,



m

i

m

i1

k

m



m

i





(n

i

1)nkn1

i1i1

得出矛盾。所以

T

是连通且

mn1

的图。

(3)



（4）

首先证明

T

无圈。对

n

作归纳证明。

当

n1

时，

mn10

，显然无圈。

假设顶点数为

n1

时无圈，今考察顶点数是

n

时的情况。此时至少有一个顶点

v

其度数

deg(v)1

。我们删去

v

及其关联边得到新图

T



，根据归纳假设

T



无圈，

再加回

v

及其关联边又得到图

T

，则

T

也无圈。

其次，若在连通图

T

中增加一条新边

(v

i

,v

j

)

v

v

，则由于

T

中由

i

到

j

存在一条通

(v,v)

v

v

路，故必有一个圈通过

i

，

j

。若这样的圈有两个，则去掉边

ij

，

T

中仍存在

v

(v,v)

v

通过

i

，

j

的圈，与

T

无圈矛盾。故加上边

ij

得到一个且仅一个圈。

(4)



（5）

vv

(v,v)

vv

若

T

不连通，则存在两个顶点

i

和

j

，在

i

和

j

之间没有路，若加边

ij

不

会产生圈，但这与假设矛盾，故

T

是连通的。又由于

T

无圈，所以删去任一边，图

便不连通。

(5)



（6）

由连通性知，任意两点间有一条路径，于是有一条通路。若此通路不唯一，则

T

中含有圈，删去此圈上任一边，图仍连通，这与假设不符，所以通路是唯一的。

(6)



（1）

显然

T

连通。下证

T

无圈。用反证法。若

T

有圈，则圈上任意两点间有两条通路，

此与通路的唯一性矛盾。故

T

是连通无圈图，即

T

是树。

从以上特征性可以看出，树是“最小的连通图”，少一边便不连通；树又是“最大

的无圈图”，多一边便有圈，因而树是以“最经济”的方式把其中各顶点连接起来

的图。

推论2.1.4 任何多于一个顶点的树都至少有两片叶。

证明 设

T

是一棵

(n,m)

树（

n2

），则



deg(v)2m2(n1)2n2

i

i1

n

（1）

若

T

中无树叶，则

T

中每个顶点的度数

2

，则



deg(v)2n

i

i1

n

（2）

若

T

中只有一片树叶，则

T

中只有一个顶点度数为1，其他顶点度数

2

，所以



deg(v)2(n1)2n2

i

i1

n

（3）

(2)，(3)都与(1)矛盾。所以

T

中至少有两片树叶。

树的特征可见：在顶点数给定的所有图中，树是边数最少的连通图， 也是边数

最多的无圈图。由此可知，在一个

(n,m)

图

G

中，若

mn1

，则

G

是不连通的；

若

mn1

，则

G

必定有圈。

例2 设T是一棵树，它有两个2度顶点，一个3度顶点，三个4度顶点，求T的

树叶数。

解 设树T有

x

片树叶，则T的顶点数

n213x

，T的边数为

mn15x

又由

2m



deg(v

i

)

得

2(5x)223143x

i1

n

所以

x9

，即树T有9片树叶。

§2.2 割边与割点

定义2.2.1若无向图

GV,E

为连通图，若有点集

V

1

V

，使图

G

删除了

V

1

的所

有顶点后，所得到的子图是非连通图，而删除了

V

1

的任何真子集后所得到的子图

仍是连通图，则称

V

1

是

G

的一个割集（Vertex Cutset）。若某一个顶点构成一个

割集，则称该顶点为割点（Cut Vertex）。

如图2，{

b

，

d

}，{

c

}，{e}都是割集，顶点

c

和顶点

e

都是割点。虽然删除顶点

a

和

c

图成为不连通的，但因{

c

}是{

a

，

c

}的真子集，所以{

a

，

c

}不是割集。

图2

定义2.2.2 若无向图

GV,E

为连通图，若有边集

E

1

E

，使图

G

删除了

E

1

的

所有边后，所得到的子图是非连通图，而删除了

E

1

的任何真子集后所得到的子图

仍是连通图，则称

E

1

是

G

的一个边割集(Edge Cutest)。若某一条边构成一个边割

集，则称该边为割边(Cut Edge)或桥(Bridge)。

定理2.2.1 一个无向连通图

G

中的顶点

v

是割点的充分必要条件是存在顶点

u

和

w

，使得连接

u

和

w

的每条路都经过

v

。

证明 充分性：如果连通图

G

中存在顶点

u

和

w

，使得连接

u

和

w

的每条路都经过

v

，则在子图

G{v}

中

u

和

w

必不可达，故

v

是割点。

必要性：如果

v

是割点，则

G{v}

中至少有两个连通分支

G

1

V

1

,E

1



和

G

2

V

2

,E

2



，任取

uV

1

，

wV

2

，因为

G

连通，故在

G

中必有连接

u

和

w

的路

P

，

但

u

和

w

在

G{v}

中不可达，因此路

P

必通过

v

，即

u

和

w

之间的任意路必经过

v

。

定理2.2.2 一个无向连通图

G

中的边

e

是割边的充分必要条件是存在顶点

u

和

w

，

使得连接

u

和

w

的每条路都经过

e

。

定理2.2.3 无向连通图

G

中的边

e

是割边的充分必要条件是

e

不包含在图的任何

基本圈中。

证明

e(x,y)

是连通图

G

的割边当且仅当

x

和

y

在

G{e}

的不同连通分支中，而

后者等价于在

G{e}

中不存在

x

到

y

的路，从而等价于

e

不包含在图的任何基本圈

中。于是定理得证。

§2.3 树与生成树

1．无向图中的生成树

定义2.3.1 若无向(连通图)

G

的生成子图是一棵树，则称该树是

G

的生成

树或支撑树(Spanning Tree)，记为

T

。生成树

T

中的边称为树枝。图

G

中其他边

称为

T

的连枝。所有这些连枝的集合称为

T

的补。

T

TT

例如，图3中

(b)

、

(c)

所示的树

1

、

2

是图

(a)

的生成树，而

(d)

所示的树

3

不是图

(a)

的生成树。

(f)

、

(g)

所示的树是图

(e)

的生成树。一般的，一个图的生成树不

唯一。

图3

Te,e,e,eTe,e,eT

{e,e,e}

考虑生成树

1

，可知

1234

是

1

的树枝，

567

是

1

的连枝，集合

567

是

T

1

的补。生成树有其一定的实际意义。

例3 某地要兴建５个工厂，拟修筑道路连接这５处。经勘测其道路可依如图3

(a)

的

无向边铺设。为使这５处都有道路相通，问至少要铺几条路？

解：这实际上是求

G

的生成树的边数问题。

一般情况下，设连通图

G

有

n

个顶点，

m

条边。由树的性质知，

T

有

n

个顶点，

n

－1条树枝，

mn1

条连枝。

在图3

(a)

中，

n5

，则

n1514

，所以至少要修４条路才行。

由图3可见，要在一个连通图

G

中找到一棵生成树，只要不断地从

G

的圈上删去

一条边，最后所得无圈的子图就是

G

的一棵生成树。于是有以下定理。

定理2.3.1任一连通图G都至少有一棵生成树。

证 若G无圈，则G本身为一树。若G有圈。则删去圈上任一边e，G–e仍连

通。对G–e重复上述讨论，直到得到G的无圈的连通子图——生成树。

定理2.3.2 无向图

G

有生成树的充分必要条件是

G

为连通图。

证明 先采用反证法来证明必要性。

若

G

不连通，则它的任何生成子图也不连通，因此不可能有生成树，与

G

有生成

树矛盾，故

G

是连通图。

再证充分性。

设

G

连通，则

G

必有连通的生成子图，令

T

是

G

的含有边数最少的生成子图，于

是

T

中必无圈（否则删去圈上的一条边不影响连通性，与

T

含边数最少矛盾），故

T

是一棵树，即生成树。

生成树的求法

求一个连通图的生成树有一个简单算法，这个算法就是在一个连通图中破掉所有的

圈，剩下不含圈的连通图就是原图一个生成树，这个算法叫做“破圈法”．

也可以用下面的算法来构造连通图的生成树．

在图G中任意取一条边

e

1

，找一条不与

e

1

构成圈的边

e

2

，然后再找一条不与{

e

1

，

e

2

}构成圈的边

e

3

，这样继续下去，直到这种过程不能进行，这时所得到的图G就

是一个生成树．这种算法我们称之为“避圈法”．

2．无向赋权图中的最小生成树

在实际工作中，有很多问题的可行解方案都可以通过一个赋权有向图表示，

例如：物流渠道的设计、物资运输路线的安排、装卸设备的更新、排水管道的铺设

等、所以赋权图被广泛应用于解决工程技术及科学管理等领域的最优化问题。通常

我们称赋权图为网络，赋权有向图为有向网络，赋权无向图为无向网络。在有向图

的讨论中，类似无向图，可以对多重边、环、简单图、链等概念进行定义，只是在

无向图中，链与路、闭链与圈概念是一致的，而在有向图中，这两个概念不能混为

一谈。概括地说，一条路必定是一条链。然而在有向图中，一条链未必是一条路，

只有在每相邻的两弧的公共顶点是其中一条弧的终点，同时又是另一条弧的始点

时，这条链才能叫做一条路这里仅讨论无向赋权图。

权 p个顶点的连通图T，每边指定一正数，称为权；图的权，是指图中所

有边的权之和。T的生成树T的每边权之和是生成树T的权.（权可以表示距离、

费用和时间等）

最小生成树 设

树，

T

G

GV,E

是一连通的带权图，则

G

的生成树

T

G

T

G

为带权生成

的树枝所带权之和称为生成树

T

G

的权(Weight)，记为

w(T

G

)

。

G

中具有最

小权的生成树称为

G

的最小生成树(Minimal Spanning Tree)。

最小生成树有很广泛地应用。例如要建造一个连接若干城市的通讯网络，已知

v

v

城市

i

和

j

之间通讯线路的造价，设计一个总造价为最小的通讯网络，就是求最小

生成树

T

G

。

求最小树通常用以下两种方法。

最小生成树

◇

普里姆算法（1912年提出）：

普里姆（Prim）算法构造最小生成树的过程为：在所有“其一个顶点已经落在生

成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加

在生成树上，直至生成树中含有n-1条边为止。普里姆算法的时间复杂度为O（n2），

与网中的边数无关，适用于求边稠密的网的最小生成树。

◇

破圈法：在给定连通图G中，任取一圈，去掉一条最大权边（如果有两条或两

条以上的边都是权最大的边，则任意去掉其中一条边），在余图中（是图G的支撑

子图）任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即可得到

图G的最小树。

三、最小生成树及其算法

如上所述，一个连通的赋权图G，可能有很多生成树．设T 为图G的一个生

成树，若把T中各边的权数相加所得的和数称之为生成树T的权数．G的所有生

成树中，权数最小者称为G的最小生成树．

求最小生成树问题有很广泛的实际应用．例如把n个城市用高压电缆连接起来

建立一个电网．如何能设计一个把n个城市联系起来的电网，使所用的电缆长度之

和最短，即费用最小（因费用与长度正比），就是一个求最小生成树的问题．

由树的性质及生成树的定义知，树T为图G的最小生成树的充分必要条件是

对T以外的任意边（v

i

,v

j

)，



(v

i

,v

j

)max{



{v

i

,v

i

1

),



(v

i

1

,v

i

2

),,



(v

i

k

,v

j

)}

其中

(v

i

,v

i

1

,v

i

2

,,v

i

k

,v

j

)

为生成树T（V，E）的连接

v

i

和v

j

的路，故G最小生成

树T必然由那些权数较小而不形成任何回路的边组成．下面所介绍的算法都是根

据这个基本原理得到的．

1. 克罗斯克尔算法

克罗斯克尔算法是1956年提出的，俗称“避圈法”．步骤如下：

（1）先把G中所有边按权数大小由小到大重新排列，并取权数最小的一条边

作为T的一条边．

（2）从剩下的边中按（1）的排列顺序取下一条边，若该边与前已取进T中的

边没有形成圈，则把该边取入Ｔ中作为Ｔ的一条边，否则舍去，继续按（１）的排

列顺序再取下一条边，…，如此下去直至有n-1条边组成G的最小生成树Ｔ．

证明 设

是

e

1

,e

2

,

T

0

为由上述算法构造的一个

G

的子图，它的顶点是

G

的

n

个顶点，

，且

T

0

T

0

的边

,e

n1

无圈。由定理7.7.1可知

T

0

是一棵树，且为图

G

的生成树。

下面证明

T

0

是最小生成树。

T

0

设图

G

的最小生成树是

T

。若

T

与

同，则在

T

0

相同，则

e

i1

T

0

是图

G

的最小生成树。若

T

与

e

1

,e

2

,,e

i

T

0

不

中至少存在一条边

e

i1

，使得不是

T

的边，但

T

0

是

T

的边。

因为

T

是树，我们在

T

中加上边

某条边

e

不在

T

0

e

i1

，必有一个圈

C

，而

e

i1

是树，所以

C

中必存在

中。对于树

T

，若以边置换

e

，则得到一棵新树

T



，树

T



的权

C(T



)C(T)C(e

i1

)C(e)

，因为

T

是最小生成树，故

C(T)C(T



)

，即

,e

i

,e

i1

C(eC(e)

i1

)

{e

1

,e

2

,,e

i

,e

i1

}

0

C(e

i1

)C(e)

e,e,

或。因为

12

是

T



的边，且在

T

0

中无圈，故

e

i1

C(e

i1

)C(e)

不可能成立，否则在

C(e

i1

)C(e)

中，自

e

1

,e

2

,,e

i

之

后将取

e

而不能取

成树，但是

T



与

程直到得到与

树。

T

0

，与题设矛盾。于是

T

0

，因此

T



也是

G

的最小生

T

0

的公共边比

T

与的公共边数多1，用

T



置换

T

，重复上述过

T

0

有

n1

条公共边的最小生成树，这时

T



就是，故

T

0

是最小生成

以图11-14为例（节点数n=8）．先按各边权数的权数由小到大排列

e

1

(v

0

,v

1

),e

2

(v

2

,v

3

),e

3

(v

1

,v

2

),

e

4

(v

0

,v

2

),e

5

(v

5

,v

6

),e

6

(v

3

,v

4

),e

7

(v

1

,v

3

),e

8

(v

4

,v

5

),e

9

(v

4

,v

7

),e

10

(v

0

,v

5

),．

由克罗斯克尔算法的步骤，顺次取边

e

1

,e

2

,e

3

,e

4

,e

5

,e

6

,e

7

,e

8

,e

9

，舍去

e

4

和e

7

，

得到最小生成树为

T=

{e

1

，e

2

，e

3

，e

5

，e

6

，e

8

，e

9

}

即为图11-17所示．

为了便于编程，我们采用所谓“最

小标号法”对节点进行重新编号，方

法如下：

先对图中各节点以自然方式编号，

如

节 点

v

0

,v

1

,v

2

,v

3

,v

4

,v

5

,v

6

,v

7

自然编号 1 2 3 4 5 6 7 8 图11-17

以后每一步对取进T中边的节点都要重新编号：若（u

1

，u

2

，···，u

r

）为T

中任意一条路，则该路所经过的节点u

1

，u

2

，···，u

r

都要重新标以它们中最小的标

号，即

l(u

1

)l(u

2

)l(u

r

)min{u

1

,u

2

,,u

r

)

．

经过这种“最小标号法”重新编号后，就能判断下一条边

e

k

(v

k

i

,v

k

j

)

是否与前

已取进T中的边构成某回路，因此决定

e

k

(v

k

i

,v

k

j

)

是否能取进T中．若

l(v

k

i

)l(v

k

j

),

则说明

e

k

(v

k

i

,v

k

j

)

取进T中会形成一个回路，应舍去

e

k

(v

k

i

,v

k

j

)

；若

l(v

k

i

)l(v

k

j

),

说

明至少有一个节点不在前已取进的T的节点中，故在T中加入

e

k

后不会形成任何

回路，因而应将

e

k

(v

k

i

,v

k

j

)

取进T中．如此下去，最终能得到最小生成树Ｔ．

克鲁斯卡尔算法的时间复杂度与图中的边数有关，适用于求边稀疏的图的最小

生成树。

2．普莱姆算法

普莱姆算法的基本思想为：

（1）先在G中任取一个节点

v

0

，并取入T 中；

（2）令S=Ｖ(G)＼Ｖ(T)，其中V（G），V（T）分别为G与T的节点集；

（3）在所有连接V（T）的节点与S的节点的边中，选出权数最小的边

(u

0

,v

0

),

即



(u

0

,v

0

)min{



(u,v)|uV(T),vS}

（4）将边

(u

0

,v

0

)

取入T中．重复（2）至（4）步骤，直至G中的节点全都取

入T中为止．

仍以图11-14为例，若

v

0

为起点，顺次取入T中的边为

(v

0

,v

1

),(v

2

,v

3

),(v

3

,v

4

),(v

4

,v

5

),



v

5

,v

6



，

(v

4

,v

7

),

或

(v

6

,v

7

)

形成的最小生成树T与图

11-17一致．

类似可定义最大生成树及其相应的算法．

例4求图4中赋权图的最小生成树。

解 因为图(a)中

n

＝8，所以按算法要执行

n

－1＝7次，其过程见图4(b)~(h)所示。

图4

例5 图5所示的赋权图

G

表示七个城市

a,b,c,d,e,f,g

及架起城市间直接通讯线路

的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出

最小造价。

图5

解 该问题相当于求图

G

的最小生成树问题，此图的最小生成树为图5中的T，因

此如图T架线使各城市间能够通讯，且总造价最小，最小造价为：

W(T

G

)134892348

．

例6求下列图（ a ）和（ b ）中的最小生成树。

解：根据克鲁斯卡尔算法，求得最小生成树如下：

图6

补充

根树及其应用

1 有向树

定义1.1 一个有向图，若不考虑边的方向，它是一棵树，则称这个有向图为有向

树(Directed Tree )。 一棵有向树，如果恰有一个顶点的入度为0，其余所有顶

点的入度都为１，则称为根树(Rooted Tree)，其中入度为0的顶点称为树根(Root)，

出度为0的顶点称为树叶，出度不为0的顶点称为分枝点或内点。

定义1.2 一棵有向树，如果恰有一个结点的入度为0，其余所有结点的入度都为1，

则称为根树。入度为0的结点称为根，出度为0的结点称为叶，出度不为0的结点

称为分枝点或内点。

从根树的结构中还可以看到，树中每一个结点都可看到是原来树中的某一棵子树的

根，由此可知，根树亦可递归定义为：

定义1.3 根树包含一个或多个结点，这些结点中某一个称为根，其他所有结点被

分成有限个子根树。

这个定义把n个结点的根树用结点数少于n的根树来定义，最后得到每一棵都是一

个结点的根树，它们就是原来那棵树的叶。

对于一棵根树，可以有树根在下或树根在上的两种不同画法，

根树的画法有：树根在下，向上生长；树根在上，向下生长。

例如，图7

(a)

、

(b)

、

(c)

和

(d)

均为有向树，其中只有

(c)

和

(d)

为根树。在根树图

(d)

中，

v

1

为树根，

v

1

,v

2

,v

3

为分枝点，其余顶点为树叶。习惯上我们把根树的根画

在上方，叶画在下方，这样就可以省去根树的箭头，如图7

(e)

所示。

v

在根树中，称从树根到顶点

v

的距离为该点的层次。这样对图7中的根树

(d)

，

1

的

层次为0，

v

2

,v

3

的层次为１，其余顶点的层次均为２。

（f）

图7

vvv

vvv

定义1.4 在根树中，若从

i

到

j

可达，则称

i

是

j

的祖先，

j

是

i

的后代；又若

vv

v

v

vv

〈

i

，

j

〉是根树中的有向边，则称

i

是

j

的父亲，

j

是

i

的儿子；如果两个顶点

是同一顶点的儿子，则称这两个顶点是兄弟。

定义1.5 在根树中，任一顶点

v

及其

v

的所有后代和从

v

出发的所有有向路中

的边构成的子图称为以

v

为根的子树。根树中的顶点

u

的子树是以

u

的儿子为根的

子树。

在现实的家族关系中，兄弟之间是有大小顺序的，为此我们引入有序树的概念。

定义1.6 如果在根树中规定了每一层次上顶点的次序，这样的根树称为有序

树(Ordered Tree)。在有序树中规定同一层次顶点的次序是从左至右。例如，图

7

(c)

和

(d)

均为有序树。

定义1.7一个有向图，如果它的每个连通分支是有向树，则称该有向图为(有向)

森林；在森林中，如果所有树都是有序树且给树指定了次序，则称此森林是有序森

林。例如，图7(f)是一个有序森林。

2

m

叉树

在树的实际应用中，我们经常研究完全

m

叉树。

定义2.1 在根树

T

中，若顶点的最大出度为

m

，则称

T

为

m

叉树(

m

-ary Tree)。

如果

T

的每个分枝点的出度都恰好等于

m

，则称

T

为完全

m

叉树(Complete

m

-ary Tree)。若

m

叉树的所有叶顶点在同一层，则称它为正则

m

叉树(Regular

m

-ary Tree)。二叉树(Binary Tree )的每个顶点

v

至多有两棵子树，分别称为

v

的左子树和右子树。若顶点

v

只有一棵子树，则称它为

v

的左子树或右子树均可。

若

T

是（正则）

m

叉树，并且是有序树，则称

T

为

m

元有序（正则）树。

二叉树(二元树) 每个顶点的出度均小于或等于2的根树

例如，在图8

(a)

是一棵二叉树，而且是正则二叉树；图8

(b)

是一棵完全二叉树；

图8

(c)

是一棵三叉树，而且是正则三叉树；图8

(d)

是一棵完全三叉树。

图8

有很多实际问题可用二叉树或

m

叉树表示。

例1 甲、乙两人进行球赛， 规定三局两胜。图9表示了比赛可能出现的各种情况

（图中顶点标甲者表示甲胜，标乙者表示乙胜），这是一棵完全二叉树。

图9

m

叉树中，应用最广泛的是二叉树。由于二叉树在计算机中最易处理，所以常常

需要把一棵有序树转换为二叉树。其一般步骤为：

(1) 从根开始，保留每个父亲与其最左边儿子的连线，删除与别的儿子的连线；

(2) 兄弟间用从左向右的有向边连接；

(3) 用如下方法选定二叉树的左儿子和右儿子：直接处于给定顶点下面的顶点

作为左儿子； 对于同一水平线上与给定顶点右邻的顶点作为右儿子，依次类推。

例2 将图10

(a)

所示的三叉树转换为一棵二叉树。

解 对图

(a)

进行步骤(1)、(2)得图

(b)

，再按步骤(3)得图

(c)

。 图10

(c)

即为所求

的二叉树。反过来，我们也可将图

(c)

还原为图

(a)

。

图10

用二叉树表示有序树的方法，可以推广到有序森林上去，只是将森林中每棵树的根

看作兄弟。其步骤为：

(1) 先把森林中的每一棵树表示成一棵二叉树；

(2) 除第一棵二叉树外，依次将每棵二叉树作为左边二叉树的根的右子树，直

到所有的二叉树都连成一棵二叉树为止。

例3将图11

(a)

所示的有序森林转换为一棵二叉树。

解 如图11

(b)

的二叉树即为所求。

图11

关于完全

m

叉树，我们有如下定理。

定理2.1 在完全

m

叉树中，若树叶数为

t

，分枝点数为

i

，则有

(m1)it1

证明 由假设知，该树有

it

个顶点，则该树边数为

it1

。因为所有顶点出度

之和等于边数，所以根据完全

m

叉树的定义知，

miit1

即

(m1)it1

。

例4 假设有一台计算机，它有一条加法指令，可计算3个数之和。如果要求9个

xx

数

1

，

2

，，

x

9

之和，问至少要执行几次加法指令？

解 用顶点表示每个数，把9个数看成树叶，将表示3个数之和的顶点作为它

们的父亲顶点。这样本问题可理解为求一个完全三叉树的分枝点的个数问题。有

(31)i91

由此得

i

＝４。

所以至少要执行 4 次加法指令。

图12表示了两种可能的计算顺序。

图12

例5 设有33盏灯，拟公用一个电源，则至少需要多少个5插头的接线板 ?

解 把33盏灯看成树叶，将5插头的接线板看成分枝点，这样本问题可理解

为求一个完全5叉树的分枝点的个数

i

的问题。有

(51)i331

由此得

i

＝8所以

至少需要8个5插头的接线板。

例6枚硬币问题。若有8枚硬币

a,b,c,d,e,f,g,h

，其中 7 枚重量相等，只有1枚

稍轻。现要求以天平为工具，用最少的比较次数挑出轻币来。

解 可用图13所示的树表示判断过程。从图中可知，只需称2次即可挑出轻

币。这种用于描述判断过程的树叫判定树。

图13

3 最优二叉树

定3.1 设有一棵二叉树，有

t

片树叶。使其树叶分别带权

带权二叉树(Weighted Binary Tree)。

定义3.2 设有一棵带权

w

1

,w

2

,,w

t

w

1

,w

2

,,w

t

的二叉树称为

的二叉树

T

，其权为

w

i

的树叶的层为

L(w

i

)

。

（1）该带权二叉树的权

W(T)

定义为

（2）在所有带权

w

1

,w

2

,,w

t

W(T)



w

i

L(w

i

)

i1

t

的二叉树中，

W(T)

最小的树称为最优二叉树

(Optimal Binary Tree)。

1952年哈夫曼（Huffman）给出了求带权

w,w,

令

S

{

12

,w

t

ww

2



}，

1

w

i

w

1

,w

2

,,w

t

的最优二叉树的方法：

,t

）。

w

t

v

w

，

i

是树叶

i

所带的权（

i1,2,

（1）在

S

中选取两个最小的权

一分支点

v

ij

，

w

j

v

v

，使它们对应的顶点

i

，

j

做兄弟，得

，令其带权为

w

i

w

ij

w

i

w

j

。

w

ij

（2）从

S

中去掉，

w

i

，再加入。

（3）若

S

中只有一个元素，则停止，否则转到(1)。

最优二叉树的权是唯一的，但最优二叉树未必唯一。

例8 求带权7， 8， 9， 12， 16的最优二叉树。

解 图14

(a)

～

(d)

给出了哈夫曼（Huffman）算法的全过程。

图14 图15

需要注意的是，最优二叉树不是唯一的，图15中的两个图都是带权1，2，3，4，

6的最优二叉树。

例9 试画出一棵带权1，2，3，4，5，6，7，8，9，10的最优二叉树。

解：根据哈夫曼算法，求得最优二叉树如下：其权为174

反之，任给定由N中元素构成的长为n-2的一个序列t

1

，t

2

，…，t

n-2

，可以如下地画一棵生成树： s

1

是N中

不在｛t

1

，t

2

，…，t

n-2

｝中的第一个号码，把s

1

与t

1

连一边；s

2

是不在｛t

2

，t

3

，…，t

n-2

｝中的N-｛s

1

｝的第

一个号码，把s

2

与t

2

连一边；s

3

是不在｛t

3

，t

4

，…，t

n-2

｝中的N-｛s

1

，s

2

｝的第一个号码，把s

3

与t

3

连一

边。继续这一过程，得n-2条边(s

1

，t

1

)，(s

2

，t

2

)，(s

3

，t

3

)，…，(s

n-2

，t

n-2

)，再连接N-｛s

1

，s

2

，s

2

, s

3

，…，

s

t-2

｝中的两个结点，则得到一棵生成树。

由此可知，序列集合｛(t

1

，t

2

，…，t

n-2

)｝与K

n

的生成树集合之间一一对应。而序列集合的基数为n，

所以K

n

的生成 树的数目为n。

本定理的证明思路较好地体现了图论与组合计数的联系，其证明方法值得借鉴揣摩。

n-2

n-2

图11.3

现在再回到前面乡村公路建设问题：将每一个村子作为结点，边表示村子之间可能的公路，不同的村

子之间公路造价是可能有所不同的，因此，以村子之间的公路造价作为边权值。从而得到一个完全图K

20

。这

样的图称作带权图(Weighted graph)。为了节省公路造价，20村子之间的公路建设可以选择生成树的结构，

需要在K

20

的生成树中选择一个造价最小者。用图论的术语来说，就是需要在K

20

中找一个权值最小的生成树T。

下面首先定义最小生成树。

若T是G的生成树，则T的权值w(T)是T的所有边的权值之和:

w(T)=.

G的所有生成树中，权值最小者称为最小生成树(minimum spanning tree)。

最小生成树起源于人类学家Jan Czekanowski在分类模式方面的研究，后由Otakar Boruvka在1926

年在对电力网络的研究中完成了初步的形式化工作，在计算机通信、运输网络等方面具有重要的应用。

但K

20

的生成树个数达到20个，通过直接比较每一棵生成树以找到造价最小的公路结构，是不可能

的事。但可以通过下面介绍的Kruskal算法来求解。

Kruskal算法

设G=(V，E，W)是有n个结点的带权连通简单图。

(1) 从G中选取一边e

1

，使w(e

1

)最小。令E

1

=｛e

1

｝，1→i

18

(2) 若已选E

i

=｛e

1

，e

2

，…，e

i

｝，则从E-E

i

中选取一边e

i

+1，满足：

① E

i

∪｛e

i

+1

② 在E-E

i

的满足①的所有边中，w(e

i+1

)最小。

(3) 若e

i+1

存在，则令E

i+1

=E

i

∪｛e

i+1

｝，i+1→i，转(2)；若e

i+1

不存在，则算法终止。此时E

i

导出的

子图就是所求的最小生成树，记为T。

下面来证明Kruskal算法的正确性。

定理11.4 Kruskal算法所得到的图T

是G的最小生成树。

*

*

证明 由算法显见，T

是G的一棵生成树。

*

设T不是最小生成树，按Kruskal算法T的边选取顺序为e

1

，e

2

，e

3

，…，e

n

*

**

对于不同于T的任一生成树T

i

，使e

i

不在T

i

中的最小i值记为f(T

i

)。令T是使f(T)值最大的一棵最

小生成树。

因为T不是最小生成树，所示e

1

，e

2

，…，e

n

中必有不在T中的边。

假设f(T)=k，即e

1

，e

2

，…，e

k-1

同时在T和T中，但e

k

不在T中。把e

k

加入T，则T∪e

k

中恰有一个

环C。注意到T中无环，于是有C中必存在一边e′

k

，e′

k

不在T中。显然T′=(T∪e

k

)-e′

k

仍是G的一棵生

成树，且w(T′)=w(T)+w(e

k

)-w(e′

k

)。

由Kruskal算法，当选定e

1

，…，e

k-1

后，｛e

1

，…，e

k-1

，e

k

｝和｛e

1

，…，e

k-1

，e′

k

｝均不构成环，

而算法选e

k

必有w(ek

k

)≤w(e′

k

)。

所以w(T′)≤w(T)。

即w(T′)也是一棵最小生成树，从而f(T′)＞k=f(T)，与f(T)最大矛盾。所以T必为最小生成树。

*

**

*

*

例11.3 图11.4中给出了两个带权连通图，并用粗线表示按Kruskal算法得到的最小生成树。

例11.10 Huffman编码

在远距离通讯中，常用由0和1组成的序列表示英文字母。发送方将英文内容转换成相应的0和1组

成的序列，接受方再将这一序列还原成英文内容。因此需要对字母进行编码，如a编码为01，b编码为101

等等。但具体如何设计编码方案？编码的方案很多，但有两条原则是基本的。

一是出现频率高的字母用较短的0和1序列表示，这样可使整个0和1序列的长度尽可能小；二是接受方能

根据编码方案准确地进行还原工作，也就是说不能出现这样的情况：a编码为01，b编码为010，c编码为11，

d编码为011，于是，如果有这样的串01011，可以翻译为ad，也可以为bc。因此要求不能出现任何一字母的

编码是其它字母编码的前缀的情况。因此这种编码也称为前缀码。

因为用0和1来对字母编码，这容易注意到可以用二分树来进行编码工作，事实上，有如下结论：

给定一棵二分树，则可确定一个前缀码。反之，对应于一个前缀码，存在一棵二分树。

事实上，对任一给定的二分树，它的每一个分枝结点有两个孩子结点，自左至右分别标记为0和1。

每一叶结点用从根到该结点的路上边的标记组成的序列标记。所有树叶上序列组成的集合就是前缀码。否则，

若一个序列是另一序列的前缀，则该序列必位于根到另一序列对应的树叶的这条路的分枝点上。反之，设前

缀码中最长序列的长为h。画一棵高为h(即根到叶结点的最大长度为h)的完全二分树，并使树叶在同一层上。

从每个分枝点向它的子枝连出两条边分别标记0和1。从根到每个结点的路上边的标记组成的序列标记该结

点。将树上不属于前缀码中序列所对应的叶结点及其关联的边删去，得到的二分树其树叶对应的序列组成的

集合就是前缀码。

现在还有一个问题是，要求出现频率高的字母编码长度尽可能短，显然对应这样的字母编码的叶子结

点最好靠近根结点。

Huffman给出了具体的基于二分树的前缀码编码算法：

设t个权w

1

，w

2

，…，w

n

，且w

1

≤w

2

≤…≤w

t

。

1) 构造t棵树，每棵树是一个结点，分别带权w

1

，w

2

，…，w

t

；i=t

2) 若i=1，算法终止。否则，设现有i棵树的根为n

1

，n

2

，…，n

i

，分别带权w′

1

，w′

2

，…，w′

i

。从

n

1

，…，n

i

中选权最小的两个结点，设为n

k

，n

l

，合并以n

k

和n

l

为根的两棵树，得到一棵树的二分树，其中以

n

k

，n

l

为根的树分别为左、右子树，根设为n′，n′带权w′

k

+w′

l

。

3) 现有i-1棵树，树根分别为n

1

，…，n

k-1

，n

k+1

，…，n

l-1

，n

l+1

，…，n

i

，n′，i=i-1时转至(2)。

按照霍夫曼算法，最终可以得到一棵二分树, 该树被称为最优二分树，简称最优树，即所得到的二分

树是带权w

1

，w

2

，…，w

t

二分树（每个树叶对应一个权值）T中，使W(T)最小的二分树。其中W（T）=

l

i

为从根到带权w

i

的树叶的路的长度。

下面两个结论表明了按照霍夫曼算法生成的二分树一定是最优树：

设一棵带权w

1

，w

2

，…，w

n

的最优树，w

1

≤w

2

≤…≤w

n

，则：

，

1）带权w

1

，w

2

的树叶v

w1

，v

w2

是兄弟，而且以树叶v

w1

，v

w2

为儿子的分枝点，其到根结点的路最长。

2）若将以带权w

1

和w

2

的树叶为儿子的分枝点改为w

1

+w

2

的树叶，得到一棵树T′，则T′也是最优树。

可以采用反证法来证明上述二结论，此略。