第十二章 树 主要内容 无向树及其性质 生成树 根树及其应用.

Presentation on theme: "第十二章 树 主要内容 无向树及其性质 生成树 根树及其应用."— Presentation transcript:

1 第十二章 树 主要内容 无向树及其性质 生成树 根树及其应用

2 12.1 无向树及其性质 定义12.1 连通无回路的无向图称为无向树, 简称树. 每个连
f f f 12.1 无向树及其性质 定义12.1 连通无回路的无向图称为无向树, 简称树. 每个连 通分支都是树的无向图称为森林. 平凡图称为平凡树. 在无 向树中, 悬挂顶点称为树叶, 度数大于或等于2的顶点称为 分支点． 例 星形树

3 无向树的性质 定理12.1 设G=<V,E>是n阶m条边的无向图，则下面各命题 是等价的： (1) G 是树
(3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1. (5) G 是连通的且 G 中任何边均为桥. (6) G 中没有回路，但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.

4 证明 证 (1)(2). 若路径不惟一, 必有回路. (2)(3). 若G中有回路，则回路上任意两点之间的路径不
证 (1)(2). 若路径不惟一, 必有回路. (2)(3). 若G中有回路，则回路上任意两点之间的路径不 惟一. 对n用归纳法证明m=n1. 当n=1时成立. 设nk时成立，证n=k+1时也成立：任取 一条边e，Ge有且仅有两个连通分支G1,G2 . nik，由归 纳假设得mi=ni1, i=1,2. 于是， m=m1+m2+1=n1+n22+1=n1. (3)(4). 只需证明G连通. 用反证法. 否则G有s(s2)个连通 分支, 它们都是树. 于是, 有mi=ni1, 这与m=n1矛盾.

5 证明 (4)(5). 只需证明G 中每条边都是桥. 下述命题显然成立: G 是 n 阶 m 条边的无向连通图，则 mn1.
eE, Ge只有n2条边，由命题可知Ge不连通，故e为桥. (5)(6). 由(5)易知G为树. 由(1)(2)知，u,vV（uv）, u到v有惟一路径，加新边(u,v)得惟一的一个圈. (6)(1). 只需证明G连通，这是显然的.

6 无向树的性质 定理12.2 设T是n阶非平凡的无向树，则T 中至少有两片树叶. 证 设 T 有 x 片树叶，由握手定理及定理10.1可知，
全是树叶，试求树叶数，并画出满足要求的非同构的无向树. 解 设有x片树叶，n = 3+x. 2m = 2(n1) = 2(2+x) = 13+22+x 解出x = 3，故T有3片树叶.

7 例题 例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个.

8 12.2 生成树 定义12.2 如果无向图G的生成子图T是树，则称T是G的生成树. 设T是G的生成树，G的在T中的边称为T的树枝，不在T中的边为T的弦. 称T的所有弦的导出子图为T的余树，记作 . 例

9 生成树存在条件 定理12.3 无向图G有生成树当且仅当G连通.
证 必要性显然. 证充分性．若G中无回路，则G为自己的生成树．若G中含圈，任取一圈，随意地删除圈上的一条边; 若仍有圈, 再任取一个圈并删去这个圈上的一条边，重复进行, 直到最后无圈为止. 最后得到的图无圈（当然无回路）、连通且是G的生成子图，因而是G的生成树． 这个产生生成树的方法称为破圈法． 推论 G为n阶m条边的无向连通图，则mn1.

10 最小生成树 定义12.3 设无向连通带权图G=<V,E,W>，T是G的一棵生成
树，T的各边权之和称为T的权，记作W(T)．G的所有生成树 中权最小的生成树称为G的最小生成树. 避圈法（Kruskal） 输入: 连通图G=<V,E,W> 输出: G的最小生成树T 1. 将G中非环边按权从小到大排列: W(e1)W(e2) …W(em). 2. 令T{e1}, i2. 3. 若ei与T中的边不构成回路, 则令TT{ei}. 4. 若|T|<n-1, 则令ii+1, 转3.

11 实例 例4 求图的一棵最小生成树. W(T)=38

12 12.3 根树及其应用 定义12.4 若有向图的基图是无向树, 则称这个有向图为有向
12.3 根树及其应用 定义12.4 若有向图的基图是无向树, 则称这个有向图为有向 树. 一个顶点的入度为0、其余顶点的入度为1的有向树称为 根树．入度为0的顶点称为树根，入度为1出度为0的顶点称 为树叶，入度为1出度不为0的顶点称为内点，内点和树根统 称为分支点．从树根到顶点v的路径的长度(即, 路径中的边 数)称为v的层数. 所有顶点的最大层数称为树高． 根树的画法——树根放上方，省去所有有向边上的箭头 例

13 家族树与根树的分类 定义12.5 设T为一棵非平凡的根树, vi,vjV(T), 若vi可达vj，
则称vi为vj的祖先, vj为vi的后代; 若vi邻接到vj, 则称vi为vj的父 亲, vj为vi的儿子. 若vj,vk的父亲相同, 则称vj与vk是兄弟． 将根树T中层数相同的顶点都标定次序, 称T为有序树． 根树的分类： (1) 若T的每个分支点至多有r个儿子，则称T为r叉树. (2) 若T的每个分支点都恰好有r个儿子, 则称T为r叉正则树. (3) 若T是r叉正则树, 且所有树叶的层数相同, 则称T为r叉完 全正则树. 有序的r叉树, r叉正则树, r叉完全正则树分别称作 r叉有序树, r叉正则有序树, r叉完全正则有序树．

14 根子树与最优二叉树 定义12.6 设T为一棵根树, vV(T), 称v及其后代的导出子图 Tv为以v为根的根子树．
2叉正则有序树的每个分支点的两个儿子导出的根子树分 别称为该分支点的左子树和右子树． 定义12.7 设2叉树T 有t片树叶v1, v2, …, vt, 权分别为w1, w2,…, wt, 称 为T 的权, 其中li是vi 的层数. 在所有有t片树叶, 带权w1, w2, …, wt 的2叉树中, 权最小的2叉树称为最优2叉树.

15 Huffman算法 Huffman算法 输入: 实数w1, w2, …, wt 输出: 最优二叉树
1. 作t片树叶, 分别以w1, w2, …, wt为权. 2. 在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点, 添加一个新分支点, 它以这2个顶点为儿子, 其权等于这2个儿子的权之和. 3. 重复2, 直到只有1个入度为0的顶点为止. W(T)等于所有分支点的权之和.

16 实例 例 5 求权为2, 2, 3, 3, 5的最优树. 解 W(T)=34

17 前缀码 定义12.8 设12…n1n是长为n的符号串, 称其子串1, 12,
…, 12…n为该符号串的前缀. 设A={1,2,…,m}是一个符 号串集合, 若A的任意两个符号串都互不为前缀, 则称A为前 缀码. 由0-1符号串构成的前缀码称作二元前缀码． 例 {1, 00, 011, 0101, 01001, 01000}为前缀码． {1, 00, 011, 0101, 0100, 01001, 01000}不是前缀码．

18 前缀码的产生 用2叉树产生二元前缀码 例 一棵正则2叉树产生惟一的前缀码（按左枝标0，右枝标1） 1 01 11 000 0010 0011
1 01 11 000 0010 0011 1 01 10 000 0010 0011 1 01 11 000 0010 0011 10 一棵正则2叉树产生惟一的前缀码（按左枝标0，右枝标1）

19 最佳前缀码 设符号Ai在传输中出现的频率为pi, 二元前缀码的长为li, 1it, 传输m个符号需要m 个二进制位. 最小的二
元前缀码称作最佳前缀码.最佳前缀码可用Huffman算法计算 以频率为权的最优二叉树产生. 例6 设在通信中, 八进制数字出现的频率如下： 0：25% ：20% ：15% ：10% 4：10% ：10% ：5% ：5% 求传输它们的最佳前缀码, 并求传输10n (n2)个按上述比例 出现的八进制数字需要多少个二进制数字？若用等长的(长 为3)的码字传输需要多少个二进制数字？

20 实例 解 传输100个八进制数字中各数字出现的个数, 即以100乘各频率为: 25, 20, 15, 10, 10, 10, 5, 5, 以它们为权构造最优二叉树. 最佳前缀码 W(T)=285， 传输10n(n2)个八进制数字, 用最佳前缀码需2.8510n位， 用等长码需310n位.

21 有序树的行遍方式 行遍(周游)有序树——对每个顶点访问且仅访问一次. 对2叉有序正则树的周游方式：
① 中序行遍法. 访问次序为：左子树、根、右子树 ② 前序行遍法. 访问次序为：根、左子树、右子树 ③ 后序行遍法. 访问次序为：左子树、右子树、根 例 用中序, 前序, 后序行遍法访问的结果分别为： b a (f d g) c e， a b (c (d f g) e)， b ((f g d) e c) a

22 用2叉有序树存放算式 用2叉有序树表示含有2元运算和1元运算的算式: 每个分支点 放一个运算符, 其运算对象是以它的儿子为树根的子树所表
示的子算式. 规定运算对象的排列顺序, 如被除数、被减数放 在左边．所有的变量和常量都放在树叶上. 例 ((b+(c+d))a)((ef)(g+h)(ij)) 用中序行遍法访问还原算式

23 波兰符号法 波兰符号法(前缀符号法): 按前序行遍法访问存放算式的2叉 有序树, 且不加括号.
运算规则: 从右到左每个运算符号对其后面紧邻的两个或一 个对象进行运算. 如对上页的算式    b + c d a   e f  + g h  i j 逆波兰符号法(后缀符号法): 按后序行遍法访问,且不加括号. 运算规则:从左到右每个运算符对其前面紧邻的两个或一个 对象进行运算. 如对上页的算式 b c d + + a  e f  g h + i j    

24 第十二章 习题课 主要内容 无向树及其性质 生成树、最小生成树 根树及其分类、最优二叉树、最佳前缀码、波兰符号法、逆波兰符号法 基本要求
深刻理解无向树的定义及性质 熟练地求解无向树 准确地求出给定带权连通图的最小生成树 理解根树及其分类等概念 熟练掌握求最优二叉树及最佳前缀码的方法 掌握波兰符号法与逆波兰符号法

25 练习1 1. 无向树 T 有ni个i 度顶点，i=2, 3, …,k，其余顶点全是树叶，求T 的树叶数.
解得 解 用树的性质：边数 m=n1（n为阶数），及握手定理. 设有t片树叶,

26 练习2 2．设n阶非平凡的无向树T中，(T)  k，k  1. 证明T至少 有k片树叶. 证 设T有s片树叶，由于(T)  k，有
解得s  k.

27 练习3 3．设G为n 阶无向简单图，n5，证明G 或 中必含圈.
证一. 反证法. 否则G与 的各连通分支都是树. 设G与 的连通分支的顶点数和边数分别为ni, mi(1is)与 (1jt). 于是 整理得 n25n+4  0 解得 1  n  4 与n  5矛盾

28 练习3 证二. 在G与 中有一个(不妨设为G)边数 若G是森林, 则mn-1, 矛盾.

29 练习4 4．画出基图为图所示无向树的所有非同构的根树
解 以a, b, c, d为根的根树同构, 选a为根, 如(1); 以 e, g 为根的根树同构，取 g为根，如(2)； 以 f 为根，如(3) . (1) (2) (3)

30 练习5 5．设T 是正则2叉树，T 有t 片树叶，证明T的阶数 n=2t1. 证一. 利用正则2叉树的定义及树的性质直接证明.
证一. 利用正则2叉树的定义及树的性质直接证明. (1) n = t+i (i为分支点数) (2) n = m+1 （m为T的边数） (3) m = 2i （正则2叉树定义） 由(2)、(3)得 ，代入（1）得n = 2t1. 证二. 利用握手定理及树的性质证. T的树根为2度顶点，所有内点为3度顶点，叶为1度顶点，有 (1) 2m = 2+3(i1)+t (2) m+1 = n = i+t 由(1) 和(2) 可解得 n = 2t1.