离散下2010-16树树是一类结构较为简单的图用途极为广泛特别二叉树

1、第16章树树是一类结构较为简单的图，用途极为广泛。特别是二叉树。学习时应很好的掌握一些概念和算法，诸如，树的充要条件，树的各种算法等等。学习要点无向树及生成树无向树的定义 (包括等价定义)无向树的性质生成树定义，由连通图构造最小生成树的方法。根树及其应用有向树及根树的定义，家族树，有序树，r叉树的概念最优二叉树的概念和哈夫曼算法，二叉树周游本章中所谈回路均指简单回路或初级回路。第十六章：树 第一节：无向树及其性质第二节：生成树第三节：根树及其应用 无向树的定义无向树连通且不含回路的无向图。无向树简称树，常用表示。平凡树平凡图。森林 连通分支数大于等于2，且每个连通分支都是树的无向图。例题判断下

2、面的图，是树，森林，还是平凡树？fceadb(1)(2)(3)(4)树的等价定义定理：设，则以下命题等价。(1) G是连通且不含回路（简单回路）(树)(2)G中每一对顶点间有且仅有一条路径。(3)G无回路且m=n-1(4)G连通且m=n-1(5)G连通，且G中任何边均为桥。 (6)G无回路，但增加一边后得到且仅得一个圈证明思路(1)(2). 关键一步是, 若路径不惟一必有回路. (2)(3). 若G中有回路，则回路上任意两点之间的路径不惟一. 对n用归纳法证明m=n1. n=1正确. 设nk时成立，证n=k+1时成立：取G中边e，Ge有且仅有两个连通分支G1,G2(为什么?) . nik，由归

3、纳假设得mi=ni1, i=1,2. 于是，m=m1+m2+1=n1+n22+1=n1.(3)(4). 只需证明G连通. 用反证法. 否则G有s（s2）个连通，每个连通分支中均无回路分支都是小树. 于是有mi=ni1, ，这与m=n1矛盾. 证明思路(4)(5). 只需证明G 中每条边都是桥. 为此只需证明命题 “G 是 n 阶 m 条边的无向连通图，则 mn1”. eE, Ge只有n2条边，由命题可知Ge不连通，故e为桥. (5)(6). 由(5)易知G为树（连通且任何边为桥，无圈），由(1)(2)知，u,vV（uv）, u到v有惟一路径，加新边(u,v)得惟一的一个圈. (6)(1). 只

4、需证明G连通，这是显然的. 树的性质(1) 树中顶点数与边数的关系：。(2) 非平凡树至少2片树叶。证明：设为阶非平凡树，设有片树叶，则有个顶点度数大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片叶。例题画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(1)(2)(3)(4)(5)例题一棵树有7片叶，3个3度顶点，其余都是4度顶点，求4度顶点多少个？解：设有个4度顶点，则顶点数，边数，由握手定理，解得，故这棵树有1个4度顶点。例题已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，

5、并画出满足要求的非同构的无向树. 解 解本题用树的性质m=n1，握手定理. 设有x片树叶，于是 n = 1+2+x = 3+x, 2m = 2(n1) = 2(2+x) = 13+22+x解出x = 3，故T有3片树叶.T 的度数列应为 1, 1, 1, 2, 2, 3，易知3度顶点与1个2度顶点相邻与和2个2度顶点均相邻是非同构的，因而有2棵非同构的无向树T1, T2，如图所示. 已知无向树T有5片树叶，2度与3度顶点各1个，其余顶点的度数均为4，求T的阶数n，并画出满足要求的所有非同构的无向树. 例题解 设T的阶数为n, 则边数为n1，4度顶点的个数为n7. 由握手定理得 2m = 2(n

6、1) = 51+21+31+4(n7)解出n = 8，4度顶点为1个. T的度数列为1, 1, 1, 1, 1, 2, 3, 4，共有3棵非同构的无向树，如图所示.例题（2）（3）从而解出无向树 T 有ni个i 度顶点，i=2, 3, ,k，其余顶点全是树叶，求T 的树叶数. 解 用树的性质：边数 m=n1（n为阶数），及握手定理. (1) 设n阶非平凡的无向树T中，(T) k，k 1. 证明T至少 有k片树叶. 证 反证法. 否则，T至多有s片树叶，s k，下面利用握手定理及树的性质m = n1推出矛盾. 由于(T) k，故存在v0，d(v0) k. 于是，由此解出s k，这与s k矛盾.

7、证本题的方法有多种，请用分支点都是割点来证明.练习第十六章：树 第一节：无向树及其性质第二节：生成树第三节：根树及其应用 生成树的定义1、定义：设是无向连通图，是的生成子图，若是树，称是的生成树。树枝弦余树在中的边，不在中的边，的所有的弦的集合的导出子图。例题上图中，(2)是(1)的生成树，(3)是(2)的余树。注意：(1) 生成树不唯一，(2) 余树不一定是树。生成树存在条件定理：无向图G具有生成树当且仅当G是连通图。证明:必要性显然充分性，如果G无回路,则G本身就是它的生成树,如G有回路,则在回路上任取一条边并去掉后仍是连通的,如G仍有回路,则继续在该回路上去掉一条边,直到图中无回路为止,

8、此时该图就是G的一棵生成树已知连通图，求其生成树步骤。生成树的性质设为连通图，(1)至少有一棵生成树，(2)，(3) 设是的生成树，是的余树，则中有条边。(4) 设是的生成树，是的余树，C为G中任意一个圈，则E(T) E(C)不为空。基本回路系统定理16.4 设T为G的生成树，e为T的任意一条弦，则Te中含一个只有一条弦其余边均为T的树枝的圈. 不同的弦对应的圈也不同. 证 设e=(u,v)，在T中u到v有惟一路径，则e为所求的圈. 定义16.3 设T是n阶m条边的无向连通图G的一棵生成树，设e1, e2, , emn+1为T 的弦. 设Cr为T 添加弦er 产生的只含弦er、其余边均为树枝的

9、圈. 称Cr为G的对应树T 的弦er的基本回路或基本圈，r=1, 2, , mn+1. 并称C1, C2, ,Cmn+1为G对应T 的基本回路系统，称mn+1为G的圈秩，记作 (G). 求基本回路的算法：设弦e=(u,v)，先求T中u到v的路径uv，再并上弦e，即得对应e的基本回路. 基本割集的存在定理16.5 设T是连通图G的一棵生成树，e为T的树枝，则G中存在只含树枝e，其余边都是弦的割集，且不同的树枝对应的割集也不同.证 由定理16.1可知，e是T的桥，因而Te有两个连通分支T1和T2，令 Se=e | eE(G)且 e 的两个端点分别属于V(T1)和V(T2)，由构造显然可知Se为G的

10、割集，eSe且Se中除e外都是弦，所以Se为所求. 显然不同的树枝对应的割集不同. 基本割集与基本割集系统定义16.4 设T是n阶连通图G的一棵生成树，e1, e2, , en1为T 的树枝，Si是G的只含树枝ei的割集，则称Si为G的对应于生成树T由树枝ei生成的基本割集，i=1, 2, , n1. 并称S1,S2, , Sn1为G 对应T 的基本割集系统，称n1为G的割集秩，记作(G). 求基本割集的算法设e为生成树T 的树枝，Te为两棵小树T1与T2，令 Se =e | eE(G)且e的两个端点分别属于T1与T2 则Se为e 对应的基本割集. 例题解 弦e, f, g对应的基本回路分别为

11、 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基=Ce, Cf, Cg. 树枝a, b, c, d对应的基本割集分别为 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, S基=Sa, Sb, Sc, Sd. 下实线边所示为生成树，求基本回路系统与基本割集系统例题如左图中，树枝集是e1, e2,e3, e9,e6, e8，则对应于e1的基本割集是e1, e4对应于e2的基本割集是e2, e10 ,e5 , e4对应于e3的基本割集是e3, e5 , e10 对应于e9的基本割集是e9, e4 , e7 ,e5对应于e

12、6的基本割集是e6, e7 , e5 对应于e8的基本割集是e5, e8 e1e3e9e8e6e2e3e2e4e6e5e7e8e9e1e10最小生成树对于有向图或无向图的每条边附加一个实数，则称为边上的权，连同附加在各边上的实数称为带权图，记为。最小生成树各边权和最小的生成树。定义：设无向连通带权图，是的一棵生成树，各边带权之和称为的权，记作。Kruskal 避圈法设阶无向连通带权图中有条边，它们带的权分别为，不妨设，(1) 取在中 (非环，若为环，则弃)。(2) 若不与在中的边构成回路，取在中，否则弃，再查，继续这一过程，直到形成树为止。例题求图的一棵最小生成树.所求最小生成树如图所示，W(

13、T)=38.例题解：求以下连通图的最小生成树及。解：例题解：求以下连通图的最小生成树及。解：的最小生成树可能不唯一，但的不同最小生成树权的值一样。第十六章：树 第一节：无向树及其性质第二节：生成树第三节：根树及其应用 根树的定义定义16.6 T是有向树（基图为无向树）(1) T 为根树T 中一个顶点入度为0，其余的入度均为1.(2) 树根入度为0的顶点(3) 树叶入度为1，出度为0的顶点(4) 内点入度为1，出度不为0的顶点(5) 分支点树根与内点的总称(6) 顶点v的层数从树根到v的通路长度(7) 树高T 中层数最大顶点的层数(8) 平凡根树平凡图根树的定义根树的顶点树叶(入度为1，出度为0

14、)分支点树根(入度为0)内点(入度为1，出度大于0)根树实例根树的画法树根放上方，省去所有有向边上的箭头例v1v11v12v9v6v13v7v8v4v3v2v10v5图中v1是树根, v2, v4, v7, v10是内点, v3, v5, v6, v8, v9, v11, v12 , v13是树叶。习惯把有向树的根画在最上方,边的箭头全指向下,则可以省略全部箭头。上图树高为4。v1v11v12v9v6v13v7v8v4v3v2v10v5画出基图为图所示无向树的所有非同构的根树 练习以a, b, c 或d为根的根树同构，选a为根，则根树如图(1); 以 e 与 g 为根的根树同构，取 g为根，则

15、根树如图(2)； 以 f 为根，如图(3) 所示. (1) (2) (3) 家族树定义16.7 T 为非平凡根树(1) 祖先与后代(2) 父亲与儿子(3) 兄弟定义16.8 设v为根树T中任意一顶点，称v及其后代的导出子图为以v为根的根子树.实例v1v11v12v9v6v13v7v8v4v3v2v10v5图中v1是v2的父亲， v2是v1的儿子, v2, v5, v6,构成的子图是T的子树且是真子树。 v1是v5的祖先，v5是v1的后裔, v1有3个儿子分别是 v2, v3, v4,他们互为兄弟。 根树的分类(1) T 为有序根树同层上顶点标定次序的根树(2) 分类 r 叉树每个分支点至多有r

16、 个儿子 r 叉有序树r 树是有序的 r 叉正则树每个分支点恰有r 个儿子 r 叉正则有序树 r 叉完全正则树树叶层数相同的r叉正则树 r 叉完全正则有序树实例2叉有序树2叉有序正则树2叉有序完全正则树最优二叉树定义16.9 设2叉树T 有t片树叶v1, v2, , vt，权分别为w1, w2, , wt，称 为T 的权，其中l(vi)是vi 的层数. 在所有有t片树叶，带权w1, w2, , wt 的2叉树中，权最小的2叉树称为最优2叉树. 求最优树的算法 Huffman算法给定实数w1, w2, , wt，且w1w2wt. (1) 连接权为w1, w2的两片树叶，得一个分支点，其权为w1+

17、w2.(2) 在w1+w2, w3, , wt 中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权. (3) 重复(2)，直到形成 t1个分支点，t片树叶为止. 例题解：下图中的树都是带权1，3，4，5，6求，。的2叉树例题例 求带权为1, 1, 2, 3, 4, 5的最优树. 解题过程由图9给出，W(T)=38例题求带权1,3,4,5,6的最优2叉树及。解：其实等于的各分支点的权之和，即最优树是不唯一的，但算法得到的树一定是最优树。求带权为2,3,5,7,8,9的最优2叉树T解：(2)(3)(4)有_片树叶。(5)有_个2度顶点，_个3度顶点，_个4度顶点。例题最佳

18、前缀码最优2叉树的用途之一是求最佳前缀码。在通讯中，我们常用0和1的符号串作为英文字母的传送信息，26个英文字母被使用的频率往往是不同的。为了使整个信息的长度尽可能短，自然希望用较短的符号串去表示使用频率高的英文字母，用较长的符号串表示使用频率低的英文字母。 为了使编码在使用中既快速又准确，可以用求最优2元树的Huffman算法解决这个问题。51前缀码定义16.10 设1, 2, , n-1, n是长度为 n 的符号串(1) 前缀1, 12, , 12n1 (2) 前缀码1, 2, , m中任何两个元素互不为前缀(3) 二元前缀码i (i=1, 2, , m) 中只出现两个符号，如0与1. 如

19、何产生二元前缀码？定理16.6 一棵2叉树产生一个二元前缀码.推论 一棵正则2叉树产生惟一的前缀码（按左子树标0，右子树标1）那么：00, 01, 100, 1010, 1011, 11111 abc, cba, bca, bac, acb, cab 1, 00, 011, 01001, 01000 是(二元)前缀码吗？如何产生二元前缀码呢？如： 0, 10, 110, 1111 1, 01, 001, 0001 等是(二元)前缀码而 1,11,101,001,0011 不是(二元)前缀码生成二元前缀码的方法给定一棵2叉树T，设它有t片树叶。设v为T的一个分支点，则v至少有一个儿子，最多有两个

20、儿子。若v有两个儿子，在由v引出的两条边上，左边的标上0，右边的标上1；若v有一个儿子，在由v引出的边上可标上0，也可标上1。设vi为T的任一片树叶，从树根到vi的通路上各边的标号组成的0，1串组成的符号串放在vi处，t片树叶处的t个符号串组成的集合为一个二元前缀码。由上面做法知， vi处的符号串的前缀均在vi所在的通路上除vi外的顶点处达到，因而所得符号串集合为二元前缀码。若T存在单子分支点，则由T产生的前缀码可能不唯一。T为正则2叉树, 则由T产生的前缀码唯一图所示二叉树产生的前缀码为 00, 10, 11, 011, 0100, 0101 最佳前缀码把各字符看作为树叶, 各字符出现的频率

21、(或n倍的频)作为其相应的权, 利用Huffman算法求出最优2叉树, 由此产生的前缀码即为最佳前缀码。在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%求传输它们的最佳前缀码，并求传输10n（n2）个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的（长为3）的码字传输需要多少个二进制数字？求最佳前缀码解 用100个八进制数字中各数字出现的个数，即以100乘各频率为权，并将各权由小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 用此权产

22、生的最优树如图所示. W(T)=285，传10n(n2)个用二进制数字需2.8510n个， 用等长码需310n个数字. 01-0 11-1 001-2 100-3 101-4 0001-500000-6 00001-7波兰符号法与逆波兰符号法行遍或周游根树T对T的每个顶点访问且仅访问一次. 对2叉有序正则树的周游方式： 中序行遍法次序为：左子树、根、右子树 前序行遍法次序为：根、左子树、右子树 后序行遍法次序为：左子树、右子树、根对图所示根树按中序、前序、后序行遍法访问结果分别为： b a (f d g) c e， a b (c (d f g) e)， b (f g d) e c) a用2叉有序正则树存放算式存放规则最高层次运算放在树根后依