第第9章章 树树 n9.1 无向树及生成树无向树及生成树n9.2 根树及其应用根树及其应用 19.1 无向树及生成树无向树及生成树 无向树、森林无向树、森林树枝、弦、余树树枝、弦、余树生成树生成树基本回路与基本回路系统基本回路与基本回路系统基本割集与基本割集系统基本割集与基本割集系统最小生成树最小生成树 2无向树的定义无向树无向树: 连通无回路的无向图连通无回路的无向图平凡树平凡树: 平凡图平凡图森林森林: 每个连通分支都是树的非连通的无向图每个连通分支都是树的非连通的无向图树叶树叶: 树中度数为树中度数为1的顶点的顶点分支点分支点: 树中度数树中度数 2的顶点的顶点例如例如(a)(b)3无向树的性质无向树的性质定定理理 设设G=是是n阶阶m条条边边的的无无向向图图，则则下下面面各各命命题是等价的：题是等价的：（1）G是树是树(连通无回路连通无回路);（2）G中任意两个顶点之间存在惟一的路径中任意两个顶点之间存在惟一的路径;（3）G中无回路且中无回路且m=n 1;（4）G是连通的且是连通的且m=n 1;（5）G是连通的且是连通的且G中任何边均为桥中任何边均为桥;（6）G中没有回路中没有回路, 但在任何两个不同的顶点之间但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈加一条新边后所得图中有惟一的一个含新边的圈. 4无向树的性质无向树的性质( (续续) ) 定理定理 设设T 是是 n 阶非平凡的无向树，则阶非平凡的无向树，则T中至少中至少有两片树叶有两片树叶. 证证 设设T有有x片树叶，由握手定理及前一个定理可知，片树叶，由握手定理及前一个定理可知， 由上式解出由上式解出x 2.5例题例题例例1 已已知知无无向向树树T中中, 有有1个个3度度顶顶点点, 2个个2度度顶顶点点, 其其余余顶顶点点全全是是树树叶叶. 试试求求树树叶叶数数, 并并画画出出满满足足要要求求的的非非同同构构的的无无向向树树. 解解 用树的性质用树的性质m=n 1和握手定理和握手定理. 设有设有x片树叶，于是片树叶，于是 n=1+2+x=3+x, 2m=2(n 1)=2 (2+x)=1 3+2 2+x解出解出x=3，故，故T有有3片树叶片树叶. T的度数列为的度数列为1, 1, 1, 2, 2, 3 有有2棵非同构的无向树棵非同构的无向树, 如图所示如图所示6例题例题例例2 已已知知无无向向树树T有有5片片树树叶叶, 2度度与与3度度顶顶点点各各1个个, 其其余余顶顶点点的的度度数数均均为为4. 求求T的的阶阶数数n, 并并画画出出满满足足要要求求的的所所有有非非同同构构的无向树的无向树. 解解 设设T的的阶阶数数为为n, 则则边边数数为为n 1, 4度度顶顶点点的的个个数数为为n 7. 由由握手定理得握手定理得 2m=2(n 1)=5 1+2 1+3 1+4(n 7)解出解出n=8, 4度顶点为度顶点为1个个. T的度数列为的度数列为1,1,1,1,1,2,3,4 有有3棵非同构的无向树棵非同构的无向树 7生成树生成树 设设G为无向连通图为无向连通图G的的生成树生成树: G的生成子图并且是树的生成子图并且是树生成树生成树T的的树枝树枝: G在在T中的边中的边生成树生成树T的的弦弦: G不在不在T中的边中的边生成树生成树T的的余树余树 : 所有弦的集合的导出子图所有弦的集合的导出子图注意：注意： 不一定连通不一定连通, 也不一定不含回路也不一定不含回路. 右图黑边构成生成树右图黑边构成生成树红边构成余树红边构成余树8生成树的存在性生成树的存在性 定理定理 任何无向连通图都有生成树任何无向连通图都有生成树.证证 用破圈法用破圈法. 若图中无圈若图中无圈, 则图本身就是自己的生成树则图本身就是自己的生成树. 否则删去圈上的任一条边否则删去圈上的任一条边, 这不破坏连通性这不破坏连通性, 重复进行重复进行 直到无圈为止直到无圈为止,剩下的图是一棵生成树剩下的图是一棵生成树.推论推论1 设设n阶阶无向连通图有无向连通图有m条边条边, 则则m n 1. 推论推论2 设设n阶无向连通图有阶无向连通图有m条边条边, 则它的生成树的余树则它的生成树的余树 有有m n+1条边条边. 推论推论3 设设 为为G的生成树的生成树 T 的余树，的余树，C 为为G 中任意一个中任意一个 圈，则圈，则C与与 一定有公共边一定有公共边. 9基本回路与基本回路系统定定义义9.3 设设G是是n阶阶m条条边边的的无无向向连连通通图图, T是是G的的一一棵棵生生成成树树, e1, e2, , em n+1为为T的的弦弦. G中中仅仅含含T的的一一条条弦弦er的的圈圈Cr称称作作对对应应弦弦er的的基基本本回回路路. 称称C1,C2, , Cm n+1为对应为对应T的的基本回路系统基本回路系统例例3 图中红边为一棵生成树图中红边为一棵生成树, ,对应它的基本回路系统为对应它的基本回路系统为bce, fae, gaed 10对应它的基本割集系统为对应它的基本割集系统为基本割集与基本割集系统定定义义9.4 设设T是是n阶阶连连通通图图G的的一一棵棵生生成成树树, e1 , e2 , , e n 1为为T的树枝，的树枝，Si是是G的只含树枝的只含树枝ei , 其他边都是弦其他边都是弦的割集的割集, 称称Si为为对对应应树树枝枝ei 的的基基本本割割集集. 称称S1, S2, , Sn 1为为对对应应T的的基本割集系统基本割集系统例例4 图中红边为一棵生成树图中红边为一棵生成树, ,a,f,g, e,b,f,g, c,b, d,g11无向图与最小生成树无向图与最小生成树 对对无向图或有向图的每一条边无向图或有向图的每一条边e附加一个实数附加一个实数w(e), 称作称作边边e的权的权. 图连同附加在边上的权称作图连同附加在边上的权称作带权图带权图, 记作记作G=. 设设T是是G的生成树的生成树, T所有边的权的和称作所有边的权的和称作T的的权权, 记作记作W(T). 最小生成树最小生成树: 带权图权最小的生成树带权图权最小的生成树求最小生成树的算法求最小生成树的算法避圈法避圈法 (Kruskal)设设G=, 将将非环边按权从小到大排序：非环边按权从小到大排序：e1, e2, , em.(1) 取取e1在在T中中(2) 检检查查e2, 若若e2与与e1不不构构成成回回路路, 则则将将e2加加入入T中中, 否否则则弃弃去去e2.(3) 检查检查e3, 重复进行直至得到生成树为止重复进行直至得到生成树为止. 12实例实例例例 求图的一棵最小生成树求图的一棵最小生成树 W(T)=38139.2 根树及其应用根树及其应用有向树有向树根树、树根、树叶、内点、分支点根树、树根、树叶、内点、分支点家族树、根子树、有序树家族树、根子树、有序树r元树（元树（r元有序树）元有序树）r元正则树（元正则树（r元有序正则树）元有序正则树）r元完全正则树（元完全正则树（r元有序完全正则树）元有序完全正则树）最优最优2元树与元树与Huffman算法算法前缀码与最佳前缀码前缀码与最佳前缀码中序行遍法、前序行遍法、后序行遍法中序行遍法、前序行遍法、后序行遍法波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法 14有向树与根树的定义有向树与根树的定义 有向树有向树: 基图为无向树的有向图基图为无向树的有向图根树根树: 有一个顶点入度为有一个顶点入度为0, 其余的入度均为其余的入度均为1的的 非平凡的有向树非平凡的有向树树根树根: 有向树中入度为有向树中入度为0的顶点的顶点树叶树叶: 有向树中入度为有向树中入度为1, 出度为出度为0的顶点的顶点内点内点: 有向树中入度为有向树中入度为1, 出度大于出度大于0的顶点的顶点分支点分支点: 树根与内点的总称树根与内点的总称顶点顶点v的层数的层数: 从树根到从树根到v的通路长度的通路长度树高树高: 有向树中顶点的最大层数有向树中顶点的最大层数15实例根树的画法根树的画法: :树根放上方树根放上方, ,省去所有有向边上的箭头省去所有有向边上的箭头右图中右图中 a是树根是树根 b,e,f,h,i是树叶是树叶 c,d,g是内点是内点 a,c,d,g是分支点是分支点 a为为0层层;1层有层有b,c; 2层有层有d,e,f; 3层有层有g,h; 4层有层有i. 树高为树高为416家族树家族树定义定义 把根树看作一棵把根树看作一棵家族树家族树:(1) 若顶点若顶点 a 邻接到顶点邻接到顶点 b, 则称则称 b 是是 a 的的儿子儿子, a 是是 b 的的父亲父亲;(2) 若若b和和c为同一个顶点的儿子为同一个顶点的儿子, 则称则称b和和c是是兄弟兄弟;(3) 若若a b且且a可达可达b, 则称则称a是是b的的祖先祖先, b是是a的的后代后代.设设v为根树的一个顶点且不是树根为根树的一个顶点且不是树根, 称称v及其所有后及其所有后代的导出子图为以代的导出子图为以v为根的为根的根子树根子树. 17根树的分类根树的分类有序树有序树: 将根树同层上的顶点规定次序将根树同层上的顶点规定次序r元树元树:根树的每个分支点至多有根树的每个分支点至多有r个儿子个儿子r元正则树元正则树: 根树的每个分支点恰有根树的每个分支点恰有r个儿子个儿子r元完全正则树元完全正则树: 树叶层数相同的树叶层数相同的r元正则树元正则树r元有序树元有序树: 有序的有序的r元树元树r元正则有序树元正则有序树: 有序的有序的r元正则树元正则树r元完全正则有序树元完全正则有序树: 有序的有序的r元完全正则树元完全正则树18最优最优2元树元树 定义定义 设设2元树元树T有有t片树叶片树叶v1, v2, , vt, 树叶的权分树叶的权分别别 为为w1, w2, , wt, 称称 为为T的权的权, 其其中中 l(vi)是是vi的层数的层数. 在所有有在所有有t片树叶片树叶, 带权带权w1, w2, , wt 的的 2元树中元树中, 权最小的权最小的2元树称为元树称为最优最优 2元树元树.19求最优树求最优树 Huffman算法算法:给定实数给定实数w1, w2, , wt, 作作t片树叶片树叶, 分别以分别以w1, w2, , wt为权为权. 在在所所有有入入度度为为0的的顶顶点点(不不一一定定是是树树叶叶)中中选选出出两两个个权权最最小小的的顶顶点点, 添添加加一一个个新新分分支支点点, 以以这这2个个顶顶点为儿子点为儿子, 其权等于这其权等于这2个儿子的权之和个儿子的权之和. 重复重复, 直到只有直到只有1个入度为个入度为0 的顶点为止的顶点为止. W(T)等于所有分支点的权之和等于所有分支点的权之和20实例实例例例 求带权为求带权为1, 1, 2, 3, 4, 5的最优树的最优树. 解题过程由下图给出，解题过程由下图给出，W(T)=38 21前缀码前缀码 设设 = 1 2 n-1 n是长度为是长度为n的符号串的符号串 的的前缀前缀: 1 2 k , k=1,2,n-1 前前缀缀码码: 1, 2, , m, 其其中中 1, 2, , m为为非非空字符空字符串串, 且任何两个互不为前缀且任何两个互不为前缀2元前缀码元前缀码: 只出现两个符号只出现两个符号(如如0与与1)的前缀码的前缀码如如 0,10,110, 1111, 10,01,001,110是是2元前缀码元前缀码 0,10,010, 1010 不是前缀码不是前缀码22前缀码前缀码( (续续) )一棵一棵2元树产生一个二元前缀码元树产生一个二元前缀码:对对每每个个分分支支点点, 若若关关联联2条条边边, 则则给给左左边边标标0, 右右边边标标1; 若只关联若只关联1条边条边, 则可以给它标则可以给它标0(看作左边看作左边), 也可以也可以标标1(看作右边看作右边). 将从树根到每一片树叶的通路上标将从树根到每一片树叶的通路上标的数字组成的字符串的数字组成的字符串记在树叶处记在树叶处, 所得的字符所得的字符串构成一个前缀码串构成一个前缀码.如右图所示如右图所示23最佳前缀码最佳前缀码例例 在通信中，设八进制数字出现的频率如下：在通信中，设八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%采用采用2元前缀码元前缀码, 求传输数字最少的求传输数字最少的2元前缀码元前缀码 (称作称作最佳前最佳前缀码缀码), 并求传输并求传输10n(n 2)个按上述比例出现的八进制数字需个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的要多少个二进制数字？若用等长的 (长为长为3) 的码字传输需要的码字传输需要多少个二进制数字多少个二进制数字?解解 用用Huffman算法求以频率算法求以频率(乘以乘以100)为权的最优为权的最优2元树元树. 这这里里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最优最优2元树如图所示元树如图所示. 24 编码编码: 0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001传传100个按比例出现的八进制数字所需二进制数字的个数个按比例出现的八进制数字所需二进制数字的个数为为 W(T)=285.传传10n(n 2)个所用二进制数字的个数为个所用二进制数字的个数为2.85 10n, 而用等而用等长长码码(长为长为3)需要用需要用 3 10n个数字个数字. 25波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法 行遍行遍(周游周游)根树根树T : 对对T 的每个顶点访问且仅访问一次的每个顶点访问且仅访问一次. 行遍行遍2元有序正则树的方式：元有序正则树的方式： 中序行遍法中序行遍法: 左子树、根、右子树左子树、根、右子树 前序行遍法前序行遍法: 根、左子树、右子树根、左子树、右子树 后序行遍法后序行遍法: 左子树、右子树、根左子树、右子树、根 例如例如, 对图所示根树按中序、前序、对图所示根树按中序、前序、 后序行遍法访问结果分别为：后序行遍法访问结果分别为： b a (f d g) c e a b (c (d f g) e) b (f g d) e c) a带下划线的是带下划线的是(子子)树根树根, 一对括号内是一棵子树一对括号内是一棵子树 26波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法( (续续) )用用2元有序正则树表示算式元有序正则树表示算式: 最高层次运算放在树最高层次运算放在树根上根上, 然后依次将运算符放在根子树的根上然后依次将运算符放在根子树的根上, 数放数放在树叶上在树叶上, 规定被除数、被减数放在左子树树叶上规定被除数、被减数放在左子树树叶上.例如例如, 右图表示算式右图表示算式(b+(c+d) a) (e f) (g+h) (i j)27波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法( (续续) )波兰符号法波兰符号法(前缀符号法前缀符号法): 按前序行遍法访问表示按前序行遍法访问表示算式的算式的2元有序正则树元有序正则树, 其结果不加括号其结果不加括号, 规定每个规定每个运算符号与其后面紧邻两个数进行运算运算符号与其后面紧邻两个数进行运算. 例如例如, 对上页中树的访问结果为对上页中树的访问结果为 b + c d a e f + g h i j 逆波兰符号法逆波兰符号法(后缀符号法后缀符号法): 按后序行遍法访问按后序行遍法访问, 规定每个运算符与前面紧邻两数运算规定每个运算符与前面紧邻两数运算. 例如例如, 对上页中树的访问结果为对上页中树的访问结果为 b c d + + a e f g h + i j 28