文库发布：121aolm离散数学

第1篇数理逻辑第2篇集合论第3篇代数结构第4篇图论第4篇图论模型化是数学中的一个基本概念，它处于所有的数学应用之心脏，也处于某些最抽象的纯数学核心之中。

R.C.Buck第4篇图论第10章图第11章特殊图第12章树第4篇图论第12章树12.1树的概念12.2生成树12.3根树、二叉树及其应用12.4典型例题解析第12章树 几何、理论算术和代数，这些学科除了定义和公理之外，没有其它原则，除了演绎以外，没有其它证明过程。但就在这一过程中，却已综合了简单性、复杂性、严密性和一般性，这一特性是不为其它学科所具有的。

WhewellW. 首先介绍树的基本概念；然后将分别介绍生成树、根树及特殊的一类根树——二叉树及其应用。第12章树树是一类特殊的二分图（偶图）。作为计算机科学中常用的一种数据结构，树有许多非常好的性质，因此树被广泛地应用于算法设计、数据结构、网络、人工智能、软件工程、知识工程以及其他领域。

12.1树的概念

定义12.1一个连通且无回路的无向图称为树。在树中度数为1的结点称为树叶，度数大于1的结点称为分枝点（内点）。单一孤立结点称为空树。如果一个无回路的无向图的每一个连通分图是树，且连通分支数大于等于2，那么称为森林。v3v2v7v4v1v9v5v8v6（a）树（b）树（c）森林定理12.1“给定图为树”与下列任一命题等价： （1）无回路的连通图； （2）无回路且e=v-1，其中e是边数，v是结点数； （3）连通且e=v-1； （4）无回路，但增加一条新边，得到一个且仅有一个回路； （5）连通，但删去一边后就不再连通； （6）每一对结点之间有且仅有一条路。证明：将一次证明⑴

⑵、⑵

⑶、⑶

⑷、⑷

⑸、⑸

⑹、⑹

⑴，从而证明6个命题之间的等价性，使定理得证。 （1）归纳法证明⑴

⑵

设在图T中，当v＝2时，连通无向图，T中 的边数e＝1，因此e＝v

1 成立。

设v＝k

1时命题成立，当v＝k时，因无向图且连通，故至少有一条边其一个端点u的度数为1。设该边为(u,w)，删去结点u，便得到一个k

1个结点的连通无向图T’，由归纳假设，图T’的边数

e’＝v’

1＝(k

1)

1＝k

2，于是再将结点u和关联边(u,w)加到图T’中得到原图T，此时图T的边数为:

e＝e’

1＝(k

2)

1＝k

1，结点数v＝v’

1＝(k

1)

1＝k，故

e＝v

1

成立。（2）反证法证明⑵

⑶若T不连通，并且有k(k≥2)个连通分支T1,T2,…,Tk，因为每个分图是连通无回路，则可证：如Ti

有vi

个结点vi＜v时，Ti

有vi

1

条边，而

v＝v1

v2

…

vk e＝(v1

1)

(v2

1)

…

(vk

1)＝v

k

但 e＝v

1

故 k＝1

这与假设G是不连通的，即

k≥2 相矛盾。（3）归纳法证明⑶

⑷若T连通且有v

1条边。

当v＝2时，e＝v

1＝1，故T必无回路。如增加一条边，那么得到且仅得到一个回路。

设v＝k

1时命题成立。考察v＝k时的情况，因为T是连通的，e＝v

1。故每个结点u有

deg(u)≥1

可以证明至少有一结点u0，使

deg(u0)＝1

若不然，即所有结点u有deg(u)≥2，则2e≥2v，即e≥v

与假设e＝v

1

矛盾。 删去u0

及其关联的边，而得到图T′，由归纳假设得知T′无回路，在T′中加入u0

及其关联边又得到T，故T无回路的，如在T中增加一条边(ui,uj)，则该边与T中ui

到uj

的路构成一个回路，则该回路必是唯一的，否则若删除这条新边，T必有回路，得出矛盾。（4）反证法证明⑷

⑸若图T不连通，则存在结点ui

与uj，ui

与uj

之间没有路，显然若加边{ui，uj}不会产生回路，与假设矛盾。又由于T无回路，故删去任一边，图就不连通。（5）反证法证明⑸

⑹由连通性可知，任两个结点间有一条路，若存在两点，在它们之间有多于一条的路，则T中必有回路，删去该回路上任一条边，图仍是连通的，与命题⑸矛盾。（6）反证法证明⑹

⑴任意两点间必有唯一一条路，则T必连通，若有回路，则回路上任两点间有两条路，与命题⑹矛盾。

根据定理12.1，如果删除树图的任意一边，树就不再连通，所以在保持相同结点的图中，树是“最小的连通图”。如果为树图增加一边，那么图中将由回路，所以在保持相同结点的图中，树是“最大的无回路图”。树以“最经济”的方式把图中各结点连接起来。因此，树作为典型的数据结构被应用在各类网络的主干网中。除了上边描述的树的性质之外，树还有其他一些特殊的性质。定理12.2树和森林都是2-可着色的，因此树和森林都是二分图。 证明略。定理12.3树和森林都是面数为1的平面图。 证明略。定理12.4任何树至少有两片叶子。证明：设树T＝<V,E>，＝v，因为T是连通图，对于任意，有

deg(Vi)≥1

且

(1)若T中每一个结点的度数大于等于2，则 得出矛盾。

(2)若T中只有一个结点度数为1，其它结点的度数大于等于2，则 得出矛盾。 故T至少有两个结点度数为1，即： 任何树至少有两片叶子。

12.2生成树树是一种具有优秀结构的、最经济的图。人们希望能很好地利用树这种结构。一些连通图虽然本身不是树，但是根据树的特性，人们想到连通图的“最小连通生成子图”应当是树，其中，重要的一类是生成树。

定义12.2若图G的生成子图是一棵树，则该树称为G的生成树。设图G有一棵生成树T，则T中的边称作树枝。图G中不在生成树上的边称为弦。所有弦的集合称为生成树T相对于G的补。 上图所示的连通图G的一棵生成树T如图(b)所示，其中e1,e4,e6,e5,e8是T的树枝

e2,e3,e7

是T的弦。{e2,e3,e7}是生成树T的补。e3e1e6e4e5e2e7e8e1e6e4e5e8（a）（b）【例12.1】请找出下图(a)所示的图G的所有生成树。解：图G的生成树如图(b)~(l)所示。

v4v1v2v3v5v6v7v8（a）v4v1v2v3v5v6v7v8（b）v4v1v2v3v5v6v7v8（c）v4v1v2v3v5v6v7v8（d）v4v1v2v3v5v6v7v8（e）v4v1v2v3v5v6v7v8（f）v4v1v2v3v5v6v7v8（g）v4v1v2v3v5v6v7v8（h）v4v1v2v3v5v6v7v8（i）v4v1v2v3v5v6v7v8（k）v4v1v2v3v5v6v7v8（j）v4v1v2v3v5v6v7v8（l）由此可见，一个连通图的生成树不唯一。定理12.5任一连通图都至少有一棵生成树。证明：⑴设连通图G没有回路，则它本身就是一棵生成树。 ⑵若G至少有一个回路，删去回路上的一条边，得到G1，它仍然是连通的，并与G有相同的结点集。 若G1

没有回路，则G1

就是G的生成树。 ⑶若G1

仍然有回路，那么再删去G1

回路上的一条边，重复上面的步骤，直到得到一个连通图H，它没有回路，但与G有相同的结点集，因此H为G的生成树。定理12.5证明再次说明，一个连通图的生成树是不唯一的。生成树有两个很重要的性质。定理12.6设G为连通无向图，那么：（1）G的任一回路与任一生成树T的关于G的补G-T至少有一条公共边。

（2）G的任一边割集与任一生成树T至少有一条公共边。证明：反证法。 （1）若有一条回路和一棵生成树的补没有公共边，那么这回路包含在生成树之中，然而这是不可能的，因为一棵生成树不能包含回路。 （2）若有一条边割集和一棵生成树没有公共边，那么删去这个边割集后，所得的子图必然包含该生成树，这意味着删去边割集后仍然连通，与边割集定义矛盾。定义12.3设G是具有n个结点的带权连通图。G的生成树T的所有边的权之和为树的权。在图G的所有生成树中，树权最小的那棵生成树称作最小生成树。注意，带权图G的最小生成树不唯一。7810（a）2025131425630301130418143097810（b）25131461130309带权图G和它的一个最小生成树T

下面我们给出求带权图G的最小生成树的Kruskal

算法。算法12.1(Kruskal)设图G有n个结点，按以下步骤可以求得图G的最小生成树。 （1）按权值升序将图G的边排序，得到表L； （2）令； （3）在表L中依次选取下一条边e，如果，且 构成的子图是无圈图，则令； （4）若，则算法停止，输出集合S即为所求。否则，转⑶，继续遍历表L。 可以证明，算法12.1求得的是图G的最小生成树。【例12.2】应用算法12.1求图G的最小生成树，G如图(a)所示。求最小生成树

e5（a）Gv61214v5v4v1v7v3v2e1e6e8e4e7e9e3e10e11e224155441e5（b）G的最小生成树

v61214v5v4v1v7v3v2e1e6e4e7e2141解： （1）根据Kruskal

算法，首先根据图G得到按权值的边排序表L：e5,e7,e2,e4,e6,e8,e9,e1,e10,e3,e11

。 （2）然后，令。 （3）接下来，依次将e5,e7,e2,e4,e6,e1

放入S中；边e8,e9

被忽略，因为它们的加入会形成圈。 （4）此时S中有6条边，满足，所以算法结束。得到的最小生成树T如图(b)所示，树权为10。

最小生成树的构造还可以使用其他算法。算法12.2（Prim算法） （1）选出结点v，令，； （2）在所有的结点中，若连接结点u和w的边e＝uw

是最小权重边，其中，，则令，； （3）若，算法停止，输出。否则，转⑵，继续向树中增加新结点。【例12.3】使用Prim算法求图G的最小生成树。解：不失一般性，选出结点v1，令，。 图(a)~(g)显示出按照Prim算法求最小生成树的过程。

e5Gv61214v5v4v1v7v3v2e1e6e8e4e7e9e3e10e11e224155441e5（g）V(T)={V1,V6,V5,V7,V4,V2,V3}E(T)={e6,e5,e7,e4,e10,e2}v61214v5v4v1v7v3v2e6e4e7e10e2141e5（c）V(T)={V1,V6,V5

}E(T)={e6,e5}v6124v5v1e6e5（d）V(T)={V1,V6,V5,V7

}E(T)={e6,e5,e7}v6124v5v1v7e6e71（b）V(T)={V1,V6}E(T)={e6}v62v1e6（b）V(T)={V1

}E(T)={}v1e5（f）V(T)={V1,V6,V5,V7,V4,V2}E(T)={e6,e5,e7,e4,e10}v61214v5v4v1v7v2e6e4e7e1014e5（e）V(T)={V1,V6,V5,V7,V4

}E(T)={e6,e5,e7,e4}v61214v5v4v1v7e6e4e71注意，例12.3求得的最小生成树（图(g)）不同于例12.2（图(b)）。这也说明一个图的最小生成树不唯一。12.3根树、二叉树及其应用本节之前，所讨论的特殊图都是无向图。本节将讨论一类有向图，也是一类特殊的树——根树。12.3.1根树定义12.4如果一个有向图在不考虑边的方向时是一棵树，那么，这个有向图称为有向树。 有向树定义12.5一棵有向树，如果恰有一个结点的入度为0，其余所有结点的入度都为1，则称为根树。入度为0的结点称为根，出度为0的结点称为叶子，出度不为0的结点称为分支点或内点。根树右图表示一棵根树，其中，V0

为根，V4,V5,V3,V8,V9,V10

为叶子，V1,V2,V6,V7

为内点或分支点。V0V3V2V1V7V6V5V4V10V9V8定义12.6设a是一棵根树的分支点，b、c是结点。如果从a到b存在一条边，则结点b被称为a的“儿子”结点，a为b的“父亲”结点。如果从a到c存在一条单向通路，则a被称为的“祖先”，c为a的“后裔”。同一个分支点的“儿子”结点被称为“兄弟”结点。 上图中，v0为v1,v2,v3

的“父亲”，v1,v2,v3

是v0的“儿子”；v0是v4,v5,v6,v7,v8,v9,v10

的祖先，它们是v0

的“后裔”；v1,v2,v3

三者是“兄弟”。 根树的任一结点v的层次是从根到该结点的单向通路长度。在上图中，v1,v2,v3

的层次是1，v4,v5,v6,v7

的层次是2，v9,v10

的层次是3。在许多情况下，需要对根树中同一父亲的儿子规定某种顺序。定义12.7如果根树T为每个父亲结点的儿子结点规定了次序，则称T为有序树。通常默认的顺序为从左到右。

根据根树的结构特点，根树还可以递归定义为：定义12.8树T称为根树，如果：

（1）T为一个孤立结点v0，v0又被称为T的树根；

（2）T1…Tk

为以v1…vk

为树根的根树，T1由T1…Tk

及与v1…vk

相邻的结点v0

组成。称v0为T的树根。根树除了具有树的一般特性外，还有下列简明特性:

（1）根树的每个结点都是一颗子树的树根； （2）除了树根，根树中每结点均为某一结点的儿子，除了树叶，根树中每一结点均为某些结点的父亲； （3）树根到叶子有唯一的通路，这样的通路中最长一条的长度称为树高。为了图示清晰，通常约定：根树的树根总画在树的顶部，同一结点的儿子画在同一水平线上。12.3.2二叉树及其遍历有一类特殊的根树称为二叉树。由于二叉树有许多很好的特性，所以二叉树有广泛的应用。定义12.9在根树中，若每一个结点的出度小于或等于m，则这棵树称为m叉树；若m＝2时，称为二叉树。如果每一个结点的出度恰好等于m或零，则这棵树称为完全m叉树；若m＝2时，称为完全二叉树。若所有的树叶层次相同，则这棵树称为正则m叉树；若m＝2时，称为正则二叉树。

图(a)~(d)分别给出了m叉树、二叉树、完全二叉树、正则二叉树。（a）m叉树（b）二叉树（c）完全二叉树（d）正则二叉树现实生活许多问题都可以用二叉树来描述和求解。例如，A和B进行一场网球比赛。如果一人连胜两盘活五盘三胜，那么他就获胜。每一盘比赛要么A获胜，要么B获胜，只有这两种可能。因此，A和B得比赛可能产生的结果可以用二叉树来表示，如图所示。AAABAAAAAABBBBBB二叉树表示的比赛结果任一棵叉树都可以改写为一棵对应的二叉树。图(a)为m叉树，将其转换为图(c)所示的二叉树，方法如下： （1）保留每个结点最左边的分支点，删去所有其他分支。同一层中，兄弟结点之间以从左到右的有向边连接，如图(b)所示。DBCAJHEFKIGDBCAJHEFKIG（a）m叉树

（b）转换第一步

（2）将直接处于给定结点下面的结点，作为左儿子，与给定结点处于同一水平线上的右邻结点作为右儿子，如图(c)所示。

DBCAJHEFKIGDBCAJHEFKIG（b）转换第一步

（c）与(a)对应的二叉树

同样地，此方法可以推广到森林，将森林改写为二叉树。图(a)所示的森林被转换为图(c)所示的二叉树。DBCAJHEFKIGLM(a)DBCAJHEFKIGLM(b)DBCAJHEFKIGLM(c)完全二叉树的一些性质。 定理12.7设完全m叉树，有t片叶子、i个分支点，则。 证明：若把m叉树当作是每局有m位选手参加比赛的单淘汰赛计划表，树叶数为t表示参加比赛的选手数，分枝点数为i表示比赛的局数，因为每局比赛将淘汰(m

1)位选手，比赛的结果共淘汰(m

1)i位选手，最后剩下一个冠军，因此(m

1)i

1＝t即(m

1)i＝t

1。定义12.10在根树中，从树根到某个结点的通路中的边数称为该结点的通路长度。分枝点的通路长度称作内部通路长度，树叶的通路长度称作外部通路长度。最长的外部通路长度称为树高。定理12.8若完全二叉树有n个分支点，内部通路长度总和为

I，外部通路长度总和为E，则。证明：归纳法。对分枝点数目n进行归纳。 （1）当n＝1时，E＝2，I＝0，故

E＝I

2n 成立。 （2）假设n＝k

1时成立，即

E’＝I’

2(k

1)

（3）当n＝k时，若删除去一个分枝点v，该分枝点与根的通路长度为l，且v的两个儿子是树叶，得到新树T’。将T’与原树比较，它减少了两片长度为l

1的树叶和一个长度为l的分枝点，因为T’有(k

1)个分枝点，故E’＝I’

2(k

1)。但在原树中，有E＝E’

2(l

1)

l＝E’

l

2,I＝I’

l，代入上式得E

l

2＝I

l

2(k

1)，即

E＝I

2k 成立。定理12.9完全二叉树的结点个数必定为奇数。 证明：完全二叉树中，除树根的度为2外，其它结点的度均为3或1，因此完全二叉树的度数总和为n

1个奇数的和加上2。若n为偶数，则n

1为奇数，从而树的度数总和为奇数，但这是不可能的。因此n必为奇数。定理12.10完全二叉树中叶子的数目，其中n为树中的结点个数。 证明：设完全二叉树T有n个结点、l片叶子和m条边，那么，除树根和叶子以外，T有n

1

l个、度为3的分支结点，因此有：得为定理12.11设完全二叉树有n个结点，则完全二叉树的高h满足，其中[]表示取整运算，取不大于[]中的表达式值得最大整数。证明：先证，再证。

（1）如果高为h

的完全二叉树的树根到每片叶子的通路长度均为h

，那么，该树的结点数为 因此，对一般高为h的完全二叉树而言，其结点数 即： 因此 故（2）如果高为h的完全二叉树的每个分支结点的两个儿子结点中必有一个是叶子，那么它的结点数应是(h

1)

h，而对一般高为h的完全二叉树而言，其结 点数为 故

由⑴⑵可知，有n个结点的完全二叉树其树高h满足算法12.3二叉树的前序遍历（先根遍历）（1）访问二叉树的根r（先根、前序）；（2）如果r有左儿子，那么以前序遍历算法访问r的左子树（以r的左儿子为根的子树）；（3）如果r有右儿子，那么以前序遍历算法访问r的右子树（以r的右儿子为根的子树）。算法12.4二叉树的中序遍历（中根遍历）（1）如果二叉树树根r有左儿子，那么以中序遍历算法访问r的左子树（以r的左儿子为根的子树）；（2）访问二叉树的根r（中根、中序）；（3）如果r有右儿子，那么以中序遍历算法访问r的右子树（以r的右儿子为根的子树）。算法12.5二叉树的后序遍历（后根遍历）（1）如果二叉树树根r有左儿子，那么以后序遍历算法访问r的左子树（以r的左儿子为根的子树）；（2）如果r有右儿子，那么以后序遍历算法访问r的右子树（以r的右儿子为根的子树）；（3）访问二叉树的根r（后根、后序）；【例12.4】请用前序、中序和后序遍历算法遍历图中所示的二叉树。解： ⑴前序遍历结果：； ⑵中序遍历结果：； ⑶后序遍历结果：DBCAJHFKIG二叉树的遍历

E12.3.3应用举例 二叉树的第一个应用就是最优树。 定义12.11设二叉树T有t片叶子，分别带权为w1,w2,…,wt，则T称为带权二叉树。如果T中带权wi

的叶子，其通路长度为L(wi)，则称为带权二叉树T的权。在所有带权w1,w2,…,wt的T中，w(T)最小的那棵被称为最优树。

该定义可以从二叉树推广到m叉树。定义12.12具有t片叶子、带权w1,w2,…,wt

的m叉树中，带权最小的m叉树称为最优m叉树。在给出求最优树的算法之前，我们必须先证明下面的定理。定理12.12设T是带权的最优树，则： （1）带权,的叶子,是兄弟； （2）以,为儿子的分支点具有最长的通路长度。证明：设在带权,,…,的最优树中，v是通路长度最长的分枝点，v的儿子分别为wx

和wy，故有

L(wx)≥L(w1) L(wy)≥L(w2)

若有L(wx)＞L(w1)，将wx

与w1

对调，得到新树T’，则

w(T’)

w(T)＝(L(wx)·w1

L(w1)·wx)

(L(wx)·wx

L(w1)·w1)＝

L(wx)(w1

wx)

L(w1)(

wx

w1)＝(

wx

w1)(L(w1)

L(wx))＜0即

w(T’)＜w(T)

与T是最优树的假定矛盾。故 L(wx)＝

L(w1)同理可证 L(wy)＝

L(w2)因此 L(w1)＝

L(w2)＝

L(wx)＝

L(wy)分别将w1，w2

与wx，wy

对调，得到一棵最优树，其中带权w1

和w2

的树叶是兄弟。

定理12.13设T是带权的最优树。如果将带权w1,w2的叶子的父结点由分支点改为带权的叶子结点，得到一棵新树T，则T也是最优树。证明：根据题设，有 w(T)＝w(T’)

w1

w2

若T’不是最优树，则必有另外一棵带权为 w1

w2，w3，…，wt的最优树T”。 对T”中带权为w1

w2的树叶vw1

w2生成两个儿子，得到树，则

w()＝w(T”)

w1

w2

因为T”是带权为w1

w2，w3，…，wt

的最优树,

故 w(T”)≤w(T’)如果 w(T”)＜w(T’) 则 w()＜w(T)

与T是带权为w1，w2，…，wt

最优树矛盾，因此

w(T”)＝w(T’) T′一棵带权为w1

w2，w3，…，wt

的最优树。根据上述定理，1952年，D.A.Huffman

给出求最优二叉树的算法。根据上面两个定理，要画一棵带有t个权的最优树，可简化为画一棵带有t

1个权的最优树，而又可简化为画一棵带t

2个权的最优树，依此类推。具体的做法是：首先找出两个最小w值，设为w1

和w2，然后对t

1个权w1

w2,w3,…,wt求作一棵最优树，并且将这棵最优树的结点vw1

w2

分叉生成两个儿子v1

和v2，依此类推。23571113171923293137415571113171923293137411071113171923293137411711131719232931374117241719232931374124341923293137412434422931374134425331374142536537414253657895657895143

238【例12.5】设一组权2,3,5,7,11,13,17,19,23,29,31,37,41。求相应的最优树。解：求最优树的过程可描述为：最优树

二叉树的另一个应用是前缀码。在远距离通讯中，常常用0和1的字符串作为英文字母传送信息，因为英文字母共有26个，故用不等长的二进制序列表示26个英文字母时，由于长度为1的序列有2个，长度为2的二进制序列有2