离散数学第七章第八节

1、1第7-8讲 根树及其应用1. 有向树2. m叉树3. 最优树4. 前缀码5. 第7-8讲 作业21、有向树（1）定义1 如果一个有向图在不考虑边的方向时是树，则称之为有向树。定义2 一棵有向树，如果恰有一个结点的入度为0，其余所有结点的入度都为1，则称为根树。 入度为0的结点称为根；出度为0的结点称为叶；出度不为0的结点称为分枝点或内点。31、有向树（2） 在一棵根树中，从根到某个结点的单向通路的长度(即边数)是固定的，它叫做该结点的层次。 左图中，左图中，b称为称为a的儿子，的儿子， a称为称为b的父亲；的父亲； a称为称为c的祖先，的祖先， c称为称为a的后裔。的后裔。对其它的结点对其它

2、的结点有类似的说法。有类似的说法。42、m叉树（1）定义3 在根树中，若每个结点的出度小于等于m，则称该树为m叉树。如果每个结点的出度恰好等于m或0，则称该树为完全m叉树。如果完全m叉树所有树叶的层次都相同，则称为正则m叉树。 图图4 4中中,(1),(1)是三叉树，是三叉树，(2)(2)是完全二叉树，是完全二叉树，(3)(3)是正则二叉树。是正则二叉树。52、m叉树（2）例1 用m叉树表示实际问题。 M和和E两人进行网球比赛，如果一人连胜两局或一共胜两人进行网球比赛，如果一人连胜两局或一共胜三局，则比赛结束，试用二叉树表示比赛可能发生的各种三局，则比赛结束，试用二叉树表示比赛可能发生的各种情

3、况。情况。解：用二叉树的分枝点表示每局赛解：用二叉树的分枝点表示每局赛事，每局比赛的胜负标在其两个儿事，每局比赛的胜负标在其两个儿子结点的旁边。从树根到树叶的每子结点的旁边。从树根到树叶的每一条路对应比赛可能发生的一种情一条路对应比赛可能发生的一种情况：况： EE，MM ； EMM ，MEE ； EMEE，MEMM； EMEME，EMEMM，MEMEE， MEMEM。62、m叉树（3）定理1 设有完全m叉树，其树叶数为t，分枝点数为I，则 (m-1)i=t-1证：可将完全可将完全m m叉树视为每局有叉树视为每局有m m位选手参加比赛的单淘汰位选手参加比赛的单淘汰赛计划表。树叶数赛计划表。树叶数

4、t t表示参加比赛的选手数，分枝点表示表示参加比赛的选手数，分枝点表示比赛的局数。因每局比赛将淘汰比赛的局数。因每局比赛将淘汰(m-1)(m-1)位位选手，故比赛结选手，故比赛结果共要淘汰果共要淘汰(m-1)i(m-1)i位位选手，最后得出一位冠军。因此选手，最后得出一位冠军。因此(m-(m-1)i+1=t1)i+1=t，即，即 (m-1)i=t-1(m-1)i=t-1。例如右图所示为例如右图所示为9位选位选手参加比赛的情况：手参加比赛的情况： t=9,i=4,m=3。72、m叉树（4）定理4设完全二叉树有n个分枝点(含根结点)，且内部通路长度的总和为L，外部通路长度的总和为E，则E=L+2n

5、。 证：对分枝点数对分枝点数n n进行归纳证明。当进行归纳证明。当n=1n=1时，时，E=2E=2，L=0L=0，故公式，故公式成立。假设成立。假设n=k-1n=k-1时成立。时成立。 当当n=kn=k时，若删去一个分枝点时，若删去一个分枝点v(v(即删除该分枝点的儿子即删除该分枝点的儿子) )。设。设该分枝点的通路长度为该分枝点的通路长度为e e，且，且v v的两个儿子是树叶，得出的新树的两个儿子是树叶，得出的新树为为TT。与原树相比，。与原树相比，TT减少了两片通路长度为减少了两片通路长度为e+1e+1的树叶和的树叶和一个通路长度为一个通路长度为e e的分枝点，因的分枝点，因TT有有k-1

6、k-1个分枝点，所以个分枝点，所以E=L+2(k-1)E=L+2(k-1)。而在原树中，。而在原树中，E=E+2(e+1)-e=E+e+2E=E+2(e+1)-e=E+e+2，L=L+eL=L+e。从这两式解出。从这两式解出EE和和LL代入前一式并整理得代入前一式并整理得E=L+2kE=L+2k。证毕。证毕。定义4 在根树中，从树根到某结点的通路的边数叫该结点的通路长度。将分枝点的通路长度称为内部通路长度，树叶的通路长度叫外部通路长度。83、最优树（1）定义5 设带权二叉树中权为wi的树叶的通路长度为L(wi)，将称为带权二叉树的权。 在所有带权w1, w2, .wt的二叉树中，w(T)最小的

7、树称为最优树，又称哈夫曼树。 设二叉树有设二叉树有t t片树叶，各片树叶分别带有权数片树叶，各片树叶分别带有权数w1, w2, .wt，则该则该二叉树称为二叉树称为带权二叉树。tiiiwLwTw1)()(问题：问题：给定一组权给定一组权w w1 1, w, w2 2, .w, .wt t，如何求相应的最优树呢？，如何求相应的最优树呢？93、最优树（2）定理5 设T为带权w1 w2 wt的最优树，则 (1) 带权w1、 w2的树叶vw1、vw2是兄弟。 (2) 以树叶vw1、vw2为儿子的分枝点的通路最长。 这个定理简单的说法是：最优树中具有最小权的两片树叶这个定理简单的说法是：最优树中具有最小

8、权的两片树叶是兄弟，且其通路长度最大。是兄弟，且其通路长度最大。定理6 设T为带权w1 w2 wt的最优树，如果将以带权w1、 w2的树叶为儿子的分枝点改为带权w1+ w2的树叶得新树T，则T也是最优树。 这个定理简单的说法是：求带这个定理简单的说法是：求带t个权的最优树，可简化为求个权的最优树，可简化为求带带t-1个权的最优树。个权的最优树。103、最优树（3）例2 假定字母假定字母a,b,c,d,ea,b,c,d,e的使用频率为的使用频率为10%,17%,20%,23%,30%,10%,17%,20%,23%,30%,设计带该权数序列的最优树，并给出其二进制编码设计带该权数序列的最优树，并

9、给出其二进制编码( (哈夫曼编哈夫曼编码码) )。编码：编码：a a：100100， b b：101101， c c：0000， d d：0101， e e：1111114、前缀码（1） 在远距离通信中，在远距离通信中，常以0和1组成的字符串来传送英文字母。例如，可以用长度为例如，可以用长度为5 5的的0 0、1 1组成的字符串来表示大小写英文组成的字符串来表示大小写英文字母和标点符号。但等长编码无法实现最高的效率。统计表字母和标点符号。但等长编码无法实现最高的效率。统计表明，有些字母使用频率高，有的则低。用较短的字符串来表明，有些字母使用频率高，有的则低。用较短的字符串来表示使用频率高的字母

10、可以提高效率。示使用频率高的字母可以提高效率。 问题是如何进行编码？前面的例子已经演示了应用最优树问题是如何进行编码？前面的例子已经演示了应用最优树实现最优编码的可行性。然而，这种编码是唯一的吗？前例实现最优编码的可行性。然而，这种编码是唯一的吗？前例对字母对字母a,b,c,d,ea,b,c,d,e的编码是的编码是100100，101101，0000，0101，1111，可否采，可否采用编码用编码001001，010010，0000，0101，1010呢？假如用这个编码发送呢？假如用这个编码发送“bdbd”,”,则相应编码是则相应编码是“01001”01001”。然而接受方译码时，将得。然而接

11、受方译码时，将得出两个可能的结果：出两个可能的结果：“010-01”010-01”和和“01-001”01-001”，即，即“bdbd”和和“dada”。 产生产生二义性的原因是由于的原因是由于d d的编码的编码“01”01”是是b b的编码的编码“010”010”的前缀造成的。用前例的编码就不会出现这种二义性。的前缀造成的。用前例的编码就不会出现这种二义性。124、前缀码（2）定义6 给定一个序列的集合，如果不存在一个序列是另一个序列的前缀，则该序列的集合称为前缀码。 例如，例如，100100，101101，0000，0101，1111是前缀码，而是前缀码，而001001，010010，00

12、00，0101，1010就不是前缀码。就不是前缀码。定理7 任意一棵二叉树对应一个前缀码。证：给定一棵二叉树，从每个分枝点出发，将左枝标为给定一棵二叉树，从每个分枝点出发，将左枝标为0，右枝标为右枝标为1，则每片树叶对应一个，则每片树叶对应一个0和和1组成的序列，该序列组成的序列，该序列是从树根到该树叶的通路上各边标号组成的。显然，没有一是从树根到该树叶的通路上各边标号组成的。显然，没有一片树叶对应的序列是另一片树叶对应序列的片树叶对应的序列是另一片树叶对应序列的前缀。所以前缀。所以任意任意一棵二叉树对应一个前缀码。一棵二叉树对应一个前缀码。134、前缀码（3）定理8 任意一个前缀码对应一棵二

13、叉树。证：设设h是某个前缀码中最长序列的长度。作一棵高为是某个前缀码中最长序列的长度。作一棵高为h的的正则二叉树，将每个分枝点的左、右枝分别标以正则二叉树，将每个分枝点的左、右枝分别标以0和和1，则，则每片树叶对应一个每片树叶对应一个0和和1组成的序列，该序列是从树根到该组成的序列，该序列是从树根到该树叶的通路上各边标号组成的。因此，长度不超过树叶的通路上各边标号组成的。因此，长度不超过h的每个的每个0和和1组成的序列必对应一个结点。组成的序列必对应一个结点。 将对应于前缀码中的每个序列的结点给予一个标记，并将对应于前缀码中的每个序列的结点给予一个标记，并删去标记结点的后裔及由它们射出的边。再

14、删去未加标记的删去标记结点的后裔及由它们射出的边。再删去未加标记的树叶，得到一棵新的二叉树，其树叶就对应给定的树叶，得到一棵新的二叉树，其树叶就对应给定的前缀码。前缀码。144、前缀码（4）例3 给定前缀码给定前缀码000000，001001，0101，11，求对应的二叉树，求对应的二叉树。解：作一棵高为作一棵高为3的正则二叉树；标记对应前缀码的结点，的正则二叉树；标记对应前缀码的结点， 并删去标记结点的后裔。并删去标记结点的后裔。154、前缀码（5） 由前缀码和二叉树的对应关系可知，如果给定的由前缀码和二叉树的对应关系可知，如果给定的前缀码前缀码对应的二叉树是对应的二叉树是完全完全二叉树二叉树，则根据此，则根据此前缀码可对前缀码可对任意任意二二进制序列译码进制序列译码。 例如，由前例中的例如，由前例中的前缀码前缀码000000，001001，0101，11可对任意二可对任意二进制序列译码。随意写一个由进制序列译码。随意写一个由0和和1组成的字符串，例如：组成的字符串，例如： 00010011011101001它可译为且只能译为：它可译为且只能译为： 000，1，001，1，01，1，1，01，001 如果被译的序列的最