离散数学课件 第七章 树

离散数学

Discrete

Mathematics第七章树7.1无向树及生成树7.2根树7.3应用27.1无向树及生成树第7章树

无向树的基本概念和性质生成树及算法

3离散数学无向树的基本概念和性质4定义7.1

不含回路的连通无向图称为无向树，简称树。每个连通分支均是树的非连通图称为森林。平凡图称为平凡树。树中度为1的顶点称为树叶，度数大于等于2的顶点称为分支点。例如，图7.1中（a）、（b）、（c）、（d）都是树。离散数学图7.1无向树的实例无向树的性质5

离散数学无向树的性质6定理7.2n阶非平凡的树中至少有2个树叶。证明

设阶非平凡的树中有m条边，因为是连通图，所以每个顶点的度数都大于等于1，设有片树叶，则有n-k个顶点的度数大于等于2。由握手定理，2m≥k+2(n-k)

由定理7.1，m=n-1，代入上式得2(n-1)≥k+2(n-k)整理得k≥2证毕。离散数学无向树的性质7例7.1

计算6阶非同构的无向树的个数。解

顶点数n=6，边数m=n-1=5，总度数为2×5=10，每个顶点的度数都大于等于1且小于等于5，因此顶点度数分配如下：（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根据每种度数分配情况，将非同构的树都画出来：（1）（2）（3）（5）各有1棵非同构的树，而（4）有2棵非同构的树，共6棵非同构的树，分别对应图7.2所示各图。离散数学图7.26阶非同构无向树无向树的性质8例7.2

在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，则该树共有多少个4度顶点？解

设x有个4度顶点，则顶点数n=7+3+x=10+x，边数为m=n-1=9+x。由握手定理可知。4x+3×3+7=2(9+x)解得x=1，故有1个4度顶点。离散数学生成树9

离散数学图7.3生成树和余树生成树10定理7.3

任何无向连通图都有生成树.证

设G是一个无向连通图，如果G中无回路，则G本身就是树，当然也是G的生成树。如果G中存在回路C，则删除C上任意一条边，图依然是连通的，如果还有回路，就再删除此回路上的一条边，直到图中无回路为止，最后得到一个连通无回路的生成子图，即为G的生成树。定理7.3的证明过程给出了求连通图生成树的一种算法，称为“破圈法”，算法的关键是判断G中是否有回路。若有回路，则删除回路中的一条边，直到剩下的图中无回路为止。推论

设n阶无向连通图有m条边,则m

n

1.证明根据定理7.3，G有生成树，生成树中有n-1条边，则m

n

1。离散数学生成树11例7.3用破圈法求图7.4所示无向连通图的生成树。离散数学

图7.4无向连通图解

图7.4中有6个顶点，9条边，生成树中应该保留5条边，根据破圈法的思想，可依次删除4条边，删除边的目的是破坏掉图中的回路，并且保证图仍然是连通的。如可依次删除(v1,v6)、(v5,v6)、(v4,v5)、(v3,v4)，如图7.5（a）~图7.5（d）所示。图7.5（d）就是图7.4的一棵生成树。图7.5用破圈法构造图7.4所示无向连通图的生成树的过程生成树12一个连通图的生成树可能不唯一，如图7.6（a）~7.6（c）也都是图7.4的生成树。除了破圈法，还可以利用深度优先搜索算法或者广度优先搜索算法等方法构造生成树。离散数学图7.6连通图7.4的生成树最小生成树13

离散数学算法14

离散数学算法15例7.4用Kruskal算法求图7.7所示赋权图的最小生成树。离散数学解

图7.7中有6个顶点，根据Kruskal算法的思想，可依次选取边(v1,v5)、(v2,v3)、(v1,v2)、(v2,v6)、(v2,v4)，加入到初始时只有个顶点而无边的非连通图如图7.8（a）~图7.8（e）所示。图7.8（e）就是图7.7的一棵最小生成树。7.2根树第7章树

有向树与根树根子树与有序树根树与有序树的分类

16离散数学有向树和根树17定义7.5对一个有向图G，若略去有向边的方向所得无向图为一棵无向树，则称G为有向树。一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根树。入度为0的顶点称为树根，入度为1、出度为0的顶点称为树叶，入度为1、出度大于0的顶点称为分支点。在画根树时，通常把树根放在最上方，边的方向都向下或者斜下方，并省掉箭头，如图7.9所示。在图中，v1为树根，v3、v5、v6、v7为树叶，v1、v2、v4为分支点。离散数学图7.9根树有向树和根树18在根树T中，从树根到顶点v的通路长度称为v的层数，记为l(v)。称层数相同的顶点在同一层上。顶点的最大层数称为树的树高，也称为树的深度，记为h(T)。在图7.9所示的根树中，根v1在第0层上，v2、v3、v4在第1层上，v5、v6、v7在第2层上，树高为2。（注：也可以规定根在第1层，在第2层上，以此类推。）。一棵根树类似于家族树，可以规定顶点之间的关系如下：（1）若顶点u邻接到顶点v，则称v为u的儿子，u为v的父亲；（2）若v、w有同一个父亲，则v、w称为兄弟；（3）从根顶点到树中任意一个顶点都有唯一的路径；（4）若u可达s，则u到s路径上的所有顶点（不包括s）都称为s的祖先；（5）u的所有后继顶点都称为u的后代。离散数学根子树与有序树19定义7.6

设T为一棵根树，v为T中的一个顶点且不是树根，称v及其后代导出的子图T’为T的以v为根的子树，简称根子树。定义7.7如果对根树每层上的顶点规定次序，这样的根树为有序树。离散数学根树与有序树的分类20定义7.8

设T为一棵根树，（1）若T的每个分支点至多有r个儿子，则称T为r叉树。（2）若T的每个分支顶点都恰好有r个儿子，则称T为r叉正则树。（3）若r叉正则树T是有序的，则称T是r叉正则树。定义7.9设T为非平凡根树，如果T的每个分支点至多有2个儿子，则称T为二叉树；若T的每个分支点都恰好有2个儿子，则称T为正则二叉树。若T是正则二叉树，且每片树叶的层数均为树高，则称T为完全正则二叉树（满正则二叉树）。离散数学根树与有序树的分类21定义7.10

设T为二叉树，∀v∈V(T)，则称v的两个儿子中左边的顶点为其左儿子顶点，右边的顶点为其右儿子顶点；称以v的左儿子顶点为根的根子树为v的左子树，以v的右儿子顶点为根的根子树为v的右子树。图7.10中是3棵二叉树，其中图7.10（b）是正则二叉树，图7.10（c）是完全正则二叉树。离散数学7.3应用第7章树

前缀编码哈夫曼树哈夫曼算法

22离散数学前缀编码23在数据通信、数据压缩问题中，需要把数据文件转换成由二进制字符0、1组成的二进制串，称之为编码。国际通用的字符编码ASCII码（美国信息交换标准码）使用7位二进制串表示一个字符。在某些特殊情况下，为了提高效率需要使用不等长的编码。例7.5

设数据文件为“AABBCDDAAAAABBBB”，该如何设计编码方案？分析

第一种方案，采用等长编码，即每个字符的编码长度一致，如表8.1所示：

离散数学前缀编码24这种编码的特点是：（1）每个字符编码的长度相同。例如可将本例中长度为16的原文件，转换为长度为32的二进制串：“00000101101111000000000001010101”。（2）能够准确无误地解码。将每两位二进制数划分一组，译回原文件形式。在等长编码中，没有考虑到各字符的出现次数，所以效率不高。第二种方案，采用不等长编码，统计每个字符的出现次数，出现次数多的字符，用较短的编码。例如采用表7.2所示的编码方案：

离散数学前缀编码25此时原文件可转换为二进制串：“0011001111000001111”，长度只有19，但是解码存在二义性，例如“0011”可以译为“AABB”、“AAD”、“CBB”、“CD”等，所以这种编码方案是不可行的。之所以会出现二义性，是因为“0”是“00”的前缀（最左子串），“1”是“11”的前缀。为了避免这种情况出现，通常采用的是一种二元前缀码，其定义如下：

定义7.11

设

=

1

2…

n，

i∈{0,1},(i=1,2...n)是长度为n的符号串，称其最左子串

1

2…

j(i≤j<n)为

的前缀。设B={

1,

2,…,

m}是一个符号串集合，若对于任意的i≠j，

i与

j互不为前缀，则称B为前缀编码。第三种方案，设计如表7.3所示的不等长前缀编码。离散数学前缀编码26采用这种编码，原文件可转换为二进制串：“0010101101111110000010101010”，长度为28，与等长编码相比，提高了效率，而且解码时不再有二义性，因此是一种可行的压缩编码方案。那么如何得到这样的编码呢？DavidA.Huffman在1952年提出了一种基于哈夫曼树（最优二叉树）的编码方案，称为哈夫曼编码，广泛应用于数据压缩、信息传输、模式识别、数据分类等领域。离散数学哈夫曼树27定义7.12设二叉树T有t片树叶v1,v2,...vt，树叶的权值分别为w1,w2,...wt，T的带权路径长度WPL(T)（WeightedPathLength）定义为：其中li是树叶vi的层数，即从树根到该树叶的路径长度。在所有含t片树叶，带权值w1,w2,...wt的二叉树中，WPL最小的二叉树称为最优二叉树或哈夫曼树。例7.6

图7.11所示的二叉树T1、T2、T3都是带权7，6，1，2的二叉树，分别计算其带权路径长度。离散数学图7.11带权二叉树哈夫曼树28解WPL(T1)=7×2+6×2+1×2+2×2=32WPL(T2)=7×3+6×3+2×2+1×1=44WPL(T3)=7×1+6×2+1×3+2×3=28可以验证，是所有带权7，6，1，2的二叉树可能具有的最小带权路径长度值，也就是说是一棵哈夫曼树。离散数学哈夫曼算法29Step1.初始化：构造棵只有一个根顶点的二叉树，n个根顶点的权值分别是给定的n个权值，得到一个二叉树集合。Step2.选取与合并：从二叉树集合中选取根顶点权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根顶点的权值为其左、右子树根顶点的权值之和。Step3.删除与加入：从集合中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合中。Step4.重复：重复步骤2和3，直到集合中只剩下一棵二叉树为止，这棵二叉树就是哈夫曼树。离散数学哈夫曼算法30例7.7

利用哈夫曼算法求带权7，6，1，2的哈夫曼树。解

图7.12给出了求哈夫曼树的过程，哈夫曼树如图7.12（d）所示，其WPL(T)=28。离散数学图7.12求解哈夫曼树的过程显然，哈夫曼树不唯一。哈夫曼算法31哈夫曼树的特点有：（1）没有孩子数为1的分支顶点，因为构造时都是两个顶点合并。故哈夫曼树一定是正则二叉树。（2）n个叶子顶点的哈夫曼树共有2n-1个顶点。（3）哈夫曼树的任意非叶顶点的左右子树交换后仍是哈夫曼树。（4）对同一组权值，可能存在多棵不同构的哈夫曼树，但它们的带权路径长度相同。离散数学哈夫曼编码32Step1.设需要编码的字符集为{c1,c2,...,cn}，它们在字符串中出现的频率为{w1,w2,...,wn}。Step2.以这些字符作为叶顶点，以它们的频率作为叶顶点的权值，构造一棵哈夫曼树。Step3.约定在哈夫曼树的左分支上标记0，右分支上标记1，则从根顶点到每个叶顶点的路径上的0、1序列即为该叶顶点对应字符的编码。离散数学哈夫曼编码33例7.3中，字符A、B、C、D出现的次数分别为7，6，1，2，在由例7.5求出的哈夫曼树的左分支上标记0，右分支上标记1，如图7.13所示：离散数学图7.13在哈夫曼树上进行标