Copyright © 《离散数学》精品课程小组 离 散 数 学 Discrete Mathematics 计算机与信息科学系 Department of Computer and Information Science Copyright © 《离散数学》精品课程小组

16.1 无向树及其性质 16.2 生成树 16.3 根树及其应用 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.1 无向树及其性质 定义16.1 连通无回路的无向图称为无向树, 或简称树, 常用T表示树(Tree);平凡图称为平凡树;若无向图G至少有两个连通分支, 每个连通都是树, 则称G为森林(Forest); 在无向图中, 悬挂顶点称为树叶(Leaf); 度数大于或等于2的顶点称为分支点(Node) 无向树有许多性质, 它们是树的充要条件, 因此它们都可看作是树的定义。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.1 无向树及其性质 （证明如下） 定理16.1 设G = <V, E>是n阶m条边的无向图, 则下面各命题是等价的: (3) G中无回路, 且m = n-1 (4) G是连通的, 且m = n-1 (5) G是连通的, 且G中任何边均为桥 (6) G中没有回路, 但在任何两个不同的顶点之间加一条新边, 在所得图中得到唯一一个含新边的圈 （证明如下） 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

由G的连通性和定理14.5的推论可知: u,vV, u与v之间存在路径。 （接）证：(1)  (2) 由G的连通性和定理14.5的推论可知: u,vV, u与v之间存在路径。 若路径不是唯一的, 设1与2都是u到v的路径。 显然必存在由1和2上边构成的回路, 这就与G中无回路矛盾。 (2)  (3) 先证明: G中无回路。 若G中存在关联某顶点v的环, 则v到v存在长为0和1的两条路经, 这与已知矛盾。 若G中存在长度大于或等于2的圈, 则圈上任何两个顶点之间都存在两条不同的路径, 这与已知条件矛盾。 （续） 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

设e = (u, v)为G中的一条边, 由于G中无回路, 所以, G-e有两个连通分支G1和G2。 （接） 下面用归纳法证明: m = n-1。 1) n = 1时, G为平凡图, 结论显然成立。 2) 设n  k(k  1)时, 结论成立。 3) 当n = k+1时 设e = (u, v)为G中的一条边, 由于G中无回路, 所以, G-e有两个连通分支G1和G2。 设ni和mi分别为Gi中的顶点数和边数, 则ni  k(i = 1, 2)。 由归纳假设可知: mi = ni-1, 于是, m=m1+m2+1=n1+n2+1-2=n-1。 (3)  (4) 假设: G不是连通的。 设G由s(s  2)个连通分支G1, G2, …, Gs, Gi中均无回路, 因此, Gi全为树(i=1..s)。 （续） 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

于是, m = i=1..smi = i=1..sni - s = n - s。 由于s  2, 这显然与条件“m=n-1”相矛盾。 （接） 由(1)(2)(3)可知: mi = ni-1。 于是, m = i=1..smi = i=1..sni - s = n - s。 由于s  2, 这显然与条件“m=n-1”相矛盾。 所以, G是连通的。 (4)  (5) 证明G中每条边均为桥, eE, 均有: E(G-e) = n-1-1 = n-2。 由“n阶m条边的无向连通图, 则m  n-1”可知: G-e不是连通图, 故e为桥。 （续） 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

由(1)(2)可知: u,vV且u  v, 则u与v之间存在唯一的路径, 则∪(u,v)为G中的圈, 显然该圈是唯一的。 （接）（5)  (6) 由于G中每条边均为桥, 因此, G中无圈。 又由于G连通, 所以, G为树。 由(1)(2)可知: u,vV且u  v, 则u与v之间存在唯一的路径, 则∪(u,v)为G中的圈, 显然该圈是唯一的。 (6)  (1) 证明: G是连通的。 u, vV且u  v, 则(u,v)∪G产生唯一的圈, 显然, 有C - (u,v)为G中u到v的通路, 故, u ~ v。 由“u和v的任意性”可知: G是连通的。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.1 无向树及其性质 定理16.2 设T是n阶非平凡的无向树, 则T中至少有两个叶结点。 证：设: T有x个叶结点。 由握手定理和定理16.1可知: 2(n-1) = i=1..nd(vi)  x+2(n-x) = 2n-x 由上式可解出: x  2。 以上定理给出了无向树的主要性质, 利用这些性质和握手定理, 可以画出阶数比较小的所有非同构的无向树。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.1 无向树及其性质 例16.1 画出6阶所有非同构的无向树。 解：设Ti是6阶无向树。 由定理16.1可知: Ti的边数mi = 5。 例16.1 画出6阶所有非同构的无向树。 解：设Ti是6阶无向树。 由定理16.1可知: Ti的边数mi = 5。 由握手定理可知: j=1..6dTi(vj) =10, 且(Ti)  1, (Ti)  5. 于是, Ti的度数列必为以下情况之一: (1) 1, 1, 1, 1, 1, 5 (2) 1, 1, 1, 1, 2, 4 (3) 1, 1, 1, 1, 3, 3 (4) 1, 1, 1, 2, 2, 3 (5) 1, 1, 2, 2, 2, 2 显然, (4)对应两棵非同构的树, 在一棵树中两个2度顶点相邻, 在另一棵树中不相邻, 其他情况均能画出一棵非同构的树。（续） 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

我们称只有一个分支点, 且分支点的度数为n-1的n (n  3)阶无向树为星形图, 称其唯一分支点为星心。 （接） (1), (2)和(3)分别对应树T1, T2和T3; (4)对应树T4和T5; (5)对应T6。 我们称只有一个分支点, 且分支点的度数为n-1的n (n  3)阶无向树为星形图, 称其唯一分支点为星心。 上图T1是6阶星形图。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

例16.2 7阶无向图有3个叶结点和1个3度顶点, 其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。 例16.2 7阶无向图有3个叶结点和1个3度顶点, 其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。 解：设Ti为满足要求的无向树, 则边数mi=6。 不妨假设: 结点v1, v2和v3是叶结点, v7是3度结点, v4, v5和v6是待定结点。 于是j=1..7d(vj) = 12 = 3+3+d(v4)+d(v5)+d(v6)。 由于1  d(vj)  6, 且d(vj)  1和d(vj)  3可知: d(vj) = 2 (j = 4, 5, 6)。 于是Ti的度数列为: 1, 1, 1, 2, 2, 2, 3。 由度数列可知: Ti中有一个3度顶点v7, v7的邻域N(v7)中有3个顶点, 这3个顶点的度数列只能是下列三种之一: (1, 1, 2), (1, 2, 2), (2, 2, 2) 此度数列只能产生这三棵非同构的7阶无向树, 依次对应右图中的树T1, T2和T3。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 定义16.2 设树T是无向图G的子图, 则称T为G的树;若树T是G的生成子图, 则称T是G的生成树(Spanning Tree);设T是G的生成树, eE(G), 若eE(T), 则称e为T的树枝, 否则, 称e为T的弦;称导出子图G[E(G)-E(T)]为余树, 记作T; 注意: T的余树没有什么特点。在下图中, 实边图为该图的一棵生成树T, 虚线部分是构成T的余树。它不连通, 但含回路。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 定理16.3 无向图G具有生成树, 当且仅当G是连通图。 证： 1) 必要性 由“生成树的定义”可知: 图G是连通图。 2) 充分性。 若G中无回路, G为自己的生成树。 若G中含圈, 任取一圈, 任意删除圈上的一条边, 若还有圈, 再删除圈上的一条边, 直到剩下的图无圈为止。 显然, 最后所得的图G’无圈、连通且为G的生成子图。 所以, 图G’就是G的生成树。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 推论1 设G为n阶m条边的无向连通图, 则m  n-1。 证： 由定理16.3可知: G有生成树。 　 设T为G的一棵生成树, 则 m = |E(G)|  |E(T)| = n-1。 推论2 设G是n阶m条边的无向连通图, T为G的生成树, 则T的余树中含有m-n+1条边。 （可由推论1获得。） 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 推论3 设T是连通图G的一棵生成树, T为T的余树, C为G中任意一个圈, 则E(T)∩E(C)  。 证： 若E(T)∩E(C) = , 则E(C)  E(T), 这说明C为T中圈。 　 这显然与“T是树”相矛盾。 定理16.4 设T为无向连通图G中一棵生成树, e为T的任意一条弦, 则T∪e中一定存在圈, 且该圈含弦e, 其余边均在T中。 证：设: e = (u, v)。 由定理16.1可知: 在T中, u和v之间存在唯一的路径(u,v), 则(u,v)∪e就是一个满足要求圈。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 由定理16.4, 可以得出下面的定义。 定义16.3 设T是n阶m条边的无向连通图G的一棵生成树, e’1, e’2, …, e’m-n+1为T的弦, Cr为T添加弦e’r产生的圈, 该圈含弦e’r, 其余边均在树T中, 称Cr为G对应T的弦e’r的基本回路或基本圈(r=1..m-n+1);称{ C1, C2, …, Cm-n+1 }为G对应T的基本回路系统, 称m-n+1为G的圈秩, 记作(G) [读: Sai]。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 在右图中, 生成树T的弦分别为e6, e7, e8, e10和e11。 假设这些弦所对应的基本回路分别为C1, C2, C3, C4和C5。 从弦开始, 按顺时针顺序写出的回路分别为: C1 = e6e4e5, C2 = e7e2e1, C3 = e8e9e2e1 　C4 = e10e3e5e2, C5 = e11e3e5e2e9 因此, 该图的圈秩为5, 基本回路系统为 { C1, C2, C3, C4, C5 }。 由此不难看出: 无向连通图G的圈秩与生成树的选取无关, 但不同生成树所对应的基本回路系统可能不同。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 定理16.5 设T是连通图G的一棵生成树, e为T的树枝, 则G中存在只含树枝e, 其余边都是弦的割集, 且不同的树枝对应的不同割集。 证：由定理16.1可知: e是T的桥。 假设: T-e有两个连通分支T1和T2。 令Se = { e | eE(G), e = (vi, vj), viV(T1)和vjV(T2) }。 由构造可知: Se为G的割集, eSe且Se中除e外都是弦, 所以, 边集Se即为所求。 不同树枝对应的割集显然也是不同的。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 定义16.4 设T是n阶连通图G的一棵生成树, e’1, e’2, …, e’n-1为T的树枝, Si是G的只含树枝e’i的割集, 则称Si为G的对应生成树T由树枝e’i生成的基本割集(i=1..n-1)称{ S1, S2, …, Sn-1 }为G对应T的基本割集系统 称n-1为G的割集秩, 记作(G)[读: eitә] 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 在下图中, e1, e2, e3, e4, e5和e9为T的树枝。 令这些树枝所对应的基本割集分别为S1, S2, S3, S4, S5和S6。以树枝为第一个元素的割集如下：　S1 = { e1, e7, e8 } S2 = { e2, e7, e8, e10, e11 } 　S3 = { e3, e10, e11 } S4 = { e4, e6 } 　S5 = { e5, e6, e10, e11} S6 = { e9, e8, e11 } 基本割集系统为{ S1, S2, S3, S4, S5, S6 }。割集秩为6.连通图G的割集秩(G)不因生成树的不同而改变, 但不同生成树对应的基本割集系统可以不同。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 下面讨论求连通带权图中的最小生成树问题。 定义16.5 设无向连通带权图G = <V, E, W>, T是G的一棵生成树, T的各边权之和称为T的权, 记作W(T)。 G的所有生成树中, 权最小的生成树称为G的最小生成树(Minimal Spanning Tree)。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 求最小生成树有许多算法, Kruskal算法(克鲁斯卡尔算法)如下: 设n阶无向连通带权图G = <V, E, W>有m条边。 不妨设G中无环(否则, 可以将所有的环先删去), 将m条边按权从小到大顺序排序为: e1, e2, …, em。 取当前最小权的边e1, 然后, 依次检查剩下边, 若边ej与T中的边构成回路, 则在T中删去边ej。 当T中有n-1条边时, 算法终止。这是得到的T即为G的最小生成树。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.2 生成树 例16.3 用Kruskal算法求下面两个图中的最小生成树。 图(a)的最小生成树T1为下图(a), W(T1) = 6; 图(b)的最小生成树T2为下图(b), W(T2) = 12。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 若有向图D的基图是无向树, 则称D为有向树。在所有有向树中, 根树最重要, 下面我们只讨论根树。 定义16.6 设T是n(n  2)阶有向图, 若T中有一个顶点的入度为0, 其余的顶点的入度均为1, 则称T为根树(Rooted Tree);入度为0的顶点称为树根(Root);入度为1出度为0的顶点称为叶结点; 入度为1出度不为0的顶点称为内结点;内点和树根统称为分支点; 从树根到结点v路径的长度称为v的层数;层数最大值称为树高; 平凡树也可称为根树。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 在根树中, 由于各有向边的方向是一致的, 所以, 画根树时可省去各边上的箭头, 并将树根画在最上方。 在下图所示的根树T中, 有8个叶结点, 6个内结点, 7个分支点, 其树高为5(即: 叶结点u或v的层数处)。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 通常我们用将家族成员之间的关系来描述根树中的结点关系, 这种关系如下面定义所述。 定义16.7 设T为一棵非平凡的根树, u, vV(T), 若u  v, 则称u是v的祖先(Ascendant), v是u的后代(Descendant)，若边<u, v>E(T), 则称u是v的父亲(Parent), v为u的儿子(Child);若结点u和v的具有相同父亲, 则称u和u是兄弟(Sibling) 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 若将根树T中相同层数的顶点都标定次序, 则称T为有序树。 根据根树T中每个分支点儿子数和是否有序, 可将根树分成: (1) 若T的每个分支点至多有k个儿子, 则称T为k叉树;若k叉树是有序的, 则称它为k叉有序树; (2) 若T的每个分支点都恰好有k个儿子, 则称T为k叉正则树;若T是有序的, 则称它为k叉正则有序树; (3) 若T是k叉正则树, 且每个叶结点的层数均为树高, 则称T为k叉完全正则树;若T是有序的, 则称它为k叉完全正则有序树。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 定义16.8 设T为一棵根树, vV(T), 称v及其后代的导出子图Tv为T的以v为根的子树。 在二叉正则有序树中, 其每个分支点的两个儿子所导出的子树分别称为其左子树和右子树。 在所有的k叉树中, 二叉树最为重要。下面介绍一些二叉树的应用。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 定义16.9 设二叉树T有k个叶结点v1, v2, …, vk, 其权分别为w1, w2, …, wk, 称W(T)= i=1..kwi×L(vi)为T的权, 其中L(vi)是vi的层数; 在所有有k个叶结点、带权w1, w2, …, wk的二叉树中, 权最小的二叉树称为最优二叉树。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 下面三棵二叉树T1, T2和T3都是带权为2,2,3,3,5的二叉树。 根据树权W(T)的定义, 计算出它们的权分别为: 　　W(T1) = 2*2 + 2*2 + 3*3 + 5*3 + 3*2 = 38 　　W(T2) = 3*4 + 5*4 + 3*3 + 2*2 + 2*1 = 47 　　W(T3) = 3*3 + 3*3 + 5*2 + 2*2 + 2*2 = 36 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 对任意带权的二叉树, 如何求出其最优树是一个值得研究的问题。 下面介绍Huffman算法来解决该问题。 (1) 给定k个非负实数w1, w2, …, wk, 令S = { w1, w2, …, wk }; (2) 在S中选择两个最小的权wi和wj, 得一个分支点, 其权为wij = wi+wj; (3) 画线<wij, wi>和<wij, wi>; (4) 在S中删去权wi和wj, 然后再加入新的权wij; (5) 重复步骤(2) ~ (4), 直到S中只有一个权值为止。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 例16.4 求带权2,2,3,3,5的最优二叉树。 利用Huffman算法求解最优二叉树的全过程如下: 例16.4 求带权2,2,3,3,5的最优二叉树。 利用Huffman算法求解最优二叉树的全过程如下: 2,2,3,3,5 3,3,4,5 4,5,6 6,9 显然, 树(d)是最优树, W(T)=34。 由此可知: 右边三棵树都不是最优二叉树。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 在通信中, 用二进制编码表示符号。例如: 可用2位二进制编码00, 01, 10和11分别表示A, B, C和D, 称这种表示法为等长码表示法。 在传输过程中, 若A, B, C和D出现的频率大体相同, 用等长码表示是很好的方法, 但当它们出现的频率相差悬殊时, 为提高传输效率, 可寻找非等长的编码。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 定义16.10 设a1a2…an-1an是长度为n的符号串, 称其子串a1, a1a2, …, a1a2…an-1分别为该符号串的长度为1, 2, …, n-1的前缀; 设A = {b1, b2, …, bm}为一个符号串集合, 若对于bi, bjA, i  j, bi和bj互不为前缀, 则称A为前缀码; 若符号串bi(i=1..m)中只出现0和1 , 则称A为二元前缀码; 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 { 1, 00, 011, 0101, 01001, 01000 }为前缀码, { 1, 00, 011, 0101, 0100, 01001, 01000 }不是前缀码, 因为0100既是01001又是01000的前缀。 研究发现: 可用二叉树产生二元前缀码。 设T是具有k个叶结点的二叉树, v为T的分支点: 若v只有一个儿子, 则在连接v的边上可标0或1; 若v有两个儿子, 在连接v的左边上标0, 右边上标1; 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 设vi是T的一个叶结点, 从树根到vi的通路上各边的标号(0或1), 按通路上边的顺序组成的符号串放在vi处, 则k个叶结点处k个符号串组成的集合为二元前缀码。 由做法可知: 叶结点vi处符号串的前缀均在vi所在通路上的顶点处达到, 因此, 所得符号串集合必为前缀码。 若T是正则二叉树, 则由T产生的前缀码是唯一的。 定理16.6 由一棵给定的二叉正则树, 可以产生出唯一的一个二元前缀码。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 例16.5 求出下图两棵二叉树所产生的二元前缀码。 例16.5 求出下图两棵二叉树所产生的二元前缀码。 右图(a)为二叉树, 将连接每个分支点的两条边分别标上0和1, 见下左图(a)所示, 产生的前缀码为{ 11, 01, 000, 0010, 0011 }。 若将一个儿子的分支点引出的边标上0, 则产生前缀码为{ 10, 01, 000, 0010, 0011 }。 上右图(b)是二叉正则树, 它只能产生唯一的前缀码。标定后二叉正则树为下右图(b)所示, 前缀码为{ 01, 10, 11, 000, 0010, 0011 }。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 上面例子产生出来前缀码都可传输5个符号, 比如: A, B, C, D和E都不会传错, 但当这些字母出现频率不同时, 哪一个符号串传输哪个字母最省呢？ 我们可用符号出现的频率为权, 用Huffman算法求最优二叉树, 由最优二叉树产生的前缀码称为最佳前缀码, 用最佳前缀码传输对应的符号可使传输的二进制数位最省。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

用Huffman算法求最优树如右图(a)。 例16.6 在通信中, 八进制数字出现的频率如下: 　　0: 25%　1: 20%　2: 15%　3: 10% 　　4: 10%　5: 10%　6: 5%　 7: 5% 　　求传输它们的最佳前缀码, 并求传输10n(n  2)个按上述比例出现的八进制数字需要多少个二进制数字？若使用等长的(长为3)的码子传输需要多少个二进制数字？ 由题意可知: 8个权(乘100后)为w7=5, w6=5, w5=10, w4=10, w3=10, w2=15, w1=20, w0=25。 用Huffman算法求最优树如右图(a)。 图中矩形框中的符号串为对应数字的编码, 即可用编码01, 11, 001, 100, 101, 0001, 00000和00001来分别传输0, 1, 2, 3, 4, 5, 6和7。 8个编码的集合{ 01, 11, 001, 100, 101, 0001, 00000, 00001 }为前缀码, 且是最佳前缀码。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 设图(a)的树为T, 显然, W(T)为传输100个题中八进制数字所用二进制数字个数。 除用定义计算W(T)外, W(T)还可等于各分支点权之和, 所以, W(T) = 10+20+35+60+100+40+20 = 285。 由此可知: 传输100个题中八进制数字需要285个二进制位, 因此, 传输10n个题中八进制数字需要10n-2×285= 2.85 ×10n个二进制位。 用长度为3的0/1符号串传输10n个八进制数字(如: 000传0, 001传1, …, 111传7), 所以, 需用3×10n个二进制位。 由此可见: 用前缀码进行编码, 可提高传输效率。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 还有, 最佳前缀码不是唯一的。因为选择两个最小权的选法不唯一, 和两个权所对应的顶点放在左右位置也可不同, 画出的最优树当然也就不同, 但它们的权都是相等的, 即它们都是最优树。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 右图(b)所示的二叉正则树是本例的另一棵二叉树T’。 图中矩形框中的符号串为对应数字的编码, 即可用编码11, 01, 111, 001, 1000, 1001, 00000和00001来分别传输0, 1, 2, 3, 4, 5, 6和7。 W(T’) = 10+20+40+100+60+35+20 = 285 = W(T)。 所以, T’也是最优树。 按这个编码传输10n(n  2)个给定频率出现的八进制数字也需用2.85×10n个二进制位。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 后根遍历(左右根) 中根遍历(左根右) 先根遍历(根左右) 下面介绍对二叉树的遍历和应用。 对一棵根树的每个顶点都仅访问一次称为对树的遍历。 对二叉有序正则树主要有以下三种遍历方式: 　1）中序遍历(中根遍历)(Inorder)：访问树结点的次序为: 左子树、根、右子树 2）前序遍历(先根遍历)(Preorder)：访问树结点的次序为: 根、左子树、右子树 3）后序遍历(后根遍历)(Postorder)：访问树结点的次序为: 左子树、右子树、根 后根遍历(左右根) 4 5 2 6 3 1 中根遍历(左根右) 4 2 5 1 6 3 先根遍历(根左右) 1 2 4 5 3 6 6 4 5 2 3 1 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 对下图所示二叉有序正则树T, 按中序、前序、后序遍历的结果如下(下式中v表示v为子树的根): 中根遍历: ( ( h d i ) b e ) a ( f c g ) 先根遍历: a ( b ( d h i ) e ) ( c f g ) 后根遍历: ( ( h i d ) e b ) ( f g c ) a 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 二叉树的遍历操作在《数据结构》等课程中还会遇到, 可用递归方法来实现。 利用二叉有序正则树可表示四则运算的算式, 然后根据不同的访问方法得到不同的算法。 用二叉有序正则树存放算式时, 最高层次的运算符放在树根上, 然后依次将运算符放在根子树的树根上, 参与运算的数放在叶结点上, 并规定: 被除数、被减数放在左子树的叶结点上。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 例16.7 1) 用二叉有序正则树表示下面算式: 解 1) 表示算式的二叉树如右图所示。 例16.7 1) 用二叉有序正则树表示下面算式: ( a * ( b + c )+ d * e * f ) ÷ ( g + ( h - i) * j ) 2) 用3种遍历法访问(1)中的二叉树, 并写出遍历结果。 解 1) 表示算式的二叉树如右图所示。 中序遍历结果 ((a*(b+c))+d*(e*f)))÷(g+((h-i)*j)) 在上式中, 利用四则运算规则省去一些括号, 得到原算式, 所以, 中序遍历的结果还原了算式。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 前序遍历结果 ÷(+*a(+bc))(*d(*ef)))(+g(*(-hi)j)) 在上式中, 规定: 每个运算符与它后面紧邻的数进行运算, 其运算结果也是正确的。 我们称运算符在运算数前面的表示法为前缀符号(Prefix Notation)或波兰符号法(Polish Notation)。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用 后序遍历结果: ((a(bc+)*)(d(ef*)*)+)(g((hi-)j*)+)÷ 在上式中, 规定: 每个运算符与它前面紧邻的数进行运算, 其运算结果也是正确的。 我们称运算符在运算数后面的表示法为后缀符号法(Postfix Notation)或逆波兰符号法(Reverse Polish Notation)。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组