1、第16章 树,树是一类结构较为简单的图，用途极为广泛。特别是二叉树。 学习时应很好的掌握一些概念和算法，诸如，树的充要条件，树的各种算法等等。,学习要点,无向树及生成树 无向树的定义 (包括等价定义) 无向树的性质 生成树 定义，由连通图构造最小生成树的克鲁斯克尔算法。 根树及其应用 有向树及根树的定义， 家族树，有序树，r叉树的概念 最优二叉树的概念和哈夫曼算法，二叉树周游本章中所谈回路均指简单回路或初级回路,第十六章：树,第一节：无向树及其性质,无向树的定义,无向树,连通且不含回路的无向图。,平凡树,平凡图。,森林,例题,判断下面的图，是树，森林，还是平凡树？,树的等价定义,(1) G是连
2、通且不含回路，即G是树 (2) G中每一对顶点间有且仅有一条路径。 (3) G无回路且m=n-1 (4) G连通且m=n-1 (5) G连通，且G中任何边均为桥。 (6) G无回路，但增加一边后得到且仅得一个圈,树的性质,(2) 非平凡树至少2片树叶。,由握手定理，,例题,画出所有的6个顶点的非同构的树。,(1),(2),(3),(4),(5),例题,故这棵树有1个4度顶点。,例题,已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树.,解 解本题用树的性质m=n1，握手定理. 设有x片树叶，于是 n = 1+2+x = 3+x,2m = 2
3、(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(n1) = 51+21+31+4(n7) 解出n = 8，4度顶点为1个.,T的度数列为1, 1, 1, 1, 1, 2, 3, 4，共有
4、3棵非同构的无向树，如图所示.,例题,（2）,（3）,从而解出,无向树 T 有ni个i 度顶点，i=2, 3, ,k，其余顶点全是树叶，求T 的树叶数.,解 用树的性质：边数 m=n1（n为阶数），及握手定理. (1),例题,第十六章：树,第二节：生成树,生成树的定义,1、定义：设,是无向连通图，,是,的生成子图，若,是树，称,是,的生成树。,树枝,弦,余树,在,中的边，,不在,中的边，,的所有的弦的集合的导出子图。,例题,上图中，(2)是(1)的生成树，,(3)是(2)的余树。,注意：,(1) 生成树不唯一，,(2) 余树不一定是树。,生成树存在条件,定理：无向图G具有生成树当且仅当G是连通
5、图 证明:必要性 显然充分性，如果G无回路,则G本身就是它的生成树,如G有回路,则在回路上任取一条边并去掉后仍是连通的,如G仍有回路,则继续在该回路上去掉一条边,直到图中无回路为止,此时该图就是G的一棵生成树,已知连通图G,，求其生成树步骤。,生成树的性质,(1),至少有一棵生成树，,(3) 设,是,的生成树，,是,的余树，,则,中有,条边。,(4) 设,是,的生成树，,是,的余树，,C为G中任意一个圈，则E(T) E(C)不为空。,基本回路的存在,定理16.4 设T为G的生成树，e为T的任意一条弦，则Te中 含一个只有一条弦其余边均为T的树枝的圈. 不同的弦对应的 圈也不同. 证 设e=(u
6、,v)，在T中u到v有惟一路径 ，则 e为所求的圈.,基本回路系统,定义16.3 设T是n阶m条边的无向连通图G的一棵生成树，设 e1, e2, , emn+1为T 的弦. 设Cr为T 添加弦er 产生的只含弦 er、其余边均为树枝的圈. 称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
7、 中存在只含树枝e，其余边都是弦的割集，且不同的树枝对 应的割集也不同.证 由定理16.1可知，e是T的桥，因而Te有两个连通分支T1 和T2，令Se=e | eE(G)且 e 的两个端点分别属于V(T1)和V(T2)， 由构造显然可知Se为G的割集，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
8、 的基本割集系统，称n1为G的割 集秩，记作(G).,求基本割集的算法: 设e为生成树T 的树枝，Te为两棵小树T1与T2，令Se =e | eE(G)且e的两个端点分别属于T1与T2 则Se为e 对应的基本割集.,例题,解 弦e, f, g对应的基本回路分别为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.,下实线边所示为生成树，求基本回路系统与基本割集系统,最小生
9、成树,最小生成树, 各边权和最小的生成树。,Kruskal 避圈法,(2) 若,不与在 中的边构成回路，取,在,中，否则弃,，再查,，继续这一过程，直到形成树为止。,例题,求图的一棵最小生成树.,所求最小生成树如 图所示，W(T)=38.,例题,解：,解：,例题,解：,解：,例题,设有6个城市v1，v2，v6，它们之间有输油管连通，其布置如图所示，Si（数字）中Si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守？输油管道总长度越短，士兵越好防守。求他们看守管道的最短的总长度。,区别,第十六章
10、：树,第三节：根树及其应用,根树的定义,定义16.6 T是有向树（基图为无向树） (1) T 为根树T 中一个顶点入度为0，其余的入度均为1. (2) 树根入度为0的顶点 (3) 树叶入度为1，出度为0的顶点 (4) 内点入度为1，出度不为0的顶点 (5) 分支点树根与内点的总称 (6) 顶点v的层数从树根到v的通路长度 (7) 树高T 中层数最大顶点的层数 (8) 平凡根树平凡图,根树的定义,根树的顶点,根树实例,根树的画法树根放上方，省去所有有向边上的箭头,例,v1,v11,v12,v9,v6,v13,v7,v8,v4,v3,v2,v10,v5,图中v1是树根, v2, v4, v7, v
11、10是内点, v3, v5, v6, v8, v9, v11, v12 , v13是树叶。 习惯把有向树的根画在最上方,边的箭头全指向下,则可以省略全部箭头。上图树高为4。,v1,v11,v12,v9,v6,v13,v7,v8,v4,v3,v2,v10,v5,画出基图为图所示无向树的所有非同构的根树,练习,以a, b, c 或d为根的根树同构，选a为根，则根树如图(1); 以 e 与 g 为根的根树同构，取 g为根，则根树如图(2)； 以 f 为根，如图(3) 所示.,(1) (2) (3),家族树,定义16.7 T 为非平凡根树 (1) 祖先与后代 (2) 父亲与儿子 (3) 兄弟定义16.
12、8 设v为根树T中任意一顶点，称v及其后代的导出子 图为以v为根的根子树.,实例,v1,v11,v12,v9,v6,v13,v7,v8,v4,v3,v2,v10,v5,图中v1是v2的父亲， v2是v1的儿子, v2, v5, v6,构成的子图是T的子树且是真子树。 v1是v5的祖先，v5是v1的后代, v1有3个儿子分别是 v2, v3, v4,它们互为兄弟。,根树的分类,(1) T 为有序根树同层上顶点标定次序的根树 (2) 分类 r 叉树每个分支点至多有r 个儿子 r 叉有序树r 树是有序的 r 叉正则树每个分支点恰有r 个儿子 r 叉正则有序树 r 叉完全正则树树叶层数相同的r叉正则树
13、 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+w2. (2) 在w1+w2, w3, , wt 中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所
14、带的权. (3) 重复(2)，直到形成 t1个分支点，t片树叶为止.,例题,解：,例题,例 求带权为1, 1, 2, 3, 4, 5的最优树. 解题过程由图9给出，W(T)=38,例题,解：,求带权为2,3,5,7,8,9的最优2叉树T,解：,(2),(3),例题,最佳前缀码,最优2叉树的用途之一是求最佳前缀码。,在通讯中，我们常用0和1的符号串作为英文字母的传送信息，26个英文字母被使用的频率往往是不同的。为了使整个信息的长度尽可能短，自然希望用较短的符号串去表示使用频率高的英文字母，用较长的符号串表示使用频率低的英文字母。,为了使编码在使用中既快速又准确，可以用求最优2元树的Huffman
15、算法解决这个问题。,50,前缀码,定义16.10 设12n-1n是长度为 n 的符号串 (1) 前缀1, 12, , 12n1 (2) 前缀码1, 2, , m中任何两个元素互不为前缀 (3) 二元前缀码i (i=1, 2, , m) 中只出现两个符号，如0与1.,那么：00, 01, 100, 1010, 1011, 11111 abc, cba, bca, bac, acb, cab 1, 00, 011, 01001, 01000 是前缀码吗？,如何产生二元前缀码呢？,如： 0, 10, 110, 11111, 01, 001, 0001 等是(二元)前缀码 而 1,11,101,001
16、,0011 不是(二元)前缀码,前缀码,生成二元前缀码的方法,给定一棵2叉树T，设它有t片树叶。设v为T的一个分支点，则v至少有一个儿子，最多有两个儿子。若v有两个儿子，在由v引出的两条边上，左边的标上0，右边的标上1；若v有一个儿子，在由v引出的边上可标上0，也可标上1。设vi为T的任一片树叶，从树根到vi的通路上各边的标号组成的0，1串组成的符号串放在vi处，t片树叶处的t个符号串组成的集合为一个二元前缀码,由上面做法知，vi处的符号串的前缀均在vi所在的通路上除vi外的顶点处达到，因而所得符号串集合为二元前缀码。T为正则2叉树, 则由T产生的前缀码唯一,图所示二叉树产生的前缀码为 00,
17、 10, 11, 011, 0100, 0101 ,最佳前缀码,把各字符看作为树叶, 各字符出现的频率作为其相应的权, 利用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=
18、10, w4=10, w5=10, w6=15, w7=20, w8=25.,W(T)=285，传10n(n2)个用二进制数字需2.8510n个， 用等长码需310n个数字.,01-0 11-1 001-2 100-3101-4 0001-5 00000-6 00001-7,波兰符号法与逆波兰符号法,行遍或周游根树T对T的每个顶点访问且仅访问一次. 对2叉有序正则树的周游方式： 中序行遍法次序为：左子树、根、右子树 前序行遍法次序为：根、左子树、右子树 后序行遍法次序为：左子树、右子树、根,对图所示根树按中序、前序、 后序行遍法访问结果分别为：b a (f d g) c e， a b (c (
19、d f g) e)， b (f g d) e c) a,用2叉有序正则树存放算式,存放规则 最高层次运算放在树根 后依次将运算符放在根子树的根上 数放在树叶上 规定：被除数、被减数放在左子树树叶上,算式 (b+(c+d)a)(ef)(g+h)(ij) 存放在图所示2叉树上.,波兰符号法,波兰符号法 按前序行遍法访问存放算式的2叉有序正则树，其结果不加 括号，规定从右到左每个运算符号与其后面紧邻两个数进行运算，运算结果正确. 称此算法为波兰符号法或前缀符号法. 对上图的 访问结果为 b + c d a e f + g h i j 逆波兰符号法 按后序行遍法访问，规定从左到右每个运算符与前面紧邻两数运算，称为逆波兰符号法或后缀符号法. 对上图的访问结果为b c d + + a e f g h + i j ,
