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。试画出满足要求的所有非同构的无向树。
例阶无向图有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 根树及其应用定义设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, }为前缀码, { 1, 00, 011, 0101, 0100, 01001, }不是前缀码, 因为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, }为前缀码, 且是最佳前缀码。 9/12/2017 9:39 PM 离散数学（第四部分图论） Copyright © 离散数学课程小组

16.3 根树及其应用设图(a)的树为T, 显然, W(T)为传输100个题中八进制数字所用二进制数字个数。
除用定义计算W(T)外, W(T)还可等于各分支点权之和, 所以, W(T) = = 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 根树及其应用右图(b)所示的二叉正则树是本例的另一棵二叉树T’。
图中矩形框中的符号串为对应数字的编码, 即可用编码11, 01, 111, 001, 1000, 1001, 00000和00001来分别传输0, 1, 2, 3, 4, 5, 6和7。 W(T’) = = 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) 表示算式的二叉树如右图所示。
例 ) 用二叉有序正则树表示下面算式: ( 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 © 离散数学课程小组

Copyright © 《离散数学》精品课程小组

Similar presentations

Presentation on theme: "Copyright © 《离散数学》精品课程小组"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

Copyright © 《离散数学》精品课程小组

Similar presentations

Presentation on theme: "Copyright © 《离散数学》精品课程小组"— Presentation transcript:

Similar presentations

About project

反馈