离散数学-图论-树-课件

第16章树第16章树1

第十六章树一、无向树1）定义：连通无回路（初级回路或简单回路）的无向图称为无向树，或简称树常用T表示树，平凡图称为平凡树．若无向图G至少有两个连通分支，则称G为森林．在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支结点．2）树的等价定义设G＝<V，E>是n阶m条边的无向图，则下面各命题是等价的：

(1)G是连通无回路（树）．可通过循环证明

(2)G中任意两个顶点之间存在惟一的路径．（连通则存在路径，若不唯一，不同路径则构成回路）

(3)G中无回路且m=n-1．有长大于等于2的回路都与唯一路径矛盾。对结点进行归纳：n=1平凡图m=0=n-1；设n=k成立；n=k+1时两个结点有唯一的路，去掉则为两个连通分支（各自满足假设）

m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1

(4)G是连通的且m=n-1．

若不连通，对各个(s>=2)连通分支是树且有mi=ni-1m=n-ss>=2矛盾第十六章树2(5)G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的初级回路．(6)G是连通的，但删去任何一条边后，所得图不连通．

G连通：若存在二个结点无通路，则在二个结点添加边后不会出现回路3）树的性质对于给定的无向图—树是边数最小的连通图（m<n-1则不连通）树是边数最多的无回路图（m>n-1则有回路）结点的度：Σd(vi)=2m=2(n-1)

定理：设T是n阶非平凡的无向树，则T中至少有

片树叶

设：有x片树叶，其余结点度数至少为2

x+2(n-x)<=2(n-1)

例：无向树T中度为4、3、2的结点各一个，其余为树叶，树叶＝？

4+3+2+k=2(3+k-1)(5)G中没有回路，但在任何两个不同的顶点之间加一条新边，在34)阶数n比较小的所有非同构的无向树．例1：画出6阶所有非同构的无向树．

m=n-1=5从树的节点之和来分析：结点之和为10分配给6个结点

111115111124111133111223112222例2：7阶无向树中有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3．试画出满足要求的所有非同构的无向树．解答：从树的节点之和来分析：7阶无向树的边数m=（），于是∑d(vi)＝12＝3＋3+d(v5)+d(v6)+d(v7)

1112223加入2，2，2如何组成结点的度数序列使之不同构

主要分析：度为3的结点v与其三个邻接点的关系

邻接关系不同就能得到不同构的树三个邻接点度数：1121222224)阶数n比较小的所有非同构的无向树．4

4）任何无向连通图G，都存在生成树

无向连通图G的生成树是不唯一的

4）任何无向连通图G，都存在生成树

53、生成树的应用要建6个工厂，修建连接的通路（见图），为使5处都有路相通，至少要建几条路？如何铺设？由于n=6所以建5条路即可4、无向图G的生成树的确定：二种方法：1、破圈法：每次去掉回路中的一条边，去掉总数为m-n+1条弦

2、避圈法：由一个结点开始选一条边，逐渐添加与边关联的结点（只要不构成回路即可）

直到所有结点被添加，(挑选n-1条边）3、生成树的应用63、带权图的最小生成树

(1)定义5设无向连通带权图G＝<V，E，W>，T是G的一棵生成树．

T的各边权之和称为T的权，记作W(T)；

G的所有生成树中权最小的生成树称为G的最小生成树。(2)最小生成树的求法（这里介绍避圈法Kruskal算法)

设n阶无向连通带权圈G＝<V，E,W>有m条边，不妨设G中没有环(否则，可以将所有的环先删去)，将m条边按权从小到大顺序排列，设为e1,e2，…,em；

取e1在T中，然后依次检查e2，e3，…，em.若ej(j≥2)与已在T中的边不能构成回路，则取ej在T中，否则弃去ej；算法停止时得到的T为G的最小生成树。3、带权图的最小生成树7避圈法Kruskal算法(n-1次)1121241245(1)(2)(3)(4)避圈法Kruskal算法(n-1次)1121241245(18破圈法(1)512436(3)1245(2)12435破圈法(1)512436(3)1245(2)124359作业：P319习题十六1、2、3、4、5、13作业：10§16.3根树及其应用有向树：设D是有向图，若D的基图是无向树，

则称D为有向树.有向树中,根树最重要,故只讨论根树.一、根树

1、定义：设T是n(n≥2)阶有向树,若T中有一个顶点的入度为0,其余顶点的入度均为1,则称T为根树。入度为0的顶点称为树根（相当于文件系统的盘符）入度为1出度为0的顶点称为树叶（具体文件）。入度为1出度不为0的顶点称为内点（文件夹），内点和树根统称为分支结点§16.3根树及其应用11是否为根树(a)(b)(c)(no)(no)(yes)是否为根树(a)(b)(c)(no12从树根到T的任意顶点v的通路(路径)长度称为v的层数。v5的层数为

层。层数最大顶点的层数称为树高．将平凡树也称为根树。右图中树高为（）。v1v2v3v4v5v6v7v8v9v10在根树中，由于各有向边的方向是一致的，所以画根树时可以省去各边上的所有箭头，并将树根画在最上方．从树根到T的任意顶点v的通路(路径)长度称为v的层数。v5的132、根树中顶点的关系

定义：设T为一棵非平凡的根树，∀vi,vj∈V(T),若vi可达vj,则称vi为vj的祖先,vj为vi的后代；若vi邻接到vj(即<vi,vj>∈E(T)，称vi为vj的父亲,而vj为vi的儿子若vj,vk的父亲相同，则称vj与vk是兄弟v1v2v3v4v5v6v7v8v9v10v1为v5的祖先,v5为v1的后代；v2为v5的父亲,而v5为v2的儿子；v4与v5是兄弟2、根树中顶点的关系v1v2v3v4v5v6v7v8v9v1143、有序树设T为根树，若将T中层数相同的顶点都标定次序，则称T为有序树根据根树T中每个分支点儿子数以及是否有序，可以将根树分成下列各类：(1)若T的每个分支点至多有r个儿子，则称T为r叉树；又若r叉树是有序的，则称它为r叉有序树．

(2)若T的每个分支点都恰好有r个儿子，则称T为r叉正则树；又若T是有序的，则称它为r叉正则有序树．

(3)若T是r叉正则树，且每个树叶的层数均为树高，则称T为r叉完全正则树，又若T是有序的，则称它为r叉完全正则有序树。3、有序树15v1v2v3v4v5v6v7v8v9v10二叉有序树v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15二叉完全正则有序树四叉树(a)(b)(c)v1v2v3v4v5v6v7v8v9v10二叉v1v2v3v164、r叉树的子树定义：设T为一棵根树，∀v∈V(T)，称v及其后代的导出子图Tv为T的以v为根的根子树．如：二叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树．v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v2v4v5

v8v9v10v11v3v6v7v12v13v14v15左子树右子树4、r叉树的子树v1v2v3v4v5v6v7v8v917二、根树的应用1、最优二叉树定义：设二叉树T有t片树叶v1,v2,…,vt,权分别为w1,w2,…,wt,称W(T)＝∑wi|(vi)｜为T的权，其中|(vi)｜是vi的层数（也可以是从根到该叶子的通路长度）．在所有有t片树叶,带权w1,w2，…,wt的二叉树中,总权值W(T)最小的二叉树称为最优二叉树三棵带权二叉树W(T1)＝2（2+2)+3*3+5*3+3*2＝38W(T2)＝4(3+5)+3*3+2*2+2＝47W(T3)＝3*(3+3)+5*2+2(2+2)＝36

二、根树的应用182.Huffman算法(在给定权值下,如何构造最优二叉树)给定实数(权值)：w1，w2，…，wt，按从小到大排序为w1≤w2≤…≤wt.(1)连接权为w1,w2的两片树叶,得一个分支点,其权为w1+w2(2)在w1+w2，w3，w4…，wt中选出两个权最小的，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权．(3)重复(2),直到形成t-1个分支点,t片树叶为止．例：求2，2，3，3，5的最优二叉树2.Huffman算法(在给定权值下,如何构造最优二叉树)19例：求2，2，3，3，5的最优二叉树2

243

36(2)3，3，4，5(1)2，2，3，3，5(3)4，5，695(4)6，9153

36最优二叉树总的原则是：权值较大的叶子距根较近，权值较小的可以距根较远例：给定一组权值3，5，6，9，11，14，16，18构造相应的最优二叉树例：求2，2，3，3，5的最优二叉树224336(203、前缀编码在通信中，常用二进制编码表示符号．

1）等长编码与不等长编码：不等长编码可以使总电文总长度较短2）不等长编码中编码的问题：如何识别？

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，2，…，m)中只出现0，1两个符号，则称A为二元前缀码{1，10，101，0101，1010，0100，01001}不是前缀码

{1，00，011，0101，01001，01000}

为前缀码．

{

1，01，111，1100，0111

}

不是前缀码1,10,01,101,0101a,b,c,d,e3、前缀编码1,10,01,101,0101212）利用二叉树产生二元前缀码规定二叉树的左子树的边为0，右子树的边为1

则将从根到叶子结点的通路中边的序列即为叶子的二元前缀编码111110000abcdea:00b:010c:011d:10e:1112）利用二叉树产生二元前缀码111110000abcdea:22通信中，每个字符出现的频率不同，如何使得传输效率最高？等长的编码一定不是最好的，考虑利用二元前缀码。3）最优二元前缀码给定所需编码的字符的频率,构造字符的二元前缀编码，使其总电文长度为最短－称为最优二元前缀码。先利用哈夫曼算法，生成最优二叉树；再得到最优二元前缀码通信中，每个字符出现的频率不同，如何使得传输效23例：传输100个八进制的数字，其出现的频率分别为：0-25%，1-20%，2-15%，3-10%，4-10%，5-10%，6-5%，7-5%。用最优二元前缀码传输需要多少二进制数字？用等长码传输需要多少二进制数字？先得到最优二元前缀码利用哈夫曼算法，生成最优二叉树，以频率为权值，5,5,10,10,10,15,20,256,7,3,4,5,2,1,067345210例：传输100个八进制的数字，其出现的频率分别为：0-25%245,5,10,10,10,15,20,256,7,3,4,5,2,1,0编码：6-0000；7-0001；3-001；4-010；5-011；2-100；1-101,0-1167345210总权值:（100个字符的bit数）W(T)=(5+5)*4+(10+10+10+15+20)*3+25*2=285等长码：0-000；1-001；2-010；3-011；4-100；5-101；6-110；7-111.总权值:W2=3*100=3005,5,10,10,10,15,20,2567345254、二叉树的周游（遍历）二叉树的周游：对于一棵二叉树的每一个结点都访问一次且仅一次的操作

1）做一条绕行整个二叉树的行走路线（不能穿过树枝）

2）按行走路线经过结点的位置（左边、下边、右边）得到周游的方法有三种：中序遍历（路线经过结点下边时访问结点）访问的次序：左子树－根－右子树前序遍历（路线经过结点左边时访问结点）访问的次序：根－左子树－右子树后序遍历（路线经过结点右边时访问结点）访问的次序：左子树－右子树－根4、二叉树的周游（遍历）26abcdefghijk中序遍历（次序：左－根－右)前序遍历（次序：根－左－右)后序遍历（次序：左－右－根)中序遍历:cbedgfaIkhj前序遍历:abcdefghikj后序遍历:cegfdbkijha例：给定二叉树，写出三种访问结点的序列例：给定二叉树周游的二种周游序列，画出该二叉树abcdefghijk中序遍历（次序：左－根－右)中序遍历:275、二叉排序树将一组需要排序的序列建立二叉排序树建立（不断添加结点为其子树：比根结点小的为左子树比根结点大的为右子树利用周游得出排序结果（中序遍历）5、二叉排序树28例：二叉排序树

20,3,4,9,25,36,7,12,18先建成二叉排序树:以第一个数为根，比根小在左，比根大在右.20749325361218建成二叉排序树后:中序遍历(走下面):3,4,7,9,12,18,20,25,36例：二叉排序树

20,3,4,9,25,36,7,12,18296、表达式的(逆)波兰式生成给定表达式：（a*(b+c)+d*e*f)/(g+(h-i)*j)表达式是中序遍历运算符对象对象/**++*c+abf*degjh-i对应的二叉树6、表达式的(逆)波兰式生成运算符对象对象/**++*c+30/**++*c+abf*degjh-i后序遍历的结果:((a(bc+)*)(d(ef*)*)+)(g((hi-)j*)+)/逆波兰式：=abc+*def**+ghi-j*+/计算机在运算该表达式时仅按照一个原则：扫描到一个运算符就将它前面二个数进行运算/**++*c+abf*degjh-i后序遍历的结果:计算31/**++*c+abf*degjh-i前序遍历的结果：／(+(*a(+bc))(*d(*ef)))(+g(*(-hi)j))=/+*a+bc*d*ef+g*-hij运算原则：运算符入栈，当扫描到两个数就进行最上面的运算符的运算

/**++*c+abf*degjh-i前序遍历的结果：32第16章树第16章树33

第十六章树一、无向树1）定义：连通无回路（初级回路或简单回路）的无向图称为无向树，或简称树常用T表示树，平凡图称为平凡树．若无向图G至少有两个连通分支，则称G为森林．在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支结点．2）树的等价定义设G＝<V，E>是n阶m条边的无向图，则下面各命题是等价的：

(1)G是连通无回路（树）．可通过循环证明

(2)G中任意两个顶点之间存在惟一的路径．（连通则存在路径，若不唯一，不同路径则构成回路）

(3)G中无回路且m=n-1．有长大于等于2的回路都与唯一路径矛盾。对结点进行归纳：n=1平凡图m=0=n-1；设n=k成立；n=k+1时两个结点有唯一的路，去掉则为两个连通分支（各自满足假设）

m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1

(4)G是连通的且m=n-1．

若不连通，对各个(s>=2)连通分支是树且有mi=ni-1m=n-ss>=2矛盾第十六章树34(5)G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的初级回路．(6)G是连通的，但删去任何一条边后，所得图不连通．

G连通：若存在二个结点无通路，则在二个结点添加边后不会出现回路3）树的性质对于给定的无向图—树是边数最小的连通图（m<n-1则不连通）树是边数最多的无回路图（m>n-1则有回路）结点的度：Σd(vi)=2m=2(n-1)

定理：设T是n阶非平凡的无向树，则T中至少有

片树叶

设：有x片树叶，其余结点度数至少为2

x+2(n-x)<=2(n-1)

例：无向树T中度为4、3、2的结点各一个，其余为树叶，树叶＝？

4+3+2+k=2(3+k-1)(5)G中没有回路，但在任何两个不同的顶点之间加一条新边，在354)阶数n比较小的所有非同构的无向树．例1：画出6阶所有非同构的无向树．

m=n-1=5从树的节点之和来分析：结点之和为10分配给6个结点

111115111124111133111223112222例2：7阶无向树中有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3．试画出满足要求的所有非同构的无向树．解答：从树的节点之和来分析：7阶无向树的边数m=（），于是∑d(vi)＝12＝3＋3+d(v5)+d(v6)+d(v7)

1112223加入2，2，2如何组成结点的度数序列使之不同构

主要分析：度为3的结点v与其三个邻接点的关系

邻接关系不同就能得到不同构的树三个邻接点度数：1121222224)阶数n比较小的所有非同构的无向树．36

4）任何无向连通图G，都存在生成树

无向连通图G的生成树是不唯一的

4）任何无向连通图G，都存在生成树

373、生成树的应用要建6个工厂，修建连接的通路（见图），为使5处都有路相通，至少要建几条路？如何铺设？由于n=6所以建5条路即可4、无向图G的生成树的确定：二种方法：1、破圈法：每次去掉回路中的一条边，去掉总数为m-n+1条弦

2、避圈法：由一个结点开始选一条边，逐渐添加与边关联的结点（只要不构成回路即可）

直到所有结点被添加，(挑选n-1条边）3、生成树的应用383、带权图的最小生成树

(1)定义5设无向连通带权图G＝<V，E，W>，T是G的一棵生成树．

T的各边权之和称为T的权，记作W(T)；

G的所有生成树中权最小的生成树称为G的最小生成树。(2)最小生成树的求法（这里介绍避圈法Kruskal算法)

设n阶无向连通带权圈G＝<V，E,W>有m条边，不妨设G中没有环(否则，可以将所有的环先删去)，将m条边按权从小到大顺序排列，设为e1,e2，…,em；

取e1在T中，然后依次检查e2，e3，…，em.若ej(j≥2)与已在T中的边不能构成回路，则取ej在T中，否则弃去ej；算法停止时得到的T为G的最小生成树。3、带权图的最小生成树39避圈法Kruskal算法(n-1次)1121241245(1)(2)(3)(4)避圈法Kruskal算法(n-1次)1121241245(140破圈法(1)512436(3)1245(2)12435破圈法(1)512436(3)1245(2)1243541作业：P319习题十六1、2、3、4、5、13作业：42§16.3根树及其应用有向树：设D是有向图，若D的基图是无向树，

则称D为有向树.有向树中,根树最重要,故只讨论根树.一、根树

1、定义：设T是n(n≥2)阶有向树,若T中有一个顶点的入度为0,其余顶点的入度均为1,则称T为根树。入度为0的顶点称为树根（相当于文件系统的盘符）入度为1出度为0的顶点称为树叶（具体文件）。入度为1出度不为0的顶点称为内点（文件夹），内点和树根统称为分支结点§16.3根树及其应用43是否为根树(a)(b)(c)(no)(no)(yes)是否为根树(a)(b)(c)(no44从树根到T的任意顶点v的通路(路径)长度称为v的层数。v5的层数为

层。层数最大顶点的层数称为树高．将平凡树也称为根树。右图中树高为（）。v1v2v3v4v5v6v7v8v9v10在根树中，由于各有向边的方向是一致的，所以画根树时可以省去各边上的所有箭头，并将树根画在最上方．从树根到T的任意顶点v的通路(路径)长度称为v的层数。v5的452、根树中顶点的关系

定义：设T为一棵非平凡的根树，∀vi,vj∈V(T),若vi可达vj,则称vi为vj的祖先,vj为vi的后代；若vi邻接到vj(即<vi,vj>∈E(T)，称vi为vj的父亲,而vj为vi的儿子若vj,vk的父亲相同，则称vj与vk是兄弟v1v2v3v4v5v6v7v8v9v10v1为v5的祖先,v5为v1的后代；v2为v5的父亲,而v5为v2的儿子；v4与v5是兄弟2、根树中顶点的关系v1v2v3v4v5v6v7v8v9v1463、有序树设T为根树，若将T中层数相同的顶点都标定次序，则称T为有序树根据根树T中每个分支点儿子数以及是否有序，可以将根树分成下列各类：(1)若T的每个分支点至多有r个儿子，则称T为r叉树；又若r叉树是有序的，则称它为r叉有序树．

(2)若T的每个分支点都恰好有r个儿子，则称T为r叉正则树；又若T是有序的，则称它为r叉正则有序树．

(3)若T是r叉正则树，且每个树叶的层数均为树高，则称T为r叉完全正则树，又若T是有序的，则称它为r叉完全正则有序树。3、有序树47v1v2v3v4v5v6v7v8v9v10二叉有序树v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15二叉完全正则有序树四叉树(a)(b)(c)v1v2v3v4v5v6v7v8v9v10二叉v1v2v3v484、r叉树的子树定义：设T为一棵根树，∀v∈V(T)，称v及其后代的导出子图Tv为T的以v为根的根子树．如：二叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树．v1v2v3v4v5v6v7v8v9v10v11v12v13v14v15v2v4v5

v8v9v10v11v3v6v7v12v13v14v15左子树右子树4、r叉树的子树v1v2v3v4v5v6v7v8v949二、根树的应用1、最优二叉树定义：设二叉树T有t片树叶v1,v2,…,vt,权分别为w1,w2,…,wt,称W(T)＝∑wi|(vi)｜为T的权，其中|(vi)｜是vi的层数（也可以是从根到该叶子的通路长度）．在所有有t片树叶,带权w1,w2，…,wt的二叉树中,总权值W(T)最小的二叉树称为最优二叉树三棵带权二叉树W(T1)＝2（2+2)+3*3+5*3+3*2＝38W(T2)＝4(3+5)+3*3+2*2+2＝47W(T3)＝3*(3+3)+5*2+2(2+2)＝36

二、根树的应用502.Huffman算法(在给定权值下,如何构造最优二叉树)给定实数(权值)：w1，w2，…，wt，按从小到大排序为w1≤w2≤…≤wt.(1)连接权为w1,w2的两片树叶,得一个分支点,其权为w1+w2(2)在w1+w2，w3，w4…，wt中选出两个权最小的，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权．(3)重复(2),直到形成t-1个分支点,t片树叶为止．例：求2，2，3，3，5的最优二叉树2.Huffman算法(在给定权值下,如何构造最优二叉树)51例：求2，2，3，3，5的最优二叉树2

243

36(2)3，3，4，5(1)2，2，3，3，5(3)4，5，695(4)6，9153

36最优二叉树总的原则是：权值较大的叶子距根较近，权值较小的可以距根较远例：给定一组权值3，5，6，9，11，14，16，18构造相应的最优二叉树例：求2，2，3，3，5的最优二叉树224336(523、前缀编码在通信中，常用二进制编码表示符号．

1）等长编码与不等长编码：不等长编码可以使总电文总长度较短2）不等长编码中编码的问题：如何识别？

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，2，…，m)中只出现0，1两个符号，则称A为二元前缀码{1，10，101，0101，1010，0100，01001}不是前缀码

{1，00，011，0101，01001，01000}

为前缀码．

{

1，01，111，1100，0111

}

不是前缀码1,10,01,101,0101a,b,c,d,e3、前缀编码1,10,01,101,0101532）利用二叉树产生二元前缀码规定二叉树的左子树的边为0，右子树的边为1

则将从根到叶子结点的通路中边的序列即为叶子的二元前缀编码111110000abcdea:00b:010c:011d:10e:1112）利用二叉树产生二元前缀码111110000abcdea:54通信中，每个字符出现的频率不同，如何使得传输效率最高？等长的编码一定不是最好的，考虑利用二元前缀码。3）最优二元前缀码给定所需编码的字符的频率,构造字符的二元前缀编码，使其总电文长度为最短－称为最优二元前缀码。先利用哈夫曼算法，生成最优二叉树；再得到最优二元前缀码通信中，每个字符出现的频率不同，如何使得传输效55例：传输100个八进制的数字，其出现的频率分别为：0-25%，1-20%，2-15%，3-10%，4-10%，5-10%，6-5%，7-5%。用最优二元前缀码传输需要多少二进制数字？用等长码传输需要多少二进制数字？先得到最优二元前缀码利用哈夫曼算法，生成最优二叉树，以频率为权值，5,5,10,10,10,15,20,256,7,3,4,5,2,1,067345210例：传输100个八进制的数字，其出现的频率分别为：0-25%565,5,10,10,10,1